Context Navigation

source: src/ResolvExpr/CandidateFinder.cpp@ 16ba4a6f

Visit:

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast-unique-expr pthread-emulation qualifiedEnum

Last change on this file since 16ba4a6f was 954c954, checked in by Fangren Yu <f37yu@…>, 5 years ago
Move function argument and return variable declarations from FunctionType to FunctionDecl
Property mode set to `100644`
File size: 63.1 KB

Rev	Line
[99d4584]	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	// CandidateFinder.cpp --
	8	//
	9	// Author : Aaron B. Moss
	10	// Created On : Wed Jun 5 14:30:00 2019
[cf32116]	11	// Last Modified By : Andrew Beach
	12	// Last Modified On : Tue Oct 1 14:55:00 2019
	13	// Update Count : 2
[99d4584]	14	//
	15
	16	#include "CandidateFinder.hpp"
	17
[432ce7a]	18	#include <deque>
[4b7cce6]	19	#include <iterator> // for back_inserter
[396037d]	20	#include <sstream>
[d57e349]	21	#include <string>
	22	#include <unordered_map>
[432ce7a]	23	#include <vector>
[396037d]	24
	25	#include "Candidate.hpp"
	26	#include "CompilationState.h"
[d57e349]	27	#include "Cost.h"
[432ce7a]	28	#include "ExplodedArg.hpp"
[898ae07]	29	#include "RenameVars.h" // for renameTyVars
[d57e349]	30	#include "Resolver.h"
[c8e4d2f8]	31	#include "ResolveTypeof.h"
[396037d]	32	#include "SatisfyAssertions.hpp"
[9d5089e]	33	#include "typeops.h" // for adjustExprType, conversionCost, polyCost, specCost
[4b7cce6]	34	#include "Unify.h"
[99d4584]	35	#include "AST/Expr.hpp"
[396037d]	36	#include "AST/Node.hpp"
	37	#include "AST/Pass.hpp"
[d57e349]	38	#include "AST/Print.hpp"
[4b7cce6]	39	#include "AST/SymbolTable.hpp"
[432ce7a]	40	#include "AST/Type.hpp"
[c1ed2ee]	41	#include "Common/utility.h" // for move, copy
[d57e349]	42	#include "SymTab/Mangler.h"
[c8e4d2f8]	43	#include "SymTab/Validate.h" // for validateType
[432ce7a]	44	#include "Tuples/Tuples.h" // for handleTupleAssignment
[396037d]	45
	46	#define PRINT( text ) if ( resolvep ) { text }
