Index: src/Common/PassVisitor.cc =================================================================== --- src/Common/PassVisitor.cc (revision 90b9e4b6a9b073a0248ee68f44eabdfbf4a4295b) +++ src/Common/PassVisitor.cc (revision 9399057263e3e87e8eb54c6a89f9bc4827990ff6) @@ -17,2 +17,3 @@ PassVisitorStats pass_visitor_stats; +Stats::Counters::SimpleCounter* BaseSyntaxNode::new_nodes = nullptr; Index: src/Common/PersistentMap.h =================================================================== --- src/Common/PersistentMap.h (revision 9399057263e3e87e8eb54c6a89f9bc4827990ff6) +++ src/Common/PersistentMap.h (revision 9399057263e3e87e8eb54c6a89f9bc4827990ff6) @@ -0,0 +1,292 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// PersistentMap.h -- +// +// Author : Aaron B. Moss +// Created On : Thu Mar 7 15:50:00 2019 +// Last Modified By : Aaron B. Moss +// Last Modified On : Thu Mar 7 15:50:00 2019 +// Update Count : 1 +// + +#pragma once + +#include // for assertf +#include // for size_t +#include // for hash, equal_to +#include // for shared_ptr, enable_shared_from_this, make_shared +#include // for unordered_map +#include // for forward, move + +/// Wraps a hash table in a persistent data structure, using a technique based +/// on the persistent array in Conchon & Filliatre "A Persistent Union-Find +/// Data Structure" + +template, typename Eq = std::equal_to> +class PersistentMap + : public std::enable_shared_from_this> { +public: + /// Type of this class + using Self = PersistentMap; + /// Type of pointer to this class + using Ptr = std::shared_ptr; + + /// Types of version nodes + enum Mode { + BASE, ///< Root node of version tree + REM, ///< Key removal node + INS, ///< Key update node + UPD ///< Key update node + }; + +private: + using Base = std::unordered_map; + + /// Insertion/update node + struct Ins { + Ptr base; ///< Modified map + Key key; ///< Key inserted + Val val; ///< Value stored + + template + Ins(P&& p, K&& k, V&& v) + : base(std::forward

(p)), key(std::forward(k)), val(std::forward(v)) {} + }; + + /// Removal node + struct Rem { + Ptr base; ///< Modified map + Key key; ///< Key removed + + template + Rem(P&& p, K&& k) : base(std::forward

