diffmatchpatch

README

diffmatchpatch

A Go implementation of the Diff Match Patch algorithms by Neil Fraser — computing differences between texts, fuzzy matching, and applying patches.

Install

go get github.com/client9/diffmatchpatch

Usage

Diff

import (
    "context"
    "github.com/client9/diffmatchpatch"
)

diffs := diffmatchpatch.DiffStrings(context.Background(), "Hello, world!", "Goodbye, world!")

for _, d := range diffs {
    switch d.Type {
    case diffmatchpatch.Insert:
        fmt.Printf("+%s", d)
    case diffmatchpatch.Delete:
        fmt.Printf("-%s", d)
    case diffmatchpatch.Equal:
        fmt.Printf(" %s", d)
    }
}

Use context.WithTimeout to limit how long the diff computation runs:

ctx, cancel := context.WithTimeout(context.Background(), 100*time.Millisecond)
defer cancel()
diffs := diffmatchpatch.DiffStrings(ctx, text1, text2)

Three diff entry points are available:

Function	Granularity
DiffStrings(ctx, s1, s2)	character
DiffRunes(ctx, r1, r2)	rune slice
DiffLines(ctx, s1, s2)	line, then character within changed blocks

Cleanup

Raw diffs can be semantically or operationally refined:

diffs = diffmatchpatch.CleanupSemantic(diffs)       // align edits to word/line boundaries
diffs = diffmatchpatch.CleanupEfficiency(diffs, 4)  // eliminate cheap equalities

Match

Locate the best approximate match for a pattern within a text:

m := diffmatchpatch.Matcher{
    Threshold: 0.5,  // 0 = exact only, 1 = match anything
    Distance:  1000, // how far from loc to search
}
loc := m.Match(text, pattern, expectedLoc)
// returns -1 if no match found within threshold

Patch

p := diffmatchpatch.Patcher{
    DeleteThreshold: 0.5,
    Margin:          4,
    EditCost:        4,
    Matcher: diffmatchpatch.Matcher{
        Threshold: 0.5,
        Distance:  1000,
    },
}

// Create patches
patches := p.Make(context.Background(), original, revised)

// Serialize / deserialize (serial subpackage — see Serialization section)
text := serial.PatchToText(patches)
patches, err := serial.PatchFromText(text)

// Apply
result, applied := p.Apply(context.Background(), patches, target)

