Changes in / [28f3a19:b21c77a]

Location:

src

Files:

• Common/InternedString.cc (added)
• Common/InternedString.h (added)
• Common/PersistentDisjointSet.h (added)
• Common/PersistentMap.h (added)
• Common/module.mk (modified) (2 diffs)
• GenPoly/Box.cc (modified) (2 diffs)
• ResolvExpr/AdjustExprType.cc (modified) (2 diffs)
• ResolvExpr/AlternativeFinder.cc (modified) (15 diffs)
• ResolvExpr/AlternativeFinder.h (modified) (2 diffs)
• ResolvExpr/CastCost.cc (modified) (2 diffs)
• ResolvExpr/ConversionCost.cc (modified) (4 diffs)
• ResolvExpr/Cost.h (modified) (10 diffs)
• ResolvExpr/Occurs.cc (modified) (4 diffs)
• ResolvExpr/PolyCost.cc (modified) (2 diffs)
• ResolvExpr/PtrsAssignable.cc (modified) (3 diffs)
• ResolvExpr/PtrsCastable.cc (modified) (3 diffs)
• ResolvExpr/ResolvMode.h (added)
• ResolvExpr/Resolver.cc (modified) (7 diffs)
• ResolvExpr/TypeEnvironment.cc (modified) (6 diffs)
• ResolvExpr/TypeEnvironment.h (modified) (7 diffs)
• ResolvExpr/Unify.cc (modified) (2 diffs)

src/Common/module.mk

@@ -10 +10 @@
 ## Author           : Richard C. Bilson
 ## Created On       : Mon Jun  1 17:49:17 2015
-## Last Modified By : Peter A. Buhr
-## Last Modified On : Tue Sep 27 11:06:38 2016
-## Update Count     : 4
+## Last Modified By : Aaron B. Moss
+## Last Modified On : Thu Jun 14 11:15:00 2018
+## Update Count     : 5
 ###############################################################################
 
@@ -20 +20 @@
        Common/GC.cc \
        Common/Assert.cc \
+       Common/InternedString.cc \
        Common/Heap.cc

src/GenPoly/Box.cc

@@ -38 +38 @@
 #include "Lvalue.h"                      // for generalizedLvalue
 #include "Parser/LinkageSpec.h"          // for C, Spec, Cforall, Intrinsic
-#include "ResolvExpr/TypeEnvironment.h"  // for EqvClass
 #include "ResolvExpr/typeops.h"          // for typesCompatible
 #include "ScopedSet.h"                   // for ScopedSet, ScopedSet<>::iter...
