Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/ResolvExpr/Unify.cc

    rf474e91 rd76c588  
    1414//
    1515
    16 #include "Unify.h"
    17 
    1816#include <cassert>                  // for assertf, assert
    1917#include <iterator>                 // for back_insert_iterator, back_inserter
    … …  
    2523#include <vector>
    2624
    27 #include "AST/Decl.hpp"
    2825#include "AST/Node.hpp"
    29 #include "AST/Pass.hpp"
    3026#include "AST/Type.hpp"
    3127#include "AST/TypeEnvironment.hpp"
    … …  
    4137#include "Tuples/Tuples.h"          // for isTtype
    4238#include "TypeEnvironment.h"        // for EqvClass, AssertionSet, OpenVarSet
     39#include "Unify.h"
    4340#include "typeops.h"                // for flatten, occurs, commonType
    44 
    45 namespace ast {
    46         class SymbolTable;
    47 }
    4841
    4942namespace SymTab {
    … …  
    5548namespace ResolvExpr {
    5649
    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 );
     50        struct Unify : public WithShortCircuiting {
     51                Unify( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
    5952
    6053                bool get_result() const { return result; }
    … …  
    8881                AssertionSet &haveAssertions;
    8982                const OpenVarSet &openVars;
    90                 WidenMode widen;
     83                WidenMode widenMode;
    9184                const SymTab::Indexer &indexer;
    9285        };
    … …  
    9487        /// Attempts an inexact unification of type1 and type2.
    9588        /// Returns false if no such unification; if the types can be unified, sets common (unless they unify exactly and have identical type qualifiers)
    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 );
     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 );
    10391
    10492        bool typesCompatible( Type *first, Type *second, const SymTab::Indexer &indexer, const TypeEnvironment &env ) {
    … …  
    124112                        const ast::Type * first, const ast::Type * second, const ast::SymbolTable & symtab,
    125113                        const ast::TypeEnvironment & env ) {
    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 );
     114                #warning unimplemented
     115                assert((first, second, symtab, env, false));
     116                return false;
    139117        }
    140118
    … …  
    166144                        const ast::Type * first, const ast::Type * second, const ast::SymbolTable & symtab,
    167145                        const ast::TypeEnvironment & env ) {
    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 );
     146                #warning unimplemented
     147                assert((first, second, symtab, env, false));
     148                return false;
    180149        }
    181150
    … …  
    202171        }
    203172
    204         bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ) {
     173        bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
    205174#ifdef DEBUG
    206175                TypeEnvironment debugEnv( env );
    … …  
    229198                                result = env.bindVarToVar(
    230199                                        var1, var2, TypeDecl::Data{ entry1->second, entry2->second }, needAssertions,
    231                                         haveAssertions, openVars, widen, indexer );
     200                                        haveAssertions, openVars, widenMode, indexer );
    232201                        }
    233202                } else if ( isopen1 ) {
    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 );
     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 );
    237206                } else {
    238                         PassVisitor<Unify_old> comparator( type2, env, needAssertions, haveAssertions, openVars, widen, indexer );
     207                        PassVisitor<Unify> comparator( type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
    239208                        type1->accept( comparator );
    240209                        result = comparator.pass.get_result();
    … …  
    261230        }
    262231
    263         bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer, Type *&common ) {
     232        bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer, Type *&common ) {
    264233                Type::Qualifiers tq1 = type1->get_qualifiers(), tq2 = type2->get_qualifiers();
    265234                type1->get_qualifiers() = Type::Qualifiers();
    … …  
    273242                std::cerr << std::endl;
    274243#endif
    275                 if ( ! unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, widen, indexer ) ) {
     244                if ( ! unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer ) ) {
    276245#ifdef DEBUG
    277246                        std::cerr << "unifyInexact: no exact unification found" << std::endl;
    278247#endif
    279                         if ( ( common = commonType( type1, type2, widen.first, widen.second, indexer, env, openVars ) ) ) {
     248                        if ( ( common = commonType( type1, type2, widenMode.widenFirst, widenMode.widenSecond, indexer, env, openVars ) ) ) {
    280249                                common->get_qualifiers() = tq1 | tq2;
    281250#ifdef DEBUG
    … …  
    293262                } else {
    294263                        if ( tq1 != tq2 ) {
    295                                 if ( ( tq1 > tq2 || widen.first ) && ( tq2 > tq1 || widen.second ) ) {
     264                                if ( ( tq1 > tq2 || widenMode.widenFirst ) && ( tq2 > tq1 || widenMode.widenSecond ) ) {
    296265                                        common = type1->clone();
    297266                                        common->get_qualifiers() = tq1 | tq2;
    … …  
    311280        }
    312281
    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) {
     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) {
    318296                result = dynamic_cast< VoidType* >( type2 );
    319297        }
    320298
    321         void Unify_old::postvisit(BasicType *basicType) {
     299        void Unify::postvisit(BasicType *basicType) {
    322300                if ( BasicType *otherBasic = dynamic_cast< BasicType* >( type2 ) ) {
    323301                        result = basicType->get_kind() == otherBasic->get_kind();
    … …  
    347325        }
    348326
    349         void Unify_old::postvisit(PointerType *pointerType) {
     327        void Unify::postvisit(PointerType *pointerType) {
    350328                if ( PointerType *otherPointer = dynamic_cast< PointerType* >( type2 ) ) {
    351329                        result = unifyExact( pointerType->get_base(), otherPointer->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
    … …  
    355333        }
    356334
    357         void Unify_old::postvisit(ReferenceType *refType) {
     335        void Unify::postvisit(ReferenceType *refType) {
    358336                if ( ReferenceType *otherRef = dynamic_cast< ReferenceType* >( type2 ) ) {
    359337                        result = unifyExact( refType->get_base(), otherRef->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
    … …  
    363341        }
    364342
    365         void Unify_old::postvisit(ArrayType *arrayType) {
     343        void Unify::postvisit(ArrayType *arrayType) {
    366344                ArrayType *otherArray = dynamic_cast< ArrayType* >( type2 );
    367345                // to unify, array types must both be VLA or both not VLA
    … …  
    443421        /// If this isn't done then argument lists can have wildly different
    444422        /// size and structure, when they should be compatible.
    445         struct TtypeExpander_old : public WithShortCircuiting {
     423        struct TtypeExpander : public WithShortCircuiting {
    446424                TypeEnvironment & tenv;
    447                 TtypeExpander_old( TypeEnvironment & tenv ) : tenv( tenv ) {}
     425                TtypeExpander( TypeEnvironment & tenv ) : tenv( tenv ) {}
    448426                void premutate( TypeInstType * ) { visit_children = false; }
    449427                Type * postmutate( TypeInstType * typeInst ) {
    … …  
    464442                dst.clear();
    465443                for ( DeclarationWithType * dcl : src ) {
    466                         PassVisitor<TtypeExpander_old> expander( env );
     444                        PassVisitor<TtypeExpander> expander( env );
    467445                        dcl->acceptMutator( expander );
    468446                        std::list< Type * > types;
    … …  
    479457        }
    480458
    481         void Unify_old::postvisit(FunctionType *functionType) {
     459        void Unify::postvisit(FunctionType *functionType) {
    482460                FunctionType *otherFunction = dynamic_cast< FunctionType* >( type2 );
    483461                if ( otherFunction && functionType->get_isVarArgs() == otherFunction->get_isVarArgs() ) {
    … …  
    490468
    491469                        // sizes don't have to match if ttypes are involved; need to be more precise wrt where the ttype is to prevent errors
    492                         if (
    493                                         (flatFunc->parameters.size() == flatOther->parameters.size() &&
    494                                                 flatFunc->returnVals.size() == flatOther->returnVals.size())
    495                                         || flatFunc->isTtype()
    496                                         || flatOther->isTtype()
    497                         ) {
     470                        if ( (flatFunc->parameters.size() == flatOther->parameters.size() && flatFunc->returnVals.size() == flatOther->returnVals.size()) || flatFunc->isTtype() || flatOther->isTtype() ) {
    498471                                if ( unifyDeclList( flatFunc->parameters.begin(), flatFunc->parameters.end(), flatOther->parameters.begin(), flatOther->parameters.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
    499472                                        if ( unifyDeclList( flatFunc->returnVals.begin(), flatFunc->returnVals.end(), flatOther->returnVals.begin(), flatOther->returnVals.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
    … …  
    511484
    512485        template< typename RefType >
    513         void Unify_old::handleRefType( RefType *inst, Type *other ) {
     486        void Unify::handleRefType( RefType *inst, Type *other ) {
    514487                // check that other type is compatible and named the same
    515488                RefType *otherStruct = dynamic_cast< RefType* >( other );
    … …  
    518491
    519492        template< typename RefType >
    520         void Unify_old::handleGenericRefType( RefType *inst, Type *other ) {
     493        void Unify::handleGenericRefType( RefType *inst, Type *other ) {
    521494                // Check that other type is compatible and named the same
    522495                handleRefType( inst, other );
    … …  
    586559        }
    587560
    588         void Unify_old::postvisit(StructInstType *structInst) {
     561        void Unify::postvisit(StructInstType *structInst) {
    589562                handleGenericRefType( structInst, type2 );
    590563        }
    591564
    592         void Unify_old::postvisit(UnionInstType *unionInst) {
     565        void Unify::postvisit(UnionInstType *unionInst) {
    593566                handleGenericRefType( unionInst, type2 );
    594567        }
    595568
    596         void Unify_old::postvisit(EnumInstType *enumInst) {
     569        void Unify::postvisit(EnumInstType *enumInst) {
    597570                handleRefType( enumInst, type2 );
    598571        }
    599572
    600         void Unify_old::postvisit(TraitInstType *contextInst) {
     573        void Unify::postvisit(TraitInstType *contextInst) {
    601574                handleRefType( contextInst, type2 );
    602575        }
    603576
    604         void Unify_old::postvisit(TypeInstType *typeInst) {
     577        void Unify::postvisit(TypeInstType *typeInst) {
    605578                assert( openVars.find( typeInst->get_name() ) == openVars.end() );
    606579                TypeInstType *otherInst = dynamic_cast< TypeInstType* >( type2 );
    … …  
    657630        }
    658631
    659         void Unify_old::postvisit(TupleType *tupleType) {
     632        void Unify::postvisit(TupleType *tupleType) {
    660633                if ( TupleType *otherTuple = dynamic_cast< TupleType* >( type2 ) ) {
    661634                        std::unique_ptr<TupleType> flat1( tupleType->clone() );
    … …  
    663636                        std::list<Type *> types1, types2;
    664637
    665                         PassVisitor<TtypeExpander_old> expander( env );
     638                        PassVisitor<TtypeExpander> expander( env );
    666639                        flat1->acceptMutator( expander );
    667640                        flat2->acceptMutator( expander );
    … …  
    674647        }
    675648
    676         void Unify_old::postvisit( __attribute__((unused)) VarArgsType *varArgsType ) {
     649        void Unify::postvisit( __attribute__((unused)) VarArgsType *varArgsType ) {
    677650                result = dynamic_cast< VarArgsType* >( type2 );
    678651        }
    679652
    680         void Unify_old::postvisit( __attribute__((unused)) ZeroType *zeroType ) {
     653        void Unify::postvisit( __attribute__((unused)) ZeroType *zeroType ) {
    681654                result = dynamic_cast< ZeroType* >( type2 );
    682655        }
    683656
    684         void Unify_old::postvisit( __attribute__((unused)) OneType *oneType ) {
     657        void Unify::postvisit( __attribute__((unused)) OneType *oneType ) {
    685658                result = dynamic_cast< OneType* >( type2 );
    686659        }
    … …  
    700673        }
    701674
    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 
    1220675        ast::ptr<ast::Type> extractResultType( const ast::FunctionType * func ) {
    1221676                if ( func->returns.empty() ) return new ast::VoidType{};
Note: See TracChangeset for help on using the changeset viewer.