source: src/AST/Pass.impl.hpp @ 55b6476

//
// Cforall Version 1.0.0 Copyright (C) 2019 University of Waterloo
//
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// ast::Pass.impl.hpp --
//
// Author           : Thierry Delisle
// Created On       : Thu May 09 15::37::05 2019
// Last Modified By :
// Last Modified On :
// Update Count     :
//

#pragma once
// IWYU pragma: private, include "AST/Pass.hpp"

#include <type_traits>
#include <unordered_map>

#include "AST/TypeSubstitution.hpp"

#define VISIT_START( node ) \
        using namespace ast; \
        /* back-up the visit children */ \
        __attribute__((unused)) ast::__pass::visit_children_guard guard1( ast::__pass::visit_children(pass, 0) ); \
        /* setup the scope for passes that want to run code at exit */ \
        __attribute__((unused)) ast::__pass::guard_value          guard2( ast::__pass::at_cleanup    (pass, 0) ); \
        /* call the implementation of the previsit of this pass */ \
        __pass::previsit( pass, node, 0 );

#define VISIT( code... ) \
        /* if this node should visit its children */ \
        if ( __visit_children() ) { \
                /* visit the children */ \
                code \
        }

#define VISIT_END( type, node ) \
        /* call the implementation of the postvisit of this pass */ \
        auto __return = __pass::postvisit( pass, node, 0 ); \
        assertf(__return, "post visit should never return null"); \
        return __return;

#ifdef PEDANTIC_PASS_ASSERT
#define __pedantic_pass_assert(...) assert (__VA_ARGS__)
#define __pedantic_pass_assertf(...) assertf(__VA_ARGS__)
#else
#define __pedantic_pass_assert(...)
#define __pedantic_pass_assertf(...)
#endif

namespace ast {
        namespace __pass {
                // Check if this is either a null pointer or a pointer to an empty container
                template<typename T>
                static inline bool empty( T * ptr ) {
                        return !ptr || ptr->empty();
                }

                //------------------------------
                template<typename it_t, template <class...> class container_t>
                static inline void take_all( it_t it, container_t<ast::ptr<ast::Decl>> * decls, bool * mutated = nullptr ) {
                        if(empty(decls)) return;

                        std::transform(decls->begin(), decls->end(), it, [](const ast::Decl * decl) -> auto {
                                        return new DeclStmt( decl->location, decl );
                                });
                        decls->clear();
                        if(mutated) *mutated = true;
                }

                template<typename it_t, template <class...> class container_t>
                static inline void take_all( it_t it, container_t<ast::ptr<ast::Stmt>> * decls, bool * mutated = nullptr ) {
                        if(empty(decls)) return;

                        std::move(decls->begin(), decls->end(), it);
                        decls->clear();
                        if(mutated) *mutated = true;
                }

                //------------------------------
                /// Check if should be skipped, different for pointers and containers
                template<typename node_t>
                bool skip( const ast::ptr<node_t> & val) {
                        return !val;
                }

                template< template <class...> class container_t, typename node_t >
                bool skip( const container_t<ast::ptr< node_t >> & val ) {
                        return val.empty();
                }

                //------------------------------
                /// Get the value to visit, different for pointers and containers
                template<typename node_t>
                auto get( const ast::ptr<node_t> & val, int ) -> decltype(val.get()) {
                        return val.get();
                }

                template<typename node_t>
                const node_t & get( const node_t & val, long) {
                        return val;
                }


                //------------------------------
                /// Check if value was mutated, different for pointers and containers
                template<typename lhs_t, typename rhs_t>
                bool differs( const lhs_t * old_val, const rhs_t * new_val ) {
                        return old_val != new_val;
                }

                template< template <class...> class container_t, typename node_t >
                bool differs( const container_t<ast::ptr< node_t >> &, const container_t<ast::ptr< node_t >> & new_val ) {
                        return !new_val.empty();
                }
        }

        template< typename pass_t >
        template< typename node_t >
        auto ast::Pass< pass_t >::call_accept( const node_t * node )
                -> typename std::enable_if<
                                !std::is_base_of<ast::Expr, node_t>::value &&
                                !std::is_base_of<ast::Stmt, node_t>::value
                        , decltype( node->accept(*this) )
                >::type
        {
                __pedantic_pass_assert( __visit_children() );
                __pedantic_pass_assert( node );

                static_assert( !std::is_base_of<ast::Expr, node_t>::value, "ERROR");
                static_assert( !std::is_base_of<ast::Stmt, node_t>::value, "ERROR");

                return node->accept( *this );
        }

        template< typename pass_t >
        const ast::Expr * ast::Pass< pass_t >::call_accept( const ast::Expr * expr ) {
                __pedantic_pass_assert( __visit_children() );
                __pedantic_pass_assert( expr );

                const ast::TypeSubstitution ** env_ptr = __pass::env( pass, 0);
                if ( env_ptr && expr->env ) {
                        *env_ptr = expr->env;
                }

                return expr->accept( *this );
        }

        template< typename pass_t >
        const ast::Stmt * ast::Pass< pass_t >::call_accept( const ast::Stmt * stmt ) {
                __pedantic_pass_assert( __visit_children() );
                __pedantic_pass_assert( stmt );

                // add a few useful symbols to the scope
                using __pass::empty;

                // get the stmts/decls that will need to be spliced in
                auto stmts_before = __pass::stmtsToAddBefore( pass, 0);
                auto stmts_after  = __pass::stmtsToAddAfter ( pass, 0);
                auto decls_before = __pass::declsToAddBefore( pass, 0);
                auto decls_after  = __pass::declsToAddAfter ( pass, 0);

                // These may be modified by subnode but most be restored once we exit this statemnet.
                ValueGuardPtr< const ast::TypeSubstitution * > __old_env         ( __pass::env( pass, 0) );
                ValueGuardPtr< typename std::remove_pointer< decltype(stmts_before) >::type > __old_decls_before( stmts_before );
                ValueGuardPtr< typename std::remove_pointer< decltype(stmts_after ) >::type > __old_decls_after ( stmts_after  );
                ValueGuardPtr< typename std::remove_pointer< decltype(decls_before) >::type > __old_stmts_before( decls_before );
                ValueGuardPtr< typename std::remove_pointer< decltype(decls_after ) >::type > __old_stmts_after ( decls_after  );

                // Now is the time to actually visit the node
                const ast::Stmt * nstmt = stmt->accept( *this );

                // If the pass doesn't want to add anything then we are done
                if( empty(stmts_before) && empty(stmts_after) && empty(decls_before) && empty(decls_after) ) {
                        return nstmt;
                }

                // Make sure that it is either adding statements or declartions but not both
                // this is because otherwise the order would be awkward to predict
                assert(( empty( stmts_before ) && empty( stmts_after ))
                    || ( empty( decls_before ) && empty( decls_after )) );

                // Create a new Compound Statement to hold the new decls/stmts
                ast::CompoundStmt * compound = new ast::CompoundStmt( stmt->location );

                // Take all the declarations that go before
                __pass::take_all( std::back_inserter( compound->kids ), decls_before );
                __pass::take_all( std::back_inserter( compound->kids ), stmts_before );

                // Insert the original declaration
                compound->kids.emplace_back( nstmt );

                // Insert all the declarations that go before
                __pass::take_all( std::back_inserter( compound->kids ), decls_after );
                __pass::take_all( std::back_inserter( compound->kids ), stmts_after );

                return compound;
        }