[99d4584]	47
	48	namespace ResolvExpr {
	49
[9d5089e]	50	const ast::Expr * referenceToRvalueConversion( const ast::Expr * expr, Cost & cost ) {
	51	if ( expr->result.as< ast::ReferenceType >() ) {
	52	// cast away reference from expr
	53	cost.incReference();
[b8524ca]	54	return new ast::CastExpr{ expr, expr->result->stripReferences() };
[9d5089e]	55	}
[2890212]	56
[9d5089e]	57	return expr;
	58	}
	59
	60	/// Unique identifier for matching expression resolutions to their requesting expression
	61	UniqueId globalResnSlot = 0;
[396037d]	62
[2890212]	63	Cost computeConversionCost(
[cf32116]	64	const ast::Type * argType, const ast::Type * paramType, bool argIsLvalue,
	65	const ast::SymbolTable & symtab, const ast::TypeEnvironment & env
[b69233ac]	66	) {
	67	PRINT(
	68	std::cerr << std::endl << "converting ";
	69	ast::print( std::cerr, argType, 2 );
	70	std::cerr << std::endl << " to ";
	71	ast::print( std::cerr, paramType, 2 );
	72	std::cerr << std::endl << "environment is: ";
	73	ast::print( std::cerr, env, 2 );
	74	std::cerr << std::endl;
	75	)
[cf32116]	76	Cost convCost = conversionCost( argType, paramType, argIsLvalue, symtab, env );
[b69233ac]	77	PRINT(
	78	std::cerr << std::endl << "cost is " << convCost << std::endl;
	79	)
	80	if ( convCost == Cost::infinity ) return convCost;
	81	convCost.incPoly( polyCost( paramType, symtab, env ) + polyCost( argType, symtab, env ) );
	82	PRINT(
	83	std::cerr << "cost with polycost is " << convCost << std::endl;
	84	)
	85	return convCost;
	86	}
	87
[9d5089e]	88	namespace {
[432ce7a]	89	/// First index is which argument, second is which alternative, third is which exploded element
	90	using ExplodedArgs_new = std::deque< std::vector< ExplodedArg > >;
	91
	92	/// Returns a list of alternatives with the minimum cost in the given list
	93	CandidateList findMinCost( const CandidateList & candidates ) {
	94	CandidateList out;
	95	Cost minCost = Cost::infinity;
	96	for ( const CandidateRef & r : candidates ) {
	97	if ( r->cost < minCost ) {
	98	minCost = r->cost;
	99	out.clear();
	100	out.emplace_back( r );
	101	} else if ( r->cost == minCost ) {
	102	out.emplace_back( r );
	103	}
	104	}
	105	return out;
	106	}
	107
[9d5089e]	108	/// Computes conversion cost for a given expression to a given type
[2890212]	109	const ast::Expr * computeExpressionConversionCost(
	110	const ast::Expr * arg, const ast::Type * paramType, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env, Cost & outCost
[9d5089e]	111	) {
[cf32116]	112	Cost convCost = computeConversionCost(
	113	arg->result, paramType, arg->get_lvalue(), symtab, env );
[9d5089e]	114	outCost += convCost;
	115
[2890212]	116	// If there is a non-zero conversion cost, ignoring poly cost, then the expression requires
	117	// conversion. Ignore poly cost for now, since this requires resolution of the cast to
[9d5089e]	118	// infer parameters and this does not currently work for the reason stated below
	119	Cost tmpCost = convCost;
	120	tmpCost.incPoly( -tmpCost.get_polyCost() );
	121	if ( tmpCost != Cost::zero ) {
	122	ast::ptr< ast::Type > newType = paramType;
	123	env.apply( newType );
[b8524ca]	124	return new ast::CastExpr{ arg, newType };
[9d5089e]	125
[2890212]	126	// xxx - should be able to resolve this cast, but at the moment pointers are not
	127	// castable to zero_t, but are implicitly convertible. This is clearly inconsistent,
[9d5089e]	128	// once this is fixed it should be possible to resolve the cast.
[2890212]	129	// xxx - this isn't working, it appears because type1 (parameter) is seen as widenable,
	130	// but it shouldn't be because this makes the conversion from DT* to DT* since
[9d5089e]	131	// commontype(zero_t, DT) is DT, rather than nothing
	132
	133	// CandidateFinder finder{ symtab, env };
	134	// finder.find( arg, ResolvMode::withAdjustment() );
[2890212]	135	// assertf( finder.candidates.size() > 0,
[9d5089e]	136	// "Somehow castable expression failed to find alternatives." );
[2890212]	137	// assertf( finder.candidates.size() == 1,
[9d5089e]	138	// "Somehow got multiple alternatives for known cast expression." );
	139	// return finder.candidates.front()->expr;
	140	}
	141
	142	return arg;
	143	}
	144
[432ce7a]	145	/// Computes conversion cost for a given candidate
[2890212]	146	Cost computeApplicationConversionCost(
	147	CandidateRef cand, const ast::SymbolTable & symtab
[432ce7a]	148	) {
[9d5089e]	149	auto appExpr = cand->expr.strict_as< ast::ApplicationExpr >();
	150	auto pointer = appExpr->func->result.strict_as< ast::PointerType >();
	151	auto function = pointer->base.strict_as< ast::FunctionType >();
	152
	153	Cost convCost = Cost::zero;
	154	const auto & params = function->params;
	155	auto param = params.begin();
	156	auto & args = appExpr->args;
	157
	158	for ( unsigned i = 0; i < args.size(); ++i ) {
	159	const ast::Type * argType = args[i]->result;
	160	PRINT(
	161	std::cerr << "arg expression:" << std::endl;
	162	ast::print( std::cerr, args[i], 2 );
	163	std::cerr << "--- results are" << std::endl;
	164	ast::print( std::cerr, argType, 2 );
	165	)
	166
	167	if ( param == params.end() ) {
	168	if ( function->isVarArgs ) {
	169	convCost.incUnsafe();
[2890212]	170	PRINT( std::cerr << "end of params with varargs function: inc unsafe: "
[9d5089e]	171	<< convCost << std::endl; ; )
	172	// convert reference-typed expressions into value-typed expressions
[2890212]	173	cand->expr = ast::mutate_field_index(
	174	appExpr, &ast::ApplicationExpr::args, i,
[9d5089e]	175	referenceToRvalueConversion( args[i], convCost ) );
	176	continue;
	177	} else return Cost::infinity;
	178	}
	179
	180	if ( auto def = args[i].as< ast::DefaultArgExpr >() ) {
	181	// Default arguments should be free - don't include conversion cost.
	182	// Unwrap them here because they are not relevant to the rest of the system
[2890212]	183	cand->expr = ast::mutate_field_index(
[9d5089e]	184	appExpr, &ast::ApplicationExpr::args, i, def->expr );
	185	++param;
	186	continue;
	187	}
	188
	189	// mark conversion cost and also specialization cost of param type
[954c954]	190	// const ast::Type * paramType = (*param)->get_type();
[2890212]	191	cand->expr = ast::mutate_field_index(
	192	appExpr, &ast::ApplicationExpr::args, i,
	193	computeExpressionConversionCost(
[954c954]	194	args[i], *param, symtab, cand->env, convCost ) );
	195	convCost.decSpec( specCost( *param ) );
[9d5089e]	196	++param; // can't be in for-loop update because of the continue
	197	}
	198
	199	if ( param != params.end() ) return Cost::infinity;
	200
[2890212]	201	// specialization cost of return types can't be accounted for directly, it disables
[9d5089e]	202	// otherwise-identical calls, like this example based on auto-newline in the I/O lib:
	203	//
	204	// forall(otype OS) {
	205	// void ?\|?(OS&, int); // with newline
	206	// OS& ?\|?(OS&, int); // no newline, always chosen due to more specialization
	207	// }
	208
	209	// mark type variable and specialization cost of forall clause
	210	convCost.incVar( function->forall.size() );
	211	for ( const ast::TypeDecl * td : function->forall ) {
	212	convCost.decSpec( td->assertions.size() );
	213	}
	214
	215	return convCost;
	216	}
	217
[2890212]	218	void makeUnifiableVars(
	219	const ast::ParameterizedType * type, ast::OpenVarSet & unifiableVars,
	220	ast::AssertionSet & need
[9d5089e]	221	) {
	222	for ( const ast::TypeDecl * tyvar : type->forall ) {
	223	unifiableVars[ tyvar->name ] = ast::TypeDecl::Data{ tyvar };
	224	for ( const ast::DeclWithType * assn : tyvar->assertions ) {
	225	need[ assn ].isUsed = true;
	226	}
	227	}
	228	}
	229
	230	/// Gets a default value from an initializer, nullptr if not present
	231	const ast::ConstantExpr * getDefaultValue( const ast::Init * init ) {
	232	if ( auto si = dynamic_cast< const ast::SingleInit * >( init ) ) {
	233	if ( auto ce = si->value.as< ast::CastExpr >() ) {
	234	return ce->arg.as< ast::ConstantExpr >();
	235	} else {
	236	return si->value.as< ast::ConstantExpr >();
	237	}
	238	}
	239	return nullptr;
	240	}
	241
	242	/// State to iteratively build a match of parameter expressions to arguments
	243	struct ArgPack {
	244	std::size_t parent; ///< Index of parent pack
	245	ast::ptr< ast::Expr > expr; ///< The argument stored here
	246	Cost cost; ///< The cost of this argument
	247	ast::TypeEnvironment env; ///< Environment for this pack
	248	ast::AssertionSet need; ///< Assertions outstanding for this pack
	249	ast::AssertionSet have; ///< Assertions found for this pack
	250	ast::OpenVarSet open; ///< Open variables for this pack
	251	unsigned nextArg; ///< Index of next argument in arguments list
	252	unsigned tupleStart; ///< Number of tuples that start at this index
	253	unsigned nextExpl; ///< Index of next exploded element
	254	unsigned explAlt; ///< Index of alternative for nextExpl > 0
	255
	256	ArgPack()
[2890212]	257	: parent( 0 ), expr(), cost( Cost::zero ), env(), need(), have(), open(), nextArg( 0 ),
[9d5089e]	258	tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {}
[2890212]	259
	260	ArgPack(
	261	const ast::TypeEnvironment & env, const ast::AssertionSet & need,
[9d5089e]	262	const ast::AssertionSet & have, const ast::OpenVarSet & open )
[2890212]	263	: parent( 0 ), expr(), cost( Cost::zero ), env( env ), need( need ), have( have ),
[9d5089e]	264	open( open ), nextArg( 0 ), tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {}
[2890212]	265
[9d5089e]	266	ArgPack(
[2890212]	267	std::size_t parent, const ast::Expr * expr, ast::TypeEnvironment && env,
	268	ast::AssertionSet && need, ast::AssertionSet && have, ast::OpenVarSet && open,
	269	unsigned nextArg, unsigned tupleStart = 0, Cost cost = Cost::zero,
[9d5089e]	270	unsigned nextExpl = 0, unsigned explAlt = 0 )
	271	: parent(parent), expr( expr ), cost( cost ), env( move( env ) ), need( move( need ) ),
	272	have( move( have ) ), open( move( open ) ), nextArg( nextArg ), tupleStart( tupleStart ),
	273	nextExpl( nextExpl ), explAlt( explAlt ) {}
[2890212]	274
[9d5089e]	275	ArgPack(
[2890212]	276	const ArgPack & o, ast::TypeEnvironment && env, ast::AssertionSet && need,
[9d5089e]	277	ast::AssertionSet && have, ast::OpenVarSet && open, unsigned nextArg, Cost added )
[2890212]	278	: parent( o.parent ), expr( o.expr ), cost( o.cost + added ), env( move( env ) ),
	279	need( move( need ) ), have( move( have ) ), open( move( open ) ), nextArg( nextArg ),
[9d5089e]	280	tupleStart( o.tupleStart ), nextExpl( 0 ), explAlt( 0 ) {}
[2890212]	281
[9d5089e]	282	/// true if this pack is in the middle of an exploded argument
	283	bool hasExpl() const { return nextExpl > 0; }
	284
	285	/// Gets the list of exploded candidates for this pack
	286	const ExplodedArg & getExpl( const ExplodedArgs_new & args ) const {
	287	return args[ nextArg-1 ][ explAlt ];
	288	}
[2890212]	289
[9d5089e]	290	/// Ends a tuple expression, consolidating the appropriate args
	291	void endTuple( const std::vector< ArgPack > & packs ) {
	292	// add all expressions in tuple to list, summing cost
	293	std::deque< const ast::Expr * > exprs;
	294	const ArgPack * pack = this;
	295	if ( expr ) { exprs.emplace_front( expr ); }
	296	while ( pack->tupleStart == 0 ) {
	297	pack = &packs[pack->parent];
	298	exprs.emplace_front( pack->expr );
	299	cost += pack->cost;
	300	}
	301	// reset pack to appropriate tuple
	302	std::vector< ast::ptr< ast::Expr > > exprv( exprs.begin(), exprs.end() );
	303	expr = new ast::TupleExpr{ expr->location, move( exprv ) };
	304	tupleStart = pack->tupleStart - 1;
	305	parent = pack->parent;
	306	}
	307	};
	308
	309	/// Instantiates an argument to match a parameter, returns false if no matching results left
[2890212]	310	bool instantiateArgument(
	311	const ast::Type * paramType, const ast::Init * init, const ExplodedArgs_new & args,
	312	std::vector< ArgPack > & results, std::size_t & genStart, const ast::SymbolTable & symtab,
	313	unsigned nTuples = 0
[9d5089e]	314	) {
	315	if ( auto tupleType = dynamic_cast< const ast::TupleType * >( paramType ) ) {
	316	// paramType is a TupleType -- group args into a TupleExpr
	317	++nTuples;
	318	for ( const ast::Type * type : *tupleType ) {
	319	// xxx - dropping initializer changes behaviour from previous, but seems correct
	320	// ^^^ need to handle the case where a tuple has a default argument
[2890212]	321	if ( ! instantiateArgument(
[9d5089e]	322	type, nullptr, args, results, genStart, symtab, nTuples ) ) return false;
	323	nTuples = 0;
	324	}
	325	// re-constitute tuples for final generation
	326	for ( auto i = genStart; i < results.size(); ++i ) {
	327	results[i].endTuple( results );
	328	}
	329	return true;
	330	} else if ( const ast::TypeInstType * ttype = Tuples::isTtype( paramType ) ) {
	331	// paramType is a ttype, consumes all remaining arguments
[2890212]	332
[9d5089e]	333	// completed tuples; will be spliced to end of results to finish
	334	std::vector< ArgPack > finalResults{};
	335
	336	// iterate until all results completed
	337	std::size_t genEnd;
	338	++nTuples;
	339	do {
	340	genEnd = results.size();
	341
	342	// add another argument to results
	343	for ( std::size_t i = genStart; i < genEnd; ++i ) {
	344	unsigned nextArg = results[i].nextArg;
[2890212]	345
[9d5089e]	346	// use next element of exploded tuple if present
	347	if ( results[i].hasExpl() ) {
	348	const ExplodedArg & expl = results[i].getExpl( args );
	349
	350	unsigned nextExpl = results[i].nextExpl + 1;
	351	if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
	352
	353	results.emplace_back(
	354	i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ),
[2890212]	355	copy( results[i].need ), copy( results[i].have ),
[9d5089e]	356	copy( results[i].open ), nextArg, nTuples, Cost::zero, nextExpl,
	357	results[i].explAlt );
	358
	359	continue;
	360	}
	361
	362	// finish result when out of arguments
	363	if ( nextArg >= args.size() ) {
	364	ArgPack newResult{
	365	results[i].env, results[i].need, results[i].have, results[i].open };
	366	newResult.nextArg = nextArg;
	367	const ast::Type * argType = nullptr;
	368
	369	if ( nTuples > 0 \|\| ! results[i].expr ) {
	370	// first iteration or no expression to clone,
	371	// push empty tuple expression
	372	newResult.parent = i;
[417117e]	373	newResult.expr = new ast::TupleExpr{ CodeLocation{}, {} };
[9d5089e]	374	argType = newResult.expr->result;
	375	} else {
	376	// clone result to collect tuple
	377	newResult.parent = results[i].parent;
	378	newResult.cost = results[i].cost;
	379	newResult.tupleStart = results[i].tupleStart;
	380	newResult.expr = results[i].expr;
	381	argType = newResult.expr->result;
	382
	383	if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {
	384	// the case where a ttype value is passed directly is special,
	385	// e.g. for argument forwarding purposes
	386	// xxx - what if passing multiple arguments, last of which is
	387	// ttype?
	388	// xxx - what would happen if unify was changed so that unifying
	389	// tuple
	390	// types flattened both before unifying lists? then pass in
	391	// TupleType (ttype) below.
	392	--newResult.tupleStart;
	393	} else {
	394	// collapse leftover arguments into tuple
	395	newResult.endTuple( results );
	396	argType = newResult.expr->result;
	397	}
	398	}
	399
	400	// check unification for ttype before adding to final
[2890212]	401	if (
	402	unify(
[9d5089e]	403	ttype, argType, newResult.env, newResult.need, newResult.have,
[2890212]	404	newResult.open, symtab )
[9d5089e]	405	) {
	406	finalResults.emplace_back( move( newResult ) );
	407	}
	408
	409	continue;
	410	}
	411
	412	// add each possible next argument
	413	for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
	414	const ExplodedArg & expl = args[nextArg][j];
	415
	416	// fresh copies of parent parameters for this iteration
	417	ast::TypeEnvironment env = results[i].env;
	418	ast::OpenVarSet open = results[i].open;
	419
	420	env.addActual( expl.env, open );
	421
	422	// skip empty tuple arguments by (nearly) cloning parent into next gen
	423	if ( expl.exprs.empty() ) {
	424	results.emplace_back(
[2890212]	425	results[i], move( env ), copy( results[i].need ),
[9d5089e]	426	copy( results[i].have ), move( open ), nextArg + 1, expl.cost );
[2890212]	427
[9d5089e]	428	continue;
	429	}
	430
	431	// add new result
	432	results.emplace_back(
[2890212]	433	i, expl.exprs.front(), move( env ), copy( results[i].need ),
	434	copy( results[i].have ), move( open ), nextArg + 1, nTuples,
[9d5089e]	435	expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
	436	}
	437	}
	438
	439	// reset for next round
	440	genStart = genEnd;
	441	nTuples = 0;
	442	} while ( genEnd != results.size() );
	443
	444	// splice final results onto results
	445	for ( std::size_t i = 0; i < finalResults.size(); ++i ) {
	446	results.emplace_back( move( finalResults[i] ) );
	447	}
	448	return ! finalResults.empty();
	449	}
	450
	451	// iterate each current subresult
	452	std::size_t genEnd = results.size();
	453	for ( std::size_t i = genStart; i < genEnd; ++i ) {
	454	unsigned nextArg = results[i].nextArg;
	455
	456	// use remainder of exploded tuple if present
	457	if ( results[i].hasExpl() ) {
	458	const ExplodedArg & expl = results[i].getExpl( args );
	459	const ast::Expr * expr = expl.exprs[ results[i].nextExpl ];
	460
	461	ast::TypeEnvironment env = results[i].env;
	462	ast::AssertionSet need = results[i].need, have = results[i].have;
	463	ast::OpenVarSet open = results[i].open;
	464
	465	const ast::Type * argType = expr->result;
	466
	467	PRINT(
	468	std::cerr << "param type is ";
	469	ast::print( std::cerr, paramType );
	470	std::cerr << std::endl << "arg type is ";
	471	ast::print( std::cerr, argType );
	472	std::cerr << std::endl;
	473	)
	474
	475	if ( unify( paramType, argType, env, need, have, open, symtab ) ) {
	476	unsigned nextExpl = results[i].nextExpl + 1;
	477	if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
	478
	479	results.emplace_back(
[2890212]	480	i, expr, move( env ), move( need ), move( have ), move( open ), nextArg,
[9d5089e]	481	nTuples, Cost::zero, nextExpl, results[i].explAlt );
	482	}
	483
	484	continue;
	485	}
	486
	487	// use default initializers if out of arguments
	488	if ( nextArg >= args.size() ) {
	489	if ( const ast::ConstantExpr * cnst = getDefaultValue( init ) ) {
	490	ast::TypeEnvironment env = results[i].env;
	491	ast::AssertionSet need = results[i].need, have = results[i].have;
	492	ast::OpenVarSet open = results[i].open;
	493
	494	if ( unify( paramType, cnst->result, env, need, have, open, symtab ) ) {
	495	results.emplace_back(
[2890212]	496	i, new ast::DefaultArgExpr{ cnst->location, cnst }, move( env ),
[9d5089e]	497	move( need ), move( have ), move( open ), nextArg, nTuples );
	498	}
	499	}
	500
	501	continue;
	502	}
	503
	504	// Check each possible next argument
	505	for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
	506	const ExplodedArg & expl = args[nextArg][j];
	507
	508	// fresh copies of parent parameters for this iteration
	509	ast::TypeEnvironment env = results[i].env;
	510	ast::AssertionSet need = results[i].need, have = results[i].have;
	511	ast::OpenVarSet open = results[i].open;
	512
	513	env.addActual( expl.env, open );
	514
	515	// skip empty tuple arguments by (nearly) cloning parent into next gen
	516	if ( expl.exprs.empty() ) {
	517	results.emplace_back(
[2890212]	518	results[i], move( env ), move( need ), move( have ), move( open ),
[9d5089e]	519	nextArg + 1, expl.cost );
[2890212]	520
[9d5089e]	521	continue;
	522	}
	523
	524	// consider only first exploded arg
	525	const ast::Expr * expr = expl.exprs.front();
	526	const ast::Type * argType = expr->result;
	527
	528	PRINT(
	529	std::cerr << "param type is ";
	530	ast::print( std::cerr, paramType );
	531	std::cerr << std::endl << "arg type is ";
	532	ast::print( std::cerr, argType );
	533	std::cerr << std::endl;
	534	)
	535
	536	// attempt to unify types
	537	if ( unify( paramType, argType, env, need, have, open, symtab ) ) {
	538	// add new result
	539	results.emplace_back(
[2890212]	540	i, expr, move( env ), move( need ), move( have ), move( open ),
[9d5089e]	541	nextArg + 1, nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
	542	}
	543	}
	544	}
	545
	546	// reset for next parameter
	547	genStart = genEnd;
	548
[e0e9a0b]	549	return genEnd != results.size(); // were any new results added?
[432ce7a]	550	}
	551
[c8e4d2f8]	552	/// Generate a cast expression from `arg` to `toType`
[2890212]	553	const ast::Expr * restructureCast(
[17a0ede2]	554	ast::ptr< ast::Expr > & arg, const ast::Type * toType, ast::GeneratedFlag isGenerated = ast::GeneratedCast
[898ae07]	555	) {
[2890212]	556	if (
	557	arg->result->size() > 1
	558	&& ! toType->isVoid()
	559	&& ! dynamic_cast< const ast::ReferenceType * >( toType )
[898ae07]	560	) {
[2890212]	561	// Argument is a tuple and the target type is neither void nor a reference. Cast each
	562	// member of the tuple to its corresponding target type, producing the tuple of those
	563	// cast expressions. If there are more components of the tuple than components in the
	564	// target type, then excess components do not come out in the result expression (but
[898ae07]	565	// UniqueExpr ensures that the side effects will still be produced)
	566	if ( Tuples::maybeImpureIgnoreUnique( arg ) ) {
[2890212]	567	// expressions which may contain side effects require a single unique instance of
[898ae07]	568	// the expression
	569	arg = new ast::UniqueExpr{ arg->location, arg };
	570	}
	571	std::vector< ast::ptr< ast::Expr > > components;
	572	for ( unsigned i = 0; i < toType->size(); ++i ) {
	573	// cast each component
	574	ast::ptr< ast::Expr > idx = new ast::TupleIndexExpr{ arg->location, arg, i };
[2890212]	575	components.emplace_back(
[898ae07]	576	restructureCast( idx, toType->getComponent( i ), isGenerated ) );
	577	}
	578	return new ast::TupleExpr{ arg->location, move( components ) };
	579	} else {
	580	// handle normally
	581	return new ast::CastExpr{ arg->location, arg, toType, isGenerated };
	582	}
	583	}
	584
	585	/// Gets the name from an untyped member expression (must be NameExpr)
	586	const std::string & getMemberName( const ast::UntypedMemberExpr * memberExpr ) {
	587	if ( memberExpr->member.as< ast::ConstantExpr >() ) {
	588	SemanticError( memberExpr, "Indexed access to struct fields unsupported: " );
	589	}
	590
	591	return memberExpr->member.strict_as< ast::NameExpr >()->name;
[c8e4d2f8]	592	}
	593
[396037d]	594	/// Actually visits expressions to find their candidate interpretations
[9ea38de]	595	class Finder final : public ast::WithShortCircuiting {
[396037d]	596	const ast::SymbolTable & symtab;
[9ea38de]	597	public:
[c15085d]	598	static size_t traceId;
[9ea38de]	599	CandidateFinder & selfFinder;
[396037d]	600	CandidateList & candidates;
	601	const ast::TypeEnvironment & tenv;
	602	ast::ptr< ast::Type > & targetType;
	603
[71d6bd8]	604	enum Errors {
	605	NotFound,
	606	NoMatch,
	607	ArgsToFew,
	608	ArgsToMany,
	609	RetsToFew,
	610	RetsToMany,
	611	NoReason
	612	};
	613
	614	struct {
	615	Errors code = NotFound;
	616	} reason;
	617
[396037d]	618	Finder( CandidateFinder & f )
[2890212]	619	: symtab( f.localSyms ), selfFinder( f ), candidates( f.candidates ), tenv( f.env ),
[396037d]	620	targetType( f.targetType ) {}
[2890212]	621
[4b7cce6]	622	void previsit( const ast::Node * ) { visit_children = false; }
	623
	624	/// Convenience to add candidate to list
	625	template<typename... Args>
	626	void addCandidate( Args &&... args ) {
	627	candidates.emplace_back( new Candidate{ std::forward<Args>( args )... } );
[71d6bd8]	628	reason.code = NoReason;
[4b7cce6]	629	}
	630
	631	void postvisit( const ast::ApplicationExpr * applicationExpr ) {
	632	addCandidate( applicationExpr, tenv );
	633	}
	634
[9d5089e]	635	/// Set up candidate assertions for inference
	636	void inferParameters( CandidateRef & newCand, CandidateList & out ) {
	637	// Set need bindings for any unbound assertions
	638	UniqueId crntResnSlot = 0; // matching ID for this expression's assertions
	639	for ( auto & assn : newCand->need ) {
	640	// skip already-matched assertions
	641	if ( assn.second.resnSlot != 0 ) continue;
	642	// assign slot for expression if needed
	643	if ( crntResnSlot == 0 ) { crntResnSlot = ++globalResnSlot; }
	644	// fix slot to assertion
	645	assn.second.resnSlot = crntResnSlot;
	646	}
	647	// pair slot to expression
	648	if ( crntResnSlot != 0 ) {
	649	newCand->expr.get_and_mutate()->inferred.resnSlots().emplace_back( crntResnSlot );
	650	}
	651
	652	// add to output list; assertion satisfaction will occur later
	653	out.emplace_back( newCand );
	654	}
	655
	656	/// Completes a function candidate with arguments located
[2890212]	657	void validateFunctionCandidate(
	658	const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results,
	659	CandidateList & out
[9d5089e]	660	) {
[2890212]	661	ast::ApplicationExpr * appExpr =
[9d5089e]	662	new ast::ApplicationExpr{ func->expr->location, func->expr };
	663	// sum cost and accumulate arguments
	664	std::deque< const ast::Expr * > args;
	665	Cost cost = func->cost;
	666	const ArgPack * pack = &result;
	667	while ( pack->expr ) {
	668	args.emplace_front( pack->expr );
	669	cost += pack->cost;
	670	pack = &results[pack->parent];
	671	}
	672	std::vector< ast::ptr< ast::Expr > > vargs( args.begin(), args.end() );
	673	appExpr->args = move( vargs );
	674	// build and validate new candidate
[2890212]	675	auto newCand =
[9d5089e]	676	std::make_shared<Candidate>( appExpr, result.env, result.open, result.need, cost );
	677	PRINT(
	678	std::cerr << "instantiate function success: " << appExpr << std::endl;
	679	std::cerr << "need assertions:" << std::endl;
	680	ast::print( std::cerr, result.need, 2 );
	681	)
	682	inferParameters( newCand, out );
	683	}
	684
[432ce7a]	685	/// Builds a list of candidates for a function, storing them in out
	686	void makeFunctionCandidates(
[2890212]	687	const CandidateRef & func, const ast::FunctionType * funcType,
[432ce7a]	688	const ExplodedArgs_new & args, CandidateList & out
	689	) {
[9d5089e]	690	ast::OpenVarSet funcOpen;
	691	ast::AssertionSet funcNeed, funcHave;
	692	ast::TypeEnvironment funcEnv{ func->env };
	693	makeUnifiableVars( funcType, funcOpen, funcNeed );
[2890212]	694	// add all type variables as open variables now so that those not used in the
[e0e9a0b]	695	// parameter list are still considered open
[9d5089e]	696	funcEnv.add( funcType->forall );
	697
	698	if ( targetType && ! targetType->isVoid() && ! funcType->returns.empty() ) {
	699	// attempt to narrow based on expected target type
[954c954]	700	const ast::Type * returnType = funcType->returns.front();
[2890212]	701	if ( ! unify(
	702	returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen, symtab )
[9d5089e]	703	) {
	704	// unification failed, do not pursue this candidate
	705	return;
	706	}
	707	}
	708
	709	// iteratively build matches, one parameter at a time
	710	std::vector< ArgPack > results;
	711	results.emplace_back( funcEnv, funcNeed, funcHave, funcOpen );
	712	std::size_t genStart = 0;
	713
[954c954]	714	// xxx - how to handle default arg after change to ftype representation?
	715	if (const ast::VariableExpr * varExpr = func->expr.as<ast::VariableExpr>()) {
	716	if (const ast::FunctionDecl * funcDecl = varExpr->var.as<ast::FunctionDecl>()) {
	717	// function may have default args only if directly calling by name
	718	// must use types on candidate however, due to RenameVars substitution
	719	auto nParams = funcType->params.size();
	720
	721	for (size_t i=0; i<nParams; ++i) {
	722	auto obj = funcDecl->params[i].strict_as<ast::ObjectDecl>();
	723	if (!instantiateArgument(
	724	funcType->params[i], obj->init, args, results, genStart, symtab)) return;
	725	}
	726	goto endMatch;
	727	}
	728	}
	729	for ( const auto & param : funcType->params ) {
[2890212]	730	// Try adding the arguments corresponding to the current parameter to the existing
[9d5089e]	731	// matches
[954c954]	732	// no default args for indirect calls
[2890212]	733	if ( ! instantiateArgument(
[954c954]	734	param, nullptr, args, results, genStart, symtab ) ) return;
[9d5089e]	735	}
	736
[954c954]	737	endMatch:
[9d5089e]	738	if ( funcType->isVarArgs ) {
	739	// append any unused arguments to vararg pack
	740	std::size_t genEnd;
	741	do {
	742	genEnd = results.size();
	743
	744	// iterate results
	745	for ( std::size_t i = genStart; i < genEnd; ++i ) {
	746	unsigned nextArg = results[i].nextArg;
	747
	748	// use remainder of exploded tuple if present
	749	if ( results[i].hasExpl() ) {
	750	const ExplodedArg & expl = results[i].getExpl( args );
	751
	752	unsigned nextExpl = results[i].nextExpl + 1;
	753	if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
	754
	755	results.emplace_back(
	756	i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ),
	757	copy( results[i].need ), copy( results[i].have ),
	758	copy( results[i].open ), nextArg, 0, Cost::zero, nextExpl,
	759	results[i].explAlt );
	760
	761	continue;
	762	}
	763
	764	// finish result when out of arguments
	765	if ( nextArg >= args.size() ) {
	766	validateFunctionCandidate( func, results[i], results, out );
	767
	768	continue;
	769	}
	770
	771	// add each possible next argument
	772	for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
	773	const ExplodedArg & expl = args[nextArg][j];
	774
	775	// fresh copies of parent parameters for this iteration
	776	ast::TypeEnvironment env = results[i].env;
	777	ast::OpenVarSet open = results[i].open;
	778
	779	env.addActual( expl.env, open );
	780
	781	// skip empty tuple arguments by (nearly) cloning parent into next gen
	782	if ( expl.exprs.empty() ) {
	783	results.emplace_back(
[2890212]	784	results[i], move( env ), copy( results[i].need ),
	785	copy( results[i].have ), move( open ), nextArg + 1,
[9d5089e]	786	expl.cost );
	787
	788	continue;
	789	}
	790
	791	// add new result
	792	results.emplace_back(
	793	i, expl.exprs.front(), move( env ), copy( results[i].need ),
[2890212]	794	copy( results[i].have ), move( open ), nextArg + 1, 0, expl.cost,
[9d5089e]	795	expl.exprs.size() == 1 ? 0 : 1, j );
	796	}
	797	}
	798
	799	genStart = genEnd;
	800	} while( genEnd != results.size() );
	801	} else {
	802	// filter out the results that don't use all the arguments
	803	for ( std::size_t i = genStart; i < results.size(); ++i ) {
	804	ArgPack & result = results[i];
	805	if ( ! result.hasExpl() && result.nextArg >= args.size() ) {
	806	validateFunctionCandidate( func, result, results, out );
	807	}
	808	}
	809	}
[4b7cce6]	810	}
	811
