Changeset 13de4478


Ignore:
Timestamp:
Apr 23, 2024, 1:37:17 PM (10 days ago)
Author:
Andrew Beach <ajbeach@…>
Branches:
master
Children:
4a3eb1c
Parents:
15215f02
Message:

Updated files in ResolvExpr? to the new indentation style. It seems the remaining places have reason to break from the style.

Location:
src/ResolvExpr
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • src/ResolvExpr/CommonType.cc

    r15215f02 r13de4478  
    3535
    3636namespace ResolvExpr {
     37
     38namespace {
    3739
    3840        // GENERATED START, DO NOT EDIT
    … …  
    710712// size_t CommonType::traceId = Stats::Heap::new_stacktrace_id("CommonType");
    711713
    712 namespace {
    713         ast::ptr< ast::Type > handleReference(
    714                 const ast::ptr< ast::Type > & t1, const ast::ptr< ast::Type > & t2, WidenMode widen,
    715                 ast::TypeEnvironment & env,
    716                 const ast::OpenVarSet & open
    717         ) {
    718                 ast::ptr<ast::Type> common;
    719                 ast::AssertionSet have, need;
    720                 ast::OpenVarSet newOpen{ open };
    721 
    722                 // need unify to bind type variables
    723                 if ( unify( t1, t2, env, have, need, newOpen, common ) ) {
    724                         ast::CV::Qualifiers q1 = t1->qualifiers, q2 = t2->qualifiers;
     714ast::ptr< ast::Type > handleReference(
     715        const ast::ptr< ast::Type > & t1, const ast::ptr< ast::Type > & t2, WidenMode widen,
     716        ast::TypeEnvironment & env,
     717        const ast::OpenVarSet & open
     718) {
     719        ast::ptr<ast::Type> common;
     720        ast::AssertionSet have, need;
     721        ast::OpenVarSet newOpen( open );
     722
     723        // need unify to bind type variables
     724        if ( unify( t1, t2, env, have, need, newOpen, common ) ) {
     725                ast::CV::Qualifiers q1 = t1->qualifiers, q2 = t2->qualifiers;
     726                PRINT(
     727                        std::cerr << "unify success: " << widenFirst << " " << widenSecond << std::endl;
     728                )
     729                if ( ( widen.first || q2 <= q1 ) && ( widen.second || q1 <= q2 ) ) {
    725730                        PRINT(
    726                                 std::cerr << "unify success: " << widenFirst << " " << widenSecond << std::endl;
     731                                std::cerr << "widen okay" << std::endl;
    727732                        )
    728                         if ( ( widen.first || q2 <= q1 ) && ( widen.second || q1 <= q2 ) ) {
    729                                 PRINT(
    730                                         std::cerr << "widen okay" << std::endl;
    731                                 )
    732                                 add_qualifiers( common, q1 | q2 );
    733                                 return common;
    734                         }
    735                 }
    736 
    737                 PRINT(
    738                         std::cerr << "exact unify failed: " << t1 << " " << t2 << std::endl;
    739                 )
    740                 return { nullptr };
    741         }
     733                        add_qualifiers( common, q1 | q2 );
     734                        return common;
     735                }
     736        }
     737
     738        PRINT(
     739                std::cerr << "exact unify failed: " << t1 << " " << t2 << std::endl;
     740        )
     741        return { nullptr };
    742742}
     743
     744} // namespace
    743745
    744746ast::ptr< ast::Type > commonType(
    … …  
    781783        }
    782784        // otherwise both are reference types of the same depth and this is handled by the visitor
    783         ast::Pass<CommonType> visitor{ type2, widen, env, open, need, have };
    784         type1->accept( visitor );
    785         // ast::ptr< ast::Type > result = visitor.core.result;
    786 
    787         return visitor.core.result;
     785        return ast::Pass<CommonType>::read( type1.get(),
     786                type2, widen, env, open, need, have );
    788787}
    789788

  • src/ResolvExpr/ConversionCost.cc

    r15215f02 r13de4478  
    3131#define PRINT(x)
    3232#endif
     33
     34namespace {
    3335
    3436        // GENERATED START, DO NOT EDIT
    … …  
    152154        );
    153155
    154 namespace {
    155156        int localPtrsAssignable(const ast::Type * t1, const ast::Type * t2,
    156157                        const ast::SymbolTable &, const ast::TypeEnvironment & env ) {

  • src/ResolvExpr/RenameVars.cc

    r15215f02 r13de4478  
    3030
    3131namespace {
    32         class RenamingData {
    33                 int level = 0;
    34                 int resetCount = 0;
    3532
    36                 int next_expr_id = 1;
    37                 int next_usage_id = 1;
    38                 ScopedMap< std::string, std::string > nameMap;
    39                 ScopedMap< std::string, ast::TypeEnvKey > idMap;
    40         public:
    41                 void reset() {
    42                         level = 0;
    43                         ++resetCount;
     33class RenamingData {
     34        int level = 0;
     35        int resetCount = 0;
     36
     37        int next_expr_id = 1;
     38        int next_usage_id = 1;
     39        ScopedMap< std::string, std::string > nameMap;
     40        ScopedMap< std::string, ast::TypeEnvKey > idMap;
     41public:
     42        void reset() {
     43                level = 0;
     44                ++resetCount;
     45        }
     46
     47        void nextUsage() {
     48                ++next_usage_id;
     49        }
     50
     51        const ast::TypeInstType * rename( const ast::TypeInstType * type ) {
     52                auto it = idMap.find( type->name );
     53                if ( it == idMap.end() ) return type;
     54
     55                // Unconditionally mutate because map will *always* have different name.
     56                ast::TypeInstType * mut = ast::shallowCopy( type );
     57                // Reconcile base node since some copies might have been made.
     58                mut->base = it->second.base;
     59                mut->formal_usage = it->second.formal_usage;
     60                mut->expr_id = it->second.expr_id;
     61                return mut;
     62        }
     63
     64        const ast::FunctionType * openLevel( const ast::FunctionType * type, RenameMode mode ) {
     65                if ( type->forall.empty() ) return type;
     66                idMap.beginScope();
     67
     68                // Load new names from this forall clause and perform renaming.
     69                auto mutType = ast::shallowCopy( type );
     70                // assert( type == mutType && "mutated type must be unique from ForallSubstitutor" );
     71                for ( auto & td : mutType->forall ) {
     72                        auto mut = ast::shallowCopy( td.get() );
     73                        // assert( td == mutDecl && "mutated decl must be unique from ForallSubstitutor" );
     74
     75                        if ( mode == GEN_EXPR_ID ) {
     76                                mut->expr_id = next_expr_id;
     77                                mut->formal_usage = -1;
     78                                ++next_expr_id;
     79                        } else if ( mode == GEN_USAGE ) {
     80                                assertf( mut->expr_id, "unfilled expression id in generating candidate type" );
     81                                mut->formal_usage = next_usage_id;
     82                        } else {
     83                                assert(false);
     84                        }
     85                        idMap[ td->name ] = ast::TypeEnvKey( *mut );
     86
     87                        td = mut;
    4488                }
    4589
    46                 void nextUsage() {
    47                         ++next_usage_id;
    48                 }
     90                return mutType;
     91        }
    4992
    50                 const ast::TypeInstType * rename( const ast::TypeInstType * type ) {
    51                         auto it = idMap.find( type->name );
    52                         if ( it == idMap.end() ) return type;
     93        void closeLevel( const ast::FunctionType * type ) {
     94                if ( type->forall.empty() ) return;
     95                idMap.endScope();
     96        }
     97};
    5398
    54                         // Unconditionally mutate because map will *always* have different name.
    55                         ast::TypeInstType * mut = ast::shallowCopy( type );
    56                         // Reconcile base node since some copies might have been made.
    57                         mut->base = it->second.base;
    58                         mut->formal_usage = it->second.formal_usage;
    59                         mut->expr_id = it->second.expr_id;
    60                         return mut;
    61                 }
     99// Global State:
     100RenamingData renaming;
    62101
    63                 const ast::FunctionType * openLevel( const ast::FunctionType * type, RenameMode mode ) {
    64                         if ( type->forall.empty() ) return type;
    65                         idMap.beginScope();
     102struct RenameVars final : public ast::PureVisitor /*: public ast::WithForallSubstitutor*/ {
     103        RenameMode mode;
    66104
    67                         // Load new names from this forall clause and perform renaming.
    68                         auto mutType = ast::shallowCopy( type );
    69                         // assert( type == mutType && "mutated type must be unique from ForallSubstitutor" );
    70                         for ( auto & td : mutType->forall ) {
    71                                 auto mut = ast::shallowCopy( td.get() );
    72                                 // assert( td == mutDecl && "mutated decl must be unique from ForallSubstitutor" );
     105        const ast::FunctionType * previsit( const ast::FunctionType * type ) {
     106                return renaming.openLevel( type, mode );
     107        }
    73108
    74                                 if (mode == GEN_EXPR_ID) {
    75                                         mut->expr_id = next_expr_id;
    76                                         mut->formal_usage = -1;
    77                                         ++next_expr_id;
    78                                 }
    79                                 else if (mode == GEN_USAGE) {
    80                                         assertf(mut->expr_id, "unfilled expression id in generating candidate type");
    81                                         mut->formal_usage = next_usage_id;
    82                                 }
    83                                 else {
    84                                         assert(false);
    85                                 }
    86                                 idMap[ td->name ] = ast::TypeEnvKey( *mut );
     109        /*
     110        const ast::StructInstType * previsit( const ast::StructInstType * type ) {
     111                return renaming.openLevel( type );
     112        }
     113        const ast::UnionInstType * previsit( const ast::UnionInstType * type ) {
     114                return renaming.openLevel( type );
     115        }
     116        const ast::TraitInstType * previsit( const ast::TraitInstType * type ) {
     117                return renaming.openLevel( type );
     118        }
     119        */
    87120
    88                                 td = mut;
    89                         }
    90 
    91                         return mutType;
    92                 }
    93 
    94                 void closeLevel( const ast::FunctionType * type ) {
    95                         if ( type->forall.empty() ) return;
    96                         idMap.endScope();
    97                 }
    98         };
    99 
    100         // Global State:
    101         RenamingData renaming;
    102 
    103         struct RenameVars final : public ast::PureVisitor /*: public ast::WithForallSubstitutor*/ {
    104                 RenameMode mode;
    105 
    106                 const ast::FunctionType * previsit( const ast::FunctionType * type ) {
    107                         return renaming.openLevel( type, mode );
    108                 }
    109 
    110                 /*
    111                 const ast::StructInstType * previsit( const ast::StructInstType * type ) {
    112                         return renaming.openLevel( type );
    113                 }
    114                 const ast::UnionInstType * previsit( const ast::UnionInstType * type ) {
    115                         return renaming.openLevel( type );
    116                 }
    117                 const ast::TraitInstType * previsit( const ast::TraitInstType * type ) {
    118                         return renaming.openLevel( type );
    119                 }
    120                 */
    121 
    122                 const ast::TypeInstType * previsit( const ast::TypeInstType * type ) {
    123                         if (mode == GEN_USAGE && !type->formal_usage) return type; // do not rename an actual type
    124                         return renaming.rename( type );
    125                 }
    126                 void postvisit( const ast::FunctionType * type ) {
    127                         renaming.closeLevel( type );
    128                 }
    129         };
     121        const ast::TypeInstType * previsit( const ast::TypeInstType * type ) {
     122                // Do not rename an actual type.
     123                if ( mode == GEN_USAGE && !type->formal_usage ) return type;
     124                return renaming.rename( type );
     125        }
     126        void postvisit( const ast::FunctionType * type ) {
     127                renaming.closeLevel( type );
     128        }
     129};
    130130
    131131} // namespace

  • src/ResolvExpr/Unify.cc

    r15215f02 r13de4478  
    4747namespace ResolvExpr {
    4848
    49         bool typesCompatible(
    50                         const ast::Type * first, const ast::Type * second,
    51                         const ast::TypeEnvironment & env ) {
    52                 ast::TypeEnvironment newEnv;
    53                 ast::OpenVarSet open, closed;
    54                 ast::AssertionSet need, have;
    55 
    56                 ast::ptr<ast::Type> newFirst{ first }, newSecond{ second };
    57                 env.apply( newFirst );
    58                 env.apply( newSecond );
    59 
    60                 // findOpenVars( newFirst, open, closed, need, have, FirstClosed );
    61                 findOpenVars( newSecond, open, closed, need, have, newEnv, FirstOpen );
    62 
    63                 return unifyExact(newFirst, newSecond, newEnv, need, have, open, noWiden() );
    64         }
    65 
    66         bool typesCompatibleIgnoreQualifiers(
    67                         const ast::Type * first, const ast::Type * second,
    68                         const ast::TypeEnvironment & env ) {
    69                 ast::TypeEnvironment newEnv;
    70                 ast::OpenVarSet open;
    71                 ast::AssertionSet need, have;
    72 
    73                 ast::Type * newFirst  = shallowCopy( first  );
    74                 ast::Type * newSecond = shallowCopy( second );
    75 
    76                 newFirst ->qualifiers = {};
    77                 newSecond->qualifiers = {};
    78                 ast::ptr< ast::Type > t1_(newFirst );
    79                 ast::ptr< ast::Type > t2_(newSecond);
    80 
    81                 ast::ptr< ast::Type > subFirst = env.apply(newFirst).node;
    82                 ast::ptr< ast::Type > subSecond = env.apply(newSecond).node;
    83 
    84                 return unifyExact(
    85                         subFirst,
    86                         subSecond,
    87                         newEnv, need, have, open, noWiden() );
    88         }
    89 
    90         namespace {
    91                                 /// Replaces ttype variables with their bound types.
    92                 /// If this isn't done when satifying ttype assertions, then argument lists can have
    93                 /// different size and structure when they should be compatible.
    94                 struct TtypeExpander : public ast::WithShortCircuiting, public ast::PureVisitor {
    95                         ast::TypeEnvironment & tenv;
    96 
    97                         TtypeExpander( ast::TypeEnvironment & env ) : tenv( env ) {}
    98 
    99                         const ast::Type * postvisit( const ast::TypeInstType * typeInst ) {
    100                                 if ( const ast::EqvClass * clz = tenv.lookup( *typeInst ) ) {
    101                                         // expand ttype parameter into its actual type
    102                                         if ( clz->data.kind == ast::TypeDecl::Ttype && clz->bound ) {
    103                                                 return clz->bound;
    104                                         }
     49bool typesCompatible(
     50                const ast::Type * first, const ast::Type * second,
     51                const ast::TypeEnvironment & env ) {
     52        ast::TypeEnvironment newEnv;
     53        ast::OpenVarSet open, closed;
     54        ast::AssertionSet need, have;
     55
     56        ast::ptr<ast::Type> newFirst( first ), newSecond( second );
     57        env.apply( newFirst );
     58        env.apply( newSecond );
     59
     60        // findOpenVars( newFirst, open, closed, need, have, FirstClosed );
     61        findOpenVars( newSecond, open, closed, need, have, newEnv, FirstOpen );
     62
     63        return unifyExact(newFirst, newSecond, newEnv, need, have, open, noWiden() );
     64}
     65
     66bool typesCompatibleIgnoreQualifiers(
     67                const ast::Type * first, const ast::Type * second,
     68                const ast::TypeEnvironment & env ) {
     69        ast::TypeEnvironment newEnv;
     70        ast::OpenVarSet open;
     71        ast::AssertionSet need, have;
     72
     73        ast::Type * newFirst  = shallowCopy( first  );
     74        ast::Type * newSecond = shallowCopy( second );
     75
     76        newFirst ->qualifiers = {};
     77        newSecond->qualifiers = {};
     78        ast::ptr< ast::Type > t1_(newFirst );
     79        ast::ptr< ast::Type > t2_(newSecond);
     80
     81        ast::ptr< ast::Type > subFirst = env.apply(newFirst).node;
     82        ast::ptr< ast::Type > subSecond = env.apply(newSecond).node;
     83
     84        return unifyExact(
     85                subFirst,
     86                subSecond,
     87                newEnv, need, have, open, noWiden() );
     88}
     89
     90namespace {
     91        /// Replaces ttype variables with their bound types.
     92        /// If this isn't done when satifying ttype assertions, then argument lists can have
     93        /// different size and structure when they should be compatible.
     94        struct TtypeExpander : public ast::WithShortCircuiting, public ast::PureVisitor {
     95                ast::TypeEnvironment & tenv;
     96
     97                TtypeExpander( ast::TypeEnvironment & env ) : tenv( env ) {}
     98
     99                const ast::Type * postvisit( const ast::TypeInstType * typeInst ) {
     100                        if ( const ast::EqvClass * clz = tenv.lookup( *typeInst ) ) {
     101                                // expand ttype parameter into its actual type
     102                                if ( clz->data.kind == ast::TypeDecl::Ttype && clz->bound ) {
     103                                        return clz->bound;
    105104                                }
    106                                 return typeInst;
    107105                        }
    108                 };
    109         }
    110 
    111         std::vector< ast::ptr< ast::Type > > flattenList(
    112                 const std::vector< ast::ptr< ast::Type > > & src, ast::TypeEnvironment & env
     106                        return typeInst;
     107                }
     108        };
     109}
     110
     111std::vector< ast::ptr< ast::Type > > flattenList(
     112        const std::vector< ast::ptr< ast::Type > > & src, ast::TypeEnvironment & env
     113) {
     114        std::vector< ast::ptr< ast::Type > > dst;
     115        dst.reserve( src.size() );
     116        for ( const auto & d : src ) {
     117                ast::Pass<TtypeExpander> expander( env );
     118                // TtypeExpander pass is impure (may mutate nodes in place)
     119                // need to make nodes shared to prevent accidental mutation
     120                ast::ptr<ast::Type> dc = d->accept(expander);
     121                auto types = flatten( dc );
     122                for ( ast::ptr< ast::Type > & t : types ) {
     123                        // outermost const, volatile, _Atomic qualifiers in parameters should not play
     124                        // a role in the unification of function types, since they do not determine
     125                        // whether a function is callable.
     126                        // NOTE: **must** consider at least mutex qualifier, since functions can be
     127                        // overloaded on outermost mutex and a mutex function has different
     128                        // requirements than a non-mutex function
     129                        remove_qualifiers( t, ast::CV::Const | ast::CV::Volatile | ast::CV::Atomic );
     130                        dst.emplace_back( t );
     131                }
     132        }
     133        return dst;
     134}
     135
     136// Unification of Expressions
     137//
     138// Boolean outcome (obvious):  Are they basically spelled the same?
     139// Side effect of binding variables (subtle):  if `sizeof(int)` ===_expr `sizeof(T)` then `int` ===_ty `T`
     140//
     141// Context:  if `float[VAREXPR1]` ===_ty `float[VAREXPR2]` then `VAREXPR1` ===_expr `VAREXPR2`
     142// where the VAREXPR are meant as notational metavariables representing the fact that unification always
     143// sees distinct ast::VariableExpr objects at these positions
     144
     145static bool unify( const ast::Expr * e1, const ast::Expr * e2, ast::TypeEnvironment & env,
     146        ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
     147        WidenMode widen );
     148
     149class UnifyExpr final : public ast::WithShortCircuiting {
     150        const ast::Expr * e2;
     151        ast::TypeEnvironment & tenv;
     152        ast::AssertionSet & need;
     153        ast::AssertionSet & have;
     154        const ast::OpenVarSet & open;
     155        WidenMode widen;
     156public:
     157        bool result;
     158
     159private:
     160
     161        void tryMatchOnStaticValue( const ast::Expr * e1 ) {
     162                Evaluation r1 = eval(e1);
     163                Evaluation r2 = eval(e2);
     164
     165                if ( !r1.hasKnownValue ) return;
     166                if ( !r2.hasKnownValue ) return;
     167
     168                if ( r1.knownValue != r2.knownValue ) return;
     169
     170                visit_children = false;
     171                result = true;
     172        }
     173
     174public:
     175
     176        void previsit( const ast::Node * ) { assert(false); }
     177
     178        void previsit( const ast::Expr * e1 ) {
     179                tryMatchOnStaticValue( e1 );
     180                visit_children = false;
     181        }
     182
     183        void previsit( const ast::CastExpr * e1 ) {
     184                tryMatchOnStaticValue( e1 );
     185
     186                if ( result ) {
     187                        assert( visit_children == false );
     188                } else {
     189                        assert( visit_children == true );
     190                        visit_children = false;
     191
     192                        auto e2c = dynamic_cast< const ast::CastExpr * >( e2 );
     193                        if ( !e2c ) return;
     194
     195                        // inspect casts' target types
     196                        if ( !unifyExact(
     197                                e1->result, e2c->result, tenv, need, have, open, widen ) ) return;
     198
     199                        // inspect casts' inner expressions
     200                        result = unify( e1->arg, e2c->arg, tenv, need, have, open, widen );
     201                }
     202        }
     203
     204        void previsit( const ast::VariableExpr * e1 ) {
     205                tryMatchOnStaticValue( e1 );
     206
     207                if ( result ) {
     208                        assert( visit_children == false );
     209                } else {
     210                        assert( visit_children == true );
     211                        visit_children = false;
     212
     213                        auto e2v = dynamic_cast< const ast::VariableExpr * >( e2 );
     214                        if ( !e2v ) return;
     215
     216                        assert(e1->var);
     217                        assert(e2v->var);
     218
     219                        // conservative: variable exprs match if their declarations are represented by the same C++ AST object
     220                        result = (e1->var == e2v->var);
     221                }
     222        }
     223
     224        void previsit( const ast::SizeofExpr * e1 ) {
     225                tryMatchOnStaticValue( e1 );
     226
     227                if ( result ) {
     228                        assert( visit_children == false );
     229                } else {
     230                        assert( visit_children == true );
     231                        visit_children = false;
     232
     233                        auto e2so = dynamic_cast< const ast::SizeofExpr * >( e2 );
     234                        if ( !e2so ) return;
     235
     236                        assert((e1->type != nullptr) ^ (e1->expr != nullptr));
     237                        assert((e2so->type != nullptr) ^ (e2so->expr != nullptr));
     238                        if ( !(e1->type && e2so->type) ) return;
     239
     240                        // expression unification calls type unification (mutual recursion)
     241                        result = unifyExact( e1->type, e2so->type, tenv, need, have, open, widen );
     242                }
     243        }
     244
     245        UnifyExpr( const ast::Expr * e2, ast::TypeEnvironment & env, ast::AssertionSet & need,
     246                ast::AssertionSet & have, const ast::OpenVarSet & open, WidenMode widen )
     247        : e2( e2 ), tenv(env), need(need), have(have), open(open), widen(widen), result(false) {}
     248};
     249
     250static bool unify( const ast::Expr * e1, const ast::Expr * e2, ast::TypeEnvironment & env,
     251        ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
     252        WidenMode widen ) {
     253        assert( e1 && e2 );
     254        return ast::Pass<UnifyExpr>::read( e1, e2, env, need, have, open, widen );
     255}
     256
     257class Unify final : public ast::WithShortCircuiting {
     258        const ast::Type * type2;
     259        ast::TypeEnvironment & tenv;
     260        ast::AssertionSet & need;
     261        ast::AssertionSet & have;
     262        const ast::OpenVarSet & open;
     263        WidenMode widen;
     264public:
     265        static size_t traceId;
     266        bool result;
     267
     268        Unify(
     269                const ast::Type * type2, ast::TypeEnvironment & env, ast::AssertionSet & need,
     270                ast::AssertionSet & have, const ast::OpenVarSet & open, WidenMode widen )
     271        : type2(type2), tenv(env), need(need), have(have), open(open), widen(widen),
     272        result(false) {}
     273
     274        void previsit( const ast::Node * ) { visit_children = false; }
     275
     276        void postvisit( const ast::VoidType * vt) {
     277                result = dynamic_cast< const ast::VoidType * >( type2 )
     278                        || tryToUnifyWithEnumValue(vt, type2, tenv, need, have, open, noWiden());
     279                ;
     280        }
     281
     282        void postvisit( const ast::BasicType * basic ) {
     283                if ( auto basic2 = dynamic_cast< const ast::BasicType * >( type2 ) ) {
     284                        result = basic->kind == basic2->kind;
     285                }
     286                result = result || tryToUnifyWithEnumValue(basic, type2, tenv, need, have, open, noWiden());
     287        }
     288
     289        void postvisit( const ast::PointerType * pointer ) {
     290                if ( auto pointer2 = dynamic_cast< const ast::PointerType * >( type2 ) ) {
     291                        result = unifyExact(
     292                                pointer->base, pointer2->base, tenv, need, have, open,
     293                                noWiden());
     294                }
     295                result = result || tryToUnifyWithEnumValue(pointer, type2, tenv, need, have, open, noWiden());
     296        }
     297
     298        void postvisit( const ast::ArrayType * array ) {
     299                auto array2 = dynamic_cast< const ast::ArrayType * >( type2 );
     300                if ( !array2 ) return;
     301
     302                if ( array->isVarLen != array2->isVarLen ) return;
     303                if ( (array->dimension != nullptr) != (array2->dimension != nullptr) ) return;
     304
     305                if ( array->dimension ) {
     306                        assert( array2->dimension );
     307                        // type unification calls expression unification (mutual recursion)
     308                        if ( !unify(array->dimension, array2->dimension,
     309                                tenv, need, have, open, widen) ) return;
     310                }
     311
     312                result = unifyExact(
     313                        array->base, array2->base, tenv, need, have, open, noWiden())
     314                        || tryToUnifyWithEnumValue(array, type2, tenv, need, have, open, noWiden());
     315        }
     316
     317        void postvisit( const ast::ReferenceType * ref ) {
     318                if ( auto ref2 = dynamic_cast< const ast::ReferenceType * >( type2 ) ) {
     319                        result = unifyExact(
     320                                ref->base, ref2->base, tenv, need, have, open, noWiden());
     321                }
     322        }
     323
     324private:
     325
     326        template< typename Iter >
     327        static bool unifyTypeList(
     328                Iter crnt1, Iter end1, Iter crnt2, Iter end2, ast::TypeEnvironment & env,
     329                ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open
    113330        ) {
    114                 std::vector< ast::ptr< ast::Type > > dst;
    115                 dst.reserve( src.size() );
    116                 for ( const auto & d : src ) {
    117                         ast::Pass<TtypeExpander> expander{ env };
    118                         // TtypeExpander pass is impure (may mutate nodes in place)
    119                         // need to make nodes shared to prevent accidental mutation
    120                         ast::ptr<ast::Type> dc = d->accept(expander);
    121                         auto types = flatten( dc );
    122                         for ( ast::ptr< ast::Type > & t : types ) {
    123                                 // outermost const, volatile, _Atomic qualifiers in parameters should not play
    124                                 // a role in the unification of function types, since they do not determine
    125                                 // whether a function is callable.
    126                                 // NOTE: **must** consider at least mutex qualifier, since functions can be
    127                                 // overloaded on outermost mutex and a mutex function has different
    128                                 // requirements than a non-mutex function
    129                                 remove_qualifiers( t, ast::CV::Const | ast::CV::Volatile | ast::CV::Atomic );
    130                                 dst.emplace_back( t );
    131                         }
    132                 }
    133                 return dst;
    134         }
    135 
    136         // Unification of Expressions
    137         //
    138         // Boolean outcome (obvious):  Are they basically spelled the same?
    139         // Side effect of binding variables (subtle):  if `sizeof(int)` ===_expr `sizeof(T)` then `int` ===_ty `T`
    140         //
    141         // Context:  if `float[VAREXPR1]` ===_ty `float[VAREXPR2]` then `VAREXPR1` ===_expr `VAREXPR2`
    142         // where the VAREXPR are meant as notational metavariables representing the fact that unification always
    143         // sees distinct ast::VariableExpr objects at these positions
    144 
    145         static bool unify( const ast::Expr * e1, const ast::Expr * e2, ast::TypeEnvironment & env,
    146                 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
    147                 WidenMode widen );
    148 
    149         class UnifyExpr final : public ast::WithShortCircuiting {
    150                 const ast::Expr * e2;
    151                 ast::TypeEnvironment & tenv;
    152                 ast::AssertionSet & need;
    153                 ast::AssertionSet & have;
    154                 const ast::OpenVarSet & open;
    155                 WidenMode widen;
    156         public:
    157                 bool result;
    158 
    159         private:
    160 
    161                 void tryMatchOnStaticValue( const ast::Expr * e1 ) {
    162                         Evaluation r1 = eval(e1);
    163                         Evaluation r2 = eval(e2);
    164 
    165                         if ( ! r1.hasKnownValue ) return;
    166                         if ( ! r2.hasKnownValue ) return;
    167 
    168                         if (r1.knownValue != r2.knownValue) return;
    169 
    170                         visit_children = false;
    171                         result = true;
    172                 }
    173 
    174         public:
    175 
    176                 void previsit( const ast::Node * ) { assert(false); }
    177 
    178                 void previsit( const ast::Expr * e1 ) {
    179                         tryMatchOnStaticValue( e1 );
    180                         visit_children = false;
    181                 }
    182 
    183                 void previsit( const ast::CastExpr * e1 ) {
    184                         tryMatchOnStaticValue( e1 );
    185 
    186                         if (result) {
    187                                 assert (visit_children == false);
    188                         } else {
    189                                 assert (visit_children == true);
    190                                 visit_children = false;
    191 
    192                                 auto e2c = dynamic_cast< const ast::CastExpr * >( e2 );
    193                                 if ( ! e2c ) return;
    194 
    195                                 // inspect casts' target types
    196                                 if ( ! unifyExact(
    197                                         e1->result, e2c->result, tenv, need, have, open, widen ) ) return;
    198 
    199                                 // inspect casts' inner expressions
    200                                 result = unify( e1->arg, e2c->arg, tenv, need, have, open, widen );
    201                         }
    202                 }
    203 
    204                 void previsit( const ast::VariableExpr * e1 ) {
    205                         tryMatchOnStaticValue( e1 );
    206 
    207                         if (result) {
    208                                 assert (visit_children == false);
    209                         } else {
    210                                 assert (visit_children == true);
    211                                 visit_children = false;
    212 
    213                                 auto e2v = dynamic_cast< const ast::VariableExpr * >( e2 );
    214                                 if ( ! e2v ) return;
    215 
    216                                 assert(e1->var);
    217                                 assert(e2v->var);
    218 
    219                                 // conservative: variable exprs match if their declarations are represented by the same C++ AST object
    220                                 result = (e1->var == e2v->var);
    221                         }
    222                 }
    223 
    224                 void previsit( const ast::SizeofExpr * e1 ) {
    225                         tryMatchOnStaticValue( e1 );
    226 
    227                         if (result) {
    228                                 assert (visit_children == false);
    229                         } else {
    230                                 assert (visit_children == true);
    231                                 visit_children = false;
    232 
    233                                 auto e2so = dynamic_cast< const ast::SizeofExpr * >( e2 );
    234                                 if ( ! e2so ) return;
    235 
    236                                 assert((e1->type != nullptr) ^ (e1->expr != nullptr));
    237                                 assert((e2so->type != nullptr) ^ (e2so->expr != nullptr));
    238                                 if ( ! (e1->type && e2so->type) )  return;
    239 
    240                                 // expression unification calls type unification (mutual recursion)
    241                                 result = unifyExact( e1->type, e2so->type, tenv, need, have, open, widen );
    242                         }
    243                 }
    244 
    245                 UnifyExpr( const ast::Expr * e2, ast::TypeEnvironment & env, ast::AssertionSet & need,
    246                         ast::AssertionSet & have, const ast::OpenVarSet & open, WidenMode widen )
    247                 : e2( e2 ), tenv(env), need(need), have(have), open(open), widen(widen), result(false) {}
    248         };
    249 
    250         static bool unify( const ast::Expr * e1, const ast::Expr * e2, ast::TypeEnvironment & env,
    251                 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
    252                 WidenMode widen ) {
    253                 assert( e1 && e2 );
    254                 return ast::Pass<UnifyExpr>::read( e1, e2, env, need, have, open, widen );
    255         }
    256 
    257         class Unify final : public ast::WithShortCircuiting {
    258                 const ast::Type * type2;
    259                 ast::TypeEnvironment & tenv;
    260                 ast::AssertionSet & need;
    261                 ast::AssertionSet & have;
    262                 const ast::OpenVarSet & open;
    263                 WidenMode widen;
    264         public:
    265                 static size_t traceId;
    266                 bool result;
    267 
    268                 Unify(
    269                         const ast::Type * type2, ast::TypeEnvironment & env, ast::AssertionSet & need,
    270                         ast::AssertionSet & have, const ast::OpenVarSet & open, WidenMode widen )
    271                 : type2(type2), tenv(env), need(need), have(have), open(open), widen(widen),
    272                 result(false) {}
    273 
    274                 void previsit( const ast::Node * ) { visit_children = false; }
    275 
    276                 void postvisit( const ast::VoidType * vt) {
    277                         result = dynamic_cast< const ast::VoidType * >( type2 )
    278                                 || tryToUnifyWithEnumValue(vt, type2, tenv, need, have, open, noWiden());
    279                         ;
    280                 }
    281 
    282                 void postvisit( const ast::BasicType * basic ) {
    283                         if ( auto basic2 = dynamic_cast< const ast::BasicType * >( type2 ) ) {
    284                                 result = basic->kind == basic2->kind;
    285                         }
    286                         result = result || tryToUnifyWithEnumValue(basic, type2, tenv, need, have, open, noWiden());
    287                 }
    288 
    289                 void postvisit( const ast::PointerType * pointer ) {
    290                         if ( auto pointer2 = dynamic_cast< const ast::PointerType * >( type2 ) ) {
    291                                 result = unifyExact(
    292                                         pointer->base, pointer2->base, tenv, need, have, open,
    293                                         noWiden());
    294                         }
    295                         result = result || tryToUnifyWithEnumValue(pointer, type2, tenv, need, have, open, noWiden());
    296                 }
    297 
    298                 void postvisit( const ast::ArrayType * array ) {
    299                         auto array2 = dynamic_cast< const ast::ArrayType * >( type2 );
    300                         if ( ! array2 ) return;
    301 
    302                         if ( array->isVarLen != array2->isVarLen ) return;
    303                         if ( (array->dimension != nullptr) != (array2->dimension != nullptr) ) return;
    304 
    305                         if ( array->dimension ) {
    306                                 assert( array2->dimension );
    307                                 // type unification calls expression unification (mutual recursion)
    308                                 if ( ! unify(array->dimension, array2->dimension,
    309                                         tenv, need, have, open, widen) ) return;
    310                         }
    311 
    312                         result = unifyExact(
    313                                 array->base, array2->base, tenv, need, have, open, noWiden())
    314                                 || tryToUnifyWithEnumValue(array, type2, tenv, need, have, open, noWiden());
    315                 }
    316 
    317                 void postvisit( const ast::ReferenceType * ref ) {
    318                         if ( auto ref2 = dynamic_cast< const ast::ReferenceType * >( type2 ) ) {
    319                                 result = unifyExact(
    320                                         ref->base, ref2->base, tenv, need, have, open, noWiden());
    321                         }
    322                 }
    323 
    324         private:
    325 
    326                 template< typename Iter >
    327                 static bool unifyTypeList(
    328                         Iter crnt1, Iter end1, Iter crnt2, Iter end2, ast::TypeEnvironment & env,
    329                         ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open
    330                 ) {
    331                         while ( crnt1 != end1 && crnt2 != end2 ) {
    332                                 const ast::Type * t1 = *crnt1;
    333                                 const ast::Type * t2 = *crnt2;
    334                                 bool isTuple1 = Tuples::isTtype( t1 );
    335                                 bool isTuple2 = Tuples::isTtype( t2 );
    336 
    337                                 // assumes here that ttype *must* be last parameter
    338                                 if ( isTuple1 && ! isTuple2 ) {
    339                                         // combine remainder of list2, then unify
    340                                         return unifyExact(
    341                                                 t1, tupleFromTypes( crnt2, end2 ), env, need, have, open,
    342                                                 noWiden() );
    343                                 } else if ( ! isTuple1 && isTuple2 ) {
    344                                         // combine remainder of list1, then unify
    345                                         return unifyExact(
    346                                                 tupleFromTypes( crnt1, end1 ), t2, env, need, have, open,
    347                                                 noWiden() );
    348                                 }
    349 
    350                                 if ( ! unifyExact(
    351                                         t1, t2, env, need, have, open, noWiden() )
    352                                 ) return false;
    353 
    354                                 ++crnt1; ++crnt2;
    355                         }
    356 
    357                         // May get to the end of one argument list before the other. This is only okay if the
    358                         // other is a ttype
    359                         if ( crnt1 != end1 ) {
    360                                 // try unifying empty tuple with ttype
    361                                 const ast::Type * t1 = *crnt1;
    362                                 if ( ! Tuples::isTtype( t1 ) ) return false;
     331                while ( crnt1 != end1 && crnt2 != end2 ) {
     332                        const ast::Type * t1 = *crnt1;
     333                        const ast::Type * t2 = *crnt2;
     334                        bool isTuple1 = Tuples::isTtype( t1 );
     335                        bool isTuple2 = Tuples::isTtype( t2 );
     336
     337                        // assumes here that ttype *must* be last parameter
     338                        if ( isTuple1 && !isTuple2 ) {
     339                                // combine remainder of list2, then unify
    363340                                return unifyExact(
    364341                                        t1, tupleFromTypes( crnt2, end2 ), env, need, have, open,
    365342                                        noWiden() );
    366                         } else if ( crnt2 != end2 ) {
    367                                 // try unifying empty tuple with ttype
    368                                 const ast::Type * t2 = *crnt2;
    369                                 if ( ! Tuples::isTtype( t2 ) ) return false;
     343                        } else if ( !isTuple1 && isTuple2 ) {
     344                                // combine remainder of list1, then unify
    370345                                return unifyExact(
    371346                                        tupleFromTypes( crnt1, end1 ), t2, env, need, have, open,
    … …  
    373348                        }
    374349
    375                         return true;
    376                 }
    377 
    378                 static bool unifyTypeList(
    379                         const std::vector< ast::ptr< ast::Type > > & list1,
    380                         const std::vector< ast::ptr< ast::Type > > & list2,
    381                         ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
    382                         const ast::OpenVarSet & open
    383                 ) {
    384                         return unifyTypeList(
    385                                 list1.begin(), list1.end(), list2.begin(), list2.end(), env, need, have, open);
    386                 }
    387 
    388                 static void markAssertionSet( ast::AssertionSet & assns, const ast::VariableExpr * assn ) {
    389                         auto i = assns.find( assn );
    390                         if ( i != assns.end() ) {
    391                                 i->second.isUsed = true;
     350                        if ( !unifyExact(
     351                                t1, t2, env, need, have, open, noWiden() )
     352                        ) return false;
     353
     354                        ++crnt1; ++crnt2;
     355                }
     356
     357                // May get to the end of one argument list before the other. This is only okay if the
     358                // other is a ttype
     359                if ( crnt1 != end1 ) {
     360                        // try unifying empty tuple with ttype
     361                        const ast::Type * t1 = *crnt1;
     362                        if ( !Tuples::isTtype( t1 ) ) return false;
     363                        return unifyExact(
     364                                t1, tupleFromTypes( crnt2, end2 ), env, need, have, open,
     365                                noWiden() );
     366                } else if ( crnt2 != end2 ) {
     367                        // try unifying empty tuple with ttype
     368                        const ast::Type * t2 = *crnt2;
     369                        if ( !Tuples::isTtype( t2 ) ) return false;
     370                        return unifyExact(
     371                                tupleFromTypes( crnt1, end1 ), t2, env, need, have, open,
     372                                noWiden() );
     373                }
     374
     375                return true;
     376        }
     377
     378        static bool unifyTypeList(
     379                const std::vector< ast::ptr< ast::Type > > & list1,
     380                const std::vector< ast::ptr< ast::Type > > & list2,
     381                ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
     382                const ast::OpenVarSet & open
     383        ) {
     384                return unifyTypeList(
     385                        list1.begin(), list1.end(), list2.begin(), list2.end(), env, need, have, open);
     386        }
     387
     388        static void markAssertionSet( ast::AssertionSet & assns, const ast::VariableExpr * assn ) {
     389                auto i = assns.find( assn );
     390                if ( i != assns.end() ) {
     391                        i->second.isUsed = true;
     392                }
     393        }
     394
     395        /// mark all assertions in `type` used in both `assn1` and `assn2`
     396        static void markAssertions(
     397                ast::AssertionSet & assn1, ast::AssertionSet & assn2,
     398                const ast::FunctionType * type
     399        ) {
     400                for ( auto & assert : type->assertions ) {
     401                        markAssertionSet( assn1, assert );
     402                        markAssertionSet( assn2, assert );
     403                }
     404        }
     405
     406        bool tryToUnifyWithEnumValue( const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env,
     407                ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
     408                WidenMode widen) {
     409                if ( auto attrType2 = dynamic_cast<const ast::EnumAttrType *>(type2)) {
     410                        if (attrType2->attr == ast::EnumAttribute::Value) {
     411                                return unifyExact( type1, attrType2->instance->base->base, env, need, have, open,
     412                                        widen);
     413                        } else if (attrType2->attr == ast::EnumAttribute::Posn) {
     414                                return unifyExact( type1, attrType2->instance, env, need, have, open, widen );
    392415                        }
    393416                }
    394 
    395                 /// mark all assertions in `type` used in both `assn1` and `assn2`
    396                 static void markAssertions(
    397                         ast::AssertionSet & assn1, ast::AssertionSet & assn2,
    398                         const ast::FunctionType * type
    399                 ) {
    400                         for ( auto & assert : type->assertions ) {
    401                                 markAssertionSet( assn1, assert );
    402                                 markAssertionSet( assn2, assert );
     417                return false;
     418        }
     419
     420public:
     421        void postvisit( const ast::FunctionType * func ) {
     422                auto func2 = dynamic_cast< const ast::FunctionType * >( type2 );
     423                if ( !func2 ) return;
     424
     425                if ( func->isVarArgs != func2->isVarArgs ) return;
     426
     427                // Flatten the parameter lists for both functions so that tuple structure does not
     428                // affect unification. Does not actually mutate function parameters.
     429                auto params = flattenList( func->params, tenv );
     430                auto params2 = flattenList( func2->params, tenv );
     431
     432                // sizes don't have to match if ttypes are involved; need to be more precise w.r.t.
     433                // where the ttype is to prevent errors
     434                if (
     435                        ( params.size() != params2.size() || func->returns.size() != func2->returns.size() )
     436                        && !func->isTtype()
     437                        && !func2->isTtype()
     438                ) return;
     439
     440                if ( !unifyTypeList( params, params2, tenv, need, have, open ) ) return;
     441                if ( !unifyTypeList(
     442                        func->returns, func2->returns, tenv, need, have, open ) ) return;
     443
     444                markAssertions( have, need, func );
     445                markAssertions( have, need, func2 );
     446
     447                result = true;
     448        }
     449
     450private:
     451        // Returns: other, cast as XInstType
     452        // Assigns this->result: whether types are compatible (up to generic parameters)
     453        template< typename XInstType >
     454        const XInstType * handleRefType( const XInstType * inst, const ast::Type * other ) {
     455                // check that the other type is compatible and named the same
     456                auto otherInst = dynamic_cast< const XInstType * >( other );
     457                if ( otherInst && inst->name == otherInst->name ) {
     458                        this->result = otherInst;
     459                }
     460                return otherInst;
     461        }
     462
     463        /// Creates a tuple type based on a list of TypeExpr
     464        template< typename Iter >
     465        static const ast::Type * tupleFromExprs(
     466                const ast::TypeExpr * param, Iter & crnt, Iter end, ast::CV::Qualifiers qs
     467        ) {
     468                std::vector< ast::ptr< ast::Type > > types;
     469                do {
     470                        types.emplace_back( param->type );
     471
     472                        ++crnt;
     473                        if ( crnt == end ) break;
     474                        param = strict_dynamic_cast< const ast::TypeExpr * >( crnt->get() );
     475                } while(true);
     476
     477                return new ast::TupleType( std::move(types), qs );
     478        }
     479
     480        template< typename XInstType >
     481        void handleGenericRefType( const XInstType * inst, const ast::Type * other ) {
     482                // check that other type is compatible and named the same
     483                const XInstType * otherInst = handleRefType( inst, other );
     484                if ( !this->result ) return;
     485
     486                // check that parameters of types unify, if any
     487                const std::vector< ast::ptr< ast::Expr > > & params = inst->params;
     488                const std::vector< ast::ptr< ast::Expr > > & params2 = otherInst->params;
     489
     490                auto it = params.begin();
     491                auto jt = params2.begin();
     492                for ( ; it != params.end() && jt != params2.end(); ++it, ++jt ) {
     493                        auto param = strict_dynamic_cast< const ast::TypeExpr * >( it->get() );
     494                        auto param2 = strict_dynamic_cast< const ast::TypeExpr * >( jt->get() );
     495
     496                        ast::ptr< ast::Type > pty = param->type;
     497                        ast::ptr< ast::Type > pty2 = param2->type;
     498
     499                        bool isTuple = Tuples::isTtype( pty );
     500                        bool isTuple2 = Tuples::isTtype( pty2 );
     501
     502                        if ( isTuple && isTuple2 ) {
     503                                ++it; ++jt;  // skip ttype parameters before break
     504                        } else if ( isTuple ) {
     505                                // bundle remaining params into tuple
     506                                pty2 = tupleFromExprs( param2, jt, params2.end(), pty->qualifiers );
     507                                ++it;  // skip ttype parameter for break
     508                        } else if ( isTuple2 ) {
     509                                // bundle remaining params into tuple
     510                                pty = tupleFromExprs( param, it, params.end(), pty2->qualifiers );
     511                                ++jt;  // skip ttype parameter for break
    403512                        }
    404                 }
    405 
    406                 bool tryToUnifyWithEnumValue( const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env,
    407                         ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
    408                         WidenMode widen) {
    409                         if ( auto attrType2 = dynamic_cast<const ast::EnumAttrType *>(type2)) {
    410                                 if (attrType2->attr == ast::EnumAttribute::Value) {
    411                                         return unifyExact( type1, attrType2->instance->base->base, env, need, have, open,
    412                                                 widen);
    413                                 } else if (attrType2->attr == ast::EnumAttribute::Posn) {
    414                                         return unifyExact( type1, attrType2->instance, env, need, have, open, widen );
    415                                 }
     513
     514                        if ( !unifyExact(
     515                                        pty, pty2, tenv, need, have, open, noWiden() ) ) {
     516                                result = false;
     517                                return;
    416518                        }
    417                         return false;
    418                 }
    419 
    420         public:
    421                 void postvisit( const ast::FunctionType * func ) {
    422                         auto func2 = dynamic_cast< const ast::FunctionType * >( type2 );
    423                         if ( ! func2 ) return;
    424 
    425                         if ( func->isVarArgs != func2->isVarArgs ) return;
    426 
    427                         // Flatten the parameter lists for both functions so that tuple structure does not
    428                         // affect unification. Does not actually mutate function parameters.
    429                         auto params = flattenList( func->params, tenv );
    430                         auto params2 = flattenList( func2->params, tenv );
    431 
    432                         // sizes don't have to match if ttypes are involved; need to be more precise w.r.t.
    433                         // where the ttype is to prevent errors
    434                         if (
    435                                 ( params.size() != params2.size() || func->returns.size() != func2->returns.size() )
    436                                 && ! func->isTtype()
    437                                 && ! func2->isTtype()
    438                         ) return;
    439 
    440                         if ( ! unifyTypeList( params, params2, tenv, need, have, open ) ) return;
    441                         if ( ! unifyTypeList(
    442                                 func->returns, func2->returns, tenv, need, have, open ) ) return;
    443 
    444                         markAssertions( have, need, func );
    445                         markAssertions( have, need, func2 );
    446 
    447                         result = true;
    448                 }
    449 
    450         private:
    451                 // Returns: other, cast as XInstType
    452                 // Assigns this->result: whether types are compatible (up to generic parameters)
    453                 template< typename XInstType >
    454                 const XInstType * handleRefType( const XInstType * inst, const ast::Type * other ) {
    455                         // check that the other type is compatible and named the same
    456                         auto otherInst = dynamic_cast< const XInstType * >( other );
    457                         if (otherInst && inst->name == otherInst->name)
    458                                 this->result = otherInst;
    459                         return otherInst;
    460                 }
    461 
    462                 /// Creates a tuple type based on a list of TypeExpr
    463                 template< typename Iter >
    464                 static const ast::Type * tupleFromExprs(
    465                         const ast::TypeExpr * param, Iter & crnt, Iter end, ast::CV::Qualifiers qs
    466                 ) {
    467                         std::vector< ast::ptr< ast::Type > > types;
    468                         do {
    469                                 types.emplace_back( param->type );
    470 
    471                                 ++crnt;
    472                                 if ( crnt == end ) break;
    473                                 param = strict_dynamic_cast< const ast::TypeExpr * >( crnt->get() );
    474                         } while(true);
    475 
    476                         return new ast::TupleType{ std::move(types), qs };
    477                 }
    478 
    479                 template< typename XInstType >
    480                 void handleGenericRefType( const XInstType * inst, const ast::Type * other ) {
    481                         // check that other type is compatible and named the same
    482                         const XInstType * otherInst = handleRefType( inst, other );
    483                         if ( ! this->result ) return;
    484 
    485                         // check that parameters of types unify, if any
    486                         const std::vector< ast::ptr< ast::Expr > > & params = inst->params;
    487                         const std::vector< ast::ptr< ast::Expr > > & params2 = otherInst->params;
    488 
    489                         auto it = params.begin();
    490                         auto jt = params2.begin();
    491                         for ( ; it != params.end() && jt != params2.end(); ++it, ++jt ) {
    492                                 auto param = strict_dynamic_cast< const ast::TypeExpr * >( it->get() );
    493                                 auto param2 = strict_dynamic_cast< const ast::TypeExpr * >( jt->get() );
    494 
    495                                 ast::ptr< ast::Type > pty = param->type;
    496                                 ast::ptr< ast::Type > pty2 = param2->type;
    497 
    498                                 bool isTuple = Tuples::isTtype( pty );
    499                                 bool isTuple2 = Tuples::isTtype( pty2 );
    500 
    501                                 if ( isTuple && isTuple2 ) {
    502                                         ++it; ++jt;  // skip ttype parameters before break
    503                                 } else if ( isTuple ) {
    504                                         // bundle remaining params into tuple
    505                                         pty2 = tupleFromExprs( param2, jt, params2.end(), pty->qualifiers );
    506                                         ++it;  // skip ttype parameter for break
    507                                 } else if ( isTuple2 ) {
    508                                         // bundle remaining params into tuple
    509                                         pty = tupleFromExprs( param, it, params.end(), pty2->qualifiers );
    510                                         ++jt;  // skip ttype parameter for break
    511                                 }
    512 
    513                                 if ( ! unifyExact(
    514                                                 pty, pty2, tenv, need, have, open, noWiden() ) ) {
    515                                         result = false;
    516                                         return;
    517                                 }
    518 
    519                                 // ttype parameter should be last
    520                                 if ( isTuple || isTuple2 ) break;
     519
     520                        // ttype parameter should be last
     521                        if ( isTuple || isTuple2 ) break;
     522                }
     523                result = it == params.end() && jt == params2.end();
     524        }
     525
     526public:
     527        void postvisit( const ast::StructInstType * aggrType ) {
     528                handleGenericRefType( aggrType, type2 );
     529                result = result || tryToUnifyWithEnumValue(aggrType, type2, tenv, need, have, open, noWiden());
     530        }
     531
     532        void postvisit( const ast::UnionInstType * aggrType ) {
     533                handleGenericRefType( aggrType, type2 );
     534                result = result || tryToUnifyWithEnumValue(aggrType, type2, tenv, need, have, open, noWiden());
     535        }
     536
     537        void postvisit( const ast::EnumInstType * aggrType ) {
     538                handleRefType( aggrType, type2 );
     539                result = result || tryToUnifyWithEnumValue(aggrType, type2, tenv, need, have, open, noWiden());
     540        }
     541
     542        void postvisit( const ast::EnumAttrType * enumAttr ) {
     543                // Lazy approach for now
     544                if ( auto otherPos = dynamic_cast< const ast::EnumAttrType *>( type2 ) ) {
     545                        if ( enumAttr->match(otherPos) ) {
     546                                result = otherPos;
    521547                        }
    522                         result = it == params.end() && jt == params2.end();
    523                 }
    524 
    525         public:
    526                 void postvisit( const ast::StructInstType * aggrType ) {
    527                         handleGenericRefType( aggrType, type2 );
    528                         result = result || tryToUnifyWithEnumValue(aggrType, type2, tenv, need, have, open, noWiden());
    529                 }
    530 
    531                 void postvisit( const ast::UnionInstType * aggrType ) {
    532                         handleGenericRefType( aggrType, type2 );
    533                         result = result || tryToUnifyWithEnumValue(aggrType, type2, tenv, need, have, open, noWiden());
    534                 }
    535 
    536                 void postvisit( const ast::EnumInstType * aggrType ) {
    537                         handleRefType( aggrType, type2 );
    538                         result = result || tryToUnifyWithEnumValue(aggrType, type2, tenv, need, have, open, noWiden());
    539                 }
    540 
    541                 void postvisit( const ast::EnumAttrType * enumAttr ) {
    542                         // Lazy approach for now
    543                         if ( auto otherPos = dynamic_cast< const ast::EnumAttrType *>(type2) ) {
    544                                 if ( enumAttr->match(otherPos) ) {
    545                                         result = otherPos;
    546                                 }
     548                }
     549        }
     550
     551        void postvisit( const ast::TraitInstType * aggrType ) {
     552                handleRefType( aggrType, type2 );
     553                result = result || tryToUnifyWithEnumValue(aggrType, type2, tenv, need, have, open, noWiden());
     554        }
     555
     556        void postvisit( const ast::TypeInstType * typeInst ) {
     557                // assert( open.find( *typeInst ) == open.end() );
     558                auto otherInst = dynamic_cast< const ast::TypeInstType * >( type2 );
     559                if ( otherInst && typeInst->name == otherInst->name ) {
     560                        this->result = otherInst;
     561                }
     562                result = result || tryToUnifyWithEnumValue(typeInst, type2, tenv, need, have, open, noWiden());
     563        }
     564
     565private:
     566        /// Creates a tuple type based on a list of Type
     567        static bool unifyList(
     568                const std::vector< ast::ptr< ast::Type > > & list1,
     569                const std::vector< ast::ptr< ast::Type > > & list2, ast::TypeEnvironment & env,
     570                ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open
     571        ) {
     572                auto crnt1 = list1.begin();
     573                auto crnt2 = list2.begin();
     574                while ( crnt1 != list1.end() && crnt2 != list2.end() ) {
     575                        const ast::Type * t1 = *crnt1;
     576                        const ast::Type * t2 = *crnt2;
     577                        bool isTuple1 = Tuples::isTtype( t1 );
     578                        bool isTuple2 = Tuples::isTtype( t2 );
     579
     580                        // assumes ttype must be last parameter
     581                        if ( isTuple1 && !isTuple2 ) {
     582                                // combine entirety of list2, then unify
     583                                return unifyExact(
     584                                        t1, tupleFromTypes( list2 ), env, need, have, open,
     585                                        noWiden() );
     586                        } else if ( !isTuple1 && isTuple2 ) {
     587                                // combine entirety of list1, then unify
     588                                return unifyExact(
     589                                        tupleFromTypes( list1 ), t2, env, need, have, open,
     590                                        noWiden() );
    547591                        }
    548                 }
    549 
    550                 void postvisit( const ast::TraitInstType * aggrType ) {
    551                         handleRefType( aggrType, type2 );
    552                         result = result || tryToUnifyWithEnumValue(aggrType, type2, tenv, need, have, open, noWiden());
    553                 }
    554 
    555                 void postvisit( const ast::TypeInstType * typeInst ) {
    556                         // assert( open.find( *typeInst ) == open.end() );
    557                         auto otherInst = dynamic_cast< const ast::TypeInstType * >( type2 );
    558                         if ( otherInst && typeInst->name == otherInst->name ) {
    559                                 this->result = otherInst;
    560                         }
    561                         result = result || tryToUnifyWithEnumValue(typeInst, type2, tenv, need, have, open, noWiden());
    562                 }
    563 
    564         private:
    565                 /// Creates a tuple type based on a list of Type
    566 
    567                 static bool unifyList(
    568                         const std::vector< ast::ptr< ast::Type > > & list1,
    569                         const std::vector< ast::ptr< ast::Type > > & list2, ast::TypeEnvironment & env,
    570                         ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open
    571                 ) {
    572                         auto crnt1 = list1.begin();
    573                         auto crnt2 = list2.begin();
    574                         while ( crnt1 != list1.end() && crnt2 != list2.end() ) {
    575                                 const ast::Type * t1 = *crnt1;
    576                                 const ast::Type * t2 = *crnt2;
    577                                 bool isTuple1 = Tuples::isTtype( t1 );
    578                                 bool isTuple2 = Tuples::isTtype( t2 );
    579 
    580                                 // assumes ttype must be last parameter
    581                                 if ( isTuple1 && ! isTuple2 ) {
    582                                         // combine entirety of list2, then unify
    583                                         return unifyExact(
    584                                                 t1, tupleFromTypes( list2 ), env, need, have, open,
    585                                                 noWiden() );
    586                                 } else if ( ! isTuple1 && isTuple2 ) {
    587                                         // combine entirety of list1, then unify
    588                                         return unifyExact(
    589                                                 tupleFromTypes( list1 ), t2, env, need, have, open,
    590                                                 noWiden() );
    591                                 }
    592 
    593                                 if ( ! unifyExact(
    594                                         t1, t2, env, need, have, open, noWiden() )
    595                                 ) return false;
    596 
    597                                 ++crnt1; ++crnt2;
    598                         }
    599 
    600                         if ( crnt1 != list1.end() ) {
    601                                 // try unifying empty tuple type with ttype
    602                                 const ast::Type * t1 = *crnt1;
    603                                 if ( ! Tuples::isTtype( t1 ) ) return false;
    604                                 // xxx - this doesn't generate an empty tuple, contrary to comment; both ported
    605                                 // from Rob's code
    606                                 return unifyExact(
    607                                                 t1, tupleFromTypes( list2 ), env, need, have, open,
    608                                                 noWiden() );
    609                         } else if ( crnt2 != list2.end() ) {
    610                                 // try unifying empty tuple with ttype
    611                                 const ast::Type * t2 = *crnt2;
    612                                 if ( ! Tuples::isTtype( t2 ) ) return false;
    613                                 // xxx - this doesn't generate an empty tuple, contrary to comment; both ported
    614                                 // from Rob's code
    615                                 return unifyExact(
    616                                                 tupleFromTypes( list1 ), t2, env, need, have, open,
    617                                                 noWiden() );
    618                         }
    619 
    620                         return true;
    621                 }
    622 
    623         public:
    624                 void postvisit( const ast::TupleType * tuple ) {
    625                         auto tuple2 = dynamic_cast< const ast::TupleType * >( type2 );
    626                         if ( ! tuple2 ) return;
    627 
    628                         ast::Pass<TtypeExpander> expander{ tenv };
    629 
    630                         const ast::Type * flat = tuple->accept( expander );
    631                         const ast::Type * flat2 = tuple2->accept( expander );
    632 
    633                         auto types = flatten( flat );
    634                         auto types2 = flatten( flat2 );
    635 
    636                         result = unifyList( types, types2, tenv, need, have, open )
    637                                 || tryToUnifyWithEnumValue(tuple, type2, tenv, need, have, open, noWiden());
    638                 }
    639 
    640                 void postvisit( const ast::VarArgsType * vat) {
    641                         result = dynamic_cast< const ast::VarArgsType * >( type2 )
    642                                 || tryToUnifyWithEnumValue(vat, type2, tenv, need, have, open, noWiden());
    643                 }
    644 
    645                 void postvisit( const ast::ZeroType * zt) {
    646                         result = dynamic_cast< const ast::ZeroType * >( type2 )
    647                                 || tryToUnifyWithEnumValue(zt, type2, tenv, need, have, open, noWiden());
    648                 }
    649 
    650                 void postvisit( const ast::OneType * ot) {
    651                         result = dynamic_cast< const ast::OneType * >( type2 )
    652                                 || tryToUnifyWithEnumValue(ot, type2, tenv, need, have, open, noWiden());
    653                 }
    654         };
    655 
    656         // size_t Unify::traceId = Stats::Heap::new_stacktrace_id("Unify");
    657 
    658         bool unify(
    659                         const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
    660                         ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
    661                         ast::OpenVarSet & open
    662         ) {
    663                 ast::ptr<ast::Type> common;
    664                 return unify( type1, type2, env, need, have, open, common );
    665         }
    666 
    667         bool unify(
    668                         const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
    669                         ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
    670                         ast::OpenVarSet & open, ast::ptr<ast::Type> & common
    671         ) {
    672                 ast::OpenVarSet closed;
    673                 // findOpenVars( type1, open, closed, need, have, FirstClosed );
    674                 findOpenVars( type2, open, closed, need, have, env, FirstOpen );
    675                 return unifyInexact(
    676                         type1, type2, env, need, have, open, WidenMode{ true, true }, common );
    677         }
    678 
    679         bool unifyExact(
    680                         const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env,
    681                         ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
    682                         WidenMode widen
    683         ) {
    684                 if ( type1->qualifiers != type2->qualifiers ) return false;
    685 
    686                 auto var1 = dynamic_cast< const ast::TypeInstType * >( type1 );
    687                 auto var2 = dynamic_cast< const ast::TypeInstType * >( type2 );
    688                 bool isopen1 = var1 && env.lookup(*var1);
    689                 bool isopen2 = var2 && env.lookup(*var2);
    690 
    691                 if ( isopen1 && isopen2 ) {
    692                         if ( var1->base->kind != var2->base->kind ) return false;
    693                         return env.bindVarToVar(
    694                                 var1, var2, ast::TypeData{ var1->base->kind, var1->base->sized||var2->base->sized }, need, have,
    695                                 open, widen );
    696                 } else if ( isopen1 ) {
    697                         return env.bindVar( var1, type2, ast::TypeData{var1->base}, need, have, open, widen );
    698                 } else if ( isopen2 ) {
    699                         return env.bindVar( var2, type1, ast::TypeData{var2->base}, need, have, open, widen );
    700                 } else {
    701                         return ast::Pass<Unify>::read(
    702                                 type1, type2, env, need, have, open, widen );
    703                 }
    704         }
    705 
    706         bool unifyInexact(
    707                         const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
    708                         ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
    709                         const ast::OpenVarSet & open, WidenMode widen,
    710                         ast::ptr<ast::Type> & common
    711         ) {
    712                 ast::CV::Qualifiers q1 = type1->qualifiers, q2 = type2->qualifiers;
    713 
    714                 // force t1 and t2 to be cloned if their qualifiers must be stripped, so that type1 and
    715                 // type2 are left unchanged; calling convention forces type{1,2}->strong_ref >= 1
    716                 ast::Type * t1 = shallowCopy(type1.get());
    717                 ast::Type * t2 = shallowCopy(type2.get());
    718                 t1->qualifiers = {};
    719                 t2->qualifiers = {};
    720                 ast::ptr< ast::Type > t1_(t1);
    721                 ast::ptr< ast::Type > t2_(t2);
    722 
    723                 if ( unifyExact( t1, t2, env, need, have, open, widen ) ) {
    724                         // if exact unification on unqualified types, try to merge qualifiers
    725                         if ( q1 == q2 || ( ( q1 > q2 || widen.first ) && ( q2 > q1 || widen.second ) ) ) {
    726                                 t1->qualifiers = q1 | q2;
    727                                 common = t1;
    728                                 return true;
    729                         } else {
    730                                 return false;
    731                         }
    732 
    733                 } else if (( common = commonType( t1, t2, env, need, have, open, widen ))) {
    734                         // no exact unification, but common type
    735                         auto c = shallowCopy(common.get());
    736                         c->qualifiers = q1 | q2;
    737                         common = c;
     592
     593                        if ( !unifyExact(
     594                                t1, t2, env, need, have, open, noWiden() )
     595                        ) return false;
     596
     597                        ++crnt1; ++crnt2;
     598                }
     599
     600                if ( crnt1 != list1.end() ) {
     601                        // try unifying empty tuple type with ttype
     602                        const ast::Type * t1 = *crnt1;
     603                        if ( !Tuples::isTtype( t1 ) ) return false;
     604                        // xxx - this doesn't generate an empty tuple, contrary to comment; both ported
     605                        // from Rob's code
     606                        return unifyExact(
     607                                        t1, tupleFromTypes( list2 ), env, need, have, open,
     608                                        noWiden() );
     609                } else if ( crnt2 != list2.end() ) {
     610                        // try unifying empty tuple with ttype
     611                        const ast::Type * t2 = *crnt2;
     612                        if ( !Tuples::isTtype( t2 ) ) return false;
     613                        // xxx - this doesn't generate an empty tuple, contrary to comment; both ported
     614                        // from Rob's code
     615                        return unifyExact(
     616                                        tupleFromTypes( list1 ), t2, env, need, have, open,
     617                                        noWiden() );
     618                }
     619
     620                return true;
     621        }
     622
     623public:
     624        void postvisit( const ast::TupleType * tuple ) {
     625                auto tuple2 = dynamic_cast< const ast::TupleType * >( type2 );
     626                if ( ! tuple2 ) return;
     627
     628                ast::Pass<TtypeExpander> expander{ tenv };
     629
     630                const ast::Type * flat = tuple->accept( expander );
     631                const ast::Type * flat2 = tuple2->accept( expander );
     632
     633                auto types = flatten( flat );
     634                auto types2 = flatten( flat2 );
     635
     636                result = unifyList( types, types2, tenv, need, have, open )
     637                        || tryToUnifyWithEnumValue(tuple, type2, tenv, need, have, open, noWiden());
     638        }
     639
     640        void postvisit( const ast::VarArgsType * vat) {
     641                result = dynamic_cast< const ast::VarArgsType * >( type2 )
     642                        || tryToUnifyWithEnumValue(vat, type2, tenv, need, have, open, noWiden());
     643        }
     644
     645        void postvisit( const ast::ZeroType * zt) {
     646                result = dynamic_cast< const ast::ZeroType * >( type2 )
     647                        || tryToUnifyWithEnumValue(zt, type2, tenv, need, have, open, noWiden());
     648        }
     649
     650        void postvisit( const ast::OneType * ot) {
     651                result = dynamic_cast< const ast::OneType * >( type2 )
     652                        || tryToUnifyWithEnumValue(ot, type2, tenv, need, have, open, noWiden());
     653        }
     654};
     655
     656// size_t Unify::traceId = Stats::Heap::new_stacktrace_id("Unify");
     657
     658bool unify(
     659                const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
     660                ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
     661                ast::OpenVarSet & open
     662) {
     663        ast::ptr<ast::Type> common;
     664        return unify( type1, type2, env, need, have, open, common );
     665}
     666
     667bool unify(
     668                const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
     669                ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
     670                ast::OpenVarSet & open, ast::ptr<ast::Type> & common
     671) {
     672        ast::OpenVarSet closed;
     673        // findOpenVars( type1, open, closed, need, have, FirstClosed );
     674        findOpenVars( type2, open, closed, need, have, env, FirstOpen );
     675        return unifyInexact(
     676                type1, type2, env, need, have, open, WidenMode{ true, true }, common );
     677}
     678
     679bool unifyExact(
     680                const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env,
     681                ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
     682                WidenMode widen
     683) {
     684        if ( type1->qualifiers != type2->qualifiers ) return false;
     685
     686        auto var1 = dynamic_cast< const ast::TypeInstType * >( type1 );
     687        auto var2 = dynamic_cast< const ast::TypeInstType * >( type2 );
     688        bool isopen1 = var1 && env.lookup(*var1);
     689        bool isopen2 = var2 && env.lookup(*var2);
     690
     691        if ( isopen1 && isopen2 ) {
     692                if ( var1->base->kind != var2->base->kind ) return false;
     693                return env.bindVarToVar(
     694                        var1, var2, ast::TypeData{ var1->base->kind, var1->base->sized||var2->base->sized }, need, have,
     695                        open, widen );
     696        } else if ( isopen1 ) {
     697                return env.bindVar( var1, type2, ast::TypeData{var1->base}, need, have, open, widen );
     698        } else if ( isopen2 ) {
     699                return env.bindVar( var2, type1, ast::TypeData{var2->base}, need, have, open, widen );
     700        } else {
     701                return ast::Pass<Unify>::read(
     702                        type1, type2, env, need, have, open, widen );
     703        }
     704}
     705
     706bool unifyInexact(
     707                const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
     708                ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
     709                const ast::OpenVarSet & open, WidenMode widen,
     710                ast::ptr<ast::Type> & common
     711) {
     712        ast::CV::Qualifiers q1 = type1->qualifiers, q2 = type2->qualifiers;
     713
     714        // force t1 and t2 to be cloned if their qualifiers must be stripped, so that type1 and
     715        // type2 are left unchanged; calling convention forces type{1,2}->strong_ref >= 1
     716        ast::Type * t1 = shallowCopy(type1.get());
     717        ast::Type * t2 = shallowCopy(type2.get());
     718        t1->qualifiers = {};
     719        t2->qualifiers = {};
     720        ast::ptr< ast::Type > t1_(t1);
     721        ast::ptr< ast::Type > t2_(t2);
     722
     723        if ( unifyExact( t1, t2, env, need, have, open, widen ) ) {
     724                // if exact unification on unqualified types, try to merge qualifiers
     725                if ( q1 == q2 || ( ( q1 > q2 || widen.first ) && ( q2 > q1 || widen.second ) ) ) {
     726                        t1->qualifiers = q1 | q2;
     727                        common = t1;
    738728                        return true;
    739729                } else {
    740730                        return false;
    741731                }
    742         }
    743 
    744         ast::ptr<ast::Type> extractResultType( const ast::FunctionType * func ) {
    745                 if ( func->returns.empty() ) return new ast::VoidType{};
    746                 if ( func->returns.size() == 1 ) return func->returns[0];
    747 
    748                 std::vector<ast::ptr<ast::Type>> tys;
    749                 for ( const auto & decl : func->returns ) {
    750                         tys.emplace_back( decl );
    751                 }
    752                 return new ast::TupleType{ std::move(tys) };
    753         }
     732        } else if (( common = commonType( t1, t2, env, need, have, open, widen ))) {
     733                // no exact unification, but common type
     734                auto c = shallowCopy(common.get());
     735                c->qualifiers = q1 | q2;
     736                common = c;
     737                return true;
     738        } else {
     739                return false;
     740        }
     741}
     742
     743ast::ptr<ast::Type> extractResultType( const ast::FunctionType * func ) {
     744        if ( func->returns.empty() ) return new ast::VoidType();
     745        if ( func->returns.size() == 1 ) return func->returns[0];
     746
     747        std::vector<ast::ptr<ast::Type>> tys;
     748        for ( const auto & decl : func->returns ) {
     749                tys.emplace_back( decl );
     750        }
     751        return new ast::TupleType( std::move(tys) );
     752}
     753
    754754} // namespace ResolvExpr
    755755

  • src/ResolvExpr/typeops.h

    r15215f02 r13de4478  
    2121
    2222namespace ResolvExpr {
    23         class TypeEnvironment;
    2423
    25         // combos: takes a list of sets and returns a set of lists representing every possible way of forming a list by
    26         // picking one element out of each set
    27         template< typename InputIterator, typename OutputIterator >
    28         void combos( InputIterator begin, InputIterator end, OutputIterator out ) {
    29                 typedef typename InputIterator::value_type SetType;
    30                 typedef typename std::vector< typename SetType::value_type > ListType;
     24class TypeEnvironment;
    3125
    32                 if ( begin == end )     {
    33                         *out++ = ListType();
    34                         return;
    35                 } // if
     26// combos: takes a list of sets and returns a set of lists representing every possible way of forming a list by
     27// picking one element out of each set
     28template< typename InputIterator, typename OutputIterator >
     29void combos( InputIterator begin, InputIterator end, OutputIterator out ) {
     30        typedef typename InputIterator::value_type SetType;
     31        typedef typename std::vector< typename SetType::value_type > ListType;
    3632
    37                 InputIterator current = begin;
    38                 begin++;
     33        if ( begin == end )     {
     34                *out++ = ListType();
     35                return;
     36        } // if
    3937
    40                 std::vector< ListType > recursiveResult;
    41                 combos( begin, end, back_inserter( recursiveResult ) );
     38        InputIterator current = begin;
     39        begin++;
    4240
    43                 for ( const auto& i : recursiveResult ) for ( const auto& j : *current ) {
    44                         ListType result;
    45                         std::back_insert_iterator< ListType > inserter = back_inserter( result );
    46                         *inserter++ = j;
    47                         std::copy( i.begin(), i.end(), inserter );
    48                         *out++ = result;
     41        std::vector< ListType > recursiveResult;
     42        combos( begin, end, back_inserter( recursiveResult ) );
     43
     44        for ( const auto& i : recursiveResult ) for ( const auto& j : *current ) {
     45                ListType result;
     46                std::back_insert_iterator< ListType > inserter = back_inserter( result );
     47                *inserter++ = j;
     48                std::copy( i.begin(), i.end(), inserter );
     49                *out++ = result;
     50        }
     51}
     52
     53/// Flatten tuple type into existing list of types.
     54inline void flatten(
     55        const ast::Type * type, std::vector< ast::ptr< ast::Type > > & out
     56) {
     57        if ( auto tupleType = dynamic_cast< const ast::TupleType * >( type ) ) {
     58                for ( const ast::Type * t : tupleType->types ) {
     59                        flatten( t, out );
    4960                }
     61        } else {
     62                out.emplace_back( type );
     63        }
     64}
     65
     66/// Flatten tuple type into list of types.
     67inline std::vector< ast::ptr< ast::Type > > flatten( const ast::Type * type ) {
     68        std::vector< ast::ptr< ast::Type > > out;
     69        out.reserve( type->size() );
     70        flatten( type, out );
     71        return out;
     72}
     73
     74template< typename Iter >
     75const ast::Type * tupleFromTypes( Iter crnt, Iter end ) {
     76        std::vector< ast::ptr< ast::Type > > types;
     77        while ( crnt != end ) {
     78                // it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure
     79                // that this results in a flat tuple
     80                flatten( *crnt, types );
     81
     82                ++crnt;
    5083        }
    5184
    52         /// flatten tuple type into existing list of types
    53         inline void flatten(
    54                 const ast::Type * type, std::vector< ast::ptr< ast::Type > > & out
    55         ) {
    56                 if ( auto tupleType = dynamic_cast< const ast::TupleType * >( type ) ) {
    57                         for ( const ast::Type * t : tupleType->types ) {
    58                                 flatten( t, out );
    59                         }
    60                 } else {
    61                         out.emplace_back( type );
    62                 }
    63         }
     85        return new ast::TupleType( std::move(types) );
     86}
    6487
    65         /// flatten tuple type into list of types
    66         inline std::vector< ast::ptr< ast::Type > > flatten( const ast::Type * type ) {
    67                 std::vector< ast::ptr< ast::Type > > out;
    68                 out.reserve( type->size() );
    69                 flatten( type, out );
    70                 return out;
    71         }
     88inline const ast::Type * tupleFromTypes(
     89        const std::vector< ast::ptr< ast::Type > > & tys
     90) {
     91        return tupleFromTypes( tys.begin(), tys.end() );
     92}
    7293
    73         template< typename Iter >
    74         const ast::Type * tupleFromTypes( Iter crnt, Iter end ) {
    75                 std::vector< ast::ptr< ast::Type > > types;
    76                 while ( crnt != end ) {
    77                         // it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure
    78                         // that this results in a flat tuple
    79                         flatten( *crnt, types );
    80 
    81                         ++crnt;
    82                 }
    83 
    84                 return new ast::TupleType{ std::move(types) };
    85         }
    86 
    87         inline const ast::Type * tupleFromTypes(
    88                 const std::vector< ast::ptr< ast::Type > > & tys
    89         ) {
    90                 return tupleFromTypes( tys.begin(), tys.end() );
    91         }
    9294} // namespace ResolvExpr
    9395
Note: See TracChangeset for help on using the changeset viewer.