Skip to main content

vvv_engine/graph/
mod.rs

1//! What vvv knows about a tree, and the questions commands ask of it.
2//!
3//! The store: every file, which language claims it, its text, and — once
4//! asked — its facts, each kept as long as the file's [`Stamp`] stays the
5//! same; per language, the [`Project`] its layout resolves paths against.
6//! One walk serves everything a command needs. Kept for a session, the
7//! graph re-reads only files that changed and parses a file once however
8//! many questions are asked of it; built per call, it is the workspace read
9//! once.
10//!
11//! The questions: what a search finds, what declares a name, what a file imports and who imports a module. Each
12//! is answered here, through a [`Namespace`], so a command composes answers
13//! instead of fetching languages, layouts and projects itself.
14
15mod candidate;
16mod fragment;
17mod import_bindings;
18mod module_navigation;
19mod namespace;
20mod navigation;
21mod navigation_scope;
22pub(crate) mod query_snapshot;
23mod references;
24mod scope;
25
26use std::collections::{BTreeSet, HashMap, HashSet};
27use std::path::{Path, PathBuf};
28use std::sync::Arc;
29use std::time::{Duration, Instant};
30
31use rayon::prelude::*;
32use vvv_core::{
33    Address, FileSet, Language, LanguageId, LanguageRegistry, Name, Oracle, Package, Packages,
34    Project, Query, Role, SourceText,
35};
36
37pub use candidate::Candidate;
38pub use fragment::{Declared, Edge, Fragment, Node, Structure};
39pub use namespace::Namespace;
40use references::{Declaration, Target};
41pub use references::{DeclarationSite, Evidence};
42pub use scope::Scope;
43
44use crate::{
45    Dep, EngineError, Importer, Match, Occurrence, Reach, Reason, ReferencesQuery, Search, Skipped,
46    Stamp, Workspace,
47};
48
49pub struct Graph {
50    pub(crate) cancellation: Option<crate::ReadCancellation>,
51    workspace: Workspace,
52    languages: LanguageRegistry,
53    /// Every file of the last walk, absolute, in path order. Only a project
54    /// needs them relative and as a set, so that is built on demand.
55    walked: Vec<PathBuf>,
56    /// When that walk happened; `None` once something may have changed it.
57    walked_at: Option<Instant>,
58    /// Every claimed file, in path order.
59    entries: Vec<Entry>,
60    /// The workspace as a language's layout sees it, built from the last
61    /// walk the first time that language asks; a search never pays for it.
62    /// A project equal to the previous build keeps its allocation, so
63    /// fragments resolved against it stay valid.
64    projects: HashMap<LanguageId, Arc<Project>>,
65    module_sources:
66        HashMap<LanguageId, Arc<std::collections::BTreeMap<PathBuf, Arc<candidate::SourceFacts>>>>,
67    /// A second opinion for tokens syntax cannot place, when the host has
68    /// one; asked after the scope, never instead of it.
69    oracle: Option<Arc<dyn Oracle>>,
70    /// The last build of each language's project, to tell a refresh that
71    /// changed nothing about the project from one that did.
72    previous: HashMap<LanguageId, Arc<Project>>,
73    /// Manifest snapshots retained with each captured project for navigation validation.
74    project_sources: HashMap<LanguageId, Vec<crate::SourceFile>>,
75}
76
77struct Entry {
78    /// Absolute, as walked.
79    path: PathBuf,
80    /// `None` when the model will not be asked again, so nothing was stamped.
81    stamp: Option<Stamp>,
82    candidate: Candidate,
83}
84
85/// How long an [`Engine`](crate::Engine) keeps its graph.
86#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
87pub enum Retention {
88    /// Read the workspace afresh for every question: right for a one-shot
89    /// command, whose single question has to read the tree anyway.
90    #[default]
91    PerCall,
92    /// Keep files and facts between questions and re-read only what changed:
93    /// right for a session that asks the same tree over and over. Within
94    /// `trust` of the last walk it does not even look — a burst of
95    /// keystrokes walks a large tree once, not per key — except after the
96    /// engine itself wrote, or was told the tree changed.
97    Session { trust: Duration },
98}
99
100impl Retention {
101    /// A session that checks the tree before every question.
102    pub const fn session() -> Self {
103        Self::Session {
104            trust: Duration::ZERO,
105        }
106    }
107
108    /// A session that trusts its last walk for `trust`.
109    pub const fn trusting(self, trust: Duration) -> Self {
110        match self {
111            Self::PerCall => Self::PerCall,
112            Self::Session { .. } => Self::Session { trust },
113        }
114    }
115}
116
117impl Graph {
118    pub fn new(workspace: Workspace, languages: LanguageRegistry) -> Self {
119        Self {
120            cancellation: None,
121            workspace,
122            languages,
123            walked: Vec::new(),
124            walked_at: None,
125            oracle: None,
126            entries: Vec::new(),
127            projects: HashMap::new(),
128            module_sources: HashMap::new(),
129            previous: HashMap::new(),
130            project_sources: HashMap::new(),
131        }
132    }
133
134    pub(crate) fn check_read(&self) -> Result<(), EngineError> {
135        self.cancellation
136            .as_ref()
137            .map_or(Ok(()), crate::ReadCancellation::check)
138    }
139    /// Walk the tree; load files that appeared or changed, forget files that
140    /// vanished, keep the rest. A graph kept for a session stamps what it
141    /// loads so the next refresh can tell; one built per call does not.
142    pub fn refresh(&mut self, retention: Retention) -> Result<(), EngineError> {
143        self.check_read()?;
144        if let Retention::Session { trust } = retention
145            && self.walked_at.is_some_and(|at| at.elapsed() < trust)
146        {
147            return Ok(());
148        }
149        let walked = self.workspace.files()?;
150        self.check_read()?;
151        let claimed: Vec<(&Path, Arc<dyn Language>)> = walked
152            .iter()
153            .filter_map(|abs| Some((abs.as_path(), self.languages.for_path(abs)?)))
154            .collect();
155
156        let before = std::mem::take(&mut self.entries);
157        let vfs = self.workspace.vfs();
158        let workspace = &self.workspace;
159        let stamping = matches!(retention, Retention::Session { .. });
160        let now: Vec<Entry> = claimed
161            .into_par_iter()
162            .map(|(abs, language)| {
163                self.check_read()?;
164                let stamp = stamping.then(|| vfs.stamp(abs)).transpose()?;
165                let known = stamp.and_then(|stamp| {
166                    before
167                        .binary_search_by(|e| e.path.as_path().cmp(abs))
168                        .ok()
169                        .map(|i| &before[i])
170                        .filter(|e| e.stamp == Some(stamp))
171                });
172                let candidate = match known {
173                    Some(known) => known.candidate.clone(),
174                    None => Candidate::new(workspace.load(abs)?, language),
175                };
176                self.check_read()?;
177                Ok(Entry {
178                    path: abs.to_path_buf(),
179                    stamp,
180                    candidate,
181                })
182            })
183            .collect::<Result<_, EngineError>>()?;
184        self.entries = now;
185        self.module_sources.clear();
186        self.previous.extend(std::mem::take(&mut self.projects));
187        self.project_sources.clear();
188        self.walked = walked;
189        self.walked_at = Some(Instant::now());
190        Ok(())
191    }
192
193    /// The tree may have changed — the engine wrote to it, or was told so:
194    /// the next refresh walks whatever it was told to trust.
195    pub fn touched(&mut self) {
196        self.walked_at = None;
197    }
198
199    /// Consult `oracle` for the tokens the scope leaves unresolved.
200    pub fn with_oracle(mut self, oracle: Arc<dyn Oracle>) -> Self {
201        self.oracle = Some(oracle);
202        self
203    }
204
205    pub(crate) fn oracle(&self) -> Option<&Arc<dyn Oracle>> {
206        self.oracle.as_ref()
207    }
208
209    /// Every file `language` claims — any registered language when `None` —
210    /// in path order.
211    pub fn files(&self, language: Option<&LanguageId>) -> Vec<Candidate> {
212        self.entries
213            .iter()
214            .map(|e| &e.candidate)
215            .filter(|c| language.is_none_or(|id| &c.language() == id))
216            .cloned()
217            .collect()
218    }
219
220    /// The one claimed file at `path` (absolute or workspace-relative).
221    pub fn candidate(&self, path: &Path) -> Option<Candidate> {
222        let abs = self.workspace.absolute(path);
223        self.entries
224            .binary_search_by(|e| e.path.as_path().cmp(abs.as_path()))
225            .ok()
226            .map(|i| self.entries[i].candidate.clone())
227    }
228
229    /// The files of `language` that spell every one of `literals` as whole
230    /// tokens: the only ones a query built from those words can match.
231    pub fn containing(&self, language: Option<&LanguageId>, literals: &[&str]) -> Vec<Candidate> {
232        self.files(language)
233            .into_par_iter()
234            .filter(|c| c.contains_all(literals))
235            .collect()
236    }
237
238    /// The workspace as `language`'s layout sees it: the walk's files plus
239    /// the packages the layout's manifests declare. Built on first use after
240    /// a refresh; `None` when the language has no layout.
241    fn project_build(&mut self, language: &LanguageId) -> Option<Arc<Project>> {
242        if let Some(built) = self.projects.get(language) {
243            return Some(built.clone());
244        }
245        let language_impl = self.languages.get(language)?;
246        let layout = language_impl.layout()?;
247        let files: FileSet = self
248            .walked
249            .iter()
250            .map(|abs| self.workspace.absolute(abs))
251            .map(|abs| self.workspace.relative(&abs))
252            .collect();
253        let manifests: Vec<&Path> = files
254            .iter()
255            .filter(|p| {
256                p.file_name()
257                    .is_some_and(|n| layout.manifests().iter().any(|m| n == *m))
258            })
259            .collect();
260        let sources: Vec<_> = manifests
261            .into_par_iter()
262            .filter_map(|manifest| {
263                self.check_read().ok()?;
264                self.workspace.load(manifest).ok()
265            })
266            .collect();
267        self.check_read().ok()?;
268        let packages: Vec<Package> = sources
269            .iter()
270            .filter_map(|file| layout.package(file.path(), file.text()))
271            .collect();
272        self.project_sources.insert(language.clone(), sources);
273        let packages = Packages::new(packages);
274        let project = Project { packages, files };
275        // The same project as last time keeps its allocation: every fragment
276        // resolved against it is still right.
277        let built = match self.previous.remove(language) {
278            Some(last) if *last == project => last,
279            _ => Arc::new(project),
280        };
281        self.projects.insert(language.clone(), built.clone());
282        Some(built)
283    }
284
285    // ------------------------------------------------------------ questions
286
287    /// Every language this graph understands.
288    pub fn language_ids(&self) -> Vec<LanguageId> {
289        self.languages.iter().map(|l| l.id()).collect()
290    }
291
292    /// The language claiming `path`, when one does.
293    pub fn language_of(&self, path: &Path) -> Option<Arc<dyn Language>> {
294        self.languages.for_path(path)
295    }
296
297    pub fn language(&self, id: &LanguageId) -> Option<Arc<dyn Language>> {
298        self.languages.get(id)
299    }
300
301    /// The language of a directory: the one claiming its first file.
302    pub fn language_of_directory(&self, dir: &Path) -> Option<Arc<dyn Language>> {
303        self.workspace
304            .vfs()
305            .walk(&self.workspace.absolute(dir))
306            .ok()?
307            .iter()
308            .find_map(|p| self.languages.for_path(p))
309    }
310
311    /// A language's module system on this tree, when it has a layout.
312    pub fn namespace(&mut self, language: &LanguageId) -> Option<Namespace> {
313        let language = self.languages.get(language)?;
314        language.layout()?;
315        let project = self.project_build(&language.id())?;
316        let sources = self
317            .module_sources
318            .entry(language.id())
319            .or_insert_with(|| {
320                Arc::new(
321                    self.entries
322                        .iter()
323                        .filter(|e| e.candidate.language() == language.id())
324                        .map(|e| (e.candidate.path().to_path_buf(), e.candidate.source.clone()))
325                        .collect(),
326                )
327            })
328            .clone();
329        Some(Namespace::new(
330            language,
331            self.cancellation.clone(),
332            project,
333            sources,
334        ))
335    }
336
337    /// The namespace of the language claiming `path`, or why there is none:
338    /// no language claims it, or the language has no layout.
339    pub fn namespace_of(&mut self, path: &Path) -> Result<Namespace, EngineError> {
340        let language = self
341            .languages
342            .for_path(path)
343            .ok_or_else(|| EngineError::NoLanguage(path.into()))?;
344        self.namespace(&language.id())
345            .ok_or_else(|| EngineError::NoLayout(language.id()))
346    }
347
348    /// The claimed file at `path`, or the error that says why there is none.
349    pub fn file(&self, path: &Path) -> Result<Candidate, EngineError> {
350        self.candidate(path)
351            .ok_or_else(|| EngineError::NoLanguage(path.into()))
352    }
353
354    /// Structural or symbolic search: only files spelling the query's
355    /// literal words are parsed. A language whose grammar cannot compile the
356    /// query is skipped and named, never fatal.
357    ///
358    /// Declarations come first, with their module address when the file has
359    /// one, then everything else by path and position — the order human
360    /// output prints and numbers.
361    pub fn search(&mut self, query: &Query) -> Result<Search, EngineError> {
362        self.search_scoped(query, &crate::SearchScope::default())
363    }
364    pub(crate) fn search_scoped(
365        &mut self,
366        query: &Query,
367        scope: &crate::SearchScope,
368    ) -> Result<Search, EngineError> {
369        let (candidates, skipped) = self.scoped_candidates(query, scope)?;
370        let per_file: Vec<Vec<Match>> = candidates
371            .par_iter()
372            .map(|c| {
373                self.check_read()?;
374                c.find(query)
375            })
376            .collect::<Result<_, _>>()?;
377        // Candidates come in path order and each file's matches in position
378        // order, so moving declarations to the front is all the ordering
379        // there is to do.
380        let mut matches: Vec<Match> = per_file.into_iter().flatten().collect();
381        self.address_declarations(&mut matches);
382        matches.sort_by_key(|m| m.role != Role::Declaration);
383        Ok(Search {
384            scope: scope.clone(),
385            query: query.clone(),
386            matches,
387            skipped,
388        })
389    }
390
391    /// Bound retained search results during collection, before a whole-tree vector exists.
392    pub(crate) fn search_bounded(
393        &mut self,
394        query: &Query,
395        scope: &crate::SearchScope,
396        maximum: usize,
397    ) -> Result<Search, EngineError> {
398        let (candidates, skipped) = self.scoped_candidates(query, scope)?;
399        let mut result = Search {
400            scope: scope.clone(),
401            query: query.clone(),
402            matches: vec![],
403            skipped,
404        };
405        let mut bytes = crate::query_store::QueryStore::weight(&result);
406        for candidate in candidates {
407            self.check_read()?;
408            let mut matches = candidate.find(query)?;
409            self.address_declarations(&mut matches);
410            for found in matches {
411                bytes = bytes.saturating_add(crate::query_store::QueryStore::weight(&found));
412                if bytes > maximum {
413                    return Err(EngineError::RetentionLimit);
414                }
415                result.matches.push(found);
416            }
417        }
418        result.matches.sort_by_key(|m| m.role != Role::Declaration);
419        Ok(result)
420    }
421
422    fn scoped_candidates(
423        &mut self,
424        query: &Query,
425        scope: &crate::SearchScope,
426    ) -> Result<(Vec<Candidate>, Vec<Skipped>), EngineError> {
427        let (candidates, skipped) = self.search_candidates(query);
428        let mut kept = Vec::new();
429        for candidate in candidates {
430            self.check_read()?;
431            if !scope.includes_path(candidate.path()) {
432                continue;
433            }
434            if !scope.packages.is_empty() {
435                let project = self.project_build(&candidate.language());
436                self.check_read()?;
437                if !scope.includes_package(
438                    project
439                        .as_ref()
440                        .and_then(|p| p.packages.containing(candidate.path())),
441                ) {
442                    continue;
443                }
444            }
445            kept.push(candidate);
446        }
447        Ok((kept, skipped))
448    }
449
450    fn search_candidates(&self, query: &Query) -> (Vec<Candidate>, Vec<Skipped>) {
451        let mut skipped = Vec::new();
452        let mut accepted: Vec<LanguageId> = Vec::new();
453        for language in self.languages.iter() {
454            if query.language().is_some_and(|id| id != &language.id()) {
455                continue;
456            }
457            match language.accepts(query) {
458                Ok(()) => accepted.push(language.id()),
459                Err(reason) => skipped.push(Skipped {
460                    language: language.id(),
461                    reason: reason.to_string(),
462                }),
463            }
464        }
465        let candidates = self
466            .containing(query.language(), &query.literals())
467            .into_iter()
468            .filter(|c| accepted.contains(&c.language()))
469            .collect();
470        (candidates, skipped)
471    }
472
473    /// Give each declaration the address `outline` would: its file's module
474    /// joined with its name, when the language has a layout, the file is
475    /// addressable and the kind is. One address lookup per file, relying on
476    /// a file's matches being contiguous.
477    fn address_declarations(&mut self, matches: &mut [Match]) {
478        let mut last: Option<(PathBuf, Option<Address>)> = None;
479        for m in matches.iter_mut() {
480            let Some(symbol) = &m.symbol else {
481                continue;
482            };
483            let Some(ns) = self.namespace(&m.language) else {
484                continue;
485            };
486            if last.as_ref().is_none_or(|(path, _)| path != &m.path) {
487                last = Some((m.path.to_path_buf(), ns.address(&m.path).ok()));
488            }
489            m.address = last
490                .as_ref()
491                .and_then(|(_, module)| module.as_ref())
492                .and_then(|module| ns.address_of(module, symbol));
493        }
494    }
495
496    /// Declarations called `query.name`, narrowed by kind, language and
497    /// `declared_in`; an error when there are none.
498    pub fn declarations(&mut self, query: &ReferencesQuery) -> Result<Vec<Match>, EngineError> {
499        let mut search = Query::named(query.name.as_str());
500        if let Some(symbol) = query.symbol {
501            search = search.with_symbol(symbol);
502        }
503        if let Some(language) = &query.language {
504            search = search.in_language(language.clone());
505        }
506        let mut declarations = self.search(&search)?.matches;
507        if let Some(file) = &query.declared_in {
508            let file = self.workspace.normalize(file);
509            declarations.retain(|d| d.path == file);
510        }
511        if declarations.is_empty() {
512            return Err(EngineError::NoSuchSymbol {
513                name: query.name.clone(),
514                kind: query.symbol,
515            });
516        }
517        Ok(declarations)
518    }
519
520    /// What a file's import statements name, each resolved to an address,
521    /// followed through re-exports to the declaration it reaches, and the
522    /// file declaring that when the layout can place it.
523    pub fn imports_of(&mut self, path: &Path) -> Result<Vec<Dep>, EngineError> {
524        let candidate = self.file(path)?;
525        let ns = self.namespace_of(path)?;
526        let source = candidate.file().source();
527        let fragment = candidate.fragment(&ns)?;
528        fragment
529            .imports()
530            .map(|edge| self.dep(&ns, path, source, edge))
531            .collect()
532    }
533
534    /// One import edge as an answer names it.
535    pub fn dep(
536        &self,
537        ns: &Namespace,
538        path: &Path,
539        source: &SourceText,
540        edge: &Edge,
541    ) -> Result<Dep, EngineError> {
542        let address = edge.dependency_address(path);
543        let origin = match (&address, edge.address()) {
544            (Some(offered), Some(target)) if offered != target => Some(target.clone()),
545            (Some(address), _) => self
546                .origin_of(ns, address)?
547                .filter(|origin| origin != address),
548            _ => None,
549        };
550        let file = origin
551            .as_ref()
552            .or(address.as_ref())
553            .and_then(|address| ns.file_of(address));
554        Ok(Dep {
555            import: edge.import.clone(),
556            start: source.position(edge.import.span.start),
557            address,
558            origin,
559            file: file.map(Into::into),
560        })
561    }
562
563    /// Every file of `ns`'s language with its edges, in parallel, path order.
564    pub fn fragments(&self, ns: &Namespace) -> Result<Vec<Node>, EngineError> {
565        self.files(Some(&ns.id()))
566            .into_par_iter()
567            .map(|candidate| {
568                Ok(Node {
569                    fragment: candidate.fragment(ns)?,
570                    candidate,
571                })
572            })
573            .collect()
574    }
575
576    /// Every file of `ns`'s language other than `path` with a declared
577    /// import resolving to an address `leads` accepts, in path order.
578    pub fn importers(
579        &self,
580        ns: &Namespace,
581        path: &Path,
582        leads: impl Fn(&Address) -> bool + Sync,
583    ) -> Result<Vec<Importer>, EngineError> {
584        Ok(self
585            .fragments(ns)?
586            .into_iter()
587            .filter(|node| node.path() != path)
588            .flat_map(|node| {
589                node.fragment
590                    .imports()
591                    .filter(|e| e.address().is_some_and(&leads))
592                    .map(|e| Importer {
593                        path: node.path().into(),
594                        import: e.import.clone(),
595                        start: node.candidate.file().source().position(e.import.span.start),
596                    })
597                    .collect::<Vec<_>>()
598            })
599            .collect())
600    }
601
602    /// Gather what a rename rests on. Occurrences come only from the
603    /// languages in which a matching declaration exists, so a Rust `foo`
604    /// never touches a TypeScript `foo`.
605    pub fn references(&mut self, query: &ReferencesQuery) -> Result<Evidence, EngineError> {
606        let graph = self;
607        let declarations = graph.declarations(query)?;
608        let languages: BTreeSet<LanguageId> =
609            declarations.iter().map(|m| m.language.clone()).collect();
610        let mut occurrences = Vec::new();
611        // Languages whose name has more than one declaration: an unresolved
612        // token there could belong to any of them.
613        let mut ambiguous = BTreeSet::new();
614        for language in languages {
615            let semantics = graph
616                .language(&language)
617                .map(|l| l.semantics())
618                .ok_or_else(|| EngineError::NoLayout(language.clone()))?;
619            let addressable = Declaration::addressable_in(&declarations, &language, semantics);
620            let mut target = Target::of(graph, query, &addressable)?;
621            if let Some(target) = &mut target
622                && let Some(ns) = graph.namespace(&language)
623            {
624                target.aliases = graph.aliases_of(&ns, &target.address, &query.name)?;
625            }
626            if addressable.len() > 1 || target.as_ref().is_some_and(|t| !t.others.is_empty()) {
627                ambiguous.insert(language.clone());
628            }
629            // No token can spell a name the text does not contain.
630            let candidates = graph.containing(Some(&language), &[&query.name]);
631            let per_file: Vec<Vec<Occurrence>> = candidates
632                .par_iter()
633                .map(|c| match &target {
634                    Some(target) => target.judge(c, &query.name),
635                    // Nothing to judge against: every token is a candidate.
636                    None => Ok(c
637                        .references(&query.name)?
638                        .into_iter()
639                        .map(|m| Occurrence::judged(m, Reason::ByName))
640                        .collect()),
641                })
642                .collect::<Result<_, _>>()?;
643            let mut judged: Vec<Occurrence> = per_file.into_iter().flatten().collect();
644            if let (Some(oracle), Some(target)) = (graph.oracle(), &target) {
645                graph.consult(oracle.as_ref(), target, &mut judged)?;
646            }
647            occurrences.extend(judged);
648        }
649        // Grouped as a preview lists them — `✓`, then `?`, then `✗`, and
650        // within those by reason — so the rows to add or drop with
651        // `--select` are one range.
652        occurrences.sort_by_key(|o| o.reason);
653        Ok(Evidence {
654            declarations,
655            occurrences,
656            ambiguous,
657        })
658    }
659
660    /// Every address that reaches `target` through re-exports, `target`
661    /// itself first: a `pub use` of the target (or of an alias of it) in a
662    /// file offers it on under that file's address — as the name it binds,
663    /// so `pub use a::X as Y` offers `Y`; a glob re-export of an alias's
664    /// module offers it under its own name. Followed to a fixed point, so
665    /// chains of re-exports resolve. Only files spelling one of the names
666    /// found so far (or a `*`) are read.
667    pub fn aliases_of(
668        &self,
669        ns: &Namespace,
670        target: &Address,
671        name: &str,
672    ) -> Result<Vec<Address>, EngineError> {
673        let mut aliases = vec![target.clone()];
674        let mut names: BTreeSet<Name> = [Name::from(name)].into();
675        let mut read: HashSet<PathBuf> = HashSet::new();
676        let mut files: Vec<Arc<Fragment>> = Vec::new();
677        // A named re-export spells the name. A glob re-export spells the
678        // language's glob marker, and sits in the alias's own package or
679        // spells that package's name in its path (`pub use foo_core::*`).
680        let glob = ns.language().glob_marker();
681        let reach = self.reach_of(ns, target)?;
682        loop {
683            let packages: BTreeSet<vvv_core::PackageId> =
684                aliases.iter().map(|a| a.package().clone()).collect();
685            let globs_toward = |c: &Candidate| {
686                glob.is_some_and(|marker| c.text().contains(marker))
687                    && (packages.iter().any(|p| c.contains_all(&[p.as_str()]))
688                        || ns
689                            .address(c.path())
690                            .is_ok_and(|a| packages.contains(a.package())))
691            };
692            let fresh: Vec<(PathBuf, Arc<Fragment>)> = self
693                .files(Some(&ns.id()))
694                .into_par_iter()
695                .filter(|c| !read.contains(c.path()))
696                .filter(|c| names.iter().any(|n| c.contains_all(&[n.as_str()])) || globs_toward(c))
697                .map(|c| Ok((c.path().to_path_buf(), c.fragment(ns)?)))
698                .collect::<Result<_, EngineError>>()?;
699            for (path, fragment) in fresh {
700                read.insert(path);
701                files.push(fragment);
702            }
703            let mut grew = false;
704            for fragment in &files {
705                let Some(module) = &fragment.module else {
706                    continue;
707                };
708                for edge in fragment.edges.iter().filter(|e| e.import.reexport) {
709                    let Some(resolved) = edge.address() else {
710                        continue;
711                    };
712                    let offered: Vec<Name> = if edge.import.glob {
713                        // A glob brings in what the module can see: the
714                        // declaration itself only where its reach admits.
715                        aliases
716                            .iter()
717                            .filter(|a| a.parent().as_ref() == Some(resolved))
718                            .filter(|a| *a != target || reach.admits(module))
719                            .filter_map(|a| a.path().last().cloned())
720                            .collect()
721                    } else if aliases.contains(resolved) {
722                        edge.import.binding().cloned().into_iter().collect()
723                    } else {
724                        Vec::new()
725                    };
726                    for name in offered {
727                        let alias = module.join(name.as_str());
728                        if !aliases.contains(&alias) {
729                            names.insert(name);
730                            aliases.push(alias);
731                            grew = true;
732                        }
733                    }
734                }
735            }
736            if !grew {
737                return Ok(aliases);
738            }
739        }
740    }
741
742    /// Ask the oracle about every token the scope left unresolved. An
743    /// answer counts only as a declaration the graph knows: the target's
744    /// own name is `Oracle`, another addressable declaration's is
745    /// `OracleOther`, anything else leaves the token as it was.
746    fn consult(
747        &self,
748        oracle: &dyn Oracle,
749        target: &Target,
750        occurrences: &mut [Occurrence],
751    ) -> Result<(), EngineError> {
752        for occurrence in occurrences
753            .iter_mut()
754            .filter(|o| o.reason == Reason::Unresolved)
755        {
756            let Some(referent) = oracle.refers(&occurrence.m.path, occurrence.m.span) else {
757                continue;
758            };
759            let Some(candidate) = self.candidate(&referent.path) else {
760                continue;
761            };
762            let fragment = candidate.fragment(&target.ns)?;
763            let Some(declared) = fragment
764                .declarations
765                .iter()
766                .find(|d| d.symbol.name_span == referent.name_span)
767            else {
768                continue;
769            };
770            let reason = if target.aliases.contains(&declared.address) {
771                Reason::Oracle
772            } else {
773                Reason::OracleOther
774            };
775            *occurrence = Occurrence::judged(occurrence.m.clone(), reason);
776        }
777        Ok(())
778    }
779
780    /// Who may name the declaration at `address`, as its file declares it;
781    /// everyone when the graph cannot find it (a re-export's own reach).
782    fn reach_of(&self, ns: &Namespace, address: &Address) -> Result<Reach, EngineError> {
783        let Some(file) = address.parent().and_then(|module| ns.file_of(&module)) else {
784            return Ok(Reach::Everyone);
785        };
786        let fragment = self.file(&file)?.fragment(ns)?;
787        Ok(fragment
788            .declarations
789            .iter()
790            .find(|d| d.address == *address)
791            .map_or(Reach::Everyone, |d| d.reach.clone()))
792    }
793
794    /// The declaration an address reaches through re-exports: the address
795    /// itself when its module declares the name; else what the module's
796    /// re-export of the name (a `pub use` binding it, or a glob of a module
797    /// that has it) leads to, followed to the end. `None` when the chain
798    /// leaves what the layout can place — another package, a type's item.
799    pub fn origin_of(
800        &self,
801        ns: &Namespace,
802        address: &Address,
803    ) -> Result<Option<Address>, EngineError> {
804        self.origin_from(ns, address, &mut HashSet::new())
805    }
806
807    fn origin_from(
808        &self,
809        ns: &Namespace,
810        at: &Address,
811        seen: &mut HashSet<Address>,
812    ) -> Result<Option<Address>, EngineError> {
813        if !seen.insert(at.clone()) {
814            return Ok(None);
815        }
816        let (Some(module), Some(name)) = (at.parent(), at.path().last()) else {
817            // A package root names itself.
818            return Ok(Some(at.clone()));
819        };
820        let Some(file) = ns.file_of(&module) else {
821            return Ok(None);
822        };
823        let fragment = self.file(&file)?.fragment(ns)?;
824        if fragment.module.as_ref() != Some(&module) {
825            return Ok(None);
826        }
827        if fragment.declarations.iter().any(|d| *name == d.symbol.name) {
828            return Ok(Some(at.clone()));
829        }
830        for edge in fragment.edges.iter().filter(|e| e.import.reexport) {
831            let Some(resolved) = edge.address() else {
832                continue;
833            };
834            let next = if edge.import.glob {
835                resolved.join(name.as_str())
836            } else if edge.import.binding() == Some(name) {
837                resolved.clone()
838            } else {
839                continue;
840            };
841            if let Some(origin) = self.origin_from(ns, &next, seen)? {
842                return Ok(Some(origin));
843            }
844        }
845        Ok(None)
846    }
847
848    /// Modules with an import or a qualified path resolving to `address` or
849    /// under it — every file of the namespace's language except `except`,
850    /// in path order. What must still see a declaration after it moves.
851    pub fn consumers(
852        &self,
853        ns: &Namespace,
854        address: &Address,
855        except: &[&Path],
856    ) -> Result<Vec<Address>, EngineError> {
857        Ok(self
858            .fragments(ns)?
859            .into_iter()
860            .filter(|node| !except.contains(&node.path()))
861            .filter(|node| node.fragment.reaches(address))
862            .filter_map(|node| node.fragment.module.clone())
863            .collect())
864    }
865}
866
867impl std::fmt::Debug for Graph {
868    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
869        f.debug_struct("Graph")
870            .field("root", &self.workspace.root())
871            .field("files", &self.walked.len())
872            .field("loaded", &self.entries.len())
873            .finish()
874    }
875}
876
877impl Graph {
878    pub(crate) fn relationship_files(
879        &mut self,
880        language: &crate::LanguageId,
881        scope: &crate::SearchScope,
882    ) -> Result<Vec<Candidate>, EngineError> {
883        let mut files = Vec::new();
884        let group = self
885            .languages
886            .get(language)
887            .map(|plugin| plugin.reference_group());
888        for file in self.files(None) {
889            if self
890                .languages
891                .get(&file.language())
892                .map(|plugin| plugin.reference_group())
893                != group
894            {
895                continue;
896            }
897            self.check_read()?;
898            if !scope.includes_path(file.path()) {
899                continue;
900            }
901            if !scope.packages.is_empty() {
902                let project = self.project_build(&file.language());
903                if !scope.includes_package(
904                    project
905                        .as_ref()
906                        .and_then(|p| p.packages.containing(file.path())),
907                ) {
908                    continue;
909                }
910            }
911            files.push(file);
912        }
913        Ok(files)
914    }
915}