source: src/GenPoly/InstantiateGeneric.cc@ a6dd5b0

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors ctor deferred_resn demangler enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox memory new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new with_gc
Last change on this file since a6dd5b0 was ea5daeb, checked in by Aaron Moss <a3moss@…>, 9 years ago

Move generic instantiation earlier
  • Property mode set to 100644
File size: 11.6 KB
Line 
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
36namespace 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* > &params, 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: //
Note: See TracBrowser for help on using the repository browser.