Module visit 

This module provides an implementation of the visitor pattern for the AST of Miden Assembly.

The pattern is implemented in terms of two traits, Visit and VisitMut, corresponding to whether or not the visitor has mutable access to each AST node.

In addition to the visitor traits, there are a number of free functions that correspond to the methods of those traits. For example, the visit methods for a Procedure are Visit::visit_procedure and VisitMut::visit_mut_procedure. There are two free functions that are used in conjunction with these methods: visit_procedure, and visit_mut_procedure, which are typically not imported directly, but are referenced through the visit module, e.g. visit::visit_procedure. These free functions implement the default visitor for the AST node they correspond to. By default, all methods of the Visit and VisitMut traits delegate to these functions. As a result, impl Visit for MyVisitor {} is technically a valid visitor, and will traverse the entire AST if invoked.

Obviously, that visitor wouldn’t be very useful, but in practice, the free functions are called to resume traversal of the AST either before or after executing the desired behavior for a given AST node. Doing so essentially corresponds to either a post- or preorder traversal of the AST respectively.

How do you choose between performing a postorder vs preorder visit? It depends on the semantics of the visitor, but here are some examples:

1. When implementing a visitor that performs constant folding/propagation, you need to visit the operands of an expression before the operator, in order to determine whether it is possible to fold, and if so, what the actual values of the operands are. As a result, this is implemented as a postorder visitor, so that the AST node corresponding to the expression is rewritten after all of it’s children.

2. When implementing an analysis based on lexical scope, it is necessary to “push down” context from the root to the leaves of the AST - the context being the contents of each AST nodes inherited scope. As a result, this is implemented as a preorder traversal, so that the context at each node can be computed before visiting the children of that node.

In both cases, the implementor must call the free function corresponding to the current AST node at the appropriate point (i.e. before/after executing the logic for the node), so that the visitor will resume its traversal of the tree correctly. Put another way, failing to do so will cause the traversal to stop at that node (it will continue visiting sibling nodes, if applicable, but it will go no deeper in the tree).

FAQs

• Why are the free visit functions needed?

Technically they aren’t - you could reimplement the visit pattern for every AST node, in each visitor, independently. However, this is a lot of boilerplate (as you can see below), and would represent a major maintenance burden if the AST changes shape at all. By implementing the default pattern in those free functions, they can be reused everywhere, and a visitor need only override the methods of those nodes it cares about. Changes to the AST only require modifying the code in this module, with the exception of visitors whose logic must be updated to reflect modifications to specific nodes they care about.

Traits

Visit

Represents an immutable AST visitor, whose “early return” type is T (by default ()).

VisitMut

Represents a mutable AST visitor, whose “early return” type is T (by default ()).

Functions

visit_alias

visit_alias_target

visit_block

visit_call

visit_constant

visit_constant_expr

visit_constant_ref

visit_debug_options

visit_enum

visit_enum_variant

visit_exec

visit_export

visit_immediate_error_message

visit_immediate_felt

visit_immediate_push_value

visit_immediate_u8

visit_immediate_u16

visit_immediate_u32

visit_immediate_word_value

visit_inst

visit_invoke_target

visit_module

visit_mut_alias

visit_mut_alias_target

visit_mut_block

visit_mut_call

visit_mut_constant

visit_mut_constant_expr

visit_mut_constant_ref

visit_mut_debug_options

visit_mut_enum

visit_mut_enum_variant

visit_mut_exec

visit_mut_export

visit_mut_immediate_error_message

visit_mut_immediate_felt

visit_mut_immediate_push_value

visit_mut_immediate_u8

visit_mut_immediate_u16

visit_mut_immediate_u32

visit_mut_immediate_word_value

visit_mut_inst

visit_mut_invoke_target

visit_mut_module

visit_mut_op

visit_mut_procedure

visit_mut_procref

visit_mut_syscall

visit_mut_system_event

visit_mut_type_alias

visit_mut_type_decl

visit_mut_type_expr

visit_mut_type_ref

visit_op

visit_procedure

visit_procref

visit_syscall

visit_system_event

visit_type_alias

visit_type_decl

visit_type_expr

visit_type_ref