1mod 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 walked: Vec<PathBuf>,
48 walked_at: Option<Instant>,
50 entries: Vec<Entry>,
52 projects: HashMap<LanguageId, (Arc<Project>, u64)>,
57 oracle: Option<Arc<dyn Oracle>>,
60 previous: HashMap<LanguageId, (Arc<Project>, u64)>,
63}
64
65struct Entry {
66 path: PathBuf,
68 stamp: Option<Stamp>,
70 candidate: Candidate,
71}
72
73#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
75pub enum Retention {
76 #[default]
79 PerCall,
80 Session { trust: Duration },
86}
87
88impl Retention {
89 pub const fn session() -> Self {
91 Self::Session {
92 trust: Duration::ZERO,
93 }
94 }
95
96 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 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 pub fn touched(&mut self) {
170 self.walked_at = None;
171 }
172
173 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 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 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 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 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 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 pub fn language_ids(&self) -> Vec<LanguageId> {
260 self.languages.iter().map(|l| l.id()).collect()
261 }
262
263 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 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 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 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 pub fn file(&self, path: &Path) -> Result<Candidate, EngineError> {
303 self.candidate(path)
304 .ok_or_else(|| EngineError::NoLanguage(path.into()))
305 }
306
307 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 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 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 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 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 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 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 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}