regexp: wrong match found without capturing parens

[rsc]

http://play.golang.org/p/n5XbC7kTDt

package main

import (
    "fmt"
    "regexp"
)

func main() {
    s := "abc"

    rePass := regexp.MustCompile("(a.*?c)|a.*?b")
    reFail := regexp.MustCompile("a.*?c|a.*?b")

    fmt.Printf("%v\n", rePass.FindStringIndex(s))
    // Writes "[0 3]"
    fmt.Printf("%v\n", reFail.FindStringIndex(s))
    // Writes "[0 2]"
}

The overall match found should not depend on capturing parens. In this case, the a.*?c branch of the alternative should take priority over the a.*?b branch in both expressions, so both should match [0 3] not [0 2].

This happens in C++ RE2 as well.

[junyer]

Summarised from commentary elsewhere:

The problem is caused by factoring of common prefixes in alternations. Complex subexpressions (e.g. involving quantifiers) aren't safe to factor because that collapses their distinct paths through the automaton.

The fix that I've proposed for RE2 is very simple. I'll port it to Go with @rsc's blessing.

[gopherbot]

CL https://golang.org/cl/18357 mentions this issue.