[432ce7a]	812	/// Adds implicit struct-conversions to the alternative list
	813	void addAnonConversions( const CandidateRef & cand ) {
[2890212]	814	// adds anonymous member interpretations whenever an aggregate value type is seen.
	815	// it's okay for the aggregate expression to have reference type -- cast it to the
[c8e4d2f8]	816	// base type to treat the aggregate as the referenced value
	817	ast::ptr< ast::Expr > aggrExpr( cand->expr );
	818	ast::ptr< ast::Type > & aggrType = aggrExpr.get_and_mutate()->result;
	819	cand->env.apply( aggrType );
[2890212]	820
[c8e4d2f8]	821	if ( aggrType.as< ast::ReferenceType >() ) {
[b8524ca]	822	aggrExpr = new ast::CastExpr{ aggrExpr, aggrType->stripReferences() };
[c8e4d2f8]	823	}
	824
	825	if ( auto structInst = aggrExpr->result.as< ast::StructInstType >() ) {
[898ae07]	826	addAggMembers( structInst, aggrExpr, *cand, Cost::safe, "" );
[c8e4d2f8]	827	} else if ( auto unionInst = aggrExpr->result.as< ast::UnionInstType >() ) {
[898ae07]	828	addAggMembers( unionInst, aggrExpr, *cand, Cost::safe, "" );
[c8e4d2f8]	829	}
	830	}
	831
	832	/// Adds aggregate member interpretations
