Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: testing/cmp: add new package #45200

Open
dsnet opened this issue Mar 24, 2021 · 28 comments
Open

proposal: testing/cmp: add new package #45200

dsnet opened this issue Mar 24, 2021 · 28 comments
Labels
Projects
Milestone

Comments

@dsnet
Copy link
Member

@dsnet dsnet commented Mar 24, 2021

TL;DR, I propose adding github.com/google/go-cmp/cmp to the standard library as testing/cmp.

Determining equality of two values is one of the most common operations needed for a unit test where the test wants to know whether some computed value matches some pre-determined expected value.

Using the Go language and standard library alone, there are two primary options:

For simple cases, these work fine, but are insufficient for more complex cases:

  • The == operator only works on comparable types, which means that it doesn't work for Go slices and maps, which are two common kinds that tests want to compare.
  • The reflect.DeepEqual function is a "recursive relaxation of Go's == operator", but has several short-comings:
    • It provides no ability to customize the comparison, which is increasingly more useful for more complex types.
    • It does not explain why two values are different, which becomes increasingly more helpful for larger values.
    • It blindly compares unexported fields, which causes a test to unfortunately have an implicit dependency on unexported artifacts of types from a module's dependencies (and therefore on undefined behavior).

For many users, the standard library is insufficient, so they turn to third-party packages to perform equality. According to the module proxy, the most common comparison module used is github.com/google/go-cmp with 7264 module dependents (and 25th most imported module). I propose including cmp in the standard library itself.

Why include cmp in the standard library?

The most widely used comparison function in Go is currently reflect.DeepEqual (with ~34k usages of reflect.DeepEqual compared to ~6k usages of cmp.Equal). Inclusion of cmp to the standard library would provide better visibility to it and allow more tests to be written that would have been better off using cmp.Equal rather than reflect.DeepEqual.

A problem with reflect.DeepEqual is that it hampers module authors from making changes to their types that otherwise should be safe to perform. Since reflect.DeepEqual blindly compares unexported fields, it causes a test to have an implicit dependency on the value of unexported fields in types that come from a module's dependency. When the author of one those types changes an unexported field, it surprisingly breaks many brittle tests. Examples of this occurring was when Go1.9 added monotonic timestamp support and the change to the internal representation of time.Time broke hundreds of test at Google. Similar problems occurred with adding/modifying unexported fields to protocol buffer messages. reflect.DeepEqual is a comparison function that looks like it works wells, but may cause the test to be brittle. Furthermore, reflect.DeepEqual does not tell you why two values are different, making it even more challenging for users to diagnose such brittle tests.

As a contributor to the standard library, there are a number of times that I would have liked to use cmp when writing tests in the standard library itself.

How is cmp.Equal similar or different than reflect.DeepEqual?

cmp.Equal is designed to be more expressive than reflect.DeepEqual. It accepts any number of user-specified options that may affect how the comparison is performed. While reflect.DeepEqual is more performant, cmp.Equal is more flexible. Also, cmp.Diff provides a humanly readable report for why two values differ, rather than simply providing a boolean result for whether they differ.

One significant difference from reflect.DeepEqual is that cmp.Equal panics by default when trying to compare unexported fields unless the user explicitly permits it with an cmp.Exporter option. This design decision was to avoid the problems observed with using reflect.DeepEqual at scale mentioned earlier.

Without any options specified, cmp.Equal is identical to reflect.DeepEqual except:

  • cmp.Equal panics when trying to comparing unexported fields
  • cmp.Equal uses a type's Equal method if it has one
  • cmp.Equal has an arguably more correct comparison for graphs
    • reflect.DeepEqual's cycle detection primarily aims to avoid infinite recursion, but does not necessarily verify whether the two graphs have the same topology, while cmp.Equal checks that the graph topology are the same.

