Changes Requirements from discussions on the LibreOffice implementation

[Svante Schubert <svante.schubert@gmail.com>]

Dear SC,

allow me to provide some feed-back from the discussion on change design in LibreOffice.

Following requirements are assumed:

1. We need to use references for the positions of the change. The nesting of changes within XML does not scale as dispatching a change includes the complete document. In addition overlapping (format) changes will not work as the order of rejection may be arbitrary. Therefore IDs are not an option as prior used for changes being tracked within the XML files. 
   In other words, this is necessary to be able to point into a remote read-only document without the need to have index on all possible positions. The position is referenced by convention counting prior logical objects.
   
2. The logical objects (e.g. paragraph, character, table cell) of the positions are hierarchical, similar their position in the ODF XML hierarchy.
   As only the XML is standardized not any application model, the XML is the binding factor.
   Top level objects for changes may be for instance on paragraphs, tables and images.
   
3. We want the changes (in our case to undo the tracked editor change) in a separate file, not the content.xml nor styles.xml. In order to be able to sign them separately (later more)
4. Once change-tracking is activated it either always tracking (I personally would find helpful for contract work) or otherwise only tracks those changes that would corrupt the position of existing changes.
   All those changes being insertion or deletion changes before an existing change require to be tracked. If this would not be the case the existing change position would need to be adopted, which might break later seals of signature.
5. The final state of the document is (in general) in the content.xml, styles.xml, etc. - if no change-tracking is supported the document is able to be loaded and should be read-only
6. The changes file contains a sequence of changes (similar to the work session of a single user)
   
7. The sequence of changes can be split up on several files, for instance by user or session. (A session is meant as potential multiple saving into same file, even multiple loading but without loaded by an editor.
8. In the future it would be helpful to be able to generate for equal documents the same hash. This seems to require an XML normalization prior to hashing. Ideas on that?
   
9. We want to be able to sign the changes of the XML by a single user in an own file (along with the content XML)
   To be able to add changes without breaking the seals, the changes would only be added to changes file.
   This is the ONLY case were the content.xml & styles.xml does not have the latest state of the document!
   Although it sounds a bit complex, most features as signature are already implemented in ODF applications such as LibreOffice and possible to be reused.
10. We want to be able to normalize the change sequence within a file, this includes:
1. No operations that cancel each other out exist in the same file. A user adding a paragraph and deleting it in the same session, will not be saved.
2. Operations of a session will be ordered by position, there will be no position being used more than once, otherwise the order will be changed and positions will be adopted according to Operational Transformation.
3. For ease of human usability, the order should be according to document order. 
   
   For example: Assume there is a document with three paragraphs, we call A, B and C.
   If a user will delete all three paragraphs the change file will be equal Independent of the order the user deletes the paragraphs:
   Add Paragraph A @pos 1
   Add Paragraph B @pos 2
   Add Paragraph C @pos 3
11. There is a unique ID on every change. For instance, an integer will do starting from "1". Changes can reference to prior change in other files. The Acceptance/Rejection of prior changes are new changes to be tracked - required for the signature scenario.)
12. As Undo/Redo have to be taking into account as user editing, mostly removing already existing changes

The first two scenarios to discuss should be:

1.  A user is doing change-tracking on a document he had worked on before with existing change files (unsigned) 
   
2.  A user is doing change-tracking on a document, where two different user worked on before with their two existing change files (unsigned) therefore the latest state is in the content.xml
   

Scenario 1)

• A "change-tracking change" contains all information to undo the user change and reference to the nodes array representing the writer model (as you described it before, Oliver)
  
• This array of nodes, I assume that the nodes within the array representing logical objects are always ordered in document order.
  
• At run-time we can determine if a new add/delete change is prior an existing change, if the new change is interfering with existing
  
• When the document is being loaded it should be possible to count the nodes representing logical objects (by events during load or likely much better by traversal on the array during load - as easier and more reusable) and compare their position with those from an existing change file
• An existing change points to a node where the change occurred. 
  
• Multiple changes can point to the same node. For instance, the user deletes A, B and C there are three pointers to the beginning.
  
• The document is empty, but the change file contains the addition of the three paragraphs.

Scenario 2)

• As above, but in addition...
• The changes of existing files can be mapped to a single sequence. The last change that is written is the first to be read.
  
• All changes from various files needs to be normalized as there is only one ordered list of changes

I hope to give more insights on these brief notes on our talk tomorrow.

Regards,

Svante