Logpat: A Regex Dialect for Alert Rules

Logpat: the Pattern Engine Behind Alert Rules

You've joined the team behind Logline, a log-search product. Customers write alert rules such as ^ERROR [[:digit:]]{3} in Logline's own small pattern dialect, and logpat (this codebase) decides which log lines match and what the capture groups contain. The engine is a hand-written parser plus a recursive backtracking matcher. Support has a pile of wrong-answer tickets, the highlighter team needs "find every match", compliance wants grep-style *longest* matches, and one customer's rule just took a worker down for ten minutes.

Do not use Python's re module (or any other library matcher such as fnmatch); the engine is the product. The dialect also differs from Python's in several deliberate ways (escapes, character classes, {, anchors, empty loops, and later the match rule), so re would give wrong answers anyway.

Codebase

charclass.py, nodes.py, results.py, textutil.py, errors.py and config.py are known-good.

How your code is run

run(operations: list[list]) -> list executes the operations in order and returns one result per operation. Every operation is [name, *args]. Errors are returned as strings, never raised.

• Text. text is a string, or an object {"repeat": unit, "times": n, "then": tail} meaning unit * n + tail (then is optional). unit/then are strings, n is an integer >= 0 (not true/false), no other keys are allowed, and the result may be at most 200 000 characters. Any other shape is invalid arguments. This is how very long inputs are written compactly.
• Match. {"span": [start, end], "groups": [...]}. Indexes are absolute positions in text (text[start:end] is the matched text). groups[g-1] is [start, end] for capture group g, or null if the group took no part in the match. A pattern without groups has "groups": [].
• Errors are "error: <code>". Argument problems are "error: invalid arguments": unknown argument count, pattern not a string, text neither a string nor a valid object, a non-object options. Unknown operation names are "error: unknown operation". A pattern that is not valid in the dialect is "error: bad pattern: <detail>" (details below). Argument problems are reported before the pattern is parsed, so ["search", "(", 5] is invalid arguments.

The pattern dialect (reference for every Part)

Characters. Any character other than \ . * + ? { ( ) [ | ^ $ matches itself (} and ] are ordinary characters). Matching is case-sensitive. . matches any character except \n.

Escapes. A backslash followed by n is a newline, by t a tab, by 1..9 a backreference (outside brackets only). Any other ASCII letter or digit after a backslash is bad escape. A backslash before anything else (punctuation, space, non-ASCII) is that character literally: \., \\, \{. A backslash that ends the pattern is trailing backslash. There are no \d, \w, \s, \b shorthands; use bracket classes.

Bracket classes [...]:

• A leading ^ negates the class. A negated class matches any character not listed, including \n.
• Items are: a single character, an escape (same rule as above, so [\]], [\-], [\] and [\n] work and [\d] is bad escape), a range lo-hi, or a named class [:name:] where name is one of digit alpha alnum upper lower space xdigit punct (ASCII only, e.g. [[:digit:]_]).
• A ] right after [ or [^ is not special: [] and [^] are empty class. Write [\]] instead.
• - is a literal only as the first or last item of the class (or escaped). Anywhere else it must form a range between two single characters, with lo <= hi; otherwise bad range ([b-a], [a-c-e], [[:digit:]-z], [a-[:digit:]]).
• A [ followed by : inside a class always starts a named class; an unknown or unterminated name is bad class (write `[

a] doesn't work, my class ends at the first ]." (same for [a\-z]`)

• "^ERROR only matches on the first line of a multi-line chunk, and $ only at the very end."
• "$ and x* never match an empty string at the end of the text."
• "(a)b|ac on ac reports group 1 = a, but the first branch never matched."
• "(a|b)+ on abba reports group 1 = a; I expected the last one."
• "After running a rule with groups, the *next* rule's groups come back null or its \1 is rejected."
• "(a*)* is accepted; Platform says rules like it must be rejected up front (see repeat can be empty)."

Do not assume this list is complete; use the dialect reference as the specification.

Example

[["search", "ab*c", "xabbbcx"],
 ["search", "(a)b|ac", "ac"],
 ["search", "(a|b)+", "abba"],
 ["search", "a{,3}", "aaa"],
 ["search", "^b", "a\nb"]]

returns

[{"span": [1, 6], "groups": []},
 {"span": [0, 2], "groups": [null]},
 {"span": [0, 4], "groups": [[3, 4]]},
 "error: bad pattern: bad repeat",
 {"span": [2, 3], "groups": []}]

Part 2: find_all and count (LOG-3077)

Goal: the highlighter needs every non-overlapping match in a text, left to right. Add ["find_all", pattern, text] returning the list of match objects, and ["count", pattern, text] returning how many matches find_all would return. Both report the same errors as search.

Rules

1. Start with pos = 0 and previous_end = -1. Repeatedly run search for the leftmost match starting at an index >= pos (anchors and ^ still look at the whole text, see Anchors).
2. If there is no match, stop.
3. If the match is empty and starts at previous_end (it would touch the end of the match just reported), drop it, set pos = start + 1 and continue. A non-empty match that starts there is fine.
4. Otherwise report it and set previous_end = end. Next pos is end if the match was non-empty, and end + 1 if it was empty.
5. Stop when pos > len(text). An empty text is searched once (so x* on "" has one match).
6. Dropping a match in rule 3 loses that position entirely: the engine does not look for a lower-priority match at the same start.

This is deliberately different from Python's re.findall.

Example

[["find_all", "[0-9]+", "a1b22c333"],
 ["find_all", "b*", "abb"],
 ["find_all", "^a", "aaa\naa"],
 ["count", "x*", ""]]

returns

[[{"span": [1, 2], "groups": []}, {"span": [3, 5], "groups": []}, {"span": [6, 9], "groups": []}],
 [{"span": [0, 0], "groups": []}, {"span": [1, 3], "groups": []}],
 [{"span": [0, 1], "groups": []}, {"span": [4, 5], "groups": []}],
 1]

(b* on abb: empty at 0, then bb; the empty match at 3 touches the end of bb, so it is dropped.)

Part 3: POSIX-style "longest" semantics (LOG-3120)

Goal: compliance wants alert rules to highlight the *longest* thing a rule can match, as grep does: error|error_code should cover the whole of error_code. Add an optional trailing options object to search, fullmatch, find_all and count: {"semantics": "first" | "longest"}. "first" (the default, and what options omitted or {} means) is the behaviour of Parts 1 and 2. Any other key, any other value, or an options that is not an object is invalid arguments (checked before the pattern is parsed).

Rules for "longest"

1. search still returns the match at the leftmost start position that has any match.
2. At that start, among all ways to match it picks the one with the greatest end. If several parses reach that same end, the highest-priority one (see priority order) wins, and its groups are reported. (Only the overall extent is POSIX-longest; captures are not subject to POSIX sub-match rules.)
3. fullmatch is unaffected by semantics: the end is already fixed at len(text).
4. find_all and count use the same rules as Part 2, with search replaced by the longest search.
5. Everything from Parts 1 and 2 still holds: errors, anchors, backreferences, and captures from abandoned paths never leaking.

Example (abcd)

[["search", "a|ab|abc", "abcd"],
 ["search", "a|ab|abc", "abcd", {"semantics": "longest"}],
 ["search", "(a|ab)(c?)", "abc"],
 ["search", "(a|ab)(c?)", "abc", {"semantics": "longest"}]]

returns

[{"span": [0, 1], "groups": []},
 {"span": [0, 3], "groups": []},
 {"span": [0, 1], "groups": [[0, 1], [1, 1]]},
 {"span": [0, 3], "groups": [[0, 2], [2, 3]]}]

Part 4: Catastrophic backtracking (INC-481) and a size limit

Goal: a customer rule (x+x+)+y against a long run of x took a worker down. Make matching run in time proportional to len(text) * (size of the pattern) for every pattern that has no backreference, with results identical to the backtracker's (spans, groups, both semantics, fullmatch, find_all).

Rules

1. Which patterns need the slow path. Exactly the patterns containing a backreference \k anywhere (inside a group, a repeat, an alternation, anywhere in the tree). They keep using the backtracker; tests only run them on short texts (a few hundred characters). Every other pattern must be matched without exponential blow-up, on texts of tens of thousands of characters, without hitting Python's recursion limit.
2. Engine option. options also accepts "engine": "auto" | "nfa" | "backtrack" (default "auto"). "auto" uses the fast engine unless the pattern has a backreference. "backtrack" forces the backtracker for any pattern. "nfa" on a pattern with a backreference returns "error: engine unsupported" (checked after the pattern is parsed, so a bad pattern is reported first). An unknown engine name is invalid arguments. Both engines must return identical results.
3. explain. ["explain", pattern] returns {"engine": "nfa" | "backtrack", "groups": n, "cost": c} where engine is what "auto" would pick, groups is the number of capture groups, and cost is defined next. Pattern errors are reported as for search; a non-string pattern is invalid arguments.
4. Pattern size limit (this changes Part 1). Patterns are now rejected with error: bad pattern: pattern too large when their cost exceeds 2000, for every operation and every engine. This is checked after the whole pattern parsed without any other error. The cost is the size of the pattern with every repeat written out:

• an ordinary character, ., a class, an anchor or a backreference costs 1; an empty branch costs 0;
• a concatenation costs the sum of its parts;
• a group costs 1 more than its body;
• an alternation costs the sum of its branches plus 1 for each |;
• x{m,n} costs n * cost(x), and x{m,} (including * and +) costs max(m, 1) * cost(x).

For example a(b|c)*d costs 6 and a{1000}a{1000} costs 2000 (allowed), while a{1000}a{1000}a and (a{1000}){2} are too large. Patterns that were valid in Part 1 but exceed the limit are now errors.

Example

[["explain", "a(b|c)*d"],
 ["explain", "((a)\\2)+"],
 ["search", "(a|a)*b", {"repeat": "a", "times": 2000}],
 ["search", "a{1000}a{1000}a", "a"],
 ["search", "(a)\\1", "aa", {"engine": "nfa"}]]

returns

[{"engine": "nfa", "groups": 1, "cost": 6},
 {"engine": "backtrack", "groups": 2, "cost": 4},
 null,
 "error: bad pattern: pattern too large",
 "error: engine unsupported"]

Notes

• You may use the AI assistant freely; you are expected to verify what it produces.
• Standard library only, but never re. No wall clock or randomness; output must be deterministic.
• Later Parts must not break earlier ones; hidden tests re-check earlier behaviour after every Part, with the fast engine and the backtracker.
• logpat runs on very long inputs in production: avoid recursion proportional to the text length in whatever you write for Part 4.
• Parts 1-3 is a strong result. Part 4 is a stretch.