use std::collections::BTreeMap;
use std::sync::Arc;
use crate::algebra::Algebra;
use crate::field::{Fp, PrimeField};
use crate::hom::matrix_is_zero;
use crate::homspace::HomSpace;
use crate::linalg::{DenseMat, SparseMat, SparseRow};
use crate::module::Module;
use super::layout::checked_coordinate;
use super::metadata::{hom_layout, relation_layouts};
use super::types::{
CompiledModuleFamily, FamilyError, FamilyFixedEntry, FamilyLayout, FamilyParameter,
FamilyParameterPosition,
};
impl CompiledModuleFamily {
pub fn new(
algebra: &Arc<Algebra>,
dimensions: Vec<usize>,
fixed: Vec<FamilyFixedEntry>,
parameters: Vec<FamilyParameter>,
) -> Result<Self, FamilyError> {
let layout = FamilyLayout::new(algebra, dimensions)?;
let fixed = checked_fixed(&layout, algebra, fixed)?;
let (parameters, parameter_indices) = checked_parameters(&layout, &fixed, parameters)?;
let relation_evaluations = relation_layouts(algebra, &layout)?;
let hom_equations = hom_layout(&layout)?;
Ok(Self {
algebra: algebra.clone(),
layout,
fixed,
parameters,
parameter_indices,
relation_evaluations,
hom_equations,
})
}
pub fn compile(
algebra: &Arc<Algebra>,
dimensions: Vec<usize>,
fixed: Vec<FamilyFixedEntry>,
parameters: Vec<FamilyParameter>,
) -> Result<Self, FamilyError> {
Self::new(algebra, dimensions, fixed, parameters)
}
accessor_methods! {
pub algebra() -> &Arc<Algebra> = |this| &this.algebra;
pub layout() -> &FamilyLayout = |this| &this.layout;
pub fixed_entries() -> &[FamilyFixedEntry] = |this| &this.fixed;
pub parameters() -> &[FamilyParameterPosition] = |this| &this.parameters;
pub relation_evaluations() -> &[super::types::RelationEvaluationLayout] = |this| &this.relation_evaluations;
pub hom_equations() -> &[super::types::HomEquationLayout] = |this| &this.hom_equations;
}
pub fn parameter_index(&self, name: &str) -> Option<usize> {
self.parameter_indices.get(name).copied()
}
pub fn specialize(&self, values: &[Fp]) -> Result<Module, FamilyError> {
let maps = self.specialized_maps(values)?;
check_relations(self, &maps)?;
Ok(Module::from_relation_checked(
self.algebra.clone(),
self.layout.dimensions.clone(),
maps,
))
}
pub fn specialize_generic(&self, values: &[Fp]) -> Result<Module, FamilyError> {
let maps = self.specialized_maps(values)?;
Module::new(self.algebra.clone(), self.layout.dimensions.clone(), maps).map_err(Into::into)
}
fn specialized_maps(&self, values: &[Fp]) -> Result<Vec<DenseMat>, FamilyError> {
let field = self.algebra.field();
let values = checked_parameter_values(&self.parameters, values, &field)?;
let coordinates =
filled_coordinates(&self.layout, &self.fixed, &self.parameters, &values, &field)?;
filled_maps(&self.layout, &coordinates)
}
pub fn specialize_raw(&self, values: &[u64]) -> Result<Module, FamilyError> {
let field = self.algebra.field();
let canonical = raw_parameter_values(values, &field)?;
self.specialize(&canonical)
}
pub fn hom_space(
&self,
source_values: &[Fp],
target_values: &[Fp],
) -> Result<HomSpace, FamilyError> {
let source = self.specialize(source_values)?;
let target = self.specialize(target_values)?;
Ok(compiled_hom_space(self, &source, &target))
}
pub fn hom_space_generic(
&self,
source_values: &[Fp],
target_values: &[Fp],
) -> Result<HomSpace, FamilyError> {
let source = self.specialize_generic(source_values)?;
let target = self.specialize_generic(target_values)?;
Ok(HomSpace::new(&source, &target)
.expect("two fibers of one compiled family share their algebra"))
}
pub fn verify(&self) -> bool {
let parameters = self
.parameters
.iter()
.map(|parameter| {
let coordinate = parameter.coordinate;
FamilyParameter::new(
parameter.name.clone(),
coordinate.arrow,
coordinate.row,
coordinate.column,
)
})
.collect();
let Ok(rebuilt) = Self::new(
&self.algebra,
self.layout.dimensions.clone(),
self.fixed.clone(),
parameters,
) else {
return false;
};
Arc::ptr_eq(&self.algebra, &rebuilt.algebra)
&& self.layout == rebuilt.layout
&& self.fixed == rebuilt.fixed
&& self.parameters == rebuilt.parameters
&& self.parameter_indices == rebuilt.parameter_indices
&& self.relation_evaluations == rebuilt.relation_evaluations
&& self.hom_equations == rebuilt.hom_equations
}
}
fn compiled_hom_space(family: &CompiledModuleFamily, source: &Module, target: &Module) -> HomSpace {
let field = family.algebra.field();
let mut rows = Vec::new();
for equation in &family.hom_equations {
let entries = equation
.terms
.iter()
.map(|term| {
let coordinate = term.coefficient;
let map = match term.side {
super::types::HomCoefficientSide::Target => target.map(coordinate.arrow),
super::types::HomCoefficientSide::Source => source.map(coordinate.arrow),
};
let value = map.get(coordinate.row, coordinate.column);
let value = match term.side {
super::types::HomCoefficientSide::Target => value,
super::types::HomCoefficientSide::Source => field.neg(value),
};
(term.variable.index, value)
})
.collect();
let row = SparseRow::from_entries(entries, &field);
if !row.is_zero() {
rows.push(row);
}
}
let constraints = SparseMat::from_rows(rows, family.layout.hom_variable_count);
let flat = constraints.kernel_basis(&field).to_dense();
HomSpace::from_checked_flat(source, target, flat)
}
fn check_relations(family: &CompiledModuleFamily, maps: &[DenseMat]) -> Result<(), FamilyError> {
let field = family.algebra.field();
for relation in &family.relation_evaluations {
let mut value = DenseMat::zero(relation.rows, relation.columns);
for term in &relation.terms {
let mut action = DenseMat::identity(relation.rows);
for factor in &term.factors {
action = action.mul(&maps[factor.arrow.index()], &field);
}
value.add_scaled_assign(&action, term.coefficient, &field);
}
if !matrix_is_zero(&value) {
return Err(FamilyError::Module(
crate::module::ModuleError::RelationActsNonzero {
index: relation.relation,
},
));
}
}
Ok(())
}
fn checked_parameter_values(
parameters: &[FamilyParameterPosition],
values: &[Fp],
field: &PrimeField,
) -> Result<Vec<Fp>, FamilyError> {
if values.len() != parameters.len() {
return Err(FamilyError::ParameterCountMismatch {
expected: parameters.len(),
got: values.len(),
});
}
for (index, &value) in values.iter().enumerate() {
if value.raw() >= field.modulus() {
return Err(FamilyError::NonCanonicalParameterValue {
index,
value: value.raw(),
});
}
}
Ok(values.to_vec())
}
fn raw_parameter_values(values: &[u64], field: &PrimeField) -> Result<Vec<Fp>, FamilyError> {
let mut canonical = Vec::new();
canonical
.try_reserve(values.len())
.map_err(|_| FamilyError::CoordinateAllocationFailed {
coordinates: values.len(),
})?;
for &value in values {
if value >= field.modulus() {
return Err(FamilyError::NonCanonicalParameterValue {
index: canonical.len(),
value,
});
}
canonical.push(field.elem(value as i64));
}
Ok(canonical)
}
fn filled_coordinates(
layout: &FamilyLayout,
fixed: &[FamilyFixedEntry],
parameters: &[FamilyParameterPosition],
values: &[Fp],
field: &PrimeField,
) -> Result<Vec<Fp>, FamilyError> {
let count = layout.coordinate_count();
let mut coordinates = Vec::new();
coordinates
.try_reserve(count)
.map_err(|_| FamilyError::CoordinateAllocationFailed { coordinates: count })?;
coordinates.resize(count, field.zero());
for entry in fixed {
let coordinate = layout
.coordinate(entry.arrow, entry.row, entry.column)
.expect("compiled fixed coordinate is in the layout");
coordinates[coordinate.index] = entry.value;
}
for (index, parameter) in parameters.iter().enumerate() {
coordinates[parameter.coordinate.index] = values[index];
}
Ok(coordinates)
}
fn filled_maps(layout: &FamilyLayout, coordinates: &[Fp]) -> Result<Vec<DenseMat>, FamilyError> {
let mut maps = Vec::new();
maps.try_reserve(layout.arrows.len())
.map_err(|_| FamilyError::CoordinateAllocationFailed {
coordinates: layout.arrows.len(),
})?;
for arrow in &layout.arrows {
maps.push(filled_map(layout, arrow, coordinates));
}
Ok(maps)
}
fn filled_map(
layout: &FamilyLayout,
arrow: &super::types::FamilyArrowLayout,
coordinates: &[Fp],
) -> DenseMat {
let mut map = DenseMat::zero(arrow.rows, arrow.columns);
for row in 0..arrow.rows {
for column in 0..arrow.columns {
let coordinate = layout
.coordinate(arrow.arrow, row, column)
.expect("arrow layout coordinate exists");
map.set(row, column, coordinates[coordinate.index]);
}
}
map
}
fn checked_fixed(
layout: &FamilyLayout,
algebra: &Algebra,
entries: Vec<FamilyFixedEntry>,
) -> Result<Vec<FamilyFixedEntry>, FamilyError> {
let mut seen = BTreeMap::new();
for entry in &entries {
checked_coordinate(layout, entry.arrow, entry.row, entry.column)?;
if entry.value.raw() >= algebra.field().modulus() {
return Err(FamilyError::NonCanonicalFixedValue {
arrow: entry.arrow,
row: entry.row,
column: entry.column,
value: entry.value.raw(),
});
}
let coordinate = (entry.arrow, entry.row, entry.column);
if seen.insert(coordinate, ()).is_some() {
return Err(FamilyError::DuplicateFixedCoordinate {
arrow: entry.arrow,
row: entry.row,
column: entry.column,
});
}
}
Ok(entries)
}
fn checked_parameters(
layout: &FamilyLayout,
fixed: &[FamilyFixedEntry],
entries: Vec<FamilyParameter>,
) -> Result<(Vec<FamilyParameterPosition>, BTreeMap<String, usize>), FamilyError> {
let mut names = BTreeMap::new();
let fixed_coordinates: BTreeMap<_, _> = fixed
.iter()
.map(|entry| ((entry.arrow, entry.row, entry.column), ()))
.collect();
let mut coordinates = BTreeMap::new();
let mut positions = Vec::new();
positions
.try_reserve(entries.len())
.map_err(|_| FamilyError::CoordinateAllocationFailed {
coordinates: entries.len(),
})?;
for (index, parameter) in entries.into_iter().enumerate() {
if parameter.name.is_empty() {
return Err(FamilyError::EmptyParameterName);
}
if names.insert(parameter.name.clone(), index).is_some() {
return Err(FamilyError::DuplicateParameterName {
name: parameter.name,
});
}
let coordinate =
checked_coordinate(layout, parameter.arrow, parameter.row, parameter.column)?;
let key = (parameter.arrow, parameter.row, parameter.column);
if fixed_coordinates.contains_key(&key) {
return Err(FamilyError::FixedParameterCollision {
arrow: parameter.arrow,
row: parameter.row,
column: parameter.column,
});
}
if coordinates.insert(key, ()).is_some() {
return Err(FamilyError::DuplicateParameterCoordinate {
arrow: parameter.arrow,
row: parameter.row,
column: parameter.column,
});
}
positions.push(FamilyParameterPosition {
name: parameter.name,
coordinate,
index,
});
}
Ok((positions, names))
}