@@ -592 +591 @@
                         // pass size/align for type variables
                         for ( TyVarMap::const_iterator tyParm = exprTyVars.begin(); tyParm != exprTyVars.end(); ++tyParm ) {
-                                ResolvExpr::EqvClass eqvClass;
                                 assert( env );
                                 if ( tyParm->second.isComplete ) {

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

@@ -9 +9 @@
 // Author           : Richard C. Bilson
 // Created On       : Sat May 16 23:52:08 2015
-// Last Modified By : Peter A. Buhr
-// Last Modified On : Sat Feb 17 11:19:39 2018
-// Update Count     : 33
+// Last Modified By : Aaron B. Moss
+// Last Modified On : Mon Jun 11 16:40:00 2018
+// Update Count     : 34
 //
 
@@ -19 +19 @@
 #include <iostream>                // for operator<<, cerr, ostream, endl
 #include <iterator>                // for back_insert_iterator, back_inserter
+#include <limits>                  // for numeric_limits<int>::max()
 #include <list>                    // for _List_iterator, list, _List_const_...
 #include <map>                     // for _Rb_tree_iterator, map, _Rb_tree_c...
 #include <memory>                  // for allocator_traits<>::value_type
+#include <tuple>                   // for tuple
 #include <utility>                 // for pair
 #include <vector>                  // for vector
@@ -244 +246 @@
         }
 
-        void AlternativeFinder::find( Expression *expr, bool adjust, bool prune, bool failFast ) {
+        void AlternativeFinder::find( Expression *expr, ResolvMode mode ) {
                 PassVisitor<Finder> finder( *this );
                 expr->accept( finder );
-                if ( failFast && alternatives.empty() ) {
+                if ( mode.failFast && alternatives.empty() ) {
                         PRINT(
                                 std::cerr << "No reasonable alternatives for expression " << expr << std::endl;
@@ -253 +255 @@
                         SemanticError( expr, "No reasonable alternatives for expression " );
                 }
-                if ( prune ) {
+                if ( mode.prune ) {
                         auto oldsize = alternatives.size();
                         PRINT(
@@ -261 +263 @@
                         AltList pruned;
                         pruneAlternatives( alternatives.begin(), alternatives.end(), back_inserter( pruned ) );
-                        if ( failFast && pruned.empty() ) {
+                        if ( mode.failFast && pruned.empty() ) {
                                 std::ostringstream stream;
                                 AltList winners;
@@ -280 +282 @@
                 }
                 // adjust types after pruning so that types substituted by pruneAlternatives are correctly adjusted
-                for ( AltList::iterator i = alternatives.begin(); i != alternatives.end(); ++i ) {
-                        if ( adjust ) {
-                                adjustExprType( i->expr->get_result(), i->env, indexer );
+                if ( mode.adjust ) {
+                        for ( Alternative& i : alternatives ) {
+                                adjustExprType( i.expr->result, i.env, indexer );
                         }
                 }
@@ -294 +296 @@
 
         void AlternativeFinder::findWithAdjustment( Expression *expr ) {
-                find( expr, true );
+                find( expr, ResolvMode::withAdjustment() );
         }
 
         void AlternativeFinder::findWithoutPrune( Expression * expr ) {
-                find( expr, true, false );
+                find( expr, ResolvMode::withoutPrune() );
         }
 
         void AlternativeFinder::maybeFind( Expression * expr ) {
-                find( expr, true, true, false );
+                find( expr, ResolvMode::withoutFailFast() );
         }
 
@@ -452 +454 @@
                 }
 
+                #if 0 // cost of assertions accounted for in function creation
                 for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) {
                         convCost += computeConversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env );
                 }
+                #endif
 
                 return convCost;
@@ -580 +584 @@
         }
 
+        namespace {
+                /// Information required to defer resolution of an expression
+                struct AssertionPack {
+                        SymTab::Indexer::IdData cdata;  ///< Satisfying declaration
+                        Type* adjType;                  ///< Satisfying type
+                        TypeEnvironment env;            ///< Post-unification environment
+                        AssertionSet have;              ///< Post-unification have-set
+                        AssertionSet need;              ///< Post-unification need-set
+                        OpenVarSet openVars;            ///< Post-unification open-var set
+
+                        AssertionPack( const SymTab::Indexer::IdData& cdata, Type* adjType, 
+                                        TypeEnvironment&& env, AssertionSet&& have, AssertionSet&& need, 
+                                        OpenVarSet&& openVars ) 
+                                : cdata(cdata), adjType(adjType), env(std::move(env)), have(std::move(have)), 
+                                  need(std::move(need)), openVars(std::move(openVars)) {}
+                };
+
+                /// List of deferred assertion resolutions for the same type
+                using DeferList = std::vector<AssertionPack>;
+
+                /// Intermediate state for assertion resolution
+                struct AssertionResnState {
+                        using DeferItem = std::tuple<DeclarationWithType*, AssertionSetValue, DeferList>;
+
+                        const Alternative& alt;           ///< Alternative being built from
+                        AssertionSet newNeed;             ///< New assertions found from current assertions
+                        OpenVarSet openVars;              ///< Open variables in current context
+                        std::vector<DeferItem> deferred;  ///< Possible deferred assertion resolutions
+                        const SymTab::Indexer& indexer;   ///< Name lookup
+
+                        AssertionResnState(const Alternative& alt, const OpenVarSet& openVars, 
+                                const SymTab::Indexer& indexer ) 
+                                : alt{alt}, have{}, newNeed{}, openVars{openVars}, indexer{indexer} {}
+                };
+
+                /// Binds a single assertion from a compatible AssertionPack, updating resolution state 
+                /// as appropriate.
+                void bindAssertion( DeclarationWithType* curDecl, AssertionSetValue& assnInfo, 
+                                AssertionResnState& resn, AssertionPack&& match ) {
+                        DeclarationWithType* candidate = match.cdata.id;
+                        
+                        addToIndexer( match.have, resn.indexer );
+                        resn.newNeed.insert( match.need.begin(), match.need.end() );
+                        resn.openVars = std::move(match.openVars);
+                        resn.alt.env = std::move(match.env);
+
+                        assertf( candidate->get_uniqueId(), "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() );
+                        for ( auto& a : match.need ) {
+                                if ( a.second.idChain.empty() ) {
+                                        a.second.idChain = assnInfo.idChain;
+                                        a.second.idChain.push_back( curDecl->get_uniqueId() );
+                                }
+                        }
+
+                        Expression* varExpr = match.cdata.combine( resn.alt.cvtCost );
+                        varExpr->result = match.adjType;
+
+                        // follow the current assertion's ID chain to find the correct set of inferred 
+                        // parameters to add the candidate o (i.e. the set of inferred parameters belonging 
+                        // to the entity which requested the assertion parameter)
+                        InferredParams* inferParams = &resn.alt.expr->inferParams;
+                        for ( UniqueId id : assnInfo.idChain ) {
+                                inferParams = (*inferParams)[ id ].inferParams.get();
+                        }
+
+                        (*inferParams)[ curDecl->get_uniqueId() ] = ParamEntry{
+                                candidate->get_uniqueId(), match.adjType, curDecl->get_type(), varExpr };
+                }
+
+                /// Resolves a single assertion, returning false if no satisfying assertion, binding it 
+                /// if there is exactly one satisfying assertion, or adding to the defer-list if there 
+                /// is more than one
+                bool resolveAssertion( DeclarationWithType* curDecl, AssertionSetValue& assnInfo, 
+                                AssertionResnState& resn ) {
+                        // skip unused assertions
+                        if ( ! assnInfo.isUsed ) return true;
+
+                        // lookup candidates for this assertion
+                        std::list< SymTab::Indexer::IdData > candidates;
+                        decls.lookupId( curDecl->name, candidates );
+
+                        // find the ones that unify with the desired type
+                        DeferList matches;
+                        for ( const auto& cdata : candidates ) {
+                                DeclarationWithType* candidate = cdata.id;
+
+                                // build independent unification context for candidate
+                                AssertionSet have, newNeed;
+                                TypeEnvironment newEnv{ resn.alt.env };
+                                OpenVarSet newOpenVars{ resn.openVars };
+                                Type* adjType = candidate->get_type()->clone();
+                                adjustExprType( adjType, newEnv, resn.indexer );
+                                renameTyVars( adjType );
+
+                                if ( unify( curDecl->get_type(), adjType, newEnv, 
+                                                newNeed, have, newOpenVars, resn.indexer ) ) {
+                                        matches.emplace_back( cdata, adjType, std::move(newEnv), std::move(have), 
+                                                std::move(newNeed), std::move(newOpenVars) );
+                                }
+                        }
+
+                        // Break if no suitable assertion
+                        if ( matches.empty() ) return false;
+
+                        // Defer if too many suitable assertions
+                        if ( matches.size() > 1 ) {
+                                resn.deferred.emplace_back( curDecl, assnInfo, std::move(matches) );
+                                return true;
+                        }
+
+                        // otherwise bind current match in ongoing scope
+                        bindAssertion( curDecl, assnInfo, resn, std::move(matches.front()) );
+
+                        return true;
+                }
+        }
+
         template< typename OutputIterator >
         void AlternativeFinder::Finder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) {
@@ -594 +715 @@
                 // )
                 addToIndexer( have, decls );
+
+                AssertionResnState resn{ newAlt, openVars, indexer };
+
+                // resolve assertions in breadth-first-order up to a limited number of levels deep
+                int level;
+                for ( level = 0; level < recursionLimit; ++level ) {
+                        // make initial pass at matching assertions
+                        for ( auto& assn : need ) {
+                                if ( ! resolveAssertion( assn.first, assn.second, resn ) ) {
+                                        // fail early if any assertion fails to resolve
+                                        return;
+                                }
+                        }
+
+                        // resolve deferred assertions by mutual compatibility and min-cost
+                        if ( ! resn.deferred.empty() ) {
+                                // TODO
+                                assert(false && "TODO: deferred assertions unimplemented");
+
+                                // reset for next round
+                                resn.deferred.clear();
+                        }
+
+                        // quit resolving assertions if done
+                        if ( resn.newNeed.empty() ) break;
+
+                        // otherwise start on next group of recursive assertions
+                        need.swap( resn.newNeed );
+                        resn.newNeed.clear();
+                }
+                if ( level >= recursionLimit ) {
+                        SemanticError( newAlt.expr->location, "Too many recursive assertions" );
+                }
+                
+                // add completed assertion to output
+                *out++ = newAlt;
+
+#if 0           
                 AssertionSet newNeed;
                 PRINT(
@@ -607 +766 @@
 //          *out++ = newAlt;
 //          )
+#endif
         }
 
@@ -640 +800 @@
 
                 ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have,
-                                const OpenVarSet& openVars)
-                        : parent(0), expr(nullptr), cost(Cost::zero), env(env), need(need), have(have),
+                                const OpenVarSet& openVars, Cost initCost = Cost::zero)
+                        : parent(0), expr(nullptr), cost(initCost), env(env), need(need), have(have),
                           openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {}
 
@@ -933 +1093 @@
         }
 
+        namespace {
+
+                struct CountSpecs : public WithVisitorRef<CountSpecs>, WithShortCircuiting {
+
+                        void postvisit(PointerType*) {
+                                // mark specialization of base type
+                                if ( count >= 0 ) ++count;
+                        }
+
+                        void postvisit(ArrayType*) {
+                                // mark specialization of base type
+                                if ( count >= 0 ) ++count;
+                        }
+
+                        void postvisit(ReferenceType*) {
+                                // mark specialization of base type -- xxx maybe not?
+                                if ( count >= 0 ) ++count;
+                        }
+
+                private:
+                        // takes minimum non-negative count over parameter/return list
+                        void takeminover( int& mincount, std::list<DeclarationWithType*>& dwts ) {
+                                for ( DeclarationWithType* dwt : dwts ) {
+                                        count = -1;
+                                        maybeAccept( dwt->get_type(), *visitor );
+                                        if ( count != -1 && count < mincount ) mincount = count;
+                                }
+                        }
+
+                public:
+                        void previsit(FunctionType*) {
+                                // override default child visiting behaviour
+                                visit_children = false;
+                        }
+
+                        void postvisit(FunctionType* fty) {
+                                // take minimal set value of count over ->returnVals and ->parameters
+                                int mincount = std::numeric_limits<int>::max();
+                                takeminover( mincount, fty->parameters );
+                                takeminover( mincount, fty->returnVals );
+                                // add another level to mincount if set
+                                count = mincount < std::numeric_limits<int>::max() ? mincount + 1 : -1;
+                        }
+
+                private:
+                        // returns minimum non-negative count + 1 over type parameters (-1 if none such)
+                        int minover( std::list<Expression*>& parms ) {
+                                int mincount = std::numeric_limits<int>::max();
+                                for ( Expression* parm : parms ) {
+                                        count = -1;
+                                        maybeAccept( parm->get_result(), *visitor );
+                                        if ( count != -1 && count < mincount ) mincount = count;
+                                }
+                                return mincount < std::numeric_limits<int>::max() ? mincount + 1 : -1;
+                        }
+                        
+                public:
+                        void previsit(StructInstType*) {
+                                // override default child behaviour
+                                visit_children = false;
+                        }
+
+                        void postvisit(StructInstType* sity) {
+                                // look for polymorphic parameters
+                                count = minover( sity->parameters );
+                        }
+
+                        void previsit(UnionInstType*) {
+                                // override default child behaviour
+                                visit_children = false;
+                        }
+
+                        void postvisit(UnionInstType* uity) {
+                                // look for polymorphic parameters
+                                count = minover( uity->parameters );
+                        }
+
+                        void postvisit(TypeInstType*) {
+                                // note polymorphic type (which may be specialized)
+                                // xxx - maybe account for open/closed type variables
+                                count = 0;
+                        }
+
+                        void previsit(TupleType*) {
+                                // override default child behaviour
+                                visit_children = false;
+                        }
+
+                        void postvisit(TupleType* tty) {
+                                // take minimum non-negative count
+                                int mincount = std::numeric_limits<int>::max();
+                                for ( Type* ty : tty->types ) {
+                                        count = -1;
+                                        maybeAccept( ty, *visitor );
+                                        if ( count != -1 && count < mincount ) mincount = count;
+                                }
+                                // xxx - maybe don't increment, tuple flattening doesn't necessarily specialize
+                                count = mincount < std::numeric_limits<int>::max() ? mincount + 1: -1;
+                        }
+
+                        int get_count() const { return count >= 0 ? count : 0; }
+                private:
+                        int count = -1;
+                };
+
+                /// Counts the specializations in the types in a function parameter or return list
+                int countSpecs( std::list<DeclarationWithType*>& dwts ) {
+                        int k = 0;
+                        for ( DeclarationWithType* dwt : dwts ) {
+                                PassVisitor<CountSpecs> counter;
+                                maybeAccept( dwt->get_type(), *counter.pass.visitor );
+                                k += counter.pass.get_count();
+                        }
+                        return k;
+                }
+
+                /// Calculates the inherent costs in a function declaration; varCost for the number of 
+                /// type variables and specCost for type assertions, as well as PolyType specializations 
+                /// in the parameter and return lists.
+                Cost declCost( FunctionType* funcType ) {
+                        Cost k = Cost::zero;
+
+                        // add cost of type variables
+                        k.incVar( funcType->forall.size() );
+
+                        // subtract cost of type assertions
+                        for ( TypeDecl* td : funcType->forall ) {
+                                k.decSpec( td->assertions.size() );
+                        }
+
+                        // count specialized polymorphic types in parameter/return lists
+                        k.decSpec( countSpecs( funcType->parameters ) );
+                        k.decSpec( countSpecs( funcType->returnVals ) );
+
+                        return k;
+                }
+        }
+
         template<typename OutputIterator>
         void AlternativeFinder::Finder::validateFunctionAlternative( const Alternative &func, 
@@ -977 +1275 @@
                 }
 
+                // calculate declaration cost of function (+vars-spec)
+                Cost funcCost = declCost( funcType );
+
                 // iteratively build matches, one parameter at a time
                 std::vector<ArgPack> results;
-                results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } );
+                results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars, funcCost } );
                 std::size_t genStart = 0;
 
@@ -1120 +1421 @@
                                         }
                                 } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->result->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer)
