Context Navigation

source: src/ResolvExpr/AlternativeFinder.cc @ 62423350

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

Last change on this file since 62423350 was 62423350, checked in by Rob Schluntz <rschlunt@…>, 7 years ago
Big push on designations and initialization: works with generic types, tuples, arrays, tests pass. Refactor guard_value_impl. Add list of declarations to TupleType?.
Property mode set to `100644`
File size: 54.7 KB

Rev	Line
[a32b204]	1	//
	2	// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
	3	//
	4	// The contents of this file are covered under the licence agreement in the
	5	// file "LICENCE" distributed with Cforall.
	6	//
[6ed1d4b]	7	// AlternativeFinder.cc --
[a32b204]	8	//
	9	// Author : Richard C. Bilson
	10	// Created On : Sat May 16 23:52:08 2015
[e04ef3a]	11	// Last Modified By : Peter A. Buhr
[615a096]	12	// Last Modified On : Fri Mar 17 09:14:17 2017
	13	// Update Count : 30
[a32b204]	14	//
	15
[51b7345]	16	#include <list>
	17	#include <iterator>
	18	#include <algorithm>
	19	#include <functional>
	20	#include <cassert>
[ebf5689]	21	#include <unordered_map>
	22	#include <utility>
	23	#include <vector>
[51b7345]	24
	25	#include "AlternativeFinder.h"
	26	#include "Alternative.h"
	27	#include "Cost.h"
	28	#include "typeops.h"
	29	#include "Unify.h"
	30	#include "RenameVars.h"
	31	#include "SynTree/Type.h"
	32	#include "SynTree/Declaration.h"
	33	#include "SynTree/Expression.h"
	34	#include "SynTree/Initializer.h"
	35	#include "SynTree/Visitor.h"
	36	#include "SymTab/Indexer.h"
	37	#include "SymTab/Mangler.h"
	38	#include "SynTree/TypeSubstitution.h"
	39	#include "SymTab/Validate.h"
[6eb8948]	40	#include "Tuples/Tuples.h"
[141b786]	41	#include "Tuples/Explode.h"
[d3b7937]	42	#include "Common/utility.h"
[70f89d00]	43	#include "InitTweak/InitTweak.h"
[77971f6]	44	#include "InitTweak/GenInit.h"
[85517ddb]	45	#include "ResolveTypeof.h"
[722617d]	46	#include "Resolver.h"
[51b7345]	47
[b87a5ed]	48	extern bool resolvep;
[6ed1d4b]	49	#define PRINT( text ) if ( resolvep ) { text }
[51b7345]	50	//#define DEBUG_COST
	51
	52	namespace ResolvExpr {
[a32b204]	53	Expression resolveInVoidContext( Expression expr, const SymTab::Indexer &indexer, TypeEnvironment &env ) {
	54	CastExpr *castToVoid = new CastExpr( expr );
	55
	56	AlternativeFinder finder( indexer, env );
	57	finder.findWithAdjustment( castToVoid );
	58
	59	// it's a property of the language that a cast expression has either 1 or 0 interpretations; if it has 0
	60	// interpretations, an exception has already been thrown.
	61	assert( finder.get_alternatives().size() == 1 );
	62	CastExpr newExpr = dynamic_cast< CastExpr >( finder.get_alternatives().front().expr );
	63	assert( newExpr );
	64	env = finder.get_alternatives().front().env;
	65	return newExpr->get_arg()->clone();
	66	}
	67
[908cc83]	68	Cost sumCost( const AltList &in ) {
	69	Cost total;
	70	for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
	71	total += i->cost;
	72	}
	73	return total;
	74	}
	75
[a32b204]	76	namespace {
	77	void printAlts( const AltList &list, std::ostream &os, int indent = 0 ) {
	78	for ( AltList::const_iterator i = list.begin(); i != list.end(); ++i ) {
	79	i->print( os, indent );
	80	os << std::endl;
	81	}
	82	}
[d9a0e76]	83
[a32b204]	84	void makeExprList( const AltList &in, std::list< Expression* > &out ) {
	85	for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
	86	out.push_back( i->expr->clone() );
	87	}
	88	}
[d9a0e76]	89
[a32b204]	90	struct PruneStruct {
	91	bool isAmbiguous;
	92	AltList::iterator candidate;
	93	PruneStruct() {}
	94	PruneStruct( AltList::iterator candidate ): isAmbiguous( false ), candidate( candidate ) {}
	95	};
	96
[0f19d763]	97	/// Prunes a list of alternatives down to those that have the minimum conversion cost for a given return type; skips ambiguous interpretations
[a32b204]	98	template< typename InputIterator, typename OutputIterator >
[d7dc824]	99	void pruneAlternatives( InputIterator begin, InputIterator end, OutputIterator out ) {
[a32b204]	100	// select the alternatives that have the minimum conversion cost for a particular set of result types
	101	std::map< std::string, PruneStruct > selected;
	102	for ( AltList::iterator candidate = begin; candidate != end; ++candidate ) {
	103	PruneStruct current( candidate );
	104	std::string mangleName;
[906e24d]	105	{
	106	Type * newType = candidate->expr->get_result()->clone();
[a32b204]	107	candidate->env.apply( newType );
[906e24d]	108	mangleName = SymTab::Mangler::mangle( newType );
[a32b204]	109	delete newType;
	110	}
	111	std::map< std::string, PruneStruct >::iterator mapPlace = selected.find( mangleName );
	112	if ( mapPlace != selected.end() ) {
	113	if ( candidate->cost < mapPlace->second.candidate->cost ) {
	114	PRINT(
[6ed1d4b]	115	std::cerr << "cost " << candidate->cost << " beats " << mapPlace->second.candidate->cost << std::endl;
[7c64920]	116	)
[0f19d763]	117	selected[ mangleName ] = current;
[a32b204]	118	} else if ( candidate->cost == mapPlace->second.candidate->cost ) {
	119	PRINT(
[6ed1d4b]	120	std::cerr << "marking ambiguous" << std::endl;
[7c64920]	121	)
[0f19d763]	122	mapPlace->second.isAmbiguous = true;
[a32b204]	123	}
	124	} else {
	125	selected[ mangleName ] = current;
	126	}
	127	}
[d9a0e76]	128
	129	PRINT(
[6ed1d4b]	130	std::cerr << "there are " << selected.size() << " alternatives before elimination" << std::endl;
[7c64920]	131	)
[a32b204]	132
[0f19d763]	133	// accept the alternatives that were unambiguous
	134	for ( std::map< std::string, PruneStruct >::iterator target = selected.begin(); target != selected.end(); ++target ) {
	135	if ( ! target->second.isAmbiguous ) {
	136	Alternative &alt = *target->second.candidate;
[906e24d]	137	alt.env.applyFree( alt.expr->get_result() );
[0f19d763]	138	*out++ = alt;
[a32b204]	139	}
[0f19d763]	140	}
[d9a0e76]	141	}
[a32b204]	142
	143	void renameTypes( Expression *expr ) {
[906e24d]	144	expr->get_result()->accept( global_renamer );
[e76acbe]	145	}
[d9a0e76]	146	}
	147
[a32b204]	148	template< typename InputIterator, typename OutputIterator >
	149	void AlternativeFinder::findSubExprs( InputIterator begin, InputIterator end, OutputIterator out ) {
	150	while ( begin != end ) {
	151	AlternativeFinder finder( indexer, env );
	152	finder.findWithAdjustment( *begin );
	153	// XXX either this
	154	//Designators::fixDesignations( finder, (*begin++)->get_argName() );
	155	// or XXX this
	156	begin++;
	157	PRINT(
[6ed1d4b]	158	std::cerr << "findSubExprs" << std::endl;
	159	printAlts( finder.alternatives, std::cerr );
[7c64920]	160	)
[0f19d763]	161	*out++ = finder;
[a32b204]	162	}
[d9a0e76]	163	}
	164
[a32b204]	165	AlternativeFinder::AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env )
	166	: indexer( indexer ), env( env ) {
[d9a0e76]	167	}
[51b7345]	168
[b6fe7e6]	169	void AlternativeFinder::find( Expression *expr, bool adjust, bool prune ) {
[a32b204]	170	expr->accept( *this );
	171	if ( alternatives.empty() ) {
	172	throw SemanticError( "No reasonable alternatives for expression ", expr );
	173	}
	174	for ( AltList::iterator i = alternatives.begin(); i != alternatives.end(); ++i ) {
	175	if ( adjust ) {
[906e24d]	176	adjustExprType( i->expr->get_result(), i->env, indexer );
[a32b204]	177	}
	178	}
[b6fe7e6]	179	if ( prune ) {
	180	PRINT(
	181	std::cerr << "alternatives before prune:" << std::endl;
	182	printAlts( alternatives, std::cerr );
	183	)
	184	AltList::iterator oldBegin = alternatives.begin();
[d7dc824]	185	pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives ) );
[b6fe7e6]	186	if ( alternatives.begin() == oldBegin ) {
	187	std::ostringstream stream;
[7933351]	188	stream << "Can't choose between " << alternatives.size() << " alternatives for expression ";
[b6fe7e6]	189	expr->print( stream );
	190	stream << "Alternatives are:";
	191	AltList winners;
	192	findMinCost( alternatives.begin(), alternatives.end(), back_inserter( winners ) );
	193	printAlts( winners, stream, 8 );
	194	throw SemanticError( stream.str() );
	195	}
	196	alternatives.erase( oldBegin, alternatives.end() );
	197	PRINT(
	198	std::cerr << "there are " << alternatives.size() << " alternatives after elimination" << std::endl;
	199	)
[a32b204]	200	}
[8e9cbb2]	201
[64ac636]	202	// Central location to handle gcc extension keyword, etc. for all expression types.
[8e9cbb2]	203	for ( Alternative &iter: alternatives ) {
	204	iter.expr->set_extension( expr->get_extension() );
[64ac636]	205	iter.expr->location = expr->location;
[8e9cbb2]	206	} // for
[0f19d763]	207	}
[d9a0e76]	208
[b6fe7e6]	209	void AlternativeFinder::findWithAdjustment( Expression *expr, bool prune ) {
	210	find( expr, true, prune );
[d9a0e76]	211	}
[a32b204]	212
[4b0f997]	213	void AlternativeFinder::addAnonConversions( const Alternative & alt ) {
	214	// adds anonymous member interpretations whenever an aggregate value type is seen.
	215	Expression * expr = alt.expr->clone();
	216	std::unique_ptr< Expression > manager( expr ); // RAII for expr
	217	alt.env.apply( expr->get_result() );
	218	if ( StructInstType structInst = dynamic_cast< StructInstType >( expr->get_result() ) ) {
	219	NameExpr nameExpr( "" );
	220	addAggMembers( structInst, expr, alt.cost+Cost( 0, 0, 1 ), alt.env, &nameExpr );
	221	} else if ( UnionInstType unionInst = dynamic_cast< UnionInstType >( expr->get_result() ) ) {
	222	NameExpr nameExpr( "" );
	223	addAggMembers( unionInst, expr, alt.cost+Cost( 0, 0, 1 ), alt.env, &nameExpr );
	224	} // if
	225	}
[77971f6]	226
[a32b204]	227	template< typename StructOrUnionType >
[add7117]	228	void AlternativeFinder::addAggMembers( StructOrUnionType aggInst, Expression expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) {
[bf32bb8]	229	// by this point, member must be a name expr
	230	NameExpr * nameExpr = safe_dynamic_cast< NameExpr * >( member );
	231	const std::string & name = nameExpr->get_name();
	232	std::list< Declaration* > members;
	233	aggInst->lookup( name, members );
[4b0f997]	234
[bf32bb8]	235	for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
	236	if ( DeclarationWithType dwt = dynamic_cast< DeclarationWithType >( *i ) ) {
[d9fa60a]	237	alternatives.push_back( Alternative( new MemberExpr( dwt, expr->clone() ), env, newCost ) );
[bf32bb8]	238	renameTypes( alternatives.back().expr );
[4b0f997]	239	addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a member expression.
[bf32bb8]	240	} else {
	241	assert( false );
[a32b204]	242	}
	243	}
[d9a0e76]	244	}
[a32b204]	245
[848ce71]	246	void AlternativeFinder::addTupleMembers( TupleType * tupleType, Expression expr, const Cost &newCost, const TypeEnvironment & env, Expression member ) {
	247	if ( ConstantExpr * constantExpr = dynamic_cast< ConstantExpr * >( member ) ) {
	248	// get the value of the constant expression as an int, must be between 0 and the length of the tuple type to have meaning
	249	// xxx - this should be improved by memoizing the value of constant exprs
	250	// during parsing and reusing that information here.
	251	std::stringstream ss( constantExpr->get_constant()->get_value() );
	252	int val;
	253	std::string tmp;
	254	if ( ss >> val && ! (ss >> tmp) ) {
	255	if ( val >= 0 && (unsigned int)val < tupleType->size() ) {
	256	alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
	257	} // if
	258	} // if
[141b786]	259	} else if ( NameExpr * nameExpr = dynamic_cast< NameExpr * >( member ) ) {
	260	// xxx - temporary hack until 0/1 are int constants
	261	if ( nameExpr->get_name() == "0" \|\| nameExpr->get_name() == "1" ) {
	262	std::stringstream ss( nameExpr->get_name() );
	263	int val;
	264	ss >> val;
	265	alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
	266	}
[848ce71]	267	} // if
	268	}
	269
[a32b204]	270	void AlternativeFinder::visit( ApplicationExpr *applicationExpr ) {
	271	alternatives.push_back( Alternative( applicationExpr->clone(), env, Cost::zero ) );
[d9a0e76]	272	}
	273
[a32b204]	274	Cost computeConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) {
[8f7cea1]	275	ApplicationExpr appExpr = safe_dynamic_cast< ApplicationExpr >( alt.expr );
[906e24d]	276	PointerType pointer = safe_dynamic_cast< PointerType >( appExpr->get_function()->get_result() );
[8f7cea1]	277	FunctionType function = safe_dynamic_cast< FunctionType >( pointer->get_base() );
[a32b204]	278
	279	Cost convCost( 0, 0, 0 );
	280	std::list< DeclarationWithType* >& formals = function->get_parameters();
	281	std::list< DeclarationWithType* >::iterator formal = formals.begin();
	282	std::list< Expression* >& actuals = appExpr->get_args();
[0362d42]	283
[a32b204]	284	for ( std::list< Expression* >::iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) {
[53e3b4a]	285	Type * actualType = (*actualExpr)->get_result();
[a32b204]	286	PRINT(
[6ed1d4b]	287	std::cerr << "actual expression:" << std::endl;
	288	(*actualExpr)->print( std::cerr, 8 );
	289	std::cerr << "--- results are" << std::endl;
[53e3b4a]	290	actualType->print( std::cerr, 8 );
[7c64920]	291	)
[a32b204]	292	Cost actualCost;
[53e3b4a]	293	if ( formal == formals.end() ) {
	294	if ( function->get_isVarArgs() ) {
	295	convCost += Cost( 1, 0, 0 );
	296	continue;
	297	} else {
	298	return Cost::infinity;
[7c64920]	299	}
[53e3b4a]	300	}
	301	Type * formalType = (*formal)->get_type();
	302	PRINT(
	303	std::cerr << std::endl << "converting ";
	304	actualType->print( std::cerr, 8 );
	305	std::cerr << std::endl << " to ";
	306	formalType->print( std::cerr, 8 );
	307	)
	308	Cost newCost = conversionCost( actualType, formalType, indexer, alt.env );
	309	PRINT(
	310	std::cerr << std::endl << "cost is" << newCost << std::endl;
	311	)
[a32b204]	312
[53e3b4a]	313	if ( newCost == Cost::infinity ) {
	314	return newCost;
[a32b204]	315	}
[53e3b4a]	316	convCost += newCost;
	317	actualCost += newCost;
[a32b204]	318	if ( actualCost != Cost( 0, 0, 0 ) ) {
[53e3b4a]	319	Type *newType = formalType->clone();
	320	alt.env.apply( newType );
	321	actualExpr = new CastExpr( actualExpr, newType );
[a32b204]	322	}
[53e3b4a]	323	convCost += Cost( 0, polyCost( formalType, alt.env, indexer ) + polyCost( actualType, alt.env, indexer ), 0 );
	324	++formal; // can't be in for-loop update because of the continue
[d9a0e76]	325	}
[a32b204]	326	if ( formal != formals.end() ) {
	327	return Cost::infinity;
[d9a0e76]	328	}
	329
[a32b204]	330	for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) {
	331	PRINT(
[6ed1d4b]	332	std::cerr << std::endl << "converting ";
	333	assert->second.actualType->print( std::cerr, 8 );
	334	std::cerr << std::endl << " to ";
	335	assert->second.formalType->print( std::cerr, 8 );
[02cea2d]	336	)
	337	Cost newCost = conversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env );
