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};
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct RefSite {
pub file: PathBuf,
pub span: Span,
pub name: String,
}
#[derive(Debug, Clone, Default)]
pub struct ReferenceIndex {
pub files: Vec<PathBuf>,
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 {
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()
}
pub fn references_to(&self, def: &DefSite) -> Vec<RefSite> {
self.by_def
.get(&DefKey::from_def(def))
.cloned()
.unwrap_or_default()
}
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))
});
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ReferenceEdge {
pub from: RefSite,
pub to_file: PathBuf,
pub to_name: String,
}
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
}
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 {
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");
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> {
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;
}
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 {
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}"
);
}
}
}
}
}