sim_codec/implementation/
tree.rs

1//! Structural validation of a `LocatedExprTree`.
2//!
3//! Walks a located expr tree and checks that each node's child count and shape
4//! match its `Expr` variant, reporting any mismatch as a codec error.
5
6use sim_kernel::{CodecId, Error, Expr, LocatedExprTree, Result};
7
8/// Check that a [`LocatedExprTree`] is structurally consistent with its `Expr`.
9///
10/// Walks the tree and verifies that every node's child count and child
11/// expressions match its `Expr` variant, returning a codec error tagged `codec`
12/// on the first mismatch. A [`TreeDecoder`](crate::TreeDecoder) can run this to
13/// self-check its output before returning it.
14pub fn validate_expr_tree(codec: CodecId, tree: &LocatedExprTree) -> Result<()> {
15    fn error(codec: CodecId, message: impl Into<String>) -> Error {
16        Error::CodecError {
17            codec,
18            message: message.into(),
19        }
20    }
21
22    fn expect_children(
23        codec: CodecId,
24        tree: &LocatedExprTree,
25        expected: usize,
26        kind: &str,
27    ) -> Result<()> {
28        if tree.children.len() != expected {
29            return Err(error(
30                codec,
31                format!(
32                    "{kind} tree expected {expected} children, found {}",
33                    tree.children.len()
34                ),
35            ));
36        }
37        Ok(())
38    }
39
40    fn validate(codec: CodecId, tree: &LocatedExprTree) -> Result<()> {
41        match &tree.expr {
42            Expr::Nil
43            | Expr::Bool(_)
44            | Expr::Number(_)
45            | Expr::Symbol(_)
46            | Expr::Local(_)
47            | Expr::String(_)
48            | Expr::Bytes(_) => expect_children(codec, tree, 0, "atomic")?,
49            Expr::List(items) => {
50                if items.len() != tree.children.len() {
51                    return Err(error(codec, "list tree child count does not match expr"));
52                }
53                for (item, child) in items.iter().zip(tree.children.iter()) {
54                    if item != &child.expr {
55                        return Err(error(
56                            codec,
57                            "list tree child expr does not match expr item",
58                        ));
59                    }
60                    validate(codec, child)?;
61                }
62            }
63            Expr::Vector(items) => {
64                if items.len() != tree.children.len() {
65                    return Err(error(codec, "vector tree child count does not match expr"));
66                }
67                for (item, child) in items.iter().zip(tree.children.iter()) {
68                    if item != &child.expr {
69                        return Err(error(
70                            codec,
71                            "vector tree child expr does not match expr item",
72                        ));
73                    }
74                    validate(codec, child)?;
75                }
76            }
77            Expr::Map(entries) => {
78                if tree.children.len() != entries.len() * 2 {
79                    return Err(error(codec, "map tree child count does not match expr"));
80                }
81                for ((key, value), pair) in entries.iter().zip(tree.children.chunks_exact(2)) {
82                    if key != &pair[0].expr || value != &pair[1].expr {
83                        return Err(error(
84                            codec,
85                            "map tree child expr does not match expr entry",
86                        ));
87                    }
88                    validate(codec, &pair[0])?;
89                    validate(codec, &pair[1])?;
90                }
91            }
92            Expr::Set(items) => {
93                if items.len() != tree.children.len() {
94                    return Err(error(codec, "set tree child count does not match expr"));
95                }
96                for (item, child) in items.iter().zip(tree.children.iter()) {
97                    if item != &child.expr {
98                        return Err(error(codec, "set tree child expr does not match expr item"));
99                    }
100                    validate(codec, child)?;
101                }
102            }
103            Expr::Call { operator, args } => {
104                expect_children(codec, tree, args.len() + 1, "call")?;
105                if operator.as_ref() != &tree.children[0].expr {
106                    return Err(error(codec, "call tree operator child does not match expr"));
107                }
108                validate(codec, &tree.children[0])?;
109                for (arg, child) in args.iter().zip(tree.children[1..].iter()) {
110                    if arg != &child.expr {
111                        return Err(error(codec, "call tree arg child does not match expr"));
112                    }
113                    validate(codec, child)?;
114                }
115            }
116            Expr::Infix { left, right, .. } => {
117                expect_children(codec, tree, 2, "infix")?;
118                if left.as_ref() != &tree.children[0].expr
119                    || right.as_ref() != &tree.children[1].expr
120                {
121                    return Err(error(codec, "infix tree children do not match expr"));
122                }
123                validate(codec, &tree.children[0])?;
124                validate(codec, &tree.children[1])?;
125            }
126            Expr::Prefix { arg, .. } => {
127                expect_children(codec, tree, 1, "prefix")?;
128                if arg.as_ref() != &tree.children[0].expr {
129                    return Err(error(codec, "prefix tree child does not match expr"));
130                }
131                validate(codec, &tree.children[0])?;
132            }
133            Expr::Postfix { arg, .. } => {
134                expect_children(codec, tree, 1, "postfix")?;
135                if arg.as_ref() != &tree.children[0].expr {
136                    return Err(error(codec, "postfix tree child does not match expr"));
137                }
138                validate(codec, &tree.children[0])?;
139            }
140            Expr::Block(items) => {
141                if items.len() != tree.children.len() {
142                    return Err(error(codec, "block tree child count does not match expr"));
143                }
144                for (item, child) in items.iter().zip(tree.children.iter()) {
145                    if item != &child.expr {
146                        return Err(error(
147                            codec,
148                            "block tree child expr does not match expr item",
149                        ));
150                    }
151                    validate(codec, child)?;
152                }
153            }
154            Expr::Quote { expr, .. } => {
155                expect_children(codec, tree, 1, "quote")?;
156                if expr.as_ref() != &tree.children[0].expr {
157                    return Err(error(codec, "quote tree child does not match expr"));
158                }
159                validate(codec, &tree.children[0])?;
160            }
161            Expr::Annotated { expr, annotations } => {
162                expect_children(codec, tree, annotations.len() + 1, "annotated")?;
163                if expr.as_ref() != &tree.children[0].expr {
164                    return Err(error(codec, "annotated expr child does not match expr"));
165                }
166                validate(codec, &tree.children[0])?;
167                for ((_, value), child) in annotations.iter().zip(tree.children[1..].iter()) {
168                    if value != &child.expr {
169                        return Err(error(
170                            codec,
171                            "annotated value child does not match expr annotation",
172                        ));
173                    }
174                    validate(codec, child)?;
175                }
176            }
177            Expr::Extension { payload, .. } => {
178                expect_children(codec, tree, 1, "extension")?;
179                if payload.as_ref() != &tree.children[0].expr {
180                    return Err(error(codec, "extension tree child does not match expr"));
181                }
182                validate(codec, &tree.children[0])?;
183            }
184        }
185        Ok(())
186    }
187
188    validate(codec, tree)
189}
sim_codec/implementation/tree.rs

sim_codec/implementation/
tree.rs
