source: src/SymTab/Indexer.cc @ e8032b0

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

Switch Indexer over to copy-on-write semantics for dramatic speedup
  • Property mode set to 100644
File size: 16.8 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// Indexer.cc --
8//
9// Author           : Richard C. Bilson
10// Created On       : Sun May 17 21:37:33 2015
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Wed Mar  2 17:31:29 2016
13// Update Count     : 11
14//
15
16#include "Indexer.h"
17
18#include "IdTable.h"
19#include "AggregateTable.h"
20#include "TypeTable.h"
21
22#include "SynTree/Declaration.h"
23#include "SynTree/Type.h"
24#include "SynTree/Expression.h"
25#include "SynTree/Initializer.h"
26#include "SynTree/Statement.h"
27
28#include <typeinfo>
29#include <utility>
30#include "Common/utility.h"
31
32#define debugPrint(x) if ( doDebug ) { std::cout << x; }
33
34namespace SymTab {
35        template< typename Container, typename VisitorType >
36        inline void acceptAllNewScope( Container &container, VisitorType &visitor ) {
37                visitor.enterScope();
38                acceptAll( container, visitor );
39                visitor.leaveScope();
40        }
41
42        struct Indexer::Impl {
43                Impl() : refCount(1), size(0), base(),
44                                idTable(), typeTable(), structTable(), enumTable(), unionTable(), traitTable() {}
45                Impl( const Indexer &_base ) : refCount(1), size(0), base( _base ),
46                                idTable(), typeTable(), structTable(), enumTable(), unionTable(), traitTable() {}
47                unsigned long refCount;   ///< Number of references to these tables
48                unsigned long size;       ///< Number of elements stored in this table
49                const Indexer base;       ///< Base indexer this extends
50               
51                IdTable idTable;          ///< Identifier namespace
52                TypeTable typeTable;      ///< Type namespace
53                StructTable structTable;  ///< Struct namespace
54                EnumTable enumTable;      ///< Enum namespace
55                UnionTable unionTable;    ///< Union namespace
56                TraitTable traitTable;    ///< Trait namespace
57        };
58
59        Indexer::Impl *Indexer::newRef( Indexer::Impl *toClone ) {
60                if ( ! toClone ) return 0;
61
62                // shorten the search chain by skipping empty links
63                Indexer::Impl *ret = toClone->size == 0 ? toClone->base.tables : toClone;
64                if ( ret ) { ++ret->refCount; }
65
66                return ret;
67        }
68
69        void Indexer::deleteRef( Indexer::Impl *toFree ) {
70                if ( ! toFree ) return;
71
72                if ( --toFree->refCount == 0 ) delete toFree;
73        }
74
75        void Indexer::makeWritable() {
76                if ( ! tables ) {
77                        tables = new Indexer::Impl;
78                } else if ( tables->refCount > 1 ) {
79                        // tables->base inherits the ref that used to belong to this indexer
80                        // this is basically equivalent to std::move( *this ) as the argument
81                        tables = new Indexer::Impl( Indexer( tables, doDebug ) );
82                }
83        }
84
85        Indexer::Indexer( bool _doDebug ) : tables(0), doDebug( _doDebug ) {}
86
87        Indexer::Indexer( const Indexer &that ) : tables( newRef( that.tables ) ), doDebug( that.doDebug ) {}
88
89        Indexer::Indexer( Indexer &&that ) : tables( that.tables ), doDebug( that.doDebug ) {
90                that.tables = 0;
91        }
92
93        Indexer::~Indexer() {
94                deleteRef( tables );
95        }
96
97        Indexer& Indexer::operator= ( const Indexer &that ) {
98                deleteRef( tables );
99
100                tables = newRef( that.tables );
101                doDebug = that.doDebug;
102
103                return *this;
104        }
105
106        Indexer& Indexer::operator= ( Indexer &&that ) {
107                deleteRef( tables );
108
109                tables = that.tables;
110                doDebug = that.doDebug;
111
112                that.tables = 0;
113
114                return *this;
115        }
116
117        void Indexer::visit( ObjectDecl *objectDecl ) {
118                enterScope();
119                maybeAccept( objectDecl->get_type(), *this );
120                leaveScope();
121                maybeAccept( objectDecl->get_init(), *this );
122                maybeAccept( objectDecl->get_bitfieldWidth(), *this );
123                if ( objectDecl->get_name() != "" ) {
124                        debugPrint( "Adding object " << objectDecl->get_name() << std::endl );
125                        addId( objectDecl );
126                } // if
127        }
128
129        void Indexer::visit( FunctionDecl *functionDecl ) {
130                if ( functionDecl->get_name() == "" ) return;
131                debugPrint( "Adding function " << functionDecl->get_name() << std::endl );
132                addId( functionDecl );
133                enterScope();
134                maybeAccept( functionDecl->get_functionType(), *this );
135                acceptAll( functionDecl->get_oldDecls(), *this );
136                maybeAccept( functionDecl->get_statements(), *this );
137                leaveScope();
138        }
139
140
141// A NOTE ON THE ORDER OF TRAVERSAL
142//
143// Types and typedefs have their base types visited before they are added to the type table.  This is ok, since there is
144// no such thing as a recursive type or typedef.
145//
146//             typedef struct { T *x; } T; // never allowed
147//
148// for structs/unions, it is possible to have recursion, so the decl should be added as if it's incomplete to begin, the
149// members are traversed, and then the complete type should be added (assuming the type is completed by this particular
150// declaration).
151//
152//             struct T { struct T *x; }; // allowed
153//
154// It is important to add the complete type to the symbol table *after* the members/base has been traversed, since that
155// traversal may modify the definition of the type and these modifications should be visible when the symbol table is
156// queried later in this pass.
157//
158// TODO: figure out whether recursive contexts are sensible/possible/reasonable.
159
160
161        void Indexer::visit( TypeDecl *typeDecl ) {
162                // see A NOTE ON THE ORDER OF TRAVERSAL, above
163                // note that assertions come after the type is added to the symtab, since they are not part of the type proper
164                // and may depend on the type itself
165                enterScope();
166                acceptAll( typeDecl->get_parameters(), *this );
167                maybeAccept( typeDecl->get_base(), *this );
168                leaveScope();
169                debugPrint( "Adding type " << typeDecl->get_name() << std::endl );
170                addType( typeDecl );
171                acceptAll( typeDecl->get_assertions(), *this );
172        }
173
174        void Indexer::visit( TypedefDecl *typeDecl ) {
175                enterScope();
176                acceptAll( typeDecl->get_parameters(), *this );
177                maybeAccept( typeDecl->get_base(), *this );
178                leaveScope();
179                debugPrint( "Adding typedef " << typeDecl->get_name() << std::endl );
180                addType( typeDecl );
181        }
182
183        void Indexer::visit( StructDecl *aggregateDecl ) {
184                // make up a forward declaration and add it before processing the members
185                StructDecl fwdDecl( aggregateDecl->get_name() );
186                cloneAll( aggregateDecl->get_parameters(), fwdDecl.get_parameters() );
187                debugPrint( "Adding fwd decl for struct " << fwdDecl.get_name() << std::endl );
188                addStruct( &fwdDecl );
189 
190                enterScope();
191                acceptAll( aggregateDecl->get_parameters(), *this );
192                acceptAll( aggregateDecl->get_members(), *this );
193                leaveScope();
194 
195                debugPrint( "Adding struct " << aggregateDecl->get_name() << std::endl );
196                // this addition replaces the forward declaration
197                addStruct( aggregateDecl );
198        }
199
200        void Indexer::visit( UnionDecl *aggregateDecl ) {
201                // make up a forward declaration and add it before processing the members
202                UnionDecl fwdDecl( aggregateDecl->get_name() );
203                cloneAll( aggregateDecl->get_parameters(), fwdDecl.get_parameters() );
204                debugPrint( "Adding fwd decl for union " << fwdDecl.get_name() << std::endl );
205                addUnion( &fwdDecl );
206 
207                enterScope();
208                acceptAll( aggregateDecl->get_parameters(), *this );
209                acceptAll( aggregateDecl->get_members(), *this );
210                leaveScope();
211 
212                debugPrint( "Adding union " << aggregateDecl->get_name() << std::endl );
213                addUnion( aggregateDecl );
214        }
215
216        void Indexer::visit( EnumDecl *aggregateDecl ) {
217                debugPrint( "Adding enum " << aggregateDecl->get_name() << std::endl );
218                addEnum( aggregateDecl );
219                // unlike structs, contexts, and unions, enums inject their members into the global scope
220                acceptAll( aggregateDecl->get_members(), *this );
221        }
222
223        void Indexer::visit( TraitDecl *aggregateDecl ) {
224                enterScope();
225                acceptAll( aggregateDecl->get_parameters(), *this );
226                acceptAll( aggregateDecl->get_members(), *this );
227                leaveScope();
228 
229                debugPrint( "Adding context " << aggregateDecl->get_name() << std::endl );
230                addTrait( aggregateDecl );
231        }
232
233        void Indexer::visit( CompoundStmt *compoundStmt ) {
234                enterScope();
235                acceptAll( compoundStmt->get_kids(), *this );
236                leaveScope();
237        }
238
239
240        void Indexer::visit( ApplicationExpr *applicationExpr ) {
241                acceptAllNewScope( applicationExpr->get_results(), *this );
242                maybeAccept( applicationExpr->get_function(), *this );
243                acceptAll( applicationExpr->get_args(), *this );
244        }
245
246        void Indexer::visit( UntypedExpr *untypedExpr ) {
247                acceptAllNewScope( untypedExpr->get_results(), *this );
248                acceptAll( untypedExpr->get_args(), *this );
249        }
250
251        void Indexer::visit( NameExpr *nameExpr ) {
252                acceptAllNewScope( nameExpr->get_results(), *this );
253        }
254
255        void Indexer::visit( AddressExpr *addressExpr ) {
256                acceptAllNewScope( addressExpr->get_results(), *this );
257                maybeAccept( addressExpr->get_arg(), *this );
258        }
259
260        void Indexer::visit( LabelAddressExpr *labAddressExpr ) {
261                acceptAllNewScope( labAddressExpr->get_results(), *this );
262                maybeAccept( labAddressExpr->get_arg(), *this );
263        }
264
265        void Indexer::visit( CastExpr *castExpr ) {
266                acceptAllNewScope( castExpr->get_results(), *this );
267                maybeAccept( castExpr->get_arg(), *this );
268        }
269
270        void Indexer::visit( UntypedMemberExpr *memberExpr ) {
271                acceptAllNewScope( memberExpr->get_results(), *this );
272                maybeAccept( memberExpr->get_aggregate(), *this );
273        }
274
275        void Indexer::visit( MemberExpr *memberExpr ) {
276                acceptAllNewScope( memberExpr->get_results(), *this );
277                maybeAccept( memberExpr->get_aggregate(), *this );
278        }
279
280        void Indexer::visit( VariableExpr *variableExpr ) {
281                acceptAllNewScope( variableExpr->get_results(), *this );
282        }
283
284        void Indexer::visit( ConstantExpr *constantExpr ) {
285                acceptAllNewScope( constantExpr->get_results(), *this );
286                maybeAccept( constantExpr->get_constant(), *this );
287        }
288
289        void Indexer::visit( SizeofExpr *sizeofExpr ) {
290                acceptAllNewScope( sizeofExpr->get_results(), *this );
291                if ( sizeofExpr->get_isType() ) {
292                        maybeAccept( sizeofExpr->get_type(), *this );
293                } else {
294                        maybeAccept( sizeofExpr->get_expr(), *this );
295                }
296        }
297
298        void Indexer::visit( AlignofExpr *alignofExpr ) {
299                acceptAllNewScope( alignofExpr->get_results(), *this );
300                if ( alignofExpr->get_isType() ) {
301                        maybeAccept( alignofExpr->get_type(), *this );
302                } else {
303                        maybeAccept( alignofExpr->get_expr(), *this );
304                }
305        }
306
307        void Indexer::visit( UntypedOffsetofExpr *offsetofExpr ) {
308                acceptAllNewScope( offsetofExpr->get_results(), *this );
309                maybeAccept( offsetofExpr->get_type(), *this );
310        }
311
312        void Indexer::visit( OffsetofExpr *offsetofExpr ) {
313                acceptAllNewScope( offsetofExpr->get_results(), *this );
314                maybeAccept( offsetofExpr->get_type(), *this );
315                maybeAccept( offsetofExpr->get_member(), *this );
316        }
317
318        void Indexer::visit( AttrExpr *attrExpr ) {
319                acceptAllNewScope( attrExpr->get_results(), *this );
320                if ( attrExpr->get_isType() ) {
321                        maybeAccept( attrExpr->get_type(), *this );
322                } else {
323                        maybeAccept( attrExpr->get_expr(), *this );
324                }
325        }
326
327        void Indexer::visit( LogicalExpr *logicalExpr ) {
328                acceptAllNewScope( logicalExpr->get_results(), *this );
329                maybeAccept( logicalExpr->get_arg1(), *this );
330                maybeAccept( logicalExpr->get_arg2(), *this );
331        }
332
333        void Indexer::visit( ConditionalExpr *conditionalExpr ) {
334                acceptAllNewScope( conditionalExpr->get_results(), *this );
335                maybeAccept( conditionalExpr->get_arg1(), *this );
336                maybeAccept( conditionalExpr->get_arg2(), *this );
337                maybeAccept( conditionalExpr->get_arg3(), *this );
338        }
339
340        void Indexer::visit( CommaExpr *commaExpr ) {
341                acceptAllNewScope( commaExpr->get_results(), *this );
342                maybeAccept( commaExpr->get_arg1(), *this );
343                maybeAccept( commaExpr->get_arg2(), *this );
344        }
345
346        void Indexer::visit( TupleExpr *tupleExpr ) {
347                acceptAllNewScope( tupleExpr->get_results(), *this );
348                acceptAll( tupleExpr->get_exprs(), *this );
349        }
350
351        void Indexer::visit( SolvedTupleExpr *tupleExpr ) {
352                acceptAllNewScope( tupleExpr->get_results(), *this );
353                acceptAll( tupleExpr->get_exprs(), *this );
354        }
355
356        void Indexer::visit( TypeExpr *typeExpr ) {
357                acceptAllNewScope( typeExpr->get_results(), *this );
358                maybeAccept( typeExpr->get_type(), *this );
359        }
360
361        void Indexer::visit( AsmExpr *asmExpr ) {
362                maybeAccept( asmExpr->get_inout(), *this );
363                maybeAccept( asmExpr->get_constraint(), *this );
364                maybeAccept( asmExpr->get_operand(), *this );
365        }
366
367        void Indexer::visit( UntypedValofExpr *valofExpr ) {
368                acceptAllNewScope( valofExpr->get_results(), *this );
369                maybeAccept( valofExpr->get_body(), *this );
370        }
371
372
373        void Indexer::visit( TraitInstType *contextInst ) {
374                acceptAll( contextInst->get_parameters(), *this );
375                acceptAll( contextInst->get_members(), *this );
376        }
377
378        void Indexer::visit( StructInstType *structInst ) {
379                if ( ! lookupStruct( structInst->get_name() ) ) {
380                        debugPrint( "Adding struct " << structInst->get_name() << " from implicit forward declaration" << std::endl );
381                        addStruct( structInst->get_name() );
382                }
383                enterScope();
384                acceptAll( structInst->get_parameters(), *this );
385                leaveScope();
386        }
387
388        void Indexer::visit( UnionInstType *unionInst ) {
389                if ( ! lookupUnion( unionInst->get_name() ) ) {
390                        debugPrint( "Adding union " << unionInst->get_name() << " from implicit forward declaration" << std::endl );
391                        addUnion( unionInst->get_name() );
392                }
393                enterScope();
394                acceptAll( unionInst->get_parameters(), *this );
395                leaveScope();
396        }
397
398        void Indexer::visit( ForStmt *forStmt ) {
399            // for statements introduce a level of scope
400            enterScope();
401            Visitor::visit( forStmt );
402            leaveScope();
403        }
404
405
406        void Indexer::lookupId( const std::string &id, std::list< DeclarationWithType* > &list ) const {
407                if ( ! tables ) return;
408               
409                tables->idTable.lookupId( id, list );
410                tables->base.lookupId( id, list );
411        }
412
413        DeclarationWithType* Indexer::lookupId( const std::string &id) const {
414                if ( ! tables ) return 0;
415               
416                DeclarationWithType *ret = tables->idTable.lookupId(id);
417                return ret ? ret : tables->base.lookupId(id);
418        }
419
420        NamedTypeDecl *Indexer::lookupType( const std::string &id ) const {
421                if ( ! tables ) return 0;
422
423                NamedTypeDecl *ret = tables->typeTable.lookup( id );
424                return ret ? ret : tables->base.lookupType( id );
425        }
426
427        StructDecl *Indexer::lookupStruct( const std::string &id ) const {
428                if ( ! tables ) return 0;
429
430                StructDecl *ret = tables->structTable.lookup( id );
431                return ret ? ret : tables->base.lookupStruct( id );
432        }
433
434        EnumDecl *Indexer::lookupEnum( const std::string &id ) const {
435                if ( ! tables ) return 0;
436
437                EnumDecl *ret = tables->enumTable.lookup( id );
438                return ret ? ret : tables->base.lookupEnum( id );
439        }
440
441        UnionDecl *Indexer::lookupUnion( const std::string &id ) const {
442                if ( ! tables ) return 0;
443
444                UnionDecl *ret = tables->unionTable.lookup( id );
445                return ret ? ret : tables->base.lookupUnion( id );
446        }
447
448        TraitDecl *Indexer::lookupTrait( const std::string &id ) const {
449                if ( ! tables ) return 0;
450
451                TraitDecl *ret = tables->traitTable.lookup( id );
452                return ret ? ret : tables->base.lookupTrait( id );
453        }
454
455        void Indexer::addId( DeclarationWithType *decl ) {
456                makeWritable();
457                tables->idTable.addDecl( decl );
458                ++tables->size;
459        }
460       
461        void Indexer::addType( NamedTypeDecl *decl ) {
462                makeWritable();
463                tables->typeTable.add( decl );
464                ++tables->size;
465        }
466
467        void Indexer::addStruct( const std::string &id ) {
468                makeWritable();
469                tables->structTable.add( id );
470                ++tables->size;
471        }
472       
473        void Indexer::addStruct( StructDecl *decl ) {
474                makeWritable();
475                tables->structTable.add( decl );
476                ++tables->size;
477        }
478       
479        void Indexer::addEnum( EnumDecl *decl ) {
480                makeWritable();
481                tables->enumTable.add( decl );
482                ++tables->size;
483        }
484
485        void Indexer::addUnion( const std::string &id ) {
486                makeWritable();
487                tables->unionTable.add( id );
488                ++tables->size;
489        }
490       
491        void Indexer::addUnion( UnionDecl *decl ) {
492                makeWritable();
493                tables->unionTable.add( decl );
494                ++tables->size;
495        }
496       
497        void Indexer::addTrait( TraitDecl *decl ) {
498                makeWritable();
499                tables->traitTable.add( decl );
500                ++tables->size;
501        }
502
503        void Indexer::enterScope() {
504                makeWritable();
505               
506                if ( doDebug ) {
507                        std::cout << "--- Entering scope" << std::endl;
508                }
509
510                tables->idTable.enterScope();
511                tables->typeTable.enterScope();
512                tables->structTable.enterScope();
513                tables->enumTable.enterScope();
514                tables->unionTable.enterScope();
515                tables->traitTable.enterScope();
516        }
517
518        void Indexer::leaveScope() {
519                using std::cout;
520               
521                makeWritable();
522               
523                if ( doDebug ) {
524                        cout << "--- Leaving scope containing" << std::endl;
525                        tables->idTable.dump( cout );
526                        tables->typeTable.dump( cout );
527                        tables->structTable.dump( cout );
528                        tables->enumTable.dump( cout );
529                        tables->unionTable.dump( cout );
530                        tables->traitTable.dump( cout );
531                }
532                tables->idTable.leaveScope();
533                tables->typeTable.leaveScope();
534                tables->structTable.leaveScope();
535                tables->enumTable.leaveScope();
536                tables->unionTable.leaveScope();
537                tables->traitTable.leaveScope();
538        }
539
540        void Indexer::print( std::ostream &os, int indent ) const {
541            using std::cerr;
542
543            cerr << "===idTable===" << std::endl;
544            if ( tables ) tables->idTable.dump( os );
545            cerr << "===typeTable===" << std::endl;
546            if ( tables ) tables->typeTable.dump( os );
547            cerr << "===structTable===" << std::endl;
548            if ( tables ) tables->structTable.dump( os );
549            cerr << "===enumTable===" << std::endl;
550            if ( tables ) tables->enumTable.dump( os );
551            cerr << "===unionTable===" << std::endl;
552            if ( tables ) tables->unionTable.dump( os );
553            cerr << "===contextTable===" << std::endl;
554            if ( tables ) tables->traitTable.dump( os );
555        }
556} // namespace SymTab
557
558// Local Variables: //
559// tab-width: 4 //
560// mode: c++ //
561// compile-command: "make install" //
562// End: //
Note: See TracBrowser for help on using the repository browser.