logicaffeine_proof/
linarith_solve.rs1use std::collections::BTreeMap;
10
11use crate::ProofTerm;
12
13#[derive(Clone, Debug, PartialEq, Eq)]
16pub struct LinExpr {
17 pub coeffs: BTreeMap<String, i64>,
18 pub constant: i64,
19}
20
21impl LinExpr {
22 fn constant(c: i64) -> Self {
23 LinExpr {
24 coeffs: BTreeMap::new(),
25 constant: c,
26 }
27 }
28 fn var(name: &str) -> Self {
29 let mut coeffs = BTreeMap::new();
30 coeffs.insert(name.to_string(), 1);
31 LinExpr {
32 coeffs,
33 constant: 0,
34 }
35 }
36 fn prune(mut self) -> Self {
37 self.coeffs.retain(|_, c| *c != 0);
38 self
39 }
40 fn add(&self, o: &Self) -> Self {
41 let mut coeffs = self.coeffs.clone();
42 for (k, v) in &o.coeffs {
43 *coeffs.entry(k.clone()).or_insert(0) += v;
44 }
45 LinExpr {
46 coeffs,
47 constant: self.constant + o.constant,
48 }
49 .prune()
50 }
51 fn neg(&self) -> Self {
52 LinExpr {
53 coeffs: self.coeffs.iter().map(|(k, v)| (k.clone(), -v)).collect(),
54 constant: -self.constant,
55 }
56 }
57 pub fn sub(&self, o: &Self) -> Self {
58 self.add(&o.neg())
59 }
60 pub fn is_const(&self) -> bool {
62 self.coeffs.is_empty()
63 }
64 fn scale(&self, k: i64) -> Self {
65 LinExpr {
66 coeffs: self
67 .coeffs
68 .iter()
69 .map(|(x, v)| (x.clone(), v * k))
70 .collect(),
71 constant: self.constant * k,
72 }
73 .prune()
74 }
75 fn is_constant(&self) -> bool {
76 self.coeffs.is_empty()
77 }
78 fn coeff(&self, v: &str) -> i64 {
79 self.coeffs.get(v).copied().unwrap_or(0)
80 }
81}
82
83pub fn parse_lin(t: &ProofTerm) -> Option<LinExpr> {
87 match t {
88 ProofTerm::Constant(s) => Some(match s.parse::<i64>() {
89 Ok(n) => LinExpr::constant(n),
90 Err(_) => LinExpr::var(s),
91 }),
92 ProofTerm::Variable(s) | ProofTerm::BoundVarRef(s) => Some(LinExpr::var(s)),
93 ProofTerm::Function(name, args) => match (name.as_str(), args.as_slice()) {
94 ("add", [a, b]) => Some(parse_lin(a)?.add(&parse_lin(b)?)),
95 ("sub", [a, b]) => Some(parse_lin(a)?.sub(&parse_lin(b)?)),
96 ("mul", [a, b]) => {
97 let (la, lb) = (parse_lin(a)?, parse_lin(b)?);
98 if la.is_constant() {
99 Some(lb.scale(la.constant))
100 } else if lb.is_constant() {
101 Some(la.scale(lb.constant))
102 } else {
103 None
104 }
105 }
106 _ => None,
107 },
108 ProofTerm::Group(_) => None,
109 }
110}
111
112#[derive(Clone, Debug)]
115struct Row {
116 e: LinExpr,
117 prov: BTreeMap<usize, i64>,
118}
119
120fn combine_prov(
121 a: &BTreeMap<usize, i64>,
122 ka: i64,
123 b: &BTreeMap<usize, i64>,
124 kb: i64,
125) -> BTreeMap<usize, i64> {
126 let mut out = BTreeMap::new();
127 for (i, v) in a {
128 *out.entry(*i).or_insert(0) += v * ka;
129 }
130 for (i, v) in b {
131 *out.entry(*i).or_insert(0) += v * kb;
132 }
133 out.retain(|_, v| *v != 0);
134 out
135}
136
137pub fn find_farkas(constraints: &[LinExpr]) -> Option<BTreeMap<usize, i64>> {
142 let mut rows: Vec<Row> = constraints
143 .iter()
144 .enumerate()
145 .map(|(i, e)| Row {
146 e: e.clone(),
147 prov: BTreeMap::from([(i, 1)]),
148 })
149 .collect();
150
151 let contradiction = |rows: &[Row]| -> Option<BTreeMap<usize, i64>> {
152 rows.iter()
153 .find(|r| r.e.is_constant() && r.e.constant > 0)
154 .map(|r| r.prov.clone())
155 };
156 if let Some(p) = contradiction(&rows) {
157 return Some(p);
158 }
159
160 let mut vars: Vec<String> = rows
162 .iter()
163 .flat_map(|r| r.e.coeffs.keys().cloned())
164 .collect();
165 vars.sort();
166 vars.dedup();
167
168 for v in vars {
169 let (mut pos, mut neg, mut zero) = (Vec::new(), Vec::new(), Vec::new());
170 for r in rows {
171 match r.e.coeff(&v) {
172 c if c > 0 => pos.push(r),
173 c if c < 0 => neg.push(r),
174 _ => zero.push(r),
175 }
176 }
177 let mut next = zero;
178 for p in &pos {
179 for n in &neg {
180 let (pc, nc) = (p.e.coeff(&v), -n.e.coeff(&v)); next.push(Row {
183 e: p.e.scale(nc).add(&n.e.scale(pc)),
184 prov: combine_prov(&p.prov, nc, &n.prov, pc),
185 });
186 }
187 }
188 rows = next;
189 if let Some(p) = contradiction(&rows) {
190 return Some(p);
191 }
192 }
193 contradiction(&rows)
194}
195
196pub fn combine(constraints: &[LinExpr], multipliers: &BTreeMap<usize, i64>) -> LinExpr {
200 let mut acc = LinExpr::constant(0);
201 for (&i, &m) in multipliers {
202 acc = acc.add(&constraints[i].scale(m));
203 }
204 acc
205}
206
207#[cfg(test)]
208#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/linarith_solve/tests.rs"]
209mod tests;