Skip to main content

raf_source/
exports.rs

1// SPDX-FileCopyrightText: 2026 Blackcat InformaticsĀ® Inc. <paudley@blackcatinformatics.ca>
2// SPDX-License-Identifier: MIT OR Apache-2.0 OR MulanPSL-2.0
3
4//! The exported items of a target: what another crate can name through its
5//! crate root.
6//!
7//! The surface is read from the settled scope tables (see [`crate::settle`]),
8//! breadth first from the crate root through the modules that a public
9//! binding reaches. A binding is public when it has a public route back to a
10//! public definition: each `use` declaration on the way, named or glob, is
11//! `pub` and not test code, and the definition is `pub` (a macro is
12//! `#[macro_export]`). That is rustc's rule: an import of a binding that is
13//! less visible than the import is refused, and a glob brings each name in no
14//! more visible than the binding it reads, so one hop that is not `pub` keeps
15//! the name out. The route is searched over every glob that brings the item
16//! in, not only the one the tables keep, so an item that a public glob and a
17//! private one both bring in is exported.
18//!
19//! Every binding of the surface is checked as the resolver checks the last
20//! segment of a path (see [`Index::binding_failure`]), and the modules of a
21//! path are each reached through such a binding, so a name that is
22//! ambiguous, that goes through a cycle of imports or that reads a glob whose
23//! path names nothing fails the query with the error
24//! [`Index::resolve`] gives for its path, as it fails a lookup.
25//!
26//! What the surface holds is charged to the item-bytes budget after what the
27//! load spent, by the layout rules of `crate::cost`, before it is kept. A few
28//! temporaries are not charged, each bounded by what the load already charged
29//! and dropped before the next is made: the search for the public route of one
30//! binding (the places it has seen, at most the bindings of the
31//! tables) and the items one name binds. What carrying the re-exports of the
32//! modules a reader's globs reach takes, its walk, its graph and tree of
33//! dominators, its searches and their answers, is charged, the work of each
34//! step included (see `Surface::carried`).
35
36use std::collections::{BTreeMap, BTreeSet, VecDeque};
37use std::error::Error;
38use std::fmt;
39use std::mem::size_of;
40use std::rc::Rc;
41
42use purrdf_lex::walk::WorkList;
43
44use crate::cost::{btree_entry, btree_map, vec_first, vec_slot};
45use crate::error::{Esc, LoadError, LoadErrorKind};
46use crate::facts::{SpanFact, TestRole, Vis};
47use crate::index::{Index, UseDecl, UseKind};
48use crate::item::{ItemId, Namespace, SymbolKind};
49use crate::meter::{Meter, Steps, over_budget, push_item_work};
50use crate::modtree::TargetId;
51use crate::path::RelPath;
52use crate::resolve::{Fail, ResolveError};
53use crate::settle::slot;
54use crate::work::{self as tally, Work};
55
56/// What [`Workspace::exported_items_with`](crate::Workspace::exported_items_with)
57/// lists.
58///
59/// The options are `#[non_exhaustive]`: a caller starts from
60/// `ExportOptions::default()` and sets the fields it needs, so adding an
61/// option is not a breaking change.
62#[derive(Debug, Clone, Default, PartialEq, Eq)]
63#[non_exhaustive]
64pub struct ExportOptions {
65    /// List the items and re-exports that `#[doc(hidden)]` hides as well,
66    /// each with [`ExportedItem::doc_hidden`] set. False by default, which
67    /// leaves them out.
68    pub include_hidden: bool,
69}
70
71/// One item of a target's public surface, under one path that another crate
72/// can name it by.
73///
74/// The struct is `#[non_exhaustive]`: adding a field is not a breaking change,
75/// so a pattern names the fields it reads and ends in `..`.
76#[derive(Debug, Clone, PartialEq, Eq)]
77#[non_exhaustive]
78pub struct ExportedItem {
79    /// The path from the crate root, starting with the target's crate path:
80    /// the exported name, which differs from the defining item's own path for
81    /// a re-export (`demo::run` for `pub use inner::go as run;`).
82    pub path: String,
83    /// The defining item, so a re-export maps back to it.
84    pub item: ItemId,
85    /// What the defining item is.
86    pub kind: SymbolKind,
87    /// The file that defines the item.
88    pub file: RelPath,
89    /// The whole defining item, attributes included.
90    pub span: SpanFact,
91    /// True when `#[doc(hidden)]` hides the path: on the item, on a module of
92    /// the path (on its declaration or as `#![doc(hidden)]` in its file), on
93    /// the `use` declaration that exports it, or on the type or trait whose
94    /// member it is.
95    pub doc_hidden: bool,
96}
97
98/// A public re-export of a target that names nothing the target itself
99/// defines as an item of the index: an item of another crate of the
100/// workspace, a crate outside the workspace or one of its items, an enum
101/// variant (variants are not items of the index), or a path the index cannot
102/// follow, such as an item a macro generates. A public glob carries such a
103/// re-export of a module it reaches into the module that reads it, under the
104/// reader's path.
105///
106/// The struct is `#[non_exhaustive]`: adding a field is not a breaking change.
107#[derive(Debug, Clone, PartialEq, Eq)]
108#[non_exhaustive]
109pub struct Reexport {
110    /// The exported path from the crate root, starting with the target's
111    /// crate path; `<module>::*` for a glob.
112    pub path: String,
113    /// The path the declaration names, as written (`serde::Serialize`,
114    /// `serde::*`, or the crate of an `extern crate` item).
115    pub written: String,
116    /// The item it names, when the index sees one: an item of another crate
117    /// of the workspace, or that crate's root. `None` for a crate outside the
118    /// workspace and for a path the index cannot follow.
119    pub item: Option<ItemId>,
120    /// The file of the declaration.
121    pub file: RelPath,
122    /// The 1-based line of the declaration.
123    pub line: usize,
124    /// True when `#[doc(hidden)]` hides the re-export, on the declaration or
125    /// on a module of its path.
126    pub doc_hidden: bool,
127}
128
129/// The public surface of a target, as
130/// [`Workspace::exported_items`](crate::Workspace::exported_items) returns it.
131///
132/// The struct is `#[non_exhaustive]`: adding a field is not a breaking change.
133#[derive(Debug, Clone, Default, PartialEq, Eq)]
134#[non_exhaustive]
135pub struct Exports {
136    /// The items of the target that another crate can name, sorted by path,
137    /// then by the order of [`Workspace::items`](crate::Workspace::items) of
138    /// the defining item.
139    pub items: Vec<ExportedItem>,
140    /// The public re-exports that name nothing the target defines, sorted by
141    /// path, file and line.
142    pub reexports: Vec<Reexport>,
143}
144
145/// Why the public surface of a target could not be listed.
146#[derive(Debug)]
147#[non_exhaustive]
148pub enum ExportError {
149    /// The id names no library or binary target of the workspace: only
150    /// those have a crate root that is a public surface.
151    NotLibraryOrBinary(TargetId),
152    /// What the surface holds passes the item-bytes budget left after the
153    /// load: a `Budget` load error naming the budget, its limit and the file
154    /// and line of the item whose entry passed it.
155    Budget(LoadError),
156    /// Native traversal storage failed its physical layout or allocation.
157    /// The load error preserves the original file, line and source cause.
158    Storage(LoadError),
159    /// Deciding whether the public globs of a module of the surface carry
160    /// the re-export at `path` from a module they reach passes the
161    /// item-bytes budget left after the load, which charges the work of that
162    /// decision: `error` is the `Budget` load error, naming the file and line
163    /// of the carried `use` declaration.
164    CarryBudget {
165        /// The exported path of the re-export being decided.
166        path: String,
167        /// The `Budget` load error.
168        error: LoadError,
169    },
170    /// A public name of the surface does not resolve: it is ambiguous, goes
171    /// through a cycle of imports, or reads a glob whose path names nothing
172    /// in the workspace, as [`Workspace::resolve`](crate::Workspace::resolve)
173    /// reports it for that path.
174    Resolve(ResolveError),
175}
176
177impl fmt::Display for ExportError {
178    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
179        match self {
180            Self::NotLibraryOrBinary(id) => write!(
181                f,
182                "target {} is not a library or a binary of the workspace",
183                id.index()
184            ),
185            Self::Budget(error) => write!(f, "the public surface is over budget: {error}"),
186            Self::Storage(error) => write!(f, "the public surface storage failed: {error}"),
187            Self::CarryBudget { path, error } => write!(
188                f,
189                "deciding whether the public globs carry the re-export `{}` is over budget: {error}",
190                Esc(path)
191            ),
192            Self::Resolve(error) => write!(f, "a public name does not resolve: {error}"),
193        }
194    }
195}
196
197impl Error for ExportError {
198    fn source(&self) -> Option<&(dyn Error + 'static)> {
199        match self {
200            Self::NotLibraryOrBinary(_) => None,
201            Self::Budget(error) | Self::Storage(error) | Self::CarryBudget { error, .. } => {
202                Some(error)
203            }
204            Self::Resolve(error) => Some(error),
205        }
206    }
207}
208
209impl ExportError {
210    /// Preserve actual budget ownership without mislabeling a physical failure.
211    fn storage(error: LoadError, carried: Option<String>) -> Self {
212        if matches!(error.kind, LoadErrorKind::Budget { .. }) {
213            match carried {
214                Some(path) => Self::CarryBudget { path, error },
215                None => Self::Budget(error),
216            }
217        } else {
218            Self::Storage(error)
219        }
220    }
221}
222
223/// A view that the public globs of a module read: the module it exports, the
224/// first public glob that reads it, and whether every public glob that reads
225/// it is `#[doc(hidden)]`.
226#[derive(Debug, Clone, Copy)]
227struct Route {
228    view: usize,
229    target: usize,
230    glob: usize,
231    hidden: bool,
232}
233
234/// The public routes of a module, with the routes whose view holds each
235/// name, so a name's routes are found without reading every route.
236struct Routes<'a> {
237    list: Vec<Route>,
238    by_name: BTreeMap<&'a str, Vec<usize>>,
239}
240
241impl Routes<'_> {
242    /// The routes whose view holds `name`, in order of view.
243    fn holding(&self, name: &str) -> impl Iterator<Item = &Route> + '_ {
244        self.by_name
245            .get(name)
246            .into_iter()
247            .flatten()
248            .map(|at| &self.list[*at])
249    }
250}
251
252/// What carrying the re-exports of the modules a reader's routes reach works
253/// with, for one reader: the reach as a graph, the modules of the reach that
254/// bind each name themselves (the reader included, sorted), the modules of
255/// the reach that carry each name, and the answers decided by a search, one
256/// for each name and carrying module. No search keeps what it walked.
257struct Carry<'a> {
258    graph: Reach,
259    binders: BTreeMap<&'a str, Vec<usize>>,
260    carriers: BTreeMap<&'a str, Vec<usize>>,
261    answers: BTreeMap<(&'a str, usize, usize), bool>,
262}
263
264/// The modules a reader's public routes reach, as a graph: node 0 is the
265/// reader, each other node a module of the reach in the order of the walk,
266/// with the nodes its routes lead to, once over the routes that
267/// `#[doc(hidden)]` does not hide ([`SHOWN`]: every route but those that leave
268/// the reader by a hidden glob, as for an item) and once over every route
269/// ([`EVERY`]), whether the shown routes reach each node, and, once a carried
270/// name needs it, the tree of dominators of each (a node dominates another
271/// when every route from the reader to the other passes it), as the interval
272/// each node the routes reach spans in a walk of the tree.
273struct Reach {
274    modules: Vec<usize>,
275    node_of: BTreeMap<usize, usize>,
276    succ: [Vec<Vec<usize>>; 2],
277    shown: Vec<bool>,
278    spans: [Option<Spans>; 2],
279}
280
281/// The interval of each node in a walk of a tree of dominators, `None` for a
282/// node the routes do not reach.
283type Spans = Vec<Option<(usize, usize)>>;
284
285/// The routes of a [`Reach`] that `#[doc(hidden)]` does not hide.
286const SHOWN: usize = 0;
287/// Every route of a [`Reach`].
288const EVERY: usize = 1;
289
290impl Reach {
291    /// True when, over the routes of `mode`, the node `above` dominates the
292    /// node `below`.
293    fn dominates(&self, mode: usize, above: usize, below: usize) -> bool {
294        match self.spans[mode]
295            .as_ref()
296            .map(|spans| (spans[above], spans[below]))
297        {
298            Some((Some(above), Some(below))) => above.0 <= below.0 && below.1 <= above.1,
299            _ => false,
300        }
301    }
302}
303
304/// The interval of each node that node 0 reaches in a walk of the tree of
305/// dominators of `succ` (`None` for a node it does not reach), by the
306/// iterative algorithm of Cooper,
307/// Harvey and Kennedy over a reverse postorder, and the work it did: a unit
308/// for each node and each edge each pass reads, and for each step of the
309/// intersections.
310fn dominator_spans(
311    succ: &[Vec<usize>],
312    meter: &Meter,
313    file: &RelPath,
314    line: usize,
315) -> Result<(Spans, usize), LoadError> {
316    let count = succ.len();
317    let mut work = 0;
318    // A postorder from node 0, on a stack of its own.
319    let mut post = vec![usize::MAX; count];
320    let mut order = Vec::with_capacity(count);
321    let mut stack = WorkList::<_, 8>::new();
322    push_item_work(&mut stack, (0, 0), meter, file, Some(line))?;
323    let mut entered = vec![false; count];
324    entered[0] = true;
325    while let Some((node, next)) = stack.pop() {
326        work += 1;
327        if let Some(&to) = succ[node].get(next) {
328            push_item_work(&mut stack, (node, next + 1), meter, file, Some(line))?;
329            if !entered[to] {
330                entered[to] = true;
331                push_item_work(&mut stack, (to, 0), meter, file, Some(line))?;
332            }
333        } else {
334            post[node] = order.len();
335            order.push(node);
336        }
337    }
338    let mut preds: Vec<Vec<usize>> = vec![Vec::new(); count];
339    for (from, tos) in succ.iter().enumerate() {
340        if post[from] == usize::MAX {
341            continue;
342        }
343        for &to in tos {
344            preds[to].push(from);
345        }
346    }
347    let mut idom = vec![usize::MAX; count];
348    idom[0] = 0;
349    let mut changed = true;
350    while changed {
351        changed = false;
352        for &node in order.iter().rev().skip(1) {
353            let mut new = usize::MAX;
354            for &pred in &preds[node] {
355                work += 1;
356                if idom[pred] == usize::MAX {
357                    continue;
358                }
359                if new == usize::MAX {
360                    new = pred;
361                    continue;
362                }
363                let (mut a, mut b) = (pred, new);
364                while a != b {
365                    while post[a] < post[b] {
366                        a = idom[a];
367                        work += 1;
368                    }
369                    while post[b] < post[a] {
370                        b = idom[b];
371                        work += 1;
372                    }
373                }
374                new = a;
375            }
376            if idom[node] != new {
377                idom[node] = new;
378                changed = true;
379            }
380        }
381    }
382    let mut children: Vec<Vec<usize>> = vec![Vec::new(); count];
383    for node in 1..count {
384        if post[node] != usize::MAX {
385            children[idom[node]].push(node);
386        }
387    }
388    let mut spans: Spans = vec![None; count];
389    let mut clock = 0;
390    let mut stack = WorkList::<_, 8>::new();
391    push_item_work(&mut stack, (0, 0), meter, file, Some(line))?;
392    while let Some((node, next)) = stack.pop() {
393        work += 1;
394        if next == 0 {
395            spans[node] = Some((clock, clock));
396            clock += 1;
397        }
398        if let Some(&child) = children[node].get(next) {
399            push_item_work(&mut stack, (node, next + 1), meter, file, Some(line))?;
400            push_item_work(&mut stack, (child, 0), meter, file, Some(line))?;
401        } else if let Some(span) = spans[node].as_mut() {
402            span.1 = clock;
403            clock += 1;
404        }
405    }
406    Ok((spans, work))
407}
408
409/// What a step of a walk of the reach is charged: the binding it keeps of
410/// the module it passes, an upper bound of what one step holds, so the work
411/// of the walks is bounded with their memory by the item-bytes budget.
412const WALK_STEP_BYTES: usize = btree_entry::<usize, bool>();
413
414/// A binding the search for a public route reads: the item, and the name in a
415/// module in the name space at a slot that binds it.
416type Place = (ItemId, usize, usize, String);
417
418/// A module waiting to be read, at the first path the search reached it by.
419struct Visit {
420    module: usize,
421    path: String,
422    hidden: bool,
423}
424
425/// What a binding of another crate names: an item the index sees (an item of
426/// another crate of the workspace, or that crate's root), or a crate outside
427/// the workspace.
428#[derive(Debug, Clone, Copy, PartialEq, Eq)]
429enum Other {
430    Seen(ItemId),
431    Outside,
432}
433
434impl Other {
435    fn item(self) -> Option<ItemId> {
436        match self {
437            Self::Seen(id) => Some(id),
438            Self::Outside => None,
439        }
440    }
441}
442
443/// What a public binding is bound by in its module: a definition or an
444/// explicit import, or the module's globs.
445#[derive(Debug, Clone, Copy, PartialEq, Eq)]
446enum By {
447    Explicit,
448    Glob,
449}
450
451/// What one listing of a surface works with.
452pub(crate) struct Surface<'a> {
453    index: &'a Index,
454    target: TargetId,
455    root: usize,
456    crate_path: &'a str,
457    options: &'a ExportOptions,
458    meter: &'a Meter,
459    /// The module paths of the target whose file has `#![doc(hidden)]`.
460    hidden_files: &'a BTreeSet<&'a str>,
461    /// The public routes of each module the search has read.
462    routes: BTreeMap<usize, Rc<Routes<'a>>>,
463    /// Whether each place a search for a public route decided has one.
464    decided: BTreeMap<Place, bool>,
465    items: Vec<ExportedItem>,
466    reexports: Vec<Reexport>,
467}
468
469/// The path a `use` declaration names, as written.
470fn written(decl: &UseDecl) -> String {
471    let (segs, glob) = match &decl.kind {
472        UseKind::Named { segs, .. } => (segs, false),
473        UseKind::Glob { segs } => (segs, true),
474    };
475    let mut text = String::new();
476    if decl.leading_colon {
477        text.push_str("::");
478    }
479    text.push_str(&segs.join("::"));
480    if glob {
481        text.push_str("::*");
482    }
483    text
484}
485
486/// True when the `use` declaration can carry a name out of its crate: it is
487/// `pub` and not test code.
488fn exporting(decl: &UseDecl) -> bool {
489    decl.vis == Vis::Public && !decl.test
490}
491
492impl<'a> Surface<'a> {
493    /// A listing of the surface of `target`, a library or a binary whose
494    /// crate root is the module `root`.
495    pub(crate) fn new(
496        index: &'a Index,
497        target: TargetId,
498        crate_path: &'a str,
499        options: &'a ExportOptions,
500        meter: &'a Meter,
501        hidden_files: &'a BTreeSet<&'a str>,
502    ) -> Self {
503        Self {
504            index,
505            target,
506            root: index.target_roots[target.index()],
507            crate_path,
508            options,
509            meter,
510            hidden_files,
511            routes: BTreeMap::new(),
512            decided: BTreeMap::new(),
513            items: Vec::new(),
514            reexports: Vec::new(),
515        }
516    }
517
518    /// Charge `bytes` held for the item `id`.
519    fn charge(&self, bytes: usize, id: ItemId) -> Result<(), ExportError> {
520        let item = &self.index.items[id.0];
521        self.meter
522            .items(bytes, &item.file, Some(item.name_line))
523            .map_err(ExportError::Budget)
524    }
525
526    /// The item that stands for `module`: its crate root or its `mod` item.
527    fn module_item(&self, module: usize) -> ItemId {
528        self.index
529            .module_items(module)
530            .first()
531            .copied()
532            .unwrap_or_else(|| self.index.root_items[&self.index.modules[module].root])
533    }
534
535    /// List the surface: every module a public binding reaches, read once at
536    /// the first path that reaches it, breadth first, a path that
537    /// `#[doc(hidden)]` does not hide before one that it does.
538    pub(crate) fn list(mut self) -> Result<Exports, ExportError> {
539        let index = self.index;
540        let root_item = index.root_items[&self.root];
541        self.charge(
542            vec_first::<ExportedItem>()
543                + vec_first::<Reexport>()
544                + 2 * vec_first::<Visit>()
545                + index.modules.len() * size_of::<bool>()
546                + btree_map::<usize, Vec<Route>>(),
547            root_item,
548        )?;
549        let mut visited = vec![false; index.modules.len()];
550        let mut shown: VecDeque<Visit> = VecDeque::new();
551        let mut hidden: VecDeque<Visit> = VecDeque::new();
552        let start = Visit {
553            module: self.root,
554            path: self.crate_path.to_owned(),
555            hidden: index.items[root_item.0].doc_hidden,
556        };
557        self.charge(vec_slot::<Visit>() + start.path.capacity(), root_item)?;
558        if start.hidden {
559            if self.options.include_hidden {
560                hidden.push_back(start);
561            }
562        } else {
563            visited[self.root] = true;
564            shown.push_back(start);
565        }
566        loop {
567            let visit = match shown.pop_front() {
568                Some(visit) => visit,
569                None => match hidden.pop_front() {
570                    Some(visit) if visited[visit.module] => continue,
571                    Some(visit) => {
572                        visited[visit.module] = true;
573                        visit
574                    }
575                    None => break,
576                },
577            };
578            let found = self.module(&visit)?;
579            for next in found {
580                if visited[next.module] {
581                    continue;
582                }
583                self.charge(
584                    vec_slot::<Visit>() + next.path.capacity(),
585                    self.module_item(next.module),
586                )?;
587                if next.hidden {
588                    hidden.push_back(next);
589                } else {
590                    visited[next.module] = true;
591                    shown.push_back(next);
592                }
593            }
594        }
595        let Self {
596            mut items,
597            mut reexports,
598            ..
599        } = self;
600        items.sort_by(|a, b| {
601            (a.path.as_str(), index.sort_key(a.item))
602                .cmp(&(b.path.as_str(), index.sort_key(b.item)))
603        });
604        reexports.sort_by(|a, b| {
605            (&a.path, &a.file, a.line, &a.written, a.item)
606                .cmp(&(&b.path, &b.file, b.line, &b.written, b.item))
607        });
608        Ok(Exports { items, reexports })
609    }
610
611    /// The public routes of `module`: the views its `pub` globs that are not
612    /// test code read, once each, in order of view, and for each name the
613    /// routes whose view holds it. Made and charged once for the listing.
614    fn routes(&mut self, module: usize) -> Result<Rc<Routes<'a>>, ExportError> {
615        if let Some(known) = self.routes.get(&module) {
616            return Ok(Rc::clone(known));
617        }
618        let index = self.index;
619        let mut by_view: BTreeMap<usize, Route> = BTreeMap::new();
620        for (glob, target, view) in index.glob_reads(module) {
621            let decl = &index.uses[glob];
622            if !exporting(decl) {
623                continue;
624            }
625            by_view
626                .entry(view)
627                .and_modify(|route| {
628                    route.glob = route.glob.min(glob);
629                    route.hidden &= decl.doc_hidden;
630                })
631                .or_insert(Route {
632                    view,
633                    target,
634                    glob,
635                    hidden: decl.doc_hidden,
636                });
637        }
638        let list: Vec<Route> = by_view.into_values().collect();
639        let mut held = 0;
640        let mut by_name: BTreeMap<&'a str, Vec<usize>> = BTreeMap::new();
641        for (at, route) in list.iter().enumerate() {
642            for name in index.view_names(route.view) {
643                by_name.entry(name).or_default().push(at);
644                held += 1;
645            }
646        }
647        self.charge(
648            btree_entry::<usize, Rc<Routes<'a>>>()
649                + size_of::<Routes<'a>>()
650                + 2 * size_of::<usize>()
651                + list.capacity() * size_of::<Route>()
652                + btree_map::<&str, Vec<usize>>()
653                + by_name.len() * (btree_entry::<&str, Vec<usize>>() + vec_first::<usize>())
654                + held * vec_slot::<usize>(),
655            self.module_item(module),
656        )?;
657        let routes = Rc::new(Routes { list, by_name });
658        self.routes.insert(module, Rc::clone(&routes));
659        Ok(routes)
660    }
661
662    /// The modules that the public routes of `start` reach, directly or through
663    /// the public routes of the modules they reach, each once, with whether
664    /// `#[doc(hidden)]` hides every such route, as it hides an item: a route
665    /// is hidden when the glob of `start` it leaves by is, whatever the
666    /// globs after it, and a module that a shown route reaches is shown. Each module the walk passes, in either of its two
667    /// passes, is charged a binding of the walk, so the walks of a listing
668    /// are bounded by the item-bytes budget with what they hold.
669    fn glob_reach(&mut self, start: usize) -> Result<Vec<(usize, bool)>, ExportError> {
670        let mut seen: BTreeMap<usize, bool> = BTreeMap::new();
671        let mut order = Vec::new();
672        let at = self.module_item(start);
673        // Shown routes first, then every route, so a module keeps the first
674        // shown route that reaches it.
675        for with_hidden in [false, true] {
676            let mut work = VecDeque::from([(start, false)]);
677            let mut entered = BTreeSet::from([start]);
678            while let Some((module, hidden)) = work.pop_front() {
679                tally::add(Work::WalkSteps, 1);
680                self.charge(WALK_STEP_BYTES, at)?;
681                if module != start
682                    && let std::collections::btree_map::Entry::Vacant(slot) = seen.entry(module)
683                {
684                    slot.insert(hidden);
685                    order.push(module);
686                }
687                for route in &self.routes(module)?.list {
688                    // As for an item, only the reader's own globs hide what
689                    // they bring in: a hidden glob further on does not.
690                    let shown = !route.hidden || module != start;
691                    if (with_hidden || shown) && entered.insert(route.target) {
692                        work.push_back((route.target, hidden || !shown));
693                    }
694                }
695            }
696        }
697        Ok(order
698            .into_iter()
699            .map(|module| (module, seen[&module]))
700            .collect())
701    }
702
703    /// True when the item `id` is declared so that another crate can name
704    /// it: `pub`, or `#[macro_export]` for a macro. That it is not test code
705    /// is checked before its route is searched.
706    fn declared_public(&self, id: ItemId) -> bool {
707        let item = &self.index.items[id.0];
708        match item.kind {
709            SymbolKind::MacroRules => item.macro_export,
710            _ => item.visibility == Vis::Public,
711        }
712    }
713
714    /// The `pub` named imports of `name` in `module` that are not test code
715    /// and bound something in the name space at `at`, in order of position.
716    fn exporting_imports(&self, module: usize, name: &str, at: usize) -> Vec<usize> {
717        let index = self.index;
718        index
719            .imports_of(module, name)
720            .iter()
721            .copied()
722            .filter(|position| index.use_bound[*position][at] && exporting(&index.uses[*position]))
723            .collect()
724    }
725
726    /// True when the binding of `id` under `name` in `module`, in the name
727    /// space at `at`, has a public route: every `use` declaration from the
728    /// binding back to the definition is `pub` and not test code, and the
729    /// definition is public.
730    ///
731    /// The search keeps a stack and the places it has seen, each with the
732    /// place it was reached from, of its own, so a cycle of globs ends it and
733    /// its depth costs the caller's stack nothing. What it decides is kept for
734    /// the listing: the places on the route it found have a public route, and
735    /// when it finds none, no place it saw has one, as it saw every place they
736    /// lead to. So a chain of re-exports is walked once for all its names.
737    fn public_route(
738        &mut self,
739        module: usize,
740        at: usize,
741        name: &str,
742        id: ItemId,
743    ) -> Result<bool, ExportError> {
744        let index = self.index;
745        let start: Place = (id, module, at, name.to_owned());
746        let mut from: BTreeMap<Place, Option<Place>> = BTreeMap::new();
747        let mut work = WorkList::<_, 8>::new();
748        let item = &index.items[id.0];
749        let meter = self.meter;
750        let push = |work: &mut WorkList<_, 8>, value| {
751            push_item_work(work, value, meter, &item.file, Some(item.name_line))
752                .map_err(|error| ExportError::storage(error, None))
753        };
754        push(&mut work, (start, None))?;
755        let mut found = None;
756        while let Some((place, parent)) = work.pop() {
757            if from.contains_key(&place) {
758                continue;
759            }
760            from.insert(place.clone(), parent);
761            match self.decided.get(&place) {
762                Some(true) => {
763                    found = Some(place);
764                    break;
765                }
766                Some(false) => continue,
767                None => {}
768            }
769            let (_, module, at, name) = &place;
770            let (module, at) = (*module, *at);
771            let defs = index.scopes[module]
772                .get(name)
773                .map(|entry| &entry.defs[at])
774                .filter(|defs| !defs.is_empty());
775            if let Some(defs) = defs {
776                let Some(origin) = defs.get(id) else {
777                    continue;
778                };
779                let next = match &origin.link {
780                    None => None,
781                    Some(_) if self.exporting_imports(module, name, at).is_empty() => continue,
782                    // A path that ends at a module and not at a name in it
783                    // binds the module's item, as a definition does.
784                    Some(link) => link.source.as_ref(),
785                };
786                match next {
787                    Some(source) => {
788                        let step = (id, source.module, slot(source.ns), source.name.clone());
789                        push(&mut work, (step, Some(place)))?;
790                    }
791                    None if self.declared_public(id) => {
792                        found = Some(place);
793                        break;
794                    }
795                    None => {}
796                }
797            } else if !index.blocked(module, name, Namespace::ALL[at], None) {
798                let routes = self.routes(module)?;
799                for route in routes.holding(name) {
800                    if index.view_holds(route.view, name, at, id) {
801                        let step = (id, route.target, at, name.clone());
802                        push(&mut work, (step, Some(place.clone())))?;
803                    }
804                }
805            }
806        }
807        let decided: Vec<(Place, bool)> = match found {
808            Some(mut place) => {
809                let mut route = Vec::new();
810                loop {
811                    let parent = from.get(&place).cloned().flatten();
812                    route.push((place, true));
813                    match parent {
814                        Some(next) => place = next,
815                        None => break,
816                    }
817                }
818                route
819            }
820            None => from.into_keys().map(|place| (place, false)).collect(),
821        };
822        let reached = !decided.is_empty() && decided[0].1;
823        for (place, public) in decided {
824            if let std::collections::btree_map::Entry::Vacant(slot) = self.decided.entry(place) {
825                self.meter
826                    .items(
827                        btree_entry::<Place, bool>() + slot.key().3.capacity(),
828                        &index.items[id.0].file,
829                        Some(index.items[id.0].name_line),
830                    )
831                    .map_err(ExportError::Budget)?;
832                slot.insert(public);
833            }
834        }
835        Ok(reached)
836    }
837
838    /// The public routes of `module` that carry `id` under `name` in the name
839    /// space at `at` out of the crate: those whose view holds it and whose
840    /// target binds it with a public route of its own (see
841    /// [`Surface::public_route`]). A glob whose view holds the item but whose
842    /// target keeps it in, behind a binding that is not `pub` or an import
843    /// that shadows it, does not export it, whatever its visibility.
844    fn carrying_routes(
845        &mut self,
846        module: usize,
847        at: usize,
848        name: &str,
849        id: ItemId,
850    ) -> Result<Vec<Route>, ExportError> {
851        let index = self.index;
852        let routes = self.routes(module)?;
853        let mut carrying = Vec::new();
854        for route in routes.holding(name) {
855            if index.view_holds(route.view, name, at, id)
856                && self.public_route(route.target, at, name, id)?
857            {
858                carrying.push(*route);
859            }
860        }
861        Ok(carrying)
862    }
863
864    /// True when the `use` declarations that export `id` under `name` in
865    /// `module` are all `#[doc(hidden)]`.
866    fn reexport_hidden(
867        &mut self,
868        module: usize,
869        at: usize,
870        name: &str,
871        id: ItemId,
872        by: By,
873    ) -> Result<bool, ExportError> {
874        let index = self.index;
875        Ok(match by {
876            By::Explicit => {
877                let imported = index.scopes[module]
878                    .get(name)
879                    .and_then(|entry| entry.defs[at].get(id))
880                    .is_some_and(|origin| origin.link.is_some());
881                let imports = self.exporting_imports(module, name, at);
882                imported
883                    && !imports.is_empty()
884                    && imports
885                        .iter()
886                        .all(|position| index.uses[*position].doc_hidden)
887            }
888            By::Glob => {
889                let carrying = self.carrying_routes(module, at, name, id)?;
890                !carrying.is_empty() && carrying.iter().all(|route| route.hidden)
891            }
892        })
893    }
894
895    /// The declaration that exports `id` under `name` in `module`, as written,
896    /// with its file and line: the first `pub` import of the name, the first
897    /// `pub` glob that brings the item in, or the item itself for an
898    /// `extern crate` item.
899    fn binding_site(
900        &mut self,
901        module: usize,
902        at: usize,
903        name: &str,
904        id: ItemId,
905        by: By,
906    ) -> Result<(String, RelPath, usize), ExportError> {
907        let index = self.index;
908        let decl = match by {
909            By::Explicit => self
910                .exporting_imports(module, name, at)
911                .first()
912                .map(|position| &index.uses[*position]),
913            By::Glob => self
914                .carrying_routes(module, at, name, id)?
915                .iter()
916                .map(|route| route.glob)
917                .min()
918                .map(|glob| &index.uses[glob]),
919        };
920        if let Some(decl) = decl {
921            return Ok((written(decl), decl.file.clone(), decl.line));
922        }
923        let item = &index.items[id.0];
924        let crate_name = index
925            .extern_names
926            .get(&id)
927            .map_or_else(|| item.name.to_string(), ToString::to_string);
928        Ok((crate_name, item.file.clone(), item.name_line))
929    }
930
931    /// `Some` when the binding of `id` names another crate: an item of
932    /// another target, or an `extern crate` item of a crate other than this
933    /// one, which stands for that crate's root when the index sees it.
934    fn other_crate(&self, id: ItemId) -> Option<Other> {
935        let index = self.index;
936        let item = &index.items[id.0];
937        if item.target != self.target {
938            return Some(Other::Seen(id));
939        }
940        if item.kind == SymbolKind::ExternCrate {
941            return match index.crate_of.get(&id) {
942                None => Some(Other::Outside),
943                Some(roots) if roots.contains(&self.root) => None,
944                Some(roots) => Some(
945                    roots
946                        .first()
947                        .and_then(|root| index.root_items.get(root).copied())
948                        .map_or(Other::Outside, Other::Seen),
949                ),
950            };
951        }
952        None
953    }
954
955    /// Keep an item of the surface, unless `#[doc(hidden)]` hides it and the
956    /// options leave hidden items out.
957    fn keep(&mut self, path: String, id: ItemId, doc_hidden: bool) -> Result<(), ExportError> {
958        if doc_hidden && !self.options.include_hidden {
959            return Ok(());
960        }
961        self.charge(vec_slot::<ExportedItem>() + path.capacity(), id)?;
962        let item = &self.index.items[id.0];
963        self.items.push(ExportedItem {
964            path,
965            item: id,
966            kind: item.kind,
967            file: item.file.clone(),
968            span: item.span.clone(),
969            doc_hidden,
970        });
971        Ok(())
972    }
973
974    /// Keep a re-export, unless `#[doc(hidden)]` hides it and the options
975    /// leave hidden items out.
976    fn keep_reexport(
977        &mut self,
978        path: String,
979        written: String,
980        item: Option<ItemId>,
981        file: RelPath,
982        line: usize,
983        doc_hidden: bool,
984    ) -> Result<(), ExportError> {
985        if doc_hidden && !self.options.include_hidden {
986            return Ok(());
987        }
988        self.meter
989            .items(
990                vec_slot::<Reexport>() + path.capacity() + written.capacity(),
991                &file,
992                Some(line),
993            )
994            .map_err(ExportError::Budget)?;
995        self.reexports.push(Reexport {
996            path,
997            written,
998            item,
999            file,
1000            line,
1001            doc_hidden,
1002        });
1003        Ok(())
1004    }
1005
1006    /// Read one module of the surface: its public re-exports of what the
1007    /// index cannot see, and each public binding of each of its names.
1008    /// Returns the modules of the target its bindings reach.
1009    fn module(&mut self, visit: &Visit) -> Result<Vec<Visit>, ExportError> {
1010        let index = self.index;
1011        let (module, path) = (visit.module, visit.path.as_str());
1012        self.unseen(visit)?;
1013        let routes = self.routes(module)?;
1014        let mut names: BTreeSet<&'a str> =
1015            index.scopes[module].keys().map(String::as_str).collect();
1016        names.extend(routes.by_name.keys().copied());
1017        self.charge(
1018            btree_map::<&str, ()>() + names.len() * btree_entry::<&str, ()>(),
1019            self.module_item(module),
1020        )?;
1021        let mut next = Vec::new();
1022        for name in names {
1023            // The items the name exports, each with the first name space it is
1024            // exported in and what binds it there.
1025            let mut found: BTreeMap<ItemId, (usize, By)> = BTreeMap::new();
1026            for ns in Namespace::ALL {
1027                let at = slot(ns);
1028                let Some((ids, from_glob)) = self.bound(module, ns, name)? else {
1029                    continue;
1030                };
1031                let mut exported = false;
1032                for &id in &ids {
1033                    if index.items[id.0].test == TestRole::None
1034                        && self.public_route(module, at, name, id)?
1035                    {
1036                        exported = true;
1037                        found
1038                            .entry(id)
1039                            .or_insert((at, if from_glob { By::Glob } else { By::Explicit }));
1040                    }
1041                }
1042                if exported
1043                    && let Some(error) = index.binding_failure(
1044                        module,
1045                        ns,
1046                        name,
1047                        &ids,
1048                        &format!("{path}::{name}"),
1049                        Steps::Query(self.meter),
1050                    )
1051                {
1052                    return Err(ExportError::Resolve(error));
1053                }
1054            }
1055            for id in index.sorted(found.keys().copied()) {
1056                let (at, by) = found[&id];
1057                if let Some(child) = self.binding(visit, name, id, at, by)? {
1058                    next.push(child);
1059                }
1060            }
1061        }
1062        Ok(next)
1063    }
1064
1065    /// The public re-exports of the module of `visit` of what the index cannot
1066    /// see, its own and those its public glob routes carry from the modules
1067    /// they reach, each under the path of `visit`.
1068    ///
1069    /// The modules the routes reach are walked once, into a graph. A carried
1070    /// import of a name is carried when some route from the reader to its
1071    /// module passes no other module that binds the name itself (see
1072    /// [`Surface::carried`]).
1073    fn unseen(&mut self, visit: &Visit) -> Result<(), ExportError> {
1074        let index = self.index;
1075        self.unseen_globs(visit, visit.module, false)?;
1076        self.unbound_imports(visit, visit.module, false, None)?;
1077        let reach = self.glob_reach(visit.module)?;
1078        if reach.is_empty() {
1079            return Ok(());
1080        }
1081        let mut carry = Carry {
1082            graph: self.reach_graph(visit.module, &reach)?,
1083            binders: BTreeMap::new(),
1084            carriers: BTreeMap::new(),
1085            answers: BTreeMap::new(),
1086        };
1087        for (node, &module) in carry.graph.modules.iter().enumerate() {
1088            let defined = index.scopes[module]
1089                .iter()
1090                .filter(|(_, entry)| entry.defs.iter().any(|bound| !bound.is_empty()))
1091                .map(|(name, _)| name.as_str());
1092            let mut imported: Vec<&'a str> = Vec::new();
1093            for position in index.named_of(module) {
1094                let decl = &index.uses[*position];
1095                if let UseKind::Named { name, .. } = &decl.kind {
1096                    imported.push(name.as_str());
1097                    if node > 0
1098                        && exporting(decl)
1099                        && !index.use_bound[*position].iter().any(|bound| *bound)
1100                    {
1101                        let carriers = carry.carriers.entry(name.as_str()).or_default();
1102                        if carriers.last() != Some(&node) {
1103                            carriers.push(node);
1104                        }
1105                    }
1106                }
1107            }
1108            for name in defined.chain(imported) {
1109                let binders = carry.binders.entry(name).or_default();
1110                if binders.last() != Some(&node) {
1111                    binders.push(node);
1112                }
1113            }
1114        }
1115        let held: usize = carry
1116            .binders
1117            .values()
1118            .chain(carry.carriers.values())
1119            .map(Vec::len)
1120            .sum();
1121        self.charge(
1122            2 * btree_map::<&str, Vec<usize>>()
1123                + (carry.binders.len() + carry.carriers.len())
1124                    * (btree_entry::<&str, Vec<usize>>() + vec_first::<usize>())
1125                + held * vec_slot::<usize>(),
1126            self.module_item(visit.module),
1127        )?;
1128        for (module, hidden) in reach {
1129            self.unseen_globs(visit, module, hidden)?;
1130            self.unbound_imports(visit, module, hidden, Some(&mut carry))?;
1131        }
1132        Ok(())
1133    }
1134
1135    /// The graph of `reach`, the modules the public routes of `reader` reach,
1136    /// charged as it is kept.
1137    fn reach_graph(
1138        &mut self,
1139        reader: usize,
1140        reach: &[(usize, bool)],
1141    ) -> Result<Reach, ExportError> {
1142        let modules: Vec<usize> = std::iter::once(reader)
1143            .chain(reach.iter().map(|(module, _)| *module))
1144            .collect();
1145        let node_of: BTreeMap<usize, usize> = modules
1146            .iter()
1147            .enumerate()
1148            .map(|(node, module)| (*module, node))
1149            .collect();
1150        let shown: Vec<bool> = std::iter::once(true)
1151            .chain(reach.iter().map(|(_, hidden)| !hidden))
1152            .collect();
1153        let mut succ: [Vec<Vec<usize>>; 2] = [
1154            Vec::with_capacity(modules.len()),
1155            Vec::with_capacity(modules.len()),
1156        ];
1157        let mut edges = 0;
1158        for (node, &module) in modules.iter().enumerate() {
1159            let routes = self.routes(module)?;
1160            for (mode, list) in succ.iter_mut().enumerate() {
1161                // As for an item, only the reader's own hidden globs are left
1162                // out of the shown routes.
1163                let mut to: Vec<usize> = routes
1164                    .list
1165                    .iter()
1166                    .filter(|route| mode == EVERY || node != 0 || !route.hidden)
1167                    .filter_map(|route| node_of.get(&route.target).copied())
1168                    .collect();
1169                to.sort_unstable();
1170                to.dedup();
1171                edges += to.len();
1172                list.push(to);
1173            }
1174        }
1175        self.charge(
1176            modules.len()
1177                * (size_of::<usize>()
1178                    + size_of::<bool>()
1179                    + btree_entry::<usize, usize>()
1180                    + 2 * size_of::<Vec<usize>>())
1181                + btree_map::<usize, usize>()
1182                + edges * size_of::<usize>(),
1183            self.module_item(reader),
1184        )?;
1185        Ok(Reach {
1186            modules,
1187            node_of,
1188            succ,
1189            shown,
1190            spans: [None, None],
1191        })
1192    }
1193
1194    /// Whether the public routes of the module of `visit` carry the name
1195    /// `name` of the import at `position` from `module`, which the walk
1196    /// reached: `Some(false)` when a route that `#[doc(hidden)]` does not
1197    /// hide carries it, `Some(true)` when only hidden routes do, and `None`
1198    /// when none does. A route carries it when it passes no module that binds
1199    /// the name itself, the reader included, but the module.
1200    fn carried(
1201        &mut self,
1202        visit: &Visit,
1203        position: usize,
1204        module: usize,
1205        name: &'a str,
1206        carry: &mut Carry<'a>,
1207    ) -> Result<Option<bool>, ExportError> {
1208        if self.carried_by(visit, position, module, name, carry, SHOWN)? {
1209            return Ok(Some(false));
1210        }
1211        Ok(self
1212            .carried_by(visit, position, module, name, carry, EVERY)?
1213            .then_some(true))
1214    }
1215
1216    /// True when a route of `mode` carries the name `name` from `module` to
1217    /// the reader of `visit` (see [`Surface::carried`]).
1218    ///
1219    /// Only a binder that the routes of `mode` reach and that has routes of
1220    /// its own there can be passed on the way. With none, the name is
1221    /// carried. One that dominates the module (is on every such route to it)
1222    /// keeps the name out, and so does the reader; with one binder that does
1223    /// not, the name is carried. With several, none of which dominates, a
1224    /// search from the reader past the binders decides the name for every
1225    /// module that carries it at once, and keeps only those answers. The tree
1226    /// of dominators of each mode is made once for the reader, the first
1227    /// time a name needs it. The work of the tree and of each search, a unit
1228    /// for each module and route it reads, is charged to the item-bytes
1229    /// budget with what they hold; a listing that passes the budget so is
1230    /// [`ExportError::CarryBudget`], naming the re-export and its
1231    /// declaration.
1232    fn carried_by(
1233        &mut self,
1234        visit: &Visit,
1235        position: usize,
1236        module: usize,
1237        name: &'a str,
1238        carry: &mut Carry<'a>,
1239        mode: usize,
1240    ) -> Result<bool, ExportError> {
1241        let decl = &self.index.uses[position];
1242        let charge = |surface: &Self, bytes: usize| {
1243            surface
1244                .meter
1245                .items(bytes, &decl.file, Some(decl.line))
1246                .map_err(|error| ExportError::CarryBudget {
1247                    path: format!("{}::{name}", visit.path),
1248                    error,
1249                })
1250        };
1251        let target = carry.graph.node_of[&module];
1252        if mode == SHOWN && !carry.graph.shown[target] {
1253            return Ok(false);
1254        }
1255        let Some(binders) = carry.binders.get(name) else {
1256            return Ok(true);
1257        };
1258        if binders.first() == Some(&0) {
1259            return Ok(false);
1260        }
1261        let succ = &carry.graph.succ[mode];
1262        let passed: Vec<usize> = binders
1263            .iter()
1264            .copied()
1265            .filter(|node| {
1266                *node != target
1267                    && !succ[*node].is_empty()
1268                    && (mode == EVERY || carry.graph.shown[*node])
1269            })
1270            .collect();
1271        if passed.is_empty() {
1272            return Ok(true);
1273        }
1274        self.ensure_spans(&mut carry.graph, mode, decl, &visit.path, name)?;
1275        if passed
1276            .iter()
1277            .any(|binder| carry.graph.dominates(mode, *binder, target))
1278        {
1279            return Ok(false);
1280        }
1281        if passed.len() == 1 {
1282            return Ok(true);
1283        }
1284        if let Some(known) = carry.answers.get(&(name, target, mode)) {
1285            return Ok(*known);
1286        }
1287        // One search for the name: from the reader, never past a module that
1288        // binds it, noting each module that carries it.
1289        let succ = &carry.graph.succ[mode];
1290        let count = carry.graph.modules.len();
1291        let mut entered = vec![false; count];
1292        entered[0] = true;
1293        let mut work = WorkList::<_, 8>::new();
1294        let push = |work: &mut WorkList<_, 8>, value| {
1295            push_item_work(work, value, self.meter, &decl.file, Some(decl.line)).map_err(|error| {
1296                ExportError::storage(error, Some(format!("{}::{name}", visit.path)))
1297            })
1298        };
1299        push(&mut work, 0)?;
1300        let mut reached = BTreeSet::new();
1301        let mut steps = 0;
1302        while let Some(node) = work.pop() {
1303            steps += 1 + succ[node].len();
1304            if node != 0 {
1305                reached.insert(node);
1306                if binders.binary_search(&node).is_ok() {
1307                    continue;
1308                }
1309            }
1310            for &to in &succ[node] {
1311                if !entered[to] {
1312                    entered[to] = true;
1313                    push(&mut work, to)?;
1314                }
1315            }
1316        }
1317        let carriers = carry.carriers.get(name).map_or(&[][..], Vec::as_slice);
1318        tally::add(Work::WalkSteps, steps);
1319        charge(
1320            self,
1321            steps * WALK_STEP_BYTES
1322                + count * size_of::<bool>()
1323                + carriers.len() * btree_entry::<(&str, usize, usize), bool>(),
1324        )?;
1325        for &carrier in carriers {
1326            carry
1327                .answers
1328                .insert((name, carrier, mode), reached.contains(&carrier));
1329        }
1330        Ok(reached.contains(&target))
1331    }
1332
1333    /// Construct the mode's dominator intervals once under the surface account.
1334    fn ensure_spans(
1335        &self,
1336        graph: &mut Reach,
1337        mode: usize,
1338        decl: &UseDecl,
1339        path: &str,
1340        name: &str,
1341    ) -> Result<(), ExportError> {
1342        if graph.spans[mode].is_some() {
1343            return Ok(());
1344        }
1345        let succ = &graph.succ[mode];
1346        let (spans, work) = dominator_spans(succ, self.meter, &decl.file, decl.line)
1347            .map_err(|error| ExportError::storage(error, Some(format!("{path}::{name}"))))?;
1348        let edges: usize = succ.iter().map(Vec::len).sum();
1349        tally::add(Work::WalkSteps, work);
1350        self.meter
1351            .items(
1352                work * WALK_STEP_BYTES
1353                    + spans.len() * (size_of::<Option<(usize, usize)>>() + 6 * size_of::<usize>())
1354                    + edges * 2 * size_of::<usize>(),
1355                &decl.file,
1356                Some(decl.line),
1357            )
1358            .map_err(|error| ExportError::CarryBudget {
1359                path: format!("{path}::{name}"),
1360                error,
1361            })?;
1362        graph.spans[mode] = Some(spans);
1363        Ok(())
1364    }
1365
1366    /// The items `module` binds to `name` in `ns`, and whether its globs
1367    /// bring them in, as [`Index::lookup_in`] answers: the bindings that
1368    /// shadow globs when there are any, else, when no explicit import keeps
1369    /// the name from the globs, what every glob of the module brings in,
1370    /// read through the views that hold the name.
1371    fn bound(
1372        &self,
1373        module: usize,
1374        ns: Namespace,
1375        name: &str,
1376    ) -> Result<Option<(Vec<ItemId>, bool)>, ExportError> {
1377        let steps = Steps::Query(self.meter);
1378        let bound = self.index.lookup_in(module, ns, name, None, steps);
1379        Index::query_refusal(steps)
1380            .map_err(|refused| ExportError::Budget(self.index.refused_load(refused)))?;
1381        let Some((bound, from_glob)) = bound else {
1382            return Ok(None);
1383        };
1384        self.charge(
1385            vec_first::<ItemId>() + bound.len() * vec_slot::<ItemId>(),
1386            self.module_item(module),
1387        )?;
1388        Ok(Some((bound.keys().copied().collect(), from_glob)))
1389    }
1390
1391    /// The public globs of `module`, read under the path of `visit` (its own
1392    /// module, or one its public glob routes reach, which `hidden` routes
1393    /// alone reach), whose path names nothing the index can look into: each
1394    /// is a re-export. One whose path names nothing in the workspace past its
1395    /// first segment fails the listing, as it fails every lookup that reads
1396    /// it, and so does one whose path rustc refuses.
1397    fn unseen_globs(
1398        &mut self,
1399        visit: &Visit,
1400        module: usize,
1401        hidden: bool,
1402    ) -> Result<(), ExportError> {
1403        let index = self.index;
1404        for &glob in index.globs_of(module) {
1405            let decl = &index.uses[glob];
1406            if !exporting(decl) {
1407                continue;
1408            }
1409            let path = format!("{}::*", visit.path);
1410            match index.glob_targets(glob, Steps::Query(self.meter)) {
1411                Ok(_) => {}
1412                Err(Fail::Missing(_)) => {
1413                    if index
1414                        .glob_broken(glob, self.meter)
1415                        .map_err(ExportError::Budget)?
1416                    {
1417                        return Err(ExportError::Resolve(index.glob_error(glob, &path)));
1418                    }
1419                    self.keep_reexport(
1420                        path,
1421                        written(decl),
1422                        None,
1423                        decl.file.clone(),
1424                        decl.line,
1425                        visit.hidden || hidden || decl.doc_hidden,
1426                    )?;
1427                }
1428                Err(Fail::SeveralCrates { roots: ids, .. } | Fail::Ambiguous(ids)) => {
1429                    return Err(ExportError::Resolve(ResolveError::Ambiguous(ids)));
1430                }
1431                // The load refuses a `super` above the crate root.
1432                Err(Fail::SuperAboveRoot) => {
1433                    return Err(ExportError::Resolve(ResolveError::Invalid(path)));
1434                }
1435                Err(Fail::Budget(refused)) => {
1436                    return Err(ExportError::Budget(index.refused_load(refused)));
1437                }
1438                Err(Fail::Storage(error)) => return Err(ExportError::storage(error, None)),
1439            }
1440        }
1441        Ok(())
1442    }
1443
1444    /// The public named imports of `module`, read under the path of `visit`
1445    /// as [`Surface::unseen_globs`] reads its globs, that bound nothing: a
1446    /// re-export of a crate outside the workspace, of one of its items, of an
1447    /// enum variant or of a path the index cannot follow, unless the module's
1448    /// globs answer for the name, or, for a module a glob route reaches, a
1449    /// module on every such route binds the name itself. A name that
1450    /// resolves to an error fails the listing.
1451    fn unbound_imports(
1452        &mut self,
1453        visit: &Visit,
1454        module: usize,
1455        hidden: bool,
1456        mut carry: Option<&mut Carry<'a>>,
1457    ) -> Result<(), ExportError> {
1458        let index = self.index;
1459        let at_path = &index.modules[module].path;
1460        let package = index.targets[index.modules[module].target.index()].package_id;
1461        for &position in index.named_of(module) {
1462            let decl = &index.uses[position];
1463            if !exporting(decl) || index.use_bound[position].iter().any(|bound| *bound) {
1464                continue;
1465            }
1466            let UseKind::Named {
1467                name, namespaces, ..
1468            } = &decl.kind
1469            else {
1470                continue;
1471            };
1472            let hidden = match carry.as_deref_mut() {
1473                Some(carry) => match self.carried(visit, position, module, name.as_str(), carry)? {
1474                    Some(hidden) => hidden,
1475                    None => continue,
1476                },
1477                None => hidden,
1478            };
1479            match index.resolve(
1480                &format!("{at_path}::{name}"),
1481                match namespaces {
1482                    crate::index::NamedNamespaces::All => None,
1483                    crate::index::NamedNamespaces::TypeOnly => Some(Namespace::Type),
1484                },
1485                Some(package),
1486                self.meter,
1487            ) {
1488                Err(ResolveError::NotFound(_)) => self.keep_reexport(
1489                    format!("{}::{name}", visit.path),
1490                    written(decl),
1491                    None,
1492                    decl.file.clone(),
1493                    decl.line,
1494                    visit.hidden || hidden || decl.doc_hidden,
1495                )?,
1496                Err(ResolveError::Budget {
1497                    budget,
1498                    limit,
1499                    file,
1500                    line,
1501                }) => return Err(ExportError::Budget(over_budget(budget, limit, &file, line))),
1502                Err(other) => return Err(ExportError::Resolve(other)),
1503                Ok(_) => {}
1504            }
1505        }
1506        Ok(())
1507    }
1508
1509    /// List the public binding of `id` under `name` in the module of `visit`:
1510    /// a re-export when it names another crate, else the item and, for a type
1511    /// or a trait, its public members. Returns the module of the target that
1512    /// a `mod` item stands for, to be read under the binding's path.
1513    fn binding(
1514        &mut self,
1515        visit: &Visit,
1516        name: &str,
1517        id: ItemId,
1518        at: usize,
1519        by: By,
1520    ) -> Result<Option<Visit>, ExportError> {
1521        let index = self.index;
1522        let module = visit.module;
1523        let path = format!("{}::{name}", visit.path);
1524        let item = &index.items[id.0];
1525        let child = (item.kind == SymbolKind::Mod)
1526            .then(|| index.module_of.get(&id).copied())
1527            .flatten();
1528        let doc_hidden = visit.hidden
1529            || item.doc_hidden
1530            || child.is_some_and(|child| {
1531                self.hidden_files
1532                    .contains(index.modules[child].path.as_str())
1533            })
1534            || self.reexport_hidden(module, at, name, id, by)?;
1535        if let Some(named) = self.other_crate(id) {
1536            let (written, file, line) = self.binding_site(module, at, name, id, by)?;
1537            self.keep_reexport(path, written, named.item(), file, line, doc_hidden)?;
1538            return Ok(None);
1539        }
1540        self.keep(path.clone(), id, doc_hidden)?;
1541        if doc_hidden && !self.options.include_hidden {
1542            return Ok(None);
1543        }
1544        match item.kind {
1545            SymbolKind::Struct | SymbolKind::Enum | SymbolKind::Union | SymbolKind::Trait => {
1546                self.members(&path, id, doc_hidden)?;
1547                Ok(None)
1548            }
1549            _ => Ok(child.map(|child| Visit {
1550                module: child,
1551                path,
1552                hidden: doc_hidden,
1553            })),
1554        }
1555    }
1556
1557    /// List the members of the type or trait `owner`, exported under
1558    /// `owner_path`: every member of a trait, and the `pub` members of the
1559    /// inherent impls of a type. The members of trait impls carry no
1560    /// visibility of their own and are not listed: their interface is the
1561    /// trait's.
1562    fn members(
1563        &mut self,
1564        owner_path: &str,
1565        owner: ItemId,
1566        hidden: bool,
1567    ) -> Result<(), ExportError> {
1568        let index = self.index;
1569        let Some(table) = index.assoc.get(&owner) else {
1570            return Ok(());
1571        };
1572        let of_trait = index.items[owner.0].kind == SymbolKind::Trait;
1573        for (name, ids) in table {
1574            for id in index.sorted(ids.iter().copied()) {
1575                let member = &index.items[id.0];
1576                if member.test != TestRole::None
1577                    || member.target != self.target
1578                    || member.trait_path.is_some()
1579                    || (!of_trait && member.visibility != Vis::Public)
1580                {
1581                    continue;
1582                }
1583                self.keep(
1584                    format!("{owner_path}::{name}"),
1585                    id,
1586                    hidden || member.doc_hidden,
1587                )?;
1588            }
1589        }
1590        Ok(())
1591    }
1592}
1593
1594#[cfg(test)]
1595mod tests;