1  // Copyright (c) 2025-2026 ACDC Network
  2  // This file is part of the alphavm library.
  3  //
  4  // Alpha Chain | Delta Chain Protocol
  5  // International Monetary Graphite.
  6  //
  7  // Derived from Aleo (https://aleo.org) and ProvableHQ (https://provable.com).
  8  // They built world-class ZK infrastructure. We installed the EASY button.
  9  // Their cryptography: elegant. Our modifications: bureaucracy-compatible.
 10  // Original brilliance: theirs. Robert's Rules: ours. Bugs: definitely ours.
 11  //
 12  // Original Aleo/ProvableHQ code subject to Apache 2.0 https://www.apache.org/licenses/LICENSE-2.0
 13  // All modifications and new work: CC0 1.0 Universal Public Domain Dedication.
 14  // No rights reserved. No permission required. No warranty. No refunds.
 15  //
 16  // https://creativecommons.org/publicdomain/zero/1.0/
 17  // SPDX-License-Identifier: CC0-1.0
 18  
 19  use crate::r1cs::Variable;
 20  use alphavm_fields::Field;
 21  
 22  use std::{
 23      cmp::Ordering,
 24      ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub},
 25  };
 26  
 27  /// This represents a linear combination of some variables, with coefficients
 28  /// in the field `F`.
 29  /// The `(coeff, var)` pairs in a `LinearCombination` are kept sorted according
 30  /// to the index of the variable in its constraint system.
 31  #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 32  pub struct LinearCombination<F: Field>(pub Vec<(Variable, F)>);
 33  
 34  impl<F: Field> AsRef<[(Variable, F)]> for LinearCombination<F> {
 35      #[inline]
 36      fn as_ref(&self) -> &[(Variable, F)] {
 37          &self.0
 38      }
 39  }
 40  
 41  impl<F: Field> From<(F, Variable)> for LinearCombination<F> {
 42      #[inline]
 43      fn from((coeff, var): (F, Variable)) -> Self {
 44          LinearCombination(vec![(var, coeff)])
 45      }
 46  }
 47  
 48  impl<F: Field> From<Variable> for LinearCombination<F> {
 49      #[inline]
 50      fn from(var: Variable) -> Self {
 51          LinearCombination(vec![(var, F::one())])
 52      }
 53  }
 54  
 55  impl<F: Field> LinearCombination<F> {
 56      /// Outputs an empty linear combination.
 57      #[inline]
 58      pub fn zero() -> LinearCombination<F> {
 59          LinearCombination(Vec::new())
 60      }
 61  
 62      /// Replaces the contents of `self` with those of `other`.
 63      #[inline]
 64      pub fn replace_in_place(&mut self, other: Self) {
 65          self.0.clear();
 66          self.0.extend_from_slice(&other.0)
 67      }
 68  
 69      /// Negate the coefficients of all variables in `self`.
 70      #[inline]
 71      pub fn negate_in_place(&mut self) {
 72          self.0.iter_mut().for_each(|(_, coeff)| *coeff = -(*coeff));
 73      }
 74  
 75      /// Double the coefficients of all variables in `self`.
 76      #[inline]
 77      pub fn double_in_place(&mut self) {
 78          self.0.iter_mut().for_each(|(_, coeff)| {
 79              coeff.double_in_place();
 80          });
 81      }
 82  
 83      /// Get the location of a variable in `self`.
 84      #[inline]
 85      pub fn get_var_loc(&self, search_var: &Variable) -> Result<usize, usize> {
 86          if self.0.len() < 6 {
 87              let mut found_index = 0;
 88              for (i, (var, _)) in self.0.iter().enumerate() {
 89                  if var >= search_var {
 90                      found_index = i;
 91                      break;
 92                  } else {
 93                      found_index += 1;
 94                  }
 95              }
 96              if self.0.get(found_index).map(|x| &x.0 == search_var).unwrap_or_default() {
 97                  Ok(found_index)
 98              } else {
 99                  Err(found_index)
100              }
101          } else {
102              self.0.binary_search_by_key(search_var, |&(cur_var, _)| cur_var)
103          }
104      }
105  }
106  
107  impl<F: Field> Add<(F, Variable)> for LinearCombination<F> {
108      type Output = Self;
109  
110      #[inline]
111      fn add(mut self, coeff_var: (F, Variable)) -> Self {
112          self += coeff_var;
113          self
114      }
115  }
116  
117  impl<F: Field> AddAssign<(F, Variable)> for LinearCombination<F> {
118      #[inline]
119      fn add_assign(&mut self, (coeff, var): (F, Variable)) {
120          match self.get_var_loc(&var) {
121              Ok(found) => {
122                  self.0[found].1 += &coeff;
123                  if self.0[found].1.is_zero() {
124                      self.0.remove(found);
125                  }
126              }
127              Err(not_found) => self.0.insert(not_found, (var, coeff)),
128          }
129      }
130  }
131  
132  impl<F: Field> Sub<(F, Variable)> for LinearCombination<F> {
133      type Output = Self;
134  
135      #[inline]
136      fn sub(self, (coeff, var): (F, Variable)) -> Self {
137          self + (-coeff, var)
138      }
139  }
140  
141  impl<F: Field> Neg for LinearCombination<F> {
142      type Output = Self;
143  
144      #[inline]
145      fn neg(mut self) -> Self {
146          self.negate_in_place();
147          self
148      }
149  }
150  
151  impl<F: Field> Mul<F> for LinearCombination<F> {
152      type Output = Self;
153  
154      #[inline]
155      fn mul(mut self, scalar: F) -> Self {
156          self *= scalar;
157          self
158      }
159  }
160  
161  impl<F: Field> MulAssign<F> for LinearCombination<F> {
162      #[inline]
163      fn mul_assign(&mut self, scalar: F) {
164          self.0.iter_mut().for_each(|(_, coeff)| *coeff *= &scalar);
165      }
166  }
167  
168  impl<F: Field> Add<Variable> for LinearCombination<F> {
169      type Output = Self;
170  
171      #[inline]
172      fn add(self, other: Variable) -> LinearCombination<F> {
173          self + (F::one(), other)
174      }
175  }
176  
177  impl<F: Field> Sub<Variable> for LinearCombination<F> {
178      type Output = LinearCombination<F>;
179  
180      #[inline]
181      fn sub(self, other: Variable) -> LinearCombination<F> {
182          self - (F::one(), other)
183      }
184  }
185  
186  fn op_impl<F: Field, F1, F2>(
187      cur: &LinearCombination<F>,
188      other: &LinearCombination<F>,
189      push_fn: F1,
190      combine_fn: F2,
191  ) -> LinearCombination<F>
192  where
193      F1: Fn(F) -> F,
194      F2: Fn(F, F) -> F,
195  {
196      let mut new_vec = Vec::with_capacity(cur.0.len() + other.0.len());
197      let mut i = 0;
198      let mut j = 0;
199      while i < cur.0.len() && j < other.0.len() {
200          let self_cur = &cur.0[i];
201          let other_cur = &other.0[j];
202          match self_cur.0.cmp(&other_cur.0) {
203              Ordering::Greater => {
204                  new_vec.push((other_cur.0, push_fn(other_cur.1)));
205                  j += 1;
206              }
207              Ordering::Less => {
208                  new_vec.push(*self_cur);
209                  i += 1;
210              }
211              Ordering::Equal => {
212                  new_vec.push((self_cur.0, combine_fn(self_cur.1, other_cur.1)));
213                  i += 1;
214                  j += 1;
215              }
216          }
217      }
218      new_vec.extend_from_slice(&cur.0[i..]);
219      while j < other.0.len() {
220          new_vec.push((other.0[j].0, push_fn(other.0[j].1)));
221          j += 1;
222      }
223      LinearCombination(new_vec)
224  }
225  
226  impl<F: Field> Add<&LinearCombination<F>> for &LinearCombination<F> {
227      type Output = LinearCombination<F>;
228  
229      fn add(self, other: &LinearCombination<F>) -> LinearCombination<F> {
230          if other.0.is_empty() {
231              return self.clone();
232          } else if self.0.is_empty() {
233              return other.clone();
234          }
235          op_impl(self, other, |coeff| coeff, |cur_coeff, other_coeff| cur_coeff + other_coeff)
236      }
237  }
238  
239  impl<F: Field> Add<LinearCombination<F>> for &LinearCombination<F> {
240      type Output = LinearCombination<F>;
241  
242      fn add(self, other: LinearCombination<F>) -> LinearCombination<F> {
243          if self.0.is_empty() {
244              return other;
245          } else if other.0.is_empty() {
246              return self.clone();
247          }
248          op_impl(self, &other, |coeff| coeff, |cur_coeff, other_coeff| cur_coeff + other_coeff)
249      }
250  }
251  
252  impl<'a, F: Field> Add<&'a LinearCombination<F>> for LinearCombination<F> {
253      type Output = LinearCombination<F>;
254  
255      fn add(self, other: &'a LinearCombination<F>) -> LinearCombination<F> {
256          if other.0.is_empty() {
257              return self;
258          } else if self.0.is_empty() {
259              return other.clone();
260          }
261          op_impl(&self, other, |coeff| coeff, |cur_coeff, other_coeff| cur_coeff + other_coeff)
262      }
263  }
264  
265  impl<F: Field> Add<LinearCombination<F>> for LinearCombination<F> {
266      type Output = Self;
267  
268      fn add(self, other: Self) -> Self {
269          if other.0.is_empty() {
270              return self;
271          } else if self.0.is_empty() {
272              return other;
273          }
274          op_impl(&self, &other, |coeff| coeff, |cur_coeff, other_coeff| cur_coeff + other_coeff)
275      }
276  }
277  
278  impl<F: Field> Sub<&LinearCombination<F>> for &LinearCombination<F> {
279      type Output = LinearCombination<F>;
280  
281      fn sub(self, other: &LinearCombination<F>) -> LinearCombination<F> {
282          if other.0.is_empty() {
283              let cur = self.clone();
284              return cur;
285          } else if self.0.is_empty() {
286              let mut other = other.clone();
287              other.negate_in_place();
288              return other;
289          }
290  
291          op_impl(self, other, |coeff| -coeff, |cur_coeff, other_coeff| cur_coeff - other_coeff)
292      }
293  }
294  
295  impl<'a, F: Field> Sub<&'a LinearCombination<F>> for LinearCombination<F> {
296      type Output = LinearCombination<F>;
297  
298      fn sub(self, other: &'a LinearCombination<F>) -> LinearCombination<F> {
299          if other.0.is_empty() {
300              return self;
301          } else if self.0.is_empty() {
302              let mut other = other.clone();
303              other.negate_in_place();
304              return other;
305          }
306          op_impl(&self, other, |coeff| -coeff, |cur_coeff, other_coeff| cur_coeff - other_coeff)
307      }
308  }
309  
310  impl<F: Field> Sub<LinearCombination<F>> for &LinearCombination<F> {
311      type Output = LinearCombination<F>;
312  
313      fn sub(self, mut other: LinearCombination<F>) -> LinearCombination<F> {
314          if self.0.is_empty() {
315              other.negate_in_place();
316              return other;
317          } else if other.0.is_empty() {
318              return self.clone();
319          }
320  
321          op_impl(self, &other, |coeff| -coeff, |cur_coeff, other_coeff| cur_coeff - other_coeff)
322      }
323  }
324  
325  impl<F: Field> Sub<LinearCombination<F>> for LinearCombination<F> {
326      type Output = LinearCombination<F>;
327  
328      fn sub(self, mut other: LinearCombination<F>) -> LinearCombination<F> {
329          if other.0.is_empty() {
330              return self;
331          } else if self.0.is_empty() {
332              other.negate_in_place();
333              return other;
334          }
335          op_impl(&self, &other, |coeff| -coeff, |cur_coeff, other_coeff| cur_coeff - other_coeff)
336      }
337  }
338  
339  impl<F: Field> Add<(F, &LinearCombination<F>)> for &LinearCombination<F> {
340      type Output = LinearCombination<F>;
341  
342      #[allow(clippy::suspicious_arithmetic_impl)]
343      fn add(self, (mul_coeff, other): (F, &LinearCombination<F>)) -> LinearCombination<F> {
344          if other.0.is_empty() {
345              return self.clone();
346          } else if self.0.is_empty() {
347              let mut other = other.clone();
348              other.mul_assign(mul_coeff);
349              return other;
350          }
351          op_impl(self, other, |coeff| mul_coeff * coeff, |cur_coeff, other_coeff| cur_coeff + (mul_coeff * other_coeff))
352      }
353  }
354  
355  impl<'a, F: Field> Add<(F, &'a LinearCombination<F>)> for LinearCombination<F> {
356      type Output = LinearCombination<F>;
357  
358      #[allow(clippy::suspicious_arithmetic_impl)]
359      fn add(self, (mul_coeff, other): (F, &'a LinearCombination<F>)) -> LinearCombination<F> {
360          if other.0.is_empty() {
361              return self;
362          } else if self.0.is_empty() {
363              let mut other = other.clone();
364              other.mul_assign(mul_coeff);
365              return other;
366          }
367          op_impl(&self, other, |coeff| mul_coeff * coeff, |cur_coeff, other_coeff| cur_coeff + (mul_coeff * other_coeff))
368      }
369  }
370  
371  impl<F: Field> Add<(F, LinearCombination<F>)> for &LinearCombination<F> {
372      type Output = LinearCombination<F>;
373  
374      #[allow(clippy::suspicious_arithmetic_impl)]
375      fn add(self, (mul_coeff, mut other): (F, LinearCombination<F>)) -> LinearCombination<F> {
376          if other.0.is_empty() {
377              return self.clone();
378          } else if self.0.is_empty() {
379              other.mul_assign(mul_coeff);
380              return other;
381          }
382          op_impl(self, &other, |coeff| mul_coeff * coeff, |cur_coeff, other_coeff| cur_coeff + (mul_coeff * other_coeff))
383      }
384  }
385  
386  impl<F: Field> Add<(F, Self)> for LinearCombination<F> {
387      type Output = Self;
388  
389      #[allow(clippy::suspicious_arithmetic_impl)]
390      fn add(self, (mul_coeff, other): (F, Self)) -> Self {
391          if other.0.is_empty() {
392              return self;
393          } else if self.0.is_empty() {
394              let mut other = other;
395              other.mul_assign(mul_coeff);
396              return other;
397          }
398          op_impl(
399              &self,
400              &other,
401              |coeff| mul_coeff * coeff,
402              |cur_coeff, other_coeff| cur_coeff + (mul_coeff * other_coeff),
403          )
404      }
405  }
406  
407  impl<F: Field> Sub<(F, &LinearCombination<F>)> for &LinearCombination<F> {
408      type Output = LinearCombination<F>;
409  
410      fn sub(self, (coeff, other): (F, &LinearCombination<F>)) -> LinearCombination<F> {
411          self + (-coeff, other)
412      }
413  }
414  
415  impl<'a, F: Field> Sub<(F, &'a LinearCombination<F>)> for LinearCombination<F> {
416      type Output = LinearCombination<F>;
417  
418      fn sub(self, (coeff, other): (F, &'a LinearCombination<F>)) -> LinearCombination<F> {
419          self + (-coeff, other)
420      }
421  }
422  
423  impl<F: Field> Sub<(F, LinearCombination<F>)> for &LinearCombination<F> {
424      type Output = LinearCombination<F>;
425  
426      fn sub(self, (coeff, other): (F, LinearCombination<F>)) -> LinearCombination<F> {
427          self + (-coeff, other)
428      }
429  }
430  
431  impl<F: Field> Sub<(F, LinearCombination<F>)> for LinearCombination<F> {
432      type Output = LinearCombination<F>;
433  
434      fn sub(self, (coeff, other): (F, LinearCombination<F>)) -> LinearCombination<F> {
435          self + (-coeff, other)
436      }
437  }
438  
439  #[cfg(test)]
440  mod tests {
441      use crate::r1cs::Index;
442  
443      use super::*;
444      use alphavm_curves::bls12_377::Fr;
445  
446      #[test]
447      fn linear_combination_append() {
448          let mut combo = LinearCombination::<Fr>::zero();
449          for i in 0..100u64 {
450              combo += (i.into(), Variable::new_unchecked(Index::Public(0)));
451          }
452          assert_eq!(combo.0.len(), 1);
453      }
454  }