Changeset 2b4daf2 for src/ResolvExpr


Ignore:
Timestamp:
Jan 7, 2021, 5:06:22 PM (5 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
5ad381b
Parents:
42f6e07 (diff), 58fe85a (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:
src/ResolvExpr
Files:
18 edited

Legend:

Unmodified
Added
Removed

  • src/ResolvExpr/AdjustExprType.cc

    r42f6e07 r2b4daf2  
    133133                const ast::Type * postvisit( const ast::TypeInstType * inst ) {
    134134                        // replace known function-type-variables with pointer-to-function
    135                         if ( const ast::EqvClass * eqvClass = tenv.lookup( inst->name ) ) {
     135                        if ( const ast::EqvClass * eqvClass = tenv.lookup( *inst ) ) {
    136136                                if ( eqvClass->data.kind == ast::TypeDecl::Ftype ) {
    137137                                        return new ast::PointerType{ inst };

  • src/ResolvExpr/CandidateFinder.cpp

    r42f6e07 r2b4daf2  
    212212                // mark type variable and specialization cost of forall clause
    213213                convCost.incVar( function->forall.size() );
    214                 for ( const ast::TypeDecl * td : function->forall ) {
    215                         convCost.decSpec( td->assertions.size() );
    216                 }
     214                convCost.decSpec( function->assertions.size() );
    217215
    218216                return convCost;
    … …  
    223221                ast::AssertionSet & need
    224222        ) {
    225                 for ( const ast::TypeDecl * tyvar : type->forall ) {
    226                         unifiableVars[ tyvar->name ] = ast::TypeDecl::Data{ tyvar };
    227                         for ( const ast::DeclWithType * assn : tyvar->assertions ) {
    228                                 need[ assn ].isUsed = true;
    229                         }
     223                for ( auto & tyvar : type->forall ) {
     224                        unifiableVars[ *tyvar ] = ast::TypeDecl::Data{ tyvar->base };
     225                }
     226                for ( auto & assn : type->assertions ) {
     227                        need[ assn ].isUsed = true;
    230228                }
    231229        }
    … …  
    907905                        // xxx - is it possible that handleTupleAssignment and main finder both produce candidates?
    908906                        // this means there exists ctor/assign functions with a tuple as first parameter.
    909                         funcFinder.find( untypedExpr->func, selfFinder.candidates.empty() ? ResolvMode::withAdjustment() : ResolvMode::withoutFailFast() );
     907                        ResolvMode mode = {
     908                                true, // adjust
     909                                !untypedExpr->func.as<ast::NameExpr>(), // prune if not calling by name
     910                                selfFinder.candidates.empty() // failfast if other options are not found
     911                        };
     912                        funcFinder.find( untypedExpr->func, mode );
    910913                        // short-circuit if no candidates
    911914                        // if ( funcFinder.candidates.empty() ) return;
    … …  
    953956                                                auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult )
    954957                                        ) {
    955                                                 if ( const ast::EqvClass * clz = func->env.lookup( inst->name ) ) {
     958                                                if ( const ast::EqvClass * clz = func->env.lookup( *inst ) ) {
    956959                                                        if ( auto function = clz->bound.as< ast::FunctionType >() ) {
    957960                                                                CandidateRef newFunc{ new Candidate{ *func } };
    … …  
    10771080                        assert( toType );
    10781081                        toType = resolveTypeof( toType, symtab );
    1079                         toType = SymTab::validateType( castExpr->location, toType, symtab );
     1082                        // toType = SymTab::validateType( castExpr->location, toType, symtab );
    10801083                        toType = adjustExprType( toType, tenv, symtab );
    10811084
    … …  
    11621165
    11631166                                        if(auto insttype = dynamic_cast<const ast::TypeInstType*>(expr)) {
    1164                                                 auto td = cand->env.lookup(insttype->name);
     1167                                                auto td = cand->env.lookup(*insttype);
    11651168                                                if(!td) { continue; }
    11661169                                                expr = td->bound.get();
    … …  
    15681571                                // calculate target type
    15691572                                const ast::Type * toType = resolveTypeof( initAlt.type, symtab );
    1570                                 toType = SymTab::validateType( initExpr->location, toType, symtab );
     1573                                // toType = SymTab::validateType( initExpr->location, toType, symtab );
    15711574                                toType = adjustExprType( toType, tenv, symtab );
    15721575                                // The call to find must occur inside this loop, otherwise polymorphic return

  • src/ResolvExpr/CastCost.cc

    r42f6e07 r2b4daf2  
    202202) {
    203203        if ( auto typeInst = dynamic_cast< const ast::TypeInstType * >( dst ) ) {
    204                 if ( const ast::EqvClass * eqvClass = env.lookup( typeInst->name ) ) {
     204                if ( const ast::EqvClass * eqvClass = env.lookup( *typeInst ) ) {
    205205                        // check cast cost against bound type, if present
    206206                        if ( eqvClass->bound ) {

  • src/ResolvExpr/CommonType.cc

    r42f6e07 r2b4daf2  
    713713                        const ast::Type * base = oPtr->base;
    714714                        if ( auto var = dynamic_cast< const ast::TypeInstType * >( base ) ) {
    715                                 auto entry = open.find( var->name );
     715                                auto entry = open.find( *var );
    716716                                if ( entry != open.end() ) {
    717717                                        ast::AssertionSet need, have;

  • src/ResolvExpr/ConversionCost.cc

    r42f6e07 r2b4daf2  
    498498) {
    499499        if ( const ast::TypeInstType * inst = dynamic_cast< const ast::TypeInstType * >( dst ) ) {
    500                 if ( const ast::EqvClass * eqv = env.lookup( inst->name ) ) {
     500                if ( const ast::EqvClass * eqv = env.lookup( *inst ) ) {
    501501                        if ( eqv->bound ) {
    502502                                return conversionCost(src, eqv->bound, srcIsLvalue, symtab, env );
    … …  
    675675
    676676void ConversionCost_new::postvisit( const ast::TypeInstType * typeInstType ) {
    677         if ( const ast::EqvClass * eqv = env.lookup( typeInstType->name ) ) {
     677        if ( const ast::EqvClass * eqv = env.lookup( *typeInstType ) ) {
    678678                cost = costCalc( eqv->bound, dst, srcIsLvalue, symtab, env );
    679679        } else if ( const ast::TypeInstType * dstAsInst =
    680680                        dynamic_cast< const ast::TypeInstType * >( dst ) ) {
    681                 if ( typeInstType->name == dstAsInst->name ) {
     681                if ( *typeInstType == *dstAsInst ) {
    682682                        cost = Cost::zero;
    683683                }

  • src/ResolvExpr/FindOpenVars.cc

    r42f6e07 r2b4daf2  
    112112                                // mark open/closed variables
    113113                                if ( nextIsOpen ) {
    114                                         for ( const ast::TypeDecl * decl : type->forall ) {
    115                                                 open[ decl->name ] = ast::TypeDecl::Data{ decl };
    116                                                 for ( const ast::DeclWithType * assert : decl->assertions ) {
    117                                                         need[ assert ].isUsed = false;
    118                                                 }
     114                                        for ( auto & decl : type->forall ) {
     115                                                open[ *decl ] = ast::TypeDecl::Data{ decl->base };
     116                                        }
     117                                        for ( auto & assert : type->assertions ) {
     118                                                need[ assert ].isUsed = false;
    119119                                        }
    120120                                } else {
    121                                         for ( const ast::TypeDecl * decl : type->forall ) {
    122                                                 closed[ decl->name ] = ast::TypeDecl::Data{ decl };
    123                                                 for ( const ast::DeclWithType * assert : decl->assertions ) {
    124                                                         have[ assert ].isUsed = false;
    125                                                 }
     121                                        for ( auto & decl : type->forall ) {
     122                                                closed[ *decl ] = ast::TypeDecl::Data{ decl->base };   
     123                                        }
     124                                        for ( auto & assert : type->assertions ) {
     125                                                have[ assert ].isUsed = false;
    126126                                        }
    127127                                }

  • src/ResolvExpr/PolyCost.cc

    r42f6e07 r2b4daf2  
    6868
    6969        void previsit( const ast::TypeInstType * type ) {
    70                 if ( const ast::EqvClass * eqv = env_.lookup( type->name ) ) /* && */ if ( eqv->bound ) {
     70                if ( const ast::EqvClass * eqv = env_.lookup( *type ) ) /* && */ if ( eqv->bound ) {
    7171                        if ( const ast::TypeInstType * otherType = eqv->bound.as< ast::TypeInstType >() ) {
    7272                                if ( symtab.lookupType( otherType->name ) ) {

  • src/ResolvExpr/PtrsAssignable.cc

    r42f6e07 r2b4daf2  
    134134        }
    135135        void postvisit( const ast::TypeInstType * inst ) {
    136                 if ( const ast::EqvClass * eqv = typeEnv.lookup( inst->name ) ) {
     136                if ( const ast::EqvClass * eqv = typeEnv.lookup( *inst ) ) {
    137137                        if ( eqv->bound ) {
    138138                                // T * = S * for any S depends on the type bound to T
    … …  
    146146                const ast::TypeEnvironment & env ) {
    147147        if ( const ast::TypeInstType * dstAsInst = dynamic_cast< const ast::TypeInstType * >( dst ) ) {
    148                 if ( const ast::EqvClass * eqv = env.lookup( dstAsInst->name ) ) {
     148                if ( const ast::EqvClass * eqv = env.lookup( *dstAsInst ) ) {
    149149                        return ptrsAssignable( src, eqv->bound, env );
    150150                }

  • src/ResolvExpr/PtrsCastable.cc

    r42f6e07 r2b4daf2  
    180180                                        }
    181181                                }
    182                         } else if ( const ast::EqvClass * eqvClass = env.lookup( inst->name ) ) {
     182                        } else if ( const ast::EqvClass * eqvClass = env.lookup( *inst ) ) {
    183183                                if ( eqvClass->data.kind == ast::TypeDecl::Ftype ) {
    184184                                        return -1;
    … …  
    283283) {
    284284        if ( auto inst = dynamic_cast< const ast::TypeInstType * >( dst ) ) {
    285                 if ( const ast::EqvClass * eqvClass = env.lookup( inst->name ) ) {
     285                if ( const ast::EqvClass * eqvClass = env.lookup( *inst ) ) {
    286286                        return ptrsAssignable( src, eqvClass->bound, env );
    287287                }

  • src/ResolvExpr/RenameVars.cc

    r42f6e07 r2b4daf2  
    1919#include <utility>                 // for pair
    2020
    21 #include "AST/ForallSubstitutionTable.hpp"
    2221#include "AST/Pass.hpp"
    2322#include "AST/Type.hpp"
    … …  
    3938                int level = 0;
    4039                int resetCount = 0;
     40
     41                int next_expr_id = 1;
     42                int next_usage_id = 1;
    4143                ScopedMap< std::string, std::string > nameMap;
     44                ScopedMap< std::string, ast::TypeInstType::TypeEnvKey > idMap;
    4245        public:
    43                 ast::ForallSubstitutionTable subs;
    44 
    4546                void reset() {
    4647                        level = 0;
    … …  
    5354                                type->name = it->second;
    5455                        }
     56                }
     57
     58                void nextUsage() {
     59                        ++next_usage_id;
    5560                }
    5661
    … …  
    7883
    7984                const ast::TypeInstType * rename( const ast::TypeInstType * type ) {
    80                         // re-linking of base type handled by WithForallSubstitutor
    81 
    8285                        // rename
    83                         auto it = nameMap.find( type->name );
    84                         if ( it != nameMap.end() ) {
    85                                 // unconditionally mutate because map will *always* have different name,
    86                                 // if this mutates, will *always* have been mutated by ForallSubstitutor above
    87                                 ast::TypeInstType * mut = ast::mutate( type );
    88                                 mut->name = it->second;
     86                        auto it = idMap.find( type->name );
     87                        if ( it != idMap.end() ) {
     88                                // unconditionally mutate because map will *always* have different name
     89                                ast::TypeInstType * mut = ast::shallowCopy( type );
     90                                // reconcile base node since some copies might have been made
     91                                mut->base = it->second.base;
     92                                mut->formal_usage = it->second.formal_usage;
     93                                mut->expr_id = it->second.expr_id;
    8994                    type = mut;
    9095                        }
    … …  
    9398                }
    9499
    95                 const ast::FunctionType * openLevel( const ast::FunctionType * type ) {
     100                const ast::FunctionType * openLevel( const ast::FunctionType * type, RenameMode mode ) {
    96101                        if ( type->forall.empty() ) return type;
    97 
    98                         nameMap.beginScope();
     102                        idMap.beginScope();
    99103
    100104                        // Load new names from this forall clause and perform renaming.
    101                         auto mutType = ast::mutate( type );
    102                         assert( type == mutType && "mutated type must be unique from ForallSubstitutor" );
    103                         for ( ast::ptr< ast::TypeDecl > & td : mutType->forall ) {
    104                                 assertf(dynamic_cast<ast::FunctionType *>(mutType), "renaming vars in non-function type");
    105                                 std::ostringstream output;
    106                                 output << "_" << resetCount << "_" << level << "_" << td->name;
    107                                 std::string newname =  output.str();
    108                                 nameMap[ td->name ] = newname;
    109                                 ++level;
    110 
    111                                 ast::TypeDecl * mutDecl = ast::mutate( td.get() );
    112                                 assert( td == mutDecl && "mutated decl must be unique from ForallSubstitutor" );
    113                                 mutDecl->name = newname;
    114                                 // assertion above means `td = mutDecl;` is unnecessary
    115                         }
    116                         // assertion above means `type = mutType;` is unnecessary
    117 
    118                         return type;
     105                        auto mutType = ast::shallowCopy( type );
     106                        // assert( type == mutType && "mutated type must be unique from ForallSubstitutor" );
     107                        for ( auto & td : mutType->forall ) {
     108                                auto mut = ast::shallowCopy( td.get() );
     109                                // assert( td == mutDecl && "mutated decl must be unique from ForallSubstitutor" );
     110
     111                                if (mode == GEN_EXPR_ID) {
     112                                        mut->expr_id = next_expr_id;
     113                                        mut->formal_usage = -1;
     114                                        ++next_expr_id;
     115                                }
     116                                else if (mode == GEN_USAGE) {
     117                                        assertf(mut->expr_id, "unfilled expression id in generating candidate type");
     118                                        mut->formal_usage = next_usage_id;
     119                                }
     120                                else {
     121                                        assert(false);
     122                                }
     123                                idMap[ td->name ] = ast::TypeInstType::TypeEnvKey(*mut);
     124                               
     125                                td = mut;
     126                        }
     127
     128                        return mutType;
    119129                }
    120130
    121131                void closeLevel( const ast::FunctionType * type ) {
    122132                        if ( type->forall.empty() ) return;
    123 
    124                         nameMap.endScope();
     133                        idMap.endScope();
    125134                }
    126135        };
    … …  
    142151        };
    143152
    144         struct RenameVars_new /*: public ast::WithForallSubstitutor*/ {
    145                 #warning when old RenameVars goes away, replace hack below with global pass inheriting from WithForallSubstitutor
    146                 ast::ForallSubstitutionTable & subs = renaming.subs;
     153        struct RenameVars_new : public ast::PureVisitor /*: public ast::WithForallSubstitutor*/ {
     154                RenameMode mode;
    147155
    148156                const ast::FunctionType * previsit( const ast::FunctionType * type ) {
    149                         return renaming.openLevel( type );
     157                        return renaming.openLevel( type, mode );
    150158                }
    151159
    … …  
    163171
    164172                const ast::TypeInstType * previsit( const ast::TypeInstType * type ) {
     173                        if (mode == GEN_USAGE && !type->formal_usage) return type; // do not rename an actual type
    165174                        return renaming.rename( type );
    166175                }
    … …  
    177186}
    178187
    179 const ast::Type * renameTyVars( const ast::Type * t ) {
    180         ast::Type *tc = ast::deepCopy(t);
     188const ast::Type * renameTyVars( const ast::Type * t, RenameMode mode, bool reset ) {
     189        // ast::Type *tc = ast::deepCopy(t);
    181190        ast::Pass<RenameVars_new> renamer;
    182 //      return t->accept( renamer );
    183         return tc->accept( renamer );
     191        renamer.core.mode = mode;
     192        if (mode == GEN_USAGE && reset) {
     193                renaming.nextUsage();
     194        }
     195        return t->accept( renamer );
    184196}
    185197
    186198void resetTyVarRenaming() {
    187199        renaming.reset();
     200        renaming.nextUsage();
    188201}
    189202

  • src/ResolvExpr/RenameVars.h

    r42f6e07 r2b4daf2  
    3030        /// Provides a consistent renaming of forall type names in a hierarchy by prefixing them with a unique "level" ID
    3131        void renameTyVars( Type * );
    32         const ast::Type * renameTyVars( const ast::Type * );
     32
     33        enum RenameMode {
     34                GEN_USAGE, // for type in VariableExpr
     35                GEN_EXPR_ID // for type in decl
     36        };
     37        const ast::Type * renameTyVars( const ast::Type *, RenameMode mode = GEN_USAGE, bool reset = true );
     38       
    3339
    3440        /// resets internal state of renamer to avoid overflow
    3541        void resetTyVarRenaming();
     42
     43       
    3644} // namespace ResolvExpr
    3745

  • src/ResolvExpr/ResolvMode.h

    r42f6e07 r2b4daf2  
    2323                const bool failFast;         ///< Fail on no resulting alternatives? [true]
    2424
    25         private:
    2625                constexpr ResolvMode(bool a, bool p, bool ff)
    2726                : adjust(a), prune(p), failFast(ff) {}
    2827
    29         public:
    3028                /// Default settings
    3129                constexpr ResolvMode() : adjust(false), prune(true), failFast(true) {}

  • src/ResolvExpr/ResolveAssertions.cc

    r42f6e07 r2b4daf2  
    397397
    398398        /// Limit to depth of recursion of assertion satisfaction
    399         static const int recursionLimit = 4;
     399        static const int recursionLimit = 7;
    400400        /// Maximum number of simultaneously-deferred assertions to attempt concurrent satisfaction of
    401401        static const int deferLimit = 10;

  • src/ResolvExpr/ResolveTypeof.cc

    r42f6e07 r2b4daf2  
    1515
    1616#include "ResolveTypeof.h"
     17#include "RenameVars.h"
    1718
    1819#include <cassert>               // for assert
    … …  
    218219                        mutDecl->mangleName = Mangle::mangle(mutDecl); // do not mangle unnamed variables
    219220               
     221                mutDecl->type = renameTyVars(mutDecl->type, RenameMode::GEN_EXPR_ID);
    220222                mutDecl->isTypeFixed = true;
    221223                return mutDecl;

  • src/ResolvExpr/Resolver.cc

    r42f6e07 r2b4daf2  
    986986                };
    987987        } // anonymous namespace
    988 
    989988        /// Check if this expression is or includes a deleted expression
    990989        const ast::DeletedExpr * findDeletedExpr( const ast::Expr * expr ) {
    … …  
    11521151                        const ast::Expr * untyped, const ast::SymbolTable & symtab
    11531152                ) {
    1154                         resetTyVarRenaming();
    11551153                        ast::TypeEnvironment env;
    11561154                        ast::ptr< ast::Expr > newExpr = resolveInVoidContext( untyped, symtab, env );
    … …  
    13121310        }
    13131311
    1314         ast::ptr< ast::Expr > resolveStmtExpr(
     1312        const ast::Expr * resolveStmtExpr(
    13151313                const ast::StmtExpr * stmtExpr, const ast::SymbolTable & symtab
    13161314        ) {
    13171315                assert( stmtExpr );
    13181316                ast::Pass< Resolver_new > resolver{ symtab };
    1319                 ast::ptr< ast::Expr > ret = stmtExpr;
    1320                 ret = ret->accept( resolver );
    1321                 strict_dynamic_cast< ast::StmtExpr * >( ret.get_and_mutate() )->computeResult();
     1317                auto ret = mutate(stmtExpr->accept(resolver));
     1318                strict_dynamic_cast< ast::StmtExpr * >( ret )->computeResult();
    13221319                return ret;
    13231320        }
    … …  
    13751372                        }
    13761373
    1377                         // handle assertions. (seems deep)
     1374                        // handle assertions
    13781375
    13791376                        symtab.enterScope();
    1380                         for (auto & typeParam : mutType->forall) {
    1381                                 auto mutParam = typeParam.get_and_mutate();
    1382                                 symtab.addType(mutParam);
    1383                                 for (auto & asst : mutParam->assertions) {
    1384                                         asst = fixObjectType(asst.strict_as<ast::ObjectDecl>(), symtab);
    1385                                         symtab.addId(asst);
    1386                                 }
    1387                                 typeParam = mutParam;
     1377                        mutType->forall.clear();
     1378                        mutType->assertions.clear();
     1379                        for (auto & typeParam : mutDecl->type_params) {
     1380                                symtab.addType(typeParam);
     1381                                mutType->forall.emplace_back(new ast::TypeInstType(typeParam->name, typeParam));
     1382                        }
     1383                        for (auto & asst : mutDecl->assertions) {
     1384                                asst = fixObjectType(asst.strict_as<ast::ObjectDecl>(), symtab);
     1385                                symtab.addId(asst);
     1386                                mutType->assertions.emplace_back(new ast::VariableExpr(functionDecl->location, asst));
    13881387                        }
    13891388
    … …  
    14071406                        mutType->returns = std::move(returnTypes);
    14081407
     1408                        auto renamedType = strict_dynamic_cast<const ast::FunctionType *>(renameTyVars(mutType, RenameMode::GEN_EXPR_ID));
     1409
    14091410                        std::list<ast::ptr<ast::Stmt>> newStmts;
    14101411                        resolveWithExprs (mutDecl->withExprs, newStmts);
    … …  
    14181419                        symtab.leaveScope();
    14191420
     1421                        mutDecl->type = renamedType;
    14201422                        mutDecl->mangleName = Mangle::mangle(mutDecl);
    14211423                        mutDecl->isTypeFixed = true;
    … …  
    15341536        const PtrType * handlePtrType( const PtrType * type, const ast::SymbolTable & symtab ) {
    15351537                if ( type->dimension ) {
    1536                         #warning should use new equivalent to Validate::SizeType rather than sizeType here
    1537                         ast::ptr< ast::Type > sizeType = new ast::BasicType{ ast::BasicType::LongUnsignedInt };
     1538                        ast::ptr< ast::Type > sizeType = ast::sizeType;
    15381539                        ast::mutate_field(
    15391540                                type, &PtrType::dimension,

  • src/ResolvExpr/Resolver.h

    r42f6e07 r2b4daf2  
    7272        ast::ptr< ast::Init > resolveCtorInit(
    7373                const ast::ConstructorInit * ctorInit, const ast::SymbolTable & symtab );
    74         /// Resolves a statement expression
    75         ast::ptr< ast::Expr > resolveStmtExpr(
     74        /// Resolves a statement expression 
     75        const ast::Expr * resolveStmtExpr(
    7676                const ast::StmtExpr * stmtExpr, const ast::SymbolTable & symtab );
    7777} // namespace ResolvExpr

  • src/ResolvExpr/SatisfyAssertions.cpp

    r42f6e07 r2b4daf2  
    5757                ast::UniqueId resnSlot;          ///< Slot for any recursive assertion IDs
    5858
    59                 AssnCandidate( 
    60                         const ast::SymbolTable::IdData c, const ast::Type * at, ast::TypeEnvironment && e, 
     59                AssnCandidate(
     60                        const ast::SymbolTable::IdData c, const ast::Type * at, ast::TypeEnvironment && e,
    6161                        ast::AssertionSet && h, ast::AssertionSet && n, ast::OpenVarSet && o, ast::UniqueId rs )
    62                 : cdata( c ), adjType( at ), env( std::move( e ) ), have( std::move( h ) ), 
     62                : cdata( c ), adjType( at ), env( std::move( e ) ), have( std::move( h ) ),
    6363                  need( std::move( n ) ), open( std::move( o ) ), resnSlot( rs ) {}
    6464        };
    … …  
    6969        /// Reference to a single deferred item
    7070        struct DeferRef {
    71                 const ast::DeclWithType * decl;
     71                const ast::VariableExpr * expr;
    7272                const ast::AssertionSetValue & info;
    7373                const AssnCandidate & match;
    7474        };
    75        
    76         /// Wrapper for the deferred items from a single assertion satisfaction. 
     75
     76        /// Wrapper for the deferred items from a single assertion satisfaction.
    7777        /// Acts like an indexed list of DeferRef
    7878        struct DeferItem {
    79                 const ast::DeclWithType * decl;
     79                const ast::VariableExpr * expr;
    8080                const ast::AssertionSetValue & info;
    8181                AssnCandidateList matches;
    8282
    83                 DeferItem( 
    84                         const ast::DeclWithType * d, const ast::AssertionSetValue & i, AssnCandidateList && ms )
    85                 : decl( d ), info( i ), matches( std::move( ms ) ) {}
     83                DeferItem(
     84                        const ast::VariableExpr * d, const ast::AssertionSetValue & i, AssnCandidateList && ms )
     85                : expr( d ), info( i ), matches( std::move( ms ) ) {}
    8686
    8787                bool empty() const { return matches.empty(); }
    … …  
    8989                AssnCandidateList::size_type size() const { return matches.size(); }
    9090
    91                 DeferRef operator[] ( unsigned i ) const { return { decl, info, matches[i] }; }
     91                DeferRef operator[] ( unsigned i ) const { return { expr, info, matches[i] }; }
    9292        };
    9393
    … …  
    117117                /// Initial satisfaction state for a candidate
    118118                SatState( CandidateRef & c, const ast::SymbolTable & syms )
    119                 : cand( c ), need(), newNeed(), deferred(), inferred(), costs{ Cost::zero }, 
     119                : cand( c ), need(), newNeed(), deferred(), inferred(), costs{ Cost::zero },
    120120                  symtab( syms ) { need.swap( c->need ); }
    121                
     121
    122122                /// Update satisfaction state for next step after previous state
    123123                SatState( SatState && o, IterateFlag )
    124                 : cand( std::move( o.cand ) ), need( o.newNeed.begin(), o.newNeed.end() ), newNeed(), 
    125                   deferred(), inferred( std::move( o.inferred ) ), costs( std::move( o.costs ) ), 
     124                : cand( std::move( o.cand ) ), need( o.newNeed.begin(), o.newNeed.end() ), newNeed(),
     125                  deferred(), inferred( std::move( o.inferred ) ), costs( std::move( o.costs ) ),
    126126                  symtab( o.symtab ) { costs.emplace_back( Cost::zero ); }
    127                
     127
    128128                /// Field-wise next step constructor
    129129                SatState(
    130                         CandidateRef && c, ast::AssertionSet && nn, InferCache && i, CostVec && cs, 
     130                        CandidateRef && c, ast::AssertionSet && nn, InferCache && i, CostVec && cs,
    131131                        ast::SymbolTable && syms )
    132                 : cand( std::move( c ) ), need( nn.begin(), nn.end() ), newNeed(), deferred(), 
     132                : cand( std::move( c ) ), need( nn.begin(), nn.end() ), newNeed(), deferred(),
    133133                  inferred( std::move( i ) ), costs( std::move( cs ) ), symtab( std::move( syms ) )
    134134                  { costs.emplace_back( Cost::zero ); }
    … …  
    138138        void addToSymbolTable( const ast::AssertionSet & have, ast::SymbolTable & symtab ) {
    139139                for ( auto & i : have ) {
    140                         if ( i.second.isUsed ) { symtab.addId( i.first ); }
     140                        if ( i.second.isUsed ) { symtab.addId( i.first->var ); }
    141141                }
    142142        }
    143143
    144144        /// Binds a single assertion, updating satisfaction state
    145         void bindAssertion( 
    146                 const ast::DeclWithType * decl, const ast::AssertionSetValue & info, CandidateRef & cand,
     145        void bindAssertion(
     146                const ast::VariableExpr * expr, const ast::AssertionSetValue & info, CandidateRef & cand,
    147147                AssnCandidate & match, InferCache & inferred
    148148        ) {
    149149                const ast::DeclWithType * candidate = match.cdata.id;
    150                 assertf( candidate->uniqueId, 
     150                assertf( candidate->uniqueId,
    151151                        "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() );
    152                
     152
    153153                ast::Expr * varExpr = match.cdata.combine( cand->expr->location, cand->cvtCost );
    154154                varExpr->result = match.adjType;
    … …  
    156156
    157157                // place newly-inferred assertion in proper location in cache
    158                 inferred[ info.resnSlot ][ decl->uniqueId ] = ast::ParamEntry{
    159                         candidate->uniqueId, candidate, match.adjType, decl->get_type(), varExpr };
     158                inferred[ info.resnSlot ][ expr->var->uniqueId ] = ast::ParamEntry{
     159                        candidate->uniqueId, candidate, match.adjType, expr->result, varExpr };
    160160        }
    161161
    … …  
    169169
    170170                std::vector<ast::SymbolTable::IdData> candidates;
    171                 auto kind = ast::SymbolTable::getSpecialFunctionKind(assn.first->name);
     171                auto kind = ast::SymbolTable::getSpecialFunctionKind(assn.first->var->name);
    172172                if (kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS) {
    173173                        // prefilter special decls by argument type, if already known
    174                         ast::ptr<ast::Type> thisArgType = strict_dynamic_cast<const ast::PointerType *>(assn.first->get_type())->base
     174                        ast::ptr<ast::Type> thisArgType = assn.first->result.strict_as<ast::PointerType>()->base
    175175                                .strict_as<ast::FunctionType>()->params[0]
    176176                                .strict_as<ast::ReferenceType>()->base;
    … …  
    184184                }
    185185                else {
    186                         candidates = sat.symtab.lookupId(assn.first->name);
     186                        candidates = sat.symtab.lookupId(assn.first->var->name);
    187187                }
    188188                for ( const ast::SymbolTable::IdData & cdata : candidates ) {
    … …  
    200200                        ast::TypeEnvironment newEnv{ sat.cand->env };
    201201                        ast::OpenVarSet newOpen{ sat.cand->open };
    202                         ast::ptr< ast::Type > toType = assn.first->get_type();
    203                         ast::ptr< ast::Type > adjType = 
    204                                 renameTyVars( adjustExprType( candidate->get_type(), newEnv, sat.symtab ) );
     202                        ast::ptr< ast::Type > toType = assn.first->result;
     203                        ast::ptr< ast::Type > adjType =
     204                                renameTyVars( adjustExprType( candidate->get_type(), newEnv, sat.symtab ), GEN_USAGE, false );
    205205
    206206                        // only keep candidates which unify
    … …  
    213213                                }
    214214
    215                                 matches.emplace_back( 
     215                                matches.emplace_back(
    216216                                        cdata, adjType, std::move( newEnv ), std::move( have ), std::move( newNeed ),
    217217                                        std::move( newOpen ), crntResnSlot );
    … …  
    287287        };
    288288
    289         /// Replace ResnSlots with InferParams and add alternative to output list, if it meets pruning 
     289        /// Replace ResnSlots with InferParams and add alternative to output list, if it meets pruning
    290290        /// threshold.
    291         void finalizeAssertions( 
    292                 CandidateRef & cand, InferCache & inferred, PruneMap & thresholds, CostVec && costs, 
    293                 CandidateList & out 
     291        void finalizeAssertions(
     292                CandidateRef & cand, InferCache & inferred, PruneMap & thresholds, CostVec && costs,
     293                CandidateList & out
    294294        ) {
    295295                // prune if cheaper alternative for same key has already been generated
    … …  
    308308        }
    309309
    310         /// Combo iterator that combines candidates into an output list, merging their environments. 
    311         /// Rejects an appended candidate if environments cannot be merged. See `Common/FilterCombos.h` 
     310        /// Combo iterator that combines candidates into an output list, merging their environments.
     311        /// Rejects an appended candidate if environments cannot be merged. See `Common/FilterCombos.h`
    312312        /// for description of "combo iterator".
    313313        class CandidateEnvMerger {
    … …  
    337337                                        // compute conversion cost from satisfying decl to assertion
    338338                                        cost += computeConversionCost(
    339                                                 assn.match.adjType, assn.decl->get_type(), false, symtab, env );
     339                                                assn.match.adjType, assn.expr->result, false, symtab, env );
    340340
    341341                                        // mark vars+specialization on function-type assertions
    … …  
    350350                                        cost.incVar( func->forall.size() );
    351351
    352                                         for ( const ast::TypeDecl * td : func->forall ) {
    353                                                 cost.decSpec( td->assertions.size() );
    354                                         }
     352                                        cost.decSpec( func->assertions.size() );
    355353                                }
    356354                        }
    … …  
    387385
    388386        /// Limit to depth of recursion of assertion satisfaction
    389         static const int recursionLimit = 4;
     387        static const int recursionLimit = 8;
    390388        /// Maximum number of simultaneously-deferred assertions to attempt concurrent satisfaction of
    391389        static const int deferLimit = 10;
    392390} // anonymous namespace
    393391
    394 void satisfyAssertions( 
    395         CandidateRef & cand, const ast::SymbolTable & symtab, CandidateList & out, 
     392void satisfyAssertions(
     393        CandidateRef & cand, const ast::SymbolTable & symtab, CandidateList & out,
    396394        std::vector<std::string> & errors
    397395) {
    … …  
    419417                        if ( it != thresholds.end() && it->second < sat.costs ) goto nextSat;
    420418
    421                         // make initial pass at matching assertions
    422                         for ( auto & assn : sat.need ) {
    423                                 // fail early if any assertion is not satisfiable
    424                                 if ( ! satisfyAssertion( assn, sat ) ) {
     419                        // should a limit be imposed? worst case here is O(n^2) but very unlikely to happen.
     420                        for (unsigned resetCount = 0; ; ++resetCount) {
     421                                ast::AssertionList next;
     422                                resetTyVarRenaming();
     423                                // make initial pass at matching assertions
     424                                for ( auto & assn : sat.need ) {
     425                                        // fail early if any assertion is not satisfiable
     426                                        if ( ! satisfyAssertion( assn, sat ) ) {
     427                                                next.emplace_back(assn);
     428                                                // goto nextSat;
     429                                        }
     430                                }
     431                                // success
     432                                if (next.empty()) break;
     433                                // fail if nothing resolves
     434                                else if (next.size() == sat.need.size()) {
    425435                                        Indenter tabs{ 3 };
    426436                                        std::ostringstream ss;
    … …  
    428438                                        print( ss, *sat.cand, ++tabs );
    429439                                        ss << (tabs-1) << "Could not satisfy assertion:\n";
    430                                         ast::print( ss, assn.first, tabs );
     440                                        ast::print( ss, next[0].first, tabs );
    431441
    432442                                        errors.emplace_back( ss.str() );
    433443                                        goto nextSat;
    434444                                }
     445                                sat.need = std::move(next);
    435446                        }
    436447
    … …  
    438449                                // either add successful match or push back next state
    439450                                if ( sat.newNeed.empty() ) {
    440                                         finalizeAssertions( 
     451                                        finalizeAssertions(
    441452                                                sat.cand, sat.inferred, thresholds, std::move( sat.costs ), out );
    442453                                } else {
    … …  
    451462                                ss << (tabs-1) << "Too many non-unique satisfying assignments for assertions:\n";
    452463                                for ( const auto & d : sat.deferred ) {
    453                                         ast::print( ss, d.decl, tabs );
     464                                        ast::print( ss, d.expr, tabs );
    454465                                }
    455466
    … …  
    460471                                std::vector< CandidateEnvMerger::OutType > compatible = filterCombos(
    461472                                        sat.deferred, CandidateEnvMerger{ sat.cand->env, sat.cand->open, sat.symtab } );
    462                                
     473
    463474                                // fail early if no mutually-compatible assertion satisfaction
    464475                                if ( compatible.empty() ) {
    … …  
    469480                                        ss << (tabs-1) << "No mutually-compatible satisfaction for assertions:\n";
    470481                                        for ( const auto& d : sat.deferred ) {
    471                                                 ast::print( ss, d.decl, tabs );
     482                                                ast::print( ss, d.expr, tabs );
    472483                                        }
    473484
    … …  
    483494                                        // set up next satisfaction state
    484495                                        CandidateRef nextCand = std::make_shared<Candidate>(
    485                                                 sat.cand->expr, std::move( compat.env ), std::move( compat.open ), 
     496                                                sat.cand->expr, std::move( compat.env ), std::move( compat.open ),
    486497                                                ast::AssertionSet{} /* need moved into satisfaction state */,
    487498                                                sat.cand->cost, sat.cand->cvtCost );
    … …  
    489500                                        ast::AssertionSet nextNewNeed{ sat.newNeed };
    490501                                        InferCache nextInferred{ sat.inferred };
    491                                        
     502
    492503                                        CostVec nextCosts{ sat.costs };
    493504                                        nextCosts.back() += compat.cost;
    494                                                                
     505
    495506                                        ast::SymbolTable nextSymtab{ sat.symtab };
    496507
    … …  
    501512                                                nextNewNeed.insert( match.need.begin(), match.need.end() );
    502513
    503                                                 bindAssertion( r.decl, r.info, nextCand, match, nextInferred );
     514                                                bindAssertion( r.expr, r.info, nextCand, match, nextInferred );
    504515                                        }
    505516
    506517                                        // either add successful match or push back next state
    507518                                        if ( nextNewNeed.empty() ) {
    508                                                 finalizeAssertions( 
     519                                                finalizeAssertions(
    509520                                                        nextCand, nextInferred, thresholds, std::move( nextCosts ), out );
    510521                                        } else {
    511                                                 nextSats.emplace_back( 
    512                                                         std::move( nextCand ), std::move( nextNewNeed ), 
    513                                                         std::move( nextInferred ), std::move( nextCosts ), 
     522                                                nextSats.emplace_back(
     523                                                        std::move( nextCand ), std::move( nextNewNeed ),
     524                                                        std::move( nextInferred ), std::move( nextCosts ),
    514525                                                        std::move( nextSymtab ) );
    515526                                        }
    … …  
    523534                nextSats.clear();
    524535        }
    525        
     536
    526537        // exceeded recursion limit if reaches here
    527538        if ( out.empty() ) {

  • src/ResolvExpr/Unify.cc

    r42f6e07 r2b4daf2  
    773773
    774774                        const ast::Type * postvisit( const ast::TypeInstType * typeInst ) {
    775                                 if ( const ast::EqvClass * clz = tenv.lookup( typeInst->name ) ) {
     775                                if ( const ast::EqvClass * clz = tenv.lookup( *typeInst ) ) {
    776776                                        // expand ttype parameter into its actual type
    777777                                        if ( clz->data.kind == ast::TypeDecl::Ttype && clz->bound ) {
    … …  
    811811                /// Creates a tuple type based on a list of DeclWithType
    812812                template< typename Iter >
    813                 static ast::ptr< ast::Type > tupleFromTypes( Iter crnt, Iter end ) {
     813                static const ast::Type * tupleFromTypes( Iter crnt, Iter end ) {
    814814                        std::vector< ast::ptr< ast::Type > > types;
    815815                        while ( crnt != end ) {
    … …  
    821821                        }
    822822
    823                         return { new ast::TupleType{ std::move(types) } };
     823                        return new ast::TupleType{ std::move(types) };
    824824                }
    825825
    … …  
    888888                }
    889889
    890                 static void markAssertionSet( ast::AssertionSet & assns, const ast::DeclWithType * assn ) {
     890                static void markAssertionSet( ast::AssertionSet & assns, const ast::VariableExpr * assn ) {
    891891                        auto i = assns.find( assn );
    892892                        if ( i != assns.end() ) {
    … …  
    900900                        const ast::FunctionType * type
    901901                ) {
    902                         for ( const auto & tyvar : type->forall ) {
    903                                 for ( const ast::DeclWithType * assert : tyvar->assertions ) {
    904                                         markAssertionSet( assn1, assert );
    905                                         markAssertionSet( assn2, assert );
    906                                 }
     902                        for ( auto & assert : type->assertions ) {
     903                                markAssertionSet( assn1, assert );
     904                                markAssertionSet( assn2, assert );
    907905                        }
    908906                }
    … …  
    10301028
    10311029                void postvisit( const ast::TypeInstType * typeInst ) {
    1032                         assert( open.find( typeInst->name ) == open.end() );
     1030                        assert( open.find( *typeInst ) == open.end() );
    10331031                        handleRefType( typeInst, type2 );
    10341032                }
    … …  
    10361034        private:
    10371035                /// Creates a tuple type based on a list of Type
    1038                 static ast::ptr< ast::Type > tupleFromTypes(
     1036                static const ast::Type * tupleFromTypes(
    10391037                        const std::vector< ast::ptr< ast::Type > > & tys
    10401038                ) {
    … …  
    11711169                auto var2 = dynamic_cast< const ast::TypeInstType * >( type2 );
    11721170                ast::OpenVarSet::const_iterator
    1173                         entry1 = var1 ? open.find( var1->name ) : open.end(),
    1174                         entry2 = var2 ? open.find( var2->name ) : open.end();
     1171                        entry1 = var1 ? open.find( *var1 ) : open.end(),
     1172                        entry2 = var2 ? open.find( *var2 ) : open.end();
    11751173                bool isopen1 = entry1 != open.end();
    11761174                bool isopen2 = entry2 != open.end();
Note: See TracChangeset for help on using the changeset viewer.