Index: c/SymTab/AggregateTable.h =================================================================== --- src/SymTab/AggregateTable.h (revision e8032b011e6d5bdc74f9cb82d480387e1e6ecee2) +++ (revision ) @@ -1,53 +1,0 @@ -// -// 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. -// -// AggregateTable.h -- -// -// Author : Richard C. Bilson -// Created On : Sun May 17 16:17:26 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Wed Mar 2 17:31:00 2016 -// Update Count : 5 -// - -#ifndef AGGREGATETABLE_H -#define AGGREGATETABLE_H - -#include -#include -#include -#include - -#include "StackTable.h" -#include "SynTree/Declaration.h" - -namespace SymTab { - template< class AggregateDeclClass > - class AggregateTableConflictFunction : public std::binary_function< AggregateDeclClass *, AggregateDeclClass *, AggregateDeclClass *> { - public: - AggregateDeclClass *operator()( AggregateDeclClass *existing, AggregateDeclClass *added ) { - if ( existing->get_members().empty() ) { - return added; - } else if ( ! added->get_members().empty() ) { - throw SemanticError( "redeclaration of ", added ); - } // if - return existing; - } - }; - - typedef StackTable< StructDecl, AggregateTableConflictFunction< StructDecl > > StructTable; - typedef StackTable< EnumDecl, AggregateTableConflictFunction< EnumDecl > > EnumTable; - typedef StackTable< UnionDecl, AggregateTableConflictFunction< UnionDecl > > UnionTable; - typedef StackTable< TraitDecl, AggregateTableConflictFunction< TraitDecl > > TraitTable; -} // namespace SymTab - -#endif // AGGREGATETABLE_H - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: src/SymTab/Indexer.cc =================================================================== --- src/SymTab/Indexer.cc (revision e8032b011e6d5bdc74f9cb82d480387e1e6ecee2) +++ src/SymTab/Indexer.cc (revision 52c2a72881ce34e949bfca571ffcb391d884f339) @@ -16,7 +16,10 @@ #include "Indexer.h" +#include +#include +#include +#include + #include "IdTable.h" -#include "AggregateTable.h" -#include "TypeTable.h" #include "SynTree/Declaration.h" @@ -26,6 +29,4 @@ #include "SynTree/Statement.h" -#include -#include #include "Common/utility.h" @@ -40,10 +41,24 @@ } + 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; + + 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() : refCount(1), size(0), base(), + Impl( unsigned long _scope ) : refCount(1), scope( _scope ), size( 0 ), base(), idTable(), typeTable(), structTable(), enumTable(), unionTable(), traitTable() {} - Impl( const Indexer &_base ) : refCount(1), size(0), base( _base ), + 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 @@ -75,17 +90,17 @@ void Indexer::makeWritable() { if ( ! tables ) { - tables = new Indexer::Impl; - } else if ( tables->refCount > 1 ) { - // tables->base inherits the ref that used to belong to this indexer - // this is basically equivalent to std::move( *this ) as the argument - tables = new Indexer::Impl( Indexer( tables, doDebug ) ); - } - } - - Indexer::Indexer( bool _doDebug ) : tables(0), doDebug( _doDebug ) {} - - Indexer::Indexer( const Indexer &that ) : tables( newRef( that.tables ) ), doDebug( that.doDebug ) {} - - Indexer::Indexer( Indexer &&that ) : tables( that.tables ), doDebug( that.doDebug ) { + // 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( bool _doDebug ) : tables( 0 ), scope( 0 ), doDebug( _doDebug ) {} + + Indexer::Indexer( const Indexer &that ) : tables( newRef( that.tables ) ), scope( that.scope ), doDebug( that.doDebug ) {} + + Indexer::Indexer( Indexer &&that ) : tables( that.tables ), scope( that.scope ), doDebug( that.doDebug ) { that.tables = 0; } @@ -99,4 +114,5 @@ tables = newRef( that.tables ); + scope = that.scope; doDebug = that.doDebug; @@ -108,4 +124,5 @@ tables = that.tables; + scope = that.scope; doDebug = that.doDebug; @@ -421,6 +438,6 @@ if ( ! tables ) return 0; - NamedTypeDecl *ret = tables->typeTable.lookup( id ); - return ret ? ret : tables->base.lookupType( id ); + TypeTable::const_iterator ret = tables->typeTable.find( id ); + return ret != tables->typeTable.end() ? ret->second : tables->base.lookupType( id ); } @@ -428,6 +445,6 @@ if ( ! tables ) return 0; - StructDecl *ret = tables->structTable.lookup( id ); - return ret ? ret : tables->base.lookupStruct( id ); + StructTable::const_iterator ret = tables->structTable.find( id ); + return ret != tables->structTable.end() ? ret->second : tables->base.lookupStruct( id ); } @@ -435,6 +452,6 @@ if ( ! tables ) return 0; - EnumDecl *ret = tables->enumTable.lookup( id ); - return ret ? ret : tables->base.lookupEnum( id ); + EnumTable::const_iterator ret = tables->enumTable.find( id ); + return ret != tables->enumTable.end() ? ret->second : tables->base.lookupEnum( id ); } @@ -442,6 +459,6 @@ if ( ! tables ) return 0; - UnionDecl *ret = tables->unionTable.lookup( id ); - return ret ? ret : tables->base.lookupUnion( id ); + UnionTable::const_iterator ret = tables->unionTable.find( id ); + return ret != tables->unionTable.end() ? ret->second : tables->base.lookupUnion( id ); } @@ -449,6 +466,46 @@ if ( ! tables ) return 0; - TraitDecl *ret = tables->traitTable.lookup( id ); - return ret ? ret : tables->base.lookupTrait( id ); + TraitTable::const_iterator ret = tables->traitTable.find( id ); + return ret != tables->traitTable.end() ? ret->second : tables->base.lookupTrait( id ); + } + + NamedTypeDecl *Indexer::lookupTypeAtScope( const std::string &id, unsigned long scope ) const { + if ( ! tables ) return 0; + if ( tables->scope < scope ) return 0; + + 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; + + 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; + + 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; + + 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; + + TraitTable::const_iterator ret = tables->traitTable.find( id ); + return ret != tables->traitTable.end() ? ret->second : tables->base.lookupTraitAtScope( id, scope ); } @@ -458,82 +515,152 @@ ++tables->size; } + + bool addedTypeConflicts( NamedTypeDecl *existing, NamedTypeDecl *added ) { + if ( existing->get_base() == 0 ) { + return false; + } else if ( added->get_base() == 0 ) { + return true; + } else { + throw SemanticError( "redeclaration of ", added ); + } + } void Indexer::addType( NamedTypeDecl *decl ) { makeWritable(); - tables->typeTable.add( decl ); - ++tables->size; + + const std::string &id = decl->get_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; + } + } + } + + bool addedDeclConflicts( AggregateDecl *existing, AggregateDecl *added ) { + if ( existing->get_members().empty() ) { + return false; + } else if ( ! added->get_members().empty() ) { + throw SemanticError( "redeclaration of ", added ); + } // if + return true; } void Indexer::addStruct( const std::string &id ) { - makeWritable(); - tables->structTable.add( id ); - ++tables->size; + addStruct( new StructDecl( id ) ); } void Indexer::addStruct( StructDecl *decl ) { makeWritable(); - tables->structTable.add( decl ); - ++tables->size; + + const std::string &id = decl->get_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; + } + } } void Indexer::addEnum( EnumDecl *decl ) { makeWritable(); - tables->enumTable.add( decl ); - ++tables->size; + + const std::string &id = decl->get_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; + } + } } void Indexer::addUnion( const std::string &id ) { - makeWritable(); - tables->unionTable.add( id ); - ++tables->size; + addUnion( new UnionDecl( id ) ); } void Indexer::addUnion( UnionDecl *decl ) { makeWritable(); - tables->unionTable.add( decl ); - ++tables->size; + + const std::string &id = decl->get_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; + } + } } void Indexer::addTrait( TraitDecl *decl ) { makeWritable(); - tables->traitTable.add( decl ); - ++tables->size; + + const std::string &id = decl->get_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::enterScope() { - makeWritable(); + ++scope; if ( doDebug ) { - std::cout << "--- Entering scope" << std::endl; - } - - tables->idTable.enterScope(); - tables->typeTable.enterScope(); - tables->structTable.enterScope(); - tables->enumTable.enterScope(); - tables->unionTable.enterScope(); - tables->traitTable.enterScope(); + std::cout << "--- Entering scope " << scope << std::endl; + } } void Indexer::leaveScope() { using std::cout; - - makeWritable(); - - if ( doDebug ) { - cout << "--- Leaving scope containing" << std::endl; - tables->idTable.dump( cout ); - tables->typeTable.dump( cout ); - tables->structTable.dump( cout ); - tables->enumTable.dump( cout ); - tables->unionTable.dump( cout ); - tables->traitTable.dump( cout ); - } - tables->idTable.leaveScope(); - tables->typeTable.leaveScope(); - tables->structTable.leaveScope(); - tables->enumTable.leaveScope(); - tables->unionTable.leaveScope(); - tables->traitTable.leaveScope(); + + assert( scope > 0 && "cannot leave initial scope" ); + --scope; + + while ( tables && tables->scope > scope ) { + if ( doDebug ) { + cout << "--- Leaving scope " << tables->scope << " containing" << std::endl; + tables->idTable.dump( cout ); + dump( tables->typeTable, cout ); + dump( tables->structTable, cout ); + dump( tables->enumTable, cout ); + dump( tables->unionTable, cout ); + dump( tables->traitTable, cout ); + } + + // swap tables for base table until we find one at an appropriate scope + Indexer::Impl *base = newRef( tables->base.tables ); + deleteRef( tables ); + tables = base; + } } @@ -544,13 +671,13 @@ if ( tables ) tables->idTable.dump( os ); cerr << "===typeTable===" << std::endl; - if ( tables ) tables->typeTable.dump( os ); + if ( tables ) dump( tables->typeTable, os ); cerr << "===structTable===" << std::endl; - if ( tables ) tables->structTable.dump( os ); + if ( tables ) dump( tables->structTable, os ); cerr << "===enumTable===" << std::endl; - if ( tables ) tables->enumTable.dump( os ); + if ( tables ) dump( tables->enumTable, os ); cerr << "===unionTable===" << std::endl; - if ( tables ) tables->unionTable.dump( os ); + if ( tables ) dump( tables->unionTable, os ); cerr << "===contextTable===" << std::endl; - if ( tables ) tables->traitTable.dump( os ); + if ( tables ) dump( tables->traitTable, os ); } } // namespace SymTab Index: src/SymTab/Indexer.h =================================================================== --- src/SymTab/Indexer.h (revision e8032b011e6d5bdc74f9cb82d480387e1e6ecee2) +++ src/SymTab/Indexer.h (revision 52c2a72881ce34e949bfca571ffcb391d884f339) @@ -90,4 +90,11 @@ void print( std::ostream &os, int indent = 0 ) const; private: + // 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; + void addId( DeclarationWithType *decl ); void addType( NamedTypeDecl *decl ); @@ -100,8 +107,7 @@ struct Impl; - Impl *tables; ///< Copy-on-write instance of table data structure - bool doDebug; ///< Display debugging trace? - - Indexer( Impl *_tables, bool _doDebug ) : tables( _tables ), doDebug( _doDebug ) {} + Impl *tables; ///< Copy-on-write instance of table data structure + unsigned long scope; ///< Scope index of this pointer + bool doDebug; ///< Display debugging trace? /// Takes a new ref to a table (returns null if null) @@ -110,5 +116,5 @@ static void deleteRef( Impl *toFree ); - /// Ensures that tables variable is writable (i.e. allocated and uniquely owned by this Indexer) + /// Ensures that tables variable is writable (i.e. allocated, uniquely owned by this Indexer, and at the current scope) void makeWritable(); }; Index: c/SymTab/StackTable.cc =================================================================== --- src/SymTab/StackTable.cc (revision e8032b011e6d5bdc74f9cb82d480387e1e6ecee2) +++ (revision ) @@ -1,84 +1,0 @@ -// -// 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. -// -// StackTable.cc -- -// -// Author : Richard C. Bilson -// Created On : Sun May 17 21:45:15 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Tue May 19 16:51:53 2015 -// Update Count : 3 -// - -#include - -#include "StackTable.h" - -namespace SymTab { - template< typename Element, typename ConflictFunction > - StackTable< Element, ConflictFunction >::StackTable() : scopeLevel( 0 ) { - } - - template< typename Element, typename ConflictFunction > - void StackTable< Element, ConflictFunction >::enterScope() { - scopeLevel++; - } - - template< typename Element, typename ConflictFunction > - void StackTable< Element, ConflictFunction >::leaveScope() { - for ( typename TableType::iterator it = table.begin(); it != table.end(); ++it ) { - std::stack< Entry >& entry = it->second; - if ( ! entry.empty() && entry.top().second == scopeLevel ) { - entry.pop(); - } // if - } // for - scopeLevel--; - assert( scopeLevel >= 0 ); - } - - template< typename Element, typename ConflictFunction > - void StackTable< Element, ConflictFunction >::add( Element *type ) { - std::stack< Entry >& entry = table[ type->get_name() ]; - if ( ! entry.empty() && entry.top().second == scopeLevel ) { - entry.top().first = conflictFunction( entry.top().first, type ); - } else { - entry.push( Entry( type, scopeLevel ) ); - } // if - } - - template< typename Element, typename ConflictFunction > - void StackTable< Element, ConflictFunction >::add( std::string fwdDeclName ) { - add( new Element( fwdDeclName ) ); - } - - template< typename Element, typename ConflictFunction > - Element *StackTable< Element, ConflictFunction >::lookup( std::string id ) const { - typename TableType::const_iterator it = table.find( id ); - if ( it == table.end() ) { - return 0; - } else if ( ! it->second.empty() ) { - return it->second.top().first; - } else { - return 0; - } // if - } - - template< typename Element, typename ConflictFunction > - void StackTable< Element, ConflictFunction >::dump( std::ostream &os ) const { - for ( typename TableType::const_iterator it = table.begin(); it != table.end(); ++it ) { - const std::stack< Entry >& entry = it->second; - if ( ! entry.empty() && entry.top().second == scopeLevel ) { - os << it->first << std::endl; - } // if - } // for - } -} // namespace SymTab - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: c/SymTab/StackTable.h =================================================================== --- src/SymTab/StackTable.h (revision e8032b011e6d5bdc74f9cb82d480387e1e6ecee2) +++ (revision ) @@ -1,55 +1,0 @@ -// -// 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. -// -// StackTable.h -- -// -// Author : Richard C. Bilson -// Created On : Sun May 17 21:47:10 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Tue May 19 16:50:36 2015 -// Update Count : 4 -// - -#ifndef STACKTABLE_H -#define STACKTABLE_H - -#include -#include -#include -#include - -namespace SymTab { - template< typename Element, typename ConflictFunction > - class StackTable { - public: - StackTable(); - - void enterScope(); - void leaveScope(); - void add( Element *type ); - void add( std::string fwdDeclName ); - Element *lookup( std::string id ) const; - - void dump( std::ostream &os ) const; // debugging - private: - typedef std::pair< Element*, int > Entry; - typedef std::map< std::string, std::stack< Entry > > TableType; - - ConflictFunction conflictFunction; - TableType table; - int scopeLevel; - }; -} // SymTab - -#include "StackTable.cc" - -#endif // STACKTABLE_H - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: // Index: c/SymTab/TypeTable.h =================================================================== --- src/SymTab/TypeTable.h (revision e8032b011e6d5bdc74f9cb82d480387e1e6ecee2) +++ (revision ) @@ -1,53 +1,0 @@ -// -// 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. -// -// TypeTable.h -- -// -// Author : Richard C. Bilson -// Created On : Sun May 17 21:48:32 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Tue May 19 16:50:25 2015 -// Update Count : 3 -// - -#ifndef TYPETABLE_H -#define TYPETABLE_H - -#include -#include -#include -#include -#include - -#include "StackTable.h" -#include "SynTree/Declaration.h" - -namespace SymTab { - class TypeTableConflictFunction : public std::binary_function< NamedTypeDecl *, NamedTypeDecl *, NamedTypeDecl * > { - public: - NamedTypeDecl *operator()( NamedTypeDecl *existing, NamedTypeDecl *added ) { - if ( existing->get_base() == 0 ) { - return added; - } else if ( added->get_base() == 0 ) { - return existing; - } else { - throw SemanticError( "redeclaration of ", added ); - } // if - assert( false ); - return 0; - } - }; - - typedef StackTable< NamedTypeDecl, TypeTableConflictFunction > TypeTable; -} // namespace SymTab - -#endif // TYPETABLE_H - -// Local Variables: // -// tab-width: 4 // -// mode: c++ // -// compile-command: "make install" // -// End: //