gabriel / muse public
feat BREAKING task/graph-traversal-abstraction #1 / 1
AI Agent gabriel · 160 days ago · Apr 18, 2026 · Diff

feat: extract canonical graph traversal into muse/core/graph.py

Add iter_ancestors(), ancestor_ids(), and find_merge_base() as the single source of truth for all commit DAG traversal in Muse. TDD with 26 tests in tests/test_core_graph.py covering BFS ordering, dedup, multi-source, first_parent_only, exclude boundaries, max_commits cap, missing commits, diamond DAGs, and LCA edge cases.

Replace inline BFS in 8 sites: - blame.py: _walk_ancestry → iter_ancestors - rev_list.py: _exclude_set → ancestor_ids; _walk_from → iter_ancestors - range_diff.py: _exclude_set → ancestor_ids; _walk_range → iter_ancestors - commit_graph.py: _ancestors_of → ancestor_ids; main run BFS → iter_ancestors - merge_engine.py: find_merge_base → delegates to graph.find_merge_base - query_engine.py: _walk_history_bfs → iter_ancestors - pack.py: walk_commits inner loop → iter_ancestors - count_objects.py: _collect_reachable_ids → iter_ancestors

gc.py intentionally retains its raw-msgpack walk for schema-evolution robustness — documented as the sole sanctioned exception.

