Skip to content
go-regexpPublic

About

Pure-Go regex engine (Onigmo lineage) with a stdlib-regexp-shaped API + lookaround/backrefs that RE2 cannot do.

Resources

Stars

1 star

Watchers

0 watching

Forks

Latest commit

 

History

16 Commits

Folders and files

NameName
Last commit message
Last commit date
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

go-regexp/engine

ci Go Reference License: BSD-3-Clause

A pure-Go (cgo-free) regular-expression engine compatible with Onigmo — the regular-expression library Ruby uses — with a public API shaped like the standard library's regexp package.

Why

The standard library regexp is built on RE2, which guarantees linear-time matching by forbidding features that require backtracking. go-regexp/engine supports the constructs RE2 rejects at compile time:

  • Lookahead (?=…) / (?!…) and lookbehind (?<=…) / (?<!…)
  • Backreferences \1, \k<name>
  • Atomic groups (?>…) and possessive quantifiers
  • Subexpression calls \g<name>, \g<0> (recursive patterns)
  • Ruby/Onigmo character properties, \h/\H, \R, named groups, and more

It matches on the backtracking VM for those patterns and transparently falls back to a linear-time lazy-NFA/DFA accelerator for the RE2-compatible subset, so the common case stays fast while the extra features remain available.

The package is named onigmo (not regexp), so it can be imported alongside the standard library regexp without an alias.

Install

go get github.com/go-regexp/engine

Usage

package main

import (
	"fmt"

	onigmo "github.com/go-regexp/engine"
)

func main() {
	// A lookahead — (?=["<]) — that RE2/stdlib regexp cannot compile.
	re := onigmo.MustCompile(`v\d+\.\d+\.\d+(?=["<])`)

	fmt.Println(re.FindAllString(`grab v1.2.3" and v4.5.6< but not v9.9.9`, -1))
	// [v1.2.3 v4.5.6]

	fmt.Println(re.MatchString(`v2.0.0"`)) // true
	fmt.Println(re.FindStringIndex(`x v3.4.5<`)) // [2 8]
}

API

The *Regexp API mirrors the standard library regexp where it overlaps:

Method Meaning
Compile, MustCompile compile a pattern (panicking variant)
String the source pattern
MatchString(s), Match(b) does the input contain a match?
FindString, FindStringIndex leftmost match text / [begin,end)
FindAllString, FindAllStringIndex all non-overlapping matches (n < 0 = all)
FindStringSubmatch, FindStringSubmatchIndex leftmost match with capture groups
NumSubexp, SubexpNames, SubexpIndex capturing-group introspection

Extensions beyond the standard library:

Method Meaning
CompileEnc, MustCompileEnc, Encoding UTF-8 vs binary (ASCII8BIT) matching
MatchBounds, MatchBoundsAt allocation-free whole-match [begin,end); …At anchors at a byte offset without scanning forward
FindStringSubmatchIndexAt anchored submatch (cursor-style lexing)
WithTimeout, Timeout per-match wall-clock limit for pathological patterns
MatchBoundsErr, MatchBoundsAtErr, FindStringSubmatchIndexErr, FindStringSubmatchIndexAtErr the same four primitives, reporting why there is no match: ErrTimeout or ErrBudget when the search was abandoned with the answer still unknown

If you are using a Regexp as a guard — a validator, a denylist, an allowlist — use an …Err method and treat a non-nil error as a refusal. The standard-library-shaped methods fold both limits into "no match", so a search abandoned on a crafted subject is indistinguishable from a subject that simply does not match, and the guard reads as "did not fire". That is fail-open, and it is what Ruby's Regexp::TimeoutError exists to prevent. Note that ErrBudget needs no timeout to be configured: it is reached under DefaultBudget on a catastrophically backtracking pattern ((a+)+\1b against "a"*26 is abandoned in ~0.83 s).

FindAll* follow the standard library's non-overlapping, left-to-right semantics, including empty-match handling (an empty match advances by one rune and an empty match adjacent to a previous match is skipped).

A *Regexp is immutable once compiled and safe for concurrent use by multiple goroutines. The heavy matcher state is built lazily on the first match.

Matching state is pooled and sized by how far a match explores, not by the length of the input: the backtracking VM's (instruction, position) memo covers only the positions an attempt reaches, and lookarounds reuse one frame per nesting depth. A tokenizer that calls FindStringSubmatchIndexAt at a cursor inside a long buffer therefore allocates little more than the capture slice it gets back (on go-slides' 100-slide benchmark deck, highlighted by go-rouge, a render went from 52 MB to 11 MB allocated).

Status

Engine and public API are complete with 100% test coverage and CI on the six supported 64-bit architectures (amd64, arm64, riscv64, loong64, ppc64le, s390x). A full org landing page, logo and hosted documentation are a follow-up.

License

BSD-3-Clause. See LICENSE.

About

Pure-Go regex engine (Onigmo lineage) with a stdlib-regexp-shaped API + lookaround/backrefs that RE2 cannot do.

Resources

Stars

1 star

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages