1use std::collections::btree_map::Entry;
37use std::collections::{BTreeMap, BTreeSet, VecDeque};
38use std::error::Error;
39use std::fmt;
40use std::mem::size_of;
41use std::panic;
42use std::str::FromStr;
43use std::thread;
44
45use proc_macro2::{Delimiter, Spacing, TokenStream, TokenTree};
46
47use crate::cost::{btree_entry, btree_map, vec_first, vec_slot};
48use crate::error::{LoadError, LoadErrorKind};
49use crate::facts::TestRole;
50use crate::index::Index;
51use crate::item::{ImplId, ItemId, SharedStr, SymbolKind};
52use crate::meter::{Meter, Steps};
53use crate::options::LoadOptions;
54use crate::parse::PARSE_STACK_BYTES;
55use crate::path::RelPath;
56use crate::work::{self, Work};
57use crate::workspace::SourceFile;
58
59mod format;
60
61#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
63pub enum Node {
64 Item(ItemId),
66 Impl(ImplId),
68}
69
70impl From<ItemId> for Node {
71 fn from(id: ItemId) -> Self {
72 Self::Item(id)
73 }
74}
75
76impl From<ImplId> for Node {
77 fn from(id: ImplId) -> Self {
78 Self::Impl(id)
79 }
80}
81
82#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
84#[non_exhaustive]
85pub enum Edge {
86 Root,
88 Contains,
91 ImplOf,
94 References,
96}
97
98#[derive(Debug, Clone, Copy, PartialEq, Eq)]
101#[non_exhaustive]
102pub struct Reached {
103 pub node: Node,
105 pub edge: Edge,
107 pub from: Option<Node>,
109}
110
111#[derive(Debug, Clone, PartialEq, Eq)]
115#[non_exhaustive]
116pub struct Reachability {
117 pub reached: Vec<Reached>,
119 at: BTreeMap<Node, usize>,
121}
122
123impl Reachability {
124 #[must_use]
126 pub fn get(&self, node: Node) -> Option<&Reached> {
127 self.at.get(&node).map(|at| &self.reached[*at])
128 }
129
130 #[must_use]
132 pub fn contains(&self, node: Node) -> bool {
133 self.at.contains_key(&node)
134 }
135
136 pub fn items(&self) -> impl Iterator<Item = ItemId> + '_ {
138 self.reached
139 .iter()
140 .filter_map(|reached| match reached.node {
141 Node::Item(id) => Some(id),
142 Node::Impl(_) => None,
143 })
144 }
145
146 pub fn impls(&self) -> impl Iterator<Item = ImplId> + '_ {
148 self.reached
149 .iter()
150 .filter_map(|reached| match reached.node {
151 Node::Impl(id) => Some(id),
152 Node::Item(_) => None,
153 })
154 }
155}
156
157#[derive(Debug)]
159#[non_exhaustive]
160pub enum ReachError {
161 UnknownItem(ItemId),
166 UnknownImpl(ImplId),
169 Source(LoadError),
176 Budget(LoadError),
181}
182
183impl From<LoadError> for ReachError {
184 fn from(error: LoadError) -> Self {
185 if matches!(error.kind, LoadErrorKind::Budget { .. }) {
186 Self::Budget(error)
187 } else {
188 Self::Source(error)
189 }
190 }
191}
192
193impl fmt::Display for ReachError {
194 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
195 match self {
196 Self::UnknownItem(id) => {
197 write!(f, "item {} is past the items of the workspace", id.index())
198 }
199 Self::UnknownImpl(id) => {
200 write!(
201 f,
202 "impl block {} is past the impl blocks of the workspace",
203 id.index()
204 )
205 }
206 Self::Source(error) => write!(f, "{error}"),
207 Self::Budget(error) => write!(f, "the walk is over budget: {error}"),
208 }
209 }
210}
211
212impl Error for ReachError {
213 fn source(&self) -> Option<&(dyn Error + 'static)> {
214 match self {
215 Self::Source(error) | Self::Budget(error) => Some(error),
216 Self::UnknownItem(_) | Self::UnknownImpl(_) => None,
217 }
218 }
219}
220
221#[derive(Debug, Clone, Copy, PartialEq, Eq)]
223enum RunKind {
224 Path,
226 SelfPath,
229 Method,
232}
233
234#[derive(Debug, Clone, Copy, PartialEq, Eq)]
239struct Run {
240 start: usize,
241 first: usize,
242 len: usize,
243 leading_colon: bool,
244 kind: RunKind,
245}
246
247#[derive(Debug, Default)]
250struct Lexed {
251 runs: Vec<Run>,
252 segs: Vec<(usize, usize)>,
253 tokens: usize,
254 formats: Option<Box<format::Formats>>,
255 format_tokens: usize,
256 format_bytes: usize,
257}
258
259impl Lexed {
260 fn start(
262 &mut self,
263 start: usize,
264 leading_colon: bool,
265 kind: RunKind,
266 seg: (usize, usize),
267 ) -> usize {
268 self.runs.push(Run {
269 start,
270 first: self.segs.len(),
271 len: 1,
272 leading_colon,
273 kind,
274 });
275 self.segs.push(seg);
276 self.runs.len() - 1
277 }
278
279 fn extend(&mut self, at: usize, seg: (usize, usize)) {
281 self.runs[at].len += 1;
282 self.segs.push(seg);
283 }
284
285 fn drop_last(&mut self) {
287 if let Some(run) = self.runs.pop() {
288 self.segs.truncate(run.first);
289 }
290 }
291}
292
293struct LexFailure {
295 message: String,
296 line: usize,
297 column: usize,
298}
299
300const KEYWORDS: [&str; 43] = [
304 "abstract", "as", "become", "box", "break", "const", "continue", "do", "else", "enum",
305 "extern", "false", "final", "fn", "for", "if", "impl", "in", "let", "loop", "macro", "match",
306 "mod", "move", "mut", "override", "priv", "pub", "ref", "return", "static", "struct", "trait",
307 "true", "type", "typeof", "unsafe", "unsized", "use", "virtual", "where", "while", "yield",
308];
309
310const KEYWORDS_2018: [&str; 4] = ["async", "await", "dyn", "try"];
312
313const KEYWORD_2024: &str = "gen";
315
316fn blocked(word: &str, edition: u16) -> bool {
319 word == "Self"
320 || KEYWORDS.contains(&word)
321 || (edition >= 2018 && KEYWORDS_2018.contains(&word))
322 || (edition >= 2024 && word == KEYWORD_2024)
323}
324
325const DECLARES: [&str; 8] = [
330 "fn", "struct", "enum", "union", "trait", "type", "mod", "static",
331];
332
333#[derive(Debug, Clone, Copy, PartialEq, Eq)]
335enum Word {
336 Plain,
338 Declares,
340 MacroRules,
342 SelfValue,
344}
345
346#[derive(Debug, Clone, Copy, PartialEq, Eq)]
348enum Tok {
349 Ident { in_run: bool, word: Word },
352 Punct { ch: char, joint: bool },
354 Other,
356}
357
358#[derive(Debug, Default)]
362struct Level {
363 last: [Option<Tok>; 3],
364 in_where: bool,
365}
366
367impl Level {
368 fn push(&mut self, tok: Tok) {
369 self.last = [self.last[1], self.last[2], Some(tok)];
370 }
371
372 fn colons(&self) -> bool {
374 matches!(
375 (self.last[1], self.last[2]),
376 (
377 Some(Tok::Punct {
378 ch: ':',
379 joint: true
380 }),
381 Some(Tok::Punct { ch: ':', .. })
382 )
383 )
384 }
385
386 fn single_dot(&self) -> bool {
388 matches!(
389 self.last[2],
390 Some(Tok::Punct {
391 ch: '.',
392 joint: false
393 })
394 ) && !matches!(
395 self.last[1],
396 Some(Tok::Punct {
397 ch: '.',
398 joint: true
399 })
400 )
401 }
402
403 fn declaring(&self) -> bool {
406 matches!(
407 (self.last[1], self.last[2]),
408 (
409 _,
410 Some(Tok::Ident {
411 word: Word::Declares,
412 ..
413 })
414 ) | (
415 Some(Tok::Ident {
416 word: Word::MacroRules,
417 ..
418 }),
419 Some(Tok::Punct { ch: '!', .. })
420 )
421 )
422 }
423
424 fn after_self_dot(&self) -> bool {
427 self.single_dot()
428 && matches!(
429 self.last[1],
430 Some(Tok::Ident {
431 word: Word::SelfValue,
432 ..
433 })
434 )
435 }
436
437 fn word(&self, word: &str) -> Word {
440 if matches!(self.last[2], Some(Tok::Punct { ch: '\'', .. })) {
441 Word::Plain
442 } else if DECLARES.contains(&word) {
443 Word::Declares
444 } else if word == "macro_rules" {
445 Word::MacroRules
446 } else if word == "self" {
447 Word::SelfValue
448 } else {
449 Word::Plain
450 }
451 }
452}
453
454enum Place {
456 Extend,
458 Start(bool, RunKind),
460 Skip,
462}
463
464#[derive(Debug, Clone, Copy)]
467struct Open {
468 at: usize,
469 supers: bool,
470}
471
472fn place(level: &Level, word: &str, raw: bool, supers: bool, edition: u16) -> Place {
477 let blocked = |word: &str| !raw && blocked(word, edition);
478 let path_word = !raw && matches!(word, "crate" | "self" | "super");
479 if level.colons() {
480 return match level.last[0] {
481 Some(Tok::Ident { in_run: true, .. }) => {
482 if blocked(word) || (path_word && !(word == "super" && supers)) {
483 Place::Skip
484 } else {
485 Place::Extend
486 }
487 }
488 Some(Tok::Ident { in_run: false, .. } | Tok::Punct { ch: '>', .. }) => Place::Skip,
489 _ if blocked(word) || path_word => Place::Skip,
490 _ => Place::Start(true, RunKind::Path),
491 };
492 }
493 let self_type = !raw && word == "Self";
494 if (blocked(word) && !self_type) || level.single_dot() || level.declaring() {
495 return Place::Skip;
496 }
497 match level.last[2] {
498 Some(Tok::Punct { ch: '\'', .. }) => Place::Skip,
499 Some(Tok::Punct { ch: '$', .. }) if word != "crate" => Place::Skip,
500 _ if self_type => Place::Start(false, RunKind::SelfPath),
501 _ => Place::Start(false, RunKind::Path),
502 }
503}
504
505fn scan(stream: TokenStream, text: &str, base: usize, edition: u16) -> Lexed {
521 let mut lexed = Lexed::default();
522 let mut stack: Vec<(proc_macro2::token_stream::IntoIter, Level)> =
523 vec![(stream.into_iter(), Level::default())];
524 let mut open: Option<Open> = None;
525 let mut colon: Option<(usize, bool)> = None;
528 let mut method: Option<(usize, (usize, usize))> = None;
531 while let Some((tokens, level)) = stack.last_mut() {
532 let tree = tokens.next();
533 if let Some((start, seg)) = method.take() {
534 let called = match &tree {
535 Some(TokenTree::Group(group)) => group.delimiter() == Delimiter::Parenthesis,
536 Some(TokenTree::Punct(punct)) => {
537 punct.as_char() == ':' && punct.spacing() == Spacing::Joint
538 }
539 _ => false,
540 };
541 if called {
542 lexed.start(start, false, RunKind::Method, seg);
543 }
544 }
545 let next_colon = matches!(&tree, Some(TokenTree::Punct(punct)) if punct.as_char() == ':');
546 if let Some((at, joint)) = colon.take()
547 && !(joint && next_colon)
548 && lexed.runs.len() == at + 1
549 {
550 lexed.drop_last();
551 open = None;
552 }
553 let Some(tree) = tree else {
554 stack.pop();
555 open = None;
556 if let Some((_, outer)) = stack.last_mut() {
557 outer.push(Tok::Other);
558 }
559 continue;
560 };
561 lexed.tokens += 1;
562 match tree {
563 TokenTree::Group(group) => {
564 open = None;
565 if group.delimiter() == Delimiter::Brace {
566 level.in_where = false;
567 }
568 stack.push((group.stream().into_iter(), Level::default()));
569 }
570 TokenTree::Ident(ident) => {
571 let range = ident.span().byte_range();
572 let span = (base + range.start, base + range.end);
573 if ident == text[span.0..span.1] {
576 open = scan_ident(&mut lexed, level, open, &ident, span, edition, &mut method);
577 } else {
578 open = None;
579 level.push(Tok::Ident {
580 in_run: false,
581 word: Word::Plain,
582 });
583 }
584 }
585 TokenTree::Punct(punct) => {
586 let ch = punct.as_char();
587 let joint = punct.spacing() == Spacing::Joint;
588 if ch == ':' {
589 let first = !matches!(
593 level.last[2],
594 Some(Tok::Punct {
595 ch: ':',
596 joint: true
597 })
598 );
599 if first
600 && !level.in_where
601 && let (Some(run), Some(Tok::Ident { in_run: true, .. })) =
602 (open, level.last[2])
603 && lexed.runs[run.at].len == 1
604 {
605 colon = Some((run.at, joint));
606 }
607 } else {
608 open = None;
611 if ch == ';' {
612 level.in_where = false;
613 }
614 }
615 level.push(Tok::Punct { ch, joint });
616 }
617 TokenTree::Literal(_) => {
618 open = None;
619 level.push(Tok::Other);
620 }
621 }
622 }
623 lexed
624}
625
626fn scan_ident(
631 lexed: &mut Lexed,
632 level: &mut Level,
633 open: Option<Open>,
634 ident: &proc_macro2::Ident,
635 span: (usize, usize),
636 edition: u16,
637 method: &mut Option<(usize, (usize, usize))>,
638) -> Option<Open> {
639 let text = ident.to_string();
640 let (word, raw) = match text.strip_prefix("r#") {
642 Some(word) => (word, true),
643 None => (text.as_str(), false),
644 };
645 let kind = if raw { Word::Plain } else { level.word(word) };
646 let (start, end) = span;
647 let seg = (end - word.len(), end);
648 if !raw && word == "where" {
649 level.in_where = true;
650 }
651 if level.after_self_dot() {
652 *method = Some((start, seg));
653 }
654 let path_word = !raw && matches!(word, "self" | "super");
655 let supers = open.is_some_and(|run| run.supers);
656 let (in_run, open) = match place(level, word, raw, supers, edition) {
657 Place::Extend => {
658 let open = open.map(|run| {
659 lexed.extend(run.at, seg);
660 Open {
661 at: run.at,
662 supers: run.supers && path_word,
663 }
664 });
665 (true, open)
666 }
667 Place::Start(leading_colon, kind) => {
668 let at = lexed.start(start, leading_colon, kind, seg);
669 (
670 true,
671 Some(Open {
672 at,
673 supers: path_word,
674 }),
675 )
676 }
677 Place::Skip => (false, None),
678 };
679 level.push(Tok::Ident { in_run, word: kind });
680 open
681}
682
683fn lex_text(text: &str, edition: u16) -> Result<Lexed, LexFailure> {
687 let mut base = 0;
688 let mut body = text;
689 if let Some(rest) = body.strip_prefix('\u{feff}') {
690 base += '\u{feff}'.len_utf8();
691 body = rest;
692 }
693 if let Some(after) = body.strip_prefix("#!")
694 && !after.trim_start().starts_with('[')
695 {
696 let cut = body.find('\n').unwrap_or(body.len());
697 base += cut;
698 body = &body[cut..];
699 }
700 let stream = TokenStream::from_str(body).map_err(|error| {
701 let start = error.span().start();
702 LexFailure {
703 message: error.to_string(),
704 line: start.line + text[..base].matches('\n').count(),
705 column: start.column + 1,
706 }
707 })?;
708 let mut lexed = scan(stream.clone(), text, base, edition);
709 (lexed.formats, lexed.format_tokens, lexed.format_bytes) = format::scan(stream, text, base);
710 lexed.runs.shrink_to_fit();
711 lexed.segs.shrink_to_fit();
712 Ok(lexed)
713}
714
715fn lex(file: &RelPath, text: &str, edition: u16) -> Result<Lexed, ReachError> {
718 thread::scope(|scope| {
719 let worker = thread::Builder::new()
720 .name(file.to_string())
721 .stack_size(PARSE_STACK_BYTES)
722 .spawn_scoped(scope, move || lex_text(text, edition))
723 .map_err(|source| {
724 ReachError::Source(LoadError::new(file, None, LoadErrorKind::Spawn(source)))
725 })?;
726 match worker.join() {
727 Ok(Ok(lexed)) => Ok(lexed),
728 Ok(Err(failure)) => Err(ReachError::Source(LoadError::new(
729 file,
730 Some(failure.line),
731 LoadErrorKind::Syntax {
732 message: failure.message,
733 column: failure.column,
734 },
735 ))),
736 Err(payload) => panic::resume_unwind(payload),
737 }
738 })
739}
740
741#[derive(Debug, Default)]
744struct FileRuns {
745 runs: Vec<Run>,
746 segs: Vec<(usize, usize)>,
747 by_unit: BTreeMap<(usize, usize), Vec<usize>>,
748 formats: Option<Box<format::Formats>>,
749 calls_by_unit: BTreeMap<(usize, usize), Vec<usize>>,
750}
751
752fn place_runs(runs: &[Run], units: Vec<(usize, usize)>) -> BTreeMap<(usize, usize), Vec<usize>> {
755 place_starts(
756 runs.iter().enumerate().map(|(at, run)| (at, run.start)),
757 units,
758 Work::ReachUnits,
759 )
760}
761
762fn place_starts(
763 starts: impl Iterator<Item = (usize, usize)>,
764 mut units: Vec<(usize, usize)>,
765 kind: Work,
766) -> BTreeMap<(usize, usize), Vec<usize>> {
767 units.sort_by(|a, b| a.0.cmp(&b.0).then(b.1.cmp(&a.1)));
769 units.dedup();
770 let mut by_unit: BTreeMap<(usize, usize), Vec<usize>> = BTreeMap::new();
771 let mut open: Vec<(usize, usize)> = Vec::new();
772 let mut next = 0;
773 for (position, start) in starts {
774 while let Some(&unit) = units.get(next).filter(|unit| unit.0 <= start) {
775 work::add(kind, 1);
776 while open.last().is_some_and(|top| top.1 <= unit.0) {
777 work::add(kind, 1);
778 open.pop();
779 }
780 open.push(unit);
781 next += 1;
782 }
783 while open.last().is_some_and(|top| top.1 <= start) {
784 work::add(kind, 1);
785 open.pop();
786 }
787 if let Some(unit) = open.last() {
788 work::add(kind, 1);
789 by_unit.entry(*unit).or_default().push(position);
790 }
791 }
792 for positions in by_unit.values_mut() {
793 positions.shrink_to_fit();
794 }
795 by_unit
796}
797
798#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
801enum Owner {
802 Block(ImplId),
804 Trait(ItemId),
806}
807
808#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
811enum Ctx {
812 Module(usize, bool),
813 Value(usize, bool),
814 Owner(Owner),
815}
816
817#[derive(Debug, Clone, Copy, Default)]
821pub(crate) struct Home {
822 module: Option<usize>,
823 owner: Option<Owner>,
824}
825
826impl Home {
827 pub(crate) const fn module(self) -> Option<usize> {
828 self.module
829 }
830}
831
832pub(crate) fn fill_homes(index: &Index, homes: &mut [Home], lexical: bool) {
834 for (module, entry) in index.modules.iter().enumerate() {
835 for id in &entry.defs {
836 work::add(Work::ReachSteps, 1);
837 homes[id.0].module = Some(module);
838 }
839 }
840 for (module, id) in &index.root_items {
841 work::add(Work::ReachSteps, 1);
842 homes[id.0].module = Some(*module);
843 }
844 if lexical {
845 for (id, module) in &index.macro_modules {
846 work::add(Work::ReachSteps, 1);
847 homes[id.0].module = Some(*module);
848 }
849 }
850 for block in &index.impl_blocks {
851 work::add(Work::ReachSteps, 1);
852 for member in &block.members {
853 work::add(Work::ReachSteps, 1);
854 homes[member.0] = Home {
855 module: Some(block.module_index),
856 owner: Some(Owner::Block(block.id)),
857 };
858 }
859 }
860 for (owner, members) in &index.assoc {
861 if index.items[owner.0].kind != SymbolKind::Trait {
862 continue;
863 }
864 homes[owner.0].owner = Some(Owner::Trait(*owner));
865 for id in members.values().flatten() {
866 work::add(Work::ReachSteps, 1);
867 homes[id.0] = Home {
868 module: homes[owner.0].module,
869 owner: Some(Owner::Trait(*owner)),
870 };
871 }
872 }
873}
874
875#[derive(Debug, Default)]
879struct BlockNames<'a> {
880 members: BTreeMap<&'a str, Vec<ItemId>>,
881 traits: Vec<ItemId>,
882}
883
884struct Unit<'u> {
888 file: &'u RelPath,
889 line: usize,
890 span: (usize, usize),
891 before: usize,
892 module: usize,
893 test: bool,
894 owner: Option<Owner>,
895}
896
897type Queued = (Node, Edge, Option<Node>);
900
901fn lists_bytes<K>(map: &BTreeMap<K, Vec<ImplId>>) -> usize {
903 btree_map::<K, Vec<ImplId>>()
904 + map
905 .values()
906 .map(|list| btree_entry::<K, Vec<ImplId>>() + list.capacity() * size_of::<ImplId>())
907 .sum::<usize>()
908}
909
910fn members_named<'a>(index: &'a Index, owner: ItemId, name: &str) -> &'a [ItemId] {
912 work::add(Work::ReachSteps, 1);
913 index
914 .assoc
915 .get(&owner)
916 .and_then(|members| members.get(name))
917 .map_or(&[], Vec::as_slice)
918}
919
920fn trait_segments(written: &str) -> Option<(bool, Vec<String>)> {
924 if written.starts_with('!') {
925 return None;
926 }
927 let path = &written[..written.find(['<', '(']).unwrap_or(written.len())];
928 let (leading_colon, path) = match path.strip_prefix("::") {
929 Some(rest) => (true, rest),
930 None => (false, path),
931 };
932 let segs: Vec<String> = path
933 .split("::")
934 .map(|seg| seg.strip_prefix("r#").unwrap_or(seg).to_owned())
935 .collect();
936 segs.iter()
937 .all(|seg| !seg.is_empty() && seg.chars().all(|c| c == '_' || c.is_alphanumeric()))
938 .then_some((leading_colon, segs))
939}
940
941struct Walk<'a> {
944 index: &'a Index,
945 files: &'a BTreeMap<RelPath, SourceFile>,
946 meter: &'a Meter,
947 homes: Vec<Home>,
949 blocks_of_type: BTreeMap<ItemId, Vec<ImplId>>,
951 blocks_of_module: BTreeMap<usize, Vec<ImplId>>,
953 block_modules_of: BTreeMap<ItemId, Vec<usize>>,
956 roots: BTreeSet<ItemId>,
958 files_runs: BTreeMap<(RelPath, u16), FileRuns>,
961 seen: BTreeMap<Ctx, BTreeSet<Box<str>>>,
965 blocks: BTreeMap<ImplId, BlockNames<'a>>,
967 format_identity: Option<format::Resolver>,
968}
969
970impl<'a> Walk<'a> {
971 fn new(
973 index: &'a Index,
974 files: &'a BTreeMap<RelPath, SourceFile>,
975 meter: &'a Meter,
976 (file, line): (&RelPath, usize),
977 ) -> Result<Self, ReachError> {
978 let mut homes = vec![Home::default(); index.items.len()];
979 fill_homes(index, &mut homes, false);
982 let mut blocks_of_type: BTreeMap<ItemId, Vec<ImplId>> = BTreeMap::new();
983 let mut blocks_of_module: BTreeMap<usize, Vec<ImplId>> = BTreeMap::new();
984 for block in &index.impl_blocks {
985 blocks_of_module
986 .entry(block.module_index)
987 .or_default()
988 .push(block.id);
989 for ty in &block.self_items {
990 work::add(Work::ReachSteps, 1);
991 blocks_of_type.entry(*ty).or_default().push(block.id);
992 }
993 }
994 let mut block_modules_of: BTreeMap<ItemId, Vec<usize>> = BTreeMap::new();
995 if !index.block_modules.is_empty() {
996 let mut in_module: BTreeMap<usize, Vec<ItemId>> = BTreeMap::new();
997 for item in &index.items {
998 if let Some(module) = homes[item.id.0].module {
999 in_module.entry(module).or_default().push(item.id);
1000 }
1001 }
1002 for site in &index.block_modules {
1003 work::add(
1004 Work::ReachSteps,
1005 1 + in_module.get(&site.parent).map_or(0, Vec::len),
1006 );
1007 let owner = in_module
1008 .get(&site.parent)
1009 .into_iter()
1010 .flatten()
1011 .map(|id| &index.items[id.0])
1012 .filter(|item| {
1013 item.file == site.file
1014 && item.span.start_byte <= site.span.0
1015 && site.span.1 <= item.span.end_byte
1016 })
1017 .min_by_key(|item| item.span.end_byte - item.span.start_byte);
1018 if let Some(owner) = owner {
1019 block_modules_of
1020 .entry(owner.id)
1021 .or_default()
1022 .push(site.module);
1023 }
1024 }
1025 }
1026 let roots: BTreeSet<ItemId> = index.root_items.values().copied().collect();
1027 let held = homes.capacity() * size_of::<Home>()
1028 + lists_bytes(&blocks_of_type)
1029 + lists_bytes(&blocks_of_module)
1030 + btree_map::<ItemId, Vec<usize>>()
1031 + block_modules_of
1032 .values()
1033 .map(|list| {
1034 btree_entry::<ItemId, Vec<usize>>() + list.capacity() * size_of::<usize>()
1035 })
1036 .sum::<usize>()
1037 + btree_map::<ItemId, ()>()
1038 + roots.len() * btree_entry::<ItemId, ()>()
1039 + btree_map::<(RelPath, u16), FileRuns>()
1040 + btree_map::<Ctx, BTreeSet<Box<str>>>()
1041 + btree_map::<ImplId, BlockNames<'_>>();
1042 meter
1043 .items(held, file, Some(line))
1044 .map_err(ReachError::Budget)?;
1045 Ok(Self {
1046 index,
1047 files,
1048 meter,
1049 homes,
1050 blocks_of_type,
1051 blocks_of_module,
1052 block_modules_of,
1053 roots,
1054 files_runs: BTreeMap::new(),
1055 seen: BTreeMap::new(),
1056 blocks: BTreeMap::new(),
1057 format_identity: None,
1058 })
1059 }
1060
1061 fn load(&mut self, file: &RelPath, module: usize) -> Result<(RelPath, u16), ReachError> {
1065 let key = (file.clone(), self.index.edition(module));
1066 if self.files_runs.contains_key(&key) {
1067 return Ok(key);
1068 }
1069 let text = self
1070 .files
1071 .get(file)
1072 .map_or("", |source| source.text.as_str());
1073 let lexed = lex(file, text, key.1)?;
1074 work::add(Work::ReachTokens, lexed.tokens);
1075 work::add(Work::ReachFormatTokens, lexed.format_tokens);
1076 work::add(Work::ReachFormatBytes, lexed.format_bytes);
1077 let mut units: Vec<(usize, usize)> = self
1078 .index
1079 .by_file
1080 .get(file)
1081 .into_iter()
1082 .flatten()
1083 .filter(|id| !self.roots.contains(id))
1084 .map(|id| {
1085 let span = &self.index.items[id.0].span;
1086 (span.start_byte, span.end_byte)
1087 })
1088 .collect();
1089 let first = self
1090 .index
1091 .impl_blocks
1092 .partition_point(|block| block.file < *file);
1093 units.extend(
1094 self.index.impl_blocks[first..]
1095 .iter()
1096 .take_while(|block| block.file == *file)
1097 .map(|block| (block.span.start_byte, block.span.end_byte)),
1098 );
1099 let calls_by_unit = lexed
1100 .formats
1101 .as_ref()
1102 .map_or_else(BTreeMap::new, |formats| {
1103 place_starts(
1104 formats
1105 .calls
1106 .iter()
1107 .enumerate()
1108 .map(|(at, call)| (at, call.start)),
1109 units.clone(),
1110 Work::ReachFormatTokens,
1111 )
1112 });
1113 let by_unit = place_runs(&lexed.runs, units);
1114 let mut held = btree_entry::<(RelPath, u16), FileRuns>()
1115 + lexed.runs.capacity() * size_of::<Run>()
1116 + lexed.segs.capacity() * size_of::<(usize, usize)>();
1117 if !by_unit.is_empty() {
1118 held += btree_map::<(usize, usize), Vec<usize>>();
1119 }
1120 for positions in by_unit.values() {
1121 held += btree_entry::<(usize, usize), Vec<usize>>()
1122 + positions.capacity() * size_of::<usize>();
1123 }
1124 if let Some(formats) = &lexed.formats {
1125 held += formats.retained_bytes();
1126 }
1127 if !calls_by_unit.is_empty() {
1128 held += btree_map::<(usize, usize), Vec<usize>>();
1129 for positions in calls_by_unit.values() {
1130 held += btree_entry::<(usize, usize), Vec<usize>>()
1131 + positions.capacity() * size_of::<usize>();
1132 }
1133 }
1134 if lexed.formats.is_some() && self.format_identity.is_none() {
1135 let identity = format::Resolver::new(self.index, self.files, self.meter, file)?;
1136 self.format_identity = Some(identity);
1137 }
1138 self.meter
1139 .items(held, file, None)
1140 .map_err(ReachError::Budget)?;
1141 self.files_runs.insert(
1142 key.clone(),
1143 FileRuns {
1144 runs: lexed.runs,
1145 segs: lexed.segs,
1146 by_unit,
1147 formats: lexed.formats,
1148 calls_by_unit,
1149 },
1150 );
1151 Ok(key)
1152 }
1153
1154 fn references(&mut self, unit: &Unit<'_>) -> Result<Vec<ItemId>, ReachError> {
1158 let key = self.load(unit.file, unit.module)?;
1159 let index = self.index;
1160 let text = self
1161 .files
1162 .get(unit.file)
1163 .map_or("", |source| source.text.as_str());
1164 let runs = &self.files_runs[&key];
1165 let mut out = Vec::new();
1166 let suppressed = format_references(
1167 index,
1168 self.meter,
1169 self.format_identity.as_ref(),
1170 &mut self.seen,
1171 unit,
1172 runs,
1173 &mut out,
1174 )?;
1175 for position in runs.by_unit.get(&unit.span).into_iter().flatten() {
1176 let run = runs.runs[*position];
1177 if run.start >= unit.before {
1178 break;
1179 }
1180 if suppressed.binary_search(&run.start).is_ok() {
1181 continue;
1182 }
1183 work::add(Work::ReachSteps, 1);
1184 let segs = &runs.segs[run.first..run.first + run.len];
1185 let word = |at: usize| &text[segs[at].0..segs[at].1];
1186 let (ctx, key) = match (run.kind, unit.owner) {
1187 (RunKind::Path, _) => {
1188 let mut key = String::from(if run.leading_colon { "::" } else { "" });
1189 for at in 0..segs.len() {
1190 if at > 0 {
1191 key.push_str("::");
1192 }
1193 key.push_str(word(at));
1194 }
1195 (Ctx::Module(unit.module, unit.test), key)
1196 }
1197 (RunKind::SelfPath, Some(owner)) if run.len > 1 => {
1199 (Ctx::Owner(owner), format!("Self::{}", word(1)))
1200 }
1201 (RunKind::Method, Some(owner)) => (Ctx::Owner(owner), format!(".{}", word(0))),
1202 (RunKind::SelfPath | RunKind::Method, _) => continue,
1203 };
1204 let mut held = btree_entry::<Box<str>, ()>() + key.len();
1205 if !self.seen.contains_key(&ctx) {
1206 held += btree_entry::<Ctx, BTreeSet<Box<str>>>() + btree_map::<Box<str>, ()>();
1207 }
1208 let seen = self.seen.entry(ctx).or_default();
1209 if seen.contains(key.as_str()) {
1210 continue;
1211 }
1212 self.meter
1213 .items(held, unit.file, Some(unit.line))
1214 .map_err(ReachError::Budget)?;
1215 seen.insert(key.into_boxed_str());
1216 work::add(Work::ReachPaths, 1);
1217 match (run.kind, ctx) {
1218 (RunKind::Path, _) => {
1219 let words: Vec<String> =
1220 (0..segs.len()).map(|at| word(at).to_owned()).collect();
1221 out.extend(index.reach_run(
1222 unit.module,
1223 &words,
1224 run.leading_colon,
1225 unit.test,
1226 Steps::QueryItems {
1227 meter: self.meter,
1228 file: unit.file,
1229 line: Some(unit.line),
1230 },
1231 )?);
1232 }
1233 (kind, Ctx::Owner(owner)) => {
1234 let (name, variant) = match kind {
1235 RunKind::SelfPath => (word(1), true),
1236 _ => (word(0), false),
1237 };
1238 let names = owner_names(
1239 index,
1240 self.meter,
1241 &mut self.blocks,
1242 owner,
1243 (name, variant),
1244 unit,
1245 )?;
1246 out.extend(names);
1247 }
1248 (_, Ctx::Module(..) | Ctx::Value(..)) => {}
1249 }
1250 }
1251 Ok(out)
1252 }
1253
1254 fn next(
1259 &mut self,
1260 node: Node,
1261 edge: Edge,
1262 first: bool,
1263 opened: &mut BTreeSet<ItemId>,
1264 ) -> Result<Vec<(Node, Edge)>, ReachError> {
1265 let index = self.index;
1266 let mut out = Vec::new();
1267 match node {
1268 Node::Item(id) => {
1269 let item = &index.items[id.0];
1270 if self.roots.contains(&id) {
1271 return Ok(out);
1272 }
1273 match item.kind {
1274 SymbolKind::Mod => {
1275 if matches!(edge, Edge::Root | Edge::Contains)
1276 && opened.insert(id)
1277 && let Some(module) = index.module_of.get(&id)
1278 {
1279 for child in &index.modules[*module].defs {
1280 work::add(Work::ReachSteps, 1);
1281 out.push((Node::Item(*child), Edge::Contains));
1282 }
1283 for block in self.blocks_of_module.get(module).into_iter().flatten() {
1284 work::add(Work::ReachSteps, 1);
1285 out.push((Node::Impl(*block), Edge::Contains));
1286 }
1287 }
1288 }
1289 SymbolKind::Struct
1290 | SymbolKind::Enum
1291 | SymbolKind::Union
1292 | SymbolKind::Trait
1293 if first =>
1294 {
1295 for member in index.assoc.get(&id).into_iter().flat_map(|m| m.values()) {
1296 for child in member {
1297 work::add(Work::ReachSteps, 1);
1298 out.push((Node::Item(*child), Edge::Contains));
1299 }
1300 }
1301 for block in self.blocks_of_type.get(&id).into_iter().flatten() {
1302 work::add(Work::ReachSteps, 1);
1303 out.push((Node::Impl(*block), Edge::ImplOf));
1304 }
1305 }
1306 _ => {}
1307 }
1308 if first {
1309 for &module in self.block_modules_of.get(&id).into_iter().flatten() {
1313 for child in &index.modules[module].defs {
1314 work::add(Work::ReachSteps, 1);
1315 out.push((Node::Item(*child), Edge::Contains));
1316 }
1317 for block in self.blocks_of_module.get(&module).into_iter().flatten() {
1318 work::add(Work::ReachSteps, 1);
1319 out.push((Node::Impl(*block), Edge::Contains));
1320 }
1321 }
1322 }
1323 let home = self.homes[id.0];
1324 if first && let Some(module) = home.module {
1325 let before = match (item.kind, &item.body) {
1327 (SymbolKind::Mod, Some(body)) => body.start_byte,
1328 _ => usize::MAX,
1329 };
1330 let unit = Unit {
1331 file: &item.file,
1332 line: item.name_line,
1333 span: (item.span.start_byte, item.span.end_byte),
1334 before,
1335 module,
1336 test: item.test != TestRole::None,
1337 owner: home.owner,
1338 };
1339 for found in self.references(&unit)? {
1340 work::add(Work::ReachSteps, 1);
1341 out.push((Node::Item(found), Edge::References));
1342 }
1343 }
1344 }
1345 Node::Impl(id) => {
1346 if first {
1347 let block = &index.impl_blocks[id.0];
1348 for member in &block.members {
1349 work::add(Work::ReachSteps, 1);
1350 out.push((Node::Item(*member), Edge::ImplOf));
1351 }
1352 let unit = Unit {
1353 file: &block.file,
1354 line: block.line,
1355 span: (block.span.start_byte, block.span.end_byte),
1356 before: usize::MAX,
1357 module: block.module_index,
1358 test: block.test != TestRole::None,
1359 owner: Some(Owner::Block(id)),
1360 };
1361 for found in self.references(&unit)? {
1362 work::add(Work::ReachSteps, 1);
1363 out.push((Node::Item(found), Edge::References));
1364 }
1365 }
1366 }
1367 }
1368 Ok(out)
1369 }
1370}
1371
1372fn format_references(
1373 index: &Index,
1374 meter: &Meter,
1375 identity: Option<&format::Resolver>,
1376 seen_paths: &mut BTreeMap<Ctx, BTreeSet<Box<str>>>,
1377 unit: &Unit<'_>,
1378 runs: &FileRuns,
1379 out: &mut Vec<ItemId>,
1380) -> Result<Vec<usize>, ReachError> {
1381 let mut suppressed = Vec::new();
1382 if let (Some(formats), Some(identity)) = (&runs.formats, identity) {
1383 for &position in runs.calls_by_unit.get(&unit.span).into_iter().flatten() {
1384 let call = &formats.calls[position];
1385 if call.start >= unit.before {
1386 break;
1387 }
1388 if !identity.standard(
1389 formats,
1390 call,
1391 index,
1392 unit,
1393 Steps::QueryItems {
1394 meter,
1395 file: unit.file,
1396 line: Some(unit.line),
1397 },
1398 )? {
1399 continue;
1400 }
1401 let Some(arguments) = &call.arguments else {
1402 continue;
1403 };
1404 let arguments = arguments
1405 .as_ref()
1406 .map_err(|refusal| ReachError::Source(refusal.error(unit.file)))?;
1407 suppressed.extend_from_slice(&arguments.bindings);
1408 for name in &arguments.captures {
1409 let ctx = Ctx::Value(unit.module, unit.test);
1410 let mut held = btree_entry::<Box<str>, ()>() + name.len();
1411 if !seen_paths.contains_key(&ctx) {
1412 held += btree_entry::<Ctx, BTreeSet<Box<str>>>() + btree_map::<Box<str>, ()>();
1413 }
1414 let seen = seen_paths.entry(ctx).or_default();
1415 if seen.contains(name.as_ref()) {
1416 continue;
1417 }
1418 meter
1419 .items(held, unit.file, Some(unit.line))
1420 .map_err(ReachError::Budget)?;
1421 seen.insert(name.clone());
1422 work::add(Work::ReachPaths, 1);
1423 out.extend(index.reach_value(
1424 unit.module,
1425 name,
1426 unit.test,
1427 Steps::QueryItems {
1428 meter,
1429 file: unit.file,
1430 line: Some(unit.line),
1431 },
1432 )?);
1433 }
1434 }
1435 }
1436 suppressed.sort_unstable();
1437 Ok(suppressed)
1438}
1439
1440fn owner_names<'a>(
1448 index: &'a Index,
1449 meter: &Meter,
1450 blocks: &mut BTreeMap<ImplId, BlockNames<'a>>,
1451 owner: Owner,
1452 (name, variant): (&str, bool),
1453 unit: &Unit<'_>,
1454) -> Result<Vec<ItemId>, ReachError> {
1455 let mut out: Vec<ItemId> = Vec::new();
1456 match owner {
1457 Owner::Trait(id) => out.extend_from_slice(members_named(index, id, name)),
1458 Owner::Block(id) => {
1459 let block = &index.impl_blocks[id.0];
1460 let names = block_names(index, meter, blocks, id, unit)?;
1461 for ty in &block.self_items {
1462 out.extend_from_slice(members_named(index, *ty, name));
1463 }
1464 if let Some(members) = names.members.get(name) {
1465 out.extend_from_slice(members);
1466 }
1467 for found in &names.traits {
1468 out.extend_from_slice(members_named(index, *found, name));
1469 }
1470 if variant && out.is_empty() {
1471 out.extend(
1472 block
1473 .self_items
1474 .iter()
1475 .filter(|ty| index.items[ty.0].kind == SymbolKind::Enum),
1476 );
1477 }
1478 }
1479 }
1480 Ok(out)
1481}
1482
1483fn block_names<'a, 'b>(
1487 index: &'a Index,
1488 meter: &Meter,
1489 blocks: &'b mut BTreeMap<ImplId, BlockNames<'a>>,
1490 id: ImplId,
1491 unit: &Unit<'_>,
1492) -> Result<&'b BlockNames<'a>, ReachError> {
1493 let slot = match blocks.entry(id) {
1494 Entry::Occupied(found) => return Ok(found.into_mut()),
1495 Entry::Vacant(slot) => slot,
1496 };
1497 let block = &index.impl_blocks[id.0];
1498 let mut names = BlockNames::default();
1499 if block.self_items.is_empty() {
1500 for member in &block.members {
1501 work::add(Work::ReachSteps, 1);
1502 names
1503 .members
1504 .entry(index.items[member.0].name.as_str())
1505 .or_default()
1506 .push(*member);
1507 }
1508 }
1509 if let Some((leading_colon, segs)) = block
1510 .trait_path
1511 .as_ref()
1512 .map(SharedStr::as_str)
1513 .and_then(trait_segments)
1514 {
1515 work::add(Work::ReachPaths, 1);
1516 names.traits = index
1517 .reach_run(
1518 block.module_index,
1519 &segs,
1520 leading_colon,
1521 block.test != TestRole::None,
1522 Steps::QueryItems {
1523 meter,
1524 file: unit.file,
1525 line: Some(unit.line),
1526 },
1527 )?
1528 .into_iter()
1529 .filter(|found| index.items[found.0].kind == SymbolKind::Trait)
1530 .collect();
1531 }
1532 let mut held =
1533 btree_entry::<ImplId, BlockNames<'_>>() + names.traits.capacity() * size_of::<ItemId>();
1534 if !names.members.is_empty() {
1535 held += btree_map::<&str, Vec<ItemId>>();
1536 }
1537 for members in names.members.values() {
1538 held += btree_entry::<&str, Vec<ItemId>>() + members.capacity() * size_of::<ItemId>();
1539 }
1540 meter
1541 .items(held, unit.file, Some(unit.line))
1542 .map_err(ReachError::Budget)?;
1543 Ok(slot.insert(names))
1544}
1545
1546fn place_of(index: &Index, node: Node) -> (&RelPath, usize) {
1548 match node {
1549 Node::Item(id) => {
1550 let item = &index.items[id.0];
1551 (&item.file, item.name_line)
1552 }
1553 Node::Impl(id) => {
1554 let block = &index.impl_blocks[id.0];
1555 (&block.file, block.line)
1556 }
1557 }
1558}
1559
1560pub(crate) fn reachable(
1564 index: &Index,
1565 files: &BTreeMap<RelPath, SourceFile>,
1566 (options, held): (&LoadOptions, usize),
1567 roots: &[Node],
1568) -> Result<Reachability, ReachError> {
1569 let mut sorted: Vec<Node> = Vec::with_capacity(roots.len());
1570 for root in roots {
1571 work::add(Work::ReachSteps, 1);
1572 match *root {
1573 Node::Item(id) if id.0 >= index.items.len() => return Err(ReachError::UnknownItem(id)),
1574 Node::Impl(id) if id.0 >= index.impl_blocks.len() => {
1575 return Err(ReachError::UnknownImpl(id));
1576 }
1577 node => sorted.push(node),
1578 }
1579 }
1580 sorted.sort_unstable();
1581 sorted.dedup();
1582 let Some(first) = sorted.first() else {
1583 return Ok(Reachability {
1584 reached: Vec::new(),
1585 at: BTreeMap::new(),
1586 });
1587 };
1588 let (file, line) = place_of(index, *first);
1589 let meter = Meter::query(options);
1590 meter
1591 .items(
1592 held + vec_first::<Reached>()
1593 + btree_map::<Node, usize>()
1594 + btree_map::<ItemId, ()>()
1595 + vec_first::<Queued>(),
1596 file,
1597 Some(line),
1598 )
1599 .map_err(ReachError::Budget)?;
1600 let mut walk = Walk::new(index, files, &meter, (file, line))?;
1601 let mut queue: VecDeque<Queued> = sorted
1602 .into_iter()
1603 .map(|node| (node, Edge::Root, None))
1604 .collect();
1605 let mut peak = queue.len();
1606 meter
1607 .items(peak * vec_slot::<Queued>(), file, Some(line))
1608 .map_err(ReachError::Budget)?;
1609 let mut reached: Vec<Reached> = Vec::new();
1610 let mut at: BTreeMap<Node, usize> = BTreeMap::new();
1611 let mut opened: BTreeSet<ItemId> = BTreeSet::new();
1612 while let Some((node, edge, from)) = queue.pop_front() {
1613 work::add(Work::ReachSteps, 1);
1614 let first = !at.contains_key(&node);
1615 let (file, line) = place_of(index, node);
1616 if first {
1617 meter
1618 .items(
1619 vec_slot::<Reached>() + btree_entry::<Node, usize>(),
1620 file,
1621 Some(line),
1622 )
1623 .map_err(ReachError::Budget)?;
1624 at.insert(node, reached.len());
1625 reached.push(Reached { node, edge, from });
1626 }
1627 let was_opened = opened.len();
1628 for (next, by) in walk.next(node, edge, first, &mut opened)? {
1629 let opens = matches!(next, Node::Item(id) if index.items[id.0].kind == SymbolKind::Mod && by == Edge::Contains && !opened.contains(&id));
1630 if opens || !at.contains_key(&next) {
1631 queue.push_back((next, by, Some(node)));
1632 }
1633 }
1634 let grown = queue.len().saturating_sub(peak) * vec_slot::<Queued>()
1636 + (opened.len() - was_opened) * btree_entry::<ItemId, ()>();
1637 peak = peak.max(queue.len());
1638 if grown > 0 {
1639 meter
1640 .items(grown, file, Some(line))
1641 .map_err(ReachError::Budget)?;
1642 }
1643 }
1644 Ok(Reachability { reached, at })
1645}
1646
1647#[cfg(test)]
1648mod tests {
1649 use std::fmt::Write as _;
1650 use std::mem::size_of;
1651
1652 use super::{DECLARES, Run, RunKind, Walk, lex_text, place_runs};
1653 use crate::budget::Budget;
1654 use crate::error::LoadErrorKind;
1655 use crate::item::Namespace;
1656 use crate::meter::{Meter, Steps};
1657 use crate::reach::{Node, ReachError};
1658 use crate::work::{self, Work};
1659 use crate::{LoadOptions, MemoryTree, Workspace};
1660
1661 fn runs_in(edition: u16, text: &str) -> Vec<(String, usize)> {
1665 let lexed = lex_text(text, edition).unwrap_or_else(|failure| panic!("{}", failure.message));
1666 lexed
1667 .runs
1668 .iter()
1669 .map(|run| {
1670 let words: Vec<&str> = lexed.segs[run.first..run.first + run.len]
1671 .iter()
1672 .map(|(start, end)| &text[*start..*end])
1673 .collect();
1674 let shown = match run.kind {
1675 RunKind::Method => format!(".{}", words.join("::")),
1676 RunKind::Path | RunKind::SelfPath => format!(
1677 "{}{}",
1678 if run.leading_colon { "::" } else { "" },
1679 words.join("::")
1680 ),
1681 };
1682 (shown, run.start)
1683 })
1684 .collect()
1685 }
1686
1687 fn runs(text: &str) -> Vec<(String, usize)> {
1688 runs_in(2021, text)
1689 }
1690
1691 fn texts_in(edition: u16, text: &str) -> Vec<String> {
1693 runs_in(edition, text)
1694 .into_iter()
1695 .map(|(text, _)| text)
1696 .collect()
1697 }
1698
1699 fn texts(text: &str) -> Vec<String> {
1701 texts_in(2021, text)
1702 }
1703
1704 #[test]
1705 fn a_run_is_an_identifier_path_that_no_dot_precedes_with_its_first_byte() {
1706 assert_eq!(runs("a::b::c"), [("a::b::c".to_owned(), 0)]);
1707 assert_eq!(texts("x.helper(); x.0.y"), ["x", "x"]);
1708 assert_eq!(texts("0..LIMIT; ..=END"), ["LIMIT", "END"]);
1709 assert_eq!(texts("::std::fmt::Debug"), ["::std::fmt::Debug"]);
1710 assert_eq!(texts("Vec::<u8>::new()"), ["Vec", "u8"]);
1711 assert_eq!(texts("<T as Tr>::f"), ["T", "Tr"]);
1712 assert_eq!(texts("r#match::x"), ["match::x"]);
1713 assert_eq!(texts("a :: b"), ["a::b"]);
1714 assert_eq!(texts("f(a::b, c)"), ["f", "a::b", "c"]);
1715 assert_eq!(runs("r#gen::x"), [("gen::x".to_owned(), 0)]);
1717 }
1718
1719 #[test]
1720 fn path_keywords_start_a_run_and_other_keywords_are_no_segment() {
1721 assert_eq!(
1722 texts("crate::a; self::b; super::super::c; self::super::d"),
1723 ["crate::a", "self::b", "super::super::c", "self::super::d"]
1724 );
1725 assert_eq!(texts("a::crate; a::self::b"), ["a", "a"]);
1727 assert_eq!(texts("r#fn::r#match"), ["fn::match"]);
1728 assert_eq!(texts("pub use a as b;"), ["a", "b"]);
1729 assert_eq!(
1731 texts("Self::new(); impl Tr for S; a::Self::b; ::Self::c"),
1732 ["Self::new", "Tr", "S", "a"]
1733 );
1734 assert_eq!(texts("Self { a: 1 }; Self(2)"), ["Self", "Self"]);
1735 }
1736
1737 #[test]
1738 fn the_keywords_are_those_of_the_edition() {
1739 let text = "async(); await(); dyn(); try(); gen(); r#gen(); r#try()";
1740 assert_eq!(
1741 texts_in(2015, text),
1742 ["async", "await", "dyn", "try", "gen", "gen", "try"]
1743 );
1744 for edition in [2018, 2021] {
1745 assert_eq!(texts_in(edition, text), ["gen", "gen", "try"], "{edition}");
1746 }
1747 assert_eq!(texts_in(2024, text), ["gen", "try"]);
1748 assert_eq!(texts_in(2015, "a::fn::b; a::dyn::b"), ["a", "a::dyn::b"]);
1750 assert_eq!(texts_in(2024, "a::gen::b; a::r#gen::b"), ["a", "a::gen::b"]);
1751 }
1752
1753 #[test]
1754 fn a_lifetime_a_metavariable_a_declared_name_and_a_bound_name_are_no_run() {
1755 assert_eq!(texts("&'a T; 'label: loop {}"), ["T"]);
1756 assert_eq!(texts("&'static Foo"), ["Foo"]);
1757 assert_eq!(texts("$x; $crate::helper()"), ["crate::helper"]);
1758 assert_eq!(texts("fn helper(x: u8) -> Foo {}"), ["u8", "Foo"]);
1759 assert_eq!(
1760 texts(
1761 "struct S { helper: u8 } enum E {} trait T {} type A = B; mod m {} const C: u8 = 1; static D: X = Y;"
1762 ),
1763 ["u8", "B", "u8", "X", "Y"]
1764 );
1765 assert_eq!(
1766 texts("macro_rules! m { () => { g() } }"),
1767 ["macro_rules", "g"]
1768 );
1769 assert_eq!(texts("S { helper: 1, other }"), ["S", "other"]);
1770 assert_eq!(texts("where T::Assoc: Bound"), ["T::Assoc", "Bound"]);
1771 assert_eq!(texts("x: ::std::Y"), ["::std::Y"]);
1772 assert_eq!(texts("x:&Y"), ["Y"]);
1773 }
1774
1775 #[test]
1776 fn const_declares_nothing_so_a_pointer_and_a_raw_borrow_name_their_path() {
1777 assert!(!DECLARES.contains(&"const"));
1778 assert_eq!(
1779 texts("fn f(p: *const Helper, q: *mut Other) {}"),
1780 ["Helper", "Other"]
1781 );
1782 assert_eq!(
1783 texts("&raw const VALUE; &raw mut OTHER"),
1784 ["raw", "VALUE", "raw", "OTHER"]
1785 );
1786 assert_eq!(
1789 texts("const C: u8 = 1; pub const D: E = F;"),
1790 ["u8", "E", "F"]
1791 );
1792 assert_eq!(
1793 texts("const fn helper() {} const unsafe fn other() {}"),
1794 Vec::<String>::new()
1795 );
1796 assert_eq!(texts("const { g() }"), ["g"]);
1797 assert_eq!(texts("fn f<const N: usize>() {}"), ["usize"]);
1798 assert_eq!(texts("impl<const N: usize> S<N> {}"), ["usize", "S", "N"]);
1799 }
1800
1801 #[test]
1802 fn a_where_clause_keeps_the_type_its_bound_is_put_on() {
1803 assert_eq!(
1804 texts("fn f<T>() where Helper: Clone, T: Into<Other> {}"),
1805 ["T", "Helper", "Clone", "T", "Into", "Other"]
1806 );
1807 assert_eq!(
1810 texts("fn f(helper: u8) where T: X { S { field: 1 } }"),
1811 ["u8", "T", "X", "S"]
1812 );
1813 assert_eq!(
1814 texts("fn g() where Self: Sized; fn h(x: u8) {}"),
1815 ["Self", "Sized", "u8"]
1816 );
1817 assert_eq!(
1818 texts(
1819 "struct S<T> where T: X { field: u8 } struct P(u8) where Q: Y; static Z: u8 = 0;"
1820 ),
1821 ["T", "T", "X", "u8", "u8", "Q", "Y", "u8"]
1822 );
1823 assert_eq!(texts("fn f<T: Clone>() {}"), ["Clone"]);
1825 }
1826
1827 #[test]
1828 fn a_name_called_on_self_is_a_method_run_and_a_field_of_self_is_not() {
1829 assert_eq!(
1830 texts("self.helper(); self.field; self.turbo::<u8>(); other.method(); self.0.x()"),
1831 [
1832 "self", ".helper", "self", "self", ".turbo", "u8", "other", "self"
1833 ]
1834 );
1835 let text = "fn f(&self) { self.r#match() }";
1836 assert_eq!(
1837 runs(text),
1838 [
1839 ("self".to_owned(), text.find("self)").expect("the receiver")),
1840 ("self".to_owned(), text.find("self.").expect("self")),
1841 (
1842 ".match".to_owned(),
1843 text.find("r#match").expect("the method")
1844 ),
1845 ]
1846 );
1847 assert_eq!(
1849 texts("self::helper(); s.helper(); Self.x()"),
1850 ["self::helper", "s", "Self"]
1851 );
1852 }
1853
1854 #[test]
1855 fn a_byte_order_mark_and_a_shebang_are_left_out_and_offsets_are_those_of_the_text() {
1856 let text = "\u{feff}fn f() { g() }";
1857 assert_eq!(runs(text), [("g".to_owned(), text.find('g').expect("g"))]);
1858 let text = "#!/usr/bin/env run\nfn f() { g() }";
1859 assert_eq!(runs(text), [("g".to_owned(), text.find("g(").expect("g"))]);
1860 assert_eq!(texts("#![allow(unused)]\nfn f() {}"), ["allow", "unused"]);
1862 let failure = lex_text("fn f() {\n\"", 2021).expect_err("an open string");
1864 assert_eq!(failure.line, 2);
1865 }
1866
1867 #[test]
1872 fn a_doc_comment_is_no_run_whatever_character_ends_it() {
1873 let text = "//! Crate §\n/// Calls abc\n/// See §1,\n/** Block ß */\n\
1874 #[doc = \"x\"]\npub fn f() { a::b() }\nfn abc() {}\n";
1875 let ws = load(text);
1876 let site = |path: &str| {
1877 Node::Item(
1878 ws.resolve_in(path, Namespace::Value)
1879 .unwrap_or_else(|e| panic!("{path}: {e}"))
1880 .sites[0],
1881 )
1882 };
1883 let reached = ws
1884 .reachable(&[site("demo::f")])
1885 .unwrap_or_else(|e| panic!("{e}"));
1886 assert!(!reached.contains(site("demo::abc")));
1887 assert_eq!(
1888 runs(text),
1889 [
1890 ("doc".to_owned(), text.find("doc").expect("the attribute")),
1891 ("a::b".to_owned(), text.find("a::b").expect("the call")),
1892 ]
1893 );
1894 }
1895
1896 fn run_at(start: usize) -> Run {
1897 Run {
1898 start,
1899 first: 0,
1900 len: 1,
1901 leading_colon: false,
1902 kind: RunKind::Path,
1903 }
1904 }
1905
1906 #[test]
1907 fn each_run_goes_to_the_innermost_unit_that_holds_its_start() {
1908 let units = vec![(120, 150), (10, 20), (0, 100), (30, 40), (0, 100)];
1911 let runs: Vec<Run> = [5, 10, 25, 35, 99, 100, 130, 160]
1912 .into_iter()
1913 .map(run_at)
1914 .collect();
1915 let placed = place_runs(&runs, units);
1916 let by: Vec<((usize, usize), Vec<usize>)> = placed.into_iter().collect();
1917 assert_eq!(
1918 by,
1919 [
1920 ((0, 100), vec![0, 2, 4]),
1921 ((10, 20), vec![1]),
1922 ((30, 40), vec![3]),
1923 ((120, 150), vec![6]),
1924 ]
1925 );
1926 }
1927
1928 const MANIFEST: &str = "[package]\nname = \"demo\"\nversion = \"0.1.0\"\nedition = \"2021\"\n";
1929
1930 fn load_with(text: &str, options: &LoadOptions) -> Workspace {
1931 let tree = MemoryTree::from([("Cargo.toml", MANIFEST), ("src/lib.rs", text)]);
1932 Workspace::load_with(&tree, &["."], options).unwrap_or_else(|e| panic!("{e}"))
1933 }
1934
1935 fn load(text: &str) -> Workspace {
1936 load_with(text, &LoadOptions::default())
1937 }
1938
1939 fn fan(items: usize, references: usize) -> Workspace {
1942 let mut text = String::new();
1943 for i in 0..items {
1944 let calls = format!("h{i}(); ").repeat(references);
1945 writeln!(text, "pub fn f{i}() {{ {calls}}}\nfn h{i}() {{}}").expect("write");
1946 }
1947 load(&text)
1948 }
1949
1950 const KINDS: [Work; 6] = [
1952 Work::ReachTokens,
1953 Work::ReachUnits,
1954 Work::ReachPaths,
1955 Work::ReachSteps,
1956 Work::SegmentReads,
1957 Work::Lookups,
1958 ];
1959
1960 fn work_of(ws: &Workspace, roots: &[Node]) -> ([usize; 6], usize) {
1963 let (reached, tally) = work::measure(usize::MAX, || ws.reachable(roots));
1964 let reached = reached.unwrap_or_else(|e| panic!("{e}")).reached.len();
1965 (KINDS.map(|kind| tally.get(kind)), reached)
1966 }
1967
1968 fn fan_work(items: usize, references: usize) -> ([usize; 6], usize) {
1971 let ws = fan(items, references);
1972 let roots: Vec<Node> = (0..items)
1973 .map(|i| {
1974 let path = format!("demo::f{i}");
1975 Node::Item(ws.resolve_in(&path, Namespace::Value).expect("f").sites[0])
1976 })
1977 .collect();
1978 work_of(&ws, &roots)
1979 }
1980
1981 #[test]
1982 fn the_work_of_a_walk_is_counted_exactly() {
1983 for (n, r) in [(1, 1), (3, 2), (5, 4)] {
1984 let ([tokens, units, paths, steps, ..], reached) = fan_work(n, r);
1985 assert_eq!(reached, 2 * n, "{n} {r}");
1986 assert_eq!(tokens, n * (9 + 3 * r), "{n} {r}");
1989 assert_eq!(units, n * r + 4 * n - 3, "{n} {r}");
1993 assert_eq!(paths, n, "{n} {r}");
1996 assert_eq!(steps, 6 * n + 1 + n * r, "{n} {r}");
2001 }
2002 }
2003
2004 #[test]
2005 fn the_work_grows_with_the_items_and_the_references_and_not_their_product() {
2006 let by_items: Vec<[usize; 6]> = [10, 20, 30].map(|n| fan_work(n, 3).0).to_vec();
2010 let by_references: Vec<[usize; 6]> = [2, 4, 6].map(|r| fan_work(10, r).0).to_vec();
2011 for sizes in [&by_items, &by_references] {
2012 for (kind, name) in KINDS.iter().enumerate() {
2013 let first = sizes[1][kind] - sizes[0][kind];
2014 let second = sizes[2][kind] - sizes[1][kind];
2015 assert_eq!(first, second, "{name:?}: {sizes:?}");
2016 }
2017 }
2018 assert_eq!(by_references[0][2], by_references[2][2]);
2021 }
2022
2023 fn kinds(types: usize, members: usize) -> String {
2031 let mut text = String::from("pub trait Tr {\n");
2032 for j in 0..members {
2033 writeln!(text, " fn t{j}(&self) -> u8;").expect("write");
2034 }
2035 text.push_str("}\npub mod top {\n");
2036 for i in 0..types {
2037 writeln!(
2038 text,
2039 "pub mod m{i} {{\n\
2040 pub struct T{i} {{ f: u8 }}\n\
2041 pub enum E{i} {{ A, B }}\n\
2042 pub type A{i} = T{i};\n\
2043 const K{i}: u8 = 1;\n\
2044 static S{i}: u8 = 2;\n\
2045 pub fn helper{i}() -> E{i} {{ E{i}::A }}\n\
2046 impl E{i} {{ pub fn is_a(&self) -> bool {{ matches!(self, Self::A) }} }}"
2047 )
2048 .expect("write");
2049 writeln!(text, "impl T{i} {{").expect("write");
2050 for j in 0..members {
2051 let next = (j + 1) % members;
2052 writeln!(
2053 text,
2054 " pub fn a{j}(&self) -> u8 {{ Self::a{next}(self) + self.a{next}() + K{i} + S{i} }}"
2055 )
2056 .expect("write");
2057 }
2058 writeln!(text, "}}\nimpl crate::Tr for T{i} {{").expect("write");
2059 for j in 0..members {
2060 writeln!(text, " fn t{j}(&self) -> u8 {{ self.a{j}() }}").expect("write");
2061 }
2062 text.push_str("}\n}\n");
2063 }
2064 text.push_str("}\n");
2065 text
2066 }
2067
2068 fn kinds_work(types: usize, members: usize) -> ([usize; 6], usize) {
2070 let ws = load(&kinds(types, members));
2071 let top = ws
2072 .resolve_in("demo::top", Namespace::Type)
2073 .expect("top")
2074 .sites[0];
2075 work_of(&ws, &[Node::Item(top)])
2076 }
2077
2078 #[test]
2079 fn the_work_over_types_impl_blocks_traits_and_members_grows_with_each_and_not_their_product() {
2080 for (n, k) in [(1, 1), (2, 3), (4, 2)] {
2085 let (_, reached) = kinds_work(n, k);
2086 assert_eq!(reached, 2 + k + n * (11 + 2 * k), "{n} {k}");
2087 }
2088 let by_types: Vec<[usize; 6]> = [4, 8, 12].map(|n| kinds_work(n, 3).0).to_vec();
2093 let by_members: Vec<[usize; 6]> = [2, 4, 6].map(|k| kinds_work(4, k).0).to_vec();
2094 for sizes in [&by_types, &by_members] {
2095 for (kind, name) in KINDS.iter().enumerate() {
2096 let first = sizes[1][kind] - sizes[0][kind];
2097 let second = sizes[2][kind] - sizes[1][kind];
2098 assert_eq!(first, second, "{name:?}: {sizes:?}");
2099 }
2100 }
2101 for (n, k) in [(1, 1), (2, 3), (4, 2), (3, 5)] {
2112 let ([tokens, units, paths, steps, segments, lookups], _) = kinds_work(n, k);
2113 assert_eq!(tokens, 8 + 9 * k + n * (83 + 38 * k), "{n} {k}");
2114 assert_eq!(units, 4 * k + n * (39 + 16 * k), "{n} {k}");
2115 assert_eq!(paths, 2 + n * (14 + 3 * k), "{n} {k}");
2116 assert_eq!(steps, 5 + 5 * k + n * (68 + 31 * k), "{n} {k}");
2117 assert_eq!(segments, 9 * n, "{n} {k}");
2118 assert_eq!(lookups, 3 + 34 * n, "{n} {k}");
2119 }
2120 }
2121
2122 #[test]
2123 fn a_path_of_fifty_thousand_segments_is_walked_once_and_not_once_for_each_prefix() {
2124 const SEGMENTS: usize = 50_000;
2125 let text = format!(
2126 "pub mod m {{ pub use crate::m; pub struct End; }}\npub type T = {}End;\n",
2127 "m::".repeat(SEGMENTS)
2128 );
2129 let ws = load(&text);
2130 let alias = ws.resolve("demo::T").expect("the alias").sites[0];
2131 let end = ws.resolve("demo::m::End").expect("the struct").sites[0];
2132 let segments = SEGMENTS + 1;
2137 let (reached, tally) = work::measure_kind(Work::SegmentReads, 4 * segments, || {
2138 ws.reachable(&[Node::Item(alias)])
2139 });
2140 let reached = reached.unwrap_or_else(|e| panic!("{e}"));
2141 assert!(reached.contains(Node::Item(end)));
2142 assert!(tally.get(Work::SegmentReads) >= segments);
2143 assert!(tally.get(Work::Lookups) <= 4 * segments);
2144 assert_eq!(tally.get(Work::ReachPaths), 1);
2145 }
2146
2147 fn dense(runs: usize) -> String {
2149 format!("pub fn f() {{ {}}}\nfn a() {{}}\n", "a; ".repeat(runs))
2150 }
2151
2152 fn walk_charge(text: &str) -> usize {
2155 let ws = load(text);
2156 let held = ws.usage().item_bytes;
2157 let walk = |limit: usize| {
2158 let ws = load_with(
2159 text,
2160 &LoadOptions {
2161 max_item_bytes: limit,
2162 ..LoadOptions::default()
2163 },
2164 );
2165 let f = ws.resolve_in("demo::f", Namespace::Value).expect("f").sites[0];
2166 ws.reachable(&[Node::Item(f)])
2167 };
2168 let (mut low, mut high) = (held, held + (1 << 24));
2169 assert!(walk(high).is_ok());
2170 while high - low > 1 {
2171 let mid = low + (high - low) / 2;
2172 if walk(mid).is_ok() {
2173 high = mid;
2174 } else {
2175 low = mid;
2176 }
2177 }
2178 let error = walk(low).expect_err("one byte less is refused");
2179 match error {
2180 ReachError::Budget(error) => {
2181 assert!(
2182 matches!(
2183 error.kind,
2184 LoadErrorKind::Budget {
2185 budget: Budget::ItemBytes,
2186 limit
2187 } if limit == low
2188 ),
2189 "{error}"
2190 );
2191 assert_eq!(error.file.as_str(), "src/lib.rs");
2192 }
2193 other => panic!("{other}"),
2194 }
2195 high - held
2196 }
2197
2198 #[test]
2199 fn what_the_walk_holds_is_charged_to_the_item_bytes_budget_on_from_the_load() {
2200 let per_run = size_of::<Run>() + size_of::<(usize, usize)>() + size_of::<usize>();
2203 let charges = [1000, 2000, 3000].map(|runs| walk_charge(&dense(runs)));
2204 assert_eq!(charges[1] - charges[0], 1000 * per_run);
2205 assert_eq!(charges[2] - charges[1], 1000 * per_run);
2206 #[cfg(target_pointer_width = "64")]
2208 assert_eq!(per_run, 56);
2209 assert!(per_run < 20 * 3, "{per_run}");
2210 }
2211
2212 #[test]
2213 fn format_candidates_charge_owned_bytes_and_return_worker_work_to_the_caller() {
2214 let source = |calls| {
2215 format!(
2216 "const VALUE:u32=7; pub fn f(){{ {} }}",
2217 "let _=format!(\"{VALUE}\");".repeat(calls)
2218 )
2219 };
2220 let samples = [32, 64, 96].map(|calls| {
2221 let text = source(calls);
2222 let ws = load(&text);
2223 let root = ws.resolve_in("demo::f", Namespace::Value).expect("f").sites[0];
2224 let capture = ws
2225 .resolve_in("demo::VALUE", Namespace::Value)
2226 .expect("VALUE")
2227 .sites[0];
2228 let (reached, tally) = work::measure(100_000, || ws.reachable(&[Node::Item(root)]));
2229 assert!(reached.expect("reachability").contains(Node::Item(capture)));
2230 let tokens = tally.get(Work::ReachFormatTokens);
2231 let bytes = tally.get(Work::ReachFormatBytes);
2232 assert!(tokens > calls, "worker token work was lost");
2233 assert!(
2234 bytes >= calls * "{VALUE}".len(),
2235 "worker decode work was lost"
2236 );
2237 (tokens, bytes, walk_charge(&text))
2238 });
2239 for at in 0..2 {
2240 let get = |n: usize| if at == 0 { samples[n].0 } else { samples[n].1 };
2241 assert_eq!(get(2) - get(1), get(1) - get(0));
2242 }
2243 assert!(samples[1].2 > samples[0].2);
2244 assert_eq!(samples[2].2 - samples[1].2, samples[1].2 - samples[0].2);
2245 }
2246
2247 #[test]
2248 fn code_prefix_reads_share_one_query_account_and_refuse_one_less() {
2249 let tree = MemoryTree::from([
2250 (
2251 "Cargo.toml",
2252 "[package]\nname='demo'\nversion='0.1.0'\nedition='2021'\n",
2253 ),
2254 (
2255 "src/lib.rs",
2256 "mod a { pub struct X {} } mod b { pub use crate::a::*; } pub use b::*;",
2257 ),
2258 ]);
2259 let ws = Workspace::load(&tree, &["."]).expect("glob source");
2260 let index = ws.index();
2261 let root = index.target_roots[0];
2262 let (file, line) = index.module_site(root);
2263 let words = ["X".to_owned()];
2264 let run = |limit| {
2265 let options = LoadOptions {
2266 max_query_work: limit,
2267 ..LoadOptions::default()
2268 };
2269 let meter = Meter::query(&options);
2270 let answer = index.reach_run(
2271 root,
2272 &words,
2273 false,
2274 false,
2275 Steps::QueryItems {
2276 meter: &meter,
2277 file: &file,
2278 line,
2279 },
2280 );
2281 (answer, meter.usage())
2282 };
2283 let (answer, usage) = run(usize::MAX);
2284 let expected = answer.expect("native admitted resolver");
2285 assert!(!expected.is_empty());
2286 assert!(usage.work > 0);
2287 assert!(usage.item_bytes > 0);
2288 assert_eq!(usage.glob_bytes, 0);
2289 assert_eq!(run(usage.work).0.expect("exact work"), expected);
2290 let error = run(usage.work - 1).0.expect_err("one work unit short");
2291 assert!(
2292 matches!(error.kind, LoadErrorKind::Budget { budget: Budget::Work, limit }
2293 if limit == usage.work - 1)
2294 );
2295 assert_eq!(error.file.as_str(), "src/lib.rs");
2296 }
2297
2298 #[test]
2299 fn a_shared_files_edition_caches_are_each_counted_and_charged_once() {
2300 let tree = MemoryTree::from([
2301 ("Cargo.toml", "[workspace]\nmembers = [\"old\", \"new\"]\n"),
2302 (
2303 "old/Cargo.toml",
2304 "[package]\nname = \"old\"\nversion = \"0.1.0\"\nedition = \"2021\"\n",
2305 ),
2306 (
2307 "new/Cargo.toml",
2308 "[package]\nname = \"new\"\nversion = \"0.1.0\"\nedition = \"2024\"\n",
2309 ),
2310 (
2311 "old/src/lib.rs",
2312 "#[path = \"../../shared.rs\"] mod shared;\n",
2313 ),
2314 (
2315 "new/src/lib.rs",
2316 "#[path = \"../../shared.rs\"] mod shared;\n",
2317 ),
2318 ("shared.rs", "pub fn f() { r#gen() }\nfn r#gen() {}\n"),
2319 ]);
2320 let ws = Workspace::load(&tree, &["."]).expect("shared source");
2321 let options = LoadOptions::default();
2322 let meter = Meter::new(&options);
2323 let files = ws
2324 .files()
2325 .map(|source| {
2326 (
2327 source.path.clone(),
2328 crate::SourceFile {
2329 path: source.path.clone(),
2330 package: source.package.clone(),
2331 shipping: source.shipping,
2332 test: source.test,
2333 text: source.text.clone(),
2334 facts: source.facts.clone(),
2335 reached: source.reached.clone(),
2336 },
2337 )
2338 })
2339 .collect();
2340 let item = |name| {
2341 ws.resolve_in(name, Namespace::Value)
2342 .expect("function")
2343 .sites[0]
2344 };
2345 let old = item("old::shared::f");
2346 let new = item("new::shared::f");
2347 let file = &ws.item(old).expect("old function").file;
2348 assert_eq!(file, &ws.item(new).expect("new function").file);
2349 let mut walk = Walk::new(ws.index(), &files, &meter, (file, 1)).expect("walk tables");
2350 let old_module = walk.homes[old.0].module.expect("old module");
2351 let new_module = walk.homes[new.0].module.expect("new module");
2352 let (_, first) = work::measure(usize::MAX, || {
2353 walk.load(file, old_module).expect("old cache")
2354 });
2355 let first_bytes = meter.usage().item_bytes;
2356 let (_, repeated) = work::measure(usize::MAX, || {
2357 walk.load(file, old_module).expect("old cache again")
2358 });
2359 assert!(first.get(Work::ReachTokens) > 0);
2360 assert_eq!(repeated.get(Work::ReachTokens), 0);
2361 assert_eq!(meter.usage().item_bytes, first_bytes);
2362 let (_, second) = work::measure(usize::MAX, || {
2363 walk.load(file, new_module).expect("new cache")
2364 });
2365 let both_bytes = meter.usage().item_bytes;
2366 assert_eq!(second.get(Work::ReachTokens), first.get(Work::ReachTokens));
2367 assert!(both_bytes > first_bytes);
2368 assert_eq!(walk.files_runs.len(), 2);
2369 let (_, repeated) = work::measure(usize::MAX, || {
2370 walk.load(file, new_module).expect("new cache again")
2371 });
2372 assert_eq!(repeated.get(Work::ReachTokens), 0);
2373 assert_eq!(meter.usage().item_bytes, both_bytes);
2374
2375 let under = |limit| -> Result<usize, ReachError> {
2376 let options = LoadOptions {
2377 max_item_bytes: limit,
2378 ..LoadOptions::default()
2379 };
2380 let meter = Meter::new(&options);
2381 let mut walk = Walk::new(ws.index(), &files, &meter, (file, 1))?;
2382 walk.load(file, old_module)?;
2383 walk.load(file, new_module)?;
2384 Ok(meter.usage().item_bytes)
2385 };
2386 assert_eq!(
2387 under(both_bytes).expect("exact retained-byte limit"),
2388 both_bytes
2389 );
2390 let error = under(both_bytes - 1).expect_err("one byte short refuses second cache");
2391 assert!(
2392 matches!(error, ReachError::Budget(ref load) if matches!(load.kind,
2393 LoadErrorKind::Budget { budget: Budget::ItemBytes, limit } if limit == both_bytes - 1))
2394 );
2395 }
2396}