regexp: compiling incorrectly #59007

apmckinlay · 2023-03-13T17:07:09Z

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

$ go version
go version go1.20.2 darwin/amd64

Does this issue reproduce with the latest release?

yes
and with 1.19 on the Go Playground

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

go env Output

$ go env
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/Users/andrew/Library/Caches/go-build"
GOENV="/Users/andrew/Library/Application Support/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="darwin"
GOINSECURE=""
GOMODCACHE="/Users/andrew/Go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="darwin"
GOPATH="/Users/andrew/Go:/Users/andrew/Dropbox/suneido_tests"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/usr/local/go"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/usr/local/go/pkg/tool/darwin_amd64"
GOVCS=""
GOVERSION="go1.20.2"
GCCGO="gccgo"
GOAMD64="v1"
AR="ar"
CC="clang"
CXX="clang++"
CGO_ENABLED="1"
GOMOD="/Users/andrew/Dropbox/gsuneido/go.mod"
GOWORK=""
CGO_CFLAGS="-O2 -g"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-O2 -g"
CGO_FFLAGS="-O2 -g"
CGO_LDFLAGS="-O2 -g"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -arch x86_64 -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/dc/0y3gfqnn56g6pd8d3_b5wz300000gn/T/go-build1311023722=/tmp/go-build -gno-record-gcc-switches -fno-common"
GOROOT/bin/go version: go version go1.20.2 darwin/amd64
GOROOT/bin/go tool compile -V: compile version go1.20.2
uname -v: Darwin Kernel Version 22.3.0: Mon Jan 30 20:42:11 PST 2023; root:xnu-8792.81.3~2/RELEASE_X86_64
ProductName:		macOS
ProductVersion:		13.2.1
BuildVersion:		22D68
lldb --version: lldb-1400.0.38.17
Apple Swift version 5.7.2 (swiftlang-5.7.2.135.5 clang-1400.0.29.51)

What did you do?

pat := regexp.MustCompile(`0A|0[aA]`)
fmt.Println(pat.MatchString("0a"))