(Fun fact) Package reflect is the 15th most imported Go package, but ~77% of the imports (for test files) only do so to use DeepEqual. In 2011, Rob Pike explained that "[reflection] is a powerful tool that should be used with care and avoided unless strictly necessary." I find it ironic that most usages of reflect is to access a function that is arguably not even about Go reflection (i.e., it doesn't provide functionality that mirrors the Go language itself).

How does cmp compare to other comparison packages?

The only other comparison module (within the top 250 most widely used modules) is github.com/go-test/deep with 845 dependents (compared to 7264 dependents for cmp). Package deep is not as flexible as cmp and relies on globals to configure how comparisons are performed.

@gopherbot gopherbot added this to the Proposal milestone Mar 24, 2021
@mvdan
Copy link
Member

@mvdan mvdan commented Mar 24, 2021

I wonder if the package path testing/cmp is appropriate. It's true that many uses will be in tests, but many others will not. And there's nothing about the API that ties it to testing or test packages. Perhaps reflect/cmp?

I generally agree with this proposal; the testing package has been borrowing bits and bops from https://github.com/frankban/quicktest recently such as its Mkdir and Setenv, and I'd love for us to incorporate more of its good ideas. The elephant in the room is its powerful and easy to use comparisons, powered by go-cmp.

Also, have you thought about size? In terms of API and packages (there's also cmpopts), but also when weighing the size of Go in its source and binary forms. A more powerful reflect.DeepEqual doesn't sound particularly heavy at first glance, but the repository contains 50 files containing ~400KiB in total.

@mvdan
Copy link
Member

@mvdan mvdan commented Mar 24, 2021

@rogpeppe
Copy link
Contributor

@rogpeppe rogpeppe commented Mar 24, 2021

As a big fan of the cmp package, this seems like a good idea to me. The API is stable and well tested.

One thought: with generics only a year or so away, I wonder if we should hold on until we can make the signatures generic:

func Diff[T any](x, y T, opts ...Option) string
func Equal[T any](x, y T, opts ...Option) bool

Although the implementation would still be using reflection under the hood, using a type parameter
would make it clear that we're expecting to compare values of the same type, and avoid common mistakes
where values of incompatible types are compared, only for the
comparison to fail at runtime.

The current behaviour would still be available by using Equal[interface{}] or Diff[interface{}].

I'd also support folding the cmpopts package into the root cmp package (I always have difficulty remembering which functionality is in which place).

@dsnet
Copy link
Member Author

@dsnet dsnet commented Mar 24, 2021

I wonder if the package path testing/cmp is appropriate. It's true that many uses will be in tests, but many others will not. And there's nothing about the API that ties it to testing or test packages. Perhaps reflect/cmp?

When cmp was first created, making it a general purpose package was one of the sub-goals. However, since cmp is predominantly used for testing purposes, it chose to use panics for situations where two types just could not be compared. The package's propensity to panicking (and it's relatively slow speed compared to reflect.DeepEqual) makes it unsuitable for non-testing usages.

@dsnet
Copy link
Member Author

@dsnet dsnet commented Mar 24, 2021

Also, have you thought about size? In terms of API and packages (there's also cmpopts), but also when weighing the size of Go in its source and binary forms. A more powerful reflect.DeepEqual doesn't sound particularly heavy at first glance, but the repository contains 50 files containing ~400KiB in total.

Nope. Thanks for raising up the thought. There's some files and functionality that can be removed I believe:

@dsnet
Copy link
Member Author

@dsnet dsnet commented Mar 24, 2021

One thought: with generics only a year or so away, I wonder if we should hold on until we can make the signatures generic:

Interesting thought. I should also note that generics would help with:

I'd also support folding the cmpopts package into the root cmp package (I always have difficulty remembering which functionality is in which place).

Yea, that's been one of my longer term goals. The main reason I haven't done so yet is because adding them in causes the godoc page to be less readable, which is another motivating reason for #44447.

@josharian
Copy link
Contributor

@josharian josharian commented Mar 24, 2021

I'd be happy for github.com/pkg/diff to morph into a useful diff package for std. I'd rather it be in golang.org/x, so that it can be used by all and sundry. (I'm frustrated by various gems locked up in std internal.) I cannot dedicate much time to it in the near future, but would be happy to be involved in API design (and contribute the existing code as a starting point). For that, it's probably time for someone (not me) to file a proposal where we can start discussing what we want out of it.

@rsc
Copy link
Contributor

@rsc rsc commented Mar 24, 2021

@josharian I've been doing various diff investigations off and on for a few years (sic) and had some time last week to hook a bunch of stuff together. I have rather a lot of thoughts, and an implementation of the the O(N)-space Myers algorithm, among others. I completely agree that we should have a standard diff package separate from testing/cmp. I need to take care of a few higher priority things but I intend to write more next month. I've retitled #23113 to make that clear.

@rsc
Copy link
Contributor

@rsc rsc commented Mar 24, 2021

@dsnet My main concern with adding testing/cmp is that it is a very large amount of code and API, especially compared to package testing itself. Just the sheer number of internal packages you listed in #45200 (comment) scares me.

Is it possible to take this opportunity to simplify at all?

@josharian
Copy link
Contributor

@josharian josharian commented Mar 24, 2021

@rsc works for me. I've been thinking about diffs on and off too. :) I look forward to chatting about it when you are ready.

@dsnet
Copy link
Member Author

@dsnet dsnet commented Mar 25, 2021

Is it possible to take this opportunity to simplify at all?

@rsc, my main point from #45200 (comment) was that most of those internal packages can be eliminated since the needed functionality has either been added to the standard library already (e.g., reflect.Value.IsZero) or already exists as an internal package (e.g., internal/fmtsort). The most significant internal package is internal/diff and ideally cmp does not need to implement its own but make use of another general purpose diffing package. I'll continue the discussion on #23113 on how to generalize the diffing algorithm there to be suitable for cmp's needs.

@dsnet
Copy link
Member Author

@dsnet dsnet commented Mar 25, 2021

My main concern with adding testing/cmp is that it is a very large amount of code

@rsc. If it's any consolation, the logic that's concerned with the semantics of whether two values are equal is around ~900 LOC. The remaining complexity comes from the logic to pretty print the difference, which accounts for ~1800 LOC. Most of that complexity is because the the reporter is a relatively large set of heuristics for how to present the difference in a way that is easiest for humans to interpret. The reporter logic was fine tuned over the past years based on user feedback and has been fairly stable for the past year or so.

@rogpeppe
Copy link
Contributor

@rogpeppe rogpeppe commented Mar 25, 2021

I'd also like to mention another possibility: the cmp package has excellent functionality for deep-printing
values, but that's buried in the code and only accessible via cmp.Diff. Printing a value recursively
is often of great value, but neither of the widely used implementations I'm aware of (spew and pretty)
are great, because it's common to need some customisation to make the output readable (for example
by omitting some fields or truncating certain byte slices).

I wonder if it might be a good idea to consider including some deep-printing functionality in the standard library.
The style of the cmp API potentially sets a nice precedent for what a deep printing API might look like.

It would probably be best if it was testing-oriented: like cmp, such a package would probably
need to use unsafe to allow it to call methods on values from unexported fields.

Aside: like @dsnet, I also think that cmp would most happily live at testing/cmp, partly for the above reason.

@komuw
Copy link
Contributor

@komuw komuw commented Mar 25, 2021

but neither of the widely used implementations I'm aware of (spew and pretty)
are great, because it's common to need some customisation to make the output readable (for example
by omitting some fields or truncating certain byte slices).

@rogpeppe I believe sanity-io/litter can do that, if I'm not mistaken.

I completely agree that we should have a standard diff package separate from testing/cmp

@rsc There's also; #41980 which I think would be related.

@smasher164
Copy link
Member

@smasher164 smasher164 commented Mar 28, 2021

I wonder if it might be a good idea to consider including some deep-printing functionality in the standard library.
The style of the cmp API potentially sets a nice precedent for what a deep printing API might look like.

I brought this up on the mailing list at one point: https://groups.google.com/g/golang-nuts/c/Tn0QeDv6fU8/m/ukcrSF6BCwAJ

Deep printing was seen as requiring possibly too much customization, leading to a complex API. And a general mechanism to traverse data structures could live outside the standard library.

Edit: related #28141

myitcv added a commit to rogpeppe/go-internal that referenced this issue Mar 29, 2021
The current version of github.com/pkg/diff.Diff has quadratic behaviour.
This means that when we attempt a diff between relatively modest sized
files, it's easy to find yourself out of memory.

Therefore, when we see a diff between two large files (large defined in
terms of number of lines), tersely report that as if the two were binary
files, i.e. do not try to render the diff.

When github.com/pkg/diff or similar supports a linear algorithm:

golang/go#45200 (comment)

we can revert this change.
myitcv added a commit to rogpeppe/go-internal that referenced this issue Mar 29, 2021
The current version of github.com/pkg/diff.Diff has quadratic behaviour.
This means that when we attempt a diff between relatively modest sized
files, it's easy to find yourself out of memory.

Therefore, when we see a diff between two large files (large defined in
terms of number of lines), tersely report that as if the two were binary
files, i.e. do not try to render the diff.

When github.com/pkg/diff or similar supports a linear algorithm:

golang/go#45200 (comment)

we can revert this change.
myitcv added a commit to rogpeppe/go-internal that referenced this issue Mar 29, 2021
)

