Implementing replaceAll with generated matchers?

[dkegel-fastly]

Implementing replaceAll with generated matchers?

[dkegel-fastly]

Here's a demo of what I'm trying to do. Not quite happy yet...

package main
  
import (
        "fmt"
        "regexp"
)

func main() {
        input := "aaa aaa"

        // Porting FindStringIndex() to fsm
        r := regexp.MustCompile(`a{2,3}`)
        match := r.FindStringIndex(input)
        fmt.Printf("regexp: r.FindStringIndex returns %d, %d\n", match[0], match[1])
        start, end := Match(input)
        fmt.Printf("fsm: Match returns %d, %d\n", start, end)

        // Porting ReplaceAll to fsm
        out := r.ReplaceAllString(input, "b")
        fmt.Printf("regexp: ReplaceAllString returns %s\n", out)
        out = myReplaceAll(input, "b")
        fmt.Printf("fsm: myReplaceAll returns %s\n", out)
}

// myReplaceAll finds all sequences in value that Match, and replaces them with repl.
// Any matches that might result from the replacement are ignored.
func myReplaceAll(value, repl string) string {
        remaining := value
        out := ""
        for remaining != "" {
                start, end := Match(remaining)
                if start == -1 {
                        out = out + remaining
                        remaining = ""
                } else {
                        println("match", remaining[start:end], "start", start, "end", end)
                        out = out + remaining[0:start] + repl
                        remaining = remaining[end:]
                }
        }
        return out
}

Save that as main.go, then create match.go with something like

re -k str -l go -r pcre 'a{2,3}' | sed 's/fsm_fsm/main/' > match.go

and run with

go run main.go match.go

Currently, it outputs

regexp: r.FindStringIndex returns 0, 3
fsm: Match returns 0, 2
regexp: ReplaceAllString returns b b
match aa start 0 end 2
match aa start 2 end 4
fsm: myReplaceAll returns ba ba

Examining the generated code, fsm expands the quantifier a{2,3} to return immediately after the 2nd a, without even trying to consume a 3rd one.
(I filed #358 for that earlier, but may not have provided enough context.)

This is a fine optimization for detecting a match, so evidently my hack to return the end offset of the match is breaking an assumption libfsm made, and/or I'm misusing libfsm in some other way.

[dhobsd]

I think you need to call Match again after you replace to find the next index. Also a good idea to use a slice instead of string here so you avoid a bunch of allocations. Looks like you're at Fastly, so may be worth looking at the Varnish implementation if that still exists. In particular you need to decide what to do if the replacement results in another match.

…

On Tue, Jun 1, 2021 at 20:24 dkegel-fastly ***@***.***> wrote: I'm flailing around a bit trying to figure out how to port that regexp to libfsm. Using re -k str -l go -r pcre 'a{2,}[^a]' | sed 's/fsm_fsm/main/' > match.go outputs regexp: r.FindStringIndex returns 0, 3 fsm: Match returns 0, 3 regexp: ReplaceAllString returns b b fsm: myReplaceAll returns b aaa Using re -k str -l go -r pcre 'a{2,}' | sed 's/fsm_fsm/main/' > match.go yields regexp: r.FindStringIndex returns 0, 3 fsm: Match returns 0, 1 regexp: ReplaceAllString returns b b fsm: myReplaceAll returns bba bba — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#357 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AABJFR36WPKJXSDQ2JZDHW3TQWB6JANCNFSM455AH5UA> .

[dkegel-fastly]

Thanks. I updated the problem description to address your last suggestion about induced matches.
I'm not worried about the inefficiency of using string for the moment.

I am very interested in suggestions for coaxing libfsm into actually finishing the match of a{2,3} instead
of calling it a day after aa.