feat(plan): implement three-way merge strategy for combining subplan ChangeSets #9293

New issue

Open

opened 2026-04-14 14:16:50 +00:00 by HAL9000 · 0 comments

HAL9000 commented

2026-04-14 14:16:50 +00:00

Owner

Metadata

Branch: feat/plan-three-way-merge-subplan-results
Commit message: feat(plan): implement three-way merge strategy for combining subplan ChangeSets
Milestone: v3.3.0 (M4: Corrections + Subplans + Checkpoints)

Background and Context

The v3.3.0 milestone (M4: Corrections + Subplans + Checkpoints) requires that results from child subplans are merged back into the parent plan's ChangeSet using a three-way merge strategy. Currently, when subplans complete execution, there is no mechanism to reconcile their individual ChangeSet outputs with the parent plan's accumulated changes.

Three-way merge is the industry-standard algorithm for combining divergent change histories: given a base (the original file state before any plan touched it), ours (changes accumulated by the parent plan), and theirs (changes produced by the subplan), the algorithm automatically merges non-overlapping hunks and flags overlapping hunks as conflicts. This mirrors how git merge works and provides a principled, deterministic approach to combining parallel workstreams.

Without this capability, subplan results cannot be safely integrated — either changes are silently overwritten or the system must serialize all subplan execution, defeating the purpose of parallel subplan execution. This issue directly satisfies the milestone acceptance criteria:

Three-way merge combines non-conflicting changes; conflicts surfaced to user

Merge strategy application on subplan results works correctly

Expected Behavior

When one or more subplans complete execution, the system merges each subplan's ChangeSet into the parent plan's ChangeSet using a three-way merge algorithm:

Base — the original file content at the time the parent plan began (snapshot stored at plan creation).
Ours — the parent plan's current accumulated ChangeSet for that file.
Theirs — the subplan's ChangeSet for that file.

Non-conflicting changes (edits to different regions of the file) are merged automatically and silently.

Conflicting changes (edits to overlapping regions) are surfaced with standard conflict markers:

<<<<<<< ours (parent plan)
def foo():
    return 1
=======
def foo():
    return 2
>>>>>>> theirs (subplan: <SUBPLAN_ID>)

The merged result (including any conflict markers) is stored back into the parent plan's ChangeSet. The parent plan's Apply phase is blocked until all conflicts are resolved.

Configurable merge strategies allow the user or automation profile to override conflict resolution:

"ours" — parent plan's version always wins; no conflict markers emitted.
"theirs" — subplan's version always wins; no conflict markers emitted.
"manual" (default) — conflicts are surfaced with markers; Apply is blocked.

agents plan diff <PLAN_ID> renders the merged ChangeSet with conflict markers highlighted (e.g., in red/yellow) so the user can review and resolve before applying.

Acceptance Criteria

ThreeWayMerger class (or equivalent) implements the three-way merge algorithm for text-based file content.
Non-conflicting hunks from parent and subplan ChangeSets are merged automatically without user intervention.
Conflicting hunks are represented in the merged ChangeSet using standard conflict markers (<<<<<<<, =======, >>>>>>>).
Merge strategy "ours" resolves all conflicts in favour of the parent plan's version.
Merge strategy "theirs" resolves all conflicts in favour of the subplan's version.
Merge strategy "manual" (default) leaves conflict markers in place and blocks the Apply phase.
agents plan diff <PLAN_ID> displays conflict markers when unresolved conflicts exist.
The Apply phase raises a MergeConflictError (or equivalent) and refuses to proceed when unresolved conflicts are present in the ChangeSet.
Merging multiple subplan ChangeSets is applied sequentially (each subplan merged one at a time into the running parent ChangeSet).
Binary files that conflict are flagged as conflicts without attempting text merge.
Unit tests cover: clean merge, single conflict, multiple conflicts, "ours" strategy, "theirs" strategy, binary file conflict.
Integration tests verify end-to-end: two subplans with overlapping edits produce conflict markers; agents plan diff shows them; Apply is blocked.
Test coverage for new code ≥ 97%.

Subtasks

