Context Navigation

source: src/ResolvExpr/AlternativeFinder.cc @ 178e4ec

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc

Last change on this file since 178e4ec was 178e4ec, checked in by Rob Schluntz <rschlunt@…>, 6 years ago
Merge branch 'master' of plg.uwaterloo.ca:/u/cforall/software/cfa/cfa-cc
Property mode set to `100644`
File size: 70.1 KB

Rev	Line
[a32b204]	1	//
	2	// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
	3	//
	4	// The contents of this file are covered under the licence agreement in the
	5	// file "LICENCE" distributed with Cforall.
	6	//
[6ed1d4b]	7	// AlternativeFinder.cc --
[a32b204]	8	//
	9	// Author : Richard C. Bilson
	10	// Created On : Sat May 16 23:52:08 2015
[b128d3e]	11	// Last Modified By : Peter A. Buhr
	12	// Last Modified On : Mon Aug 28 13:47:24 2017
	13	// Update Count : 32
[a32b204]	14	//
	15
[ea6332d]	16	#include <algorithm> // for copy
[e3e16bc]	17	#include <cassert> // for strict_dynamic_cast, assert, assertf
[403b388]	18	#include <cstddef> // for size_t
[ea6332d]	19	#include <iostream> // for operator<<, cerr, ostream, endl
	20	#include <iterator> // for back_insert_iterator, back_inserter
	21	#include <list> // for _List_iterator, list, _List_const_...
	22	#include <map> // for _Rb_tree_iterator, map, _Rb_tree_c...
[403b388]	23	#include <memory> // for allocator_traits<>::value_type, unique_ptr
[ea6332d]	24	#include <utility> // for pair
[aeb75b1]	25	#include <vector> // for vector
[51b7345]	26
[ea6332d]	27	#include "Alternative.h" // for AltList, Alternative
[51b7345]	28	#include "AlternativeFinder.h"
[ea6332d]	29	#include "Common/SemanticError.h" // for SemanticError
	30	#include "Common/utility.h" // for deleteAll, printAll, CodeLocation
	31	#include "Cost.h" // for Cost, Cost::zero, operator<<, Cost...
[a8b27c6]	32	#include "ExplodedActual.h" // for ExplodedActual
[ea6332d]	33	#include "InitTweak/InitTweak.h" // for getFunctionName
	34	#include "RenameVars.h" // for RenameVars, global_renamer
	35	#include "ResolveTypeof.h" // for resolveTypeof
	36	#include "Resolver.h" // for resolveStmtExpr
	37	#include "SymTab/Indexer.h" // for Indexer
	38	#include "SymTab/Mangler.h" // for Mangler
	39	#include "SymTab/Validate.h" // for validateType
	40	#include "SynTree/Constant.h" // for Constant
	41	#include "SynTree/Declaration.h" // for DeclarationWithType, TypeDecl, Dec...
	42	#include "SynTree/Expression.h" // for Expression, CastExpr, NameExpr
	43	#include "SynTree/Initializer.h" // for SingleInit, operator<<, Designation
	44	#include "SynTree/SynTree.h" // for UniqueId
	45	#include "SynTree/Type.h" // for Type, FunctionType, PointerType
	46	#include "Tuples/Explode.h" // for explode
	47	#include "Tuples/Tuples.h" // for isTtype, handleTupleAssignment
	48	#include "Unify.h" // for unify
	49	#include "typeops.h" // for adjustExprType, polyCost, castCost
[51b7345]	50
[b87a5ed]	51	extern bool resolvep;
[6ed1d4b]	52	#define PRINT( text ) if ( resolvep ) { text }
[51b7345]	53	//#define DEBUG_COST
	54
[403b388]	55	using std::move;
	56
	57	/// copies any copyable type
	58	template<typename T>
	59	T copy(const T& x) { return x; }
	60
[51b7345]	61	namespace ResolvExpr {
[a32b204]	62	Expression resolveInVoidContext( Expression expr, const SymTab::Indexer &indexer, TypeEnvironment &env ) {
	63	CastExpr *castToVoid = new CastExpr( expr );
	64
	65	AlternativeFinder finder( indexer, env );
	66	finder.findWithAdjustment( castToVoid );
	67
	68	// it's a property of the language that a cast expression has either 1 or 0 interpretations; if it has 0
	69	// interpretations, an exception has already been thrown.
	70	assert( finder.get_alternatives().size() == 1 );
	71	CastExpr newExpr = dynamic_cast< CastExpr >( finder.get_alternatives().front().expr );
	72	assert( newExpr );
	73	env = finder.get_alternatives().front().env;
	74	return newExpr->get_arg()->clone();
	75	}
	76
[908cc83]	77	Cost sumCost( const AltList &in ) {
[89be1c68]	78	Cost total = Cost::zero;
[908cc83]	79	for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
	80	total += i->cost;
	81	}
	82	return total;
	83	}
	84
[a32b204]	85	namespace {
[50377a4]	86	void printAlts( const AltList &list, std::ostream &os, unsigned int indentAmt = 0 ) {
	87	Indenter indent = { Indenter::tabsize, indentAmt };
[a32b204]	88	for ( AltList::const_iterator i = list.begin(); i != list.end(); ++i ) {
	89	i->print( os, indent );
	90	os << std::endl;
	91	}
	92	}
[d9a0e76]	93
[a32b204]	94	void makeExprList( const AltList &in, std::list< Expression* > &out ) {
	95	for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
	96	out.push_back( i->expr->clone() );
	97	}
	98	}
[d9a0e76]	99
[a32b204]	100	struct PruneStruct {
	101	bool isAmbiguous;
	102	AltList::iterator candidate;
	103	PruneStruct() {}
	104	PruneStruct( AltList::iterator candidate ): isAmbiguous( false ), candidate( candidate ) {}
	105	};
	106
[0f19d763]	107	/// Prunes a list of alternatives down to those that have the minimum conversion cost for a given return type; skips ambiguous interpretations
[a32b204]	108	template< typename InputIterator, typename OutputIterator >
[d7dc824]	109	void pruneAlternatives( InputIterator begin, InputIterator end, OutputIterator out ) {
[a32b204]	110	// select the alternatives that have the minimum conversion cost for a particular set of result types
	111	std::map< std::string, PruneStruct > selected;
	112	for ( AltList::iterator candidate = begin; candidate != end; ++candidate ) {
	113	PruneStruct current( candidate );
	114	std::string mangleName;
[906e24d]	115	{
	116	Type * newType = candidate->expr->get_result()->clone();
[a32b204]	117	candidate->env.apply( newType );
[906e24d]	118	mangleName = SymTab::Mangler::mangle( newType );
[a32b204]	119	delete newType;
	120	}
	121	std::map< std::string, PruneStruct >::iterator mapPlace = selected.find( mangleName );
	122	if ( mapPlace != selected.end() ) {
	123	if ( candidate->cost < mapPlace->second.candidate->cost ) {
	124	PRINT(
[6ed1d4b]	125	std::cerr << "cost " << candidate->cost << " beats " << mapPlace->second.candidate->cost << std::endl;
[7c64920]	126	)
[0f19d763]	127	selected[ mangleName ] = current;
[a32b204]	128	} else if ( candidate->cost == mapPlace->second.candidate->cost ) {
	129	PRINT(
[6ed1d4b]	130	std::cerr << "marking ambiguous" << std::endl;
[7c64920]	131	)
[0f19d763]	132	mapPlace->second.isAmbiguous = true;
[b0837e4]	133	} else {
	134	PRINT(
	135	std::cerr << "cost " << candidate->cost << " loses to " << mapPlace->second.candidate->cost << std::endl;
	136	)
[a32b204]	137	}
	138	} else {
	139	selected[ mangleName ] = current;
	140	}
	141	}
[d9a0e76]	142
[0f19d763]	143	// accept the alternatives that were unambiguous
	144	for ( std::map< std::string, PruneStruct >::iterator target = selected.begin(); target != selected.end(); ++target ) {
	145	if ( ! target->second.isAmbiguous ) {
	146	Alternative &alt = *target->second.candidate;
[906e24d]	147	alt.env.applyFree( alt.expr->get_result() );
[0f19d763]	148	*out++ = alt;
[a32b204]	149	}
[0f19d763]	150	}
[d9a0e76]	151	}
[a32b204]	152
	153	void renameTypes( Expression *expr ) {
[906e24d]	154	expr->get_result()->accept( global_renamer );
[e76acbe]	155	}
[1dcd9554]	156	} // namespace
[b1bead1]	157
[1dcd9554]	158	void referenceToRvalueConversion( Expression *& expr ) {
	159	if ( dynamic_cast< ReferenceType * >( expr->get_result() ) ) {
	160	// cast away reference from expr
	161	expr = new CastExpr( expr, expr->get_result()->stripReferences()->clone() );
[b1bead1]	162	}
[1dcd9554]	163	}
[d9a0e76]	164
[a32b204]	165	template< typename InputIterator, typename OutputIterator >
	166	void AlternativeFinder::findSubExprs( InputIterator begin, InputIterator end, OutputIterator out ) {
	167	while ( begin != end ) {
	168	AlternativeFinder finder( indexer, env );
	169	finder.findWithAdjustment( *begin );
	170	// XXX either this
	171	//Designators::fixDesignations( finder, (*begin++)->get_argName() );
	172	// or XXX this
	173	begin++;
	174	PRINT(
[6ed1d4b]	175	std::cerr << "findSubExprs" << std::endl;
	176	printAlts( finder.alternatives, std::cerr );
[7c64920]	177	)
[0f19d763]	178	*out++ = finder;
[a32b204]	179	}
[d9a0e76]	180	}
	181
