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
/* Query-local test-selection policy. Project rules retain their declared order.
*/
#include "foundation/arena.h"
#include "mcp/test_impact.h"
#include <limits.h>
#include <stdint.h>
#include <string.h>
#include <yyjson/yyjson.h>
enum {
TP_MAX_PATTERN = 65536,
TP_MAX_COMPAT_PATHS = 256,
TP_MAX_COMPAT_PATH = 1024,
TP_MAX_EXPANSIONS = 4096,
TP_MAX_EXPANDED_BYTES = 262144,
TP_MAX_BRACE_DEPTH = 16,
TP_MAX_MATCH_BYTES = 65536,
TP_MATCH_MAX_WORK = 16 * 1024 * 1024
};
typedef enum {
TP_LITERAL,
TP_QUESTION,
TP_STAR,
TP_DOUBLE_STAR,
TP_DOUBLE_STAR_SLASH,
TP_CLASS
} tp_token_kind_t;
typedef struct {
tp_token_kind_t kind;
unsigned char literal;
const unsigned char *class_bits;
} tp_token_t;
typedef struct tp_pattern tp_pattern_t;
struct tp_pattern {
const char *text;
size_t len;
tp_pattern_t *next;
tp_token_t *tokens;
size_t token_count;
bool rooted;
bool dir_only;
bool disabled;
};
typedef struct {
tp_pattern_t *head;
tp_pattern_t *tail;
bool perf;
} tp_patterns_t;
typedef struct {
tp_patterns_t paths;
tp_patterns_t suites;
} tp_rule_matchers_t;
typedef struct {
tp_patterns_t suites;
tp_patterns_t excludes;
} tp_lane_matchers_t;
struct cbm_test_policy {
CBMArena arena;
cbm_test_rule_t *rules;
tp_rule_matchers_t *rule_matchers;
int rule_count;
cbm_test_lane_t *lanes;
tp_lane_matchers_t *lane_matchers;
int lane_count;
const char *digest;
size_t expansion_count;
size_t expanded_bytes;
const char **compat_paths;
int compat_count;
};
/* Expansion uses an acyclic graph with shared continuations. Its explicit
* traversal stack bounds stack use even for thousands of adjacent groups. */
typedef struct tp_expand_node tp_expand_node_t;
struct tp_expand_node {
const char *text;
size_t len;
tp_expand_node_t *next;
tp_expand_node_t *alternatives;
tp_expand_node_t *sibling;
};
typedef struct {
tp_expand_node_t *head;
tp_expand_node_t *tail;
} tp_chain_t;
typedef struct {
CBMArena arena;
const char *text;
size_t len;
size_t pos;
size_t alternative_count;
bool valid;
} tp_expander_t;
static yyjson_val *tp_field(yyjson_val *object, const char *name, bool *valid) {
if (!yyjson_is_obj(object)) {
*valid = false;
return NULL;
}
yyjson_val *found = NULL, *key, *value;
size_t index, maximum, len = strlen(name);
yyjson_obj_foreach(object, index, maximum, key, value) {
if (yyjson_get_len(key) == len && memcmp(yyjson_get_str(key), name, len) == 0) {
if (found) {
*valid = false;
return NULL;
}
found = value;
}
}
return found;
}
static const char *tp_string(yyjson_val *value, size_t *len) {
const char *text = yyjson_get_str(value);
size_t n = yyjson_get_len(value);
if (!text || !n || strlen(text) != n)
return NULL;
if (len)
*len = n;
return text;
}
static bool tp_pattern_valid(const char *text, size_t len) {
if (!text || !len || len > TP_MAX_PATTERN || text[0] == '!' || text[0] == '#' ||
memchr(text, '\0', len) || memchr(text, '\n', len) || memchr(text, '\r', len))
return false;
if (text[len - 1] == ' ' || text[len - 1] == '\t') {
size_t escapes = 0;
for (size_t i = len - 1; i && text[i - 1] == '\\'; i--)
escapes++;
if (!(escapes & 1U))
return false;
}
return true;
}
/* Braces and commas inside a well-formed class are not expansion syntax.
* An unmatched '[' is a literal; it does not hide later brace syntax. */
static size_t tp_class_end(const char *text, size_t len, size_t open) {
size_t i = open + 1;
if (i < len && (text[i] == '!' || text[i] == '^'))
i++;
if (i < len && text[i] == ']')
i++;
for (; i < len; i++) {
if (text[i] == '\\' && i + 1 < len) {
i++;
continue;
}
if (text[i] == ']')
return i + 1;
}
return open + 1;
}
static tp_expand_node_t *tp_expand_node(tp_expander_t *exp, const char *text, size_t len) {
tp_expand_node_t *node = cbm_arena_calloc(&exp->arena, sizeof(*node));
if (!node) {
exp->valid = false;
return NULL;
}
node->text = text;
node->len = len;
return node;
}
static void tp_chain_append(tp_chain_t *chain, tp_chain_t add) {
if (!add.head)
return;
if (chain->tail)
chain->tail->next = add.head;
else
chain->head = add.head;
chain->tail = add.tail;
}
static void tp_chain_literal(tp_expander_t *exp, tp_chain_t *chain, const char *text, size_t len) {
tp_expand_node_t *node = tp_expand_node(exp, text, len);
tp_chain_t one = {node, node};
tp_chain_append(chain, one);
}
static tp_chain_t tp_parse_sequence(tp_expander_t *exp, unsigned depth, bool in_group);
static tp_chain_t tp_parse_group(tp_expander_t *exp, unsigned depth) {
tp_chain_t result = {0};
size_t open = exp->pos++;
if (depth >= TP_MAX_BRACE_DEPTH) {
exp->valid = false;
return result;
}
tp_expand_node_t *first = NULL, *last = NULL;
tp_expand_node_t *join = tp_expand_node(exp, NULL, 0);
size_t count = 0;
while (exp->valid) {
tp_chain_t branch = tp_parse_sequence(exp, depth + 1, true);
if (!exp->valid)
return result;
if (!branch.head)
tp_chain_literal(exp, &branch, NULL, 0);
if (!exp->valid)
return result;
branch.tail->next = join;
if (last)
last->sibling = branch.head;
else
first = branch.head;
last = branch.head;
count++;
if (exp->pos >= exp->len) {
exp->valid = false;
return result;
}
if (exp->text[exp->pos] == '}') {
exp->pos++;
break;
}
/* parse_sequence stops at either a comma or a closing brace. */
exp->pos++;
}
if (!exp->valid)
return result;
if (count == 1) {
/* A group with no comma preserves its braces, while nested groups
* still expand: {a{b,c}} yields {ab} and {ac}. */
tp_chain_literal(exp, &result, exp->text + open, 1);
if (!exp->valid)
return (tp_chain_t){0};
result.tail->next = first;
result.tail = join;
tp_chain_literal(exp, &result, exp->text + exp->pos - 1, 1);
} else {
tp_expand_node_t *choice = tp_expand_node(exp, NULL, 0);
if (!choice)
return (tp_chain_t){0};
choice->alternatives = first;
result.head = choice;
result.tail = join;
exp->alternative_count += count;
}
return result;
}
static tp_chain_t tp_parse_sequence(tp_expander_t *exp, unsigned depth, bool in_group) {
tp_chain_t result = {0};
size_t literal = exp->pos;
while (exp->pos < exp->len && exp->valid) {
char ch = exp->text[exp->pos];
if (ch == '\\' && exp->pos + 1 < exp->len) {
exp->pos += 2;
continue;
}
if (ch == '[') {
exp->pos = tp_class_end(exp->text, exp->len, exp->pos);
continue;
}
if (ch == '}' || (in_group && ch == ',')) {
if (!in_group)
exp->valid = false;
break;
}
if (ch == '{') {
if (exp->pos > literal)
tp_chain_literal(exp, &result, exp->text + literal, exp->pos - literal);
tp_chain_t group = tp_parse_group(exp, depth);
tp_chain_append(&result, group);
literal = exp->pos;
} else {
exp->pos++;
}
}
if (exp->valid && exp->pos > literal)
tp_chain_literal(exp, &result, exp->text + literal, exp->pos - literal);
return result;
}
static unsigned char tp_class_char(const char *text, size_t end, size_t *pos) {
if (text[*pos] == '\\' && *pos + 1 < end)
(*pos)++;
return (unsigned char)text[(*pos)++];
}
static bool tp_compile_class(cbm_test_policy_t *policy, const char *text, size_t open, size_t end,
tp_token_t *token) {
unsigned char *bits = cbm_arena_calloc(&policy->arena, 32);
if (!bits)
return false;
size_t pos = open + 1, close = end - 1;
bool negate = text[pos] == '!' || text[pos] == '^';
if (negate)
pos++;
while (pos < close) {
unsigned char first = tp_class_char(text, close, &pos);
if (pos + 1 < close && text[pos] == '-') {
pos++;
unsigned char last = tp_class_char(text, close, &pos);
for (unsigned ch = first; ch <= last; ch++)
bits[ch >> 3] |= (unsigned char)(1U << (ch & 7U));
} else {
bits[first >> 3] |= (unsigned char)(1U << (first & 7U));
}
}
if (negate) {
for (int i = 0; i < 32; i++)
bits[i] = (unsigned char)~bits[i];
}
/* A class, even a negated class or an explicit slash range, cannot
* consume a path separator. */
bits[(unsigned)'/' >> 3] &= (unsigned char)~(1U << ((unsigned)'/' & 7U));
token->kind = TP_CLASS;
token->class_bits = bits;
return true;
}
static bool tp_compile_pattern(cbm_test_policy_t *policy, tp_pattern_t *pattern, bool path_mode) {
const char *text = pattern->text;
size_t start = 0, end = pattern->len;
if (path_mode) {
if (text[0] == '/') {
pattern->rooted = true;
start++;
}
size_t escapes = 0;
for (size_t i = end - 1; i && text[i - 1] == '\\'; i--)
escapes++;
if (text[end - 1] == '/' && !(escapes & 1U)) {
pattern->dir_only = true;
end--;
}
if (end <= start) {
pattern->disabled = true;
return true;
}
/* As in gitignore discovery, any interior slash anchors a path
* pattern, even when it appears within a class or is escaped. */
if (memchr(text + start, '/', end - start))
pattern->rooted = true;
}
pattern->tokens = cbm_arena_calloc(&policy->arena, (end - start) * sizeof(tp_token_t));
if (!pattern->tokens)
return false;
for (size_t pos = start; pos < end;) {
tp_token_t *token = &pattern->tokens[pattern->token_count++];
unsigned char ch = (unsigned char)text[pos++];
if (ch == '\\' && pos < end) {
token->kind = TP_LITERAL;
token->literal = (unsigned char)text[pos++];
} else if (ch == '*') {
size_t star_start = pos - 1;
while (pos < end && text[pos] == '*')
pos++;
/* Globstar is special only as an entire path component. An
* embedded run such as a**b is an ordinary star and
* must neither cross nor consume a separator. */
bool globstar = pos - star_start >= 2 &&
(star_start == start || text[star_start - 1] == '/') &&
(pos == end || text[pos] == '/');
if (globstar && pos < end) {
token->kind = TP_DOUBLE_STAR_SLASH;
pattern->rooted = path_mode;
pos++;
} else {
token->kind = globstar ? TP_DOUBLE_STAR : TP_STAR;
}
} else if (ch == '?') {
token->kind = TP_QUESTION;
} else if (ch == '[') {
size_t class_end = tp_class_end(text, end, pos - 1);
if (class_end > pos) {
if (!tp_compile_class(policy, text, pos - 1, class_end, token))
return false;
pos = class_end;
} else {
token->kind = TP_LITERAL;
token->literal = ch;
}
} else {
token->kind = TP_LITERAL;
token->literal = ch;
}
if (path_mode && token->kind == TP_LITERAL && token->literal == '/')
pattern->rooted = true;
}
return true;
}
static bool tp_add_expansion(cbm_test_policy_t *policy, tp_patterns_t *patterns, const char *text,
size_t len, bool semantic_perf) {
if (!tp_pattern_valid(text, len) || policy->expansion_count >= TP_MAX_EXPANSIONS ||
len > TP_MAX_EXPANDED_BYTES - policy->expanded_bytes)
return false;
policy->expansion_count++;
policy->expanded_bytes += len;
if (semantic_perf && len == 5 && memcmp(text, "@perf", 5) == 0) {
patterns->perf = true;
return true;
}
tp_pattern_t *pattern = cbm_arena_calloc(&policy->arena, sizeof(*pattern));
if (!pattern)
return false;
pattern->text = cbm_arena_strndup(&policy->arena, text, len);
if (!pattern->text)
return false;
pattern->len = len;
if (!tp_compile_pattern(policy, pattern, !semantic_perf))
return false;
if (patterns->tail)
patterns->tail->next = pattern;
else
patterns->head = pattern;
patterns->tail = pattern;
return true;
}
typedef struct {
tp_expand_node_t *node;
size_t used;
} tp_expand_frame_t;
static bool tp_expand_pattern(cbm_test_policy_t *policy, tp_patterns_t *patterns, const char *text,
size_t len, bool semantic_perf) {
if (!tp_pattern_valid(text, len))
return false;
tp_expander_t exp = {.text = text, .len = len, .valid = true};
cbm_arena_init_lazy(&exp.arena, 4096);
tp_chain_t chain = tp_parse_sequence(&exp, 0, false);
if (!exp.valid || exp.pos != len)
goto invalid;
size_t capacity = exp.alternative_count + 1;
tp_expand_frame_t *stack = cbm_arena_alloc(&exp.arena, capacity * sizeof(*stack));
char *output = cbm_arena_alloc(&exp.arena, TP_MAX_PATTERN + 1U);
if (!stack || !output)
goto invalid;
size_t pending = 0;
stack[pending++] = (tp_expand_frame_t){chain.head, 0};
while (pending) {
tp_expand_frame_t frame = stack[--pending];
size_t used = frame.used;
tp_expand_node_t *node = frame.node;
bool branched = false;
while (node) {
if (node->alternatives) {
size_t first_pending = pending;
for (tp_expand_node_t *alt = node->alternatives; alt; alt = alt->sibling) {
if (pending >= capacity)
goto invalid;
stack[pending++] = (tp_expand_frame_t){alt, used};
}
/* The LIFO stack visits alternatives in their source order. */
for (size_t left = first_pending, right = pending - 1; left < right;
left++, right--) {
tp_expand_frame_t swap = stack[left];
stack[left] = stack[right];
stack[right] = swap;
}
branched = true;
break;
}
if (node->len > TP_MAX_PATTERN - used)
goto invalid;
if (node->len)
memcpy(output + used, node->text, node->len);
used += node->len;
node = node->next;
}
if (!branched) {
output[used] = '\0';
if (!tp_add_expansion(policy, patterns, output, used, semantic_perf))
goto invalid;
}
}
cbm_arena_destroy(&exp.arena);
return true;
invalid:
cbm_arena_destroy(&exp.arena);
return false;
}
/* Public arrays retain original spellings. Expanded patterns are separate,
* so receipt/reporting clients do not lose the project configuration. */
static bool tp_string_array(cbm_test_policy_t *policy, yyjson_val *value, bool nonempty,
const char *const **result, int *count, tp_patterns_t *patterns,
bool semantic_perf) {
if (!yyjson_is_arr(value))
return false;
size_t size = yyjson_arr_size(value);
if ((nonempty && !size) || size > INT_MAX || size > SIZE_MAX / sizeof(char *))
return false;
const char **items = size ? cbm_arena_alloc(&policy->arena, size * sizeof(*items)) : NULL;
if (size && !items)
return false;
size_t index, maximum;
yyjson_val *item;
yyjson_arr_foreach(value, index, maximum, item) {
size_t len = 0;
const char *text = tp_string(item, &len);
if (!text)
return false;
items[index] = cbm_arena_strndup(&policy->arena, text, len);
if (!items[index] ||
(patterns && !tp_expand_pattern(policy, patterns, text, len, semantic_perf)))
return false;
}
*result = items;
*count = (int)size;
return true;
}
static bool tp_parse_lanes(cbm_test_policy_t *policy, yyjson_val *value) {
if (!yyjson_is_arr(value) || !yyjson_arr_size(value) || yyjson_arr_size(value) > INT_MAX)
return false;
size_t count = yyjson_arr_size(value);
if (count > SIZE_MAX / sizeof(*policy->lanes) ||
count > SIZE_MAX / sizeof(*policy->lane_matchers))
return false;
policy->lanes = cbm_arena_calloc(&policy->arena, count * sizeof(*policy->lanes));
policy->lane_matchers =
cbm_arena_calloc(&policy->arena, count * sizeof(*policy->lane_matchers));
if (!policy->lanes || !policy->lane_matchers)
return false;
policy->lane_count = (int)count;
size_t index, maximum;
yyjson_val *value_lane;
yyjson_arr_foreach(value, index, maximum, value_lane) {
bool valid = true;
yyjson_val *name = tp_field(value_lane, "name", &valid);
yyjson_val *suites = tp_field(value_lane, "suites", &valid);
yyjson_val *excludes = tp_field(value_lane, "exclude_suites", &valid);
yyjson_val *signals = tp_field(value_lane, "signals", &valid);
yyjson_val *default_action = tp_field(value_lane, "default", &valid);
yyjson_val *narrow = tp_field(value_lane, "narrow", &valid);
const char *name_text = tp_string(name, NULL);
const char *default_text = tp_string(default_action, NULL);
if (!valid || !name_text || !default_text ||
(strcmp(default_text, "run") != 0 && strcmp(default_text, "skip") != 0) ||
(narrow && !yyjson_is_bool(narrow)))
return false;
for (size_t earlier = 0; earlier < index; earlier++) {
if (strcmp(policy->lanes[earlier].name, name_text) == 0)
return false;
}
cbm_test_lane_t *lane = &policy->lanes[index];
tp_lane_matchers_t *matchers = &policy->lane_matchers[index];
lane->name = cbm_arena_strdup(&policy->arena, name_text);
lane->default_run = strcmp(default_text, "run") == 0;
lane->narrow = narrow && yyjson_get_bool(narrow);
if (!lane->name ||
!tp_string_array(policy, suites, true, &lane->suites, &lane->suite_count,
&matchers->suites, true) ||
(excludes && !tp_string_array(policy, excludes, false, &lane->exclude_suites,
&lane->exclude_count, &matchers->excludes, true)) ||
(signals && !tp_string_array(policy, signals, false, &lane->signals,
&lane->signal_count, NULL, false)))
return false;
}
return true;
}
static bool tp_key_segment(yyjson_val *value, int *segment) {
const char *text = tp_string(value, NULL);
static const char prefix[] = "path_segment:";
if (!text || strncmp(text, prefix, sizeof(prefix) - 1) != 0)
return false;
text += sizeof(prefix) - 1;
if (!*text)
return false;
unsigned result = 0;
for (; *text; text++) {
if (*text < '0' || *text > '9')
return false;
unsigned digit = (unsigned)(*text - '0');
if (result > ((unsigned)INT_MAX - digit) / 10U)
return false;
result = result * 10U + digit;
}
*segment = (int)result;
return true;
}
/* `unreferenced` of a referencing_tests rule: absent or "run_all" keeps the
* fail-safe default (a path no test names runs everything); "ignore" lets it
* select nothing — for data no test can depend on without naming it. */
static bool tp_unreferenced(yyjson_val *value, bool *ignore) {
*ignore = false;
if (!value)
return true;
const char *text = tp_string(value, NULL);
if (!text)
return false;
if (strcmp(text, "ignore") == 0) {
*ignore = true;
return true;
}
return strcmp(text, "run_all") == 0;
}
static const char *const tp_build_paths[] = {
"Makefile*", "CMakeLists.txt", "*.cmake", "meson.build", "BUILD*",
"WORKSPACE", "package*.json", "go.mod", "go.sum", "Cargo.*",
"pom.xml", "build.gradle*", "pyproject.toml", "setup.*", "requirements*.txt"};
static const char *const tp_ci_paths[] = {".github/**", ".gitlab-ci.yml", ".circleci/**",
"Jenkinsfile*", ".buildkite/**", "azure-pipelines*.yml"};
static const char *const tp_vendor_paths[] = {"vendor*/**", "third_party/**"};
static const char *const tp_conftest_paths[] = {"conftest.py"};
/* The selection's own configuration: a change to it may loosen what it
* selects, so it runs everything (smart-ci-design review M-4). */
static const char *const tp_config_paths[] = {".codebase-memory.json"};
static const char *const tp_documentation_paths[] = {"docs/**", "**/*.md", "LICENSE*"};
typedef struct {
const char *id;
cbm_test_rule_action_t action;
const char *const *paths;
size_t path_count;
} tp_builtin_t;
#define TP_COUNT(array) (sizeof(array) / sizeof((array)[0]))
static const tp_builtin_t tp_builtins[] = {
{"builtin:test-impact-config", CBM_TEST_RULE_RUN_ALL, tp_config_paths,
TP_COUNT(tp_config_paths)},
{"builtin:build", CBM_TEST_RULE_RUN_ALL, tp_build_paths, TP_COUNT(tp_build_paths)},
{"builtin:ci", CBM_TEST_RULE_RUN_ALL, tp_ci_paths, TP_COUNT(tp_ci_paths)},
{"builtin:vendor", CBM_TEST_RULE_RUN_ALL, tp_vendor_paths, TP_COUNT(tp_vendor_paths)},
{"builtin:conftest", CBM_TEST_RULE_RUN_ALL, tp_conftest_paths, TP_COUNT(tp_conftest_paths)},
{"builtin:documentation", CBM_TEST_RULE_IGNORE, tp_documentation_paths,
TP_COUNT(tp_documentation_paths)}};
static bool tp_parse_rule(cbm_test_policy_t *policy, yyjson_val *value, int index) {
bool valid = true;
yyjson_val *id = tp_field(value, "id", &valid);
yyjson_val *paths = tp_field(value, "paths", &valid);
yyjson_val *action = tp_field(value, "action", &valid);
yyjson_val *lanes = tp_field(value, "lanes", &valid);
yyjson_val *suites = tp_field(value, "suites", &valid);
yyjson_val *key = tp_field(value, "key", &valid);
yyjson_val *unreferenced = tp_field(value, "unreferenced", &valid);
const char *id_text = tp_string(id, NULL), *action_text = tp_string(action, NULL);
if (!valid || !id_text || !action_text)
return false;
for (int earlier = 0; earlier < index; earlier++) {
if (strcmp(policy->rules[earlier].id, id_text) == 0)
return false;
}
for (size_t builtin = 0; builtin < TP_COUNT(tp_builtins); builtin++) {
if (strcmp(tp_builtins[builtin].id, id_text) == 0)
return false;
}
cbm_test_rule_t *rule = &policy->rules[index];
tp_rule_matchers_t *matchers = &policy->rule_matchers[index];
rule->key_segment = -1;
rule->id = cbm_arena_strdup(&policy->arena, id_text);
if (!rule->id || !tp_string_array(policy, paths, true, &rule->paths, &rule->path_count,
&matchers->paths, false))
return false;
if (strcmp(action_text, "run_all") == 0) {
rule->action = CBM_TEST_RULE_RUN_ALL;
return !lanes && !suites && !key && !unreferenced;
}
if (strcmp(action_text, "ignore") == 0) {
rule->action = CBM_TEST_RULE_IGNORE;
return !lanes && !suites && !key && !unreferenced;
}
if (strcmp(action_text, "lanes") == 0) {
rule->action = CBM_TEST_RULE_LANES;
return !suites && !key && !unreferenced &&
tp_string_array(policy, lanes, true, &rule->lanes, &rule->lane_count, NULL, false);
}
if (strcmp(action_text, "suites") == 0) {
rule->action = CBM_TEST_RULE_SUITES;
return !lanes && !key && !unreferenced &&
tp_string_array(policy, suites, true, &rule->suites, &rule->suite_count,
&matchers->suites, true);
}
if (strcmp(action_text, "referencing_tests") == 0) {
rule->action = CBM_TEST_RULE_REFERENCING_TESTS;
if (lanes || suites || !tp_unreferenced(unreferenced, &rule->unreferenced_ignore))
return false;
const char *key_text = tp_string(key, NULL);
if (key_text && strcmp(key_text, "path") == 0) {
rule->key_path = true;
return true;
}
return tp_key_segment(key, &rule->key_segment);
}
return false;
}
static bool tp_copy_patterns(cbm_test_policy_t *policy, const char *const *source, size_t count,
const char *const **result, tp_patterns_t *patterns,
bool semantic_perf) {
const char **items = cbm_arena_alloc(&policy->arena, count * sizeof(*items));
if (!items)
return false;
for (size_t i = 0; i < count; i++) {
items[i] = cbm_arena_strdup(&policy->arena, source[i]);
if (!items[i] ||
!tp_expand_pattern(policy, patterns, source[i], strlen(source[i]), semantic_perf))
return false;
}
*result = items;
return true;
}
static bool tp_default_lane(cbm_test_policy_t *policy) {
static const char *const suites[] = {"*"};
static const char *const excludes[] = {"@perf"};
policy->lanes = cbm_arena_calloc(&policy->arena, sizeof(*policy->lanes));
policy->lane_matchers = cbm_arena_calloc(&policy->arena, sizeof(*policy->lane_matchers));
if (!policy->lanes || !policy->lane_matchers)
return false;
policy->lane_count = 1;
cbm_test_lane_t *lane = policy->lanes;
lane->name = cbm_arena_strdup(&policy->arena, "unit");
lane->suite_count = 1;
lane->exclude_count = 1;
lane->default_run = true;
lane->narrow = true;
return lane->name &&
tp_copy_patterns(policy, suites, 1, &lane->suites, &policy->lane_matchers->suites,
true) &&
tp_copy_patterns(policy, excludes, 1, &lane->exclude_suites,
&policy->lane_matchers->excludes, true);
}
static bool tp_add_builtins(cbm_test_policy_t *policy, int first) {
for (size_t i = 0; i < TP_COUNT(tp_builtins); i++) {
const tp_builtin_t *source = &tp_builtins[i];
cbm_test_rule_t *rule = &policy->rules[first + (int)i];
rule->id = cbm_arena_strdup(&policy->arena, source->id);
rule->action = source->action;
rule->builtin = true;
rule->key_segment = -1;
rule->path_count = (int)source->path_count;
if (!rule->id || !tp_copy_patterns(policy, source->paths, source->path_count, &rule->paths,
&policy->rule_matchers[first + (int)i].paths, false))
return false;
}
return true;
}
/* A repository-relative file path: no root, no backslash, no empty, `.` or
* `..` segment, no trailing slash. */
static bool tp_relative_path(const char *text, size_t len) {
if (!text || !len || len > TP_MAX_COMPAT_PATH || text[0] == '/' || text[len - 1] == '/' ||
memchr(text, '\\', len))
return false;
const char *segment = text;
const char *end = text + len;
while (segment < end) {
const char *slash = memchr(segment, '/', (size_t)(end - segment));
size_t n = (size_t)((slash ? slash : end) - segment);
if (!n || (n == 1 && segment[0] == '.') ||
(n == 2 && segment[0] == '.' && segment[1] == '.'))
return false;
segment += n + 1;
}
return true;
}
/* `coverage`: what a recorded coverage map depends on beyond the code it
* measures. Strict on keys: an ignored misspelling would make admitting a map
* easier, never harder. */
static bool tp_parse_coverage(cbm_test_policy_t *policy, yyjson_val *coverage) {
bool valid = true;
yyjson_val *paths = tp_field(coverage, "compatibility_paths", &valid);
if (!valid || yyjson_obj_size(coverage) != (paths ? 1U : 0U) ||
(paths && !yyjson_is_arr(paths)))
return false;
size_t count = paths ? yyjson_arr_size(paths) : 0;
if (count > TP_MAX_COMPAT_PATHS)
return false;
policy->compat_paths =
cbm_arena_calloc(&policy->arena, (count ? count : 1) * sizeof(*policy->compat_paths));
if (!policy->compat_paths)
return false;
size_t index, maximum;
yyjson_val *path;
yyjson_arr_foreach(paths, index, maximum, path) {
size_t len = 0;
const char *text = tp_string(path, &len);
if (!tp_relative_path(text, len))
return false;
policy->compat_paths[index] = cbm_arena_strdup(&policy->arena, text);
if (!policy->compat_paths[index])
return false;
}
policy->compat_count = (int)count;
return true;
}
static bool tp_parse_policy(cbm_test_policy_t *policy, yyjson_val *impact) {
bool valid = true;
yyjson_val *rules = NULL, *lanes = NULL;
if (impact) {
yyjson_val *version = tp_field(impact, "version", &valid);
rules = tp_field(impact, "rules", &valid);
lanes = tp_field(impact, "lanes", &valid);
yyjson_val *unmapped = tp_field(impact, "unmapped_files", &valid);
yyjson_val *coverage = tp_field(impact, "coverage", &valid);
if (!valid || !yyjson_is_uint(version) || yyjson_get_uint(version) != 1)
return false;
if (coverage && !tp_parse_coverage(policy, coverage))
return false;
if (unmapped) {
const char *text = tp_string(unmapped, NULL);
if (!text || strcmp(text, "run_all") != 0)
return false;
}
}
if (lanes ? !tp_parse_lanes(policy, lanes) : !tp_default_lane(policy))
return false;
size_t project_count = rules ? yyjson_arr_size(rules) : 0;
if ((rules && !yyjson_is_arr(rules)) || project_count > INT_MAX - TP_COUNT(tp_builtins))
return false;
size_t count = project_count + TP_COUNT(tp_builtins);
if (count > SIZE_MAX / sizeof(*policy->rules) ||
count > SIZE_MAX / sizeof(*policy->rule_matchers))
return false;
policy->rules = cbm_arena_calloc(&policy->arena, count * sizeof(*policy->rules));
policy->rule_matchers =
cbm_arena_calloc(&policy->arena, count * sizeof(*policy->rule_matchers));
if (!policy->rules || !policy->rule_matchers)
return false;
policy->rule_count = (int)count;
size_t index, maximum;
yyjson_val *rule_value;
yyjson_arr_foreach(rules, index, maximum, rule_value) {
if (!tp_parse_rule(policy, rule_value, (int)index))
return false;
}
if (!tp_add_builtins(policy, (int)project_count))
return false;
for (size_t i = 0; i < project_count; i++) {
const cbm_test_rule_t *rule = &policy->rules[i];
for (int reference = 0; reference < rule->lane_count; reference++) {
bool found = false;
for (int lane = 0; lane < policy->lane_count; lane++) {
if (strcmp(rule->lanes[reference], policy->lanes[lane].name) == 0) {
found = true;
break;
}
}
if (!found)
return false;
}
}
return true;
}
cbm_test_policy_t *cbm_test_policy_new(const cbm_test_config_t *config) {
if (!config)
return NULL;
size_t len = 0;
bool absent = false;
const char *source = cbm_test_config_source(config, &len, &absent);
if ((!absent && (!source || !len)) || len > TP_MAX_PATTERN ||
(len && (!source || memchr(source, '\0', len))))
return NULL;
CBMArena arena;
cbm_arena_init_lazy(&arena, 4096);
cbm_test_policy_t *policy = cbm_arena_calloc(&arena, sizeof(*policy));
if (!policy) {
cbm_arena_destroy(&arena);
return NULL;
}
policy->arena = arena;
policy->digest = cbm_arena_strdup(&policy->arena, cbm_test_config_digest(config));
if (!policy->digest)
goto invalid;
yyjson_doc *doc = absent ? NULL : yyjson_read(source, len, 0);
if (!absent && !doc)
goto invalid;
bool valid = true;
yyjson_val *impact = doc ? tp_field(yyjson_doc_get_root(doc), "test_impact", &valid) : NULL;
valid = valid && tp_parse_policy(policy, impact);
yyjson_doc_free(doc);
if (valid)
return policy;
invalid:
cbm_test_policy_free(policy);
return NULL;
}
void cbm_test_policy_free(cbm_test_policy_t *policy) {
if (!policy)
return;
CBMArena arena = policy->arena;
cbm_arena_destroy(&arena);
}
const cbm_test_rule_t *cbm_test_policy_rules(const cbm_test_policy_t *policy, int *count) {
if (count)
*count = policy ? policy->rule_count : 0;
return policy ? policy->rules : NULL;
}
const cbm_test_lane_t *cbm_test_policy_lanes(const cbm_test_policy_t *policy, int *count) {
if (count)
*count = policy ? policy->lane_count : 0;
return policy ? policy->lanes : NULL;
}
const char *cbm_test_policy_digest(const cbm_test_policy_t *policy) {
return policy ? policy->digest : "";
}
const char *const *cbm_test_policy_compatibility_paths(const cbm_test_policy_t *policy,
int *count) {
if (count)
*count = policy ? policy->compat_count : 0;
return policy && policy->compat_count ? (const char *const *)policy->compat_paths : NULL;
}
typedef struct {
CBMArena arena;
unsigned char *first;
unsigned char *second;
size_t budget;
} tp_match_context_t;
static bool tp_match_length(const char *text, size_t *len) {
if (!text || !*text)
return false;
for (size_t i = 0; i <= TP_MAX_MATCH_BYTES; i++) {
if (!text[i]) {
*len = i;
return true;
}
}
return false;
}
static bool tp_match_begin(tp_match_context_t *context, size_t len) {
memset(context, 0, sizeof(*context));
cbm_arena_init_lazy(&context->arena, 4096);
context->budget = TP_MATCH_MAX_WORK;
context->first = cbm_arena_alloc(&context->arena, len + 1);
context->second = cbm_arena_alloc(&context->arena, len + 1);
if (!context->first || !context->second) {
cbm_arena_destroy(&context->arena);
return false;
}
return true;
}
/* Unlike the discovery matcher's best-effort API, this evaluator must never
* turn resource exhaustion into permission to omit a test. Two suffix rows
* evaluate each (token, input byte) once, with an explicit per-operation
* budget shared by every rule and directory ancestor. Suffix/ancestor scans
* also consume one unit per byte. It uses no recursion.
* False is an error; *matched is only meaningful when true is returned. */
static bool tp_glob_matches(tp_match_context_t *context, const tp_pattern_t *pattern,
const char *text, size_t len, bool direct, bool *matched) {
*matched = false;
if (pattern->disabled)
return true;
unsigned char *next = context->first, *current = context->second;
if (context->budget < len + 1)
return false;
context->budget -= len + 1;
memset(next, 0, len + 1);
next[len] = 1;
for (size_t token_index = pattern->token_count; token_index > 0; token_index--) {
const tp_token_t *token = &pattern->tokens[token_index - 1];
if (context->budget < len + 1)
return false;
context->budget -= len + 1;
bool slash_suffix = false;
for (size_t remaining = len + 1; remaining > 0; remaining--) {
size_t pos = remaining - 1;
bool has_char = pos < len;
unsigned char ch = has_char ? (unsigned char)text[pos] : 0;
switch (token->kind) {
case TP_LITERAL:
current[pos] = has_char && ch == token->literal && next[pos + 1];
break;
case TP_QUESTION:
current[pos] = has_char && ch != '/' && next[pos + 1];
break;
case TP_STAR:
current[pos] = next[pos] || (has_char && ch != '/' && current[pos + 1]);
break;
case TP_DOUBLE_STAR:
current[pos] = next[pos] || (has_char && current[pos + 1]);
break;
case TP_DOUBLE_STAR_SLASH:
if (has_char && ch == '/' && next[pos + 1])
slash_suffix = true;
current[pos] = next[pos] || slash_suffix;
break;
case TP_CLASS:
current[pos] =
has_char && (token->class_bits[ch >> 3] & (1U << (ch & 7U))) && next[pos + 1];
break;
}
}
unsigned char *swap = next;
next = current;
current = swap;
}
if (next[0]) {
*matched = true;
return true;
}
if (!direct && !pattern->rooted) {
for (size_t pos = 0; pos < len; pos++) {
if (!context->budget)
return false;
context->budget--;
if (text[pos] == '/' && next[pos + 1]) {
*matched = true;
break;
}
}
}
return true;
}
static bool tp_path_patterns_match(tp_match_context_t *context, const tp_patterns_t *patterns,
const char *path, size_t len, bool *matched) {
*matched = false;
for (const tp_pattern_t *pattern = patterns->head; pattern; pattern = pattern->next) {
if (!pattern->dir_only) {
if (!tp_glob_matches(context, pattern, path, len, false, matched))
return false;
if (*matched)
return true;
}
/* Discovery evaluates each ancestor as a directory before reaching
* its files. Prefix lengths give the same semantics without a copy
* or allocation whose failure might be mistaken for a non-match. */
for (size_t end = 1; end < len; end++) {
if (!context->budget)
return false;
context->budget--;
if (path[end] == '/') {
if (!tp_glob_matches(context, pattern, path, end, false, matched))
return false;
if (*matched)
return true;
}
}
}
return true;
}
static bool tp_suite_patterns_match(tp_match_context_t *context, const tp_patterns_t *patterns,
const char *suite, size_t len, bool perf, bool *matched) {
*matched = patterns->perf && perf;
if (*matched)
return true;
for (const tp_pattern_t *pattern = patterns->head; pattern; pattern = pattern->next) {
if (!tp_glob_matches(context, pattern, suite, len, true, matched))
return false;
if (*matched)
return true;
}
return true;
}
bool cbm_test_policy_match_path(const cbm_test_policy_t *policy, const char *path,
const cbm_test_rule_t **rule) {
if (rule)
*rule = NULL;
size_t len = 0;
if (!policy || !rule || !tp_match_length(path, &len))
return false;
tp_match_context_t context;
if (!tp_match_begin(&context, len))
return false;
bool valid = true;
for (int i = 0; i < policy->rule_count; i++) {
bool matched = false;
if (!tp_path_patterns_match(&context, &policy->rule_matchers[i].paths, path, len,
&matched)) {
valid = false;
break;
}
if (matched) {
*rule = &policy->rules[i];
break;
}
}
cbm_arena_destroy(&context.arena);
return valid;
}
bool cbm_test_policy_lane_selects_suite(const cbm_test_policy_t *policy, int lane,
const char *suite, bool perf, bool *selected) {
if (selected)
*selected = false;
size_t len = 0;
if (!policy || !selected || lane < 0 || lane >= policy->lane_count ||
!tp_match_length(suite, &len))
return false;
tp_match_context_t context;
if (!tp_match_begin(&context, len))
return false;
const tp_lane_matchers_t *matchers = &policy->lane_matchers[lane];
bool included = false, excluded = false;
bool valid = tp_suite_patterns_match(&context, &matchers->suites, suite, len, perf, &included);
if (valid && included)
valid = tp_suite_patterns_match(&context, &matchers->excludes, suite, len, perf, &excluded);
if (valid)
*selected = included && !excluded;
cbm_arena_destroy(&context.arena);
return valid;
}
bool cbm_test_policy_rule_selects_suite(const cbm_test_policy_t *policy, int rule,
const char *suite, bool perf, bool *selected) {
if (selected)
*selected = false;
size_t len = 0;
if (!policy || !selected || rule < 0 || rule >= policy->rule_count ||
policy->rules[rule].action != CBM_TEST_RULE_SUITES || !tp_match_length(suite, &len))
return false;
tp_match_context_t context;
if (!tp_match_begin(&context, len))
return false;
bool matched = false;
bool valid = tp_suite_patterns_match(&context, &policy->rule_matchers[rule].suites, suite, len,
perf, &matched);
if (valid)
*selected = matched;
cbm_arena_destroy(&context.arena);
return valid;
}