Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/ResolvExpr/Unify.cc

    rd76c588 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{};
Note: See TracChangeset for help on using the changeset viewer.