//
// 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.
//
// Box.cpp -- Implement polymorphic function calls and types.
//
// Author           : Andrew Beach
// Created On       : Thr Oct  6 13:39:00 2022
// Last Modified By : Peter A. Buhr
// Last Modified On : Thu Dec 14 17:42:17 2023
// Update Count     : 7
//

#include "Box.hpp"

#include "AST/Decl.hpp"                // for Decl, FunctionDecl, ...
#include "AST/Expr.hpp"                // for AlignofExpr, ConstantExpr, ...
#include "AST/Init.hpp"                // for Init, SingleInit
#include "AST/Inspect.hpp"             // for getFunctionName
#include "AST/Pass.hpp"                // for Pass, WithDeclsToAdd, ...
#include "AST/Stmt.hpp"                // for CompoundStmt, ExprStmt, ...
#include "AST/Vector.hpp"              // for vector
#include "AST/GenericSubstitution.hpp" // for genericSubstitution
#include "CodeGen/OperatorTable.hpp"   // for isAssignment
#include "Common/Iterate.hpp"          // for group_iterate
#include "Common/ScopedMap.hpp"        // for ScopedMap
#include "Common/ToString.hpp"         // for toCString
#include "Common/UniqueName.hpp"       // for UniqueName
#include "GenPoly/FindFunction.hpp"    // for findFunction
#include "GenPoly/GenPoly.hpp"         // for getFunctionType, isPolyType, ...
#include "GenPoly/Lvalue.hpp"          // for generalizedLvalue
#include "GenPoly/ScopedSet.hpp"       // for ScopedSet
#include "GenPoly/ScrubTypeVars.hpp"   // for scrubTypeVars, scrubAllTypeVars
#include "ResolvExpr/Unify.hpp"        // for typesCompatible
#include "SymTab/Mangler.hpp"          // for mangle, mangleType

