Considering OT’s transform algorithm for an Insert operation and a Delete operation executed at the same time, on two different clients. Insert.pos is in the range [Delete.pos, Delete.pos + Delete.count - 1].
To keep both the intentions executed, we can turn the Delete operation into at most two delete operations, to keep both the insert intention and the delete intention executed. More specifically, [Delete.pos, Insert.pos - 1] and [Insert.pos + Insert.content.length, Delete.pos + Delete.count + Insert.content.length - 1].
However, it will turns an operation into two operations. Could it cause time complexity problem?
I later checked ot.js but found their behaviours different.
In Operational-Transformation/ot.js/lib/simple-text-operation.js, it just ignored the Insert operation.
if (a instanceof Insert && b instanceof Delete) {
if (a.position <= b.position) {
return [a, new Delete(b.count, b.position + a.str.length)];
}
if (a.position >= b.position + b.count) {
return [new Insert(a.str, a.position - b.count), b];
}
// Here, we have to delete the inserted string of operation a.
// That doesn't preserve the intention of operation a, but it's the only
// thing we can do to get a valid transform function.
return [noop, new Delete(b.count + a.str.length, b.position)];
}
But in https://operational-transformation.github.io/ , the OT take the choice I mentioned in the top of passage (splitting the Delete operation into <=2 operations).
(You can try to remove orem ips in Alice and insert hi at pos = 5 in Bob to see effect.)
I am confused that two behaviors are different, and according to some blogs I see on the Internet, transform should be return only two operations, not two operation arrays (which means splitting is not allowed).