source: src/SymTab/Indexer.cc@ e8032b0

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 e8032b0 was e8032b0, checked in by Aaron Moss <a3moss@…>, 10 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.