[a32b204]	182	AlternativeFinder::AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env )
	183	: indexer( indexer ), env( env ) {
[d9a0e76]	184	}
[51b7345]	185
[4e66a18]	186	void AlternativeFinder::find( Expression *expr, bool adjust, bool prune, bool failFast ) {
[a32b204]	187	expr->accept( *this );
[4e66a18]	188	if ( failFast && alternatives.empty() ) {
[83882e9]	189	PRINT(
	190	std::cerr << "No reasonable alternatives for expression " << expr << std::endl;
	191	)
[a32b204]	192	throw SemanticError( "No reasonable alternatives for expression ", expr );
	193	}
[b6fe7e6]	194	if ( prune ) {
[b0837e4]	195	auto oldsize = alternatives.size();
[b6fe7e6]	196	PRINT(
	197	std::cerr << "alternatives before prune:" << std::endl;
	198	printAlts( alternatives, std::cerr );
	199	)
[bd4f2e9]	200	AltList pruned;
	201	pruneAlternatives( alternatives.begin(), alternatives.end(), back_inserter( pruned ) );
	202	if ( failFast && pruned.empty() ) {
[b6fe7e6]	203	std::ostringstream stream;
	204	AltList winners;
	205	findMinCost( alternatives.begin(), alternatives.end(), back_inserter( winners ) );
[50377a4]	206	stream << "Cannot choose between " << winners.size() << " alternatives for expression\n";
[5a824c2]	207	expr->print( stream );
[50377a4]	208	stream << "Alternatives are:\n";
	209	printAlts( winners, stream, 1 );
[b6fe7e6]	210	throw SemanticError( stream.str() );
	211	}
[bd4f2e9]	212	alternatives = move(pruned);
[b0837e4]	213	PRINT(
	214	std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
	215	)
[b6fe7e6]	216	PRINT(
	217	std::cerr << "there are " << alternatives.size() << " alternatives after elimination" << std::endl;
	218	)
[a32b204]	219	}
[954ef5b]	220	// adjust types after pruning so that types substituted by pruneAlternatives are correctly adjusted
	221	for ( AltList::iterator i = alternatives.begin(); i != alternatives.end(); ++i ) {
	222	if ( adjust ) {
	223	adjustExprType( i->expr->get_result(), i->env, indexer );
	224	}
	225	}
[8e9cbb2]	226
[64ac636]	227	// Central location to handle gcc extension keyword, etc. for all expression types.
[8e9cbb2]	228	for ( Alternative &iter: alternatives ) {
	229	iter.expr->set_extension( expr->get_extension() );
[64ac636]	230	iter.expr->location = expr->location;
[8e9cbb2]	231	} // for
[0f19d763]	232	}
[d9a0e76]	233
[4e66a18]	234	void AlternativeFinder::findWithAdjustment( Expression *expr ) {
	235	find( expr, true );
	236	}
	237
	238	void AlternativeFinder::findWithoutPrune( Expression * expr ) {
	239	find( expr, true, false );
	240	}
	241
	242	void AlternativeFinder::maybeFind( Expression * expr ) {
	243	find( expr, true, true, false );
[d9a0e76]	244	}
[a32b204]	245
[4b0f997]	246	void AlternativeFinder::addAnonConversions( const Alternative & alt ) {
	247	// adds anonymous member interpretations whenever an aggregate value type is seen.
[d1685588]	248	// it's okay for the aggregate expression to have reference type -- cast it to the base type to treat the aggregate as the referenced value
	249	std::unique_ptr<Expression> aggrExpr( alt.expr->clone() );
	250	alt.env.apply( aggrExpr->get_result() );
	251	Type * aggrType = aggrExpr->get_result();
	252	if ( dynamic_cast< ReferenceType * >( aggrType ) ) {
	253	aggrType = aggrType->stripReferences();
	254	aggrExpr.reset( new CastExpr( aggrExpr.release(), aggrType->clone() ) );
	255	}
	256
	257	if ( StructInstType structInst = dynamic_cast< StructInstType >( aggrExpr->get_result() ) ) {
[4b0f997]	258	NameExpr nameExpr( "" );
[d1685588]	259	addAggMembers( structInst, aggrExpr.get(), alt.cost+Cost::safe, alt.env, &nameExpr );
	260	} else if ( UnionInstType unionInst = dynamic_cast< UnionInstType >( aggrExpr->get_result() ) ) {
[4b0f997]	261	NameExpr nameExpr( "" );
[d1685588]	262	addAggMembers( unionInst, aggrExpr.get(), alt.cost+Cost::safe, alt.env, &nameExpr );
[4b0f997]	263	} // if
	264	}
[77971f6]	265
[a32b204]	266	template< typename StructOrUnionType >
[add7117]	267	void AlternativeFinder::addAggMembers( StructOrUnionType aggInst, Expression expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) {
[bf32bb8]	268	// by this point, member must be a name expr
[c93bc28]	269	NameExpr * nameExpr = dynamic_cast< NameExpr * >( member );
	270	if ( ! nameExpr ) return;
[bf32bb8]	271	const std::string & name = nameExpr->get_name();
	272	std::list< Declaration* > members;
	273	aggInst->lookup( name, members );
[4b0f997]	274
[bf32bb8]	275	for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
	276	if ( DeclarationWithType dwt = dynamic_cast< DeclarationWithType >( *i ) ) {
[d9fa60a]	277	alternatives.push_back( Alternative( new MemberExpr( dwt, expr->clone() ), env, newCost ) );
[bf32bb8]	278	renameTypes( alternatives.back().expr );
[4b0f997]	279	addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a member expression.
[bf32bb8]	280	} else {
	281	assert( false );
[a32b204]	282	}
	283	}
[d9a0e76]	284	}
[a32b204]	285
[848ce71]	286	void AlternativeFinder::addTupleMembers( TupleType * tupleType, Expression expr, const Cost &newCost, const TypeEnvironment & env, Expression member ) {
	287	if ( ConstantExpr * constantExpr = dynamic_cast< ConstantExpr * >( member ) ) {
	288	// get the value of the constant expression as an int, must be between 0 and the length of the tuple type to have meaning
	289	// xxx - this should be improved by memoizing the value of constant exprs
	290	// during parsing and reusing that information here.
	291	std::stringstream ss( constantExpr->get_constant()->get_value() );
[c93bc28]	292	int val = 0;
[848ce71]	293	std::string tmp;
	294	if ( ss >> val && ! (ss >> tmp) ) {
	295	if ( val >= 0 && (unsigned int)val < tupleType->size() ) {
	296	alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
	297	} // if
	298	} // if
[141b786]	299	} else if ( NameExpr * nameExpr = dynamic_cast< NameExpr * >( member ) ) {
	300	// xxx - temporary hack until 0/1 are int constants
	301	if ( nameExpr->get_name() == "0" \|\| nameExpr->get_name() == "1" ) {
	302	std::stringstream ss( nameExpr->get_name() );
	303	int val;
	304	ss >> val;
	305	alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
	306	}
[848ce71]	307	} // if
	308	}
	309
[a32b204]	310	void AlternativeFinder::visit( ApplicationExpr *applicationExpr ) {
	311	alternatives.push_back( Alternative( applicationExpr->clone(), env, Cost::zero ) );
[d9a0e76]	312	}
	313
[ddf8a29]	314	Cost computeConversionCost( Type * actualType, Type * formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) {
	315	PRINT(
	316	std::cerr << std::endl << "converting ";
	317	actualType->print( std::cerr, 8 );
	318	std::cerr << std::endl << " to ";
	319	formalType->print( std::cerr, 8 );
	320	std::cerr << std::endl << "environment is: ";
	321	env.print( std::cerr, 8 );
	322	std::cerr << std::endl;
	323	)
	324	Cost convCost = conversionCost( actualType, formalType, indexer, env );
	325	PRINT(
[d06c808]	326	std::cerr << std::endl << "cost is " << convCost << std::endl;
[ddf8a29]	327	)
	328	if ( convCost == Cost::infinity ) {
	329	return convCost;
	330	}
	331	convCost.incPoly( polyCost( formalType, env, indexer ) + polyCost( actualType, env, indexer ) );
[d06c808]	332	PRINT(
	333	std::cerr << "cost with polycost is " << convCost << std::endl;
	334	)
[ddf8a29]	335	return convCost;
	336	}
	337
	338	Cost computeExpressionConversionCost( Expression & actualExpr, Type formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) {
	339	Cost convCost = computeConversionCost( actualExpr->result, formalType, indexer, env );
	340
[bb666f64]	341	// if there is a non-zero conversion cost, ignoring poly cost, then the expression requires conversion.
	342	// ignore poly cost for now, since this requires resolution of the cast to infer parameters and this
	343	// does not currently work for the reason stated below.
[ddf8a29]	344	Cost tmpCost = convCost;
	345	tmpCost.incPoly( -tmpCost.get_polyCost() );
	346	if ( tmpCost != Cost::zero ) {
	347	Type *newType = formalType->clone();
	348	env.apply( newType );
	349	actualExpr = new CastExpr( actualExpr, newType );
	350	// xxx - SHOULD be able to resolve this cast, but at the moment pointers are not castable to zero_t, but are implicitly convertible. This is clearly
	351	// inconsistent, once this is fixed it should be possible to resolve the cast.
	352	// xxx - this isn't working, it appears because type1 (the formal type) is seen as widenable, but it shouldn't be, because this makes the conversion from DT* to DT* since commontype(zero_t, DT) is DT, rather than just nothing.
	353
	354	// AlternativeFinder finder( indexer, env );
	355	// finder.findWithAdjustment( actualExpr );
	356	// assertf( finder.get_alternatives().size() > 0, "Somehow castable expression failed to find alternatives." );
	357	// assertf( finder.get_alternatives().size() == 1, "Somehow got multiple alternatives for known cast expression." );
	358	// Alternative & alt = finder.get_alternatives().front();
	359	// delete actualExpr;
	360	// actualExpr = alt.expr->clone();
	361	}
	362	return convCost;
	363	}
	364
	365	Cost computeApplicationConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) {
[e3e16bc]	366	ApplicationExpr appExpr = strict_dynamic_cast< ApplicationExpr >( alt.expr );
	367	PointerType pointer = strict_dynamic_cast< PointerType >( appExpr->get_function()->get_result() );
	368	FunctionType function = strict_dynamic_cast< FunctionType >( pointer->get_base() );
[a32b204]	369
[89be1c68]	370	Cost convCost = Cost::zero;
[a32b204]	371	std::list< DeclarationWithType* >& formals = function->get_parameters();
	372	std::list< DeclarationWithType* >::iterator formal = formals.begin();
	373	std::list< Expression* >& actuals = appExpr->get_args();
[0362d42]	374
[a32b204]	375	for ( std::list< Expression* >::iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) {
[53e3b4a]	376	Type * actualType = (*actualExpr)->get_result();
[a32b204]	377	PRINT(
[6ed1d4b]	378	std::cerr << "actual expression:" << std::endl;
	379	(*actualExpr)->print( std::cerr, 8 );
	380	std::cerr << "--- results are" << std::endl;
[53e3b4a]	381	actualType->print( std::cerr, 8 );
[7c64920]	382	)
[53e3b4a]	383	if ( formal == formals.end() ) {
	384	if ( function->get_isVarArgs() ) {
[89be1c68]	385	convCost.incUnsafe();
[d06c808]	386	PRINT( std::cerr << "end of formals with varargs function: inc unsafe: " << convCost << std::endl; ; )
[b1bead1]	387	// convert reference-typed expressions to value-typed expressions
	388	referenceToRvalueConversion( *actualExpr );
[53e3b4a]	389	continue;
	390	} else {
	391	return Cost::infinity;
[7c64920]	392	}
[53e3b4a]	393	}
	394	Type * formalType = (*formal)->get_type();
[ddf8a29]	395	convCost += computeExpressionConversionCost( *actualExpr, formalType, indexer, alt.env );
[53e3b4a]	396	++formal; // can't be in for-loop update because of the continue
[d9a0e76]	397	}
[a32b204]	398	if ( formal != formals.end() ) {
	399	return Cost::infinity;
[d9a0e76]	400	}
	401
[a32b204]	402	for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) {
[ddf8a29]	403	convCost += computeConversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env );
[a32b204]	404	}
[d9a0e76]	405
[a32b204]	406	return convCost;
	407	}
