Balisage Paper: Track Changes Support for Automated Regex-Based Text Replacement in XML Documents

Change Tracking Representations in XML

Change tracking in XML documents takes three principal forms, each with different implications for automated processing.

Element wrapping. The most common approach uses dedicated elements to delimit inserted and deleted content. OOXML (ISO/IEC 29500) [1] wraps insertions in <w:ins> and deletions in <w:del>, each carrying author and timestamp attributes. ODF [2] uses analogous <text:insertion> and <text:deletion> elements. The ContentXML (CXML) format used in our implementation employs <style> elements with a status attribute whose value is "added" or "deleted", described in section “The Track Changes Markup Model”. In all these formats, the document contains both the original and proposed text simultaneously, and the change-tracking elements alter the document's tree structure by introducing additional nesting levels.

Processing instructions. An alternative approach uses processing instructions (PIs) to mark change boundaries without altering the element tree. The oXygen XML editor, for example, uses <?oxy_insert_start?> / <?oxy_insert_end?> and <?oxy_delete?> PIs [8]. Because PIs are not elements, they do not affect document nesting—a property that simplifies some processing scenarios but complicates others, since PIs cannot directly contain the deleted text.

Delta files. DeltaXML and similar tools represent changes as a separate delta document or as annotations merged into the original tree, rather than inline element pairs [9]. La Fontaine [10] proposes a standard change-tracking vocabulary for XML. La Fontaine's earlier work [11] provides a taxonomy of change-tracking models and discusses the design trade-offs among them.

The element-wrapping model is defined by the CXML (ContentXML) schema, maintained by Typefi [6], and is a constraint of the platform rather than a design choice. However, the pipeline described in this paper would apply, with straightforward adaptations, to any element-wrapping change-tracking vocabulary.

Tree-Based vs. String-Based Text Replacement

There are two broad strategies for applying regex replacements to XML content.

Tree-native replacement operates on text nodes within the parsed tree. The XSLT instruction xsl:analyze-string (available since XSLT 2.0 [12]) and the XPath function fn:analyze-string (available since XPath 3.0 [13]) decompose a string into matching and non-matching substrings, enabling regex-driven transformations without leaving the tree model. Kalvesmaki's TAN library [14] extends this approach with tan:batch-replace(), which applies an ordered sequence of find/replace pairs to text nodes, handling back-references and case folding within XSLT. The advantage of tree-native replacement is that tag boundaries are never at risk: the processor sees only text-node content, not serialized markup.

String-based replacement serializes an XML subtree to a string, applies regex matches to the serialized form, and parses the result back into the tree. This is the approach taken in the present work. The choice is driven by compatibility with a large corpus of existing dictionaries whose regex patterns were authored against serialized paragraph text, including patterns that span inline element boundaries—for example, matching text that is partly in one inline element and partly in adjacent text. The cost is that the serialized string contains tag syntax that the regex engine must be taught to avoid (section “Tag Context Detection”), and each round-trip through serialization and parsing introduces potential for namespace or whitespace artifacts (section Design Trade-offs, paragraph Serialization round-tripping).

Offset Management and Operational Transformation

When multiple replacements are applied sequentially to a single text, each replacement may change the text's length, shifting the positions of all subsequent match candidates. This is a well-known problem in collaborative editing, where it is addressed by operational transformation (OT) [7]. In OT, each editing operation carries positional metadata that is transformed against preceding operations to account for insertions and deletions that have shifted the text.

Our offset propagation strategy (section “Offset Management”) is a simplified instance of OT: replacements are applied sequentially rather than concurrently, and the transformation function is a simple additive shift rather than the more complex inclusion/exclusion transforms required for concurrent edits. The connection is worth noting because it clarifies the correctness invariant: after all replacements have been applied, every positional record must refer to the same final text state—exactly the convergence property that OT guarantees.

Phase 1: Unwrapping Pre-existing Track Changes

