use std::collections::{BTreeMap, BTreeSet, VecDeque};
use std::error::Error;
use std::fmt;
use std::mem::size_of;
use std::rc::Rc;
use purrdf_lex::walk::WorkList;
use crate::cost::{btree_entry, btree_map, vec_first, vec_slot};
use crate::error::{Esc, LoadError, LoadErrorKind};
use crate::facts::{SpanFact, TestRole, Vis};
use crate::index::{Index, UseDecl, UseKind};
use crate::item::{ItemId, Namespace, SymbolKind};
use crate::meter::{Meter, Steps, over_budget, push_item_work};
use crate::modtree::TargetId;
use crate::path::RelPath;
use crate::resolve::{Fail, ResolveError};
use crate::settle::slot;
use crate::work::{self as tally, Work};
#[derive(Debug, Clone, Default, PartialEq, Eq)]
#[non_exhaustive]
pub struct ExportOptions {
pub include_hidden: bool,
}
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub struct ExportedItem {
pub path: String,
pub item: ItemId,
pub kind: SymbolKind,
pub file: RelPath,
pub span: SpanFact,
pub doc_hidden: bool,
}
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub struct Reexport {
pub path: String,
pub written: String,
pub item: Option<ItemId>,
pub file: RelPath,
pub line: usize,
pub doc_hidden: bool,
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
#[non_exhaustive]
pub struct Exports {
pub items: Vec<ExportedItem>,
pub reexports: Vec<Reexport>,
}
#[derive(Debug)]
#[non_exhaustive]
pub enum ExportError {
NotLibraryOrBinary(TargetId),
Budget(LoadError),
Storage(LoadError),
CarryBudget {
path: String,
error: LoadError,
},
Resolve(ResolveError),
}
impl fmt::Display for ExportError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::NotLibraryOrBinary(id) => write!(
f,
"target {} is not a library or a binary of the workspace",
id.index()
),
Self::Budget(error) => write!(f, "the public surface is over budget: {error}"),
Self::Storage(error) => write!(f, "the public surface storage failed: {error}"),
Self::CarryBudget { path, error } => write!(
f,
"deciding whether the public globs carry the re-export `{}` is over budget: {error}",
Esc(path)
),
Self::Resolve(error) => write!(f, "a public name does not resolve: {error}"),
}
}
}
impl Error for ExportError {
fn source(&self) -> Option<&(dyn Error + 'static)> {
match self {
Self::NotLibraryOrBinary(_) => None,
Self::Budget(error) | Self::Storage(error) | Self::CarryBudget { error, .. } => {
Some(error)
}
Self::Resolve(error) => Some(error),
}
}
}
impl ExportError {
fn storage(error: LoadError, carried: Option<String>) -> Self {
if matches!(error.kind, LoadErrorKind::Budget { .. }) {
match carried {
Some(path) => Self::CarryBudget { path, error },
None => Self::Budget(error),
}
} else {
Self::Storage(error)
}
}
}
#[derive(Debug, Clone, Copy)]
struct Route {
view: usize,
target: usize,
glob: usize,
hidden: bool,
}
struct Routes<'a> {
list: Vec<Route>,
by_name: BTreeMap<&'a str, Vec<usize>>,
}
impl Routes<'_> {
fn holding(&self, name: &str) -> impl Iterator<Item = &Route> + '_ {
self.by_name
.get(name)
.into_iter()
.flatten()
.map(|at| &self.list[*at])
}
}
struct Carry<'a> {
graph: Reach,
binders: BTreeMap<&'a str, Vec<usize>>,
carriers: BTreeMap<&'a str, Vec<usize>>,
answers: BTreeMap<(&'a str, usize, usize), bool>,
}
struct Reach {
modules: Vec<usize>,
node_of: BTreeMap<usize, usize>,
succ: [Vec<Vec<usize>>; 2],
shown: Vec<bool>,
spans: [Option<Spans>; 2],
}
type Spans = Vec<Option<(usize, usize)>>;
const SHOWN: usize = 0;
const EVERY: usize = 1;
impl Reach {
fn dominates(&self, mode: usize, above: usize, below: usize) -> bool {
match self.spans[mode]
.as_ref()
.map(|spans| (spans[above], spans[below]))
{
Some((Some(above), Some(below))) => above.0 <= below.0 && below.1 <= above.1,
_ => false,
}
}
}
fn dominator_spans(
succ: &[Vec<usize>],
meter: &Meter,
file: &RelPath,
line: usize,
) -> Result<(Spans, usize), LoadError> {
let count = succ.len();
let mut work = 0;
let mut post = vec![usize::MAX; count];
let mut order = Vec::with_capacity(count);
let mut stack = WorkList::<_, 8>::new();
push_item_work(&mut stack, (0, 0), meter, file, Some(line))?;
let mut entered = vec![false; count];
entered[0] = true;
while let Some((node, next)) = stack.pop() {
work += 1;
if let Some(&to) = succ[node].get(next) {
push_item_work(&mut stack, (node, next + 1), meter, file, Some(line))?;
if !entered[to] {
entered[to] = true;
push_item_work(&mut stack, (to, 0), meter, file, Some(line))?;
}
} else {
post[node] = order.len();
order.push(node);
}
}
let mut preds: Vec<Vec<usize>> = vec![Vec::new(); count];
for (from, tos) in succ.iter().enumerate() {
if post[from] == usize::MAX {
continue;
}
for &to in tos {
preds[to].push(from);
}
}
let mut idom = vec![usize::MAX; count];
idom[0] = 0;
let mut changed = true;
while changed {
changed = false;
for &node in order.iter().rev().skip(1) {
let mut new = usize::MAX;
for &pred in &preds[node] {
work += 1;
if idom[pred] == usize::MAX {
continue;
}
if new == usize::MAX {
new = pred;
continue;
}
let (mut a, mut b) = (pred, new);
while a != b {
while post[a] < post[b] {
a = idom[a];
work += 1;
}
while post[b] < post[a] {
b = idom[b];
work += 1;
}
}
new = a;
}
if idom[node] != new {
idom[node] = new;
changed = true;
}
}
}
let mut children: Vec<Vec<usize>> = vec![Vec::new(); count];
for node in 1..count {
if post[node] != usize::MAX {
children[idom[node]].push(node);
}
}
let mut spans: Spans = vec![None; count];
let mut clock = 0;
let mut stack = WorkList::<_, 8>::new();
push_item_work(&mut stack, (0, 0), meter, file, Some(line))?;
while let Some((node, next)) = stack.pop() {
work += 1;
if next == 0 {
spans[node] = Some((clock, clock));
clock += 1;
}
if let Some(&child) = children[node].get(next) {
push_item_work(&mut stack, (node, next + 1), meter, file, Some(line))?;
push_item_work(&mut stack, (child, 0), meter, file, Some(line))?;
} else if let Some(span) = spans[node].as_mut() {
span.1 = clock;
clock += 1;
}
}
Ok((spans, work))
}
const WALK_STEP_BYTES: usize = btree_entry::<usize, bool>();
type Place = (ItemId, usize, usize, String);
struct Visit {
module: usize,
path: String,
hidden: bool,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Other {
Seen(ItemId),
Outside,
}
impl Other {
fn item(self) -> Option<ItemId> {
match self {
Self::Seen(id) => Some(id),
Self::Outside => None,
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum By {
Explicit,
Glob,
}
pub(crate) struct Surface<'a> {
index: &'a Index,
target: TargetId,
root: usize,
crate_path: &'a str,
options: &'a ExportOptions,
meter: &'a Meter,
hidden_files: &'a BTreeSet<&'a str>,
routes: BTreeMap<usize, Rc<Routes<'a>>>,
decided: BTreeMap<Place, bool>,
items: Vec<ExportedItem>,
reexports: Vec<Reexport>,
}
fn written(decl: &UseDecl) -> String {
let (segs, glob) = match &decl.kind {
UseKind::Named { segs, .. } => (segs, false),
UseKind::Glob { segs } => (segs, true),
};
let mut text = String::new();
if decl.leading_colon {
text.push_str("::");
}
text.push_str(&segs.join("::"));
if glob {
text.push_str("::*");
}
text
}
fn exporting(decl: &UseDecl) -> bool {
decl.vis == Vis::Public && !decl.test
}
impl<'a> Surface<'a> {
pub(crate) fn new(
index: &'a Index,
target: TargetId,
crate_path: &'a str,
options: &'a ExportOptions,
meter: &'a Meter,
hidden_files: &'a BTreeSet<&'a str>,
) -> Self {
Self {
index,
target,
root: index.target_roots[target.index()],
crate_path,
options,
meter,
hidden_files,
routes: BTreeMap::new(),
decided: BTreeMap::new(),
items: Vec::new(),
reexports: Vec::new(),
}
}
fn charge(&self, bytes: usize, id: ItemId) -> Result<(), ExportError> {
let item = &self.index.items[id.0];
self.meter
.items(bytes, &item.file, Some(item.name_line))
.map_err(ExportError::Budget)
}
fn module_item(&self, module: usize) -> ItemId {
self.index
.module_items(module)
.first()
.copied()
.unwrap_or_else(|| self.index.root_items[&self.index.modules[module].root])
}
pub(crate) fn list(mut self) -> Result<Exports, ExportError> {
let index = self.index;
let root_item = index.root_items[&self.root];
self.charge(
vec_first::<ExportedItem>()
+ vec_first::<Reexport>()
+ 2 * vec_first::<Visit>()
+ index.modules.len() * size_of::<bool>()
+ btree_map::<usize, Vec<Route>>(),
root_item,
)?;
let mut visited = vec![false; index.modules.len()];
let mut shown: VecDeque<Visit> = VecDeque::new();
let mut hidden: VecDeque<Visit> = VecDeque::new();
let start = Visit {
module: self.root,
path: self.crate_path.to_owned(),
hidden: index.items[root_item.0].doc_hidden,
};
self.charge(vec_slot::<Visit>() + start.path.capacity(), root_item)?;
if start.hidden {
if self.options.include_hidden {
hidden.push_back(start);
}
} else {
visited[self.root] = true;
shown.push_back(start);
}
loop {
let visit = match shown.pop_front() {
Some(visit) => visit,
None => match hidden.pop_front() {
Some(visit) if visited[visit.module] => continue,
Some(visit) => {
visited[visit.module] = true;
visit
}
None => break,
},
};
let found = self.module(&visit)?;
for next in found {
if visited[next.module] {
continue;
}
self.charge(
vec_slot::<Visit>() + next.path.capacity(),
self.module_item(next.module),
)?;
if next.hidden {
hidden.push_back(next);
} else {
visited[next.module] = true;
shown.push_back(next);
}
}
}
let Self {
mut items,
mut reexports,
..
} = self;
items.sort_by(|a, b| {
(a.path.as_str(), index.sort_key(a.item))
.cmp(&(b.path.as_str(), index.sort_key(b.item)))
});
reexports.sort_by(|a, b| {
(&a.path, &a.file, a.line, &a.written, a.item)
.cmp(&(&b.path, &b.file, b.line, &b.written, b.item))
});
Ok(Exports { items, reexports })
}
fn routes(&mut self, module: usize) -> Result<Rc<Routes<'a>>, ExportError> {
if let Some(known) = self.routes.get(&module) {
return Ok(Rc::clone(known));
}
let index = self.index;
let mut by_view: BTreeMap<usize, Route> = BTreeMap::new();
for (glob, target, view) in index.glob_reads(module) {
let decl = &index.uses[glob];
if !exporting(decl) {
continue;
}
by_view
.entry(view)
.and_modify(|route| {
route.glob = route.glob.min(glob);
route.hidden &= decl.doc_hidden;
})
.or_insert(Route {
view,
target,
glob,
hidden: decl.doc_hidden,
});
}
let list: Vec<Route> = by_view.into_values().collect();
let mut held = 0;
let mut by_name: BTreeMap<&'a str, Vec<usize>> = BTreeMap::new();
for (at, route) in list.iter().enumerate() {
for name in index.view_names(route.view) {
by_name.entry(name).or_default().push(at);
held += 1;
}
}
self.charge(
btree_entry::<usize, Rc<Routes<'a>>>()
+ size_of::<Routes<'a>>()
+ 2 * size_of::<usize>()
+ list.capacity() * size_of::<Route>()
+ btree_map::<&str, Vec<usize>>()
+ by_name.len() * (btree_entry::<&str, Vec<usize>>() + vec_first::<usize>())
+ held * vec_slot::<usize>(),
self.module_item(module),
)?;
let routes = Rc::new(Routes { list, by_name });
self.routes.insert(module, Rc::clone(&routes));
Ok(routes)
}
fn glob_reach(&mut self, start: usize) -> Result<Vec<(usize, bool)>, ExportError> {
let mut seen: BTreeMap<usize, bool> = BTreeMap::new();
let mut order = Vec::new();
let at = self.module_item(start);
for with_hidden in [false, true] {
let mut work = VecDeque::from([(start, false)]);
let mut entered = BTreeSet::from([start]);
while let Some((module, hidden)) = work.pop_front() {
tally::add(Work::WalkSteps, 1);
self.charge(WALK_STEP_BYTES, at)?;
if module != start
&& let std::collections::btree_map::Entry::Vacant(slot) = seen.entry(module)
{
slot.insert(hidden);
order.push(module);
}
for route in &self.routes(module)?.list {
let shown = !route.hidden || module != start;
if (with_hidden || shown) && entered.insert(route.target) {
work.push_back((route.target, hidden || !shown));
}
}
}
}
Ok(order
.into_iter()
.map(|module| (module, seen[&module]))
.collect())
}
fn declared_public(&self, id: ItemId) -> bool {
let item = &self.index.items[id.0];
match item.kind {
SymbolKind::MacroRules => item.macro_export,
_ => item.visibility == Vis::Public,
}
}
fn exporting_imports(&self, module: usize, name: &str, at: usize) -> Vec<usize> {
let index = self.index;
index
.imports_of(module, name)
.iter()
.copied()
.filter(|position| index.use_bound[*position][at] && exporting(&index.uses[*position]))
.collect()
}
fn public_route(
&mut self,
module: usize,
at: usize,
name: &str,
id: ItemId,
) -> Result<bool, ExportError> {
let index = self.index;
let start: Place = (id, module, at, name.to_owned());
let mut from: BTreeMap<Place, Option<Place>> = BTreeMap::new();
let mut work = WorkList::<_, 8>::new();
let item = &index.items[id.0];
let meter = self.meter;
let push = |work: &mut WorkList<_, 8>, value| {
push_item_work(work, value, meter, &item.file, Some(item.name_line))
.map_err(|error| ExportError::storage(error, None))
};
push(&mut work, (start, None))?;
let mut found = None;
while let Some((place, parent)) = work.pop() {
if from.contains_key(&place) {
continue;
}
from.insert(place.clone(), parent);
match self.decided.get(&place) {
Some(true) => {
found = Some(place);
break;
}
Some(false) => continue,
None => {}
}
let (_, module, at, name) = &place;
let (module, at) = (*module, *at);
let defs = index.scopes[module]
.get(name)
.map(|entry| &entry.defs[at])
.filter(|defs| !defs.is_empty());
if let Some(defs) = defs {
let Some(origin) = defs.get(id) else {
continue;
};
let next = match &origin.link {
None => None,
Some(_) if self.exporting_imports(module, name, at).is_empty() => continue,
Some(link) => link.source.as_ref(),
};
match next {
Some(source) => {
let step = (id, source.module, slot(source.ns), source.name.clone());
push(&mut work, (step, Some(place)))?;
}
None if self.declared_public(id) => {
found = Some(place);
break;
}
None => {}
}
} else if !index.blocked(module, name, Namespace::ALL[at], None) {
let routes = self.routes(module)?;
for route in routes.holding(name) {
if index.view_holds(route.view, name, at, id) {
let step = (id, route.target, at, name.clone());
push(&mut work, (step, Some(place.clone())))?;
}
}
}
}
let decided: Vec<(Place, bool)> = match found {
Some(mut place) => {
let mut route = Vec::new();
loop {
let parent = from.get(&place).cloned().flatten();
route.push((place, true));
match parent {
Some(next) => place = next,
None => break,
}
}
route
}
None => from.into_keys().map(|place| (place, false)).collect(),
};
let reached = !decided.is_empty() && decided[0].1;
for (place, public) in decided {
if let std::collections::btree_map::Entry::Vacant(slot) = self.decided.entry(place) {
self.meter
.items(
btree_entry::<Place, bool>() + slot.key().3.capacity(),
&index.items[id.0].file,
Some(index.items[id.0].name_line),
)
.map_err(ExportError::Budget)?;
slot.insert(public);
}
}
Ok(reached)
}
fn carrying_routes(
&mut self,
module: usize,
at: usize,
name: &str,
id: ItemId,
) -> Result<Vec<Route>, ExportError> {
let index = self.index;
let routes = self.routes(module)?;
let mut carrying = Vec::new();
for route in routes.holding(name) {
if index.view_holds(route.view, name, at, id)
&& self.public_route(route.target, at, name, id)?
{
carrying.push(*route);
}
}
Ok(carrying)
}
fn reexport_hidden(
&mut self,
module: usize,
at: usize,
name: &str,
id: ItemId,
by: By,
) -> Result<bool, ExportError> {
let index = self.index;
Ok(match by {
By::Explicit => {
let imported = index.scopes[module]
.get(name)
.and_then(|entry| entry.defs[at].get(id))
.is_some_and(|origin| origin.link.is_some());
let imports = self.exporting_imports(module, name, at);
imported
&& !imports.is_empty()
&& imports
.iter()
.all(|position| index.uses[*position].doc_hidden)
}
By::Glob => {
let carrying = self.carrying_routes(module, at, name, id)?;
!carrying.is_empty() && carrying.iter().all(|route| route.hidden)
}
})
}
fn binding_site(
&mut self,
module: usize,
at: usize,
name: &str,
id: ItemId,
by: By,
) -> Result<(String, RelPath, usize), ExportError> {
let index = self.index;
let decl = match by {
By::Explicit => self
.exporting_imports(module, name, at)
.first()
.map(|position| &index.uses[*position]),
By::Glob => self
.carrying_routes(module, at, name, id)?
.iter()
.map(|route| route.glob)
.min()
.map(|glob| &index.uses[glob]),
};
if let Some(decl) = decl {
return Ok((written(decl), decl.file.clone(), decl.line));
}
let item = &index.items[id.0];
let crate_name = index
.extern_names
.get(&id)
.map_or_else(|| item.name.to_string(), ToString::to_string);
Ok((crate_name, item.file.clone(), item.name_line))
}
fn other_crate(&self, id: ItemId) -> Option<Other> {
let index = self.index;
let item = &index.items[id.0];
if item.target != self.target {
return Some(Other::Seen(id));
}
if item.kind == SymbolKind::ExternCrate {
return match index.crate_of.get(&id) {
None => Some(Other::Outside),
Some(roots) if roots.contains(&self.root) => None,
Some(roots) => Some(
roots
.first()
.and_then(|root| index.root_items.get(root).copied())
.map_or(Other::Outside, Other::Seen),
),
};
}
None
}
fn keep(&mut self, path: String, id: ItemId, doc_hidden: bool) -> Result<(), ExportError> {
if doc_hidden && !self.options.include_hidden {
return Ok(());
}
self.charge(vec_slot::<ExportedItem>() + path.capacity(), id)?;
let item = &self.index.items[id.0];
self.items.push(ExportedItem {
path,
item: id,
kind: item.kind,
file: item.file.clone(),
span: item.span.clone(),
doc_hidden,
});
Ok(())
}
fn keep_reexport(
&mut self,
path: String,
written: String,
item: Option<ItemId>,
file: RelPath,
line: usize,
doc_hidden: bool,
) -> Result<(), ExportError> {
if doc_hidden && !self.options.include_hidden {
return Ok(());
}
self.meter
.items(
vec_slot::<Reexport>() + path.capacity() + written.capacity(),
&file,
Some(line),
)
.map_err(ExportError::Budget)?;
self.reexports.push(Reexport {
path,
written,
item,
file,
line,
doc_hidden,
});
Ok(())
}
fn module(&mut self, visit: &Visit) -> Result<Vec<Visit>, ExportError> {
let index = self.index;
let (module, path) = (visit.module, visit.path.as_str());
self.unseen(visit)?;
let routes = self.routes(module)?;
let mut names: BTreeSet<&'a str> =
index.scopes[module].keys().map(String::as_str).collect();
names.extend(routes.by_name.keys().copied());
self.charge(
btree_map::<&str, ()>() + names.len() * btree_entry::<&str, ()>(),
self.module_item(module),
)?;
let mut next = Vec::new();
for name in names {
let mut found: BTreeMap<ItemId, (usize, By)> = BTreeMap::new();
for ns in Namespace::ALL {
let at = slot(ns);
let Some((ids, from_glob)) = self.bound(module, ns, name)? else {
continue;
};
let mut exported = false;
for &id in &ids {
if index.items[id.0].test == TestRole::None
&& self.public_route(module, at, name, id)?
{
exported = true;
found
.entry(id)
.or_insert((at, if from_glob { By::Glob } else { By::Explicit }));
}
}
if exported
&& let Some(error) = index.binding_failure(
module,
ns,
name,
&ids,
&format!("{path}::{name}"),
Steps::Query(self.meter),
)
{
return Err(ExportError::Resolve(error));
}
}
for id in index.sorted(found.keys().copied()) {
let (at, by) = found[&id];
if let Some(child) = self.binding(visit, name, id, at, by)? {
next.push(child);
}
}
}
Ok(next)
}
fn unseen(&mut self, visit: &Visit) -> Result<(), ExportError> {
let index = self.index;
self.unseen_globs(visit, visit.module, false)?;
self.unbound_imports(visit, visit.module, false, None)?;
let reach = self.glob_reach(visit.module)?;
if reach.is_empty() {
return Ok(());
}
let mut carry = Carry {
graph: self.reach_graph(visit.module, &reach)?,
binders: BTreeMap::new(),
carriers: BTreeMap::new(),
answers: BTreeMap::new(),
};
for (node, &module) in carry.graph.modules.iter().enumerate() {
let defined = index.scopes[module]
.iter()
.filter(|(_, entry)| entry.defs.iter().any(|bound| !bound.is_empty()))
.map(|(name, _)| name.as_str());
let mut imported: Vec<&'a str> = Vec::new();
for position in index.named_of(module) {
let decl = &index.uses[*position];
if let UseKind::Named { name, .. } = &decl.kind {
imported.push(name.as_str());
if node > 0
&& exporting(decl)
&& !index.use_bound[*position].iter().any(|bound| *bound)
{
let carriers = carry.carriers.entry(name.as_str()).or_default();
if carriers.last() != Some(&node) {
carriers.push(node);
}
}
}
}
for name in defined.chain(imported) {
let binders = carry.binders.entry(name).or_default();
if binders.last() != Some(&node) {
binders.push(node);
}
}
}
let held: usize = carry
.binders
.values()
.chain(carry.carriers.values())
.map(Vec::len)
.sum();
self.charge(
2 * btree_map::<&str, Vec<usize>>()
+ (carry.binders.len() + carry.carriers.len())
* (btree_entry::<&str, Vec<usize>>() + vec_first::<usize>())
+ held * vec_slot::<usize>(),
self.module_item(visit.module),
)?;
for (module, hidden) in reach {
self.unseen_globs(visit, module, hidden)?;
self.unbound_imports(visit, module, hidden, Some(&mut carry))?;
}
Ok(())
}
fn reach_graph(
&mut self,
reader: usize,
reach: &[(usize, bool)],
) -> Result<Reach, ExportError> {
let modules: Vec<usize> = std::iter::once(reader)
.chain(reach.iter().map(|(module, _)| *module))
.collect();
let node_of: BTreeMap<usize, usize> = modules
.iter()
.enumerate()
.map(|(node, module)| (*module, node))
.collect();
let shown: Vec<bool> = std::iter::once(true)
.chain(reach.iter().map(|(_, hidden)| !hidden))
.collect();
let mut succ: [Vec<Vec<usize>>; 2] = [
Vec::with_capacity(modules.len()),
Vec::with_capacity(modules.len()),
];
let mut edges = 0;
for (node, &module) in modules.iter().enumerate() {
let routes = self.routes(module)?;
for (mode, list) in succ.iter_mut().enumerate() {
let mut to: Vec<usize> = routes
.list
.iter()
.filter(|route| mode == EVERY || node != 0 || !route.hidden)
.filter_map(|route| node_of.get(&route.target).copied())
.collect();
to.sort_unstable();
to.dedup();
edges += to.len();
list.push(to);
}
}
self.charge(
modules.len()
* (size_of::<usize>()
+ size_of::<bool>()
+ btree_entry::<usize, usize>()
+ 2 * size_of::<Vec<usize>>())
+ btree_map::<usize, usize>()
+ edges * size_of::<usize>(),
self.module_item(reader),
)?;
Ok(Reach {
modules,
node_of,
succ,
shown,
spans: [None, None],
})
}
fn carried(
&mut self,
visit: &Visit,
position: usize,
module: usize,
name: &'a str,
carry: &mut Carry<'a>,
) -> Result<Option<bool>, ExportError> {
if self.carried_by(visit, position, module, name, carry, SHOWN)? {
return Ok(Some(false));
}
Ok(self
.carried_by(visit, position, module, name, carry, EVERY)?
.then_some(true))
}
fn carried_by(
&mut self,
visit: &Visit,
position: usize,
module: usize,
name: &'a str,
carry: &mut Carry<'a>,
mode: usize,
) -> Result<bool, ExportError> {
let decl = &self.index.uses[position];
let charge = |surface: &Self, bytes: usize| {
surface
.meter
.items(bytes, &decl.file, Some(decl.line))
.map_err(|error| ExportError::CarryBudget {
path: format!("{}::{name}", visit.path),
error,
})
};
let target = carry.graph.node_of[&module];
if mode == SHOWN && !carry.graph.shown[target] {
return Ok(false);
}
let Some(binders) = carry.binders.get(name) else {
return Ok(true);
};
if binders.first() == Some(&0) {
return Ok(false);
}
let succ = &carry.graph.succ[mode];
let passed: Vec<usize> = binders
.iter()
.copied()
.filter(|node| {
*node != target
&& !succ[*node].is_empty()
&& (mode == EVERY || carry.graph.shown[*node])
})
.collect();
if passed.is_empty() {
return Ok(true);
}
self.ensure_spans(&mut carry.graph, mode, decl, &visit.path, name)?;
if passed
.iter()
.any(|binder| carry.graph.dominates(mode, *binder, target))
{
return Ok(false);
}
if passed.len() == 1 {
return Ok(true);
}
if let Some(known) = carry.answers.get(&(name, target, mode)) {
return Ok(*known);
}
let succ = &carry.graph.succ[mode];
let count = carry.graph.modules.len();
let mut entered = vec![false; count];
entered[0] = true;
let mut work = WorkList::<_, 8>::new();
let push = |work: &mut WorkList<_, 8>, value| {
push_item_work(work, value, self.meter, &decl.file, Some(decl.line)).map_err(|error| {
ExportError::storage(error, Some(format!("{}::{name}", visit.path)))
})
};
push(&mut work, 0)?;
let mut reached = BTreeSet::new();
let mut steps = 0;
while let Some(node) = work.pop() {
steps += 1 + succ[node].len();
if node != 0 {
reached.insert(node);
if binders.binary_search(&node).is_ok() {
continue;
}
}
for &to in &succ[node] {
if !entered[to] {
entered[to] = true;
push(&mut work, to)?;
}
}
}
let carriers = carry.carriers.get(name).map_or(&[][..], Vec::as_slice);
tally::add(Work::WalkSteps, steps);
charge(
self,
steps * WALK_STEP_BYTES
+ count * size_of::<bool>()
+ carriers.len() * btree_entry::<(&str, usize, usize), bool>(),
)?;
for &carrier in carriers {
carry
.answers
.insert((name, carrier, mode), reached.contains(&carrier));
}
Ok(reached.contains(&target))
}
fn ensure_spans(
&self,
graph: &mut Reach,
mode: usize,
decl: &UseDecl,
path: &str,
name: &str,
) -> Result<(), ExportError> {
if graph.spans[mode].is_some() {
return Ok(());
}
let succ = &graph.succ[mode];
let (spans, work) = dominator_spans(succ, self.meter, &decl.file, decl.line)
.map_err(|error| ExportError::storage(error, Some(format!("{path}::{name}"))))?;
let edges: usize = succ.iter().map(Vec::len).sum();
tally::add(Work::WalkSteps, work);
self.meter
.items(
work * WALK_STEP_BYTES
+ spans.len() * (size_of::<Option<(usize, usize)>>() + 6 * size_of::<usize>())
+ edges * 2 * size_of::<usize>(),
&decl.file,
Some(decl.line),
)
.map_err(|error| ExportError::CarryBudget {
path: format!("{path}::{name}"),
error,
})?;
graph.spans[mode] = Some(spans);
Ok(())
}
fn bound(
&self,
module: usize,
ns: Namespace,
name: &str,
) -> Result<Option<(Vec<ItemId>, bool)>, ExportError> {
let steps = Steps::Query(self.meter);
let bound = self.index.lookup_in(module, ns, name, None, steps);
Index::query_refusal(steps)
.map_err(|refused| ExportError::Budget(self.index.refused_load(refused)))?;
let Some((bound, from_glob)) = bound else {
return Ok(None);
};
self.charge(
vec_first::<ItemId>() + bound.len() * vec_slot::<ItemId>(),
self.module_item(module),
)?;
Ok(Some((bound.keys().copied().collect(), from_glob)))
}
fn unseen_globs(
&mut self,
visit: &Visit,
module: usize,
hidden: bool,
) -> Result<(), ExportError> {
let index = self.index;
for &glob in index.globs_of(module) {
let decl = &index.uses[glob];
if !exporting(decl) {
continue;
}
let path = format!("{}::*", visit.path);
match index.glob_targets(glob, Steps::Query(self.meter)) {
Ok(_) => {}
Err(Fail::Missing(_)) => {
if index
.glob_broken(glob, self.meter)
.map_err(ExportError::Budget)?
{
return Err(ExportError::Resolve(index.glob_error(glob, &path)));
}
self.keep_reexport(
path,
written(decl),
None,
decl.file.clone(),
decl.line,
visit.hidden || hidden || decl.doc_hidden,
)?;
}
Err(Fail::SeveralCrates { roots: ids, .. } | Fail::Ambiguous(ids)) => {
return Err(ExportError::Resolve(ResolveError::Ambiguous(ids)));
}
Err(Fail::SuperAboveRoot) => {
return Err(ExportError::Resolve(ResolveError::Invalid(path)));
}
Err(Fail::Budget(refused)) => {
return Err(ExportError::Budget(index.refused_load(refused)));
}
Err(Fail::Storage(error)) => return Err(ExportError::storage(error, None)),
}
}
Ok(())
}
fn unbound_imports(
&mut self,
visit: &Visit,
module: usize,
hidden: bool,
mut carry: Option<&mut Carry<'a>>,
) -> Result<(), ExportError> {
let index = self.index;
let at_path = &index.modules[module].path;
let package = index.targets[index.modules[module].target.index()].package_id;
for &position in index.named_of(module) {
let decl = &index.uses[position];
if !exporting(decl) || index.use_bound[position].iter().any(|bound| *bound) {
continue;
}
let UseKind::Named {
name, namespaces, ..
} = &decl.kind
else {
continue;
};
let hidden = match carry.as_deref_mut() {
Some(carry) => match self.carried(visit, position, module, name.as_str(), carry)? {
Some(hidden) => hidden,
None => continue,
},
None => hidden,
};
match index.resolve(
&format!("{at_path}::{name}"),
match namespaces {
crate::index::NamedNamespaces::All => None,
crate::index::NamedNamespaces::TypeOnly => Some(Namespace::Type),
},
Some(package),
self.meter,
) {
Err(ResolveError::NotFound(_)) => self.keep_reexport(
format!("{}::{name}", visit.path),
written(decl),
None,
decl.file.clone(),
decl.line,
visit.hidden || hidden || decl.doc_hidden,
)?,
Err(ResolveError::Budget {
budget,
limit,
file,
line,
}) => return Err(ExportError::Budget(over_budget(budget, limit, &file, line))),
Err(other) => return Err(ExportError::Resolve(other)),
Ok(_) => {}
}
}
Ok(())
}
fn binding(
&mut self,
visit: &Visit,
name: &str,
id: ItemId,
at: usize,
by: By,
) -> Result<Option<Visit>, ExportError> {
let index = self.index;
let module = visit.module;
let path = format!("{}::{name}", visit.path);
let item = &index.items[id.0];
let child = (item.kind == SymbolKind::Mod)
.then(|| index.module_of.get(&id).copied())
.flatten();
let doc_hidden = visit.hidden
|| item.doc_hidden
|| child.is_some_and(|child| {
self.hidden_files
.contains(index.modules[child].path.as_str())
})
|| self.reexport_hidden(module, at, name, id, by)?;
if let Some(named) = self.other_crate(id) {
let (written, file, line) = self.binding_site(module, at, name, id, by)?;
self.keep_reexport(path, written, named.item(), file, line, doc_hidden)?;
return Ok(None);
}
self.keep(path.clone(), id, doc_hidden)?;
if doc_hidden && !self.options.include_hidden {
return Ok(None);
}
match item.kind {
SymbolKind::Struct | SymbolKind::Enum | SymbolKind::Union | SymbolKind::Trait => {
self.members(&path, id, doc_hidden)?;
Ok(None)
}
_ => Ok(child.map(|child| Visit {
module: child,
path,
hidden: doc_hidden,
})),
}
}
fn members(
&mut self,
owner_path: &str,
owner: ItemId,
hidden: bool,
) -> Result<(), ExportError> {
let index = self.index;
let Some(table) = index.assoc.get(&owner) else {
return Ok(());
};
let of_trait = index.items[owner.0].kind == SymbolKind::Trait;
for (name, ids) in table {
for id in index.sorted(ids.iter().copied()) {
let member = &index.items[id.0];
if member.test != TestRole::None
|| member.target != self.target
|| member.trait_path.is_some()
|| (!of_trait && member.visibility != Vis::Public)
{
continue;
}
self.keep(
format!("{owner_path}::{name}"),
id,
hidden || member.doc_hidden,
)?;
}
}
Ok(())
}
}
#[cfg(test)]
mod tests;