diff

README

diff

A Myers diff algorithm implementation in Go. Includes gdiff, a minimal command-line diff tool.

Install

go install github.com/teleivo/diff/cmd/gdiff@latest

Library

import "github.com/teleivo/diff"

edits := diff.Lines(oldLines, newLines)

// Write in unified diff format
diff.Write(os.Stdout, edits)

// Write with gutter format (line numbers, visible whitespace)
diff.Write(os.Stdout, edits, diff.WithGutter())

// Write with ANSI color (red deletions, green insertions)
diff.Write(os.Stdout, edits, diff.WithGutter(), diff.WithColor())

Given a DOT file before and after formatting with dotx:

// old.dot                           // new.dot
digraph {                            digraph {
    3 -> 2 -> 4                          3 -> 2 -> 4
      [color="blue",len=2.6]              [color="blue",len=2.6]
        rank = same                      rank=same
                                     }
}

Unified (gdiff old.dot new.dot):

@@ -1,5 +2,4 @@
 digraph {
 	3 -> 2 -> 4 [color="blue",len=2.6]
-		rank = same
-
+	rank=same
 }

Gutter (gdiff --gutter old.dot new.dot):

1   │ digraph {
2   │ 	3 -> 2 -> 4 [color="blue",len=2.6]
3 - │ →→rank·=·same
4 - │ ↵
  + │ →rank=same
5   │ }

CLI

gdiff file1.txt file2.txt
gdiff --gutter file1.txt file2.txt

Exit codes: 0 (identical), 1 (differences found), 2 (error)

Development

Benchmarks

go test -bench=. | tee results.bench
./plot.sh results.bench

The plots show how time and space scale with sequence length N across two D (edit distance) values, and confirm both implementations match their theoretical complexity.

Profiling

Generate test files and run profiling:

seq 1 100000 > a.txt
seq 1 100000 | awk 'NR%2==0{print $0"x"} NR%2!=0{print}' > b.txt

go build -o gdiff ./cmd/gdiff
./gdiff --cpuprofile cpu.prof --memprofile mem.prof a.txt b.txt > /dev/null

go tool pprof -top cpu.prof
go tool pprof -alloc_space -top mem.prof

Acknowledgments

This implementation is based on James Coglan's great blog series "The Myers Diff Algorithm" which walks through Eugene Myers' 1986 paper "An O(ND) Difference Algorithm and Its Variations".

Disclaimer

I wrote this library for my personal projects and it is provided as-is without warranty. It is tailored to my needs and my intention is not to adjust it to someone else's liking. Feel free to use it!

See LICENSE for full license terms.

Documentation

Overview

Package diff implements the Myers diff algorithm for computing the shortest edit script (SES) between two sequences.

It uses the linear space variant (Section 4b) described in Eugene W. Myers' paper "An O(ND) Difference Algorithm and Its Variations" (1986). It runs in O(ND) time and O(N) space where N is the sum of the lengths of the two sequences and D is the size of the minimum edit script.

Index

• func Write(w io.Writer, edits []Edit, opts ...Option) error
• type Edit
  • func Lines(oldLines, newLines []string) []Edit
• type OpType
  • func (op OpType) String() string
• type Option
  • func WithColor() Option
  • func WithContext(lines int) Option
  • func WithGutter() Option

Functions

func Write

func Write(w io.Writer, edits []Edit, opts ...Option) error

Write writes the edits to w. By default it produces unified diff output with hunk headers and 3 lines of context. Use WithGutter and WithContext to configure the output.

Types

type Edit

type Edit struct {
	Op      OpType
	OldLine string // line from the old sequence (for Del and Eq)
	NewLine string // line from the new sequence (for Ins and Eq)
}

Edit represents a single edit operation in the diff. Line values may include a trailing '\n' delimiter. A line without a trailing '\n' represents the last line of a sequence that has no final newline.

func Lines

func Lines(oldLines, newLines []string) []Edit

Lines computes the shortest edit script to transform oldLines into newLines. It returns a slice of Edit operations that, when applied in order, convert oldLines to newLines. It uses the linear space variant of the Myers algorithm (Section 4b of the paper), which runs in O(ND) time and O(N) space.

type OpType

type OpType int

OpType represents the type of edit operation.

const (
	// Ins indicates a line should be inserted from the new sequence.
	Ins OpType = iota
	// Del indicates a line should be deleted from the old sequence.
	Del
	// Eq indicates the line is equal in both sequences.
	Eq
)

func (OpType) String

func (op OpType) String() string

type Option

type Option func(*config)

Option configures how Write formats its output.

func WithColor

func WithColor() Option

WithColor enables ANSI color output: deletions are red (\033[31m) and insertions are green (\033[32m). The caller is responsible for terminal detection and NO_COLOR handling.

func WithContext

func WithContext(lines int) Option

WithContext sets the number of unchanged lines to show around each change. It panics if lines is negative. The default is 3.

func WithGutter

func WithGutter() Option

WithGutter enables gutter format: each line is prefixed with a line number from the old sequence, an operation indicator, and a │ separator. Whitespace in changed lines is made visible (spaces as ·, tabs as →, trailing newlines as ↵). Runs of identical lines beyond the context window are collapsed into a summary line.