harn-modules 0.10.196

Cross-file module graph and import resolution utilities for Harn
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
//! Inverse of [`super::ModuleGraph::definition_of`].
//!
//! The graph already records where a name is defined. This module walks
//! retained ASTs and records every use that resolves to that same
//! [`super::DefSite`], so find-references and `harn graph` answer from
//! resolution rather than a bare-string match.

use std::collections::{HashMap, HashSet};
use std::path::PathBuf;

use harn_lexer::{Lexer, Span, Token, TokenKind};
use harn_parser::{
    lexical::{resolved_identifier_bindings_with_source, BindingId, MatchPatternCatalog},
    visit::walk_program_interpolated,
    Node,
};

use super::{DefKind, DefSite, ModuleGraph, ParsedModuleSource};

/// One use of a name that resolved to a [`DefSite`].
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct RefSite {
    pub file: PathBuf,
    pub span: Span,
    pub name: String,
}

/// Resolution-backed reference index for a built module graph.
///
/// Built from the same graph that answers go-to-definition. Two same-named
/// symbols in different modules stay distinct because each use is keyed by
/// the `DefSite` it resolved to, not by the identifier text.
#[derive(Debug, Clone, Default)]
pub struct ReferenceIndex {
    /// Every file whose AST was walked. A consumer can tell whether the
    /// answer covers the tree it asked about.
    pub files: Vec<PathBuf>,
    /// True when at least one walked file came from an unsaved buffer
    /// rather than disk. The LSP has those; `harn graph` does not.
    pub has_unsaved_buffers: bool,
    by_def: HashMap<DefKey, Vec<RefSite>>,
    definitions: HashMap<DefKey, DefSite>,
    site_defs: Vec<(RefSite, DefKey)>,
}

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct DefKey {
    file: PathBuf,
    name: String,
    start: usize,
    end: usize,
}

impl DefKey {
    fn from_def(def: &DefSite) -> Self {
        Self {
            file: def.file.clone(),
            name: def.name.clone(),
            start: def.span.start,
            end: def.span.end,
        }
    }
}

impl ReferenceIndex {
    /// Definition resolved at one identifier token.
    ///
    /// This positional lookup is required for lexical shadowing: a file and
    /// name alone cannot distinguish a local binding from an imported symbol.
    pub fn definition_at(
        &self,
        file: &std::path::Path,
        name: &str,
        offset: usize,
    ) -> Option<DefSite> {
        let file = super::canonical_path(file);
        self.site_defs
            .iter()
            .filter(|(site, _)| {
                site.file == file
                    && site.name == name
                    && offset >= site.span.start
                    && offset <= site.span.end
            })
            .min_by_key(|(site, _)| site.span.end.saturating_sub(site.span.start))
            .and_then(|(_, key)| self.definitions.get(key))
            .cloned()
    }

    /// Uses that resolve to `def`, including the definition site itself.
    pub fn references_to(&self, def: &DefSite) -> Vec<RefSite> {
        self.by_def
            .get(&DefKey::from_def(def))
            .cloned()
            .unwrap_or_default()
    }

    /// Every resolved use → definition edge, sorted for deterministic tests
    /// and `harn graph --json`.
    pub fn edges(&self) -> Vec<ReferenceEdge> {
        let mut edges = Vec::new();
        for (key, refs) in &self.by_def {
            for site in refs {
                edges.push(ReferenceEdge {
                    from: site.clone(),
                    to_file: key.file.clone(),
                    to_name: key.name.clone(),
                });
            }
        }
        sort_edges(&mut edges);
        edges
    }
}

fn sort_edges(edges: &mut [ReferenceEdge]) {
    edges.sort_by(|left, right| {
        left.from
            .file
            .cmp(&right.from.file)
            .then_with(|| left.from.span.start.cmp(&right.from.span.start))
            .then_with(|| left.to_file.cmp(&right.to_file))
            .then_with(|| left.to_name.cmp(&right.to_name))
    });
}

/// One resolution-backed reference edge: a use site and the definition it
/// resolved to.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ReferenceEdge {
    pub from: RefSite,
    pub to_file: PathBuf,
    pub to_name: String,
}