applied is a []bool with one entry per patch (large patches are split to fit within the platform's Bitap word size, so len(applied) may exceed len(patches)).

Utilities

diffmatchpatch.TranslateIndex(diffs, i)  // map index from text1 to text2

Serialization

The serial subpackage provides text serialization for both diffs and patches. These formats use URI encoding for compatibility with the original JavaScript implementation and other diff-match-patch ports.

import "github.com/client9/diffmatchpatch/serial"

// Compact cross-language diff encoding
encoded := serial.ToDelta(diffs)
diffs, err := serial.FromDelta(text1, encoded)

// Patch text format (unified-diff-like, but character-granularity)
text := serial.PatchToText(patches)
patches, err := serial.PatchFromText(text)

License

This code is licensed under MIT

The original code is licensed under Apache 2.0.

Documentation

Overview

Package diffmatchpatch implements the Diff Match Patch algorithms for computing differences between two texts, fuzzy matching, and applying patches. Ported from Neil Fraser's original implementation at https://github.com/google/diff-match-patch.

Index

• func TranslateIndex(diffs []Diff, loc int) int
• type Diff
  • func CleanupEfficiency(diffs []Diff, editCost int) []Diff
  • func CleanupMerge(diffs []Diff) []Diff
  • func CleanupSemantic(diffs []Diff) []Diff
  • func CleanupSemanticLossless(diffs []Diff) []Diff
  • func DiffLines(ctx context.Context, s1, s2 string) []Diff
  • func DiffRunes(ctx context.Context, r1, r2 []rune) []Diff
  • func DiffStrings(ctx context.Context, s1, s2 string) []Diff
  • func (d Diff) String() string
• type LinesToRunesResult
  • func LinesToRunes(text1, text2 string) LinesToRunesResult
• type Matcher
  • func (m Matcher) Match(text, pattern string, loc int) int
• type Operation
• type Patch
• type Patcher
  • func (p Patcher) Apply(ctx context.Context, patches []Patch, text string) (string, []bool)
  • func (p Patcher) Make(ctx context.Context, text1, text2 string) []Patch
  • func (p Patcher) MakeFromDiffs(diffs []Diff) []Patch
  • func (p Patcher) MakeFromTextAndDiffs(text1 string, diffs []Diff) []Patch

Functions

func TranslateIndex

func TranslateIndex(diffs []Diff, loc int) int

TranslateIndex maps a rune index in text1 to the corresponding rune index in text2, accounting for insertions and deletions described by diffs.

Types

type Diff

type Diff struct {
	Type Operation
	Text []rune
}

Diff represents a single edit operation on a piece of text.

func CleanupEfficiency

func CleanupEfficiency(diffs []Diff, editCost int) []Diff

CleanupEfficiency reduces diffs by eliminating operationally trivial equalities. editCost is the minimum rune count of an equality that is worth preserving; equalities shorter than this threshold are converted to insert/delete pairs. A value of 4 is typical.

func CleanupMerge

func CleanupMerge(diffs []Diff) []Diff

CleanupMerge reorders and merges like edit sections.

func CleanupSemantic

func CleanupSemantic(diffs []Diff) []Diff

CleanupSemantic reduces diffs by eliminating semantically trivial equalities.

func CleanupSemanticLossless

func CleanupSemanticLossless(diffs []Diff) []Diff

CleanupSemanticLossless shifts edits to align on word/line boundaries.

func DiffLines

func DiffLines(ctx context.Context, s1, s2 string) []Diff

DiffLines diffs two strings using a two-pass algorithm. The first pass operates at line granularity to quickly locate changed regions; the second pass re-diffs each changed region at character level to produce precise intra-line edits. The returned diffs therefore contain character-level operations, not whole-line ones. To diff at line granularity only, encode lines as runes with DiffRunes. Use context.WithTimeout to bound execution time; context.Background() for no limit.

func DiffRunes

func DiffRunes(ctx context.Context, r1, r2 []rune) []Diff

DiffRunes computes the differences between two rune slices. Use context.WithTimeout to bound execution time; context.Background() for no limit.

func DiffStrings

func DiffStrings(ctx context.Context, s1, s2 string) []Diff

DiffStrings computes character-level differences between two strings. Use context.WithTimeout to bound execution time; context.Background() for no limit.

func (Diff) String

func (d Diff) String() string

String returns the text of the diff as a string.

type LinesToRunesResult

type LinesToRunesResult struct {
	Text1 []rune   // text1, encoded as one rune per line
	Text2 []rune   // text2, encoded as one rune per line
	Lines []string // Lines[r] is the line text for rune value r
}

LinesToRunesResult holds the output of LinesToRunes: two texts encoded one rune per line, plus the table mapping each rune value back to its line. Diffing Text1/Text2 with DiffRunes and expanding the result through Lines yields a line-granularity diff.

func LinesToRunes

func LinesToRunes(text1, text2 string) LinesToRunesResult

LinesToRunes encodes two texts into rune sequences where each rune value is an index into the returned Lines table — the encoding DiffLines uses internally to line-diff before re-diffing changed regions at character level. Exposed for callers that want pure line-level diffing instead: feed Text1/Text2 to DiffRunes, then look up each result rune in Lines.

Line counts are capped (40000 for text1, 65535 for text2, matching other diff-match-patch ports); text beyond the cap is folded into one final line per text so encoding stays bounded on huge inputs.

type Matcher

type Matcher struct {
	// Threshold controls how loosely to match (0.0 = perfect, 1.0 = very loose).
	Threshold float32
	// Distance is how far from loc to search (0 = exact location only).
	Distance int
}

Matcher performs fuzzy text matching with configurable accuracy.

func (Matcher) Match

func (m Matcher) Match(text, pattern string, loc int) int

Match locates the best instance of pattern in text near loc and returns the rune index of the match, or -1 if no match is found within the configured Threshold and Distance.

type Operation

type Operation int

Operation is the type of a diff edit operation.

const (
	Delete Operation = iota // Delete marks text present in text1 but absent from text2.
	Insert                  // Insert marks text absent from text1 but present in text2.
	Equal                   // Equal marks text identical in both text1 and text2.
)

type Patch

type Patch struct {
	Diffs   []Diff
	Start1  int // start position in text1 (source)
	Start2  int // start position in text2 (target)
	Length1 int // length of the affected region in text1
	Length2 int // length of the affected region in text2
}

Patch represents a set of diffs to apply to a text.

type Patcher

type Patcher struct {
	// DeleteThreshold is the maximum acceptable edit-distance ratio between the
	// expected and matched text when applying a patch fuzzily. Patches whose
	// ratio exceeds this value are rejected. 0 requires an exact match; 0.5
	// tolerates up to half the source text being different.
	DeleteThreshold float32
	// Margin is the number of context runes included around each change in a
	// patch, and the minimum buffer size used when splitting oversized patches.
	// A value of 4 is typical.
	Margin int
	// EditCost is passed to CleanupEfficiency in Make to convert short equalities
	// into insert/delete pairs before building patches. A value of 4 is typical.
	// It is not used by MakeFromTextAndDiffs or MakeFromDiffs.
	EditCost int
	// Matcher is the fuzzy-match configuration used to locate patch positions
	// during Apply.
	Matcher Matcher
}

Patcher holds configuration for computing and applying patches. The zero value is valid but conservative: a DeleteThreshold of 0 rejects any imperfect match, and a Margin of 0 includes no context around changes. Typical values: DeleteThreshold 0.5, Margin 4, EditCost 4, Matcher{Threshold: 0.5, Distance: 1000}.

func (Patcher) Apply

func (p Patcher) Apply(ctx context.Context, patches []Patch, text string) (string, []bool)

Apply applies patches to text and returns the patched text along with a boolean result per patch indicating whether it was applied successfully. Patches that span more than bitapMaxBits runes are split internally, so the results slice may be longer than the input patches slice. A patch is rejected if its location cannot be found within Matcher.Threshold or if the fuzzy edit-distance ratio exceeds DeleteThreshold. Use context.WithTimeout to limit time spent on fuzzy re-diffing.

func (Patcher) Make

func (p Patcher) Make(ctx context.Context, text1, text2 string) []Patch

Make computes patches to transform text1 into text2. It diffs the two texts, applies CleanupSemantic and CleanupEfficiency (using EditCost), then builds the patch list. Use context.WithTimeout to limit the diff computation time.

func (Patcher) MakeFromDiffs

func (p Patcher) MakeFromDiffs(diffs []Diff) []Patch

MakeFromDiffs computes patches from diffs alone, reconstructing text1 from the Delete and Equal segments. Prefer MakeFromTextAndDiffs when text1 is already available.

func (Patcher) MakeFromTextAndDiffs

func (p Patcher) MakeFromTextAndDiffs(text1 string, diffs []Diff) []Patch

MakeFromTextAndDiffs computes patches that transform text1 into text2, where diffs describes that transformation. text1 must be consistent with the Delete and Equal operations in diffs. Returns nil if diffs is empty.