Hello!
I’m working on a feature that allows user to compare prosemirror documents, and highlight differences between them. I’ve successfully implemented calculating and highlighting the differences, and generating a doc that works pretty much like the versions demo in the yjs repository.
One thing I’ve noticed is that updateYFragment updates the mapping pretty aggressively instead of trying to keep the changes small.
Here is an example:
The first version has the following content:
# Hello
p How is it going?
The second one has the following content:
# Hi
# Hello
p How is it going?
# Ok
An optimal update would keep “Hello” and “How is it going” the same, and insert the other two headings.
The algorithm in updateYFragment
though prioritises updating nodes of the same type, regardless of their content.
let updateLeft = leftY instanceof Y.XmlElement && matchNodeName(leftY, leftP)
let updateRight = rightY instanceof Y.XmlElement && matchNodeName(rightY, rightP)
if (updateLeft && updateRight) {
// decide which which element to update
// ...
} else {
// ...
}
In the case above though, because we added a new heading at the bottom, that won’t match the paragraph of the old version, and so we’ll start updating all the nodes from the top, effectively marking all the doc as changed.
Would it be possible to optimise the algorithm to output a smaller changeset? It reminds me of the stable marriage problem, which would help find the best match between nodes and keep the mapping more “stable”.
Thanks a lot for your work!