rsc / binaryregexp Goto Github PK

In mandiant/GoReSym@11d153d we hit performance issues with the regex execution over large amounts of data. After reading https://blog.burntsushi.net/regex-internals/ ("Literal optimizations') I realized it was trivial to implement a pruning algorithm by first scanning for some fixed sequence of the regex then matching via regex only these candidate chunks. This massively improved performance for us.

I suggest evaluating this optimization for the regex doExecute routine. It would work by extracting some literal substring of a given regex (I chose longest fixed sequence myself) then using bytes.Index to first scan the data for the matching literals. Then call the existing doExecute routine per candidate match. In case the literal is at the middle or end of a regex, the candidate chunks should be of length [-len(regex), len(regex)] this is a large enough window it encompasses the whole regex without any annoying specific offset fixups. bytes.Index is extremely fast based on testing, much more so than the regex execution routine.

Can you suggest some other library which solves regex for binary strings if this is not maintained?

Noticed at https://source.cloud.google.com/results/invocations/ef6e5fed-b9c8-4cd3-8c85-416d58dcbc3c/targets/cloud-go-libraries%2Fgoogle-cloud-go%2Fpresubmit%2Fgo19/log

the package doesn't build on Go1.9 because we use strings.Builder which was introduced in Go1.10.

However, we've got type aliases and can make a Buffer type that uses strings.Builder for >=Go1.10 otherwise bytes.Buffer, and since those types have the same methods this can be fixed with some build constraints

On <=Go1.9

// +build !go1.10
type Buffer = bytes.Buffer

On >=Go1.10

// +build go1.10
type Buffer = strings.Builder

I am mailing a fix shortly.

I have been looking into this library to allow regexp to match arbitrary byte sequences in a pattern. It seems that while it works fine for truly arbitrary bytes, utf8 bytes, or more precisely Go string literals with unicode characters in them, do not seem to get matched. While this library is not meant to use unicode semantics, e.g. I believe . matches a single byte, not a single rune, I would expect utf8 bytes themselves to still be matchable.

For context, re2 with Latin1 encoding, which intuitively seems like it would behave similarly to this library, is able to match utf8.

I have created a test case comparing binaryregexp and re2 with latin1 for the same expression/input using utf8 strings here

https://github.com/anuraaga/binaryregexp-unicodefailure

--- FAIL: TestUnicode (0.00s)
    --- FAIL: TestUnicode/ハロー/ハローワールド (0.00s)
        --- PASS: TestUnicode/ハロー/ハローワールド/re2 (0.00s)
        --- FAIL: TestUnicode/ハロー/ハローワールド/binaryregexp (0.00s)


    --- PASS: TestUnicode/ハロー/グッバイワールド (0.00s)
        --- PASS: TestUnicode/ハロー/グッバイワールド/re2 (0.00s)
        --- PASS: TestUnicode/ハロー/グッバイワールド/binaryregexp (0.00s)

FAIL