feat(decision): implement influence DAG traversal in correction affected subtree computation #556

Merged

freemo merged 1 commit from feature/m5-influence-dag-traversal into master

2026-03-04 15:46:55 +00:00

freemo commented

2026-03-04 04:22:26 +00:00

Owner

Summary

Extended CorrectionService._compute_affected_subtree() to BFS over both the structural tree (parent-child) and influence DAG (decision_dependencies edges), computing the union of all transitively affected decisions as specified in § Affected Subtree Computation (lines 28359-28391).
Added cycle detection guard via visited set — corrupt DAG cycles are handled gracefully with a warning log rather than infinite loops.
Updated DecisionService.record_decision() to accept dependency_decision_ids for recording influence relationships during decision creation, populating the influence DAG.
Added DecisionService.get_influence_edges() to retrieve the influence DAG as an adjacency list.
All public CorrectionService methods (analyze_impact, execute_revert, execute_correction, generate_dry_run_report) now accept an optional influence_edges parameter (backward-compatible, defaults to None).

Key Design Decisions

Single BFS pass over union of edges: Rather than separate traversals for structural tree and influence DAG, one BFS pass unions both edge sources. This ensures O(V+E) complexity and consistent visit order.
Cycle detection via visited set: The visited set prevents revisiting nodes. A warning is logged when a cycle is detected (indicating data corruption), but the BFS terminates cleanly.
Influence edge logging: Traversal emits count of influence edges processed for observability.
Backward-compatible API: Existing callers that only pass decision_tree without influence_edges continue to work identically.

Test Results

Behave BDD: 257 features passed, 8145 scenarios passed, 31446 steps passed — 0 failures, 0 errors
Robot Framework: 1120 passed, 23 failed (all 23 failures are pre-existing, unrelated to this change; our 6 new tests all pass)
Coverage: 97.0% (threshold: 97%)
Lint: All checks passed (ruff)
Typecheck: 0 errors, 0 warnings (pyright strict)

Files Changed

src/cleveragents/application/services/correction_service.py — Extended _compute_affected_subtree() and public method signatures
src/cleveragents/application/services/decision_service.py — Added dependency_decision_ids, _record_dependencies(), get_influence_edges()
features/influence_dag_traversal.feature — 11 BDD scenarios
features/steps/influence_dag_traversal_steps.py — Step implementations
robot/influence_dag_traversal.robot — 6 Robot Framework integration tests
robot/helper_influence_dag_traversal.py — Robot helper script
benchmarks/influence_dag_bench.py — ASV benchmarks for traversal performance
CHANGELOG.md — Changelog entry

Closes #542

## Summary - Extended `CorrectionService._compute_affected_subtree()` to BFS over both the structural tree (parent-child) and influence DAG (`decision_dependencies` edges), computing the union of all transitively affected decisions as specified in § Affected Subtree Computation (lines 28359-28391). - Added cycle detection guard via visited set — corrupt DAG cycles are handled gracefully with a warning log rather than infinite loops. - Updated `DecisionService.record_decision()` to accept `dependency_decision_ids` for recording influence relationships during decision creation, populating the influence DAG. - Added `DecisionService.get_influence_edges()` to retrieve the influence DAG as an adjacency list. - All public `CorrectionService` methods (`analyze_impact`, `execute_revert`, `execute_correction`, `generate_dry_run_report`) now accept an optional `influence_edges` parameter (backward-compatible, defaults to `None`). ## Key Design Decisions - **Single BFS pass over union of edges**: Rather than separate traversals for structural tree and influence DAG, one BFS pass unions both edge sources. This ensures O(V+E) complexity and consistent visit order. - **Cycle detection via visited set**: The visited set prevents revisiting nodes. A warning is logged when a cycle is detected (indicating data corruption), but the BFS terminates cleanly. - **Influence edge logging**: Traversal emits count of influence edges processed for observability. - **Backward-compatible API**: Existing callers that only pass `decision_tree` without `influence_edges` continue to work identically. ## Test Results - **Behave BDD**: 257 features passed, 8145 scenarios passed, 31446 steps passed — 0 failures, 0 errors - **Robot Framework**: 1120 passed, 23 failed (all 23 failures are pre-existing, unrelated to this change; our 6 new tests all pass) - **Coverage**: 97.0% (threshold: 97%) - **Lint**: All checks passed (ruff) - **Typecheck**: 0 errors, 0 warnings (pyright strict) ## Files Changed - `src/cleveragents/application/services/correction_service.py` — Extended `_compute_affected_subtree()` and public method signatures - `src/cleveragents/application/services/decision_service.py` — Added `dependency_decision_ids`, `_record_dependencies()`, `get_influence_edges()` - `features/influence_dag_traversal.feature` — 11 BDD scenarios - `features/steps/influence_dag_traversal_steps.py` — Step implementations - `robot/influence_dag_traversal.robot` — 6 Robot Framework integration tests - `robot/helper_influence_dag_traversal.py` — Robot helper script - `benchmarks/influence_dag_bench.py` — ASV benchmarks for traversal performance - `CHANGELOG.md` — Changelog entry Closes #542

Rows
Columns