Skip to content

Discussion: generic version #9

Open
@josharian

Description

@josharian
Contributor

The README says that we're waiting for generics. This issue can serve as a place to discuss that, as the generic proposals roll in.

Unfortunately, the latest generic proposal (summer 2019) doesn't play nicely with the diff package. Quoting myself from some private correspondence with Ian:

The Myer's diff implementation requires input of the form (a, b []T), where some elements of a will be compared for equality with the elements of b. The most common T are string, []byte, and []rune, but I do also want it to be more fully generic. What should the contract for T be?

It can't just be contracts.comparable, because, among other reasons, []byte doesn't support ==.

It's a bit awkward for it to be T Equal(T) bool, because then you need to use a named type for strings just to provide an implementation of Equals, which is the sort of "you've just moved around the boilerplate" problem you mention with interfaces. (This is also reminiscent of the comment on the main thread about intermingling methods and basic types, and the consequent need for type switches that work on contracts.) And you also have to convert from []string to []namedString (or [][]byte to []namedByteSlice) just to do the diff, which is annoying and O(n) instead of O(1).

...

After more pondering, the best solution I've come up with using the current proposal is to accept an equality function and use generic adapters for those. Here's an example, typed straight into email (so use a lenient parser). It uses SameSlice rather than Diff, because it exhibits the same challenges and is much simpler to implement and understand.

func (type T) SameSlice(a, b []T, eq func(T, T) bool) bool {
  if len(a) != len(b) {
    return false
  }
  for i := range a {
    if !eq(a[i],  b[i]) {
      return false
    }
  }
  return true
}

func (type T comparable) builtinEqual(x, y T) bool {
  return x == y
}

Call sites look like:

a := []string{ ... some strings ... }
b := []string{ ... more strings ... }
same := SameSlice(a, b, builtinEqual(string))

Or for [][]byte arguments:

same := SameSlice(a, b, bytes.Equal)

And you could write a generic adapter to go from types with an Equal method to an eq function.

So at least for the moment, I'm going to press forward with a non-generic version. We can re-evaluate if/when the next generics proposal draft arrives.

Activity

mvdan

mvdan commented on Aug 28, 2019

@mvdan
Contributor

+1 to not waiting. A diff package in Go is useful today. Generics might be mainstream two years from now, and like you say, we're not even sure if they will help our API design.

With modules in place, it's always possible and easy to make a v2.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

      Development

      No branches or pull requests

        Participants

        @josharian@mvdan

        Issue actions

          Discussion: generic version · Issue #9 · pkg/diff