[2890212]	833	void addAggMembers(
[98e8b3b]	834	const ast::BaseInstType * aggrInst, const ast::Expr * expr,
[2890212]	835	const Candidate & cand, const Cost & addedCost, const std::string & name
[c8e4d2f8]	836	) {
	837	for ( const ast::Decl * decl : aggrInst->lookup( name ) ) {
	838	auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( decl );
[2890212]	839	CandidateRef newCand = std::make_shared<Candidate>(
[898ae07]	840	cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost );
[2890212]	841	// add anonymous member interpretations whenever an aggregate value type is seen
[c8e4d2f8]	842	// as a member expression
	843	addAnonConversions( newCand );
	844	candidates.emplace_back( move( newCand ) );
	845	}
[432ce7a]	846	}
	847
[898ae07]	848	/// Adds tuple member interpretations
[2890212]	849	void addTupleMembers(
	850	const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand,
	851	const Cost & addedCost, const ast::Expr * member
[898ae07]	852	) {
	853	if ( auto constantExpr = dynamic_cast< const ast::ConstantExpr * >( member ) ) {
[2890212]	854	// get the value of the constant expression as an int, must be between 0 and the
[898ae07]	855	// length of the tuple to have meaning
	856	long long val = constantExpr->intValue();
	857	if ( val >= 0 && (unsigned long long)val < tupleType->size() ) {
	858	addCandidate(
[2890212]	859	cand, new ast::TupleIndexExpr{ expr->location, expr, (unsigned)val },
[898ae07]	860	addedCost );
	861	}
	862	}
	863	}
	864
[432ce7a]	865	void postvisit( const ast::UntypedExpr * untypedExpr ) {
	866	CandidateFinder funcFinder{ symtab, tenv };
	867	funcFinder.find( untypedExpr->func, ResolvMode::withAdjustment() );
	868	// short-circuit if no candidates
	869	if ( funcFinder.candidates.empty() ) return;
	870
[71d6bd8]	871	reason.code = NoMatch;
	872
[2890212]	873	std::vector< CandidateFinder > argCandidates =
[432ce7a]	874	selfFinder.findSubExprs( untypedExpr->args );
[2890212]	875
[432ce7a]	876	// take care of possible tuple assignments
	877	// if not tuple assignment, handled as normal function call
	878	Tuples::handleTupleAssignment( selfFinder, untypedExpr, argCandidates );
	879
	880	// find function operators
	881	ast::ptr< ast::Expr > opExpr = new ast::NameExpr{ untypedExpr->location, "?()" };
	882	CandidateFinder opFinder{ symtab, tenv };
	883	// okay if there aren't any function operations
	884	opFinder.find( opExpr, ResolvMode::withoutFailFast() );
	885	PRINT(
	886	std::cerr << "known function ops:" << std::endl;
	887	print( std::cerr, opFinder.candidates, 1 );
	888	)
	889
	890	// pre-explode arguments
	891	ExplodedArgs_new argExpansions;
	892	for ( const CandidateFinder & args : argCandidates ) {
	893	argExpansions.emplace_back();
	894	auto & argE = argExpansions.back();
	895	for ( const CandidateRef & arg : args ) { argE.emplace_back( *arg, symtab ); }
	896	}
	897
	898	// Find function matches
	899	CandidateList found;
	900	SemanticErrorException errors;
	901	for ( CandidateRef & func : funcFinder ) {
	902	try {
	903	PRINT(
	904	std::cerr << "working on alternative:" << std::endl;
	905	print( std::cerr, *func, 2 );
	906	)
	907
	908	// check if the type is a pointer to function
	909	const ast::Type * funcResult = func->expr->result->stripReferences();
	910	if ( auto pointer = dynamic_cast< const ast::PointerType * >( funcResult ) ) {
	911	if ( auto function = pointer->base.as< ast::FunctionType >() ) {
	912	CandidateRef newFunc{ new Candidate{ *func } };
[2890212]	913	newFunc->expr =
[432ce7a]	914	referenceToRvalueConversion( newFunc->expr, newFunc->cost );
	915	makeFunctionCandidates( newFunc, function, argExpansions, found );
	916	}
[2890212]	917	} else if (
	918	auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult )
[432ce7a]	919	) {
	920	if ( const ast::EqvClass * clz = func->env.lookup( inst->name ) ) {
	921	if ( auto function = clz->bound.as< ast::FunctionType >() ) {
	922	CandidateRef newFunc{ new Candidate{ *func } };
[2890212]	923	newFunc->expr =
[432ce7a]	924	referenceToRvalueConversion( newFunc->expr, newFunc->cost );
	925	makeFunctionCandidates( newFunc, function, argExpansions, found );
	926	}
	927	}
	928	}
	929	} catch ( SemanticErrorException & e ) { errors.append( e ); }
	930	}
	931
	932	// Find matches on function operators `?()`
	933	if ( ! opFinder.candidates.empty() ) {
	934	// add exploded function alternatives to front of argument list
	935	std::vector< ExplodedArg > funcE;
	936	funcE.reserve( funcFinder.candidates.size() );
[2890212]	937	for ( const CandidateRef & func : funcFinder ) {
[432ce7a]	938	funcE.emplace_back( *func, symtab );
	939	}
[9d5089e]	940	argExpansions.emplace_front( move( funcE ) );
[432ce7a]	941
	942	for ( const CandidateRef & op : opFinder ) {
	943	try {
	944	// check if type is pointer-to-function
	945	const ast::Type * opResult = op->expr->result->stripReferences();
	946	if ( auto pointer = dynamic_cast< const ast::PointerType * >( opResult ) ) {
	947	if ( auto function = pointer->base.as< ast::FunctionType >() ) {
	948	CandidateRef newOp{ new Candidate{ *op} };
[2890212]	949	newOp->expr =
[432ce7a]	950	referenceToRvalueConversion( newOp->expr, newOp->cost );
	951	makeFunctionCandidates( newOp, function, argExpansions, found );
	952	}
	953	}
	954	} catch ( SemanticErrorException & e ) { errors.append( e ); }
	955	}
	956	}
	957
