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 namespace;
18mod references;
19mod scope;
20
21use std::collections::HashMap;
22use std::path::{Path, PathBuf};
23use std::sync::Arc;
24use std::time::{Duration, Instant};
25
26use rayon::prelude::*;
27use vvv_core::{
28    Address, FileSet, Language, LanguageId, LanguageRegistry, Oracle, Package, Packages, Project,
29    Query, Role, SourceText,
30};
31
32pub use candidate::Candidate;
33pub use fragment::{Declared, Edge, Fragment, Node, Structure};
34pub use namespace::Namespace;
35pub use references::{DeclarationSite, Evidence};
36pub use scope::Scope;
37
38use crate::{
39    Dep, EngineError, Importer, Match, ReferencesQuery, Search, Skipped, Stamp, Workspace,
40};
41
42pub struct Graph {
43    workspace: Workspace,
44    languages: LanguageRegistry,
45    /// Every file of the last walk, absolute, in path order. Only a project
46    /// needs them relative and as a set, so that is built on demand.
47    walked: Vec<PathBuf>,
48    /// When that walk happened; `None` once something may have changed it.
49    walked_at: Option<Instant>,
50    /// Every claimed file, in path order.
51    entries: Vec<Entry>,
52    /// The workspace as a language's layout sees it, built from the last
53    /// walk the first time that language asks; a search never pays for it.
54    /// With it, which build this is: a project equal to the previous build
55    /// keeps its number, so fragments resolved against it stay valid.
56    projects: HashMap<LanguageId, (Arc<Project>, u64)>,
57    /// A second opinion for tokens syntax cannot place, when the host has
58    /// one; asked after the scope, never instead of it.
59    oracle: Option<Arc<dyn Oracle>>,
60    /// The last build of each language's project, to tell a refresh that
61    /// changed nothing about the project from one that did.
62    previous: HashMap<LanguageId, (Arc<Project>, u64)>,
63}
64
65struct Entry {
66    /// Absolute, as walked.
67    path: PathBuf,
68    /// `None` when the model will not be asked again, so nothing was stamped.
69    stamp: Option<Stamp>,
70    candidate: Candidate,
71}
72
73/// How long an [`Engine`](crate::Engine) keeps its graph.
74#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
75pub enum Retention {
76    /// Read the workspace afresh for every question: right for a one-shot
77    /// command, whose single question has to read the tree anyway.
78    #[default]
79    PerCall,
80    /// Keep files and facts between questions and re-read only what changed:
81    /// right for a session that asks the same tree over and over. Within
82    /// `trust` of the last walk it does not even look — a burst of
83    /// keystrokes walks a large tree once, not per key — except after the
84    /// engine itself wrote, or was told the tree changed.
85    Session { trust: Duration },
86}
87
88impl Retention {
89    /// A session that checks the tree before every question.
90    pub const fn session() -> Self {
91        Self::Session {
92            trust: Duration::ZERO,
93        }
94    }
95
96    /// A session that trusts its last walk for `trust`.
97    pub const fn trusting(self, trust: Duration) -> Self {
98        match self {
99            Self::PerCall => Self::PerCall,
100            Self::Session { .. } => Self::Session { trust },
101        }
102    }
103}
104
105impl Graph {
106    pub fn new(workspace: Workspace, languages: LanguageRegistry) -> Self {
107        Self {
108            workspace,
109            languages,
110            walked: Vec::new(),
111            walked_at: None,
112            oracle: None,
113            entries: Vec::new(),
114            projects: HashMap::new(),
115            previous: HashMap::new(),
116        }
117    }
118
119    /// Walk the tree; load files that appeared or changed, forget files that
120    /// vanished, keep the rest. A graph kept for a session stamps what it
121    /// loads so the next refresh can tell; one built per call does not.
122    pub fn refresh(&mut self, retention: Retention) -> Result<(), EngineError> {
123        if let Retention::Session { trust } = retention
124            && self.walked_at.is_some_and(|at| at.elapsed() < trust)
125        {
126            return Ok(());
127        }
128        let walked = self.workspace.files()?;
129        let claimed: Vec<(&Path, Arc<dyn Language>)> = walked
130            .iter()
131            .filter_map(|abs| Some((abs.as_path(), self.languages.for_path(abs)?)))
132            .collect();
133
134        let before = std::mem::take(&mut self.entries);
135        let vfs = self.workspace.vfs();
136        let workspace = &self.workspace;
137        let stamping = matches!(retention, Retention::Session { .. });
138        let now: Vec<Entry> = claimed
139            .into_par_iter()
140            .map(|(abs, language)| {
141                let stamp = stamping.then(|| vfs.stamp(abs)).transpose()?;
142                let known = stamp.and_then(|stamp| {
143                    before
144                        .binary_search_by(|e| e.path.as_path().cmp(abs))
145                        .ok()
146                        .map(|i| &before[i])
147                        .filter(|e| e.stamp == Some(stamp))
148                });
149                let candidate = match known {
150                    Some(known) => known.candidate.clone(),
151                    None => Candidate::new(workspace.load(abs)?, language),
152                };
153                Ok(Entry {
154                    path: abs.to_path_buf(),
155                    stamp,
156                    candidate,
157                })
158            })
159            .collect::<Result<_, EngineError>>()?;
160        self.entries = now;
161        self.previous = std::mem::take(&mut self.projects);
162        self.walked = walked;
163        self.walked_at = Some(Instant::now());
164        Ok(())
165    }
166
167    /// The tree may have changed — the engine wrote to it, or was told so:
168    /// the next refresh walks whatever it was told to trust.
169    pub fn touched(&mut self) {
170        self.walked_at = None;
171    }
172
173    /// Consult `oracle` for the tokens the scope leaves unresolved.
174    pub fn with_oracle(mut self, oracle: Arc<dyn Oracle>) -> Self {
175        self.oracle = Some(oracle);
176        self
177    }
178
179    pub(crate) fn oracle(&self) -> Option<&Arc<dyn Oracle>> {
180        self.oracle.as_ref()
181    }
182
183    /// Every file `language` claims — any registered language when `None` —
184    /// in path order.
185    pub fn files(&self, language: Option<&LanguageId>) -> Vec<Candidate> {
186        self.entries
187            .iter()
188            .map(|e| &e.candidate)
189            .filter(|c| language.is_none_or(|id| &c.language() == id))
190            .cloned()
191            .collect()
192    }
193
194    /// The one claimed file at `path` (absolute or workspace-relative).
195    pub fn candidate(&self, path: &Path) -> Option<Candidate> {
196        let abs = self.workspace.absolute(path);
197        self.entries
198            .binary_search_by(|e| e.path.as_path().cmp(abs.as_path()))
199            .ok()
200            .map(|i| self.entries[i].candidate.clone())
201    }
202
203    /// The files of `language` that spell every one of `literals` as whole
204    /// tokens: the only ones a query built from those words can match.
205    pub fn containing(&self, language: Option<&LanguageId>, literals: &[&str]) -> Vec<Candidate> {
206        self.files(language)
207            .into_par_iter()
208            .filter(|c| c.contains_all(literals))
209            .collect()
210    }
211
212    /// The workspace as `language`'s layout sees it: the walk's files plus
213    /// the packages the layout's manifests declare. Built on first use after
214    /// a refresh; `None` when the language has no layout.
215    /// The project and the number of its build.
216    fn project_build(&mut self, language: &LanguageId) -> Option<(Arc<Project>, u64)> {
217        if let Some(built) = self.projects.get(language) {
218            return Some(built.clone());
219        }
220        let language_impl = self.languages.get(language)?;
221        let layout = language_impl.layout()?;
222        let vfs = self.workspace.vfs();
223        let files: FileSet = self
224            .walked
225            .iter()
226            .map(|abs| self.workspace.absolute(abs))
227            .map(|abs| self.workspace.relative(&abs))
228            .collect();
229        let manifests: Vec<&Path> = files
230            .iter()
231            .filter(|p| {
232                p.file_name()
233                    .is_some_and(|n| layout.manifests().iter().any(|m| n == *m))
234            })
235            .collect();
236        let packages: Vec<Package> = manifests
237            .into_par_iter()
238            .filter_map(|manifest| {
239                let text = vfs.read(&self.workspace.absolute(manifest)).ok()?;
240                layout.package(manifest, &text)
241            })
242            .collect();
243        let packages = Packages::new(packages);
244        let project = Project { packages, files };
245        // The same project as last time keeps its number: every fragment
246        // resolved against it is still right.
247        let built = match self.previous.remove(language) {
248            Some((last, generation)) if *last == project => (last, generation),
249            Some((_, generation)) => (Arc::new(project), generation + 1),
250            None => (Arc::new(project), 1),
251        };
252        self.projects.insert(language.clone(), built.clone());
253        Some(built)
254    }
255
256    // ------------------------------------------------------------ questions
257
258    /// Every language this graph understands.
259    pub fn language_ids(&self) -> Vec<LanguageId> {
260        self.languages.iter().map(|l| l.id()).collect()
261    }
262
263    /// The language claiming `path`, when one does.
264    pub fn language_of(&self, path: &Path) -> Option<Arc<dyn Language>> {
265        self.languages.for_path(path)
266    }
267
268    pub fn language(&self, id: &LanguageId) -> Option<Arc<dyn Language>> {
269        self.languages.get(id)
270    }
271
272    /// The language of a directory: the one claiming its first file.
273    pub fn language_of_directory(&self, dir: &Path) -> Option<Arc<dyn Language>> {
274        self.workspace
275            .vfs()
276            .walk(&self.workspace.absolute(dir))
277            .ok()?
278            .iter()
279            .find_map(|p| self.languages.for_path(p))
280    }
281
282    /// A language's module system on this tree, when it has a layout.
283    pub fn namespace(&mut self, language: &LanguageId) -> Option<Namespace> {
284        let language = self.languages.get(language)?;
285        language.layout()?;
286        let (project, generation) = self.project_build(&language.id())?;
287        Some(Namespace::new(language, project, generation))
288    }
289
290    /// The namespace of the language claiming `path`, or why there is none:
291    /// no language claims it, or the language has no layout.
292    pub fn namespace_of(&mut self, path: &Path) -> Result<Namespace, EngineError> {
293        let language = self
294            .languages
295            .for_path(path)
296            .ok_or_else(|| EngineError::NoLanguage(path.into()))?;
297        self.namespace(&language.id())
298            .ok_or_else(|| EngineError::NoLayout(language.id()))
299    }
300
301    /// The claimed file at `path`, or the error that says why there is none.
302    pub fn file(&self, path: &Path) -> Result<Candidate, EngineError> {
303        self.candidate(path)
304            .ok_or_else(|| EngineError::NoLanguage(path.into()))
305    }
306
307    /// Structural or symbolic search: only files spelling the query's
308    /// literal words are parsed. A language whose grammar cannot compile the
309    /// query is skipped and named, never fatal.
310    ///
311    /// Declarations come first, with their module address when the file has
312    /// one, then everything else by path and position — the order human
313    /// output prints and numbers.
314    pub fn search(&mut self, query: &Query) -> Result<Search, EngineError> {
315        let mut skipped = Vec::new();
316        let mut accepted: Vec<LanguageId> = Vec::new();
317        for language in self.languages.iter() {
318            if query.language().is_some_and(|id| id != &language.id()) {
319                continue;
320            }
321            match language.accepts(query) {
322                Ok(()) => accepted.push(language.id()),
323                Err(reason) => skipped.push(Skipped {
324                    language: language.id(),
325                    reason: reason.to_string(),
326                }),
327            }
328        }
329        let candidates: Vec<Candidate> = self
330            .containing(query.language(), &query.literals())
331            .into_iter()
332            .filter(|c| accepted.contains(&c.language()))
333            .collect();
334        let per_file: Vec<Vec<Match>> = candidates
335            .par_iter()
336            .map(|c| c.find(query))
337            .collect::<Result<_, _>>()?;
338        // Candidates come in path order and each file's matches in position
339        // order, so moving declarations to the front is all the ordering
340        // there is to do.
341        let mut matches: Vec<Match> = per_file.into_iter().flatten().collect();
342        self.address_declarations(&mut matches);
343        matches.sort_by_key(|m| m.role != Role::Declaration);
344        Ok(Search {
345            query: query.clone(),
346            matches,
347            skipped,
348        })
349    }
350
351    /// Give each declaration the address `outline` would: its file's module
352    /// joined with its name, when the language has a layout, the file is
353    /// addressable and the kind is. One address lookup per file, relying on
354    /// a file's matches being contiguous.
355    fn address_declarations(&mut self, matches: &mut [Match]) {
356        let mut last: Option<(PathBuf, Option<Address>)> = None;
357        for m in matches.iter_mut() {
358            let Some(symbol) = &m.symbol else {
359                continue;
360            };
361            let Some(ns) = self.namespace(&m.language) else {
362                continue;
363            };
364            if last.as_ref().is_none_or(|(path, _)| path != &m.path) {
365                last = Some((m.path.to_path_buf(), ns.address(&m.path).ok()));
366            }
367            m.address = last
368                .as_ref()
369                .and_then(|(_, module)| module.as_ref())
370                .and_then(|module| ns.address_of(module, symbol));
371        }
372    }
373
374    /// Declarations called `query.name`, narrowed by kind, language and
375    /// `declared_in`; an error when there are none.
376    pub fn declarations(&mut self, query: &ReferencesQuery) -> Result<Vec<Match>, EngineError> {
377        let mut search = Query::named(query.name.as_str());
378        if let Some(symbol) = query.symbol {
379            search = search.with_symbol(symbol);
380        }
381        if let Some(language) = &query.language {
382            search = search.in_language(language.clone());
383        }
384        let mut declarations = self.search(&search)?.matches;
385        if let Some(file) = &query.declared_in {
386            let file = self.workspace.normalize(file);
387            declarations.retain(|d| d.path == file);
388        }
389        if declarations.is_empty() {
390            return Err(EngineError::NoSuchSymbol {
391                name: query.name.clone(),
392                kind: query.symbol,
393            });
394        }
395        Ok(declarations)
396    }
397
398    /// What a file's import statements name, each resolved to an address,
399    /// followed through re-exports to the declaration it reaches, and the
400    /// file declaring that when the layout can place it.
401    pub fn imports_of(&mut self, path: &Path) -> Result<Vec<Dep>, EngineError> {
402        let candidate = self.file(path)?;
403        let ns = self.namespace_of(path)?;
404        let source = candidate.file().source();
405        let fragment = candidate.fragment(&ns)?;
406        fragment
407            .imports()
408            .map(|edge| self.dep(&ns, source, edge))
409            .collect()
410    }
411
412    /// One import edge as an answer names it.
413    pub fn dep(
414        &self,
415        ns: &Namespace,
416        source: &SourceText,
417        edge: &Edge,
418    ) -> Result<Dep, EngineError> {
419        let origin = match &edge.address {
420            Some(address) => self.origin_of(ns, address)?.filter(|o| o != address),
421            None => None,
422        };
423        let file = origin
424            .as_ref()
425            .or(edge.address.as_ref())
426            .and_then(|a| ns.file_of(a));
427        Ok(Dep {
428            import: edge.import.clone(),
429            start: source.position(edge.import.span.start),
430            address: edge.address.clone(),
431            origin,
432            file: file.map(Into::into),
433        })
434    }
435
436    /// Every file of `ns`'s language with its edges, in parallel, path order.
437    pub fn fragments(&self, ns: &Namespace) -> Result<Vec<Node>, EngineError> {
438        self.files(Some(&ns.id()))
439            .into_par_iter()
440            .map(|candidate| {
441                Ok(Node {
442                    fragment: candidate.fragment(ns)?,
443                    candidate,
444                })
445            })
446            .collect()
447    }
448
449    /// Every file of `ns`'s language other than `path` with a declared
450    /// import resolving to an address `leads` accepts, in path order.
451    pub fn importers(
452        &self,
453        ns: &Namespace,
454        path: &Path,
455        leads: impl Fn(&Address) -> bool + Sync,
456    ) -> Result<Vec<Importer>, EngineError> {
457        Ok(self
458            .fragments(ns)?
459            .into_iter()
460            .filter(|node| node.path() != path)
461            .flat_map(|node| {
462                node.fragment
463                    .imports()
464                    .filter(|e| e.address.as_ref().is_some_and(&leads))
465                    .map(|e| Importer {
466                        path: node.path().into(),
467                        import: e.import.clone(),
468                        start: node.candidate.file().source().position(e.import.span.start),
469                    })
470                    .collect::<Vec<_>>()
471            })
472            .collect())
473    }
474}
475
476impl std::fmt::Debug for Graph {
477    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
478        f.debug_struct("Graph")
479            .field("root", &self.workspace.root())
480            .field("files", &self.walked.len())
481            .field("loaded", &self.entries.len())
482            .finish()
483    }
484}