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.
5 // Package diff supports a pluggable diff algorithm.
12 "golang.org/x/tools/internal/span"
15 // TextEdit represents a change to a section of a document.
16 // The text within the specified span should be replaced by the supplied new text.
17 type TextEdit struct {
22 // ComputeEdits is the type for a function that produces a set of edits that
23 // convert from the before content to the after content.
24 type ComputeEdits func(uri span.URI, before, after string) []TextEdit
26 // SortTextEdits attempts to order all edits by their starting points.
27 // The sort is stable so that edits with the same starting point will not
29 func SortTextEdits(d []TextEdit) {
30 // Use a stable sort to maintain the order of edits inserted at the same position.
31 sort.SliceStable(d, func(i int, j int) bool {
32 return span.Compare(d[i].Span, d[j].Span) < 0
36 // ApplyEdits applies the set of edits to the before and returns the resulting
38 // It may panic or produce garbage if the edits are not valid for the provided
40 func ApplyEdits(before string, edits []TextEdit) string {
42 // - all of the edits apply to before
43 // - and all the spans for each TextEdit have the same URI
47 _, edits, _ = prepareEdits(before, edits)
48 after := strings.Builder{}
50 for _, edit := range edits {
51 start := edit.Span.Start().Offset()
53 after.WriteString(before[last:start])
56 after.WriteString(edit.NewText)
57 last = edit.Span.End().Offset()
59 if last < len(before) {
60 after.WriteString(before[last:])
65 // LineEdits takes a set of edits and expands and merges them as necessary
66 // to ensure that there are only full line edits left when it is done.
67 func LineEdits(before string, edits []TextEdit) []TextEdit {
71 c, edits, partial := prepareEdits(before, edits)
73 edits = lineEdits(before, c, edits)
78 // prepareEdits returns a sorted copy of the edits
79 func prepareEdits(before string, edits []TextEdit) (*span.TokenConverter, []TextEdit, bool) {
81 c := span.NewContentConverter("", []byte(before))
82 copied := make([]TextEdit, len(edits))
83 for i, edit := range edits {
84 edit.Span, _ = edit.Span.WithAll(c)
87 edit.Span.Start().Offset() >= len(before) ||
88 edit.Span.Start().Column() > 1 || edit.Span.End().Column() > 1
91 return c, copied, partial
94 // lineEdits rewrites the edits to always be full line edits
95 func lineEdits(before string, c *span.TokenConverter, edits []TextEdit) []TextEdit {
96 adjusted := make([]TextEdit, 0, len(edits))
97 current := TextEdit{Span: span.Invalid}
98 for _, edit := range edits {
99 if current.Span.IsValid() && edit.Span.Start().Line() <= current.Span.End().Line() {
100 // overlaps with the current edit, need to combine
101 // first get the gap from the previous edit
102 gap := before[current.Span.End().Offset():edit.Span.Start().Offset()]
103 // now add the text of this edit
104 current.NewText += gap + edit.NewText
105 // and then adjust the end position
106 current.Span = span.New(current.Span.URI(), current.Span.Start(), edit.Span.End())
108 // does not overlap, add previous run (if there is one)
109 adjusted = addEdit(before, adjusted, current)
110 // and then remember this edit as the start of the next run
114 // add the current pending run if there is one
115 return addEdit(before, adjusted, current)
118 func addEdit(before string, edits []TextEdit, edit TextEdit) []TextEdit {
119 if !edit.Span.IsValid() {
122 // if edit is partial, expand it to full line now
123 start := edit.Span.Start()
124 end := edit.Span.End()
125 if start.Column() > 1 {
126 // prepend the text and adjust to start of line
127 delta := start.Column() - 1
128 start = span.NewPoint(start.Line(), 1, start.Offset()-delta)
129 edit.Span = span.New(edit.Span.URI(), start, end)
130 edit.NewText = before[start.Offset():start.Offset()+delta] + edit.NewText
132 if start.Offset() >= len(before) && start.Line() > 1 && before[len(before)-1] != '\n' {
133 // after end of file that does not end in eol, so join to last line of file
134 // to do this we need to know where the start of the last line was
135 eol := strings.LastIndex(before, "\n")
137 // file is one non terminated line
140 delta := len(before) - eol
141 start = span.NewPoint(start.Line()-1, 1, start.Offset()-delta)
142 edit.Span = span.New(edit.Span.URI(), start, end)
143 edit.NewText = before[start.Offset():start.Offset()+delta] + edit.NewText
145 if end.Column() > 1 {
146 remains := before[end.Offset():]
147 eol := strings.IndexRune(remains, '\n')
153 end = span.NewPoint(end.Line()+1, 1, end.Offset()+eol)
154 edit.Span = span.New(edit.Span.URI(), start, end)
155 edit.NewText = edit.NewText + remains[:eol]
157 edits = append(edits, edit)