Undo and redo in relationship to CRDTs/multiplayer seems to be an underexplored area with huge challenges. Here's a case where multiplayer undo-redo becomes interesting for visual programming. (This would be visual programming, e.g. via a blocks/node interface, but I'll use JavaScript and React to express the states) Initial state: Empty div.

return (
 <div>
 </div>
);

User A: Inserts a new Dialog component, which uses an "open" state to control its rendering.

const [open, setOpen] = useState(false);
return (
  <div>
    <Dialog open={open} />
  <div>
);

Now, an undo by User A at this point would rightly remove both the

useState

statement and

Dialog

element. But, lets say user B does this before that: User B: Inserts an expression that references and displays the open state:

const [open, setOpen] = useState(false);
return (
  <div>
    <Dialog open={open} />
    <h1>Open: {open}</h1>
  <div>
);

If User A now wants to undo, removing the

open

state would break User B's use of said state. Are there any examples in research or open source of how to gracefully resolve this? I assume that node based programming could run into this dependency challenge, but I'm unaware of any node based tools that support multiplayer with undo/redo. One approach I can think of is to check whether there are dependencies on nodes that would be removed by undo, and simply aborting the undo with an error, but I'm curious if there is a more elegant approach. On a related note, the UI would also have to prevent a traditional delete operation on the

open

state, since this would leave the program in an invalid state.

Particularly if A and B are seeing each other's edits in real time, you could make a case to keep things simple and maintain a single sequence of operations that either side can unwind things from. In your example A would first undo B's operation. Doesn't really use CRDTs' special properties, though.

That's the crux of the problem. People don't expect their undo/redo stack to be affected by other people's actions, but there can be cross-client dependencies between the stacks. We're already doing undo/redo history rewriting, e.g. to incorporate other peoples changes on component properties (I set a rectangle to green, you set it to red, I undo + redo, and we should be back to red to not loose your changes). But this class of problem seems beyond that because the operations in the undo/redo stack don't capture the dependencies to other people's actions. Hmm... 🤔

If you haven’t seen https://en.wikipedia.org/wiki/Operational_transformation yet… 🙂

@Alex Cruise Have read a bit about OT, but that reading quickly guided me towards CRDTs as being a more modern approach that's easier to implement. Problem is, this scenario might not fit with CRDTs. What made you think of OT? Are there examples where you've seen this case solved elegantly?

OT is the only thing I’ve seen that works at all! 😅

Current mental model: Undo redo is time traveling. Undo redo combined with multiplayer and other people's undo redo is the multiverse with conflicting timelines 🥳💥

yeah, I’ve thought (and built) quite a bit about versioning over the years. If you want to get really fine-grained, OT or something equally complex seems like the way to go… But if you don’t mind forcing updates to be more coarse-grained, in which a thing with a long-lived identity is CRUD’d, it doesn’t need to be so hard

Good point on how coarse-grained ops are, because I'm thinking a hybrid approach could be needed. Certain ops, like changing simple component properties, are frequent and need to be optimistically applied. Other things, like inserting new components with dependencies on an import statement and state management could use another approach.

A nice middle ground my team proposed recently, which supports some of the reasons you want branching, is to store every pointer between entities as an (id, version) tuple rather than just an id… If the version field is null, it means we want to point to whichever version is the latest; if it’s not null, it means we want to pin that specific version

For our case, the code being edited is versioned using git and push/pulled via GitHub where approval can happen via PRs and automatic checks. I'm inclined to think that on the design canvas itself (we're a UX design tool), everyone should be seeing the exact same thing in real time while they work.

yeah, if you don’t need to be responsible for merging up in userspace, that simplifies things quite a bit 🙂

The crux of the challenge is to avoid an invalid source file with multiple people doing structural edits and undo + redo 😂

Undo/redo within the user’s work in progress, with respect to an immutable snapshot is fine… Undo/redo across commits is much, much harder. 🙂

My instinct: model "Undo" as a regular operation that can conflict with others. If A creates something, B builds on it (more generally, makes a dependent change), and then A hits Ctrl-Z it should register a conflict in exactly the same way as if A manually deleted the thing. Maybe the only difference would be that the parent state of the undo op is guaranteed to be the result of the op it's undoing, rather than incorporating other changes (this sidesteps the question of whether A's client has seen B's edits). But the basic idea is that you need to handle all those cases anyway, so just use them for Undo. Ed: I guess I should be explicit that in this scenario the undo stack or whatever is probably private state, scoped to the client.

@Andrew F Makes sense. We already use reverse ops for undo, but they don't have the concept of a blocking conflict error. I guess the thing that tripped me up was the search for conflict-free ops, but it seems like if program structures are dependent, yet can be independently removed (or at least attempted to), it's unavoidable to run into blocking conflicts since the program would otherwise end up in an invalid state. In practical terms, these will be edge cases, but they still need predictable behavior. For user A there is still the option to first delete the

open

state expression that user B added, and then remove the Dialog along with the `open`state that no other elements depend on now.

The option for conflicts that I am curious about (but haven't seen any serious work on) is to include conflict markers in the fundamental data model, so they can just stay there until whatever squishy human process is relevant can decide what the right answer is. Optionally, automatically squash nested or adjacent conflict markers (less felicitous if you want to annotate each conflict site or branch, maybe record who made each change). Incidentally, for me the idea of explicit conflict markers is tied to my ancient ideas for an editor for prose/poetry that lets you keep around various possibilities for a line or passage. So I guess if you go that route, and also use it for conflict markers, uh, let me know. :)

Ah, interesting. I think that has real merit in knowledge work where it's a collaboration to sort out a complicated topic. I recall also wanting branching for our pitch deck, where we could try out variations and target different audiences.

@Andrew F Fossil has the distinction between "branch" and "fork". One is for intentionally branching off, the other for managing conflicts without the "stop the world and rebase before you can go on with your work" approach of git: https://www.fossil-scm.org/home/doc/trunk/www/branching.wiki

The rules for what's natural change depending where you are on the scale from Google Docs-style live collaboration to git-style merging commits. If it's a platform where users can see different states locally, then I think User A's local state should roll back to as if they had never created the Dialog, and User B should now be treated as having implicitly created the Dialog the moment they made a dependent element. User A can't really "complain" about their undo being ignored, because they understand that User B is allowed to have the same idea they previously had.

@Chris Knott We have to contend with both real-time and git-style for our case 😂 For real time, the program must always be in a valid state, otherwise we can't compute the visual outcome that needs to be rendered onto the canvas where the designer is doing their work and interacting with the program. Multiple designers viewing the same canvas should be seeing the same thing (converging on it at least, as updates cross the network). Then, once the design work is ready to go into the shared git repo via a push, a traditional conflict can occur, e.g. if developers renamed a component that the designer added new instances of. While we could technically have diverging local states for the canvas for each designer (visual programmer more generally), I suspect that would amount to mind-melting complexity that these "end-user" programmers would rather do without. The way we can go about exploring different design choices (program structures) would be driven by creating separate branches, where each branch checkout has a single shared + converging canvas.