namespace GenPoly {

namespace {

/// The layout type is used to represent sizes, alignments and offsets.
ast::BasicType * makeLayoutType() {
	return new ast::BasicType( ast::BasicKind::LongUnsignedInt );
}

/// Fixed version of layout type (just adding a 'C' in C++ style).
ast::BasicType * makeLayoutCType() {
	return new ast::BasicType( ast::BasicKind::LongUnsignedInt,
		ast::CV::Qualifiers( ast::CV::Const ) );
}

// --------------------------------------------------------------------------
/// Adds layout-generation functions to polymorphic types.
struct LayoutFunctionBuilder final :
		public ast::WithDeclsToAdd<>,
		public ast::WithShortCircuiting,
		public ast::WithVisitorRef<LayoutFunctionBuilder> {
	void previsit( ast::StructDecl const * decl );
	void previsit( ast::UnionDecl const * decl );
};

/// Get all sized type declarations; those that affect a layout function.
ast::vector<ast::TypeDecl> takeSizedParams(
		ast::vector<ast::TypeDecl> const & decls ) {
	ast::vector<ast::TypeDecl> sizedParams;
	for ( ast::ptr<ast::TypeDecl> const & decl : decls ) {
		if ( decl->isComplete() ) {
			sizedParams.emplace_back( decl );
		}
	}
	return sizedParams;
}

/// Adds parameters for otype size and alignment to a function type.
void addSTypeParams(
		ast::vector<ast::DeclWithType> & params,
		ast::vector<ast::TypeDecl> const & sizedParams ) {
	for ( ast::ptr<ast::TypeDecl> const & sizedParam : sizedParams ) {
		ast::TypeInstType inst( sizedParam );
		std::string paramName = Mangle::mangleType( &inst );
		params.emplace_back( new ast::ObjectDecl(
			sizedParam->location,
			sizeofName( paramName ),
			makeLayoutCType()
		) );
		params.emplace_back( new ast::ObjectDecl(
			sizedParam->location,
			alignofName( paramName ),
			makeLayoutCType()
		) );
	}
}

ast::Type * makeLayoutOutType() {
	return new ast::PointerType( makeLayoutType() );
}

struct LayoutData {
	ast::FunctionDecl * function;
	ast::ObjectDecl * sizeofParam;
	ast::ObjectDecl * alignofParam;
	ast::ObjectDecl * offsetofParam;
};

LayoutData buildLayoutFunction(
		CodeLocation const & location, ast::AggregateDecl const * aggr,
		ast::vector<ast::TypeDecl> const & sizedParams,
		bool isInFunction, bool isStruct ) {
	ast::ObjectDecl * sizeParam = new ast::ObjectDecl(
		location,
		sizeofName( aggr->name ),
		makeLayoutOutType()
	);
	ast::ObjectDecl * alignParam = new ast::ObjectDecl(
		location,
		alignofName( aggr->name ),
		makeLayoutOutType()
	);
	ast::ObjectDecl * offsetParam = nullptr;
	ast::vector<ast::DeclWithType> params = { sizeParam, alignParam };
	if ( isStruct ) {
		offsetParam = new ast::ObjectDecl(
			location,
			offsetofName( aggr->name ),
			makeLayoutOutType()
		);
		params.push_back( offsetParam );
	}
	addSTypeParams( params, sizedParams );

	// Routines at global scope marked "static" to prevent multiple
	// definitions is separate translation units because each unit generates
	// copies of the default routines for each aggregate.
	ast::FunctionDecl * layoutDecl = new ast::FunctionDecl(
		location,
		layoutofName( aggr ),
		{}, // forall
		{}, // assertions
		std::move( params ),
		{}, // returns
		new ast::CompoundStmt( location ),
		isInFunction ? ast::Storage::Classes() : ast::Storage::Static,
		ast::Linkage::AutoGen,
		{}, // attrs
		ast::Function::Inline,
		ast::FixedArgs
	);
	layoutDecl->fixUniqueId();
	return LayoutData{ layoutDecl, sizeParam, alignParam, offsetParam };
}

/// Makes a binary operation.
ast::Expr * makeOp( CodeLocation const & location, std::string const & name,
		ast::Expr const * lhs, ast::Expr const * rhs ) {
	return new ast::UntypedExpr( location,
		new ast::NameExpr( location, name ), { lhs, rhs } );
}

/// Make a binary operation and wrap it in a statement.
ast::Stmt * makeOpStmt( CodeLocation const & location, std::string const & name,
		ast::Expr const * lhs, ast::Expr const * rhs ) {
	return new ast::ExprStmt( location, makeOp( location, name, lhs, rhs ) );
}

/// Returns the dereference of a local pointer variable.
ast::Expr * derefVar(
		CodeLocation const & location, ast::ObjectDecl const * var ) {
	return ast::UntypedExpr::createDeref( location,
		new ast::VariableExpr( location, var ) );
}

/// Makes an if-statement with a single-expression then and no else.
ast::Stmt * makeCond( CodeLocation const & location,
		ast::Expr const * cond, ast::Expr const * thenPart ) {
	return new ast::IfStmt( location,
		cond, new ast::ExprStmt( location, thenPart ), nullptr );
}

/// Makes a statement that aligns lhs to rhs (rhs should be an integer
/// power of two).
ast::Stmt * makeAlignTo( CodeLocation const & location,
		ast::Expr const * lhs, ast::Expr const * rhs ) {
	// Check that the lhs is zeroed out to the level of rhs.
	ast::Expr * ifCond = makeOp( location, "?&?", lhs,
		makeOp( location, "?-?", rhs,
				ast::ConstantExpr::from_ulong( location, 1 ) ) );
	// If not aligned, increment to alignment.
	ast::Expr * ifExpr = makeOp( location, "?+=?", ast::deepCopy( lhs ),
		makeOp( location, "?-?", ast::deepCopy( rhs ),
				ast::deepCopy( ifCond ) ) );
	return makeCond( location, ifCond, ifExpr );
}

/// Makes a statement that assigns rhs to lhs if lhs < rhs.
ast::Stmt * makeAssignMax( CodeLocation const & location,
		ast::Expr const * lhs, ast::Expr const * rhs ) {
	return makeCond( location,
		makeOp( location, "?<?", ast::deepCopy( lhs ), ast::deepCopy( rhs ) ),
		makeOp( location, "?=?", lhs, rhs ) );
}

void LayoutFunctionBuilder::previsit( ast::StructDecl const * decl ) {
	// Do not generate layout function for empty tag structures.
	visit_children = false;
	if ( decl->members.empty() ) return;

	// Get parameters that can change layout, exiting early if none.
	ast::vector<ast::TypeDecl> sizedParams =
		takeSizedParams( decl->params );
	if ( sizedParams.empty() ) return;

	CodeLocation const & location = decl->location;

	// Build layout function signature.
	LayoutData layout = buildLayoutFunction(
		location, decl, sizedParams, isInFunction(), true );
	ast::FunctionDecl * layoutDecl = layout.function;
	// Also return these or extract them from the parameter list?
	ast::ObjectDecl const * sizeofParam = layout.sizeofParam;
	ast::ObjectDecl const * alignofParam = layout.alignofParam;
	ast::ObjectDecl const * offsetofParam = layout.offsetofParam;
	assert( nullptr != layout.offsetofParam );

	// Calculate structure layout in function body.
	// Initialize size and alignment to 0 and 1
	// (Will have at least one member to update size).
	auto & kids = layoutDecl->stmts.get_and_mutate()->kids;
	kids.emplace_back( makeOpStmt( location, "?=?",
		derefVar( location, sizeofParam ),
		ast::ConstantExpr::from_ulong( location, 0 )
	) );
	kids.emplace_back( makeOpStmt( location, "?=?",
		derefVar( location, alignofParam ),
		ast::ConstantExpr::from_ulong( location, 1 )
	) );
	// TODO: Polymorphic types will be out of the struct declaration scope.
	// This breaks invariants until it is corrected later.
	for ( auto const & member : enumerate( decl->members ) ) {
		auto dwt = member.val.strict_as<ast::DeclWithType>();
		ast::Type const * memberType = dwt->get_type();

		if ( 0 < member.idx ) {
			// Make sure all later members have padding to align them.
			kids.emplace_back( makeAlignTo( location,
				derefVar( location, sizeofParam ),
				new ast::AlignofExpr( location, ast::deepCopy( memberType ) )
			) );
		}

		// Place current size in the current offset index.
		kids.emplace_back( makeOpStmt( location, "?=?",
			makeOp( location, "?[?]",
				new ast::VariableExpr( location, offsetofParam ),
				ast::ConstantExpr::from_ulong( location, member.idx ) ),
			derefVar( location, sizeofParam ) ) );

		// Add member size to current size.
		kids.emplace_back( makeOpStmt( location, "?+=?",
			derefVar( location, sizeofParam ),
			new ast::SizeofExpr( location, ast::deepCopy( memberType ) ) ) );

		// Take max of member alignment and global alignment.
		// (As align is always 2^n, this will always be a multiple of both.)
		kids.emplace_back( makeAssignMax( location,
			derefVar( location, alignofParam ),
			new ast::AlignofExpr( location, ast::deepCopy( memberType ) ) ) );
	}
	// Make sure the type is end-padded to a multiple of its alignment.
	kids.emplace_back( makeAlignTo( location,
		derefVar( location, sizeofParam ),
		derefVar( location, alignofParam ) ) );

	declsToAddAfter.emplace_back( layoutDecl );
}

void LayoutFunctionBuilder::previsit( ast::UnionDecl const * decl ) {
	visit_children = false;
	// Do not generate layout function for empty tag unions.
	if ( decl->members.empty() ) return;

	// Get parameters that can change layout, exiting early if none.
	ast::vector<ast::TypeDecl> sizedParams =
		takeSizedParams( decl->params );
	if ( sizedParams.empty() ) return;

	CodeLocation const & location = decl->location;

	// Build layout function signature.
	LayoutData layout = buildLayoutFunction(
		location, decl, sizedParams, isInFunction(), false );
	ast::FunctionDecl * layoutDecl = layout.function;
	// Also return these or extract them from the parameter list?
	ast::ObjectDecl const * sizeofParam = layout.sizeofParam;
	ast::ObjectDecl const * alignofParam = layout.alignofParam;
	assert( nullptr == layout.offsetofParam );

	// Calculate union layout in function body.
	// Both are simply the maximum for union (actually align is always the
	// LCM, but with powers of two that is also the maximum).
	auto & kids = layoutDecl->stmts.get_and_mutate()->kids;
	kids.emplace_back( makeOpStmt( location,
		"?=?", derefVar( location, sizeofParam ),
		ast::ConstantExpr::from_ulong( location, 1 )
	) );
	kids.emplace_back( makeOpStmt( location,
		"?=?", derefVar( location, alignofParam ),
		ast::ConstantExpr::from_ulong( location, 1 )
	) );
	// TODO: Polymorphic types will be out of the union declaration scope.
	// This breaks invariants until it is corrected later.
	for ( auto const & member : decl->members ) {
		auto dwt = member.strict_as<ast::DeclWithType>();
		ast::Type const * memberType = dwt->get_type();

		// Take max member size and global size.
		kids.emplace_back( makeAssignMax( location,
			derefVar( location, sizeofParam ),
			new ast::SizeofExpr( location, ast::deepCopy( memberType ) )
		) );

		// Take max of member alignment and global alignment.
		kids.emplace_back( makeAssignMax( location,
			derefVar( location, alignofParam ),
			new ast::AlignofExpr( location, ast::deepCopy( memberType ) )
		) );
	}
	kids.emplace_back( makeAlignTo( location,
		derefVar( location, sizeofParam ),
		derefVar( location, alignofParam ) ) );

	declsToAddAfter.emplace_back( layoutDecl );
}

// --------------------------------------------------------------------------
/// Application expression transformer.
/// * Replaces polymorphic return types with out-parameters.
/// * Replaces call to polymorphic functions with adapter calls which handles
///   dynamic arguments and return values.
/// * Adds appropriate type variables to the function calls.
struct CallAdapter final :
		public ast::WithConstTypeSubstitution,
		public ast::WithGuards,
		public ast::WithShortCircuiting,
		public ast::WithStmtsToAdd<>,
		public ast::WithVisitorRef<CallAdapter> {
	CallAdapter();

	void previsit( ast::Decl const * decl );
	ast::FunctionDecl const * previsit( ast::FunctionDecl const * decl );
	void previsit( ast::TypeDecl const * decl );
	void previsit( ast::CommaExpr const * expr );
	ast::Expr const * postvisit( ast::ApplicationExpr const * expr );
	ast::Expr const * postvisit( ast::UntypedExpr const * expr );
	void previsit( ast::AddressExpr const * expr );
	ast::Expr const * postvisit( ast::AddressExpr const * expr );
	ast::ReturnStmt const * previsit( ast::ReturnStmt const * stmt );

	void beginScope();
	void endScope();
private:
	// Many helpers here use a mutable ApplicationExpr as an in/out parameter
	// instead of using the return value, to save on mutates and free up the
	// return value.

	/// Passes extra layout arguments for sized polymorphic type parameters.
	void passTypeVars(
		ast::ApplicationExpr * expr,
		ast::vector<ast::Expr> & extraArgs,
		ast::FunctionType const * funcType );
	/// Wraps a function application with a new temporary for the
	/// out-parameter return value.
	ast::Expr const * addRetParam(
		ast::ApplicationExpr * expr, ast::Type const * retType );
	/// Wraps a function application returning a polymorphic type with a new
	/// temporary for the out-parameter return value.
	ast::Expr const * addDynRetParam(
		ast::ApplicationExpr * expr, ast::Type const * polyType );
	/// Modify a call so it passes the function through the correct adapter.
	ast::Expr const * applyAdapter(
		ast::ApplicationExpr * expr,
		ast::FunctionType const * function );
	/// Convert a single argument into its boxed form to pass the parameter.
	void boxParam( ast::ptr<ast::Expr> & arg,
		ast::Type const * formal, TypeVarMap const & exprTyVars );
	/// Box every argument from arg forward, matching the functionType
	/// parameter list. arg should point into expr's argument list.
	void boxParams(
		ast::ApplicationExpr * expr,
		ast::Type const * polyRetType,
		ast::FunctionType const * function,
		const TypeVarMap & typeVars );
	/// Adds the inferred parameters derived from the assertions of the
	/// expression to the call.
	void addInferredParams(
		ast::ApplicationExpr * expr,
		ast::vector<ast::Expr> & extraArgs,
		ast::FunctionType const * functionType,
		const TypeVarMap & typeVars );
	/// Stores assignment operators from assertion list in
	/// local map of assignment operations.
	void passAdapters(
		ast::ApplicationExpr * expr,
		ast::FunctionType const * type,
		const TypeVarMap & typeVars );
	/// Create an adapter function based on the type of the adaptee and the
	/// real type with the type substitutions applied.
	ast::FunctionDecl * makeAdapter(
		ast::FunctionType const * adaptee,
		ast::FunctionType const * realType,
		std::string const & mangleName,
		TypeVarMap const & typeVars,
		CodeLocation const & location ) const;
	/// Replaces intrinsic operator functions with their arithmetic desugaring.
	ast::Expr const * handleIntrinsics( ast::ApplicationExpr const * );
	/// Inserts a new temporary variable into the current scope with an
	/// auto-generated name.
	ast::ObjectDecl * makeTemporary(
		CodeLocation const & location, ast::Type const * type );

	TypeVarMap scopeTypeVars;
	ScopedMap< std::string, ast::DeclWithType const * > adapters;
	std::map< ast::ApplicationExpr const *, ast::Expr const * > retVals;
	ast::DeclWithType const * retval;
	UniqueName tmpNamer;
};

/// Replaces a polymorphic type with its concrete equivalant under the
/// current environment (returns itself if concrete).
/// If `doClone` is set to false, will not clone interior types
ast::Type const * replaceWithConcrete(
		ast::Type const * type,
		ast::TypeSubstitution const & typeSubs,
		bool doCopy = true );

/// Replaces all the type parameters of a generic type with their
/// concrete equivalents under the current environment.
void replaceParametersWithConcrete(
		ast::vector<ast::Expr> & params,
		ast::TypeSubstitution const & typeSubs ) {
	for ( ast::ptr<ast::Expr> & paramExpr : params ) {
		ast::TypeExpr const * param = paramExpr.as<ast::TypeExpr>();
		assertf( param, "Aggregate parameters should be type expressions." );
		paramExpr = ast::mutate_field( param, &ast::TypeExpr::type,
			replaceWithConcrete( param->type.get(), typeSubs, false ) );
	}
}

ast::Type const * replaceWithConcrete(
		ast::Type const * type,
		ast::TypeSubstitution const & typeSubs,
		bool doCopy ) {
	if ( auto instType = dynamic_cast<ast::TypeInstType const *>( type ) ) {
		ast::Type const * concrete = typeSubs.lookup( instType );
		return ( nullptr != concrete ) ? concrete : instType;
	} else if ( auto structType =
			dynamic_cast<ast::StructInstType const *>( type ) ) {
		ast::StructInstType * newType =
			doCopy ? ast::deepCopy( structType ) : ast::mutate( structType );
		replaceParametersWithConcrete( newType->params, typeSubs );
		return newType;
	} else if ( auto unionType =
			dynamic_cast<ast::UnionInstType const *>( type ) ) {
		ast::UnionInstType * newType =
			doCopy ? ast::deepCopy( unionType ) : ast::mutate( unionType );
		replaceParametersWithConcrete( newType->params, typeSubs );
		return newType;
	} else {
		return type;
	}
}

std::string makePolyMonoSuffix(
		ast::FunctionType const * function,
		TypeVarMap const & typeVars ) {
	// If the return type or a parameter type involved polymorphic types,
	// then the adapter will need to take those polymorphic types as pointers.
	// Therefore, there can be two different functions with the same mangled
	// name, so we need to further mangle the names.
	std::stringstream name;
	for ( auto ret : function->returns ) {
		name << ( isPolyType( ret, typeVars ) ? 'P' : 'M' );
	}
	name << '_';
	for ( auto arg : function->params ) {
		name << ( isPolyType( arg, typeVars ) ? 'P' : 'M' );
	}
	return name.str();
}

std::string mangleAdapterName(
		ast::FunctionType const * function,
		TypeVarMap const & typeVars ) {
	return Mangle::mangle( function, {} )
		+ makePolyMonoSuffix( function, typeVars );
}

std::string makeAdapterName( std::string const & mangleName ) {
	return "_adapter" + mangleName;
}

void makeRetParam( ast::FunctionType * type ) {
	ast::ptr<ast::Type> & retParam = type->returns.front();

	// Make a new parameter that is a pointer to the type of the old return value.
	retParam = new ast::PointerType( retParam.get() );
	type->params.emplace( type->params.begin(), retParam );

	// We don't need the return value any more.
	type->returns.clear();
}

ast::FunctionType * makeAdapterType(
		ast::FunctionType const * adaptee,
		TypeVarMap const & typeVars ) {
	assertf( ast::FixedArgs == adaptee->isVarArgs,
		"Cannot adapt a varadic function, should have been checked." );
	ast::FunctionType * adapter = ast::deepCopy( adaptee );
	if ( isDynRet( adapter, typeVars ) ) {
		makeRetParam( adapter );
	}
	adapter->params.emplace( adapter->params.begin(),
		new ast::PointerType( new ast::FunctionType( ast::VariableArgs ) )
	);
	return adapter;
}

CallAdapter::CallAdapter() : tmpNamer( "_temp" ) {}

void CallAdapter::previsit( ast::Decl const * ) {
	// Prevent type declaration information from leaking out.
	GuardScope( scopeTypeVars );
}

ast::FunctionDecl const * CallAdapter::previsit( ast::FunctionDecl const * decl ) {
	// Prevent type declaration information from leaking out.
	GuardScope( scopeTypeVars );

	if ( nullptr == decl->stmts ) {
		return decl;
	}

	GuardValue( retval );

	// Process polymorphic return value.
	retval = nullptr;
	ast::FunctionType const * type = decl->type;
	if ( isDynRet( type ) && decl->linkage != ast::Linkage::C ) {
		retval = decl->returns.front();

		// Give names to unnamed return values.
		if ( "" == retval->name ) {
			auto mutRet = ast::mutate( retval );
			mutRet->name = "_retparam";
			mutRet->linkage = ast::Linkage::C;
			retval = mutRet;
			decl = ast::mutate_field_index( decl,
				&ast::FunctionDecl::returns, 0, mutRet );
		}
	}

	// The formal_usage/expr_id values may be off if we get them from the
	// type, trying the declaration instead.
	makeTypeVarMap( type, scopeTypeVars );

	// Get all needed adapters from the call. We will forward them.
	ast::vector<ast::FunctionType> functions;
	for ( ast::ptr<ast::VariableExpr> const & assertion : type->assertions ) {
		auto atype = assertion->result.get();
		findFunction( atype, functions, scopeTypeVars, needsAdapter );
	}

	for ( ast::ptr<ast::Type> const & arg : type->params ) {
		findFunction( arg, functions, scopeTypeVars, needsAdapter );
	}

	for ( auto funcType : functions ) {
		std::string mangleName = mangleAdapterName( funcType, scopeTypeVars );
		if ( adapters.contains( mangleName ) ) continue;
		std::string adapterName = makeAdapterName( mangleName );
		// NODE: This creates floating nodes, breaking invariants.
		// This is corrected in the RewireAdapters sub-pass.
		adapters.insert(
			mangleName,
			new ast::ObjectDecl(
				decl->location,
				adapterName,
				new ast::PointerType(
					makeAdapterType( funcType, scopeTypeVars ) ),
				nullptr, // init
				ast::Storage::Classes(),
				ast::Linkage::C
			)
		);
	}

	return decl;
}

void CallAdapter::previsit( ast::TypeDecl const * decl ) {
	addToTypeVarMap( decl, scopeTypeVars );
}

void CallAdapter::previsit( ast::CommaExpr const * expr ) {
	// Attempting to find application expressions that were mutated by the
	// copy constructor passes to use an explicit return variable, so that
	// the variable can be reused as a parameter to the call rather than
	// creating a new temporary variable. Previously this step was an
	// optimization, but with the introduction of tuples and UniqueExprs,
	// it is necessary to ensure that they use the same variable.
	// Essentially, looking for pattern:
	// (x=f(...), x)
	// To compound the issue, the right side can be *x, etc.
	// because of lvalue-returning functions
	if ( auto assign = expr->arg1.as<ast::UntypedExpr>() ) {
		if ( CodeGen::isAssignment( ast::getFunctionName( assign ) ) ) {
			assert( 2 == assign->args.size() );
			if ( auto app = assign->args.back().as<ast::ApplicationExpr>() ) {
				// First argument is assignable, so it must be an lvalue,
				// so it should be legal to takes its address.
				retVals.insert_or_assign( app, assign->args.front() );
			}
		}
	}
}

ast::Expr const * CallAdapter::postvisit( ast::ApplicationExpr const * expr ) {
	assert( expr->func->result );
	ast::FunctionType const * function = getFunctionType( expr->func->result );
	assertf( function, "ApplicationExpr has non-function type %s",
			toCString( expr->func->result ) );

	if ( auto newExpr = handleIntrinsics( expr ) ) {
		return newExpr;
	}

	ast::ApplicationExpr * mutExpr = ast::mutate( expr );
	ast::Expr const * ret = expr;

	TypeVarMap exprTypeVars;
	makeTypeVarMap( function, exprTypeVars );
	auto dynRetType = isDynRet( function, exprTypeVars );

	// NOTE: addDynRetParam needs to know the actual (generated) return type
	// so it can make a temporary variable, so pass the result type form the
	// `expr` `passTypeVars` needs to know the program-text return type ([ex]
	// the distinction between _conc_T30 and T3(int)) concRetType may not be
	// a good name in one or both of these places.
	if ( dynRetType ) {
		ast::Type const * result = mutExpr->result;
		ast::Type const * concRetType = result->isVoid() ? nullptr : result;
		// [Comment from before translation.]
		// Used to use dynRetType instead of concRetType.
		ret = addDynRetParam( mutExpr, concRetType );
	} else if ( needsAdapter( function, scopeTypeVars )
			&& !needsAdapter( function, exprTypeVars ) ) {
		// Change the application so it calls the adapter rather than the
		// passed function.
		ret = applyAdapter( mutExpr, function );
	}

	ast::vector<ast::Expr> prependArgs;
	passTypeVars( mutExpr, prependArgs, function );
	addInferredParams( mutExpr, prependArgs, function, exprTypeVars );

	boxParams( mutExpr, dynRetType, function, exprTypeVars );
	spliceBegin( mutExpr->args, prependArgs );
	passAdapters( mutExpr, function, exprTypeVars );

	return ret;
}

// Get the referent (base type of pointer). Must succeed.
ast::Type const * getReferentType( ast::ptr<ast::Type> const & type ) {
	auto pointerType = type.strict_as<ast::PointerType>();
	assertf( pointerType->base, "getReferentType: pointer base is nullptr." );
	return pointerType->base.get();
}

bool isPolyDeref( ast::UntypedExpr const * expr,
		TypeVarMap const & typeVars,
		ast::TypeSubstitution const * typeSubs ) {
	auto name = expr->func.as<ast::NameExpr>();
	if ( name && "*?" == name->name ) {
		// It's a deref.
		// Must look under the * (and strip its ptr-ty) because expr's
		// result could be ar/ptr-decayed.  If expr.inner:T(*)[n], then
		// expr is a poly deref, even though expr:T*, which is not poly.
		auto referentType = getReferentType( expr->args.front()->result );
		return isPolyType( referentType, typeVars, typeSubs );
	}
	return false;
}

ast::Expr const * CallAdapter::postvisit( ast::UntypedExpr const * expr ) {
	if ( isPolyDeref( expr, scopeTypeVars, typeSubs ) ) {
		return expr->args.front();
	}
	return expr;
}

void CallAdapter::previsit( ast::AddressExpr const * ) {
	visit_children = false;
}

ast::Expr const * CallAdapter::postvisit( ast::AddressExpr const * expr ) {
	assert( expr->arg->result );
	assert( !expr->arg->result->isVoid() );

	bool doesNeedAdapter = false;
	if ( auto un = expr->arg.as<ast::UntypedExpr>() ) {
		if ( isPolyDeref( un, scopeTypeVars, typeSubs ) ) {
			if ( auto app = un->args.front().as<ast::ApplicationExpr>() ) {
				assert( app->func->result );
				auto function = getFunctionType( app->func->result );
				assert( function );
				doesNeedAdapter = needsAdapter( function, scopeTypeVars );
			}
		}
	}
	// isPolyType check needs to happen before mutating expr arg,
	// so pull it forward out of the if condition.
	expr = ast::mutate_field( expr, &ast::AddressExpr::arg,
			expr->arg->accept( *visitor ) );
	// But must happen after mutate, since argument might change
	// (ex. intrinsic *?, ?[?]) re-evaluate above comment.
	bool polyType = isPolyType( expr->arg->result, scopeTypeVars, typeSubs );
	if ( polyType || doesNeedAdapter ) {
		ast::Expr * ret = ast::mutate( expr->arg.get() );
		ret->result = ast::deepCopy( expr->result );
		return ret;
	} else {
		return expr;
	}
}

ast::ReturnStmt const * CallAdapter::previsit( ast::ReturnStmt const * stmt ) {
	// Since retval is set when the return type is dynamic, this function
	// should have been converted to void return & out parameter.
	if ( retval && stmt->expr ) {
		assert( stmt->expr->result );
		assert( !stmt->expr->result->isVoid() );
		return ast::mutate_field( stmt, &ast::ReturnStmt::expr, nullptr );
	}
	return stmt;
}

void CallAdapter::beginScope() {
	adapters.beginScope();
}

void CallAdapter::endScope() {
	adapters.endScope();
}

/// Find instances of polymorphic type parameters.
struct PolyFinder {
	TypeVarMap const & typeVars;
	bool result = false;
	PolyFinder( TypeVarMap const & tvs ) : typeVars( tvs ) {}

	void previsit( ast::TypeInstType const * type ) {
		if ( isPolyType( type, typeVars ) ) result = true;
	}
};

/// True if these is an instance of a polymorphic type parameter in the type.
bool hasPolymorphism( ast::Type const * type, TypeVarMap const & typeVars ) {
	return ast::Pass<PolyFinder>::read( type, typeVars );
}

void CallAdapter::passTypeVars(
		ast::ApplicationExpr * expr,
		ast::vector<ast::Expr> & extraArgs,
		ast::FunctionType const * function ) {
	assert( typeSubs );
	// Pass size/align for type variables.
	for ( ast::ptr<ast::TypeInstType> const & typeVar : function->forall ) {
		if ( !typeVar->base->isComplete() ) continue;
		ast::Type const * concrete = typeSubs->lookup( typeVar );
		if ( !concrete ) {
			// Should this be an assertion?
			SemanticError( expr->location, "\nunbound type variable %s in application %s",
						   toString( typeSubs ).c_str(), typeVar->typeString().c_str() );
		}
		extraArgs.emplace_back(
			new ast::SizeofExpr( expr->location, ast::deepCopy( concrete ) ) );
		extraArgs.emplace_back(
			new ast::AlignofExpr( expr->location, ast::deepCopy( concrete ) ) );
	}
}

ast::Expr const * CallAdapter::addRetParam(
		ast::ApplicationExpr * expr, ast::Type const * retType ) {
	// Create temporary to hold return value of polymorphic function and
	// produce that temporary as a result using a comma expression.
	assert( retType );

	ast::Expr * paramExpr = nullptr;
	// Try to use existing return value parameter if it exists,
	// otherwise create a new temporary.
	if ( retVals.count( expr ) ) {
		paramExpr = ast::deepCopy( retVals[ expr ] );
	} else {
		auto newObj = makeTemporary( expr->location, ast::deepCopy( retType ) );
		paramExpr = new ast::VariableExpr( expr->location, newObj );
	}
	ast::Expr * retExpr = ast::deepCopy( paramExpr );

	// If the type of the temporary is not polpmorphic, box temporary by
	// taking its address; otherwise the temporary is already boxed and can
	// be used directly.
	if ( !isPolyType( paramExpr->result, scopeTypeVars, typeSubs ) ) {
		paramExpr = new ast::AddressExpr( paramExpr->location, paramExpr );
	}
	// Add argument to function call.
	expr->args.insert( expr->args.begin(), paramExpr );
	// Build a comma expression to call the function and return a value.
	ast::CommaExpr * comma = new ast::CommaExpr(
		expr->location, expr, retExpr );
	comma->env = expr->env;
	expr->env = nullptr;
	return comma;
}

ast::Expr const * CallAdapter::addDynRetParam(
		ast::ApplicationExpr * expr, ast::Type const * polyType ) {
	assert( typeSubs );
	ast::Type const * concrete = replaceWithConcrete( polyType, *typeSubs );
	// Add out-parameter for return value.
	return addRetParam( expr, concrete );
}

ast::Expr const * CallAdapter::applyAdapter(
		ast::ApplicationExpr * expr,
		ast::FunctionType const * function ) {
	ast::Expr const * ret = expr;
	if ( isDynRet( function, scopeTypeVars ) ) {
		ret = addRetParam( expr, function->returns.front() );
	}
	std::string mangleName = mangleAdapterName( function, scopeTypeVars );
	std::string adapterName = makeAdapterName( mangleName );

	// Cast adaptee to `void (*)()`, since it may have any type inside a
	// polymorphic function.
	ast::Type const * adapteeType = new ast::PointerType(
		new ast::FunctionType( ast::VariableArgs ) );
	expr->args.insert( expr->args.begin(),
		new ast::CastExpr( expr->location, expr->func, adapteeType ) );
	// The result field is never set on NameExpr. / Now it is.
	auto head = new ast::NameExpr( expr->location, adapterName );
	head->result = ast::deepCopy( adapteeType );
	expr->func = head;

	return ret;
}

/// Cast parameters to polymorphic functions so that types are replaced with
/// `void *` if they are type parameters in the formal type.
/// This gets rid of warnings from gcc.
void addCast(
		ast::ptr<ast::Expr> & actual,
		ast::Type const * formal,
		TypeVarMap const & typeVars ) {
	// Type contains polymorphism, but isn't exactly a polytype, in which
	// case it has some real actual type (ex. unsigned int) and casting to
	// `void *` is wrong.
	if ( hasPolymorphism( formal, typeVars )
			&& !isPolyType( formal, typeVars ) ) {
		ast::Type const * newType = ast::deepCopy( formal );
		newType = scrubTypeVars( newType, typeVars );
		actual = new ast::CastExpr( actual->location, actual, newType );
	}
}

void CallAdapter::boxParam( ast::ptr<ast::Expr> & arg,
		ast::Type const * param, TypeVarMap const & exprTypeVars ) {
	assertf( arg->result, "arg does not have result: %s", toCString( arg ) );
	addCast( arg, param, exprTypeVars );
	if ( !needsBoxing( param, arg->result, exprTypeVars, typeSubs ) ) {
		return;
	}
	CodeLocation const & location = arg->location;

	if ( arg->get_lvalue() ) {
		// The argument expression may be CFA lvalue, but not C lvalue,
		// so apply generalizedLvalue transformations.
		// if ( auto var = dynamic_cast<ast::VariableExpr const *>( arg ) ) {
		//  if ( dynamic_cast<ast::ArrayType const *>( varExpr->var->get_type() ) ){
		//      // temporary hack - don't box arrays, because &arr is not the same as &arr[0]
		//      return;
		//  }
		// }
		arg = generalizedLvalue( new ast::AddressExpr( arg->location, arg ) );
		if ( !ResolvExpr::typesCompatible( param, arg->result ) ) {
			// Silence warnings by casting boxed parameters when the actually
			// type does not match up with the formal type.
			arg = new ast::CastExpr( location, arg, ast::deepCopy( param ) );
		}
	} else {
		// Use type computed in unification to declare boxed variables.
		ast::ptr<ast::Type> newType = ast::deepCopy( param );
		if ( typeSubs ) typeSubs->apply( newType );
		ast::ObjectDecl * newObj = makeTemporary( location, newType );
		auto assign = ast::UntypedExpr::createCall( location, "?=?", {
			new ast::VariableExpr( location, newObj ),
			arg,
		} );
		stmtsToAddBefore.push_back( new ast::ExprStmt( location, assign ) );
		arg = new ast::AddressExpr(
			new ast::VariableExpr( location, newObj ) );
	}
}

void CallAdapter::boxParams(
		ast::ApplicationExpr * expr,
		ast::Type const * polyRetType,
		ast::FunctionType const * function,
		const TypeVarMap & typeVars ) {
	// Start at the beginning, but the return argument may have been added.
	auto arg = expr->args.begin();
	if ( polyRetType ) ++arg;

	for ( auto param : function->params ) {
		assertf( arg != expr->args.end(),
			"boxParams: missing argument for param %s to %s in %s",
			toCString( param ), toCString( function ), toCString( expr ) );
		boxParam( *arg, param, typeVars );
		++arg;
	}
}

void CallAdapter::addInferredParams(
		ast::ApplicationExpr * expr,
		ast::vector<ast::Expr> & extraArgs,
		ast::FunctionType const * functionType,
		TypeVarMap const & typeVars ) {
	for ( auto assertion : functionType->assertions ) {
		auto inferParam = expr->inferred.inferParams().find(
			assertion->var->uniqueId );
		assertf( inferParam != expr->inferred.inferParams().end(),
			"addInferredParams missing inferred parameter: %s in: %s",
			toCString( assertion ), toCString( expr ) );
		ast::ptr<ast::Expr> newExpr = ast::deepCopy( inferParam->second.expr );
		boxParam( newExpr, assertion->result, typeVars );
		extraArgs.emplace_back( newExpr.release() );
	}
}

/// Modifies the ApplicationExpr to accept adapter functions for its
/// assertion and parameters, declares the required adapters.
void CallAdapter::passAdapters(
		ast::ApplicationExpr * expr,
		ast::FunctionType const * type,
		const TypeVarMap & exprTypeVars ) {
	// Collect a list of function types passed as parameters or implicit
	// parameters (assertions).
	ast::vector<ast::Type> const & paramList = type->params;
	ast::vector<ast::FunctionType> functions;

	for ( ast::ptr<ast::VariableExpr> const & assertion : type->assertions ) {
		findFunction( assertion->result, functions, exprTypeVars, needsAdapter );
	}
	for ( ast::ptr<ast::Type> const & arg : paramList ) {
		findFunction( arg, functions, exprTypeVars, needsAdapter );
	}

	// Parameter function types for which an appropriate adapter has been
	// generated. We cannot use the types after applying substitutions,
	// since two different parameter types may be unified to the same type.
	std::set<std::string> adaptersDone;

	CodeLocation const & location = expr->location;

	for ( ast::ptr<ast::FunctionType> const & funcType : functions ) {
		std::string mangleName = Mangle::mangle( funcType );

		// Only attempt to create an adapter or pass one as a parameter if we
		// haven't already done so for this pre-substitution parameter
		// function type.
		// The second part of the result if is if the element was inserted.
		if ( !adaptersDone.insert( mangleName ).second ) continue;

		// Apply substitution to type variables to figure out what the
		// adapter's type should look like. (Copy to make the release safe.)
		assert( typeSubs );
		auto result = typeSubs->apply( ast::deepCopy( funcType ) );
		ast::FunctionType * realType = ast::mutate( result.node.release() );
		mangleName = Mangle::mangle( realType );
		mangleName += makePolyMonoSuffix( funcType, exprTypeVars );

		// Check if the adapter has already been created, or has to be.
		using AdapterIter = decltype(adapters)::iterator;
		AdapterIter adapter = adapters.find( mangleName );
		if ( adapter == adapters.end() ) {
			ast::FunctionDecl * newAdapter = makeAdapter(
				funcType, realType, mangleName, exprTypeVars, location );
			std::pair<AdapterIter, bool> answer =
				adapters.insert( mangleName, newAdapter );
			adapter = answer.first;
			stmtsToAddBefore.push_back(
				new ast::DeclStmt( location, newAdapter ) );
		}
		assert( adapter != adapters.end() );

		// Add the approprate adapter as a parameter.
		expr->args.insert( expr->args.begin(),
			new ast::VariableExpr( location, adapter->second ) );
	}
}

// Parameter and argument may be used wrong around here.
ast::Expr * makeAdapterArg(
		ast::DeclWithType const * param,
		ast::Type const * arg,
		ast::Type const * realParam,
		TypeVarMap const & typeVars,
		CodeLocation const & location ) {
	assert( param );
	assert( arg );
	assert( realParam );
	if ( isPolyType( realParam, typeVars ) && !isPolyType( arg ) ) {
		ast::UntypedExpr * deref = ast::UntypedExpr::createDeref(
			location,
			new ast::CastExpr( location,
				new ast::VariableExpr( location, param ),
				new ast::PointerType( ast::deepCopy( arg ) )
			)
		);
		deref->result = ast::deepCopy( arg );
		return deref;
	}
	return new ast::VariableExpr( location, param );
}

// This seems to be one of the problematic functions.
void addAdapterParams(
		ast::ApplicationExpr * adaptee,
		ast::vector<ast::Type>::const_iterator arg,
		ast::vector<ast::DeclWithType>::iterator param,
		ast::vector<ast::DeclWithType>::iterator paramEnd,
		ast::vector<ast::Type>::const_iterator realParam,
		TypeVarMap const & typeVars,
		CodeLocation const & location ) {
	UniqueName paramNamer( "_p" );
	for ( ; param != paramEnd ; ++param, ++arg, ++realParam ) {
		if ( "" == (*param)->name ) {
			auto mutParam = (*param).get_and_mutate();
			mutParam->name = paramNamer.newName();
			mutParam->linkage = ast::Linkage::C;
		}
		adaptee->args.push_back(
			makeAdapterArg( *param, *arg, *realParam, typeVars, location ) );
	}
}

ast::FunctionDecl * CallAdapter::makeAdapter(
		ast::FunctionType const * adaptee,
		ast::FunctionType const * realType,
		std::string const & mangleName,
		TypeVarMap const & typeVars,
		CodeLocation const & location ) const {
	ast::FunctionType * adapterType = makeAdapterType( adaptee, typeVars );
	adapterType = ast::mutate( scrubTypeVars( adapterType, typeVars ) );

	// Some of these names will be overwritten, but it gives a default.
	UniqueName pNamer( "_param" );
	UniqueName rNamer( "_ret" );

	bool first = true;

	ast::FunctionDecl * adapterDecl = new ast::FunctionDecl( location,
		makeAdapterName( mangleName ),
		{}, // forall
		{}, // assertions
		map_range<ast::vector<ast::DeclWithType>>( adapterType->params,
				[&pNamer, &location, &first]( ast::ptr<ast::Type> const & param ) {
			// [Trying to make the generated code match exactly more often.]
			if ( first ) {
				first = false;
				return new ast::ObjectDecl( location, "_adaptee", param );
			}
			return new ast::ObjectDecl( location, pNamer.newName(), param );
		} ),
		map_range<ast::vector<ast::DeclWithType>>( adapterType->returns,
				[&rNamer, &location]( ast::ptr<ast::Type> const & retval ) {
			return new ast::ObjectDecl( location, rNamer.newName(), retval );
		} ),
		nullptr, // stmts
		{}, // storage
		ast::Linkage::C
	);

	ast::DeclWithType * adapteeDecl =
		adapterDecl->params.front().get_and_mutate();
	adapteeDecl->name = "_adaptee";

	// Do not carry over attributes to real type parameters/return values.
	auto mutRealType = ast::mutate( realType );
	for ( ast::ptr<ast::Type> & decl : mutRealType->params ) {
		if ( decl->attributes.empty() ) continue;
		auto mut = ast::mutate( decl.get() );
		mut->attributes.clear();
		decl = mut;
	}
	for ( ast::ptr<ast::Type> & decl : mutRealType->returns ) {
		if ( decl->attributes.empty() ) continue;
		auto mut = ast::mutate( decl.get() );
		mut->attributes.clear();
		decl = mut;
	}
	realType = mutRealType;

	ast::ApplicationExpr * adapteeApp = new ast::ApplicationExpr( location,
		new ast::CastExpr( location,
			new ast::VariableExpr( location, adapteeDecl ),
			new ast::PointerType( realType )
		)
	);

	for ( auto const & [assertArg, assertParam, assertReal] : group_iterate(
			realType->assertions, adapterType->assertions, adaptee->assertions ) ) {
		adapteeApp->args.push_back( makeAdapterArg(
			assertParam->var, assertArg->var->get_type(),
			assertReal->var->get_type(), typeVars, location
		) );
	}

	ast::vector<ast::Type>::const_iterator
		arg = realType->params.begin(),
		param = adapterType->params.begin(),
		realParam = adaptee->params.begin();
	ast::vector<ast::DeclWithType>::iterator
		paramDecl = adapterDecl->params.begin();
	// Skip adaptee parameter in the adapter type.
	++param;
	++paramDecl;

	ast::Stmt * bodyStmt;
	// Returns void/nothing.
	if ( realType->returns.empty() ) {
		addAdapterParams( adapteeApp, arg, paramDecl, adapterDecl->params.end(),
			realParam, typeVars, location );
		bodyStmt = new ast::ExprStmt( location, adapteeApp );
	// Returns a polymorphic type.
	} else if ( isDynType( adaptee->returns.front(), typeVars ) ) {
		ast::UntypedExpr * assign = new ast::UntypedExpr( location,
			new ast::NameExpr( location, "?=?" ) );
		ast::UntypedExpr * deref = ast::UntypedExpr::createDeref( location,
			new ast::CastExpr( location,
				new ast::VariableExpr( location, *paramDecl++ ),
				new ast::PointerType(
					ast::deepCopy( realType->returns.front() ) ) ) );
		assign->args.push_back( deref );
		addAdapterParams( adapteeApp, arg, paramDecl, adapterDecl->params.end(),
			realParam, typeVars, location );
		assign->args.push_back( adapteeApp );
		bodyStmt = new ast::ExprStmt( location, assign );
	// Adapter for a function that returns a monomorphic value.
	} else {
		addAdapterParams( adapteeApp, arg, paramDecl, adapterDecl->params.end(),
				realParam, typeVars, location );
		bodyStmt = new ast::ReturnStmt( location, adapteeApp );
	}

	adapterDecl->stmts = new ast::CompoundStmt( location, { bodyStmt } );
	return adapterDecl;
}

ast::Expr const * makeIncrDecrExpr(
		CodeLocation const & location,
		ast::ApplicationExpr const * expr,
		ast::Type const * polyType,
		bool isIncr ) {
	ast::NameExpr * opExpr =
			new ast::NameExpr( location, isIncr ? "?+=?" : "?-=?" );
	ast::UntypedExpr * addAssign = new ast::UntypedExpr( location, opExpr );
	if ( auto address = expr->args.front().as<ast::AddressExpr>() ) {
		addAssign->args.push_back( address->arg );
	} else {
		addAssign->args.push_back( expr->args.front() );
	}
	addAssign->args.push_back( new ast::NameExpr( location,
		sizeofName( Mangle::mangleType( polyType ) ) ) );
	addAssign->result = ast::deepCopy( expr->result );
	addAssign->env = expr->env ? expr->env : addAssign->env;
	return addAssign;
}

/// Handles intrinsic functions for postvisit ApplicationExpr.
ast::Expr const * CallAdapter::handleIntrinsics(
		ast::ApplicationExpr const * expr ) {
	auto varExpr = expr->func.as<ast::VariableExpr>();
	if ( !varExpr || varExpr->var->linkage != ast::Linkage::Intrinsic ) {
		return nullptr;
	}
	std::string const & varName = varExpr->var->name;

	// Index Intrinsic:
	if ( "?[?]" == varName ) {
		assert( expr->result );
		assert( 2 == expr->args.size() );

		ast::ptr<ast::Type> const & argType1 = expr->args.front()->result;
		ast::ptr<ast::Type> const & argType2 = expr->args.back()->result;

		// Two Cases: a[i] with first arg poly ptr, i[a] with second arg poly ptr
		bool isPoly1 = isPolyPtr( argType1, scopeTypeVars, typeSubs ) != nullptr;
		bool isPoly2 = isPolyPtr( argType2, scopeTypeVars, typeSubs ) != nullptr;

		// If neither argument is a polymorphic pointer, do nothing.
		if ( !isPoly1 && !isPoly2 ) {
			return expr;
		}
		// The arguments cannot both be polymorphic pointers.
		assert( !isPoly1 || !isPoly2 );
		// (So exactly one of the arguments is a polymorphic pointer.)

		CodeLocation const & location = expr->location;
		CodeLocation const & location1 = expr->args.front()->location;
		CodeLocation const & location2 = expr->args.back()->location;

		ast::UntypedExpr * ret = new ast::UntypedExpr( location,
				new ast::NameExpr( location, "?+?" ) );
		if ( isPoly1 ) {
			auto referentType = getReferentType( argType1 );
			auto multiply = ast::UntypedExpr::createCall( location2, "?*?", {
				expr->args.back(),
				new ast::SizeofExpr( location1, deepCopy( referentType ) ),
			} );
			ret->args.push_back( expr->args.front() );
			ret->args.push_back( multiply );
		} else {
			assert( isPoly2 );
			auto referentType = getReferentType( argType2 );
			auto multiply = ast::UntypedExpr::createCall( location1, "?*?", {
				expr->args.front(),
				new ast::SizeofExpr( location2, deepCopy( referentType ) ),
			} );
			ret->args.push_back( multiply );
			ret->args.push_back( expr->args.back() );
		}
		ret->result = ast::deepCopy( expr->result );
		ret->env = expr->env ? expr->env : ret->env;
		return ret;
	// Dereference Intrinsic:
	} else if ( "*?" == varName ) {
		assert( expr->result );
		assert( 1 == expr->args.size() );

		// If this isn't for a poly type, then do nothing.
		auto referentType = getReferentType( expr->args.front()->result );
		if ( !isPolyType( referentType, scopeTypeVars, typeSubs ) ) {
			return expr;
		}

		// Remove dereference from polymorphic types since they are boxed.
		ast::Expr * ret = ast::deepCopy( expr->args.front() );
		// Fix expression type to remove pointer.
		ret->result = expr->result;
		// apply pointer decay
		if (auto retArTy = ret->result.as<ast::ArrayType>()) {
			ret->result = new ast::PointerType( retArTy->base );
		}
		ret->env = expr->env ? expr->env : ret->env;
		return ret;
	// Post-Increment/Decrement Intrinsics:
	} else if ( "?++" == varName || "?--" == varName ) {
		assert( expr->result );
		assert( 1 == expr->args.size() );

		ast::Type const * baseType =
			isPolyType( expr->result, scopeTypeVars, typeSubs );
		if ( nullptr == baseType ) {
			return expr;
		}
		ast::Type * tempType = ast::deepCopy( expr->result );
		if ( typeSubs ) {
			auto result = typeSubs->apply( tempType );
			tempType = ast::mutate( result.node.release() );
		}
		CodeLocation const & location = expr->location;
		ast::ObjectDecl * newObj = makeTemporary( location, tempType );
		ast::VariableExpr * tempExpr =
			new ast::VariableExpr( location, newObj );
		ast::UntypedExpr * assignExpr = new ast::UntypedExpr( location,
			new ast::NameExpr( location, "?=?" ) );
		assignExpr->args.push_back( ast::deepCopy( tempExpr ) );
		if ( auto address = expr->args.front().as<ast::AddressExpr>() ) {
			assignExpr->args.push_back( ast::deepCopy( address->arg ) );
		} else {
			assignExpr->args.push_back( ast::deepCopy( expr->args.front() ) );
		}
		return new ast::CommaExpr( location,
			new ast::CommaExpr( location,
				assignExpr,
				makeIncrDecrExpr( location, expr, baseType, "?++" == varName )
			),
			tempExpr
		);
	// Pre-Increment/Decrement Intrinsics:
	} else if ( "++?" == varName || "--?" == varName ) {
		assert( expr->result );
		assert( 1 == expr->args.size() );

		ast::Type const * baseType =
			isPolyType( expr->result, scopeTypeVars, typeSubs );
		if ( nullptr == baseType ) {
			return expr;
		}
		return makeIncrDecrExpr(
			expr->location, expr, baseType, "++?" == varName );
	// Addition and Subtraction Intrinsics:
	} else if ( "?+?" == varName || "?-?" == varName ) {
		assert( expr->result );
		assert( 2 == expr->args.size() );

		ast::ptr<ast::Type> const & argType1 = expr->args.front()->result;
		ast::ptr<ast::Type> const & argType2 = expr->args.back()->result;

		bool isPoly1 = isPolyPtr( argType1, scopeTypeVars, typeSubs ) != nullptr;
		bool isPoly2 = isPolyPtr( argType2, scopeTypeVars, typeSubs ) != nullptr;

		CodeLocation const & location = expr->location;
		CodeLocation const & location1 = expr->args.front()->location;
		CodeLocation const & location2 = expr->args.back()->location;
		// LHS - RHS -> (LHS - RHS) / sizeof(LHS)
		if ( isPoly1 && isPoly2 ) {
			// There are only subtraction intrinsics for this pattern.
			assert( "?-?" == varName );
			auto referentType = getReferentType( argType1 );
			auto divide = ast::UntypedExpr::createCall( location, "?/?", {
				expr,
				new ast::SizeofExpr( location, deepCopy( referentType ) ),
			} );
			if ( expr->env ) divide->env = expr->env;
			return divide;
		// LHS op RHS -> LHS op (RHS * sizeof(LHS))
		} else if ( isPoly1 ) {
			auto referentType = getReferentType( argType1 );
			auto multiply = ast::UntypedExpr::createCall( location2, "?*?", {
				expr->args.back(),
				new ast::SizeofExpr( location1, deepCopy( referentType ) ),
			} );
			return ast::mutate_field_index(
				expr, &ast::ApplicationExpr::args, 1, multiply );
		// LHS op RHS -> (LHS * sizeof(RHS)) op RHS
		} else if ( isPoly2 ) {
			auto referentType = getReferentType( argType2 );
			auto multiply = ast::UntypedExpr::createCall( location1, "?*?", {
				expr->args.front(),
				new ast::SizeofExpr( location2, deepCopy( referentType ) ),
			} );
			return ast::mutate_field_index(
				expr, &ast::ApplicationExpr::args, 0, multiply );
		}
	// Addition and Subtraction Relative Assignment Intrinsics:
	} else if ( "?+=?" == varName || "?-=?" == varName ) {
		assert( expr->result );
		assert( 2 == expr->args.size() );

		CodeLocation const & location1 = expr->args.front()->location;
		CodeLocation const & location2 = expr->args.back()->location;
		auto baseType = isPolyPtr( expr->result, scopeTypeVars, typeSubs );
		// LHS op RHS -> LHS op (RHS * sizeof(LHS))
		if ( baseType ) {
			auto multiply = ast::UntypedExpr::createCall( location2, "?*?", {
				expr->args.back(),
				new ast::SizeofExpr( location1, deepCopy( baseType ) ),
			} );
			return ast::mutate_field_index(
				expr, &ast::ApplicationExpr::args, 1, multiply );
		}
	}
	return expr;
}

ast::ObjectDecl * CallAdapter::makeTemporary(
		CodeLocation const & location, ast::Type const * type ) {
	auto newObj = new ast::ObjectDecl( location, tmpNamer.newName(), type );
	stmtsToAddBefore.push_back( new ast::DeclStmt( location, newObj ) );
	return newObj;
}

// --------------------------------------------------------------------------
/// Modifies declarations to accept implicit parameters.
/// * Move polymorphic returns in function types to pointer-type parameters.
/// * Adds type size and assertion parameters to parameter lists.
struct DeclAdapter final {
	ast::FunctionDecl const * previsit( ast::FunctionDecl const * decl );
	ast::FunctionDecl const * postvisit( ast::FunctionDecl const * decl );
private:
	void addAdapters( ast::FunctionDecl * decl, TypeVarMap & localTypeVars );
};

ast::ObjectDecl * makeObj(
		CodeLocation const & location, std::string const & name ) {
	// The size/align parameters may be unused, so add the unused attribute.
	return new ast::ObjectDecl( location, name,
		makeLayoutCType(),
		nullptr, ast::Storage::Classes(), ast::Linkage::C, nullptr,
		{ new ast::Attribute( "unused" ) } );
}

/// A modified and specialized version of ast::add_qualifiers.
ast::Type const * addConst( ast::Type const * type ) {
	ast::CV::Qualifiers cvq = { ast::CV::Const };
	if ( ( type->qualifiers & cvq ) != 0 ) return type;
	auto mutType = ast::mutate( type );
	mutType->qualifiers |= cvq;
	return mutType;
}

ast::FunctionDecl const * DeclAdapter::previsit( ast::FunctionDecl const * decl ) {
	TypeVarMap localTypeVars;
	makeTypeVarMap( decl, localTypeVars );

	auto mutDecl = mutate( decl );

	// Move polymorphic return type to parameter list.
	if ( isDynRet( mutDecl->type ) ) {
		auto ret = strict_dynamic_cast<ast::ObjectDecl *>(
			mutDecl->returns.front().get_and_mutate() );
		ret->set_type( new ast::PointerType( ret->type ) );
		mutDecl->params.insert( mutDecl->params.begin(), ret );
		mutDecl->returns.erase( mutDecl->returns.begin() );
		ret->init = nullptr;
	}

	// Add size/align and assertions for type parameters to parameter list.
	ast::vector<ast::DeclWithType> inferredParams;
	ast::vector<ast::DeclWithType> layoutParams;
	for ( ast::ptr<ast::TypeDecl> & typeParam : mutDecl->type_params ) {
		auto mutParam = mutate( typeParam.get() );
		// Add all size and alignment parameters to parameter list.
		if ( mutParam->isComplete() ) {
			ast::TypeInstType paramType( mutParam );
			std::string paramName = Mangle::mangleType( &paramType );

			auto sizeParam = makeObj( typeParam->location, sizeofName( paramName ) );
			layoutParams.emplace_back( sizeParam );

			auto alignParam = makeObj( typeParam->location, alignofName( paramName ) );
			layoutParams.emplace_back( alignParam );
		}
		// Assertions should be stored in the main list.
		assert( mutParam->assertions.empty() );
		typeParam = mutParam;
	}
	for ( ast::ptr<ast::DeclWithType> & assert : mutDecl->assertions ) {
		ast::DeclWithType * mutAssert = ast::mutate( assert.get() );
		// Assertion parameters may not be used in body,
		// pass along with unused attribute.
		mutAssert->attributes.push_back( new ast::Attribute( "unused" ) );
		mutAssert->set_type( addConst( mutAssert->get_type() ) );
		inferredParams.emplace_back( mutAssert );
	}
	mutDecl->assertions.clear();

	// Prepend each argument group. From last group to first. addAdapters
	// does do the same, it just does it itself and see all other parameters.
	spliceBegin( mutDecl->params, inferredParams );
	spliceBegin( mutDecl->params, layoutParams );
	addAdapters( mutDecl, localTypeVars );

	// Now have to update the type to match the declaration.
	ast::FunctionType * type = new ast::FunctionType(
		mutDecl->type->isVarArgs, mutDecl->type->qualifiers );
	// The forall clauses don't match until Eraser. The assertions are empty.
	for ( auto param : mutDecl->params ) {
		type->params.emplace_back( param->get_type() );
	}
	for ( auto retval : mutDecl->returns ) {
		type->returns.emplace_back( retval->get_type() );
	}
	mutDecl->type = type;

	return mutDecl;
}

ast::FunctionDecl const * DeclAdapter::postvisit(
		ast::FunctionDecl const * decl ) {
	ast::FunctionDecl * mutDecl = mutate( decl );
	if ( !mutDecl->returns.empty() && mutDecl->stmts
			// Intrinsic functions won't be using the _retval so no need to
			// generate it.
			&& mutDecl->linkage != ast::Linkage::Intrinsic
			// Remove check for prefix once thunks properly use ctor/dtors.
			&& !isPrefix( mutDecl->name, "_thunk" )
			&& !isPrefix( mutDecl->name, "_adapter" ) ) {
		assert( 1 == mutDecl->returns.size() );
		ast::DeclWithType const * retval = mutDecl->returns.front();
		if ( "" == retval->name ) {
			retval = ast::mutate_field(
				retval, &ast::DeclWithType::name, "_retval" );
			mutDecl->returns.front() = retval;
		}
		auto stmts = mutDecl->stmts.get_and_mutate();
		stmts->kids.push_front( new ast::DeclStmt( retval->location, retval ) );
		ast::DeclWithType * newRet = ast::deepCopy( retval );
		mutDecl->returns.front() = newRet;
	}
	// Errors should have been caught by this point, remove initializers from
	// parameters to allow correct codegen of default arguments.
	for ( ast::ptr<ast::DeclWithType> & param : mutDecl->params ) {
		if ( auto obj = param.as<ast::ObjectDecl>() ) {
			param = ast::mutate_field( obj, &ast::ObjectDecl::init, nullptr );
		}
	}
	return mutDecl;
}

void DeclAdapter::addAdapters(
		ast::FunctionDecl * mutDecl, TypeVarMap & localTypeVars ) {
	ast::vector<ast::FunctionType> functions;
	for ( ast::ptr<ast::DeclWithType> & arg : mutDecl->params ) {
		ast::Type const * type = arg->get_type();
		type = findAndReplaceFunction( type, functions, localTypeVars, needsAdapter );
		arg.get_and_mutate()->set_type( type );
	}
	std::set<std::string> adaptersDone;
	for ( ast::ptr<ast::FunctionType> const & func : functions ) {
		std::string mangleName = mangleAdapterName( func, localTypeVars );
		if ( adaptersDone.find( mangleName ) != adaptersDone.end() ) {
			continue;
		}
		std::string adapterName = makeAdapterName( mangleName );
		// The adapter may not actually be used, so make sure it has unused.
		mutDecl->params.insert( mutDecl->params.begin(), new ast::ObjectDecl(
			mutDecl->location, adapterName,
			new ast::PointerType( makeAdapterType( func, localTypeVars ) ),
			nullptr, {}, {}, nullptr,
			{ new ast::Attribute( "unused" ) } ) );
		adaptersDone.insert( adaptersDone.begin(), mangleName );
	}
}

// --------------------------------------------------------------------------
/// Corrects the floating nodes created in CallAdapter.
struct RewireAdapters final : public ast::WithGuards {
	ScopedMap<std::string, ast::ObjectDecl const *> adapters;
	void beginScope() { adapters.beginScope(); }
	void endScope() { adapters.endScope(); }
	void previsit( ast::FunctionDecl const * decl );
	ast::VariableExpr const * previsit( ast::VariableExpr const * expr );
};

void RewireAdapters::previsit( ast::FunctionDecl const * decl ) {
	GuardScope( adapters );
	for ( ast::ptr<ast::DeclWithType> const & param : decl->params ) {
		if ( auto objectParam = param.as<ast::ObjectDecl>() ) {
			adapters.insert( objectParam->name, objectParam );
		}
	}
}

ast::VariableExpr const * RewireAdapters::previsit(
		ast::VariableExpr const * expr ) {
	// If the node is not floating, we can skip.
	if ( expr->var->isManaged() ) return expr;
	auto it = adapters.find( expr->var->name );
	assertf( it != adapters.end(), "Could not correct floating node." );
	return ast::mutate_field( expr, &ast::VariableExpr::var, it->second );
}

// --------------------------------------------------------------------------
/// Inserts code to access polymorphic layout inforation.
/// * Replaces member and size/alignment/offsetof expressions on polymorphic
///   generic types with calculated expressions.
/// * Replaces member expressions for polymorphic types with calculated
///   add-field-offset-and-dereference.
/// * Calculates polymorphic offsetof expressions from offset array.
/// * Inserts dynamic calculation of polymorphic type layouts where needed.
struct PolyGenericCalculator final :
		public ast::WithConstTypeSubstitution,
		public ast::WithDeclsToAdd<>,
		public ast::WithGuards,
		public ast::WithStmtsToAdd<>,
		public ast::WithVisitorRef<PolyGenericCalculator> {
	PolyGenericCalculator();

	void previsit( ast::FunctionDecl const * decl );
	void previsit( ast::TypedefDecl const * decl );
	void previsit( ast::TypeDecl const * decl );
	ast::Decl const * postvisit( ast::TypeDecl const * decl );
	ast::StructDecl const * previsit( ast::StructDecl const * decl );
	ast::UnionDecl const * previsit( ast::UnionDecl const * decl );
	ast::DeclStmt const * previsit( ast::DeclStmt const * stmt );
	ast::Expr const * postvisit( ast::MemberExpr const * expr );
	void previsit( ast::AddressExpr const * expr );
	ast::Expr const * postvisit( ast::AddressExpr const * expr );
	ast::Expr const * postvisit( ast::SizeofExpr const * expr );
	ast::Expr const * postvisit( ast::AlignofExpr const * expr );
	ast::Expr const * postvisit( ast::OffsetofExpr const * expr );
	ast::Expr const * postvisit( ast::OffsetPackExpr const * expr );

	void beginScope();
	void endScope();
private:
	/// Makes a new variable in the current scope with the given name,
	/// type and optional initializer.
	ast::ObjectDecl * makeVar(
			CodeLocation const & location, std::string const & name,
			ast::Type const * type, ast::Init const * init = nullptr );
	/// Returns true if the type has a dynamic layout;
	/// such a layout will be stored in appropriately-named local variables
	/// when the function returns.
	bool findGeneric( CodeLocation const & location, ast::Type const * );
	/// Adds type parameters to the layout call; will generate the
	/// appropriate parameters if needed.
	void addSTypeParamsToLayoutCall(
		ast::UntypedExpr * layoutCall,
		const ast::vector<ast::Type> & otypeParams );
	/// Change the type of generic aggregate members to char[].
	void mutateMembers( ast::AggregateDecl * aggr );
	/// Returns the calculated sizeof/alignof expressions for type, or
	/// nullptr for use C size/alignof().
	ast::Expr const * genSizeof( CodeLocation const &, ast::Type const * );
	ast::Expr const * genAlignof( CodeLocation const &, ast::Type const * );
	/// Enters a new scope for type-variables,
	/// adding the type variables from the provided type.
	void beginTypeScope( ast::Type const * );

	/// The type variables and polymorphic parameters currently in scope.
	TypeVarMap scopeTypeVars;
	/// Set of generic type layouts known in the current scope,
	/// indexed by sizeofName.
	ScopedSet<std::string> knownLayouts;
	/// Set of non-generic types for which the offset array exists in the
	/// current scope, indexed by offsetofName.
	ScopedSet<std::string> knownOffsets;
	/// Namer for VLA (variable length array) buffers.
	UniqueName bufNamer;
	/// If the argument of an AddressExpr is MemberExpr, it is stored here.
	ast::MemberExpr const * addrMember = nullptr;
};

PolyGenericCalculator::PolyGenericCalculator() :
	knownLayouts(), knownOffsets(), bufNamer( "_buf" )
{}

/// Recursive section of polyToMonoType.
ast::Type * polyToMonoTypeRec( CodeLocation const & loc,
		ast::Type const * ty ) {
	if ( auto aTy = dynamic_cast<ast::ArrayType const *>( ty ) ) {
		auto monoBase = polyToMonoTypeRec( loc, aTy->base );
		return new ast::ArrayType( monoBase, aTy->dimension,
			aTy->isVarLen, aTy->isStatic, aTy->qualifiers );
	} else {
		auto charType = new ast::BasicType( ast::BasicKind::Char );
		auto size = new ast::NameExpr( loc,
			sizeofName( Mangle::mangleType( ty ) ) );
		return new ast::ArrayType( charType, size,
			ast::VariableLen, ast::DynamicDim, ast::CV::Qualifiers() );
	}
}

/// Converts polymorphic type into a suitable monomorphic representation.
/// Simple cases: T -> __attribute__(( aligned(8) )) char[sizeof_T];
/// Array cases: T[eOut][eIn] ->  __attribute__(( aligned(8) )) char[eOut][eIn][sizeof_T];
ast::Type * polyToMonoType( CodeLocation const & loc, ast::Type const * ty ) {
	auto ret = polyToMonoTypeRec( loc, ty );
	ret->attributes.emplace_back( new ast::Attribute( "aligned",
		{ ast::ConstantExpr::from_int( loc, 8 ) } ) );
	return ret;
}

void PolyGenericCalculator::previsit( ast::FunctionDecl const * decl ) {
	GuardScope( *this );
	beginTypeScope( decl->type );
}

void PolyGenericCalculator::previsit( ast::TypedefDecl const * decl ) {
	assertf( false, "All typedef declarations should be removed." );
	beginTypeScope( decl->base );
}

void PolyGenericCalculator::previsit( ast::TypeDecl const * decl ) {
	addToTypeVarMap( decl, scopeTypeVars );
}

ast::Decl const * PolyGenericCalculator::postvisit(
		ast::TypeDecl const * decl ) {
	ast::Type const * base = decl->base;
	if ( nullptr == base ) return decl;

	// Add size/align variables for opaque type declarations.
	ast::TypeInstType inst( decl->name, decl );
	std::string typeName = Mangle::mangleType( &inst );

	ast::ObjectDecl * sizeDecl = new ast::ObjectDecl( decl->location,
		sizeofName( typeName ), makeLayoutCType(),
		new ast::SingleInit( decl->location,
			new ast::SizeofExpr( decl->location, deepCopy( base ) )
		)
	);
	ast::ObjectDecl * alignDecl = new ast::ObjectDecl( decl->location,
		alignofName( typeName ), makeLayoutCType(),
		new ast::SingleInit( decl->location,
			new ast::AlignofExpr( decl->location, deepCopy( base ) )
		)
	);

	// Ensure that the initializing sizeof/alignof exprs are properly mutated.
	sizeDecl->accept( *visitor );
	alignDecl->accept( *visitor );

	// A little trick to replace this with two declarations.
	// Adding after makes sure that there is no conflict with adding stmts.
	declsToAddAfter.push_back( alignDecl );
	return sizeDecl;
}

ast::StructDecl const * PolyGenericCalculator::previsit(
		ast::StructDecl const * decl ) {
	auto mutDecl = mutate( decl );
	mutateMembers( mutDecl );
	return mutDecl;
}

ast::UnionDecl const * PolyGenericCalculator::previsit(
		ast::UnionDecl const * decl ) {
	auto mutDecl = mutate( decl );
	mutateMembers( mutDecl );
	return mutDecl;
}

ast::DeclStmt const * PolyGenericCalculator::previsit( ast::DeclStmt const * stmt ) {
	ast::ObjectDecl const * decl = stmt->decl.as<ast::ObjectDecl>();
	if ( !decl || !findGeneric( decl->location, decl->type ) ) {
		return stmt;
	}

	// Change initialization of a polymorphic value object to allocate via a
	// variable-length-array (alloca cannot be safely used in loops).
	ast::ObjectDecl * newBuf = new ast::ObjectDecl( decl->location,
		bufNamer.newName(),
		polyToMonoType( decl->location, decl->type ),
		nullptr, {}, ast::Linkage::C
	);
	stmtsToAddBefore.push_back( new ast::DeclStmt( stmt->location, newBuf ) );

	// If the object has a cleanup attribute, the clean-up should be on the
	// buffer, not the pointer. [Perhaps this should be lifted?]
	auto matchAndMove = [newBuf]( ast::ptr<ast::Attribute> & attr ) {
		if ( "cleanup" == attr->name ) {
			newBuf->attributes.push_back( attr );
			return true;
		}
		return false;
	};

	auto mutDecl = mutate( decl );

	// Forally, side effects are not safe in this function. But it works.
	erase_if( mutDecl->attributes, matchAndMove );

	// Change the decl's type.
	// Upon finishing the box pass, it shall be void*.
	// At this middle-of-box-pass point, that type is T.

	// example 1
	// before box:                                  T     t ;
	// before here:  char _bufxx    [_sizeof_Y1T];  T     t = _bufxx;
	// after here:   char _bufxx    [_sizeof_Y1T];  T     t = _bufxx;  (no change here - non array case)
	// after box:    char _bufxx    [_sizeof_Y1T];  void *t = _bufxx;

	// example 2
	// before box:                                  T     t[42] ;
	// before here:  char _bufxx[42][_sizeof_Y1T];  T     t[42] = _bufxx;
	// after here:   char _bufxx[42][_sizeof_Y1T];  T     t     = _bufxx;
	// after box:    char _bufxx[42][_sizeof_Y1T];  void *t     = _bufxx;

	// Strip all "array of" wrappers
	while ( auto arrayType = dynamic_cast<ast::ArrayType const *>( mutDecl->type.get() ) ) {
		mutDecl->type = arrayType->base;
	}

	mutDecl->init = new ast::SingleInit( decl->location,
		new ast::VariableExpr( decl->location, newBuf ) );

	return ast::mutate_field( stmt, &ast::DeclStmt::decl, mutDecl );
}

/// Checks if memberDecl matches the decl from an aggregate.
bool isMember( ast::DeclWithType const * memberDecl, ast::Decl const * decl ) {
	// No matter the field, if the name is different it is not the same.
	if ( memberDecl->name != decl->name ) {
		return false;
	}

	if ( memberDecl->name.empty() ) {
		// Plan-9 Field: Match on unique_id.
		return ( memberDecl->uniqueId == decl->uniqueId );
	}

	ast::DeclWithType const * declWithType =
		strict_dynamic_cast<ast::DeclWithType const *>( decl );

	if ( memberDecl->mangleName.empty() || declWithType->mangleName.empty() ) {
		// Tuple-Element Field: Expect neither had mangled name;
		// accept match on simple name (like field_2) only.
		assert( memberDecl->mangleName.empty() );
		assert( declWithType->mangleName.empty() );
		return true;
	}

	// Ordinary Field: Use full name to accommodate overloading.
	return ( memberDecl->mangleName == declWithType->mangleName );
}

/// Finds the member in the base list that matches the given declaration;
/// returns its index, or -1 if not present.
long findMember( ast::DeclWithType const * memberDecl,
		const ast::vector<ast::Decl> & baseDecls ) {
	for ( auto const & [index, value] : enumerate( baseDecls ) ) {
		if ( isMember( memberDecl, value.get() ) ) {
			return index;
		}
	}
	return -1;
}

/// Returns an index expression into the offset array for a type.
ast::Expr * makeOffsetIndex( CodeLocation const & location,
		ast::Type const * objectType, long i ) {
	std::string name = offsetofName( Mangle::mangleType( objectType ) );
	return ast::UntypedExpr::createCall( location, "?[?]", {
		new ast::NameExpr( location, name ),
		ast::ConstantExpr::from_ulong( location, i ),
	} );
}

ast::Expr const * PolyGenericCalculator::postvisit(
		ast::MemberExpr const * expr ) {
	// Only mutate member expressions for polymorphic types.
	ast::Type const * objectType = hasPolyBase(
		expr->aggregate->result, scopeTypeVars
	);
	if ( !objectType ) return expr;
	// Ensure layout for this type is available.
	// The boolean result is ignored.
	findGeneric( expr->location, objectType );

	// Replace member expression with dynamically-computed layout expression.
	ast::Expr * newMemberExpr = nullptr;
	if ( auto structType = dynamic_cast<ast::StructInstType const *>( objectType ) ) {
		long offsetIndex = findMember( expr->member, structType->base->members );
		if ( -1 == offsetIndex ) return expr;

		// Replace member expression with pointer to struct plus offset.
		ast::UntypedExpr * fieldLoc = new ast::UntypedExpr( expr->location,
				new ast::NameExpr( expr->location, "?+?" ) );
		ast::Expr * aggr = deepCopy( expr->aggregate );
		aggr->env = nullptr;
		fieldLoc->args.push_back( aggr );
		fieldLoc->args.push_back(
			makeOffsetIndex( expr->location, objectType, offsetIndex ) );
		fieldLoc->result = deepCopy( expr->result );
		newMemberExpr = fieldLoc;
	// Union members are all at offset zero, so just use the aggregate expr.
	} else if ( dynamic_cast<ast::UnionInstType const *>( objectType ) ) {
		ast::Expr * aggr = deepCopy( expr->aggregate );
		aggr->env = nullptr;
		aggr->result = deepCopy( expr->result );
		newMemberExpr = aggr;
	} else {
		return expr;
	}
	assert( newMemberExpr );

	// Must apply the generic substitution to the member type to handle cases
	// where the member is a generic parameter subsituted by a known concrete
	// type. [ex]
	//	forall( T ) struct Box { T x; }
	//	forall( T ) void f() {
	//		Box( T * ) b; b.x;
	//	}
	// TODO: expr->result should be exactly expr->member->get_type() after
	// substitution, so it doesn't seem like it should be necessary to apply
	// the substitution manually. For some reason this is not currently the
	// case. This requires more investigation.
	ast::ptr<ast::Type> memberType = deepCopy( expr->member->get_type() );
	ast::TypeSubstitution sub = genericSubstitution( objectType );
	sub.apply( memberType );

	// Not all members of a polymorphic type are themselves of a polymorphic
	// type; in this case the member expression should be wrapped and
	// dereferenced to form an lvalue.
	if ( !isPolyType( memberType, scopeTypeVars ) ) {
		auto ptrCastExpr = new ast::CastExpr( expr->location, newMemberExpr,
			new ast::PointerType( memberType ) );
		auto derefExpr = ast::UntypedExpr::createDeref( expr->location,
			ptrCastExpr );
		newMemberExpr = derefExpr;
	}

	return newMemberExpr;
}

void PolyGenericCalculator::previsit( ast::AddressExpr const * expr ) {
	GuardValue( addrMember ) = expr->arg.as<ast::MemberExpr>();
}

ast::Expr const * PolyGenericCalculator::postvisit(
		ast::AddressExpr const * expr ) {
	// arg has to have been a MemberExpr and has been mutated.
	if ( nullptr == addrMember || expr->arg == addrMember ) {
		return expr;
	}
	ast::UntypedExpr const * untyped = expr->arg.as<ast::UntypedExpr>();
	if ( !untyped || getFunctionName( untyped ) != "?+?" ) {
		return expr;
	}
	// MemberExpr was converted to pointer + offset; and it is not valid C to
	// take the address of an addition, so strip away the address-of.
	// It also preserves the env value.
	return ast::mutate_field( expr->arg.get(), &ast::Expr::env, expr->env );
}

ast::Expr const * PolyGenericCalculator::postvisit(
		ast::SizeofExpr const * expr ) {
	ast::Expr const * gen = genSizeof( expr->location, expr->type );
	return ( gen ) ? gen : expr;
}

ast::Expr const * PolyGenericCalculator::postvisit(
		ast::AlignofExpr const * expr ) {
	ast::Expr const * gen = genAlignof( expr->location, expr->type );
	return ( gen ) ? gen : expr;
}

ast::Expr const * PolyGenericCalculator::postvisit(
		ast::OffsetofExpr const * expr ) {
	ast::Type const * type = expr->type;
	if ( !findGeneric( expr->location, type ) ) return expr;

	// Structures replace offsetof expression with an index into offset array.
	if ( auto structType = dynamic_cast<ast::StructInstType const *>( type ) ) {
		long offsetIndex = findMember( expr->member, structType->base->members );
		if ( -1 == offsetIndex ) return expr;

		return makeOffsetIndex( expr->location, type, offsetIndex );
	// All union members are at offset zero.
	} else if ( dynamic_cast<ast::UnionInstType const *>( type ) ) {
		return ast::ConstantExpr::from_ulong( expr->location, 0 );
	} else {
		return expr;
	}
}

ast::Expr const * PolyGenericCalculator::postvisit(
		ast::OffsetPackExpr const * expr ) {
	ast::StructInstType const * type = expr->type;

	// Pull offset back from generated type information.
	if ( findGeneric( expr->location, type ) ) {
		return new ast::NameExpr( expr->location,
			offsetofName( Mangle::mangleType( type ) ) );
	}

	std::string offsetName = offsetofName( Mangle::mangleType( type ) );
	// Use the already generated offsets for this type.
	if ( knownOffsets.contains( offsetName ) ) {
		return new ast::NameExpr( expr->location, offsetName );
	}

	knownOffsets.insert( offsetName );

	// Build initializer list for offset array.
	ast::vector<ast::Init> inits;
	for ( ast::ptr<ast::Decl> const & member : type->base->members ) {
		auto memberDecl = member.as<ast::DeclWithType>();
		assertf( memberDecl, "Requesting offset of non-DWT member: %s",
			toCString( member ) );
		inits.push_back( new ast::SingleInit( expr->location,
			new ast::OffsetofExpr( expr->location,
				deepCopy( type ),
				memberDecl
			)
		) );
	}

	auto offsetArray = makeVar( expr->location, offsetName,
		new ast::ArrayType(
			makeLayoutType(),
			ast::ConstantExpr::from_ulong( expr->location, inits.size() ),
			ast::FixedLen,
			ast::DynamicDim
		),
		new ast::ListInit( expr->location, std::move( inits ) )
	);

	return new ast::VariableExpr( expr->location, offsetArray );
}

void PolyGenericCalculator::beginScope() {
	knownLayouts.beginScope();
	knownOffsets.beginScope();
}

void PolyGenericCalculator::endScope() {
	knownOffsets.endScope();
	knownLayouts.endScope();
}

ast::ObjectDecl * PolyGenericCalculator::makeVar(
		CodeLocation const & location, std::string const & name,
		ast::Type const * type, ast::Init const * init ) {
	ast::ObjectDecl * ret = new ast::ObjectDecl( location, name, type, init );
	stmtsToAddBefore.push_back( new ast::DeclStmt( location, ret ) );
	return ret;
}

/// Returns true if any of the otype parameters have a dynamic layout; and
/// puts all otype parameters in the output list.
bool findGenericParams(
		ast::vector<ast::Type> & out,
		ast::vector<ast::TypeDecl> const & baseParams,
		ast::vector<ast::Expr> const & typeParams ) {
	bool hasDynamicLayout = false;

	for ( auto const & [baseParam, typeParam] : group_iterate(
			baseParams, typeParams ) ) {
		if ( !baseParam->isComplete() ) continue;
		ast::TypeExpr const * typeExpr = typeParam.as<ast::TypeExpr>();
		assertf( typeExpr, "All type parameters should be type expressions." );

		ast::Type const * type = typeExpr->type.get();
		out.push_back( type );
		if ( isPolyType( type ) ) hasDynamicLayout = true;
	}

	return hasDynamicLayout;
}

bool PolyGenericCalculator::findGeneric(
		CodeLocation const & location, ast::Type const * type ) {
	type = replaceTypeInst( type, typeSubs );

	if ( auto inst = dynamic_cast<ast::TypeInstType const *>( type ) ) {
		// Assumes that getting put in the scopeTypeVars includes having the
		// layout variables set.
		if ( scopeTypeVars.contains( *inst ) ) {
			return true;
		}
	} else if ( auto inst = dynamic_cast<ast::StructInstType const *>( type ) ) {
		// Check if this type already has a layout generated for it.
		std::string typeName = Mangle::mangleType( type );
		if ( knownLayouts.contains( typeName ) ) return true;

		// Check if any type parameters have dynamic layout;
		// If none do, this type is (or will be) monomorphized.
		ast::vector<ast::Type> sizedParams;
		if ( !findGenericParams( sizedParams,
				inst->base->params, inst->params ) ) {
			return false;
		}

		// Insert local variables for layout and generate call to layout
		// function.
		// Done early so as not to interfere with the later addition of
		// parameters to the layout call.
		knownLayouts.insert( typeName );

		int memberCount = inst->base->members.size();
		if ( 0 == memberCount ) {
			// All empty structures have the same layout (size 1, align 1).
			makeVar( location,
				sizeofName( typeName ), makeLayoutType(),
				new ast::SingleInit( location,
						ast::ConstantExpr::from_ulong( location, 1 ) ) );
			makeVar( location,
				alignofName( typeName ), makeLayoutType(),
				new ast::SingleInit( location,
						ast::ConstantExpr::from_ulong( location, 1 ) ) );
			// Since 0-length arrays are forbidden in C, skip the offset array.
		} else {
			ast::ObjectDecl const * sizeofVar = makeVar( location,
				sizeofName( typeName ), makeLayoutType(), nullptr );
			ast::ObjectDecl const * alignofVar = makeVar( location,
				alignofName( typeName ), makeLayoutType(), nullptr );
			ast::ObjectDecl const * offsetofVar = makeVar( location,
				offsetofName( typeName ),
				new ast::ArrayType(
					makeLayoutType(),
					ast::ConstantExpr::from_int( location, memberCount ),
					ast::FixedLen,
					ast::DynamicDim
				),
				nullptr
			);

			// Generate call to layout function.
			ast::UntypedExpr * layoutCall = new ast::UntypedExpr( location,
				new ast::NameExpr( location, layoutofName( inst->base ) ),
				{
					new ast::AddressExpr(
						new ast::VariableExpr( location, sizeofVar ) ),
					new ast::AddressExpr(
						new ast::VariableExpr( location, alignofVar ) ),
					new ast::VariableExpr( location, offsetofVar ),
				} );

			addSTypeParamsToLayoutCall( layoutCall, sizedParams );

			stmtsToAddBefore.emplace_back(
				new ast::ExprStmt( location, layoutCall ) );
		}

		return true;
	} else if ( auto inst = dynamic_cast<ast::UnionInstType const *>( type ) ) {
		// Check if this type already has a layout generated for it.
		std::string typeName = Mangle::mangleType( type );
		if ( knownLayouts.contains( typeName ) ) return true;

		// Check if any type parameters have dynamic layout;
		// If none do, this type is (or will be) monomorphized.
		ast::vector<ast::Type> sizedParams;
		if ( !findGenericParams( sizedParams,
				inst->base->params, inst->params ) ) {
			return false;
		}

		// Insert local variables for layout and generate call to layout
		// function.
		// Done early so as not to interfere with the later addition of
		// parameters to the layout call.
		knownLayouts.insert( typeName );

		ast::ObjectDecl * sizeofVar = makeVar( location,
			sizeofName( typeName ), makeLayoutType() );
		ast::ObjectDecl * alignofVar = makeVar( location,
			alignofName( typeName ), makeLayoutType() );

		ast::UntypedExpr * layoutCall = new ast::UntypedExpr( location,
			new ast::NameExpr( location, layoutofName( inst->base ) ),
			{
				new ast::AddressExpr(
					new ast::VariableExpr( location, sizeofVar ) ),
				new ast::AddressExpr(
					new ast::VariableExpr( location, alignofVar ) ),
			} );

		addSTypeParamsToLayoutCall( layoutCall, sizedParams );

		stmtsToAddBefore.emplace_back(
			new ast::ExprStmt( location, layoutCall ) );

		return true;

	} else if ( auto inst = dynamic_cast<ast::ArrayType const *>( type ) ) {
		return findGeneric( location, inst->base );
	}
	return false;
}

void PolyGenericCalculator::addSTypeParamsToLayoutCall(
		ast::UntypedExpr * layoutCall,
		const ast::vector<ast::Type> & otypeParams ) {
	CodeLocation const & location = layoutCall->location;
	ast::vector<ast::Expr> & args = layoutCall->args;
	for ( ast::ptr<ast::Type> const & param : otypeParams ) {
		if ( findGeneric( location, param ) ) {
			// Push size/align vars for a generic parameter back.
			std::string paramName = Mangle::mangleType( param );
			args.emplace_back(
				new ast::NameExpr( location, sizeofName( paramName ) ) );
			args.emplace_back(
				new ast::NameExpr( location, alignofName( paramName ) ) );
		} else {
			args.emplace_back(
				new ast::SizeofExpr( location, ast::deepCopy( param ) ) );
			args.emplace_back(
				new ast::AlignofExpr( location, ast::deepCopy( param ) ) );
		}
	}
}

void PolyGenericCalculator::mutateMembers( ast::AggregateDecl * aggr ) {
	std::set<std::string> genericParams;
	for ( ast::ptr<ast::TypeDecl> const & decl : aggr->params ) {
		genericParams.insert( decl->name );
	}
	for ( ast::ptr<ast::Decl> & decl : aggr->members ) {
		auto field = decl.as<ast::ObjectDecl>();
		if ( nullptr == field ) continue;

		ast::Type const * type = replaceTypeInst( field->type, typeSubs );
		auto typeInst = dynamic_cast<ast::TypeInstType const *>( type );
		if ( nullptr == typeInst ) continue;

		// Do not try to monoporphize generic parameters.
		if ( scopeTypeVars.contains( ast::TypeEnvKey( *typeInst ) ) &&
				!genericParams.count( typeInst->name ) ) {
			// Polymorphic aggregate members should be converted into
			// monomorphic members. Using char[size_T] here respects
			// the expected sizing rules of an aggregate type.
			decl = ast::mutate_field( field, &ast::ObjectDecl::type,
				polyToMonoType( field->location, field->type ) );
		}
	}
}

ast::Expr const * PolyGenericCalculator::genSizeof(
		CodeLocation const & location, ast::Type const * type ) {
	if ( auto * array = dynamic_cast<ast::ArrayType const *>( type ) ) {
		// Generate calculated size for possibly generic array.
		ast::Expr const * sizeofBase = genSizeof( location, array->base );
		if ( nullptr == sizeofBase ) return nullptr;
		ast::Expr const * dim = array->dimension;
		return makeOp( location, "?*?", sizeofBase, dim );
	} else if ( findGeneric( location, type ) ) {
		// Generate reference to _sizeof parameter
		return new ast::NameExpr( location, sizeofName(
				Mangle::mangleType( type ) ) );
	} else {
		return nullptr;
	}
}

ast::Expr const * PolyGenericCalculator::genAlignof(
		CodeLocation const & location, ast::Type const * type ) {
	if ( auto * array = dynamic_cast<ast::ArrayType const *>( type ) ) {
		// alignof array is alignof element
		return genAlignof( location, array->base );
	} else if ( findGeneric( location, type ) ) {
		// Generate reference to _alignof parameter
		return new ast::NameExpr( location, alignofName(
				Mangle::mangleType( type ) ) );
	} else {
		return nullptr;
	}
}

void PolyGenericCalculator::beginTypeScope( ast::Type const * type ) {
	GuardScope( scopeTypeVars );
	makeTypeVarMap( type, scopeTypeVars );
}

// --------------------------------------------------------------------------
/// Removes unneeded or incorrect type information.
/// * Replaces initialization of polymorphic values with alloca.
/// * Replaces declaration of dtype/ftype with appropriate void expression.
/// * Replaces sizeof expressions of polymorphic types with a variable.
/// * Strips fields from generic structure declarations.
struct Eraser final :
		public ast::WithGuards {
	void guardTypeVarMap( ast::Type const * type ) {
		GuardScope( scopeTypeVars );
		makeTypeVarMap( type, scopeTypeVars );
	}

	ast::ObjectDecl const * previsit( ast::ObjectDecl const * decl );
	ast::FunctionDecl const * previsit( ast::FunctionDecl const * decl );
	ast::FunctionDecl const * postvisit( ast::FunctionDecl const * decl );
	ast::TypedefDecl const * previsit( ast::TypedefDecl const * decl );
	ast::StructDecl const * previsit( ast::StructDecl const * decl );
	ast::UnionDecl const * previsit( ast::UnionDecl const * decl );
	void previsit( ast::TypeDecl const * decl );
	void previsit( ast::PointerType const * type );
	void previsit( ast::FunctionType const * type );
public:
	TypeVarMap scopeTypeVars;
};

ast::ObjectDecl const * Eraser::previsit( ast::ObjectDecl const * decl ) {
	guardTypeVarMap( decl->type );
	return scrubAllTypeVars( decl );
}

ast::FunctionDecl const * Eraser::previsit( ast::FunctionDecl const * decl ) {
	guardTypeVarMap( decl->type );
	return scrubAllTypeVars( decl );
}

ast::FunctionDecl const * Eraser::postvisit( ast::FunctionDecl const * decl ) {
	if ( decl->type_params.empty() ) return decl;
	auto mutDecl = mutate( decl );
	mutDecl->type_params.clear();
	return mutDecl;
}

ast::TypedefDecl const * Eraser::previsit( ast::TypedefDecl const * decl ) {
	guardTypeVarMap( decl->base );
	return scrubAllTypeVars( decl );
}

/// Strips the members from a generic aggregate.
template<typename node_t>
node_t const * stripGenericMembers( node_t const * decl ) {
	if ( decl->params.empty() ) return decl;
	auto mutDecl = ast::mutate( decl );
	mutDecl->members.clear();
	return mutDecl;
}

ast::StructDecl const * Eraser::previsit( ast::StructDecl const * decl ) {
	return stripGenericMembers( decl );
}

ast::UnionDecl const * Eraser::previsit( ast::UnionDecl const * decl ) {
	return stripGenericMembers( decl );
}

void Eraser::previsit( ast::TypeDecl const * decl ) {
	addToTypeVarMap( decl, scopeTypeVars );
}

void Eraser::previsit( ast::PointerType const * type ) {
	guardTypeVarMap( type );
}

void Eraser::previsit( ast::FunctionType const * type ) {
	guardTypeVarMap( type );
}

} // namespace

// --------------------------------------------------------------------------
void box( ast::TranslationUnit & translationUnit ) {
	ast::Pass<LayoutFunctionBuilder>::run( translationUnit );
	ast::Pass<CallAdapter>::run( translationUnit );
	ast::Pass<DeclAdapter>::run( translationUnit );
	ast::Pass<RewireAdapters>::run( translationUnit );
	ast::Pass<PolyGenericCalculator>::run( translationUnit );
	ast::Pass<Eraser>::run( translationUnit );
}

} // namespace GenPoly

// Local Variables: //
// tab-width: 4 //
// mode: c++ //
// compile-command: "make install" //
// End: //