refactor(recipe): add maximal leaf candidate selection to overlay resolver#496
Merged
yuanchen8911 merged 1 commit intoApr 6, 2026
Conversation
yuanchen8911
force-pushed
the
refactor/maximal-leaf-candidate-selection
branch
2 times, most recently
from
869f74f to
e8e511b
Compare
mchmarny
requested changes
Apr 6, 2026
mchmarny
left a comment
mchmarny
left a comment
Member
There was a problem hiding this comment.
Clean implementation — algorithm is correct and the behavior change is well-documented. One blocker (missing observability on the filter) and two small nits inline.
yuanchen8911
force-pushed
the
refactor/maximal-leaf-candidate-selection
branch
from
e8e511b to
9fde20c
Compare
Contributor
Author
|
All three items addressed:
All tests pass with @mchmarny — ready for another look. |
yuanchen8911
force-pushed
the
refactor/maximal-leaf-candidate-selection
branch
from
77819a6 to
b14b49f
Compare
…gOverlays Add filterToMaximalLeaves() to FindMatchingOverlays that removes any matching overlay that is an ancestor (via spec.base chain) of another matching overlay. Only the most-specific leaves survive as candidates; their full inheritance chains are still resolved during merging. This is a shared semantic change under both BuildRecipeResult and BuildRecipeResultWithEvaluator — both use FindMatchingOverlays as the entry point for candidate selection. Evaluator behavior change: with maximal leaf selection, ancestor overlays are no longer independent candidates. When a leaf's constraints fail evaluation, the entire candidate is excluded — ancestors do not silently fill in as fallback candidates. The result falls back to base-only output plus any other non-excluded leaf candidates. The current overlay tree is linear (every matching overlay is an ancestor of the most-specific leaf), so this is a no-op for existing recipes. It becomes load-bearing when composition mechanisms (mixins, intermediates) introduce overlays at the same specificity level. Add unit tests for the maximal leaf filter, a characterization test that verifies all leaf overlays discovered from recipes/overlays/ produce identical hydrated content through both build paths, and a failing-leaf test that verifies excluded candidates do not include ancestors. Signed-off-by: Yuan Chen <[email protected]>
yuanchen8911
force-pushed
the
refactor/maximal-leaf-candidate-selection
branch
from
b14b49f to
25762ee
Compare
mchmarny
approved these changes
Apr 6, 2026
This was referenced Apr 7, 2026
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Summary
Add maximal leaf candidate selection to
FindMatchingOverlays— filter out any matching overlay that is an ancestor (viaspec.basechain) of another matching overlay. Only the most-specific leaves survive as candidates.Motivation / Context
The overlay resolver currently applies all matching overlays independently, then expands each match's inheritance chain. This works correctly with the current linear tree structure, but breaks when composition mechanisms (mixins, intermediates) introduce overlays at the same specificity level — ancestor overlays compete with their descendants, producing non-deterministic merge results.
This is Phase 2 of the revised ADR-005 (#439): stabilize resolver semantics before adding composition abstractions.
Fixes: N/A
Related: #439, #305, #492, #493
Type of Change
Component(s) Affected
cmd/aicr,pkg/cli)cmd/aicrd,pkg/api,pkg/server)pkg/recipe)pkg/bundler,pkg/component/*)pkg/collector,pkg/snapshotter)pkg/validator)pkg/errors,pkg/k8s)docs/,examples/)Implementation Notes
filterToMaximalLeaves()is a shared helper called byFindMatchingOverlays, which is the entry point for bothBuildRecipeResultandBuildRecipeResultWithEvaluator. This ensures consistent candidate selection regardless of call site.The filter builds a set of all ancestors of matching overlays by walking each match's
spec.basechain (with cycle detection), then removes any match whose name appears in that ancestor set.Evaluator behavior change: With maximal leaf selection, ancestor overlays are no longer independent candidates in
BuildRecipeResultWithEvaluator. When a leaf's constraints fail evaluation, the entire candidate is excluded — ancestors do not silently fill in as fallback candidates. The result falls back to base plus any other non-excluded leaf candidates (e.g.,monitoring-hpawhich matchesintent: anyand is not an ancestor of any other overlay). This is intentional and covered byTestEvaluatorFailingLeafExcludesCandidate.Current tree impact: The existing overlay tree is linear — every matching overlay is an ancestor of the most-specific leaf. For
BuildRecipeResult(no evaluator), the filter is a no-op: hydrated recipe content is unchanged for all current overlays. ForBuildRecipeResultWithEvaluator, the fallback behavior changes as described above, but this path is only exercised when constraints fail against a snapshot.appliedOverlaysmetadata change: 3 of 28 overlay combinations show minor ordering shifts in theappliedOverlayslist. Hydrated recipe content is unchanged.Testing
filterToMaximalLeaves: ancestor filtering with cycle detection, multiple branches, single matchrecipes/overlays/produce identical hydrated content through bothBuildRecipeResultandBuildRecipeResultWithEvaluator(pass-all evaluator)monitoring-hparemains applied as independent non-ancestor leafRisk Assessment
Rollout notes: The evaluator-path fallback behavior changes: when a leaf fails constraint evaluation, its ancestors no longer appear as independent candidates. This only affects
BuildRecipeResultWithEvaluatorwhen constraints fail. Revert by removing thefilterToMaximalLeavescall inFindMatchingOverlays.Checklist
make testwith-race)make lint)git commit -S) — GPG signing info