Skip to content

Commit 42a9320

Browse files
committed
graph: one identity per conditional definition, SPAWNS edges, no cross-language guesses
The test-impact engine selects tests by walking the graph, so it can only be as right as the graph. Three gaps made it wrong: One identity for a definition's mutually exclusive variants - A definition written once per #if/#else branch, per #[cfg], per platform file (foo_linux.c / foo_win.c, platform directories) or per Go build tag is ONE node. The graph buffer keeps every variant's span in a `variants` node property (definition labels only), so a change in any variant maps to the definition. - Extraction now sees definitions inside conditional blocks where it skipped them: C++/C#/ObjC class members under #if (one cursor walk, conditional block types per language in lang_specs), Elixir defs under if/unless, Fortran .F90/.F95/.F03/.F08, Rust #[cfg] twins (no more `name#cfg(...)` QNs that lost every call), C platform files and directories (non-static file-scope functions). - Haskell: the vendored scanner reads only an #if group's first branch. The grammar stays upstream; every further branch is parsed as its own same-length view (cpp_branch_views.c) and adds what the raw parse missed. haskell/bytestring: no new partial parses, +27 functions, IMPORTS 322 -> 329, 131 definitions with variant spans. - Incremental closure repair re-parses every file of such a definition when one of them changes (variant partners through DEFINES), so a repair equals a full index. No cross-language name guesses - A name-only resolution (unique_name, suffix_match, qualified_suffix, field_type_hint, and same_module across files that only share a path stem) never binds a symbol another language defines. - Bash imports are the files a script sources: every top-level command was read as an import of its name (`set -e` imported "set", bound to a TSX method in 137 scripts here). - This repository: cross-language CALLS 5,916 -> 5,091; the remainder are C/C++ pairs, builtins and same-stem module collisions (recorded). SPAWNS edges (per language, like the HTTP client patterns) - A call that starts a program (subprocess.run, exec.Command, child_process.spawn, posix_spawn, system, Process.Start, Command::new, ... about 30 languages, through the file's own imports) gets a SPAWNS edge to a Process node named after the program (literal first word, or <dynamic>) instead of a CALLS guess. No target resolution. Both resolvers ask at the same point (parity test). The engine follows the graph - Seeds map changed lines through every variant span; a test written once per #if branch is one test; when a change reaches a non-test `main`, the tests that spawn processes are reached too (the process runs main, and main reaches everything). Signed-off-by: Martin Vogel <[email protected]>
1 parent ec0bc46 commit 42a9320

39 files changed

Lines changed: 4130 additions & 214 deletions

‎Makefile.cbm‎

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -375,12 +375,14 @@ EXTRACTION_SRCS = \
375375
$(CBM_DIR)/extract_dbt.c \
376376
$(CBM_DIR)/sql_values.c \
377377
$(CBM_DIR)/helpers.c \
378+
$(CBM_DIR)/cpp_branch_views.c \
378379
$(CBM_DIR)/result_compact.c \
379380
$(CBM_DIR)/result_spill.c \
380381
$(CBM_DIR)/lang_specs.c \
381382
$(CBM_DIR)/macro_table.c \
382383
$(CBM_DIR)/iris_export_xml.c \
383-
$(CBM_DIR)/service_patterns.c
384+
$(CBM_DIR)/service_patterns.c \
385+
$(CBM_DIR)/spawn_patterns.c
384386

385387
# LSP resolvers (compiled as one unit via lsp_all.c)
386388
LSP_SRCS = $(CBM_DIR)/lsp_all.c
@@ -481,6 +483,7 @@ PIPELINE_SRCS = \
481483
src/pipeline/pass_parallel.c \
482484
src/pipeline/pass_definitions.c \
483485
src/pipeline/pass_calls.c \
486+
src/pipeline/pass_spawns.c \
484487
src/pipeline/pass_lsp_cross.c \
485488
src/pipeline/pass_usages.c \
486489
src/pipeline/pass_semantic.c \
@@ -790,7 +793,7 @@ TEST_JAVA_LSP_SRCS = tests/test_java_lsp.c tests/test_java_lsp_coverage.c
790793
TEST_KOTLIN_LSP_SRCS = tests/test_kotlin_lsp.c
791794
TEST_RUST_LSP_SRCS = tests/test_rust_lsp.c
792795

