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