The current version of github.com/pkg/diff.Diff has quadratic behaviour.
This means that when we attempt a diff between relatively modest sized
files, it's easy to find yourself out of memory.

Therefore, when we see a diff between two large files (large defined in
terms of number of lines), tersely report that as if the two were binary
files, i.e. do not try to render the diff.

When github.com/pkg/diff or similar supports a linear algorithm:

golang/go#45200 (comment)

we can revert this change.
@rsc rsc moved this from Incoming to Active in Proposals Apr 1, 2021
@rsc
Copy link
Contributor

@rsc rsc commented Apr 1, 2021

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

@rsc rsc changed the title proposal: add testing/cmp proposal: testing/cmp: add new package Apr 1, 2021
@peterbourgon
Copy link
Member

@peterbourgon peterbourgon commented Apr 12, 2021

I use cmp in many of my projects, and would love to see its capabilities become part of the stdlib. But the current package API is unnecessarily complex and esoteric; IMO it would need to be substantially simplified (read: reduced) before it could be realistically considered for inclusion.

@rogpeppe
Copy link
Contributor

@rogpeppe rogpeppe commented Apr 12, 2021

But the current package API is unnecessarily complex and esoteric; IMO it would need to be substantially simplified (read: reduced) before it could be realistically considered for inclusion.

