TextDiff

The TextDiff module computes edit scripts for arrays and text, applies and inverts them, and formats line differences as unified diffs.

Scripts are computed with Myers' O(ND) algorithm in linear space, after trimming common prefixes and suffixes. Scripts are minimal unless the optional maxEdits search cap is exceeded. Word diffs, semantic cleanup and collaborative editing protocols are out of scope.

14 exports Since v4.0.6 Source

Combinators

apply

Since v4.0.6

Applies an edit script to an array.

Details

Equal and Delete runs consume items from before by count, Equal runs copy them to the result, and Insert runs add their items. Run contents are not compared with before, since under a custom equivalence Equal items can differ from the input.

Gotchas

Fails with a TextDiffError when the runs do not consume exactly before.length items.

See

applyText for the string variant
invert to apply a script in reverse

Signature

declare function apply<A>(before: readonly Array<A>, edits: readonly Array<Edit<A>>): Result<Array<A>, TextDiffError>

Example Replaying a script

import { Result, TextDiff } from "effect"

const edits = TextDiff.diff([1, 2, 3], [1, 3, 4])

TextDiff.apply([1, 2, 3], edits) // => Result.succeed([1, 3, 4])

applyText

Since v4.0.6

Applies a text edit script to a string.

Details

Works with scripts from both lines and codePoints. The joined items of each Equal and Delete run must match before at the current position, so a script made for different text is rejected rather than applied.

Gotchas

Fails with a TextDiffError when a run does not match before, or when the runs do not cover all of it.

See

apply for the array variant

Signature

declare function applyText(before: string, edits: readonly Array<Edit<string>>): Result<string, TextDiffError>

Example Replaying a code point diff

import { Result, TextDiff } from "effect"

const edits = TextDiff.codePoints("cat", "cut")

TextDiff.applyText("cat", edits) // => Result.succeed("cut")

invert

Since v4.0.6

Inverts an edit script, so it turns after back into before.

Details

Swaps the items of each change's Delete and Insert runs, keeping deletions before insertions. Equal runs are unchanged.

Signature

declare function invert<A>(edits: readonly Array<Edit<A>>): Array<Edit<A>>

Example Undoing a change

import { Result, TextDiff } from "effect"

const edits = TextDiff.diff([1, 2], [1, 3])

TextDiff.apply([1, 3], TextDiff.invert(edits)) // => Result.succeed([1, 2])

Constructors

codePoints

Since v4.0.6

Computes a minimal code point edit script between two strings.

Details

Items are Unicode code points, so a surrogate pair is never split between runs. Grapheme clusters, such as an emoji with modifiers or a letter with combining marks, can still be split. The UTF-16 length of a run is the sum of its items' lengths.

Gotchas

Without maxEdits, work is quadratic for unrelated inputs. Set maxEdits when diffing large or untrusted text.

See

lines for a line diff
applyText to replay a script on a string

Signature

declare function codePoints(before: string, after: string, options?: {
  readonly maxEdits?: number;
}): Array<Edit<string>>

Example Diffing code points

import { TextDiff } from "effect"

TextDiff.codePoints("cat", "cut") // => [{ _tag: "Equal", items: ["c"] }, { _tag: "Delete", items: ["a"] }, { _tag: "Insert", items: ["u"] }, { _tag: "Equal", items: ["t"] }]

diff

Since v4.0.6

Computes a minimal edit script between two arrays, comparing items with Equal.equals.

Details

Unless the maxEdits cap is exceeded, the script has the fewest possible inserted plus deleted items. The choice is deterministic, and each change lists its deletions before its insertions.

Gotchas

Without maxEdits, work is quadratic for unrelated inputs. Set maxEdits when diffing large or untrusted arrays.

See

diffWith to compare items with a custom equivalence
apply to replay a script

Signature

declare function diff<A>(before: readonly Array<A>, after: readonly Array<A>, options?: {
  readonly maxEdits?: number;
}): Array<Edit<A>>

Example Diffing two arrays

import { TextDiff } from "effect"

TextDiff.diff([1, 2, 3, 4], [1, 3, 4, 5]) // => [{ _tag: "Equal", items: [1] }, { _tag: "Delete", items: [2] }, { _tag: "Equal", items: [3, 4] }, { _tag: "Insert", items: [5] }]

diffWith

Since v4.0.6

Creates a function that computes a minimal edit script between two arrays using a custom equivalence.

When to use

Use when items should match by key or by a structural comparison other than Equal.equals.

Details

Unless the maxEdits cap is exceeded, the script has the fewest possible inserted plus deleted items. Equal runs carry the items from before, not necessarily the exact values from after.

