Stream: t-compiler/rust-analyzer

Topic: algo::diff


Lukas Wirth (Oct 24 2020 at 20:04, on Zulip):

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.

Lukas Wirth (Oct 24 2020 at 20:06, on Zulip):

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?

matklad (Oct 26 2020 at 10:53, on Zulip):

I wouldn't worry too much about runtime complexity

matklad (Oct 26 2020 at 10:53, on Zulip):

Stuff is mostly small, etc.

matklad (Oct 26 2020 at 10:55, on Zulip):

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.

Lukas Wirth (Oct 26 2020 at 14:07, on Zulip):

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:

Lukas Wirth (Oct 26 2020 at 14:07, on Zulip):

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

Last update: Jul 24 2021 at 21:15UTC