search

rust-analyzer / rowan

Apache License 2.0
689 stars 57 forks source link

[Feature Request] Unique ids per node instance #75

Closed Kixiron closed 3 years ago

Kixiron commented 3 years ago

Having a way to uniquely identify nodes on a per-occurrence basis would really help with implementing incremental parsing and compilation

CAD97 commented 3 years ago

What exactly is the desired API here? IIRC we already have == which has a fast path for for identity equivalence, and we could add a ptr_eq (to green nodes) which just checks identity equivalence.

Nodes are identity equal if they have the same content and went through the same builder cache.

(Disclaimer: at this point I'm having trouble remembering what's already done by Rowan's green trees and what's only done by Sorbus's green trees.)

Kixiron commented 3 years ago

Well, this is per-occurrence of each node, not whether the nodes are the same. For example, I wouldn't want 1 and 1 to be equal in this scenario, since each of the 1s came from a different place, even though the ast backing them is identical

CAD97 commented 3 years ago

SyntaxNodes also have an Eq impl that checks their text span as well as the AST equivalence.

Being able to tell apart just GreenNode based on where they are in the tree is an explicit nongoal, as we want to (and do) do deduplication of small AST fragments.

r-a uses (TextRange, Kind) as a lightweight "SyntaxPtr" type that identifies a node in the tree without all of the thread-local parent pointers of SyntaxNode. Perhaps that's what you're looking for? There is intent to add this type to Rowan once we can make it perform better than naïvely. (Currently, for tree depth and width, SyntaxPtr resolution is O(d • w) where it could be O(d • log w), with a bigger ptr or a tree that stores cumulative offsets.)

Kixiron commented 3 years ago

The SyntaxPtr method should work, thank you!