sha256:b6bd084f73a3976352f97a4914e4fa1f0c0a108e04f417a8ea6d05147f4ede5d sha
sha256:6639a894c0a9672cc11c4777695e9ef23ced2bb444e06eb3daee82f190041d01 parent
+70 ~12 −9 symbols
sha256:b8fc304cca93c12b46031354249ef50aee9104ebab60f26d6e2096e2bc595d86 snapshot
+70
symbols added
~12
symbols modified
−9
symbols removed
0
dead code introduced
Semantic Changes 91 symbols
~ muse/core/graph.py .py 11 symbols added
+ ancestor_ids function function ancestor_ids L152–194
+ find_merge_base function function find_merge_base L202–280
+ AbstractSet import import AbstractSet L40–40
+ CommitRecord import import CommitRecord L42–42
+ Iterable import import Iterable L39–39
+ Iterator import import Iterator L39–39
+ annotations import import annotations L35–35
+ collections import import collections L37–37
+ pathlib import import pathlib L38–38
+ read_commit import import read_commit L42–42
+ iter_ancestors function function iter_ancestors L50–144
~ tests/test_core_graph.py .py 47 symbols added
+ TestAncestorIds class class TestAncestorIds L261–312
+ test_empty_starts_returns_empty_set method method test_empty_starts_returns_empty_set L273–275
+ test_exclude_boundaries_respected method method test_exclude_boundaries_respected L277–285
+ test_max_commits_respected method method test_max_commits_respected L287–297
+ test_range_exclusion_pattern method method test_range_exclusion_pattern L299–312
+ test_returns_set_of_prefixed_ids method method test_returns_set_of_prefixed_ids L262–271
+ TestFindMergeBase class class TestFindMergeBase L320–387
+ test_ancestor_of_itself_via_chain method method test_ancestor_of_itself_via_chain L380–387
+ test_deeper_lca method method test_deeper_lca L342–348
+ test_linear_chain_returns_common_ancestor method method test_linear_chain_returns_common_ancestor L326–332
+ test_max_ancestors_raises_on_deep_graph method method test_max_ancestors_raises_on_deep_graph L366–378
+ test_no_common_ancestor_returns_none method method test_no_common_ancestor_returns_none L350–356
+ test_same_commit_returns_itself method method test_same_commit_returns_itself L321–324
+ test_symmetric method method test_symmetric L358–364
+ test_true_merge_returns_lca method method test_true_merge_returns_lca L334–340
+ TestIterAncestors class class TestIterAncestors L101–253
+ test_diamond_dag_shared_ancestor_visited_once method method test_diamond_dag_shared_ancestor_visited_once L137–149
+ test_empty_starts_yields_nothing method method test_empty_starts_yields_nothing L102–104
+ test_exclude_stops_at_boundary method method test_exclude_stops_at_boundary L164–174
+ test_first_parent_only_skips_second_parent method method test_first_parent_only_skips_second_parent L151–162
+ test_linear_chain_yields_all_in_bfs_order method method test_linear_chain_yields_all_in_bfs_order L113–121
+ test_max_commits_caps_yield method method test_max_commits_caps_yield L176–184
+ test_merge_commit_visits_both_parents method method test_merge_commit_visits_both_parents L123–135
+ test_missing_commit_skipped_walk_continues method method test_missing_commit_skipped_walk_continues L186–212
+ test_multi_source_shared_ancestor_once method method test_multi_source_shared_ancestor_once L226–234
+ test_multi_source_starts method method test_multi_source_starts L214–224
+ test_single_root_commit method method test_single_root_commit L106–111
+ test_uses_deque_not_list method method test_uses_deque_not_list L246–253
+ test_yields_commit_records_not_ids method method test_yields_commit_records_not_ids L236–244
+ _BASE_DT variable variable _BASE_DT L44–44
+ _ids function function _ids L92–93
+ _make_repo function function _make_repo L52–58
+ _write_commit function function _write_commit L61–89
+ CommitRecord import import CommitRecord L42–42
+ SnapshotRecord import import SnapshotRecord L42–42
+ ancestor_ids import import ancestor_ids L40–40
+ annotations import import annotations L32–32
+ compute_commit_id import import compute_commit_id L41–41
+ compute_snapshot_id import import compute_snapshot_id L41–41
+ datetime import import datetime L34–34
+ find_merge_base import import find_merge_base L40–40
+ iter_ancestors import import iter_ancestors L40–40
+ json import import json L35–35
+ pathlib import import pathlib L36–36
+ pytest import import pytest L38–38
+ write_commit import import write_commit L42–42
+ write_snapshot import import write_snapshot L42–42
~ muse/cli/commands/commit_graph.py .py 2 symbols added, 1 symbol removed, 2 symbols modified
− deque import import deque L77–77
+ ancestor_ids import import ancestor_ids L80–80
+ iter_ancestors import import iter_ancestors L80–80
~ _ancestors_of
~ run
~ muse/cli/commands/count_objects.py .py 1 symbol added, 1 symbol removed, 1 symbol modified
− deque import import deque L66–66
+ iter_ancestors import import iter_ancestors L70–70
~ _collect_reachable_ids
~ muse/cli/commands/range_diff.py .py 2 symbols added, 1 symbol removed, 2 symbols modified
− deque import import deque L89–89
+ ancestor_ids import import ancestor_ids L93–93
+ iter_ancestors import import iter_ancestors L93–93
~ _exclude_set
~ _walk_range
~ muse/cli/commands/rev_list.py .py 2 symbols added, 1 symbol removed, 2 symbols modified
− deque import import deque L56–56
+ ancestor_ids import import ancestor_ids L60–60
+ iter_ancestors import import iter_ancestors L60–60
~ _exclude_set
~ _walk_from
~ muse/core/blame.py .py 1 symbol added, 1 symbol removed, 1 symbol modified
− deque import import deque L37–37
+ iter_ancestors import import iter_ancestors L39–39
~ _walk_ancestry
~ muse/core/merge_engine.py .py 1 symbol removed, 1 symbol modified
− deque import import deque L55–55
~ find_merge_base
~ muse/core/pack.py .py 1 symbol added, 1 symbol modified
+ iter_ancestors import import iter_ancestors L39–39
~ walk_commits
~ muse/core/query_engine.py .py 1 symbol added, 1 symbol removed, 1 symbol modified
− deque import import deque L76–76
+ iter_ancestors import import iter_ancestors L80–80
~ _walk_history_bfs
~ tests/test_cmd_commit_graph.py .py 1 symbol added, 1 symbol removed, 1 symbol modified
− test_ancestors_of_missing_commit_returns_partial method method test_ancestors_of_missing_commit_returns_partial L148–155
+ test_ancestors_of_missing_commit_returns_empty method method test_ancestors_of_missing_commit_returns_empty L148–157
~ TestUnit
~ tests/test_core_blame.py .py 1 symbol added, 1 symbol removed
− test_walk_ancestry_uses_deque function function test_walk_ancestry_uses_deque L215–227
+ test_walk_ancestry_delegates_to_iter_ancestors function function test_walk_ancestry_delegates_to_iter_ancestors L215–228
← Older Oldest on task/graph-traversal-abstraction
All commits
Newer → Latest on task/graph-traversal-abstraction

0 comments

No comments yet. Be the first to start the discussion.

To add a comment, use the Muse CLI: muse hub commit comment sha256:b6bd084f73a3976352f97a4914e4fa1f0c0a108e04f417a8ea6d05147f4ede5d --body "your comment"