use crate::certificate::{AmbiguityKind, CERT_SCHEMA, CertParseError, Certificate};
use crate::field::{FieldError, Fp, PrimeField};
use crate::order::ORDER_ID;
use crate::quiver::{PathWord, Quiver, QuiverError};
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct CycleWitness {
pub prefix: Vec<u32>,
pub cycle: Vec<u32>,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum TraceSite {
Membership { input: usize },
Ambiguity { index: usize },
}
display_error! { TraceSite {
Self::Membership { input } => "membership trace {input}";
Self::Ambiguity { index } => "ambiguity trace {index}";
} }
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum TermDefect {
Empty,
ZeroCoefficient,
NonCanonicalCoefficient { coeff: u64 },
WordTooShort { len: usize },
InvalidWord(QuiverError),
MixedSource,
MixedTarget,
NotDescending,
}
display_error! { TermDefect {
Self::Empty => "relation has no terms";
Self::ZeroCoefficient => "coefficient is zero";
Self::NonCanonicalCoefficient { coeff } => "coefficient {coeff} is not in 0..p";
Self::WordTooShort { len } => "word has length {len}, below 2";
Self::InvalidWord(error) => "word is not a path: {error}";
Self::MixedSource => "word starts at a different vertex than term 0";
Self::MixedTarget => "word ends at a different vertex than term 0";
Self::NotDescending => "word is not strictly below the word before it";
} }
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum WitnessDefect {
EmptyCycle,
NotAPath(QuiverError),
ContainsLeadingWord { lead: usize, position: usize },
PrefixLeaves { at: usize },
CycleLeaves { at: usize },
CycleDoesNotReturn { reached: usize, back: usize },
}
display_error! { WitnessDefect {
Self::EmptyCycle => "the cycle word is empty";
Self::NotAPath(error) => "prefix and two cycles do not spell a path: {error}";
Self::ContainsLeadingWord { lead, position } => "the leading word of basis element {lead} occurs at position {position}";
Self::PrefixLeaves { at } => "the prefix leaves the automaton at position {at}";
Self::CycleLeaves { at } => "the cycle leaves the automaton at position {at}";
Self::CycleDoesNotReturn { reached, back } => "the cycle starts at state {reached} but ends at state {back}";
} }
macro_rules! verify_error_enum {
(
$(#[$enum_meta:meta])*
$name:ident {
$(
$(#[$meta:meta])*
$variant:ident $(($inner:ty))?
$( { $($field:ident : $ty:ty),* $(,)? } )? ;
)*
}
) => {
$(#[$enum_meta])*
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum $name {
$(
$(#[$meta])*
$variant $(($inner))? $( { $($field : $ty),* } )?,
)*
}
};
}
verify_error_enum! {
VerifyError {
Parse(CertParseError);
Schema { found: String };
Order { found: String };
Field(FieldError);
Quiver(QuiverError);
InputRelation { index: usize, term: usize, defect: TermDefect };
BasisRelation { index: usize, term: usize, defect: TermDefect };
BasisNotMonic { index: usize, coeff: u64 };
BasisNotReduced { lead: usize, element: usize, term: usize, position: usize };
OriginCount { basis: usize, origin: usize };
OriginCoefficient { element: usize, term: usize, coeff: u64 };
OriginInputIndex { element: usize, term: usize, input_index: usize, inputs: usize };
OriginNotComposable { element: usize, term: usize, error: QuiverError };
OriginMismatch { element: usize, word: Vec<u32> };
MembershipCount { inputs: usize, traces: usize };
MembershipStart { input: usize };
TraceStepBasisIndex { site: TraceSite, step: usize, basis_index: usize, basis: usize };
TraceStepWord { site: TraceSite, step: usize };
TraceStepPath { site: TraceSite, step: usize, error: QuiverError };
TraceStepAbsent { site: TraceSite, step: usize, word: Vec<u32> };
TraceStepCoefficient { site: TraceSite, step: usize, expected: u64, found: u64 };
TraceStepAscending { site: TraceSite, step: usize, word: Vec<u32> };
TraceRemainder { site: TraceSite, word: Vec<u32> };
AmbiguityMissing { i: usize, j: usize, kind: AmbiguityKind, offset: usize };
AmbiguityExtra { i: usize, j: usize, kind: AmbiguityKind, offset: usize };
AmbiguityDuplicate { i: usize, j: usize, kind: AmbiguityKind, offset: usize };
AmbiguityOrder { index: usize, i: usize, j: usize, kind: AmbiguityKind, offset: usize };
AmbiguityStart { index: usize, term: usize, defect: TermDefect };
AmbiguityStartMismatch { index: usize };
AutomatonStateCount { vertices: u32, states: usize };
AutomatonStates { position: usize, expected: Option<Vec<u32>>, found: Option<Vec<u32>> };
AutomatonTransitions {
position: usize,
expected: Option<(usize, u32, usize)>,
found: Option<(usize, u32, usize)>,
};
FinitenessClaim { claimed_finite: bool };
InfiniteWitness { defect: WitnessDefect };
NormalWords {
position: usize,
expected: Option<Vec<u32>>,
found: Option<Vec<u32>>,
};
InfiniteDimensional { witness: CycleWitness };
}
}
display_error! { VerifyError {
Self::Parse(error) => "certificate rejected: {error}";
Self::Schema { found } => "schema is {found:?}, expected {CERT_SCHEMA:?}";
Self::Order { found } => "order is {found:?}, expected {ORDER_ID:?}";
Self::Field(error) => "field rejected: {error}";
Self::Quiver(error) => "quiver rejected: {error}";
Self::InputRelation { index, term, defect } => "input relation {index}, term {term}: {defect}";
Self::BasisRelation { index, term, defect } => "basis element {index}, term {term}: {defect}";
Self::BasisNotMonic { index, coeff } => "basis element {index} has leading coefficient {coeff}, not 1";
Self::BasisNotReduced { lead, element, term, position } => "leading word of basis element {lead} occurs in word {term} of basis element {element} at position {position}";
Self::OriginCount { basis, origin } => "origin has {origin} entries for {basis} basis elements";
Self::OriginCoefficient { element, term, coeff } => "origin of basis element {element}, term {term}: coefficient {coeff} is zero or not in 0..p";
Self::OriginInputIndex { element, term, input_index, inputs } => "origin of basis element {element}, term {term}: input index {input_index} outside 0..{inputs}";
Self::OriginNotComposable { element, term, error } => "origin of basis element {element}, term {term}: expansion is not a path: {error}";
Self::OriginMismatch { element, word } => "origin of basis element {element} does not expand to it; the sides differ at word {word:?}";
Self::MembershipCount { inputs, traces } => "membership has {traces} traces for {inputs} inputs";
Self::MembershipStart { input } => "membership trace {input} does not start at input relation {input}";
Self::TraceStepBasisIndex { site, step, basis_index, basis } => "{site}, step {step}: basis index {basis_index} outside 0..{basis}";
Self::TraceStepWord { site, step } => "{site}, step {step}: word is not left, leading word, right concatenated";
Self::TraceStepPath { site, step, error } => "{site}, step {step}: not a path: {error}";
Self::TraceStepAbsent { site, step, word } => "{site}, step {step}: word {word:?} has coefficient zero";
Self::TraceStepCoefficient { site, step, expected, found } => "{site}, step {step}: the word has coefficient {expected}, the step says {found}";
Self::TraceStepAscending { site, step, word } => "{site}, step {step}: expanded word {word:?} is not strictly below the eliminated word";
Self::TraceRemainder { site, word } => "{site}: not zero after the last step; largest remaining word {word:?}";
Self::AmbiguityMissing { i, j, kind, offset } => "ambiguity ({i}, {j}, {}, {offset}) is missing", kind.as_str();
Self::AmbiguityExtra { i, j, kind, offset } => "({i}, {j}, {}, {offset}) is not an ambiguity of the basis", kind.as_str();
Self::AmbiguityDuplicate { i, j, kind, offset } => "ambiguity ({i}, {j}, {}, {offset}) is listed twice", kind.as_str();
Self::AmbiguityOrder { index, i, j, kind, offset } => "ambiguity entry {index} skips ({i}, {j}, {}, {offset}); the list must follow the canonical key order", kind.as_str();
Self::AmbiguityStart { index, term, defect } => "ambiguity {index}, start term {term}: {defect}";
Self::AmbiguityStartMismatch { index } => "ambiguity {index}: start is not the composition or its negation";
Self::AutomatonStateCount { vertices, states } => "the automaton has {states} states for {vertices} vertices";
Self::AutomatonStates { position, expected, found } => "automaton states differ at position {position}: expected {expected:?}, found {found:?}";
Self::AutomatonTransitions { position, expected, found } => "automaton transitions differ at position {position}: expected {expected:?}, found {found:?}";
Self::FinitenessClaim { claimed_finite: true } => "the certificate claims a finite language but the automaton has a cycle";
Self::FinitenessClaim { claimed_finite: false } => "the certificate claims an infinite language but the automaton is acyclic";
Self::InfiniteWitness { defect } => "the infinite-dimension witness is rejected: {defect}";
Self::NormalWords { position, expected, found } => "normal words differ at position {position}: expected {expected:?}, found {found:?}";
Self::InfiniteDimensional { witness } => "the quotient is infinite dimensional: prefix {:?}, cycle {:?}", witness.prefix, witness.cycle;
} }
error_source!(VerifyError {
Self::Parse(error) => Some(error),
Self::Field(error) => Some(error),
Self::Quiver(error) => Some(error),
_ => None,
});
#[derive(Clone, Debug)]
pub struct VerifiedCompletion {
pub(super) certificate: Certificate,
pub(super) quiver: Quiver,
pub(super) field: PrimeField,
pub(super) basis: Vec<Vec<(Fp, PathWord)>>,
pub(super) normal_words: Vec<PathWord>,
}
impl VerifiedCompletion {
accessor_methods! {
pub certificate() -> &Certificate = |this| &this.certificate;
pub quiver() -> &Quiver = |this| &this.quiver;
pub field() -> PrimeField = |this| this.field;
pub basis() -> &[Vec<(Fp, PathWord)>] = |this| &this.basis;
pub normal_words() -> &[PathWord] = |this| &this.normal_words;
}
}