[d9a0e76]	408
[8c84ebd]	409	/// Adds type variables to the open variable set and marks their assertions
[a32b204]	410	void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ) {
[8c49c0e]	411	for ( Type::ForallList::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
[2c57025]	412	unifiableVars[ (tyvar)->get_name() ] = TypeDecl::Data{ tyvar };
[a32b204]	413	for ( std::list< DeclarationWithType* >::iterator assert = (tyvar)->get_assertions().begin(); assert != (tyvar)->get_assertions().end(); ++assert ) {
[6c3a988f]	414	needAssertions[ *assert ].isUsed = true;
[a32b204]	415	}
[d9a0e76]	416	/// needAssertions.insert( needAssertions.end(), (tyvar)->get_assertions().begin(), (tyvar)->get_assertions().end() );
	417	}
	418	}
[a32b204]	419
[89b686a]	420	// /// Map of declaration uniqueIds (intended to be the assertions in an AssertionSet) to their parents and the number of times they've been included
	421	//typedef std::unordered_map< UniqueId, std::unordered_map< UniqueId, unsigned > > AssertionParentSet;
[79970ed]	422
[a1d7679]	423	static const int recursionLimit = /10/ 4; ///< Limit to depth of recursion satisfaction
[89b686a]	424	//static const unsigned recursionParentLimit = 1; ///< Limit to the number of times an assertion can recursively use itself
[51b7345]	425
[a32b204]	426	void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) {
	427	for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) {
[6c3a988f]	428	if ( i->second.isUsed ) {
[33a25f9]	429	indexer.addId( i->first );
[a32b204]	430	}
	431	}
[d9a0e76]	432	}
[79970ed]	433
[a32b204]	434	template< typename ForwardIterator, typename OutputIterator >
[79970ed]	435	void inferRecursive( ForwardIterator begin, ForwardIterator end, const Alternative &newAlt, OpenVarSet &openVars, const SymTab::Indexer &decls, const AssertionSet &newNeed, /const AssertionParentSet &needParents,/
[ebf5689]	436	int level, const SymTab::Indexer &indexer, OutputIterator out ) {
[a32b204]	437	if ( begin == end ) {
	438	if ( newNeed.empty() ) {
[6c3a988f]	439	PRINT(
	440	std::cerr << "all assertions satisfied, output alternative: ";
	441	newAlt.print( std::cerr );
	442	std::cerr << std::endl;
	443	);
[a32b204]	444	*out++ = newAlt;
	445	return;
	446	} else if ( level >= recursionLimit ) {
	447	throw SemanticError( "Too many recursive assertions" );
	448	} else {
	449	AssertionSet newerNeed;
	450	PRINT(
	451	std::cerr << "recursing with new set:" << std::endl;
	452	printAssertionSet( newNeed, std::cerr, 8 );
[7c64920]	453	)
[89b686a]	454	inferRecursive( newNeed.begin(), newNeed.end(), newAlt, openVars, decls, newerNeed, /needParents,/ level+1, indexer, out );
[a32b204]	455	return;
	456	}
	457	}
	458
	459	ForwardIterator cur = begin++;
[6c3a988f]	460	if ( ! cur->second.isUsed ) {
[89b686a]	461	inferRecursive( begin, end, newAlt, openVars, decls, newNeed, /needParents,/ level, indexer, out );
[7933351]	462	return; // xxx - should this continue? previously this wasn't here, and it looks like it should be
[a32b204]	463	}
	464	DeclarationWithType *curDecl = cur->first;
[7933351]	465
[d9a0e76]	466	PRINT(
[a32b204]	467	std::cerr << "inferRecursive: assertion is ";
	468	curDecl->print( std::cerr );
	469	std::cerr << std::endl;
[7c64920]	470	)
[0f19d763]	471	std::list< DeclarationWithType* > candidates;
[a32b204]	472	decls.lookupId( curDecl->get_name(), candidates );
[6ed1d4b]	473	/// if ( candidates.empty() ) { std::cerr << "no candidates!" << std::endl; }
[a32b204]	474	for ( std::list< DeclarationWithType* >::const_iterator candidate = candidates.begin(); candidate != candidates.end(); ++candidate ) {
	475	PRINT(
[6ed1d4b]	476	std::cerr << "inferRecursive: candidate is ";
	477	(*candidate)->print( std::cerr );
	478	std::cerr << std::endl;
[7c64920]	479	)
[79970ed]	480
[0f19d763]	481	AssertionSet newHave, newerNeed( newNeed );
[a32b204]	482	TypeEnvironment newEnv( newAlt.env );
	483	OpenVarSet newOpenVars( openVars );
	484	Type adjType = (candidate)->get_type()->clone();
	485	adjustExprType( adjType, newEnv, indexer );
	486	adjType->accept( global_renamer );
	487	PRINT(
	488	std::cerr << "unifying ";
	489	curDecl->get_type()->print( std::cerr );
	490	std::cerr << " with ";
	491	adjType->print( std::cerr );
	492	std::cerr << std::endl;
[7c64920]	493	)
[0f19d763]	494	if ( unify( curDecl->get_type(), adjType, newEnv, newerNeed, newHave, newOpenVars, indexer ) ) {
	495	PRINT(
	496	std::cerr << "success!" << std::endl;
[a32b204]	497	)
[0f19d763]	498	SymTab::Indexer newDecls( decls );
	499	addToIndexer( newHave, newDecls );
	500	Alternative newerAlt( newAlt );
	501	newerAlt.env = newEnv;
[6137fbb]	502	assertf( (candidate)->get_uniqueId(), "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() );
[22cad76]	503	DeclarationWithType candDecl = static_cast< DeclarationWithType >( Declaration::declFromId( (*candidate)->get_uniqueId() ) );
[6c3a988f]	504
	505	// everything with an empty idChain was pulled in by the current assertion.
	506	// add current assertion's idChain + current assertion's ID so that the correct inferParameters can be found.
	507	for ( auto & a : newerNeed ) {
	508	if ( a.second.idChain.empty() ) {
	509	a.second.idChain = cur->second.idChain;
	510	a.second.idChain.push_back( curDecl->get_uniqueId() );
	511	}
	512	}
	513
[89b686a]	514	//AssertionParentSet newNeedParents( needParents );
[22cad76]	515	// skip repeatingly-self-recursive assertion satisfaction
[89b686a]	516	// DOESN'T WORK: grandchild nodes conflict with their cousins
	517	//if ( newNeedParents[ curDecl->get_uniqueId() ][ candDecl->get_uniqueId() ]++ > recursionParentLimit ) continue;
[22cad76]	518	Expression *varExpr = new VariableExpr( candDecl );
[906e24d]	519	delete varExpr->get_result();
	520	varExpr->set_result( adjType->clone() );
[0f19d763]	521	PRINT(
[6ed1d4b]	522	std::cerr << "satisfying assertion " << curDecl->get_uniqueId() << " ";
	523	curDecl->print( std::cerr );
	524	std::cerr << " with declaration " << (*candidate)->get_uniqueId() << " ";
	525	(*candidate)->print( std::cerr );
	526	std::cerr << std::endl;
[7c64920]	527	)
[6c3a988f]	528	// follow the current assertion's ID chain to find the correct set of inferred parameters to add the candidate to (i.e. the set of inferred parameters belonging to the entity which requested the assertion parameter).
[df626eb]	529	InferredParams * inferParameters = &newerAlt.expr->get_inferParams();
[6c3a988f]	530	for ( UniqueId id : cur->second.idChain ) {
	531	inferParameters = (*inferParameters)[ id ].inferParams.get();
	532	}
[0f19d763]	533	// XXX: this is a memory leak, but adjType can't be deleted because it might contain assertions
[6c3a988f]	534	(inferParameters)[ curDecl->get_uniqueId() ] = ParamEntry( (candidate)->get_uniqueId(), adjType->clone(), curDecl->get_type()->clone(), varExpr );
[89b686a]	535	inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, /newNeedParents,/ level, indexer, out );
[0f19d763]	536	} else {
	537	delete adjType;
	538	}
[a32b204]	539	}
[d9a0e76]	540	}
	541
[a32b204]	542	template< typename OutputIterator >
	543	void AlternativeFinder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) {
[d9a0e76]	544	// PRINT(
[6ed1d4b]	545	// std::cerr << "inferParameters: assertions needed are" << std::endl;
	546	// printAll( need, std::cerr, 8 );
[d9a0e76]	547	// )
[a32b204]	548	SymTab::Indexer decls( indexer );
[e4d829b]	549	// PRINT(
	550	// std::cerr << "============= original indexer" << std::endl;
	551	// indexer.print( std::cerr );
	552	// std::cerr << "============= new indexer" << std::endl;
	553	// decls.print( std::cerr );
	554	// )
[0f19d763]	555	addToIndexer( have, decls );
[a32b204]	556	AssertionSet newNeed;
[89b686a]	557	//AssertionParentSet needParents;
[74b007ba]	558	PRINT(
	559	std::cerr << "env is: " << std::endl;
	560	newAlt.env.print( std::cerr, 0 );
	561	std::cerr << std::endl;
	562	)
	563
[89b686a]	564	inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, /needParents,/ 0, indexer, out );
[d9a0e76]	565	// PRINT(
[6ed1d4b]	566	// std::cerr << "declaration 14 is ";
[d9a0e76]	567	// Declaration::declFromId
	568	// *out++ = newAlt;
	569	// )
	570	}
	571