793-
TEST_INTEGRATION_SRCS = tests/test_integration.c tests/test_incremental.c tests/test_lang_contract.c tests/test_edge_imports.c tests/test_edge_structural.c tests/test_lsp_resolution_probe.c tests/test_node_creation_probe.c tests/test_edge_types_probe.c tests/test_convergence_probe.c tests/test_matrix_known_classes.c tests/test_matrix_new_constructs.c tests/test_grammar_probe_a.c tests/test_grammar_probe_b.c tests/test_grammar_probe_c.c tests/test_grammar_probe_d.c tests/test_grammar_probe_e.c tests/test_grammar_probe_f.c tests/test_grammar_probe_g.c
796+
TEST_INTEGRATION_SRCS = tests/test_integration.c tests/test_incremental.c tests/test_lang_contract.c tests/test_edge_imports.c tests/test_edge_structural.c tests/test_lsp_resolution_probe.c tests/test_node_creation_probe.c tests/test_edge_types_probe.c tests/test_convergence_probe.c tests/test_matrix_known_classes.c tests/test_matrix_new_constructs.c tests/test_grammar_probe_a.c tests/test_grammar_probe_b.c tests/test_grammar_probe_c.c tests/test_grammar_probe_d.c tests/test_grammar_probe_e.c tests/test_grammar_probe_f.c tests/test_grammar_probe_g.c tests/test_conditional_variants.c tests/test_spawns.c
794797

795798
TEST_TRACES_SRCS = tests/test_traces.c
796799

‎README.md‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -229,6 +229,7 @@ The install script placed beside the binary is **reported, not deleted** — uni
229229
- `USAGE` — an identifier is used, but a unique callable target is not proven (including ambiguous or complex expressions)
230230
- `IMPORTS`, `DEFINES`, `IMPLEMENTS`, `INHERITS`
231231
- `HTTP_CALLS`, `ASYNC_CALLS` (cross-service)
232+
- `SPAWNS` — the caller starts another program (`subprocess.run`, `exec.Command`, `posix_spawn`, `Process.Start`, ...); the target is a `Process` node named after the program, or `<dynamic>` when the program is not a literal
232233
- `EMITS`, `LISTENS_ON` (channels)
233234
- `DATA_FLOWS` with arg-to-param mapping + field access chains
234235
- `SIMILAR_TO` (MinHash + LSH near-clone detection, Jaccard scored)
@@ -740,7 +741,7 @@ mode. `index_status` keeps describing the published graph and its freshness.
740741

741742
### Edge Types
742743

743-
`CONTAINS_PACKAGE`, `CONTAINS_FOLDER`, `CONTAINS_FILE`, `DEFINES`, `DEFINES_METHOD`, `IMPORTS`, `CALLS`, `CALL_REFERENCE`, `HTTP_CALLS`, `ASYNC_CALLS`, `IMPLEMENTS`, `HANDLES`, `USAGE`, `CONFIGURES`, `REFERENCES_FILE`, `WRITES`, `MEMBER_OF`, `TESTS`, `USES_TYPE`, `FILE_CHANGES_WITH`
744+
`CONTAINS_PACKAGE`, `CONTAINS_FOLDER`, `CONTAINS_FILE`, `DEFINES`, `DEFINES_METHOD`, `IMPORTS`, `CALLS`, `CALL_REFERENCE`, `HTTP_CALLS`, `ASYNC_CALLS`, `SPAWNS`, `IMPLEMENTS`, `HANDLES`, `USAGE`, `CONFIGURES`, `REFERENCES_FILE`, `WRITES`, `MEMBER_OF`, `TESTS`, `USES_TYPE`, `FILE_CHANGES_WITH`
744745

