Intervals don't seem to go back to their previous positions after an undo operation

[amruth-ms]

If an interval's start and end offset is @15 in the document and if user deletes the text from @[10 - 20] and does an undo immediately. And now if the interval's start and end offset is queried, it will be @20 instead of @15.

The ask from this bug is to make interval positions undo friendly. The intervals should be back at their previous position instead of being at the end of inserted text after an undo operation. In the above example, after the undo operation the interval's start and end offset should be @15 instead of @20.

The following are the API being used to created intervals, delete text and query the interval position

APIs to create intervals

const sharedIntervalCollection = sharedString.getIntervalCollection(intervalType); const sharedInterval = sharedIntervalCollection.add(startOffset, endOffset, IntervalType.SlideOnRemove, properties);

APIs to delete text

sharedString.removeText(startOffset, LengthOfDeletedText);

APIs to get interval position

const sharedIntervalCollection = sharedString.getIntervalCollection(intervalType); const sharedInterval = sharedIntervalCollection.getIntervalById(intervalId); To get start position: sharedInterval.start.toPosition() To get end position: sharedInterval.end.toPosition()

[curtisman]

@Abe27342 FYI.

[Abe27342]

Hi @amruth-ms --thanks for the report. I looked into this just now as well as the other merge-tree undo/redo situation you wondered might be related.

The behavior you describe is as designed: sequence and merge-tree don't have built-in notions of undo or redo, so there's no way to reasonably expect them to revert reference slides (even via intervals) when a segment delete gets reverted.

However, this is certainly a scenario we want to support! The exposed APIs on merge-tree and sequence should make it possible to implement the behavior you want in your undo-redo logic. I'm planning on updating the example undo-redo handler for sequence to do this (sneak preview here). The gist of it is that on segment remove, you can inspect any removed segments for refs you might want to restore:

                    if (event.deltaOperation === MergeTreeDeltaType.REMOVE) {
                        current.refsToRestore = Array.from(range.segment.localRefs ?? []).map((ref) => ({ ref, offset: ref.getOffset() }));
                    }

Then, in your revert logic, you can restore them in-place by sliding like so:

                            if (insertSegment.localRefs === undefined && tracked.refsToRestore!.length > 0) {
                                insertSegment.localRefs = new LocalReferenceCollection(insertSegment);
                            }
                            for (const { ref, offset } of tracked.refsToRestore!) {
                                ref.callbacks?.beforeSlide?.();
                                insertSegment.localRefs?.addLocalRef(ref, offset);
                                ref.callbacks?.afterSlide?.();
                            }

There are still some things I need to work out in that example (you can see the sneak preview has a few TODOs), but the above code should be pretty close to what you want. Hopefully that's enough to unblock you while I sort out the details in the example implementation.

[amruth-ms]

Hi @Abe27342 . Thank you very much for your response :) . I will try the approach you suggested.

[amruth-ms]

Hi @Abe27342 , I tried the solution to make intervals undo friendly. I am putting a couple of questions I had when I tried the solution below. Could you please let me know your thoughts on them?

1. We are currently using Fluid version 1.2.0. In that version I don't see addLocalRef method having two parameters. It just has one parameter with type ReferencePosition. So, in our revert code, I could not do insertSegment.localRefs?.addLocalRef(ref, offset). I wanted to check if addLocalRef method has any recent changes and will be released in a new Fluid version and accepts two parameters instead of just one?

2. I was wondering if the solution to make intervals undo friendly will make intervals positions to be in sync across different clients? For example, there are two clients(client1 and client2). client1 inserts an interval with same start and end position @15. Now client1 deletes text in range @[10 - 20] and immediately does an undo. Client1 will be able to restore the interval start and end positions to be @15 as it stores the references when deleting the text and will restore in its revert logic when an undo operation is done. But client2 will see the client1's undo operation just as a normal insertion of text and it will not have a chance to restore interval positions properly. So eventually I am thinking client1 will have its interval start and end positions @15 but client2 will have its interval start and end position @20. Just wanted to check if my understanding is right in this scenario.

