Local code intelligence for developers and AI agents. Connect code, docs and infrastructure in a persistent graph, with CBM Lens, MCP tools, agent integrations and change-aware test selection.
C aiderastclaude-codecode-analysiscode-intelligencecodexcursorcypherdeveloper-toolsgemini-cligraph-visualizationkilocodeknowledge-graphmcpmcp-servermodel-context-protocolopencodesqlitetree-sitterwindsurf
/*
* compat_regex.c — Portable regular expression implementation.
*
* POSIX: direct wrappers around <regex.h>.
* Windows: vendored TRE regex library (BSD-licensed).
*
* Both backends expand bounded repetition at compile time, so cbm_regcomp
* sizes a pattern first (the compile-size guard below) and refuses one whose
* compiled form would be too large, before the platform compiler allocates
* anything.
*/
#include "foundation/constants.h"
#include "foundation/compat_regex.h"
#include <stdbool.h>
#include <stdint.h>
#include <string.h>
/* ── Compile-size guard (shared by both backends) ─────────────────
*
* The platform compilers expand `X{m,n}` into n copies of X, so nested
* intervals multiply: `((((a){20}){20}){20}){20}` is 160,000 expanded atoms
* from 25 bytes of pattern. A K-way alternation additionally costs about K^2
* position-set entries on the TRE-derived backends (macOS libc and the vendored
* TRE), because every union node copies its branches' sets.
*
* Measured on macOS libc with REG_EXTENDED|REG_NOSUB: the nested shape costs
* about 0.6 KB of heap per expanded atom, 1.1 KB with submatch tracking on,
* 1.7 KB with REG_ICASE and 2.3 KB with both; a K-way alternation adds about
* 70 B x K^2 on top of its branches (twice that under REG_ICASE), and an
* alternation under an interval pays that for every copy, about 1 KB per unit
* with REG_NOSUB and 2.8 KB with REG_ICASE plus submatches. glibc costs about
* 0.45 KB per atom and expands intervals the same way.
*
* cbm_regcomp_estimate_units() counts expanded atoms in one linear pass with
* saturating arithmetic and charges a K-way alternation K^2/8 units, the
* measured ratio between the two costs. With CBM_REGEX_COMPILE_BUDGET_UNITS =
* 32768 the heaviest accepted compile is a repeated alternation at about 30 MB
* with REG_NOSUB and about 90 MB under the ICASE-plus-submatch flag set no
* call site uses; the nested shape tops out at 13^4 = 28,561 units, about
* 16 MB. `(\w{1,100}){1,20}` (2,000 units) and an alternation of 500 short
* names (31,250 units plus its letters) remain accepted. */
enum { REGEX_GROUP_DEPTH_MAX = 64 };
typedef struct {
uint64_t total; /* units of this group so far; includes `last` */
uint64_t last; /* units of the element a following quantifier applies to */
uint64_t branches; /* alternatives in this group: 1 + the number of '|' */
} regex_frame_t;
static uint64_t regex_sat_add(uint64_t a, uint64_t b) {
return a > UINT64_MAX - b ? UINT64_MAX : a + b;
}
static uint64_t regex_sat_mul(uint64_t a, uint64_t b) {
if (a == 0 || b == 0) {
return 0;
}
return a > UINT64_MAX / b ? UINT64_MAX : a * b;
}
static void regex_frame_atom(regex_frame_t *f, uint64_t units) {
f->total = regex_sat_add(f->total, units);
f->last = units;
}
/* An interval applies to the last element: n copies of it replace the one. */
static void regex_frame_repeat_last(regex_frame_t *f, uint64_t copies) {
uint64_t grown = regex_sat_mul(f->last, copies);
f->total = regex_sat_add(f->total - f->last, grown);
f->last = grown;
}
/* Units a closed group contributes to its parent: its content plus the K^2/8
* alternation share, never less than one atom. */
static uint64_t regex_frame_units(const regex_frame_t *f) {
uint64_t alternation = regex_sat_mul(f->branches, f->branches) / 8;
uint64_t units = regex_sat_add(f->total, alternation);
return units ? units : 1;
}
/* Skip the bracket expression opening at p[i] == '['. Returns the index just
* past its closing ']', or the end of the string when it is unterminated.
* Nothing inside is an operator: `[]a]`, `[^]a]` and `[[:alpha:]]` are each
* one atom, and a brace inside brackets never opens an interval. */
static size_t regex_skip_bracket(const char *p, size_t i) {
size_t j = i + 1;
if (p[j] == '^') {
j++;
}
if (p[j] == ']') {
j++;
}
while (p[j] && p[j] != ']') {
if (p[j] == '[' && (p[j + 1] == ':' || p[j + 1] == '=' || p[j + 1] == '.')) {
char close = p[j + 1];
size_t k = j + 2;
while (p[k] && !(p[k] == close && p[k + 1] == ']')) {
k++;
}
j = p[k] ? k + 2 : k;
} else {
j++;
}
}
return p[j] ? j + 1 : j;
}
static bool regex_parse_digits(const char *p, size_t *i, uint64_t *value) {
bool any = false;
*value = 0;
while (p[*i] >= '0' && p[*i] <= '9') {
*value = regex_sat_add(regex_sat_mul(*value, 10), (uint64_t)(p[*i] - '0'));
(*i)++;
any = true;
}
return any;
}
/* Parse the interval body that starts at p[i], just past the opening brace
* (`{` in extended syntax, `\{` in basic). On success stores the number of
* copies the compiler will make (the upper bound, or the lower bound for
* `{m,}`, at least 1) and the index just past the closing brace. Anything that
* is not an interval leaves the brace to be counted as a literal, which is what
* the backends that accept it do; the others reject the pattern. */
static bool regex_parse_interval(const char *p, size_t i, bool extended, uint64_t *copies,
size_t *end) {
uint64_t lower = 0;
uint64_t upper = 0;
bool has_lower = regex_parse_digits(p, &i, &lower);
bool has_upper = false;
if (p[i] == ',') {
i++;
has_upper = regex_parse_digits(p, &i, &upper);
} else {
if (!has_lower) {
return false;
}
upper = lower;
has_upper = true;
}
if (extended) {
if (p[i] != '}') {
return false;
}
i++;
} else {
if (p[i] != '\\' || p[i + 1] != '}') {
return false;
}
i += 2;
}
uint64_t n = has_upper ? upper : lower;
if (has_upper && lower > upper) {
n = lower; /* `{5,3}` is rejected by the backends; count the larger bound */
}
*copies = n ? n : 1;
*end = i;
return true;
}
uint64_t cbm_regcomp_estimate_units(const char *pattern, int flags) {
const bool extended = (flags & CBM_REG_EXTENDED) != 0;
regex_frame_t frames[REGEX_GROUP_DEPTH_MAX];
int depth = 0;
frames[0] = (regex_frame_t){0, 0, 1};
size_t i = 0;
while (pattern[i]) {
char c = pattern[i];
if (c == '[') {
i = regex_skip_bracket(pattern, i);
regex_frame_atom(&frames[depth], 1);
continue;
}
/* In extended syntax the bare characters operate and `\x` is one
* literal; in basic syntax only `\(`, `\)`, `\{`, `\|`, `\+`, `\?` and
* a bare `*` operate. */
char op = 0;
size_t len = 1;
if (c == '\\') {
len = pattern[i + 1] ? 2 : 1;
if (!extended && len == 2 && strchr("(){|+?", pattern[i + 1])) {
op = pattern[i + 1];
}
} else if (extended ? strchr("(){|*+?", c) != NULL : c == '*') {
op = c;
}
regex_frame_t *f = &frames[depth];
switch (op) {
case '(':
if (depth + 1 >= REGEX_GROUP_DEPTH_MAX) {
return UINT64_MAX;
}
frames[++depth] = (regex_frame_t){0, 0, 1};
break;
case ')':
if (depth == 0) {
regex_frame_atom(f, 1); /* unmatched: a literal where accepted */
break;
}
depth--;
regex_frame_atom(&frames[depth], regex_frame_units(f));
break;
case '|':
f->branches = regex_sat_add(f->branches, 1);
f->last = 0;
break;
case '{': {
uint64_t copies = 0;
size_t end = 0;
if (regex_parse_interval(pattern, i + len, extended, &copies, &end)) {
regex_frame_repeat_last(f, copies);
i = end;
continue;
}
regex_frame_atom(f, 1);
break;
}
case '*':
case '+':
case '?':
break; /* unbounded or optional repetition is not expanded */
default:
regex_frame_atom(f, 1);
break;
}
i += len;
}
while (depth > 0) {
regex_frame_t *f = &frames[depth];
depth--;
regex_frame_atom(&frames[depth], regex_frame_units(f));
}
return regex_frame_units(&frames[0]);
}
/* Refuse a pattern before the platform compiler sees it. */
static int regex_compile_guard(const char *pattern, int flags) {
size_t len = 0;
while (len <= (size_t)CBM_REGEX_PATTERN_MAX_BYTES && pattern[len]) {
len++;
}
if (len > (size_t)CBM_REGEX_PATTERN_MAX_BYTES) {
return CBM_REG_ETOOBIG;
}
if (cbm_regcomp_estimate_units(pattern, flags) > (uint64_t)CBM_REGEX_COMPILE_BUDGET_UNITS) {
return CBM_REG_ETOOBIG;
}
return CBM_REG_OK;
}
#ifdef _WIN32
/* ── Windows: use vendored TRE regex ─────────────────────────── */
#include "../../vendored/tre/regex.h"
_Static_assert(sizeof(regex_t) <= CBM_SZ_256,
"cbm_regex_t opaque buffer too small for TRE regex_t");
static int translate_flags_tre(int flags) {
int tre_flags = 0;
if (flags & CBM_REG_EXTENDED)
tre_flags |= REG_EXTENDED;
if (flags & CBM_REG_ICASE)
tre_flags |= REG_ICASE;
if (flags & CBM_REG_NOSUB)
tre_flags |= REG_NOSUB;
if (flags & CBM_REG_NEWLINE)
tre_flags |= REG_NEWLINE;
return tre_flags;
}
int cbm_regcomp(cbm_regex_t *r, const char *pattern, int flags) {
int refused = regex_compile_guard(pattern, flags);
if (refused != CBM_REG_OK) {
return refused;
}
regex_t *re = (regex_t *)r->opaque;
int rc = tre_regcomp(re, pattern, translate_flags_tre(flags));
return rc == 0 ? CBM_REG_OK : rc;
}
int cbm_regexec(const cbm_regex_t *r, const char *str, int nmatch, cbm_regmatch_t *matches,
int eflags) {
const regex_t *re = (const regex_t *)r->opaque;
if (nmatch <= 0 || !matches) {
int rc = tre_regexec(re, str, 0, NULL, eflags);
return rc == 0 ? CBM_REG_OK : CBM_REG_NOMATCH;
}
regmatch_t pmatch[CBM_SZ_32];
int n = nmatch > CBM_SZ_32 ? CBM_SZ_32 : nmatch;
int rc = tre_regexec(re, str, (size_t)n, pmatch, eflags);
if (rc != 0)
return CBM_REG_NOMATCH;
for (int i = 0; i < n; i++) {
matches[i].rm_so = (int)pmatch[i].rm_so;
matches[i].rm_eo = (int)pmatch[i].rm_eo;
}
return CBM_REG_OK;
}
void cbm_regfree(cbm_regex_t *r) {
regex_t *re = (regex_t *)r->opaque;
tre_regfree(re);
}
#else /* POSIX */
/* ── POSIX implementation ─────────────────────────────────────── */
#include <regex.h>
/* Static assert: our opaque buffer is large enough for regex_t.
* If this fires, increase cbm_regex_t.opaque size. */
_Static_assert(sizeof(regex_t) <= CBM_SZ_256, "cbm_regex_t opaque buffer too small for regex_t");
static int translate_flags(int flags) {
int posix_flags = 0;
if (flags & CBM_REG_EXTENDED) {
posix_flags |= REG_EXTENDED;
}
if (flags & CBM_REG_ICASE) {
posix_flags |= REG_ICASE;
}
if (flags & CBM_REG_NOSUB) {
posix_flags |= REG_NOSUB;
}
if (flags & CBM_REG_NEWLINE) {
posix_flags |= REG_NEWLINE;
}
return posix_flags;
}
int cbm_regcomp(cbm_regex_t *r, const char *pattern, int flags) {
int refused = regex_compile_guard(pattern, flags);
if (refused != CBM_REG_OK) {
return refused;
}
regex_t *re = (regex_t *)r->opaque;
int rc = regcomp(re, pattern, translate_flags(flags));
return rc == 0 ? CBM_REG_OK : rc;
}
int cbm_regexec(const cbm_regex_t *r, const char *str, int nmatch, cbm_regmatch_t *matches,
int eflags) {
const regex_t *re = (const regex_t *)r->opaque;
if (nmatch <= 0 || !matches) {
int rc = regexec(re, str, 0, NULL, eflags);
return rc == 0 ? CBM_REG_OK : CBM_REG_NOMATCH;
}
/* Map through POSIX regmatch_t */
regmatch_t pmatch[CBM_SZ_32];
int n = nmatch > CBM_SZ_32 ? CBM_SZ_32 : nmatch;
int rc = regexec(re, str, (size_t)n, pmatch, eflags);
if (rc != 0) {
return CBM_REG_NOMATCH;
}
for (int i = 0; i < n; i++) {
matches[i].rm_so = (int)pmatch[i].rm_so;
matches[i].rm_eo = (int)pmatch[i].rm_eo;
}
return CBM_REG_OK;
}
void cbm_regfree(cbm_regex_t *r) {
regex_t *re = (regex_t *)r->opaque;
regfree(re);
}
#endif /* _WIN32 */