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