# Algorithm Design

This document describes the internal data model, Myers shortest-edit-path
implementation, Unicode handling, and Unified Diff hunk construction.

## Processing Pipeline

Character diff follows this pipeline:

```text
String inputs
  -> Unicode scalar arrays (`Array[Char]`)
  -> common prefix/suffix removal
  -> Myers shortest edit path on the changed middle
  -> per-character `EditOp` values
  -> optional adjacent-operation compaction
```

Unified Diff follows a parallel line-oriented path:

```text
String inputs
  -> CRLF/CR to LF normalization
  -> arrays of complete lines with EOF-termination state
  -> the same generic Myers path search
  -> line `EditOp` values
  -> context-window grouping
  -> Unified Diff headers and hunks
```

Sharing the path search keeps tie-breaking and minimality consistent between
character and line diffs.

The standard renderer includes each line's termination flag in equality. The
same visible text with different EOF-newline state is therefore represented as
a deletion plus insertion, with the unterminated side followed by the
conventional marker.

## Unicode Model

MoonBit strings use UTF-16 indexing. `String.length()` therefore counts code
units, and a non-BMP character occupies two positions. Indexing and slicing one
position at a time can produce an isolated surrogate.

The public `diff` function converts each input with `String::to_array()`. The
result contains Unicode scalar values (`Char`), so every `Equal`, `Delete`, and
`Insert` value contains a valid complete character.

This is scalar-value safety, not grapheme-cluster segmentation. A visual emoji
sequence can contain several scalar values joined by modifiers or zero-width
joiners.

## Myers Frontier

For old length `N` and new length `M`, the edit graph uses coordinates `(x, y)`:

- moving right deletes one old item;
- moving down inserts one new item;
- moving diagonally over equal items consumes a free matching run, or snake.

A diagonal is identified by `k = x - y`. For each edit depth `d`, the algorithm
stores the furthest reached `x` on every reachable diagonal. A candidate path
comes from either diagonal `k - 1` (delete) or `k + 1` (insert), then advances
over all equal items.

The first frontier reaching `(N, M)` has minimum edit depth `D`, which proves
that the resulting number of insertions plus deletions is minimal.

When insertion and deletion reach equally far, the implementation chooses the
deletion path. This produces stable, deterministic scripts where replacements
appear as deletes followed by inserts.

## Traceback

Each depth stores a snapshot of the previous frontier. Starting at `(N, M)`,
traceback examines the snapshot for depth `d` to identify the predecessor
diagonal:

1. Emit matching diagonal items in reverse as `Keep` steps.
2. Emit one `Remove` or `Add` step for the edit edge.
3. Continue from the predecessor coordinate at depth `d - 1`.
4. Reverse the completed internal step array.

Character and line callers map the internal index steps to public string-based
`EditOp` values.

## Prefix and Suffix Reduction

Character diff removes common edges before invoking Myers. A one-character
change inside a large otherwise-equal string therefore searches only the small
changed middle. The preserved edges are restored as `Equal` operations.

Line diff currently runs Myers over the complete normalized line arrays because
hunk coordinates need the complete sequence.

## Hunk Grouping

`unified_diff_with_context` creates a context window around every changed line.
Overlapping or touching windows are merged. Each resulting range is rendered as
one hunk.

Before rendering a hunk, the implementation counts old and new lines consumed
before the range and within the range. Insertions consume only new lines;
deletions consume only old lines; equal operations consume both. This also
produces correct zero-length ranges such as `-0,0` for insertion before the
first old line.

## Complexity

Let `D` be the minimum number of insertions and deletions:

- frontier search time: `O((N+M)*D)`;
- frontier array size: `O(N+M)`;
- stored traceback snapshots: `O((N+M)*D)`;
- emitted edit script: `O(N+M)`.

For local edits, `D` is small and the trace is substantially smaller than a
full `N*M` matrix. Completely different long inputs remain a worst case because
`D` approaches `N+M`.

## Correctness Invariants

The tests enforce these invariants:

```text
reconstruct_old(diff(old, new)) == old
reconstruct_new(diff(old, new)) == new
stats(diff).delete_count + stats(diff).insert_count == D
compact(diff) represents the same old and new texts
apply(diff(old, new), old) == Ok(new)
apply(invert(diff(old, new)), new) == Ok(old)
```

The corpus includes empty strings, repeated text, line breaks, BMP characters,
emoji, and supplementary-plane characters.