-                                        if ( const EqvClass *eqvClass = func->env.lookup( typeInst->name ) ) {
-                                                if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass->type ) ) {
+                                        if ( ClassRef eqvClass = func->env.lookup( typeInst->name ) ) {
+                                                if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.get_bound().type ) ) {
                                                         Alternative newFunc( *func );
                                                         referenceToRvalueConversion( newFunc.expr, newFunc.cost );

src/ResolvExpr/AlternativeFinder.h

@@ -22 +22 @@
 #include "Alternative.h"                 // for AltList, Alternative
 #include "ExplodedActual.h"              // for ExplodedActual
+#include "ResolvMode.h"                  // for ResolvMode
 #include "ResolvExpr/Cost.h"             // for Cost, Cost::infinity
 #include "ResolvExpr/TypeEnvironment.h"  // for AssertionSet, OpenVarSet
@@ -68 +69 @@
                 }
 
-                void find( Expression *expr, bool adjust = false, bool prune = true, bool failFast = true );
+                void find( Expression *expr, ResolvMode mode = ResolvMode{} );
                 /// Calls find with the adjust flag set; adjustment turns array and function types into equivalent pointer types
                 void findWithAdjustment( Expression *expr );

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
@@ -29 +29 @@
 
 namespace ResolvExpr {
-        const Cost Cost::zero =      Cost(  0,  0,  0,  0 );
-        const Cost Cost::infinity =  Cost( -1, -1, -1, -1 );
-        const Cost Cost::unsafe =    Cost(  1,  0,  0,  0 );
-        const Cost Cost::poly =      Cost(  0,  1,  0,  0 );
-        const Cost Cost::safe =      Cost(  0,  0,  1,  0 );
-        const Cost Cost::reference = Cost(  0,  0,  0,  1 );
+        const Cost Cost::zero =      Cost{  0,  0,  0,  0,  0,  0 };
+        const Cost Cost::infinity =  Cost{ -1, -1, -1,  1, -1, -1 };
+        const Cost Cost::unsafe =    Cost{  1,  0,  0,  0,  0,  0 };
+        const Cost Cost::poly =      Cost{  0,  1,  0,  0,  0,  0 };
+        const Cost Cost::var =       Cost{  0,  0,  1,  0,  0,  0 };
+        const Cost Cost::spec =      Cost{  0,  0,  0, -1,  0,  0 };
+        const Cost Cost::safe =      Cost{  0,  0,  0,  0,  1,  0 };
+        const Cost Cost::reference = Cost{  0,  0,  0,  0,  0,  1 };
 
 #if 0
@@ -44 +46 @@
                 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;
@@ -368 +370 @@
 
         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/Cost.h

@@ -9 +9 @@
 // Author           : Richard C. Bilson
 // Created On       : Sun May 17 09:39:50 2015
-// Last Modified By : Peter A. Buhr
-// Last Modified On : Sat Jul 22 09:35:55 2017
-// Update Count     : 5
+// Last Modified By : Aaron B. Moss
+// Last Modified On : Mon Jun 11 16:04:00 2018
+// Update Count     : 6
 //
 
@@ -21 +21 @@
         class Cost {
           private:
-                Cost( int unsafeCost, int polyCost, int safeCost, int referenceCost );
+                Cost( int unsafeCost, int polyCost, int varCost, int specCost, int safeCost, int referenceCost );
 
           public:
                 Cost & incUnsafe( int inc = 1 );
                 Cost & incPoly( int inc = 1 );
+                Cost & incVar( int inc = 1 );
+                Cost & decSpec( int dec = 1 );
                 Cost & incSafe( int inc = 1 );
                 Cost & incReference( int inc = 1 );
@@ -31 +33 @@
                 int get_unsafeCost() const { return unsafeCost; }
                 int get_polyCost() const { return polyCost; }
+                int get_varCost() const { return varCost; }
+                int get_specCost() const { return specCost; }
                 int get_safeCost() const { return safeCost; }
                 int get_referenceCost() const { return referenceCost; }
@@ -47 +51 @@
                 static const Cost unsafe;
                 static const Cost poly;
+                static const Cost var;
+                static const Cost spec;
                 static const Cost safe;
                 static const Cost reference;
           private:
-                int compare( const Cost &other ) const;
 
-                int unsafeCost;
-                int polyCost;
-                int safeCost;
-                int referenceCost;
+                int unsafeCost;     ///< Unsafe (narrowing) conversions
+                int polyCost;       ///< Count of parameters and return values bound to some poly type
+                int varCost;        ///< Count of polymorphic type variables
+                int specCost;       ///< Polymorphic type specializations (type assertions), negative cost
+                int safeCost;       ///< Safe (widening) conversions
+                int referenceCost;  ///< reference conversions
         };
 
-        inline Cost::Cost( int unsafeCost, int polyCost, int safeCost, int referenceCost ) : unsafeCost( unsafeCost ), polyCost( polyCost ), safeCost( safeCost ), referenceCost( referenceCost ) {}
+        inline Cost::Cost( 
+                int unsafeCost, int polyCost, int varCost, int specCost, int safeCost, int referenceCost ) : unsafeCost( unsafeCost ), polyCost( polyCost ), varCost( varCost ), specCost( specCost ), 
+                  safeCost( safeCost ), referenceCost( referenceCost ) {}
 
         inline Cost & Cost::incUnsafe( int inc ) {
@@ -69 +78 @@
                 if ( *this == infinity ) return *this;
                 polyCost += inc;
+                return *this;
+        }
+
+        inline Cost & Cost::incVar( int inc ) {
+                if ( *this == infinity ) return *this;
+                varCost += inc;
+                return *this;
+        }
+
+        inline Cost& Cost::decSpec( int dec ) {
+                if ( *this == infinity ) return *this;
+                specCost -= dec;
                 return *this;
         }
@@ -86 +107 @@
         inline Cost Cost::operator+( const Cost &other ) const {
                 if ( *this == infinity || other == infinity ) return infinity;
-                return Cost( unsafeCost + other.unsafeCost, polyCost + other.polyCost, safeCost + other.safeCost, referenceCost + other.referenceCost );
+                return Cost( 
+                        unsafeCost + other.unsafeCost, polyCost + other.polyCost, 
+                        varCost + other.varCost, specCost + other.specCost, 
+                        safeCost + other.safeCost, referenceCost + other.referenceCost );
         }
 
         inline Cost Cost::operator-( const Cost &other ) const {
                 if ( *this == infinity || other == infinity ) return infinity;
-                return Cost( unsafeCost - other.unsafeCost, polyCost - other.polyCost, safeCost - other.safeCost, referenceCost - other.referenceCost );
+                return Cost( 
+                        unsafeCost - other.unsafeCost, polyCost - other.polyCost, 
+                        varCost + other.varCost, specCost + other.specCost, 
+                        safeCost - other.safeCost, referenceCost - other.referenceCost );
         }
 
@@ -102 +129 @@
                 unsafeCost += other.unsafeCost;
                 polyCost += other.polyCost;
+                varCost += other.varCost;
+                specCost += other.specCost;
                 safeCost += other.safeCost;
                 referenceCost += other.referenceCost;
@@ -119 +148 @@
                 } else if ( polyCost < other.polyCost ) {
                         return true;
+                } else if ( varCost > other.varCost ) {
+                        return false;
+                } else if ( varCost < other.varCost ) {
+                        return true;
+                } else if ( specCost > other.specCost ) {
+                        return false;
+                } else if ( specCost < other.specCost ) {
+                        return true;
                 } else if ( safeCost > other.safeCost ) {
                         return false;
@@ -135 +172 @@
                 return unsafeCost == other.unsafeCost
                         && polyCost == other.polyCost
+                        && varCost == other.varCost
+                        && specCost == other.specCost
                         && safeCost == other.safeCost
                         && referenceCost == other.referenceCost;
@@ -144 +183 @@
 
         inline std::ostream &operator<<( std::ostream &os, const Cost &cost ) {
-                os << "( " << cost.unsafeCost << ", " << cost.polyCost << ", " << cost.safeCost << ", " << cost.referenceCost << " )";
-                return os;
+                return os << "( " << cost.unsafeCost << ", " << cost.polyCost << ", " 
+                          << cost.varCost << ", " << cost.specCost << ", "
+                          << cost.safeCost << ", " << cost.referenceCost << " )";
         }
 } // namespace ResolvExpr

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/Resolver.cc