[2890212]	958	// Implement SFINAE; resolution errors are only errors if there aren't any non-error
[432ce7a]	959	// candidates
	960	if ( found.empty() && ! errors.isEmpty() ) { throw errors; }
	961
	962	// Compute conversion costs
	963	for ( CandidateRef & withFunc : found ) {
	964	Cost cvtCost = computeApplicationConversionCost( withFunc, symtab );
	965
	966	PRINT(
	967	auto appExpr = withFunc->expr.strict_as< ast::ApplicationExpr >();
	968	auto pointer = appExpr->func->result.strict_as< ast::PointerType >();
	969	auto function = pointer->base.strict_as< ast::FunctionType >();
[2890212]	970
[432ce7a]	971	std::cerr << "Case +++++++++++++ " << appExpr->func << std::endl;
	972	std::cerr << "parameters are:" << std::endl;
	973	ast::printAll( std::cerr, function->params, 2 );
	974	std::cerr << "arguments are:" << std::endl;
	975	ast::printAll( std::cerr, appExpr->args, 2 );
	976	std::cerr << "bindings are:" << std::endl;
	977	ast::print( std::cerr, withFunc->env, 2 );
	978	std::cerr << "cost is: " << withFunc->cost << std::endl;
	979	std::cerr << "cost of conversion is:" << cvtCost << std::endl;
	980	)
	981
	982	if ( cvtCost != Cost::infinity ) {
	983	withFunc->cvtCost = cvtCost;
[9d5089e]	984	candidates.emplace_back( move( withFunc ) );
[432ce7a]	985	}
	986	}
[9d5089e]	987	found = move( candidates );
[432ce7a]	988
	989	// use a new list so that candidates are not examined by addAnonConversions twice
	990	CandidateList winners = findMinCost( found );
	991	promoteCvtCost( winners );
	992
[2890212]	993	// function may return a struct/union value, in which case we need to add candidates
	994	// for implicit conversions to each of the anonymous members, which must happen after
[432ce7a]	995	// `findMinCost`, since anon conversions are never the cheapest
	996	for ( const CandidateRef & c : winners ) {
	997	addAnonConversions( c );
	998	}
	999	spliceBegin( candidates, winners );
	1000
	1001	if ( candidates.empty() && targetType && ! targetType->isVoid() ) {
[2890212]	1002	// If resolution is unsuccessful with a target type, try again without, since it
[432ce7a]	1003	// will sometimes succeed when it wouldn't with a target type binding.
	1004	// For example:
	1005	// forall( otype T ) T & ?[]( T *, ptrdiff_t );
	1006	// const char * x = "hello world";
	1007	// unsigned char ch = x[0];
	1008	// Fails with simple return type binding (xxx -- check this!) as follows:
	1009	// * T is bound to unsigned char
	1010	// * (x: const char ) is unified with unsigned char , which fails
	1011	// xxx -- fix this better
	1012	targetType = nullptr;
	1013	postvisit( untypedExpr );
	1014	}
	1015	}
	1016
[4b7cce6]	1017	/// true if expression is an lvalue
	1018	static bool isLvalue( const ast::Expr * x ) {
[cf32116]	1019	return x->result && ( x->get_lvalue() \|\| x->result.as< ast::ReferenceType >() );
[4b7cce6]	1020	}
	1021
	1022	void postvisit( const ast::AddressExpr * addressExpr ) {
	1023	CandidateFinder finder{ symtab, tenv };
	1024	finder.find( addressExpr->arg );
[71d6bd8]	1025
	1026	if( finder.candidates.empty() ) return;
	1027
	1028	reason.code = NoMatch;
	1029
[4b7cce6]	1030	for ( CandidateRef & r : finder.candidates ) {
	1031	if ( ! isLvalue( r->expr ) ) continue;
	1032	addCandidate( *r, new ast::AddressExpr{ addressExpr->location, r->expr } );
	1033	}
	1034	}
	1035
	1036	void postvisit( const ast::LabelAddressExpr * labelExpr ) {
	1037	addCandidate( labelExpr, tenv );
	1038	}
	1039
	1040	void postvisit( const ast::CastExpr * castExpr ) {
[c8e4d2f8]	1041	ast::ptr< ast::Type > toType = castExpr->result;
	1042	assert( toType );
	1043	toType = resolveTypeof( toType, symtab );
[18e683b]	1044	toType = SymTab::validateType( castExpr->location, toType, symtab );
[c8e4d2f8]	1045	toType = adjustExprType( toType, tenv, symtab );
	1046
	1047	CandidateFinder finder{ symtab, tenv, toType };
	1048	finder.find( castExpr->arg, ResolvMode::withAdjustment() );
	1049
[71d6bd8]	1050	if( !finder.candidates.empty() ) reason.code = NoMatch;
	1051
[c8e4d2f8]	1052	CandidateList matches;
	1053	for ( CandidateRef & cand : finder.candidates ) {
	1054	ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have;
	1055	ast::OpenVarSet open( cand->open );
	1056
	1057	cand->env.extractOpenVars( open );
	1058
[2890212]	1059	// It is possible that a cast can throw away some values in a multiply-valued
	1060	// expression, e.g. cast-to-void, one value to zero. Figure out the prefix of the
	1061	// subexpression results that are cast directly. The candidate is invalid if it
[c8e4d2f8]	1062	// has fewer results than there are types to cast to.
	1063	int discardedValues = cand->expr->result->size() - toType->size();
	1064	if ( discardedValues < 0 ) continue;
	1065
	1066	// unification run for side-effects
	1067	unify( toType, cand->expr->result, cand->env, need, have, open, symtab );
[cf32116]	1068	Cost thisCost = castCost( cand->expr->result, toType, cand->expr->get_lvalue(),
	1069	symtab, cand->env );
[c8e4d2f8]	1070	PRINT(
	1071	std::cerr << "working on cast with result: " << toType << std::endl;
	1072	std::cerr << "and expr type: " << cand->expr->result << std::endl;
	1073	std::cerr << "env: " << cand->env << std::endl;
	1074	)
	1075	if ( thisCost != Cost::infinity ) {
	1076	PRINT(
	1077	std::cerr << "has finite cost." << std::endl;
	1078	)
	1079	// count one safe conversion for each value that is thrown away
	1080	thisCost.incSafe( discardedValues );
[2890212]	1081	CandidateRef newCand = std::make_shared<Candidate>(
	1082	restructureCast( cand->expr, toType, castExpr->isGenerated ),
	1083	copy( cand->env ), move( open ), move( need ), cand->cost,
[c8e4d2f8]	1084	cand->cost + thisCost );
	1085	inferParameters( newCand, matches );
	1086	}
	1087	}
	1088
[898ae07]	1089	// select first on argument cost, then conversion cost
	1090	CandidateList minArgCost = findMinCost( matches );
	1091	promoteCvtCost( minArgCost );
	1092	candidates = findMinCost( minArgCost );
[4b7cce6]	1093	}
	1094
	1095	void postvisit( const ast::VirtualCastExpr * castExpr ) {
	1096	assertf( castExpr->result, "Implicit virtual cast targets not yet supported." );
	1097	CandidateFinder finder{ symtab, tenv };
	1098	// don't prune here, all alternatives guaranteed to have same type
	1099	finder.find( castExpr->arg, ResolvMode::withoutPrune() );
	1100	for ( CandidateRef & r : finder.candidates ) {
[2890212]	1101	addCandidate(
	1102	*r,
[c8e4d2f8]	1103	new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } );
[4b7cce6]	1104	}
	1105	}
	1106
[4ef08f7]	1107	void postvisit( const ast::KeywordCastExpr * castExpr ) {
	1108	const auto & loc = castExpr->location;
	1109	assertf( castExpr->result, "Cast target should have been set in Validate." );
	1110	auto ref = castExpr->result.strict_as<ast::ReferenceType>();
	1111	auto inst = ref->base.strict_as<ast::StructInstType>();
	1112	auto target = inst->base.get();
	1113
	1114	CandidateFinder finder{ symtab, tenv };
	1115
	1116	auto pick_alternatives = [target, this](CandidateList & found, bool expect_ref) {
	1117	for(auto & cand : found) {
	1118	const ast::Type * expr = cand->expr->result.get();
	1119	if(expect_ref) {
	1120	auto res = dynamic_cast<const ast::ReferenceType*>(expr);
	1121	if(!res) { continue; }
	1122	expr = res->base.get();
	1123	}
	1124
	1125	if(auto insttype = dynamic_cast<const ast::TypeInstType*>(expr)) {
	1126	auto td = cand->env.lookup(insttype->name);
	1127	if(!td) { continue; }
	1128	expr = td->bound.get();
	1129	}
	1130
	1131	if(auto base = dynamic_cast<const ast::StructInstType*>(expr)) {
	1132	if(base->base == target) {
	1133	candidates.push_back( std::move(cand) );
	1134	reason.code = NoReason;
	1135	}
	1136	}
	1137	}
	1138	};
	1139
	1140	try {
	1141	// Attempt 1 : turn (thread&)X into ($thread&)X.__thrd
	1142	// Clone is purely for memory management
	1143	std::unique_ptr<const ast::Expr> tech1 { new ast::UntypedMemberExpr(loc, new ast::NameExpr(loc, castExpr->concrete_target.field), castExpr->arg) };
	1144
	1145	// don't prune here, since it's guaranteed all alternatives will have the same type
	1146	finder.find( tech1.get(), ResolvMode::withoutPrune() );
	1147	pick_alternatives(finder.candidates, false);
	1148
	1149	return;
	1150	} catch(SemanticErrorException & ) {}
	1151
	1152	// Fallback : turn (thread&)X into ($thread&)get_thread(X)
	1153	std::unique_ptr<const ast::Expr> fallback { ast::UntypedExpr::createDeref(loc, new ast::UntypedExpr(loc, new ast::NameExpr(loc, castExpr->concrete_target.getter), { castExpr->arg })) };
	1154	// don't prune here, since it's guaranteed all alternatives will have the same type
	1155	finder.find( fallback.get(), ResolvMode::withoutPrune() );
	1156
	1157	pick_alternatives(finder.candidates, true);
	1158
	1159	// Whatever happens here, we have no more fallbacks
	1160	}
	1161
[4b7cce6]	1162	void postvisit( const ast::UntypedMemberExpr * memberExpr ) {
[898ae07]	1163	CandidateFinder aggFinder{ symtab, tenv };
	1164	aggFinder.find( memberExpr->aggregate, ResolvMode::withAdjustment() );
	1165	for ( CandidateRef & agg : aggFinder.candidates ) {
[2890212]	1166	// it's okay for the aggregate expression to have reference type -- cast it to the
[898ae07]	1167	// base type to treat the aggregate as the referenced value
	1168	Cost addedCost = Cost::zero;
	1169	agg->expr = referenceToRvalueConversion( agg->expr, addedCost );
	1170
	1171	// find member of the given type
	1172	if ( auto structInst = agg->expr->result.as< ast::StructInstType >() ) {
[2890212]	1173	addAggMembers(
[898ae07]	1174	structInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) );
	1175	} else if ( auto unionInst = agg->expr->result.as< ast::UnionInstType >() ) {
[2890212]	1176	addAggMembers(
[898ae07]	1177	unionInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) );
	1178	} else if ( auto tupleType = agg->expr->result.as< ast::TupleType >() ) {
	1179	addTupleMembers( tupleType, agg->expr, *agg, addedCost, memberExpr->member );
	1180	}
	1181	}
[4b7cce6]	1182	}
	1183
	1184	void postvisit( const ast::MemberExpr * memberExpr ) {
	1185	addCandidate( memberExpr, tenv );
	1186	}
	1187
[898ae07]	1188	void postvisit( const ast::NameExpr * nameExpr ) {
	1189	std::vector< ast::SymbolTable::IdData > declList = symtab.lookupId( nameExpr->name );
	1190	PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; )
[71d6bd8]	1191	if( declList.empty() ) return;
	1192
	1193	reason.code = NoMatch;
	1194
[898ae07]	1195	for ( auto & data : declList ) {
	1196	Cost cost = Cost::zero;
	1197	ast::Expr * newExpr = data.combine( nameExpr->location, cost );
	1198
	1199	CandidateRef newCand = std::make_shared<Candidate>(
[2890212]	1200	newExpr, copy( tenv ), ast::OpenVarSet{}, ast::AssertionSet{}, Cost::zero,
[898ae07]	1201	cost );
	1202	PRINT(
	1203	std::cerr << "decl is ";
	1204	ast::print( std::cerr, data.id );
	1205	std::cerr << std::endl;
	1206	std::cerr << "newExpr is ";
	1207	ast::print( std::cerr, newExpr );
	1208	std::cerr << std::endl;
	1209	)
[2890212]	1210	newCand->expr = ast::mutate_field(
	1211	newCand->expr.get(), &ast::Expr::result,
[898ae07]	1212	renameTyVars( newCand->expr->result ) );
[2890212]	1213	// add anonymous member interpretations whenever an aggregate value type is seen
[898ae07]	1214	// as a name expression
	1215	addAnonConversions( newCand );
	1216	candidates.emplace_back( move( newCand ) );
	1217	}
[4b7cce6]	1218	}
	1219
	1220	void postvisit( const ast::VariableExpr * variableExpr ) {
	1221	// not sufficient to just pass `variableExpr` here, type might have changed since
	1222	// creation
[2890212]	1223	addCandidate(
[4b7cce6]	1224	new ast::VariableExpr{ variableExpr->location, variableExpr->var }, tenv );
	1225	}
	1226
	1227	void postvisit( const ast::ConstantExpr * constantExpr ) {
	1228	addCandidate( constantExpr, tenv );
	1229	}
	1230
	1231	void postvisit( const ast::SizeofExpr * sizeofExpr ) {
[898ae07]	1232	if ( sizeofExpr->type ) {
[2890212]	1233	addCandidate(
	1234	new ast::SizeofExpr{
	1235	sizeofExpr->location, resolveTypeof( sizeofExpr->type, symtab ) },
[898ae07]	1236	tenv );
	1237	} else {
	1238	// find all candidates for the argument to sizeof
	1239	CandidateFinder finder{ symtab, tenv };
	1240	finder.find( sizeofExpr->expr );
	1241	// find the lowest-cost candidate, otherwise ambiguous
	1242	CandidateList winners = findMinCost( finder.candidates );
	1243	if ( winners.size() != 1 ) {
[2890212]	1244	SemanticError(
[898ae07]	1245	sizeofExpr->expr.get(), "Ambiguous expression in sizeof operand: " );
	1246	}
	1247	// return the lowest-cost candidate
	1248	CandidateRef & choice = winners.front();
	1249	choice->expr = referenceToRvalueConversion( choice->expr, choice->cost );
	1250	choice->cost = Cost::zero;
	1251	addCandidate( *choice, new ast::SizeofExpr{ sizeofExpr->location, choice->expr } );
	1252	}
[4b7cce6]	1253	}
	1254
	1255	void postvisit( const ast::AlignofExpr * alignofExpr ) {
[898ae07]	1256	if ( alignofExpr->type ) {
[2890212]	1257	addCandidate(
	1258	new ast::AlignofExpr{
	1259	alignofExpr->location, resolveTypeof( alignofExpr->type, symtab ) },
[898ae07]	1260	tenv );
	1261	} else {
	1262	// find all candidates for the argument to alignof
	1263	CandidateFinder finder{ symtab, tenv };
	1264	finder.find( alignofExpr->expr );
	1265	// find the lowest-cost candidate, otherwise ambiguous
	1266	CandidateList winners = findMinCost( finder.candidates );
	1267	if ( winners.size() != 1 ) {
[2890212]	1268	SemanticError(
[898ae07]	1269	alignofExpr->expr.get(), "Ambiguous expression in alignof operand: " );
	1270	}
	1271	// return the lowest-cost candidate
	1272	CandidateRef & choice = winners.front();
	1273	choice->expr = referenceToRvalueConversion( choice->expr, choice->cost );
	1274	choice->cost = Cost::zero;
[2890212]	1275	addCandidate(
[898ae07]	1276	*choice, new ast::AlignofExpr{ alignofExpr->location, choice->expr } );
	1277	}
[4b7cce6]	1278	}
	1279
	1280	void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) {
[98e8b3b]	1281	const ast::BaseInstType * aggInst;
[898ae07]	1282	if (( aggInst = offsetofExpr->type.as< ast::StructInstType >() )) ;
	1283	else if (( aggInst = offsetofExpr->type.as< ast::UnionInstType >() )) ;
	1284	else return;
	1285
	1286	for ( const ast::Decl * member : aggInst->lookup( offsetofExpr->member ) ) {
	1287	auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( member );
[2890212]	1288	addCandidate(
[898ae07]	1289	new ast::OffsetofExpr{ offsetofExpr->location, aggInst, dwt }, tenv );
	1290	}
[4b7cce6]	1291	}
	1292
	1293	void postvisit( const ast::OffsetofExpr * offsetofExpr ) {
	1294	addCandidate( offsetofExpr, tenv );
	1295	}
	1296
	1297	void postvisit( const ast::OffsetPackExpr * offsetPackExpr ) {
	1298	addCandidate( offsetPackExpr, tenv );
	1299	}
	1300
	1301	void postvisit( const ast::LogicalExpr * logicalExpr ) {
	1302	CandidateFinder finder1{ symtab, tenv };
	1303	finder1.find( logicalExpr->arg1, ResolvMode::withAdjustment() );
	1304	if ( finder1.candidates.empty() ) return;
	1305
	1306	CandidateFinder finder2{ symtab, tenv };
	1307	finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() );
	1308	if ( finder2.candidates.empty() ) return;
	1309
[71d6bd8]	1310	reason.code = NoMatch;
	1311
[4b7cce6]	1312	for ( const CandidateRef & r1 : finder1.candidates ) {
	1313	for ( const CandidateRef & r2 : finder2.candidates ) {
	1314	ast::TypeEnvironment env{ r1->env };
	1315	env.simpleCombine( r2->env );
	1316	ast::OpenVarSet open{ r1->open };
	1317	mergeOpenVars( open, r2->open );
	1318	ast::AssertionSet need;
	1319	mergeAssertionSet( need, r1->need );
	1320	mergeAssertionSet( need, r2->need );
	1321
	1322	addCandidate(
[2890212]	1323	new ast::LogicalExpr{
[4b7cce6]	1324	logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd },
[9d5089e]	1325	move( env ), move( open ), move( need ), r1->cost + r2->cost );
[4b7cce6]	1326	}
	1327	}
	1328	}
	1329
	1330	void postvisit( const ast::ConditionalExpr * conditionalExpr ) {
	1331	// candidates for condition
	1332	CandidateFinder finder1{ symtab, tenv };
	1333	finder1.find( conditionalExpr->arg1, ResolvMode::withAdjustment() );
	1334	if ( finder1.candidates.empty() ) return;
	1335
	1336	// candidates for true result
	1337	CandidateFinder finder2{ symtab, tenv };
	1338	finder2.find( conditionalExpr->arg2, ResolvMode::withAdjustment() );
	1339	if ( finder2.candidates.empty() ) return;
	1340
	1341	// candidates for false result
	1342	CandidateFinder finder3{ symtab, tenv };
	1343	finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() );
	1344	if ( finder3.candidates.empty() ) return;
	1345
