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

index/suffixarray: FindAllIndex gives wrong results for anchored regexp #30511

Open
antong opened this issue Mar 1, 2019 · 6 comments
Open
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone

Comments

@antong
Copy link
Contributor

antong commented Mar 1, 2019

What version of Go are you using (go version)?

$ go version
go version go1.12 linux/amd64

Does this issue reproduce with the latest release?

It does reproduce with Go versions 1.3 to 1.12 (latest at the time of writing), but it works as expected in Go version 1.2.

What operating system and processor architecture are you using (go env)?

go env Output
$ go env
GOARCH="amd64"
GOBIN=""
GOCACHE="/root/.cache/go-build"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOOS="linux"
GOPATH="/go"
GOPROXY=""
GORACE=""
GOROOT="/usr/local/go"
GOTMPDIR=""
GOTOOLDIR="/usr/local/go/pkg/tool/linux_amd64"
GCCGO="gccgo"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build610735870=/tmp/go-build -gno-record-gcc-switches"

What did you do?

I called the suffixarray FindAllIndex method with a regexp anchored both to the beginning and end of text (https://play.golang.org/p/TaXeqtHt4Iq):

func main() {
	idx := suffixarray.New([]byte("banana"))
	re := regexp.MustCompile("^a$")
	fmt.Println(idx.FindAllIndex(re, -1))
	// Output:
	// [[1 2] [3 4] [5 6]]
}

What did you expect to see?

I expected an empty result [], the same result as for the equivalent regexp method FindAllIndex (https://play.golang.org/p/PVThOv1EE8S):

func main() {
	re := regexp.MustCompile("^a$")
	fmt.Println(re.FindAllIndex([]byte("banana"), -1))
	// Output:
	// []
}

What did you see instead?

suffixarray FindAllIndex returned the following index pairs in "banana" for the regexp "^a$":

[[1 2] [3 4] [5 6]]

The FindAllIndex documentation reads:

FindAllIndex returns a sorted list of non-overlapping matches of the regular expression r, where a match is a pair of indices specifying the matched slice of x.Bytes(). If n < 0, all matches are returned in successive order. Otherwise, at most n matches are returned and they may not be successive. The result is nil if there are no matches, or if n == 0.

There are no matches for the expression "^a$" in the string "banana". Therefore the result should be empty, nil.

Go 1.2 produced the expected result. This is a regression in Go 1.3 where the behaviour of the regexp method LiteralPrefix changed. See the discussion in #30425.

@bcmills
Copy link
Member

bcmills commented Mar 1, 2019

CC @griesemer

@bcmills bcmills added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Mar 1, 2019
@griesemer
Copy link
Contributor

griesemer commented Mar 6, 2019

We should adjust FindAllIndex as necessary, but I'd like to get a definitive answer on why regexp LiteralPrefix changed over time and what its correct behavior should be. Also, given how long this has not worked as expected, this is not urgent.

Waiting for resolution of #30425 .

@griesemer griesemer added the WaitingForInfo Issue is not actionable because of missing required information, which needs to be provided. label Mar 6, 2019
@griesemer griesemer self-assigned this Mar 6, 2019
@griesemer griesemer added this to the Unplanned milestone Mar 6, 2019
@gopherbot
Copy link

Timed out in state WaitingForInfo. Closing.

(I am just a bot, though. Please speak up if this is a mistake or you have the requested information.)

@cespare
Copy link
Contributor

cespare commented Apr 6, 2019

Reopening this. I think the info that @griesemer was waiting for is from a Go team member who knows about LiteralPrefix changes, not from the issue creator.

@cespare cespare reopened this Apr 6, 2019
@cespare cespare removed the WaitingForInfo Issue is not actionable because of missing required information, which needs to be provided. label Apr 6, 2019
@cespare
Copy link
Contributor

cespare commented Apr 6, 2019

Hmph.

@cespare cespare reopened this Apr 6, 2019
@agnivade
Copy link
Contributor

agnivade commented Apr 9, 2019

@rsc for the regex question

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
None yet
Development

No branches or pull requests

6 participants