[Abe27342]

@amruth-ms Eurgh, you're totally right about the client sync issue. Can't believe I missed that. We'll still need you to do work in the undo-redo handler, but it should be with higher-level APIs. The most obvious thing to do would be to expose a function intervalFromEndpoint(endpoint: LocalReferencePosition): SequenceInterval function on IntervalCollection, which you could then use like so:

for (const { ref, offset } of tracked.refsToRestore) {
    const pos = sharedString.getPosition(insertSegment) + offset; // probably want more validation here
    const [label] = refGetRangeLabels(ref);
    // Both of those lines may want some more validation; getPosition() can return -1 if the segment is detached, and
    // refGetRangeLabels should be an array of length 1 (but may be undefined, so should check that first and throw more clear error)
    const collection = sharedString.getIntervalCollection(label);
    const interval = collection.intervalFromEndpoint(ref);
    collection.change(
        interval.getIntervalId(),
        ref === interval.start ? pos : undefined,
        ref === interval.end ? pos : undefined
    );
}

Might be worth only issuing one change op for both endpoints if both endpoints are getting moved back as part of a single undo. But that's the gist of how it would work with that API. There are also some details to work out with how IntervalCollection is currently factored, since it's generic right now. Maybe just a free function that gives the interval id from the endpoint would be better, that would avoid a step and should still work fine.

I'm curious if @anthony-murphy has any thoughts on this as he's thought more about undo-redo than I have.

[Abe27342]

I remembered that our original plan here was to use the changeInterval event on IntervalCollection to power this. In order for that to work, one needs the changes currently checked into next. But I don't think it makes sense to add the alternative query for doing this that I described above, if it's going to be immediately deprecated (it's not too much code, but it does add an extra prop to each local reference that's part of an interval collection)

I'm still going to confirm that the changes in next make this reasonable and update the framework undo-redo handler demonstrating how one can do that.

[Abe27342]

The changes in next do help, but they're not enough and IMO provide a worse experience than my previous proposal. The problem is that by the time the interval slides, the local op that caused such a slide has already been acked. This means there's basically no easy way to infer the correct place to restore the intervals to (in contrast to the above approach, where we know the exact segoff to undo the change). With a complex state machine and exposing additional query APIs on client/sequence, it's technically possible, but seems a lot easier to just expose the query API. I'm going to proceed forward with that, and I'll link a "close but not quite" commit demonstrating the issue with doing it based on changes.

[amruth-ms]

Hi @Abe27342. Thank you very much for your detailed explanation and my apologies for the delayed response. I think the I get the gist behind the first approach (i.e, using the intervalFromEndpoint(endpoint: LocalReferencePosition): SequenceInterval query API and restore the interval interval positions after undoing a text deletion). But it looks like there is one other solution by using changeInterval. I am not sure if I fully understand this approach and the following statement

I remembered that our original plan here was to use the changeInterval event on IntervalCollection to power this. In order for that to work, one needs the changes currently checked into next.

I am thinking, when a deletion of text happens and if there were intervals inside the text before getting deleted, the solution is to first call changeInterval API to change interval positions and then delete the text. So that when undo operation is done, first the deleted text will be put back and then we undo the change the happened because of the changeInterval API. For example, if an interval's start and end positions were @15 and if a user deletes the text from @[10,20]. We first call changeInterval API, to change the intervals start and end positions to be @10. And now we delete the text from @[10,20]. Now, if user does an undo operation, we first put back the deleted text from @[10,20] and undo the change that caused by changeInterval API call during the deletion (i.e, putting back the interval's start and end positions @15 now). I have a feeling that I totally mis-understood the solution. Very sorry if I did. Please let me know if I don't have the correct understanding.

