summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Cargo.lock375
-rw-r--r--Cargo.toml8
-rw-r--r--flake.lock45
-rw-r--r--flake.nix29
-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
9 files changed, 1820 insertions, 83 deletions
diff --git a/Cargo.lock b/Cargo.lock
index ff68afe..4c838d5 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -3,6 +3,12 @@
3version = 3 3version = 3
4 4
5[[package]] 5[[package]]
6name = "ahash"
7version = "0.4.8"
8source = "registry+https://github.com/rust-lang/crates.io-index"
9checksum = "0453232ace82dee0dd0b4c87a59bd90f7b53b314f3e0f61fe2ee7c8a16482289"
10
11[[package]]
6name = "aho-corasick" 12name = "aho-corasick"
7version = "0.7.19" 13version = "0.7.19"
8source = "registry+https://github.com/rust-lang/crates.io-index" 14source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -19,9 +25,12 @@ checksum = "bef38d45163c2f1dde094a7dfd33ccf595c92905c8f8f4fdc18d06fb1037718a"
19 25
20[[package]] 26[[package]]
21name = "cc" 27name = "cc"
22version = "1.0.73" 28version = "1.0.83"
23source = "registry+https://github.com/rust-lang/crates.io-index" 29source = "registry+https://github.com/rust-lang/crates.io-index"
24checksum = "2fff2a6927b3bb87f9595d67196a70493f627687a71d87a0d692242c33f58c11" 30checksum = "f1174fb0b6ec23863f8b971027804a42614e347eafb0a95bf0b12cdae21fc4d0"
31dependencies = [
32 "libc",
33]
25 34
26[[package]] 35[[package]]
27name = "cfg-if" 36name = "cfg-if"
@@ -44,12 +53,34 @@ dependencies = [
44] 53]
45 54
46[[package]] 55[[package]]
56name = "dissimilar"
57version = "1.0.7"
58source = "registry+https://github.com/rust-lang/crates.io-index"
59checksum = "86e3bdc80eee6e16b2b6b0f87fbc98c04bee3455e35174c0de1a125d0688c632"
60
61[[package]]
47name = "encode_unicode" 62name = "encode_unicode"
48version = "0.3.6" 63version = "0.3.6"
49source = "registry+https://github.com/rust-lang/crates.io-index" 64source = "registry+https://github.com/rust-lang/crates.io-index"
50checksum = "a357d28ed41a50f9c765dbfe56cbc04a64e53e5fc58ba79fbc34c10ef3df831f" 65checksum = "a357d28ed41a50f9c765dbfe56cbc04a64e53e5fc58ba79fbc34c10ef3df831f"
51 66
52[[package]] 67[[package]]
68name = "equivalent"
69version = "1.0.1"
70source = "registry+https://github.com/rust-lang/crates.io-index"
71checksum = "5443807d6dff69373d433ab9ef5378ad8df50ca6298caf15de6e52e24aaf54d5"
72
73[[package]]
74name = "expect-test"
75version = "1.4.1"
76source = "registry+https://github.com/rust-lang/crates.io-index"
77checksum = "30d9eafeadd538e68fb28016364c9732d78e420b9ff8853fa5e4058861e9f8d3"
78dependencies = [
79 "dissimilar",
80 "once_cell",
81]
82
83[[package]]
53name = "filetime" 84name = "filetime"
54version = "0.2.17" 85version = "0.2.17"
55source = "registry+https://github.com/rust-lang/crates.io-index" 86source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -62,6 +93,37 @@ dependencies = [
62] 93]
63 94
64[[package]] 95[[package]]
96name = "fixedbitset"
97version = "0.4.2"
98source = "registry+https://github.com/rust-lang/crates.io-index"
99checksum = "0ce7134b9999ecaf8bcd65542e436736ef32ddca1b3e06094cb6ec5755203b80"
100
101[[package]]
102name = "hashbrown"
103version = "0.9.1"
104source = "registry+https://github.com/rust-lang/crates.io-index"
105checksum = "d7afe4a420e3fe79967a00898cc1f4db7c8a49a9333a29f8a4bd76a253d5cd04"
106dependencies = [
107 "ahash",
108]
109
110[[package]]
111name = "hashbrown"
112version = "0.14.3"
113source = "registry+https://github.com/rust-lang/crates.io-index"
114checksum = "290f1a1d9242c78d09ce40a5e87e7554ee637af1351968159f4952f028f75604"
115
116[[package]]
117name = "indexmap"
118version = "2.1.0"
119source = "registry+https://github.com/rust-lang/crates.io-index"
120checksum = "d530e1a18b1cb4c484e6e34556a0d948706958449fca0cab753d649f2bce3d1f"
121dependencies = [
122 "equivalent",
123 "hashbrown 0.14.3",
124]
125
126[[package]]
65name = "inotify" 127name = "inotify"
66version = "0.9.6" 128version = "0.9.6"
67source = "registry+https://github.com/rust-lang/crates.io-index" 129source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -82,6 +144,12 @@ dependencies = [
82] 144]
83 145
84[[package]] 146[[package]]
147name = "itoa"
148version = "1.0.10"
149source = "registry+https://github.com/rust-lang/crates.io-index"
150checksum = "b1a46d1a171d865aa5f83f92695765caa047a9b4cbae2cbf37dbd613a793fd4c"
151
152[[package]]
85name = "kqueue" 153name = "kqueue"
86version = "1.0.6" 154version = "1.0.6"
87source = "registry+https://github.com/rust-lang/crates.io-index" 155source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -152,9 +220,45 @@ dependencies = [
152 220
153[[package]] 221[[package]]
154name = "once_cell" 222name = "once_cell"
155version = "1.14.0" 223version = "1.19.0"
156source = "registry+https://github.com/rust-lang/crates.io-index" 224source = "registry+https://github.com/rust-lang/crates.io-index"
157checksum = "2f7254b99e31cad77da24b08ebf628882739a608578bb1bcdfc1f9c21260d7c0" 225checksum = "3fdb12b2476b595f9358c5161aa467c2438859caa136dec86c26fdd2efe17b92"
226
227[[package]]
228name = "petgraph"
229version = "0.6.4"
230source = "registry+https://github.com/rust-lang/crates.io-index"
231checksum = "e1d3afd2628e69da2be385eb6f2fd57c8ac7977ceeff6dc166ff1657b0e386a9"
232dependencies = [
233 "fixedbitset",
234 "indexmap",
235 "serde",
236 "serde_derive",
237]
238
239[[package]]
240name = "pin-project-lite"
241version = "0.2.13"
242source = "registry+https://github.com/rust-lang/crates.io-index"
243checksum = "8afb450f006bf6385ca15ef45d71d2288452bc3683ce2e2cacc0d18e4be60b58"
244
245[[package]]
246name = "proc-macro2"
247version = "1.0.76"
248source = "registry+https://github.com/rust-lang/crates.io-index"
249checksum = "95fc56cda0b5c3325f5fbbd7ff9fda9e02bb00bb3dac51252d2f1bfa1cb8cc8c"
250dependencies = [
251 "unicode-ident",
252]
253
254[[package]]
255name = "quote"
256version = "1.0.35"
257source = "registry+https://github.com/rust-lang/crates.io-index"
258checksum = "291ec9ab5efd934aaf503a6466c5d5251535d108ee747472c3977cc5acc868ef"
259dependencies = [
260 "proc-macro2",
261]
158 262
159[[package]] 263[[package]]
160name = "redox_syscall" 264name = "redox_syscall"
@@ -183,6 +287,12 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
183checksum = "a3f87b73ce11b1619a3c6332f45341e0047173771e8b8b73f87bfeefb7b56244" 287checksum = "a3f87b73ce11b1619a3c6332f45341e0047173771e8b8b73f87bfeefb7b56244"
184 288
185[[package]] 289[[package]]
290name = "ryu"
291version = "1.0.16"
292source = "registry+https://github.com/rust-lang/crates.io-index"
293checksum = "f98d2aa92eebf49b69786be48e4477826b256916e84a57ff2a4f21923b48eb4c"
294
295[[package]]
186name = "same-file" 296name = "same-file"
187version = "1.0.6" 297version = "1.0.6"
188source = "registry+https://github.com/rust-lang/crates.io-index" 298source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -192,6 +302,103 @@ dependencies = [
192] 302]
193 303
194[[package]] 304[[package]]
305name = "scope-graph"
306version = "0.1.0"
307dependencies = [
308 "expect-test",
309 "once_cell",
310 "petgraph",
311 "serde",
312 "serde_derive",
313 "thiserror",
314 "tracing",
315 "tree-sitter",
316 "tree-sitter-c",
317 "tree-sitter-c-sharp",
318 "tree-sitter-cpp",
319 "tree-sitter-go 0.19.1 (git+https://github.com/tree-sitter/tree-sitter-go?rev=05900fa)",
320 "tree-sitter-java",
321 "tree-sitter-javascript",
322 "tree-sitter-php",
323 "tree-sitter-python",
324 "tree-sitter-r",
325 "tree-sitter-ruby",
326 "tree-sitter-rust",
327 "tree-sitter-typescript",
328]
329
330[[package]]
331name = "serde"
332version = "1.0.193"
333source = "registry+https://github.com/rust-lang/crates.io-index"
334checksum = "25dd9975e68d0cb5aa1120c288333fc98731bd1dd12f561e468ea4728c042b89"
335dependencies = [
336 "serde_derive",
337]
338
339[[package]]
340name = "serde_derive"
341version = "1.0.193"
342source = "registry+https://github.com/rust-lang/crates.io-index"
343checksum = "43576ca501357b9b071ac53cdc7da8ef0cbd9493d8df094cd821777ea6e894d3"
344dependencies = [
345 "proc-macro2",
346 "quote",
347 "syn",
348]
349
350[[package]]
351name = "serde_json"
352version = "1.0.109"
353source = "registry+https://github.com/rust-lang/crates.io-index"
354checksum = "cb0652c533506ad7a2e353cce269330d6afd8bdfb6d75e0ace5b35aacbd7b9e9"
355dependencies = [
356 "itoa",
357 "ryu",
358 "serde",
359]
360
361[[package]]
362name = "smallvec"
363version = "1.11.2"
364source = "registry+https://github.com/rust-lang/crates.io-index"
365checksum = "4dccd0940a2dcdf68d092b8cbab7dc0ad8fa938bf95787e1b916b0e3d0e8e970"
366
367[[package]]
368name = "stag"
369version = "0.1.0"
370dependencies = [
371 "once_cell",
372 "petgraph",
373 "serde",
374 "thiserror",
375 "tree-sitter",
376 "tree-sitter-graph",
377 "tree-sitter-rust",
378]
379
380[[package]]
381name = "string-interner"
382version = "0.12.2"
383source = "registry+https://github.com/rust-lang/crates.io-index"
384checksum = "383196d1876517ee6f9f0864d1fc1070331b803335d3c6daaa04bbcccd823c08"
385dependencies = [
386 "cfg-if",
387 "hashbrown 0.9.1",
388]
389
390[[package]]
391name = "syn"
392version = "2.0.48"
393source = "registry+https://github.com/rust-lang/crates.io-index"
394checksum = "0f3531638e407dfc0814761abb7c00a5b54992b849452a0646b7f65c9f770f3f"
395dependencies = [
396 "proc-macro2",
397 "quote",
398 "unicode-ident",
399]
400
401[[package]]
195name = "terminal_size" 402name = "terminal_size"
196version = "0.1.17" 403version = "0.1.17"
197source = "registry+https://github.com/rust-lang/crates.io-index" 404source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -202,16 +409,104 @@ dependencies = [
202] 409]
203 410
204[[package]] 411[[package]]
412name = "thiserror"
413version = "1.0.56"
414source = "registry+https://github.com/rust-lang/crates.io-index"
415checksum = "d54378c645627613241d077a3a79db965db602882668f9136ac42af9ecb730ad"
416dependencies = [
417 "thiserror-impl",
418]
419
420[[package]]
421name = "thiserror-impl"
422version = "1.0.56"
423source = "registry+https://github.com/rust-lang/crates.io-index"
424checksum = "fa0faa943b50f3db30a20aa7e265dbc66076993efed8463e8de414e5d06d3471"
425dependencies = [
426 "proc-macro2",
427 "quote",
428 "syn",
429]
430
431[[package]]
432name = "tracing"
433version = "0.1.40"
434source = "registry+https://github.com/rust-lang/crates.io-index"
435checksum = "c3523ab5a71916ccf420eebdf5521fcef02141234bbc0b8a49f2fdc4544364ef"
436dependencies = [
437 "pin-project-lite",
438 "tracing-attributes",
439 "tracing-core",
440]
441
442[[package]]
443name = "tracing-attributes"
444version = "0.1.27"
445source = "registry+https://github.com/rust-lang/crates.io-index"
446checksum = "34704c8d6ebcbc939824180af020566b01a7c01f80641264eba0999f6c2b6be7"
447dependencies = [
448 "proc-macro2",
449 "quote",
450 "syn",
451]
452
453[[package]]
454name = "tracing-core"
455version = "0.1.32"
456source = "registry+https://github.com/rust-lang/crates.io-index"
457checksum = "c06d3da6113f116aaee68e4d601191614c9053067f9ab7f6edbcb161237daa54"
458dependencies = [
459 "once_cell",
460]
461
462[[package]]
205name = "tree-sitter" 463name = "tree-sitter"
206version = "0.20.9" 464version = "0.20.10"
207source = "registry+https://github.com/rust-lang/crates.io-index" 465source = "registry+https://github.com/rust-lang/crates.io-index"
208checksum = "d4423c784fe11398ca91e505cdc71356b07b1a924fc8735cfab5333afe3e18bc" 466checksum = "e747b1f9b7b931ed39a548c1fae149101497de3c1fc8d9e18c62c1a66c683d3d"
209dependencies = [ 467dependencies = [
210 "cc", 468 "cc",
211 "regex", 469 "regex",
212] 470]
213 471
214[[package]] 472[[package]]
473name = "tree-sitter-COBOL"
474version = "0.0.1"
475dependencies = [
476 "cc",
477 "tree-sitter",
478]
479
480[[package]]
481name = "tree-sitter-c"
482version = "0.20.6"
483source = "registry+https://github.com/rust-lang/crates.io-index"
484checksum = "30b03bdf218020057abee831581a74bff8c298323d6c6cd1a70556430ded9f4b"
485dependencies = [
486 "cc",
487 "tree-sitter",
488]
489
490[[package]]
491name = "tree-sitter-c-sharp"
492version = "0.20.0"
493source = "registry+https://github.com/rust-lang/crates.io-index"
494checksum = "b9ab3dc608f34924fa9e10533a95f62dbc14b6de0ddd7107722eba66fe19ae31"
495dependencies = [
496 "cc",
497 "tree-sitter",
498]
499
500[[package]]
501name = "tree-sitter-cpp"
502version = "0.20.0"
503source = "git+https://github.com/tree-sitter/tree-sitter-cpp?rev=5ead1e2#5ead1e26c6ab71919db0f1880c46a278a93bc5ea"
504dependencies = [
505 "cc",
506 "tree-sitter",
507]
508
509[[package]]
215name = "tree-sitter-elm" 510name = "tree-sitter-elm"
216version = "5.6.3" 511version = "5.6.3"
217source = "registry+https://github.com/rust-lang/crates.io-index" 512source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -232,10 +527,42 @@ dependencies = [
232] 527]
233 528
234[[package]] 529[[package]]
235name = "tree-sitter-javascript" 530name = "tree-sitter-go"
531version = "0.19.1"
532source = "git+https://github.com/tree-sitter/tree-sitter-go?rev=05900fa#05900faa3cdb5d2d8c8bd5e77ee698487e0a8611"
533dependencies = [
534 "cc",
535 "tree-sitter",
536]
537
538[[package]]
539name = "tree-sitter-graph"
540version = "0.11.0"
541dependencies = [
542 "log",
543 "regex",
544 "serde",
545 "serde_json",
546 "smallvec",
547 "string-interner",
548 "thiserror",
549 "tree-sitter",
550]
551
552[[package]]
553name = "tree-sitter-java"
236version = "0.20.0" 554version = "0.20.0"
555source = "git+https://github.com/tree-sitter/tree-sitter-java?tag=v0.20.0#ac14b4b1884102839455d32543ab6d53ae089ab7"
556dependencies = [
557 "cc",
558 "tree-sitter",
559]
560
561[[package]]
562name = "tree-sitter-javascript"
563version = "0.20.1"
237source = "registry+https://github.com/rust-lang/crates.io-index" 564source = "registry+https://github.com/rust-lang/crates.io-index"
238checksum = "2490fab08630b2c8943c320f7b63473cbf65511c8d83aec551beb9b4375906ed" 565checksum = "edbc663376bdd294bd1f0a6daf859aedb9aa5bdb72217d7ad8ba2d5314102cf7"
239dependencies = [ 566dependencies = [
240 "cc", 567 "cc",
241 "tree-sitter", 568 "tree-sitter",
@@ -251,6 +578,16 @@ dependencies = [
251] 578]
252 579
253[[package]] 580[[package]]
581name = "tree-sitter-md"
582version = "0.1.5"
583source = "registry+https://github.com/rust-lang/crates.io-index"
584checksum = "5a237fa10f6b466b76c783c79b08cc172581e547ef1dbb6ddf1f8b4e230157e1"
585dependencies = [
586 "cc",
587 "tree-sitter",
588]
589
590[[package]]
254name = "tree-sitter-mdx" 591name = "tree-sitter-mdx"
255version = "0.0.1" 592version = "0.0.1"
256source = "git+https://github.com/jlopezcur/tree-sitter-mdx#df43681bff333228fa60b69c09a1e7a6f9ed1610" 593source = "git+https://github.com/jlopezcur/tree-sitter-mdx#df43681bff333228fa60b69c09a1e7a6f9ed1610"
@@ -270,9 +607,9 @@ dependencies = [
270 607
271[[package]] 608[[package]]
272name = "tree-sitter-python" 609name = "tree-sitter-python"
273version = "0.20.2" 610version = "0.20.4"
274source = "registry+https://github.com/rust-lang/crates.io-index" 611source = "registry+https://github.com/rust-lang/crates.io-index"
275checksum = "dda114f58048f5059dcf158aff691dffb8e113e6d2b50d94263fd68711975287" 612checksum = "e6c93b1b1fbd0d399db3445f51fd3058e43d0b4dcff62ddbdb46e66550978aa5"
276dependencies = [ 613dependencies = [
277 "cc", 614 "cc",
278 "tree-sitter", 615 "tree-sitter",
@@ -300,9 +637,9 @@ dependencies = [
300 637
301[[package]] 638[[package]]
302name = "tree-sitter-rust" 639name = "tree-sitter-rust"
303version = "0.20.3" 640version = "0.20.4"
304source = "registry+https://github.com/rust-lang/crates.io-index" 641source = "registry+https://github.com/rust-lang/crates.io-index"
305checksum = "797842733e252dc11ae5d403a18060bf337b822fc2ae5ddfaa6ff4d9cc20bda6" 642checksum = "b0832309b0b2b6d33760ce5c0e818cb47e1d72b468516bfe4134408926fa7594"
306dependencies = [ 643dependencies = [
307 "cc", 644 "cc",
308 "tree-sitter", 645 "tree-sitter",
@@ -310,9 +647,9 @@ dependencies = [
310 647
311[[package]] 648[[package]]
312name = "tree-sitter-typescript" 649name = "tree-sitter-typescript"
313version = "0.20.1" 650version = "0.20.3"
314source = "registry+https://github.com/rust-lang/crates.io-index" 651source = "registry+https://github.com/rust-lang/crates.io-index"
315checksum = "4e8ed0ecb931cdff13c6a13f45ccd615156e2779d9ffb0395864e05505e6e86d" 652checksum = "a75049f0aafabb2aac205d7bb24da162b53dcd0cfb326785f25a2f32efa8071a"
316dependencies = [ 653dependencies = [
317 "cc", 654 "cc",
318 "tree-sitter", 655 "tree-sitter",
@@ -326,10 +663,12 @@ dependencies = [
326 "notify", 663 "notify",
327 "once_cell", 664 "once_cell",
328 "tree-sitter", 665 "tree-sitter",
666 "tree-sitter-COBOL",
329 "tree-sitter-elm", 667 "tree-sitter-elm",
330 "tree-sitter-go", 668 "tree-sitter-go 0.19.1 (registry+https://github.com/rust-lang/crates.io-index)",
331 "tree-sitter-javascript", 669 "tree-sitter-javascript",
332 "tree-sitter-json", 670 "tree-sitter-json",
671 "tree-sitter-md",
333 "tree-sitter-mdx", 672 "tree-sitter-mdx",
334 "tree-sitter-php", 673 "tree-sitter-php",
335 "tree-sitter-python", 674 "tree-sitter-python",
@@ -340,6 +679,12 @@ dependencies = [
340] 679]
341 680
342[[package]] 681[[package]]
682name = "unicode-ident"
683version = "1.0.12"
684source = "registry+https://github.com/rust-lang/crates.io-index"
685checksum = "3354b9ac3fae1ff6755cb6db53683adb661634f67557942dea4facebec0fee4b"
686
687[[package]]
343name = "unicode-width" 688name = "unicode-width"
344version = "0.1.10" 689version = "0.1.10"
345source = "registry+https://github.com/rust-lang/crates.io-index" 690source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/Cargo.toml b/Cargo.toml
index d9cd8e1..f57c417 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -1,5 +1,11 @@
1[workspace] 1[workspace]
2 2
3resolver = "2"
3members = [ 4members = [
4 "tree-viz" 5 "tree-viz",
6 "scope-graph",
7 "stag",
8]
9exclude = [
10 "tree-sitter-graph"
5] 11]
diff --git a/flake.lock b/flake.lock
index a7c083f..ec56c37 100644
--- a/flake.lock
+++ b/flake.lock
@@ -1,26 +1,5 @@
1{ 1{
2 "nodes": { 2 "nodes": {
3 "fenix": {
4 "inputs": {
5 "nixpkgs": [
6 "nixpkgs"
7 ],
8 "rust-analyzer-src": "rust-analyzer-src"
9 },
10 "locked": {
11 "lastModified": 1645251813,
12 "narHash": "sha256-cQ66tGjnZclBCS3nD26mZ5fUH+3/HnysGffBiWXUSHk=",
13 "owner": "nix-community",
14 "repo": "fenix",
15 "rev": "9892337b588c38ec59466a1c89befce464aae7f8",
16 "type": "github"
17 },
18 "original": {
19 "owner": "nix-community",
20 "repo": "fenix",
21 "type": "github"
22 }
23 },
24 "gitignore": { 3 "gitignore": {
25 "inputs": { 4 "inputs": {
26 "nixpkgs": [ 5 "nixpkgs": [
@@ -43,11 +22,11 @@
43 }, 22 },
44 "nixpkgs": { 23 "nixpkgs": {
45 "locked": { 24 "locked": {
46 "lastModified": 1645013224, 25 "lastModified": 1704161960,
47 "narHash": "sha256-b7OEC8vwzJv3rsz9pwnTX2LQDkeOWz2DbKypkVvNHXc=", 26 "narHash": "sha256-QGua89Pmq+FBAro8NriTuoO/wNaUtugt29/qqA8zeeM=",
48 "owner": "nixos", 27 "owner": "nixos",
49 "repo": "nixpkgs", 28 "repo": "nixpkgs",
50 "rev": "b66b39216b1fef2d8c33cc7a5c72d8da80b79970", 29 "rev": "63143ac2c9186be6d9da6035fa22620018c85932",
51 "type": "github" 30 "type": "github"
52 }, 31 },
53 "original": { 32 "original": {
@@ -59,27 +38,9 @@
59 }, 38 },
60 "root": { 39 "root": {
61 "inputs": { 40 "inputs": {
62 "fenix": "fenix",
63 "gitignore": "gitignore", 41 "gitignore": "gitignore",
64 "nixpkgs": "nixpkgs" 42 "nixpkgs": "nixpkgs"
65 } 43 }
66 },
67 "rust-analyzer-src": {
68 "flake": false,
69 "locked": {
70 "lastModified": 1645205556,
71 "narHash": "sha256-e4lZW3qRyOEJ+vLKFQP7m2Dxh5P44NrnekZYLxlucww=",
72 "owner": "rust-analyzer",
73 "repo": "rust-analyzer",
74 "rev": "acf5874b39f3dc5262317a6074d9fc7285081161",
75 "type": "github"
76 },
77 "original": {
78 "owner": "rust-analyzer",
79 "ref": "nightly",
80 "repo": "rust-analyzer",
81 "type": "github"
82 }
83 } 44 }
84 }, 45 },
85 "root": "root", 46 "root": "root",
diff --git a/flake.nix b/flake.nix
index 861792b..5f0f1d6 100644
--- a/flake.nix
+++ b/flake.nix
@@ -3,11 +3,6 @@
3 3
4 nixpkgs.url = "github:nixos/nixpkgs/nixpkgs-unstable"; 4 nixpkgs.url = "github:nixos/nixpkgs/nixpkgs-unstable";
5 5
6 fenix = {
7 url = "github:nix-community/fenix";
8 inputs.nixpkgs.follows = "nixpkgs";
9 };
10
11 gitignore = { 6 gitignore = {
12 url = "github:hercules-ci/gitignore.nix"; 7 url = "github:hercules-ci/gitignore.nix";
13 inputs.nixpkgs.follows = "nixpkgs"; 8 inputs.nixpkgs.follows = "nixpkgs";
@@ -18,7 +13,6 @@
18 outputs = 13 outputs =
19 { self 14 { self
20 , nixpkgs 15 , nixpkgs
21 , fenix
22 , gitignore 16 , gitignore
23 }: 17 }:
24 let 18 let
@@ -29,37 +23,22 @@
29 nixpkgsFor = forAllSystems (system: 23 nixpkgsFor = forAllSystems (system:
30 import nixpkgs { inherit system; }); 24 import nixpkgs { inherit system; });
31 25
32 chanspec = {
33 date = "2022-09-01";
34 channel = "nightly";
35 sha256 = "tS2IHsewoaEMHn9x8DfcEJefShcW85iDrfBWXOZJa9c="; # set zeros after modifying channel or date
36 };
37 rustChannel = p: (fenix.overlay p p).fenix.toolchainOf chanspec;
38
39 in 26 in
40 { 27 {
41 28
42
43 devShell = forAllSystems (system: 29 devShell = forAllSystems (system:
44 let 30 let
45 pkgs = nixpkgsFor."${system}"; 31 pkgs = nixpkgsFor."${system}";
46 toolchain = (rustChannel pkgs).withComponents [
47 "rustc"
48 "cargo"
49 "rust-std"
50 "rustfmt"
51 "clippy"
52 "rust-src"
53 ];
54 inherit (fenix.packages."${system}") rust-analyzer;
55 in 32 in
56 pkgs.mkShell { 33 pkgs.mkShell {
57 nativeBuildInputs = [ 34 nativeBuildInputs = [
58 pkgs.cargo-watch 35 pkgs.cargo-watch
59 pkgs.bacon 36 pkgs.bacon
60 pkgs.cargo-insta 37 pkgs.cargo-insta
61 rust-analyzer 38 pkgs.rust-analyzer
62 toolchain 39 pkgs.rustc
40 pkgs.rustfmt
41 pkgs.cargo
63 ]; 42 ];
64 RUST_LOG = "info"; 43 RUST_LOG = "info";
65 RUST_BACKTRACE = 1; 44 RUST_BACKTRACE = 1;
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}