(p)), key(std::forward(k)) {} + }; + + /// Underlying storage + union Data { + char def; + Base base; + Ins ins; + Rem rem; + + Data() : def('\0') {} + ~Data() {} + } data; + + /// Type of node + mutable Mode mode; + + /// get mutable reference as T + template + T& as() { return reinterpret_cast(data); } + + /// get const reference as T + template + const T& as() const { return reinterpret_cast(data); } + + /// get rvalue reference as T + template + T&& take_as() { return std::move(as()); } + + /// initialize as T + template + void init( Args&&... args ) { + new( &as() ) T { std::forward(args)... }; + } + + /// reset as current mode + void reset() { + switch( mode ) { + case BASE: as().~Base(); break; + case REM: as().~Rem(); break; + case INS: case UPD: as().~Ins(); break; + } + } + + /// reset as base + void reset_as_base() { + as().~Base(); + } + +public: + using key_type = typename Base::key_type; + using mapped_type = typename Base::mapped_type; + using value_type = typename Base::value_type; + using size_type = typename Base::size_type; + using difference_type = typename Base::difference_type; + using iterator = typename Base::const_iterator; + + PersistentMap() : data(), mode(BASE) { init(); } + + PersistentMap( Base&& b ) : data(), mode(BASE) { init(std::move(b)); } + + PersistentMap( const Self& o ) = delete; + + Self& operator= ( const Self& o ) = delete; + + ~PersistentMap() { reset(); } + + /// Create a pointer to a new, empty persistent map + static Ptr new_ptr() { return std::make_shared(); } + + /// reroot persistent map at current node + void reroot() const { + // recursive base case + if ( mode == BASE ) return; + + // reroot base + Self* mut_this = const_cast(this); + Ptr base = ( mode == REM ) ? mut_this->as().base : mut_this->as().base; + base->reroot(); + + // remove map from base + Base base_map = base->take_as(); + base->reset_as_base(); + + // switch base to inverse of self and mutate base map + switch ( mode ) { + case REM: { + Rem& self = mut_this->as(); + auto it = base_map.find( self.key ); + + base->init( + mut_this->shared_from_this(), std::move(self.key), std::move(it->second) ); + base->mode = INS; + + base_map.erase( it ); + break; + } + case INS: { + Ins& self = mut_this->as(); + + base->init( mut_this->shared_from_this(), self.key ); + base->mode = REM; + + base_map.emplace( std::move(self.key), std::move(self.val) ); + break; + } + case UPD: { + Ins& self = mut_this->as(); + auto it = base_map.find( self.key ); + + base->init( + mut_this->shared_from_this(), std::move(self.key), std::move(it->second) ); + base->mode = UPD; + + it->second = std::move(self.val); + break; + } + case BASE: assertf(false, "unreachable"); break; + } + + // set base map into self + mut_this->reset(); + mut_this->init( std::move(base_map) ); + mode = BASE; + } + +private: + /// the base after rerooting at the current node + const Base& rerooted() const { + reroot(); + return as(); + } + +public: + /// true iff the map is empty + bool empty() const { return rerooted().empty(); } + + /// number of entries in map + size_type size() const { return rerooted().size(); } + + /// begin iterator for map; may be invalidated by calls to non-iteration functions + /// or functions on other maps in the same tree + iterator begin() const { return rerooted().begin(); } + + /// end iterator for map; may be invalidated by calls to non-iteration functions + /// or functions on other maps in the same tree + iterator end() const { return rerooted().end(); } + + /// underlying map iterator for value + iterator find(const Key& k) const { return rerooted().find( k ); } + + /// check if value is present + size_type count(const Key& k) const { return rerooted().count( k ); } + + /// get value; undefined behaviour if not present + const Val& get(const Key& k) const { + const Base& self = rerooted(); + auto it = self.find( k ); + return it->second; + } + + /// get value; returns default if not present + template + Val get_or_default(const Key& k, V&& d) const { + const Base& self = rerooted(); + auto it = self.find( k ); + if ( it == self.end() ) return d; + else return it->second; + } + + /// set value, storing new map in output variable + template + Ptr set(K&& k, V&& v) { + reroot(); + + // transfer map to new node + Ptr ret = std::make_shared( take_as() ); + reset_as_base(); + Base& base_map = ret->as(); + + // check if this is update or insert + auto it = base_map.find( k ); + if ( it == base_map.end() ) { + // set self to REM node and insert into base + init( ret, k ); + mode = REM; + + base_map.emplace_hint( it, std::forward(k), std::forward(v) ); + } else { + // set self to UPD node and modify base + init( ret, std::forward(k), std::move(it->second) ); + mode = UPD; + + it->second = std::forward(v); + } + + return ret; + } + + /// remove value, storing new map in output variable; does nothing if key not in map + Ptr erase(const Key& k) { + reroot(); + + // exit early if key does not exist in map + if ( ! as().count( k ) ) return this->shared_from_this(); + + // transfer map to new node + Ptr ret = std::make_shared( take_as() ); + reset_as_base(); + Base& base_map = ret->as(); + + // set self to INS node and remove from base + init( ret, k, base_map[k] ); + mode = INS; + + base_map.erase( k ); + + return ret; + } +}; + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/Common/Stats/Counter.h =================================================================== --- src/Common/Stats/Counter.h (revision 90b9e4b6a9b073a0248ee68f44eabdfbf4a4295b) +++ src/Common/Stats/Counter.h (revision 9399057263e3e87e8eb54c6a89f9bc4827990ff6) @@ -37,4 +37,5 @@ class SimpleCounter { public: + inline void operator++() {} inline void operator++(int) {} inline void operator+=(size_t) {} @@ -84,4 +85,5 @@ virtual void print(std::ostream & os) override { os << count; } + inline void operator++() { if(!enabled) return; count++; } inline void operator++(int) { if(!enabled) return; count++; } inline void operator+=(size_t value) { if(!enabled) return; count += value; } Index: src/SymTab/Indexer.cc =================================================================== --- src/SymTab/Indexer.cc (revision 90b9e4b6a9b073a0248ee68f44eabdfbf4a4295b) +++ src/SymTab/Indexer.cc (revision 9399057263e3e87e8eb54c6a89f9bc4827990ff6) @@ -9,7 +9,7 @@ // Author : Richard C. Bilson // Created On : Sun May 17 21:37:33 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Thu Aug 17 16:08:40 2017 -// Update Count : 20 +// Last Modified By : Aaron B. Moss +// Last Modified On : Fri Mar 8 13:55:00 2019 +// Update Count : 21 // @@ -17,15 +17,16 @@ #include // for assert, strict_dynamic_cast -#include // for operator<<, basic_ostream, ostream #include // for string, operator<<, operator!= +#include // for shared_ptr, make_shared #include // for operator!=, unordered_map<>::const... #include // for unordered_set #include // for pair, make_pair, move +#include // for vector #include "CodeGen/OperatorTable.h" // for isCtorDtor, isCtorDtorAssign #include "Common/SemanticError.h" // for SemanticError #include "Common/utility.h" // for cloneAll -#include "Common/Stats/Counter.h" // for counters -#include "GenPoly/GenPoly.h" +#include "Common/Stats/Counter.h" // for counters +#include "GenPoly/GenPoly.h" // for getFunctionType #include "InitTweak/InitTweak.h" // for isConstructor, isCopyFunction, isC... #include "Mangler.h" // for Mangler @@ -39,27 +40,9 @@ #include "SynTree/Type.h" // for Type, StructInstType, UnionInstType -#define debugPrint(x) if ( doDebug ) { std::cerr << x; } - namespace SymTab { // Statistics block namespace { - - static inline auto stats_idtable() { - using namespace Stats::Counters; - static auto group = build("IdTable"); - static struct { - SimpleCounter * find; - AverageCounter * size; - AverageCounter * key; - } ret = { - .find = build("Find calls", group), - .size = build>("Average Size", group), - .key = build>("Average Key Size", group), - }; - return ret; - } - - static inline auto stats_indexers() { + static inline auto stats() { using namespace Stats::Counters; static auto group = build("Indexers"); @@ -67,11 +50,23 @@ SimpleCounter * count; AverageCounter * size; - AverageCounter * depth_a; - MaxCounter * depth_m; + SimpleCounter * new_scopes; + SimpleCounter * lazy_scopes; + AverageCounter * avg_scope_depth; + MaxCounter * max_scope_depth; + SimpleCounter * add_calls; + SimpleCounter * lookup_calls; + SimpleCounter * map_lookups; + SimpleCounter * map_mutations; } ret = { .count = build("Count", group), .size = build>("Average Size", group), - .depth_a = build>("Average Depth", group), - .depth_m = build>("Max Depth", group), + .new_scopes = build("Scopes", group), + .lazy_scopes = build("Lazy Scopes", group), + .avg_scope_depth = build>("Average Scope", group), + .max_scope_depth = build>("Max Scope", group), + .add_calls = build("Add Calls", group), + .lookup_calls = build("Lookup Calls", group), + .map_lookups = build("Map Lookups", group), + .map_mutations = build("Map Mutations", group) }; return ret; @@ -79,391 +74,116 @@ } - std::ostream & operator<<( std::ostream & out, const Indexer::IdData & data ) { - return out << "(" << data.id << "," << data.baseExpr << ")"; - } - - typedef std::unordered_map< std::string, Indexer::IdData > MangleTable; - typedef std::unordered_map< std::string, MangleTable > IdTable; - typedef std::unordered_map< std::string, NamedTypeDecl* > TypeTable; - typedef std::unordered_map< std::string, StructDecl* > StructTable; - typedef std::unordered_map< std::string, EnumDecl* > EnumTable; - typedef std::unordered_map< std::string, UnionDecl* > UnionTable; - typedef std::unordered_map< std::string, TraitDecl* > TraitTable; - - void dump( const IdTable &table, std::ostream &os ) { - for ( IdTable::const_iterator id = table.begin(); id != table.end(); ++id ) { - for ( MangleTable::const_iterator mangle = id->second.begin(); mangle != id->second.end(); ++mangle ) { - os << mangle->second << std::endl; - } - } - } - - template< typename Decl > - void dump( const std::unordered_map< std::string, Decl* > &table, std::ostream &os ) { - for ( typename std::unordered_map< std::string, Decl* >::const_iterator it = table.begin(); it != table.end(); ++it ) { - os << it->second << std::endl; - } // for - } - - struct Indexer::Impl { - Impl( unsigned long _scope ) : refCount(1), scope( _scope ), size( 0 ), base(), - idTable(), typeTable(), structTable(), enumTable(), unionTable(), traitTable() {} - Impl( unsigned long _scope, Indexer &&_base ) : refCount(1), scope( _scope ), size( 0 ), base( _base ), - idTable(), typeTable(), structTable(), enumTable(), unionTable(), traitTable() {} - unsigned long refCount; ///< Number of references to these tables - unsigned long scope; ///< Scope these tables are associated with - unsigned long size; ///< Number of elements stored in this table - const Indexer base; ///< Base indexer this extends - - IdTable idTable; ///< Identifier namespace - TypeTable typeTable; ///< Type namespace - StructTable structTable; ///< Struct namespace - EnumTable enumTable; ///< Enum namespace - UnionTable unionTable; ///< Union namespace - TraitTable traitTable; ///< Trait namespace - }; - - Indexer::Impl *Indexer::newRef( Indexer::Impl *toClone ) { - if ( ! toClone ) return 0; - - // shorten the search chain by skipping empty links - Indexer::Impl *ret = toClone->size == 0 ? toClone->base.tables : toClone; - if ( ret ) { ++ret->refCount; } - - return ret; - } - - void Indexer::deleteRef( Indexer::Impl *toFree ) { - if ( ! toFree ) return; - - if ( --toFree->refCount == 0 ) delete toFree; - } - - void Indexer::removeSpecialOverrides( const std::string &id, std::list< IdData > & out ) const { - // only need to perform this step for constructors, destructors, and assignment functions - if ( ! CodeGen::isCtorDtorAssign( id ) ) return; - - // helpful data structure to organize properties for a type - struct ValueType { - struct DeclBall { // properties for this particular decl - IdData decl; - bool isUserDefinedFunc; - bool isCopyFunc; - }; - // properties for this type - bool existsUserDefinedCopyFunc = false; // user-defined copy ctor found - BaseSyntaxNode * deleteStmt = nullptr; // non-null if a user-defined function is found - std::list< DeclBall > decls; - - // another FunctionDecl for the current type was found - determine - // if it has special properties and update data structure accordingly - ValueType & operator+=( IdData data ) { - DeclarationWithType * function = data.id; - bool isUserDefinedFunc = ! LinkageSpec::isOverridable( function->linkage ); - bool isCopyFunc = InitTweak::isCopyFunction( function, function->name ); - decls.push_back( DeclBall{ data, isUserDefinedFunc, isCopyFunc } ); - existsUserDefinedCopyFunc = existsUserDefinedCopyFunc || (isUserDefinedFunc && isCopyFunc); - if ( isUserDefinedFunc && ! deleteStmt ) { - // any user-defined function can act as an implicit delete statement for generated constructors. - // a delete stmt should not act as an implicit delete statement. - deleteStmt = data.id; - } - return *this; - } - }; // ValueType - - std::list< IdData > copy; - copy.splice( copy.end(), out ); - - // organize discovered declarations by type - std::unordered_map< std::string, ValueType > funcMap; - for ( auto decl : copy ) { - if ( FunctionDecl * function = dynamic_cast< FunctionDecl * >( decl.id ) ) { - std::list< DeclarationWithType * > & params = function->type->parameters; - assert( ! params.empty() ); - // use base type of pointer, so that qualifiers on the pointer type aren't considered. - Type * base = InitTweak::getPointerBase( params.front()->get_type() ); - assert( base ); - funcMap[ Mangler::mangle( base ) ] += decl; - } else { - out.push_back( decl ); - } - } - - // if a type contains user defined ctor/dtor/assign, then special rules trigger, which determine - // the set of ctor/dtor/assign that can be used by the requester. In particular, if the user defines - // a default ctor, then the generated default ctor is unavailable, likewise for copy ctor - // and dtor. If the user defines any ctor/dtor, then no generated field ctors are available. - // If the user defines any ctor then the generated default ctor is unavailable (intrinsic default - // ctor must be overridden exactly). If the user defines anything that looks like a copy constructor, - // then the generated copy constructor is unavailable, and likewise for the assignment operator. - for ( std::pair< const std::string, ValueType > & pair : funcMap ) { - ValueType & val = pair.second; - for ( ValueType::DeclBall ball : val.decls ) { - bool isNotUserDefinedFunc = ! ball.isUserDefinedFunc && ball.decl.id->linkage != LinkageSpec::Intrinsic; - bool isCopyFunc = ball.isCopyFunc; - bool existsUserDefinedCopyFunc = val.existsUserDefinedCopyFunc; - - // only implicitly delete non-user defined functions that are not intrinsic, and are - // not copy functions (assignment or copy constructor). If a user-defined copy function exists, - // do not pass along the non-user-defined copy functions since signatures do not have to match, - // and the generated functions will often be cheaper. - if ( isNotUserDefinedFunc ) { - if ( isCopyFunc ) { - // Skip over non-user-defined copy functions when there is a user-defined copy function. - // Since their signatures do not have to be exact, deleting them is the wrong choice. - if ( existsUserDefinedCopyFunc ) continue; - } else { - // delete non-user-defined non-copy functions if applicable. - // deleteStmt will be non-null only if a user-defined function is found. - ball.decl.deleteStmt = val.deleteStmt; - } - } - out.push_back( ball.decl ); - } - } - } - - void Indexer::makeWritable() { - if ( ! tables ) { - // create indexer if not yet set - tables = new Indexer::Impl( scope ); - } else if ( tables->refCount > 1 || tables->scope != scope ) { - // make this indexer the base of a fresh indexer at the current scope - tables = new Indexer::Impl( scope, std::move( *this ) ); - } - } - - Indexer::Indexer() : tables( 0 ), scope( 0 ) { - (*stats_indexers().count)++; - } - - Indexer::Indexer( const Indexer &that ) : doDebug( that.doDebug ), tables( newRef( that.tables ) ), scope( that.scope ) { - (*stats_indexers().count)++; - } - - Indexer::Indexer( Indexer &&that ) : doDebug( that.doDebug ), tables( that.tables ), scope( that.scope ) { - that.tables = 0; - } + Indexer::Indexer() + : idTable(), typeTable(), structTable(), enumTable(), unionTable(), traitTable(), + prevScope(), scope( 0 ), repScope( 0 ) { ++*stats().count; } Indexer::~Indexer() { - if(tables) { - stats_indexers().size->push( tables->idTable.size() ); - size_t depth = 1; - for( auto crnt = tables->base.tables; crnt; crnt = crnt->base.tables ) { - ++depth; - } - stats_indexers().depth_a->push( depth ); - stats_indexers().depth_m->push( depth ); - } - deleteRef( tables ); - } - - Indexer& Indexer::operator= ( const Indexer &that ) { - deleteRef( tables ); - - tables = newRef( that.tables ); - scope = that.scope; - doDebug = that.doDebug; - - return *this; - } - - Indexer& Indexer::operator= ( Indexer &&that ) { - deleteRef( tables ); - - tables = that.tables; - scope = that.scope; - doDebug = that.doDebug; - - that.tables = 0; - - return *this; + stats().size->push( idTable ? idTable->size() : 0 ); + } + + void Indexer::lazyInitScope() { + if ( repScope < scope ) { + ++*stats().lazy_scopes; + // create rollback + prevScope = std::make_shared( *this ); + // update repScope + repScope = scope; + } + } + + void Indexer::enterScope() { + ++scope; + + ++*stats().new_scopes; + stats().avg_scope_depth->push( scope ); + stats().max_scope_depth->push( scope ); + } + + void Indexer::leaveScope() { + if ( repScope == scope ) { + Ptr prev = prevScope; // make sure prevScope stays live + *this = std::move(*prevScope); // replace with previous scope + } + + --scope; } void Indexer::lookupId( const std::string &id, std::list< IdData > &out ) const { - std::unordered_set< std::string > foundMangleNames; - - Indexer::Impl *searchTables = tables; - while ( searchTables ) { - - (*stats_idtable().find)++; - stats_idtable().key->push( id.size() ); - stats_idtable().size->push( searchTables->idTable.size() ); - IdTable::const_iterator decls = searchTables->idTable.find( id ); - if ( decls != searchTables->idTable.end() ) { - const MangleTable &mangleTable = decls->second; - for ( MangleTable::const_iterator decl = mangleTable.begin(); decl != mangleTable.end(); ++decl ) { - // mark the mangled name as found, skipping this insertion if a declaration for that name has already been found - if ( foundMangleNames.insert( decl->first ).second == false ) continue; - - out.push_back( decl->second ); - } - } - - // get declarations from base indexers - searchTables = searchTables->base.tables; - } - - // some special functions, e.g. constructors and destructors - // remove autogenerated functions when they are defined so that - // they can never be matched - removeSpecialOverrides( id, out ); + ++*stats().lookup_calls; + if ( ! idTable ) return; + + ++*stats().map_lookups; + auto decls = idTable->find( id ); + if ( decls == idTable->end() ) return; + + for ( auto decl : *(decls->second) ) { + out.push_back( decl.second ); + } } NamedTypeDecl *Indexer::lookupType( const std::string &id ) const { - if ( ! tables ) return 0; - - TypeTable::const_iterator ret = tables->typeTable.find( id ); - return ret != tables->typeTable.end() ? ret->second : tables->base.lookupType( id ); + ++*stats().lookup_calls; + if ( ! typeTable ) return nullptr; + ++*stats().map_lookups; + auto it = typeTable->find( id ); + return it == typeTable->end() ? nullptr : it->second.decl; } StructDecl *Indexer::lookupStruct( const std::string &id ) const { - if ( ! tables ) return 0; - - StructTable::const_iterator ret = tables->structTable.find( id ); - return ret != tables->structTable.end() ? ret->second : tables->base.lookupStruct( id ); + ++*stats().lookup_calls; + if ( ! structTable ) return nullptr; + ++*stats().map_lookups; + auto it = structTable->find( id ); + return it == structTable->end() ? nullptr : it->second.decl; + } + + EnumDecl *Indexer::lookupEnum( const std::string &id ) const { + ++*stats().lookup_calls; + if ( ! enumTable ) return nullptr; + ++*stats().map_lookups; + auto it = enumTable->find( id ); + return it == enumTable->end() ? nullptr : it->second.decl; + } + + UnionDecl *Indexer::lookupUnion( const std::string &id ) const { + ++*stats().lookup_calls; + if ( ! unionTable ) return nullptr; + ++*stats().map_lookups; + auto it = unionTable->find( id ); + return it == unionTable->end() ? nullptr : it->second.decl; + } + + TraitDecl *Indexer::lookupTrait( const std::string &id ) const { + ++*stats().lookup_calls; + if ( ! traitTable ) return nullptr; + ++*stats().map_lookups; + auto it = traitTable->find( id ); + return it == traitTable->end() ? nullptr : it->second.decl; + } + + const Indexer* Indexer::atScope( unsigned long target ) const { + // by lazy construction, final indexer in list has repScope 0, cannot be > target + // otherwise, will find first scope representing the target + const Indexer* indexer = this; + while ( indexer->repScope > target ) { + indexer = indexer->prevScope.get(); + } + return indexer; } NamedTypeDecl *Indexer::globalLookupType( const std::string &id ) const { - return lookupTypeAtScope( id, 0 ); + return atScope( 0 )->lookupType( id ); } StructDecl *Indexer::globalLookupStruct( const std::string &id ) const { - return lookupStructAtScope( id, 0 ); + return atScope( 0 )->lookupStruct( id ); } UnionDecl *Indexer::globalLookupUnion( const std::string &id ) const { - return lookupUnionAtScope( id, 0 ); + return atScope( 0 )->lookupUnion( id ); } EnumDecl *Indexer::globalLookupEnum( const std::string &id ) const { - return lookupEnumAtScope( id, 0 ); - } - - EnumDecl *Indexer::lookupEnum( const std::string &id ) const { - if ( ! tables ) return 0; - - EnumTable::const_iterator ret = tables->enumTable.find( id ); - return ret != tables->enumTable.end() ? ret->second : tables->base.lookupEnum( id ); - } - - UnionDecl *Indexer::lookupUnion( const std::string &id ) const { - if ( ! tables ) return 0; - - UnionTable::const_iterator ret = tables->unionTable.find( id ); - return ret != tables->unionTable.end() ? ret->second : tables->base.lookupUnion( id ); - } - - TraitDecl *Indexer::lookupTrait( const std::string &id ) const { - if ( ! tables ) return 0; - - TraitTable::const_iterator ret = tables->traitTable.find( id ); - return ret != tables->traitTable.end() ? ret->second : tables->base.lookupTrait( id ); - } - - const Indexer::IdData * Indexer::lookupIdAtScope( const std::string &id, const std::string &mangleName, unsigned long scope ) const { - if ( ! tables ) return nullptr; - if ( tables->scope < scope ) return nullptr; - - (*stats_idtable().find)++; - stats_idtable().key->push( id.size() ); - stats_idtable().size->push( tables->idTable.size() ); - IdTable::const_iterator decls = tables->idTable.find( id ); - if ( decls != tables->idTable.end() ) { - const MangleTable &mangleTable = decls->second; - MangleTable::const_iterator decl = mangleTable.find( mangleName ); - if ( decl != mangleTable.end() ) return &decl->second; - } - - return tables->base.lookupIdAtScope( id, mangleName, scope ); - } - - Indexer::IdData * Indexer::lookupIdAtScope( const std::string &id, const std::string &mangleName, unsigned long scope ) { - return const_cast(const_cast(this)->lookupIdAtScope( id, mangleName, scope )); - } - - bool Indexer::hasIncompatibleCDecl( const std::string &id, const std::string &mangleName, unsigned long scope ) const { - if ( ! tables ) return false; - if ( tables->scope < scope ) return false; - - (*stats_idtable().find)++; - stats_idtable().key->push( id.size() ); - stats_idtable().size->push( tables->idTable.size() ); - IdTable::const_iterator decls = tables->idTable.find( id ); - if ( decls != tables->idTable.end() ) { - const MangleTable &mangleTable = decls->second; - for ( MangleTable::const_iterator decl = mangleTable.begin(); decl != mangleTable.end(); ++decl ) { - // check for C decls with the same name, skipping those with a compatible type (by mangleName) - if ( ! LinkageSpec::isMangled( decl->second.id->get_linkage() ) && decl->first != mangleName ) return true; - } - } - - return tables->base.hasIncompatibleCDecl( id, mangleName, scope ); - } - - bool Indexer::hasCompatibleCDecl( const std::string &id, const std::string &mangleName, unsigned long scope ) const { - if ( ! tables ) return false; - if ( tables->scope < scope ) return false; - - (*stats_idtable().find)++; - stats_idtable().key->push( id.size() ); - stats_idtable().size->push( tables->idTable.size() ); - IdTable::const_iterator decls = tables->idTable.find( id ); - if ( decls != tables->idTable.end() ) { - const MangleTable &mangleTable = decls->second; - for ( MangleTable::const_iterator decl = mangleTable.begin(); decl != mangleTable.end(); ++decl ) { - // check for C decls with the same name, skipping - // those with an incompatible type (by mangleName) - if ( ! LinkageSpec::isMangled( decl->second.id->get_linkage() ) && decl->first == mangleName ) return true; - } - } - - return tables->base.hasCompatibleCDecl( id, mangleName, scope ); - } - - NamedTypeDecl *Indexer::lookupTypeAtScope( const std::string &id, unsigned long scope ) const { - if ( ! tables ) return 0; - if ( tables->scope < scope ) return 0; - if ( tables->scope > scope ) return tables->base.lookupTypeAtScope( id, scope ); - - TypeTable::const_iterator ret = tables->typeTable.find( id ); - return ret != tables->typeTable.end() ? ret->second : tables->base.lookupTypeAtScope( id, scope ); - } - - StructDecl *Indexer::lookupStructAtScope( const std::string &id, unsigned long scope ) const { - if ( ! tables ) return 0; - if ( tables->scope < scope ) return 0; - if ( tables->scope > scope ) return tables->base.lookupStructAtScope( id, scope ); - - StructTable::const_iterator ret = tables->structTable.find( id ); - return ret != tables->structTable.end() ? ret->second : tables->base.lookupStructAtScope( id, scope ); - } - - EnumDecl *Indexer::lookupEnumAtScope( const std::string &id, unsigned long scope ) const { - if ( ! tables ) return 0; - if ( tables->scope < scope ) return 0; - if ( tables->scope > scope ) return tables->base.lookupEnumAtScope( id, scope ); - - EnumTable::const_iterator ret = tables->enumTable.find( id ); - return ret != tables->enumTable.end() ? ret->second : tables->base.lookupEnumAtScope( id, scope ); - } - - UnionDecl *Indexer::lookupUnionAtScope( const std::string &id, unsigned long scope ) const { - if ( ! tables ) return 0; - if ( tables->scope < scope ) return 0; - if ( tables->scope > scope ) return tables->base.lookupUnionAtScope( id, scope ); - - UnionTable::const_iterator ret = tables->unionTable.find( id ); - return ret != tables->unionTable.end() ? ret->second : tables->base.lookupUnionAtScope( id, scope ); - } - - TraitDecl *Indexer::lookupTraitAtScope( const std::string &id, unsigned long scope ) const { - if ( ! tables ) return 0; - if ( tables->scope < scope ) return 0; - if ( tables->scope > scope ) return tables->base.lookupTraitAtScope( id, scope ); - - TraitTable::const_iterator ret = tables->traitTable.find( id ); - return ret != tables->traitTable.end() ? ret->second : tables->base.lookupTraitAtScope( id, scope ); + return atScope( 0 )->lookupEnum( id ); } @@ -487,45 +207,241 @@ } - bool addedIdConflicts( Indexer::IdData & existing, DeclarationWithType *added, BaseSyntaxNode * deleteStmt, Indexer::ConflictFunction handleConflicts ) { - // if we're giving the same name mangling to things of different types then there is something wrong + + bool Indexer::addedIdConflicts( + const Indexer::IdData & existing, DeclarationWithType *added, + Indexer::OnConflict handleConflicts, BaseSyntaxNode * deleteStmt ) { + // if we're giving the same name mangling to things of different types then there is + // something wrong assert( (isObject( added ) && isObject( existing.id ) ) || ( isFunction( added ) && isFunction( existing.id ) ) ); - if ( LinkageSpec::isOverridable( existing.id->get_linkage() ) ) { + if ( LinkageSpec::isOverridable( existing.id->linkage ) ) { // new definition shadows the autogenerated one, even at the same scope return false; - } else if ( LinkageSpec::isMangled( added->get_linkage() ) || ResolvExpr::typesCompatible( added->get_type(), existing.id->get_type(), Indexer() ) ) { + } else if ( LinkageSpec::isMangled( added->linkage ) + || ResolvExpr::typesCompatible( + added->get_type(), existing.id->get_type(), Indexer() ) ) { // it is a conflict if one declaration is deleted and the other is not if ( deleteStmt && ! existing.deleteStmt ) { - return handleConflicts( existing, "deletion of defined identifier " ); + if ( handleConflicts.mode == OnConflict::Error ) { + SemanticError( added, "deletion of defined identifier " ); + } + return true; } else if ( ! deleteStmt && existing.deleteStmt ) { - return handleConflicts( existing, "definition of deleted identifier " ); + if ( handleConflicts.mode == OnConflict::Error ) { + SemanticError( added, "definition of deleted identifier " ); + } + return true; } if ( isDefinition( added ) && isDefinition( existing.id ) ) { - if ( isFunction( added ) ) { - return handleConflicts( existing, "duplicate function definition for " ); + if ( handleConflicts.mode == OnConflict::Error ) { + SemanticError( added, + isFunction( added ) ? + "duplicate function definition for " : + "duplicate object definition for " ); + } + return true; + } // if + } else { + if ( handleConflicts.mode == OnConflict::Error ) { + SemanticError( added, "duplicate definition for " ); + } + return true; + } // if + + return true; + } + + bool Indexer::hasCompatibleCDecl( const std::string &id, const std::string &mangleName ) const { + if ( ! idTable ) return false; + + ++*stats().map_lookups; + auto decls = idTable->find( id ); + if ( decls == idTable->end() ) return false; + + for ( auto decl : *(decls->second) ) { + // skip other scopes (hidden by this decl) + if ( decl.second.scope != scope ) continue; + // check for C decl with compatible type (by mangleName) + if ( ! LinkageSpec::isMangled( decl.second.id->linkage ) && decl.first == mangleName ) { + return true; + } + } + + return false; + } + + bool Indexer::hasIncompatibleCDecl( + const std::string &id, const std::string &mangleName ) const { + if ( ! idTable ) return false; + + ++*stats().map_lookups; + auto decls = idTable->find( id ); + if ( decls == idTable->end() ) return false; + + for ( auto decl : *(decls->second) ) { + // skip other scopes (hidden by this decl) + if ( decl.second.scope != scope ) continue; + // check for C decl with incompatible type (by manglename) + if ( ! LinkageSpec::isMangled( decl.second.id->linkage ) && decl.first != mangleName ) { + return true; + } + } + + return false; + } + + /// gets the base type of the first parameter; decl must be a ctor/dtor/assignment function + std::string getOtypeKey( FunctionDecl* function ) { + auto& params = function->type->parameters; + assert( ! params.empty() ); + // use base type of pointer, so that qualifiers on the pointer type aren't considered. + Type* base = InitTweak::getPointerBase( params.front()->get_type() ); + assert( base ); + return Mangler::mangle( base ); + } + + /// gets the declaration for the function acting on a type specified by otype key, + /// nullptr if none such + FunctionDecl * getFunctionForOtype( DeclarationWithType * decl, const std::string& otypeKey ) { + FunctionDecl * func = dynamic_cast< FunctionDecl * >( decl ); + if ( ! func || otypeKey != getOtypeKey( func ) ) return nullptr; + return func; + } + + bool Indexer::removeSpecialOverrides( + Indexer::IdData& data, Indexer::MangleTable::Ptr& mangleTable ) { + // if a type contains user defined ctor/dtor/assign, then special rules trigger, which + // determinethe set of ctor/dtor/assign that can be used by the requester. In particular, + // if the user defines a default ctor, then the generated default ctor is unavailable, + // likewise for copy ctor and dtor. If the user defines any ctor/dtor, then no generated + // field ctors are available. If the user defines any ctor then the generated default ctor + // is unavailable (intrinsic default ctor must be overridden exactly). If the user defines + // anything that looks like a copy constructor, then the generated copy constructor is + // unavailable, and likewise for the assignment operator. + + // only relevant on function declarations + FunctionDecl * function = dynamic_cast< FunctionDecl * >( data.id ); + if ( ! function ) return true; + // only need to perform this check for constructors, destructors, and assignment functions + if ( ! CodeGen::isCtorDtorAssign( data.id->name ) ) return true; + + // set up information for this type + bool dataIsUserDefinedFunc = ! LinkageSpec::isOverridable( function->linkage ); + bool dataIsCopyFunc = InitTweak::isCopyFunction( function, function->name ); + std::string dataOtypeKey = getOtypeKey( function ); + + if ( dataIsUserDefinedFunc && dataIsCopyFunc ) { + // this is a user-defined copy function + // if this is the first such, delete/remove non-user-defined overloads as needed + std::vector< std::string > removed; + std::vector< MangleTable::value_type > deleted; + bool alreadyUserDefinedFunc = false; + + for ( const auto& entry : *mangleTable ) { + // skip decls that aren't functions or are for the wrong type + FunctionDecl * decl = getFunctionForOtype( entry.second.id, dataOtypeKey ); + if ( ! decl ) continue; + + bool isCopyFunc = InitTweak::isCopyFunction( decl, decl->name ); + if ( ! LinkageSpec::isOverridable( decl->linkage ) ) { + // matching user-defined function + if ( isCopyFunc ) { + // mutation already performed, return early + return true; + } else { + // note that non-copy deletions already performed + alreadyUserDefinedFunc = true; + } } else { - return handleConflicts( existing, "duplicate object definition for " ); - } // if - } // if - } else { - return handleConflicts( existing, "duplicate definition for " ); - } // if - + // non-user-defined function; mark for deletion/removal as appropriate + if ( isCopyFunc ) { + removed.push_back( entry.first ); + } else if ( ! alreadyUserDefinedFunc ) { + deleted.push_back( entry ); + } + } + } + + // perform removals from mangle table, and deletions if necessary + for ( const auto& key : removed ) { + ++*stats().map_mutations; + mangleTable = mangleTable->erase( key ); + } + if ( ! alreadyUserDefinedFunc ) for ( const auto& entry : deleted ) { + ++*stats().map_mutations; + mangleTable = mangleTable->set( entry.first, IdData{ entry.second, function } ); + } + } else if ( dataIsUserDefinedFunc ) { + // this is a user-defined non-copy function + // if this is the first user-defined function, delete non-user-defined overloads + std::vector< MangleTable::value_type > deleted; + + for ( const auto& entry : *mangleTable ) { + // skip decls that aren't functions or are for the wrong type + FunctionDecl * decl = getFunctionForOtype( entry.second.id, dataOtypeKey ); + if ( ! decl ) continue; + + // exit early if already a matching user-defined function; + // earlier function will have mutated table + if ( ! LinkageSpec::isOverridable( decl->linkage ) ) return true; + + // skip mutating intrinsic functions + if ( decl->linkage == LinkageSpec::Intrinsic ) continue; + + // user-defined non-copy functions do not override copy functions + if ( InitTweak::isCopyFunction( decl, decl->name ) ) continue; + + // this function to be deleted after mangleTable iteration is complete + deleted.push_back( entry ); + } + + // mark deletions to update mangle table + // this needs to be a separate loop because of iterator invalidation + for ( const auto& entry : deleted ) { + ++*stats().map_mutations; + mangleTable = mangleTable->set( entry.first, IdData{ entry.second, function } ); + } + } else if ( function->linkage != LinkageSpec::Intrinsic ) { + // this is an overridable generated function + // if there already exists a matching user-defined function, delete this appropriately + for ( const auto& entry : *mangleTable ) { + // skip decls that aren't functions or are for the wrong type + FunctionDecl * decl = getFunctionForOtype( entry.second.id, dataOtypeKey ); + if ( ! decl ) continue; + + // skip non-user-defined functions + if ( LinkageSpec::isOverridable( decl->linkage ) ) continue; + + if ( dataIsCopyFunc ) { + // remove current function if exists a user-defined copy function + // since the signatures for copy functions don't need to match exactly, using + // a delete statement is the wrong approach + if ( InitTweak::isCopyFunction( decl, decl->name ) ) return false; + } else { + // mark current function deleted by first user-defined function found + data.deleteStmt = decl; + return true; + } + } + } + + // nothing (more) to fix, return true return true; } - void Indexer::addId( DeclarationWithType *decl, ConflictFunction handleConflicts, Expression * baseExpr, BaseSyntaxNode * deleteStmt ) { - if ( decl->name == "" ) return; - debugPrint( "Adding Id " << decl->name << std::endl ); - makeWritable(); - + void Indexer::addId( + DeclarationWithType *decl, OnConflict handleConflicts, Expression * baseExpr, + BaseSyntaxNode * deleteStmt ) { + ++*stats().add_calls; const std::string &name = decl->name; + if ( name == "" ) return; + std::string mangleName; if ( LinkageSpec::isOverridable( decl->linkage ) ) { - // mangle the name without including the appropriate suffix, so overridable routines are placed into the - // same "bucket" as their user defined versions. + // mangle the name without including the appropriate suffix, so overridable routines + // are placed into the same "bucket" as their user defined versions. mangleName = Mangler::mangle( decl, false ); } else { @@ -533,38 +449,71 @@ } // if - // this ensures that no two declarations with the same unmangled name at the same scope both have C linkage - if ( ! LinkageSpec::isMangled( decl->linkage ) ) { - // NOTE this is broken in Richard's original code in such a way that it never triggers (it - // doesn't check decls that have the same manglename, and all C-linkage decls are defined to - // have their name as their manglename, hence the error can never trigger). - // The code here is closer to correct, but name mangling would have to be completely - // isomorphic to C type-compatibility, which it may not be. - if ( hasIncompatibleCDecl( name, mangleName, scope ) ) { + // this ensures that no two declarations with the same unmangled name at the same scope + // both have C linkage + if ( LinkageSpec::isMangled( decl->linkage ) ) { + // Check that a Cforall declaration doesn't override any C declaration + if ( hasCompatibleCDecl( name, mangleName ) ) { + SemanticError( decl, "Cforall declaration hides C function " ); + } + } else { + // NOTE: only correct if name mangling is completely isomorphic to C + // type-compatibility, which it may not be. + if ( hasIncompatibleCDecl( name, mangleName ) ) { SemanticError( decl, "conflicting overload of C function " ); } - } else { - // Check that a Cforall declaration doesn't override any C declaration - if ( hasCompatibleCDecl( name, mangleName, scope ) ) { - SemanticError( decl, "Cforall declaration hides C function " ); - } - } - - // Skip repeat declarations of the same identifier - IdData * existing = lookupIdAtScope( name, mangleName, scope ); - if ( existing && existing->id && addedIdConflicts( *existing, decl, deleteStmt, handleConflicts ) ) return; - - // add to indexer - tables->idTable[ name ][ mangleName ] = IdData{ decl, baseExpr, deleteStmt }; - ++tables->size; + } + + // ensure tables exist and add identifier + MangleTable::Ptr mangleTable; + if ( ! idTable ) { + idTable = IdTable::new_ptr(); + mangleTable = MangleTable::new_ptr(); + } else { + ++*stats().map_lookups; + auto decls = idTable->find( name ); + if ( decls == idTable->end() ) { + mangleTable = MangleTable::new_ptr(); + } else { + mangleTable = decls->second; + // skip in-scope repeat declarations of same identifier + ++*stats().map_lookups; + auto existing = mangleTable->find( mangleName ); + if ( existing != mangleTable->end() + && existing->second.scope == scope + && existing->second.id ) { + if ( addedIdConflicts( existing->second, decl, handleConflicts, deleteStmt ) ) { + if ( handleConflicts.mode == OnConflict::Delete ) { + // set delete expression for conflicting identifier + lazyInitScope(); + *stats().map_mutations += 2; + idTable = idTable->set( + name, + mangleTable->set( + mangleName, + IdData{ existing->second, handleConflicts.deleteStmt } ) ); + } + return; + } + } + } + } + + // add/overwrite with new identifier + lazyInitScope(); + IdData data{ decl, baseExpr, deleteStmt, scope }; + // Ensure that auto-generated ctor/dtor/assignment are deleted if necessary + if ( ! removeSpecialOverrides( data, mangleTable ) ) return; + *stats().map_mutations += 2; + idTable = idTable->set( name, mangleTable->set( mangleName, std::move(data) ) ); } void Indexer::addId( DeclarationWithType * decl, Expression * baseExpr ) { // default handling of conflicts is to raise an error - addId( decl, [decl](IdData &, const std::string & msg) { SemanticError( decl, msg ); return true; }, baseExpr, decl->isDeleted ? decl : nullptr ); + addId( decl, OnConflict::error(), baseExpr, decl->isDeleted ? decl : nullptr ); } void Indexer::addDeletedId( DeclarationWithType * decl, BaseSyntaxNode * deleteStmt ) { // default handling of conflicts is to raise an error - addId( decl, [decl](IdData &, const std::string & msg) { SemanticError( decl, msg ); return true; }, nullptr, deleteStmt ); + addId( decl, OnConflict::error(), nullptr, deleteStmt ); } @@ -581,25 +530,26 @@ } } - // does not need to be added to the table if both existing and added have a base that are the same + // does not need to be added to the table if both existing and added have a base that are + // the same return true; } void Indexer::addType( NamedTypeDecl *decl ) { - debugPrint( "Adding type " << decl->name << std::endl ); - makeWritable(); - + ++*stats().add_calls; const std::string &id = decl->name; - TypeTable::iterator existing = tables->typeTable.find( id ); - if ( existing == tables->typeTable.end() ) { - NamedTypeDecl *parent = tables->base.lookupTypeAtScope( id, scope ); - if ( ! parent || ! addedTypeConflicts( parent, decl ) ) { - tables->typeTable.insert( existing, std::make_pair( id, decl ) ); - ++tables->size; - } - } else { - if ( ! addedTypeConflicts( existing->second, decl ) ) { - existing->second = decl; - } - } + + if ( ! typeTable ) { + typeTable = TypeTable::new_ptr(); + } else { + ++*stats().map_lookups; + auto existing = typeTable->find( id ); + if ( existing != typeTable->end() + && existing->second.scope == scope + && addedTypeConflicts( existing->second.decl, decl ) ) return; + } + + lazyInitScope(); + ++*stats().map_mutations; + typeTable = typeTable->set( id, Scoped{ decl, scope } ); } @@ -614,90 +564,89 @@ void Indexer::addStruct( const std::string &id ) { - debugPrint( "Adding fwd decl for struct " << id << std::endl ); addStruct( new StructDecl( id ) ); } void Indexer::addStruct( StructDecl *decl ) { - debugPrint( "Adding struct " << decl->name << std::endl ); - makeWritable(); - + ++*stats().add_calls; const std::string &id = decl->name; - StructTable::iterator existing = tables->structTable.find( id ); - if ( existing == tables->structTable.end() ) { - StructDecl *parent = tables->base.lookupStructAtScope( id, scope ); - if ( ! parent || ! addedDeclConflicts( parent, decl ) ) { - tables->structTable.insert( existing, std::make_pair( id, decl ) ); - ++tables->size; - } - } else { - if ( ! addedDeclConflicts( existing->second, decl ) ) { - existing->second = decl; - } - } + + if ( ! structTable ) { + structTable = StructTable::new_ptr(); + } else { + ++*stats().map_lookups; + auto existing = structTable->find( id ); + if ( existing != structTable->end() + && existing->second.scope == scope + && addedDeclConflicts( existing->second.decl, decl ) ) return; + } + + lazyInitScope(); + ++*stats().map_mutations; + structTable = structTable->set( id, Scoped{ decl, scope } ); } void Indexer::addEnum( EnumDecl *decl ) { - debugPrint( "Adding enum " << decl->name << std::endl ); - makeWritable(); - + ++*stats().add_calls; const std::string &id = decl->name; - EnumTable::iterator existing = tables->enumTable.find( id ); - if ( existing == tables->enumTable.end() ) { - EnumDecl *parent = tables->base.lookupEnumAtScope( id, scope ); - if ( ! parent || ! addedDeclConflicts( parent, decl ) ) { - tables->enumTable.insert( existing, std::make_pair( id, decl ) ); - ++tables->size; - } - } else { - if ( ! addedDeclConflicts( existing->second, decl ) ) { - existing->second = decl; - } - } + + if ( ! enumTable ) { + enumTable = EnumTable::new_ptr(); + } else { + ++*stats().map_lookups; + auto existing = enumTable->find( id ); + if ( existing != enumTable->end() + && existing->second.scope == scope + && addedDeclConflicts( existing->second.decl, decl ) ) return; + } + + lazyInitScope(); + ++*stats().map_mutations; + enumTable = enumTable->set( id, Scoped{ decl, scope } ); } void Indexer::addUnion( const std::string &id ) { - debugPrint( "Adding fwd decl for union " << id << std::endl ); addUnion( new UnionDecl( id ) ); } void Indexer::addUnion( UnionDecl *decl ) { - debugPrint( "Adding union " << decl->name << std::endl ); - makeWritable(); - + ++*stats().add_calls; const std::string &id = decl->name; - UnionTable::iterator existing = tables->unionTable.find( id ); - if ( existing == tables->unionTable.end() ) { - UnionDecl *parent = tables->base.lookupUnionAtScope( id, scope ); - if ( ! parent || ! addedDeclConflicts( parent, decl ) ) { - tables->unionTable.insert( existing, std::make_pair( id, decl ) ); - ++tables->size; - } - } else { - if ( ! addedDeclConflicts( existing->second, decl ) ) { - existing->second = decl; - } - } + + if ( ! unionTable ) { + unionTable = UnionTable::new_ptr(); + } else { + ++*stats().map_lookups; + auto existing = unionTable->find( id ); + if ( existing != unionTable->end() + && existing->second.scope == scope + && addedDeclConflicts( existing->second.decl, decl ) ) return; + } + + lazyInitScope(); + ++*stats().map_mutations; + unionTable = unionTable->set( id, Scoped{ decl, scope } ); } void Indexer::addTrait( TraitDecl *decl ) { - debugPrint( "Adding trait " << decl->name << std::endl ); - makeWritable(); - + ++*stats().add_calls; const std::string &id = decl->name; - TraitTable::iterator existing = tables->traitTable.find( id ); - if ( existing == tables->traitTable.end() ) { - TraitDecl *parent = tables->base.lookupTraitAtScope( id, scope ); - if ( ! parent || ! addedDeclConflicts( parent, decl ) ) { - tables->traitTable.insert( existing, std::make_pair( id, decl ) ); - ++tables->size; - } - } else { - if ( ! addedDeclConflicts( existing->second, decl ) ) { - existing->second = decl; - } - } - } - - void Indexer::addMembers( AggregateDecl * aggr, Expression * expr, ConflictFunction handleConflicts ) { + + if ( ! traitTable ) { + traitTable = TraitTable::new_ptr(); + } else { + ++*stats().map_lookups; + auto existing = traitTable->find( id ); + if ( existing != traitTable->end() + && existing->second.scope == scope + && addedDeclConflicts( existing->second.decl, decl ) ) return; + } + + lazyInitScope(); + ++*stats().map_mutations; + traitTable = traitTable->set( id, Scoped{ decl, scope } ); + } + + void Indexer::addMembers( AggregateDecl * aggr, Expression * expr, + OnConflict handleConflicts ) { for ( Declaration * decl : aggr->members ) { if ( DeclarationWithType * dwt = dynamic_cast< DeclarationWithType * >( decl ) ) { @@ -705,5 +654,5 @@ if ( dwt->name == "" ) { Type * t = dwt->get_type()->stripReferences(); - if ( dynamic_cast< StructInstType * >( t ) || dynamic_cast< UnionInstType * >( t ) ) { + if ( dynamic_cast( t ) || dynamic_cast( t ) ) { Expression * base = expr->clone(); ResolvExpr::Cost cost = ResolvExpr::Cost::zero; // xxx - carry this cost into the indexer as a base cost? @@ -722,9 +671,5 @@ assertf( aggr, "WithStmt expr has non-aggregate type: %s", toString( expr->result ).c_str() ); - addMembers( aggr, expr, [withStmt](IdData & existing, const std::string &) { - // on conflict, delete the identifier - existing.deleteStmt = withStmt; - return true; - }); + addMembers( aggr, expr, OnConflict::deleteWith( withStmt ) ); } } @@ -748,64 +693,4 @@ addIds( ftype->returnVals ); addIds( ftype->parameters ); - } - - void Indexer::enterScope() { - ++scope; - - if ( doDebug ) { - std::cerr << "--- Entering scope " << scope << std::endl; - } - } - - void Indexer::leaveScope() { - using std::cerr; - - assert( scope > 0 && "cannot leave initial scope" ); - if ( doDebug ) { - cerr << "--- Leaving scope " << scope << " containing" << std::endl; - } - --scope; - - while ( tables && tables->scope > scope ) { - if ( doDebug ) { - dump( tables->idTable, cerr ); - dump( tables->typeTable, cerr ); - dump( tables->structTable, cerr ); - dump( tables->enumTable, cerr ); - dump( tables->unionTable, cerr ); - dump( tables->traitTable, cerr ); - } - - // swap tables for base table until we find one at an appropriate scope - Indexer::Impl *base = newRef( tables->base.tables ); - deleteRef( tables ); - tables = base; - } - } - - void Indexer::print( std::ostream &os, int indent ) const { - using std::cerr; - - if ( tables ) { - os << "--- scope " << tables->scope << " ---" << std::endl; - - os << "===idTable===" << std::endl; - dump( tables->idTable, os ); - os << "===typeTable===" << std::endl; - dump( tables->typeTable, os ); - os << "===structTable===" << std::endl; - dump( tables->structTable, os ); - os << "===enumTable===" << std::endl; - dump( tables->enumTable, os ); - os << "===unionTable===" << std::endl; - dump( tables->unionTable, os ); - os << "===contextTable===" << std::endl; - dump( tables->traitTable, os ); - - tables->base.print( os, indent ); - } else { - os << "--- end ---" << std::endl; - } - } Index: src/SymTab/Indexer.h =================================================================== --- src/SymTab/Indexer.h (revision 90b9e4b6a9b073a0248ee68f44eabdfbf4a4295b) +++ src/SymTab/Indexer.h (revision 9399057263e3e87e8eb54c6a89f9bc4827990ff6) @@ -9,36 +9,31 @@ // Author : Richard C. Bilson // Created On : Sun May 17 21:38:55 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Thu Aug 17 16:09:12 2017 -// Update Count : 8 +// Last Modified By : Aaron B. Moss +// Last Modified On : Fri Mar 8 13:55:00 2019 +// Update Count : 9 // #pragma once -#include // for ostream -#include // for list -#include // for string -#include // for function +#include // for function +#include // for list +#include // for shared_ptr, enable_shared_from_this +#include // for string -#include "SynTree/Visitor.h" // for Visitor -#include "SynTree/SynTree.h" // for AST nodes +#include "Common/PersistentMap.h" // for PersistentMap +#include "SynTree/SynTree.h" // for AST nodes namespace ResolvExpr { -class Cost; + class Cost; } namespace SymTab { - class Indexer { - public: + class Indexer : public std::enable_shared_from_this { + public: explicit Indexer(); + virtual ~Indexer(); - Indexer( const Indexer &that ); - Indexer( Indexer &&that ); - virtual ~Indexer(); - Indexer& operator= ( const Indexer &that ); - Indexer& operator= ( Indexer &&that ); - - // when using an indexer manually (e.g., within a mutator traversal), it is necessary to tell the indexer - // explicitly when scopes begin and end + // when using an indexer manually (e.g., within a mutator traversal), it is necessary to + // tell the indexer explicitly when scopes begin and end void enterScope(); void leaveScope(); @@ -50,8 +45,15 @@ /// non-null if this declaration is deleted BaseSyntaxNode * deleteStmt = nullptr; + /// scope of identifier + unsigned long scope = 0; // NOTE: shouldn't need either of these constructors, but gcc-4 does not properly support initializer lists with default members. IdData() = default; - IdData( DeclarationWithType * id, Expression * baseExpr, BaseSyntaxNode * deleteStmt ) : id( id ), baseExpr( baseExpr ), deleteStmt( deleteStmt ) {} + IdData( + DeclarationWithType * id, Expression * baseExpr, BaseSyntaxNode * deleteStmt, + unsigned long scope ) + : id( id ), baseExpr( baseExpr ), deleteStmt( deleteStmt ), scope( scope ) {} + IdData( const IdData& o, BaseSyntaxNode * deleteStmt ) + : id( o.id ), baseExpr( o.baseExpr ), deleteStmt( deleteStmt ), scope( o.scope ) {} Expression * combine( ResolvExpr::Cost & cost ) const; @@ -80,22 +82,4 @@ EnumDecl *globalLookupEnum( const std::string &id ) const; - void print( std::ostream &os, int indent = 0 ) const; - - /// looks up a specific mangled ID at the given scope - IdData * lookupIdAtScope( const std::string &id, const std::string &mangleName, unsigned long scope ); - const IdData * lookupIdAtScope( const std::string &id, const std::string &mangleName, unsigned long scope ) const; - /// returns true if there exists a declaration with C linkage and the given name with a different mangled name - bool hasIncompatibleCDecl( const std::string &id, const std::string &mangleName, unsigned long scope ) const; - /// returns true if there exists a declaration with C linkage and the given name with the same mangled name - bool hasCompatibleCDecl( const std::string &id, const std::string &mangleName, unsigned long scope ) const; - // equivalents to lookup functions that only look at tables at scope `scope` (which should be >= tables->scope) - NamedTypeDecl *lookupTypeAtScope( const std::string &id, unsigned long scope ) const; - StructDecl *lookupStructAtScope( const std::string &id, unsigned long scope ) const; - EnumDecl *lookupEnumAtScope( const std::string &id, unsigned long scope ) const; - UnionDecl *lookupUnionAtScope( const std::string &id, unsigned long scope ) const; - TraitDecl *lookupTraitAtScope( const std::string &id, unsigned long scope ) const; - - typedef std::function ConflictFunction; - void addId( DeclarationWithType * decl, Expression * baseExpr = nullptr ); void addDeletedId( DeclarationWithType * decl, BaseSyntaxNode * deleteStmt ); @@ -112,7 +96,4 @@ void addWith( std::list< Expression * > & withExprs, BaseSyntaxNode * withStmt ); - /// adds all of the members of the Aggregate (addWith helper) - void addMembers( AggregateDecl * aggr, Expression * expr, ConflictFunction ); - /// convenience function for adding a list of Ids to the indexer void addIds( const std::list< DeclarationWithType * > & decls ); @@ -124,26 +105,80 @@ void addFunctionType( FunctionType * ftype ); - bool doDebug = false; ///< Display debugging trace? private: - struct Impl; + /// Wraps a Decl* with a scope + template + struct Scoped { + Decl* decl; ///< declaration + unsigned long scope; ///< scope of this declaration - Impl *tables; ///< Copy-on-write instance of table data structure - unsigned long scope; ///< Scope index of this pointer + Scoped(Decl* d, unsigned long s) : decl(d), scope(s) {} + }; - /// Takes a new ref to a table (returns null if null) - static Impl *newRef( Impl *toClone ); - /// Clears a ref to a table (does nothing if null) - static void deleteRef( Impl *toFree ); + using Ptr = std::shared_ptr; - // Removes matching autogenerated constructors and destructors - // so that they will not be selected - // void removeSpecialOverrides( FunctionDecl *decl ); - void removeSpecialOverrides( const std::string &id, std::list< IdData > & out ) const; + using MangleTable = PersistentMap< std::string, IdData >; + using IdTable = PersistentMap< std::string, MangleTable::Ptr >; + using TypeTable = PersistentMap< std::string, Scoped >; + using StructTable = PersistentMap< std::string, Scoped >; + using EnumTable = PersistentMap< std::string, Scoped >; + using UnionTable = PersistentMap< std::string, Scoped >; + using TraitTable = PersistentMap< std::string, Scoped >; - /// Ensures that tables variable is writable (i.e. allocated, uniquely owned by this Indexer, and at the current scope) - void makeWritable(); + IdTable::Ptr idTable; ///< identifier namespace + TypeTable::Ptr typeTable; ///< type namespace + StructTable::Ptr structTable; ///< struct namespace + EnumTable::Ptr enumTable; ///< enum namespace + UnionTable::Ptr unionTable; ///< union namespace + TraitTable::Ptr traitTable; ///< trait namespace + + Ptr prevScope; ///< reference to indexer for parent scope + unsigned long scope; ///< Scope index of this indexer + unsigned long repScope; ///< Scope index of currently represented scope + + /// Ensures that a proper backtracking scope exists before a mutation + void lazyInitScope(); + + /// Gets the indexer at the given scope + const Indexer* atScope( unsigned long scope ) const; + + /// Removes matching autogenerated constructors and destructors so that they will not be + /// selected. If returns false, passed decl should not be added. + bool removeSpecialOverrides( IdData& decl, MangleTable::Ptr& mangleTable ); + + /// Options for handling identifier conflicts + struct OnConflict { + enum { + Error, ///< Throw a semantic error + Delete ///< Delete the earlier version with the delete statement + } mode; + BaseSyntaxNode * deleteStmt; ///< Statement that deletes this expression + + private: + OnConflict() : mode(Error), deleteStmt(nullptr) {} + OnConflict( BaseSyntaxNode * d ) : mode(Delete), deleteStmt(d) {} + public: + OnConflict( const OnConflict& ) = default; + + static OnConflict error() { return {}; } + static OnConflict deleteWith( BaseSyntaxNode * d ) { return { d }; } + }; + + /// true if the existing identifier conflicts with the added identifier + bool addedIdConflicts( + const IdData& existing, DeclarationWithType * added, OnConflict handleConflicts, + BaseSyntaxNode * deleteStmt ); /// common code for addId, addDeletedId, etc. - void addId( DeclarationWithType * decl, ConflictFunction, Expression * baseExpr = nullptr, BaseSyntaxNode * deleteStmt = nullptr ); + void addId( + DeclarationWithType * decl, OnConflict handleConflicts, + Expression * baseExpr = nullptr, BaseSyntaxNode * deleteStmt = nullptr ); + + /// adds all of the members of the Aggregate (addWith helper) + void addMembers( AggregateDecl * aggr, Expression * expr, OnConflict handleConflicts ); + + /// returns true if there exists a declaration with C linkage and the given name with the same mangled name + bool hasCompatibleCDecl( const std::string &id, const std::string &mangleName ) const; + /// returns true if there exists a declaration with C linkage and the given name with a different mangled name + bool hasIncompatibleCDecl( const std::string &id, const std::string &mangleName ) const; }; } // namespace SymTab Index: src/SynTree/BaseSyntaxNode.h =================================================================== --- src/SynTree/BaseSyntaxNode.h (revision 90b9e4b6a9b073a0248ee68f44eabdfbf4a4295b) +++ src/SynTree/BaseSyntaxNode.h (revision 9399057263e3e87e8eb54c6a89f9bc4827990ff6) @@ -18,4 +18,6 @@ #include "Common/CodeLocation.h" #include "Common/Indenter.h" +#include "Common/Stats.h" + class Visitor; class Mutator; @@ -23,5 +25,10 @@ class BaseSyntaxNode { public: + static Stats::Counters::SimpleCounter* new_nodes; + CodeLocation location; + + BaseSyntaxNode() { ++*new_nodes; } + BaseSyntaxNode( const BaseSyntaxNode& ) { ++*new_nodes; } virtual ~BaseSyntaxNode() {} Index: src/main.cc =================================================================== --- src/main.cc (revision 90b9e4b6a9b073a0248ee68f44eabdfbf4a4295b) +++ src/main.cc (revision 9399057263e3e87e8eb54c6a89f9bc4827990ff6) @@ -65,13 +65,21 @@ using namespace std; - void NewPass(const char * const name) { Stats::Heap::newPass(name); using namespace Stats::Counters; - static auto pass_visitor_group = build("Pass Visitor"); - auto pass = build(name, pass_visitor_group); - pass_visitor_stats.depth = 0; - pass_visitor_stats.avg = build>("Average Depth", pass); - pass_visitor_stats.max = build>("Max Depth", pass); + + { + static auto group = build("Pass Visitor"); + auto pass = build(name, group); + pass_visitor_stats.depth = 0; + pass_visitor_stats.avg = build>("Average Depth", pass); + pass_visitor_stats.max = build>("Max Depth", pass); + } + + { + static auto group = build("Syntax Node"); + auto pass = build(name, group); + BaseSyntaxNode::new_nodes = build("Allocs", pass); + } } Index: tests/raii/.expect/memberCtors-ERR1.txt =================================================================== --- tests/raii/.expect/memberCtors-ERR1.txt (revision 90b9e4b6a9b073a0248ee68f44eabdfbf4a4295b) +++ tests/raii/.expect/memberCtors-ERR1.txt (revision 9399057263e3e87e8eb54c6a89f9bc4827990ff6) @@ -1,1 +1,1 @@ -raii/memberCtors.cfa:71:1 error: in void ?{}(B &b), field a2 used before being constructed +error: in void ?{}(B &b), field a2 used before being constructed Index: tests/warnings/.expect/self-assignment.txt =================================================================== --- tests/warnings/.expect/self-assignment.txt (revision 90b9e4b6a9b073a0248ee68f44eabdfbf4a4295b) +++ tests/warnings/.expect/self-assignment.txt (revision 9399057263e3e87e8eb54c6a89f9bc4827990ff6) @@ -1,11 +1,11 @@ -warnings/self-assignment.cfa:29:1 warning: self assignment of expression: Generated Cast of: +warning: self assignment of expression: Generated Cast of: Variable Expression: j: signed int ... to: reference to signed int -warnings/self-assignment.cfa:30:1 warning: self assignment of expression: Generated Cast of: +warning: self assignment of expression: Generated Cast of: Variable Expression: s: instance of struct S with body 1 ... to: reference to instance of struct S with body 1 -warnings/self-assignment.cfa:31:1 warning: self assignment of expression: Generated Cast of: +warning: self assignment of expression: Generated Cast of: Member Expression, with field: i: signed int @@ -14,5 +14,5 @@ ... to: reference to signed int -warnings/self-assignment.cfa:32:1 warning: self assignment of expression: Generated Cast of: +warning: self assignment of expression: Generated Cast of: Member Expression, with field: i: signed int