How can we guarantee relationships are preserved between types with regard to the UndoManager?

Show
1

I’m rolling up a few thoughts into this post but please stick with me on it, I’ll try to keep it as concise as possible. Consider the following example where I have two types: a dictionary of items (arbitrary); and an array representing an associated ordering of said items.

import * as Y from "yjs"

const doc = new Y.Doc()
const root = doc.getMap("root")

const history = new Y.UndoManager(root, {
    trackedOrigins: new Set([doc.clientID])
})

const itemIndex = root.set("index", new Y.Map())
const itemOrder = root.set("order", new Y.Array())

// initial state
Y.transact(doc, () => {
    itemIndex.set("foo", 1)
    itemIndex.set("bar", 2)
    itemOrder.insert(0, ["bar", "foo"])
})


// local client updates the value of an item
history.stopCapturing()
Y.transact(doc, () => {
    itemIndex.set("bar", 3)
}, doc.clientID)

// a remote client deletes the same item
Y.transact(doc, () => {
    itemIndex.delete("bar")
    itemOrder.forEach((item, idx) => {
        if(item === "bar") {
            itemOrder.delete(idx)
        }
    })
})

// local client undoes the last change
history.undo()

In this scenario I am left with the following effective state:

{
    index: { 
        foo: 1, 
        bar: 2
    }, 
    order: ["foo"]
}

Now I understand that this is expected behaviour however I am still looking for a means of expressing some higher-level constraints for entities in my schema. In this case I would like to provide some guarantees that no item can exist in index that does not exist in order (and vice-versa).

There are a multitude of scenarios - including when merging conflicting changes - where such relationships can also be impacted by partially applied changes but I’ve chosen the UndoManager for this example since it seems to be the component where I have the least control.

I’ve explored several strategies that appear not to be viable (specific questions in bold):

  • It is not possible to introspect state on the Y.Transaction and abort the transaction if it does not meet some validation criteria. I also see that this limitation is noted in the documentation.
    • Q. Is supporting some kind of transaction validation on the roadmap?
  • It does not appear possible or is at least difficult or otherwise impractical to introspect a StackItem prior to calling undo or redo as the change set is not represented in a format that can be reasoned about easily.
    • Q. Most of the API here look internal-only - is there a means of exposing the changes in a “patch” format?

Crudely / naively I’ve also tried cloning the document and applying a foreign history item in order to try and produce some state that I can reason about without modifying the main document, but all the internal references seem to change so this ultimately doesn’t work.

const clone = new Y.Doc();
Y.applyUpdate(clone, Y.encodeStateAsUpdate(doc));
const historyClone = new Y.UndoManager(clone.getMap("root"), {
    trackedOrigins: new Set([history])
})
historyClone.undoStack.push(history.undoStack.at(-1))
historyClone.undo()

Q. Is there a way to accurately clone a document preserving the history stack or is this a terrible idea?

Some variation of the above would be my ideal outcome - it feels safer to be able to pre-screen the compatibility of updates before they are applied, else we leave the potential for the corruption of meaningful relationships. This is problematic because we generally are delayed in realising that there is an issue and issues tends to have cascading side-effects that are difficult to troubleshoot.

In order to work around this issue for the moment I’ve been attempting to catch erroneous state configurations as part of some cleanup routines however this in itself presents another concern. For example given something like:

const cleanup = (doc: Y.Doc) => {
    const order = new Set(itemOrder.toArray())
    itemIndex.forEach((_, key) => {
        if(!order.has(key)) {
            itemIndex.delete(key)
        }
    })
}

history.on("stack-item-popped", () => {
    cleanup(doc)
})

It looks like this event is fired after the Y.transact call in the UndoManager - i.e. there isn’t a guarantee that both the change and the cleanup would be syndicated to other clients in the same sync event. It would be problematic in my case - even if momentarily - for other clients to receive partially applied / invalid state.

Q. Have I missed something here, is this a guarantee that is actually provided by the API?

I’ve subsequently then tried calling the following in order to provide my own guarantee:

Y.transact(doc, () => {
    history.undo()
    cleanup(doc)
})

This “sort of” works, except the for the fact that it changes the order of events - notably the change to afterTransaction prevents the StackItem from being added to the redo stack. :man_facepalming:

So… I now have this monstrosity where I’m trying to wrestle control of the transaction from the UndoManager and monkey patch the undoing and redoing flags in order to preserve the expected behaviour.

export class MyUndoManager extends Y.UndoManager {
  private undoingAuthority = false;
  private redoingAuthority = false;

  lastAction!: "undo" | "redo";
  lastStackItem!:
    | ReturnType<Y.UndoManager["undo"]>
    | ReturnType<Y.UndoManager["redo"]>;

  constructor(...args: ConstructorParameters<typeof Y.UndoManager>) {
    super(...args);

    Object.defineProperty(this, "undoing", {
      set: () => {
        /* noop */
      },
      get: () => this.undoingAuthority,
    });

    Object.defineProperty(this, "redoing", {
      set: () => {
        /* noop */
      },
      get: () => this.redoingAuthority,
    });
  }

  undo() {
    if (!this.undoStack.length) {
      // don't create a transaction!
      return null;
    }

    this.lastAction = "undo";
    this.lastStackItem = this.undoStack.at(-1) ?? null;
    this.undoingAuthority = true;

    let stackItem: ReturnType<Y.UndoManager["undo"]> = null;

    try {
      Y.transact(
        this.doc,
        (tx) => {
          stackItem = super.undo();
          cleanup(this.doc as Y.Doc, tx);
        },
        this
      );
    } finally {
      this.undoingAuthority = false;
    }

    return stackItem;
  }

  redo() {
    if (!this.redoStack.length) {
      // don't create a transaction!
      return null;
    }

    this.lastAction = "redo";
    this.lastStackItem = this.redoStack.at(-1) ?? null;
    this.redoingAuthority = true;

    let stackItem: ReturnType<Y.UndoManager["redo"]> = null;

    try {
      Y.transact(
        this.doc,
        (tx) => {
          stackItem = super.redo();
          cleanup(this.doc as Y.Doc, tx);
        },
        this
      );
    } finally {
      this.redoingAuthority = false;
    }

    return stackItem;
  }
}

Q. Is this a reasonable direction to take?

In summary I’m essentially chasing something akin to ACID-like guarantees over transactions.

I’m conscious that the described state structure may not be ideal and maybe relying on the completeness of state isn’t the best mental model either - but for context we are applying yjs retrospectively to an existing project and scaling development of a large state tree with many engineers is proving challenging.

Q. What is the pragmatic middle ground here?