Changeset 982f95d for src/ResolvExpr

Timestamp:

Jun 15, 2018, 5:09:29 PM (6 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

new-env

Children:

97397a26

Parents:

1d7b0a8

Message:

Start of new environment implementation; terribly broken

Location:

src/ResolvExpr

Files:

• AdjustExprType.cc (modified) (2 diffs)
• AlternativeFinder.cc (modified) (1 diff)
• CastCost.cc (modified) (2 diffs)
• ConversionCost.cc (modified) (3 diffs)
• Occurs.cc (modified) (4 diffs)
• PolyCost.cc (modified) (2 diffs)
• PtrsAssignable.cc (modified) (3 diffs)
• PtrsCastable.cc (modified) (3 diffs)
• TypeEnvironment.cc (modified) (6 diffs)
• TypeEnvironment.h (modified) (7 diffs)
• Unify.cc (modified) (3 diffs)

src/ResolvExpr/AdjustExprType.cc

@@ -19 +19 @@
 #include "SynTree/Mutator.h"      // for Mutator
 #include "SynTree/Type.h"         // for PointerType, TypeInstType, Type
-#include "TypeEnvironment.h"      // for EqvClass, TypeEnvironment
+#include "TypeEnvironment.h"      // for ClassRef, TypeEnvironment
 
 namespace ResolvExpr {
@@ -74 +74 @@
 
         Type * AdjustExprType::postmutate( TypeInstType * typeInst ) {
-                if ( const EqvClass* eqvClass = env.lookup( typeInst->get_name() ) ) {
-                        if ( eqvClass->data.kind == TypeDecl::Ftype ) {
+                if ( ClassRef eqvClass = env.lookup( typeInst->get_name() ) ) {
+                        if ( eqvClass.get_bound().data.kind == TypeDecl::Ftype ) {
                                 return new PointerType{ Type::Qualifiers(), typeInst };
                         }

src/ResolvExpr/AlternativeFinder.cc

@@ -1109 +1109 @@
                                         }
                                 } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->get_result()->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer)
-                                        if ( const EqvClass *eqvClass = func->env.lookup( typeInst->get_name() ) ) {
-                                                if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass->type ) ) {
+                                        if ( ClassRef eqvClass = func->env.lookup( typeInst->get_name() ) ) {
+                                                if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.get_bound().type ) ) {
                                                         Alternative newFunc( *func );
                                                         referenceToRvalueConversion( newFunc.expr, newFunc.cost );

src/ResolvExpr/CastCost.cc

@@ -18 +18 @@
 #include "ConversionCost.h"              // for ConversionCost
 #include "Cost.h"                        // for Cost, Cost::infinity
-#include "ResolvExpr/TypeEnvironment.h"  // for TypeEnvironment, EqvClass
+#include "ResolvExpr/TypeEnvironment.h"  // for TypeEnvironment, ClassRef
 #include "SymTab/Indexer.h"              // for Indexer
 #include "SynTree/Declaration.h"         // for TypeDecl, NamedTypeDecl
@@ -43 +43 @@
         Cost castCost( Type *src, Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env ) {
                 if ( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) {
-                        if ( const EqvClass* eqvClass = env.lookup( destAsTypeInst->get_name() ) ) {
-                                if ( eqvClass->type ) {
-                                        return castCost( src, eqvClass->type, indexer, env );
+                        if ( ClassRef eqvClass = env.lookup( destAsTypeInst->get_name() ) ) {
+                                if ( Type* boundTy = eqvClass.get_bound().type ) {
+                                        return castCost( src, boundTy, indexer, env );
                                 } else {
                                         return Cost::infinity;

src/ResolvExpr/ConversionCost.cc

@@ -22 +22 @@
 #include "Common/GC.h"                   // for new_static_root
 #include "ResolvExpr/Cost.h"             // for Cost
-#include "ResolvExpr/TypeEnvironment.h"  // for EqvClass, TypeEnvironment
+#include "ResolvExpr/TypeEnvironment.h"  // for ClassRef, TypeEnvironment
 #include "SymTab/Indexer.h"              // for Indexer
 #include "SynTree/Declaration.h"         // for TypeDecl, NamedTypeDecl
@@ -44 +44 @@
                 if ( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) {
                         PRINT( std::cerr << "type inst " << destAsTypeInst->name; )
-                        if ( const EqvClass* eqvClass = env.lookup( destAsTypeInst->name ) ) {
-                                if ( eqvClass->type ) {
-                                        return conversionCost( src, eqvClass->type, indexer, env );
+                        if ( ClassRef eqvClass = env.lookup( destAsTypeInst->name ) ) {
+                                if ( Type* boundTy = eqvClass.get_bound().type ) {
+                                        return conversionCost( src, boundTy, indexer, env );
                                 } else {
                                         return Cost::infinity;
@@ -360 +360 @@
 
         void ConversionCost::postvisit( TypeInstType *inst ) {
-                if ( const EqvClass *eqvClass = env.lookup( inst->name ) ) {
-                        cost = costFunc( eqvClass->type, dest, indexer, env );
+                if ( ClassRef eqvClass = env.lookup( inst->name ) ) {
+                        cost = costFunc( eqvClass.get_bound().type, dest, indexer, env );
                 } else if ( TypeInstType *destAsInst = dynamic_cast< TypeInstType* >( dest ) ) {
                         if ( inst->name == destAsInst->name ) {

src/ResolvExpr/Occurs.cc

@@ -14 +14 @@
 //
 
-#include <set>                // for set, _Rb_tree_const_iterator
 #include <string>             // for string
+#include <unordered_set>      // for unordered_set
 
 #include "Common/PassVisitor.h"
 #include "SynTree/Type.h"     // for TypeInstType, Type
-#include "TypeEnvironment.h"  // for EqvClass, TypeEnvironment
+#include "TypeEnvironment.h"  // for ClassRef, TypeEnvironment
 
 namespace ResolvExpr {
@@ -27 +27 @@
 
                 bool result;
-                std::set< std::string > eqvVars;
+                using VarSet = std::unordered_set< std::string >;
+                VarSet eqvVars;
                 const TypeEnvironment &tenv;
         };
@@ -38 +39 @@
 
         Occurs::Occurs( std::string varName, const TypeEnvironment & env ) : result( false ), tenv( env ) {
-                if ( const EqvClass *eqvClass = tenv.lookup( varName ) ) {
-                        eqvVars = eqvClass->vars;
+                if ( ClassRef eqvClass = tenv.lookup( varName ) ) {
+                        eqvVars = eqvClass.get_vars<VarSet>();
                 } else {
                         eqvVars.insert( varName );
@@ -51 +52 @@
                 if ( eqvVars.find( typeInst->get_name() ) != eqvVars.end() ) {
                         result = true;
-                } else if ( const EqvClass *eqvClass = tenv.lookup( typeInst->get_name() ) ) {
-                        if ( eqvClass->type ) {
+                } else if ( ClassRef eqvClass = tenv.lookup( typeInst->get_name() ) ) {
+                        if ( Type* boundTy = eqvClass.get_bound().type ) {
 ///       std::cerr << typeInst->get_name() << " is bound to";
-///       eqvClass.type->print( std::cerr );
+///       boundTy->print( std::cerr );
 ///       std::cerr << std::endl;
-                                eqvClass->type->accept( *visitor );
+                                boundTy->accept( *visitor );
                         } // if
                 } // if

src/ResolvExpr/PolyCost.cc

@@ -17 +17 @@
 #include "SymTab/Indexer.h"   // for Indexer
 #include "SynTree/Type.h"     // for TypeInstType, Type
-#include "TypeEnvironment.h"  // for EqvClass, TypeEnvironment
+#include "TypeEnvironment.h"  // for ClassRef, TypeEnvironment
 
 namespace ResolvExpr {
@@ -39 +39 @@
 
         void PolyCost::previsit(TypeInstType * typeInst) {
-                if ( const EqvClass *eqvClass = tenv.lookup( typeInst->name ) ) {
-                        if ( eqvClass->type ) {
-                                if ( TypeInstType * otherTypeInst = dynamic_cast< TypeInstType* >( eqvClass->type ) ) {
+                if ( ClassRef eqvClass = tenv.lookup( typeInst->name ) ) {
+                        if ( Type* boundTy = eqvClass.get_bound().type ) {
+                                if ( TypeInstType * otherTypeInst = dynamic_cast< TypeInstType* >( boundTy ) ) {
                                         if ( indexer.lookupType( otherTypeInst->name ) ) {
                                                 // bound to opaque type

src/ResolvExpr/PtrsAssignable.cc

@@ -15 +15 @@
 
 #include "Common/PassVisitor.h"
-#include "ResolvExpr/TypeEnvironment.h"  // for EqvClass, TypeEnvironment
+#include "ResolvExpr/TypeEnvironment.h"  // for ClassRef, TypeEnvironment
 #include "SynTree/Type.h"                // for TypeInstType, Type, BasicType
 #include "SynTree/Visitor.h"             // for Visitor
@@ -51 +51 @@
                 // std::cerr << "assignable: " << src << " | " << dest << std::endl;
                 if ( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) {
-                        if ( const EqvClass *eqvClass = env.lookup( destAsTypeInst->get_name() ) ) {
-                                return ptrsAssignable( src, eqvClass->type, env );
+                        if ( ClassRef eqvClass = env.lookup( destAsTypeInst->get_name() ) ) {
+                                return ptrsAssignable( src, eqvClass.get_bound().type, env );
                         } // if
                 } // if
@@ -94 +94 @@
         void PtrsAssignable::postvisit(  __attribute__((unused)) TraitInstType *inst ) {}
         void PtrsAssignable::postvisit( TypeInstType *inst ) {
-                if ( const EqvClass *eqvClass = env.lookup( inst->get_name() ) ) {
-                        if ( eqvClass->type ) {
+                if ( ClassRef eqvClass = env.lookup( inst->get_name() ) ) {
+                        if ( Type* boundTy = eqvClass.get_bound().type ) {
                                 // T * = S * for any S depends on the type bound to T
-                                result = ptrsAssignable( eqvClass->type, dest, env );
+                                result = ptrsAssignable( boundTy, dest, env );
                         }
                 } // if

src/ResolvExpr/PtrsCastable.cc

@@ -15 +15 @@
 
 #include "Common/PassVisitor.h"
-#include "ResolvExpr/TypeEnvironment.h"  // for EqvClass, TypeEnvironment
+#include "ResolvExpr/TypeEnvironment.h"  // for ClassRef, TypeEnvironment
 #include "SymTab/Indexer.h"              // for Indexer
 #include "SynTree/Declaration.h"         // for TypeDecl, TypeDecl::Kind::Ftype
@@ -63 +63 @@
                                                 } // if
                                         } //if
-                                } else if ( const EqvClass *eqvClass = env.lookup( typeInst->get_name() ) ) {
-                                        if ( eqvClass->data.kind == TypeDecl::Ftype ) {
+                                } else if ( ClassRef eqvClass = env.lookup( typeInst->get_name() ) ) {
+                                        if ( eqvClass.get_bound().data.kind == TypeDecl::Ftype ) {
                                                 return -1;
                                         } // if
@@ -78 +78 @@
         int ptrsCastable( Type *src, Type *dest, const TypeEnvironment &env, const SymTab::Indexer &indexer ) {
                 if ( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) {
-                        if ( const EqvClass *eqvClass = env.lookup( destAsTypeInst->get_name() ) ) {
+                        if ( ClassRef eqvClass = env.lookup( destAsTypeInst->get_name() ) ) {
                                 // xxx - should this be ptrsCastable?
-                                return ptrsAssignable( src, eqvClass->type, env );
+                                return ptrsAssignable( src, eqvClass.get_bound().type, env );
                         } // if
                 } // if

src/ResolvExpr/TypeEnvironment.cc

@@ -19 +19 @@
 #include <utility>                     // for pair, move
 
+#include "Common/InternedString.h"     // for interned_string
 #include "Common/PassVisitor.h"        // for PassVisitor<GcTracer>
 #include "Common/utility.h"            // for maybeClone
+#include "SymTab/Indexer.h"            // for Indexer
 #include "SynTree/GcTracer.h"          // for PassVisitor<GcTracer>
 #include "SynTree/Type.h"              // for Type, FunctionType, Type::Fora...
 #include "SynTree/TypeSubstitution.h"  // for TypeSubstitution
 #include "TypeEnvironment.h"
+#include "Unify.h"                     // for unifyInexact
 
 namespace ResolvExpr {
@@ -45 +48 @@
         }
 
+#if 0
         void EqvClass::initialize( const EqvClass &src, EqvClass &dest ) {
                 dest.vars = src.vars;
@@ -52 +56 @@
         }
 
-        EqvClass::EqvClass() : type( 0 ), allowWidening( true ) {
-        }
+        EqvClass::EqvClass() : vars(), type( 0 ), allowWidening( true ), data() {}
+
+        EqvClass::EqvClass( std::vector<interned_string>&& vs, BoundType&& bound )
+                : vars( vs.begin(), vs.end() ), type( maybeClone( bound.type ) ), 
+                  allowWidening( bound.allowWidening ), data( bound.data ) {}
 
         EqvClass::EqvClass( const EqvClass &other ) {
@@ -91 +98 @@
                 return nullptr;
         }
-
+#endif
+
+        std::pair<interned_string, interned_string> TypeEnvironment::mergeClasses( 
+                        interned_string root1, interned_string root2 ) {
+                // merge classes
+                Classes* newClasses = classes->merge( root1, root2 );
+
+                // 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 );
+                
+                // finalize classes
+                classes = newClasses;
+                return ret;
+        }
+
+        ClassRef TypeEnvironment::lookup( interned_string var ) const {
+                interned_string root = classes->find_or_default( var, nullptr );
+                if ( root ) return { this, root };
+                else return { nullptr, var };
+        }
+
+        bool tyVarCompatible( const TypeDecl::Data & data, Type *type ) {
+                switch ( data.kind ) {
+                  case TypeDecl::Dtype:
+                        // to bind to an object type variable, the type must not be a function type.
+                        // if the type variable is specified to be a complete type then the incoming
+                        // type must also be complete
+                        // xxx - should this also check that type is not a tuple type and that it's not a ttype?
+                        return ! isFtype( type ) && (! data.isComplete || type->isComplete() );
+                  case TypeDecl::Ftype:
+                        return isFtype( type );
+                  case TypeDecl::Ttype:
+                        // ttype unifies with any tuple type
+                        return dynamic_cast< TupleType * >( type ) || Tuples::isTtype( type );
+                } // switch
+                return false;
+        }
+
+        bool TypeEnvironment::bindVar( TypeInstType* typeInst, Type* bindTo, 
+                        const TypeDecl::Data& data, AssertionSet& need, AssertionSet& have, 
+                        const OpenVarSet& openVars, WidenMode widenMode, const SymTab::Indexer& indexer ) {
+                // remove references from other, so that type variables can only bind to value types
+                bindTo = bindTo->stripReferences();
+                
+                auto tyVar = openVars.find( typeInst->get_name() );
+                assert( tyVar != openVars.end() );
+                if ( ! tyVarCompatible( tyVar->second, other ) ) return false;
+
+                if ( occurs( bindTo, typeInst->get_name(), *this ) ) return false;
+
+                if ( ClassRef curClass = lookup( typeInst->get_name() ) ) {
+                        BoundType curData = curClass.get_bound();
+                        if ( curData.type ) {
+                                Type* common = nullptr;
+                                // attempt to unify equivalence class type (which needs its qualifiers restored) 
+                                // with the target type
+                                Type* newType = curData.type->clone();
+                                newType->get_qualifiers() = typeInst->get_qualifiers();
+                                if ( unifyInexact( newType, bindTo, *this, need, have, openVars, 
+                                                widenMode & WidenMode{ curData.allowWidening, true }, indexer, common ) ) {
+                                        if ( common ) {
+                                                // update bound type to common type
+                                                common->get_qualifiers() = Type::Qualifiers{};
+                                                curData.type = common;
+                                                bindings = bindings->set( curClass.update_root(), curData );
+                                        }
+                                        return true;
+                                } else return false;
+                        } else {
+                                // update bound type to other type
+                                curData.type = bindTo->clone();
+                                curData.type->get_qualifiers() = Type::Qualifiers{};
+                                curData.allowWidening = widenMode.widenFirst && widenMode.widenSecond;
+                                bindings = bindings->set( curClass.get_root(), curData );
+                        }
+                } else {
+                        // make new class consisting entirely of this variable
+                        BoundType curData{ bindTo->clone(), widenMode.first && widenMode.second, data };
+                        curData.type->get_qualifiers() = Type::Qualifiers{};
+                        classes = classes->add( curClass.get_root() );
+                        bindings = bindings->set( curClass.get_root(), curData );
+                }
+                return true;
+        }
+        
+        bool TypeEnvironment::bindVarToVar( TypeInstType* var1, TypeInstType* var2, 
+                        const TypeDecl::Data& data, AssertionSet& need, AssertionSet& have, 
+                        const OpenVarSet& openVars, WidenMode widenMode, const SymTab::Indexer& indexer ) {
+                ClassRef class1 = env.lookup( var1->get_name() );
+                ClassRef class2 = env.lookup( var2->get_name() );
+                
+                // exit early if variables already bound together
+                if ( class1 && class2 && class1 == class2 ) {
+                        BoundType data1 = class1.get_bound();
+                        // narrow the binding if needed
+                        if ( data1.allowWidening && widenMode.first != widenMode.second ) {
+                                data1.allowWidening = false;
+                                bindings = bindings->set( class1.get_root(), data1 );
+                        }
+                        return true;
+                }
+
+                BoundType data1 = class1 ? class1.get_bound() : BoundType{};
+                BoundType data2 = class2 ? class2.get_bound() : BoundType{};
+
+                bool widen1 = data1.allowWidening && widenMode.widenFirst;
+                bool widen2 = data2.allowWidening && widenMode.widenSecond;
+
+                if ( data1.type && data2.type ) {
+                        // attempt to unify bound classes
+                        Type* common = nullptr;
+                        if ( unifyInexact( data1.type->clone(), data2.type->clone(), *this, need, have, 
+                                        openVars, WidenMode{ widen1, widen2 }, indexer, common ) ) {
+                                // merge type variables
+                                interned_string root = mergeClasses( class1.update_root(), class2.update_root() );
+                                // update bindings
+                                data1.allowWidening = widen1 && widen2;
+                                if ( common ) {
+                                        common->get_qualifiers() = Type::Qualifiers{};
+                                        data1.type = common;
+                                }
+                                bindings = bindings->set( root, data1 );
+                        } else return false;
+                } else if ( class1 && class2 ) {
+                        // both classes exist, only one bound -- merge type variables
+                        auto merged = mergeClasses( class1.get_root(), class2.get_root() );
+                        // remove subordinate binding
+                        bindings = bindings->erase( merged.second );
+                        // update root binding (narrow widening as needed, or set new binding for changed root)
+                        if ( data1.type ) {
+                                if ( data1.allowWidening != widen1 ) {
+                                        data1.allowWidening = widen1;
+                                        bindings = bindings->set( merged.first, data1 );
+                                } else if ( merged.first == class2.get_root() ) {
+                                        bindings = bindings->set( merged.first, data1 );
+                                }
+                        } else /* if ( data2.type ) */ {
+                                if ( data2.allowWidening != widen2 ) {
+                                        data2.allowWidening = widen2;
+                                        bindings = bindings->set( root, data2 );
+                                } else if ( merged.first == class1.get_root() ) {
+                                        bindings = bindings->set( merged.first, data2 );
+                                }
+                        }
+                } else if ( class1 ) {
+                        // add unbound var2 to class1
+                        classes = classes->add( class2.get_root() );
+                        auto merged = mergeClasses( class1.get_root(), class2.get_root() );
+                        // update bindings (narrow as needed, or switch binding to root)
+                        if ( merged.first == class2.get_root() ) {
+                                data1.allowWidening = widen1;
+                                bindings = bindings->erase( merged.second )->set( merged.first, data1 );
+                        } else if ( data1.allowWidening != widen1 ) {
+                                bindings = bindings->set( merged.first, data1 );
+                        }
+                } else if ( class2 ) {
+                        // add unbound var1 to class1
+                        classes = classes->add( class1.get_root() );
+                        auto merged = mergeClasses( class1.get_root(), class2.get_root() );
+                        // update bindings (narrow as needed, or switch binding to root)
+                        if ( merged.first == class1.get_root() ) {
+                                data2.allowWidening = widen2;
+                                bindings = bindings->erase( merged.second )->set( merged.first, data2 );
+                        } else if ( data2.allowWidening != widen2 ) {
+                                bindings = bindings->set( merged.first, data2 );
+                        }
+                } else {
+                        // make new class with pair of unbound vars
+                        classes = classes->add( class1.get_root() )->add( class2.get_root() );
+                        auto merged = mergeClasses( class1.get_root(), class2.get_root() );
+                        bindings = bindings->set( merged.first, BoundType{ nullptr, widen1 && widen2, data } );
+                }
+                return true;
+        }
+
+#if !1
         /// Removes any class from env that intersects eqvClass
         void filterOverlappingClasses( std::list<EqvClass> &env, const EqvClass &eqvClass ) {
@@ -180 +363 @@
         }
 
-        void TypeEnvironment::combine( const TypeEnvironment &second, Type *(*combineFunc)( Type*, Type* ) ) {
-                TypeEnvironment secondCopy( second );
-                for ( std::list< EqvClass >::iterator firstClass = env.begin(); firstClass != env.end(); ++firstClass ) {
-                        EqvClass &newClass = *firstClass;
-                        std::set< std::string > newVars;
-                        for ( std::set< std::string >::const_iterator var = firstClass->vars.begin(); var != firstClass->vars.end(); ++var ) {
-                                std::list< EqvClass >::iterator secondClass = secondCopy.internal_lookup( *var );
-                                if ( secondClass != secondCopy.env.end() ) {
-                                        newVars.insert( secondClass->vars.begin(), secondClass->vars.end() );
-                                        if ( secondClass->type ) {
-                                                if ( newClass.type ) {
-                                                        newClass.type = combineFunc( newClass.type, secondClass->type );
-                                                        newClass.allowWidening = newClass.allowWidening && secondClass->allowWidening;
-                                                } else {
-                                                        newClass.type = secondClass->type->clone();
-                                                        newClass.allowWidening = secondClass->allowWidening;
-                                                } // if
-                                        } // if
-                                        secondCopy.env.erase( secondClass );
-                                } // if
-                        } // for
-                        newClass.vars.insert( newVars.begin(), newVars.end() );
-                } // for
-                for ( std::list< EqvClass >::iterator secondClass = secondCopy.env.begin(); secondClass != secondCopy.env.end(); ++secondClass ) {
-                        env.push_back( *secondClass );
-                } // for
-        }
-
         void TypeEnvironment::extractOpenVars( OpenVarSet &openVars ) const {
                 for ( std::list< EqvClass >::const_iterator eqvClass = env.begin(); eqvClass != env.end(); ++eqvClass ) {
@@ -231 +386 @@
                 return out;
         }
+#endif
 
         PassVisitor<GcTracer> & operator<<( PassVisitor<GcTracer> & gc, const TypeEnvironment & env ) {
-                for ( const EqvClass & c : env ) {
-                        maybeAccept( c.type, gc );
+                for ( ClassRef c : env ) {
+                        maybeAccept( c.get_bound().type, gc );
                 }
                 return gc;

src/ResolvExpr/TypeEnvironment.h

@@ -7 +7 @@
 // TypeEnvironment.h --
 //
-// Author           : Richard C. Bilson
+// Author           : Aaron B. Moss
 // Created On       : Sun May 17 12:24:58 2015
-// Last Modified By : Peter A. Buhr
-// Last Modified On : Sat Jul 22 09:35:45 2017
-// Update Count     : 3
+// Last Modified By : Aaron B. Moss
+// Last Modified On : Wed Jun 13 16:31:00 2018
+// Update Count     : 4
 //
 
 #pragma once
 
-#include <iostream>                    // for ostream
-#include <list>                        // for list, list<>::iterator, list<>...
-#include <map>                         // for map, map<>::value_compare
-#include <set>                         // for set
-#include <string>                      // for string
-
-#include "SynTree/Declaration.h"       // for TypeDecl::Data, DeclarationWit...
-#include "SynTree/SynTree.h"           // for UniqueId
-#include "SynTree/Type.h"              // for Type, Type::ForallList
-#include "SynTree/TypeSubstitution.h"  // for TypeSubstitution
-
-template< typename Pass >
-class PassVisitor;
+#include <iostream>                        // for ostream
+#include <iterator>
+#include <list>                            // for list, list<>::iterator, list<>...
+#include <map>                             // for map, map<>::value_compare
+#include <set>                             // for set
+#include <string>                          // for string
+#include <utility>                         // for pair
+#include <vector>                          // for vector
+
+#include "Common/InternedString.h"         // for interned_string
+#include "Common/PersistentDisjointSet.h"  // for PersistentDisjointSet
+#include "Common/PersistentMap.h"          // for PersistentMap
+#include "SynTree/Declaration.h"           // for TypeDecl::Data, DeclarationWit...
+#include "SynTree/SynTree.h"               // for UniqueId
+#include "SynTree/Type.h"                  // for Type, TypeInstType, Type::ForallList
+#include "SynTree/TypeSubstitution.h"      // for TypeSubstitution
+
+template< typename Pass > class PassVisitor;
 class GcTracer;
+namespace SymTab { class Indexer; }
 
 namespace ResolvExpr {
@@ -40 +46 @@
         // declarations.
         //
-        // I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this comparator.
+        // I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this 
+        // comparator.
         //
         // Note: since this compares pointers for position, minor changes in the source file that affect
         // memory layout can alter compilation time in unpredictable ways. For example, the placement
         // of a line directive can reorder type pointers with respect to each other so that assertions
-        // are seen in different orders, causing a potentially different number of unification calls when
-        // resolving assertions. I've seen a TU go from 36 seconds to 27 seconds by reordering line directives
-        // alone, so it would be nice to fix this comparison so that assertions compare more consistently.
-        // I've tried to modify this to compare on mangle name instead of type as the second comparator, but
-        // this causes some assertions to never be recorded. More investigation is needed.
+        // are seen in different orders, causing a potentially different number of unification calls 
+        // when resolving assertions. I've seen a TU go from 36 seconds to 27 seconds by reordering 
+        // line directives alone, so it would be nice to fix this comparison so that assertions compare 
+        // more consistently. I've tried to modify this to compare on mangle name instead of type as 
+        // the second comparator, but this causes some assertions to never be recorded. More 
+        // investigation is needed.
         struct AssertCompare {
                 bool operator()( DeclarationWithType * d1, DeclarationWithType * d2 ) const {
@@ -59 +67 @@
         struct AssertionSetValue {
                 bool isUsed;
-                // chain of Unique IDs of the assertion declarations. The first ID in the chain is the ID of an assertion on the current type,
-                // with each successive ID being the ID of an assertion pulled in by the previous ID. The last ID in the chain is
-                // the ID of the assertion that pulled in the current assertion.
+                // chain of Unique IDs of the assertion declarations. The first ID in the chain is the ID 
+                // of an assertion on the current type, with each successive ID being the ID of an 
+                // assertion pulled in by the previous ID. The last ID in the chain is the ID of the 
+                // assertion that pulled in the current assertion.
                 std::list< UniqueId > idChain;
         };
@@ -70 +79 @@
         void printOpenVarSet( const OpenVarSet &, std::ostream &, int indent = 0 );
 
+        /// A data structure for holding all the necessary information for a type binding
+        struct BoundType {
+                Type* type;
+                bool allowWidening;
+                TypeDecl::Data data;
+        };
+
+#if 0
+        /// An equivalence class, with its binding information
         struct EqvClass {
                 std::set< std::string > vars;
@@ -78 +96 @@
                 void initialize( const EqvClass &src, EqvClass &dest );
                 EqvClass();
+                EqvClass( std::vector<interned_string>&& vars, BoundType&& bound );
                 EqvClass( const EqvClass &other );
                 EqvClass &operator=( const EqvClass &other );
                 void print( std::ostream &os, Indenter indent = {} ) const;
         };
+#endif
+
+        class TypeEnvironment;
+
+        /// A reference to an equivalence class that may be used to constitute one from its environment
+        class ClassRef {
+                friend TypeEnvironment;
+
+                const TypeEnvironment* env;  ///< Containing environment
+                interned_string root;        ///< Name of root type
+
+        public:
+                ClassRef() : env(nullptr), root(nullptr) {}
+                ClassRef( const TypeEnvironment* env, interned_string root ) : env(env), root(root) {}
+
+                /// Gets the root of the reference equivalence class;
+                interned_string get_root() const { return root; }
+
+                /// Ensures that root is still the representative element of this typeclass;
+                /// undefined behaviour if called without referenced typeclass; returns new root
+                inline interned_string update_root();
+
+                /// Gets the type variables of the referenced equivalence class, empty list for none
+                template<typename T = std::vector<interned_string>>
+                inline T get_vars() const;
+
+                /// 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
+                explicit operator bool() const { return env != nullptr; }
+
+                bool operator== (const ClassRef& o) const { return env == o.env && root == o.root; }
+                bool operator!= (const ClassRef& o) const { return !(*this == o); }
+        };
 
         class TypeEnvironment {
+                friend ClassRef;
+
+                /// Backing storage for equivalence classes
+                using Classes = PersistentDisjointSet<interned_string>;
+                /// Type bindings included in this environment (from class root)
+                using Bindings = PersistentMap<interned_string, BoundType>;
+
+                /// Sets of equivalent type variables, stored by name
+                Classes* classes;
+                /// Bindings from roots of equivalence classes to type binding information. 
+                /// All roots have a binding so that the list of classes can be reconstituted, though these 
+                /// may be null.
+                Bindings* bindings;
+
+                /// Merges the classes rooted at root1 and root2, returning a pair containing the root and 
+                /// child of the bound class. Does not check for validity of merge.
+                std::pair<interned_string, interned_string> mergeClasses( 
+                        interned_string root1, interned_string root2 );
+
           public:
-                const EqvClass* lookup( const std::string &var ) const;
+                class iterator : public std::iterator<
+                                std::forward_iterator_tag, 
+                                ClassRef, 
+                                std::iterator_traits<Bindings::iterator>::difference_type,
+                                ClassRef,
+                                ClassRef> {
+                        friend TypeEnvironment;
+                        
+                        const TypeEnvironment* env;
+                        Bindings::iterator it;
+
+                        iterator(const TypeEnvironment* e, Bindings::iterator&& i) : env(e), it(std::move(i)) {}
+
+                        ClassRef ref() const { return { env, it->first }; }
+                public:
+                        iterator() = default;
+
+                        reference operator* () { return ref(); }
+                        pointer operator-> () { return ref(); }
+
+                        iterator& operator++ () { ++it; return *this; }
+                        iterator operator++ (int) { iterator tmp = *this; ++(*this); return tmp; }
+
+                        bool operator== (const iterator& o) const { return env == o.env && it == o.it; }
+                        bool operator!= (const iterator& o) const { return !(*this == o); }
+                };
+
+                /// Finds a reference to the class containing `var`, invalid if none such.
+                /// returned root variable will be valid regardless
+                ClassRef lookup( interned_string var ) const;
+                ClassRef lookup( const std::string &var ) const { return lookup( var ); }
+
+                /// Binds a type variable to a type; returns false if fails
+                bool bindVar( TypeInstType* typeInst, Type* bindTo, const TypeDecl::Data& data, 
+                        AssertionSet& need, AssertionSet& have, const OpenVarSet& openVars, 
+                        WidenMode widenMode, const SymTab::Indexer& indexer );
+                
+                /// Binds two type variables together; returns false if fails
+                bool bindVarToVar( TypeInstType* var1, TypeInstType* var2, const TypeDecl::Data& data, 
+                        AssertionSet& need, AssertionSet& have, const OpenVarSet& openVars, 
+                        WidenMode widenMode, const SymTab::Indexer& indexer );
+#if !1
                 void add( const EqvClass &eqvClass );
                 void add( EqvClass &&eqvClass  );
@@ -93 +213 @@
                 template< typename SynTreeClass > int applyFree( SynTreeClass *&type ) const;
                 void makeSubstitution( TypeSubstitution &result ) const;
-                bool isEmpty() const { return env.empty(); }
+#endif
+                bool isEmpty() const { return classes->empty(); }
+#if !1
                 void print( std::ostream &os, Indenter indent = {} ) const;
-                void combine( const TypeEnvironment &second, Type *(*combineFunc)( Type*, Type* ) );
                 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.
                 void addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars );
-
-                typedef std::list< EqvClass >::iterator iterator;
-                iterator begin() { return env.begin(); }
-                iterator end() { return env.end(); }
+#endif
+
+                iterator begin() { return { this, bindings->begin() }; }
+                iterator end() { return { this, bindings->end() }; }
+#if 0
                 typedef std::list< EqvClass >::const_iterator const_iterator;
                 const_iterator begin() const { return env.begin(); }
                 const_iterator end() const { return env.end(); }
-          private:
-                std::list< EqvClass > env;
-                std::list< EqvClass >::iterator internal_lookup( const std::string &var );
-        };
+#endif
+        };
+
+        void ClassRef::update_root() { return root = env->classes->find( root ); }
+
+        template<typename T>
+        T ClassRef::get_vars() const {
+                T vars;
+                env->classes->find_class( root, std::inserter(vars, vars.end()) );
+                return vars;
+        }
+
+        BoundType ClassRef::get_bound() const {
+                return env->bindings->get_or_default( root, BoundType{} );
+        }
+
+#if 0
+        EqvClass ClassRef::get_class() const { return { get_vars(), get_bound() }; }
+#endif
 
         template< typename SynTreeClass >
@@ -129 +268 @@
         }
 
+#if !1
         std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env );
+#endif
 
         PassVisitor<GcTracer> & operator<<( PassVisitor<GcTracer> & gc, const TypeEnvironment & env );

src/ResolvExpr/Unify.cc

@@ -31 +31 @@
 #include "SynTree/Visitor.h"      // for Visitor
 #include "Tuples/Tuples.h"        // for isTtype
-#include "TypeEnvironment.h"      // for EqvClass, AssertionSet, OpenVarSet
+#include "TypeEnvironment.h"      // for ClassRef, AssertionSet, OpenVarSet
 #include "Unify.h"
 #include "typeops.h"              // for flatten, occurs, commonType
@@ -128 +128 @@
                         return typeInst->get_isFtype();
                 } // if
-                return false;
-        }
-
-        bool tyVarCompatible( const TypeDecl::Data & data, Type *type ) {
-                switch ( data.kind ) {
-                  case TypeDecl::Dtype:
-                        // to bind to an object type variable, the type must not be a function type.
-                        // if the type variable is specified to be a complete type then the incoming
-                        // type must also be complete
-                        // xxx - should this also check that type is not a tuple type and that it's not a ttype?
-                        return ! isFtype( type ) && (! data.isComplete || type->isComplete() );
-                  case TypeDecl::Ftype:
-                        return isFtype( type );
-                  case TypeDecl::Ttype:
-                        // ttype unifies with any tuple type
-                        return dynamic_cast< TupleType * >( type ) || Tuples::isTtype( type );
-                } // switch
                 return false;
         }
@@ -525 +508 @@
                 void premutate( TypeInstType * ) { visit_children = false; }
                 Type * postmutate( TypeInstType * typeInst ) {
-                        if ( const EqvClass *eqvClass = tenv.lookup( typeInst->get_name() ) ) {
+                        if ( ClassRef eqvClass = tenv.lookup( typeInst->get_name() ) ) {
                                 // expand ttype parameter into its actual type
-                                if ( eqvClass->data.kind == TypeDecl::Ttype && eqvClass->type ) {
-                                        return eqvClass->type->clone();
+                                BoundType cBound = eqvClass.get_bound();
+                                if ( cBound.data.kind == TypeDecl::Ttype && cBound.type ) {
+                                        return cBound.type->clone();
                                 }
                         }