Index: src/GenPoly/InstantiateGeneric.cc
===================================================================
--- src/GenPoly/InstantiateGeneric.cc	(revision d8847b7e0bcf675a467161ab62fbe142bb2d4e95)
+++ src/GenPoly/InstantiateGeneric.cc	(revision d8847b7e0bcf675a467161ab62fbe142bb2d4e95)
@@ -0,0 +1,242 @@
+//
+// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
+//
+// The contents of this file are covered under the licence agreement in the
+// file "LICENCE" distributed with Cforall.
+//
+// InstantiateGeneric.h --
+//
+// Author           : Aaron B. Moss
+// Created On       : Wed Nov 11 14:55:01 2015
+// Last Modified By : Aaron B. Moss
+// Last Modified On : Wed Nov 11 14:55:01 2015
+// Update Count     : 1
+//
+
+#include <list>
+#include <map>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include "InstantiateGeneric.h"
+#include "PolyMutator.h"
+
+#include "SymTab/TypeEquality.h"
+#include "SynTree/Declaration.h"
+#include "SynTree/Mutator.h"
+#include "SynTree/Statement.h"
+#include "SynTree/Type.h"
+#include "SynTree/TypeSubstitution.h"
+
+#include "UniqueName.h"
+#include "utility.h"
+
+namespace GenPoly {
+
+	class Instantiate : public PolyMutator {
+	public:
+		/// Key for a unique concrete type; generic base type paired with type parameter list
+		struct ConcreteType {
+			ConcreteType() : base(NULL), params() {}
+
+			ConcreteType(AggregateDecl *_base, const std::list< Type* >& _params) : base(_base), params() { cloneAll(_params, params); }
+
+			ConcreteType(const ConcreteType& that) : base(that.base), params() { cloneAll(that.params, params); }
+
+			/// Extracts types from a list of Expression* (which should be TypeExpr*)
+			ConcreteType(AggregateDecl *_base, const std::list< Expression* >& _params) : base(_base), params() {
+				for ( std::list< Expression* >::const_iterator it = _params.begin(); it != _params.end(); ++it ) {
+					TypeExpr *param = dynamic_cast< TypeExpr* >(*it);
+					assert(param && "Aggregate parameters should be type expressions");
+					params.push_back( param->get_type()->clone() );
+				}
+			}
+
+			ConcreteType& operator= (const ConcreteType& that) {
+				deleteAll( params );
+				params.clear();
+				
+				base = that.base;
+				cloneAll( that.params, params );
+
+				return *this;
+			}
+
+			~ConcreteType() { deleteAll( params ); }
+			
+			bool operator== (const ConcreteType& that) const {
+				if ( base != that.base ) return false;
+				if ( params.size() != that.params.size() ) return false;
+				for ( std::list< Type* >::const_iterator it = params.begin(), jt = that.params.begin(); it != params.end(); ++it, ++jt ) {
+					if ( ! SymTab::typeEquals(*it, *jt) ) return false;
+				}
+				return true;
+			}
+
+			AggregateDecl *base;        ///< Base generic type
+			std::list< Type* > params;  ///< Instantiation parameters
+		};
+		
+		/// Maps a concrete type to the instantiated struct type, accounting for scope
+		class InstantiationMap {
+			/// Pair of concrete type and declaration that instantiates it
+			typedef std::pair< ConcreteType, AggregateDecl* > Instantiation;
+			/// Map of generic types to instantiations of them
+			typedef std::map< AggregateDecl*, std::vector< Instantiation > > Scope;
+
+			std::vector< Scope > scopes;  ///< list of scopes, from outermost to innermost
+
+		public:
+			/// Starts a new scope
+			void beginScope() {
+				Scope scope;
+				scopes.push_back(scope);
+			}
+
+			/// Ends a scope
+			void endScope() {
+				scopes.pop_back();
+			}
+			
+			/// Default constructor initializes with one scope
+			InstantiationMap() { beginScope(); }
+
+		private:
+			/// Gets the declaration for the concrete instantiation of this type, assuming it has already been instantiated in the current scope.
+			/// Returns NULL on none such.
+			AggregateDecl* lookup( AggregateDecl *generic, std::list< Expression* >& params ) {
+				ConcreteType key(generic, params);
+				// scan scopes from innermost out
+				for ( std::vector< Scope >::const_reverse_iterator scope = scopes.rbegin(); scope != scopes.rend(); ++scope ) {
+					// skip scope if no instantiations of this generic type
+					Scope::const_iterator insts = scope->find( generic );
+					if ( insts == scope->end() ) continue;
+					// look through instantiations for matches to concrete type
+					for ( std::vector< Instantiation >::const_iterator inst = insts->second.begin(); inst != insts->second.end(); ++inst ) {
+						if ( inst->first == key ) return inst->second;
+					}
+				}
+				// no matching instantiation found
+				return NULL;
+			}
+		public:
+			StructDecl* lookup( StructInstType *inst ) { return (StructDecl*)lookup( inst->get_baseStruct(), inst->get_parameters() ); }
+			UnionDecl* lookup( UnionInstType *inst ) { return (UnionDecl*)lookup( inst->get_baseUnion(), inst->get_parameters() ); }
+
+		private:
+			/// Adds a declaration for a concrete type to the current scope
+			void insert( AggregateDecl *generic, std::list< Expression* >& params, AggregateDecl *decl ) {
+				ConcreteType key(generic, params);
+				scopes.back()[generic].push_back( std::make_pair( key, decl ) );
+			}
+		public:
+			void insert( StructInstType *inst, StructDecl *decl ) { insert( inst->get_baseStruct(), inst->get_parameters(), decl ); }
+			void insert( UnionInstType *inst, UnionDecl *decl ) { insert( inst->get_baseUnion(), inst->get_parameters(), decl ); }
+		};
+
+		virtual Type* mutate( StructInstType *inst );
+		virtual Type* mutate( UnionInstType *inst );
+		
+		virtual void doBeginScope();
+		virtual void doEndScope();
+
+	private:
+		/// Adds a declaration to the current environment and the statements to add
+		void addDeclaration( AggregateDecl *decl ) {
+			std::list< Label > labels;
+			DeclStmt *stmt = new DeclStmt( labels, decl );
+			PolyMutator::stmtsToAdd.push_back( stmt );
+		}
+		
+		InstantiationMap instantiations;
+		UniqueName typeNamer;
+	};
+	
+	void instantiateGeneric( std::list< Declaration* >& translationUnit ) {
+		Instantiate instantiator;
+		mutateAll( translationUnit, instantiator );
+	}
+
+	/// Substitutes types of members of in according to baseParams => params, appending the result to out
+	void substituteMembers( const std::list< Declaration* >& in,
+							const std::list< TypeDecl * >& baseParams, const std::list< Expression* >& params,
+						    std::list< Declaration* >& out ) {
+		// substitute types into new members
+		TypeSubstitution subs( baseParams.begin(), baseParams.end(), params.begin() );
+		for ( std::list< Declaration* >::const_iterator member = in.begin(); member != in.end(); ++member ) {
+			Declaration *newMember = (*member)->clone();
+			subs.apply(newMember);
+			out.push_back( newMember );
+		}
+	}
+
+	Type* Instantiate::mutate( StructInstType *inst ) {
+		// mutate subtypes
+		Type *mutated = Mutator::mutate( inst );
+		inst = dynamic_cast< StructInstType* >( mutated );
+		if ( ! inst ) return mutated;
+
+		// exit early if no need for further mutation
+		if ( inst->get_parameters().empty() ) return inst;
+		
+		// make concrete instantiation of generic type
+		StructDecl *concDecl = instantiations.lookup( inst );
+		if ( ! concDecl ) {
+			// set concDecl to new type, insert type declaration into statements to add
+			concDecl = new StructDecl( typeNamer.newName( inst->get_name() ) );
+			substituteMembers( inst->get_baseStruct()->get_members(),
+								inst->get_baseParameters(), inst->get_parameters(),
+								concDecl->get_members() );
+			addDeclaration( concDecl );
+			instantiations.insert( inst, concDecl );
+		}
+		StructInstType *newInst = new StructInstType( inst->get_qualifiers(), concDecl->get_name() );
+		newInst->set_baseStruct( concDecl );
+		delete inst;
+		return newInst;
+	}
+	
+	Type* Instantiate::mutate( UnionInstType *inst ) {
+		// mutate subtypes
+		Type *mutated = Mutator::mutate( inst );
+		inst = dynamic_cast< UnionInstType* >( mutated );
+		if ( ! inst ) return mutated;
+
+		// exit early if no need for further mutation
+		if ( inst->get_parameters().empty() ) return inst;
+
+		// make concrete instantiation of generic type
+		UnionDecl *concDecl = instantiations.lookup( inst );
+		if ( ! concDecl ) {
+			// set concDecl to new type, insert type declaration into statements to add
+			concDecl = new UnionDecl( typeNamer.newName( inst->get_name() ) );
+			substituteMembers( inst->get_baseUnion()->get_members(),
+								inst->get_baseParameters(), inst->get_parameters(),
+								concDecl->get_members() );
+			addDeclaration( concDecl );
+			instantiations.insert( inst, concDecl );
+		}
+		UnionInstType *newInst = new UnionInstType( inst->get_qualifiers(), concDecl->get_name() );
+		newInst->set_baseUnion( concDecl );
+		delete inst;
+		return newInst;
+	}
+	
+	void Instantiate::doBeginScope() {
+		// push a new concrete type scope
+		instantiations.beginScope();
+	}
+
+	void Instantiate::doEndScope() {
+		// pop the last concrete type scope
+		instantiations.endScope();
+	}
+	
+}  // namespace GenPoly
+
+// Local Variables: //
+// tab-width: 4 //
+// mode: c++ //
+// compile-command: "make install" //
+// End: //
Index: src/GenPoly/InstantiateGeneric.h
===================================================================
--- src/GenPoly/InstantiateGeneric.h	(revision d8847b7e0bcf675a467161ab62fbe142bb2d4e95)
+++ src/GenPoly/InstantiateGeneric.h	(revision d8847b7e0bcf675a467161ab62fbe142bb2d4e95)
@@ -0,0 +1,33 @@
+//
+// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
+//
+// The contents of this file are covered under the licence agreement in the
+// file "LICENCE" distributed with Cforall.
+//
+// InstantiateGeneric.h --
+//
+// Author           : Aaron B. Moss
+// Created On       : Wed Nov 11 14:55:01 2015
+// Last Modified By : Aaron B. Moss
+// Last Modified On : Wed Nov 11 14:55:01 2015
+// Update Count     : 1
+//
+
+#ifndef _INSTANTIATEGENERIC_H
+#define _INSTANTIATEGENERIC_H
+
+#include <list>
+#include "SynTree/SynTree.h"
+
+namespace GenPoly {
+	/// Replaces generic structs used outside polymorphic contexts with their concrete instantiations
+	void instantiateGeneric( std::list< Declaration* >& translationUnit );
+} // namespace GenPoly
+
+#endif // _INSTANTIATEGENERIC_H
+
+// Local Variables: //
+// tab-width: 4 //
+// mode: c++ //
+// compile-command: "make install" //
+// End: //
Index: src/GenPoly/module.mk
===================================================================
--- src/GenPoly/module.mk	(revision 37a3b8f9cd78867281402907e903cddfd9b978a1)
+++ src/GenPoly/module.mk	(revision d8847b7e0bcf675a467161ab62fbe142bb2d4e95)
@@ -22,3 +22,4 @@
        GenPoly/Specialize.cc \
        GenPoly/CopyParams.cc \
-       GenPoly/FindFunction.cc
+       GenPoly/FindFunction.cc \
+       GenPoly/InstantiateGeneric.cc
Index: src/Makefile.in
===================================================================
--- src/Makefile.in	(revision 37a3b8f9cd78867281402907e903cddfd9b978a1)
+++ src/Makefile.in	(revision d8847b7e0bcf675a467161ab62fbe142bb2d4e95)
@@ -121,4 +121,5 @@
 	GenPoly/cfa_cpp-CopyParams.$(OBJEXT) \
 	GenPoly/cfa_cpp-FindFunction.$(OBJEXT) \
+	GenPoly/cfa_cpp-InstantiateGeneric.$(OBJEXT) \
 	InitTweak/cfa_cpp-InitModel.$(OBJEXT) \
 	InitTweak/cfa_cpp-InitExpander.$(OBJEXT) \
@@ -347,12 +348,12 @@
 	GenPoly/ScrubTyVars.cc GenPoly/Lvalue.cc GenPoly/Specialize.cc \
 	GenPoly/CopyParams.cc GenPoly/FindFunction.cc \
-	InitTweak/InitModel.cc InitTweak/InitExpander.cc \
-	InitTweak/Mutate.cc InitTweak/Association.cc \
-	InitTweak/RemoveInit.cc Parser/parser.yy Parser/lex.ll \
-	Parser/TypedefTable.cc Parser/ParseNode.cc \
-	Parser/DeclarationNode.cc Parser/ExpressionNode.cc \
-	Parser/StatementNode.cc Parser/InitializerNode.cc \
-	Parser/TypeData.cc Parser/LinkageSpec.cc \
-	Parser/parseutility.cc Parser/Parser.cc \
+	GenPoly/InstantiateGeneric.cc InitTweak/InitModel.cc \
+	InitTweak/InitExpander.cc InitTweak/Mutate.cc \
+	InitTweak/Association.cc InitTweak/RemoveInit.cc \
+	Parser/parser.yy Parser/lex.ll Parser/TypedefTable.cc \
+	Parser/ParseNode.cc Parser/DeclarationNode.cc \
+	Parser/ExpressionNode.cc Parser/StatementNode.cc \
+	Parser/InitializerNode.cc Parser/TypeData.cc \
+	Parser/LinkageSpec.cc Parser/parseutility.cc Parser/Parser.cc \
 	ResolvExpr/AlternativeFinder.cc ResolvExpr/Alternative.cc \
 	ResolvExpr/Unify.cc ResolvExpr/PtrsAssignable.cc \
