Text Diff Viewer — Python source

"""text-diff — Python port (CosmoDev polyglot showcase).

Computes a diff between two strings at line / word / char granularity using a
classic LCS (longest-common-subsequence) dynamic-programming table. No
third-party dependencies, fully deterministic.

Ported from ``src/lib/text-diff.ts`` — display source, part of CosmoDev's
polyglot tool pages (dev.cosmolabs.org). Behavior is functionally equivalent to
the canonical TypeScript implementation.

Token invariant: every tokenizer splits a string into tokens whose exact
concatenation reconstructs the original, so concatenating every ``DiffPart.text``
in order reconstructs the *changed* string ``b`` (under default options).
"""

from __future__ import annotations

import re
from dataclasses import dataclass
from typing import Literal, Optional


DiffType = Literal["equal", "added", "removed"]
Granularity = Literal["line", "word", "char"]

# Word splitting: the capture group keeps whitespace runs as their own tokens so
# concatenation reconstructs the input exactly.
_WORD_SPLIT = re.compile(r"(\s+)")
# Whitespace collapse for the ignoreWhitespace comparison key.
_WS_RUN = re.compile(r"\s+")


@dataclass
class DiffPart:
    """A single merged run of the diff: a category and its text."""

    type: DiffType
    text: str


@dataclass
class DiffOptions:
    """Comparison-key normalization. The original token is always emitted.

    With all flags False (the default) normalization is the identity function,
    so the reconstruction invariant holds exactly; opting in may relax it.
    """

    ignore_case: bool = False
    trim: bool = False
    ignore_whitespace: bool = False


@dataclass
class DiffSummary:
    """Per-category character counts (granularity-agnostic)."""

    added: int = 0
    removed: int = 0
    unchanged: int = 0


@dataclass
class UnifiedHeaders:
    """Filename labels for the ``---``/``+++`` header lines."""

    old: str = ""
    new: str = ""


def _normalize_key(token: str, opts: DiffOptions) -> str:
    """Normalize a token for COMPARISON only; the original is always emitted.

    Order matters: ignoreWhitespace first (collapse + trim), then an explicit
    trim, then case folding. ``str.lower`` mirrors JavaScript's ``toLowerCase``
    (a Unicode lowercase mapping, not the more aggressive ``casefold``).
    """
    s = token
    if opts.ignore_whitespace:
        s = _WS_RUN.sub(" ", s).strip()
    if opts.trim:
        s = s.strip()
    if opts.ignore_case:
        s = s.lower()
    return s


def tokenize(text: str, granularity: Granularity) -> list[str]:
    """Split ``text`` into reconstructable tokens.

    * ``char`` — code-point split (Python strings are Unicode); concatenation === text.
    * ``word`` — alternating maximal whitespace runs and non-whitespace runs;
      concatenation === text.
    * ``line`` — content-only lines (``text.split('\\n')``); a trailing ``''``
      marks that the text ends with a newline. Reconstruction joins with ``\\n``.
    """
    if text == "":
        return []
    if granularity == "char":
        return list(text)
    if granularity == "word":
        # The capture group keeps separators as tokens; drop the empty strings
        # that appear at the ends / between adjacent runs.
        return [t for t in _WORD_SPLIT.split(text) if t]
    return text.split("\n")  # line


def diff(
    a: str,
    b: str,
    granularity: Granularity = "line",
    opts: Optional[DiffOptions] = None,
) -> list[DiffPart]:
    """Compute a diff between ``a`` (original) and ``b`` (changed).

    Returns merged runs of ``DiffPart``. Uses an LCS dynamic-programming table.
    Opt-in normalization compares on a normalized key but emits the ORIGINAL
    token, so an equal part may carry ``a``'s text.
    """
    if opts is None:
        opts = DiffOptions()

    A = tokenize(a, granularity)
    B = tokenize(b, granularity)
    # Compare on a normalized key; emit the original token.
    a_key = [_normalize_key(t, opts) for t in A]
    b_key = [_normalize_key(t, opts) for t in B]
    n, m = len(a_key), len(b_key)

    # dp[i][j] = length of the LCS of a_key[i..] and b_key[j..], built backwards
    # so each cell only depends on already-computed cells (i+1, j+1).
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        row, nrow, aki = dp[i], dp[i + 1], a_key[i]
        for j in range(m - 1, -1, -1):
            if aki == b_key[j]:
                row[j] = nrow[j + 1] + 1
            elif nrow[j] >= row[j + 1]:
                row[j] = nrow[j]
            else:
                row[j] = row[j + 1]

    # Greedy walk: equal on a key match; otherwise drop the side whose remaining
    # LCS is larger. The ``>=`` tie favors 'removed', matching the canonical walk.
    raw: list[DiffPart] = []
    i = j = 0
    while i < n and j < m:
        if a_key[i] == b_key[j]:
            raw.append(DiffPart("equal", A[i]))
            i += 1
            j += 1
        elif dp[i + 1][j] >= dp[i][j + 1]:
            raw.append(DiffPart("removed", A[i]))
            i += 1
        else:
            raw.append(DiffPart("added", B[j]))
            j += 1
    while i < n:
        raw.append(DiffPart("removed", A[i]))
        i += 1
    while j < m:
        raw.append(DiffPart("added", B[j]))
        j += 1

    # Merge consecutive runs of the same type. Lines rejoin with '\n'; char/word
    # tokens already carry their separators and concatenate with ''.
    sep = "\n" if granularity == "line" else ""
    merged: list[DiffPart] = []
    for r in raw:
        if merged and merged[-1].type == r.type:
            merged[-1].text += sep + r.text
        else:
            merged.append(DiffPart(r.type, r.text))
    return merged


