Skip to content

Commit 1a34255

Browse files
committed
fix(graph): quality round after the v0.11.0 probe — deterministic resolution, findability, coverage, names
Nine findings from the 2026-09-16 graph-quality probe over the eleven bench corpora, each with a test that fails without its fix and a before/after measurement on the real corpus. Deterministic resolution (O9). Two indexes of one kernel tree differed in 5,821 IMPORTS and 632 CALLS edges. Three order/load dependencies carried it: the `#include` target was the first by-name hit whose path ends with the include path — a bucket in worker merge order (include/linux/device.h vs tools/virtio/linux/device.h); the registry broke suffix_match score ties by bucket position; the LSP budget-share rule measured wall time. Include targets now prefer the File node, the least nested path, then the lexicographic path; registry ties prefer the least nested QN, then the smaller QN; the budget share is measured in thread CPU time like the budget itself. Two kernel indexes are now identical (8,529,723 nodes, 1,974,940 CALLS, zero churn), as are two elasticsearch indexes. Findability. search_graph's BM25 path honours the `label` filter and ranks an exact-name definition above test methods that repeat the token (15/15 probe queries). Coverage. The parse-coverage gap tree subtracts definitions the walker recovered inside an error region (multi-line only); kernel/sched/core.c reports 476 flagged lines instead of 7,674. Precision. Config-language callers (Makefile, CMake, YAML) no longer bind unique_name into code (kernel Makefile -> C CALLS 195 -> 0). JS-family token names ({}, 1, (x: T) => U) are not definitions; computed, quoted and escaped member keys stay (TypeScript 204 junk -> 0, 1,782 real names kept). Names are cut at their first line (elasticsearch YAML 8,306 -> 0); a comment inside an argument list is not an argument, so no Route node is named by a Java block comment; the wildcard route `/*` is still a route. HTML/Vue/Svelte/Astro embedded member calls stay unbound. Recall. A Python call through a self- or cls-rooted attribute keeps a specific unique_name member target (Django +751, elasticsearch +3,288 CALLS, no new callee names). Robustness. Edge properties never carry a split UTF-8 sequence (the 120-byte expression cut and the JSON escaper both trim a partial code point). CLI array flags accept a JSON-array literal. Cypher seeds a single-hop pattern from its selective end (kernel `MATCH (a)-[:CALLS]->(b) WHERE b.name = '_printk'`: execution limit -> 7.9 s). Signed-off-by: Martin Vogel <[email protected]>
1 parent d615088 commit 1a34255

24 files changed

Lines changed: 1634 additions & 139 deletions

‎internal/cbm/cbm.c‎

Lines changed: 192 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -125,7 +125,79 @@ void cbm_reset_profile(void) {
125125
} \
126126
} while (0)
127127

