# onediff docs, all pages (OneDiff 1.0.1)
Every page of https://recursiveai.org/onediff/docs/ as markdown, getting started first. Index: https://recursiveai.org/onediff/llms.txt
# Getting started with OneDiff
Install OneDiff 1.0.1 for .NET 10, diff and merge text, compare two documents into a verified change list, and write a redline as HTML, JSON or PDF. Pure C#, with no native code and no network access.
## Install
The packages target `net10.0`, so you need the .NET 10 SDK.
```shell
dotnet new console -o OneDiffStart
cd OneDiffStart
dotnet add package RecursiveAI.OneDiff --version 1.0.1
```
Five packages are on NuGet at 1.0.1, all on one version:
- **`RecursiveAI.OneDiff`**: the text core. Diff, patches and three-way merge, with no dependency beyond the .NET base class library.
- **`RecursiveAI.OneDiff.Documents`**: the comparison engine, HTML redlines and the JSON change list. It brings in the core and `RecursiveAI.OneFont`.
- **`RecursiveAI.OneDiff.Pdf`**: digital PDFs in; changes marked on the original pages, or a rendered redline PDF. It brings in `.Documents`, `RecursiveAI.OnePdf` and `RecursiveAI.OneRender.Pdf`.
- **`RecursiveAI.OneDiff.Ocr`**: scanned PDFs and images, read by a local OCR engine (`RecursiveAI.OneOcr`).
- **`RecursiveAI.OneDiff.Tool`**: the `onediff` command-line tool.
Word documents are not part of 1.0. In the README’s words: “Coming in later releases: Word documents in and tracked-changes DOCX out (`RecursiveAI.OneDiff.Word`, in this repository and not in the first release), spreadsheets, slides, and the OneNLP value recognizer (`RecursiveAI.OneDiff.Nlp`).” Until then an Office file is refused:
```text
NotSupportedException: No document source is registered for this input, which looks like an Office Open XML or other zip-based document. Support for Office documents (DOCX, XLSX and PPTX) is coming in a 1.x release. Meanwhile, export the documents to PDF and compare the PDFs (with RecursiveAI.OneDiff.Pdf).
```
## Diff, patch and merge text
Put this in `Program.cs` and run `dotnet run`:
```csharp
using OneDiff;
using OneDiff.Merge;
string oldText = "Deliver within 30 days.\nPay within 45 days.\n";
string newText = "Deliver within 21 days.\nPay within 45 days.\n";
// The words that changed, as Markdown
Console.WriteLine(Diff.ToMarkdownInline(Diff.Words(oldText, newText)));
// A unified patch, and applying it
string patch = Diff.Unified(oldText, newText, "a/terms.txt", "b/terms.txt");
Console.Write(patch);
Console.WriteLine($"applied: {Diff.ApplyUnified(oldText, patch).Text == newText}");
// A three-way merge: edits to different lines merge
string baseText = "one\ntwo\nthree\nfour\n";
string ours = "ONE\ntwo\nthree\nfour\n";
string theirs = "one\ntwo\nthree\nFOUR\n";
TextMerge merged = Diff.Merge(baseText, ours, theirs);
Console.Write(merged.Text);
Console.WriteLine($"conflicts: {merged.HasConflicts}");
```
```text
Deliver within 3021 days.
Pay within 45 days.
--- a/terms.txt
+++ b/terms.txt
@@ -1,2 +1,2 @@
-Deliver within 30 days.
+Deliver within 21 days.
Pay within 45 days.
applied: True
ONE
two
three
FOUR
conflicts: False
```
Edits to the same or neighboring lines are a conflict, written with conflict markers in git’s `merge`, `diff3` or `zdiff3` style. See [Three-way merge](https://recursiveai.org/onediff/docs/merge/) and [Patches](https://recursiveai.org/onediff/docs/patches/).
## Compare two documents
Document comparison is in `.Documents`:
```shell
dotnet add package RecursiveAI.OneDiff.Documents --version 1.0.1
```
Save two versions of a short contract as `v1.txt` and `v2.txt`:
```text
1. Supply. The Supplier shall deliver the goods within 30 days of each order.
2. Payment. The Customer shall pay each invoice within 45 days of its date.
```
In `v2.txt`, change `30 days` to `21 days`. Then:
```csharp
using OneDiff.Documents;
using OneDiff.Documents.Serialization;
Comparison cmp = Comparison.Of("v1.txt", "v2.txt");
foreach (Change c in cmp.Changes.Where(c => c.IsSubstantive))
{
Console.WriteLine($"{c.Kind}: {c.Old.Text} -> {c.New.Text}");
if (c.OldValue is { } was && c.NewValue is { } now)
Console.WriteLine($" {c.Type}: {was.Canonical} -> {now.Canonical}");
}
Console.WriteLine($"complete: {cmp.Verification.Passed}");
// The output form follows the extension
cmp.SaveAs("redline.html");
cmp.SaveAs("changes.json");
Comparison again = ComparisonJson.Read(File.ReadAllBytes("changes.json"));
Console.WriteLine($"read back: {again.Changes.Length} changes, complete: {again.Verification.Passed}");
```
```text
Replace: 30 days -> 21 days
Duration: 30 d -> 21 d
complete: True
read back: 1 changes, complete: True
```
The change is typed: a duration, with both values resolved. `complete` is the completeness check every comparison runs: the old document plus the changes gives the new one, and the new one minus the changes gives the old. Reading the JSON back runs the check again, so an edited file fails it. See [The compare model](https://recursiveai.org/onediff/docs/compare-model/) and [Change semantics](https://recursiveai.org/onediff/docs/semantics/).
## Redline PDFs
PDF input and output are in `.Pdf`:
```shell
dotnet add package RecursiveAI.OneDiff.Pdf --version 1.0.1
```
With two versions of a digital PDF, `v1.pdf` and `v2.pdf` (here, the two text files above saved as PDF):
```csharp
using OneDiff.Documents;
using OneDiff.Pdf;
PdfRedline.Register(); // once at startup
// Highlights on v2.pdf's own pages, with the old text in the pop-ups
Redline.Create("v1.pdf", "v2.pdf", "markup.pdf");
// A rendered redline: a new, tagged PDF laid out from the comparison
Comparison cmp = Comparison.Of("v1.pdf", "v2.pdf");
cmp.SaveAs("redline.pdf", PdfRedline.Rendered);
cmp.SaveAs("side-by-side.html", RedlineForm.HtmlSideBySide);
foreach (Change c in cmp.Changes.Where(c => c.IsSubstantive))
Console.WriteLine($"{c.Kind}: {c.Old.Text} -> {c.New.Text}");
```
```text
Replace: 30 days -> 21 days
```
`markup.pdf` is `v2.pdf` with a highlight and its pop-up note; the page content is untouched. `redline.pdf` is a two-page tagged PDF: a summary of the changes by type, then the text with `30` struck through and `21` inserted. Every look the writers have is in [Samples and redline looks](https://recursiveai.org/onediff/docs/samples/).
A PDF with no text layer is refused rather than compared as empty:
```text
InvalidDataException: This PDF has no text layer, so it is probably a scan. Reference RecursiveAI.OneDiff.Ocr and call OcrRedline.Register() to read it by OCR.
```
## Scans
Scanned PDFs and images (PNG, JPEG, TIFF) are in `.Ocr`, which reads them with a local OCR engine:
```shell
dotnet add package RecursiveAI.OneDiff.Ocr --version 1.0.1
```
```csharp
using OneDiff.Documents;
using OneDiff.Ocr;
OcrRedline.Register(); // once at startup; reads scans and digital PDFs
Redline.Create("scan-v1.png", "scan-v2.png", "scan-markup.pdf");
foreach (Change c in Comparison.Of("scan-v1.png", "scan-v2.png").Changes)
Console.WriteLine($"{c.Kind}: {c.Old.Text} -> {c.New.Text}, " +
$"confidence {c.OcrConfidence:0.00}, possible OCR error: {c.PossibleOcrError}");
```
```text
Replace: 30 days -> 21 days, confidence 0.98, possible OCR error: False
```
A change whose words were read with a confidence below 0.95 (the default threshold) is flagged as a possible recognition error; the flag never hides a change. Scans are Latin-script only, and in the README’s words, “In browser WebAssembly, reading scans with `RecursiveAI.OneDiff.Ocr` fails with a `TypeLoadException` from the image library it uses (OneImage).” See [Scans and images](https://recursiveai.org/onediff/docs/ocr/).
## The onediff tool
```shell
dotnet tool install --global RecursiveAI.OneDiff.Tool --version 1.0.1
onediff diff v1.txt v2.txt
onediff compare v1.pdf v2.pdf -o markup.pdf
```
```text
--- v1.txt
+++ v2.txt
@@ -1,3 +1,3 @@
-1. Supply. The Supplier shall deliver the goods within 30 days of each order.
+1. Supply. The Supplier shall deliver the goods within 21 days of each order.
2. Payment. The Customer shall pay each invoice within 45 days of its date.
```
`onediff diff` exits 1 when the texts differ, as `diff` does. The other commands are `patch`, `merge`, `combine` (reviewers’ copies of one original) and `chain` (a series of versions); `onediff --help` lists each one’s options.
## Next
- [Overview](https://recursiveai.org/onediff/docs/overview/): what OneDiff is, the packages and the happy path.
- [Migrating from DiffPlex](https://recursiveai.org/onediff/docs/migrating-from-diffplex/) and [from WmlComparer](https://recursiveai.org/onediff/docs/migrating-from-wmlcomparer/).
- [Results](https://recursiveai.org/onediff/docs/results/): every measured result, including the rows that lose.
# OneDiff
**Text diff and document comparison for .NET.**
This project is unaffiliated with any other project named OneDiff, including the Python diffusion-model accelerator of that name.
OneDiff is a clean-room diff and comparison library for .NET, in two layers:
- **A text diff core** (`RecursiveAI.OneDiff`): Myers, patience and histogram diff over any sequence; line, word, character and grapheme tokenizers; semantic and efficiency cleanup; unified and diff-match-patch patches with fuzzy apply; three-way merge in git's conflict styles. It depends on nothing beyond the .NET base class library.
- **Document comparison** (`RecursiveAI.OneDiff.Documents` and the adapters): a compare model with source anchors, alignment that follows moves, splits and merges, typed changes with resolved values (`30 days → 60 days`), renumbering and renamed defined terms as single changes, combining reviewers' copies, and version chains. **PDFs** (digital, and scans through a local OCR engine) are read into the model; the changes are marked on the original pages with real annotations, written as a rendered redline PDF, as HTML (inline or side by side), or as a versioned JSON change list.
Every comparison is checked for completeness: old plus the changes gives new, and new minus the changes gives old. If a grouping cannot be inverted, the engine falls back to a coarser complete one and says so; strict mode throws instead. Differences that a setting hides (typography, page numbers, comments, …) are counted in a ledger, never dropped. Nothing needs a model: the deterministic engine keeps that promise on its own.
It targets `net10.0`, uses no native code, and is built to be NativeAOT-, trimming- and WebAssembly-friendly. The same inputs and settings give byte-identical output. Nothing touches the network.
## Install
```
dotnet add package RecursiveAI.OneDiff # the text core
dotnet add package RecursiveAI.OneDiff.Documents # document comparison, HTML and JSON
dotnet add package RecursiveAI.OneDiff.Pdf # PDF in, PDF out
dotnet add package RecursiveAI.OneDiff.Ocr # scans
dotnet tool install --global RecursiveAI.OneDiff.Tool # the `onediff` command
```
| Package | Contents |
|---|---|
| `RecursiveAI.OneDiff` | The text core. Depends on nothing beyond the base class library. |
| `RecursiveAI.OneDiff.Documents` | The comparison engine: compare model, alignment, grouping, typed changes, verification, combine and chains, the change report, JSON, HTML redlines. Depends on the core and `RecursiveAI.OneFont`. |
| `RecursiveAI.OneDiff.Pdf` | Reads digital PDFs; marks changes on the original pages; writes a rendered redline PDF. Depends on `.Documents`, `RecursiveAI.OnePdf` and `RecursiveAI.OneRender.Pdf`. |
| `RecursiveAI.OneDiff.Ocr` | Reads scanned PDFs and images through `RecursiveAI.OneOcr`, with each word's confidence; differences that may be recognition errors are flagged. |
| `RecursiveAI.OneDiff.Tool` | The `onediff` tool: `diff`, `patch`, `merge`, `compare`, `combine`, `chain`. |
Coming in later releases: Word documents in and tracked-changes DOCX out (`RecursiveAI.OneDiff.Word`, in this repository and not in the first release), spreadsheets, slides, and the OneNLP value recognizer (`RecursiveAI.OneDiff.Nlp`). Until then a Word file is refused with a message that says support is coming in a 1.x release and suggests comparing PDF exports.
## The happy path
Each line below is a runnable sample in [samples/OneDiff.Samples](https://github.com/recursive-ai-oss/onediff-csharp/blob/6443915c4136cc8c5a49fa2543322011665f309e/samples/OneDiff.Samples/Samples.cs).
```csharp
using OneDiff;
using OneDiff.Documents;
using OneDiff.Documents.Serialization;
using OneDiff.Merge;
using OneDiff.Pdf;
// Text: the words that changed, a unified patch, a three-way merge.
string marked = Diff.ToMarkdownInline(Diff.Words(oldText, newText));
string patch = Diff.Unified(oldText, newText);
TextMerge both = Diff.Merge(baseText, ours, theirs); // both.Text, both.HasConflicts
// PDF: a redline on the new document's own pages (highlights, with the old text in the pop-ups).
PdfRedline.Register(); // once at startup
Redline.Create("v1.pdf", "v2.pdf", "markup.pdf");
// PDF: a rendered, tagged redline PDF; or an HTML page with the two documents side by side.
var cmp = Comparison.Of("v1.pdf", "v2.pdf");
cmp.SaveAs("redline.pdf", PdfRedline.Rendered);
cmp.SaveAs("side-by-side.html", RedlineForm.HtmlSideBySide);
// The change list: walk what changed in substance, or save it as JSON and read it back.
foreach (var c in cmp.Changes.Where(c => c.IsSubstantive))
Console.WriteLine($"{c.Kind}: {c.Old.Text} -> {c.New.Text}");
Redline.Create("v1.pdf", "v2.pdf", "changes.json");
Comparison again = ComparisonJson.Read(File.ReadAllBytes("changes.json"));
```
Inputs are recognized by their content, and the output form follows the extension of the output path. The same from a shell: `onediff compare v1.pdf v2.pdf -o markup.pdf`. A PDF that has no text layer is refused with a message that names `RecursiveAI.OneDiff.Ocr` (call `OcrRedline.Register()` to read scans); it is never compared as an empty document. For streams that refuse synchronous I/O, such as an ASP.NET Core request body, use `Redline.CreateAsync`, `Comparison.OfAsync`, `SaveAsync` and `ComparisonJson.ReadAsync`.
## The low level
Every layer is public: the comparison is five stages over immutable values, and the alignment between the two documents is a value you can correct and run again.
```csharp
using OneDiff.Documents;
using OneDiff.Documents.Model; // CompareDocument
using OneDiff.Documents.Pipeline; // Alignment
CompareDocument a = CompareDocument.FromText(oldText, "old");
CompareDocument b = CompareDocument.FromText(newText, "new");
Alignment alignment = Stages.Align(a, b);
alignment = alignment.Pin(oldNodeId, newNodeId); // a reviewer's correction
Comparison result = Stages.Verify(Stages.Classify(Stages.Group(Stages.DiffPairs(alignment))));
```
## Documentation
Start at [docs/index.md](https://github.com/recursive-ai-oss/onediff-csharp/blob/6443915c4136cc8c5a49fa2543322011665f309e/docs/index.md). The pages that matter first:
- Samples, every redline look, and how to choose a form: [docs/samples/README.md](https://recursiveai.org/onediff/docs/samples/)
- Coming from DiffPlex: [docs/migrating-from-diffplex.md](https://recursiveai.org/onediff/docs/migrating-from-diffplex/); from `WmlComparer` or Docxodus: [docs/migrating-from-wmlcomparer.md](https://recursiveai.org/onediff/docs/migrating-from-wmlcomparer/)
- What a comparison is and how it is proved complete: [docs/compare-model.md](https://recursiveai.org/onediff/docs/compare-model/)
- Measured results, including the rows that are pending or lose: [docs/results.md](https://recursiveai.org/onediff/docs/results/). Nothing beyond that page is claimed. In short: Myers' edit length equals GNU diff's minimum on 9,483 corpus pairs, three-way merge equals `git merge-file` byte for byte on 2,599 real triples in all three conflict styles, and in the speed rows against DiffPlex and diff-match-patch every area's geometric-mean time ratio is below 1.0 (the worst single row is 1.13×, patch make against diff-match-patch on x64).
## Known issues
- In browser WebAssembly, reading scans with `RecursiveAI.OneDiff.Ocr` fails with a `TypeLoadException` from the image library it uses (OneImage). Scans compare normally on every native platform; text, document and digital-PDF comparison work in the browser.
## Building
```
dotnet build -c Release
dotnet test --solution OneDiff.slnx -c Release
```
Build output goes outside the checkout; set `ONEDIFF_ARTIFACTS` to choose where. See [docs/building.md](https://recursiveai.org/onediff/docs/building/).
## License
Dual-licensed under either of [MIT](https://github.com/recursive-ai-oss/onediff-csharp/tree/6443915c4136cc8c5a49fa2543322011665f309e/LICENSE-MIT) or [Apache-2.0](https://github.com/recursive-ai-oss/onediff-csharp/tree/6443915c4136cc8c5a49fa2543322011665f309e/LICENSE-APACHE), at your option. © Recursive AI, LLC.
# Samples
The runnable code samples (one task per method) are in [samples/OneDiff.Samples](https://github.com/recursive-ai-oss/onediff-csharp/blob/6443915c4136cc8c5a49fa2543322011665f309e/samples/OneDiff.Samples/Samples.cs). This page covers the rendered files and the choice of form.
Every file here is made from a short pair of documents written for the purpose (a list of clauses with an edit, an insertion, a deletion, a move and a formatting change), by the tests that check the writers. A change in the look shows up as a change to these files in review. To rewrite them after an intended change, run the tests with `ONEDIFF_UPDATE_SAMPLES=1`.
| Files | What they show |
|---|---|
| `-inline.html`, `-side-by-side.html` | The HTML redline in each preset: `blackline`, `sidebyside`, `word`, `developer`. |
| `-inline.pdf`, `-side-by-side.pdf` | The rendered redline PDF in the same presets and layouts: a new, tagged PDF laid out from the comparison (A4, landscape for side by side). |
| `markup-on-pages.pdf` | Original-page markup: two short PDFs compared, and the changes marked as annotations on the new PDF's pages (the pages themselves are untouched). |
## Happy path, one or two lines each
A PDF output needs `PdfRedline.Register()` once at startup. The output form follows the extension of the output path, and inputs are recognized by their content.
```csharp
// Text core: the edits between two strings, as a unified diff.
string patch = Diff.Unified(oldText, newText);
// Redline as a self-contained HTML page (inline), and as the versioned change list (JSON).
Redline.Create("v1.txt", "v2.txt", "redline.html");
Redline.Create("v1.txt", "v2.txt", "changes.json");
// Redline as a PDF. Any input kind renders to a blackline; a PDF as the new document is marked on its own pages.
PdfRedline.Register();
Redline.Create("v1.txt", "v2.txt", "redline.pdf"); // rendered blackline
Redline.Create("v1.pdf", "v2.pdf", "markup.pdf"); // highlights and notes on v2's pages
// Choose the form or the look yourself.
var cmp = Comparison.Of("v1.pdf", "v2.pdf");
cmp.SaveAs("redline.pdf", PdfRedline.Rendered); // rendered redline from PDF inputs
cmp.SaveAs("side-by-side.pdf", PdfRedline.RenderedSideBySide, RedlineStyle.SideBySide);
cmp.SaveAs("redline.html", RedlineForm.HtmlSideBySide);
```
# Migrating from DiffPlex
This page maps the calls in DiffPlex's README, checked against the public members of DiffPlex 1.9.0, to the `RecursiveAI.OneDiff` calls that do the same job. It is a mapping only: OneDiff does not copy DiffPlex's types or shapes, and there is no compatibility layer. Where the README does not say exactly what a DiffPlex option does, the row says "closest" and you should check the result on your own data. Rows marked *not provided* have no equivalent in the text core.
Everything below is in namespace `OneDiff` (and `OneDiff.Tokenization`, `OneDiff.Merge` where noted). All calls are static and take plain strings.
## The result: `DiffResult` → `TextDiff` and `EditScript`
`Diff.Lines`, `Diff.Words`, `Diff.Characters`, `Diff.Graphemes` and `Diff.Text` return a `TextDiff`: both strings, their tokens and an `EditScript`. The script is a list of `Edit` runs (`Equal`, `Delete`, `Insert`) whose indices count tokens of the old and new text. `TextDiff.OldSpan(edit)` and `NewSpan(edit)` give a run's text back. Replacements are a `Delete` followed by an `Insert`.
## `Differ` (`IDiffer`)
| DiffPlex | OneDiff | Notes |
|---|---|---|
| `CreateLineDiffs(old, new, ignoreWhitespace: false)` | `Diff.Lines(old, new)` | Line tokens keep their line terminator, so `a\r\n` and `a\n` are different lines. |
| `CreateLineDiffs(old, new, ignoreWhitespace: true)` | `Diff.LinesUsing(old, new, TokenComparer.IgnoreWhiteSpaceChanges)` or `TokenComparer.IgnoreAllWhiteSpace` | Closest. `IgnoreWhiteSpaceChanges` treats runs of white space as equal (and ignores a different line ending); `IgnoreAllWhiteSpace` drops white space altogether. |
| `CreateCharacterDiffs(old, new, ignoreWhitespace)` | `Diff.Characters(old, new)`; with a comparer, `Diff.TextUsing(old, new, comparer, TokenKind.Character)` | Characters are Unicode scalar values, so surrogate pairs stay whole. `Diff.Graphemes` compares user-perceived characters. |
| `CreateWordDiffs(old, new, ignoreWhitespace, separators)` | `Diff.Words(old, new)`; with a comparer, `Diff.WordsUsing(old, new, comparer)` | Word boundaries are fixed rules (see `TokenKind.Word`), not a separator list, so token boundaries differ from DiffPlex's. For your own separators, cut the text yourself and use `Diff.Sequences` (below). |
| `CreateCustomDiffs(old, new, ignoreWhiteSpace, chunker)` | `Diff.Sequences(oldChunks, newChunks, comparer: …)` | You split the text; the script indexes your chunks. |
| `CreateDiffs(old, new, ignoreWhiteSpace, ignoreCase, chunker)` | `Diff.TextUsing(old, new, TokenComparer.Create(ignoreCase, whiteSpace), kind)` | `TokenComparer.IgnoreCase`, `.IgnoreWhiteSpaceChanges`, `.IgnoreAllWhiteSpace` and `.Create(ignoreCase, WhiteSpaceHandling)` cover the combinations. The edit script still indexes the original tokens. |
Which algorithm runs is a parameter: `Diff.Lines(old, new, DiffAlgorithm.Patience)` (`Myers`, `Patience`, `Histogram`). To cap the work on untrusted text: `Diff.Lines(old, new, new DiffSettings { MaxWork = 100_000 }).Diagnostic.CostCapReached`. DiffPlex's `Differ` has no algorithm choice or cap to map these to.
### Chunkers (`IChunker`)
| DiffPlex | OneDiff |
|---|---|
| `LineChunker`, `LineEndingsPreservingChunker` | `TokenKind.Line` (line tokens include their terminator) |
| `CharacterChunker` | `TokenKind.Character` (or `TokenKind.Grapheme`) |
| `WordChunker` | `TokenKind.Word` |
| `DelimiterChunker`, `CustomFunctionChunker` | split yourself, then `Diff.Sequences` |
`Tokenizer.Tokenize(text, kind)` returns the token ranges if you want to look at them.
## `InlineDiffBuilder` (the README's console sample)
OneDiff's line type is `DiffRun`, not `DiffPiece`, so a file can import both `DiffPlex.DiffBuilder.Model` and `OneDiff` while you migrate it without an ambiguous reference.
The README builds an inline model with `InlineDiffBuilder.Diff(before, after)` and prints each line of `diff.Lines` with a `+`, `-` or blank prefix according to `line.Type`. `TextDiff.Lines` is the same view: one entry per line with its kind, text (without the line break) and line number in each text.
| DiffPlex | OneDiff |
|---|---|
| `DiffPaneModel.Lines` | `TextDiff.Lines` |
| `DiffPiece.Type` (`Unchanged`, `Deleted`, `Inserted`) | `DiffRun.Kind` (`EditKind.Equal`, `Delete`, `Insert`) |
| `DiffPiece.Text` | `DiffRun.Text` |
| `DiffPiece.Position` | `DiffRun.OldLine` / `DiffRun.NewLine` (both, one or the other, from 1; null on the side that lacks the line) |
| `DiffPaneModel.HasDifferences` | `!diff.Script.IsIdentical` |
```csharp
var sb = new StringBuilder();
foreach (DiffRun line in Diff.Lines(before, after).Lines)
{
string prefix = line.Kind switch { EditKind.Insert => "+ ", EditKind.Delete => "- ", _ => " " };
sb.Append(prefix).Append(line.Text).Append('\n');
}
```
`TextDiff.Pieces` gives the same runs without cutting them at line breaks (for a word diff, runs of words). `diff.Script`, `OldSpan` and `NewSpan` are still there when you want token indices. For a finished rendering instead of a loop: `Diff.ToTerminal(diff)` (ANSI colours, changed words highlighted, context lines and hunks), `Diff.ToMarkdown(diff)` (a fenced `diff` block) and `Diff.ToMarkdownInline(Diff.Words(a, b))` (``/`` inline).
## `SideBySideDiffBuilder` (`ISideBySideDiffBuilder`)
`Diff.SideBySide(old, new)` returns a `SideBySideDiff`: aligned `Rows`, each with a `Kind` (`Unchanged`, `Deleted`, `Inserted`, `Modified`) and a `Left` and `Right` cell. A cell has the line number, the text and `Parts`, which for a modified line are the word-level pieces (Equal and Delete on the left, Equal and Insert on the right), the way DiffPlex fills `SubPieces`.
| DiffPlex | OneDiff |
|---|---|
| `SideBySideDiffModel.OldText.Lines`, `.NewText.Lines` (padded with `Imaginary` pieces) | `SideBySideDiff.Rows`, with `Left` or `Right` null where DiffPlex pads |
| `DiffPiece.Type` `Modified` | `SideBySideRow.Kind == SideBySideKind.Modified` |
| `DiffPiece.SubPieces` | `SideBySideCell.Parts` |
```csharp
foreach (SideBySideRow row in Diff.SideBySide(before, after).Rows)
{
string left = row.Left?.Text ?? "", right = row.Right?.Text ?? "";
Console.WriteLine($"{row.Kind,-9} | {left,-30} | {right}");
}
```
With an already computed line diff (for example one made with a comparer): `Diff.ToSideBySide(diff)`.
## `UnidiffRenderer`
| DiffPlex 1.9.0 | OneDiff |
|---|---|
| `GenerateUnidiff(old, new, oldFileName, newFileName, ignoreWhitespace, ignoreCase, contextLines)` | `Diff.Unified(old, new, oldFileName, newFileName, contextLines)` |
| `Generate(old, new, oldFileName, newFileName, ignoreWhitespace, ignoreCase)` | `Diff.Unified(old, new, oldFileName, newFileName)` |
| `Generate(diffResult, oldFileName, newFileName)` | `Diff.Unified(old, new, …)` (the diff is computed inside; to keep a `TextDiff`, render it with `Diff.ToMarkdown` or `TerminalRenderer`) |
| options to ignore white space and case | not available on `Diff.Unified`; render a comparer-based diff with `TerminalRenderer` or `MarkdownRenderer` over `Diff.LinesUsing(…)` instead |
`Diff.Unified` has no timestamps in the header lines, and also takes `algorithm:` or, to cap the work, `DiffSettings`. Unified text parses back with `UnifiedPatch.Parse` and applies with `Diff.ApplyUnified`.
## `ThreeWayDiffer` (`IThreeWayDiffer`)
DiffPlex's `CreateMerge(baseText, oldText, newText, ignoreWhiteSpace, ignoreCase, chunker)` takes the two modified versions as "old text" and "new text"; they map to `ours` and `theirs`, in that order. Its result, `ThreeWayMergeResult`, has `IsSuccessful`, `MergedPieces`, `ConflictBlocks` and `DiffResult`.
| DiffPlex 1.9.0 | OneDiff |
|---|---|
| `CreateMerge(baseText, oldText, newText, …)` | `Diff.Merge(baseText, ours: oldText, theirs: newText)` returns a `TextMerge` |
| `result.IsSuccessful` | `!merge.HasConflicts` |
| `result.ConflictBlocks` | `merge.Conflicts`: each with the base, ours and theirs lines and line numbers; `merge.ConflictCount` for the count |
| `result.MergedPieces` | `merge.Text`, with conflicts marked in git's `merge`, `diff3` or `zdiff3` layout (`new MergeSettings { Style = … }`), or settled with `Resolution = ConflictResolution.Ours/Theirs/Union` |
| `CreateDiffs(…)` (three-way diff) | `merge.Regions`: the stretches of the merge, each with its base, ours and theirs line range |
| `ignoreWhiteSpace`, `ignoreCase`, `chunker` | `Diff.Merge(baseItems, ours, theirs, settings, comparer)` over items you cut yourself (for example lines) with the comparer you want; `ItemMerge.Items` holds the merged items |
```csharp
TextMerge merge = Diff.Merge(baseText, ours: oldText, theirs: newText);
if (merge.HasConflicts)
foreach (MergeConflict c in merge.Conflicts)
Console.WriteLine($"conflict at ours line {c.OursLine}: {c.OursText} / {c.TheirsText}");
else Console.WriteLine(merge.Text);
```
Changes on adjacent lines are a conflict, as in git; changes separated by an unchanged line merge cleanly.
## Beyond DiffPlex
The text core also has semantic and efficiency cleanup (`Diff.Semantic`, `Diff.Efficient`), diff-match-patch patch text (`Diff.PatchText`, `Diff.ApplyPatchText`) and unified patch apply with fuzz (`Diff.ApplyUnified`), and the `onediff diff | patch | merge` command line over the same calls. Document comparison lives in `RecursiveAI.OneDiff.Documents` and the adapter packages.
The snippets and mappings above that show behaviour are covered by tests in the repository (`MigrationPageTests`).
# Migrating from WmlComparer and Docxodus
This page maps the calls in the README of Docxodus 15.0.0 (the NuGet package page; it is the maintained descendant of Open-Xml-PowerTools' `WmlComparer`, which that README says was removed in v11.0.0) to the OneDiff calls that do the same job. Names on the Docxodus side are only the ones that README shows: `DocxCompare.Compare`, `WmlDocument`, `SaveAs`, `DocxDiff` with `GetRevisions()`, `GetEditScriptJson()`, `GetSemanticChanges()` and `GetSemanticChangesJson()`, the `PreAcceptInputRevisions` and `PreserveInputRevisions` options, N-way consolidate, `RevisionProcessor` and the `Redline` command-line tool. Members of the older `WmlComparer` settings and revision types are not mapped, because the current documentation does not describe them. It is a mapping only: OneDiff does not copy their types or shapes, and there is no compatibility layer. Where the documentation does not say what an option does exactly, the row says "closest" and you should check the result on your own documents. Rows marked *not provided* have no equivalent.
## What works at 1.0
Reading and writing Word files is in `RecursiveAI.OneDiff.Word`, which ships after 1.0 (it builds from this repository today). The 1.0 packages are `RecursiveAI.OneDiff`, `.Documents`, `.Pdf`, `.Ocr` and the `onediff` tool.
| Task | At 1.0, without `.Word` | With `.Word` |
|---|---|---|
| Compare two `.docx` files | **Not possible.** The input is recognized by its first bytes and the call throws `NotSupportedException`: "No document source is registered for this input, which looks like an Office Open XML or other zip-based document. Support for Office documents (DOCX, XLSX and PPTX) is coming in a 1.x release. Meanwhile, export the documents to PDF and compare the PDFs (with RecursiveAI.OneDiff.Pdf)." | `WordRedline.Register()` once, then `Comparison.Of("v1.docx", "v2.docx")` |
| Write a `.docx` with tracked changes | Not possible: asking for a `.docx` output throws `NotSupportedException`: "No output form is registered for '.docx'. Support for DOCX output is coming in a 1.x release. Meanwhile, export the documents to PDF and compare the PDFs (with RecursiveAI.OneDiff.Pdf)." | `comparison.SaveAs("redline.docx")` |
| Compare `.docx` against a PDF, write HTML, JSON or a PDF redline | Not possible (the `.docx` side cannot be read). | Works: `.Word` and `.Pdf` registered together. |
| Compare PDFs, text or scans; HTML, JSON, rendered-redline and on-page-markup outputs | Works. | Works. |
So a team that needs Word-in, Word-out redlines today uses the `.Word` package from this repository; nothing in the 1.0 set reads a `.docx`.
## The one-liner and the object model
`DocxCompare.Compare(a, b)` returns a redlined document. The OneDiff equivalents split the same job in two, so that you can keep and inspect the comparison before choosing an output.
| WmlComparer / Docxodus | OneDiff | Notes |
|---|---|---|
| `new WmlDocument("v1.docx")` | A path, or `DocumentInput.FromBytes(bytes, name)` / `FromStream` / `FromString` | Inputs are sniffed by content, never by extension. |
| `var redline = DocxCompare.Compare(new WmlDocument("v1.docx"), new WmlDocument("v2.docx")); redline.SaveAs("redline.docx");` | `Redline.Create("v1.docx", "v2.docx", "redline.docx")` | The output form follows the extension of the output path. Needs `WordRedline.Register()` once. |
| the same, keeping the result | `var cmp = Comparison.Of("v1.docx", "v2.docx"); cmp.SaveAs("redline.docx");` | `Comparison` is the verified change list; any number of outputs can be written from it. `cmp.ToBytes(form)` gives bytes instead of a file. |
| `DocxCompare.Compare` compares the *accepted* view of each input (`DocxDiff` alone compares the raw markup unless `PreAcceptInputRevisions` or `PreserveInputRevisions` is set) | The default: `WordSourceOptions.Revisions = WordRevisionMode.Accepted` | `WordRevisionMode.AsOriginal` reads the documents as they were before their tracked changes; `Refuse` throws if a document holds any. Register a configured source with `WordRedline.Register(new WordSourceOptions { Revisions = … })`. |
| the redlined document opens in Word with real `w:ins` / `w:del` / moves | `DocxRedline`, built on the new document by default (`BuildOn = WordBuildOn.Old` builds on the old one) | Accept-all gives the new document and reject-all the old, over the compare model; what a revision cannot express comes back in `DocxRedlineResult.NotCarried` from `new DocxRedline().Create(cmp, stream)`. |
## Settings
The Docxodus README documents no comparison settings by name beyond the two revision options above, so this table maps OneDiff's own settings to the job, not to a member.
| What you want | OneDiff | Notes |
|---|---|---|
| the revision author | `cmp.SaveAs("redline.docx", new DocxRedline { Author = "Redline" })` | Default author `OneDiff`. |
| a revision date | `new DocxRedline { Date = someDate }` | No date is written unless you set one, so equal inputs give byte-identical files. |
| how finely blocks are matched | `CompareSettings.MatchThreshold` (how similar two paragraphs must be to count as the same one, default 0.5), `SplitMergeThreshold` and `MoveThreshold` | These govern how blocks are matched, not how finely words are compared. |
| what to show and hide | `CompareSettings.Legal` (default), `Strict`, `TextOnly`, `Hidden` categories, `CollapseCascades`, `TypedChanges`, `DetectMoves`, `CostCap`, `ThrowOnFailure` | See [compare-model.md](https://recursiveai.org/onediff/docs/compare-model/) and [semantics.md](https://recursiveai.org/onediff/docs/semantics/). `Strict` ignores nothing and throws instead of falling back. |
## Reading the revisions
| Docxodus (`DocxDiff`) | OneDiff | Notes |
|---|---|---|
| `GetRevisions()`, typed revisions | `cmp.Changes`, an `ImmutableArray` | OneDiff reads the changes from the comparison, not back out of the output file. |
| an inserted, deleted or moved revision | `change.Kind`: `Insert`, `Delete`, `Replace`, `Move`, `Split`, `Merge`, `Format`, `Attribute` | A replacement is one change with both sides, not a delete plus an insert. |
| the revision's text | `change.Old.Text` and `change.New.Text` | Every change carries both sides and both anchors. |
| the stable anchors on a revision | `change.Old.Anchor` and `change.New.Anchor` | Anchors name the source (a part and path, a PDF quad set, an OCR word). |
| a revision's author | *Not applicable* to a single comparison. `Redline.Combine` / `Combination` attribute each change to the reviewer's copy it came from. | |
| `GetEditScriptJson()` | `Redline.Create(a, b, "changes.json")` or `ComparisonJson.Write(cmp)`; `ComparisonJson.Read(bytes)` reads it back and re-checks it | A versioned schema, [schema/comparison-v1.json](https://github.com/recursive-ai-oss/onediff-csharp/blob/6443915c4136cc8c5a49fa2543322011665f309e/docs/schema/comparison-v1.json). |
| `GetSemanticChanges()` / `GetSemanticChangesJson()` | `change.Type`, `change.OldValue` / `NewValue`, `change.IsSubstantive`, and `cmp.Ledger` | Typed values (`30 d → 60 d`), the substantive filter and the ledger of differences hidden by settings. |
| `RevisionProcessor` (accept and reject revisions) | *Not provided.* OneDiff writes redlines; accepting and rejecting is OneDocument's job (`RevisionAuthor`), which OneDiff uses to verify its own output. | |
```csharp
using OneDiff.Documents;
using OneDiff.Word;
WordRedline.Register(); // once at startup
var cmp = Comparison.Of("v1.docx", "v2.docx");
cmp.SaveAs("redline.docx", new DocxRedline { Author = "Redline" });
foreach (var change in cmp.Changes.Where(c => c.IsSubstantive))
Console.WriteLine($"{change.Kind}: {change.Old.Text} -> {change.New.Text}");
```
## Consolidating reviewers' copies
The Docxodus README describes an N-way consolidate against one base. The OneDiff call is `Redline.Combine("original.docx", ["alice.docx", "bob.docx"], "combined.html")` (or `Combination.Of`), which attributes each change to its reviewer and flags conflicting edits without picking a winner. The output today is the change report (`.html`) or the JSON form; a DOCX with one revision author per reviewer comes with a later `.Word` release. See [combine.md](https://recursiveai.org/onediff/docs/combine/).
## Not covered here
Rendering, editing sessions, markdown projection, content-control helpers and the other parts of the Docxodus toolkit are not comparison, and OneDiff has no counterpart. The npm, Python and CLI surfaces of those packages have no OneDiff counterpart either; the OneDiff command line is `onediff compare v1.pdf v2.pdf -o markup.pdf` for the 1.0 formats.
The snippets and mappings above that show behaviour are covered by tests in the repository (`MigrationPageTests` in the `.Word` tests, and the unsupported-input message in the samples tests).
# Diff algorithms
Behaviour of `MyersDiff`, `PatienceDiff` and `HistogramDiff`. All three take two `ReadOnlySpan` of item ids (equal ids are equal items) and return a canonical `EditScript`: equal runs, and between them a deletion followed by an insertion.
## Myers
Myers 1986, "An O(ND) Difference Algorithm and Its Variations": the greedy furthest-reaching search (section 3) with the linear-space middle-snake refinement (section 4b). The script has the fewest deleted plus inserted items possible (`D`), unless the work cap below is reached.
- A common prefix and suffix are removed first; they belong to some minimal script.
- Items that occur on one side only are set aside before the search (they cannot be in a longest common subsequence) and the search runs on what is left. Minimality is unaffected. This is skipped when the ids are negative or too sparse to count in an array.
- The search finds the middle snake of the (sub)problem, then solves the two halves, depth `O(log D)`. Memory is linear in the input.
- Tie-breaking: among minimal scripts, the one whose forward and reverse searches meet first. It depends only on the input, so repeated runs give the same script. Where several minimal scripts exist this one is not chosen for readability; cleanup does that.
## Work cap
Every search counts work in edit-graph steps: one per diagonal visited plus one per item matched while following a snake (Myers), and for the anchor-based algorithms one per item scanned plus one per item compared while growing a match.
- The default cap is 2^31 steps, far above what ordinary inputs need (a pair differing by D edits costs on the order of D² steps).
- `Compute(old, new, maxWork, out diagnostic)` takes an explicit cap. `long.MaxValue` means unbounded. `DiffDiagnostic.CostCapReached` reports whether it was hit and `Work` how much was spent.
- When the cap is reached, parts already solved stay as they are and every part not yet searched becomes one deletion followed by one insertion. The script is valid but, for Myers, may be longer than the minimum. Patience and histogram are not minimal anyway.
- Cancellation is checked once per edit count `d` in Myers and once per segment in the anchor-based algorithms.
## Patience
From the published write-ups of Bram Cohen's patience diff. In each pair of ranges (after trimming a common prefix and suffix):
1. Items that occur exactly once in each range are candidates, taken in old order.
2. Their longest subsequence that is increasing in both ranges (patience sorting over the new positions) becomes the anchors.
3. The ranges between anchors are processed the same way.
4. A range with no candidate is finished with Myers.
## Histogram
From the published descriptions of histogram diff. In each pair of ranges (after trimming):
1. Count how often each item occurs in the old range.
2. For each item of the new range that occurs in the old range at most 64 times, take each old occurrence as a starting point, grow the match in both directions while items are equal, and score it by its rarest item (lowest old-range count). A lower score wins; on equal scores the longer match; then the earlier one (earlier in the new range, then in the old).
3. After examining a starting point, scanning resumes after the furthest end of the matches grown from it.
4. The best match is the anchor; the ranges before and after it are processed the same way.
5. If the ranges share items but every shared item occurs more than 64 times in the old range, the range is finished with Myers. If they share nothing it is one deletion plus one insertion.
The limit of 64 is a fixed constant of this implementation.
## Lines and the final newline
Line tokens keep their terminator, so a last line with and without a newline are different items. Tokenizers decide where a line ends; the corpus comparison against GNU `diff` used `\n` only as the line end, as GNU does.
## Settings on the one-liners
`DiffSettings` (`Algorithm`, `MaxWork`) is taken by `Diff.Text`, `Lines`, `Words`, `Characters`, `Graphemes`, `TextUsing`, `LinesUsing`, `WordsUsing`, `Semantic`, `Efficient` (the cap applies to the diff that is cleaned up; the cleanup passes run once over its edits), `Unified` and `Sequences` (which also reports the `DiffDiagnostic`). `TextDiff.Diagnostic` says whether the cap ended the search early (`CostCapReached`) and the work spent (the items of the shared head and tail count too; a diff with nothing to compare, such as an empty side, reports zero); it is all zero for a diff built with `TextDiff.Create`, and cleanup keeps it. A capped line diff is `Diff.Lines(a, b, new DiffSettings { MaxWork = 100_000 })`. Merges take the same two knobs in `MergeSettings`.
# Patches
How OneDiff reads, writes and applies unified diffs and diff-match-patch patch text. The code is in `src/OneDiff/Patching`; every rule below is checked by the gates in [measurement.md](https://recursiveai.org/onediff/docs/measurement/).
## Unified diff
The format is the GNU unified format (GNU diffutils manual, "Unified Format" and "Detailed Unified").
**Lines.** Text is cut at `\n` only. Each line keeps its terminator, so `\r\n` files round-trip byte for byte and a lone `\r` is ordinary content. A last line without a terminator differs from the same line with one, which is what makes `\ No newline at end of file` come out right.
**Making.** Changes whose gap of unchanged lines is at most twice the context length share a hunk. The default context is three lines; zero is allowed. A side with no lines in a hunk names the line before it (`-0,0`, `+5,0`). A count of one is left out (`-3`). Names on the `---`/`+++` lines are the caller's; timestamps appear only when given. Identical inputs give the empty string. A name containing a control character, quote or backslash is written in git's quoted form.
**Parsing.**
- Text before the first `---`/`+++` pair and between files that is not a header is skipped, as the patch manual says. Git's extended header lines (`diff --git`, `index`, mode, rename and similarity lines) directly before a file are kept verbatim on that file. Binary and rename-only sections are not supported and are skipped.
- A hunk header is `@@ -a[,b] +c[,d] @@` followed by an optional section heading. Numbers above about a billion are rejected. A hunk takes exactly the lines its counts announce; fewer is a truncated patch, more is an unexpected line. An empty line inside a hunk is an empty context line. `\ No newline at end of file` removes the terminator from the line before it.
- Trailing carriage returns on header lines are dropped. A `@@` line outside a file's hunks, or a `---` line without `+++`, is an error.
- Input over 2^28 characters is refused. Memory use is proportional to the input; no allocation depends on a number in the input.
**Applying.** Hunks are matched against the text line by line, exactly. For each hunk:
1. It is looked for where its header says, shifted by the offset the previous hunk was found at, then at growing distance, later lines before earlier ones at the same distance.
2. If it does not match, context lines are ignored. *Fuzz n* leaves at most (longest context − n) lines at each end, so a hunk whose contexts differ (because it sits at the edge of the file) loses lines from its longer side first. At most two levels by default.
3. A hunk with less leading than trailing context (after fuzz) must match at the top of the file; the mirror case at the end.
4. A hunk may not match where its ignored leading context would fall before the first line. Ignored trailing context may run past the last line.
5. A hunk never matches before the lines earlier hunks used.
6. A hunk that matches nowhere is rejected, with the reason `ContextMismatch`, or `AlreadyApplied` when its new lines are found where its old lines are not. Applying never throws for a conflict; the rejected hunks are returned as a patch.
Rules 2–4 are not in the patch manual. They were settled by comparing results with GNU patch 2.8 (run as `patch -f`, which never asks and never assumes a reversed patch) on thousands of generated drifted files (`tests/OneDiff.Tests/Patches/GnuPatchAgreementTests.cs`).
**Reverse.** `Reverse` swaps the sides of every hunk; applying a reversed patch to the new text gives the old.
## diff-match-patch patch text
The format and the matching are those of diff-match-patch's published wiki ("Unidiff" and "API") and of Wu and Manber, "Fast text searching allowing errors" (1992).
**Format.** Each patch is `@@ -s1[,l1] +s2[,l2] @@` and one line per diff: a space, `-` or `+` followed by the text, URI-encoded as UTF-8 with the space left as it is. A length of one is left out; with a length of zero the start is written as it is, otherwise it is one-based. The context is rolling: the starts of a patch are those of the text after the earlier patches were applied. A lone surrogate is written as the three bytes its code unit would take, and read back the same way. Reading takes the starts from the headers and recomputes the lengths.
**Offsets.** Starts count UTF-16 code units by default (the JavaScript, Java and C# ports). The Python package counts code points; `DmpOffsetUnit.CodePoint` makes `Make` and `Apply` use them, which is needed to exchange patches with it for text outside the Basic Multilingual Plane.
**Making.** The character diff trims common ends, compares long texts line by line first, and never splits a surrogate pair. No readability cleanup is applied. Context grows by the margin (default 4) until the patch's old text is unique in the text, up to the match limit, plus one more margin.
**Applying.** The text is padded at both ends, patches longer than `MatchMaxBits` (default 32) are split, and each patch is placed by `Match` near where it expects to be, shifted by the drift of the patches before it. A patch whose old text is longer than the limit is located by its first and last stretch. When the found text differs from the expected text, the patch's edits are mapped through a diff between the two; a long deletion over text that differs by more than `PatchDeleteThreshold` is refused. Per patch the result says applied, not found, or too different. Cost is the text length times the number of patches.
**Match.** An exact hit at the expected place wins; otherwise Bitap scores each candidate as errors / pattern length + distance / `MatchDistance` and takes the best one under `MatchThreshold` (defaults 0.5, 1000).
## Limits and errors
Both parsers return a typed error (`PatchParseError`: kind, line, offset) through `TryParse`/`TryFromText`, or throw `PatchFormatException` from `Parse`/`FromText`. Nothing else is thrown for bad patch text. The parsers and appliers are fuzzed (`fuzz/OneDiff.Fuzz`).
## Options on the one-liners
`Diff.ApplyUnified(text, patch, options)` takes `UnifiedApplyOptions` (fuzz, offset limit, reverse). `Diff.ApplyPatchText(text, patchText, patcher, cancellationToken)` and `Diff.PatchText(old, new, patcher, cancellationToken)` take the `DmpPatcher` whose thresholds and margin apply; without one the defaults are used. Where a hunk or patch was not placed, `HunkResult.Line` and `DmpPatchResult.Location` are `null`. `DmpPatcher.TryMatch` returns false for no match and for a pattern longer than `MatchMaxBits`.
# Three-way merge
`ThreeWayMerge` (and `Diff.Merge`) merge a common ancestor (base) with two descendants (ours, theirs) over any sequence; the text form works on lines. The structure follows Khanna, Kuber and Pierce, "A Formal Investigation of Diff3" (FSTTCS 2007); the conflict layouts follow git's documentation for `git merge-file` and `git merge` (conflict styles). Where those leave behaviour open, it was settled by running `git merge-file` 2.51.2 on crafted inputs and the 2,599 triples of the merge corpus, and is marked *observed* below.
## Lines
A line ends at `\n` and keeps its ending. A lone `\r` is not a line break. Two lines are equal only if their endings are too (`a` and `a\n` differ, `a\r\n` and `a\n` differ). The last line may have no ending.
## Aligning
Each side is aligned with the base, and the alignment is turned into hunks: maximal runs of changed items, each a range of the base and the range of the side that replaces it. With the default algorithm (Myers) the merge uses its own alignment, not the shortest-script one of `Diff`, because several equally short scripts exist and a merge is only as good as the extents of its hunks. Patience and histogram use the library's own alignments. The rules below were each found by comparing with the output of `git diff` and `git merge-file` 2.51.2 on crafted inputs (every pair over three lines up to length 4, 20,000 random pairs, 60,000 longer pairs with a frequent line) and then confirmed on the 2,599 merge triples. All are *observed in output of git 2.51.2*.
1. **Trimming.** The common start and end of the two sequences are matched first and take no part in anything below.
2. **Items that cannot match.** An item with no copy in the other sequence is changed. The counts are over the whole other sequence, before trimming.
3. **Items with too many copies.** An item is *frequent* when the other sequence holds at least `limit(N)` copies of it, N being the length of the sequence the item is in. There is no limit under 8 items; the limit is 4 for N from 8 to 15, 8 for 16 to 63, 16 for 64 to 255, 32 for 256 to 1023, 64 from 1024 (a power of two near the square root of N).
4. **Which frequent items stay.** Inside the trimmed range, look left and right from a frequent item over items that have no copy (counted as D, left and right) and over other frequent items (counted in P, which starts at 2), stopping at the first ordinary item. The item stays in the search when either D is zero, or when D left plus D right is at most three times P; otherwise it is changed. The looks are static: another frequent item being dropped does not change them.
5. **The search.** Myers 1986 §4b on what is left (forward and reverse searches meeting at a middle snake, recursing on both halves), except that the forward diagonals of each step are visited from k = d down to k = -d; the reverse ones go up. For base `aab` against `ba` this matches the `b`, where visiting in the paper's order matches an `a`.
6. **Sliding.** A run of changed items that could sit in several places is placed by sliding it up as far as it goes (joining runs it meets) and then down as far as it goes, noting each place where the other sequence has a run lined up with it; if sliding down joins the next run, the joined run starts again (up, then down with fresh memory); it settles at the last lined-up place, or at the lowest place if there is none. The first sequence is settled against the other one as searched; the second against the first as settled.
The result is not always the shortest script. Items skipped by rules 2 to 4 never match, so the hunks can be longer than the minimum.
## Walking the hunks
Both hunk lists are walked together in base order.
- A hunk that has no counterpart touching it is **one-sided**: ours-only or theirs-only; the merge takes that side.
- An ours hunk and a theirs hunk with the same base range and the same new items are one **false conflict** (`BothSame`): taken once.
- Anything else is a **conflict**. Observed: hunks that merely touch (one ends where the other starts, or both insert at one point) conflict. A conflict covers every hunk of either side that overlaps or touches it, repeatedly, so its base range is the union and its ours and theirs ranges are what each side holds there.
- Observed: a conflict whose two sides end up equal after different splits into hunks is still a conflict in the diff3 and zdiff3 styles. In the merge style, narrowing (below) finds nothing left to mark and it disappears.
## Conflict styles
- **merge.** Each conflict is narrowed by aligning its ours side with its theirs side: shared items stay out and each differing stretch is a conflict of its own. Then neighbouring conflicts are joined (observed): two conflicts with only shared, unchanged items between them become one when the gap is at most three items, or when no item of the gap holds an ASCII letter or digit. A gap that holds a one-sided change does not qualify; a false conflict settled earlier counts as shared text. Layout: ours section, `=======`, theirs section.
- **diff3.** No narrowing and no joining. Layout: ours, `|||||||` with the base, `=======`, theirs.
- **zdiff3.** diff3, but items that begin both sides identically move out before the conflict and items that end both sides identically move out after it (observed: the start is taken first, the end from what is left). The base section stays whole. A conflict can end up with empty ours and theirs sections.
Markers are `<<<<<<<`, `|||||||`, `=======`, `>>>>>>>` (marker size adjustable) followed by a space and the label when there is one. A section whose last line has no ending gets one inside a conflict, so the next marker starts a line.
## Line endings in markers
Observed: marker lines (and the ending added to an unterminated last line) use CR LF exactly when, for the conflict: the base line before it (or the first base line when it starts the file) ends in CR LF, and so does the corresponding line of ours and of theirs where there is one. An empty base never asks for CR LF. For a conflict that was narrowed or joined, the base line is the one before where the whole conflict began.
## Resolutions
`Ours`, `Theirs` and `Union` settle conflicts after narrowing, joining and trimming (so `Union` on a narrowed conflict gives each narrowed piece's two sides, not the whole conflict twice). `Union` writes ours first and adds a line ending after an unterminated last line of ours. The conflict count is then zero.
## Structured result
`Regions` tile the base, ours and theirs: each region holds the three ranges. Narrowed or trimmed conflicts share the conflict's base range: the first conflicting piece carries all of it, and shared items around the pieces are `BothSame` regions with an empty base range.
## Agreement with git
On the 2,599 real merge triples of the corpus, the text produced equals the output of `git merge-file` 2.51.2 byte for byte in the merge, diff3 and zdiff3 styles, with git choosing its own alignment. The base-to-side alignments themselves still differ from `git diff` on a few corpus pairs (26 of 5,198); none of them changes a merge. Very large inputs may differ from git where git gives up searching for the shortest script, which is not modelled here; the cost cap below is OneDiff's own.
## Cost cap
The alignments of one merge share a budget, `MergeSettings.MaxWork` (2^31 by default, the default of the diff algorithms; zero or more). Work is counted as in the Myers search: one unit per diagonal visited, per item compared along a diagonal, and per item slid. Items that cannot match and the frequent-item rule (steps 2 to 4 above) are linear and not counted.
When the budget runs out:
- the search stops, and every stretch it had not solved is reported as changed on both sides (the same coarsening Myers uses: unsearched parts become delete and insert);
- sliding (step 6) stops where it is; each slide step keeps the alignment valid;
- the merge carries on with the hunks it has. Hunks that are longer than needed only make conflicts larger, or turn a clean merge into a conflict. A change of either side is never dropped: it is applied or inside a conflict, and the regions still tile all three inputs;
- `TextMerge.Diagnostic` and `ItemMerge.Diagnostic` have `CostCapReached` set and `Work` holds the work spent, a little over the cap at most (the cap is checked once per search round, so the overshoot is bounded by the size of the inputs).
A merge that stays within the budget is byte-for-byte what it would be without a cap. With the default cap this never happens on the merge corpus. The patience and histogram alignments receive what is left of the budget and report the same way.
## Conflicts and merged items
`TextMerge.Conflicts` lists the conflict regions in order as `MergeConflict`s: index, region, the 1-based line each version starts on, and the three versions' lines (line endings included). It lists the places the sides disagreed whether or not `MergeSettings.Resolution` settled them in `Text`, so with a resolution `ConflictCount` is zero while `Conflicts` still shows what was settled. `Diff.Merge` returns an `ItemMerge`: `Items` is the merged sequence with conflicts settled as `Resolution` says (null when the resolution is `None` and there are conflicts, because there is no single sequence then), and `Resolve(how)` settles them another way (Ours, Theirs, or Union with ours first).
# Text output: terminal and Markdown
Renderers over a line-token `TextDiff`. Output is a pure function of the diff and the renderer's settings: the same input gives the same bytes on every platform. Every output line ends in `\n`, whatever the input's line endings.
## Hunks (both formats)
- Lines are the line tokens of the diff. A line's terminator (`\n`, `\r\n` or a lone `\r`) is not shown.
- A change is surrounded by `ContextLines` equal lines (default 3). Two changes whose gap is at most twice that share one hunk, so no line appears twice. With 0 context every change is its own hunk.
- A hunk starts with `@@ -a,b +c,d @@`: one-based first line and line count on each side. A count of 1 is written without `,1`. An empty range names the line before it (`-0,0` at the start of the text).
- Lines are prefixed `' '` (context), `-` (only in the old text) and `+` (only in the new text). Deletions of a changed block come before its insertions.
- A shown line that had no terminator is followed by `\ No newline at end of file`.
- When `OldName` or `NewName` is set, `--- old` and `+++ new` precede the first hunk.
- An identical pair renders as the empty string.
## Terminal
- Colour (default on): hunk headers cyan (`ESC[36m`), file headers bold, deletions red (`ESC[31m`), insertions green (`ESC[32m`), the no-newline note dim; each styled line ends with `ESC[0m`. Colour off writes the same text without any escape sequence.
- Word level (colour on only): in a changed block that has both deleted and inserted lines, the block's old and new lines are diffed word by word and the changed words are wrapped in reverse video (`ESC[7m` … `ESC[27m`). Skipped when either side of the block exceeds 8192 chars, or when under 30% of the longer side (counting non-white-space chars) is shared — those lines are rewrites and marking everything is noise.
- Control characters in the text (below U+0020 except tab, U+007F, U+0080–U+009F) are replaced by a visible picture (U+2400 block, U+2421, U+FFFD) so compared text cannot drive the terminal.
## Markdown
- Line diff: the hunks above in a fenced block opened with `diff`. The fence is three backticks, or one more than the longest backtick run in the content.
- Inline diff (any token kind): the new text, each deletion wrapped in `` and each insertion in ``. A run that spans line breaks is wrapped per line, with the breaks outside the tags. `&` and `<` are escaped as `&` and `<`; other Markdown is left as written. ``/`` is used rather than `~~`/`**` because those collide with markup already in the text and cannot be escaped reliably.
## Reading views
Three views read a `TextDiff` without token arithmetic.
- `TextDiff.Pieces`: one `DiffRun(Kind, OldLine, NewLine, Text)` per edit run, with the run's text as it stands (line breaks included) and the 1-based line each side starts on (`null` on the side that lacks the run). Works for every token kind.
- `TextDiff.Lines`: the pieces cut at line breaks (`\n`, `\r\n`, a lone `\r`), the breaks dropped. For a line diff that is one entry per line; for a word or character diff a changed line shows as several entries with the same line number. A side's line number advances when a piece starts a new line on that side, so an unterminated last line is one line.
- `Diff.SideBySide(old, new)` / `SideBySideDiff.From(lineDiff)`: aligned rows. A run of deleted lines followed by a run of inserted lines is paired line by line into `Modified` rows (the longer run's remainder is `Deleted` or `Inserted` rows with the other cell null). A modified row's cells hold word-level `Parts` from `Diff.Words` plus semantic cleanup of the two lines: Equal and Delete on the left, Equal and Insert on the right. Needs a diff made with line tokens.
# The compare model, the stages and the completeness guarantee
This note describes the contracts of `RecursiveAI.OneDiff.Documents`: what a compared document is, how a comparison is built from five stages, and how every comparison is proved complete. Sources, alignment, in-pair diff, grouping, writers and models plug in through the types named here.
## 1. The guarantee
For every comparison:
1. **Every difference is accounted for.** Each difference between the two compare models is either a *change* or an entry in the *ledger* (hidden by a setting: category, count, locations). Content outside the model is reported "differs, not itemized" from a content hash.
2. **Invertible.** Old with the changes applied is new; new with the changes removed is old. This is checked by replaying the changes' edits over the compared content in both directions, not by trusting the stage that made them.
3. **Both sides, both anchors.** Every change carries the old and new text it concerns and an anchor for each side that resolves back to the source.
4. **Grouping is display.** Changes are atomic data. A `ChangeGroup` lists change ids and carries no data, so removing or reshaping groups never loses or alters a change.
`Stages.Verify` checks all four on every comparison. On failure it falls back, step by step, to a coarser grouping that is still complete, and records why in the diagnostics; with `CompareSettings.ThrowOnFailure` it throws `ComparisonVerificationException` instead. Without any model the deterministic stages keep every promise; a model may reorder, group and score but cannot hide a change, because whatever it produces is verified like everything else.
## 2. The compare model
A `CompareDocument` is an immutable forest of `Node`s in document (pre-order) order. `Nodes[i].Id == i`, and a parent always has a smaller id than its children, so a node's id is its position. A document also has a display `Name`, the `SourceHash` of the input bytes, a `SourceFormat`, and `Opaque` parts.
A `Node` has:
| Member | Meaning |
|---|---|
| `Kind` | `Section`, `Paragraph`, `ListItem`, `Table`, `TableRow`, `TableCell`, `Footnote`, `Endnote`, `Header`, `Footer`, `Comment`, `Field`, `Image`, `TextBox`, `ContentControl`, `Property` |
| `Text` | normalized text the node's own content is compared on (empty for pure containers); never contains U+001E |
| `Runs` | character formatting over `Text`: sorted, non-overlapping, adjacent equal runs merged, never an empty format |
| `Attributes` | block-level attributes as a sorted string map (paragraph style, list label and level, hashes, field code, property name) |
| `Anchor`, `Segments` | where the node came from; segments anchor pieces of the text (a line, a word) |
| `Folds` | what normalization changed (below) |
Conventions for the flowing kind:
- **List items** carry their resolved label in `list.label` (and `list.level`, `list.format`), so a renumbering is an attribute change, not a text change.
- **Fields** are `Field` nodes under their paragraph: the code is `field.code`, the result is the node's text. A source that wants the field to appear in the paragraph's text puts U+FFFC there; the child node holds the content.
- **Hyperlinks** are the `run.link` attribute of the linked text.
- **Images** are `Image` nodes with `hash.content` and, when a source has one, `hash.perceptual`.
- **Comments** and **document properties** are nodes (`Comment`, with block children; `Property`, named by `prop.name`, the value is the text). They can be hidden into the ledger.
- Attribute keys have a prefix that says which hiding category they belong to: `run.` (character formatting), `para.`, `list.`, `section.`, `field.`. Other prefixes (`hash.`, `table.`, `prop.`, …) are content or structure and are never hidden.
**Slides and grids** are not read by the 1.0 packages. The model is shaped for them (`DocumentKind`, `Anchor.ForCell`, attributes for geometry, R1C1 formulas and number formats) so that they can arrive as sources without a change to the stages. `Stages.Align` refuses to compare documents of different kinds.
### Anchors
An `Anchor` is a source location the engine copies but never interprets. The anchor kinds are `Node` (an opaque adapter reference, for example a hub node), `PdfQuads` (glyph quadrilaterals with their pages), `OcrWords` (word quadrilaterals plus the lowest confidence), `Cell` (sheet and A1 address) and `TextSpan` (a character range of a named text part). `.Documents` references no source library; adapters choose the `Reference` string. Anchors are the contract between sources and writers: a source attaches them, the engine copies them onto changes, a writer resolves them.
`Anchor.Union` combines neighbouring anchors (hull of text spans, concatenated quads with the lowest OCR confidence, otherwise the first). A change side's anchor is the union of the anchors of the node segments its range overlaps, or the node's anchor when it has no segments. Verification recomputes that and compares.
### Normalization and the ledger
A normalizer (`ITextNormalizer`) looks at one position of raw text and may replace the characters there. `TextNormalization.Normalize` runs them and returns the normalized text plus a `NormalizationFold` per replacement: its ledger category, its place in the normalized text, and the original characters. A node keeps both, so `Node.RawText` always reconstructs the source text. The built-in `TypographicNormalizer` folds quotes, the dash family and runs of horizontal whitespace; PDF sources add `LineBreaks`, `Hyphenation` and `PageNumbers` folds in the same way.
What the settings hide is a **projection** of the model:
- A fold whose category is hidden stays folded; a fold whose category is *not* hidden is undone, so its difference shows as ordinary text.
- Run and block attributes whose category is hidden are removed from the compared content. `Comment` and `Property` subtrees are hidden whole.
- The ledger then lists every difference that exists in the full model but not in the compared projection, outside the regions a change already shows: each place where a hidden fold, hidden format run or hidden attribute differs between paired nodes, each hidden node added, removed or changed, and each opaque part that differs. Differences inside a region a change shows belong to that change.
`LedgerBuilder` computes the ledger from the alignment, the edits and the settings only, so verification recomputes it and fails when an entry is missing.
## 3. The alignment
An `Alignment` says which nodes correspond. It holds both documents, the settings, and `AlignmentLink`s: `Match` (one old node is one new node in the same place), `Move` (same node elsewhere), `Split` (one old, several new) and `Merge` (several old, one new). A node is in at most one link. Nodes in no link are deleted (old) or inserted (new). A link joins nodes of one `NodeKind`.
Edit it with `Pin(old, new)`, `Force(oldNodes, newNodes, kind)` and `Unpin(linkId)`; each returns a corrected copy, normalized. Run `Stages.Align(old, new, seed: alignment)` to keep pinned links and re-pair the rest, or just run `DiffPairs` onwards on the copy.
**Normalization of links** (`Alignment.Normalize`) decides which one-to-one links are `Move`. A link is a `Match` only if its old parent is paired with its new parent and it belongs to the longest run of siblings that kept their order; every other one-to-one link is a `Move`. Hidden-subtree links and splits and merges are exempt. Verification checks the same two rules on every `Match`, so a reorder can never hide: it has to be a visible `Move` change.
## 4. The stages
All stages are pure functions of immutable values, thread-safe, and take a `CancellationToken`; the cost cap (`CompareSettings.CostCap`) travels with the settings in the alignment. Exceeding a cap never throws: the stage returns a coarser, still complete result and adds a `Warning` diagnostic.
```csharp
Alignment Stages.Align(old, new, scorer?, settings?, seed?, ct)
PairDiffs Stages.DiffPairs(alignment, ct)
ChangeSet Stages.Group(pairDiffs, ct)
ChangeSet Stages.Classify(changeSet, ct)
Comparison Stages.Verify(changeSet, ct)
Comparison.Of(old, new, settings?, scorer?, ct) // the five in a row
```
| Stage | What it does | Contract the next stage relies on |
|---|---|---|
| `Align` | The text core over subtree hashes of all nodes in document order, equal subtrees that moved, then text blocks: candidates from a shingle index, splits and merges from containment, ambiguous pairs judged by `IPairScorer` in batches, a global maximum-weight assignment; then containers by matched content and position; then `Normalize`. Details: [alignment.md](https://recursiveai.org/onediff/docs/alignment/) | links satisfy the rules above |
| `DiffPairs` | Per link, a word-level diff over UAX #29 segments with semantic cleanup; format-only edits for equal text with different runs; attribute edits; the ledger. Details: [grouping.md](https://recursiveai.org/onediff/docs/grouping/) | for every non-hidden link, edits that replay old → new and back; `Links[i]` is indexed by link id |
| `Group` | Rule-based change units (values, overlap, sentence and clause breaks, density), one `Change` per unit, whole inserted/deleted nodes, moves, splits, merges and attribute changes; display groups, with cascades and defined-term renames lifted when `CollapseCascades` is on. Details: [grouping.md](https://recursiveai.org/onediff/docs/grouping/), [semantics.md](https://recursiveai.org/onediff/docs/semantics/) | every inserted/deleted node and every link is explained; ids unique; groups partition the changes |
| `Classify` | Change types and resolved values (when `TypedChanges` is on, through the value recognizer), `IsSubstantive`, OCR flags and the `Decision` on every change. Details: [semantics.md](https://recursiveai.org/onediff/docs/semantics/) | none beyond `Group` |
| `Verify` | The checks in section 5, the fallback, and the `Comparison` | — |
Seams: `IPairScorer` (`Score`, `ScoreBatch`) for alignment candidates, `ITextNormalizer` for sources, `IDocumentSource` for inputs. A scorer can only reweigh pairings; every pairing is verified afterwards. `IValueRecognizer` is the seam on `Classify` for typed values (`CompareSettings.ValueRecognizer`); `Change.Decision` records rule, model or user with a score.
### Change shapes
- **Whole node** inserted or deleted: `LinkId = -1`, one side present, no edits.
- **Region** (Insert, Delete, Replace, Format) inside a link: one or more `RegionEdit`s. Coordinates are in the *joined compared text* of the link's nodes (one node: its compared text; a split or merge: the nodes joined with U+001E). An insertion has a zero-length old range, a deletion a zero-length new range, a format change equal old and new text with different runs. `OldRuns`/`NewRuns` carry the formatting of the replaced and replacing characters relative to the edit.
- **Move**: no edits; both sides cover the whole node. Edits to a moved node are separate changes with the same `LinkId`.
- **Split/Merge**: one change for the link carrying all of its edits.
- **Attribute**: `AttributeEdit`s per (old node, new node) pair; absent values are `null`.
## 5. Verification
`Verifier` takes only an alignment, changes, groups and a ledger, and checks:
| Code | Check |
|---|---|
| V100–V104 | change ids unique and non-negative; groups unique; groups list only known changes; every change in exactly one group; sides and edit lists present |
| V105–V113 | a change attached to no link is a whole-node insert/delete of an unmatched node with no edits; link ids valid; the change names the link's nodes; sides have well-formed ranges, the text of that range, and an anchor equal to the one the model resolves; a change's sides contain all of its edits (they may show more, such as a whole number or sentence) |
| V200 | every visible old node is in exactly one link or deleted exactly once; every visible new node likewise inserted |
| V300–V304 | hidden links have no changes; a `Move`/`Split`/`Merge` link has exactly one change of that kind; the link's edits replay old → new **and** new → old over text and formatting; attribute edits replay both ways |
| V400–V401 | every `Match` keeps its parent and its sibling order |
| V500 | the ledger lists every hidden difference |
**Fallback** (when not strict), each step checked again: **1** regroup with the plain fallback stages on the same alignment (drops a bad grouping or a bad in-pair diff); **2** replace every changed block as a whole (drops a bad word diff); **3** nothing aligned, so every block is deleted and inserted (drops a bad alignment). `VerificationResult.FallbackLevel` records the level, and the failures that triggered it are `Error` diagnostics (`verify.V302`, …) followed by a `verify.fallback` warning. The fallback rate is expected to be 0; any non-zero rate is a defect in the stage that produced the failing result.
## 6. JSON
`ComparisonJson.Write` / `Read`; schema version 1 in `docs/schema/comparison-v1.json`. The output is compact UTF-8, keys in a fixed order, empty optional members omitted, non-ASCII escaped, so equal comparisons give equal bytes on every platform; a change's `type`, `oldValue`, `newValue` and `substantive` members are optional additions to version 1 (docs/semantics.md) and a reader that does not know them can ignore them; the reader is bounded (`ComparisonJsonLimits`: input bytes, array length, depth) and throws only `ComparisonFormatException`. Reading validates structure and, by default (`verify: true`), re-runs the completeness checks on what it read, so `Comparison.Verification.Passed` is true only when this process proved it; a stored claim is never copied. With `verify: false` the result says `Verification.VerifiedHere == false` and `Passed == false`. A `Comparison` is immutable, so `Check()` only returns the failures (an empty array when everything holds) and never changes `Verification`; to get `Passed == true`, read again with `verify: true`. The exception carries the position of a syntax error (`LineNumber`, `BytePositionInLine`, `Path`). `ComparisonJson.ReadAsync` / `WriteAsync` take streams that refuse synchronous I/O. A source warning (a damaged input) becomes a diagnostic with the code `source.old.` or `source.new.`; the JSON schema is unchanged.
## 7. Plain text
`PlainTextSource` reads UTF-8/UTF-16 text (by byte order mark, otherwise UTF-8) into one `Section` holding a `Paragraph` per run of non-blank lines; the lines are kept, joined by LF. It normalizes with the typographic normalizer and gives each paragraph a `TextSpan` anchor into the decoded text and a segment per line. A paragraph that opens with a list marker and goes on (`4.2 Payment`, `(a) the Buyer`; the rule is `ListMarkers.IsMarker`, shared with the PDF and scan sources) is a `ListItem` whose `list.label` is the marker and whose text starts after it, so a renumbering is the same kind of change (a non-substantive attribute change inside a "Renumbering" cascade) whichever kind of file the clauses were read from. Input containing a zero byte (and no UTF-16 mark) is not text. Sources are chosen by content (`DocumentSources.Sniff`), never by file name.
## 8. Extending it
- **Alignment:** described in `alignment.md`. A replacement stage returns a normalized `Alignment`; a scorer plugs in through `IPairScorer`.
- **In-pair diff and grouping:** produce `LinkDiff`s with replayable `RegionEdit`s; group by emitting `Change`s whose edits are a partition of the link's edits, and `ChangeGroup`s over their ids. Never put data in a group.
- **Ledger:** extend `LedgerBuilder` for new categories (page numbers, hyphenation); `Verify` recomputes it from edits.
- **Writers:** read `Comparison`; resolve `Anchor`s; use `Change.Old/New` for text and `Groups` for display.
- **Sources:** build with `CompareDocumentBuilder`, normalize with `TextNormalization`, attach anchors and segments, set `SourceHash`; implement `IDocumentSource.CanRead` by content.
# Alignment
What `Stages.Align` does, in the order it does it, so that a different implementation (or a person correcting one) can follow the same rules. The result is an `Alignment` of `Match`, `Move`, `Split` and `Merge` links (see `compare-model.md`); verification checks it afterwards, so these rules decide how a change *reads*, never whether the comparison is complete.
Everything is deterministic: the same inputs and settings give the same links. Ties are broken by node number, never by hash order or time.
## 0. Preparation
For each node: its compared text (normalization folds whose category is not hidden are undone), its words (letters and digits runs of the word tokenizer, compared exactly), the *shingles* of its words (hashes of neighbouring word pairs; the single words too when the text has three words or fewer), and a *subtree id*. Two nodes have the same subtree id exactly when their kind, compared text, content hash (or property name) and child subtree ids are equal. Block attributes and formatting are not part of the id, so a formatting-only change is still an exact match and shows as a format or attribute change later. Pinned links from the seed alignment are kept first and their nodes are left out of everything below.
## 1. Exact sequence
The text core (the settings' algorithm; histogram when the product of the two lengths is over the cost cap) runs over the subtree id plus depth of every unpinned node in document order. Equal runs become `Exact` matches. What lies between two matches is a *stretch*: the old and new nodes in the same stretch are each other's natural partners later. Because the sequence is diffed, a block repeated several times lines up with its own repetitions in order and never crosses.
A sequence can have several equally long readings when blocks repeat, and the text core takes one of them without looking at where the blocks sit. Three rules, applied in this order each time the sequence is run, choose among them by structure:
1. **Windows without a stable run.** Between two runs of at least eight matches in step (which nothing could change), the stretch is searched again (a table of at most 1,500 × 1,500 nodes and 2^20 cells) for the longest match, and among the longest the one with the least *drift*: the sum over matches of how far the position of the pair, counted from the window's start, differs between the sides. Of clauses that differ only in a figure, the one in the same place is matched, not the one that would have to jump over its neighbour.
2. **Copies.** When a run of unmatched nodes (or its last or first whole sibling subtrees) is an exact copy of the run next to it, the copies form a chain and the one left unmatched is the one that keeps all the others nearest to their place on the other side (the sum of index differences; ties go to the later copy, because a copy is made after its original). Copies move as whole sibling subtrees, never cut.
3. **Container context.** A *repeated* pair is a match of a block whose subtree id occurs more than once on a side, or whose subtree holds at most five words (a table value, a short label). It contradicts its context when, walking up from both blocks through containers of equal kind, a container is already matched to another node, or is the *provisional partner* of another. Provisional partners are containers (not matched exactly) where the blocks that are not repeated vote: each exactly matched, non-repeated text block votes for every pair of its unmatched ancestors, and two containers are partners when each is the other's single best vote. A pair that contradicts its context is banned: the subtrees on both sides get ids nothing else has, and the sequence is run again (at most four times). So a value in one row is not paired with the equal value of a row it does not belong to, and a deleted row does not lend its equal cell to the row above.
Stretches are numbered by the matches before them, from the final sequence.
## 2. Exact relocation (when `DetectMoves`)
Subtrees that are still wholly unmatched and equal on both sides are paired wherever they sit, largest subtree first, and among equal subtrees in document order. A moved clause is one link; a moved table is one link for the table plus matches for what is inside it. Subtrees without text or images are never relocated. Two refinements keep equal text from being taken for a move by chance:
- Among equal candidates, one that contradicts its container context (step 1, rule 3) is passed over, and one whose parent is the partner of this one's parent is preferred. The first 64 free candidates are looked at.
- A single text block is not relocated when both it and its partner each have a close edited partner (similarity at least `MatchThreshold`) among the free blocks of the stretch they sit in: clauses that differ only in a figure, each figure shifted by one place, are edits. The pair is left to step 3, where it competes with those edits.
## 3. Text blocks
Eligible blocks are unmatched nodes with at least one word.
1. **Candidates.** An inverted index of shingles (a shingle in more than 24 blocks is ignored) is built for each side. Each block votes for the blocks of the same kind it shares shingles with; the six best (most shared shingles, then nearest position, then lowest number) become candidates, from both directions. Short stretches (at most 100 old-by-new pairs) are compared in full. The work is bounded by the posting cap, so it is near-linear.
2. **Similarity.** The Dice coefficient of the two word multisets; for texts of at most three words also the character-pair Dice, whichever is larger. Pairs under 0.30 are dropped.
3. **Splits and merges** (when `DetectSplitsAndMerges`). A block is a *part* of a longer block (at least four words) when it has at least three words, at least two shingles, and at least 60% of its shingles are in the longer one. Parts of one block that are neighbouring siblings form runs; every window of two to eight parts is scored by the Dice coefficient of the block against the union of the parts. The best window is proposed when it reaches `SplitMergeThreshold` and beats the best single candidate of the block by more than 0.05. A block is not counted as a part of a whole when the whole's previous or next sibling is a better home for it: the sibling is the block's best other candidate, at least `MatchThreshold` similar, and holds a larger share of the block's words than the whole does (or an equal share and a higher similarity). Two neighbouring paragraphs that were both edited, and share template sentences, are then not read as a split. Proposals are accepted best first, skipping any whose nodes are taken.
4. **Judging.** A candidate under 0.95 is ambiguous and goes to the scorer, in batches of 1,024 pairs (`IPairScorer.ScoreBatch`); the rest keep the similarity. The default scorer, `RulesPairScorer`, is the similarity adjusted by structure (+0.02 for each of paragraph style and list level that is equal on both sides, −0.05 for each that differs). A custom scorer replaces that judgement and is never asked about pairs the exact stages or the 0.95 rule settled.
5. **Admission.** A pair in the same stretch needs at least `MatchThreshold`; any other pair is a move candidate and needs `DetectMoves` and either at least `MoveThreshold`, or at least `MatchThreshold` with a *unique partner*: the pair is the best candidate of both blocks and beats every other candidate of either block (local ones included) by at least 0.15. An edited clause that moved has one such partner; two near-identical clauses have two, so neither is guessed.
6. **Choice.** Each admitted pair is weighed: judged similarity, +0.10 if both blocks are in the same stretch, +0.05 if the previous or next sibling of one is matched to the previous or next sibling of the other, +0.02 × (1 − distance between their relative positions in the documents). The global matcher then picks the set of pairs in which no block repeats and the total weight is largest: connected groups of candidates are solved exactly with the Hungarian method up to a size bound, and greedily (heaviest first) beyond it. Chosen pairs in the same stretch have origin `Similar`, the others `Relocated`. A pair that contradicts its container context (step 1, rule 3) and is a repeated pair is left out.
## 4. Containers
A container is an unmatched node with no text of its own that groups others (table, row, cell, section, note, header, footer, comment, text box, content control).
1. **By content.** For every matched pair of text blocks or images, each pair of their ancestors of equal kind gets a vote. A pair of containers scores twice its votes over the sum of their content counts (capped at 1); pairs under 0.25 are dropped; the rest are weighed (+0.05 when their parents are paired, +0.02 × nearness) and chosen by the same global matcher. So a table whose rows were reordered and edited is still the same table, and a row with a new column cell is still the same row.
2. **By position.** Walking the paired containers from the roots down: among the children of a pair, the matched children that keep their order are anchors; between two anchors, if the old side and the new side hold the same number (at least one) of unmatched containers of a kind, they are paired in order (score 0.5, origin `Similar`). This pairs empty cells, rows whose text was all rewritten, and the only section or table of a rewritten document.
3. **Text in a paired cell.** In a pair of table cells, between two matched siblings, a single unmatched text block of a kind on each side is paired (score 0.5, origin `Similar`): a cell whose text was rewritten past recognition is one replace, not a delete beside an insert.
## 5. The cost cap
`CompareSettings.CostCap` bounds the work of the search for edited blocks: comparisons of two blocks, windows of splits and merges, and the cubic work of exact assignments, with postings visited counted at one sixteenth. When the bound is passed, step 3 stops before it creates any link, a warning diagnostic `align.cap` is added, and the result keeps the exact matches, relocations and the containers: complete, but edited blocks show as deleted and inserted. The exact sequence (step 1) is not capped; it uses Myers while the product of the lengths is within the cap and histogram beyond it (an `align.large` information diagnostic).
## 6. Normalization
The links are then normalized (see `compare-model.md`): which one-to-one links are `Move` is decided by the parent and sibling-order rules, not by the steps above.
## Editing
`Pin`, `Force` and `Unpin` act on the result. `Stages.Align(..., seed:)` keeps the pinned links of the seed, does not look at its other links, and aligns everything else afresh.
# In-pair diff and grouping
How the edits inside a pair of aligned blocks are found, and how they become the changes a reader sees. Everything here is deterministic: the same inputs and settings give the same changes in the same order.
## 1. The in-pair diff (`Stages.DiffPairs`)
For every link of the alignment (hidden links are skipped), the **joined compared text** of each side is compared. A split or merge joins its nodes with U+001E; a link of one node on each side uses just the node's compared text. Equal text costs nothing.
1. **Words.** Each text is cut at UAX #29 word boundaries (section 4, no tailoring; OneFont's `TextSegmentation`). Segments include white space and punctuation, so they partition the text and every edit maps to an exact character range. Han ideographs and kana are one segment per character (UAX #29 has no dictionary); Thai, Lao, Khmer and Myanmar runs are one segment per run of letters.
2. **Script.** The configured algorithm (`CompareSettings.Algorithm`, Myers by default) diffs the segment sequences. If the number of segment pairs exceeds `CompareSettings.CostCap`, the link falls back to one replacement between the common start and end and a `diffpairs.cap` warning says so.
3. **Cleanup.** The text core's semantic cleanup runs over the script (`DiffCleanup.Semantic`): an equal stretch no longer than the edits on both sides of it is absorbed, so a stray "the" does not cut one rewritten phrase in two, and a lone insertion or deletion slides to a word edge. Cleanup never changes what the script turns into what; the new text and the old text stay exactly reproducible.
4. **Refinement.** A region that replaced one segment by one segment and holds digits on both sides ("1,250,000" → "1,520,000"), and a region in a script without spaces between words on both sides, is diffed again by grapheme clusters, and the refinement is kept if something is shared and it falls into at most three pieces. Other replaced words stay whole: "Parties" replaced by "Party" is one edit, not "ies" by "y".
5. **Formatting.** Text that is equal on both sides can still differ in formatting. The text is cut wherever either side's formatting changes, and each piece is labelled with exactly what differs (`run.bold` off to on, `run.font` A to B). Neighbouring pieces with the same label are one edit. An edit whose old and new text are equal is a **format-only edit**; its `OldRuns` and `NewRuns` carry the formatting on each side. Formatting categories the settings hide never reach this stage; they are in the ledger.
The result is a `LinkDiff` per link: ordered, non-overlapping `RegionEdit`s in the coordinates of the joined text, which replay old → new and new → old over text and formatting, plus the attribute edits of the nodes. Verification replays them.
## 2. Change units (`Stages.Group`)
The edits are **atomic data** and stay atomic. Grouping chooses **change units**: each unit is one `Change` holding one or more of the link's edits. The units of a link partition its edits, and a unit's sides are ranges of the joined text that **contain** all its edits (a side may show more than its edits, never less). Whole-node insertions and deletions, moves, splits, merges and attribute changes are made as before. `ChangeGroup`s are display regions over change ids and hold no data: one per change, except that a moved node and everything inside it (its attribute changes and text edits) form one region, and so do the cells of one table row that were inserted or deleted whole.
Rules, in order, per ordinary link:
1. **Values.** Each text edit is widened to cover every value it touches on each side: a date (`March 3, 2025`, `2026-01-31`, `3/4/2025`, `2025年3月4日`), an amount (`$1,250,000`, `USD 5,000`, `5,000 euros`, with million/billion), a percentage (`12.5%`, `12 percent`), a duration (`30 days`, `10 business days`, `三十日`, `30日`), or a plain number. So "30 days" becoming "60 days" is one change reading `30 days → 60 days`, while its edit is the digit. An edit that only drops or adds characters of a value ("15%" to "5%", "2 500 EUR" to "12 500 EUR") is empty on one side; that side takes in the value it touches when it is the other side's value with exactly the edit's characters left out, so the change reads `15% → 5%` and not "15% deleted". The patterns are simple and deterministic; they are not recognizers (what a value means is decided later).
2. **Overlap.** Units that meet or overlap are joined. A formatting edit that overlaps a unit becomes part of that unit; this can make a unit reach its neighbour, so joining and taking in repeat until nothing changes.
3. **Breaks.** Units never join across a **sentence end** (UAX #29 section 5, on either side's text) or a **clause break**: `;` or `:` followed by white space, or a line break. A unit may still contain an edit that itself crosses a boundary.
4. **Density, per clause** (the run of units between two breaks). With changed words counted on both sides (a word is two half-words; each ideograph, kana or Thai character is one):
- at least two units, and at least **a quarter** of the clause's words changed: all the clause's edits become one unit widened to the whole clause on both sides;
- at least three units, and at least **12%** changed: likewise;
- otherwise units join only when the unchanged text between them is **two words or less**.
5. **Formatting units.** Format-only edits that no text unit took in become format changes (`ChangeKind.Format`): one per edit, and neighbours with the **same label** join across white space alone, if no text unit lies between.
A unit's kind is `Format` when all its edits are format-only, otherwise `Insert` when its old side is empty, `Delete` when its new side is empty, else `Replace`. Units are ordered by where they start in the new text. The thresholds (join distance, the two density shares and their minimum unit counts) were chosen on the synthetic dev and train splits and never on the eval split. On dev, boundary F1 moves by at most 0.001 over join distances 0 to 6, whole-clause shares 0.15 to 0.4, scattered shares 0.09 to 0.2 and minimum counts 2 to 4, so the values above are kept; the density rules together are worth about 0.015 boundary F1 (on dev, switching them off scored 0.887 against 0.902, measured before the value rule above and the no-difference rule in docs/measurement.md).
Cascades, defined-term renames, typed values and the substantive filter are in docs/semantics.md. They arrange or label the units made here and never change an edit; one thing reaches back into this stage: an edit that replaces a renamed defined term by its new name stays a unit of its own (the *pinned* edits, section 1 of docs/semantics.md), unless the units around it reach it.
## 3. Why the units are not merged edits
Merging scattered edits into one big replace edit would be simpler, but it would turn unchanged words into deleted and inserted ones, and a writer that wants the finer view (words struck inside a rewritten sentence) could no longer have it. Keeping the atomic edits in the unit gives both: a writer that shows units reads `Change.Old` / `Change.New`; a writer that shows detail reads `Change.Edits`.
## 4. Verification
`Verify` checks every claim here without trusting this code: each edit replays, each change names its link's nodes, its sides' texts and anchors are the source's, its edits lie inside its sides, and every change is in exactly one group. If a check fails, the engine falls back to the reference stages on the same alignment (one change per edit), then to whole-block replacement.
# Change semantics
What a change is *about*, and which changes belong together. Everything here is deterministic and works without a model. Nothing here alters an edit: cascades and renames are display groups over changes that stay in the list, types and values are labels on changes, and `Verify` checks the same completeness it always did.
Where it runs:
| Stage | Setting | Does |
|---|---|---|
| `Stages.Group` | `CollapseCascades` | pins rename edits (section 1), then lifts the changes of a renumbering and of a rename into `GroupKind.Cascade` and `GroupKind.Rename` groups |
| `Stages.Classify` | `TypedChanges` for types and values; always for `IsSubstantive` | sets `Change.Type`, `OldValue`, `NewValue`, `IsSubstantive` and the decision |
`CompareSettings.Legal` turns both on; `Strict` and `TextOnly` leave them off (Strict collapses and types nothing, so every edit reads as it is).
## 1. Cascades and renames
**Cascade.** A *renumbering* is a change whose attribute edits are all a list label going from one value to another (`list.label` `3.2` to `3.3`; surrounding space, brackets and a closing full stop do not count: `3.` and `3`). A *reference change* is a replacement whose old side and new side are each a reference to a clause: a keyword and a number (`Section 3.2`, `§ 3.2`, `Abschnitt 3.2`, `l'article 3.2`, `cláusula 3.2`, `البند 3.2`, `第3.2条`), or just the number when the keyword stands right before it. A reference change is *caused by the renumbering* when its pair of numbers is one of the renumbered labels (`3.2` to `3.3` here and in a label). The cascade group holds every renumbering and every caused reference change of the comparison, one group per comparison, titled "Renumbering". A reference edited by hand to a number no label moved to is not in it; it is a substantive `Reference` change. A reference that the density rules of `docs/grouping.md` merged into a larger unit with other edits is not a reference change and is not in the group either; the other edits are then not hidden by it.
**Rename.** The terms a document defines are the quoted phrases that the text goes on to define: followed by `means`, `shall mean`, `has the meaning`, `bezeichnet`, `bedeutet`, `désigne`, `signifie`, `significa`, `是指`, `指`, `とは`, `をいう`, `تعني`, `يعني` and the like, or closed by a bracket as in `(the "Supplier")` and `(以下「X」という)`. Quotes may be `" “ „ « ‹ 「 『`. A *renamed term* is a replacement of a term only the old document defines by a term only the new document defines, in at least two places (the definition and a use, or more). A prefix or suffix both texts share (an attached preposition such as Arabic `لـ`) is set aside when that is what it takes to find the two terms. The rename group holds those changes, one group per pair of terms, titled `"old" → "new"`. A change takes part only if its sides are exactly the two terms.
**Pinned edits.** To keep a rename from swallowing the other edits of its sentence, an edit that replaces a renamed term by its new name is not joined with the edits around it by the density rules of `docs/grouping.md`; it is its own unit unless the units built without it already reach it (then it goes back among them, as before). The pairs are found from the edits alone, before units are built.
A change that sits inside a larger region (the paragraph of a move) is lifted out of that region into its group; the other changes of the region stay together. Every change is in exactly one group after this, as `Verify` requires.
## 2. Types and resolved values
`Change.Type` is `None` for an ordinary text change. With `TypedChanges`, in this order:
1. `Formatting` for a format change; `Numbering` for a list-label attribute change (values: the label without closing punctuation).
2. `Typography` for a text change whose sides are equal once white space is dropped and quotation marks and dashes are made plain.
3. In a cascade group, `Reference`; in a rename group, `DefinedTerm` (values: the two terms).
4. A reference outside a cascade is `Reference` with the clause numbers as values.
5. A value change: each side that is present is, as a whole, exactly one value found by the recognizer, and when both are present they are of one kind: `Amount`, `Date`, `Duration`, `Percentage`, `Number`, `Party`. A kind with no resolved value on a side (an ambiguous date) still types the change, with a decision score of 0.5 instead of 1 and no value on that side.
6. A replacement, insertion or deletion of a term the document defines (one side may be empty): `DefinedTerm`.
Everything is a rule: `Decision.By` is `Rule`, the source names the rule (`semantics.value`, `semantics.reference`, `semantics.numbering`, `semantics.term`, `semantics.party`, `semantics.format`, `semantics.typography`, or `semantics` for the rest), the score is 1 except as stated in 5. A model that decides later does so with `DecidedBy.Model` and its own score.
**Canonical values** are the same in every language:
| Type | Canonical | Examples |
|---|---|---|
| Amount | ISO 4217 code, space, number | `USD 25000` (from `USD 25,000`, `25,000 دولار`), `EUR 18000` (`18.000 EUR`, `2 500 EUR` is `EUR 2500`), `CNY 4800` (`人民币4,800元`), `USD 2000000` (`$2 million`) |
| Date | ISO 8601 | `2028-05-16`, `2029-06-01` (`1. Juni 2029`), `2025-01-03` (`3 de enero de 2025`), `2029-08-06` (`6 أغسطس 2029`), `2027-12-27` (`2027年12月27日`); `2025-03` and `--03-16` when the day or the year is missing |
| Duration | number, space, unit (`s min h d bd w mo y`) | `30 d`, `10 bd` (business or working days), `18 mo` (`18 Monaten`), `9 mo` (`9个月`), `30 d` (`三十日`), `1 y` (`1年`) |
| Percentage | number and `%` | `12.5%`, `6%` (`6 %`) |
| Number | invariant decimal | `42` |
| Reference | the clause number | `8.4` (from `Section 8.4`, `البند 8.4`, `第8.4条`) |
| Numbering | the label without closing punctuation | `2.2` |
| DefinedTerm, Party | the text | `Software` |
Numbers: a number with one separator and exactly three digits after it (and one to three before, not starting with 0) reads as a thousands group (`1.200` is 1200, `1,200` is 1200, `0.500` is 0.5); in every other case a single separator is the decimal mark; with both, the last is the decimal mark. A date whose day and month could be either (`3/4/2025`; with dots `3.4.2025` is day first) is recognized and not resolved.
Month, unit and currency names are written for English, German, French, Spanish, Arabic, Chinese and Japanese; other languages are recognized where they use digits and symbols. The `Party` recognizer finds a name that ends in a legal form (`Inc`, `Ltd`, `LLC`, `plc`, `GmbH`, `AG`, `S.A.`, `SARL`, `B.V.`, `株式会社`, `有限公司` …).
## 3. The recognizer seam
```csharp
public interface IValueRecognizer
{
ImmutableArray Recognize(string text, string? language);
}
public readonly record struct RecognizedValue(int Start, int Length, ChangeType Type, ResolvedValue? Value);
ChangeSet typed = Stages.Classify(changes, myRecognizer);
```
`Recognize` returns the values of a short text (a change side), ordered by position and not overlapping; `Type` is one of the value types (`Amount`, `Date`, `Duration`, `Percentage`, `Number`, `Party`); `Value` is null when the text reads as such a value but cannot be resolved. An implementation is **pure and thread-safe**: no clock, no current culture, no network, no state shared between calls. `language` is a BCP 47 tag when the caller knows it, otherwise null. A recognizer from another package (multilingual, model-backed) replaces `BuiltInValueRecognizer`; only values come from it. References, list labels, defined terms and the substantive flag are decided by the library's own rules, so a recognizer cannot hide or reclassify a change. The recognizer a comparison uses is `CompareSettings.ValueRecognizer` when set, else the one registered process-wide with `ValueRecognizers.Register`, else `BuiltInValueRecognizer`; the reference stages that run when verification falls back read it from the settings too. `Comparison.Of` and the other one-liners therefore use the built-in recognizer unless one of those names another. The `RecursiveAI.OneDiff.Nlp` package supplies one built on OneNLP (`docs/nlp.md`).
## 4. Substantive
`Change.IsSubstantive` says whether the change alters what the document says. It is true for a change nobody classified.
Not substantive: `Format` changes; `Attribute` changes (style, list label, level); `Typography`; the reference changes of a cascade; whole-paragraph insertions and deletions of empty text; splits and merges whose edits only add or remove the paragraph break and white space.
Substantive: everything else, including moves, defined-term changes and renames (a drafting choice a reader still wants to see), insertions and deletions of text, and an image or table inserted or deleted.
`Comparison.Changes.Where(c => c.IsSubstantive)` is the filter; the substantive view of the HTML pages and the change report build on it.
## 5. JSON and HTML
Schema version 1 gains four optional members on a change (`type`, `oldValue`, `newValue`, `substantive`); see `docs/schema/comparison-v1.json`. They are written only when set (`type` unless `none`, values when present, `substantive` only as `false`), so comparisons made without semantics are byte-identical to before. A reader that does not know them ignores them. Groups of kind `cascade` and `rename` already existed in the schema; a group's `changes` are its occurrences and `title` is `Renumbering` or the term pair.
The HTML pages list each cascade and rename group once under "Grouped changes", with its occurrences (`data-group`, `data-occurrence` attributes); the marks in the text are the changes themselves and are untouched.
## 6. Measured
Rows and definitions in `docs/measurement.md` (Semantic rows).
# Combine, version chains and the change report
Normative description of `Combination`, `ComparisonChain` and `ChangeReport` in `RecursiveAI.OneDiff.Documents` (namespace `OneDiff.Documents.Combine`). The compare model, anchors, alignment and grouping they build on are in `compare-model.md`, `alignment.md` and `grouping.md`.
## 1. Combine
**Input.** One original document and N ≥ 1 reviewers' copies of it. Reviewer *k* is the *k*-th copy; its index is its position in the list. Every copy is compared with the original by the ordinary stages (`Comparison.Of(original, copy_k, settings)`), so each reviewer has a verified, invertible `Comparison` over the **same** `CompareDocument` object. `Combination.From` accepts ready comparisons and requires that they share that object (node ids are then the same everywhere).
**Result.** `Combination` holds the original, the reviewers, their comparisons, the combined changes, the conflicts, diagnostics and a verification record. The combined result never contains a decision between reviewers: nothing is dropped, preferred or merged away unless two reviewers made *the same* change.
### 1.1 Combined changes
A *combined change* stands for one change of one reviewer's comparison or, when several reviewers made the same change, for all of those. It carries the first holder's `Change` (both sides, both anchors, edits), the reviewers, the holders (`reviewer`, `change id` in that reviewer's comparison), the reviewers of each edit, and the conflict it is in (or -1). Combined changes are numbered 0..n-1 in the order of the original: by the first old node, then an insertion after the node it follows, then the position inside the node, then reviewer, then the reviewer's own change number. The order is total, so the output is deterministic.
### 1.2 What a change claims
Every change makes *claims* about the original, in the original's coordinates. A claim is a kind, the old nodes it concerns, a character range (for text), a key and an effect:
| Claim | From | Range / key | Effect |
|---|---|---|---|
| Text | each edit of a change | old nodes of the link, `[OldStart, OldEnd)` in their joined text (a point when the range is empty) | the new text and its formatting runs (`txt`), or the new formatting only (`fmt`) |
| Whole | a node deleted whole | the node | `del` |
| Structure | a split or merge | the old nodes | kind, number of new nodes, new text |
| Attr | each attribute edit | node and attribute key | the new value |
| Moved | a move | the old node; key = destination | `mv` |
| Insert | a node inserted whole | key = place: the old node of the linked parent, the old node of the nearest linked sibling before it, the number of unlinked siblings between, and the path below the top of an inserted subtree | node kind, text, attributes, runs |
A change with no claim by these rules still claims its old nodes (Structure) or, with none, its place (Insert), so no change can pass unnoticed next to another's.
### 1.3 Identical changes are merged
Two reviewers' changes are **the same** when they have the same kind, the same claims (kind, nodes, range, key, effect) and the same new text. They become one combined change attributed to both. Numbers that differ between comparisons (change ids, new-side node ids and offsets) play no part. A reviewer never merges with itself.
**Edit-level attribution.** A reviewer's change groups edits into display units, and two reviewers may group the same edit differently (one changed a neighbouring word too). Such changes are not merged, but each edit is attributed on its own: `EditReviewers[i]` lists every reviewer who made the *same edit* as edit *i* of the shown change — the same place in the original, the same new text and formatting — whether or not their change is the one shown. So a shared edit is never mistaken for a private one, and a combined change is never hidden by another.
### 1.4 Conflicts
Claims of **different reviewers** conflict when they cannot all be applied to the original. Identical claims never conflict. The rules:
| Claims | Conflict when | Kind |
|---|---|---|
| Whole × anything on a shared node | always (a node deleted by one reviewer and edited, moved, restructured or given an attribute by another) | `EditAndDelete` |
| Text × Text, same old nodes | the ranges overlap: they share a character; or a point lies strictly inside the other range; or two points coincide | `Edits` |
| Text × Text, different but intersecting old nodes | always (a merge or split edit against an edit of one of its nodes; coordinates are not comparable) | `Edits` |
| Moved × Moved, same node | different destinations | `Move` |
| Structure × Structure, shared node | different effect | `Structure` |
| Attr × Attr, same node and key | different values | `Attribute` |
| Insert × Insert | the same place, different content | `Insert` |
**Derived claims never conflict.** A list label (`para.label`) that changed, a change of type numbering, and a reference rewritten to follow a renumbering (type reference, not substantive) are consequences of other changes: two reviewers who deleted different clauses renumber the same later clause differently, and merging both deletions gives a third number that neither chose. These changes are attributed and merged like any other and never flagged; the changes that cause them are the ones that conflict, when they do. (The reference rule needs `TypedChanges`; list labels do not.)
A point at the edge of a range does not conflict with it; two edits on different words of one paragraph do not conflict. Text × Structure, Text × Attr, Text × Moved, and a moved node's inner edits against its move do not conflict: they commute.
A *conflict* is a connected component of conflicting combined changes, with at least two changes of at least two reviewers. Its `Kind` is the most serious (lowest in the table above, by enum order) of its pairs; `Reviewers` lists those involved. Conflicts are numbered in the order of their first change. **Every conflicting version is shown; none is preferred.** A change shared by reviewers A and B that overlaps a change of C puts A's, B's and C's versions in one conflict.
### 1.5 Verification
`Combination.Check()` returns failures with codes:
| Code | Check |
|---|---|
| C001, C002 | each reviewer's comparison was made from the combination's original and passes `Comparison.Check` |
| C101–C104 | combined change ids are 0..n-1; each has holders; every holder exists; no reviewer change is attributed twice |
| C105 | every holder's change equals the shown change in kind, old side, edits (place, new text, formatting) and new text |
| C106, C107, C108 | the reviewers equal the holders' reviewers; edit attributions are as many as edits, include every holder, and name only reviewers who made that edit |
| C109 | every change of every reviewer is in some combined change |
| C201–C204 | the stored conflicts equal the conflicts recomputed from the changes (ids, kinds, members, reviewers), each has ≥2 changes of ≥2 reviewers, and each change's conflict id is right |
C101–C104 and C109 together say that the changes attributed to reviewer *k* are exactly the changes of *k*'s comparison, each once. Projecting the combined result onto *k* (`ChangesOf(k)`, each by its holder entry for *k*) therefore gives the very change list of *k*'s verified comparison, so old + changes = *k*'s copy and the copy − changes = old, per reviewer, on every run.
**Fallback.** If a check fails, the combination is rebuilt without merging (every reviewer's change listed on its own, conflicts recomputed) with a `combine.fallback` warning and `combine.C…` error diagnostics for the failures that were recovered from (`Verification.FallbackLevel` 1). If it still fails, `ComparisonVerificationException`. With `CompareSettings.ThrowOnFailure` (strict) the first failure throws. Without the model, nothing here depends on it.
### 1.6 Entry points
`Combination.Of(original, copies, settings, scorer, token)`; `Combination.From(comparisons, token)`; `Redline.Combine(originalPath, copyPaths, outputPath, settings)` (thin: reads the files, `Combination.Of`, `SaveAs`); CLI `onediff combine ... -o `. `Combination.SaveAs` writes the change report (`.html`) or the JSON form (`.json`). Per-reviewer inline redline documents and DOCX with revision authors per reviewer come with the Word writer.
## 2. Version chains
`ComparisonChain.Of(versions, settings, scorer, token)` compares version *i* with *i* + 1 for every step and the first version with the last (the *net* comparison). Step *i*'s new document is step *i* + 1's old document: the same object, so the steps compose. Every step and the net comparison are ordinary verified comparisons; `Check()` re-runs them (H001–H004) and confirms the steps meet and the net runs from the first version to the last.
**Step attribution.** Each change belongs to the step that made it (a step's changes are its own comparison's). For the net view, `StepsOf(netChangeId)` lists the steps that touched a net change. A step touches it when
1. one of its changes concerns a block the net change's old blocks became (followed forward through the steps' alignments), or that the net change's new blocks came from (followed backward);
2. one of those blocks is deleted or created in that step (a block removed with its parent has no change of its own);
3. for a net move: the step moved anything (moving one block changes the relative order of the others, so the net comparison may show a different block as moved);
4. otherwise (the net comparison paired interchangeable blocks, say empty cells, differently from the steps): the steps that made a change of the same kind, and failing that any step that changed anything or reordered blocks (identical blocks, such as empty cells, can swap places with no change to show).
The grain is the block: two edits to one paragraph in different steps are both attributed to both steps in the net view; the step comparisons say exactly which step made which edit.
Entry points: `ComparisonChain.Of`, `Redline.Chain(versionPaths, outputPath, settings)`, CLI `onediff chain ... -o `.
## 3. Change report
`ChangeReport.From(comparison | combination | chain)` is a plain data object; `ToHtml()` renders it as one self-contained page (inline style, no scripts, no time or environment: the same report gives the same bytes).
- **Counts** by change kind and by change type (only those that occur), the number of substantive changes, and the ledger (hidden differences by category).
- **The substantive list** (`IsSubstantive`): location, kind, the old and new text (shortened to 200 characters), and the resolved values (`Duration 30 d → 60 d`). *Location* is `§` and the list label of the block or its nearest labelled ancestor (`§4.2`), otherwise `¶` and the block's number among paragraphs and list items.
- **Combination:** changes attributed per reviewer, how many were made by one, two, … reviewers, and a section per conflict listing every reviewer's version side by side with the reviewers named.
- **Chain:** a section per step with its counts and substantive list, then the net section, each net change with the steps that touched it.
## 4. JSON forms
Both embed complete `onediff.comparison` documents (see `schema/comparison-v1.json`, unchanged) and add attribution. Schemas: `schema/combination-v1.json`, `schema/chain-v1.json`. Written with `Utf8JsonWriter`; byte-identical for equal inputs.
`onediff.combination` v1: `original` {name, hash}; `reviewers` [{index, name, hash}]; `verification` {passed, fallbackLevel, failureCount}; `changes` [{id, kind, reviewers [], holders [{reviewer, change}], editReviewers [[…]] (omitted without edits), conflict (omitted when none)}]; `conflicts` [{id, kind (`editAndDelete`, `edits`, `move`, `structure`, `attribute`, `insert`), changes [], reviewers []}]; `diagnostics`; `comparisons` [full comparison per reviewer, by index]. A combined change's content is the holder's change in `comparisons[reviewer].changes[change]`.
`onediff.chain` v1: `versions` [{name, hash}]; `steps` [{index, from, to, comparison}]; `net` {comparison, changeSteps [{change, steps []}]}; `diagnostics`.
The existing `onediff.comparison` document is unchanged. There is no per-change step or reviewer member in it, because a comparison has one old and one new side: attribution belongs to the document that holds several of them.
## 5. Limits and cost
Claims are grouped by old node and by insertion place; pairs are compared only inside a group, so cost is quadratic only in the edits to one node. The combination's own work is a small fraction of the N comparisons it is built on (see `measurement.md`). Memory is linear in the changes. Cancellation is observed between comparisons.
## 6. Samples
`docs/samples/inputs/` holds the plain-text contract used below: an original, three reviewers' copies (`alice`, `bob`, `carol`) and four versions (`v1` to `v4`). `docs/samples/combine-report.html` is `onediff combine original.txt alice.txt bob.txt carol.txt -o combine-report.html` (two shared changes, one conflict over a payment period that two reviewers set to 60 and one to 30 days), and `docs/samples/chain-report.html` is `onediff chain v1.txt v2.txt v3.txt v4.txt -o chain-report.html`.
# HTML output and the redline entry points
This note describes what `RecursiveAI.OneDiff.Documents` writes as HTML, how a page maps back to the comparison it came from, and how adapter packages plug their inputs and output forms into `Redline.Create` and `Comparison.SaveAs`.
## 1. The page
Both layouts are one self-contained file: UTF-8 without a byte order mark, LF line ends, inline CSS, no scripts, no external fetches (no `src`, no `url()`, no `@import`, no link other than in-page `#` anchors), system font stacks. The same comparison and style give the same bytes on every platform; the clock is never read. A timestamp appears only when `RedlineStyle.Timestamp` is set.
```
RedlineStyle.Language ("en"); the page furniture is English
charset, viewport, generator, ,