Documentation
¶
Overview ¶
Package textdiff compares two texts line by line: the shortest edit script (Myers, "An O(ND) Difference Algorithm and Its Variations", 1986), grouped into hunks with context, as a unified diff, or as rows for a side-by-side view.
The search is Myers' linear-space refinement: it finds the middle snake of the edit graph from both ends at once and recurses on the two halves, so memory is O(N+M) whatever the distance, and time O((N+M)·D) for D edits. Lines are interned to integers first, so a comparison is one integer test, and the common prefix and suffix are taken off before the search.
Two texts that share almost nothing can make D close to N+M, and the time quadratic. A budget bounds the work: when a sub-problem exceeds it, that part is reported as deleted and inserted as a whole. The script is then still correct (applying it to a gives b) but no longer minimal there, as GNU diff does past its "too expensive" heuristic. Options.Budget sets it; the default keeps two 10 000-line texts with nothing in common well under a second.
Index ¶
Constants ¶
const DefaultBudget = 20_000_000
DefaultBudget is the work allowed when Options.Budget is 0.
Variables ¶
This section is empty.
Functions ¶
func Split ¶
Split cuts a text into lines, without their "\n". A final newline does not make an empty last line, and an empty text has no lines.
Types ¶
type Edit ¶
Edit is one step of the script, in order: A indexes a (Equal, Delete), B indexes b (Equal, Insert). The index an edit does not use is the position in that text where it happens, so a script can be walked with both cursors.
type Hunk ¶
Hunk is a run of changes with the lines of context around it: lines AStart..AStart+ALen of a against BStart..BStart+BLen of b (0-based).
type Options ¶
type Options struct {
// Budget bounds the work of the search, in steps of the edit graph
// (0: DefaultBudget; negative: no bound).
Budget int
}
Options tune the comparison.
type Row ¶
Row is one line of a side-by-side view: A is the line of a on the left, B the line of b on the right, -1 for a blank side. Op is Equal for an unchanged line, Delete for a line only on the left, Insert for a line only on the right; a changed line has both sides and Op Delete.
func SideBySide ¶
SideBySide lays a script out in rows: equal lines face each other, and in each block of changes the deleted lines face the inserted ones in order, the longer side running on against blanks.
Source Files