tre

package module
v0.1.2 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Nov 7, 2026 License: BSD-2-Clause Imports: 5 Imported by: 1

README

tre

A pure-Go port of TRE, the POSIX regular expression engine (leftmost-longest, submatch addressing with tags, lazy quantifiers, back-references, \< \> \b \w \d \s, (?i) and friends) that R uses for its default patterns (perl = FALSE, fixed = FALSE).

  • BSD 2-Clause, with the TRE notice kept in NOTICE.
  • Ported from upstream TRE at commit 71bfcaf (lib/tre-parse.c, tre-compile.c, tre-match-parallel.c, tre-match-backtrack.c, regexec.c): parse, AST, tagged NFA, the parallel matcher, and the backtracking matcher used only when the pattern has back-references.
  • Options.RCompat reproduces the behaviours of R 4.6.2's modified copy of TRE where they differ from upstream (listed below), so github.com/go-embedded-r/r answers like R.
  • Resource limits: pattern size, AST nodes, NFA states and transitions, the size of the firstpos/lastpos sets, and match steps. A hostile pattern or subject gets an error (ErrESpace, ErrSteps), never an out-of-memory or a hang.
re, err := tre.Compile(`(a|ab)(c|bcd)(d*)`, tre.Extended)
m, err := re.ExecString("abcd", 4, 0) // []tre.Match{{0,4},{0,1},{1,4},{4,4}}

Offsets are in characters (UTF-8 decoded), or bytes with tre.UseBytes.

Not ported

Approximate matching (tre-match-approx.c, the {~n}, {+n}, {1i+1d<2} bound syntax): a pattern using it fails with ErrApprox. The C library's system-wctype, multibyte-string and user-string front ends: one engine over []rune code units replaces them. Character classes use Go's unicode tables, so classes of non-ASCII characters can differ from a given C library's iswctype.

How it is checked

  • TRE's own tests: tests/retest.c is built from upstream and run through a recording wrapper (cmd/crefbuild -record); TestRetest replays every call against the port: 286 compilations and 3514 executions (wide) and 3510 (narrow) with byte-for-byte equal return codes and match offsets. Excluded and counted: the 4 narrow-API patterns of retest's EUC-JP section (20 executions), which run in a multibyte locale the port does not have.
  • Differential fuzz against upstream TRE built as C (TestDifferential, random patterns with lazy quantifiers, back-references, assertions, classes, every flag): 197,588 compared, 0 mismatches. Excluded and counted: 2,410 approximate-matching patterns, 1 backtracking case cut by the step limit.
  • R 4.6.2 for the R-level behaviour, through evalfuzz --mode regex of go-embedded-r/r (grepl, sub, gsub, regexpr, gregexpr, regmatches, strsplit).
  • Fuzz target FuzzCompileExec (corpus in testdata/fuzz), bomb tests that assert refusals under GOMEMLIMIT and ulimit -v, govulncheck, 3 OSes with -race, 386, every GOOS, wasm. The CI oracle lane rebuilds the C oracle at the pinned upstream commit.

Where R's copy differs from upstream TRE