(https://go.dev/play/p/jCLPp8AXnJB)

What did you expect to see?

true

What did you see instead?

false

I tested on regex101 to confirm that this should match.
(Strangely, it shows golang matching)
It appears to compile incorrectly. Simplify doesn't seem to matter.

syntax.Parse("0A|0[aA]", 0)
fmt.Println(syntax.Compile(re))
  0	fail
  1*	rune1 "0" -> 2
  2	rune1 "A" -> 3
  3	nop -> 4
  4	match

syntax.Parse("0a|0[aA]", 0)
fmt.Println(syntax.Compile(re))
  0	fail
  1*	rune1 "0" -> 2
  2	rune "AAaa" -> 3
  3	match

The text was updated successfully, but these errors were encountered:

cherrymui · 2023-03-13T23:06:46Z

cc @rsc

ianlancetaylor · 2023-03-14T04:29:25Z

The regexp 0A|0[aA] means 0(A|0)[aA]. You seem to be looking for (0A)|(0[aA]).

randall77 · 2023-03-14T05:01:42Z

From https://github.com/google/re2/wiki/Syntax , it says

The operator precedence, from weakest to strongest binding, is first alternation, then concatenation, and finally the repetition operators... Some examples: ab|cd is equivalent to (ab)|(cd)

That makes me think the OP's regexp is (0A)|(0[aA]), not 0(A|0)[aA].

crisman · 2023-03-14T05:03:34Z

The regexp 0A|0[aA] means 0(A|0)[aA]. You seem to be looking for (0A)|(0[aA]).

No, re2 flavor regex don't bind that way, see https://github.com/google/re2/wiki/Syntax

Some examples: ab|cd is equivalent to (ab)|(cd);

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

For re `aB|a[cd]` parsed as `a[Bc-d]`
For re `0A|0[aA]` parsed as `0A(?:)`
For re `0a|0[aA]` parsed as `0[Aa]`

Notice the second one parsed as the string 0A followed by an empty non-capturing group, which is just wrong. It should be similar to the third item where the alternation collapsed and the second character is casefolded a (either [aA] or (?i:a)).

An prefix followed by a capital letter with a character class with capital and lower case seems broken, larger prefixes are still broken (see the play link above)

crisman · 2023-03-14T10:47:12Z

I think that syntax.Regexp Equal() is broken between literals and caseFolded literals.

justA, _ := syntax.Parse(`A`, syntax.Perl)
foldA, _ := syntax.Parse(`(?i:A)`, syntax.Perl)
fmt.Println(justA.Equal(foldA)) // should not be true

Given the odd pattern as above (0A|0[aA]).

In src/regexp/syntax/parse.go once factor() pulls out the 0 prefix it then tries to factor() between A and (?i:A) (what [aA] is parsed as) and is able to find a prefix of A as Equal() says true. Once the code goes wrong it then does some sillyness with alternation between two empty non-capturing groups, which makes no sense as one would expect down a wrong branch.

In src/regexp/syntax/regexp.go Equal() under the case OpLiteral does not have any logic for the FoldCase flag, which I think is the error.

At first glance the logic in re2/regexp.cc TopEqual() for Literal does care about FoldCase which lets me be more sure this is what needs fixing.

apmckinlay · 2023-03-14T17:58:40Z

The regexp 0A|0[aA] means 0(A|0)[aA]. You seem to be looking for (0A)|(0[aA]).

Even if that was the case, there would still be a problem because 0A|0[aA] is compiling and working very differently from 0a|0[aA] (as I showed)

ianlancetaylor · 2023-03-14T18:14:38Z

Apologies for being confused.

dolmen · 2023-12-12T09:26:05Z

$ perl -E 'say ("0a" =~ /0A|0[Aa]/)'
1
$ go version
go version go1.21.5 darwin/arm64
$ go run github.com/dolmen-go/goeval@latest -i=regexp -i=fmt 'fmt.Println(regexp.MustCompile("0A|0[Aa]").MatchString("0a"))' 
false

dolmen · 2023-12-12T10:51:28Z

@apmckinlay You must use the regexp/syntax.Perl flag with regexp/syntax.Parse to match regexp.Compile behaviour.

Here is your example fixed: https://go.dev/play/p/OrLoZxhMwMN

But the issue is still there.

junyer · 2023-12-12T12:27:52Z

RE2 has a similar bug, FWIW, but it's caused by this assumption. I haven't looked into what the Go regexp package is doing, but I suspect that @crisman is correct or, at the very least, on the right track.

Fixing `Equal` method in `regexp/syntax` package fixes compilation of some alternate patterns like `0A|0[aA]`. Fixes golang#59007

Fixing Equal method in regexp/syntax package fixes compilation of some alternate patterns like "0A|0[aA]". Fixes golang#59007

gopherbot · 2024-03-07T11:28:10Z

Change https://go.dev/cl/569735 mentions this issue: regexp: fix compiling alternate patterns of different fold case literals

Fixing Equal method in regexp/syntax package fixes compilation of some alternate patterns like "0A|0[aA]". Fixes golang#59007

apmckinlay changed the title ~~regex: compiling incorrectly~~ regexp: compiling incorrectly Mar 13, 2023

cherrymui added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Mar 13, 2023

cherrymui added this to the Go1.21 milestone Mar 13, 2023

ianlancetaylor closed this as not planned Won't fix, can't repro, duplicate, stale Mar 14, 2023

randall77 reopened this Mar 14, 2023

gopherbot modified the milestones: Go1.21, Go1.22 Aug 8, 2023

junyer mentioned this issue Dec 12, 2023

the parser can incorrectly merge runs of literals and/or character classes google/re2#467

Closed

gopherbot modified the milestones: Go1.22, Go1.23 Feb 6, 2024

itchyny added a commit to itchyny/go that referenced this issue Mar 7, 2024

regexp: fix compiling alternate patterns of different fold case literals

70d9905

Fixing `Equal` method in `regexp/syntax` package fixes compilation of some alternate patterns like `0A|0[aA]`. Fixes golang#59007

itchyny added a commit to itchyny/go that referenced this issue Mar 7, 2024

regexp: fix compiling alternate patterns of different fold case literals

62e7ff6

Fixing Equal method in regexp/syntax package fixes compilation of some alternate patterns like "0A|0[aA]". Fixes golang#59007

itchyny linked a pull request Mar 7, 2024 that will close this issue

regexp: fix compiling alternate patterns of different fold case literals #66165

Open

itchyny added a commit to itchyny/go that referenced this issue Apr 2, 2024

regexp: fix compiling alternate patterns of different fold case literals

8d63173

Fixing Equal method in regexp/syntax package fixes compilation of some alternate patterns like "0A|0[aA]". Fixes golang#59007

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

regexp: compiling incorrectly #59007

regexp: compiling incorrectly #59007

apmckinlay commented Mar 13, 2023 •

edited

cherrymui commented Mar 13, 2023

ianlancetaylor commented Mar 14, 2023

randall77 commented Mar 14, 2023

crisman commented Mar 14, 2023

crisman commented Mar 14, 2023

apmckinlay commented Mar 14, 2023

ianlancetaylor commented Mar 14, 2023

dolmen commented Dec 12, 2023 •

edited

dolmen commented Dec 12, 2023

junyer commented Dec 12, 2023

gopherbot commented Mar 7, 2024

regexp: compiling incorrectly #59007

regexp: compiling incorrectly #59007

Comments

apmckinlay commented Mar 13, 2023 • edited

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

Does this issue reproduce with the latest release?

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

What did you do?

What did you expect to see?

What did you see instead?

cherrymui commented Mar 13, 2023

ianlancetaylor commented Mar 14, 2023

randall77 commented Mar 14, 2023

crisman commented Mar 14, 2023

crisman commented Mar 14, 2023

apmckinlay commented Mar 14, 2023

ianlancetaylor commented Mar 14, 2023

dolmen commented Dec 12, 2023 • edited

dolmen commented Dec 12, 2023

junyer commented Dec 12, 2023

gopherbot commented Mar 7, 2024

apmckinlay commented Mar 13, 2023 •

edited

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

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

dolmen commented Dec 12, 2023 •

edited