use purrdf_lex::allocation::{Admission, Memory, OrderedTable, Shared, StorageError};
use purrdf_lex::walk::{WorkList, try_equal_range_by};
use super::{GlobFacts, GlobPath, Index, LoadError, Namespace, Source, Steps};
use crate::meter::{Meter, NativeAdmission, Transient};
use crate::path::RelPath;
struct FactAdmission<'m> {
native: NativeAdmission<'m>,
steps: Steps<'m>,
live: usize,
failure: Option<LoadError>,
}
impl Admission for FactAdmission<'_> {
fn resize(&mut self, live: usize) -> Result<(), StorageError> {
if live > self.live {
let words = (live - self.live).div_ceil(size_of::<usize>());
if let Err(error) = self.steps.storage_work(words.saturating_mul(4)) {
self.failure = Some(error);
return Err(StorageError::AdmissionFailed);
}
}
self.native.resize(live)?;
self.live = live;
Ok(())
}
}
pub(super) fn table_work(len: usize, steps: Steps<'_>) -> Result<(), LoadError> {
steps.storage_work(table_units(len))
}
pub(super) fn table_units(len: usize) -> usize {
8 * (len.max(1).ilog2() as usize + 1)
}
struct Account<'m> {
steps: Steps<'m>,
items: Option<(&'m Meter, &'m RelPath, Option<usize>)>,
live: usize,
}
impl<'m> Account<'m> {
fn scratch(steps: Steps<'m>) -> Self {
Self {
steps,
items: None,
live: 0,
}
}
fn native<T>(
&mut self,
action: impl FnOnce(&mut Memory<'_, FactAdmission<'_>>) -> Result<T, StorageError>,
) -> Result<T, LoadError> {
let native = self.items.map_or_else(
|| NativeAdmission::resume(self.steps, self.live),
|(meter, file, line)| NativeAdmission::items(meter, file, line, self.live),
);
let mut admission = FactAdmission {
native,
steps: self.steps,
live: self.live,
failure: None,
};
let result = {
let mut memory = Memory::resume(&mut admission, self.live);
let result = action(&mut memory);
self.live = memory.admitted_bytes();
result
};
result.map_err(|error| {
admission
.failure
.take()
.unwrap_or_else(|| admission.native.graph_error(error.into()))
})
}
fn insert<K: Ord, V>(
&mut self,
table: &mut OrderedTable<K, V>,
key: K,
value: V,
) -> Result<Option<V>, LoadError> {
table_work(table.len(), self.steps)?;
self.native(|memory| table.insert(key, value, memory))
}
fn push<T>(&mut self, into: &mut Vec<T>, value: T) -> Result<(), LoadError> {
self.steps.storage_work(1)?;
self.native(|memory| memory.push(into, value))
}
fn queue<T>(&mut self, into: &mut WorkList<T, 8>, value: T) -> Result<(), LoadError> {
self.steps.storage_work(1)?;
self.native(|memory| into.try_push_admitted(value, memory))
}
}
impl Index {
pub(super) fn globs_read(
&self,
reach: &[Vec<usize>],
module: usize,
ns: Namespace,
name: &str,
steps: Steps<'_>,
) -> Result<OrderedTable<usize, ()>, LoadError> {
let mut account = Account::scratch(steps);
let mut seen = OrderedTable::default();
account.insert(&mut seen, module, ())?;
let mut work = WorkList::new();
account.queue(&mut work, module)?;
let mut out = OrderedTable::default();
while let Some(at) = work.pop() {
steps.storage_work((name.len() + 1).saturating_mul(
4 * (self.scopes[at].len().max(1).ilog2() as usize + 1)
+ 4 * (self.named_imports.len().max(1).ilog2() as usize + 1),
))?;
steps.storage_work(self.imports_of(at, name).len())?;
if self.binds_explicitly(at, ns, name) {
continue;
}
table_work(self.glob_imports.len(), steps)?;
for glob in self.globs_of(at) {
account.insert(&mut out, *glob, ())?;
table_work(self.glob_imports.len(), steps)?;
let key = (self.uses[*glob].module, *glob);
let range = try_equal_range_by(&self.glob_imports, |position| {
Ok::<_, std::convert::Infallible>(
(self.uses[*position].module, *position).cmp(&key),
)
})
.expect("integer comparison cannot fail");
assert!(
!range.is_empty(),
"a module glob belongs to the frozen registry"
);
for target in &reach[range.start] {
if account.insert(&mut seen, *target, ())?.is_none() {
account.queue(&mut work, *target)?;
}
}
}
}
Ok(out)
}
pub(super) fn unresolved_glob_read(
&self,
reads: &[Source],
steps: Steps<'_>,
) -> Result<Option<usize>, LoadError> {
let Some(facts) = self.glob_facts().filter(|facts| !facts.broken.is_empty()) else {
return Ok(None);
};
let Some(source) = reads.first() else {
return Ok(None);
};
let memory = steps.query_meter().map(Transient::new);
let (file, line) = self.module_site(source.module);
let steps = steps.with_query_storage(memory.as_ref(), (&file, line));
let mut account = Account::scratch(steps);
let mut places = OrderedTable::default();
for source in reads {
steps.storage_work(source.name.len().saturating_mul(table_units(places.len())))?;
account.insert(
&mut places,
(source.module, source.ns, source.name.as_str()),
(),
)?;
}
let mut first = None;
for ((module, ns, name), ()) in places.ordered() {
let memory = steps.temporary();
let read_steps = memory.as_ref().map_or(steps, |memory| steps.at(memory));
let globs = self.globs_read(&facts.reach, *module, *ns, name, read_steps)?;
for (glob, ()) in globs.ordered() {
table_work(facts.broken.len(), steps)?;
if facts.broken.get(glob).is_some() {
first = Some(first.map_or(*glob, |old: usize| old.min(*glob)));
}
}
}
Ok(first)
}
pub(crate) fn settle_glob_facts(&mut self, meter: &Meter) -> Result<(), LoadError> {
let Some(&first) = self.glob_imports.first() else {
self.glob_facts = super::GlobFactsCache::default();
return Ok(());
};
let decl = &self.uses[first];
let memory = Transient::new(meter);
let steps = Steps::LoadAt {
memory: &memory,
file: &decl.file,
line: decl.line,
};
let mut scratch = Account::scratch(steps);
let mut retained = Account {
steps,
items: Some((meter, &decl.file, Some(decl.line))),
live: 0,
};
let mut facts = GlobFacts::default();
retained.native(|memory| memory.reserve(&mut facts.reach, self.glob_imports.len()))?;
let mut misses = OrderedTable::<usize, Vec<Source>>::default();
let mut unknown = WorkList::new();
for &glob in &self.glob_imports {
let decl = &self.uses[glob];
let path_memory = memory.child();
let path_steps = Steps::LoadAt {
memory: &path_memory,
file: &decl.file,
line: decl.line,
};
scratch.steps = Steps::LoadAt {
memory: &memory,
file: &decl.file,
line: decl.line,
};
retained.steps = scratch.steps;
retained.items = Some((meter, &decl.file, Some(decl.line)));
path_steps.storage_work(1)?;
let path = self.glob_path(glob, path_steps)?;
self.settle_lookups(meter, glob)?;
let mut row = Vec::new();
match path {
GlobPath::Resolves(targets) => {
for target in targets {
retained.push(&mut row, target)?;
}
}
GlobPath::Misses(sources) => {
let bytes = sources.capacity() * size_of::<Source>()
+ sources
.iter()
.map(|source| source.name.capacity())
.sum::<usize>();
path_memory.transfer_to(&memory, bytes, &decl.file, Some(decl.line))?;
scratch.insert(&mut misses, glob, sources)?;
}
GlobPath::Unknown => {
scratch.queue(&mut unknown, glob)?;
}
GlobPath::Nothing => {}
}
retained.push(&mut facts.reach, row)?;
}
self.complete_glob_facts(
&mut facts,
&misses,
&mut unknown,
&mut scratch,
&mut retained,
)?;
let decl = &self.uses[first];
let bytes = Shared::<GlobFacts>::allocation_layout().size();
meter.work(
bytes.div_ceil(size_of::<usize>()) * 4,
&decl.file,
Some(decl.line),
)?;
meter.items(bytes, &decl.file, Some(decl.line))?;
let facts = Shared::try_new(facts).map_err(|_| {
LoadError::new(
&decl.file,
Some(decl.line),
crate::LoadErrorKind::Storage(StorageError::AllocationFailed),
)
})?;
self.glob_facts.replace(facts);
Ok(())
}
fn complete_glob_facts<'a>(
&'a self,
facts: &mut GlobFacts,
misses: &OrderedTable<usize, Vec<Source>>,
unknown: &mut WorkList<usize, 8>,
scratch: &mut Account<'a>,
retained: &mut Account<'a>,
) -> Result<(), LoadError> {
let mut readers = OrderedTable::<usize, Vec<usize>>::default();
for (glob, sources) in misses.ordered() {
let decl = &self.uses[*glob];
let Steps::LoadAt { memory, .. } = scratch.steps else {
unreachable!("construction owns a load lease")
};
scratch.steps = Steps::LoadAt {
memory,
file: &decl.file,
line: decl.line,
};
let steps = scratch.steps;
for source in sources {
steps
.storage_work((source.name.len() + 1).saturating_mul(
4 * (self.named_imports.len().max(1).ilog2() as usize + 1),
))?;
let imports = self.imports_of(source.module, &source.name);
steps.storage_work(imports.len())?;
if imports.iter().any(|position| {
self.uses[*position]
.kind
.terminal_namespaces()
.contains(&source.ns)
}) {
scratch.queue(unknown, *glob)?;
}
let memory = steps.temporary();
let read_steps = memory.as_ref().map_or(steps, |memory| steps.at(memory));
let read = self.globs_read(
&facts.reach,
source.module,
source.ns,
&source.name,
read_steps,
)?;
for (other, ()) in read.ordered() {
if other == glob {
continue;
}
table_work(readers.len(), steps)?;
if readers.get(other).is_none() {
scratch.insert(&mut readers, *other, Vec::new())?;
}
table_work(readers.len(), steps)?;
let row = readers.get_mut(other).expect("the reader row was admitted");
scratch.push(row, *glob)?;
}
}
}
let mut opaque = OrderedTable::default();
while let Some(glob) = unknown.pop() {
let decl = &self.uses[glob];
let Steps::LoadAt { memory, .. } = scratch.steps else {
unreachable!("construction owns a load lease")
};
scratch.steps = Steps::LoadAt {
memory,
file: &decl.file,
line: decl.line,
};
if scratch.insert(&mut opaque, glob, ())?.is_none() {
table_work(readers.len(), scratch.steps)?;
for &reader in readers.get(&glob).into_iter().flatten() {
scratch.queue(unknown, reader)?;
}
}
}
for (glob, _) in misses.ordered() {
let decl = &self.uses[*glob];
let Steps::LoadAt { memory, .. } = scratch.steps else {
unreachable!("construction owns a load lease")
};
retained.steps = Steps::LoadAt {
memory,
file: &decl.file,
line: decl.line,
};
retained.items = Some((
retained.items.expect("retained index admission").0,
&decl.file,
Some(decl.line),
));
table_work(opaque.len(), scratch.steps)?;
if opaque.get(glob).is_none() {
retained.insert(&mut facts.broken, *glob, ())?;
}
}
Ok(())
}
}