Changeset 92d41a4


Ignore:
Timestamp:
Mar 20, 2019, 4:19:29 PM (5 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
ADT, arm-eh, ast-experimental, cleanup-dtors, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
b5cff2b
Parents:
709e0e0 (diff), 114bde6 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'persistent-indexer'

Location:
src
Files:
1 added
6 edited

Legend:

Unmodified
Added
Removed

  • src/Common/PassVisitor.cc

    r709e0e0 r92d41a4  
    1717
    1818PassVisitorStats pass_visitor_stats;
     19Stats::Counters::SimpleCounter* BaseSyntaxNode::new_nodes = nullptr;

  • src/Common/Stats/Counter.h

    r709e0e0 r92d41a4  
    3737                        class SimpleCounter {
    3838                        public:
     39                                inline void operator++() {}
    3940                                inline void operator++(int) {}
    4041                                inline void operator+=(size_t) {}
    … …  
    8485                                virtual void print(std::ostream & os) override { os << count; }
    8586
     87                                inline void operator++()             { if(!enabled) return; count++;        }
    8688                                inline void operator++(int)          { if(!enabled) return; count++;        }
    8789                                inline void operator+=(size_t value) { if(!enabled) return; count += value; }

  • src/SymTab/Indexer.cc

    r709e0e0 r92d41a4  
    99// Author           : Richard C. Bilson
    1010// Created On       : Sun May 17 21:37:33 2015
    11 // Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Aug 17 16:08:40 2017
    13 // Update Count     : 20
     11// Last Modified By : Aaron B. Moss
     12// Last Modified On : Fri Mar  8 13:55:00 2019
     13// Update Count     : 21
    1414//
    1515
    … …  
    1717
    1818#include <cassert>                 // for assert, strict_dynamic_cast
    19 #include <iostream>                // for operator<<, basic_ostream, ostream
    2019#include <string>                  // for string, operator<<, operator!=
     20#include <memory>                  // for shared_ptr, make_shared
    2121#include <unordered_map>           // for operator!=, unordered_map<>::const...
    2222#include <unordered_set>           // for unordered_set
    2323#include <utility>                 // for pair, make_pair, move
     24#include <vector>                  // for vector
    2425
    2526#include "CodeGen/OperatorTable.h" // for isCtorDtor, isCtorDtorAssign
    2627#include "Common/SemanticError.h"  // for SemanticError
    2728#include "Common/utility.h"        // for cloneAll
    28 #include "Common/Stats/Counter.h" // for counters
    29 #include "GenPoly/GenPoly.h"
     29#include "Common/Stats/Counter.h"  // for counters
     30#include "GenPoly/GenPoly.h"       // for getFunctionType
    3031#include "InitTweak/InitTweak.h"   // for isConstructor, isCopyFunction, isC...
    3132#include "Mangler.h"               // for Mangler
    … …  
    3940#include "SynTree/Type.h"          // for Type, StructInstType, UnionInstType
    4041
    41 #define debugPrint(x) if ( doDebug ) { std::cerr << x; }
    42 
    4342namespace SymTab {
    4443
    4544        // Statistics block
    4645        namespace {
    47 
    48                 static inline auto stats_idtable() {
    49                         using namespace Stats::Counters;
    50                         static auto group = build<CounterGroup>("IdTable");
    51                         static struct {
    52                                 SimpleCounter * find;
    53                                 AverageCounter<double> * size;
    54                                 AverageCounter<double> * key;
    55                         } ret = {
    56                                 .find = build<SimpleCounter>("Find calls", group),
    57                                 .size = build<AverageCounter<double>>("Average Size", group),
    58                                 .key  = build<AverageCounter<double>>("Average Key Size", group),
    59                         };
    60                         return ret;
    61                 }
    62 
    63                 static inline auto stats_indexers() {
     46                static inline auto stats() {
    6447                        using namespace Stats::Counters;
    6548                        static auto group   = build<CounterGroup>("Indexers");
    … …  
    6750                                SimpleCounter * count;
    6851                                AverageCounter<double> * size;
    69                                 AverageCounter<double> * depth_a;
    70                                 MaxCounter<size_t> * depth_m;
     52                                SimpleCounter * new_scopes;
     53                                SimpleCounter * lazy_scopes;
     54                                AverageCounter<double> * avg_scope_depth;
     55                                MaxCounter<size_t> * max_scope_depth;
     56                                SimpleCounter * add_calls;
     57                                SimpleCounter * lookup_calls;
     58                                SimpleCounter * map_lookups;
     59                                SimpleCounter * map_mutations;
    7160                        } ret = {
    7261                                .count   = build<SimpleCounter>("Count", group),
    7362                                .size    = build<AverageCounter<double>>("Average Size", group),
    74                                 .depth_a = build<AverageCounter<double>>("Average Depth", group),
    75                                 .depth_m = build<MaxCounter<size_t>>("Max Depth", group),
     63                                .new_scopes = build<SimpleCounter>("Scopes", group),
     64                                .lazy_scopes = build<SimpleCounter>("Lazy Scopes", group),
     65                                .avg_scope_depth = build<AverageCounter<double>>("Average Scope", group),
     66                                .max_scope_depth = build<MaxCounter<size_t>>("Max Scope", group),
     67                                .add_calls = build<SimpleCounter>("Add Calls", group),
     68                                .lookup_calls = build<SimpleCounter>("Lookup Calls", group),
     69                                .map_lookups = build<SimpleCounter>("Map Lookups", group),
     70                                .map_mutations = build<SimpleCounter>("Map Mutations", group)
    7671                        };
    7772                        return ret;
    … …  
    7974        }
    8075
    81         std::ostream & operator<<( std::ostream & out, const Indexer::IdData & data ) {
    82                 return out << "(" << data.id << "," << data.baseExpr << ")";
    83         }
    84 
    85         typedef std::unordered_map< std::string, Indexer::IdData > MangleTable;
    86         typedef std::unordered_map< std::string, MangleTable > IdTable;
    87         typedef std::unordered_map< std::string, NamedTypeDecl* > TypeTable;
    88         typedef std::unordered_map< std::string, StructDecl* > StructTable;
    89         typedef std::unordered_map< std::string, EnumDecl* > EnumTable;
    90         typedef std::unordered_map< std::string, UnionDecl* > UnionTable;
    91         typedef std::unordered_map< std::string, TraitDecl* > TraitTable;
    92 
    93         void dump( const IdTable &table, std::ostream &os ) {
    94                 for ( IdTable::const_iterator id = table.begin(); id != table.end(); ++id ) {
    95                         for ( MangleTable::const_iterator mangle = id->second.begin(); mangle != id->second.end(); ++mangle ) {
    96                                 os << mangle->second << std::endl;
    97                         }
    98                 }
    99         }
    100 
    101         template< typename Decl >
    102         void dump( const std::unordered_map< std::string, Decl* > &table, std::ostream &os ) {
    103                 for ( typename std::unordered_map< std::string, Decl* >::const_iterator it = table.begin(); it != table.end(); ++it ) {
    104                         os << it->second << std::endl;
    105                 } // for
    106         }
    107 
    108         struct Indexer::Impl {
    109                 Impl( unsigned long _scope ) : refCount(1), scope( _scope ), size( 0 ), base(),
    110                                 idTable(), typeTable(), structTable(), enumTable(), unionTable(), traitTable() {}
    111                 Impl( unsigned long _scope, Indexer &&_base ) : refCount(1), scope( _scope ), size( 0 ), base( _base ),
    112                                 idTable(), typeTable(), structTable(), enumTable(), unionTable(), traitTable() {}
    113                 unsigned long refCount;   ///< Number of references to these tables
    114                 unsigned long scope;      ///< Scope these tables are associated with
    115                 unsigned long size;       ///< Number of elements stored in this table
    116                 const Indexer base;       ///< Base indexer this extends
    117 
    118                 IdTable idTable;          ///< Identifier namespace
    119                 TypeTable typeTable;      ///< Type namespace
    120                 StructTable structTable;  ///< Struct namespace
    121                 EnumTable enumTable;      ///< Enum namespace
    122                 UnionTable unionTable;    ///< Union namespace
    123                 TraitTable traitTable;    ///< Trait namespace
    124         };
    125 
    126         Indexer::Impl *Indexer::newRef( Indexer::Impl *toClone ) {
    127                 if ( ! toClone ) return 0;
    128 
    129                 // shorten the search chain by skipping empty links
    130                 Indexer::Impl *ret = toClone->size == 0 ? toClone->base.tables : toClone;
    131                 if ( ret ) { ++ret->refCount; }
    132 
    133                 return ret;
    134         }
    135 
    136         void Indexer::deleteRef( Indexer::Impl *toFree ) {
    137                 if ( ! toFree ) return;
    138 
    139                 if ( --toFree->refCount == 0 ) delete toFree;
    140         }
    141 
    142         void Indexer::removeSpecialOverrides( const std::string &id, std::list< IdData > & out ) const {
    143                 // only need to perform this step for constructors, destructors, and assignment functions
    144                 if ( ! CodeGen::isCtorDtorAssign( id ) ) return;
    145 
    146                 // helpful data structure to organize properties for a type
    147                 struct ValueType {
    148                         struct DeclBall { // properties for this particular decl
    149                                 IdData decl;
    150                                 bool isUserDefinedFunc;
    151                                 bool isCopyFunc;
    152                         };
    153                         // properties for this type
    154                         bool existsUserDefinedCopyFunc = false;    // user-defined copy ctor found
    155                         BaseSyntaxNode * deleteStmt = nullptr;     // non-null if a user-defined function is found
    156                         std::list< DeclBall > decls;
    157 
    158                         // another FunctionDecl for the current type was found - determine
    159                         // if it has special properties and update data structure accordingly
    160                         ValueType & operator+=( IdData data ) {
    161                                 DeclarationWithType * function = data.id;
    162                                 bool isUserDefinedFunc = ! LinkageSpec::isOverridable( function->linkage );
    163                                 bool isCopyFunc = InitTweak::isCopyFunction( function, function->name );
    164                                 decls.push_back( DeclBall{ data, isUserDefinedFunc, isCopyFunc } );
    165                                 existsUserDefinedCopyFunc = existsUserDefinedCopyFunc || (isUserDefinedFunc && isCopyFunc);
    166                                 if ( isUserDefinedFunc && ! deleteStmt ) {
    167                                         // any user-defined function can act as an implicit delete statement for generated constructors.
    168                                         // a delete stmt should not act as an implicit delete statement.
    169                                         deleteStmt = data.id;
    170                                 }
    171                                 return *this;
    172                         }
    173                 }; // ValueType
    174 
    175                 std::list< IdData > copy;
    176                 copy.splice( copy.end(), out );
    177 
    178                 // organize discovered declarations by type
    179                 std::unordered_map< std::string, ValueType > funcMap;
    180                 for ( auto decl : copy ) {
    181                         if ( FunctionDecl * function = dynamic_cast< FunctionDecl * >( decl.id ) ) {
    182                                 std::list< DeclarationWithType * > & params = function->type->parameters;
    183                                 assert( ! params.empty() );
    184                                 // use base type of pointer, so that qualifiers on the pointer type aren't considered.
    185                                 Type * base = InitTweak::getPointerBase( params.front()->get_type() );
    186                                 assert( base );
    187                                 funcMap[ Mangler::mangle( base ) ] += decl;
    188                         } else {
    189                                 out.push_back( decl );
    190                         }
    191                 }
    192 
    193                 // if a type contains user defined ctor/dtor/assign, then special rules trigger, which determine
    194                 // the set of ctor/dtor/assign that can be used  by the requester. In particular, if the user defines
    195                 // a default ctor, then the generated default ctor is unavailable, likewise for copy ctor
    196                 // and dtor. If the user defines any ctor/dtor, then no generated field ctors are available.
    197                 // If the user defines any ctor then the generated default ctor is unavailable (intrinsic default
    198                 // ctor must be overridden exactly). If the user defines anything that looks like a copy constructor,
    199                 // then the generated copy constructor is unavailable, and likewise for the assignment operator.
    200                 for ( std::pair< const std::string, ValueType > & pair : funcMap ) {
    201                         ValueType & val = pair.second;
    202                         for ( ValueType::DeclBall ball : val.decls ) {
    203                                 bool isNotUserDefinedFunc = ! ball.isUserDefinedFunc && ball.decl.id->linkage != LinkageSpec::Intrinsic;
    204                                 bool isCopyFunc = ball.isCopyFunc;
    205                                 bool existsUserDefinedCopyFunc = val.existsUserDefinedCopyFunc;
    206 
    207                                 // only implicitly delete non-user defined functions that are not intrinsic, and are
    208                                 // not copy functions (assignment or copy constructor). If a  user-defined copy function exists,
    209                                 // do not pass along the non-user-defined copy functions since signatures do not have to match,
    210                                 // and the generated functions will often be cheaper.
    211                                 if ( isNotUserDefinedFunc ) {
    212                                         if ( isCopyFunc ) {
    213                                                 // Skip over non-user-defined copy functions when there is a user-defined copy function.
    214                                                 // Since their signatures do not have to be exact, deleting them is the wrong choice.
    215                                                 if ( existsUserDefinedCopyFunc ) continue;
    216                                         } else {
    217                                                 // delete non-user-defined non-copy functions if applicable.
    218                                                 // deleteStmt will be non-null only if a user-defined function is found.
    219                                                 ball.decl.deleteStmt = val.deleteStmt;
    220                                         }
    221                                 }
    222                                 out.push_back( ball.decl );
    223                         }
    224                 }
    225         }
    226 
    227         void Indexer::makeWritable() {
    228                 if ( ! tables ) {
    229                         // create indexer if not yet set
    230                         tables = new Indexer::Impl( scope );
    231                 } else if ( tables->refCount > 1 || tables->scope != scope ) {
    232                         // make this indexer the base of a fresh indexer at the current scope
    233                         tables = new Indexer::Impl( scope, std::move( *this ) );
    234                 }
    235         }
    236 
    237         Indexer::Indexer() : tables( 0 ), scope( 0 ) {
    238                 (*stats_indexers().count)++;
    239         }
    240 
    241         Indexer::Indexer( const Indexer &that ) : doDebug( that.doDebug ), tables( newRef( that.tables ) ), scope( that.scope ) {
    242                 (*stats_indexers().count)++;
    243         }
    244 
    245         Indexer::Indexer( Indexer &&that ) : doDebug( that.doDebug ), tables( that.tables ), scope( that.scope ) {
    246                 that.tables = 0;
    247         }
     76        Indexer::Indexer()
     77        : idTable(), typeTable(), structTable(), enumTable(), unionTable(), traitTable(),
     78          prevScope(), scope( 0 ), repScope( 0 ) { ++*stats().count; }
    24879
    24980        Indexer::~Indexer() {
    250                 if(tables) {
    251                         stats_indexers().size->push( tables->idTable.size() );
    252                         size_t depth = 1;
    253                         for( auto crnt = tables->base.tables; crnt; crnt = crnt->base.tables ) {
    254                                 ++depth;
    255                         }
    256                         stats_indexers().depth_a->push( depth );
    257                         stats_indexers().depth_m->push( depth );
    258                 }
    259                 deleteRef( tables );
    260         }
    261 
    262         Indexer& Indexer::operator= ( const Indexer &that ) {
    263                 deleteRef( tables );
    264 
    265                 tables = newRef( that.tables );
    266                 scope = that.scope;
    267                 doDebug = that.doDebug;
    268 
    269                 return *this;
    270         }
    271 
    272         Indexer& Indexer::operator= ( Indexer &&that ) {
    273                 deleteRef( tables );
    274 
    275                 tables = that.tables;
    276                 scope = that.scope;
    277                 doDebug = that.doDebug;
    278 
    279                 that.tables = 0;
    280 
    281                 return *this;
     81                stats().size->push( idTable ? idTable->size() : 0 );
     82        }
     83
     84        void Indexer::lazyInitScope() {
     85                if ( repScope < scope ) {
     86                        ++*stats().lazy_scopes;
     87                        // create rollback
     88                        prevScope = std::make_shared<Indexer>( *this );
     89                        // update repScope
     90                        repScope = scope;
     91                }
     92        }
     93
     94        void Indexer::enterScope() {
     95                ++scope;
     96
     97                ++*stats().new_scopes;
     98                stats().avg_scope_depth->push( scope );
     99                stats().max_scope_depth->push( scope );
     100        }
     101
     102        void Indexer::leaveScope() {
     103                if ( repScope == scope ) {
     104                        Ptr prev = prevScope;           // make sure prevScope stays live
     105                        *this = std::move(*prevScope);  // replace with previous scope
     106                }
     107
     108                --scope;
    282109        }
    283110
    284111        void Indexer::lookupId( const std::string &id, std::list< IdData > &out ) const {
    285                 std::unordered_set< std::string > foundMangleNames;
    286 
    287                 Indexer::Impl *searchTables = tables;
    288                 while ( searchTables ) {
    289 
    290                         (*stats_idtable().find)++;
    291                         stats_idtable().key->push( id.size() );
    292                         stats_idtable().size->push( searchTables->idTable.size() );
    293                         IdTable::const_iterator decls = searchTables->idTable.find( id );
    294                         if ( decls != searchTables->idTable.end() ) {
    295                                 const MangleTable &mangleTable = decls->second;
    296                                 for ( MangleTable::const_iterator decl = mangleTable.begin(); decl != mangleTable.end(); ++decl ) {
    297                                         // mark the mangled name as found, skipping this insertion if a declaration for that name has already been found
    298                                         if ( foundMangleNames.insert( decl->first ).second == false ) continue;
    299 
    300                                         out.push_back( decl->second );
    301                                 }
    302                         }
    303 
    304                         // get declarations from base indexers
    305                         searchTables = searchTables->base.tables;
    306                 }
    307 
    308                 // some special functions, e.g. constructors and destructors
    309                 // remove autogenerated functions when they are defined so that
    310                 // they can never be matched
    311                 removeSpecialOverrides( id, out );
     112                ++*stats().lookup_calls;
     113                if ( ! idTable ) return;
     114
     115                ++*stats().map_lookups;
     116                auto decls = idTable->find( id );
     117                if ( decls == idTable->end() ) return;
     118
     119                for ( auto decl : *(decls->second) ) {
     120                        out.push_back( decl.second );
     121                }
    312122        }
    313123
    314124        NamedTypeDecl *Indexer::lookupType( const std::string &id ) const {
    315                 if ( ! tables ) return 0;
    316 
    317                 TypeTable::const_iterator ret = tables->typeTable.find( id );
    318                 return ret != tables->typeTable.end() ? ret->second : tables->base.lookupType( id );
     125                ++*stats().lookup_calls;
     126                if ( ! typeTable ) return nullptr;
     127                ++*stats().map_lookups;
     128                auto it = typeTable->find( id );
     129                return it == typeTable->end() ? nullptr : it->second.decl;
    319130        }
    320131
    321132        StructDecl *Indexer::lookupStruct( const std::string &id ) const {
    322                 if ( ! tables ) return 0;
    323 
    324                 StructTable::const_iterator ret = tables->structTable.find( id );
    325                 return ret != tables->structTable.end() ? ret->second : tables->base.lookupStruct( id );
     133                ++*stats().lookup_calls;
     134                if ( ! structTable ) return nullptr;
     135                ++*stats().map_lookups;
     136                auto it = structTable->find( id );
     137                return it == structTable->end() ? nullptr : it->second.decl;
     138        }
     139
     140        EnumDecl *Indexer::lookupEnum( const std::string &id ) const {
     141                ++*stats().lookup_calls;
     142                if ( ! enumTable ) return nullptr;
     143                ++*stats().map_lookups;
     144                auto it = enumTable->find( id );
     145                return it == enumTable->end() ? nullptr : it->second.decl;
     146        }
     147
     148        UnionDecl *Indexer::lookupUnion( const std::string &id ) const {
     149                ++*stats().lookup_calls;
     150                if ( ! unionTable ) return nullptr;
     151                ++*stats().map_lookups;
     152                auto it = unionTable->find( id );
     153                return it == unionTable->end() ? nullptr : it->second.decl;
     154        }
     155
     156        TraitDecl *Indexer::lookupTrait( const std::string &id ) const {
     157                ++*stats().lookup_calls;
     158                if ( ! traitTable ) return nullptr;
     159                ++*stats().map_lookups;
     160                auto it = traitTable->find( id );
     161                return it == traitTable->end() ? nullptr : it->second.decl;
     162        }
     163
     164        const Indexer* Indexer::atScope( unsigned long target ) const {
     165                // by lazy construction, final indexer in list has repScope 0, cannot be > target
     166                // otherwise, will find first scope representing the target
     167                const Indexer* indexer = this;
     168                while ( indexer->repScope > target ) {
     169                        indexer = indexer->prevScope.get();
     170                }
     171                return indexer;
    326172        }
    327173
    328174        NamedTypeDecl *Indexer::globalLookupType( const std::string &id ) const {
    329                 return lookupTypeAtScope( id, 0 );
     175                return atScope( 0 )->lookupType( id );
    330176        }
    331177
    332178        StructDecl *Indexer::globalLookupStruct( const std::string &id ) const {
    333                 return lookupStructAtScope( id, 0 );
     179                return atScope( 0 )->lookupStruct( id );
    334180        }
    335181
    336182        UnionDecl *Indexer::globalLookupUnion( const std::string &id ) const {
    337                 return lookupUnionAtScope( id, 0 );
     183                return atScope( 0 )->lookupUnion( id );
    338184        }
    339185
    340186        EnumDecl *Indexer::globalLookupEnum( const std::string &id ) const {
    341                 return lookupEnumAtScope( id, 0 );
    342         }
    343 
    344         EnumDecl *Indexer::lookupEnum( const std::string &id ) const {
    345                 if ( ! tables ) return 0;
    346 
    347                 EnumTable::const_iterator ret = tables->enumTable.find( id );
    348                 return ret != tables->enumTable.end() ? ret->second : tables->base.lookupEnum( id );
    349         }
    350 
    351         UnionDecl *Indexer::lookupUnion( const std::string &id ) const {
    352                 if ( ! tables ) return 0;
    353 
    354                 UnionTable::const_iterator ret = tables->unionTable.find( id );
    355                 return ret != tables->unionTable.end() ? ret->second : tables->base.lookupUnion( id );
    356         }
    357 
    358         TraitDecl *Indexer::lookupTrait( const std::string &id ) const {
    359                 if ( ! tables ) return 0;
    360 
    361                 TraitTable::const_iterator ret = tables->traitTable.find( id );
    362                 return ret != tables->traitTable.end() ? ret->second : tables->base.lookupTrait( id );
    363         }
    364 
    365         const Indexer::IdData * Indexer::lookupIdAtScope( const std::string &id, const std::string &mangleName, unsigned long scope ) const {
    366                 if ( ! tables ) return nullptr;
    367                 if ( tables->scope < scope ) return nullptr;
    368 
    369                 (*stats_idtable().find)++;
    370                 stats_idtable().key->push( id.size() );
    371                 stats_idtable().size->push( tables->idTable.size() );
    372                 IdTable::const_iterator decls = tables->idTable.find( id );
    373                 if ( decls != tables->idTable.end() ) {
    374                         const MangleTable &mangleTable = decls->second;
    375                         MangleTable::const_iterator decl = mangleTable.find( mangleName );
    376                         if ( decl != mangleTable.end() ) return &decl->second;
    377                 }
    378 
    379                 return tables->base.lookupIdAtScope( id, mangleName, scope );
    380         }
    381 
    382         Indexer::IdData * Indexer::lookupIdAtScope( const std::string &id, const std::string &mangleName, unsigned long scope ) {
    383                 return const_cast<IdData *>(const_cast<const Indexer *>(this)->lookupIdAtScope( id, mangleName, scope ));
    384         }
    385 
    386         bool Indexer::hasIncompatibleCDecl( const std::string &id, const std::string &mangleName, unsigned long scope ) const {
    387                 if ( ! tables ) return false;
    388                 if ( tables->scope < scope ) return false;
    389 
    390                 (*stats_idtable().find)++;
    391                 stats_idtable().key->push( id.size() );
    392                 stats_idtable().size->push( tables->idTable.size() );
    393                 IdTable::const_iterator decls = tables->idTable.find( id );
    394                 if ( decls != tables->idTable.end() ) {
    395                         const MangleTable &mangleTable = decls->second;
    396                         for ( MangleTable::const_iterator decl = mangleTable.begin(); decl != mangleTable.end(); ++decl ) {
    397                                 // check for C decls with the same name, skipping those with a compatible type (by mangleName)
    398                                 if ( ! LinkageSpec::isMangled( decl->second.id->get_linkage() ) && decl->first != mangleName ) return true;
    399                         }
    400                 }
    401 
    402                 return tables->base.hasIncompatibleCDecl( id, mangleName, scope );
    403         }
    404 
    405         bool Indexer::hasCompatibleCDecl( const std::string &id, const std::string &mangleName, unsigned long scope ) const {
    406                 if ( ! tables ) return false;
    407                 if ( tables->scope < scope ) return false;
    408 
    409                 (*stats_idtable().find)++;
    410                 stats_idtable().key->push( id.size() );
    411                 stats_idtable().size->push( tables->idTable.size() );
    412                 IdTable::const_iterator decls = tables->idTable.find( id );
    413                 if ( decls != tables->idTable.end() ) {
    414                         const MangleTable &mangleTable = decls->second;
    415                         for ( MangleTable::const_iterator decl = mangleTable.begin(); decl != mangleTable.end(); ++decl ) {
    416                                 // check for C decls with the same name, skipping
    417                                 // those with an incompatible type (by mangleName)
    418                                 if ( ! LinkageSpec::isMangled( decl->second.id->get_linkage() ) && decl->first == mangleName ) return true;
    419                         }
    420                 }
    421 
    422                 return tables->base.hasCompatibleCDecl( id, mangleName, scope );
    423         }
    424 
    425         NamedTypeDecl *Indexer::lookupTypeAtScope( const std::string &id, unsigned long scope ) const {
    426                 if ( ! tables ) return 0;
    427                 if ( tables->scope < scope ) return 0;
    428                 if ( tables->scope > scope ) return tables->base.lookupTypeAtScope( id, scope );
    429 
    430                 TypeTable::const_iterator ret = tables->typeTable.find( id );
    431                 return ret != tables->typeTable.end() ? ret->second : tables->base.lookupTypeAtScope( id, scope );
    432         }
    433 
    434         StructDecl *Indexer::lookupStructAtScope( const std::string &id, unsigned long scope ) const {
    435                 if ( ! tables ) return 0;
    436                 if ( tables->scope < scope ) return 0;
    437                 if ( tables->scope > scope ) return tables->base.lookupStructAtScope( id, scope );
    438 
    439                 StructTable::const_iterator ret = tables->structTable.find( id );
    440                 return ret != tables->structTable.end() ? ret->second : tables->base.lookupStructAtScope( id, scope );
    441         }
    442 
    443         EnumDecl *Indexer::lookupEnumAtScope( const std::string &id, unsigned long scope ) const {
    444                 if ( ! tables ) return 0;
    445                 if ( tables->scope < scope ) return 0;
    446                 if ( tables->scope > scope ) return tables->base.lookupEnumAtScope( id, scope );
    447 
    448                 EnumTable::const_iterator ret = tables->enumTable.find( id );
    449                 return ret != tables->enumTable.end() ? ret->second : tables->base.lookupEnumAtScope( id, scope );
    450         }
    451 
    452         UnionDecl *Indexer::lookupUnionAtScope( const std::string &id, unsigned long scope ) const {
    453                 if ( ! tables ) return 0;
    454                 if ( tables->scope < scope ) return 0;
    455                 if ( tables->scope > scope ) return tables->base.lookupUnionAtScope( id, scope );
    456 
    457                 UnionTable::const_iterator ret = tables->unionTable.find( id );
    458                 return ret != tables->unionTable.end() ? ret->second : tables->base.lookupUnionAtScope( id, scope );
    459         }
    460 
    461         TraitDecl *Indexer::lookupTraitAtScope( const std::string &id, unsigned long scope ) const {
    462                 if ( ! tables ) return 0;
    463                 if ( tables->scope < scope ) return 0;
    464                 if ( tables->scope > scope ) return tables->base.lookupTraitAtScope( id, scope );
    465 
    466                 TraitTable::const_iterator ret = tables->traitTable.find( id );
    467                 return ret != tables->traitTable.end() ? ret->second : tables->base.lookupTraitAtScope( id, scope );
     187                return atScope( 0 )->lookupEnum( id );
    468188        }
    469189
    … …  
    487207        }
    488208
    489         bool addedIdConflicts( Indexer::IdData & existing, DeclarationWithType *added, BaseSyntaxNode * deleteStmt, Indexer::ConflictFunction handleConflicts ) {
    490                 // if we're giving the same name mangling to things of different types then there is something wrong
     209       
     210        bool Indexer::addedIdConflicts(
     211                        const Indexer::IdData & existing, DeclarationWithType *added,
     212                        Indexer::OnConflict handleConflicts, BaseSyntaxNode * deleteStmt ) {
     213                // if we're giving the same name mangling to things of different types then there is
     214                // something wrong
    491215                assert( (isObject( added ) && isObject( existing.id ) )
    492216                        || ( isFunction( added ) && isFunction( existing.id ) ) );
    493217
    494                 if ( LinkageSpec::isOverridable( existing.id->get_linkage() ) ) {
     218                if ( LinkageSpec::isOverridable( existing.id->linkage ) ) {
    495219                        // new definition shadows the autogenerated one, even at the same scope
    496220                        return false;
    497                 } else if ( LinkageSpec::isMangled( added->get_linkage() ) || ResolvExpr::typesCompatible( added->get_type(), existing.id->get_type(), Indexer() ) ) {
     221                } else if ( LinkageSpec::isMangled( added->linkage )
     222                                || ResolvExpr::typesCompatible(
     223                                        added->get_type(), existing.id->get_type(), Indexer() ) ) {
    498224
    499225                        // it is a conflict if one declaration is deleted and the other is not
    500226                        if ( deleteStmt && ! existing.deleteStmt ) {
    501                                 return handleConflicts( existing, "deletion of defined identifier " );
     227                                if ( handleConflicts.mode == OnConflict::Error ) {
     228                                        SemanticError( added, "deletion of defined identifier " );
     229                                }
     230                                return true;
    502231                        } else if ( ! deleteStmt && existing.deleteStmt ) {
    503                                 return handleConflicts( existing, "definition of deleted identifier " );
     232                                if ( handleConflicts.mode == OnConflict::Error ) {
     233                                        SemanticError( added, "definition of deleted identifier " );
     234                                }
     235                                return true;
    504236                        }
    505237
    506238                        if ( isDefinition( added ) && isDefinition( existing.id ) ) {
    507                                 if ( isFunction( added ) ) {
    508                                         return handleConflicts( existing, "duplicate function definition for " );
     239                                if ( handleConflicts.mode == OnConflict::Error ) {
     240                                        SemanticError( added,
     241                                                isFunction( added ) ?
     242                                                        "duplicate function definition for " :
     243                                                        "duplicate object definition for " );
     244                                }
     245                                return true;
     246                        } // if
     247                } else {
     248                        if ( handleConflicts.mode == OnConflict::Error ) {
     249                                SemanticError( added, "duplicate definition for " );
     250                        }
     251                        return true;
     252                } // if
     253
     254                return true;
     255        }
     256
     257        bool Indexer::hasCompatibleCDecl( const std::string &id, const std::string &mangleName ) const {
     258                if ( ! idTable ) return false;
     259
     260                ++*stats().map_lookups;
     261                auto decls = idTable->find( id );
     262                if ( decls == idTable->end() ) return false;
     263
     264                for ( auto decl : *(decls->second) ) {
     265                        // skip other scopes (hidden by this decl)
     266                        if ( decl.second.scope != scope ) continue;
     267                        // check for C decl with compatible type (by mangleName)
     268                        if ( ! LinkageSpec::isMangled( decl.second.id->linkage ) && decl.first == mangleName ) {
     269                                return true;
     270                        }
     271                }
     272               
     273                return false;
     274        }
     275
     276        bool Indexer::hasIncompatibleCDecl(
     277                        const std::string &id, const std::string &mangleName ) const {
     278                if ( ! idTable ) return false;
     279
     280                ++*stats().map_lookups;
     281                auto decls = idTable->find( id );
     282                if ( decls == idTable->end() ) return false;
     283
     284                for ( auto decl : *(decls->second) ) {
     285                        // skip other scopes (hidden by this decl)
     286                        if ( decl.second.scope != scope ) continue;
     287                        // check for C decl with incompatible type (by manglename)
     288                        if ( ! LinkageSpec::isMangled( decl.second.id->linkage ) && decl.first != mangleName ) {
     289                                return true;
     290                        }
     291                }
     292
     293                return false;
     294        }
     295
     296        /// gets the base type of the first parameter; decl must be a ctor/dtor/assignment function
     297        std::string getOtypeKey( FunctionDecl* function ) {
     298                auto& params = function->type->parameters;
     299                assert( ! params.empty() );
     300                // use base type of pointer, so that qualifiers on the pointer type aren't considered.
     301                Type* base = InitTweak::getPointerBase( params.front()->get_type() );
     302                assert( base );
     303                return Mangler::mangle( base );
     304        }
     305
     306        /// gets the declaration for the function acting on a type specified by otype key,
     307        /// nullptr if none such
     308        FunctionDecl * getFunctionForOtype( DeclarationWithType * decl, const std::string& otypeKey ) {
     309                FunctionDecl * func = dynamic_cast< FunctionDecl * >( decl );
     310                if ( ! func || otypeKey != getOtypeKey( func ) ) return nullptr;
     311                return func;
     312        }
     313
     314        bool Indexer::removeSpecialOverrides(
     315                        Indexer::IdData& data, Indexer::MangleTable::Ptr& mangleTable ) {
     316                // if a type contains user defined ctor/dtor/assign, then special rules trigger, which
     317                // determinethe set of ctor/dtor/assign that can be used  by the requester. In particular,
     318                // if the user defines a default ctor, then the generated default ctor is unavailable,
     319                // likewise for copy ctor and dtor. If the user defines any ctor/dtor, then no generated
     320                // field ctors are available. If the user defines any ctor then the generated default ctor
     321                // is unavailable (intrinsic default ctor must be overridden exactly). If the user defines
     322                // anything that looks like a copy constructor, then the generated copy constructor is
     323                // unavailable, and likewise for the assignment operator.
     324
     325                // only relevant on function declarations
     326                FunctionDecl * function = dynamic_cast< FunctionDecl * >( data.id );
     327                if ( ! function ) return true;
     328                // only need to perform this check for constructors, destructors, and assignment functions
     329                if ( ! CodeGen::isCtorDtorAssign( data.id->name ) ) return true;
     330
     331                // set up information for this type
     332                bool dataIsUserDefinedFunc = ! LinkageSpec::isOverridable( function->linkage );
     333                bool dataIsCopyFunc = InitTweak::isCopyFunction( function, function->name );
     334                std::string dataOtypeKey = getOtypeKey( function );
     335
     336                if ( dataIsUserDefinedFunc && dataIsCopyFunc ) {
     337                        // this is a user-defined copy function
     338                        // if this is the first such, delete/remove non-user-defined overloads as needed
     339                        std::vector< std::string > removed;
     340                        std::vector< MangleTable::value_type > deleted;
     341                        bool alreadyUserDefinedFunc = false;
     342                       
     343                        for ( const auto& entry : *mangleTable ) {
     344                                // skip decls that aren't functions or are for the wrong type
     345                                FunctionDecl * decl = getFunctionForOtype( entry.second.id, dataOtypeKey );
     346                                if ( ! decl ) continue;
     347
     348                                bool isCopyFunc = InitTweak::isCopyFunction( decl, decl->name );
     349                                if ( ! LinkageSpec::isOverridable( decl->linkage ) ) {
     350                                        // matching user-defined function
     351                                        if ( isCopyFunc ) {
     352                                                // mutation already performed, return early
     353                                                return true;
     354                                        } else {
     355                                                // note that non-copy deletions already performed
     356                                                alreadyUserDefinedFunc = true;
     357                                        }
    509358                                } else {
    510                                         return handleConflicts( existing, "duplicate object definition for " );
    511                                 } // if
    512                         } // if
    513                 } else {
    514                         return handleConflicts( existing, "duplicate definition for " );
    515                 } // if
    516 
     359                                        // non-user-defined function; mark for deletion/removal as appropriate
     360                                        if ( isCopyFunc ) {
     361                                                removed.push_back( entry.first );
     362                                        } else if ( ! alreadyUserDefinedFunc ) {
     363                                                deleted.push_back( entry );
     364                                        }
     365                                }
     366                        }
     367
     368                        // perform removals from mangle table, and deletions if necessary
     369                        for ( const auto& key : removed ) {
     370                                ++*stats().map_mutations;
     371                                mangleTable = mangleTable->erase( key );
     372                        }
     373                        if ( ! alreadyUserDefinedFunc ) for ( const auto& entry : deleted ) {
     374                                ++*stats().map_mutations;
     375                                mangleTable = mangleTable->set( entry.first, IdData{ entry.second, function } );
     376                        }
     377                } else if ( dataIsUserDefinedFunc ) {
     378                        // this is a user-defined non-copy function
     379                        // if this is the first user-defined function, delete non-user-defined overloads
     380                        std::vector< MangleTable::value_type > deleted;
     381                       
     382                        for ( const auto& entry : *mangleTable ) {
     383                                // skip decls that aren't functions or are for the wrong type
     384                                FunctionDecl * decl = getFunctionForOtype( entry.second.id, dataOtypeKey );
     385                                if ( ! decl ) continue;
     386
     387                                // exit early if already a matching user-defined function;
     388                                // earlier function will have mutated table
     389                                if ( ! LinkageSpec::isOverridable( decl->linkage ) ) return true;
     390
     391                                // skip mutating intrinsic functions
     392                                if ( decl->linkage == LinkageSpec::Intrinsic ) continue;
     393
     394                                // user-defined non-copy functions do not override copy functions
     395                                if ( InitTweak::isCopyFunction( decl, decl->name ) ) continue;
     396
     397                                // this function to be deleted after mangleTable iteration is complete
     398                                deleted.push_back( entry );
     399                        }
     400
     401                        // mark deletions to update mangle table
     402                        // this needs to be a separate loop because of iterator invalidation
     403                        for ( const auto& entry : deleted ) {
     404                                ++*stats().map_mutations;
     405                                mangleTable = mangleTable->set( entry.first, IdData{ entry.second, function } );
     406                        }
     407                } else if ( function->linkage != LinkageSpec::Intrinsic ) {
     408                        // this is an overridable generated function
     409                        // if there already exists a matching user-defined function, delete this appropriately
     410                        for ( const auto& entry : *mangleTable ) {
     411                                // skip decls that aren't functions or are for the wrong type
     412                                FunctionDecl * decl = getFunctionForOtype( entry.second.id, dataOtypeKey );
     413                                if ( ! decl ) continue;
     414
     415                                // skip non-user-defined functions
     416                                if ( LinkageSpec::isOverridable( decl->linkage ) ) continue;
     417
     418                                if ( dataIsCopyFunc ) {
     419                                        // remove current function if exists a user-defined copy function
     420                                        // since the signatures for copy functions don't need to match exactly, using
     421                                        // a delete statement is the wrong approach
     422                                        if ( InitTweak::isCopyFunction( decl, decl->name ) ) return false;
     423                                } else {
     424                                        // mark current function deleted by first user-defined function found
     425                                        data.deleteStmt = decl;
     426                                        return true;
     427                                }
     428                        }
     429                }
     430               
     431                // nothing (more) to fix, return true
    517432                return true;
    518433        }
    519434
    520         void Indexer::addId( DeclarationWithType *decl, ConflictFunction handleConflicts, Expression * baseExpr, BaseSyntaxNode * deleteStmt ) {
    521                 if ( decl->name == "" ) return;
    522                 debugPrint( "Adding Id " << decl->name << std::endl );
    523                 makeWritable();
    524 
     435        void Indexer::addId(
     436                        DeclarationWithType *decl, OnConflict handleConflicts, Expression * baseExpr,
     437                        BaseSyntaxNode * deleteStmt ) {
     438                ++*stats().add_calls;
    525439                const std::string &name = decl->name;
     440                if ( name == "" ) return;
     441               
    526442                std::string mangleName;
    527443                if ( LinkageSpec::isOverridable( decl->linkage ) ) {
    528                         // mangle the name without including the appropriate suffix, so overridable routines are placed into the
    529                         // same "bucket" as their user defined versions.
     444                        // mangle the name without including the appropriate suffix, so overridable routines
     445                        // are placed into the same "bucket" as their user defined versions.
    530446                        mangleName = Mangler::mangle( decl, false );
    531447                } else {
    … …  
    533449                } // if
    534450
    535                 // this ensures that no two declarations with the same unmangled name at the same scope both have C linkage
    536                 if ( ! LinkageSpec::isMangled( decl->linkage ) ) {
    537                         // NOTE this is broken in Richard's original code in such a way that it never triggers (it
    538                         // doesn't check decls that have the same manglename, and all C-linkage decls are defined to
    539                         // have their name as their manglename, hence the error can never trigger).
    540                         // The code here is closer to correct, but name mangling would have to be completely
    541                         // isomorphic to C type-compatibility, which it may not be.
    542                         if ( hasIncompatibleCDecl( name, mangleName, scope ) ) {
     451                // this ensures that no two declarations with the same unmangled name at the same scope
     452                // both have C linkage
     453                if ( LinkageSpec::isMangled( decl->linkage ) ) {
     454                        // Check that a Cforall declaration doesn't override any C declaration
     455                        if ( hasCompatibleCDecl( name, mangleName ) ) {
     456                                SemanticError( decl, "Cforall declaration hides C function " );
     457                        }
     458                } else {
     459                        // NOTE: only correct if name mangling is completely isomorphic to C
     460                        // type-compatibility, which it may not be.
     461                        if ( hasIncompatibleCDecl( name, mangleName ) ) {
    543462                                SemanticError( decl, "conflicting overload of C function " );
    544463                        }
    545                 } else {
    546                         // Check that a Cforall declaration doesn't override any C declaration
    547                         if ( hasCompatibleCDecl( name, mangleName, scope ) ) {
    548                                 SemanticError( decl, "Cforall declaration hides C function " );
    549                         }
    550                 }
    551 
    552                 // Skip repeat declarations of the same identifier
    553                 IdData * existing = lookupIdAtScope( name, mangleName, scope );
    554                 if ( existing && existing->id && addedIdConflicts( *existing, decl, deleteStmt, handleConflicts ) ) return;
    555 
    556                 // add to indexer
    557                 tables->idTable[ name ][ mangleName ] = IdData{ decl, baseExpr, deleteStmt };
    558                 ++tables->size;
     464                }
     465
     466                // ensure tables exist and add identifier
     467                MangleTable::Ptr mangleTable;
     468                if ( ! idTable ) {
     469                        idTable = IdTable::new_ptr();
     470                        mangleTable = MangleTable::new_ptr();
     471                } else {
     472                        ++*stats().map_lookups;
     473                        auto decls = idTable->find( name );
     474                        if ( decls == idTable->end() ) {
     475                                mangleTable = MangleTable::new_ptr();
     476                        } else {
     477                                mangleTable = decls->second;
     478                                // skip in-scope repeat declarations of same identifier
     479                                ++*stats().map_lookups;
     480                                auto existing = mangleTable->find( mangleName );
     481                                if ( existing != mangleTable->end()
     482                                                && existing->second.scope == scope
     483                                                && existing->second.id ) {
     484                                        if ( addedIdConflicts( existing->second, decl, handleConflicts, deleteStmt ) ) {
     485                                                if ( handleConflicts.mode == OnConflict::Delete ) {
     486                                                        // set delete expression for conflicting identifier
     487                                                        lazyInitScope();
     488                                                        *stats().map_mutations += 2;
     489                                                        idTable = idTable->set(
     490                                                                name,
     491                                                                mangleTable->set(
     492                                                                        mangleName,
     493                                                                        IdData{ existing->second, handleConflicts.deleteStmt } ) );
     494                                                }
     495                                                return;
     496                                        }
     497                                }
     498                        }
     499                }
     500
     501                // add/overwrite with new identifier
     502                lazyInitScope();
     503                IdData data{ decl, baseExpr, deleteStmt, scope };
     504                // Ensure that auto-generated ctor/dtor/assignment are deleted if necessary
     505                if ( ! removeSpecialOverrides( data, mangleTable ) ) return;
     506                *stats().map_mutations += 2;
     507                idTable = idTable->set( name, mangleTable->set( mangleName, std::move(data) ) );
    559508        }
    560509
    561510        void Indexer::addId( DeclarationWithType * decl, Expression * baseExpr ) {
    562511                // default handling of conflicts is to raise an error
    563                 addId( decl, [decl](IdData &, const std::string & msg) { SemanticError( decl, msg ); return true; }, baseExpr, decl->isDeleted ? decl : nullptr );
     512                addId( decl, OnConflict::error(), baseExpr, decl->isDeleted ? decl : nullptr );
    564513        }
    565514
    566515        void Indexer::addDeletedId( DeclarationWithType * decl, BaseSyntaxNode * deleteStmt ) {
    567516                // default handling of conflicts is to raise an error
    568                 addId( decl, [decl](IdData &, const std::string & msg) { SemanticError( decl, msg ); return true; }, nullptr, deleteStmt );
     517                addId( decl, OnConflict::error(), nullptr, deleteStmt );
    569518        }
    570519
    … …  
    581530                        }
    582531                }
    583                 // does not need to be added to the table if both existing and added have a base that are the same
     532                // does not need to be added to the table if both existing and added have a base that are
     533                // the same
    584534                return true;
    585535        }
    586536
    587537        void Indexer::addType( NamedTypeDecl *decl ) {
    588                 debugPrint( "Adding type " << decl->name << std::endl );
    589                 makeWritable();
    590 
     538                ++*stats().add_calls;
    591539                const std::string &id = decl->name;
    592                 TypeTable::iterator existing = tables->typeTable.find( id );
    593                 if ( existing == tables->typeTable.end() ) {
    594                         NamedTypeDecl *parent = tables->base.lookupTypeAtScope( id, scope );
    595                         if ( ! parent || ! addedTypeConflicts( parent, decl ) ) {
    596                                 tables->typeTable.insert( existing, std::make_pair( id, decl ) );
    597                                 ++tables->size;
    598                         }
    599                 } else {
    600                         if ( ! addedTypeConflicts( existing->second, decl ) ) {
    601                                 existing->second = decl;
    602                         }
    603                 }
     540
     541                if ( ! typeTable ) {
     542                        typeTable = TypeTable::new_ptr();
     543                } else {
     544                        ++*stats().map_lookups;
     545                        auto existing = typeTable->find( id );
     546                        if ( existing != typeTable->end()
     547                                && existing->second.scope == scope
     548                                && addedTypeConflicts( existing->second.decl, decl ) ) return;
     549                }
     550               
     551                lazyInitScope();
     552                ++*stats().map_mutations;
     553                typeTable = typeTable->set( id, Scoped<NamedTypeDecl>{ decl, scope } );
    604554        }
    605555
    … …  
    614564
    615565        void Indexer::addStruct( const std::string &id ) {
    616                 debugPrint( "Adding fwd decl for struct " << id << std::endl );
    617566                addStruct( new StructDecl( id ) );
    618567        }
    619568
    620569        void Indexer::addStruct( StructDecl *decl ) {
    621                 debugPrint( "Adding struct " << decl->name << std::endl );
    622                 makeWritable();
    623 
     570                ++*stats().add_calls;
    624571                const std::string &id = decl->name;
    625                 StructTable::iterator existing = tables->structTable.find( id );
    626                 if ( existing == tables->structTable.end() ) {
    627                         StructDecl *parent = tables->base.lookupStructAtScope( id, scope );
    628                         if ( ! parent || ! addedDeclConflicts( parent, decl ) ) {
    629                                 tables->structTable.insert( existing, std::make_pair( id, decl ) );
    630                                 ++tables->size;
    631                         }
    632                 } else {
    633                         if ( ! addedDeclConflicts( existing->second, decl ) ) {
    634                                 existing->second = decl;
    635                         }
    636                 }
     572
     573                if ( ! structTable ) {
     574                        structTable = StructTable::new_ptr();
     575                } else {
     576                        ++*stats().map_lookups;
     577                        auto existing = structTable->find( id );
     578                        if ( existing != structTable->end() 
     579                                && existing->second.scope == scope
     580                                && addedDeclConflicts( existing->second.decl, decl ) ) return;
     581                }
     582
     583                lazyInitScope();
     584                ++*stats().map_mutations;
     585                structTable = structTable->set( id, Scoped<StructDecl>{ decl, scope } );
    637586        }
    638587
    639588        void Indexer::addEnum( EnumDecl *decl ) {
    640                 debugPrint( "Adding enum " << decl->name << std::endl );
    641                 makeWritable();
    642 
     589                ++*stats().add_calls;
    643590                const std::string &id = decl->name;
    644                 EnumTable::iterator existing = tables->enumTable.find( id );
    645                 if ( existing == tables->enumTable.end() ) {
    646                         EnumDecl *parent = tables->base.lookupEnumAtScope( id, scope );
    647                         if ( ! parent || ! addedDeclConflicts( parent, decl ) ) {
    648                                 tables->enumTable.insert( existing, std::make_pair( id, decl ) );
    649                                 ++tables->size;
    650                         }
    651                 } else {
    652                         if ( ! addedDeclConflicts( existing->second, decl ) ) {
    653                                 existing->second = decl;
    654                         }
    655                 }
     591
     592                if ( ! enumTable ) {
     593                        enumTable = EnumTable::new_ptr();
     594                } else {
     595                        ++*stats().map_lookups;
     596                        auto existing = enumTable->find( id );
     597                        if ( existing != enumTable->end() 
     598                                && existing->second.scope == scope
     599                                && addedDeclConflicts( existing->second.decl, decl ) ) return;
     600                }
     601               
     602                lazyInitScope();
     603                ++*stats().map_mutations;
     604                enumTable = enumTable->set( id, Scoped<EnumDecl>{ decl, scope } );
    656605        }
    657606
    658607        void Indexer::addUnion( const std::string &id ) {
    659                 debugPrint( "Adding fwd decl for union " << id << std::endl );
    660608                addUnion( new UnionDecl( id ) );
    661609        }
    662610
    663611        void Indexer::addUnion( UnionDecl *decl ) {
    664                 debugPrint( "Adding union " << decl->name << std::endl );
    665                 makeWritable();
    666 
     612                ++*stats().add_calls;
    667613                const std::string &id = decl->name;
    668                 UnionTable::iterator existing = tables->unionTable.find( id );
    669                 if ( existing == tables->unionTable.end() ) {
    670                         UnionDecl *parent = tables->base.lookupUnionAtScope( id, scope );
    671                         if ( ! parent || ! addedDeclConflicts( parent, decl ) ) {
    672                                 tables->unionTable.insert( existing, std::make_pair( id, decl ) );
    673                                 ++tables->size;
    674                         }
    675                 } else {
    676                         if ( ! addedDeclConflicts( existing->second, decl ) ) {
    677                                 existing->second = decl;
    678                         }
    679                 }
     614
     615                if ( ! unionTable ) {
     616                        unionTable = UnionTable::new_ptr();
     617                } else {
     618                        ++*stats().map_lookups;
     619                        auto existing = unionTable->find( id );
     620                        if ( existing != unionTable->end()
     621                                && existing->second.scope == scope
     622                                && addedDeclConflicts( existing->second.decl, decl ) ) return;
     623                }
     624
     625                lazyInitScope();
     626                ++*stats().map_mutations;
     627                unionTable = unionTable->set( id, Scoped<UnionDecl>{ decl, scope } );
    680628        }
    681629
    682630        void Indexer::addTrait( TraitDecl *decl ) {
    683                 debugPrint( "Adding trait " << decl->name << std::endl );
    684                 makeWritable();
    685 
     631                ++*stats().add_calls;
    686632                const std::string &id = decl->name;
    687                 TraitTable::iterator existing = tables->traitTable.find( id );
    688                 if ( existing == tables->traitTable.end() ) {
    689                         TraitDecl *parent = tables->base.lookupTraitAtScope( id, scope );
    690                         if ( ! parent || ! addedDeclConflicts( parent, decl ) ) {
    691                                 tables->traitTable.insert( existing, std::make_pair( id, decl ) );
    692                                 ++tables->size;
    693                         }
    694                 } else {
    695                         if ( ! addedDeclConflicts( existing->second, decl ) ) {
    696                                 existing->second = decl;
    697                         }
    698                 }
    699         }
    700 
    701         void Indexer::addMembers( AggregateDecl * aggr, Expression * expr, ConflictFunction handleConflicts ) {
     633
     634                if ( ! traitTable ) {
     635                        traitTable = TraitTable::new_ptr();
     636                } else {
     637                        ++*stats().map_lookups;
     638                        auto existing = traitTable->find( id );
     639                        if ( existing != traitTable->end()
     640                                && existing->second.scope == scope
     641                                && addedDeclConflicts( existing->second.decl, decl ) ) return;
     642                }
     643
     644                lazyInitScope();
     645                ++*stats().map_mutations;
     646                traitTable = traitTable->set( id, Scoped<TraitDecl>{ decl, scope } );
     647        }
     648
     649        void Indexer::addMembers( AggregateDecl * aggr, Expression * expr,
     650                        OnConflict handleConflicts ) {
    702651                for ( Declaration * decl : aggr->members ) {
    703652                        if ( DeclarationWithType * dwt = dynamic_cast< DeclarationWithType * >( decl ) ) {
    … …  
    705654                                if ( dwt->name == "" ) {
    706655                                        Type * t = dwt->get_type()->stripReferences();
    707                                         if ( dynamic_cast< StructInstType * >( t ) || dynamic_cast< UnionInstType * >( t ) ) {
     656                                        if ( dynamic_cast<StructInstType*>( t ) || dynamic_cast<UnionInstType*>( t ) ) {
    708657                                                Expression * base = expr->clone();
    709658                                                ResolvExpr::Cost cost = ResolvExpr::Cost::zero; // xxx - carry this cost into the indexer as a base cost?
    … …  
    722671                                assertf( aggr, "WithStmt expr has non-aggregate type: %s", toString( expr->result ).c_str() );
    723672
    724                                 addMembers( aggr, expr, [withStmt](IdData & existing, const std::string &) {
    725                                         // on conflict, delete the identifier
    726                                         existing.deleteStmt = withStmt;
    727                                         return true;
    728                                 });
     673                                addMembers( aggr, expr, OnConflict::deleteWith( withStmt ) );
    729674                        }
    730675                }
    … …  
    748693                addIds( ftype->returnVals );
    749694                addIds( ftype->parameters );
    750         }
    751 
    752         void Indexer::enterScope() {
    753                 ++scope;
    754 
    755                 if ( doDebug ) {
    756                         std::cerr << "--- Entering scope " << scope << std::endl;
    757                 }
    758         }
    759 
    760         void Indexer::leaveScope() {
    761                 using std::cerr;
    762 
    763                 assert( scope > 0 && "cannot leave initial scope" );
    764                 if ( doDebug ) {
    765                         cerr << "--- Leaving scope " << scope << " containing" << std::endl;
    766                 }
    767                 --scope;
    768 
    769                 while ( tables && tables->scope > scope ) {
    770                         if ( doDebug ) {
    771                                 dump( tables->idTable, cerr );
    772                                 dump( tables->typeTable, cerr );
    773                                 dump( tables->structTable, cerr );
    774                                 dump( tables->enumTable, cerr );
    775                                 dump( tables->unionTable, cerr );
    776                                 dump( tables->traitTable, cerr );
    777                         }
    778 
    779                         // swap tables for base table until we find one at an appropriate scope
    780                         Indexer::Impl *base = newRef( tables->base.tables );
    781                         deleteRef( tables );
    782                         tables = base;
    783                 }
    784         }
    785 
    786         void Indexer::print( std::ostream &os, int indent ) const {
    787                 using std::cerr;
    788 
    789                 if ( tables ) {
    790                         os << "--- scope " << tables->scope << " ---" << std::endl;
    791 
    792                         os << "===idTable===" << std::endl;
    793                         dump( tables->idTable, os );
    794                         os << "===typeTable===" << std::endl;
    795                         dump( tables->typeTable, os );
    796                         os << "===structTable===" << std::endl;
    797                         dump( tables->structTable, os );
    798                         os << "===enumTable===" << std::endl;
    799                         dump( tables->enumTable, os );
    800                         os << "===unionTable===" << std::endl;
    801                         dump( tables->unionTable, os );
    802                         os << "===contextTable===" << std::endl;
    803                         dump( tables->traitTable, os );
    804 
    805                         tables->base.print( os, indent );
    806                 } else {
    807                         os << "--- end ---" << std::endl;
    808                 }
    809 
    810695        }
    811696

  • src/SymTab/Indexer.h

    r709e0e0 r92d41a4  
    99// Author           : Richard C. Bilson
    1010// Created On       : Sun May 17 21:38:55 2015
    11 // Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Aug 17 16:09:12 2017
    13 // Update Count     : 8
     11// Last Modified By : Aaron B. Moss
     12// Last Modified On : Fri Mar  8 13:55:00 2019
     13// Update Count     : 9
    1414//
    1515
    1616#pragma once
    1717
    18 #include <iosfwd>             // for ostream
    19 #include <list>               // for list
    20 #include <string>             // for string
    21 #include <functional>         // for function
     18#include <functional>              // for function
     19#include <list>                    // for list
     20#include <memory>                  // for shared_ptr, enable_shared_from_this
     21#include <string>                  // for string
    2222
    23 #include "SynTree/Visitor.h"  // for Visitor
    24 #include "SynTree/SynTree.h"  // for AST nodes
     23#include "Common/PersistentMap.h"  // for PersistentMap
     24#include "SynTree/SynTree.h"       // for AST nodes
    2525
    2626namespace ResolvExpr {
    27 class Cost;
     27        class Cost;
    2828}
    2929
    3030namespace SymTab {
    31         class Indexer {
    32           public:
     31        class Indexer : public std::enable_shared_from_this<SymTab::Indexer> {
     32        public:
    3333                explicit Indexer();
     34                virtual ~Indexer();
    3435
    35                 Indexer( const Indexer &that );
    36                 Indexer( Indexer &&that );
    37                 virtual ~Indexer();
    38                 Indexer& operator= ( const Indexer &that );
    39                 Indexer& operator= ( Indexer &&that );
    40 
    41                 // when using an indexer manually (e.g., within a mutator traversal), it is necessary to tell the indexer
    42                 // explicitly when scopes begin and end
     36                // when using an indexer manually (e.g., within a mutator traversal), it is necessary to
     37                // tell the indexer explicitly when scopes begin and end
    4338                void enterScope();
    4439                void leaveScope();
    … …  
    5045                        /// non-null if this declaration is deleted
    5146                        BaseSyntaxNode * deleteStmt = nullptr;
     47                        /// scope of identifier
     48                        unsigned long scope = 0;
    5249
    5350                        // NOTE: shouldn't need either of these constructors, but gcc-4 does not properly support initializer lists with default members.
    5451                        IdData() = default;
    55                         IdData( DeclarationWithType * id, Expression * baseExpr, BaseSyntaxNode * deleteStmt ) : id( id ), baseExpr( baseExpr ), deleteStmt( deleteStmt ) {}
     52                        IdData(
     53                                DeclarationWithType * id, Expression * baseExpr, BaseSyntaxNode * deleteStmt,
     54                                unsigned long scope )
     55                                : id( id ), baseExpr( baseExpr ), deleteStmt( deleteStmt ), scope( scope ) {}
     56                        IdData( const IdData& o, BaseSyntaxNode * deleteStmt )
     57                                : id( o.id ), baseExpr( o.baseExpr ), deleteStmt( deleteStmt ), scope( o.scope ) {}
    5658
    5759                        Expression * combine( ResolvExpr::Cost & cost ) const;
    … …  
    8082                EnumDecl *globalLookupEnum( const std::string &id ) const;
    8183
    82                 void print( std::ostream &os, int indent = 0 ) const;
    83 
    84                 /// looks up a specific mangled ID at the given scope
    85                 IdData * lookupIdAtScope( const std::string &id, const std::string &mangleName, unsigned long scope );
    86                 const IdData * lookupIdAtScope( const std::string &id, const std::string &mangleName, unsigned long scope ) const;
    87                 /// returns true if there exists a declaration with C linkage and the given name with a different mangled name
    88                 bool hasIncompatibleCDecl( const std::string &id, const std::string &mangleName, unsigned long scope ) const;
    89                 /// returns true if there exists a declaration with C linkage and the given name with the same mangled name
    90                 bool hasCompatibleCDecl( const std::string &id, const std::string &mangleName, unsigned long scope ) const;
    91                 // equivalents to lookup functions that only look at tables at scope `scope` (which should be >= tables->scope)
    92                 NamedTypeDecl *lookupTypeAtScope( const std::string &id, unsigned long scope ) const;
    93                 StructDecl *lookupStructAtScope( const std::string &id, unsigned long scope ) const;
    94                 EnumDecl *lookupEnumAtScope( const std::string &id, unsigned long scope ) const;
    95                 UnionDecl *lookupUnionAtScope( const std::string &id, unsigned long scope ) const;
    96                 TraitDecl *lookupTraitAtScope( const std::string &id, unsigned long scope ) const;
    97 
    98                 typedef std::function<bool(IdData &, const std::string &)> ConflictFunction;
    99 
    10084                void addId( DeclarationWithType * decl, Expression * baseExpr = nullptr );
    10185                void addDeletedId( DeclarationWithType * decl, BaseSyntaxNode * deleteStmt );
    … …  
    11296                void addWith( std::list< Expression * > & withExprs, BaseSyntaxNode * withStmt );
    11397
    114                 /// adds all of the members of the Aggregate (addWith helper)
    115                 void addMembers( AggregateDecl * aggr, Expression * expr, ConflictFunction );
    116 
    11798                /// convenience function for adding a list of Ids to the indexer
    11899                void addIds( const std::list< DeclarationWithType * > & decls );
    … …  
    124105                void addFunctionType( FunctionType * ftype );
    125106
    126                 bool doDebug = false; ///< Display debugging trace?
    127107          private:
    128                 struct Impl;
     108                /// Wraps a Decl* with a scope
     109                template<typename Decl>
     110                struct Scoped {
     111                        Decl* decl;           ///< declaration
     112                        unsigned long scope;  ///< scope of this declaration
    129113
    130                 Impl *tables;         ///< Copy-on-write instance of table data structure
    131                 unsigned long scope;  ///< Scope index of this pointer
     114                        Scoped(Decl* d, unsigned long s) : decl(d), scope(s) {}
     115                };
    132116
    133                 /// Takes a new ref to a table (returns null if null)
    134                 static Impl *newRef( Impl *toClone );
    135                 /// Clears a ref to a table (does nothing if null)
    136                 static void deleteRef( Impl *toFree );
     117                using Ptr = std::shared_ptr<const Indexer>;
    137118
    138                 // Removes matching autogenerated constructors and destructors
    139                 // so that they will not be selected
    140                 // void removeSpecialOverrides( FunctionDecl *decl );
    141                 void removeSpecialOverrides( const std::string &id, std::list< IdData > & out ) const;
     119                using MangleTable = PersistentMap< std::string, IdData >;
     120                using IdTable = PersistentMap< std::string, MangleTable::Ptr >;
     121                using TypeTable = PersistentMap< std::string, Scoped<NamedTypeDecl> >;
     122                using StructTable = PersistentMap< std::string, Scoped<StructDecl> >;
     123                using EnumTable = PersistentMap< std::string, Scoped<EnumDecl> >;
     124                using UnionTable = PersistentMap< std::string, Scoped<UnionDecl> >;
     125                using TraitTable = PersistentMap< std::string, Scoped<TraitDecl> >;
    142126
    143                 /// Ensures that tables variable is writable (i.e. allocated, uniquely owned by this Indexer, and at the current scope)
    144                 void makeWritable();
     127                IdTable::Ptr idTable;          ///< identifier namespace
     128                TypeTable::Ptr typeTable;      ///< type namespace
     129                StructTable::Ptr structTable;  ///< struct namespace
     130                EnumTable::Ptr enumTable;      ///< enum namespace
     131                UnionTable::Ptr unionTable;    ///< union namespace
     132                TraitTable::Ptr traitTable;    ///< trait namespace
     133
     134                Ptr prevScope;                 ///< reference to indexer for parent scope
     135                unsigned long scope;           ///< Scope index of this indexer
     136                unsigned long repScope;        ///< Scope index of currently represented scope
     137
     138                /// Ensures that a proper backtracking scope exists before a mutation
     139                void lazyInitScope();
     140
     141                /// Gets the indexer at the given scope
     142                const Indexer* atScope( unsigned long scope ) const;
     143
     144                /// Removes matching autogenerated constructors and destructors so that they will not be
     145                /// selected. If returns false, passed decl should not be added.
     146                bool removeSpecialOverrides( IdData& decl, MangleTable::Ptr& mangleTable );
     147
     148                /// Options for handling identifier conflicts
     149                struct OnConflict {
     150                        enum {
     151                                Error,  ///< Throw a semantic error
     152                                Delete  ///< Delete the earlier version with the delete statement
     153                        } mode;
     154                        BaseSyntaxNode * deleteStmt;  ///< Statement that deletes this expression
     155
     156                private:
     157                        OnConflict() : mode(Error), deleteStmt(nullptr) {}
     158                        OnConflict( BaseSyntaxNode * d ) : mode(Delete), deleteStmt(d) {}
     159                public:
     160                        OnConflict( const OnConflict& ) = default;
     161
     162                        static OnConflict error() { return {}; }
     163                        static OnConflict deleteWith( BaseSyntaxNode * d ) { return { d }; }
     164                };
     165
     166                /// true if the existing identifier conflicts with the added identifier
     167                bool addedIdConflicts(
     168                        const IdData& existing, DeclarationWithType * added, OnConflict handleConflicts,
     169                        BaseSyntaxNode * deleteStmt );
    145170
    146171                /// common code for addId, addDeletedId, etc.
    147                 void addId( DeclarationWithType * decl, ConflictFunction, Expression * baseExpr = nullptr, BaseSyntaxNode * deleteStmt = nullptr );
     172                void addId(
     173                        DeclarationWithType * decl, OnConflict handleConflicts,
     174                        Expression * baseExpr = nullptr, BaseSyntaxNode * deleteStmt = nullptr );
     175
     176                /// adds all of the members of the Aggregate (addWith helper)
     177                void addMembers( AggregateDecl * aggr, Expression * expr, OnConflict handleConflicts );
     178
     179                /// returns true if there exists a declaration with C linkage and the given name with the same mangled name
     180                bool hasCompatibleCDecl( const std::string &id, const std::string &mangleName ) const;
     181                /// returns true if there exists a declaration with C linkage and the given name with a different mangled name
     182                bool hasIncompatibleCDecl( const std::string &id, const std::string &mangleName ) const;
    148183        };
    149184} // namespace SymTab

  • src/SynTree/BaseSyntaxNode.h

    r709e0e0 r92d41a4  
    1818#include "Common/CodeLocation.h"
    1919#include "Common/Indenter.h"
     20#include "Common/Stats.h"
     21
    2022class Visitor;
    2123class Mutator;
    … …  
    2325class BaseSyntaxNode {
    2426  public:
     27  static Stats::Counters::SimpleCounter* new_nodes;
     28
    2529        CodeLocation location;
     30
     31  BaseSyntaxNode() { ++*new_nodes; }
     32  BaseSyntaxNode( const BaseSyntaxNode& ) { ++*new_nodes; }
    2633
    2734        virtual ~BaseSyntaxNode() {}

  • src/main.cc

    r709e0e0 r92d41a4  
    6565using namespace std;
    6666
    67 
    6867void NewPass(const char * const name) {
    6968        Stats::Heap::newPass(name);
    7069        using namespace Stats::Counters;
    71         static auto pass_visitor_group = build<CounterGroup>("Pass Visitor");
    72         auto pass = build<CounterGroup>(name, pass_visitor_group);
    73         pass_visitor_stats.depth = 0;
    74         pass_visitor_stats.avg = build<AverageCounter<double>>("Average Depth", pass);
    75         pass_visitor_stats.max = build<MaxCounter<double>>("Max Depth", pass);
     70       
     71        {
     72                static auto group = build<CounterGroup>("Pass Visitor");
     73                auto pass = build<CounterGroup>(name, group);
     74                pass_visitor_stats.depth = 0;
     75                pass_visitor_stats.avg = build<AverageCounter<double>>("Average Depth", pass);
     76                pass_visitor_stats.max = build<MaxCounter<double>>("Max Depth", pass);
     77        }
     78
     79        {
     80                static auto group = build<CounterGroup>("Syntax Node");
     81                auto pass = build<CounterGroup>(name, group);
     82                BaseSyntaxNode::new_nodes = build<SimpleCounter>("Allocs", pass);
     83        }
    7684}
    7785
Note: See TracChangeset for help on using the changeset viewer.