1use 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#[derive(Debug, Clone, Default, PartialEq, Eq)]
63#[non_exhaustive]
64pub struct ExportOptions {
65 pub include_hidden: bool,
69}
70
71#[derive(Debug, Clone, PartialEq, Eq)]
77#[non_exhaustive]
78pub struct ExportedItem {
79 pub path: String,
83 pub item: ItemId,
85 pub kind: SymbolKind,
87 pub file: RelPath,
89 pub span: SpanFact,
91 pub doc_hidden: bool,
96}
97
98#[derive(Debug, Clone, PartialEq, Eq)]
108#[non_exhaustive]
109pub struct Reexport {
110 pub path: String,
113 pub written: String,
116 pub item: Option<ItemId>,
120 pub file: RelPath,
122 pub line: usize,
124 pub doc_hidden: bool,
127}
128
129#[derive(Debug, Clone, Default, PartialEq, Eq)]
134#[non_exhaustive]
135pub struct Exports {
136 pub items: Vec<ExportedItem>,
140 pub reexports: Vec<Reexport>,
143}
144
145#[derive(Debug)]
147#[non_exhaustive]
148pub enum ExportError {
149 NotLibraryOrBinary(TargetId),
152 Budget(LoadError),
156 Storage(LoadError),
159 CarryBudget {
165 path: String,
167 error: LoadError,
169 },
170 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 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#[derive(Debug, Clone, Copy)]
227struct Route {
228 view: usize,
229 target: usize,
230 glob: usize,
231 hidden: bool,
232}
233
234struct Routes<'a> {
237 list: Vec<Route>,
238 by_name: BTreeMap<&'a str, Vec<usize>>,
239}
240
241impl Routes<'_> {
242 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
252struct 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
264struct 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
281type Spans = Vec<Option<(usize, usize)>>;
284
285const SHOWN: usize = 0;
287const EVERY: usize = 1;
289
290impl Reach {
291 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
304fn 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 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
409const WALK_STEP_BYTES: usize = btree_entry::<usize, bool>();
413
414type Place = (ItemId, usize, usize, String);
417
418struct Visit {
420 module: usize,
421 path: String,
422 hidden: bool,
423}
424
425#[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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
446enum By {
447 Explicit,
448 Glob,
449}
450
451pub(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 hidden_files: &'a BTreeSet<&'a str>,
461 routes: BTreeMap<usize, Rc<Routes<'a>>>,
463 decided: BTreeMap<Place, bool>,
465 items: Vec<ExportedItem>,
466 reexports: Vec<Reexport>,
467}
468
469fn 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
486fn exporting(decl: &UseDecl) -> bool {
489 decl.vis == Vis::Public && !decl.test
490}
491
492impl<'a> Surface<'a> {
493 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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;