gabriel / muse public
feat BREAKING feat/105-octopus-merge #1 / 1
AI Agent gabriel · 1 day ago · Oct 21, 2026 · Diff

feat: add N-way octopus merge strategy

muse#105. Git's octopus strategy merges 3+ branches into one commit when none of them conflict with each other. Muse had no equivalent: every merge strategy in merge_engine.py is structurally two-way (one base, two sides), the CLI's branch argument was nargs='?' (exactly one), and the domain plugin protocol's merge(base, left, right) signature has no N-way variant.

Design decisions (both confirmed before implementation): - CLI surface: multiple positional args (muse merge branch1 branch2 branch3), matching git's actual real octopus syntax -- no new flag. branch went from nargs='?' to nargs='*'; 1 arg is the unchanged existing two-way path, 2+ routes to the new octopus path. - Engine approach: the engine alone decides safety by computing N pairwise diffs against one shared base and checking for divergent overlap -- it never calls a new N-way domain-plugin method. Reuses the exact two-way primitives every domain already implements (diff_snapshots, detect_conflicts), deferring a real N-way protocol extension unless a domain ever needs true N-way semantic logic beyond "these changes don't overlap."

Commit-identity note: hash_commit/commit_identity_bytes already accepted an arbitrary-length parent_ids list and sorted it before hashing -- N-way merge commit IDs needed zero changes to the hashing layer. The actual schema gap was storage: CommitRecord only had two discrete parent fields. Added parent_commit_ids: list[str] (empty for ordinary 0/1/2-parent commits, which keep using the legacy two fields exactly as before -- purely additive, zero impact on existing commits) and a single helper, commit_parent_ids(record), that every parent-walking caller should use instead of reading the fields directly.

Found and fixed real correctness gaps while auditing every parent_commit_id/parent2_commit_id call site for N-way safety: - gc.py's reachability walk hardcoded the 2-parent tuple directly -- for an octopus merge, this would have marked the 3rd+ parent's entire ancestry as unreachable garbage and deleted it. Verified live: created an octopus merge, deleted one of the three merged branches' own ref (so its tip is reachable ONLY via the merge commit's 3rd parent), ran gc -- commit survived. Confirmed this would have been silently deleted before the fix (same code path, same hardcoded tuple). - verify.py's two ancestor walks (shallow-graft snapshot collection, main BFS) had the identical hardcoded-tuple gap -- would have under-verified octopus merge ancestry and could have false-flagged legitimate objects as orphaned. - name_rev.py's BFS had the same gap -- would have mis-named or missed commits reachable only through a 3rd+ parent. - graph.py's iter_ancestors and find_merge_base (the shared primitives nearly everything else delegates through) were the actual leverage point -- fixing these two functions propagates N-way-correct traversal to every downstream command built on them for free. - read.py's plain-text "Parent:" display and commit_graph.py's node output only showed 2 of N parents -- cosmetic but user-visible; both now show the full list. - rev_list.py's non-first-parent walk had the same hardcoded-tuple gap.

Left unchanged, deliberately: cherry-pick, revert, rebase, bisect, patch-id, format-patch, symlog, note-hotspots, midi-query, query_engine's follow_merges path -- all of these are legitimately first-parent-only operations by design (same as git's own default merge-commit handling for these commands), not regressions.

New tests/test_octopus_merge.py: clean 3-way and 4-way merges (one commit, correct parent count, correct unioned manifest); conflict refusal naming the exact conflicting branch pair and paths; convergent changes (two branches agreeing on the same result) correctly NOT treated as a conflict, matching two-way merge semantics; minimum-2-targets validation; no-common-ancestor refusal; CommitRecord round-trip for 3-parent commits; legacy 2-parent and 1-parent commits resolving identically via commit_parent_ids (the additive-schema guarantee). 11 tests, all green.

Regression suite (589 tests across every file touched -- octopus engine, merge CLI, merge_engine, graph, merge-base, commit-graph, log, commit, verify, read, rev-list, name-rev, gc): zero regressions.

Verified against the real CLI (muse-dev, not just pytest): clean 3-way octopus merge produces one commit with 4 parents and the correct unioned file set; two branches touching the same path refuse cleanly with the exact conflicting pair and path named in both text and --json output; the gc data-loss scenario above, reproduced and confirmed fixed live.

Docs: docs/domain-extensibility.md's Axis B section now documents octopus as a seventh (N-way, structurally distinct) merge mode alongside the existing six two-way strategies.

sha256:677e01f6429bf7ecf69b4dfb356d75b84245cd93db6377364ca6dfad0e426784 sha
sha256:dfb030d712110599faeb978c6b5eaa4534b9544477860a1e44542d41fdb37abd parent
+53 ~32 symbols
12 changed · 1211 in snapshot files
sha256:18841372f5c83743f0970aa87b936b723d070bc26ac8823d637c0c61900d34b8 snapshot
+53
symbols added
~32
symbols modified
12
files changed
1211
files in snapshot
0
dead code introduced
Semantic Changes 85 symbols
~ muse/core/octopus_merge.py .py 16 symbols added
+ OctopusConflictError class class OctopusConflictError L41–59
+ __init__ method method __init__ L49–59
+ OctopusMergeError class class OctopusMergeError L37–38
+ OctopusNoCommonAncestorError class class OctopusNoCommonAncestorError L62–63
+ OctopusResult class class OctopusResult L67–73
+ _manifest_for_commit function function _manifest_for_commit L76–83
+ compute_octopus_merge function function compute_octopus_merge L86–175
+ Manifest import import Manifest L34–34
+ annotations import import annotations L26–26
+ dataclass class import dataclass L29–29
+ detect_conflicts import import detect_conflicts L32–32
+ diff_snapshots import import diff_snapshots L32–32
+ find_merge_base import import find_merge_base L32–32
+ pathlib import import pathlib L28–28
+ read_commit import import read_commit L31–31
+ read_snapshot import import read_snapshot L33–33
~ tests/test_octopus_merge.py .py 28 symbols added
+ _commit_file function function _commit_file L40–45
+ _run function function _run L31–37
+ _tip function function _tip L68–71
+ disjoint_branches_repo function function disjoint_branches_repo L49–65
+ CliRunner import import CliRunner L19–19
+ InvokeResult import import InvokeResult L19–19
+ OctopusConflictError import import OctopusConflictError L21–21
+ OctopusNoCommonAncestorError import import OctopusNoCommonAncestorError L21–21
+ annotations import import annotations L12–12
+ commit_parent_ids import import commit_parent_ids L20–20
+ compute_octopus_merge import import compute_octopus_merge L21–21
+ get_head_commit_id import import get_head_commit_id L26–26
+ os import import os L14–14
+ pathlib import import pathlib L15–15
+ pytest import import pytest L17–17
+ read_commit import import read_commit L20–20
+ runner variable variable runner L28–28
+ test_commit_parent_ids_falls_back_for_legacy_two_parent_commits function function test_commit_parent_ids_falls_back_for_legacy_two_parent_commits L283–300
+ test_commit_parent_ids_single_parent_unaffected function function test_commit_parent_ids_single_parent_unaffected L303–317
+ test_muse_merge_cli_accepts_multiple_branches function function test_muse_merge_cli_accepts_multiple_branches L80–87
+ test_muse_merge_cli_json_reports_conflict function function test_muse_merge_cli_json_reports_conflict L90–109
+ test_octopus_merge_four_way_succeeds function function test_octopus_merge_four_way_succeeds L130–150
+ test_octopus_merge_no_common_ancestor_raises function function test_octopus_merge_no_common_ancestor_raises L222–240
+ test_octopus_merge_refuses_when_two_branches_touch_same_path function function test_octopus_merge_refuses_when_two_branches_touch_same_path L157–187
+ test_octopus_merge_requires_at_least_two_targets function function test_octopus_merge_requires_at_least_two_targets L215–219
+ test_octopus_merge_three_disjoint_branches_succeeds function function test_octopus_merge_three_disjoint_branches_succeeds L116–127
+ test_octopus_merge_tolerates_convergent_changes function function test_octopus_merge_tolerates_convergent_changes L190–212
+ test_write_commit_with_three_parents_round_trips function function test_write_commit_with_three_parents_round_trips L247–280
~ docs/domain-extensibility.md .md 1 symbol added, 3 symbols modified
+ Seventh mode: octopus (N-way) merge section Seventh mode: octopus (N-way) merge L146–168
~ The Muse Extensibility Surface: Breadth and Depth
~ Axis B: how divergence gets reconciled
~ The core idea: two independent axes
~ muse/cli/commands/commit_graph.py .py 1 symbol added, 3 symbols modified
+ commit_parent_ids import import commit_parent_ids L83–83
~ _CommitNode
~ read_commit
~ run
~ muse/cli/commands/merge.py .py 1 symbol added, 2 symbols modified
+ _run_octopus_merge function function _run_octopus_merge L270–449
~ register
~ run
~ muse/cli/commands/name_rev.py .py 1 symbol added, 2 symbols modified
+ commit_parent_ids import import commit_parent_ids L113–113
~ _build_name_map
~ read_commit
~ muse/cli/commands/read.py .py 1 symbol added, 4 symbols modified
+ commit_parent_ids import import commit_parent_ids L91–91
~ find_commits_by_prefix
~ read_commit
~ resolve_commit_ref
~ run
~ muse/cli/commands/rev_list.py .py 1 symbol added, 4 symbols modified
+ commit_parent_ids import import commit_parent_ids L65–65
~ _walk_from
~ CommitRecord
~ read_commit
~ resolve_commit_ref
~ muse/core/commits.py .py 1 symbol added, 5 symbols modified
+ commit_parent_ids function function commit_parent_ids L383–405
~ CommitDict
~ CommitRecord
~ from_dict
~ to_dict
~ _verify_commit_id
~ muse/core/gc.py .py 1 symbol modified
~ _collect_reachable_commits
~ muse/core/graph.py .py 1 symbol added, 4 symbols modified
+ commit_parent_ids import import commit_parent_ids L48–48
~ find_merge_base
~ CommitRecord
~ read_commit
~ iter_ancestors
~ muse/core/verify.py .py 1 symbol added, 4 symbols modified
+ commit_parent_ids import import commit_parent_ids L61–61
~ _collect_ancestor_snapshots
~ CommitRecord
~ read_commit
~ run_verify
Files Changed
+2 ~10
1211 in snapshot
+ muse/core/octopus_merge.py .py
+ tests/test_octopus_merge.py .py
~ docs/domain-extensibility.md .md
~ muse/cli/commands/commit_graph.py .py
~ muse/cli/commands/merge.py .py
~ muse/cli/commands/name_rev.py .py
~ muse/cli/commands/read.py .py
~ muse/cli/commands/rev_list.py .py
~ muse/core/commits.py .py
~ muse/core/gc.py .py
~ muse/core/graph.py .py
~ muse/core/verify.py .py
← Older Oldest on feat/105-octopus-merge
All commits
Newer → Latest on feat/105-octopus-merge

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:677e01f6429bf7ecf69b4dfb356d75b84245cd93db6377364ca6dfad0e426784 --body "your comment"