fix: (?s).* prefix clipped to the suffix's line in ReverseSuffix/ReverseSuffixSet (regression in v0.12.15) #191

With the s flag (. matches \n), patterns that start with .* and end in a literal suffix return a match that starts at the beginning of the suffix's line instead of the beginning of the input. This is a regression in v0.12.15; v0.12.14 returns the stdlib result for these patterns.

Repro

package main

import (
	"fmt"
	"regexp"

	"github.com/coregx/coregex"
)

func main() {
	for _, c := range [][2]string{
		{`(?s).*\.txt`, "a\nb.txt"},
		{`(?s).*\.(txt|log)`, "a\nb.log"},
		{`(?s).*\.txt`, "q.txt\nz\nb.txt"},
	} {
		std := regexp.MustCompile(c[0])
		cre := coregex.MustCompile(c[0])
		fmt.Printf("%-18q %-18q stdlib=%v coregex=%v\n", c[0], c[1],
			std.FindStringIndex(c[1]), cre.FindStringIndex(c[1]))
	}
}

v0.12.29:

"(?s).*\\.txt"     "a\nb.txt"         stdlib=[0 7] coregex=[2 7]
"(?s).*\\.(txt|log)" "a\nb.log"         stdlib=[0 7] coregex=[2 7]
"(?s).*\\.txt"     "q.txt\nz\nb.txt"  stdlib=[0 13] coregex=[8 13]

v0.12.14 prints the stdlib result for all three.

Wrong bounds also come from FindAllStringIndex, FindStringSubmatchIndex (including capture groups, e.g. (?s)(.*)@example\.com gives [2 15 2 3] instead of [0 15 0 3]), ReplaceAllString and Split. MatchString is correct.

Not affected: the same patterns without (?s) (they are correct, as fixed in #146), (?s).+\.txt, and (?s).*\.txt$.

Affected strategies: UseReverseSuffix ((?s).*\.txt, (?s).*@example\.com, (?s).*(foo|bar)baz, (?s:.*)\.txt) and UseReverseSuffixSet ((?s).*\.(txt|log)), checked with COREGEX_DEBUG=1.

Cause

hasDotStarPrefix in meta/strategy.go returns true for both OpStar(OpAnyChar) ((?s).*) and OpStar(OpAnyCharNotNL) (.*). The result is passed as matchStartZero to NewReverseSuffixSearcher and NewReverseSuffixSetSearcher (meta/compile.go), and with that flag both searchers bound the match to the suffix's line via lineStartBefore and a line-end search, in Find, FindAt and findIndicesAtImpl. That line bound is right for OpAnyCharNotNL only. It came in with the .* newline-boundary fix in #146.

Related: multiple suffixes across lines

(?s).*\.txt on "q.txt\nz\nb.txt" should be one greedy match [0 13]. Besides Find above (v0.12.15+), FindAllStringIndex, FindStringSubmatchIndex, ReplaceAllString and Split are wrong here already in v0.12.8, so this part predates #146:

Expected behavior

For (?s).*X, the match starts at the search start and ends after the last X in the input, as in regexp.

Context

Found in uawk, which prepends (?s) to every AWK regex (POSIX: . matches newline). With v0.12.29, match("x\ny@example.com", /.*@example\.com/) sets RSTART=3 instead of 1, and sub/split with such patterns return wrong results on strings containing \n.

Refs #178