summaryrefslogtreecommitdiff
path: root/stag
diff options
context:
space:
mode:
Diffstat (limited to 'stag')
-rw-r--r--stag/Cargo.toml16
-rw-r--r--stag/src/main.rs810
-rw-r--r--stag/src/scopes.scm463
-rw-r--r--stag/src/stag.scm36
-rw-r--r--stag/src/text_range.rs121
5 files changed, 1446 insertions, 0 deletions
diff --git a/stag/Cargo.toml b/stag/Cargo.toml
new file mode 100644
index 0000000..24f07e0
--- /dev/null
+++ b/stag/Cargo.toml
@@ -0,0 +1,16 @@
1[package]
2name = "stag"
3version = "0.1.0"
4edition = "2021"
5
6# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
7
8[dependencies]
9petgraph = { version = "0.6.4", default-features = false, features = ["serde-1"] }
10serde = {version = "1.0.188", features = ["derive"]}
11once_cell = "1.19.0"
12thiserror = "1.0.56"
13tree-sitter-graph = { path = "../tree-sitter-graph/"}
14tree-sitter-rust = "0.20.4"
15tree-sitter = "0.20.10"
16
diff --git a/stag/src/main.rs b/stag/src/main.rs
new file mode 100644
index 0000000..eae6fe9
--- /dev/null
+++ b/stag/src/main.rs
@@ -0,0 +1,810 @@
1use std::collections::VecDeque;
2
3use serde::Deserialize;
4use serde::Serialize;
5use tree_sitter::Parser;
6use tree_sitter_graph::ast::File;
7use tree_sitter_graph::functions::{Function, Functions};
8use tree_sitter_graph::graph::Value;
9use tree_sitter_graph::ExecutionConfig;
10use tree_sitter_graph::ExecutionError;
11use tree_sitter_graph::Identifier;
12use tree_sitter_graph::NoCancellation;
13use tree_sitter_graph::Variables;
14
15mod text_range;
16use text_range::TextRange;
17
18use petgraph::{graph::NodeIndex, visit::EdgeRef, Direction, Graph};
19
20fn main() {
21 let scopes = std::fs::read_to_string("src/stag.scm").unwrap();
22 let src = r#"fn main() {
23 let a = 3;
24 let b = 4;
25 a + b
26}
27 "#;
28
29 let mut parser = Parser::new();
30 let language = tree_sitter_rust::language();
31 parser.set_language(language).unwrap();
32 let tree = parser.parse(src.as_bytes(), None).unwrap();
33
34 let file = File::from_str(language, &scopes).unwrap();
35
36 let mut functions = Functions::stdlib();
37 functions.add(Identifier::from("scope"), ScopeShorthand);
38 functions.add(Identifier::from("def"), DefShorthand);
39 functions.add(Identifier::from("ref"), RefShortHand);
40 functions.add(Identifier::from("cover"), CoverRanges);
41 functions.add(Identifier::from("range"), NodeRange);
42
43 let mut globals = Variables::new();
44 globals
45 .add(Identifier::from("filename"), "test.rs".into())
46 .map_err(|_| ExecutionError::DuplicateVariable("filename".into()))
47 .unwrap();
48
49 let config = ExecutionConfig::new(&functions, &globals);
50
51 let graph = file.execute(&tree, &src, &config, &NoCancellation).unwrap();
52
53 let mut sg = ScopeGraph::new(tree.root_node().range().into());
54
55 sg = build_scope_graph(graph, sg);
56
57 println!("{:#?}", sg);
58}
59
60fn range_to_value(value: &tree_sitter::Range) -> Value {
61 let start = Value::from(vec![
62 Value::from(value.start_byte as u32),
63 Value::from(value.start_point.row as u32),
64 Value::from(value.start_point.column as u32),
65 ]);
66 let end = Value::from(vec![
67 Value::from(value.end_byte as u32),
68 Value::from(value.end_point.row as u32),
69 Value::from(value.end_point.column as u32),
70 ]);
71 Value::from(vec![start, end])
72}
73
74fn value_to_range(value: &Value) -> tree_sitter::Range {
75 let range = value.as_list().unwrap();
76 let start = range[0].as_list().unwrap();
77 let end = range[1].as_list().unwrap();
78 tree_sitter::Range {
79 start_byte: start[0].as_integer().unwrap() as usize,
80 start_point: tree_sitter::Point {
81 row: start[1].as_integer().unwrap() as usize,
82 column: start[2].as_integer().unwrap() as usize,
83 },
84 end_byte: end[0].as_integer().unwrap() as usize,
85 end_point: tree_sitter::Point {
86 row: end[1].as_integer().unwrap() as usize,
87 column: end[2].as_integer().unwrap() as usize,
88 },
89 }
90}
91
92fn is_string_attr(node: &tree_sitter_graph::graph::GraphNode, key: &str, value: &str) -> bool {
93 matches!(node.attributes.get(&Identifier::from(key)).and_then(|v| v.as_str().ok()), Some(v) if v == value)
94}
95
96fn is_scope(node: &tree_sitter_graph::graph::GraphNode) -> bool {
97 is_string_attr(node, "kind", "scope")
98}
99
100fn is_import(node: &tree_sitter_graph::graph::GraphNode) -> bool {
101 is_string_attr(node, "kind", "import")
102}
103
104fn is_def(node: &tree_sitter_graph::graph::GraphNode) -> bool {
105 is_string_attr(node, "kind", "def")
106}
107
108fn is_ref(node: &tree_sitter_graph::graph::GraphNode) -> bool {
109 is_string_attr(node, "kind", "ref")
110}
111
112pub struct ScopeShorthand;
113
114impl Function for ScopeShorthand {
115 fn call(
116 &self,
117 graph: &mut tree_sitter_graph::graph::Graph,
118 source: &str,
119 parameters: &mut dyn tree_sitter_graph::functions::Parameters,
120 ) -> Result<tree_sitter_graph::graph::Value, ExecutionError> {
121 let target_range = parameters.param()?;
122 if target_range.as_list().is_err() {
123 return Err(ExecutionError::ExpectedList(format!(
124 "`scope` expects list"
125 )));
126 }
127 parameters.finish()?;
128
129 let graph_node = graph.add_graph_node();
130 graph[graph_node]
131 .attributes
132 .add::<String>(Identifier::from("kind"), "scope".into());
133 graph[graph_node]
134 .attributes
135 .add(Identifier::from("range"), target_range);
136
137 Ok(tree_sitter_graph::graph::Value::GraphNode(graph_node))
138 }
139}
140
141pub struct DefShorthand;
142
143impl Function for DefShorthand {
144 fn call(
145 &self,
146 graph: &mut tree_sitter_graph::graph::Graph,
147 source: &str,
148 parameters: &mut dyn tree_sitter_graph::functions::Parameters,
149 ) -> Result<tree_sitter_graph::graph::Value, ExecutionError> {
150 let target_node = parameters.param()?.into_syntax_node_ref()?;
151 let ts_node = graph[target_node];
152 parameters.finish()?;
153
154 let graph_node = graph.add_graph_node();
155 graph[graph_node]
156 .attributes
157 .add::<String>(Identifier::from("kind"), "def".into());
158 graph[graph_node]
159 .attributes
160 .add::<String>(Identifier::from("scope"), "local".into());
161 graph[graph_node].attributes.add::<String>(
162 Identifier::from("text"),
163 source[ts_node.byte_range()].to_string().into(),
164 );
165 graph[graph_node]
166 .attributes
167 .add(Identifier::from("range"), range_to_value(&ts_node.range()));
168 graph[graph_node]
169 .attributes
170 .add::<tree_sitter_graph::graph::SyntaxNodeRef>(
171 Identifier::from("target"),
172 target_node.into(),
173 );
174
175 Ok(tree_sitter_graph::graph::Value::GraphNode(graph_node))
176 }
177}
178
179pub struct RefShortHand;
180
181impl Function for RefShortHand {
182 fn call(
183 &self,
184 graph: &mut tree_sitter_graph::graph::Graph,
185 source: &str,
186 parameters: &mut dyn tree_sitter_graph::functions::Parameters,
187 ) -> Result<tree_sitter_graph::graph::Value, ExecutionError> {
188 let target_node = parameters.param()?.into_syntax_node_ref()?;
189 let ts_node = graph[target_node];
190 parameters.finish()?;
191
192 let graph_node = graph.add_graph_node();
193 graph[graph_node]
194 .attributes
195 .add::<String>(Identifier::from("kind"), "ref".into());
196 graph[graph_node].attributes.add::<String>(
197 Identifier::from("text"),
198 source[ts_node.byte_range()].to_string().into(),
199 );
200 graph[graph_node]
201 .attributes
202 .add(Identifier::from("range"), range_to_value(&ts_node.range()));
203 graph[graph_node]
204 .attributes
205 .add::<tree_sitter_graph::graph::SyntaxNodeRef>(
206 Identifier::from("target"),
207 target_node.into(),
208 );
209
210 Ok(tree_sitter_graph::graph::Value::GraphNode(graph_node))
211 }
212}
213
214pub struct CoverRanges;
215
216impl Function for CoverRanges {
217 fn call(
218 &self,
219 graph: &mut tree_sitter_graph::graph::Graph,
220 _source: &str,
221 parameters: &mut dyn tree_sitter_graph::functions::Parameters,
222 ) -> Result<tree_sitter_graph::graph::Value, ExecutionError> {
223 let node_a = parameters.param()?.into_syntax_node_ref()?;
224 let node_b = parameters.param()?.into_syntax_node_ref()?;
225 let ts_node_a = graph[node_a];
226 let ts_node_b = graph[node_b];
227
228 let mut range = cover(ts_node_a.range(), ts_node_b.range());
229 while let Ok(param) = parameters.param() {
230 range = cover(range, graph[param.into_syntax_node_ref()?].range())
231 }
232
233 Ok(range_to_value(&range))
234 }
235}
236
237fn cover(a: tree_sitter::Range, b: tree_sitter::Range) -> tree_sitter::Range {
238 let (start_byte, start_point) = if a.start_point < b.start_point {
239 (a.start_byte, a.start_point)
240 } else {
241 (b.start_byte, b.start_point)
242 };
243 let (end_byte, end_point) = if a.end_point > b.end_point {
244 (a.end_byte, a.end_point)
245 } else {
246 (b.end_byte, b.end_point)
247 };
248 tree_sitter::Range {
249 start_byte,
250 start_point,
251 end_byte,
252 end_point,
253 }
254}
255
256pub struct NodeRange;
257
258impl Function for NodeRange {
259 fn call(
260 &self,
261 graph: &mut tree_sitter_graph::graph::Graph,
262 _source: &str,
263 parameters: &mut dyn tree_sitter_graph::functions::Parameters,
264 ) -> Result<tree_sitter_graph::graph::Value, ExecutionError> {
265 let target_node = parameters.param()?.into_syntax_node_ref()?;
266 let ts_node = graph[target_node];
267 Ok(range_to_value(&ts_node.range()))
268 }
269}
270
271#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq, Hash)]
272pub struct LocalDef {
273 pub range: TextRange,
274 pub text: String,
275 pub symbol: Option<String>,
276}
277
278impl LocalDef {
279 /// Initialize a new definition
280 pub fn new(range: TextRange, text: String, symbol: Option<String>) -> Self {
281 Self {
282 range,
283 text,
284 symbol,
285 }
286 }
287
288 pub fn name<'a>(&self, buffer: &'a [u8]) -> &'a [u8] {
289 &buffer[self.range.start.byte..self.range.end.byte]
290 }
291}
292
293#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq, Hash)]
294pub struct LocalImport {
295 pub range: TextRange,
296 pub text: String,
297}
298
299impl LocalImport {
300 /// Initialize a new import
301 pub fn new(range: TextRange, text: String) -> Self {
302 Self { range, text }
303 }
304
305 pub fn name<'a>(&self, buffer: &'a [u8]) -> &'a [u8] {
306 &buffer[self.range.start.byte..self.range.end.byte]
307 }
308}
309
310#[derive(Debug, Clone, Serialize, Deserialize)]
311pub struct Reference {
312 pub range: TextRange,
313 pub text: String,
314 pub symbol: Option<String>,
315}
316
317impl Reference {
318 /// Initialize a new reference
319 pub fn new(range: TextRange, text: String, symbol: Option<String>) -> Self {
320 Self {
321 range,
322 text,
323 symbol,
324 }
325 }
326}
327
328#[derive(Debug, Clone, Copy, Serialize, Deserialize)]
329pub struct LocalScope {
330 pub range: TextRange,
331}
332
333impl LocalScope {
334 pub fn new(range: TextRange) -> Self {
335 Self { range }
336 }
337}
338
339pub struct ScopeStack<'a> {
340 pub scope_graph: &'a ScopeGraph,
341 pub start: Option<NodeIndex<u32>>,
342}
343
344impl<'a> Iterator for ScopeStack<'a> {
345 type Item = NodeIndex<u32>;
346 fn next(&mut self) -> Option<Self::Item> {
347 if let Some(start) = self.start {
348 let parent = self
349 .scope_graph
350 .graph
351 .edges_directed(start, Direction::Outgoing)
352 .find(|edge| *edge.weight() == EdgeKind::ScopeToScope)
353 .map(|edge| edge.target());
354 let original = start;
355 self.start = parent;
356 Some(original)
357 } else {
358 None
359 }
360 }
361}
362
363/// The type of a node in the ScopeGraph
364#[derive(Serialize, Deserialize, Debug, Clone)]
365pub enum NodeKind {
366 /// A scope node
367 Scope(LocalScope),
368
369 /// A definition node
370 Def(LocalDef),
371
372 /// An import node
373 Import(LocalImport),
374
375 /// A reference node
376 Ref(Reference),
377}
378
379impl NodeKind {
380 /// Construct a scope node from a range
381 pub fn scope(range: TextRange) -> Self {
382 Self::Scope(LocalScope::new(range))
383 }
384
385 /// Produce the range spanned by this node
386 pub fn range(&self) -> TextRange {
387 match self {
388 Self::Scope(l) => l.range,
389 Self::Def(d) => d.range,
390 Self::Ref(r) => r.range,
391 Self::Import(i) => i.range,
392 }
393 }
394}
395
396/// Describes the relation between two nodes in the ScopeGraph
397#[derive(Serialize, Deserialize, PartialEq, Eq, Copy, Clone, Debug)]
398pub enum EdgeKind {
399 /// The edge weight from a nested scope to its parent scope
400 ScopeToScope,
401
402 /// The edge weight from a definition to its definition scope
403 DefToScope,
404
405 /// The edge weight from an import to its definition scope
406 ImportToScope,
407
408 /// The edge weight from a reference to its definition
409 RefToDef,
410
411 /// The edge weight from a reference to its import
412 RefToImport,
413}
414
415/// A graph representation of scopes and names in a single syntax tree
416#[derive(Debug, Serialize, Deserialize, Clone)]
417pub struct ScopeGraph {
418 /// The raw graph
419 pub graph: Graph<NodeKind, EdgeKind>,
420
421 // Graphs do not have the concept of a `root`, but lexical scopes follow the syntax
422 // tree, and as a result, have a "root" node. The root_idx points to a scope node that
423 // encompasses the entire file: the file-global scope.
424 root_idx: NodeIndex,
425}
426
427impl ScopeGraph {
428 pub fn new(range: TextRange) -> Self {
429 let mut graph = Graph::new();
430 let root_idx = graph.add_node(NodeKind::scope(range));
431 Self { graph, root_idx }
432 }
433
434 pub fn get_node(&self, node_idx: NodeIndex) -> Option<&NodeKind> {
435 self.graph.node_weight(node_idx)
436 }
437
438 /// Insert a local scope into the scope-graph
439 pub fn insert_local_scope(&mut self, new: LocalScope) {
440 if let Some(parent_scope) = self.scope_by_range(new.range, self.root_idx) {
441 let new_scope = NodeKind::Scope(new);
442 let new_idx = self.graph.add_node(new_scope);
443 self.graph
444 .add_edge(new_idx, parent_scope, EdgeKind::ScopeToScope);
445 }
446 }
447
448 /// Insert a def into the scope-graph
449 pub fn insert_local_def(&mut self, new: LocalDef) {
450 if let Some(defining_scope) = self.scope_by_range(new.range, self.root_idx) {
451 let new_def = NodeKind::Def(new);
452 let new_idx = self.graph.add_node(new_def);
453 self.graph
454 .add_edge(new_idx, defining_scope, EdgeKind::DefToScope);
455 }
456 }
457
458 /// Insert a def into the scope-graph, at the parent scope of the defining scope
459 pub fn insert_hoisted_def(&mut self, new: LocalDef) {
460 if let Some(defining_scope) = self.scope_by_range(new.range, self.root_idx) {
461 let new_def = NodeKind::Def(new);
462 let new_idx = self.graph.add_node(new_def);
463
464 // if the parent scope exists, insert this def there, if not,
465 // insert into the defining scope
466 let target_scope = self.parent_scope(defining_scope).unwrap_or(defining_scope);
467
468 self.graph
469 .add_edge(new_idx, target_scope, EdgeKind::DefToScope);
470 }
471 }
472
473 /// Insert a def into the scope-graph, at the root scope
474 pub fn insert_global_def(&mut self, new: LocalDef) {
475 let new_def = NodeKind::Def(new);
476 let new_idx = self.graph.add_node(new_def);
477 self.graph
478 .add_edge(new_idx, self.root_idx, EdgeKind::DefToScope);
479 }
480
481 /// Insert an import into the scope-graph
482 pub fn insert_local_import(&mut self, new: LocalImport) {
483 if let Some(defining_scope) = self.scope_by_range(new.range, self.root_idx) {
484 let new_imp = NodeKind::Import(new);
485 let new_idx = self.graph.add_node(new_imp);
486 self.graph
487 .add_edge(new_idx, defining_scope, EdgeKind::ImportToScope);
488 }
489 }
490
491 /// Insert a ref into the scope-graph
492 pub fn insert_ref(&mut self, new: Reference) {
493 let mut possible_defs = vec![];
494 let mut possible_imports = vec![];
495 if let Some(local_scope_idx) = self.scope_by_range(new.range, self.root_idx) {
496 // traverse the scopes from the current-scope to the root-scope
497 for scope in self.scope_stack(local_scope_idx) {
498 // find candidate definitions in each scope
499 for local_def in self
500 .graph
501 .edges_directed(scope, Direction::Incoming)
502 .filter(|edge| *edge.weight() == EdgeKind::DefToScope)
503 .map(|edge| edge.source())
504 {
505 if let NodeKind::Def(def) = &self.graph[local_def] {
506 if new.text == def.text {
507 match (def.symbol.as_ref(), new.symbol.as_ref()) {
508 // both contain symbols, but they don't belong to the same namepspace
509 (Some(d), Some(r)) if d != r => {}
510
511 // in all other cases, form an edge from the ref to def.
512 // an empty symbol belongs to all namespaces:
513 // * (None, None)
514 // * (None, Some(_))
515 // * (Some(_), None)
516 // * (Some(_), Some(_)) if def.namespace == ref.namespace
517 _ => {
518 possible_defs.push(local_def);
519 }
520 };
521 }
522 }
523 }
524
525 // find candidate imports in each scope
526 for local_import in self
527 .graph
528 .edges_directed(scope, Direction::Incoming)
529 .filter(|edge| *edge.weight() == EdgeKind::ImportToScope)
530 .map(|edge| edge.source())
531 {
532 if let NodeKind::Import(import) = &self.graph[local_import] {
533 if new.text == import.text {
534 possible_imports.push(local_import);
535 }
536 }
537 }
538 }
539 }
540
541 if !possible_defs.is_empty() || !possible_imports.is_empty() {
542 let new_ref = NodeKind::Ref(new);
543 let ref_idx = self.graph.add_node(new_ref);
544 for def_idx in possible_defs {
545 self.graph.add_edge(ref_idx, def_idx, EdgeKind::RefToDef);
546 }
547 for imp_idx in possible_imports {
548 self.graph.add_edge(ref_idx, imp_idx, EdgeKind::RefToImport);
549 }
550 }
551 }
552
553 fn scope_stack(&self, start: NodeIndex) -> ScopeStack<'_> {
554 ScopeStack {
555 scope_graph: self,
556 start: Some(start),
557 }
558 }
559
560 // The smallest scope that encompasses `range`. Start at `start` and narrow down if possible.
561 fn scope_by_range(&self, range: TextRange, start: NodeIndex) -> Option<NodeIndex> {
562 let target_range = self.graph[start].range();
563 if target_range.contains(&range) {
564 let mut child_scopes = self
565 .graph
566 .edges_directed(start, Direction::Incoming)
567 .filter(|edge| *edge.weight() == EdgeKind::ScopeToScope)
568 .map(|edge| edge.source())
569 .collect::<Vec<_>>();
570
571 child_scopes.sort_by_key(|s| self.graph[*s].range());
572 let target_child_scope = child_scopes.binary_search_by(|x| {
573 if self.graph[*x].range().contains(&range) {
574 std::cmp::Ordering::Equal
575 } else {
576 self.graph[*x].range().cmp(&range)
577 }
578 });
579
580 if let Some(t) = target_child_scope
581 .ok()
582 .and_then(|idx| child_scopes.get(idx))
583 .and_then(|s| self.scope_by_range(range, *s))
584 {
585 return Some(t);
586 } else {
587 return Some(start);
588 }
589 }
590 None
591 }
592
593 // Produce the parent scope of a given scope
594 fn parent_scope(&self, start: NodeIndex) -> Option<NodeIndex> {
595 if matches!(self.graph[start], NodeKind::Scope(_)) {
596 return self
597 .graph
598 .edges_directed(start, Direction::Outgoing)
599 .filter(|edge| *edge.weight() == EdgeKind::ScopeToScope)
600 .map(|edge| edge.target())
601 .next();
602 }
603 None
604 }
605
606 /// Produce a list of interesting ranges: ranges of defs and refs
607 pub fn hoverable_ranges(&self) -> Box<dyn Iterator<Item = TextRange> + '_> {
608 let iterator =
609 self.graph
610 .node_indices()
611 .filter_map(|node_idx| match &self.graph[node_idx] {
612 NodeKind::Scope(_) => None,
613 NodeKind::Def(d) => Some(d.range),
614 NodeKind::Ref(r) => Some(r.range),
615 NodeKind::Import(i) => Some(i.range),
616 });
617 Box::new(iterator)
618 }
619
620 /// Produce possible definitions for a reference
621 pub fn definitions(
622 &self,
623 reference_node: NodeIndex,
624 ) -> Box<dyn Iterator<Item = NodeIndex> + '_> {
625 let iterator = self
626 .graph
627 .edges_directed(reference_node, Direction::Outgoing)
628 .filter(|edge| *edge.weight() == EdgeKind::RefToDef)
629 .map(|edge| edge.target());
630 Box::new(iterator)
631 }
632
633 /// Produce possible imports for a reference
634 pub fn imports(&self, reference_node: NodeIndex) -> Box<dyn Iterator<Item = NodeIndex> + '_> {
635 let iterator = self
636 .graph
637 .edges_directed(reference_node, Direction::Outgoing)
638 .filter(|edge| *edge.weight() == EdgeKind::RefToImport)
639 .map(|edge| edge.target());
640 Box::new(iterator)
641 }
642
643 /// Produce possible references for a definition/import node
644 pub fn references(
645 &self,
646 definition_node: NodeIndex,
647 ) -> Box<dyn Iterator<Item = NodeIndex> + '_> {
648 let iterator = self
649 .graph
650 .edges_directed(definition_node, Direction::Incoming)
651 .filter(|edge| {
652 *edge.weight() == EdgeKind::RefToDef || *edge.weight() == EdgeKind::RefToImport
653 })
654 .map(|edge| edge.source());
655 Box::new(iterator)
656 }
657
658 pub fn node_by_range(&self, start_byte: usize, end_byte: usize) -> Option<NodeIndex> {
659 self.graph
660 .node_indices()
661 .filter(|&idx| self.is_definition(idx) || self.is_reference(idx) || self.is_import(idx))
662 .find(|&idx| {
663 let node = self.graph[idx].range();
664 start_byte >= node.start.byte && end_byte <= node.end.byte
665 })
666 }
667
668 /// The "value" of a definition is loosely characterized as
669 ///
670 /// - the body of a function block
671 /// - the body of a class
672 /// - the parameters list defining generic types
673 /// - the RHS of a value
674 ///
675 /// The heuristic used here is
676 /// - the smallest scope-node that encompasses the definition_node
677 /// - or the largest scope-node on the same line as the to the definition_node
678 pub fn value_of_definition(&self, def_idx: NodeIndex) -> Option<NodeIndex> {
679 let smallest_scope_node = self
680 .scope_by_range(self.graph[def_idx].range(), self.root_idx)
681 .filter(|&idx| {
682 self.graph[idx].range().start.line == self.graph[def_idx].range().start.line
683 });
684 let largest_adjacent_node = self
685 .graph
686 .node_indices()
687 .filter(|&idx| match self.graph[idx] {
688 NodeKind::Scope(scope) => {
689 scope.range.start.line == self.graph[def_idx].range().start.line
690 }
691 _ => false,
692 })
693 .max_by_key(|idx| self.graph[*idx].range().size());
694
695 smallest_scope_node.or(largest_adjacent_node)
696 }
697
698 pub fn node_by_position(&self, line: usize, column: usize) -> Option<NodeIndex> {
699 self.graph
700 .node_indices()
701 .filter(|&idx| self.is_definition(idx) || self.is_reference(idx))
702 .find(|&idx| {
703 let node = self.graph[idx].range();
704 node.start.line == line
705 && node.end.line == line
706 && node.start.column <= column
707 && node.end.column >= column
708 })
709 }
710
711 #[cfg(test)]
712 pub fn find_node_by_name(&self, src: &[u8], name: &[u8]) -> Option<NodeIndex> {
713 self.graph.node_indices().find(|idx| {
714 matches!(
715 &self.graph[*idx],
716 NodeKind::Def(d) if d.name(src) == name)
717 })
718 }
719
720 pub fn is_definition(&self, node_idx: NodeIndex) -> bool {
721 matches!(self.graph[node_idx], NodeKind::Def(_))
722 }
723
724 pub fn is_reference(&self, node_idx: NodeIndex) -> bool {
725 matches!(self.graph[node_idx], NodeKind::Ref(_))
726 }
727
728 pub fn is_scope(&self, node_idx: NodeIndex) -> bool {
729 matches!(self.graph[node_idx], NodeKind::Scope(_))
730 }
731
732 pub fn is_import(&self, node_idx: NodeIndex) -> bool {
733 matches!(self.graph[node_idx], NodeKind::Import(_))
734 }
735}
736
737fn build_scope_graph(
738 tsg: tree_sitter_graph::graph::Graph,
739 mut scope_graph: ScopeGraph,
740) -> ScopeGraph {
741 let nodes = tsg.iter_nodes().collect::<Vec<_>>();
742 // insert scopes first
743 for node in nodes
744 .iter()
745 .map(|node_ref| &tsg[*node_ref])
746 .filter(|node| is_scope(node))
747 {
748 let range = value_to_range(node.attributes.get(&Identifier::from("range")).unwrap());
749 let scope = LocalScope::new(range.into());
750 scope_graph.insert_local_scope(scope);
751 }
752
753 for node in nodes
754 .iter()
755 .map(|node_ref| &tsg[*node_ref])
756 .filter(|node| is_import(node))
757 {
758 let range = value_to_range(node.attributes.get(&Identifier::from("range")).unwrap());
759 let text = node
760 .attributes
761 .get(&Identifier::from("text"))
762 .and_then(|id| id.clone().into_string().ok())
763 .expect("import without text");
764 let import = LocalImport::new(range.into(), text);
765 scope_graph.insert_local_import(import);
766 }
767
768 for node in nodes
769 .iter()
770 .map(|node_ref| &tsg[*node_ref])
771 .filter(|node| is_def(node))
772 {
773 let range = value_to_range(node.attributes.get(&Identifier::from("range")).unwrap());
774 let symbol = node
775 .attributes
776 .get(&Identifier::from("symbol"))
777 .and_then(|id| id.clone().into_string().ok());
778 let text = node
779 .attributes
780 .get(&Identifier::from("text"))
781 .and_then(|id| id.clone().into_string().ok())
782 .expect("def without text");
783 let local_def = LocalDef::new(range.into(), text, symbol);
784
785 // TODO: fix scoping here
786 scope_graph.insert_local_def(local_def);
787 }
788
789 for node in nodes
790 .iter()
791 .map(|node_ref| &tsg[*node_ref])
792 .filter(|node| is_ref(node))
793 {
794 let range = value_to_range(node.attributes.get(&Identifier::from("range")).unwrap());
795 let symbol = node
796 .attributes
797 .get(&Identifier::from("symbol"))
798 .and_then(|id| id.clone().into_string().ok());
799 let text = node
800 .attributes
801 .get(&Identifier::from("text"))
802 .and_then(|id| id.clone().into_string().ok())
803 .expect("ref without text");
804 let ref_ = Reference::new(range.into(), text, symbol);
805
806 scope_graph.insert_ref(ref_);
807 }
808
809 scope_graph
810}
diff --git a/stag/src/scopes.scm b/stag/src/scopes.scm
new file mode 100644
index 0000000..8a5c385
--- /dev/null
+++ b/stag/src/scopes.scm
@@ -0,0 +1,463 @@
1;; see tree-sitter-rust/src/grammar.json for an exhaustive list of productions
2
3;; scopes
4(block) @local.scope ; { ... }
5(function_item) @local.scope
6(declaration_list) @local.scope ; mod { ... }
7
8;; impl items can define types and lifetimes:
9;;
10;; impl<'a, T> Trait for Struct { .. }
11;;
12;; in order to constrain those to the impl block,
13;; we add a local scope here:
14(impl_item) @local.scope
15(struct_item) @local.scope
16(enum_item) @local.scope
17(union_item) @local.scope
18(type_item) @local.scope
19(trait_item) @local.scope
20
21;; let expressions create scopes
22(if_expression
23 [(let_condition)
24 (let_chain)]) @local.scope
25
26;; each match arm can bind variables with
27;; patterns, without creating a block scope;
28;;
29;; match _ {
30;; (a, b) => a,
31;; }
32;;
33;; The bindings for a, b are constrained to
34;; the match arm.
35(match_arm) @local.scope
36
37;; loop labels are defs that are available only
38;; within the scope they create:
39;;
40;; 'outer: loop {
41;; let x = 2;
42;; };
43;; let y = 2;
44;;
45;; Produces a scope graph like so:
46;;
47;; {
48;; defs: [ y ],
49;; scopes: [
50;; {
51;; defs: [ 'outer ],
52;; scopes: [
53;; {
54;; defs: [ x ]
55;; }
56;; ]
57;; }
58;; ]
59;; }
60;;
61(loop_expression) @local.scope
62(for_expression) @local.scope
63(while_expression) @local.scope
64
65
66;; defs
67
68;; let x = ...;
69(let_declaration
70 pattern: (identifier) @local.definition.variable)
71
72;; if let x = ...;
73;; while let x = ...;
74(let_condition
75 .
76 (identifier) @local.definition.variable)
77
78;; let (a, b, ...) = ..;
79;; if let (a, b, ...) = {}
80;; while let (a, b, ...) = {}
81;; match _ { (a, b) => { .. } }
82(tuple_pattern (identifier) @local.definition.variable)
83
84;; Some(a)
85(tuple_struct_pattern
86 type: (_)
87 (identifier) @local.definition.variable)
88
89;; let S { field: a } = ..;
90(struct_pattern
91 (field_pattern
92 (identifier) @local.definition.variable))
93
94;; let S { a, b } = ..;
95(struct_pattern
96 (field_pattern
97 (shorthand_field_identifier) @local.definition.variable))
98
99;; (mut x: T)
100(mut_pattern (identifier) @local.definition.variable)
101
102;; (ref x: T)
103(ref_pattern (identifier) @local.definition.variable)
104
105;; const x = ...;
106(const_item (identifier) @local.definition.const)
107
108;; static x = ...;
109(static_item (identifier) @local.definition.const)
110
111;; fn _(x: _)
112(parameters
113 (parameter
114 pattern: (identifier) @local.definition.variable))
115;; fn _(self)
116(parameters
117 (self_parameter
118 (self) @local.definition.variable))
119
120;; type parameters
121(type_parameters
122 (type_identifier) @local.definition.typedef)
123(type_parameters
124 (lifetime) @local.definition.lifetime)
125(constrained_type_parameter
126 left: (type_identifier) @local.definition.typedef)
127
128;; |x| { ... }
129;; no type
130(closure_parameters (identifier) @local.definition.variable)
131
132;; |x: T| { ... }
133;; with type
134(closure_parameters
135 (parameter
136 (identifier) @local.definition.variable))
137
138;;fn x(..)
139(function_item (identifier) @hoist.definition.function)
140
141;; 'outer: loop { .. }
142(loop_expression
143 (loop_label) @local.definition.label)
144
145;; `for` exprs create two defs: a label (if any) and the
146;; loop variable
147(for_expression . (identifier) @local.definition.variable)
148(for_expression (loop_label) @local.definition.label)
149
150;; 'label: while cond { .. }
151(while_expression
152 (loop_label) @local.definition.label)
153
154;; type definitions
155(struct_item (type_identifier) @hoist.definition.struct)
156(enum_item (type_identifier) @hoist.definition.enum)
157(union_item (type_identifier) @hoist.definition.union)
158(type_item . (type_identifier) @hoist.definition.typedef)
159(trait_item (type_identifier) @hoist.definition.interface)
160
161;; struct and union fields
162(field_declaration_list
163 (field_declaration
164 (field_identifier) @local.definition.field))
165
166;; enum variants
167(enum_variant_list
168 (enum_variant
169 (identifier) @local.definition.enumerator))
170
171;; mod x;
172(mod_item (identifier) @local.definition.module)
173
174;; use statements
175
176;; use item;
177(use_declaration
178 (identifier) @local.import)
179
180;; use path as item;
181(use_as_clause
182 alias: (identifier) @local.import)
183
184;; use path::item;
185(use_declaration
186 (scoped_identifier
187 name: (identifier) @local.import))
188
189;; use module::{member1, member2, member3};
190(use_list
191 (identifier) @local.import)
192(use_list
193 (scoped_identifier
194 name: (identifier) @local.import))
195
196
197;; refs
198
199;; !x
200(unary_expression (identifier) @local.reference)
201
202;; &x
203(reference_expression (identifier) @local.reference)
204
205;; (x)
206(parenthesized_expression (identifier) @local.reference)
207
208;; x?
209(try_expression (identifier) @local.reference)
210
211;; a = b
212(assignment_expression (identifier) @local.reference)
213
214;; a op b
215(binary_expression (identifier) @local.reference)
216
217;; a op= b
218(compound_assignment_expr (identifier) @local.reference)
219
220;; a as b
221(type_cast_expression (identifier) @local.reference)
222
223;; a()
224(call_expression (identifier) @local.reference)
225
226;; Self::foo()
227;;
228;; `foo` can be resolved
229(call_expression
230 (scoped_identifier
231 (identifier) @_self_type
232 (identifier) @local.reference)
233 (#match? @_self_type "Self"))
234
235;; self.foo()
236;;
237;; `foo` can be resolved
238(call_expression
239 (field_expression
240 (self)
241 (field_identifier) @local.reference))
242
243;; return a
244(return_expression (identifier) @local.reference)
245
246;; break a
247(break_expression (identifier) @local.reference)
248
249;; break 'label
250(break_expression (loop_label) @local.reference)
251
252;; continue 'label;
253(continue_expression (loop_label) @local.reference)
254
255;; yield x;
256(yield_expression (identifier) @local.reference)
257
258;; await a
259(await_expression (identifier) @local.reference)
260
261;; (a, b)
262(tuple_expression (identifier) @local.reference)
263
264;; a[]
265(index_expression (identifier) @local.reference)
266
267;; ident;
268(expression_statement (identifier) @local.reference)
269
270;; a..b
271(range_expression (identifier) @local.reference)
272
273;; [ident; N]
274(array_expression (identifier) @local.reference)
275
276;; path::to::item
277;;
278;; `path` is a ref
279(scoped_identifier
280 path: (identifier) @local.reference)
281
282;; rhs of let decls
283(let_declaration
284 value: (identifier) @local.reference)
285
286;; type T = [T; N]
287;;
288;; N is a ident ref
289(array_type
290 length: (identifier) @local.reference)
291
292;; S { _ }
293(struct_expression
294 (type_identifier) @local.reference)
295
296;; S { a }
297(struct_expression
298 (field_initializer_list
299 (shorthand_field_initializer
300 (identifier) @local.reference)))
301
302;; S { a: value }
303(struct_expression
304 (field_initializer_list
305 (field_initializer
306 (identifier) @local.reference)))
307
308;; S { ..a }
309(struct_expression
310 (field_initializer_list
311 (base_field_initializer
312 (identifier) @local.reference)))
313
314;; if a {}
315(if_expression (identifier) @local.reference)
316
317;; for pattern in value {}
318;;
319;; `value` is a ref
320(for_expression
321 value: (identifier) @local.reference)
322
323;; while a {}
324(while_expression (identifier) @local.reference)
325
326;; if let _ = a {}
327;;
328;; the ident following the `=` is a ref
329;; the ident preceding the `=` is a def
330;; while let _ = a {}
331(let_condition
332 "="
333 (identifier) @local.reference)
334
335
336;; match a
337(match_expression (identifier) @local.reference)
338
339;; match _ {
340;; pattern => a,
341;; }
342;;
343;; this `a` is somehow not any expression form
344(match_arm (identifier) @local.reference)
345
346;; a.b
347;;
348;; `b` is ignored
349(field_expression
350 (identifier) @local.reference)
351
352;; { stmt; foo }
353(block
354 (identifier) @local.reference)
355
356;; arguments to method calls or function calls
357(arguments
358 (identifier) @local.reference)
359
360;; impl S { .. }
361(impl_item (type_identifier) @local.reference)
362
363;; where T: ...
364(where_predicate
365 left: (type_identifier) @local.reference)
366
367;; trait bounds
368(trait_bounds
369 (type_identifier) @local.reference)
370(trait_bounds
371 (lifetime) @local.reference)
372
373;; idents in macros
374(token_tree
375 (identifier) @local.reference)
376
377;; types
378
379;; (T, U)
380(tuple_type
381 (type_identifier) @local.reference)
382
383;; &T
384(reference_type
385 (type_identifier) @local.reference)
386
387;; &'a T
388(reference_type
389 (lifetime) @local.reference)
390
391;; &'a self
392(self_parameter
393 (lifetime) @local.reference)
394
395;; *mut T
396;; *const T
397(pointer_type
398 (type_identifier) @local.reference)
399
400;; A<_>
401(generic_type
402 (type_identifier) @local.reference)
403
404;; _<V>
405(type_arguments
406 (type_identifier) @local.reference)
407(type_arguments
408 (lifetime) @local.reference)
409
410;; T<U = V>
411;;
412;; U is ignored
413;; V is a ref
414(type_binding
415 name: (_)
416 type: (type_identifier) @local.reference)
417
418;; [T]
419(array_type
420 (type_identifier) @local.reference)
421
422;; type T = U;
423;;
424;; T is a def
425;; U is a ref
426(type_item
427 name: (_)
428 type: (type_identifier) @local.reference)
429
430(function_item
431 return_type: (type_identifier) @local.reference)
432
433;; type refs in params
434;;
435;; fn _(_: T)
436(parameters
437 (parameter
438 type: (type_identifier) @local.reference))
439
440;; dyn T
441(dynamic_type
442 (type_identifier) @local.reference)
443
444;; <T>::call()
445(bracketed_type
446 (type_identifier) @local.reference)
447
448;; T as Trait
449(qualified_type
450 (type_identifier) @local.reference)
451
452;; module::T
453;;
454;; `module` is a def
455;; `T` is a ref
456(scoped_type_identifier
457 path: (identifier) @local.reference)
458
459;; struct _ { field: Type }
460;; `Type` is a ref
461 (field_declaration
462 name: (_)
463 type: (type_identifier) @local.reference)
diff --git a/stag/src/stag.scm b/stag/src/stag.scm
new file mode 100644
index 0000000..b6271b8
--- /dev/null
+++ b/stag/src/stag.scm
@@ -0,0 +1,36 @@
1[
2 (block)
3 (declaration_list)
4 (impl_item)
5 (struct_item)
6 (enum_item)
7 (union_item)
8 (type_item)
9 (trait_item)
10 (if_expression
11 [(let_condition)
12 (let_chain)])
13 ] @cap
14{
15 (scope (range @cap))
16}
17
18(function_item
19 (parameters) @params
20 (block) @body)
21{
22 (scope (cover @params @body))
23}
24
25
26(let_declaration
27 pattern: (identifier) @cap)
28{
29 (def @cap)
30}
31
32
33(binary_expression (identifier) @c) {
34 (ref @c)
35}
36
diff --git a/stag/src/text_range.rs b/stag/src/text_range.rs
new file mode 100644
index 0000000..5b1ec67
--- /dev/null
+++ b/stag/src/text_range.rs
@@ -0,0 +1,121 @@
1use std::cmp::{Ord, Ordering};
2
3use serde::{Deserialize, Serialize};
4
5/// A singular position in a text document
6#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
7pub struct Point {
8 /// The byte index
9 pub byte: usize,
10
11 /// 0-indexed line number
12 pub line: usize,
13
14 /// Position within the line
15 pub column: usize,
16}
17
18impl PartialOrd for Point {
19 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
20 Some(self.cmp(other))
21 }
22}
23
24impl Ord for Point {
25 fn cmp(&self, other: &Self) -> Ordering {
26 self.byte.cmp(&other.byte)
27 }
28}
29
30impl Point {
31 pub fn new(byte: usize, line: usize, column: usize) -> Self {
32 Self { byte, line, column }
33 }
34
35 pub fn from_byte(byte: usize, line_end_indices: &[u32]) -> Self {
36 let line = line_end_indices
37 .iter()
38 .position(|&line_end_byte| (line_end_byte as usize) > byte)
39 .unwrap_or(0);
40
41 let column = line
42 .checked_sub(1)
43 .and_then(|idx| line_end_indices.get(idx))
44 .map(|&prev_line_end| byte.saturating_sub(prev_line_end as usize))
45 .unwrap_or(byte);
46
47 Self::new(byte, line, column)
48 }
49}
50
51#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
52pub struct TextRange {
53 pub start: Point,
54 pub end: Point,
55}
56
57impl PartialOrd for TextRange {
58 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
59 Some(self.cmp(other))
60 }
61}
62
63impl Ord for TextRange {
64 fn cmp(&self, other: &Self) -> Ordering {
65 let compare_start_byte = self.start.byte.cmp(&other.start.byte);
66 let compare_size = self.size().cmp(&other.size());
67
68 compare_start_byte.then(compare_size)
69 }
70}
71
72impl TextRange {
73 pub fn new(start: Point, end: Point) -> Self {
74 assert!(start <= end);
75 Self { start, end }
76 }
77
78 pub fn contains(&self, other: &TextRange) -> bool {
79 // (self.start ... [other.start ... other.end] ... self.end)
80 self.start <= other.start && other.end <= self.end
81 }
82
83 #[allow(unused)]
84 pub fn contains_strict(&self, other: TextRange) -> bool {
85 // (self.start ... (other.start ... other.end) ... self.end)
86 self.start < other.start && other.end <= self.end
87 }
88
89 pub fn size(&self) -> usize {
90 self.end.byte.saturating_sub(self.start.byte)
91 }
92
93 pub fn from_byte_range(range: std::ops::Range<usize>, line_end_indices: &[u32]) -> Self {
94 let start = Point::from_byte(range.start, line_end_indices);
95 let end = Point::from_byte(range.end, line_end_indices);
96 Self::new(start, end)
97 }
98}
99
100impl From<tree_sitter::Range> for TextRange {
101 fn from(r: tree_sitter::Range) -> Self {
102 Self {
103 start: Point {
104 byte: r.start_byte,
105 line: r.start_point.row,
106 column: r.start_point.column,
107 },
108 end: Point {
109 byte: r.end_byte,
110 line: r.end_point.row,
111 column: r.end_point.column,
112 },
113 }
114 }
115}
116
117impl From<TextRange> for std::ops::Range<usize> {
118 fn from(r: TextRange) -> std::ops::Range<usize> {
119 r.start.byte..r.end.byte
120 }
121}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-22 17:57:28 +0000