The purpose of the first phase is to transform the paragraph from its mixed markup/track-changes form into clean text (still XML, but without <style status> wrapper elements), while recording the position and authorship of every pre-existing track change so it can be reinstated in Phase 3.

The method traverses the child elements of the paragraph looking for <style> elements with a status attribute. For each status="deleted" element, it records the inner XML content as deletedText, finds the element's character offset within the serialized paragraph string, removes the element from the DOM, and creates a ReplacementInfo record. For each status="added" element, it moves the element's children directly into the parent paragraph (unwrapping the <style> wrapper), records the addedText, and creates a corresponding ReplacementInfo record. In both cases, the author and dateTime attributes from the original element are preserved in the ReplacementInfo.

                     
// Phase 1 — simplified excerpt
if ("deleted".equalsIgnoreCase(status)) {
    deletedText = convertNodeToString(tc, transformer);
    start = pText.indexOf("<style author=\"" + tc.getAttribute("author")
                          + "\" ... status=\"deleted\">" + deletedText + "</style>");
    pElement.removeChild(tc);
}
if ("added".equalsIgnoreCase(status)) {
    addedText = convertNodeToString(tc, transformer);
    while (tc.hasChildNodes())
        pElement.insertBefore(tc.getFirstChild(), tc);
    pElement.removeChild(tc);
}
ReplacementInfo rInfo = new ReplacementInfo(
    "", 0, start, start + codePointCount(addedText),
    deletedText, addedText, true,
    tc.getAttribute("author"), tc.getAttribute("dateTime"));
allReplacementsForPNode.add(rInfo);

After Phase 1, pElement contains the paragraph with track changes unwrapped—the added text is present inline and the deleted text is captured in allReplacementsForPNode. The paragraph is now ready for regex processing without any change-tracking markup interfering with pattern matching.

Phase 2: Regex Replacement with Position Tracking

Phase 2 processes the paragraph through each rule group in order. For each group it performs the following steps.

Serialization. The paragraph node is serialized to a string. Protected inline elements are replaced with fixed-width placeholder strings padded to the same code-point length as the serialized element. This allows the text positions of surrounding content to remain stable while preventing replacements from being applied inside protected markup.

Pattern matching. For each rule whose scope matches the paragraph's style, a java.util.regex.Pattern is compiled and applied to the serialized text. For each match, the code checks:

For each accepted match, a ReplacementInfo is added to the per-group local list.

Offset-aware application. After all rules in the group have been scanned, the per-group replacements are sorted by start position and applied sequentially to a StringBuffer:

                     
for (ReplacementInfo info : allReplacementsForGroup) {
    int offset = codePointCount(info.getReplacedText())
               - codePointCount(info.getOriginalText());
    buffer.replace(info.getStartIndex(), info.getEndIndex(),
                   info.getReplacedText());

    // Shift all subsequent replacements in the same group
    allReplacementsForGroup.stream()
        .filter(r -> r.getStartIndex() > info.getStartIndex())
        .forEach(r -> {
            r.setStartIndex(r.getStartIndex() + offset);
            r.setEndIndex(r.getEndIndex() + offset);
        });

    // Shift TC records from earlier groups that fall after this position
    allReplacementsForPNode.stream()
        .filter(r -> r.getStartIndex() > info.getStartIndex()
                  && r.getGroup() < info.getGroup())
        .forEach(r -> {
            r.setStartIndex(r.getStartIndex() + offset);
            r.setEndIndex(r.getEndIndex() + offset);
        });

    if (info.getEnableTc() && !isSameText) {
        allReplacementsForPNode.add(new ReplacementInfo(
            info.getRegexId(), groupIndex,
            info.getStartIndex(), info.getEndIndex() + offset,
            info.getOriginalText(), info.getReplacedText(),
            true, "", ""));
    }
}