Gotchas

Without maxEdits, work grows with the product of the input size and the number of differences, which is quadratic for unrelated inputs. Set maxEdits for large or untrusted inputs.

See

diff for the Equal.equals variant

Signature

declare function diffWith<A>(isEquivalent: (self: A, that: A) => boolean): (before: readonly Array<A>, after: readonly Array<A>, options?: {
  readonly maxEdits?: number;
}) => Array<Edit<A>>

Example Matching items by id

import { TextDiff } from "effect"

const diffById = TextDiff.diffWith<{ readonly id: number }>((a, b) => a.id === b.id)

diffById([{ id: 1 }, { id: 2 }], [{ id: 2 }]) // => [{ _tag: "Delete", items: [{ id: 1 }] }, { _tag: "Equal", items: [{ id: 2 }] }]

lines

Since v4.0.6

Computes a minimal line-level edit script between two strings.

Details

Each line keeps its \n terminator, so \n versus \r\n endings and a missing final newline are reported as changes. Joining the items of a run gives the exact text it covers.

Gotchas

Without maxEdits, work is quadratic for unrelated inputs. Set maxEdits when diffing large or untrusted text.

See

codePoints for a code point diff
unified to format a line diff

Signature

declare function lines(before: string, after: string, options?: {
  readonly maxEdits?: number;
}): Array<Edit<string>>

Example Diffing lines

import { TextDiff } from "effect"

TextDiff.lines("a\nb\n", "a\nc\n") // => [{ _tag: "Equal", items: ["a\n"] }, { _tag: "Delete", items: ["b\n"] }, { _tag: "Insert", items: ["c\n"] }]

Errors

TextDiffError

Since v4.0.6

Error returned when an edit script does not fit the input it is applied to.

See

apply and applyText for the operations that return it
isTextDiffError for narrowing unknown values

Signature

declare class TextDiffError extends YieldableError<this> & {
  readonly _tag: "TextDiffError";
} & Readonly<{
  readonly message: string;
}> {
  constructor(args: {
    readonly message: string;
  });
  readonly "~effect/TextDiff/TextDiffError": "~effect/TextDiff/TextDiffError";
}

Example Rejecting a script made for other input

import { Result, TextDiff } from "effect"

const edits = TextDiff.diff([1, 2], [1])

Result.mapError(TextDiff.apply([1], edits), TextDiff.isTextDiffError) // => Result.fail(true)

Formatting

unified

Since v4.0.6

Formats a line edit script as a unified diff.

Details

The script must come from lines, or otherwise hold one line per item. The output follows diff -u: hunks whose context would touch or overlap are merged, and a final line without a newline is followed by \ No newline at end of file. When fromFile or toFile is set, both header lines are emitted and an unset name falls back to the other. A script without changes produces an empty string.

Gotchas

Among equally small diffs, hunks can differ from those of GNU diff or Git, which apply extra heuristics.

See

lines to compute a line diff

Signature

declare function unified(edits: readonly Array<Edit<string>>, options?: {
  readonly context?: number;
  readonly fromFile?: string;
  readonly toFile?: string;
}): string

Example Formatting a unified diff

import { TextDiff } from "effect"

TextDiff.unified(TextDiff.lines("a\nb\n", "a\nc\n")) // => "@@ -1,2 +1,2 @@\n a\n-b\n+c\n"

Guards

isTextDiffError

Since v4.0.6

Checks whether a value is a TextDiffError.

Signature

declare function isTextDiffError(u: unknown): u is TextDiffError

Models

Edit

type

Since v4.0.6

One run of an edit script.

Details

Equal runs carry items kept from before, Delete runs carry items removed from before, and Insert runs carry items added from after. Scripts produced by this module never contain empty runs or two adjacent runs with the same tag, and within each change the Delete run comes before the Insert run.

See

diff to compute an edit script

Signature

type Edit<A> = EditEqual<A> | EditInsert<A> | EditDelete<A>

EditDelete

interface

Since v4.0.6

Run of items present only in the before sequence.

Signature

interface EditDelete<A> {
  readonly _tag: "Delete";
  readonly items: readonly Array<A>;
}

EditEqual

interface

Since v4.0.6

Run of items present in both sequences.

Signature

interface EditEqual<A> {
  readonly _tag: "Equal";
  readonly items: readonly Array<A>;
}

EditInsert

interface

Since v4.0.6

Run of items present only in the after sequence.

Signature

interface EditInsert<A> {
  readonly _tag: "Insert";
  readonly items: readonly Array<A>;
}