Nonlinear Undo/Redo

[JordanMartinez]

WIP

Here's the flowchart of the system that is read from left to right. A line of code (or pseudo code) is an orange box. Black arrows point from an orange box to its actual method's implementation. Method implementations, if/else blocks, and for loops are in groups. Finally, red lines indicate the order in which the code is run.

And here's a better version read top to down.

I'm now working on implementing updateChangesPostUndoBubble in DocumentDAG. However, I just realized that I will probably need to change the way the NonlinearUndoManager attempts to merge a previously done change. I'm not yet sure how that will affect everything else.

[JordanMartinez]

I was getting overwhelmed because I wasn't sure how prev() would work given that there are 3 situations that all use that same code. However, once I did it manually on a whiteboard, I figured out where my logic was incorrect. Now that that has been fixed, I believe the underlying code actually works now.

In other words, designing an integration test like this could have bugs in two areas: the code I'm using to test the nonlienar undo/redo system, or the nonlinear undo/redo system itself. Now that I'm confident that nonlinear system works, I only need to finish implementing my tests on the code I'm using to test it before I can write the tests for the nonlinear system itself.

I plan on finishing this before this coming Sunday. I may need to clean up the commit history in the following week, but the code itself should be good by Saturday night.

[JordanMartinez]

This PR is now feature-complete (I think). I just need to finish writing all the test that prove that. It's definitely not supposed to be ThreadSafe

• I'm not sure if my implementation of FixedSizeArrayList is error-free.
• I've run across an issue with DocumentDAGTest.UpdateBubbledUndoDependencyTests. I keep getting an IndexOutOfBoundsException when a dependency does not remove as much text as it inserts. However, once I figure that out, I'll finally be able to start writing the tests for this PR's actual code. Sheez....

[JordanMartinez]

I've concluded that one can bubble a TextChange in two ways: the bubbled portion stores the original undo's "removed" string / redo's "inserted" string while the grounded portion stores an empty string for its counterpart, or vice versa.

[JordanMartinez]

Ok, I've exhaustively tested DocumentDAG. Now it's time to write the actual tests for the nonlinear package.

[JordanMartinez]

Updated logic flowchart:

Logic flowchart (top down):

[JordanMartinez]

:-/ I was hoping to finish this PR's actual tests by tonight, but it looks like I ran out of time due to working on other RTFX stuff. I'll try to finish it by this next week, but no guarantees because school is starting up again.

[JordanMartinez]

