code review 150270043: regexp/syntax: reject large repetitions created by nest...

regexp/syntax: reject large repetitions created by nesting small ones

Fixes issue 7609.

[rsc, 2014-09-29 23:27:37]

Hello r (cc: golang-codereviews@googlegroups.com),

I'd like you to review this change to
https://code.google.com/p/go/

[r, 2014-09-29 23:32:26]

LGTM

https://codereview.appspot.com/150270043/diff/40001/src/regexp/syntax/parse.go
File src/regexp/syntax/parse.go (right):

https://codereview.appspot.com/150270043/diff/40001/src/regexp/syntax/parse.g...
src/regexp/syntax/parse.go:271: // triggering a parse error, so each subtree can
only be rewalked 9 times.
this is fine but would it also avoid the quadratic behavior to remember the
result and avoid rewalks that way?

[rsc, 2014-09-30 01:03:43]

https://codereview.appspot.com/150270043/diff/40001/src/regexp/syntax/parse.go
File src/regexp/syntax/parse.go (right):

https://codereview.appspot.com/150270043/diff/40001/src/regexp/syntax/parse.g...
src/regexp/syntax/parse.go:271: // triggering a parse error, so each subtree can
only be rewalked 9 times.
On 2014/09/29 23:32:25, r wrote:
> this is fine but would it also avoid the quadratic behavior to remember the
> result and avoid rewalks that way?

You'd have to remember the maximum product of the repetitions for a given
*Regexp, and then you could check whether the new product >= 1000 each time you
pile on a new repetition. Unfortunately, I don't have anywhere I trust to put
that information:

(1) I could change parser.stack from []*Regexp to []struct{re *Regexp; repeat
int}, but then I have to update every place where the stack is manipulated.

(2) I could add a new field to Regexp, but today Regexp is completely exported
fields and can be prepared by other code. I don't want to add an unexported
field and break that, and I don't want to add a new exported field. A more
fundamental problem is that *Regexps are reused during parsing. As one is popped
off a stack it goes onto a free list and then can be reused to avoid a future
allocation. And others are just reused in place by direct modification. I'd have
to find every reuse position and invalidate the derived repetition information.

(3) I could keep in the parser a map[*Regexp]int. That avoids the field problem
but not the stale cache problem of (2).

I would have liked to put this logic in Simplify, since Simplify could just pass
the repetition depth down during its recursion, but Simplify's declaration means
it cannot fail. If not for Go 1 compatibility, I would add an error result
there. I could try to detect the result of Simplify on one of these in Compile,
but it's non-trivial and I'm not convinced I'd get it right. Since Parse already
rejects x{1001} it seemed at least consistent to put the check here.

The 9x here is annoying but not a deal breaker: each of the nine is a quick
traversal and probably noise compared to the actual building of the tree in the
first place. It seems to be the best of many bad choices.

[rsc, 2014-09-30 16:08:13]

*** Submitted as https://code.google.com/p/go/source/detail?r=a0fced236e4d ***

regexp/syntax: reject large repetitions created by nesting small ones

Fixes issue 7609.

LGTM=r
R=r
CC=golang-codereviews
https://codereview.appspot.com/150270043