[71d6bd8]	1346	reason.code = NoMatch;
	1347
[4b7cce6]	1348	for ( const CandidateRef & r1 : finder1.candidates ) {
	1349	for ( const CandidateRef & r2 : finder2.candidates ) {
	1350	for ( const CandidateRef & r3 : finder3.candidates ) {
	1351	ast::TypeEnvironment env{ r1->env };
	1352	env.simpleCombine( r2->env );
	1353	env.simpleCombine( r3->env );
	1354	ast::OpenVarSet open{ r1->open };
	1355	mergeOpenVars( open, r2->open );
	1356	mergeOpenVars( open, r3->open );
	1357	ast::AssertionSet need;
	1358	mergeAssertionSet( need, r1->need );
	1359	mergeAssertionSet( need, r2->need );
	1360	mergeAssertionSet( need, r3->need );
	1361	ast::AssertionSet have;
	1362
[2890212]	1363	// unify true and false results, then infer parameters to produce new
[4b7cce6]	1364	// candidates
	1365	ast::ptr< ast::Type > common;
[2890212]	1366	if (
	1367	unify(
	1368	r2->expr->result, r3->expr->result, env, need, have, open, symtab,
	1369	common )
[4b7cce6]	1370	) {
[898ae07]	1371	// generate typed expression
[2890212]	1372	ast::ConditionalExpr * newExpr = new ast::ConditionalExpr{
[898ae07]	1373	conditionalExpr->location, r1->expr, r2->expr, r3->expr };
	1374	newExpr->result = common ? common : r2->expr->result;
	1375	// convert both options to result type
	1376	Cost cost = r1->cost + r2->cost + r3->cost;
[2890212]	1377	newExpr->arg2 = computeExpressionConversionCost(
[898ae07]	1378	newExpr->arg2, newExpr->result, symtab, env, cost );
	1379	newExpr->arg3 = computeExpressionConversionCost(
	1380	newExpr->arg3, newExpr->result, symtab, env, cost );
	1381	// output candidate
	1382	CandidateRef newCand = std::make_shared<Candidate>(
	1383	newExpr, move( env ), move( open ), move( need ), cost );
	1384	inferParameters( newCand, candidates );
[4b7cce6]	1385	}
	1386	}
	1387	}
	1388	}
	1389	}
	1390
	1391	void postvisit( const ast::CommaExpr * commaExpr ) {
	1392	ast::TypeEnvironment env{ tenv };
	1393	ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, symtab, env );
[2890212]	1394
[4b7cce6]	1395	CandidateFinder finder2{ symtab, env };
	1396	finder2.find( commaExpr->arg2, ResolvMode::withAdjustment() );
	1397
	1398	for ( const CandidateRef & r2 : finder2.candidates ) {
	1399	addCandidate( *r2, new ast::CommaExpr{ commaExpr->location, arg1, r2->expr } );
	1400	}
	1401	}
	1402
	1403	void postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr ) {
	1404	addCandidate( ctorExpr, tenv );
	1405	}
	1406
	1407	void postvisit( const ast::ConstructorExpr * ctorExpr ) {
	1408	CandidateFinder finder{ symtab, tenv };
	1409	finder.find( ctorExpr->callExpr, ResolvMode::withoutPrune() );
	1410	for ( CandidateRef & r : finder.candidates ) {
	1411	addCandidate( *r, new ast::ConstructorExpr{ ctorExpr->location, r->expr } );
	1412	}
	1413	}
	1414
	1415	void postvisit( const ast::RangeExpr * rangeExpr ) {
	1416	// resolve low and high, accept candidates where low and high types unify
	1417	CandidateFinder finder1{ symtab, tenv };
	1418	finder1.find( rangeExpr->low, ResolvMode::withAdjustment() );
	1419	if ( finder1.candidates.empty() ) return;
	1420
	1421	CandidateFinder finder2{ symtab, tenv };
	1422	finder2.find( rangeExpr->high, ResolvMode::withAdjustment() );
	1423	if ( finder2.candidates.empty() ) return;
	1424
[71d6bd8]	1425	reason.code = NoMatch;
	1426
[4b7cce6]	1427	for ( const CandidateRef & r1 : finder1.candidates ) {
	1428	for ( const CandidateRef & r2 : finder2.candidates ) {
	1429	ast::TypeEnvironment env{ r1->env };
	1430	env.simpleCombine( r2->env );
	1431	ast::OpenVarSet open{ r1->open };
	1432	mergeOpenVars( open, r2->open );
	1433	ast::AssertionSet need;
	1434	mergeAssertionSet( need, r1->need );
	1435	mergeAssertionSet( need, r2->need );
	1436	ast::AssertionSet have;
	1437
	1438	ast::ptr< ast::Type > common;
[2890212]	1439	if (
	1440	unify(
	1441	r1->expr->result, r2->expr->result, env, need, have, open, symtab,
	1442	common )
[4b7cce6]	1443	) {
[898ae07]	1444	// generate new expression
[2890212]	1445	ast::RangeExpr * newExpr =
[4b7cce6]	1446	new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr };
	1447	newExpr->result = common ? common : r1->expr->result;
[898ae07]	1448	// add candidate
	1449	CandidateRef newCand = std::make_shared<Candidate>(
[2890212]	1450	newExpr, move( env ), move( open ), move( need ),
[898ae07]	1451	r1->cost + r2->cost );
	1452	inferParameters( newCand, candidates );
[4b7cce6]	1453	}
	1454	}
	1455	}
	1456	}
	1457
	1458	void postvisit( const ast::UntypedTupleExpr * tupleExpr ) {
[2890212]	1459	std::vector< CandidateFinder > subCandidates =
[4b7cce6]	1460	selfFinder.findSubExprs( tupleExpr->exprs );
	1461	std::vector< CandidateList > possibilities;
	1462	combos( subCandidates.begin(), subCandidates.end(), back_inserter( possibilities ) );
	1463
	1464	for ( const CandidateList & subs : possibilities ) {
	1465	std::vector< ast::ptr< ast::Expr > > exprs;
	1466	exprs.reserve( subs.size() );
	1467	for ( const CandidateRef & sub : subs ) { exprs.emplace_back( sub->expr ); }
	1468
	1469	ast::TypeEnvironment env;
	1470	ast::OpenVarSet open;
	1471	ast::AssertionSet need;
	1472	for ( const CandidateRef & sub : subs ) {
	1473	env.simpleCombine( sub->env );
	1474	mergeOpenVars( open, sub->open );
	1475	mergeAssertionSet( need, sub->need );
	1476	}
	1477
	1478	addCandidate(
[2890212]	1479	new ast::TupleExpr{ tupleExpr->location, move( exprs ) },
[9d5089e]	1480	move( env ), move( open ), move( need ), sumCost( subs ) );
[4b7cce6]	1481	}
	1482	}
	1483
	1484	void postvisit( const ast::TupleExpr * tupleExpr ) {
	1485	addCandidate( tupleExpr, tenv );
	1486	}
	1487
	1488	void postvisit( const ast::TupleIndexExpr * tupleExpr ) {
	1489	addCandidate( tupleExpr, tenv );
	1490	}
	1491
	1492	void postvisit( const ast::TupleAssignExpr * tupleExpr ) {
	1493	addCandidate( tupleExpr, tenv );
	1494	}
	1495
	1496	void postvisit( const ast::UniqueExpr * unqExpr ) {
	1497	CandidateFinder finder{ symtab, tenv };
	1498	finder.find( unqExpr->expr, ResolvMode::withAdjustment() );
	1499	for ( CandidateRef & r : finder.candidates ) {
	1500	// ensure that the the id is passed on so that the expressions are "linked"
	1501	addCandidate( *r, new ast::UniqueExpr{ unqExpr->location, r->expr, unqExpr->id } );
	1502	}
	1503	}
	1504
	1505	void postvisit( const ast::StmtExpr * stmtExpr ) {
[17a0ede2]	1506	addCandidate( resolveStmtExpr( stmtExpr, symtab ), tenv );
[4b7cce6]	1507	}
	1508
	1509	void postvisit( const ast::UntypedInitExpr * initExpr ) {
[17a0ede2]	1510	// handle each option like a cast
	1511	CandidateList matches;
	1512	PRINT(
	1513	std::cerr << "untyped init expr: " << initExpr << std::endl;
	1514	)
	1515	// O(n^2) checks of d-types with e-types
	1516	for ( const ast::InitAlternative & initAlt : initExpr->initAlts ) {
	1517	// calculate target type
	1518	const ast::Type * toType = resolveTypeof( initAlt.type, symtab );
[18e683b]	1519	toType = SymTab::validateType( initExpr->location, toType, symtab );
[17a0ede2]	1520	toType = adjustExprType( toType, tenv, symtab );
[2890212]	1521	// The call to find must occur inside this loop, otherwise polymorphic return
	1522	// types are not bound to the initialization type, since return type variables are
	1523	// only open for the duration of resolving the UntypedExpr.
[17a0ede2]	1524	CandidateFinder finder{ symtab, tenv, toType };
	1525	finder.find( initExpr->expr, ResolvMode::withAdjustment() );
	1526	for ( CandidateRef & cand : finder.candidates ) {
[71d6bd8]	1527	if(reason.code == NotFound) reason.code = NoMatch;
	1528
[17a0ede2]	1529	ast::TypeEnvironment env{ cand->env };
	1530	ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have;
	1531	ast::OpenVarSet open{ cand->open };
	1532
	1533	PRINT(
	1534	std::cerr << " @ " << toType << " " << initAlt.designation << std::endl;
	1535	)
	1536
[2890212]	1537	// It is possible that a cast can throw away some values in a multiply-valued
	1538	// expression, e.g. cast-to-void, one value to zero. Figure out the prefix of
	1539	// the subexpression results that are cast directly. The candidate is invalid
[17a0ede2]	1540	// if it has fewer results than there are types to cast to.
	1541	int discardedValues = cand->expr->result->size() - toType->size();
	1542	if ( discardedValues < 0 ) continue;
	1543
	1544	// unification run for side-effects
	1545	unify( toType, cand->expr->result, env, need, have, open, symtab );
[ef9988b]	1546	Cost thisCost = computeConversionCost( cand->expr->result, toType, cand->expr->get_lvalue(),
[cf32116]	1547	symtab, env );
[2890212]	1548
[17a0ede2]	1549	if ( thisCost != Cost::infinity ) {
	1550	// count one safe conversion for each value that is thrown away
	1551	thisCost.incSafe( discardedValues );
[2890212]	1552	CandidateRef newCand = std::make_shared<Candidate>(
	1553	new ast::InitExpr{
	1554	initExpr->location, restructureCast( cand->expr, toType ),
	1555	initAlt.designation },
[ef9988b]	1556	move(env), move( open ), move( need ), cand->cost, thisCost );
[17a0ede2]	1557	inferParameters( newCand, matches );
	1558	}
	1559	}
	1560	}
	1561
	1562	// select first on argument cost, then conversion cost
	1563	CandidateList minArgCost = findMinCost( matches );
	1564	promoteCvtCost( minArgCost );
	1565	candidates = findMinCost( minArgCost );
[4b7cce6]	1566	}
	1567
	1568	void postvisit( const ast::InitExpr * ) {
	1569	assertf( false, "CandidateFinder should never see a resolved InitExpr." );
	1570	}
	1571
	1572	void postvisit( const ast::DeletedExpr * ) {
	1573	assertf( false, "CandidateFinder should never see a DeletedExpr." );
	1574	}
	1575
	1576	void postvisit( const ast::GenericExpr * ) {
	1577	assertf( false, "_Generic is not yet supported." );
	1578	}