[a32b204]	338	PRINT(
[6ed1d4b]	339	std::cerr << std::endl << "cost of conversion is " << newCost << std::endl;
[02cea2d]	340	)
	341	if ( newCost == Cost::infinity ) {
	342	return newCost;
	343	}
[a32b204]	344	convCost += newCost;
	345	convCost += Cost( 0, polyCost( assert->second.formalType, alt.env, indexer ) + polyCost( assert->second.actualType, alt.env, indexer ), 0 );
	346	}
[d9a0e76]	347
[a32b204]	348	return convCost;
	349	}
[d9a0e76]	350
[8c84ebd]	351	/// Adds type variables to the open variable set and marks their assertions
[a32b204]	352	void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ) {
[8c49c0e]	353	for ( Type::ForallList::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
[2c57025]	354	unifiableVars[ (tyvar)->get_name() ] = TypeDecl::Data{ tyvar };
[a32b204]	355	for ( std::list< DeclarationWithType* >::iterator assert = (tyvar)->get_assertions().begin(); assert != (tyvar)->get_assertions().end(); ++assert ) {
[6c3a988f]	356	needAssertions[ *assert ].isUsed = true;
[a32b204]	357	}
[d9a0e76]	358	/// needAssertions.insert( needAssertions.end(), (tyvar)->get_assertions().begin(), (tyvar)->get_assertions().end() );
	359	}
	360	}