@@ -33 +33 @@
 #include "ResolveTypeof.h"               // for resolveTypeof
 #include "Resolver.h"
+#include "ResolvMode.h"                  // for ResolvMode
 #include "SymTab/Autogen.h"              // for SizeType
 #include "SymTab/Indexer.h"              // for Indexer
@@ -50 +51 @@
 namespace ResolvExpr {
         struct Resolver final : public WithIndexer, public WithGuards, public WithVisitorRef<Resolver>, public WithShortCircuiting, public WithStmtsToAdd {
+        
+        friend void resolve( std::list<Declaration*> );
+
                 Resolver() {}
                 Resolver( const SymTab::Indexer & other ) {
@@ -95 +99 @@
                 CurrentObject currentObject = nullptr;
                 bool inEnumDecl = false;
+                bool atTopLevel = false;  ///< Was this resolver set up at the top level of resolution
         };
 
         void resolve( std::list< Declaration * > translationUnit ) {
                 PassVisitor<Resolver> resolver;
+                resolver.pass.atTopLevel = true;  // mark resolver as top-level
                 acceptAll( translationUnit, resolver );
         }
@@ -165 +171 @@
 
         namespace {
-                void findUnfinishedKindExpression(Expression * untyped, Alternative & alt, const SymTab::Indexer & indexer, const std::string & kindStr, std::function<bool(const Alternative &)> pred, bool adjust = false, bool prune = true, bool failFast = true) {
+                void findUnfinishedKindExpression( Expression * untyped, Alternative & alt, const SymTab::Indexer & indexer, const std::string & kindStr, std::function<bool(const Alternative &)> pred, ResolvMode mode = ResolvMode{} ) {
                         assertf( untyped, "expected a non-null expression." );
 
@@ -172 +178 @@
                         TypeEnvironment env;
                         AlternativeFinder finder( indexer, env );
-                        finder.find( untyped, adjust, prune, failFast );
+                        finder.find( untyped, mode );
 
                         #if 0
@@ -218 +224 @@
 
                 /// resolve `untyped` to the expression whose alternative satisfies `pred` with the lowest cost; kindStr is used for providing better error messages
-                void findKindExpression(Expression *& untyped, const SymTab::Indexer & indexer, const std::string & kindStr, std::function<bool(const Alternative &)> pred, bool adjust = false, bool prune = true, bool failFast = true) {
+                void findKindExpression(Expression *& untyped, const SymTab::Indexer & indexer, const std::string & kindStr, std::function<bool(const Alternative &)> pred, ResolvMode mode = ResolvMode{}) {
                         if ( ! untyped ) return;
                         Alternative choice;
-                        findUnfinishedKindExpression( untyped, choice, indexer, kindStr, pred, adjust, prune, failFast );
+                        findUnfinishedKindExpression( untyped, choice, indexer, kindStr, pred, mode );
                         finishExpr( choice.expr, choice.env, untyped->env );
                         untyped = choice.expr;
@@ -250 +256 @@
                 // set up and resolve expression cast to void
                 Alternative choice;
-                findUnfinishedKindExpression( untyped, choice, indexer, "", standardAlternativeFilter, true );
+                findUnfinishedKindExpression( untyped, choice, indexer, "", standardAlternativeFilter, ResolvMode::withAdjustment() );
                 CastExpr * castExpr = strict_dynamic_cast< CastExpr * >( choice.expr );
                 env = std::move( choice.env );

src/ResolvExpr/TypeEnvironment.cc

@@ -7 +7 @@
 // TypeEnvironment.cc --
 //
-// Author           : Richard C. Bilson
+// Author           : Aaron B. Moss
 // Created On       : Sun May 17 12:19:47 2015
 // Last Modified By : Aaron B. Moss
-// Last Modified On : Mon Jun 18 11:58:00 2018
-// Update Count     : 4
+// Last Modified On : Fri Jun 29 15:51:00 2018
+// Update Count     : 5
 //
 
@@ -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 "Tuples/Tuples.h"             // for isTtype
 #include "TypeEnvironment.h"
 #include "typeops.h"                   // for occurs
@@ -48 +49 @@
         }
 
+#if 0
         void EqvClass::initialize( const EqvClass &src, EqvClass &dest ) {
                 initialize( src, dest, src.type );
@@ -115 +117 @@
                 return nullptr;
         }
-
-        /// Removes any class from env that intersects eqvClass
-        void filterOverlappingClasses( std::list<EqvClass> &env, const EqvClass &eqvClass ) {
-                for ( auto i = env.begin(); i != env.end(); ) {
-                        auto next = i;
-                        ++next;
-                        std::set<std::string> 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) );
-                } // for
-        }
-
-        void TypeEnvironment::add( const TypeSubstitution & sub ) {
-                EqvClass newClass;
-                for ( auto p : sub ) {
-                        newClass.vars.insert( p.first );
-                        newClass.type = p.second->clone();
-                        newClass.allowWidening = false;
-                        // 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) );
-                }
-        }
-
-        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
-                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() );
-        }
-
-        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
-        }
-
-        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) );
-                }
+#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 };
         }
 
