Index: src/Common/GC.cc
===================================================================
--- src/Common/GC.cc	(revision 5c140301192225f6a3f669eb918000f25962a75e)
+++ src/Common/GC.cc	(revision d318a182b0b2491a1aa64771c523470334852f01)
@@ -41,6 +41,5 @@
 
 const GC& GC::operator<< (const GC_Object* obj) const {
-	if( obj )
-	{
+	if( obj ) {
 		if( obj->mark != this->mark ) {
 			obj->mark = this->mark;
@@ -49,4 +48,12 @@
 	}
 	return *this;
+}
+
+bool GC::notrace_mark(const GC_Object* obj) const {
+	if ( obj && obj->mark != this->mark ) {
+		obj->mark = this->mark;
+		return true;
+	}
+	return false;
 }
 
Index: src/Common/GC.h
===================================================================
--- src/Common/GC.h	(revision 5c140301192225f6a3f669eb918000f25962a75e)
+++ src/Common/GC.h	(revision d318a182b0b2491a1aa64771c523470334852f01)
@@ -38,4 +38,7 @@
 	/// Traces a traceable object
 	const GC& operator<< (const GC_Object*) const;
+
+	/// No-trace mark; returns true if the object exists and was not already marked
+	bool notrace_mark(const GC_Object*) const;
 
 	/// Adds a new object to garbage collection
Index: src/Common/PersistentDisjointSet.h
===================================================================
--- src/Common/PersistentDisjointSet.h	(revision 5c140301192225f6a3f669eb918000f25962a75e)
+++ src/Common/PersistentDisjointSet.h	(revision d318a182b0b2491a1aa64771c523470334852f01)
@@ -281,4 +281,5 @@
 	const Base& rerooted() const {
 		reroot();
+		assertf(mode == BASE, "reroot results in base");
 		return as<Base>();
 	}
@@ -332,21 +333,24 @@
 	}
 
-	/// Adds fresh class including only one item; returns updated map
+	/// Adds fresh class including only one item; returns updated map (or self if no change)
 	template<typename E>
 	Self* add(E&& i) {
 		reroot();
-		
-		// transfer map to new node
-		Self* ret = new Self{ BASE, take_as<Base>() };
+
+		// add new element to node
+		Base base_map = take_as<Base>();
+		bool added = base_map.emplace( i, Node{ i } ).second;
+
+		// fail early on node already present
+		if ( ! added ) {
+			as<Base>() = std::move(base_map);
+			return this;
+		}
+
+		// make new return node and reset self as REM node
+		Self* ret = new Self{ BASE, std::move(base_map) };
 		reset_as_base();
-
-		// set self to REM node
 		init<Add>( ret, i );
 		mode = REM;
-		
-		// add element in returned map
-		Base& base_map = ret->as<Base>();
-		bool added = base_map.emplace( i, Node{ std::forward<E>(i) } ).second;
-		assertf(added, "added element already present in map");
 
 		return ret;
@@ -460,11 +464,15 @@
 		const Base& self = rerooted();
 
-		Elm crnt = i;
-		do {
+		// exit early if class not present
+		auto it = self.find( i );
+		if ( it == self.end() ) return;
+
+		// apply f to each member of class
+		f( i );
+		for ( Elm crnt = it->second.next; crnt != i; crnt = it->second.next ) {
 			f( crnt );
-			auto it = self.find( crnt );
+			it = self.find( crnt );
 			assertf( it != self.end(), "current node must exist in base" );
-			crnt = it->second.next;
-		} while ( crnt != i );
+		}
 	}
 
Index: src/Common/PersistentMap.h
===================================================================
--- src/Common/PersistentMap.h	(revision 5c140301192225f6a3f669eb918000f25962a75e)
+++ src/Common/PersistentMap.h	(revision d318a182b0b2491a1aa64771c523470334852f01)
@@ -141,18 +141,15 @@
 					gc.maybe_trace( entry.first, entry.second );
 				}
-				return;
-			}
+			} break;
 			case REM: {
 				const Rem& self = as<Rem>();
 				gc << self.base;
 				gc.maybe_trace( self.key );
-				return;
-			}
+			} break;
 			case INS: case UPD: {
 				const Ins& self = as<Ins>();
 				gc << self.base;
 				gc.maybe_trace( self.key, self.val );
-				return;
-			}
+			} break;
 			default: assertf(false, "invalid mode");
 		}
@@ -198,6 +195,5 @@
 
 				base_map.erase( it );
-				break;
-			}
+			} break;
 			case INS: {
 				Ins& self = mut_this->as<Ins>();
@@ -207,6 +203,5 @@
 
 				base_map.emplace( std::move(self.key), std::move(self.val) );
-				break;
-			}
+			} break;
 			case UPD: {
 				Ins& self = mut_this->as<Ins>();
@@ -218,6 +213,5 @@
 
 				it->second = std::move(self.val);
-				break;
-			}
+			} break;
 			default: assertf(false, "invalid mode");
 		}
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 );
Index: src/SynTree/GcTracer.h
===================================================================
--- src/SynTree/GcTracer.h	(revision 5c140301192225f6a3f669eb918000f25962a75e)
+++ src/SynTree/GcTracer.h	(revision d318a182b0b2491a1aa64771c523470334852f01)
@@ -25,6 +25,5 @@
 #include "Common/GC.h"
 #include "Common/PassVisitor.h"
-
-class Expression;
+#include "ResolvExpr/TypeEnvironment.h"
 
 /// Implements `trace` method for syntax nodes
@@ -34,4 +33,7 @@
 public:
 	GcTracer( const GC& gc ) : gc(gc) {}
+
+	template<typename... Args>
+	void traceAll(Args&... args) { ::traceAll(gc, args...); }
 
 	// mark node and children
@@ -151,4 +153,38 @@
 		maybeAccept( type->baseUnion, *visitor );
 	}
+
+private:
+	void visit( const ResolvExpr::TypeEnvironment::Classes* c ) {
+		typedef ResolvExpr::TypeEnvironment::Classes C;
+		// trace all parent classes, short-circuiting at one traced
+		while ( gc.notrace_mark( c ) && c->get_mode() != C::BASE ) { c = c->get_base(); }
+	}
+
+	void visit( const ResolvExpr::TypeEnvironment::Bindings* b ) {
+		typedef ResolvExpr::TypeEnvironment::Bindings B;
+
+		while ( true ) {
+			if ( ! gc.notrace_mark( b ) ) return;  // short-circuit if already traced
+
+			if ( b->get_mode() == B::BASE ) break; // break if this is a base map
+			
+			if ( b->get_mode() != B::REM ) { // trace bound intermediate elements
+				maybeAccept( b->get_val().type, *visitor );
+			}
+
+			b = b->get_base();
+		}
+
+		// trace bound elements in base binding
+		b->for_each( [&](interned_string, const ResolvExpr::BoundType& bound) {
+			maybeAccept( bound.type, *visitor );  // trace bound elements
+		} );
+	}
+
+public:
+	void visit( const ResolvExpr::TypeEnvironment& env ) {
+		visit( env.classes );
+		visit( env.bindings );
+	}
 };