[WIP] Rebase PATCH against MOVE

Inviz commented 7 years ago

This is a work in progress, not ready for merge. I'm opening up this PR early to get possible feedback early, and to track the progress to avoid duplicated work during refactoring.

[X] Rebase DEL-like patches against MOVE
[x] Rebase multiple-hunk splices against MOVE
[x] Rebase INS/replace against MOVE
[ ] Rebase MOVE against other types
[ ] Generate MOVE operations in jot.diff()

I think the base algorithm is ready. I followed TDD approach, but I think we need tests to be more exhaustive, so I'll double that amount at least.

Hopefully the code in itself makes the basic idea visible (tried to be rather clear than smart). I split SPLICE ops in two wherever they intersect with MOVE range. I considered LTR/RTL MOVE commands, but there is still a bunch of things that need to be looked into, mostly related to inserting text which I did not account for at all yet. I tried to make the code as simple as possible, but I do however rely on simplify() call to combine SPLICE operations again.

Inviz commented 7 years ago

I think I may slowly get to the point where I don't think all hope is lost. I reworked the code quite a bit to keep mutations contained and also made sure standard hunk-iteration logic is preserved to get to text insertion soon.

Still have (unpushed) failing tests, but it does feel like I'll get it working eventually.

Inviz commented 7 years ago

Finally, I made it to text insertion. I refactored things quite a bit as my understanding of the problem and solution grew. I think it became quite neat.

I do not handle a case of MOVE where new_pos is within removed hunk. I think this is the only "true" conflict that should return null without conflictless mode. I'll get to it.

I still have a big bunch of specs unpushed, because I need to convert them from jasmine to tap every time. I'll do it in a bigger bulk, as I want to be sure the code is very well tested to safely hand off

Inviz commented 7 years ago

The algorithm turned out to be pretty difficult to figure out, but it is actually pretty simple (but with many special cases). In the middle of working on it, I decided to finish it as a standalone library with permissive license (https://github.com/Inviz/O/blob/master/src/move.js).

I took a lot of inspiration from jot, but I implemented my own algorithms, and choose slightly different data structures without AST. Thank you!

JoshData / jot

[WIP] Rebase PATCH against MOVE #9