Design ThreeWayMerger interface — define inputs (base, ours, theirs, strategy) and output (MergedChangeSet with conflict metadata).
Implement diff3 / three-way merge algorithm — produce merged hunks with conflict markers for overlapping regions.
Implement merge strategy resolution — "ours", "theirs", "manual" modes applied per-file during merge.
Integrate merger into subplan result collection — hook into the point where a subplan's ChangeSet is returned to the parent plan (post-execution callback or SubplanResult handler).
Persist merged ChangeSet to database — ensure the merged result (including conflict markers) is stored and retrievable.
Block Apply phase on unresolved conflicts — add a pre-apply validation step that scans the ChangeSet for conflict markers and raises MergeConflictError if found.
Update agents plan diff rendering — highlight conflict marker lines in the diff output (colour-coded or annotated).
Handle binary file conflicts — detect binary files and emit a binary-conflict sentinel instead of attempting text merge.
Write unit tests — cover all merge scenarios and strategy modes.
Write integration tests — end-to-end scenario with two subplans producing overlapping edits.
Update documentation / docstrings — document ThreeWayMerger, merge strategies, and conflict resolution workflow.

Definition of Done

This issue is closed when:

ThreeWayMerger is implemented and all unit tests pass.
Subplan result collection automatically invokes the merger for each completed subplan.
Non-conflicting changes from subplans are merged silently into the parent ChangeSet.
Conflicting changes produce conflict markers in the parent ChangeSet when strategy is "manual".
agents plan diff <PLAN_ID> correctly renders conflict markers.
The Apply phase is blocked (raises MergeConflictError) when unresolved conflicts exist.
All merge strategy modes ("ours", "theirs", "manual") behave as specified.
Integration tests pass end-to-end.
Test coverage for new/modified code is ≥ 97%.
No regressions in existing plan, subplan, or apply tests.

Automated by CleverAgents Bot
Agent: new-issue-creator