I was looking at the tests last night and came across an issue with my implementation of QueuePosition. I decided a position should be valid in two cases. The first one isn't the problem: the queue's list of changes is empty and the forgottenCount is the same. The second one is: the queue contains a change in its list of changes (because the change could be repositioned in the queue's history). However, whenever a queue pushes a new change, whether an undo/change/redo, it calls updateUndo/Redo. Since the original change is sometimes replaced with an updated version, changes.contains(storedChange) is sometimes true (true if no update was needed; false if it was needed) and thus isn't a good way to indicate its validity.

I think I'll have to wrap the change in another object that can be used to track whether the change stored there is the same object (original or updated) or if it's a new object entirely. Thus, it would be List<Version<C>> changes where Version would be:

class Version<C> {
    private C change;
    public C getChange() { return change; }
    public void setChange(C c) { change = c; }
}

Then, when a change is merely updated, I can use identity equals to determine whether the queue position is still valid. However, due to the possibility of a change being bubbled, the question becomes, "Do I replace the old change with the grounded portion and create a second Version object for the bubbly portion? Or do I create 2 Version objects? I'm leaning towards the latter option.

I have yet to write tests for the nonlinear undo manager

[JordanMartinez]

I updated my code to use the Version idea (though I think Wrapper or Container is a better way to describe the class' functionality). The UnlimitedNonlinearChangeQueue's QueuePosition tests still failed, which baffled me until I figured out the real issue, something that I forgot still needed to be done.

When the UndoManager attempts to merge a change, it will call queue.prev() and either pushes a merged change or, when no merge is possible, both as new changes. I realized that the Nonlinear version of this approach needs to handle that situation differently than the Linear version. There are 4 situations for which to account:

1. When prev change is a regular change that can be merged with the pushed change
2. When prev change is a bubbled change that can be merged with the pushed change
3. When prev change is a regular change that cannot be merged with the pushed change
4. When prev change is a bubbled change that cannot be merged with the pushed change

I haven't yet thought through how that should be handled.

[JordanMartinez]

The issue with using Version is that it is now mutable because I have to update its change object to insure that it can identity equals one stored in a QueuePosition. I understood that issue, but it wasn't my goal then to correct that. After more thought, I decided this should be further abstracted out of that object. Rather than using the Version object itself to check for identity equals, I should just create a blank Object that is stored in a Version object. This object could then be used for identity equals without Version needing to be mutable.

As for other things:

• calling undo twice consecutively screws up something. I haven't debugged it further, but that's the issue stopping all 3 QueuePosition tests for the unlimited variant
• I still need to update FixedSizeArrayList to use a "revolving" approach like you use in the Linear version, so that every time a new change is added, I'm not moving all changes to the left by one index but merely wrapping around back to the 0th index of the array.

[JordanMartinez]

I may have an off-by-one issue in FixedSizeRevolvingArrayList. However, that's my first run through in making it work.

[JordanMartinez]

I tested FSRAL last night with tests. It failed due to System.arrayCopy throwing an ArrayIndexOutOfBoundsException and I know why. However, I'm not sure if I'll get to fix it this week, though, due to time constraints.

[JordanMartinez]

K, FixedSizeList is finished, though I still wonder if my code will work for a fixed size list of two changes (the array copy might throw an AIOOBE, so I'll test that theory out later). Not knowing much about memory usage, I also wonder if such an implementation should use an array or just two changes called first and second.

Update: a size of 2 still passes the tests.

[JordanMartinez]

Ok, I got the Unlimited variant's queue position tests to pass. I haven't actually thought about what additional tests it might need due to being nonlinear. The FixedSize variant's tests will need to account for the bubble strategies that are used.

[JordanMartinez]

Ok. The fixed size NCQ tests pass now.

[JordanMartinez]

... but they don't account for different bubble strategies

[JordanMartinez]

I've cleaned up the code into a shorter commit history.

[JordanMartinez]

The most recent NonlinearUndoManager.LinearTests test that uses the unlimited variant produced a bug that I fixed in this most recent commit. However, I'm a bit confused. The unlimited and fixed size variants use the same code base, but the issue arises only with the unlimited variant. I'm still going to change the fixed size variant to do the same thing the unlimited one does just in case. However, I'm making a note of this now so that I don't forget later. Though this bug might be caused by something else, it doesn't seem like it. The issue was caused by the original undo's starting position not getting bumped to the left/right due to another pushed undo/redo. That didn't occur, presumably, because it wasn't one of the changes included in the undos being updated. Most likely, the javadoc I wrote there is outdated from when I originally wrote it last summer since it probably understood things in a different way than I do now.

[JordanMartinez]

At this point, I only need to write the NonlinearUndoManagerTest.NonlinearTests and then write tests that account for the FixedSize variant's bubble forget strategies to insure the QueuePosition works as expected.

[JordanMartinez]

I forgot to account for the situation when redoing all changes in a queue. Now the fixed size and unlimited variants tests don't pass because the changes' starting positions aren't being bumped, so the text appears to be reversed because they all insert text at 0 originally.

[JordanMartinez]

After investigating this more, the issue is not in the undo system's code but rather in the DocumentDAG#updateRedo method:

@Override
public TextChange updateRedo(TextChange outdatedRedo, TextChange pushedChange) {
    if (pushedChange.removedEndPosition() <= outdatedRedo.getStart()) {
        return outdatedRedo.bumpPosition(pushedChange.getDifference());
    } else {
        // either pushedChange occurs to the right of outdatedUndo
        // or it actually modifies outdatedRedo, in which case it might be bubbly
        return outdatedRedo;
    }
}

The reversal of the text occurs because I'm using insertion() to push new changes, which calls replace(0, removedText.length(), insertedText). Thus, undoing any of these changes always deletes text, so any redos start positions are eventually set to 0. When I redo the first change (whose start = 0 and removed length = 0, thus removedEndPosition = 0, which equals all the redos' start position), it bumps all of redos' start positions by the redone change's difference. Since I'm always inserting text, this bump amount is always positive, causing all redos to update their start positions to be immediately after the redone change. Each redone change causes the remaining ones to bump their start to be immediately after that redone change. Thus, the inserted text comes after the last insertion, not before as it should and through this chain, the text is reversed.

The obvious workaround is to add another if statement before that code runs:

if (pushedChange.removedEndPosition == 0 && outdatedRedo.getStart() == 0) {
    return outdatedReo;
} else if /* the rest of the method */

However, will this always be the desired result? If not, it disproves an initial belief I had, that a NonlinearUndoManager could also be used as a linear one.

[JordanMartinez]

One idea I thought of today that might be able to get around this issue is if I separate the start position in TextChange into two parts: the original starting position, and the adjustable bump position. Thus, whenever a TextChange is bumped, bumpAmount is updated and the original start position is left untouched. When the change's getStartPosition() is called, it returns the sum of the original start position and the bumpAmount. In this way, I could distinguish between a change that was originally inserted at 0 and later adjusted to refer to a non-zero position in the document due to later insertions in front of it and a change that was added at a non-zero position that was adjusted to point to 0. I'm not sure whether this would be able to fix the issue I discovered above as I haven't thought through all of its implications yet.

[JordanMartinez]

Just FYI. I more or less stopped working on this as soon as I realized it wouldn't be necessary for a 0.7 stable release of RTFX. I still need it for my own code (so I'll get back to it later on), but I'd rather get a stable RTFX version first as that's more important in my code that undo/redo capabilities.

[TomasMikula]

Yeah. Didn't I warn you early on that this would be a gargantuan task? :D

Oh and by the way, "non-linear" isn't very descriptive: it says what it isn't, not what it is. If I told you I had a non-dog pet, you wouldn't have much of an idea of what pet I had.

[JordanMartinez]

Yeah. Didn't I warn you early on that this would be a gargantuan task? :D

You did, but I figured this would be my way of proving (more to myself than to you) that I could actually program good original code (since much of what I have done on your projects have been bug fixes or other things that use your code as a model to follow and only change in minor non-original/non-creative ways). Well, that and my code needs a non-linear undo/redo system (you'd think I'd learn not to take on near-impossible projects without any prior experience in some field, but....... I did and still do :laughing: )

Besides, my belief (when isn't it not the case on this PR, lol?) is that this PR is almost done. That's also partly why I stopped working on it as it should work after I implement that bumpAmount idea (so I pray!).

Oh and by the way, "non-linear" isn't very descriptive: it says what it isn't, not what it is. If I told you I had a non-dog pet, you wouldn't have much of an idea of what pet I had.

If you said that, I would assume you had a cat, haha. Good point though. I've realized in this PR that non-linear could mean a different route that reaches the current state in the model (how I'm currently interpreting the term), or an unexpected result entirely (as discovered in the reverse issue I hope to fix with that bumpAmount idea).

[TomasMikula]

Way to learn 👍

I don't actually have a pet, but could be a hamster :P

[JordanMartinez]

One other thought I had. Right now, prev is used in two cases to get a change: 1) to undo that change or 2) to try to merge that change with a recently-pushed change. Since there are not two separate methods for this in ChangeQueue, and since I was trying to maintain source compatibility in ChangeQueue, a NonlinearChangeQueue's prev sometimes returns a bubbled part of the next undo (if it is bubbly) for a merge even if the two changes cannot be merged or it results in an identity change, an issue raised in #14.

Ideally, there should be 2 methods for each case, so that NonlinearChangeQueue can still extend ChangeQueue and LinearChangeQueue only needs to override the method with the regular push. The first (perhaps prevForUndo) will bubble the undo because it is going to be undone. The latter (perhaps prevForMerge) will do the work necessary to create a bubble version of the next undo, but it will not update the graph. In other words, if the code attempts to merge a bubbly change and a new pushed change, this is how the those possibilities should be handled:

1. Unsuccessful Merge: do not update the graph and just push the new change
2. Successful Merge results in non-identity change: update the graph and queue and overwrite the last change (if the undo is not the next undo (indexOf(change) != currentPosition-1), the change will be moved to that position and then split into two parts where the grounded portion will be the same index as the original and the bubbled will be one index greater. In this case, the last change is the bubbled part of the original change).
3. Successful Merge results in identity change: do the same as option 1.

[JordanMartinez]

I'm closing this since I'm no longer pursuing Java-related projects.