1use std::collections::HashMap;
2
3use m2_syn::visit::Visit;
4use m2_syn::{
5 Array, BinaryExpr, BinaryOperator, Component, Expr, ExprPack, ForLoop, Holder, IfStatement,
6 IntegerLiteral, IterationDomain, List, LoopBody, ParseError, ReturnExpr, Sequence,
7 StringLiteral, Symbol, WhileLoop, parse_file,
8};
9
10#[derive(Debug, Clone, PartialEq, Eq)]
11enum TypeRange<T, Q> {
12 Known(Vec<T>),
13 Deferred(Q),
14}
15
16#[derive(Debug, Clone, PartialEq, Eq)]
17struct Fact<T, V, Q> {
18 types: TypeRange<T, Q>,
19 value: Option<V>,
20}
21
22#[derive(Debug, Clone, Copy)]
23enum CollectionKind {
24 Array,
25 List,
26 Sequence,
27}
28
29#[derive(Debug, Clone, Copy)]
30enum ControlKind {
31 If,
32 For,
33 While,
34 Return,
35}
36
37trait InferenceContext {
38 type Type: Clone;
39 type Value: Clone;
40 type Query: Clone;
41
42 fn integer(&self, literal: &IntegerLiteral) -> FactOf<Self>;
43 fn string(&self, literal: &StringLiteral) -> FactOf<Self>;
44 fn symbol(&self, symbol: &Symbol) -> FactOf<Self>;
45 fn binary(&self, node: &BinaryExpr, left: FactOf<Self>, right: FactOf<Self>) -> FactOf<Self>;
46 fn collection(&self, kind: CollectionKind, elements: Vec<FactOf<Self>>) -> FactOf<Self>;
47 fn control(&self, kind: ControlKind, neighbours: Vec<FactOf<Self>>) -> FactOf<Self>;
48}
49
50type FactOf<C> = Fact<
51 <C as InferenceContext>::Type,
52 <C as InferenceContext>::Value,
53 <C as InferenceContext>::Query,
54>;
55
56struct TypeChecker<'context, C: InferenceContext> {
57 context: &'context C,
58 results: Vec<FactOf<C>>,
59}
60
61impl<C: InferenceContext> TypeChecker<'_, C> {
62 fn infer(&mut self, expression: &Expr) -> FactOf<C> {
63 let old_len = self.results.len();
64 self.visit_expr(expression);
65 assert_eq!(self.results.len(), old_len + 1);
66 self.results.pop().expect("expression produced one fact")
67 }
68
69 fn components(&mut self, components: &Option<ExprPack>) -> Vec<FactOf<C>> {
70 components
71 .iter()
72 .flat_map(|pack| pack.pack.iter())
73 .filter_map(|component| match component {
74 Component::Expr(expression) => Some(self.infer(expression)),
75 Component::Empty(_) => None,
76 })
77 .collect()
78 }
79
80 fn loop_body(&mut self, body: &LoopBody) -> Vec<FactOf<C>> {
81 let mut neighbours = Vec::new();
82 if let Some(step) = &body.list_step {
83 neighbours.push(self.infer(&step.expr));
84 }
85 if let Some(step) = &body.do_step {
86 neighbours.push(self.infer(&step.statement));
87 }
88 neighbours
89 }
90}
91
92impl<'ast, C: InferenceContext> Visit<'ast> for TypeChecker<'_, C> {
93 fn visit_integer_literal(&mut self, literal: &'ast IntegerLiteral) {
94 self.results.push(self.context.integer(literal));
95 }
96
97 fn visit_string_literal(&mut self, literal: &'ast StringLiteral) {
98 self.results.push(self.context.string(literal));
99 }
100
101 fn visit_symbol(&mut self, symbol: &'ast Symbol) {
102 self.results.push(self.context.symbol(symbol));
103 }
104
105 fn visit_binary_expr(&mut self, expression: &'ast BinaryExpr) {
106 let left = self.infer(&expression.left_operand);
107 let right = self.infer(&expression.right_operand);
108 self.results
109 .push(self.context.binary(expression, left, right));
110 }
111
112 fn visit_holder(&mut self, expression: &'ast Holder) {
113 let fact = expression.value.as_deref().map(|value| self.infer(value));
114 self.results.push(fact.unwrap_or_else(|| {
115 self.context
116 .collection(CollectionKind::Sequence, Vec::new())
117 }));
118 }
119
120 fn visit_array(&mut self, array: &'ast Array) {
121 let elements = self.components(&array.elements);
122 self.results
123 .push(self.context.collection(CollectionKind::Array, elements));
124 }
125
126 fn visit_list(&mut self, list: &'ast List) {
127 let elements = self.components(&list.elements);
128 self.results
129 .push(self.context.collection(CollectionKind::List, elements));
130 }
131
132 fn visit_sequence(&mut self, sequence: &'ast Sequence) {
133 let elements = self.components(&sequence.elements);
134 self.results
135 .push(self.context.collection(CollectionKind::Sequence, elements));
136 }
137
138 fn visit_if_statement(&mut self, statement: &'ast IfStatement) {
139 let mut neighbours = vec![
140 self.infer(&statement.condition),
141 self.infer(&statement.then_clause.expr),
142 ];
143 if let Some(clause) = &statement.else_clause {
144 neighbours.push(self.infer(&clause.expr));
145 }
146 self.results
147 .push(self.context.control(ControlKind::If, neighbours));
148 }
149
150 fn visit_for_loop(&mut self, statement: &'ast ForLoop) {
151 let mut neighbours = Vec::new();
152 if let Some(domain) = &statement.iteration_domain {
153 match domain {
154 IterationDomain::IterRange(range) => {
155 if let Some(bound) = &range.lower_bound {
156 neighbours.push(self.infer(&bound.value));
157 }
158 if let Some(bound) = &range.upper_bound {
159 neighbours.push(self.infer(&bound.value));
160 }
161 }
162 IterationDomain::IterIn(domain) => {
163 neighbours.push(self.infer(&domain.collection));
164 }
165 }
166 }
167 neighbours.extend(
168 statement
169 .when_condition
170 .iter()
171 .map(|condition| self.infer(&condition.condition)),
172 );
173 neighbours.extend(self.loop_body(&statement.body));
174 self.results
175 .push(self.context.control(ControlKind::For, neighbours));
176 }
177
178 fn visit_while_loop(&mut self, statement: &'ast WhileLoop) {
179 let mut neighbours = vec![self.infer(&statement.condition)];
180 neighbours.extend(self.loop_body(&statement.body));
181 self.results
182 .push(self.context.control(ControlKind::While, neighbours));
183 }
184
185 fn visit_return_expr(&mut self, statement: &'ast ReturnExpr) {
186 let neighbours = statement
187 .value
188 .iter()
189 .map(|value| self.infer(value))
190 .collect();
191 self.results
192 .push(self.context.control(ControlKind::Return, neighbours));
193 }
194}
195
196#[derive(Debug, Clone, PartialEq, Eq)]
197enum DemoType {
198 Integer,
199 Number,
200 String,
201 Array,
202 List,
203 Sequence,
204 Thing,
205}
206
207#[derive(Debug, Clone, PartialEq, Eq)]
208enum DemoValue {
209 Integer(i64),
210}
211
212type DemoFact = Fact<DemoType, DemoValue, String>;
213
214struct DemoRegistry {
215 symbols: HashMap<String, DemoFact>,
216}
217
218impl DemoRegistry {
219 fn known(types: Vec<DemoType>, value: Option<DemoValue>) -> DemoFact {
220 Fact {
221 types: TypeRange::Known(types),
222 value,
223 }
224 }
225
226 fn deferred(query: impl Into<String>) -> DemoFact {
227 Fact {
228 types: TypeRange::Deferred(query.into()),
229 value: None,
230 }
231 }
232}
233
234impl InferenceContext for DemoRegistry {
235 type Type = DemoType;
236 type Value = DemoValue;
237 type Query = String;
238
239 fn integer(&self, literal: &IntegerLiteral) -> DemoFact {
240 Self::known(
241 vec![DemoType::Integer, DemoType::Number, DemoType::Thing],
242 literal.text().parse().ok().map(DemoValue::Integer),
243 )
244 }
245
246 fn string(&self, _literal: &StringLiteral) -> DemoFact {
247 Self::known(vec![DemoType::String, DemoType::Thing], None)
248 }
249
250 fn symbol(&self, symbol: &Symbol) -> DemoFact {
251 self.symbols
252 .get(symbol.text())
253 .cloned()
254 .unwrap_or_else(|| Self::deferred(format!("symbol `{}`", symbol.text())))
255 }
256
257 fn binary(&self, node: &BinaryExpr, left: DemoFact, right: DemoFact) -> DemoFact {
258 match (&node.operator, left.value, right.value) {
259 (
260 BinaryOperator::Add(_),
261 Some(DemoValue::Integer(left)),
262 Some(DemoValue::Integer(right)),
263 ) => Self::known(
264 vec![DemoType::Integer, DemoType::Number, DemoType::Thing],
265 Some(DemoValue::Integer(left + right)),
266 ),
267 _ => Self::deferred("installed binary signature"),
268 }
269 }
270
271 fn collection(&self, kind: CollectionKind, _elements: Vec<DemoFact>) -> DemoFact {
272 let ty = match kind {
273 CollectionKind::Array => DemoType::Array,
274 CollectionKind::List => DemoType::List,
275 CollectionKind::Sequence => DemoType::Sequence,
276 };
277 Self::known(vec![ty, DemoType::Thing], None)
278 }
279
280 fn control(&self, kind: ControlKind, _neighbours: Vec<DemoFact>) -> DemoFact {
281 Self::deferred(format!("{kind:?} typing rule"))
282 }
283}
284
285fn infer(source: &str, context: &DemoRegistry) -> Result<DemoFact, ParseError> {
286 let file = parse_file(source)?;
287 let expression = match file.cells[0].content.pack.first() {
288 Component::Expr(expression) => expression.as_ref(),
289 Component::Empty(_) => panic!("expected an expression component"),
290 };
291 Ok(TypeChecker {
292 context,
293 results: Vec::new(),
294 }
295 .infer(expression))
296}
297
298fn main() -> Result<(), ParseError> {
299 let context = DemoRegistry {
300 symbols: HashMap::from([(
301 "answer".into(),
302 DemoRegistry::known(
303 vec![DemoType::Integer, DemoType::Number, DemoType::Thing],
304 Some(DemoValue::Integer(40)),
305 ),
306 )]),
307 };
308
309 let known = infer("(answer + 2)", &context)?;
310 let deferred = infer("missing + 2", &context)?;
311 let collection = infer("{answer, missing}", &context)?;
312
313 println!("known: {known:?}");
314 println!("deferred: {deferred:?}");
315 println!("collection: {collection:?}");
316 Ok(())
317}