Context Navigation

source: src/ResolvExpr/AlternativeFinder.cc @ 1a59641

new-env

Last change on this file since 1a59641 was 1a59641, checked in by Aaron Moss <a3moss@…>, 5 years ago
Fix open var handling in BF assn resolution; memory usage reasonable again
Property mode set to `100644`
File size: 88.5 KB

Line
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	//
7	// AlternativeFinder.cc --
8	//
9	// Author : Richard C. Bilson
10	// Created On : Sat May 16 23:52:08 2015
11	// Last Modified By : Aaron B. Moss
12	// Last Modified On : Mon Jun 11 16:40:00 2018
13	// Update Count : 34
14	//
15
16	#include <algorithm> // for copy
17	#include <cassert> // for strict_dynamic_cast, assert, assertf
18	#include <cstddef> // for size_t
19	#include <iostream> // for operator<<, cerr, ostream, endl
20	#include <iterator> // for back_insert_iterator, back_inserter
21	#include <limits> // for numeric_limits<int>::max()
22	#include <list> // for _List_iterator, list, _List_const_...
23	#include <map> // for _Rb_tree_iterator, map, _Rb_tree_c...
24	#include <memory> // for allocator_traits<>::value_type
25	#include <tuple> // for tuple
26	#include <utility> // for pair
27	#include <vector> // for vector
28
29	#include "Alternative.h" // for AltList, Alternative
30	#include "AlternativeFinder.h"
31	#include "Common/SemanticError.h" // for SemanticError
32	#include "Common/utility.h" // for deleteAll, printAll, CodeLocation
33	#include "Cost.h" // for Cost, Cost::zero, operator<<, Cost...
34	#include "ExplodedActual.h" // for ExplodedActual
35	#include "InitTweak/InitTweak.h" // for getFunctionName
36	#include "RenameVars.h" // for RenameVars, global_renamer
37	#include "ResolveTypeof.h" // for resolveTypeof
38	#include "Resolver.h" // for resolveStmtExpr
39	#include "Common/FilterCombos.h" // for filterCombos
40	#include "Common/GC.h" // for new_static_root
41	#include "SymTab/Indexer.h" // for Indexer
42	#include "SymTab/Mangler.h" // for Mangler
43	#include "SymTab/Validate.h" // for validateType
44	#include "SynTree/Constant.h" // for Constant
45	#include "SynTree/Declaration.h" // for DeclarationWithType, TypeDecl, Dec...
46	#include "SynTree/Expression.h" // for Expression, CastExpr, NameExpr
47	#include "SynTree/Initializer.h" // for SingleInit, operator<<, Designation
48	#include "SynTree/SynTree.h" // for UniqueId
49	#include "SynTree/Type.h" // for Type, FunctionType, PointerType
50	#include "Tuples/Explode.h" // for explode
51	#include "Tuples/Tuples.h" // for isTtype, handleTupleAssignment
52	#include "Unify.h" // for unify
53	#include "typeops.h" // for adjustExprType, polyCost, castCost
54
55	extern bool resolvep;
56	#define PRINT( text ) if ( resolvep ) { text }
57	//#define DEBUG_COST
58
59	using std::move;
60
61	/// copies any copyable type
62	template<typename T>
63	T copy(const T& x) { return x; }
64
65	namespace ResolvExpr {
66	struct AlternativeFinder::Finder : public WithShortCircuiting {
67	Finder( AlternativeFinder & altFinder ) : altFinder( altFinder ), indexer( altFinder.indexer ), alternatives( altFinder.alternatives ), env( altFinder.env ), targetType( altFinder.targetType ) {}
68
69	void previsit( BaseSyntaxNode * ) { visit_children = false; }
70
71	void postvisit( ApplicationExpr * applicationExpr );
72	void postvisit( UntypedExpr * untypedExpr );
73	void postvisit( AddressExpr * addressExpr );
74	void postvisit( LabelAddressExpr * labelExpr );
75	void postvisit( CastExpr * castExpr );
76	void postvisit( VirtualCastExpr * castExpr );
77	void postvisit( UntypedMemberExpr * memberExpr );
78	void postvisit( MemberExpr * memberExpr );
79	void postvisit( NameExpr * variableExpr );
80	void postvisit( VariableExpr * variableExpr );
81	void postvisit( ConstantExpr * constantExpr );
82	void postvisit( SizeofExpr * sizeofExpr );
83	void postvisit( AlignofExpr * alignofExpr );
84	void postvisit( UntypedOffsetofExpr * offsetofExpr );
85	void postvisit( OffsetofExpr * offsetofExpr );
86	void postvisit( OffsetPackExpr * offsetPackExpr );
87	void postvisit( AttrExpr * attrExpr );
88	void postvisit( LogicalExpr * logicalExpr );
89	void postvisit( ConditionalExpr * conditionalExpr );
90	void postvisit( CommaExpr * commaExpr );
91	void postvisit( ImplicitCopyCtorExpr * impCpCtorExpr );
92	void postvisit( ConstructorExpr * ctorExpr );
93	void postvisit( RangeExpr * rangeExpr );
94	void postvisit( UntypedTupleExpr * tupleExpr );
95	void postvisit( TupleExpr * tupleExpr );
96	void postvisit( TupleIndexExpr * tupleExpr );
97	void postvisit( TupleAssignExpr * tupleExpr );
98	void postvisit( UniqueExpr * unqExpr );
99	void postvisit( StmtExpr * stmtExpr );
100	void postvisit( UntypedInitExpr * initExpr );
101	void postvisit( InitExpr * initExpr );
102	void postvisit( DeletedExpr * delExpr );
103	void postvisit( GenericExpr * genExpr );
104
105	/// Adds alternatives for anonymous members
106	void addAnonConversions( const Alternative & alt );
107	/// Adds alternatives for member expressions, given the aggregate, conversion cost for that aggregate, and name of the member
108	template< typename StructOrUnionType > void addAggMembers( StructOrUnionType aggInst, Expression expr, const Cost &newCost, const TypeEnvironment & env, const std::string & name );
109	/// Adds alternatives for member expressions where the left side has tuple type
110	void addTupleMembers( TupleType * tupleType, Expression expr, const Cost &newCost, const TypeEnvironment & env, Expression member );
111	/// Adds alternatives for offsetof expressions, given the base type and name of the member
112	template< typename StructOrUnionType > void addOffsetof( StructOrUnionType *aggInst, const std::string &name );
113	/// Takes a final result and checks if its assertions can be satisfied
114	template<typename OutputIterator>
115	void validateFunctionAlternative( const Alternative &func, ArgPack& result, const std::vector<ArgPack>& results, OutputIterator out );
116	/// Finds matching alternatives for a function, given a set of arguments
117	template<typename OutputIterator>
118	void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const ExplodedArgs& args, OutputIterator out );
119	/// Checks if assertion parameters match for a new alternative
120	template< typename OutputIterator >
121	void inferParameters( const AssertionSet &need, AssertionSet &have, Alternative &&newAlt, OpenVarSet &openVars, OutputIterator out );
122	private:
123	AlternativeFinder & altFinder;
124	const SymTab::Indexer &indexer;
125	AltList & alternatives;
126	const TypeEnvironment &env;
127	Type *& targetType;
128	};
129
130	Cost sumCost( const AltList &in ) {
131	Cost total = Cost::zero;
132	for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
133	total += i->cost;
134	}
135	return total;
136	}
137
138	void printAlts( const AltList &list, std::ostream &os, unsigned int indentAmt ) {
139	Indenter indent = { Indenter::tabsize, indentAmt };
140	for ( AltList::const_iterator i = list.begin(); i != list.end(); ++i ) {
141	i->print( os, indent );
142	os << std::endl;
143	}
144	}
145
146	namespace {
147	void makeExprList( const AltList &in, std::list< Expression* > &out ) {
148	for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
149	out.push_back( i->expr->clone() );
150	}
151	}
152
153	struct PruneStruct {
154	bool isAmbiguous;
155	AltList::iterator candidate;
156	PruneStruct() {}
157	PruneStruct( AltList::iterator candidate ): isAmbiguous( false ), candidate( candidate ) {}
158	};
159
160	/// Prunes a list of alternatives down to those that have the minimum conversion cost for a given return type; skips ambiguous interpretations
161	template< typename InputIterator, typename OutputIterator >
162	void pruneAlternatives( InputIterator begin, InputIterator end, OutputIterator out ) {
163	// select the alternatives that have the minimum conversion cost for a particular set of result types
164	std::map< std::string, PruneStruct > selected;
165	for ( AltList::iterator candidate = begin; candidate != end; ++candidate ) {
166	PruneStruct current( candidate );
167	std::string mangleName;
168	{
169	Type * newType = candidate->expr->get_result()->clone();
170	candidate->env.apply( newType );
171	mangleName = SymTab::Mangler::mangle( newType );
172	}
173	std::map< std::string, PruneStruct >::iterator mapPlace = selected.find( mangleName );
174	if ( mapPlace != selected.end() ) {
175	if ( candidate->cost < mapPlace->second.candidate->cost ) {
176	PRINT(
177	std::cerr << "cost " << candidate->cost << " beats " << mapPlace->second.candidate->cost << std::endl;
178	)
179	selected[ mangleName ] = current;
180	} else if ( candidate->cost == mapPlace->second.candidate->cost ) {
181	// if one of the candidates contains a deleted identifier, can pick the other, since
182	// deleted expressions should not be ambiguous if there is another option that is at least as good
183	if ( findDeletedExpr( candidate->expr ) ) {
184	// do nothing
185	PRINT( std::cerr << "candidate is deleted" << std::endl; )
186	} else if ( findDeletedExpr( mapPlace->second.candidate->expr ) ) {
187	PRINT( std::cerr << "current is deleted" << std::endl; )
188	selected[ mangleName ] = current;
189	} else {
190	PRINT(
191	std::cerr << "marking ambiguous" << std::endl;
192	)
193	mapPlace->second.isAmbiguous = true;
194	}
195	} else {
196	PRINT(
197	std::cerr << "cost " << candidate->cost << " loses to " << mapPlace->second.candidate->cost << std::endl;
198	)
199	}
200	} else {
201	selected[ mangleName ] = current;
202	}
203	}
204
205	// accept the alternatives that were unambiguous
206	for ( std::map< std::string, PruneStruct >::iterator target = selected.begin(); target != selected.end(); ++target ) {
207	if ( ! target->second.isAmbiguous ) {
208	Alternative &alt = *target->second.candidate;
209	alt.env.applyFree( alt.expr->get_result() );
210	*out++ = alt;
211	}
212	}
213	}
214
215	void renameTypes( Expression *expr ) {
216	renameTyVars( expr->result );
217	}
218	} // namespace
219
220	void referenceToRvalueConversion( Expression *& expr, Cost & cost ) {
221	if ( dynamic_cast< ReferenceType * >( expr->get_result() ) ) {
222	// cast away reference from expr
223	expr = new CastExpr( expr, expr->get_result()->stripReferences()->clone() );
224	cost.incReference();
225	}
226	}
227
228	template< typename InputIterator, typename OutputIterator >
229	void AlternativeFinder::findSubExprs( InputIterator begin, InputIterator end, OutputIterator out ) {
230	while ( begin != end ) {
231	AlternativeFinder finder( indexer, env );
232	finder.findWithAdjustment( *begin );
233	// XXX either this
234	//Designators::fixDesignations( finder, (*begin++)->get_argName() );
235	// or XXX this
236	begin++;
237	PRINT(
238	std::cerr << "findSubExprs" << std::endl;
239	printAlts( finder.alternatives, std::cerr );
240	)
241	*out++ = finder;
242	}
243	}
244
245	AlternativeFinder::AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env )
246	: indexer( indexer ), env( env ) {
247	}
248
249	void AlternativeFinder::find( Expression *expr, ResolvMode mode ) {
250	PassVisitor<Finder> finder( *this );
251	expr->accept( finder );
252	if ( mode.failFast && alternatives.empty() ) {
253	PRINT(
254	std::cerr << "No reasonable alternatives for expression " << expr << std::endl;
255	)
256	SemanticError( expr, "No reasonable alternatives for expression " );
257	}
258	if ( mode.prune ) {
259	auto oldsize = alternatives.size();
260	PRINT(
261	std::cerr << "alternatives before prune:" << std::endl;
262	printAlts( alternatives, std::cerr );
263	)
264	AltList pruned;
265	pruneAlternatives( alternatives.begin(), alternatives.end(), back_inserter( pruned ) );
266	if ( mode.failFast && pruned.empty() ) {
267	std::ostringstream stream;
268	AltList winners;
269	findMinCost( alternatives.begin(), alternatives.end(), back_inserter( winners ) );
270	stream << "Cannot choose between " << winners.size() << " alternatives for expression\n";
271	expr->print( stream );
272	stream << " Alternatives are:\n";
273	printAlts( winners, stream, 1 );
274	SemanticError( expr->location, stream.str() );
275	}
276	alternatives = move(pruned);
277	PRINT(
278	std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
279	)
280	PRINT(
281	std::cerr << "there are " << alternatives.size() << " alternatives after elimination" << std::endl;
282	)
283	}
284	// adjust types after pruning so that types substituted by pruneAlternatives are correctly adjusted
285	if ( mode.adjust ) {
286	for ( Alternative& i : alternatives ) {
287	adjustExprType( i.expr->result, i.env, indexer );
288	}
289	}
290
291	// Central location to handle gcc extension keyword, etc. for all expression types.
292	for ( Alternative &iter: alternatives ) {
293	iter.expr->set_extension( expr->get_extension() );
294	iter.expr->location = expr->location;
295	} // for
296	}
297
298	void AlternativeFinder::findWithAdjustment( Expression *expr ) {
299	find( expr, ResolvMode::withAdjustment() );
300	}
301
302	void AlternativeFinder::findWithoutPrune( Expression * expr ) {
303	find( expr, ResolvMode::withoutPrune() );
304	}
305
306	void AlternativeFinder::maybeFind( Expression * expr ) {
307	find( expr, ResolvMode::withoutFailFast() );
308	}
309
310	void AlternativeFinder::Finder::addAnonConversions( const Alternative & alt ) {
311	// adds anonymous member interpretations whenever an aggregate value type is seen.
312	// 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
313	Expression* aggrExpr = alt.expr->clone();
314	alt.env.apply( aggrExpr->result );
315	Type * aggrType = aggrExpr->result;
316	if ( dynamic_cast< ReferenceType * >( aggrType ) ) {
317	aggrType = aggrType->stripReferences();
318	aggrExpr = new CastExpr{ aggrExpr, aggrType->clone() };
319	}
320
321	if ( StructInstType structInst = dynamic_cast< StructInstType >( aggrExpr->result ) ) {
322	addAggMembers( structInst, aggrExpr, alt.cost+Cost::safe, alt.env, "" );
323	} else if ( UnionInstType unionInst = dynamic_cast< UnionInstType >( aggrExpr->result ) ) {
324	addAggMembers( unionInst, aggrExpr, alt.cost+Cost::safe, alt.env, "" );
325	} // if
326	}
327
328	template< typename StructOrUnionType >
329	void AlternativeFinder::Finder::addAggMembers( StructOrUnionType aggInst, Expression expr, const Cost &newCost, const TypeEnvironment & env, const std::string & name ) {
330	std::list< Declaration* > members;
331	aggInst->lookup( name, members );
332
333	for ( Declaration * decl : members ) {
334	if ( DeclarationWithType dwt = dynamic_cast< DeclarationWithType >( decl ) ) {
335	// addAnonAlternatives uses vector::push_back, which invalidates references to existing elements, so
336	// can't construct in place and use vector::back
337	Alternative newAlt( new MemberExpr( dwt, expr->clone() ), env, newCost );
338	renameTypes( newAlt.expr );
339	addAnonConversions( newAlt ); // add anonymous member interpretations whenever an aggregate value type is seen as a member expression.
340	alternatives.push_back( std::move(newAlt) );
341	} else {
342	assert( false );
343	}
344	}
345	}
346
347	void AlternativeFinder::Finder::addTupleMembers( TupleType * tupleType, Expression expr, const Cost &newCost, const TypeEnvironment & env, Expression member ) {
348	if ( ConstantExpr * constantExpr = dynamic_cast< ConstantExpr * >( member ) ) {
349	// get the value of the constant expression as an int, must be between 0 and the length of the tuple type to have meaning
350	auto val = constantExpr->intValue();
351	std::string tmp;
352	if ( val >= 0 && (unsigned long long)val < tupleType->size() ) {
353	alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
354	} // if
355	} // if
356	}
357
358	void AlternativeFinder::Finder::postvisit( ApplicationExpr *applicationExpr ) {
359	alternatives.push_back( Alternative( applicationExpr, env, Cost::zero ) );
360	}
361
362	Cost computeConversionCost( Type * actualType, Type * formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) {
363	PRINT(
364	std::cerr << std::endl << "converting ";
365	actualType->print( std::cerr, 8 );
366	std::cerr << std::endl << " to ";
367	formalType->print( std::cerr, 8 );
368	std::cerr << std::endl << "environment is: ";
369	env.print( std::cerr, 8 );
370	std::cerr << std::endl;
371	)
372	Cost convCost = conversionCost( actualType, formalType, indexer, env );
373	PRINT(
374	std::cerr << std::endl << "cost is " << convCost << std::endl;
375	)
376	if ( convCost == Cost::infinity ) {
377	return convCost;
378	}
379	convCost.incPoly( polyCost( formalType, env, indexer ) + polyCost( actualType, env, indexer ) );
380	PRINT(
381	std::cerr << "cost with polycost is " << convCost << std::endl;
382	)
383	return convCost;
384	}
385
386	Cost computeExpressionConversionCost( Expression & actualExpr, Type formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) {
387	Cost convCost = computeConversionCost( actualExpr->result, formalType, indexer, env );
388
389	// if there is a non-zero conversion cost, ignoring poly cost, then the expression requires conversion.
390	// ignore poly cost for now, since this requires resolution of the cast to infer parameters and this
391	// does not currently work for the reason stated below.
392	Cost tmpCost = convCost;
393	tmpCost.incPoly( -tmpCost.get_polyCost() );
394	if ( tmpCost != Cost::zero ) {
395	Type *newType = formalType->clone();
396	env.apply( newType );
397	actualExpr = new CastExpr( actualExpr, newType );
398	// 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
399	// inconsistent, once this is fixed it should be possible to resolve the cast.
400	// 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.
401
402	// AlternativeFinder finder( indexer, env );
403	// finder.findWithAdjustment( actualExpr );
404	// assertf( finder.get_alternatives().size() > 0, "Somehow castable expression failed to find alternatives." );
405	// assertf( finder.get_alternatives().size() == 1, "Somehow got multiple alternatives for known cast expression." );
406	// Alternative & alt = finder.get_alternatives().front();
407	// delete actualExpr;
408	// actualExpr = alt.expr->clone();
409	}
410	return convCost;
411	}
412
413	Cost computeApplicationConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) {
414	ApplicationExpr appExpr = strict_dynamic_cast< ApplicationExpr >( alt.expr );
415	PointerType pointer = strict_dynamic_cast< PointerType >( appExpr->get_function()->get_result() );
416	FunctionType function = strict_dynamic_cast< FunctionType >( pointer->get_base() );
417
418	Cost convCost = Cost::zero;
419	std::list< DeclarationWithType* >& formals = function->get_parameters();
420	std::list< DeclarationWithType* >::iterator formal = formals.begin();
421	std::list< Expression* >& actuals = appExpr->get_args();
422
423	for ( std::list< Expression* >::iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) {
424	Type * actualType = (*actualExpr)->get_result();
425	PRINT(
426	std::cerr << "actual expression:" << std::endl;
427	(*actualExpr)->print( std::cerr, 8 );
428	std::cerr << "--- results are" << std::endl;
429	actualType->print( std::cerr, 8 );
430	)
431	if ( formal == formals.end() ) {
432	if ( function->get_isVarArgs() ) {
433	convCost.incUnsafe();
434	PRINT( std::cerr << "end of formals with varargs function: inc unsafe: " << convCost << std::endl; ; )
435	// convert reference-typed expressions to value-typed expressions
436	referenceToRvalueConversion( *actualExpr, convCost );
437	continue;
438	} else {
439	return Cost::infinity;
440	}
441	}
442	if ( DefaultArgExpr * def = dynamic_cast< DefaultArgExpr * >( *actualExpr ) ) {
443	// default arguments should be free - don't include conversion cost.
444	// Unwrap them here because they are not relevant to the rest of the system.
445	*actualExpr = def->expr;
446	++formal;
447	continue;
448	}
449	Type * formalType = (*formal)->get_type();
450	convCost += computeExpressionConversionCost( *actualExpr, formalType, indexer, alt.env );
451	++formal; // can't be in for-loop update because of the continue
452	}
453	if ( formal != formals.end() ) {
454	return Cost::infinity;
455	}
456
457	#if 1 // cost of assertions accounted for in function creation
458	for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) {
459	convCost += computeConversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env );
460	}
461	#endif
462
463	return convCost;
464	}
465
466	/// Adds type variables to the open variable set and marks their assertions
467	void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ) {
468	for ( Type::ForallList::const_iterator tyvar = type->forall.begin(); tyvar != type->forall.end(); ++tyvar ) {
469	unifiableVars[ (tyvar)->get_name() ] = TypeDecl::Data{ tyvar };
470	for ( std::list< DeclarationWithType* >::iterator assert = (tyvar)->assertions.begin(); assert != (tyvar)->assertions.end(); ++assert ) {
471	needAssertions[ *assert ].isUsed = true;
472	}
473	/// needAssertions.insert( needAssertions.end(), (tyvar)->get_assertions().begin(), (tyvar)->get_assertions().end() );
474	}
475	}
476
477	static const int recursionLimit = /10/ 4; ///< Limit to depth of recursion satisfaction
478
479	void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) {
480	for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) {
481	if ( i->second.isUsed ) {
482	indexer.addId( i->first );
483	}
484	}
485	}
486
487	template< typename ForwardIterator, typename OutputIterator >
488	void inferRecursive( ForwardIterator begin, ForwardIterator end, const Alternative &newAlt, OpenVarSet &openVars, const SymTab::Indexer &decls, const AssertionSet &newNeed, int level, const SymTab::Indexer &indexer, OutputIterator out ) {
489	if ( begin == end ) {
490	if ( newNeed.empty() ) {
491	PRINT(
492	std::cerr << "all assertions satisfied, output alternative: ";
493	newAlt.print( std::cerr );
494	std::cerr << std::endl;
495	);
496	*out++ = newAlt;
497	return;
498	} else if ( level >= recursionLimit ) {
499	SemanticError( newAlt.expr->location, "Too many recursive assertions" );
500	} else {
501	AssertionSet newerNeed;
502	PRINT(
503	std::cerr << "recursing with new set:" << std::endl;
504	printAssertionSet( newNeed, std::cerr, 8 );
505	)
506	inferRecursive( newNeed.begin(), newNeed.end(), newAlt, openVars, decls, newerNeed, level+1, indexer, out );
507	return;
508	}
509	}
510
511	ForwardIterator cur = begin++;
512	if ( ! cur->second.isUsed ) {
513	inferRecursive( begin, end, newAlt, openVars, decls, newNeed, level, indexer, out );
514	return; // xxx - should this continue? previously this wasn't here, and it looks like it should be
515	}
516	DeclarationWithType *curDecl = cur->first;
517
518	PRINT(
519	std::cerr << "inferRecursive: assertion is ";
520	curDecl->print( std::cerr );
521	std::cerr << std::endl;
522	)
523	std::list< SymTab::Indexer::IdData > candidates;
524	decls.lookupId( curDecl->get_name(), candidates );
525	/// if ( candidates.empty() ) { std::cerr << "no candidates!" << std::endl; }
526	for ( const auto & data : candidates ) {
527	DeclarationWithType * candidate = data.id;
528	PRINT(
529	std::cerr << "inferRecursive: candidate is ";
530	candidate->print( std::cerr );
531	std::cerr << std::endl;
532	)
533
534	AssertionSet newHave, newerNeed( newNeed );
535	TypeEnvironment newEnv( newAlt.env );
536	OpenVarSet newOpenVars( openVars );
537	Type *adjType = candidate->get_type()->clone();
538	adjustExprType( adjType, newEnv, indexer );
539	renameTyVars( adjType );
540	PRINT(
541	std::cerr << "unifying ";
542	curDecl->get_type()->print( std::cerr );
543	std::cerr << " with ";
544	adjType->print( std::cerr );
545	std::cerr << std::endl;
546	)
547	if ( unify( curDecl->get_type(), adjType, newEnv, newerNeed, newHave, newOpenVars, indexer ) ) {
548	PRINT(
549	std::cerr << "success!" << std::endl;
550	)
551	SymTab::Indexer newDecls( decls );
552	addToIndexer( newHave, newDecls );
553	Alternative newerAlt( newAlt );
554	newerAlt.env = newEnv;
555	assertf( candidate->get_uniqueId(), "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() );
556
557	// everything with an empty idChain was pulled in by the current assertion.
558	// add current assertion's idChain + current assertion's ID so that the correct inferParameters can be found.
559	for ( auto & a : newerNeed ) {
560	if ( a.second.idChain.empty() ) {
561	a.second.idChain = cur->second.idChain;
562	a.second.idChain.push_back( curDecl->get_uniqueId() );
563	}
564	}
565
566	Expression *varExpr = data.combine( newerAlt.cvtCost );
567	varExpr->set_result( adjType->clone() );
568	PRINT(
569	std::cerr << "satisfying assertion " << curDecl->get_uniqueId() << " ";
570	curDecl->print( std::cerr );
571	std::cerr << " with declaration " << candidate->get_uniqueId() << " ";
572	candidate->print( std::cerr );
573	std::cerr << std::endl;
574	)
575	// 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).
576	InferredParams * inferParameters = &newerAlt.expr->get_inferParams();
577	for ( UniqueId id : cur->second.idChain ) {
578	inferParameters = (*inferParameters)[ id ].inferParams.get();
579	}
580
581	(*inferParameters)[ curDecl->get_uniqueId() ] = ParamEntry( candidate->get_uniqueId(), adjType, curDecl->get_type(), varExpr );
582	inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, level, indexer, out );
583	}
584	}
585	}
586
587	#if 1
588	namespace {
589	/// Information required to defer resolution of an expression
590	struct AssertionPack {
591	SymTab::Indexer::IdData cdata; ///< Satisfying declaration
592	Type* adjType; ///< Satisfying type
593	TypeEnvironment env; ///< Post-unification environment
594	AssertionSet have; ///< Post-unification have-set
595	AssertionSet need; ///< Post-unification need-set
596	OpenVarSet openVars; ///< Post-unification open-var set
597
598	AssertionPack( const SymTab::Indexer::IdData& cdata, Type* adjType,
599	TypeEnvironment&& env, AssertionSet&& have, AssertionSet&& need,
600	OpenVarSet&& openVars )
601	: cdata(cdata), adjType(adjType), env(std::move(env)), have(std::move(have)),
602	need(std::move(need)), openVars(std::move(openVars)) {}
603
604	class iterator {
605	friend AssertionPack;
606	public:
607	const AssertionPack& pack;
608	private:
609	AssertionSet::iterator it;
610
611	iterator(const AssertionPack& p, AssertionSet::iterator i) : pack{p}, it{i} {}
612	public:
613	iterator& operator++ () { ++it; return *this; }
614	iterator operator++ (int) { iterator tmp = *this; ++it; return tmp; }
615	AssertionSet::value_type& operator* () { return *it; }
616	AssertionSet::value_type* operator-> () { return it.operator->(); }
617	bool operator== (const iterator& o) const { return this == &o && it == o.it; }
618	bool operator!= (const iterator& o) const { return !(*this == o); }
619	};
620
621	iterator begin() { return { *this, need.begin() }; }
622	iterator end() { return { *this, need.end() }; }
623	};
624
625	/// List of deferred assertion resolutions for the same type
626	using DeferList = std::vector<AssertionPack>;
627
628	/// Single deferred item
629	struct DeferElement {
630	const DeclarationWithType* curDecl;
631	const AssertionSetValue& assnInfo;
632	const AssertionPack& match;
633	};
634
635	/// Wrapper for the DeferList of a single assertion resolution
636	struct DeferItem {
637	DeclarationWithType* curDecl;
638	AssertionSetValue assnInfo;
639	DeferList matches;
640
641	DeferItem(DeclarationWithType* cd, const AssertionSetValue& ai, DeferList&& m )
642	: curDecl{cd}, assnInfo{ai}, matches(std::move(m)) {}
643
644	bool empty() const { return matches.empty(); }
645
646	DeferList::size_type size() const { return matches.size(); }
647
648	DeferElement operator[] ( unsigned i ) const {
649	return { curDecl, assnInfo, matches[i] };
650	}
651	};
652
653	/// Flag for state iteration
654	enum CopyFlag { IterateState };
655
656	/// Intermediate state for assertion resolution
657	struct AssertionResnState {
658	Alternative alt; ///< Alternative being built from
659	AssertionSet need; ///< Assertions to find
660	AssertionSet newNeed; ///< New assertions found from current assertions
661	OpenVarSet openVars; ///< Open variables in current context
662	std::vector<DeferItem> deferred; ///< Possible deferred assertion resolutions
663	SymTab::Indexer& indexer; ///< Name lookup
664
665	/// field-wise constructor (some fields defaulted)
666	AssertionResnState(Alternative&& alt, const AssertionSet& need,
667	const OpenVarSet& openVars, SymTab::Indexer& indexer )
668	: alt{std::move(alt)}, need{need}, newNeed{}, openVars{openVars}, deferred{},
669	indexer{indexer} {}
670
671	/// construct iterated state object from previous state
672	AssertionResnState(AssertionResnState&& o, CopyFlag)
673	: alt{std::move(o.alt)}, need{std::move(o.newNeed)}, newNeed{},
674	openVars{std::move(o.openVars)}, deferred{}, indexer{o.indexer} {}
675
676	/// copy resn state updated with specified data
677	AssertionResnState(const AssertionResnState& o, const AssertionSet& need,
678	const OpenVarSet& openVars, TypeEnvironment& env )
679	: alt{o.alt}, need{}, newNeed{o.newNeed}, openVars{openVars}, deferred{},
680	indexer{o.indexer} {
681	newNeed.insert( need.begin(), need.end() );
682	alt.env = env;
683	}
684	};
685
686	/// Binds a single assertion from a compatible AssertionPack, updating resolution state
687	/// as appropriate.
688	void bindAssertion( const DeclarationWithType* curDecl, const AssertionSetValue& assnInfo,
689	Alternative& alt, AssertionPack& match ) {
690
691	DeclarationWithType* candidate = match.cdata.id;
692	assertf( candidate->get_uniqueId(), "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() );
693	for ( auto& a : match.need ) {
694	if ( a.second.idChain.empty() ) {
695	a.second.idChain = assnInfo.idChain;
696	a.second.idChain.push_back( curDecl->get_uniqueId() );
697	}
698	}
699
700	Expression* varExpr = match.cdata.combine( alt.cvtCost );
701	varExpr->result = match.adjType;
702
703	// follow the current assertion's ID chain to find the correct set of inferred
704	// parameters to add the candidate o (i.e. the set of inferred parameters belonging
705	// to the entity which requested the assertion parameter)
706	InferredParams* inferParams = &alt.expr->inferParams;
707	for ( UniqueId id : assnInfo.idChain ) {
708	inferParams = (*inferParams)[ id ].inferParams.get();
709	}
710
711	(*inferParams)[ curDecl->get_uniqueId() ] = ParamEntry{
712	candidate->get_uniqueId(), match.adjType, curDecl->get_type(), varExpr };
713	}
714
715	/// Resolves a single assertion, returning false if no satisfying assertion, binding it
716	/// if there is exactly one satisfying assertion, or adding to the defer-list if there
717	/// is more than one
718	bool resolveAssertion( DeclarationWithType* curDecl, AssertionSetValue& assnInfo,
719	AssertionResnState& resn ) {
720	// skip unused assertions
721	if ( ! assnInfo.isUsed ) return true;
722
723	// lookup candidates for this assertion
724	std::list< SymTab::Indexer::IdData > candidates;
725	resn.indexer.lookupId( curDecl->name, candidates );
726
727	// find the ones that unify with the desired type
728	DeferList matches;
729	for ( const auto& cdata : candidates ) {
730	DeclarationWithType* candidate = cdata.id;
731
732	// build independent unification context for candidate
733	AssertionSet have, newNeed;
734	TypeEnvironment newEnv{ resn.alt.env };
735	OpenVarSet newOpenVars{ resn.openVars };
736	Type* adjType = candidate->get_type()->clone();
737	adjustExprType( adjType, newEnv, resn.indexer );
738	renameTyVars( adjType );
739
740	if ( unify( curDecl->get_type(), adjType, newEnv,
741	newNeed, have, newOpenVars, resn.indexer ) ) {
742	matches.emplace_back( cdata, adjType, std::move(newEnv), std::move(have),
743	std::move(newNeed), std::move(newOpenVars) );
744	}
745	}
746
747	// Break if no suitable assertion
748	if ( matches.empty() ) return false;
749
750	// Defer if too many suitable assertions
751	if ( matches.size() > 1 ) {
752	resn.deferred.emplace_back( curDecl, assnInfo, std::move(matches) );
753	return true;
754	}
755
756	// otherwise bind current match in ongoing scope
757	AssertionPack& match = matches.front();
758	addToIndexer( match.have, resn.indexer );
759	resn.newNeed.insert( match.need.begin(), match.need.end() );
760	resn.openVars = std::move(match.openVars);
761	resn.alt.env = std::move(match.env);
762
763	bindAssertion( curDecl, assnInfo, resn.alt, match );
764	return true;
765	}
766
767	/// Combo iterator that combines interpretations into an interpretation list, merging
768	/// their environments. Rejects an appended interpretation if the environments cannot
769	/// be merged.
770	class InterpretationEnvMerger {
771	/// Current list of merged interpretations
772	std::vector<DeferElement> crnt;
773	/// Stack of environments, to support backtracking
774	std::vector<TypeEnvironment> envs;
775	/// Open variables for environment combination
776	std::vector<OpenVarSet> varSets;
777	/// Indexer to use for environment merges
778	const SymTab::Indexer& indexer;
779	public:
780	/// The merged environment/open variables and the list of interpretations
781	struct OutType {
782	TypeEnvironment env;
783	OpenVarSet openVars;
784	std::vector<DeferElement> assns;
785
786	OutType( const TypeEnvironment& env, const OpenVarSet& openVars,
787	const std::vector<DeferElement>& assns )
788	: env(env), openVars(openVars), assns(assns) {}
789	};
790
791	InterpretationEnvMerger( const TypeEnvironment& env, const OpenVarSet& openVars,
792	const SymTab::Indexer& indexer ) : crnt{}, envs{}, varSets{}, indexer{indexer} {
793	envs.push_back( env );
794	varSets.push_back( openVars );
795	}
796
797	ComboResult append( DeferElement i ) {
798	TypeEnvironment env = envs.back();
799	OpenVarSet openVars = varSets.back();
800	mergeOpenVars( openVars, i.match.openVars );
801
802	if ( ! env.combine( i.match.env, openVars, indexer ) )
803	return ComboResult::REJECT_THIS;
804
805	crnt.push_back( i );
806	envs.push_back( env );
807	varSets.push_back( openVars );
808	return ComboResult::ACCEPT;
809	}
810
811	void backtrack() {
812	crnt.pop_back();
813	envs.pop_back();
814	varSets.pop_back();
815	}
816
817	OutType finalize() { return { envs.back(), varSets.back(), crnt }; }
818	};
819	}
820	#endif
821
822	template< typename OutputIterator >
823	void AlternativeFinder::Finder::inferParameters( const AssertionSet &need, AssertionSet &have, Alternative &&newAlt, OpenVarSet &openVars, OutputIterator out ) {
824	// PRINT(
825	// std::cerr << "inferParameters: assertions needed are" << std::endl;
826	// printAll( need, std::cerr, 8 );
827	// )
828	SymTab::Indexer decls( indexer );
829	// PRINT(
830	// std::cerr << "============= original indexer" << std::endl;
831	// indexer.print( std::cerr );
832	// std::cerr << "============= new indexer" << std::endl;
833	// decls.print( std::cerr );
834	// )
835	addToIndexer( have, decls );
836	#if 1
837	using ResnList = std::vector<AssertionResnState>;
838	ResnList resns{ AssertionResnState{ std::move(newAlt), need, openVars, decls } };
839	ResnList new_resns{};
840
841	// resolve assertions in breadth-first-order up to a limited number of levels deep
842	for ( int level = 0; level < recursionLimit; ++level ) {
843	// scan over all mutually-compatible resolutions
844	for ( auto& resn : resns ) {
845	// make initial pass at matching assertions
846	for ( auto& assn : resn.need ) {
847	if ( ! resolveAssertion( assn.first, assn.second, resn ) ) {
848	// fail early if any assertion fails to resolve
849	goto nextResn;
850	}
851	}
852
853	if ( ! resn.deferred.empty() ) {
854	// resolve deferred assertions by mutual compatibility
855
856	std::vector<InterpretationEnvMerger::OutType> compatible = filterCombos(
857	resn.deferred,
858	InterpretationEnvMerger{ resn.alt.env, resn.openVars, resn.indexer } );
859
860	for ( auto& compat : compatible ) {
861	AssertionResnState new_resn = resn;
862
863	// add compatible assertions to new resolution state
864	for ( DeferElement el : compat.assns ) {
865	AssertionPack match = el.match;
866	addToIndexer( match.have, new_resn.indexer );
867	resn.newNeed.insert( match.need.begin(), match.need.end() );
868
869	bindAssertion( el.curDecl, el.assnInfo, new_resn.alt, match );
870	}
871
872	// set mutual environment into resolution state
873	new_resn.alt.env = std::move(compat.env);
874	new_resn.openVars = std::move(compat.openVars);
875
876	// add successful match or push back next state
877	if ( new_resn.newNeed.empty() ) {
878	*out++ = new_resn.alt;
879	} else {
880	new_resns.emplace_back( std::move(new_resn), IterateState );
881	}
882	}
883	} else {
884	// add successful match or push back next state
885	if ( resn.newNeed.empty() ) {
886	*out++ = resn.alt;
887	} else {
888	new_resns.emplace_back( std::move(resn), IterateState );
889	}
890	}
891	nextResn:; }
892
893	// finish or reset for next round
894	if ( new_resns.empty() ) return;
895	resns.swap( new_resns );
896	new_resns.clear();
897	}
898	// if reaches here, exceeded recursion limit
899	SemanticError( newAlt.expr->location, "Too many recursive assertions" );
900
901	#else
902	AssertionSet newNeed;
903	PRINT(
904	std::cerr << "env is: " << std::endl;
905	newAlt.env.print( std::cerr, 0 );
906	std::cerr << std::endl;
907	)
908
909	inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, 0, indexer, out );
910	// PRINT(
911	// std::cerr << "declaration 14 is ";
912	// Declaration::declFromId
913	// *out++ = newAlt;
914	// )
915	#endif
916	}
917
918	/// Gets a default value from an initializer, nullptr if not present
919	ConstantExpr* getDefaultValue( Initializer* init ) {
920	if ( SingleInit* si = dynamic_cast<SingleInit*>( init ) ) {
921	if ( CastExpr* ce = dynamic_cast<CastExpr*>( si->value ) ) {
922	return dynamic_cast<ConstantExpr*>( ce->arg );
923	} else {
924	return dynamic_cast<ConstantExpr*>( si->value );
925	}
926	}
927	return nullptr;
928	}
929
930	/// State to iteratively build a match of parameter expressions to arguments
931	struct ArgPack {
932	std::size_t parent; ///< Index of parent pack
933	Expression* expr; ///< The argument stored here
934	Cost cost; ///< The cost of this argument
935	TypeEnvironment env; ///< Environment for this pack
936	AssertionSet need; ///< Assertions outstanding for this pack
937	AssertionSet have; ///< Assertions found for this pack
938	OpenVarSet openVars; ///< Open variables for this pack
939	unsigned nextArg; ///< Index of next argument in arguments list
940	unsigned tupleStart; ///< Number of tuples that start at this index
941	unsigned nextExpl; ///< Index of next exploded element
942	unsigned explAlt; ///< Index of alternative for nextExpl > 0
943
944	ArgPack()
945	: parent(0), expr(nullptr), cost(Cost::zero), env(), need(), have(), openVars(),
946	nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {}
947
948	ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have,
949	const OpenVarSet& openVars, Cost initCost = Cost::zero)
950	: parent(0), expr(nullptr), cost(initCost), env(env), need(need), have(have),
951	openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {}
952
953	ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need,
954	AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg,
955	unsigned tupleStart = 0, Cost cost = Cost::zero, unsigned nextExpl = 0,
956	unsigned explAlt = 0 )
957	: parent(parent), expr(expr), cost(cost), env(move(env)), need(move(need)),
958	have(move(have)), openVars(move(openVars)), nextArg(nextArg), tupleStart(tupleStart),
959	nextExpl(nextExpl), explAlt(explAlt) {}
960
961	ArgPack(const ArgPack& o, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have,
962	OpenVarSet&& openVars, unsigned nextArg, Cost added )
963	: parent(o.parent), expr(o.expr), cost(o.cost + added), env(move(env)),
964	need(move(need)), have(move(have)), openVars(move(openVars)), nextArg(nextArg),
965	tupleStart(o.tupleStart), nextExpl(0), explAlt(0) {}
966
967	/// true iff this pack is in the middle of an exploded argument
968	bool hasExpl() const { return nextExpl > 0; }
969
970	/// Gets the list of exploded alternatives for this pack
971	const ExplodedActual& getExpl( const ExplodedArgs& args ) const {
972	return args[nextArg-1][explAlt];
973	}
974
975	/// Ends a tuple expression, consolidating the appropriate actuals
976	void endTuple( const std::vector<ArgPack>& packs ) {
977	// add all expressions in tuple to list, summing cost
978	std::list<Expression*> exprs;
979	const ArgPack* pack = this;
980	if ( expr ) { exprs.push_front( expr ); }
981	while ( pack->tupleStart == 0 ) {
982	pack = &packs[pack->parent];
983	exprs.push_front( pack->expr );
984	cost += pack->cost;
985	}
986	// reset pack to appropriate tuple
987	expr = new TupleExpr{ exprs };
988	tupleStart = pack->tupleStart - 1;
989	parent = pack->parent;
990	}
991	};
992
993	/// Instantiates an argument to match a formal, returns false if no results left
994	bool instantiateArgument( Type* formalType, Initializer* initializer,
995	const ExplodedArgs& args, std::vector<ArgPack>& results, std::size_t& genStart,
996	const SymTab::Indexer& indexer, unsigned nTuples = 0 ) {
997	if ( TupleType * tupleType = dynamic_cast<TupleType*>( formalType ) ) {
998	// formalType is a TupleType - group actuals into a TupleExpr
999	++nTuples;
1000	for ( Type* type : *tupleType ) {
1001	// xxx - dropping initializer changes behaviour from previous, but seems correct
1002	// ^^^ need to handle the case where a tuple has a default argument
1003	if ( ! instantiateArgument(
1004	type, nullptr, args, results, genStart, indexer, nTuples ) )
1005	return false;
1006	nTuples = 0;
1007	}
1008	// re-consititute tuples for final generation
1009	for ( auto i = genStart; i < results.size(); ++i ) {
1010	results[i].endTuple( results );
1011	}
1012	return true;
1013	} else if ( TypeInstType * ttype = Tuples::isTtype( formalType ) ) {
1014	// formalType is a ttype, consumes all remaining arguments
1015	// xxx - mixing default arguments with variadic??
1016
1017	// completed tuples; will be spliced to end of results to finish
1018	std::vector<ArgPack> finalResults{};
1019
1020	// iterate until all results completed
1021	std::size_t genEnd;
1022	++nTuples;
1023	do {
1024	genEnd = results.size();
1025
1026	// add another argument to results
1027	for ( std::size_t i = genStart; i < genEnd; ++i ) {
1028	auto nextArg = results[i].nextArg;
1029
1030	// use next element of exploded tuple if present
1031	if ( results[i].hasExpl() ) {
1032	const ExplodedActual& expl = results[i].getExpl( args );
1033
1034	unsigned nextExpl = results[i].nextExpl + 1;
1035	if ( nextExpl == expl.exprs.size() ) {
1036	nextExpl = 0;
1037	}
1038
1039	results.emplace_back(
1040	i, expl.exprs[results[i].nextExpl], copy(results[i].env),
1041	copy(results[i].need), copy(results[i].have),
1042	copy(results[i].openVars), nextArg, nTuples, Cost::zero, nextExpl,
1043	results[i].explAlt );
1044
1045	continue;
1046	}
1047
1048	// finish result when out of arguments
1049	if ( nextArg >= args.size() ) {
1050	ArgPack newResult{
1051	results[i].env, results[i].need, results[i].have,
1052	results[i].openVars };
1053	newResult.nextArg = nextArg;
1054	Type* argType;
1055
1056	if ( nTuples > 0 \|\| ! results[i].expr ) {
1057	// first iteration or no expression to clone,
1058	// push empty tuple expression
1059	newResult.parent = i;
1060	std::list<Expression*> emptyList;
1061	newResult.expr = new TupleExpr{ emptyList };
1062	argType = newResult.expr->get_result();
1063	} else {
1064	// clone result to collect tuple
1065	newResult.parent = results[i].parent;
1066	newResult.cost = results[i].cost;
1067	newResult.tupleStart = results[i].tupleStart;
1068	newResult.expr = results[i].expr;
1069	argType = newResult.expr->get_result();
1070
1071	if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {
1072	// the case where a ttype value is passed directly is special,
1073	// e.g. for argument forwarding purposes
1074	// xxx - what if passing multiple arguments, last of which is
1075	// ttype?
1076	// xxx - what would happen if unify was changed so that unifying
1077	// tuple
1078	// types flattened both before unifying lists? then pass in
1079	// TupleType (ttype) below.
1080	--newResult.tupleStart;
1081	} else {
1082	// collapse leftover arguments into tuple
1083	newResult.endTuple( results );
1084	argType = newResult.expr->get_result();
1085	}
1086	}
1087
1088	// check unification for ttype before adding to final
1089	if ( unify( ttype, argType, newResult.env, newResult.need, newResult.have,
1090	newResult.openVars, indexer ) ) {
1091	finalResults.push_back( move(newResult) );
1092	}
1093
1094	continue;
1095	}
1096
1097	// add each possible next argument
1098	for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
1099	const ExplodedActual& expl = args[nextArg][j];
1100
1101	// fresh copies of parent parameters for this iteration
1102	TypeEnvironment env = results[i].env;
1103	OpenVarSet openVars = results[i].openVars;
1104
1105	env.addActual( expl.env, openVars );
1106
1107	// skip empty tuple arguments by (near-)cloning parent into next gen
1108	if ( expl.exprs.empty() ) {
1109	results.emplace_back(
1110	results[i], move(env), copy(results[i].need),
1111	copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
1112
1113	continue;
1114	}
1115
1116	// add new result
1117	results.emplace_back(
1118	i, expl.exprs.front(), move(env), copy(results[i].need),
1119	copy(results[i].have), move(openVars), nextArg + 1,
1120	nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
1121	}
1122	}
1123
1124	// reset for next round
1125	genStart = genEnd;
1126	nTuples = 0;
1127	} while ( genEnd != results.size() );
1128
1129	// splice final results onto results
1130	for ( std::size_t i = 0; i < finalResults.size(); ++i ) {
1131	results.push_back( move(finalResults[i]) );
1132	}
1133	return ! finalResults.empty();
1134	}
1135
1136	// iterate each current subresult
1137	std::size_t genEnd = results.size();
1138	for ( std::size_t i = genStart; i < genEnd; ++i ) {
1139	auto nextArg = results[i].nextArg;
1140
1141	// use remainder of exploded tuple if present
1142	if ( results[i].hasExpl() ) {
1143	const ExplodedActual& expl = results[i].getExpl( args );
1144	Expression* expr = expl.exprs[results[i].nextExpl];
1145
1146	TypeEnvironment env = results[i].env;
1147	AssertionSet need = results[i].need, have = results[i].have;
1148	OpenVarSet openVars = results[i].openVars;
1149
1150	Type* actualType = expr->get_result();
1151
1152	PRINT(
1153	std::cerr << "formal type is ";
1154	formalType->print( std::cerr );
1155	std::cerr << std::endl << "actual type is ";
1156	actualType->print( std::cerr );
1157	std::cerr << std::endl;
1158	)
1159
1160	if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
1161	unsigned nextExpl = results[i].nextExpl + 1;
1162	if ( nextExpl == expl.exprs.size() ) {
1163	nextExpl = 0;
1164	}
1165
1166	results.emplace_back(
1167	i, expr, move(env), move(need), move(have), move(openVars), nextArg,
1168	nTuples, Cost::zero, nextExpl, results[i].explAlt );
1169	}
1170
1171	continue;
1172	}
1173
1174	// use default initializers if out of arguments
1175	if ( nextArg >= args.size() ) {
1176	if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) {
1177	if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) {
1178	TypeEnvironment env = results[i].env;
1179	AssertionSet need = results[i].need, have = results[i].have;
1180	OpenVarSet openVars = results[i].openVars;
1181
1182	if ( unify( formalType, cnst->get_type(), env, need, have, openVars,
1183	indexer ) ) {
1184	results.emplace_back(
1185	i, new DefaultArgExpr( cnstExpr ), move(env), move(need), move(have),
1186	move(openVars), nextArg, nTuples );
1187	}
1188	}
1189	}
1190
1191	continue;
1192	}
1193
1194	// Check each possible next argument
1195	for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
1196	const ExplodedActual& expl = args[nextArg][j];
1197
1198	// fresh copies of parent parameters for this iteration
1199	TypeEnvironment env = results[i].env;
1200	AssertionSet need = results[i].need, have = results[i].have;
1201	OpenVarSet openVars = results[i].openVars;
1202
1203	env.addActual( expl.env, openVars );
1204
1205	// skip empty tuple arguments by (near-)cloning parent into next gen
1206	if ( expl.exprs.empty() ) {
1207	results.emplace_back(
1208	results[i], move(env), move(need), move(have), move(openVars),
1209	nextArg + 1, expl.cost );
1210
1211	continue;
1212	}
1213
1214	// consider only first exploded actual
1215	Expression* expr = expl.exprs.front();
1216	Type* actualType = expr->result->clone();
1217
1218	PRINT(
1219	std::cerr << "formal type is ";
1220	formalType->print( std::cerr );
1221	std::cerr << std::endl << "actual type is ";
1222	actualType->print( std::cerr );
1223	std::cerr << std::endl;
1224	)
1225
1226	// attempt to unify types
1227	if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
1228	// add new result
1229	results.emplace_back(
1230	i, expr, move(env), move(need), move(have), move(openVars), nextArg + 1,
1231	nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
1232	}
1233	}
1234	}
1235
1236	// reset for next parameter
1237	genStart = genEnd;
1238
1239	return genEnd != results.size();
1240	}
1241
1242	#if !1
1243	namespace {
1244
1245	struct CountSpecs : public WithVisitorRef<CountSpecs>, WithShortCircuiting {
1246
1247	void postvisit(PointerType*) {
1248	// mark specialization of base type
1249	if ( count >= 0 ) ++count;
1250	}
1251
1252	void postvisit(ArrayType*) {
1253	// mark specialization of base type
1254	if ( count >= 0 ) ++count;
1255	}
1256
1257	void postvisit(ReferenceType*) {
1258	// mark specialization of base type -- xxx maybe not?
1259	if ( count >= 0 ) ++count;
1260	}
1261
1262	private:
1263	// takes minimum non-negative count over parameter/return list
1264	void takeminover( int& mincount, std::list<DeclarationWithType*>& dwts ) {
1265	for ( DeclarationWithType* dwt : dwts ) {
1266	count = -1;
1267	maybeAccept( dwt->get_type(), *visitor );
1268	if ( count != -1 && count < mincount ) mincount = count;
1269	}
1270	}
1271
1272	public:
1273	void previsit(FunctionType*) {
1274	// override default child visiting behaviour
1275	visit_children = false;
1276	}
1277
1278	void postvisit(FunctionType* fty) {
1279	// take minimal set value of count over ->returnVals and ->parameters
1280	int mincount = std::numeric_limits<int>::max();
1281	takeminover( mincount, fty->parameters );
1282	takeminover( mincount, fty->returnVals );
1283	// add another level to mincount if set
1284	count = mincount < std::numeric_limits<int>::max() ? mincount + 1 : -1;
1285	}
1286
1287	private:
1288	// returns minimum non-negative count + 1 over type parameters (-1 if none such)
1289	int minover( std::list<Expression*>& parms ) {
1290	int mincount = std::numeric_limits<int>::max();
1291	for ( Expression* parm : parms ) {
1292	count = -1;
1293	maybeAccept( parm->get_result(), *visitor );
1294	if ( count != -1 && count < mincount ) mincount = count;
1295	}
1296	return mincount < std::numeric_limits<int>::max() ? mincount + 1 : -1;
1297	}
1298
1299	public:
1300	void previsit(StructInstType*) {
1301	// override default child behaviour
1302	visit_children = false;
1303	}
1304
1305	void postvisit(StructInstType* sity) {
1306	// look for polymorphic parameters
1307	count = minover( sity->parameters );
1308	}
1309
1310	void previsit(UnionInstType*) {
1311	// override default child behaviour
1312	visit_children = false;
1313	}
1314
1315	void postvisit(UnionInstType* uity) {
1316	// look for polymorphic parameters
1317	count = minover( uity->parameters );
1318	}
1319
1320	void postvisit(TypeInstType*) {
1321	// note polymorphic type (which may be specialized)
1322	// xxx - maybe account for open/closed type variables
1323	count = 0;
1324	}
1325
1326	void previsit(TupleType*) {
1327	// override default child behaviour
1328	visit_children = false;
1329	}
1330
1331	void postvisit(TupleType* tty) {
1332	// take minimum non-negative count
1333	int mincount = std::numeric_limits<int>::max();
1334	for ( Type* ty : tty->types ) {
1335	count = -1;
1336	maybeAccept( ty, *visitor );
1337	if ( count != -1 && count < mincount ) mincount = count;
1338	}
1339	// xxx - maybe don't increment, tuple flattening doesn't necessarily specialize
1340	count = mincount < std::numeric_limits<int>::max() ? mincount + 1: -1;
1341	}
1342
1343	int get_count() const { return count >= 0 ? count : 0; }
1344	private:
1345	int count = -1;
1346	};
1347
1348	/// Counts the specializations in the types in a function parameter or return list
1349	int countSpecs( std::list<DeclarationWithType*>& dwts ) {
1350	int k = 0;
1351	for ( DeclarationWithType* dwt : dwts ) {
1352	PassVisitor<CountSpecs> counter;
1353	maybeAccept( dwt->get_type(), *counter.pass.visitor );
1354	k += counter.pass.get_count();
1355	}
1356	return k;
1357	}
1358
1359	/// Calculates the inherent costs in a function declaration; varCost for the number of
1360	/// type variables and specCost for type assertions, as well as PolyType specializations
1361	/// in the parameter and return lists.
1362	Cost declCost( FunctionType* funcType ) {
1363	Cost k = Cost::zero;
1364
1365	// add cost of type variables
1366	k.incVar( funcType->forall.size() );
1367
1368	// subtract cost of type assertions
1369	for ( TypeDecl* td : funcType->forall ) {
1370	k.decSpec( td->assertions.size() );
1371	}
1372
1373	// count specialized polymorphic types in parameter/return lists
1374	k.decSpec( countSpecs( funcType->parameters ) );
1375	k.decSpec( countSpecs( funcType->returnVals ) );
1376
1377	return k;
1378	}
1379	}
1380	#endif
1381
1382	template<typename OutputIterator>
1383	void AlternativeFinder::Finder::validateFunctionAlternative( const Alternative &func,
1384	ArgPack& result, const std::vector<ArgPack>& results, OutputIterator out ) {
1385	ApplicationExpr *appExpr = new ApplicationExpr( func.expr );
1386	// sum cost and accumulate actuals
1387	std::list<Expression*>& args = appExpr->args;
1388	Cost cost = func.cost;
1389	const ArgPack* pack = &result;
1390	while ( pack->expr ) {
1391	args.push_front( pack->expr );
1392	cost += pack->cost;
1393	pack = &results[pack->parent];
1394	}
1395	// build and validate new alternative
1396	Alternative newAlt( appExpr, result.env, cost );
1397	PRINT(
1398	std::cerr << "instantiate function success: " << appExpr << std::endl;
1399	std::cerr << "need assertions:" << std::endl;
1400	printAssertionSet( result.need, std::cerr, 8 );
1401	)
1402	inferParameters( result.need, result.have, std::move(newAlt), result.openVars, out );
1403	}
1404
1405	template<typename OutputIterator>
1406	void AlternativeFinder::Finder::makeFunctionAlternatives( const Alternative &func,
1407	FunctionType *funcType, const ExplodedArgs &args, OutputIterator out ) {
1408	OpenVarSet funcOpenVars;
1409	AssertionSet funcNeed, funcHave;
1410	TypeEnvironment funcEnv( func.env );
1411	makeUnifiableVars( funcType, funcOpenVars, funcNeed );
1412	// add all type variables as open variables now so that those not used in the parameter
1413	// list are still considered open.
1414	funcEnv.add( funcType->forall );
1415
1416	if ( targetType && ! targetType->isVoid() && ! funcType->returnVals.empty() ) {
1417	// attempt to narrow based on expected target type
1418	Type * returnType = funcType->returnVals.front()->get_type();
1419	if ( ! unify( returnType, targetType, funcEnv, funcNeed, funcHave, funcOpenVars,
1420	indexer ) ) {
1421	// unification failed, don't pursue this function alternative
1422	return;
1423	}
1424	}
1425
1426	// calculate declaration cost of function (+vars-spec)
1427	#if !1
1428	Cost funcCost = declCost( funcType );
1429	#else
1430	Cost funcCost = Cost::zero;
1431	#endif
1432
1433	// iteratively build matches, one parameter at a time
1434	std::vector<ArgPack> results;
1435	results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars, funcCost } );
1436	std::size_t genStart = 0;
1437
1438	for ( DeclarationWithType* formal : funcType->parameters ) {
1439	ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal );
1440	if ( ! instantiateArgument(
1441	obj->type, obj->init, args, results, genStart, indexer ) )
1442	return;
1443	}
1444
1445	if ( funcType->get_isVarArgs() ) {
1446	// append any unused arguments to vararg pack
1447	std::size_t genEnd;
1448	do {
1449	genEnd = results.size();
1450
1451	// iterate results
1452	for ( std::size_t i = genStart; i < genEnd; ++i ) {
1453	auto nextArg = results[i].nextArg;
1454
1455	// use remainder of exploded tuple if present
1456	if ( results[i].hasExpl() ) {
1457	const ExplodedActual& expl = results[i].getExpl( args );
1458
1459	unsigned nextExpl = results[i].nextExpl + 1;
1460	if ( nextExpl == expl.exprs.size() ) {
1461	nextExpl = 0;
1462	}
1463
1464	results.emplace_back(
1465	i, expl.exprs[results[i].nextExpl], copy(results[i].env),
1466	copy(results[i].need), copy(results[i].have),
1467	copy(results[i].openVars), nextArg, 0, Cost::zero, nextExpl,
1468	results[i].explAlt );
1469
1470	continue;
1471	}
1472
1473	// finish result when out of arguments
1474	if ( nextArg >= args.size() ) {
1475	validateFunctionAlternative( func, results[i], results, out );
1476
1477	continue;
1478	}
1479
1480	// add each possible next argument
1481	for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
1482	const ExplodedActual& expl = args[nextArg][j];
1483
1484	// fresh copies of parent parameters for this iteration
1485	TypeEnvironment env = results[i].env;
1486	OpenVarSet openVars = results[i].openVars;
1487
1488	env.addActual( expl.env, openVars );
1489
1490	// skip empty tuple arguments by (near-)cloning parent into next gen
1491	if ( expl.exprs.empty() ) {
1492	results.emplace_back(
1493	results[i], move(env), copy(results[i].need),
1494	copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
1495
1496	continue;
1497	}
1498
1499	// add new result
1500	results.emplace_back(
1501	i, expl.exprs.front(), move(env), copy(results[i].need),
1502	copy(results[i].have), move(openVars), nextArg + 1, 0,
1503	expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
1504	}
1505	}
1506
1507	genStart = genEnd;
1508	} while ( genEnd != results.size() );
1509	} else {
1510	// filter out results that don't use all the arguments
1511	for ( std::size_t i = genStart; i < results.size(); ++i ) {
1512	ArgPack& result = results[i];
1513	if ( ! result.hasExpl() && result.nextArg >= args.size() ) {
1514	validateFunctionAlternative( func, result, results, out );
1515	}
1516	}
1517	}
1518	}
1519
1520	void AlternativeFinder::Finder::postvisit( UntypedExpr *untypedExpr ) {
1521	AlternativeFinder funcFinder( indexer, env );
1522	funcFinder.findWithAdjustment( untypedExpr->function );
1523	// if there are no function alternatives, then proceeding is a waste of time.
1524	// xxx - findWithAdjustment throws, so this check and others like it shouldn't be necessary.
1525	if ( funcFinder.alternatives.empty() ) return;
1526
1527	std::vector< AlternativeFinder > argAlternatives;
1528	altFinder.findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(),
1529	back_inserter( argAlternatives ) );
1530
1531	// take care of possible tuple assignments
1532	// if not tuple assignment, assignment is taken care of as a normal function call
1533	Tuples::handleTupleAssignment( altFinder, untypedExpr, argAlternatives );
1534
1535	// find function operators
1536	static auto *opExpr = new_static_root<NameExpr>( "?()" );
1537	AlternativeFinder funcOpFinder( indexer, env );
1538	// it's ok if there aren't any defined function ops
1539	funcOpFinder.maybeFind( opExpr );
1540	PRINT(
1541	std::cerr << "known function ops:" << std::endl;
1542	printAlts( funcOpFinder.alternatives, std::cerr, 1 );
1543	)
1544
1545	// pre-explode arguments
1546	ExplodedArgs argExpansions;
1547	argExpansions.reserve( argAlternatives.size() );
1548
1549	for ( const AlternativeFinder& arg : argAlternatives ) {
1550	argExpansions.emplace_back();
1551	auto& argE = argExpansions.back();
1552	// argE.reserve( arg.alternatives.size() );
1553
1554	for ( const Alternative& actual : arg ) {
1555	argE.emplace_back( actual, indexer );
1556	}
1557	}
1558
1559	AltList candidates;
1560	SemanticErrorException errors;
1561	for ( AltList::iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) {
1562	try {
1563	PRINT(
1564	std::cerr << "working on alternative: " << std::endl;
1565	func->print( std::cerr, 8 );
1566	)
1567	// check if the type is pointer to function
1568	if ( PointerType pointer = dynamic_cast< PointerType >( func->expr->get_result()->stripReferences() ) ) {
1569	if ( FunctionType function = dynamic_cast< FunctionType >( pointer->get_base() ) ) {
1570	Alternative newFunc( *func );
1571	referenceToRvalueConversion( newFunc.expr, newFunc.cost );
1572	makeFunctionAlternatives( newFunc, function, argExpansions,
1573	std::back_inserter( candidates ) );
1574	}
1575	} else if ( TypeInstType typeInst = dynamic_cast< TypeInstType >( func->expr->result->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer)
1576	if ( ClassRef eqvClass = func->env.lookup( typeInst->name ) ) {
1577	if ( FunctionType function = dynamic_cast< FunctionType >( eqvClass.get_bound().type ) ) {
1578	Alternative newFunc( *func );
1579	referenceToRvalueConversion( newFunc.expr, newFunc.cost );
1580	makeFunctionAlternatives( newFunc, function, argExpansions,
1581	std::back_inserter( candidates ) );
1582	} // if
1583	} // if
1584	}
1585	} catch ( SemanticErrorException &e ) {
1586	errors.append( e );
1587	}
1588	} // for
1589
1590	// try each function operator ?() with each function alternative
1591	if ( ! funcOpFinder.alternatives.empty() ) {
1592	// add exploded function alternatives to front of argument list
1593	std::vector<ExplodedActual> funcE;
1594	funcE.reserve( funcFinder.alternatives.size() );
1595	for ( const Alternative& actual : funcFinder ) {
1596	funcE.emplace_back( actual, indexer );
1597	}
1598	argExpansions.insert( argExpansions.begin(), move(funcE) );
1599
1600	for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin();
1601	funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
1602	try {
1603	// check if type is a pointer to function
1604	if ( PointerType* pointer = dynamic_cast<PointerType*>(
1605	funcOp->expr->get_result()->stripReferences() ) ) {
1606	if ( FunctionType* function =
1607	dynamic_cast<FunctionType*>( pointer->get_base() ) ) {
1608	Alternative newFunc( *funcOp );
1609	referenceToRvalueConversion( newFunc.expr, newFunc.cost );
1610	makeFunctionAlternatives( newFunc, function, argExpansions,
1611	std::back_inserter( candidates ) );
1612	}
1613	}
1614	} catch ( SemanticErrorException &e ) {
1615	errors.append( e );
1616	}
1617	}
1618	}
1619
1620	// Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
1621	if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }
1622
1623	// compute conversionsion costs
1624	for ( Alternative& withFunc : candidates ) {
1625	Cost cvtCost = computeApplicationConversionCost( withFunc, indexer );
1626
1627	PRINT(
1628	ApplicationExpr appExpr = strict_dynamic_cast< ApplicationExpr >( withFunc.expr );
1629	PointerType pointer = strict_dynamic_cast< PointerType >( appExpr->get_function()->get_result() );
1630	FunctionType function = strict_dynamic_cast< FunctionType >( pointer->get_base() );
1631	std::cerr << "Case +++++++++++++ " << appExpr->get_function() << std::endl;
1632	std::cerr << "formals are:" << std::endl;
1633	printAll( function->get_parameters(), std::cerr, 8 );
1634	std::cerr << "actuals are:" << std::endl;
1635	printAll( appExpr->get_args(), std::cerr, 8 );
1636	std::cerr << "bindings are:" << std::endl;
1637	withFunc.env.print( std::cerr, 8 );
1638	std::cerr << "cost of conversion is:" << cvtCost << std::endl;
1639	)
1640	if ( cvtCost != Cost::infinity ) {
1641	withFunc.cvtCost = cvtCost;
1642	alternatives.push_back( withFunc );
1643	} // if
1644	} // for
1645
1646	candidates = move(alternatives);
1647
1648	// use a new list so that alternatives are not examined by addAnonConversions twice.
1649	AltList winners;
1650	findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) );
1651
1652	// function may return struct or union value, in which case we need to add alternatives
1653	// for implicitconversions to each of the anonymous members, must happen after findMinCost
1654	// since anon conversions are never the cheapest expression
1655	for ( const Alternative & alt : winners ) {
1656	addAnonConversions( alt );
1657	}
1658	spliceBegin( alternatives, winners );
1659
1660	if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
1661	// xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
1662	// target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
1663	// forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
1664	// const char * x = "hello world";
1665	// unsigned char ch = x[0];
1666	// Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
1667	// with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
1668	// fix this issue in a more robust way.
1669	targetType = nullptr;
1670	postvisit( untypedExpr );
1671	}
1672	}
1673
1674	bool isLvalue( Expression *expr ) {
1675	// xxx - recurse into tuples?
1676	return expr->result && ( expr->get_result()->get_lvalue() \|\| dynamic_cast< ReferenceType * >( expr->get_result() ) );
1677	}
1678
1679	void AlternativeFinder::Finder::postvisit( AddressExpr *addressExpr ) {
1680	AlternativeFinder finder( indexer, env );
1681	finder.find( addressExpr->get_arg() );
1682	for ( Alternative& alt : finder.alternatives ) {
1683	if ( isLvalue( alt.expr ) ) {
1684	alternatives.push_back(
1685	Alternative{ new AddressExpr( alt.expr ), alt.env, alt.cost } );
1686	} // if
1687	} // for
1688	}
1689
1690	void AlternativeFinder::Finder::postvisit( LabelAddressExpr * expr ) {
1691	alternatives.push_back( Alternative{ expr, env, Cost::zero } );
1692	}
1693
1694	Expression * restructureCast( Expression * argExpr, Type * toType, bool isGenerated ) {
1695	if ( argExpr->get_result()->size() > 1 && ! toType->isVoid() && ! dynamic_cast<ReferenceType *>( toType ) ) {
1696	// Argument expression is a tuple and the target type is not void and not a reference type.
1697	// Cast each member of the tuple to its corresponding target type, producing the tuple of those
1698	// cast expressions. If there are more components of the tuple than components in the target type,
1699	// then excess components do not come out in the result expression (but UniqueExprs ensure that
1700	// side effects will still be done).
1701	if ( Tuples::maybeImpureIgnoreUnique( argExpr ) ) {
1702	// expressions which may contain side effects require a single unique instance of the expression.
1703	argExpr = new UniqueExpr( argExpr );
1704	}
1705	std::list< Expression * > componentExprs;
1706	for ( unsigned int i = 0; i < toType->size(); i++ ) {
1707	// cast each component
1708	TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
1709	componentExprs.push_back( restructureCast( idx, toType->getComponent( i ), isGenerated ) );
1710	}
1711	assert( componentExprs.size() > 0 );
1712	// produce the tuple of casts
1713	return new TupleExpr( componentExprs );
1714	} else {
1715	// handle normally
1716	CastExpr * ret = new CastExpr( argExpr, toType->clone() );
1717	ret->isGenerated = isGenerated;
1718	return ret;
1719	}
1720	}
1721
1722	void AlternativeFinder::Finder::postvisit( CastExpr *castExpr ) {
1723	Type *& toType = castExpr->get_result();
1724	assert( toType );
1725	toType = resolveTypeof( toType, indexer );
1726	SymTab::validateType( toType, &indexer );
1727	adjustExprType( toType, env, indexer );
1728
1729	AlternativeFinder finder( indexer, env );
1730	finder.targetType = toType;
1731	finder.findWithAdjustment( castExpr->arg );
1732
1733	AltList candidates;
1734	for ( Alternative & alt : finder.alternatives ) {
1735	AssertionSet needAssertions, haveAssertions;
1736	OpenVarSet openVars;
1737
1738	alt.env.extractOpenVars( openVars );
1739
1740	// It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a
1741	// cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results
1742	// that are cast directly. The candidate is invalid if it has fewer results than there are types to cast
1743	// to.
1744	int discardedValues = alt.expr->result->size() - castExpr->result->size();
1745	if ( discardedValues < 0 ) continue;
1746	// xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1747	// allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1748	// unification run for side-effects
1749	unify( castExpr->result, alt.expr->result, alt.env, needAssertions,
1750	haveAssertions, openVars, indexer );
1751	Cost thisCost = castCost( alt.expr->result, castExpr->result, indexer,
1752	alt.env );
1753	PRINT(
1754	std::cerr << "working on cast with result: " << castExpr->result << std::endl;
1755	std::cerr << "and expr type: " << alt.expr->result << std::endl;
1756	std::cerr << "env: " << alt.env << std::endl;
1757	)
1758	if ( thisCost != Cost::infinity ) {
1759	PRINT(
1760	std::cerr << "has finite cost." << std::endl;
1761	)
1762	// count one safe conversion for each value that is thrown away
1763	thisCost.incSafe( discardedValues );
1764	Alternative newAlt( restructureCast( alt.expr->clone(), toType, castExpr->isGenerated ), alt.env,
1765	alt.cost, thisCost );
1766	inferParameters( needAssertions, haveAssertions, std::move(newAlt), openVars,
1767	back_inserter( candidates ) );
1768	} // if
1769	} // for
1770
1771	// findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1772	// cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice
1773	// selects first based on argument cost, then on conversion cost.
1774	AltList minArgCost;
1775	findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1776	findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1777	}
1778
1779	void AlternativeFinder::Finder::postvisit( VirtualCastExpr * castExpr ) {
1780	assertf( castExpr->get_result(), "Implicate virtual cast targets not yet supported." );
1781	AlternativeFinder finder( indexer, env );
1782	// don't prune here, since it's guaranteed all alternatives will have the same type
1783	finder.findWithoutPrune( castExpr->get_arg() );
1784	for ( Alternative & alt : finder.alternatives ) {
1785	alternatives.push_back( Alternative(
1786	new VirtualCastExpr( alt.expr, castExpr->get_result()->clone() ),
1787	alt.env, alt.cost ) );
1788	}
1789	}
1790
1791	namespace {
1792	/// Gets name from untyped member expression (member must be NameExpr)
1793	const std::string& get_member_name( UntypedMemberExpr *memberExpr ) {
1794	NameExpr * nameExpr = dynamic_cast< NameExpr * >( memberExpr->get_member() );
1795	assert( nameExpr );
1796	return nameExpr->get_name();
1797	}
1798	}
1799
1800	void AlternativeFinder::Finder::postvisit( UntypedMemberExpr *memberExpr ) {
1801	AlternativeFinder funcFinder( indexer, env );
1802	funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
1803	for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
1804	// 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
1805	Cost cost = agg->cost;
1806	Expression * aggrExpr = agg->expr->clone();
1807	referenceToRvalueConversion( aggrExpr, cost );
1808
1809	// find member of the given type
1810	if ( StructInstType structInst = dynamic_cast< StructInstType >( aggrExpr->get_result() ) ) {
1811	addAggMembers( structInst, aggrExpr, cost, agg->env, get_member_name(memberExpr) );
1812	} else if ( UnionInstType unionInst = dynamic_cast< UnionInstType >( aggrExpr->get_result() ) ) {
1813	addAggMembers( unionInst, aggrExpr, cost, agg->env, get_member_name(memberExpr) );
1814	} else if ( TupleType * tupleType = dynamic_cast< TupleType * >( aggrExpr->get_result() ) ) {
1815	addTupleMembers( tupleType, aggrExpr, cost, agg->env, memberExpr->get_member() );
1816	} // if
1817	} // for
1818	}
1819
1820	void AlternativeFinder::Finder::postvisit( MemberExpr *memberExpr ) {
1821	alternatives.push_back( Alternative( memberExpr, env, Cost::zero ) );
1822	}
1823
1824	void AlternativeFinder::Finder::postvisit( NameExpr *nameExpr ) {
1825	std::list< SymTab::Indexer::IdData > declList;
1826	indexer.lookupId( nameExpr->name, declList );
1827	PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; )
1828	for ( auto & data : declList ) {
1829	Cost cost = Cost::zero;
1830	Expression * newExpr = data.combine( cost );
1831
1832	// addAnonAlternatives uses vector::push_back, which invalidates references to existing elements, so
1833	// can't construct in place and use vector::back
1834	Alternative newAlt( newExpr, env, Cost::zero, cost );
1835	PRINT(
1836	std::cerr << "decl is ";
1837	data.id->print( std::cerr );
1838	std::cerr << std::endl;
1839	std::cerr << "newExpr is ";
1840	newExpr->print( std::cerr );
1841	std::cerr << std::endl;
1842	)
1843	renameTypes( newAlt.expr );
1844	addAnonConversions( newAlt ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
1845	alternatives.push_back( std::move(newAlt) );
1846	} // for
1847	}
1848
1849	void AlternativeFinder::Finder::postvisit( VariableExpr *variableExpr ) {
1850	// not sufficient to clone here, because variable's type may have changed
1851	// since the VariableExpr was originally created.
1852	alternatives.push_back( Alternative( new VariableExpr( variableExpr->var ), env, Cost::zero ) );
1853	}
1854
1855	void AlternativeFinder::Finder::postvisit( ConstantExpr *constantExpr ) {
1856	alternatives.push_back( Alternative( constantExpr, env, Cost::zero ) );
1857	}
1858
1859	void AlternativeFinder::Finder::postvisit( SizeofExpr *sizeofExpr ) {
1860	if ( sizeofExpr->get_isType() ) {
1861	Type * newType = sizeofExpr->get_type()->clone();
1862	alternatives.push_back( Alternative( new SizeofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1863	} else {
1864	// find all alternatives for the argument to sizeof
1865	AlternativeFinder finder( indexer, env );
1866	finder.find( sizeofExpr->get_expr() );
1867	// find the lowest cost alternative among the alternatives, otherwise ambiguous
1868	AltList winners;
1869	findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1870	if ( winners.size() != 1 ) {
1871	SemanticError( sizeofExpr->get_expr(), "Ambiguous expression in sizeof operand: " );
1872	} // if
1873	// return the lowest cost alternative for the argument
1874	Alternative &choice = winners.front();
1875	referenceToRvalueConversion( choice.expr, choice.cost );
1876	alternatives.push_back( Alternative( new SizeofExpr( choice.expr ), choice.env, Cost::zero ) );
1877	} // if
1878	}
1879
1880	void AlternativeFinder::Finder::postvisit( AlignofExpr *alignofExpr ) {
1881	if ( alignofExpr->get_isType() ) {
1882	Type * newType = alignofExpr->get_type()->clone();
1883	alternatives.push_back( Alternative( new AlignofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1884	} else {
1885	// find all alternatives for the argument to sizeof
1886	AlternativeFinder finder( indexer, env );
1887	finder.find( alignofExpr->get_expr() );
1888	// find the lowest cost alternative among the alternatives, otherwise ambiguous
1889	AltList winners;
1890	findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1891	if ( winners.size() != 1 ) {
1892	SemanticError( alignofExpr->get_expr(), "Ambiguous expression in alignof operand: " );
1893	} // if
1894	// return the lowest cost alternative for the argument
1895	Alternative &choice = winners.front();
1896	referenceToRvalueConversion( choice.expr, choice.cost );
1897	alternatives.push_back( Alternative( new AlignofExpr( choice.expr ), choice.env, Cost::zero ) );
1898	} // if
1899	}
1900
1901	template< typename StructOrUnionType >
1902	void AlternativeFinder::Finder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
1903	std::list< Declaration* > members;
1904	aggInst->lookup( name, members );
1905	for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
1906	if ( DeclarationWithType dwt = dynamic_cast< DeclarationWithType >( *i ) ) {
1907	alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
1908	renameTypes( alternatives.back().expr );
1909	} else {
1910	assert( false );
1911	}
1912	}
1913	}
1914
1915	void AlternativeFinder::Finder::postvisit( UntypedOffsetofExpr *offsetofExpr ) {
1916	AlternativeFinder funcFinder( indexer, env );
1917	// xxx - resolveTypeof?
1918	if ( StructInstType structInst = dynamic_cast< StructInstType >( offsetofExpr->get_type() ) ) {
1919	addOffsetof( structInst, offsetofExpr->member );
1920	} else if ( UnionInstType unionInst = dynamic_cast< UnionInstType >( offsetofExpr->get_type() ) ) {
1921	addOffsetof( unionInst, offsetofExpr->member );
1922	}
1923	}
1924
1925	void AlternativeFinder::Finder::postvisit( OffsetofExpr *offsetofExpr ) {
1926	alternatives.push_back( Alternative( offsetofExpr, env, Cost::zero ) );
1927	}
1928
1929	void AlternativeFinder::Finder::postvisit( OffsetPackExpr *offsetPackExpr ) {
1930	alternatives.push_back( Alternative( offsetPackExpr, env, Cost::zero ) );
1931	}
1932
1933	namespace {
1934	void resolveAttr( SymTab::Indexer::IdData data, FunctionType function, Type argType, const TypeEnvironment &env, AlternativeFinder & finder ) {
1935	// assume no polymorphism
1936	// assume no implicit conversions
1937	assert( function->get_parameters().size() == 1 );
1938	PRINT(
1939	std::cerr << "resolvAttr: funcDecl is ";
1940	data.id->print( std::cerr );
1941	std::cerr << " argType is ";
1942	argType->print( std::cerr );
1943	std::cerr << std::endl;
1944	)
1945	const SymTab::Indexer & indexer = finder.get_indexer();
1946	AltList & alternatives = finder.get_alternatives();
1947	if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
1948	Cost cost = Cost::zero;
1949	Expression * newExpr = data.combine( cost );
1950	alternatives.push_back( Alternative( new AttrExpr( newExpr, argType->clone() ), env, Cost::zero, cost ) );
1951	for ( DeclarationWithType * retVal : function->returnVals ) {
1952	alternatives.back().expr->result = retVal->get_type()->clone();
1953	} // for
1954	} // if
1955	}
1956	}
1957
1958	void AlternativeFinder::Finder::postvisit( AttrExpr *attrExpr ) {
1959	// assume no 'pointer-to-attribute'
1960	NameExpr nameExpr = dynamic_cast< NameExpr >( attrExpr->get_attr() );
1961	assert( nameExpr );
1962	std::list< SymTab::Indexer::IdData > attrList;
1963	indexer.lookupId( nameExpr->get_name(), attrList );
1964	if ( attrExpr->get_isType() \|\| attrExpr->get_expr() ) {
1965	for ( auto & data : attrList ) {
1966	DeclarationWithType * id = data.id;
1967	// check if the type is function
1968	if ( FunctionType function = dynamic_cast< FunctionType >( id->get_type() ) ) {
1969	// assume exactly one parameter
1970	if ( function->get_parameters().size() == 1 ) {
1971	if ( attrExpr->get_isType() ) {
1972	resolveAttr( data, function, attrExpr->get_type(), env, altFinder);
1973	} else {
1974	AlternativeFinder finder( indexer, env );
1975	finder.find( attrExpr->get_expr() );
1976	for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
1977	if ( choice->expr->get_result()->size() == 1 ) {
1978	resolveAttr(data, function, choice->expr->get_result(), choice->env, altFinder );
1979	} // fi
1980	} // for
1981	} // if
1982	} // if
1983	} // if
1984	} // for
1985	} else {
1986	for ( auto & data : attrList ) {
1987	Cost cost = Cost::zero;
1988	Expression * newExpr = data.combine( cost );
1989	alternatives.push_back( Alternative( newExpr, env, Cost::zero, cost ) );
1990	renameTypes( alternatives.back().expr );
1991	} // for
1992	} // if
1993	}
1994
1995	void AlternativeFinder::Finder::postvisit( LogicalExpr *logicalExpr ) {
1996	AlternativeFinder firstFinder( indexer, env );
1997	firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
1998	if ( firstFinder.alternatives.empty() ) return;
1999	AlternativeFinder secondFinder( indexer, env );
2000	secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
2001	if ( secondFinder.alternatives.empty() ) return;
2002	for ( const Alternative & first : firstFinder.alternatives ) {
2003	for ( const Alternative & second : secondFinder.alternatives ) {
2004	TypeEnvironment compositeEnv;
2005	compositeEnv.simpleCombine( first.env );
2006	compositeEnv.simpleCombine( second.env );
2007
2008	LogicalExpr *newExpr = new LogicalExpr( first.expr, second.expr, logicalExpr->get_isAnd() );
2009	alternatives.push_back( Alternative( newExpr, compositeEnv, first.cost + second.cost ) );
2010	}
2011	}
2012	}
2013
2014	void AlternativeFinder::Finder::postvisit( ConditionalExpr *conditionalExpr ) {
2015	// find alternatives for condition
2016	AlternativeFinder firstFinder( indexer, env );
2017	firstFinder.findWithAdjustment( conditionalExpr->arg1 );
2018	if ( firstFinder.alternatives.empty() ) return;
2019	// find alternatives for true expression
2020	AlternativeFinder secondFinder( indexer, env );
2021	secondFinder.findWithAdjustment( conditionalExpr->arg2 );
2022	if ( secondFinder.alternatives.empty() ) return;
2023	// find alterantives for false expression
2024	AlternativeFinder thirdFinder( indexer, env );
2025	thirdFinder.findWithAdjustment( conditionalExpr->arg3 );
2026	if ( thirdFinder.alternatives.empty() ) return;
2027	for ( const Alternative & first : firstFinder.alternatives ) {
2028	for ( const Alternative & second : secondFinder.alternatives ) {
2029	for ( const Alternative & third : thirdFinder.alternatives ) {
2030	TypeEnvironment compositeEnv;
2031	compositeEnv.simpleCombine( first.env );
2032	compositeEnv.simpleCombine( second.env );
2033	compositeEnv.simpleCombine( third.env );
2034
2035	// unify true and false types, then infer parameters to produce new alternatives
2036	OpenVarSet openVars;
2037	AssertionSet needAssertions, haveAssertions;
2038	Alternative newAlt( 0, compositeEnv, first.cost + second.cost + third.cost );
2039	Type* commonType = nullptr;
2040	if ( unify( second.expr->result, third.expr->result, newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
2041	ConditionalExpr *newExpr = new ConditionalExpr( first.expr, second.expr, third.expr );
2042	newExpr->result = commonType ? commonType : second.expr->result->clone();
2043	// convert both options to the conditional result type
2044	newAlt.cost += computeExpressionConversionCost( newExpr->arg2, newExpr->result, indexer, newAlt.env );
2045	newAlt.cost += computeExpressionConversionCost( newExpr->arg3, newExpr->result, indexer, newAlt.env );
2046	newAlt.expr = newExpr;
2047	inferParameters( needAssertions, haveAssertions, std::move(newAlt), openVars, back_inserter( alternatives ) );
2048	} // if
2049	} // for
2050	} // for
2051	} // for
2052	}
2053
2054	void AlternativeFinder::Finder::postvisit( CommaExpr *commaExpr ) {
2055	TypeEnvironment newEnv( env );
2056	Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
2057	AlternativeFinder secondFinder( indexer, newEnv );
2058	secondFinder.findWithAdjustment( commaExpr->get_arg2() );
2059	for ( const Alternative & alt : secondFinder.alternatives ) {
2060	alternatives.push_back( Alternative( new CommaExpr( newFirstArg, alt.expr ), alt.env, alt.cost ) );
2061	} // for
2062	}
2063
2064	void AlternativeFinder::Finder::postvisit( RangeExpr * rangeExpr ) {
2065	// resolve low and high, accept alternatives whose low and high types unify
2066	AlternativeFinder firstFinder( indexer, env );
2067	firstFinder.findWithAdjustment( rangeExpr->low );
2068	if ( firstFinder.alternatives.empty() ) return;
2069	AlternativeFinder secondFinder( indexer, env );
2070	secondFinder.findWithAdjustment( rangeExpr->high );
2071	if ( secondFinder.alternatives.empty() ) return;
2072	for ( const Alternative & first : firstFinder.alternatives ) {
2073	for ( const Alternative & second : secondFinder.alternatives ) {
2074	TypeEnvironment compositeEnv;
2075	compositeEnv.simpleCombine( first.env );
2076	compositeEnv.simpleCombine( second.env );
2077	OpenVarSet openVars;
2078	AssertionSet needAssertions, haveAssertions;
2079	Alternative newAlt( 0, compositeEnv, first.cost + second.cost );
2080	Type* commonType = nullptr;
2081	if ( unify( first.expr->result, second.expr->result, newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
2082	RangeExpr * newExpr = new RangeExpr( first.expr, second.expr );
2083	newExpr->result = commonType ? commonType : first.expr->result->clone();
2084	newAlt.expr = newExpr;
2085	inferParameters( needAssertions, haveAssertions, std::move(newAlt), openVars, back_inserter( alternatives ) );
2086	} // if
2087	} // for
2088	} // for
2089	}
2090
2091	void AlternativeFinder::Finder::postvisit( UntypedTupleExpr *tupleExpr ) {
2092	std::vector< AlternativeFinder > subExprAlternatives;
2093	altFinder.findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(),
2094	back_inserter( subExprAlternatives ) );
2095	std::vector< AltList > possibilities;
2096	combos( subExprAlternatives.begin(), subExprAlternatives.end(),
2097	back_inserter( possibilities ) );
2098	for ( const AltList& alts : possibilities ) {
2099	std::list< Expression * > exprs;
2100	makeExprList( alts, exprs );
2101
2102	TypeEnvironment compositeEnv;
2103	simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
2104	alternatives.push_back(
2105	Alternative{ new TupleExpr( exprs ), compositeEnv, sumCost( alts ) } );
2106	} // for
2107	}
2108
2109	void AlternativeFinder::Finder::postvisit( TupleExpr *tupleExpr ) {
2110	alternatives.push_back( Alternative( tupleExpr, env, Cost::zero ) );
2111	}
2112
2113	void AlternativeFinder::Finder::postvisit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
2114	alternatives.push_back( Alternative( impCpCtorExpr, env, Cost::zero ) );
2115	}
2116
2117	void AlternativeFinder::Finder::postvisit( ConstructorExpr * ctorExpr ) {
2118	AlternativeFinder finder( indexer, env );
2119	// don't prune here, since it's guaranteed all alternatives will have the same type
2120	// (giving the alternatives different types is half of the point of ConstructorExpr nodes)
2121	finder.findWithoutPrune( ctorExpr->get_callExpr() );
2122	for ( Alternative & alt : finder.alternatives ) {
2123	alternatives.push_back( Alternative( new ConstructorExpr( alt.expr ), alt.env, alt.cost ) );
2124	}
2125	}
2126
2127	void AlternativeFinder::Finder::postvisit( TupleIndexExpr *tupleExpr ) {
2128	alternatives.push_back( Alternative( tupleExpr, env, Cost::zero ) );
2129	}
2130
2131	void AlternativeFinder::Finder::postvisit( TupleAssignExpr *tupleAssignExpr ) {
2132	alternatives.push_back( Alternative( tupleAssignExpr, env, Cost::zero ) );
2133	}
2134
2135	void AlternativeFinder::Finder::postvisit( UniqueExpr *unqExpr ) {
2136	AlternativeFinder finder( indexer, env );
2137	finder.findWithAdjustment( unqExpr->get_expr() );
2138	for ( Alternative & alt : finder.alternatives ) {
2139	// ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
2140	UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr, unqExpr->get_id() );
2141	alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
2142	}
2143	}
2144
2145	void AlternativeFinder::Finder::postvisit( StmtExpr *stmtExpr ) {
2146	StmtExpr * newStmtExpr = stmtExpr->clone();
2147	ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
2148	// xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
2149	alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
2150	}
2151
2152	void AlternativeFinder::Finder::postvisit( UntypedInitExpr *initExpr ) {
2153	// handle each option like a cast
2154	AltList candidates;
2155	PRINT(
2156	std::cerr << "untyped init expr: " << initExpr << std::endl;
2157	)
2158	// O(N^2) checks of d-types with e-types
2159	for ( InitAlternative & initAlt : initExpr->get_initAlts() ) {
2160	Type * toType = resolveTypeof( initAlt.type->clone(), indexer );
2161	SymTab::validateType( toType, &indexer );
2162	adjustExprType( toType, env, indexer );
2163	// Ideally the call to findWithAdjustment could be moved out of the loop, but unfortunately it currently has to occur inside or else
2164	// polymorphic return types are not properly bound to the initialization type, since return type variables are only open for the duration of resolving
2165	// the UntypedExpr. This is only actually an issue in initialization contexts that allow more than one possible initialization type, but it is still suboptimal.
2166	AlternativeFinder finder( indexer, env );
2167	finder.targetType = toType;
2168	finder.findWithAdjustment( initExpr->expr );
2169	for ( Alternative & alt : finder.get_alternatives() ) {
2170	TypeEnvironment newEnv( alt.env );
2171	AssertionSet needAssertions, haveAssertions;
2172	OpenVarSet openVars; // find things in env that don't have a "representative type" and claim those are open vars?
2173	PRINT(
2174	std::cerr << " @ " << toType << " " << initAlt.designation << std::endl;
2175	)
2176	// It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a
2177	// cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results
2178	// that are cast directly. The candidate is invalid if it has fewer results than there are types to cast
2179	// to.
2180	int discardedValues = alt.expr->result->size() - toType->size();
2181	if ( discardedValues < 0 ) continue;
2182	// xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
2183	// allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
2184	// unification run for side-effects
2185	unify( toType, alt.expr->result, newEnv, needAssertions, haveAssertions, openVars, indexer ); // xxx - do some inspecting on this line... why isn't result bound to initAlt.type??
2186
2187	Cost thisCost = castCost( alt.expr->result, toType, indexer, newEnv );
2188	if ( thisCost != Cost::infinity ) {
2189	// count one safe conversion for each value that is thrown away
2190	thisCost.incSafe( discardedValues );
2191	Alternative newAlt( new InitExpr( restructureCast( alt.expr, toType, true ), initAlt.designation ), newEnv, alt.cost, thisCost );
2192	inferParameters( needAssertions, haveAssertions, std::move(newAlt), openVars, back_inserter( candidates ) );
2193	}
2194	}
2195	}
2196
2197	// findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
2198	// cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice
2199	// selects first based on argument cost, then on conversion cost.
2200	AltList minArgCost;
2201	findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
2202	findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
2203	}
2204
2205	void AlternativeFinder::Finder::postvisit( InitExpr * ) {
2206	assertf( false, "AlternativeFinder should never see a resolved InitExpr." );
2207	}
2208
2209	void AlternativeFinder::Finder::postvisit( DeletedExpr * ) {
2210	assertf( false, "AlternativeFinder should never see a DeletedExpr." );
2211	}
2212
2213	void AlternativeFinder::Finder::postvisit( GenericExpr * ) {
2214	assertf( false, "_Generic is not yet supported." );
2215	}
2216	} // namespace ResolvExpr
2217
2218	// Local Variables: //
2219	// tab-width: 4 //
2220	// mode: c++ //
2221	// compile-command: "make install" //
2222	// End: //

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

Download in other formats: