sim_shape/algebra/
boolean.rs

1//! Boolean shape combinators: `AndShape`, `OrShape`, and `NotShape`, plus the
2//! `OrStrategy` that picks between first-match and best-match disjunction.
3
4use std::sync::Arc;
5
6use sim_kernel::{Cx, Diagnostic, Expr, Result, Value, shape_is_subshape_of};
7
8use crate::{
9    algebra::{capture_symbol, number_expr, number_value},
10    base::{Bindings, MatchScore, Shape, ShapeDoc, ShapeMatch},
11};
12
13/// Shape that accepts only when every child shape accepts.
14///
15/// `AndShape` short-circuits on the first rejecting child. On success it
16/// combines child captures and adds their scores to the combiner base score.
17///
18/// ```rust
19/// # use std::sync::Arc;
20/// # use sim_kernel::{Cx, DefaultFactory, Expr, NoopEvalPolicy};
21/// # use sim_shape::{AndShape, AnyShape, ExprKind, ExprKindShape, Shape};
22/// # let mut cx = Cx::new(Arc::new(NoopEvalPolicy), Arc::new(DefaultFactory));
23/// let shape = AndShape::new(vec![
24///     Arc::new(AnyShape),
25///     Arc::new(ExprKindShape::new(ExprKind::Bool)),
26/// ]);
27///
28/// assert!(shape.check_expr(&mut cx, &Expr::Bool(true)).unwrap().accepted);
29/// assert!(!shape
30///     .check_expr(&mut cx, &Expr::String("not bool".to_owned()))
31///     .unwrap()
32///     .accepted);
33/// ```
34pub struct AndShape {
35    parts: Vec<Arc<dyn Shape>>,
36}
37
38impl AndShape {
39    /// Build a conjunction over the given child shapes.
40    pub fn new(parts: Vec<Arc<dyn Shape>>) -> Self {
41        Self { parts }
42    }
43
44    /// Return the child shapes in conjunction order.
45    pub fn parts(&self) -> &[Arc<dyn Shape>] {
46        &self.parts
47    }
48}
49
50impl Shape for AndShape {
51    fn is_total(&self) -> bool {
52        self.parts.iter().all(|part| part.is_total())
53    }
54
55    fn is_effectful(&self) -> bool {
56        self.parts.iter().any(|part| part.is_effectful())
57    }
58
59    fn is_subshape_of(&self, cx: &mut Cx, parent: &dyn Shape) -> Result<Option<bool>> {
60        for part in &self.parts {
61            if shape_is_subshape_of(cx, part.as_ref(), parent)? {
62                return Ok(Some(true));
63            }
64        }
65
66        let Some(parent) = parent.as_any().downcast_ref::<Self>() else {
67            return Ok(None);
68        };
69        for parent_part in parent.parts() {
70            let mut covered = false;
71            for part in &self.parts {
72                if shape_is_subshape_of(cx, part.as_ref(), parent_part.as_ref())? {
73                    covered = true;
74                    break;
75                }
76            }
77            if !covered {
78                return Ok(None);
79            }
80        }
81        Ok(Some(true))
82    }
83
84    fn check_value(&self, cx: &mut Cx, value: Value) -> Result<ShapeMatch> {
85        if self.parts.is_empty() {
86            return Ok(ShapeMatch::accept(MatchScore::exact(0)));
87        }
88
89        let mut out = ShapeMatch::accept(MatchScore::exact(10));
90        for part in &self.parts {
91            let mut matched = part.check_value(cx, value.clone())?;
92            if !matched.accepted {
93                matched
94                    .diagnostics
95                    .insert(0, Diagnostic::error("shape-and: child rejected"));
96                return Ok(matched);
97            }
98            out.captures.extend(matched.captures);
99            out.score += matched.score;
100        }
101        Ok(out)
102    }
103
104    fn check_expr(&self, cx: &mut Cx, expr: &Expr) -> Result<ShapeMatch> {
105        if self.parts.is_empty() {
106            return Ok(ShapeMatch::accept(MatchScore::exact(0)));
107        }
108
109        let mut out = ShapeMatch::accept(MatchScore::exact(10));
110        for part in &self.parts {
111            let mut matched = part.check_expr(cx, expr)?;
112            if !matched.accepted {
113                matched
114                    .diagnostics
115                    .insert(0, Diagnostic::error("shape-and: child rejected"));
116                return Ok(matched);
117            }
118            out.captures.extend(matched.captures);
119            out.score += matched.score;
120        }
121        Ok(out)
122    }
123
124    fn describe(&self, cx: &mut Cx) -> Result<ShapeDoc> {
125        let mut doc = ShapeDoc::new("and shape");
126        for part in &self.parts {
127            doc = doc.with_detail(part.describe(cx)?.name);
128        }
129        Ok(doc)
130    }
131}
132
133/// Branch selection policy for [`OrShape`].
134#[derive(Clone, Copy, Debug, PartialEq, Eq)]
135pub enum OrStrategy {
136    /// Return the first accepted branch in registration order.
137    FirstMatch,
138    /// Evaluate every branch and return the accepted branch with best score.
139    BestScore,
140}
141
142/// Shape that accepts when at least one child shape accepts.
143///
144/// By default, `OrShape` returns the leftmost accepted branch. Use
145/// [`OrShape::with_strategy`] with [`OrStrategy::BestScore`] when callers need
146/// all branches evaluated for score-based choice.
147///
148/// ```rust
149/// # use std::sync::Arc;
150/// # use sim_kernel::{Cx, DefaultFactory, Expr, NoopEvalPolicy};
151/// # use sim_shape::{ExprKind, ExprKindShape, OrShape, Shape};
152/// # let mut cx = Cx::new(Arc::new(NoopEvalPolicy), Arc::new(DefaultFactory));
153/// let shape = OrShape::new(vec![
154///     Arc::new(ExprKindShape::new(ExprKind::Bool)),
155///     Arc::new(ExprKindShape::new(ExprKind::String)),
156/// ]);
157///
158/// assert!(shape
159///     .check_expr(&mut cx, &Expr::String("accepted".to_owned()))
160///     .unwrap()
161///     .accepted);
162/// ```
163pub struct OrShape {
164    choices: Vec<Arc<dyn Shape>>,
165    strategy: OrStrategy,
166}
167
168impl OrShape {
169    /// Build a disjunction that returns the first accepted branch.
170    pub fn new(choices: Vec<Arc<dyn Shape>>) -> Self {
171        Self::with_strategy(choices, OrStrategy::FirstMatch)
172    }
173
174    /// Build a disjunction with an explicit branch-selection strategy.
175    pub fn with_strategy(choices: Vec<Arc<dyn Shape>>, strategy: OrStrategy) -> Self {
176        Self { choices, strategy }
177    }
178
179    /// Return the candidate branches in registration order.
180    pub fn choices(&self) -> &[Arc<dyn Shape>] {
181        &self.choices
182    }
183
184    /// Return the configured branch-selection strategy.
185    pub fn strategy(&self) -> OrStrategy {
186        self.strategy
187    }
188}
189
190impl Shape for OrShape {
191    fn is_total(&self) -> bool {
192        self.choices.iter().any(|choice| choice.is_total())
193    }
194
195    fn is_effectful(&self) -> bool {
196        self.choices.iter().any(|choice| choice.is_effectful())
197    }
198
199    fn is_subshape_of(&self, cx: &mut Cx, parent: &dyn Shape) -> Result<Option<bool>> {
200        for choice in &self.choices {
201            if !shape_is_subshape_of(cx, choice.as_ref(), parent)? {
202                return Ok(None);
203            }
204        }
205        Ok(Some(true))
206    }
207
208    fn check_value(&self, cx: &mut Cx, value: Value) -> Result<ShapeMatch> {
209        match self.strategy {
210            OrStrategy::FirstMatch => check_value_first(cx, &self.choices, value),
211            OrStrategy::BestScore => check_value_best(cx, &self.choices, value),
212        }
213    }
214
215    fn check_expr(&self, cx: &mut Cx, expr: &Expr) -> Result<ShapeMatch> {
216        match self.strategy {
217            OrStrategy::FirstMatch => check_expr_first(cx, &self.choices, expr),
218            OrStrategy::BestScore => check_expr_best(cx, &self.choices, expr),
219        }
220    }
221
222    fn describe(&self, cx: &mut Cx) -> Result<ShapeDoc> {
223        let mut doc = ShapeDoc::new("or shape");
224        for choice in &self.choices {
225            doc = doc.with_detail(choice.describe(cx)?.name);
226        }
227        Ok(doc)
228    }
229}
230
231/// Shape that accepts when the inner shape rejects.
232///
233/// `NotShape` is a predicate complement. It records the `shape/negated`
234/// capture on accepted matches and does not leak captures from the rejected
235/// inner match.
236///
237/// ```rust
238/// # use std::sync::Arc;
239/// # use sim_kernel::{Cx, DefaultFactory, Expr, NoopEvalPolicy};
240/// # use sim_shape::{ExprKind, ExprKindShape, NotShape, Shape};
241/// # let mut cx = Cx::new(Arc::new(NoopEvalPolicy), Arc::new(DefaultFactory));
242/// let shape = NotShape::new(Arc::new(ExprKindShape::new(ExprKind::Bool)));
243///
244/// assert!(shape
245///     .check_expr(&mut cx, &Expr::String("not bool".to_owned()))
246///     .unwrap()
247///     .accepted);
248/// ```
249pub struct NotShape {
250    inner: Arc<dyn Shape>,
251}
252
253impl NotShape {
254    /// Build the complement of the given inner shape.
255    pub fn new(inner: Arc<dyn Shape>) -> Self {
256        Self { inner }
257    }
258
259    /// Return the negated inner shape.
260    pub fn inner(&self) -> &Arc<dyn Shape> {
261        &self.inner
262    }
263}
264
265impl Shape for NotShape {
266    fn is_effectful(&self) -> bool {
267        self.inner.is_effectful()
268    }
269
270    fn is_subshape_of(&self, cx: &mut Cx, parent: &dyn Shape) -> Result<Option<bool>> {
271        let Some(parent) = parent.as_any().downcast_ref::<Self>() else {
272            return Ok(None);
273        };
274        shape_is_subshape_of(cx, parent.inner.as_ref(), self.inner.as_ref()).map(Some)
275    }
276
277    fn check_value(&self, cx: &mut Cx, value: Value) -> Result<ShapeMatch> {
278        let matched = self.inner.check_value(cx, value)?;
279        if matched.accepted {
280            return Ok(ShapeMatch::reject("shape-not: inner accepted"));
281        }
282        let mut out = ShapeMatch::accept(MatchScore::exact(10));
283        out.captures
284            .bind_value(capture_symbol("negated"), cx.factory().bool(true)?);
285        Ok(out)
286    }
287
288    fn check_expr(&self, cx: &mut Cx, expr: &Expr) -> Result<ShapeMatch> {
289        let matched = self.inner.check_expr(cx, expr)?;
290        if matched.accepted {
291            return Ok(ShapeMatch::reject("shape-not: inner accepted"));
292        }
293        let mut out = ShapeMatch::accept(MatchScore::exact(10));
294        out.captures
295            .bind_expr(capture_symbol("negated"), Expr::Bool(true));
296        Ok(out)
297    }
298
299    fn describe(&self, cx: &mut Cx) -> Result<ShapeDoc> {
300        Ok(ShapeDoc::new("not shape").with_detail(self.inner.describe(cx)?.name))
301    }
302}
303
304fn check_value_first(cx: &mut Cx, choices: &[Arc<dyn Shape>], value: Value) -> Result<ShapeMatch> {
305    let mut diagnostics = Vec::new();
306    for (index, choice) in choices.iter().enumerate() {
307        let mut matched = choice.check_value(cx, value.clone())?;
308        if matched.accepted {
309            matched
310                .captures
311                .bind_value(capture_symbol("branch-index"), number_value(cx, index)?);
312            return Ok(matched);
313        }
314        diagnostics.extend(matched.diagnostics);
315    }
316    reject_or(diagnostics)
317}
318
319fn check_value_best(cx: &mut Cx, choices: &[Arc<dyn Shape>], value: Value) -> Result<ShapeMatch> {
320    let mut diagnostics = Vec::new();
321    let mut best = None::<(usize, ShapeMatch)>;
322    for (index, choice) in choices.iter().enumerate() {
323        let matched = choice.check_value(cx, value.clone())?;
324        if matched.accepted {
325            let replace = best
326                .as_ref()
327                .map(|(_, current)| matched.score > current.score)
328                .unwrap_or(true);
329            if replace {
330                best = Some((index, matched));
331            }
332        } else {
333            diagnostics.extend(matched.diagnostics);
334        }
335    }
336    match best {
337        Some((index, mut matched)) => {
338            matched
339                .captures
340                .bind_value(capture_symbol("branch-index"), number_value(cx, index)?);
341            Ok(matched)
342        }
343        None => reject_or(diagnostics),
344    }
345}
346
347fn check_expr_first(cx: &mut Cx, choices: &[Arc<dyn Shape>], expr: &Expr) -> Result<ShapeMatch> {
348    let mut diagnostics = Vec::new();
349    for (index, choice) in choices.iter().enumerate() {
350        let mut matched = choice.check_expr(cx, expr)?;
351        if matched.accepted {
352            matched
353                .captures
354                .bind_expr(capture_symbol("branch-index"), number_expr(index));
355            return Ok(matched);
356        }
357        diagnostics.extend(matched.diagnostics);
358    }
359    reject_or(diagnostics)
360}
361
362fn check_expr_best(cx: &mut Cx, choices: &[Arc<dyn Shape>], expr: &Expr) -> Result<ShapeMatch> {
363    let mut diagnostics = Vec::new();
364    let mut best = None::<(usize, ShapeMatch)>;
365    for (index, choice) in choices.iter().enumerate() {
366        let matched = choice.check_expr(cx, expr)?;
367        if matched.accepted {
368            let replace = best
369                .as_ref()
370                .map(|(_, current)| matched.score > current.score)
371                .unwrap_or(true);
372            if replace {
373                best = Some((index, matched));
374            }
375        } else {
376            diagnostics.extend(matched.diagnostics);
377        }
378    }
379    match best {
380        Some((index, mut matched)) => {
381            matched
382                .captures
383                .bind_expr(capture_symbol("branch-index"), number_expr(index));
384            Ok(matched)
385        }
386        None => reject_or(diagnostics),
387    }
388}
389
390fn reject_or(mut diagnostics: Vec<Diagnostic>) -> Result<ShapeMatch> {
391    diagnostics.insert(0, Diagnostic::error("shape-or: no branch accepted"));
392    Ok(ShapeMatch {
393        accepted: false,
394        captures: Bindings::new(),
395        score: MatchScore::reject(),
396        diagnostics,
397    })
398}
sim_shape/algebra/boolean.rs

sim_shape/algebra/
boolean.rs