I'm interested in what aspects of the API you see as possibilities for simplification. Personally I've see it as an example of a nice composable API and can't see how it could be simplified much without removing a lot of its usefulness.

As I said above, generics could make the API more obvious. Another example, Transformer could have a generic signature rather than using interface{}:

func Transformer[T, R any](name string, f func(T) R) Option
@peterbourgon
Copy link
Member

@peterbourgon peterbourgon commented Apr 12, 2021

I'm interested in what aspects of the API you see as possibilities for simplification.

With the huge caveat that this is all IMO —

  • Value transformation is out of scope for a comparison package, all transform-related stuff should be dropped outright
  • Value tree analysis is of niche utility at best, it doesn't carry its weight in the API surface and should be removed
  • Custom equality is useful, but cmp generalizes too far, most of the expressive capabilities here can be removed

I think what you're left with is cmp.Equal, cmp.Diff, some way to toggle cmp.AllowUnexported, and a hook to provide your own comparison function. That feels like about the right size and shape for a package like this, to me. I also feel like that's about 90% of the current package's usefulness, anyway.

edit: It might be worth stating explicitly the problem that a package testing/cmp would be solving. I don't think it's providing a powerful and expressive toolkit for arbitrary value comparisons. I think it's just being a nicer reflect.DeepEqual.

@dsnet
Copy link
Member Author

@dsnet dsnet commented Apr 12, 2021

Here's a histogram of all cmp and cmpopt usages according to the latest version of all public modules:

  36273 cmp.Diff
  11808 cmp.Equal
   2516 cmp.Comparer
   2314 cmp.Option
   1929 cmp.AllowUnexported
   1680 cmpopts.IgnoreUnexported
   1654 cmpopts.IgnoreFields
   1509 cmpopts.EquateEmpty
   1334 cmp.Options
    607 cmp.Transformer
    523 cmpopts.SortSlices
    369 cmp.Path
    256 cmp.Result
    243 cmp.FilterPath
    242 cmp.Ignore
    187 cmpopts.IgnoreTypes
    152 cmp.Transform
    130 cmp.FilterValues
    125 cmpopts.EquateNaNs
     92 cmpopts.EquateApprox
     91 cmp.Reporter
     90 cmpopts.EquateErrors
     69 cmpopts.AnyError
     66 cmpopts.IgnoreInterfaces
     54 cmpopts.AcyclicTransformer
     39 cmpopts.EquateApproxTime
     39 cmp.MapIndex
     38 cmp.PathStep
     36 cmpopts.IgnoreMapEntries
     31 cmpopts.IgnoreSliceElements
     28 cmp.Exporter
     26 cmpopts.SortMaps
     23 cmp.StructField
     13 cmp.SliceIndex
      9 cmp.Indirect
      8 cmp.TypeAssertion

