Hi Eric,
I'll break up my reply into the following three independent points,
since there's more than one issue being discussed here in this thread.
1. It is true that the IP2 property you've mentioned does not hold.
The operation inversion code was written to be used for undo and redo,
and our undo/redo algorithms do not require the IP2 property.
2. With regard to composition behaviour, consider the two following
operations.
x = {
retain(1)
deleteCharacters("a")
retain(1)
}
y = {
retain(1)
characters("a")
retain(1)
}
Then:
x . y = {
retain(2)
}
y . x = {
retain(1)
deleteCharacters("a")
characters("a")
retain(1)
}
When you delete a character "a" from a document, you are deleting the
same character that was inserted into the document by some past
operation.
However, when you insert the character "a" into a document, that
character "a" is considered distinct from any other characters "a" in
the document, and also considered distinct from any characters "a"
that might have existed in the document in the past. So when you
delete a character "a" and then insert a character "a" at the same
location, you are not reinserting the same character "a" that you
previously deleted, but rather you are inserting a completely new
character "a" (and the old character "a" that you just deleted remains
deleted).
This explains why "y . x" has both a deletion and an insertion.
Furthermore, there are a few reasons why it would be undesirable to
define "y . x" to be "retain(2)". I've listed three below.
A. Better preservation of the intention of the operation (especially
since transformations are designed in such a way that they try to
preserve as well as possible the intention that the operation
expresses). If one operation deletes a character and the next
operation inserts a character, you want their composition to express
the intention that a character be deleted and a character be
inserted. This should be true even if the inserted character (either
by coincidence or by design) happens to have the same value and
location as the old deleted character.
B. Correct display of differences between document versions. Quite
often, you want to show not just document state, but also the changes
that occurred between two historical versions of the document. For
example, in playback mode, you might want to show what has changed
from one playback frame to the next. Or, when revisiting a wave, it's
often useful to see what has changed since you last visited the wave.
You can use the composition of all operations between two historical
versions to express the difference between the two historical
versions. You most likely want this composition to reflect exactly
what content was deleted from the older version and what content was
inserted in the newer version (rather than trying to "optimise" this
composition into some sort of minimal diff, which can result in a
hodgepodge of strange-looking deletions and insertions).
C. Ability to determine attribution for the different portions of the
document content. It can be useful to display who authored what in a
document. For example, a wave client could possibly render different
parts of the document with different colours (or some other visual
indicator) to differentiate between contributions from different
participants. If you delete an "a" from the document and then insert
an "a" at the same location, it is not equivalent to doing nothing.
On the contrary, you are deleting an "a" authored by someone else, and
inserting an "a" authored by you.
3. The third point is just an informational note I thought I should
point out. The composer you currently have access to in the code base
should not be used inside undo algorithms or optimised transform
algorithms. We're making a different type of composer for that
purpose.
There are two effects of operations that can be composed, and so our
current design calls for two composers, one specialised for each
purpose:
A. Composer of the mutational effects of operations. This composes
the effects that operations have on documents.
B. Composer of the transformational effects of operations. (This
actually composes structures which are a little more sophisticated
than operations, rather than operations themselves.)
A's intended use is to efficiently express accumulated changes to a
document in a compact manner. The composed operations don't have to
transform exactly the same way as their constituent parts. In fact, a
composed operation usually transforms slightly more nicely than
transforming its constituent parts individually. Composer A is the
composer you probably should be using in nearly all cases.
B's intended use is to combine transformational effects in such a way
that they can be used to improve the efficiency of transform and undo
algorithms. It is this second composition (B) that is relevant when
discussing the relationship between composition (in B's sense),
transformation, and undo/redo algorithms.
I hope this clears up the confusion.
Best wishes,
Alex
On Sep 10, 3:25 pm, Eric Kidd <[email protected]> wrote:
> On Sep 9, 9:33 pm, Michael K <[email protected]> wrote:
>
> > Without reading the necessary material, my guess is that
>
> > deleteCharacters("def")
> > characters("def")
>
> > can be concatenated to
>
> > retain(3)
>
> I'm aware that certain OT frameworks can perform this normalization
> without breaking the underlying OT algorithm. But empirically, Google
> Wave does not perform this normalization. And I _think_ there are good
> reasons for this, at least once the first deleteCharacters("def") has
> been propagated. As far as I can tell, an implementation which
> performs this normalization will corrupt waves. (Of course, it's safe
> to perform this normalization when no other participant in the
> protocol can see either of the operations involved.)
>
> AFAICT, the OT algorithms which allow arbitrary cancellation of an
> operation and inverse are all more complicated that Wave. In other
> words, I believe this is a deliberate design decision, and not a
> shortcoming in the operation composer.
>
> Cheers,
> Eric
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Wave
Protocol" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/wave-protocol?hl=en
-~----------~----~----~----~------~----~------~--~---
