use rustc_hash::FxHashMap;
use crate::certificate::{Certificate, RelationData};
use crate::completion::CompletionLimits;
use crate::field::{Fp, PrimeField};
use crate::linalg::DenseMat;
use crate::monomial::MonomialError;
use crate::quiver::{ArrowId, PathWord, Quiver};
use crate::relation::{Presentation, Relation, RelationError};
use crate::verify::{CycleWitness, VerifyError};
pub type BasisIdx = usize;
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum AlgebraBuildError {
Monomial(MonomialError),
Relation(RelationError),
NonAdmissible {
stable_power: usize,
dimension: usize,
},
InputRelationsMismatch { index: usize },
InfiniteDimensional {
certificate: Box<Certificate>,
witness: CycleWitness,
},
Truncated(crate::completion::TruncationDiagnostics),
Verification(VerifyError),
}
display_error! { AlgebraBuildError {
Self::Monomial(error) => "monomial input rejected: {error}";
Self::Relation(error) => "relation rejected: {error}";
Self::NonAdmissible { stable_power, dimension } => "the ideal is not admissible: J^{stable_power} has dimension {dimension} and equals every higher power, so J is not nilpotent";
Self::InputRelationsMismatch { index } => "the certificate's input relations differ from the presentation at index {index}";
Self::InfiniteDimensional { witness, .. } => "the quotient is infinite dimensional: prefix {:?}, cycle {:?}" , witness.prefix, witness.cycle;
Self::Truncated(diagnostics) => "completion ran out of budget ({:?}): basis {}, pending ambiguities {}, steps {}", diagnostics.reason, diagnostics.basis_len, diagnostics.pending_ambiguities, diagnostics.steps_used;
Self::Verification(error) => "the engine's certificate failed verification: {error}";
} }
error_source!(AlgebraBuildError {
Self::Monomial(error) => Some(error),
Self::Relation(error) => Some(error),
Self::Verification(error) => Some(error),
_ => None,
});
pub(super) fn check_input_relations(
presentation: &Presentation,
certificate: &Certificate,
) -> Result<(), AlgebraBuildError> {
let asked = presentation.relations();
let found = &certificate.input_relations;
let differs =
|index: &usize| asked.get(*index).map(relation_data).as_ref() != found.get(*index);
match (0..asked.len().max(found.len())).find(differs) {
Some(index) => Err(AlgebraBuildError::InputRelationsMismatch { index }),
None => Ok(()),
}
}
fn relation_data(relation: &Relation) -> RelationData {
relation
.terms()
.iter()
.map(|(coeff, word)| (coeff.raw(), word.arrows().iter().map(|a| a.0).collect()))
.collect()
}
pub(super) type BasisIndexes = (
FxHashMap<Vec<ArrowId>, BasisIdx>,
Vec<Vec<BasisIdx>>,
Vec<Vec<BasisIdx>>,
Vec<Vec<Vec<BasisIdx>>>,
);
pub(super) fn index_basis(quiver: &Quiver, basis: &[PathWord]) -> BasisIndexes {
let n = quiver.num_vertices() as usize;
let mut index_of = FxHashMap::default();
for (i, p) in basis.iter().enumerate() {
if !p.is_trivial() {
index_of.insert(p.arrows().to_vec(), i);
}
}
let mut from = vec![Vec::new(); n];
let mut to = vec![Vec::new(); n];
let mut between = vec![vec![Vec::new(); n]; n];
for (i, p) in basis.iter().enumerate() {
from[p.source() as usize].push(i);
to[p.target() as usize].push(i);
between[p.source() as usize][p.target() as usize].push(i);
}
(index_of, from, to, between)
}
#[derive(Debug)]
pub struct Algebra {
pub(super) quiver: Quiver,
pub(super) field: PrimeField,
pub(super) relations: Vec<Relation>,
pub(super) certificate: Certificate,
pub(super) limits: CompletionLimits,
pub(super) basis: Vec<PathWord>,
pub(super) index_of: FxHashMap<Vec<ArrowId>, BasisIdx>,
pub(super) from: Vec<Vec<BasisIdx>>,
pub(super) to: Vec<Vec<BasisIdx>>,
pub(super) between: Vec<Vec<Vec<BasisIdx>>>,
pub(super) right_mul: Vec<Vec<Vec<(BasisIdx, Fp)>>>,
pub(super) left_mul: Vec<Vec<Vec<(BasisIdx, Fp)>>>,
pub(super) radical_powers: Vec<Vec<Vec<DenseMat>>>,
}