use std::collections::hash_map::Entry;
use std::convert::Infallible;
use std::fmt;
use std::hash::Hash;
use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::{Arc, Mutex, OnceLock};
use rustc_hash::FxHashMap;
use crate::algebra::{Algebra, AlgebraBuildError};
use crate::ar::TauError;
use crate::ar::tau_with_opposite;
use crate::basic::{
BasicDecomposition, BasicError, ProjectiveSupport, SupportPairIsoOutcome, pair_iso,
};
use crate::decompose::Decomposition;
use crate::endo::EndoAlgebra;
use crate::hom::HomError;
use crate::module::Module;
use crate::opposite::OppositeMap;
#[derive(Clone)]
pub(crate) struct ModuleKey(Module);
debug_fields!(
ModuleKey |this| {
"addr" => this.0.addr();
"dim_vector" => this.0.dim_vector();
});
impl ModuleKey {
pub(crate) fn new(module: &Module) -> ModuleKey {
Self(module.clone())
}
accessor_methods! {
#[cfg(test)]
pub(crate) module() -> &Module = |this| &this.0;
}
}
nominal_key!(ModuleKey, |this, other| this.0.ptr_eq(&other.0), |this| {
this.0.addr()
});
#[derive(Clone)]
pub(crate) struct AlgebraKey(Arc<Algebra>);
debug_fields!(
AlgebraKey |this| {
"addr" => Arc::as_ptr(&this.0) as usize;
});
impl AlgebraKey {
pub(crate) fn new(algebra: &Arc<Algebra>) -> AlgebraKey {
Self(algebra.clone())
}
}
nominal_key!(
AlgebraKey,
|this, other| Arc::ptr_eq(&this.0, &other.0),
|this| Arc::as_ptr(&this.0) as usize
);
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub(crate) struct BasicKey {
assembled: ModuleKey,
summands: Box<[ModuleKey]>,
}
impl BasicKey {
pub(crate) fn new(decomposition: &BasicDecomposition) -> BasicKey {
let assembled = ModuleKey::new(decomposition.module());
let summands = decomposition
.summands()
.iter()
.map(|summand| ModuleKey::new(summand.module()))
.collect();
BasicKey {
assembled,
summands,
}
}
}
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub(crate) struct SupportKey {
algebra: AlgebraKey,
vertices: Box<[u32]>,
}
impl SupportKey {
pub(crate) fn new(support: &ProjectiveSupport) -> SupportKey {
Self {
algebra: AlgebraKey::new(support.algebra()),
vertices: support.vertices().into(),
}
}
}
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub(crate) struct PairKey {
module: BasicKey,
projective: SupportKey,
}
impl PairKey {
pub(crate) fn new(module: &BasicDecomposition, projective: &ProjectiveSupport) -> PairKey {
Self {
module: BasicKey::new(module),
projective: SupportKey::new(projective),
}
}
}
pub(crate) struct Memo<K, V, E> {
cells: Mutex<FxHashMap<K, MemoCell<V, E>>>,
hits: AtomicU64,
misses: AtomicU64,
}
type MemoCell<V, E> = Arc<OnceLock<Result<Arc<V>, Arc<E>>>>;
impl<K: Eq + Hash, V, E> fmt::Debug for Memo<K, V, E> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("Memo").field("len", &self.len()).finish()
}
}
impl<K: Eq + Hash, V, E> Memo<K, V, E> {
pub(crate) fn new() -> Memo<K, V, E> {
Memo {
cells: Mutex::new(FxHashMap::default()),
hits: AtomicU64::new(0),
misses: AtomicU64::new(0),
}
}
pub(crate) fn get_or_compute<F>(&self, key: K, compute: F) -> Result<Arc<V>, Arc<E>>
where
F: FnOnce() -> Result<V, E>,
{
let (cell, miss) = {
let mut cells = self
.cells
.lock()
.expect("the map lock covers one map operation, which does not panic");
match cells.entry(key) {
Entry::Occupied(entry) => (Arc::clone(entry.get()), false),
Entry::Vacant(entry) => {
let cell = entry.insert(Arc::new(OnceLock::new()));
(Arc::clone(cell), true)
}
}
};
(if miss { &self.misses } else { &self.hits }).fetch_add(1, Ordering::Relaxed);
cell.get_or_init(|| compute().map(Arc::new).map_err(Arc::new))
.clone()
}
fn value<F>(&self, key: K, compute: F) -> Result<Arc<V>, E>
where
E: Clone,
F: FnOnce() -> Result<V, E>,
{
self.get_or_compute(key, compute)
.map_err(|error| (*error).clone())
}
accessor_methods! {
pub(crate) len() -> usize = |this| this.cells
.lock()
.expect("the map lock covers one map operation, which does not panic")
.len();
#[cfg(test)]
stats() -> (u64, u64) = |this| (
this.hits.load(Ordering::Relaxed),
this.misses.load(Ordering::Relaxed),
);
#[cfg(test)]
pub(crate) is_empty() -> bool = |this| this.len() == 0;
}
}
#[derive(Debug)]
pub(crate) struct VerificationContext {
opposite: Memo<AlgebraKey, OppositeMap, AlgebraBuildError>,
endo: Memo<ModuleKey, EndoAlgebra, Infallible>,
hom_dim: Memo<(ModuleKey, ModuleKey), usize, HomError>,
tau: Memo<ModuleKey, Module, TauError>,
decompose: Memo<ModuleKey, Decomposition, Infallible>,
pair_iso: Memo<(PairKey, PairKey), SupportPairIsoOutcome, BasicError>,
}
impl VerificationContext {
pub(crate) fn new() -> VerificationContext {
VerificationContext {
opposite: Memo::new(),
endo: Memo::new(),
hom_dim: Memo::new(),
tau: Memo::new(),
decompose: Memo::new(),
pair_iso: Memo::new(),
}
}
pub(crate) fn opposite_for(
&self,
algebra: &Arc<Algebra>,
) -> Result<Arc<OppositeMap>, AlgebraBuildError> {
self.opposite.value(AlgebraKey::new(algebra), || {
crate::opposite::opposite(algebra)
})
}
pub(crate) fn endo_for(&self, module: &Module) -> Arc<EndoAlgebra> {
self.endo
.value(ModuleKey::new(module), || Ok(EndoAlgebra::new(module)))
.unwrap_or_else(|never| match never {})
}
pub(crate) fn hom_dim_for(&self, source: &Module, target: &Module) -> Result<usize, HomError> {
self.hom_dim
.value((ModuleKey::new(source), ModuleKey::new(target)), || {
crate::hom::hom_dim(source, target)
})
.map(|value| *value)
}
pub(crate) fn tau_for(&self, module: &Module) -> Result<Arc<Module>, TauError> {
self.tau.value(ModuleKey::new(module), || {
let opposite = self
.opposite_for(module.algebra())
.map_err(TauError::Opposite)?;
tau_with_opposite(module, &opposite)
})
}
pub(crate) fn decompose_for(&self, module: &Module) -> Arc<Decomposition> {
self.decompose
.value(ModuleKey::new(module), || {
let root = (!module.is_zero()).then(|| self.endo_for(module).as_ref().clone());
Ok(crate::decompose::decompose_with_root_endo(module, root))
})
.unwrap_or_else(|never| match never {})
}
pub(crate) fn pair_iso_for(
&self,
first_module: &BasicDecomposition,
first_projective: &ProjectiveSupport,
second_module: &BasicDecomposition,
second_projective: &ProjectiveSupport,
) -> Result<Arc<SupportPairIsoOutcome>, BasicError> {
self.pair_iso.value(
(
PairKey::new(first_module, first_projective),
PairKey::new(second_module, second_projective),
),
|| {
pair_iso(
first_module,
first_projective,
second_module,
second_projective,
)
},
)
}
#[cfg(test)]
pub(crate) fn memo_stats(&self) -> (u64, u64) {
let stats = [
self.opposite.stats(),
self.endo.stats(),
self.hom_dim.stats(),
self.tau.stats(),
self.decompose.stats(),
self.pair_iso.stats(),
];
(
stats.iter().map(|(hits, _)| hits).sum(),
stats.iter().map(|(_, misses)| misses).sum(),
)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::algebra::{kronecker, linear_an};
use crate::ar::tau;
use crate::basic::pair_iso;
use crate::decompose::decompose;
use crate::field::PrimeField;
use crate::hom::hom_dim;
use crate::iso::{IsoOutcome, is_isomorphic};
use crate::linalg::DenseMat;
fn fields() -> [PrimeField; 2] {
[PrimeField::new(2).unwrap(), PrimeField::new(5).unwrap()]
}
fn kronecker_pair(field: PrimeField) -> (Module, Module) {
let algebra = kronecker(2, field);
let one = DenseMat::from_rows(&[vec![field.one()]]);
let zero = DenseMat::zero(1, 1);
let build = |maps: Vec<DenseMat>| {
Module::new(algebra.clone(), vec![1, 1], maps).expect("a kronecker representation")
};
(
build(vec![one.clone(), zero.clone()]),
build(vec![zero, one]),
)
}
fn basic(m: &Module) -> BasicDecomposition {
BasicDecomposition::new(m).expect("a kronecker regular module is indecomposable")
}
#[test]
fn verification_context_separates_nominal_kronecker_modules() {
for field in fields() {
let (x, y) = kronecker_pair(field);
let context = VerificationContext::new();
let tau_x = context
.tau
.get_or_compute(ModuleKey::new(&x), || tau(&x))
.expect("kronecker translates");
let tau_y = context
.tau
.get_or_compute(ModuleKey::new(&y), || tau(&y))
.expect("kronecker translates");
assert_eq!(hom_dim(&y, &tau_y).expect("one algebra"), 1);
assert_eq!(hom_dim(&y, &tau_x).expect("one algebra"), 0);
assert_eq!(context.tau.len(), 2);
let uncached = tau(&y).expect("kronecker translates");
assert!(matches!(
is_isomorphic(&tau_y, &uncached).expect("one algebra"),
IsoOutcome::Isomorphic(_)
));
let endo_x = context
.endo
.get_or_compute(ModuleKey::new(&x), || Ok(EndoAlgebra::new(&x)))
.expect("End is total");
let endo_y = context
.endo
.get_or_compute(ModuleKey::new(&y), || Ok(EndoAlgebra::new(&y)))
.expect("End is total");
assert_eq!(context.endo.len(), 2);
assert!(endo_x.module().ptr_eq(&x));
assert!(endo_y.module().ptr_eq(&y));
let split_x = context
.decompose
.get_or_compute(ModuleKey::new(&x), || Ok(decompose(&x)))
.expect("decompose is total");
let split_y = context
.decompose
.get_or_compute(ModuleKey::new(&y), || Ok(decompose(&y)))
.expect("decompose is total");
assert_eq!(context.decompose.len(), 2);
assert!(split_x.split().total().ptr_eq(&x));
assert!(split_y.split().total().ptr_eq(&y));
let mut dims = Vec::new();
for (source, target) in [(&x, &x), (&x, &y), (&y, &x), (&y, &y)] {
let key = (ModuleKey::new(source), ModuleKey::new(target));
dims.push(
*context
.hom_dim
.get_or_compute(key, || hom_dim(source, target))
.expect("one algebra"),
);
}
assert_eq!(context.hom_dim.len(), 4);
assert_eq!(dims, vec![1, 0, 0, 1]);
let (dec_x, dec_y) = (basic(&x), basic(&y));
let support = ProjectiveSupport::new(x.algebra(), &[]).expect("the empty support");
let (key_x, key_y) = (
PairKey::new(&dec_x, &support),
PairKey::new(&dec_y, &support),
);
let same = context
.pair_iso
.get_or_compute((key_x.clone(), key_x.clone()), || {
pair_iso(&dec_x, &support, &dec_x, &support)
})
.expect("both pairs are certified");
let cross = context
.pair_iso
.get_or_compute((key_x, key_y), || {
pair_iso(&dec_x, &support, &dec_y, &support)
})
.expect("both pairs are certified");
assert_eq!(context.pair_iso.len(), 2);
assert!(matches!(*same, SupportPairIsoOutcome::Isomorphic(_)));
assert!(matches!(*cross, SupportPairIsoOutcome::NotIsomorphic(_)));
for module in [&x, &y] {
context
.opposite
.get_or_compute(AlgebraKey::new(module.algebra()), || {
crate::opposite::opposite(module.algebra())
})
.expect("the kronecker algebra has an opposite");
}
assert_eq!(context.opposite.len(), 1);
}
}
#[test]
fn the_second_request_for_one_key_returns_the_stored_value() {
let (x, _) = kronecker_pair(fields()[1]);
let context = VerificationContext::new();
let first = context
.tau
.get_or_compute(ModuleKey::new(&x), || tau(&x))
.expect("kronecker translates");
let second = context
.tau
.get_or_compute(ModuleKey::new(&x), || {
unreachable!("a stored entry answers the second request")
})
.expect("kronecker translates");
assert!(Arc::ptr_eq(&first, &second));
assert_eq!(context.tau.len(), 1);
}
#[test]
fn a_stored_failure_answers_later_callers_with_the_same_error() {
let (x, _) = kronecker_pair(fields()[1]);
let memo: Memo<ModuleKey, usize, String> = Memo::new();
let first = memo
.get_or_compute(ModuleKey::new(&x), || Err("routes disagree".into()))
.expect_err("the computation failed");
assert_eq!(memo.len(), 1);
let second = memo
.get_or_compute(ModuleKey::new(&x), || {
unreachable!("a stored failure answers the second request")
})
.expect_err("the stored failure is returned again");
assert_eq!(*second, "routes disagree");
assert!(Arc::ptr_eq(&first, &second));
}
#[test]
fn a_new_verification_context_holds_no_entries() {
let context = VerificationContext::new();
assert!(context.opposite.is_empty());
assert!(context.endo.is_empty());
assert!(context.hom_dim.is_empty());
assert!(context.tau.is_empty());
assert!(context.decompose.is_empty());
assert!(context.pair_iso.is_empty());
}
#[test]
fn a_module_key_keeps_its_address_out_of_later_allocations() {
let algebra = kronecker(2, fields()[1]);
let key = ModuleKey::new(&Module::simple(&algebra, 0));
for _ in 0..64 {
let later = Module::simple(&algebra, 0);
assert_ne!(key, ModuleKey::new(&later));
}
assert_eq!(key, ModuleKey::new(key.module()));
}
#[test]
fn a_support_key_separates_two_algebras_whose_supports_compare_equal() {
let field = fields()[1];
let (first, second) = (kronecker(2, field), kronecker(2, field));
let a = ProjectiveSupport::new(&first, &[0]).expect("vertex 0 is a vertex");
let b = ProjectiveSupport::new(&second, &[0]).expect("vertex 0 is a vertex");
assert_eq!(a, b);
assert_ne!(SupportKey::new(&a), SupportKey::new(&b));
}
#[test]
fn a_basic_key_separates_two_orders_of_one_summand_list() {
let (x, y) = kronecker_pair(fields()[1]);
let (sum, _, _) = crate::module::direct_sum(&[&x, &y]);
let assembled = ModuleKey::new(&sum);
let forward = BasicKey {
assembled: assembled.clone(),
summands: Box::new([ModuleKey::new(&x), ModuleKey::new(&y)]),
};
let backward = BasicKey {
assembled,
summands: Box::new([ModuleKey::new(&y), ModuleKey::new(&x)]),
};
assert_ne!(forward, backward);
}
#[test]
fn the_hom_dim_key_separates_the_two_orders_of_one_module_pair() {
let algebra = linear_an(2, fields()[1]);
let projective = Module::projective(&algebra, 0);
let simple = Module::simple(&algebra, 0);
let forward = hom_dim(&projective, &simple).expect("one algebra");
let backward = hom_dim(&simple, &projective).expect("one algebra");
assert_ne!(
forward, backward,
"the fixture has to be asymmetric for the memo test below to bite"
);
let context = VerificationContext::new();
let mut stored = Vec::new();
for (source, target) in [(&projective, &simple), (&simple, &projective)] {
let key = (ModuleKey::new(source), ModuleKey::new(target));
stored.push(
*context
.hom_dim
.get_or_compute(key, || hom_dim(source, target))
.expect("one algebra"),
);
}
assert_eq!(context.hom_dim.len(), 2);
assert_eq!(stored, vec![forward, backward]);
}
#[test]
fn a_verification_context_is_shareable_across_threads() {
fn assert_send_sync<T: Send + Sync>() {}
assert_send_sync::<VerificationContext>();
}
}