proposal: regexp: add iterator forms of matching methods

[rsc]

We propose to add methods to regexp that allow iterating over matches instead of having to accumulate all the matches into a slice.

This is one of a collection of proposals updating the standard library for the new 'range over function' feature (#61405). It would only be accepted if that proposal is accepted. See #61897 for a list of related proposals.

Regexp has a lot of methods that return slices of all matches (the “FindAll*” methods). Each should have an iterator equivalent that doesn’t build the slice. They can be named by removing the “Find” prefix. The docs would change as follows. (Plain text is unchanged; strikethrough is removed, bold is added):

There are 16 24 methods of Regexp that match a regular expression and identify the matched text. Their names are matched by this regular expression:

(Find|All|FindAll)?(String)?(Submatch)?(Index)?

If 'All' is present, the routine matches successive non-overlapping matches of the entire expression.
The ‘Find’ form returns the first match. The ‘All’ form returns an iterator over all matches.
Empty matches abutting a preceding match are ignored.
The For ‘FindAll’, the return value is a slice containing the successive return values of the corresponding non-’All’ non-‘Find’ routine. These The ‘FindAll’ routines take an extra integer argument, ...

Instead of enumerating all eight methods here, let’s just show one example.
FindAllString currently reads:

// FindAllString is the 'All' version of FindString; it returns a slice of all
// successive matches of the expression, as defined by the 'All' description in
// the package comment. A return value of nil indicates no match.
func (re *Regexp) FindAllString(s string, n int) []string

This would change to become a pair of methods:

// FindAllString is the 'All' 'FindAll' version of FindString; it returns a slice of all
// successive matches of the expression, as defined by the 'All' 'FindAll' description in
// the package comment. A return value of nil indicates no match.
func (re *Regexp) FindAllString(s string, n int) []string

// AllString is the ‘All’ version of ‘FindString’; it returns an iterator over all
// successive matches of the expression, as defined by the ‘All’ description in
// the package comment.
func (re *Regexp) AllString(s string) iter.Seq[[]string]

The full list is:

// All is the ‘All’ version of ‘Find’: it returns an iterator over all ...
func (re *Regexp) All(b []byte) iter.Seq[[]byte]

// AllIndex is the ‘All’ version of ‘FindIndex’: it returns an iterator over all ...
func (re *Regexp) AllIndex(b []byte) iter.Seq[[]int]

// AllString is the ‘All’ version of ‘FindString’: it returns an iterator over all ...
func (re *Regexp) AllString(s string) iter.Seq[string]

// AllStringIndex is the ‘All’ version of ‘FindStringIndex’: it returns an iterator over all ...
func (re *Regexp) AllStringIndex(s string) iter.Seq[[]int]

// AllStringSubmatch is the ‘All’ version of ‘FindStringSubmatch’: it returns an iterator ...
func (re *Regexp) AllStringSubmatch(s string) iter.Seq[[]string]

// AllStringSubmatchIndex is the ‘All’ version of ‘FindStringSubmatchIndex’: it returns ...
func (re *Regexp) AllStringSubmatchIndex(s string) iter.Seq[[]int]

// AllSubmatch is the ‘All’ version of ‘FindSubmatch’: it returns an iterator over all ...
func (re *Regexp) AllSubmatch(b []byte) iter.Seq[[][]byte]

// AllSubmatchIndex is the ‘All’ version of ‘FindSubmatchIndex’: it returns an iterator ...
func (re *Regexp) AllSubmatchIndex(b []byte) iter.Seq[[]int]

There would also be a new SplitSeq method alongside regexp.Regexp.Split, completing the analogy with strings.Split and strings.SplitSeq.

// SplitSeq returns an iterator over substrings of s separated by the expression.
func (re *Regexp) SplitSeq(s string) iter.Seq[string]

[cespare]

@rsc under "The full list is" the actual function signatures need to be fixed to match the correct names in the doc comments.

[magical]

It seems like you are trying to establish a general pattern in the stdlib that the word All in a method means that it returns an iterator. However, the regexp package has already established a pattern that All means a method that returns a slice. I don't think that dropping the Find prefix is a particularly good or memorable compromise, and that it would be better in this case to find a different word to replace All (say, Iter).

Which is to say, I think these names would be a lot clearer:

    func (re *Regexp) FindIter(b []byte) iter.Seq[[]byte]
    func (re *Regexp) FindIterIndex(b []byte) iter.Seq[[]int]
    func (re *Regexp) FindIterString(s string) iter.Seq[string]
    func (re *Regexp) FindIterStringIndex(s string) iter.Seq[[]int]
    func (re *Regexp) FindIterStringSubmatch(s string) iter.Seq[[]string]
    func (re *Regexp) FindIterStringSubmatchIndex(s string) iter.Seq[[]int]
    func (re *Regexp) FindIterSubmatch(b []byte) iter.Seq[[][]byte]
    func (re *Regexp) FindIterSubmatchIndex(b []byte) iter.Seq[[]int]

[Merovius]

@magical I think Iter as a name component reads very badly. I'd be fine with it in regexp (given how rarely it's used), but definitely not as a general convention. I'd prefer essentially anything over changing the All convention to an Iter convention, including accepting this slight ambiguity in the regexp package, deviating from the All convention in the regexp package only, or not adding iterator-versions of methods to regexp at all. In particular given how rarely used the regexp package is in my experience.

[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

[benhoyt]

I have found it quite confusing in the past to figure out which of the 16 Find* methods to use for a particular task. Determining String vs non-string is quite straight-forward, but I always have to re-read several paragraph of docs and play around to determine which one of the remaining 8 to use. It's cute, even elegant, that the method names are matched by a regex (Find(All)?(String)?(Submatch)?(Index)?), but in my experience that doesn't make it easier to choose which one you need. This proposal is going to increase that cognitive burden. I don't have a concrete suggestion, but I wonder if there's a better way. From this perspective I do think having Iter (or Seq?) in the name could help. Or maybe there needs to be a "regex method chooser wizard" in the docs? Only semi-serious, but maybe this can be solved by documentation improvements.

[extemporalgenome]

In addition to the correction @cespare proposes, I believe your AllString example has the wrong returned iterator element type ([]string). It should be string:

func (re *Regexp) AllString(s string) iter.Seq[string]

[extemporalgenome]

I believe it would be beneficial to document in the relevant methods that any yielded slices ([]byte, []int, [][]byte, []string) cannot be retained beyond the current iteration step, thus allowing the regex implementation to reuse these slices. There is precedent for this kind of restriction in bytes.Buffer.Bytes and elsewhere.

I suspect most use-cases will be unaffected by this restriction, other than to benefit from reduced allocations (which could potentially further benefit from internal use of sync.Pool to share applications between unrelated iterations). Those cases that do need to retain the slice can easily enough call slices.Clone or append.

go vet could include a check to ensure these slices do not escape in most cases.

[leaxoy]

Emm, that is, we will have nearly 60 methods to do matching? 😂

How about add a new type RegexpIter? And provide methods convert between the two.

[extemporalgenome]

I agree with @leaxoy.

Irrespective of my above comments, I believe we'll be better served with an approach closer to bufio.Scanner, in which something like a *Match value, with methods for fetching index offset ranges, individual matches as a string or byte slice, etc.