And we are planning to add undo support for intervals only in our code after we have access to the changes present in this PR(https://github.com/microsoft/FluidFramework/pull/10966). We will need the changes in this PR to implement undo/redo mechanism for intervals, as the APIs in this PR provide us the previous information of intervals(like previous properties when interval properties are getting changed or previous position when interval position is getting changed). We will likely be adding the support(if needed) for making intervals go back to their previous positions after a deletion of text operation is undone, after having access to the changes present in https://github.com/microsoft/FluidFramework/pull/10966.

[Abe27342]

I am thinking, when a deletion of text happens and if there were intervals inside the text before getting deleted, the solution is to first call changeInterval API to change interval positions and then delete the text. So that when undo operation is done, first the deleted text will be put back and then we undo the change the happened because of the changeInterval API. For example, if an interval's start and end positions were @15 and if a user deletes the text from @[10,20]. We first call changeInterval API, to change the intervals start and end positions to be @10. And now we delete the text from @[10,20]. Now, if user does an undo operation, we first put back the deleted text from @[10,20] and undo the change that caused by changeInterval API call during the deletion (i.e, putting back the interval's start and end positions @15 now). I have a feeling that I totally mis-understood the solution. Very sorry if I did. Please let me know if I don't have the correct understanding.

This generally seems like it could work, though it would add overhead to what's sent over the wire (each segment removal potentially necessitates first changing a number of intervals). If you expect the number of intervals to generally be small, that's a reasonable tradeoff. Might also lead to poorer-quality merges if someone else is concurrently trying to change the endpoint. But that's probably not a big deal.

If you decide to do this, do note that in most cases intervals won't slide anymore--only if the op isn't meant to go on the undo-redo stack (so you don't actually issue a changeInterval) or if there's some concurrency such as someone adding an interval around where you're concurrently deleting. That's totally fine, just wanted to point it out.

[amruth-ms]

This generally seems like it could work, though it would add overhead to what's sent over the wire (each segment removal potentially necessitates first changing a number of intervals).

Agree that the approach I mentioned adds overhead and we will probably not proceed with this solution. We will most likely use the query API (like intervalFromEndpoint(endpoint: LocalReferencePosition): SequenceInterval) solution and restore interval positions during an undo operation. We will likely make relevant changes once we have access to the changes present in https://github.com/microsoft/FluidFramework/pull/10966 and the query API.

[Abe27342]

@amruth-ms The ability to get an interval from its endpoint is checked in, so once released you should be unblocked on this issue. Since one undo-redo approach was nearly working and the issues with it seem solvable from within the undo-redo handler, I'm going to table the work to implement a proper undo-redo handle until a bit later this sprint (depending how much I get randomized, may leak into next).

In the meantime I'll leave this issue open. Let me know if you run into issues that it doesn't seem like you have the APIs to resolve.

[amruth-ms]

@Abe27342 Sounds great. Thank you so much for the quick addition of interval endpoint API :)

[microsoft-github-policy-service[bot]]

This PR has been automatically marked as stale because it has had no activity for 60 days. It will be closed if no further activity occurs within 8 days of this comment. Thank you for your contributions to Fluid Framework!

[Abe27342]

bad bot. We recently funded work on this issue. re-opening. @scarlettjlee @jzaffiro could you close once current undo-redo work is resolved?

[Abe27342]

Some more context on this:

Our stance at the time this issue was opened was that we should expect customers to implement that behavior in their stack. When the issue was originally opened, even that was infeasible since there was a lot of nonsense/not enough information in IntervalCollection's change events and a lack of an ability to go from interval endpoint to the interval.

Since then, our stance is relaxed and we're working on default support through a similar revertibles notion to what merge-tree has for text edits. It will still require hooking up the revertibles into some undo/redo management system, but the burden should be roughly what's expected from any other DDS. Scarlett and Jillian are working on this right now, and AB#3578 tracks that work internally.

[scarlettjlee]

Revertibles have now been implemented that can be created from events on intervals + string.