[d8847b7] | 1 | // |
---|
| 2 | // Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo |
---|
| 3 | // |
---|
| 4 | // The contents of this file are covered under the licence agreement in the |
---|
| 5 | // file "LICENCE" distributed with Cforall. |
---|
| 6 | // |
---|
| 7 | // InstantiateGeneric.h -- |
---|
| 8 | // |
---|
| 9 | // Author : Aaron B. Moss |
---|
| 10 | // Created On : Wed Nov 11 14:55:01 2015 |
---|
| 11 | // Last Modified By : Aaron B. Moss |
---|
| 12 | // Last Modified On : Wed Nov 11 14:55:01 2015 |
---|
| 13 | // Update Count : 1 |
---|
| 14 | // |
---|
| 15 | |
---|
| 16 | #include <list> |
---|
| 17 | #include <map> |
---|
| 18 | #include <string> |
---|
| 19 | #include <utility> |
---|
| 20 | #include <vector> |
---|
| 21 | |
---|
| 22 | #include "InstantiateGeneric.h" |
---|
| 23 | #include "PolyMutator.h" |
---|
| 24 | |
---|
[a2eda27] | 25 | #include "ResolvExpr/typeops.h" |
---|
| 26 | #include "SymTab/Indexer.h" |
---|
[d8847b7] | 27 | #include "SynTree/Declaration.h" |
---|
| 28 | #include "SynTree/Mutator.h" |
---|
| 29 | #include "SynTree/Statement.h" |
---|
| 30 | #include "SynTree/Type.h" |
---|
| 31 | #include "SynTree/TypeSubstitution.h" |
---|
| 32 | |
---|
| 33 | #include "UniqueName.h" |
---|
| 34 | #include "utility.h" |
---|
| 35 | |
---|
| 36 | namespace GenPoly { |
---|
| 37 | |
---|
[258eb5c9] | 38 | /// Key for a unique concrete type; generic base type paired with type parameter list |
---|
| 39 | struct ConcreteType { |
---|
| 40 | ConcreteType() : base(NULL), params() {} |
---|
[d8847b7] | 41 | |
---|
[258eb5c9] | 42 | ConcreteType(AggregateDecl *_base, const std::list< Type* >& _params) : base(_base), params() { cloneAll(_params, params); } |
---|
[d8847b7] | 43 | |
---|
[258eb5c9] | 44 | ConcreteType(const ConcreteType& that) : base(that.base), params() { cloneAll(that.params, params); } |
---|
[d8847b7] | 45 | |
---|
[258eb5c9] | 46 | /// Extracts types from a list of Expression* (which should be TypeExpr*) |
---|
| 47 | ConcreteType(AggregateDecl *_base, const std::list< Expression* >& _params) : base(_base), params() { |
---|
| 48 | for ( std::list< Expression* >::const_iterator it = _params.begin(); it != _params.end(); ++it ) { |
---|
| 49 | TypeExpr *param = dynamic_cast< TypeExpr* >(*it); |
---|
| 50 | assert(param && "Aggregate parameters should be type expressions"); |
---|
| 51 | params.push_back( param->get_type()->clone() ); |
---|
[d8847b7] | 52 | } |
---|
[258eb5c9] | 53 | } |
---|
[d8847b7] | 54 | |
---|
[258eb5c9] | 55 | ConcreteType& operator= (const ConcreteType& that) { |
---|
| 56 | deleteAll( params ); |
---|
| 57 | params.clear(); |
---|
[d8847b7] | 58 | |
---|
[258eb5c9] | 59 | base = that.base; |
---|
| 60 | cloneAll( that.params, params ); |
---|
[d8847b7] | 61 | |
---|
[258eb5c9] | 62 | return *this; |
---|
| 63 | } |
---|
[d8847b7] | 64 | |
---|
[258eb5c9] | 65 | ~ConcreteType() { deleteAll( params ); } |
---|
| 66 | |
---|
| 67 | bool operator== (const ConcreteType& that) const { |
---|
| 68 | SymTab::Indexer dummy; |
---|
[d8847b7] | 69 | |
---|
[258eb5c9] | 70 | if ( base != that.base ) return false; |
---|
| 71 | if ( params.size() != that.params.size() ) return false; |
---|
| 72 | for ( std::list< Type* >::const_iterator it = params.begin(), jt = that.params.begin(); it != params.end(); ++it, ++jt ) { |
---|
| 73 | if ( ! ResolvExpr::typesCompatible( *it, *jt, dummy ) ) return false; |
---|
[d8847b7] | 74 | } |
---|
[258eb5c9] | 75 | return true; |
---|
| 76 | } |
---|
| 77 | |
---|
| 78 | AggregateDecl *base; ///< Base generic type |
---|
| 79 | std::list< Type* > params; ///< Instantiation parameters |
---|
| 80 | }; |
---|
| 81 | |
---|
| 82 | /// Maps a concrete type to the instantiated struct type, accounting for scope |
---|
| 83 | class InstantiationMap { |
---|
| 84 | /// Pair of concrete type and declaration that instantiates it |
---|
| 85 | typedef std::pair< ConcreteType, AggregateDecl* > Instantiation; |
---|
| 86 | /// Map of generic types to instantiations of them |
---|
| 87 | typedef std::map< AggregateDecl*, std::vector< Instantiation > > Scope; |
---|
| 88 | |
---|
| 89 | std::vector< Scope > scopes; ///< list of scopes, from outermost to innermost |
---|
| 90 | |
---|
| 91 | public: |
---|
| 92 | /// Starts a new scope |
---|
| 93 | void beginScope() { |
---|
| 94 | Scope scope; |
---|
| 95 | scopes.push_back(scope); |
---|
| 96 | } |
---|
| 97 | |
---|
| 98 | /// Ends a scope |
---|
| 99 | void endScope() { |
---|
| 100 | scopes.pop_back(); |
---|
| 101 | } |
---|
| 102 | |
---|
| 103 | /// Default constructor initializes with one scope |
---|
| 104 | InstantiationMap() { beginScope(); } |
---|
| 105 | |
---|
| 106 | private: |
---|
| 107 | /// Gets the declaration for the concrete instantiation of this type, assuming it has already been instantiated in the current scope. |
---|
| 108 | /// Returns NULL on none such. |
---|
| 109 | AggregateDecl* lookup( AggregateDecl *generic, std::list< Expression* >& params ) { |
---|
| 110 | ConcreteType key(generic, params); |
---|
| 111 | // scan scopes from innermost out |
---|
| 112 | for ( std::vector< Scope >::const_reverse_iterator scope = scopes.rbegin(); scope != scopes.rend(); ++scope ) { |
---|
| 113 | // skip scope if no instantiations of this generic type |
---|
| 114 | Scope::const_iterator insts = scope->find( generic ); |
---|
| 115 | if ( insts == scope->end() ) continue; |
---|
| 116 | // look through instantiations for matches to concrete type |
---|
| 117 | for ( std::vector< Instantiation >::const_iterator inst = insts->second.begin(); inst != insts->second.end(); ++inst ) { |
---|
| 118 | if ( inst->first == key ) return inst->second; |
---|
[d8847b7] | 119 | } |
---|
| 120 | } |
---|
[258eb5c9] | 121 | // no matching instantiation found |
---|
| 122 | return NULL; |
---|
| 123 | } |
---|
| 124 | public: |
---|
| 125 | StructDecl* lookup( StructInstType *inst ) { return (StructDecl*)lookup( inst->get_baseStruct(), inst->get_parameters() ); } |
---|
| 126 | UnionDecl* lookup( UnionInstType *inst ) { return (UnionDecl*)lookup( inst->get_baseUnion(), inst->get_parameters() ); } |
---|
| 127 | |
---|
| 128 | private: |
---|
| 129 | /// Adds a declaration for a concrete type to the current scope |
---|
| 130 | void insert( AggregateDecl *generic, std::list< Expression* >& params, AggregateDecl *decl ) { |
---|
| 131 | ConcreteType key(generic, params); |
---|
| 132 | scopes.back()[generic].push_back( std::make_pair( key, decl ) ); |
---|
| 133 | } |
---|
| 134 | public: |
---|
| 135 | void insert( StructInstType *inst, StructDecl *decl ) { insert( inst->get_baseStruct(), inst->get_parameters(), decl ); } |
---|
| 136 | void insert( UnionInstType *inst, UnionDecl *decl ) { insert( inst->get_baseUnion(), inst->get_parameters(), decl ); } |
---|
| 137 | }; |
---|
[d8847b7] | 138 | |
---|
[258eb5c9] | 139 | /// Mutator pass that replaces concrete instantiations of generic types with actual struct declarations, scoped appropriately |
---|
| 140 | class Instantiate : public PolyMutator { |
---|
| 141 | InstantiationMap instantiations; |
---|
| 142 | UniqueName typeNamer; |
---|
| 143 | |
---|
| 144 | public: |
---|
| 145 | Instantiate() : instantiations(), typeNamer("_conc_") {} |
---|
| 146 | |
---|
| 147 | /// Mutates the whole translation unit, inserting new struct declarations as appropriate |
---|
| 148 | void mutateAll( std::list< Declaration* >& translationUnit ); |
---|
| 149 | |
---|
[d8847b7] | 150 | virtual Type* mutate( StructInstType *inst ); |
---|
| 151 | virtual Type* mutate( UnionInstType *inst ); |
---|
| 152 | |
---|
| 153 | virtual void doBeginScope(); |
---|
| 154 | virtual void doEndScope(); |
---|
| 155 | |
---|
| 156 | private: |
---|
| 157 | /// Adds a declaration to the current environment and the statements to add |
---|
| 158 | void addDeclaration( AggregateDecl *decl ) { |
---|
[258eb5c9] | 159 | std::list< Label > nolabels; |
---|
| 160 | DeclStmt *stmt = new DeclStmt( nolabels, decl ); |
---|
[d8847b7] | 161 | PolyMutator::stmtsToAdd.push_back( stmt ); |
---|
| 162 | } |
---|
| 163 | }; |
---|
| 164 | |
---|
| 165 | void instantiateGeneric( std::list< Declaration* >& translationUnit ) { |
---|
| 166 | Instantiate instantiator; |
---|
[258eb5c9] | 167 | // mutateAll( translationUnit, instantiator ); |
---|
| 168 | instantiator.mutateAll( translationUnit ); |
---|
| 169 | } |
---|
| 170 | |
---|
| 171 | void Instantiate::mutateAll( std::list< Declaration* >& translationUnit ) { |
---|
| 172 | // below copied and modified from Mutator.h:mutateAll() |
---|
| 173 | SemanticError errors; |
---|
| 174 | for ( std::list< Declaration* >::iterator decl = translationUnit.begin(); decl != translationUnit.end(); ++decl ) { |
---|
| 175 | try { |
---|
| 176 | if ( *decl ) { |
---|
| 177 | *decl = dynamic_cast< Declaration* >( (*decl)->acceptMutator( *this ) ); |
---|
| 178 | assert( *decl ); |
---|
| 179 | // account for missing top-level declarations |
---|
| 180 | for ( std::list< Statement* >::const_iterator stmt = PolyMutator::stmtsToAdd.begin(); stmt != PolyMutator::stmtsToAdd.end(); ++stmt ) { |
---|
| 181 | DeclStmt *declStmt = dynamic_cast< DeclStmt* >( *stmt ); |
---|
| 182 | assert( declStmt ); |
---|
| 183 | translationUnit.insert( decl, declStmt->get_decl() ); |
---|
| 184 | } |
---|
| 185 | PolyMutator::stmtsToAdd.clear(); |
---|
| 186 | } // if |
---|
| 187 | } catch( SemanticError &e ) { |
---|
| 188 | errors.append( e ); |
---|
| 189 | } // try |
---|
| 190 | } // for |
---|
| 191 | if ( ! errors.isEmpty() ) { |
---|
| 192 | throw errors; |
---|
| 193 | } // if |
---|
[d8847b7] | 194 | } |
---|
| 195 | |
---|
| 196 | /// Substitutes types of members of in according to baseParams => params, appending the result to out |
---|
| 197 | void substituteMembers( const std::list< Declaration* >& in, |
---|
| 198 | const std::list< TypeDecl * >& baseParams, const std::list< Expression* >& params, |
---|
| 199 | std::list< Declaration* >& out ) { |
---|
| 200 | // substitute types into new members |
---|
| 201 | TypeSubstitution subs( baseParams.begin(), baseParams.end(), params.begin() ); |
---|
| 202 | for ( std::list< Declaration* >::const_iterator member = in.begin(); member != in.end(); ++member ) { |
---|
| 203 | Declaration *newMember = (*member)->clone(); |
---|
| 204 | subs.apply(newMember); |
---|
| 205 | out.push_back( newMember ); |
---|
| 206 | } |
---|
| 207 | } |
---|
| 208 | |
---|
| 209 | Type* Instantiate::mutate( StructInstType *inst ) { |
---|
| 210 | // mutate subtypes |
---|
| 211 | Type *mutated = Mutator::mutate( inst ); |
---|
| 212 | inst = dynamic_cast< StructInstType* >( mutated ); |
---|
| 213 | if ( ! inst ) return mutated; |
---|
| 214 | |
---|
| 215 | // exit early if no need for further mutation |
---|
| 216 | if ( inst->get_parameters().empty() ) return inst; |
---|
| 217 | |
---|
| 218 | // make concrete instantiation of generic type |
---|
| 219 | StructDecl *concDecl = instantiations.lookup( inst ); |
---|
| 220 | if ( ! concDecl ) { |
---|
[ed94eac] | 221 | assert( inst->get_baseParameters() && "Base struct has parameters" ); |
---|
[d8847b7] | 222 | // set concDecl to new type, insert type declaration into statements to add |
---|
| 223 | concDecl = new StructDecl( typeNamer.newName( inst->get_name() ) ); |
---|
| 224 | substituteMembers( inst->get_baseStruct()->get_members(), |
---|
[ed94eac] | 225 | *inst->get_baseParameters(), inst->get_parameters(), |
---|
[d8847b7] | 226 | concDecl->get_members() ); |
---|
| 227 | addDeclaration( concDecl ); |
---|
| 228 | instantiations.insert( inst, concDecl ); |
---|
| 229 | } |
---|
| 230 | StructInstType *newInst = new StructInstType( inst->get_qualifiers(), concDecl->get_name() ); |
---|
| 231 | newInst->set_baseStruct( concDecl ); |
---|
| 232 | delete inst; |
---|
| 233 | return newInst; |
---|
| 234 | } |
---|
| 235 | |
---|
| 236 | Type* Instantiate::mutate( UnionInstType *inst ) { |
---|
| 237 | // mutate subtypes |
---|
| 238 | Type *mutated = Mutator::mutate( inst ); |
---|
| 239 | inst = dynamic_cast< UnionInstType* >( mutated ); |
---|
| 240 | if ( ! inst ) return mutated; |
---|
| 241 | |
---|
| 242 | // exit early if no need for further mutation |
---|
| 243 | if ( inst->get_parameters().empty() ) return inst; |
---|
| 244 | |
---|
| 245 | // make concrete instantiation of generic type |
---|
| 246 | UnionDecl *concDecl = instantiations.lookup( inst ); |
---|
| 247 | if ( ! concDecl ) { |
---|
| 248 | // set concDecl to new type, insert type declaration into statements to add |
---|
[ed94eac] | 249 | assert( inst->get_baseParameters() && "Base union has parameters" ); |
---|
[d8847b7] | 250 | concDecl = new UnionDecl( typeNamer.newName( inst->get_name() ) ); |
---|
| 251 | substituteMembers( inst->get_baseUnion()->get_members(), |
---|
[ed94eac] | 252 | *inst->get_baseParameters(), inst->get_parameters(), |
---|
[d8847b7] | 253 | concDecl->get_members() ); |
---|
| 254 | addDeclaration( concDecl ); |
---|
| 255 | instantiations.insert( inst, concDecl ); |
---|
| 256 | } |
---|
| 257 | UnionInstType *newInst = new UnionInstType( inst->get_qualifiers(), concDecl->get_name() ); |
---|
| 258 | newInst->set_baseUnion( concDecl ); |
---|
| 259 | delete inst; |
---|
| 260 | return newInst; |
---|
| 261 | } |
---|
| 262 | |
---|
| 263 | void Instantiate::doBeginScope() { |
---|
| 264 | // push a new concrete type scope |
---|
| 265 | instantiations.beginScope(); |
---|
| 266 | } |
---|
| 267 | |
---|
| 268 | void Instantiate::doEndScope() { |
---|
| 269 | // pop the last concrete type scope |
---|
| 270 | instantiations.endScope(); |
---|
| 271 | } |
---|
| 272 | |
---|
| 273 | } // namespace GenPoly |
---|
| 274 | |
---|
| 275 | // Local Variables: // |
---|
| 276 | // tab-width: 4 // |
---|
| 277 | // mode: c++ // |
---|
| 278 | // compile-command: "make install" // |
---|
| 279 | // End: // |
---|