internal/diff/ndiff.go

// Copyright 2022 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package diff

import (
	"go/token"
	"log"
	"strings"
	"unicode/utf8"

	"golang.org/x/tools/internal/diff/lcs"
	"golang.org/x/tools/internal/span"
)

// maxDiffs is a limit on how deeply the lcs algorithm should search
// the value is just a guess
const maxDiffs = 30

// Strings computes the differences between two strings.
// (Both it and the diff in the myers package have type ComputeEdits, which
// is why the arguments are strings, not []bytes.)
// TODO(adonovan): opt: consider switching everything to []bytes, if
// that's the more common type in practice. Or provide both flavors?
func Strings(uri span.URI, before, after string) []TextEdit {
	if before == after {
		// very frequently true
		return nil
	}
	// the diffs returned by the lcs package use indexes into whatever slice
	// was passed in. TextEdits need a span.Span which is computed with
	// byte offsets, so rune or line offsets need to be converted.
	// TODO(adonovan): opt: eliminate all the unnecessary allocations.
	if needrunes(before) || needrunes(after) {
		diffs, _ := lcs.Compute([]rune(before), []rune(after), maxDiffs/2)
		diffs = runeOffsets(diffs, []rune(before))
		return convertDiffs(uri, diffs, []byte(before))
	} else {
		diffs, _ := lcs.Compute([]byte(before), []byte(after), maxDiffs/2)
		return convertDiffs(uri, diffs, []byte(before))
	}
}

// Lines computes the differences between two list of lines.
// TODO(adonovan): unused except by its test. Do we actually need it?
func Lines(uri span.URI, before, after []string) []TextEdit {
	diffs, _ := lcs.Compute(before, after, maxDiffs/2)
	diffs = lineOffsets(diffs, before)
	return convertDiffs(uri, diffs, []byte(strJoin(before)))
	// the code is not coping with possible missing \ns at the ends
}

// convert diffs with byte offsets into diffs with line and column
func convertDiffs(uri span.URI, diffs []lcs.Diff, src []byte) []TextEdit {
	ans := make([]TextEdit, len(diffs))

	// Reuse the machinery of go/token to convert (content, offset) to (line, column).
	tf := token.NewFileSet().AddFile("", -1, len(src))
	tf.SetLinesForContent(src)

	offsetToPoint := func(offset int) span.Point {
		// Re-use span.ToPosition's EOF workaround.
		// It is infallible if the diffs are consistent with src.
		line, col, err := span.ToPosition(tf, offset)
		if err != nil {
			log.Fatalf("invalid offset: %v", err)
		}
		return span.NewPoint(line, col, offset)
	}

	for i, d := range diffs {
		start := offsetToPoint(d.Start)
		end := start
		if d.End != d.Start {
			end = offsetToPoint(d.End)
		}
		ans[i] = TextEdit{span.New(uri, start, end), d.Text}
	}
	return ans
}

// convert diffs with rune offsets into diffs with byte offsets
func runeOffsets(diffs []lcs.Diff, src []rune) []lcs.Diff {
	var idx int
	var tmp strings.Builder // string because []byte([]rune) is illegal
	for i, d := range diffs {
		tmp.WriteString(string(src[idx:d.Start]))
		v := tmp.Len()
		tmp.WriteString(string(src[d.Start:d.End]))
		d.Start = v
		idx = d.End
		d.End = tmp.Len()
		diffs[i] = d
	}
	return diffs
}

// convert diffs with line offsets into diffs with byte offsets
func lineOffsets(diffs []lcs.Diff, src []string) []lcs.Diff {
	var idx int
	var tmp strings.Builder // bytes/
	for i, d := range diffs {
		tmp.WriteString(strJoin(src[idx:d.Start]))
		v := tmp.Len()
		tmp.WriteString(strJoin(src[d.Start:d.End]))
		d.Start = v
		idx = d.End
		d.End = tmp.Len()
		diffs[i] = d
	}
	return diffs
}

// join lines. (strings.Join doesn't add a trailing separator)
func strJoin(elems []string) string {
	if len(elems) == 0 {
		return ""
	}
	n := 0
	for i := 0; i < len(elems); i++ {
		n += len(elems[i])
	}

	var b strings.Builder
	b.Grow(n)
	for _, s := range elems {
		b.WriteString(s)
		//b.WriteByte('\n')
	}
	return b.String()
}

// need runes is true if the string needs to be converted to []rune
// for random access
func needrunes(s string) bool {
	for i := 0; i < len(s); i++ {
		if s[i] >= utf8.RuneSelf {
			return true
		}
	}
	return false
}