[a32b204]	361
[aefcc3b]	362	/// instantiate a single argument by matching actuals from [actualIt, actualEnd) against formalType,
	363	/// producing expression(s) in out and their total cost in cost.
	364	template< typename AltIterator, typename OutputIterator >
	365	bool instantiateArgument( Type * formalType, Initializer * defaultValue, AltIterator & actualIt, AltIterator actualEnd, OpenVarSet & openVars, TypeEnvironment & resultEnv, AssertionSet & resultNeed, AssertionSet & resultHave, const SymTab::Indexer & indexer, Cost & cost, OutputIterator out ) {
	366	if ( TupleType * tupleType = dynamic_cast< TupleType * >( formalType ) ) {
	367	// formalType is a TupleType - group actuals into a TupleExpr whose type unifies with the TupleType
[907eccb]	368	std::list< Expression * > exprs;
[aefcc3b]	369	for ( Type * type : *tupleType ) {
[907eccb]	370	if ( ! instantiateArgument( type, defaultValue, actualIt, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( exprs ) ) ) {
	371	deleteAll( exprs );
[aefcc3b]	372	return false;
	373	}
	374	}
[907eccb]	375	*out++ = new TupleExpr( exprs );
[4c8621ac]	376	} else if ( TypeInstType * ttype = Tuples::isTtype( formalType ) ) {
	377	// xxx - mixing default arguments with variadic??
	378	std::list< Expression * > exprs;
	379	for ( ; actualIt != actualEnd; ++actualIt ) {
	380	exprs.push_back( actualIt->expr->clone() );
	381	cost += actualIt->cost;
[53e3b4a]	382	}
[4c8621ac]	383	Expression * arg = nullptr;
	384	if ( exprs.size() == 1 && Tuples::isTtype( exprs.front()->get_result() ) ) {
	385	// the case where a ttype value is passed directly is special, e.g. for argument forwarding purposes
	386	// xxx - what if passing multiple arguments, last of which is ttype?
	387	// xxx - what would happen if unify was changed so that unifying tuple types flattened both before unifying lists? then pass in TupleType(ttype) below.
	388	arg = exprs.front();
	389	} else {
	390	arg = new TupleExpr( exprs );
	391	}
	392	assert( arg && arg->get_result() );
	393	if ( ! unify( ttype, arg->get_result(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
	394	return false;
	395	}
	396	*out++ = arg;
	397	} else if ( actualIt != actualEnd ) {
[aefcc3b]	398	// both actualType and formalType are atomic (non-tuple) types - if they unify
	399	// then accept actual as an argument, otherwise return false (fail to instantiate argument)
	400	Expression * actual = actualIt->expr;
	401	Type * actualType = actual->get_result();
	402	PRINT(
	403	std::cerr << "formal type is ";
	404	formalType->print( std::cerr );
	405	std::cerr << std::endl << "actual type is ";
	406	actualType->print( std::cerr );
	407	std::cerr << std::endl;
	408	)
	409	if ( ! unify( formalType, actualType, resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
	410	return false;
	411	}
	412	// move the expression from the alternative to the output iterator
	413	*out++ = actual;
	414	actualIt->expr = nullptr;
	415	cost += actualIt->cost;
	416	++actualIt;
	417	} else {
	418	// End of actuals - Handle default values
	419	if ( SingleInit si = dynamic_cast<SingleInit >( defaultValue )) {
[064cb18]	420	if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( si->get_value() ) ) {
	421	// so far, only constant expressions are accepted as default values
	422	if ( ConstantExpr cnstexpr = dynamic_cast<ConstantExpr >( castExpr->get_arg() ) ) {
	423	if ( Constant cnst = dynamic_cast<Constant >( cnstexpr->get_constant() ) ) {
	424	if ( unify( formalType, cnst->get_type(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
	425	*out++ = cnstexpr->clone();
	426	return true;
	427	} // if
[aefcc3b]	428	} // if
	429	} // if
[064cb18]	430	}
[aefcc3b]	431	} // if
	432	return false;
	433	} // if
	434	return true;
	435	}
	436
	437	bool AlternativeFinder::instantiateFunction( std::list< DeclarationWithType* >& formals, const AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave, AltList & out ) {
[a32b204]	438	simpleCombineEnvironments( actuals.begin(), actuals.end(), resultEnv );
	439	// make sure we don't widen any existing bindings
	440	for ( TypeEnvironment::iterator i = resultEnv.begin(); i != resultEnv.end(); ++i ) {
	441	i->allowWidening = false;
	442	}
	443	resultEnv.extractOpenVars( openVars );
	444
[aefcc3b]	445	// flatten actuals so that each actual has an atomic (non-tuple) type
	446	AltList exploded;
[77971f6]	447	Tuples::explode( actuals, indexer, back_inserter( exploded ) );
[aefcc3b]	448
	449	AltList::iterator actualExpr = exploded.begin();
	450	AltList::iterator actualEnd = exploded.end();
	451	for ( DeclarationWithType * formal : formals ) {
	452	// match flattened actuals with formal parameters - actuals will be grouped to match
	453	// with formals as appropriate
	454	Cost cost;
	455	std::list< Expression * > newExprs;
	456	ObjectDecl * obj = safe_dynamic_cast< ObjectDecl * >( formal );
	457	if ( ! instantiateArgument( obj->get_type(), obj->get_init(), actualExpr, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( newExprs ) ) ) {
	458	deleteAll( newExprs );
	459	return false;
[a32b204]	460	}
[aefcc3b]	461	// success - produce argument as a new alternative
	462	assert( newExprs.size() == 1 );
	463	out.push_back( Alternative( newExprs.front(), resultEnv, cost ) );
[a32b204]	464	}
[aefcc3b]	465	if ( actualExpr != actualEnd ) {
	466	// there are still actuals remaining, but we've run out of formal parameters to match against
	467	// this is okay only if the function is variadic
	468	if ( ! isVarArgs ) {
	469	return false;
	470	}
	471	out.splice( out.end(), exploded, actualExpr, actualEnd );
[a32b204]	472	}
	473	return true;
[d9a0e76]	474	}
[51b7345]	475
[89b686a]	476	// /// Map of declaration uniqueIds (intended to be the assertions in an AssertionSet) to their parents and the number of times they've been included
	477	//typedef std::unordered_map< UniqueId, std::unordered_map< UniqueId, unsigned > > AssertionParentSet;
[79970ed]	478
[a1d7679]	479	static const int recursionLimit = /10/ 4; ///< Limit to depth of recursion satisfaction
[89b686a]	480	//static const unsigned recursionParentLimit = 1; ///< Limit to the number of times an assertion can recursively use itself
[51b7345]	481
[a32b204]	482	void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) {
	483	for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) {
[6c3a988f]	484	if ( i->second.isUsed ) {
[a32b204]	485	i->first->accept( indexer );
	486	}
	487	}
[d9a0e76]	488	}
[79970ed]	489
[a32b204]	490	template< typename ForwardIterator, typename OutputIterator >
[79970ed]	491	void inferRecursive( ForwardIterator begin, ForwardIterator end, const Alternative &newAlt, OpenVarSet &openVars, const SymTab::Indexer &decls, const AssertionSet &newNeed, /const AssertionParentSet &needParents,/
[ebf5689]	492	int level, const SymTab::Indexer &indexer, OutputIterator out ) {
[a32b204]	493	if ( begin == end ) {
	494	if ( newNeed.empty() ) {
[6c3a988f]	495	PRINT(
	496	std::cerr << "all assertions satisfied, output alternative: ";
	497	newAlt.print( std::cerr );
	498	std::cerr << std::endl;
	499	);
[a32b204]	500	*out++ = newAlt;
	501	return;
	502	} else if ( level >= recursionLimit ) {
	503	throw SemanticError( "Too many recursive assertions" );
	504	} else {
	505	AssertionSet newerNeed;
	506	PRINT(
	507	std::cerr << "recursing with new set:" << std::endl;
	508	printAssertionSet( newNeed, std::cerr, 8 );
[7c64920]	509	)
[89b686a]	510	inferRecursive( newNeed.begin(), newNeed.end(), newAlt, openVars, decls, newerNeed, /needParents,/ level+1, indexer, out );
[a32b204]	511	return;
	512	}
	513	}
	514
	515	ForwardIterator cur = begin++;
[6c3a988f]	516	if ( ! cur->second.isUsed ) {
[89b686a]	517	inferRecursive( begin, end, newAlt, openVars, decls, newNeed, /needParents,/ level, indexer, out );
[7933351]	518	return; // xxx - should this continue? previously this wasn't here, and it looks like it should be
[a32b204]	519	}
	520	DeclarationWithType *curDecl = cur->first;
[7933351]	521
[d9a0e76]	522	PRINT(
[a32b204]	523	std::cerr << "inferRecursive: assertion is ";
	524	curDecl->print( std::cerr );
	525	std::cerr << std::endl;
[7c64920]	526	)
[0f19d763]	527	std::list< DeclarationWithType* > candidates;
[a32b204]	528	decls.lookupId( curDecl->get_name(), candidates );
[6ed1d4b]	529	/// if ( candidates.empty() ) { std::cerr << "no candidates!" << std::endl; }
[a32b204]	530	for ( std::list< DeclarationWithType* >::const_iterator candidate = candidates.begin(); candidate != candidates.end(); ++candidate ) {
	531	PRINT(
[6ed1d4b]	532	std::cerr << "inferRecursive: candidate is ";
	533	(*candidate)->print( std::cerr );
	534	std::cerr << std::endl;
[7c64920]	535	)
[79970ed]	536
[0f19d763]	537	AssertionSet newHave, newerNeed( newNeed );
[a32b204]	538	TypeEnvironment newEnv( newAlt.env );
	539	OpenVarSet newOpenVars( openVars );
	540	Type adjType = (candidate)->get_type()->clone();
	541	adjustExprType( adjType, newEnv, indexer );
	542	adjType->accept( global_renamer );
	543	PRINT(
	544	std::cerr << "unifying ";
	545	curDecl->get_type()->print( std::cerr );
	546	std::cerr << " with ";
	547	adjType->print( std::cerr );
	548	std::cerr << std::endl;
[7c64920]	549	)
[0f19d763]	550	if ( unify( curDecl->get_type(), adjType, newEnv, newerNeed, newHave, newOpenVars, indexer ) ) {
	551	PRINT(
	552	std::cerr << "success!" << std::endl;
[a32b204]	553	)
[0f19d763]	554	SymTab::Indexer newDecls( decls );
	555	addToIndexer( newHave, newDecls );
	556	Alternative newerAlt( newAlt );
	557	newerAlt.env = newEnv;
	558	assert( (*candidate)->get_uniqueId() );
[22cad76]	559	DeclarationWithType candDecl = static_cast< DeclarationWithType >( Declaration::declFromId( (*candidate)->get_uniqueId() ) );
[6c3a988f]	560
	561	// everything with an empty idChain was pulled in by the current assertion.
	562	// add current assertion's idChain + current assertion's ID so that the correct inferParameters can be found.
	563	for ( auto & a : newerNeed ) {
	564	if ( a.second.idChain.empty() ) {
	565	a.second.idChain = cur->second.idChain;
	566	a.second.idChain.push_back( curDecl->get_uniqueId() );
	567	}
	568	}
	569
[89b686a]	570	//AssertionParentSet newNeedParents( needParents );
[22cad76]	571	// skip repeatingly-self-recursive assertion satisfaction
[89b686a]	572	// DOESN'T WORK: grandchild nodes conflict with their cousins
	573	//if ( newNeedParents[ curDecl->get_uniqueId() ][ candDecl->get_uniqueId() ]++ > recursionParentLimit ) continue;
[22cad76]	574	Expression *varExpr = new VariableExpr( candDecl );
[906e24d]	575	delete varExpr->get_result();
	576	varExpr->set_result( adjType->clone() );
[0f19d763]	577	PRINT(
[6ed1d4b]	578	std::cerr << "satisfying assertion " << curDecl->get_uniqueId() << " ";
	579	curDecl->print( std::cerr );
	580	std::cerr << " with declaration " << (*candidate)->get_uniqueId() << " ";
	581	(*candidate)->print( std::cerr );
	582	std::cerr << std::endl;
[7c64920]	583	)
[0f19d763]	584	ApplicationExpr appExpr = static_cast< ApplicationExpr >( newerAlt.expr );
[6c3a988f]	585	// follow the current assertion's ID chain to find the correct set of inferred parameters to add the candidate to (i.e. the set of inferred parameters belonging to the entity which requested the assertion parameter).
	586	InferredParams * inferParameters = &appExpr->get_inferParams();
	587	for ( UniqueId id : cur->second.idChain ) {
	588	inferParameters = (*inferParameters)[ id ].inferParams.get();
	589	}
[0f19d763]	590	// XXX: this is a memory leak, but adjType can't be deleted because it might contain assertions
[6c3a988f]	591	(inferParameters)[ curDecl->get_uniqueId() ] = ParamEntry( (candidate)->get_uniqueId(), adjType->clone(), curDecl->get_type()->clone(), varExpr );
[89b686a]	592	inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, /newNeedParents,/ level, indexer, out );
[0f19d763]	593	} else {
	594	delete adjType;
	595	}
[a32b204]	596	}
[d9a0e76]	597	}
	598
[a32b204]	599	template< typename OutputIterator >
	600	void AlternativeFinder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) {
[d9a0e76]	601	// PRINT(
[6ed1d4b]	602	// std::cerr << "inferParameters: assertions needed are" << std::endl;
	603	// printAll( need, std::cerr, 8 );
[d9a0e76]	604	// )
[a32b204]	605	SymTab::Indexer decls( indexer );
[e4d829b]	606	// PRINT(
	607	// std::cerr << "============= original indexer" << std::endl;
	608	// indexer.print( std::cerr );
	609	// std::cerr << "============= new indexer" << std::endl;
	610	// decls.print( std::cerr );
	611	// )
[0f19d763]	612	addToIndexer( have, decls );
[a32b204]	613	AssertionSet newNeed;
[89b686a]	614	//AssertionParentSet needParents;
	615	inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, /needParents,/ 0, indexer, out );
