nprasad2077/codebase-memory-mcp
1
0 Fork 0
mirror of https://github.com/DeusData/codebase-memory-mcp.git synced 2026-11-04 10:48:20 +00:00
Code Issues Packages Projects Releases Wiki Activity
Files
codex/codeql-main-alerts
codebase-memory-mcp/tests/test_store_impact.c
T
Martin Vogel 7aa384b401 fix(graph): platform variants keep their path QNs and are related by variant_key 
42a93202 gave a non-static C-family function under a platform directory
(arch/x86/, src/win/, ...) or file suffix a platform-neutral QN, so the
platform variants of one function shared a node. On the Linux kernel that
merged only 644 of 17,413 such definitions; the other 16,769 lost their
path for nothing (`arch/arm64/mm/init.c` mem_init became
`arch.mm.init.mem_init`, and a lookup by its path QN found nothing),
arches missing from the token list kept their paths, and calls bound to
merged nodes produced impossible arch -> other-arch CALLS.

Every definition keeps its path-derived QN again (the v0.11.0 identity).
The platform-neutral QN is now a key: definitions carrying one get a
`variant_key` node property, and nodes of a project sharing a key are one
variant group. The test-impact walk (store_impact `follow_variant_keys`,
enabled by the test-impact engine) treats a reached variant as reaching its
whole group, at seeding and at every step, so a change confined to the
Windows variant still selects the tests that reach the POSIX variant's
callers. The key is a pure function of a definition's own path, name and
linkage: incremental re-parsing of the changed file writes what a full
index writes. Same-QN variants (#if/#else, Rust cfg, Go build tags,
.c/.h pairs) and their `variants` property are unchanged. No new edge type.

Proof (macOS arm64):
- Linux kernel subset (arch, include, kernel, mm, lib; 27,005 files):
  arch functions whose QN is not under their own path 12,873 -> 0;
  arch/A -> arch/B CALLS 10,353 -> 7,101; 581 variant groups (1,815
  members), each one of the former cross-file merges; the path QN of
  arch/arm64's mem_init resolves.
- This repository: 13 groups (test_impact_tree_{posix,windows},
  mem_override_{posix,win}); before, 22 of 49 platform-path functions had a
  stripped QN.
- New/rewritten tests (RED on the old tree or without the walk
  expansion): conditional_variants cv_c_platform_files,
  cv_c_platform_directories, cv_incremental_platform_files;
  test_impact_engine
  test_impact_engine_platform_variants_reach_each_others_callers;
  store_impact impact_walk_crosses_platform_variants_only_when_asked;
  cv_incremental_variant_partners re-fixtured to Go build tags.
- 18 affected suites: 2710 passed, 4 Windows-only skips.

Signed-off-by: Martin Vogel <martin.vogel.tech@gmail.com>
2026-10-13 18:33:40 +02:00

422 lines
17 KiB
C
Raw Permalink Blame History

