sim_shape/
recursive.rs

1//! Recursive shape descriptors backed by named definitions.
2
3use std::cell::RefCell;
4use std::sync::Arc;
5
6use sim_kernel::{Cx, Expr, Result, Shape, ShapeDoc, ShapeMatch, Symbol, Value};
7
8use crate::recursion::DepthGuard;
9
10type DefFrame = Vec<(Symbol, Arc<dyn Shape>)>;
11
12thread_local! {
13    static DEF_STACK: RefCell<Vec<DefFrame>> = RefCell::new(Vec::new());
14}
15
16/// A shape with a root descriptor and named definitions available to refs.
17#[derive(Clone)]
18pub struct ShapeDefs {
19    /// The root shape checked by this descriptor.
20    pub root: Arc<dyn Shape>,
21    /// Named shapes that [`ShapeDefRef`] entries may resolve while checking.
22    pub defs: Vec<(Symbol, Arc<dyn Shape>)>,
23}
24
25impl ShapeDefs {
26    /// Build a recursive descriptor from a root shape and named definitions.
27    pub fn new(root: Arc<dyn Shape>, defs: Vec<(Symbol, Arc<dyn Shape>)>) -> Self {
28        Self { root, defs }
29    }
30
31    /// Root shape for this recursive descriptor.
32    pub fn root(&self) -> &Arc<dyn Shape> {
33        &self.root
34    }
35
36    /// Named definitions available while checking this descriptor.
37    pub fn defs(&self) -> &[(Symbol, Arc<dyn Shape>)] {
38        &self.defs
39    }
40}
41
42/// A reference to a named shape inside the surrounding [`ShapeDefs`].
43#[derive(Clone)]
44pub struct ShapeDefRef {
45    /// The definition name to resolve.
46    pub name: Symbol,
47}
48
49impl ShapeDefRef {
50    /// Build a definition reference.
51    pub fn new(name: Symbol) -> Self {
52        Self { name }
53    }
54
55    /// The definition name this reference resolves.
56    pub fn name(&self) -> &Symbol {
57        &self.name
58    }
59}
60
61impl Shape for ShapeDefs {
62    fn symbol(&self) -> Option<Symbol> {
63        Some(Symbol::qualified("shape", "Defs"))
64    }
65
66    fn is_effectful(&self) -> bool {
67        self.root.is_effectful() || self.defs.iter().any(|(_, shape)| shape.is_effectful())
68    }
69
70    fn is_total(&self) -> bool {
71        self.root.is_total()
72    }
73
74    fn check_value(&self, cx: &mut Cx, value: Value) -> Result<ShapeMatch> {
75        let _scope = DefScope::push(&self.defs);
76        self.root.check_value(cx, value)
77    }
78
79    fn check_expr(&self, cx: &mut Cx, expr: &Expr) -> Result<ShapeMatch> {
80        let _scope = DefScope::push(&self.defs);
81        self.root.check_expr(cx, expr)
82    }
83
84    fn describe(&self, cx: &mut Cx) -> Result<ShapeDoc> {
85        let mut doc = ShapeDoc::new("shape defs").with_detail(self.root.describe(cx)?.name);
86        for (name, _) in &self.defs {
87            doc = doc.with_detail(name.to_string());
88        }
89        Ok(doc)
90    }
91}
92
93impl Shape for ShapeDefRef {
94    fn symbol(&self) -> Option<Symbol> {
95        Some(Symbol::qualified("shape", "Ref"))
96    }
97
98    fn check_value(&self, cx: &mut Cx, value: Value) -> Result<ShapeMatch> {
99        self.with_resolved_shape(|shape| shape.check_value(cx, value))
100    }
101
102    fn check_expr(&self, cx: &mut Cx, expr: &Expr) -> Result<ShapeMatch> {
103        self.with_resolved_shape(|shape| shape.check_expr(cx, expr))
104    }
105
106    fn describe(&self, _cx: &mut Cx) -> Result<ShapeDoc> {
107        Ok(ShapeDoc::new("shape ref").with_detail(self.name.to_string()))
108    }
109}
110
111impl ShapeDefRef {
112    fn with_resolved_shape(
113        &self,
114        check: impl FnOnce(Arc<dyn Shape>) -> Result<ShapeMatch>,
115    ) -> Result<ShapeMatch> {
116        let Some(_guard) = DepthGuard::enter() else {
117            return Ok(ShapeMatch::reject(format!(
118                "shape-ref: recursion budget exhausted while resolving {}",
119                self.name
120            )));
121        };
122        let Some(shape) = resolve_def(&self.name) else {
123            return Ok(ShapeMatch::reject(format!(
124                "shape-ref: undefined reference {}",
125                self.name
126            )));
127        };
128        check(shape)
129    }
130}
131
132struct DefScope;
133
134impl DefScope {
135    fn push(defs: &[(Symbol, Arc<dyn Shape>)]) -> Self {
136        DEF_STACK.with(|stack| stack.borrow_mut().push(defs.to_vec()));
137        Self
138    }
139}
140
141impl Drop for DefScope {
142    fn drop(&mut self) {
143        DEF_STACK.with(|stack| {
144            stack.borrow_mut().pop();
145        });
146    }
147}
148
149fn resolve_def(name: &Symbol) -> Option<Arc<dyn Shape>> {
150    DEF_STACK.with(|stack| {
151        stack.borrow().iter().rev().find_map(|frame| {
152            frame
153                .iter()
154                .rev()
155                .find(|(candidate, _)| candidate == name)
156                .map(|(_, shape)| shape.clone())
157        })
158    })
159}
160
161#[cfg(test)]
162mod tests {
163    use std::sync::Arc;
164
165    use sim_citizen::{CitizenLib, value_from_expr};
166    use sim_kernel::{
167        Cx, DefaultFactory, Expr, NoopEvalPolicy, NumberLiteral, Symbol, read_construct_capability,
168    };
169
170    use super::{ShapeDefRef, ShapeDefs};
171    use crate::grammar::{Production, shape_grammar_graph};
172    use crate::recursion::MAX_SHAPE_DEPTH;
173    use crate::{AnyShape, ExprKind, ExprKindShape, ListShape, OneOfShape, Shape};
174
175    fn number_expr(text: &str) -> Expr {
176        Expr::Number(NumberLiteral {
177            domain: Symbol::qualified("numbers", "f64"),
178            canonical: text.to_owned(),
179        })
180    }
181
182    fn list_expr(depth: usize) -> Expr {
183        let mut expr = Expr::Nil;
184        for index in 0..depth {
185            expr = Expr::List(vec![number_expr(&index.to_string()), expr]);
186        }
187        expr
188    }
189
190    fn node_shape() -> ShapeDefs {
191        let node = Symbol::new("Node");
192        ShapeDefs::new(
193            Arc::new(ShapeDefRef::new(node.clone())),
194            vec![(
195                node.clone(),
196                Arc::new(OneOfShape::new(vec![
197                    Arc::new(ExprKindShape::new(ExprKind::Nil)),
198                    Arc::new(ListShape::new(vec![
199                        Arc::new(ExprKindShape::new(ExprKind::Number)),
200                        Arc::new(ShapeDefRef::new(node)),
201                    ])),
202                ])),
203            )],
204        )
205    }
206
207    #[test]
208    fn recursive_shape_accepts_exprs_and_values_within_depth_bound() {
209        let shape = node_shape();
210        let expr = list_expr(MAX_SHAPE_DEPTH - 1);
211        let mut cx = Cx::new(Arc::new(NoopEvalPolicy), Arc::new(DefaultFactory));
212
213        assert!(shape.check_expr(&mut cx, &expr).unwrap().accepted);
214
215        let value = value_from_expr(&mut cx, &expr).unwrap();
216        assert!(shape.check_value(&mut cx, value).unwrap().accepted);
217    }
218
219    #[test]
220    fn recursive_shape_rejects_when_depth_budget_is_spent() {
221        let shape = node_shape();
222        let expr = list_expr(MAX_SHAPE_DEPTH);
223        let mut cx = Cx::new(Arc::new(NoopEvalPolicy), Arc::new(DefaultFactory));
224        let matched = shape.check_expr(&mut cx, &expr).unwrap();
225
226        assert!(!matched.accepted);
227        assert!(
228            matched
229                .diagnostics
230                .iter()
231                .any(|diagnostic| diagnostic.message.contains("recursion budget exhausted"))
232        );
233    }
234
235    #[test]
236    fn recursive_shape_rejects_undefined_refs() {
237        let shape = ShapeDefs::new(
238            Arc::new(ShapeDefRef::new(Symbol::new("Missing"))),
239            Vec::new(),
240        );
241        let mut cx = Cx::new(Arc::new(NoopEvalPolicy), Arc::new(DefaultFactory));
242        let matched = shape.check_expr(&mut cx, &Expr::Nil).unwrap();
243
244        assert!(!matched.accepted);
245        assert!(
246            matched
247                .diagnostics
248                .iter()
249                .any(|diagnostic| diagnostic.message.contains("undefined reference Missing"))
250        );
251    }
252
253    #[test]
254    fn recursive_shape_lowers_to_ref_and_defs() {
255        let graph = shape_grammar_graph(&node_shape()).unwrap();
256        let node = Symbol::new("Node");
257
258        assert_eq!(graph.root, Production::Ref(node.clone()));
259        assert_eq!(graph.defs.len(), 1);
260        assert_eq!(graph.defs[0].0, node.clone());
261        assert!(contains_ref(&graph.defs[0].1, &node));
262    }
263
264    #[test]
265    fn recursive_shape_roundtrips_through_read_construct() {
266        let mut cx = Cx::new(Arc::new(NoopEvalPolicy), Arc::new(DefaultFactory));
267        cx.load_lib(&CitizenLib::all()).unwrap();
268        cx.grant(read_construct_capability());
269        let node = Symbol::new("Node");
270        let shape: Arc<dyn Shape> = Arc::new(ShapeDefs::new(
271            Arc::new(ShapeDefRef::new(node.clone())),
272            vec![(node, Arc::new(AnyShape))],
273        ));
274        let encoded = crate::citizen::encode_shape_expr(shape.as_ref()).unwrap();
275        let Expr::Call { operator, args } = &encoded else {
276            panic!("shape defs should encode as a constructor call");
277        };
278        let Expr::Symbol(class) = operator.as_ref() else {
279            panic!("shape defs constructor operator should be a symbol");
280        };
281        let values = args
282            .iter()
283            .map(|arg| value_from_expr(&mut cx, arg))
284            .collect::<sim_kernel::Result<Vec<_>>>()
285            .unwrap();
286        let decoded = cx.read_construct(class, values).unwrap();
287        let decoded_shape = decoded
288            .object()
289            .as_shape()
290            .expect("shape read-construct should return a shape value");
291
292        assert!(
293            decoded_shape
294                .check_expr(&mut cx, &Expr::Bool(true))
295                .unwrap()
296                .accepted
297        );
298        assert_eq!(
299            crate::citizen::encode_shape_expr(decoded_shape).unwrap(),
300            encoded
301        );
302    }
303
304    fn contains_ref(production: &Production, name: &Symbol) -> bool {
305        match production {
306            Production::Ref(candidate) => candidate == name,
307            Production::Seq(items) | Production::Alt(items) => {
308                items.iter().any(|item| contains_ref(item, name))
309            }
310            Production::Repeat { inner, .. } => contains_ref(inner, name),
311            Production::Call { head, args } => {
312                contains_ref(head, name) || args.iter().any(|arg| contains_ref(arg, name))
313            }
314            Production::Terminal(_) => false,
315        }
316    }
317}
sim_shape/recursive.rs

sim_shape/
recursive.rs
