Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Eclipse Projects » Eclipse Communications Framework (ECF) » DocShare inconsistency
DocShare inconsistency [message #624004] Wed, 30 July 2008 19:52 Go to next message
Jonas Boetel is currently offline Jonas BoetelFriend
Messages: 1
Registered: July 2009
Junior Member
Hi,

I'm a big fan of Operational Transformation and all excited to see it
integrated into Eclipse. Needless to say that I immediately tried DocShare
myself. I have read some papers about Operational Transformation before
and I know that a lot of older implementations fail when it comes to
corner cases.

What I did is the following:
1. Shared an C++ document with a friend over Skype
2. Started editing non-overlapping sections (works great)
3. Tried automatic code reformatting (works too, looks kind of funny
seeing the changes dropping in one by one at the other site)
4. Tried automatic code reformatting while the other site is editing too
(inconsistency occurred)

From the Google talk I deduce that you already know about possible
inconsistencies when using "high level" editing functions. I wanted to
know if there is a problem with the Operational Transformation
implementation (Cola) or with the integration into Eclipse or something
else.

I looked at the source code and my best guess is that Cola might be fine.
I don't really know because of the tricky case when there is an insertion
inside a deletion. What i stumbled upon where the synchronization
mechanisms used for applying transformed operations to the document.

If I understood it correctly DocShare works on an IDocument where it
registered an IDocumentListener. I think this is a great idea because if
you can get the low level document synced you can sync every document
build upon it automatically. I also think that every document change
triggers the according events. It should definitely be possible to
reconstruct a single document just by listening to the change events and
applying them on a local copy. Even when those changes are caused by high
level edit operations.

So if Cola is not the problem and DocShare isn't missing any changes and
the communication channel is reliable, what is causing the
inconsistencies? My guess is as follows: When DocShare integrates a remote
operation it uses asyncExec to transforms it against the known local
operations and to apply the transformed operation to the document. I say
"known" local operations because I'm not sure if it's possible to have a
race condition here.

Is it possible to miss a document change while in asyncExec? Can there be
document changes in non-UI threads? What if a local change happens while
DocShare is in the "setEditorToRefuseInput(); [..]
setEditorToAcceptInput();" block? The related question is: How do other
edit operations guarantee consistency? For example the code reformatting
mentioned earlier. How do those operations gain exclusive access to the
underlying document? Is there some mechanism to acquire a mutex on an
IDocument?

The other question is: Are there plans to support more than two sites? I
know that Operational Transformation gets really complicated because you
need TP2 ( T(T(b,a),T(c,a)) == T(T(a,b),T(c,b)) ). In fact the only
implementation i know of being able to guarantee TP1 & TP2 is the one with
tombstones from Gérald Oster which basically never deletes anything. I'd
like to offer my help in this regard.

Thank you for your attention and patience.

Jonas Boetel
Re: DocShare inconsistency [message #624006 is a reply to message #624004] Thu, 31 July 2008 20:05 Go to previous messageGo to next message
Scott Lewis is currently offline Scott LewisFriend
Messages: 972
Registered: July 2009
Senior Member
Hi Jonas,

Thanks very much for this report.

Jonas Boetel wrote:
> Hi,
>
> I'm a big fan of Operational Transformation and all excited to see it
> integrated into Eclipse. Needless to say that I immediately tried
> DocShare myself. I have read some papers about Operational
> Transformation before and I know that a lot of older implementations
> fail when it comes to corner cases.
>
> What I did is the following:
> 1. Shared an C++ document with a friend over Skype


I didn't realize that you/someone had added shared editing to C++
editor. That's great! Can/would you be willing to contribute the
modifications/new plugin for other's usage?


> 2. Started editing non-overlapping sections (works great)
> 3. Tried automatic code reformatting (works too, looks kind of funny
> seeing the changes dropping in one by one at the other site)
> 4. Tried automatic code reformatting while the other site is editing too
> (inconsistency occurred)
>
> From the Google talk I deduce that you already know about possible
> inconsistencies when using "high level" editing functions. I wanted to
> know if there is a problem with the Operational Transformation
> implementation (Cola) or with the integration into Eclipse or something
> else.


Not a known/previously reported problem...but this is very possible (as
you have found :). There are, as you know, several high level
operations in several eclipse editors (like code reformatting,
refactorings, etc) that consist of several/many operations...and there
can be/is a problem when any of the following occur:

a) The high-level operations are not reflected accurately in the
low-level operations (insert/delete).
b) Some/all of the resulting low-level operations do not result in
IDocumentListener notifications (I'm not sure whether this is happening
or not in your case...but it is possible)
c) The operations are somehow improperly interleaved with remote
operations (e.g. by having other threads apply operations...so complex
sequences are not applied atomically).