[aeb75b1]	572	/// Gets a default value from an initializer, nullptr if not present
	573	ConstantExpr* getDefaultValue( Initializer* init ) {
	574	if ( SingleInit* si = dynamic_cast<SingleInit*>( init ) ) {
	575	if ( CastExpr* ce = dynamic_cast<CastExpr*>( si->get_value() ) ) {
	576	return dynamic_cast<ConstantExpr*>( ce->get_arg() );
	577	}
	578	}
	579	return nullptr;
	580	}
	581
	582	/// State to iteratively build a match of parameter expressions to arguments
	583	struct ArgPack {
[452747a]	584	std::size_t parent; ///< Index of parent pack
[403b388]	585	std::unique_ptr<Expression> expr; ///< The argument stored here
	586	Cost cost; ///< The cost of this argument
	587	TypeEnvironment env; ///< Environment for this pack
	588	AssertionSet need; ///< Assertions outstanding for this pack
	589	AssertionSet have; ///< Assertions found for this pack
	590	OpenVarSet openVars; ///< Open variables for this pack
	591	unsigned nextArg; ///< Index of next argument in arguments list
	592	unsigned tupleStart; ///< Number of tuples that start at this index
[a8b27c6]	593	unsigned nextExpl; ///< Index of next exploded element
	594	unsigned explAlt; ///< Index of alternative for nextExpl > 0
[403b388]	595
	596	ArgPack()
	597	: parent(0), expr(), cost(Cost::zero), env(), need(), have(), openVars(), nextArg(0),
[178e4ec]	598
[a8b27c6]	599	tupleStart(0), nextExpl(0), explAlt(0) {}
[aeb75b1]	600
[11094d9]	601	ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have,
[aeb75b1]	602	const OpenVarSet& openVars)
[452747a]	603	: parent(0), expr(), cost(Cost::zero), env(env), need(need), have(have),
[a8b27c6]	604	openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {}
[11094d9]	605
[452747a]	606	ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need,
	607	AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg,
[178e4ec]	608	unsigned tupleStart = 0, Cost cost = Cost::zero, unsigned nextExpl = 0,
[a8b27c6]	609	unsigned explAlt = 0 )
[452747a]	610	: parent(parent), expr(expr->clone()), cost(cost), env(move(env)), need(move(need)),
[403b388]	611	have(move(have)), openVars(move(openVars)), nextArg(nextArg), tupleStart(tupleStart),
[a8b27c6]	612	nextExpl(nextExpl), explAlt(explAlt) {}
[452747a]	613
	614	ArgPack(const ArgPack& o, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have,
[73a5cadb]	615	OpenVarSet&& openVars, unsigned nextArg, Cost added )
[452747a]	616	: parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), cost(o.cost + added),
	617	env(move(env)), need(move(need)), have(move(have)), openVars(move(openVars)),
[a8b27c6]	618	nextArg(nextArg), tupleStart(o.tupleStart), nextExpl(0), explAlt(0) {}
[73a5cadb]	619
[a8b27c6]	620	/// true iff this pack is in the middle of an exploded argument
	621	bool hasExpl() const { return nextExpl > 0; }
[aeb75b1]	622
[a8b27c6]	623	/// Gets the list of exploded alternatives for this pack
	624	const ExplodedActual& getExpl( const ExplodedArgs& args ) const {
	625	return args[nextArg-1][explAlt];
	626	}
[aeb75b1]	627
	628	/// Ends a tuple expression, consolidating the appropriate actuals
[403b388]	629	void endTuple( const std::vector<ArgPack>& packs ) {
	630	// add all expressions in tuple to list, summing cost
[aeb75b1]	631	std::list<Expression*> exprs;
[403b388]	632	const ArgPack* pack = this;
	633	if ( expr ) { exprs.push_front( expr.release() ); }
	634	while ( pack->tupleStart == 0 ) {
	635	pack = &packs[pack->parent];
	636	exprs.push_front( pack->expr->clone() );
	637	cost += pack->cost;
[aeb75b1]	638	}
[403b388]	639	// reset pack to appropriate tuple
	640	expr.reset( new TupleExpr( exprs ) );
	641	tupleStart = pack->tupleStart - 1;
	642	parent = pack->parent;
[aeb75b1]	643	}
[4b6ef70]	644	};
[aeb75b1]	645
	646	/// Instantiates an argument to match a formal, returns false if no results left
[11094d9]	647	bool instantiateArgument( Type* formalType, Initializer* initializer,
[178e4ec]	648	const ExplodedArgs& args, std::vector<ArgPack>& results, std::size_t& genStart,
[a8b27c6]	649	const SymTab::Indexer& indexer, unsigned nTuples = 0 ) {
[aeb75b1]	650	if ( TupleType* tupleType = dynamic_cast<TupleType*>( formalType ) ) {
	651	// formalType is a TupleType - group actuals into a TupleExpr
[403b388]	652	++nTuples;
[aeb75b1]	653	for ( Type* type : *tupleType ) {
	654	// xxx - dropping initializer changes behaviour from previous, but seems correct
[452747a]	655	if ( ! instantiateArgument(
	656	type, nullptr, args, results, genStart, indexer, nTuples ) )
[aeb75b1]	657	return false;
[403b388]	658	nTuples = 0;
	659	}
	660	// re-consititute tuples for final generation
	661	for ( auto i = genStart; i < results.size(); ++i ) {
	662	results[i].endTuple( results );
[aeb75b1]	663	}
	664	return true;
	665	} else if ( TypeInstType* ttype = Tuples::isTtype( formalType ) ) {
	666	// formalType is a ttype, consumes all remaining arguments
	667	// xxx - mixing default arguments with variadic??
[403b388]	668
	669	// completed tuples; will be spliced to end of results to finish
	670	std::vector<ArgPack> finalResults{};
	671
[aeb75b1]	672	// iterate until all results completed
[403b388]	673	std::size_t genEnd;
	674	++nTuples;
	675	do {
	676	genEnd = results.size();
	677
[aeb75b1]	678	// add another argument to results
[403b388]	679	for ( std::size_t i = genStart; i < genEnd; ++i ) {
[a8b27c6]	680	auto nextArg = results[i].nextArg;
[452747a]	681
[62194cb]	682	// use next element of exploded tuple if present
[a8b27c6]	683	if ( results[i].hasExpl() ) {
	684	const ExplodedActual& expl = results[i].getExpl( args );
[403b388]	685
[a8b27c6]	686	unsigned nextExpl = results[i].nextExpl + 1;
[62194cb]	687	if ( nextExpl == expl.exprs.size() ) {
[a8b27c6]	688	nextExpl = 0;
	689	}
[403b388]	690
	691	results.emplace_back(
[178e4ec]	692	i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env),
	693	copy(results[i].need), copy(results[i].have),
	694	copy(results[i].openVars), nextArg, nTuples, Cost::zero, nextExpl,
[62194cb]	695	results[i].explAlt );
[452747a]	696
[403b388]	697	continue;
	698	}
[452747a]	699
[aeb75b1]	700	// finish result when out of arguments
[a8b27c6]	701	if ( nextArg >= args.size() ) {
[452747a]	702	ArgPack newResult{
	703	results[i].env, results[i].need, results[i].have,
[403b388]	704	results[i].openVars };
[a8b27c6]	705	newResult.nextArg = nextArg;
[403b388]	706	Type* argType;
	707
	708	if ( nTuples > 0 ) {
	709	// first iteration, push empty tuple expression
	710	newResult.parent = i;
	711	std::list<Expression*> emptyList;
	712	newResult.expr.reset( new TupleExpr( emptyList ) );
	713	argType = newResult.expr->get_result();
[aeb75b1]	714	} else {
[403b388]	715	// clone result to collect tuple
	716	newResult.parent = results[i].parent;
	717	newResult.cost = results[i].cost;
	718	newResult.tupleStart = results[i].tupleStart;
	719	newResult.expr.reset( results[i].expr->clone() );
	720	argType = newResult.expr->get_result();
	721
	722	if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {
[452747a]	723	// the case where a ttype value is passed directly is special,
[403b388]	724	// e.g. for argument forwarding purposes
[452747a]	725	// xxx - what if passing multiple arguments, last of which is
[403b388]	726	// ttype?
[452747a]	727	// xxx - what would happen if unify was changed so that unifying
	728	// tuple
	729	// types flattened both before unifying lists? then pass in
[403b388]	730	// TupleType (ttype) below.
	731	--newResult.tupleStart;
	732	} else {
	733	// collapse leftover arguments into tuple
	734	newResult.endTuple( results );
	735	argType = newResult.expr->get_result();
	736	}
[aeb75b1]	737	}
[403b388]	738
[aeb75b1]	739	// check unification for ttype before adding to final
[452747a]	740	if ( unify( ttype, argType, newResult.env, newResult.need, newResult.have,
[403b388]	741	newResult.openVars, indexer ) ) {
	742	finalResults.push_back( move(newResult) );
[aeb75b1]	743	}
[452747a]	744
[aeb75b1]	745	continue;
	746	}
	747
	748	// add each possible next argument
[a8b27c6]	749	for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
	750	const ExplodedActual& expl = args[nextArg][j];
[178e4ec]	751
[403b388]	752	// fresh copies of parent parameters for this iteration
	753	TypeEnvironment env = results[i].env;
	754	OpenVarSet openVars = results[i].openVars;
	755
[a8b27c6]	756	env.addActual( expl.env, openVars );
[11094d9]	757
[a8b27c6]	758	// skip empty tuple arguments by (near-)cloning parent into next gen
[62194cb]	759	if ( expl.exprs.empty() ) {
[73a5cadb]	760	results.emplace_back(
[452747a]	761	results[i], move(env), copy(results[i].need),
[a8b27c6]	762	copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
[452747a]	763
[403b388]	764	continue;
[4b6ef70]	765	}
[11094d9]	766
[403b388]	767	// add new result
	768	results.emplace_back(
[178e4ec]	769	i, expl.exprs.front().get(), move(env), copy(results[i].need),
	770	copy(results[i].have), move(openVars), nextArg + 1,
[62194cb]	771	nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
[aeb75b1]	772	}
	773	}
	774
	775	// reset for next round
[403b388]	776	genStart = genEnd;
	777	nTuples = 0;
	778	} while ( genEnd != results.size() );
	779
	780	// splice final results onto results
	781	for ( std::size_t i = 0; i < finalResults.size(); ++i ) {
	782	results.push_back( move(finalResults[i]) );
[aeb75b1]	783	}
[403b388]	784	return ! finalResults.empty();
[aeb75b1]	785	}
[11094d9]	786
[aeb75b1]	787	// iterate each current subresult
[403b388]	788	std::size_t genEnd = results.size();
	789	for ( std::size_t i = genStart; i < genEnd; ++i ) {
[a8b27c6]	790	auto nextArg = results[i].nextArg;
	791
[403b388]	792	// use remainder of exploded tuple if present
[a8b27c6]	793	if ( results[i].hasExpl() ) {
	794	const ExplodedActual& expl = results[i].getExpl( args );
[62194cb]	795	Expression* expr = expl.exprs[results[i].nextExpl].get();
[452747a]	796
[403b388]	797	TypeEnvironment env = results[i].env;
	798	AssertionSet need = results[i].need, have = results[i].have;
	799	OpenVarSet openVars = results[i].openVars;
[4b6ef70]	800
[62194cb]	801	Type* actualType = expr->get_result();
[4b6ef70]	802
	803	PRINT(
	804	std::cerr << "formal type is ";
	805	formalType->print( std::cerr );
	806	std::cerr << std::endl << "actual type is ";
	807	actualType->print( std::cerr );
	808	std::cerr << std::endl;
	809	)
[11094d9]	810
[403b388]	811	if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
[a8b27c6]	812	unsigned nextExpl = results[i].nextExpl + 1;
[62194cb]	813	if ( nextExpl == expl.exprs.size() ) {
[a8b27c6]	814	nextExpl = 0;
	815	}
[178e4ec]	816
[452747a]	817	results.emplace_back(
[178e4ec]	818	i, expr, move(env), move(need), move(have), move(openVars), nextArg,
[62194cb]	819	nTuples, Cost::zero, nextExpl, results[i].explAlt );
[4b6ef70]	820	}
	821
	822	continue;
[403b388]	823	}
[452747a]	824
[403b388]	825	// use default initializers if out of arguments
[a8b27c6]	826	if ( nextArg >= args.size() ) {
[aeb75b1]	827	if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) {
	828	if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) {
[403b388]	829	TypeEnvironment env = results[i].env;
	830	AssertionSet need = results[i].need, have = results[i].have;
	831	OpenVarSet openVars = results[i].openVars;
	832
[452747a]	833	if ( unify( formalType, cnst->get_type(), env, need, have, openVars,
[403b388]	834	indexer ) ) {
	835	results.emplace_back(
[452747a]	836	i, cnstExpr, move(env), move(need), move(have),
[a8b27c6]	837	move(openVars), nextArg, nTuples );
[aeb75b1]	838	}
	839	}
	840	}
