use std::cell::RefCell;
use std::collections::{BTreeMap, BTreeSet, HashMap};
use std::rc::Rc;
use super::item_head::Visibility;
use super::path_vocab::path_within;
use super::path_vocab::{PathSite, WrittenRoot, written_root};
use super::path_vocab::{Sysroot, sysroot_crate};
use super::path_vocab::{block_segment, is_block_segment, names_a_block_item, readable_module};
pub(super) use super::scope_tree::Namespace;
use super::scope_tree::{Binding, DeclKind, Declaration, ScopeKind, ScopeTable};
use super::token_tree::Edition;
const MAX_RESOLUTION_CHAIN: usize = 64;
const MAX_RESOLUTION_PATHS: usize = 32_768;
const MAX_RESOLUTION_BYTES: usize = 8 * 1024 * 1024;
const MAX_GLOB_GRAPH_PATHS: usize = 1_048_576;
const MAX_GLOB_GRAPH_BYTES: usize = 64 * 1024 * 1024;
fn width_refusal() -> String {
format!(
"cannot judge a resolution holding more than {MAX_RESOLUTION_PATHS} candidate paths or \
{MAX_RESOLUTION_BYTES} bytes of path text; reduce the branching imports, globs or re-exports"
)
}
#[derive(Default)]
pub(super) struct ReadingSize {
paths: usize,
bytes: usize,
}
impl ReadingSize {
pub(super) fn add(&mut self, path: &str) -> Result<(), String> {
self.paths = self.paths.saturating_add(1);
self.bytes = self.bytes.saturating_add(path.len());
self.check()
}
fn head(&mut self, head: &Head) -> Result<(), String> {
match head {
Head::Candidates {
bound,
declared,
through,
heads,
foreign,
..
} => {
for path in bound
.iter()
.map(|(path, _)| path.as_str())
.chain(declared.iter().map(Declared::path))
.chain(
through
.iter()
.chain(heads)
.chain(foreign)
.map(String::as_str),
)
{
self.add(path)?;
}
Ok(())
}
Head::Foreign(paths) => paths.iter().try_for_each(|path| self.add(path)),
_ => Ok(()),
}
}
fn check_graph(&self) -> Result<(), String> {
if self.paths > MAX_GLOB_GRAPH_PATHS || self.bytes > MAX_GLOB_GRAPH_BYTES {
Err(format!(
"cannot judge a glob graph holding more than {MAX_GLOB_GRAPH_PATHS} candidate paths or \
{MAX_GLOB_GRAPH_BYTES} bytes of path text; reduce the branching imports, globs or re-exports"
))
} else {
Ok(())
}
}
fn check(&self) -> Result<(), String> {
if self.paths > MAX_RESOLUTION_PATHS || self.bytes > MAX_RESOLUTION_BYTES {
Err(width_refusal())
} else {
Ok(())
}
}
}
fn chain_refusal(quote: &str, module: &str) -> String {
format!(
"cannot judge a chain of more than {MAX_RESOLUTION_CHAIN} imports, globs, re-exports and `type` \
aliases from `{quote};` in {}",
readable_module(module)
)
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub(super) enum Named {
Paths(Vec<String>),
External(String),
Unbound {
head: String,
rest: Vec<String>,
also: Vec<String>,
},
Local,
Invalid,
PastCap(String),
}
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub(super) enum Declared {
Module(String),
Item(String),
}
impl Declared {
pub(super) fn path(&self) -> &str {
match self {
Declared::Module(path) | Declared::Item(path) => path,
}
}
}
type Bound = (String, String);
#[derive(Clone, PartialEq, Eq)]
enum Head {
Candidates {
bound: Vec<Bound>,
declared: Vec<Declared>,
through: Vec<String>,
heads: Vec<String>,
foreign: Vec<String>,
open: bool,
},
Local,
Foreign(Vec<String>),
Unbound,
PastCap(String),
}
type GlobNode = (usize, u32, String);
enum GlobRead {
Answered(Head),
Globs {
own: Option<Head>,
edges: Vec<GlobEdge>,
},
}
enum GlobEdge {
Into {
quote: String,
target: String,
into: Vec<usize>,
},
Foreign(String),
}
#[derive(Default)]
struct GlobGraph {
nodes: Vec<GlobNode>,
index: HashMap<GlobNode, usize>,
reads: Vec<GlobRead>,
}
impl GlobGraph {
fn node(&mut self, t: usize, id: u32, from: &str) -> usize {
let key = (t, id, from.to_string());
if let Some(&n) = self.index.get(&key) {
return n;
}
self.nodes.push(key.clone());
self.index.insert(key, self.nodes.len() - 1);
self.nodes.len() - 1
}
fn settle(&self, head: &str) -> Result<Vec<Head>, String> {
let order = self.children_first();
let mut total = ReadingSize::default();
let mut sizes = Vec::new();
let mut answers = Vec::new();
for read in &self.reads {
let answer = match read {
GlobRead::Answered(answer) => answer.clone(),
GlobRead::Globs { own, .. } => own.clone().unwrap_or(Head::Unbound),
};
let mut size = ReadingSize::default();
size.head(&answer)?;
total.paths += size.paths;
total.bytes += size.bytes;
total.check_graph()?;
sizes.push(size);
answers.push(answer);
}
for _ in 0..=self.nodes.len() {
let mut changed = false;
for &n in &order {
let GlobRead::Globs { own, edges } = &self.reads[n] else {
continue;
};
let globbed = match joined(edges.iter().map(|edge| match edge {
GlobEdge::Foreign(path) => Head::Foreign(vec![path.clone()]),
GlobEdge::Into {
quote,
target,
into,
} => brought_through(
joined(into.iter().map(|&m| answers[m].clone())),
quote,
target,
head,
),
})) {
Head::Local => Head::Unbound,
other => other,
};
let answer = match (own, globbed) {
(None, globbed) => globbed,
(Some(own), Head::Unbound) => own.clone(),
(Some(own), globbed) => joined([own.clone(), globbed]),
};
if answer != answers[n] {
let mut size = ReadingSize::default();
size.head(&answer)?;
total.paths = total.paths - sizes[n].paths + size.paths;
total.bytes = total.bytes - sizes[n].bytes + size.bytes;
total.check_graph()?;
sizes[n] = size;
answers[n] = answer;
changed = true;
}
}
if !changed {
return Ok(answers);
}
}
Err(format!(
"cannot judge what the globs reaching `{head}` bring: their answers do not settle within {} readings",
self.nodes.len() + 1
))
}
fn children_first(&self) -> Vec<usize> {
let children = |n: usize| -> Vec<usize> {
match &self.reads[n] {
GlobRead::Globs { edges, .. } => edges
.iter()
.flat_map(|edge| match edge {
GlobEdge::Into { into, .. } => into.clone(),
GlobEdge::Foreign(_) => Vec::new(),
})
.collect(),
GlobRead::Answered(_) => Vec::new(),
}
};
let mut order = Vec::with_capacity(self.nodes.len());
let mut seen = vec![false; self.nodes.len()];
for root in 0..self.nodes.len() {
if seen[root] {
continue;
}
seen[root] = true;
let mut stack = vec![(root, children(root), 0usize)];
while let Some((n, kids, next)) = stack.last_mut() {
if let Some(&kid) = kids.get(*next) {
*next += 1;
if !seen[kid] {
seen[kid] = true;
stack.push((kid, children(kid), 0));
}
} else {
order.push(*n);
stack.pop();
}
}
}
order
}
}
fn brought_through(found: Head, quote: &str, target: &str, head: &str) -> Head {
match found {
Head::Candidates {
bound,
declared,
through,
foreign,
..
} => Head::Candidates {
bound: bound
.into_iter()
.chain(
declared
.iter()
.map(|d| (d.path().to_string(), quote.to_string())),
)
.collect(),
declared: Vec::new(),
through: through
.into_iter()
.chain([format!("{target}::{head}")])
.collect(),
heads: vec![format!("{target}::{head}")],
foreign,
open: false,
},
other => other,
}
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
enum Presence {
#[default]
Absent,
Unknown,
Known,
}
#[derive(Clone, Debug, Default)]
struct Denoted {
paths: Vec<String>,
beside: Vec<String>,
presence: Presence,
terminal_reaches: bool,
}
pub(super) fn with_rest(mut path: String, rest: &[String]) -> String {
for segment in rest {
path.push_str("::");
path.push_str(segment);
}
path
}
pub(super) fn extern_crate_names(target: &str) -> Declared {
if target == "crate" {
Declared::Module(target.to_string())
} else {
Declared::Item(target.to_string())
}
}
#[derive(Default)]
pub(super) struct Walk {
resolving: Vec<Resolving>,
cuts: usize,
}
struct Resolving {
key: (usize, u32, String),
quote: String,
module: String,
}
impl Walk {
fn meets_cycle(&mut self, key: &(usize, u32, String)) -> bool {
let cycle = self.resolving.iter().any(|entry| &entry.key == key);
self.cuts += usize::from(cycle);
cycle
}
fn reads_itself(&self, key: &(usize, u32, String)) -> bool {
self.resolving.last().is_some_and(|entry| &entry.key == key)
}
fn enter(
&mut self,
key: (usize, u32, String),
quote: String,
module: &str,
) -> Result<(), String> {
if self.resolving.len() >= MAX_RESOLUTION_CHAIN {
let first = &self.resolving[0];
return Err(chain_refusal(&first.quote, &first.module));
}
self.resolving.push(Resolving {
key,
quote,
module: module.to_string(),
});
Ok(())
}
fn leave(&mut self) {
self.resolving.pop();
}
}
pub(super) enum BindingNames {
Paths(Vec<String>, Vec<String>),
Local,
PastCap(String),
}
type NameKey = (usize, u32, String, PathSite, Namespace);
type PresenceKey = (usize, u32, String, String, Namespace);
type DenoteKey = (String, Namespace, bool, Option<(String, bool)>);
struct DenotationMemo {
answers: HashMap<DenoteKey, Result<Rc<Denoted>, String>>,
paths: usize,
bytes: usize,
limits: (usize, usize, usize),
}
impl Default for DenotationMemo {
fn default() -> Self {
Self {
answers: HashMap::new(),
paths: 0,
bytes: 0,
limits: (262_144, 1_048_576, 64 * 1024 * 1024),
}
}
}
impl DenotationMemo {
fn get(&self, key: &DenoteKey) -> Option<&Result<Rc<Denoted>, String>> {
self.answers.get(key)
}
fn insert(
&mut self,
key: DenoteKey,
answer: Result<Rc<Denoted>, String>,
) -> Result<(), String> {
let mut paths = self.paths;
let mut bytes = self.bytes.saturating_add(key.0.len());
if let Some((prefix, _)) = &key.3 {
bytes = bytes.saturating_add(prefix.len());
}
match &answer {
Ok(answer) => {
for path in answer.paths.iter().chain(&answer.beside) {
paths = paths.saturating_add(1);
bytes = bytes.saturating_add(path.len());
}
}
Err(message) => bytes = bytes.saturating_add(message.len()),
}
let (entries_limit, paths_limit, bytes_limit) = self.limits;
if self.answers.len() >= entries_limit || paths > paths_limit || bytes > bytes_limit {
return Err(format!(
"cannot judge a denotation memo holding more than {entries_limit} readings, {paths_limit} candidate paths or {bytes_limit} bytes of key and answer text; reduce the branching imports, globs or re-exports"
));
}
self.answers.insert(key, answer);
self.paths = paths;
self.bytes = bytes;
Ok(())
}
fn clear(&mut self) {
self.answers.clear();
self.paths = 0;
self.bytes = 0;
}
}
type GlobKey = (usize, u32, usize);
type GlobTargets = HashMap<GlobKey, Result<Vec<String>, String>>;
type LookupKey = (usize, u32, String, Namespace, String, usize, bool);
pub(super) struct CrateScopes {
pub(super) tables: Vec<ScopeTable>,
edition: Edition,
proc_macro: bool,
dependencies: BTreeSet<String>,
pub(super) modules: BTreeMap<String, Vec<(usize, u32)>>,
blocks: BTreeMap<String, (usize, u32)>,
extern_prelude: BTreeMap<String, Vec<Declared>>,
certain_externs: BTreeSet<String>,
named: RefCell<HashMap<NameKey, Named>>,
denoted: RefCell<DenotationMemo>,
looked: RefCell<HashMap<LookupKey, Head>>,
presence: RefCell<HashMap<PresenceKey, Presence>>,
globs: RefCell<Option<GlobTargets>>,
reading_globs: RefCell<Option<GlobTargets>>,
reading_glob: RefCell<Option<GlobKey>>,
read_itself: std::cell::Cell<bool>,
#[cfg(test)]
scope_reads: std::cell::Cell<usize>,
}
impl CrateScopes {
fn extern_prelude_holds(&self, head: &str) -> bool {
match sysroot_crate(head) {
Some(Sysroot::Prelude) => true,
Some(Sysroot::ProcMacro) => self.proc_macro,
Some(Sysroot::Test) | None => false,
}
}
pub(super) fn in_a_proc_macro_crate(self) -> Self {
CrateScopes {
proc_macro: true,
..self
}
}
fn crate_named(&self, head: String, rest: &[String]) -> Option<String> {
(self.dependencies.contains(&head) || self.extern_prelude_holds(&head))
.then(|| with_rest(head, rest))
}
pub(super) fn depending_on(self, dependencies: BTreeSet<String>) -> Self {
CrateScopes {
dependencies,
..self
}
}
pub(super) fn new(tables: Vec<ScopeTable>, edition: Edition) -> Self {
let mut modules: BTreeMap<String, Vec<(usize, u32)>> = BTreeMap::new();
let mut blocks: BTreeMap<String, (usize, u32)> = BTreeMap::new();
let mut extern_prelude: BTreeMap<String, Vec<Declared>> = BTreeMap::new();
let mut certain_externs = BTreeSet::new();
for (t, table) in tables.iter().enumerate() {
for (id, scope) in table.scopes.iter().enumerate() {
let id = u32::try_from(id).expect("scope table exceeds u32");
match scope.kind {
ScopeKind::Module => modules
.entry(scope.module.clone())
.or_default()
.push((t, id)),
ScopeKind::Block => {
blocks.insert(
format!("{}::{}", scope.module, block_segment(table.table, id)),
(t, id),
);
}
}
if scope.kind == ScopeKind::Module && scope.module == "crate" {
for (name, all) in &scope.declarations {
for declaration in all {
if let DeclKind::ExternCrate { target, gated } = &declaration.kind {
if !gated {
certain_externs.insert(name.clone());
}
extern_prelude
.entry(name.clone())
.or_default()
.push(extern_crate_names(target));
}
}
}
}
}
}
CrateScopes {
tables,
edition,
proc_macro: false,
dependencies: BTreeSet::new(),
modules,
blocks,
extern_prelude,
certain_externs,
named: RefCell::default(),
denoted: RefCell::default(),
looked: RefCell::default(),
presence: RefCell::default(),
globs: RefCell::default(),
reading_globs: RefCell::default(),
reading_glob: RefCell::default(),
read_itself: std::cell::Cell::default(),
#[cfg(test)]
scope_reads: std::cell::Cell::default(),
}
}
pub(super) fn table(&self, t: usize) -> &ScopeTable {
&self.tables[t]
}
pub(super) fn head_names(
&self,
t: usize,
scope: u32,
written: &str,
site: PathSite,
ns: Namespace,
) -> Named {
self.name_raw(
t,
scope,
written,
site,
ns,
&mut Vec::new(),
&mut Walk::default(),
true,
)
}
pub(super) fn name(
&self,
t: usize,
scope: u32,
written: &str,
site: PathSite,
ns: Namespace,
) -> Named {
let key = (t, scope, written.to_string(), site, ns);
if let Some(named) = self.named.borrow().get(&key) {
return named.clone();
}
let mut through = Vec::new();
let named = match self.name_raw(
t,
scope,
written,
site,
ns,
&mut through,
&mut Walk::default(),
false,
) {
Named::Paths(paths) => match self.denote_all(through, &paths, ns) {
Err(refusal) => Named::PastCap(refusal),
Ok(None) => Named::Local,
Ok(Some(denoted)) => Named::Paths(denoted),
},
Named::Unbound { head, rest, also } if !also.is_empty() => {
match self.denote_all(through, &also, ns) {
Err(refusal) => Named::PastCap(refusal),
Ok(denoted) => Named::Unbound {
head,
rest,
also: denoted.unwrap_or_default(),
},
}
}
other => other,
};
self.named.borrow_mut().insert(key, named.clone());
named
}
fn denote_all(
&self,
through: Vec<String>,
paths: &[String],
ns: Namespace,
) -> Result<Option<Vec<String>>, String> {
let mut denoted = through;
let mut size = ReadingSize::default();
for path in &denoted {
size.add(path)?;
}
let mut past_cap = None;
for path in paths {
match self.denote(path, ns) {
Ok(found) => {
for path in found {
if let Err(refusal) = size.add(&path) {
past_cap = least(past_cap, refusal);
break;
}
denoted.push(path);
}
}
Err(refusal) => past_cap = least(past_cap, refusal),
}
}
if let Some(refusal) = past_cap {
return Err(refusal);
}
let reached = !denoted.is_empty();
denoted.retain(|path| !names_a_block_item(path));
Ok((!reached || !denoted.is_empty()).then(|| sorted_unique(denoted)))
}
pub(super) fn denote(&self, path: &str, ns: Namespace) -> Result<Vec<String>, String> {
self.denotation(path, ns, true, None)
.map(|denoted| sorted_unique(denoted.paths.iter().chain(&denoted.beside).cloned()))
}
#[cfg(test)]
fn readable_paths(&self, path: &str, ns: Namespace) -> Result<Vec<String>, String> {
self.denotation(path, ns, false, None)
.map(|denoted| denoted.paths.clone())
}
pub(super) fn hazard_paths(
&self,
path: &str,
ns: Namespace,
prefix: &str,
ancestors: bool,
) -> Result<(Vec<String>, bool), String> {
self.denotation(path, ns, false, Some((prefix, ancestors)))
.map(|denoted| (denoted.paths.clone(), denoted.terminal_reaches))
}
fn denotation(
&self,
path: &str,
ns: Namespace,
candidates: bool,
hazard: Option<(&str, bool)>,
) -> Result<Rc<Denoted>, String> {
let key = (
path.to_string(),
ns,
candidates,
hazard.map(|(prefix, ancestors)| (prefix.to_string(), ancestors)),
);
if let Some(found) = self.denoted.borrow().get(&key) {
return found.clone();
}
let found = self
.denote_in(path, ns, &mut Walk::default(), candidates, hazard)
.map(Rc::new);
self.denoted.borrow_mut().insert(key, found.clone())?;
found
}
#[allow(clippy::too_many_arguments)]
fn name_raw(
&self,
t: usize,
scope: u32,
written: &str,
site: PathSite,
ns: Namespace,
through: &mut Vec<String>,
walk: &mut Walk,
head_alone: bool,
) -> Named {
let module = &self.tables[t].scopes[scope as usize].module;
let mut named_by =
|head: Head, head_name: String, rest: Vec<String>, from_root: bool| match head {
Head::Candidates {
bound,
declared,
through: passed,
heads,
foreign,
open,
} => {
let named: Vec<String> = if head_alone {
heads
} else {
through.extend(passed.into_iter().map(|p| with_rest(p, &rest)));
bound
.into_iter()
.map(|(path, _)| path)
.chain(declared.iter().map(|d| d.path().to_string()))
.collect()
}
.into_iter()
.chain(foreign.into_iter().filter(|_| from_root))
.map(|p| with_rest(p, &rest))
.collect();
match open {
false => Named::Paths(named),
true if self.extern_prelude_holds(&head_name) => Named::Paths(
named
.into_iter()
.chain([with_rest(head_name, &rest)])
.collect(),
),
true => Named::Unbound {
head: head_name,
rest,
also: named,
},
}
}
Head::Foreign(paths) if from_root => {
Named::Paths(paths.into_iter().map(|p| with_rest(p, &rest)).collect())
}
Head::Local => Named::Local,
Head::PastCap(refusal) => Named::PastCap(refusal),
Head::Unbound | Head::Foreign(_) if self.extern_prelude_holds(&head_name) => {
Named::Paths(vec![with_rest(head_name, &rest)])
}
Head::Unbound if from_root => Named::External(with_rest(head_name, &rest)),
Head::Unbound | Head::Foreign(_) => Named::Unbound {
head: head_name,
rest,
also: Vec::new(),
},
};
let last_ns = |rest: &[String]| if rest.is_empty() { ns } else { Namespace::Type };
match written_root(written, module, site, self.edition) {
WrittenRoot::Crate(path) => Named::Paths(vec![path]),
WrittenRoot::Extern { head, rest } => {
let found = self.in_extern_prelude(&head, last_ns(&rest));
named_by(found, head, rest, true)
}
WrittenRoot::FromCrateRoot { head, rest } => {
let found = self.lookup_in_module("crate", &head, last_ns(&rest), "crate", walk);
named_by(found, head, rest, true)
}
WrittenRoot::Bare { head, rest } => {
let found = self.lookup(t, scope, &head, last_ns(&rest), walk);
named_by(found, head, rest, false)
}
WrittenRoot::Invalid => Named::Invalid,
}
}
fn lookup(&self, t: usize, scope: u32, head: &str, ns: Namespace, walk: &mut Walk) -> Head {
if ns == Namespace::Either {
return joined(
[Namespace::Type, Namespace::Value].map(|ns| self.lookup(t, scope, head, ns, walk)),
);
}
let mut current = Some(scope);
let mut unsettled = Vec::new();
let mut gated = false;
while let Some(id) = current {
let entry = &self.tables[t].scopes[id as usize];
match self.scope_lookup(t, id, head, ns, &entry.module, walk) {
Head::Unbound | Head::Foreign(_) if entry.kind == ScopeKind::Block => {
current = entry.parent;
}
Head::Unbound | Head::Foreign(_) => break,
answer if !self.answer_ends_lookup(&answer, t, id, head, ns, walk) => {
gated |= self.held_only_where_gated(t, id, head, ns);
unsettled.push(answer);
current = match entry.kind {
ScopeKind::Block => entry.parent,
ScopeKind::Module => None,
};
}
answer if unsettled.is_empty() => return answer,
answer => return joined(unsettled.into_iter().chain([answer])),
}
}
let prelude = self.in_extern_prelude(head, ns);
let open = match prelude {
Head::Candidates { .. } => !self.certain_externs.contains(head),
_ => gated,
};
let mut answer = joined(unsettled.into_iter().chain([prelude]));
if open {
if let Head::Candidates { open, .. } = &mut answer {
*open = true;
} else if answer == Head::Local {
answer = Head::Unbound;
}
}
answer
}
fn answer_ends_lookup(
&self,
answer: &Head,
t: usize,
id: u32,
head: &str,
ns: Namespace,
walk: &mut Walk,
) -> bool {
!(matches!(answer, Head::Candidates { .. } | Head::Local)
&& self.may_not_hold_here(t, id, head, ns, walk))
}
fn may_not_hold_here(
&self,
t: usize,
id: u32,
head: &str,
ns: Namespace,
walk: &mut Walk,
) -> bool {
self.held_only_where_gated(t, id, head, ns)
|| self.binds_only_what_is_not_read(t, id, head, ns, walk)
}
fn held_only_where_gated(&self, t: usize, id: u32, head: &str, ns: Namespace) -> bool {
let entry = &self.tables[t].scopes[id as usize];
let held = entry.ungated.get(head);
(entry.bindings.contains_key(head) || entry.declarations.contains_key(head))
&& !held.is_some_and(|&(type_ns, value_ns)| match ns {
Namespace::Type => type_ns,
Namespace::Value => value_ns,
Namespace::Either => type_ns || value_ns,
})
}
fn binds_only_what_is_not_read(
&self,
t: usize,
id: u32,
head: &str,
ns: Namespace,
walk: &mut Walk,
) -> bool {
if ns == Namespace::Either {
return [Namespace::Type, Namespace::Value]
.into_iter()
.any(|ns| self.binds_only_what_is_not_read(t, id, head, ns, walk));
}
let entry = &self.tables[t].scopes[id as usize];
if entry
.declarations
.get(head)
.is_some_and(|all| all.iter().any(|declaration| declaration.in_namespace(ns)))
{
return false;
}
let bindings = entry.bindings.get(head).map_or(&[][..], Vec::as_slice);
!bindings.is_empty()
&& bindings.iter().all(|binding| match binding {
Binding::Import { written, .. } => matches!(
self.import_presence(t, id, head, written, ns, walk),
Ok(Presence::Unknown)
),
Binding::Alias { .. } => false,
})
}
fn in_extern_prelude(&self, head: &str, ns: Namespace) -> Head {
match self.extern_prelude.get(head) {
Some(declared) if ns != Namespace::Value => Head::Candidates {
bound: Vec::new(),
heads: declared.iter().map(|d| d.path().to_string()).collect(),
declared: declared.clone(),
through: Vec::new(),
foreign: Vec::new(),
open: false,
},
_ => Head::Unbound,
}
}
fn scope_lookup(
&self,
t: usize,
id: u32,
head: &str,
ns: Namespace,
from: &str,
walk: &mut Walk,
) -> Head {
if ns == Namespace::Either {
return joined(
[Namespace::Type, Namespace::Value]
.map(|ns| self.scope_lookup(t, id, head, ns, from, walk)),
);
}
let memo = (
t,
id,
head.to_string(),
ns,
from.to_string(),
walk.resolving.len(),
walk.reads_itself(&(t, id, head.to_string())),
);
if let Some(head) = self.looked.borrow().get(&memo) {
return head.clone();
}
let cuts = walk.cuts;
let answer = self.scope_lookup_once(t, id, head, ns, from, walk);
if walk.cuts == cuts && !matches!(answer, Head::PastCap(_)) {
self.looked.borrow_mut().insert(memo, answer.clone());
}
answer
}
fn scope_lookup_once(
&self,
t: usize,
id: u32,
head: &str,
ns: Namespace,
from: &str,
walk: &mut Walk,
) -> Head {
#[cfg(test)]
self.scope_reads.set(self.scope_reads.get() + 1);
match self.bound_here(t, id, head, ns, from, walk) {
Some(answer)
if !self.tables[t].scopes[id as usize].globs.is_empty()
&& !self.answer_ends_lookup(&answer, t, id, head, ns, walk) =>
{
match self.through_globs(t, id, head, ns, from, walk) {
Head::Unbound => answer,
globbed => joined([answer, globbed]),
}
}
Some(answer) => answer,
None => self.through_globs(t, id, head, ns, from, walk),
}
}
fn bound_here(
&self,
t: usize,
id: u32,
head: &str,
ns: Namespace,
from: &str,
walk: &mut Walk,
) -> Option<Head> {
let entry = &self.tables[t].scopes[id as usize];
if let Some(refusal) = self.tables[t].refusal() {
return Some(Head::PastCap(format!(
"it reads names through `{}`, whose file holds what the scanner cannot read: {refusal}",
entry.module
)));
}
let visible = |visibility: &Visibility| visibility.visible_from(&entry.module, from);
let key = (t, id, head.to_string());
let mut bindings: Vec<&Binding> = Vec::new();
if !walk.reads_itself(&key) && !walk.meets_cycle(&key) {
for binding in entry.bindings.get(head).into_iter().flatten() {
if !visible(binding.visibility()) {
continue;
}
match self.binding_holds(t, id, head, binding, ns, walk) {
Ok(true) => bindings.push(binding),
Ok(false) => {}
Err(refusal) => return Some(Head::PastCap(refusal)),
}
}
}
let declarations: Vec<&Declaration> = entry
.declarations
.get(head)
.into_iter()
.flatten()
.filter(|declaration| declaration.in_namespace(ns) && visible(&declaration.visibility))
.collect();
if !bindings.is_empty() || !declarations.is_empty() {
let (mut bound, mut declared, mut through): (Vec<Bound>, Vec<Declared>, Vec<String>) =
(Vec::new(), Vec::new(), Vec::new());
let mut names_a_local_item = false;
for binding in bindings {
match self.binding_names(t, id, head, binding, ns, walk) {
BindingNames::Paths(found, passed) => {
let quote = binding_quote(head, binding);
bound.extend(found.into_iter().map(|path| (path, quote.clone())));
through.extend(passed);
}
BindingNames::Local => names_a_local_item = true,
BindingNames::PastCap(refusal) => return Some(Head::PastCap(refusal)),
}
}
for declaration in declarations {
match (&declaration.kind, entry.kind) {
(DeclKind::Module(path), _) => declared.push(Declared::Module(path.clone())),
(DeclKind::ExternCrate { target, .. }, _) => {
declared.push(extern_crate_names(target))
}
(DeclKind::Item(_), ScopeKind::Module) => {
declared.push(Declared::Item(format!("{}::{head}", entry.module)));
}
(DeclKind::Item(_), ScopeKind::Block) => names_a_local_item = true,
}
}
if bound.is_empty() && declared.is_empty() && names_a_local_item {
return Some(Head::Local);
}
declared.sort();
declared.dedup();
let heads = bound
.iter()
.map(|(path, _)| path.clone())
.chain(declared.iter().map(|d| d.path().to_string()))
.collect();
return Some(Head::Candidates {
bound,
declared,
through,
heads,
foreign: Vec::new(),
open: false,
});
}
None
}
fn through_globs(
&self,
t: usize,
id: u32,
head: &str,
ns: Namespace,
from: &str,
walk: &mut Walk,
) -> Head {
let cuts = walk.cuts;
let depth = walk.resolving.len();
let mut graph = GlobGraph::default();
let start = graph.node(t, id, from);
let mut next = 0;
while next < graph.nodes.len() {
let (t, id, from) = graph.nodes[next].clone();
next += 1;
let reading = if next - 1 == start {
self.glob_edges(&mut graph, t, id, head, &from)
} else {
let itself = walk.reads_itself(&(t, id, head.to_string()));
let memo = (t, id, head.to_string(), ns, from.clone(), depth, itself);
let held = self.looked.borrow().get(&memo).cloned();
match held.or_else(|| self.bound_here(t, id, head, ns, &from, walk)) {
Some(answer) if !self.answer_ends_lookup(&answer, t, id, head, ns, walk) => {
match self.glob_edges(&mut graph, t, id, head, &from) {
GlobRead::Globs { edges, .. } => GlobRead::Globs {
own: Some(answer),
edges,
},
refused => refused,
}
}
Some(answer) => GlobRead::Answered(answer),
None => self.glob_edges(&mut graph, t, id, head, &from),
}
};
graph.reads.push(reading);
}
let answers = match graph.settle(head) {
Ok(answers) => answers,
Err(refusal) => return Head::PastCap(refusal),
};
if walk.cuts == cuts {
let mut looked = self.looked.borrow_mut();
for (n, (t, id, from)) in graph.nodes.iter().enumerate() {
if n != start
&& matches!(graph.reads[n], GlobRead::Globs { .. })
&& !matches!(answers[n], Head::PastCap(_))
{
let itself = walk.reads_itself(&(*t, *id, head.to_string()));
looked.insert(
(*t, *id, head.to_string(), ns, from.clone(), depth, itself),
answers[n].clone(),
);
}
}
}
answers[start].clone()
}
fn glob_edges(
&self,
graph: &mut GlobGraph,
t: usize,
id: u32,
head: &str,
from: &str,
) -> GlobRead {
let entry = &self.tables[t].scopes[id as usize];
let mut edges = Vec::new();
let mut size = ReadingSize::default();
for (i, glob) in entry.globs.iter().enumerate() {
if !glob.visibility.visible_from(&entry.module, from) {
continue;
}
let targets = match self.glob_targets(t, id, i) {
Ok(targets) => targets,
Err(refusal) => return GlobRead::Answered(Head::PastCap(refusal)),
};
for target in targets {
if let Err(refusal) = size.add(&target) {
return GlobRead::Answered(Head::PastCap(refusal));
}
let scopes = path_within(&target, "crate")
.then(|| self.modules.get(&target))
.flatten();
if let Some(scopes) = scopes {
let into = scopes
.iter()
.map(|&(t, s)| graph.node(t, s, &entry.module))
.collect();
edges.push(GlobEdge::Into {
quote: format!("use {}::*", glob.written),
target,
into,
});
} else {
edges.push(GlobEdge::Foreign(format!("{target}::{head}")));
}
}
}
GlobRead::Globs { own: None, edges }
}
fn lookup_in_module(
&self,
module: &str,
head: &str,
ns: Namespace,
from: &str,
walk: &mut Walk,
) -> Head {
let scopes = match self.blocks.get(module) {
Some(block) => std::slice::from_ref(block),
None => self.modules.get(module).map_or(&[][..], Vec::as_slice),
};
joined(
scopes
.iter()
.map(|&(t, s)| self.scope_lookup(t, s, head, ns, from, walk))
.collect::<Vec<_>>(),
)
}
fn binding_holds(
&self,
t: usize,
scope: u32,
name: &str,
binding: &Binding,
ns: Namespace,
walk: &mut Walk,
) -> Result<bool, String> {
let Binding::Import {
written,
module_only,
..
} = binding
else {
return Ok(ns != Namespace::Value);
};
if *module_only {
return Ok(ns != Namespace::Value);
}
if self.import_presence(t, scope, name, written, ns, walk)? != Presence::Absent {
return Ok(true);
}
Ok(self.import_presence(t, scope, name, written, ns.other(), walk)? == Presence::Absent)
}
fn import_presence(
&self,
t: usize,
scope: u32,
name: &str,
written: &str,
ns: Namespace,
walk: &mut Walk,
) -> Result<Presence, String> {
let key = (t, scope, name.to_string(), written.to_string(), ns);
if let Some(presence) = self.presence.borrow().get(&key) {
return Ok(*presence);
}
let module = &self.tables[t].scopes[scope as usize].module;
let cuts = walk.cuts;
walk.enter(
(t, scope, name.to_string()),
format!("use {written}"),
module,
)?;
let presence = match self.name_raw(
t,
scope,
written,
PathSite::Use,
ns,
&mut Vec::new(),
walk,
false,
) {
Named::Paths(paths) => paths.iter().try_fold(Presence::Absent, |most, path| {
let presence = if path_within(path, "crate") {
self.denote_in(path, ns, walk, false, None)
.map(|denoted| denoted.presence)
} else {
Ok(Presence::Unknown)
};
presence.map(|presence| most.max(presence))
}),
Named::External(_) | Named::Unbound { .. } => Ok(Presence::Unknown),
Named::Local => Ok(Presence::Known),
Named::Invalid => Ok(Presence::Absent),
Named::PastCap(refusal) => Err(refusal),
};
walk.leave();
if let (Ok(presence), true) = (&presence, walk.cuts == cuts) {
self.presence.borrow_mut().insert(key, *presence);
}
presence
}
pub(super) fn binding_names(
&self,
t: usize,
scope: u32,
name: &str,
binding: &Binding,
ns: Namespace,
walk: &mut Walk,
) -> BindingNames {
let (written, site, ns, quote) = match binding {
Binding::Import { written, .. } => {
(written, PathSite::Use, ns, format!("use {written}"))
}
Binding::Alias { written, .. } => (
written,
PathSite::Expr,
Namespace::Type,
format!("type {name} = {written}"),
),
};
let module = &self.tables[t].scopes[scope as usize].module;
if let Err(refusal) = walk.enter((t, scope, name.to_string()), quote, module) {
return BindingNames::PastCap(refusal);
}
let mut through = Vec::new();
let named = self.name_raw(t, scope, written, site, ns, &mut through, walk, false);
walk.leave();
match named {
Named::Paths(paths) => BindingNames::Paths(paths, through),
Named::External(path) => BindingNames::Paths(vec![path], through),
Named::Unbound { head, rest, also } => BindingNames::Paths(
self.crate_named(head, &rest)
.into_iter()
.chain(also)
.collect(),
through,
),
Named::Local => BindingNames::Local,
Named::Invalid => BindingNames::Paths(Vec::new(), through),
Named::PastCap(refusal) => BindingNames::PastCap(refusal),
}
}
pub(super) fn glob_targets(
&self,
t: usize,
scope: u32,
i: usize,
) -> Result<Vec<String>, String> {
let key = (t, scope, i);
if let Some(all) = self.globs.borrow().as_ref() {
return all.get(&key).cloned().unwrap_or_else(|| Ok(Vec::new()));
}
if self.reading_globs.borrow().is_some() {
if *self.reading_glob.borrow() == Some(key) {
self.read_itself.set(true);
return Ok(Vec::new());
}
return self.last_read(key);
}
let every: Vec<GlobKey> = self
.tables
.iter()
.enumerate()
.flat_map(|(t, table)| {
table
.scopes
.iter()
.enumerate()
.flat_map(move |(id, entry)| {
let id = u32::try_from(id).expect("scope table exceeds u32");
(0..entry.globs.len()).map(move |i| (t, id, i))
})
})
.collect();
*self.reading_globs.borrow_mut() = Some(GlobTargets::new());
let passes = MAX_RESOLUTION_CHAIN.max(2 * (every.len() + 1));
let mut settled = false;
for pass in 0..passes {
let mut changed = false;
let order: Box<dyn Iterator<Item = &GlobKey>> = if pass % 2 == 0 {
Box::new(every.iter())
} else {
Box::new(every.iter().rev())
};
for &glob in order {
changed |= self.read_in_pass(glob);
}
if !changed {
settled = true;
break;
}
}
let read = self
.reading_globs
.borrow_mut()
.take()
.expect("the glob readings are set before the passes");
let all: GlobTargets = if settled {
read
} else {
let refusal = format!(
"cannot judge a compilation unit whose globs do not settle on what they name within {passes} passes"
);
every
.iter()
.map(|&key| (key, Err(refusal.clone())))
.collect()
};
self.forget_readings();
let found = all.get(&key).cloned().unwrap_or_else(|| Ok(Vec::new()));
*self.globs.borrow_mut() = Some(all);
found
}
fn last_read(&self, key: GlobKey) -> Result<Vec<String>, String> {
self.reading_globs
.borrow()
.as_ref()
.and_then(|all| all.get(&key).cloned())
.unwrap_or_else(|| Ok(Vec::new()))
}
fn read_in_pass(&self, key: GlobKey) -> bool {
self.forget_readings();
*self.reading_glob.borrow_mut() = Some(key);
self.read_itself.set(false);
let reading = self.read_glob(key.0, key.1, key.2).and_then(|paths| {
let mut size = ReadingSize::default();
for path in &paths {
size.add(path)?;
}
Ok(paths)
});
*self.reading_glob.borrow_mut() = None;
if self.read_itself.get() {
self.forget_readings();
}
if reading == self.last_read(key) {
return false;
}
if let Some(all) = self.reading_globs.borrow_mut().as_mut() {
all.insert(key, reading);
}
true
}
fn forget_readings(&self) {
self.named.borrow_mut().clear();
self.denoted.borrow_mut().clear();
self.looked.borrow_mut().clear();
self.presence.borrow_mut().clear();
}
fn read_glob(&self, t: usize, scope: u32, i: usize) -> Result<Vec<String>, String> {
let entry = &self.tables[t].scopes[scope as usize];
let written = &entry.globs[i].written;
let mut walk = Walk::default();
walk.enter(
(t, scope, format!("*{i}")),
format!("use {written}::*"),
&entry.module,
)?;
let named = self.name_raw(
t,
scope,
written,
PathSite::Use,
Namespace::Type,
&mut Vec::new(),
&mut walk,
false,
);
match named {
Named::Paths(paths) => self.read_glob_paths(&paths, Vec::new(), &mut walk),
Named::External(path) => Ok(vec![path]),
Named::Unbound { head, rest, also } => self.read_glob_paths(
&also,
self.crate_named(head, &rest).into_iter().collect(),
&mut walk,
),
Named::Local | Named::Invalid => Ok(Vec::new()),
Named::PastCap(refusal) => Err(refusal),
}
}
fn read_glob_paths(
&self,
paths: &[String],
mut found: Vec<String>,
walk: &mut Walk,
) -> Result<Vec<String>, String> {
let mut size = ReadingSize::default();
for path in &found {
size.add(path)?;
}
for path in paths {
for path in self
.denote_in(path, Namespace::Type, walk, false, None)?
.paths
{
size.add(&path)?;
found.push(path);
}
}
Ok(found)
}
fn denote_in(
&self,
path: &str,
ns: Namespace,
walk: &mut Walk,
candidates: bool,
hazard: Option<(&str, bool)>,
) -> Result<Denoted, String> {
ReadingSize::default().add(path)?;
let Some(rest) = crate_rooted(path) else {
return Ok(Denoted {
paths: vec![path.to_string()],
beside: Vec::new(),
presence: Presence::Unknown,
terminal_reaches: false,
});
};
let mut reading = Reading::new(rest, candidates, hazard);
while let Some((module, rest, chain)) = reading.next()? {
self.read_branch(&mut reading, module, &rest, chain, ns, walk)?;
}
Ok(reading.denoted())
}
fn read_branch(
&self,
reading: &mut Reading,
module: String,
rest: &[String],
chain: Vec<Link>,
ns: Namespace,
walk: &mut Walk,
) -> Result<(), String> {
let Some((segment, after)) = rest.split_first() else {
reading.find(module)?;
reading.raise(Presence::Known);
return Ok(());
};
let here = format!("{module}::{segment}");
if is_block_segment(segment) {
if let Some((name, beyond)) = after.split_first() {
let file_module = format!("{here}::{name}");
if !self.blocks.contains_key(&here) && self.modules.contains_key(&file_module) {
reading.step(file_module, beyond.to_vec(), chain);
return Ok(());
}
}
reading.step(here, after.to_vec(), chain);
return Ok(());
}
let segment_ns = if after.is_empty() {
ns
} else {
Namespace::Type
};
match self.lookup_in_module(&module, segment, segment_ns, &module, walk) {
Head::Candidates {
bound,
declared,
through,
foreign,
..
} => {
for path in through {
reading.find(with_rest(path, after))?;
}
if !foreign.is_empty() {
reading.terminal(foreign, after)?;
reading.raise(Presence::Unknown);
}
for declaration in declared {
match declaration {
Declared::Module(inner) if !after.is_empty() => {
reading.branch(inner, after.to_vec(), chain.clone())?;
}
Declared::Module(path) | Declared::Item(path) => {
reading.find(with_rest(path, after))?;
reading.raise(Presence::Known);
}
}
}
if !bound.is_empty() {
reading.follow_bound(&module, segment, after, chain, bound, walk)?;
}
}
Head::Foreign(paths) => {
reading.find(with_rest(here, after))?;
reading.terminal(paths, after)?;
reading.raise(Presence::Unknown);
}
Head::PastCap(refusal) => return Err(refusal),
Head::Local => {
reading.find(with_rest(here, after))?;
reading.raise(Presence::Known);
}
Head::Unbound => {
reading.find(with_rest(here, after))?;
if !after.is_empty() || self.may_generate_items(&module) {
reading.raise(Presence::Unknown);
}
}
}
Ok(())
}
fn may_generate_items(&self, module: &str) -> bool {
self.modules
.get(module)
.into_iter()
.flatten()
.any(|&(t, s)| self.tables[t].scopes[s as usize].macro_items)
}
}
fn crate_rooted(path: &str) -> Option<Vec<String>> {
if path == "crate" {
return Some(Vec::new());
}
path.strip_prefix("crate::")
.map(|rest| rest.split("::").map(str::to_string).collect())
}
type Branch = (String, Vec<String>, Vec<Link>);
struct Reading<'h> {
work: Vec<Branch>,
seen: BTreeSet<(String, Vec<String>)>,
found: Vec<String>,
beside: Vec<String>,
presence: Presence,
terminal_reaches: bool,
size: ReadingSize,
candidates: bool,
hazard: Option<(&'h str, bool)>,
}
impl<'h> Reading<'h> {
fn new(rest: Vec<String>, candidates: bool, hazard: Option<(&'h str, bool)>) -> Self {
Reading {
work: vec![("crate".to_string(), rest, Vec::new())],
seen: BTreeSet::new(),
found: Vec::new(),
beside: Vec::new(),
presence: Presence::Absent,
terminal_reaches: false,
size: ReadingSize::default(),
candidates,
hazard,
}
}
fn next(&mut self) -> Result<Option<Branch>, String> {
while let Some((module, rest, chain)) = self.work.pop() {
self.size.add(&module)?;
self.size.bytes = self
.size
.bytes
.saturating_add(rest.iter().map(String::len).sum::<usize>());
self.size.check()?;
if self.size.paths.saturating_add(self.work.len()) > MAX_RESOLUTION_PATHS {
return Err(width_refusal());
}
if self.seen.insert((module.clone(), rest.clone())) {
return Ok(Some((module, rest, chain)));
}
}
Ok(None)
}
fn find(&mut self, path: String) -> Result<(), String> {
self.size.add(&path)?;
self.found.push(path);
Ok(())
}
fn branch(
&mut self,
module: String,
rest: Vec<String>,
chain: Vec<Link>,
) -> Result<(), String> {
self.size.add(&with_rest(module.clone(), &rest))?;
self.work.push((module, rest, chain));
Ok(())
}
fn step(&mut self, module: String, rest: Vec<String>, chain: Vec<Link>) {
self.work.push((module, rest, chain));
}
fn raise(&mut self, presence: Presence) {
self.presence = self.presence.max(presence);
}
fn terminal(&mut self, paths: Vec<String>, after: &[String]) -> Result<(), String> {
if !self.candidates && self.hazard.is_none() {
return Ok(());
}
for path in paths {
let path = with_rest(path, after);
self.size.add(&path)?;
if let Some((prefix, ancestors)) = self.hazard {
self.terminal_reaches |=
path_within(&path, prefix) || (ancestors && path_within(prefix, &path));
}
if self.candidates {
self.beside.push(path);
}
}
Ok(())
}
fn follow_bound(
&mut self,
module: &str,
segment: &str,
after: &[String],
chain: Vec<Link>,
bound: Vec<Bound>,
walk: &mut Walk,
) -> Result<(), String> {
self.find(with_rest(format!("{module}::{segment}"), after))?;
if chain
.iter()
.any(|(m, name, _)| m == module && name == segment)
{
walk.cuts += 1;
self.raise(Presence::Unknown);
return Ok(());
}
if chain.len() >= MAX_RESOLUTION_CHAIN {
return Err(chain_refusal(&chain[0].2, &chain[0].0));
}
for (target, quote) in bound {
let target = with_rest(target, after);
match crate_rooted(&target) {
Some(rest) => {
let mut chain = chain.clone();
chain.push((module.to_string(), segment.to_string(), quote));
self.branch("crate".to_string(), rest, chain)?;
}
None => {
self.size.add(&target)?;
self.find(target)?;
self.raise(Presence::Unknown);
}
}
}
Ok(())
}
fn denoted(self) -> Denoted {
Denoted {
paths: sorted_unique(self.found),
beside: sorted_unique(self.beside),
presence: self.presence,
terminal_reaches: self.terminal_reaches,
}
}
}
fn binding_quote(name: &str, binding: &Binding) -> String {
match binding {
Binding::Import { written, .. } => format!("use {written}"),
Binding::Alias { written, .. } => format!("type {name} = {written}"),
}
}
type Link = (String, String, String);
fn joined(heads: impl IntoIterator<Item = Head>) -> Head {
let (mut bound, mut declared, mut through, mut alone, mut foreign, mut local) = (
Vec::new(),
Vec::new(),
Vec::new(),
Vec::new(),
Vec::new(),
false,
);
let mut refused: Option<String> = None;
let mut open = false;
let mut size = ReadingSize::default();
for head in heads {
if let Err(refusal) = size.head(&head) {
return Head::PastCap(refusal);
}
match head {
Head::PastCap(refusal) => refused = least(refused, refusal),
Head::Candidates {
bound: b,
declared: d,
through: p,
heads: g,
foreign: f,
open: o,
} => {
bound.extend(b);
declared.extend(d);
through.extend(p);
alone.extend(g);
foreign.extend(f);
open |= o;
}
Head::Foreign(paths) => foreign.extend(paths),
Head::Local => local = true,
Head::Unbound => {}
}
}
if let Some(refusal) = refused {
Head::PastCap(refusal)
} else if !bound.is_empty() || !declared.is_empty() {
declared.sort();
declared.dedup();
Head::Candidates {
bound: sorted_unique(bound),
declared,
through: sorted_unique(through),
heads: sorted_unique(alone),
foreign: sorted_unique(foreign),
open,
}
} else if local {
Head::Local
} else if !foreign.is_empty() {
Head::Foreign(sorted_unique(foreign))
} else {
Head::Unbound
}
}
pub(super) fn least(held: Option<String>, refusal: String) -> Option<String> {
Some(match held {
Some(held) if held <= refusal => held,
_ => refusal,
})
}
fn sorted_unique<T: Ord>(paths: impl IntoIterator<Item = T>) -> Vec<T> {
let mut paths: Vec<T> = paths.into_iter().collect();
paths.sort();
paths.dedup();
paths
}
#[cfg(test)]
mod tests {
use super::super::token_tree::{Edition, TokenTree};
use super::*;
#[test]
fn mutually_globbed_gated_modules_have_bounded_reading_work() {
for (count, dense) in [(8, true), (16, true), (32, false)] {
let mut source = String::new();
for i in 0..count {
source.push_str(&format!("#[cfg(unix)] pub mod m{i} {{\n"));
for j in 0..count {
if i != j && (dense || j == (i + 1) % count || j == (i + count - 1) % count) {
source.push_str(&format!("pub use crate::m{j}::*;\n"));
}
}
if i == 0 {
source.push_str("pub fn f() {}\n");
}
source.push_str("}\n");
}
source.push_str("pub use m0::*;\npub fn g() { f(); }\n");
let tree = TokenTree::lex(&source, Edition::Rust2021);
let token = (0..tree.len())
.find(|&i| tree.start(i) >= source.find("f();").unwrap())
.unwrap();
let scopes = CrateScopes::new(
vec![ScopeTable::build(&tree, "crate", 0)],
Edition::Rust2021,
);
let answer = scopes.name(
0,
scopes.table(0).scope_at(token),
"f",
PathSite::Expr,
Namespace::Value,
);
assert!(
matches!(&answer, Named::Paths(paths) if paths.iter().any(|p| p == "crate::m0::f")),
"{answer:?}"
);
let reads = scopes.scope_reads.get();
assert!(
reads <= 32 * count * count * count,
"{count} modules read {reads} scopes"
);
}
}
#[test]
fn foreign_candidates_beside_local_ones_are_terminal_for_every_reader() {
let source = "pub mod a { pub struct V; } pub mod s { #[cfg(any())] pub use crate::a::*; #[cfg(not(any()))] pub use std::process::*; }";
let tree = TokenTree::lex(source, Edition::Rust2021);
let scopes = CrateScopes::new(
vec![ScopeTable::build(&tree, "crate", 0)],
Edition::Rust2021,
);
assert!(
scopes
.denote("crate::s::V", Namespace::Type)
.unwrap()
.contains(&"std::process::V".to_string())
);
assert!(
!scopes
.readable_paths("crate::s::V", Namespace::Type)
.unwrap()
.contains(&"std::process::V".to_string())
);
for ancestors in [false, true] {
let (paths, reaches) = scopes
.hazard_paths("crate::s::V", Namespace::Type, "std::process", ancestors)
.unwrap();
assert!(!paths.contains(&"std::process::V".to_string()));
assert!(reaches);
}
assert_eq!(
scopes
.denote_in(
"crate::s::V",
Namespace::Type,
&mut Walk::default(),
false,
None
)
.unwrap()
.presence,
Presence::Known
);
}
#[test]
fn distinct_denotations_share_a_retention_budget() {
for limits in [
(2, usize::MAX, usize::MAX),
(usize::MAX, 2, usize::MAX),
(usize::MAX, usize::MAX, 24),
] {
let scopes = CrateScopes::new(Vec::new(), Edition::Rust2021);
scopes.denoted.borrow_mut().limits = limits;
for path in ["std::a", "std::b"] {
assert_eq!(scopes.denote(path, Namespace::Type).unwrap(), vec![path]);
assert_eq!(scopes.denote(path, Namespace::Type).unwrap(), vec![path]);
}
let error = scopes.denote("std::c", Namespace::Type).unwrap_err();
assert!(error.contains("cannot judge a denotation memo"), "{error}");
assert_eq!(scopes.denoted.borrow().answers.len(), 2);
scopes.forget_readings();
assert_eq!(
scopes.denote("std::c", Namespace::Type).unwrap(),
vec!["std::c"]
);
}
}
#[test]
fn denotation_retention_charges_terminal_candidates_and_hazard_keys() {
let source = "pub mod a { pub struct V; } pub mod s { #[cfg(any())] pub use crate::a::*; #[cfg(not(any()))] pub use std::process::*; }";
let tree = TokenTree::lex(source, Edition::Rust2021);
let scopes = CrateScopes::new(
vec![ScopeTable::build(&tree, "crate", 0)],
Edition::Rust2021,
);
scopes.denoted.borrow_mut().limits = (usize::MAX, 1, usize::MAX);
assert!(
scopes
.denote("crate::s::V", Namespace::Type)
.unwrap_err()
.contains("denotation memo")
);
assert!(scopes.denoted.borrow().answers.is_empty());
let scopes = CrateScopes::new(Vec::new(), Edition::Rust2021);
scopes.denoted.borrow_mut().limits = (usize::MAX, usize::MAX, 12);
assert!(
scopes
.hazard_paths("std::a", Namespace::Type, "std", false)
.unwrap_err()
.contains("denotation memo")
);
assert!(scopes.denoted.borrow().answers.is_empty());
let mut memo = DenotationMemo {
limits: (usize::MAX, usize::MAX, 6),
..Default::default()
};
assert!(
memo.insert(
("std::a".to_string(), Namespace::Type, false, None),
Err("refusal".to_string())
)
.is_err()
);
assert!(memo.answers.is_empty());
}
#[test]
fn resolution_width_and_path_bytes_refuse_before_growth() {
let paths = (0..=MAX_RESOLUTION_PATHS).map(|i| Head::Foreign(vec![format!("dep::p{i}")]));
assert!(matches!(joined(paths), Head::PastCap(message) if message == width_refusal()));
let tree = TokenTree::lex("", Edition::Rust2021);
let scopes = CrateScopes::new(
vec![ScopeTable::build(&tree, "crate", 0)],
Edition::Rust2021,
);
assert_eq!(
scopes.denote(&"x".repeat(MAX_RESOLUTION_BYTES + 1), Namespace::Type),
Err(width_refusal())
);
let paths = vec!["std::process".to_string(); MAX_RESOLUTION_PATHS + 1];
assert_eq!(
scopes.denote_all(Vec::new(), &paths, Namespace::Type),
Err(width_refusal())
);
assert_eq!(
scopes.read_glob_paths(&paths, Vec::new(), &mut Walk::default()),
Err(width_refusal())
);
let paths: Vec<String> = (0..MAX_RESOLUTION_PATHS)
.map(|i| format!("dep::p{i}"))
.collect();
let count = MAX_GLOB_GRAPH_PATHS / MAX_RESOLUTION_PATHS + 1;
let graph = GlobGraph {
nodes: (0..count).map(|i| (i, 0, "crate".to_string())).collect(),
index: HashMap::new(),
reads: (0..count)
.map(|_| GlobRead::Answered(Head::Foreign(paths.clone())))
.collect(),
};
assert!(
matches!(graph.settle("f"), Err(message) if message.contains("glob graph holding more than"))
);
let mut size = ReadingSize::default();
assert!(size.add(&"x".repeat(MAX_RESOLUTION_BYTES)).is_ok());
assert_eq!(size.add("x"), Err(width_refusal()));
}
fn ring_reading(links: usize) -> (usize, bool) {
let mut source = String::from("pub mod forbidden { pub fn f() {} }\n");
for i in 0..links {
source.push_str(&format!(
"pub mod m{i} {{ #[cfg(unix)] pub use crate::m{}::f; #[cfg(not(unix))] pub use crate::forbidden::f; }}\n",
i + 1
));
}
source.push_str(&format!(
"pub mod m{links} {{ #[cfg(unix)] pub use crate::forbidden::f; #[cfg(not(unix))] pub use crate::m0::f; }}\n\
pub fn g() {{ m0::f(); }}\n"
));
let tree = TokenTree::lex(&source, Edition::Rust2021);
let offset = source.find("m0::f()").unwrap();
let token = (0..tree.len()).find(|&i| tree.start(i) >= offset).unwrap();
let scopes = CrateScopes::new(
vec![ScopeTable::build(&tree, "crate", 0)],
Edition::Rust2021,
);
let named = scopes.name(
0,
scopes.table(0).scope_at(token),
"m0::f",
PathSite::Expr,
Namespace::Value,
);
let reaches = matches!(&named, Named::Paths(paths) if paths.iter().any(|p| p == "crate::forbidden::f"));
(scopes.scope_reads.get(), reaches)
}
#[test]
fn a_cfg_closed_re_export_ring_is_read_in_time_exponential_in_its_length() {
let (short, short_reaches) = ring_reading(8);
let (long, long_reaches) = ring_reading(11);
assert!(
short_reaches && long_reaches,
"both rings name crate::forbidden::f"
);
assert!(
long >= short * 4,
"eleven links read {long} scopes and eight {short}: the ring no longer doubles per link, so the declared \
bound a-cfg-closed-re-export-ring-is-read-in-time-exponential-in-its-length no longer holds and should be \
retired"
);
}
fn resolved(source: &str, at: &str, head: &str, ns: Namespace) -> Option<String> {
let tree = TokenTree::lex(source, Edition::Rust2018);
let offset = source.find(at).unwrap();
let token = (0..tree.len()).find(|&i| tree.start(i) >= offset).unwrap();
let table = ScopeTable::build(&tree, "crate::core", 0);
let root = TokenTree::lex("pub mod core;\n", Edition::Rust2018);
let root = ScopeTable::build(&root, "crate", 1);
let scopes = CrateScopes::new(vec![table, root], Edition::Rust2018);
match scopes.name(0, scopes.table(0).scope_at(token), head, PathSite::Expr, ns) {
Named::Paths(paths) => Some(paths.join(" | ")),
Named::Unbound { also, .. } if !also.is_empty() => Some(also.join(" | ")),
Named::Local => Some("<local>".to_string()),
_ => None,
}
}
#[test]
fn written_root_classifies_each_root_once() {
let bare = |head: &str, rest: &[&str]| WrittenRoot::Bare {
head: head.to_string(),
rest: rest.iter().map(|s| s.to_string()).collect(),
};
let from_root = |head: &str, rest: &[&str]| WrittenRoot::FromCrateRoot {
head: head.to_string(),
rest: rest.iter().map(|s| s.to_string()).collect(),
};
let extern_ = |head: &str, rest: &[&str]| WrittenRoot::Extern {
head: head.to_string(),
rest: rest.iter().map(|s| s.to_string()).collect(),
};
let crate_ = |path: &str| WrittenRoot::Crate(path.to_string());
for (written, module, site, edition, expected) in [
(
"std::time",
"crate::core",
PathSite::Expr,
Edition::Rust2018,
bare("std", &["time"]),
),
(
"::core::time",
"crate::core",
PathSite::Expr,
Edition::Rust2018,
extern_("core", &["time"]),
),
(
"::alloc::vec",
"crate::core",
PathSite::Use,
Edition::Rust2015,
from_root("alloc", &["vec"]),
),
(
"crate::a::X",
"crate::core",
PathSite::Expr,
Edition::Rust2018,
crate_("crate::a::X"),
),
(
"super::X",
"crate::core::t",
PathSite::Use,
Edition::Rust2018,
crate_("crate::core::X"),
),
(
"self::X",
"crate::core",
PathSite::Expr,
Edition::Rust2018,
crate_("crate::core::X"),
),
(
"super::super::X",
"crate",
PathSite::Expr,
Edition::Rust2018,
WrittenRoot::Invalid,
),
(
"::self::X",
"crate::core",
PathSite::Expr,
Edition::Rust2018,
WrittenRoot::Invalid,
),
(
"::super::X",
"crate::core",
PathSite::Use,
Edition::Rust2015,
WrittenRoot::Invalid,
),
(
"::md5x::f",
"crate::core",
PathSite::Expr,
Edition::Rust2018,
extern_("md5x", &["f"]),
),
(
"::md5x::f",
"crate::core",
PathSite::Expr,
Edition::Rust2015,
from_root("md5x", &["f"]),
),
(
"clock::now",
"crate::core",
PathSite::Use,
Edition::Rust2015,
from_root("clock", &["now"]),
),
(
"clock::now",
"crate::core",
PathSite::Expr,
Edition::Rust2015,
bare("clock", &["now"]),
),
(
"clock::now",
"crate::core",
PathSite::Use,
Edition::Rust2018,
bare("clock", &["now"]),
),
(
"r#try::f",
"crate::core",
PathSite::Expr,
Edition::Rust2018,
bare("try", &["f"]),
),
(
"",
"crate::core",
PathSite::Expr,
Edition::Rust2018,
WrittenRoot::Invalid,
),
] {
assert_eq!(
written_root(written, module, site, edition),
expected,
"`{written}` at {module}, {edition:?}"
);
}
}
#[test]
fn a_block_use_binds_its_whole_block_and_nothing_outside() {
let source = "mod a { pub struct X; }\nmod b { pub struct X; }\nuse crate::core::a::X;\nfn h() { X::fa(); }\nfn g() { X::early(); use crate::core::b::X; X::fb(); }\nfn k() { X::late(); }\n";
for (at, expected) in [
("X::fa", "crate::core::a::X"),
("X::early", "crate::core::b::X"),
("X::fb", "crate::core::b::X"),
("X::late", "crate::core::a::X"),
] {
assert_eq!(
resolved(source, at, "X", Namespace::Type).as_deref(),
Some(expected),
"{at}"
);
}
}
#[test]
fn a_block_item_shadows_in_its_namespace_only() {
let source = "use std::process::Command;\nfn g() { struct Command {} let _ = Command::new(); let _ = Command(); }\n";
assert_eq!(
resolved(source, "Command::new", "Command", Namespace::Type).as_deref(),
Some("<local>")
);
assert_eq!(
resolved(source, "Command()", "Command", Namespace::Value).as_deref(),
Some("std::process::Command"),
"a braced struct names no value"
);
}
#[test]
fn member_bodies_bind_nothing_and_pass_through_bodies_bind_outward() {
let source = "use std::process::Command;\nimpl S { const Command: u8 = 0; fn f() { Command::a(); } }\nenum E { Command }\nfn g() { extern \"C\" { fn Command(); } Command(); }\ncfg_if! { if #[cfg(unix)] { use crate::u::Y; } else { use crate::w::Y; } }\nfn y() { Y::b(); }\n";
assert_eq!(
resolved(source, "Command::a", "Command", Namespace::Type).as_deref(),
Some("std::process::Command")
);
assert_eq!(
resolved(source, "Command();", "Command", Namespace::Value).as_deref(),
Some("<local>"),
"an extern block's item belongs to the enclosing block"
);
assert_eq!(
resolved(source, "Y::b", "Y", Namespace::Type).as_deref(),
Some("crate::u::Y | crate::w::Y"),
"each cfg_if arm's use binds at module scope, and both are candidates"
);
}
#[test]
fn a_keyword_in_a_type_heads_no_item() {
let source = "use std::process::Command;\nfn g() -> impl Sized { let _: &'static str = \"\"; Command::new() }\n";
assert_eq!(
resolved(source, "Command::new", "Command", Namespace::Type).as_deref(),
Some("std::process::Command")
);
}
}