Index: src/Common/ScopedMap.h =================================================================== --- src/Common/ScopedMap.h (revision 8a972486173f920eea1f1868fff138e1568a8a59) +++ src/Common/ScopedMap.h (revision 2125443a425acb1ef9b560898cf33182c9f1dd8b) @@ -37,5 +37,5 @@ template Scope(N && n) : map(), note(std::forward(n)) {} - + Scope() = default; Scope(const Scope &) = default; @@ -46,5 +46,6 @@ typedef std::vector< Scope > ScopeList; - ScopeList scopes; ///< scoped list of maps + /// Scoped list of maps. + ScopeList scopes; public: typedef typename MapType::key_type key_type; @@ -58,158 +59,7 @@ typedef typename MapType::const_pointer const_pointer; - class iterator : public std::iterator< std::bidirectional_iterator_tag, value_type > { - friend class ScopedMap; - friend class const_iterator; - typedef typename ScopedMap::MapType::iterator wrapped_iterator; - typedef typename ScopedMap::ScopeList scope_list; - typedef typename scope_list::size_type size_type; - - /// Checks if this iterator points to a valid item - bool is_valid() const { - return it != (*scopes)[level].map.end(); - } - - /// Increments on invalid - iterator & next_valid() { - if ( ! is_valid() ) { ++(*this); } - return *this; - } - - /// Decrements on invalid - iterator & prev_valid() { - if ( ! is_valid() ) { --(*this); } - return *this; - } - - iterator(scope_list & _scopes, const wrapped_iterator & _it, size_type inLevel) - : scopes(&_scopes), it(_it), level(inLevel) {} - public: - iterator(const iterator & that) : scopes(that.scopes), it(that.it), level(that.level) {} - iterator & operator= (const iterator & that) { - scopes = that.scopes; level = that.level; it = that.it; - return *this; - } - - reference operator* () { return *it; } - pointer operator-> () const { return it.operator->(); } - - iterator & operator++ () { - if ( it == (*scopes)[level].map.end() ) { - if ( level == 0 ) return *this; - --level; - it = (*scopes)[level].map.begin(); - } else { - ++it; - } - return next_valid(); - } - iterator operator++ (int) { iterator tmp = *this; ++(*this); return tmp; } - - iterator & operator-- () { - // may fail if this is the begin iterator; allowed by STL spec - if ( it == (*scopes)[level].map.begin() ) { - ++level; - it = (*scopes)[level].map.end(); - } - --it; - return prev_valid(); - } - iterator operator-- (int) { iterator tmp = *this; --(*this); return tmp; } - - bool operator== (const iterator & that) const { - return scopes == that.scopes && level == that.level && it == that.it; - } - bool operator!= (const iterator & that) const { return !( *this == that ); } - - size_type get_level() const { return level; } - - Note & get_note() { return (*scopes)[level].note; } - const Note & get_note() const { return (*scopes)[level].note; } - - private: - scope_list *scopes; - wrapped_iterator it; - size_type level; - }; - - class const_iterator : public std::iterator< std::bidirectional_iterator_tag, - value_type > { - friend class ScopedMap; - typedef typename ScopedMap::MapType::iterator wrapped_iterator; - typedef typename ScopedMap::MapType::const_iterator wrapped_const_iterator; - typedef typename ScopedMap::ScopeList scope_list; - typedef typename scope_list::size_type size_type; - - /// Checks if this iterator points to a valid item - bool is_valid() const { - return it != (*scopes)[level].map.end(); - } - - /// Increments on invalid - const_iterator & next_valid() { - if ( ! is_valid() ) { ++(*this); } - return *this; - } - - /// Decrements on invalid - const_iterator & prev_valid() { - if ( ! is_valid() ) { --(*this); } - return *this; - } - - const_iterator(scope_list const & _scopes, const wrapped_const_iterator & _it, size_type inLevel) - : scopes(&_scopes), it(_it), level(inLevel) {} - public: - const_iterator(const iterator & that) : scopes(that.scopes), it(that.it), level(that.level) {} - const_iterator(const const_iterator & that) : scopes(that.scopes), it(that.it), level(that.level) {} - const_iterator & operator= (const iterator & that) { - scopes = that.scopes; level = that.level; it = that.it; - return *this; - } - const_iterator & operator= (const const_iterator & that) { - scopes = that.scopes; level = that.level; it = that.it; - return *this; - } - - const_reference operator* () { return *it; } - const_pointer operator-> () { return it.operator->(); } - - const_iterator & operator++ () { - if ( it == (*scopes)[level].map.end() ) { - if ( level == 0 ) return *this; - --level; - it = (*scopes)[level].map.begin(); - } else { - ++it; - } - return next_valid(); - } - const_iterator operator++ (int) { const_iterator tmp = *this; ++(*this); return tmp; } - - const_iterator & operator-- () { - // may fail if this is the begin iterator; allowed by STL spec - if ( it == (*scopes)[level].map.begin() ) { - ++level; - it = (*scopes)[level].map.end(); - } - --it; - return prev_valid(); - } - const_iterator operator-- (int) { const_iterator tmp = *this; --(*this); return tmp; } - - bool operator== (const const_iterator & that) const { - return scopes == that.scopes && level == that.level && it == that.it; - } - bool operator!= (const const_iterator & that) const { return !( *this == that ); } - - size_type get_level() const { return level; } - - const Note & get_note() const { return (*scopes)[level].note; } - - private: - scope_list const *scopes; - wrapped_const_iterator it; - size_type level; - }; + // Both iterator types are complete bidrectional iterators, see below. + class iterator; + class const_iterator; /// Starts a new scope @@ -297,11 +147,4 @@ } - template< typename value_type_t > - std::pair< iterator, bool > insert( iterator at, value_type_t && value ) { - MapType & scope = (*at.scopes)[ at.level ].map; - std::pair< typename MapType::iterator, bool > res = scope.insert( std::forward( value ) ); - return std::make_pair( iterator(scopes, std::move( res.first ), at.level), std::move( res.second ) ); - } - template< typename value_t > std::pair< iterator, bool > insert( const Key & key, value_t && value ) { return insert( std::make_pair( key, std::forward( value ) ) ); } @@ -324,10 +167,5 @@ } - iterator erase( iterator pos ) { - MapType & scope = (*pos.scopes)[ pos.level ].map; - const typename iterator::wrapped_iterator & new_it = scope.erase( pos.it ); - iterator it( *pos.scopes, new_it, pos.level ); - return it.next_valid(); - } + iterator erase( iterator pos ); size_type count( const Key & key ) const { @@ -344,4 +182,171 @@ } }; + +template +class ScopedMap::iterator : + public std::iterator< std::bidirectional_iterator_tag, value_type > { + friend class ScopedMap; + friend class const_iterator; + typedef typename ScopedMap::MapType::iterator wrapped_iterator; + typedef typename ScopedMap::ScopeList scope_list; + typedef typename scope_list::size_type size_type; + + /// Checks if this iterator points to a valid item + bool is_valid() const { + return it != (*scopes)[level].map.end(); + } + + /// Increments on invalid + iterator & next_valid() { + if ( ! is_valid() ) { ++(*this); } + return *this; + } + + /// Decrements on invalid + iterator & prev_valid() { + if ( ! is_valid() ) { --(*this); } + return *this; + } + + iterator(scope_list & _scopes, const wrapped_iterator & _it, size_type inLevel) + : scopes(&_scopes), it(_it), level(inLevel) {} +public: + iterator(const iterator & that) : scopes(that.scopes), it(that.it), level(that.level) {} + iterator & operator= (const iterator & that) { + scopes = that.scopes; level = that.level; it = that.it; + return *this; + } + + reference operator* () { return *it; } + pointer operator-> () const { return it.operator->(); } + + iterator & operator++ () { + if ( it == (*scopes)[level].map.end() ) { + if ( level == 0 ) return *this; + --level; + it = (*scopes)[level].map.begin(); + } else { + ++it; + } + return next_valid(); + } + iterator operator++ (int) { iterator tmp = *this; ++(*this); return tmp; } + + iterator & operator-- () { + // may fail if this is the begin iterator; allowed by STL spec + if ( it == (*scopes)[level].map.begin() ) { + ++level; + it = (*scopes)[level].map.end(); + } + --it; + return prev_valid(); + } + iterator operator-- (int) { iterator tmp = *this; --(*this); return tmp; } + + bool operator== (const iterator & that) const { + return scopes == that.scopes && level == that.level && it == that.it; + } + bool operator!= (const iterator & that) const { return !( *this == that ); } + + size_type get_level() const { return level; } + + Note & get_note() { return (*scopes)[level].note; } + const Note & get_note() const { return (*scopes)[level].note; } + +private: + scope_list *scopes; + wrapped_iterator it; + size_type level; +}; + +template +class ScopedMap::const_iterator : + public std::iterator< std::bidirectional_iterator_tag, value_type > { + friend class ScopedMap; + typedef typename ScopedMap::MapType::iterator wrapped_iterator; + typedef typename ScopedMap::MapType::const_iterator wrapped_const_iterator; + typedef typename ScopedMap::ScopeList scope_list; + typedef typename scope_list::size_type size_type; + + /// Checks if this iterator points to a valid item + bool is_valid() const { + return it != (*scopes)[level].map.end(); + } + + /// Increments on invalid + const_iterator & next_valid() { + if ( ! is_valid() ) { ++(*this); } + return *this; + } + + /// Decrements on invalid + const_iterator & prev_valid() { + if ( ! is_valid() ) { --(*this); } + return *this; + } + + const_iterator(scope_list const & _scopes, const wrapped_const_iterator & _it, size_type inLevel) + : scopes(&_scopes), it(_it), level(inLevel) {} +public: + const_iterator(const iterator & that) : scopes(that.scopes), it(that.it), level(that.level) {} + const_iterator(const const_iterator & that) : scopes(that.scopes), it(that.it), level(that.level) {} + const_iterator & operator= (const iterator & that) { + scopes = that.scopes; level = that.level; it = that.it; + return *this; + } + const_iterator & operator= (const const_iterator & that) { + scopes = that.scopes; level = that.level; it = that.it; + return *this; + } + + const_reference operator* () { return *it; } + const_pointer operator-> () { return it.operator->(); } + + const_iterator & operator++ () { + if ( it == (*scopes)[level].map.end() ) { + if ( level == 0 ) return *this; + --level; + it = (*scopes)[level].map.begin(); + } else { + ++it; + } + return next_valid(); + } + const_iterator operator++ (int) { const_iterator tmp = *this; ++(*this); return tmp; } + + const_iterator & operator-- () { + // may fail if this is the begin iterator; allowed by STL spec + if ( it == (*scopes)[level].map.begin() ) { + ++level; + it = (*scopes)[level].map.end(); + } + --it; + return prev_valid(); + } + const_iterator operator-- (int) { const_iterator tmp = *this; --(*this); return tmp; } + + bool operator== (const const_iterator & that) const { + return scopes == that.scopes && level == that.level && it == that.it; + } + bool operator!= (const const_iterator & that) const { return !( *this == that ); } + + size_type get_level() const { return level; } + + const Note & get_note() const { return (*scopes)[level].note; } + +private: + scope_list const *scopes; + wrapped_const_iterator it; + size_type level; +}; + +template +typename ScopedMap::iterator + ScopedMap::erase( iterator pos ) { + MapType & scope = (*pos.scopes)[ pos.level ].map; + const typename iterator::wrapped_iterator & new_it = scope.erase( pos.it ); + iterator it( *pos.scopes, new_it, pos.level ); + return it.next_valid(); +} // Local Variables: // Index: src/Concurrency/Actors.cpp =================================================================== --- src/Concurrency/Actors.cpp (revision 8a972486173f920eea1f1868fff138e1568a8a59) +++ src/Concurrency/Actors.cpp (revision 2125443a425acb1ef9b560898cf33182c9f1dd8b) @@ -21,11 +21,13 @@ #include "AST/TranslationUnit.hpp" #include "AST/Expr.hpp" +#include using namespace ast; +using namespace std; namespace Concurrency { struct CollectactorStructDecls : public ast::WithGuards { - std::map & actorStructDecls; - std::map & messageStructDecls; + unordered_set & actorStructDecls; + unordered_set & messageStructDecls; const StructDecl ** requestDecl; const EnumDecl ** allocationDecl; @@ -34,9 +36,12 @@ StructDecl * parentDecl; bool insideStruct = false; - + bool namedDecl = false; + + // finds and sets a ptr to the Allocation enum, which is needed in the next pass void previsit( const EnumDecl * decl ) { if( decl->name == "Allocation" ) *allocationDecl = decl; } + // finds and sets a ptr to the actor, message, and request structs, which are needed in the next pass void previsit( const StructDecl * decl ) { GuardValue(insideStruct); @@ -45,14 +50,26 @@ if( decl->name == "actor" ) *actorDecl = decl; if( decl->name == "message" ) *msgDecl = decl; - if( decl->name == "request" ) *requestDecl = decl; + if( decl->name == "request" ) *requestDecl = decl; } + // this catches structs of the form: + // struct dummy_actor { actor a; }; + // since they should be: + // struct dummy_actor { inline actor; }; + void previsit ( const ObjectDecl * decl ) { + if ( insideStruct && ! decl->name.empty() ) { + GuardValue(namedDecl); + namedDecl = true; + } + } + + // this collects the valid actor and message struct decl pts void postvisit( const StructInstType * node ) { if ( ! *actorDecl || ! *msgDecl ) return; - if ( insideStruct ) { + if ( insideStruct && !namedDecl ) { if ( node->aggr() == *actorDecl ) { - actorStructDecls.insert({parentDecl, 1}); + actorStructDecls.insert( parentDecl ); } else if ( node->aggr() == *msgDecl ) { - messageStructDecls.insert({parentDecl, 1}); + messageStructDecls.insert( parentDecl ); } } @@ -60,5 +77,5 @@ public: - CollectactorStructDecls( std::map & actorStructDecls, std::map & messageStructDecls, + CollectactorStructDecls( unordered_set & actorStructDecls, unordered_set & messageStructDecls, const StructDecl ** requestDecl, const EnumDecl ** allocationDecl, const StructDecl ** actorDecl, const StructDecl ** msgDecl ) : actorStructDecls( actorStructDecls ), messageStructDecls( messageStructDecls ), requestDecl( requestDecl ), @@ -66,12 +83,111 @@ }; +// keeps track of all fwdDecls of message routines so that we can hoist them to right after the appropriate decls +class FwdDeclTable { + + // tracks which decls we have seen so that we can hoist the FunctionDecl to the highest point possible + struct FwdDeclData { + const StructDecl * actorDecl; + const StructDecl * msgDecl; + FunctionDecl * fwdDecl; + bool actorFound; + bool msgFound; + + bool readyToInsert() { return actorFound && msgFound; } + bool foundActor() { actorFound = true; return readyToInsert(); } + bool foundMsg() { msgFound = true; return readyToInsert(); } + + FwdDeclData( const StructDecl * actorDecl, const StructDecl * msgDecl, FunctionDecl * fwdDecl ) : + actorDecl(actorDecl), msgDecl(msgDecl), fwdDecl(fwdDecl), actorFound(false), msgFound(false) {} + }; + + // map indexed by actor struct ptr + // value is map of all FwdDeclData that contains said actor struct ptr + // inner map is indexed by the message struct ptr of FwdDeclData + unordered_map> actorMap; + + // this map is the same except the outer map is indexed by message ptr and the inner is indexed by actor ptr + unordered_map> msgMap; + + void insert( const StructDecl * decl, const StructDecl * otherDecl, unordered_map> & map, FwdDeclData * data ) { + auto iter = map.find( decl ); + if ( iter != map.end() ) { // if decl exists in map append data to existing inner map + iter->second.emplace( make_pair( otherDecl, data ) ); + } else { // else create inner map for key + map.emplace( make_pair( decl, unordered_map( { make_pair( otherDecl, data ) } ) ) ); + } + } + + public: + // insert decl into table so that we can fwd declare it later (average cost: O(1)) + void insertDecl( const StructDecl * actorDecl, const StructDecl * msgDecl, FunctionDecl * fwdDecl ) { + FwdDeclData * declToInsert = new FwdDeclData( actorDecl, msgDecl, fwdDecl ); + insert( actorDecl, msgDecl, actorMap, declToInsert ); + insert( msgDecl, actorDecl, msgMap, declToInsert ); + } + + // returns list of decls to insert after current struct decl + // Over the entire pass the runtime of this routine is O(r) where r is the # of receive routines + list updateDecl( const StructDecl * decl, bool isMsg ) { + unordered_map> & map = isMsg ? msgMap : actorMap; + unordered_map> & otherMap = isMsg ? actorMap : msgMap; + auto iter = map.find( decl ); + list toInsertAfter; // this is populated with decls that are ready to insert + if ( iter == map.end() ) return toInsertAfter; + + // iterate over inner map + unordered_map & currInnerMap = iter->second; + for ( auto innerIter = currInnerMap.begin(); innerIter != currInnerMap.end(); ) { + FwdDeclData * currentDatum = innerIter->second; + bool readyToInsert = isMsg ? currentDatum->foundMsg() : currentDatum->foundActor(); + if ( ! readyToInsert ) { ++innerIter; continue; } + + // readyToInsert is true so we are good to insert the forward decl of the message fn + toInsertAfter.push_back( currentDatum->fwdDecl ); + + // need to remove from other map before deleting + // find inner map in other map ( other map is actor map if original is msg map and vice versa ) + const StructDecl * otherDecl = isMsg ? currentDatum->actorDecl : currentDatum->msgDecl; + auto otherMapIter = otherMap.find( otherDecl ); + + unordered_map & otherInnerMap = otherMapIter->second; + + // find the FwdDeclData we need to remove in the other inner map + auto otherInnerIter = otherInnerMap.find( decl ); + + // remove references to deleted FwdDeclData from current inner map + innerIter = currInnerMap.erase( innerIter ); // this does the increment so no explicit inc needed + + // remove references to deleted FwdDeclData from other inner map + otherInnerMap.erase( otherInnerIter ); + + // if other inner map is now empty, remove key from other outer map + if ( otherInnerMap.empty() ) + otherMap.erase( otherDecl ); + + // now we are safe to delete the FwdDeclData since we are done with it + // and we have removed all references to it from our data structures + delete currentDatum; + } + + // if current inner map is now empty, remove key from outer map. + // Have to do this after iterating for safety + if ( currInnerMap.empty() ) + map.erase( decl ); + + return toInsertAfter; + } +}; + +#define __ALLOC 0 // C_TODO: complete swap to no-alloc version + struct GenReceiveDecls : public ast::WithDeclsToAdd<> { - std::map & actorStructDecls; - std::map & messageStructDecls; + unordered_set & actorStructDecls; + unordered_set & messageStructDecls; const StructDecl ** requestDecl; const EnumDecl ** allocationDecl; const StructDecl ** actorDecl; const StructDecl ** msgDecl; - std::vector & forwardDecls; + FwdDeclTable & forwardDecls; void postvisit( const FunctionDecl * decl ) { @@ -90,5 +206,7 @@ // If the struct instances are derived actor and message types then generate the message send routine - if ( actorStructDecls.count( arg1InstType->aggr() ) && messageStructDecls.count( arg2InstType->aggr() ) ) { + auto actorIter = actorStructDecls.find( arg1InstType->aggr() ); + auto messageIter = messageStructDecls.find( arg2InstType->aggr() ); + if ( actorIter != actorStructDecls.end() && messageIter != messageStructDecls.end() ) { // check that we have found all the decls we need from @@ -107,7 +225,8 @@ return receiver; } - */ + */ // C_TODO: update this with new no alloc version CompoundStmt * sendBody = new CompoundStmt( decl->location ); + #if __ALLOC // Generates: request * new_req = alloc(); sendBody->push_back( new DeclStmt( @@ -120,4 +239,15 @@ ) )); + #else + // Generates: request new_req; + sendBody->push_back( new DeclStmt( + decl->location, + new ObjectDecl( + decl->location, + "new_req", + new StructInstType( *requestDecl ) + ) + )); + #endif // Function type is: Allocation (*)( derived_actor &, derived_msg & ) @@ -160,4 +290,5 @@ )); + #if __ALLOC // Generates: (*new_req){ &receiver, &msg, fn }; sendBody->push_back( new ExprStmt( @@ -189,4 +320,35 @@ ) )); + #else + // Generates: new_req{ &receiver, &msg, fn }; + sendBody->push_back( new ExprStmt( + decl->location, + new UntypedExpr ( + decl->location, + new NameExpr( decl->location, "?{}" ), + { + new NameExpr( decl->location, "new_req" ), + new AddressExpr( new NameExpr( decl->location, "receiver" ) ), + new AddressExpr( new NameExpr( decl->location, "msg" ) ), + new NameExpr( decl->location, "fn" ) + } + ) + )); + + // Generates: send( receiver, new_req ); + sendBody->push_back( new ExprStmt( + decl->location, + new UntypedExpr ( + decl->location, + new NameExpr( decl->location, "send" ), + { + { + new NameExpr( decl->location, "receiver" ), + new NameExpr( decl->location, "new_req" ) + } + } + ) + )); + #endif // Generates: return receiver; @@ -225,5 +387,6 @@ // forward decls to resolve use before decl problem for '|' routines - forwardDecls.push_back( ast::deepCopy( sendOperatorFunction ) ); + forwardDecls.insertDecl( *actorIter, *messageIter , ast::deepCopy( sendOperatorFunction ) ); + // forwardDecls.push_back( ast::deepCopy( sendOperatorFunction ) ); sendOperatorFunction->stmts = sendBody; @@ -233,51 +396,51 @@ public: - GenReceiveDecls( std::map & actorStructDecls, std::map & messageStructDecls, + GenReceiveDecls( unordered_set & actorStructDecls, unordered_set & messageStructDecls, const StructDecl ** requestDecl, const EnumDecl ** allocationDecl, const StructDecl ** actorDecl, const StructDecl ** msgDecl, - std::vector & forwardDecls ) : actorStructDecls(actorStructDecls), messageStructDecls(messageStructDecls), + FwdDeclTable & forwardDecls ) : actorStructDecls(actorStructDecls), messageStructDecls(messageStructDecls), requestDecl(requestDecl), allocationDecl(allocationDecl), actorDecl(actorDecl), msgDecl(msgDecl), forwardDecls(forwardDecls) {} }; struct GenFwdDecls : public ast::WithDeclsToAdd<> { - std::map & actorStructDecls; - std::map & messageStructDecls; - std::vector & forwardDecls; - bool done; - - void postvisit( const FunctionDecl * decl ) { - if ( done ) return; - // return if not of the form receive( param1, param2 ) or if it is a forward decl - if ( decl->name != "receive" || decl->params.size() != 2 || !decl->stmts ) return; - - // the params should be references - const ReferenceType * derivedActorRef = dynamic_cast(decl->params.at(0)->get_type()); - const ReferenceType * derivedMsgRef = dynamic_cast(decl->params.at(1)->get_type()); - if ( !derivedActorRef || !derivedMsgRef ) return; - - // the references should be to struct instances - const StructInstType * arg1InstType = dynamic_cast(derivedActorRef->base.get()); - const StructInstType * arg2InstType = dynamic_cast(derivedMsgRef->base.get()); - if ( !arg1InstType || !arg2InstType ) return; - - // If the struct instances are derived actor and message types then generate the message send routine - if ( actorStructDecls.count( arg1InstType->aggr() ) && messageStructDecls.count( arg2InstType->aggr() ) ) { - done = true; - for ( const auto & func : forwardDecls ) { - declsToAddBefore.push_back( func ); - } + unordered_set & actorStructDecls; + unordered_set & messageStructDecls; + FwdDeclTable & forwardDecls; + + void postvisit( const StructDecl * decl ) { + list toAddAfter; + auto actorIter = actorStructDecls.find( decl ); + if ( actorIter != actorStructDecls.end() ) { // this is a derived actor decl + // get list of fwd decls that we can now insert + toAddAfter = forwardDecls.updateDecl( decl, false ); + + // get rid of decl from actorStructDecls since we no longer need it + actorStructDecls.erase( actorIter ); + } else { + auto messageIter = messageStructDecls.find( decl ); + if ( messageIter == messageStructDecls.end() ) return; + + toAddAfter = forwardDecls.updateDecl( decl, true ); + + // get rid of decl from messageStructDecls since we no longer need it + messageStructDecls.erase( messageIter ); + } + + // add the fwd decls to declsToAddAfter + for ( FunctionDecl * func : toAddAfter ) { + declsToAddAfter.push_back( func ); } } public: - GenFwdDecls( std::map & actorStructDecls, std::map & messageStructDecls, - std::vector & forwardDecls ) : actorStructDecls(actorStructDecls), messageStructDecls(messageStructDecls), - forwardDecls(forwardDecls), done(false) {} + GenFwdDecls( unordered_set & actorStructDecls, unordered_set & messageStructDecls, + FwdDeclTable & forwardDecls ) : actorStructDecls(actorStructDecls), messageStructDecls(messageStructDecls), + forwardDecls(forwardDecls) {} }; void implementActors( TranslationUnit & translationUnit ) { - // maps to collect all derived actor and message types - std::map actorStructDecls; - std::map messageStructDecls; - std::vector forwardDecls; + // unordered_maps to collect all derived actor and message types + unordered_set actorStructDecls; + unordered_set messageStructDecls; + FwdDeclTable forwardDecls; // for storing through the passes Index: src/GenPoly/ErasableScopedMap.h =================================================================== --- src/GenPoly/ErasableScopedMap.h (revision 8a972486173f920eea1f1868fff138e1568a8a59) +++ src/GenPoly/ErasableScopedMap.h (revision 2125443a425acb1ef9b560898cf33182c9f1dd8b) @@ -51,5 +51,5 @@ typedef typename Scope::const_pointer const_pointer; - // Both iterator types are complete bidirection iterators, defined below. + // Both iterator types are complete bidirectional iterators, see below. class iterator; class const_iterator; Index: src/GenPoly/ScopedSet.h =================================================================== --- src/GenPoly/ScopedSet.h (revision 8a972486173f920eea1f1868fff138e1568a8a59) +++ src/GenPoly/ScopedSet.h (revision 2125443a425acb1ef9b560898cf33182c9f1dd8b) @@ -21,231 +21,238 @@ namespace GenPoly { - /// A set where the items are placed into nested scopes; - /// inserted items are placed into the innermost scope, lookup looks from the innermost scope outward - template - class ScopedSet { - typedef std::set< Value > Scope; - typedef std::vector< Scope > ScopeList; - - ScopeList scopes; ///< scoped list of sets - public: - typedef typename Scope::key_type key_type; - typedef typename Scope::value_type value_type; - typedef typename ScopeList::size_type size_type; - typedef typename ScopeList::difference_type difference_type; - typedef typename Scope::reference reference; - typedef typename Scope::const_reference const_reference; - typedef typename Scope::pointer pointer; - typedef typename Scope::const_pointer const_pointer; - - class iterator : public std::iterator< std::bidirectional_iterator_tag, - value_type > { - friend class ScopedSet; - friend class const_iterator; - typedef typename std::set< Value >::iterator wrapped_iterator; - typedef typename std::vector< std::set< Value > > scope_list; - typedef typename scope_list::size_type size_type; - - /// Checks if this iterator points to a valid item - bool is_valid() const { - return it != (*scopes)[i].end(); - } - - /// Increments on invalid - iterator& next_valid() { - if ( ! is_valid() ) { ++(*this); } - return *this; - } - - /// Decrements on invalid - iterator& prev_valid() { - if ( ! is_valid() ) { --(*this); } - return *this; - } - - iterator(scope_list const &_scopes, const wrapped_iterator &_it, size_type _i) - : scopes(&_scopes), it(_it), i(_i) {} - public: - iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {} - iterator& operator= (const iterator &that) { - scopes = that.scopes; i = that.i; it = that.it; - return *this; - } - - reference operator* () { return *it; } - pointer operator-> () { return it.operator->(); } - - iterator& operator++ () { - if ( it == (*scopes)[i].end() ) { - if ( i == 0 ) return *this; - --i; - it = (*scopes)[i].begin(); - } else { - ++it; - } - return next_valid(); - } - iterator operator++ (int) { iterator tmp = *this; ++(*this); return tmp; } - - iterator& operator-- () { - // may fail if this is the begin iterator; allowed by STL spec - if ( it == (*scopes)[i].begin() ) { - ++i; - it = (*scopes)[i].end(); - } - --it; - return prev_valid(); - } - iterator operator-- (int) { iterator tmp = *this; --(*this); return tmp; } - - bool operator== (const iterator &that) { - return scopes == that.scopes && i == that.i && it == that.it; - } - bool operator!= (const iterator &that) { return !( *this == that ); } - - size_type get_level() const { return i; } - - private: - scope_list const *scopes; - wrapped_iterator it; - size_type i; - }; - - class const_iterator : public std::iterator< std::bidirectional_iterator_tag, - value_type > { - friend class ScopedSet; - typedef typename std::set< Value >::iterator wrapped_iterator; - typedef typename std::set< Value >::const_iterator wrapped_const_iterator; - typedef typename std::vector< std::set< Value > > scope_list; - typedef typename scope_list::size_type size_type; - - /// Checks if this iterator points to a valid item - bool is_valid() const { - return it != (*scopes)[i].end(); - } - - /// Increments on invalid - const_iterator& next_valid() { - if ( ! is_valid() ) { ++(*this); } - return *this; - } - - /// Decrements on invalid - const_iterator& prev_valid() { - if ( ! is_valid() ) { --(*this); } - return *this; - } - - const_iterator(scope_list const &_scopes, const wrapped_const_iterator &_it, size_type _i) - : scopes(&_scopes), it(_it), i(_i) {} - public: - const_iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {} - const_iterator(const const_iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {} - const_iterator& operator= (const iterator &that) { - scopes = that.scopes; i = that.i; it = that.it; - return *this; - } - const_iterator& operator= (const const_iterator &that) { - scopes = that.scopes; i = that.i; it = that.it; - return *this; - } - - const_reference operator* () { return *it; } - const_pointer operator-> () { return it.operator->(); } - - const_iterator& operator++ () { - if ( it == (*scopes)[i].end() ) { - if ( i == 0 ) return *this; - --i; - it = (*scopes)[i].begin(); - } else { - ++it; - } - return next_valid(); - } - const_iterator operator++ (int) { const_iterator tmp = *this; ++(*this); return tmp; } - - const_iterator& operator-- () { - // may fail if this is the begin iterator; allowed by STL spec - if ( it == (*scopes)[i].begin() ) { - ++i; - it = (*scopes)[i].end(); - } - --it; - return prev_valid(); - } - const_iterator operator-- (int) { const_iterator tmp = *this; --(*this); return tmp; } - - bool operator== (const const_iterator &that) { - return scopes == that.scopes && i == that.i && it == that.it; - } - bool operator!= (const const_iterator &that) { return !( *this == that ); } - - size_type get_level() const { return i; } - - private: - scope_list const *scopes; - wrapped_const_iterator it; - size_type i; - }; - - /// Starts a new scope - void beginScope() { - Scope scope; - scopes.push_back(scope); - } - - /// Ends a scope; invalidates any iterators pointing to elements of that scope - void endScope() { - scopes.pop_back(); - } - - /// Default constructor initializes with one scope - ScopedSet() { beginScope(); } - - iterator begin() { return iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); } - const_iterator begin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); } - const_iterator cbegin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); } - iterator end() { return iterator(scopes, scopes[0].end(), 0); } - const_iterator end() const { return const_iterator(scopes, scopes[0].end(), 0); } - const_iterator cend() const { return const_iterator(scopes, scopes[0].end(), 0); } - - /// Gets the index of the current scope (counted from 1) - size_type currentScope() const { return scopes.size(); } - - /// Finds the given key in the outermost scope it occurs; returns end() for none such - iterator find( const Value &key ) { - for ( size_type i = scopes.size() - 1; ; --i ) { - typename Scope::iterator val = scopes[i].find( key ); - if ( val != scopes[i].end() ) return iterator( scopes, val, i ); - if ( i == 0 ) break; - } - return end(); - } - const_iterator find( const Value &key ) const { - return const_iterator( const_cast< ScopedSet< Value >* >(this)->find( key ) ); - } - - /// Finds the given key in the outermost scope inside the given scope where it occurs - iterator findNext( const_iterator &it, const Value &key ) { - if ( it.i == 0 ) return end(); + +/// A set where the items are placed into nested scopes; +/// inserted items are placed into the innermost scope, lookup looks from the innermost scope outward +template +class ScopedSet { + typedef std::set< Value > Scope; + typedef std::vector< Scope > ScopeList; + + ScopeList scopes; ///< scoped list of sets +public: + typedef typename Scope::key_type key_type; + typedef typename Scope::value_type value_type; + typedef typename ScopeList::size_type size_type; + typedef typename ScopeList::difference_type difference_type; + typedef typename Scope::reference reference; + typedef typename Scope::const_reference const_reference; + typedef typename Scope::pointer pointer; + typedef typename Scope::const_pointer const_pointer; + + // Both iterator types are complete bidirectional iterators, see below. + class iterator; + class const_iterator; + + /// Starts a new scope + void beginScope() { + Scope scope; + scopes.push_back(scope); + } + + /// Ends a scope; invalidates any iterators pointing to elements of that scope + void endScope() { + scopes.pop_back(); + } + + /// Default constructor initializes with one scope + ScopedSet() { beginScope(); } + + iterator begin() { return iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); } + const_iterator begin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); } + const_iterator cbegin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); } + iterator end() { return iterator(scopes, scopes[0].end(), 0); } + const_iterator end() const { return const_iterator(scopes, scopes[0].end(), 0); } + const_iterator cend() const { return const_iterator(scopes, scopes[0].end(), 0); } + + /// Gets the index of the current scope (counted from 1) + size_type currentScope() const { return scopes.size(); } + + /// Finds the given key in the outermost scope it occurs; returns end() for none such + iterator find( const Value &key ) { + for ( size_type i = scopes.size() - 1; ; --i ) { + typename Scope::iterator val = scopes[i].find( key ); + if ( val != scopes[i].end() ) return iterator( scopes, val, i ); + if ( i == 0 ) break; + } + return end(); + } + const_iterator find( const Value &key ) const { + return const_iterator( const_cast< ScopedSet< Value >* >(this)->find( key ) ); + } + + /// Finds the given key in the outermost scope inside the given scope where it occurs + iterator findNext( const_iterator &it, const Value &key ) { + if ( it.i == 0 ) return end(); for ( size_type i = it.i - 1; ; --i ) { - typename Scope::iterator val = scopes[i].find( key ); - if ( val != scopes[i].end() ) return iterator( scopes, val, i ); - if ( i == 0 ) break; - } - return end(); - } - const_iterator findNext( const_iterator &it, const Value &key ) const { - return const_iterator( const_cast< ScopedSet< Value >* >(this)->findNext( it, key ) ); - } - - /// Inserts the given value into the outermost scope - std::pair< iterator, bool > insert( const value_type &value ) { - std::pair< typename Scope::iterator, bool > res = scopes.back().insert( value ); - return std::make_pair( iterator(scopes, res.first, scopes.size()-1), res.second ); - } - - }; + typename Scope::iterator val = scopes[i].find( key ); + if ( val != scopes[i].end() ) return iterator( scopes, val, i ); + if ( i == 0 ) break; + } + return end(); + } + const_iterator findNext( const_iterator &it, const Value &key ) const { + return const_iterator( const_cast< ScopedSet< Value >* >(this)->findNext( it, key ) ); + } + + /// Inserts the given value into the outermost scope + std::pair< iterator, bool > insert( const value_type &value ) { + std::pair< typename Scope::iterator, bool > res = scopes.back().insert( value ); + return std::make_pair( iterator(scopes, res.first, scopes.size()-1), res.second ); + } +}; + +template +class ScopedSet::iterator : + public std::iterator< std::bidirectional_iterator_tag, value_type > { + friend class ScopedSet; + friend class const_iterator; + typedef typename std::set< Value >::iterator wrapped_iterator; + typedef typename std::vector< std::set< Value > > scope_list; + typedef typename scope_list::size_type size_type; + + /// Checks if this iterator points to a valid item + bool is_valid() const { + return it != (*scopes)[i].end(); + } + + /// Increments on invalid + iterator& next_valid() { + if ( ! is_valid() ) { ++(*this); } + return *this; + } + + /// Decrements on invalid + iterator& prev_valid() { + if ( ! is_valid() ) { --(*this); } + return *this; + } + + iterator(scope_list const &_scopes, const wrapped_iterator &_it, size_type _i) + : scopes(&_scopes), it(_it), i(_i) {} +public: + iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {} + iterator& operator= (const iterator &that) { + scopes = that.scopes; i = that.i; it = that.it; + return *this; + } + + reference operator* () { return *it; } + pointer operator-> () { return it.operator->(); } + + iterator& operator++ () { + if ( it == (*scopes)[i].end() ) { + if ( i == 0 ) return *this; + --i; + it = (*scopes)[i].begin(); + } else { + ++it; + } + return next_valid(); + } + iterator operator++ (int) { iterator tmp = *this; ++(*this); return tmp; } + + iterator& operator-- () { + // may fail if this is the begin iterator; allowed by STL spec + if ( it == (*scopes)[i].begin() ) { + ++i; + it = (*scopes)[i].end(); + } + --it; + return prev_valid(); + } + iterator operator-- (int) { iterator tmp = *this; --(*this); return tmp; } + + bool operator== (const iterator &that) { + return scopes == that.scopes && i == that.i && it == that.it; + } + bool operator!= (const iterator &that) { return !( *this == that ); } + + size_type get_level() const { return i; } + +private: + scope_list const *scopes; + wrapped_iterator it; + size_type i; +}; + +template +class ScopedSet::const_iterator : + public std::iterator< std::bidirectional_iterator_tag, value_type > { + friend class ScopedSet; + typedef typename std::set< Value >::iterator wrapped_iterator; + typedef typename std::set< Value >::const_iterator wrapped_const_iterator; + typedef typename std::vector< std::set< Value > > scope_list; + typedef typename scope_list::size_type size_type; + + /// Checks if this iterator points to a valid item + bool is_valid() const { + return it != (*scopes)[i].end(); + } + + /// Increments on invalid + const_iterator& next_valid() { + if ( ! is_valid() ) { ++(*this); } + return *this; + } + + /// Decrements on invalid + const_iterator& prev_valid() { + if ( ! is_valid() ) { --(*this); } + return *this; + } + + const_iterator(scope_list const &_scopes, const wrapped_const_iterator &_it, size_type _i) + : scopes(&_scopes), it(_it), i(_i) {} +public: + const_iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {} + const_iterator(const const_iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {} + const_iterator& operator= (const iterator &that) { + scopes = that.scopes; i = that.i; it = that.it; + return *this; + } + const_iterator& operator= (const const_iterator &that) { + scopes = that.scopes; i = that.i; it = that.it; + return *this; + } + + const_reference operator* () { return *it; } + const_pointer operator-> () { return it.operator->(); } + + const_iterator& operator++ () { + if ( it == (*scopes)[i].end() ) { + if ( i == 0 ) return *this; + --i; + it = (*scopes)[i].begin(); + } else { + ++it; + } + return next_valid(); + } + const_iterator operator++ (int) { const_iterator tmp = *this; ++(*this); return tmp; } + + const_iterator& operator-- () { + // may fail if this is the begin iterator; allowed by STL spec + if ( it == (*scopes)[i].begin() ) { + ++i; + it = (*scopes)[i].end(); + } + --it; + return prev_valid(); + } + const_iterator operator-- (int) { const_iterator tmp = *this; --(*this); return tmp; } + + bool operator== (const const_iterator &that) { + return scopes == that.scopes && i == that.i && it == that.it; + } + bool operator!= (const const_iterator &that) { return !( *this == that ); } + + size_type get_level() const { return i; } + +private: + scope_list const *scopes; + wrapped_const_iterator it; + size_type i; +}; + } // namespace GenPoly