Skip to main content

harn_modules/
references.rs

1//! Inverse of [`super::ModuleGraph::definition_of`].
2//!
3//! The graph already records where a name is defined. This module walks
4//! retained ASTs and records every use that resolves to that same
5//! [`super::DefSite`], so find-references and `harn graph` answer from
6//! resolution rather than a bare-string match.
7
8use std::collections::{HashMap, HashSet};
9use std::path::PathBuf;
10
11use harn_lexer::{Lexer, Span, Token, TokenKind};
12use harn_parser::{
13    lexical::{resolved_identifier_bindings_with_source, BindingId, MatchPatternCatalog},
14    visit::walk_program_interpolated,
15    Node,
16};
17
18use super::{DefKind, DefSite, ModuleGraph, ParsedModuleSource};
19
20/// One use of a name that resolved to a [`DefSite`].
21#[derive(Debug, Clone, PartialEq, Eq)]
22pub struct RefSite {
23    pub file: PathBuf,
24    pub span: Span,
25    pub name: String,
26}
27
28/// Resolution-backed reference index for a built module graph.
29///
30/// Built from the same graph that answers go-to-definition. Two same-named
31/// symbols in different modules stay distinct because each use is keyed by
32/// the `DefSite` it resolved to, not by the identifier text.
33#[derive(Debug, Clone, Default)]
34pub struct ReferenceIndex {
35    /// Every file whose AST was walked. A consumer can tell whether the
36    /// answer covers the tree it asked about.
37    pub files: Vec<PathBuf>,
38    /// True when at least one walked file came from an unsaved buffer
39    /// rather than disk. The LSP has those; `harn graph` does not.
40    pub has_unsaved_buffers: bool,
41    by_def: HashMap<DefKey, Vec<RefSite>>,
42    definitions: HashMap<DefKey, DefSite>,
43    site_defs: Vec<(RefSite, DefKey)>,
44}
45
46#[derive(Debug, Clone, PartialEq, Eq, Hash)]
47struct DefKey {
48    file: PathBuf,
49    name: String,
50    start: usize,
51    end: usize,
52}
53
54impl DefKey {
55    fn from_def(def: &DefSite) -> Self {
56        Self {
57            file: def.file.clone(),
58            name: def.name.clone(),
59            start: def.span.start,
60            end: def.span.end,
61        }
62    }
63}
64
65impl ReferenceIndex {
66    /// Definition resolved at one identifier token.
67    ///
68    /// This positional lookup is required for lexical shadowing: a file and
69    /// name alone cannot distinguish a local binding from an imported symbol.
70    pub fn definition_at(
71        &self,
72        file: &std::path::Path,
73        name: &str,
74        offset: usize,
75    ) -> Option<DefSite> {
76        let file = super::canonical_path(file);
77        self.site_defs
78            .iter()
79            .filter(|(site, _)| {
80                site.file == file
81                    && site.name == name
82                    && offset >= site.span.start
83                    && offset <= site.span.end
84            })
85            .min_by_key(|(site, _)| site.span.end.saturating_sub(site.span.start))
86            .and_then(|(_, key)| self.definitions.get(key))
87            .cloned()
88    }
89
90    /// Uses that resolve to `def`, including the definition site itself.
91    pub fn references_to(&self, def: &DefSite) -> Vec<RefSite> {
92        self.by_def
93            .get(&DefKey::from_def(def))
94            .cloned()
95            .unwrap_or_default()
96    }
97
98    /// Every resolved use → definition edge, sorted for deterministic tests
99    /// and `harn graph --json`.
100    pub fn edges(&self) -> Vec<ReferenceEdge> {
101        let mut edges = Vec::new();
102        for (key, refs) in &self.by_def {
103            for site in refs {
104                edges.push(ReferenceEdge {
105                    from: site.clone(),
106                    to_file: key.file.clone(),
107                    to_name: key.name.clone(),
108                });
109            }
110        }
111        sort_edges(&mut edges);
112        edges
113    }
114}
115
116fn sort_edges(edges: &mut [ReferenceEdge]) {
117    edges.sort_by(|left, right| {
118        left.from
119            .file
120            .cmp(&right.from.file)
121            .then_with(|| left.from.span.start.cmp(&right.from.span.start))
122            .then_with(|| left.to_file.cmp(&right.to_file))
123            .then_with(|| left.to_name.cmp(&right.to_name))
124    });
125}
126
127/// One resolution-backed reference edge: a use site and the definition it
128/// resolved to.
129#[derive(Debug, Clone, PartialEq, Eq)]
130pub struct ReferenceEdge {
131    pub from: RefSite,
132    pub to_file: PathBuf,
133    pub to_name: String,
134}
135
136/// Walk `sources` and record every identifier that [`ModuleGraph::definition_of`]
137/// can resolve.
138///
139/// `unsaved` names files whose text came from an editor buffer. The index
140/// reports that so a consumer knows whether it is looking at the file it
141/// just edited.
142pub fn index_references(
143    graph: &ModuleGraph,
144    sources: &HashMap<PathBuf, ParsedModuleSource>,
145    unsaved: &HashSet<PathBuf>,
146) -> ReferenceIndex {
147    let mut files: Vec<PathBuf> = sources.keys().cloned().collect();
148    files.sort();
149    let has_unsaved_buffers = files.iter().any(|file| unsaved.contains(file));
150    let mut index = ReferenceIndex {
151        files,
152        has_unsaved_buffers,
153        by_def: HashMap::new(),
154        definitions: HashMap::new(),
155        site_defs: Vec::new(),
156    };
157
158    walk_resolved_references(graph, sources, |def, site| {
159        insert_reference(&mut index, def, site);
160    });
161
162    for refs in index.by_def.values_mut() {
163        refs.sort_by(|left, right| {
164            left.file
165                .cmp(&right.file)
166                .then_with(|| left.span.start.cmp(&right.span.start))
167        });
168        refs.dedup_by(|left, right| {
169            left.file == right.file
170                && left.span.start == right.span.start
171                && left.name == right.name
172        });
173    }
174    index.site_defs.sort_by(|(left, _), (right, _)| {
175        left.file
176            .cmp(&right.file)
177            .then_with(|| left.span.start.cmp(&right.span.start))
178            .then_with(|| left.name.cmp(&right.name))
179    });
180    index
181        .site_defs
182        .dedup_by(|(left, left_key), (right, right_key)| {
183            left.file == right.file
184                && left.span == right.span
185                && left.name == right.name
186                && left_key == right_key
187        });
188
189    index
190}
191
192/// Resolve the same references as the positional index, retaining only the
193/// first occurrence per source file and definition for file-level graphs.
194pub fn file_reference_edges(
195    graph: &ModuleGraph,
196    sources: &HashMap<PathBuf, ParsedModuleSource>,
197) -> Vec<ReferenceEdge> {
198    let mut targets: HashMap<(PathBuf, DefKey), RefSite> = HashMap::new();
199    walk_resolved_references(graph, sources, |def, site| {
200        let key = (site.file.clone(), DefKey::from_def(&def));
201        targets
202            .entry(key)
203            .and_modify(|first| {
204                if site.span.start < first.span.start {
205                    *first = site.clone();
206                }
207            })
208            .or_insert(site);
209    });
210    let mut edges: Vec<_> = targets
211        .into_iter()
212        .map(|((_, key), from)| ReferenceEdge {
213            from,
214            to_file: key.file,
215            to_name: key.name,
216        })
217        .collect();
218    sort_edges(&mut edges);
219    edges
220}
221
222fn walk_resolved_references(
223    graph: &ModuleGraph,
224    sources: &HashMap<PathBuf, ParsedModuleSource>,
225    mut visit: impl FnMut(DefSite, RefSite),
226) {
227    for (file, parsed) in sources {
228        // The graph is immutable for this pass, so repeated lookups of the
229        // same name in this file resolve identically, including misses.
230        let mut definitions: HashMap<String, Option<DefSite>> = HashMap::new();
231        let mut definition_of = |name: &str| {
232            if let Some(definition) = definitions.get(name) {
233                return definition.clone();
234            }
235            let definition = graph.definition_of(file, name);
236            definitions.insert(name.to_owned(), definition.clone());
237            definition
238        };
239        let lexical = resolved_identifier_bindings_with_source(
240            &[],
241            &parsed.program,
242            Some(&parsed.source),
243            &MatchPatternCatalog::default(),
244        );
245        let tokens = Lexer::new(&parsed.source)
246            .tokenize()
247            .expect("a retained parsed source must still lex");
248
249        // A local declaration may not otherwise appear as an identifier AST
250        // node. Seed every binding reached by a use so include-declaration and
251        // a cursor on the declaration resolve to the same stable identity.
252        let mut lexical_defs: HashMap<BindingId, DefSite> = HashMap::new();
253        for binding in lexical.values() {
254            lexical_defs.entry(binding.clone()).or_insert_with(|| {
255                definition_of(&binding.name)
256                    .filter(|def| {
257                        def.file == *file
258                            && def.span.start == binding.declaration_start
259                            && def.span.end == binding.declaration_end
260                    })
261                    .unwrap_or_else(|| DefSite {
262                        name: binding.name.clone(),
263                        file: file.clone(),
264                        kind: DefKind::Variable,
265                        span: Span::with_offsets(
266                            binding.declaration_start,
267                            binding.declaration_end,
268                            1,
269                            1,
270                        ),
271                    })
272            });
273        }
274        for (binding, def) in &lexical_defs {
275            if let Some(span) = identifier_span(
276                &tokens,
277                &parsed.source,
278                &binding.name,
279                binding.declaration_start,
280                binding.declaration_end,
281                None,
282            ) {
283                visit(
284                    def.clone(),
285                    RefSite {
286                        file: file.clone(),
287                        span,
288                        name: binding.name.clone(),
289                    },
290                );
291            }
292        }
293
294        walk_program_interpolated(&parsed.source, &parsed.program, &mut |node| {
295            for (name, broad_span) in name_uses(node) {
296                let def = lexical
297                    .get(&(broad_span.start, broad_span.end))
298                    .and_then(|binding| lexical_defs.get(binding).cloned())
299                    .or_else(|| definition_of(name));
300                if let (Some(def), Some(span)) = (
301                    def,
302                    identifier_span(
303                        &tokens,
304                        &parsed.source,
305                        name,
306                        broad_span.start,
307                        broad_span.end,
308                        Some((broad_span.line, broad_span.column)),
309                    ),
310                ) {
311                    visit(
312                        def,
313                        RefSite {
314                            file: file.clone(),
315                            span,
316                            name: name.to_string(),
317                        },
318                    );
319                }
320            }
321        });
322    }
323}
324
325fn insert_reference(index: &mut ReferenceIndex, def: DefSite, site: RefSite) {
326    let key = DefKey::from_def(&def);
327    index.definitions.entry(key.clone()).or_insert(def);
328    index
329        .by_def
330        .entry(key.clone())
331        .or_default()
332        .push(site.clone());
333    index.site_defs.push((site, key));
334}
335
336fn identifier_span(
337    tokens: &[Token],
338    source: &str,
339    name: &str,
340    start: usize,
341    end: usize,
342    position: Option<(usize, usize)>,
343) -> Option<Span> {
344    // Lexer tokens are emitted in source order. Skip tokens before the
345    // requested range instead of rescanning the file for every identifier.
346    let first = tokens.partition_point(|token| token.span.start < start);
347    let found = tokens[first..]
348        .iter()
349        .take_while(|token| token.span.start <= end)
350        .find_map(|token| match &token.kind {
351            TokenKind::Identifier(found)
352                if found == name && token.span.start >= start && token.span.end <= end =>
353            {
354                Some(token.span)
355            }
356            _ => None,
357        });
358    if found.is_some() {
359        return found;
360    }
361
362    // Interpolation expressions are nested inside a string token in the
363    // containing file. Re-lex their AST range at its original coordinates.
364    let enclosing = first.checked_sub(1).and_then(|index| tokens.get(index))?;
365    if !matches!(enclosing.kind, TokenKind::InterpolatedString(_)) || end > enclosing.span.end {
366        return None;
367    }
368    let segment = source.get(start..end)?;
369    let (line, column) = if let Some(position) = position {
370        position
371    } else {
372        // Declarations have byte offsets but no line/column in BindingId.
373        // Count only within the containing token, not from the file start.
374        let prefix = source.get(enclosing.span.start..start)?;
375        let lines = prefix.bytes().filter(|byte| *byte == b'\n').count();
376        let column = prefix.rsplit('\n').next()?.chars().count()
377            + if lines == 0 { enclosing.span.column } else { 1 };
378        (enclosing.span.line + lines, column)
379    };
380    Lexer::with_position_and_offset(segment, line, column, start)
381        .tokenize()
382        .ok()?
383        .into_iter()
384        .find_map(|token| match token.kind {
385            TokenKind::Identifier(found) if found == name => Some(token.span),
386            _ => None,
387        })
388}
389
390fn name_uses(node: &harn_parser::SNode) -> Vec<(&str, Span)> {
391    match &node.node {
392        Node::Identifier(name) => vec![(name.as_str(), node.span)],
393        Node::FunctionCall { name, .. } => vec![(name.as_str(), node.span)],
394        Node::FnDecl { name, .. }
395        | Node::Pipeline { name, .. }
396        | Node::ToolDecl { name, .. }
397        | Node::SkillDecl { name, .. }
398        | Node::StructDecl { name, .. }
399        | Node::EnumDecl { name, .. }
400        | Node::InterfaceDecl { name, .. }
401        | Node::TypeDecl { name, .. }
402        | Node::OverrideDecl { name, .. } => vec![(name.as_str(), node.span)],
403        Node::EvalPackDecl { binding_name, .. } => vec![(binding_name.as_str(), node.span)],
404        _ => Vec::new(),
405    }
406}
407
408#[cfg(test)]
409mod identifier_span_tests {
410    use super::*;
411
412    #[test]
413    fn ordered_lookup_matches_linear_lookup_for_all_source_ranges() {
414        let source = "let alpha = 1\nlet βeta = alpha + alpha\nlet text = \"hello {alpha}\"\n";
415        let tokens = Lexer::new(source).tokenize().unwrap();
416        assert!(tokens
417            .windows(2)
418            .all(|pair| pair[0].span.start <= pair[1].span.start));
419        for start in 0..=source.len() {
420            for end in start..=source.len() {
421                for name in ["alpha", "βeta", "text", "absent"] {
422                    let expected = tokens.iter().find_map(|token| match &token.kind {
423                        TokenKind::Identifier(found)
424                            if found == name
425                                && token.span.start >= start
426                                && token.span.end <= end =>
427                        {
428                            Some(token.span)
429                        }
430                        _ => None,
431                    });
432                    assert_eq!(
433                        identifier_span(&tokens, source, name, start, end, None),
434                        expected,
435                        "{name} in {start}..{end}"
436                    );
437                }
438            }
439        }
440    }
441}