[d9a0e76]	616	// PRINT(
[6ed1d4b]	617	// std::cerr << "declaration 14 is ";
[d9a0e76]	618	// Declaration::declFromId
	619	// *out++ = newAlt;
	620	// )
	621	}
	622
[a32b204]	623	template< typename OutputIterator >
[aefcc3b]	624	void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const AltList &actualAlt, OutputIterator out ) {
[a32b204]	625	OpenVarSet openVars;
	626	AssertionSet resultNeed, resultHave;
	627	TypeEnvironment resultEnv;
	628	makeUnifiableVars( funcType, openVars, resultNeed );
[7f623d6f]	629	resultEnv.add( funcType->get_forall() ); // add all type variables as open variables now so that those not used in the parameter list are still considered open
[aefcc3b]	630	AltList instantiatedActuals; // filled by instantiate function
[53e3b4a]	631	if ( targetType && ! targetType->isVoid() && ! funcType->get_returnVals().empty() ) {
[ea83e00a]	632	// attempt to narrow based on expected target type
	633	Type * returnType = funcType->get_returnVals().front()->get_type();
	634	if ( ! unify( returnType, targetType, resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
	635	// unification failed, don't pursue this alternative
	636	return;
	637	}
	638	}
	639
[aefcc3b]	640	if ( instantiateFunction( funcType->get_parameters(), actualAlt, funcType->get_isVarArgs(), openVars, resultEnv, resultNeed, resultHave, instantiatedActuals ) ) {
[a32b204]	641	ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
[aefcc3b]	642	Alternative newAlt( appExpr, resultEnv, sumCost( instantiatedActuals ) );
	643	makeExprList( instantiatedActuals, appExpr->get_args() );
[a32b204]	644	PRINT(
[6ed1d4b]	645	std::cerr << "need assertions:" << std::endl;
	646	printAssertionSet( resultNeed, std::cerr, 8 );
[7c64920]	647	)
[0f19d763]	648	inferParameters( resultNeed, resultHave, newAlt, openVars, out );
[d9a0e76]	649	}
	650	}
	651
[a32b204]	652	void AlternativeFinder::visit( UntypedExpr *untypedExpr ) {
	653	bool doneInit = false;
	654	AlternativeFinder funcOpFinder( indexer, env );
[d9a0e76]	655
[6ed1d4b]	656	AlternativeFinder funcFinder( indexer, env );
	657
	658	{
[70f89d00]	659	std::string fname = InitTweak::getFunctionName( untypedExpr );
	660	if ( fname == "&&" ) {
[2871210]	661	VoidType v = Type::Qualifiers(); // resolve to type void *
	662	PointerType pt( Type::Qualifiers(), v.clone() );
	663	UntypedExpr *vexpr = untypedExpr->clone();
[906e24d]	664	vexpr->set_result( pt.clone() );
[2871210]	665	alternatives.push_back( Alternative( vexpr, env, Cost()) );
[a32b204]	666	return;
	667	}
	668	}
[d9a0e76]	669
[a32b204]	670	funcFinder.findWithAdjustment( untypedExpr->get_function() );
	671	std::list< AlternativeFinder > argAlternatives;
	672	findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), back_inserter( argAlternatives ) );
[d9a0e76]	673
[a32b204]	674	std::list< AltList > possibilities;
	675	combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) );
[d9a0e76]	676
[5af62f1]	677	// take care of possible tuple assignments
	678	// if not tuple assignment, assignment is taken care of as a normal function call
	679	Tuples::handleTupleAssignment( *this, untypedExpr, possibilities );
[d9a0e76]	680
[a32b204]	681	AltList candidates;
[91b8a17]	682	SemanticError errors;
[a32b204]	683	for ( AltList::const_iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) {
[91b8a17]	684	try {
	685	PRINT(
	686	std::cerr << "working on alternative: " << std::endl;
	687	func->print( std::cerr, 8 );
	688	)
	689	// check if the type is pointer to function
	690	PointerType *pointer;
[906e24d]	691	if ( ( pointer = dynamic_cast< PointerType* >( func->expr->get_result() ) ) ) {
[91b8a17]	692	if ( FunctionType function = dynamic_cast< FunctionType >( pointer->get_base() ) ) {
	693	for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
	694	// XXX
	695	//Designators::check_alternative( function, *actualAlt );
	696	makeFunctionAlternatives( func, function, actualAlt, std::back_inserter( candidates ) );
	697	}
	698	} else if ( TypeInstType typeInst = dynamic_cast< TypeInstType >( pointer->get_base() ) ) {
	699	EqvClass eqvClass;
	700	if ( func->env.lookup( typeInst->get_name(), eqvClass ) && eqvClass.type ) {
	701	if ( FunctionType function = dynamic_cast< FunctionType >( eqvClass.type ) ) {
	702	for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
	703	makeFunctionAlternatives( func, function, actualAlt, std::back_inserter( candidates ) );
	704	} // for
	705	} // if
[a32b204]	706	} // if
	707	} // if
[91b8a17]	708	} else {
	709	// seek a function operator that's compatible
	710	if ( ! doneInit ) {
	711	doneInit = true;
	712	NameExpr *opExpr = new NameExpr( "?()" );
	713	try {
	714	funcOpFinder.findWithAdjustment( opExpr );
	715	} catch( SemanticError &e ) {
	716	// it's ok if there aren't any defined function ops
	717	}
	718	PRINT(
	719	std::cerr << "known function ops:" << std::endl;
	720	printAlts( funcOpFinder.alternatives, std::cerr, 8 );
	721	)
[a32b204]	722	}
	723
[91b8a17]	724	for ( AltList::const_iterator funcOp = funcOpFinder.alternatives.begin(); funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
	725	// check if the type is pointer to function
	726	PointerType *pointer;
[906e24d]	727	if ( ( pointer = dynamic_cast< PointerType* >( funcOp->expr->get_result() ) ) ) {
[91b8a17]	728	if ( FunctionType function = dynamic_cast< FunctionType >( pointer->get_base() ) ) {
	729	for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
	730	AltList currentAlt;
	731	currentAlt.push_back( *func );
	732	currentAlt.insert( currentAlt.end(), actualAlt->begin(), actualAlt->end() );
	733	makeFunctionAlternatives( *funcOp, function, currentAlt, std::back_inserter( candidates ) );
	734	} // for
	735	} // if
[a32b204]	736	} // if
[91b8a17]	737	} // for
	738	} // if
	739	} catch ( SemanticError &e ) {
	740	errors.append( e );
	741	}
