[ea5daeb] | 1 | // |
---|
| 2 | // Cforall Version 1.0.0 Copyright (C) 2016 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.cc -- |
---|
| 8 | // |
---|
| 9 | // Author : Aaron B. Moss |
---|
| 10 | // Created On : Thu Aug 04 18:33:00 2016 |
---|
| 11 | // Last Modified By : Aaron B. Moss |
---|
| 12 | // Last Modified On : Thu Aug 04 18:33:00 2016 |
---|
| 13 | // Update Count : 1 |
---|
| 14 | // |
---|
| 15 | |
---|
| 16 | #include <cassert> |
---|
| 17 | #include <list> |
---|
| 18 | #include <utility> |
---|
| 19 | #include <vector> |
---|
| 20 | |
---|
| 21 | #include "InstantiateGeneric.h" |
---|
| 22 | |
---|
| 23 | #include "DeclMutator.h" |
---|
| 24 | #include "GenPoly.h" |
---|
| 25 | #include "ScopedMap.h" |
---|
| 26 | |
---|
| 27 | #include "ResolvExpr/typeops.h" |
---|
| 28 | |
---|
| 29 | #include "SynTree/Declaration.h" |
---|
| 30 | #include "SynTree/Expression.h" |
---|
| 31 | #include "SynTree/Type.h" |
---|
| 32 | |
---|
| 33 | #include "Common/UniqueName.h" |
---|
| 34 | #include "Common/utility.h" |
---|
| 35 | |
---|
| 36 | namespace GenPoly { |
---|
| 37 | |
---|
| 38 | /// Abstracts type equality for a list of parameter types |
---|
| 39 | struct TypeList { |
---|
| 40 | TypeList() : params() {} |
---|
| 41 | TypeList( const std::list< Type* > &_params ) : params() { cloneAll(_params, params); } |
---|
| 42 | TypeList( std::list< Type* > &&_params ) : params( _params ) {} |
---|
| 43 | |
---|
| 44 | TypeList( const TypeList &that ) : params() { cloneAll(that.params, params); } |
---|
| 45 | TypeList( TypeList &&that ) : params( std::move( that.params ) ) {} |
---|
| 46 | |
---|
| 47 | /// Extracts types from a list of TypeExpr* |
---|
| 48 | TypeList( const std::list< TypeExpr* >& _params ) : params() { |
---|
| 49 | for ( std::list< TypeExpr* >::const_iterator param = _params.begin(); param != _params.end(); ++param ) { |
---|
| 50 | params.push_back( (*param)->get_type()->clone() ); |
---|
| 51 | } |
---|
| 52 | } |
---|
| 53 | |
---|
| 54 | TypeList& operator= ( const TypeList &that ) { |
---|
| 55 | deleteAll( params ); |
---|
| 56 | |
---|
| 57 | params.clear(); |
---|
| 58 | cloneAll( that.params, params ); |
---|
| 59 | |
---|
| 60 | return *this; |
---|
| 61 | } |
---|
| 62 | |
---|
| 63 | TypeList& operator= ( TypeList &&that ) { |
---|
| 64 | deleteAll( params ); |
---|
| 65 | |
---|
| 66 | params = std::move( that.params ); |
---|
| 67 | |
---|
| 68 | return *this; |
---|
| 69 | } |
---|
| 70 | |
---|
| 71 | ~TypeList() { deleteAll( params ); } |
---|
| 72 | |
---|
| 73 | bool operator== ( const TypeList& that ) const { |
---|
| 74 | if ( params.size() != that.params.size() ) return false; |
---|
| 75 | |
---|
| 76 | SymTab::Indexer dummy; |
---|
| 77 | for ( std::list< Type* >::const_iterator it = params.begin(), jt = that.params.begin(); it != params.end(); ++it, ++jt ) { |
---|
| 78 | if ( ! ResolvExpr::typesCompatible( *it, *jt, dummy ) ) return false; |
---|
| 79 | } |
---|
| 80 | return true; |
---|
| 81 | } |
---|
| 82 | |
---|
| 83 | std::list< Type* > params; ///< Instantiation parameters |
---|
| 84 | }; |
---|
| 85 | |
---|
| 86 | /// Maps a key and a TypeList to the some value, accounting for scope |
---|
| 87 | template< typename Key, typename Value > |
---|
| 88 | class InstantiationMap { |
---|
| 89 | /// Wraps value for a specific (Key, TypeList) combination |
---|
| 90 | typedef std::pair< TypeList, Value* > Instantiation; |
---|
| 91 | /// List of TypeLists paired with their appropriate values |
---|
| 92 | typedef std::vector< Instantiation > ValueList; |
---|
| 93 | /// Underlying map type; maps keys to a linear list of corresponding TypeLists and values |
---|
| 94 | typedef ScopedMap< Key*, ValueList > InnerMap; |
---|
| 95 | |
---|
| 96 | InnerMap instantiations; ///< instantiations |
---|
| 97 | |
---|
| 98 | public: |
---|
| 99 | /// Starts a new scope |
---|
| 100 | void beginScope() { instantiations.beginScope(); } |
---|
| 101 | |
---|
| 102 | /// Ends a scope |
---|
| 103 | void endScope() { instantiations.endScope(); } |
---|
| 104 | |
---|
| 105 | /// Gets the value for the (key, typeList) pair, returns NULL on none such. |
---|
| 106 | Value *lookup( Key *key, const std::list< TypeExpr* >& params ) const { |
---|
| 107 | TypeList typeList( params ); |
---|
| 108 | |
---|
| 109 | // scan scopes for matches to the key |
---|
| 110 | for ( typename InnerMap::const_iterator insts = instantiations.find( key ); insts != instantiations.end(); insts = instantiations.findNext( insts, key ) ) { |
---|
| 111 | for ( typename ValueList::const_reverse_iterator inst = insts->second.rbegin(); inst != insts->second.rend(); ++inst ) { |
---|
| 112 | if ( inst->first == typeList ) return inst->second; |
---|
| 113 | } |
---|
| 114 | } |
---|
| 115 | // no matching instantiations found |
---|
| 116 | return 0; |
---|
| 117 | } |
---|
| 118 | |
---|
| 119 | /// Adds a value for a (key, typeList) pair to the current scope |
---|
| 120 | void insert( Key *key, const std::list< TypeExpr* > ¶ms, Value *value ) { |
---|
| 121 | instantiations[ key ].push_back( Instantiation( TypeList( params ), value ) ); |
---|
| 122 | } |
---|
| 123 | }; |
---|
| 124 | |
---|
| 125 | /// Mutator pass that replaces concrete instantiations of generic types with actual struct declarations, scoped appropriately |
---|
| 126 | class GenericInstantiator : public DeclMutator { |
---|
| 127 | /// Map of (generic type, parameter list) pairs to concrete type instantiations |
---|
| 128 | InstantiationMap< AggregateDecl, AggregateDecl > instantiations; |
---|
| 129 | /// Namer for concrete types |
---|
| 130 | UniqueName typeNamer; |
---|
| 131 | |
---|
| 132 | public: |
---|
| 133 | GenericInstantiator() : DeclMutator(), instantiations(), typeNamer("_conc_") {} |
---|
| 134 | |
---|
| 135 | virtual Type* mutate( StructInstType *inst ); |
---|
| 136 | virtual Type* mutate( UnionInstType *inst ); |
---|
| 137 | |
---|
| 138 | virtual void doBeginScope(); |
---|
| 139 | virtual void doEndScope(); |
---|
| 140 | private: |
---|
| 141 | /// Wrap instantiation lookup for structs |
---|
| 142 | StructDecl* lookup( StructInstType *inst, const std::list< TypeExpr* > &typeSubs ) { return (StructDecl*)instantiations.lookup( inst->get_baseStruct(), typeSubs ); } |
---|
| 143 | /// Wrap instantiation lookup for unions |
---|
| 144 | UnionDecl* lookup( UnionInstType *inst, const std::list< TypeExpr* > &typeSubs ) { return (UnionDecl*)instantiations.lookup( inst->get_baseUnion(), typeSubs ); } |
---|
| 145 | /// Wrap instantiation insertion for structs |
---|
| 146 | void insert( StructInstType *inst, const std::list< TypeExpr* > &typeSubs, StructDecl *decl ) { instantiations.insert( inst->get_baseStruct(), typeSubs, decl ); } |
---|
| 147 | /// Wrap instantiation insertion for unions |
---|
| 148 | void insert( UnionInstType *inst, const std::list< TypeExpr* > &typeSubs, UnionDecl *decl ) { instantiations.insert( inst->get_baseUnion(), typeSubs, decl ); } |
---|
| 149 | }; |
---|
| 150 | |
---|
| 151 | void instantiateGeneric( std::list< Declaration* > &translationUnit ) { |
---|
| 152 | GenericInstantiator instantiator; |
---|
| 153 | instantiator.mutateDeclarationList( translationUnit ); |
---|
| 154 | } |
---|
| 155 | |
---|
| 156 | //////////////////////////////////////// GenericInstantiator ////////////////////////////////////////////////// |
---|
| 157 | |
---|
| 158 | /// Possible options for a given specialization of a generic type |
---|
| 159 | enum class genericType { |
---|
| 160 | dtypeStatic, ///< Concrete instantiation based solely on {d,f}type-to-void conversions |
---|
| 161 | concrete, ///< Concrete instantiation requiring at least one parameter type |
---|
| 162 | dynamic ///< No concrete instantiation |
---|
| 163 | }; |
---|
| 164 | |
---|
| 165 | genericType& operator |= ( genericType& gt, const genericType& ht ) { |
---|
| 166 | switch ( gt ) { |
---|
| 167 | case genericType::dtypeStatic: |
---|
| 168 | gt = ht; |
---|
| 169 | break; |
---|
| 170 | case genericType::concrete: |
---|
| 171 | if ( ht == genericType::dynamic ) { gt = genericType::dynamic; } |
---|
| 172 | break; |
---|
| 173 | case genericType::dynamic: |
---|
| 174 | // nothing possible |
---|
| 175 | break; |
---|
| 176 | } |
---|
| 177 | return gt; |
---|
| 178 | } |
---|
| 179 | |
---|
| 180 | /// Makes substitutions of params into baseParams; returns true if all parameters substituted for a concrete type |
---|
| 181 | genericType makeSubstitutions( const std::list< TypeDecl* >& baseParams, const std::list< Expression* >& params, std::list< TypeExpr* >& out ) { |
---|
| 182 | genericType gt = genericType::dtypeStatic; |
---|
| 183 | |
---|
| 184 | // substitute concrete types for given parameters, and incomplete types for placeholders |
---|
| 185 | std::list< TypeDecl* >::const_iterator baseParam = baseParams.begin(); |
---|
| 186 | std::list< Expression* >::const_iterator param = params.begin(); |
---|
| 187 | for ( ; baseParam != baseParams.end() && param != params.end(); ++baseParam, ++param ) { |
---|
| 188 | TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param ); |
---|
| 189 | assert(paramType && "Aggregate parameters should be type expressions"); |
---|
| 190 | |
---|
| 191 | switch ( (*baseParam)->get_kind() ) { |
---|
| 192 | case TypeDecl::Any: { |
---|
| 193 | // substitute parameter for otype; makes the type concrete or dynamic depending on the parameter |
---|
| 194 | out.push_back( paramType->clone() ); |
---|
| 195 | gt |= isPolyType( paramType->get_type() ) ? genericType::dynamic : genericType::concrete; |
---|
| 196 | break; |
---|
| 197 | } |
---|
| 198 | case TypeDecl::Dtype: |
---|
| 199 | // can pretend that any dtype is `void` |
---|
| 200 | out.push_back( new TypeExpr( new VoidType( Type::Qualifiers() ) ) ); |
---|
| 201 | break; |
---|
| 202 | case TypeDecl::Ftype: |
---|
| 203 | // can pretend that any ftype is `void (*)(void)` |
---|
| 204 | out.push_back( new TypeExpr( new FunctionType( Type::Qualifiers(), false ) ) ); |
---|
| 205 | break; |
---|
| 206 | } |
---|
| 207 | } |
---|
| 208 | |
---|
| 209 | assert( baseParam == baseParams.end() && param == params.end() && "Type parameters should match type variables" ); |
---|
| 210 | return gt; |
---|
| 211 | } |
---|
| 212 | |
---|
| 213 | /// Substitutes types of members of in according to baseParams => typeSubs, appending the result to out |
---|
| 214 | void substituteMembers( const std::list< Declaration* >& in, const std::list< TypeDecl* >& baseParams, const std::list< TypeExpr* >& typeSubs, |
---|
| 215 | std::list< Declaration* >& out ) { |
---|
| 216 | // substitute types into new members |
---|
| 217 | TypeSubstitution subs( baseParams.begin(), baseParams.end(), typeSubs.begin() ); |
---|
| 218 | for ( std::list< Declaration* >::const_iterator member = in.begin(); member != in.end(); ++member ) { |
---|
| 219 | Declaration *newMember = (*member)->clone(); |
---|
| 220 | subs.apply(newMember); |
---|
| 221 | out.push_back( newMember ); |
---|
| 222 | } |
---|
| 223 | } |
---|
| 224 | |
---|
| 225 | Type* GenericInstantiator::mutate( StructInstType *inst ) { |
---|
| 226 | // mutate subtypes |
---|
| 227 | Type *mutated = Mutator::mutate( inst ); |
---|
| 228 | inst = dynamic_cast< StructInstType* >( mutated ); |
---|
| 229 | if ( ! inst ) return mutated; |
---|
| 230 | |
---|
| 231 | // exit early if no need for further mutation |
---|
| 232 | if ( inst->get_parameters().empty() ) return inst; |
---|
| 233 | assert( inst->get_baseParameters() && "Base struct has parameters" ); |
---|
| 234 | |
---|
| 235 | // check if type can be concretely instantiated; put substitutions into typeSubs |
---|
| 236 | std::list< TypeExpr* > typeSubs; |
---|
| 237 | genericType gt = makeSubstitutions( *inst->get_baseParameters(), inst->get_parameters(), typeSubs ); |
---|
| 238 | switch ( gt ) { |
---|
| 239 | case genericType::dtypeStatic: // TODO strip params off original decl and reuse here |
---|
| 240 | case genericType::concrete: |
---|
| 241 | { |
---|
| 242 | // make concrete instantiation of generic type |
---|
| 243 | StructDecl *concDecl = lookup( inst, typeSubs ); |
---|
| 244 | if ( ! concDecl ) { |
---|
| 245 | // set concDecl to new type, insert type declaration into statements to add |
---|
| 246 | concDecl = new StructDecl( typeNamer.newName( inst->get_name() ) ); |
---|
| 247 | substituteMembers( inst->get_baseStruct()->get_members(), *inst->get_baseParameters(), typeSubs, concDecl->get_members() ); |
---|
| 248 | DeclMutator::addDeclaration( concDecl ); |
---|
| 249 | insert( inst, typeSubs, concDecl ); |
---|
| 250 | } |
---|
| 251 | StructInstType *newInst = new StructInstType( inst->get_qualifiers(), concDecl->get_name() ); |
---|
| 252 | newInst->set_baseStruct( concDecl ); |
---|
| 253 | |
---|
| 254 | delete inst; |
---|
| 255 | inst = newInst; |
---|
| 256 | break; |
---|
| 257 | } |
---|
| 258 | |
---|
| 259 | case genericType::dynamic: |
---|
| 260 | // do nothing |
---|
| 261 | break; |
---|
| 262 | } |
---|
| 263 | |
---|
| 264 | deleteAll( typeSubs ); |
---|
| 265 | return inst; |
---|
| 266 | } |
---|
| 267 | |
---|
| 268 | Type* GenericInstantiator::mutate( UnionInstType *inst ) { |
---|
| 269 | // mutate subtypes |
---|
| 270 | Type *mutated = Mutator::mutate( inst ); |
---|
| 271 | inst = dynamic_cast< UnionInstType* >( mutated ); |
---|
| 272 | if ( ! inst ) return mutated; |
---|
| 273 | |
---|
| 274 | // exit early if no need for further mutation |
---|
| 275 | if ( inst->get_parameters().empty() ) return inst; |
---|
| 276 | assert( inst->get_baseParameters() && "Base union has parameters" ); |
---|
| 277 | |
---|
| 278 | // check if type can be concretely instantiated; put substitutions into typeSubs |
---|
| 279 | std::list< TypeExpr* > typeSubs; |
---|
| 280 | genericType gt = makeSubstitutions( *inst->get_baseParameters(), inst->get_parameters(), typeSubs ); |
---|
| 281 | switch ( gt ) { |
---|
| 282 | case genericType::dtypeStatic: // TODO strip params off original decls and reuse here |
---|
| 283 | case genericType::concrete: |
---|
| 284 | { |
---|
| 285 | // make concrete instantiation of generic type |
---|
| 286 | UnionDecl *concDecl = lookup( inst, typeSubs ); |
---|
| 287 | if ( ! concDecl ) { |
---|
| 288 | // set concDecl to new type, insert type declaration into statements to add |
---|
| 289 | concDecl = new UnionDecl( typeNamer.newName( inst->get_name() ) ); |
---|
| 290 | substituteMembers( inst->get_baseUnion()->get_members(), *inst->get_baseParameters(), typeSubs, concDecl->get_members() ); |
---|
| 291 | DeclMutator::addDeclaration( concDecl ); |
---|
| 292 | insert( inst, typeSubs, concDecl ); |
---|
| 293 | } |
---|
| 294 | UnionInstType *newInst = new UnionInstType( inst->get_qualifiers(), concDecl->get_name() ); |
---|
| 295 | newInst->set_baseUnion( concDecl ); |
---|
| 296 | |
---|
| 297 | delete inst; |
---|
| 298 | inst = newInst; |
---|
| 299 | break; |
---|
| 300 | } |
---|
| 301 | case genericType::dynamic: |
---|
| 302 | // do nothing |
---|
| 303 | break; |
---|
| 304 | } |
---|
| 305 | |
---|
| 306 | deleteAll( typeSubs ); |
---|
| 307 | return inst; |
---|
| 308 | } |
---|
| 309 | |
---|
| 310 | void GenericInstantiator::doBeginScope() { |
---|
| 311 | DeclMutator::doBeginScope(); |
---|
| 312 | instantiations.beginScope(); |
---|
| 313 | } |
---|
| 314 | |
---|
| 315 | void GenericInstantiator::doEndScope() { |
---|
| 316 | DeclMutator::doEndScope(); |
---|
| 317 | instantiations.endScope(); |
---|
| 318 | } |
---|
| 319 | |
---|
| 320 | } // namespace GenPoly |
---|
| 321 | |
---|
| 322 | // Local Variables: // |
---|
| 323 | // tab-width: 4 // |
---|
| 324 | // mode: c++ // |
---|
| 325 | // compile-command: "make install" // |
---|
| 326 | // End: // |
---|