@@ -233 +165 @@
         }
 
-        bool TypeEnvironment::bindVar( TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
-                
+        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();
-                OpenVarSet::const_iterator tyvar = openVars.find( typeInst->get_name() );
-                assert( tyvar != openVars.end() );
-                if ( ! tyVarCompatible( tyvar->second, bindTo ) ) {
-                        return false;
-                } // if
-                if ( occurs( bindTo, typeInst->get_name(), *this ) ) {
-                        return false;
-                } // if
-                auto curClass = internal_lookup( typeInst->get_name() );
-                if ( curClass != env.end() ) {
-                        if ( curClass->type ) {
-                                Type *common = 0;
-                                // attempt to unify equivalence class type (which has qualifiers stripped, so they must be restored) with the type to bind to
-                                Type *newType = curClass->type->clone();
+                
+                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( curClass->allowWidening, true ), indexer, common ) ) {
+                                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{};
-                                                curClass->set_type( common );
-                                        } // if
+                                                curData.type = common;
+                                                bindings = bindings->set( curClass.update_root(), curData );
+                                        }
+                                        return true;
                                 } else return false;
                         } else {
-                                Type* newType = bindTo->clone();
-                                newType->get_qualifiers() = Type::Qualifiers{};
-                                curClass->set_type( newType );
-                                curClass->allowWidening = widenMode.widenFirst && widenMode.widenSecond;
-                        } // if
+                                // 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 {
-                        EqvClass newClass;
-                        newClass.vars.insert( typeInst->get_name() );
-                        newClass.type = bindTo->clone();
-                        newClass.type->get_qualifiers() = Type::Qualifiers();
-                        newClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond;
-                        newClass.data = data;
-                        env.push_back( std::move(newClass) );
-                } // if
+                        // 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 ) {
-
-                auto class1 = internal_lookup( var1->get_name() );
-                auto class2 = internal_lookup( var2->get_name() );
+        
+        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 != env.end() && class1 == class2 ) {
-                        class1->allowWidening &= widenMode;
+                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;
                 }
 
