PeopleCode Regex

A regular expression engine written entirely in PeopleCode. No Java calls, no external libraries, no App Engine shell-outs, and no database dependencies. It is a single Application Class that parses a pattern into an AST, optimizes it, and executes it with a backtracking matcher.

PeopleTools has never shipped a real regular expression API. Developers have historically been left with Find, Substring, using Java with APIs you can't remember or round tripping to your database to leverage regex functions there. This project fills that gap with a pure PeopleCode implementation that behaves the way developers coming from Java, .NET, JavaScript, or Python expect a regex engine to behave.

Contents

File	Purpose
Regex.pcode	The engine. This is the only file you need at runtime.
UnitTests.pcode	A self contained API test suite (over 300 assertions) that runs in seconds.
RE2TestRunner.pcode	A long running conformance harness that validates the engine against Google's RE2 test corpus.
test-suite/	The RE2 test corpus (5.7 million cases in NDJSON form) plus the most recent compliance report.

Installation

Choose an Application Package you want to add these classes to. Inside it, create a subpackage named Regex and add the Application Classes:

<YourPackage>:Regex:Regex        <- contents of Regex.pcode
<YourPackage>:Regex:UnitTests    <- contents of UnitTests.pcode  (optional)

The example code throughout this README assumes the classes live under GT_OSS, so an import reads import GT_OSS:Regex:Regex. Substitute your own package name wherever you see GT_OSS.

The package path matters. UnitTests.pcode and RE2TestRunner.pcode both contain import GT_OSS:Regex:... statements and create GT_OSS:Regex:Regex() calls. If you install the engine under a different package name, update the import and create statements in those two programs to match your package, or they will not compile.

Only Regex.pcode is required in production. The test programs are development aids.

Quick start

import GT_OSS:Regex:Regex;

Local GT_OSS:Regex:Regex &re = create GT_OSS:Regex:Regex();

/* Does the subject contain a match? */
&re.Init("\bcat\b");
If &re.Test("the cat sat") Then
   MessageBox(0, "", 0, 0, "Found it");
End-If;

/* Pull the pieces out of a version string */
&re.Init("(\d+)\.(\d+)\.(\d+)");
Local array of string &m = &re.Exec("version 1.2.3");
If &m <> Null Then
   /* &m[1] = "1.2.3", &m[2] = "1", &m[3] = "2", &m[4] = "3" */
End-If;

/* Reformat every date in a string */
&re.Init("(\d{2})/(\d{2})/(\d{4})");
Local string &s = &re.Replace("Born 03/15/1990 and 07/04/2000", "$3-$1-$2");
/* &s = "Born 1990-03-15 and 2000-07-04" */

A single Regex instance is reusable. Call Init again with a new pattern whenever you want to switch patterns.

Public API

Every pattern must be compiled with Init before any matching method is called.

Methods

Method	Returns	Description
Init(&pattern)		Compiles the pattern. Throws an exception on unsupported syntax.
Test(&subj)	boolean	True if the pattern matches anywhere in the subject.
Exec(&subj)	array of string	The leftmost match, or Null if there is no match. Element 1 is the full match, elements 2 through N+1 are capture groups 1 through N. Groups that did not participate come back as empty strings.
ExecAt(&subj, &startPos)	array of string	Attempts a match anchored at the given 1 based position. Returns Null if the pattern does not match starting exactly there.
ExecAll(&subj)	array of array of string	Every non overlapping match, each in the same shape Exec returns.
Replace(&subj, &repl)	string	Replaces every match.
ReplaceFirst(&subj, &repl)	string	Replaces only the first match.
Split(&subj)	array of string	Splits the subject on each match. Captures are discarded.
SplitWithCaptures(&subj)	array of string	Splits the subject and interleaves the capture groups between the segments.
Escape(&aInput)	string	Escapes regex metacharacters so a literal string can be used safely as a pattern.

Properties

Property	Type	Access	Description
Pattern	string	read	The pattern last passed to Init.
CaptureRanges	array of array of number	read	Positions of the last match. Each entry is a [start, end] pair using 1 based, inclusive offsets. Entry 1 is the full match, the rest are the groups. A group that did not participate is reported as [0, 0].
LastNamedCaptures	Hash	read	Named capture groups from the last match, keyed by group name. Each value is an array where element 2 holds the captured text.
SnapshotCount	number	read	Diagnostic. Number of capture state snapshots taken during the last match.
SnapshotRestoreCount	number	read	Diagnostic. Number of snapshot restores during the last match.

