leo_passes/const_propagation/
ast.rs

1// Copyright (C) 2019-2025 Provable Inc.
2// This file is part of the Leo library.
3
4// The Leo library is free software: you can redistribute it and/or modify
5// it under the terms of the GNU General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8
9// The Leo library is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12// GNU General Public License for more details.
13
14// You should have received a copy of the GNU General Public License
15// along with the Leo library. If not, see <https://www.gnu.org/licenses/>.
16
17use leo_ast::{
18    interpreter_value::{self, Value},
19    *,
20};
21use leo_errors::StaticAnalyzerError;
22use leo_span::{Symbol, sym};
23
24use super::ConstPropagationVisitor;
25
26const VALUE_ERROR: &str = "A non-future value should always be able to be converted into an expression";
27
28impl AstReconstructor for ConstPropagationVisitor<'_> {
29    type AdditionalInput = ();
30    type AdditionalOutput = Option<Value>;
31
32    /* Types */
33    fn reconstruct_array_type(&mut self, input: leo_ast::ArrayType) -> (leo_ast::Type, Self::AdditionalOutput) {
34        let (length, opt_value) = self.reconstruct_expression(*input.length, &());
35
36        // If we can't evaluate this array length, keep track of it for error reporting later
37        if opt_value.is_none() {
38            self.array_length_not_evaluated = Some(length.span());
39        }
40
41        (
42            leo_ast::Type::Array(leo_ast::ArrayType {
43                element_type: Box::new(self.reconstruct_type(*input.element_type).0),
44                length: Box::new(length),
45            }),
46            Default::default(),
47        )
48    }
49
50    /* Expressions */
51    fn reconstruct_expression(&mut self, input: Expression, _additional: &()) -> (Expression, Self::AdditionalOutput) {
52        let opt_old_type = self.state.type_table.get(&input.id());
53        let (new_expr, opt_value) = match input {
54            Expression::Array(array) => self.reconstruct_array(array, &()),
55            Expression::ArrayAccess(access) => self.reconstruct_array_access(*access, &()),
56            Expression::AssociatedConstant(constant) => self.reconstruct_associated_constant(constant, &()),
57            Expression::AssociatedFunction(function) => self.reconstruct_associated_function(function, &()),
58            Expression::Async(async_) => self.reconstruct_async(async_, &()),
59            Expression::Binary(binary) => self.reconstruct_binary(*binary, &()),
60            Expression::Call(call) => self.reconstruct_call(*call, &()),
61            Expression::Cast(cast) => self.reconstruct_cast(*cast, &()),
62            Expression::Struct(struct_) => self.reconstruct_struct_init(struct_, &()),
63            Expression::Err(err) => self.reconstruct_err(err, &()),
64            Expression::Path(path) => self.reconstruct_path(path, &()),
65            Expression::Literal(value) => self.reconstruct_literal(value, &()),
66            Expression::Locator(locator) => self.reconstruct_locator(locator, &()),
67            Expression::MemberAccess(access) => self.reconstruct_member_access(*access, &()),
68            Expression::Repeat(repeat) => self.reconstruct_repeat(*repeat, &()),
69            Expression::Ternary(ternary) => self.reconstruct_ternary(*ternary, &()),
70            Expression::Tuple(tuple) => self.reconstruct_tuple(tuple, &()),
71            Expression::TupleAccess(access) => self.reconstruct_tuple_access(*access, &()),
72            Expression::Unary(unary) => self.reconstruct_unary(*unary, &()),
73            Expression::Unit(unit) => self.reconstruct_unit(unit, &()),
74        };
75
76        // If the expression was in the type table before, make an entry for the new expression.
77        if let Some(old_type) = opt_old_type {
78            self.state.type_table.insert(new_expr.id(), old_type);
79        }
80
81        (new_expr, opt_value)
82    }
83
84    fn reconstruct_struct_init(
85        &mut self,
86        mut input: StructExpression,
87        _additional: &(),
88    ) -> (Expression, Self::AdditionalOutput) {
89        let mut values = Vec::new();
90        input.const_arguments.iter_mut().for_each(|arg| {
91            *arg = self.reconstruct_expression(std::mem::take(arg), &()).0;
92        });
93        for member in input.members.iter_mut() {
94            let expression = member.expression.take().unwrap_or_else(|| {
95                Path::from(member.identifier).with_absolute_path(Some(vec![member.identifier.name])).into()
96            });
97            let (new_expr, value_opt) = self.reconstruct_expression(expression, &());
98            member.expression = Some(new_expr);
99            if let Some(value) = value_opt {
100                values.push(value);
101            }
102        }
103
104        if values.len() == input.members.len() && input.const_arguments.is_empty() {
105            let value = Value::make_struct(
106                input.members.iter().map(|mem| mem.identifier.name).zip(values),
107                self.program,
108                input.path.absolute_path(),
109            );
110            (input.into(), Some(value))
111        } else {
112            (input.into(), None)
113        }
114    }
115
116    fn reconstruct_ternary(
117        &mut self,
118        input: TernaryExpression,
119        _additional: &(),
120    ) -> (Expression, Self::AdditionalOutput) {
121        let (cond, cond_value) = self.reconstruct_expression(input.condition, &());
122
123        match cond_value.and_then(|v| v.try_into().ok()) {
124            Some(true) => self.reconstruct_expression(input.if_true, &()),
125            Some(false) => self.reconstruct_expression(input.if_false, &()),
126            _ => (
127                TernaryExpression {
128                    condition: cond,
129                    if_true: self.reconstruct_expression(input.if_true, &()).0,
130                    if_false: self.reconstruct_expression(input.if_false, &()).0,
131                    ..input
132                }
133                .into(),
134                None,
135            ),
136        }
137    }
138
139    fn reconstruct_array_access(
140        &mut self,
141        input: ArrayAccess,
142        _additional: &(),
143    ) -> (Expression, Self::AdditionalOutput) {
144        let span = input.span();
145        let id = input.id();
146        let array_id = input.array.id();
147        let (array, array_opt) = self.reconstruct_expression(input.array, &());
148        let (index, index_opt) = self.reconstruct_expression(input.index, &());
149        if let Some(index_value) = index_opt {
150            // We can perform compile time bounds checking.
151
152            let ty = self.state.type_table.get(&array_id);
153            let Some(Type::Array(array_ty)) = ty else {
154                panic!("Type checking guaranteed that this is an array.");
155            };
156            let len = array_ty.length.as_u32();
157
158            if let Some(len) = len {
159                let index_in_bounds = matches!(index_value.as_u32(), Some(index) if index < len);
160
161                if !index_in_bounds {
162                    // Only emit a bounds error if we have no other errors yet.
163                    // This prevents a chain of redundant error messages when a loop is unrolled.
164                    if !self.state.handler.had_errors() {
165                        // Get the integer string with no suffix.
166                        let integer_with_suffix = index_value.to_string();
167                        let suffix_index = integer_with_suffix.find(['i', 'u']).unwrap_or(integer_with_suffix.len());
168                        self.emit_err(StaticAnalyzerError::array_bounds(
169                            &integer_with_suffix[..suffix_index],
170                            len,
171                            span,
172                        ));
173                    }
174                } else if let Some(array_value) = array_opt {
175                    // We're in bounds and we can evaluate the array at compile time, so just return the value.
176                    let result_value = array_value
177                        .array_index(index_value.as_u32().unwrap() as usize)
178                        .expect("We already checked bounds.");
179                    return (
180                        self.value_to_expression(&result_value, span, id).expect(VALUE_ERROR),
181                        Some(result_value.clone()),
182                    );
183                }
184            }
185        } else {
186            self.array_index_not_evaluated = Some(index.span());
187        }
188        (ArrayAccess { array, index, ..input }.into(), None)
189    }
190
191    fn reconstruct_associated_constant(
192        &mut self,
193        input: leo_ast::AssociatedConstantExpression,
194        _additional: &(),
195    ) -> (Expression, Self::AdditionalOutput) {
196        // Currently there is only one associated constant.
197        let generator = Value::generator();
198        let expr = self.value_to_expression_node(&generator, &input).expect(VALUE_ERROR);
199        (expr, Some(generator))
200    }
201
202    fn reconstruct_associated_function(
203        &mut self,
204        mut input: leo_ast::AssociatedFunctionExpression,
205        _additional: &(),
206    ) -> (Expression, Self::AdditionalOutput) {
207        let mut values = Vec::new();
208        for argument in input.arguments.iter_mut() {
209            let (new_argument, opt_value) = self.reconstruct_expression(std::mem::take(argument), &());
210            *argument = new_argument;
211            if let Some(value) = opt_value {
212                values.push(value);
213            }
214        }
215
216        if values.len() == input.arguments.len() && !matches!(input.variant.name, sym::CheatCode | sym::Mapping) {
217            // We've evaluated every argument, and this function isn't a cheat code or mapping
218            // operation, so maybe we can compute the result at compile time.
219            let core_function = CoreFunction::try_from(&input).expect("Type checking guarantees this is valid.");
220
221            match interpreter_value::evaluate_core_function(&mut values, core_function, &[], input.span()) {
222                Ok(Some(value)) => {
223                    // Successful evaluation.
224                    let expr = self.value_to_expression_node(&value, &input).expect(VALUE_ERROR);
225                    return (expr, Some(value));
226                }
227                Ok(None) =>
228                    // No errors, but we were unable to evaluate.
229                    {}
230                Err(err) => {
231                    self.emit_err(StaticAnalyzerError::compile_core_function(err, input.span()));
232                }
233            }
234        }
235
236        (input.into(), Default::default())
237    }
238
239    fn reconstruct_member_access(
240        &mut self,
241        input: MemberAccess,
242        _additional: &(),
243    ) -> (Expression, Self::AdditionalOutput) {
244        let span = input.span();
245        let id = input.id();
246        let (inner, value_opt) = self.reconstruct_expression(input.inner, &());
247        let member_name = input.name.name;
248        if let Some(struct_) = value_opt {
249            let value_result = struct_.member_access(member_name).expect("Type checking guarantees the member exists.");
250
251            (self.value_to_expression(&value_result, span, id).expect(VALUE_ERROR), Some(value_result.clone()))
252        } else {
253            (MemberAccess { inner, ..input }.into(), None)
254        }
255    }
256
257    fn reconstruct_repeat(
258        &mut self,
259        input: leo_ast::RepeatExpression,
260        _additional: &(),
261    ) -> (Expression, Self::AdditionalOutput) {
262        let (expr, expr_value) = self.reconstruct_expression(input.expr.clone(), &());
263        let (count, count_value) = self.reconstruct_expression(input.count.clone(), &());
264
265        if count_value.is_none() {
266            self.repeat_count_not_evaluated = Some(count.span());
267        }
268
269        match (expr_value, count.as_u32()) {
270            (Some(value), Some(count_u32)) => (
271                RepeatExpression { expr, count, ..input }.into(),
272                Some(Value::make_array(std::iter::repeat_n(value, count_u32 as usize))),
273            ),
274            _ => (RepeatExpression { expr, count, ..input }.into(), None),
275        }
276    }
277
278    fn reconstruct_tuple_access(
279        &mut self,
280        input: TupleAccess,
281        _additional: &(),
282    ) -> (Expression, Self::AdditionalOutput) {
283        let span = input.span();
284        let id = input.id();
285        let (tuple, value_opt) = self.reconstruct_expression(input.tuple, &());
286        if let Some(tuple_value) = value_opt {
287            let value_result = tuple_value.tuple_index(input.index.value()).expect("Type checking checked bounds.");
288            (self.value_to_expression(&value_result, span, id).expect(VALUE_ERROR), Some(value_result.clone()))
289        } else {
290            (TupleAccess { tuple, ..input }.into(), None)
291        }
292    }
293
294    fn reconstruct_array(
295        &mut self,
296        mut input: leo_ast::ArrayExpression,
297        _additional: &(),
298    ) -> (Expression, Self::AdditionalOutput) {
299        let mut values = Vec::new();
300        input.elements.iter_mut().for_each(|element| {
301            let (new_element, value_opt) = self.reconstruct_expression(std::mem::take(element), &());
302            if let Some(value) = value_opt {
303                values.push(value);
304            }
305            *element = new_element;
306        });
307        if values.len() == input.elements.len() {
308            (input.into(), Some(Value::make_array(values.into_iter())))
309        } else {
310            (input.into(), None)
311        }
312    }
313
314    fn reconstruct_binary(
315        &mut self,
316        input: leo_ast::BinaryExpression,
317        _additional: &(),
318    ) -> (Expression, Self::AdditionalOutput) {
319        let span = input.span();
320        let input_id = input.id();
321
322        let (left, lhs_opt_value) = self.reconstruct_expression(input.left, &());
323        let (right, rhs_opt_value) = self.reconstruct_expression(input.right, &());
324
325        if let (Some(lhs_value), Some(rhs_value)) = (lhs_opt_value, rhs_opt_value) {
326            // We were able to evaluate both operands, so we can evaluate this expression.
327            match interpreter_value::evaluate_binary(
328                span,
329                input.op,
330                &lhs_value,
331                &rhs_value,
332                &self.state.type_table.get(&input_id),
333            ) {
334                Ok(new_value) => {
335                    let new_expr = self.value_to_expression(&new_value, span, input_id).expect(VALUE_ERROR);
336                    return (new_expr, Some(new_value));
337                }
338                Err(err) => self
339                    .emit_err(StaticAnalyzerError::compile_time_binary_op(lhs_value, rhs_value, input.op, err, span)),
340            }
341        }
342
343        (BinaryExpression { left, right, ..input }.into(), None)
344    }
345
346    fn reconstruct_call(
347        &mut self,
348        mut input: leo_ast::CallExpression,
349        _additional: &(),
350    ) -> (Expression, Self::AdditionalOutput) {
351        input.const_arguments.iter_mut().for_each(|arg| {
352            *arg = self.reconstruct_expression(std::mem::take(arg), &()).0;
353        });
354        input.arguments.iter_mut().for_each(|arg| {
355            *arg = self.reconstruct_expression(std::mem::take(arg), &()).0;
356        });
357        (input.into(), Default::default())
358    }
359
360    fn reconstruct_cast(
361        &mut self,
362        input: leo_ast::CastExpression,
363        _additional: &(),
364    ) -> (Expression, Self::AdditionalOutput) {
365        let span = input.span();
366        let id = input.id();
367
368        let (expr, opt_value) = self.reconstruct_expression(input.expression, &());
369
370        if let Some(value) = opt_value {
371            if let Some(cast_value) = value.cast(&input.type_) {
372                let expr = self.value_to_expression(&cast_value, span, id).expect(VALUE_ERROR);
373                return (expr, Some(cast_value));
374            } else {
375                self.emit_err(StaticAnalyzerError::compile_time_cast(value, &input.type_, span));
376            }
377        }
378        (CastExpression { expression: expr, ..input }.into(), None)
379    }
380
381    fn reconstruct_err(
382        &mut self,
383        _input: leo_ast::ErrExpression,
384        _additional: &(),
385    ) -> (Expression, Self::AdditionalOutput) {
386        panic!("`ErrExpression`s should not be in the AST at this phase of compilation.")
387    }
388
389    fn reconstruct_path(&mut self, input: leo_ast::Path, _additional: &()) -> (Expression, Self::AdditionalOutput) {
390        // Substitute the identifier with the constant value if it is a constant that's been evaluated.
391        if let Some(expression) = self.state.symbol_table.lookup_const(self.program, &input.absolute_path()) {
392            let (expression, opt_value) = self.reconstruct_expression(expression, &());
393            if opt_value.is_some() {
394                return (expression, opt_value);
395            }
396        }
397
398        (input.into(), None)
399    }
400
401    fn reconstruct_literal(
402        &mut self,
403        mut input: leo_ast::Literal,
404        _additional: &(),
405    ) -> (Expression, Self::AdditionalOutput) {
406        let type_info = self.state.type_table.get(&input.id());
407
408        // If this is an optional, then unwrap it first.
409        let type_info = type_info.as_ref().map(|ty| match ty {
410            Type::Optional(opt) => *opt.inner.clone(),
411            _ => ty.clone(),
412        });
413
414        if let Ok(value) = interpreter_value::literal_to_value(&input, &type_info) {
415            // If we know the type of an unsuffixed literal, might as well change it to a suffixed literal. This way, we
416            // do not have to infer the type again in later passes of type checking.
417            if let LiteralVariant::Unsuffixed(s) = input.variant {
418                match type_info.expect("Expected type information to be available") {
419                    Type::Integer(ty) => input.variant = LiteralVariant::Integer(ty, s),
420                    Type::Field => input.variant = LiteralVariant::Field(s),
421                    Type::Group => input.variant = LiteralVariant::Group(s),
422                    Type::Scalar => input.variant = LiteralVariant::Scalar(s),
423                    _ => panic!("Type checking should have prevented this."),
424                }
425            }
426            (input.into(), Some(value))
427        } else {
428            (input.into(), None)
429        }
430    }
431
432    fn reconstruct_locator(
433        &mut self,
434        input: leo_ast::LocatorExpression,
435        _additional: &(),
436    ) -> (Expression, Self::AdditionalOutput) {
437        (input.into(), Default::default())
438    }
439
440    fn reconstruct_tuple(
441        &mut self,
442        mut input: leo_ast::TupleExpression,
443        _additional: &(),
444    ) -> (Expression, Self::AdditionalOutput) {
445        let mut values = Vec::with_capacity(input.elements.len());
446        for expr in input.elements.iter_mut() {
447            let (new_expr, opt_value) = self.reconstruct_expression(std::mem::take(expr), &());
448            *expr = new_expr;
449            if let Some(value) = opt_value {
450                values.push(value);
451            }
452        }
453
454        let opt_value = if values.len() == input.elements.len() { Some(Value::make_tuple(values)) } else { None };
455
456        (input.into(), opt_value)
457    }
458
459    fn reconstruct_unary(&mut self, input: UnaryExpression, _additional: &()) -> (Expression, Self::AdditionalOutput) {
460        let input_id = input.id();
461        let span = input.span;
462        let (receiver, opt_value) = self.reconstruct_expression(input.receiver, &());
463
464        if let Some(value) = opt_value {
465            // We were able to evaluate the operand, so we can evaluate the expression.
466            match interpreter_value::evaluate_unary(span, input.op, &value, &self.state.type_table.get(&input_id)) {
467                Ok(new_value) => {
468                    let new_expr = self.value_to_expression(&new_value, span, input_id).expect(VALUE_ERROR);
469                    return (new_expr, Some(new_value));
470                }
471                Err(err) => self.emit_err(StaticAnalyzerError::compile_time_unary_op(value, input.op, err, span)),
472            }
473        }
474        (UnaryExpression { receiver, ..input }.into(), None)
475    }
476
477    fn reconstruct_unit(
478        &mut self,
479        input: leo_ast::UnitExpression,
480        _additional: &(),
481    ) -> (Expression, Self::AdditionalOutput) {
482        (input.into(), None)
483    }
484
485    /* Statements */
486    fn reconstruct_assert(&mut self, mut input: AssertStatement) -> (Statement, Self::AdditionalOutput) {
487        // Catching asserts at compile time is not feasible here due to control flow, but could be done in
488        // a later pass after loops are unrolled and conditionals are flattened.
489        input.variant = match input.variant {
490            AssertVariant::Assert(expr) => AssertVariant::Assert(self.reconstruct_expression(expr, &()).0),
491
492            AssertVariant::AssertEq(lhs, rhs) => AssertVariant::AssertEq(
493                self.reconstruct_expression(lhs, &()).0,
494                self.reconstruct_expression(rhs, &()).0,
495            ),
496
497            AssertVariant::AssertNeq(lhs, rhs) => AssertVariant::AssertNeq(
498                self.reconstruct_expression(lhs, &()).0,
499                self.reconstruct_expression(rhs, &()).0,
500            ),
501        };
502
503        (input.into(), None)
504    }
505
506    fn reconstruct_assign(&mut self, assign: AssignStatement) -> (Statement, Self::AdditionalOutput) {
507        let value = self.reconstruct_expression(assign.value, &()).0;
508        let place = self.reconstruct_expression(assign.place, &()).0;
509        (AssignStatement { value, place, ..assign }.into(), None)
510    }
511
512    fn reconstruct_block(&mut self, mut block: Block) -> (Block, Self::AdditionalOutput) {
513        self.in_scope(block.id(), |slf| {
514            block.statements.retain_mut(|statement| {
515                let bogus_statement = Statement::dummy();
516                let this_statement = std::mem::replace(statement, bogus_statement);
517                *statement = slf.reconstruct_statement(this_statement).0;
518                !statement.is_empty()
519            });
520            (block, None)
521        })
522    }
523
524    fn reconstruct_conditional(
525        &mut self,
526        mut conditional: ConditionalStatement,
527    ) -> (Statement, Self::AdditionalOutput) {
528        conditional.condition = self.reconstruct_expression(conditional.condition, &()).0;
529        conditional.then = self.reconstruct_block(conditional.then).0;
530        if let Some(mut otherwise) = conditional.otherwise {
531            *otherwise = self.reconstruct_statement(*otherwise).0;
532            conditional.otherwise = Some(otherwise);
533        }
534
535        (Statement::Conditional(conditional), None)
536    }
537
538    fn reconstruct_const(&mut self, mut input: ConstDeclaration) -> (Statement, Self::AdditionalOutput) {
539        if matches!(input.type_, Type::Optional(_)) {
540            return (input.into(), None);
541        }
542
543        let span = input.span();
544
545        let type_ = self.reconstruct_type(input.type_).0;
546        let (expr, opt_value) = self.reconstruct_expression(input.value, &());
547
548        if opt_value.is_some() {
549            let path: &[Symbol] = if self.state.symbol_table.global_scope() {
550                // Then we need to insert the const with its full module-scoped path.
551                &self.module.iter().copied().chain(std::iter::once(input.place.name)).collect::<Vec<_>>()
552            } else {
553                &[input.place.name]
554            };
555            if self.state.symbol_table.lookup_const(self.program, path).is_none() {
556                // It wasn't already evaluated - insert it and record that we've made a change.
557                self.state.symbol_table.insert_const(self.program, path, expr.clone());
558                self.changed = true;
559            }
560        } else {
561            self.const_not_evaluated = Some(span);
562        }
563
564        input.type_ = type_;
565        input.value = expr;
566
567        (Statement::Const(input), None)
568    }
569
570    fn reconstruct_definition(&mut self, definition: DefinitionStatement) -> (Statement, Self::AdditionalOutput) {
571        (
572            DefinitionStatement {
573                type_: definition.type_.map(|ty| self.reconstruct_type(ty).0),
574                value: self.reconstruct_expression(definition.value, &()).0,
575                ..definition
576            }
577            .into(),
578            None,
579        )
580    }
581
582    fn reconstruct_expression_statement(
583        &mut self,
584        mut input: ExpressionStatement,
585    ) -> (Statement, Self::AdditionalOutput) {
586        input.expression = self.reconstruct_expression(input.expression, &()).0;
587
588        if matches!(&input.expression, Expression::Unit(..) | Expression::Literal(..)) {
589            // We were able to evaluate this at compile time, but we need to get rid of this statement as
590            // we can't have expression statements that aren't calls.
591            (Statement::dummy(), Default::default())
592        } else {
593            (input.into(), Default::default())
594        }
595    }
596
597    fn reconstruct_iteration(&mut self, iteration: IterationStatement) -> (Statement, Self::AdditionalOutput) {
598        let id = iteration.id();
599        let type_ = iteration.type_.map(|ty| self.reconstruct_type(ty).0);
600        let start = self.reconstruct_expression(iteration.start, &()).0;
601        let stop = self.reconstruct_expression(iteration.stop, &()).0;
602        self.in_scope(id, |slf| {
603            (
604                IterationStatement { type_, start, stop, block: slf.reconstruct_block(iteration.block).0, ..iteration }
605                    .into(),
606                None,
607            )
608        })
609    }
610
611    fn reconstruct_return(&mut self, input: ReturnStatement) -> (Statement, Self::AdditionalOutput) {
612        (
613            ReturnStatement { expression: self.reconstruct_expression(input.expression, &()).0, ..input }.into(),
614            Default::default(),
615        )
616    }
617}
leo_passes/const_propagation/ast.rs

leo_passes/const_propagation/
ast.rs
