Changeset 5a3ac84


Ignore:
Timestamp:
Mar 15, 2017, 5:01:18 PM (5 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, resolv-new, with_gc
Children:
9b443c7f
Parents:
17df48e
Message:

Fixed Box(T*) generic instantiation bug

Location:
src/GenPoly
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • src/GenPoly/Box.cc

    r17df48e r5a3ac84  
    381381                // calculate struct layout in function body
    382382
    383                 // initialize size and alignment to 0 and 1 (will have at least one member to re-edit size
     383                // initialize size and alignment to 0 and 1 (will have at least one member to re-edit size)
    384384                addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( sizeParam ), new ConstantExpr( Constant( sizeAlignType->clone(), "0" ) ) ) );
    385385                addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( alignParam ), new ConstantExpr( Constant( sizeAlignType->clone(), "1" ) ) ) );
     
    18521852
    18531853                        DeclClass *ret = static_cast< DeclClass *>( Mutator::mutate( decl ) );
    1854                         ScrubTyVars::scrub( decl, scopeTyVars );
     1854                        // ScrubTyVars::scrub( decl, scopeTyVars );
     1855                        ScrubTyVars::scrubAll( decl );
    18551856
    18561857                        scopeTyVars.endScope();
  • src/GenPoly/GenPoly.cc

    r17df48e r5a3ac84  
    1515
    1616#include "GenPoly.h"
     17#include "assert.h"
    1718
    1819#include "SynTree/Expression.h"
    1920#include "SynTree/Type.h"
     21#include "ResolvExpr/typeops.h"
    2022
    2123#include <iostream>
     24#include <iterator>
     25#include <list>
     26#include <typeindex>
     27#include <typeinfo>
     28#include <vector>
    2229using namespace std;
    2330
     
    3845                        for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
    3946                                TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param );
    40                                 assert(paramType && "Aggregate parameters should be type expressions");
     47                                assertf(paramType, "Aggregate parameters should be type expressions");
    4148                                if ( isPolyType( paramType->get_type(), tyVars, env ) ) return true;
    4249                        }
     
    4855                        for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
    4956                                TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param );
    50                                 assert(paramType && "Aggregate parameters should be type expressions");
     57                                assertf(paramType, "Aggregate parameters should be type expressions");
    5158                                if ( isDynType( paramType->get_type(), tyVars, env ) ) return true;
     59                        }
     60                        return false;
     61                }
     62
     63                /// Checks a parameter list for inclusion of polymorphic parameters; will substitute according to env if present
     64                bool includesPolyParams( std::list< Expression* >& params, const TypeSubstitution *env ) {
     65                        for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
     66                                TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param );
     67                                assertf(paramType, "Aggregate parameters should be type expressions");
     68                                if ( includesPolyType( paramType->get_type(), env ) ) return true;
     69                        }
     70                        return false;
     71                }
     72
     73                /// Checks a parameter list for inclusion of polymorphic parameters from tyVars; will substitute according to env if present
     74                bool includesPolyParams( std::list< Expression* >& params, const TyVarMap &tyVars, const TypeSubstitution *env ) {
     75                        for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
     76                                TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param );
     77                                assertf(paramType, "Aggregate parameters should be type expressions");
     78                                if ( includesPolyType( paramType->get_type(), tyVars, env ) ) return true;
    5279                        }
    5380                        return false;
     
    187214
    188215                return isPolyType( type, tyVars, env );
     216        }
     217
     218        bool includesPolyType( Type *type, const TypeSubstitution *env ) {
     219                type = replaceTypeInst( type, env );
     220
     221                if ( dynamic_cast< TypeInstType * >( type ) ) {
     222                        return true;
     223                } else if ( PointerType *pointerType = dynamic_cast< PointerType* >( type ) ) {
     224                        if ( includesPolyType( pointerType->get_base(), env ) ) return true;
     225                } else if ( StructInstType *structType = dynamic_cast< StructInstType* >( type ) ) {
     226                        if ( includesPolyParams( structType->get_parameters(), env ) ) return true;
     227                } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( type ) ) {
     228                        if ( includesPolyParams( unionType->get_parameters(), env ) ) return true;
     229                }
     230                return false;
     231        }
     232
     233        bool includesPolyType( Type *type, const TyVarMap &tyVars, const TypeSubstitution *env ) {
     234                type = replaceTypeInst( type, env );
     235
     236                if ( TypeInstType *typeInstType = dynamic_cast< TypeInstType * >( type ) ) {
     237                        if ( tyVars.find( typeInstType->get_name() ) != tyVars.end() ) {
     238                                return true;
     239                        }
     240                } else if ( PointerType *pointerType = dynamic_cast< PointerType* >( type ) ) {
     241                        if ( includesPolyType( pointerType->get_base(), tyVars, env ) ) return true;
     242                } else if ( StructInstType *structType = dynamic_cast< StructInstType* >( type ) ) {
     243                        if ( includesPolyParams( structType->get_parameters(), tyVars, env ) ) return true;
     244                } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( type ) ) {
     245                        if ( includesPolyParams( unionType->get_parameters(), tyVars, env ) ) return true;
     246                }
     247                return false;
    189248        }
    190249
     
    237296        }
    238297
     298        namespace {
     299                /// Checks if is a pointer to D
     300                template<typename D, typename B>
     301                bool is( const B* p ) { return type_index{typeid(D)} == type_index{typeid(*p)}; }
     302
     303                /// Converts to a pointer to D without checking for safety
     304                template<typename D, typename B>
     305                inline D* as( B* p ) { return reinterpret_cast<D*>(p); }
     306
     307                /// Flattens a declaration list
     308                template<typename Output>
     309                void flattenList( list< DeclarationWithType* > src, Output out ) {
     310                        for ( DeclarationWithType* decl : src ) {
     311                                ResolvExpr::flatten( decl->get_type(), out );
     312                        }
     313                }
     314
     315                /// Flattens a list of types
     316                template<typename Output>
     317                void flattenList( list< Type* > src, Output out ) {
     318                        for ( Type* ty : src ) {
     319                                ResolvExpr::flatten( ty, out );
     320                        }
     321                }
     322
     323                /// Checks if two lists of parameters are equal up to polymorphic substitution.
     324                bool paramListsPolyCompatible( const list< Expression* >& aparams, const list< Expression* >& bparams ) {
     325                        if ( aparams.size() != bparams.size() ) return false;
     326
     327                        for ( list< Expression* >::const_iterator at = aparams.begin(), bt = bparams.begin();
     328                                        at != aparams.end(); ++at, ++bt ) {
     329                                TypeExpr *aparam = dynamic_cast< TypeExpr* >(*at);
     330                                assertf(aparam, "Aggregate parameters should be type expressions");
     331                                TypeExpr *bparam = dynamic_cast< TypeExpr* >(*bt);
     332                                assertf(bparam, "Aggregate parameters should be type expressions");
     333
     334                                // xxx - might need to let VoidType be a wildcard here too; could have some voids
     335                                // stuffed in for dtype-statics.
     336                                // if ( is<VoidType>( aparam->get_type() ) || is<VoidType>( bparam->get_type() ) ) continue;
     337                                if ( ! typesPolyCompatible( aparam->get_type(), bparam->get_type() ) ) return false;
     338                        }
     339                       
     340                        return true;
     341                }
     342        }
     343
     344        bool typesPolyCompatible( Type *a, Type *b ) {
     345                type_index aid{ typeid(*a) };
     346                // polymorphic types always match
     347                if ( aid == type_index{typeid(TypeInstType)} ) return true;
     348               
     349                type_index bid{ typeid(*b) };
     350                // polymorphic types always match
     351                if ( bid == type_index{typeid(TypeInstType)} ) return true;
     352               
     353                // can't match otherwise if different types
     354                if ( aid != bid ) return false;
     355
     356                // recurse through type structure (conditions borrowed from Unify.cc)
     357                if ( aid == type_index{typeid(BasicType)} ) {
     358                        return as<BasicType>(a)->get_kind() == as<BasicType>(b)->get_kind();
     359                } else if ( aid == type_index{typeid(PointerType)} ) {
     360                        PointerType *ap = as<PointerType>(a), *bp = as<PointerType>(b);
     361
     362                        // void pointers should match any other pointer type
     363                        return is<VoidType>( ap->get_base() ) || is<VoidType>( bp->get_base() )
     364                                || typesPolyCompatible( ap->get_base(), bp->get_base() );
     365                } else if ( aid == type_index{typeid(ArrayType)} ) {
     366                        ArrayType *aa = as<ArrayType>(a), *ba = as<ArrayType>(b);
     367
     368                        if ( aa->get_isVarLen() ) {
     369                                if ( ! ba->get_isVarLen() ) return false;
     370                        } else {
     371                                if ( ba->get_isVarLen() ) return false;
     372
     373                                ConstantExpr *ad = dynamic_cast<ConstantExpr*>( aa->get_dimension() );
     374                                ConstantExpr *bd = dynamic_cast<ConstantExpr*>( ba->get_dimension() );
     375                                if ( ad && bd
     376                                                && ad->get_constant()->get_value() != bd->get_constant()->get_value() )
     377                                        return false;
     378                        }
     379
     380                        return typesPolyCompatible( aa->get_base(), ba->get_base() );
     381                } else if ( aid == type_index{typeid(FunctionType)} ) {
     382                        FunctionType *af = as<FunctionType>(a), *bf = as<FunctionType>(b);
     383
     384                        vector<Type*> aparams, bparams;
     385                        flattenList( af->get_parameters(), back_inserter( aparams ) );
     386                        flattenList( bf->get_parameters(), back_inserter( bparams ) );
     387                        if ( aparams.size() != bparams.size() ) return false;
     388
     389                        vector<Type*> areturns, breturns;
     390                        flattenList( af->get_returnVals(), back_inserter( areturns ) );
     391                        flattenList( bf->get_returnVals(), back_inserter( breturns ) );
     392                        if ( areturns.size() != breturns.size() ) return false;
     393
     394                        for ( unsigned i = 0; i < aparams.size(); ++i ) {
     395                                if ( ! typesPolyCompatible( aparams[i], bparams[i] ) ) return false;
     396                        }
     397                        for ( unsigned i = 0; i < areturns.size(); ++i ) {
     398                                if ( ! typesPolyCompatible( areturns[i], breturns[i] ) ) return false;
     399                        }
     400                        return true;
     401                } else if ( aid == type_index{typeid(StructInstType)} ) {
     402                        StructInstType *aa = as<StructInstType>(a), *ba = as<StructInstType>(b);
     403
     404                        if ( aa->get_name() != ba->get_name() ) return false;
     405                        return paramListsPolyCompatible( aa->get_parameters(), ba->get_parameters() );
     406                } else if ( aid == type_index{typeid(UnionInstType)} ) {
     407                        UnionInstType *aa = as<UnionInstType>(a), *ba = as<UnionInstType>(b);
     408
     409                        if ( aa->get_name() != ba->get_name() ) return false;
     410                        return paramListsPolyCompatible( aa->get_parameters(), ba->get_parameters() );
     411                } else if ( aid == type_index{typeid(EnumInstType)} ) {
     412                        return as<EnumInstType>(a)->get_name() == as<EnumInstType>(b)->get_name();
     413                } else if ( aid == type_index{typeid(TraitInstType)} ) {
     414                        return as<TraitInstType>(a)->get_name() == as<TraitInstType>(b)->get_name();
     415                } else if ( aid == type_index{typeid(TupleType)} ) {
     416                        TupleType *at = as<TupleType>(a), *bt = as<TupleType>(b);
     417
     418                        vector<Type*> atypes, btypes;
     419                        flattenList( at->get_types(), back_inserter( atypes ) );
     420                        flattenList( bt->get_types(), back_inserter( btypes ) );
     421                        if ( atypes.size() != btypes.size() ) return false;
     422
     423                        for ( unsigned i = 0; i < atypes.size(); ++i ) {
     424                                if ( ! typesPolyCompatible( atypes[i], btypes[i] ) ) return false;
     425                        }
     426                        return true;
     427                } else return true; // VoidType, VarArgsType, ZeroType & OneType just need the same type
     428        }
     429
    239430        void addToTyVarMap( TypeDecl * tyVar, TyVarMap &tyVarMap ) {
    240431                tyVarMap[ tyVar->get_name() ] = TypeDecl::Data{ tyVar };
  • src/GenPoly/GenPoly.h

    r17df48e r5a3ac84  
    6767        Type *hasPolyBase( Type *type, const TyVarMap &tyVars, int *levels = 0, const TypeSubstitution *env = 0 );
    6868
     69        /// true iff this type or some base of this type after dereferencing pointers is either polymorphic or a generic type with at least one
     70        /// polymorphic parameter; will look up substitution in env if provided.
     71        bool includesPolyType( Type *type, const TypeSubstitution *env = 0 );
     72
     73        /// true iff this type or some base of this type after dereferencing pointers is either polymorphic in tyVars, or a generic type with
     74        /// at least one polymorphic parameter in tyVars; will look up substitution in env if provided.
     75        bool includesPolyType( Type *type, const TyVarMap &tyVars, const TypeSubstitution *env = 0 );
     76
    6977        /// Returns a pointer to the base FunctionType if ty is the type of a function (or pointer to one), NULL otherwise
    7078        FunctionType *getFunctionType( Type *ty );
     
    7381        /// N will be stored in levels, if provided
    7482        VariableExpr *getBaseVar( Expression *expr, int *levels = 0 );
     83
     84        /// true iff types are structurally identical, where TypeInstType's match any type.
     85        bool typesPolyCompatible( Type *aty, Type *bty );
    7586
    7687        /// Adds the type variable `tyVar` to `tyVarMap`
  • src/GenPoly/InstantiateGeneric.cc

    r17df48e r5a3ac84  
    1616#include <cassert>
    1717#include <list>
     18#include <unordered_map>
    1819#include <utility>
    1920#include <vector>
    20 #include <unordered_map>
    2121
    2222#include "InstantiateGeneric.h"
     
    2525#include "GenPoly.h"
    2626#include "ScopedSet.h"
     27#include "ScrubTyVars.h"
    2728#include "PolyMutator.h"
    2829
     
    7778                        if ( params.size() != that.params.size() ) return false;
    7879
    79                         SymTab::Indexer dummy;
    8080                        for ( std::list< Type* >::const_iterator it = params.begin(), jt = that.params.begin(); it != params.end(); ++it, ++jt ) {
    81                                 if ( ! ResolvExpr::typesCompatible( *it, *jt, dummy ) ) return false;
     81                                if ( ! typesPolyCompatible( *it, *jt ) ) return false;
    8282                        }
    8383                        return true;
     
    227227                        if ( (*baseParam)->isComplete() ) {
    228228                                // substitute parameter for complete (otype or sized dtype) type
    229                                 int pointerLevels = 0;
    230                                 if ( hasPolyBase( paramType->get_type(), &pointerLevels ) && pointerLevels > 0 ) {
    231                                         // Make a void* with equivalent nesting
    232                                         Type* voidPtr = new VoidType( Type::Qualifiers() );
    233                                         while ( pointerLevels > 0 ) {
    234                                                 // Just about data layout, so qualifiers *shouldn't* matter
    235                                                 voidPtr = new PointerType( Type::Qualifiers(), voidPtr );
    236                                                 --pointerLevels;
    237                                         }
    238                                         out.push_back( new TypeExpr( voidPtr ) );
    239                                         // this type is still dtype-static, no change to gt
     229                                if ( isPolyType( paramType->get_type() ) ) {
     230                                        // substitute polymorphic parameter type in to generic type
     231                                        out.push_back( paramType->clone() );
     232                                        gt = genericType::dynamic;
    240233                                } else {
    241                                         // Just clone parameter type
    242                                         out.push_back( paramType->clone() );
    243                                         // make the struct concrete or dynamic depending on the parameter
    244                                         gt |= isPolyType( paramType->get_type() ) ? genericType::dynamic : genericType::concrete;
     234                                        // normalize possibly dtype-static parameter type
     235                                        out.push_back( new TypeExpr{
     236                                                ScrubTyVars::scrubAll( paramType->get_type()->clone() ) } );
     237                                        gt |= genericType::concrete;
    245238                                }
    246239                        } else switch ( (*baseParam)->get_kind() ) {
     
    373366                                concDecl = new StructDecl( typeNamer.newName( inst->get_name() ) );
    374367                                concDecl->set_body( inst->get_baseStruct()->has_body() );
    375                                 substituteMembers( inst->get_baseStruct()->get_members(), *inst->get_baseParameters(), typeSubs,        concDecl->get_members() );
     368                                substituteMembers( inst->get_baseStruct()->get_members(), *inst->get_baseParameters(), typeSubs, concDecl->get_members() );
    376369                                DeclMutator::addDeclaration( concDecl );
    377370                                insert( inst, typeSubs, concDecl );
  • src/GenPoly/ScrubTyVars.cc

    r17df48e r5a3ac84  
    2626namespace GenPoly {
    2727        Type * ScrubTyVars::mutate( TypeInstType *typeInst ) {
    28                 TyVarMap::const_iterator tyVar = tyVars.find( typeInst->get_name() );
    29                 if ( tyVar != tyVars.end() ) {
     28                if ( ! tyVars ) {
     29                        if ( typeInst->get_isFtype() ) {
     30                                delete typeInst;
     31                                return new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) );
     32                        } else {
     33                                PointerType *ret = new PointerType( Type::Qualifiers(), new VoidType( typeInst->get_qualifiers() ) );
     34                                delete typeInst;
     35                                return ret;
     36                        }
     37                }
     38
     39                TyVarMap::const_iterator tyVar = tyVars->find( typeInst->get_name() );
     40                if ( tyVar != tyVars->end() ) {
    3041                        switch ( tyVar->second.kind ) {
    3142                          case TypeDecl::Any:
  • src/GenPoly/ScrubTyVars.h

    r17df48e r5a3ac84  
    2626namespace GenPoly {
    2727        class ScrubTyVars : public Mutator {
    28           public:
    29                 ScrubTyVars( const TyVarMap &tyVars, bool dynamicOnly = false ): tyVars( tyVars ), dynamicOnly( dynamicOnly ) {}
     28                /// Whether to scrub all type variables from the provided map, dynamic type variables from the provided map, or all type variables
     29                enum ScrubMode { FromMap, DynamicFromMap, All };
    3030
     31                ScrubTyVars() : tyVars(nullptr), mode( All ) {}
     32
     33                ScrubTyVars( const TyVarMap &tyVars, ScrubMode mode = FromMap ): tyVars( &tyVars ), mode( mode ) {}
     34
     35        public:
    3136                /// For all polymorphic types with type variables in `tyVars`, replaces generic types, dtypes, and ftypes with the appropriate void type,
    3237                /// and sizeof/alignof expressions with the proper variable
     
    3843                template< typename SynTreeClass >
    3944                static SynTreeClass *scrubDynamic( SynTreeClass *target, const TyVarMap &tyVars );
     45
     46                /// For all polymorphic types, replaces generic types, dtypes, and ftypes with the appropriate void type,
     47                /// and sizeof/alignof expressions with the proper variable
     48                template< typename SynTreeClass >
     49                static SynTreeClass *scrubAll( SynTreeClass *target );
    4050
    4151                virtual Type* mutate( TypeInstType *typeInst );
     
    4959                /// Returns the type if it should be scrubbed, NULL otherwise.
    5060                Type* shouldScrub( Type *ty ) {
    51                         return dynamicOnly ? isDynType( ty, tyVars ) : isPolyType( ty, tyVars );
    52 //                      if ( ! dynamicOnly ) return isPolyType( ty, tyVars );
    53 //
    54 //                      if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( ty ) ) {
    55 //                              return tyVars.find( typeInst->get_name() ) != tyVars.end() ? ty : 0;
    56 //                      }
    57 //
    58 //                      return isDynType( ty, tyVars );
     61                        switch ( mode ) {
     62                        case FromMap: return isPolyType( ty, *tyVars );
     63                        case DynamicFromMap: return isDynType( ty, *tyVars );
     64                        case All: return isPolyType( ty );
     65                        }
     66                        assert(false); return nullptr; // unreachable
     67                        // return dynamicOnly ? isDynType( ty, tyVars ) : isPolyType( ty, tyVars );
    5968                }
    6069               
     
    6271                Type* mutateAggregateType( Type *ty );
    6372               
    64                 const TyVarMap &tyVars;  ///< Type variables to scrub
    65                 bool dynamicOnly;        ///< only scrub the types with dynamic layout? [false]
     73                const TyVarMap *tyVars;  ///< Type variables to scrub
     74                ScrubMode mode;          ///< which type variables to scrub? [FromMap]
    6675        };
    6776
     
    7483        template< typename SynTreeClass >
    7584        SynTreeClass * ScrubTyVars::scrubDynamic( SynTreeClass *target, const TyVarMap &tyVars ) {
    76                 ScrubTyVars scrubber( tyVars, true );
     85                ScrubTyVars scrubber( tyVars, ScrubTyVars::DynamicFromMap );
     86                return static_cast< SynTreeClass * >( target->acceptMutator( scrubber ) );
     87        }
     88
     89        template< typename SynTreeClass >
     90        SynTreeClass * ScrubTyVars::scrubAll( SynTreeClass *target ) {
     91                ScrubTyVars scrubber;
    7792                return static_cast< SynTreeClass * >( target->acceptMutator( scrubber ) );
    7893        }
Note: See TracChangeset for help on using the changeset viewer.