Index: src/GenPoly/InstantiateGeneric.cc =================================================================== --- src/GenPoly/InstantiateGeneric.cc (revision b0b958a2dfe5052fbfc59bc8543a758787df2f9d) +++ src/GenPoly/InstantiateGeneric.cc (revision 5bf47126bd2626236e355b067fca0454ce0498fd) @@ -44,10 +44,8 @@ ConcreteType(const ConcreteType& that) : base(that.base), params() { cloneAll(that.params, params); } - /// Extracts types from a list of Expression* (which should be TypeExpr*) - ConcreteType(AggregateDecl *_base, const std::list< Expression* >& _params) : base(_base), params() { - for ( std::list< Expression* >::const_iterator it = _params.begin(); it != _params.end(); ++it ) { - TypeExpr *param = dynamic_cast< TypeExpr* >(*it); - assert(param && "Aggregate parameters should be type expressions"); - params.push_back( param->get_type()->clone() ); + /// Extracts types from a list of TypeExpr* + ConcreteType(AggregateDecl *_base, const std::list< TypeExpr* >& _params) : base(_base), params() { + for ( std::list< TypeExpr* >::const_iterator param = _params.begin(); param != _params.end(); ++param ) { + params.push_back( (*param)->get_type()->clone() ); } } @@ -66,7 +64,7 @@ bool operator== (const ConcreteType& that) const { + if ( base != that.base ) return false; + SymTab::Indexer dummy; - - if ( base != that.base ) return false; if ( params.size() != that.params.size() ) return false; for ( std::list< Type* >::const_iterator it = params.begin(), jt = that.params.begin(); it != params.end(); ++it, ++jt ) { @@ -82,6 +80,12 @@ /// Maps a concrete type to the instantiated struct type, accounting for scope class InstantiationMap { - /// Pair of concrete type and declaration that instantiates it - typedef std::pair< ConcreteType, AggregateDecl* > Instantiation; + /// Instantiation of a generic type, with key information to find it + struct Instantiation { + ConcreteType key; ///< Instantiation parameters for this type + AggregateDecl *decl; ///< Declaration of the instantiated generic type + + Instantiation() : key(), decl(0) {} + Instantiation(const ConcreteType &_key, AggregateDecl *_decl) : key(_key), decl(_decl) {} + }; /// Map of generic types to instantiations of them typedef std::map< AggregateDecl*, std::vector< Instantiation > > Scope; @@ -107,5 +111,5 @@ /// Gets the declaration for the concrete instantiation of this type, assuming it has already been instantiated in the current scope. /// Returns NULL on none such. - AggregateDecl* lookup( AggregateDecl *generic, std::list< Expression* >& params ) { + AggregateDecl* lookup( AggregateDecl *generic, const std::list< TypeExpr* >& params ) { ConcreteType key(generic, params); // scan scopes from innermost out @@ -116,5 +120,5 @@ // look through instantiations for matches to concrete type for ( std::vector< Instantiation >::const_iterator inst = insts->second.begin(); inst != insts->second.end(); ++inst ) { - if ( inst->first == key ) return inst->second; + if ( inst->key == key ) return inst->decl; } } @@ -123,16 +127,16 @@ } public: - StructDecl* lookup( StructInstType *inst ) { return (StructDecl*)lookup( inst->get_baseStruct(), inst->get_parameters() ); } - UnionDecl* lookup( UnionInstType *inst ) { return (UnionDecl*)lookup( inst->get_baseUnion(), inst->get_parameters() ); } + StructDecl* lookup( StructInstType *inst, const std::list< TypeExpr* > &typeSubs ) { return (StructDecl*)lookup( inst->get_baseStruct(), typeSubs ); } + UnionDecl* lookup( UnionInstType *inst, const std::list< TypeExpr* > &typeSubs ) { return (UnionDecl*)lookup( inst->get_baseUnion(), typeSubs ); } private: /// Adds a declaration for a concrete type to the current scope - void insert( AggregateDecl *generic, std::list< Expression* >& params, AggregateDecl *decl ) { + void insert( AggregateDecl *generic, const std::list< TypeExpr* > ¶ms, AggregateDecl *decl ) { ConcreteType key(generic, params); - scopes.back()[generic].push_back( std::make_pair( key, decl ) ); + scopes.back()[generic].push_back( Instantiation( key, decl ) ); } public: - void insert( StructInstType *inst, StructDecl *decl ) { insert( inst->get_baseStruct(), inst->get_parameters(), decl ); } - void insert( UnionInstType *inst, UnionDecl *decl ) { insert( inst->get_baseUnion(), inst->get_parameters(), decl ); } + void insert( StructInstType *inst, const std::list< TypeExpr* > &typeSubs, StructDecl *decl ) { insert( inst->get_baseStruct(), typeSubs, decl ); } + void insert( UnionInstType *inst, const std::list< TypeExpr* > &typeSubs, UnionDecl *decl ) { insert( inst->get_baseUnion(), typeSubs, decl ); } }; @@ -144,4 +148,7 @@ public: Instantiate() : DeclMutator(), instantiations(), typeNamer("_conc_") {} + +// virtual Declaration* mutate( StructDecl *aggregateDecl ); +// virtual Declaration* mutate( UnionDecl *aggregateDecl ); virtual Type* mutate( StructInstType *inst ); @@ -157,10 +164,54 @@ } - /// Substitutes types of members of in according to baseParams => params, appending the result to out - void substituteMembers( const std::list< Declaration* >& in, - const std::list< TypeDecl * >& baseParams, const std::list< Expression* >& params, + /// Makes substitutions of params into baseParams; returns true if all parameters substituted for a concrete type + bool makeSubstitutions( const std::list< TypeDecl* >& baseParams, const std::list< Expression* >& params, std::list< TypeExpr* >& out ) { + bool allConcrete = true; // will finish the substitution list even if they're not all concrete + + // substitute concrete types for given parameters, and incomplete types for placeholders + std::list< TypeDecl* >::const_iterator baseParam = baseParams.begin(); + std::list< Expression* >::const_iterator param = params.begin(); + for ( ; baseParam != baseParams.end() && param != params.end(); ++baseParam, ++param ) { + switch ( (*baseParam)->get_kind() ) { + case TypeDecl::Any: { // any type is a valid substitution here; complete types can be used to instantiate generics + TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param ); + assert(paramType && "Aggregate parameters should be type expressions"); + out.push_back( paramType->clone() ); + // check that the substituted type isn't a type variable itself + if ( dynamic_cast< TypeInstType* >( paramType->get_type() ) ) { + allConcrete = false; + } + break; + } + case TypeDecl::Dtype: // dtype can be consistently replaced with void [only pointers, which become void*] + out.push_back( new TypeExpr( new VoidType( Type::Qualifiers() ) ) ); + break; + case TypeDecl::Ftype: // pointer-to-ftype can be consistently replaced with void (*)(void) [similar to dtype] + out.push_back( new TypeExpr( new FunctionType( Type::Qualifiers(), false ) ) ); + break; + } + } + + // if not enough parameters given, substitute remaining incomplete types for placeholders + for ( ; baseParam != baseParams.end(); ++baseParam ) { + switch ( (*baseParam)->get_kind() ) { + case TypeDecl::Any: // no more substitutions here, fail early + return false; + case TypeDecl::Dtype: // dtype can be consistently replaced with void [only pointers, which become void*] + out.push_back( new TypeExpr( new VoidType( Type::Qualifiers() ) ) ); + break; + case TypeDecl::Ftype: // pointer-to-ftype can be consistently replaced with void (*)(void) [similar to dtype] + out.push_back( new TypeExpr( new FunctionType( Type::Qualifiers(), false ) ) ); + break; + } + } + + return allConcrete; + } + + /// Substitutes types of members of in according to baseParams => typeSubs, appending the result to out + void substituteMembers( const std::list< Declaration* >& in, const std::list< TypeDecl* >& baseParams, const std::list< TypeExpr* >& typeSubs, std::list< Declaration* >& out ) { // substitute types into new members - TypeSubstitution subs( baseParams.begin(), baseParams.end(), params.begin() ); + TypeSubstitution subs( baseParams.begin(), baseParams.end(), typeSubs.begin() ); for ( std::list< Declaration* >::const_iterator member = in.begin(); member != in.end(); ++member ) { Declaration *newMember = (*member)->clone(); @@ -178,19 +229,26 @@ // exit early if no need for further mutation if ( inst->get_parameters().empty() ) return inst; + assert( inst->get_baseParameters() && "Base struct has parameters" ); + + // check if type can be concretely instantiated; put substitutions into typeSubs + std::list< TypeExpr* > typeSubs; + if ( ! makeSubstitutions( *inst->get_baseParameters(), inst->get_parameters(), typeSubs ) ) { + deleteAll( typeSubs ); + return inst; + } // make concrete instantiation of generic type - StructDecl *concDecl = instantiations.lookup( inst ); + StructDecl *concDecl = instantiations.lookup( inst, typeSubs ); if ( ! concDecl ) { - assert( inst->get_baseParameters() && "Base struct has parameters" ); // set concDecl to new type, insert type declaration into statements to add concDecl = new StructDecl( typeNamer.newName( inst->get_name() ) ); - substituteMembers( inst->get_baseStruct()->get_members(), - *inst->get_baseParameters(), inst->get_parameters(), - concDecl->get_members() ); + substituteMembers( inst->get_baseStruct()->get_members(), *inst->get_baseParameters(), typeSubs, concDecl->get_members() ); DeclMutator::addDeclaration( concDecl ); - instantiations.insert( inst, concDecl ); + instantiations.insert( inst, typeSubs, concDecl ); } StructInstType *newInst = new StructInstType( inst->get_qualifiers(), concDecl->get_name() ); newInst->set_baseStruct( concDecl ); + + deleteAll( typeSubs ); delete inst; return newInst; @@ -205,19 +263,26 @@ // exit early if no need for further mutation if ( inst->get_parameters().empty() ) return inst; - + assert( inst->get_baseParameters() && "Base union has parameters" ); + + // check if type can be concretely instantiated; put substitutions into typeSubs + std::list< TypeExpr* > typeSubs; + if ( ! makeSubstitutions( *inst->get_baseParameters(), inst->get_parameters(), typeSubs ) ) { + deleteAll( typeSubs ); + return inst; + } + // make concrete instantiation of generic type - UnionDecl *concDecl = instantiations.lookup( inst ); + UnionDecl *concDecl = instantiations.lookup( inst, typeSubs ); if ( ! concDecl ) { // set concDecl to new type, insert type declaration into statements to add - assert( inst->get_baseParameters() && "Base union has parameters" ); concDecl = new UnionDecl( typeNamer.newName( inst->get_name() ) ); - substituteMembers( inst->get_baseUnion()->get_members(), - *inst->get_baseParameters(), inst->get_parameters(), - concDecl->get_members() ); + substituteMembers( inst->get_baseUnion()->get_members(), *inst->get_baseParameters(), typeSubs, concDecl->get_members() ); DeclMutator::addDeclaration( concDecl ); - instantiations.insert( inst, concDecl ); + instantiations.insert( inst, typeSubs, concDecl ); } UnionInstType *newInst = new UnionInstType( inst->get_qualifiers(), concDecl->get_name() ); newInst->set_baseUnion( concDecl ); + + deleteAll( typeSubs ); delete inst; return newInst;