Processing instruction-based features

A common method of tracking changes in XML is to capture them inline, in the document itself, using processing instructions. Processing instructions are XML nodes that provide information to the application that is rendering or otherwise handling the XML. In serialized XML, they are represented in the format:

A common use of processing instructions is to designate the XSLT or CSS stylesheet to be used in rendering XML:

In this example, we see the target is "xml-stylesheet" and the content is given in pseudo-attributes. Pseudo-attributes resemble attributes found within elements, in that they have a name followed by an equals sign and a quoted value, but they are not separate nodes as real attributes are.

An advantage of processing instructions is that they may be placed anywhere in an XML document without causing validation errors. So, the same processing instructions may be used in XML documents valid to any document type definition (DTD) or schema. This is important when designing a system that may be used to edit XML from different DTDs.

Processing instructions are effective at capturing simple insertions. In this example, the target is set as "insertion", and the content is a pseudo-attribute that gives the text that has been inserted:

The processing instruction for simple insertions may be unambiguously placed where the text in question should appear. Retaining the placement of PIs for deletions may, however, be complicated by the addition of text in the same location as the deleted text that separates the place where the text was deleted from the PI itself.

In either case, processing instructions struggle to capture mixed content, that is, text that has other elements interspersed, such as text formatting elements or cross references. The reason is that the working copy of of the text needs to remain valid, and so, if a change including internal tagging captured in a processing instruction is rejected, there is a risk that the document will no longer be valid. As well, "unwraps" of tagging can be captured in processing instructions, but they and other changes are computationally expensive, as the system must update the PI with each user interaction. This quickly becomes too slow to be useful.

The complexity grows with nested formatting, deletions whose boundaries fall in the middle of formatted text, etc. For these reasons, some systems using PIs to track changes limit themselves to tracking insertions and deletions of text only, and this choice can lead to odd behaviors when coupled with functionality that allows users to accept or reject changes. If formatting is not tracked in a deletion, for example, rejecting that deletion may reinstate the text while losing the formatting.

A potential way to get around the issues of mixed content is to use pairs of processing instructions, associated by an id pseudo-attribute, that span the range of the deletion:

However, processing instructions that carry the same "id" in a pseudo-attribute are not really related in a way that is meaningful in the context of XML, as matching ID and IDREF attributes are. So, any system using pairs of processing instructions to wrap changes must add a layer of its own logic to keep track of their positions and relation. This can be tricky, especially when the changes in a document build up, involve structural changes and moving large blocks of text, or include changes by different users that overlap or conflict. When evaluating an XML editor that used such a system, we could find combinations of changes and accept/reject actions that resulted in much of the document being deleted without that deletion being tracked.

We did not move forward with that system.

1:1 XML differencing

The accuracy and stability problems of tracking changes using processing instructions are largely solved by using XML differencing. XML differencing allows the separation of concerns around editing functionality, on one hand, and change tracking on the other. Changes are not tracked in real time while a user is editing and they are not stored in the edited document itself using XML nodes that are not quite up to the task. Instead, two versions of a document are compared, and the differences are presented to the user. So, the editing process does not suffer a performance hit for having to keep track of changes at the same time, and it is guaranteed that changes will not be "lost" due to garbled markup in the document itself.

Rendering changes identified by XML differencing can prove to be a challenge. The differencing engine must resolve the longest common subsequence problem so that the changes reported are meaningful to the editor reviewing them. In the example given in O'Connor et al. (2012), the text "The entrails told the future" is changed to "Then trains stole the furniture". A raw differencing of those strings of text yields "Then entrail ns stold e the furniture" (where underlines are insertions and strikethroughs are deletions), which is less than clear and gives the editor too many changes to review. Fortunately, more sophisticated differencing engines such as DeltaXML do a good job grouping changes into meaningful blocks, yielding "The entrails told Then trains stole the future furniture".

Typefi made use of DeltaXML and 1:1 XML differencing when they developed a redlining application for the International Organization for Standardization (ISO; Perera, 2014). ISO was publishing 1700 standards per year at that time, and most of the revisions were done by multiple people in MS Word files. Using Word's Track Changes feature was considered unreliable, as authors could make changes "disappear" by accepting or rejecting them. In addition, overlapping changes, moving blocks of text, and text that was added and then deleted could combine to create an overwhelming and misleading record of the changes made.

