Ignore:
Timestamp:
Aug 27, 2018, 4:40:34 PM (7 years ago)
Author:
Rob Schluntz <rschlunt@…>
Branches:
ADT, arm-eh, ast-experimental, cleanup-dtors, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
b7c89aa
Parents:
f9feab8 (diff), 305581d (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' into cleanup-dtors

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/ResolvExpr/Unify.cc

    rf9feab8 r90152a4  
    99// Author           : Richard C. Bilson
    1010// Created On       : Sun May 17 12:27:10 2015
    11 // Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Mar 16 16:22:54 2017
    13 // Update Count     : 42
     11// Last Modified By : Aaron B. Moss
     12// Last Modified On : Mon Jun 18 11:58:00 2018
     13// Update Count     : 43
    1414//
    1515
    … …  
    2020#include <set>                    // for set
    2121#include <string>                 // for string, operator==, operator!=, bas...
    22 #include <utility>                // for pair
     22#include <utility>                // for pair, move
    2323
    2424#include "Common/PassVisitor.h"   // for PassVisitor
    … …  
    4444namespace ResolvExpr {
    4545
    46         class Unify : public Visitor {
    47           public:
     46        struct Unify : public WithShortCircuiting {
    4847                Unify( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
    4948
    5049                bool get_result() const { return result; }
     50
     51                void previsit( BaseSyntaxNode * ) { visit_children = false; }
     52
     53                void postvisit( VoidType * voidType );
     54                void postvisit( BasicType * basicType );
     55                void postvisit( PointerType * pointerType );
     56                void postvisit( ArrayType * arrayType );
     57                void postvisit( ReferenceType * refType );
     58                void postvisit( FunctionType * functionType );
     59                void postvisit( StructInstType * aggregateUseType );
     60                void postvisit( UnionInstType * aggregateUseType );
     61                void postvisit( EnumInstType * aggregateUseType );
     62                void postvisit( TraitInstType * aggregateUseType );
     63                void postvisit( TypeInstType * aggregateUseType );
     64                void postvisit( TupleType * tupleType );
     65                void postvisit( VarArgsType * varArgsType );
     66                void postvisit( ZeroType * zeroType );
     67                void postvisit( OneType * oneType );
     68
    5169          private:
    52                 virtual void visit(VoidType *voidType);
    53                 virtual void visit(BasicType *basicType);
    54                 virtual void visit(PointerType *pointerType);
    55                 virtual void visit(ArrayType *arrayType);
    56                 virtual void visit(ReferenceType *refType);
    57                 virtual void visit(FunctionType *functionType);
    58                 virtual void visit(StructInstType *aggregateUseType);
    59                 virtual void visit(UnionInstType *aggregateUseType);
    60                 virtual void visit(EnumInstType *aggregateUseType);
    61                 virtual void visit(TraitInstType *aggregateUseType);
    62                 virtual void visit(TypeInstType *aggregateUseType);
    63                 virtual void visit(TupleType *tupleType);
    64                 virtual void visit(VarArgsType *varArgsType);
    65                 virtual void visit(ZeroType *zeroType);
    66                 virtual void visit(OneType *oneType);
    67 
    6870                template< typename RefType > void handleRefType( RefType *inst, Type *other );
    6971                template< typename RefType > void handleGenericRefType( RefType *inst, Type *other );
    … …  
    127129        }
    128130
    129         bool isFtype( Type *type ) {
    130                 if ( dynamic_cast< FunctionType* >( type ) ) {
    131                         return true;
    132                 } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( type ) ) {
    133                         return typeInst->get_isFtype();
    134                 } // if
    135                 return false;
    136         }
    137 
    138         bool tyVarCompatible( const TypeDecl::Data & data, Type *type ) {
    139                 switch ( data.kind ) {
    140                   case TypeDecl::Dtype:
    141                         // to bind to an object type variable, the type must not be a function type.
    142                         // if the type variable is specified to be a complete type then the incoming
    143                         // type must also be complete
    144                         // xxx - should this also check that type is not a tuple type and that it's not a ttype?
    145                         return ! isFtype( type ) && (! data.isComplete || type->isComplete() );
    146                   case TypeDecl::Ftype:
    147                         return isFtype( type );
    148                   case TypeDecl::Ttype:
    149                         // ttype unifies with any tuple type
    150                         return dynamic_cast< TupleType * >( type ) || Tuples::isTtype( type );
    151                 } // switch
    152                 return false;
    153         }
    154 
    155         bool bindVar( TypeInstType *typeInst, Type *other, const TypeDecl::Data & data, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
    156                 // remove references from other, so that type variables can only bind to value types
    157                 other = other->stripReferences();
    158                 OpenVarSet::const_iterator tyvar = openVars.find( typeInst->get_name() );
    159                 assert( tyvar != openVars.end() );
    160                 if ( ! tyVarCompatible( tyvar->second, other ) ) {
    161                         return false;
    162                 } // if
    163                 if ( occurs( other, typeInst->get_name(), env ) ) {
    164                         return false;
    165                 } // if
    166                 EqvClass curClass;
    167                 if ( env.lookup( typeInst->get_name(), curClass ) ) {
    168                         if ( curClass.type ) {
    169                                 Type *common = 0;
    170                                 // attempt to unify equivalence class type (which has qualifiers stripped, so they must be restored) with the type to bind to
    171                                 std::unique_ptr< Type > newType( curClass.type->clone() );
    172                                 newType->get_qualifiers() = typeInst->get_qualifiers();
    173                                 if ( unifyInexact( newType.get(), other, env, needAssertions, haveAssertions, openVars, widenMode & WidenMode( curClass.allowWidening, true ), indexer, common ) ) {
    174                                         if ( common ) {
    175                                                 common->get_qualifiers() = Type::Qualifiers();
    176                                                 delete curClass.type;
    177                                                 curClass.type = common;
    178                                                 env.add( curClass );
    179                                         } // if
    180                                         return true;
    181                                 } else {
    182                                         return false;
    183                                 } // if
    184                         } else {
    185                                 curClass.type = other->clone();
    186                                 curClass.type->get_qualifiers() = Type::Qualifiers();
    187                                 curClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond;
    188                                 env.add( curClass );
    189                         } // if
    190                 } else {
    191                         EqvClass newClass;
    192                         newClass.vars.insert( typeInst->get_name() );
    193                         newClass.type = other->clone();
    194                         newClass.type->get_qualifiers() = Type::Qualifiers();
    195                         newClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond;
    196                         newClass.data = data;
    197                         env.add( newClass );
    198                 } // if
    199                 return true;
    200         }
    201 
    202         bool bindVarToVar( TypeInstType *var1, TypeInstType *var2, const TypeDecl::Data & data, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
    203                 bool result = true;
    204                 EqvClass class1, class2;
    205                 bool hasClass1 = false, hasClass2 = false;
    206                 bool widen1 = false, widen2 = false;
    207                 Type *type1 = 0, *type2 = 0;
    208 
    209                 if ( env.lookup( var1->get_name(), class1 ) ) {
    210                         hasClass1 = true;
    211                         if ( class1.type ) {
    212                                 if ( occurs( class1.type, var2->get_name(), env ) ) {
    213                                         return false;
    214                                 } // if
    215                                 type1 = class1.type->clone();
    216                         } // if
    217                         widen1 = widenMode.widenFirst && class1.allowWidening;
    218                 } // if
    219                 if ( env.lookup( var2->get_name(), class2 ) ) {
    220                         hasClass2 = true;
    221                         if ( class2.type ) {
    222                                 if ( occurs( class2.type, var1->get_name(), env ) ) {
    223                                         return false;
    224                                 } // if
    225                                 type2 = class2.type->clone();
    226                         } // if
    227                         widen2 = widenMode.widenSecond && class2.allowWidening;
    228                 } // if
    229 
    230                 if ( type1 && type2 ) {
    231 //    std::cerr << "has type1 && type2" << std::endl;
    232                         WidenMode newWidenMode ( widen1, widen2 );
    233                         Type *common = 0;
    234                         if ( unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, newWidenMode, indexer, common ) ) {
    235                                 class1.vars.insert( class2.vars.begin(), class2.vars.end() );
    236                                 class1.allowWidening = widen1 && widen2;
    237                                 if ( common ) {
    238                                         common->get_qualifiers() = Type::Qualifiers();
    239                                         delete class1.type;
    240                                         class1.type = common;
    241                                 } // if
    242                                 env.add( class1 );
    243                         } else {
    244                                 result = false;
    245                         } // if
    246                 } else if ( hasClass1 && hasClass2 ) {
    247                         if ( type1 ) {
    248                                 class1.vars.insert( class2.vars.begin(), class2.vars.end() );
    249                                 class1.allowWidening = widen1;
    250                                 env.add( class1 );
    251                         } else {
    252                                 class2.vars.insert( class1.vars.begin(), class1.vars.end() );
    253                                 class2.allowWidening = widen2;
    254                                 env.add( class2 );
    255                         } // if
    256                 } else if ( hasClass1 ) {
    257                         class1.vars.insert( var2->get_name() );
    258                         class1.allowWidening = widen1;
    259                         env.add( class1 );
    260                 } else if ( hasClass2 ) {
    261                         class2.vars.insert( var1->get_name() );
    262                         class2.allowWidening = widen2;
    263                         env.add( class2 );
    264                 } else {
    265                         EqvClass newClass;
    266                         newClass.vars.insert( var1->get_name() );
    267                         newClass.vars.insert( var2->get_name() );
    268                         newClass.allowWidening = widen1 && widen2;
    269                         newClass.data = data;
    270                         env.add( newClass );
    271                 } // if
    272                 delete type1;
    273                 delete type2;
    274                 return result;
    275         }
    276 
    277131        bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
    278132                OpenVarSet closedVars;
    … …  
    319173
    320174                if ( isopen1 && isopen2 && entry1->second == entry2->second ) {
    321                         result = bindVarToVar( var1, var2, entry1->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
     175                        result = env.bindVarToVar( var1, var2, entry1->second, needAssertions, haveAssertions, openVars, widenMode, indexer );
    322176                } else if ( isopen1 ) {
    323                         result = bindVar( var1, type2, entry1->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
    324                 } else if ( isopen2 ) {
    325                         result = bindVar( var2, type1, entry2->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
     177                        result = env.bindVar( var1, type2, entry1->second, needAssertions, haveAssertions, openVars, widenMode, indexer );
     178                } else if ( isopen2 ) { // TODO: swap widenMode values in call, since type positions are flipped?
     179                        result = env.bindVar( var2, type1, entry2->second, needAssertions, haveAssertions, openVars, widenMode, indexer );
    326180                } else {
    327                         Unify comparator( type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
     181                        PassVisitor<Unify> comparator( type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
    328182                        type1->accept( comparator );
    329                         result = comparator.get_result();
     183                        result = comparator.pass.get_result();
    330184                } // if
    331185#ifdef DEBUG
    … …  
    404258        }
    405259
    406         void Unify::visit( __attribute__((unused)) VoidType *voidType) {
     260        void Unify::postvisit( __attribute__((unused)) VoidType *voidType) {
    407261                result = dynamic_cast< VoidType* >( type2 );
    408262        }
    409263
    410         void Unify::visit(BasicType *basicType) {
     264        void Unify::postvisit(BasicType *basicType) {
    411265                if ( BasicType *otherBasic = dynamic_cast< BasicType* >( type2 ) ) {
    412266                        result = basicType->get_kind() == otherBasic->get_kind();
    … …  
    436290        }
    437291
    438         void Unify::visit(PointerType *pointerType) {
     292        void Unify::postvisit(PointerType *pointerType) {
    439293                if ( PointerType *otherPointer = dynamic_cast< PointerType* >( type2 ) ) {
    440294                        result = unifyExact( pointerType->get_base(), otherPointer->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
    … …  
    444298        }
    445299
    446         void Unify::visit(ReferenceType *refType) {
     300        void Unify::postvisit(ReferenceType *refType) {
    447301                if ( ReferenceType *otherRef = dynamic_cast< ReferenceType* >( type2 ) ) {
    448302                        result = unifyExact( refType->get_base(), otherRef->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
    … …  
    452306        }
    453307
    454         void Unify::visit(ArrayType *arrayType) {
     308        void Unify::postvisit(ArrayType *arrayType) {
    455309                ArrayType *otherArray = dynamic_cast< ArrayType* >( type2 );
    456310                // to unify, array types must both be VLA or both not VLA
    … …  
    537391                void premutate( TypeInstType * ) { visit_children = false; }
    538392                Type * postmutate( TypeInstType * typeInst ) {
    539                         EqvClass eqvClass;
    540                         if ( tenv.lookup( typeInst->get_name(), eqvClass ) ) {
    541                                 if ( eqvClass.data.kind == TypeDecl::Ttype ) {
    542                                         // expand ttype parameter into its actual type
    543                                         if ( eqvClass.type ) {
    544                                                 delete typeInst;
    545                                                 return eqvClass.type->clone();
    546                                         }
     393                        if ( const EqvClass *eqvClass = tenv.lookup( typeInst->get_name() ) ) {
     394                                // expand ttype parameter into its actual type
     395                                if ( eqvClass->data.kind == TypeDecl::Ttype && eqvClass->type ) {
     396                                        delete typeInst;
     397                                        return eqvClass->type->clone();
    547398                                }
    548399                        }
    … …  
    561412                        flatten( dcl->get_type(), back_inserter( types ) );
    562413                        for ( Type * t : types ) {
     414                                // outermost const, volatile, _Atomic qualifiers in parameters should not play a role in the unification of function types, since they do not determine whether a function is callable.
     415                                // Note: MUST consider at least mutex qualifier, since functions can be overloaded on outermost mutex and a mutex function has different requirements than a non-mutex function.
     416                                t->get_qualifiers() -= Type::Qualifiers(Type::Const | Type::Volatile | Type::Atomic);
     417
    563418                                dst.push_back( new ObjectDecl( "", Type::StorageClasses(), LinkageSpec::C, nullptr, t, nullptr ) );
    564419                        }
    … …  
    567422        }
    568423
    569         void Unify::visit(FunctionType *functionType) {
     424        void Unify::postvisit(FunctionType *functionType) {
    570425                FunctionType *otherFunction = dynamic_cast< FunctionType* >( type2 );
    571426                if ( otherFunction && functionType->get_isVarArgs() == otherFunction->get_isVarArgs() ) {
    … …  
    578433
    579434                        // sizes don't have to match if ttypes are involved; need to be more precise wrt where the ttype is to prevent errors
    580                         if ( (flatFunc->get_parameters().size() == flatOther->get_parameters().size() && flatFunc->get_returnVals().size() == flatOther->get_returnVals().size()) || flatFunc->isTtype() || flatOther->isTtype() ) {
    581                                 if ( unifyDeclList( flatFunc->get_parameters().begin(), flatFunc->get_parameters().end(), flatOther->get_parameters().begin(), flatOther->get_parameters().end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
    582                                         if ( unifyDeclList( flatFunc->get_returnVals().begin(), flatFunc->get_returnVals().end(), flatOther->get_returnVals().begin(), flatOther->get_returnVals().end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
     435                        if ( (flatFunc->parameters.size() == flatOther->parameters.size() && flatFunc->returnVals.size() == flatOther->returnVals.size()) || flatFunc->isTtype() || flatOther->isTtype() ) {
     436                                if ( unifyDeclList( flatFunc->parameters.begin(), flatFunc->parameters.end(), flatOther->parameters.begin(), flatOther->parameters.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
     437                                        if ( unifyDeclList( flatFunc->returnVals.begin(), flatFunc->returnVals.end(), flatOther->returnVals.begin(), flatOther->returnVals.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
    583438
    584439                                                // the original types must be used in mark assertions, since pointer comparisons are used
    … …  
    597452                // check that other type is compatible and named the same
    598453                RefType *otherStruct = dynamic_cast< RefType* >( other );
    599                 result = otherStruct && inst->get_name() == otherStruct->get_name();
     454                result = otherStruct && inst->name == otherStruct->name;
    600455        }
    601456
    … …  
    606461                if ( ! result ) return;
    607462                // Check that parameters of types unify, if any
    608                 std::list< Expression* > params = inst->get_parameters();
    609                 std::list< Expression* > otherParams = ((RefType*)other)->get_parameters();
     463                std::list< Expression* > params = inst->parameters;
     464                std::list< Expression* > otherParams = ((RefType*)other)->parameters;
    610465
    611466                std::list< Expression* >::const_iterator it = params.begin(), jt = otherParams.begin();
    … …  
    669524        }
    670525
    671         void Unify::visit(StructInstType *structInst) {
     526        void Unify::postvisit(StructInstType *structInst) {
    672527                handleGenericRefType( structInst, type2 );
    673528        }
    674529
    675         void Unify::visit(UnionInstType *unionInst) {
     530        void Unify::postvisit(UnionInstType *unionInst) {
    676531                handleGenericRefType( unionInst, type2 );
    677532        }
    678533
    679         void Unify::visit(EnumInstType *enumInst) {
     534        void Unify::postvisit(EnumInstType *enumInst) {
    680535                handleRefType( enumInst, type2 );
    681536        }
    682537
    683         void Unify::visit(TraitInstType *contextInst) {
     538        void Unify::postvisit(TraitInstType *contextInst) {
    684539                handleRefType( contextInst, type2 );
    685540        }
    686541
    687         void Unify::visit(TypeInstType *typeInst) {
     542        void Unify::postvisit(TypeInstType *typeInst) {
    688543                assert( openVars.find( typeInst->get_name() ) == openVars.end() );
    689544                TypeInstType *otherInst = dynamic_cast< TypeInstType* >( type2 );
    … …  
    740595        }
    741596
    742         void Unify::visit(TupleType *tupleType) {
     597        void Unify::postvisit(TupleType *tupleType) {
    743598                if ( TupleType *otherTuple = dynamic_cast< TupleType* >( type2 ) ) {
    744599                        std::unique_ptr<TupleType> flat1( tupleType->clone() );
    … …  
    757612        }
    758613
    759         void Unify::visit( __attribute__((unused)) VarArgsType *varArgsType ) {
     614        void Unify::postvisit( __attribute__((unused)) VarArgsType *varArgsType ) {
    760615                result = dynamic_cast< VarArgsType* >( type2 );
    761616        }
    762617
    763         void Unify::visit( __attribute__((unused)) ZeroType *zeroType ) {
     618        void Unify::postvisit( __attribute__((unused)) ZeroType *zeroType ) {
    764619                result = dynamic_cast< ZeroType* >( type2 );
    765620        }
    766621
    767         void Unify::visit( __attribute__((unused)) OneType *oneType ) {
     622        void Unify::postvisit( __attribute__((unused)) OneType *oneType ) {
    768623                result = dynamic_cast< OneType* >( type2 );
    769624        }
Note: See TracChangeset for help on using the changeset viewer.