[403b388]	841
[aeb75b1]	842	continue;
	843	}
	844
	845	// Check each possible next argument
[a8b27c6]	846	for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
	847	const ExplodedActual& expl = args[nextArg][j];
	848
[403b388]	849	// fresh copies of parent parameters for this iteration
	850	TypeEnvironment env = results[i].env;
	851	AssertionSet need = results[i].need, have = results[i].have;
	852	OpenVarSet openVars = results[i].openVars;
	853
[a8b27c6]	854	env.addActual( expl.env, openVars );
[4b6ef70]	855
[a8b27c6]	856	// skip empty tuple arguments by (near-)cloning parent into next gen
[62194cb]	857	if ( expl.exprs.empty() ) {
[73a5cadb]	858	results.emplace_back(
[178e4ec]	859	results[i], move(env), move(need), move(have), move(openVars),
[a8b27c6]	860	nextArg + 1, expl.cost );
[73a5cadb]	861
[4b6ef70]	862	continue;
	863	}
[aeb75b1]	864
[4b6ef70]	865	// consider only first exploded actual
[62194cb]	866	Expression* expr = expl.exprs.front().get();
	867	Type* actualType = expr->get_result()->clone();
[a585396]	868
[4b6ef70]	869	PRINT(
	870	std::cerr << "formal type is ";
	871	formalType->print( std::cerr );
	872	std::cerr << std::endl << "actual type is ";
	873	actualType->print( std::cerr );
	874	std::cerr << std::endl;
	875	)
[aeb75b1]	876
[4b6ef70]	877	// attempt to unify types
[403b388]	878	if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
	879	// add new result
	880	results.emplace_back(
[178e4ec]	881	i, expr, move(env), move(need), move(have), move(openVars), nextArg + 1,
[62194cb]	882	nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
[4b6ef70]	883	}
[aeb75b1]	884	}
	885	}
	886
	887	// reset for next parameter
[403b388]	888	genStart = genEnd;
[11094d9]	889
[403b388]	890	return genEnd != results.size();
	891	}
	892
	893	template<typename OutputIterator>
[452747a]	894	void AlternativeFinder::validateFunctionAlternative( const Alternative &func, ArgPack& result,
[403b388]	895	const std::vector<ArgPack>& results, OutputIterator out ) {
	896	ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
	897	// sum cost and accumulate actuals
	898	std::list<Expression*>& args = appExpr->get_args();
	899	Cost cost = Cost::zero;
	900	const ArgPack* pack = &result;
	901	while ( pack->expr ) {
	902	args.push_front( pack->expr->clone() );
	903	cost += pack->cost;
	904	pack = &results[pack->parent];
	905	}
	906	// build and validate new alternative
	907	Alternative newAlt( appExpr, result.env, cost );
	908	PRINT(
	909	std::cerr << "instantiate function success: " << appExpr << std::endl;
	910	std::cerr << "need assertions:" << std::endl;
	911	printAssertionSet( result.need, std::cerr, 8 );
	912	)
	913	inferParameters( result.need, result.have, newAlt, result.openVars, out );
[11094d9]	914	}
[aeb75b1]	915
	916	template<typename OutputIterator>
[11094d9]	917	void AlternativeFinder::makeFunctionAlternatives( const Alternative &func,
[a8b27c6]	918	FunctionType *funcType, const ExplodedArgs &args, OutputIterator out ) {
[aeb75b1]	919	OpenVarSet funcOpenVars;
	920	AssertionSet funcNeed, funcHave;
[3f7e12cb]	921	TypeEnvironment funcEnv( func.env );
[aeb75b1]	922	makeUnifiableVars( funcType, funcOpenVars, funcNeed );
[11094d9]	923	// add all type variables as open variables now so that those not used in the parameter
[aeb75b1]	924	// list are still considered open.
	925	funcEnv.add( funcType->get_forall() );
[11094d9]	926
[53e3b4a]	927	if ( targetType && ! targetType->isVoid() && ! funcType->get_returnVals().empty() ) {
[ea83e00a]	928	// attempt to narrow based on expected target type
	929	Type * returnType = funcType->get_returnVals().front()->get_type();
[11094d9]	930	if ( ! unify( returnType, targetType, funcEnv, funcNeed, funcHave, funcOpenVars,
[aeb75b1]	931	indexer ) ) {
	932	// unification failed, don't pursue this function alternative
[ea83e00a]	933	return;
	934	}
	935	}
	936
[aeb75b1]	937	// iteratively build matches, one parameter at a time
[403b388]	938	std::vector<ArgPack> results;
	939	results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } );
	940	std::size_t genStart = 0;
	941
[aeb75b1]	942	for ( DeclarationWithType* formal : funcType->get_parameters() ) {
	943	ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal );
[11094d9]	944	if ( ! instantiateArgument(
[403b388]	945	obj->get_type(), obj->get_init(), args, results, genStart, indexer ) )
[aeb75b1]	946	return;
	947	}
	948
	949	if ( funcType->get_isVarArgs() ) {
[403b388]	950	// append any unused arguments to vararg pack
	951	std::size_t genEnd;
	952	do {
	953	genEnd = results.size();
	954
	955	// iterate results
	956	for ( std::size_t i = genStart; i < genEnd; ++i ) {
[a8b27c6]	957	auto nextArg = results[i].nextArg;
[452747a]	958
[403b388]	959	// use remainder of exploded tuple if present
[a8b27c6]	960	if ( results[i].hasExpl() ) {
	961	const ExplodedActual& expl = results[i].getExpl( args );
[403b388]	962
[a8b27c6]	963	unsigned nextExpl = results[i].nextExpl + 1;
[62194cb]	964	if ( nextExpl == expl.exprs.size() ) {
[a8b27c6]	965	nextExpl = 0;
	966	}
[403b388]	967
	968	results.emplace_back(
[178e4ec]	969	i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env),
	970	copy(results[i].need), copy(results[i].have),
	971	copy(results[i].openVars), nextArg, 0, Cost::zero, nextExpl,
[62194cb]	972	results[i].explAlt );
[452747a]	973
[403b388]	974	continue;
	975	}
	976
	977	// finish result when out of arguments
[a8b27c6]	978	if ( nextArg >= args.size() ) {
[403b388]	979	validateFunctionAlternative( func, results[i], results, out );
[fae6f21]	980
[aeb75b1]	981	continue;
	982	}
	983
	984	// add each possible next argument
[a8b27c6]	985	for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
	986	const ExplodedActual& expl = args[nextArg][j];
	987
[403b388]	988	// fresh copies of parent parameters for this iteration
	989	TypeEnvironment env = results[i].env;
	990	OpenVarSet openVars = results[i].openVars;
	991
[a8b27c6]	992	env.addActual( expl.env, openVars );
[d551d0a]	993
[a8b27c6]	994	// skip empty tuple arguments by (near-)cloning parent into next gen
[62194cb]	995	if ( expl.exprs.empty() ) {
[452747a]	996	results.emplace_back(
	997	results[i], move(env), copy(results[i].need),
[a8b27c6]	998	copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
[178e4ec]	999
[403b388]	1000	continue;
	1001	}
[d551d0a]	1002
[403b388]	1003	// add new result
	1004	results.emplace_back(
[178e4ec]	1005	i, expl.exprs.front().get(), move(env), copy(results[i].need),
	1006	copy(results[i].have), move(openVars), nextArg + 1, 0,
[62194cb]	1007	expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
[aeb75b1]	1008	}
	1009	}
	1010
[403b388]	1011	genStart = genEnd;
	1012	} while ( genEnd != results.size() );
[aeb75b1]	1013	} else {
	1014	// filter out results that don't use all the arguments
[403b388]	1015	for ( std::size_t i = genStart; i < results.size(); ++i ) {
	1016	ArgPack& result = results[i];
[a8b27c6]	1017	if ( ! result.hasExpl() && result.nextArg >= args.size() ) {
[403b388]	1018	validateFunctionAlternative( func, result, results, out );
[aeb75b1]	1019	}
	1020	}
	1021	}
[d9a0e76]	1022	}
	1023
[a32b204]	1024	void AlternativeFinder::visit( UntypedExpr *untypedExpr ) {
[6ccfb7f]	1025	AlternativeFinder funcFinder( indexer, env );
[a32b204]	1026	funcFinder.findWithAdjustment( untypedExpr->get_function() );
[6ccfb7f]	1027	// if there are no function alternatives, then proceeding is a waste of time.
	1028	if ( funcFinder.alternatives.empty() ) return;
	1029
[aeb75b1]	1030	std::vector< AlternativeFinder > argAlternatives;
[11094d9]	1031	findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(),
[aeb75b1]	1032	back_inserter( argAlternatives ) );
[d9a0e76]	1033
[5af62f1]	1034	// take care of possible tuple assignments
	1035	// if not tuple assignment, assignment is taken care of as a normal function call
[c43c171]	1036	Tuples::handleTupleAssignment( *this, untypedExpr, argAlternatives );
	1037
