use std::cmp::Ordering;
use std::collections::{BTreeMap, BTreeSet, VecDeque};
use crate::certificate::{
AmbiguityEntry, AmbiguityKind, AutomatonData, CERT_SCHEMA, Certificate, FinitenessData,
OriginTerm, QuiverData, RelationData, Trace, TraceStep,
};
use crate::field::{Fp, PrimeField};
use crate::order::{ORDER_ID, word_cmp};
use crate::quiver::{ArrowId, Quiver};
use crate::relation::{Presentation, Relation};
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct CompletionLimits {
pub max_basis: usize,
pub max_word_len: usize,
pub max_steps: usize,
}
impl Default for CompletionLimits {
fn default() -> Self {
CompletionLimits {
max_basis: 4096,
max_word_len: 64,
max_steps: 1_000_000,
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum TruncationReason {
BasisBudget,
WordLenBudget,
StepBudget,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct TruncationDiagnostics {
pub basis_len: usize,
pub pending_ambiguities: usize,
pub steps_used: usize,
pub reason: TruncationReason,
}
#[derive(Clone, Debug, PartialEq, Eq)]
#[allow(clippy::large_enum_variant)]
pub enum Outcome {
Complete(Certificate),
Truncated(TruncationDiagnostics),
}
type Word = Vec<ArrowId>;
#[derive(Clone, Debug)]
struct Poly {
terms: Vec<(Fp, Word)>,
}
impl Poly {
fn zero() -> Poly {
Poly { terms: Vec::new() }
}
fn is_zero(&self) -> bool {
self.terms.is_empty()
}
}
type Origin = BTreeMap<(usize, Word, Word), Fp>;
#[derive(Clone, Debug)]
struct BasisElem {
poly: Poly,
origin: Origin,
}
fn lead_word(elem: &BasisElem) -> &Word {
&elem.poly.terms[0].1
}
fn concat2(a: &[ArrowId], b: &[ArrowId]) -> Word {
a.iter().chain(b).copied().collect()
}
fn concat3(a: &[ArrowId], b: &[ArrowId], c: &[ArrowId]) -> Word {
a.iter().chain(b).chain(c).copied().collect()
}
fn raw_word(word: &[ArrowId]) -> Vec<u32> {
word.iter().map(|a| a.0).collect()
}
fn poly_from_relation(relation: &Relation) -> Poly {
Poly {
terms: relation
.terms()
.iter()
.map(|(c, w)| (*c, w.arrows().to_vec()))
.collect(),
}
}
fn poly_data(poly: &Poly) -> RelationData {
poly.terms
.iter()
.map(|(c, w)| (c.raw(), raw_word(w)))
.collect()
}
fn add_scaled(
field: PrimeField,
base: &Poly,
c: Fp,
left: &[ArrowId],
src: &Poly,
right: &[ArrowId],
) -> Poly {
let addend: Vec<(Fp, Word)> = src
.terms
.iter()
.map(|(k, w)| (field.mul(c, *k), concat3(left, w, right)))
.collect();
let mut merged = Vec::with_capacity(base.terms.len() + addend.len());
let mut i = 0;
let mut j = 0;
while i < base.terms.len() && j < addend.len() {
match word_cmp(&base.terms[i].1, &addend[j].1) {
Ordering::Greater => {
merged.push(base.terms[i].clone());
i += 1;
}
Ordering::Less => {
merged.push(addend[j].clone());
j += 1;
}
Ordering::Equal => {
let sum = field.add(base.terms[i].0, addend[j].0);
if !sum.is_zero() {
merged.push((sum, base.terms[i].1.clone()));
}
i += 1;
j += 1;
}
}
}
merged.extend_from_slice(&base.terms[i..]);
merged.extend(addend.into_iter().skip(j));
Poly { terms: merged }
}
fn origin_add_scaled(
field: PrimeField,
target: &mut Origin,
c: Fp,
left: &[ArrowId],
src: &Origin,
right: &[ArrowId],
) {
for ((index, l, r), k) in src {
let key = (*index, concat2(left, l), concat2(r, right));
let current = target.get(&key).copied().unwrap_or(field.zero());
let sum = field.add(current, field.mul(c, *k));
if sum.is_zero() {
target.remove(&key);
} else {
target.insert(key, sum);
}
}
}
fn make_monic(field: PrimeField, poly: &mut Poly, origin: &mut Origin) {
let lead_coeff = poly.terms[0].0;
if lead_coeff == field.one() {
return;
}
let inv = field.inv(lead_coeff);
for (c, _) in &mut poly.terms {
*c = field.mul(inv, *c);
}
for c in origin.values_mut() {
*c = field.mul(inv, *c);
}
}
fn find_factor(word: &[ArrowId], pattern: &[ArrowId]) -> Option<usize> {
if pattern.len() > word.len() {
return None;
}
(0..=word.len() - pattern.len()).find(|&start| word[start..start + pattern.len()] == *pattern)
}
fn find_reduction(
basis: &[BasisElem],
skip: Option<usize>,
poly: &Poly,
) -> Option<(usize, usize, usize)> {
for (term_index, (_, word)) in poly.terms.iter().enumerate() {
for (basis_index, elem) in basis.iter().enumerate() {
if skip == Some(basis_index) {
continue;
}
if let Some(position) = find_factor(word, lead_word(elem)) {
return Some((term_index, basis_index, position));
}
}
}
None
}
const KIND_OVERLAP: u8 = 0;
const KIND_INCLUSION: u8 = 1;
type AmbKey = (usize, usize, u8, usize);
fn pair_ambiguities(
i: usize,
j: usize,
li: &[ArrowId],
lj: &[ArrowId],
out: &mut BTreeSet<AmbKey>,
) {
for k in 1..li.len().min(lj.len()) {
if li[li.len() - k..] == lj[..k] {
out.insert((i, j, KIND_OVERLAP, li.len() - k));
}
}
if lj.len() < li.len() {
for offset in 0..=li.len() - lj.len() {
if li[offset..offset + lj.len()] == *lj {
out.insert((i, j, KIND_INCLUSION, offset));
}
}
}
}
fn superposition_len(basis: &[BasisElem], key: AmbKey) -> usize {
let (i, j, kind, offset) = key;
if kind == KIND_OVERLAP {
offset + lead_word(&basis[j]).len()
} else {
let _ = j;
lead_word(&basis[i]).len()
}
}
struct StepsExhausted;
struct Engine<'a> {
field: PrimeField,
limits: &'a CompletionLimits,
steps: usize,
}
impl Engine<'_> {
fn diag(
&self,
basis_len: usize,
pending_ambiguities: usize,
reason: TruncationReason,
) -> TruncationDiagnostics {
TruncationDiagnostics {
basis_len,
pending_ambiguities,
steps_used: self.steps,
reason,
}
}
fn reduce_full(
&mut self,
basis: &[BasisElem],
skip: Option<usize>,
poly: &mut Poly,
mut origin: Option<&mut Origin>,
mut trace: Option<&mut Vec<TraceStep>>,
) -> Result<(), StepsExhausted> {
loop {
let Some((term_index, basis_index, position)) = find_reduction(basis, skip, poly)
else {
return Ok(());
};
if self.steps >= self.limits.max_steps {
return Err(StepsExhausted);
}
self.steps += 1;
let (coeff, word) = poly.terms[term_index].clone();
let lead_len = lead_word(&basis[basis_index]).len();
let left = word[..position].to_vec();
let right = word[position + lead_len..].to_vec();
if let Some(steps) = trace.as_deref_mut() {
steps.push(TraceStep {
word: raw_word(&word),
basis_index,
left: raw_word(&left),
right: raw_word(&right),
coeff: coeff.raw(),
});
}
let neg = self.field.neg(coeff);
*poly = add_scaled(
self.field,
poly,
neg,
&left,
&basis[basis_index].poly,
&right,
);
if let Some(target) = origin.as_deref_mut() {
origin_add_scaled(
self.field,
target,
neg,
&left,
&basis[basis_index].origin,
&right,
);
}
}
}
fn composition(&self, basis: &[BasisElem], key: AmbKey) -> (Poly, Origin) {
let (i, j, kind, offset) = key;
let li = lead_word(&basis[i]).clone();
let lj = lead_word(&basis[j]).clone();
let neg_one = self.field.neg(self.field.one());
let (u, v): (&[ArrowId], &[ArrowId]) = if kind == KIND_OVERLAP {
(&li[..offset], &lj[li.len() - offset..])
} else {
(&li[..offset], &li[offset + lj.len()..])
};
let mut poly;
let mut origin;
if kind == KIND_OVERLAP {
poly = add_scaled(
self.field,
&Poly::zero(),
self.field.one(),
&[],
&basis[i].poly,
v,
);
origin = Origin::new();
origin_add_scaled(
self.field,
&mut origin,
self.field.one(),
&[],
&basis[i].origin,
v,
);
poly = add_scaled(self.field, &poly, neg_one, u, &basis[j].poly, &[]);
origin_add_scaled(self.field, &mut origin, neg_one, u, &basis[j].origin, &[]);
} else {
poly = basis[i].poly.clone();
origin = basis[i].origin.clone();
poly = add_scaled(self.field, &poly, neg_one, u, &basis[j].poly, v);
origin_add_scaled(self.field, &mut origin, neg_one, u, &basis[j].origin, v);
}
(poly, origin)
}
fn interreduce(
&mut self,
basis: Vec<BasisElem>,
) -> Result<(Vec<BasisElem>, bool), TruncationDiagnostics> {
let mut kept: Vec<BasisElem> = Vec::new();
for (i, elem) in basis.iter().enumerate() {
let redundant = basis.iter().enumerate().any(|(j, other)| {
j != i && find_factor(lead_word(elem), lead_word(other)).is_some()
});
if !redundant {
kept.push(elem.clone());
}
}
let dropped = kept.len() != basis.len();
kept.sort_by(|a, b| word_cmp(lead_word(a), lead_word(b)));
for index in 0..kept.len() {
let mut elem = kept[index].clone();
if self
.reduce_full(
&kept,
Some(index),
&mut elem.poly,
Some(&mut elem.origin),
None,
)
.is_err()
{
return Err(self.diag(kept.len(), 0, TruncationReason::StepBudget));
}
kept[index] = elem;
}
Ok((kept, dropped))
}
fn emit(
&mut self,
presentation: &Presentation,
basis: &[BasisElem],
) -> Result<Certificate, TruncationDiagnostics> {
let mut keys: BTreeSet<AmbKey> = BTreeSet::new();
for i in 0..basis.len() {
for j in 0..basis.len() {
pair_ambiguities(i, j, lead_word(&basis[i]), lead_word(&basis[j]), &mut keys);
}
}
let input_relations: Vec<RelationData> = presentation
.relations()
.iter()
.map(|r| poly_data(&poly_from_relation(r)))
.collect();
let mut membership = Vec::with_capacity(input_relations.len());
for relation in presentation.relations() {
let mut poly = poly_from_relation(relation);
let start = poly_data(&poly);
let mut steps = Vec::new();
if self
.reduce_full(basis, None, &mut poly, None, Some(&mut steps))
.is_err()
{
return Err(self.diag(basis.len(), keys.len(), TruncationReason::StepBudget));
}
debug_assert!(
poly.is_zero(),
"input relation must reduce to zero over the final basis"
);
membership.push(Trace { start, steps });
}
let total = keys.len();
let mut ambiguities = Vec::with_capacity(total);
for (done, &key) in keys.iter().enumerate() {
let (mut poly, _) = self.composition(basis, key);
let start = poly_data(&poly);
let mut steps = Vec::new();
if self
.reduce_full(basis, None, &mut poly, None, Some(&mut steps))
.is_err()
{
return Err(self.diag(basis.len(), total - done, TruncationReason::StepBudget));
}
debug_assert!(
poly.is_zero(),
"composition must reduce to zero over the final basis"
);
let (i, j, kind, offset) = key;
ambiguities.push(AmbiguityEntry {
i,
j,
kind: if kind == KIND_OVERLAP {
AmbiguityKind::Overlap
} else {
AmbiguityKind::Inclusion
},
offset,
trace: Trace { start, steps },
});
}
let leads: Vec<&Word> = basis.iter().map(lead_word).collect();
let quiver = presentation.quiver();
let automaton = PrefixAutomaton::build(quiver, &leads);
let (finiteness, normal_words) = match automaton.cycle_witness() {
Some((prefix, cycle)) => (FinitenessData::Infinite { prefix, cycle }, Vec::new()),
None => (
FinitenessData::Finite,
self.normal_words(quiver, &automaton, basis.len())?,
),
};
Ok(Certificate {
schema: CERT_SCHEMA.to_string(),
field: self.field.modulus(),
quiver: QuiverData {
vertices: quiver.num_vertices(),
arrows: quiver.arrows().to_vec(),
},
order: ORDER_ID.to_string(),
input_relations,
basis: basis.iter().map(|e| poly_data(&e.poly)).collect(),
origin: basis.iter().map(origin_terms).collect(),
membership,
ambiguities,
normal_words,
automaton: automaton.data(),
finiteness,
})
}
fn normal_words(
&mut self,
quiver: &Quiver,
automaton: &PrefixAutomaton,
basis_len: usize,
) -> Result<Vec<Vec<u32>>, TruncationDiagnostics> {
let mut rows: Vec<(u32, u32, Word)> = Vec::new();
let mut states: Vec<usize> = Vec::new();
for v in 0..quiver.num_vertices() {
if self.steps >= self.limits.max_steps {
return Err(self.diag(basis_len, 0, TruncationReason::StepBudget));
}
self.steps += 1;
rows.push((v, v, Vec::new()));
states.push(v as usize);
}
let mut level_start = 0;
while level_start < rows.len() {
let level_end = rows.len();
for i in level_start..level_end {
let (source, target, word) = rows[i].clone();
let s = states[i];
for &a in quiver.arrows_from(target) {
if let Some(next) = automaton.step(s, a) {
if self.steps >= self.limits.max_steps {
return Err(self.diag(basis_len, 0, TruncationReason::StepBudget));
}
self.steps += 1;
let mut extended = word.clone();
extended.push(a);
rows.push((source, quiver.target(a), extended));
states.push(next);
}
}
}
level_start = level_end;
}
rows.sort_by(|(sa, _, wa), (sb, _, wb)| {
wa.len().cmp(&wb.len()).then(sa.cmp(sb)).then(wa.cmp(wb))
});
Ok(rows.into_iter().map(|(_, _, w)| raw_word(&w)).collect())
}
}
fn origin_terms(elem: &BasisElem) -> Vec<OriginTerm> {
elem.origin
.iter()
.map(|((index, left, right), coeff)| OriginTerm {
coeff: coeff.raw(),
left: raw_word(left),
input_index: *index,
right: raw_word(right),
})
.collect()
}
pub fn complete(presentation: &Presentation, limits: &CompletionLimits) -> Outcome {
match run(presentation, limits) {
Ok(certificate) => Outcome::Complete(certificate),
Err(diagnostics) => Outcome::Truncated(diagnostics),
}
}
fn run(
presentation: &Presentation,
limits: &CompletionLimits,
) -> Result<Certificate, TruncationDiagnostics> {
let mut engine = Engine {
field: presentation.field(),
limits,
steps: 0,
};
let mut basis: Vec<BasisElem> = Vec::new();
for (index, relation) in presentation.relations().iter().enumerate() {
if relation.leading().1.len() > limits.max_word_len {
return Err(engine.diag(basis.len(), 0, TruncationReason::WordLenBudget));
}
let mut poly = poly_from_relation(relation);
let mut origin = Origin::new();
origin.insert((index, Vec::new(), Vec::new()), engine.field.one());
if engine
.reduce_full(&basis, None, &mut poly, Some(&mut origin), None)
.is_err()
{
return Err(engine.diag(basis.len(), 0, TruncationReason::StepBudget));
}
if poly.is_zero() {
continue;
}
if basis.len() >= limits.max_basis {
return Err(engine.diag(basis.len(), 0, TruncationReason::BasisBudget));
}
make_monic(engine.field, &mut poly, &mut origin);
basis.push(BasisElem { poly, origin });
}
loop {
let mut queue: BTreeSet<AmbKey> = BTreeSet::new();
for i in 0..basis.len() {
for j in 0..basis.len() {
pair_ambiguities(i, j, lead_word(&basis[i]), lead_word(&basis[j]), &mut queue);
}
}
while let Some(key) = queue.pop_first() {
let pending = queue.len() + 1;
if superposition_len(&basis, key) > limits.max_word_len {
return Err(engine.diag(basis.len(), pending, TruncationReason::WordLenBudget));
}
let (mut poly, mut origin) = engine.composition(&basis, key);
if engine
.reduce_full(&basis, None, &mut poly, Some(&mut origin), None)
.is_err()
{
return Err(engine.diag(basis.len(), pending, TruncationReason::StepBudget));
}
if poly.is_zero() {
continue;
}
if basis.len() >= limits.max_basis {
return Err(engine.diag(basis.len(), pending, TruncationReason::BasisBudget));
}
make_monic(engine.field, &mut poly, &mut origin);
basis.push(BasisElem { poly, origin });
let new = basis.len() - 1;
for other in 0..basis.len() {
pair_ambiguities(
new,
other,
lead_word(&basis[new]),
lead_word(&basis[other]),
&mut queue,
);
pair_ambiguities(
other,
new,
lead_word(&basis[other]),
lead_word(&basis[new]),
&mut queue,
);
}
}
let (reduced, dropped) = engine.interreduce(basis)?;
basis = reduced;
if !dropped {
break;
}
}
engine.emit(presentation, &basis)
}
struct PrefixAutomaton {
words: Vec<Word>,
trans: Vec<Vec<Option<usize>>>,
starts: usize,
}
impl PrefixAutomaton {
fn build(quiver: &Quiver, forbidden: &[&Word]) -> PrefixAutomaton {
let n = quiver.num_vertices() as usize;
let mut prefix_set: BTreeSet<Word> = BTreeSet::new();
for word in forbidden {
for len in 1..word.len() {
prefix_set.insert(word[..len].to_vec());
}
}
let mut words: Vec<Word> = vec![Word::new(); n];
let mut prefix_index: BTreeMap<Word, usize> = BTreeMap::new();
for prefix in prefix_set {
prefix_index.insert(prefix.clone(), words.len());
words.push(prefix);
}
let forbidden_set: BTreeSet<&[ArrowId]> = forbidden.iter().map(|w| w.as_slice()).collect();
let mut trans = vec![vec![None; quiver.num_arrows()]; words.len()];
for (s, row) in trans.iter_mut().enumerate() {
let (word, vertex): (&[ArrowId], u32) = if s < n {
(&[], s as u32)
} else {
let w = words[s].as_slice();
(w, quiver.target(w[w.len() - 1]))
};
for &a in quiver.arrows_from(vertex) {
let mut extended = word.to_vec();
extended.push(a);
let mut next = Some(quiver.target(a) as usize);
for start in 0..extended.len() {
let suffix = &extended[start..];
if forbidden_set.contains(suffix) {
next = None;
break;
}
if let Some(&k) = prefix_index.get(suffix) {
next = Some(k);
break;
}
}
row[a.index()] = next;
}
}
PrefixAutomaton {
words,
trans,
starts: n,
}
}
fn data(&self) -> AutomatonData {
let states = self.words.iter().map(|w| raw_word(w)).collect();
let mut transitions = Vec::new();
for (state, row) in self.trans.iter().enumerate() {
for (arrow, next) in row.iter().enumerate() {
if let Some(next) = next {
transitions.push((state, arrow as u32, *next));
}
}
}
AutomatonData {
states,
transitions,
}
}
fn cycle_witness(&self) -> Option<(Vec<u32>, Vec<u32>)> {
let m = self.trans.len();
let mut reachable = vec![false; m];
let mut parent: Vec<Option<(usize, u32)>> = vec![None; m];
let mut queue: VecDeque<usize> = (0..self.starts).collect();
reachable[..self.starts].fill(true);
while let Some(state) = queue.pop_front() {
for (arrow, next) in self.trans[state].iter().enumerate() {
let Some(next) = *next else { continue };
if !reachable[next] {
reachable[next] = true;
parent[next] = Some((state, arrow as u32));
queue.push_back(next);
}
}
}
let mut out_degree = vec![0usize; m];
let mut predecessors: Vec<Vec<usize>> = vec![Vec::new(); m];
for state in 0..m {
if !reachable[state] {
continue;
}
for &next in self.trans[state].iter().flatten() {
out_degree[state] += 1;
predecessors[next].push(state);
}
}
let mut removed = vec![false; m];
let mut ready: VecDeque<usize> = (0..m)
.filter(|&state| reachable[state] && out_degree[state] == 0)
.collect();
while let Some(state) = ready.pop_front() {
removed[state] = true;
for &before in &predecessors[state] {
out_degree[before] -= 1;
if out_degree[before] == 0 {
ready.push_back(before);
}
}
}
let live = |state: usize| reachable[state] && !removed[state];
let start = (0..m).find(|&state| live(state))?;
let mut position = BTreeMap::new();
let mut walk: Vec<u32> = Vec::new();
let mut current = start;
let (entry, cycle_state) = loop {
if let Some(&at) = position.get(¤t) {
break (at, current);
}
position.insert(current, walk.len());
let (arrow, next) = self.trans[current]
.iter()
.enumerate()
.find_map(|(arrow, next)| next.filter(|&t| live(t)).map(|t| (arrow as u32, t)))
.expect("a state that survives pruning keeps a surviving successor");
walk.push(arrow);
current = next;
};
let cycle = walk[entry..].to_vec();
let mut prefix = Vec::new();
let mut state = cycle_state;
while let Some((before, arrow)) = parent[state] {
prefix.push(arrow);
state = before;
}
prefix.reverse();
Some((prefix, cycle))
}
#[inline]
fn step(&self, state: usize, arrow: ArrowId) -> Option<usize> {
self.trans[state][arrow.index()]
}
}
#[cfg(test)]
mod tests {
use super::*;
fn f(p: u64) -> PrimeField {
PrimeField::new(p).unwrap()
}
fn ids(raw: &[u32]) -> Vec<ArrowId> {
raw.iter().copied().map(ArrowId).collect()
}
fn rel(quiver: &Quiver, field: PrimeField, terms: &[(i64, &[u32])]) -> Relation {
Relation::new(
quiver,
field,
terms
.iter()
.map(|(c, w)| (field.elem(*c), ids(w)))
.collect(),
)
.unwrap()
}
fn completed(presentation: &Presentation) -> Certificate {
match complete(presentation, &CompletionLimits::default()) {
Outcome::Complete(certificate) => certificate,
Outcome::Truncated(diagnostics) => panic!("unexpected truncation: {diagnostics:?}"),
}
}
fn truncated(presentation: &Presentation, limits: &CompletionLimits) -> TruncationDiagnostics {
match complete(presentation, limits) {
Outcome::Complete(_) => panic!("expected truncation"),
Outcome::Truncated(diagnostics) => diagnostics,
}
}
fn x_cubed() -> Presentation {
let quiver = Quiver::new(1, &[(0, 0)]).unwrap();
let field = f(5);
let r = rel(&quiver, field, &[(1, &[0, 0, 0])]);
Presentation::new(quiver, field, vec![r]).unwrap()
}
fn commutative_square() -> Presentation {
let quiver = Quiver::new(4, &[(0, 1), (1, 3), (0, 2), (2, 3)]).unwrap();
let field = f(5);
let r = rel(&quiver, field, &[(1, &[0, 1]), (-1, &[2, 3])]);
Presentation::new(quiver, field, vec![r]).unwrap()
}
fn overlap_example() -> Presentation {
let quiver = Quiver::new(1, &[(0, 0), (0, 0)]).unwrap();
let field = f(2);
let r0 = rel(&quiver, field, &[(1, &[1, 0]), (-1, &[0, 0])]);
let r1 = rel(&quiver, field, &[(1, &[1, 1])]);
Presentation::new(quiver, field, vec![r0, r1]).unwrap()
}
fn overlap_example_swapped() -> Presentation {
let quiver = Quiver::new(1, &[(0, 0), (0, 0)]).unwrap();
let field = f(2);
let r0 = rel(&quiver, field, &[(1, &[1, 0]), (-1, &[0, 0])]);
let r1 = rel(&quiver, field, &[(1, &[1, 1])]);
Presentation::new(quiver, field, vec![r1, r0]).unwrap()
}
fn inhomogeneous() -> Presentation {
let quiver = Quiver::new(5, &[(0, 1), (1, 3), (0, 2), (2, 4), (4, 3)]).unwrap();
let field = f(5);
let r = rel(&quiver, field, &[(1, &[2, 3, 4]), (-1, &[0, 1])]);
Presentation::new(quiver, field, vec![r]).unwrap()
}
fn inclusion_example() -> Presentation {
let quiver = Quiver::new(1, &[(0, 0)]).unwrap();
let field = f(2);
let r0 = rel(&quiver, field, &[(1, &[0, 0, 0, 0, 0])]);
let r1 = rel(&quiver, field, &[(1, &[0, 0, 0, 0]), (1, &[0, 0])]);
Presentation::new(quiver, field, vec![r0, r1]).unwrap()
}
fn one_loop_free() -> Presentation {
let quiver = Quiver::new(1, &[(0, 0)]).unwrap();
Presentation::new(quiver, f(2), Vec::new()).unwrap()
}
fn all_examples() -> Vec<Presentation> {
vec![
x_cubed(),
commutative_square(),
overlap_example(),
overlap_example_swapped(),
inhomogeneous(),
inclusion_example(),
one_loop_free(),
]
}
fn expand_origin(
field: PrimeField,
inputs: &[RelationData],
origin: &[OriginTerm],
) -> RelationData {
let mut acc: BTreeMap<Vec<u32>, Fp> = BTreeMap::new();
for term in origin {
let c = field.elem(term.coeff as i64);
for (rc, rw) in &inputs[term.input_index] {
let mut word = term.left.clone();
word.extend_from_slice(rw);
word.extend_from_slice(&term.right);
let add = field.mul(c, field.elem(*rc as i64));
let sum = field.add(acc.get(&word).copied().unwrap_or(field.zero()), add);
if sum.is_zero() {
acc.remove(&word);
} else {
acc.insert(word, sum);
}
}
}
let mut expanded: Vec<(u64, Vec<u32>)> =
acc.into_iter().map(|(w, c)| (c.raw(), w)).collect();
expanded.sort_by(|(_, a), (_, b)| b.len().cmp(&a.len()).then(b.cmp(a)));
expanded
}
fn assert_trace_reduces_to_zero(field: PrimeField, basis: &[RelationData], trace: &Trace) {
let mut acc: BTreeMap<Vec<u32>, Fp> = BTreeMap::new();
for (c, w) in &trace.start {
assert!(acc.insert(w.clone(), field.elem(*c as i64)).is_none());
}
for step in &trace.steps {
let elem = &basis[step.basis_index];
let mut recomposed = step.left.clone();
recomposed.extend_from_slice(&elem[0].1);
recomposed.extend_from_slice(&step.right);
assert_eq!(step.word, recomposed);
let c = field.elem(step.coeff as i64);
for (bc, bw) in elem {
let mut word = step.left.clone();
word.extend_from_slice(bw);
word.extend_from_slice(&step.right);
let sub = field.mul(c, field.elem(*bc as i64));
let sum = field.sub(acc.get(&word).copied().unwrap_or(field.zero()), sub);
if sum.is_zero() {
acc.remove(&word);
} else {
acc.insert(word, sum);
}
}
}
assert!(acc.is_empty(), "trace does not end at zero: {acc:?}");
}
#[test]
fn monomial_x_cubed_is_a_no_op() {
let c = completed(&x_cubed());
assert_eq!(c.schema, CERT_SCHEMA);
assert_eq!(c.field, 5);
assert_eq!(c.order, ORDER_ID);
assert_eq!(
c.quiver,
QuiverData {
vertices: 1,
arrows: vec![(0, 0)],
}
);
assert_eq!(c.input_relations, vec![vec![(1, vec![0, 0, 0])]]);
assert_eq!(c.basis, vec![vec![(1, vec![0, 0, 0])]]);
assert_eq!(
c.origin,
vec![vec![OriginTerm {
coeff: 1,
left: vec![],
input_index: 0,
right: vec![],
}]]
);
assert_eq!(
c.membership,
vec![Trace {
start: vec![(1, vec![0, 0, 0])],
steps: vec![TraceStep {
word: vec![0, 0, 0],
basis_index: 0,
left: vec![],
right: vec![],
coeff: 1,
}],
}]
);
assert_eq!(c.ambiguities.len(), 2);
for (entry, offset) in c.ambiguities.iter().zip([1usize, 2]) {
assert_eq!(
(entry.i, entry.j, entry.kind, entry.offset),
(0, 0, AmbiguityKind::Overlap, offset)
);
assert_eq!(
entry.trace,
Trace {
start: vec![],
steps: vec![],
}
);
}
assert_eq!(c.normal_words, vec![vec![], vec![0], vec![0, 0]]);
assert_eq!(
c.automaton,
AutomatonData {
states: vec![vec![], vec![0], vec![0, 0]],
transitions: vec![(0, 0, 1), (1, 0, 2)],
}
);
assert_eq!(c.finiteness, FinitenessData::Finite);
}
#[test]
fn commutative_square_rewrites_cd_to_ab() {
let c = completed(&commutative_square());
assert_eq!(
c.input_relations,
vec![vec![(4, vec![2, 3]), (1, vec![0, 1])]]
);
assert_eq!(c.basis, vec![vec![(1, vec![2, 3]), (4, vec![0, 1])]]);
assert_eq!(
c.origin,
vec![vec![OriginTerm {
coeff: 4,
left: vec![],
input_index: 0,
right: vec![],
}]]
);
assert_eq!(
c.membership,
vec![Trace {
start: vec![(4, vec![2, 3]), (1, vec![0, 1])],
steps: vec![TraceStep {
word: vec![2, 3],
basis_index: 0,
left: vec![],
right: vec![],
coeff: 4,
}],
}]
);
assert!(c.ambiguities.is_empty());
assert_eq!(
c.normal_words,
vec![
vec![],
vec![],
vec![],
vec![],
vec![0],
vec![2],
vec![1],
vec![3],
vec![0, 1],
]
);
assert_eq!(c.normal_words.len(), 9);
}
#[test]
fn overlap_completion_adds_xxx() {
let c = completed(&overlap_example());
assert_eq!(
c.basis,
vec![
vec![(1, vec![1, 0]), (1, vec![0, 0])],
vec![(1, vec![1, 1])],
vec![(1, vec![0, 0, 0])],
]
);
assert_eq!(
c.origin[0],
vec![OriginTerm {
coeff: 1,
left: vec![],
input_index: 0,
right: vec![],
}]
);
assert_eq!(
c.origin[1],
vec![OriginTerm {
coeff: 1,
left: vec![],
input_index: 1,
right: vec![],
}]
);
assert_eq!(
c.origin[2],
vec![
OriginTerm {
coeff: 1,
left: vec![],
input_index: 0,
right: vec![0],
},
OriginTerm {
coeff: 1,
left: vec![1],
input_index: 0,
right: vec![],
},
OriginTerm {
coeff: 1,
left: vec![],
input_index: 1,
right: vec![0],
},
]
);
let keys: Vec<_> = c
.ambiguities
.iter()
.map(|e| (e.i, e.j, e.kind, e.offset))
.collect();
assert_eq!(
keys,
vec![
(0, 2, AmbiguityKind::Overlap, 1),
(1, 0, AmbiguityKind::Overlap, 1),
(1, 1, AmbiguityKind::Overlap, 1),
(2, 2, AmbiguityKind::Overlap, 1),
(2, 2, AmbiguityKind::Overlap, 2),
]
);
assert_eq!(c.ambiguities[0].trace.start, vec![(1, vec![0, 0, 0, 0])]);
assert_eq!(
c.ambiguities[0].trace.steps,
vec![TraceStep {
word: vec![0, 0, 0, 0],
basis_index: 2,
left: vec![],
right: vec![0],
coeff: 1,
}]
);
assert_eq!(c.ambiguities[1].trace.start, vec![(1, vec![1, 0, 0])]);
assert_eq!(
c.ambiguities[1].trace.steps,
vec![
TraceStep {
word: vec![1, 0, 0],
basis_index: 0,
left: vec![],
right: vec![0],
coeff: 1,
},
TraceStep {
word: vec![0, 0, 0],
basis_index: 2,
left: vec![],
right: vec![],
coeff: 1,
},
]
);
for entry in &c.ambiguities[2..] {
assert_eq!(
entry.trace,
Trace {
start: vec![],
steps: vec![],
}
);
}
assert_eq!(
c.normal_words,
vec![
vec![],
vec![0],
vec![1],
vec![0, 0],
vec![0, 1],
vec![0, 0, 1],
]
);
}
#[test]
fn inclusion_collapses_to_x_squared() {
let c = completed(&inclusion_example());
assert_eq!(c.basis, vec![vec![(1, vec![0, 0])]]);
assert_eq!(c.normal_words, vec![vec![], vec![0]]);
let keys: Vec<_> = c
.ambiguities
.iter()
.map(|e| (e.i, e.j, e.kind, e.offset))
.collect();
assert_eq!(keys, vec![(0, 0, AmbiguityKind::Overlap, 1)]);
assert_eq!(
c.ambiguities[0].trace,
Trace {
start: vec![],
steps: vec![],
}
);
assert_eq!(
c.membership,
vec![
Trace {
start: vec![(1, vec![0, 0, 0, 0, 0])],
steps: vec![TraceStep {
word: vec![0, 0, 0, 0, 0],
basis_index: 0,
left: vec![],
right: vec![0, 0, 0],
coeff: 1,
}],
},
Trace {
start: vec![(1, vec![0, 0, 0, 0]), (1, vec![0, 0])],
steps: vec![
TraceStep {
word: vec![0, 0, 0, 0],
basis_index: 0,
left: vec![],
right: vec![0, 0],
coeff: 1,
},
TraceStep {
word: vec![0, 0],
basis_index: 0,
left: vec![],
right: vec![],
coeff: 1,
},
],
},
]
);
}
#[test]
fn inhomogeneous_relation_completes_without_ambiguities() {
let c = completed(&inhomogeneous());
assert_eq!(
c.input_relations,
vec![vec![(1, vec![2, 3, 4]), (4, vec![0, 1])]]
);
assert_eq!(c.basis, vec![vec![(1, vec![2, 3, 4]), (4, vec![0, 1])]]);
assert!(c.ambiguities.is_empty());
assert_eq!(
c.membership,
vec![Trace {
start: vec![(1, vec![2, 3, 4]), (4, vec![0, 1])],
steps: vec![TraceStep {
word: vec![2, 3, 4],
basis_index: 0,
left: vec![],
right: vec![],
coeff: 1,
}],
}]
);
assert_eq!(
c.normal_words,
vec![
vec![],
vec![],
vec![],
vec![],
vec![],
vec![0],
vec![2],
vec![1],
vec![3],
vec![4],
vec![0, 1],
vec![2, 3],
vec![3, 4],
]
);
assert_eq!(c.normal_words.len(), 13);
}
#[test]
fn tight_basis_budget_truncates() {
let limits = CompletionLimits {
max_basis: 2,
..CompletionLimits::default()
};
assert_eq!(
truncated(&overlap_example(), &limits),
TruncationDiagnostics {
basis_len: 2,
pending_ambiguities: 2,
steps_used: 1,
reason: TruncationReason::BasisBudget,
}
);
}
#[test]
fn tight_word_len_budget_truncates() {
let limits = CompletionLimits {
max_word_len: 3,
..CompletionLimits::default()
};
assert_eq!(
truncated(&overlap_example(), &limits),
TruncationDiagnostics {
basis_len: 3,
pending_ambiguities: 4,
steps_used: 1,
reason: TruncationReason::WordLenBudget,
}
);
}
#[test]
fn tight_step_budget_truncates() {
let limits = CompletionLimits {
max_steps: 1,
..CompletionLimits::default()
};
assert_eq!(
truncated(&overlap_example(), &limits),
TruncationDiagnostics {
basis_len: 3,
pending_ambiguities: 4,
steps_used: 1,
reason: TruncationReason::StepBudget,
}
);
}
#[test]
fn identical_input_gives_identical_bytes() {
let p = overlap_example();
let first = completed(&p).to_canonical_json();
let second = completed(&p).to_canonical_json();
assert_eq!(first, second);
}
#[test]
fn input_order_does_not_change_the_basis() {
let straight = completed(&overlap_example());
let swapped = completed(&overlap_example_swapped());
let a: BTreeSet<RelationData> = straight.basis.iter().cloned().collect();
let b: BTreeSet<RelationData> = swapped.basis.iter().cloned().collect();
assert_eq!(a, b);
}
#[test]
fn free_loop_reports_empty_normal_words() {
let c = completed(&one_loop_free());
assert!(c.input_relations.is_empty());
assert!(c.basis.is_empty());
assert!(c.origin.is_empty());
assert!(c.membership.is_empty());
assert!(c.ambiguities.is_empty());
assert_eq!(c.normal_words, Vec::<Vec<u32>>::new());
assert_eq!(
c.automaton,
AutomatonData {
states: vec![vec![]],
transitions: vec![(0, 0, 0)],
}
);
assert_eq!(
c.finiteness,
FinitenessData::Infinite {
prefix: vec![],
cycle: vec![0],
}
);
}
#[test]
fn huge_finite_language_truncates_instead_of_exhausting_memory() {
let layers = 40u32;
let mut arrows = Vec::new();
for v in 0..layers {
arrows.push((v, v + 1));
arrows.push((v, v + 1));
}
let quiver = Quiver::new(layers + 1, &arrows).unwrap();
let presentation = Presentation::new(quiver, f(2), Vec::new()).unwrap();
let limits = CompletionLimits {
max_steps: 10_000,
..CompletionLimits::default()
};
let started = std::time::Instant::now();
let diagnostics = truncated(&presentation, &limits);
assert_eq!(diagnostics.reason, TruncationReason::StepBudget);
assert_eq!(diagnostics.steps_used, 10_000);
assert_eq!(diagnostics.pending_ambiguities, 0);
assert!(
started.elapsed() < std::time::Duration::from_secs(5),
"truncation must be fast"
);
}
#[test]
fn origins_expand_to_their_basis_elements() {
for presentation in all_examples() {
let c = completed(&presentation);
let field = PrimeField::new(c.field).unwrap();
for (j, origin) in c.origin.iter().enumerate() {
assert_eq!(
expand_origin(field, &c.input_relations, origin),
c.basis[j],
"origin {j}"
);
}
}
}
#[test]
fn all_traces_replay_to_zero() {
for presentation in all_examples() {
let c = completed(&presentation);
let field = PrimeField::new(c.field).unwrap();
for (i, trace) in c.membership.iter().enumerate() {
assert_eq!(trace.start, c.input_relations[i]);
assert_trace_reduces_to_zero(field, &c.basis, trace);
}
for entry in &c.ambiguities {
assert_trace_reduces_to_zero(field, &c.basis, &entry.trace);
}
}
}
}