        template< typename pass_t >
        template< template <class...> class container_t >
        container_t< ptr<Stmt> > ast::Pass< pass_t >::call_accept( const container_t< ptr<Stmt> > & statements ) {
                __pedantic_pass_assert( __visit_children() );
                if( statements.empty() ) return {};

                // We are going to aggregate errors for all these statements
                SemanticErrorException errors;

                // add a few useful symbols to the scope
                using __pass::empty;

                // get the stmts/decls that will need to be spliced in
                auto stmts_before = __pass::stmtsToAddBefore( pass, 0);
                auto stmts_after  = __pass::stmtsToAddAfter ( pass, 0);
                auto decls_before = __pass::declsToAddBefore( pass, 0);
                auto decls_after  = __pass::declsToAddAfter ( pass, 0);

                // These may be modified by subnode but most be restored once we exit this statemnet.
                ValueGuardPtr< typename std::remove_pointer< decltype(stmts_before) >::type > __old_decls_before( stmts_before );
                ValueGuardPtr< typename std::remove_pointer< decltype(stmts_after ) >::type > __old_decls_after ( stmts_after  );
                ValueGuardPtr< typename std::remove_pointer< decltype(decls_before) >::type > __old_stmts_before( decls_before );
                ValueGuardPtr< typename std::remove_pointer< decltype(decls_after ) >::type > __old_stmts_after ( decls_after  );

                // update pass statitistics
                pass_visitor_stats.depth++;
                pass_visitor_stats.max->push(pass_visitor_stats.depth);
                pass_visitor_stats.avg->push(pass_visitor_stats.depth);

                bool mutated = false;
                container_t< ptr<Stmt> > new_kids;
                for( const Stmt * stmt : statements ) {
                        try {
                                __pedantic_pass_assert( stmt );
                                const ast::Stmt * new_stmt = stmt->accept( *this );
                                assert( new_stmt );
                                if(new_stmt != stmt ) mutated = true;

                                // Make sure that it is either adding statements or declartions but not both
                                // this is because otherwise the order would be awkward to predict
                                assert(( empty( stmts_before ) && empty( stmts_after ))
                                    || ( empty( decls_before ) && empty( decls_after )) );



                                // Take all the statements which should have gone after, N/A for first iteration
                                __pass::take_all( std::back_inserter( new_kids ), decls_before, &mutated );
                                __pass::take_all( std::back_inserter( new_kids ), stmts_before, &mutated );

                                // Now add the statement if there is one
                                new_kids.emplace_back( new_stmt );

                                // Take all the declarations that go before
                                __pass::take_all( std::back_inserter( new_kids ), decls_after, &mutated );
                                __pass::take_all( std::back_inserter( new_kids ), stmts_after, &mutated );
                        }
                        catch ( SemanticErrorException &e ) {
                                errors.append( e );
                        }
                }
                pass_visitor_stats.depth--;
                if ( !errors.isEmpty() ) { throw errors; }

                return mutated ? new_kids : container_t< ptr<Stmt> >();
        }

        template< typename pass_t >
        template< template <class...> class container_t, typename node_t >
        container_t< ast::ptr<node_t> > ast::Pass< pass_t >::call_accept( const container_t< ast::ptr<node_t> > & container ) {
                __pedantic_pass_assert( __visit_children() );
                if( container.empty() ) return {};
                SemanticErrorException errors;

                pass_visitor_stats.depth++;
                pass_visitor_stats.max->push(pass_visitor_stats.depth);
                pass_visitor_stats.avg->push(pass_visitor_stats.depth);

                bool mutated = false;
                container_t< ast::ptr<node_t> > new_kids;
                for ( const node_t * node : container ) {
                        try {
                                __pedantic_pass_assert( node );
                                const node_t * new_stmt = strict_dynamic_cast< const node_t * >( node->accept( *this ) );
                                if(new_stmt != node ) mutated = true;

                                new_kids.emplace_back( new_stmt );
                        }
                        catch( SemanticErrorException &e ) {
                                errors.append( e );
                        }
                }
                pass_visitor_stats.depth--;
                if ( ! errors.isEmpty() ) { throw errors; }

                return mutated ? new_kids : container_t< ast::ptr<node_t> >();
        }

        template< typename pass_t >
        template<typename node_t, typename parent_t, typename child_t>
        void ast::Pass< pass_t >::maybe_accept(
                const node_t * & parent,
                child_t parent_t::*child
        ) {
                static_assert( std::is_base_of<parent_t, node_t>::value, "Error deducing member object" );

                if(__pass::skip(parent->*child)) return;
                const auto & old_val = __pass::get(parent->*child, 0);

                static_assert( !std::is_same<const ast::Node * &, decltype(old_val)>::value, "ERROR");

                auto new_val = call_accept( old_val );

                static_assert( !std::is_same<const ast::Node *, decltype(new_val)>::value || std::is_same<int, decltype(old_val)>::value, "ERROR");

                if( __pass::differs(old_val, new_val) ) {
                        auto new_parent = mutate(parent);
                        new_parent->*child = new_val;
                        parent = new_parent;
                }
        }


        template< typename pass_t >
        template< typename node_t >
        void ast::Pass< pass_t >::mutate_forall( const node_t *& node ) {
                if ( auto subs = __pass::forall::subs( pass, 0 ) ) {
                        // tracking TypeDecl substitution, full clone
                        if ( node->forall.empty() ) return;

                        node_t * mut = mutate( node );
                        mut->forall = subs->clone( node->forall, *this );
                        node = mut;
                } else {
                        // not tracking TypeDecl substitution, just mutate
                        maybe_accept( node, &node_t::forall );
                }
        }
}

