Index: src/AST/Type.cpp
===================================================================
--- src/AST/Type.cpp	(revision bc899d6a44ef2923a2bd54f336bb656b8624bc30)
+++ src/AST/Type.cpp	(revision 63d1ebe7115e4450a16b96fb0ea497249a457c47)
@@ -147,4 +147,10 @@
 // --- TypeInstType
 
+bool TypeInstType::operator==( const TypeInstType & other ) const {
+	return base == other.base
+		&& formal_usage == other.formal_usage
+		&& expr_id == other.expr_id;
+}
+
 TypeInstType::TypeInstType( const TypeDecl * b,
 	CV::Qualifiers q, std::vector<ptr<Attribute>> && as )
@@ -157,4 +163,33 @@
 
 bool TypeInstType::isComplete() const { return base->sized; }
+
+std::string TypeInstType::TypeEnvKey::typeString() const {
+	return std::string("_") + std::to_string(formal_usage)
+		+ "_" + std::to_string(expr_id) + "_" + base->name;
+}
+
+bool TypeInstType::TypeEnvKey::operator==(
+		const TypeInstType::TypeEnvKey & other ) const {
+	return base == other.base
+		&& formal_usage == other.formal_usage
+		&& expr_id == other.expr_id;
+}
+
+bool TypeInstType::TypeEnvKey::operator<(
+		const TypeInstType::TypeEnvKey & other ) const {
+	// TypeEnvKey ordering is an arbitrary total ordering.
+	// It doesn't mean anything but allows for a sorting.
+	if ( base < other.base ) {
+		return true;
+	} else if ( other.base < base ) {
+		return false;
+	} else if ( formal_usage < other.formal_usage ) {
+		return true;
+	} else if ( other.formal_usage < formal_usage ) {
+		return false;
+	} else {
+		return expr_id < other.expr_id;
+	}
+}
 
 // --- TupleType
Index: src/AST/Type.hpp
===================================================================
--- src/AST/Type.hpp	(revision bc899d6a44ef2923a2bd54f336bb656b8624bc30)
+++ src/AST/Type.hpp	(revision 63d1ebe7115e4450a16b96fb0ea497249a457c47)
@@ -408,11 +408,14 @@
 
 		TypeEnvKey() = default;
-		TypeEnvKey(const TypeDecl * base, int formal_usage = 0, int expr_id = 0): base(base), formal_usage(formal_usage), expr_id(expr_id) {}
-		TypeEnvKey(const TypeInstType & inst): base(inst.base), formal_usage(inst.formal_usage), expr_id(inst.expr_id) {}
-		std::string typeString() const { return std::string("_") + std::to_string(formal_usage) + "_" + std::to_string(expr_id) + "_" + base->name; }
-		bool operator==(const TypeEnvKey & other) const { return base == other.base && formal_usage == other.formal_usage && expr_id == other.expr_id; }
+		TypeEnvKey(const TypeDecl * base, int formal_usage = 0, int expr_id = 0)
+		: base(base), formal_usage(formal_usage), expr_id(expr_id) {}
+		TypeEnvKey(const TypeInstType & inst)
+		: base(inst.base), formal_usage(inst.formal_usage), expr_id(inst.expr_id) {}
+		std::string typeString() const;
+		bool operator==(const TypeEnvKey & other) const;
+		bool operator<(const TypeEnvKey & other) const;
 	};
 
-	bool operator==(const TypeInstType & other) const { return base == other.base && formal_usage == other.formal_usage && expr_id == other.expr_id; }
+	bool operator==(const TypeInstType & other) const;
 
 	TypeInstType(