README
¶
Diff
This package contains a set of diff algorithms that can be used to diff arbitrary sequences.
See the package docs for more information.
The code is MIT licensed -- please see LICENSE.txt for details.
Documentation
¶
Overview ¶
Package diff contains code to produce diffs of arbitrary sequences.
For example, diffing two files (represented as lines of strings), producing a unified diff:
result := diff.UnifiedDiffer(lines1, lines)
for _, line := range result { fmt.Println(line) }
Or to diff two strings character by character:
ss1 = diff.StringSequence("one as .")
ss2 = diff.StringSequence("ike .")
d := diff.NewDiffer().Diff(ss1, ss2)
... process d
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func UnifiedDiff ¶
UnifiedDiff compares left and right line-by-line, returning a unified diff.
Types ¶
type DynamicDiffer ¶
type DynamicDiffer struct{}
DynamicDiffer constructs an optimally short diff using a naive dynamic programming method. It uses O(NM) space and time where N and M are the sizes of the sequences it's asked to diff.
func (DynamicDiffer) Diff ¶
func (DynamicDiffer) Diff(left, right Sequence) []Edit
Diff diffs the two sequences using a naive dynamic programming approach.
type Edit ¶
type Edit struct {
DI, DJ int
}
An Edit describes part of an edit from one sequence to another. (x, x) -> x elements that are the same in both sequences. (x, 0) -> the removal of x lines from the first sequence. (0, x) -> the addition of x lines from the second sequence.
(x, y) where x != 0, y != 0 and x != y is not allowed.
type HashesSequence ¶
type HashesSequence []uint64
A HashesSequence is a slice of hashes.
func (HashesSequence) Fingerprint ¶
func (hs HashesSequence) Fingerprint(idx int) uint64
Fingerprint returns the fingerprint of the indexed hash. In this case, the fingerprint is just the hash itself.
func (HashesSequence) Length ¶
func (hs HashesSequence) Length() int
Length returns the number of hashes in this sequence.
type MyersDiffer ¶
type MyersDiffer struct{}
MyersDiffer constructs an optimally short diff using the algorithm described in "An O(ND) Difference Algorithm and Its Variations" by Eugene Myers.
func (MyersDiffer) Diff ¶
func (MyersDiffer) Diff(left, right Sequence) []Edit
Diff diffs left and right, producting a minimal set of edits.
type PatienceDiffer ¶
type PatienceDiffer struct{}
PatienceDiffer generates diffs using the Patience Diff algorithm. This: 1. Removes matching lines from the start and end of a file 2. Computes the LCS for lines that occur uniquely in both sequences 3. Do step 1 for the sections in between. It's described in http://bramcohen.livejournal.com/73318.html
func (PatienceDiffer) Diff ¶
func (PatienceDiffer) Diff(left, right Sequence) []Edit
Diff diffs left and right, using Bram Cohen's "patience" diffing algorithm.
type Sequence ¶
A Sequence is something that can be diffed against another sequence. Diffs are done based on hashes rather than the underlying sequence for efficiency.
func NewLineSequence ¶
NewLineSequence constructs a Sequence from a slice of lines.
type StringSequence ¶
type StringSequence string
A StringSequence is a Sequence of bytes in a string.
func (StringSequence) Fingerprint ¶
func (ss StringSequence) Fingerprint(idx int) uint64
Fingerprint returns the fingerprint of the character at the given index. The fingerprint in this case is just the character itself.
func (StringSequence) Length ¶
func (ss StringSequence) Length() int
Length returns the length of the string sequence.
type UniqueRunDiffer ¶
type UniqueRunDiffer struct {
D Differ
}
An UniqueRunDiffer isn't a differ itself. Instead, it replaces runs of elements which don't appear in the "other" sequence with a single item before using the underlying differ.
func (UniqueRunDiffer) Diff ¶
func (urd UniqueRunDiffer) Diff(left, right Sequence) []Edit
Diff diffs left and right. First it replaces runs of elements of each sequence that don't appear in the other sequence with a single element, and then calls the underlying differ.
Source Files