128+
/* A definition name never spans lines. Config extractors hand over a node's
129+
* whole text — a YAML block key, a Makefile recipe (`endif\n\n$(obj)/x.h`), a
130+
* ktest .conf directive — and the line break rode into the graph (2026-09-16
131+
* probe: 8,301 Field nodes on elastic/elasticsearch, 91 kernel nodes). Cut at
132+
* the first line break and drop trailing blanks; the qualified name carries
133+
* the same text as its last segment and is cut the same way. */
134+
static const char *cbm_first_line(CBMArena *a, const char *text) {
135+
if (!text) {
136+
return text;
137+
}
138+
const char *nl = strpbrk(text, "\r\n");
139+
if (!nl) {
140+
return text;
141+
}
142+
size_t n = (size_t)(nl - text);
143+
while (n > 0 && (text[n - 1] == ' ' || text[n - 1] == '\t')) {
144+
n--;
145+
}
146+
char *cut = (char *)cbm_arena_alloc(a, n + 1);
147+
if (!cut) {
148+
return text;
149+
}
150+
memcpy(cut, text, n);
151+
cut[n] = '\0';
152+
return cut;
153+
}
154+
155+
/* JS/TS files: a definition named by a literal token is the walker naming a
156+
* function or variable from an object key or a numeric pattern element —
157+
* `{}` (1,534 incoming CALLS on microsoft/TypeScript's test baselines), `1`
158+
* (38 nodes), a quoted string. An identifier starts with a letter, `_`, `$`,
159+
* `#` (private members) or a non-ASCII byte; anything else is not a name. */
160+
static bool cbm_js_family_path(const char *path) {
161+
if (!path) {
162+
return false;
163+
}
164+
const char *dot = strrchr(path, '.');
165+
if (!dot) {
166+
return false;
167+
}
168+
static const char *const exts[] = {".js", ".mjs", ".cjs", ".jsx", ".ts",
169+
".mts", ".cts", ".tsx", ".ets", NULL};
170+
for (int i = 0; exts[i]; i++) {
171+
if (strcmp(dot, exts[i]) == 0) {
172+
return true;
173+
}
174+
}
175+
return false;
176+
}
177+
178+
static bool cbm_js_name_is_junk(const char *name) {
179+
if (!name || !name[0]) {
180+
return false; /* empty names are handled by the callers' own rules */
181+
}
182+
unsigned char c = (unsigned char)name[0];
183+
bool identifier_start = (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || c == '_' ||
184+
c == '$' || c == '#' || c >= 0x80;
185+
/* Member names JS spells without an identifier start are still names:
186+
* computed keys (`[Symbol.iterator]`), string-literal keys (`"my-key"`,
187+
* `'x'`) and escaped identifiers (`А`). Measured on the TypeScript
188+
* corpus: 1,531 `[…]` members, 97 quoted members, 154 escaped
189+
* identifiers — all real definitions. What remains ({…} patterns, numeric
190+
* literals, parenthesised types, `...rest`) is a token, not a name. */
191+
bool member_key_start = c == '[' || c == '"' || c == '\'' || c == '\\';
192+
return !identifier_start && !member_key_start;
193+
}
194+
128195
void cbm_defs_push(CBMDefArray *arr, CBMArena *a, CBMDefinition def) {
196+
def.name = cbm_first_line(a, def.name);
197+
def.qualified_name = cbm_first_line(a, def.qualified_name);
198+
if (cbm_js_family_path(def.file_path) && cbm_js_name_is_junk(def.name)) {
199+
return;
200+
}
129201
GROW_ARRAY(arr, a);
130202
arr->items[arr->count++] = def;
131203
}
@@ -1358,14 +1430,88 @@ static void cbm_mark_pp_error_rows(TSNode n, uint8_t *rows, uint32_t row_count,
13581430
/* Recovery subtraction (#963): tree-sitter error recovery plus the
13591431
* ERROR-descending def walker often still extract constructs INSIDE a failed
13601432
* region (verified: a function in an #ifdef-split ERROR region and even a
1361-
* `def broken(:` both came back as defs). A region whose every line is
1362-
* covered by definitions that START inside it is definitely recovered — its
1363-
* constructs ARE in the graph — so flagging it would be a false miss.
1364-
* Container defs (Module/Package) are ignored: a file-spanning Module node is
1365-
* not evidence the region's constructs survived. Conservative: partially
1366-
* covered regions stay flagged. */
1367-
static bool cbm_region_is_recovered(uint32_t rs, uint32_t re, const CBMDefArray *defs) {
1368-
enum { MAX_COVER_DEFS = 256 };
1433+
* `def broken(:` both came back as defs). The lines a definition that STARTS
1434+
* inside the region covers are therefore in the graph, and only the lines no
1435+
* definition covers can honestly be called missed. Container defs
1436+
* (Module/Package) are ignored: a file-spanning Module node is not evidence
1437+
* the region's constructs survived.
1438+
*
1439+
* This used to be all-or-nothing — a region stayed flagged whole unless every
1440+
* line was covered. On torvalds/linux (2026-09-16 probe) one ERROR node that
1441+
* swallowed the second half of kernel/sched/core.c (lines 5522–11284) survived
1442+
* because of the comment and macro lines between its 286 extracted functions,
1443+
* and the coverage report told a reader 68 % of the scheduler was unindexed.
1444+
* Now the uncovered gaps are reported instead, and a gap holding only blank,
1445+
* comment or preprocessor lines is not a miss at all. */
1446+
static uint32_t *cbm_line_offsets(const char *src, int src_len, uint32_t *out_lines) {
1447+
uint32_t lines = 1;
1448+
for (int i = 0; i < src_len; i++) {
1449+
if (src[i] == '\n') {
1450+
lines++;
1451+
}
1452+
}
1453+
uint32_t *offs = (uint32_t *)malloc((size_t)(lines + 1) * sizeof(uint32_t));
1454+
if (!offs) {
1455+
*out_lines = 0;
1456+
return NULL;
1457+
}
1458+
uint32_t n = 0;
1459+
offs[n++] = 0;
1460+
for (int i = 0; i < src_len && n < lines; i++) {
1461+
if (src[i] == '\n') {
1462+
offs[n++] = (uint32_t)i + 1;
1463+
}
1464+
}
1465+
offs[n] = (uint32_t)src_len;
1466+
*out_lines = n;
1467+
return offs;
1468+
}
1469+
1470+
/* A 1-based line that holds nothing a reader would call missed code: blank,
1471+
* a comment line, or a preprocessor directive (the import pass owns #include;
1472+
* #if/#endif carry no construct of their own). */
1473+
static bool cbm_line_is_inert(const char *src, const uint32_t *offs, uint32_t nlines,
1474+
uint32_t line) {
1475+
if (!src || !offs || line == 0 || line > nlines) {
1476+
return true;
1477+
}
1478+
const char *p = src + offs[line - 1];
1479+
const char *end = src + offs[line];
1480+
while (p < end && (*p == ' ' || *p == '\t' || *p == '\r')) {
1481+
p++;
1482+
}
1483+
if (p >= end || *p == '\n') {
1484+
return true;
1485+
}
1486+
if (p[0] == '/' && p + 1 < end && (p[1] == '/' || p[1] == '*')) {
1487+
return true;
1488+
}
1489+
return p[0] == '*' || p[0] == '#';
1490+
}
1491+
1492+
static void cbm_regions_emit_gap(cbm_error_regions_t *out, uint32_t gs, uint32_t ge,
1493+
const char *src, const uint32_t *offs, uint32_t nlines) {
1494+
bool live = false;
1495+
for (uint32_t l = gs; l <= ge && !live; l++) {
1496+
live = !cbm_line_is_inert(src, offs, nlines, l);
1497+
}
1498+
if (!live) {
1499+
return;
1500+
}
1501+
if (out->count < CBM_MAX_ERROR_REGIONS) {
1502+
out->starts[out->count] = gs;
1503+
out->ends[out->count] = ge;
1504+
out->count++;
1505+
} else {
1506+
out->dropped++;
1507+
}
1508+
}
1509+
1510+
/* Replace [rs, re] by the sub-ranges no in-region definition covers. */
1511+
static void cbm_region_uncovered_gaps(uint32_t rs, uint32_t re, const CBMDefArray *defs,
1512+
const char *src, const uint32_t *offs, uint32_t nlines,
1513+
cbm_error_regions_t *out) {
1514+
enum { MAX_COVER_DEFS = 1024 };
13691515
uint32_t starts[MAX_COVER_DEFS];
13701516
uint32_t ends[MAX_COVER_DEFS];
13711517
int n = 0;
@@ -1377,14 +1523,25 @@ static bool cbm_region_is_recovered(uint32_t rs, uint32_t re, const CBMDefArray
13771523
if (d->start_line < rs || d->start_line > re) {
13781524
continue; /* recovery evidence must originate inside the region */
13791525
}
1526+
/* A one-line definition salvaged from inside an error region is the
1527+
* walker's guess at broken text (`def x(:` comes back as a def, a
1528+
* mis-parsed `static _Thread_local int x` as a Variable named `int`,
1529+
* and Python's synthetic builtins all sit on line 1); only a construct
1530+
* whose body spans lines proves it was understood. Conservative: real
1531+
* one-line variables and macros inside a failed region keep their line
1532+
* flagged. */
1533+
if (d->end_line <= d->start_line) {
1534+
continue;
1535+
}
13801536
starts[n] = d->start_line;
1381-
ends[n] = d->end_line < d->start_line ? d->start_line : d->end_line;
1537+
ends[n] = d->end_line;
13821538
n++;
13831539
}
13841540
if (n == 0) {
1385-
return false;
1541+
cbm_regions_emit_gap(out, rs, re, src, offs, nlines);
1542+
return;
13861543
}
1387-
/* Insertion-sort by start, then sweep for gaps in [rs, re]. */
1544+
/* Insertion-sort by start, then sweep and emit the gaps in [rs, re]. */
13881545
for (int i = 1; i < n; i++) {
13891546
uint32_t s = starts[i];
13901547
uint32_t e = ends[i];
@@ -1397,16 +1554,18 @@ static bool cbm_region_is_recovered(uint32_t rs, uint32_t re, const CBMDefArray
13971554
starts[j + 1] = s;
13981555
ends[j + 1] = e;
13991556
}
1400-
uint32_t covered_to = rs - 1;
1557+
uint32_t cursor = rs;
14011558
for (int i = 0; i < n; i++) {
1402-
if (starts[i] > covered_to + 1) {
1403-
return false; /* uncovered gap */
1559+
if (starts[i] > cursor) {
1560+
cbm_regions_emit_gap(out, cursor, starts[i] - 1, src, offs, nlines);
14041561
}
1405-
if (ends[i] > covered_to) {
1406-
covered_to = ends[i];
1562+
if (ends[i] + 1 > cursor) {
1563+
cursor = ends[i] + 1;
14071564
}
14081565
}
1409-
return covered_to >= re;
1566+
if (cursor <= re) {
1567+
cbm_regions_emit_gap(out, cursor, re, src, offs, nlines);
1568+
}
14101569
}
14111570

14121571
/* #961: true when 1-based `line` of `src` contains `name` (used to verify a
@@ -1598,16 +1757,19 @@ static bool cbm_remap_preprocessed_def(CBMDefinition *def, const CBMPreprocessed
15981757
return true;
15991758
}
16001759

1601-
static void cbm_subtract_recovered_regions(cbm_error_regions_t *regs, const CBMDefArray *defs) {
1602-
int kept = 0;
1760+
static void cbm_subtract_recovered_regions(cbm_error_regions_t *regs, const CBMDefArray *defs,
1761+
const char *src, int src_len) {
1762+
if (regs->count <= 0) {
1763+
return;
1764+
}
1765+
uint32_t nlines = 0;
1766+
uint32_t *offs = cbm_line_offsets(src, src_len, &nlines);
1767+
cbm_error_regions_t out = {{0}, {0}, 0, regs->dropped};
16031768
for (int i = 0; i < regs->count; i++) {
1604-
if (!cbm_region_is_recovered(regs->starts[i], regs->ends[i], defs)) {
1605-
regs->starts[kept] = regs->starts[i];
1606-
regs->ends[kept] = regs->ends[i];
1607-
kept++;
1608-
}
1769+
cbm_region_uncovered_gaps(regs->starts[i], regs->ends[i], defs, src, offs, nlines, &out);
16091770
}
1610-
regs->count = kept;
1771+
free(offs);
1772+
*regs = out;
16111773
}
16121774

16131775
/* #1071: a function-like macro invocation whose argument is a type token
@@ -2019,6 +2181,10 @@ static CBMFileResult *extract_file_ex_body(const char *source, int source_len, C
20192181

20202182
TSTree *tree = ts_parser_parse_with_options(parser, NULL, ts_input, opts);
20212183
uint64_t t1 = now_ns();
2184+
uint64_t parse_cpu_ns = cbm_thread_cpu_time_ns() - cpu_start_ns;
2185+
#ifdef CBM_ENABLE_TEST_SEAMS
2186+
t1 += tl_parse_wall_seam_offset_ns; /* the stall seam inflates every wall reading */
2187+
#endif
20222188

20232189
if (!tree) {
20242190
result->has_error = true;
@@ -2669,7 +2835,7 @@ static CBMFileResult *extract_file_ex_body(const char *source, int source_len, C
26692835
* splitting a brace inside a recovered function looks unrecovered:
26702836
* the refinement keeps only the discarded branch, the function starts
26712837
* above it, and the evidence falls outside the range. */
2672-
cbm_subtract_recovered_regions(&regs, &result->defs);
2838+
cbm_subtract_recovered_regions(&regs, &result->defs, source, source_len);
26732839
/* Phase 2: cut what is left down to the lines the preprocessed parse
26742840
* could not explain. */
26752841
if (pp_line_map) {

‎internal/cbm/cbm.h‎

Lines changed: 25 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -269,26 +269,31 @@ typedef struct {
269269
* calls at 251 MB with most of that empty slots. Readers index it exactly
270270
* as before; only `sizeof` changed. */
271271
CBMCallArg *args;
272-
int arg_count; // number of captured arguments (<= CBM_MAX_CALL_ARGS)
273-
int loop_depth; // enclosing loop nesting at the call site
274-
int branch_depth; // enclosing branch nesting at the call site
275-
int start_line; // 1-based source line of the call (for def range-match)
276-
uint32_t site_start_byte; // exact AST occurrence span; end > start when present
277-
uint32_t site_end_byte; // exclusive byte offset in the source file
278-
CBMSourceOrigin source_origin; // raw source or C-family preprocessed buffer
279-
bool is_method; // method/member call with an UNRESOLVED receiver. Perl:
280-
// arrow/method call ($obj->m). TS/JS/TSX: member call
281-
// x.foo() whose receiver is not this/super. Python:
282-
// x.foo() where x is not self/cls/super() and is not
283-
// rooted in an imported name. Read by the weak-member
284-
// guard and by the pxc synthetic-carrier dedup key in
285-
// pass_lsp_cross.c. Default false.
286-
bool requires_lsp_resolution; // synthetic semantic candidate (for example an implicit
287-
// C++ operator). Never fall back to textual resolution.
288-
bool callee_is_locally_bound; // bare call foo() whose callee identifier is bound as a
289-
// parameter of an enclosing function, so it cannot be the
290-
// module-level foo. Python only today. Read by the
291-
// weak-local-binding guard. Default false.
272+
int arg_count; // number of captured arguments (<= CBM_MAX_CALL_ARGS)
273+
int loop_depth; // enclosing loop nesting at the call site
274+
int branch_depth; // enclosing branch nesting at the call site
275+
int start_line; // 1-based source line of the call (for def range-match)
276+
uint32_t site_start_byte; // exact AST occurrence span; end > start when present
277+
uint32_t site_end_byte; // exclusive byte offset in the source file
278+
CBMSourceOrigin source_origin; // raw source or C-family preprocessed buffer
279+
bool is_method; // method/member call with an UNRESOLVED receiver. Perl:
280+
// arrow/method call ($obj->m). TS/JS/TSX: member call
281+
// x.foo() whose receiver is not this/super. Python:
282+
// x.foo() where x is not self/cls/super() and is not
283+
// rooted in an imported name. Read by the weak-member
284+
// guard and by the pxc synthetic-carrier dedup key in
285+
// pass_lsp_cross.c. Default false.
286+
bool requires_lsp_resolution; // synthetic semantic candidate (for example an implicit
287+
// C++ operator). Never fall back to textual resolution.
288+
bool callee_is_locally_bound; // bare call foo() whose callee identifier is bound as a
289+
// parameter of an enclosing function, so it cannot be the
290+
// module-level foo. Python only today. Read by the
291+
// weak-local-binding guard. Default false.
292+
bool receiver_is_self_attribute; // Python member call whose receiver is an attribute
293+
// chain rooted at self/cls but not self/cls itself
294+
// (self.compiler.apply_converters()). An object the
295+
// class owns, not a parameter: read by the weak-member
296+
// guard's unique-name exemption. Default false.
292297
} CBMCall;
293298

294299
typedef struct {

‎internal/cbm/extract_calls.c‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2068,6 +2068,14 @@ static void extract_call_args(CBMExtractCtx *ctx, TSNode args, CBMCall *call) {
20682068
for (uint32_t ai = 0; ai < argc && call->arg_count < CBM_MAX_CALL_ARGS; ai++) {
20692069
TSNode arg_node = ts_node_named_child(args, ai);
20702070
const char *ak = ts_node_type(arg_node);
2071+
/* tree-sitter lists a comment inside the argument list as a named
2072+
* child (Java block_comment/line_comment, C-family comment). It is
2073+
* not an argument: taken as one, a leading block comment became
2074+
* args[0] and the Route pass read its text as a URL. */
2075+
if (strcmp(ak, "comment") == 0 || strcmp(ak, "line_comment") == 0 ||
2076+
strcmp(ak, "block_comment") == 0) {
2077+
continue;
2078+
}
20712079
if (!call->args) {
20722080
call->args = cbm_arena_calloc(ctx->arena, CBM_MAX_CALL_ARGS * sizeof(CBMCallArg));
20732081
if (!call->args) {
@@ -2965,6 +2973,28 @@ static char *resolve_objectscript_instance_call(CBMArena *a, TSNode node, const
29652973
* statically-known type here, so the call must not bind by short name alone.
29662974
* Note `self.client.send()` is NOT exempt: the receiver is `self.client`, an
29672975
* attribute of unknown type, not `self` itself. */
2976+
/* True when a Python attribute-call receiver is an attribute chain ROOTED at
2977+
* self/cls but is not self/cls itself: `self.compiler.apply_converters()` has
2978+
* receiver `self.compiler`, an object the class owns. The weak-member guard's
2979+
* unique-name exemption keys on this shape (see cbm_weak_member_unique_name_
2980+
* exempt): a bare parameter (`accelerator.backward()`) carries no ownership
2981+
* evidence and stays suppressed. Direct `self.m()` is already exempt via
2982+
* python_receiver_is_exempt and is deliberately NOT flagged here. */
2983+
static bool python_receiver_rooted_at_self(CBMExtractCtx *ctx, TSNode receiver) {
2984+
if (ts_node_is_null(receiver) || strcmp(ts_node_type(receiver), "attribute") != 0) {
2985+
return false;
2986+
}
2987+
TSNode root = receiver;
2988+
while (!ts_node_is_null(root) && strcmp(ts_node_type(root), "attribute") == 0) {
2989+
root = ts_node_child_by_field_name(root, TS_FIELD("object"));
2990+
}
2991+
if (ts_node_is_null(root) || strcmp(ts_node_type(root), "identifier") != 0) {
2992+
return false;
2993+
}
2994+
char *name = cbm_node_text(ctx->arena, root, ctx->source);
2995+
return name && (strcmp(name, "self") == 0 || strcmp(name, "cls") == 0);
2996+
}
2997+
29682998
static bool python_receiver_is_exempt(CBMExtractCtx *ctx, TSNode receiver) {
29692999
if (ts_node_is_null(receiver)) {
29703000
return false;
@@ -3695,6 +3725,7 @@ CBMInvocationDescriptor handle_calls(CBMExtractCtx *ctx, TSNode node, const CBML
36953725
if (!ts_node_is_null(fn) && strcmp(ts_node_type(fn), "attribute") == 0) {
36963726
TSNode obj = ts_node_child_by_field_name(fn, TS_FIELD("object"));
36973727
call.is_method = !python_receiver_is_exempt(ctx, obj);
3728+
call.receiver_is_self_attribute = python_receiver_rooted_at_self(ctx, obj);
36983729
} else if (!ts_node_is_null(fn) && strcmp(ts_node_type(fn), "identifier") == 0) {
36993730
call.callee_is_locally_bound = python_callee_is_bound_parameter(ctx, state, fn);
37003731
}

0 commit comments

Comments
 (0)