Some observations:

  • cmp.{Equal,Diff} are unsurprisingly the most widely used.
  • cmp.Transformer is less widely used than cmp.Comparer, but it's still a non-trivial amount of usages (4:1 ratio).
  • cmpopts.{IgnoreUnexported,IgnoreFields,EquateEmpty} together account for ~5k usages, which is twice the number of cmp.Comparer usages.
  • cmp.{Path,PathStep,StructField,SliceIndex,MapIndex,Indirect,TypeAssertion,Transform} may not be widely used, but they're critical to the operation of cmpopts.{IgnoreUnexported,IgnoreFields,EquateEmpty}, the other cmpopt options, and any custom options that a user may write. We can't just remove them, but we could move them to some other package to hide up-front visibility to them. These types are similar to the reflect package. It's not widely used, but is critical to the operation of widely used packages like encoding/json or text/template.

It might be worth stating explicitly the problem that a package testing/cmp would be solving. I don't think it's providing a powerful and expressive toolkit for arbitrary value comparisons. I think it's just being a nicer reflect.DeepEqual.

In the initial post, I mentioned that one of the shortcomings of reflect.DeepEqual was that "it provides no ability to customize the comparison, which is increasingly more useful for more complex types." Certainly there can be a difference in opinion in how much customization should be permitted, but I'm of the (biased) opinion that at least what's currently in cmp is mostly the right balance. Perhaps, the lesser used functionality (e.g., cmp.Path, cmp.PathStep, and the concrete path step types) can be moved elsewhere out of immediate visibility, but not removed.

@peterbourgon
Copy link
Member

@peterbourgon peterbourgon commented Apr 12, 2021

Certainly there can be a difference in opinion in how much customization should be permitted, but I'm of the (biased) opinion that at least what's currently in cmp is mostly the right balance.

I appreciate that you get value out of what's currently there, but delivering value is just one part of the calculus when deciding whether or not to add a new feature — necessary, but insufficient. The other part is balancing that value with the costs it brings, often to areas like API size and coherence, emergent complexity with other features, and so on.

The (demonstrated!) value of the package is disproportionally weighted in a small part of its API. And the costs it carries are quite high: beyond the very large SLoC, already discussed above, its API is undeniably big, and much of that API is inscrutable without careful study. From where I sit, the calculus just doesn't work — especially not for the stdlib, where the bar is as high as it gets.

(All IMO, of course.)

one of the shortcomings of reflect.DeepEqual was that "it provides no ability to customize the comparison, which is increasingly more useful for more complex types."

Does that customization need to be performed by code that lives in the stdlib? Why is that a better place for it than in x/ somewhere? Or, perhaps better yet, attached to the types that need the customization? Is the need for this kind of customization actually strong and widespread enough that it makes sense to generalize in this way?

@rogpeppe
Copy link
Contributor

@rogpeppe rogpeppe commented Apr 12, 2021

much of that API is inscrutable without careful study

From that, I take away something I've felt before too: that the docs could use a bunch more examples,
particularly in the less-used parts of the API.

That said, I found that the API generally rewards a bit of study; the underlying model is elegant, which counts for a lot IMHO.

For myself, I can think of two things that have made me ponder parts of the existing API in the past:

  • whether the comparison operators really need to be symmetric. Often you're comparing expected against actual and it can make sense for the "expected" to be treated fuzzily (for example by allowing a particularly formatted string to be treated as a regular expression) but the "actual" to be precise.
  • I wanted to do some path-based filtering and found it hard. I can't remember why now :)