[6ccfb7f]	1038	// find function operators
[4e66a18]	1039	static NameExpr *opExpr = new NameExpr( "?()" );
[6ccfb7f]	1040	AlternativeFinder funcOpFinder( indexer, env );
[4e66a18]	1041	// it's ok if there aren't any defined function ops
	1042	funcOpFinder.maybeFind( opExpr);
[6ccfb7f]	1043	PRINT(
	1044	std::cerr << "known function ops:" << std::endl;
[50377a4]	1045	printAlts( funcOpFinder.alternatives, std::cerr, 1 );
[6ccfb7f]	1046	)
	1047
[a8b27c6]	1048	// pre-explode arguments
	1049	ExplodedArgs argExpansions;
	1050	argExpansions.reserve( argAlternatives.size() );
	1051
	1052	for ( const AlternativeFinder& arg : argAlternatives ) {
	1053	argExpansions.emplace_back();
	1054	auto& argE = argExpansions.back();
	1055	argE.reserve( arg.alternatives.size() );
[178e4ec]	1056
[a8b27c6]	1057	for ( const Alternative& actual : arg ) {
	1058	argE.emplace_back( actual, indexer );
	1059	}
	1060	}
	1061
[a32b204]	1062	AltList candidates;
[91b8a17]	1063	SemanticError errors;
[b1bead1]	1064	for ( AltList::iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) {
[91b8a17]	1065	try {
	1066	PRINT(
	1067	std::cerr << "working on alternative: " << std::endl;
	1068	func->print( std::cerr, 8 );
	1069	)
	1070	// check if the type is pointer to function
[b1bead1]	1071	if ( PointerType pointer = dynamic_cast< PointerType >( func->expr->get_result()->stripReferences() ) ) {
[91b8a17]	1072	if ( FunctionType function = dynamic_cast< FunctionType >( pointer->get_base() ) ) {
[326338ae]	1073	Alternative newFunc( *func );
	1074	referenceToRvalueConversion( newFunc.expr );
[a8b27c6]	1075	makeFunctionAlternatives( newFunc, function, argExpansions,
[aeb75b1]	1076	std::back_inserter( candidates ) );
[b1bead1]	1077	}
	1078	} else if ( TypeInstType typeInst = dynamic_cast< TypeInstType >( func->expr->get_result()->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer)
	1079	EqvClass eqvClass;
	1080	if ( func->env.lookup( typeInst->get_name(), eqvClass ) && eqvClass.type ) {
	1081	if ( FunctionType function = dynamic_cast< FunctionType >( eqvClass.type ) ) {
[326338ae]	1082	Alternative newFunc( *func );
	1083	referenceToRvalueConversion( newFunc.expr );
[a8b27c6]	1084	makeFunctionAlternatives( newFunc, function, argExpansions,
[aeb75b1]	1085	std::back_inserter( candidates ) );
[a32b204]	1086	} // if
	1087	} // if
[11094d9]	1088	}
[91b8a17]	1089	} catch ( SemanticError &e ) {
	1090	errors.append( e );
	1091	}
[a32b204]	1092	} // for
	1093
[aeb75b1]	1094	// try each function operator ?() with each function alternative
	1095	if ( ! funcOpFinder.alternatives.empty() ) {
[a8b27c6]	1096	// add exploded function alternatives to front of argument list
	1097	std::vector<ExplodedActual> funcE;
	1098	funcE.reserve( funcFinder.alternatives.size() );
	1099	for ( const Alternative& actual : funcFinder ) {
	1100	funcE.emplace_back( actual, indexer );
	1101	}
	1102	argExpansions.insert( argExpansions.begin(), move(funcE) );
[aeb75b1]	1103
	1104	for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin();
	1105	funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
	1106	try {
	1107	// check if type is a pointer to function
[11094d9]	1108	if ( PointerType* pointer = dynamic_cast<PointerType*>(
[aeb75b1]	1109	funcOp->expr->get_result()->stripReferences() ) ) {
[11094d9]	1110	if ( FunctionType* function =
[aeb75b1]	1111	dynamic_cast<FunctionType*>( pointer->get_base() ) ) {
	1112	Alternative newFunc( *funcOp );
	1113	referenceToRvalueConversion( newFunc.expr );
[a8b27c6]	1114	makeFunctionAlternatives( newFunc, function, argExpansions,
[aeb75b1]	1115	std::back_inserter( candidates ) );
	1116	}
	1117	}
	1118	} catch ( SemanticError &e ) {
	1119	errors.append( e );
	1120	}
	1121	}
	1122	}
	1123
[91b8a17]	1124	// Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
	1125	if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }
	1126
[4b0f997]	1127	// compute conversionsion costs
[bd4f2e9]	1128	for ( Alternative& withFunc : candidates ) {
	1129	Cost cvtCost = computeApplicationConversionCost( withFunc, indexer );
[a32b204]	1130
	1131	PRINT(
[bd4f2e9]	1132	ApplicationExpr appExpr = strict_dynamic_cast< ApplicationExpr >( withFunc.expr );
[e3e16bc]	1133	PointerType pointer = strict_dynamic_cast< PointerType >( appExpr->get_function()->get_result() );
	1134	FunctionType function = strict_dynamic_cast< FunctionType >( pointer->get_base() );
[a61ad31]	1135	std::cerr << "Case +++++++++++++ " << appExpr->get_function() << std::endl;
[6ed1d4b]	1136	std::cerr << "formals are:" << std::endl;
	1137	printAll( function->get_parameters(), std::cerr, 8 );
	1138	std::cerr << "actuals are:" << std::endl;
	1139	printAll( appExpr->get_args(), std::cerr, 8 );
	1140	std::cerr << "bindings are:" << std::endl;
[bd4f2e9]	1141	withFunc.env.print( std::cerr, 8 );
[6ed1d4b]	1142	std::cerr << "cost of conversion is:" << cvtCost << std::endl;
[7c64920]	1143	)
	1144	if ( cvtCost != Cost::infinity ) {
[bd4f2e9]	1145	withFunc.cvtCost = cvtCost;
	1146	alternatives.push_back( withFunc );
[7c64920]	1147	} // if
[a32b204]	1148	} // for
[4b0f997]	1149
[bd4f2e9]	1150	candidates = move(alternatives);
[a32b204]	1151
[11094d9]	1152	// use a new list so that alternatives are not examined by addAnonConversions twice.
	1153	AltList winners;
	1154	findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) );
[ea83e00a]	1155
[452747a]	1156	// function may return struct or union value, in which case we need to add alternatives
	1157	// for implicitconversions to each of the anonymous members, must happen after findMinCost
[bd4f2e9]	1158	// since anon conversions are never the cheapest expression
[11094d9]	1159	for ( const Alternative & alt : winners ) {
[ca946a4]	1160	addAnonConversions( alt );
	1161	}
[bd4f2e9]	1162	spliceBegin( alternatives, winners );
[ca946a4]	1163
[ea83e00a]	1164	if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
	1165	// xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
	1166	// target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
	1167	// forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
	1168	// const char * x = "hello world";
	1169	// unsigned char ch = x[0];
	1170	// Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
	1171	// with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
	1172	// fix this issue in a more robust way.
	1173	targetType = nullptr;
	1174	visit( untypedExpr );
	1175	}
[a32b204]	1176	}
	1177
	1178	bool isLvalue( Expression *expr ) {
[906e24d]	1179	// xxx - recurse into tuples?
[d29fa5f]	1180	return expr->result && ( expr->get_result()->get_lvalue() \|\| dynamic_cast< ReferenceType * >( expr->get_result() ) );
[a32b204]	1181	}
	1182
	1183	void AlternativeFinder::visit( AddressExpr *addressExpr ) {
	1184	AlternativeFinder finder( indexer, env );
	1185	finder.find( addressExpr->get_arg() );
[bd4f2e9]	1186	for ( Alternative& alt : finder.alternatives ) {
	1187	if ( isLvalue( alt.expr ) ) {
[452747a]	1188	alternatives.push_back(
[bd4f2e9]	1189	Alternative{ new AddressExpr( alt.expr->clone() ), alt.env, alt.cost } );
[a32b204]	1190	} // if
	1191	} // for
	1192	}
	1193
[5809461]	1194	void AlternativeFinder::visit( LabelAddressExpr * expr ) {
[bd4f2e9]	1195	alternatives.push_back( Alternative{ expr->clone(), env, Cost::zero } );
[5809461]	1196	}
	1197
[62423350]	1198	Expression * restructureCast( Expression * argExpr, Type * toType ) {
[e6cee92]	1199	if ( argExpr->get_result()->size() > 1 && ! toType->isVoid() && ! dynamic_cast<ReferenceType *>( toType ) ) {
	1200	// Argument expression is a tuple and the target type is not void and not a reference type.
	1201	// Cast each member of the tuple to its corresponding target type, producing the tuple of those
	1202	// cast expressions. If there are more components of the tuple than components in the target type,
	1203	// then excess components do not come out in the result expression (but UniqueExprs ensure that
	1204	// side effects will still be done).
[5ccb10d]	1205	if ( Tuples::maybeImpureIgnoreUnique( argExpr ) ) {
[62423350]	1206	// expressions which may contain side effects require a single unique instance of the expression.
	1207	argExpr = new UniqueExpr( argExpr );
	1208	}
	1209	std::list< Expression * > componentExprs;
	1210	for ( unsigned int i = 0; i < toType->size(); i++ ) {
	1211	// cast each component
	1212	TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
	1213	componentExprs.push_back( restructureCast( idx, toType->getComponent( i ) ) );
	1214	}
	1215	delete argExpr;
	1216	assert( componentExprs.size() > 0 );
	1217	// produce the tuple of casts
	1218	return new TupleExpr( componentExprs );
	1219	} else {
	1220	// handle normally
	1221	return new CastExpr( argExpr, toType->clone() );
	1222	}
	1223	}
	1224