>
> I looked at the source code and my best guess is that Cola might be
> fine. I don't really know because of the tricky case when there is an
> insertion inside a deletion. What i stumbled upon where the
> synchronization mechanisms used for applying transformed operations to
> the document.
>
> If I understood it correctly DocShare works on an IDocument where it
> registered an IDocumentListener. I think this is a great idea because if
> you can get the low level document synced you can sync every document
> build upon it automatically. I also think that every document change
> triggers the according events.


We think so too...although this is up to every editor implementation to
get correct...and of course we can't guarantee that.


>It should definitely be possible to
> reconstruct a single document just by listening to the change events and
> applying them on a local copy. Even when those changes are caused by
> high level edit operations.

Yes...although if...for whatever reason (a) is not satisfied, then
high-level operations might create problems.

>
> So if Cola is not the problem and DocShare isn't missing any changes and
> the communication channel is reliable, what is causing the
> inconsistencies? My guess is as follows: When DocShare integrates a
> remote operation it uses asyncExec to transforms it against the known
> local operations and to apply the transformed operation to the document.
> I say "known" local operations because I'm not sure if it's possible to
> have a race condition here.
>
> Is it possible to miss a document change while in asyncExec? Can there
> be document changes in non-UI threads?


This is indeed possible...and I don't know what (if any) policy there is
within the workbench editors (or others) regarding synchronizing
document changes/changes to document in non-UI threads. We need to
consult with someone more directly involved in the editor framework, I
believe, to answer this question. I will try to forward this onto Kai
Maetzel, who I know from the Eclipse Board, and who used to (at least)
work on the editor framework.

If others know the synchronization policy WRT multi-threaded access to
the IDocument please let all know.

What if a local change happens
> while DocShare is in the "setEditorToRefuseInput(); [..]
> setEditorToAcceptInput();" block? The related question is: How do other
> edit operations guarantee consistency? For example the code reformatting
> mentioned earlier. How do those operations gain exclusive access to the
> underlying document? Is there some mechanism to acquire a mutex on an
> IDocument?

Again, good question. I don't immediately know. We will find out.
Obviously, the current strategy assumes that the UI thread is the only
one accessing the IDocument...which may indeed be wrong (for high-level
operations particularly).

>
> The other question is: Are there plans to support more than two sites? I
> know that Operational Transformation gets really complicated because you
> need TP2 ( T(T(b,a),T(c,a)) == T(T(a,b),T(c,b)) ). In fact the only
> implementation i know of being able to guarantee TP1 & TP2 is the one
> with tombstones from Gérald Oster which basically never deletes
> anything. I'd like to offer my help in this regard.

Yes, there are plans for more than two sites:

https://bugs.eclipse.org/bugs/show_bug.cgi?id=240290

>
> Thank you for your attention and patience.

Thank you! Your report/observations are very helpful...and your offer
of help/assistance is most appreciated. Thanksinadvance for that!

