Skip to content

Commit fff8ea2

Browse files
committed
fix(depindex): select most-imported packages when auto_dep_limit truncates
Previous behavior: cbm_discover_installed_deps() truncated the discovered package list at max_results strictly in discovery order (npm/bun manifest key order, vendor-directory scan order, or manifest-Variable search order). When a project declared more packages than auto_dep_limit (default 20), the indexed subset was "first declared", not "most used", even though the auto_dep_limit registry help text (cli.c:10413) claimed "20 covers the most-used imports". New behavior: when discovery finds more candidates than max_results, over- fetch up to min(max_results * 5, 500) candidates (CBM_DEP_DISCOVERY_ OVERFETCH_MULTIPLIER / _MAX in depindex.c), then rank them by distinct project import-reference count, descending, before truncating to max_results. Ranking reuses the exact node source cbm_dep_link_cross_edges() already matches against dep Module nodes (project-scoped label="Variable" nodes, exact name match) via a new shared constant CBM_DEP_PROJECT_IMPORT_FETCH_LIMIT (500, was a literal duplicated in cross_edges) instead of inventing a second import-matching scheme. Tiebreak: packages with equal import counts sort by package name ascending, so selection is deterministic and reproducible across runs. Fallback: if the import-count store query fails, rank_by_import_usage() returns -1 and cbm_discover_installed_deps() fails OPEN — keeps discovery order and still truncates to max_results, rather than failing the whole auto-index. No behavior change when discovery finds max_results or fewer candidates: the manifest-search ecosystem path keeps its raw SQL fetch window pinned to max_results * 5 (not the larger over-fetch bound), so the underlying query and its result ordering are unchanged whenever the true candidate count is within the cap; npm and vendored-directory discovery only raise their internal stopping condition, which is a no-op unless it would otherwise have truncated. No new config keys: reuses auto_dep_limit as the post-rank cap. Tests added (tests/test_depindex.c, new fixture setup_npm_rank_fixture() using a real package.json + node_modules/ tree, and insert_import_reference() building the project Variable/import nodes rank_by_import_usage() counts): - test_discover_deps_ranks_by_import_usage: 5 declared packages, 3 imported with distinct counts (4/2/1), max_results=3 -> selects the 3 imported packages in count-descending order. - test_discover_deps_tiebreak_by_name_is_deterministic: declaration order scrambled, only one package imported; the four zero-count packages must tie-break alphabetically. - test_discover_deps_at_limit_preserves_discovery_order: candidate count equals max_results (3 == 3), so ranking must not run even though one package is heavily imported; asserts declaration order is unchanged. - test_discover_deps_rank_query_failure_falls_back_to_discovery_order: DROP TABLE nodes after project registration (npm discovery is disk-only and needs no store query, so only the ranking query fails); asserts discovery order is preserved rather than erroring. Verified TDD RED: git-stashed depindex.c only (keeping the new tests) and reran CBM_ONLY_SUITE=depindex - the two ranking tests failed with the expected "pkg-a" != "pkg-c" mismatch (order unranked), while the at-limit and fail-open tests passed unchanged (they describe pre-existing behavior). Restored the implementation and reran: all 40 depindex suite tests pass. Full suite (make -f Makefile.cbm test, ASan/UBSan): 7217 passed, 1 skipped (pre-existing Windows-only skip, unrelated), exit 0. macOS heap leak check (make -f Makefile.cbm test-leak) on the suites it covers: 0 leaks for 0 total leaked bytes (the leak-check suite list is hardcoded in Makefile.cbm and does not include depindex; manual review of the new alloc/free pairing in rank_by_import_usage() and the truncation loop in cbm_discover_installed_deps() follows the same borrow/free lifecycle already used by cbm_dep_link_cross_edges()'s mod_by_name/mod_out). cli.c: sharpen auto_dep_limit help text from "20 covers the most-used imports" to "When more packages are installed than this limit, the most-imported packages are selected (ranked by project import references, ties broken by name)" so the claim is accurate now that it is enforced. Files changed: - src/depindex/depindex.c: new rank_by_import_usage() (depindex.c:582-631) and its cbm_dep_rank_entry_t/cmp_dep_rank_entry() sort key (depindex.c:547-568); cbm_discover_installed_deps() reworked to compute fetch_limit and rank-then-truncate (depindex.c:638-738); new CBM_DEP_DISCOVERY_OVERFETCH_MULTIPLIER/_MAX enum constants and the shared CBM_DEP_PROJECT_IMPORT_FETCH_LIMIT define; cbm_dep_link_cross_edges()'s literal params.limit = 500 replaced with the shared constant. - src/cli/cli.c: auto_dep_limit help text (cli.c:10413-10417). - tests/test_depindex.c: 4 new tests + 2 helpers, registered in SUITE(depindex). Note: notes/2026-07-21-2332-path-autoindex-dependency-asymmetry-analysis.md section 9 also floated a "secondary signal" of weighting import sites by PageRank of the importing module. Not implemented here per that section's own framing ("a refinement, not a requirement") and the task's scope (plain import-reference-count ranking); left as a documented future refinement, not a deviation. Signed-off-by: Andrew Hundt <[email protected]>
1 parent 9185b98 commit fff8ea2

3 files changed

Lines changed: 391 additions & 43 deletions

File tree

‎src/cli/cli.c‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -10413,8 +10413,9 @@ const cbm_config_entry_t CBM_CONFIG_REGISTRY[] = {
1041310413
{"auto_dep_limit", "20", NULL, "Dependencies",
1041410414
"Max number of packages to auto-index",
1041510415
"0-10000",
10416-
"20 covers the most-used imports. Raise to 100+ for comprehensive dependency analysis. "
10417-
"0 = unlimited (may be very slow for large dependency trees)."},
10416+
"When more packages are installed than this limit, the most-imported packages are selected "
10417+
"(ranked by project import references, ties broken by name). Raise to 100+ for comprehensive "
10418+
"dependency analysis. 0 = unlimited (may be very slow for large dependency trees)."},
1041810419
{"dep_max_files", "1000", NULL, "Dependencies",
1041910420
"Max source files per dependency package (0=unlimited)",
1042010421
"0-1000000",

‎src/depindex/depindex.c‎

Lines changed: 189 additions & 41 deletions
Original file line numberDiff line numberDiff line change
@@ -24,8 +24,28 @@
2424
enum {
2525
CBM_DEP_MANIFEST_MAX_BYTES = 1024 * 1024,
2626
CBM_DEP_DISCOVERY_INITIAL_CAPACITY = 16,
27+
/* Usage-ranked selection (depindex.c: cbm_discover_installed_deps) needs
28+
* to see more candidates than the final cap so the most-imported
29+
* packages can be picked instead of merely the first discovered.
30+
* CBM_DEP_DISCOVERY_OVERFETCH_MULTIPLIER scales the cap; the result is
31+
* clamped to CBM_DEP_DISCOVERY_OVERFETCH_MAX regardless of multiplier.
32+
* Bound rationale: each retained cbm_dep_discovered_t candidate owns
33+
* three heap strings (package, path, version), so unbounded over-fetch
34+
* is a real memory cost, not just extra compute. */
35+
CBM_DEP_DISCOVERY_OVERFETCH_MULTIPLIER = 5,
36+
CBM_DEP_DISCOVERY_OVERFETCH_MAX = 500,
2737
};
2838

39+
/* Upper bound for fetching project Variable/import-reference nodes, shared by
40+
* cbm_dep_link_cross_edges() (matches project imports to already-indexed dep
41+
* Module nodes) and rank_by_import_usage() below (counts project imports per
42+
* not-yet-indexed candidate package). Both consumers match project import
43+
* references to package names by exact node name over the same node source,
44+
* so they share one fetch bound and one query shape rather than inventing a
45+
* second matching scheme (repo CLAUDE.md: prefer extending the established
46+
* path). */
47+
#define CBM_DEP_PROJECT_IMPORT_FETCH_LIMIT 500
48+
2949
/* ── Package Manager Parse/String ──────────────────────────────── */
3050

3151
cbm_pkg_manager_t cbm_parse_pkg_manager(const char *s) {
@@ -524,10 +544,97 @@ static int discover_vendored_deps(const char *project_root, cbm_dep_discovered_t
524544
return 0;
525545
}
526546

547+
/* Sort key for rank_by_import_usage: pairs a discovered candidate with how
548+
* many distinct project import references name it. A plain array of
549+
* cbm_dep_discovered_t can't carry a sort key without either mutating the
550+
* public struct or threading context through qsort (not portable in C11),
551+
* so this local wrapper is the established pattern in this codebase for
552+
* qsort-by-derived-key (see path_alias.c comparators). */
553+
typedef struct {
554+
cbm_dep_discovered_t entry;
555+
int64_t import_count;
556+
} cbm_dep_rank_entry_t;
557+
558+
/* Descending by import_count; ties broken by package name ascending so
559+
* selection is deterministic and reproducible across runs. */
560+
static int cmp_dep_rank_entry(const void *a, const void *b) {
561+
const cbm_dep_rank_entry_t *ea = a;
562+
const cbm_dep_rank_entry_t *eb = b;
563+
if (ea->import_count != eb->import_count)
564+
return (ea->import_count < eb->import_count) ? 1 : -1;
565+
const char *na = ea->entry.package ? ea->entry.package : "";
566+
const char *nb = eb->entry.package ? eb->entry.package : "";
567+
return strcmp(na, nb);
568+
}
569+
570+
/* Rank discovered candidates by how many distinct project import references
571+
* name each package, descending; tiebreak by package name ascending.
572+
* Reorders candidates[] in place.
573+
*
574+
* Reuses the exact node source cbm_dep_link_cross_edges() matches against
575+
* dep Module nodes (project-scoped Variable-label nodes, matched by exact
576+
* name) instead of inventing a second import-matching scheme, per repo
577+
* CLAUDE.md.
578+
*
579+
* Returns 0 on success. Returns -1 if the store query failed; callers MUST
580+
* fail OPEN on -1 (keep discovery order) rather than fail the whole
581+
* auto-index — ranking is a refinement, not a correctness requirement. */
582+
static int rank_by_import_usage(cbm_store_t *store, const char *project_name,
583+
cbm_dep_discovered_t *candidates, int candidate_count) {
584+
if (!store || !project_name || !candidates || candidate_count <= 0) return -1;
585+
586+
cbm_search_params_t params = {0};
587+
params.project = project_name;
588+
params.project_exact = true;
589+
params.label = "Variable";
590+
params.limit = CBM_DEP_PROJECT_IMPORT_FETCH_LIMIT;
591+
592+
cbm_search_output_t out = {0};
593+
if (cbm_store_search(store, &params, &out) != 0) {
594+
cbm_store_search_free(&out);
595+
return -1;
596+
}
597+
598+
CBMHashTable *counts = cbm_ht_create((uint32_t)(out.count > 0 ? out.count : 1));
599+
if (!counts) {
600+
cbm_store_search_free(&out);
601+
return -1;
602+
}
603+
for (int i = 0; i < out.count; i++) {
604+
const char *name = out.results[i].node.name;
605+
if (!name || !name[0]) continue;
606+
intptr_t cur = (intptr_t)cbm_ht_get(counts, name);
607+
cbm_ht_set(counts, name, (void *)(cur + 1));
608+
}
609+
610+
cbm_dep_rank_entry_t *ranked = calloc((size_t)candidate_count, sizeof(*ranked));
611+
if (!ranked) {
612+
cbm_ht_free(counts);
613+
cbm_store_search_free(&out);
614+
return -1;
615+
}
616+
for (int i = 0; i < candidate_count; i++) {
617+
ranked[i].entry = candidates[i];
618+
ranked[i].import_count = candidates[i].package
619+
? (int64_t)(intptr_t)cbm_ht_get(counts, candidates[i].package)
620+
: 0;
621+
}
622+
qsort(ranked, (size_t)candidate_count, sizeof(*ranked), cmp_dep_rank_entry);
623+
for (int i = 0; i < candidate_count; i++) {
624+
candidates[i] = ranked[i].entry;
625+
}
626+
627+
free(ranked);
628+
cbm_ht_free(counts);
629+
cbm_store_search_free(&out);
630+
return 0;
631+
}
632+
527633
/* Discover installed deps by querying the graph for Variable nodes
528634
* in manifest files under dependency sections.
529635
* Runtime: O(search_limit) for query + O(N) for filtering + O(N) for resolution.
530-
* Memory: O(max_results) for the results array. */
636+
* Memory: O(fetch_limit) for the results array before ranking truncates it to
637+
* max_results (see CBM_DEP_DISCOVERY_OVERFETCH_MULTIPLIER/_MAX). */
531638
int cbm_discover_installed_deps(cbm_pkg_manager_t mgr, const char *project_root,
532639
cbm_store_t *store, const char *project_name,
533640
cbm_dep_discovered_t **out, int *count,
@@ -537,55 +644,96 @@ int cbm_discover_installed_deps(cbm_pkg_manager_t mgr, const char *project_root,
537644
*count = 0;
538645
if (max_results <= 0) max_results = CBM_DEFAULT_AUTO_DEP_LIMIT;
539646

540-
if (mgr == CBM_PKG_NPM || mgr == CBM_PKG_BUN) {
541-
return discover_npm_deps(mgr, project_root, out, count, max_results);
647+
/* Over-fetch so usage ranking has more candidates to choose from than the
648+
* final cap. When the caller's cap already meets or exceeds the ceiling,
649+
* fetch exactly what was asked (no headroom to rank within, but never
650+
* less than requested). */
651+
int fetch_limit = max_results;
652+
if (max_results < INT_MAX / CBM_DEP_DISCOVERY_OVERFETCH_MULTIPLIER) {
653+
int overfetch = max_results * CBM_DEP_DISCOVERY_OVERFETCH_MULTIPLIER;
654+
fetch_limit = overfetch < CBM_DEP_DISCOVERY_OVERFETCH_MAX ? overfetch
655+
: CBM_DEP_DISCOVERY_OVERFETCH_MAX;
656+
if (fetch_limit < max_results) fetch_limit = max_results;
542657
}
543658

544-
/* C/C++ build systems and generic vendored deps: scan vendor directories directly.
545-
* These don't have a registry/lockfile to parse; deps live in the source tree. */
546-
if (mgr == CBM_PKG_MAKE || mgr == CBM_PKG_CMAKE ||
547-
mgr == CBM_PKG_MESON || mgr == CBM_PKG_CONAN ||
548-
mgr == CBM_PKG_CUSTOM) {
549-
return discover_vendored_deps(project_root, out, count, max_results);
550-
}
551-
552-
cbm_search_params_t params = {0};
553-
params.project = project_name;
554-
params.label = "Variable";
555-
params.qn_pattern = "dependencies|require";
556-
params.limit = max_results * 5; /* over-fetch since we filter post-query */
659+
int rc;
660+
if (mgr == CBM_PKG_NPM || mgr == CBM_PKG_BUN) {
661+
rc = discover_npm_deps(mgr, project_root, out, count, fetch_limit);
662+
} else if (mgr == CBM_PKG_MAKE || mgr == CBM_PKG_CMAKE || mgr == CBM_PKG_MESON ||
663+
mgr == CBM_PKG_CONAN || mgr == CBM_PKG_CUSTOM) {
664+
/* C/C++ build systems and generic vendored deps: scan vendor directories
665+
* directly. These don't have a registry/lockfile to parse; deps live in
666+
* the source tree. */
667+
rc = discover_vendored_deps(project_root, out, count, fetch_limit);
668+
} else {
669+
cbm_search_params_t params = {0};
670+
params.project = project_name;
671+
params.label = "Variable";
672+
params.qn_pattern = "dependencies|require";
673+
/* Raw-hit window stays tied to max_results (not fetch_limit): this is
674+
* the SQL fetch bound for filtering, distinct from the retention cap
675+
* below. Keeping it unscaled by fetch_limit means the underlying
676+
* query and its ordering never change, so results are byte-identical
677+
* to today whenever the true distinct-package count is within
678+
* max_results — only the retention cap grows to let ranking see more
679+
* of the SAME raw window. */
680+
params.limit = max_results * 5; /* over-fetch since we filter post-query */
681+
682+
cbm_search_output_t search_out = {0};
683+
rc = cbm_store_search(store, &params, &search_out);
684+
if (rc != 0) {
685+
cbm_store_search_free(&search_out);
686+
return -1;
687+
}
557688

558-
cbm_search_output_t search_out = {0};
559-
int rc = cbm_store_search(store, &params, &search_out);
560-
if (rc != 0) return -1;
689+
cbm_dep_discovered_t *results = calloc((size_t)fetch_limit, sizeof(cbm_dep_discovered_t));
690+
if (!results) {
691+
cbm_store_search_free(&search_out);
692+
return -1;
693+
}
561694

562-
cbm_dep_discovered_t *results = calloc(max_results, sizeof(cbm_dep_discovered_t));
563-
if (!results) {
564-
cbm_store_search_free(&search_out);
565-
return -1;
566-
}
695+
int n = 0;
696+
for (int i = 0; i < search_out.count && n < fetch_limit; i++) {
697+
const char *fp = search_out.results[i].node.file_path;
698+
const char *name = search_out.results[i].node.name;
699+
if (!fp || !name || !name[0]) continue;
567700

568-
int n = 0;
569-
for (int i = 0; i < search_out.count && n < max_results; i++) {
570-
const char *fp = search_out.results[i].node.file_path;
571-
const char *name = search_out.results[i].node.name;
572-
if (!fp || !name || !name[0]) continue;
701+
/* Filter to manifest files only (DRY via CBM_MANIFEST_FILES) */
702+
if (!cbm_is_manifest_path(fp)) continue;
573703

574-
/* Filter to manifest files only (DRY via CBM_MANIFEST_FILES) */
575-
if (!cbm_is_manifest_path(fp)) continue;
704+
cbm_dep_resolved_t resolved = {0};
705+
if (cbm_resolve_pkg_source(mgr, name, project_root, &resolved) == 0) {
706+
results[n].package = cbm_strdup(name);
707+
results[n].path = resolved.path;
708+
results[n].version = resolved.version;
709+
n++;
710+
}
711+
}
576712

577-
cbm_dep_resolved_t resolved = {0};
578-
if (cbm_resolve_pkg_source(mgr, name, project_root, &resolved) == 0) {
579-
results[n].package = cbm_strdup(name);
580-
results[n].path = resolved.path;
581-
results[n].version = resolved.version;
582-
n++;
713+
cbm_store_search_free(&search_out);
714+
*out = results;
715+
*count = n;
716+
rc = 0;
717+
}
718+
if (rc != 0) return rc;
719+
720+
/* Rank-then-truncate only when discovery actually found more than the
721+
* cap; otherwise the result is byte-identical to today regardless of the
722+
* (larger) internal fetch_limit used above — see the callers of this
723+
* function in cbm_dep_auto_index_effective(). */
724+
if (*count > max_results) {
725+
if (rank_by_import_usage(store, project_name, *out, *count) != 0) {
726+
/* Fail open: store query failed, keep discovery order (today's
727+
* semantics) rather than fail the whole auto-index. */
728+
}
729+
for (int i = max_results; i < *count; i++) {
730+
free((void *)(*out)[i].package);
731+
free((void *)(*out)[i].path);
732+
free((void *)(*out)[i].version);
583733
}
734+
*count = max_results;
584735
}
585736

586-
cbm_store_search_free(&search_out);
587-
*out = results;
588-
*count = n;
589737
return 0;
590738
}
591739

@@ -695,7 +843,7 @@ int cbm_dep_link_cross_edges(cbm_store_t *store, const char *project_name) {
695843
params.project = project_name;
696844
params.project_exact = true;
697845
params.label = "Variable"; /* import statements are typically Variable nodes */
698-
params.limit = 500;
846+
params.limit = CBM_DEP_PROJECT_IMPORT_FETCH_LIMIT;
699847

700848
cbm_search_output_t out = {0};
701849
int rc = cbm_store_search(store, &params, &out);

0 commit comments

Comments
 (0)