sim_kernel/
shape.rs

1//! The [`Shape`] protocol: the one shared engine for matching and binding.
2//!
3//! Shape is a first-class kernel protocol used across parsing, checking,
4//! binding, dispatch, macro syntax, codec grammar, and overload selection; the
5//! kernel defines the protocol and the match/binding contracts, while concrete
6//! shapes are implemented by the libraries.
7
8use std::{any::Any, sync::Arc};
9
10use crate::{
11    callable::Callable,
12    env::{Cx, Env},
13    error::{Diagnostic, Error, Result},
14    expr::Expr,
15    hint::{HintMetadata, diagnostic_hints_value},
16    id::{CORE_SHAPE_CLASS_ID, ShapeId, Symbol},
17    object::{Args, ClassRef, Object, RawArgs, ShapeRef},
18    value::Value,
19};
20
21/// The one shared engine for matching and binding across the runtime.
22///
23/// `Shape` is among the kernel's most important contracts: a single protocol
24/// reused for parsing, checking, binding, dispatch, macro syntax, codec
25/// grammar, lambda locals, and overload selection. It is a first-class kernel
26/// protocol -- object-accessible through [`as_shape`](crate::ObjectCompat::as_shape),
27/// callable as a matcher (every `Shape` is a [`Callable`]), and subclassable
28/// through open metadata rather than a closed enum.
29///
30/// The kernel defines only this protocol and the match/binding contracts
31/// ([`ShapeMatch`], [`ShapeBindings`], [`MatchScore`], [`ShapeDoc`]). Concrete
32/// grammars and matchers are supplied by libraries; SIM is a Rust runtime, not
33/// a Lisp runtime, so no particular surface syntax is baked in here.
34///
35/// A type checks a value with [`check_value`](Shape::check_value) and an
36/// expression with [`check_expr`](Shape::check_expr); both yield a
37/// [`ShapeMatch`]. [`describe`](Shape::describe) provides the human-facing
38/// [`ShapeDoc`]. The remaining methods carry optional identity and subshape
39/// metadata and default to neutral answers.
40///
41/// # Examples
42///
43/// ```
44/// use std::sync::Arc;
45/// use sim_kernel::{Cx, DefaultFactory, NoopEvalPolicy, Value};
46/// use sim_kernel::shape::{MatchScore, Shape, ShapeDoc, ShapeMatch};
47///
48/// struct AnyShape;
49/// impl Shape for AnyShape {
50///     fn check_value(&self, _cx: &mut Cx, _v: Value) -> sim_kernel::Result<ShapeMatch> {
51///         Ok(ShapeMatch::accept(MatchScore::exact(1)))
52///     }
53///     fn check_expr(&self, _cx: &mut Cx, _e: &sim_kernel::Expr) -> sim_kernel::Result<ShapeMatch> {
54///         Ok(ShapeMatch::accept(MatchScore::exact(1)))
55///     }
56///     fn describe(&self, _cx: &mut Cx) -> sim_kernel::Result<ShapeDoc> {
57///         Ok(ShapeDoc::new("any"))
58///     }
59/// }
60///
61/// let mut cx = Cx::new(Arc::new(NoopEvalPolicy), Arc::new(DefaultFactory));
62/// let value = cx.factory().string("ok".to_owned()).unwrap();
63/// let matched = AnyShape.check_value(&mut cx, value).unwrap();
64/// assert!(matched.accepted);
65/// ```
66pub trait Shape: Callable {
67    /// Stable [`ShapeId`] when this shape has runtime identity, else `None`.
68    fn id(&self) -> Option<ShapeId> {
69        None
70    }
71
72    /// Symbol naming this shape when it has one, else `None`.
73    fn symbol(&self) -> Option<Symbol> {
74        None
75    }
76
77    /// Parent shapes for the subshape walk; empty by default.
78    fn parents(&self, _cx: &mut Cx) -> Result<Vec<ShapeRef>> {
79        Ok(Vec::new())
80    }
81
82    /// Whether matching this shape may run effects; `false` by default.
83    fn is_effectful(&self) -> bool {
84        false
85    }
86
87    /// Whether this shape accepts every input in its domain; `false` by default.
88    fn is_total(&self) -> bool {
89        false
90    }
91
92    /// Return a concrete implication answer when this shape owns the semantics.
93    ///
94    /// `None` keeps the kernel on the generic id, symbol, Any, and parent walk
95    /// path instead of requiring a closed enum of every concrete shape kind.
96    fn is_subshape_of(&self, _cx: &mut Cx, _parent: &dyn Shape) -> Result<Option<bool>> {
97        Ok(None)
98    }
99
100    /// Check a [`Value`] against this shape, yielding a [`ShapeMatch`].
101    fn check_value(&self, cx: &mut Cx, value: Value) -> Result<ShapeMatch>;
102    /// Check an [`Expr`] against this shape, yielding a [`ShapeMatch`].
103    fn check_expr(&self, cx: &mut Cx, expr: &Expr) -> Result<ShapeMatch>;
104    /// Produce the human-facing [`ShapeDoc`] for this shape.
105    fn describe(&self, cx: &mut Cx) -> Result<ShapeDoc>;
106}
107
108impl<T> Object for T
109where
110    T: Shape + Any,
111{
112    fn display(&self, cx: &mut Cx) -> Result<String> {
113        let doc = self.describe(cx)?;
114        match self.symbol() {
115            Some(symbol) => Ok(format!("#<shape {} {}>", symbol, doc.name)),
116            None => Ok(format!("#<shape {}>", doc.name)),
117        }
118    }
119
120    fn as_any(&self) -> &dyn Any {
121        self
122    }
123}
124
125impl<T> crate::ObjectCompat for T
126where
127    T: Shape + Any,
128{
129    fn class(&self, cx: &mut Cx) -> Result<ClassRef> {
130        let symbol = Symbol::qualified("core", "Shape");
131        if let Some(value) = cx.registry().class_by_symbol(&symbol) {
132            return Ok(value.clone());
133        }
134        cx.factory().class_stub(CORE_SHAPE_CLASS_ID, symbol)
135    }
136    fn as_table(&self, cx: &mut Cx) -> Result<Value> {
137        let doc = self.describe(cx)?;
138        let mut entries = vec![
139            (Symbol::new("name"), cx.factory().string(doc.name)?),
140            (
141                Symbol::new("effectful"),
142                cx.factory().bool(self.is_effectful())?,
143            ),
144            (Symbol::new("total"), cx.factory().bool(self.is_total())?),
145        ];
146        if let Some(symbol) = self.symbol() {
147            entries.push((
148                Symbol::new("symbol"),
149                cx.factory().string(symbol.to_string())?,
150            ));
151        }
152        for (index, detail) in doc.details.into_iter().enumerate() {
153            entries.push((
154                Symbol::qualified("detail", index.to_string()),
155                cx.factory().string(detail)?,
156            ));
157        }
158        cx.factory().table(entries)
159    }
160    fn as_shape(&self) -> Option<&dyn Shape> {
161        Some(self)
162    }
163}
164
165impl<T> Callable for T
166where
167    T: Shape,
168{
169    fn call(&self, cx: &mut Cx, args: Args) -> Result<Value> {
170        let [value] = args.values() else {
171            return Err(Error::Eval("shape call expects 1 argument".to_owned()));
172        };
173        call_shape(cx, self, ShapeCallTarget::Value(value.clone()))
174    }
175
176    fn call_exprs(&self, cx: &mut Cx, args: RawArgs) -> Result<Value> {
177        let [expr] = args.exprs() else {
178            return Err(Error::Eval("shape call expects 1 expression".to_owned()));
179        };
180        call_shape(cx, self, ShapeCallTarget::Expr(expr.clone()))
181    }
182}
183
184/// Human-facing description of a [`Shape`]: a name plus optional detail lines.
185#[derive(Clone, Debug, Default, PartialEq, Eq)]
186pub struct ShapeDoc {
187    /// Short name of the shape.
188    pub name: String,
189    /// Additional detail lines describing the shape.
190    pub details: Vec<String>,
191}
192
193impl ShapeDoc {
194    /// Create a [`ShapeDoc`] with the given name and no details.
195    pub fn new(name: impl Into<String>) -> Self {
196        Self {
197            name: name.into(),
198            details: Vec::new(),
199        }
200    }
201
202    /// Append a detail line, returning the updated doc (builder style).
203    pub fn with_detail(mut self, detail: impl Into<String>) -> Self {
204        self.details.push(detail.into());
205        self
206    }
207}
208
209/// A match quality score used to rank shapes during overload selection.
210///
211/// Higher scores are preferred; [`reject`](MatchScore::reject) marks a
212/// non-match.
213#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
214pub struct MatchScore(i32);
215
216impl MatchScore {
217    /// Build a score from an explicit integer weight.
218    pub fn exact(value: i32) -> Self {
219        Self(value)
220    }
221
222    /// The score that marks a rejected match (far below any accept).
223    pub fn reject() -> Self {
224        Self(i32::MIN / 2)
225    }
226
227    /// The underlying integer weight.
228    pub fn value(self) -> i32 {
229        self.0
230    }
231}
232
233impl core::ops::AddAssign for MatchScore {
234    fn add_assign(&mut self, rhs: Self) {
235        self.0 += rhs.0;
236    }
237}
238
239/// Captures produced by a successful match: named values and named exprs.
240///
241/// A match binds names to either runtime [`Value`]s or unevaluated [`Expr`]s;
242/// the bindings can later be projected into an [`Env`].
243#[derive(Clone, Debug, Default)]
244pub struct ShapeBindings {
245    values: Vec<(Symbol, Value)>,
246    exprs: Vec<(Symbol, Expr)>,
247}
248
249impl ShapeBindings {
250    /// Create an empty set of bindings.
251    pub fn new() -> Self {
252        Self::default()
253    }
254
255    /// Bind a name to a runtime [`Value`].
256    pub fn bind_value(&mut self, name: Symbol, value: Value) {
257        self.values.push((name, value));
258    }
259
260    /// Bind a name to an unevaluated [`Expr`].
261    pub fn bind_expr(&mut self, name: Symbol, expr: Expr) {
262        self.exprs.push((name, expr));
263    }
264
265    /// Append all bindings from `other` into this set.
266    pub fn extend(&mut self, other: ShapeBindings) {
267        self.values.extend(other.values);
268        self.exprs.extend(other.exprs);
269    }
270
271    /// The value bindings, in insertion order.
272    pub fn values(&self) -> &[(Symbol, Value)] {
273        &self.values
274    }
275
276    /// The expr bindings, in insertion order.
277    pub fn exprs(&self) -> &[(Symbol, Expr)] {
278        &self.exprs
279    }
280
281    /// Install these bindings as a fresh child of the context's current env.
282    pub fn into_env(self, cx: &mut Cx) -> Result<()> {
283        let env = self.into_child_env(cx)?;
284        *cx.env_mut() = env;
285        Ok(())
286    }
287
288    /// Build a child [`Env`] from the context's env populated with these
289    /// bindings, without installing it.
290    pub fn into_child_env(self, cx: &mut Cx) -> Result<Env> {
291        let mut env = Env::child(Arc::new(cx.env().clone()));
292        for (name, value) in self.values {
293            env.define(name, value);
294        }
295        for (name, expr) in self.exprs {
296            let value = cx.factory().expr(expr)?;
297            env.define(name, value);
298        }
299        Ok(env)
300    }
301}
302
303/// The outcome of checking a value or expr against a [`Shape`].
304///
305/// Carries acceptance, captured [`ShapeBindings`], a [`MatchScore`] for
306/// ranking, and any [`Diagnostic`]s gathered during the check.
307///
308/// # Examples
309///
310/// ```
311/// use sim_kernel::shape::{MatchScore, ShapeMatch};
312///
313/// let ok = ShapeMatch::accept(MatchScore::exact(3));
314/// assert!(ok.accepted);
315/// assert_eq!(ok.score.value(), 3);
316///
317/// let no = ShapeMatch::reject("expected a string");
318/// assert!(!no.accepted);
319/// assert_eq!(no.diagnostics.len(), 1);
320/// ```
321#[derive(Clone, Debug)]
322pub struct ShapeMatch {
323    /// Whether the input satisfied the shape.
324    pub accepted: bool,
325    /// Names captured by the match.
326    pub captures: ShapeBindings,
327    /// Ranking score for overload selection.
328    pub score: MatchScore,
329    /// Diagnostics gathered while matching.
330    pub diagnostics: Vec<Diagnostic>,
331}
332
333impl ShapeMatch {
334    /// An accepted match with the given score and no captures or diagnostics.
335    pub fn accept(score: MatchScore) -> Self {
336        Self {
337            accepted: true,
338            captures: ShapeBindings::new(),
339            score,
340            diagnostics: Vec::new(),
341        }
342    }
343
344    /// A rejected match carrying a single error diagnostic.
345    pub fn reject(message: impl Into<String>) -> Self {
346        Self {
347            accepted: false,
348            captures: ShapeBindings::new(),
349            score: MatchScore::reject(),
350            diagnostics: vec![Diagnostic::error(message)],
351        }
352    }
353
354    /// A rejected match carrying one already-built diagnostic.
355    pub fn reject_with_diagnostic(diagnostic: Diagnostic) -> Self {
356        Self {
357            accepted: false,
358            captures: ShapeBindings::new(),
359            score: MatchScore::reject(),
360            diagnostics: vec![diagnostic],
361        }
362    }
363}
364
365// sim-non-citizen(reason = "shape match result projection; canonical data is exposed as a table", kind = "marker", descriptor = "")
366/// Object wrapper exposing a [`ShapeMatch`] to the runtime as a table.
367#[derive(Clone, Debug)]
368pub struct ShapeMatchObject {
369    matched: ShapeMatch,
370}
371
372impl ShapeMatchObject {
373    /// Wrap a [`ShapeMatch`] as a runtime object.
374    pub fn new(matched: ShapeMatch) -> Self {
375        Self { matched }
376    }
377
378    /// Borrow the wrapped [`ShapeMatch`].
379    pub fn matched(&self) -> &ShapeMatch {
380        &self.matched
381    }
382}
383
384impl Object for ShapeMatchObject {
385    fn display(&self, _cx: &mut Cx) -> Result<String> {
386        Ok(format!(
387            "#<shape-match {} score={}>",
388            if self.matched.accepted {
389                "accepted"
390            } else {
391                "rejected"
392            },
393            self.matched.score.value()
394        ))
395    }
396
397    fn as_any(&self) -> &dyn Any {
398        self
399    }
400}
401
402impl crate::ObjectCompat for ShapeMatchObject {
403    fn class(&self, cx: &mut Cx) -> Result<ClassRef> {
404        let symbol = Symbol::qualified("core", "ShapeMatch");
405        if let Some(value) = cx.registry().class_by_symbol(&symbol) {
406            return Ok(value.clone());
407        }
408        cx.factory()
409            .class_stub(crate::id::CORE_SHAPE_MATCH_CLASS_ID, symbol)
410    }
411    fn truth(&self, _cx: &mut Cx) -> Result<bool> {
412        Ok(self.matched.accepted)
413    }
414    fn as_table(&self, cx: &mut Cx) -> Result<Value> {
415        shape_match_table(cx, &self.matched)
416    }
417    fn as_expr(&self, cx: &mut Cx) -> Result<Expr> {
418        self.as_table(cx)?.object().as_expr(cx)
419    }
420}
421
422/// A coarse classifier over [`Expr`] variants, used by grammar shapes.
423///
424/// Each variant names a structural kind of expression; [`matches`](ExprKind::matches)
425/// tests an [`Expr`] against the kind and [`name`](ExprKind::name) gives its
426/// stable lowercase tag.
427#[derive(Clone, Debug, PartialEq, Eq)]
428pub enum ExprKind {
429    /// The nil expression.
430    Nil,
431    /// A boolean literal.
432    Bool,
433    /// A number literal.
434    Number,
435    /// A symbol.
436    Symbol,
437    /// A string literal.
438    String,
439    /// A byte-string literal.
440    Bytes,
441    /// A list form.
442    List,
443    /// A vector form.
444    Vector,
445    /// A map form.
446    Map,
447    /// A set form.
448    Set,
449    /// A call form.
450    Call,
451    /// An infix operator form.
452    Infix,
453    /// A prefix operator form.
454    Prefix,
455    /// A postfix operator form.
456    Postfix,
457    /// A block form.
458    Block,
459    /// A quote form.
460    Quote,
461    /// An annotated form.
462    Annotated,
463    /// An extension form.
464    Extension,
465}
466
467impl ExprKind {
468    /// Whether `expr` is an instance of this structural kind.
469    pub fn matches(&self, expr: &Expr) -> bool {
470        matches!(
471            (self, expr),
472            (Self::Nil, Expr::Nil)
473                | (Self::Bool, Expr::Bool(_))
474                | (Self::Number, Expr::Number(_))
475                | (Self::Symbol, Expr::Symbol(_))
476                | (Self::String, Expr::String(_))
477                | (Self::Bytes, Expr::Bytes(_))
478                | (Self::List, Expr::List(_))
479                | (Self::Vector, Expr::Vector(_))
480                | (Self::Map, Expr::Map(_))
481                | (Self::Set, Expr::Set(_))
482                | (Self::Call, Expr::Call { .. })
483                | (Self::Infix, Expr::Infix { .. })
484                | (Self::Prefix, Expr::Prefix { .. })
485                | (Self::Postfix, Expr::Postfix { .. })
486                | (Self::Block, Expr::Block(_))
487                | (Self::Quote, Expr::Quote { .. })
488                | (Self::Annotated, Expr::Annotated { .. })
489                | (Self::Extension, Expr::Extension { .. })
490        )
491    }
492
493    /// The stable lowercase tag for this kind (e.g. `"string"`).
494    pub fn name(&self) -> &'static str {
495        match self {
496            Self::Nil => "nil",
497            Self::Bool => "bool",
498            Self::Number => "number",
499            Self::Symbol => "symbol",
500            Self::String => "string",
501            Self::Bytes => "bytes",
502            Self::List => "list",
503            Self::Vector => "vector",
504            Self::Map => "map",
505            Self::Set => "set",
506            Self::Call => "call",
507            Self::Infix => "infix",
508            Self::Prefix => "prefix",
509            Self::Postfix => "postfix",
510            Self::Block => "block",
511            Self::Quote => "quote",
512            Self::Annotated => "annotated",
513            Self::Extension => "extension",
514        }
515    }
516}
517
518/// What a [`call_shape`] invocation checks: a runtime value or an expr.
519#[derive(Clone, Debug)]
520pub enum ShapeCallTarget {
521    /// Check a runtime [`Value`].
522    Value(Value),
523    /// Check an [`Expr`].
524    Expr(Expr),
525}
526
527/// Run a shape against a [`ShapeCallTarget`] and return the match as a value.
528///
529/// This is the matcher-call path: it dispatches to
530/// [`check_value`](Shape::check_value) or [`check_expr`](Shape::check_expr) and
531/// wraps the [`ShapeMatch`] via [`shape_match_value`].
532pub fn call_shape(cx: &mut Cx, shape: &dyn Shape, target: ShapeCallTarget) -> Result<Value> {
533    let matched = match target {
534        ShapeCallTarget::Value(value) => shape.check_value(cx, value)?,
535        ShapeCallTarget::Expr(expr) => shape.check_expr(cx, &expr)?,
536    };
537    shape_match_value(cx, matched)
538}
539
540/// Wrap a [`ShapeMatch`] as an opaque [`ShapeMatchObject`] runtime value.
541pub fn shape_match_value(cx: &mut Cx, matched: ShapeMatch) -> Result<Value> {
542    cx.factory()
543        .opaque(Arc::new(ShapeMatchObject::new(matched)))
544}
545
546/// Decide whether `child` is a subshape of `parent`.
547///
548/// The generic walk compares ids and symbols, consults the shape's own
549/// [`is_subshape_of`](Shape::is_subshape_of) override, treats the core `Any`
550/// and `AnyShape` symbols as a top for non-effectful shapes, and otherwise
551/// recurses through the declared [`parents`](Shape::parents).
552pub fn shape_is_subshape_of(cx: &mut Cx, child: &dyn Shape, parent: &dyn Shape) -> Result<bool> {
553    if let (Some(child_id), Some(parent_id)) = (child.id(), parent.id())
554        && child_id == parent_id
555    {
556        return Ok(true);
557    }
558    if let (Some(child_symbol), Some(parent_symbol)) = (child.symbol(), parent.symbol())
559        && child_symbol == parent_symbol
560    {
561        return Ok(true);
562    }
563    if let Some(answer) = child.is_subshape_of(cx, parent)? {
564        return Ok(answer);
565    }
566    if matches!(
567        parent.symbol(),
568        Some(symbol)
569            if symbol == Symbol::qualified("core", "Any")
570                || symbol == Symbol::qualified("core", "AnyShape")
571    ) && !child.is_effectful()
572    {
573        return Ok(true);
574    }
575    for candidate in child.parents(cx)? {
576        let Some(candidate) = candidate.object().as_shape() else {
577            continue;
578        };
579        if shape_is_subshape_of(cx, candidate, parent)? {
580            return Ok(true);
581        }
582    }
583    Ok(false)
584}
585
586fn shape_match_table(cx: &mut Cx, matched: &ShapeMatch) -> Result<Value> {
587    let value_captures = cx.factory().table(matched.captures.values().to_vec())?;
588    let expr_captures = cx.factory().table(
589        matched
590            .captures
591            .exprs()
592            .iter()
593            .map(|(symbol, expr)| Ok((symbol.clone(), cx.factory().expr(expr.clone())?)))
594            .collect::<Result<Vec<_>>>()?,
595    )?;
596    let diagnostics = matched
597        .diagnostics
598        .clone()
599        .into_iter()
600        .map(|diagnostic| diagnostic_value(cx, diagnostic))
601        .collect::<Result<Vec<_>>>()?;
602    let diagnostics = cx.factory().list(diagnostics)?;
603    cx.factory().table(vec![
604        (
605            Symbol::new("accepted"),
606            cx.factory().bool(matched.accepted)?,
607        ),
608        (
609            Symbol::new("score"),
610            cx.factory().number_literal(
611                Symbol::qualified("numbers", "f64"),
612                matched.score.value().to_string(),
613            )?,
614        ),
615        (Symbol::qualified("captures", "value"), value_captures),
616        (Symbol::qualified("captures", "expr"), expr_captures),
617        (Symbol::new("diagnostics"), diagnostics),
618    ])
619}
620
621fn diagnostic_value(cx: &mut Cx, diagnostic: Diagnostic) -> Result<Value> {
622    let hints = diagnostic_hints_value(cx, &diagnostic)?;
623    let severity = match diagnostic.severity {
624        crate::error::Severity::Error => "error",
625        crate::error::Severity::Warning => "warning",
626        crate::error::Severity::Info => "info",
627        crate::error::Severity::Note => "note",
628    };
629    let related = diagnostic
630        .related
631        .into_iter()
632        .filter(|related| !HintMetadata::is_hint_diagnostic(related))
633        .map(|related| diagnostic_value(cx, related))
634        .collect::<Result<Vec<_>>>()?;
635    let related = cx.factory().list(related)?;
636    let mut entries = vec![
637        (
638            Symbol::new("severity"),
639            cx.factory().symbol(Symbol::new(severity))?,
640        ),
641        (
642            Symbol::new("message"),
643            cx.factory().string(diagnostic.message)?,
644        ),
645        (Symbol::new("related"), related),
646        (Symbol::new("hints"), hints),
647    ];
648    if let Some(code) = diagnostic.code {
649        entries.push((Symbol::new("code"), cx.factory().symbol(code)?));
650    }
651    cx.factory().table(entries)
652}
653
654#[cfg(test)]
655#[path = "shape_tests.rs"]
656mod tests;
sim_kernel/shape.rs

sim_kernel/
shape.rs