The solution was to use eXtyles to export the text of the "before" and "after" versions to XML and then compare them using DeltaXML. The resulting XML diff was then visualized using Typefi. The rendered version showed easily understood green underlining for insertions and red strikethrough for deletions. Because the comparison highlighted only the changes that made it into the final version, users were not distracted by the "noise" of back and forth deliberations that occurred in the Word file.

However, one workflow's noise is another's music (https://youtu.be/BcqC8LSoBws; warning: flashing and strobing lights). In a journal article production workflow, editors will want to see all the changes made at each correction stage and, importantly, they'll want to know who made what changes.

Supersetting with change tracking elements and attributes

To overcome the limitations of 1:1 XML differencing and the inherent instability of using processing instructions to try to capture complex changes in JATS XML, one can superset the DTD by adding specialized change tracking elements. This approach was taken by Dartmouth Journal Services when it developed its ArticleExpress JATS editor (O'Connor et al., 2012).

As in processing instruction-based change tracking systems, information about the alterations is captured inline in the XML itself. However, using elements and attributes to encode this information instead of processing instructions and pseudo-attributes makes such a system more robust, as the underlying XML editor is built to handle the manipulation of these XML nodes. An insertion or deletion element wraps the changed text, and if inserted text was, say, split into separate paragraphs, the native functionality of the XML editor duplicates the change tracking tagging, thus maintaining its integrity.

This system exposes internal (changes within changes) and overlapping changes by using XSLT to denormalize the change tracking elements added by the XML editor.

This structure gives necessary information to the system's accept/reject feature. In that feature, when changes are found within changes, the "outer" change must be acted upon first to maintain the integrity of the XML. The action taken on the outer change determines whether the inner change may be accepted or rejected. For example, the acceptance of an outer insertion allows either acceptance or rejection of an inner insertion. The rejection of an outer insertion, on the other hand, would force the rejection of the inner insertion. This prevents the acceptance of an inner insertion that may only be valid in the context of the outer insertion. A rules engine was built to handle all of the various combinations of insertions and deletions, and it worked recursively to any depth of nesting.

There are drawbacks to such a system. It works fine for text insertions, deletions, and formatting, but did not capture changes to structure or attribute values. Being dependent on the event handlers and listeners of the XML editor added issues of compexity and potential performance problems. Also, XSLTs and the supersetted DTD needed to be maintained through revisions of JATS. Not insignificantly, the change tracking system took quite a bit of time and effort to develop, and it was sensitive to changes in the API of the underlying editor.

Architecture

The DH application is developed as a stand-alone component. It contains only the logic for computing the changelog and the diffs, it does not store the revisions of an article. The revisions of an article are stored in the Editorial Manager database. The DH Architecture diagram depicts the logical overview of the components and their responsibilities.

DH Architecture

The Document History backend contains the following main components as depicted in the Main components diagram:

Main components

• The API component is a set of REST API services which are invoked by the DH UI.
• The CMS Client component retrieves the JATS XML contents of the revisions of the article which to compare from Editorial Manager.
• The FDiff component is an XML diffing engine which provides an XML-based A/B comparison between to XML files.
• The Changelog component stitches multiple FDiff A/B comparisons together into a so-called changelog. This changelog contains all across all the revisions of an article. The output of the changelog is JATS article XML enriched with change annotations.

XML Encoding of changes

The DH component is schema agnostic, it operates on JATS, NISO-STS, DITA or any other schemata alike. As such, the changes are encoded using proprietary XML elements and attributes in a separate namespace. The consequence of this choice is that the resulting annotated JATS article XML does no longer conform to the JATS schema. For the DH UI, that is not a problem because it offers a read-only view with custom rendering logic.

For further downstream processing of the enriched article it would require either an extension to the JATS schema, or an transformation to equivalent elements and attributes in the schema. JATS Version 1.2, nor the closely related NISO STS 1.0, does not provide suitable constructs for encoding such changes. Alternatively, XML processing instructions may be used to encode the changes. This is not explored as part of this paper.

In its current state the following change types are recognized and encoded:

1. Text additions and deletions. (See Example: Simple text changes)
2. Wrapping and unwrapping of inline elements. (See Example: Inline formatting changes)
3. Insertions and deletions of block-level elements.
4. Moving of block-level elements (See Example: Moves).
5. Block-level replacements for MathML equations and images.
6. Attribute additions, deletions and modifications.

Example: Simple text changes

<p>A sentence with <fxd:text fxd:addition="">added</fxd:text> and <fxd:text fxd:deletion="">deleted</fxd:text> text.</p>

Example: Inline formatting changes

<p>Text which of which <bold fxd:wrap="">a part</bold> is made bold. Text of which <bold fxd:unwrap="">a part</bold> was bold.</p>

Example: Moves

<article> <body> <!-- The new location of the paragraph --> <p fxd:moveId="move-123">The following sentence is an English-language pangram—a sentence that contains all of the letters (more...)

Changelog

Consider the Revisions and their comparisons diagram. Each box represents the XML of a specific revision of the article. So in this example there are three revision of the article: R1, R2 and R3. R1 and R3 are attributed to the author Charles while R2 is attributed to author Bert. The arrows between the boxes represent comparisons.

Revisions and their comparisons

In a typical diff application, only two revisions are compared, say R1 and R3. In such application it would be impossible to attribute a change to a specific revision and thus author. A user of such application needs to perform two comparisons in order to be able to properly attribute changes to the respective authors. This can be done in a traditional diff application but is cumbersome because the author would need to switch between the two comparisons manually.

Overlapping changes are changes made by one author, say Bert in R2 which are subsequently revert by another author, Charles in R3. This is also known as an edit-war (Yasseri et al., 2012). The net result of both changes would be zero and thus would not show up in a A/B comparison between R1 and R3.

A changelog is a set of A/B comparisons stitched together in such a way that the result is a concatenation of all the individual comparisons. This is done in order to be able to attribute changes to a specific authors and to be able to display overlapping changes. Each change incorporated in the changelog is annotated with the specific revision in which to change was made. This is how the DH UI can display when and by whom a particular change was made. This information and some more are stored in the fxd:changeId attribute.

The stitching algorithm, which creates the changelog, needs to split changes if a change in a later revision is within a prior change. Consider the Example editor war fragment where a change with identified by id1 was split by a later change identified by id2.

The stitching algorithm also needs to be able to track moves temporally. For example: a paragraph can first be moved, then be edited and then be moved again for example. The author must be able to see both moves and edits separately.

FDiff

The problem of document change detection is defined as the problem of finding a "minimum-cost edit script" that transforms one document into another document. A generic tree-to-tree correction (Tai, 1979) algorithm focuses on the syntactic structure. This algorithm works well for data oriented documents but not for text oriented documents. For our purposes we needed an algorithm which focuses on structured text. The core of the problem is to find changes which were made. XML documents, by definition, are trees, thus the problem is called the tree-to-tree correction problem. There are several algorithms known, each which their own running time and behavior characteristics.

The implementation of FDIff is a modified version of the X-tree Diff+ algorithm (Lee and Kim, 2006). This algorithm is optimized for structured text documents and supports insert, delete, update, move and copy (currently unused) operations.

Given 2 XML documents, referred to as left and right, the goal of the algorithm is to work out an optimal matching between the nodes. The algorithm works by finding a match between the nodes in the left and the nodes on the right. Each match has a score between 0 and 1 to indicate how good the match is. The steps required are layed out in the X-tree Diff+ paper. The algorithm is O(n) where n is the sum of the number of nodes in left and right.

The exact implementation of this algorithm is non-trivial and deservers it's own paper and thus is out of scope for this paper. The main modifications to the X-tree Diff+ will be described though.

This algorithm has the following features:

• It operates on XML document representation of structured texts.
• It leverages Fonto family concepts (e.g. block, frame, object, etc.) to optimize performance (Middel, 2019).
• It uses text similarity instead of stable identifiers.
• It produces an edit script that features the operations insert, delete, update and move. (copy is described in the paper but is not used at the moment).
• It computes an edit script in near linear time and space on average.

There are two modifications to the X-tree Diff+ algorithm, discussed in the following sections.