1use 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#[derive(Debug, Clone, PartialEq, Eq)]
22pub struct RefSite {
23 pub file: PathBuf,
24 pub span: Span,
25 pub name: String,
26}
27
28#[derive(Debug, Clone, Default)]
34pub struct ReferenceIndex {
35 pub files: Vec<PathBuf>,
38 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 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 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 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#[derive(Debug, Clone, PartialEq, Eq)]
130pub struct ReferenceEdge {
131 pub from: RefSite,
132 pub to_file: PathBuf,
133 pub to_name: String,
134}
135
136pub 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
192pub 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 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 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 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 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 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}