//------------------------------------------------------------------------------------------------------------------------------------------------------------------------
//========================================================================================================================================================================
//========================================================================================================================================================================
//========================================================================================================================================================================
//========================================================================================================================================================================
//========================================================================================================================================================================
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------

template< typename pass_t >
inline void ast::accept_all( std::list< ast::ptr<ast::Decl> > & decls, ast::Pass< pass_t > & visitor ) {
        // We are going to aggregate errors for all these statements
        SemanticErrorException errors;

        // add a few useful symbols to the scope
        using __pass::empty;

        // get the stmts/decls that will need to be spliced in
        auto decls_before = __pass::declsToAddBefore( visitor.pass, 0);
        auto decls_after  = __pass::declsToAddAfter ( visitor.pass, 0);

        // update pass statitistics
        pass_visitor_stats.depth++;
        pass_visitor_stats.max->push(pass_visitor_stats.depth);
        pass_visitor_stats.avg->push(pass_visitor_stats.depth);

        for ( std::list< ast::ptr<ast::Decl> >::iterator i = decls.begin(); ; ++i ) {
                // splice in new declarations after previous decl
                if ( !empty( decls_after ) ) { decls.splice( i, *decls_after ); }

                if ( i == decls.end() ) break;

                try {
                        // run visitor on declaration
                        ast::ptr<ast::Decl> & node = *i;
                        assert( node );
                        node = node->accept( visitor );
                }
                catch( SemanticErrorException &e ) {
                        errors.append( e );
                }

                // splice in new declarations before current decl
                if ( !empty( decls_before ) ) { decls.splice( i, *decls_before ); }
        }
        pass_visitor_stats.depth--;
        if ( !errors.isEmpty() ) { throw errors; }
}

// A NOTE ON THE ORDER OF TRAVERSAL
//
// Types and typedefs have their base types visited before they are added to the type table.  This is ok, since there is
// no such thing as a recursive type or typedef.
//
//             typedef struct { T *x; } T; // never allowed
//
// for structs/unions, it is possible to have recursion, so the decl should be added as if it's incomplete to begin, the
// members are traversed, and then the complete type should be added (assuming the type is completed by this particular
// declaration).
//
//             struct T { struct T *x; }; // allowed
//
// It is important to add the complete type to the symbol table *after* the members/base has been traversed, since that
// traversal may modify the definition of the type and these modifications should be visible when the symbol table is
// queried later in this pass.

//--------------------------------------------------------------------------
// ObjectDecl
template< typename pass_t >
const ast::DeclWithType * ast::Pass< pass_t >::visit( const ast::ObjectDecl * node ) {
        VISIT_START( node );

        VISIT(
                {
                        guard_symtab guard { *this };
                        maybe_accept( node, &ObjectDecl::type );
                }
                maybe_accept( node, &ObjectDecl::init          );
                maybe_accept( node, &ObjectDecl::bitfieldWidth );
                maybe_accept( node, &ObjectDecl::attributes    );
        )

        __pass::symtab::addId( pass, 0, node );

        VISIT_END( DeclWithType, node );
}

//--------------------------------------------------------------------------
// FunctionDecl
template< typename pass_t >
const ast::DeclWithType * ast::Pass< pass_t >::visit( const ast::FunctionDecl * node ) {
        VISIT_START( node );

        __pass::symtab::addId( pass, 0, node );

        VISIT(maybe_accept( node, &FunctionDecl::withExprs );)
        {
                // with clause introduces a level of scope (for the with expression members).
                // with clause exprs are added to the symbol table before parameters so that parameters
                // shadow with exprs and not the other way around.
                guard_symtab guard { *this };
                __pass::symtab::addWith( pass, 0, node->withExprs, node );
                {
                        guard_symtab guard { *this };
                        // implicit add __func__ identifier as specified in the C manual 6.4.2.2
                        static ast::ptr< ast::ObjectDecl > func{ new ast::ObjectDecl{ 
                                CodeLocation{}, "__func__",
                                new ast::ArrayType{
                                        new ast::BasicType{ ast::BasicType::Char, ast::CV::Const },
                                        nullptr, VariableLen, DynamicDim
                                }
                        } };
                        __pass::symtab::addId( pass, 0, func );
                        VISIT(
                                maybe_accept( node, &FunctionDecl::type );
                                // function body needs to have the same scope as parameters - CompoundStmt will not enter
                                // a new scope if inFunction is true
                                ValueGuard< bool > oldInFunction( inFunction );
                                inFunction = true;
                                maybe_accept( node, &FunctionDecl::stmts );
                                maybe_accept( node, &FunctionDecl::attributes );
                        )
                }
        }

        VISIT_END( DeclWithType, node );
}

//--------------------------------------------------------------------------
// StructDecl
template< typename pass_t >
const ast::Decl * ast::Pass< pass_t >::visit( const ast::StructDecl * node ) {
        VISIT_START( node );

        // make up a forward declaration and add it before processing the members
        // needs to be on the heap because addStruct saves the pointer
        __pass::symtab::addStructFwd( pass, 0, node );

        VISIT({
                guard_symtab guard { * this };
                maybe_accept( node, &StructDecl::params  );
                maybe_accept( node, &StructDecl::members );
        })

        // this addition replaces the forward declaration
        __pass::symtab::addStruct( pass, 0, node );

        VISIT_END( Decl, node );
}

//--------------------------------------------------------------------------
// UnionDecl
template< typename pass_t >
const ast::Decl * ast::Pass< pass_t >::visit( const ast::UnionDecl * node ) {
        VISIT_START( node );

        // make up a forward declaration and add it before processing the members
        __pass::symtab::addUnionFwd( pass, 0, node );

        VISIT({
                guard_symtab guard { * this };
                maybe_accept( node, &UnionDecl::params  );
                maybe_accept( node, &UnionDecl::members );
        })

        __pass::symtab::addUnion( pass, 0, node );

        VISIT_END( Decl, node );
}

