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::{errors::SynthesisError, ConstraintSystem, Index, LinearCombination, OptionalVec, Variable};
 20  use alphavm_fields::Field;
 21  
 22  use cfg_if::cfg_if;
 23  use fxhash::{FxBuildHasher, FxHashMap};
 24  use indexmap::{map::Entry, IndexMap, IndexSet};
 25  use itertools::Itertools;
 26  
 27  /// This field is the scalar field (Fr) of BLS12-377.
 28  pub type Fr = alphavm_curves::bls12_377::Fr;
 29  
 30  #[allow(dead_code)]
 31  #[derive(Debug, Clone)]
 32  enum NamedObject {
 33      Constraint(usize),
 34      Var(Variable),
 35      // contains the list of named objects that belong to it
 36      Namespace(Namespace),
 37  }
 38  
 39  #[derive(Debug, Clone, Default)]
 40  struct Namespace {
 41      children: Vec<NamedObject>,
 42      idx: NamespaceIndex,
 43  }
 44  
 45  impl Namespace {
 46      fn push(&mut self, child: NamedObject) {
 47          self.children.push(child);
 48      }
 49  }
 50  
 51  type InternedField = usize;
 52  type InternedPathSegment = usize;
 53  type NamespaceIndex = usize;
 54  
 55  #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
 56  pub struct InternedPath {
 57      parent_namespace: NamespaceIndex,
 58      last_segment: InternedPathSegment,
 59  }
 60  
 61  #[derive(PartialEq, Eq, Hash)]
 62  pub struct TestConstraint {
 63      interned_path: InternedPath,
 64      a: Vec<(Variable, InternedField)>,
 65      b: Vec<(Variable, InternedField)>,
 66      c: Vec<(Variable, InternedField)>,
 67  }
 68  
 69  #[derive(Default, Debug)]
 70  pub struct CurrentNamespace {
 71      segments: Vec<InternedPathSegment>,
 72      indices: Vec<NamespaceIndex>,
 73  }
 74  
 75  impl CurrentNamespace {
 76      fn idx(&self) -> usize {
 77          self.indices.last().copied().unwrap_or(0)
 78      }
 79  
 80      fn pop(&mut self) {
 81          assert!(self.segments.pop().is_some());
 82          assert!(self.indices.pop().is_some());
 83      }
 84  }
 85  
 86  /// Constraint system for testing purposes.
 87  pub struct TestConstraintSystem<F: Field> {
 88      // used to intern full paths in test scenarios, for get and set purposes
 89      interned_full_paths: FxHashMap<Vec<InternedPathSegment>, InternedPath>,
 90      // used to intern namespace segments
 91      interned_path_segments: IndexSet<String, FxBuildHasher>,
 92      // used to intern fields belonging to F
 93      interned_fields: IndexSet<F, FxBuildHasher>,
 94      // contains named objects bound to their (interned) paths; the indices are
 95      // used for NamespaceIndex lookups
 96      named_objects: IndexMap<InternedPath, NamedObject, FxBuildHasher>,
 97      // a stack of current path's segments and the index of the current path's
 98      // index in the named_objects map
 99      current_namespace: CurrentNamespace,
100      // the list of currently applicable constraints
101      constraints: OptionalVec<TestConstraint>,
102      // the list of currently applicable input variables
103      public_variables: OptionalVec<InternedField>,
104      // the list of currently applicable auxiliary variables
105      private_variables: OptionalVec<InternedField>,
106  }
107  
108  impl<F: Field> Default for TestConstraintSystem<F> {
109      fn default() -> Self {
110          let mut interned_path_segments = IndexSet::with_hasher(FxBuildHasher::default());
111          let path_segment = "ONE".to_owned();
112          let interned_path_segment = interned_path_segments.insert_full(path_segment).0;
113          let interned_path = InternedPath { parent_namespace: 0, last_segment: interned_path_segment };
114  
115          cfg_if! {
116              if #[cfg(debug_assertions)] {
117                  let mut interned_full_paths = FxHashMap::default();
118                  interned_full_paths.insert(vec![interned_path_segment], interned_path);
119              } else {
120                  let interned_full_paths = FxHashMap::default();
121              }
122          }
123  
124          let mut named_objects = IndexMap::with_hasher(FxBuildHasher::default());
125          named_objects.insert_full(interned_path, NamedObject::Var(TestConstraintSystem::<F>::one()));
126  
127          let mut interned_fields = IndexSet::with_hasher(FxBuildHasher::default());
128          let interned_field = interned_fields.insert_full(F::one()).0;
129  
130          let mut inputs: OptionalVec<InternedField> = Default::default();
131          inputs.insert(interned_field);
132  
133          let constraints = OptionalVec::default();
134  
135          TestConstraintSystem {
136              interned_full_paths,
137              interned_fields,
138              interned_path_segments,
139              named_objects,
140              current_namespace: Default::default(),
141              constraints,
142              public_variables: inputs,
143              private_variables: Default::default(),
144          }
145      }
146  }
147  
148  impl<F: Field> TestConstraintSystem<F> {
149      pub fn new() -> Self {
150          Self::default()
151      }
152  
153      /// Prints the constraint at which `self` and `other` differ.
154      pub fn diff(&self, other: &Self) {
155          for (i, (self_c, other_c)) in self.constraints.iter().zip(other.constraints.iter()).enumerate() {
156              let self_interned_path = self_c.interned_path;
157              let other_interned_path = other_c.interned_path;
158              if self_c.a != other_c.a {
159                  println!("A row {i} is different:");
160                  println!("self: {}", self.unintern_path(self_interned_path));
161                  println!("other: {}", other.unintern_path(other_interned_path));
162                  break;
163              }
164  
165              if self_c.b != other_c.b {
166                  println!("B row {i} is different:");
167                  println!("self: {}", self.unintern_path(self_interned_path));
168                  println!("other: {}", other.unintern_path(other_interned_path));
169                  break;
170              }
171  
172              if self_c.c != other_c.c {
173                  println!("C row {i} is different:");
174                  println!("self: {}", self.unintern_path(self_interned_path));
175                  println!("other: {}", other.unintern_path(other_interned_path));
176                  break;
177              }
178          }
179      }
180  
181      #[inline]
182      fn intern_path(&self, path: &str) -> InternedPath {
183          let mut vec = vec![];
184  
185          for segment in path.split('/') {
186              vec.push(self.interned_path_segments.get_index_of(segment).unwrap());
187          }
188  
189          *self.interned_full_paths.get(&vec).unwrap()
190      }
191  
192      fn unintern_path(&self, interned_path: InternedPath) -> String {
193          let last_segment = self.interned_path_segments.get_index(interned_path.last_segment).unwrap();
194          let mut reversed_uninterned_segments = vec![last_segment];
195  
196          let mut parent_ns = interned_path.parent_namespace;
197          while parent_ns != 0 {
198              let interned_parent_ns = self.named_objects.get_index(parent_ns).unwrap().0;
199              let parent_segment = self.interned_path_segments.get_index(interned_parent_ns.last_segment).unwrap();
200              reversed_uninterned_segments.push(parent_segment);
201              parent_ns = interned_parent_ns.parent_namespace;
202          }
203  
204          let segments = reversed_uninterned_segments.into_iter().map(|s| s.as_str()).rev();
205          Itertools::intersperse(segments, "/").collect()
206      }
207  
208      pub fn print_named_objects(&self) {
209          for TestConstraint { interned_path, .. } in self.constraints.iter() {
210              println!("{}", self.unintern_path(*interned_path));
211          }
212      }
213  
214      fn eval_lc(&self, terms: &[(Variable, InternedField)]) -> F {
215          let mut acc = F::zero();
216  
217          for &(var, interned_coeff) in terms {
218              let interned_tmp = match var.get_unchecked() {
219                  Index::Public(index) => self.public_variables[index],
220                  Index::Private(index) => self.private_variables[index],
221              };
222              let mut tmp = *self.interned_fields.get_index(interned_tmp).unwrap();
223              let coeff = self.interned_fields.get_index(interned_coeff).unwrap();
224  
225              tmp.mul_assign(coeff);
226              acc.add_assign(tmp);
227          }
228  
229          acc
230      }
231  
232      pub fn which_is_unsatisfied(&self) -> Option<String> {
233          for TestConstraint { interned_path, a, b, c } in self.constraints.iter() {
234              let mut a = self.eval_lc(a.as_ref());
235              let b = self.eval_lc(b.as_ref());
236              let c = self.eval_lc(c.as_ref());
237  
238              a.mul_assign(&b);
239  
240              if a != c {
241                  return Some(self.unintern_path(*interned_path));
242              }
243          }
244  
245          None
246      }
247  
248      #[inline]
249      pub fn is_satisfied(&self) -> bool {
250          self.which_is_unsatisfied().is_none()
251      }
252  
253      #[inline]
254      pub fn num_non_zero(&self) -> (usize, usize, usize) {
255          let mut non_zero_a = 0;
256          let mut non_zero_b = 0;
257          let mut non_zero_c = 0;
258          for TestConstraint { a, b, c, .. } in self.constraints.iter() {
259              non_zero_a += a.len();
260              non_zero_b += b.len();
261              non_zero_c += c.len();
262          }
263          (non_zero_a, non_zero_b, non_zero_c)
264      }
265  
266      #[inline]
267      pub fn num_constraints(&self) -> usize {
268          self.constraints.len()
269      }
270  
271      #[inline]
272      pub fn get_constraint_path(&self, i: usize) -> String {
273          self.unintern_path(self.constraints.iter().nth(i).unwrap().interned_path)
274      }
275  
276      pub fn set(&mut self, path: &str, to: F) {
277          let interned_path = self.intern_path(path);
278          let interned_field = self.interned_fields.insert_full(to).0;
279  
280          match self.named_objects.get(&interned_path) {
281              Some(NamedObject::Var(v)) => match v.get_unchecked() {
282                  Index::Public(index) => self.public_variables[index] = interned_field,
283                  Index::Private(index) => self.private_variables[index] = interned_field,
284              },
285              Some(e) => panic!("tried to set path `{path}` to value, but `{e:?}` already exists there."),
286              _ => panic!("no variable exists at path: {path}"),
287          }
288      }
289  
290      pub fn get(&mut self, path: &str) -> F {
291          let interned_path = self.intern_path(path);
292  
293          let interned_field = match self.named_objects.get(&interned_path) {
294              Some(NamedObject::Var(v)) => match v.get_unchecked() {
295                  Index::Public(index) => self.public_variables[index],
296                  Index::Private(index) => self.private_variables[index],
297              },
298              Some(e) => panic!("tried to get value of path `{path}`, but `{e:?}` exists there (not a variable)"),
299              _ => panic!("no variable exists at path: {path}"),
300          };
301  
302          *self.interned_fields.get_index(interned_field).unwrap()
303      }
304  
305      #[inline]
306      fn set_named_obj(&mut self, interned_path: InternedPath, to: NamedObject) -> NamespaceIndex {
307          match self.named_objects.entry(interned_path) {
308              Entry::Vacant(e) => {
309                  let ns_idx = e.index();
310                  e.insert(to);
311                  ns_idx
312              }
313              Entry::Occupied(e) => {
314                  let interned_segments = e.swap_remove_entry().0;
315                  panic!("tried to create object at existing path: {}", self.unintern_path(interned_segments));
316              }
317          }
318      }
319  
320      #[inline]
321      fn compute_path(&mut self, new_segment: &str) -> InternedPath {
322          let (interned_segment, new) = if let Some(index) = self.interned_path_segments.get_index_of(new_segment) {
323              (index, false)
324          } else {
325              self.interned_path_segments.insert_full(new_segment.to_owned())
326          };
327  
328          // only perform the check for segments not seen before
329          assert!(!new || !new_segment.contains('/'), "'/' is not allowed in names");
330  
331          let interned_path =
332              InternedPath { parent_namespace: self.current_namespace.idx(), last_segment: interned_segment };
333  
334          cfg_if! {
335              if #[cfg(debug_assertions)] {
336                  let mut full_path = self.current_namespace.segments.clone();
337                  full_path.push(interned_segment);
338                  self.interned_full_paths.insert(full_path, interned_path);
339              }
340          }
341  
342          interned_path
343      }
344  
345      #[cfg(not(debug_assertions))]
346      fn purge_namespace(&mut self, namespace: Namespace) {
347          for child_obj in namespace.children {
348              match child_obj {
349                  NamedObject::Var(var) => match var.get_unchecked() {
350                      Index::Private(idx) => {
351                          self.private_variables.remove(idx);
352                      }
353                      Index::Public(idx) => {
354                          self.public_variables.remove(idx);
355                      }
356                  },
357                  NamedObject::Constraint(idx) => {
358                      self.constraints.remove(idx);
359                  }
360                  NamedObject::Namespace(children) => {
361                      self.purge_namespace(children);
362                  }
363              }
364              self.named_objects.swap_remove_index(namespace.idx);
365          }
366      }
367  
368      #[inline]
369      fn register_object_in_namespace(&mut self, named_obj: NamedObject) {
370          if let NamedObject::Namespace(ns) = self.named_objects.get_index_mut(self.current_namespace.idx()).unwrap().1 {
371              ns.push(named_obj);
372          }
373      }
374  }
375  
376  impl<F: Field> ConstraintSystem<F> for TestConstraintSystem<F> {
377      type Root = Self;
378  
379      fn alloc<Fn, A, AR>(&mut self, annotation: A, f: Fn) -> Result<Variable, SynthesisError>
380      where
381          Fn: FnOnce() -> Result<F, SynthesisError>,
382          A: FnOnce() -> AR,
383          AR: AsRef<str>,
384      {
385          let interned_path = self.compute_path(annotation().as_ref());
386          let interned_field = self.interned_fields.insert_full(f()?).0;
387          let index = self.private_variables.insert(interned_field);
388          let var = Variable::new_unchecked(Index::Private(index));
389          let named_obj = NamedObject::Var(var);
390          self.register_object_in_namespace(named_obj.clone());
391          self.set_named_obj(interned_path, named_obj);
392  
393          Ok(var)
394      }
395  
396      fn alloc_input<Fn, A, AR>(&mut self, annotation: A, f: Fn) -> Result<Variable, SynthesisError>
397      where
398          Fn: FnOnce() -> Result<F, SynthesisError>,
399          A: FnOnce() -> AR,
400          AR: AsRef<str>,
401      {
402          let interned_path = self.compute_path(annotation().as_ref());
403          let interned_field = self.interned_fields.insert_full(f()?).0;
404          let index = self.public_variables.insert(interned_field);
405          let var = Variable::new_unchecked(Index::Public(index));
406          let named_obj = NamedObject::Var(var);
407          self.register_object_in_namespace(named_obj.clone());
408          self.set_named_obj(interned_path, named_obj);
409  
410          Ok(var)
411      }
412  
413      fn enforce<A, AR, LA, LB, LC>(&mut self, annotation: A, a: LA, b: LB, c: LC)
414      where
415          A: FnOnce() -> AR,
416          AR: AsRef<str>,
417          LA: FnOnce(LinearCombination<F>) -> LinearCombination<F>,
418          LB: FnOnce(LinearCombination<F>) -> LinearCombination<F>,
419          LC: FnOnce(LinearCombination<F>) -> LinearCombination<F>,
420      {
421          let interned_path = self.compute_path(annotation().as_ref());
422          let index = self.constraints.next_idx();
423          let named_obj = NamedObject::Constraint(index);
424          self.register_object_in_namespace(named_obj.clone());
425          self.set_named_obj(interned_path, named_obj);
426  
427          let mut intern_fields = |uninterned: Vec<(Variable, F)>| -> Vec<(Variable, InternedField)> {
428              uninterned
429                  .into_iter()
430                  .map(|(var, field)| {
431                      let interned_field = self.interned_fields.insert_full(field).0;
432                      (var, interned_field)
433                  })
434                  .collect()
435          };
436  
437          let a = intern_fields(a(LinearCombination::zero()).0);
438          let b = intern_fields(b(LinearCombination::zero()).0);
439          let c = intern_fields(c(LinearCombination::zero()).0);
440  
441          self.constraints.insert(TestConstraint { interned_path, a, b, c });
442      }
443  
444      fn push_namespace<NR: AsRef<str>, N: FnOnce() -> NR>(&mut self, name_fn: N) {
445          let name = name_fn();
446          let interned_path = self.compute_path(name.as_ref());
447          let new_segment = interned_path.last_segment;
448          let named_obj = NamedObject::Namespace(Default::default());
449          self.register_object_in_namespace(named_obj.clone());
450          let namespace_idx = self.set_named_obj(interned_path, named_obj);
451          if let NamedObject::Namespace(ref mut ns) = self.named_objects[namespace_idx] {
452              ns.idx = namespace_idx;
453          };
454  
455          self.current_namespace.segments.push(new_segment);
456          self.current_namespace.indices.push(namespace_idx);
457      }
458  
459      #[cfg(not(debug_assertions))]
460      fn pop_namespace(&mut self) {
461          let namespace = if let NamedObject::Namespace(no) =
462              self.named_objects.swap_remove_index(self.current_namespace.idx()).unwrap().1
463          {
464              no
465          } else {
466              unreachable!()
467          };
468  
469          // remove object belonging to the popped namespace
470          self.purge_namespace(namespace);
471  
472          // update the current namespace
473          self.current_namespace.pop();
474      }
475  
476      #[cfg(debug_assertions)]
477      fn pop_namespace(&mut self) {
478          // don't perform a full cleanup in test conditions, so that all the variables,
479          // constraints and namespace indices remain available throughout the tests
480  
481          self.current_namespace.pop();
482      }
483  
484      #[inline]
485      fn get_root(&mut self) -> &mut Self::Root {
486          self
487      }
488  
489      #[inline]
490      fn num_constraints(&self) -> usize {
491          self.num_constraints()
492      }
493  
494      #[inline]
495      fn num_public_variables(&self) -> usize {
496          self.public_variables.len()
497      }
498  
499      #[inline]
500      fn num_private_variables(&self) -> usize {
501          self.private_variables.len()
502      }
503  
504      #[inline]
505      fn is_in_setup_mode(&self) -> bool {
506          false
507      }
508  }