use super::{
GlobRead, Holding, HoldingKey, Index, LoadError, NativeAdmission, OrderedTable, Place,
QueryRows, Steps, StorageError, Supply, Transient, UseDecl, Work, WorkList, search_units,
tally,
};
mod marks;
use marks::Marks;
pub(super) fn reader(reads: &[Vec<GlobRead>]) -> Option<usize> {
let mut candidates = reads
.iter()
.enumerate()
.filter(|(_, reads)| reads.len() >= 2);
match (candidates.next(), candidates.next()) {
(Some((reader, _)), None) => Some(reader),
_ => None,
}
}
pub(super) struct CutHolding {
holders: Marks,
firm_equivalent: bool,
}
impl CutHolding {
pub(super) fn answer(
&self,
from: usize,
returning: bool,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
) -> Result<bool, LoadError> {
Ok(self
.holders
.get(from, charge)?
.is_some_and(|mark| mark == if returning { 2 } else { 1 }))
}
}
#[derive(Default)]
pub(super) struct Cuts {
rows: OrderedTable<(usize, HoldingKey), CutHolding>,
live: usize,
}
pub(super) enum Returning<'a> {
Full(&'a Holding, Option<(usize, usize)>),
Cut(&'a CutHolding),
}
impl Returning<'_> {
pub(super) fn returns(
&self,
from: usize,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
) -> Result<bool, LoadError> {
Ok(match self {
Self::Full(proof, Some(outer)) => proof
.span
.get(&from)
.is_some_and(|inner| outer.0 <= inner.0 && inner.1 <= outer.1),
Self::Full(_, None) => false,
Self::Cut(proof) => return proof.answer(from, true, charge),
})
}
}
fn admitted<T>(
memory: &Transient<'_>,
decl: &UseDecl,
live: &mut usize,
action: impl FnOnce(
&mut purrdf_lex::allocation::Memory<'_, NativeAdmission<'_>>,
) -> Result<T, StorageError>,
) -> Result<T, LoadError> {
let mut admission = NativeAdmission::resume(
Steps::LoadAt {
memory,
file: &decl.file,
line: decl.line,
},
*live,
);
let result = {
let mut native = purrdf_lex::allocation::Memory::resume(&mut admission, *live);
let result = action(&mut native);
*live = native.admitted_bytes();
result
};
result.map_err(|error| admission.graph_error(error.into()))
}
struct Walk<'s, 'm> {
holders: Marks,
retained: &'s Transient<'m>,
modules: usize,
visited: OrderedTable<Place, ()>,
pending: WorkList<Place, 8>,
live: usize,
cut: Place,
reader_reachable: bool,
}
impl Walk<'_, '_> {
fn visit(
&mut self,
place: &Place,
returning: bool,
memory: &Transient<'_>,
decl: &UseDecl,
step: &mut dyn FnMut(usize) -> Result<(), LoadError>,
) -> Result<(), LoadError> {
step(1 + place.1.len())?;
let requested = place.1 == self.cut.1 && place.2 == self.cut.2;
if !returning && requested && place.0 == self.cut.0 {
self.reader_reachable = true;
return Ok(());
}
if requested {
if !self
.holders
.mark(place.0, self.modules, returning, self.retained, decl, step)?
{
return Ok(());
}
} else {
step((6 + place.1.len()).saturating_mul(4 * search_units(self.visited.len())))?;
if self.visited.get(place).is_some() {
return Ok(());
}
}
admitted(memory, decl, &mut self.live, |native| {
if !requested {
self.visited.insert(place.clone(), (), native)?;
}
self.pending.try_push_admitted(place.clone(), native)
})
}
fn drain(
&mut self,
index: &Index,
(supply, key): (&Supply<'_>, &HoldingKey),
returning: bool,
memory: &Transient<'_>,
step: &mut dyn FnMut(usize) -> Result<(), LoadError>,
rows: &mut Option<&mut QueryRows<'_, '_, '_>>,
) -> Result<bool, LoadError> {
let decl = &index.uses[index.glob_imports[0]];
let mut firm_equivalent = true;
while let Some(place) = self.pending.pop() {
step(1)?;
firm_equivalent &= index.visit_holder_routes(
supply,
key,
&place,
step,
rows,
|destination, step| self.visit(destination, returning, memory, decl, step),
)?;
}
Ok(firm_equivalent)
}
}
impl Index {
pub(super) fn retained_cut<'s>(
&self,
supply: &'s mut Supply<'_>,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
reader: usize,
query: &HoldingKey,
rows: Option<&mut QueryRows<'_, '_, '_>>,
) -> Result<&'s CutHolding, LoadError> {
#[cfg(test)]
super::reference::retrieved_holder();
let mut other = query.clone();
other.4 = !other.4;
let other = (reader, other);
charge(1 + (1 + query.1.len()).saturating_mul(8 * search_units(supply.cuts.rows.len())))?;
let key = if supply
.cuts
.rows
.get(&other)
.is_some_and(|proof| proof.firm_equivalent)
{
other
} else {
(reader, query.clone())
};
if supply.cuts.rows.get(&key).is_none() {
let proof = self.cut_holding(supply, charge, reader, &key.1, rows)?;
let decl = &self.uses[self.glob_imports[0]];
admitted(&supply.memory, decl, &mut supply.cuts.live, |native| {
supply.cuts.rows.insert(key.clone(), proof, native)
})?;
}
Ok(supply
.cuts
.rows
.get(&key)
.expect("the exact reader-qualified proof was admitted"))
}
fn cut_holding(
&self,
supply: &Supply<'_>,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
reader: usize,
query: &HoldingKey,
mut rows: Option<&mut QueryRows<'_, '_, '_>>,
) -> Result<CutHolding, LoadError> {
let (id, name, at, required, carried) = query;
let memory = supply.memory.child();
let decl = &self.uses[self.glob_imports[0]];
let mut step = |units| {
tally::add(Work::SupplySteps, units);
charge(units)
};
let mut walk = Walk {
holders: Marks::default(),
retained: &supply.memory,
modules: self.modules.len(),
visited: OrderedTable::default(),
pending: WorkList::new(),
live: 0,
cut: (reader, name.clone(), *at),
reader_reachable: false,
};
let mut firm_equivalent = true;
for (root, level) in supply.roots.get(id).into_iter().flatten() {
step(1)?;
if root.2 != *at || !self.level_covers(*level, *required, &mut step)? {
continue;
}
firm_equivalent &= !level.is_companion();
if !level.is_companion() || *carried {
walk.visit(root, false, &memory, decl, &mut step)?;
}
}
firm_equivalent &=
walk.drain(self, (supply, query), false, &memory, &mut step, &mut rows)?;
if walk.reader_reachable {
let cut = walk.cut.clone();
walk.visit(&cut, true, &memory, decl, &mut step)?;
firm_equivalent &=
walk.drain(self, (supply, query), true, &memory, &mut step, &mut rows)?;
}
Ok(CutHolding {
holders: walk.holders,
firm_equivalent,
})
}
pub(super) fn visit_holder_routes(
&self,
supply: &Supply<'_>,
query: &HoldingKey,
held: &Place,
step: &mut dyn FnMut(usize) -> Result<(), LoadError>,
rows: &mut Option<&mut QueryRows<'_, '_, '_>>,
mut visit: impl FnMut(
&Place,
&mut dyn FnMut(usize) -> Result<(), LoadError>,
) -> Result<(), LoadError>,
) -> Result<bool, LoadError> {
let (id, _, _, required, carried) = query;
let mut firm_equivalent = true;
for (destination, level) in supply.named.get(&(*id, held.clone())).into_iter().flatten() {
step(1)?;
let visible = self.level_covers(*level, *required, step)?;
let promoted =
!visible && self.promoted_companion(destination, *id, *required, step, rows)?;
if visible || promoted {
let companion = level.is_companion() || promoted;
firm_equivalent &= !companion;
if !companion || *carried {
visit(destination, step)?;
}
}
}
for &(module, at_read, glob_level) in &supply.readers[held.0] {
step(1)?;
if self.binds_itself(module, &held.1, held.2) {
continue;
}
let view = self.globs.reads[module][at_read].view;
let Some(level) = self.routed_level(view, &held.1, held.2, *id, rows, step)? else {
continue;
};
let destination = (module, held.1.clone(), held.2);
let visible = self.level_covers(glob_level, *required, step)?
&& self.level_covers(level, *required, step)?;
let promoted =
!visible && self.promoted_companion(&destination, *id, *required, step, rows)?;
if visible || promoted {
let companion = level.is_companion() || promoted;
firm_equivalent &= !companion;
if !companion || *carried {
visit(&destination, step)?;
}
}
}
Ok(firm_equivalent)
}
}