sim_shape/compare/
normal.rs

1//! Shape normalization: reduce a shape to a `ShapeNormalForm` classified by
2//! `ShapeNormalKind` so comparison and relation analysis can reason uniformly.
3
4use sim_kernel::{Cx, Result, Symbol};
5
6use crate::{
7    AndShape, AnyShape, ListShape, NotShape, OneOfShape, OrShape, RepeatShape, Shape,
8    TableExtraPolicy, TableShape,
9};
10
11/// Structural summary used by conservative shape comparison.
12///
13/// Normal forms expose enough algebraic structure for relation checks without
14/// adding a closed kind enum to the kernel `Shape` trait.
15#[derive(Clone, Debug, PartialEq, Eq)]
16pub struct ShapeNormalForm {
17    /// Normalized structural kind.
18    pub kind: ShapeNormalKind,
19    /// Human-readable label from the source shape description.
20    pub label: String,
21}
22
23/// Normalized shape structure understood by comparison helpers.
24#[derive(Clone, Debug, PartialEq, Eq)]
25pub enum ShapeNormalKind {
26    /// The total `AnyShape`.
27    Any,
28    /// A symbol-bearing atomic shape.
29    Atom(Symbol),
30    /// Flattened conjunction.
31    And(Vec<ShapeNormalForm>),
32    /// Flattened disjunction, including `OneOfShape`.
33    Or(Vec<ShapeNormalForm>),
34    /// Complement of another normal form.
35    Not(Box<ShapeNormalForm>),
36    /// Fixed or variadic list structure.
37    List {
38        /// Prefix item shapes.
39        items: Vec<ShapeNormalForm>,
40        /// Optional rest shape for variadic lists.
41        rest: Option<Box<ShapeNormalForm>>,
42    },
43    /// Table fields and whether extra keys are rejected.
44    Table {
45        /// Named field shapes.
46        fields: Vec<(Symbol, ShapeNormalForm)>,
47        /// True when the table rejects extra keys.
48        closed: bool,
49    },
50    /// Repeated collection body and bounds.
51    Repeat {
52        /// Item shape.
53        body: Box<ShapeNormalForm>,
54        /// Minimum item count.
55        min: usize,
56        /// Optional maximum item count.
57        max: Option<usize>,
58    },
59    /// Shape with no exposed structure.
60    Opaque,
61}
62
63impl ShapeNormalForm {
64    fn new(kind: ShapeNormalKind, label: impl Into<String>) -> Self {
65        Self {
66            kind,
67            label: label.into(),
68        }
69    }
70}
71
72/// Build the conservative comparison normal form for a shape.
73pub fn normalize_shape(cx: &mut Cx, shape: &dyn Shape) -> Result<ShapeNormalForm> {
74    if shape.as_any().is::<AnyShape>() {
75        return Ok(ShapeNormalForm::new(ShapeNormalKind::Any, "Any"));
76    }
77
78    if let Some(and) = shape.as_any().downcast_ref::<AndShape>() {
79        let mut parts = Vec::new();
80        for part in and.parts() {
81            let normalized = normalize_shape(cx, part.as_ref())?;
82            match normalized.kind {
83                ShapeNormalKind::And(nested) => parts.extend(nested),
84                _ => parts.push(normalized),
85            }
86        }
87        return Ok(ShapeNormalForm::new(
88            ShapeNormalKind::And(parts),
89            label(cx, shape)?,
90        ));
91    }
92
93    if let Some(or) = shape.as_any().downcast_ref::<OrShape>() {
94        return normalize_or(cx, shape, or.choices());
95    }
96
97    if let Some(one_of) = shape.as_any().downcast_ref::<OneOfShape>() {
98        return normalize_or(cx, shape, one_of.choices());
99    }
100
101    if let Some(not) = shape.as_any().downcast_ref::<NotShape>() {
102        let inner = normalize_shape(cx, not.inner().as_ref())?;
103        return Ok(ShapeNormalForm::new(
104            ShapeNormalKind::Not(Box::new(inner)),
105            label(cx, shape)?,
106        ));
107    }
108
109    if let Some(list) = shape.as_any().downcast_ref::<ListShape>() {
110        let items = list
111            .items()
112            .iter()
113            .map(|item| normalize_shape(cx, item.as_ref()))
114            .collect::<Result<Vec<_>>>()?;
115        let rest = list
116            .rest()
117            .map(|rest| normalize_shape(cx, rest.as_ref()).map(Box::new))
118            .transpose()?;
119        return Ok(ShapeNormalForm::new(
120            ShapeNormalKind::List { items, rest },
121            label(cx, shape)?,
122        ));
123    }
124
125    if let Some(table) = shape.as_any().downcast_ref::<TableShape>() {
126        let fields = table
127            .fields()
128            .iter()
129            .map(|field| {
130                Ok((
131                    field.key.clone(),
132                    normalize_shape(cx, field.shape.as_ref())?,
133                ))
134            })
135            .collect::<Result<Vec<_>>>()?;
136        return Ok(ShapeNormalForm::new(
137            ShapeNormalKind::Table {
138                fields,
139                closed: matches!(table.extra(), TableExtraPolicy::Reject),
140            },
141            label(cx, shape)?,
142        ));
143    }
144
145    if let Some(repeat) = shape.as_any().downcast_ref::<RepeatShape>() {
146        let body = normalize_shape(cx, repeat.body().as_ref())?;
147        return Ok(ShapeNormalForm::new(
148            ShapeNormalKind::Repeat {
149                body: Box::new(body),
150                min: repeat.min(),
151                max: repeat.max(),
152            },
153            label(cx, shape)?,
154        ));
155    }
156
157    if let Some(symbol) = shape.symbol() {
158        return Ok(ShapeNormalForm::new(
159            ShapeNormalKind::Atom(symbol.clone()),
160            symbol.to_string(),
161        ));
162    }
163
164    Ok(ShapeNormalForm::new(
165        ShapeNormalKind::Opaque,
166        label(cx, shape)?,
167    ))
168}
169
170fn normalize_or(
171    cx: &mut Cx,
172    shape: &dyn Shape,
173    choices: &[std::sync::Arc<dyn Shape>],
174) -> Result<ShapeNormalForm> {
175    let mut out = Vec::new();
176    for choice in choices {
177        let normalized = normalize_shape(cx, choice.as_ref())?;
178        match normalized.kind {
179            ShapeNormalKind::Or(nested) => out.extend(nested),
180            _ => out.push(normalized),
181        }
182    }
183    Ok(ShapeNormalForm::new(
184        ShapeNormalKind::Or(out),
185        label(cx, shape)?,
186    ))
187}
188
189fn label(cx: &mut Cx, shape: &dyn Shape) -> Result<String> {
190    Ok(shape.describe(cx)?.name)
191}
sim_shape/compare/normal.rs

sim_shape/compare/
normal.rs
