Context Navigation

source: src/ResolvExpr/CandidateFinder.cpp@ 3bc69f2

Visit:

ADT ast-experimental enum pthread-emulation qualifiedEnum

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

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

Download in other formats: