Index: src/ResolvExpr/TypeEnvironment.cc
===================================================================
--- src/ResolvExpr/TypeEnvironment.cc	(revision 5c140301192225f6a3f669eb918000f25962a75e)
+++ src/ResolvExpr/TypeEnvironment.cc	(revision d318a182b0b2491a1aa64771c523470334852f01)
@@ -33,4 +33,66 @@
 
 namespace ResolvExpr {
+	#if 1
+	#define PRE_POST_VALIDATE auto dbg = ValidateGuard{this, __func__};
+	#define PRE_POST_VALIDATE_NOM auto dbg = ValidateGuard{this};
+	struct ValidateGuard {
+		const TypeEnvironment* env;
+		const TypeEnvironment::Classes* old_classes;
+		const TypeEnvironment::Bindings* old_bindings;
+		const char* last_fn;
+
+		void validate_classes( const TypeEnvironment::Classes* c ) {
+			typedef TypeEnvironment::Classes C;
+
+			assertf( c != nullptr, "classes non-null" );
+			
+			C::Mode cmode = c->get_mode();
+			if ( cmode == C::BASE ) {
+				// xxx - consistency checks
+			} else {
+				assertf( cmode == C::ADD || cmode == C::REM || cmode == C::ADDTO || cmode == C::REMFROM, "valid classes mode" );
+				validate_classes( c->get_base() );
+			}
+		}
+
+		void validate_bindings( const TypeEnvironment::Bindings* b ) {
+			typedef TypeEnvironment::Bindings B;
+
+			assertf( b != nullptr, "bindings non-null" );
+
+			B::Mode bmode = b->get_mode();
+			if ( bmode == B::BASE ) {
+				// xxx - consistency checks
+			} else {
+				assertf( bmode == B::REM || bmode == B::INS || bmode == B::UPD, "valid bindings mode" );
+				validate_bindings( b->get_base() );
+			}
+		}
+
+		void validate_env() {
+			validate_classes( env->classes );
+			validate_bindings( env->bindings );
+			
+			// xxx - joint validation
+		}
+
+		ValidateGuard(const TypeEnvironment* e)
+			: env{e}, old_classes{e->classes}, old_bindings{e->bindings}, last_fn{e->last_fn}
+			{ validate_env(); }
+		ValidateGuard(const TypeEnvironment* e, const char* fn)
+			: env{e}, old_classes{e->classes}, old_bindings{e->bindings}, last_fn{fn} 
+			{ validate_env(); }
+		~ValidateGuard() {
+			validate_env();
+			if ( env->classes != old_classes ) validate_classes( old_classes );
+			if ( env->bindings != old_bindings ) validate_bindings( old_bindings );
+			const_cast<TypeEnvironment*>(env)->last_fn = last_fn;
+		}
+	};
+	#else
+	#define PRE_POST_VALIDATE
+	#define PRE_POST_VALIDATE_NOM
+	#endif
+
 	void printAssertionSet( const AssertionSet &assertions, std::ostream &os, int indent ) {
 		for ( AssertionSet::const_iterator i = assertions.begin(); i != assertions.end(); ++i ) {
@@ -53,4 +115,5 @@
 	std::pair<interned_string, interned_string> TypeEnvironment::mergeClasses( 
 			interned_string root1, interned_string root2 ) {
+		PRE_POST_VALIDATE
 		// merge classes
 		Classes* newClasses = classes->merge( root1, root2 );
@@ -100,4 +163,5 @@
 			const TypeDecl::Data& data, AssertionSet& need, AssertionSet& have, 
 			const OpenVarSet& openVars, WidenMode widenMode, const SymTab::Indexer& indexer ) {
+		PRE_POST_VALIDATE
 		// remove references from other, so that type variables can only bind to value types
 		bindTo = bindTo->stripReferences();
@@ -148,4 +212,5 @@
 			const TypeDecl::Data& data, AssertionSet& need, AssertionSet& have, 
 			const OpenVarSet& openVars, WidenMode widenMode, const SymTab::Indexer& indexer ) {
+		PRE_POST_VALIDATE
 		ClassRef class1 = lookup( var1->get_name() );
 		ClassRef class2 = lookup( var2->get_name() );
@@ -237,4 +302,5 @@
 
 	void TypeEnvironment::add( const Type::ForallList &tyDecls ) {
+		PRE_POST_VALIDATE
 		for ( Type::ForallList::const_iterator i = tyDecls.begin(); i != tyDecls.end(); ++i ) {
 			interned_string name = (*i)->get_name();
@@ -245,4 +311,5 @@
 
 	void TypeEnvironment::add( const TypeSubstitution & sub ) {
+		PRE_POST_VALIDATE
 		interned_string not_found{nullptr};
 
@@ -251,5 +318,5 @@
 			
 			// filter overlapping classes out of existing environment
-			// (this is a very shady assumption, but has worked for a long time...)
+			// xxx - this is a very shady assumption, but has worked for a long time...
 			interned_string root = classes->find_or_default( var, not_found );
 			if ( root != not_found ) {
@@ -270,4 +337,5 @@
 
 	void TypeEnvironment::makeSubstitution( TypeSubstitution &sub ) const {
+		PRE_POST_VALIDATE_NOM
 		bindings->for_each([&]( interned_string root, const BoundType& bound ){
 			classes->for_class(root, [&]( interned_string var ) {
@@ -300,15 +368,42 @@
 	}
 
+	namespace {
+		// temporary representation of an equivalence class
+		struct EqvClass {
+			std::vector<interned_string> vars;
+			BoundType bound;
+
+			EqvClass() = default;
+			EqvClass(const BoundType& b) : bound{b} {}
+		};
+	}
+
 	void TypeEnvironment::simpleCombine( const TypeEnvironment &o ) {
+		PRE_POST_VALIDATE
+		// check for same environment
+		if ( classes == o.classes && bindings == o.bindings ) return;
+
+		// read out equivalence classes (avoids conflicting reroots)
+		std::vector<EqvClass> ecs;
 		o.bindings->for_each( [&]( interned_string root, const BoundType& bound ) {
-			// add members of new class
+			ecs.emplace_back(bound);
+			o.classes->for_class( root, [&]( interned_string var ) {
+				ecs.back().vars.push_back( var );
+			} );
+		} );
+
+		// read equivalence classes into self
+		for ( EqvClass& ec : ecs ) {
+			// merge vars
 			interned_string new_root{nullptr};
-			o.classes->for_class( root, [this,&new_root]( interned_string var ) {
-				classes = classes->add( var );
+			for ( interned_string var : ec.vars ) {
+				Classes* new_classes = classes->add( var );
+				if ( new_classes == classes ) { var = classes->find( var ); }
+				else { classes = new_classes; }
 				new_root = new_root ? mergeClasses( new_root, var ).first : var;
-			});
-			// set binding for new class
-			bindings = bindings->set( new_root, bound );
-		});
+			}
+			// set binding
+			bindings = bindings->set( new_root, ec.bound );
+		}
 	}
 
@@ -322,19 +417,42 @@
 
 	void TypeEnvironment::addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars ) {
+		PRE_POST_VALIDATE
+		if ( classes == actualEnv.classes && bindings == actualEnv.bindings ) {
+			// actualEnv already the same, just need to update openVars
+			extractOpenVars( openVars );
+			return;
+		} else assertf(classes != actualEnv.classes && bindings != actualEnv.bindings, "classes & bindings updated together");
+
+		// read out equivalence classes (avoids conflicting reroots)
+		std::vector<EqvClass> ecs;
 		actualEnv.bindings->for_each( [&]( interned_string root, const BoundType& bound ) {
-			// add members of new class, setting openVars concurrently
+			ecs.emplace_back(bound);
+			actualEnv.classes->for_class( root, [&]( interned_string var ) {
+				ecs.back().vars.push_back( var );
+			} );
+		} );
+
+		// add members of new class, setting openVars concurrently
+		for ( EqvClass& ec : ecs ) {
+			// merge vars
 			interned_string new_root{nullptr};
-			actualEnv.classes->for_class( root, [&]( interned_string var ) {
-				classes = classes->add( var );
+			for ( interned_string var : ec.vars ) {
+				openVars[ var ] = ec.bound.data;
+				Classes* new_classes = classes->add( var );
+				if ( new_classes == classes ) {
+					// xxx - this case is a bit sketchy, but has been working
+					// xxx - merging the classes is a departure from previous behaviour
+					var = classes->find( var );
+				} else { classes = new_classes; }
 				new_root = new_root ? mergeClasses( new_root, var ).first : var;
-				openVars[ var ] = bound.data;
-			} );
-			// add new type binding without widening
+			}
+			// set binding without widening
 			bindings = bindings->set( new_root, 
-				BoundType{ maybeClone(bound.type), false, bound.data } );
-		} );
+				BoundType{ maybeClone(ec.bound.type), false, ec.bound.data } );
+		}
 	}
 
 	void TypeEnvironment::forbidWidening() {
+		PRE_POST_VALIDATE
 		bindings = bindings->mutate_each([]( const interned_string&, BoundType& c ) {
 			if ( c.allowWidening ) {
@@ -352,7 +470,8 @@
 
 	PassVisitor<GcTracer> & operator<<( PassVisitor<GcTracer> & gc, const TypeEnvironment & env ) {
-		for ( ClassRef c : env ) {
-			maybeAccept( c.get_bound().type, gc );
-		}
+		gc.pass.visit( env );
+		// for ( ClassRef c : env ) {
+		// 	maybeAccept( c.get_bound().type, gc );
+		// }
 		return gc;
 	}
Index: src/ResolvExpr/TypeEnvironment.h
===================================================================
--- src/ResolvExpr/TypeEnvironment.h	(revision 5c140301192225f6a3f669eb918000f25962a75e)
+++ src/ResolvExpr/TypeEnvironment.h	(revision d318a182b0b2491a1aa64771c523470334852f01)
@@ -138,7 +138,10 @@
 	};
 
+	class ValidateGuard;
+
 	class TypeEnvironment {
 		friend ClassRef;
-
+		friend GcTracer;
+		
 		/// Backing storage for equivalence classes
 		using Classes = PersistentDisjointSet<interned_string>;
@@ -152,4 +155,8 @@
 		/// may be null.
 		Bindings* bindings;
+
+		// for debugging
+		friend ValidateGuard;
+		const char* last_fn = "<none>";
 
 		/// Merges the classes rooted at root1 and root2, returning a pair containing the root and 
@@ -234,5 +241,4 @@
 	T ClassRef::get_vars() const {
 		T vars;
-		if ( ! env->classes->count( root ) ) return vars;
 		env->classes->for_class( root, [&vars]( interned_string var ) {
 			vars.insert( vars.end(), var );