ndiff.go

     1  // Copyright 2022 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
     6  
     7  import (
     8  	"bytes"
     9  	"strings"
    10  	"unicode/utf8"
    11  
    12  	"golang.org/x/tools/internal/diff/lcs"
    13  )
    14  
    15  // Lines computes differences between two strings. All edits are at line boundaries.
    16  func Lines(before, after string) []Edit {
    17  	beforeLines, bOffsets := splitLines(before)
    18  	afterLines, _ := splitLines(after)
    19  	diffs := lcs.DiffLines(beforeLines, afterLines)
    20  
    21  	// Convert from LCS diffs to Edits
    22  	res := make([]Edit, len(diffs))
    23  	for i, d := range diffs {
    24  		res[i] = Edit{
    25  			Start: bOffsets[d.Start],
    26  			End:   bOffsets[d.End],
    27  			New:   strings.Join(afterLines[d.ReplStart:d.ReplEnd], ""),
    28  		}
    29  	}
    30  	return res
    31  }
    32  
    33  // Strings computes the differences between two strings.
    34  // The resulting edits respect rune boundaries.
    35  func Strings(before, after string) []Edit {
    36  	if before == after {
    37  		return nil // common case
    38  	}
    39  
    40  	if isASCII(before) && isASCII(after) {
    41  		// TODO(adonovan): opt: specialize diffASCII for strings.
    42  		return diffASCII([]byte(before), []byte(after))
    43  	}
    44  	return diffRunes([]rune(before), []rune(after))
    45  }
    46  
    47  // Bytes computes the differences between two byte slices.
    48  // The resulting edits respect rune boundaries.
    49  func Bytes(before, after []byte) []Edit {
    50  	if bytes.Equal(before, after) {
    51  		return nil // common case
    52  	}
    53  
    54  	if isASCII(before) && isASCII(after) {
    55  		return diffASCII(before, after)
    56  	}
    57  	return diffRunes(runes(before), runes(after))
    58  }
    59  
    60  func diffASCII(before, after []byte) []Edit {
    61  	diffs := lcs.DiffBytes(before, after)
    62  
    63  	// Convert from LCS diffs.
    64  	res := make([]Edit, len(diffs))
    65  	for i, d := range diffs {
    66  		res[i] = Edit{d.Start, d.End, string(after[d.ReplStart:d.ReplEnd])}
    67  	}
    68  	return res
    69  }
    70  
    71  func diffRunes(before, after []rune) []Edit {
    72  	diffs := lcs.DiffRunes(before, after)
    73  
    74  	// The diffs returned by the lcs package use indexes
    75  	// into whatever slice was passed in.
    76  	// Convert rune offsets to byte offsets.
    77  	res := make([]Edit, len(diffs))
    78  	lastEnd := 0
    79  	utf8Len := 0
    80  	for i, d := range diffs {
    81  		utf8Len += runesLen(before[lastEnd:d.Start]) // text between edits
    82  		start := utf8Len
    83  		utf8Len += runesLen(before[d.Start:d.End]) // text deleted by this edit
    84  		res[i] = Edit{start, utf8Len, string(after[d.ReplStart:d.ReplEnd])}
    85  		lastEnd = d.End
    86  	}
    87  	return res
    88  }
    89  
    90  // runes is like []rune(string(bytes)) without the duplicate allocation.
    91  func runes(bytes []byte) []rune {
    92  	n := utf8.RuneCount(bytes)
    93  	runes := make([]rune, n)
    94  	for i := range n {
    95  		r, sz := utf8.DecodeRune(bytes)
    96  		bytes = bytes[sz:]
    97  		runes[i] = r
    98  	}
    99  	return runes
   100  }
   101  
   102  // runesLen returns the length in bytes of the UTF-8 encoding of runes.
   103  func runesLen(runes []rune) (len int) {
   104  	for _, r := range runes {
   105  		len += utf8.RuneLen(r)
   106  	}
   107  	return len
   108  }
   109  
   110  // isASCII reports whether s contains only ASCII.
   111  func isASCII[S string | []byte](s S) bool {
   112  	for i := 0; i < len(s); i++ {
   113  		if s[i] >= utf8.RuneSelf {
   114  			return false
   115  		}
   116  	}
   117  	return true
   118  }
   119
View as plain text