Changeset f474e91


Ignore:
Timestamp:
Jun 3, 2019, 5:36:43 PM (3 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
arm-eh, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr
Children:
4ae2364
Parents:
8d70648
Message:

Port unification calculations to new AST

Location:
src
Files:
13 edited

Legend:

Unmodified
Added
Removed
  • src/AST/Decl.hpp

    r8d70648 rf474e91  
    102102        ptr<Expr> bitfieldWidth;
    103103
    104         ObjectDecl( const CodeLocation & loc, const std::string & name, const Type * type, Init * init = nullptr,
    105                 Storage::Classes storage = {}, Linkage::Spec linkage = Linkage::C, Expr * bitWd = nullptr,
    106                 std::vector< ptr<Attribute> > && attrs = {}, Function::Specs fs = {})
     104        ObjectDecl( const CodeLocation & loc, const std::string & name, const Type * type,
     105                Init * init = nullptr, Storage::Classes storage = {}, Linkage::Spec linkage = Linkage::C,
     106                Expr * bitWd = nullptr, std::vector< ptr<Attribute> > && attrs = {},
     107                Function::Specs fs = {} )
    107108        : DeclWithType( loc, name, storage, linkage, std::move(attrs), fs ), type( type ),
    108109          init( init ), bitfieldWidth( bitWd ) {}
  • src/AST/TypeEnvironment.cpp

    r8d70648 rf474e91  
    4646}
    4747
    48 void print( std::ostream & out, const OpenVarSet & openVars, Indenter indent ) {
     48void print( std::ostream & out, const OpenVarSet & open, Indenter indent ) {
    4949        out << indent;
    5050        bool first = true;
    51         for ( const auto & i : openVars ) {
     51        for ( const auto & i : open ) {
    5252                if ( first ) { first = false; } else { out << ' '; }
    5353                out << i.first << "(" << i.second << ")";
     
    166166
    167167bool TypeEnvironment::combine(
    168                 const TypeEnvironment & o, OpenVarSet & openVars, const SymbolTable & symtab ) {
     168                const TypeEnvironment & o, OpenVarSet & open, const SymbolTable & symtab ) {
    169169        // short-circuit easy cases
    170170        if ( o.empty() ) return true;
     
    189189                        EqvClass & r = *rt;
    190190                        // merge bindings
    191                         if ( ! mergeBound( r, c, openVars, symtab ) ) return false;
     191                        if ( ! mergeBound( r, c, open, symtab ) ) return false;
    192192                        // merge previous unbound variables into this class, checking occurs if needed
    193193                        if ( r.bound ) for ( const auto & u : c.vars ) {
     
    204204                                } else if ( st != rt ) {
    205205                                        // bound, but not to the same class
    206                                         if ( ! mergeClasses( rt, st, openVars, symtab ) ) return false;
     206                                        if ( ! mergeClasses( rt, st, open, symtab ) ) return false;
    207207                                }       // ignore bound into the same class
    208208                        }
     
    216216}
    217217
    218 void TypeEnvironment::extractOpenVars( OpenVarSet & openVars ) const {
     218void TypeEnvironment::extractOpenVars( OpenVarSet & open ) const {
    219219        for ( const auto & clz : env ) {
    220220                for ( const auto & var : clz.vars ) {
    221                         openVars[ var ] = clz.data;
    222                 }
    223         }
    224 }
    225 
    226 void TypeEnvironment::addActual( const TypeEnvironment & actualEnv, OpenVarSet & openVars ) {
     221                        open[ var ] = clz.data;
     222                }
     223        }
     224}
     225
     226void TypeEnvironment::addActual( const TypeEnvironment & actualEnv, OpenVarSet & open ) {
    227227        for ( const auto & clz : actualEnv ) {
    228228                EqvClass c = clz;
    229229                c.allowWidening = false;
    230230                for ( const auto & var : c.vars ) {
    231                         openVars[ var ] = c.data;
     231                        open[ var ] = c.data;
    232232                }
    233233                env.emplace_back( std::move(c) );
     
    268268bool TypeEnvironment::bindVar(
    269269                const TypeInstType * typeInst, const Type * bindTo, const TypeDecl::Data & data,
    270                 AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars,
    271                 WidenMode widenMode, const SymbolTable & symtab ) {
     270                AssertionSet & need, AssertionSet & have, const OpenVarSet & open, WidenMode widen,
     271                const SymbolTable & symtab
     272) {
    272273        // remove references from bound type, so that type variables can only bind to value types
    273         bindTo = bindTo->stripReferences();
    274         auto tyvar = openVars.find( typeInst->name );
    275         assert( tyvar != openVars.end() );
    276         if ( ! tyVarCompatible( tyvar->second, bindTo ) ) return false;
    277         if ( occurs( bindTo, typeInst->name, *this ) ) return false;
     274        ptr<Type> target = bindTo->stripReferences();
     275        auto tyvar = open.find( typeInst->name );
     276        assert( tyvar != open.end() );
     277        if ( ! tyVarCompatible( tyvar->second, target ) ) return false;
     278        if ( occurs( target, typeInst->name, *this ) ) return false;
    278279
    279280        auto it = internal_lookup( typeInst->name );
     
    282283                        // attempt to unify equivalence class type with type to bind to.
    283284                        // equivalence class type has stripped qualifiers which must be restored
    284                         const Type * common = nullptr;
     285                        ptr<Type> common;
    285286                        ptr<Type> newType = it->bound;
    286287                        newType.get_and_mutate()->qualifiers = typeInst->qualifiers;
    287288                        if ( unifyInexact(
    288                                         newType, bindTo, *this, need, have, openVars,
    289                                         widenMode & WidenMode{ it->allowWidening, true }, symtab, common ) ) {
     289                                        newType, target, *this, need, have, open,
     290                                        widen & WidenMode{ it->allowWidening, true }, symtab, common ) ) {
    290291                                if ( common ) {
    291                                         it->bound = common;
     292                                        it->bound = std::move(common);
    292293                                        clear_qualifiers( it->bound );
    293294                                }
    294295                        } else return false;
    295296                } else {
    296                         it->bound = bindTo;
     297                        it->bound = std::move(target);
    297298                        clear_qualifiers( it->bound );
    298                         it->allowWidening = widenMode.widenFirst && widenMode.widenSecond;
     299                        it->allowWidening = widen.first && widen.second;
    299300                }
    300301        } else {
    301302                env.emplace_back(
    302                         typeInst->name, bindTo, widenMode.widenFirst && widenMode.widenSecond, data );
     303                        typeInst->name, target, widen.first && widen.second, data );
    303304        }
    304305        return true;
     
    307308bool TypeEnvironment::bindVarToVar(
    308309                const TypeInstType * var1, const TypeInstType * var2, TypeDecl::Data && data,
    309                 AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars,
    310                 WidenMode widenMode, const SymbolTable & symtab ) {
     310                AssertionSet & need, AssertionSet & have, const OpenVarSet & open,
     311                WidenMode widen, const SymbolTable & symtab
     312) {
    311313        auto c1 = internal_lookup( var1->name );
    312314        auto c2 = internal_lookup( var2->name );
     
    314316        // exit early if variables already bound together
    315317        if ( c1 != env.end() && c1 == c2 ) {
    316                 c1->allowWidening &= widenMode;
     318                c1->allowWidening &= widen;
    317319                return true;
    318320        }
     
    327329                        type1 = c1->bound;
    328330                }
    329                 widen1 = widenMode.widenFirst && c1->allowWidening;
     331                widen1 = widen.first && c1->allowWidening;
    330332        }
    331333        if ( c2 != env.end() ) {
     
    334336                        type2 = c2->bound;
    335337                }
    336                 widen2 = widenMode.widenSecond && c2->allowWidening;
     338                widen2 = widen.second && c2->allowWidening;
    337339        }
    338340
     
    341343                ptr<Type> newType1{ type1 }, newType2{ type2 };
    342344                WidenMode newWidenMode{ widen1, widen2 };
    343                 const Type * common = nullptr;
     345                ptr<Type> common;
    344346
    345347                if ( unifyInexact(
    346                                 newType1, newType2, *this, need, have, openVars, newWidenMode, symtab, common ) ) {
     348                                newType1, newType2, *this, need, have, open, newWidenMode, symtab, common ) ) {
    347349                        c1->vars.insert( c2->vars.begin(), c2->vars.end() );
    348350                        c1->allowWidening = widen1 && widen2;
    349351                        if ( common ) {
    350                                 c1->bound = common;
     352                                c1->bound = std::move(common);
    351353                                clear_qualifiers( c1->bound );
    352354                        }
     
    395397
    396398bool TypeEnvironment::mergeBound(
    397                 EqvClass & to, const EqvClass & from, OpenVarSet & openVars, const SymbolTable & symtab ) {
     399                EqvClass & to, const EqvClass & from, OpenVarSet & open, const SymbolTable & symtab ) {
    398400        if ( from.bound ) {
    399401                if ( to.bound ) {
    400402                        // attempt to unify bound types
    401403                        ptr<Type> toType{ to.bound }, fromType{ from.bound };
    402                         WidenMode widenMode{ to.allowWidening, from.allowWidening };
    403                         const Type * common = nullptr;
     404                        WidenMode widen{ to.allowWidening, from.allowWidening };
     405                        ptr<Type> common;
    404406                        AssertionSet need, have;
    405407
    406408                        if ( unifyInexact(
    407                                         toType, fromType, *this, need, have, openVars, widenMode, symtab, common ) ) {
     409                                        toType, fromType, *this, need, have, open, widen, symtab, common ) ) {
    408410                                // unifies, set common type if necessary
    409411                                if ( common ) {
    410                                         to.bound = common;
     412                                        to.bound = std::move(common);
    411413                                        clear_qualifiers( to.bound );
    412414                                }
     
    423425
    424426bool TypeEnvironment::mergeClasses(
    425                 ClassList::iterator to, ClassList::iterator from, OpenVarSet & openVars,
    426                 const SymbolTable & symtab ) {
     427        ClassList::iterator to, ClassList::iterator from, OpenVarSet & open, const SymbolTable & symtab
     428) {
    427429        EqvClass & r = *to, & s = *from;
    428430
    429431        // ensure bounds match
    430         if ( ! mergeBound( r, s, openVars, symtab ) ) return false;
     432        if ( ! mergeBound( r, s, open, symtab ) ) return false;
    431433
    432434        // check safely bindable
  • src/AST/TypeEnvironment.hpp

    r8d70648 rf474e91  
    178178                const TypeInstType * typeInst, const Type * bindTo, const TypeDecl::Data & data,
    179179                AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars,
    180                 ResolvExpr::WidenMode widenMode, const SymbolTable & symtab );
     180                ResolvExpr::WidenMode widen, const SymbolTable & symtab );
    181181       
    182182        /// Binds the type classes represented by `var1` and `var2` together; will add one or both
     
    185185                const TypeInstType * var1, const TypeInstType * var2, TypeDecl::Data && data,
    186186                AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars,
    187                 ResolvExpr::WidenMode widenMode, const SymbolTable & symtab );
     187                ResolvExpr::WidenMode widen, const SymbolTable & symtab );
    188188
    189189        /// Disallows widening for all bindings in the environment
  • src/AST/porting.md

    r8d70648 rf474e91  
    291291* moved to be helper function in `TypeEnvironment.cpp` (its only use)
    292292
     293`WidenMode`
     294* changed `widenFirst`, `widenSecond` => `first`, `second`
     295* changed `WidenMode widenMode` => `WidenMode widen`
     296
    293297[1] https://gcc.gnu.org/onlinedocs/gcc-9.1.0/gcc/Type-Attributes.html#Type-Attributes
    294298
  • src/ResolvExpr/CommonType.cc

    r8d70648 rf474e91  
    176176        }
    177177
     178        const ast::Type * commonType(
     179                        const ast::Type * type1, const ast::Type * type2, WidenMode widen,
     180                        const ast::SymbolTable & symtab, ast::TypeEnvironment & env,
     181                        const ast::OpenVarSet & open ) {
     182                #warning unimplemented
     183                (void)type1; (void)type2; (void)widen; (void)symtab; (void)env; (void)open;
     184                assert(false);
     185                return nullptr;
     186        }
     187
    178188        // GENERATED START, DO NOT EDIT
    179189        // GENERATED BY BasicTypes-gen.cc
  • src/ResolvExpr/FindOpenVars.cc

    r8d70648 rf474e91  
    9393                common_action( tupleType );
    9494        }
     95
     96        void findOpenVars(
     97                        const ast::Type * type, ast::OpenVarSet & open, ast::OpenVarSet & closed,
     98                        ast::AssertionSet & need, ast::AssertionSet & have, FirstMode firstIsOpen ) {
     99                #warning unimplemented
     100                (void)type; (void)open; (void)closed; (void)need; (void)have; (void)firstIsOpen;
     101                assert(false);
     102        }
    95103} // namespace ResolvExpr
    96104
  • src/ResolvExpr/FindOpenVars.h

    r8d70648 rf474e91  
    1616#pragma once
    1717
     18#include "AST/TypeEnvironment.hpp"  // for AssertionSet, OpenVarSet
    1819#include "ResolvExpr/TypeEnvironment.h"  // for AssertionSet, OpenVarSet
    1920
    2021class Type;
     22namespace ast {
     23        class Type;
     24}
    2125
    2226namespace ResolvExpr {
    2327        // Updates open and closed variables and their associated assertions
    2428        void findOpenVars( Type *type, OpenVarSet &openVars, OpenVarSet &closedVars, AssertionSet &needAssertions, AssertionSet &haveAssertions, bool firstIsOpen );
     29
     30        enum FirstMode { FirstClosed, FirstOpen };
     31
     32        // Updates open and closed variables and their associated assertions
     33        void findOpenVars(
     34                const ast::Type * type, ast::OpenVarSet & open, ast::OpenVarSet & closed,
     35                ast::AssertionSet & need, ast::AssertionSet & have, FirstMode firstIsOpen );
    2536} // namespace ResolvExpr
    2637
  • src/ResolvExpr/TypeEnvironment.cc

    r8d70648 rf474e91  
    205205                                // attempt to unify bound types
    206206                                std::unique_ptr<Type> toType{ to.type->clone() }, fromType{ from.type->clone() };
    207                                 WidenMode widenMode{ to.allowWidening, from.allowWidening };
     207                                WidenMode widen{ to.allowWidening, from.allowWidening };
    208208                                Type* common = nullptr;
    209209                                AssertionSet need, have;
    210                                 if ( unifyInexact( toType.get(), fromType.get(), *this, need, have, openVars, widenMode, indexer, common ) ) {
     210                                if ( unifyInexact( toType.get(), fromType.get(), *this, need, have, openVars, widen, indexer, common ) ) {
    211211                                        // unifies, set common type if necessary
    212212                                        if ( common ) {
     
    343343        }
    344344
    345         bool TypeEnvironment::bindVar( TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
     345        bool TypeEnvironment::bindVar( TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ) {
    346346
    347347                // remove references from other, so that type variables can only bind to value types
     
    362362                                std::unique_ptr< Type > newType( curClass->type->clone() );
    363363                                newType->get_qualifiers() = typeInst->get_qualifiers();
    364                                 if ( unifyInexact( newType.get(), bindTo, *this, need, have, openVars, widenMode & WidenMode( curClass->allowWidening, true ), indexer, common ) ) {
     364                                if ( unifyInexact( newType.get(), bindTo, *this, need, have, openVars, widen & WidenMode( curClass->allowWidening, true ), indexer, common ) ) {
    365365                                        if ( common ) {
    366366                                                common->get_qualifiers() = Type::Qualifiers{};
     
    372372                                newType->get_qualifiers() = Type::Qualifiers{};
    373373                                curClass->set_type( newType );
    374                                 curClass->allowWidening = widenMode.widenFirst && widenMode.widenSecond;
     374                                curClass->allowWidening = widen.first && widen.second;
    375375                        } // if
    376376                } else {
     
    379379                        newClass.type = bindTo->clone();
    380380                        newClass.type->get_qualifiers() = Type::Qualifiers();
    381                         newClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond;
     381                        newClass.allowWidening = widen.first && widen.second;
    382382                        newClass.data = data;
    383383                        env.push_back( std::move(newClass) );
     
    388388        bool TypeEnvironment::bindVarToVar( TypeInstType *var1, TypeInstType *var2,
    389389                        TypeDecl::Data && data, AssertionSet &need, AssertionSet &have,
    390                         const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
     390                        const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ) {
    391391
    392392                auto class1 = internal_lookup( var1->get_name() );
     
    395395                // exit early if variables already bound together
    396396                if ( class1 != env.end() && class1 == class2 ) {
    397                         class1->allowWidening &= widenMode;
     397                        class1->allowWidening &= widen;
    398398                        return true;
    399399                }
     
    408408                                type1 = class1->type;
    409409                        } // if
    410                         widen1 = widenMode.widenFirst && class1->allowWidening;
     410                        widen1 = widen.first && class1->allowWidening;
    411411                } // if
    412412                if ( class2 != env.end() ) {
     
    415415                                type2 = class2->type;
    416416                        } // if
    417                         widen2 = widenMode.widenSecond && class2->allowWidening;
     417                        widen2 = widen.second && class2->allowWidening;
    418418                } // if
    419419
  • src/ResolvExpr/TypeEnvironment.h

    r8d70648 rf474e91  
    136136                /// Binds the type class represented by `typeInst` to the type `bindTo`; will add
    137137                /// the class if needed. Returns false on failure.
    138                 bool bindVar( TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
     138                bool bindVar( TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer );
    139139               
    140140                /// Binds the type classes represented by `var1` and `var2` together; will add
    141141                /// one or both classes if needed. Returns false on failure.
    142                 bool bindVarToVar( TypeInstType *var1, TypeInstType *var2, TypeDecl::Data && data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
     142                bool bindVarToVar( TypeInstType *var1, TypeInstType *var2, TypeDecl::Data && data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer );
    143143
    144144                /// Disallows widening for all bindings in the environment
  • src/ResolvExpr/Unify.cc

    r8d70648 rf474e91  
    1414//
    1515
     16#include "Unify.h"
     17
    1618#include <cassert>                  // for assertf, assert
    1719#include <iterator>                 // for back_insert_iterator, back_inserter
     
    2325#include <vector>
    2426
     27#include "AST/Decl.hpp"
    2528#include "AST/Node.hpp"
     29#include "AST/Pass.hpp"
    2630#include "AST/Type.hpp"
    2731#include "AST/TypeEnvironment.hpp"
     
    3741#include "Tuples/Tuples.h"          // for isTtype
    3842#include "TypeEnvironment.h"        // for EqvClass, AssertionSet, OpenVarSet
    39 #include "Unify.h"
    4043#include "typeops.h"                // for flatten, occurs, commonType
     44
     45namespace ast {
     46        class SymbolTable;
     47}
    4148
    4249namespace SymTab {
     
    4855namespace ResolvExpr {
    4956
    50         struct Unify : public WithShortCircuiting {
    51                 Unify( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
     57        struct Unify_old : public WithShortCircuiting {
     58                Unify_old( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer );
    5259
    5360                bool get_result() const { return result; }
     
    8188                AssertionSet &haveAssertions;
    8289                const OpenVarSet &openVars;
    83                 WidenMode widenMode;
     90                WidenMode widen;
    8491                const SymTab::Indexer &indexer;
    8592        };
     
    8794        /// Attempts an inexact unification of type1 and type2.
    8895        /// Returns false if no such unification; if the types can be unified, sets common (unless they unify exactly and have identical type qualifiers)
    89         bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer, Type *&common );
    90         bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
     96        bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer, Type *&common );
     97        bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer );
     98
     99        bool unifyExact(
     100                const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env,
     101                ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
     102                WidenMode widen, const ast::SymbolTable & symtab );
    91103
    92104        bool typesCompatible( Type *first, Type *second, const SymTab::Indexer &indexer, const TypeEnvironment &env ) {
     
    112124                        const ast::Type * first, const ast::Type * second, const ast::SymbolTable & symtab,
    113125                        const ast::TypeEnvironment & env ) {
    114                 #warning unimplemented
    115                 assert((first, second, symtab, env, false));
    116                 return false;
     126                ast::TypeEnvironment newEnv;
     127                ast::OpenVarSet open, closed;
     128                ast::AssertionSet need, have;
     129
     130                ast::ptr<ast::Type> newFirst{ first }, newSecond{ second };
     131                env.apply( newFirst );
     132                env.apply( newSecond );
     133
     134                findOpenVars( newFirst, open, closed, need, have, FirstClosed );
     135                findOpenVars( newSecond, open, closed, need, have, FirstOpen );
     136
     137                return unifyExact(
     138                        newFirst, newSecond, newEnv, need, have, open, WidenMode{ false, false }, symtab );
    117139        }
    118140
     
    144166                        const ast::Type * first, const ast::Type * second, const ast::SymbolTable & symtab,
    145167                        const ast::TypeEnvironment & env ) {
    146                 #warning unimplemented
    147                 assert((first, second, symtab, env, false));
    148                 return false;
     168                ast::TypeEnvironment newEnv;
     169                ast::OpenVarSet open;
     170                ast::AssertionSet need, have;
     171               
     172                ast::ptr<ast::Type> newFirst{ first }, newSecond{ second };
     173                env.apply( newFirst );
     174                env.apply( newSecond );
     175                clear_qualifiers( newFirst );
     176                clear_qualifiers( newSecond );
     177
     178                return unifyExact(
     179                        newFirst, newSecond, newEnv, need, have, open, WidenMode{ false, false }, symtab );
    149180        }
    150181
     
    171202        }
    172203
    173         bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
     204        bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ) {
    174205#ifdef DEBUG
    175206                TypeEnvironment debugEnv( env );
     
    198229                                result = env.bindVarToVar(
    199230                                        var1, var2, TypeDecl::Data{ entry1->second, entry2->second }, needAssertions,
    200                                         haveAssertions, openVars, widenMode, indexer );
     231                                        haveAssertions, openVars, widen, indexer );
    201232                        }
    202233                } else if ( isopen1 ) {
    203                         result = env.bindVar( var1, type2, entry1->second, needAssertions, haveAssertions, openVars, widenMode, indexer );
    204                 } else if ( isopen2 ) { // TODO: swap widenMode values in call, since type positions are flipped?
    205                         result = env.bindVar( var2, type1, entry2->second, needAssertions, haveAssertions, openVars, widenMode, indexer );
     234                        result = env.bindVar( var1, type2, entry1->second, needAssertions, haveAssertions, openVars, widen, indexer );
     235                } else if ( isopen2 ) { // TODO: swap widen values in call, since type positions are flipped?
     236                        result = env.bindVar( var2, type1, entry2->second, needAssertions, haveAssertions, openVars, widen, indexer );
    206237                } else {
    207                         PassVisitor<Unify> comparator( type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
     238                        PassVisitor<Unify_old> comparator( type2, env, needAssertions, haveAssertions, openVars, widen, indexer );
    208239                        type1->accept( comparator );
    209240                        result = comparator.pass.get_result();
     
    230261        }
    231262
    232         bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer, Type *&common ) {
     263        bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer, Type *&common ) {
    233264                Type::Qualifiers tq1 = type1->get_qualifiers(), tq2 = type2->get_qualifiers();
    234265                type1->get_qualifiers() = Type::Qualifiers();
     
    242273                std::cerr << std::endl;
    243274#endif
    244                 if ( ! unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer ) ) {
     275                if ( ! unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, widen, indexer ) ) {
    245276#ifdef DEBUG
    246277                        std::cerr << "unifyInexact: no exact unification found" << std::endl;
    247278#endif
    248                         if ( ( common = commonType( type1, type2, widenMode.widenFirst, widenMode.widenSecond, indexer, env, openVars ) ) ) {
     279                        if ( ( common = commonType( type1, type2, widen.first, widen.second, indexer, env, openVars ) ) ) {
    249280                                common->get_qualifiers() = tq1 | tq2;
    250281#ifdef DEBUG
     
    262293                } else {
    263294                        if ( tq1 != tq2 ) {
    264                                 if ( ( tq1 > tq2 || widenMode.widenFirst ) && ( tq2 > tq1 || widenMode.widenSecond ) ) {
     295                                if ( ( tq1 > tq2 || widen.first ) && ( tq2 > tq1 || widen.second ) ) {
    265296                                        common = type1->clone();
    266297                                        common->get_qualifiers() = tq1 | tq2;
     
    280311        }
    281312
    282         bool unifyInexact(
    283                         const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env,
    284                         ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & openVars,
    285                         WidenMode widenMode, const ast::SymbolTable & symtab, const ast::Type *& common ) {
    286                 #warning unimplemented
    287                 assert((type1, type2, env, need, have, openVars, widenMode, symtab, common, false));
    288                 return false;
    289         }
    290 
    291         Unify::Unify( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer )
    292                 : result( false ), type2( type2 ), env( env ), needAssertions( needAssertions ), haveAssertions( haveAssertions ), openVars( openVars ), widenMode( widenMode ), indexer( indexer ) {
    293         }
    294 
    295         void Unify::postvisit( __attribute__((unused)) VoidType *voidType) {
     313        Unify_old::Unify_old( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer )
     314                : result( false ), type2( type2 ), env( env ), needAssertions( needAssertions ), haveAssertions( haveAssertions ), openVars( openVars ), widen( widen ), indexer( indexer ) {
     315        }
     316
     317        void Unify_old::postvisit( __attribute__((unused)) VoidType *voidType) {
    296318                result = dynamic_cast< VoidType* >( type2 );
    297319        }
    298320
    299         void Unify::postvisit(BasicType *basicType) {
     321        void Unify_old::postvisit(BasicType *basicType) {
    300322                if ( BasicType *otherBasic = dynamic_cast< BasicType* >( type2 ) ) {
    301323                        result = basicType->get_kind() == otherBasic->get_kind();
     
    325347        }
    326348
    327         void Unify::postvisit(PointerType *pointerType) {
     349        void Unify_old::postvisit(PointerType *pointerType) {
    328350                if ( PointerType *otherPointer = dynamic_cast< PointerType* >( type2 ) ) {
    329351                        result = unifyExact( pointerType->get_base(), otherPointer->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
     
    333355        }
    334356
    335         void Unify::postvisit(ReferenceType *refType) {
     357        void Unify_old::postvisit(ReferenceType *refType) {
    336358                if ( ReferenceType *otherRef = dynamic_cast< ReferenceType* >( type2 ) ) {
    337359                        result = unifyExact( refType->get_base(), otherRef->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
     
    341363        }
    342364
    343         void Unify::postvisit(ArrayType *arrayType) {
     365        void Unify_old::postvisit(ArrayType *arrayType) {
    344366                ArrayType *otherArray = dynamic_cast< ArrayType* >( type2 );
    345367                // to unify, array types must both be VLA or both not VLA
     
    421443        /// If this isn't done then argument lists can have wildly different
    422444        /// size and structure, when they should be compatible.
    423         struct TtypeExpander : public WithShortCircuiting {
     445        struct TtypeExpander_old : public WithShortCircuiting {
    424446                TypeEnvironment & tenv;
    425                 TtypeExpander( TypeEnvironment & tenv ) : tenv( tenv ) {}
     447                TtypeExpander_old( TypeEnvironment & tenv ) : tenv( tenv ) {}
    426448                void premutate( TypeInstType * ) { visit_children = false; }
    427449                Type * postmutate( TypeInstType * typeInst ) {
     
    442464                dst.clear();
    443465                for ( DeclarationWithType * dcl : src ) {
    444                         PassVisitor<TtypeExpander> expander( env );
     466                        PassVisitor<TtypeExpander_old> expander( env );
    445467                        dcl->acceptMutator( expander );
    446468                        std::list< Type * > types;
     
    457479        }
    458480
    459         void Unify::postvisit(FunctionType *functionType) {
     481        void Unify_old::postvisit(FunctionType *functionType) {
    460482                FunctionType *otherFunction = dynamic_cast< FunctionType* >( type2 );
    461483                if ( otherFunction && functionType->get_isVarArgs() == otherFunction->get_isVarArgs() ) {
     
    468490
    469491                        // sizes don't have to match if ttypes are involved; need to be more precise wrt where the ttype is to prevent errors
    470                         if ( (flatFunc->parameters.size() == flatOther->parameters.size() && flatFunc->returnVals.size() == flatOther->returnVals.size()) || flatFunc->isTtype() || flatOther->isTtype() ) {
     492                        if (
     493                                        (flatFunc->parameters.size() == flatOther->parameters.size() &&
     494                                                flatFunc->returnVals.size() == flatOther->returnVals.size())
     495                                        || flatFunc->isTtype()
     496                                        || flatOther->isTtype()
     497                        ) {
    471498                                if ( unifyDeclList( flatFunc->parameters.begin(), flatFunc->parameters.end(), flatOther->parameters.begin(), flatOther->parameters.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
    472499                                        if ( unifyDeclList( flatFunc->returnVals.begin(), flatFunc->returnVals.end(), flatOther->returnVals.begin(), flatOther->returnVals.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
     
    484511
    485512        template< typename RefType >
    486         void Unify::handleRefType( RefType *inst, Type *other ) {
     513        void Unify_old::handleRefType( RefType *inst, Type *other ) {
    487514                // check that other type is compatible and named the same
    488515                RefType *otherStruct = dynamic_cast< RefType* >( other );
     
    491518
    492519        template< typename RefType >
    493         void Unify::handleGenericRefType( RefType *inst, Type *other ) {
     520        void Unify_old::handleGenericRefType( RefType *inst, Type *other ) {
    494521                // Check that other type is compatible and named the same
    495522                handleRefType( inst, other );
     
    559586        }
    560587
    561         void Unify::postvisit(StructInstType *structInst) {
     588        void Unify_old::postvisit(StructInstType *structInst) {
    562589                handleGenericRefType( structInst, type2 );
    563590        }
    564591
    565         void Unify::postvisit(UnionInstType *unionInst) {
     592        void Unify_old::postvisit(UnionInstType *unionInst) {
    566593                handleGenericRefType( unionInst, type2 );
    567594        }
    568595
    569         void Unify::postvisit(EnumInstType *enumInst) {
     596        void Unify_old::postvisit(EnumInstType *enumInst) {
    570597                handleRefType( enumInst, type2 );
    571598        }
    572599
    573         void Unify::postvisit(TraitInstType *contextInst) {
     600        void Unify_old::postvisit(TraitInstType *contextInst) {
    574601                handleRefType( contextInst, type2 );
    575602        }
    576603
    577         void Unify::postvisit(TypeInstType *typeInst) {
     604        void Unify_old::postvisit(TypeInstType *typeInst) {
    578605                assert( openVars.find( typeInst->get_name() ) == openVars.end() );
    579606                TypeInstType *otherInst = dynamic_cast< TypeInstType* >( type2 );
     
    630657        }
    631658
    632         void Unify::postvisit(TupleType *tupleType) {
     659        void Unify_old::postvisit(TupleType *tupleType) {
    633660                if ( TupleType *otherTuple = dynamic_cast< TupleType* >( type2 ) ) {
    634661                        std::unique_ptr<TupleType> flat1( tupleType->clone() );
     
    636663                        std::list<Type *> types1, types2;
    637664
    638                         PassVisitor<TtypeExpander> expander( env );
     665                        PassVisitor<TtypeExpander_old> expander( env );
    639666                        flat1->acceptMutator( expander );
    640667                        flat2->acceptMutator( expander );
     
    647674        }
    648675
    649         void Unify::postvisit( __attribute__((unused)) VarArgsType *varArgsType ) {
     676        void Unify_old::postvisit( __attribute__((unused)) VarArgsType *varArgsType ) {
    650677                result = dynamic_cast< VarArgsType* >( type2 );
    651678        }
    652679
    653         void Unify::postvisit( __attribute__((unused)) ZeroType *zeroType ) {
     680        void Unify_old::postvisit( __attribute__((unused)) ZeroType *zeroType ) {
    654681                result = dynamic_cast< ZeroType* >( type2 );
    655682        }
    656683
    657         void Unify::postvisit( __attribute__((unused)) OneType *oneType ) {
     684        void Unify_old::postvisit( __attribute__((unused)) OneType *oneType ) {
    658685                result = dynamic_cast< OneType* >( type2 );
    659686        }
     
    673700        }
    674701
     702        class Unify_new : public ast::WithShortCircuiting {
     703                const ast::Type * type2;
     704                ast::TypeEnvironment & tenv;
     705                ast::AssertionSet & need;
     706                ast::AssertionSet & have;
     707                const ast::OpenVarSet & open;
     708                WidenMode widen;
     709                const ast::SymbolTable & symtab;
     710        public:
     711                bool result;
     712
     713                Unify_new(
     714                        const ast::Type * type2, ast::TypeEnvironment & env, ast::AssertionSet & need,
     715                        ast::AssertionSet & have, const ast::OpenVarSet & open, WidenMode widen,
     716                        const ast::SymbolTable & symtab )
     717                : type2(type2), tenv(env), need(need), have(have), open(open), widen(widen),
     718                  symtab(symtab), result(false) {}
     719
     720                void previsit( const ast::Node * ) { visit_children = false; }
     721               
     722                void previsit( const ast::VoidType * ) {
     723                        visit_children = false;
     724                        result = dynamic_cast< const ast::VoidType * >( type2 );
     725                }
     726
     727                void previsit( const ast::BasicType * basic ) {
     728                        visit_children = false;
     729                        if ( auto basic2 = dynamic_cast< const ast::BasicType * >( type2 ) ) {
     730                                result = basic->kind == basic2->kind;
     731                        }
     732                }
     733
     734                void previsit( const ast::PointerType * pointer ) {
     735                        visit_children = false;
     736                        if ( auto pointer2 = dynamic_cast< const ast::PointerType * >( type2 ) ) {
     737                                result = unifyExact(
     738                                        pointer->base, pointer2->base, tenv, need, have, open,
     739                                        WidenMode{ false, false }, symtab );
     740                        }
     741                }
     742
     743                void previsit( const ast::ArrayType * array ) {
     744                        visit_children = false;
     745                        auto array2 = dynamic_cast< const ast::ArrayType * >( type2 );
     746                        if ( ! array2 ) return;
     747
     748                        // to unify, array types must both be VLA or both not VLA and both must have a
     749                        // dimension expression or not have a dimension
     750                        if ( array->isVarLen != array2->isVarLen ) return;
     751                        if ( ! array->isVarLen && ! array2->isVarLen
     752                                        && array->dimension && array2->dimension ) {
     753                                auto ce1 = array->dimension.as< ast::ConstantExpr >();
     754                                auto ce2 = array2->dimension.as< ast::ConstantExpr >();
     755
     756                                // see C11 Reference Manual 6.7.6.2.6
     757                                // two array types with size specifiers that are integer constant expressions are
     758                                // compatible if both size specifiers have the same constant value
     759                                if ( ce1 && ce2 && ce1->intValue() != ce2->intValue() ) return;
     760                        }
     761
     762                        result = unifyExact(
     763                                array->base, array2->base, tenv, need, have, open, WidenMode{ false, false },
     764                                symtab );
     765                }
     766
     767                void previsit( const ast::ReferenceType * ref ) {
     768                        visit_children = false;
     769                        if ( auto ref2 = dynamic_cast< const ast::ReferenceType * >( type2 ) ) {
     770                                result = unifyExact(
     771                                        ref->base, ref2->base, tenv, need, have, open, WidenMode{ false, false },
     772                                        symtab );
     773                        }
     774                }
     775
     776        private:
     777                /// Replaces ttype variables with their bound types.
     778                /// If this isn't done when satifying ttype assertions, then argument lists can have
     779                /// different size and structure when they should be compatible.
     780                struct TtypeExpander_new : public ast::WithShortCircuiting {
     781                        ast::TypeEnvironment & tenv;
     782
     783                        TtypeExpander_new( ast::TypeEnvironment & env ) : tenv( env ) {}
     784
     785                        const ast::Type * postmutate( const ast::TypeInstType * typeInst ) {
     786                                if ( const ast::EqvClass * clz = tenv.lookup( typeInst->name ) ) {
     787                                        // expand ttype parameter into its actual type
     788                                        if ( clz->data.kind == ast::TypeVar::Ttype && clz->bound ) {
     789                                                return clz->bound;
     790                                        }
     791                                }
     792                                return typeInst;
     793                        }
     794                };
     795
     796                /// returns flattened version of `src`
     797                static std::vector< ast::ptr< ast::DeclWithType > > flattenList(
     798                        const std::vector< ast::ptr< ast::DeclWithType > > & src, ast::TypeEnvironment & env
     799                ) {
     800                        std::vector< ast::ptr< ast::DeclWithType > > dst;
     801                        dst.reserve( src.size() );
     802                        for ( const ast::DeclWithType * d : src ) {
     803                                ast::Pass<TtypeExpander_new> expander{ env };
     804                                d = d->accept( expander );
     805                                auto types = flatten( d->get_type() );
     806                                for ( ast::ptr< ast::Type > & t : types ) {
     807                                        // outermost const, volatile, _Atomic qualifiers in parameters should not play
     808                                        // a role in the unification of function types, since they do not determine
     809                                        // whether a function is callable.
     810                                        // NOTE: **must** consider at least mutex qualifier, since functions can be
     811                                        // overloaded on outermost mutex and a mutex function has different
     812                                        // requirements than a non-mutex function
     813                                        t.get_and_mutate()->qualifiers
     814                                                -= ast::CV::Const | ast::CV::Volatile | ast::CV::Atomic;
     815                                        dst.emplace_back( new ast::ObjectDecl{ d->location, "", t } );
     816                                }
     817                        }
     818                        return dst;
     819                }
     820
     821                /// Creates a tuple type based on a list of DeclWithType
     822                template< typename Iter >
     823                static ast::ptr< ast::Type > tupleFromDecls( Iter crnt, Iter end ) {
     824                        std::vector< ast::ptr< ast::Type > > types;
     825                        while ( crnt != end ) {
     826                                // it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure
     827                                // that this results in a flat tuple
     828                                flatten( (*crnt)->get_type(), types );
     829
     830                                ++crnt;
     831                        }
     832
     833                        return { new ast::TupleType{ std::move(types) } };
     834                }
     835
     836                template< typename Iter >
     837                static bool unifyDeclList(
     838                        Iter crnt1, Iter end1, Iter crnt2, Iter end2, ast::TypeEnvironment & env,
     839                        ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
     840                        const ast::SymbolTable & symtab
     841                ) {
     842                        while ( crnt1 != end1 && crnt2 != end2 ) {
     843                                const ast::Type * t1 = (*crnt1)->get_type();
     844                                const ast::Type * t2 = (*crnt2)->get_type();
     845                                bool isTuple1 = Tuples::isTtype( t1 );
     846                                bool isTuple2 = Tuples::isTtype( t2 );
     847
     848                                // assumes here that ttype *must* be last parameter
     849                                if ( isTuple1 && ! isTuple2 ) {
     850                                        // combine remainder of list2, then unify
     851                                        return unifyExact(
     852                                                t1, tupleFromDecls( crnt2, end2 ), env, need, have, open,
     853                                                WidenMode{ false, false }, symtab );
     854                                } else if ( ! isTuple1 && isTuple2 ) {
     855                                        // combine remainder of list1, then unify
     856                                        return unifyExact(
     857                                                tupleFromDecls( crnt1, end1 ), t2, env, need, have, open,
     858                                                WidenMode{ false, false }, symtab );
     859                                }
     860
     861                                if ( ! unifyExact(
     862                                        t1, t2, env, need, have, open, WidenMode{ false, false }, symtab )
     863                                ) return false;
     864
     865                                ++crnt1; ++crnt2;
     866                        }
     867
     868                        // May get to the end of one argument list before the other. This is only okay if the
     869                        // other is a ttype
     870                        if ( crnt1 != end1 ) {
     871                                // try unifying empty tuple with ttype
     872                                const ast::Type * t1 = (*crnt1)->get_type();
     873                                if ( ! Tuples::isTtype( t1 ) ) return false;
     874                                return unifyExact(
     875                                        t1, tupleFromDecls( crnt2, end2 ), env, need, have, open,
     876                                        WidenMode{ false, false }, symtab );
     877                        } else if ( crnt2 != end2 ) {
     878                                // try unifying empty tuple with ttype
     879                                const ast::Type * t2 = (*crnt2)->get_type();
     880                                if ( ! Tuples::isTtype( t2 ) ) return false;
     881                                return unifyExact(
     882                                        tupleFromDecls( crnt1, end1 ), t2, env, need, have, open,
     883                                        WidenMode{ false, false }, symtab );
     884                        }
     885
     886                        return true;
     887                }
     888
     889                static bool unifyDeclList(
     890                        const std::vector< ast::ptr< ast::DeclWithType > > & list1,
     891                        const std::vector< ast::ptr< ast::DeclWithType > > & list2,
     892                        ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
     893                        const ast::OpenVarSet & open, const ast::SymbolTable & symtab
     894                ) {
     895                        return unifyDeclList(
     896                                list1.begin(), list1.end(), list2.begin(), list2.end(), env, need, have, open,
     897                                symtab );
     898                }
     899
     900                static void markAssertionSet( ast::AssertionSet & assns, const ast::DeclWithType * assn ) {
     901                        auto i = assns.find( assn );
     902                        if ( i != assns.end() ) {
     903                                i->second.isUsed = true;
     904                        }
     905                }
     906
     907                /// mark all assertions in `type` used in both `assn1` and `assn2`
     908                static void markAssertions(
     909                        ast::AssertionSet & assn1, ast::AssertionSet & assn2,
     910                        const ast::ParameterizedType * type
     911                ) {
     912                        for ( const auto & tyvar : type->forall ) {
     913                                for ( const ast::DeclWithType * assert : tyvar->assertions ) {
     914                                        markAssertionSet( assn1, assert );
     915                                        markAssertionSet( assn2, assert );
     916                                }
     917                        }
     918                }
     919
     920        public:
     921                void previsit( const ast::FunctionType * func ) {
     922                        visit_children = false;
     923                        auto func2 = dynamic_cast< const ast::FunctionType * >( type2 );
     924                        if ( ! func2 ) return;
     925
     926                        if ( func->isVarArgs != func2->isVarArgs ) return;
     927                       
     928                        // Flatten the parameter lists for both functions so that tuple structure does not
     929                        // affect unification. Does not actually mutate function parameters.
     930                        auto params = flattenList( func->params, tenv );
     931                        auto params2 = flattenList( func2->params, tenv );
     932
     933                        // sizes don't have to match if ttypes are involved; need to be more precise w.r.t.
     934                        // where the ttype is to prevent errors
     935                        if (
     936                                ( params.size() != params2.size() || func->returns.size() != func2->returns.size() )
     937                                && ! func->isTtype()
     938                                && ! func2->isTtype()
     939                        ) return;
     940
     941                        if ( ! unifyDeclList( params, params2, tenv, need, have, open, symtab ) ) return;
     942                        if ( ! unifyDeclList(
     943                                func->returns, func2->returns, tenv, need, have, open, symtab ) ) return;
     944                       
     945                        markAssertions( have, need, func );
     946                        markAssertions( have, need, func2 );
     947
     948                        result = true;
     949                }
     950       
     951        private:
     952                template< typename RefType >
     953                const RefType * handleRefType( const RefType * inst, const ast::Type * other ) {
     954                        visit_children = false;
     955                        // check that the other type is compatible and named the same
     956                        auto otherInst = dynamic_cast< const RefType * >( other );
     957                        result = otherInst && inst->name == otherInst->name;
     958                        return otherInst;
     959                }
     960
     961                /// Creates a tuple type based on a list of TypeExpr
     962                template< typename Iter >
     963                static const ast::Type * tupleFromExprs(
     964                        const ast::TypeExpr * param, Iter & crnt, Iter end, ast::CV::Qualifiers qs
     965                ) {
     966                        std::vector< ast::ptr< ast::Type > > types;
     967                        do {
     968                                types.emplace_back( param->type );
     969
     970                                ++crnt;
     971                                if ( crnt == end ) break;
     972                                param = strict_dynamic_cast< const ast::TypeExpr * >( crnt->get() );
     973                        } while(true);
     974
     975                        return new ast::TupleType{ std::move(types), qs };
     976                }
     977
     978                template< typename RefType >
     979                void handleGenericRefType( const RefType * inst, const ast::Type * other ) {
     980                        // check that other type is compatible and named the same
     981                        const RefType * inst2 = handleRefType( inst, other );
     982                        if ( ! inst2 ) return;
     983                       
     984                        // check that parameters of types unify, if any
     985                        const std::vector< ast::ptr< ast::Expr > > & params = inst->params;
     986                        const std::vector< ast::ptr< ast::Expr > > & params2 = inst2->params;
     987
     988                        auto it = params.begin();
     989                        auto jt = params2.begin();
     990                        for ( ; it != params.end() && jt != params2.end(); ++it, ++jt ) {
     991                                auto param = strict_dynamic_cast< const ast::TypeExpr * >( it->get() );
     992                                auto param2 = strict_dynamic_cast< const ast::TypeExpr * >( jt->get() );
     993
     994                                ast::ptr< ast::Type > pty = param->type;
     995                                ast::ptr< ast::Type > pty2 = param2->type;
     996
     997                                bool isTuple = Tuples::isTtype( pty );
     998                                bool isTuple2 = Tuples::isTtype( pty2 );
     999
     1000                                if ( isTuple && isTuple2 ) {
     1001                                        ++it; ++jt;  // skip ttype parameters before break
     1002                                } else if ( isTuple ) {
     1003                                        // bundle remaining params into tuple
     1004                                        pty2 = tupleFromExprs( param2, jt, params2.end(), pty->qualifiers );
     1005                                        ++it;  // skip ttype parameter for break
     1006                                } else if ( isTuple2 ) {
     1007                                        // bundle remaining params into tuple
     1008                                        pty = tupleFromExprs( param, it, params.end(), pty2->qualifiers );
     1009                                        ++jt;  // skip ttype parameter for break
     1010                                }
     1011
     1012                                if ( ! unifyExact(
     1013                                                pty, pty2, tenv, need, have, open, WidenMode{ false, false }, symtab ) ) {
     1014                                        result = false;
     1015                                        return;
     1016                                }
     1017
     1018                                // ttype parameter should be last
     1019                                if ( isTuple || isTuple2 ) break;
     1020                        }
     1021                        result = it == params.end() && jt == params2.end();
     1022                }
     1023
     1024        public:
     1025                void previsit( const ast::StructInstType * aggrType ) {
     1026                        handleGenericRefType( aggrType, type2 );
     1027                }
     1028
     1029                void previsit( const ast::UnionInstType * aggrType ) {
     1030                        handleGenericRefType( aggrType, type2 );
     1031                }
     1032
     1033                void previsit( const ast::EnumInstType * aggrType ) {
     1034                        handleRefType( aggrType, type2 );
     1035                }
     1036
     1037                void previsit( const ast::TraitInstType * aggrType ) {
     1038                        handleRefType( aggrType, type2 );
     1039                }
     1040
     1041                void previsit( const ast::TypeInstType * typeInst ) {
     1042                        assert( open.find( typeInst->name ) == open.end() );
     1043                        handleRefType( typeInst, type2 );
     1044                }
     1045
     1046        private:
     1047                /// Creates a tuple type based on a list of Type
     1048                static ast::ptr< ast::Type > tupleFromTypes(
     1049                        const std::vector< ast::ptr< ast::Type > > & tys
     1050                ) {
     1051                        std::vector< ast::ptr< ast::Type > > out;
     1052                        for ( const ast::Type * ty : tys ) {
     1053                                // it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure
     1054                                // that this results in a flat tuple
     1055                                flatten( ty, out );
     1056                        }
     1057
     1058                        return { new ast::TupleType{ std::move(out) } };
     1059                }
     1060
     1061                static bool unifyList(
     1062                        const std::vector< ast::ptr< ast::Type > > & list1,
     1063                        const std::vector< ast::ptr< ast::Type > > & list2, ast::TypeEnvironment & env,
     1064                        ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
     1065                        const ast::SymbolTable & symtab
     1066                ) {
     1067                        auto crnt1 = list1.begin();
     1068                        auto crnt2 = list2.begin();
     1069                        while ( crnt1 != list1.end() && crnt2 != list2.end() ) {
     1070                                const ast::Type * t1 = *crnt1;
     1071                                const ast::Type * t2 = *crnt2;
     1072                                bool isTuple1 = Tuples::isTtype( t1 );
     1073                                bool isTuple2 = Tuples::isTtype( t2 );
     1074
     1075                                // assumes ttype must be last parameter
     1076                                if ( isTuple1 && ! isTuple2 ) {
     1077                                        // combine entirety of list2, then unify
     1078                                        return unifyExact(
     1079                                                t1, tupleFromTypes( list2 ), env, need, have, open,
     1080                                                WidenMode{ false, false }, symtab );
     1081                                } else if ( ! isTuple1 && isTuple2 ) {
     1082                                        // combine entirety of list1, then unify
     1083                                        return unifyExact(
     1084                                                tupleFromTypes( list1 ), t2, env, need, have, open,
     1085                                                WidenMode{ false, false }, symtab );
     1086                                }
     1087
     1088                                if ( ! unifyExact(
     1089                                        t1, t2, env, need, have, open, WidenMode{ false, false }, symtab )
     1090                                ) return false;
     1091
     1092                                ++crnt1; ++crnt2;
     1093                        }
     1094
     1095                        if ( crnt1 != list1.end() ) {
     1096                                // try unifying empty tuple type with ttype
     1097                                const ast::Type * t1 = *crnt1;
     1098                                if ( ! Tuples::isTtype( t1 ) ) return false;
     1099                                // xxx - this doesn't generate an empty tuple, contrary to comment; both ported
     1100                                // from Rob's code
     1101                                return unifyExact(
     1102                                                t1, tupleFromTypes( list2 ), env, need, have, open,
     1103                                                WidenMode{ false, false }, symtab );
     1104                        } else if ( crnt2 != list2.end() ) {
     1105                                // try unifying empty tuple with ttype
     1106                                const ast::Type * t2 = *crnt2;
     1107                                if ( ! Tuples::isTtype( t2 ) ) return false;
     1108                                // xxx - this doesn't generate an empty tuple, contrary to comment; both ported
     1109                                // from Rob's code
     1110                                return unifyExact(
     1111                                                tupleFromTypes( list1 ), t2, env, need, have, open,
     1112                                                WidenMode{ false, false }, symtab );
     1113                        }
     1114
     1115                        return true;
     1116                }
     1117
     1118        public:
     1119                void previsit( const ast::TupleType * tuple ) {
     1120                        visit_children = false;
     1121                        auto tuple2 = dynamic_cast< const ast::TupleType * >( type2 );
     1122                        if ( ! tuple2 ) return;
     1123
     1124                        ast::Pass<TtypeExpander_new> expander{ tenv };
     1125                        const ast::Type * flat = tuple->accept( expander );
     1126                        const ast::Type * flat2 = tuple2->accept( expander );
     1127
     1128                        auto types = flatten( flat );
     1129                        auto types2 = flatten( flat2 );
     1130
     1131                        result = unifyList( types, types2, tenv, need, have, open, symtab );
     1132                }
     1133
     1134                void previsit( const ast::VarArgsType * ) {
     1135                        visit_children = false;
     1136                        result = dynamic_cast< const ast::VarArgsType * >( type2 );
     1137                }
     1138
     1139                void previsit( const ast::ZeroType * ) {
     1140                        visit_children = false;
     1141                        result = dynamic_cast< const ast::ZeroType * >( type2 );
     1142                }
     1143
     1144                void previsit( const ast::OneType * ) {
     1145                        visit_children = false;
     1146                        result = dynamic_cast< const ast::OneType * >( type2 );
     1147                }       
     1148
     1149          private:
     1150                template< typename RefType > void handleRefType( RefType *inst, Type *other );
     1151                template< typename RefType > void handleGenericRefType( RefType *inst, Type *other );
     1152        };
     1153
     1154        bool unifyExact(
     1155                        const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env,
     1156                        ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
     1157                        WidenMode widen, const ast::SymbolTable & symtab
     1158        ) {
     1159                if ( type1->qualifiers != type2->qualifiers ) return false;
     1160
     1161                auto var1 = dynamic_cast< const ast::TypeInstType * >( type1 );
     1162                auto var2 = dynamic_cast< const ast::TypeInstType * >( type2 );
     1163                ast::OpenVarSet::const_iterator
     1164                        entry1 = var1 ? open.find( var1->name ) : open.end(),
     1165                        entry2 = var2 ? open.find( var2->name ) : open.end();
     1166                bool isopen1 = entry1 != open.end();
     1167                bool isopen2 = entry2 != open.end();
     1168
     1169                if ( isopen1 && isopen2 ) {
     1170                        if ( entry1->second.kind != entry2->second.kind ) return false;
     1171                        return env.bindVarToVar(
     1172                                var1, var2, ast::TypeDecl::Data{ entry1->second, entry2->second }, need, have,
     1173                                open, widen, symtab );
     1174                } else if ( isopen1 ) {
     1175                        return env.bindVar( var1, type2, entry1->second, need, have, open, widen, symtab );
     1176                } else if ( isopen2 ) {
     1177                        return env.bindVar( var2, type1, entry2->second, need, have, open, widen, symtab );
     1178                } else {
     1179                        ast::Pass<Unify_new> comparator{ type2, env, need, have, open, widen, symtab };
     1180                        type1->accept( comparator );
     1181                        return comparator.pass.result;
     1182                }
     1183        }
     1184
     1185        bool unifyInexact(
     1186                        ast::ptr<ast::Type> & type1, ast::ptr<ast::Type> & type2, ast::TypeEnvironment & env,
     1187                        ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
     1188                        WidenMode widen, const ast::SymbolTable & symtab, ast::ptr<ast::Type> & common
     1189        ) {
     1190                ast::CV::Qualifiers q1 = type1->qualifiers, q2 = type2->qualifiers;
     1191               
     1192                // force t1 and t2 to be cloned if their qualifiers must be stripped, so that type1 and
     1193                // type2 are left unchanged; calling convention forces type{1,2}->strong_ref >= 1
     1194                ast::ptr<ast::Type> t1{ type1 }, t2{ type2 };
     1195                clear_qualifiers( t1 );
     1196                clear_qualifiers( t2 );
     1197               
     1198                if ( unifyExact( t1, t2, env, need, have, open, widen, symtab ) ) {
     1199                        t1 = nullptr; t2 = nullptr; // release t1, t2 to avoid spurious clones
     1200
     1201                        // if exact unification on unqualified types, try to merge qualifiers
     1202                        if ( q1 == q2 || ( ( q1 > q2 || widen.first ) && ( q2 > q1 || widen.second ) ) ) {
     1203                                common.set_and_mutate( type1 )->qualifiers = q1 | q2;
     1204                                return true;
     1205                        } else {
     1206                                return false;
     1207                        }
     1208
     1209                } else if (( common = commonType( t1, t2, widen, symtab, env, open ) )) {
     1210                        t1 = nullptr; t2 = nullptr; // release t1, t2 to avoid spurious clones
     1211
     1212                        // no exact unification, but common type
     1213                        common.get_and_mutate()->qualifiers = q1 | q2;
     1214                        return true;
     1215                } else {
     1216                        return false;
     1217                }
     1218        }
     1219
    6751220        ast::ptr<ast::Type> extractResultType( const ast::FunctionType * func ) {
    6761221                if ( func->returns.empty() ) return new ast::VoidType{};
  • src/ResolvExpr/Unify.h

    r8d70648 rf474e91  
    1818#include <list>                   // for list
    1919
     20#include "AST/Node.hpp"             // for ptr
    2021#include "AST/TypeEnvironment.hpp"  // for TypeEnvironment, AssertionSet, OpenVarSet
    2122#include "Common/utility.h"       // for deleteAll
     
    3940        bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer, Type *&commonType );
    4041        bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer );
    41         bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer, Type *&common );
     42        bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer, Type *&common );
    4243
    4344        template< typename Iterator1, typename Iterator2 >
     
    6869        }
    6970
     71        bool unifyExact(
     72                const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env,
     73                ast::AssertionSet & need, ast::AssertionSet & have, ast::OpenVarSet & open,
     74                const ast::SymbolTable & symtab );
     75
    7076        bool unifyInexact(
    71                 const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env,
    72                 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & openVars,
    73                 WidenMode widenMode, const ast::SymbolTable & symtab, const ast::Type *& common );
     77                ast::ptr<ast::Type> & type1, ast::ptr<ast::Type> & type2, ast::TypeEnvironment & env,
     78                ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
     79                WidenMode widen, const ast::SymbolTable & symtab, ast::ptr<ast::Type> & common );
    7480
    7581} // namespace ResolvExpr
  • src/ResolvExpr/WidenMode.h

    r8d70648 rf474e91  
    1818namespace ResolvExpr {
    1919        struct WidenMode {
    20                 WidenMode( bool widenFirst, bool widenSecond ): widenFirst( widenFirst ), widenSecond( widenSecond ) {}
    21                 WidenMode &operator|=( const WidenMode &other ) { widenFirst |= other.widenFirst; widenSecond |= other.widenSecond; return *this; }
    22                 WidenMode &operator&=( const WidenMode &other ) { widenFirst &= other.widenFirst; widenSecond &= other.widenSecond; return *this; }
    23                 WidenMode operator|( const WidenMode &other ) { WidenMode newWM( *this ); newWM |= other; return newWM; }
    24                 WidenMode operator&( const WidenMode &other ) { WidenMode newWM( *this ); newWM &= other; return newWM; }
    25                 operator bool() { return widenFirst && widenSecond; }
     20                WidenMode( bool first, bool second ): first( first ), second( second ) {}
     21               
     22                WidenMode &operator|=( const WidenMode &other ) {
     23                        first |= other.first; second |= other.second; return *this;
     24                }
    2625
    27                 bool widenFirst : 1, widenSecond : 1;
     26                WidenMode &operator&=( const WidenMode &other ) {
     27                        first &= other.first; second &= other.second; return *this;
     28                }
     29
     30                WidenMode operator|( const WidenMode &other ) {
     31                        WidenMode newWM( *this ); newWM |= other; return newWM;
     32                }
     33
     34                WidenMode operator&( const WidenMode &other ) {
     35                        WidenMode newWM( *this ); newWM &= other; return newWM;
     36                }
     37               
     38                operator bool() { return first && second; }
     39
     40                bool first : 1, second : 1;
    2841        };
    2942} // namespace ResolvExpr
  • src/ResolvExpr/typeops.h

    r8d70648 rf474e91  
    1818#include <vector>
    1919
     20#include "Cost.h"
     21#include "TypeEnvironment.h"
     22#include "WidenMode.h"
    2023#include "AST/Fwd.hpp"
    2124#include "AST/Node.hpp"
     
    2629#include "SynTree/Type.h"
    2730#include "SymTab/Indexer.h"
    28 #include "Cost.h"
    29 #include "TypeEnvironment.h"
    3031
    3132namespace ResolvExpr {
     
    117118        // in CommonType.cc
    118119        Type * commonType( Type *type1, Type *type2, bool widenFirst, bool widenSecond, const SymTab::Indexer &indexer, TypeEnvironment &env, const OpenVarSet &openVars );
     120        const ast::Type * commonType(
     121                const ast::Type * type1, const ast::Type * type2, WidenMode widen,
     122                const ast::SymbolTable & symtab, ast::TypeEnvironment & env, const ast::OpenVarSet & open );
    119123
    120124        // in PolyCost.cc
     
    141145        const ast::Expr * referenceToRvalueConversion( const ast::Expr * expr, Cost & cost );
    142146
    143         // flatten tuple type into list of types
     147        /// flatten tuple type into list of types
    144148        template< typename OutputIterator >
    145149        void flatten( Type * type, OutputIterator out ) {
     
    152156                }
    153157        }
     158
     159        /// flatten tuple type into existing list of types
     160        static inline void flatten(
     161                const ast::Type * type, std::vector< ast::ptr< ast::Type > > & out
     162        ) {
     163                if ( auto tupleType = dynamic_cast< const ast::TupleType * >( type ) ) {       
     164                        for ( const ast::Type * t : tupleType->types ) {
     165                                flatten( t, out );
     166                        }
     167                } else {
     168                        out.emplace_back( type );
     169                }
     170        }
     171
     172        /// flatten tuple type into list of types
     173        static inline std::vector< ast::ptr< ast::Type > > flatten( const ast::Type * type ) {
     174                std::vector< ast::ptr< ast::Type > > out;
     175                out.reserve( type->size() );
     176                flatten( type, out );
     177                return out;
     178        }
    154179} // namespace ResolvExpr
    155180
Note: See TracChangeset for help on using the changeset viewer.