//--------------------------------------------------------------------------
// EnumDecl
template< typename pass_t >
const ast::Decl * ast::Pass< pass_t >::visit( const ast::EnumDecl * node ) {
        VISIT_START( node );

        __pass::symtab::addEnum( pass, 0, node );

        VISIT(
                // unlike structs, traits, and unions, enums inject their members into the global scope
                maybe_accept( node, &EnumDecl::params  );
                maybe_accept( node, &EnumDecl::members );
        )

        VISIT_END( Decl, node );
}

//--------------------------------------------------------------------------
// TraitDecl
template< typename pass_t >
const ast::Decl * ast::Pass< pass_t >::visit( const ast::TraitDecl * node ) {
        VISIT_START( node );

        VISIT({
                guard_symtab guard { *this };
                maybe_accept( node, &TraitDecl::params  );
                maybe_accept( node, &TraitDecl::members );
        })

        __pass::symtab::addTrait( pass, 0, node );

        VISIT_END( Decl, node );
}

//--------------------------------------------------------------------------
// TypeDecl
template< typename pass_t >
const ast::Decl * ast::Pass< pass_t >::visit( const ast::TypeDecl * node ) {
        VISIT_START( node );

        VISIT({
                guard_symtab guard { *this };
                maybe_accept( node, &TypeDecl::params );
                maybe_accept( node, &TypeDecl::base   );
        })

        // see A NOTE ON THE ORDER OF TRAVERSAL, above
        // note that assertions come after the type is added to the symtab, since they are not part of the type proper
        // and may depend on the type itself
        __pass::symtab::addType( pass, 0, node );

        VISIT(
                maybe_accept( node, &TypeDecl::assertions );

                {
                        guard_symtab guard { *this };
                        maybe_accept( node, &TypeDecl::init );
                }
        )

        VISIT_END( Decl, node );
}

//--------------------------------------------------------------------------
// TypedefDecl
template< typename pass_t >
const ast::Decl * ast::Pass< pass_t >::visit( const ast::TypedefDecl * node ) {
        VISIT_START( node );

        VISIT({
                guard_symtab guard { *this };
                maybe_accept( node, &TypedefDecl::params );
                maybe_accept( node, &TypedefDecl::base   );
        })

        __pass::symtab::addType( pass, 0, node );

        VISIT( maybe_accept( node, &TypedefDecl::assertions ); )

        VISIT_END( Decl, node );
}

//--------------------------------------------------------------------------
// AsmDecl
template< typename pass_t >
const ast::AsmDecl * ast::Pass< pass_t >::visit( const ast::AsmDecl * node ) {
        VISIT_START( node );

        VISIT(
                maybe_accept( node, &AsmDecl::stmt );
        )

        VISIT_END( AsmDecl, node );
}

//--------------------------------------------------------------------------
// StaticAssertDecl
template< typename pass_t >
const ast::StaticAssertDecl * ast::Pass< pass_t >::visit( const ast::StaticAssertDecl * node ) {
        VISIT_START( node );

        VISIT(
                maybe_accept( node, &StaticAssertDecl::cond );
                maybe_accept( node, &StaticAssertDecl::msg  );
        )

        VISIT_END( StaticAssertDecl, node );
}

//--------------------------------------------------------------------------
// CompoundStmt
template< typename pass_t >
const ast::CompoundStmt * ast::Pass< pass_t >::visit( const ast::CompoundStmt * node ) {
        VISIT_START( node );
        VISIT({
                // do not enter a new scope if inFunction is true - needs to check old state before the assignment
                auto guard1 = makeFuncGuard( [this, inFunctionCpy = this->inFunction]() {
                        if ( ! inFunctionCpy ) __pass::symtab::enter(pass, 0);
                }, [this, inFunctionCpy = this->inFunction]() {
                        if ( ! inFunctionCpy ) __pass::symtab::leave(pass, 0);
                });
                ValueGuard< bool > guard2( inFunction );
                guard_scope guard3 { *this };
                inFunction = false;
                maybe_accept( node, &CompoundStmt::kids );
        })
        VISIT_END( CompoundStmt, node );
}

//--------------------------------------------------------------------------
// ExprStmt
template< typename pass_t >
const ast::Stmt * ast::Pass< pass_t >::visit( const ast::ExprStmt * node ) {
        VISIT_START( node );

        VISIT(
                maybe_accept( node, &ExprStmt::expr );
        )

        VISIT_END( Stmt, node );
}

//--------------------------------------------------------------------------
// AsmStmt
template< typename pass_t >
const ast::Stmt * ast::Pass< pass_t >::visit( const ast::AsmStmt * node ) {
        VISIT_START( node )

        VISIT(
                maybe_accept( node, &AsmStmt::instruction );
                maybe_accept( node, &AsmStmt::output      );
                maybe_accept( node, &AsmStmt::input       );
                maybe_accept( node, &AsmStmt::clobber     );
        )

        VISIT_END( Stmt, node );
}

//--------------------------------------------------------------------------
// DirectiveStmt
template< typename pass_t >
const ast::Stmt * ast::Pass< pass_t >::visit( const ast::DirectiveStmt * node ) {
        VISIT_START( node )

        VISIT_END( Stmt, node );
}

//--------------------------------------------------------------------------
// IfStmt
template< typename pass_t >
const ast::Stmt * ast::Pass< pass_t >::visit( const ast::IfStmt * node ) {
        VISIT_START( node );

        VISIT({
                // if statements introduce a level of scope (for the initialization)
                guard_symtab guard { *this };
                maybe_accept( node, &IfStmt::inits    );
                maybe_accept( node, &IfStmt::cond     );
                maybe_accept( node, &IfStmt::thenPart );
                maybe_accept( node, &IfStmt::elsePart );
        })

        VISIT_END( Stmt, node );
}

//--------------------------------------------------------------------------
// WhileStmt
template< typename pass_t >
const ast::Stmt * ast::Pass< pass_t >::visit( const ast::WhileStmt * node ) {
        VISIT_START( node );

        VISIT({
                // while statements introduce a level of scope (for the initialization)
                guard_symtab guard { *this };
                maybe_accept( node, &WhileStmt::inits );
                maybe_accept( node, &WhileStmt::cond  );
                maybe_accept( node, &WhileStmt::body  );
        })

        VISIT_END( Stmt, node );
}

//--------------------------------------------------------------------------
// ForStmt
template< typename pass_t >
const ast::Stmt * ast::Pass< pass_t >::visit( const ast::ForStmt * node ) {
        VISIT_START( node );

        VISIT({
                // for statements introduce a level of scope (for the initialization)
                guard_symtab guard { *this };
                maybe_accept( node, &ForStmt::inits );
                maybe_accept( node, &ForStmt::cond  );
                maybe_accept( node, &ForStmt::inc   );
                maybe_accept( node, &ForStmt::body  );
        })

        VISIT_END( Stmt, node );
}