-                bool widen1 = false, widen2 = false;
-                const Type *type1 = nullptr, *type2 = nullptr;
-
-                // check for existing bindings, perform occurs check
-                if ( class1 != env.end() ) {
-                        if ( class1->type ) {
-                                if ( occurs( class1->type, var2->get_name(), *this ) ) return false;
-                                type1 = class1->type;
-                        } // if
-                        widen1 = widenMode.widenFirst && class1->allowWidening;
-                } // if
-                if ( class2 != env.end() ) {
-                        if ( class2->type ) {
-                                if ( occurs( class2->type, var1->get_name(), *this ) ) return false;
-                                type2 = class2->type;
-                        } // if
-                        widen2 = widenMode.widenSecond && class2->allowWidening;
-                } // if
-
-                if ( type1 && type2 ) {
-                        // both classes bound, merge if bound types can be unified
-                        Type *newType1 = type1->clone(), *newType2 = type2->clone();
-                        WidenMode newWidenMode{ widen1, widen2 };
-                        Type *common = 0;
-                        if ( unifyInexact( newType1, newType2, *this, need, have, openVars, newWidenMode, indexer, common ) ) {
-                                class1->vars.insert( class2->vars.begin(), class2->vars.end() );
-                                class1->allowWidening = widen1 && widen2;
+                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{};
-                                        class1->set_type( common );
+                                        data1.type = common;
                                 }
-                                env.erase( class2 );
+                                bindings = bindings->set( root, data1 );
                         } else return false;
