miden_assembly_syntax/sema/passes/const_eval.rs
1use alloc::{sync::Arc, vec::Vec};
2use core::ops::ControlFlow;
3
4use miden_core::{events::EventId, utils::hash_string_to_word};
5use miden_debug_types::{Span, Spanned};
6
7use crate::{
8 Felt,
9 ast::{
10 constants::{ConstEnvironment, ConstEvalError, eval::CachedConstantValue},
11 *,
12 },
13 parser::{IntValue, PushValue, WordValue},
14};
15
16/// This visitor evaluates all constant expressions and folds them to literals.
17///
18/// This visitor is abstracted over the const-evaluation environment so that it's implementation
19/// can be reused for both module-local rewrites, and link-time rewrites where we have all the
20/// symbols available to resolve foreign constants.
21pub struct ConstEvalVisitor<'env, Env>
22where
23 Env: ?Sized + ConstEnvironment,
24{
25 env: &'env mut Env,
26 errors: Vec<<Env as ConstEnvironment>::Error>,
27}
28
29impl<'env, Env> ConstEvalVisitor<'env, Env>
30where
31 Env: ?Sized + ConstEnvironment,
32 <Env as ConstEnvironment>::Error: From<ConstEvalError>,
33{
34 pub fn new(env: &'env mut Env) -> Self {
35 Self { env, errors: Default::default() }
36 }
37
38 pub fn into_result(self) -> Result<(), Vec<<Env as ConstEnvironment>::Error>> {
39 if self.errors.is_empty() {
40 Ok(())
41 } else {
42 Err(self.errors)
43 }
44 }
45
46 fn eval_const<T>(&mut self, imm: &mut Immediate<T>) -> ControlFlow<()>
47 where
48 T: TryFrom<u64>,
49 {
50 match imm {
51 Immediate::Value(_) => ControlFlow::Continue(()),
52 Immediate::Constant(name) => {
53 let span = name.span();
54 let value = match self.env.get(name) {
55 Ok(Some(
56 CachedConstantValue::Hit(ConstantValue::Int(value))
57 | CachedConstantValue::Miss(ConstantExpr::Int(value)),
58 )) => *value,
59 Ok(Some(CachedConstantValue::Miss(
60 expr @ (ConstantExpr::Var(_) | ConstantExpr::BinaryOp { .. }),
61 ))) => {
62 // A reference to another constant was used, try to evaluate the expression
63 let expr = expr.clone();
64 match constants::eval::expr(&expr, self.env) {
65 Ok(ConstantExpr::Int(value)) => value,
66 // Unable to evaluate in the current context
67 Ok(ConstantExpr::Var(_) | ConstantExpr::BinaryOp { .. }) => {
68 return ControlFlow::Continue(());
69 },
70 Ok(_) => {
71 self.errors.push(
72 ConstEvalError::InvalidConstant {
73 span,
74 expected: "an integer",
75 source_file: self.env.get_source_file_for(span),
76 }
77 .into(),
78 );
79 return ControlFlow::Continue(());
80 },
81 Err(err) => {
82 self.errors.push(err);
83 return ControlFlow::Continue(());
84 },
85 }
86 },
87 Ok(Some(_)) => {
88 self.errors.push(
89 ConstEvalError::InvalidConstant {
90 span,
91 expected: core::any::type_name::<T>(),
92 source_file: self.env.get_source_file_for(span),
93 }
94 .into(),
95 );
96 return ControlFlow::Continue(());
97 },
98 Ok(None) => return ControlFlow::Continue(()),
99 Err(err) => {
100 self.errors.push(err);
101 return ControlFlow::Continue(());
102 },
103 };
104 match T::try_from(value.as_int()) {
105 Ok(value) => {
106 *imm = Immediate::Value(Span::new(span, value));
107 },
108 Err(_) => {
109 self.errors.push(
110 ConstEvalError::ImmediateOverflow {
111 span,
112 source_file: self.env.get_source_file_for(span),
113 }
114 .into(),
115 );
116 },
117 }
118 ControlFlow::Continue(())
119 },
120 }
121 }
122}
123
124impl<'env, Env> VisitMut for ConstEvalVisitor<'env, Env>
125where
126 Env: ?Sized + ConstEnvironment,
127 <Env as ConstEnvironment>::Error: From<ConstEvalError>,
128{
129 fn visit_mut_constant(&mut self, constant: &mut Constant) -> ControlFlow<()> {
130 if constant.value.is_value() {
131 return ControlFlow::Continue(());
132 }
133
134 match constants::eval::expr(&constant.value, self.env) {
135 Ok(evaluated) => {
136 constant.value = evaluated;
137 },
138 Err(err) => {
139 self.errors.push(err);
140 },
141 }
142 ControlFlow::Continue(())
143 }
144 fn visit_mut_inst(&mut self, inst: &mut Span<Instruction>) -> ControlFlow<()> {
145 use crate::ast::Instruction;
146 if let Instruction::EmitImm(Immediate::Constant(name)) = &**inst {
147 let span = name.span();
148 match self.env.get(name) {
149 Ok(Some(
150 CachedConstantValue::Miss(ConstantExpr::Hash(HashKind::Event, _))
151 | CachedConstantValue::Hit(ConstantValue::Hash(HashKind::Event, _)),
152 )) => {
153 // CHANGE: allow `emit.EVENT` when `EVENT` was defined via
154 // const.EVENT = event("...")
155 // NOTE: This function only validates the kind; the actual resolution to a Felt
156 // happens below in `visit_mut_immediate_felt` just like other Felt immediates.
157 // Enabled syntax:
158 // const.EVT = event("...")
159 // emit.EVT
160 },
161 Ok(Some(CachedConstantValue::Miss(expr @ ConstantExpr::Var(_)))) => {
162 // A reference to another constant was used, try to evaluate the expression
163 let expr = expr.clone();
164 match constants::eval::expr(&expr, self.env) {
165 Ok(ConstantExpr::Hash(HashKind::Event, _)) => (),
166 // Unable to evaluate in the current context
167 Ok(ConstantExpr::Var(_)) => return ControlFlow::Continue(()),
168 Ok(_) => {
169 self.errors.push(
170 ConstEvalError::InvalidConstant {
171 span,
172 expected: "an event name",
173 source_file: self.env.get_source_file_for(span),
174 }
175 .into(),
176 );
177 },
178 Err(err) => {
179 self.errors.push(err);
180 },
181 }
182 },
183 Ok(Some(_)) => {
184 // CHANGE: disallow `emit.CONST` unless CONST is defined via `event("...")`.
185 // Examples which now error:
186 // const.BAD = 42
187 // emit.BAD
188 // const.W = word("foo")
189 // emit.W
190 self.errors.push(
191 ConstEvalError::InvalidConstant {
192 span,
193 expected: "an event name",
194 source_file: self.env.get_source_file_for(span),
195 }
196 .into(),
197 );
198 },
199 // The value is not yet available, proceed for now
200 Ok(None) => return ControlFlow::Continue(()),
201 Err(err) => {
202 self.errors.push(err);
203 },
204 }
205 }
206 visit::visit_mut_inst(self, inst)
207 }
208 fn visit_mut_immediate_u8(&mut self, imm: &mut Immediate<u8>) -> ControlFlow<()> {
209 self.eval_const(imm)
210 }
211 fn visit_mut_immediate_u16(&mut self, imm: &mut Immediate<u16>) -> ControlFlow<()> {
212 self.eval_const(imm)
213 }
214 fn visit_mut_immediate_u32(&mut self, imm: &mut Immediate<u32>) -> ControlFlow<()> {
215 self.eval_const(imm)
216 }
217 fn visit_mut_immediate_error_message(
218 &mut self,
219 imm: &mut Immediate<Arc<str>>,
220 ) -> ControlFlow<()> {
221 match imm {
222 Immediate::Value(_) => ControlFlow::Continue(()),
223 Immediate::Constant(name) => {
224 let span = name.span();
225 match self.env.get_error(name) {
226 Ok(Some(value)) => {
227 *imm = Immediate::Value(Span::new(span, value));
228 },
229 // The constant is externally-defined, and not available yet
230 Ok(None) => (),
231 Err(error) => {
232 self.errors.push(error);
233 },
234 }
235 ControlFlow::Continue(())
236 },
237 }
238 }
239 fn visit_mut_immediate_felt(&mut self, imm: &mut Immediate<Felt>) -> ControlFlow<()> {
240 match imm {
241 Immediate::Value(_) => ControlFlow::Continue(()),
242 Immediate::Constant(name) => {
243 let span = name.span();
244 match self.env.get(name) {
245 Ok(Some(
246 CachedConstantValue::Miss(ConstantExpr::Int(value))
247 | CachedConstantValue::Hit(ConstantValue::Int(value)),
248 )) => {
249 *imm = Immediate::Value(Span::new(
250 span,
251 Felt::new_unchecked(value.inner().as_int()),
252 ));
253 },
254 Ok(Some(
255 CachedConstantValue::Miss(ConstantExpr::Hash(HashKind::Event, string))
256 | CachedConstantValue::Hit(ConstantValue::Hash(HashKind::Event, string)),
257 )) => {
258 // CHANGE: resolve `event("...")` to a Felt when a Felt immediate is
259 // expected (e.g. enables `emit.EVENT`):
260 // const.EVT = event("...")
261 // emit.EVT
262 let event_id = EventId::from_name(string.as_str()).as_felt();
263 *imm = Immediate::Value(Span::new(span, event_id));
264 },
265 Ok(Some(CachedConstantValue::Miss(
266 expr @ (ConstantExpr::Var(_) | ConstantExpr::BinaryOp { .. }),
267 ))) => {
268 // A reference to another constant was used, try to evaluate the expression
269 let expr = expr.clone();
270 match constants::eval::expr(&expr, self.env) {
271 Ok(ConstantExpr::Int(value)) => {
272 *imm = Immediate::Value(Span::new(
273 span,
274 Felt::new_unchecked(value.inner().as_int()),
275 ));
276 },
277 Ok(ConstantExpr::Hash(HashKind::Event, value)) => {
278 // CHANGE: resolve `event("...")` to a Felt when a Felt immediate is
279 // expected (e.g. enables `emit.EVENT`):
280 // const.EVT = event("...")
281 // emit.EVT
282 let event_id = EventId::from_name(value.as_str()).as_felt();
283 *imm = Immediate::Value(Span::new(span, event_id));
284 },
285 // Unable to evaluate in the current context
286 Ok(ConstantExpr::Var(_) | ConstantExpr::BinaryOp { .. }) => (),
287 Ok(_) => {
288 self.errors.push(
289 ConstEvalError::InvalidConstant {
290 span,
291 expected: "a felt",
292 source_file: self.env.get_source_file_for(span),
293 }
294 .into(),
295 );
296 },
297 Err(err) => {
298 self.errors.push(err);
299 },
300 }
301 },
302 // Invalid value
303 Ok(Some(_)) => {
304 self.errors.push(
305 ConstEvalError::InvalidConstant {
306 span,
307 expected: "a felt",
308 source_file: self.env.get_source_file_for(span),
309 }
310 .into(),
311 );
312 },
313 // The constant expression references an externally-defined symbol which is
314 // not available yet, so ignore for now
315 Ok(None) => (),
316 Err(err) => {
317 self.errors.push(err);
318 },
319 }
320 ControlFlow::Continue(())
321 },
322 }
323 }
324
325 fn visit_mut_immediate_push_value(
326 &mut self,
327 imm: &mut Immediate<PushValue>,
328 ) -> ControlFlow<()> {
329 match imm {
330 Immediate::Value(_) => ControlFlow::Continue(()),
331 Immediate::Constant(name) => {
332 let span = name.span();
333 match self.env.get(name) {
334 Ok(Some(
335 CachedConstantValue::Miss(ConstantExpr::Int(value))
336 | CachedConstantValue::Hit(ConstantValue::Int(value)),
337 )) => {
338 *imm = Immediate::Value(Span::new(span, PushValue::Int(*value.inner())));
339 },
340 Ok(Some(
341 CachedConstantValue::Miss(ConstantExpr::Word(value))
342 | CachedConstantValue::Hit(ConstantValue::Word(value)),
343 )) => {
344 *imm = Immediate::Value(Span::new(span, PushValue::Word(*value.inner())));
345 },
346 Ok(Some(
347 CachedConstantValue::Miss(ConstantExpr::Hash(hash_kind, string))
348 | CachedConstantValue::Hit(ConstantValue::Hash(hash_kind, string)),
349 )) => match hash_kind {
350 HashKind::Word => {
351 // Existing behavior for `const.W = word("...")`:
352 // push.W # pushes a Word
353 let hash_word = hash_string_to_word(string.as_str());
354 *imm = Immediate::Value(Span::new(
355 span,
356 PushValue::Word(WordValue(*hash_word)),
357 ));
358 },
359 HashKind::Event => {
360 // CHANGE: allow `const.EVT = event("...")` with IntValue contexts by
361 // reducing to a Felt via word()[0]. Enables:
362 // const.EVT = event("...")
363 // push.EVT # pushes the Felt event id
364 let event_id = EventId::from_name(string.as_str()).as_felt();
365 *imm =
366 Immediate::Value(Span::new(span, IntValue::Felt(event_id).into()));
367 },
368 },
369 Ok(Some(CachedConstantValue::Miss(
370 expr @ (ConstantExpr::Var(_) | ConstantExpr::BinaryOp { .. }),
371 ))) => {
372 // A reference to another constant was used, try to evaluate the expression
373 let expr = expr.clone();
374 match constants::eval::expr(&expr, self.env) {
375 Ok(ConstantExpr::Int(value)) => {
376 *imm = Immediate::Value(Span::new(
377 span,
378 PushValue::Int(*value.inner()),
379 ));
380 },
381 Ok(ConstantExpr::Word(value)) => {
382 *imm = Immediate::Value(Span::new(
383 span,
384 PushValue::Word(*value.inner()),
385 ));
386 },
387 Ok(ConstantExpr::Hash(HashKind::Word, value)) => {
388 // Existing behavior for `const.W = word("...")`:
389 // push.W # pushes a Word
390 let hash_word = hash_string_to_word(value.as_str());
391 *imm = Immediate::Value(Span::new(
392 span,
393 PushValue::Word(WordValue(*hash_word)),
394 ));
395 },
396 Ok(ConstantExpr::Hash(HashKind::Event, value)) => {
397 // CHANGE: allow `const.EVT = event("...")` with IntValue contexts
398 // by reducing to a Felt via word()[0]. Enables:
399 // const.EVT = event("...")
400 // push.EVT # pushes the Felt event id
401 let event_id = EventId::from_name(value.as_str()).as_felt();
402 *imm = Immediate::Value(Span::new(
403 span,
404 IntValue::Felt(event_id).into(),
405 ));
406 },
407 // Unable to evaluate in the current context
408 Ok(ConstantExpr::Var(_) | ConstantExpr::BinaryOp { .. }) => (),
409 Ok(_) => {
410 self.errors.push(
411 ConstEvalError::InvalidConstant {
412 span,
413 expected: "an integer or word",
414 source_file: self.env.get_source_file_for(span),
415 }
416 .into(),
417 );
418 },
419 Err(err) => {
420 self.errors.push(err);
421 },
422 }
423 },
424 Ok(Some(_)) => {
425 self.errors.push(
426 ConstEvalError::InvalidConstant {
427 span,
428 expected: "an integer or word",
429 source_file: self.env.get_source_file_for(span),
430 }
431 .into(),
432 );
433 },
434 // The constant references an externally-defined symbol which is not yet
435 // available, so ignore for now
436 Ok(None) => (),
437 Err(err) => {
438 self.errors.push(err);
439 },
440 }
441 ControlFlow::Continue(())
442 },
443 }
444 }
445
446 fn visit_mut_immediate_word_value(
447 &mut self,
448 imm: &mut Immediate<WordValue>,
449 ) -> ControlFlow<()> {
450 match imm {
451 Immediate::Value(_) => ControlFlow::Continue(()),
452 Immediate::Constant(name) => {
453 let span = name.span();
454 match self.env.get(name) {
455 Ok(Some(
456 CachedConstantValue::Miss(ConstantExpr::Word(value))
457 | CachedConstantValue::Hit(ConstantValue::Word(value)),
458 )) => {
459 *imm = Immediate::Value(Span::new(span, *value.inner()));
460 },
461 Ok(Some(
462 CachedConstantValue::Miss(ConstantExpr::Hash(HashKind::Word, string))
463 | CachedConstantValue::Hit(ConstantValue::Hash(HashKind::Word, string)),
464 )) => {
465 // Existing behavior for `const.W = word("...")`:
466 // push.W # pushes a Word
467 let hash_word = hash_string_to_word(string.as_str());
468 *imm = Immediate::Value(Span::new(span, WordValue(*hash_word)));
469 },
470 Ok(Some(CachedConstantValue::Miss(expr @ ConstantExpr::Var(_)))) => {
471 // A reference to another constant was used, try to evaluate the expression
472 let expr = expr.clone();
473 match constants::eval::expr(&expr, self.env) {
474 Ok(ConstantExpr::Word(value)) => {
475 *imm = Immediate::Value(Span::new(span, *value.inner()));
476 },
477 Ok(ConstantExpr::Hash(HashKind::Word, value)) => {
478 // Existing behavior for `const.W = word("...")`:
479 // push.W # pushes a Word
480 let hash_word = hash_string_to_word(value.as_str());
481 *imm = Immediate::Value(Span::new(span, WordValue(*hash_word)));
482 },
483 // Unable to evaluate in the current context
484 Ok(ConstantExpr::Var(_)) => (),
485 Ok(_) => {
486 self.errors.push(
487 ConstEvalError::InvalidConstant {
488 span,
489 expected: "a word",
490 source_file: self.env.get_source_file_for(span),
491 }
492 .into(),
493 );
494 },
495 Err(err) => {
496 self.errors.push(err);
497 },
498 }
499 },
500 Ok(Some(_)) => {
501 self.errors.push(
502 ConstEvalError::InvalidConstant {
503 span,
504 expected: "a word",
505 source_file: self.env.get_source_file_for(span),
506 }
507 .into(),
508 );
509 },
510 // The constant references an externally-defined symbol which is not yet
511 // available, so ignore for now
512 Ok(None) => (),
513 Err(err) => {
514 self.errors.push(err);
515 },
516 }
517 ControlFlow::Continue(())
518 },
519 }
520 }
521}