@leighmcculloch
Copy link
Contributor

@leighmcculloch leighmcculloch commented Apr 12, 2021

I use go-cmp to do the comparison of objects and it's pretty handy for that, but I've found the diffing capabilities lacking, especially for multiline strings, so I'm not sure it is in a state that it should be merged into the stdlib.

Some test frameworks use github.com/pmezard/go-difflib as it provides much better multiline text diffs. I use it in my own test framework for this reason, and it's also used in the popular stretchr/testify.

If imported, maybe the cmp package should focus on equality only, and not include diffing functionality?

@dsnet
Copy link
Member Author

@dsnet dsnet commented Apr 12, 2021

I've found the diffing capabilities lacking, especially for multiline strings

@leighmcculloch, what version of cmp are you using? Higher fidelity printing of multiline strings has been added since v0.5.0. See this example output.

@Merovius
Copy link

@Merovius Merovius commented Apr 12, 2021

Does that customization need to be performed by code that lives in the stdlib?

FWIW, as it currently stands, the Option interface is opaque. So any 3rd party implementations must be implemented based on the Options that are already there.

Personally, I think this is a bit unfortunate, but I'm not sure how to fix it. In any case, one obvious answer to "the API surface is too big" would be to make it possible/easy to factor out the lesser used options into x/ or 3rd party packages, as @peterbourgon suggests. I think for that, we'd either need to make Option a functionally complete interface that allows 3rd party implementations, or find a minimum orthogonal set of Options that can serve as a basis (the existing ones are obviously a basis, but they don't seem minimal - especially if you include cmpopts).

Personally I'm not convinced cmp should be in the stdlib either. IMO it works just fine as a 3rd party module and I generally agree that the API surface it provides seems a bit unwieldy. I think it might live well in x/ and I think something like it, but a lot smaller could fit into the stdlib. At that point, we're not really talking about "putting go-cmp into the stdlib", but we are talking about "provide a package for better generic comparisons, inspired by go-cmp" and I think we'd need to actually see how that would look, before talking about if it "works" or not.

@Merovius
Copy link

@Merovius Merovius commented Apr 12, 2021

Oh, also, FWIW: When I used go-cmp in the past, but needed more than cmpopts.SortSlices or something of that sort, I found it easier to implement the comparison function directly and use that, instead of trying to fit it into cmp.Equal, which tended to cause a bunch of confusing dynamic type-errors for me. cmp.Diff provides more bang for your buck (as implementing diff is harder), of course. But I found it telling that the API seemingly makes some things more difficult to do with the package, than without.

@seebs
Copy link
Contributor

@seebs seebs commented Apr 20, 2021

In addition to the other issues, I'd note: I frequently want to compare slices such that i consider a nil slice to be equivalent to a non-nil slice of len 0, and reflect.DeepEqual has bitten me on that several times, and worse, done so such that a naive printf of the slices (using %d if they're []int) doesn't show any difference...

Writing a function that compares two things and tells me whether or how they differ has usually been a great return on time spent in improving test quality and outputs, but I've written that function for []int far more often than I should.

@dsnet
Copy link
Member Author

@dsnet dsnet commented Apr 20, 2021

When I used go-cmp in the past, but needed more than cmpopts.SortSlices or something of that sort, I found it easier to implement the comparison function directly

@Merovius. Yea, while cmpopts.SortSlices allows the ability to sort any slice type, I agree that it's not always easy to use. In the case of a simple type (e.g., int), it's unfortunate needing to provide an explicit less function when it's trivial. In the case of a more complex type, the comparison can get complicated and may not be aware of any ignored fields. There's been some discussion about having a generic less function, but there are some non-trivial problems to figure out. In most cases, the user doesn't care about the order, but wants to functionally treat a slice as a multi-set.

#45200 (comment)

@seebs, it's not clear to me whether your comment is in support or opposition towards the proposal. Since cmp.Equal has it's heritage in reflect.DeepEqual it treats []T(nil) and []T{} as inequal. That said, cmp.Diff does clearly show when the difference is due to nil-ness. Also, the cmpopts.EquateEmpty option can be used to treat such cases as equal.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
Linked pull requests

Successfully merging a pull request may close this issue.

None yet