Index: src/GenPoly/Box.cc =================================================================== --- src/GenPoly/Box.cc (revision 8ef9c5e7c34b1c5ff8f0ceff99f5b33aa922b62c) +++ src/GenPoly/Box.cc (revision 5a3ac848c64ea57337a51b1cff756fb8e593d201) @@ -381,5 +381,5 @@ // calculate struct layout in function body - // initialize size and alignment to 0 and 1 (will have at least one member to re-edit size + // initialize size and alignment to 0 and 1 (will have at least one member to re-edit size) addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( sizeParam ), new ConstantExpr( Constant( sizeAlignType->clone(), "0" ) ) ) ); addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( alignParam ), new ConstantExpr( Constant( sizeAlignType->clone(), "1" ) ) ) ); @@ -1852,5 +1852,6 @@ DeclClass *ret = static_cast< DeclClass *>( Mutator::mutate( decl ) ); - ScrubTyVars::scrub( decl, scopeTyVars ); + // ScrubTyVars::scrub( decl, scopeTyVars ); + ScrubTyVars::scrubAll( decl ); scopeTyVars.endScope(); Index: src/GenPoly/GenPoly.cc =================================================================== --- src/GenPoly/GenPoly.cc (revision 8ef9c5e7c34b1c5ff8f0ceff99f5b33aa922b62c) +++ src/GenPoly/GenPoly.cc (revision 5a3ac848c64ea57337a51b1cff756fb8e593d201) @@ -15,9 +15,16 @@ #include "GenPoly.h" +#include "assert.h" #include "SynTree/Expression.h" #include "SynTree/Type.h" +#include "ResolvExpr/typeops.h" #include +#include +#include +#include +#include +#include using namespace std; @@ -38,5 +45,5 @@ for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) { TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param ); - assert(paramType && "Aggregate parameters should be type expressions"); + assertf(paramType, "Aggregate parameters should be type expressions"); if ( isPolyType( paramType->get_type(), tyVars, env ) ) return true; } @@ -48,6 +55,26 @@ for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) { TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param ); - assert(paramType && "Aggregate parameters should be type expressions"); + assertf(paramType, "Aggregate parameters should be type expressions"); if ( isDynType( paramType->get_type(), tyVars, env ) ) return true; + } + return false; + } + + /// Checks a parameter list for inclusion of polymorphic parameters; will substitute according to env if present + bool includesPolyParams( std::list< Expression* >& params, const TypeSubstitution *env ) { + for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) { + TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param ); + assertf(paramType, "Aggregate parameters should be type expressions"); + if ( includesPolyType( paramType->get_type(), env ) ) return true; + } + return false; + } + + /// Checks a parameter list for inclusion of polymorphic parameters from tyVars; will substitute according to env if present + bool includesPolyParams( std::list< Expression* >& params, const TyVarMap &tyVars, const TypeSubstitution *env ) { + for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) { + TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param ); + assertf(paramType, "Aggregate parameters should be type expressions"); + if ( includesPolyType( paramType->get_type(), tyVars, env ) ) return true; } return false; @@ -187,4 +214,36 @@ return isPolyType( type, tyVars, env ); + } + + bool includesPolyType( Type *type, const TypeSubstitution *env ) { + type = replaceTypeInst( type, env ); + + if ( dynamic_cast< TypeInstType * >( type ) ) { + return true; + } else if ( PointerType *pointerType = dynamic_cast< PointerType* >( type ) ) { + if ( includesPolyType( pointerType->get_base(), env ) ) return true; + } else if ( StructInstType *structType = dynamic_cast< StructInstType* >( type ) ) { + if ( includesPolyParams( structType->get_parameters(), env ) ) return true; + } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( type ) ) { + if ( includesPolyParams( unionType->get_parameters(), env ) ) return true; + } + return false; + } + + bool includesPolyType( Type *type, const TyVarMap &tyVars, const TypeSubstitution *env ) { + type = replaceTypeInst( type, env ); + + if ( TypeInstType *typeInstType = dynamic_cast< TypeInstType * >( type ) ) { + if ( tyVars.find( typeInstType->get_name() ) != tyVars.end() ) { + return true; + } + } else if ( PointerType *pointerType = dynamic_cast< PointerType* >( type ) ) { + if ( includesPolyType( pointerType->get_base(), tyVars, env ) ) return true; + } else if ( StructInstType *structType = dynamic_cast< StructInstType* >( type ) ) { + if ( includesPolyParams( structType->get_parameters(), tyVars, env ) ) return true; + } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( type ) ) { + if ( includesPolyParams( unionType->get_parameters(), tyVars, env ) ) return true; + } + return false; } @@ -237,4 +296,136 @@ } + namespace { + /// Checks if is a pointer to D + template + bool is( const B* p ) { return type_index{typeid(D)} == type_index{typeid(*p)}; } + + /// Converts to a pointer to D without checking for safety + template + inline D* as( B* p ) { return reinterpret_cast(p); } + + /// Flattens a declaration list + template + void flattenList( list< DeclarationWithType* > src, Output out ) { + for ( DeclarationWithType* decl : src ) { + ResolvExpr::flatten( decl->get_type(), out ); + } + } + + /// Flattens a list of types + template + void flattenList( list< Type* > src, Output out ) { + for ( Type* ty : src ) { + ResolvExpr::flatten( ty, out ); + } + } + + /// Checks if two lists of parameters are equal up to polymorphic substitution. + bool paramListsPolyCompatible( const list< Expression* >& aparams, const list< Expression* >& bparams ) { + if ( aparams.size() != bparams.size() ) return false; + + for ( list< Expression* >::const_iterator at = aparams.begin(), bt = bparams.begin(); + at != aparams.end(); ++at, ++bt ) { + TypeExpr *aparam = dynamic_cast< TypeExpr* >(*at); + assertf(aparam, "Aggregate parameters should be type expressions"); + TypeExpr *bparam = dynamic_cast< TypeExpr* >(*bt); + assertf(bparam, "Aggregate parameters should be type expressions"); + + // xxx - might need to let VoidType be a wildcard here too; could have some voids + // stuffed in for dtype-statics. + // if ( is( aparam->get_type() ) || is( bparam->get_type() ) ) continue; + if ( ! typesPolyCompatible( aparam->get_type(), bparam->get_type() ) ) return false; + } + + return true; + } + } + + bool typesPolyCompatible( Type *a, Type *b ) { + type_index aid{ typeid(*a) }; + // polymorphic types always match + if ( aid == type_index{typeid(TypeInstType)} ) return true; + + type_index bid{ typeid(*b) }; + // polymorphic types always match + if ( bid == type_index{typeid(TypeInstType)} ) return true; + + // can't match otherwise if different types + if ( aid != bid ) return false; + + // recurse through type structure (conditions borrowed from Unify.cc) + if ( aid == type_index{typeid(BasicType)} ) { + return as(a)->get_kind() == as(b)->get_kind(); + } else if ( aid == type_index{typeid(PointerType)} ) { + PointerType *ap = as(a), *bp = as(b); + + // void pointers should match any other pointer type + return is( ap->get_base() ) || is( bp->get_base() ) + || typesPolyCompatible( ap->get_base(), bp->get_base() ); + } else if ( aid == type_index{typeid(ArrayType)} ) { + ArrayType *aa = as(a), *ba = as(b); + + if ( aa->get_isVarLen() ) { + if ( ! ba->get_isVarLen() ) return false; + } else { + if ( ba->get_isVarLen() ) return false; + + ConstantExpr *ad = dynamic_cast( aa->get_dimension() ); + ConstantExpr *bd = dynamic_cast( ba->get_dimension() ); + if ( ad && bd + && ad->get_constant()->get_value() != bd->get_constant()->get_value() ) + return false; + } + + return typesPolyCompatible( aa->get_base(), ba->get_base() ); + } else if ( aid == type_index{typeid(FunctionType)} ) { + FunctionType *af = as(a), *bf = as(b); + + vector aparams, bparams; + flattenList( af->get_parameters(), back_inserter( aparams ) ); + flattenList( bf->get_parameters(), back_inserter( bparams ) ); + if ( aparams.size() != bparams.size() ) return false; + + vector areturns, breturns; + flattenList( af->get_returnVals(), back_inserter( areturns ) ); + flattenList( bf->get_returnVals(), back_inserter( breturns ) ); + if ( areturns.size() != breturns.size() ) return false; + + for ( unsigned i = 0; i < aparams.size(); ++i ) { + if ( ! typesPolyCompatible( aparams[i], bparams[i] ) ) return false; + } + for ( unsigned i = 0; i < areturns.size(); ++i ) { + if ( ! typesPolyCompatible( areturns[i], breturns[i] ) ) return false; + } + return true; + } else if ( aid == type_index{typeid(StructInstType)} ) { + StructInstType *aa = as(a), *ba = as(b); + + if ( aa->get_name() != ba->get_name() ) return false; + return paramListsPolyCompatible( aa->get_parameters(), ba->get_parameters() ); + } else if ( aid == type_index{typeid(UnionInstType)} ) { + UnionInstType *aa = as(a), *ba = as(b); + + if ( aa->get_name() != ba->get_name() ) return false; + return paramListsPolyCompatible( aa->get_parameters(), ba->get_parameters() ); + } else if ( aid == type_index{typeid(EnumInstType)} ) { + return as(a)->get_name() == as(b)->get_name(); + } else if ( aid == type_index{typeid(TraitInstType)} ) { + return as(a)->get_name() == as(b)->get_name(); + } else if ( aid == type_index{typeid(TupleType)} ) { + TupleType *at = as(a), *bt = as(b); + + vector atypes, btypes; + flattenList( at->get_types(), back_inserter( atypes ) ); + flattenList( bt->get_types(), back_inserter( btypes ) ); + if ( atypes.size() != btypes.size() ) return false; + + for ( unsigned i = 0; i < atypes.size(); ++i ) { + if ( ! typesPolyCompatible( atypes[i], btypes[i] ) ) return false; + } + return true; + } else return true; // VoidType, VarArgsType, ZeroType & OneType just need the same type + } + void addToTyVarMap( TypeDecl * tyVar, TyVarMap &tyVarMap ) { tyVarMap[ tyVar->get_name() ] = TypeDecl::Data{ tyVar }; Index: src/GenPoly/GenPoly.h =================================================================== --- src/GenPoly/GenPoly.h (revision 8ef9c5e7c34b1c5ff8f0ceff99f5b33aa922b62c) +++ src/GenPoly/GenPoly.h (revision 5a3ac848c64ea57337a51b1cff756fb8e593d201) @@ -67,4 +67,12 @@ Type *hasPolyBase( Type *type, const TyVarMap &tyVars, int *levels = 0, const TypeSubstitution *env = 0 ); + /// true iff this type or some base of this type after dereferencing pointers is either polymorphic or a generic type with at least one + /// polymorphic parameter; will look up substitution in env if provided. + bool includesPolyType( Type *type, const TypeSubstitution *env = 0 ); + + /// true iff this type or some base of this type after dereferencing pointers is either polymorphic in tyVars, or a generic type with + /// at least one polymorphic parameter in tyVars; will look up substitution in env if provided. + bool includesPolyType( Type *type, const TyVarMap &tyVars, const TypeSubstitution *env = 0 ); + /// Returns a pointer to the base FunctionType if ty is the type of a function (or pointer to one), NULL otherwise FunctionType *getFunctionType( Type *ty ); @@ -73,4 +81,7 @@ /// N will be stored in levels, if provided VariableExpr *getBaseVar( Expression *expr, int *levels = 0 ); + + /// true iff types are structurally identical, where TypeInstType's match any type. + bool typesPolyCompatible( Type *aty, Type *bty ); /// Adds the type variable `tyVar` to `tyVarMap` Index: src/GenPoly/InstantiateGeneric.cc =================================================================== --- src/GenPoly/InstantiateGeneric.cc (revision 8ef9c5e7c34b1c5ff8f0ceff99f5b33aa922b62c) +++ src/GenPoly/InstantiateGeneric.cc (revision 5a3ac848c64ea57337a51b1cff756fb8e593d201) @@ -16,7 +16,7 @@ #include #include +#include #include #include -#include #include "InstantiateGeneric.h" @@ -25,4 +25,5 @@ #include "GenPoly.h" #include "ScopedSet.h" +#include "ScrubTyVars.h" #include "PolyMutator.h" @@ -77,7 +78,6 @@ if ( params.size() != that.params.size() ) return false; - SymTab::Indexer dummy; for ( std::list< Type* >::const_iterator it = params.begin(), jt = that.params.begin(); it != params.end(); ++it, ++jt ) { - if ( ! ResolvExpr::typesCompatible( *it, *jt, dummy ) ) return false; + if ( ! typesPolyCompatible( *it, *jt ) ) return false; } return true; @@ -227,20 +227,13 @@ if ( (*baseParam)->isComplete() ) { // substitute parameter for complete (otype or sized dtype) type - int pointerLevels = 0; - if ( hasPolyBase( paramType->get_type(), &pointerLevels ) && pointerLevels > 0 ) { - // Make a void* with equivalent nesting - Type* voidPtr = new VoidType( Type::Qualifiers() ); - while ( pointerLevels > 0 ) { - // Just about data layout, so qualifiers *shouldn't* matter - voidPtr = new PointerType( Type::Qualifiers(), voidPtr ); - --pointerLevels; - } - out.push_back( new TypeExpr( voidPtr ) ); - // this type is still dtype-static, no change to gt + if ( isPolyType( paramType->get_type() ) ) { + // substitute polymorphic parameter type in to generic type + out.push_back( paramType->clone() ); + gt = genericType::dynamic; } else { - // Just clone parameter type - out.push_back( paramType->clone() ); - // make the struct concrete or dynamic depending on the parameter - gt |= isPolyType( paramType->get_type() ) ? genericType::dynamic : genericType::concrete; + // normalize possibly dtype-static parameter type + out.push_back( new TypeExpr{ + ScrubTyVars::scrubAll( paramType->get_type()->clone() ) } ); + gt |= genericType::concrete; } } else switch ( (*baseParam)->get_kind() ) { @@ -373,5 +366,5 @@ concDecl = new StructDecl( typeNamer.newName( inst->get_name() ) ); concDecl->set_body( inst->get_baseStruct()->has_body() ); - substituteMembers( inst->get_baseStruct()->get_members(), *inst->get_baseParameters(), typeSubs, concDecl->get_members() ); + substituteMembers( inst->get_baseStruct()->get_members(), *inst->get_baseParameters(), typeSubs, concDecl->get_members() ); DeclMutator::addDeclaration( concDecl ); insert( inst, typeSubs, concDecl ); Index: src/GenPoly/ScrubTyVars.cc =================================================================== --- src/GenPoly/ScrubTyVars.cc (revision 8ef9c5e7c34b1c5ff8f0ceff99f5b33aa922b62c) +++ src/GenPoly/ScrubTyVars.cc (revision 5a3ac848c64ea57337a51b1cff756fb8e593d201) @@ -26,6 +26,17 @@ namespace GenPoly { Type * ScrubTyVars::mutate( TypeInstType *typeInst ) { - TyVarMap::const_iterator tyVar = tyVars.find( typeInst->get_name() ); - if ( tyVar != tyVars.end() ) { + if ( ! tyVars ) { + if ( typeInst->get_isFtype() ) { + delete typeInst; + return new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) ); + } else { + PointerType *ret = new PointerType( Type::Qualifiers(), new VoidType( typeInst->get_qualifiers() ) ); + delete typeInst; + return ret; + } + } + + TyVarMap::const_iterator tyVar = tyVars->find( typeInst->get_name() ); + if ( tyVar != tyVars->end() ) { switch ( tyVar->second.kind ) { case TypeDecl::Any: Index: src/GenPoly/ScrubTyVars.h =================================================================== --- src/GenPoly/ScrubTyVars.h (revision 8ef9c5e7c34b1c5ff8f0ceff99f5b33aa922b62c) +++ src/GenPoly/ScrubTyVars.h (revision 5a3ac848c64ea57337a51b1cff756fb8e593d201) @@ -26,7 +26,12 @@ namespace GenPoly { class ScrubTyVars : public Mutator { - public: - ScrubTyVars( const TyVarMap &tyVars, bool dynamicOnly = false ): tyVars( tyVars ), dynamicOnly( dynamicOnly ) {} + /// Whether to scrub all type variables from the provided map, dynamic type variables from the provided map, or all type variables + enum ScrubMode { FromMap, DynamicFromMap, All }; + ScrubTyVars() : tyVars(nullptr), mode( All ) {} + + ScrubTyVars( const TyVarMap &tyVars, ScrubMode mode = FromMap ): tyVars( &tyVars ), mode( mode ) {} + + public: /// For all polymorphic types with type variables in `tyVars`, replaces generic types, dtypes, and ftypes with the appropriate void type, /// and sizeof/alignof expressions with the proper variable @@ -38,4 +43,9 @@ template< typename SynTreeClass > static SynTreeClass *scrubDynamic( SynTreeClass *target, const TyVarMap &tyVars ); + + /// For all polymorphic types, replaces generic types, dtypes, and ftypes with the appropriate void type, + /// and sizeof/alignof expressions with the proper variable + template< typename SynTreeClass > + static SynTreeClass *scrubAll( SynTreeClass *target ); virtual Type* mutate( TypeInstType *typeInst ); @@ -49,12 +59,11 @@ /// Returns the type if it should be scrubbed, NULL otherwise. Type* shouldScrub( Type *ty ) { - return dynamicOnly ? isDynType( ty, tyVars ) : isPolyType( ty, tyVars ); -// if ( ! dynamicOnly ) return isPolyType( ty, tyVars ); -// -// if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( ty ) ) { -// return tyVars.find( typeInst->get_name() ) != tyVars.end() ? ty : 0; -// } -// -// return isDynType( ty, tyVars ); + switch ( mode ) { + case FromMap: return isPolyType( ty, *tyVars ); + case DynamicFromMap: return isDynType( ty, *tyVars ); + case All: return isPolyType( ty ); + } + assert(false); return nullptr; // unreachable + // return dynamicOnly ? isDynType( ty, tyVars ) : isPolyType( ty, tyVars ); } @@ -62,6 +71,6 @@ Type* mutateAggregateType( Type *ty ); - const TyVarMap &tyVars; ///< Type variables to scrub - bool dynamicOnly; ///< only scrub the types with dynamic layout? [false] + const TyVarMap *tyVars; ///< Type variables to scrub + ScrubMode mode; ///< which type variables to scrub? [FromMap] }; @@ -74,5 +83,11 @@ template< typename SynTreeClass > SynTreeClass * ScrubTyVars::scrubDynamic( SynTreeClass *target, const TyVarMap &tyVars ) { - ScrubTyVars scrubber( tyVars, true ); + ScrubTyVars scrubber( tyVars, ScrubTyVars::DynamicFromMap ); + return static_cast< SynTreeClass * >( target->acceptMutator( scrubber ) ); + } + + template< typename SynTreeClass > + SynTreeClass * ScrubTyVars::scrubAll( SynTreeClass *target ) { + ScrubTyVars scrubber; return static_cast< SynTreeClass * >( target->acceptMutator( scrubber ) ); }