Found by diffing R 4.6.2 src/extra/tre against upstream (R's changes are GPL and were used as specification only; the behaviours are re-implemented here and judged by R itself):

  • {,n} keeps a minimum of -1, so it matches n+1 repetitions (^a{,3}$ matches aaaa); a bound that overflows an int means "unbounded, or 1"; a bound above 255 is "Invalid contents of {}" (never "Maximum repetition"); {m,n} expands to (|x(|x)) rather than (x(x)?)?.
  • An empty REG_LITERAL pattern matches the empty string.
  • The backtracking matcher decides whether to retry from a later start position by the current character instead of the character at the start of the attempt: a back-reference search that fails at the end of the subject does not try later starts (([abc]+)\w*\1 does not match banana in R).
  • The items of a bracket expression (and the two cases of an (?i) literal) share one NFA position.
  • tre_copy_ast forgets the negated classes of a copied literal: in wide mode [^[:space:]]{1,3} matches a space on its repetitions.
  • Messages and limits: no TRE_MAX_RE, no REG_BADMAX, assert becomes an R error, one extra text for tre_version; int positions where upstream uses size_t.

Upstream changes R's old copy lacks, kept here: the pattern-length and string-length limits, the saturating bound parser, the hex-escape length limit.

Documentation

Overview

Package tre is a Go port of TRE, the POSIX regular expression engine by Ville Laurikari that R uses for its default (perl=FALSE, fixed=FALSE) patterns. It ports tre-parse.c, tre-compile.c, tre-match-parallel.c, tre-match-backtrack.c and regexec.c from upstream TRE; the licence notice of TRE is in the file NOTICE.

Not ported: approximate matching (tre-match-approx.c, the {~n} bound syntax); a pattern that uses it is rejected with ErrBadPat. The wide character, system wctype and multibyte-string front ends of the C library are replaced by one engine over []rune code units.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type EFlags

type EFlags int

EFlags are the tre_regexec() flags.

const (
	NotBOL EFlags = 1 // REG_NOTBOL
	NotEOL EFlags = 2 // REG_NOTEOL
	// BacktrackingMatcher forces the backtracking matcher
	// (REG_BACKTRACKING_MATCHER).
	BacktrackingMatcher EFlags = 8
)

type ErrCode

type ErrCode int

ErrCode is a TRE error code; the zero value, RegOK, is success. ErrCode implements error. The messages are those of TRE's regerror.c.

const (
	RegOK ErrCode = iota
	ErrNoMatch
	ErrBadPat
	ErrECollate
	ErrECType
	ErrEEscape
	ErrESubReg
	ErrEBrack
	ErrEParen
	ErrEBrace
	ErrBadBR
	ErrERange
	ErrESpace
	ErrBadRpt
	ErrBadMax
	// ErrSteps is not a TRE code: the match exceeded Limits.MaxSteps.
	ErrSteps
	// ErrApprox is not a TRE code: the pattern uses TRE's approximate
	// matching syntax ({~n}, {+n}, {1i+1d<2}), which is not ported.
	ErrApprox
)

The error codes, in the order of tre.h's reg_errcode_t.

func (ErrCode) Error

func (c ErrCode) Error() string

Error returns the TRE message for the code.

type Flags

type Flags int

Flags are the tre_regcomp() flags, with the values of tre.h.

const (
	Extended   Flags = 1  // REG_EXTENDED
	ICase      Flags = 2  // REG_ICASE
	Newline    Flags = 4  // REG_NEWLINE
	NoSub      Flags = 8  // REG_NOSUB
	Literal    Flags = 16 // REG_LITERAL: the pattern is a literal string
	RightAssoc Flags = 32 // REG_RIGHT_ASSOC
	Ungreedy   Flags = 64 // REG_UNGREEDY
	// UseBytes is R's REG_USEBYTES: the pattern and the subject are
	// sequences of bytes (code units below 256), not characters; character
	// classes are expanded over 0..255 as TRE does in a single-byte locale.
	UseBytes Flags = 128
)

type Limits

type Limits struct {
	// MaxPattern is the longest pattern in code units (default 65536, TRE's
	// TRE_MAX_RE).
	MaxPattern int
	// MaxNodes bounds the AST nodes, including those created by expanding
	// bounded repetition (default 1<<20).
	MaxNodes int
	// MaxStates bounds the positions (NFA states) (default 1<<19).
	MaxStates int
	// MaxTransitions bounds the NFA transitions (default 1<<23).
	MaxTransitions int
	// MaxSetItems bounds the entries of all firstpos/lastpos sets, whose
	// size can be quadratic in the pattern (default 1<<23).
	MaxSetItems int
	// MaxSteps bounds the work of one match: transitions examined by the
	// parallel matcher, loop iterations and transitions by the backtracking
	// matcher (default 1<<28; negative means unlimited).
	MaxSteps int
}

Limits bound the resources of one compilation and one match; the zero value of a field selects its default. They make hostile patterns and inputs fail with an error instead of exhausting memory or time.

type Match

type Match struct{ So, Eo int }

Match is one submatch: the offsets are in code units of the matched input (characters, or bytes in byte mode); -1 means the group did not take part.

type Options

type Options struct {
	Flags Flags
	// RCompat selects the behaviours of R's modified copy of TRE where they
	// differ from upstream TRE: {,n} keeps a minimum of -1 (so it matches
	// n+1 repetitions), a bound that overflows an int is "unbounded or 1",
	// a bound above 255 is "Invalid contents of {}" (never "Maximum
	// repetition"), {m,n} is expanded as (|x(|x...)) rather than (x(x...)?)?,
	// and an empty REG_LITERAL pattern matches "".
	RCompat bool
	Limits  Limits
}

Options configure Compile.

type Regexp

type Regexp struct {
	// contains filtered or unexported fields
}

Regexp is a compiled pattern. It is safe for concurrent use.

func Compile

func Compile(pattern string, flags Flags) (*Regexp, error)

Compile compiles pattern, a UTF-8 string, with default options. With the UseBytes flag each byte of the pattern is one code unit.

func CompileOptions

func CompileOptions(pattern string, opt Options) (*Regexp, error)

CompileOptions compiles pattern with the given options.

func CompileRunes

func CompileRunes(pattern []rune, opt Options) (*Regexp, error)

CompileRunes compiles a pattern given as code units.

func (*Regexp) Exec

func (re *Regexp) Exec(s []rune, nmatch int, eflags EFlags) ([]Match, error)

Exec matches the subject s, given as code units, and returns nmatch submatches (the first is the whole match). The error is ErrNoMatch when the subject does not match, ErrSteps when the step limit was exceeded.

func (*Regexp) ExecString

func (re *Regexp) ExecString(s string, nmatch int, eflags EFlags) ([]Match, error)

ExecString matches the string s. In byte mode every byte is a code unit and the offsets are byte offsets; otherwise s is decoded as UTF-8 and the offsets are in characters. A subject that is not valid UTF-8 does not match (TRE's mbrtowc failure).

func (*Regexp) HaveBackrefs

func (re *Regexp) HaveBackrefs() bool

HaveBackrefs reports whether the pattern has back references (and so is matched by the backtracking matcher).

func (*Regexp) MatchString

func (re *Regexp) MatchString(s string) bool

MatchString reports whether s matches (no submatches are computed).

func (*Regexp) NumSubexp

func (re *Regexp) NumSubexp() int

NumSubexp returns the number of parenthesized subexpressions.

Directories

Path Synopsis
cmd
crefbuild command
Command crefbuild builds the C oracle (upstream TRE with the differential harness and the retest recorder) and, with -record, writes the recordings of TRE's own tests to testdata.
Command crefbuild builds the C oracle (upstream TRE with the differential harness and the retest recorder) and, with -record, writes the recordings of TRE's own tests to testdata.
internal
cref
Package cref builds upstream TRE (C) with the harness and recorder of this directory and drives the harness: it is the engine-level oracle of the Go port's tests.
Package cref builds upstream TRE (C) with the harness and recorder of this directory and drives the harness: it is the engine-level oracle of the Go port's tests.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL