From be60a9f66d1c01b15ddc3a56bca0416ce8dee0fd Mon Sep 17 00:00:00 2001 From: Akshay Date: Tue, 16 Jan 2024 21:18:52 +0000 Subject: begin work on stag --- Cargo.lock | 375 ++++++++++++++++++++++- Cargo.toml | 8 +- flake.lock | 45 +-- flake.nix | 29 +- stag/Cargo.toml | 16 + stag/src/main.rs | 810 +++++++++++++++++++++++++++++++++++++++++++++++++ stag/src/scopes.scm | 463 ++++++++++++++++++++++++++++ stag/src/stag.scm | 36 +++ stag/src/text_range.rs | 121 ++++++++ 9 files changed, 1820 insertions(+), 83 deletions(-) create mode 100644 stag/Cargo.toml create mode 100644 stag/src/main.rs create mode 100644 stag/src/scopes.scm create mode 100644 stag/src/stag.scm create mode 100644 stag/src/text_range.rs diff --git a/Cargo.lock b/Cargo.lock index ff68afe..4c838d5 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -2,6 +2,12 @@ # It is not intended for manual editing. version = 3 +[[package]] +name = "ahash" +version = "0.4.8" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0453232ace82dee0dd0b4c87a59bd90f7b53b314f3e0f61fe2ee7c8a16482289" + [[package]] name = "aho-corasick" version = "0.7.19" @@ -19,9 +25,12 @@ checksum = "bef38d45163c2f1dde094a7dfd33ccf595c92905c8f8f4fdc18d06fb1037718a" [[package]] name = "cc" -version = "1.0.73" +version = "1.0.83" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "2fff2a6927b3bb87f9595d67196a70493f627687a71d87a0d692242c33f58c11" +checksum = "f1174fb0b6ec23863f8b971027804a42614e347eafb0a95bf0b12cdae21fc4d0" +dependencies = [ + "libc", +] [[package]] name = "cfg-if" @@ -43,12 +52,34 @@ dependencies = [ "winapi", ] +[[package]] +name = "dissimilar" +version = "1.0.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "86e3bdc80eee6e16b2b6b0f87fbc98c04bee3455e35174c0de1a125d0688c632" + [[package]] name = "encode_unicode" version = "0.3.6" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "a357d28ed41a50f9c765dbfe56cbc04a64e53e5fc58ba79fbc34c10ef3df831f" +[[package]] +name = "equivalent" +version = "1.0.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5443807d6dff69373d433ab9ef5378ad8df50ca6298caf15de6e52e24aaf54d5" + +[[package]] +name = "expect-test" +version = "1.4.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "30d9eafeadd538e68fb28016364c9732d78e420b9ff8853fa5e4058861e9f8d3" +dependencies = [ + "dissimilar", + "once_cell", +] + [[package]] name = "filetime" version = "0.2.17" @@ -61,6 +92,37 @@ dependencies = [ "windows-sys", ] +[[package]] +name = "fixedbitset" +version = "0.4.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0ce7134b9999ecaf8bcd65542e436736ef32ddca1b3e06094cb6ec5755203b80" + +[[package]] +name = "hashbrown" +version = "0.9.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d7afe4a420e3fe79967a00898cc1f4db7c8a49a9333a29f8a4bd76a253d5cd04" +dependencies = [ + "ahash", +] + +[[package]] +name = "hashbrown" +version = "0.14.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "290f1a1d9242c78d09ce40a5e87e7554ee637af1351968159f4952f028f75604" + +[[package]] +name = "indexmap" +version = "2.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d530e1a18b1cb4c484e6e34556a0d948706958449fca0cab753d649f2bce3d1f" +dependencies = [ + "equivalent", + "hashbrown 0.14.3", +] + [[package]] name = "inotify" version = "0.9.6" @@ -81,6 +143,12 @@ dependencies = [ "libc", ] +[[package]] +name = "itoa" +version = "1.0.10" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b1a46d1a171d865aa5f83f92695765caa047a9b4cbae2cbf37dbd613a793fd4c" + [[package]] name = "kqueue" version = "1.0.6" @@ -152,9 +220,45 @@ dependencies = [ [[package]] name = "once_cell" -version = "1.14.0" +version = "1.19.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "2f7254b99e31cad77da24b08ebf628882739a608578bb1bcdfc1f9c21260d7c0" +checksum = "3fdb12b2476b595f9358c5161aa467c2438859caa136dec86c26fdd2efe17b92" + +[[package]] +name = "petgraph" +version = "0.6.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e1d3afd2628e69da2be385eb6f2fd57c8ac7977ceeff6dc166ff1657b0e386a9" +dependencies = [ + "fixedbitset", + "indexmap", + "serde", + "serde_derive", +] + +[[package]] +name = "pin-project-lite" +version = "0.2.13" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8afb450f006bf6385ca15ef45d71d2288452bc3683ce2e2cacc0d18e4be60b58" + +[[package]] +name = "proc-macro2" +version = "1.0.76" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "95fc56cda0b5c3325f5fbbd7ff9fda9e02bb00bb3dac51252d2f1bfa1cb8cc8c" +dependencies = [ + "unicode-ident", +] + +[[package]] +name = "quote" +version = "1.0.35" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "291ec9ab5efd934aaf503a6466c5d5251535d108ee747472c3977cc5acc868ef" +dependencies = [ + "proc-macro2", +] [[package]] name = "redox_syscall" @@ -182,6 +286,12 @@ version = "0.6.27" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "a3f87b73ce11b1619a3c6332f45341e0047173771e8b8b73f87bfeefb7b56244" +[[package]] +name = "ryu" +version = "1.0.16" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f98d2aa92eebf49b69786be48e4477826b256916e84a57ff2a4f21923b48eb4c" + [[package]] name = "same-file" version = "1.0.6" @@ -191,6 +301,103 @@ dependencies = [ "winapi-util", ] +[[package]] +name = "scope-graph" +version = "0.1.0" +dependencies = [ + "expect-test", + "once_cell", + "petgraph", + "serde", + "serde_derive", + "thiserror", + "tracing", + "tree-sitter", + "tree-sitter-c", + "tree-sitter-c-sharp", + "tree-sitter-cpp", + "tree-sitter-go 0.19.1 (git+https://github.com/tree-sitter/tree-sitter-go?rev=05900fa)", + "tree-sitter-java", + "tree-sitter-javascript", + "tree-sitter-php", + "tree-sitter-python", + "tree-sitter-r", + "tree-sitter-ruby", + "tree-sitter-rust", + "tree-sitter-typescript", +] + +[[package]] +name = "serde" +version = "1.0.193" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "25dd9975e68d0cb5aa1120c288333fc98731bd1dd12f561e468ea4728c042b89" +dependencies = [ + "serde_derive", +] + +[[package]] +name = "serde_derive" +version = "1.0.193" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "43576ca501357b9b071ac53cdc7da8ef0cbd9493d8df094cd821777ea6e894d3" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "serde_json" +version = "1.0.109" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "cb0652c533506ad7a2e353cce269330d6afd8bdfb6d75e0ace5b35aacbd7b9e9" +dependencies = [ + "itoa", + "ryu", + "serde", +] + +[[package]] +name = "smallvec" +version = "1.11.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4dccd0940a2dcdf68d092b8cbab7dc0ad8fa938bf95787e1b916b0e3d0e8e970" + +[[package]] +name = "stag" +version = "0.1.0" +dependencies = [ + "once_cell", + "petgraph", + "serde", + "thiserror", + "tree-sitter", + "tree-sitter-graph", + "tree-sitter-rust", +] + +[[package]] +name = "string-interner" +version = "0.12.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "383196d1876517ee6f9f0864d1fc1070331b803335d3c6daaa04bbcccd823c08" +dependencies = [ + "cfg-if", + "hashbrown 0.9.1", +] + +[[package]] +name = "syn" +version = "2.0.48" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0f3531638e407dfc0814761abb7c00a5b54992b849452a0646b7f65c9f770f3f" +dependencies = [ + "proc-macro2", + "quote", + "unicode-ident", +] + [[package]] name = "terminal_size" version = "0.1.17" @@ -201,16 +408,104 @@ dependencies = [ "winapi", ] +[[package]] +name = "thiserror" +version = "1.0.56" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d54378c645627613241d077a3a79db965db602882668f9136ac42af9ecb730ad" +dependencies = [ + "thiserror-impl", +] + +[[package]] +name = "thiserror-impl" +version = "1.0.56" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "fa0faa943b50f3db30a20aa7e265dbc66076993efed8463e8de414e5d06d3471" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "tracing" +version = "0.1.40" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c3523ab5a71916ccf420eebdf5521fcef02141234bbc0b8a49f2fdc4544364ef" +dependencies = [ + "pin-project-lite", + "tracing-attributes", + "tracing-core", +] + +[[package]] +name = "tracing-attributes" +version = "0.1.27" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "34704c8d6ebcbc939824180af020566b01a7c01f80641264eba0999f6c2b6be7" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "tracing-core" +version = "0.1.32" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c06d3da6113f116aaee68e4d601191614c9053067f9ab7f6edbcb161237daa54" +dependencies = [ + "once_cell", +] + [[package]] name = "tree-sitter" -version = "0.20.9" +version = "0.20.10" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "d4423c784fe11398ca91e505cdc71356b07b1a924fc8735cfab5333afe3e18bc" +checksum = "e747b1f9b7b931ed39a548c1fae149101497de3c1fc8d9e18c62c1a66c683d3d" dependencies = [ "cc", "regex", ] +[[package]] +name = "tree-sitter-COBOL" +version = "0.0.1" +dependencies = [ + "cc", + "tree-sitter", +] + +[[package]] +name = "tree-sitter-c" +version = "0.20.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "30b03bdf218020057abee831581a74bff8c298323d6c6cd1a70556430ded9f4b" +dependencies = [ + "cc", + "tree-sitter", +] + +[[package]] +name = "tree-sitter-c-sharp" +version = "0.20.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b9ab3dc608f34924fa9e10533a95f62dbc14b6de0ddd7107722eba66fe19ae31" +dependencies = [ + "cc", + "tree-sitter", +] + +[[package]] +name = "tree-sitter-cpp" +version = "0.20.0" +source = "git+https://github.com/tree-sitter/tree-sitter-cpp?rev=5ead1e2#5ead1e26c6ab71919db0f1880c46a278a93bc5ea" +dependencies = [ + "cc", + "tree-sitter", +] + [[package]] name = "tree-sitter-elm" version = "5.6.3" @@ -232,10 +527,42 @@ dependencies = [ ] [[package]] -name = "tree-sitter-javascript" +name = "tree-sitter-go" +version = "0.19.1" +source = "git+https://github.com/tree-sitter/tree-sitter-go?rev=05900fa#05900faa3cdb5d2d8c8bd5e77ee698487e0a8611" +dependencies = [ + "cc", + "tree-sitter", +] + +[[package]] +name = "tree-sitter-graph" +version = "0.11.0" +dependencies = [ + "log", + "regex", + "serde", + "serde_json", + "smallvec", + "string-interner", + "thiserror", + "tree-sitter", +] + +[[package]] +name = "tree-sitter-java" version = "0.20.0" +source = "git+https://github.com/tree-sitter/tree-sitter-java?tag=v0.20.0#ac14b4b1884102839455d32543ab6d53ae089ab7" +dependencies = [ + "cc", + "tree-sitter", +] + +[[package]] +name = "tree-sitter-javascript" +version = "0.20.1" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "2490fab08630b2c8943c320f7b63473cbf65511c8d83aec551beb9b4375906ed" +checksum = "edbc663376bdd294bd1f0a6daf859aedb9aa5bdb72217d7ad8ba2d5314102cf7" dependencies = [ "cc", "tree-sitter", @@ -250,6 +577,16 @@ dependencies = [ "tree-sitter", ] +[[package]] +name = "tree-sitter-md" +version = "0.1.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5a237fa10f6b466b76c783c79b08cc172581e547ef1dbb6ddf1f8b4e230157e1" +dependencies = [ + "cc", + "tree-sitter", +] + [[package]] name = "tree-sitter-mdx" version = "0.0.1" @@ -270,9 +607,9 @@ dependencies = [ [[package]] name = "tree-sitter-python" -version = "0.20.2" +version = "0.20.4" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "dda114f58048f5059dcf158aff691dffb8e113e6d2b50d94263fd68711975287" +checksum = "e6c93b1b1fbd0d399db3445f51fd3058e43d0b4dcff62ddbdb46e66550978aa5" dependencies = [ "cc", "tree-sitter", @@ -300,9 +637,9 @@ dependencies = [ [[package]] name = "tree-sitter-rust" -version = "0.20.3" +version = "0.20.4" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "797842733e252dc11ae5d403a18060bf337b822fc2ae5ddfaa6ff4d9cc20bda6" +checksum = "b0832309b0b2b6d33760ce5c0e818cb47e1d72b468516bfe4134408926fa7594" dependencies = [ "cc", "tree-sitter", @@ -310,9 +647,9 @@ dependencies = [ [[package]] name = "tree-sitter-typescript" -version = "0.20.1" +version = "0.20.3" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "4e8ed0ecb931cdff13c6a13f45ccd615156e2779d9ffb0395864e05505e6e86d" +checksum = "a75049f0aafabb2aac205d7bb24da162b53dcd0cfb326785f25a2f32efa8071a" dependencies = [ "cc", "tree-sitter", @@ -326,10 +663,12 @@ dependencies = [ "notify", "once_cell", "tree-sitter", + "tree-sitter-COBOL", "tree-sitter-elm", - "tree-sitter-go", + "tree-sitter-go 0.19.1 (registry+https://github.com/rust-lang/crates.io-index)", "tree-sitter-javascript", "tree-sitter-json", + "tree-sitter-md", "tree-sitter-mdx", "tree-sitter-php", "tree-sitter-python", @@ -339,6 +678,12 @@ dependencies = [ "tree-sitter-typescript", ] +[[package]] +name = "unicode-ident" +version = "1.0.12" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3354b9ac3fae1ff6755cb6db53683adb661634f67557942dea4facebec0fee4b" + [[package]] name = "unicode-width" version = "0.1.10" diff --git a/Cargo.toml b/Cargo.toml index d9cd8e1..f57c417 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -1,5 +1,11 @@ [workspace] +resolver = "2" members = [ - "tree-viz" + "tree-viz", + "scope-graph", + "stag", +] +exclude = [ + "tree-sitter-graph" ] diff --git a/flake.lock b/flake.lock index a7c083f..ec56c37 100644 --- a/flake.lock +++ b/flake.lock @@ -1,26 +1,5 @@ { "nodes": { - "fenix": { - "inputs": { - "nixpkgs": [ - "nixpkgs" - ], - "rust-analyzer-src": "rust-analyzer-src" - }, - "locked": { - "lastModified": 1645251813, - "narHash": "sha256-cQ66tGjnZclBCS3nD26mZ5fUH+3/HnysGffBiWXUSHk=", - "owner": "nix-community", - "repo": "fenix", - "rev": "9892337b588c38ec59466a1c89befce464aae7f8", - "type": "github" - }, - "original": { - "owner": "nix-community", - "repo": "fenix", - "type": "github" - } - }, "gitignore": { "inputs": { "nixpkgs": [ @@ -43,11 +22,11 @@ }, "nixpkgs": { "locked": { - "lastModified": 1645013224, - "narHash": "sha256-b7OEC8vwzJv3rsz9pwnTX2LQDkeOWz2DbKypkVvNHXc=", + "lastModified": 1704161960, + "narHash": "sha256-QGua89Pmq+FBAro8NriTuoO/wNaUtugt29/qqA8zeeM=", "owner": "nixos", "repo": "nixpkgs", - "rev": "b66b39216b1fef2d8c33cc7a5c72d8da80b79970", + "rev": "63143ac2c9186be6d9da6035fa22620018c85932", "type": "github" }, "original": { @@ -59,27 +38,9 @@ }, "root": { "inputs": { - "fenix": "fenix", "gitignore": "gitignore", "nixpkgs": "nixpkgs" } - }, - "rust-analyzer-src": { - "flake": false, - "locked": { - "lastModified": 1645205556, - "narHash": "sha256-e4lZW3qRyOEJ+vLKFQP7m2Dxh5P44NrnekZYLxlucww=", - "owner": "rust-analyzer", - "repo": "rust-analyzer", - "rev": "acf5874b39f3dc5262317a6074d9fc7285081161", - "type": "github" - }, - "original": { - "owner": "rust-analyzer", - "ref": "nightly", - "repo": "rust-analyzer", - "type": "github" - } } }, "root": "root", diff --git a/flake.nix b/flake.nix index 861792b..5f0f1d6 100644 --- a/flake.nix +++ b/flake.nix @@ -3,11 +3,6 @@ nixpkgs.url = "github:nixos/nixpkgs/nixpkgs-unstable"; - fenix = { - url = "github:nix-community/fenix"; - inputs.nixpkgs.follows = "nixpkgs"; - }; - gitignore = { url = "github:hercules-ci/gitignore.nix"; inputs.nixpkgs.follows = "nixpkgs"; @@ -18,7 +13,6 @@ outputs = { self , nixpkgs - , fenix , gitignore }: let @@ -29,37 +23,22 @@ nixpkgsFor = forAllSystems (system: import nixpkgs { inherit system; }); - chanspec = { - date = "2022-09-01"; - channel = "nightly"; - sha256 = "tS2IHsewoaEMHn9x8DfcEJefShcW85iDrfBWXOZJa9c="; # set zeros after modifying channel or date - }; - rustChannel = p: (fenix.overlay p p).fenix.toolchainOf chanspec; - in { - devShell = forAllSystems (system: let pkgs = nixpkgsFor."${system}"; - toolchain = (rustChannel pkgs).withComponents [ - "rustc" - "cargo" - "rust-std" - "rustfmt" - "clippy" - "rust-src" - ]; - inherit (fenix.packages."${system}") rust-analyzer; in pkgs.mkShell { nativeBuildInputs = [ pkgs.cargo-watch pkgs.bacon pkgs.cargo-insta - rust-analyzer - toolchain + pkgs.rust-analyzer + pkgs.rustc + pkgs.rustfmt + pkgs.cargo ]; RUST_LOG = "info"; 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 @@ +[package] +name = "stag" +version = "0.1.0" +edition = "2021" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] +petgraph = { version = "0.6.4", default-features = false, features = ["serde-1"] } +serde = {version = "1.0.188", features = ["derive"]} +once_cell = "1.19.0" +thiserror = "1.0.56" +tree-sitter-graph = { path = "../tree-sitter-graph/"} +tree-sitter-rust = "0.20.4" +tree-sitter = "0.20.10" + 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 @@ +use std::collections::VecDeque; + +use serde::Deserialize; +use serde::Serialize; +use tree_sitter::Parser; +use tree_sitter_graph::ast::File; +use tree_sitter_graph::functions::{Function, Functions}; +use tree_sitter_graph::graph::Value; +use tree_sitter_graph::ExecutionConfig; +use tree_sitter_graph::ExecutionError; +use tree_sitter_graph::Identifier; +use tree_sitter_graph::NoCancellation; +use tree_sitter_graph::Variables; + +mod text_range; +use text_range::TextRange; + +use petgraph::{graph::NodeIndex, visit::EdgeRef, Direction, Graph}; + +fn main() { + let scopes = std::fs::read_to_string("src/stag.scm").unwrap(); + let src = r#"fn main() { + let a = 3; + let b = 4; + a + b +} + "#; + + let mut parser = Parser::new(); + let language = tree_sitter_rust::language(); + parser.set_language(language).unwrap(); + let tree = parser.parse(src.as_bytes(), None).unwrap(); + + let file = File::from_str(language, &scopes).unwrap(); + + let mut functions = Functions::stdlib(); + functions.add(Identifier::from("scope"), ScopeShorthand); + functions.add(Identifier::from("def"), DefShorthand); + functions.add(Identifier::from("ref"), RefShortHand); + functions.add(Identifier::from("cover"), CoverRanges); + functions.add(Identifier::from("range"), NodeRange); + + let mut globals = Variables::new(); + globals + .add(Identifier::from("filename"), "test.rs".into()) + .map_err(|_| ExecutionError::DuplicateVariable("filename".into())) + .unwrap(); + + let config = ExecutionConfig::new(&functions, &globals); + + let graph = file.execute(&tree, &src, &config, &NoCancellation).unwrap(); + + let mut sg = ScopeGraph::new(tree.root_node().range().into()); + + sg = build_scope_graph(graph, sg); + + println!("{:#?}", sg); +} + +fn range_to_value(value: &tree_sitter::Range) -> Value { + let start = Value::from(vec![ + Value::from(value.start_byte as u32), + Value::from(value.start_point.row as u32), + Value::from(value.start_point.column as u32), + ]); + let end = Value::from(vec![ + Value::from(value.end_byte as u32), + Value::from(value.end_point.row as u32), + Value::from(value.end_point.column as u32), + ]); + Value::from(vec![start, end]) +} + +fn value_to_range(value: &Value) -> tree_sitter::Range { + let range = value.as_list().unwrap(); + let start = range[0].as_list().unwrap(); + let end = range[1].as_list().unwrap(); + tree_sitter::Range { + start_byte: start[0].as_integer().unwrap() as usize, + start_point: tree_sitter::Point { + row: start[1].as_integer().unwrap() as usize, + column: start[2].as_integer().unwrap() as usize, + }, + end_byte: end[0].as_integer().unwrap() as usize, + end_point: tree_sitter::Point { + row: end[1].as_integer().unwrap() as usize, + column: end[2].as_integer().unwrap() as usize, + }, + } +} + +fn is_string_attr(node: &tree_sitter_graph::graph::GraphNode, key: &str, value: &str) -> bool { + matches!(node.attributes.get(&Identifier::from(key)).and_then(|v| v.as_str().ok()), Some(v) if v == value) +} + +fn is_scope(node: &tree_sitter_graph::graph::GraphNode) -> bool { + is_string_attr(node, "kind", "scope") +} + +fn is_import(node: &tree_sitter_graph::graph::GraphNode) -> bool { + is_string_attr(node, "kind", "import") +} + +fn is_def(node: &tree_sitter_graph::graph::GraphNode) -> bool { + is_string_attr(node, "kind", "def") +} + +fn is_ref(node: &tree_sitter_graph::graph::GraphNode) -> bool { + is_string_attr(node, "kind", "ref") +} + +pub struct ScopeShorthand; + +impl Function for ScopeShorthand { + fn call( + &self, + graph: &mut tree_sitter_graph::graph::Graph, + source: &str, + parameters: &mut dyn tree_sitter_graph::functions::Parameters, + ) -> Result { + let target_range = parameters.param()?; + if target_range.as_list().is_err() { + return Err(ExecutionError::ExpectedList(format!( + "`scope` expects list" + ))); + } + parameters.finish()?; + + let graph_node = graph.add_graph_node(); + graph[graph_node] + .attributes + .add::(Identifier::from("kind"), "scope".into()); + graph[graph_node] + .attributes + .add(Identifier::from("range"), target_range); + + Ok(tree_sitter_graph::graph::Value::GraphNode(graph_node)) + } +} + +pub struct DefShorthand; + +impl Function for DefShorthand { + fn call( + &self, + graph: &mut tree_sitter_graph::graph::Graph, + source: &str, + parameters: &mut dyn tree_sitter_graph::functions::Parameters, + ) -> Result { + let target_node = parameters.param()?.into_syntax_node_ref()?; + let ts_node = graph[target_node]; + parameters.finish()?; + + let graph_node = graph.add_graph_node(); + graph[graph_node] + .attributes + .add::(Identifier::from("kind"), "def".into()); + graph[graph_node] + .attributes + .add::(Identifier::from("scope"), "local".into()); + graph[graph_node].attributes.add::( + Identifier::from("text"), + source[ts_node.byte_range()].to_string().into(), + ); + graph[graph_node] + .attributes + .add(Identifier::from("range"), range_to_value(&ts_node.range())); + graph[graph_node] + .attributes + .add::( + Identifier::from("target"), + target_node.into(), + ); + + Ok(tree_sitter_graph::graph::Value::GraphNode(graph_node)) + } +} + +pub struct RefShortHand; + +impl Function for RefShortHand { + fn call( + &self, + graph: &mut tree_sitter_graph::graph::Graph, + source: &str, + parameters: &mut dyn tree_sitter_graph::functions::Parameters, + ) -> Result { + let target_node = parameters.param()?.into_syntax_node_ref()?; + let ts_node = graph[target_node]; + parameters.finish()?; + + let graph_node = graph.add_graph_node(); + graph[graph_node] + .attributes + .add::(Identifier::from("kind"), "ref".into()); + graph[graph_node].attributes.add::( + Identifier::from("text"), + source[ts_node.byte_range()].to_string().into(), + ); + graph[graph_node] + .attributes + .add(Identifier::from("range"), range_to_value(&ts_node.range())); + graph[graph_node] + .attributes + .add::( + Identifier::from("target"), + target_node.into(), + ); + + Ok(tree_sitter_graph::graph::Value::GraphNode(graph_node)) + } +} + +pub struct CoverRanges; + +impl Function for CoverRanges { + fn call( + &self, + graph: &mut tree_sitter_graph::graph::Graph, + _source: &str, + parameters: &mut dyn tree_sitter_graph::functions::Parameters, + ) -> Result { + let node_a = parameters.param()?.into_syntax_node_ref()?; + let node_b = parameters.param()?.into_syntax_node_ref()?; + let ts_node_a = graph[node_a]; + let ts_node_b = graph[node_b]; + + let mut range = cover(ts_node_a.range(), ts_node_b.range()); + while let Ok(param) = parameters.param() { + range = cover(range, graph[param.into_syntax_node_ref()?].range()) + } + + Ok(range_to_value(&range)) + } +} + +fn cover(a: tree_sitter::Range, b: tree_sitter::Range) -> tree_sitter::Range { + let (start_byte, start_point) = if a.start_point < b.start_point { + (a.start_byte, a.start_point) + } else { + (b.start_byte, b.start_point) + }; + let (end_byte, end_point) = if a.end_point > b.end_point { + (a.end_byte, a.end_point) + } else { + (b.end_byte, b.end_point) + }; + tree_sitter::Range { + start_byte, + start_point, + end_byte, + end_point, + } +} + +pub struct NodeRange; + +impl Function for NodeRange { + fn call( + &self, + graph: &mut tree_sitter_graph::graph::Graph, + _source: &str, + parameters: &mut dyn tree_sitter_graph::functions::Parameters, + ) -> Result { + let target_node = parameters.param()?.into_syntax_node_ref()?; + let ts_node = graph[target_node]; + Ok(range_to_value(&ts_node.range())) + } +} + +#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq, Hash)] +pub struct LocalDef { + pub range: TextRange, + pub text: String, + pub symbol: Option, +} + +impl LocalDef { + /// Initialize a new definition + pub fn new(range: TextRange, text: String, symbol: Option) -> Self { + Self { + range, + text, + symbol, + } + } + + pub fn name<'a>(&self, buffer: &'a [u8]) -> &'a [u8] { + &buffer[self.range.start.byte..self.range.end.byte] + } +} + +#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq, Hash)] +pub struct LocalImport { + pub range: TextRange, + pub text: String, +} + +impl LocalImport { + /// Initialize a new import + pub fn new(range: TextRange, text: String) -> Self { + Self { range, text } + } + + pub fn name<'a>(&self, buffer: &'a [u8]) -> &'a [u8] { + &buffer[self.range.start.byte..self.range.end.byte] + } +} + +#[derive(Debug, Clone, Serialize, Deserialize)] +pub struct Reference { + pub range: TextRange, + pub text: String, + pub symbol: Option, +} + +impl Reference { + /// Initialize a new reference + pub fn new(range: TextRange, text: String, symbol: Option) -> Self { + Self { + range, + text, + symbol, + } + } +} + +#[derive(Debug, Clone, Copy, Serialize, Deserialize)] +pub struct LocalScope { + pub range: TextRange, +} + +impl LocalScope { + pub fn new(range: TextRange) -> Self { + Self { range } + } +} + +pub struct ScopeStack<'a> { + pub scope_graph: &'a ScopeGraph, + pub start: Option>, +} + +impl<'a> Iterator for ScopeStack<'a> { + type Item = NodeIndex; + fn next(&mut self) -> Option { + if let Some(start) = self.start { + let parent = self + .scope_graph + .graph + .edges_directed(start, Direction::Outgoing) + .find(|edge| *edge.weight() == EdgeKind::ScopeToScope) + .map(|edge| edge.target()); + let original = start; + self.start = parent; + Some(original) + } else { + None + } + } +} + +/// The type of a node in the ScopeGraph +#[derive(Serialize, Deserialize, Debug, Clone)] +pub enum NodeKind { + /// A scope node + Scope(LocalScope), + + /// A definition node + Def(LocalDef), + + /// An import node + Import(LocalImport), + + /// A reference node + Ref(Reference), +} + +impl NodeKind { + /// Construct a scope node from a range + pub fn scope(range: TextRange) -> Self { + Self::Scope(LocalScope::new(range)) + } + + /// Produce the range spanned by this node + pub fn range(&self) -> TextRange { + match self { + Self::Scope(l) => l.range, + Self::Def(d) => d.range, + Self::Ref(r) => r.range, + Self::Import(i) => i.range, + } + } +} + +/// Describes the relation between two nodes in the ScopeGraph +#[derive(Serialize, Deserialize, PartialEq, Eq, Copy, Clone, Debug)] +pub enum EdgeKind { + /// The edge weight from a nested scope to its parent scope + ScopeToScope, + + /// The edge weight from a definition to its definition scope + DefToScope, + + /// The edge weight from an import to its definition scope + ImportToScope, + + /// The edge weight from a reference to its definition + RefToDef, + + /// The edge weight from a reference to its import + RefToImport, +} + +/// A graph representation of scopes and names in a single syntax tree +#[derive(Debug, Serialize, Deserialize, Clone)] +pub struct ScopeGraph { + /// The raw graph + pub graph: Graph, + + // Graphs do not have the concept of a `root`, but lexical scopes follow the syntax + // tree, and as a result, have a "root" node. The root_idx points to a scope node that + // encompasses the entire file: the file-global scope. + root_idx: NodeIndex, +} + +impl ScopeGraph { + pub fn new(range: TextRange) -> Self { + let mut graph = Graph::new(); + let root_idx = graph.add_node(NodeKind::scope(range)); + Self { graph, root_idx } + } + + pub fn get_node(&self, node_idx: NodeIndex) -> Option<&NodeKind> { + self.graph.node_weight(node_idx) + } + + /// Insert a local scope into the scope-graph + pub fn insert_local_scope(&mut self, new: LocalScope) { + if let Some(parent_scope) = self.scope_by_range(new.range, self.root_idx) { + let new_scope = NodeKind::Scope(new); + let new_idx = self.graph.add_node(new_scope); + self.graph + .add_edge(new_idx, parent_scope, EdgeKind::ScopeToScope); + } + } + + /// Insert a def into the scope-graph + pub fn insert_local_def(&mut self, new: LocalDef) { + if let Some(defining_scope) = self.scope_by_range(new.range, self.root_idx) { + let new_def = NodeKind::Def(new); + let new_idx = self.graph.add_node(new_def); + self.graph + .add_edge(new_idx, defining_scope, EdgeKind::DefToScope); + } + } + + /// Insert a def into the scope-graph, at the parent scope of the defining scope + pub fn insert_hoisted_def(&mut self, new: LocalDef) { + if let Some(defining_scope) = self.scope_by_range(new.range, self.root_idx) { + let new_def = NodeKind::Def(new); + let new_idx = self.graph.add_node(new_def); + + // if the parent scope exists, insert this def there, if not, + // insert into the defining scope + let target_scope = self.parent_scope(defining_scope).unwrap_or(defining_scope); + + self.graph + .add_edge(new_idx, target_scope, EdgeKind::DefToScope); + } + } + + /// Insert a def into the scope-graph, at the root scope + pub fn insert_global_def(&mut self, new: LocalDef) { + let new_def = NodeKind::Def(new); + let new_idx = self.graph.add_node(new_def); + self.graph + .add_edge(new_idx, self.root_idx, EdgeKind::DefToScope); + } + + /// Insert an import into the scope-graph + pub fn insert_local_import(&mut self, new: LocalImport) { + if let Some(defining_scope) = self.scope_by_range(new.range, self.root_idx) { + let new_imp = NodeKind::Import(new); + let new_idx = self.graph.add_node(new_imp); + self.graph + .add_edge(new_idx, defining_scope, EdgeKind::ImportToScope); + } + } + + /// Insert a ref into the scope-graph + pub fn insert_ref(&mut self, new: Reference) { + let mut possible_defs = vec![]; + let mut possible_imports = vec![]; + if let Some(local_scope_idx) = self.scope_by_range(new.range, self.root_idx) { + // traverse the scopes from the current-scope to the root-scope + for scope in self.scope_stack(local_scope_idx) { + // find candidate definitions in each scope + for local_def in self + .graph + .edges_directed(scope, Direction::Incoming) + .filter(|edge| *edge.weight() == EdgeKind::DefToScope) + .map(|edge| edge.source()) + { + if let NodeKind::Def(def) = &self.graph[local_def] { + if new.text == def.text { + match (def.symbol.as_ref(), new.symbol.as_ref()) { + // both contain symbols, but they don't belong to the same namepspace + (Some(d), Some(r)) if d != r => {} + + // in all other cases, form an edge from the ref to def. + // an empty symbol belongs to all namespaces: + // * (None, None) + // * (None, Some(_)) + // * (Some(_), None) + // * (Some(_), Some(_)) if def.namespace == ref.namespace + _ => { + possible_defs.push(local_def); + } + }; + } + } + } + + // find candidate imports in each scope + for local_import in self + .graph + .edges_directed(scope, Direction::Incoming) + .filter(|edge| *edge.weight() == EdgeKind::ImportToScope) + .map(|edge| edge.source()) + { + if let NodeKind::Import(import) = &self.graph[local_import] { + if new.text == import.text { + possible_imports.push(local_import); + } + } + } + } + } + + if !possible_defs.is_empty() || !possible_imports.is_empty() { + let new_ref = NodeKind::Ref(new); + let ref_idx = self.graph.add_node(new_ref); + for def_idx in possible_defs { + self.graph.add_edge(ref_idx, def_idx, EdgeKind::RefToDef); + } + for imp_idx in possible_imports { + self.graph.add_edge(ref_idx, imp_idx, EdgeKind::RefToImport); + } + } + } + + fn scope_stack(&self, start: NodeIndex) -> ScopeStack<'_> { + ScopeStack { + scope_graph: self, + start: Some(start), + } + } + + // The smallest scope that encompasses `range`. Start at `start` and narrow down if possible. + fn scope_by_range(&self, range: TextRange, start: NodeIndex) -> Option { + let target_range = self.graph[start].range(); + if target_range.contains(&range) { + let mut child_scopes = self + .graph + .edges_directed(start, Direction::Incoming) + .filter(|edge| *edge.weight() == EdgeKind::ScopeToScope) + .map(|edge| edge.source()) + .collect::>(); + + child_scopes.sort_by_key(|s| self.graph[*s].range()); + let target_child_scope = child_scopes.binary_search_by(|x| { + if self.graph[*x].range().contains(&range) { + std::cmp::Ordering::Equal + } else { + self.graph[*x].range().cmp(&range) + } + }); + + if let Some(t) = target_child_scope + .ok() + .and_then(|idx| child_scopes.get(idx)) + .and_then(|s| self.scope_by_range(range, *s)) + { + return Some(t); + } else { + return Some(start); + } + } + None + } + + // Produce the parent scope of a given scope + fn parent_scope(&self, start: NodeIndex) -> Option { + if matches!(self.graph[start], NodeKind::Scope(_)) { + return self + .graph + .edges_directed(start, Direction::Outgoing) + .filter(|edge| *edge.weight() == EdgeKind::ScopeToScope) + .map(|edge| edge.target()) + .next(); + } + None + } + + /// Produce a list of interesting ranges: ranges of defs and refs + pub fn hoverable_ranges(&self) -> Box + '_> { + let iterator = + self.graph + .node_indices() + .filter_map(|node_idx| match &self.graph[node_idx] { + NodeKind::Scope(_) => None, + NodeKind::Def(d) => Some(d.range), + NodeKind::Ref(r) => Some(r.range), + NodeKind::Import(i) => Some(i.range), + }); + Box::new(iterator) + } + + /// Produce possible definitions for a reference + pub fn definitions( + &self, + reference_node: NodeIndex, + ) -> Box + '_> { + let iterator = self + .graph + .edges_directed(reference_node, Direction::Outgoing) + .filter(|edge| *edge.weight() == EdgeKind::RefToDef) + .map(|edge| edge.target()); + Box::new(iterator) + } + + /// Produce possible imports for a reference + pub fn imports(&self, reference_node: NodeIndex) -> Box + '_> { + let iterator = self + .graph + .edges_directed(reference_node, Direction::Outgoing) + .filter(|edge| *edge.weight() == EdgeKind::RefToImport) + .map(|edge| edge.target()); + Box::new(iterator) + } + + /// Produce possible references for a definition/import node + pub fn references( + &self, + definition_node: NodeIndex, + ) -> Box + '_> { + let iterator = self + .graph + .edges_directed(definition_node, Direction::Incoming) + .filter(|edge| { + *edge.weight() == EdgeKind::RefToDef || *edge.weight() == EdgeKind::RefToImport + }) + .map(|edge| edge.source()); + Box::new(iterator) + } + + pub fn node_by_range(&self, start_byte: usize, end_byte: usize) -> Option { + self.graph + .node_indices() + .filter(|&idx| self.is_definition(idx) || self.is_reference(idx) || self.is_import(idx)) + .find(|&idx| { + let node = self.graph[idx].range(); + start_byte >= node.start.byte && end_byte <= node.end.byte + }) + } + + /// The "value" of a definition is loosely characterized as + /// + /// - the body of a function block + /// - the body of a class + /// - the parameters list defining generic types + /// - the RHS of a value + /// + /// The heuristic used here is + /// - the smallest scope-node that encompasses the definition_node + /// - or the largest scope-node on the same line as the to the definition_node + pub fn value_of_definition(&self, def_idx: NodeIndex) -> Option { + let smallest_scope_node = self + .scope_by_range(self.graph[def_idx].range(), self.root_idx) + .filter(|&idx| { + self.graph[idx].range().start.line == self.graph[def_idx].range().start.line + }); + let largest_adjacent_node = self + .graph + .node_indices() + .filter(|&idx| match self.graph[idx] { + NodeKind::Scope(scope) => { + scope.range.start.line == self.graph[def_idx].range().start.line + } + _ => false, + }) + .max_by_key(|idx| self.graph[*idx].range().size()); + + smallest_scope_node.or(largest_adjacent_node) + } + + pub fn node_by_position(&self, line: usize, column: usize) -> Option { + self.graph + .node_indices() + .filter(|&idx| self.is_definition(idx) || self.is_reference(idx)) + .find(|&idx| { + let node = self.graph[idx].range(); + node.start.line == line + && node.end.line == line + && node.start.column <= column + && node.end.column >= column + }) + } + + #[cfg(test)] + pub fn find_node_by_name(&self, src: &[u8], name: &[u8]) -> Option { + self.graph.node_indices().find(|idx| { + matches!( + &self.graph[*idx], + NodeKind::Def(d) if d.name(src) == name) + }) + } + + pub fn is_definition(&self, node_idx: NodeIndex) -> bool { + matches!(self.graph[node_idx], NodeKind::Def(_)) + } + + pub fn is_reference(&self, node_idx: NodeIndex) -> bool { + matches!(self.graph[node_idx], NodeKind::Ref(_)) + } + + pub fn is_scope(&self, node_idx: NodeIndex) -> bool { + matches!(self.graph[node_idx], NodeKind::Scope(_)) + } + + pub fn is_import(&self, node_idx: NodeIndex) -> bool { + matches!(self.graph[node_idx], NodeKind::Import(_)) + } +} + +fn build_scope_graph( + tsg: tree_sitter_graph::graph::Graph, + mut scope_graph: ScopeGraph, +) -> ScopeGraph { + let nodes = tsg.iter_nodes().collect::>(); + // insert scopes first + for node in nodes + .iter() + .map(|node_ref| &tsg[*node_ref]) + .filter(|node| is_scope(node)) + { + let range = value_to_range(node.attributes.get(&Identifier::from("range")).unwrap()); + let scope = LocalScope::new(range.into()); + scope_graph.insert_local_scope(scope); + } + + for node in nodes + .iter() + .map(|node_ref| &tsg[*node_ref]) + .filter(|node| is_import(node)) + { + let range = value_to_range(node.attributes.get(&Identifier::from("range")).unwrap()); + let text = node + .attributes + .get(&Identifier::from("text")) + .and_then(|id| id.clone().into_string().ok()) + .expect("import without text"); + let import = LocalImport::new(range.into(), text); + scope_graph.insert_local_import(import); + } + + for node in nodes + .iter() + .map(|node_ref| &tsg[*node_ref]) + .filter(|node| is_def(node)) + { + let range = value_to_range(node.attributes.get(&Identifier::from("range")).unwrap()); + let symbol = node + .attributes + .get(&Identifier::from("symbol")) + .and_then(|id| id.clone().into_string().ok()); + let text = node + .attributes + .get(&Identifier::from("text")) + .and_then(|id| id.clone().into_string().ok()) + .expect("def without text"); + let local_def = LocalDef::new(range.into(), text, symbol); + + // TODO: fix scoping here + scope_graph.insert_local_def(local_def); + } + + for node in nodes + .iter() + .map(|node_ref| &tsg[*node_ref]) + .filter(|node| is_ref(node)) + { + let range = value_to_range(node.attributes.get(&Identifier::from("range")).unwrap()); + let symbol = node + .attributes + .get(&Identifier::from("symbol")) + .and_then(|id| id.clone().into_string().ok()); + let text = node + .attributes + .get(&Identifier::from("text")) + .and_then(|id| id.clone().into_string().ok()) + .expect("ref without text"); + let ref_ = Reference::new(range.into(), text, symbol); + + scope_graph.insert_ref(ref_); + } + + scope_graph +} 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 @@ +;; see tree-sitter-rust/src/grammar.json for an exhaustive list of productions + +;; scopes +(block) @local.scope ; { ... } +(function_item) @local.scope +(declaration_list) @local.scope ; mod { ... } + +;; impl items can define types and lifetimes: +;; +;; impl<'a, T> Trait for Struct { .. } +;; +;; in order to constrain those to the impl block, +;; we add a local scope here: +(impl_item) @local.scope +(struct_item) @local.scope +(enum_item) @local.scope +(union_item) @local.scope +(type_item) @local.scope +(trait_item) @local.scope + +;; let expressions create scopes +(if_expression + [(let_condition) + (let_chain)]) @local.scope + +;; each match arm can bind variables with +;; patterns, without creating a block scope; +;; +;; match _ { +;; (a, b) => a, +;; } +;; +;; The bindings for a, b are constrained to +;; the match arm. +(match_arm) @local.scope + +;; loop labels are defs that are available only +;; within the scope they create: +;; +;; 'outer: loop { +;; let x = 2; +;; }; +;; let y = 2; +;; +;; Produces a scope graph like so: +;; +;; { +;; defs: [ y ], +;; scopes: [ +;; { +;; defs: [ 'outer ], +;; scopes: [ +;; { +;; defs: [ x ] +;; } +;; ] +;; } +;; ] +;; } +;; +(loop_expression) @local.scope +(for_expression) @local.scope +(while_expression) @local.scope + + +;; defs + +;; let x = ...; +(let_declaration + pattern: (identifier) @local.definition.variable) + +;; if let x = ...; +;; while let x = ...; +(let_condition + . + (identifier) @local.definition.variable) + +;; let (a, b, ...) = ..; +;; if let (a, b, ...) = {} +;; while let (a, b, ...) = {} +;; match _ { (a, b) => { .. } } +(tuple_pattern (identifier) @local.definition.variable) + +;; Some(a) +(tuple_struct_pattern + type: (_) + (identifier) @local.definition.variable) + +;; let S { field: a } = ..; +(struct_pattern + (field_pattern + (identifier) @local.definition.variable)) + +;; let S { a, b } = ..; +(struct_pattern + (field_pattern + (shorthand_field_identifier) @local.definition.variable)) + +;; (mut x: T) +(mut_pattern (identifier) @local.definition.variable) + +;; (ref x: T) +(ref_pattern (identifier) @local.definition.variable) + +;; const x = ...; +(const_item (identifier) @local.definition.const) + +;; static x = ...; +(static_item (identifier) @local.definition.const) + +;; fn _(x: _) +(parameters + (parameter + pattern: (identifier) @local.definition.variable)) +;; fn _(self) +(parameters + (self_parameter + (self) @local.definition.variable)) + +;; type parameters +(type_parameters + (type_identifier) @local.definition.typedef) +(type_parameters + (lifetime) @local.definition.lifetime) +(constrained_type_parameter + left: (type_identifier) @local.definition.typedef) + +;; |x| { ... } +;; no type +(closure_parameters (identifier) @local.definition.variable) + +;; |x: T| { ... } +;; with type +(closure_parameters + (parameter + (identifier) @local.definition.variable)) + +;;fn x(..) +(function_item (identifier) @hoist.definition.function) + +;; 'outer: loop { .. } +(loop_expression + (loop_label) @local.definition.label) + +;; `for` exprs create two defs: a label (if any) and the +;; loop variable +(for_expression . (identifier) @local.definition.variable) +(for_expression (loop_label) @local.definition.label) + +;; 'label: while cond { .. } +(while_expression + (loop_label) @local.definition.label) + +;; type definitions +(struct_item (type_identifier) @hoist.definition.struct) +(enum_item (type_identifier) @hoist.definition.enum) +(union_item (type_identifier) @hoist.definition.union) +(type_item . (type_identifier) @hoist.definition.typedef) +(trait_item (type_identifier) @hoist.definition.interface) + +;; struct and union fields +(field_declaration_list + (field_declaration + (field_identifier) @local.definition.field)) + +;; enum variants +(enum_variant_list + (enum_variant + (identifier) @local.definition.enumerator)) + +;; mod x; +(mod_item (identifier) @local.definition.module) + +;; use statements + +;; use item; +(use_declaration + (identifier) @local.import) + +;; use path as item; +(use_as_clause + alias: (identifier) @local.import) + +;; use path::item; +(use_declaration + (scoped_identifier + name: (identifier) @local.import)) + +;; use module::{member1, member2, member3}; +(use_list + (identifier) @local.import) +(use_list + (scoped_identifier + name: (identifier) @local.import)) + + +;; refs + +;; !x +(unary_expression (identifier) @local.reference) + +;; &x +(reference_expression (identifier) @local.reference) + +;; (x) +(parenthesized_expression (identifier) @local.reference) + +;; x? +(try_expression (identifier) @local.reference) + +;; a = b +(assignment_expression (identifier) @local.reference) + +;; a op b +(binary_expression (identifier) @local.reference) + +;; a op= b +(compound_assignment_expr (identifier) @local.reference) + +;; a as b +(type_cast_expression (identifier) @local.reference) + +;; a() +(call_expression (identifier) @local.reference) + +;; Self::foo() +;; +;; `foo` can be resolved +(call_expression + (scoped_identifier + (identifier) @_self_type + (identifier) @local.reference) + (#match? @_self_type "Self")) + +;; self.foo() +;; +;; `foo` can be resolved +(call_expression + (field_expression + (self) + (field_identifier) @local.reference)) + +;; return a +(return_expression (identifier) @local.reference) + +;; break a +(break_expression (identifier) @local.reference) + +;; break 'label +(break_expression (loop_label) @local.reference) + +;; continue 'label; +(continue_expression (loop_label) @local.reference) + +;; yield x; +(yield_expression (identifier) @local.reference) + +;; await a +(await_expression (identifier) @local.reference) + +;; (a, b) +(tuple_expression (identifier) @local.reference) + +;; a[] +(index_expression (identifier) @local.reference) + +;; ident; +(expression_statement (identifier) @local.reference) + +;; a..b +(range_expression (identifier) @local.reference) + +;; [ident; N] +(array_expression (identifier) @local.reference) + +;; path::to::item +;; +;; `path` is a ref +(scoped_identifier + path: (identifier) @local.reference) + +;; rhs of let decls +(let_declaration + value: (identifier) @local.reference) + +;; type T = [T; N] +;; +;; N is a ident ref +(array_type + length: (identifier) @local.reference) + +;; S { _ } +(struct_expression + (type_identifier) @local.reference) + +;; S { a } +(struct_expression + (field_initializer_list + (shorthand_field_initializer + (identifier) @local.reference))) + +;; S { a: value } +(struct_expression + (field_initializer_list + (field_initializer + (identifier) @local.reference))) + +;; S { ..a } +(struct_expression + (field_initializer_list + (base_field_initializer + (identifier) @local.reference))) + +;; if a {} +(if_expression (identifier) @local.reference) + +;; for pattern in value {} +;; +;; `value` is a ref +(for_expression + value: (identifier) @local.reference) + +;; while a {} +(while_expression (identifier) @local.reference) + +;; if let _ = a {} +;; +;; the ident following the `=` is a ref +;; the ident preceding the `=` is a def +;; while let _ = a {} +(let_condition + "=" + (identifier) @local.reference) + + +;; match a +(match_expression (identifier) @local.reference) + +;; match _ { +;; pattern => a, +;; } +;; +;; this `a` is somehow not any expression form +(match_arm (identifier) @local.reference) + +;; a.b +;; +;; `b` is ignored +(field_expression + (identifier) @local.reference) + +;; { stmt; foo } +(block + (identifier) @local.reference) + +;; arguments to method calls or function calls +(arguments + (identifier) @local.reference) + +;; impl S { .. } +(impl_item (type_identifier) @local.reference) + +;; where T: ... +(where_predicate + left: (type_identifier) @local.reference) + +;; trait bounds +(trait_bounds + (type_identifier) @local.reference) +(trait_bounds + (lifetime) @local.reference) + +;; idents in macros +(token_tree + (identifier) @local.reference) + +;; types + +;; (T, U) +(tuple_type + (type_identifier) @local.reference) + +;; &T +(reference_type + (type_identifier) @local.reference) + +;; &'a T +(reference_type + (lifetime) @local.reference) + +;; &'a self +(self_parameter + (lifetime) @local.reference) + +;; *mut T +;; *const T +(pointer_type + (type_identifier) @local.reference) + +;; A<_> +(generic_type + (type_identifier) @local.reference) + +;; _ +(type_arguments + (type_identifier) @local.reference) +(type_arguments + (lifetime) @local.reference) + +;; T +;; +;; U is ignored +;; V is a ref +(type_binding + name: (_) + type: (type_identifier) @local.reference) + +;; [T] +(array_type + (type_identifier) @local.reference) + +;; type T = U; +;; +;; T is a def +;; U is a ref +(type_item + name: (_) + type: (type_identifier) @local.reference) + +(function_item + return_type: (type_identifier) @local.reference) + +;; type refs in params +;; +;; fn _(_: T) +(parameters + (parameter + type: (type_identifier) @local.reference)) + +;; dyn T +(dynamic_type + (type_identifier) @local.reference) + +;; ::call() +(bracketed_type + (type_identifier) @local.reference) + +;; T as Trait +(qualified_type + (type_identifier) @local.reference) + +;; module::T +;; +;; `module` is a def +;; `T` is a ref +(scoped_type_identifier + path: (identifier) @local.reference) + +;; struct _ { field: Type } +;; `Type` is a ref + (field_declaration + name: (_) + 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 @@ +[ + (block) + (declaration_list) + (impl_item) + (struct_item) + (enum_item) + (union_item) + (type_item) + (trait_item) + (if_expression + [(let_condition) + (let_chain)]) + ] @cap +{ + (scope (range @cap)) +} + +(function_item + (parameters) @params + (block) @body) +{ + (scope (cover @params @body)) +} + + +(let_declaration + pattern: (identifier) @cap) +{ + (def @cap) +} + + +(binary_expression (identifier) @c) { + (ref @c) +} + 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 @@ +use std::cmp::{Ord, Ordering}; + +use serde::{Deserialize, Serialize}; + +/// A singular position in a text document +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)] +pub struct Point { + /// The byte index + pub byte: usize, + + /// 0-indexed line number + pub line: usize, + + /// Position within the line + pub column: usize, +} + +impl PartialOrd for Point { + fn partial_cmp(&self, other: &Self) -> Option { + Some(self.cmp(other)) + } +} + +impl Ord for Point { + fn cmp(&self, other: &Self) -> Ordering { + self.byte.cmp(&other.byte) + } +} + +impl Point { + pub fn new(byte: usize, line: usize, column: usize) -> Self { + Self { byte, line, column } + } + + pub fn from_byte(byte: usize, line_end_indices: &[u32]) -> Self { + let line = line_end_indices + .iter() + .position(|&line_end_byte| (line_end_byte as usize) > byte) + .unwrap_or(0); + + let column = line + .checked_sub(1) + .and_then(|idx| line_end_indices.get(idx)) + .map(|&prev_line_end| byte.saturating_sub(prev_line_end as usize)) + .unwrap_or(byte); + + Self::new(byte, line, column) + } +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)] +pub struct TextRange { + pub start: Point, + pub end: Point, +} + +impl PartialOrd for TextRange { + fn partial_cmp(&self, other: &Self) -> Option { + Some(self.cmp(other)) + } +} + +impl Ord for TextRange { + fn cmp(&self, other: &Self) -> Ordering { + let compare_start_byte = self.start.byte.cmp(&other.start.byte); + let compare_size = self.size().cmp(&other.size()); + + compare_start_byte.then(compare_size) + } +} + +impl TextRange { + pub fn new(start: Point, end: Point) -> Self { + assert!(start <= end); + Self { start, end } + } + + pub fn contains(&self, other: &TextRange) -> bool { + // (self.start ... [other.start ... other.end] ... self.end) + self.start <= other.start && other.end <= self.end + } + + #[allow(unused)] + pub fn contains_strict(&self, other: TextRange) -> bool { + // (self.start ... (other.start ... other.end) ... self.end) + self.start < other.start && other.end <= self.end + } + + pub fn size(&self) -> usize { + self.end.byte.saturating_sub(self.start.byte) + } + + pub fn from_byte_range(range: std::ops::Range, line_end_indices: &[u32]) -> Self { + let start = Point::from_byte(range.start, line_end_indices); + let end = Point::from_byte(range.end, line_end_indices); + Self::new(start, end) + } +} + +impl From for TextRange { + fn from(r: tree_sitter::Range) -> Self { + Self { + start: Point { + byte: r.start_byte, + line: r.start_point.row, + column: r.start_point.column, + }, + end: Point { + byte: r.end_byte, + line: r.end_point.row, + column: r.end_point.column, + }, + } + } +} + +impl From for std::ops::Range { + fn from(r: TextRange) -> std::ops::Range { + r.start.byte..r.end.byte + } +} -- cgit v1.2.3