Scott
Re: DocShare inconsistency [message #624010 is a reply to message #624004] Mon, 04 August 2008 23:01 Go to previous message
Scott Lewis is currently offline Scott LewisFriend
Messages: 972
Registered: July 2009
Senior Member
Hi Jonas/all,

I contacted my colleague that works on the jface text components (i.e.
IDocument stuff), and here are some of his response to my question. I said:

"Basically, among other things we need to understand the synchronization
conventions around access to IDocuments. If you have any info or
pointers, it would be most appreciated."

Kai responded:

....In principle, synchronization in the text framework is weak. For a
long time, the basic assumption has been that all access is in the UI
thread. With quickdiff, spelling, and annotation update in the
background this changed but only for those use cases. A good entry point
is ISynchronizable. Document and AnnotationModel are implementing this
interface. Look at the call sites for methods of it.

Scott


Jonas Boetel wrote:
> Hi,
>
> I'm a big fan of Operational Transformation and all excited to see it
> integrated into Eclipse. Needless to say that I immediately tried
> DocShare myself. I have read some papers about Operational
> Transformation before and I know that a lot of older implementations
> fail when it comes to corner cases.
>
> What I did is the following:
> 1. Shared an C++ document with a friend over Skype
> 2. Started editing non-overlapping sections (works great)
> 3. Tried automatic code reformatting (works too, looks kind of funny
> seeing the changes dropping in one by one at the other site)
> 4. Tried automatic code reformatting while the other site is editing too
> (inconsistency occurred)
>
> From the Google talk I deduce that you already know about possible
> inconsistencies when using "high level" editing functions. I wanted to
> know if there is a problem with the Operational Transformation
> implementation (Cola) or with the integration into Eclipse or something
> else.
>
> I looked at the source code and my best guess is that Cola might be
> fine. I don't really know because of the tricky case when there is an
> insertion inside a deletion. What i stumbled upon where the
> synchronization mechanisms used for applying transformed operations to
> the document.
>
> If I understood it correctly DocShare works on an IDocument where it
> registered an IDocumentListener. I think this is a great idea because if
> you can get the low level document synced you can sync every document
> build upon it automatically. I also think that every document change
> triggers the according events. It should definitely be possible to
> reconstruct a single document just by listening to the change events and
> applying them on a local copy. Even when those changes are caused by
> high level edit operations.
>
> So if Cola is not the problem and DocShare isn't missing any changes and
> the communication channel is reliable, what is causing the
> inconsistencies? My guess is as follows: When DocShare integrates a
> remote operation it uses asyncExec to transforms it against the known
> local operations and to apply the transformed operation to the document.
> I say "known" local operations because I'm not sure if it's possible to
> have a race condition here.
>
> Is it possible to miss a document change while in asyncExec? Can there
> be document changes in non-UI threads? What if a local change happens
> while DocShare is in the "setEditorToRefuseInput(); [..]
> setEditorToAcceptInput();" block? The related question is: How do other
> edit operations guarantee consistency? For example the code reformatting
> mentioned earlier. How do those operations gain exclusive access to the
> underlying document? Is there some mechanism to acquire a mutex on an
> IDocument?
>
> The other question is: Are there plans to support more than two sites? I
> know that Operational Transformation gets really complicated because you
> need TP2 ( T(T(b,a),T(c,a)) == T(T(a,b),T(c,b)) ). In fact the only
> implementation i know of being able to guarantee TP1 & TP2 is the one
> with tombstones from Gérald Oster which basically never deletes
> anything. I'd like to offer my help in this regard.
>
> Thank you for your attention and patience.
>
> Jonas Boetel
>
>
Previous Topic:ECF conference call for TODAY 7/31 cancelled
Next Topic:ECF twitter provider
Goto Forum:
  


Current Time: Mon Nov 24 03:00:01 GMT 2014

Powered by FUDForum. Page generated in 0.01669 seconds
.:: Contact :: Home ::.

Powered by: FUDforum 3.0.2.
Copyright ©2001-2010 FUDforum Bulletin Board Software