Changes in src/SymTab/Validate.cc [44547b0:5408b59]

File:

• src/SymTab/Validate.cc (modified) (2 diffs)

src/SymTab/Validate.cc

@@ -47 +47 @@
 #include <utility>                     // for pair
 
+#include "AST/Chain.hpp"
+#include "AST/Decl.hpp"
+#include "AST/Node.hpp"
+#include "AST/Pass.hpp"
+#include "AST/SymbolTable.hpp"
+#include "AST/Type.hpp"
+#include "AST/TypeSubstitution.hpp"
 #include "CodeGen/CodeGenerator.h"     // for genName
 #include "CodeGen/OperatorTable.h"     // for isCtorDtor, isCtorDtorAssign
@@ -1319 +1326 @@
         }
 
+namespace {
+        /// Replaces enum types by int, and function/array types in function parameter and return
+        /// lists by appropriate pointers
+        /*
+        struct EnumAndPointerDecay_new {
+                const ast::EnumDecl * previsit( const ast::EnumDecl * enumDecl ) {
+                        // set the type of each member of the enumeration to be EnumConstant
+                        for ( unsigned i = 0; i < enumDecl->members.size(); ++i ) {
+                                // build new version of object with EnumConstant
+                                ast::ptr< ast::ObjectDecl > obj =
+                                        enumDecl->members[i].strict_as< ast::ObjectDecl >();
+                                obj.get_and_mutate()->type =
+                                        new ast::EnumInstType{ enumDecl->name, ast::CV::Const };
+
+                                // set into decl
+                                ast::EnumDecl * mut = mutate( enumDecl );
+                                mut->members[i] = obj.get();
+                                enumDecl = mut;
+                        }
+                        return enumDecl;
+                }
+
+                static const ast::FunctionType * fixFunctionList(
+                        const ast::FunctionType * func,
+                        std::vector< ast::ptr< ast::DeclWithType > > ast::FunctionType::* field,
+                        ast::ArgumentFlag isVarArgs = ast::FixedArgs
+                ) {
+                        const auto & dwts = func->* field;
+                        unsigned nvals = dwts.size();
+                        bool hasVoid = false;
+                        for ( unsigned i = 0; i < nvals; ++i ) {
+                                func = ast::mutate_field_index( func, field, i, fixFunction( dwts[i], hasVoid ) );
+                        }
+
+                        // the only case in which "void" is valid is where it is the only one in the list
+                        if ( hasVoid && ( nvals > 1 || isVarArgs ) ) {
+                                SemanticError(
+                                        dwts.front()->location, func, "invalid type void in function type" );
+                        }
+
+                        // one void is the only thing in the list, remove it
+                        if ( hasVoid ) {
+                                func = ast::mutate_field(
+                                        func, field, std::vector< ast::ptr< ast::DeclWithType > >{} );
+                        }
+
+                        return func;
+                }
+
+                const ast::FunctionType * previsit( const ast::FunctionType * func ) {
+                        func = fixFunctionList( func, &ast::FunctionType::params, func->isVarArgs );
+                        return fixFunctionList( func, &ast::FunctionType::returns );
+                }
+        };
+
+        /// expand assertions from a trait instance, performing appropriate type variable substitutions
+        void expandAssertions(
+                const ast::TraitInstType * inst, std::vector< ast::ptr< ast::DeclWithType > > & out
+        ) {
+                assertf( inst->base, "Trait instance not linked to base trait: %s", toCString( inst ) );
+
+                // build list of trait members, substituting trait decl parameters for instance parameters
+                ast::TypeSubstitution sub{
+                        inst->base->params.begin(), inst->base->params.end(), inst->params.begin() };
+                // deliberately take ast::ptr by-value to ensure this does not mutate inst->base
+                for ( ast::ptr< ast::Decl > decl : inst->base->members ) {
+                        auto member = decl.strict_as< ast::DeclWithType >();
+                        sub.apply( member );
+                        out.emplace_back( member );
+                }
+        }
+
+        /// Associates forward declarations of aggregates with their definitions
+        class LinkReferenceToTypes_new final
+        : public ast::WithSymbolTable, public ast::WithGuards, public
+          ast::WithVisitorRef<LinkReferenceToTypes_new>, public ast::WithShortCircuiting {
+
+                // these maps of uses of forward declarations of types need to have the actual type
+                // declaration switched in * after * they have been traversed. To enable this in the
+                // ast::Pass framework, any node that needs to be so mutated has mutate() called on it
+                // before it is placed in the map, properly updating its parents in the usual traversal,
+                // then can have the actual mutation applied later
+                using ForwardEnumsType = std::unordered_multimap< std::string, ast::EnumInstType * >;
+                using ForwardStructsType = std::unordered_multimap< std::string, ast::StructInstType * >;
+                using ForwardUnionsType = std::unordered_multimap< std::string, ast::UnionInstType * >;
+
+                const CodeLocation & location;
+                const ast::SymbolTable * localSymtab;
+
+                ForwardEnumsType forwardEnums;
+                ForwardStructsType forwardStructs;
+                ForwardUnionsType forwardUnions;
+
+                /// true if currently in a generic type body, so that type parameter instances can be
+                /// renamed appropriately
+                bool inGeneric = false;
+
+        public:
+                /// contstruct using running symbol table
+                LinkReferenceToTypes_new( const CodeLocation & loc )
+                : location( loc ), localSymtab( &symtab ) {}
+
+                /// construct using provided symbol table
+                LinkReferenceToTypes_new( const CodeLocation & loc, const ast::SymbolTable & syms )
+                : location( loc ), localSymtab( &syms ) {}
+
+                const ast::Type * postvisit( const ast::TypeInstType * typeInst ) {
+                        // ensure generic parameter instances are renamed like the base type
+                        if ( inGeneric && typeInst->base ) {
+                                typeInst = ast::mutate_field(
+                                        typeInst, &ast::TypeInstType::name, typeInst->base->name );
+                        }
+
+                        if (
+                                auto typeDecl = dynamic_cast< const ast::TypeDecl * >(
+                                        localSymtab->lookupType( typeInst->name ) )
+                        ) {
+                                typeInst = ast::mutate_field( typeInst, &ast::TypeInstType::kind, typeDecl->kind );
+                        }
+
+                        return typeInst;
+                }
+
+                const ast::Type * postvisit( const ast::EnumInstType * inst ) {
+                        const ast::EnumDecl * decl = localSymtab->lookupEnum( inst->name );
+                        // not a semantic error if the enum is not found, just an implicit forward declaration
+                        if ( decl ) {
+                                inst = ast::mutate_field( inst, &ast::EnumInstType::base, decl );
+                        }
+                        if ( ! decl || ! decl->body ) {
+                                // forward declaration
+                                auto mut = mutate( inst );
+                                forwardEnums.emplace( inst->name, mut );
+                                inst = mut;
+                        }
+                        return inst;
+                }
+
+                void checkGenericParameters( const ast::BaseInstType * inst ) {
+                        for ( const ast::Expr * param : inst->params ) {
+                                if ( ! dynamic_cast< const ast::TypeExpr * >( param ) ) {
+                                        SemanticError(
+                                                location, inst, "Expression parameters for generic types are currently "
+                                                "unsupported: " );
+                                }
+                        }
+                }
+
+                const ast::StructInstType * postvisit( const ast::StructInstType * inst ) {
+                        const ast::StructDecl * decl = localSymtab->lookupStruct( inst->name );
+                        // not a semantic error if the struct is not found, just an implicit forward declaration
+                        if ( decl ) {
+                                inst = ast::mutate_field( inst, &ast::StructInstType::base, decl );
+                        }
+                        if ( ! decl || ! decl->body ) {
+                                // forward declaration
+                                auto mut = mutate( inst );
+                                forwardStructs.emplace( inst->name, mut );
+                                inst = mut;
+                        }
+                        checkGenericParameters( inst );
+                        return inst;
+                }
+
+                const ast::UnionInstType * postvisit( const ast::UnionInstType * inst ) {
+                        const ast::UnionDecl * decl = localSymtab->lookupUnion( inst->name );
+                        // not a semantic error if the struct is not found, just an implicit forward declaration
+                        if ( decl ) {
+                                inst = ast::mutate_field( inst, &ast::UnionInstType::base, decl );
+                        }
+                        if ( ! decl || ! decl->body ) {
+                                // forward declaration
+                                auto mut = mutate( inst );
+                                forwardUnions.emplace( inst->name, mut );
+                                inst = mut;
+                        }
+                        checkGenericParameters( inst );
+                        return inst;
+                }
+
+                const ast::Type * postvisit( const ast::TraitInstType * traitInst ) {
+                        // handle other traits
+                        const ast::TraitDecl * traitDecl = localSymtab->lookupTrait( traitInst->name );
+                        if ( ! traitDecl )       {
+                                SemanticError( location, "use of undeclared trait " + traitInst->name );
+                        }
+                        if ( traitDecl->params.size() != traitInst->params.size() ) {
+                                SemanticError( location, traitInst, "incorrect number of trait parameters: " );
+                        }
+                        traitInst = ast::mutate_field( traitInst, &ast::TraitInstType::base, traitDecl );
+
+                        // need to carry over the "sized" status of each decl in the instance
+                        for ( unsigned i = 0; i < traitDecl->params.size(); ++i ) {
+                                auto expr = traitInst->params[i].as< ast::TypeExpr >();
+                                if ( ! expr ) {
+                                        SemanticError(
+                                                traitInst->params[i].get(), "Expression parameters for trait instances "
+                                                "are currently unsupported: " );
+                                }
+
+                                if ( auto inst = expr->type.as< ast::TypeInstType >() ) {
+                                        if ( traitDecl->params[i]->sized && ! inst->base->sized ) {
+                                                // traitInst = ast::mutate_field_index(
+                                                //      traitInst, &ast::TraitInstType::params, i,
+                                                //      ...
+                                                // );
+                                                ast::TraitInstType * mut = ast::mutate( traitInst );
+                                                ast::chain_mutate( mut->params[i] )
+                                                        ( &ast::TypeExpr::type )
+                                                                ( &ast::TypeInstType::base )->sized = true;
+                                                traitInst = mut;
+                                        }
+                                }
+                        }
+
+                        return traitInst;
+                }
+
+                void previsit( const ast::QualifiedType * ) { visit_children = false; }
+
+                const ast::Type * postvisit( const ast::QualifiedType * qualType ) {
+                        // linking only makes sense for the "oldest ancestor" of the qualified type
+                        return ast::mutate_field(
+                                qualType, &ast::QualifiedType::parent, qualType->parent->accept( * visitor ) );
+                }
+
+                const ast::Decl * postvisit( const ast::EnumDecl * enumDecl ) {
+                        // visit enum members first so that the types of self-referencing members are updated
+                        // properly
+                        if ( ! enumDecl->body ) return enumDecl;
+
+                        // update forward declarations to point here
+                        auto fwds = forwardEnums.equal_range( enumDecl->name );
+                        if ( fwds.first != fwds.second ) {
+                                auto inst = fwds.first;
+                                do {
+                                        // forward decl is stored * mutably * in map, can thus be updated
+                                        inst->second->base = enumDecl;
+                                } while ( ++inst != fwds.second );
+                                forwardEnums.erase( fwds.first, fwds.second );
+                        }
+
+                        // ensure that enumerator initializers are properly set
+                        for ( unsigned i = 0; i < enumDecl->members.size(); ++i ) {
+                                auto field = enumDecl->members[i].strict_as< ast::ObjectDecl >();
+                                if ( field->init ) {
+                                        // need to resolve enumerator initializers early so that other passes that
+                                        // determine if an expression is constexpr have appropriate information
+                                        auto init = field->init.strict_as< ast::SingleInit >();
+
+                                        enumDecl = ast::mutate_field_index(
+                                                enumDecl, &ast::EnumDecl::members, i,
+                                                ast::mutate_field( field, &ast::ObjectDecl::init,
+                                                        ast::mutate_field( init, &ast::SingleInit::value,
+                                                                ResolvExpr::findSingleExpression(
+                                                                        init->value, new ast::BasicType{ ast::BasicType::SignedInt },
+                                                                        symtab ) ) ) );
+                                }
+                        }
+
+                        return enumDecl;
+                }
+
+                /// rename generic type parameters uniquely so that they do not conflict with user defined
+                /// function forall parameters, e.g. the T in Box and the T in f, below
+                ///   forall(otype T)
+                ///   struct Box {
+                ///     T x;
+                ///   };
+                ///   forall(otype T)
+                ///   void f(Box(T) b) {
+                ///     ...
+                ///   }
+                template< typename AggrDecl >
+                const AggrDecl * renameGenericParams( const AggrDecl * aggr ) {
+                        GuardValue( inGeneric );
+                        inGeneric = ! aggr->params.empty();
+
+                        for ( unsigned i = 0; i < aggr->params.size(); ++i ) {
+                                const ast::TypeDecl * td = aggr->params[i];
+
+                                aggr = ast::mutate_field_index(
+                                        aggr, &AggrDecl::params, i,
+                                        ast::mutate_field( td, &ast::TypeDecl::name, "__" + td->name + "_generic_" ) );
+                        }
+                        return aggr;
+                }
+
+                const ast::StructDecl * previsit( const ast::StructDecl * structDecl ) {
+                        return renameGenericParams( structDecl );
+                }
+
+                void postvisit( const ast::StructDecl * structDecl ) {
+                        // visit struct members first so that the types of self-referencing members are
+                        // updated properly
+                        if ( ! structDecl->body ) return;
+
+                        // update forward declarations to point here
+                        auto fwds = forwardStructs.equal_range( structDecl->name );
+                        if ( fwds.first != fwds.second ) {
+                                auto inst = fwds.first;
+                                do {
+                                        // forward decl is stored * mutably * in map, can thus be updated
+                                        inst->second->base = structDecl;
+                                } while ( ++inst != fwds.second );
+                                forwardStructs.erase( fwds.first, fwds.second );
+                        }
+                }
+
+                const ast::UnionDecl * previsit( const ast::UnionDecl * unionDecl ) {
+                        return renameGenericParams( unionDecl );
+                }
+
+                void postvisit( const ast::UnionDecl * unionDecl ) {
+                        // visit union members first so that the types of self-referencing members are updated
+                        // properly
+                        if ( ! unionDecl->body ) return;
+
+                        // update forward declarations to point here
+                        auto fwds = forwardUnions.equal_range( unionDecl->name );
+                        if ( fwds.first != fwds.second ) {
+                                auto inst = fwds.first;
+                                do {
+                                        // forward decl is stored * mutably * in map, can thus be updated
+                                        inst->second->base = unionDecl;
+                                } while ( ++inst != fwds.second );
+                                forwardUnions.erase( fwds.first, fwds.second );
+                        }
+                }
+
+                const ast::Decl * postvisit( const ast::TraitDecl * traitDecl ) {
+                        // set the "sized" status for the special "sized" trait
+                        if ( traitDecl->name == "sized" ) {
+                                assertf( traitDecl->params.size() == 1, "Built-in trait 'sized' has incorrect "
+                                        "number of parameters: %zd", traitDecl->params.size() );
+
+                                traitDecl = ast::mutate_field_index(
+                                        traitDecl, &ast::TraitDecl::params, 0,
+                                        ast::mutate_field(
+                                                traitDecl->params.front().get(), &ast::TypeDecl::sized, true ) );
+                        }
+
+                        // move assertions from type parameters into the body of the trait
+                        std::vector< ast::ptr< ast::DeclWithType > > added;
+                        for ( const ast::TypeDecl * td : traitDecl->params ) {
+                                for ( const ast::DeclWithType * assn : td->assertions ) {
+                                        auto inst = dynamic_cast< const ast::TraitInstType * >( assn->get_type() );
+                                        if ( inst ) {
+                                                expandAssertions( inst, added );
+                                        } else {
+                                                added.emplace_back( assn );
+                                        }
+                                }
+                        }
+                        if ( ! added.empty() ) {
+                                auto mut = mutate( traitDecl );
+                                for ( const ast::DeclWithType * decl : added ) {
+                                        mut->members.emplace_back( decl );
+                                }
+                                traitDecl = mut;
+                        }
+
+                        return traitDecl;
+                }
+        };
+
+        /// Replaces array and function types in forall lists by appropriate pointer type and assigns
+        /// each object and function declaration a unique ID
+        class ForallPointerDecay_new {
+                const CodeLocation & location;
+        public:
+                ForallPointerDecay_new( const CodeLocation & loc ) : location( loc ) {}
+
+                const ast::ObjectDecl * previsit( const ast::ObjectDecl * obj ) {
+                        // ensure that operator names only apply to functions or function pointers
+                        if (
+                                CodeGen::isOperator( obj->name )
+                                && ! dynamic_cast< const ast::FunctionType * >( obj->type->stripDeclarator() )
+                        ) {
+                                SemanticError( obj->location, toCString( "operator ", obj->name.c_str(), " is not "
+                                        "a function or function pointer." )  );
+                        }
+
+                        // ensure object has unique ID
+                        if ( obj->uniqueId ) return obj;
+                        auto mut = mutate( obj );
+                        mut->fixUniqueId();
+                        return mut;
+                }
+
+                const ast::FunctionDecl * previsit( const ast::FunctionDecl * func ) {
+                        // ensure function has unique ID
+                        if ( func->uniqueId ) return func;
+                        auto mut = mutate( func );
+                        mut->fixUniqueId();
+                        return mut;
+                }
+
+                /// Fix up assertions -- flattens assertion lists, removing all trait instances
+                template< typename node_t, typename parent_t >
+                static const node_t * forallFixer(
+                        const CodeLocation & loc, const node_t * node,
+                        ast::FunctionType::ForallList parent_t::* forallField
+                ) {
+                        for ( unsigned i = 0; i < (node->* forallField).size(); ++i ) {
+                                const ast::TypeDecl * type = (node->* forallField)[i];
+                                if ( type->assertions.empty() ) continue;
+
+                                std::vector< ast::ptr< ast::DeclWithType > > asserts;
+                                asserts.reserve( type->assertions.size() );
+
+                                // expand trait instances into their members
+                                for ( const ast::DeclWithType * assn : type->assertions ) {
+                                        auto traitInst =
+                                                dynamic_cast< const ast::TraitInstType * >( assn->get_type() );
+                                        if ( traitInst ) {
+                                                // expand trait instance to all its members
+                                                expandAssertions( traitInst, asserts );
+                                        } else {
+                                                // pass other assertions through
+                                                asserts.emplace_back( assn );
+                                        }
+                                }
+
+                                // apply FixFunction to every assertion to check for invalid void type
+                                for ( ast::ptr< ast::DeclWithType > & assn : asserts ) {
+                                        bool isVoid = false;
+                                        assn = fixFunction( assn, isVoid );
+                                        if ( isVoid ) {
+                                                SemanticError( loc, node, "invalid type void in assertion of function " );
+                                        }
+                                }
+
+                                // place mutated assertion list in node
+                                auto mut = mutate( type );
+                                mut->assertions = move( asserts );
+                                node = ast::mutate_field_index( node, forallField, i, mut );
+                        }
+                        return node;
+                }
+
+                const ast::FunctionType * previsit( const ast::FunctionType * ftype ) {
+                        return forallFixer( location, ftype, &ast::FunctionType::forall );
+                }
+
+                const ast::StructDecl * previsit( const ast::StructDecl * aggrDecl ) {
+                        return forallFixer( aggrDecl->location, aggrDecl, &ast::StructDecl::params );
+                }
+
+                const ast::UnionDecl * previsit( const ast::UnionDecl * aggrDecl ) {
+                        return forallFixer( aggrDecl->location, aggrDecl, &ast::UnionDecl::params );
+                }
+        };
+        */
+} // anonymous namespace
+
+/*
+const ast::Type * validateType(
+                const CodeLocation & loc, const ast::Type * type, const ast::SymbolTable & symtab ) {
+        // ast::Pass< EnumAndPointerDecay_new > epc;
+        ast::Pass< LinkReferenceToTypes_new > lrt{ loc, symtab };
+        ast::Pass< ForallPointerDecay_new > fpd{ loc };
+
+        return type->accept( lrt )->accept( fpd );
+}
+*/
+
 } // namespace SymTab