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 | |
---|
25 | #include "SymTab/TypeEquality.h" |
---|
26 | #include "SynTree/Declaration.h" |
---|
27 | #include "SynTree/Mutator.h" |
---|
28 | #include "SynTree/Statement.h" |
---|
29 | #include "SynTree/Type.h" |
---|
30 | #include "SynTree/TypeSubstitution.h" |
---|
31 | |
---|
32 | #include "UniqueName.h" |
---|
33 | #include "utility.h" |
---|
34 | |
---|
35 | namespace GenPoly { |
---|
36 | |
---|
37 | class Instantiate : public PolyMutator { |
---|
38 | public: |
---|
39 | /// Key for a unique concrete type; generic base type paired with type parameter list |
---|
40 | struct ConcreteType { |
---|
41 | ConcreteType() : base(NULL), params() {} |
---|
42 | |
---|
43 | ConcreteType(AggregateDecl *_base, const std::list< Type* >& _params) : base(_base), params() { cloneAll(_params, params); } |
---|
44 | |
---|
45 | ConcreteType(const ConcreteType& that) : base(that.base), params() { cloneAll(that.params, params); } |
---|
46 | |
---|
47 | /// Extracts types from a list of Expression* (which should be TypeExpr*) |
---|
48 | ConcreteType(AggregateDecl *_base, const std::list< Expression* >& _params) : base(_base), params() { |
---|
49 | for ( std::list< Expression* >::const_iterator it = _params.begin(); it != _params.end(); ++it ) { |
---|
50 | TypeExpr *param = dynamic_cast< TypeExpr* >(*it); |
---|
51 | assert(param && "Aggregate parameters should be type expressions"); |
---|
52 | params.push_back( param->get_type()->clone() ); |
---|
53 | } |
---|
54 | } |
---|
55 | |
---|
56 | ConcreteType& operator= (const ConcreteType& that) { |
---|
57 | deleteAll( params ); |
---|
58 | params.clear(); |
---|
59 | |
---|
60 | base = that.base; |
---|
61 | cloneAll( that.params, params ); |
---|
62 | |
---|
63 | return *this; |
---|
64 | } |
---|
65 | |
---|
66 | ~ConcreteType() { deleteAll( params ); } |
---|
67 | |
---|
68 | bool operator== (const ConcreteType& that) const { |
---|
69 | if ( base != that.base ) return false; |
---|
70 | if ( params.size() != that.params.size() ) return false; |
---|
71 | for ( std::list< Type* >::const_iterator it = params.begin(), jt = that.params.begin(); it != params.end(); ++it, ++jt ) { |
---|
72 | if ( ! SymTab::typeEquals(*it, *jt) ) return false; |
---|
73 | } |
---|
74 | return true; |
---|
75 | } |
---|
76 | |
---|
77 | AggregateDecl *base; ///< Base generic type |
---|
78 | std::list< Type* > params; ///< Instantiation parameters |
---|
79 | }; |
---|
80 | |
---|
81 | /// Maps a concrete type to the instantiated struct type, accounting for scope |
---|
82 | class InstantiationMap { |
---|
83 | /// Pair of concrete type and declaration that instantiates it |
---|
84 | typedef std::pair< ConcreteType, AggregateDecl* > Instantiation; |
---|
85 | /// Map of generic types to instantiations of them |
---|
86 | typedef std::map< AggregateDecl*, std::vector< Instantiation > > Scope; |
---|
87 | |
---|
88 | std::vector< Scope > scopes; ///< list of scopes, from outermost to innermost |
---|
89 | |
---|
90 | public: |
---|
91 | /// Starts a new scope |
---|
92 | void beginScope() { |
---|
93 | Scope scope; |
---|
94 | scopes.push_back(scope); |
---|
95 | } |
---|
96 | |
---|
97 | /// Ends a scope |
---|
98 | void endScope() { |
---|
99 | scopes.pop_back(); |
---|
100 | } |
---|
101 | |
---|
102 | /// Default constructor initializes with one scope |
---|
103 | InstantiationMap() { beginScope(); } |
---|
104 | |
---|
105 | private: |
---|
106 | /// Gets the declaration for the concrete instantiation of this type, assuming it has already been instantiated in the current scope. |
---|
107 | /// Returns NULL on none such. |
---|
108 | AggregateDecl* lookup( AggregateDecl *generic, std::list< Expression* >& params ) { |
---|
109 | ConcreteType key(generic, params); |
---|
110 | // scan scopes from innermost out |
---|
111 | for ( std::vector< Scope >::const_reverse_iterator scope = scopes.rbegin(); scope != scopes.rend(); ++scope ) { |
---|
112 | // skip scope if no instantiations of this generic type |
---|
113 | Scope::const_iterator insts = scope->find( generic ); |
---|
114 | if ( insts == scope->end() ) continue; |
---|
115 | // look through instantiations for matches to concrete type |
---|
116 | for ( std::vector< Instantiation >::const_iterator inst = insts->second.begin(); inst != insts->second.end(); ++inst ) { |
---|
117 | if ( inst->first == key ) return inst->second; |
---|
118 | } |
---|
119 | } |
---|
120 | // no matching instantiation found |
---|
121 | return NULL; |
---|
122 | } |
---|
123 | public: |
---|
124 | StructDecl* lookup( StructInstType *inst ) { return (StructDecl*)lookup( inst->get_baseStruct(), inst->get_parameters() ); } |
---|
125 | UnionDecl* lookup( UnionInstType *inst ) { return (UnionDecl*)lookup( inst->get_baseUnion(), inst->get_parameters() ); } |
---|
126 | |
---|
127 | private: |
---|
128 | /// Adds a declaration for a concrete type to the current scope |
---|
129 | void insert( AggregateDecl *generic, std::list< Expression* >& params, AggregateDecl *decl ) { |
---|
130 | ConcreteType key(generic, params); |
---|
131 | scopes.back()[generic].push_back( std::make_pair( key, decl ) ); |
---|
132 | } |
---|
133 | public: |
---|
134 | void insert( StructInstType *inst, StructDecl *decl ) { insert( inst->get_baseStruct(), inst->get_parameters(), decl ); } |
---|
135 | void insert( UnionInstType *inst, UnionDecl *decl ) { insert( inst->get_baseUnion(), inst->get_parameters(), decl ); } |
---|
136 | }; |
---|
137 | |
---|
138 | virtual Type* mutate( StructInstType *inst ); |
---|
139 | virtual Type* mutate( UnionInstType *inst ); |
---|
140 | |
---|
141 | virtual void doBeginScope(); |
---|
142 | virtual void doEndScope(); |
---|
143 | |
---|
144 | private: |
---|
145 | /// Adds a declaration to the current environment and the statements to add |
---|
146 | void addDeclaration( AggregateDecl *decl ) { |
---|
147 | std::list< Label > labels; |
---|
148 | DeclStmt *stmt = new DeclStmt( labels, decl ); |
---|
149 | PolyMutator::stmtsToAdd.push_back( stmt ); |
---|
150 | } |
---|
151 | |
---|
152 | InstantiationMap instantiations; |
---|
153 | UniqueName typeNamer; |
---|
154 | }; |
---|
155 | |
---|
156 | void instantiateGeneric( std::list< Declaration* >& translationUnit ) { |
---|
157 | Instantiate instantiator; |
---|
158 | mutateAll( translationUnit, instantiator ); |
---|
159 | } |
---|
160 | |
---|
161 | /// Substitutes types of members of in according to baseParams => params, appending the result to out |
---|
162 | void substituteMembers( const std::list< Declaration* >& in, |
---|
163 | const std::list< TypeDecl * >& baseParams, const std::list< Expression* >& params, |
---|
164 | std::list< Declaration* >& out ) { |
---|
165 | // substitute types into new members |
---|
166 | TypeSubstitution subs( baseParams.begin(), baseParams.end(), params.begin() ); |
---|
167 | for ( std::list< Declaration* >::const_iterator member = in.begin(); member != in.end(); ++member ) { |
---|
168 | Declaration *newMember = (*member)->clone(); |
---|
169 | subs.apply(newMember); |
---|
170 | out.push_back( newMember ); |
---|
171 | } |
---|
172 | } |
---|
173 | |
---|
174 | Type* Instantiate::mutate( StructInstType *inst ) { |
---|
175 | // mutate subtypes |
---|
176 | Type *mutated = Mutator::mutate( inst ); |
---|
177 | inst = dynamic_cast< StructInstType* >( mutated ); |
---|
178 | if ( ! inst ) return mutated; |
---|
179 | |
---|
180 | // exit early if no need for further mutation |
---|
181 | if ( inst->get_parameters().empty() ) return inst; |
---|
182 | |
---|
183 | // make concrete instantiation of generic type |
---|
184 | StructDecl *concDecl = instantiations.lookup( inst ); |
---|
185 | if ( ! concDecl ) { |
---|
186 | // set concDecl to new type, insert type declaration into statements to add |
---|
187 | concDecl = new StructDecl( typeNamer.newName( inst->get_name() ) ); |
---|
188 | substituteMembers( inst->get_baseStruct()->get_members(), |
---|
189 | inst->get_baseParameters(), inst->get_parameters(), |
---|
190 | concDecl->get_members() ); |
---|
191 | addDeclaration( concDecl ); |
---|
192 | instantiations.insert( inst, concDecl ); |
---|
193 | } |
---|
194 | StructInstType *newInst = new StructInstType( inst->get_qualifiers(), concDecl->get_name() ); |
---|
195 | newInst->set_baseStruct( concDecl ); |
---|
196 | delete inst; |
---|
197 | return newInst; |
---|
198 | } |
---|
199 | |
---|
200 | Type* Instantiate::mutate( UnionInstType *inst ) { |
---|
201 | // mutate subtypes |
---|
202 | Type *mutated = Mutator::mutate( inst ); |
---|
203 | inst = dynamic_cast< UnionInstType* >( mutated ); |
---|
204 | if ( ! inst ) return mutated; |
---|
205 | |
---|
206 | // exit early if no need for further mutation |
---|
207 | if ( inst->get_parameters().empty() ) return inst; |
---|
208 | |
---|
209 | // make concrete instantiation of generic type |
---|
210 | UnionDecl *concDecl = instantiations.lookup( inst ); |
---|
211 | if ( ! concDecl ) { |
---|
212 | // set concDecl to new type, insert type declaration into statements to add |
---|
213 | concDecl = new UnionDecl( typeNamer.newName( inst->get_name() ) ); |
---|
214 | substituteMembers( inst->get_baseUnion()->get_members(), |
---|
215 | inst->get_baseParameters(), inst->get_parameters(), |
---|
216 | concDecl->get_members() ); |
---|
217 | addDeclaration( concDecl ); |
---|
218 | instantiations.insert( inst, concDecl ); |
---|
219 | } |
---|
220 | UnionInstType *newInst = new UnionInstType( inst->get_qualifiers(), concDecl->get_name() ); |
---|
221 | newInst->set_baseUnion( concDecl ); |
---|
222 | delete inst; |
---|
223 | return newInst; |
---|
224 | } |
---|
225 | |
---|
226 | void Instantiate::doBeginScope() { |
---|
227 | // push a new concrete type scope |
---|
228 | instantiations.beginScope(); |
---|
229 | } |
---|
230 | |
---|
231 | void Instantiate::doEndScope() { |
---|
232 | // pop the last concrete type scope |
---|
233 | instantiations.endScope(); |
---|
234 | } |
---|
235 | |
---|
236 | } // namespace GenPoly |
---|
237 | |
---|
238 | // Local Variables: // |
---|
239 | // tab-width: 4 // |
---|
240 | // mode: c++ // |
---|
241 | // compile-command: "make install" // |
---|
242 | // End: // |
---|