use purrdf_hash::fixed::FixedState;
use purrdf_lex::allocation::{OrderedTable, StorageError};
mod cut;
mod ranked;
use purrdf_lex::walk::WorkList;
use std::borrow::Cow;
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
use std::mem::size_of;
use std::ops::Bound::{Excluded, Unbounded};
use crate::cost::{btree_entry, btree_map, hash_entry, hash_map, shared_text, vec_first, vec_slot};
use crate::error::LoadError;
use crate::facts::Vis;
use crate::index::{Index, UseDecl};
use crate::item::{ItemId, Namespace, SharedStr};
use crate::meter::{Meter, NativeAdmission, Steps, Transient};
use crate::path::RelPath;
use crate::resolve::{Fail, Heads};
use crate::settle::{Bound, Origin, vis_key};
use crate::work::{self as tally, Work};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct Level(usize);
impl Level {
const COMPANION: usize = 1;
pub(crate) const PUBLIC: Self = Self(usize::MAX - 1);
pub(crate) const NOBODY: Self = Self(usize::MAX - 3);
pub(crate) const fn within(module: usize) -> Self {
assert!(
module < Self::NOBODY.0 >> 1,
"module index does not fit a visibility level"
);
Self(module << 1)
}
pub(crate) const fn companion(self) -> Self {
Self(self.0 | Self::COMPANION)
}
const fn plain(self) -> Self {
Self(self.0 & !Self::COMPANION)
}
const fn is_companion(self) -> bool {
self.0 & Self::COMPANION != 0
}
const fn module(self) -> Option<usize> {
let plain = self.plain();
if plain.0 >= Self::NOBODY.0 {
None
} else {
Some(plain.0 >> 1)
}
}
fn order_key(self) -> (u8, usize) {
match self.plain() {
Self::PUBLIC => (if self.is_companion() { 3 } else { 5 }, 0),
Self::NOBODY => (if self.is_companion() { 2 } else { 4 }, 0),
plain => (u8::from(self.is_companion()), plain.0 >> 1),
}
}
}
impl PartialOrd for Level {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Level {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.order_key().cmp(&other.order_key())
}
}
pub(crate) const fn ambiguity_seen(candidates: usize, seen: usize) -> bool {
candidates > 1 && seen > 0
}
type Held = (ItemId, Level);
fn copy_held<'a>(
ids: &[Held],
inline: &'a mut [Held; 2],
steps: Steps<'_>,
) -> Result<Cow<'a, [Held]>, LoadError> {
steps.storage_work(ids.len())?;
if ids.len() <= inline.len() {
let held = &mut inline[..ids.len()];
held.copy_from_slice(ids);
return Ok(Cow::Borrowed(held));
}
let mut copied = Vec::new();
let mut admission = NativeAdmission::new(steps);
purrdf_lex::allocation::Memory::new(&mut admission)
.reserve(&mut copied, ids.len())
.map_err(|error| admission.graph_error(error.into()))?;
copied.extend_from_slice(ids);
Ok(Cow::Owned(copied))
}
pub(crate) fn reserve_next<T>(into: &mut Vec<T>, steps: Steps<'_>) -> Result<(), LoadError> {
let live = size_of::<T>() * into.capacity();
let mut admission = NativeAdmission::resume(steps, live);
let result =
purrdf_lex::allocation::Memory::resume(&mut admission, live).reserve_for_push(into);
result.map_err(|error| admission.graph_error(purrdf_core::graph::GraphError::Storage(error)))
}
pub(crate) fn push_work<T, const N: usize>(
into: &mut WorkList<T, N>,
value: T,
steps: Steps<'_>,
) -> Result<(), LoadError> {
let live = size_of::<T>() * into.heap_capacity();
let mut admission = NativeAdmission::resume(steps, live);
into.try_push_admitted(
value,
&mut purrdf_lex::allocation::Memory::resume(&mut admission, live),
)
.map_err(|error| admission.graph_error(error.into()))
}
fn add_holder(
place: &Place,
nodes: &mut Vec<Place>,
places: &mut BTreeMap<Place, usize>,
successors: &mut Vec<Vec<usize>>,
predecessors: &mut Vec<Vec<usize>>,
step: &mut dyn FnMut(usize) -> Result<(), LoadError>,
admit: &dyn Fn(usize) -> Result<(), LoadError>,
) -> Result<usize, LoadError> {
if let Some(node) = places.get(place) {
return Ok(*node);
}
step(1)?;
admit(SUPPLY_NODE_BYTES)?;
let node = nodes.len();
places.insert(place.clone(), node);
nodes.push(place.clone());
successors.push(Vec::new());
predecessors.push(Vec::new());
Ok(node)
}
fn sort_units(length: usize) -> usize {
if length < 2 {
0
} else {
length * (length.ilog2() as usize + 1)
}
}
fn search_units(length: usize) -> usize {
1 + length.saturating_add(1).ilog2() as usize
}
fn redelivery_bytes(found: &[(&GlobRead, Cow<'_, [Held]>)]) -> usize {
let entries = found.iter().map(|(_, held)| held.len()).sum::<usize>();
let per_entry = btree_entry::<ItemId, Vec<(Level, usize)>>()
+ vec_first::<(Level, usize)>()
+ vec_slot::<(Level, usize)>()
+ btree_entry::<ItemId, Vec<usize>>()
+ vec_first::<usize>()
+ vec_slot::<usize>();
let base = btree_map::<ItemId, Vec<(Level, usize)>>() + btree_map::<ItemId, Vec<usize>>();
base.saturating_add(entries.saturating_mul(per_entry))
}
struct SelectionRead<'a> {
offset: usize,
known: &'a [Held],
}
struct Redelivery<'a> {
selected: Vec<Option<Level>>,
reads: Vec<SelectionRead<'a>>,
}
impl<'a> Redelivery<'a> {
fn new(
index: &'a Index,
found: &[(&GlobRead, Cow<'_, [Held]>)],
name: &str,
at: usize,
memory: &Transient<'_>,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
) -> Result<Self, LoadError> {
let decl = &index.uses[index.glob_imports[0]];
let entries = found.iter().map(|(_, held)| held.len()).sum::<usize>();
charge(found.len() + entries)?;
let mut answer = Self {
selected: Vec::new(),
reads: Vec::new(),
};
let mut admission = NativeAdmission::new(Steps::LoadAt {
memory,
file: &decl.file,
line: decl.line,
});
let allocated = {
let mut native = purrdf_lex::allocation::Memory::new(&mut admission);
native
.reserve(&mut answer.reads, found.len())
.and_then(|()| native.reserve(&mut answer.selected, entries))
};
allocated.map_err(|error| admission.graph_error(error.into()))?;
answer.selected.resize(entries, None);
let mut offset = 0;
for (read, held) in found {
answer.reads.push(SelectionRead {
offset,
known: index.replacements(read, name, at),
});
offset += held.len();
}
Ok(answer)
}
}
type SelectionTable = OrderedTable<(ItemId, Vec<ItemId>), Vec<(usize, usize)>>;
#[derive(Default)]
struct SelectionGroups {
table: SelectionTable,
live: usize,
}
impl SelectionGroups {
fn add(
&mut self,
id: ItemId,
held: &[Held],
member: (usize, usize),
memory: &Transient<'_>,
decl: &UseDecl,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
) -> Result<(), LoadError> {
charge(
1 + held
.len()
.saturating_mul(search_units(self.table.len()).saturating_mul(4)),
)?;
let mut admission = NativeAdmission::resume(
Steps::LoadAt {
memory,
file: &decl.file,
line: decl.line,
},
self.live,
);
let result = {
let mut native = purrdf_lex::allocation::Memory::resume(&mut admission, self.live);
let result = self.insert(id, held, member, &mut native);
self.live = native.admitted_bytes();
result
};
result.map_err(|error| admission.graph_error(error.into()))
}
fn insert(
&mut self,
id: ItemId,
held: &[Held],
member: (usize, usize),
storage: &mut purrdf_lex::allocation::Memory<'_, NativeAdmission<'_>>,
) -> Result<(), StorageError> {
if let Some(members) = self.table.get_mut_by(|(candidate, competitors)| {
id.cmp(candidate).then_with(|| {
held.iter()
.filter_map(|entry| (entry.0 != id).then_some(entry.0))
.cmp(competitors.iter().copied())
})
}) {
storage.reserve_for_push(members)?;
members.push(member);
return Ok(());
}
let mut competitors = Vec::new();
storage.reserve(&mut competitors, held.len().saturating_sub(1))?;
competitors.extend(
held.iter()
.filter_map(|entry| (entry.0 != id).then_some(entry.0)),
);
let mut members = Vec::new();
storage.reserve_for_push(&mut members)?;
members.push(member);
let _previous = self.table.insert((id, competitors), members, storage)?;
Ok(())
}
}
fn replacement_level(known: &[Held], id: ItemId) -> Option<Level> {
known
.binary_search_by_key(&id, |entry| entry.0)
.ok()
.map(|place| known[place].1)
}
type Exported = Vec<(String, [Vec<Held>; 3])>;
type Gathered = (Exported, bool, Vec<(SharedStr, usize)>);
type Changed = (Vec<(usize, (usize, usize))>, Vec<usize>);
type Told = (usize, usize, usize, bool);
type DropNames = HashMap<SharedStr, [Vec<Held>; 3], FixedState>;
type Drops = BTreeMap<(usize, usize), DropNames>;
type Replacement = (usize, usize, SharedStr, usize, ItemId, Level);
type Lists = Box<[Vec<Held>; 3]>;
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct View {
target: usize,
class: Box<[bool]>,
names: BTreeMap<SharedStr, Lists>,
active: Vec<(usize, usize, usize)>,
turns: usize,
passive: BTreeMap<usize, Vec<usize>>,
places: BTreeMap<usize, Vec<usize>>,
site: usize,
hidden: bool,
unseen: Option<Box<Unseen>>,
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
struct Unseen {
covert: BTreeMap<usize, Vec<(usize, usize)>>,
open: BTreeSet<usize>,
hiding: BTreeSet<usize>,
dropped: BTreeSet<(SharedStr, usize)>,
}
static NO_UNSEEN: Unseen = Unseen {
covert: BTreeMap::new(),
open: BTreeSet::new(),
hiding: BTreeSet::new(),
dropped: BTreeSet::new(),
};
impl View {
fn unseen(&self) -> &Unseen {
self.unseen.as_deref().unwrap_or(&NO_UNSEEN)
}
fn unseen_mut(&mut self) -> &mut Unseen {
self.unseen.get_or_insert_with(Box::default)
}
fn unseen_bytes(&self) -> usize {
if self.unseen.is_some() {
0
} else {
size_of::<Unseen>()
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct GlobRead {
pub(crate) glob: usize,
pub(crate) target: usize,
view: usize,
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub(crate) struct GlobTables {
views: Vec<View>,
view_of: BTreeMap<(usize, Box<[bool]>), usize>,
exports: Vec<Vec<usize>>,
reads: Vec<Vec<GlobRead>>,
read_by: BTreeSet<(usize, usize)>,
passing: BTreeSet<(usize, usize, Level)>,
depth: Vec<usize>,
in_path: Vec<bool>,
strings: HashSet<SharedStr, FixedState>,
charged: usize,
drops: Drops,
replaced_names: HashMap<SharedStr, [bool; 3], FixedState>,
dropped: usize,
companions: HashMap<SharedStr, [bool; 3], FixedState>,
holding: HashMap<SharedStr, Vec<usize>, FixedState>,
exact: BTreeSet<(usize, SharedStr, usize)>,
}
struct Queue<'m> {
work: WorkList<Grown<'m>, 1>,
memory: Transient<'m>,
}
impl<'m> Queue<'m> {
fn new(meter: &'m Meter) -> Self {
Self {
work: WorkList::new(),
memory: Transient::new(meter),
}
}
fn push(&mut self, grown: Grown<'m>, decl: &UseDecl) -> Result<(), LoadError> {
let live = self.work.heap_capacity() * size_of::<Grown<'_>>();
let mut admission = NativeAdmission::resume(
Steps::LoadAt {
memory: &self.memory,
file: &decl.file,
line: decl.line,
},
live,
);
self.work
.try_push_admitted(
grown,
&mut purrdf_lex::allocation::Memory::resume(&mut admission, live),
)
.map_err(|error| admission.graph_error(error.into()))
}
}
struct Added<'m> {
ids: Vec<Held>,
_memory: Transient<'m>,
}
impl std::ops::Deref for Added<'_> {
type Target = [Held];
fn deref(&self) -> &[Held] {
&self.ids
}
}
enum Holders<'a> {
All(std::slice::Iter<'a, GlobRead>),
Places {
reads: &'a [GlobRead],
lists: std::vec::IntoIter<&'a [usize]>,
list: std::slice::Iter<'a, usize>,
left: usize,
scanned: usize,
},
}
impl Holders<'_> {
const fn scanned(&self) -> usize {
match self {
Self::All(_) => 0,
Self::Places { scanned, .. } => *scanned,
}
}
}
impl<'a> Iterator for Holders<'a> {
type Item = &'a GlobRead;
fn next(&mut self) -> Option<&'a GlobRead> {
match self {
Self::All(reads) => reads.next(),
Self::Places {
reads,
lists,
list,
left,
..
} => loop {
if let Some(place) = list.next() {
*left -= 1;
return Some(&reads[*place]);
}
*list = lists.next()?.iter();
},
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
match self {
Self::All(reads) => reads.size_hint(),
Self::Places { left, .. } => (*left, Some(*left)),
}
}
}
impl ExactSizeIterator for Holders<'_> {}
#[derive(Clone, Copy)]
enum RouteVis<'a> {
Written(&'a Vis),
At(Level),
}
impl RouteVis<'_> {
fn same(self, other: Self) -> bool {
match (self, other) {
(Self::Written(left), Self::Written(right)) => left == right,
(Self::At(left), Self::At(right)) => left.plain() == right.plain(),
_ => false,
}
}
}
struct Routes<'a> {
id: ItemId,
target: usize,
glob: usize,
kept: RouteVis<'a>,
public: bool,
first: RouteVis<'a>,
others: Vec<RouteVis<'a>>,
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub(crate) struct ImportReach {
reaches: Vec<bool>,
globbed_by: Vec<BTreeSet<usize>>,
}
struct Grown<'m> {
view: usize,
name: SharedStr,
at: usize,
ids: Added<'m>,
}
impl<'m> Grown<'m> {
const fn new(view: usize, name: SharedStr, at: usize, ids: Added<'m>) -> Self {
Self {
view,
name,
at,
ids,
}
}
}
type Place = (usize, SharedStr, usize);
type SupplyRoute = (Place, Level);
type HoldingKey = (ItemId, SharedStr, usize, Level, bool);
struct HolderGraph {
nodes: Vec<Place>,
place: BTreeMap<Place, usize>,
successors: Vec<Vec<usize>>,
predecessors: Vec<Vec<usize>>,
}
impl HolderGraph {
fn new(at: usize) -> Self {
Self {
nodes: vec![(NONE, SharedStr::from(""), at)],
place: BTreeMap::new(),
successors: vec![Vec::new()],
predecessors: vec![Vec::new()],
}
}
fn edge(
&mut self,
from: usize,
destination: &Place,
step: &mut dyn FnMut(usize) -> Result<(), LoadError>,
admit: &dyn Fn(usize) -> Result<(), LoadError>,
) -> Result<(), LoadError> {
let node = add_holder(
destination,
&mut self.nodes,
&mut self.place,
&mut self.successors,
&mut self.predecessors,
step,
admit,
)?;
admit(SUPPLY_EDGE_BYTES)?;
self.successors[from].push(node);
self.predecessors[node].push(from);
Ok(())
}
}
struct Supply<'m> {
readers: Vec<Vec<(usize, usize, Level)>>,
roots: BTreeMap<ItemId, Vec<SupplyRoute>>,
named: BTreeMap<(ItemId, Place), Vec<SupplyRoute>>,
holdings: BTreeMap<HoldingKey, Holding>,
cut_reader: Option<usize>,
cuts: cut::Cuts,
refused: Option<LoadError>,
memory: Transient<'m>,
}
#[derive(Clone, Copy)]
enum NameRow<'i> {
Unqueried,
Known(Option<&'i [Vec<Held>; 3]>),
}
struct RowScratch<'i, 'm> {
rows: Vec<NameRow<'i>>,
touched: Vec<usize>,
name: Option<SharedStr>,
memory: Transient<'m>,
}
impl<'i, 'm> RowScratch<'i, 'm> {
fn new(
views: usize,
memory: Transient<'m>,
decl: &UseDecl,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
) -> Result<Self, LoadError> {
charge(views)?;
let mut scratch = Self {
rows: Vec::new(),
touched: Vec::new(),
name: None,
memory,
};
let mut admission = NativeAdmission::new(Steps::LoadAt {
memory: &scratch.memory,
file: &decl.file,
line: decl.line,
});
let result = {
let mut native = purrdf_lex::allocation::Memory::new(&mut admission);
native
.reserve(&mut scratch.rows, views)
.and_then(|()| native.reserve(&mut scratch.touched, views))
};
result.map_err(|error| admission.graph_error(error.into()))?;
scratch.rows.resize(views, NameRow::Unqueried);
Ok(scratch)
}
fn insert(&mut self, view: usize, row: Option<&'i [Vec<Held>; 3]>) {
self.touched.push(view);
self.rows[view] = NameRow::Known(row);
}
}
struct QueryRows<'q, 'i, 'm> {
index: &'i Index,
name: &'q str,
scratch: &'q mut RowScratch<'i, 'm>,
}
impl<'q, 'i, 'm> QueryRows<'q, 'i, 'm> {
fn new(
index: &'i Index,
name: &'q SharedStr,
phase: &'q mut Option<RowScratch<'i, 'm>>,
memory: &Transient<'m>,
decl: &UseDecl,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
) -> Result<Self, LoadError> {
if phase.is_none() {
*phase = Some(RowScratch::new(
index.globs.views.len(),
memory.child(),
decl,
charge,
)?);
}
let scratch = phase.as_mut().expect("the phase row scratch was admitted");
charge(1)?;
let same = scratch
.name
.as_ref()
.is_some_and(|previous| std::ptr::eq(previous.as_str(), name.as_str()));
if !same {
charge(1 + scratch.touched.len())?;
for view in scratch.touched.drain(..) {
scratch.rows[view] = NameRow::Unqueried;
}
scratch.name = Some(name.clone());
}
Ok(Self {
index,
name,
scratch,
})
}
fn matches(&self, name: &str) -> bool {
std::ptr::eq(name, self.name) || name == self.name
}
fn raw_row(&mut self, view: usize) -> Option<&'i [Vec<Held>; 3]> {
match self.scratch.rows[view] {
NameRow::Known(row) => row,
NameRow::Unqueried => self.fill_raw_row(view),
}
}
fn fill_raw_row(&mut self, view: usize) -> Option<&'i [Vec<Held>; 3]> {
let row = self.index.globs.views[view]
.names
.get(self.name)
.map(Box::as_ref);
self.scratch.insert(view, row);
row
}
fn level(
&mut self,
view: usize,
name: &str,
at: usize,
id: ItemId,
charge: &mut dyn FnMut(usize) -> Result<(), LoadError>,
) -> Result<Option<Level>, LoadError> {
charge(1)?;
if !std::ptr::eq(name, self.name) {
charge(1 + name.len().min(self.name.len()))?;
if name != self.name {
return Ok(self.index.held_level(view, name, at, id));
}
}
charge(1)?;
let row = if let NameRow::Known(row) = self.scratch.rows[view] {
row
} else {
charge(1)?;
self.fill_raw_row(view)
};
Ok(row.and_then(|lists| {
let held = &lists[at];
held.binary_search_by_key(&id, |entry| entry.0)
.ok()
.map(|place| held[place].1)
}))
}
}
struct Routing<'a, 'i, 'm> {
index: &'i Index,
supply: &'a mut Supply<'m>,
reader: usize,
name: &'a SharedStr,
at: usize,
charge: &'a dyn Fn(usize) -> Result<(), LoadError>,
rows: QueryRows<'a, 'i, 'm>,
}
impl Routing<'_, '_, '_> {
fn ask(&mut self, from: usize, id: ItemId, level: Level, returning: bool) -> bool {
self.index.supplied(
self.supply,
self.charge,
from,
self.reader,
self.name,
self.at,
id,
level,
returning,
Some(&mut self.rows),
)
}
fn returning(
&mut self,
id: ItemId,
required: Level,
apply: impl FnOnce(cut::Returning<'_>) -> Result<(), LoadError>,
) -> Result<(), LoadError> {
if self.supply.refused.is_some() || required == Level::NOBODY {
return Ok(());
}
if self.supply.cut_reader == Some(self.reader) {
let key = (id, self.name.clone(), self.at, required, true);
let proof = self.index.retained_cut(
self.supply,
self.charge,
self.reader,
&key,
Some(&mut self.rows),
)?;
return apply(cut::Returning::Cut(proof));
}
let other = (id, self.name.clone(), self.at, required, false);
let key = if self
.supply
.holdings
.get(&other)
.is_some_and(|proof| proof.firm_equivalent)
{
other
} else {
(id, self.name.clone(), self.at, required, true)
};
let proof =
self.index
.retained_holding(self.supply, self.charge, &key, Some(&mut self.rows))?;
let reader = proof.span.get(&self.reader).copied();
apply(cut::Returning::Full(proof, reader))
}
}
#[derive(Default)]
struct Holding {
span: BTreeMap<usize, (usize, usize)>,
firm_equivalent: bool,
}
impl Holding {
fn retain(
place: BTreeMap<Place, usize>,
span: &[(usize, usize)],
firm_equivalent: bool,
name: &SharedStr,
at: usize,
memory: &Transient<'_>,
decl: &UseDecl,
) -> Result<Self, LoadError> {
let retained = place
.keys()
.filter(|(_, held_name, held_at)| held_name == name && *held_at == at)
.count();
memory.charge(
btree_map::<usize, (usize, usize)>()
+ retained * btree_entry::<usize, (usize, usize)>(),
&decl.file,
Some(decl.line),
)?;
Ok(Self {
firm_equivalent,
span: place
.into_iter()
.filter(|((_, held_name, held_at), _)| held_name == name && *held_at == at)
.map(|((module, _, _), node)| (module, span[node]))
.collect(),
})
}
fn holds(&self, module: usize) -> bool {
self.span.contains_key(&module)
}
fn dominates(&self, module: usize, held: usize) -> bool {
match (self.span.get(&module), self.span.get(&held)) {
(Some(outer), Some(inner)) => outer.0 <= inner.0 && inner.1 <= outer.1,
_ => false,
}
}
}
const SUPPLY_NODE_BYTES: usize = btree_entry::<Place, usize>()
+ vec_slot::<Place>()
+ 4 * (vec_slot::<Vec<usize>>() + vec_first::<usize>())
+ 9 * vec_slot::<usize>()
+ vec_slot::<(usize, usize)>();
const SUPPLY_EDGE_BYTES: usize = 2 * vec_slot::<usize>() + vec_slot::<(usize, usize)>();
const SUPPLY_BASE_BYTES: usize = btree_map::<Place, usize>()
+ vec_first::<Place>()
+ 4 * vec_first::<Vec<usize>>()
+ 9 * vec_first::<usize>()
+ vec_first::<(usize, usize)>()
+ SUPPLY_NODE_BYTES;
const NONE: usize = usize::MAX;
const VIEW_BYTES: usize = vec_slot::<View>()
+ btree_entry::<(usize, Box<[bool]>), usize>()
+ vec_slot::<usize>()
+ vec_first::<usize>()
+ btree_map::<SharedStr, Lists>()
+ vec_first::<(usize, usize, usize)>()
+ 2 * btree_map::<usize, Vec<usize>>();
const NAME_BYTES: usize = btree_entry::<SharedStr, Lists>() + size_of::<[Vec<Held>; 3]>();
const READ_BYTES: usize = vec_slot::<GlobRead>()
+ btree_entry::<(usize, usize), ()>()
+ btree_entry::<(usize, usize, usize), ()>()
+ 2 * vec_slot::<(usize, usize, usize)>()
+ btree_entry::<usize, Vec<usize>>()
+ vec_first::<usize>()
+ vec_slot::<usize>();
const fn base_bytes(modules: usize) -> usize {
modules * (vec_slot::<Vec<usize>>() + vec_slot::<Vec<GlobRead>>())
+ vec_first::<Vec<usize>>()
+ vec_first::<Vec<GlobRead>>()
+ vec_first::<View>()
+ btree_map::<(usize, Box<[bool]>), usize>()
+ btree_map::<(usize, usize), ()>()
+ btree_map::<(usize, usize, usize), ()>()
+ hash_map::<SharedStr>()
+ hash_map::<(SharedStr, [bool; 3])>()
+ hash_map::<(SharedStr, Vec<usize>)>()
}
const fn holder_bytes(first: bool) -> usize {
vec_slot::<usize>()
+ if first {
hash_entry::<(SharedStr, Vec<usize>)>() + vec_first::<usize>()
} else {
0
}
}
const fn covert_bytes(first_of_module: bool, first_of_view: bool) -> usize {
vec_slot::<(usize, usize)>()
+ if first_of_module {
btree_entry::<usize, Vec<(usize, usize)>>() + vec_first::<(usize, usize)>()
} else {
0
}
+ if first_of_view {
btree_map::<usize, Vec<(usize, usize)>>()
} else {
0
}
}
pub(crate) const fn set_bytes<T>(first: bool) -> usize {
btree_entry::<T, ()>() + if first { btree_map::<T, ()>() } else { 0 }
}
pub(crate) trait Waiters {
fn wake(&mut self, module: usize, name: &str) -> Result<(), LoadError>;
fn waiting_on(&self, name: &str) -> Option<&BTreeSet<usize>>;
fn waited_in(
&self,
module: usize,
memory: &Transient<'_>,
file: &RelPath,
line: usize,
) -> Result<Vec<String>, LoadError>;
}
pub(crate) struct Nobody;
impl Waiters for Nobody {
fn wake(&mut self, _module: usize, _name: &str) -> Result<(), LoadError> {
Ok(())
}
fn waiting_on(&self, _name: &str) -> Option<&BTreeSet<usize>> {
None
}
fn waited_in(
&self,
_module: usize,
_memory: &Transient<'_>,
_file: &RelPath,
_line: usize,
) -> Result<Vec<String>, LoadError> {
Ok(Vec::new())
}
}
#[cfg(test)]
pub(crate) mod reference {
use std::cell::Cell;
thread_local! {
static EXACT: Cell<bool> = const { Cell::new(false) };
static BUILDS: Cell<[usize; 2]> = const { Cell::new([0; 2]) };
static DISCOVERIES: Cell<usize> = const { Cell::new(0) };
static SINGLE_RETURNING: Cell<bool> = const { Cell::new(false) };
static HOLDER_RETRIEVALS: Cell<usize> = const { Cell::new(0) };
}
struct Restore(bool);
impl Drop for Restore {
fn drop(&mut self) {
EXACT.set(self.0);
}
}
pub(crate) fn exact<T>(run: impl FnOnce() -> T) -> T {
let _restore = Restore(EXACT.replace(true));
run()
}
pub(crate) fn is_exact() -> bool {
EXACT.get()
}
pub(crate) fn built() {
let mut builds = BUILDS.get();
builds[usize::from(EXACT.get())] += 1;
BUILDS.set(builds);
}
pub(crate) fn builds() -> [usize; 2] {
BUILDS.get()
}
pub(crate) fn with_single_returning<T>(run: impl FnOnce() -> T) -> T {
struct Restore(bool);
impl Drop for Restore {
fn drop(&mut self) {
SINGLE_RETURNING.set(self.0);
}
}
let _restore = Restore(SINGLE_RETURNING.replace(true));
run()
}
pub(crate) fn single_returning() -> bool {
SINGLE_RETURNING.get()
}
pub(crate) fn retrieved_holder() {
HOLDER_RETRIEVALS.set(HOLDER_RETRIEVALS.get() + 1);
}
pub(crate) fn holder_retrievals() -> usize {
HOLDER_RETRIEVALS.get()
}
pub(crate) fn discovered() {
DISCOVERIES.set(DISCOVERIES.get() + 1);
}
pub(crate) fn discoveries() -> usize {
DISCOVERIES.get()
}
}
impl Index {
pub(crate) fn glob_visibilities(&mut self, meter: &Meter) -> Result<(), LoadError> {
let Some(&first) = self.glob_imports.first() else {
return Ok(());
};
if !self.globs.depth.is_empty() {
return Ok(());
}
let in_path_text =
|vis: &Vis| matches!(vis, Vis::Restricted(text) if text.starts_with("in "));
let bytes = vec_first::<usize>()
+ vec_first::<bool>()
+ self.modules.len() * (vec_slot::<usize>() + vec_slot::<bool>());
let decl = &self.uses[first];
meter.globs(bytes, &decl.file, Some(decl.line))?;
let mut in_path = vec![false; self.modules.len()];
for (module, record) in self.modules.iter().enumerate() {
in_path[module] = record
.defs
.iter()
.any(|id| in_path_text(&self.items[id.0].visibility));
}
for decl in &self.uses {
in_path[decl.module] |= in_path_text(&decl.vis);
}
let depth: Vec<usize> = (0..self.modules.len())
.map(|module| self.module_depth(module))
.collect();
self.globs.depth = depth;
self.globs.in_path = in_path;
Ok(())
}
pub(crate) fn clear_globs(&mut self) {
let depth = std::mem::take(&mut self.globs.depth);
let in_path = std::mem::take(&mut self.globs.in_path);
let drops = std::mem::take(&mut self.globs.drops);
let replaced_names = std::mem::take(&mut self.globs.replaced_names);
let dropped = self.globs.dropped;
self.globs = GlobTables {
depth,
in_path,
drops,
replaced_names,
dropped,
..GlobTables::default()
};
}
pub(crate) fn release_globs(&mut self, meter: &Meter) {
meter.release_globs(self.globs.charged);
self.clear_globs();
}
pub(crate) fn reset_globs(&mut self, meter: &Meter) -> Result<(), LoadError> {
self.release_globs(meter);
let Some(&first) = self.glob_imports.first() else {
return Ok(());
};
#[cfg(test)]
reference::built();
self.charge_tables(base_bytes(self.modules.len()), first, meter)?;
self.globs.exports = vec![Vec::new(); self.modules.len()];
self.globs.reads = vec![Vec::new(); self.modules.len()];
Ok(())
}
fn depth_of(&self, module: usize) -> usize {
self.globs
.depth
.get(module)
.copied()
.unwrap_or_else(|| self.module_depth(module))
}
fn width(&self, level: Level) -> usize {
match level.module() {
Some(module) => 1 + self.depth_of(module),
None if level.plain() == Level::PUBLIC => 0,
None => usize::MAX,
}
}
fn width_order(&self, left: Level, right: Level) -> std::cmp::Ordering {
let (left, right) = (left.plain(), right.plain());
if left == right {
std::cmp::Ordering::Equal
} else {
match (left, right) {
(Level::PUBLIC, _) | (_, Level::NOBODY) => std::cmp::Ordering::Less,
(_, Level::PUBLIC) | (Level::NOBODY, _) => std::cmp::Ordering::Greater,
_ => self.width(left).cmp(&self.width(right)),
}
}
}
pub(crate) fn level_covers(
&self,
offered: Level,
required: Level,
charge: &mut dyn FnMut(usize) -> Result<(), LoadError>,
) -> Result<bool, LoadError> {
let (offered, required) = (offered.plain(), required.plain());
if offered == Level::NOBODY || required == Level::NOBODY {
return Ok(false);
}
if offered == Level::PUBLIC || offered == required {
return Ok(true);
}
let (Some(offered), Some(mut required)) = (offered.module(), required.module()) else {
return Ok(false);
};
loop {
charge(1)?;
if offered == required {
return Ok(true);
}
match self.modules[required].parent {
Some(parent) => required = parent,
None => return Ok(false),
}
}
}
pub(crate) fn wider(&self, left: Level, right: Level) -> Level {
if self.width_order(right, left).is_lt() {
right
} else {
left
}
}
pub(crate) fn meet(&self, left: Level, right: Level) -> Level {
if self.width_order(right, left).is_gt() {
right
} else {
left
}
}
pub(crate) fn level_of(&self, vis: &Vis, home: usize, steps: Steps<'_>) -> Level {
self.read_level_of(vis, home, steps)
.expect("nonretained visibility levels reserve no import storage")
}
pub(crate) fn read_level_of(
&self,
vis: &Vis,
home: usize,
steps: Steps<'_>,
) -> Result<Level, Fail> {
Ok(match vis {
Vis::Public => Level::PUBLIC,
Vis::Inherited => Level::within(home),
Vis::Restricted(text) => match text.as_str() {
"crate" => Level::within(self.modules[home].root),
"self" => Level::within(home),
"super" => self.modules[home]
.parent
.map_or(Level::NOBODY, Level::within),
other => {
if let Some(written) = other.strip_prefix("in ") {
self.level_in(written, home, steps)?
} else {
Level::NOBODY
}
}
},
})
}
fn level_in(&self, written: &str, home: usize, steps: Steps<'_>) -> Result<Level, Fail> {
let segs = Self::visibility_path(written, steps)?;
let walked = match self.walk(home, &segs, false, Namespace::Type, Heads::Local, steps) {
Ok(walked) => walked,
Err(Fail::Storage(error)) => return Err(Fail::Storage(error)),
Err(_) => return Ok(Level::NOBODY),
};
Ok(walked
.modules
.iter()
.copied()
.chain(walked.items.keys().flat_map(|id| self.modules_for(*id)))
.filter(|ancestor| self.within(home, *ancestor))
.map(Level::within)
.reduce(|left, right| self.wider(left, right))
.unwrap_or(Level::NOBODY))
}
pub(crate) fn vis_at(&self, level: Level, home: usize) -> Vis {
let Some(module) = level.module() else {
return if level.plain() == Level::PUBLIC {
Vis::Public
} else {
Vis::Restricted("in ".to_owned())
};
};
let root = self.modules[home].root;
if module == home {
Vis::Inherited
} else if module == root {
Vis::Restricted("crate".to_owned())
} else {
let (path, base) = (&self.modules[module].path, &self.modules[root].path);
Vis::Restricted(format!("in crate{}", &path[base.len()..]))
}
}
fn allowed(&self, module: usize, class: &[bool], level: Level) -> bool {
match level.module() {
Some(within) => {
debug_assert!(self.within(module, within), "a level is an ancestor's");
class.get(self.depth_of(within)).copied().unwrap_or(false)
}
None => level.plain() == Level::PUBLIC,
}
}
fn class_for(&self, target: usize, importer: usize) -> Box<[bool]> {
let mut chain = vec![target];
while let Some(parent) = self.modules[*chain.last().expect("one module")].parent {
chain.push(parent);
}
chain
.iter()
.rev()
.map(|ancestor| self.within(importer, *ancestor))
.collect()
}
pub(crate) fn exports_by_path(&self, module: usize) -> bool {
self.globs.in_path.get(module).copied().unwrap_or(false)
}
fn reads_of(&self, module: usize) -> &[GlobRead] {
self.globs.reads.get(module).map_or(&[], Vec::as_slice)
}
fn exports_of(&self, module: usize) -> &[usize] {
self.globs.exports.get(module).map_or(&[], Vec::as_slice)
}
fn exact_mode() -> bool {
#[cfg(test)]
{
reference::is_exact()
}
#[cfg(not(test))]
{
false
}
}
fn flagged(&self, name: &str, at: usize) -> bool {
Self::exact_mode()
|| self.replaced(name, at)
|| (!self.globs.companions.is_empty()
&& self
.globs
.companions
.get(name)
.is_some_and(|spaces| spaces[at]))
}
fn replaced(&self, name: &str, at: usize) -> bool {
self.globs
.replaced_names
.get(name)
.is_some_and(|spaces| spaces[at])
}
fn covert_level(&self, module: usize, level: Level) -> bool {
!Self::exact_mode()
&& !self.exports_by_path(module)
&& !self.exports_of(module).is_empty()
&& self
.exports_of(module)
.iter()
.all(|view| !self.allowed(module, &self.globs.views[*view].class, level))
}
fn reads_holding(&self, module: usize, name: &str) -> Holders<'_> {
let reads = self.reads_of(module);
if Self::exact_mode() {
return Holders::All(reads.iter());
}
let Some(views) = self.globs.holding.get(name) else {
return Holders::All([].iter());
};
if views.len() >= reads.len() {
return Holders::All(reads.iter());
}
tally::add(Work::HolderScans, views.len());
let lists: Vec<&[usize]> = views
.iter()
.filter_map(|view| self.globs.views[*view].places.get(&module))
.map(Vec::as_slice)
.collect();
let left = lists.iter().map(|list| list.len()).sum();
Holders::Places {
reads,
lists: lists.into_iter(),
list: [].iter(),
left,
scanned: views.len(),
}
}
pub(crate) fn glob_reads(
&self,
module: usize,
) -> impl Iterator<Item = (usize, usize, usize)> + '_ {
self.reads_of(module).iter().map(|read| {
tally::add(Work::ViewReads, 1);
(read.glob, read.target, read.view)
})
}
pub(crate) fn view_holds(&self, view: usize, name: &str, at: usize, id: ItemId) -> bool {
tally::add(Work::ViewReads, 1);
self.held_level(view, name, at, id).is_some()
}
fn held_level(&self, view: usize, name: &str, at: usize, id: ItemId) -> Option<Level> {
let held = &self.globs.views[view].names.get(name)?[at];
held.binary_search_by_key(&id, |entry| entry.0)
.ok()
.map(|place| held[place].1)
}
fn routed_level(
&self,
view: usize,
name: &str,
at: usize,
id: ItemId,
rows: &mut Option<&mut QueryRows<'_, '_, '_>>,
charge: &mut dyn FnMut(usize) -> Result<(), LoadError>,
) -> Result<Option<Level>, LoadError> {
match rows {
Some(rows) => rows.level(view, name, at, id, charge),
None => Ok(self.held_level(view, name, at, id)),
}
}
fn promoted_companion(
&self,
place: &Place,
id: ItemId,
required: Level,
charge: &mut dyn FnMut(usize) -> Result<(), LoadError>,
rows: &mut Option<&mut QueryRows<'_, '_, '_>>,
) -> Result<bool, LoadError> {
for view in self.exports_of(place.0) {
charge(1)?;
if let Some(level) = self.routed_level(*view, &place.1, place.2, id, rows, charge)?
&& level.is_companion()
&& self.level_covers(level, required, charge)?
{
return Ok(true);
}
}
Ok(false)
}
pub(crate) fn view_names(&self, view: usize) -> impl Iterator<Item = &str> + '_ {
self.globs.views[view].names.keys().map(|name| {
tally::add(Work::ViewReads, 1);
name.as_str()
})
}
pub(crate) fn globbed(&self, module: usize, name: &str, at: usize, steps: Steps<'_>) -> Bound {
self.read_globbed(module, name, at, steps)
.expect("nonretained glob lookups reserve no import storage")
}
pub(crate) fn read_globbed(
&self,
module: usize,
name: &str,
at: usize,
steps: Steps<'_>,
) -> Result<Bound, Fail> {
let reads = self.reads_holding(module, name);
self.count_lookups(steps, module, reads.scanned(), reads.len());
if !self.flagged(name, at) {
return self.globbed_plain(module, reads, name, at, steps);
}
let mut bound = Bound::new();
for (read, held) in self.delivered(module, reads, name, at, None, Work::LookupReads) {
let decl = &self.uses[read.glob];
let own = self.read_level_of(&decl.vis, module, steps)?;
for (id, level) in held.iter() {
steps.storage_work(1 + bound.len()).map_err(Fail::Storage)?;
tally::add(Work::LookupRoutes, 1);
let met = self.meet(own, *level);
let vis = if met == own {
decl.vis.clone()
} else {
self.vis_at(met, module)
};
let mut origin = Self::glob_origin(decl, vis, read.target, at, name);
origin.companion = level.is_companion();
bound.offer_work(*id, &origin, steps)?;
bound.offer(*id, origin);
}
}
Ok(bound)
}
pub(crate) fn unnamed_glob_source(
&self,
module: usize,
name: &str,
at: usize,
id: ItemId,
viewer: usize,
steps: Steps<'_>,
) -> Result<bool, Fail> {
let mut found = false;
self.delivered_item_sources(
module,
name,
at,
id,
Some(viewer),
steps,
&mut |target, _| {
if self.scopes[target]
.get(name)
.is_none_or(|entry| entry.defs[at].is_empty())
{
found = true;
}
Ok(())
},
)?;
Ok(found)
}
#[expect(
clippy::too_many_arguments,
reason = "one selected binding and its reader identify the delivered routes"
)]
pub(crate) fn delivered_item_sources(
&self,
module: usize,
name: &str,
at: usize,
id: ItemId,
viewer: Option<usize>,
steps: Steps<'_>,
visit: &mut dyn FnMut(usize, usize) -> Result<(), LoadError>,
) -> Result<(), Fail> {
let memory = steps.temporary();
let steps = memory.as_ref().map_or(steps, |memory| steps.at(memory));
self.reserve_glob_lookup(module, name, at, steps)?;
let reads = self.reads_holding(module, name);
self.count_lookups(steps, module, reads.scanned(), reads.len());
for (read, held) in self.delivered(module, reads, name, at, None, Work::LookupReads) {
steps.storage_work(1 + held.len()).map_err(Fail::Storage)?;
let Ok(found) = held.binary_search_by_key(&id, |entry| entry.0) else {
continue;
};
let own = self.read_level_of(&self.uses[read.glob].vis, module, steps)?;
if let Some(viewer) = viewer
&& !self
.level_covers(
self.meet(own, held[found].1),
Level::within(viewer),
&mut |units| steps.storage_work(units),
)
.map_err(Fail::Storage)?
{
continue;
}
visit(read.target, read.glob).map_err(Fail::Storage)?;
}
Ok(())
}
pub(crate) fn bound_name(&self, module: usize, name: &str) -> Option<&str> {
self.scopes[module]
.get_key_value(name)
.map(|(key, _)| key.as_str())
.or_else(|| self.globs.strings.get(name).map(AsRef::as_ref))
}
fn admitted_holders(
&self,
module: usize,
name: &str,
steps: Steps<'_>,
) -> Result<Holders<'_>, Fail> {
if let Some(views) = self.globs.holding.get(name)
&& views.len() < self.reads_of(module).len()
{
steps.storage_work(views.len()).map_err(Fail::Storage)?;
steps
.reserve(vec_first::<&[usize]>() + views.len() * vec_slot::<&[usize]>())
.map_err(Fail::Storage)?;
}
Ok(self.reads_holding(module, name))
}
pub(crate) fn reserve_glob_lookup(
&self,
module: usize,
name: &str,
at: usize,
steps: Steps<'_>,
) -> Result<(), Fail> {
let reads = self.admitted_holders(module, name, steps)?;
steps.storage_work(reads.len()).map_err(Fail::Storage)?;
let mut bytes = vec_first::<Routes<'_>>()
+ 2 * vec_first::<(ItemId, Origin)>()
+ vec_first::<(&GlobRead, Cow<'_, [Held]>)>();
for read in reads {
let Some(lists) = self.globs.views[read.view].names.get(name) else {
continue;
};
let held = &lists[at];
if held.is_empty() {
continue;
}
steps.storage_work(held.len()).map_err(Fail::Storage)?;
let written = match &self.uses[read.glob].vis {
Vis::Restricted(text) => text.len(),
_ => 0,
};
let text = written.max(9 + self.modules[module].path.len());
let route = vec_slot::<Routes<'_>>()
+ vec_first::<RouteVis<'_>>()
+ vec_slot::<RouteVis<'_>>()
+ 3 * (vec_first::<Vis>() + vec_slot::<Vis>() + text)
+ 2 * (vec_slot::<(ItemId, Origin)>() + 2 * name.len() + text);
bytes += held.len() * route + vec_slot::<(&GlobRead, Cow<'_, [Held]>)>();
if !self.replacements(read, name, at).is_empty() {
bytes += vec_first::<Held>() + held.len() * vec_slot::<Held>();
}
}
steps.reserve(bytes).map_err(Fail::Storage)
}
fn globbed_plain(
&self,
module: usize,
reads: Holders<'_>,
name: &str,
at: usize,
steps: Steps<'_>,
) -> Result<Bound, Fail> {
let mut items: Vec<Routes<'_>> = Vec::new();
for read in reads {
tally::add(Work::LookupReads, 1);
let Some(held) = self.globs.views[read.view]
.names
.get(name)
.map(|lists| &lists[at])
.filter(|held| !held.is_empty())
else {
continue;
};
let decl = &self.uses[read.glob];
let own = self.read_level_of(&decl.vis, module, steps)?;
for (id, level) in held {
steps.storage_work(1 + items.len()).map_err(Fail::Storage)?;
let met = self.meet(own, *level);
let vis = if met == own {
RouteVis::Written(&decl.vis)
} else {
RouteVis::At(met)
};
let public = match vis {
RouteVis::Written(written) => *written == Vis::Public,
RouteVis::At(level) => level.plain() == Level::PUBLIC,
};
match items.binary_search_by_key(id, |routes| routes.id) {
Err(place) => items.insert(
place,
Routes {
id: *id,
target: read.target,
glob: read.glob,
kept: vis,
public,
first: vis,
others: Vec::new(),
},
),
Ok(place) => {
let routes = &mut items[place];
steps
.storage_work(routes.others.len())
.map_err(Fail::Storage)?;
if read.target < routes.target {
routes.target = read.target;
routes.glob = read.glob;
routes.kept = vis;
}
routes.public |= public;
if !vis.same(routes.first)
&& !routes.others.iter().any(|other| vis.same(*other))
{
routes.others.push(vis);
}
}
}
}
}
let mut bound = Bound::new();
for routes in items {
tally::add(Work::LookupRoutes, 1);
let vis_of = |vis: RouteVis<'_>| match vis {
RouteVis::Written(written) => written.clone(),
RouteVis::At(level) => self.vis_at(level, module),
};
let kept = vis_of(routes.kept);
let decl = &self.uses[routes.glob];
let mut origin = Self::glob_origin(decl, kept, routes.target, at, name);
if routes.public {
origin.vis = Vis::Public;
} else {
let mut also: Vec<Vis> = Vec::new();
for vis in std::iter::once(routes.first).chain(routes.others) {
steps.storage_work(1 + also.len()).map_err(Fail::Storage)?;
let vis = vis_of(vis);
if vis != origin.vis && !also.contains(&vis) {
also.push(vis);
}
}
if !also.is_empty() {
steps
.storage_work(also.len().saturating_mul(also.len().ilog2() as usize + 1))
.map_err(Fail::Storage)?;
also.sort_by(|left, right| vis_key(left).cmp(&vis_key(right)));
origin.also = Some(also.into_boxed_slice());
}
}
bound.offer_work(routes.id, &origin, steps)?;
bound.offer(routes.id, origin);
}
Ok(bound)
}
fn delivered<'a>(
&'a self,
module: usize,
reads: Holders<'a>,
name: &str,
at: usize,
class: Option<&[bool]>,
visits: Work,
) -> Vec<(&'a GlobRead, Cow<'a, [Held]>)> {
let mut found = self.read_lists(reads, name, at, visits, None);
for (read, held) in &mut found {
self.filter_delivered((module, name, at), read, class, held, Work::ListCopies);
}
found
}
fn filter_delivered(
&self,
(module, name, at): (usize, &str, usize),
read: &GlobRead,
class: Option<&[bool]>,
held: &mut Cow<'_, [Held]>,
copies: Work,
) {
let replacements = self.replacements(read, name, at);
self.filter_known_delivered(module, class, replacements, held, copies);
}
fn filter_known_delivered(
&self,
module: usize,
class: Option<&[bool]>,
replacements: &[Held],
held: &mut Cow<'_, [Held]>,
copies: Work,
) {
let selected = |id| {
replacements
.binary_search_by_key(&id, |entry| entry.0)
.ok()
.map(|place| replacements[place].1)
.filter(|level| class.is_none_or(|class| self.allowed(module, class, *level)))
};
if replacements
.iter()
.any(|entry| class.is_none_or(|class| self.allowed(module, class, entry.1)))
{
if held.iter().all(|entry| {
selected(entry.0).is_some_and(|support| {
!entry.1.is_companion() && self.meet(entry.1, support) == entry.1
})
}) {
return;
}
if matches!(held, Cow::Borrowed(_)) {
tally::add(copies, 1);
}
let held = held.to_mut();
held.retain(|entry| selected(entry.0).is_some());
for entry in held {
entry.1 = self.meet(
entry.1.plain(),
selected(entry.0).expect("retained support"),
);
}
}
}
fn known_delivered<'a>(
&'a self,
module: usize,
class: &'a [bool],
replacements: &'a [Held],
held: &'a [Held],
) -> impl Iterator<Item = Held> + 'a {
let active = replacements
.iter()
.any(|entry| self.allowed(module, class, entry.1));
let mut position = 0;
held.iter().copied().filter_map(move |entry| {
if !active {
return Some(entry);
}
while position < replacements.len() && replacements[position].0 < entry.0 {
position += 1;
}
let &(id, support) = replacements.get(position)?;
(id == entry.0 && self.allowed(module, class, support))
.then(|| (entry.0, self.meet(entry.1.plain(), support)))
})
}
fn read_lists<'a>(
&'a self,
reads: Holders<'a>,
name: &str,
at: usize,
visits: Work,
rows: Option<&mut QueryRows<'_, 'a, '_>>,
) -> Vec<(&'a GlobRead, Cow<'a, [Held]>)> {
let mut found = Vec::new();
let mut previous = None;
let mut rows = rows.filter(|rows| rows.matches(name));
for read in reads {
tally::add(visits, 1);
let lists = match previous {
Some((view, lists)) if view == read.view => lists,
_ => {
let lists = match &mut rows {
Some(rows) => rows.raw_row(read.view),
None => self.globs.views[read.view].names.get(name).map(Box::as_ref),
};
previous = Some((read.view, lists));
lists
}
};
let Some(lists) = lists else {
continue;
};
if !lists[at].is_empty() {
found.push((read, Cow::Borrowed(lists[at].as_slice())));
}
}
found
}
fn redelivered<'a>(
&'a self,
(module, name, at): (usize, &str, usize),
found: &[(&GlobRead, Cow<'_, [Held]>)],
memory: &Transient<'_>,
routed: &mut Routing<'_, '_, '_>,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
) -> Result<Redelivery<'a>, LoadError> {
let decl = &self.uses[self.glob_imports[0]];
charge(found.len())?;
memory.charge(redelivery_bytes(found), &decl.file, Some(decl.line))?;
let mut answer = Redelivery::new(self, found, name, at, memory, charge)?;
let mut supporters: BTreeMap<ItemId, Vec<(Level, usize)>> = BTreeMap::new();
let mut carriers: BTreeMap<ItemId, Vec<usize>> = BTreeMap::new();
for (this, (read, held)) in found.iter().enumerate() {
charge(1 + held.len())?;
let glob = {
let visibility_memory = memory.child();
self.read_level_of(
&self.uses[read.glob].vis,
module,
Steps::LoadAt {
memory: &visibility_memory,
file: &decl.file,
line: decl.line,
},
)
.map_err(crate::settle::storage_failure)?
};
for (id, level) in held.iter() {
charge(search_units(carriers.len()) + search_units(supporters.len()))?;
carriers.entry(*id).or_default().push(this);
if !level.is_companion() {
supporters
.entry(*id)
.or_default()
.push((self.meet(glob, *level), this));
}
}
}
for list in supporters.values_mut() {
charge(sort_units(list.len()))?;
list.sort_by(|(left, left_other), (right, right_other)| {
self.width_order(*left, *right)
.then_with(|| left_other.cmp(right_other))
});
}
let groups_memory = memory.child();
let groups = self.selection_groups(found, &answer, &supporters, &groups_memory, charge)?;
if groups.table.is_empty() {
return Ok(answer);
}
let excluded_memory = memory.child();
let mut excluded = Vec::new();
let mut admission = NativeAdmission::new(Steps::LoadAt {
memory: &excluded_memory,
file: &decl.file,
line: decl.line,
});
purrdf_lex::allocation::Memory::new(&mut admission)
.reserve(&mut excluded, found.len())
.map_err(|error| admission.graph_error(error.into()))?;
charge(found.len())?;
excluded.resize(found.len(), 0usize);
for (group, ((id, competitors), members)) in groups.table.ordered().enumerate() {
let id = *id;
let generation = group + 1;
for competing in competitors {
charge(search_units(carriers.len()))?;
if let Some(carriers) = carriers.get(competing) {
charge(1 + carriers.len())?;
for &carrier in carriers {
excluded[carrier] = generation;
}
}
}
let best = Self::independent_supporters(
found,
supporters.get(&id).map_or(&[][..], Vec::as_slice),
(&excluded, generation),
id,
routed,
charge,
)?;
if self.confirm_returning_batch(
found,
members,
id,
best,
module,
routed,
&mut answer.selected,
charge,
)? {
continue;
}
for &(this, position) in members {
charge(1)?;
let selected = Self::carrier_support(best, found[this].0.view);
if let Some(level) = selected
&& self.confirms_carrier(&found[this], id, level, routed, charge)?
{
answer.selected[position] = Some(level);
}
}
}
Ok(answer)
}
fn selection_groups(
&self,
found: &[(&GlobRead, Cow<'_, [Held]>)],
answer: &Redelivery<'_>,
supporters: &BTreeMap<ItemId, Vec<(Level, usize)>>,
memory: &Transient<'_>,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
) -> Result<SelectionGroups, LoadError> {
let decl = &self.uses[self.glob_imports[0]];
let mut groups = SelectionGroups::default();
for (this, (_, held)) in found.iter().enumerate() {
charge(1 + held.len())?;
if !held.iter().any(|entry| entry.1.is_companion()) {
continue;
}
for (position, (id, _)) in held.iter().enumerate() {
if Self::maximal_replacement(answer.reads[this].known, *id, charge)? {
continue;
}
if !self.possibly_supported(held, *id, supporters, charge)? {
continue;
}
groups.add(
*id,
held,
(this, answer.reads[this].offset + position),
memory,
decl,
charge,
)?;
}
}
Ok(groups)
}
#[expect(
clippy::too_many_arguments,
reason = "the existing group and its borrowed selection destination"
)]
fn confirm_returning_batch(
&self,
found: &[(&GlobRead, Cow<'_, [Held]>)],
members: &[(usize, usize)],
id: ItemId,
best: [Option<(Level, usize)>; 2],
module: usize,
routed: &mut Routing<'_, '_, '_>,
selected: &mut [Option<Level>],
charge: &dyn Fn(usize) -> Result<(), LoadError>,
) -> Result<bool, LoadError> {
let Some(required) =
self.uniform_returning_level(found, members, id, best, module, charge)?
else {
return Ok(false);
};
routed.returning(id, required, |proof| {
for &(this, position) in members {
charge(1)?;
let Some(level) = Self::carrier_support(best, found[this].0.view) else {
continue;
};
let Some(actual) = self.carrier_requirement(&found[this], id, level, charge)?
else {
continue;
};
if actual != required || found[this].0.target == module {
continue;
}
if proof.returns(found[this].0.target, charge)? {
selected[position] = Some(level);
}
}
Ok(())
})?;
Ok(true)
}
fn carrier_support(best: [Option<(Level, usize)>; 2], view: usize) -> Option<Level> {
match best {
[Some((level, other)), _] if other != view => Some(level),
[_, Some((level, _))] => Some(level),
_ => None,
}
}
fn carrier_requirement(
&self,
(_, held): &(&GlobRead, Cow<'_, [Held]>),
id: ItemId,
level: Level,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
) -> Result<Option<Level>, LoadError> {
if !self.preserves_firm_competitors(held, id, level, charge)? {
return Ok(None);
}
charge(held.len())?;
let carrier = held
.iter()
.find_map(|(candidate, level)| (*candidate == id).then_some(level.plain()))
.expect("a carrier holds its selected identity");
Ok(Some(self.meet(level.plain(), carrier).plain()))
}
fn uniform_returning_level(
&self,
found: &[(&GlobRead, Cow<'_, [Held]>)],
members: &[(usize, usize)],
id: ItemId,
best: [Option<(Level, usize)>; 2],
reader: usize,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
) -> Result<Option<Level>, LoadError> {
#[cfg(test)]
if reference::single_returning() {
return Ok(None);
}
let mut uniform = None;
for &(this, _) in members {
charge(1)?;
let Some(level) = Self::carrier_support(best, found[this].0.view) else {
continue;
};
let Some(required) = self.carrier_requirement(&found[this], id, level, charge)? else {
continue;
};
if found[this].0.target == reader || required == Level::NOBODY {
continue;
}
if uniform.is_some_and(|previous| previous != required) {
return Ok(None);
}
uniform = Some(required);
}
Ok(uniform)
}
fn independent_supporters(
found: &[(&GlobRead, Cow<'_, [Held]>)],
supporters: &[(Level, usize)],
(excluded, generation): (&[usize], usize),
id: ItemId,
routed: &mut Routing<'_, '_, '_>,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
) -> Result<[Option<(Level, usize)>; 2], LoadError> {
let mut best = [None, None];
for &(level, other) in supporters {
charge(1)?;
if level.plain() == Level::NOBODY
|| excluded[other] == generation
|| !routed.ask(found[other].0.target, id, level.plain(), false)
{
continue;
}
let view = found[other].0.view;
match best {
[None, _] => best[0] = Some((level, view)),
[Some((_, first)), None] if first != view => {
best[1] = Some((level, view));
break;
}
_ => {}
}
}
Ok(best)
}
fn maximal_replacement(
known: &[Held],
id: ItemId,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
) -> Result<bool, LoadError> {
charge(search_units(known.len()))?;
Ok(replacement_level(known, id).is_some_and(|level| level.plain() == Level::PUBLIC))
}
fn possibly_supported(
&self,
held: &[Held],
id: ItemId,
supporters: &BTreeMap<ItemId, Vec<(Level, usize)>>,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
) -> Result<bool, LoadError> {
charge(search_units(supporters.len()))?;
let Some(&(ceiling, _)) = supporters.get(&id).and_then(|list| list.first()) else {
return Ok(false);
};
self.preserves_firm_competitors(held, id, ceiling, charge)
}
fn preserves_firm_competitors(
&self,
held: &[Held],
id: ItemId,
level: Level,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
) -> Result<bool, LoadError> {
charge(held.len())?;
Ok(!held.iter().any(|(other, original)| {
*other != id && !original.is_companion() && self.width_order(*original, level).is_lt()
}))
}
fn confirms_carrier(
&self,
found: &(&GlobRead, Cow<'_, [Held]>),
id: ItemId,
level: Level,
routed: &mut Routing<'_, '_, '_>,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
) -> Result<bool, LoadError> {
let Some(required) = self.carrier_requirement(found, id, level, charge)? else {
return Ok(false);
};
Ok(routed.ask(found.0.target, id, required, true))
}
fn binds_itself(&self, module: usize, name: &str, at: usize) -> bool {
self.scopes[module]
.get(name)
.is_some_and(|entry| !entry.defs[at].is_empty())
}
fn replacements(&self, read: &GlobRead, name: &str, at: usize) -> &[Held] {
self.globs
.drops
.get(&(read.glob, read.target))
.and_then(|names| names.get(name))
.map_or(&[], |spaces| spaces[at].as_slice())
}
pub(crate) fn drop_count(&self) -> usize {
self.globs.dropped
}
pub(crate) fn record_drops(&mut self, meter: &Meter) -> Result<usize, LoadError> {
let Some(&first) = self.glob_imports.first() else {
return Ok(0);
};
let decl = &self.uses[first];
let (file, line) = (decl.file.clone(), decl.line);
let memory = Transient::new(meter);
let steps = Steps::LoadAt {
memory: &memory,
file: &file,
line,
};
let companions = self.companion_names(&memory, meter, first)?;
let mut supply: Option<Supply<'_>> = None;
let mut row_scratch = None;
let mut due: Vec<Replacement> = Vec::new();
for module in 0..self.globs.reads.len() {
let reads = self.reads_of(module);
if reads.len() < 2 {
continue;
}
meter.work(reads.len(), &file, Some(line))?;
let names_memory = memory.child();
let names = self.companion_queries(reads, &companions, &names_memory, meter, first)?;
for (name, at) in names {
let query_memory = Transient::new(meter);
let query_steps = Steps::LoadAt {
memory: &query_memory,
file: &file,
line,
};
let holders = self
.admitted_holders(module, name, query_steps)
.map_err(crate::settle::storage_failure)?;
meter.work(holders.len(), &file, Some(line))?;
query_steps.reserve(
vec_first::<(&GlobRead, Cow<'_, [Held]>)>()
+ holders.len() * vec_slot::<(&GlobRead, Cow<'_, [Held]>)>(),
)?;
let charge = |steps: usize| meter.work(steps, &file, Some(line));
let mut rows =
QueryRows::new(self, name, &mut row_scratch, &memory, decl, &charge)?;
charge(holders.len().saturating_mul(2).saturating_add(1))?;
let found = self.read_lists(holders, name, *at, Work::DropReads, Some(&mut rows));
if supply.is_none() {
supply = Some(self.supply(meter, first)?);
}
let supply = supply.as_mut().expect("the supply graph was constructed");
let redelivered = self.redelivered(
(module, name, *at),
&found,
&query_memory,
&mut Routing {
index: self,
supply,
reader: module,
name,
at: *at,
charge: &charge,
rows,
},
&|units| self.candidate_steps(units, first, meter),
)?;
if let Some(refused) = supply.refused.take() {
return Err(refused);
}
meter.work(found.len() + redelivered.selected.len(), &file, Some(line))?;
for ((read, held), selected) in found.iter().zip(&redelivered.reads) {
for (position, (id, _)) in held.iter().enumerate() {
let Some(level) = redelivered.selected[selected.offset + position] else {
continue;
};
meter.work(search_units(selected.known.len()), &file, Some(line))?;
let known = replacement_level(selected.known, *id);
if known.is_none_or(|known| self.width_order(level, known).is_lt()) {
reserve_next(&mut due, steps)?;
due.push((read.glob, read.target, name.clone(), *at, *id, level));
}
}
}
}
}
drop((supply, companions, row_scratch));
self.record_replacements(due, meter, first)
}
fn record_replacements(
&mut self,
due: Vec<Replacement>,
meter: &Meter,
first: usize,
) -> Result<usize, LoadError> {
let recorded = due.len();
for replacement in due {
self.record_replacement(replacement, meter, first)?;
}
#[cfg(test)]
reference::discovered();
Ok(recorded)
}
fn companion_queries<'a>(
&self,
reads: &[GlobRead],
companions: &'a [Vec<(SharedStr, usize)>],
names_memory: &Transient<'_>,
meter: &Meter,
first: usize,
) -> Result<Vec<&'a (SharedStr, usize)>, LoadError> {
let decl = &self.uses[first];
let (file, line) = (&decl.file, decl.line);
let entries = reads
.iter()
.map(|read| companions[read.view].len())
.sum::<usize>();
names_memory.charge(
hash_map::<(*const u8, usize)>()
+ vec_first::<&(SharedStr, usize)>()
+ entries
* (hash_entry::<(*const u8, usize)>() + vec_slot::<&(SharedStr, usize)>()),
file,
Some(line),
)?;
meter.work(entries, file, Some(line))?;
let mut seen = HashSet::with_hasher(FixedState::new());
let names: Vec<_> = reads
.iter()
.flat_map(|read| &companions[read.view])
.filter(|name| seen.insert((name.0.as_ptr(), name.1)))
.collect();
Ok(names)
}
fn companion_names(
&self,
memory: &Transient<'_>,
meter: &Meter,
first: usize,
) -> Result<Vec<Vec<(SharedStr, usize)>>, LoadError> {
let decl = &self.uses[first];
meter.work(self.globs.views.len(), &decl.file, Some(decl.line))?;
let names = self
.globs
.views
.iter()
.map(|view| view.names.len())
.sum::<usize>();
meter.work(names.saturating_mul(3), &decl.file, Some(decl.line))?;
let candidates = self
.globs
.views
.iter()
.flat_map(|view| view.names.values())
.flat_map(|lists| lists.iter())
.map(Vec::len)
.sum::<usize>();
meter.work(
candidates + names.saturating_mul(3),
&decl.file,
Some(decl.line),
)?;
memory.charge(
vec_first::<Vec<(SharedStr, usize)>>()
+ self.globs.views.len()
* (vec_slot::<Vec<(SharedStr, usize)>>() + vec_first::<(SharedStr, usize)>())
+ names.saturating_mul(3 * vec_slot::<(SharedStr, usize)>()),
&decl.file,
Some(decl.line),
)?;
Ok(self
.globs
.views
.iter()
.map(|view| {
view.names
.iter()
.flat_map(|(name, lists)| {
(0..3)
.filter(|at| lists[*at].iter().any(|entry| entry.1.is_companion()))
.map(|at| (name.clone(), at))
})
.collect()
})
.collect())
}
fn record_replacement(
&mut self,
(glob, target, name, at, id, level): Replacement,
meter: &Meter,
first: usize,
) -> Result<(), LoadError> {
let decl = &self.uses[first];
let mut bytes = 0;
if self.globs.replaced_names.is_empty() {
bytes += hash_map::<(SharedStr, [bool; 3])>();
}
let recorded = self.globs.replaced_names.get(name.as_str());
if recorded.is_none() {
bytes += hash_entry::<(SharedStr, [bool; 3])>();
}
let publish_name = recorded.is_none_or(|spaces| !spaces[at]);
if self.globs.drops.is_empty() {
bytes += btree_map::<(usize, usize), DropNames>();
}
let placement = self.globs.drops.entry((glob, target));
let names = match &placement {
std::collections::btree_map::Entry::Occupied(entry) => Some(entry.get()),
std::collections::btree_map::Entry::Vacant(_) => None,
};
if names.is_none() {
bytes += btree_entry::<(usize, usize), DropNames>()
+ hash_map::<(SharedStr, [Vec<Held>; 3])>();
}
let spaces = names.and_then(|names| names.get(name.as_str()));
if spaces.is_none() {
bytes += hash_entry::<(SharedStr, [Vec<Held>; 3])>() + shared_text(name.len());
}
let known = spaces.map(|spaces| &spaces[at]);
meter.work(
known.map_or(1, |entries| 1 + entries.len()),
&decl.file,
Some(decl.line),
)?;
let position = known.map_or(Err(0), |entries| {
entries.binary_search_by_key(&id, |entry| entry.0)
});
if position.is_err() {
bytes += vec_slot::<Held>()
+ if known.is_none_or(Vec::is_empty) {
vec_first::<Held>()
} else {
0
};
}
meter.items(bytes, &decl.file, Some(decl.line))?;
if publish_name {
self.globs.replaced_names.entry(name.clone()).or_default()[at] = true;
}
let entries = &mut placement.or_default().entry(name).or_default()[at];
match position {
Ok(place) => entries[place].1 = level,
Err(place) => {
entries.reserve_exact(1);
entries.insert(place, (id, level));
}
}
self.globs.dropped += 1;
Ok(())
}
fn definition_supply(
&self,
meter: &Meter,
first: usize,
steps: Steps<'_>,
) -> Result<BTreeMap<ItemId, Vec<SupplyRoute>>, LoadError> {
steps.reserve(btree_map::<ItemId, Vec<SupplyRoute>>())?;
let mut roots: BTreeMap<ItemId, Vec<SupplyRoute>> = BTreeMap::new();
for (module, record) in self.modules.iter().enumerate() {
for id in &record.defs {
let item = &self.items[id.0];
steps.reserve(shared_text(item.name.len()))?;
let name = SharedStr::from(item.name.as_str());
let vis = if item.kind == crate::item::SymbolKind::MacroRules {
&Vis::Public
} else {
&item.visibility
};
let visibility_memory = steps.temporary();
let visibility_steps = visibility_memory.as_ref().map_or(steps, |m| steps.at(m));
let level = self
.read_level_of(vis, module, visibility_steps)
.map_err(crate::settle::storage_failure)?;
drop(visibility_memory);
for (at, ns) in Namespace::ALL.into_iter().enumerate() {
self.candidate_steps(1, first, meter)?;
if !item.in_namespace(ns) {
continue;
}
if !roots.contains_key(id) {
steps.reserve(btree_entry::<ItemId, Vec<SupplyRoute>>())?;
}
let into = roots.entry(*id).or_default();
reserve_next(into, steps)?;
into.push(((module, name.clone(), at), level));
}
}
}
Ok(roots)
}
pub(crate) fn grounded_cycle_imports(
&self,
imports: &BTreeMap<usize, Vec<usize>>,
meter: &Meter,
proof_steps: Steps<'_>,
) -> Result<Option<Vec<crate::settle::FinalFallback>>, LoadError> {
let mut supply = None;
let mut certified = Vec::new();
for (&position, spaces) in imports {
let decl = &self.uses[position];
meter.work(1, &decl.file, Some(decl.line))?;
tally::add(Work::SupplySteps, 1);
if self.use_bound[position].iter().any(|bound| *bound) {
continue;
}
let Some(&first) = self.glob_imports.first() else {
return Ok(None);
};
let memory = Transient::new(meter);
let steps = Steps::LoadAt {
memory: &memory,
file: &decl.file,
line: decl.line,
};
let answers = self.fallback_supply(position, spaces, steps)?;
self.drain_lookups(meter, &decl.file, Some(decl.line))?;
if answers.is_empty() {
return Ok(None);
}
if supply.is_none() {
supply = Some(self.supply(meter, first)?);
}
let supply = supply.as_mut().expect("the supply graph was constructed");
let crate::index::UseKind::Named { name, .. } = &decl.kind else {
unreachable!("only named imports belong to a namespace cycle");
};
supply
.memory
.charge(shared_text(name.len()), &decl.file, Some(decl.line))?;
let name = SharedStr::from(name.as_str());
let charge = |units| meter.work(units, &decl.file, Some(decl.line));
let mut grounded = None;
for answer in answers {
let at = crate::settle::slot(answer.ns);
let holding = self.retained_holding(
supply,
&charge,
&(answer.id, name.clone(), at, answer.level, false),
None,
)?;
if !holding.holds(decl.module) {
continue;
}
if let Some(source) = answer.source {
supply.memory.charge(
shared_text(source.name.len()),
&decl.file,
Some(decl.line),
)?;
let source_name = SharedStr::from(source.name.as_str());
let holding = self.retained_holding(
supply,
&charge,
&(
answer.id,
source_name,
crate::settle::slot(source.ns),
answer.level,
false,
),
None,
)?;
if !holding.holds(source.module) {
continue;
}
}
grounded = Some(crate::settle::FinalFallback {
position,
at,
id: answer.id,
});
break;
}
let Some(answer) = grounded else {
return Ok(None);
};
reserve_next(&mut certified, proof_steps)?;
certified.push(answer);
}
Ok(Some(certified))
}
pub(crate) fn grounded_shadow_cuts(
&self,
cuts: &[crate::settle::ShadowCut],
meter: &Meter,
) -> Result<bool, LoadError> {
if cuts.is_empty() {
return Ok(false);
}
let Some(&first) = self.glob_imports.first() else {
return Ok(false);
};
let mut supply = self.supply(meter, first)?;
for cut in cuts {
let decl = &self.uses[first];
supply.memory.charge(
shared_text(cut.source.name.len()),
&decl.file,
Some(decl.line),
)?;
let name = SharedStr::from(cut.source.name.as_str());
let charge = |units| meter.work(units, &decl.file, Some(decl.line));
let holding = self.retained_holding(
&mut supply,
&charge,
&(
cut.id,
name,
crate::settle::slot(cut.source.ns),
Level::within(cut.source.module),
false,
),
None,
)?;
if !holding.holds(cut.source.module) {
return Ok(false);
}
}
Ok(true)
}
fn supply<'m>(&self, meter: &'m Meter, first: usize) -> Result<Supply<'m>, LoadError> {
let memory = Transient::new(meter);
let decl = &self.uses[first];
let charge = |bytes| memory.charge(bytes, &decl.file, Some(decl.line));
charge(
vec_first::<Vec<(usize, usize, Level)>>()
+ self.modules.len()
* (vec_slot::<Vec<(usize, usize, Level)>>()
+ vec_first::<(usize, usize, Level)>())
+ btree_map::<(ItemId, Place), Vec<SupplyRoute>>()
+ btree_map::<HoldingKey, Holding>(),
)?;
let mut readers: Vec<Vec<(usize, usize, Level)>> = vec![Vec::new(); self.modules.len()];
self.candidate_steps(self.globs.reads.len(), first, meter)?;
let cut_reader = cut::reader(&self.globs.reads);
for (module, reads) in self.globs.reads.iter().enumerate() {
for (place, read) in reads.iter().enumerate() {
self.candidate_steps(1, first, meter)?;
let visibility_memory = memory.child();
let level = self
.read_level_of(
&self.uses[read.glob].vis,
module,
Steps::LoadAt {
memory: &visibility_memory,
file: &decl.file,
line: decl.line,
},
)
.map_err(crate::settle::storage_failure)?;
drop(visibility_memory);
let into = &mut readers[read.target];
reserve_next(
into,
Steps::LoadAt {
memory: &memory,
file: &decl.file,
line: decl.line,
},
)?;
into.push((module, place, level));
}
}
let steps = Steps::LoadAt {
memory: &memory,
file: &decl.file,
line: decl.line,
};
let mut roots = self.definition_supply(meter, first, steps)?;
let mut named: BTreeMap<(ItemId, Place), Vec<SupplyRoute>> = BTreeMap::new();
for (position, import) in self.uses.iter().enumerate() {
self.candidate_steps(1, first, meter)?;
let crate::index::UseKind::Named { name, .. } = &import.kind else {
continue;
};
let route_memory = memory.child();
let routes = self.import_supply(position, steps.at(&route_memory))?;
self.drain_lookups(meter, &decl.file, Some(decl.line))?;
if routes.is_empty() {
continue;
}
charge(shared_text(name.len()))?;
let name = SharedStr::from(name.as_str());
for route in routes {
let destination = (import.module, name.clone(), crate::settle::slot(route.ns));
if let Some(source) = route.source {
charge(shared_text(source.name.len()))?;
let source = (
source.module,
SharedStr::from(source.name.as_str()),
crate::settle::slot(source.ns),
);
let key = (route.id, source);
if !named.contains_key(&key) {
charge(btree_entry::<(ItemId, Place), Vec<SupplyRoute>>())?;
}
let into = named.entry(key).or_default();
reserve_next(into, steps)?;
into.push((destination, route.level));
} else {
if !roots.contains_key(&route.id) {
charge(btree_entry::<ItemId, Vec<SupplyRoute>>())?;
}
let into = roots.entry(route.id).or_default();
reserve_next(into, steps)?;
into.push((destination, route.level));
}
}
}
Ok(Supply {
readers,
roots,
named,
holdings: BTreeMap::new(),
cut_reader,
cuts: cut::Cuts::default(),
refused: None,
memory,
})
}
#[expect(
clippy::too_many_arguments,
reason = "one question, the search state and the budget it is charged to"
)]
fn supplied(
&self,
supply: &mut Supply<'_>,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
from: usize,
reader: usize,
name: &SharedStr,
at: usize,
id: ItemId,
required: Level,
returning: bool,
rows: Option<&mut QueryRows<'_, '_, '_>>,
) -> bool {
let required = required.plain();
if supply.refused.is_some() || from == reader || required == Level::NOBODY {
return false;
}
if !returning
&& self.scopes[from].get(name.as_str()).is_some_and(|entry| {
entry.defs[at]
.get(id)
.is_some_and(|origin| origin.link.is_none())
})
&& let Some(roots) = supply.roots.get(&id)
{
let mut step = |units| {
tally::add(Work::SupplySteps, units);
charge(units)
};
if let Err(refused) = step(1 + roots.len()) {
supply.refused = Some(refused);
return false;
}
for (place, level) in roots {
if place.0 == from && place.1 == *name && place.2 == at {
match self.level_covers(*level, required, &mut step) {
Ok(true) => return true,
Ok(false) => {}
Err(refused) => {
supply.refused = Some(refused);
return false;
}
}
}
}
}
if supply.cut_reader == Some(reader) {
let key = (id, name.clone(), at, required, returning);
return match self
.retained_cut(supply, charge, reader, &key, rows)
.and_then(|proof| proof.answer(from, returning, charge))
{
Ok(answer) => answer,
Err(refused) => {
supply.refused = Some(refused);
false
}
};
}
let other = (id, name.clone(), at, required, !returning);
let key = if supply
.holdings
.get(&other)
.is_some_and(|holding| holding.firm_equivalent)
{
other
} else {
(id, name.clone(), at, required, returning)
};
let holding = match self.retained_holding(supply, charge, &key, rows) {
Ok(holding) => holding,
Err(refused) => {
supply.refused = Some(refused);
return false;
}
};
holding.holds(from) && holding.dominates(reader, from) == returning
}
fn retained_holding<'s>(
&self,
supply: &'s mut Supply<'_>,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
key: &HoldingKey,
rows: Option<&mut QueryRows<'_, '_, '_>>,
) -> Result<&'s Holding, LoadError> {
#[cfg(test)]
reference::retrieved_holder();
if !supply.holdings.contains_key(key) {
let holding = self.holding(supply, charge, key, rows)?;
let decl = &self.uses[self.glob_imports[0]];
supply.memory.charge(
btree_entry::<HoldingKey, Holding>(),
&decl.file,
Some(decl.line),
)?;
supply.holdings.insert(key.clone(), holding);
}
Ok(&supply.holdings[key])
}
fn holding(
&self,
supply: &Supply<'_>,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
query: &HoldingKey,
mut rows: Option<&mut QueryRows<'_, '_, '_>>,
) -> Result<Holding, LoadError> {
let (id, name, at, required, carried) = query;
let (id, at, required, carried) = (*id, *at, *required, *carried);
let memory = supply.memory.child();
let decl = &self.uses[self.glob_imports[0]];
let admit = |bytes| memory.charge(bytes, &decl.file, Some(decl.line));
admit(SUPPLY_BASE_BYTES)?;
let mut step = |count: usize| {
tally::add(Work::SupplySteps, count);
charge(count)
};
step(1)?;
let mut graph = HolderGraph::new(at);
let mut firm_equivalent = true;
for (root, level) in supply
.roots
.get(&id)
.into_iter()
.flatten()
.filter(|(root, _)| root.2 == at)
{
step(1)?;
if !self.level_covers(*level, required, &mut step)? {
continue;
}
firm_equivalent &= !level.is_companion();
if level.is_companion() && !carried {
continue;
}
graph.edge(0, root, &mut step, &admit)?;
}
let mut next = 1;
while let Some(held) = graph.nodes.get(next).cloned() {
firm_equivalent &= self.visit_holder_routes(
supply,
query,
&held,
&mut step,
&mut rows,
|destination, step| graph.edge(next, destination, step, &admit),
)?;
next += 1;
}
let stack_steps = Steps::LoadAt {
memory: &memory,
file: &decl.file,
line: decl.line,
};
let span = holder_spans(
&dominators(
&graph.successors,
&graph.predecessors,
&mut step,
stack_steps,
)?,
&mut step,
stack_steps,
)?;
Holding::retain(
graph.place,
&span,
firm_equivalent,
name,
at,
&supply.memory,
decl,
)
}
pub(crate) fn read_globbed_any(
&self,
module: usize,
name: &str,
at: usize,
steps: Steps<'_>,
) -> Result<bool, Fail> {
tally::add(Work::AnyLookups, 1);
if self.replaced(name, at) {
let memory = steps.temporary();
let bounded = memory.as_ref().map_or(steps, |memory| steps.at(memory));
self.reserve_glob_lookup(module, name, at, bounded)?;
return Ok(!self.read_globbed(module, name, at, bounded)?.is_empty());
}
if let Some(views) = self.globs.holding.get(name)
&& views.len() < self.reads_of(module).len()
{
steps
.reserve(vec_first::<&[usize]>() + views.len() * vec_slot::<&[usize]>())
.map_err(Fail::Storage)?;
}
let mut reads = self.reads_holding(module, name);
let mut visited = 0;
let found = reads.any(|read| {
tally::add(Work::LookupReads, 1);
visited += 1;
self.globs.views[read.view]
.names
.get(name)
.is_some_and(|lists| !lists[at].is_empty())
});
self.count_lookups(steps, module, reads.scanned(), visited);
Ok(found)
}
fn count_lookups(&self, steps: Steps<'_>, module: usize, scanned: usize, reads: usize) {
tally::add(Work::LookupScans, scanned);
let units = scanned + reads;
if units == 0 {
return;
}
match steps {
Steps::Load | Steps::LoadAt { .. } => self.lookups.add(units),
Steps::Query(meter) => {
tally::add(Work::LookupCharges, units);
meter.count_query(units, module);
}
Steps::Observed(_) | Steps::QueryAt { .. } | Steps::QueryItems { .. } => {
tally::add(Work::LookupCharges, units);
steps
.query_meter()
.expect("query proof has a meter")
.count_query(units, module);
}
}
}
fn blocked_in(&self, module: usize, name: &str, at: usize) -> bool {
self.imports_of(module, name)
.iter()
.any(|position| !self.use_free[*position][at] || self.left_to_globs(*position, at))
}
fn defs_held(&self, module: usize, class: &[bool], defs: &Bound) -> Vec<Held> {
self.defs_held_iter(module, class, defs).collect()
}
fn defs_held_iter<'a>(
&'a self,
module: usize,
class: &'a [bool],
defs: &'a Bound,
) -> impl Iterator<Item = Held> + 'a {
defs.iter().filter_map(move |(id, origin)| {
origin
.visibilities()
.map(|vis| self.level_of(vis, module, Steps::Load))
.filter(|level| self.allowed(module, class, *level))
.reduce(|left, right| self.wider(left, right))
.map(|level| {
(
*id,
if origin.companion {
level.companion()
} else {
level
},
)
})
})
}
fn widest(&self, held: &mut Vec<Held>, site: usize, meter: &Meter) -> Result<(), LoadError> {
self.widest_charged(held, &|units| self.candidate_steps(units, site, meter))
}
fn widest_charged(
&self,
held: &mut Vec<Held>,
charge: &impl Fn(usize) -> Result<(), LoadError>,
) -> Result<(), LoadError> {
if held.len() < 2 {
return Ok(());
}
charge(sort_units(held.len()) + held.len())?;
held.sort_unstable_by(|left, right| {
left.0
.cmp(&right.0)
.then_with(|| self.width_order(left.1, right.1))
});
held.dedup_by(|later, retained| {
if later.0 != retained.0 {
return false;
}
if !later.1.is_companion() {
retained.1 = retained.1.plain();
}
true
});
Ok(())
}
fn glob_held(
&self,
module: usize,
class: &[bool],
glob: Level,
held: &[Held],
into: (&mut Vec<Held>, &mut Vec<Held>),
) {
self.glob_held_iter(module, class, glob, held.iter().copied(), into);
}
fn glob_held_iter(
&self,
module: usize,
class: &[bool],
glob: Level,
held: impl Iterator<Item = Held>,
into: (&mut Vec<Held>, &mut Vec<Held>),
) {
let (seen, hidden) = into;
for (id, level) in held {
let mut met = self.meet(glob, level).plain();
if level.is_companion() {
met = met.companion();
}
if self.allowed(module, class, met) {
seen.push((id, met));
} else {
hidden.push((id, met));
}
}
}
fn exposed(
&self,
seen: Vec<Held>,
hidden: Vec<Held>,
site: usize,
meter: &Meter,
) -> Result<Vec<Held>, LoadError> {
self.exposed_charged(seen, hidden, &|units| {
self.candidate_steps(units, site, meter)
})
}
fn exposed_charged(
&self,
mut seen: Vec<Held>,
mut hidden: Vec<Held>,
charge: &impl Fn(usize) -> Result<(), LoadError>,
) -> Result<Vec<Held>, LoadError> {
self.expose_in_place(&mut seen, &mut hidden, charge)?;
Ok(seen)
}
fn expose_in_place(
&self,
seen: &mut Vec<Held>,
hidden: &mut Vec<Held>,
charge: &impl Fn(usize) -> Result<(), LoadError>,
) -> Result<(), LoadError> {
self.widest_charged(seen, charge)?;
charge(seen.len() + hidden.len() + sort_units(hidden.len()))?;
let Some(widest) = seen
.iter()
.map(|held| held.1)
.reduce(|left, right| self.wider(left, right))
else {
return Ok(());
};
hidden.retain(|(id, _)| seen.binary_search_by_key(id, |held| held.0).is_err());
hidden.sort_unstable_by_key(|held| held.0);
hidden.dedup_by_key(|held| held.0);
if !ambiguity_seen(seen.len() + hidden.len(), seen.len()) {
return Ok(());
}
charge(hidden.len() + sort_units(seen.len() + hidden.len()))?;
seen.extend(hidden.drain(..).map(|(id, _)| (id, widest.companion())));
seen.sort_unstable_by_key(|held| held.0);
Ok(())
}
fn export_ids(
&self,
target: usize,
class: &[bool],
name: &str,
at: usize,
site: usize,
meter: &Meter,
) -> Result<Vec<Held>, LoadError> {
Ok(self.exported(target, class, name, at, site, meter)?.0)
}
fn exported(
&self,
target: usize,
class: &[bool],
name: &str,
at: usize,
site: usize,
meter: &Meter,
) -> Result<(Vec<Held>, bool), LoadError> {
if let Some(defs) = self.scopes[target]
.get(name)
.map(|entry| &entry.defs[at])
.filter(|defs| !defs.is_empty())
{
return Ok((self.defs_held(target, class, defs), false));
}
if self.blocked_in(target, name, at) {
return Ok((Vec::new(), false));
}
let reads = self.reads_holding(target, name);
self.charge_steps(reads.scanned() + reads.len(), site, meter)?;
tally::add(Work::Recomputations, 1);
let (seen, hidden) = if self.flagged(name, at) {
self.split_globs_delivered(target, reads, class, name, at)
} else {
self.split_globs_plain(target, reads, class, name, at)
};
let delivered = !seen.is_empty() || !hidden.is_empty();
Ok((self.exposed(seen, hidden, site, meter)?, delivered))
}
fn split_globs_delivered(
&self,
target: usize,
reads: Holders<'_>,
class: &[bool],
name: &str,
at: usize,
) -> (Vec<Held>, Vec<Held>) {
let (mut seen, mut hidden) = (Vec::new(), Vec::new());
for (read, held) in
self.delivered(target, reads, name, at, Some(class), Work::RecomputedReads)
{
let glob = self.level_of(&self.uses[read.glob].vis, target, Steps::Load);
self.glob_held(target, class, glob, &held, (&mut seen, &mut hidden));
}
(seen, hidden)
}
fn split_globs_plain(
&self,
target: usize,
reads: Holders<'_>,
class: &[bool],
name: &str,
at: usize,
) -> (Vec<Held>, Vec<Held>) {
let (mut seen, mut hidden) = (Vec::new(), Vec::new());
for read in reads {
tally::add(Work::RecomputedReads, 1);
let Some(held) = self.globs.views[read.view]
.names
.get(name)
.map(|lists| &lists[at])
.filter(|held| !held.is_empty())
else {
continue;
};
let glob = self.level_of(&self.uses[read.glob].vis, target, Steps::Load);
self.glob_held(target, class, glob, held, (&mut seen, &mut hidden));
}
(seen, hidden)
}
fn add_to_view<'m>(
&mut self,
view: usize,
name: &str,
at: usize,
ids: &[Held],
meter: &'m Meter,
) -> Result<Added<'m>, LoadError> {
let memory = Transient::new(meter);
if ids.is_empty() {
return Ok(Added {
ids: Vec::new(),
_memory: memory,
});
}
let decl = &self.uses[self.globs.views[view].site];
memory.charge(
vec_first::<Held>() + ids.len() * vec_slot::<Held>(),
&decl.file,
Some(decl.line),
)?;
self.charge_steps(ids.len(), self.globs.views[view].site, meter)?;
tally::add(Work::CandidateSteps, ids.len());
let held = self.globs.views[view].names.get(name);
let mut new = 0;
let fresh: Vec<Held> = ids
.iter()
.copied()
.filter(|(id, level)| {
let known = held.and_then(|lists| {
lists[at]
.binary_search_by_key(id, |known| known.0)
.ok()
.map(|place| lists[at][place].1)
});
match known {
None => {
new += 1;
true
}
Some(known) => {
self.width_order(*level, known).is_lt()
|| known.is_companion() && !level.is_companion()
}
}
})
.collect();
if fresh.is_empty() {
return Ok(Added {
ids: fresh,
_memory: memory,
});
}
let mut bytes = new * vec_slot::<Held>();
if held.is_none_or(|lists| lists[at].is_empty()) {
bytes += vec_first::<Held>();
}
let key = if held.is_some() {
None
} else {
bytes += NAME_BYTES + holder_bytes(!self.globs.holding.contains_key(name));
let known = self.globs.strings.get(name).cloned();
if known.is_none() {
bytes += shared_text(name.len()) + hash_entry::<SharedStr>();
}
let text = known.is_none();
Some((known, text))
};
if fresh.iter().any(|entry| entry.1.is_companion())
&& !self.globs.companions.contains_key(name)
{
bytes += hash_entry::<(SharedStr, [bool; 3])>();
}
let scratch = Transient::new(meter);
if new < fresh.len() {
scratch.charge(
vec_first::<Held>() + fresh.len() * vec_slot::<Held>(),
&decl.file,
Some(decl.line),
)?;
}
self.charge_tables(bytes, self.globs.views[view].site, meter)?;
let key = key.map(|(known, text)| (known.unwrap_or_else(|| SharedStr::from(name)), text));
let widened = (new < fresh.len()).then(|| self.widened_entries(view, name, at, &fresh));
let finals = widened.as_deref().unwrap_or(&fresh);
#[cfg(test)]
self.assert_widened(view, name, at, finals);
self.store_entries(view, name, at, key, finals);
Ok(Added {
ids: fresh,
_memory: memory,
})
}
fn widened_entries(&self, view: usize, name: &str, at: usize, fresh: &[Held]) -> Vec<Held> {
let held = self.globs.views[view]
.names
.get(name)
.map(|lists| &lists[at]);
fresh
.iter()
.map(|entry| {
let known = held.and_then(|held| {
held.binary_search_by_key(&entry.0, |known| known.0)
.ok()
.map(|place| held[place].1)
});
let Some(known) = known else { return *entry };
let mut level = if self.width_order(entry.1, known).is_lt() {
entry.1.plain()
} else {
known.plain()
};
if known.is_companion() && entry.1.is_companion() {
level = level.companion();
}
(entry.0, level)
})
.collect()
}
fn store_entries(
&mut self,
view: usize,
name: &str,
at: usize,
key: Option<(SharedStr, bool)>,
finals: &[Held],
) {
if finals.iter().any(|entry| entry.1.is_companion()) {
let key = key
.as_ref()
.map(|(key, _)| key.clone())
.or_else(|| self.globs.strings.get(name).cloned())
.expect("a name a view holds is interned");
self.globs.companions.entry(key).or_default()[at] = true;
}
let lists = match key {
Some((key, text)) => {
if text {
self.globs.strings.insert(key.clone());
}
self.globs
.holding
.entry(key.clone())
.or_default()
.push(view);
self.globs.views[view].names.entry(key).or_default()
}
None => self.globs.views[view]
.names
.get_mut(name)
.expect("the name is held"),
};
for entry in finals {
match lists[at].binary_search_by_key(&entry.0, |known| known.0) {
Ok(place) => lists[at][place] = *entry,
Err(place) => lists[at].insert(place, *entry),
}
}
}
#[cfg(test)]
fn assert_widened(&self, view: usize, name: &str, at: usize, finals: &[Held]) {
let Some(lists) = self.globs.views[view].names.get(name) else {
return;
};
for (id, level) in finals {
if let Ok(place) = lists[at].binary_search_by_key(id, |known| known.0) {
let known = lists[at][place].1;
assert!(
self.width_order(*level, known).is_le()
&& (known.is_companion() || !level.is_companion()),
"the view {view} narrows {id:?} under {name} in the name space {at}: \
{known:?} to {level:?}"
);
}
}
}
fn charge_tables(&mut self, bytes: usize, site: usize, meter: &Meter) -> Result<(), LoadError> {
let decl = &self.uses[site];
meter.globs(bytes, &decl.file, Some(decl.line))?;
self.globs.charged += bytes;
Ok(())
}
fn charge_work(&self, bytes: usize, site: usize, meter: &Meter) -> Result<(), LoadError> {
let decl = &self.uses[site];
meter.globs(bytes, &decl.file, Some(decl.line))
}
fn charge_steps(&self, units: usize, site: usize, meter: &Meter) -> Result<(), LoadError> {
let decl = &self.uses[site];
meter.work(units, &decl.file, Some(decl.line))
}
fn candidate_steps(&self, units: usize, site: usize, meter: &Meter) -> Result<(), LoadError> {
self.charge_steps(units, site, meter)?;
tally::add(Work::CandidateSteps, units);
Ok(())
}
fn make_view(
&mut self,
target: usize,
class: &[bool],
site: usize,
meter: &Meter,
) -> Result<usize, LoadError> {
self.charge_tables(VIEW_BYTES + 2 * class.len(), site, meter)?;
let view = self.globs.views.len();
self.globs.views.push(View {
target,
class: class.into(),
names: BTreeMap::new(),
active: Vec::new(),
turns: 0,
passive: BTreeMap::new(),
places: BTreeMap::new(),
site,
hidden: false,
unseen: None,
});
self.globs.view_of.insert((target, class.into()), view);
self.globs.exports[target].push(view);
self.turn_readers(target, site, meter)?;
let reads = self.reads_of(target).len();
let listed = vec_first::<(usize, Level)>() + reads * vec_slot::<(usize, Level)>();
self.charge_work(listed, site, meter)?;
self.charge_steps(reads, site, meter)?;
let exact = Self::exact_mode();
let covert = |glob: Level| !exact && !self.allowed(target, class, glob);
let mut sources: Vec<(usize, Level)> = self
.reads_of(target)
.iter()
.map(|read| {
(
read.view,
self.level_of(&self.uses[read.glob].vis, target, Steps::Load),
)
})
.collect();
sources.sort_unstable_by_key(|(source, glob)| (covert(*glob), *source, *glob));
sources.dedup();
let split = sources.partition_point(|(_, glob)| !covert(*glob));
let (shown, hidden) = sources.split_at(split);
let gathered = self.gather_bytes(target, shown);
self.charge_work(gathered, site, meter)?;
let names = self.scopes[target].len()
+ shown
.iter()
.map(|(source, _)| self.globs.views[*source].names.len())
.sum::<usize>();
self.charge_steps(names, site, meter)?;
let (content, any_hidden, dropped) =
self.gather(target, class, shown, hidden, site, meter)?;
let hiding: Vec<usize> = hidden.iter().map(|(source, _)| *source).collect();
drop(sources);
meter.release_globs(listed);
self.globs.views[view].hidden = any_hidden;
if !any_hidden {
for read in 0..self.globs.reads[target].len() {
let read_view = self.globs.reads[target][read].view;
if self.globs.views[read_view]
.unseen()
.covert
.contains_key(&target)
{
self.note_open(read_view, target, site, meter)?;
}
}
}
for source in hiding {
self.note_hiding(view, source, site, meter)?;
}
for (name, at) in dropped {
self.note_dropped(view, name, at, site, meter)?;
}
for (name, lists) in content {
for (at, ids) in lists.into_iter().enumerate() {
self.add_to_view(view, &name, at, &ids, meter)?;
}
}
meter.release_globs(gathered);
Ok(view)
}
fn turn_readers(&mut self, target: usize, site: usize, meter: &Meter) -> Result<(), LoadError> {
for read in 0..self.globs.reads[target].len() {
let read_view = self.globs.reads[target][read].view;
let level = self.level_of(
&self.uses[self.globs.reads[target][read].glob].vis,
target,
Steps::Load,
);
let shown = !self.covert_level(target, level);
let readers = &self.globs.views[read_view];
let passive = readers
.passive
.get(&target)
.and_then(|list| list.iter().position(|known| *known == read));
if let Some(at) = passive {
if !shown {
let covert = &readers.unseen().covert;
let bytes = covert_bytes(!covert.contains_key(&target), covert.is_empty())
+ readers.unseen_bytes();
self.charge_tables(bytes, site, meter)?;
}
let readers = &mut self.globs.views[read_view];
let list = readers.passive.get_mut(&target).expect("listed");
list.remove(at);
if list.is_empty() {
readers.passive.remove(&target);
}
let turn = readers.turns;
readers.turns += 1;
if shown {
readers.active.push((target, read, turn));
} else {
readers
.unseen_mut()
.covert
.entry(target)
.or_default()
.push((read, turn));
}
} else if shown
&& let Some(at) = readers
.unseen()
.covert
.get(&target)
.and_then(|list| list.iter().position(|known| known.0 == read))
{
let readers = &mut self.globs.views[read_view];
let unseen = readers.unseen_mut();
let list = unseen.covert.get_mut(&target).expect("listed");
let (_, turn) = list.remove(at);
if list.is_empty() {
unseen.covert.remove(&target);
unseen.open.remove(&target);
}
let place = readers.active.partition_point(|known| known.2 < turn);
readers.active.insert(place, (target, read, turn));
}
}
Ok(())
}
fn note_open(
&mut self,
view: usize,
module: usize,
site: usize,
meter: &Meter,
) -> Result<(), LoadError> {
let unseen = &self.globs.views[view];
let open = &unseen.unseen().open;
if open.contains(&module) {
return Ok(());
}
let bytes = set_bytes::<usize>(open.is_empty()) + unseen.unseen_bytes();
self.charge_tables(bytes, site, meter)?;
self.globs.views[view].unseen_mut().open.insert(module);
Ok(())
}
fn note_hiding(
&mut self,
view: usize,
source: usize,
site: usize,
meter: &Meter,
) -> Result<(), LoadError> {
let unseen = &self.globs.views[view];
let hiding = &unseen.unseen().hiding;
if hiding.contains(&source) {
return Ok(());
}
let bytes = set_bytes::<usize>(hiding.is_empty()) + unseen.unseen_bytes();
self.charge_tables(bytes, site, meter)?;
self.globs.views[view].unseen_mut().hiding.insert(source);
Ok(())
}
fn note_dropped(
&mut self,
view: usize,
name: SharedStr,
at: usize,
site: usize,
meter: &Meter,
) -> Result<(), LoadError> {
let unseen = &self.globs.views[view];
let dropped = &unseen.unseen().dropped;
let key = (name, at);
if dropped.contains(&key) {
return Ok(());
}
let bytes = set_bytes::<(SharedStr, usize)>(dropped.is_empty()) + unseen.unseen_bytes();
self.charge_tables(bytes, site, meter)?;
self.globs.views[view].unseen_mut().dropped.insert(key);
Ok(())
}
fn gather<'s>(
&'s self,
target: usize,
class: &[bool],
shown: &[(usize, Level)],
covert: &[(usize, Level)],
site: usize,
meter: &Meter,
) -> Result<Gathered, LoadError> {
let mut content: BTreeMap<&'s str, [Vec<Held>; 3]> = BTreeMap::new();
let mut outside: BTreeMap<(&'s str, usize), Vec<Held>> = BTreeMap::new();
let mut blocked: BTreeMap<(&'s str, usize), bool> = BTreeMap::new();
for (name, entry) in &self.scopes[target] {
for (at, defs) in entry.defs.iter().enumerate() {
let held = self.defs_held(target, class, defs);
if !held.is_empty() {
content.entry(name.as_str()).or_default()[at] = held;
}
}
}
for (source, glob) in shown {
for (name, lists) in &self.globs.views[*source].names {
for (at, held) in lists.iter().enumerate() {
if held.is_empty()
|| self.binds_itself(target, name, at)
|| *blocked
.entry((name.as_str(), at))
.or_insert_with(|| self.blocked_in(target, name, at))
{
continue;
}
let mut hidden = Vec::new();
self.glob_held(
target,
class,
*glob,
held,
(
&mut content.entry(name.as_str()).or_default()[at],
&mut hidden,
),
);
if !hidden.is_empty() {
outside
.entry((name.as_str(), at))
.or_default()
.extend(hidden);
}
}
}
}
let (any_hidden, probed) =
self.gather_covert(target, class, covert, &content, &mut outside, site, meter)?;
let mut gathered: Exported = Vec::with_capacity(content.len());
let mut dropped: Vec<(SharedStr, usize)> = Vec::new();
for (name, mut lists) in content {
for (at, ids) in lists.iter_mut().enumerate() {
let hidden = outside.remove(&(name, at)).unwrap_or_default();
let plain = !self.flagged(name, at);
if plain && ids.is_empty() && !hidden.is_empty() {
let key = self
.globs
.strings
.get(name)
.expect("a name a view holds is interned");
dropped.push((key.clone(), at));
}
*ids = if !self.replaced(name, at)
&& (plain
|| (hidden.is_empty() && !ids.iter().any(|held| held.1.is_companion())))
{
self.exposed(std::mem::take(ids), hidden, site, meter)?
} else {
self.export_ids(target, class, name, at, site, meter)?
};
}
gathered.push((name.to_owned(), lists));
}
meter.release_globs(probed);
Ok((gathered, any_hidden, dropped))
}
#[expect(
clippy::too_many_arguments,
reason = "one gathering: the view's module and class, the views probed, what was gathered and the budget"
)]
fn gather_covert<'s>(
&'s self,
target: usize,
class: &[bool],
covert: &[(usize, Level)],
content: &BTreeMap<&'s str, [Vec<Held>; 3]>,
outside: &mut BTreeMap<(&'s str, usize), Vec<Held>>,
site: usize,
meter: &Meter,
) -> Result<(bool, usize), LoadError> {
let mut any_hidden = !outside.is_empty();
let mut probed = 0;
for (source, glob) in covert {
let names = &self.globs.views[*source].names;
if !any_hidden {
for (name, lists) in names {
self.charge_steps(1, site, meter)?;
if (0..3).any(|at| {
!lists[at].is_empty()
&& !self.binds_itself(target, name, at)
&& !self.blocked_in(target, name, at)
}) {
any_hidden = true;
break;
}
}
}
self.charge_steps(content.len().min(names.len()), site, meter)?;
let mut probe = |name: &'s str, lists: &Lists| -> Result<(), LoadError> {
for (at, held) in lists.iter().enumerate() {
if held.is_empty()
|| content[name][at].is_empty()
|| self.binds_itself(target, name, at)
{
continue;
}
let bytes = btree_entry::<(&str, usize), Vec<Held>>()
+ vec_first::<Held>()
+ held.len() * vec_slot::<Held>();
self.charge_work(bytes, site, meter)?;
probed += bytes;
let hidden = outside.entry((name, at)).or_default();
let before = hidden.len();
self.glob_held(target, class, *glob, held, (&mut Vec::new(), hidden));
debug_assert_eq!(
hidden.len() - before,
held.len(),
"a glob the class cannot access brings in only what it cannot access"
);
}
Ok(())
};
if content.len() <= names.len() {
for name in content.keys() {
if let Some(lists) = names.get(*name) {
probe(name, lists)?;
}
}
} else {
for (name, lists) in names {
if content.contains_key(name.as_str()) {
probe(name.as_str(), lists)?;
}
}
}
}
Ok((any_hidden, probed))
}
fn gather_bytes(&self, target: usize, sources: &[(usize, Level)]) -> usize {
const NAME: usize = btree_entry::<&str, [Vec<Held>; 3]>()
+ vec_slot::<(String, [Vec<Held>; 3])>()
+ 3 * vec_first::<Held>();
let own: usize = self.scopes[target]
.iter()
.map(|(name, entry)| {
NAME + name.len()
+ entry
.defs
.iter()
.map(|defs| defs.iter().count() * vec_slot::<Held>())
.sum::<usize>()
})
.sum();
let globbed: usize = sources
.iter()
.flat_map(|(source, _)| &self.globs.views[*source].names)
.map(|(name, lists)| {
NAME + name.len()
+ 3 * (btree_entry::<(&str, usize), bool>()
+ btree_entry::<(&str, usize), Vec<Held>>()
+ vec_first::<Held>())
+ lists
.iter()
.map(|ids| 2 * ids.len() * vec_slot::<Held>())
.sum::<usize>()
})
.sum();
btree_map::<&str, [Vec<Held>; 3]>()
+ btree_map::<(&str, usize), bool>()
+ vec_first::<(String, [Vec<Held>; 3])>()
+ own
+ globbed
}
pub(crate) fn read_glob(
&mut self,
glob: usize,
target: usize,
waiters: &mut dyn Waiters,
meter: &Meter,
) -> Result<(), LoadError> {
let module = self.uses[glob].module;
let class = self.class_for(target, module);
if let Some(view) = self.globs.view_of.get(&(target, class.clone()))
&& self.globs.read_by.contains(&(glob, *view))
{
return Ok(());
}
let view = match self.globs.view_of.get(&(target, class.clone())) {
Some(view) => *view,
None => self.make_view(target, &class, glob, meter)?,
};
let mut bytes = READ_BYTES + vec_slot::<usize>();
if self.globs.reads[module].is_empty() {
bytes += vec_first::<GlobRead>();
}
if !self.globs.views[view].places.contains_key(&module) {
bytes += btree_entry::<usize, Vec<usize>>() + vec_first::<usize>();
}
self.charge_tables(bytes, glob, meter)?;
let read = self.globs.reads[module].len();
self.globs.reads[module].push(GlobRead { glob, target, view });
self.globs.views[view]
.places
.entry(module)
.or_default()
.push(read);
self.globs.read_by.insert((glob, view));
let level = self.level_of(&self.uses[glob].vis, module, Steps::Load);
if !Self::exact_mode() && !self.exports_by_path(module) {
for place in 0..self.exports_of(module).len() {
let own = self.globs.exports[module][place];
if !self.allowed(module, &self.globs.views[own].class, level) {
self.note_hiding(own, view, glob, meter)?;
}
}
}
let first = self.globs.passing.insert((module, view, level));
let passes = first && !self.exports_of(module).is_empty();
if passes && self.covert_level(module, level) {
return self.read_covert(module, read, view, glob, waiters, meter);
}
if !passes {
if first {
self.globs.views[view]
.passive
.entry(module)
.or_default()
.push(read);
}
let memory = Transient::new(meter);
let decl = &self.uses[glob];
for name in waiters.waited_in(module, &memory, &decl.file, decl.line)? {
if self.globs.views[view].names.contains_key(name.as_str()) {
waiters.wake(module, &name)?;
}
}
return Ok(());
}
let turn = self.globs.views[view].turns;
self.globs.views[view].turns += 1;
self.globs.views[view].active.push((module, read, turn));
let mut after: Option<SharedStr> = None;
loop {
let names = &self.globs.views[view].names;
let next = match &after {
None => names.iter().next(),
Some(name) => names
.range::<SharedStr, _>((Excluded(name), Unbounded))
.next(),
};
let Some((name, source)) = next else {
return Ok(());
};
let memory = Transient::new(meter);
let decl = &self.uses[glob];
let steps = Steps::LoadAt {
memory: &memory,
file: &decl.file,
line: decl.line,
};
let name = name.clone();
let mut inline = [[(ItemId(0), Level::NOBODY); 2]; 3];
let [types, values, macros] = &mut inline;
let lists = [
copy_held(&source[0], types, steps)?,
copy_held(&source[1], values, steps)?,
copy_held(&source[2], macros, steps)?,
];
for (at, ids) in lists.iter().enumerate() {
if !ids.is_empty() {
self.charge_steps(1, glob, meter)?;
let mut work = Queue::new(meter);
self.arrive(module, read, &name, at, ids, &mut work, waiters, meter)?;
self.pass_on(work, waiters, meter)?;
}
}
after = Some(name);
}
}
fn read_covert(
&mut self,
module: usize,
read: usize,
view: usize,
glob: usize,
waiters: &mut dyn Waiters,
meter: &Meter,
) -> Result<(), LoadError> {
let unseen = &self.globs.views[view];
let covert = &unseen.unseen().covert;
let bytes =
covert_bytes(!covert.contains_key(&module), covert.is_empty()) + unseen.unseen_bytes();
self.charge_tables(bytes, glob, meter)?;
let readers = &mut self.globs.views[view];
let turn = readers.turns;
readers.turns += 1;
readers
.unseen_mut()
.covert
.entry(module)
.or_default()
.push((read, turn));
let memory = Transient::new(meter);
let decl = &self.uses[glob];
let waited = waiters.waited_in(module, &memory, &decl.file, decl.line)?;
self.covert_steps(waited.len(), glob, meter)?;
if self
.exports_of(module)
.iter()
.any(|own| !self.globs.views[*own].hidden)
{
let mut found = false;
for (name, lists) in &self.globs.views[view].names {
self.covert_steps(1, glob, meter)?;
if (0..3).any(|at| {
!lists[at].is_empty()
&& !self.binds_itself(module, name, at)
&& !self.blocked_in(module, name, at)
}) {
found = true;
break;
}
}
if found {
for place in 0..self.globs.exports[module].len() {
let own = self.globs.exports[module][place];
self.globs.views[own].hidden = true;
}
}
}
if self
.exports_of(module)
.iter()
.any(|own| !self.globs.views[*own].hidden)
{
self.note_open(view, module, glob, meter)?;
}
let mut waits = waited.iter().peekable();
for (name, at) in self.covert_due(module, view, glob, meter, &memory)? {
while let Some(waiting) = waits.next_if(|waiting| waiting.as_str() <= name.as_str()) {
if self.globs.views[view].names.contains_key(waiting.as_str()) {
waiters.wake(module, waiting)?;
}
}
self.covert_steps(1, glob, meter)?;
let candidates = Transient::new(meter);
let decl = &self.uses[glob];
let mut inline = [(ItemId(0), Level::NOBODY); 2];
let ids = copy_held(
&self.globs.views[view].names[name.as_str()][at],
&mut inline,
Steps::LoadAt {
memory: &candidates,
file: &decl.file,
line: decl.line,
},
)?;
let mut work = Queue::new(meter);
self.arrive(module, read, &name, at, &ids, &mut work, waiters, meter)?;
self.pass_on(work, waiters, meter)?;
}
for waiting in waits {
if self.globs.views[view].names.contains_key(waiting.as_str()) {
waiters.wake(module, waiting)?;
}
}
Ok(())
}
fn covert_due(
&self,
module: usize,
view: usize,
glob: usize,
meter: &Meter,
memory: &Transient<'_>,
) -> Result<Vec<(SharedStr, usize)>, LoadError> {
let steps = Steps::LoadAt {
memory,
file: &self.uses[glob].file,
line: self.uses[glob].line,
};
let own = self.exports_of(module);
let source = &self.globs.views[view].names;
let holds = |names: &BTreeMap<SharedStr, Lists>, name: &str, at: usize| {
names.get(name).is_some_and(|lists| !lists[at].is_empty())
};
let open = |name: &str, at: usize| {
!self.binds_itself(module, name, at) && !self.blocked_in(module, name, at)
};
steps.storage_work(own.len())?;
let held: usize = own
.iter()
.map(|own| self.globs.views[*own].names.len())
.sum();
let mut due: Vec<(SharedStr, usize)> = Vec::new();
if held <= source.len() {
self.covert_steps(held, glob, meter)?;
for own in own {
for (name, lists) in &self.globs.views[*own].names {
for (at, ids) in lists.iter().enumerate() {
if !ids.is_empty() && holds(source, name, at) && open(name, at) {
reserve_next(&mut due, steps)?;
due.push((name.clone(), at));
}
}
}
}
steps.storage_work(
due.len()
.saturating_mul(due.len().checked_ilog2().unwrap_or(0) as usize + 1),
)?;
due.sort_unstable();
steps.storage_work(due.len())?;
due.dedup();
} else {
self.covert_steps(source.len(), glob, meter)?;
for (name, lists) in source {
for (at, ids) in lists.iter().enumerate() {
if ids.is_empty() || !open(name, at) {
continue;
}
let mut held = false;
for own in own {
steps.storage_work(1)?;
if holds(&self.globs.views[*own].names, name, at) {
held = true;
break;
}
}
if held {
reserve_next(&mut due, steps)?;
due.push((name.clone(), at));
}
}
}
}
Ok(due)
}
fn covert_steps(&self, units: usize, site: usize, meter: &Meter) -> Result<(), LoadError> {
tally::add(Work::CovertChecks, units);
self.charge_steps(units, site, meter)
}
pub(crate) fn refresh(
&mut self,
module: usize,
name: &str,
waiters: &mut dyn Waiters,
meter: &Meter,
) -> Result<(), LoadError> {
for place in 0..self.exports_of(module).len() {
let view = self.globs.exports[module][place];
let site = self.globs.views[view].site;
for at in 0..3 {
let class = &self.globs.views[view].class;
let (ids, delivered) = self.exported(module, class, name, at, site, meter)?;
if delivered {
self.mark_exact(view, name, at, site, meter)?;
}
let fresh = self.add_to_view(view, name, at, &ids, meter)?;
if !fresh.is_empty() {
let grown = Grown::new(
view,
self.globs.strings.get(name).expect("interned").clone(),
at,
fresh,
);
let mut queue = Queue::new(meter);
queue.push(grown, &self.uses[self.globs.views[view].site])?;
self.pass_on(queue, waiters, meter)?;
}
}
}
Ok(())
}
fn mark_exact(
&mut self,
view: usize,
name: &str,
at: usize,
site: usize,
meter: &Meter,
) -> Result<(), LoadError> {
let key = if let Some(key) = self.globs.strings.get(name) {
if self.globs.exact.contains(&(view, key.clone(), at)) {
return Ok(());
}
key.clone()
} else {
self.charge_tables(
shared_text(name.len()) + hash_entry::<SharedStr>(),
site,
meter,
)?;
let key = SharedStr::from(name);
self.globs.strings.insert(key.clone());
key
};
self.charge_tables(
set_bytes::<(usize, SharedStr, usize)>(self.globs.exact.is_empty()),
site,
meter,
)?;
self.globs.exact.insert((view, key, at));
Ok(())
}
fn pass_on<'m>(
&mut self,
mut queue: Queue<'m>,
waiters: &mut dyn Waiters,
meter: &'m Meter,
) -> Result<(), LoadError> {
while let Some(grown) = queue.work.pop() {
let passive = &self.globs.views[grown.view].passive;
if !passive.is_empty()
&& let Some(modules) = waiters.waiting_on(&grown.name)
{
let woken: Vec<usize> = if modules.len() <= passive.len() {
modules
.iter()
.copied()
.filter(|module| passive.contains_key(module))
.collect()
} else {
passive
.keys()
.copied()
.filter(|module| modules.contains(module))
.collect()
};
for module in woken {
waiters.wake(module, &grown.name)?;
}
}
let told = if self.globs.views[grown.view].unseen().covert.is_empty() {
Vec::new()
} else {
self.covert_told(&grown, &*waiters, meter)?
};
let mut next = 0;
for reader in 0..self.globs.views[grown.view].active.len() {
let (module, read, turn) = self.globs.views[grown.view].active[reader];
while let Some(&covert) = told.get(next).filter(|covert| covert.0 < turn) {
self.tell_covert(&grown, covert, &mut queue, waiters, meter)?;
next += 1;
}
let glob = self.globs.reads[module][read].glob;
self.charge_steps(1, glob, meter)?;
self.arrive(
module,
read,
&grown.name,
grown.at,
&grown.ids,
&mut queue,
waiters,
meter,
)?;
}
for covert in &told[next..] {
self.tell_covert(&grown, *covert, &mut queue, waiters, meter)?;
}
}
Ok(())
}
fn covert_told(
&mut self,
grown: &Grown,
waiters: &dyn Waiters,
meter: &Meter,
) -> Result<Vec<Told>, LoadError> {
let site = self.globs.views[grown.view].site;
let (due, closed) = self.covert_changed(grown, site, meter)?;
if let Some(unseen) = self.globs.views[grown.view].unseen.as_mut() {
for module in closed {
unseen.open.remove(&module);
}
}
let readers = &self.globs.views[grown.view].unseen().covert;
let mut told: Vec<Told> = due
.iter()
.map(|&(module, (read, turn))| (turn, module, read, true))
.collect();
if let Some(modules) = waiters.waiting_on(&grown.name) {
self.covert_steps(modules.len().min(readers.len()), site, meter)?;
let waiting: Vec<usize> = if modules.len() <= readers.len() {
modules
.iter()
.copied()
.filter(|module| readers.contains_key(module))
.collect()
} else {
readers
.keys()
.copied()
.filter(|module| modules.contains(module))
.collect()
};
for module in waiting {
if due.binary_search_by_key(&module, |entry| entry.0).is_err() {
let (read, turn) = readers[&module][0];
told.push((turn, module, read, false));
}
}
}
told.sort_unstable();
Ok(told)
}
fn tell_covert<'m>(
&mut self,
grown: &Grown,
told: Told,
queue: &mut Queue<'m>,
waiters: &mut dyn Waiters,
meter: &'m Meter,
) -> Result<(), LoadError> {
let (_, module, read, arrives) = told;
if !arrives {
waiters.wake(module, &grown.name)?;
return Ok(());
}
self.arrive(
module,
read,
&grown.name,
grown.at,
&grown.ids,
queue,
waiters,
meter,
)
}
fn covert_changed(
&self,
grown: &Grown,
site: usize,
meter: &Meter,
) -> Result<Changed, LoadError> {
let flagged = self.flagged(&grown.name, grown.at);
let readers = self.globs.views[grown.view].unseen();
let mut found: Vec<usize> = Vec::new();
let holders = if readers.covert.len() > 1 {
self.globs
.holding
.get(grown.name.as_str())
.map(Vec::as_slice)
.filter(|holders| holders.len() < readers.covert.len())
} else {
None
};
if let Some(holders) = holders {
self.covert_steps(holders.len(), site, meter)?;
found.extend(
holders
.iter()
.map(|view| self.globs.views[*view].target)
.filter(|module| readers.covert.contains_key(module)),
);
}
self.covert_steps(readers.open.len(), site, meter)?;
let mut closed: Vec<usize> = Vec::new();
for module in &readers.open {
if self
.exports_of(*module)
.iter()
.any(|own| !self.globs.views[*own].hidden)
{
found.push(*module);
} else {
closed.push(*module);
}
}
let mut due: Vec<(usize, (usize, usize))> = Vec::new();
if holders.is_some() || !found.is_empty() {
if holders.is_none() {
found.extend(readers.covert.keys().copied());
}
found.sort_unstable();
found.dedup();
for module in found {
self.covert_steps(1, site, meter)?;
if !self.covert_inert(module, grown, flagged) {
due.push((module, readers.covert[&module][0]));
}
}
} else {
for (module, reads) in &readers.covert {
self.covert_steps(1, site, meter)?;
if !self.covert_inert(*module, grown, flagged) {
due.push((*module, reads[0]));
}
}
}
Ok((due, closed))
}
fn covert_inert(&self, module: usize, grown: &Grown, flagged: bool) -> bool {
self.exports_of(module).iter().all(|own| {
let view = &self.globs.views[*own];
view.hidden
&& view
.names
.get(grown.name.as_str())
.map(|lists| &lists[grown.at])
.filter(|held| !held.is_empty())
.is_none_or(|held| {
!flagged
&& !self.is_exact(*own, &grown.name, grown.at)
&& grown.ids.iter().all(|(id, _)| {
held.binary_search_by_key(id, |known| known.0).is_ok()
})
})
})
}
fn is_exact(&self, view: usize, name: &SharedStr, at: usize) -> bool {
!self.globs.exact.is_empty() && self.globs.exact.contains(&(view, name.clone(), at))
}
#[expect(
clippy::too_many_arguments,
reason = "one change passed on, the place it arrives at and the two sinks"
)]
fn arrive<'m>(
&mut self,
module: usize,
read: usize,
name: &SharedStr,
at: usize,
ids: &[Held],
work: &mut Queue<'m>,
waiters: &mut dyn Waiters,
meter: &'m Meter,
) -> Result<(), LoadError> {
waiters.wake(module, name)?;
if self.binds_itself(module, name, at) {
return Ok(());
}
let glob = self.globs.reads[module][read].glob;
let level = self.level_of(&self.uses[glob].vis, module, Steps::Load);
if self.blocked_in(module, name, at) {
for place in 0..self.exports_of(module).len() {
let view = self.globs.exports[module][place];
self.mark_exact(view, name, at, glob, meter)?;
}
return Ok(());
}
let plain = !self.flagged(name, at) && !self.exports_by_path(module);
for place in 0..self.globs.exports[module].len() {
let view = self.globs.exports[module][place];
let exact = self.is_exact(view, name, at);
let own = &self.globs.views[view];
let held = own
.names
.get(name.as_str())
.map(|lists| lists[at].as_slice())
.filter(|held| !held.is_empty());
if let Some(held) = held
&& !self.exports_by_path(module)
&& !exact
{
self.charge_steps(ids.len(), glob, meter)?;
tally::add(Work::CandidateSteps, ids.len());
if let Some(any_hidden) = self.unchanged(module, &own.class, level, held, ids) {
tally::add(Work::Deltas, 1);
if any_hidden {
self.globs.views[view].hidden = true;
}
continue;
}
}
let passed = match held {
Some(_) if plain && !exact => {
self.delta(module, view, name, at, level, ids, glob, meter)?
}
held => {
let holds = held.is_some();
self.arrival(
module, view, name, at, level, ids, holds, plain, exact, glob, meter,
)?
}
};
let Some(passed) = passed else {
continue;
};
let fresh = self.add_to_view(view, name, at, &passed, meter)?;
if !fresh.is_empty() {
work.push(Grown::new(view, name.clone(), at, fresh), &self.uses[glob])?;
}
}
Ok(())
}
fn unchanged(
&self,
module: usize,
class: &[bool],
level: Level,
held: &[Held],
ids: &[Held],
) -> Option<bool> {
let mut any_hidden = false;
for (id, item) in ids {
let met = self.meet(level, *item).plain();
let shown = self.allowed(module, class, met);
any_hidden |= !shown;
let kept = held
.binary_search_by_key(id, |known| known.0)
.is_ok_and(|place| {
self.width_order(held[place].1, met).is_le()
&& (!shown || item.is_companion() || !held[place].1.is_companion())
});
if !kept {
return None;
}
}
Some(any_hidden)
}
#[expect(
clippy::too_many_arguments,
reason = "one change arriving at one view, the glob it came through and the budget"
)]
fn delta(
&mut self,
module: usize,
view: usize,
name: &SharedStr,
at: usize,
level: Level,
ids: &[Held],
glob: usize,
meter: &Meter,
) -> Result<Option<Vec<Held>>, LoadError> {
let own = &self.globs.views[view];
let held = &own.names[name.as_str()][at];
let (mut seen, mut hidden) = (Vec::new(), Vec::new());
self.glob_held(module, &own.class, level, ids, (&mut seen, &mut hidden));
let newly: Vec<Held> = hidden
.iter()
.copied()
.filter(|(id, _)| held.binary_search_by_key(id, |known| known.0).is_err())
.collect();
let passed = if newly.is_empty() {
self.widest(&mut seen, glob, meter)?;
seen
} else {
tally::add(Work::Exposures, newly.len());
self.charge_steps(newly.len(), glob, meter)?;
self.export_ids(module, &own.class, name, at, glob, meter)?
};
if !hidden.is_empty() {
self.globs.views[view].hidden = true;
}
Ok(Some(passed))
}
#[expect(
clippy::too_many_arguments,
reason = "one change arriving at one view, the glob it came through and the budget"
)]
fn arrival(
&mut self,
module: usize,
view: usize,
name: &SharedStr,
at: usize,
level: Level,
ids: &[Held],
holds: bool,
plain: bool,
exact: bool,
glob: usize,
meter: &Meter,
) -> Result<Option<Vec<Held>>, LoadError> {
if exact || self.replaced(name, at) {
let class = &self.globs.views[view].class;
return self
.export_ids(module, class, name, at, glob, meter)
.map(Some);
}
let own = &self.globs.views[view];
let class: &[bool] = &own.class;
let (mut seen, mut hidden) = (Vec::new(), Vec::new());
self.glob_held(module, class, level, ids, (&mut seen, &mut hidden));
let fresh = plain && !holds;
let (passed, hide) = if !seen.is_empty() {
if own.hidden
&& hidden.is_empty()
&& fresh
&& self.hides_nothing(module, view, name, at, glob, meter)?
{
self.widest(&mut seen, glob, meter)?;
(Some(seen), false)
} else if own.hidden || !hidden.is_empty() {
(
Some(self.export_ids(module, class, name, at, glob, meter)?),
true,
)
} else if seen.iter().any(|held| held.1.is_companion()) {
(
Some(self.export_ids(module, class, name, at, glob, meter)?),
false,
)
} else {
self.widest(&mut seen, glob, meter)?;
(Some(seen), false)
}
} else if !hidden.is_empty() && holds {
(
Some(self.export_ids(module, class, name, at, glob, meter)?),
true,
)
} else {
if fresh && !hidden.is_empty() {
let site = self.globs.views[view].site;
self.note_dropped(view, name.clone(), at, site, meter)?;
}
(None, !hidden.is_empty())
};
if hide {
self.globs.views[view].hidden = true;
}
Ok(passed)
}
fn hides_nothing(
&self,
module: usize,
view: usize,
name: &SharedStr,
at: usize,
glob: usize,
meter: &Meter,
) -> Result<bool, LoadError> {
let own = self.globs.views[view].unseen();
let again = self
.globs
.holding
.get(name.as_str())
.map_or(0, Vec::len)
.min(self.reads_of(module).len());
if own.hiding.len() >= again {
return Ok(false);
}
let steps = 1 + own.hiding.len();
tally::add(Work::HiddenChecks, steps);
self.charge_steps(steps, glob, meter)?;
Ok(!own.dropped.contains(&(name.clone(), at))
&& own.hiding.iter().all(|source| {
self.globs.views[*source]
.names
.get(name.as_str())
.is_none_or(|lists| lists[at].is_empty())
}))
}
pub(crate) fn record_glob_edge(
&mut self,
glob: usize,
module: usize,
target: usize,
meter: &Meter,
) -> Result<(), LoadError> {
let decl = &self.uses[glob];
if self.import_reach.reaches.is_empty() {
meter.globs(
self.modules.len() * (vec_slot::<bool>() + vec_slot::<BTreeSet<usize>>())
+ vec_first::<bool>()
+ vec_first::<BTreeSet<usize>>(),
&decl.file,
Some(decl.line),
)?;
let mut reaches = vec![false; self.modules.len()];
for position in &self.named_imports {
reaches[self.uses[*position].module] = true;
}
self.import_reach.reaches = reaches;
self.import_reach.globbed_by = vec![BTreeSet::new(); self.modules.len()];
}
if self.import_reach.globbed_by[target].contains(&module) {
return Ok(());
}
meter.globs(
btree_map::<usize, ()>() + btree_entry::<usize, ()>(),
&decl.file,
Some(decl.line),
)?;
self.import_reach.globbed_by[target].insert(module);
if !self.import_reach.reaches[target] {
return Ok(());
}
let memory = Transient::new(meter);
let steps = Steps::LoadAt {
memory: &memory,
file: &decl.file,
line: decl.line,
};
let mut work = WorkList::<_, 8>::new();
push_work(&mut work, module, steps)?;
while let Some(next) = work.pop() {
if !std::mem::replace(&mut self.import_reach.reaches[next], true) {
for &reader in &self.import_reach.globbed_by[next] {
push_work(&mut work, reader, steps)?;
}
}
}
Ok(())
}
pub(crate) fn reaches_import(&self, module: usize) -> bool {
self.import_reach
.reaches
.get(module)
.is_none_or(|reaches| *reaches)
}
}
fn holder_spans(
dominator: &[usize],
step: &mut dyn FnMut(usize) -> Result<(), LoadError>,
storage: Steps<'_>,
) -> Result<Vec<(usize, usize)>, LoadError> {
let mut children: Vec<Vec<usize>> = vec![Vec::new(); dominator.len()];
for (node, parent) in dominator.iter().enumerate().skip(1) {
if *parent != NONE {
children[*parent].push(node);
}
}
let mut span = vec![(0, 0); dominator.len()];
let mut position = 0;
let mut walk = WorkList::<_, 8>::new();
push_work(&mut walk, (0, 0), storage)?;
while let Some((node, child)) = walk.pop() {
if child == 0 {
span[node].0 = position;
position += 1;
}
if let Some(&next) = children[node].get(child) {
step(1)?;
push_work(&mut walk, (node, child + 1), storage)?;
push_work(&mut walk, (next, 0), storage)?;
} else {
span[node].1 = position;
position += 1;
}
}
Ok(span)
}
fn dominators(
successors: &[Vec<usize>],
predecessors: &[Vec<usize>],
step: &mut dyn FnMut(usize) -> Result<(), LoadError>,
storage: Steps<'_>,
) -> Result<Vec<usize>, LoadError> {
let count = successors.len();
let mut number = vec![NONE; count];
let mut vertex: Vec<usize> = Vec::with_capacity(count);
let mut parent = vec![NONE; count];
step(1)?;
let mut walk = WorkList::<_, 8>::new();
push_work(&mut walk, (0, NONE), storage)?;
while let Some((node, from)) = walk.pop() {
if number[node] != NONE {
continue;
}
step(1)?;
number[node] = vertex.len();
vertex.push(node);
parent[node] = from;
for &to in successors[node].iter().rev() {
if number[to] == NONE {
step(1)?;
push_work(&mut walk, (to, node), storage)?;
}
}
}
let mut semi: Vec<usize> = number.clone();
let mut ancestor = vec![NONE; count];
let mut label: Vec<usize> = (0..count).collect();
let mut dominator = vec![NONE; count];
let mut bucket: Vec<Vec<usize>> = vec![Vec::new(); count];
let mut path = WorkList::<_, 8>::new();
let mut eval = |node: usize,
ancestor: &mut Vec<usize>,
label: &mut Vec<usize>,
semi: &[usize],
step: &mut dyn FnMut(usize) -> Result<(), LoadError>|
-> Result<usize, LoadError> {
step(1)?;
if ancestor[node] == NONE {
return Ok(node);
}
let mut at = node;
while ancestor[ancestor[at]] != NONE {
step(1)?;
push_work(&mut path, at, storage)?;
at = ancestor[at];
}
while !path.is_empty() {
step(1)?;
let at = path.pop().expect("the compression path is nonempty");
let up = ancestor[at];
if semi[label[up]] < semi[label[at]] {
label[at] = label[up];
}
ancestor[at] = ancestor[up];
}
Ok(label[node])
};
for &node in vertex.iter().skip(1).rev() {
for &from in &predecessors[node] {
step(1)?;
if number[from] == NONE {
continue;
}
let least = eval(from, &mut ancestor, &mut label, &semi, step)?;
if semi[least] < semi[node] {
semi[node] = semi[least];
}
}
step(1)?;
bucket[vertex[semi[node]]].push(node);
let up = parent[node];
ancestor[node] = up;
for waiting in std::mem::take(&mut bucket[up]) {
step(1)?;
let least = eval(waiting, &mut ancestor, &mut label, &semi, step)?;
dominator[waiting] = if semi[least] < semi[waiting] {
least
} else {
up
};
}
}
for &node in vertex.iter().skip(1) {
step(1)?;
if dominator[node] != vertex[semi[node]] {
dominator[node] = dominator[dominator[node]];
}
}
Ok(dominator)
}
#[cfg(test)]
#[path = "../tests/support/shapes/globs.rs"]
#[expect(
dead_code,
reason = "the unit tests build the shapes; the examples also resolve their paths"
)]
mod shapes;
#[cfg(test)]
mod equivalence;
#[cfg(test)]
mod incremental;
#[cfg(test)]
mod lookups;
#[cfg(test)]
mod delivery;
#[cfg(test)]
mod tests {
use std::fmt::Write as _;
use crate::work::{Work, measure_kind};
use crate::{MemoryTree, Namespace, Workspace};
const UNIT: usize = 40;
#[test]
fn holder_visibility_uses_ancestry_instead_of_sibling_depth() {
let tree: MemoryTree = [
("Cargo.toml", DEMO),
("src/lib.rs", "pub mod a { pub mod child {} } pub mod b {}"),
]
.into_iter()
.collect();
let ws = Workspace::load(&tree, &["."]).expect("loads");
let index = ws.index();
let module = |path: &str| {
index
.modules
.iter()
.position(|module| module.path == path)
.expect("module")
};
let a = super::Level::within(module("demo::a"));
let child = super::Level::within(module("demo::a::child"));
let b = super::Level::within(module("demo::b"));
let covers = |offered, required| {
index
.level_covers(offered, required, &mut |_| Ok(()))
.expect("unlimited work")
};
assert!(covers(a, child));
assert!(!covers(child, a));
assert!(!covers(a, b));
assert!(!covers(b, child));
assert!(covers(super::Level::PUBLIC, child));
assert!(!covers(child, super::Level::PUBLIC));
assert!(!covers(super::Level::NOBODY, child));
assert!(!covers(a, super::Level::NOBODY));
assert!(covers(a.companion(), child));
}
#[test]
fn named_supplier_levels_stay_with_the_declaration_that_provides_them() {
let tree: MemoryTree = [
("Cargo.toml", DEMO),
(
"src/lib.rs",
"pub mod d { pub struct B {} }\n\
pub mod a { pub use crate::d::B; }\n\
pub mod b { pub use crate::d::B; }\n\
pub mod c {\n\
#[cfg(feature = \"first\")] use crate::a::B;\n\
#[cfg(not(feature = \"first\"))] pub use crate::b::B;\n\
}\n\
pub mod g { pub use crate::d::*; }\n",
),
]
.into_iter()
.collect();
let ws = Workspace::load(&tree, &["."]).expect("loads both configuration alternatives");
let index = ws.index();
let module = |path: &str| {
index
.modules
.iter()
.position(|module| module.path == path)
.expect("module")
};
let id = index
.items
.iter()
.find(|item| item.path == "demo::d::B")
.expect("defined item")
.id;
let meter = crate::meter::Meter::new(&crate::LoadOptions::default());
let supply = index
.supply(&meter, index.glob_imports[0])
.expect("admitted routes");
let c = module("demo::c");
for (source, expected) in [
("demo::a", super::Level::within(c)),
("demo::b", super::Level::PUBLIC),
] {
let routes = &supply.named[&(
id,
(
module(source),
"B".into(),
crate::settle::slot(Namespace::Type),
),
)];
assert_eq!(
routes,
&[(
(c, "B".into(), crate::settle::slot(Namespace::Type)),
expected
)]
);
}
}
#[test]
fn native_resumed_growth_admits_overlapping_buffers_before_mutation() {
use crate::meter::{Meter, Steps, Transient};
use crate::{Budget, LoadErrorKind, LoadOptions, RelPath};
let file = RelPath::new("src/imports.rs").expect("path");
let run = |limit| {
let meter = Meter::new(&LoadOptions {
max_glob_bytes: limit,
..LoadOptions::default()
});
let memory = Transient::new(&meter);
memory.charge(7, &file, Some(2)).expect("unrelated payload");
let steps = Steps::LoadAt {
memory: &memory,
file: &file,
line: 13,
};
let mut values: Vec<usize> = Vec::new();
let mut refused = false;
for value in 0..5 {
match super::reserve_next(&mut values, steps) {
Ok(()) => values.push(value),
Err(error) => {
assert_eq!(values, [0, 1, 2, 3]);
assert_eq!(
(error.file.as_str(), error.line),
("src/imports.rs", Some(13))
);
assert!(matches!(error.kind, LoadErrorKind::Budget {
budget: Budget::GlobBytes, limit: found,
} if found == limit));
refused = true;
break;
}
}
}
if !refused {
assert_eq!(values, [0, 1, 2, 3, 4]);
}
(refused, meter.usage().glob_bytes)
};
let (refused, peak) = run(usize::MAX);
assert!(!refused);
assert!(!run(peak).0);
assert!(run(peak - 1).0);
}
const CEILING: usize = 400 * UNIT;
const DEMO: &str = "[package]\nname = \"demo\"\nversion = \"0.1.0\"\nedition = \"2024\"\n";
const BASE: &str = "pub mod d { pub struct X {} }\npub mod p { pub struct X {} }\n";
fn chain(n: usize, extra: &str, more: &dyn Fn(usize) -> String) -> String {
let mut lib = String::from(BASE);
writeln!(lib, "pub mod c0 {{ pub use crate::d::*; {extra} }}").expect("write");
for i in 1..n {
writeln!(lib, "pub mod c{i} {{ pub use crate::c{}::*; }}", i - 1).expect("write");
}
for i in 0..n {
writeln!(
lib,
"pub mod a{i} {{ pub use crate::r{i}::*; use crate::p::*; }}"
)
.expect("write");
writeln!(
lib,
"pub mod r{i} {{ pub use crate::a{i}::*; pub use crate::c{}::*; {} }}",
n - 1,
more(i)
)
.expect("write");
}
lib
}
#[test]
fn independent_same_item_supply_preserves_the_carriers_ambiguity() {
let lib = format!(
"{BASE}pub mod a {{ pub use crate::d::*; use crate::p::*; }}\n\
pub mod c {{ pub use crate::d::*; }}\n\
pub mod r0 {{ pub use crate::a::*; pub use crate::c::*; }}\n"
);
let tree: MemoryTree = [("Cargo.toml", DEMO), ("src/lib.rs", lib.as_str())]
.into_iter()
.collect();
let ws = Workspace::load(&tree, &["."]).expect("loads");
let Err(crate::ResolveError::Ambiguous(ids)) =
ws.resolve_from_in("demo::r0", "self::X", Namespace::Type)
else {
panic!("the independently supplied carrier must remain ambiguous");
};
let mut paths: Vec<_> = ids
.iter()
.map(|id| ws.index().items[id.0].path.as_str())
.collect();
paths.sort_unstable();
assert_eq!(paths, ["demo::d::X", "demo::p::X"]);
}
fn plain(n: usize) -> String {
chain(n, "", &|_| String::new())
}
fn fan_in(n: usize) -> String {
let mut readers = String::new();
for i in 0..n {
write!(readers, "pub use crate::r{i}::*; ").expect("write");
}
chain(n, &readers, &|_| String::new())
}
fn nested(n: usize) -> String {
chain(n, "", &|i| {
if i == 0 {
String::new()
} else {
format!("pub use crate::r{}::*;", i - 1)
}
})
}
fn counted(lib: &str) -> (usize, String) {
let tree: MemoryTree = [("Cargo.toml", DEMO), ("src/lib.rs", lib)]
.into_iter()
.collect();
let (ws, tally) = measure_kind(Work::SupplySteps, CEILING, || {
Workspace::load(&tree, &["."]).unwrap_or_else(|e| panic!("{e}"))
});
let found = ws
.resolve_from_in("demo::r0", "self::X", Namespace::Type)
.map_or_else(|e| format!("{e:?}"), |found| found.path);
let steps = tally.get(Work::SupplySteps);
assert!(
ws.usage().work >= steps,
"{} steps of work for {steps} of the search",
ws.usage().work
);
(steps, found)
}
fn assert_linear(build: &dyn Fn(usize) -> String) {
let counts = [1, 2, 3].map(|units| {
let (count, found) = counted(&build(units * UNIT));
assert_eq!(found, "demo::d::X");
count
});
let [one, two, three] = counts;
assert!(one > 0, "the search counted nothing: {counts:?}");
assert!(
three + one <= 2 * two,
"the search grows faster than the chain: {counts:?}"
);
}
#[test]
fn the_holders_of_an_item_apart_from_each_reader_of_a_chain_of_globs_are_found_in_steps_linear_in_the_chain()
{
assert_linear(&plain);
}
#[test]
fn the_holders_of_an_item_apart_from_readers_the_start_of_the_chain_globs_back_are_found_in_steps_linear_in_the_chain()
{
assert_linear(&fan_in);
}
#[test]
fn the_holders_of_an_item_apart_from_readers_that_form_a_chain_of_their_own_are_found_in_steps_linear_in_the_chains()
{
assert_linear(&nested);
}
#[test]
fn a_read_that_holds_no_companion_starts_no_search_for_the_holders_of_its_items() {
let mut lib = String::from(BASE);
lib.push_str(
"pub mod a { pub use crate::d::*; use crate::p::*; }\n\
pub mod e { pub struct X {} }\npub mod e1 { pub use crate::e::*; }\n\
pub mod e2 { pub use crate::e::*; }\n",
);
for i in 0..3 * UNIT {
writeln!(
lib,
"pub mod r{i} {{ pub use crate::a::*; pub use crate::e1::*; pub use crate::e2::*; }}"
)
.expect("write");
}
let (count, found) = counted(&lib);
assert_eq!(count, 0);
assert!(found.starts_with("Ambiguous"), "{found}");
}
fn dominates_by(dominator: &[usize], ruler: usize, node: usize) -> bool {
let mut at = node;
loop {
if at == ruler {
return true;
}
if at == 0 || dominator[at] == super::NONE {
return false;
}
at = dominator[at];
}
}
fn reached_without(successors: &[Vec<usize>], left_out: Option<usize>, node: usize) -> bool {
let mut seen = vec![false; successors.len()];
let mut work = purrdf_lex::walk::WorkList::<_, 8>::new();
super::push_work(&mut work, 0, super::Steps::Load).expect("test stack");
while let Some(at) = work.pop() {
if Some(at) == left_out || seen[at] {
continue;
}
seen[at] = true;
for &next in &successors[at] {
super::push_work(&mut work, next, super::Steps::Load).expect("test stack");
}
}
seen[node]
}
fn check_dominators(successors: &[Vec<usize>]) -> Vec<usize> {
let mut predecessors = vec![Vec::new(); successors.len()];
for (node, next) in successors.iter().enumerate() {
for &to in next {
predecessors[to].push(node);
}
}
let dominator = super::dominators(
successors,
&predecessors,
&mut |_| Ok(()),
super::Steps::Load,
)
.unwrap_or_else(|e| panic!("{e}"));
for node in 0..successors.len() {
if !reached_without(successors, None, node) {
assert_eq!(dominator[node], super::NONE, "{successors:?}: {node}");
continue;
}
for ruler in 0..successors.len() {
let expected = ruler == node || !reached_without(successors, Some(ruler), node);
assert_eq!(
dominates_by(&dominator, ruler, node),
expected,
"{successors:?}: does {ruler} dominate {node}"
);
}
}
dominator
}
#[test]
fn the_dominators_of_small_holder_graphs_follow_their_definition() {
let dominator = check_dominators(&[vec![1, 2], vec![3], vec![3], vec![]]);
assert_eq!(dominator[3], 0);
let dominator = check_dominators(&[vec![1], vec![2], vec![1, 3], vec![]]);
assert_eq!((dominator[2], dominator[3]), (1, 2));
let dominator = check_dominators(&[vec![1], vec![1, 2], vec![]]);
assert_eq!(dominator[2], 1);
let dominator = check_dominators(&[vec![1], vec![], vec![1]]);
assert_eq!(dominator[2], super::NONE);
let dominator = check_dominators(&[vec![1, 1], vec![2, 2], vec![]]);
assert_eq!(dominator[2], 1);
let dominator = check_dominators(&[vec![1, 4], vec![2], vec![3], vec![1], vec![3]]);
assert_eq!((dominator[2], dominator[3]), (1, 0));
}
#[test]
fn the_dominators_of_seeded_random_graphs_follow_their_definition() {
let mut state: u64 = 0x5eed_0f00_d000_0014;
let mut next = move |bound: usize| {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
usize::try_from(state % u64::try_from(bound).expect("small")).expect("small")
};
for _ in 0..400 {
let count = 2 + next(8);
let edges = next(3 * count);
let mut successors: Vec<Vec<usize>> = vec![Vec::new(); count];
for _ in 0..edges {
let from = next(count);
let to = 1 + next(count - 1);
successors[from].push(to);
}
check_dominators(&successors);
}
}
}
#[cfg(test)]
mod work_budget {
use std::fmt::Write as _;
use super::shapes::{
MANIFEST as DEMO, ambiguous_hub, chain, companion_fan_in, holder_scan, hub, lookups,
many_items, prelude, private_fan_in, pub_fan_in,
};
use crate::meter::charges;
use crate::{Budget, LoadError, LoadErrorKind, LoadOptions, MemoryTree, Workspace};
fn load(lib: &str, max_work: usize) -> Result<Workspace, LoadError> {
let tree: MemoryTree = [("Cargo.toml", DEMO), ("src/lib.rs", lib)]
.into_iter()
.collect();
let options = LoadOptions {
max_work,
..LoadOptions::default()
};
Workspace::load_with(&tree, &["."], &options)
}
fn work(lib: &str) -> usize {
load(lib, Budget::Work.limit())
.unwrap_or_else(|error| panic!("loads: {error}"))
.usage()
.work
}
#[test]
fn an_export_read_charges_each_visited_read_and_holder_before_returning_its_answer() {
use crate::meter::Meter;
use crate::work::{Work, measure};
for unrelated in [0, 8] {
let mut lib = String::from("pub mod d { pub struct X {} }\n");
for i in 0..unrelated {
writeln!(lib, "pub mod e{i} {{ pub struct Y{i} {{}} }}").expect("write");
}
lib.push_str("pub mod t { pub use crate::d::*;\n");
for i in 0..unrelated {
writeln!(lib, "pub use crate::e{i}::*;").expect("write");
}
lib.push_str("}\n");
let workspace = load(&lib, Budget::Work.limit()).expect("loads");
let index = workspace.index();
let target = index
.modules
.iter()
.position(|m| m.path == "demo::t")
.expect("target");
let root = index
.modules
.iter()
.position(|m| m.path == "demo")
.expect("root");
let class = index.class_for(target, root);
let site = index.reads_of(target)[0].glob;
let read = |limit| {
let meter = Meter::new(&LoadOptions {
max_work: limit,
..LoadOptions::default()
});
let (answer, tally) = measure(usize::MAX, || {
index.export_ids(target, &class, "X", 0, site, &meter)
});
(answer, tally, meter.usage().work)
};
let (answer, tally, spent) = read(usize::MAX);
let answer = answer.expect("export succeeds");
assert_eq!(answer.len(), 1);
assert_eq!(index.items[answer[0].0.0].path, "demo::d::X");
assert!(tally.get(Work::RecomputedReads) > 0);
assert_eq!(tally.get(Work::HolderScans) > 0, unrelated > 0);
assert_eq!(
spent,
tally.get(Work::RecomputedReads)
+ tally.get(Work::HolderScans)
+ tally.get(Work::CandidateSteps)
);
assert_eq!(read(spent).0.expect("exact budget"), answer);
let error = read(spent - 1).0.expect_err("one step less");
assert!(
matches!(error.kind, LoadErrorKind::Budget {
budget: Budget::Work, limit
} if limit == spent - 1),
"{error}"
);
}
}
#[test]
fn a_new_view_charges_raw_reads_and_unique_source_names_before_gathering() {
use crate::meter::Meter;
use crate::work::{Work, measure};
let workspace = load(
"pub mod d { pub struct X {} pub struct Z {} }\n\
pub mod t { pub fn own() {} pub use crate::d::*; pub use crate::d::*; }\n",
Budget::Work.limit(),
)
.expect("loads");
let mut index = workspace.index().clone();
let target = index
.modules
.iter()
.position(|m| m.path == "demo::t")
.expect("target");
let root = index
.modules
.iter()
.position(|m| m.path == "demo")
.expect("root");
assert_eq!(index.exports_of(target), []);
let class = index.class_for(target, root);
let reads = index.reads_of(target);
assert_eq!(reads.len(), 2);
assert_eq!(reads[0].view, reads[1].view);
let site = reads[0].glob;
let listed = reads.len();
let names = index.scopes[target].len() + index.globs.views[reads[0].view].names.len();
assert_eq!((listed, names), (2, 3));
let meter = Meter::new(&LoadOptions::default());
let (view, tally) = measure(usize::MAX, || index.make_view(target, &class, site, &meter));
let view = &index.globs.views[view.expect("new view")];
assert_eq!(view.names.len(), 3);
for view in &index.globs.views {
for name in view.names.keys() {
let canonical = index
.globs
.strings
.get(name.as_ref())
.expect("interned name");
assert!(std::ptr::eq(name.as_ref(), canonical.as_ref()));
}
}
for (name, expected) in [
("X", "demo::d::X"),
("Z", "demo::d::Z"),
("own", "demo::t::own"),
] {
let held = view.names[name].iter().flatten().collect::<Vec<_>>();
assert_eq!(held.len(), 1);
assert_eq!(index.items[held[0].0.0].path, expected);
}
assert_eq!(
meter.usage().work,
listed + names + tally.get(Work::CandidateSteps)
);
}
type Shape = (&'static str, fn(usize) -> String, usize);
const SHAPES: [Shape; 10] = [
("chain", chain, 20),
("many items", many_items, 20),
("fan-in of pub globs", pub_fan_in, 20),
("fan-in of private globs", private_fan_in, 20),
("companion fan-in", companion_fan_in, 20),
("prelude", prelude, 34),
("hub", hub, 43),
("ambiguous hub", ambiguous_hub, 43),
("lookups", lookups, 44),
("holder scan", holder_scan, 43),
];
#[test]
fn each_shape_loads_at_its_measured_work_and_refuses_one_step_less() {
for (shape, build, _) in SHAPES {
for n in [8, 16, 24, 32] {
let lib = build(n);
let workspace = load(&lib, Budget::Work.limit()).expect("loads");
let spent = workspace.usage().work;
assert!(spent > 0, "{shape} of {n}");
let exact = load(&lib, spent).expect("exact budget");
assert_eq!(exact.usage(), workspace.usage(), "{shape} of {n}");
let error = load(&lib, spent - 1).expect_err("one step less");
assert!(
matches!(error.kind, LoadErrorKind::Budget {
budget: Budget::Work, limit
} if limit == spent - 1),
"{shape} of {n}: {error}"
);
assert_eq!(error.file.as_str(), "src/lib.rs");
let line = error.line.expect("responsible import");
assert!(
lib.lines()
.nth(line - 1)
.is_some_and(|text| text.contains("use ")),
"{shape} of {n}: {error}"
);
}
}
}
#[test]
fn doubling_a_shape_keeps_actual_work_within_its_growth_bound() {
let mut failures = Vec::new();
for (shape, build, bound) in SHAPES {
let measured =
[32, 64, 128].map(|n| crate::work::measure(usize::MAX, || work(&build(n))));
let [one, two, four] = measured.map(|(work, _)| work);
assert!(
one > 0 && two > one && four > two,
"{shape}: {one}, {two}, {four}"
);
let (small, large) = (two - one, four - two);
if large * 10 > small * bound {
failures.push(format!(
"{shape}: {small} then {large}, upper bound {bound}/10; {measured:?}"
));
}
}
assert!(failures.is_empty(), "{}", failures.join("\n"));
}
#[test]
fn actual_work_from_100_to_800_stays_within_each_shapes_doubling_bound() {
for (shape, build, bound) in SHAPES {
let sizes = if shape == "holder scan" {
[25, 50, 100, 200]
} else {
[100, 200, 400, 800]
};
let counts = sizes.map(|n| work(&build(n)));
assert!(
counts[0] > 0 && counts.windows(2).all(|pair| pair[1] > pair[0]),
"{shape}: {counts:?}"
);
let increments: Vec<_> = counts.windows(2).map(|pair| pair[1] - pair[0]).collect();
for pair in increments.windows(2) {
assert!(
pair[1] * 10 <= pair[0] * bound,
"{shape}: {counts:?}, upper bound {bound}/10"
);
}
}
}
#[test]
fn holder_scan_sources_beyond_the_admitted_growth_sizes_are_refused() {
let tokens = load(&holder_scan(400), Budget::Work.limit()).expect_err("token budget");
assert!(
matches!(tokens.kind, LoadErrorKind::Budget {
budget: Budget::FileTokens, limit
} if limit == Budget::FileTokens.limit()),
"{tokens}"
);
let bytes = load(&holder_scan(800), Budget::Work.limit()).expect_err("file byte budget");
assert!(
matches!(bytes.kind, LoadErrorKind::Tree(ref source)
if matches!(source.as_ref(), crate::TreeError::TooLarge { limit, .. }
if *limit == crate::DEFAULT_MAX_FILE_BYTES)),
"{bytes}"
);
}
#[test]
fn a_settle_heavy_shape_is_refused_at_the_charge_that_passes_a_small_limit() {
for (shape, lib) in [
("fan-in", private_fan_in(32)),
("prelude", prelude(32)),
("hub", hub(32)),
("holder scan", holder_scan(16)),
] {
charges::take();
let total = work(&lib);
let all = charges::take();
assert_eq!(all.iter().sum::<usize>(), total, "{shape}");
let (mut limit, mut place) = (0, 0);
while limit < total / 10 || all[place] == 0 {
limit += all[place];
place += 1;
}
let error = load(&lib, limit).expect_err("over the limit");
assert!(
matches!(
error.kind,
LoadErrorKind::Budget {
budget: Budget::Work,
limit: refused
} if refused == limit
),
"{shape}: {error}"
);
assert_eq!(error.file.as_str(), "src/lib.rs", "{shape}");
let line = error.line.expect("the line of a glob");
assert!(
lib.lines()
.nth(line - 1)
.is_some_and(|text| text.contains("::*;")),
"{shape}: {line}"
);
let made = charges::take();
assert_eq!(made, all[..=place], "{shape}");
let spent: usize = made.iter().sum();
assert_eq!(spent, limit + all[place], "{shape}");
assert!(spent < total, "{shape}: {spent} of {total}");
}
}
}
#[cfg(test)]
mod settling {
use super::shapes::{
MANIFEST, ambiguous_hub, chain, companion_fan_in, holder_scan, hub, lookups, many_items,
prelude, private_fan_in, pub_fan_in,
};
use crate::work::{Work, measure};
use crate::{MemoryTree, Workspace};
const N: usize = 8;
const KINDS: [Work; 11] = [
Work::Recomputations,
Work::RecomputedReads,
Work::DropReads,
Work::ListCopies,
Work::LookupReads,
Work::LookupRoutes,
Work::HolderScans,
Work::CovertChecks,
Work::Deltas,
Work::Exposures,
Work::HiddenChecks,
];
type Pin = [fn(usize) -> usize; 11];
const fn none(_n: usize) -> usize {
0
}
fn counted(lib: &str) -> [usize; 11] {
let tree: MemoryTree = [("Cargo.toml", MANIFEST), ("src/lib.rs", lib)]
.into_iter()
.collect();
let (_, tally) = measure(usize::MAX, || {
Workspace::load(&tree, &["."]).unwrap_or_else(|error| panic!("loads: {error}"))
});
KINDS.map(|work| tally.get(work))
}
fn assert_pinned(shape: &str, build: fn(usize) -> String, pin: Pin) -> [[usize; 11]; 3] {
[1, 2, 3].map(|units| {
let n = units * N;
let counts = counted(&build(n));
let expected = pin.map(|count| count(n));
assert_eq!(counts, expected, "{shape} of {n}: {KINDS:?}");
counts
})
}
fn assert_one_replay_omitted(
shape: &str,
build: fn(usize) -> String,
pin: Pin,
) -> [[usize; 11]; 3] {
[1, 2, 3].map(|units| {
let n = units * N;
let lib = build(n);
let tree: MemoryTree = [("Cargo.toml", MANIFEST), ("src/lib.rs", lib.as_str())]
.into_iter()
.collect();
let (ws, actual) = measure(usize::MAX, || {
Workspace::load(&tree, &["."]).expect("fixed-path load")
});
let mut index = ws.index().clone();
index.lookups.built(false);
let meter = crate::meter::Meter::new(&crate::LoadOptions::default());
let decl = &index.uses[index.glob_imports[0]];
meter
.globs(index.globs.charged, &decl.file, Some(decl.line))
.expect("resident cloned tables fit");
let ((), replay) = measure(usize::MAX, || {
index
.replay_globs_for_measurement(&meter)
.expect("one actual replay");
});
let counts = KINDS.map(|kind| actual.get(kind));
let with_replay = KINDS.map(|kind| actual.get(kind) + replay.get(kind));
assert_eq!(
with_replay,
pin.map(|count| count(n)),
"{shape} of {n}: actual + one replay; {KINDS:?}"
);
assert!(
replay.get(Work::CovertChecks) > 0,
"the omitted replay has real work"
);
counts
})
}
fn second_difference([one, two, three]: [usize; 3]) -> isize {
let [one, two, three] =
[one, two, three].map(|count| isize::try_from(count).expect("a small count"));
three - 2 * two + one
}
fn of(counts: &[[usize; 11]; 3], work: Work) -> [usize; 3] {
let place = KINDS
.iter()
.position(|kind| *kind == work)
.expect("a pinned kind");
counts.map(|at| at[place])
}
#[test]
fn the_settling_of_a_chain_of_globs_counts_its_pinned_polynomials_at_n_2n_and_3n() {
assert_pinned("chain", chain, [none; 11]);
}
#[test]
fn the_settling_of_a_module_of_many_items_globbed_from_many_modules_counts_its_pinned_polynomials_at_n_2n_and_3n()
{
assert_pinned("many items", many_items, [none; 11]);
}
#[test]
fn the_settling_of_a_fan_in_of_pub_globs_counts_its_pinned_polynomials_at_n_2n_and_3n() {
assert_pinned("fan-in of pub globs", pub_fan_in, [none; 11]);
}
#[test]
fn the_settling_of_a_fan_in_of_private_globs_counts_its_pinned_polynomials_at_n_2n_and_3n() {
assert_pinned("fan-in of private globs", private_fan_in, [none; 11]);
}
#[test]
fn a_companion_fan_in_keeps_each_operation_population_linear_without_list_copies() {
let counts = [1, 2, 3].map(|units| counted(&companion_fan_in(units * N)));
for work in KINDS {
assert_eq!(second_difference(of(&counts, work)), 0, "{work:?}");
}
for work in [
Work::Recomputations,
Work::RecomputedReads,
Work::DropReads,
Work::HolderScans,
Work::CovertChecks,
Work::Exposures,
] {
assert!(of(&counts, work).iter().all(|count| *count > 0), "{work:?}");
}
assert_eq!(of(&counts, Work::ListCopies), [0; 3]);
}
#[test]
fn a_reading_again_looks_at_the_reads_whose_view_holds_the_name_whatever_the_reads_of_the_module()
{
for n in [100, 200, 400] {
let private = counted(&private_fan_in(n));
assert_eq!(
[private[0], private[1]],
[0, 0],
"fan-in of private globs of {n}"
);
let carried = counted(&companion_fan_in(n));
let [recomputed, reads, drops, _, _, _, scans, ..] = carried;
assert!(recomputed > 0 && reads > 0 && scans > 0);
assert!(reads <= 2 * recomputed, "{n}: {carried:?}");
assert!(scans <= 4 * (recomputed + drops), "{n}: {carried:?}");
}
}
#[test]
fn the_settling_of_the_prelude_pattern_counts_its_pinned_polynomials_at_n_2n_and_3n() {
let counts = assert_one_replay_omitted(
"prelude",
prelude,
[
none,
none,
none,
none,
none,
none,
none,
|n| 8 * n - 5,
none,
none,
none,
],
);
assert_eq!(second_difference(of(&counts, Work::CovertChecks)), 0);
}
#[test]
fn the_settling_of_a_hub_counts_its_pinned_polynomials_at_n_2n_and_3n() {
let counts = assert_one_replay_omitted(
"hub",
hub,
[
none,
none,
none,
none,
none,
none,
none,
|n| n * n,
|n| n * n - 2 * n,
none,
none,
],
);
for work in [Work::CovertChecks, Work::Deltas] {
assert_eq!(
2 * second_difference(of(&counts, work)),
2 * 8 * 8,
"{work:?}"
);
}
}
#[test]
fn a_companion_hub_keeps_local_definitions_and_reads_without_copying_candidate_lists() {
for n in [8, 16, 24] {
let lib = ambiguous_hub(n);
let tree: MemoryTree = [("Cargo.toml", MANIFEST), ("src/lib.rs", lib.as_str())]
.into_iter()
.collect();
let (workspace, tally) = measure(usize::MAX, || {
Workspace::load(&tree, &["."]).expect("loads")
});
for sibling in 0..n {
let path = format!("demo::s{sibling}::T{}", sibling / 2);
assert_eq!(
workspace.resolve(&path).expect("local definition").path,
path
);
}
assert!(tally.get(Work::RecomputedReads) > 0);
assert!(tally.get(Work::DropReads) > 0);
assert_eq!(tally.get(Work::ListCopies), 0);
}
}
#[test]
fn a_companion_hub_bounds_delivery_and_carrier_graph_growth_together() {
let kinds = [
Work::Recomputations,
Work::RecomputedReads,
Work::DropReads,
Work::ListCopies,
Work::HolderScans,
Work::CovertChecks,
Work::Deltas,
Work::SupplySteps,
Work::CandidateSteps,
Work::SettleSteps,
Work::ProofReads,
Work::ProofCopies,
Work::ProofSteps,
];
let counts = [8, 16, 24, 32].map(|n| {
let lib = ambiguous_hub(n);
let tree: MemoryTree = [("Cargo.toml", MANIFEST), ("src/lib.rs", lib.as_str())]
.into_iter()
.collect();
let (workspace, tally) = measure(usize::MAX, || {
Workspace::load(&tree, &["."]).expect("loads")
});
let counts = kinds.map(|kind| tally.get(kind));
eprintln!(
"n = {n}: {kinds:?} = {counts:?}; charged work = {}",
workspace.usage().work
);
(counts, workspace.usage().work)
});
for (at, kind) in kinds.into_iter().enumerate() {
if matches!(
kind,
Work::ProofReads | Work::ProofCopies | Work::ProofSteps
) {
assert!(counts[1].0[at] > 0, "actual constructive work: {kind:?}");
}
assert!(
counts[3].0[at] * 10 <= counts[1].0[at] * 43,
"{kind:?}: {counts:?}"
);
}
assert!(
counts[3].1 * 10 <= counts[1].1 * 43,
"whole charged work: {counts:?}"
);
}
#[test]
fn named_import_lookup_routes_stay_linear_and_read_work_stays_quadratic() {
let sizes = [8, 16, 32];
let counts = sizes.map(|n| counted(&lookups(n)));
for (n, counts) in sizes.into_iter().zip(counts) {
for (kind, count) in KINDS.into_iter().zip(counts) {
match kind {
Work::LookupReads => assert!(count > 0),
Work::LookupRoutes => {
let routes = if cfg!(debug_assertions) { 17 } else { 15 };
assert_eq!(count, routes * n);
}
_ => assert_eq!(count, 0, "{kind:?}"),
}
}
}
let reads = counts.map(|counts| counts[4]);
assert!(reads[0] > 0 && reads[1] > reads[0] && reads[2] > reads[1]);
assert!(
(reads[2] - reads[1]) * 10 <= (reads[1] - reads[0]) * 44,
"{reads:?}"
);
}
#[test]
fn the_settling_of_a_module_whose_names_many_views_hold_counts_its_pinned_polynomials_at_n_2n_and_3n()
{
let counts = assert_one_replay_omitted(
"module whose names many views hold",
holder_scan,
[
none,
none,
none,
none,
none,
none,
none,
|n| 2 * n,
none,
none,
|n| 8 * n * n,
],
);
assert_eq!(
2 * second_difference(of(&counts, Work::HiddenChecks)),
8 * 2 * 8 * 8
);
}
}
#[cfg(test)]
mod monotone {
use super::{Held, Index, Level};
use crate::item::ItemId;
use crate::meter::Meter;
use crate::options::LoadOptions;
use crate::{MemoryTree, Workspace};
fn viewed() -> (Index, Meter, usize) {
let tree: MemoryTree = [
(
"Cargo.toml",
"[package]\nname = \"demo\"\nversion = \"0.1.0\"\nedition = \"2021\"\n",
),
(
"src/lib.rs",
"pub mod d { pub struct X; }\npub mod a { pub use crate::d::*; }\n",
),
]
.into_iter()
.collect();
let mut index = Workspace::load(&tree, &["."])
.expect("loads")
.index()
.clone();
let meter = Meter::new(&LoadOptions::default());
index.clear_globs();
index.globs.exports = vec![Vec::new(); index.modules.len()];
index.globs.reads = vec![Vec::new(); index.modules.len()];
let site = *index.glob_imports.first().expect("a glob import");
let view = index
.make_view(0, &[true], site, &meter)
.expect("the view is made");
(index, meter, view)
}
fn held(index: &Index, view: usize, item: ItemId) -> Option<Held> {
let lists = index.globs.views[view].names.get("X")?;
lists[0].iter().copied().find(|entry| entry.0 == item)
}
#[test]
fn an_entry_held_as_a_companion_is_widened_as_it_is_added_again_and_made_plain_only_by_a_plain_entry()
{
let (mut index, meter, view) = viewed();
let item = ItemId(1);
let narrow = Level::within(1);
let wide = Level::within(0);
assert!(index.width(wide) < index.width(narrow));
for (level, expected) in [
(narrow.companion(), narrow.companion()),
(wide.companion(), wide.companion()),
(wide.companion(), wide.companion()),
(narrow.companion(), wide.companion()),
] {
index
.add_to_view(view, "X", 0, &[(item, level)], &meter)
.expect("added");
assert_eq!(held(&index, view, item), Some((item, expected)));
}
let fresh = index
.add_to_view(view, "X", 0, &[(item, wide)], &meter)
.expect("added");
assert_eq!(fresh.ids, vec![(item, wide)]);
assert_eq!(held(&index, view, item), Some((item, wide)));
index
.add_to_view(view, "X", 0, &[(item, Level::PUBLIC.companion())], &meter)
.expect("added");
assert_eq!(held(&index, view, item), Some((item, Level::PUBLIC)));
}
#[test]
#[should_panic(expected = "narrows")]
fn an_entry_that_narrows_the_level_an_item_is_held_at_is_refused() {
let (mut index, meter, view) = viewed();
let item = ItemId(1);
index
.add_to_view(view, "X", 0, &[(item, Level::PUBLIC.companion())], &meter)
.expect("added");
index.assert_widened(view, "X", 0, &[(item, Level::within(1).companion())]);
}
#[test]
#[should_panic(expected = "narrows")]
fn an_entry_that_makes_a_plain_item_a_companion_again_is_refused() {
let (mut index, meter, view) = viewed();
let item = ItemId(1);
index
.add_to_view(view, "X", 0, &[(item, Level::within(0))], &meter)
.expect("added");
index.assert_widened(view, "X", 0, &[(item, Level::within(0).companion())]);
}
}
#[cfg(test)]
mod table_bytes {
use std::mem::size_of;
use super::{Held, Index, Level, Nobody, Unseen, covert_bytes, set_bytes};
use crate::cost::{
btree_entry, btree_map, hash_entry, hash_map, shared_text, vec_first, vec_slot,
};
use crate::item::{ItemId, SharedStr};
use crate::meter::Meter;
use crate::options::LoadOptions;
use crate::{MemoryTree, Workspace};
const fn name_taken() -> usize {
super::NAME_BYTES + vec_first::<Held>() + vec_slot::<Held>()
}
fn emptied() -> (Index, Meter, usize, usize, [usize; 2], usize) {
let tree: MemoryTree = [
(
"Cargo.toml",
"[package]\nname = \"demo\"\nversion = \"0.1.0\"\nedition = \"2021\"\n",
),
(
"src/lib.rs",
"pub mod d {}\npub mod a { pub use crate::d::*; use crate::d::*; }\n",
),
]
.into_iter()
.collect();
let mut index = Workspace::load(&tree, &["."])
.expect("loads")
.index()
.clone();
let meter = Meter::new(&LoadOptions::default());
index.clear_globs();
index
.reset_globs(&meter)
.expect("the tables are built again");
let module = |path: &str| {
index
.modules
.iter()
.position(|module| module.path == path)
.expect("a module of the crate")
};
let (a, d) = (module("demo::a"), module("demo::d"));
let globs = [index.glob_imports[0], index.glob_imports[1]];
let base = index.globs.charged;
(index, meter, a, d, globs, base)
}
#[test]
fn the_tables_of_the_views_that_hold_each_name_and_of_the_names_with_a_companion_are_charged_their_first_room()
{
let (index, .., base) = emptied();
let modules = index.modules.len();
let expected = modules * (vec_slot::<Vec<usize>>() + vec_slot::<Vec<super::GlobRead>>())
+ vec_first::<Vec<usize>>()
+ vec_first::<Vec<super::GlobRead>>()
+ vec_first::<super::View>()
+ btree_map::<(usize, Box<[bool]>), usize>()
+ btree_map::<(usize, usize), ()>()
+ btree_map::<(usize, usize, usize), ()>()
+ hash_map::<SharedStr>()
+ hash_map::<(SharedStr, [bool; 3])>()
+ hash_map::<(SharedStr, Vec<usize>)>();
assert_eq!(base, expected, "{modules} modules");
#[cfg(target_pointer_width = "64")]
assert_eq!((modules, base), (3, BASE_BYTES));
}
#[test]
fn each_name_a_view_takes_is_charged_its_slot_among_the_holders_of_the_name_and_the_first_companion_its_entry()
{
let (mut index, meter, a, d, globs, _) = emptied();
let class = index.class_for(d, a);
let first = index.make_view(d, &class, globs[0], &meter).expect("made");
let second = index
.make_view(a, &[true, false], globs[0], &meter)
.expect("made");
let item = ItemId(1);
let take = |index: &mut Index, view: usize, name: &str, level: Level| {
let before = index.globs.charged;
index
.add_to_view(view, name, 0, &[(item, level)], &meter)
.expect("added");
index.globs.charged - before
};
let text = shared_text(1) + hash_entry::<SharedStr>();
let holders = hash_entry::<(SharedStr, Vec<usize>)>() + vec_first::<usize>();
let slot = vec_slot::<usize>();
let companion = hash_entry::<(SharedStr, [bool; 3])>();
let charged = [
take(&mut index, first, "X", Level::PUBLIC),
take(&mut index, second, "X", Level::PUBLIC),
take(&mut index, first, "Y", Level::PUBLIC.companion()),
take(&mut index, second, "Y", Level::PUBLIC.companion()),
];
let expected = [
name_taken() + text + holders + slot,
name_taken() + slot,
name_taken() + text + holders + slot + companion,
name_taken() + slot,
];
assert_eq!(charged, expected);
#[cfg(target_pointer_width = "64")]
assert_eq!(charged, TAKEN_BYTES);
assert_eq!(index.globs.holding.get("X"), Some(&vec![first, second]));
assert_eq!(index.globs.holding.get("Y"), Some(&vec![first, second]));
assert_eq!(index.globs.companions.get("Y"), Some(&[true, false, false]));
assert_eq!(index.globs.companions.get("X"), None);
}
#[test]
fn each_read_of_a_view_is_charged_its_place_among_the_reads_of_its_module_of_that_view() {
let (mut index, meter, a, d, globs, _) = emptied();
let class = index.class_for(d, a);
let before = index.globs.charged;
let view = index.make_view(d, &class, globs[0], &meter).expect("made");
let made = index.globs.charged - before;
let read = |index: &mut Index, glob: usize| {
let before = index.globs.charged;
index.read_glob(glob, d, &mut Nobody, &meter).expect("read");
index.globs.charged - before
};
let charged = [read(&mut index, globs[0]), read(&mut index, globs[1])];
assert_eq!(
made,
super::VIEW_BYTES + 2 * class.len(),
"the view of `d` for `a`"
);
assert_eq!(
super::VIEW_BYTES,
vec_slot::<super::View>()
+ btree_entry::<(usize, Box<[bool]>), usize>()
+ vec_slot::<usize>()
+ vec_first::<usize>()
+ btree_map::<SharedStr, super::Lists>()
+ vec_first::<(usize, usize, usize)>()
+ 2 * btree_map::<usize, Vec<usize>>()
);
let place = vec_slot::<usize>();
let first_places = btree_entry::<usize, Vec<usize>>() + vec_first::<usize>();
assert_eq!(
charged,
[
super::READ_BYTES + vec_first::<super::GlobRead>() + place + first_places,
super::READ_BYTES + place
]
);
#[cfg(target_pointer_width = "64")]
assert_eq!((made, charged), READ_VIEW_BYTES);
assert_eq!(index.globs.views[view].places.get(&a), Some(&vec![0, 1]));
}
#[cfg(target_pointer_width = "64")]
const BASE_BYTES: usize = 2688;
#[cfg(target_pointer_width = "64")]
const TAKEN_BYTES: [usize; 4] = [520, 290, 595, 290];
#[cfg(target_pointer_width = "64")]
const READ_VIEW_BYTES: (usize, [usize; 2]) = (1627, [789, 526]);
fn viewed_from_outside() -> (Index, Meter, usize, usize, [usize; 2], usize, Box<[bool]>) {
let (mut index, meter, a, d, globs, _) = emptied();
let outside = index.class_for(a, d);
let view = index
.make_view(a, &outside, globs[0], &meter)
.expect("made");
(index, meter, a, d, globs, view, outside)
}
fn charged(index: &mut Index, run: &dyn Fn(&mut Index)) -> usize {
let before = index.globs.charged;
run(index);
index.globs.charged - before
}
#[test]
fn each_covert_reader_open_reader_and_view_read_through_a_glob_a_class_cannot_access_is_charged_its_entry_and_the_first_room_of_its_table()
{
let (mut index, meter, a, d, globs, view, outside) = viewed_from_outside();
let metered = &meter;
let read = |glob: usize| {
move |index: &mut Index| {
index
.read_glob(glob, d, &mut Nobody, metered)
.expect("read");
}
};
let public = charged(&mut index, &read(globs[0]));
let private = charged(&mut index, &read(globs[1]));
let d_view = index.globs.exports[d][0];
assert!(index.globs.views[d_view].unseen().covert.contains_key(&a));
assert!(index.globs.views[d_view].unseen().open.contains(&a));
assert_eq!(
index.globs.views[view]
.unseen()
.hiding
.iter()
.copied()
.collect::<Vec<_>>(),
vec![d_view]
);
let made = super::VIEW_BYTES + 2 * outside.len();
let place = vec_slot::<usize>();
let first_places = btree_entry::<usize, Vec<usize>>() + vec_first::<usize>();
let expected_public =
made + super::READ_BYTES + vec_first::<super::GlobRead>() + place + first_places;
let expected_private = super::READ_BYTES
+ place
+ set_bytes::<usize>(true)
+ covert_bytes(true, true)
+ set_bytes::<usize>(true)
+ 2 * size_of::<Unseen>();
assert_eq!([public, private], [expected_public, expected_private]);
assert_eq!(
covert_bytes(true, true),
vec_slot::<(usize, usize)>()
+ btree_entry::<usize, Vec<(usize, usize)>>()
+ vec_first::<(usize, usize)>()
+ btree_map::<usize, Vec<(usize, usize)>>()
);
assert_eq!(
set_bytes::<usize>(true),
btree_entry::<usize, ()>() + btree_map::<usize, ()>()
);
#[cfg(target_pointer_width = "64")]
assert_eq!([public, private], COVERT_READ_BYTES);
}
#[test]
fn each_name_a_view_dropped_and_each_name_a_reading_again_set_is_charged_its_entry_and_the_first_room_of_its_record()
{
let (mut index, meter, _, _, globs, view, _) = viewed_from_outside();
let site = globs[0];
let x = SharedStr::from("X");
let drop_at = |at: usize| {
let (x, meter) = (x.clone(), &meter);
move |index: &mut Index| {
index
.note_dropped(view, x.clone(), at, site, meter)
.expect("noted");
}
};
let dropped = [0, 1, 1].map(|at| charged(&mut index, &drop_at(at)));
assert_eq!(
dropped,
[
set_bytes::<(SharedStr, usize)>(true) + size_of::<Unseen>(),
set_bytes::<(SharedStr, usize)>(false),
0
]
);
let mark_at = |at: usize| {
let meter = &meter;
move |index: &mut Index| {
index
.mark_exact(view, "Q", at, site, meter)
.expect("marked");
}
};
let exact = [0, 1, 1].map(|at| charged(&mut index, &mark_at(at)));
assert_eq!(
exact,
[
shared_text(1)
+ hash_entry::<SharedStr>()
+ set_bytes::<(usize, SharedStr, usize)>(true),
set_bytes::<(usize, SharedStr, usize)>(false),
0
]
);
#[cfg(target_pointer_width = "64")]
assert_eq!((dropped, exact), RECORD_BYTES);
}
#[cfg(target_pointer_width = "64")]
const COVERT_READ_BYTES: [usize; 2] = [2416, 1647];
#[cfg(target_pointer_width = "64")]
const RECORD_BYTES: ([usize; 3], [usize; 3]) = ([490, 106, 0], [586, 135, 0]);
}