/// Walk `sources` and record every identifier that [`ModuleGraph::definition_of`]
/// can resolve.
///
/// `unsaved` names files whose text came from an editor buffer. The index
/// reports that so a consumer knows whether it is looking at the file it
/// just edited.
pub fn index_references(
    graph: &ModuleGraph,
    sources: &HashMap<PathBuf, ParsedModuleSource>,
    unsaved: &HashSet<PathBuf>,
) -> ReferenceIndex {
    let mut files: Vec<PathBuf> = sources.keys().cloned().collect();
    files.sort();
    let has_unsaved_buffers = files.iter().any(|file| unsaved.contains(file));
    let mut index = ReferenceIndex {
        files,
        has_unsaved_buffers,
        by_def: HashMap::new(),
        definitions: HashMap::new(),
        site_defs: Vec::new(),
    };

    walk_resolved_references(graph, sources, |def, site| {
        insert_reference(&mut index, def, site);
    });

    for refs in index.by_def.values_mut() {
        refs.sort_by(|left, right| {
            left.file
                .cmp(&right.file)
                .then_with(|| left.span.start.cmp(&right.span.start))
        });
        refs.dedup_by(|left, right| {
            left.file == right.file
                && left.span.start == right.span.start
                && left.name == right.name
        });
    }
    index.site_defs.sort_by(|(left, _), (right, _)| {
        left.file
            .cmp(&right.file)
            .then_with(|| left.span.start.cmp(&right.span.start))
            .then_with(|| left.name.cmp(&right.name))
    });
    index
        .site_defs
        .dedup_by(|(left, left_key), (right, right_key)| {
            left.file == right.file
                && left.span == right.span
                && left.name == right.name
                && left_key == right_key
        });

    index
}

/// Resolve the same references as the positional index, retaining only the
/// first occurrence per source file and definition for file-level graphs.
pub fn file_reference_edges(
    graph: &ModuleGraph,
    sources: &HashMap<PathBuf, ParsedModuleSource>,
) -> Vec<ReferenceEdge> {
    let mut targets: HashMap<(PathBuf, DefKey), RefSite> = HashMap::new();
    walk_resolved_references(graph, sources, |def, site| {
        let key = (site.file.clone(), DefKey::from_def(&def));
        targets
            .entry(key)
            .and_modify(|first| {
                if site.span.start < first.span.start {
                    *first = site.clone();
                }
            })
            .or_insert(site);
    });
    let mut edges: Vec<_> = targets
        .into_iter()
        .map(|((_, key), from)| ReferenceEdge {
            from,
            to_file: key.file,
            to_name: key.name,
        })
        .collect();
    sort_edges(&mut edges);
    edges
}

fn walk_resolved_references(
    graph: &ModuleGraph,
    sources: &HashMap<PathBuf, ParsedModuleSource>,
    mut visit: impl FnMut(DefSite, RefSite),
) {
    for (file, parsed) in sources {
        // The graph is immutable for this pass, so repeated lookups of the
        // same name in this file resolve identically, including misses.
        let mut definitions: HashMap<String, Option<DefSite>> = HashMap::new();
        let mut definition_of = |name: &str| {
            if let Some(definition) = definitions.get(name) {
                return definition.clone();
            }
            let definition = graph.definition_of(file, name);
            definitions.insert(name.to_owned(), definition.clone());
            definition
        };
        let lexical = resolved_identifier_bindings_with_source(
            &[],
            &parsed.program,
            Some(&parsed.source),
            &MatchPatternCatalog::default(),
        );
        let tokens = Lexer::new(&parsed.source)
            .tokenize()
            .expect("a retained parsed source must still lex");

        // A local declaration may not otherwise appear as an identifier AST
        // node. Seed every binding reached by a use so include-declaration and
        // a cursor on the declaration resolve to the same stable identity.
        let mut lexical_defs: HashMap<BindingId, DefSite> = HashMap::new();
        for binding in lexical.values() {
            lexical_defs.entry(binding.clone()).or_insert_with(|| {
                definition_of(&binding.name)
                    .filter(|def| {
                        def.file == *file
                            && def.span.start == binding.declaration_start
                            && def.span.end == binding.declaration_end
                    })
                    .unwrap_or_else(|| DefSite {
                        name: binding.name.clone(),
                        file: file.clone(),
                        kind: DefKind::Variable,
                        span: Span::with_offsets(
                            binding.declaration_start,
                            binding.declaration_end,
                            1,
                            1,
                        ),
                    })
            });
        }
        for (binding, def) in &lexical_defs {
            if let Some(span) = identifier_span(
                &tokens,
                &parsed.source,
                &binding.name,
                binding.declaration_start,
                binding.declaration_end,
                None,
            ) {
                visit(
                    def.clone(),
                    RefSite {
                        file: file.clone(),
                        span,
                        name: binding.name.clone(),
                    },
                );
            }
        }

        walk_program_interpolated(&parsed.source, &parsed.program, &mut |node| {
            for (name, broad_span) in name_uses(node) {
                let def = lexical
                    .get(&(broad_span.start, broad_span.end))
                    .and_then(|binding| lexical_defs.get(binding).cloned())
                    .or_else(|| definition_of(name));
                if let (Some(def), Some(span)) = (
                    def,
                    identifier_span(
                        &tokens,
                        &parsed.source,
                        name,
                        broad_span.start,
                        broad_span.end,
                        Some((broad_span.line, broad_span.column)),
                    ),
                ) {
                    visit(
                        def,
                        RefSite {
                            file: file.clone(),
                            span,
                            name: name.to_string(),
                        },
                    );
                }
            }
        });
    }
}