//--------------------------------------------------------------------------
// SwitchStmt
template< typename pass_t >
const ast::Stmt * ast::Pass< pass_t >::visit( const ast::SwitchStmt * node ) {
        VISIT_START( node );

        VISIT(
                maybe_accept( node, &SwitchStmt::cond  );
                maybe_accept( node, &SwitchStmt::stmts );
        )

        VISIT_END( Stmt, node );
}

//--------------------------------------------------------------------------
// CaseStmt
template< typename pass_t >
const ast::Stmt * ast::Pass< pass_t >::visit( const ast::CaseStmt * node ) {
        VISIT_START( node );

        VISIT(
                maybe_accept( node, &CaseStmt::cond  );
                maybe_accept( node, &CaseStmt::stmts );
        )

        VISIT_END( Stmt, node );
}

//--------------------------------------------------------------------------
// BranchStmt
template< typename pass_t >
const ast::Stmt * ast::Pass< pass_t >::visit( const ast::BranchStmt * node ) {
        VISIT_START( node );
        VISIT_END( Stmt, node );
}

//--------------------------------------------------------------------------
// ReturnStmt
template< typename pass_t >
const ast::Stmt * ast::Pass< pass_t >::visit( const ast::ReturnStmt * node ) {
        VISIT_START( node );

        VISIT(
                maybe_accept( node, &ReturnStmt::expr );
        )

        VISIT_END( Stmt, node );
}

//--------------------------------------------------------------------------
// ThrowStmt
template< typename pass_t >
const ast::Stmt * ast::Pass< pass_t >::visit( const ast::ThrowStmt * node ) {
        VISIT_START( node );

        VISIT(
                maybe_accept( node, &ThrowStmt::expr   );
                maybe_accept( node, &ThrowStmt::target );
        )

        VISIT_END( Stmt, node );
}

//--------------------------------------------------------------------------
// TryStmt
template< typename pass_t >
const ast::Stmt * ast::Pass< pass_t >::visit( const ast::TryStmt * node ) {
        VISIT_START( node );

        VISIT(
                maybe_accept( node, &TryStmt::body     );
                maybe_accept( node, &TryStmt::handlers );
                maybe_accept( node, &TryStmt::finally  );
        )

        VISIT_END( Stmt, node );
}

//--------------------------------------------------------------------------
// CatchStmt
template< typename pass_t >
const ast::Stmt * ast::Pass< pass_t >::visit( const ast::CatchStmt * node ) {
        VISIT_START( node );

        VISIT({
                // catch statements introduce a level of scope (for the caught exception)
                guard_symtab guard { *this };
                maybe_accept( node, &CatchStmt::decl );
                maybe_accept( node, &CatchStmt::cond );
                maybe_accept( node, &CatchStmt::body );
        })

        VISIT_END( Stmt, node );
}

//--------------------------------------------------------------------------
// FinallyStmt
template< typename pass_t >
const ast::Stmt * ast::Pass< pass_t >::visit( const ast::FinallyStmt * node ) {
        VISIT_START( node );

        VISIT(
                maybe_accept( node, &FinallyStmt::body );
        )

        VISIT_END( Stmt, node );
}

//--------------------------------------------------------------------------
// WaitForStmt
template< typename pass_t >
const ast::Stmt * ast::Pass< pass_t >::visit( const ast::WaitForStmt * node ) {
        VISIT_START( node );
                // for( auto & clause : node->clauses ) {
                //      maybeAccept_impl( clause.target.function, *this );
                //      maybeAccept_impl( clause.target.arguments, *this );

                //      maybeAccept_impl( clause.statement, *this );
                //      maybeAccept_impl( clause.condition, *this );
                // }

        VISIT({
                std::vector<WaitForStmt::Clause> new_clauses;
                new_clauses.reserve( node->clauses.size() );
                bool mutated = false;
                for( const auto & clause : node->clauses ) {

                        const Expr * func = clause.target.func ? clause.target.func->accept(*this) : nullptr;
                        if(func != clause.target.func) mutated = true;

                        std::vector<ptr<Expr>> new_args;
                        new_args.reserve(clause.target.args.size());
                        for( const auto & arg : clause.target.args ) {
                                auto a = arg->accept(*this);
                                new_args.push_back( a );
                                if( a != arg ) mutated = true;
                        }

                        const Stmt * stmt = clause.stmt ? clause.stmt->accept(*this) : nullptr;
                        if(stmt != clause.stmt) mutated = true;

                        const Expr * cond = clause.cond ? clause.cond->accept(*this) : nullptr;
                        if(cond != clause.cond) mutated = true;

                        new_clauses.push_back( WaitForStmt::Clause{ {func, std::move(new_args) }, stmt, cond } );
                }

                if(mutated) {
                        auto n = mutate(node);
                        n->clauses = std::move( new_clauses );
                        node = n;
                }
        })

        #define maybe_accept(field) \
                if(node->field) { \
                        auto nval = call_accept( node->field ); \
                        if(nval != node->field ) { \
                                auto nparent = mutate(node); \
                                nparent->field = nval; \
                                node = nparent; \
                        } \
                }

        VISIT(
                maybe_accept( timeout.time );
                maybe_accept( timeout.stmt );
                maybe_accept( timeout.cond );
                maybe_accept( orElse.stmt  );
                maybe_accept( orElse.cond  );
        )

        #undef maybe_accept

        VISIT_END( Stmt, node );
}

//--------------------------------------------------------------------------
// WithStmt
template< typename pass_t >
const ast::Stmt * ast::Pass< pass_t >::visit( const ast::WithStmt * node ) {
        VISIT_START( node );

        VISIT(
                maybe_accept( node, &WithStmt::exprs );
                {
                        // catch statements introduce a level of scope (for the caught exception)
                        guard_symtab guard { *this };
                        __pass::symtab::addWith( pass, 0, node->exprs, node );
                        maybe_accept( node, &WithStmt::stmt );
                }
        )
        VISIT_END( Stmt, node );
}

//--------------------------------------------------------------------------
// NullStmt
template< typename pass_t >
const ast::NullStmt * ast::Pass< pass_t >::visit( const ast::NullStmt * node ) {
        VISIT_START( node );
        VISIT_END( NullStmt, node );
}