The critical invariant is that every ReplacementInfo in allReplacementsForPNode—whether from Phase 1 (pre-existing track changes) or accumulated during Phase 2—always refers to positions in the current processed text, not in any earlier snapshot. The two-level filtering (same-group records vs. earlier-group records) maintains this invariant as groups are processed in sequence.

Placeholder restoration. After each group's replacements are applied, the placeholder strings for protected elements are expanded back to their full XML serializations.

Phase 3: Reconstructing Track Changes Markup

After Phase 2 completes, currentProcessedText is the fully replaced paragraph text as a flat string (still containing inline XML markup for bold, superscript, etc., but no <style status> wrappers), and allReplacementsForPNode is a sorted list of every change that should be recorded as a track change—both pre-existing editorial changes and new programmatic ones.

The reconstruction method walks through allReplacementsForPNode in order and produces a new XML string:

                     
public String processTrackChanges(String text,
        List<ReplacementInfo> replacements,
        int start, int end, ...) {

    StringBuilder result = new StringBuilder();
    int currentIndex = start;

    for (ReplacementInfo info : replacements) {
        // Skip records that are "shadows" of pre-existing TC changes
        boolean isSameText = replacements.stream().anyMatch(r ->
            r.getStartIndex() == info.getStartIndex()
            && r.getReplacedText().equals(info.getOriginalText()));

        if (info.getStartIndex() > end
                || info.getEndIndex() <= currentIndex
                || isSameText)
            continue;

        // Emit any text between the previous change and this one
        if (info.getStartIndex() > currentIndex)
            result.append(text.substring(currentIndex, info.getStartIndex()));

        // Collect nested replacements
        List<ReplacementInfo> nested = replacements.stream()
            .filter(other -> other != info
                && (other.getStartIndex() >= info.getStartIndex()
                    && other.getEndIndex() <= info.getEndIndex()
                    && other.getGroup() >= info.getGroup()
                    || other.getStartIndex() == info.getStartIndex()
                    && other.getOriginalText().equals(info.getReplacedText())))
            .collect(toList());

        String addedContent = nested.isEmpty()
            ? info.getReplacedText()
            : processTrackChanges(text, nested,
                                  info.getStartIndex(), info.getEndIndex(), ...);

        String author = info.getAuthor().isEmpty()
            ? "Tool: " + info.getRegexId()
            : info.getAuthor();
        String timestamp = info.getDateTime().isEmpty()
            ? config.getTimeStamp()
            : info.getDateTime();

        result.append("<style status=\"deleted\" author=\"" + author
                      + "\" dateTime=\"" + timestamp + "\">"
                      + info.getOriginalText() + "</style>");
        result.append("<style status=\"added\" author=\"" + author
                      + "\" dateTime=\"" + timestamp + "\">"
                      + addedContent + "</style>");

        currentIndex = info.getEndIndex();
    }

    if (currentIndex < end)
        result.append(text.substring(currentIndex, end));

    return result.toString();
}

For programmatic changes, the author string is synthesized from the rule identifier and the timestamp is the current system time (or a fixed value for reproducible testing). For pre-existing editorial changes, the original author and timestamp are forwarded unchanged.

Cross-Group Positional Nesting

The nesting condition in Phase 3 has two disjuncts. The second (semantic match: other.originalText.equals(info.replacedText)) detects genuine nesting as described above—a later rule modifies text that an earlier rule introduced. The first disjunct is purely positional: it checks whether one record's range falls inside another's. However, because offset propagation (section “Cross-Group Consistency”) retroactively shifts earlier-group records to account for length changes made by later groups, an earlier-group record's position may end up inside a later-group record's range as an artifact of the arithmetic, even though the two records operated on independent text in separate passes.

To prevent the positional condition from misclassifying such cases as nested, the condition includes a group-ordering guard: positional containment is only recognized when the inner record belongs to the same or a later group than the outer record. Records from an earlier group can only be nested via the semantic condition. This separation ensures that the two disjuncts handle complementary cases: same-or-later-group nesting is detected by position, cross-group nesting by textual identity.

