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
/*
* store_impact.c — fixpoint impact walk over the stored graph. See
* store_impact.h for the contract.
*
* The walk is level-synchronous. Each level's frontier is sorted by qualified
* name and expanded edge type by edge type, in the rank order of the request:
* the first time a node is seen is therefore through its smallest (edge rank,
* parent name), which is the parent the contract promises, with no comparison
* in the inner loop.
*/
#include "store/store_impact.h"
#include "foundation/constants.h"
#include "foundation/mem_core.h"
#include <limits.h>
#include <sqlite3.h>
#include <stdlib.h>
#include <string.h>
enum {
IMPACT_INIT_CAP = 64,
IMPACT_GROWTH = 2,
IMPACT_COL_QN = 0,
IMPACT_COL_LABEL = 1,
IMPACT_BIND_ID = 1,
IMPACT_BIND_TYPE = 2,
IMPACT_ROUTE_IN_COUNT = 3,
};
static const char IMPACT_HANDLES[] = "HANDLES";
/* The via_edge of a node reached as a platform variant (follow_variant_keys):
* the property that relates the two, since no edge does. */
static const char IMPACT_VARIANT_KEY[] = "variant_key";
static const char IMPACT_ROUTE_LABEL[] = "Route";
static const char *const IMPACT_ROUTE_IN[IMPACT_ROUTE_IN_COUNT] = {"HTTP_CALLS", "ASYNC_CALLS",
"GRPC_CALLS"};
struct cbm_impact_walk {
sqlite3 *db;
cbm_store_read_scope_t *scope; /* borrowed; NULL preserves legacy path */
int status; /* sticky, keep count intact for allocated-row cleanup */
char *project;
char **edge_types; /* owned copies: a hit's via_edge points into these */
int edge_type_count;
bool follow_routes;
bool follow_variant_keys;
int max_hops; /* 0 = fixpoint */
int64_t max_id; /* largest node id when the walk opened */
int32_t *slot; /* [max_id + 1]: index into hits + 1; 0 = not reached */
uint8_t *sink; /* [max_id + 1]: reached, never expanded */
/* Platform variant groups (follow_variant_keys), read once at open: the
* nodes sharing one `variant_key`, groups of two or more only. The
* members of group g are variant_members[variant_start[g] ..
* variant_start[g + 1]), by id. variant_group is NULL when no group
* exists. */
int32_t *variant_group; /* [max_id + 1]: group index + 1; 0 = in none */
int64_t *variant_members;
int32_t *variant_start; /* [group count + 1] */
cbm_impact_hit_t *hits;
int count;
int cap;
int max_hop;
sqlite3_stmt *stmt_node; /* qualified name and label of one node */
sqlite3_stmt *stmt_in; /* sources of the edges of one type into a node */
sqlite3_stmt *stmt_out; /* targets of the edges of one type out of a node */
};
/* One frontier entry: the name to sort by and the hit it belongs to. The name
* pointer stays valid while the hit array grows; an index into it does too. */
typedef struct {
const char *qualified_name;
int hit;
} impact_frontier_t;
typedef struct {
impact_frontier_t *items;
int count;
int cap;
} impact_frontier_list_t;
static int impact_frontier_cmp(const void *left, const void *right) {
const impact_frontier_t *a = (const impact_frontier_t *)left;
const impact_frontier_t *b = (const impact_frontier_t *)right;
return strcmp(a->qualified_name, b->qualified_name);
}
static int impact_hit_cmp(const void *left, const void *right) {
const cbm_impact_hit_t *a = (const cbm_impact_hit_t *)left;
const cbm_impact_hit_t *b = (const cbm_impact_hit_t *)right;
if (a->hop != b->hop) {
return a->hop < b->hop ? -1 : 1;
}
return strcmp(a->qualified_name, b->qualified_name);
}
/* Keep allocated rows for close even when their public view is invalidated. */
static int impact_fail(cbm_impact_walk_t *w, int status) {
if (!w) {
return CBM_STORE_ERR;
}
if (w->status == CBM_STORE_OK) {
w->status = w->scope
? cbm_store_read_scope_fail(w->scope, status)
: (status == CBM_STORE_CANCELLED ? CBM_STORE_CANCELLED : CBM_STORE_ERR);
}
sqlite3_reset(w->stmt_node);
sqlite3_reset(w->stmt_in);
sqlite3_reset(w->stmt_out);
return w->status;
}
static bool impact_check(cbm_impact_walk_t *w) {
if (!w || w->status != CBM_STORE_OK) {
return false;
}
int status = w->scope ? cbm_store_read_scope_check(w->scope) : CBM_STORE_OK;
if (status != CBM_STORE_OK) {
impact_fail(w, status);
return false;
}
return true;
}
static bool impact_visible(const cbm_impact_walk_t *w) {
return w && w->status == CBM_STORE_OK &&
(!w->scope || cbm_store_read_scope_check(w->scope) == CBM_STORE_OK);
}
/* Scoped sorting polls inside comparisons and heap work. Each swap is atomic
* with respect to cancellation so the array remains a permutation for cleanup.
* The legacy path retains its existing qsort and comparators exactly. */
static bool impact_sort_compare(cbm_impact_walk_t *w, const void *a, const void *b, bool hits,
int *order) {
if (!impact_check(w)) {
return false;
}
const char *left;
const char *right;
if (hits) {
const cbm_impact_hit_t *x = a;
const cbm_impact_hit_t *y = b;
if (x->hop != y->hop) {
*order = x->hop < y->hop ? -1 : 1;
return true;
}
left = x->qualified_name;
right = y->qualified_name;
} else {
left = ((const impact_frontier_t *)a)->qualified_name;
right = ((const impact_frontier_t *)b)->qualified_name;
}
const unsigned char *x = (const unsigned char *)left;
const unsigned char *y = (const unsigned char *)right;
unsigned ticks = 0;
while (*x && *x == *y) {
x++;
y++;
if (++ticks == 256) {
ticks = 0;
if (!impact_check(w)) {
return false;
}
}
}
*order = (*x > *y) - (*x < *y);
return true;
}
static void impact_sort_swap(unsigned char *a, unsigned char *b, size_t size) {
for (size_t i = 0; i < size; i++) {
unsigned char byte = a[i];
a[i] = b[i];
b[i] = byte;
}
}
static bool impact_sift(cbm_impact_walk_t *w, unsigned char *items, size_t count, size_t root,
size_t size, bool hits) {
while (root < count / 2) {
if (!impact_check(w)) {
return false;
}
size_t child = root * 2 + 1;
int order;
if (child + 1 < count) {
if (!impact_sort_compare(w, items + child * size, items + (child + 1) * size, hits,
&order)) {
return false;
}
if (order < 0) {
child++;
}
}
if (!impact_sort_compare(w, items + root * size, items + child * size, hits, &order)) {
return false;
}
if (order >= 0) {
break;
}
impact_sort_swap(items + root * size, items + child * size, size);
root = child;
}
return true;
}
static bool impact_sort(cbm_impact_walk_t *w, void *array, int count, size_t size, bool hits) {
if (!impact_check(w)) {
return false;
}
if (!w->scope) {
if (count > 1) {
qsort(array, (size_t)count, size, hits ? impact_hit_cmp : impact_frontier_cmp);
}
return true;
}
unsigned char *items = array;
for (size_t root = (size_t)count / 2; root > 0; root--) {
if (!impact_sift(w, items, (size_t)count, root - 1, size, hits)) {
return false;
}
}
for (size_t end = (size_t)count; end > 1; end--) {
if (!impact_check(w)) {
return false;
}
impact_sort_swap(items, items + (end - 1) * size, size);
if (!impact_sift(w, items, end - 1, 0, size, hits)) {
return false;
}
}
return impact_check(w);
}
static bool impact_frontier_push(impact_frontier_list_t *list, const char *qualified_name,
int hit) {
if (list->count == list->cap) {
if (list->cap > INT_MAX / IMPACT_GROWTH) {
return false;
}
int cap = list->cap ? list->cap * IMPACT_GROWTH : IMPACT_INIT_CAP;
impact_frontier_t *grown = (impact_frontier_t *)cbm_realloc(
CBM_MEM_CLASS_STORE, list->items, (size_t)cap * sizeof(*grown));
if (!grown) {
return false;
}
list->items = grown;
list->cap = cap;
}
list->items[list->count].qualified_name = qualified_name;
list->items[list->count].hit = hit;
list->count++;
return true;
}
static bool impact_known_id(const cbm_impact_walk_t *w, int64_t id) {
return id > 0 && id <= w->max_id;
}
typedef enum {
IMPACT_ADD_OK = 0,
IMPACT_ADD_NO_NODE, /* the id names no node of this project */
IMPACT_ADD_ERROR, /* allocation or SQLite failure */
} impact_add_t;
/* Record `id` as reached and queue it for expansion. The caller has checked
* that it is in range and not reached yet. */
static impact_add_t impact_add_hit(cbm_impact_walk_t *w, impact_frontier_list_t *next, int64_t id,
int hop, int64_t via_id, const char *via_edge) {
if (!impact_check(w) || sqlite3_reset(w->stmt_node) != SQLITE_OK ||
sqlite3_bind_int64(w->stmt_node, IMPACT_BIND_ID, id) != SQLITE_OK) {
return IMPACT_ADD_ERROR;
}
int rc = sqlite3_step(w->stmt_node);
if (!impact_check(w)) {
return IMPACT_ADD_ERROR;
}
if (rc == SQLITE_DONE) {
sqlite3_reset(w->stmt_node);
return IMPACT_ADD_NO_NODE;
}
if (rc != SQLITE_ROW) {
return IMPACT_ADD_ERROR;
}
const char *qn = (const char *)sqlite3_column_text(w->stmt_node, IMPACT_COL_QN);
const char *label = (const char *)sqlite3_column_text(w->stmt_node, IMPACT_COL_LABEL);
if (w->count == w->cap) {
if (w->cap > INT_MAX / IMPACT_GROWTH) {
return IMPACT_ADD_ERROR;
}
int cap = w->cap ? w->cap * IMPACT_GROWTH : IMPACT_INIT_CAP;
cbm_impact_hit_t *grown = (cbm_impact_hit_t *)cbm_realloc(CBM_MEM_CLASS_STORE, w->hits,
(size_t)cap * sizeof(*grown));
if (!grown) {
return IMPACT_ADD_ERROR;
}
w->hits = grown;
w->cap = cap;
}
char *qn_copy = cbm_mem_strdup(CBM_MEM_CLASS_STORE, qn ? qn : "");
char *label_copy = cbm_mem_strdup(CBM_MEM_CLASS_STORE, label ? label : "");
if (!qn_copy || !label_copy || !impact_frontier_push(next, qn_copy, w->count)) {
cbm_free(CBM_MEM_CLASS_STORE, qn_copy);
cbm_free(CBM_MEM_CLASS_STORE, label_copy);
return IMPACT_ADD_ERROR;
}
cbm_impact_hit_t *hit = &w->hits[w->count];
hit->id = id;
hit->hop = hop;
hit->via_id = via_id;
hit->via_edge = via_edge;
hit->qualified_name = qn_copy;
hit->label = label_copy;
w->slot[id] = w->count + SKIP_ONE;
w->count++;
if (hop > w->max_hop) {
w->max_hop = hop;
}
if (sqlite3_reset(w->stmt_node) != SQLITE_OK || !impact_check(w)) {
return IMPACT_ADD_ERROR;
}
return IMPACT_ADD_OK;
}
/* Follow one edge type from `from` (a frontier hit) to every neighbour not
* reached yet. stmt selects the far end of the edges of that type. */
static bool impact_expand(cbm_impact_walk_t *w, sqlite3_stmt *stmt, int from, const char *edge_type,
impact_frontier_list_t *next) {
if (!impact_check(w) || w->hits[from].hop == INT_MAX) {
return false;
}
int64_t from_id = w->hits[from].id;
int hop = w->hits[from].hop + SKIP_ONE;
if (sqlite3_reset(stmt) != SQLITE_OK ||
sqlite3_bind_int64(stmt, IMPACT_BIND_ID, from_id) != SQLITE_OK ||
sqlite3_bind_text(stmt, IMPACT_BIND_TYPE, edge_type, CBM_NOT_FOUND, SQLITE_STATIC) !=
SQLITE_OK) {
return false;
}
int rc;
while ((rc = sqlite3_step(stmt)) == SQLITE_ROW) {
if (!impact_check(w)) {
return false;
}
int64_t id = sqlite3_column_int64(stmt, 0);
if (!impact_known_id(w, id) || w->slot[id] != 0) {
continue;
}
/* An edge whose far end has no node row (or one of another project)
* leads nowhere; it is not an error of the request. */
if (impact_add_hit(w, next, id, hop, from_id, edge_type) == IMPACT_ADD_ERROR) {
return false;
}
}
return rc == SQLITE_DONE && sqlite3_reset(stmt) == SQLITE_OK && impact_check(w);
}
/* Reach the other platform variants of `from` (a frontier hit): the members
* of its variant group not reached yet. */
static bool impact_expand_variants(cbm_impact_walk_t *w, int from, impact_frontier_list_t *next) {
if (!impact_check(w) || w->hits[from].hop == INT_MAX) {
return false;
}
int64_t from_id = w->hits[from].id;
int32_t group = w->variant_group[from_id];
if (group == 0) {
return true;
}
int hop = w->hits[from].hop + SKIP_ONE;
for (int32_t m = w->variant_start[group - SKIP_ONE]; m < w->variant_start[group]; m++) {
int64_t id = w->variant_members[m];
if (w->slot[id] != 0) {
continue;
}
if (impact_add_hit(w, next, id, hop, from_id, IMPACT_VARIANT_KEY) == IMPACT_ADD_ERROR) {
return false;
}
}
return impact_check(w);
}
static bool impact_expand_routes(cbm_impact_walk_t *w, const impact_frontier_list_t *frontier,
impact_frontier_list_t *next) {
for (int f = 0; f < frontier->count; f++) {
if (!impact_check(w)) {
return false;
}
int hit = frontier->items[f].hit;
if (!w->sink[w->hits[hit].id] &&
!impact_expand(w, w->stmt_out, hit, IMPACT_HANDLES, next)) {
return false;
}
}
for (int t = 0; t < IMPACT_ROUTE_IN_COUNT; t++) {
for (int f = 0; f < frontier->count; f++) {
if (!impact_check(w)) {
return false;
}
int hit = frontier->items[f].hit;
if (w->sink[w->hits[hit].id] || strcmp(w->hits[hit].label, IMPACT_ROUTE_LABEL) != 0) {
continue;
}
if (!impact_expand(w, w->stmt_in, hit, IMPACT_ROUTE_IN[t], next)) {
return false;
}
}
}
return true;
}
static bool impact_expand_level(cbm_impact_walk_t *w, const impact_frontier_list_t *frontier,
impact_frontier_list_t *next) {
for (int t = 0; t < w->edge_type_count; t++) {
for (int f = 0; f < frontier->count; f++) {
if (!impact_check(w)) {
return false;
}
int hit = frontier->items[f].hit;
if (w->sink[w->hits[hit].id]) {
continue;
}
if (!impact_expand(w, w->stmt_in, hit, w->edge_types[t], next)) {
return false;
}
}
}
if (w->follow_routes && !impact_expand_routes(w, frontier, next)) {
return false;
}
/* Platform variants rank last: an edge from the same level wins. */
for (int f = 0; w->variant_group && f < frontier->count; f++) {
if (!impact_check(w)) {
return false;
}
int hit = frontier->items[f].hit;
if (!w->sink[w->hits[hit].id] && !impact_expand_variants(w, hit, next)) {
return false;
}
}
return true;
}
static void impact_free_strings(cbm_impact_walk_t *w) {
for (int i = 0; i < w->count; i++) {
cbm_free(CBM_MEM_CLASS_STORE, (char *)w->hits[i].qualified_name);
cbm_free(CBM_MEM_CLASS_STORE, (char *)w->hits[i].label);
}
}
void cbm_impact_walk_close(cbm_impact_walk_t *w) {
if (!w) {
return;
}
sqlite3_finalize(w->stmt_node);
sqlite3_finalize(w->stmt_in);
sqlite3_finalize(w->stmt_out);
impact_free_strings(w);
cbm_free(CBM_MEM_CLASS_STORE, w->hits);
cbm_free(CBM_MEM_CLASS_STORE, w->slot);
cbm_free(CBM_MEM_CLASS_STORE, w->sink);
cbm_free(CBM_MEM_CLASS_STORE, w->variant_group);
cbm_free(CBM_MEM_CLASS_STORE, w->variant_members);
cbm_free(CBM_MEM_CLASS_STORE, w->variant_start);
for (int i = 0; i < w->edge_type_count; i++) {
cbm_free(CBM_MEM_CLASS_STORE, w->edge_types[i]);
}
cbm_free(CBM_MEM_CLASS_STORE, w->edge_types);
cbm_free(CBM_MEM_CLASS_STORE, w->project);
cbm_free(CBM_MEM_CLASS_STORE, w);
}
static bool impact_copy_policy(cbm_impact_walk_t *w, const cbm_impact_policy_t *policy) {
w->project = cbm_mem_strdup(CBM_MEM_CLASS_STORE, policy->project);
w->edge_types =
(char **)cbm_calloc(CBM_MEM_CLASS_STORE, (size_t)policy->edge_type_count * sizeof(char *));
if (!w->project || !w->edge_types) {
return false;
}
for (int i = 0; i < policy->edge_type_count; i++) {
if (!impact_check(w)) {
return false;
}
if (!policy->edge_types[i] || !policy->edge_types[i][0]) {
return false;
}
w->edge_types[i] = cbm_mem_strdup(CBM_MEM_CLASS_STORE, policy->edge_types[i]);
if (!w->edge_types[i]) {
return false;
}
w->edge_type_count = i + SKIP_ONE;
}
w->follow_routes = policy->follow_routes;
w->follow_variant_keys = policy->follow_variant_keys;
w->max_hops = policy->max_hops > 0 ? policy->max_hops : 0;
return true;
}
static bool impact_prepare(cbm_impact_walk_t *w) {
sqlite3_stmt *max_stmt = NULL;
if (!impact_check(w) || sqlite3_prepare_v2(w->db, "SELECT COALESCE(MAX(id), 0) FROM nodes",
CBM_NOT_FOUND, &max_stmt, NULL) != SQLITE_OK) {
return false;
}
bool have_max = sqlite3_step(max_stmt) == SQLITE_ROW;
if (have_max) {
w->max_id = sqlite3_column_int64(max_stmt, 0);
}
int finalized = sqlite3_finalize(max_stmt);
if (!have_max || finalized != SQLITE_OK || !impact_check(w) || w->max_id < 0 ||
w->max_id >= INT32_MAX) {
return false;
}
/* The whole per-node state, sized once from the graph: whether the walk
* can run is decided here, not while it is half way through. */
size_t slots = (size_t)w->max_id + SKIP_ONE;
w->slot = (int32_t *)cbm_calloc(CBM_MEM_CLASS_STORE, slots * sizeof(int32_t));
w->sink = (uint8_t *)cbm_calloc(CBM_MEM_CLASS_STORE, slots);
if (!w->slot || !w->sink) {
return false;
}
if (!impact_check(w) ||
sqlite3_prepare_v2(w->db,
"SELECT qualified_name, label FROM nodes WHERE id = ?1 AND project = ?2",
CBM_NOT_FOUND, &w->stmt_node, NULL) != SQLITE_OK ||
!impact_check(w) ||
sqlite3_prepare_v2(w->db, "SELECT source_id FROM edges WHERE target_id = ?1 AND type = ?2",
CBM_NOT_FOUND, &w->stmt_in, NULL) != SQLITE_OK ||
!impact_check(w) ||
sqlite3_prepare_v2(w->db, "SELECT target_id FROM edges WHERE source_id = ?1 AND type = ?2",
CBM_NOT_FOUND, &w->stmt_out, NULL) != SQLITE_OK) {
return false;
}
/* The project never changes for the life of the walk. */
return sqlite3_bind_text(w->stmt_node, IMPACT_BIND_TYPE, w->project, CBM_NOT_FOUND,
SQLITE_STATIC) == SQLITE_OK &&
impact_check(w);
}
static bool impact_grow(void **items, int *cap, int count, size_t size) {
if (count < *cap) {
return true;
}
if (*cap > INT_MAX / IMPACT_GROWTH) {
return false;
}
int next = *cap ? *cap * IMPACT_GROWTH : IMPACT_INIT_CAP;
void *grown = cbm_realloc(CBM_MEM_CLASS_STORE, *items, (size_t)next * size);
if (!grown) {
return false;
}
*items = grown;
*cap = next;
return true;
}
/* The ids read so far end the run of one key: it is a group when two or more
* nodes carry the key; a key on one node relates nothing and is dropped. */
static bool impact_close_variant_run(cbm_impact_walk_t *w, int run, int *count, int *groups,
int *group_cap) {
if (*count - run < PAIR_LEN) {
*count = run;
return true;
}
if (!impact_grow((void **)&w->variant_start, group_cap, *groups, sizeof(int32_t))) {
return false;
}
w->variant_start[(*groups)++] = run;
return true;
}
/* Platform variant groups (follow_variant_keys): every node of the project
* that carries a `variant_key`, in one read ordered by (key, id), so the
* groups are a pure function of the graph. The instr() guard keeps the JSON
* parse to the nodes that have the property. */
static bool impact_load_variants(cbm_impact_walk_t *w) {
if (!w->follow_variant_keys) {
return true;
}
sqlite3_stmt *stmt = NULL;
if (!impact_check(w) ||
sqlite3_prepare_v2(w->db,
"SELECT k, id FROM (SELECT id, CASE WHEN json_valid(properties)"
" THEN json_extract(properties, '$.variant_key') END AS k FROM nodes"
" WHERE project = ?1 AND instr(properties, '\"variant_key\"') > 0)"
" WHERE typeof(k) = 'text' ORDER BY k, id",
CBM_NOT_FOUND, &stmt, NULL) != SQLITE_OK ||
sqlite3_bind_text(stmt, IMPACT_BIND_ID, w->project, CBM_NOT_FOUND, SQLITE_STATIC) !=
SQLITE_OK) {
sqlite3_finalize(stmt);
return false;
}
int count = 0;
int cap = 0;
int groups = 0;
int group_cap = 0;
int run = 0; /* where the current key's ids start in variant_members */
char *key = NULL; /* the current key */
bool ok = true;
int rc = SQLITE_ROW;
while (ok && (rc = sqlite3_step(stmt)) == SQLITE_ROW) {
const char *k = (const char *)sqlite3_column_text(stmt, 0);
int64_t id = sqlite3_column_int64(stmt, SKIP_ONE);
ok = impact_check(w);
if (!ok || !k || !impact_known_id(w, id)) {
continue;
}
if (!key || strcmp(key, k) != 0) {
ok = impact_close_variant_run(w, run, &count, &groups, &group_cap);
run = count;
cbm_free(CBM_MEM_CLASS_STORE, key);
key = cbm_mem_strdup(CBM_MEM_CLASS_STORE, k);
ok = ok && key;
}
ok = ok &&
impact_grow((void **)&w->variant_members, &cap, count, sizeof(*w->variant_members));
if (ok) {
w->variant_members[count++] = id;
}
}
cbm_free(CBM_MEM_CLASS_STORE, key);
ok = ok && rc == SQLITE_DONE && impact_close_variant_run(w, run, &count, &groups, &group_cap);
ok = sqlite3_finalize(stmt) == SQLITE_OK && ok && impact_check(w);
if (!ok || groups == 0) {
return ok;
}
/* The end of the last group. */
if (!impact_grow((void **)&w->variant_start, &group_cap, groups, sizeof(int32_t))) {
return false;
}
w->variant_start[groups] = count;
w->variant_group = (int32_t *)cbm_calloc(CBM_MEM_CLASS_STORE,
((size_t)w->max_id + SKIP_ONE) * sizeof(int32_t));
if (!w->variant_group) {
return false;
}
for (int g = 0; g < groups; g++) {
for (int32_t m = w->variant_start[g]; m < w->variant_start[g + SKIP_ONE]; m++) {
w->variant_group[w->variant_members[m]] = g + SKIP_ONE;
}
}
return impact_check(w);
}
static int impact_open(cbm_store_t *s, cbm_store_read_scope_t *scope,
const cbm_impact_policy_t *policy, cbm_impact_walk_t **out) {
if (out) {
*out = NULL;
}
if (scope) {
int status = cbm_store_read_scope_check(scope);
if (status != CBM_STORE_OK) {
return status;
}
}
sqlite3 *db = cbm_store_get_db(s);
if (!db || !out || !policy || !policy->project || !policy->project[0] || !policy->edge_types ||
policy->edge_type_count <= 0) {
return scope ? cbm_store_read_scope_fail(scope, CBM_STORE_ERR) : CBM_STORE_ERR;
}
cbm_impact_walk_t *w = (cbm_impact_walk_t *)cbm_calloc(CBM_MEM_CLASS_STORE, sizeof(*w));
if (!w) {
return scope ? cbm_store_read_scope_fail(scope, CBM_STORE_ERR) : CBM_STORE_ERR;
}
w->db = db;
w->scope = scope;
if (!impact_copy_policy(w, policy) || !impact_prepare(w) || !impact_load_variants(w) ||
!impact_check(w)) {
int status = impact_fail(w, CBM_STORE_ERR);
cbm_impact_walk_close(w);
return status;
}
*out = w;
return CBM_STORE_OK;
}
int cbm_impact_walk_open(cbm_store_t *s, const cbm_impact_policy_t *policy,
cbm_impact_walk_t **out) {
return impact_open(s, NULL, policy, out);
}
int cbm_impact_walk_open_scoped(cbm_store_read_scope_t *scope, const cbm_impact_policy_t *policy,
cbm_impact_walk_t **out) {
if (!scope) {
if (out) {
*out = NULL;
}
return CBM_STORE_ERR;
}
return impact_open(cbm_store_read_scope_store(scope), scope, policy, out);
}
/* True when `id` names a node of the walk's project. */
static bool impact_node_exists(cbm_impact_walk_t *w, int64_t id) {
if (!impact_check(w) || !impact_known_id(w, id) || sqlite3_reset(w->stmt_node) != SQLITE_OK ||
sqlite3_bind_int64(w->stmt_node, IMPACT_BIND_ID, id) != SQLITE_OK) {
return false;
}
int rc = sqlite3_step(w->stmt_node);
int reset = sqlite3_reset(w->stmt_node);
return rc == SQLITE_ROW && reset == SQLITE_OK && impact_check(w);
}
int cbm_impact_walk_add_sinks(cbm_impact_walk_t *w, const int64_t *ids, int count) {
if (!impact_check(w) || count < 0 || (count > 0 && !ids)) {
return impact_fail(w, CBM_STORE_ERR);
}
for (int i = 0; i < count; i++) {
if (!impact_node_exists(w, ids[i])) {
return impact_fail(w, CBM_STORE_ERR);
}
}
for (int i = 0; i < count; i++) {
if (!impact_check(w)) {
return impact_fail(w, CBM_STORE_ERR);
}
w->sink[ids[i]] = SKIP_ONE;
}
return impact_check(w) ? CBM_STORE_OK : impact_fail(w, CBM_STORE_ERR);
}
static bool impact_canonical_order(cbm_impact_walk_t *w) {
if (!impact_sort(w, w->hits, w->count, sizeof(*w->hits), true)) {
return false;
}
for (int i = 0; i < w->count; i++) {
if (!impact_check(w)) {
return false;
}
w->slot[w->hits[i].id] = i + SKIP_ONE;
}
return impact_check(w);
}
int cbm_impact_walk_run(cbm_impact_walk_t *w, const int64_t *seeds, int count) {
if (!impact_check(w) || count < 0 || (count > 0 && !seeds) ||
(w->count > 0 && w->max_hop == INT_MAX)) {
return impact_fail(w, CBM_STORE_ERR);
}
for (int i = 0; i < count; i++) {
if (!impact_check(w) || !impact_known_id(w, seeds[i])) {
return impact_fail(w, CBM_STORE_ERR);
}
}
impact_frontier_list_t frontier = {0};
impact_frontier_list_t next = {0};
int base_hop = w->count > 0 ? w->max_hop + SKIP_ONE : 0;
int level = 0; /* hops walked from the seeds of this run */
bool ok = true;
for (int i = 0; i < count && ok; i++) {
if (!impact_check(w)) {
ok = false;
break;
}
if (w->slot[seeds[i]] != 0) {
continue; /* reached already, or the same seed twice */
}
ok = impact_add_hit(w, &frontier, seeds[i], base_hop, 0, NULL) == IMPACT_ADD_OK;
}
while (ok && frontier.count > 0 && (w->max_hops == 0 || level < w->max_hops)) {
if (level == INT_MAX ||
!impact_sort(w, frontier.items, frontier.count, sizeof(*frontier.items), false)) {
ok = false;
break;
}
level++;
next.count = 0;
ok = impact_expand_level(w, &frontier, &next);
impact_frontier_list_t done = frontier;
frontier = next;
next = done;
}
cbm_free(CBM_MEM_CLASS_STORE, frontier.items);
cbm_free(CBM_MEM_CLASS_STORE, next.items);
sqlite3_reset(w->stmt_node);
sqlite3_reset(w->stmt_in);
sqlite3_reset(w->stmt_out);
if (!ok || !impact_canonical_order(w) || !impact_check(w)) {
return impact_fail(w, CBM_STORE_ERR);
}
return CBM_STORE_OK;
}
int cbm_impact_walk_count(const cbm_impact_walk_t *w) {
return impact_visible(w) ? w->count : 0;
}
const cbm_impact_hit_t *cbm_impact_walk_hits(const cbm_impact_walk_t *w) {
return impact_visible(w) ? w->hits : NULL;
}
bool cbm_impact_walk_reached(const cbm_impact_walk_t *w, int64_t id) {
return impact_visible(w) && impact_known_id(w, id) && w->slot[id] != 0;
}
const cbm_impact_hit_t *cbm_impact_walk_hit(const cbm_impact_walk_t *w, int64_t id) {
return cbm_impact_walk_reached(w, id) ? &w->hits[w->slot[id] - SKIP_ONE] : NULL;
}