[396037d]	1579	};
	1580
[0d070ca]	1581	// size_t Finder::traceId = Stats::Heap::new_stacktrace_id("Finder");
[2890212]	1582	/// Prunes a list of candidates down to those that have the minimum conversion cost for a given
[396037d]	1583	/// return type. Skips ambiguous candidates.
	1584	CandidateList pruneCandidates( CandidateList & candidates ) {
[d57e349]	1585	struct PruneStruct {
	1586	CandidateRef candidate;
	1587	bool ambiguous;
	1588
	1589	PruneStruct() = default;
	1590	PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {}
	1591	};
	1592
	1593	// find lowest-cost candidate for each type
	1594	std::unordered_map< std::string, PruneStruct > selected;
	1595	for ( CandidateRef & candidate : candidates ) {
	1596	std::string mangleName;
	1597	{
	1598	ast::ptr< ast::Type > newType = candidate->expr->result;
[4e13e2a]	1599	assertf(candidate->expr->result, "Result of expression %p for candidate is null", candidate->expr.get());
[d57e349]	1600	candidate->env.apply( newType );
	1601	mangleName = Mangle::mangle( newType );
	1602	}
	1603
	1604	auto found = selected.find( mangleName );
	1605	if ( found != selected.end() ) {
	1606	if ( candidate->cost < found->second.candidate->cost ) {
	1607	PRINT(
[2890212]	1608	std::cerr << "cost " << candidate->cost << " beats "
[d57e349]	1609	<< found->second.candidate->cost << std::endl;
	1610	)
	1611
	1612	found->second = PruneStruct{ candidate };
	1613	} else if ( candidate->cost == found->second.candidate->cost ) {
[2890212]	1614	// if one of the candidates contains a deleted identifier, can pick the other,
	1615	// since deleted expressions should not be ambiguous if there is another option
[d57e349]	1616	// that is at least as good
	1617	if ( findDeletedExpr( candidate->expr ) ) {
	1618	// do nothing
	1619	PRINT( std::cerr << "candidate is deleted" << std::endl; )
	1620	} else if ( findDeletedExpr( found->second.candidate->expr ) ) {
	1621	PRINT( std::cerr << "current is deleted" << std::endl; )
	1622	found->second = PruneStruct{ candidate };
	1623	} else {
	1624	PRINT( std::cerr << "marking ambiguous" << std::endl; )
	1625	found->second.ambiguous = true;
	1626	}
	1627	} else {
	1628	PRINT(
[2890212]	1629	std::cerr << "cost " << candidate->cost << " loses to "
[d57e349]	1630	<< found->second.candidate->cost << std::endl;
	1631	)
	1632	}
	1633	} else {
	1634	selected.emplace_hint( found, mangleName, candidate );
	1635	}
	1636	}
	1637
	1638	// report unambiguous min-cost candidates
	1639	CandidateList out;
	1640	for ( auto & target : selected ) {
	1641	if ( target.second.ambiguous ) continue;
	1642
	1643	CandidateRef cand = target.second.candidate;
[2890212]	1644
[d57e349]	1645	ast::ptr< ast::Type > newResult = cand->expr->result;
	1646	cand->env.applyFree( newResult );
	1647	cand->expr = ast::mutate_field(
[9d5089e]	1648	cand->expr.get(), &ast::Expr::result, move( newResult ) );
[2890212]	1649
[d57e349]	1650	out.emplace_back( cand );
	1651	}
	1652	return out;
	1653	}
	1654
[396037d]	1655	} // anonymous namespace
	1656
[99d4584]	1657	void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) {
[396037d]	1658	// Find alternatives for expression
	1659	ast::Pass<Finder> finder{ *this };
	1660	expr->accept( finder );
	1661
	1662	if ( mode.failFast && candidates.empty() ) {
[7ff3e522]	1663	switch(finder.core.reason.code) {
[71d6bd8]	1664	case Finder::NotFound:
	1665	{ SemanticError( expr, "No alternatives for expression " ); break; }
	1666	case Finder::NoMatch:
	1667	{ SemanticError( expr, "Invalid application of existing declaration(s) in expression " ); break; }
	1668	case Finder::ArgsToFew:
	1669	case Finder::ArgsToMany:
	1670	case Finder::RetsToFew:
	1671	case Finder::RetsToMany:
	1672	case Finder::NoReason:
	1673	default:
	1674	{ SemanticError( expr->location, "No reasonable alternatives for expression : reasons unkown" ); }
	1675	}
[396037d]	1676	}
	1677
	1678	if ( mode.satisfyAssns \|\| mode.prune ) {
	1679	// trim candidates to just those where the assertions are satisfiable
	1680	// - necessary pre-requisite to pruning
	1681	CandidateList satisfied;
	1682	std::vector< std::string > errors;
[b69233ac]	1683	for ( CandidateRef & candidate : candidates ) {
[9ea38de]	1684	satisfyAssertions( candidate, localSyms, satisfied, errors );
[396037d]	1685	}
	1686
	1687	// fail early if none such
	1688	if ( mode.failFast && satisfied.empty() ) {
	1689	std::ostringstream stream;
	1690	stream << "No alternatives with satisfiable assertions for " << expr << "\n";
	1691	for ( const auto& err : errors ) {
	1692	stream << err;
	1693	}
	1694	SemanticError( expr->location, stream.str() );
	1695	}
	1696
	1697	// reset candidates
[9d5089e]	1698	candidates = move( satisfied );
[396037d]	1699	}
	1700
	1701	if ( mode.prune ) {
	1702	// trim candidates to single best one
	1703	PRINT(
	1704	std::cerr << "alternatives before prune:" << std::endl;
	1705	print( std::cerr, candidates );
	1706	)
	1707
	1708	CandidateList pruned = pruneCandidates( candidates );
[2890212]	1709
[396037d]	1710	if ( mode.failFast && pruned.empty() ) {
	1711	std::ostringstream stream;
[d57e349]	1712	CandidateList winners = findMinCost( candidates );
	1713	stream << "Cannot choose between " << winners.size() << " alternatives for "
	1714	"expression\n";
	1715	ast::print( stream, expr );
	1716	stream << " Alternatives are:\n";
	1717	print( stream, winners, 1 );
	1718	SemanticError( expr->location, stream.str() );
[396037d]	1719	}
[d57e349]	1720
	1721	auto oldsize = candidates.size();
[9d5089e]	1722	candidates = move( pruned );
[d57e349]	1723
	1724	PRINT(
	1725	std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
	1726	)
	1727	PRINT(
[2890212]	1728	std::cerr << "there are " << candidates.size() << " alternatives after elimination"
[d57e349]	1729	<< std::endl;
	1730	)
[396037d]	1731	}
	1732
[2890212]	1733	// adjust types after pruning so that types substituted by pruneAlternatives are correctly
[d57e349]	1734	// adjusted
	1735	if ( mode.adjust ) {
	1736	for ( CandidateRef & r : candidates ) {
[2890212]	1737	r->expr = ast::mutate_field(
	1738	r->expr.get(), &ast::Expr::result,
[9ea38de]	1739	adjustExprType( r->expr->result, r->env, localSyms ) );
[d57e349]	1740	}
	1741	}
	1742
	1743	// Central location to handle gcc extension keyword, etc. for all expressions
	1744	for ( CandidateRef & r : candidates ) {
	1745	if ( r->expr->extension != expr->extension ) {
	1746	r->expr.get_and_mutate()->extension = expr->extension;
	1747	}
	1748	}
[99d4584]	1749	}
	1750
[2890212]	1751	std::vector< CandidateFinder > CandidateFinder::findSubExprs(
	1752	const std::vector< ast::ptr< ast::Expr > > & xs
[2773ab8]	1753	) {
	1754	std::vector< CandidateFinder > out;
	1755
[396037d]	1756	for ( const auto & x : xs ) {
[9ea38de]	1757	out.emplace_back( localSyms, env );
[396037d]	1758	out.back().find( x, ResolvMode::withAdjustment() );
[2890212]	1759
[396037d]	1760	PRINT(
	1761	std::cerr << "findSubExprs" << std::endl;
	1762	print( std::cerr, out.back().candidates );
	1763	)
	1764	}
[2773ab8]	1765
	1766	return out;
	1767	}
	1768
[99d4584]	1769	} // namespace ResolvExpr
	1770
	1771	// Local Variables: //
	1772	// tab-width: 4 //
	1773	// mode: c++ //
	1774	// compile-command: "make install" //
	1775	// End: //

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

Download in other formats: