I just realized a big mistake I made when rewriting the algo::diff function. The generated diff is now all over the place when something has been inserted or deleted due to those changes offsetting the nodes. As in an insert in a node causes all nodes beyond that point(including the inserted node) to be marked as replacements so diffing is anything but minimal now. I just realized that while trying to integrate my recent changes into the auto import cursor fix branch because the cursor now jumps even further instead of not jumping at all.
One solution I could think of is to check if the current node we are looking at is at the same position in the other tree or a next_sibling of the node at that position which would allow to do proper judgement about whether this was an insertion or not but this feels like causing runtime complexity to skyrocket I think?
I wouldn't worry too much about runtime complexity
Stuff is mostly small, etc.
I would worry a lot about implementation complexity -- diff-ing is not the prettiest code there is, and it's already a lot of it. It's not inconceivable that there's some order-of-magnitude better way to handle this :-) The current diffing was explicitly written as the simplest thing I can come up with in n minutes, I wish we used something more principled.
I see, I did look around a bit for proper node/ast based diff algorithms but I only found a few things that were too complex for me atm :sweat_smile:
I would make another PR that does the look-ahead in algo::diff to properly find insertions if that is alright then because that is the only blocker(after merging the SyntaxRewriter changes) left for the auto-import cursor jumping