Skip to content

πŸ’« Toolkit to help you get started with SDD or any other process!

18.8 KB
Raw Blame
"""Pure-function merge engine for workflow step lists."""

from __future__ import annotations

import copy
from dataclasses import dataclass
from typing import Any

from .schema import VALID_OPERATIONS, Overlay, OverlayEdit


@dataclass(frozen=True)
class ComposedStep:
    """Attribution tracking for a single composed step."""

    step_id: str
    source: str


@dataclass(frozen=True)
class OverlayLayer:
    """An overlay together with its layer source for attribution."""

    overlay: Overlay
    source: str


# Nested step keys that may contain a list of steps.
_NESTED_LIST_KEYS = ("then", "else", "steps", "default")


def find_step(
    steps: list[dict[str, Any]], step_id: str
) -> tuple[list[dict[str, Any]], int] | None:
    """Recursively locate a step by ID and return its (parent_list, index).

    Searches flat lists and nested lists inside ``then``, ``else``, ``steps``,
    ``default``, and ``cases.*``.  Does *not* descend into ``fan-out`` template
    steps because those are runtime-multiplied stamps, not uniquely-addressable
    nodes.
    """
    for i, step in enumerate(steps):
        if not isinstance(step, dict):
            continue
        if step.get("id") == step_id:
            return (steps, i)
        for key in _NESTED_LIST_KEYS:
            nested = step.get(key)
            if isinstance(nested, list):
                result = find_step(nested, step_id)
                if result is not None:
                    return result
        cases = step.get("cases")
        if isinstance(cases, dict):
            for case_steps in cases.values():
                if isinstance(case_steps, list):
                    result = find_step(case_steps, step_id)
                    if result is not None:
                        return result
    return None


def _all_base_step_ids(steps: list[dict[str, Any]]) -> set[str]:
    """Collect all step IDs reachable in a step tree (excluding fan-out templates)."""
    ids: set[str] = set()
    for step in steps:
        if not isinstance(step, dict):
            continue
        step_id = step.get("id")
        if isinstance(step_id, str):
            ids.add(step_id)
        for key in _NESTED_LIST_KEYS:
            nested = step.get(key)
            if isinstance(nested, list):
                ids.update(_all_base_step_ids(nested))
        cases = step.get("cases")
        if isinstance(cases, dict):
            for case_steps in cases.values():
                if isinstance(case_steps, list):
                    ids.update(_all_base_step_ids(case_steps))
    return ids


def _descendant_ids(step: dict[str, Any]) -> set[str]:
    """Return all step IDs nested inside *step* (not including *step* itself)."""
    ids: set[str] = set()
    for key in _NESTED_LIST_KEYS:
        nested = step.get(key)
        if isinstance(nested, list):
            ids.update(_all_base_step_ids(nested))
    cases = step.get("cases")
    if isinstance(cases, dict):
        for case_steps in cases.values():
            if isinstance(case_steps, list):
                ids.update(_all_base_step_ids(case_steps))
    return ids


def _check_anchor_conflicts(
    anchor_operations: dict[str, str],
    base_steps: list[dict[str, Any]],
) -> list[str]:
    """Return error messages for anchor pairs where one is an ancestor of the other.

    Only flags conflicts where the ancestor's winning edit is ``replace`` or
    ``remove`` β€” operations that destroy the subtree and make any descendant
    anchor unresolvable.  Pure insert operations on an ancestor leave it intact,
    so its descendants remain reachable regardless of processing order.

    Callers should raise on any returned errors before mutating the step tree.
    """
    errors: list[str] = []
    for anchor, operation in sorted(anchor_operations.items()):
        if operation in ("insert_after", "insert_before"):
            # Inserts leave the ancestor step intact; descendants are unaffected.
            continue
        location = find_step(base_steps, anchor)
        if location is None:
            continue  # missing anchors are reported by validate_edits
        parent_list, idx = location
        step = parent_list[idx]
        conflicting = set(anchor_operations.keys()) & _descendant_ids(step)
        for child_anchor in sorted(conflicting):
            errors.append(
                f"Anchor conflict: '{anchor}' is an ancestor of '{child_anchor}'. "
                "Targeting both anchors in the same overlay set produces "
                "order-dependent results; restructure edits to avoid nesting."
            )
    return errors