Code-Point Indexing

The system uses Java's String.codePointCount(0, length) rather than String.length() for all position computations. This ensures correctness for Unicode content containing characters outside the Basic Multilingual Plane (represented as surrogate pairs in Java's UTF-16 char encoding), which appear in scientific and mathematical content—a common case in academic publishing.

Intra-Group Offset Propagation

Within a single rule group, replacements are sorted by start position and applied left-to-right. After each application, the offset Δ = codePointCount(replacedText) − codePointCount(originalText) is propagated forward:

The directional filter (startIndex > info.getStartIndex()) ensures that only records positioned after the current replacement are shifted, since the replacement does not affect text before its start position.

A concrete example illustrates how positions shift after a replacement:

Before replacement:   "the  h  of onset"
                       0  4  6  8
                          ↑ match: " h " → " hour " (Δ = +3)

After replacement:    "the  hour  of onset"
                       0  4      9  11
                                 ↑  ↑
                          positions shifted by +3

Records after this position:  startIndex += 3, endIndex += 3
Records before this position: unchanged

Cross-Group Consistency

Rules in later groups see the text as modified by all earlier groups. When a later group produces a ReplacementInfo, its positions are already correct for the current text state. Earlier-group records in allReplacementsForPNode must be retroactively adjusted whenever a later-group replacement changes the text length. The condition r.getGroup() < info.getGroup() in the offset propagation loop performs this retroactive adjustment.

This approach means that after all groups are processed, every record in allReplacementsForPNode—regardless of which phase or which group produced it—is positioned relative to the same final text snapshot that Phase 3 operates on. A consequence is that an earlier-group record's position may be shifted into a later-group record's range, creating a positional coincidence that Phase 3 distinguishes from semantic nesting via the group-ordering guard (section “Cross-Group Positional Nesting”).

Tag Context Detection

A particularly subtle offset concern involves XML tags embedded in the serialized paragraph text. A scanning method examines angle brackets to determine whether a regex match's span falls entirely within a tag's angle-bracket delimiters, partially straddles a tag boundary, or falls entirely between tags. Only matches classified as falling entirely outside of tags are accepted. A match that straddles a tag opening or closing is discarded without generating a ReplacementInfo, preventing the replacement engine from corrupting the XML markup.

Design Trade-offs

DOM vs. streaming. The implementation uses DOM (Document Object Model) [3] parsing throughout. For the document sizes encountered in publishing workflows—typically tens of thousands of words per document—DOM's memory model is acceptable. A streaming approach (SAX or StAX) would complicate the paragraph-reversal traversal and the node-replacement operations that are central to the pipeline.

Paragraph-level granularity. Track changes reconstruction operates at the paragraph (<p>) level. Each paragraph is processed independently: it is extracted as a DOM subtree, serialized to string, processed, and replaced in the document. This granularity matches the editorial workflow assumption that reviewers accept or reject changes paragraph by paragraph. It also provides error isolation: if a single paragraph produces malformed XML during reconstruction, only that paragraph fails; the remaining paragraphs are still processed.

Serialization round-tripping. The pipeline repeatedly converts between DOM nodes and strings. Each round-trip wraps the target string in a temporary element before parsing, then imports the resulting child nodes into the main document as a DocumentFragment. The implementation configures the serializer with OMIT_XML_DECLARATION=yes and INDENT=no to prevent namespace or whitespace artifacts.

Limitations

Single-layer nesting. The current implementation handles the two most common scenarios: (a) programmatic changes applied to a clean document, and (b) programmatic changes applied to a document that already contains at most one layer of pre-existing track changes per position. Deeply nested track changes (three or more layers, arising from multiple sequential editing passes—human or programmatic—whose results have not yet been accepted) are not excluded by the data model but are not a tested path, and the recursive processTrackChanges() call would need to be evaluated carefully for correctness in that case.

