Document comparison (DocReview)
DocumentComparer.compare(original:revised:options:) returns a ComparisonResult:
| Member | Content |
|---|---|
changes |
[DocumentChange]: kind (inserted, deleted, modified, moved, formatting, style, structure), body block indexes on both sides, before/after excerpts, a readable detail, and the story (body, header, footer, note). |
rows |
[AlignedRow] for the side-by-side view, in the order of merged.body: equal, modified, inserted, deleted, movedFrom, movedTo, with the original, revised and merged block indexes. |
merged |
The revised document in which every difference is a tracked change by options.author. |
summary |
Counts per kind, words inserted / deleted / moved, similarity. |
reportMarkdown, reportDocument |
The report as Markdown and as a formatted ORIX document (title, summary table, change list, page-number footer). |
ComparisonResult has the same name as Foundation.ComparisonResult. A file that imports Foundation writes DocReview.ComparisonResult
or uses the alias DocumentComparison.
Pipeline
- Flatten. Pending tracked changes of both inputs are read as accepted (deleted runs dropped, marks cleared). Block indexes do not move.
- Fingerprint. Every block gets a content key: the paragraph text (lower-cased with
ignoreCase, white space collapsed withignoreWhitespace) in which each inline object is replaced by its payload key; a table is the keys of its cells; breaks and generated blocks are their kind. Formatting is not part of the key. Keys are interned to integers, so equality is exact (no hash collision). - Block alignment (
SequenceDiff.lcs). Common prefix and suffix are trimmed; keys that occur exactly once on each side are pinned (patience diff, longest increasing chain in O(n log n)); between two pins the linear-space Myers algorithm (middle snake, two diagonal vectors, O(n + m) memory) finds the rest. A Myers sub-problem that needs more than 2 048 edit steps is abandoned and treated as having nothing in common. No O(n²) table exists at block level. - Gap pairing. Between two matches, unmatched original and revised blocks of the same type are paired when the Dice similarity of
their word bags is ≥ 0.5 (
ComparisonTuning.modifiedSimilarity); the pair is one modified block instead of a deletion and an insertion. Gaps up to 10 000 cell pairs are paired optimally (order-preserving dynamic programming on the gap only); larger gaps use a forward window of 32 blocks. - Moves. Among the paragraphs left deleted and inserted: an exact move needs the same content key, at least 24 UTF-16 units and 4 words; a move with edits needs Dice similarity ≥ 0.85, at least 40 units and 8 words, and is searched only while (deleted × inserted) ≤ 250 000. Anything else stays a deletion and an insertion. Tables are never reported as moved.
- Token diff. A pair of paragraphs is tokenised (words from
NSString.enumerateSubstrings(.byWords), so Chinese, Japanese and Thai are segmented into words; runs of white space; every other composed character on its own; each inline object is one token keyed by its payload) and diffed with Myers (cap 4 096). Token boundaries are composed-character boundaries, so no edit splits a surrogate pair, a ZWJ emoji sequence or a base letter and its combining marks. Offsets are UTF-16. - Formatting. On text that is equal on both sides, the two runs are compared: identical direct properties and character style → no
change; otherwise the fully resolved formatting of each run in its own style sheet decides (so
bold: falseon a non-bold style is not a change). A difference becomes aformattingchange ("Bold added", "Font size 11 → 12") and never a content change. Paragraph properties and lists areformatting; a different paragraph style isstyle("Style Heading2 → Heading3"); a changed style definition isstyletoo.
Inline payload keys: image = bytes of the asset (the id when the asset is absent) + width × height; shape = kind, size, text; equation =
LaTeX + display flag; citation = keys with locator, prefix, suffix; note reference = kind, and the note content for block alignment;
cross-reference = target + display; field = kind and argument; bookmark = name. Alternative text, crop, rotation and placement of an
image are reported as formatting.
Tables
Rows are aligned by LCS on their text; a gap with as many rows on each side pairs them in order, otherwise by similarity ≥ 0.5.
When the column counts differ and both tables are regular (one unmerged cell per grid column in every row), columns are aligned the same
way on their content in the paired rows. Paired rows × paired columns are compared cell by cell (a cell holding one paragraph on each
side is always shown as an edited paragraph). Inserted or deleted rows and columns are structure changes. Tables with no row or column
in common, or with different column counts and merged cells, are reported as replaced: the original table as a deletion followed by
the revised table as an insertion.
Other stories and structure
- Notes: note references that face each other in a paragraph diff have their contents compared; changes carry
story == .note(id)and the block index of the host paragraph. - Headers and footers are compared for every section index present on both sides, every variant.
- Page setup differences per section (paper, orientation, margins, columns, numbering, border, watermark …) are one
structurechange. - Page, column and section breaks, tables of contents and the bibliography block inserted or removed are
structurechanges.
The merged document
| Difference | Representation |
|---|---|
| Inserted text | runs with Revision(.insertion) |
| Deleted text | the original runs, kept, with Revision(.deletion) |
| Inserted / deleted paragraph | every run and markRevision carry the revision |
| Formatting of unchanged text | FormatRevision(previous:previousCharStyle:) holding the original properties |
| Moved paragraph | deleted at the old place, inserted at the new one |
| Inserted / deleted table row or column | every paragraph of its cells is marked inserted / deleted |
| Replaced table | the original table fully deleted, then the revised table fully inserted |
Revision ids are cmp-N, deterministic. Blocks taken from the original get a new id when theirs is already used (id~o), and the notes,
image assets, styles, lists and references they need are copied into the merged document.
Invariant (tested, including 40 seeded random edit scripts): accepting every change gives the revised text, rejecting every change gives the original text. Limits of the invariant, all due to what the model can track:
- Paragraph style, paragraph properties, list membership, table and cell properties, page setup: the merged document takes the revised value; the difference is reported but cannot be rejected (there is no paragraph-level format revision).
- Removed breaks and generated blocks are reported but not kept (no tracked deletion for atomic blocks);
AlignedRow.mergedis nil. - In a table that gains a column and loses a row at once, a deleted row keeps the original cells only, so it is shorter than the grid.
- Canonically equivalent text ("é" precomposed against "e" + U+0301) is equal text; the merged document keeps the revised encoding.
- With
ignoreCase/ignoreWhitespace, the ignored differences are taken from the revised document.
Performance
Measured by PerformanceTests (debug build, Apple silicon): two documents of 5 000 paragraphs with 250 edits, 100 deletions,
100 insertions and 20 moves in about 0.4 s; two unrelated documents of 3 000 paragraphs (worst case) in about 0.8 s.
Only the blocks that fall in a gap are tokenised.