def _init_sources_recursively(
    steps: list[dict[str, Any]], sources: dict[str, str]
) -> None:
    """Initialize attribution sources for all base steps, recursively."""
    for step in steps:
        if not isinstance(step, dict):
            continue
        step_id = step.get("id")
        if isinstance(step_id, str):
            sources[step_id] = "base"
        for key in _NESTED_LIST_KEYS:
            nested = step.get(key)
            if isinstance(nested, list):
                _init_sources_recursively(nested, sources)
        cases = step.get("cases")
        if isinstance(cases, dict):
            for case_steps in cases.values():
                if isinstance(case_steps, list):
                    _init_sources_recursively(case_steps, sources)


def _record_sources_recursively(
    step: dict[str, Any],
    source: str,
    sources: dict[str, str],
) -> None:
    """Record *source* for a step and all its nested child steps.

    Traverses ``then``, ``else``, ``steps``, ``default``, and ``cases.*``
    so that ``workflow resolve`` attributes every step inside a composite
    insert or replacement to the correct overlay layer.
    """
    step_id = step.get("id")
    if isinstance(step_id, str):
        sources[step_id] = source
    for key in _NESTED_LIST_KEYS:
        nested = step.get(key)
        if isinstance(nested, list):
            for child in nested:
                if isinstance(child, dict):
                    _record_sources_recursively(child, source, sources)
    cases = step.get("cases")
    if isinstance(cases, dict):
        for case_steps in cases.values():
            if isinstance(case_steps, list):
                for child in case_steps:
                    if isinstance(child, dict):
                        _record_sources_recursively(child, source, sources)


def _remove_sources_recursively(
    step: dict[str, Any],
    sources: dict[str, str],
) -> None:
    """Remove source entries for a step and all its nested child steps.

    Traverses the same nesting keys as ``_record_sources_recursively``.
    """
    step_id = step.get("id")
    if isinstance(step_id, str) and sources.get(step_id) == "base":
        sources.pop(step_id, None)
    for key in _NESTED_LIST_KEYS:
        nested = step.get(key)
        if isinstance(nested, list):
            for child in nested:
                if isinstance(child, dict):
                    _remove_sources_recursively(child, sources)
    cases = step.get("cases")
    if isinstance(cases, dict):
        for case_steps in cases.values():
            if isinstance(case_steps, list):
                for child in case_steps:
                    if isinstance(child, dict):
                        _remove_sources_recursively(child, sources)



def _build_attribution(
    steps: list[dict[str, Any]],
    sources: dict[str, str],
) -> list[ComposedStep]:
    """Build an ordered attribution list from the composed step tree."""
    result: list[ComposedStep] = []
    for step in steps:
        if not isinstance(step, dict):
            continue
        step_id = step.get("id")
        if isinstance(step_id, str):
            result.append(ComposedStep(step_id, sources.get(step_id, "unknown")))
        for key in _NESTED_LIST_KEYS:
            nested = step.get(key)
            if isinstance(nested, list):
                result.extend(_build_attribution(nested, sources))
        cases = step.get("cases")
        if isinstance(cases, dict):
            for case_steps in cases.values():
                if isinstance(case_steps, list):
                    result.extend(_build_attribution(case_steps, sources))
    return result


def _winning_fate_edit(
    edits: list[tuple[OverlayLayer, OverlayEdit]],
) -> tuple[OverlayLayer, OverlayEdit] | None:
    """Return the edit that decides an anchor's fate.

    Normally that is simply the last edit in merge order. The exception this
    helper exists for: when the last edit is an ``insert_*``, the same overlay
    may *also* have declared a ``replace`` on the anchor earlier in the file.
    Declaration order inside one overlay is not a precedence signal -- priority
    is a per-overlay property -- so the trailing insert must not cancel that
    overlay's own replacement, which previously reverted the anchor to the base
    step and discarded the replacement silently.

    A ``replace`` leaves the anchor in place, so both edits can be honoured.
    ``remove`` is deliberately NOT rescued here: it destroys the anchor, so an
    insert relative to it cannot also apply, and choosing between them is a
    separate question. That combination keeps its existing behaviour.

    For the same reason the rescue applies only to an *unambiguous*
    replace-plus-insert layer. If the winning layer also declared a ``remove``
    on this anchor, the layer is asking for two incompatible fates and picking
    one is that same separate question -- so the previous trailing-insert
    outcome is preserved and such layers stay byte-identical to their
    pre-rescue behaviour.

    Returns ``None`` only when there are no edits.
    """
    if not edits:
        return None
    winning_layer, last_edit = edits[-1]
    if last_edit.operation not in ("insert_after", "insert_before"):
        return edits[-1]
    replacement: tuple[OverlayLayer, OverlayEdit] | None = None
    for layer, edit in edits:
        if layer is not winning_layer:
            continue
        if edit.operation == "remove":
            # Ambiguous layer (replace *and* remove on one anchor): leave the
            # pre-existing trailing-insert fate untouched.
            return edits[-1]
        if edit.operation == "replace":
            replacement = (layer, edit)
    return replacement if replacement is not None else edits[-1]