@@ -553,4 +554,6 @@
 	GenPoly/$(DEPDIR)/$(am__dirstamp)
 GenPoly/cfa_cpp-FindFunction.$(OBJEXT): GenPoly/$(am__dirstamp) \
+	GenPoly/$(DEPDIR)/$(am__dirstamp)
+GenPoly/cfa_cpp-InstantiateGeneric.$(OBJEXT): GenPoly/$(am__dirstamp) \
 	GenPoly/$(DEPDIR)/$(am__dirstamp)
 InitTweak/$(am__dirstamp):
@@ -784,4 +787,5 @@
 	-rm -f GenPoly/cfa_cpp-FindFunction.$(OBJEXT)
 	-rm -f GenPoly/cfa_cpp-GenPoly.$(OBJEXT)
+	-rm -f GenPoly/cfa_cpp-InstantiateGeneric.$(OBJEXT)
 	-rm -f GenPoly/cfa_cpp-Lvalue.$(OBJEXT)
 	-rm -f GenPoly/cfa_cpp-PolyMutator.$(OBJEXT)
@@ -893,4 +897,5 @@
 @AMDEP_TRUE@@am__include@ @am__quote@GenPoly/$(DEPDIR)/cfa_cpp-FindFunction.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@GenPoly/$(DEPDIR)/cfa_cpp-GenPoly.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@GenPoly/$(DEPDIR)/cfa_cpp-InstantiateGeneric.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@GenPoly/$(DEPDIR)/cfa_cpp-Lvalue.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@GenPoly/$(DEPDIR)/cfa_cpp-PolyMutator.Po@am__quote@
@@ -1357,4 +1362,18 @@
 @am__fastdepCXX_FALSE@	$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(cfa_cpp_CXXFLAGS) $(CXXFLAGS) -c -o GenPoly/cfa_cpp-FindFunction.obj `if test -f 'GenPoly/FindFunction.cc'; then $(CYGPATH_W) 'GenPoly/FindFunction.cc'; else $(CYGPATH_W) '$(srcdir)/GenPoly/FindFunction.cc'; fi`
 
+GenPoly/cfa_cpp-InstantiateGeneric.o: GenPoly/InstantiateGeneric.cc
+@am__fastdepCXX_TRUE@	$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(cfa_cpp_CXXFLAGS) $(CXXFLAGS) -MT GenPoly/cfa_cpp-InstantiateGeneric.o -MD -MP -MF GenPoly/$(DEPDIR)/cfa_cpp-InstantiateGeneric.Tpo -c -o GenPoly/cfa_cpp-InstantiateGeneric.o `test -f 'GenPoly/InstantiateGeneric.cc' || echo '$(srcdir)/'`GenPoly/InstantiateGeneric.cc
+@am__fastdepCXX_TRUE@	$(am__mv) GenPoly/$(DEPDIR)/cfa_cpp-InstantiateGeneric.Tpo GenPoly/$(DEPDIR)/cfa_cpp-InstantiateGeneric.Po
+@AMDEP_TRUE@@am__fastdepCXX_FALSE@	source='GenPoly/InstantiateGeneric.cc' object='GenPoly/cfa_cpp-InstantiateGeneric.o' libtool=no @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCXX_FALSE@	DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCXX_FALSE@	$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(cfa_cpp_CXXFLAGS) $(CXXFLAGS) -c -o GenPoly/cfa_cpp-InstantiateGeneric.o `test -f 'GenPoly/InstantiateGeneric.cc' || echo '$(srcdir)/'`GenPoly/InstantiateGeneric.cc
+
+GenPoly/cfa_cpp-InstantiateGeneric.obj: GenPoly/InstantiateGeneric.cc
+@am__fastdepCXX_TRUE@	$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(cfa_cpp_CXXFLAGS) $(CXXFLAGS) -MT GenPoly/cfa_cpp-InstantiateGeneric.obj -MD -MP -MF GenPoly/$(DEPDIR)/cfa_cpp-InstantiateGeneric.Tpo -c -o GenPoly/cfa_cpp-InstantiateGeneric.obj `if test -f 'GenPoly/InstantiateGeneric.cc'; then $(CYGPATH_W) 'GenPoly/InstantiateGeneric.cc'; else $(CYGPATH_W) '$(srcdir)/GenPoly/InstantiateGeneric.cc'; fi`
+@am__fastdepCXX_TRUE@	$(am__mv) GenPoly/$(DEPDIR)/cfa_cpp-InstantiateGeneric.Tpo GenPoly/$(DEPDIR)/cfa_cpp-InstantiateGeneric.Po
+@AMDEP_TRUE@@am__fastdepCXX_FALSE@	source='GenPoly/InstantiateGeneric.cc' object='GenPoly/cfa_cpp-InstantiateGeneric.obj' libtool=no @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCXX_FALSE@	DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCXX_FALSE@	$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(cfa_cpp_CXXFLAGS) $(CXXFLAGS) -c -o GenPoly/cfa_cpp-InstantiateGeneric.obj `if test -f 'GenPoly/InstantiateGeneric.cc'; then $(CYGPATH_W) 'GenPoly/InstantiateGeneric.cc'; else $(CYGPATH_W) '$(srcdir)/GenPoly/InstantiateGeneric.cc'; fi`
+
 InitTweak/cfa_cpp-InitModel.o: InitTweak/InitModel.cc
 @am__fastdepCXX_TRUE@	$(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(cfa_cpp_CXXFLAGS) $(CXXFLAGS) -MT InitTweak/cfa_cpp-InitModel.o -MD -MP -MF InitTweak/$(DEPDIR)/cfa_cpp-InitModel.Tpo -c -o InitTweak/cfa_cpp-InitModel.o `test -f 'InitTweak/InitModel.cc' || echo '$(srcdir)/'`InitTweak/InitModel.cc
Index: src/main.cc
===================================================================
--- src/main.cc	(revision 37a3b8f9cd78867281402907e903cddfd9b978a1)
+++ src/main.cc	(revision d8847b7e0bcf675a467161ab62fbe142bb2d4e95)
@@ -24,4 +24,5 @@
 #include "SynTree/Declaration.h"
 #include "SynTree/Visitor.h"
+#include "GenPoly/InstantiateGeneric.h"
 #include "GenPoly/Lvalue.h"
 #include "GenPoly/Specialize.h"
@@ -268,4 +269,6 @@
 		}
 
+		OPTPRINT( "instantiateGeneric" )
+		GenPoly::instantiateGeneric( translationUnit );
 		OPTPRINT( "copyParams" );
 		GenPoly::copyParams( translationUnit );