Configuration flags

All flags are plain properties on the instance. Set them before calling Init. Init copies the flag values into the compiled state, so a flag changed afterwards will not affect the already compiled pattern.

Flag	Type	Default	Effect
IgnoreCase	boolean	False	Case insensitive matching, equivalent to the i flag. Also applies to backreference comparison.
Multiline	boolean	False	^ and $ match at line boundaries rather than only at the start and end of the subject. Equivalent to the m flag.
DotAll	boolean	False	. also matches a newline. Equivalent to the s flag.
MaxSteps	number	200000	Backtracking budget. When a single match exceeds this many engine steps, the engine throws Match aborted: too many steps. Set to 0 or a negative number to fall back to the default.
EnableSurrogatePairs	boolean	True	Correct handling of non BMP characters such as emoji and rare CJK. See below.
DEBUG_TRACE	boolean	False	Emits the optimized AST and a step by step match trace.

Local GT_OSS:Regex:Regex &re = create GT_OSS:Regex:Regex();
&re.IgnoreCase = True;
&re.Multiline = True;
&re.Init("^error: (.+)$");     /* flags are captured here */

Flags can also be applied to part of a pattern using an inline flag group, which does not require touching the properties:

&re.Init("(?i:hello) WORLD");  /* "hello" is case insensitive, " WORLD" is not */

A note on EnableSurrogatePairs

PeopleCode strings are UTF-16, so a character outside the Basic Multilingual Plane (an emoji, for example) occupies two code units. Naive character-at-a-time matching would split those pairs and produce wrong results. When EnableSurrogatePairs is on, the engine internally maps each surrogate pair to a single private use area code point before compiling and matching, then maps it back on the way out, so . and + and character classes all treat the emoji as one character.

&re.EnableSurrogatePairs = True;
&re.Init("😀+");
Local array of string &m = &re.Exec("abc😀😀😀def");   /* &m[1] = "😀😀😀" */

This normalization pass costs time on every call. If you know your subjects and patterns are entirely within the BMP, which covers all ordinary Latin, accented, and CJK text, set EnableSurrogatePairs = False for a measurable speedup. The default is True, so this is an opt out rather than an opt in.

Two limits apply while it is on. A single subject may contain at most 6,400 distinct non BMP characters, which is the size of the private use area the engine borrows, and exceeding that throws PUA capacity exceeded. Character class ranges with non BMP endpoints, such as [😀-😎], are rejected at Init.

A note on DEBUG_TRACE

Trace output is written with %Response.Write, which means it is only useful from a context that has a response stream, such as an IScript or an iScript-backed page. Leave it off in Application Engine and in production code.

Safety limits

A backtracking engine can be driven into exponential behavior by a pathological pattern, the classic example being (a+)+b against a long run of a characters. Two guards are built in.

• Step budget. Controlled by MaxSteps, default 200,000. Exceeding it throws Match aborted: too many steps.
• Wall clock ceiling. A hard limit of 5 seconds per match attempt, after which the engine throws Match time exceeded. This is a private constant (&MAX_EXEC_TIME) rather than a property, so raising it means editing the class.

Both convert a hang into a catchable exception. Wrap Exec and friends in a try block if you are running untrusted or user supplied patterns.

The engine also applies several optimizations at compile time that reduce the chance of ever hitting these limits: dead node elimination, quantifier and character class simplification, group flattening, literal concatenation, alternation factoring, anchored start detection, literal prefix extraction for fast scanning, and memoization of failed match positions.

Supported syntax

Quantifiers

Syntax	Meaning
* + ?	Zero or more, one or more, zero or one. Greedy.
{n} {n,} {n,m}	Exact, minimum, and bounded repetition.
*? +? ?? {n,m}?	Lazy variants. Match as few as possible.
*+ ++ ?+ {n,m}+	Possessive variants. Match greedily and never give characters back.

Groups

Syntax	Meaning
(...)	Capturing group.
(?:...)	Non capturing group.
(?<name>...)	Named capturing group. Names start with a letter or underscore, and may then contain letters, digits, underscores, and hyphens.
(?P<name>...)	Named capturing group, Python spelling. Equivalent to the above.
(?>...)	Atomic group. Commits to the first way it matches.
(?i:...) (?m:...) (?s:...) (?-i:...)	Inline flag groups. Recognized flag letters are i, m, and s.
(?(1)yes|no)	Conditional. Chooses a branch based on whether a group participated.
(?R) (?1)	Recursion into the whole pattern or into a numbered group.

Backreferences

Syntax	Meaning
\1 through \99	Numbered backreference. Two digit forms resolve greedily: \12 means group 12 when 12 groups exist, otherwise group 1 followed by a literal 2.
\k<name> \k'name'	Named backreference.

Lookaround

Syntax	Meaning
(?=...)	Positive lookahead.
(?!...)	Negative lookahead.
(?<=...)	Positive lookbehind. Must be fixed width.
(?<!...)	Negative lookbehind. Must be fixed width.

Lookbehinds are validated at Init time and must have a single, known width. A lookbehind whose width cannot be determined throws Variable-length lookbehind not supported. That rules out three things:

• An unbounded or ranged quantifier, so (?<=a+) and (?<=a{1,3}) throw, while (?<=a{3}) is fine.
• An alternation whose branches differ in width, so (?<=a|bc) throws, while (?<=ab|cd) is fine.
• An anchor or boundary inside the lookbehind, so (?<=\bfoo) throws.

Backreferences inside a lookbehind are supported as long as the group they point at is itself fixed width. Captures made inside any lookaround are rolled back once the assertion completes, so they are not visible in the final result.

Anchors and boundaries

^ $ \A \Z \z \b \B

^ and $ respect the Multiline flag. \A and \z are always absolute.

Character classes and escapes

Syntax	Meaning
[abc] [^abc] [a-z]	Class, negated class, range.
\d \D \w \W \s \S	Digit, word, and whitespace shorthands and their negations. Valid inside and outside a class. \s covers space, tab, newline, form feed, and carriage return, matching RE2 rather than PCRE.
[[:alpha:]] and friends	POSIX classes: alnum, alpha, blank, cntrl, digit, graph, lower, print, punct, space, upper, xdigit. An unrecognized name throws.
\n \r \t \f \v \a \e \\	Control and literal escapes. Valid inside and outside a class. \e is bell, not escape.
.	Any character except a line feed, or any character at all when DotAll is set. A carriage return is matched by . even without DotAll.
\C	Any character, including a line feed, regardless of the DotAll setting.
|	Alternation.

Class subtraction and intersection, as in [a-z&&[^aeiou]], are not supported. Inside a class, & and a nested [ are ordinary literal characters.

Replacement syntax

Replace and ReplaceFirst expand the following tokens in the replacement string.

Token	Expands to
$0 through $99	The full match, or the numbered capture group.
${1} ${name}	Braced form of a numbered or named group. Use this when the following character would otherwise be read as part of the number.
$&	The full match.
$`	The text before the match.
$'	The text after the match.
$$	A literal dollar sign.
\1 through \9	Alternative backreference form.
\n \r \t \\	Newline, carriage return, tab, and a literal backslash.

An unrecognized $ sequence is passed through unchanged rather than throwing.

Not supported

The following constructs are rejected or absent. Where the engine throws, it does so at Init time rather than silently doing the wrong thing.

Construct	Behavior
(?i) style bare inline flags	Throws. Use the group form (?i:...), or set the IgnoreCase property.
(?#comment)	Throws.
(?'name'...) .NET named groups, (?P=name) Python named backreferences, (?|...) branch reset	Throws. Any (? construct the parser does not recognize reports the inline flag error. Use (?<name>...) and \k<name> instead.
Variable width lookbehind, or a lookbehind containing an anchor or boundary	Throws.
Unknown POSIX class names, including negated forms such as [:^alpha:]	Throws.
A character class range with a non BMP endpoint, such as [😀-😎]	Throws.
\xHH, \x{HHHH}, \uHHHH, \cX, octal escapes	Not implemented, and they do not throw. \x41 is read as a literal x followed by 41, and \0 is a literal 0. Build the character with Char(65) in PeopleCode instead.
\p{...} Unicode property classes	Not implemented. \p is a literal p.
\Q ... \E literal quoting	Not implemented. Use the Escape method instead.
Extended or verbose mode (x flag)	Not implemented. (?x:...) is accepted but the x is silently ignored, so whitespace and # in a pattern are always significant.
\G, \K, \h, \H, \R, \N, \X	Not implemented. Each is read as the bare literal letter.
Class subtraction and intersection	Not implemented.
Leftmost-longest (POSIX) match semantics	Not implemented. The engine is leftmost-first, like PCRE, Java, and .NET.

One parsing behavior fails quietly. A { that follows an atom is always treated as the start of a quantifier, and there is no fallback that reinterprets a malformed quantifier as a literal brace. Write \{ whenever you mean a literal opening brace after an atom.

Compliance

The engine is validated against the published test corpus for Google's RE2, by way of the sihlfall/regex-test-cases reformatting of it. The corpus lives in test-suite/data as 27 NDJSON files.

The most recent full run, checked in at test-suite/results.html:

Metric	Result
Total test cases	5,716,884
Distinct patterns compiled	107,012
Match accuracy	100.0%
Group accuracy	100.0%
Errors	0
Total runtime	2,416 seconds
Average time per case	0.14 ms to 2.31 ms depending on the suite

The corpus covers literal matching including case folding and UTF-8, simple and capturing repetition, exhaustive empty string behavior, punctuation, line endings, character classes, and awkward UTF-8 sequences.

Two caveats.

The corpus tests unanchored, leftmost-first semantics only. The original RE2 data records four results per case, crossing two match semantics (leftmost-first and leftmost-longest) with two anchoring modes. This repository keeps only the unanchored leftmost-first entry, which is the semantic that PCRE, Java, .NET, JavaScript, and Python all use. The engine is not validated against, and does not implement, RE2's leftmost-longest mode.

The corpus does not exercise the PCRE style extensions. Lookaround, backreferences, atomic groups, conditionals, and recursion are outside what RE2 supports, so they are not in the RE2 data. Those features are covered by UnitTests.pcode instead. Taken together: RE2 conformance establishes that the common core is correct against a very large body of cases, and the unit tests establish that the extensions behave the way a PCRE user expects.

Running the tests

Unit tests

UnitTests.pcode is fast, has no external dependencies, and is the one to run after any change to the engine. It is designed to be driven from an IScript so the results render in a browser, but it works from anywhere that can create the class.

import GT_OSS:Regex:UnitTests;

Local GT_OSS:Regex:UnitTests &t = create GT_OSS:Regex:UnitTests();
&t.RunTests();

%Response.Write("Passed: " | &t.Passed | " of " | &t.Total | " in " | &t.Duration | "s<br />");

Local number &i;
For &i = 1 To &t.Failures.Len
   %Response.Write(&t.Failures [&i] | "<br />");
End-For;

It covers Test, Replace, ReplaceFirst, ExecAll, Split, SplitWithCaptures, backreferences, backreferences inside lookbehinds, non BMP handling, and a set of end to end integration cases.

RE2 conformance runner

RE2TestRunner.pcode walks the entire 5.7 million case corpus. A full run takes roughly forty minutes, which puts it well past what a page or an IScript will tolerate, so run it as an Application Engine program. It also reads the corpus from the local file system and writes an HTML report back to it, so it is meant to run in two tier mode against your development machine, launched from Application Designer, with the repository checked out locally.

Before running it, edit the two hard coded paths near the top of the program:

Local array of string &fileNames = FindFiles("C:\path\to\test-suite\data\*.ndjson", %FilePath_Absolute);
Local string &outputLogPath = "C:\path\to\test-suite\results.html";

Two knobs are useful while iterating:

• &onlyFileIndex runs a single corpus file instead of all 27. Set it to 0 for a full run, or to a 1 based index to isolate one file. This turns a forty minute run into a much shorter one when you are chasing a specific regression.
• &stopOnUTF8Error halts on the first UTF-8 mismatch rather than recording it and continuing.

Progress is reported through MessageBox every 10,000 cases, and the final HTML report lands at &outputLogPath.

Credits and license

This engine began as a port of the ASF regex engine by ECP Solutions, and has been substantially extended since. The original ASF license notice is retained at the top of Regex.pcode.

The engine is released under the MIT License. See LICENSE.

The RE2 test corpus in test-suite/ carries its own license from the original test case distribution. See test-suite/LICENSE.