source: src/GenPoly/InstantiateGeneric.cc @ a2eda27

aaron-thesisarm-ehcleanup-dtorsctordeferred_resndemanglerenumforall-pointer-decaygc_noraiijacob/cs343-translationjenkins-sandboxmemorynew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newstringwith_gc
Last change on this file since a2eda27 was a2eda27, checked in by Aaron Moss <a3moss@…>, 7 years ago

Switch type matching to use typesCompatible (on Rob's recommendation)

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