Index: src/GenPoly/InstantiateGeneric.cc =================================================================== --- src/GenPoly/InstantiateGeneric.cc (revision d8847b7e0bcf675a467161ab62fbe142bb2d4e95) +++ src/GenPoly/InstantiateGeneric.cc (revision d8847b7e0bcf675a467161ab62fbe142bb2d4e95) @@ -0,0 +1,242 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// InstantiateGeneric.h -- +// +// Author : Aaron B. Moss +// Created On : Wed Nov 11 14:55:01 2015 +// Last Modified By : Aaron B. Moss +// Last Modified On : Wed Nov 11 14:55:01 2015 +// Update Count : 1 +// + +#include +#include +#include +#include +#include + +#include "InstantiateGeneric.h" +#include "PolyMutator.h" + +#include "SymTab/TypeEquality.h" +#include "SynTree/Declaration.h" +#include "SynTree/Mutator.h" +#include "SynTree/Statement.h" +#include "SynTree/Type.h" +#include "SynTree/TypeSubstitution.h" + +#include "UniqueName.h" +#include "utility.h" + +namespace GenPoly { + + class Instantiate : public PolyMutator { + public: + /// Key for a unique concrete type; generic base type paired with type parameter list + struct ConcreteType { + ConcreteType() : base(NULL), params() {} + + ConcreteType(AggregateDecl *_base, const std::list< Type* >& _params) : base(_base), params() { cloneAll(_params, params); } + + 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() ); + } + } + + ConcreteType& operator= (const ConcreteType& that) { + deleteAll( params ); + params.clear(); + + base = that.base; + cloneAll( that.params, params ); + + return *this; + } + + ~ConcreteType() { deleteAll( params ); } + + bool operator== (const ConcreteType& that) const { + 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 ) { + if ( ! SymTab::typeEquals(*it, *jt) ) return false; + } + return true; + } + + AggregateDecl *base; ///< Base generic type + std::list< Type* > params; ///< Instantiation parameters + }; + + /// 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; + /// Map of generic types to instantiations of them + typedef std::map< AggregateDecl*, std::vector< Instantiation > > Scope; + + std::vector< Scope > scopes; ///< list of scopes, from outermost to innermost + + public: + /// Starts a new scope + void beginScope() { + Scope scope; + scopes.push_back(scope); + } + + /// Ends a scope + void endScope() { + scopes.pop_back(); + } + + /// Default constructor initializes with one scope + InstantiationMap() { beginScope(); } + + private: + /// 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 ) { + ConcreteType key(generic, params); + // scan scopes from innermost out + for ( std::vector< Scope >::const_reverse_iterator scope = scopes.rbegin(); scope != scopes.rend(); ++scope ) { + // skip scope if no instantiations of this generic type + Scope::const_iterator insts = scope->find( generic ); + if ( insts == scope->end() ) continue; + // 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; + } + } + // no matching instantiation found + return NULL; + } + 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() ); } + + private: + /// Adds a declaration for a concrete type to the current scope + void insert( AggregateDecl *generic, std::list< Expression* >& params, AggregateDecl *decl ) { + ConcreteType key(generic, params); + scopes.back()[generic].push_back( std::make_pair( 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 ); } + }; + + virtual Type* mutate( StructInstType *inst ); + virtual Type* mutate( UnionInstType *inst ); + + virtual void doBeginScope(); + virtual void doEndScope(); + + private: + /// Adds a declaration to the current environment and the statements to add + void addDeclaration( AggregateDecl *decl ) { + std::list< Label > labels; + DeclStmt *stmt = new DeclStmt( labels, decl ); + PolyMutator::stmtsToAdd.push_back( stmt ); + } + + InstantiationMap instantiations; + UniqueName typeNamer; + }; + + void instantiateGeneric( std::list< Declaration* >& translationUnit ) { + Instantiate instantiator; + mutateAll( translationUnit, instantiator ); + } + + /// 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, + std::list< Declaration* >& out ) { + // substitute types into new members + TypeSubstitution subs( baseParams.begin(), baseParams.end(), params.begin() ); + for ( std::list< Declaration* >::const_iterator member = in.begin(); member != in.end(); ++member ) { + Declaration *newMember = (*member)->clone(); + subs.apply(newMember); + out.push_back( newMember ); + } + } + + Type* Instantiate::mutate( StructInstType *inst ) { + // mutate subtypes + Type *mutated = Mutator::mutate( inst ); + inst = dynamic_cast< StructInstType* >( mutated ); + if ( ! inst ) return mutated; + + // exit early if no need for further mutation + if ( inst->get_parameters().empty() ) return inst; + + // make concrete instantiation of generic type + StructDecl *concDecl = instantiations.lookup( inst ); + if ( ! concDecl ) { + // 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() ); + addDeclaration( concDecl ); + instantiations.insert( inst, concDecl ); + } + StructInstType *newInst = new StructInstType( inst->get_qualifiers(), concDecl->get_name() ); + newInst->set_baseStruct( concDecl ); + delete inst; + return newInst; + } + + Type* Instantiate::mutate( UnionInstType *inst ) { + // mutate subtypes + Type *mutated = Mutator::mutate( inst ); + inst = dynamic_cast< UnionInstType* >( mutated ); + if ( ! inst ) return mutated; + + // exit early if no need for further mutation + if ( inst->get_parameters().empty() ) return inst; + + // make concrete instantiation of generic type + UnionDecl *concDecl = instantiations.lookup( inst ); + if ( ! concDecl ) { + // set concDecl to new type, insert type declaration into statements to add + concDecl = new UnionDecl( typeNamer.newName( inst->get_name() ) ); + substituteMembers( inst->get_baseUnion()->get_members(), + inst->get_baseParameters(), inst->get_parameters(), + concDecl->get_members() ); + addDeclaration( concDecl ); + instantiations.insert( inst, concDecl ); + } + UnionInstType *newInst = new UnionInstType( inst->get_qualifiers(), concDecl->get_name() ); + newInst->set_baseUnion( concDecl ); + delete inst; + return newInst; + } + + void Instantiate::doBeginScope() { + // push a new concrete type scope + instantiations.beginScope(); + } + + void Instantiate::doEndScope() { + // pop the last concrete type scope + instantiations.endScope(); + } + +} // namespace GenPoly + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/GenPoly/InstantiateGeneric.h =================================================================== --- src/GenPoly/InstantiateGeneric.h (revision d8847b7e0bcf675a467161ab62fbe142bb2d4e95) +++ src/GenPoly/InstantiateGeneric.h (revision d8847b7e0bcf675a467161ab62fbe142bb2d4e95) @@ -0,0 +1,33 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// InstantiateGeneric.h -- +// +// Author : Aaron B. Moss +// Created On : Wed Nov 11 14:55:01 2015 +// Last Modified By : Aaron B. Moss +// Last Modified On : Wed Nov 11 14:55:01 2015 +// Update Count : 1 +// + +#ifndef _INSTANTIATEGENERIC_H +#define _INSTANTIATEGENERIC_H + +#include +#include "SynTree/SynTree.h" + +namespace GenPoly { + /// Replaces generic structs used outside polymorphic contexts with their concrete instantiations + void instantiateGeneric( std::list< Declaration* >& translationUnit ); +} // namespace GenPoly + +#endif // _INSTANTIATEGENERIC_H + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/GenPoly/module.mk =================================================================== --- src/GenPoly/module.mk (revision d2ded3e7b80d4d46102610712560152e44975503) +++ src/GenPoly/module.mk (revision d8847b7e0bcf675a467161ab62fbe142bb2d4e95) @@ -22,3 +22,4 @@ GenPoly/Specialize.cc \ GenPoly/CopyParams.cc \ - GenPoly/FindFunction.cc + GenPoly/FindFunction.cc \ + GenPoly/InstantiateGeneric.cc