Repository navigation
Commit fff8ea2
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
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
10413 | 10413 | | |
10414 | 10414 | | |
10415 | 10415 | | |
10416 | | - | |
10417 | | - | |
| 10416 | + | |
| 10417 | + | |
| 10418 | + | |
10418 | 10419 | | |
10419 | 10420 | | |
10420 | 10421 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
24 | 24 | | |
25 | 25 | | |
26 | 26 | | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
27 | 37 | | |
28 | 38 | | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
29 | 49 | | |
30 | 50 | | |
31 | 51 | | |
| |||
524 | 544 | | |
525 | 545 | | |
526 | 546 | | |
| 547 | + | |
| 548 | + | |
| 549 | + | |
| 550 | + | |
| 551 | + | |
| 552 | + | |
| 553 | + | |
| 554 | + | |
| 555 | + | |
| 556 | + | |
| 557 | + | |
| 558 | + | |
| 559 | + | |
| 560 | + | |
| 561 | + | |
| 562 | + | |
| 563 | + | |
| 564 | + | |
| 565 | + | |
| 566 | + | |
| 567 | + | |
| 568 | + | |
| 569 | + | |
| 570 | + | |
| 571 | + | |
| 572 | + | |
| 573 | + | |
| 574 | + | |
| 575 | + | |
| 576 | + | |
| 577 | + | |
| 578 | + | |
| 579 | + | |
| 580 | + | |
| 581 | + | |
| 582 | + | |
| 583 | + | |
| 584 | + | |
| 585 | + | |
| 586 | + | |
| 587 | + | |
| 588 | + | |
| 589 | + | |
| 590 | + | |
| 591 | + | |
| 592 | + | |
| 593 | + | |
| 594 | + | |
| 595 | + | |
| 596 | + | |
| 597 | + | |
| 598 | + | |
| 599 | + | |
| 600 | + | |
| 601 | + | |
| 602 | + | |
| 603 | + | |
| 604 | + | |
| 605 | + | |
| 606 | + | |
| 607 | + | |
| 608 | + | |
| 609 | + | |
| 610 | + | |
| 611 | + | |
| 612 | + | |
| 613 | + | |
| 614 | + | |
| 615 | + | |
| 616 | + | |
| 617 | + | |
| 618 | + | |
| 619 | + | |
| 620 | + | |
| 621 | + | |
| 622 | + | |
| 623 | + | |
| 624 | + | |
| 625 | + | |
| 626 | + | |
| 627 | + | |
| 628 | + | |
| 629 | + | |
| 630 | + | |
| 631 | + | |
| 632 | + | |
527 | 633 | | |
528 | 634 | | |
529 | 635 | | |
530 | | - | |
| 636 | + | |
| 637 | + | |
531 | 638 | | |
532 | 639 | | |
533 | 640 | | |
| |||
537 | 644 | | |
538 | 645 | | |
539 | 646 | | |
540 | | - | |
541 | | - | |
| 647 | + | |
| 648 | + | |
| 649 | + | |
| 650 | + | |
| 651 | + | |
| 652 | + | |
| 653 | + | |
| 654 | + | |
| 655 | + | |
| 656 | + | |
542 | 657 | | |
543 | 658 | | |
544 | | - | |
545 | | - | |
546 | | - | |
547 | | - | |
548 | | - | |
549 | | - | |
550 | | - | |
551 | | - | |
552 | | - | |
553 | | - | |
554 | | - | |
555 | | - | |
556 | | - | |
| 659 | + | |
| 660 | + | |
| 661 | + | |
| 662 | + | |
| 663 | + | |
| 664 | + | |
| 665 | + | |
| 666 | + | |
| 667 | + | |
| 668 | + | |
| 669 | + | |
| 670 | + | |
| 671 | + | |
| 672 | + | |
| 673 | + | |
| 674 | + | |
| 675 | + | |
| 676 | + | |
| 677 | + | |
| 678 | + | |
| 679 | + | |
| 680 | + | |
| 681 | + | |
| 682 | + | |
| 683 | + | |
| 684 | + | |
| 685 | + | |
| 686 | + | |
| 687 | + | |
557 | 688 | | |
558 | | - | |
559 | | - | |
560 | | - | |
| 689 | + | |
| 690 | + | |
| 691 | + | |
| 692 | + | |
| 693 | + | |
561 | 694 | | |
562 | | - | |
563 | | - | |
564 | | - | |
565 | | - | |
566 | | - | |
| 695 | + | |
| 696 | + | |
| 697 | + | |
| 698 | + | |
| 699 | + | |
567 | 700 | | |
568 | | - | |
569 | | - | |
570 | | - | |
571 | | - | |
572 | | - | |
| 701 | + | |
| 702 | + | |
573 | 703 | | |
574 | | - | |
575 | | - | |
| 704 | + | |
| 705 | + | |
| 706 | + | |
| 707 | + | |
| 708 | + | |
| 709 | + | |
| 710 | + | |
| 711 | + | |
576 | 712 | | |
577 | | - | |
578 | | - | |
579 | | - | |
580 | | - | |
581 | | - | |
582 | | - | |
| 713 | + | |
| 714 | + | |
| 715 | + | |
| 716 | + | |
| 717 | + | |
| 718 | + | |
| 719 | + | |
| 720 | + | |
| 721 | + | |
| 722 | + | |
| 723 | + | |
| 724 | + | |
| 725 | + | |
| 726 | + | |
| 727 | + | |
| 728 | + | |
| 729 | + | |
| 730 | + | |
| 731 | + | |
| 732 | + | |
583 | 733 | | |
| 734 | + | |
584 | 735 | | |
585 | 736 | | |
586 | | - | |
587 | | - | |
588 | | - | |
589 | 737 | | |
590 | 738 | | |
591 | 739 | | |
| |||
695 | 843 | | |
696 | 844 | | |
697 | 845 | | |
698 | | - | |
| 846 | + | |
699 | 847 | | |
700 | 848 | | |
701 | 849 | | |
| |||
0 commit comments