//--------------------------------------------------------------------------
// DeclStmt
template< typename pass_t >
const ast::Stmt * ast::Pass< pass_t >::visit( const ast::DeclStmt * node ) {
        VISIT_START( node );

        VISIT(
                maybe_accept( node, &DeclStmt::decl );
        )

        VISIT_END( Stmt, node );
}

//--------------------------------------------------------------------------
// ImplicitCtorDtorStmt
template< typename pass_t >
const ast::Stmt * ast::Pass< pass_t >::visit( const ast::ImplicitCtorDtorStmt * node ) {
        VISIT_START( node );

        // For now this isn't visited, it is unclear if this causes problem
        // if all tests are known to pass, remove this code
        // VISIT(
        //      maybe_accept( node, &ImplicitCtorDtorStmt::callStmt );
        // )

        VISIT_END( Stmt, node );
}

//--------------------------------------------------------------------------
// ApplicationExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::ApplicationExpr * node ) {
        VISIT_START( node );

        VISIT(
                {
                        guard_symtab guard { *this };
                        maybe_accept( node, &ApplicationExpr::result );
                }
                maybe_accept( node, &ApplicationExpr::func );
                maybe_accept( node, &ApplicationExpr::args );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// UntypedExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::UntypedExpr * node ) {
        VISIT_START( node );

        VISIT(
                {
                        guard_symtab guard { *this };
                        maybe_accept( node, &UntypedExpr::result );
                }

                maybe_accept( node, &UntypedExpr::args );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// NameExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::NameExpr * node ) {
        VISIT_START( node );

        VISIT({
                guard_symtab guard { *this };
                maybe_accept( node, &NameExpr::result );
        })

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// CastExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::CastExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &CastExpr::result );
                }
                maybe_accept( node, &CastExpr::arg );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// KeywordCastExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::KeywordCastExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &KeywordCastExpr::result );
                }
                maybe_accept( node, &KeywordCastExpr::arg );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// VirtualCastExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::VirtualCastExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &VirtualCastExpr::result );
                }
                maybe_accept( node, &VirtualCastExpr::arg );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// AddressExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::AddressExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &AddressExpr::result );
                }
                maybe_accept( node, &AddressExpr::arg );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// LabelAddressExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::LabelAddressExpr * node ) {
        VISIT_START( node );

        VISIT({
                guard_symtab guard { *this };
                maybe_accept( node, &LabelAddressExpr::result );
        })

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// UntypedMemberExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::UntypedMemberExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &UntypedMemberExpr::result );
                }
                maybe_accept( node, &UntypedMemberExpr::aggregate );
                maybe_accept( node, &UntypedMemberExpr::member    );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// MemberExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::MemberExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &MemberExpr::result );
                }
                maybe_accept( node, &MemberExpr::aggregate );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// VariableExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::VariableExpr * node ) {
        VISIT_START( node );

        VISIT({
                guard_symtab guard { *this };
                maybe_accept( node, &VariableExpr::result );
        })

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// ConstantExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::ConstantExpr * node ) {
        VISIT_START( node );

        VISIT({
                guard_symtab guard { *this };
                maybe_accept( node, &ConstantExpr::result );
        })

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// SizeofExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::SizeofExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &SizeofExpr::result );
                }
                if ( node->type ) {
                        maybe_accept( node, &SizeofExpr::type );
                } else {
                        maybe_accept( node, &SizeofExpr::expr );
                }
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// AlignofExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::AlignofExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &AlignofExpr::result );
                }
                if ( node->type ) {
                        maybe_accept( node, &AlignofExpr::type );
                } else {
                        maybe_accept( node, &AlignofExpr::expr );
                }
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// UntypedOffsetofExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::UntypedOffsetofExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &UntypedOffsetofExpr::result );
                }
                maybe_accept( node, &UntypedOffsetofExpr::type   );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// OffsetofExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::OffsetofExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &OffsetofExpr::result );
                }
                maybe_accept( node, &OffsetofExpr::type   );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// OffsetPackExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::OffsetPackExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &OffsetPackExpr::result );
                }
                maybe_accept( node, &OffsetPackExpr::type   );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// LogicalExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::LogicalExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &LogicalExpr::result );
                }
                maybe_accept( node, &LogicalExpr::arg1 );
                maybe_accept( node, &LogicalExpr::arg2 );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// ConditionalExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::ConditionalExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &ConditionalExpr::result );
                }
                maybe_accept( node, &ConditionalExpr::arg1 );
                maybe_accept( node, &ConditionalExpr::arg2 );
                maybe_accept( node, &ConditionalExpr::arg3 );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// CommaExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::CommaExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &CommaExpr::result );
                }
                maybe_accept( node, &CommaExpr::arg1 );
                maybe_accept( node, &CommaExpr::arg2 );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// TypeExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::TypeExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &TypeExpr::result );
                }
                maybe_accept( node, &TypeExpr::type );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// AsmExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::AsmExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &AsmExpr::result );
                }
                maybe_accept( node, &AsmExpr::inout      );
                maybe_accept( node, &AsmExpr::constraint );
                maybe_accept( node, &AsmExpr::operand    );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// ImplicitCopyCtorExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::ImplicitCopyCtorExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &ImplicitCopyCtorExpr::result );
                }
                maybe_accept( node, &ImplicitCopyCtorExpr::callExpr    );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// ConstructorExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::ConstructorExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &ConstructorExpr::result );
                }
                maybe_accept( node, &ConstructorExpr::callExpr );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// CompoundLiteralExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::CompoundLiteralExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &CompoundLiteralExpr::result );
                }
                maybe_accept( node, &CompoundLiteralExpr::init );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// RangeExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::RangeExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &RangeExpr::result );
                }
                maybe_accept( node, &RangeExpr::low    );
                maybe_accept( node, &RangeExpr::high   );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// UntypedTupleExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::UntypedTupleExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &UntypedTupleExpr::result );
                }
                maybe_accept( node, &UntypedTupleExpr::exprs  );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// TupleExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::TupleExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &TupleExpr::result );
                }
                maybe_accept( node, &TupleExpr::exprs  );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// TupleIndexExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::TupleIndexExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &TupleIndexExpr::result );
                }
                maybe_accept( node, &TupleIndexExpr::tuple  );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// TupleAssignExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::TupleAssignExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &TupleAssignExpr::result );
                }
                maybe_accept( node, &TupleAssignExpr::stmtExpr );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// StmtExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::StmtExpr * node ) {
        VISIT_START( node );

        VISIT(// don't want statements from outer CompoundStmts to be added to this StmtExpr
                // get the stmts that will need to be spliced in
                auto stmts_before = __pass::stmtsToAddBefore( pass, 0);
                auto stmts_after  = __pass::stmtsToAddAfter ( pass, 0);

                // These may be modified by subnode but most be restored once we exit this statemnet.
                ValueGuardPtr< const ast::TypeSubstitution * > __old_env( __pass::env( pass, 0) );
                ValueGuardPtr< typename std::remove_pointer< decltype(stmts_before) >::type > __old_decls_before( stmts_before );
                ValueGuardPtr< typename std::remove_pointer< decltype(stmts_after ) >::type > __old_decls_after ( stmts_after  );

                {
                        guard_symtab guard { *this };
                        maybe_accept( node, &StmtExpr::result );
                }
                maybe_accept( node, &StmtExpr::stmts       );
                maybe_accept( node, &StmtExpr::returnDecls );
                maybe_accept( node, &StmtExpr::dtors       );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// UniqueExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::UniqueExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &UniqueExpr::result );
                }
                maybe_accept( node, &UniqueExpr::expr   );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// UntypedInitExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::UntypedInitExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &UntypedInitExpr::result );
                }
                maybe_accept( node, &UntypedInitExpr::expr   );
                // not currently visiting initAlts, but this doesn't matter since this node is only used in the resolver.
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// InitExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::InitExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &InitExpr::result );
                }
                maybe_accept( node, &InitExpr::expr   );
                maybe_accept( node, &InitExpr::designation );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// DeletedExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::DeletedExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &DeletedExpr::result );
                }
                maybe_accept( node, &DeletedExpr::expr );
                // don't visit deleteStmt, because it is a pointer to somewhere else in the tree.
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// DefaultArgExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::DefaultArgExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &DefaultArgExpr::result );
                }
                maybe_accept( node, &DefaultArgExpr::expr );
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// GenericExpr
template< typename pass_t >
const ast::Expr * ast::Pass< pass_t >::visit( const ast::GenericExpr * node ) {
        VISIT_START( node );

        VISIT({
                        guard_symtab guard { *this };
                        maybe_accept( node, &GenericExpr::result );
                }
                maybe_accept( node, &GenericExpr::control );

                std::vector<GenericExpr::Association> new_kids;
                new_kids.reserve(node->associations.size());
                bool mutated = false;
                for( const auto & assoc : node->associations ) {
                        const Type * type = nullptr;
                        if( assoc.type ) {
                                guard_symtab guard { *this };
                                type = assoc.type->accept( *this );
                                if( type != assoc.type ) mutated = true;
                        }
                        const Expr * expr = nullptr;
                        if( assoc.expr ) {
                                expr = assoc.expr->accept( *this );
                                if( expr != assoc.expr ) mutated = true;
                        }
                        new_kids.emplace_back( type, expr );
                }

                if(mutated) {
                        auto n = mutate(node);
                        n->associations = std::move( new_kids );
                        node = n;
                }
        )

        VISIT_END( Expr, node );
}

