delta/go-git.git/src/regexp, branch dev.cmdgo

regexp: fix repeat of preferred empty match

2021-05-13T14:52:20+00:00

In Perl mode, (|a)* should match an empty string at the start of the
input. Instead it matches as many a's as possible.
Because (|a)+ is handled correctly, matching only an empty string,
this leads to the paradox that e* can match more text than e+
(for e = (|a)) and that e+ is sometimes different from ee*.

This is a very old bug that ultimately derives from the picture I drew
for e* in https://swtch.com/~rsc/regexp/regexp1.html. The picture is
correct for longest-match (POSIX) regexps but subtly wrong for
preferred-match (Perl) regexps in the case where e has a preferred
empty match. Pointed out by Andrew Gallant in private mail.

The current code treats e* and e+ as the same structure, with
different entry points. In the case of e* the preference list ends up
not quite in the right order, in part because the “before e” and
“after e” states are the same state. Splitting them apart fixes the
preference list, and that can be done by compiling e* as if it were
(e+)?.

Like with any bug fix, there is a very low chance of breaking a
program that accidentally depends on the buggy behavior.

RE2, Go, and Rust all have this bug, and we've all agreed to fix it,
to keep the implementations in sync.

Fixes #46123.

Change-Id: I70e742e71e0a23b626593b16ddef3c1e73b413b0
Reviewed-on: https://go-review.googlesource.com/c/go/+/318750
Trust: Russ Cox 
Run-TryBot: Russ Cox 
Reviewed-by: Rob Pike 
TryBot-Result: Go Bot

all: go fmt std cmd (but revert vendor)

2021-02-20T03:54:50+00:00

Make all our package sources use Go 1.17 gofmt format
(adding //go:build lines).

Part of //go:build change (#41184).
See https://golang.org/design/draft-gobuild

Change-Id: Ia0534360e4957e58cd9a18429c39d0e32a6addb4
Reviewed-on: https://go-review.googlesource.com/c/go/+/294430
Trust: Russ Cox 
Run-TryBot: Russ Cox 
TryBot-Result: Go Bot 
Reviewed-by: Jason A. Donenfeld 
Reviewed-by: Ian Lance Taylor

regexp/syntax: add note about Unicode character classes

2020-11-25T15:10:09+00:00

As proposed on golang-nuts:
https://groups.google.com/g/golang-nuts/c/M3lmSUptExQ/m/hRySV9GsCAAJ

Includes the latest updates from re2's mksyntaxgo:
https://code.googlesource.com/re2/+/refs/heads/master/doc/mksyntaxgo

Change-Id: Ib7b79aa6531f473feabd0a7f1d263cd65c4388e4
Reviewed-on: https://go-review.googlesource.com/c/go/+/264678
Reviewed-by: Russ Cox 
Trust: Emmanuel Odeke

regexp/syntax: append patchLists in constant time

2020-06-18T00:40:11+00:00

By keeping a tail pointer, we can append to a patchList in constant
time, rather than in time proportional to the length of the list. This
gets rid of the quadratic compile times we were seeing for long series
of alternations.

This is basically the same change as
https://github.com/google/re2/commit/e9d517989f66f2e0a24cde42f4d2424dd3e4a9b9.

Fixes #39542.

Change-Id: Ib4ca0ca9c55abd1594df1984653c7d311ccf7572
Reviewed-on: https://go-review.googlesource.com/c/go/+/238079
Run-TryBot: Ian Lance Taylor 
TryBot-Result: Gobot Gobot 
Reviewed-by: Ian Lance Taylor

regexp/syntax: fix comment on p.literal and simplify

2020-04-17T22:12:02+00:00

p.literal's doc comment said it returned a value but it doesn't.
While we're here, p.newLiteral is only called from p.literal,
so simplify the code by merging the two.

Change-Id: Ia357937a99f4e7473f0f1ec837113a39eaeb83d4
Reviewed-on: https://go-review.googlesource.com/c/go/+/222659
Run-TryBot: Russ Cox 
TryBot-Result: Gobot Gobot 
Reviewed-by: Ian Lance Taylor

regexp: add (*Regexp).SubexpIndex

2020-04-10T09:38:07+00:00

SubexpIndex returns the index of the first subexpression with the given name,
or -1 if there is no subexpression with that name.

Fixes #32420

Change-Id: Ie1f9d22d50fb84e18added80a9d9a9f6dca8ffc4
Reviewed-on: https://go-review.googlesource.com/c/go/+/187919
Run-TryBot: Ian Lance Taylor 
TryBot-Result: Gobot Gobot 
Reviewed-by: Daniel Martí

regexp: skip long-running benchmarks if -short is specified

2019-10-17T19:53:52+00:00

This CL helps race.bash finish in a reasonable amount of
time. Otherwise the Match/Hard1/32M benchmark takes over 1200 seconds
to finish on arm64, triggering a timeout.  With this change the regexp
benchmarks as a whole take only about a minute.

Change-Id: Ie2260ef9f5709e32a74bd76f135bc384b2d9853f
Reviewed-on: https://go-review.googlesource.com/c/go/+/201742
Run-TryBot: Keith Randall 
Reviewed-by: Brad Fitzpatrick 
TryBot-Result: Gobot Gobot

regexp: add examples for FindSubmatchIndex and Longest

2019-09-28T00:37:35+00:00

updates #21450

Change-Id: Ibffe0dadc1e1523c55cd5f5b8a69bc1c399a255d
GitHub-Last-Rev: 507f55508121a525de4d210e7ada1396ccaaf367
GitHub-Pull-Request: golang/go#33497
Reviewed-on: https://go-review.googlesource.com/c/go/+/189177
Run-TryBot: Ian Lance Taylor 
TryBot-Result: Gobot Gobot 
Reviewed-by: Ian Lance Taylor

regexp: add more examples for Regexp methods

2019-09-18T20:26:36+00:00

Since I first started on this CL, most of the methods have had examples
added by other folks, so this is now one new example, and additions to
two existing examples for extra clarity.

The issue has a comment about not necessarily having examples for all
methods, but I recall finding this package pretty confusing when I first
used it, and having concrete examples would have really helped me
navigate all the different options. There are more
String methods with examples now, but I think seeing how the byte-slice
methods work could also be helpful to explain the differences.

Updates #21450

Change-Id: I27b4eeb634fb8ab59f791c0961cce79a67889826
Reviewed-on: https://go-review.googlesource.com/c/go/+/120145
Reviewed-by: Daniel Martí 
Reviewed-by: Ian Lance Taylor 
Run-TryBot: Daniel Martí 
TryBot-Result: Gobot Gobot

regexp: add example for NumSubexp

2019-09-10T20:33:25+00:00

Updates #21450

Change-Id: Idf276e97f816933cc0f752cdcd5e713b5c975833
GitHub-Last-Rev: 198e585f92db6e7ac126b49cd751b333e9a44b93
GitHub-Pull-Request: golang/go#33490
Reviewed-on: https://go-review.googlesource.com/c/go/+/189138
Run-TryBot: Ian Lance Taylor 
TryBot-Result: Gobot Gobot 
Reviewed-by: Ian Lance Taylor