## Metadata - **Branch:** `feat/plan-three-way-merge-subplan-results` - **Commit message:** `feat(plan): implement three-way merge strategy for combining subplan ChangeSets` - **Milestone:** v3.3.0 (M4: Corrections + Subplans + Checkpoints) --- ## Background and Context The v3.3.0 milestone (M4: Corrections + Subplans + Checkpoints) requires that results from child subplans are merged back into the parent plan's `ChangeSet` using a three-way merge strategy. Currently, when subplans complete execution, there is no mechanism to reconcile their individual `ChangeSet` outputs with the parent plan's accumulated changes. Three-way merge is the industry-standard algorithm for combining divergent change histories: given a **base** (the original file state before any plan touched it), **ours** (changes accumulated by the parent plan), and **theirs** (changes produced by the subplan), the algorithm automatically merges non-overlapping hunks and flags overlapping hunks as conflicts. This mirrors how `git merge` works and provides a principled, deterministic approach to combining parallel workstreams. Without this capability, subplan results cannot be safely integrated — either changes are silently overwritten or the system must serialize all subplan execution, defeating the purpose of parallel subplan execution. This issue directly satisfies the milestone acceptance criteria: > - Three-way merge combines non-conflicting changes; conflicts surfaced to user > - Merge strategy application on subplan results works correctly --- ## Expected Behavior When one or more subplans complete execution, the system merges each subplan's `ChangeSet` into the parent plan's `ChangeSet` using a three-way merge algorithm: 1. **Base** — the original file content at the time the parent plan began (snapshot stored at plan creation). 2. **Ours** — the parent plan's current accumulated `ChangeSet` for that file. 3. **Theirs** — the subplan's `ChangeSet` for that file. **Non-conflicting changes** (edits to different regions of the file) are merged automatically and silently. **Conflicting changes** (edits to overlapping regions) are surfaced with standard conflict markers: ``` <<<<<<< ours (parent plan) def foo(): return 1 ======= def foo(): return 2 >>>>>>> theirs (subplan: <SUBPLAN_ID>) ``` The merged result (including any conflict markers) is stored back into the parent plan's `ChangeSet`. The parent plan's Apply phase is **blocked** until all conflicts are resolved. **Configurable merge strategies** allow the user or automation profile to override conflict resolution: - `"ours"` — parent plan's version always wins; no conflict markers emitted. - `"theirs"` — subplan's version always wins; no conflict markers emitted. - `"manual"` (default) — conflicts are surfaced with markers; Apply is blocked. `agents plan diff <PLAN_ID>` renders the merged `ChangeSet` with conflict markers highlighted (e.g., in red/yellow) so the user can review and resolve before applying. --- ## Acceptance Criteria - [ ] `ThreeWayMerger` class (or equivalent) implements the three-way merge algorithm for text-based file content. - [ ] Non-conflicting hunks from parent and subplan `ChangeSet`s are merged automatically without user intervention. - [ ] Conflicting hunks are represented in the merged `ChangeSet` using standard conflict markers (`<<<<<<<`, `=======`, `>>>>>>>`). - [ ] Merge strategy `"ours"` resolves all conflicts in favour of the parent plan's version. - [ ] Merge strategy `"theirs"` resolves all conflicts in favour of the subplan's version. - [ ] Merge strategy `"manual"` (default) leaves conflict markers in place and blocks the Apply phase. - [ ] `agents plan diff <PLAN_ID>` displays conflict markers when unresolved conflicts exist. - [ ] The Apply phase raises a `MergeConflictError` (or equivalent) and refuses to proceed when unresolved conflicts are present in the `ChangeSet`. - [ ] Merging multiple subplan `ChangeSet`s is applied sequentially (each subplan merged one at a time into the running parent `ChangeSet`). - [ ] Binary files that conflict are flagged as conflicts without attempting text merge. - [ ] Unit tests cover: clean merge, single conflict, multiple conflicts, `"ours"` strategy, `"theirs"` strategy, binary file conflict. - [ ] Integration tests verify end-to-end: two subplans with overlapping edits produce conflict markers; `agents plan diff` shows them; Apply is blocked. - [ ] Test coverage for new code ≥ 97%. --- ## Subtasks - [ ] **Design `ThreeWayMerger` interface** — define inputs (`base`, `ours`, `theirs`, `strategy`) and output (`MergedChangeSet` with conflict metadata). - [ ] **Implement diff3 / three-way merge algorithm** — produce merged hunks with conflict markers for overlapping regions. - [ ] **Implement merge strategy resolution** — `"ours"`, `"theirs"`, `"manual"` modes applied per-file during merge. - [ ] **Integrate merger into subplan result collection** — hook into the point where a subplan's `ChangeSet` is returned to the parent plan (post-execution callback or `SubplanResult` handler). - [ ] **Persist merged `ChangeSet` to database** — ensure the merged result (including conflict markers) is stored and retrievable. - [ ] **Block Apply phase on unresolved conflicts** — add a pre-apply validation step that scans the `ChangeSet` for conflict markers and raises `MergeConflictError` if found. - [ ] **Update `agents plan diff` rendering** — highlight conflict marker lines in the diff output (colour-coded or annotated). - [ ] **Handle binary file conflicts** — detect binary files and emit a binary-conflict sentinel instead of attempting text merge. - [ ] **Write unit tests** — cover all merge scenarios and strategy modes. - [ ] **Write integration tests** — end-to-end scenario with two subplans producing overlapping edits. - [ ] **Update documentation / docstrings** — document `ThreeWayMerger`, merge strategies, and conflict resolution workflow. --- ## Definition of Done This issue is closed when: 1. `ThreeWayMerger` is implemented and all unit tests pass. 2. Subplan result collection automatically invokes the merger for each completed subplan. 3. Non-conflicting changes from subplans are merged silently into the parent `ChangeSet`. 4. Conflicting changes produce conflict markers in the parent `ChangeSet` when strategy is `"manual"`. 5. `agents plan diff <PLAN_ID>` correctly renders conflict markers. 6. The Apply phase is blocked (raises `MergeConflictError`) when unresolved conflicts exist. 7. All merge strategy modes (`"ours"`, `"theirs"`, `"manual"`) behave as specified. 8. Integration tests pass end-to-end. 9. Test coverage for new/modified code is ≥ 97%. 10. No regressions in existing plan, subplan, or apply tests. --- **Automated by CleverAgents Bot** Agent: new-issue-creator

HAL9000 added the

labels

2026-04-14 14:18:28 +00:00

HAL9000 added this to the v3.3.0 milestone