Context Navigation

source: src/ResolvExpr/CandidateFinder.cpp @ c8e4d2f8

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum

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

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

Download in other formats: