use std::collections::btree_map::Entry;
use std::collections::{BTreeMap, BTreeSet, VecDeque};
use std::error::Error;
use std::fmt;
use std::mem::size_of;
use std::panic;
use std::str::FromStr;
use std::thread;
use proc_macro2::{Delimiter, Spacing, TokenStream, TokenTree};
use crate::cost::{btree_entry, btree_map, vec_first, vec_slot};
use crate::error::{LoadError, LoadErrorKind};
use crate::facts::TestRole;
use crate::index::Index;
use crate::item::{ImplId, ItemId, SharedStr, SymbolKind};
use crate::meter::{Meter, Steps};
use crate::options::LoadOptions;
use crate::parse::PARSE_STACK_BYTES;
use crate::path::RelPath;
use crate::work::{self, Work};
use crate::workspace::SourceFile;
mod format;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub enum Node {
Item(ItemId),
Impl(ImplId),
}
impl From<ItemId> for Node {
fn from(id: ItemId) -> Self {
Self::Item(id)
}
}
impl From<ImplId> for Node {
fn from(id: ImplId) -> Self {
Self::Impl(id)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
#[non_exhaustive]
pub enum Edge {
Root,
Contains,
ImplOf,
References,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub struct Reached {
pub node: Node,
pub edge: Edge,
pub from: Option<Node>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub struct Reachability {
pub reached: Vec<Reached>,
at: BTreeMap<Node, usize>,
}
impl Reachability {
#[must_use]
pub fn get(&self, node: Node) -> Option<&Reached> {
self.at.get(&node).map(|at| &self.reached[*at])
}
#[must_use]
pub fn contains(&self, node: Node) -> bool {
self.at.contains_key(&node)
}
pub fn items(&self) -> impl Iterator<Item = ItemId> + '_ {
self.reached
.iter()
.filter_map(|reached| match reached.node {
Node::Item(id) => Some(id),
Node::Impl(_) => None,
})
}
pub fn impls(&self) -> impl Iterator<Item = ImplId> + '_ {
self.reached
.iter()
.filter_map(|reached| match reached.node {
Node::Impl(id) => Some(id),
Node::Item(_) => None,
})
}
}
#[derive(Debug)]
#[non_exhaustive]
pub enum ReachError {
UnknownItem(ItemId),
UnknownImpl(ImplId),
Source(LoadError),
Budget(LoadError),
}
impl From<LoadError> for ReachError {
fn from(error: LoadError) -> Self {
if matches!(error.kind, LoadErrorKind::Budget { .. }) {
Self::Budget(error)
} else {
Self::Source(error)
}
}
}
impl fmt::Display for ReachError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::UnknownItem(id) => {
write!(f, "item {} is past the items of the workspace", id.index())
}
Self::UnknownImpl(id) => {
write!(
f,
"impl block {} is past the impl blocks of the workspace",
id.index()
)
}
Self::Source(error) => write!(f, "{error}"),
Self::Budget(error) => write!(f, "the walk is over budget: {error}"),
}
}
}
impl Error for ReachError {
fn source(&self) -> Option<&(dyn Error + 'static)> {
match self {
Self::Source(error) | Self::Budget(error) => Some(error),
Self::UnknownItem(_) | Self::UnknownImpl(_) => None,
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum RunKind {
Path,
SelfPath,
Method,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Run {
start: usize,
first: usize,
len: usize,
leading_colon: bool,
kind: RunKind,
}
#[derive(Debug, Default)]
struct Lexed {
runs: Vec<Run>,
segs: Vec<(usize, usize)>,
tokens: usize,
formats: Option<Box<format::Formats>>,
format_tokens: usize,
format_bytes: usize,
}
impl Lexed {
fn start(
&mut self,
start: usize,
leading_colon: bool,
kind: RunKind,
seg: (usize, usize),
) -> usize {
self.runs.push(Run {
start,
first: self.segs.len(),
len: 1,
leading_colon,
kind,
});
self.segs.push(seg);
self.runs.len() - 1
}
fn extend(&mut self, at: usize, seg: (usize, usize)) {
self.runs[at].len += 1;
self.segs.push(seg);
}
fn drop_last(&mut self) {
if let Some(run) = self.runs.pop() {
self.segs.truncate(run.first);
}
}
}
struct LexFailure {
message: String,
line: usize,
column: usize,
}
const KEYWORDS: [&str; 43] = [
"abstract", "as", "become", "box", "break", "const", "continue", "do", "else", "enum",
"extern", "false", "final", "fn", "for", "if", "impl", "in", "let", "loop", "macro", "match",
"mod", "move", "mut", "override", "priv", "pub", "ref", "return", "static", "struct", "trait",
"true", "type", "typeof", "unsafe", "unsized", "use", "virtual", "where", "while", "yield",
];
const KEYWORDS_2018: [&str; 4] = ["async", "await", "dyn", "try"];
const KEYWORD_2024: &str = "gen";
fn blocked(word: &str, edition: u16) -> bool {
word == "Self"
|| KEYWORDS.contains(&word)
|| (edition >= 2018 && KEYWORDS_2018.contains(&word))
|| (edition >= 2024 && word == KEYWORD_2024)
}
const DECLARES: [&str; 8] = [
"fn", "struct", "enum", "union", "trait", "type", "mod", "static",
];
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Word {
Plain,
Declares,
MacroRules,
SelfValue,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Tok {
Ident { in_run: bool, word: Word },
Punct { ch: char, joint: bool },
Other,
}
#[derive(Debug, Default)]
struct Level {
last: [Option<Tok>; 3],
in_where: bool,
}
impl Level {
fn push(&mut self, tok: Tok) {
self.last = [self.last[1], self.last[2], Some(tok)];
}
fn colons(&self) -> bool {
matches!(
(self.last[1], self.last[2]),
(
Some(Tok::Punct {
ch: ':',
joint: true
}),
Some(Tok::Punct { ch: ':', .. })
)
)
}
fn single_dot(&self) -> bool {
matches!(
self.last[2],
Some(Tok::Punct {
ch: '.',
joint: false
})
) && !matches!(
self.last[1],
Some(Tok::Punct {
ch: '.',
joint: true
})
)
}
fn declaring(&self) -> bool {
matches!(
(self.last[1], self.last[2]),
(
_,
Some(Tok::Ident {
word: Word::Declares,
..
})
) | (
Some(Tok::Ident {
word: Word::MacroRules,
..
}),
Some(Tok::Punct { ch: '!', .. })
)
)
}
fn after_self_dot(&self) -> bool {
self.single_dot()
&& matches!(
self.last[1],
Some(Tok::Ident {
word: Word::SelfValue,
..
})
)
}
fn word(&self, word: &str) -> Word {
if matches!(self.last[2], Some(Tok::Punct { ch: '\'', .. })) {
Word::Plain
} else if DECLARES.contains(&word) {
Word::Declares
} else if word == "macro_rules" {
Word::MacroRules
} else if word == "self" {
Word::SelfValue
} else {
Word::Plain
}
}
}
enum Place {
Extend,
Start(bool, RunKind),
Skip,
}
#[derive(Debug, Clone, Copy)]
struct Open {
at: usize,
supers: bool,
}
fn place(level: &Level, word: &str, raw: bool, supers: bool, edition: u16) -> Place {
let blocked = |word: &str| !raw && blocked(word, edition);
let path_word = !raw && matches!(word, "crate" | "self" | "super");
if level.colons() {
return match level.last[0] {
Some(Tok::Ident { in_run: true, .. }) => {
if blocked(word) || (path_word && !(word == "super" && supers)) {
Place::Skip
} else {
Place::Extend
}
}
Some(Tok::Ident { in_run: false, .. } | Tok::Punct { ch: '>', .. }) => Place::Skip,
_ if blocked(word) || path_word => Place::Skip,
_ => Place::Start(true, RunKind::Path),
};
}
let self_type = !raw && word == "Self";
if (blocked(word) && !self_type) || level.single_dot() || level.declaring() {
return Place::Skip;
}
match level.last[2] {
Some(Tok::Punct { ch: '\'', .. }) => Place::Skip,
Some(Tok::Punct { ch: '$', .. }) if word != "crate" => Place::Skip,
_ if self_type => Place::Start(false, RunKind::SelfPath),
_ => Place::Start(false, RunKind::Path),
}
}
fn scan(stream: TokenStream, text: &str, base: usize, edition: u16) -> Lexed {
let mut lexed = Lexed::default();
let mut stack: Vec<(proc_macro2::token_stream::IntoIter, Level)> =
vec![(stream.into_iter(), Level::default())];
let mut open: Option<Open> = None;
let mut colon: Option<(usize, bool)> = None;
let mut method: Option<(usize, (usize, usize))> = None;
while let Some((tokens, level)) = stack.last_mut() {
let tree = tokens.next();
if let Some((start, seg)) = method.take() {
let called = match &tree {
Some(TokenTree::Group(group)) => group.delimiter() == Delimiter::Parenthesis,
Some(TokenTree::Punct(punct)) => {
punct.as_char() == ':' && punct.spacing() == Spacing::Joint
}
_ => false,
};
if called {
lexed.start(start, false, RunKind::Method, seg);
}
}
let next_colon = matches!(&tree, Some(TokenTree::Punct(punct)) if punct.as_char() == ':');
if let Some((at, joint)) = colon.take()
&& !(joint && next_colon)
&& lexed.runs.len() == at + 1
{
lexed.drop_last();
open = None;
}
let Some(tree) = tree else {
stack.pop();
open = None;
if let Some((_, outer)) = stack.last_mut() {
outer.push(Tok::Other);
}
continue;
};
lexed.tokens += 1;
match tree {
TokenTree::Group(group) => {
open = None;
if group.delimiter() == Delimiter::Brace {
level.in_where = false;
}
stack.push((group.stream().into_iter(), Level::default()));
}
TokenTree::Ident(ident) => {
let range = ident.span().byte_range();
let span = (base + range.start, base + range.end);
if ident == text[span.0..span.1] {
open = scan_ident(&mut lexed, level, open, &ident, span, edition, &mut method);
} else {
open = None;
level.push(Tok::Ident {
in_run: false,
word: Word::Plain,
});
}
}
TokenTree::Punct(punct) => {
let ch = punct.as_char();
let joint = punct.spacing() == Spacing::Joint;
if ch == ':' {
let first = !matches!(
level.last[2],
Some(Tok::Punct {
ch: ':',
joint: true
})
);
if first
&& !level.in_where
&& let (Some(run), Some(Tok::Ident { in_run: true, .. })) =
(open, level.last[2])
&& lexed.runs[run.at].len == 1
{
colon = Some((run.at, joint));
}
} else {
open = None;
if ch == ';' {
level.in_where = false;
}
}
level.push(Tok::Punct { ch, joint });
}
TokenTree::Literal(_) => {
open = None;
level.push(Tok::Other);
}
}
}
lexed
}
fn scan_ident(
lexed: &mut Lexed,
level: &mut Level,
open: Option<Open>,
ident: &proc_macro2::Ident,
span: (usize, usize),
edition: u16,
method: &mut Option<(usize, (usize, usize))>,
) -> Option<Open> {
let text = ident.to_string();
let (word, raw) = match text.strip_prefix("r#") {
Some(word) => (word, true),
None => (text.as_str(), false),
};
let kind = if raw { Word::Plain } else { level.word(word) };
let (start, end) = span;
let seg = (end - word.len(), end);
if !raw && word == "where" {
level.in_where = true;
}
if level.after_self_dot() {
*method = Some((start, seg));
}
let path_word = !raw && matches!(word, "self" | "super");
let supers = open.is_some_and(|run| run.supers);
let (in_run, open) = match place(level, word, raw, supers, edition) {
Place::Extend => {
let open = open.map(|run| {
lexed.extend(run.at, seg);
Open {
at: run.at,
supers: run.supers && path_word,
}
});
(true, open)
}
Place::Start(leading_colon, kind) => {
let at = lexed.start(start, leading_colon, kind, seg);
(
true,
Some(Open {
at,
supers: path_word,
}),
)
}
Place::Skip => (false, None),
};
level.push(Tok::Ident { in_run, word: kind });
open
}
fn lex_text(text: &str, edition: u16) -> Result<Lexed, LexFailure> {
let mut base = 0;
let mut body = text;
if let Some(rest) = body.strip_prefix('\u{feff}') {
base += '\u{feff}'.len_utf8();
body = rest;
}
if let Some(after) = body.strip_prefix("#!")
&& !after.trim_start().starts_with('[')
{
let cut = body.find('\n').unwrap_or(body.len());
base += cut;
body = &body[cut..];
}
let stream = TokenStream::from_str(body).map_err(|error| {
let start = error.span().start();
LexFailure {
message: error.to_string(),
line: start.line + text[..base].matches('\n').count(),
column: start.column + 1,
}
})?;
let mut lexed = scan(stream.clone(), text, base, edition);
(lexed.formats, lexed.format_tokens, lexed.format_bytes) = format::scan(stream, text, base);
lexed.runs.shrink_to_fit();
lexed.segs.shrink_to_fit();
Ok(lexed)
}
fn lex(file: &RelPath, text: &str, edition: u16) -> Result<Lexed, ReachError> {
thread::scope(|scope| {
let worker = thread::Builder::new()
.name(file.to_string())
.stack_size(PARSE_STACK_BYTES)
.spawn_scoped(scope, move || lex_text(text, edition))
.map_err(|source| {
ReachError::Source(LoadError::new(file, None, LoadErrorKind::Spawn(source)))
})?;
match worker.join() {
Ok(Ok(lexed)) => Ok(lexed),
Ok(Err(failure)) => Err(ReachError::Source(LoadError::new(
file,
Some(failure.line),
LoadErrorKind::Syntax {
message: failure.message,
column: failure.column,
},
))),
Err(payload) => panic::resume_unwind(payload),
}
})
}
#[derive(Debug, Default)]
struct FileRuns {
runs: Vec<Run>,
segs: Vec<(usize, usize)>,
by_unit: BTreeMap<(usize, usize), Vec<usize>>,
formats: Option<Box<format::Formats>>,
calls_by_unit: BTreeMap<(usize, usize), Vec<usize>>,
}
fn place_runs(runs: &[Run], units: Vec<(usize, usize)>) -> BTreeMap<(usize, usize), Vec<usize>> {
place_starts(
runs.iter().enumerate().map(|(at, run)| (at, run.start)),
units,
Work::ReachUnits,
)
}
fn place_starts(
starts: impl Iterator<Item = (usize, usize)>,
mut units: Vec<(usize, usize)>,
kind: Work,
) -> BTreeMap<(usize, usize), Vec<usize>> {
units.sort_by(|a, b| a.0.cmp(&b.0).then(b.1.cmp(&a.1)));
units.dedup();
let mut by_unit: BTreeMap<(usize, usize), Vec<usize>> = BTreeMap::new();
let mut open: Vec<(usize, usize)> = Vec::new();
let mut next = 0;
for (position, start) in starts {
while let Some(&unit) = units.get(next).filter(|unit| unit.0 <= start) {
work::add(kind, 1);
while open.last().is_some_and(|top| top.1 <= unit.0) {
work::add(kind, 1);
open.pop();
}
open.push(unit);
next += 1;
}
while open.last().is_some_and(|top| top.1 <= start) {
work::add(kind, 1);
open.pop();
}
if let Some(unit) = open.last() {
work::add(kind, 1);
by_unit.entry(*unit).or_default().push(position);
}
}
for positions in by_unit.values_mut() {
positions.shrink_to_fit();
}
by_unit
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
enum Owner {
Block(ImplId),
Trait(ItemId),
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
enum Ctx {
Module(usize, bool),
Value(usize, bool),
Owner(Owner),
}
#[derive(Debug, Clone, Copy, Default)]
pub(crate) struct Home {
module: Option<usize>,
owner: Option<Owner>,
}
impl Home {
pub(crate) const fn module(self) -> Option<usize> {
self.module
}
}
pub(crate) fn fill_homes(index: &Index, homes: &mut [Home], lexical: bool) {
for (module, entry) in index.modules.iter().enumerate() {
for id in &entry.defs {
work::add(Work::ReachSteps, 1);
homes[id.0].module = Some(module);
}
}
for (module, id) in &index.root_items {
work::add(Work::ReachSteps, 1);
homes[id.0].module = Some(*module);
}
if lexical {
for (id, module) in &index.macro_modules {
work::add(Work::ReachSteps, 1);
homes[id.0].module = Some(*module);
}
}
for block in &index.impl_blocks {
work::add(Work::ReachSteps, 1);
for member in &block.members {
work::add(Work::ReachSteps, 1);
homes[member.0] = Home {
module: Some(block.module_index),
owner: Some(Owner::Block(block.id)),
};
}
}
for (owner, members) in &index.assoc {
if index.items[owner.0].kind != SymbolKind::Trait {
continue;
}
homes[owner.0].owner = Some(Owner::Trait(*owner));
for id in members.values().flatten() {
work::add(Work::ReachSteps, 1);
homes[id.0] = Home {
module: homes[owner.0].module,
owner: Some(Owner::Trait(*owner)),
};
}
}
}
#[derive(Debug, Default)]
struct BlockNames<'a> {
members: BTreeMap<&'a str, Vec<ItemId>>,
traits: Vec<ItemId>,
}
struct Unit<'u> {
file: &'u RelPath,
line: usize,
span: (usize, usize),
before: usize,
module: usize,
test: bool,
owner: Option<Owner>,
}
type Queued = (Node, Edge, Option<Node>);
fn lists_bytes<K>(map: &BTreeMap<K, Vec<ImplId>>) -> usize {
btree_map::<K, Vec<ImplId>>()
+ map
.values()
.map(|list| btree_entry::<K, Vec<ImplId>>() + list.capacity() * size_of::<ImplId>())
.sum::<usize>()
}
fn members_named<'a>(index: &'a Index, owner: ItemId, name: &str) -> &'a [ItemId] {
work::add(Work::ReachSteps, 1);
index
.assoc
.get(&owner)
.and_then(|members| members.get(name))
.map_or(&[], Vec::as_slice)
}
fn trait_segments(written: &str) -> Option<(bool, Vec<String>)> {
if written.starts_with('!') {
return None;
}
let path = &written[..written.find(['<', '(']).unwrap_or(written.len())];
let (leading_colon, path) = match path.strip_prefix("::") {
Some(rest) => (true, rest),
None => (false, path),
};
let segs: Vec<String> = path
.split("::")
.map(|seg| seg.strip_prefix("r#").unwrap_or(seg).to_owned())
.collect();
segs.iter()
.all(|seg| !seg.is_empty() && seg.chars().all(|c| c == '_' || c.is_alphanumeric()))
.then_some((leading_colon, segs))
}
struct Walk<'a> {
index: &'a Index,
files: &'a BTreeMap<RelPath, SourceFile>,
meter: &'a Meter,
homes: Vec<Home>,
blocks_of_type: BTreeMap<ItemId, Vec<ImplId>>,
blocks_of_module: BTreeMap<usize, Vec<ImplId>>,
block_modules_of: BTreeMap<ItemId, Vec<usize>>,
roots: BTreeSet<ItemId>,
files_runs: BTreeMap<(RelPath, u16), FileRuns>,
seen: BTreeMap<Ctx, BTreeSet<Box<str>>>,
blocks: BTreeMap<ImplId, BlockNames<'a>>,
format_identity: Option<format::Resolver>,
}
impl<'a> Walk<'a> {
fn new(
index: &'a Index,
files: &'a BTreeMap<RelPath, SourceFile>,
meter: &'a Meter,
(file, line): (&RelPath, usize),
) -> Result<Self, ReachError> {
let mut homes = vec![Home::default(); index.items.len()];
fill_homes(index, &mut homes, false);
let mut blocks_of_type: BTreeMap<ItemId, Vec<ImplId>> = BTreeMap::new();
let mut blocks_of_module: BTreeMap<usize, Vec<ImplId>> = BTreeMap::new();
for block in &index.impl_blocks {
blocks_of_module
.entry(block.module_index)
.or_default()
.push(block.id);
for ty in &block.self_items {
work::add(Work::ReachSteps, 1);
blocks_of_type.entry(*ty).or_default().push(block.id);
}
}
let mut block_modules_of: BTreeMap<ItemId, Vec<usize>> = BTreeMap::new();
if !index.block_modules.is_empty() {
let mut in_module: BTreeMap<usize, Vec<ItemId>> = BTreeMap::new();
for item in &index.items {
if let Some(module) = homes[item.id.0].module {
in_module.entry(module).or_default().push(item.id);
}
}
for site in &index.block_modules {
work::add(
Work::ReachSteps,
1 + in_module.get(&site.parent).map_or(0, Vec::len),
);
let owner = in_module
.get(&site.parent)
.into_iter()
.flatten()
.map(|id| &index.items[id.0])
.filter(|item| {
item.file == site.file
&& item.span.start_byte <= site.span.0
&& site.span.1 <= item.span.end_byte
})
.min_by_key(|item| item.span.end_byte - item.span.start_byte);
if let Some(owner) = owner {
block_modules_of
.entry(owner.id)
.or_default()
.push(site.module);
}
}
}
let roots: BTreeSet<ItemId> = index.root_items.values().copied().collect();
let held = homes.capacity() * size_of::<Home>()
+ lists_bytes(&blocks_of_type)
+ lists_bytes(&blocks_of_module)
+ btree_map::<ItemId, Vec<usize>>()
+ block_modules_of
.values()
.map(|list| {
btree_entry::<ItemId, Vec<usize>>() + list.capacity() * size_of::<usize>()
})
.sum::<usize>()
+ btree_map::<ItemId, ()>()
+ roots.len() * btree_entry::<ItemId, ()>()
+ btree_map::<(RelPath, u16), FileRuns>()
+ btree_map::<Ctx, BTreeSet<Box<str>>>()
+ btree_map::<ImplId, BlockNames<'_>>();
meter
.items(held, file, Some(line))
.map_err(ReachError::Budget)?;
Ok(Self {
index,
files,
meter,
homes,
blocks_of_type,
blocks_of_module,
block_modules_of,
roots,
files_runs: BTreeMap::new(),
seen: BTreeMap::new(),
blocks: BTreeMap::new(),
format_identity: None,
})
}
fn load(&mut self, file: &RelPath, module: usize) -> Result<(RelPath, u16), ReachError> {
let key = (file.clone(), self.index.edition(module));
if self.files_runs.contains_key(&key) {
return Ok(key);
}
let text = self
.files
.get(file)
.map_or("", |source| source.text.as_str());
let lexed = lex(file, text, key.1)?;
work::add(Work::ReachTokens, lexed.tokens);
work::add(Work::ReachFormatTokens, lexed.format_tokens);
work::add(Work::ReachFormatBytes, lexed.format_bytes);
let mut units: Vec<(usize, usize)> = self
.index
.by_file
.get(file)
.into_iter()
.flatten()
.filter(|id| !self.roots.contains(id))
.map(|id| {
let span = &self.index.items[id.0].span;
(span.start_byte, span.end_byte)
})
.collect();
let first = self
.index
.impl_blocks
.partition_point(|block| block.file < *file);
units.extend(
self.index.impl_blocks[first..]
.iter()
.take_while(|block| block.file == *file)
.map(|block| (block.span.start_byte, block.span.end_byte)),
);
let calls_by_unit = lexed
.formats
.as_ref()
.map_or_else(BTreeMap::new, |formats| {
place_starts(
formats
.calls
.iter()
.enumerate()
.map(|(at, call)| (at, call.start)),
units.clone(),
Work::ReachFormatTokens,
)
});
let by_unit = place_runs(&lexed.runs, units);
let mut held = btree_entry::<(RelPath, u16), FileRuns>()
+ lexed.runs.capacity() * size_of::<Run>()
+ lexed.segs.capacity() * size_of::<(usize, usize)>();
if !by_unit.is_empty() {
held += btree_map::<(usize, usize), Vec<usize>>();
}
for positions in by_unit.values() {
held += btree_entry::<(usize, usize), Vec<usize>>()
+ positions.capacity() * size_of::<usize>();
}
if let Some(formats) = &lexed.formats {
held += formats.retained_bytes();
}
if !calls_by_unit.is_empty() {
held += btree_map::<(usize, usize), Vec<usize>>();
for positions in calls_by_unit.values() {
held += btree_entry::<(usize, usize), Vec<usize>>()
+ positions.capacity() * size_of::<usize>();
}
}
if lexed.formats.is_some() && self.format_identity.is_none() {
let identity = format::Resolver::new(self.index, self.files, self.meter, file)?;
self.format_identity = Some(identity);
}
self.meter
.items(held, file, None)
.map_err(ReachError::Budget)?;
self.files_runs.insert(
key.clone(),
FileRuns {
runs: lexed.runs,
segs: lexed.segs,
by_unit,
formats: lexed.formats,
calls_by_unit,
},
);
Ok(key)
}
fn references(&mut self, unit: &Unit<'_>) -> Result<Vec<ItemId>, ReachError> {
let key = self.load(unit.file, unit.module)?;
let index = self.index;
let text = self
.files
.get(unit.file)
.map_or("", |source| source.text.as_str());
let runs = &self.files_runs[&key];
let mut out = Vec::new();
let suppressed = format_references(
index,
self.meter,
self.format_identity.as_ref(),
&mut self.seen,
unit,
runs,
&mut out,
)?;
for position in runs.by_unit.get(&unit.span).into_iter().flatten() {
let run = runs.runs[*position];
if run.start >= unit.before {
break;
}
if suppressed.binary_search(&run.start).is_ok() {
continue;
}
work::add(Work::ReachSteps, 1);
let segs = &runs.segs[run.first..run.first + run.len];
let word = |at: usize| &text[segs[at].0..segs[at].1];
let (ctx, key) = match (run.kind, unit.owner) {
(RunKind::Path, _) => {
let mut key = String::from(if run.leading_colon { "::" } else { "" });
for at in 0..segs.len() {
if at > 0 {
key.push_str("::");
}
key.push_str(word(at));
}
(Ctx::Module(unit.module, unit.test), key)
}
(RunKind::SelfPath, Some(owner)) if run.len > 1 => {
(Ctx::Owner(owner), format!("Self::{}", word(1)))
}
(RunKind::Method, Some(owner)) => (Ctx::Owner(owner), format!(".{}", word(0))),
(RunKind::SelfPath | RunKind::Method, _) => continue,
};
let mut held = btree_entry::<Box<str>, ()>() + key.len();
if !self.seen.contains_key(&ctx) {
held += btree_entry::<Ctx, BTreeSet<Box<str>>>() + btree_map::<Box<str>, ()>();
}
let seen = self.seen.entry(ctx).or_default();
if seen.contains(key.as_str()) {
continue;
}
self.meter
.items(held, unit.file, Some(unit.line))
.map_err(ReachError::Budget)?;
seen.insert(key.into_boxed_str());
work::add(Work::ReachPaths, 1);
match (run.kind, ctx) {
(RunKind::Path, _) => {
let words: Vec<String> =
(0..segs.len()).map(|at| word(at).to_owned()).collect();
out.extend(index.reach_run(
unit.module,
&words,
run.leading_colon,
unit.test,
Steps::QueryItems {
meter: self.meter,
file: unit.file,
line: Some(unit.line),
},
)?);
}
(kind, Ctx::Owner(owner)) => {
let (name, variant) = match kind {
RunKind::SelfPath => (word(1), true),
_ => (word(0), false),
};
let names = owner_names(
index,
self.meter,
&mut self.blocks,
owner,
(name, variant),
unit,
)?;
out.extend(names);
}
(_, Ctx::Module(..) | Ctx::Value(..)) => {}
}
}
Ok(out)
}
fn next(
&mut self,
node: Node,
edge: Edge,
first: bool,
opened: &mut BTreeSet<ItemId>,
) -> Result<Vec<(Node, Edge)>, ReachError> {
let index = self.index;
let mut out = Vec::new();
match node {
Node::Item(id) => {
let item = &index.items[id.0];
if self.roots.contains(&id) {
return Ok(out);
}
match item.kind {
SymbolKind::Mod => {
if matches!(edge, Edge::Root | Edge::Contains)
&& opened.insert(id)
&& let Some(module) = index.module_of.get(&id)
{
for child in &index.modules[*module].defs {
work::add(Work::ReachSteps, 1);
out.push((Node::Item(*child), Edge::Contains));
}
for block in self.blocks_of_module.get(module).into_iter().flatten() {
work::add(Work::ReachSteps, 1);
out.push((Node::Impl(*block), Edge::Contains));
}
}
}
SymbolKind::Struct
| SymbolKind::Enum
| SymbolKind::Union
| SymbolKind::Trait
if first =>
{
for member in index.assoc.get(&id).into_iter().flat_map(|m| m.values()) {
for child in member {
work::add(Work::ReachSteps, 1);
out.push((Node::Item(*child), Edge::Contains));
}
}
for block in self.blocks_of_type.get(&id).into_iter().flatten() {
work::add(Work::ReachSteps, 1);
out.push((Node::Impl(*block), Edge::ImplOf));
}
}
_ => {}
}
if first {
for &module in self.block_modules_of.get(&id).into_iter().flatten() {
for child in &index.modules[module].defs {
work::add(Work::ReachSteps, 1);
out.push((Node::Item(*child), Edge::Contains));
}
for block in self.blocks_of_module.get(&module).into_iter().flatten() {
work::add(Work::ReachSteps, 1);
out.push((Node::Impl(*block), Edge::Contains));
}
}
}
let home = self.homes[id.0];
if first && let Some(module) = home.module {
let before = match (item.kind, &item.body) {
(SymbolKind::Mod, Some(body)) => body.start_byte,
_ => usize::MAX,
};
let unit = Unit {
file: &item.file,
line: item.name_line,
span: (item.span.start_byte, item.span.end_byte),
before,
module,
test: item.test != TestRole::None,
owner: home.owner,
};
for found in self.references(&unit)? {
work::add(Work::ReachSteps, 1);
out.push((Node::Item(found), Edge::References));
}
}
}
Node::Impl(id) => {
if first {
let block = &index.impl_blocks[id.0];
for member in &block.members {
work::add(Work::ReachSteps, 1);
out.push((Node::Item(*member), Edge::ImplOf));
}
let unit = Unit {
file: &block.file,
line: block.line,
span: (block.span.start_byte, block.span.end_byte),
before: usize::MAX,
module: block.module_index,
test: block.test != TestRole::None,
owner: Some(Owner::Block(id)),
};
for found in self.references(&unit)? {
work::add(Work::ReachSteps, 1);
out.push((Node::Item(found), Edge::References));
}
}
}
}
Ok(out)
}
}
fn format_references(
index: &Index,
meter: &Meter,
identity: Option<&format::Resolver>,
seen_paths: &mut BTreeMap<Ctx, BTreeSet<Box<str>>>,
unit: &Unit<'_>,
runs: &FileRuns,
out: &mut Vec<ItemId>,
) -> Result<Vec<usize>, ReachError> {
let mut suppressed = Vec::new();
if let (Some(formats), Some(identity)) = (&runs.formats, identity) {
for &position in runs.calls_by_unit.get(&unit.span).into_iter().flatten() {
let call = &formats.calls[position];
if call.start >= unit.before {
break;
}
if !identity.standard(
formats,
call,
index,
unit,
Steps::QueryItems {
meter,
file: unit.file,
line: Some(unit.line),
},
)? {
continue;
}
let Some(arguments) = &call.arguments else {
continue;
};
let arguments = arguments
.as_ref()
.map_err(|refusal| ReachError::Source(refusal.error(unit.file)))?;
suppressed.extend_from_slice(&arguments.bindings);
for name in &arguments.captures {
let ctx = Ctx::Value(unit.module, unit.test);
let mut held = btree_entry::<Box<str>, ()>() + name.len();
if !seen_paths.contains_key(&ctx) {
held += btree_entry::<Ctx, BTreeSet<Box<str>>>() + btree_map::<Box<str>, ()>();
}
let seen = seen_paths.entry(ctx).or_default();
if seen.contains(name.as_ref()) {
continue;
}
meter
.items(held, unit.file, Some(unit.line))
.map_err(ReachError::Budget)?;
seen.insert(name.clone());
work::add(Work::ReachPaths, 1);
out.extend(index.reach_value(
unit.module,
name,
unit.test,
Steps::QueryItems {
meter,
file: unit.file,
line: Some(unit.line),
},
)?);
}
}
}
suppressed.sort_unstable();
Ok(suppressed)
}
fn owner_names<'a>(
index: &'a Index,
meter: &Meter,
blocks: &mut BTreeMap<ImplId, BlockNames<'a>>,
owner: Owner,
(name, variant): (&str, bool),
unit: &Unit<'_>,
) -> Result<Vec<ItemId>, ReachError> {
let mut out: Vec<ItemId> = Vec::new();
match owner {
Owner::Trait(id) => out.extend_from_slice(members_named(index, id, name)),
Owner::Block(id) => {
let block = &index.impl_blocks[id.0];
let names = block_names(index, meter, blocks, id, unit)?;
for ty in &block.self_items {
out.extend_from_slice(members_named(index, *ty, name));
}
if let Some(members) = names.members.get(name) {
out.extend_from_slice(members);
}
for found in &names.traits {
out.extend_from_slice(members_named(index, *found, name));
}
if variant && out.is_empty() {
out.extend(
block
.self_items
.iter()
.filter(|ty| index.items[ty.0].kind == SymbolKind::Enum),
);
}
}
}
Ok(out)
}
fn block_names<'a, 'b>(
index: &'a Index,
meter: &Meter,
blocks: &'b mut BTreeMap<ImplId, BlockNames<'a>>,
id: ImplId,
unit: &Unit<'_>,
) -> Result<&'b BlockNames<'a>, ReachError> {
let slot = match blocks.entry(id) {
Entry::Occupied(found) => return Ok(found.into_mut()),
Entry::Vacant(slot) => slot,
};
let block = &index.impl_blocks[id.0];
let mut names = BlockNames::default();
if block.self_items.is_empty() {
for member in &block.members {
work::add(Work::ReachSteps, 1);
names
.members
.entry(index.items[member.0].name.as_str())
.or_default()
.push(*member);
}
}
if let Some((leading_colon, segs)) = block
.trait_path
.as_ref()
.map(SharedStr::as_str)
.and_then(trait_segments)
{
work::add(Work::ReachPaths, 1);
names.traits = index
.reach_run(
block.module_index,
&segs,
leading_colon,
block.test != TestRole::None,
Steps::QueryItems {
meter,
file: unit.file,
line: Some(unit.line),
},
)?
.into_iter()
.filter(|found| index.items[found.0].kind == SymbolKind::Trait)
.collect();
}
let mut held =
btree_entry::<ImplId, BlockNames<'_>>() + names.traits.capacity() * size_of::<ItemId>();
if !names.members.is_empty() {
held += btree_map::<&str, Vec<ItemId>>();
}
for members in names.members.values() {
held += btree_entry::<&str, Vec<ItemId>>() + members.capacity() * size_of::<ItemId>();
}
meter
.items(held, unit.file, Some(unit.line))
.map_err(ReachError::Budget)?;
Ok(slot.insert(names))
}
fn place_of(index: &Index, node: Node) -> (&RelPath, usize) {
match node {
Node::Item(id) => {
let item = &index.items[id.0];
(&item.file, item.name_line)
}
Node::Impl(id) => {
let block = &index.impl_blocks[id.0];
(&block.file, block.line)
}
}
}
pub(crate) fn reachable(
index: &Index,
files: &BTreeMap<RelPath, SourceFile>,
(options, held): (&LoadOptions, usize),
roots: &[Node],
) -> Result<Reachability, ReachError> {
let mut sorted: Vec<Node> = Vec::with_capacity(roots.len());
for root in roots {
work::add(Work::ReachSteps, 1);
match *root {
Node::Item(id) if id.0 >= index.items.len() => return Err(ReachError::UnknownItem(id)),
Node::Impl(id) if id.0 >= index.impl_blocks.len() => {
return Err(ReachError::UnknownImpl(id));
}
node => sorted.push(node),
}
}
sorted.sort_unstable();
sorted.dedup();
let Some(first) = sorted.first() else {
return Ok(Reachability {
reached: Vec::new(),
at: BTreeMap::new(),
});
};
let (file, line) = place_of(index, *first);
let meter = Meter::query(options);
meter
.items(
held + vec_first::<Reached>()
+ btree_map::<Node, usize>()
+ btree_map::<ItemId, ()>()
+ vec_first::<Queued>(),
file,
Some(line),
)
.map_err(ReachError::Budget)?;
let mut walk = Walk::new(index, files, &meter, (file, line))?;
let mut queue: VecDeque<Queued> = sorted
.into_iter()
.map(|node| (node, Edge::Root, None))
.collect();
let mut peak = queue.len();
meter
.items(peak * vec_slot::<Queued>(), file, Some(line))
.map_err(ReachError::Budget)?;
let mut reached: Vec<Reached> = Vec::new();
let mut at: BTreeMap<Node, usize> = BTreeMap::new();
let mut opened: BTreeSet<ItemId> = BTreeSet::new();
while let Some((node, edge, from)) = queue.pop_front() {
work::add(Work::ReachSteps, 1);
let first = !at.contains_key(&node);
let (file, line) = place_of(index, node);
if first {
meter
.items(
vec_slot::<Reached>() + btree_entry::<Node, usize>(),
file,
Some(line),
)
.map_err(ReachError::Budget)?;
at.insert(node, reached.len());
reached.push(Reached { node, edge, from });
}
let was_opened = opened.len();
for (next, by) in walk.next(node, edge, first, &mut opened)? {
let opens = matches!(next, Node::Item(id) if index.items[id.0].kind == SymbolKind::Mod && by == Edge::Contains && !opened.contains(&id));
if opens || !at.contains_key(&next) {
queue.push_back((next, by, Some(node)));
}
}
let grown = queue.len().saturating_sub(peak) * vec_slot::<Queued>()
+ (opened.len() - was_opened) * btree_entry::<ItemId, ()>();
peak = peak.max(queue.len());
if grown > 0 {
meter
.items(grown, file, Some(line))
.map_err(ReachError::Budget)?;
}
}
Ok(Reachability { reached, at })
}
#[cfg(test)]
mod tests {
use std::fmt::Write as _;
use std::mem::size_of;
use super::{DECLARES, Run, RunKind, Walk, lex_text, place_runs};
use crate::budget::Budget;
use crate::error::LoadErrorKind;
use crate::item::Namespace;
use crate::meter::{Meter, Steps};
use crate::reach::{Node, ReachError};
use crate::work::{self, Work};
use crate::{LoadOptions, MemoryTree, Workspace};
fn runs_in(edition: u16, text: &str) -> Vec<(String, usize)> {
let lexed = lex_text(text, edition).unwrap_or_else(|failure| panic!("{}", failure.message));
lexed
.runs
.iter()
.map(|run| {
let words: Vec<&str> = lexed.segs[run.first..run.first + run.len]
.iter()
.map(|(start, end)| &text[*start..*end])
.collect();
let shown = match run.kind {
RunKind::Method => format!(".{}", words.join("::")),
RunKind::Path | RunKind::SelfPath => format!(
"{}{}",
if run.leading_colon { "::" } else { "" },
words.join("::")
),
};
(shown, run.start)
})
.collect()
}
fn runs(text: &str) -> Vec<(String, usize)> {
runs_in(2021, text)
}
fn texts_in(edition: u16, text: &str) -> Vec<String> {
runs_in(edition, text)
.into_iter()
.map(|(text, _)| text)
.collect()
}
fn texts(text: &str) -> Vec<String> {
texts_in(2021, text)
}
#[test]
fn a_run_is_an_identifier_path_that_no_dot_precedes_with_its_first_byte() {
assert_eq!(runs("a::b::c"), [("a::b::c".to_owned(), 0)]);
assert_eq!(texts("x.helper(); x.0.y"), ["x", "x"]);
assert_eq!(texts("0..LIMIT; ..=END"), ["LIMIT", "END"]);
assert_eq!(texts("::std::fmt::Debug"), ["::std::fmt::Debug"]);
assert_eq!(texts("Vec::<u8>::new()"), ["Vec", "u8"]);
assert_eq!(texts("<T as Tr>::f"), ["T", "Tr"]);
assert_eq!(texts("r#match::x"), ["match::x"]);
assert_eq!(texts("a :: b"), ["a::b"]);
assert_eq!(texts("f(a::b, c)"), ["f", "a::b", "c"]);
assert_eq!(runs("r#gen::x"), [("gen::x".to_owned(), 0)]);
}
#[test]
fn path_keywords_start_a_run_and_other_keywords_are_no_segment() {
assert_eq!(
texts("crate::a; self::b; super::super::c; self::super::d"),
["crate::a", "self::b", "super::super::c", "self::super::d"]
);
assert_eq!(texts("a::crate; a::self::b"), ["a", "a"]);
assert_eq!(texts("r#fn::r#match"), ["fn::match"]);
assert_eq!(texts("pub use a as b;"), ["a", "b"]);
assert_eq!(
texts("Self::new(); impl Tr for S; a::Self::b; ::Self::c"),
["Self::new", "Tr", "S", "a"]
);
assert_eq!(texts("Self { a: 1 }; Self(2)"), ["Self", "Self"]);
}
#[test]
fn the_keywords_are_those_of_the_edition() {
let text = "async(); await(); dyn(); try(); gen(); r#gen(); r#try()";
assert_eq!(
texts_in(2015, text),
["async", "await", "dyn", "try", "gen", "gen", "try"]
);
for edition in [2018, 2021] {
assert_eq!(texts_in(edition, text), ["gen", "gen", "try"], "{edition}");
}
assert_eq!(texts_in(2024, text), ["gen", "try"]);
assert_eq!(texts_in(2015, "a::fn::b; a::dyn::b"), ["a", "a::dyn::b"]);
assert_eq!(texts_in(2024, "a::gen::b; a::r#gen::b"), ["a", "a::gen::b"]);
}
#[test]
fn a_lifetime_a_metavariable_a_declared_name_and_a_bound_name_are_no_run() {
assert_eq!(texts("&'a T; 'label: loop {}"), ["T"]);
assert_eq!(texts("&'static Foo"), ["Foo"]);
assert_eq!(texts("$x; $crate::helper()"), ["crate::helper"]);
assert_eq!(texts("fn helper(x: u8) -> Foo {}"), ["u8", "Foo"]);
assert_eq!(
texts(
"struct S { helper: u8 } enum E {} trait T {} type A = B; mod m {} const C: u8 = 1; static D: X = Y;"
),
["u8", "B", "u8", "X", "Y"]
);
assert_eq!(
texts("macro_rules! m { () => { g() } }"),
["macro_rules", "g"]
);
assert_eq!(texts("S { helper: 1, other }"), ["S", "other"]);
assert_eq!(texts("where T::Assoc: Bound"), ["T::Assoc", "Bound"]);
assert_eq!(texts("x: ::std::Y"), ["::std::Y"]);
assert_eq!(texts("x:&Y"), ["Y"]);
}
#[test]
fn const_declares_nothing_so_a_pointer_and_a_raw_borrow_name_their_path() {
assert!(!DECLARES.contains(&"const"));
assert_eq!(
texts("fn f(p: *const Helper, q: *mut Other) {}"),
["Helper", "Other"]
);
assert_eq!(
texts("&raw const VALUE; &raw mut OTHER"),
["raw", "VALUE", "raw", "OTHER"]
);
assert_eq!(
texts("const C: u8 = 1; pub const D: E = F;"),
["u8", "E", "F"]
);
assert_eq!(
texts("const fn helper() {} const unsafe fn other() {}"),
Vec::<String>::new()
);
assert_eq!(texts("const { g() }"), ["g"]);
assert_eq!(texts("fn f<const N: usize>() {}"), ["usize"]);
assert_eq!(texts("impl<const N: usize> S<N> {}"), ["usize", "S", "N"]);
}
#[test]
fn a_where_clause_keeps_the_type_its_bound_is_put_on() {
assert_eq!(
texts("fn f<T>() where Helper: Clone, T: Into<Other> {}"),
["T", "Helper", "Clone", "T", "Into", "Other"]
);
assert_eq!(
texts("fn f(helper: u8) where T: X { S { field: 1 } }"),
["u8", "T", "X", "S"]
);
assert_eq!(
texts("fn g() where Self: Sized; fn h(x: u8) {}"),
["Self", "Sized", "u8"]
);
assert_eq!(
texts(
"struct S<T> where T: X { field: u8 } struct P(u8) where Q: Y; static Z: u8 = 0;"
),
["T", "T", "X", "u8", "u8", "Q", "Y", "u8"]
);
assert_eq!(texts("fn f<T: Clone>() {}"), ["Clone"]);
}
#[test]
fn a_name_called_on_self_is_a_method_run_and_a_field_of_self_is_not() {
assert_eq!(
texts("self.helper(); self.field; self.turbo::<u8>(); other.method(); self.0.x()"),
[
"self", ".helper", "self", "self", ".turbo", "u8", "other", "self"
]
);
let text = "fn f(&self) { self.r#match() }";
assert_eq!(
runs(text),
[
("self".to_owned(), text.find("self)").expect("the receiver")),
("self".to_owned(), text.find("self.").expect("self")),
(
".match".to_owned(),
text.find("r#match").expect("the method")
),
]
);
assert_eq!(
texts("self::helper(); s.helper(); Self.x()"),
["self::helper", "s", "Self"]
);
}
#[test]
fn a_byte_order_mark_and_a_shebang_are_left_out_and_offsets_are_those_of_the_text() {
let text = "\u{feff}fn f() { g() }";
assert_eq!(runs(text), [("g".to_owned(), text.find('g').expect("g"))]);
let text = "#!/usr/bin/env run\nfn f() { g() }";
assert_eq!(runs(text), [("g".to_owned(), text.find("g(").expect("g"))]);
assert_eq!(texts("#![allow(unused)]\nfn f() {}"), ["allow", "unused"]);
let failure = lex_text("fn f() {\n\"", 2021).expect_err("an open string");
assert_eq!(failure.line, 2);
}
#[test]
fn a_doc_comment_is_no_run_whatever_character_ends_it() {
let text = "//! Crate §\n/// Calls abc\n/// See §1,\n/** Block ß */\n\
#[doc = \"x\"]\npub fn f() { a::b() }\nfn abc() {}\n";
let ws = load(text);
let site = |path: &str| {
Node::Item(
ws.resolve_in(path, Namespace::Value)
.unwrap_or_else(|e| panic!("{path}: {e}"))
.sites[0],
)
};
let reached = ws
.reachable(&[site("demo::f")])
.unwrap_or_else(|e| panic!("{e}"));
assert!(!reached.contains(site("demo::abc")));
assert_eq!(
runs(text),
[
("doc".to_owned(), text.find("doc").expect("the attribute")),
("a::b".to_owned(), text.find("a::b").expect("the call")),
]
);
}
fn run_at(start: usize) -> Run {
Run {
start,
first: 0,
len: 1,
leading_colon: false,
kind: RunKind::Path,
}
}
#[test]
fn each_run_goes_to_the_innermost_unit_that_holds_its_start() {
let units = vec![(120, 150), (10, 20), (0, 100), (30, 40), (0, 100)];
let runs: Vec<Run> = [5, 10, 25, 35, 99, 100, 130, 160]
.into_iter()
.map(run_at)
.collect();
let placed = place_runs(&runs, units);
let by: Vec<((usize, usize), Vec<usize>)> = placed.into_iter().collect();
assert_eq!(
by,
[
((0, 100), vec![0, 2, 4]),
((10, 20), vec![1]),
((30, 40), vec![3]),
((120, 150), vec![6]),
]
);
}
const MANIFEST: &str = "[package]\nname = \"demo\"\nversion = \"0.1.0\"\nedition = \"2021\"\n";
fn load_with(text: &str, options: &LoadOptions) -> Workspace {
let tree = MemoryTree::from([("Cargo.toml", MANIFEST), ("src/lib.rs", text)]);
Workspace::load_with(&tree, &["."], options).unwrap_or_else(|e| panic!("{e}"))
}
fn load(text: &str) -> Workspace {
load_with(text, &LoadOptions::default())
}
fn fan(items: usize, references: usize) -> Workspace {
let mut text = String::new();
for i in 0..items {
let calls = format!("h{i}(); ").repeat(references);
writeln!(text, "pub fn f{i}() {{ {calls}}}\nfn h{i}() {{}}").expect("write");
}
load(&text)
}
const KINDS: [Work; 6] = [
Work::ReachTokens,
Work::ReachUnits,
Work::ReachPaths,
Work::ReachSteps,
Work::SegmentReads,
Work::Lookups,
];
fn work_of(ws: &Workspace, roots: &[Node]) -> ([usize; 6], usize) {
let (reached, tally) = work::measure(usize::MAX, || ws.reachable(roots));
let reached = reached.unwrap_or_else(|e| panic!("{e}")).reached.len();
(KINDS.map(|kind| tally.get(kind)), reached)
}
fn fan_work(items: usize, references: usize) -> ([usize; 6], usize) {
let ws = fan(items, references);
let roots: Vec<Node> = (0..items)
.map(|i| {
let path = format!("demo::f{i}");
Node::Item(ws.resolve_in(&path, Namespace::Value).expect("f").sites[0])
})
.collect();
work_of(&ws, &roots)
}
#[test]
fn the_work_of_a_walk_is_counted_exactly() {
for (n, r) in [(1, 1), (3, 2), (5, 4)] {
let ([tokens, units, paths, steps, ..], reached) = fan_work(n, r);
assert_eq!(reached, 2 * n, "{n} {r}");
assert_eq!(tokens, n * (9 + 3 * r), "{n} {r}");
assert_eq!(units, n * r + 4 * n - 3, "{n} {r}");
assert_eq!(paths, n, "{n} {r}");
assert_eq!(steps, 6 * n + 1 + n * r, "{n} {r}");
}
}
#[test]
fn the_work_grows_with_the_items_and_the_references_and_not_their_product() {
let by_items: Vec<[usize; 6]> = [10, 20, 30].map(|n| fan_work(n, 3).0).to_vec();
let by_references: Vec<[usize; 6]> = [2, 4, 6].map(|r| fan_work(10, r).0).to_vec();
for sizes in [&by_items, &by_references] {
for (kind, name) in KINDS.iter().enumerate() {
let first = sizes[1][kind] - sizes[0][kind];
let second = sizes[2][kind] - sizes[1][kind];
assert_eq!(first, second, "{name:?}: {sizes:?}");
}
}
assert_eq!(by_references[0][2], by_references[2][2]);
}
fn kinds(types: usize, members: usize) -> String {
let mut text = String::from("pub trait Tr {\n");
for j in 0..members {
writeln!(text, " fn t{j}(&self) -> u8;").expect("write");
}
text.push_str("}\npub mod top {\n");
for i in 0..types {
writeln!(
text,
"pub mod m{i} {{\n\
pub struct T{i} {{ f: u8 }}\n\
pub enum E{i} {{ A, B }}\n\
pub type A{i} = T{i};\n\
const K{i}: u8 = 1;\n\
static S{i}: u8 = 2;\n\
pub fn helper{i}() -> E{i} {{ E{i}::A }}\n\
impl E{i} {{ pub fn is_a(&self) -> bool {{ matches!(self, Self::A) }} }}"
)
.expect("write");
writeln!(text, "impl T{i} {{").expect("write");
for j in 0..members {
let next = (j + 1) % members;
writeln!(
text,
" pub fn a{j}(&self) -> u8 {{ Self::a{next}(self) + self.a{next}() + K{i} + S{i} }}"
)
.expect("write");
}
writeln!(text, "}}\nimpl crate::Tr for T{i} {{").expect("write");
for j in 0..members {
writeln!(text, " fn t{j}(&self) -> u8 {{ self.a{j}() }}").expect("write");
}
text.push_str("}\n}\n");
}
text.push_str("}\n");
text
}
fn kinds_work(types: usize, members: usize) -> ([usize; 6], usize) {
let ws = load(&kinds(types, members));
let top = ws
.resolve_in("demo::top", Namespace::Type)
.expect("top")
.sites[0];
work_of(&ws, &[Node::Item(top)])
}
#[test]
fn the_work_over_types_impl_blocks_traits_and_members_grows_with_each_and_not_their_product() {
for (n, k) in [(1, 1), (2, 3), (4, 2)] {
let (_, reached) = kinds_work(n, k);
assert_eq!(reached, 2 + k + n * (11 + 2 * k), "{n} {k}");
}
let by_types: Vec<[usize; 6]> = [4, 8, 12].map(|n| kinds_work(n, 3).0).to_vec();
let by_members: Vec<[usize; 6]> = [2, 4, 6].map(|k| kinds_work(4, k).0).to_vec();
for sizes in [&by_types, &by_members] {
for (kind, name) in KINDS.iter().enumerate() {
let first = sizes[1][kind] - sizes[0][kind];
let second = sizes[2][kind] - sizes[1][kind];
assert_eq!(first, second, "{name:?}: {sizes:?}");
}
}
for (n, k) in [(1, 1), (2, 3), (4, 2), (3, 5)] {
let ([tokens, units, paths, steps, segments, lookups], _) = kinds_work(n, k);
assert_eq!(tokens, 8 + 9 * k + n * (83 + 38 * k), "{n} {k}");
assert_eq!(units, 4 * k + n * (39 + 16 * k), "{n} {k}");
assert_eq!(paths, 2 + n * (14 + 3 * k), "{n} {k}");
assert_eq!(steps, 5 + 5 * k + n * (68 + 31 * k), "{n} {k}");
assert_eq!(segments, 9 * n, "{n} {k}");
assert_eq!(lookups, 3 + 34 * n, "{n} {k}");
}
}
#[test]
fn a_path_of_fifty_thousand_segments_is_walked_once_and_not_once_for_each_prefix() {
const SEGMENTS: usize = 50_000;
let text = format!(
"pub mod m {{ pub use crate::m; pub struct End; }}\npub type T = {}End;\n",
"m::".repeat(SEGMENTS)
);
let ws = load(&text);
let alias = ws.resolve("demo::T").expect("the alias").sites[0];
let end = ws.resolve("demo::m::End").expect("the struct").sites[0];
let segments = SEGMENTS + 1;
let (reached, tally) = work::measure_kind(Work::SegmentReads, 4 * segments, || {
ws.reachable(&[Node::Item(alias)])
});
let reached = reached.unwrap_or_else(|e| panic!("{e}"));
assert!(reached.contains(Node::Item(end)));
assert!(tally.get(Work::SegmentReads) >= segments);
assert!(tally.get(Work::Lookups) <= 4 * segments);
assert_eq!(tally.get(Work::ReachPaths), 1);
}
fn dense(runs: usize) -> String {
format!("pub fn f() {{ {}}}\nfn a() {{}}\n", "a; ".repeat(runs))
}
fn walk_charge(text: &str) -> usize {
let ws = load(text);
let held = ws.usage().item_bytes;
let walk = |limit: usize| {
let ws = load_with(
text,
&LoadOptions {
max_item_bytes: limit,
..LoadOptions::default()
},
);
let f = ws.resolve_in("demo::f", Namespace::Value).expect("f").sites[0];
ws.reachable(&[Node::Item(f)])
};
let (mut low, mut high) = (held, held + (1 << 24));
assert!(walk(high).is_ok());
while high - low > 1 {
let mid = low + (high - low) / 2;
if walk(mid).is_ok() {
high = mid;
} else {
low = mid;
}
}
let error = walk(low).expect_err("one byte less is refused");
match error {
ReachError::Budget(error) => {
assert!(
matches!(
error.kind,
LoadErrorKind::Budget {
budget: Budget::ItemBytes,
limit
} if limit == low
),
"{error}"
);
assert_eq!(error.file.as_str(), "src/lib.rs");
}
other => panic!("{other}"),
}
high - held
}
#[test]
fn what_the_walk_holds_is_charged_to_the_item_bytes_budget_on_from_the_load() {
let per_run = size_of::<Run>() + size_of::<(usize, usize)>() + size_of::<usize>();
let charges = [1000, 2000, 3000].map(|runs| walk_charge(&dense(runs)));
assert_eq!(charges[1] - charges[0], 1000 * per_run);
assert_eq!(charges[2] - charges[1], 1000 * per_run);
#[cfg(target_pointer_width = "64")]
assert_eq!(per_run, 56);
assert!(per_run < 20 * 3, "{per_run}");
}
#[test]
fn format_candidates_charge_owned_bytes_and_return_worker_work_to_the_caller() {
let source = |calls| {
format!(
"const VALUE:u32=7; pub fn f(){{ {} }}",
"let _=format!(\"{VALUE}\");".repeat(calls)
)
};
let samples = [32, 64, 96].map(|calls| {
let text = source(calls);
let ws = load(&text);
let root = ws.resolve_in("demo::f", Namespace::Value).expect("f").sites[0];
let capture = ws
.resolve_in("demo::VALUE", Namespace::Value)
.expect("VALUE")
.sites[0];
let (reached, tally) = work::measure(100_000, || ws.reachable(&[Node::Item(root)]));
assert!(reached.expect("reachability").contains(Node::Item(capture)));
let tokens = tally.get(Work::ReachFormatTokens);
let bytes = tally.get(Work::ReachFormatBytes);
assert!(tokens > calls, "worker token work was lost");
assert!(
bytes >= calls * "{VALUE}".len(),
"worker decode work was lost"
);
(tokens, bytes, walk_charge(&text))
});
for at in 0..2 {
let get = |n: usize| if at == 0 { samples[n].0 } else { samples[n].1 };
assert_eq!(get(2) - get(1), get(1) - get(0));
}
assert!(samples[1].2 > samples[0].2);
assert_eq!(samples[2].2 - samples[1].2, samples[1].2 - samples[0].2);
}
#[test]
fn code_prefix_reads_share_one_query_account_and_refuse_one_less() {
let tree = MemoryTree::from([
(
"Cargo.toml",
"[package]\nname='demo'\nversion='0.1.0'\nedition='2021'\n",
),
(
"src/lib.rs",
"mod a { pub struct X {} } mod b { pub use crate::a::*; } pub use b::*;",
),
]);
let ws = Workspace::load(&tree, &["."]).expect("glob source");
let index = ws.index();
let root = index.target_roots[0];
let (file, line) = index.module_site(root);
let words = ["X".to_owned()];
let run = |limit| {
let options = LoadOptions {
max_query_work: limit,
..LoadOptions::default()
};
let meter = Meter::query(&options);
let answer = index.reach_run(
root,
&words,
false,
false,
Steps::QueryItems {
meter: &meter,
file: &file,
line,
},
);
(answer, meter.usage())
};
let (answer, usage) = run(usize::MAX);
let expected = answer.expect("native admitted resolver");
assert!(!expected.is_empty());
assert!(usage.work > 0);
assert!(usage.item_bytes > 0);
assert_eq!(usage.glob_bytes, 0);
assert_eq!(run(usage.work).0.expect("exact work"), expected);
let error = run(usage.work - 1).0.expect_err("one work unit short");
assert!(
matches!(error.kind, LoadErrorKind::Budget { budget: Budget::Work, limit }
if limit == usage.work - 1)
);
assert_eq!(error.file.as_str(), "src/lib.rs");
}
#[test]
fn a_shared_files_edition_caches_are_each_counted_and_charged_once() {
let tree = MemoryTree::from([
("Cargo.toml", "[workspace]\nmembers = [\"old\", \"new\"]\n"),
(
"old/Cargo.toml",
"[package]\nname = \"old\"\nversion = \"0.1.0\"\nedition = \"2021\"\n",
),
(
"new/Cargo.toml",
"[package]\nname = \"new\"\nversion = \"0.1.0\"\nedition = \"2024\"\n",
),
(
"old/src/lib.rs",
"#[path = \"../../shared.rs\"] mod shared;\n",
),
(
"new/src/lib.rs",
"#[path = \"../../shared.rs\"] mod shared;\n",
),
("shared.rs", "pub fn f() { r#gen() }\nfn r#gen() {}\n"),
]);
let ws = Workspace::load(&tree, &["."]).expect("shared source");
let options = LoadOptions::default();
let meter = Meter::new(&options);
let files = ws
.files()
.map(|source| {
(
source.path.clone(),
crate::SourceFile {
path: source.path.clone(),
package: source.package.clone(),
shipping: source.shipping,
test: source.test,
text: source.text.clone(),
facts: source.facts.clone(),
reached: source.reached.clone(),
},
)
})
.collect();
let item = |name| {
ws.resolve_in(name, Namespace::Value)
.expect("function")
.sites[0]
};
let old = item("old::shared::f");
let new = item("new::shared::f");
let file = &ws.item(old).expect("old function").file;
assert_eq!(file, &ws.item(new).expect("new function").file);
let mut walk = Walk::new(ws.index(), &files, &meter, (file, 1)).expect("walk tables");
let old_module = walk.homes[old.0].module.expect("old module");
let new_module = walk.homes[new.0].module.expect("new module");
let (_, first) = work::measure(usize::MAX, || {
walk.load(file, old_module).expect("old cache")
});
let first_bytes = meter.usage().item_bytes;
let (_, repeated) = work::measure(usize::MAX, || {
walk.load(file, old_module).expect("old cache again")
});
assert!(first.get(Work::ReachTokens) > 0);
assert_eq!(repeated.get(Work::ReachTokens), 0);
assert_eq!(meter.usage().item_bytes, first_bytes);
let (_, second) = work::measure(usize::MAX, || {
walk.load(file, new_module).expect("new cache")
});
let both_bytes = meter.usage().item_bytes;
assert_eq!(second.get(Work::ReachTokens), first.get(Work::ReachTokens));
assert!(both_bytes > first_bytes);
assert_eq!(walk.files_runs.len(), 2);
let (_, repeated) = work::measure(usize::MAX, || {
walk.load(file, new_module).expect("new cache again")
});
assert_eq!(repeated.get(Work::ReachTokens), 0);
assert_eq!(meter.usage().item_bytes, both_bytes);
let under = |limit| -> Result<usize, ReachError> {
let options = LoadOptions {
max_item_bytes: limit,
..LoadOptions::default()
};
let meter = Meter::new(&options);
let mut walk = Walk::new(ws.index(), &files, &meter, (file, 1))?;
walk.load(file, old_module)?;
walk.load(file, new_module)?;
Ok(meter.usage().item_bytes)
};
assert_eq!(
under(both_bytes).expect("exact retained-byte limit"),
both_bytes
);
let error = under(both_bytes - 1).expect_err("one byte short refuses second cache");
assert!(
matches!(error, ReachError::Budget(ref load) if matches!(load.kind,
LoadErrorKind::Budget { budget: Budget::ItemBytes, limit } if limit == both_bytes - 1))
);
}
}