Skip to main content

vvv_engine/capabilities/
relationships.rs

1//! Evidence-bearing call and reference sites for an exact symbol.
2use super::incoming::{DiscoveryWork, IncomingReferences};
3use crate::graph::query_snapshot::QuerySnapshot;
4use crate::{
5    DefinitionLocation, Engine, EngineError, NavigationOrigin, NavigationQuery, Position,
6    ResolutionEvidence, ResolutionOutcome, ResolutionQuery, SearchScope, Selection, SnapshotId,
7    SourceAnchor, SymbolRef, UnavailableReason,
8};
9use serde::{Deserialize, Serialize};
10use vvv_core::{CallKind, Symbol, SymbolKind};
11
12#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
13#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
14#[serde(rename_all = "snake_case")]
15pub enum RelationshipKind {
16    Callers,
17    Callees,
18    References,
19}
20
21#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
22#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
23#[serde(default, deny_unknown_fields)]
24pub struct RelationshipBudget {
25    #[cfg_attr(feature = "schema", schemars(range(min = 1024, max = 1048576)))]
26    pub max_bytes: usize,
27    #[cfg_attr(feature = "schema", schemars(range(min = 1, max = 1024)))]
28    pub max_items: usize,
29    #[cfg_attr(feature = "schema", schemars(range(min = 1, max = 16384)))]
30    pub max_lookups: usize,
31    #[cfg_attr(feature = "schema", schemars(range(min = 1, max = 4096)))]
32    pub max_files: usize,
33}
34impl Default for RelationshipBudget {
35    fn default() -> Self {
36        Self {
37            max_bytes: 16_384,
38            max_items: 64,
39            max_lookups: 1024,
40            max_files: 128,
41        }
42    }
43}
44impl RelationshipBudget {
45    pub fn validate(&self) -> Result<(), EngineError> {
46        if !(1024..=1_048_576).contains(&self.max_bytes)
47            || !(1..=1024).contains(&self.max_items)
48            || !(1..=16_384).contains(&self.max_lookups)
49            || !(1..=4096).contains(&self.max_files)
50        {
51            return Err(EngineError::InvalidBudget);
52        }
53        Ok(())
54    }
55}
56
57#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
58#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
59pub struct RelationshipsQuery {
60    pub origin: NavigationOrigin,
61    #[serde(default)]
62    pub selection: Selection,
63    pub kind: RelationshipKind,
64    #[serde(default)]
65    pub scope: SearchScope,
66    #[serde(default)]
67    pub budget: RelationshipBudget,
68}
69
70#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
71#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
72pub struct Relationships {
73    pub snapshot: SnapshotId,
74    pub subject: ResolutionOutcome,
75    pub kind: RelationshipKind,
76    pub scope: SearchScope,
77    pub items: Vec<Relationship>,
78    pub coverage: RelationshipCoverage,
79    #[serde(default, skip_serializing_if = "Option::is_none")]
80    pub next_cursor: Option<crate::Cursor>,
81}
82
83#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
84#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
85pub struct Relationship {
86    /// Exact identifier (or unsupported callee expression) providing the evidence.
87    pub site: SourceAnchor,
88    pub start: Position,
89    pub spelling: String,
90    /// Owner of a call site; absent for non-call references and anonymous callables.
91    pub caller: Option<SymbolRef>,
92    /// None denotes a non-call reference, including imports and value references.
93    pub call: Option<CallKind>,
94    #[serde(flatten)]
95    pub resolution: RelationshipResolution,
96}
97#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
98#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
99#[serde(tag = "outcome", rename_all = "snake_case")]
100pub enum RelationshipResolution {
101    Confirmed {
102        target: SymbolRef,
103        evidence: ResolutionEvidence,
104    },
105    Ambiguous {
106        candidates: Vec<DefinitionLocation>,
107    },
108    Unavailable {
109        reason: UnavailableReason,
110    },
111    /// A call to a local/parameter/value binding does not identify the invoked function.
112    Indirect {
113        binding: Option<SymbolRef>,
114    },
115}
116#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
117#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
118#[serde(rename_all = "snake_case")]
119pub enum RelationshipLimit {
120    Files,
121    Lookups,
122    Items,
123    Bytes,
124}
125
126#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
127#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
128#[serde(rename_all = "snake_case")]
129pub enum RelationshipLimitation {
130    ReceiverTypes,
131    IndirectTargets,
132    MacroExpansion,
133    AnonymousCallers,
134    UnsupportedBindings,
135    UnenumeratedAliases,
136}
137
138#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
139#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
140pub struct RelationshipCoverage {
141    /// Known gaps remain even when the candidate scan finishes.
142    pub limitations: Vec<RelationshipLimitation>,
143    pub files_scanned: usize,
144    pub files_remaining: usize,
145    pub lookups: usize,
146    pub omitted_items: usize,
147    pub stopped_by: Option<RelationshipLimit>,
148    /// Files whose plugin does not provide syntactic call facts.
149    pub unsupported_files: usize,
150    /// Import bindings that could not be resolved while discovering alias spellings.
151    pub unresolved_imports: usize,
152    /// Completion of the candidate scan, not proof of a complete runtime call graph.
153    pub scan_complete: bool,
154}
155impl RelationshipsQuery {
156    pub fn new(origin: NavigationOrigin, kind: RelationshipKind) -> Self {
157        Self {
158            origin,
159            kind,
160            selection: Selection::All,
161            scope: SearchScope::default(),
162            budget: RelationshipBudget::default(),
163        }
164    }
165    pub fn execute(self, engine: &Engine) -> Result<Relationships, EngineError> {
166        let _operation = engine.operation();
167        self.execute_in(engine)
168    }
169    pub(crate) fn execute_in(self, engine: &Engine) -> Result<Relationships, EngineError> {
170        self.budget.validate()?;
171        self.scope.validate()?;
172        let (mut graph, snapshot) = QuerySnapshot::capture(engine)?;
173        let seed = ResolutionQuery(NavigationQuery {
174            origin: self.origin.clone(),
175            selection: self.selection.clone(),
176        })
177        .execute_in(&mut graph)?;
178        let data = RelationshipSeed {
179            subject: seed.outcome,
180            kind: self.kind,
181            scope: self.scope.clone(),
182            files: vec![],
183        };
184        let mut data = data;
185        if let ResolutionOutcome::Resolved { definition, .. } = &data.subject {
186            data.files = graph
187                .relationship_files(&definition.target.language, &data.scope)?
188                .into_iter()
189                .filter(|file| {
190                    data.kind != RelationshipKind::Callees
191                        || file.path() == definition.target.declaration.path.as_path()
192                })
193                .map(|file| file.path().into())
194                .collect();
195        }
196        let mut session = super::pagination::PageSession::new(
197            engine,
198            snapshot,
199            &(self.origin, self.selection, self.kind, self.scope),
200            crate::query_store::QueryData::Relationships(data),
201        );
202        let reply =
203            RelationshipSession::default().page(engine, &mut graph, &mut session, self.budget);
204        match session.finish(engine, reply)? {
205            crate::PageReply::Relationships(reply) => Ok(reply),
206            _ => unreachable!("capability returns its own page"),
207        }
208    }
209}
210
211#[derive(Debug, serde::Serialize)]
212pub(crate) struct RelationshipSeed {
213    subject: ResolutionOutcome,
214    kind: RelationshipKind,
215    scope: SearchScope,
216    files: Vec<crate::RelPath>,
217}
218
219#[derive(Debug, Default, Clone, serde::Serialize)]
220pub(crate) struct RelationshipSession {
221    file: usize,
222    incoming: Option<IncomingReferences>,
223    pending: Option<Relationship>,
224    unsupported_files: usize,
225}
226
227impl RelationshipSession {
228    fn done(&self, seed: &RelationshipSeed) -> bool {
229        self.pending.is_none()
230            && (self.file == seed.files.len()
231                || (self.file + 1 == seed.files.len()
232                    && self.incoming.as_ref().is_some_and(|incoming| {
233                        incoming
234                            .sites
235                            .as_ref()
236                            .is_some_and(|sites| incoming.site == sites.len())
237                    })))
238    }
239
240    fn cursor(
241        &self,
242        engine: &Engine,
243        session: &super::pagination::PageSession,
244        seed: &RelationshipSeed,
245    ) -> Option<crate::Cursor> {
246        (!self.done(seed)).then(|| {
247            session.token(
248                engine,
249                &crate::query_store::Checkpoint::Relationships(self.clone()),
250            )
251        })
252    }
253
254    pub(crate) fn page(
255        mut self,
256        engine: &Engine,
257        graph: &mut crate::graph::Graph,
258        session: &mut super::pagination::PageSession,
259        budget: RelationshipBudget,
260    ) -> Result<crate::PageReply, EngineError> {
261        let root = session.root.clone();
262        let crate::query_store::QueryData::Relationships(seed) = &root.data else {
263            return Err(EngineError::InvalidCursor);
264        };
265        let mut result = Relationships {
266            snapshot: root.identity.clone(),
267            subject: seed.subject.clone(),
268            kind: seed.kind,
269            scope: seed.scope.clone(),
270            items: vec![],
271            next_cursor: None,
272            coverage: RelationshipCoverage {
273                limitations: vec![
274                    RelationshipLimitation::ReceiverTypes,
275                    RelationshipLimitation::IndirectTargets,
276                    RelationshipLimitation::MacroExpansion,
277                    RelationshipLimitation::AnonymousCallers,
278                    RelationshipLimitation::UnsupportedBindings,
279                    RelationshipLimitation::UnenumeratedAliases,
280                ],
281                files_scanned: 0,
282                files_remaining: seed.files.len().saturating_sub(self.file),
283                lookups: 0,
284                omitted_items: 0,
285                stopped_by: None,
286                unsupported_files: self.unsupported_files,
287                unresolved_imports: 0,
288                scan_complete: false,
289            },
290        };
291        let mut charged_file = None;
292        while !self.done(seed) {
293            graph.check_read()?;
294            if result.items.len() == budget.max_items {
295                result.coverage.stopped_by = Some(RelationshipLimit::Items);
296                break;
297            }
298            if self.pending.is_none() {
299                if charged_file != Some(self.file) {
300                    if result.coverage.files_scanned == budget.max_files {
301                        result.coverage.stopped_by = Some(RelationshipLimit::Files);
302                        break;
303                    }
304                    result.coverage.files_scanned += 1;
305                    charged_file = Some(self.file);
306                }
307                let file = graph.file(&seed.files[self.file])?;
308                let facts = file.facts()?;
309                let ResolutionOutcome::Resolved { definition, .. } = &seed.subject else {
310                    break;
311                };
312                let target = &definition.target;
313                if self.incoming.is_none() {
314                    if !facts.calls_supported {
315                        self.unsupported_files += 1;
316                        if seed.kind != RelationshipKind::References {
317                            self.file += 1;
318                            continue;
319                        }
320                    }
321                    self.incoming = Some(IncomingReferences::new(
322                        &file,
323                        &definition.name,
324                        seed.kind == RelationshipKind::Callers,
325                    )?);
326                }
327                let incoming = self.incoming.as_mut().expect("current file discovery");
328                if seed.kind != RelationshipKind::Callees {
329                    let mut work = DiscoveryWork {
330                        lookups: result.coverage.lookups,
331                        max_lookups: budget.max_lookups,
332                        unresolved_imports: 0,
333                    };
334                    let ready = incoming.prepare(graph, &file, target, &mut work, &mut vec![])?;
335                    result.coverage.lookups = work.lookups;
336                    result.coverage.unresolved_imports += work.unresolved_imports;
337                    if !ready {
338                        result.coverage.stopped_by = Some(RelationshipLimit::Lookups);
339                        break;
340                    }
341                }
342                if incoming.sites.is_none() {
343                    incoming.sites = Some(match seed.kind {
344                        RelationshipKind::Callees => facts
345                            .calls
346                            .iter()
347                            .filter(|call| call.owner == Some(target.name_span))
348                            .map(|call| call.callee)
349                            .collect(),
350                        RelationshipKind::Callers => facts
351                            .calls
352                            .iter()
353                            .filter(|call| {
354                                file.text()
355                                    .get(call.callee.start..call.callee.end)
356                                    .is_some_and(|name| incoming.names().contains(name))
357                            })
358                            .map(|call| call.callee)
359                            .collect(),
360                        RelationshipKind::References => facts
361                            .tokens()
362                            .filter(|(name, _, span)| {
363                                incoming.names().contains(*name)
364                                    && !(file.path() == target.declaration.path.as_path()
365                                        && *span == target.name_span)
366                            })
367                            .map(|(_, _, span)| span)
368                            .collect(),
369                    });
370                }
371                let sites = incoming.sites.as_ref().expect("discovered sites");
372                let Some(&span) = sites.get(incoming.site) else {
373                    self.file += 1;
374                    self.incoming = None;
375                    continue;
376                };
377                if result.coverage.lookups == budget.max_lookups {
378                    result.coverage.stopped_by = Some(RelationshipLimit::Lookups);
379                    break;
380                }
381                incoming.site += 1;
382                let call = facts.calls.iter().find(|call| call.callee == span);
383                let site = SourceAnchor {
384                    path: file.path().into(),
385                    content: file.file().content_id(),
386                    span,
387                };
388                let spelling = file
389                    .text()
390                    .get(span.start..span.end)
391                    .ok_or_else(|| EngineError::InvalidAnchor {
392                        path: file.path().into(),
393                    })?
394                    .to_owned();
395                result.coverage.lookups += 1;
396                let resolution = if call.is_some_and(|c| c.kind == CallKind::Indirect) {
397                    RelationshipResolution::Indirect { binding: None }
398                } else {
399                    let found = ResolutionQuery(NavigationQuery::occurrence(site.clone()))
400                        .execute_in(graph)?;
401                    match found.outcome {
402                        ResolutionOutcome::Resolved { definition, .. } => {
403                            if call.is_some()
404                                && seed.kind != RelationshipKind::References
405                                && !matches!(
406                                    definition.target.kind,
407                                    SymbolKind::Function | SymbolKind::Method
408                                )
409                            {
410                                if matches!(
411                                    definition.target.kind,
412                                    SymbolKind::Variable
413                                        | SymbolKind::Parameter
414                                        | SymbolKind::Const
415                                        | SymbolKind::Static
416                                ) {
417                                    RelationshipResolution::Indirect {
418                                        binding: Some(definition.target),
419                                    }
420                                } else {
421                                    RelationshipResolution::Unavailable {
422                                        reason: UnavailableReason::UnsupportedContext,
423                                    }
424                                }
425                            } else {
426                                if seed.kind != RelationshipKind::Callees
427                                    && definition.target != *target
428                                {
429                                    continue;
430                                }
431                                RelationshipResolution::Confirmed {
432                                    target: definition.target,
433                                    evidence: definition.evidence,
434                                }
435                            }
436                        }
437                        ResolutionOutcome::Ambiguous { candidates } => {
438                            if seed.kind != RelationshipKind::Callees
439                                && !candidates.iter().any(|c| c.target == *target)
440                            {
441                                continue;
442                            }
443                            RelationshipResolution::Ambiguous { candidates }
444                        }
445                        ResolutionOutcome::Unavailable { reason } => {
446                            RelationshipResolution::Unavailable { reason }
447                        }
448                    }
449                };
450
451                let caller = call
452                    .and_then(|call| call.owner)
453                    .and_then(|owner| {
454                        facts
455                            .symbols
456                            .iter()
457                            .find(|symbol| symbol.name_span == owner)
458                    })
459                    .map(|symbol| Relationship::symbol(&site, &target.language, symbol));
460                self.pending = Some(Relationship {
461                    start: file.file().source().position(span.start),
462                    site,
463                    spelling,
464                    caller,
465                    call: call.map(|call| call.kind),
466                    resolution,
467                });
468            }
469            let pending = self.pending.as_ref().expect("pending relationship").clone();
470            let mut after = self.clone();
471            after.pending = None;
472            result.items.push(pending.clone());
473            result.next_cursor = after.cursor(engine, session, seed);
474            result.coverage.scan_complete = after.done(seed) && after.unsupported_files == 0;
475            result.coverage.files_remaining = if after.done(seed) {
476                0
477            } else {
478                seed.files.len().saturating_sub(after.file)
479            };
480            let required_bytes = serde_json::to_vec(&result)
481                .expect("relationships serialize")
482                .len();
483            if required_bytes > budget.max_bytes {
484                result.items.pop();
485                if result.items.is_empty() {
486                    return Err(EngineError::PageOutputLimit {
487                        max_bytes: budget.max_bytes,
488                        required_bytes,
489                        anchor: Some(pending.site),
490                    });
491                }
492                result.coverage.stopped_by = Some(RelationshipLimit::Bytes);
493                break;
494            }
495            self = after;
496        }
497        result.coverage.unsupported_files = self.unsupported_files;
498        result.coverage.scan_complete = self.done(seed)
499            && self.unsupported_files == 0
500            && matches!(seed.subject, ResolutionOutcome::Resolved { .. });
501        result.coverage.files_remaining = if self.done(seed) {
502            0
503        } else {
504            seed.files.len().saturating_sub(self.file)
505        };
506        result.next_cursor = self.cursor(engine, session, seed);
507        let required_bytes = serde_json::to_vec(&result)
508            .expect("relationships serialize")
509            .len();
510        if required_bytes > budget.max_bytes {
511            return Err(EngineError::PageOutputLimit {
512                max_bytes: budget.max_bytes,
513                required_bytes,
514                anchor: None,
515            });
516        }
517        if result.next_cursor.is_some() {
518            session.retain(crate::query_store::Checkpoint::Relationships(self));
519        }
520        Ok(crate::PageReply::Relationships(result))
521    }
522}
523
524impl Relationship {
525    fn symbol(site: &SourceAnchor, language: &crate::LanguageId, symbol: &Symbol) -> SymbolRef {
526        SymbolRef {
527            language: language.clone(),
528            declaration: SourceAnchor {
529                path: site.path.clone(),
530                content: site.content.clone(),
531                span: symbol.extent,
532            },
533            name_span: symbol.name_span,
534            kind: symbol.kind,
535        }
536    }
537}
538
539impl crate::report::Document {
540    pub(crate) fn relationships(result: &Relationships) -> Self {
541        use crate::protocol::display::{Line, Role};
542        use crate::protocol::vocabulary::Plural;
543        let mut report = Self::resolution(&crate::ResolutionReply {
544            snapshot: result.snapshot.clone(),
545            outcome: result.subject.clone(),
546        });
547        if !matches!(result.subject, ResolutionOutcome::Resolved { .. }) {
548            return report;
549        }
550        report.block_body(crate::report::Block::Relationships(result.items.clone()));
551        report.notes([Line::single(
552            Role::Dim,
553            format!(
554                "{}; {} scanned; {}",
555                Plural(result.items.len(), "site"),
556                Plural(result.coverage.files_scanned, "file"),
557                Plural(result.coverage.lookups, "lookup")
558            ),
559        )]);
560        if !result.coverage.scan_complete {
561            report.notes([Line::single(
562                Role::Dim,
563                "Candidate scan incomplete; session clients can continue, or narrow the scope or increase the budget",
564            )]);
565        }
566        report.notes([Line::single(Role::Dim, "Unresolved sites are possible relationships, not confirmed calls. Receiver types, indirect targets, and macro expansion are not inferred.")]);
567        report
568    }
569}