Index: src/SymTab/Validate.cc
===================================================================
--- src/SymTab/Validate.cc	(revision c1ed2eed49812bcfa4987e47ccc9eda7d2fbf8c0)
+++ src/SymTab/Validate.cc	(revision b58affe779a55d123b874225988bd1dcb75f0ce4)
@@ -44,6 +44,8 @@
 #include <list>                        // for list
 #include <string>                      // for string
+#include <unordered_map>               // for unordered_map
 #include <utility>                     // for pair
 
+#include "AST/Chain.hpp"
 #include "AST/Decl.hpp"
 #include "AST/Node.hpp"
@@ -54,4 +56,5 @@
 #include "CodeGen/OperatorTable.h"     // for isCtorDtor, isCtorDtorAssign
 #include "ControlStruct/Mutate.h"      // for ForExprMutator
+#include "Common/CodeLocation.h"       // for CodeLocation
 #include "Common/Stats.h"              // for Stats::Heap
 #include "Common/PassVisitor.h"        // for PassVisitor, WithDeclsToAdd
@@ -1428,13 +1431,273 @@
 
 	/// Associates forward declarations of aggregates with their definitions
-	struct LinkReferenceToTypes_new final 
+	class LinkReferenceToTypes_new final 
 	: public ast::WithSymbolTable, public ast::WithGuards, public 
 	  ast::WithVisitorRef<LinkReferenceToTypes_new>, public ast::WithShortCircuiting {
 		
-		const ast::SymbolTable * localSyms;
-
-		LinkReferenceToTypes_new( const ast::SymbolTable & syms ) : localSyms( &syms ) {}
-
-		#warning incomplete
+		// these maps of uses of forward declarations of types need to have the actual type 
+		// declaration switched in *after* they have been traversed. To enable this in the 
+		// ast::Pass framework, any node that needs to be so mutated has mutate() called on it 
+		// before it is placed in the map, properly updating its parents in the usual traversal, 
+		// then can have the actual mutation applied later
+		using ForwardEnumsType = std::unordered_multimap< std::string, ast::EnumInstType * >;
+		using ForwardStructsType = std::unordered_multimap< std::string, ast::StructInstType * >;
+		using ForwardUnionsType = std::unordered_multimap< std::string, ast::UnionInstType * >;
+		
+		const CodeLocation & location;
+		const ast::SymbolTable * localSymtab;
+		
+		ForwardEnumsType forwardEnums;
+		ForwardStructsType forwardStructs;
+		ForwardUnionsType forwardUnions;
+
+		/// true if currently in a generic type body, so that type parameter instances can be 
+		/// renamed appropriately
+		bool inGeneric = false;
+
+	public:
+		/// contstruct using running symbol table
+		LinkReferenceToTypes_new( const CodeLocation & loc ) 
+		: location( loc ), localSymtab( &symtab ) {}
+		
+		/// construct using provided symbol table
+		LinkReferenceToTypes_new( const CodeLocation & loc, const ast::SymbolTable & syms ) 
+		: location( loc ), localSymtab( &syms ) {}
+
+		const ast::Type * postvisit( const ast::TypeInstType * typeInst ) {
+			// ensure generic parameter instances are renamed like the base type
+			if ( inGeneric && typeInst->base ) {
+				typeInst = ast::mutate_field( 
+					typeInst, &ast::TypeInstType::name, typeInst->base->name );
+			}
+
+			if ( 
+				auto typeDecl = dynamic_cast< const ast::TypeDecl * >( 
+					localSymtab->lookupType( typeInst->name ) ) 
+			) {
+				typeInst = ast::mutate_field( typeInst, &ast::TypeInstType::kind, typeDecl->kind );
+			}
+
+			return typeInst;
+		}
+
+		const ast::Type * postvisit( const ast::EnumInstType * inst ) {
+			const ast::EnumDecl * decl = localSymtab->lookupEnum( inst->name );
+			// not a semantic error if the enum is not found, just an implicit forward declaration
+			if ( decl ) {
+				inst = ast::mutate_field( inst, &ast::EnumInstType::base, decl );
+			}
+			if ( ! decl || ! decl->body ) {
+				// forward declaration
+				auto mut = mutate( inst );
+				forwardEnums.emplace( inst->name, mut );
+				inst = mut;
+			}
+			return inst;
+		}
+
+		void checkGenericParameters( const ast::ReferenceToType * inst ) {
+			for ( const ast::Expr * param : inst->params ) {
+				if ( ! dynamic_cast< const ast::TypeExpr * >( param ) ) {
+					SemanticError( 
+						location, inst, "Expression parameters for generic types are currently "
+						"unsupported: " );
+				}
+			}
+		}
+
+		const ast::StructInstType * postvisit( const ast::StructInstType * inst ) {
+			const ast::StructDecl * decl = localSymtab->lookupStruct( inst->name );
+			// not a semantic error if the struct is not found, just an implicit forward declaration
+			if ( decl ) {
+				inst = ast::mutate_field( inst, &ast::StructInstType::base, decl );
+			}
+			if ( ! decl || ! decl->body ) {
+				// forward declaration
+				auto mut = mutate( inst );
+				forwardStructs.emplace( inst->name, mut );
+				inst = mut;
+			}
+			checkGenericParameters( inst );
+			return inst;
+		}
+
+		const ast::UnionInstType * postvisit( const ast::UnionInstType * inst ) {
+			const ast::UnionDecl * decl = localSymtab->lookupUnion( inst->name );
+			// not a semantic error if the struct is not found, just an implicit forward declaration
+			if ( decl ) {
+				inst = ast::mutate_field( inst, &ast::UnionInstType::base, decl );
+			}
+			if ( ! decl || ! decl->body ) {
+				// forward declaration
+				auto mut = mutate( inst );
+				forwardUnions.emplace( inst->name, mut );
+				inst = mut;
+			}
+			checkGenericParameters( inst );
+			return inst;
+		}
+
+		const ast::Type * postvisit( const ast::TraitInstType * traitInst ) {
+			// handle other traits
+			const ast::TraitDecl * traitDecl = localSymtab->lookupTrait( traitInst->name );
+			if ( ! traitDecl )	 {
+				SemanticError( location, "use of undeclared trait " + traitInst->name );
+			}
+			if ( traitDecl->params.size() != traitInst->params.size() ) {
+				SemanticError( location, traitInst, "incorrect number of trait parameters: " );
+			}
+			traitInst = ast::mutate_field( traitInst, &ast::TraitInstType::base, traitDecl );
+
+			// need to carry over the "sized" status of each decl in the instance
+			for ( unsigned i = 0; i < traitDecl->params.size(); ++i ) {
+				auto expr = traitInst->params[i].as< ast::TypeExpr >();
+				if ( ! expr ) {
+					SemanticError( 
+						traitInst->params[i].get(), "Expression parameters for trait instances "
+						"are currently unsupported: " );
+				}
+
+				if ( auto inst = expr->type.as< ast::TypeInstType >() ) {
+					if ( traitDecl->params[i]->sized && ! inst->base->sized ) {
+						// traitInst = ast::mutate_field_index(
+						// 	traitInst, &ast::TraitInstType::params, i,
+						// 	...
+						// );
+						ast::TraitInstType * mut = ast::mutate( traitInst );
+						ast::chain_mutate( mut->params[i] )
+							( &ast::TypeExpr::type )
+								( &ast::TypeInstType::base )->sized = true;
+						traitInst = mut;
+					}
+				}
+			}
+
+			return traitInst;
+		}
+		
+		void previsit( const ast::QualifiedType * ) { visit_children = false; }
+		
+		const ast::Type * postvisit( const ast::QualifiedType * qualType ) {
+			// linking only makes sense for the "oldest ancestor" of the qualified type
+			return ast::mutate_field( 
+				qualType, &ast::QualifiedType::parent, qualType->parent->accept( *visitor ) );
+		}
+
+		const ast::Decl * postvisit( const ast::EnumDecl * enumDecl ) {
+			// visit enum members first so that the types of self-referencing members are updated 
+			// properly
+			if ( ! enumDecl->body ) return enumDecl;
+
+			// update forward declarations to point here
+			auto fwds = forwardEnums.equal_range( enumDecl->name );
+			if ( fwds.first != fwds.second ) {
+				auto inst = fwds.first;
+				do {
+					// forward decl is stored *mutably* in map, can thus be updated
+					inst->second->base = enumDecl;
+				} while ( ++inst != fwds.second );
+				forwardEnums.erase( fwds.first, fwds.second );
+			}
+			
+			// ensure that enumerator initializers are properly set
+			for ( unsigned i = 0; i < enumDecl->members.size(); ++i ) {
+				auto field = enumDecl->members[i].strict_as< ast::ObjectDecl >();
+				if ( field->init ) {
+					// need to resolve enumerator initializers early so that other passes that 
+					// determine if an expression is constexpr have appropriate information
+					auto init = field->init.strict_as< ast::SingleInit >();
+					
+					enumDecl = ast::mutate_field_index( 
+						enumDecl, &ast::EnumDecl::members, i, 
+						ast::mutate_field( field, &ast::ObjectDecl::init, 
+							ast::mutate_field( init, &ast::SingleInit::value,
+								ResolvExpr::findSingleExpression( 
+									init->value, new ast::BasicType{ ast::BasicType::SignedInt },
+									symtab ) ) ) );
+				}
+			}
+
+			return enumDecl;
+		}
+
+		/// rename generic type parameters uniquely so that they do not conflict with user defined 
+		/// function forall parameters, e.g. the T in Box and the T in f, below
+		///   forall(otype T)
+		///   struct Box {
+		///     T x;
+		///   };
+		///   forall(otype T)
+		///   void f(Box(T) b) {
+		///     ...
+		///   }
+		template< typename AggrDecl >
+		const AggrDecl * renameGenericParams( const AggrDecl * aggr ) {
+			GuardValue( inGeneric );
+			inGeneric = ! aggr->params.empty();
+
+			for ( unsigned i = 0; i < aggr->params.size(); ++i ) {
+				const ast::TypeDecl * td = aggr->params[i];
+
+				aggr = ast::mutate_field_index( 
+					aggr, &AggrDecl::params, i, 
+					ast::mutate_field( td, &ast::TypeDecl::name, "__" + td->name + "_generic_" ) );
+			}
+			return aggr;
+		}
+
+		const ast::StructDecl * previsit( const ast::StructDecl * structDecl ) {
+			return renameGenericParams( structDecl );
+		}
+
+		void postvisit( const ast::StructDecl * structDecl ) {
+			// visit struct members first so that the types of self-referencing members are 
+			// updated properly
+			if ( ! structDecl->body ) return;
+
+			// update forward declarations to point here
+			auto fwds = forwardStructs.equal_range( structDecl->name );
+			if ( fwds.first != fwds.second ) {
+				auto inst = fwds.first;
+				do {
+					// forward decl is stored *mutably* in map, can thus be updated
+					inst->second->base = structDecl;
+				} while ( ++inst != fwds.second );
+				forwardStructs.erase( fwds.first, fwds.second );
+			}
+		}
+
+		const ast::UnionDecl * previsit( const ast::UnionDecl * unionDecl ) {
+			return renameGenericParams( unionDecl );
+		}
+
+		void postvisit( const ast::UnionDecl * unionDecl ) {
+			// visit union members first so that the types of self-referencing members are updated 
+			// properly
+			if ( ! unionDecl->body ) return;
+
+			// update forward declarations to point here
+			auto fwds = forwardUnions.equal_range( unionDecl->name );
+			if ( fwds.first != fwds.second ) {
+				auto inst = fwds.first;
+				do {
+					// forward decl is stored *mutably* in map, can thus be updated
+					inst->second->base = unionDecl;
+				} while ( ++inst != fwds.second );
+				forwardUnions.erase( fwds.first, fwds.second );
+			}
+		}
+
+		const ast::Decl * postvisit( const ast::TraitDecl * traitDecl ) {
+			// set the "sized" status for the special "sized" trait
+			if ( traitDecl->name != "sized" ) return traitDecl;
+
+			assertf( traitDecl->params.size() == 1, "Built-in trait 'sized' has incorrect number "
+				"of parameters: %zd", traitDecl->params.size() );
+
+			return ast::mutate_field_index( 
+				traitDecl, &ast::TraitDecl::params, 0, 
+				ast::mutate_field( 
+					traitDecl->params.front().get(), &ast::TypeDecl::sized, true ) );
+		}
 	};
 
@@ -1446,7 +1709,8 @@
 } // anonymous namespace
 
-const ast::Type * validateType( const ast::Type * type, const ast::SymbolTable & symtab ) {
+const ast::Type * validateType( 
+		const CodeLocation & loc, const ast::Type * type, const ast::SymbolTable & symtab ) {
 	ast::Pass< EnumAndPointerDecay_new > epc;
-	ast::Pass< LinkReferenceToTypes_new > lrt{ symtab };
+	ast::Pass< LinkReferenceToTypes_new > lrt{ loc, symtab };
 	ast::Pass< ForallPointerDecay_new > fpd;
 
