Index: src/ResolvExpr/TypeEnvironment.cc =================================================================== --- src/ResolvExpr/TypeEnvironment.cc (revision b21c77a0e211d9361763565a2eb5ef4330f2957b) +++ src/ResolvExpr/TypeEnvironment.cc (revision 184557ed94d1cdbdc6fd685e497e5375f8968a96) @@ -21,4 +21,5 @@ #include "Common/InternedString.h" // for interned_string #include "Common/PassVisitor.h" // for PassVisitor +#include "Common/option.h" // for option #include "Common/utility.h" // for maybeClone #include "SymTab/Indexer.h" // for Indexer @@ -49,74 +50,4 @@ } -#if 0 - void EqvClass::initialize( const EqvClass &src, EqvClass &dest ) { - initialize( src, dest, src.type ); - } - - void EqvClass::initialize( const EqvClass &src, EqvClass &dest, const Type *ty ) { - dest.vars = src.vars; - dest.type = maybeClone( ty ); - dest.allowWidening = src.allowWidening; - dest.data = src.data; - } - - EqvClass::EqvClass() : type( nullptr ), allowWidening( true ) { - } - - EqvClass::EqvClass( const EqvClass &other ) { - initialize( other, *this ); - } - - EqvClass::EqvClass( const EqvClass &other, const Type *ty ) { - initialize( other, *this, ty ); - } - - EqvClass::EqvClass( EqvClass &&other ) - : vars{std::move(other.vars)}, type{other.type}, - allowWidening{std::move(other.allowWidening)}, data{std::move(other.data)} { - other.type = nullptr; - } - - EqvClass &EqvClass::operator=( const EqvClass &other ) { - if ( this == &other ) return *this; - initialize( other, *this ); - return *this; - } - - EqvClass &EqvClass::operator=( EqvClass &&other ) { - if ( this == &other ) return *this; - - vars = std::move(other.vars); - type = other.type; - allowWidening = std::move(other.allowWidening); - data = std::move(other.data); - - return *this; - } - - void EqvClass::set_type( Type* ty ) { type = ty; } - - void EqvClass::print( std::ostream &os, Indenter indent ) const { - os << "( "; - std::copy( vars.begin(), vars.end(), std::ostream_iterator< std::string >( os, " " ) ); - os << ")"; - if ( type ) { - os << " -> "; - type->print( os, indent+1 ); - } // if - if ( ! allowWidening ) { - os << " (no widening)"; - } // if - os << std::endl; - } - - const EqvClass* TypeEnvironment::lookup( const std::string &var ) const { - for ( std::list< EqvClass >::const_iterator i = env.begin(); i != env.end(); ++i ) { - if ( i->vars.find( var ) != i->vars.end() ) return &*i; - } // for - return nullptr; - } -#endif - std::pair TypeEnvironment::mergeClasses( interned_string root1, interned_string root2 ) { @@ -126,5 +57,5 @@ // determine new root assertf(classes->get_mode() == Classes::REMFROM, "classes updated to REMFROM by merge"); - auto ret = std::make_pair( classes->get_root(), classes->get_child ); + auto ret = std::make_pair( classes->get_root(), classes->get_child() ); // finalize classes @@ -302,94 +233,112 @@ } -#if !1 - /// Removes any class from env that intersects eqvClass - void filterOverlappingClasses( std::list &env, const EqvClass &eqvClass ) { - for ( auto i = env.begin(); i != env.end(); ) { - auto next = i; - ++next; - std::set intersection; - std::set_intersection( i->vars.begin(), i->vars.end(), eqvClass.vars.begin(), eqvClass.vars.end(), - std::inserter( intersection, intersection.begin() ) ); - if ( ! intersection.empty() ) { env.erase( i ); } - i = next; - } - } - - void TypeEnvironment::add( EqvClass &&eqvClass ) { - filterOverlappingClasses( env, eqvClass ); - env.push_back( std::move(eqvClass) ); - } - void TypeEnvironment::add( const Type::ForallList &tyDecls ) { for ( Type::ForallList::const_iterator i = tyDecls.begin(); i != tyDecls.end(); ++i ) { - EqvClass newClass; - newClass.vars.insert( (*i)->get_name() ); - newClass.data = TypeDecl::Data{ (*i) }; - env.push_back( std::move(newClass) ); + interned_string name = (*i)->get_name(); + classes = classes->add( name ); + bindings = bindings->set( name, *i ); } // for } void TypeEnvironment::add( const TypeSubstitution & sub ) { - EqvClass newClass; + interned_string not_found{nullptr}; + for ( auto p : sub ) { - newClass.vars.insert( p.first ); - newClass.type = p.second->clone(); - newClass.allowWidening = false; + interned_string var = p.first; + + // filter overlapping classes out of existing environment + // (this is a very shady assumption, but has worked for a long time...) + interned_string root = classes->find_or_default( v, not_found ); + if ( root != not_found ) { + classes = classes->remove_class( root ); + bindings = bindings->erase( root ); + } + // Minimal assumptions. Not technically correct, but might be good enough, and // is the best we can do at the moment since information is lost in the // transition to TypeSubstitution - newClass.data = TypeDecl::Data{ TypeDecl::Dtype, false }; - add( std::move(newClass) ); + TypeDecl::Data data{ TypeDecl::Dtype, false }; + + // add variable to class and bindings + classes = classes->add( var ); + bindings = bindings->set( var, BoundType{ p.second->clone, false, data } ); } } void TypeEnvironment::makeSubstitution( TypeSubstitution &sub ) const { - for ( std::list< EqvClass >::const_iterator theClass = env.begin(); theClass != env.end(); ++theClass ) { - for ( std::set< std::string >::const_iterator theVar = theClass->vars.begin(); theVar != theClass->vars.end(); ++theVar ) { - if ( theClass->type ) { - sub.add( *theVar, theClass->type ); - } else if ( theVar != theClass->vars.begin() ) { - TypeInstType *newTypeInst = new TypeInstType( Type::Qualifiers(), *theClass->vars.begin(), theClass->data.kind == TypeDecl::Ftype ); - sub.add( *theVar, newTypeInst ); - } // if - } // for - } // for + bindings->apply_to_all([classes, &sub]( interned_string root, const BoundType& bound ){ + classes->apply_to_class(root, [&]( interned_string var ) { + if ( bound.type ) { + sub.add( var, bound.type ); + } else if ( var != root ) { + sub.add( var, new TypeInstType{ + Type::Qualifiers{}, root, bound.data.kind == TypeDecl::Ftype } ); + } + }); + }); + sub.normalize(); } void TypeEnvironment::print( std::ostream &os, Indenter indent ) const { - for ( const EqvClass & theClass : env ) { - theClass.print( os, indent ); - } // for - } - - std::list< EqvClass >::iterator TypeEnvironment::internal_lookup( const std::string &var ) { - for ( std::list< EqvClass >::iterator i = env.begin(); i != env.end(); ++i ) { - if ( i->vars.count( var ) ) return i; - } // for - return env.end(); - } - - void TypeEnvironment::simpleCombine( const TypeEnvironment &second ) { - env.insert( env.end(), second.env.begin(), second.env.end() ); + bindings->apply_to_all([classes,&]( interned_string root, const BoundType& bound ) { + os << "( "; + classes->apply_to_class( root, [&os]( interned_string var ) { os << var << " "; } ); + os << ")"; + if ( bound.type ) { + os << " -> "; + type->print( os, indent+1 ); + } + if ( ! bound.allowWidening ) { + os << " (no widening)"; + } + os << std::endl; + }); + } + + void TypeEnvironment::simpleCombine( const TypeEnvironment &o ) { + o.bindings->apply_to_all( [&]( interned_string root, const BoundType& bound ) { + // add members of new class + interned_string new_root{nullptr}; + o.classes->apply_to_class( root, [this,&new_root]( interned_string var ) { + classes = classes->add( var ); + new_root = new_root ? mergeClasses( new_root, var ).first : var; + }); + // set binding for new class + bindings = bindings->set( new_root, bound ); + }); } void TypeEnvironment::extractOpenVars( OpenVarSet &openVars ) const { - for ( std::list< EqvClass >::const_iterator eqvClass = env.begin(); eqvClass != env.end(); ++eqvClass ) { - for ( std::set< std::string >::const_iterator var = eqvClass->vars.begin(); var != eqvClass->vars.end(); ++var ) { - openVars[ *var ] = eqvClass->data; - } // for - } // for + bindings->apply_to_all( [classes,&openVars]( interned_string root, const BoundType& bound ) { + classes->apply_to_class( root, [&openVars,&bound]( interned_string var ) { + openVars[ var ] = bound.data; + } ); + } ); } void TypeEnvironment::addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars ) { - for ( const EqvClass& c : actualEnv ) { - EqvClass c2 = c; - c2.allowWidening = false; - for ( const std::string& var : c2.vars ) { - openVars[ var ] = c2.data; - } - env.push_back( std::move(c2) ); - } + actualEnv.bindings->apply_to_all( [&]( interned_string root, const BoundType& bound ) { + // add members of new class, setting openVars concurrently + interned_string new_root{nullptr}; + actualEnv.classes->apply_to_class( root, [&]( interned_string var ) { + classes = classes->add( var ); + new_root = new_root ? mergeClasses( new_root, var ).first : var; + openVars[ var ] = bound.data; + } ); + // add new type binding without widening + bindings = bindings->set( new_root, + BoundType{ maybeClone(bound.type), false, bound.data } ); + } ); + } + + void TypeEnvironment::forbidWidening() { + bindings = bindings->apply_to_all([]( const interned_string& k, BoundType& c ) { + if ( c.allowWidening ) { + option ret = c; + c.allowWidening = false; + return ret; + } else return option{}; + }); } @@ -398,5 +347,4 @@ return out; } -#endif PassVisitor & operator<<( PassVisitor & gc, const TypeEnvironment & env ) { Index: src/ResolvExpr/TypeEnvironment.h =================================================================== --- src/ResolvExpr/TypeEnvironment.h (revision b21c77a0e211d9361763565a2eb5ef4330f2957b) +++ src/ResolvExpr/TypeEnvironment.h (revision 184557ed94d1cdbdc6fd685e497e5375f8968a96) @@ -86,29 +86,22 @@ bool allowWidening; TypeDecl::Data data; - }; - -#if 0 - /// An equivalence class, with its binding information - struct EqvClass { - std::set< std::string > vars; - Type *type; - bool allowWidening; - TypeDecl::Data data; - - void initialize( const EqvClass &src, EqvClass &dest ); - void initialize( const EqvClass &src, EqvClass &dest, const Type *ty ); - EqvClass(); - EqvClass( const EqvClass &other ); - EqvClass( const EqvClass &other, const Type *ty ); - EqvClass( EqvClass &&other ); - EqvClass &operator=( const EqvClass &other ); - EqvClass &operator=( EqvClass &&other ); - void print( std::ostream &os, Indenter indent = {} ) const; - - /// Takes ownership of `ty`, freeing old `type` - void set_type(Type* ty); - }; -#endif - + + BoundType() = default; + BoundType( TypeDecl* td ) : type{nullptr}, allowWidening{true}, data{td} {} + BoundType( Type* ty, bool aw, const TypeDecl::Data& td ) + : type{ty}, allowWidening{aw}, data{td} {} + BoundType( const BoundType& o ) + : type{maybeClone(o.type)}, allowWidening{o.allowWidening}, data{o.data} {} + BoundType( BoundType&& o ) = default; + BoundType& operator= (const BoundType& o) { + if ( this == &o ) return *this; + type = maybeClone( o.type ); + allowWidening = o.allowWidening; + data = o.data; + return *this; + } + BoundType& operator= (BoundType&& o) = default; + }; + class TypeEnvironment; @@ -137,10 +130,4 @@ /// Gets the bound type information of the referenced equivalence class, default if none inline BoundType get_bound() const; - -#if 0 - /// Gets the referenced equivalence class - inline EqvClass get_class() const; - EqvClass operator* () const { return get_class(); } -#endif // Check that there is a referenced typeclass @@ -171,5 +158,5 @@ interned_string root1, interned_string root2 ); - public: + public: class iterator : public std::iterator< std::forward_iterator_tag, @@ -213,7 +200,5 @@ AssertionSet& need, AssertionSet& have, const OpenVarSet& openVars, WidenMode widenMode, const SymTab::Indexer& indexer ); -#if !1 - private: - void add( EqvClass &&eqvClass ); + public: void add( const Type::ForallList &tyDecls ); @@ -222,14 +207,14 @@ template< typename SynTreeClass > int applyFree( SynTreeClass *&type ) const; void makeSubstitution( TypeSubstitution &result ) const; -#endif bool isEmpty() const { return classes->empty(); } -#if !1 void print( std::ostream &os, Indenter indent = {} ) const; + + /// Combines two environments without checking invariants. + /// Caller should ensure environments do not share type variables. void simpleCombine( const TypeEnvironment &second ); + void extractOpenVars( OpenVarSet &openVars ) const; -#endif TypeEnvironment *clone() const { return new TypeEnvironment( *this ); } -#if !1 /// Iteratively adds the environment of a new actual (with allowWidening = false), /// and extracts open variables. @@ -238,5 +223,4 @@ /// Disallows widening for all bindings in the environment void forbidWidening(); -#endif iterator begin() { return { this, bindings->begin() }; } @@ -244,10 +228,13 @@ }; - void ClassRef::update_root() { return root = env->classes->find( root ); } + interned_string ClassRef::update_root() { return root = env->classes->find( root ); } template T ClassRef::get_vars() const { T vars; - env->classes->find_class( root, std::inserter(vars, vars.end()) ); + if ( ! env->classes->count( root ) ) return vars; + env->classes->apply_to_class( root, [&vars]( interned_string var ) { + vars.insert( vars.end(), var ); + } ); return vars; } @@ -256,8 +243,4 @@ return env->bindings->get_or_default( root, BoundType{} ); } - -#if 0 - EqvClass ClassRef::get_class() const { return { get_vars(), get_bound() }; } -#endif template< typename SynTreeClass > @@ -275,7 +258,5 @@ } -#if !1 std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env ); -#endif PassVisitor & operator<<( PassVisitor & gc, const TypeEnvironment & env );