-                } else if ( class1 != env.end() && class2 != env.end() ) {
-                        // both classes exist, at least one unbound, merge unconditionally
-                        if ( type1 ) {
-                                class1->vars.insert( class2->vars.begin(), class2->vars.end() );
-                                class1->allowWidening = widen1;
-                                env.erase( class2 );
-                        } else {
-                                class2->vars.insert( class1->vars.begin(), class1->vars.end() );
-                                class2->allowWidening = widen2;
-                                env.erase( class1 );
-                        } // if
-                } else if ( class1 != env.end() ) {
-                        // var2 unbound, add to class1
-                        class1->vars.insert( var2->get_name() );
-                        class1->allowWidening = widen1;
-                } else if ( class2 != env.end() ) {
-                        // var1 unbound, add to class2
-                        class2->vars.insert( var1->get_name() );
-                        class2->allowWidening = widen2;
+                } 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 {
-                        // neither var bound, create new class
+                        // 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 ) {
+                for ( auto i = env.begin(); i != env.end(); ) {
+                        auto next = i;
+                        ++next;
+                        std::set<std::string> 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( var1->get_name() );
-                        newClass.vars.insert( var2->get_name() );
-                        newClass.allowWidening = widen1 && widen2;
-                        newClass.data = data;
+                        newClass.vars.insert( (*i)->get_name() );
+                        newClass.data = TypeDecl::Data{ (*i) };
                         env.push_back( std::move(newClass) );
-                } // if
-                return true;
-        }
-
-        void TypeEnvironment::forbidWidening() {
-                for ( EqvClass& c : env ) c.allowWidening = false;
+                } // for
+        }
+
+        void TypeEnvironment::add( const TypeSubstitution & sub ) {
+                EqvClass newClass;
+                for ( auto p : sub ) {
+                        newClass.vars.insert( p.first );
+                        newClass.type = p.second->clone();
+                        newClass.allowWidening = false;
+                        // 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) );
+                }
+        }
+
+        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
+                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() );
+        }
+
+        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
+        }
+
+        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) );
+                }
         }
 
@@ -359 +398 @@
                 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 : Aaron B. Moss
-// Last Modified On : Mon Jun 18 11:58:00 2018
-// Update Count     : 4
+// Last Modified On : Fri Jun 29 16:00:00 2018
+// Update Count     : 5
 //
 
 #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 <utility>                     // for move, swap
+#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 "WidenMode.h"                 // for WidenMode
 
-#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 "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 {
@@ -43 +48 @@
         // 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 {
@@ -62 +69 @@
         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;
         };
@@ -73 +81 @@
         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;
@@ -92 +109 @@
                 void set_type(Type* ty);
         };
+#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;
-          private:
-                void add( EqvClass &&eqvClass  );
-          public:
+                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
+        private:
+                void add( EqvClass &&eqvClass );
+        public:
                 void add( const Type::ForallList &tyDecls );
                 void add( const TypeSubstitution & sub );
@@ -104 +222 @@
                 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 );
 
-                /// Binds the type class represented by `typeInst` to the type `bindTo`; will add 
-                /// the class if needed. Returns false on failure.
-                bool bindVar( TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
-                
-                /// Binds the type classes represented by `var1` and `var2` together; will add 
-                /// one or both classes if needed. Returns false on failure.
-                bool bindVarToVar( TypeInstType *var1, TypeInstType *var2, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
-
                 /// Disallows widening for all bindings in the environment
                 void forbidWidening();
-
-                using iterator = std::list< EqvClass >::const_iterator;
-                iterator begin() const { return env.begin(); }
-                iterator end() const { return env.end(); }
-
-          private:
-                std::list< EqvClass > env;
-                
-                std::list< EqvClass >::iterator internal_lookup( const std::string &var );
-        };
+#endif
+
+                iterator begin() { return { this, bindings->begin() }; }
+                iterator end() { return { this, bindings->end() }; }
+        };
+
+        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 >
@@ -150 +275 @@
         }
 
+#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
@@ -377 +377 @@
                 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();
                                 }
                         }