[a32b204]	1225	void AlternativeFinder::visit( CastExpr *castExpr ) {
[906e24d]	1226	Type *& toType = castExpr->get_result();
[7933351]	1227	assert( toType );
[906e24d]	1228	toType = resolveTypeof( toType, indexer );
	1229	SymTab::validateType( toType, &indexer );
	1230	adjustExprType( toType, env, indexer );
[a32b204]	1231
	1232	AlternativeFinder finder( indexer, env );
[7933351]	1233	finder.targetType = toType;
[a32b204]	1234	finder.findWithAdjustment( castExpr->get_arg() );
	1235
	1236	AltList candidates;
[452747a]	1237	for ( Alternative & alt : finder.alternatives ) {
[a32b204]	1238	AssertionSet needAssertions, haveAssertions;
	1239	OpenVarSet openVars;
	1240
	1241	// It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a
	1242	// cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results
	1243	// that are cast directly. The candidate is invalid if it has fewer results than there are types to cast
	1244	// to.
[bd4f2e9]	1245	int discardedValues = alt.expr->get_result()->size() - castExpr->get_result()->size();
[a32b204]	1246	if ( discardedValues < 0 ) continue;
[7933351]	1247	// xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
	1248	// allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
[adcdd2f]	1249	// unification run for side-effects
[452747a]	1250	unify( castExpr->get_result(), alt.expr->get_result(), alt.env, needAssertions,
[bd4f2e9]	1251	haveAssertions, openVars, indexer );
[452747a]	1252	Cost thisCost = castCost( alt.expr->get_result(), castExpr->get_result(), indexer,
[bd4f2e9]	1253	alt.env );
[7e4c4f4]	1254	PRINT(
	1255	std::cerr << "working on cast with result: " << castExpr->result << std::endl;
[452747a]	1256	std::cerr << "and expr type: " << alt.expr->result << std::endl;
	1257	std::cerr << "env: " << alt.env << std::endl;
[7e4c4f4]	1258	)
[a32b204]	1259	if ( thisCost != Cost::infinity ) {
[7e4c4f4]	1260	PRINT(
	1261	std::cerr << "has finite cost." << std::endl;
	1262	)
[a32b204]	1263	// count one safe conversion for each value that is thrown away
[89be1c68]	1264	thisCost.incSafe( discardedValues );
[452747a]	1265	Alternative newAlt( restructureCast( alt.expr->clone(), toType ), alt.env,
[bd4f2e9]	1266	alt.cost, thisCost );
[452747a]	1267	inferParameters( needAssertions, haveAssertions, newAlt, openVars,
[bd4f2e9]	1268	back_inserter( candidates ) );
[a32b204]	1269	} // if
	1270	} // for
	1271
	1272	// findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
	1273	// cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice
	1274	// selects first based on argument cost, then on conversion cost.
	1275	AltList minArgCost;
	1276	findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
	1277	findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
	1278	}
	1279
[a5f0529]	1280	void AlternativeFinder::visit( VirtualCastExpr * castExpr ) {
	1281	assertf( castExpr->get_result(), "Implicate virtual cast targets not yet supported." );
	1282	AlternativeFinder finder( indexer, env );
	1283	// don't prune here, since it's guaranteed all alternatives will have the same type
[4e66a18]	1284	finder.findWithoutPrune( castExpr->get_arg() );
[a5f0529]	1285	for ( Alternative & alt : finder.alternatives ) {
	1286	alternatives.push_back( Alternative(
	1287	new VirtualCastExpr( alt.expr->clone(), castExpr->get_result()->clone() ),
	1288	alt.env, alt.cost ) );
	1289	}
	1290	}
	1291
[a32b204]	1292	void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) {
	1293	AlternativeFinder funcFinder( indexer, env );
	1294	funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
	1295	for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
[a61ad31]	1296	// it's okay for the aggregate expression to have reference type -- cast it to the base type to treat the aggregate as the referenced value
	1297	std::unique_ptr<Expression> aggrExpr( agg->expr->clone() );
	1298	Type * aggrType = aggrExpr->get_result();
	1299	if ( dynamic_cast< ReferenceType * >( aggrType ) ) {
	1300	aggrType = aggrType->stripReferences();
	1301	aggrExpr.reset( new CastExpr( aggrExpr.release(), aggrType->clone() ) );
	1302	}
	1303	// find member of the given type
	1304	if ( StructInstType structInst = dynamic_cast< StructInstType >( aggrExpr->get_result() ) ) {
	1305	addAggMembers( structInst, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
	1306	} else if ( UnionInstType unionInst = dynamic_cast< UnionInstType >( aggrExpr->get_result() ) ) {
	1307	addAggMembers( unionInst, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
	1308	} else if ( TupleType * tupleType = dynamic_cast< TupleType * >( aggrExpr->get_result() ) ) {
	1309	addTupleMembers( tupleType, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
[a32b204]	1310	} // if
	1311	} // for
	1312	}
	1313
	1314	void AlternativeFinder::visit( MemberExpr *memberExpr ) {
	1315	alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
	1316	}
	1317
	1318	void AlternativeFinder::visit( NameExpr *nameExpr ) {
	1319	std::list< DeclarationWithType* > declList;
	1320	indexer.lookupId( nameExpr->get_name(), declList );
	1321	PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; )
[0f19d763]	1322	for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) {
[bf4b4cf]	1323	VariableExpr newExpr( *i );
[89be1c68]	1324	alternatives.push_back( Alternative( newExpr.clone(), env, Cost::zero ) );
[0f19d763]	1325	PRINT(
	1326	std::cerr << "decl is ";
	1327	(*i)->print( std::cerr );
	1328	std::cerr << std::endl;
	1329	std::cerr << "newExpr is ";
	1330	newExpr.print( std::cerr );
	1331	std::cerr << std::endl;
[7c64920]	1332	)
[0f19d763]	1333	renameTypes( alternatives.back().expr );
[4b0f997]	1334	addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
[0f19d763]	1335	} // for
[a32b204]	1336	}
	1337
	1338	void AlternativeFinder::visit( VariableExpr *variableExpr ) {
[85517ddb]	1339	// not sufficient to clone here, because variable's type may have changed
	1340	// since the VariableExpr was originally created.
	1341	alternatives.push_back( Alternative( new VariableExpr( variableExpr->get_var() ), env, Cost::zero ) );
[a32b204]	1342	}
	1343
	1344	void AlternativeFinder::visit( ConstantExpr *constantExpr ) {
	1345	alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
	1346	}
	1347
	1348	void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) {
	1349	if ( sizeofExpr->get_isType() ) {
[322b97e]	1350	Type * newType = sizeofExpr->get_type()->clone();
	1351	alternatives.push_back( Alternative( new SizeofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
[a32b204]	1352	} else {
	1353	// find all alternatives for the argument to sizeof
	1354	AlternativeFinder finder( indexer, env );
	1355	finder.find( sizeofExpr->get_expr() );
	1356	// find the lowest cost alternative among the alternatives, otherwise ambiguous
	1357	AltList winners;
	1358	findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
	1359	if ( winners.size() != 1 ) {
	1360	throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() );
	1361	} // if
	1362	// return the lowest cost alternative for the argument
	1363	Alternative &choice = winners.front();
[b37dba0]	1364	referenceToRvalueConversion( choice.expr );
[a32b204]	1365	alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
[47534159]	1366	} // if
	1367	}
	1368
	1369	void AlternativeFinder::visit( AlignofExpr *alignofExpr ) {
	1370	if ( alignofExpr->get_isType() ) {
[322b97e]	1371	Type * newType = alignofExpr->get_type()->clone();
	1372	alternatives.push_back( Alternative( new AlignofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
[47534159]	1373	} else {
	1374	// find all alternatives for the argument to sizeof
	1375	AlternativeFinder finder( indexer, env );
	1376	finder.find( alignofExpr->get_expr() );
	1377	// find the lowest cost alternative among the alternatives, otherwise ambiguous
	1378	AltList winners;
	1379	findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
	1380	if ( winners.size() != 1 ) {
	1381	throw SemanticError( "Ambiguous expression in alignof operand: ", alignofExpr->get_expr() );
	1382	} // if
	1383	// return the lowest cost alternative for the argument
	1384	Alternative &choice = winners.front();
[b37dba0]	1385	referenceToRvalueConversion( choice.expr );
[47534159]	1386	alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
[a32b204]	1387	} // if
	1388	}
	1389
[2a4b088]	1390	template< typename StructOrUnionType >
	1391	void AlternativeFinder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
	1392	std::list< Declaration* > members;
	1393	aggInst->lookup( name, members );
	1394	for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
	1395	if ( DeclarationWithType dwt = dynamic_cast< DeclarationWithType >( *i ) ) {
[79970ed]	1396	alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
[2a4b088]	1397	renameTypes( alternatives.back().expr );
	1398	} else {
	1399	assert( false );
	1400	}
	1401	}
	1402	}
[6ed1d4b]	1403
[2a4b088]	1404	void AlternativeFinder::visit( UntypedOffsetofExpr *offsetofExpr ) {
	1405	AlternativeFinder funcFinder( indexer, env );
[85517ddb]	1406	// xxx - resolveTypeof?
[2a4b088]	1407	if ( StructInstType structInst = dynamic_cast< StructInstType >( offsetofExpr->get_type() ) ) {
	1408	addOffsetof( structInst, offsetofExpr->get_member() );
	1409	} else if ( UnionInstType unionInst = dynamic_cast< UnionInstType >( offsetofExpr->get_type() ) ) {
	1410	addOffsetof( unionInst, offsetofExpr->get_member() );
	1411	}
	1412	}
[6ed1d4b]	1413
[25a054f]	1414	void AlternativeFinder::visit( OffsetofExpr *offsetofExpr ) {
	1415	alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
[afc1045]	1416	}
	1417
	1418	void AlternativeFinder::visit( OffsetPackExpr *offsetPackExpr ) {
	1419	alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
[25a054f]	1420	}
	1421
[a32b204]	1422	void AlternativeFinder::resolveAttr( DeclarationWithType funcDecl, FunctionType function, Type *argType, const TypeEnvironment &env ) {
	1423	// assume no polymorphism
	1424	// assume no implicit conversions
	1425	assert( function->get_parameters().size() == 1 );
	1426	PRINT(
[6ed1d4b]	1427	std::cerr << "resolvAttr: funcDecl is ";
	1428	funcDecl->print( std::cerr );
	1429	std::cerr << " argType is ";
	1430	argType->print( std::cerr );
	1431	std::cerr << std::endl;
[7c64920]	1432	)
	1433	if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
	1434	alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) );
	1435	for ( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) {
[906e24d]	1436	alternatives.back().expr->set_result( (*i)->get_type()->clone() );
[7c64920]	1437	} // for
	1438	} // if