def _traverse_and_apply(
    steps: list[dict[str, Any]],
    edits_by_anchor: dict[str, list[tuple[OverlayLayer, OverlayEdit]]],
    sources: dict[str, str],
) -> list[dict[str, Any]]:
    """Walk the original step tree and apply overlay edits as each step is encountered.

    Edits are always resolved against the *original* structure β€” this function
    traverses the unmodified list passed in, so a replacement step's new ID can
    never be mistaken for a base anchor.  Nested lists (``then``, ``else``, etc.)
    are recursed into only for steps that survive the edit (not for replaced
    steps).

    *edits* are expected to be in merge order (lowest priority first, highest
    priority last). The winning edit for each anchor is chosen by
    ``_winning_fate_edit`` -- normally ``edits[-1]``, except that a trailing
    ``insert_*`` does not cancel a ``replace`` declared earlier by that same
    overlay. Go through that helper rather than reading ``edits[-1]`` directly.
    """
    result: list[dict[str, Any]] = []

    for step in steps:
        if not isinstance(step, dict):
            result.append(step)
            continue

        step_id = step.get("id")
        edits = edits_by_anchor.get(step_id, []) if isinstance(step_id, str) else []
        fate = _winning_fate_edit(edits)
        winning_edit = fate[1] if fate is not None else None

        if winning_edit is not None and winning_edit.operation == "remove":
            # Winning edit removes this step; ignore all other edits on this anchor.
            # Do NOT call _remove_sources_recursively here: _build_attribution only
            # traverses the result list, so stale sources entries for removed steps
            # are never read.  Calling it would incorrectly pop the attribution of a
            # *surviving* step that reuses the same ID (e.g. a replacement step
            # introduced by a higher-priority overlay targeting a different anchor).
            continue

        # Insert before (in merge order).
        for layer, edit in edits:
            if edit.operation == "insert_before":
                new_step = copy.deepcopy(edit.step)
                _record_sources_recursively(new_step, layer.source, sources)
                result.append(new_step)

        if winning_edit is not None and winning_edit.operation == "replace":
            winning_layer = fate[0]
            new_step = copy.deepcopy(winning_edit.step)
            _remove_sources_recursively(step, sources)
            _record_sources_recursively(new_step, winning_layer.source, sources)
            result.append(new_step)
        else:
            # No replacement: keep this step and recurse into its nested lists.
            for key in _NESTED_LIST_KEYS:
                nested = step.get(key)
                if isinstance(nested, list):
                    step[key] = _traverse_and_apply(nested, edits_by_anchor, sources)
            cases = step.get("cases")
            if isinstance(cases, dict):
                for case_key, case_steps in cases.items():
                    if isinstance(case_steps, list):
                        cases[case_key] = _traverse_and_apply(case_steps, edits_by_anchor, sources)
            result.append(step)

        # Insert after: higher-priority overlays land closer to the anchor
        # (reversed merge order), but a single overlay's own inserts must keep
        # their declared order β€” mirroring the forward insert_before loop above.
        # Reversing the whole flat list would also flip an overlay's own edits,
        # so group contiguous same-layer edits and reverse the GROUP order only.
        after_groups: list[list[tuple[OverlayLayer, OverlayEdit]]] = []
        for layer, edit in edits:
            if edit.operation != "insert_after":
                continue
            if after_groups and after_groups[-1][0][0] is layer:
                after_groups[-1].append((layer, edit))
            else:
                after_groups.append([(layer, edit)])
        for group in reversed(after_groups):
            for layer, edit in group:
                new_step = copy.deepcopy(edit.step)
                _record_sources_recursively(new_step, layer.source, sources)
                result.append(new_step)

    return result