/*
* test_store_impact.c — the fixpoint impact walk (src/store/store_impact.c).
*
* The walk answers "what depends on these nodes" for test selection, so its
* result must be a pure function of the graph and the request: complete (no
* depth bound, cycles included), and identical whatever order rows, node ids
* or seeds happen to arrive in.
*/
#include "test_framework.h"
#include <store/store.h>
#include <store/store_impact.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static int64_t add_node(cbm_store_t *s, const char *label, const char *name) {
char qn[64];
snprintf(qn, sizeof(qn), "test.%s", name);
cbm_node_t node = {.project = "test", .label = label, .name = name, .qualified_name = qn};
return cbm_store_upsert_node(s, &node);
}
/* `from` depends on `to`: the edge the walk follows backwards. */
static void add_edge(cbm_store_t *s, int64_t from, int64_t to, const char *type) {
cbm_edge_t e = {.project = "test", .source_id = from, .target_id = to, .type = type};
(void)cbm_store_insert_edge(s, &e);
}
static cbm_store_t *new_store(void) {
cbm_store_t *s = cbm_store_open_memory();
if (s) {
cbm_store_upsert_project(s, "test", "/tmp/test");
}
return s;
}
static const char *const CALLS_ONLY[] = {"CALLS"};
static const char *const CALLS_USAGE[] = {"CALLS", "USAGE"};
static cbm_impact_walk_t *open_walk(cbm_store_t *s, const char *const *types, int count,
bool routes) {
cbm_impact_policy_t policy = {
.project = "test", .edge_types = types, .edge_type_count = count, .follow_routes = routes};
cbm_impact_walk_t *w = NULL;
return cbm_impact_walk_open(s, &policy, &w) == CBM_STORE_OK ? w : NULL;
}
static const cbm_impact_hit_t *hit_of(const cbm_impact_walk_t *w, int64_t id) {
const cbm_impact_hit_t *hits = cbm_impact_walk_hits(w);
for (int i = 0; i < cbm_impact_walk_count(w); i++) {
if (hits[i].id == id) {
return &hits[i];
}
}
return NULL;
}
TEST(impact_walk_follows_a_chain_to_its_end) {
/* n30 calls n29 calls ... calls n0. No depth bound: a change to n0 reaches
* all thirty, each at its own hop. */
enum { LEN = 31 };
cbm_store_t *s = new_store();
ASSERT_NOT_NULL(s);
int64_t ids[LEN];
for (int i = 0; i < LEN; i++) {
char name[16];
snprintf(name, sizeof(name), "n%02d", i);
ids[i] = add_node(s, "Function", name);
}
for (int i = 1; i < LEN; i++) {
add_edge(s, ids[i], ids[i - 1], "CALLS");
}
cbm_impact_walk_t *w = open_walk(s, CALLS_ONLY, 1, false);
ASSERT_NOT_NULL(w);
ASSERT_EQ(cbm_impact_walk_run(w, &ids[0], 1), CBM_STORE_OK);
ASSERT_EQ(cbm_impact_walk_count(w), LEN);
for (int i = 0; i < LEN; i++) {
const cbm_impact_hit_t *h = hit_of(w, ids[i]);
ASSERT_NOT_NULL(h);
ASSERT_EQ(h->hop, i);
ASSERT_EQ(h->via_id, i == 0 ? 0 : ids[i - 1]);
}
ASSERT_NULL(hit_of(w, ids[0])->via_edge);
ASSERT_STR_EQ(hit_of(w, ids[1])->via_edge, "CALLS");
ASSERT_TRUE(cbm_impact_walk_hit(w, ids[7]) == hit_of(w, ids[7]));
cbm_impact_walk_close(w);
/* A hop limit keeps the same answer, cut at that distance. */
cbm_impact_policy_t bounded = {
.project = "test", .edge_types = CALLS_ONLY, .edge_type_count = 1, .max_hops = 3};
ASSERT_EQ(cbm_impact_walk_open(s, &bounded, &w), CBM_STORE_OK);
ASSERT_EQ(cbm_impact_walk_run(w, &ids[0], 1), CBM_STORE_OK);
ASSERT_EQ(cbm_impact_walk_count(w), 4);
ASSERT_EQ(cbm_impact_walk_hit(w, ids[3])->hop, 3);
ASSERT_NULL(cbm_impact_walk_hit(w, ids[4]));
cbm_impact_walk_close(w);
cbm_store_close(s);
PASS();
}
TEST(impact_walk_terminates_on_a_cycle) {
/* a -> b -> c -> a, and a self-loop on b. Every node is reached once. */
cbm_store_t *s = new_store();
int64_t a = add_node(s, "Function", "a");
int64_t b = add_node(s, "Function", "b");
int64_t c = add_node(s, "Function", "c");
add_edge(s, a, b, "CALLS");
add_edge(s, b, c, "CALLS");
add_edge(s, c, a, "CALLS");
add_edge(s, b, b, "CALLS");
cbm_impact_walk_t *w = open_walk(s, CALLS_ONLY, 1, false);
ASSERT_NOT_NULL(w);
ASSERT_EQ(cbm_impact_walk_run(w, &a, 1), CBM_STORE_OK);
ASSERT_EQ(cbm_impact_walk_count(w), 3);
ASSERT_EQ(hit_of(w, a)->hop, 0);
ASSERT_EQ(hit_of(w, c)->hop, 1); /* c calls a */
ASSERT_EQ(hit_of(w, b)->hop, 2); /* b calls c */
cbm_impact_walk_close(w);
cbm_store_close(s);
PASS();
}
/* seed <- {parent_a, parent_b} <- x. Which parent x is reached THROUGH must not
* depend on the order nodes or edges were inserted in. */
static int64_t build_diamond(cbm_store_t *s, bool reversed, int64_t *seed, int64_t *parent_a,
int64_t *parent_b) {
int64_t x;
if (reversed) {
x = add_node(s, "Function", "x");
*parent_b = add_node(s, "Function", "parent_b");
*parent_a = add_node(s, "Function", "parent_a");
*seed = add_node(s, "Function", "seed");
add_edge(s, x, *parent_b, "CALLS");
add_edge(s, x, *parent_a, "CALLS");
add_edge(s, *parent_b, *seed, "CALLS");
add_edge(s, *parent_a, *seed, "CALLS");
} else {
*seed = add_node(s, "Function", "seed");
*parent_a = add_node(s, "Function", "parent_a");
*parent_b = add_node(s, "Function", "parent_b");
x = add_node(s, "Function", "x");
add_edge(s, *parent_a, *seed, "CALLS");
add_edge(s, *parent_b, *seed, "CALLS");
add_edge(s, x, *parent_a, "CALLS");
add_edge(s, x, *parent_b, "CALLS");
}
return x;
}
TEST(impact_walk_via_parent_is_the_smallest_qualified_name) {
for (int reversed = 0; reversed < 2; reversed++) {
cbm_store_t *s = new_store();
int64_t seed;
int64_t parent_a;
int64_t parent_b;
int64_t x = build_diamond(s, reversed != 0, &seed, &parent_a, &parent_b);
cbm_impact_walk_t *w = open_walk(s, CALLS_ONLY, 1, false);
ASSERT_NOT_NULL(w);
ASSERT_EQ(cbm_impact_walk_run(w, &seed, 1), CBM_STORE_OK);
ASSERT_EQ(cbm_impact_walk_count(w), 4);
ASSERT_EQ(hit_of(w, x)->hop, 2);
ASSERT_EQ(hit_of(w, x)->via_id, parent_a);
/* Canonical order: by hop, then by qualified name. */
const cbm_impact_hit_t *hits = cbm_impact_walk_hits(w);
ASSERT_EQ(hits[0].id, seed);
ASSERT_EQ(hits[1].id, parent_a);
ASSERT_EQ(hits[2].id, parent_b);
ASSERT_EQ(hits[3].id, x);
ASSERT_STR_EQ(hits[1].qualified_name, "test.parent_a");
cbm_impact_walk_close(w);
cbm_store_close(s);
}
PASS();
}
TEST(impact_walk_via_edge_rank_beats_the_name) {
/* x reaches the change through `zeta` by CALLS and through `alpha` by
* USAGE. The request ranks CALLS first, so the path shown is the call,
* although `alpha` sorts first. */
cbm_store_t *s = new_store();
int64_t seed = add_node(s, "Function", "seed");
int64_t alpha = add_node(s, "Function", "alpha");
int64_t zeta = add_node(s, "Function", "zeta");
int64_t x = add_node(s, "Function", "x");
add_edge(s, alpha, seed, "CALLS");
add_edge(s, zeta, seed, "CALLS");
add_edge(s, x, alpha, "USAGE");
add_edge(s, x, zeta, "CALLS");
cbm_impact_walk_t *w = open_walk(s, CALLS_USAGE, 2, false);
ASSERT_NOT_NULL(w);
ASSERT_EQ(cbm_impact_walk_run(w, &seed, 1), CBM_STORE_OK);
ASSERT_EQ(hit_of(w, x)->via_id, zeta);
ASSERT_STR_EQ(hit_of(w, x)->via_edge, "CALLS");
cbm_impact_walk_close(w);
/* Ranked the other way round, the same graph shows the usage. */
static const char *const usage_first[] = {"USAGE", "CALLS"};
w = open_walk(s, usage_first, 2, false);
ASSERT_NOT_NULL(w);
ASSERT_EQ(cbm_impact_walk_run(w, &seed, 1), CBM_STORE_OK);
ASSERT_EQ(hit_of(w, x)->via_id, alpha);
ASSERT_STR_EQ(hit_of(w, x)->via_edge, "USAGE");
cbm_impact_walk_close(w);
cbm_store_close(s);
PASS();
}
TEST(impact_walk_follows_only_the_requested_edge_types) {
cbm_store_t *s = new_store();
int64_t seed = add_node(s, "Function", "seed");
int64_t caller = add_node(s, "Function", "caller");
int64_t reader = add_node(s, "Function", "reader");
int64_t importer = add_node(s, "Module", "importer");
add_edge(s, caller, seed, "CALLS");
add_edge(s, reader, seed, "USAGE");
add_edge(s, importer, seed, "IMPORTS");
cbm_impact_walk_t *w = open_walk(s, CALLS_ONLY, 1, false);
ASSERT_EQ(cbm_impact_walk_run(w, &seed, 1), CBM_STORE_OK);
ASSERT_EQ(cbm_impact_walk_count(w), 2);
ASSERT_NOT_NULL(hit_of(w, caller));
ASSERT_NULL(hit_of(w, reader));
cbm_impact_walk_close(w);
w = open_walk(s, CALLS_USAGE, 2, false);
ASSERT_EQ(cbm_impact_walk_run(w, &seed, 1), CBM_STORE_OK);
ASSERT_EQ(cbm_impact_walk_count(w), 3);
ASSERT_NOT_NULL(hit_of(w, reader));
ASSERT_NULL(hit_of(w, importer));
ASSERT_TRUE(cbm_impact_walk_reached(w, reader));
ASSERT_FALSE(cbm_impact_walk_reached(w, importer));
cbm_impact_walk_close(w);
cbm_store_close(s);
PASS();
}
TEST(impact_walk_reaches_a_sink_and_stops_there) {
/* test_case calls seed, runner calls test_case. A test case is a sink: it
* is selected, and what calls it is not "impacted by the change". */
cbm_store_t *s = new_store();
int64_t seed = add_node(s, "Function", "seed");
int64_t test_case = add_node(s, "Function", "test_case");
int64_t runner = add_node(s, "Function", "runner");
int64_t helper = add_node(s, "Function", "helper");
int64_t other = add_node(s, "Function", "other");
add_edge(s, test_case, seed, "CALLS");
add_edge(s, runner, test_case, "CALLS");
add_edge(s, helper, seed, "CALLS");
add_edge(s, other, helper, "CALLS");
cbm_impact_walk_t *w = open_walk(s, CALLS_ONLY, 1, false);
ASSERT_EQ(cbm_impact_walk_add_sinks(w, &test_case, 1), CBM_STORE_OK);
ASSERT_EQ(cbm_impact_walk_run(w, &seed, 1), CBM_STORE_OK);
ASSERT_NOT_NULL(hit_of(w, test_case));
ASSERT_NULL(hit_of(w, runner));
ASSERT_NOT_NULL(hit_of(w, other));
ASSERT_EQ(cbm_impact_walk_count(w), 4);
cbm_impact_walk_close(w);
/* A sink that is itself the change is not expanded either. */
w = open_walk(s, CALLS_ONLY, 1, false);
ASSERT_EQ(cbm_impact_walk_add_sinks(w, &test_case, 1), CBM_STORE_OK);
ASSERT_EQ(cbm_impact_walk_run(w, &test_case, 1), CBM_STORE_OK);
ASSERT_EQ(cbm_impact_walk_count(w), 1);
cbm_impact_walk_close(w);
cbm_store_close(s);
PASS();
}
TEST(impact_walk_second_run_continues_from_the_first) {
/* A lift adds seeds after the first fixpoint: they enter one hop beyond
* everything reached so far, and what was reached keeps its place. */
cbm_store_t *s = new_store();
int64_t seed = add_node(s, "Function", "seed");
int64_t caller = add_node(s, "Function", "caller");
int64_t spawner = add_node(s, "Function", "spawner");
int64_t spawn_user = add_node(s, "Function", "spawn_user");
add_edge(s, caller, seed, "CALLS");
add_edge(s, spawn_user, spawner, "CALLS");
add_edge(s, spawn_user, caller, "CALLS");
cbm_impact_walk_t *w = open_walk(s, CALLS_ONLY, 1, false);
ASSERT_EQ(cbm_impact_walk_run(w, &seed, 1), CBM_STORE_OK);
ASSERT_EQ(cbm_impact_walk_count(w), 3);
ASSERT_EQ(hit_of(w, spawn_user)->hop, 2);
int64_t lift[] = {spawner, caller};
ASSERT_EQ(cbm_impact_walk_run(w, lift, 2), CBM_STORE_OK);
ASSERT_EQ(cbm_impact_walk_count(w), 4);
ASSERT_EQ(hit_of(w, spawner)->hop, 3);
ASSERT_EQ(hit_of(w, spawner)->via_id, 0);
ASSERT_EQ(hit_of(w, caller)->hop, 1);
ASSERT_EQ(hit_of(w, spawn_user)->hop, 2);
cbm_impact_walk_close(w);
cbm_store_close(s);
PASS();
}
TEST(impact_walk_crosses_a_route_only_when_asked) {
/* handler --HANDLES--> route <--HTTP_CALLS-- client. A change to the
* handler concerns the client that calls its route. */
cbm_store_t *s = new_store();
int64_t handler = add_node(s, "Function", "handler");
int64_t route = add_node(s, "Route", "GET_orders");
int64_t client = add_node(s, "Function", "client");
int64_t client_caller = add_node(s, "Function", "client_caller");
add_edge(s, handler, route, "HANDLES");
add_edge(s, client, route, "HTTP_CALLS");
add_edge(s, client_caller, client, "CALLS");
cbm_impact_walk_t *w = open_walk(s, CALLS_ONLY, 1, false);
ASSERT_EQ(cbm_impact_walk_run(w, &handler, 1), CBM_STORE_OK);
ASSERT_EQ(cbm_impact_walk_count(w), 1);
cbm_impact_walk_close(w);
w = open_walk(s, CALLS_ONLY, 1, true);
ASSERT_EQ(cbm_impact_walk_run(w, &handler, 1), CBM_STORE_OK);
ASSERT_EQ(cbm_impact_walk_count(w), 4);
ASSERT_EQ(hit_of(w, route)->hop, 1);
ASSERT_STR_EQ(hit_of(w, route)->via_edge, "HANDLES");
ASSERT_EQ(hit_of(w, client)->hop, 2);
ASSERT_STR_EQ(hit_of(w, client)->via_edge, "HTTP_CALLS");
ASSERT_EQ(hit_of(w, client_caller)->hop, 3);
cbm_impact_walk_close(w);
cbm_store_close(s);
PASS();
}
static int64_t add_keyed(cbm_store_t *s, const char *name, const char *key) {
char qn[64];
char props[128];
snprintf(qn, sizeof(qn), "test.%s", name);
snprintf(props, sizeof(props), "{\"variant_key\":\"%s\"}", key);
cbm_node_t node = {.project = "test",
.label = "Function",
.name = name,
.qualified_name = qn,
.properties_json = props};
return cbm_store_upsert_node(s, &node);
}
TEST(impact_walk_crosses_platform_variants_only_when_asked) {
/* pick_win and pick_posix are the platform variants of one function (one
* variant_key); caller binds to pick_posix alone. A change to pick_win
* concerns caller. A key on one node relates nothing. */
cbm_store_t *s = new_store();
int64_t win = add_keyed(s, "pick_win", "test.pick");
int64_t posix = add_keyed(s, "pick_posix", "test.pick");
int64_t lone = add_keyed(s, "lone_win", "test.lone");
int64_t caller = add_node(s, "Function", "caller");
int64_t lone_caller = add_node(s, "Function", "lone_caller");
add_edge(s, caller, posix, "CALLS");
add_edge(s, lone_caller, lone, "CALLS");
cbm_impact_walk_t *w = open_walk(s, CALLS_ONLY, 1, false);
ASSERT_EQ(cbm_impact_walk_run(w, &win, 1), CBM_STORE_OK);
ASSERT_EQ(cbm_impact_walk_count(w), 1);
cbm_impact_walk_close(w);
cbm_impact_policy_t variants = {.project = "test",
.edge_types = CALLS_ONLY,
.edge_type_count = 1,
.follow_variant_keys = true};
ASSERT_EQ(cbm_impact_walk_open(s, &variants, &w), CBM_STORE_OK);
ASSERT_EQ(cbm_impact_walk_run(w, &win, 1), CBM_STORE_OK);
ASSERT_EQ(cbm_impact_walk_count(w), 3);
ASSERT_EQ(hit_of(w, posix)->hop, 1);
ASSERT_EQ(hit_of(w, posix)->via_id, win);
ASSERT_STR_EQ(hit_of(w, posix)->via_edge, "variant_key");
ASSERT_EQ(hit_of(w, caller)->hop, 2);
ASSERT_STR_EQ(hit_of(w, caller)->via_edge, "CALLS");
cbm_impact_walk_close(w);
/* The other direction, and a singleton key. */
ASSERT_EQ(cbm_impact_walk_open(s, &variants, &w), CBM_STORE_OK);
int64_t seeds[] = {posix, lone};
ASSERT_EQ(cbm_impact_walk_run(w, seeds, 2), CBM_STORE_OK);
ASSERT_EQ(cbm_impact_walk_count(w), 5);
ASSERT_EQ(hit_of(w, win)->hop, 1);
ASSERT_EQ(hit_of(w, caller)->hop, 1);
ASSERT_EQ(hit_of(w, lone_caller)->hop, 1);
cbm_impact_walk_close(w);
cbm_store_close(s);
PASS();
}
TEST(impact_walk_rejects_what_it_cannot_answer) {
cbm_store_t *s = new_store();
int64_t seed = add_node(s, "Function", "seed");
cbm_impact_walk_t *w = NULL;
cbm_impact_policy_t no_types = {.project = "test", .edge_types = NULL, .edge_type_count = 0};
ASSERT_EQ(cbm_impact_walk_open(s, &no_types, &w), CBM_STORE_ERR);
ASSERT_NULL(w);
ASSERT_EQ(cbm_impact_walk_open(NULL, &no_types, &w), CBM_STORE_ERR);
/* A seed the store does not hold is an error, never an empty answer: an
* empty answer would read as "nothing depends on this". */
w = open_walk(s, CALLS_ONLY, 1, false);
ASSERT_NOT_NULL(w);
int64_t unknown = seed + 1000;
ASSERT_EQ(cbm_impact_walk_run(w, &unknown, 1), CBM_STORE_ERR);
ASSERT_EQ(cbm_impact_walk_add_sinks(w, &unknown, 1), CBM_STORE_ERR);
cbm_impact_walk_close(w);
/* Duplicate seeds are one seed. */
w = open_walk(s, CALLS_ONLY, 1, false);
int64_t twice[] = {seed, seed};
ASSERT_EQ(cbm_impact_walk_run(w, twice, 2), CBM_STORE_OK);
ASSERT_EQ(cbm_impact_walk_count(w), 1);
cbm_impact_walk_close(w);
cbm_impact_walk_close(NULL);
cbm_store_close(s);
PASS();
}
SUITE(store_impact) {
RUN_TEST(impact_walk_follows_a_chain_to_its_end);
RUN_TEST(impact_walk_terminates_on_a_cycle);
RUN_TEST(impact_walk_via_parent_is_the_smallest_qualified_name);
RUN_TEST(impact_walk_via_edge_rank_beats_the_name);
RUN_TEST(impact_walk_follows_only_the_requested_edge_types);
RUN_TEST(impact_walk_reaches_a_sink_and_stops_there);
RUN_TEST(impact_walk_second_run_continues_from_the_first);
RUN_TEST(impact_walk_crosses_a_route_only_when_asked);
RUN_TEST(impact_walk_crosses_platform_variants_only_when_asked);
RUN_TEST(impact_walk_rejects_what_it_cannot_answer);
}
Reference in new issue View Git Blame Copy Permalink