The idea of doing this seems fine, but perhaps the documentation should include a few caveats to cover the following points. (There's lots of ways to write diff, and sadly no best one. This one is for inputs that are fairly similar, or fairly short.)

1. When the edit distance between the inputs is fairly small, the algorithm might find a minimal edit sequence, but it might not. All that is claimed is that applying the Edits to the 'before' gets the 'after'.
2. There is an internal (inaccessible) parameter that controls the maximum length of the returned []Edit. If this bound is hit, the returned []Edit will have sensible edits at the beginning and end of the input, but a big replace in the middle.

See previously #23113, #41980.

See also #45200.

Instead of SortEdits(), maybe func (Edit) Less(Edit) bool would be more general. It's pretty straightforward to plug in via slices.SortFunc(edits, diff.Edit.Less).

I agree that we should guarantee only that the composition of diff.Strings and diff.Apply is the identity, and nothing about the specific edits that it returns. We should probably also define the Unified text form in more detail.

Thanks for the links to related proposals. There's a fair bit of interest in both the narrow concept of text diff as proposed here, and in richer kinds of structured value diff for use in testing. If some form of the latter is accepted into the standard library, then perhaps simple text diff, on which it would depend, would also need to be in the standard library, though not necessarily exposed. I'm going to resist the temptation to argue that this should be a standard package. We can always do that later.

Instead of SortEdits(), maybe func (Edit) Less(Edit) bool would be more general. It's pretty straightforward to plug in via slices.SortFunc(edits, diff.Edit.Less).

I tried that initially, but it turns out to be incorrect: it's imperative that you use sort.Stable for edits since insertions at the same point must preserve their relative order.

I tried that initially, but it turns out to be incorrect: it's imperative that you use sort.Stable for edits since insertions at the same point must preserve their relative order.

There is also a slices.SortStableFunc().

Alternatively, you could add a mechanism to Edit that could help them maintain their relative ordering outside of external context such as a numbered priority. Otherwise, if you need a function to sort a []Edit, the implicit assumption is that an unsorted slice is likely to be obtained from somewhere, but if the relative ordering of the elements of that slice is important than there's also an assumption that that slice will always already be partially ordered correctly. That seems kind of error-prone to me.

the implicit assumption is that an unsorted slice is likely to be obtained from somewhere, but if the relative ordering of the elements of that slice is important than there's also an assumption that that slice will always already be partially ordered correctly. That seems kind of error-prone to me.

The definition of Apply makes clear that the slice of edits is a list, not a set: the relative ordering of insertions is important. But Apply can call SortEdits internally. Within gopls, we use SortEdits after merging lists of edits to the same file, but simple concatenation should suffice. It's also used to ensure to ensure a deterministic order, which some clients have mistakenly assumed.

Perhaps we should remove SortEdits from the API and let gopls implement its own copy of that function.

Can the Strings and Bytes functions be unified behind [byteseq string|[]byte]? Perhaps diff.Of?

Can the Strings and Bytes functions be unified behind [byteseq string|[]byte]? Perhaps diff.Of?

They could, but it seems like a lot of trouble just to achieve name overloading.

The other way around, I feel like it's a lot of work to have duplicate Strings and Bytes functions that work the same way instead of having callers cast their []byte to string or having a single generic function.

The other way around, I feel like it's a lot of work to have duplicate Strings and Bytes functions that work the same way instead of having callers cast their []byte to string or having a single generic function.

The allocation penalty of the bytes conversions for large files when the diff is empty (the common case, which needn't allocate any Edits) is a pretty significant multiple of the cost of the actual diff algorithm: 8x in one quick benchmark of a 10KB file.

There's no need to maintain two versions of the functionality in either case. It's very easy as proposed to just use the same implementation since it doesn't perform any modification in Bytes():

func Strings(before, after string) []Edit {
  return Bytes(
    unsafe.Slice(unsafe.StringData(before), len(before)),
    unsafe.Slice(unsafe.StringData(after), len(after)),
  )
}

Or, so as to avoid the unsafe usage, you could have each of the exported functions call a third, unexported function that's generic like your suggestion. I don't think that's really necessary, though.

it doesn't perform any modification in Bytes():

That's true, but the proof requires auditing a thousand lines of code across half a dozen files, so I hesitate.

The generics approach is safer and more appealing, and it should nicely handle even the intentional differences between bytes and strings. For example, string(x)==string(y) is an efficient way to compare bytestring values, and Edit{New: string(x[i:j])} allocates if and only if x is a []byte. (Sadly golang.org/x/tools still can't use generics quite yet, but soon.)

It may cause significant expansion of the object code though; I should measure.

Chatting with @rsc yesterday he raised a number of interesting questions:

• Should the Edit.New field be a string as proposed, potentially incurring allocation when the input is a []byte slice, or a pair of indices into the "new" text? The latter avoids allocation but requires that the new text be present in order to further interpret the slice of edits.

• Should the order of arguments to Unified be (oldLabel string, oldContent []byte, newLabel string, newContent []byte), alternating labels and contents, so that it's impossible to switch a label and a content by mistake? Personally I'm not sure the risk is so great that it's worth doing. If you execute the statement even once with the arguments switched you'll notice immediately (e.g. your test for an empty diff will fail). And if we provided a string-content variant of Unified (as perhaps we should for both convenience and efficiency) then it would nullify the benefit.

• What exactly is promised regarding the diff? I think we should promise only that the composition Apply(Diff(x, y), x) yields y. For unified diffs we don't have a parser; in practice the one that matters is GNU patch, so we could require that our output can be successfully parsed and applied by it, but GNU patch's "detailed description" of the unified diff format leaves some things unstated.

• The Myers algorithm (without a depth bound) is quadratic. Our implementation does use a depth bound, but may yet generate very suboptimal diffs for large files with widespread edits. (Classic worst case: removing carriage returns before line feeds in Windows text files.) Is that acceptable? Russ added an implementation of Hunt-Szymanski internal to the standard library; it is O(n log n) and based on unique lines.

• Our implementation returns sub-line edits (e.g. the diff for a fix to a single-letter typo may be minimal). Internally it merges and expands these to line granularity when printing unified output, but the function to do this is not exposed. Do real clients want sub-line edits? (gopls does)

• Proposals to add a testing-specific diff function (e.g. testing.Diff) might have an easier time answering some of these questions because the domain is more constrained: typically, in a test, the inputs and outputs small, they are nearly always equal, and the desired output is just unified text, not a list-of-edits data structure. A general purpose API such as this one might need to consider more extreme performance outliers.

For unified diffs we don't have a parser; in practice the one that matters is GNU patch, so we could require that our output can be successfully parsed and applied by it, but GNU patch's "detailed description" of the unified diff format leaves some things unstated.

That sounds like an excellent application for a fuzz test! 🙃

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

On one hand, I would like this to be a generic Diff function that can compare any two []E, which is what cmp needs. However, I recognize that there are a lot of cool optimizations that only exist if we treat []E as essentially a sequence of runes (or bytes).

I think there's utility in providing a Diff that is specialized for text, but would still love to see a Diff that can find the difference between two lists of length n and m given only an equality function (similar to the internal Difference function used by cmp).

This package doesn't seem to be specific to the Go language like others packages in x/tools. From README:

This repository provides the golang.org/x/tools module, comprising various tools and packages mostly for static analysis of Go programs

So why not x/text/diff?

This package doesn't seem to be specific to the Go language like others packages in x/tools. [...] So why not x/text/diff?

The text module is primarily concerned with internationalization and localization, and deals with Unicode normalization, whereas this implementation computes differences over rune sequences without regard to such matters. Also, diff is an important component of typical code transformation tools, which is very much the domain of the x/tools module.

FWIW I think x/text/diff would be a fine home for a diff package - text doesn't have to be all about Unicode. For example text/template is not. But we probably still shouldn't commit to a diff API right now anyway.

I think this package is too special purpose. It's designed for an editor, where sub-line diffs are useful, but there's no point in producing a large number of them.

This issue is actively tracked through the proposal process, presumably it should be re-opened to allow that process to continue?

@pjweinb doesn't seem to be a member of the Go team. How did he close the issue? Shouldn't that be something only the author of the issue or a moderator can do?

Hi, Peter is indeed a member of the Go team, and the main author of the package. The proposal was a joint one, and we are both happy to retract it in light of the various concerns raised. Sorry for the confusion.

@pjweinb, I think there's a good avatar you could use for your Github account online somewhere, so people recognize you.