//--------------------------------------------------------------------------
// VoidType
template< typename pass_t >
const ast::Type * ast::Pass< pass_t >::visit( const ast::VoidType * node ) {
        VISIT_START( node );

        VISIT_END( Type, node );
}

//--------------------------------------------------------------------------
// BasicType
template< typename pass_t >
const ast::Type * ast::Pass< pass_t >::visit( const ast::BasicType * node ) {
        VISIT_START( node );

        VISIT_END( Type, node );
}

//--------------------------------------------------------------------------
// PointerType
template< typename pass_t >
const ast::Type * ast::Pass< pass_t >::visit( const ast::PointerType * node ) {
        VISIT_START( node );

        VISIT(
                // xxx - should PointerType visit/mutate dimension?
                maybe_accept( node, &PointerType::base );
        )

        VISIT_END( Type, node );
}

//--------------------------------------------------------------------------
// ArrayType
template< typename pass_t >
const ast::Type * ast::Pass< pass_t >::visit( const ast::ArrayType * node ) {
        VISIT_START( node );

        VISIT(
                maybe_accept( node, &ArrayType::dimension );
                maybe_accept( node, &ArrayType::base );
        )

        VISIT_END( Type, node );
}

//--------------------------------------------------------------------------
// ReferenceType
template< typename pass_t >
const ast::Type * ast::Pass< pass_t >::visit( const ast::ReferenceType * node ) {
        VISIT_START( node );

        VISIT(
                maybe_accept( node, &ReferenceType::base );
        )

        VISIT_END( Type, node );
}

//--------------------------------------------------------------------------
// QualifiedType
template< typename pass_t >
const ast::Type * ast::Pass< pass_t >::visit( const ast::QualifiedType * node ) {
        VISIT_START( node );

        VISIT(
                maybe_accept( node, &QualifiedType::parent );
                maybe_accept( node, &QualifiedType::child );
        )

        VISIT_END( Type, node );
}

//--------------------------------------------------------------------------
// FunctionType
template< typename pass_t >
const ast::Type * ast::Pass< pass_t >::visit( const ast::FunctionType * node ) {
        VISIT_START( node );

        VISIT({
                guard_forall_subs forall_guard { *this, node };
                mutate_forall( node );
                maybe_accept( node, &FunctionType::returns );
                maybe_accept( node, &FunctionType::params  );
        })

        VISIT_END( Type, node );
}

//--------------------------------------------------------------------------
// StructInstType
template< typename pass_t >
const ast::Type * ast::Pass< pass_t >::visit( const ast::StructInstType * node ) {
        VISIT_START( node );

        __pass::symtab::addStruct( pass, 0, node->name );

        VISIT({
                guard_symtab guard { *this };
                guard_forall_subs forall_guard { *this, node };
                mutate_forall( node );
                maybe_accept( node, &StructInstType::params );
        })

        VISIT_END( Type, node );
}