Overlapping changes across positions. Consider the case where an editor has changed alpha to beta and an automated rule targets alphabet in the original text. The string alphabet spans the boundary of the editorial change: alpha has been replaced by beta, and bet is now followed by whatever came after. In the element-wrapping model, there is no clean representation of a change that straddles a pre-existing change boundary. The current implementation handles this conservatively: Phase 1 unwraps the editorial change, so the text seen by Phase 2 reflects the current state (beta...), not the original (alpha...). A rule targeting the original text alphabet would simply not match. This is correct behavior—the tool processes the document as it stands—but it means the tool cannot reason about the original pre-change text. Word processors with richer change-tracking models (such as OOXML's run-fragmentation and anchor-based approach) can represent finer-grained overlapping edits, at the cost of considerably more complex markup.

Rule ordering. Because replacements within a group are sorted by start position and applied left-to-right, the result is deterministic given a fixed rule order. However, the interaction between rule groups—where a later group may replace text introduced by an earlier group—is order-dependent. This is intentional: dictionary precedence gives authors control over the order in which transformations are applied. The nested track-changes representation faithfully records this layering so reviewers can see which automated step produced which change.

Comparison with XSLT-Based Approaches

An alternative implementation strategy would use XSLT to apply the replacement rules. The tree-native approach to regex replacement, via xsl:analyze-string (XSLT 2.0+) or fn:analyze-string (XPath/XQuery 3.0+), provides a solid foundation for this kind of work [12], [13]. In a purely tree-native design, regex operations would target individual text nodes, avoiding serialization of the full paragraph markup. However, since the existing dictionaries contain patterns that match across inline element boundaries, an XSLT implementation would still need to serialize paragraph content to a string for matching and parse the result back into the tree—the same round-trip the current Java implementation performs.

The regex capabilities of XPath 3.0 cover most of Java's java.util.regex features. The notable gaps are: lookbehind assertions (XPath regex supports lookahead (?=...) and (?!...) but not lookbehind (?<=...) and (?<!...)), possessive quantifiers, and certain Unicode property shortcuts. Saxon's j flag for fn:matches and fn:replace provides access to Java's full regex engine, bridging most of these gaps for deployments that use Saxon [15]. XPath 4.0 (currently in draft) proposes adding lookbehind support to the standard [16].

Kalvesmaki's tan:batch-replace() [14] could serve as the replacement engine for Phase 2, but it is opaque with respect to per-replacement positional metadata: it returns transformed text but not the replacement log—start position, end position, original text, replaced text, and group number for each match—that Phase 3's track-changes reconstruction requires.

However, the core algorithm described in this paper is fundamentally stateful and imperative. ReplacementInfo records are accumulated, mutated in-place, filtered by group, sorted, and passed through recursive calls. The offset propagation requires in-place mutation of a shared list with different filtering criteria at each step. While XSLT 3.0 can model this using maps, arrays, xsl:iterate, and accumulators [12], the natural grain of XSLT is declarative tree transformation—not maintaining and mutating shared position records across sequential passes. XSLT accumulators, in particular, could be used for offset tracking: an accumulator that observes text nodes could maintain a running position counter. But the two-level offset adjustment (same-group vs. earlier-group) and the recursive nesting detection would require threading complex state through the accumulator or restructuring the algorithm into a more functional form.

The decision to use Java was driven by three factors: integration requirements with Typefi's plugin API, the natural fit of the imperative algorithm with Java's mutable data structures, and compatibility with a large corpus of existing Orion dictionaries whose regex patterns were authored against serialized paragraph text. An XSLT-based reimplementation is feasible and might benefit from the tree-native approach for the replacement step, but would require either rewriting these dictionaries to operate on text nodes or replicating the serialization strategy, and the track-changes reconstruction logic would likely need to be restructured rather than transliterated.