[a32b204]	1439	}
	1440
	1441	void AlternativeFinder::visit( AttrExpr *attrExpr ) {
	1442	// assume no 'pointer-to-attribute'
	1443	NameExpr nameExpr = dynamic_cast< NameExpr >( attrExpr->get_attr() );
	1444	assert( nameExpr );
	1445	std::list< DeclarationWithType* > attrList;
	1446	indexer.lookupId( nameExpr->get_name(), attrList );
	1447	if ( attrExpr->get_isType() \|\| attrExpr->get_expr() ) {
	1448	for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
	1449	// check if the type is function
	1450	if ( FunctionType function = dynamic_cast< FunctionType >( (*i)->get_type() ) ) {
	1451	// assume exactly one parameter
	1452	if ( function->get_parameters().size() == 1 ) {
	1453	if ( attrExpr->get_isType() ) {
	1454	resolveAttr( *i, function, attrExpr->get_type(), env );
	1455	} else {
	1456	AlternativeFinder finder( indexer, env );
	1457	finder.find( attrExpr->get_expr() );
	1458	for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
[906e24d]	1459	if ( choice->expr->get_result()->size() == 1 ) {
	1460	resolveAttr(*i, function, choice->expr->get_result(), choice->env );
[a32b204]	1461	} // fi
	1462	} // for
	1463	} // if
	1464	} // if
	1465	} // if
	1466	} // for
	1467	} else {
	1468	for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
	1469	VariableExpr newExpr( *i );
[89be1c68]	1470	alternatives.push_back( Alternative( newExpr.clone(), env, Cost::zero ) );
[a32b204]	1471	renameTypes( alternatives.back().expr );
	1472	} // for
	1473	} // if
	1474	}
	1475
	1476	void AlternativeFinder::visit( LogicalExpr *logicalExpr ) {
	1477	AlternativeFinder firstFinder( indexer, env );
	1478	firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
	1479	for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
	1480	AlternativeFinder secondFinder( indexer, first->env );
	1481	secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
	1482	for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
	1483	LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() );
	1484	alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) );
[d9a0e76]	1485	}
	1486	}
	1487	}
[51b7345]	1488
[a32b204]	1489	void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) {
[32b8144]	1490	// find alternatives for condition
[a32b204]	1491	AlternativeFinder firstFinder( indexer, env );
	1492	firstFinder.findWithAdjustment( conditionalExpr->get_arg1() );
	1493	for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
[32b8144]	1494	// find alternatives for true expression
[a32b204]	1495	AlternativeFinder secondFinder( indexer, first->env );
	1496	secondFinder.findWithAdjustment( conditionalExpr->get_arg2() );
	1497	for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
[32b8144]	1498	// find alterantives for false expression
[a32b204]	1499	AlternativeFinder thirdFinder( indexer, second->env );
	1500	thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() );
	1501	for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) {
[32b8144]	1502	// unify true and false types, then infer parameters to produce new alternatives
[a32b204]	1503	OpenVarSet openVars;
	1504	AssertionSet needAssertions, haveAssertions;
	1505	Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost );
[668e971a]	1506	Type* commonType = nullptr;
[906e24d]	1507	if ( unify( second->expr->get_result(), third->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
[a32b204]	1508	ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() );
[906e24d]	1509	newExpr->set_result( commonType ? commonType : second->expr->get_result()->clone() );
[ddf8a29]	1510	// convert both options to the conditional result type
	1511	newAlt.cost += computeExpressionConversionCost( newExpr->arg2, newExpr->result, indexer, newAlt.env );
	1512	newAlt.cost += computeExpressionConversionCost( newExpr->arg3, newExpr->result, indexer, newAlt.env );
[a32b204]	1513	newAlt.expr = newExpr;
	1514	inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
	1515	} // if
	1516	} // for
	1517	} // for
	1518	} // for
	1519	}
	1520
	1521	void AlternativeFinder::visit( CommaExpr *commaExpr ) {
	1522	TypeEnvironment newEnv( env );
	1523	Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
	1524	AlternativeFinder secondFinder( indexer, newEnv );
	1525	secondFinder.findWithAdjustment( commaExpr->get_arg2() );
	1526	for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) {
	1527	alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) );
	1528	} // for
	1529	delete newFirstArg;
	1530	}
	1531
[32b8144]	1532	void AlternativeFinder::visit( RangeExpr * rangeExpr ) {
	1533	// resolve low and high, accept alternatives whose low and high types unify
	1534	AlternativeFinder firstFinder( indexer, env );
	1535	firstFinder.findWithAdjustment( rangeExpr->get_low() );
	1536	for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
	1537	AlternativeFinder secondFinder( indexer, first->env );
	1538	secondFinder.findWithAdjustment( rangeExpr->get_high() );
	1539	for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
	1540	OpenVarSet openVars;
	1541	AssertionSet needAssertions, haveAssertions;
	1542	Alternative newAlt( 0, second->env, first->cost + second->cost );
	1543	Type* commonType = nullptr;
	1544	if ( unify( first->expr->get_result(), second->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
	1545	RangeExpr *newExpr = new RangeExpr( first->expr->clone(), second->expr->clone() );
	1546	newExpr->set_result( commonType ? commonType : first->expr->get_result()->clone() );
	1547	newAlt.expr = newExpr;
	1548	inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
	1549	} // if
	1550	} // for
	1551	} // for
	1552	}
	1553
[907eccb]	1554	void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) {
[bd4f2e9]	1555	std::vector< AlternativeFinder > subExprAlternatives;
[452747a]	1556	findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(),
[bd4f2e9]	1557	back_inserter( subExprAlternatives ) );
	1558	std::vector< AltList > possibilities;
[452747a]	1559	combos( subExprAlternatives.begin(), subExprAlternatives.end(),
[bd4f2e9]	1560	back_inserter( possibilities ) );
	1561	for ( const AltList& alts : possibilities ) {
[907eccb]	1562	std::list< Expression * > exprs;
[bd4f2e9]	1563	makeExprList( alts, exprs );
[a32b204]	1564
	1565	TypeEnvironment compositeEnv;
[bd4f2e9]	1566	simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
[452747a]	1567	alternatives.push_back(
[bd4f2e9]	1568	Alternative{ new TupleExpr( exprs ), compositeEnv, sumCost( alts ) } );
[a32b204]	1569	} // for
[d9a0e76]	1570	}
[dc2e7e0]	1571
[907eccb]	1572	void AlternativeFinder::visit( TupleExpr *tupleExpr ) {
	1573	alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
	1574	}
	1575
[dc2e7e0]	1576	void AlternativeFinder::visit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
	1577	alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
	1578	}
[b6fe7e6]	1579
	1580	void AlternativeFinder::visit( ConstructorExpr * ctorExpr ) {
	1581	AlternativeFinder finder( indexer, env );
	1582	// don't prune here, since it's guaranteed all alternatives will have the same type
	1583	// (giving the alternatives different types is half of the point of ConstructorExpr nodes)
[4e66a18]	1584	finder.findWithoutPrune( ctorExpr->get_callExpr() );
[b6fe7e6]	1585	for ( Alternative & alt : finder.alternatives ) {
	1586	alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
	1587	}
	1588	}
[8f7cea1]	1589
	1590	void AlternativeFinder::visit( TupleIndexExpr *tupleExpr ) {
	1591	alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
	1592	}
[aa8f9df]	1593
	1594	void AlternativeFinder::visit( TupleAssignExpr *tupleAssignExpr ) {
	1595	alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) );
	1596	}
[bf32bb8]	1597
	1598	void AlternativeFinder::visit( UniqueExpr *unqExpr ) {
	1599	AlternativeFinder finder( indexer, env );
	1600	finder.findWithAdjustment( unqExpr->get_expr() );
	1601	for ( Alternative & alt : finder.alternatives ) {
[141b786]	1602	// ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
[77971f6]	1603	UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
[141b786]	1604	alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
[bf32bb8]	1605	}
	1606	}
	1607
[722617d]	1608	void AlternativeFinder::visit( StmtExpr *stmtExpr ) {
	1609	StmtExpr * newStmtExpr = stmtExpr->clone();
	1610	ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
	1611	// xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
	1612	alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
	1613	}
	1614
[e4d829b]	1615	void AlternativeFinder::visit( UntypedInitExpr *initExpr ) {
[62423350]	1616	// handle each option like a cast
[e4d829b]	1617	AltList candidates;
[62423350]	1618	PRINT( std::cerr << "untyped init expr: " << initExpr << std::endl; )
[e4d829b]	1619	// O(N^2) checks of d-types with e-types
[62423350]	1620	for ( InitAlternative & initAlt : initExpr->get_initAlts() ) {
[228099e]	1621	Type * toType = resolveTypeof( initAlt.type->clone(), indexer );
[62423350]	1622	SymTab::validateType( toType, &indexer );
	1623	adjustExprType( toType, env, indexer );
	1624	// Ideally the call to findWithAdjustment could be moved out of the loop, but unfortunately it currently has to occur inside or else
	1625	// polymorphic return types are not properly bound to the initialization type, since return type variables are only open for the duration of resolving
	1626	// the UntypedExpr. This is only actually an issue in initialization contexts that allow more than one possible initialization type, but it is still suboptimal.
	1627	AlternativeFinder finder( indexer, env );
	1628	finder.targetType = toType;
	1629	finder.findWithAdjustment( initExpr->get_expr() );
	1630	for ( Alternative & alt : finder.get_alternatives() ) {
	1631	TypeEnvironment newEnv( alt.env );
[e4d829b]	1632	AssertionSet needAssertions, haveAssertions;
[62423350]	1633	OpenVarSet openVars; // find things in env that don't have a "representative type" and claim those are open vars?
	1634	PRINT( std::cerr << " @ " << toType << " " << initAlt.designation << std::endl; )
[e4d829b]	1635	// It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a
	1636	// cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results
	1637	// that are cast directly. The candidate is invalid if it has fewer results than there are types to cast
	1638	// to.
[62423350]	1639	int discardedValues = alt.expr->get_result()->size() - toType->size();
[e4d829b]	1640	if ( discardedValues < 0 ) continue;
	1641	// xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
	1642	// allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
	1643	// unification run for side-effects
[62423350]	1644	unify( toType, alt.expr->get_result(), newEnv, needAssertions, haveAssertions, openVars, indexer ); // xxx - do some inspecting on this line... why isn't result bound to initAlt.type??
[e4d829b]	1645
[62423350]	1646	Cost thisCost = castCost( alt.expr->get_result(), toType, indexer, newEnv );
[e4d829b]	1647	if ( thisCost != Cost::infinity ) {
	1648	// count one safe conversion for each value that is thrown away
[89be1c68]	1649	thisCost.incSafe( discardedValues );
[bb666f64]	1650	Alternative newAlt( new InitExpr( restructureCast( alt.expr->clone(), toType ), initAlt.designation->clone() ), newEnv, alt.cost, thisCost );
	1651	inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
[e4d829b]	1652	}
	1653	}
	1654	}
	1655
	1656	// findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
	1657	// cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice
	1658	// selects first based on argument cost, then on conversion cost.
	1659	AltList minArgCost;
	1660	findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
	1661	findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
	1662	}
[51b7345]	1663	} // namespace ResolvExpr
[a32b204]	1664
	1665	// Local Variables: //
	1666	// tab-width: 4 //
	1667	// mode: c++ //
	1668	// compile-command: "make install" //
	1669	// End: //

Note: See TracBrowser for help on using the repository browser.

Download in other formats: