source: src/GenPoly/InstantiateGeneric.cc@ 000b914

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

Generic instantiator now only instantiates complete types; can stub in incomplete types
  • Property mode set to 100644
File size: 11.7 KB
Line 
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.cc --
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 "DeclMutator.h"
24
25#include "ResolvExpr/typeops.h"
26#include "SymTab/Indexer.h"
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
36namespace GenPoly {
37
38 /// Key for a unique concrete type; generic base type paired with type parameter list
39 struct ConcreteType {
40 ConcreteType() : base(NULL), params() {}
41
42 ConcreteType(AggregateDecl *_base, const std::list< Type* >& _params) : base(_base), params() { cloneAll(_params, params); }
43
44 ConcreteType(const ConcreteType& that) : base(that.base), params() { cloneAll(that.params, params); }
45
46 /// Extracts types from a list of TypeExpr*
47 ConcreteType(AggregateDecl *_base, const std::list< TypeExpr* >& _params) : base(_base), params() {
48 for ( std::list< TypeExpr* >::const_iterator param = _params.begin(); param != _params.end(); ++param ) {
49 params.push_back( (*param)->get_type()->clone() );
50 }
51 }
52
53 ConcreteType& operator= (const ConcreteType& that) {
54 deleteAll( params );
55 params.clear();
56
57 base = that.base;
58 cloneAll( that.params, params );
59
60 return *this;
61 }
62
63 ~ConcreteType() { deleteAll( params ); }
64
65 bool operator== (const ConcreteType& that) const {
66 if ( base != that.base ) return false;
67
68 SymTab::Indexer dummy;
69 if ( params.size() != that.params.size() ) return false;
70 for ( std::list< Type* >::const_iterator it = params.begin(), jt = that.params.begin(); it != params.end(); ++it, ++jt ) {
71 if ( ! ResolvExpr::typesCompatible( *it, *jt, dummy ) ) return false;
72 }
73 return true;
74 }
75
76 AggregateDecl *base; ///< Base generic type
77 std::list< Type* > params; ///< Instantiation parameters
78 };
79
80 /// Maps a concrete type to the instantiated struct type, accounting for scope
81 class InstantiationMap {
82 /// Instantiation of a generic type, with key information to find it
83 struct Instantiation {
84 ConcreteType key; ///< Instantiation parameters for this type
85 AggregateDecl *decl; ///< Declaration of the instantiated generic type
86
87 Instantiation() : key(), decl(0) {}
88 Instantiation(const ConcreteType &_key, AggregateDecl *_decl) : key(_key), decl(_decl) {}
89 };
90 /// Map of generic types to instantiations of them
91 typedef std::map< AggregateDecl*, std::vector< Instantiation > > Scope;
92
93 std::vector< Scope > scopes; ///< list of scopes, from outermost to innermost
94
95 public:
96 /// Starts a new scope
97 void beginScope() {
98 Scope scope;
99 scopes.push_back(scope);
100 }
101
102 /// Ends a scope
103 void endScope() {
104 scopes.pop_back();
105 }
106
107 /// Default constructor initializes with one scope
108 InstantiationMap() { beginScope(); }
109
110 private:
111 /// Gets the declaration for the concrete instantiation of this type, assuming it has already been instantiated in the current scope.
112 /// Returns NULL on none such.
113 AggregateDecl* lookup( AggregateDecl *generic, const std::list< TypeExpr* >& params ) {
114 ConcreteType key(generic, params);
115 // scan scopes from innermost out
116 for ( std::vector< Scope >::const_reverse_iterator scope = scopes.rbegin(); scope != scopes.rend(); ++scope ) {
117 // skip scope if no instantiations of this generic type
118 Scope::const_iterator insts = scope->find( generic );
119 if ( insts == scope->end() ) continue;
120 // look through instantiations for matches to concrete type
121 for ( std::vector< Instantiation >::const_iterator inst = insts->second.begin(); inst != insts->second.end(); ++inst ) {
122 if ( inst->key == key ) return inst->decl;
123 }
124 }
125 // no matching instantiation found
126 return NULL;
127 }
128 public:
129 StructDecl* lookup( StructInstType *inst, const std::list< TypeExpr* > &typeSubs ) { return (StructDecl*)lookup( inst->get_baseStruct(), typeSubs ); }
130 UnionDecl* lookup( UnionInstType *inst, const std::list< TypeExpr* > &typeSubs ) { return (UnionDecl*)lookup( inst->get_baseUnion(), typeSubs ); }
131
132 private:
133 /// Adds a declaration for a concrete type to the current scope
134 void insert( AggregateDecl *generic, const std::list< TypeExpr* > &params, AggregateDecl *decl ) {
135 ConcreteType key(generic, params);
136 scopes.back()[generic].push_back( Instantiation( key, decl ) );
137 }
138 public:
139 void insert( StructInstType *inst, const std::list< TypeExpr* > &typeSubs, StructDecl *decl ) { insert( inst->get_baseStruct(), typeSubs, decl ); }
140 void insert( UnionInstType *inst, const std::list< TypeExpr* > &typeSubs, UnionDecl *decl ) { insert( inst->get_baseUnion(), typeSubs, decl ); }
141 };
142
143 /// Mutator pass that replaces concrete instantiations of generic types with actual struct declarations, scoped appropriately
144 class Instantiate : public DeclMutator {
145 InstantiationMap instantiations;
146 UniqueName typeNamer;
147
148 public:
149 Instantiate() : DeclMutator(), instantiations(), typeNamer("_conc_") {}
150
151// virtual Declaration* mutate( StructDecl *aggregateDecl );
152// virtual Declaration* mutate( UnionDecl *aggregateDecl );
153
154 virtual Type* mutate( StructInstType *inst );
155 virtual Type* mutate( UnionInstType *inst );
156
157 virtual void doBeginScope();
158 virtual void doEndScope();
159 };
160
161 void instantiateGeneric( std::list< Declaration* >& translationUnit ) {
162 Instantiate instantiator;
163 instantiator.mutateDeclarationList( translationUnit );
164 }
165
166 /// Makes substitutions of params into baseParams; returns true if all parameters substituted for a concrete type
167 bool makeSubstitutions( const std::list< TypeDecl* >& baseParams, const std::list< Expression* >& params, std::list< TypeExpr* >& out ) {
168 bool allConcrete = true; // will finish the substitution list even if they're not all concrete
169
170 // substitute concrete types for given parameters, and incomplete types for placeholders
171 std::list< TypeDecl* >::const_iterator baseParam = baseParams.begin();
172 std::list< Expression* >::const_iterator param = params.begin();
173 for ( ; baseParam != baseParams.end() && param != params.end(); ++baseParam, ++param ) {
174 switch ( (*baseParam)->get_kind() ) {
175 case TypeDecl::Any: { // any type is a valid substitution here; complete types can be used to instantiate generics
176 TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param );
177 assert(paramType && "Aggregate parameters should be type expressions");
178 out.push_back( paramType->clone() );
179 // check that the substituted type isn't a type variable itself
180 if ( dynamic_cast< TypeInstType* >( paramType->get_type() ) ) {
181 allConcrete = false;
182 }
183 break;
184 }
185 case TypeDecl::Dtype: // dtype can be consistently replaced with void [only pointers, which become void*]
186 out.push_back( new TypeExpr( new VoidType( Type::Qualifiers() ) ) );
187 break;
188 case TypeDecl::Ftype: // pointer-to-ftype can be consistently replaced with void (*)(void) [similar to dtype]
189 out.push_back( new TypeExpr( new FunctionType( Type::Qualifiers(), false ) ) );
190 break;
191 }
192 }
193
194 // if not enough parameters given, substitute remaining incomplete types for placeholders
195 for ( ; baseParam != baseParams.end(); ++baseParam ) {
196 switch ( (*baseParam)->get_kind() ) {
197 case TypeDecl::Any: // no more substitutions here, fail early
198 return false;
199 case TypeDecl::Dtype: // dtype can be consistently replaced with void [only pointers, which become void*]
200 out.push_back( new TypeExpr( new VoidType( Type::Qualifiers() ) ) );
201 break;
202 case TypeDecl::Ftype: // pointer-to-ftype can be consistently replaced with void (*)(void) [similar to dtype]
203 out.push_back( new TypeExpr( new FunctionType( Type::Qualifiers(), false ) ) );
204 break;
205 }
206 }
207
208 return allConcrete;
209 }
210
211 /// Substitutes types of members of in according to baseParams => typeSubs, appending the result to out
212 void substituteMembers( const std::list< Declaration* >& in, const std::list< TypeDecl* >& baseParams, const std::list< TypeExpr* >& typeSubs,
213 std::list< Declaration* >& out ) {
214 // substitute types into new members
215 TypeSubstitution subs( baseParams.begin(), baseParams.end(), typeSubs.begin() );
216 for ( std::list< Declaration* >::const_iterator member = in.begin(); member != in.end(); ++member ) {
217 Declaration *newMember = (*member)->clone();
218 subs.apply(newMember);
219 out.push_back( newMember );
220 }
221 }
222
223 Type* Instantiate::mutate( StructInstType *inst ) {
224 // mutate subtypes
225 Type *mutated = Mutator::mutate( inst );
226 inst = dynamic_cast< StructInstType* >( mutated );
227 if ( ! inst ) return mutated;
228
229 // exit early if no need for further mutation
230 if ( inst->get_parameters().empty() ) return inst;
231 assert( inst->get_baseParameters() && "Base struct has parameters" );
232
233 // check if type can be concretely instantiated; put substitutions into typeSubs
234 std::list< TypeExpr* > typeSubs;
235 if ( ! makeSubstitutions( *inst->get_baseParameters(), inst->get_parameters(), typeSubs ) ) {
236 deleteAll( typeSubs );
237 return inst;
238 }
239
240 // make concrete instantiation of generic type
241 StructDecl *concDecl = instantiations.lookup( inst, typeSubs );
242 if ( ! concDecl ) {
243 // set concDecl to new type, insert type declaration into statements to add
244 concDecl = new StructDecl( typeNamer.newName( inst->get_name() ) );
245 substituteMembers( inst->get_baseStruct()->get_members(), *inst->get_baseParameters(), typeSubs, concDecl->get_members() );
246 DeclMutator::addDeclaration( concDecl );
247 instantiations.insert( inst, typeSubs, concDecl );
248 }
249 StructInstType *newInst = new StructInstType( inst->get_qualifiers(), concDecl->get_name() );
250 newInst->set_baseStruct( concDecl );
251
252 deleteAll( typeSubs );
253 delete inst;
254 return newInst;
255 }
256
257 Type* Instantiate::mutate( UnionInstType *inst ) {
258 // mutate subtypes
259 Type *mutated = Mutator::mutate( inst );
260 inst = dynamic_cast< UnionInstType* >( mutated );
261 if ( ! inst ) return mutated;
262
263 // exit early if no need for further mutation
264 if ( inst->get_parameters().empty() ) return inst;
265 assert( inst->get_baseParameters() && "Base union has parameters" );
266
267 // check if type can be concretely instantiated; put substitutions into typeSubs
268 std::list< TypeExpr* > typeSubs;
269 if ( ! makeSubstitutions( *inst->get_baseParameters(), inst->get_parameters(), typeSubs ) ) {
270 deleteAll( typeSubs );
271 return inst;
272 }
273
274 // make concrete instantiation of generic type
275 UnionDecl *concDecl = instantiations.lookup( inst, typeSubs );
276 if ( ! concDecl ) {
277 // set concDecl to new type, insert type declaration into statements to add
278 concDecl = new UnionDecl( typeNamer.newName( inst->get_name() ) );
279 substituteMembers( inst->get_baseUnion()->get_members(), *inst->get_baseParameters(), typeSubs, concDecl->get_members() );
280 DeclMutator::addDeclaration( concDecl );
281 instantiations.insert( inst, typeSubs, concDecl );
282 }
283 UnionInstType *newInst = new UnionInstType( inst->get_qualifiers(), concDecl->get_name() );
284 newInst->set_baseUnion( concDecl );
285
286 deleteAll( typeSubs );
287 delete inst;
288 return newInst;
289 }
290
291 void Instantiate::doBeginScope() {
292 DeclMutator::doBeginScope();
293 // push a new concrete type scope
294 instantiations.beginScope();
295 }
296
297 void Instantiate::doEndScope() {
298 DeclMutator::doEndScope();
299 // pop the last concrete type scope
300 instantiations.endScope();
301 }
302
303} // namespace GenPoly
304
305// Local Variables: //
306// tab-width: 4 //
307// mode: c++ //
308// compile-command: "make install" //
309// End: //
Note: See TracBrowser for help on using the repository browser.