def summary(parts: list[DiffPart]) -> DiffSummary:
    """Count characters per diff category. ``len()`` counts Unicode code points.

    Under opt-in normalization an equal part carries ``a``'s text, so
    ``unchanged`` reflects ``a``'s length, not ``b``'s.
    """
    out = DiffSummary()
    for p in parts:
        length = len(p.text)
        if p.type == "added":
            out.added += length
        elif p.type == "removed":
            out.removed += length
        else:
            out.unchanged += length
    return out


# Lines of context kept around each change in unified output.
_CONTEXT = 3


def _prefix_for(t: DiffType) -> str:
    return "+" if t == "added" else "-" if t == "removed" else " "


def _expand_lines(parts: list[DiffPart]) -> list[DiffPart]:
    """One entry per output line. A trailing newline yields no phantom empty line
    — it terminates the preceding line."""
    entries: list[DiffPart] = []
    for p in parts:
        segs = p.text.split("\n")
        if p.text.endswith("\n"):
            segs.pop()
        for s in segs:
            entries.append(DiffPart(p.type, s))
    return entries


def to_unified_diff(
    parts: list[DiffPart],
    headers: Optional[UnifiedHeaders] = None,
    granularity: Granularity = "line",
) -> str:
    """Render a unified-diff string.

    Emits ``---``/``+++`` header lines when ``headers`` is given. For ``line``
    granularity, groups changes into hunks with 3 lines of context and a
    ``@@ -oldStart,oldLen +newStart,newLen @@`` header per hunk. For
    ``word``/``char`` emits one prefixed line per output line with no hunks.
    """
    out: list[str] = []
    if headers is not None:
        out.append(f"--- {headers.old}")
        out.append(f"+++ {headers.new}")

    entries = _expand_lines(parts)

    if granularity != "line":
        for e in entries:
            out.append(_prefix_for(e.type) + e.text)
        return "\n".join(out)

    # Line granularity: group changes into hunks bounded by _CONTEXT lines.
    changed_idx = [k for k, e in enumerate(entries) if e.type != "equal"]
    if not changed_idx:
        return "\n".join(out)

    last = len(entries) - 1

    # Merge changes within 2*_CONTEXT of each other into one hunk [start..end].
    ranges: list[tuple[int, int]] = []
    cur_start = max(0, changed_idx[0] - _CONTEXT)
    cur_end = min(last, changed_idx[0] + _CONTEXT)
    for k in changed_idx[1:]:
        s = max(0, k - _CONTEXT)
        if s <= cur_end + 1:
            cur_end = min(last, k + _CONTEXT)
        else:
            ranges.append((cur_start, cur_end))
            cur_start, cur_end = s, min(last, k + _CONTEXT)
    ranges.append((cur_start, cur_end))

    for r_start, r_end in ranges:
        # Old side = entries that are not 'added'; new side = not 'removed'.
        old_before = sum(1 for k in range(r_start) if entries[k].type != "added")
        new_before = sum(1 for k in range(r_start) if entries[k].type != "removed")
        old_len = sum(1 for k in range(r_start, r_end + 1) if entries[k].type != "added")
        new_len = sum(1 for k in range(r_start, r_end + 1) if entries[k].type != "removed")
        # Empty-side convention: a length-0 side reports the preceding line number
        # (or 0 at the very start of an empty file).
        old_start = old_before if old_len == 0 else old_before + 1
        new_start = new_before if new_len == 0 else new_before + 1
        out.append(f"@@ -{old_start},{old_len} +{new_start},{new_len} @@")
        for k in range(r_start, r_end + 1):
            out.append(_prefix_for(entries[k].type) + entries[k].text)

    return "\n".join(out)