//--------------------------------------------------------------------------
// UnionInstType
template< typename pass_t >
const ast::Type * ast::Pass< pass_t >::visit( const ast::UnionInstType * node ) {
        VISIT_START( node );

        __pass::symtab::addUnion( pass, 0, node->name );

        VISIT({
                guard_symtab guard { *this };
                guard_forall_subs forall_guard { *this, node };
                mutate_forall( node );
                maybe_accept( node, &UnionInstType::params );
        })

        VISIT_END( Type, node );
}

//--------------------------------------------------------------------------
// EnumInstType
template< typename pass_t >
const ast::Type * ast::Pass< pass_t >::visit( const ast::EnumInstType * node ) {
        VISIT_START( node );

        VISIT({
                guard_forall_subs forall_guard { *this, node };
                mutate_forall( node );
                maybe_accept( node, &EnumInstType::params );
        })

        VISIT_END( Type, node );
}

//--------------------------------------------------------------------------
// TraitInstType
template< typename pass_t >
const ast::Type * ast::Pass< pass_t >::visit( const ast::TraitInstType * node ) {
        VISIT_START( node );

        VISIT({
                guard_forall_subs forall_guard { *this, node };
                mutate_forall( node );
                maybe_accept( node, &TraitInstType::params );
        })

        VISIT_END( Type, node );
}

//--------------------------------------------------------------------------
// TypeInstType
template< typename pass_t >
const ast::Type * ast::Pass< pass_t >::visit( const ast::TypeInstType * node ) {
        VISIT_START( node );

        VISIT(
                {
                        guard_forall_subs forall_guard { *this, node };
                        mutate_forall( node );
                        maybe_accept( node, &TypeInstType::params );
                }
                // ensure that base re-bound if doing substitution
                __pass::forall::replace( pass, 0, node );
        )

        VISIT_END( Type, node );
}

//--------------------------------------------------------------------------
// TupleType
template< typename pass_t >
const ast::Type * ast::Pass< pass_t >::visit( const ast::TupleType * node ) {
        VISIT_START( node );

        VISIT(
                maybe_accept( node, &TupleType::types );
                maybe_accept( node, &TupleType::members );
        )

        VISIT_END( Type, node );
}

//--------------------------------------------------------------------------
// TypeofType
template< typename pass_t >
const ast::Type * ast::Pass< pass_t >::visit( const ast::TypeofType * node ) {
        VISIT_START( node );

        VISIT(
                maybe_accept( node, &TypeofType::expr );
        )

        VISIT_END( Type, node );
}

//--------------------------------------------------------------------------
// VarArgsType
template< typename pass_t >
const ast::Type * ast::Pass< pass_t >::visit( const ast::VarArgsType * node ) {
        VISIT_START( node );

        VISIT_END( Type, node );
}

//--------------------------------------------------------------------------
// ZeroType
template< typename pass_t >
const ast::Type * ast::Pass< pass_t >::visit( const ast::ZeroType * node ) {
        VISIT_START( node );

        VISIT_END( Type, node );
}

//--------------------------------------------------------------------------
// OneType
template< typename pass_t >
const ast::Type * ast::Pass< pass_t >::visit( const ast::OneType * node ) {
        VISIT_START( node );

        VISIT_END( Type, node );
}

//--------------------------------------------------------------------------
// GlobalScopeType
template< typename pass_t >
const ast::Type * ast::Pass< pass_t >::visit( const ast::GlobalScopeType * node ) {
        VISIT_START( node );

        VISIT_END( Type, node );
}


//--------------------------------------------------------------------------
// Designation
template< typename pass_t >
const ast::Designation * ast::Pass< pass_t >::visit( const ast::Designation * node ) {
        VISIT_START( node );

        VISIT( maybe_accept( node, &Designation::designators ); )

        VISIT_END( Designation, node );
}

//--------------------------------------------------------------------------
// SingleInit
template< typename pass_t >
const ast::Init * ast::Pass< pass_t >::visit( const ast::SingleInit * node ) {
        VISIT_START( node );

        VISIT(
                maybe_accept( node, &SingleInit::value );
        )

        VISIT_END( Init, node );
}

//--------------------------------------------------------------------------
// ListInit
template< typename pass_t >
const ast::Init * ast::Pass< pass_t >::visit( const ast::ListInit * node ) {
        VISIT_START( node );

        VISIT(
                maybe_accept( node, &ListInit::designations );
                maybe_accept( node, &ListInit::initializers );
        )

        VISIT_END( Init, node );
}

//--------------------------------------------------------------------------
// ConstructorInit
template< typename pass_t >
const ast::Init * ast::Pass< pass_t >::visit( const ast::ConstructorInit * node ) {
        VISIT_START( node );

        VISIT(
                maybe_accept( node, &ConstructorInit::ctor );
                maybe_accept( node, &ConstructorInit::dtor );
                maybe_accept( node, &ConstructorInit::init );
        )

        VISIT_END( Init, node );
}

//--------------------------------------------------------------------------
// Attribute
template< typename pass_t >
const ast::Attribute * ast::Pass< pass_t >::visit( const ast::Attribute * node  )  {
        VISIT_START( node );

        VISIT(
                maybe_accept( node, &Attribute::params );
        )

        VISIT_END( Attribute, node );
}

//--------------------------------------------------------------------------
// TypeSubstitution
template< typename pass_t >
const ast::TypeSubstitution * ast::Pass< pass_t >::visit( const ast::TypeSubstitution * node ) {
        VISIT_START( node );

        VISIT(
                {
                        bool mutated = false;
                        std::unordered_map< std::string, ast::ptr< ast::Type > > new_map;
                        for ( const auto & p : node->typeEnv ) {
                                guard_symtab guard { *this };
                                auto new_node = p.second->accept( *this );
                                if (new_node != p.second) mutated = false;
                                new_map.insert({ p.first, new_node });
                        }
                        if (mutated) {
                                auto new_node = mutate( node );
                                new_node->typeEnv.swap( new_map );
                                node = new_node;
                        }
                }

                {
                        bool mutated = false;
                        std::unordered_map< std::string, ast::ptr< ast::Expr > > new_map;
                        for ( const auto & p : node->varEnv ) {
                                guard_symtab guard { *this };
                                auto new_node = p.second->accept( *this );
                                if (new_node != p.second) mutated = false;
                                new_map.insert({ p.first, new_node });
                        }
                        if (mutated) {
                                auto new_node = mutate( node );
                                new_node->varEnv.swap( new_map );
                                node = new_node;
                        }
                }
        )

        VISIT_END( TypeSubstitution, node );
}

#undef VISIT_START
#undef VISIT
#undef VISIT_END