| 1 | // Copyright 2019 The Go Authors. All rights reserved. |
|---|---|
| 2 | // Use of this source code is governed by a BSD-style |
| 3 | // license that can be found in the LICENSE file. |
| 4 | |
| 5 | // Package diff computes differences between text files or strings. |
| 6 | package diff |
| 7 | |
| 8 | import ( |
| 9 | "fmt" |
| 10 | "sort" |
| 11 | "strings" |
| 12 | ) |
| 13 | |
| 14 | // An Edit describes the replacement of a portion of a text file. |
| 15 | type Edit struct { |
| 16 | Start, End int // byte offsets of the region to replace |
| 17 | New string // the replacement |
| 18 | } |
| 19 | |
| 20 | // Apply applies a sequence of edits to the src buffer and returns the |
| 21 | // result. Edits are applied in order of start offset; edits with the |
| 22 | // same start offset are applied in they order they were provided. |
| 23 | // |
| 24 | // Apply returns an error if any edit is out of bounds, |
| 25 | // or if any pair of edits is overlapping. |
| 26 | func Apply(src string, edits []Edit) (string, error) { |
| 27 | edits, size, err := validate(src, edits) |
| 28 | if err != nil { |
| 29 | return "", err |
| 30 | } |
| 31 | |
| 32 | // Apply edits. |
| 33 | out := make([]byte, 0, size) |
| 34 | lastEnd := 0 |
| 35 | for _, edit := range edits { |
| 36 | if lastEnd < edit.Start { |
| 37 | out = append(out, src[lastEnd:edit.Start]...) |
| 38 | } |
| 39 | out = append(out, edit.New...) |
| 40 | lastEnd = edit.End |
| 41 | } |
| 42 | out = append(out, src[lastEnd:]...) |
| 43 | |
| 44 | if len(out) != size { |
| 45 | panic("wrong size") |
| 46 | } |
| 47 | |
| 48 | return string(out), nil |
| 49 | } |
| 50 | |
| 51 | // validate checks that edits are consistent with src, |
| 52 | // and returns the size of the patched output. |
| 53 | // It may return a different slice. |
| 54 | func validate(src string, edits []Edit) ([]Edit, int, error) { |
| 55 | if !sort.IsSorted(editsSort(edits)) { |
| 56 | edits = append([]Edit(nil), edits...) |
| 57 | SortEdits(edits) |
| 58 | } |
| 59 | |
| 60 | // Check validity of edits and compute final size. |
| 61 | size := len(src) |
| 62 | lastEnd := 0 |
| 63 | for _, edit := range edits { |
| 64 | if !(0 <= edit.Start && edit.Start <= edit.End && edit.End <= len(src)) { |
| 65 | return nil, 0, fmt.Errorf("diff has out-of-bounds edits") |
| 66 | } |
| 67 | if edit.Start < lastEnd { |
| 68 | return nil, 0, fmt.Errorf("diff has overlapping edits") |
| 69 | } |
| 70 | size += len(edit.New) + edit.Start - edit.End |
| 71 | lastEnd = edit.End |
| 72 | } |
| 73 | |
| 74 | return edits, size, nil |
| 75 | } |
| 76 | |
| 77 | // SortEdits orders a slice of Edits by (start, end) offset. |
| 78 | // This ordering puts insertions (end = start) before deletions |
| 79 | // (end > start) at the same point, but uses a stable sort to preserve |
| 80 | // the order of multiple insertions at the same point. |
| 81 | // (Apply detects multiple deletions at the same point as an error.) |
| 82 | func SortEdits(edits []Edit) { |
| 83 | sort.Stable(editsSort(edits)) |
| 84 | } |
| 85 | |
| 86 | type editsSort []Edit |
| 87 | |
| 88 | func (a editsSort) Len() int { return len(a) } |
| 89 | func (a editsSort) Less(i, j int) bool { |
| 90 | if cmp := a[i].Start - a[j].Start; cmp != 0 { |
| 91 | return cmp < 0 |
| 92 | } |
| 93 | return a[i].End < a[j].End |
| 94 | } |
| 95 | func (a editsSort) Swap(i, j int) { a[i], a[j] = a[j], a[i] } |
| 96 | |
| 97 | // lineEdits expands and merges a sequence of edits so that each |
| 98 | // resulting edit replaces one or more complete lines. |
| 99 | // See ApplyEdits for preconditions. |
| 100 | func lineEdits(src string, edits []Edit) ([]Edit, error) { |
| 101 | edits, _, err := validate(src, edits) |
| 102 | if err != nil { |
| 103 | return nil, err |
| 104 | } |
| 105 | |
| 106 | // Do all edits begin and end at the start of a line? |
| 107 | // TODO(adonovan): opt: is this fast path necessary? |
| 108 | // (Also, it complicates the result ownership.) |
| 109 | for _, edit := range edits { |
| 110 | if edit.Start >= len(src) || // insertion at EOF |
| 111 | edit.Start > 0 && src[edit.Start-1] != '\n' || // not at line start |
| 112 | edit.End > 0 && src[edit.End-1] != '\n' { // not at line start |
| 113 | goto expand |
| 114 | } |
| 115 | } |
| 116 | return edits, nil // aligned |
| 117 | |
| 118 | expand: |
| 119 | expanded := make([]Edit, 0, len(edits)) // a guess |
| 120 | prev := edits[0] |
| 121 | // TODO(adonovan): opt: start from the first misaligned edit. |
| 122 | // TODO(adonovan): opt: avoid quadratic cost of string += string. |
| 123 | for _, edit := range edits[1:] { |
| 124 | between := src[prev.End:edit.Start] |
| 125 | if !strings.Contains(between, "\n") { |
| 126 | // overlapping lines: combine with previous edit. |
| 127 | prev.New += between + edit.New |
| 128 | prev.End = edit.End |
| 129 | } else { |
| 130 | // non-overlapping lines: flush previous edit. |
| 131 | expanded = append(expanded, expandEdit(prev, src)) |
| 132 | prev = edit |
| 133 | } |
| 134 | } |
| 135 | return append(expanded, expandEdit(prev, src)), nil // flush final edit |
| 136 | } |
| 137 | |
| 138 | // expandEdit returns edit expanded to complete whole lines. |
| 139 | func expandEdit(edit Edit, src string) Edit { |
| 140 | // Expand start left to start of line. |
| 141 | // (delta is the zero-based column number of of start.) |
| 142 | start := edit.Start |
| 143 | if delta := start - 1 - strings.LastIndex(src[:start], "\n"); delta > 0 { |
| 144 | edit.Start -= delta |
| 145 | edit.New = src[start-delta:start] + edit.New |
| 146 | } |
| 147 | |
| 148 | // Expand end right to end of line. |
| 149 | // (endCol is the zero-based column number of end.) |
| 150 | end := edit.End |
| 151 | if endCol := end - 1 - strings.LastIndex(src[:end], "\n"); endCol > 0 { |
| 152 | if nl := strings.IndexByte(src[end:], '\n'); nl < 0 { |
| 153 | edit.End = len(src) // extend to EOF |
| 154 | } else { |
| 155 | edit.End = end + nl + 1 // extend beyond \n |
| 156 | } |
| 157 | edit.New += src[end:edit.End] |
| 158 | } |
| 159 | |
| 160 | return edit |
| 161 | } |
| 162 |
Members