[a32b204]	742	} // for
	743
[91b8a17]	744	// Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
	745	if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }
	746
[4b0f997]	747	// compute conversionsion costs
[a32b204]	748	for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) {
	749	Cost cvtCost = computeConversionCost( *withFunc, indexer );
	750
	751	PRINT(
[8f7cea1]	752	ApplicationExpr appExpr = safe_dynamic_cast< ApplicationExpr >( withFunc->expr );
[906e24d]	753	PointerType pointer = safe_dynamic_cast< PointerType >( appExpr->get_function()->get_result() );
[8f7cea1]	754	FunctionType function = safe_dynamic_cast< FunctionType >( pointer->get_base() );
[6ed1d4b]	755	std::cerr << "Case +++++++++++++" << std::endl;
	756	std::cerr << "formals are:" << std::endl;
	757	printAll( function->get_parameters(), std::cerr, 8 );
	758	std::cerr << "actuals are:" << std::endl;
	759	printAll( appExpr->get_args(), std::cerr, 8 );
	760	std::cerr << "bindings are:" << std::endl;
	761	withFunc->env.print( std::cerr, 8 );
	762	std::cerr << "cost of conversion is:" << cvtCost << std::endl;
[7c64920]	763	)
	764	if ( cvtCost != Cost::infinity ) {
	765	withFunc->cvtCost = cvtCost;
	766	alternatives.push_back( *withFunc );
	767	} // if
[a32b204]	768	} // for
[4b0f997]	769
[a32b204]	770	candidates.clear();
	771	candidates.splice( candidates.end(), alternatives );
	772
	773	findMinCost( candidates.begin(), candidates.end(), std::back_inserter( alternatives ) );
[ea83e00a]	774
[ca946a4]	775	// function may return struct or union value, in which case we need to add alternatives for implicit
	776	// conversions to each of the anonymous members, must happen after findMinCost since anon conversions
	777	// are never the cheapest expression
	778	for ( const Alternative & alt : alternatives ) {
	779	addAnonConversions( alt );
	780	}
	781
[ea83e00a]	782	if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
	783	// xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
	784	// target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
	785	// forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
	786	// const char * x = "hello world";
	787	// unsigned char ch = x[0];
	788	// Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
	789	// with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
	790	// fix this issue in a more robust way.
	791	targetType = nullptr;
	792	visit( untypedExpr );
	793	}
[a32b204]	794	}
	795
	796	bool isLvalue( Expression *expr ) {
[906e24d]	797	// xxx - recurse into tuples?
[615a096]	798	return expr->has_result() && expr->get_result()->get_lvalue();
[a32b204]	799	}
	800
	801	void AlternativeFinder::visit( AddressExpr *addressExpr ) {
	802	AlternativeFinder finder( indexer, env );
	803	finder.find( addressExpr->get_arg() );
	804	for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
	805	if ( isLvalue( i->expr ) ) {
	806	alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) );
	807	} // if
	808	} // for
	809	}
	810
[62423350]	811	Expression * restructureCast( Expression * argExpr, Type * toType ) {
	812	if ( argExpr->get_result()->size() > 1 && ! toType->isVoid() ) {
	813	// Argument expression is a tuple and the target type is not void. Cast each member of the tuple
	814	// to its corresponding target type, producing the tuple of those cast expressions. If there are
	815	// more components of the tuple than components in the target type, then excess components do not
	816	// come out in the result expression (but UniqueExprs ensure that side effects will still be done).
	817	if ( Tuples::maybeImpure( argExpr ) && ! dynamic_cast< UniqueExpr * >( argExpr ) ) {
	818	// expressions which may contain side effects require a single unique instance of the expression.
	819	argExpr = new UniqueExpr( argExpr );
	820	}
	821	std::list< Expression * > componentExprs;
	822	for ( unsigned int i = 0; i < toType->size(); i++ ) {
	823	// cast each component
	824	TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
	825	componentExprs.push_back( restructureCast( idx, toType->getComponent( i ) ) );
	826	}
	827	delete argExpr;
	828	assert( componentExprs.size() > 0 );
	829	// produce the tuple of casts
	830	return new TupleExpr( componentExprs );
	831	} else {
	832	// handle normally
	833	return new CastExpr( argExpr, toType->clone() );
	834	}
	835	}
	836
[a32b204]	837	void AlternativeFinder::visit( CastExpr *castExpr ) {
[906e24d]	838	Type *& toType = castExpr->get_result();
[7933351]	839	assert( toType );
[906e24d]	840	toType = resolveTypeof( toType, indexer );
	841	SymTab::validateType( toType, &indexer );
	842	adjustExprType( toType, env, indexer );
[a32b204]	843
	844	AlternativeFinder finder( indexer, env );
[7933351]	845	finder.targetType = toType;
[a32b204]	846	finder.findWithAdjustment( castExpr->get_arg() );
	847
	848	AltList candidates;
	849	for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
	850	AssertionSet needAssertions, haveAssertions;
	851	OpenVarSet openVars;
	852
	853	// It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a
	854	// cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results
	855	// that are cast directly. The candidate is invalid if it has fewer results than there are types to cast
	856	// to.
[906e24d]	857	int discardedValues = (*i).expr->get_result()->size() - castExpr->get_result()->size();
[a32b204]	858	if ( discardedValues < 0 ) continue;
[7933351]	859	// xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
	860	// allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
[adcdd2f]	861	// unification run for side-effects
[906e24d]	862	unify( castExpr->get_result(), (*i).expr->get_result(), i->env, needAssertions, haveAssertions, openVars, indexer );
	863	Cost thisCost = castCost( (*i).expr->get_result(), castExpr->get_result(), indexer, i->env );
[a32b204]	864	if ( thisCost != Cost::infinity ) {
	865	// count one safe conversion for each value that is thrown away
	866	thisCost += Cost( 0, 0, discardedValues );
[7933351]	867
[62423350]	868	candidates.push_back( Alternative( restructureCast( i->expr->clone(), toType ), i->env, i->cost, thisCost ) );
[a32b204]	869	} // if
	870	} // for
	871
	872	// findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
	873	// cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice
	874	// selects first based on argument cost, then on conversion cost.
	875	AltList minArgCost;
	876	findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
	877	findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
	878	}
	879
	880	void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) {
	881	AlternativeFinder funcFinder( indexer, env );
	882	funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
	883	for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
[906e24d]	884	if ( StructInstType structInst = dynamic_cast< StructInstType >( agg->expr->get_result() ) ) {
	885	addAggMembers( structInst, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
	886	} else if ( UnionInstType unionInst = dynamic_cast< UnionInstType >( agg->expr->get_result() ) ) {
	887	addAggMembers( unionInst, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
[848ce71]	888	} else if ( TupleType * tupleType = dynamic_cast< TupleType * >( agg->expr->get_result() ) ) {
	889	addTupleMembers( tupleType, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
[a32b204]	890	} // if
	891	} // for
	892	}
	893
	894	void AlternativeFinder::visit( MemberExpr *memberExpr ) {
	895	alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
	896	}
	897
	898	void AlternativeFinder::visit( NameExpr *nameExpr ) {
	899	std::list< DeclarationWithType* > declList;
	900	indexer.lookupId( nameExpr->get_name(), declList );
	901	PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; )
[0f19d763]	902	for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) {
	903	VariableExpr newExpr( *i, nameExpr->get_argName() );
	904	alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) );
	905	PRINT(
	906	std::cerr << "decl is ";
	907	(*i)->print( std::cerr );
	908	std::cerr << std::endl;
	909	std::cerr << "newExpr is ";
	910	newExpr.print( std::cerr );
	911	std::cerr << std::endl;
[7c64920]	912	)
[0f19d763]	913	renameTypes( alternatives.back().expr );
[4b0f997]	914	addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
[0f19d763]	915	} // for
[a32b204]	916	}
	917
	918	void AlternativeFinder::visit( VariableExpr *variableExpr ) {
[85517ddb]	919	// not sufficient to clone here, because variable's type may have changed
	920	// since the VariableExpr was originally created.
	921	alternatives.push_back( Alternative( new VariableExpr( variableExpr->get_var() ), env, Cost::zero ) );
[a32b204]	922	}
	923
	924	void AlternativeFinder::visit( ConstantExpr *constantExpr ) {
	925	alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
	926	}
	927
	928	void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) {
	929	if ( sizeofExpr->get_isType() ) {
[85517ddb]	930	// xxx - resolveTypeof?
[a32b204]	931	alternatives.push_back( Alternative( sizeofExpr->clone(), env, Cost::zero ) );
	932	} else {
	933	// find all alternatives for the argument to sizeof
	934	AlternativeFinder finder( indexer, env );
	935	finder.find( sizeofExpr->get_expr() );
	936	// find the lowest cost alternative among the alternatives, otherwise ambiguous
	937	AltList winners;
	938	findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
	939	if ( winners.size() != 1 ) {
	940	throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() );
	941	} // if
	942	// return the lowest cost alternative for the argument
	943	Alternative &choice = winners.front();
	944	alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
[47534159]	945	} // if
	946	}
	947
	948	void AlternativeFinder::visit( AlignofExpr *alignofExpr ) {
	949	if ( alignofExpr->get_isType() ) {
[85517ddb]	950	// xxx - resolveTypeof?
[47534159]	951	alternatives.push_back( Alternative( alignofExpr->clone(), env, Cost::zero ) );
	952	} else {
	953	// find all alternatives for the argument to sizeof
	954	AlternativeFinder finder( indexer, env );
	955	finder.find( alignofExpr->get_expr() );
	956	// find the lowest cost alternative among the alternatives, otherwise ambiguous
	957	AltList winners;
	958	findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
	959	if ( winners.size() != 1 ) {
	960	throw SemanticError( "Ambiguous expression in alignof operand: ", alignofExpr->get_expr() );
	961	} // if
	962	// return the lowest cost alternative for the argument
	963	Alternative &choice = winners.front();
	964	alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
[a32b204]	965	} // if
	966	}
	967