fn insert_reference(index: &mut ReferenceIndex, def: DefSite, site: RefSite) {
    let key = DefKey::from_def(&def);
    index.definitions.entry(key.clone()).or_insert(def);
    index
        .by_def
        .entry(key.clone())
        .or_default()
        .push(site.clone());
    index.site_defs.push((site, key));
}

fn identifier_span(
    tokens: &[Token],
    source: &str,
    name: &str,
    start: usize,
    end: usize,
    position: Option<(usize, usize)>,
) -> Option<Span> {
    // Lexer tokens are emitted in source order. Skip tokens before the
    // requested range instead of rescanning the file for every identifier.
    let first = tokens.partition_point(|token| token.span.start < start);
    let found = tokens[first..]
        .iter()
        .take_while(|token| token.span.start <= end)
        .find_map(|token| match &token.kind {
            TokenKind::Identifier(found)
                if found == name && token.span.start >= start && token.span.end <= end =>
            {
                Some(token.span)
            }
            _ => None,
        });
    if found.is_some() {
        return found;
    }

    // Interpolation expressions are nested inside a string token in the
    // containing file. Re-lex their AST range at its original coordinates.
    let enclosing = first.checked_sub(1).and_then(|index| tokens.get(index))?;
    if !matches!(enclosing.kind, TokenKind::InterpolatedString(_)) || end > enclosing.span.end {
        return None;
    }
    let segment = source.get(start..end)?;
    let (line, column) = if let Some(position) = position {
        position
    } else {
        // Declarations have byte offsets but no line/column in BindingId.
        // Count only within the containing token, not from the file start.
        let prefix = source.get(enclosing.span.start..start)?;
        let lines = prefix.bytes().filter(|byte| *byte == b'\n').count();
        let column = prefix.rsplit('\n').next()?.chars().count()
            + if lines == 0 { enclosing.span.column } else { 1 };
        (enclosing.span.line + lines, column)
    };
    Lexer::with_position_and_offset(segment, line, column, start)
        .tokenize()
        .ok()?
        .into_iter()
        .find_map(|token| match token.kind {
            TokenKind::Identifier(found) if found == name => Some(token.span),
            _ => None,
        })
}

fn name_uses(node: &harn_parser::SNode) -> Vec<(&str, Span)> {
    match &node.node {
        Node::Identifier(name) => vec![(name.as_str(), node.span)],
        Node::FunctionCall { name, .. } => vec![(name.as_str(), node.span)],
        Node::FnDecl { name, .. }
        | Node::Pipeline { name, .. }
        | Node::ToolDecl { name, .. }
        | Node::SkillDecl { name, .. }
        | Node::StructDecl { name, .. }
        | Node::EnumDecl { name, .. }
        | Node::InterfaceDecl { name, .. }
        | Node::TypeDecl { name, .. }
        | Node::OverrideDecl { name, .. } => vec![(name.as_str(), node.span)],
        Node::EvalPackDecl { binding_name, .. } => vec![(binding_name.as_str(), node.span)],
        _ => Vec::new(),
    }
}

#[cfg(test)]
mod identifier_span_tests {
    use super::*;

    #[test]
    fn ordered_lookup_matches_linear_lookup_for_all_source_ranges() {
        let source = "let alpha = 1\nlet βeta = alpha + alpha\nlet text = \"hello {alpha}\"\n";
        let tokens = Lexer::new(source).tokenize().unwrap();
        assert!(tokens
            .windows(2)
            .all(|pair| pair[0].span.start <= pair[1].span.start));
        for start in 0..=source.len() {
            for end in start..=source.len() {
                for name in ["alpha", "βeta", "text", "absent"] {
                    let expected = tokens.iter().find_map(|token| match &token.kind {
                        TokenKind::Identifier(found)
                            if found == name
                                && token.span.start >= start
                                && token.span.end <= end =>
                        {
                            Some(token.span)
                        }
                        _ => None,
                    });
                    assert_eq!(
                        identifier_span(&tokens, source, name, start, end, None),
                        expected,
                        "{name} in {start}..{end}"
                    );
                }
            }
        }
    }
}