proposal: strings: add func CommonPrefixLen(x, y string) int

[adonovan]

A common recurring operation on strings is to remove or advance past the common prefix of two strings. Here are some examples from the main Go repository and the golang.org/x/tools repo:

https://github.com/golang/tools/blob/master/go/internal/gcimporter/bexport.go#L264
https://github.com/golang/tools/blob/master/internal/lsp/source/comment.go#L229
https://github.com/golang/go/blob/master/src/cmd/compile/internal/base/timings.go#L122
https://github.com/golang/go/blob/master/src/cmd/compile/internal/ir/dump.go#L129
https://github.com/golang/go/blob/master/src/strings/replace.go#L170
https://github.com/golang/go/blob/master/src/net/addrselect.go#L199
https://github.com/golang/go/blob/master/src/go/printer/printer.go#L485
https://github.com/golang/go/blob/master/src/go/doc/comment/parse.go#L397

This function is easy enough to implement by hand:

commonLen :=  min(len(a), len(b))
for i = 0; i < commonLen && a[i] == b[i]; i++ {}

but it's possible to make it significantly faster than the naive version. This CL contains a version that runs 6x faster yet is still safe and portable. The code describes ways that it might be made much faster still at the cost of unsafe or assembly:
https://go-review.googlesource.com/c/go/+/408116

While benchmarking and optimizing a diff algorithm this week, I noticed that one of the main profiling hotspots was, in essence, a CommonPrefixLen operation:
https://go-review.googlesource.com/c/tools/+/396855/11/internal/lsp/diff/lcs/old.go#219
(It's a little hard to see in this form, but in a private branch I refactored the code so that the dynamic dispatch of eq(x, y byte) was moved outside the loop. In essence the primitive operation over which this algorithm is abstracted is CommonPrefixLen.)

I propose that we add func CommonPrefixLen(x, y string) int to the standard strings package. An analogous function should be added to the bytes package too.

We could also add a CommonPrefix(x, y string) string function, which actually strips off the prefix rather than merely returning its length, but I don't think this is necessary as it is trivial to implement. Also, whereas CommonPrefixLen makes sense for bytes, it's less clear what bytes.CommonPrefix should do, since its result must alias one of the arguments. The first one presumably? Better to avoid the question.

[robpike]

CommonPrefixLen is harder to use and less intuitive. I hear your argument against CommonPrefix but there is an easy rebuttal, as suggested by yourself and by this proposed doc comment.

CommonPrefix returns the longest prefix shared by the two arguments. The return value is sliced from the first argument.

If you don't like that way around, flip the arguments.

[SeanTolstoyevski]

Both functions will be useful for Golang developers.
If this is accepted, I suggest both added to the standard library.

[rhysh]

I'd expect a function in the bytes package would operate on bytes. But several functions in the strings package operate specifically on runes. Would CommonPrefix{,Len} split UTF-8 runes?

https://go.dev/play/p/DfUyiNfhvmI

"¼" ¼ 0xc2bc [U+00BC]
"½" ½ 0xc2bd [U+00BD]
"\xc2" � 0xc2 [U+FFFD]

[robpike]

@rhysh Very good question.

[adonovan]

[rob] CommonPrefixLen is harder to use and less intuitive.

In the linked examples, the specific callers want the Len variant in a slim majority of cases. I'd be ok with just CommonPrefix though.

[rhys] But several functions in the strings package operate specifically on runes. Would CommonPrefix{,Len} split UTF-8 runes?

Yes. Though this would make it the first function in the strings package that, when given UTF-8 arguments, does not always return a UTF-8 result.

[rsc]

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

[icholy]

Appears that there are 5 possible variations here:

1. strings.CommonPrefixLen operates on bytes, returns # of bytes
2. strings.CommonPrefixLen operates on runes, returns # of bytes
3. strings.CommonPrefixLen operates on runes, returns # of runes (probably useless)
4. strings.CommonPrefix operates on bytes, returns slice of first arg.
5. strings.CommonPrefix operates on runes, returns slice of first arg.

Yes. Though this would make it the first function in the strings package that, when given UTF-8 arguments, does not always return a UTF-8 result.

Would the UTF-8 aware versions of these functions be compatible with the examples you presented?

[rsc]

If we add to strings, we should add to bytes, which says 'Package bytes implements functions for the manipulation of byte slices. It is analogous to the facilities of the strings package.' I also expect that strings.CommonPrefixLen(string(x), string(y)) == bytes.CommonPrefixLen(x, y). I should never be surprised by changing code that works on strings to work on []byte by s/strings./bytes./g.

Of course, once you get to combining characters, even UTF-8 boundaries are not always right. So maybe it should be bytes always.

Looking at the examples, it does seem that many of them want the length anyway, so returning the length and avoiding the "which one gets sliced" might be best.

That gets us to "bytes only - no UTF-8 worries - and returning the length".

func CommonPrefixLen(x, y string) int {
    n := 0
    for n < len(x) && n < len(y) && x[n] == y[n] {
        n++
    }
    return n
}

And same for []byte. What do people think?

[robpike]

I think it's more helpful to slice the result than return its length, only to slice it again, so maybe it should go in anyway. It just seems more natural as an API. If you want both, though, that's fine. And those examples don't feel representative to me, but then I don't write the kind of code others do.

Which will you slice? As I said, do and document the first argument.

[rsc]

The arguments in favor of CommonPrefixLen are that
(1) it avoids the "which is sliced" question, and
(2) in the examples we looked at, the code was already using the length more often than the slice itself.

If the examples we looked at are not representative, does anyone want to contribute more examples of existing code that would use CommonPrefix or CommonPrefixLen?

Another potential reason for CommonPrefixLen is that this length might be in the middle of a UTF-8 boundary or a grapheme cluster or any of those things. Making the user do the slice might make them think a bit about whether it's a sensible place to slice.

[robpike]

@rsc Your last paragraph doesn't seem compelling. In writing

prefix := s[:strings.CommonPrefixLen(s, t)]

at what moment do I ask where I'm slicing that I wouldn't ask with

prefix := strings.CommonPrefix(s, t)

I'm not arguing against CommonPrefixLen, I'm just arguing that it feels sound to me to offer CommonPrefix as well. And for the third time, the question of which to slice is trivial to answer and understand. It's not an issue at all.