[2a4b088]	968	template< typename StructOrUnionType >
	969	void AlternativeFinder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
	970	std::list< Declaration* > members;
	971	aggInst->lookup( name, members );
	972	for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
	973	if ( DeclarationWithType dwt = dynamic_cast< DeclarationWithType >( *i ) ) {
[79970ed]	974	alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
[2a4b088]	975	renameTypes( alternatives.back().expr );
	976	} else {
	977	assert( false );
	978	}
	979	}
	980	}
[6ed1d4b]	981
[2a4b088]	982	void AlternativeFinder::visit( UntypedOffsetofExpr *offsetofExpr ) {
	983	AlternativeFinder funcFinder( indexer, env );
[85517ddb]	984	// xxx - resolveTypeof?
[2a4b088]	985	if ( StructInstType structInst = dynamic_cast< StructInstType >( offsetofExpr->get_type() ) ) {
	986	addOffsetof( structInst, offsetofExpr->get_member() );
	987	} else if ( UnionInstType unionInst = dynamic_cast< UnionInstType >( offsetofExpr->get_type() ) ) {
	988	addOffsetof( unionInst, offsetofExpr->get_member() );
	989	}
	990	}
[6ed1d4b]	991
[25a054f]	992	void AlternativeFinder::visit( OffsetofExpr *offsetofExpr ) {
	993	alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
[afc1045]	994	}
	995
	996	void AlternativeFinder::visit( OffsetPackExpr *offsetPackExpr ) {
	997	alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
[25a054f]	998	}
	999
[a32b204]	1000	void AlternativeFinder::resolveAttr( DeclarationWithType funcDecl, FunctionType function, Type *argType, const TypeEnvironment &env ) {
	1001	// assume no polymorphism
	1002	// assume no implicit conversions
	1003	assert( function->get_parameters().size() == 1 );
	1004	PRINT(
[6ed1d4b]	1005	std::cerr << "resolvAttr: funcDecl is ";
	1006	funcDecl->print( std::cerr );
	1007	std::cerr << " argType is ";
	1008	argType->print( std::cerr );
	1009	std::cerr << std::endl;
[7c64920]	1010	)
	1011	if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
	1012	alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) );
	1013	for ( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) {
[906e24d]	1014	alternatives.back().expr->set_result( (*i)->get_type()->clone() );
[7c64920]	1015	} // for
	1016	} // if
[a32b204]	1017	}
	1018
	1019	void AlternativeFinder::visit( AttrExpr *attrExpr ) {
	1020	// assume no 'pointer-to-attribute'
	1021	NameExpr nameExpr = dynamic_cast< NameExpr >( attrExpr->get_attr() );
	1022	assert( nameExpr );
	1023	std::list< DeclarationWithType* > attrList;
	1024	indexer.lookupId( nameExpr->get_name(), attrList );
	1025	if ( attrExpr->get_isType() \|\| attrExpr->get_expr() ) {
	1026	for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
	1027	// check if the type is function
	1028	if ( FunctionType function = dynamic_cast< FunctionType >( (*i)->get_type() ) ) {
	1029	// assume exactly one parameter
	1030	if ( function->get_parameters().size() == 1 ) {
	1031	if ( attrExpr->get_isType() ) {
	1032	resolveAttr( *i, function, attrExpr->get_type(), env );
	1033	} else {
	1034	AlternativeFinder finder( indexer, env );
	1035	finder.find( attrExpr->get_expr() );
	1036	for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
[906e24d]	1037	if ( choice->expr->get_result()->size() == 1 ) {
	1038	resolveAttr(*i, function, choice->expr->get_result(), choice->env );
[a32b204]	1039	} // fi
	1040	} // for
	1041	} // if
	1042	} // if
	1043	} // if
	1044	} // for
	1045	} else {
	1046	for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
	1047	VariableExpr newExpr( *i );
	1048	alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) );
	1049	renameTypes( alternatives.back().expr );
	1050	} // for
	1051	} // if
	1052	}
	1053
	1054	void AlternativeFinder::visit( LogicalExpr *logicalExpr ) {
	1055	AlternativeFinder firstFinder( indexer, env );
	1056	firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
	1057	for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
	1058	AlternativeFinder secondFinder( indexer, first->env );
	1059	secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
	1060	for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
	1061	LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() );
	1062	alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) );
[d9a0e76]	1063	}
	1064	}
	1065	}
[51b7345]	1066
[a32b204]	1067	void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) {
[32b8144]	1068	// find alternatives for condition
[a32b204]	1069	AlternativeFinder firstFinder( indexer, env );
	1070	firstFinder.findWithAdjustment( conditionalExpr->get_arg1() );
	1071	for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
[32b8144]	1072	// find alternatives for true expression
[a32b204]	1073	AlternativeFinder secondFinder( indexer, first->env );
	1074	secondFinder.findWithAdjustment( conditionalExpr->get_arg2() );
	1075	for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
[32b8144]	1076	// find alterantives for false expression
[a32b204]	1077	AlternativeFinder thirdFinder( indexer, second->env );
	1078	thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() );
	1079	for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) {
[32b8144]	1080	// unify true and false types, then infer parameters to produce new alternatives
[a32b204]	1081	OpenVarSet openVars;
	1082	AssertionSet needAssertions, haveAssertions;
	1083	Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost );
[668e971a]	1084	Type* commonType = nullptr;
[906e24d]	1085	if ( unify( second->expr->get_result(), third->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
[a32b204]	1086	ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() );
[906e24d]	1087	newExpr->set_result( commonType ? commonType : second->expr->get_result()->clone() );
[a32b204]	1088	newAlt.expr = newExpr;
	1089	inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
	1090	} // if
	1091	} // for
	1092	} // for
	1093	} // for
	1094	}
	1095
	1096	void AlternativeFinder::visit( CommaExpr *commaExpr ) {
	1097	TypeEnvironment newEnv( env );
	1098	Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
	1099	AlternativeFinder secondFinder( indexer, newEnv );
	1100	secondFinder.findWithAdjustment( commaExpr->get_arg2() );
	1101	for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) {
	1102	alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) );
	1103	} // for
	1104	delete newFirstArg;
	1105	}
	1106
[32b8144]	1107	void AlternativeFinder::visit( RangeExpr * rangeExpr ) {
	1108	// resolve low and high, accept alternatives whose low and high types unify
	1109	AlternativeFinder firstFinder( indexer, env );
	1110	firstFinder.findWithAdjustment( rangeExpr->get_low() );
	1111	for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
	1112	AlternativeFinder secondFinder( indexer, first->env );
	1113	secondFinder.findWithAdjustment( rangeExpr->get_high() );
	1114	for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
	1115	OpenVarSet openVars;
	1116	AssertionSet needAssertions, haveAssertions;
	1117	Alternative newAlt( 0, second->env, first->cost + second->cost );
	1118	Type* commonType = nullptr;
	1119	if ( unify( first->expr->get_result(), second->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
	1120	RangeExpr *newExpr = new RangeExpr( first->expr->clone(), second->expr->clone() );
	1121	newExpr->set_result( commonType ? commonType : first->expr->get_result()->clone() );
	1122	newAlt.expr = newExpr;
	1123	inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
	1124	} // if
	1125	} // for
	1126	} // for
	1127	}
	1128
[907eccb]	1129	void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) {
[a32b204]	1130	std::list< AlternativeFinder > subExprAlternatives;
	1131	findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) );
	1132	std::list< AltList > possibilities;
	1133	combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) );
	1134	for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) {
[907eccb]	1135	std::list< Expression * > exprs;
	1136	makeExprList( *i, exprs );
[a32b204]	1137
	1138	TypeEnvironment compositeEnv;
	1139	simpleCombineEnvironments( i->begin(), i->end(), compositeEnv );
[907eccb]	1140	alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) );
[a32b204]	1141	} // for
[d9a0e76]	1142	}
[dc2e7e0]	1143
[907eccb]	1144	void AlternativeFinder::visit( TupleExpr *tupleExpr ) {
	1145	alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
	1146	}
	1147
[dc2e7e0]	1148	void AlternativeFinder::visit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
	1149	alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
	1150	}
[b6fe7e6]	1151
	1152	void AlternativeFinder::visit( ConstructorExpr * ctorExpr ) {
	1153	AlternativeFinder finder( indexer, env );
	1154	// don't prune here, since it's guaranteed all alternatives will have the same type
	1155	// (giving the alternatives different types is half of the point of ConstructorExpr nodes)
	1156	finder.findWithAdjustment( ctorExpr->get_callExpr(), false );
	1157	for ( Alternative & alt : finder.alternatives ) {
	1158	alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
	1159	}
	1160	}
[8f7cea1]	1161
	1162	void AlternativeFinder::visit( TupleIndexExpr *tupleExpr ) {
	1163	alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
	1164	}
[aa8f9df]	1165
	1166	void AlternativeFinder::visit( TupleAssignExpr *tupleAssignExpr ) {
	1167	alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) );
	1168	}
[bf32bb8]	1169
	1170	void AlternativeFinder::visit( UniqueExpr *unqExpr ) {
	1171	AlternativeFinder finder( indexer, env );
	1172	finder.findWithAdjustment( unqExpr->get_expr() );
	1173	for ( Alternative & alt : finder.alternatives ) {
[141b786]	1174	// ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
[77971f6]	1175	UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
[141b786]	1176	alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
[bf32bb8]	1177	}
	1178	}
	1179
[722617d]	1180	void AlternativeFinder::visit( StmtExpr *stmtExpr ) {
	1181	StmtExpr * newStmtExpr = stmtExpr->clone();
	1182	ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
	1183	// xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
	1184	alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
	1185	}
	1186
[e4d829b]	1187	void AlternativeFinder::visit( UntypedInitExpr *initExpr ) {
[62423350]	1188	// handle each option like a cast
[e4d829b]	1189	AltList candidates;
[62423350]	1190	PRINT( std::cerr << "untyped init expr: " << initExpr << std::endl; )
[e4d829b]	1191	// O(N^2) checks of d-types with e-types
[62423350]	1192	for ( InitAlternative & initAlt : initExpr->get_initAlts() ) {
	1193	Type * toType = resolveTypeof( initAlt.type, indexer );
	1194	SymTab::validateType( toType, &indexer );
	1195	adjustExprType( toType, env, indexer );
	1196	// Ideally the call to findWithAdjustment could be moved out of the loop, but unfortunately it currently has to occur inside or else
	1197	// polymorphic return types are not properly bound to the initialization type, since return type variables are only open for the duration of resolving
	1198	// the UntypedExpr. This is only actually an issue in initialization contexts that allow more than one possible initialization type, but it is still suboptimal.
	1199	AlternativeFinder finder( indexer, env );
	1200	finder.targetType = toType;
	1201	finder.findWithAdjustment( initExpr->get_expr() );
	1202	for ( Alternative & alt : finder.get_alternatives() ) {
	1203	TypeEnvironment newEnv( alt.env );
[e4d829b]	1204	AssertionSet needAssertions, haveAssertions;
[62423350]	1205	OpenVarSet openVars; // find things in env that don't have a "representative type" and claim those are open vars?
	1206	PRINT( std::cerr << " @ " << toType << " " << initAlt.designation << std::endl; )
[e4d829b]	1207	// It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a
	1208	// cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results
	1209	// that are cast directly. The candidate is invalid if it has fewer results than there are types to cast
	1210	// to.
[62423350]	1211	int discardedValues = alt.expr->get_result()->size() - toType->size();
[e4d829b]	1212	if ( discardedValues < 0 ) continue;
	1213	// xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
	1214	// allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
	1215	// unification run for side-effects
[62423350]	1216	unify( toType, alt.expr->get_result(), newEnv, needAssertions, haveAssertions, openVars, indexer ); // xxx - do some inspecting on this line... why isn't result bound to initAlt.type??
[e4d829b]	1217
[62423350]	1218	Cost thisCost = castCost( alt.expr->get_result(), toType, indexer, newEnv );
[e4d829b]	1219	if ( thisCost != Cost::infinity ) {
	1220	// count one safe conversion for each value that is thrown away
	1221	thisCost += Cost( 0, 0, discardedValues );
[62423350]	1222	candidates.push_back( Alternative( new InitExpr( restructureCast( alt.expr->clone(), toType ), initAlt.designation->clone() ), newEnv, alt.cost, thisCost ) );
[e4d829b]	1223	}
	1224	}
	1225	}
	1226
	1227	// findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
	1228	// cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice
	1229	// selects first based on argument cost, then on conversion cost.
	1230	AltList minArgCost;
	1231	findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
	1232	findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
	1233	}
[51b7345]	1234	} // namespace ResolvExpr
[a32b204]	1235
	1236	// Local Variables: //
	1237	// tab-width: 4 //
	1238	// mode: c++ //
	1239	// compile-command: "make install" //
	1240	// End: //

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

Download in other formats: