Hi, I’ve been investigating behaviours of collaborative text-editing algorithms for a paper I hope to publish about the correctness properties of many of these algorithms. I’ve been looking at the collaborative editing in ProseMirror and found a strange behaviour, which I would like to ask about. I would like to ask whether this behaviour is already known, or whether it should be considered a bug.
We find that the algorithm can reorder characters under certain scenarios. In the script below, the user intends to insert the character ‘u’ at the start of the document, but if the network messages are sent in a certain way, that character will end up being reordered to the back of the document.
import { Schema, Slice, Fragment } from "prosemirror-model"
import { EditorState } from "prosemirror-state"
import { ReplaceStep } from "prosemirror-transform"
import { collab, receiveTransaction, sendableSteps, getVersion } from "prosemirror-collab"
const schema = new Schema({
nodes: { doc: { content: "paragraph" }, paragraph: { content: "text*" }, text: {} },
})
const doc = schema.node("doc", null, [schema.node("paragraph")])
const text = (c) => c.state.doc.textBetween(1, c.state.doc.content.size - 1)
// The authority: a log of accepted steps and who wrote each one. A submission is
// accepted only if it applies to the version the log is already at.
const log = [], ids = []
const client = (id) => ({ id, state: EditorState.create({ doc, plugins: [collab({ clientID: id })] }) })
const type = (c, pos, ch) => {
const slice = new Slice(Fragment.from(schema.text(ch)), 0, 0)
c.state = c.state.apply(c.state.tr.step(new ReplaceStep(pos + 1, pos + 1, slice)))
}
const erase = (c, pos) =>
(c.state = c.state.apply(c.state.tr.step(new ReplaceStep(pos + 1, pos + 2, Slice.empty))))
const submit = (c) => {
const s = sendableSteps(c.state)
if (s && s.version === log.length) s.steps.forEach((step) => (log.push(step), ids.push(c.id)))
}
const sync = (c) => {
const v = getVersion(c.state)
if (v < log.length)
c.state = c.state.apply(receiveTransaction(c.state, log.slice(v), ids.slice(v)))
}
const A = client(0), B = client(1)
type(B, 0, "y"); submit(B); sync(B) // B types y, the authority accepts it
type(A, 0, "y") // A types y and d. A never submits, so these
type(A, 1, "d") // stay unconfirmed and get rebased below.
sync(A) // A -> "yyd"
type(A, 0, "u") // A -> "uyyd": u goes in front of B's y
erase(B, 0); submit(B) // B deletes that y, the authority accepts it
console.log(text(A)) // "uyyd"
sync(A)
console.log(text(A)) // "ydu" -- the u is now at the end
I also was able to reproduce the same behaviour on the example text editors at ProseMirror collab example . Below is a screen recording of this behaviour, where you can see on the left the character ‘u’ gets reordered. The text editor on the right runs as normal. The text editor on the left was modified so that it does not send messages to the server (by running some javascript below in the console), it can still receive messages though.
//Javascript to reject client submitting messages to the server
;(() => {
const open = XMLHttpRequest.prototype.open
const send = XMLHttpRequest.prototype.send
XMLHttpRequest.prototype.open = function (method, url, ...rest) {
// Only the submission POST. The long-poll GET carries a query string.
this._reject = method === "POST" && /\/events(\?|$)/.test(url)
return open.call(this, method, url, ...rest)
}
XMLHttpRequest.prototype.send = function (body) {
if (!this._reject) return send.call(this, body)
Object.defineProperty(this, "status", { value: 409 })
Object.defineProperty(this, "statusText", { value: "Conflict" })
Object.defineProperty(this, "responseText", { value: "Version not current" })
setTimeout(() => this.dispatchEvent(new Event("load")), 0)
}
window.stopRejecting = () => {
XMLHttpRequest.prototype.open = open
XMLHttpRequest.prototype.send = send
}
console.log("submissions from this tab will now be rejected; call stopRejecting() to undo")
})()