745746
### Qualified Names
746747

‎internal/cbm/cbm.c‎

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@
2222
#include "lsp/rust_lsp.h"
2323
#include "preprocessor.h"
2424
#include "sql_values.h" // #1735: literal INSERT rows kept out of the SQL parse
25+
#include "cpp_branch_views.h"
2526
#include "foundation/compat.h"
2627
#include "foundation/compat_fs.h" // cbm_fopen — crash-supervisor per-file marker write
2728
#include "foundation/hash_table.h" // CBMHashTable — crash-supervisor quarantine set
@@ -2146,6 +2147,102 @@ static bool cbm_sql_values_exclusion_on(const char *rel_path) {
21462147
return true;
21472148
}
21482149

2150+
/* Drop the entries a branch view re-extracted from code outside the
2151+
* conditionals: a definition with a QN the file already has at the same line,
2152+
* an import with the same name and path. */
2153+
static void cpp_view_drop_seen(CBMFileResult *r, int defs_before, int imports_before) {
2154+
int w = defs_before;
2155+
for (int i = defs_before; i < r->defs.count; i++) {
2156+
const CBMDefinition *d = &r->defs.items[i];
2157+
bool seen = false;
2158+
for (int j = 0; j < w && !seen; j++) {
2159+
const CBMDefinition *e = &r->defs.items[j];
2160+
seen = e->start_line == d->start_line && e->qualified_name && d->qualified_name &&
2161+
strcmp(e->qualified_name, d->qualified_name) == 0;
2162+
}
2163+
if (!seen) {
2164+
r->defs.items[w++] = *d;
2165+
}
2166+
}
2167+
r->defs.count = w;
2168+
w = imports_before;
2169+
for (int i = imports_before; i < r->imports.count; i++) {
2170+
const CBMImport *m = &r->imports.items[i];
2171+
bool seen = false;
2172+
for (int j = 0; j < w && !seen; j++) {
2173+
const CBMImport *e = &r->imports.items[j];
2174+
seen = e->local_name && m->local_name && e->module_path && m->module_path &&
2175+
strcmp(e->local_name, m->local_name) == 0 &&
2176+
strcmp(e->module_path, m->module_path) == 0;
2177+
}
2178+
if (!seen) {
2179+
r->imports.items[w++] = *m;
2180+
}
2181+
}
2182+
r->imports.count = w;
2183+
}
2184+
2185+
/* Haskell: the scanner parses the first branch of an #if group and swallows
2186+
* the rest up to #endif as one token, so what is written once per
2187+
* configuration (a definition, an import, a call in the other branch) was
2188+
* seen in its first variant only. Every further branch is parsed as its own
2189+
* view (cpp_branch_views.h: same bytes and lines, the other branches and the
2190+
* conditional lines blanked) and extracted into the same result, under the
2191+
* raw parse's budget. A definition at another line under a QN the file
2192+
* already has is that definition's variant; the graph keeps one identity with
2193+
* both spans. Calls and usages outside the conditionals come back as
2194+
* duplicates, which the pipeline dedups by caller and callee. The raw parse
2195+
* alone decides the file's parse status. */
2196+
static void extract_cpp_branch_views(const CBMExtractCtx *raw, const TSLanguage *ts_lang,
2197+
int64_t timeout_micros) {
2198+
int views = cbm_cpp_branch_view_count(raw->arena, raw->source, raw->source_len);
2199+
for (int v = 1; v <= views; v++) {
2200+
char *view = cbm_cpp_branch_view(raw->arena, raw->source, raw->source_len, v);
2201+
TSParser *parser = view ? get_thread_parser(ts_lang, raw->language) : NULL;
2202+
if (!parser) {
2203+
return;
2204+
}
2205+
ts_parser_reset(parser);
2206+
CBMStringInput input = {view, (uint32_t)raw->source_len};
2207+
TSInput ts_input = {&input, cbm_string_read, TSInputEncodingUTF8, NULL};
2208+
TSParseOptions opts = {0};
2209+
CBMParseBudget budget = {0}; // cppcheck-suppress unreadVariable
2210+
if (timeout_micros > 0) {
2211+
uint64_t budget_ns = (uint64_t)timeout_micros * USEC_TO_NSEC;
2212+
budget.cpu_deadline_ns = cbm_thread_cpu_time_ns() + budget_ns;
2213+
budget.wall_ceiling_ns = now_ns() + budget_ns * CBM_PARSE_WALL_CEILING_FACTOR;
2214+
opts.payload = &budget;
2215+
opts.progress_callback = cbm_timeout_cb;
2216+
}
2217+
TSTree *tree = ts_parser_parse_with_options(parser, NULL, ts_input, opts);
2218+
if (!tree) {
2219+
return;
2220+
}
2221+
CBMExtractCtx vctx = {
2222+
.arena = raw->arena,
2223+
.scratch = raw->scratch,
2224+
.result = raw->result,
2225+
.source = view,
2226+
.source_len = raw->source_len,
2227+
.language = raw->language,
2228+
.project = raw->project,
2229+
.rel_path = raw->rel_path,
2230+
.module_qn = raw->module_qn,
2231+
.root = ts_tree_root_node(tree),
2232+
.macro_table = raw->macro_table,
2233+
.return_type_table = raw->return_type_table,
2234+
.walk_budget_nodes = cbm_walk_max_nodes(),
2235+
};
2236+
int defs_before = raw->result->defs.count;
2237+
int imports_before = raw->result->imports.count;
2238+
cbm_extract_definitions(&vctx);
2239+
cbm_extract_imports(&vctx);
2240+
cbm_extract_unified(&vctx);
2241+
cpp_view_drop_seen(raw->result, defs_before, imports_before);
2242+
ts_tree_delete(tree);
2243+
}
2244+
}
2245+
21492246
static CBMFileResult *extract_file_ex_body(const char *source, int source_len, CBMLanguage language,
21502247
const char *project, const char *rel_path,
21512248
int64_t timeout_micros, const char **extra_defines,
@@ -2353,6 +2450,9 @@ static CBMFileResult *extract_file_ex_body(const char *source, int source_len, C
23532450
cbm_test_declarations_finish(&ctx);
23542451
cbm_extract_imports(&ctx);
23552452
cbm_extract_unified(&ctx);
2453+
if (cbm_lang_needs_cpp_branch_views(language)) {
2454+
extract_cpp_branch_views(&ctx, ts_lang, timeout_micros);
2455+
}
23562456
result->tree_nodes = ts_node_descendant_count(root);
23572457
result->walk_nodes_visited = ctx.walk_nodes_visited;
23582458
if (ctx.walk_budget_exhausted) {

‎internal/cbm/cpp_branch_views.c‎

Lines changed: 183 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,183 @@
1+
/*
2+
* cpp_branch_views.c — one parse view per #if/#else branch (see the header).
3+
*/
4+
#include "cpp_branch_views.h"
5+
6+
#include <string.h>
7+
8+
enum { CPP_LINE_CODE, CPP_LINE_START, CPP_LINE_ELSE, CPP_LINE_END };
9+
10+
enum { CPP_NEST_MAX = 64 };
11+
12+
bool cbm_lang_needs_cpp_branch_views(CBMLanguage lang) {
13+
return lang == CBM_LANG_HASKELL;
14+
}
15+
16+
static bool cpp_word_char(char c) {
17+
return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') || c == '_';
18+
}
19+
20+
// Classify the line at src[pos..end): a conditional directive is a '#' in
21+
// column 0, optional blanks, then the directive word — the same lines the
22+
// Haskell scanner treats as conditionals.
23+
static int cpp_line_kind(const char *src, int pos, int end) {
24+
if (pos >= end || src[pos] != '#') {
25+
return CPP_LINE_CODE;
26+
}
27+
int p = pos + 1;
28+
while (p < end && (src[p] == ' ' || src[p] == '\t')) {
29+
p++;
30+
}
31+
int w = p;
32+
while (w < end && cpp_word_char(src[w])) {
33+
w++;
34+
}
35+
static const struct {
36+
const char *word;
37+
int kind;
38+
} words[] = {
39+
{"if", CPP_LINE_START}, {"ifdef", CPP_LINE_START}, {"ifndef", CPP_LINE_START},
40+
{"else", CPP_LINE_ELSE}, {"elif", CPP_LINE_ELSE}, {"elifdef", CPP_LINE_ELSE},
41+
{"elifndef", CPP_LINE_ELSE}, {"endif", CPP_LINE_END},
42+
};
43+
size_t n = (size_t)(w - p);
44+
for (size_t i = 0; i < sizeof(words) / sizeof(words[0]); i++) {
45+
if (strlen(words[i].word) == n && memcmp(src + p, words[i].word, n) == 0) {
46+
return words[i].kind;
47+
}
48+
}
49+
return CPP_LINE_CODE;
50+
}
51+
52+
static int cpp_line_end(const char *src, int pos, int len) {
53+
const char *nl = memchr(src + pos, '\n', (size_t)(len - pos));
54+
return nl ? (int)(nl - src) : len;
55+
}
56+
57+
typedef struct {
58+
int group; // groups are numbered in order of their #if line
59+
int branch; // branch the current line is in
60+
bool outer; // the enclosing context is kept
61+
} cpp_frame_t;
62+
63+
typedef struct {
64+
cpp_frame_t frames[CPP_NEST_MAX];
65+
int depth;
66+
int overflow; // groups nested past CPP_NEST_MAX are not tracked
67+
int next;
68+
} cpp_nest_t;
69+
70+
// Track one line. Returns the innermost tracked group when the line is one of
71+
// its #else/#elif lines, else NULL.
72+
static cpp_frame_t *cpp_nest_step(cpp_nest_t *n, int kind, bool active) {
73+
switch (kind) {
74+
case CPP_LINE_START:
75+
if (n->depth < CPP_NEST_MAX && n->overflow == 0) {
76+
n->frames[n->depth++] = (cpp_frame_t){n->next, 0, active};
77+
} else {
78+
n->overflow++;
79+
}
80+
n->next++;
81+
return NULL;
82+
case CPP_LINE_ELSE:
83+
if (n->overflow > 0 || n->depth == 0) {
84+
return NULL;
85+
}
86+
n->frames[n->depth - 1].branch++;
87+
return &n->frames[n->depth - 1];
88+
case CPP_LINE_END:
89+
if (n->overflow > 0) {
90+
n->overflow--;
91+
} else if (n->depth > 0) {
92+
n->depth--;
93+
}
94+
return NULL;
95+
default:
96+
return NULL;
97+
}
98+
}
99+
100+
// Branch count per group. Returns the group count, or -1 on allocation failure.
101+
static int cpp_group_branches(CBMArena *a, const char *src, int len, int **out) {
102+
int groups = 0;
103+
for (int pos = 0; pos < len;) {
104+
int end = cpp_line_end(src, pos, len);
105+
groups += cpp_line_kind(src, pos, end) == CPP_LINE_START;
106+
pos = end + 1;
107+
}
108+
*out = NULL;
109+
if (groups == 0) {
110+
return 0;
111+
}
112+
int *branches = cbm_arena_alloc(a, sizeof(int) * (size_t)groups);
113+
if (!branches) {
114+
return -1;
115+
}
116+
for (int g = 0; g < groups; g++) {
117+
branches[g] = 1;
118+
}
119+
cpp_nest_t nest = {.depth = 0};
120+
for (int pos = 0; pos < len;) {
121+
int end = cpp_line_end(src, pos, len);
122+
cpp_frame_t *frame = cpp_nest_step(&nest, cpp_line_kind(src, pos, end), true);
123+
if (frame) {
124+
branches[frame->group] = frame->branch + 1;
125+
}
126+
pos = end + 1;
127+
}
128+
*out = branches;
129+
return groups;
130+
}
131+
132+
int cbm_cpp_branch_view_count(CBMArena *a, const char *src, int len) {
133+
int *branches = NULL;
134+
int groups = cpp_group_branches(a, src, len, &branches);
135+
int most = 1;
136+
for (int g = 0; g < groups; g++) {
137+
if (branches[g] > most) {
138+
most = branches[g];
139+
}
140+
}
141+
int views = most - 1;
142+
return views > CBM_CPP_BRANCH_VIEWS_MAX ? CBM_CPP_BRANCH_VIEWS_MAX : views;
143+
}
144+
145+
// The current line belongs to the view: every enclosing group sits in the
146+
// branch the view keeps.
147+
static bool cpp_view_keeps(const cpp_nest_t *n, const int *branches, int view) {
148+
if (n->depth == 0) {
149+
return true;
150+
}
151+
const cpp_frame_t *top = &n->frames[n->depth - 1];
152+
int nb = branches[top->group];
153+
int kept = 0;
154+
if (nb >= 2) {
155+
kept = view < nb - 1 ? view : nb - 1;
156+
}
157+
return top->outer && top->branch == kept;
158+
}
159+
160+
char *cbm_cpp_branch_view(CBMArena *a, const char *src, int len, int view) {
161+
int *branches = NULL;
162+
int groups = cpp_group_branches(a, src, len, &branches);
163+
char *buf = groups >= 0 ? cbm_arena_alloc(a, (size_t)len + 1) : NULL;
164+
if (!buf) {
165+
return NULL;
166+
}
167+
memcpy(buf, src, (size_t)len);
168+
buf[len] = '\0';
169+
cpp_nest_t nest = {.depth = 0};
170+
for (int pos = 0; pos < len;) {
171+
int end = cpp_line_end(src, pos, len);
172+
bool kept = cpp_view_keeps(&nest, branches, view);
173+
int kind = cpp_line_kind(src, pos, end);
174+
cpp_nest_step(&nest, kind, kept);
175+
if (kind != CPP_LINE_CODE || !kept) {
176+
for (int i = pos; i < end; i++) {
177+
buf[i] = buf[i] == '\r' ? '\r' : ' ';
178+
}
179+
}
180+
pos = end + 1;
181+
}
182+
return buf;
183+
}

‎internal/cbm/cpp_branch_views.h‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
#ifndef CBM_CPP_BRANCH_VIEWS_H
2+
#define CBM_CPP_BRANCH_VIEWS_H
3+
4+
#include "cbm.h"
5+
6+
/*
7+
* Branch views of a source whose grammar parses only the first branch of an
8+
* #if/#else group (the Haskell scanner swallows everything from #else to
9+
* #endif as one token, so a definition written once per configuration is seen
10+
* in its first variant only).
11+
*
12+
* A view keeps the source byte for byte and line for line: the branch it
13+
* selects in every group stays, the other branches and all conditional lines
14+
* (#if/#ifdef/#ifndef/#else/#elif.../#endif) become spaces, newlines stay. So
15+
* every span extracted from a view is a raw-source span.
16+
*
17+
* View v (1-based) selects branch min(v, branches - 1) of a group with at
18+
* least two branches, and the only branch of a group without one.
19+
*/
20+
21+
#define CBM_CPP_BRANCH_VIEWS_MAX 3
22+
23+
// True when `lang`'s grammar parses only the first branch of a conditional.
24+
bool cbm_lang_needs_cpp_branch_views(CBMLanguage lang);
25+
26+
// Number of views the source needs (0 when no group has a second branch),
27+
// at most CBM_CPP_BRANCH_VIEWS_MAX.
28+
int cbm_cpp_branch_view_count(CBMArena *a, const char *src, int len);
29+
30+
// View `view` (1..count) as an arena buffer of exactly `len` bytes plus a NUL,
31+
// or NULL on allocation failure.
32+
char *cbm_cpp_branch_view(CBMArena *a, const char *src, int len, int view);
33+
34+
#endif

0 commit comments

Comments
 (0)