def merge_steps(
    base_steps: list[dict[str, Any]],
    overlays: list[OverlayLayer],
) -> tuple[list[dict[str, Any]], list[ComposedStep]]:
    """Apply overlays to base steps in merge order and return composed steps.

    *overlays* is expected to be sorted by merge order (lowest priority first,
    highest priority last).  The returned step list is a deep copy of the base;
    base_steps is never mutated.

    Higher-wins semantics are enforced for edits that target the same base
    anchor: the highest-priority edit (last in *overlays*) decides the fate of
    the anchor.  A lower-priority ``remove`` cannot prevent a higher-priority
    ``replace`` or ``insert_*`` on the same anchor.
    """
    steps = copy.deepcopy(base_steps)
    sources: dict[str, str] = {}
    _init_sources_recursively(steps, sources)

    # Group edits by anchor, preserving merge order.
    edits_by_anchor: dict[str, list[tuple[OverlayLayer, OverlayEdit]]] = {}
    for layer in overlays:
        for edit in layer.overlay.edits:
            edits_by_anchor.setdefault(edit.anchor, []).append((layer, edit))

    # Raise early for non-remove edits that target anchors not present in the base.
    # Overlays always apply to the original tree; they cannot target steps introduced
    # by other overlays.
    base_ids = _all_base_step_ids(base_steps)
    for anchor, anchor_edits in edits_by_anchor.items():
        winning_op = anchor_edits[-1][1].operation
        if winning_op != "remove" and anchor not in base_ids:
            raise ValueError(f"Anchor '{anchor}' not found in workflow steps.")

    # Reject edits that target anchors with a parent/descendant relationship when
    # the ancestor edit replaces or removes its subtree β€” those produce
    # order-dependent results.  Pure insert edits on an ancestor are safe because
    # the ancestor step (and its descendants) remain intact.
    # Must agree with ``_traverse_and_apply``: use the same fate rule, or the
    # conflict guard stops firing for a subtree that is in fact replaced.
    # Every anchor stays in the mapping even when its fate is a pure insert --
    # ``_check_anchor_conflicts`` reads the key set to find *descendant*
    # anchors, so dropping insert-only anchors would stop conflicts being
    # detected against them.
    anchor_winning_ops = {}
    for anchor, anchor_edits in edits_by_anchor.items():
        anchor_fate = _winning_fate_edit(anchor_edits)
        anchor_winning_ops[anchor] = (
            anchor_fate[1].operation
            if anchor_fate is not None
            else anchor_edits[-1][1].operation
        )
    anchor_conflicts = _check_anchor_conflicts(anchor_winning_ops, base_steps)
    if anchor_conflicts:
        raise ValueError(
            "Overlay anchor conflict(s) detected:\n  - " + "\n  - ".join(anchor_conflicts)
        )

    # Apply all overlay edits via a single-pass traversal of the original tree.
    # Each edit is resolved against the original step structure, so a replacement
    # step's new ID can never be mistaken for a base anchor in a later edit group.
    result = _traverse_and_apply(steps, edits_by_anchor, sources)

    attribution = _build_attribution(result, sources)
    return result, attribution


def validate_edits(
    edits: list[OverlayEdit],
    base_step_ids: set[str],
) -> list[str]:
    """Validate overlay edits against a set of known base step IDs.

    Returns a list of human-readable error messages.  Does not raise.
    """
    errors: list[str] = []
    for idx, edit in enumerate(edits):
        if edit.operation not in VALID_OPERATIONS:
            errors.append(f"Edit {idx}: invalid operation {edit.operation!r}.")
            continue
        if edit.anchor not in base_step_ids:
            errors.append(
                f"Edit {idx}: anchor '{edit.anchor}' does not match any base step id."
            )
        if edit.operation == "remove":
            if edit.step is not None:
                errors.append(f"Edit {idx}: 'remove' must not include a step.")
            continue
        if not isinstance(edit.step, dict):
            errors.append(f"Edit {idx}: '{edit.operation}' requires a step mapping.")
            continue
        step_id = edit.step.get("id")
        if not isinstance(step_id, str) or not step_id:
            errors.append(f"Edit {idx}: step is missing required 'id'.")
            continue
        if ":" in step_id:
            errors.append(
                f"Edit {idx}: step id {step_id!r} contains ':' which is reserved "
                "for engine-generated nested IDs."
            )
    return errors