What is the best way to correlate old nodes from an edited tree, with nodes from the new tree? #800
Unanswered
Pyromuffin
asked this question in
Q&A
Replies: 2 comments 1 reply
-
@Pyromuffin Have you had any progress on this? |
Beta Was this translation helpful? Give feedback.
1 reply
-
In general node ids are a reliable (but sometimes conservative) way to detect that a sub tree hasn’t changed. If a node is reused, it’s id is stable. Sometimes though, an unchanged node may be recreated with a new id if it is close to an edit. |
Beta Was this translation helpful? Give feedback.
0 replies
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
-
I'm currently working on getting incremental syntax tree analysis working, and I'm wondering what is the best way to correlate nodes from an old edited tree and the new tree resulting from parsing the old tree with edits. It seems like the node ids of the nodes in the new tree are different (though i haven't exhaustively proven this, if some of the unedited subtrees are reused, then this becomes slightly easier),
Basically, I need to find out which scopes have changed, so i can re-analyze them, saving me the work of re-analyzing the entire program. I'm currently using a hashmap with the scope's node.id as the key for each analyzed scope data structure.
Using ts_tree_get_changed_ranges gets me the changed ranges, and using ts_node_named_descendant_for_byte_range gets me the changed node in the new tree, but if it has a different ID than the old node, then I don't have a way of looking up which scope that was that has changed.
I could also use the new start and end byte range to try to match the new node against ts_node_edit'd old nodes, assuming i keep the old node instances around.
the documentation for ts_node_edit() states that if you keep an old node instance around, you can use this function to update the ranges on it. To get the end point it has to go to the subtree, which i think is only valid if you haven't ts_tree_delete'd the tree that the old node came from. For those end points to be valid, ts_edit_tree must be modifying the subtree sizes of the old tree.
If i want to keep reusing this node, do i need to keep that old tree around in perpetuity? In that case, is it better to
option 1 seems like it wouldn't work if the new tree creates new scopes, because those nodes just don't exist anywhere in the old tree. To make that work, each time a tree adds a scope, I would have to keep that tree around forever.
option 2 means i need to correlate all the scope nodes from the old tree with the new tree and replace the old nodes with the new nodes in the hashmap, assuming no subtrees are reused. Having to iterate through the entire tree to find every scope node is not really incremental when a single change is confined to at most one scope.
I'm wondering if you have any suggestion on what is the best way to do this.
Thanks,
Kelly
Beta Was this translation helpful? Give feedback.
All reactions