Skip to main content

dsl_kit_core/
lib.rs

1//! Engine primitives for `dsl-kit` (v3 engine shape).
2//!
3//! This crate defines the observable primitives every DSL built with the
4//! kit carries: stable node identifiers, call frame identifiers with
5//! depth, iteration counters, root-to-node paths, an event stream, the
6//! `Stepper` trait modelling evaluation as an externally-driven state
7//! machine, an AST traversal contract, and structured errors that always
8//! carry the location at which the error happened.
9//!
10//! ## v3 shape (Round 13)
11//!
12//! - `Stepper` is a sync trait; async is a host concern. Interpretation is
13//!   observable, steppable, and supports first-class fan-out with structured
14//!   join through `Par` frames.
15//! - Suspensions are identified by `SuspensionId` and can be N-in-flight;
16//!   the host resolves each with `Ok(Value)` or `Err(EffectError)`.
17//! - Fan-out is expressed by a `Par` frame with a `JoinPolicy` (shape +
18//!   fail); reducers fold the collected slots into the parent value.
19//! - Cancellation is cooperative; the host drains cancelled ids via
20//!   `take_cancellations()` and looks them up in its own runtime-handle
21//!   map.
22//!
23//! The full behavioural specification lives in the rustdoc of
24//! [`Engine`], [`Stepper`], and the item-level contracts they link.
25
26#![warn(missing_docs)]
27
28// Re-exported for `#[derive(DslExec)]`-generated code (`Call` payload
29// construction); not part of the public API surface.
30#[doc(hidden)]
31pub use serde_json;
32
33use std::borrow::Cow;
34use std::collections::HashMap;
35use std::fmt;
36use std::sync::Arc;
37use std::sync::atomic::{AtomicU64, Ordering};
38
39mod drive;
40mod engine;
41pub mod suggest;
42pub use drive::{AsyncEffectResolver, DriveOutcome, EffectResolver, drive, drive_async};
43pub use engine::{Ast, Engine, ExecError, LoopDecision, NodeKind};
44pub use suggest::{
45    Applicability, FixSuggestion, NoopSuggester, PatchPart, Suggester, SuggesterHandle, Suggestion,
46    noop_handle,
47};
48
49// ---------- Observation primitives --------------------------------------
50
51/// Stable identifier assigned to every AST node when the tree is built.
52///
53/// A `NodeId` is orthogonal to source location: two nodes at the same
54/// source span but in different expansions carry different IDs, and the
55/// same node retains its ID across evaluation runs.
56#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
57pub struct NodeId(pub u64);
58
59impl fmt::Display for NodeId {
60    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
61        write!(f, "n{}", self.0)
62    }
63}
64
65/// Identifier for a single activation of a function-like node.
66#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
67pub struct CallFrameId(pub u64);
68
69impl fmt::Display for CallFrameId {
70    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
71        write!(f, "f{}", self.0)
72    }
73}
74
75/// Position within the current iteration of a loop-shaped node.
76#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
77pub struct Iteration(pub u64);
78
79/// Root-to-node identifier chain, usable for path-shaped breakpoint
80/// conditions.
81#[derive(Debug, Clone, PartialEq, Eq, Hash, Default)]
82pub struct Path(pub Vec<NodeId>);
83
84impl Path {
85    /// Returns an empty path (i.e. the root).
86    #[inline]
87    pub fn root() -> Self {
88        Path(Vec::new())
89    }
90
91    /// Returns a new path with `node` pushed onto the end.
92    pub fn push(&self, node: NodeId) -> Self {
93        let mut next = self.0.clone();
94        next.push(node);
95        Path(next)
96    }
97
98    /// Depth of the path (number of node IDs).
99    #[inline]
100    pub fn depth(&self) -> usize {
101        self.0.len()
102    }
103
104    /// Returns the node ID at the tip of the path, if any.
105    pub fn tip(&self) -> Option<NodeId> {
106        self.0.last().copied()
107    }
108}
109
110impl fmt::Display for Path {
111    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
112        if self.0.is_empty() {
113            return write!(f, "/");
114        }
115        for id in &self.0 {
116            write!(f, "/{id}")?;
117        }
118        Ok(())
119    }
120}
121
122/// Monotonic ID generator for nodes and call frames.
123#[derive(Debug, Default)]
124pub struct IdGen {
125    next: AtomicU64,
126}
127
128impl IdGen {
129    /// Creates a fresh generator initialised at zero.
130    pub const fn new() -> Self {
131        Self {
132            next: AtomicU64::new(0),
133        }
134    }
135
136    /// Allocates a fresh `NodeId`.
137    pub fn node(&self) -> NodeId {
138        NodeId(self.next.fetch_add(1, Ordering::Relaxed))
139    }
140
141    /// Allocates a fresh `CallFrameId`.
142    pub fn frame(&self) -> CallFrameId {
143        CallFrameId(self.next.fetch_add(1, Ordering::Relaxed))
144    }
145}
146
147/// Location context attached to every emitted event and to every error.
148#[derive(Debug, Clone, PartialEq, Eq)]
149pub struct NodeContext {
150    /// The node currently being evaluated.
151    pub node: NodeId,
152    /// The root-to-node path leading to `node`.
153    pub path: Path,
154    /// The active call frame, if any.
155    pub frame: Option<CallFrameId>,
156    /// Depth of the current call / evaluation stack.
157    pub depth: u32,
158    /// Iteration counter when the surrounding node is loop-shaped.
159    pub iteration: Option<Iteration>,
160}
161
162impl NodeContext {
163    /// Builds a context for a node visited without any active frame.
164    pub fn at(node: NodeId, path: Path) -> Self {
165        Self {
166            node,
167            path,
168            frame: None,
169            depth: 0,
170            iteration: None,
171        }
172    }
173}
174
175impl fmt::Display for NodeContext {
176    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
177        write!(f, "{}", self.node)?;
178        if let Some(frame) = self.frame {
179            write!(f, " (frame {}, depth {})", frame, self.depth)?;
180        }
181        if let Some(it) = self.iteration {
182            write!(f, " iter {}", it.0)?;
183        }
184        write!(f, " at {}", self.path)
185    }
186}
187
188// ---------- Suspension identity ----------------------------------------
189
190/// Stable identifier for one in-flight suspension.
191///
192/// Allocated by the engine when a `Frame::PendingEffect` leaf is created.
193/// The host uses it as the key on [`Stepper::resolve`] and as the map key
194/// for its own `SuspensionId -> runtime handle` bookkeeping when
195/// cooperative cancellation is required. Monotonic within one `Stepper`
196/// instance; never reused, even after cancellation.
197#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
198pub struct SuspensionId(pub u64);
199
200impl fmt::Display for SuspensionId {
201    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
202        write!(f, "s{}", self.0)
203    }
204}
205
206/// One live suspension.
207#[derive(Debug, Clone)]
208pub struct Pending {
209    /// Stable identifier.
210    pub id: SuspensionId,
211    /// Why the engine yielded.
212    pub reason: SuspendReason,
213    /// Where the suspension happened.
214    pub at: NodeContext,
215}
216
217// ---------- Suspend reason ---------------------------------------------
218
219/// Why the engine yielded control.
220///
221/// Cancellation runtime handles are NOT stored here — the host maintains
222/// its own `SuspensionId -> handle` map.
223#[derive(Debug, Clone)]
224#[non_exhaustive]
225pub enum SuspendReason {
226    /// A first-class external effect (LLM call, tool invocation, …).
227    Call {
228        /// Host-defined effect descriptor.
229        spec: CallSpec,
230    },
231    /// A registered breakpoint fired.
232    Breakpoint,
233    /// The scheduler chose to yield cooperatively.
234    Cooperative,
235    /// Host-defined effect the DSL wants to model beyond `Call`.
236    User {
237        /// Short tag identifying the effect kind.
238        tag: Cow<'static, str>,
239    },
240}
241
242impl fmt::Display for SuspendReason {
243    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
244        match self {
245            SuspendReason::Call { spec } => write!(f, "call({})", spec.label),
246            SuspendReason::Breakpoint => write!(f, "breakpoint"),
247            SuspendReason::Cooperative => write!(f, "cooperative"),
248            SuspendReason::User { tag } => write!(f, "user({tag})"),
249        }
250    }
251}
252
253/// Host-defined effect descriptor. Opaque to the engine.
254#[derive(Debug, Clone)]
255pub struct CallSpec {
256    /// Short human-readable label (also fed into the DSL's canned
257    /// responses when applicable).
258    pub label: String,
259    /// Effect payload; the engine stores it verbatim and the host
260    /// interprets it per the DSL's semantics.
261    pub payload: serde_json::Value,
262}
263
264// ---------- Event stream -----------------------------------------------
265
266/// One observation from the evaluator.
267#[derive(Debug, Clone)]
268#[non_exhaustive]
269pub enum Event {
270    /// Emitted before a node's semantics run.
271    VisitPre {
272        /// Where the observation happened.
273        at: NodeContext,
274    },
275    /// Emitted after a node's semantics complete.
276    VisitPost {
277        /// Where the observation happened.
278        at: NodeContext,
279    },
280    /// A function-like node started a new call frame.
281    FrameEnter {
282        /// Where the observation happened.
283        at: NodeContext,
284    },
285    /// A function-like node's frame ended.
286    FrameLeave {
287        /// Where the observation happened.
288        at: NodeContext,
289    },
290    /// A loop node advanced to a new iteration.
291    IterationTick {
292        /// Where the observation happened.
293        at: NodeContext,
294    },
295    /// The stepper is about to yield to the outside world.
296    Suspend {
297        /// Where the observation happened.
298        at: NodeContext,
299        /// Why the stepper is yielding.
300        reason: SuspendReason,
301    },
302    /// The stepper resumed after a yield.
303    Resume {
304        /// Where the observation happened.
305        at: NodeContext,
306    },
307    /// A suspension was cancelled (tracer convenience; the authoritative
308    /// channel is [`Stepper::take_cancellations`]).
309    Cancel {
310        /// The cancelled suspension.
311        id: SuspensionId,
312    },
313}
314
315/// Sink for the event stream.
316pub trait EventSink {
317    /// Consumes one event.
318    fn emit(&mut self, event: &Event);
319}
320
321/// A no-op sink useful for tests and for evaluators that do not need
322/// observation.
323#[derive(Debug, Default)]
324pub struct NullSink;
325
326impl EventSink for NullSink {
327    #[inline]
328    fn emit(&mut self, _event: &Event) {}
329}
330
331/// Silent event sink that counts each event kind.
332///
333/// Used by the engine as its default observation channel so hosts
334/// can inspect basic activity without wiring a custom sink.
335#[derive(Debug, Default, Clone, Copy)]
336pub struct CountingSink {
337    /// Number of `VisitPre` events observed.
338    pub visit_pre: u32,
339    /// Number of `VisitPost` events observed.
340    pub visit_post: u32,
341    /// Number of `FrameEnter` events observed.
342    pub frame_enter: u32,
343    /// Number of `FrameLeave` events observed.
344    pub frame_leave: u32,
345    /// Number of `IterationTick` events observed.
346    pub iteration_tick: u32,
347    /// Number of `Suspend` events observed.
348    pub suspend: u32,
349    /// Number of `Resume` events observed.
350    pub resume: u32,
351}
352
353impl EventSink for CountingSink {
354    fn emit(&mut self, event: &Event) {
355        match event {
356            Event::VisitPre { .. } => self.visit_pre += 1,
357            Event::VisitPost { .. } => self.visit_post += 1,
358            Event::FrameEnter { .. } => self.frame_enter += 1,
359            Event::FrameLeave { .. } => self.frame_leave += 1,
360            Event::IterationTick { .. } => self.iteration_tick += 1,
361            Event::Suspend { .. } => self.suspend += 1,
362            Event::Resume { .. } => self.resume += 1,
363            _ => {}
364        }
365    }
366}
367
368impl CountingSink {
369    /// Returns a single-line human-readable event histogram.
370    pub fn summarise(&self) -> String {
371        format!(
372            "pre={} post={} frame_enter={} frame_leave={} iter={} suspend={} resume={}",
373            self.visit_pre,
374            self.visit_post,
375            self.frame_enter,
376            self.frame_leave,
377            self.iteration_tick,
378            self.suspend,
379            self.resume,
380        )
381    }
382}
383
384/// Recording event sink that keeps every observed [`Event`] in order.
385///
386/// Complements [`CountingSink`] (built-in on `Engine`) by preserving the
387/// full event history for downstream inspection — debuggers, tracers,
388/// test assertions, etc. Attach one to an engine via
389/// `Engine::attach_sink` and drain / snapshot it between mutations.
390#[derive(Debug, Default, Clone)]
391pub struct BufferingSink {
392    events: Vec<Event>,
393}
394
395impl BufferingSink {
396    /// Creates an empty, unbounded buffer.
397    pub fn new() -> Self {
398        Self { events: Vec::new() }
399    }
400
401    /// Creates an empty buffer with pre-allocated capacity `cap`.
402    ///
403    /// The buffer is still logically unbounded; `cap` is only a
404    /// hint to avoid early re-allocations.
405    pub fn with_capacity(cap: usize) -> Self {
406        Self {
407            events: Vec::with_capacity(cap),
408        }
409    }
410
411    /// Returns a slice view of the recorded events without draining.
412    pub fn snapshot(&self) -> &[Event] {
413        &self.events
414    }
415
416    /// Takes every recorded event and clears the buffer.
417    pub fn drain(&mut self) -> Vec<Event> {
418        std::mem::take(&mut self.events)
419    }
420
421    /// Discards every recorded event without returning them.
422    pub fn clear(&mut self) {
423        self.events.clear();
424    }
425
426    /// Number of recorded events currently held.
427    pub fn len(&self) -> usize {
428        self.events.len()
429    }
430
431    /// True when no events are held.
432    pub fn is_empty(&self) -> bool {
433        self.events.is_empty()
434    }
435}
436
437impl EventSink for BufferingSink {
438    fn emit(&mut self, event: &Event) {
439        self.events.push(event.clone());
440    }
441}
442
443// ---------- Errors ------------------------------------------------------
444
445/// Structured error type for engine and evaluator failures.
446///
447/// Every applicable variant carries a [`NodeContext`] or a
448/// [`SuspensionId`] / [`ReducerId`] so that error messages, MCP tool
449/// responses, and log lines can always answer "at which node / for
450/// which id did this happen?". Diagnostic codes are stable,
451/// machine-readable identifiers under the `dsl_kit::` namespace.
452#[derive(Debug, thiserror::Error, miette::Diagnostic)]
453#[non_exhaustive]
454pub enum EngineError {
455    /// The evaluator explicitly aborted the current step.
456    #[error("evaluation aborted at {at}: {reason}")]
457    #[diagnostic(
458        code(dsl_kit::eval::aborted),
459        help(
460            "The interpreter returned an `Aborted` outcome. Inspect the reason and the node context to locate the abort site."
461        )
462    )]
463    Aborted {
464        /// Where the abort happened.
465        at: NodeContext,
466        /// Why the evaluator aborted.
467        reason: String,
468    },
469
470    /// A node's semantics returned an error.
471    #[error("evaluator failed at {at}")]
472    #[diagnostic(
473        code(dsl_kit::eval::failed),
474        help(
475            "The interpreter returned an error while evaluating this node. The `#[source]` chain points at the underlying failure."
476        )
477    )]
478    EvalFailed {
479        /// Where the failure happened.
480        at: NodeContext,
481        /// The underlying error returned by the interpreter.
482        #[source]
483        source: Box<dyn std::error::Error + Send + Sync>,
484    },
485
486    /// A traversal or stepper reached a node that was expected to have a
487    /// specific shape but did not.
488    #[error("malformed AST at {at}: {detail}")]
489    #[diagnostic(
490        code(dsl_kit::ast::malformed),
491        help(
492            "An AST invariant was violated. This usually means a hand-constructed tree omitted a required child."
493        )
494    )]
495    Malformed {
496        /// Where the invariant violation was detected.
497        at: NodeContext,
498        /// Human-readable description of the invariant that failed.
499        detail: String,
500    },
501
502    /// The host tried to resume a suspended stepper before it had suspended,
503    /// or resumed twice for a single suspension.
504    #[error("stepper protocol violation at {at}: {detail}")]
505    #[diagnostic(
506        code(dsl_kit::stepper::protocol),
507        help(
508            "The stepper's suspend/resume contract was broken. Each `PendingEffect` leaf must be resolved exactly once before further steps observe its value."
509        )
510    )]
511    StepperProtocol {
512        /// Where the protocol violation was detected.
513        at: NodeContext,
514        /// Human-readable description of the misuse.
515        detail: String,
516    },
517
518    /// The host called `resolve` with a `SuspensionId` the engine does
519    /// not know about (never created, already resolved, or belonging to
520    /// a cancelled leg). Hosts treat this as a benign no-op — it
521    /// happens routinely for cancelled effects whose external work
522    /// completes after abort.
523    #[error("unknown suspension {id}")]
524    #[diagnostic(
525        code(dsl_kit::stepper::unknown_suspension),
526        help(
527            "The host called resolve() with a SuspensionId the engine does not know. This is the expected outcome for a late response arriving after the effect's branch was cancelled."
528        )
529    )]
530    UnknownSuspension {
531        /// The unknown suspension id.
532        id: SuspensionId,
533    },
534
535    /// A `ParFrame` referenced a `ReducerId` that is not registered in
536    /// the active [`ReducerRegistry`].
537    #[error("unknown reducer {id:?}{hint}")]
538    #[diagnostic(
539        code(dsl_kit::reducer::unknown),
540        help(
541            "The ParFrame's reducer_id was not found in the ReducerRegistry. Register the reducer at Stepper build time or fix the AST to reference a known id."
542        )
543    )]
544    UnknownReducer {
545        /// The unknown reducer id.
546        id: ReducerId,
547        /// Optional `did you mean` hint produced by the registry's
548        /// injected [`Suggester`]. Empty when no suggester is wired
549        /// or no candidate scored above threshold, so the historical
550        /// `unknown reducer "X"` wording is preserved as the base
551        /// case.
552        hint: String,
553    },
554
555    /// An `Apply` node referenced an [`OpId`] that is not registered in
556    /// the active [`OpRegistry`].
557    #[error("unknown op {id:?}{hint}")]
558    #[diagnostic(
559        code(dsl_kit::op::unknown),
560        help(
561            "The Apply node's op_id was not found in the OpRegistry. Register the op at Stepper build time (Engine::new_with_ops) or fix the AST to reference a known id."
562        )
563    )]
564    UnknownOp {
565        /// The unknown op id.
566        id: OpId,
567        /// Optional `did you mean` hint produced by the registry's
568        /// injected [`Suggester`]. Same semantics as
569        /// [`Self::UnknownReducer::hint`].
570        hint: String,
571    },
572}
573
574/// Result alias for engine and evaluator operations.
575pub type EngineResult<T> = Result<T, EngineError>;
576
577/// One entry in an error catalogue: a stable machine-readable code paired
578/// with the human-readable help text explaining how to react to it.
579#[derive(Debug, Clone, PartialEq, Eq)]
580pub struct ErrorCatalogEntry {
581    /// Stable diagnostic code, e.g. `"dsl_kit::eval::aborted"`.
582    pub code: String,
583    /// Help text mirroring the miette `help(..)` attribute on the variant.
584    pub help: String,
585}
586
587/// Returns the built-in [`EngineError`] catalogue.
588pub fn engine_error_catalog() -> Vec<ErrorCatalogEntry> {
589    use miette::Diagnostic;
590
591    fn ctx() -> NodeContext {
592        NodeContext::at(NodeId(0), Path::root())
593    }
594
595    let samples: Vec<EngineError> = vec![
596        EngineError::Aborted {
597            at: ctx(),
598            reason: String::new(),
599        },
600        EngineError::EvalFailed {
601            at: ctx(),
602            source: Box::new(std::io::Error::other("")),
603        },
604        EngineError::Malformed {
605            at: ctx(),
606            detail: String::new(),
607        },
608        EngineError::StepperProtocol {
609            at: ctx(),
610            detail: String::new(),
611        },
612        EngineError::UnknownSuspension {
613            id: SuspensionId(0),
614        },
615        EngineError::UnknownReducer {
616            id: ReducerId(String::new()),
617            hint: String::new(),
618        },
619        EngineError::UnknownOp {
620            id: OpId(String::new()),
621            hint: String::new(),
622        },
623    ];
624
625    samples
626        .into_iter()
627        .filter_map(|e| {
628            let code = e.code()?.to_string();
629            let help = e.help()?.to_string();
630            Some(ErrorCatalogEntry { code, help })
631        })
632        .collect()
633}
634
635// ---------- Step outcome & Stepper -------------------------------------
636
637/// Result of one [`Stepper::step`] call.
638///
639/// The three states name the driver's next action verbatim:
640///
641/// - `Ready` — the engine made progress and can make more without host
642///   input. Call `step()` again immediately.
643/// - `Blocked { newly_pending }` — the engine did everything it can
644///   without host input. Do NOT call `step()` again until at least one
645///   `resolve` has been fed back, or a cancellation observed via
646///   `take_cancellations()`.
647/// - `Done(v)` — the root frame produced a value; interpretation is
648///   complete.
649///
650/// Terminal failure is returned as `Err(Stepper::Error)` from `step()`;
651/// there is no `Failed` variant. Cancellations queued during the failing
652/// step are still drainable via `take_cancellations()` after the `Err`.
653#[derive(Debug, Clone)]
654pub enum StepOutcome<V> {
655    /// Engine advanced; keep looping.
656    Ready,
657    /// Engine is blocked awaiting host input. `newly_pending` names
658    /// suspensions created this call (may be empty when the block is
659    /// on already-live pending).
660    Blocked {
661        /// Suspensions newly created during this `step` call.
662        newly_pending: smallvec::SmallVec<[Pending; 1]>,
663    },
664    /// Interpretation completed with a value.
665    Done(V),
666}
667
668/// Something that can be driven one step at a time from the outside.
669///
670/// v3 shape: sync trait, generic in `V` / `C` / `D` / `EffectError` /
671/// `Error`. Async is a host concern — a host wrapping the stepper in
672/// `FuturesUnordered<ResolverFuture>` is the canonical async story.
673pub trait Stepper {
674    /// Value the stepper produces on completion.
675    type Value;
676    /// DSL-specific node cursor state stored inside `Frame::Node`.
677    type Cursor;
678    /// DSL-specific state delta / write log stored inside `Env` and
679    /// merged by reducers at join.
680    type Delta;
681    /// DSL-specific effect-side failure surfaced via `resolve`.
682    type EffectError: std::error::Error + Send + Sync + 'static;
683    /// DSL / engine-level error surfaced from `step` and `resolve`.
684    type Error: From<Self::EffectError> + std::error::Error + Send + Sync + 'static;
685
686    /// Advance the interpretation as far as possible without host input.
687    fn step(&mut self) -> Result<StepOutcome<Self::Value>, Self::Error>;
688
689    /// Feed a response back for one pending suspension.
690    ///
691    /// Order-independent; the host may resolve pending IDs in any
692    /// order. Unknown IDs return an error the host may treat as a
693    /// benign no-op (see [`EngineError::UnknownSuspension`]).
694    fn resolve(
695        &mut self,
696        id: SuspensionId,
697        result: Result<Self::Value, Self::EffectError>,
698    ) -> Result<(), Self::Error>;
699
700    /// Snapshot of every suspension currently blocking the tree.
701    /// Excludes ids under `Frame::Cancelled` sub-trees. Order matches
702    /// DFS pre-order over the frame tree.
703    fn pending(&self) -> &[Pending];
704
705    /// Drain the set of suspensions the engine has just cancelled.
706    /// Must be called after every `Ok(Ready)` AND every `Err(_)`
707    /// return from `step()`.
708    fn take_cancellations(&mut self) -> Vec<SuspensionId>;
709
710    /// Root of the live frame tree. Debugger read.
711    fn frame_tree(&self) -> &FrameTree<Self::Value, Self::Cursor, Self::Delta, Self::EffectError>;
712
713    /// True when the root has produced a value.
714    fn is_done(&self) -> bool;
715}
716
717// ---------- Frame tree --------------------------------------------------
718
719/// Which child slot in a `ParFrame` a value corresponds to.
720pub type ChildIndex = usize;
721
722/// Why a sub-tree was cancelled.
723#[derive(Debug, Clone)]
724pub enum CancelReason {
725    /// Cancelled because the enclosing `Par` policy fired
726    /// (`Any` / `FirstK` winner selected).
727    ParPolicyFired,
728    /// Cancelled because a sibling failed (FailFast).
729    SiblingFailed,
730}
731
732/// One node in the live frame tree.
733#[derive(Debug)]
734pub enum Frame<V, C, D, EE> {
735    /// An interior interpretation node currently executing.
736    Node {
737        /// AST node this frame is interpreting.
738        node: NodeId,
739        /// Shared environment snapshot.
740        env: EnvRef<D>,
741        /// DSL-specific cursor (opaque to the engine).
742        cursor: C,
743    },
744    /// A fan-out root. Children live on the enclosing `FrameTree.kids`.
745    Par(ParFrame<V, D, EE>),
746    /// A labelled section wrapper (no fan-out semantics).
747    Scope {
748        /// Section label.
749        label: String,
750        /// Shared environment snapshot.
751        env: EnvRef<D>,
752    },
753    /// A leaf blocked on an external effect.
754    PendingEffect {
755        /// Stable id (also present in `Stepper::pending`).
756        id: SuspensionId,
757    },
758    /// A leaf whose value is ready and waiting to be consumed by its
759    /// parent frame's continuation.
760    Value(V),
761    /// A sub-tree the engine has cancelled. Never selected for `step()`
762    /// progress; kept so the debugger can render it.
763    Cancelled {
764        /// Why the sub-tree was cancelled.
765        reason: CancelReason,
766    },
767}
768
769/// Tree of frames. `kids[i]` under a `Par` root is the `i`-th sibling
770/// child, matched positionally with `ParFrame.slots[i]` and
771/// `ParFrame.deltas[i]`.
772#[derive(Debug)]
773pub struct FrameTree<V, C, D, EE> {
774    /// The frame at this node.
775    pub root: Frame<V, C, D, EE>,
776    /// Child sub-trees.
777    pub kids: Vec<FrameTree<V, C, D, EE>>,
778}
779
780/// Fan-out metadata.
781///
782/// `children` are stored on the enclosing `FrameTree.kids`; `slots`,
783/// `deltas`, and `completion_order` are indexed against that same
784/// positional list.
785#[derive(Debug)]
786pub struct ParFrame<V, D, EE> {
787    /// Policy (shape + fail).
788    pub policy: JoinPolicy,
789    /// `slots[i]` is `Some(v)` once child i completed successfully;
790    /// `None` while still running, pending, or cancelled without a
791    /// value. FailFast: reroutes failure to `Err` before reducer.
792    /// CollectAll: per-child failures live in `failures[i]`; combine
793    /// slot + failure at reducer-invocation time.
794    pub slots: Vec<Option<V>>,
795    /// Per-child effect-side failures (CollectAll only). `Some(e)`
796    /// once the child resolved with `Err(e)`; always `None` under
797    /// FailFast (failures reroute to `Err` before the reducer runs).
798    pub failures: Vec<Option<EE>>,
799    /// Per-child accumulated delta.
800    pub deltas: Vec<Option<D>>,
801    /// Order in which children completed successfully.
802    pub completion_order: Vec<ChildIndex>,
803    /// Registry key for the reducer.
804    pub reducer_id: ReducerId,
805    /// Resolved reducer handle (FailFast or CollectAll, matching
806    /// `policy.fail`).
807    pub reducer: ReducerHandle<V, D, EE>,
808    /// True once the shape has fired.
809    pub joined: bool,
810}
811
812// ---------- Join policy -------------------------------------------------
813
814/// Full policy for a `ParFrame`: success-side `shape` + failure-side
815/// `fail`.
816#[derive(Debug, Clone, Copy)]
817pub struct JoinPolicy {
818    /// Success completion condition.
819    pub shape: JoinShape,
820    /// Failure handling.
821    pub fail: FailPolicy,
822}
823
824/// Success-side completion condition.
825#[derive(Debug, Clone, Copy)]
826pub enum JoinShape {
827    /// Every child must complete successfully.
828    All,
829    /// The first successful child wins; remaining children are cancelled.
830    Any,
831    /// The first `k` successful children win; remaining children are
832    /// cancelled.
833    FirstK(usize),
834}
835
836/// Failure-side policy.
837#[derive(Debug, Clone, Copy)]
838pub enum FailPolicy {
839    /// A single child failure aborts the `Par` immediately.
840    FailFast,
841    /// Failures are collected into slots; shape completion still decides
842    /// based on the count of successes.
843    CollectAll,
844}
845
846// ---------- Reducer trait + registry -----------------------------------
847
848/// Serialisable name for a registered reducer.
849#[derive(Debug, Clone, PartialEq, Eq, Hash)]
850pub struct ReducerId(pub String);
851
852impl fmt::Display for ReducerId {
853    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
854        write!(f, "{}", self.0)
855    }
856}
857
858impl From<&str> for ReducerId {
859    fn from(s: &str) -> Self {
860        ReducerId(s.to_string())
861    }
862}
863
864impl From<String> for ReducerId {
865    fn from(s: String) -> Self {
866        ReducerId(s)
867    }
868}
869
870/// FailFast reducer. Sees successful joins only.
871pub trait Reducer<V, D>: Send + Sync {
872    /// Fold slots + deltas + completion order into a joined `(V, D)`.
873    fn reduce(
874        &self,
875        slots: &[Option<V>],
876        deltas: &[Option<D>],
877        winners: &[ChildIndex],
878    ) -> Result<(V, D), EngineError>;
879}
880
881/// CollectAll reducer. Sees the full success/failure slot vector.
882pub trait ReducerCollectAll<V, D, EffectError>: Send + Sync {
883    /// Fold slots (each `Some(Ok)` / `Some(Err)` / `None`) + deltas +
884    /// completion order into a joined `(V, D)`.
885    fn reduce(
886        &self,
887        slots: &[Option<Result<V, EffectError>>],
888        deltas: &[Option<D>],
889        winners: &[ChildIndex],
890    ) -> Result<(V, D), EngineError>;
891}
892
893/// Runtime handle for the resolved reducer of a `ParFrame`.
894///
895/// Which variant is present is dictated by `JoinPolicy.fail`. The
896/// `CollectAll` variant is typed directly in the effect-error `EE`
897/// so the engine can invoke `reduce` on a `&[Option<Result<V, EE>>]`
898/// slot vector at fold time without any downcast.
899pub enum ReducerHandle<V, D, EE> {
900    /// FailFast-typed reducer.
901    FailFast(Arc<dyn Reducer<V, D>>),
902    /// CollectAll-typed reducer, typed in the effect-error `EE`.
903    CollectAll(Arc<dyn ReducerCollectAll<V, D, EE>>),
904}
905
906impl<V, D, EE> fmt::Debug for ReducerHandle<V, D, EE> {
907    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
908        match self {
909            ReducerHandle::FailFast(_) => f.write_str("ReducerHandle::FailFast(..)"),
910            ReducerHandle::CollectAll(_) => f.write_str("ReducerHandle::CollectAll(..)"),
911        }
912    }
913}
914
915impl<V, D, EE> Clone for ReducerHandle<V, D, EE> {
916    fn clone(&self) -> Self {
917        match self {
918            ReducerHandle::FailFast(a) => ReducerHandle::FailFast(a.clone()),
919            ReducerHandle::CollectAll(a) => ReducerHandle::CollectAll(a.clone()),
920        }
921    }
922}
923
924/// Runtime lookup table.
925///
926/// Constructed by the host at Stepper build time; a DSL typically ships
927/// a helper `default_registry()` that registers its standard reducers
928/// under the canonical ids (`"reduce_all_ordered"` etc.).
929pub struct ReducerRegistry<V, D, EffectError> {
930    fail_fast: HashMap<ReducerId, Arc<dyn Reducer<V, D>>>,
931    collect_all: HashMap<ReducerId, Arc<dyn ReducerCollectAll<V, D, EffectError>>>,
932    suggester: crate::suggest::SuggesterHandle,
933}
934
935impl<V, D, EE> Default for ReducerRegistry<V, D, EE> {
936    fn default() -> Self {
937        Self::new()
938    }
939}
940
941impl<V, D, EE> ReducerRegistry<V, D, EE> {
942    /// Creates an empty registry.
943    pub fn new() -> Self {
944        Self {
945            fail_fast: HashMap::new(),
946            collect_all: HashMap::new(),
947            suggester: crate::suggest::noop_handle(),
948        }
949    }
950
951    /// Injects a fuzzy-match [`Suggester`](crate::Suggester) used to
952    /// enrich [`EngineError::UnknownReducer`] with a `did you mean X?`
953    /// hint at [`Self::resolve`] time.
954    ///
955    /// The default is a no-op suggester, so the crate stays free of a
956    /// similarity algorithm on its own. Pass
957    /// `Arc::new(dsl_kit_fuzzy::FuzzySuggester::default())` (or any
958    /// other [`Suggester`](crate::Suggester) impl) at the composition
959    /// root to enable hints.
960    pub fn with_suggester(mut self, suggester: crate::suggest::SuggesterHandle) -> Self {
961        self.suggester = suggester;
962        self
963    }
964
965    /// Registers a FailFast-typed reducer under `id`.
966    pub fn register_fail_fast(
967        &mut self,
968        id: impl Into<ReducerId>,
969        reducer: Arc<dyn Reducer<V, D>>,
970    ) {
971        self.fail_fast.insert(id.into(), reducer);
972    }
973
974    /// Registers a CollectAll-typed reducer under `id`.
975    pub fn register_collect_all(
976        &mut self,
977        id: impl Into<ReducerId>,
978        reducer: Arc<dyn ReducerCollectAll<V, D, EE>>,
979    ) {
980        self.collect_all.insert(id.into(), reducer);
981    }
982
983    /// Resolves the reducer for a `ParFrame` at construction time.
984    ///
985    /// The `fail` argument disambiguates when the same id has been
986    /// registered under both traits. Returns
987    /// `EngineError::UnknownReducer` on miss.
988    pub fn resolve(
989        &self,
990        id: &ReducerId,
991        fail: FailPolicy,
992    ) -> Result<ReducerHandle<V, D, EE>, EngineError> {
993        let miss = || {
994            // Candidates are drawn from the branch the caller asked
995            // for so the hint never suggests an id that would still
996            // miss under the same `fail` policy.
997            let names: Vec<&str> = match fail {
998                FailPolicy::FailFast => self.fail_fast.keys().map(|k| k.0.as_str()).collect(),
999                FailPolicy::CollectAll => self.collect_all.keys().map(|k| k.0.as_str()).collect(),
1000            };
1001            let hint = self
1002                .suggester
1003                .enrich_unknown(&id.0, &names)
1004                .map(|h| format!(" ({h})"))
1005                .unwrap_or_default();
1006            EngineError::UnknownReducer {
1007                id: id.clone(),
1008                hint,
1009            }
1010        };
1011        match fail {
1012            FailPolicy::FailFast => self
1013                .fail_fast
1014                .get(id)
1015                .cloned()
1016                .map(ReducerHandle::FailFast)
1017                .ok_or_else(miss),
1018            FailPolicy::CollectAll => self
1019                .collect_all
1020                .get(id)
1021                .cloned()
1022                .map(ReducerHandle::CollectAll)
1023                .ok_or_else(miss),
1024        }
1025    }
1026}
1027
1028// ---------- Op trait + registry -----------------------------------------
1029
1030/// Serialisable name for a registered op.
1031#[derive(Debug, Clone, PartialEq, Eq, Hash)]
1032pub struct OpId(pub String);
1033
1034impl fmt::Display for OpId {
1035    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1036        write!(f, "{}", self.0)
1037    }
1038}
1039
1040impl From<&str> for OpId {
1041    fn from(s: &str) -> Self {
1042        OpId(s.to_string())
1043    }
1044}
1045
1046impl From<String> for OpId {
1047    fn from(s: String) -> Self {
1048        OpId(s)
1049    }
1050}
1051
1052/// A pure value fold applied by an `Apply` node once every child
1053/// argument has produced a value.
1054///
1055/// Ops never suspend: effects belong in `Call` children, whose values
1056/// arrive here as ordinary `args` entries. Domain failures (division by
1057/// zero, type mismatch on a dynamic value) are reported as
1058/// [`EngineError::EvalFailed`] with the node context supplied by the
1059/// engine at the call site.
1060pub trait Op<V>: Send + Sync {
1061    /// Fold the evaluated child values into the node's value.
1062    ///
1063    /// `args` holds one entry per `Apply` child, in declaration order.
1064    /// Zero-child `Apply` nodes invoke the op with an empty slice.
1065    fn apply(&self, node: NodeId, args: &[V]) -> Result<V, EngineError>;
1066}
1067
1068/// Runtime handle for the resolved op of an `Apply` frame.
1069pub type OpHandle<V> = Arc<dyn Op<V>>;
1070
1071/// Runtime lookup table for [`Op`]s, the `Apply` counterpart of
1072/// [`ReducerRegistry`].
1073///
1074/// Constructed by the host at Stepper build time; a DSL typically ships
1075/// a helper that registers its standard ops under canonical ids
1076/// (`"add"`, `"mul"`, ...). Passed to [`Engine::new_with_ops`]; DSLs
1077/// with no `Apply` nodes can stay on [`Engine::new`], which uses an
1078/// empty registry.
1079///
1080/// [`Engine::new`]: crate::Engine::new
1081/// [`Engine::new_with_ops`]: crate::Engine::new_with_ops
1082pub struct OpRegistry<V> {
1083    ops: HashMap<OpId, OpHandle<V>>,
1084    suggester: crate::suggest::SuggesterHandle,
1085}
1086
1087impl<V> Default for OpRegistry<V> {
1088    fn default() -> Self {
1089        Self::new()
1090    }
1091}
1092
1093impl<V> OpRegistry<V> {
1094    /// Creates an empty registry.
1095    pub fn new() -> Self {
1096        Self {
1097            ops: HashMap::new(),
1098            suggester: crate::suggest::noop_handle(),
1099        }
1100    }
1101
1102    /// Injects a fuzzy-match [`Suggester`](crate::Suggester) used to
1103    /// enrich [`EngineError::UnknownOp`] with a `did you mean X?`
1104    /// hint at [`Self::resolve`] time.
1105    ///
1106    /// The default is a no-op suggester, so the crate stays free of a
1107    /// similarity algorithm on its own. Pass
1108    /// `Arc::new(dsl_kit_fuzzy::FuzzySuggester::default())` at the
1109    /// composition root to enable hints.
1110    pub fn with_suggester(mut self, suggester: crate::suggest::SuggesterHandle) -> Self {
1111        self.suggester = suggester;
1112        self
1113    }
1114
1115    /// Registers an op under `id`.
1116    pub fn register(&mut self, id: impl Into<OpId>, op: OpHandle<V>) {
1117        self.ops.insert(id.into(), op);
1118    }
1119
1120    /// Resolves the op for an `Apply` frame at spawn / validation time.
1121    /// Returns [`EngineError::UnknownOp`] on miss.
1122    pub fn resolve(&self, id: &OpId) -> Result<OpHandle<V>, EngineError> {
1123        self.ops.get(id).cloned().ok_or_else(|| {
1124            let names: Vec<&str> = self.ops.keys().map(|k| k.0.as_str()).collect();
1125            let hint = self
1126                .suggester
1127                .enrich_unknown(&id.0, &names)
1128                .map(|h| format!(" ({h})"))
1129                .unwrap_or_default();
1130            EngineError::UnknownOp {
1131                id: id.clone(),
1132                hint,
1133            }
1134        })
1135    }
1136}
1137
1138// ---------- Derived execution (DslExec / DslSemantics / DerivedAst) ----
1139
1140/// Mechanical node classification, normally supplied by
1141/// `#[derive(DslExec)]` from `dsl-kit-macros`.
1142///
1143/// This is the derivable half of an [`Ast`]: which engine [`NodeKind`]
1144/// each variant maps to, and the payload of `value`-marked literal
1145/// variants. The semantic half (value type, truthiness, bindings)
1146/// lives in [`DslSemantics`]; [`DerivedAst`] zips the two into an
1147/// engine-ready [`Ast`].
1148pub trait DslExec: Walk {
1149    /// Payload type of `#[dsl_exec(value)]` variants. `()` when the
1150    /// enum has no value variants.
1151    type LitValue: Clone + fmt::Debug;
1152
1153    /// Engine classification of this node.
1154    fn exec_kind(&self) -> NodeKind;
1155
1156    /// Payload of a value variant; `None` for every other variant.
1157    fn exec_literal(&self) -> Option<Self::LitValue>;
1158}
1159
1160/// The semantic half an author writes next to `#[derive(DslExec)]`:
1161/// the runtime value type and the hooks whose meaning the kit cannot
1162/// derive. Every hook mirrors its [`Ast`] counterpart and keeps the
1163/// same default, so a DSL only implements what its node kinds use.
1164pub trait DslSemantics {
1165    /// Runtime value type produced by the DSL.
1166    type Value: Clone + fmt::Debug;
1167    /// Per-child state delta accumulated across a `Par` and extended
1168    /// by `Bind`.
1169    type Delta: Clone + Default + fmt::Debug;
1170    /// Effect-side failure the host reports through `resolve`.
1171    type EffectError: std::error::Error + Clone + Send + Sync + 'static;
1172    /// Per-frame cursor surfaced through the projected frame tree.
1173    type Cursor: Clone + fmt::Debug + Default;
1174
1175    /// See [`Ast::unit_value`].
1176    fn unit_value(&self) -> Self::Value;
1177
1178    /// See [`Ast::truthy`].
1179    fn truthy(&self, _value: &Self::Value) -> Option<bool> {
1180        None
1181    }
1182
1183    /// See [`Ast::continue_loop`].
1184    fn continue_loop(&self, _node: NodeId, _last: &Self::Value, _iteration: usize) -> LoopDecision {
1185        LoopDecision::Break
1186    }
1187
1188    /// See [`Ast::bind_delta`].
1189    fn bind_delta(&self, _name: &str, _value: &Self::Value) -> Option<Self::Delta> {
1190        None
1191    }
1192
1193    /// See [`Ast::lookup`].
1194    fn lookup(&self, _delta: &Self::Delta, _name: &str) -> Option<Self::Value> {
1195        None
1196    }
1197}
1198
1199/// Engine-ready [`Ast`] assembled from a `#[derive(DslExec)]` node
1200/// type plus a [`DslSemantics`] implementation.
1201///
1202/// Construction walks the tree once to build the `NodeId -> node`
1203/// lookup; `node_kind` / `literal` then delegate to the derived
1204/// classification and every semantic hook to `S`.
1205///
1206/// This form borrows the tree (`&'a N`), so an [`Engine`] built from it
1207/// cannot outlive the program it walks — the right choice for a
1208/// transient engine. See [`OwnedDerivedAst`] for a variant that projects
1209/// the tree into owned storage and carries no lifetime; reach for it
1210/// when embedding an engine in a long-lived host that would otherwise
1211/// need `Box::leak` to keep program and engine together.
1212pub struct DerivedAst<'a, N, S> {
1213    root: &'a N,
1214    by_id: HashMap<NodeId, &'a N>,
1215    sem: S,
1216}
1217
1218impl<'a, N: DslExec, S> DerivedAst<'a, N, S> {
1219    /// Builds the lookup for `root` and attaches the semantics.
1220    pub fn new(root: &'a N, sem: S) -> Self {
1221        fn collect<'a, N: Walk>(node: &'a N, map: &mut HashMap<NodeId, &'a N>) {
1222            map.insert(node.node_id(), node);
1223            for child in node.children() {
1224                collect(child, map);
1225            }
1226        }
1227        let mut by_id = HashMap::new();
1228        collect(root, &mut by_id);
1229        Self { root, by_id, sem }
1230    }
1231
1232    fn node(&self, id: NodeId) -> &'a N {
1233        self.by_id.get(&id).copied().expect("unknown NodeId")
1234    }
1235}
1236
1237impl<N, S> Ast for DerivedAst<'_, N, S>
1238where
1239    N: DslExec,
1240    S: DslSemantics,
1241    S::Value: From<N::LitValue>,
1242{
1243    type Value = S::Value;
1244    type Delta = S::Delta;
1245    type EffectError = S::EffectError;
1246    type Cursor = S::Cursor;
1247
1248    fn root(&self) -> NodeId {
1249        self.root.node_id()
1250    }
1251
1252    fn node_kind(&self, id: NodeId) -> NodeKind {
1253        self.node(id).exec_kind()
1254    }
1255
1256    fn unit_value(&self) -> Self::Value {
1257        self.sem.unit_value()
1258    }
1259
1260    fn truthy(&self, value: &Self::Value) -> Option<bool> {
1261        self.sem.truthy(value)
1262    }
1263
1264    fn continue_loop(&self, node: NodeId, last: &Self::Value, iteration: usize) -> LoopDecision {
1265        self.sem.continue_loop(node, last, iteration)
1266    }
1267
1268    fn bind_delta(&self, name: &str, value: &Self::Value) -> Option<Self::Delta> {
1269        self.sem.bind_delta(name, value)
1270    }
1271
1272    fn lookup(&self, delta: &Self::Delta, name: &str) -> Option<Self::Value> {
1273        self.sem.lookup(delta, name)
1274    }
1275
1276    fn literal(&self, node: NodeId) -> Option<Self::Value> {
1277        self.node(node).exec_literal().map(S::Value::from)
1278    }
1279}
1280
1281/// Owned counterpart of [`DerivedAst`]: an engine-ready [`Ast`] that
1282/// carries no borrow of the source tree.
1283///
1284/// [`DerivedAst`] keeps `&'a N` references into a live tree, so an
1285/// [`Engine`] built from it cannot outlive that tree. A long-lived host
1286/// that wants to hold its program and engine together in one struct
1287/// therefore had to synthesise a `&'static` borrow with `Box::leak`.
1288/// `OwnedDerivedAst` removes that need: its constructor walks `root`
1289/// once, projecting each node's classification ([`NodeKind`]) and
1290/// literal payload into an owned side table. The borrow ends when the
1291/// constructor returns, so the result carries no lifetime — a host can
1292/// own `program: N` alongside `engine: Engine<OwnedDerivedAst<L, S>>` in
1293/// the same struct with no leak and no `unsafe` (and no `Arc`).
1294///
1295/// Use [`DerivedAst`] when a borrow of the tree is acceptable — a
1296/// transient engine that lives no longer than the program it walks. Use
1297/// `OwnedDerivedAst` when the engine is embedded in a long-lived host.
1298///
1299/// When `L` and `S` are both [`Clone`], `OwnedDerivedAst` is `Clone`,
1300/// so a host can keep a pristine copy of the projection to rebuild the
1301/// engine from on reset.
1302pub struct OwnedDerivedAst<L, S> {
1303    root: NodeId,
1304    nodes: HashMap<NodeId, OwnedNode<L>>,
1305    sem: S,
1306}
1307
1308/// Owned per-node projection captured by [`OwnedDerivedAst::new`]: the
1309/// node's engine classification plus its literal payload, both stored
1310/// by value so the projection outlives the source tree.
1311#[derive(Clone)]
1312struct OwnedNode<L> {
1313    kind: NodeKind,
1314    literal: Option<L>,
1315}
1316
1317impl<L, S> OwnedDerivedAst<L, S> {
1318    /// Walks `root` once, projecting each node's classification and
1319    /// literal payload into owned storage. The borrow ends when this
1320    /// constructor returns — the result carries no lifetime.
1321    pub fn new<N>(root: &N, sem: S) -> Self
1322    where
1323        N: DslExec<LitValue = L>,
1324    {
1325        fn collect<N: DslExec>(node: &N, map: &mut HashMap<NodeId, OwnedNode<N::LitValue>>) {
1326            map.insert(
1327                node.node_id(),
1328                OwnedNode {
1329                    kind: node.exec_kind(),
1330                    literal: node.exec_literal(),
1331                },
1332            );
1333            for child in node.children() {
1334                collect(child, map);
1335            }
1336        }
1337        let mut nodes = HashMap::new();
1338        collect(root, &mut nodes);
1339        Self {
1340            root: root.node_id(),
1341            nodes,
1342            sem,
1343        }
1344    }
1345
1346    fn node(&self, id: NodeId) -> &OwnedNode<L> {
1347        self.nodes.get(&id).expect("unknown NodeId")
1348    }
1349}
1350
1351impl<L, S> Clone for OwnedDerivedAst<L, S>
1352where
1353    L: Clone,
1354    S: Clone,
1355{
1356    fn clone(&self) -> Self {
1357        Self {
1358            root: self.root,
1359            nodes: self.nodes.clone(),
1360            sem: self.sem.clone(),
1361        }
1362    }
1363}
1364
1365impl<L, S> Ast for OwnedDerivedAst<L, S>
1366where
1367    L: Clone + fmt::Debug,
1368    S: DslSemantics,
1369    S::Value: From<L>,
1370{
1371    type Value = S::Value;
1372    type Delta = S::Delta;
1373    type EffectError = S::EffectError;
1374    type Cursor = S::Cursor;
1375
1376    fn root(&self) -> NodeId {
1377        self.root
1378    }
1379
1380    fn node_kind(&self, id: NodeId) -> NodeKind {
1381        self.node(id).kind.clone()
1382    }
1383
1384    fn unit_value(&self) -> Self::Value {
1385        self.sem.unit_value()
1386    }
1387
1388    fn truthy(&self, value: &Self::Value) -> Option<bool> {
1389        self.sem.truthy(value)
1390    }
1391
1392    fn continue_loop(&self, node: NodeId, last: &Self::Value, iteration: usize) -> LoopDecision {
1393        self.sem.continue_loop(node, last, iteration)
1394    }
1395
1396    fn bind_delta(&self, name: &str, value: &Self::Value) -> Option<Self::Delta> {
1397        self.sem.bind_delta(name, value)
1398    }
1399
1400    fn lookup(&self, delta: &Self::Delta, name: &str) -> Option<Self::Value> {
1401        self.sem.lookup(delta, name)
1402    }
1403
1404    fn literal(&self, node: NodeId) -> Option<Self::Value> {
1405        self.node(node).literal.clone().map(S::Value::from)
1406    }
1407}
1408
1409// ---------- Environment sharing ----------------------------------------
1410
1411/// Shared environment handle.
1412///
1413/// Reads are cheap `Arc` clones. Writes accumulate in a per-child `D`
1414/// (state delta) inside a `Par` and are merged by the reducer at join.
1415#[derive(Debug)]
1416pub struct EnvRef<D>(pub Arc<Env<D>>);
1417
1418impl<D> Clone for EnvRef<D> {
1419    fn clone(&self) -> Self {
1420        EnvRef(self.0.clone())
1421    }
1422}
1423
1424/// The `Env` a `Frame::Node` or `Frame::Scope` holds. Generic over the
1425/// DSL-owned `D` (state delta); the engine does not interpret `D`.
1426#[derive(Debug)]
1427pub struct Env<D> {
1428    /// The DSL's own state delta / bindings snapshot.
1429    pub delta: D,
1430    /// Optional parent for lexical lookup.
1431    pub parent: Option<Arc<Env<D>>>,
1432}
1433
1434// ---------- Marker traits + traversal ----------------------------------
1435
1436/// Marker trait for AST enums recognised by the kit.
1437pub trait DslNode {
1438    /// Returns the stable ID assigned to this node.
1439    fn node_id(&self) -> NodeId;
1440
1441    /// Returns the enum variant name of this node as a static string
1442    /// (e.g. `"Seq"`, `"Par"`, `"Call"`).
1443    ///
1444    /// The name matches the variant's Rust source ident and lines up
1445    /// with `dsl_kit_schema::VariantSchema::name` when the type also
1446    /// derives `DslSchema`. Consumers use this to correlate a runtime
1447    /// node with its type-level schema entry — schema-aware lint
1448    /// rules, editor tooling, and any other component that needs to
1449    /// go from an AST value to "which variant is this" without
1450    /// downcasting.
1451    fn variant_name(&self) -> &'static str;
1452}
1453
1454// ---------- Breakpoints -------------------------------------------------
1455
1456/// Identifier assigned by a [`BreakpointSet`] to each added condition.
1457#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
1458pub struct BreakpointId(pub u64);
1459
1460impl fmt::Display for BreakpointId {
1461    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1462        write!(f, "bp{}", self.0)
1463    }
1464}
1465
1466/// A boolean predicate over [`NodeContext`] used to describe conditional
1467/// breakpoints.
1468#[derive(Debug, Clone, PartialEq, Eq)]
1469pub enum BreakCondition {
1470    /// Matches when the node ID is exactly `id`.
1471    Node(NodeId),
1472    /// Matches when the current path has the given prefix.
1473    PathPrefix(Path),
1474    /// Matches when the current path equals the given path exactly.
1475    PathExact(Path),
1476    /// Matches when the current call-frame depth is at least `n`.
1477    DepthAtLeast(u32),
1478    /// Matches when the current call-frame depth is at most `n`.
1479    DepthAtMost(u32),
1480    /// Matches when the current call-frame depth equals `n` exactly.
1481    DepthEquals(u32),
1482    /// Matches when the iteration counter equals `n`.
1483    Iteration(u64),
1484    /// Matches when the current call frame equals `frame`.
1485    CallFrame(CallFrameId),
1486    /// Matches when any child matches.
1487    Any(Vec<BreakCondition>),
1488    /// Matches when every child matches.
1489    All(Vec<BreakCondition>),
1490    /// Matches when the inner does not match.
1491    Not(Box<BreakCondition>),
1492    /// Always matches (useful as a debugger's "break on every node" mode).
1493    Always,
1494    /// Never matches (useful as a disabled placeholder).
1495    Never,
1496}
1497
1498impl BreakCondition {
1499    /// Convenience constructor.
1500    pub fn at_node(id: NodeId) -> Self {
1501        Self::Node(id)
1502    }
1503
1504    /// Convenience constructor.
1505    pub fn under_path(path: Path) -> Self {
1506        Self::PathPrefix(path)
1507    }
1508
1509    /// Convenience constructor.
1510    pub fn at_path(path: Path) -> Self {
1511        Self::PathExact(path)
1512    }
1513
1514    /// Convenience constructor.
1515    pub fn at_depth_at_least(n: u32) -> Self {
1516        Self::DepthAtLeast(n)
1517    }
1518
1519    /// Convenience constructor.
1520    pub fn at_depth_at_most(n: u32) -> Self {
1521        Self::DepthAtMost(n)
1522    }
1523
1524    /// Convenience constructor.
1525    pub fn at_depth(n: u32) -> Self {
1526        Self::DepthEquals(n)
1527    }
1528
1529    /// Convenience constructor.
1530    pub fn at_iteration(n: u64) -> Self {
1531        Self::Iteration(n)
1532    }
1533
1534    /// Convenience constructor.
1535    pub fn in_call_frame(frame: CallFrameId) -> Self {
1536        Self::CallFrame(frame)
1537    }
1538
1539    /// Logical AND.
1540    pub fn and(self, other: Self) -> Self {
1541        match (self, other) {
1542            (Self::All(mut xs), Self::All(ys)) => {
1543                xs.extend(ys);
1544                Self::All(xs)
1545            }
1546            (Self::All(mut xs), other) => {
1547                xs.push(other);
1548                Self::All(xs)
1549            }
1550            (this, Self::All(mut ys)) => {
1551                ys.insert(0, this);
1552                Self::All(ys)
1553            }
1554            (this, other) => Self::All(vec![this, other]),
1555        }
1556    }
1557
1558    /// Logical OR.
1559    pub fn or(self, other: Self) -> Self {
1560        match (self, other) {
1561            (Self::Any(mut xs), Self::Any(ys)) => {
1562                xs.extend(ys);
1563                Self::Any(xs)
1564            }
1565            (Self::Any(mut xs), other) => {
1566                xs.push(other);
1567                Self::Any(xs)
1568            }
1569            (this, Self::Any(mut ys)) => {
1570                ys.insert(0, this);
1571                Self::Any(ys)
1572            }
1573            (this, other) => Self::Any(vec![this, other]),
1574        }
1575    }
1576
1577    /// Evaluates the condition against a context.
1578    pub fn matches(&self, ctx: &NodeContext) -> bool {
1579        match self {
1580            Self::Node(id) => ctx.node == *id,
1581            Self::PathPrefix(prefix) => {
1582                ctx.path.0.len() >= prefix.0.len() && ctx.path.0[..prefix.0.len()] == prefix.0[..]
1583            }
1584            Self::PathExact(path) => ctx.path == *path,
1585            Self::DepthAtLeast(n) => ctx.depth >= *n,
1586            Self::DepthAtMost(n) => ctx.depth <= *n,
1587            Self::DepthEquals(n) => ctx.depth == *n,
1588            Self::Iteration(n) => ctx.iteration.map(|i| i.0 == *n).unwrap_or(false),
1589            Self::CallFrame(frame) => ctx.frame == Some(*frame),
1590            Self::Any(children) => children.iter().any(|c| c.matches(ctx)),
1591            Self::All(children) => children.iter().all(|c| c.matches(ctx)),
1592            Self::Not(inner) => !inner.matches(ctx),
1593            Self::Always => true,
1594            Self::Never => false,
1595        }
1596    }
1597}
1598
1599impl std::ops::Not for BreakCondition {
1600    type Output = Self;
1601
1602    /// Logical NOT: `!cond` matches exactly when `cond` does not.
1603    fn not(self) -> Self {
1604        Self::Not(Box::new(self))
1605    }
1606}
1607
1608/// A registry of breakpoint conditions and their assigned IDs.
1609#[derive(Debug, Default)]
1610pub struct BreakpointSet {
1611    next: u64,
1612    entries: Vec<(BreakpointId, BreakCondition)>,
1613}
1614
1615impl BreakpointSet {
1616    /// Creates an empty set.
1617    pub fn new() -> Self {
1618        Self {
1619            next: 1,
1620            entries: Vec::new(),
1621        }
1622    }
1623
1624    /// Adds a condition and returns its assigned id.
1625    pub fn add(&mut self, condition: BreakCondition) -> BreakpointId {
1626        let id = BreakpointId(self.next);
1627        self.next += 1;
1628        self.entries.push((id, condition));
1629        id
1630    }
1631
1632    /// Removes an entry by id. Returns whether an entry was found.
1633    pub fn remove(&mut self, id: BreakpointId) -> bool {
1634        let before = self.entries.len();
1635        self.entries.retain(|(entry_id, _)| *entry_id != id);
1636        self.entries.len() != before
1637    }
1638
1639    /// Returns the ids of all entries whose condition matches `ctx`.
1640    pub fn matches(&self, ctx: &NodeContext) -> Vec<BreakpointId> {
1641        self.entries
1642            .iter()
1643            .filter(|(_, cond)| cond.matches(ctx))
1644            .map(|(id, _)| *id)
1645            .collect()
1646    }
1647
1648    /// Returns whether the set has no entries.
1649    pub fn is_empty(&self) -> bool {
1650        self.entries.is_empty()
1651    }
1652
1653    /// Number of entries currently registered.
1654    pub fn len(&self) -> usize {
1655        self.entries.len()
1656    }
1657
1658    /// Iterates over the registered `(id, condition)` pairs.
1659    pub fn iter(&self) -> impl Iterator<Item = (BreakpointId, &BreakCondition)> {
1660        self.entries.iter().map(|(id, c)| (*id, c))
1661    }
1662}
1663
1664// ---------- Traversal ---------------------------------------------------
1665
1666/// Which side of a node's traversal the visitor is currently on.
1667#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1668pub enum Phase {
1669    /// Before descending into the node's children.
1670    Pre,
1671    /// After all children have been visited.
1672    Post,
1673}
1674
1675/// AST traversal contract.
1676pub trait Walk: DslNode + Sized {
1677    /// Direct children of this node, in traversal order.
1678    fn children(&self) -> Vec<&Self>;
1679
1680    /// Depth-first pre / post traversal.
1681    fn walk<F>(&self, visitor: &mut F)
1682    where
1683        F: FnMut(&Self, Phase),
1684    {
1685        visitor(self, Phase::Pre);
1686        for child in self.children() {
1687            child.walk(visitor);
1688        }
1689        visitor(self, Phase::Post);
1690    }
1691
1692    /// Depth-first traversal with early exit.
1693    fn walk_until<F, T>(&self, visitor: &mut F) -> Option<T>
1694    where
1695        F: FnMut(&Self, Phase) -> Option<T>,
1696    {
1697        if let Some(t) = visitor(self, Phase::Pre) {
1698            return Some(t);
1699        }
1700        for child in self.children() {
1701            if let Some(t) = child.walk_until(visitor) {
1702                return Some(t);
1703            }
1704        }
1705        visitor(self, Phase::Post)
1706    }
1707
1708    /// Locates a node by its stable ID.
1709    fn find_by_id(&self, target: NodeId) -> Option<&Self> {
1710        self.walk_until(&mut |node, phase| {
1711            if phase == Phase::Pre && node.node_id() == target {
1712                Some(node as *const Self)
1713            } else {
1714                None
1715            }
1716        })
1717        .map(|ptr| unsafe { &*ptr })
1718    }
1719}
1720
1721/// Mutable counterpart of [`Walk`].
1722pub trait WalkMut: DslNode + Sized {
1723    /// Direct children of this node, mutably, in traversal order.
1724    fn children_mut(&mut self) -> Vec<&mut Self>;
1725
1726    /// Depth-first pre / post traversal with mutable access.
1727    fn walk_mut<F>(&mut self, visitor: &mut F)
1728    where
1729        F: FnMut(&mut Self, Phase),
1730    {
1731        visitor(self, Phase::Pre);
1732        for child in self.children_mut() {
1733            child.walk_mut(visitor);
1734        }
1735        visitor(self, Phase::Post);
1736    }
1737}
1738
1739#[cfg(test)]
1740mod tests {
1741    use super::*;
1742
1743    #[test]
1744    fn path_push_extends_depth() {
1745        let ids = IdGen::new();
1746        let a = ids.node();
1747        let b = ids.node();
1748
1749        let root = Path::root();
1750        assert_eq!(root.depth(), 0);
1751
1752        let one = root.push(a);
1753        assert_eq!(one.depth(), 1);
1754
1755        let two = one.push(b);
1756        assert_eq!(two.depth(), 2);
1757        assert_eq!(two.tip(), Some(b));
1758    }
1759
1760    #[test]
1761    fn id_generator_yields_distinct_ids() {
1762        let ids = IdGen::new();
1763        let a = ids.node();
1764        let b = ids.node();
1765        assert_ne!(a, b);
1766    }
1767
1768    #[test]
1769    fn null_sink_accepts_events() {
1770        let mut sink = NullSink;
1771        let event = Event::VisitPre {
1772            at: NodeContext::at(NodeId(0), Path::root()),
1773        };
1774        sink.emit(&event);
1775    }
1776
1777    fn ctx_at(node: NodeId, path: Path, depth: u32) -> NodeContext {
1778        NodeContext {
1779            node,
1780            path,
1781            frame: None,
1782            depth,
1783            iteration: None,
1784        }
1785    }
1786
1787    #[test]
1788    fn breakpoint_node_matches_exact_id() {
1789        let cond = BreakCondition::at_node(NodeId(7));
1790        assert!(cond.matches(&ctx_at(NodeId(7), Path::root().push(NodeId(7)), 1)));
1791        assert!(!cond.matches(&ctx_at(NodeId(8), Path::root().push(NodeId(8)), 1)));
1792    }
1793
1794    #[test]
1795    fn breakpoint_set_add_matches_remove() {
1796        let mut set = BreakpointSet::new();
1797        let hit = set.add(BreakCondition::at_node(NodeId(4)));
1798        let miss = set.add(BreakCondition::at_node(NodeId(99)));
1799
1800        let ctx = ctx_at(NodeId(4), Path::root().push(NodeId(4)), 1);
1801        assert_eq!(set.matches(&ctx), vec![hit]);
1802
1803        assert!(set.remove(hit));
1804        assert!(set.matches(&ctx).is_empty());
1805        assert_eq!(set.len(), 1);
1806        assert!(set.iter().any(|(id, _)| id == miss));
1807    }
1808
1809    #[test]
1810    fn engine_error_carries_stable_code() {
1811        let err = EngineError::Aborted {
1812            at: NodeContext::at(NodeId(1), Path::root().push(NodeId(1))),
1813            reason: "user requested".into(),
1814        };
1815        use miette::Diagnostic;
1816        assert_eq!(
1817            err.code().map(|c| c.to_string()).as_deref(),
1818            Some("dsl_kit::eval::aborted")
1819        );
1820    }
1821
1822    #[test]
1823    fn engine_error_catalog_covers_every_variant() {
1824        let entries = engine_error_catalog();
1825        let codes: Vec<&str> = entries.iter().map(|e| e.code.as_str()).collect();
1826        assert!(codes.contains(&"dsl_kit::eval::aborted"));
1827        assert!(codes.contains(&"dsl_kit::eval::failed"));
1828        assert!(codes.contains(&"dsl_kit::ast::malformed"));
1829        assert!(codes.contains(&"dsl_kit::stepper::protocol"));
1830        assert!(codes.contains(&"dsl_kit::stepper::unknown_suspension"));
1831        assert!(codes.contains(&"dsl_kit::reducer::unknown"));
1832        for entry in &entries {
1833            assert!(!entry.help.is_empty(), "help empty for {}", entry.code);
1834        }
1835    }
1836
1837    #[test]
1838    fn reducer_id_from_str_and_string() {
1839        let a: ReducerId = "foo".into();
1840        let b: ReducerId = String::from("foo").into();
1841        assert_eq!(a, b);
1842    }
1843
1844    #[test]
1845    fn reducer_registry_resolves_fail_fast_and_collect_all_independently() {
1846        // A trivial FailFast reducer that returns the first non-None
1847        // slot verbatim.
1848        struct FirstNonNone;
1849        impl Reducer<i64, ()> for FirstNonNone {
1850            fn reduce(
1851                &self,
1852                slots: &[Option<i64>],
1853                _deltas: &[Option<()>],
1854                _winners: &[ChildIndex],
1855            ) -> Result<(i64, ()), EngineError> {
1856                let v = slots.iter().find_map(|s| *s).unwrap_or(0);
1857                Ok((v, ()))
1858            }
1859        }
1860
1861        // A trivial CollectAll reducer.
1862        struct CountOk;
1863        impl ReducerCollectAll<i64, (), std::io::Error> for CountOk {
1864            fn reduce(
1865                &self,
1866                slots: &[Option<Result<i64, std::io::Error>>],
1867                _deltas: &[Option<()>],
1868                _winners: &[ChildIndex],
1869            ) -> Result<(i64, ()), EngineError> {
1870                let count = slots.iter().filter(|s| matches!(s, Some(Ok(_)))).count();
1871                Ok((count as i64, ()))
1872            }
1873        }
1874
1875        let mut reg: ReducerRegistry<i64, (), std::io::Error> = ReducerRegistry::new();
1876        reg.register_fail_fast("first", Arc::new(FirstNonNone));
1877        reg.register_collect_all("count_ok", Arc::new(CountOk));
1878
1879        let ff = reg.resolve(&"first".into(), FailPolicy::FailFast).unwrap();
1880        assert!(matches!(ff, ReducerHandle::FailFast(_)));
1881        let ca = reg
1882            .resolve(&"count_ok".into(), FailPolicy::CollectAll)
1883            .unwrap();
1884        assert!(matches!(ca, ReducerHandle::CollectAll(_)));
1885
1886        let miss = reg.resolve(&"nope".into(), FailPolicy::FailFast);
1887        assert!(matches!(miss, Err(EngineError::UnknownReducer { .. })));
1888    }
1889
1890    /// Fixed-output suggester used to prove the with_suggester wiring
1891    /// without depending on `dsl-kit-fuzzy` — a real dev-dep on that
1892    /// crate would create a cycle since fuzzy already depends on
1893    /// dsl-kit-core, and cargo cannot unify the `Suggester` trait
1894    /// across the two versions of core that would result.
1895    struct FixedSuggester(&'static str);
1896    impl Suggester for FixedSuggester {
1897        fn suggest<'a>(&self, _q: &str, cands: &'a [&str]) -> Vec<Suggestion<'a>> {
1898            cands
1899                .iter()
1900                .find(|c| **c == self.0)
1901                .map(|c| Suggestion {
1902                    candidate: c,
1903                    score: 1.0,
1904                })
1905                .into_iter()
1906                .collect()
1907        }
1908    }
1909
1910    #[test]
1911    fn unknown_reducer_defaults_to_no_hint() {
1912        // Without an injected suggester the historical `unknown
1913        // reducer "X"` wording is preserved verbatim.
1914        struct Noop;
1915        impl Reducer<i64, ()> for Noop {
1916            fn reduce(
1917                &self,
1918                _s: &[Option<i64>],
1919                _d: &[Option<()>],
1920                _w: &[ChildIndex],
1921            ) -> Result<(i64, ()), EngineError> {
1922                Ok((0, ()))
1923            }
1924        }
1925        let mut reg: ReducerRegistry<i64, (), std::io::Error> = ReducerRegistry::new();
1926        reg.register_fail_fast("first", Arc::new(Noop));
1927        let miss = reg.resolve(&"frst".into(), FailPolicy::FailFast);
1928        let err = match miss {
1929            Err(e) => e,
1930            Ok(_) => panic!("expected miss"),
1931        };
1932        // Base wording matches the historical `{id:?}` Debug shape;
1933        // the trailing `hint` is empty so no parenthesised clause
1934        // appears.
1935        assert_eq!(err.to_string(), "unknown reducer ReducerId(\"frst\")");
1936    }
1937
1938    #[test]
1939    fn unknown_reducer_with_suggester_appends_hint() {
1940        struct Noop;
1941        impl Reducer<i64, ()> for Noop {
1942            fn reduce(
1943                &self,
1944                _s: &[Option<i64>],
1945                _d: &[Option<()>],
1946                _w: &[ChildIndex],
1947            ) -> Result<(i64, ()), EngineError> {
1948                Ok((0, ()))
1949            }
1950        }
1951        let mut reg: ReducerRegistry<i64, (), std::io::Error> = ReducerRegistry::new();
1952        reg.register_fail_fast("first", Arc::new(Noop));
1953        let reg = reg.with_suggester(Arc::new(FixedSuggester("first")));
1954        let miss = reg.resolve(&"frst".into(), FailPolicy::FailFast);
1955        let err = match miss {
1956            Err(e) => e,
1957            Ok(_) => panic!("expected miss"),
1958        };
1959        let msg = err.to_string();
1960        assert!(
1961            msg.contains("did you mean") && msg.contains("first"),
1962            "expected hint, got: {msg}"
1963        );
1964    }
1965
1966    #[test]
1967    fn unknown_op_defaults_to_no_hint() {
1968        struct AddOp;
1969        impl Op<i64> for AddOp {
1970            fn apply(&self, _n: NodeId, args: &[i64]) -> Result<i64, EngineError> {
1971                Ok(args.iter().sum())
1972            }
1973        }
1974        let mut reg: OpRegistry<i64> = OpRegistry::new();
1975        reg.register("add", Arc::new(AddOp));
1976        let miss = reg.resolve(&"ad".into());
1977        let err = match miss {
1978            Err(e) => e,
1979            Ok(_) => panic!("expected miss"),
1980        };
1981        assert_eq!(err.to_string(), "unknown op OpId(\"ad\")");
1982    }
1983
1984    #[test]
1985    fn unknown_op_with_suggester_appends_hint() {
1986        struct AddOp;
1987        impl Op<i64> for AddOp {
1988            fn apply(&self, _n: NodeId, args: &[i64]) -> Result<i64, EngineError> {
1989                Ok(args.iter().sum())
1990            }
1991        }
1992        let mut reg: OpRegistry<i64> = OpRegistry::new();
1993        reg.register("add", Arc::new(AddOp));
1994        let reg = reg.with_suggester(Arc::new(FixedSuggester("add")));
1995        let miss = reg.resolve(&"ad".into());
1996        let err = match miss {
1997            Err(e) => e,
1998            Ok(_) => panic!("expected miss"),
1999        };
2000        let msg = err.to_string();
2001        assert!(
2002            msg.contains("did you mean") && msg.contains("add"),
2003            "expected hint, got: {msg}"
2004        );
2005    }
2006}