Index: src/GenPoly/Box.cc =================================================================== --- src/GenPoly/Box.cc (revision 63c0dbff99733b7093a5d2218a2b3362a30d0831) +++ src/GenPoly/Box.cc (revision bfae637fd56b22bbc3c95a309296411f8ab7d9ed) @@ -1278,5 +1278,5 @@ std::list< Expression *>::iterator paramBegin = appExpr->get_args().begin(); - TyVarMap exprTyVars; + TyVarMap exprTyVars( (TypeDecl::Kind)-1 ); makeTyVarMap( function, exprTyVars ); ReferenceToType *polyRetType = isPolyRet( function ); Index: src/GenPoly/ErasableScopedMap.h =================================================================== --- src/GenPoly/ErasableScopedMap.h (revision bfae637fd56b22bbc3c95a309296411f8ab7d9ed) +++ src/GenPoly/ErasableScopedMap.h (revision bfae637fd56b22bbc3c95a309296411f8ab7d9ed) @@ -0,0 +1,286 @@ +// +// 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. +// +// ScopedMap.h -- +// +// Author : Aaron B. Moss +// Created On : Wed Dec 2 11:37:00 2015 +// Last Modified By : Aaron B. Moss +// Last Modified On : Wed Dec 2 11:37:00 2015 +// Update Count : 1 +// + +#ifndef _ERASABLESCOPEDMAP_H +#define _ERASABLESCOPEDMAP_H + +#include +#include +#include +#include +#include + +namespace GenPoly { + /// A map where the items are placed into nested scopes; + /// inserted items are placed into the innermost scope, lookup looks from the innermost scope outward; + /// erasing a key means that find() will no longer report any instance of the key in a scope further + /// out, but the erasure itself is scoped. Key erasure works by inserting a sentinal value into the + /// value field, and thus only works for Value types where a meaningful sentinal can be chosen. + template + class ErasableScopedMap { + typedef std::map< Key, Value > Scope; + typedef std::vector< Scope > ScopeList; + + ScopeList scopes; ///< scoped list of maps + Value erased; ///< sentinal value for erased keys + public: + typedef typename Scope::key_type key_type; + typedef typename Scope::mapped_type mapped_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 ErasableScopedMap; + friend class const_iterator; + typedef typename std::map< Key, Value >::iterator wrapped_iterator; + typedef typename std::vector< std::map< Key, 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 != map->scopes[i].end() && it->second != map->erased; + } + + /// 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(ErasableScopedMap< Key, Value > const &_map, const wrapped_iterator &_it, size_type _i) + : map(&_map), it(_it), i(_i) {} + + public: + iterator(const iterator &that) : map(that.map), it(that.it), i(that.i) {} + iterator& operator= (const iterator &that) { + map = that.map; i = that.i; it = that.it; + return *this; + } + + reference operator* () { return *it; } + pointer operator-> () { return it.operator->(); } + + iterator& operator++ () { + if ( it == map->scopes[i].end() ) { + if ( i == 0 ) return *this; + --i; + it = map->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 == map->scopes[i].begin() ) { + ++i; + it = map->scopes[i].end(); + } + --it; + return prev_valid(); + } + iterator& operator-- (int) { iterator tmp = *this; --(*this); return tmp; } + + bool operator== (const iterator &that) { + return map == that.map && i == that.i && it == that.it; + } + bool operator!= (const iterator &that) { return !( *this == that ); } + + private: + ErasableScopedMap< Key, Value > const *map; + wrapped_iterator it; + size_type i; + }; + + class const_iterator : public std::iterator< std::bidirectional_iterator_tag, + value_type > { + friend class ErasableScopedMap; + typedef typename std::map< Key, Value >::iterator wrapped_iterator; + typedef typename std::map< Key, Value >::const_iterator wrapped_const_iterator; + typedef typename std::vector< std::map< Key, 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 != map->scopes[i].end() && it->second != map->erased; + } + + /// 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(ErasableScopedMap< Key, Value > const &_map, const wrapped_const_iterator &_it, size_type _i) + : map(&_map), it(_it), i(_i) {} + public: + const_iterator(const iterator &that) : map(that.map), it(that.it), i(that.i) {} + const_iterator(const const_iterator &that) : map(that.map), it(that.it), i(that.i) {} + const_iterator& operator= (const iterator &that) { + map = that.map; i = that.i; it = that.it; + return *this; + } + const_iterator& operator= (const const_iterator &that) { + map = that.map; i = that.i; it = that.it; + return *this; + } + + const_reference operator* () { return *it; } + const_pointer operator-> () { return it.operator->(); } + + const_iterator& operator++ () { + if ( it == map->scopes[i].end() ) { + if ( i == 0 ) return *this; + --i; + it = map->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 == map->scopes[i].begin() ) { + ++i; + it = map->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 map == that.map && i == that.i && it == that.it; + } + bool operator!= (const const_iterator &that) { return !( *this == that ); } + + private: + ErasableScopedMap< Key, Value > const *map; + 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(); + assert( ! scopes.empty() ); + } + + /// Default constructor initializes with one scope + ErasableScopedMap( const Value &erased_ ) : erased( erased_ ) { beginScope(); } + + iterator begin() { return iterator(*this, scopes.back().begin(), scopes.size()-1).next_valid(); } + const_iterator begin() const { return const_iterator(*this, scopes.back().begin(), scopes.size()-1).next_valid(); } + const_iterator cbegin() const { return const_iterator(*this, scopes.back().begin(), scopes.size()-1).next_valid(); } + iterator end() { return iterator(*this, scopes[0].end(), 0); } + const_iterator end() const { return const_iterator(*this, scopes[0].end(), 0); } + const_iterator cend() const { return const_iterator(*this, 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 Key &key ) { + for ( size_type i = scopes.size() - 1; ; --i ) { + typename Scope::iterator val = scopes[i].find( key ); + if ( val != scopes[i].end() ) { + return val->second == erased ? end() : iterator( *this, val, i ); + } + if ( i == 0 ) break; + } + return end(); + } + const_iterator find( const Key &key ) const { + return const_iterator( const_cast< ErasableScopedMap< Key, 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 Key &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 val->second == erased ? end() : iterator( *this, val, i ); + } + if ( i == 0 ) break; + } + return end(); + } + const_iterator findNext( const_iterator &it, const Key &key ) const { + return const_iterator( const_cast< ErasableScopedMap< Key, Value >* >(this)->findNext( it, key ) ); + } + + /// Inserts the given key-value pair 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(*this, res.first, scopes.size()-1), res.second ); + } + std::pair< iterator, bool > insert( const Key &key, const Value &value ) { return insert( std::make_pair( key, value ) ); } + + /// Marks the given element as erased from this scope inward; returns 1 for erased an element, 0 otherwise + size_type erase( const Key &key ) { + typename Scope::iterator val = scopes.back().find( key ); + if ( val != scopes.back().end() ) { + val->second = erased; + return 1; + } else { + scopes.back().insert( val, std::make_pair( key, erased ) ); + return 0; + } + } + + Value& operator[] ( const Key &key ) { + iterator slot = find( key ); + if ( slot != end() ) return slot->second; + return insert( key, Value() ).first->second; + } + }; +} // namespace GenPoly + +#endif // _ERASABLESCOPEDMAP_H + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/GenPoly/FindFunction.cc =================================================================== --- src/GenPoly/FindFunction.cc (revision 63c0dbff99733b7093a5d2218a2b3362a30d0831) +++ src/GenPoly/FindFunction.cc (revision bfae637fd56b22bbc3c95a309296411f8ab7d9ed) @@ -55,5 +55,5 @@ TyVarMap::iterator var = tyVars.find( (*i)->get_name() ); if ( var != tyVars.end() ) { - tyVars.erase( var ); + tyVars.erase( var->first ); } // if } // for Index: src/GenPoly/GenPoly.cc =================================================================== --- src/GenPoly/GenPoly.cc (revision 63c0dbff99733b7093a5d2218a2b3362a30d0831) +++ src/GenPoly/GenPoly.cc (revision bfae637fd56b22bbc3c95a309296411f8ab7d9ed) @@ -37,5 +37,5 @@ ReferenceToType *isPolyRet( FunctionType *function ) { if ( ! function->get_returnVals().empty() ) { - TyVarMap forallTypes; + TyVarMap forallTypes( (TypeDecl::Kind)-1 ); makeTyVarMap( function, forallTypes ); return (ReferenceToType*)isPolyType( function->get_returnVals().front()->get_type(), forallTypes ); Index: src/GenPoly/GenPoly.h =================================================================== --- src/GenPoly/GenPoly.h (revision 63c0dbff99733b7093a5d2218a2b3362a30d0831) +++ src/GenPoly/GenPoly.h (revision bfae637fd56b22bbc3c95a309296411f8ab7d9ed) @@ -17,8 +17,9 @@ #define GENPOLY_H -#include #include #include #include + +#include "ErasableScopedMap.h" #include "SymTab/Mangler.h" @@ -29,5 +30,5 @@ namespace GenPoly { - typedef std::map< std::string, TypeDecl::Kind > TyVarMap; + typedef ErasableScopedMap< std::string, TypeDecl::Kind > TyVarMap; /// A function needs an adapter if it returns a polymorphic value or if any of its Index: src/GenPoly/PolyMutator.cc =================================================================== --- src/GenPoly/PolyMutator.cc (revision 63c0dbff99733b7093a5d2218a2b3362a30d0831) +++ src/GenPoly/PolyMutator.cc (revision bfae637fd56b22bbc3c95a309296411f8ab7d9ed) @@ -27,6 +27,5 @@ } - PolyMutator::PolyMutator() : env( 0 ) { - } + PolyMutator::PolyMutator() : scopeTyVars( (TypeDecl::Kind)-1 ), env( 0 ) {} void PolyMutator::mutateStatementList( std::list< Statement* > &statements ) {