sim_shape/algebra/
collection.rs

1//! Collection shapes: `TableShape` with its per-field specs and extra-field
2//! policy, and `RepeatShape` for matching repeated occurrences of a shape.
3
4use std::sync::Arc;
5
6use sim_kernel::{
7    Cx, Diagnostic, Expr, Result, Symbol, Table, Value, force_list_to_vec, shape_is_subshape_of,
8};
9
10use crate::{
11    algebra::{capture_symbol, number_expr, number_value, symbol_list_expr, symbol_list_value},
12    base::{Bindings, MatchScore, Shape, ShapeDoc, ShapeMatch},
13    duplicate_keys::reject_duplicate_symbol_keys,
14};
15
16/// Shape for table values or map expressions with named field constraints.
17///
18/// Required fields must be present and accepted by their field shapes. Extra
19/// fields are controlled by [`TableExtraPolicy`].
20///
21/// ```rust
22/// # use std::sync::Arc;
23/// # use sim_kernel::{Cx, DefaultFactory, Expr, NoopEvalPolicy, Symbol};
24/// # use sim_shape::{ExprKind, ExprKindShape, Shape, TableShape};
25/// # let mut cx = Cx::new(Arc::new(NoopEvalPolicy), Arc::new(DefaultFactory));
26/// let shape = TableShape::single(
27///     Symbol::new("ok"),
28///     Arc::new(ExprKindShape::new(ExprKind::Bool)),
29/// );
30/// let expr = Expr::Map(vec![(Expr::Symbol(Symbol::new("ok")), Expr::Bool(true))]);
31///
32/// assert!(shape.check_expr(&mut cx, &expr).unwrap().accepted);
33/// ```
34#[derive(Clone)]
35pub struct TableShape {
36    fields: Vec<TableFieldSpec>,
37    extra: TableExtraPolicy,
38}
39
40/// One field constraint inside a [`TableShape`].
41#[derive(Clone)]
42pub struct TableFieldSpec {
43    /// Symbol key to look up in the table or map expression.
44    pub key: Symbol,
45    /// Shape that must accept the field value or expression.
46    pub shape: Arc<dyn Shape>,
47    /// Whether the field must be present.
48    pub required: bool,
49}
50
51/// Policy for keys not listed in a [`TableShape`].
52#[derive(Clone)]
53pub enum TableExtraPolicy {
54    /// Accept extra keys without checking their values.
55    Allow,
56    /// Reject any extra key.
57    Reject,
58    /// Check each extra value with the supplied shape.
59    Shape(Arc<dyn Shape>),
60}
61
62impl TableShape {
63    /// Build a table shape requiring a single named field, allowing extras.
64    pub fn single(key: Symbol, shape: Arc<dyn Shape>) -> Self {
65        Self::new(
66            vec![TableFieldSpec {
67                key,
68                shape,
69                required: true,
70            }],
71            TableExtraPolicy::Allow,
72        )
73    }
74
75    /// Build a table shape from explicit field specs and an extra-key policy.
76    pub fn new(fields: Vec<TableFieldSpec>, extra: TableExtraPolicy) -> Self {
77        Self { fields, extra }
78    }
79
80    /// Return the field constraints in declaration order.
81    pub fn fields(&self) -> &[TableFieldSpec] {
82        &self.fields
83    }
84
85    /// Return the policy applied to keys not listed in the field specs.
86    pub fn extra(&self) -> &TableExtraPolicy {
87        &self.extra
88    }
89}
90
91impl Shape for TableShape {
92    fn is_total(&self) -> bool {
93        self.fields.is_empty() && matches!(self.extra, TableExtraPolicy::Allow)
94    }
95
96    fn is_effectful(&self) -> bool {
97        self.fields.iter().any(|field| field.shape.is_effectful())
98            || matches!(&self.extra, TableExtraPolicy::Shape(shape) if shape.is_effectful())
99    }
100
101    fn is_subshape_of(&self, cx: &mut Cx, parent: &dyn Shape) -> Result<Option<bool>> {
102        let Some(parent) = parent.as_any().downcast_ref::<Self>() else {
103            return Ok(None);
104        };
105
106        for parent_field in parent.fields() {
107            if !parent_field_compatible(cx, self, parent_field)? {
108                return Ok(None);
109            }
110        }
111
112        for child_field in self.fields() {
113            if parent
114                .fields()
115                .iter()
116                .any(|parent_field| parent_field.key == child_field.key)
117            {
118                continue;
119            }
120            if !field_accepted_by_parent(cx, child_field, parent)? {
121                return Ok(None);
122            }
123        }
124
125        if extra_policy_at_least_as_strict(cx, &self.extra, &parent.extra)? {
126            Ok(Some(true))
127        } else {
128            Ok(None)
129        }
130    }
131
132    fn check_value(&self, cx: &mut Cx, value: Value) -> Result<ShapeMatch> {
133        if let Some(table) = value.object().as_table_impl() {
134            return self.check_table_value(cx, table);
135        }
136
137        let table_value = value.object().as_table(cx)?;
138        let Some(table) = table_value.object().as_table_impl() else {
139            return Ok(ShapeMatch::reject("shape-table: expected table"));
140        };
141        self.check_table_value(cx, table)
142    }
143
144    fn check_expr(&self, cx: &mut Cx, expr: &Expr) -> Result<ShapeMatch> {
145        let Expr::Map(entries) = expr else {
146            return Ok(ShapeMatch::reject("shape-table: expected map expression"));
147        };
148
149        let mut parsed = Vec::with_capacity(entries.len());
150        for (key, value) in entries {
151            let Expr::Symbol(key) = key else {
152                return Ok(ShapeMatch::reject("shape-table: map key must be symbol"));
153            };
154            parsed.push((key.clone(), value.clone()));
155        }
156        self.check_map_expr(cx, &parsed)
157    }
158
159    fn describe(&self, cx: &mut Cx) -> Result<ShapeDoc> {
160        let mut doc = ShapeDoc::new("table shape");
161        for field in &self.fields {
162            doc = doc.with_detail(format!("{}: {}", field.key, field.shape.describe(cx)?.name));
163        }
164        Ok(doc)
165    }
166}
167
168/// Shape for homogeneous list-like values and collection expressions.
169///
170/// `RepeatShape` checks every item with the body shape and can enforce minimum
171/// and maximum item counts.
172///
173/// ```rust
174/// # use std::sync::Arc;
175/// # use sim_kernel::{Cx, DefaultFactory, Expr, NoopEvalPolicy};
176/// # use sim_shape::{ExprKind, ExprKindShape, RepeatShape, Shape};
177/// # let mut cx = Cx::new(Arc::new(NoopEvalPolicy), Arc::new(DefaultFactory));
178/// let shape = RepeatShape::with_bounds(
179///     Arc::new(ExprKindShape::new(ExprKind::Bool)),
180///     1,
181///     Some(2),
182/// );
183///
184/// assert!(shape
185///     .check_expr(&mut cx, &Expr::Vector(vec![Expr::Bool(true)]))
186///     .unwrap()
187///     .accepted);
188/// ```
189pub struct RepeatShape {
190    body: Arc<dyn Shape>,
191    min: usize,
192    max: Option<usize>,
193}
194
195impl RepeatShape {
196    /// Build an unbounded repeat over the given body shape.
197    pub fn new(body: Arc<dyn Shape>) -> Self {
198        Self::with_bounds(body, 0, None)
199    }
200
201    /// Build a repeat with a minimum and optional maximum item count.
202    pub fn with_bounds(body: Arc<dyn Shape>, min: usize, max: Option<usize>) -> Self {
203        Self { body, min, max }
204    }
205
206    /// Return the shape applied to each item.
207    pub fn body(&self) -> &Arc<dyn Shape> {
208        &self.body
209    }
210
211    /// Return the minimum required item count.
212    pub fn min(&self) -> usize {
213        self.min
214    }
215
216    /// Return the maximum allowed item count, if bounded.
217    pub fn max(&self) -> Option<usize> {
218        self.max
219    }
220}
221
222impl Shape for RepeatShape {
223    fn is_effectful(&self) -> bool {
224        self.body.is_effectful()
225    }
226
227    fn is_subshape_of(&self, cx: &mut Cx, parent: &dyn Shape) -> Result<Option<bool>> {
228        let Some(parent) = parent.as_any().downcast_ref::<Self>() else {
229            return Ok(None);
230        };
231        if self.min < parent.min {
232            return Ok(None);
233        }
234        if !max_at_most(self.max, parent.max) {
235            return Ok(None);
236        }
237        shape_is_subshape_of(cx, self.body.as_ref(), parent.body.as_ref()).map(Some)
238    }
239
240    fn check_value(&self, cx: &mut Cx, value: Value) -> Result<ShapeMatch> {
241        let Some(list) = value.object().as_list() else {
242            let expr = value.object().as_expr(cx)?;
243            return self.check_expr(cx, &expr);
244        };
245        let items = force_list_to_vec(cx, list, "shape-repeat")?;
246        self.check_values(cx, &items)
247    }
248
249    fn check_expr(&self, cx: &mut Cx, expr: &Expr) -> Result<ShapeMatch> {
250        let items = match expr {
251            Expr::List(items) | Expr::Vector(items) | Expr::Set(items) => items,
252            _ => return Ok(ShapeMatch::reject("shape-repeat: expected list expression")),
253        };
254        let mut out = ShapeMatch::accept(MatchScore::exact(20));
255        for item in items {
256            let mut matched = self.body.check_expr(cx, item)?;
257            if !matched.accepted {
258                matched
259                    .diagnostics
260                    .insert(0, Diagnostic::error("shape-repeat: item rejected"));
261                return Ok(matched);
262            }
263            out.captures.extend(matched.captures);
264            out.score += matched.score;
265        }
266        self.finish_expr(out, items.len())
267    }
268
269    fn describe(&self, cx: &mut Cx) -> Result<ShapeDoc> {
270        let max = self
271            .max
272            .map(|max| max.to_string())
273            .unwrap_or_else(|| "unbounded".to_owned());
274        Ok(ShapeDoc::new("repeat shape")
275            .with_detail(self.body.describe(cx)?.name)
276            .with_detail(format!("min {}", self.min))
277            .with_detail(format!("max {max}")))
278    }
279}
280
281impl TableShape {
282    fn check_table_value(&self, cx: &mut Cx, table: &dyn Table) -> Result<ShapeMatch> {
283        let entries = table.entries(cx)?;
284        self.check_value_entries(cx, &entries)
285    }
286
287    fn check_value_entries(&self, cx: &mut Cx, entries: &[(Symbol, Value)]) -> Result<ShapeMatch> {
288        match reject_duplicate_symbol_keys(entries, "shape-table") {
289            Ok(()) => {}
290            Err(sim_kernel::Error::Eval(message)) => return Ok(ShapeMatch::reject(message)),
291            Err(err) => return Err(err),
292        }
293
294        let mut out = ShapeMatch::accept(MatchScore::exact(20));
295        let mut matched_keys = Vec::new();
296        let mut missing_keys = Vec::new();
297
298        for field in &self.fields {
299            let Some((_, value)) = entries.iter().find(|(key, _)| *key == field.key) else {
300                if field.required {
301                    missing_keys.push(field.key.clone());
302                }
303                continue;
304            };
305            let mut matched = field.shape.check_value(cx, value.clone())?;
306            if !matched.accepted {
307                matched
308                    .diagnostics
309                    .insert(0, Diagnostic::error("shape-table: field rejected"));
310                return Ok(matched);
311            }
312            out.captures.extend(matched.captures);
313            out.score += matched.score;
314            matched_keys.push(field.key.clone());
315        }
316
317        if !missing_keys.is_empty() {
318            let mut captures = Bindings::new();
319            captures.bind_value(
320                capture_symbol("missing-keys"),
321                symbol_list_value(cx, &missing_keys)?,
322            );
323            return Ok(ShapeMatch {
324                accepted: false,
325                captures,
326                score: MatchScore::reject(),
327                diagnostics: vec![Diagnostic::error("shape-table: missing keys")],
328            });
329        }
330
331        let field_keys = self
332            .fields
333            .iter()
334            .map(|field| field.key.clone())
335            .collect::<Vec<_>>();
336        for (key, value) in entries {
337            if field_keys.contains(key) {
338                continue;
339            }
340            match &self.extra {
341                TableExtraPolicy::Allow => {}
342                TableExtraPolicy::Reject => {
343                    return Ok(ShapeMatch::reject(format!("shape-table: extra key {key}")));
344                }
345                TableExtraPolicy::Shape(shape) => {
346                    let mut matched = shape.check_value(cx, value.clone())?;
347                    if !matched.accepted {
348                        matched
349                            .diagnostics
350                            .insert(0, Diagnostic::error("shape-table: extra value rejected"));
351                        return Ok(matched);
352                    }
353                    out.captures.extend(matched.captures);
354                    out.score += matched.score;
355                }
356            }
357        }
358
359        out.captures.bind_value(
360            capture_symbol("matched-keys"),
361            symbol_list_value(cx, &matched_keys)?,
362        );
363        Ok(out)
364    }
365
366    fn check_map_expr(&self, cx: &mut Cx, entries: &[(Symbol, Expr)]) -> Result<ShapeMatch> {
367        match reject_duplicate_symbol_keys(entries, "shape-table") {
368            Ok(()) => {}
369            Err(sim_kernel::Error::Eval(message)) => return Ok(ShapeMatch::reject(message)),
370            Err(err) => return Err(err),
371        }
372
373        let mut out = ShapeMatch::accept(MatchScore::exact(20));
374        let mut matched_keys = Vec::new();
375        let mut missing_keys = Vec::new();
376
377        for field in &self.fields {
378            let Some((_, value)) = entries.iter().find(|(key, _)| *key == field.key) else {
379                if field.required {
380                    missing_keys.push(field.key.clone());
381                }
382                continue;
383            };
384            let mut matched = field.shape.check_expr(cx, value)?;
385            if !matched.accepted {
386                matched
387                    .diagnostics
388                    .insert(0, Diagnostic::error("shape-table: field rejected"));
389                return Ok(matched);
390            }
391            out.captures.extend(matched.captures);
392            out.score += matched.score;
393            matched_keys.push(field.key.clone());
394        }
395
396        if !missing_keys.is_empty() {
397            let mut captures = Bindings::new();
398            captures.bind_expr(
399                capture_symbol("missing-keys"),
400                symbol_list_expr(&missing_keys),
401            );
402            return Ok(ShapeMatch {
403                accepted: false,
404                captures,
405                score: MatchScore::reject(),
406                diagnostics: vec![Diagnostic::error("shape-table: missing keys")],
407            });
408        }
409
410        let field_keys = self
411            .fields
412            .iter()
413            .map(|field| field.key.clone())
414            .collect::<Vec<_>>();
415        for (key, value) in entries {
416            if field_keys.contains(key) {
417                continue;
418            }
419            match &self.extra {
420                TableExtraPolicy::Allow => {}
421                TableExtraPolicy::Reject => {
422                    return Ok(ShapeMatch::reject(format!("shape-table: extra key {key}")));
423                }
424                TableExtraPolicy::Shape(shape) => {
425                    let mut matched = shape.check_expr(cx, value)?;
426                    if !matched.accepted {
427                        matched
428                            .diagnostics
429                            .insert(0, Diagnostic::error("shape-table: extra value rejected"));
430                        return Ok(matched);
431                    }
432                    out.captures.extend(matched.captures);
433                    out.score += matched.score;
434                }
435            }
436        }
437
438        out.captures.bind_expr(
439            capture_symbol("matched-keys"),
440            symbol_list_expr(&matched_keys),
441        );
442        Ok(out)
443    }
444}
445
446impl RepeatShape {
447    fn check_values(&self, cx: &mut Cx, items: &[Value]) -> Result<ShapeMatch> {
448        let mut out = ShapeMatch::accept(MatchScore::exact(20));
449        for item in items {
450            let mut matched = self.body.check_value(cx, item.clone())?;
451            if !matched.accepted {
452                matched
453                    .diagnostics
454                    .insert(0, Diagnostic::error("shape-repeat: item rejected"));
455                return Ok(matched);
456            }
457            out.captures.extend(matched.captures);
458            out.score += matched.score;
459        }
460        self.finish_value(cx, out, items.len())
461    }
462
463    fn finish_value(&self, cx: &mut Cx, mut out: ShapeMatch, count: usize) -> Result<ShapeMatch> {
464        if count < self.min {
465            return Ok(ShapeMatch::reject("shape-repeat: too few items"));
466        }
467        if matches!(self.max, Some(max) if count > max) {
468            return Ok(ShapeMatch::reject("shape-repeat: too many items"));
469        }
470        out.captures
471            .bind_value(capture_symbol("repeat-count"), number_value(cx, count)?);
472        Ok(out)
473    }
474
475    fn finish_expr(&self, mut out: ShapeMatch, count: usize) -> Result<ShapeMatch> {
476        if count < self.min {
477            return Ok(ShapeMatch::reject("shape-repeat: too few items"));
478        }
479        if matches!(self.max, Some(max) if count > max) {
480            return Ok(ShapeMatch::reject("shape-repeat: too many items"));
481        }
482        out.captures
483            .bind_expr(capture_symbol("repeat-count"), number_expr(count));
484        Ok(out)
485    }
486}
487
488fn extra_policy_at_least_as_strict(
489    cx: &mut Cx,
490    child: &TableExtraPolicy,
491    parent: &TableExtraPolicy,
492) -> Result<bool> {
493    Ok(match (child, parent) {
494        (_, TableExtraPolicy::Allow) => true,
495        (TableExtraPolicy::Reject, TableExtraPolicy::Reject | TableExtraPolicy::Shape(_)) => true,
496        (TableExtraPolicy::Shape(child), TableExtraPolicy::Shape(parent)) => {
497            shape_is_subshape_of(cx, child.as_ref(), parent.as_ref())?
498        }
499        (TableExtraPolicy::Allow, TableExtraPolicy::Reject | TableExtraPolicy::Shape(_)) => false,
500        (TableExtraPolicy::Shape(_), TableExtraPolicy::Reject) => false,
501    })
502}
503
504fn parent_field_compatible(
505    cx: &mut Cx,
506    child: &TableShape,
507    parent_field: &TableFieldSpec,
508) -> Result<bool> {
509    if let Some(child_field) = child
510        .fields()
511        .iter()
512        .find(|candidate| candidate.key == parent_field.key)
513    {
514        if parent_field.required && !child_field.required {
515            return Ok(false);
516        }
517        return shape_is_subshape_of(cx, child_field.shape.as_ref(), parent_field.shape.as_ref());
518    }
519
520    if parent_field.required {
521        return Ok(false);
522    }
523
524    match child.extra() {
525        TableExtraPolicy::Reject => Ok(true),
526        // Unchecked extras can hit this optional key with values the parent field rejects.
527        TableExtraPolicy::Allow => Ok(false),
528        TableExtraPolicy::Shape(shape) => {
529            shape_is_subshape_of(cx, shape.as_ref(), parent_field.shape.as_ref())
530        }
531    }
532}
533
534fn field_accepted_by_parent(
535    cx: &mut Cx,
536    child_field: &TableFieldSpec,
537    parent: &TableShape,
538) -> Result<bool> {
539    if let Some(parent_field) = parent
540        .fields()
541        .iter()
542        .find(|candidate| candidate.key == child_field.key)
543    {
544        return shape_is_subshape_of(cx, child_field.shape.as_ref(), parent_field.shape.as_ref());
545    }
546
547    match parent.extra() {
548        TableExtraPolicy::Allow => Ok(true),
549        TableExtraPolicy::Reject => Ok(false),
550        TableExtraPolicy::Shape(extra) => {
551            shape_is_subshape_of(cx, child_field.shape.as_ref(), extra.as_ref())
552        }
553    }
554}
555
556fn max_at_most(child: Option<usize>, parent: Option<usize>) -> bool {
557    match (child, parent) {
558        (_, None) => true,
559        (Some(child), Some(parent)) => child <= parent,
560        (None, Some(_)) => false,
561    }
562}
sim_shape/algebra/collection.rs

sim_shape/algebra/
collection.rs
