Index: src/GenPoly/InstantiateGeneric.cc
===================================================================
--- src/GenPoly/InstantiateGeneric.cc	(revision 05587c2d3a71d2b397650a80fab2b53de1a89dc7)
+++ src/GenPoly/InstantiateGeneric.cc	(revision 05587c2d3a71d2b397650a80fab2b53de1a89dc7)
@@ -0,0 +1,277 @@
+//
+// 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 "ResolvExpr/typeops.h"
+#include "SymTab/Indexer.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 {
+
+	/// 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 {
+			SymTab::Indexer dummy;
+
+			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 ( ! ResolvExpr::typesCompatible( *it, *jt, dummy ) ) 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 ); }
+	};
+
+	/// Mutator pass that replaces concrete instantiations of generic types with actual struct declarations, scoped appropriately
+	class Instantiate : public PolyMutator {
+		InstantiationMap instantiations;
+		UniqueName typeNamer;
+
+	public:
+		Instantiate() : instantiations(), typeNamer("_conc_") {}
+
+		/// Mutates the whole translation unit, inserting new struct declarations as appropriate
+		void mutateAll( std::list< Declaration* >& translationUnit );
+		
+		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 > nolabels;
+			DeclStmt *stmt = new DeclStmt( nolabels, decl );
+			PolyMutator::stmtsToAdd.push_back( stmt );
+		}
+	};
+	
+	void instantiateGeneric( std::list< Declaration* >& translationUnit ) {
+		Instantiate instantiator;
+//		mutateAll( translationUnit, instantiator );
+		instantiator.mutateAll( translationUnit );
+	}
+
+	void Instantiate::mutateAll( std::list< Declaration* >& translationUnit ) {
+		// below copied and modified from Mutator.h:mutateAll()
+		SemanticError errors;
+		for ( std::list< Declaration* >::iterator decl = translationUnit.begin(); decl != translationUnit.end(); ++decl ) {
+			try {
+				if ( *decl ) {
+					*decl = dynamic_cast< Declaration* >( (*decl)->acceptMutator( *this ) );
+					assert( *decl );
+					// account for missing top-level declarations
+					for ( std::list< Statement* >::const_iterator stmt = PolyMutator::stmtsToAdd.begin(); stmt != PolyMutator::stmtsToAdd.end(); ++stmt ) {
+						DeclStmt *declStmt = dynamic_cast< DeclStmt* >( *stmt );
+						assert( declStmt );
+						translationUnit.insert( decl, declStmt->get_decl() );
+					}
+					PolyMutator::stmtsToAdd.clear();
+				} // if
+			} catch( SemanticError &e ) {
+				errors.append( e );
+			} // try
+		} // for
+		if ( ! errors.isEmpty() ) {
+			throw errors;
+		} // if
+	}
+
+	/// 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 05587c2d3a71d2b397650a80fab2b53de1a89dc7)
+++ src/GenPoly/InstantiateGeneric.h	(revision 05587c2d3a71d2b397650a80fab2b53de1a89dc7)
@@ -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 e56cfdb005c6b37a022fa1d268ad747523f7d2c4)
+++ src/GenPoly/module.mk	(revision 05587c2d3a71d2b397650a80fab2b53de1a89dc7)
@@ -22,3 +22,4 @@
        GenPoly/Specialize.cc \
        GenPoly/CopyParams.cc \
-       GenPoly/FindFunction.cc
+       GenPoly/FindFunction.cc \
+       GenPoly/InstantiateGeneric.cc