Context Navigation

source: src/ResolvExpr/AlternativeFinder.cc @ 8f60f0b

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 8f60f0b was 722617d, checked in by Rob Schluntz <rschlunt@…>, 8 years ago
resolve StmtExprs?
Property mode set to `100644`
File size: 48.6 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
[8e9cbb2]	12	// Last Modified On : Mon Jul 4 17:02:51 2016
	13	// Update Count : 29
[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 >
	99	void pruneAlternatives( InputIterator begin, InputIterator end, OutputIterator out, const SymTab::Indexer &indexer ) {
	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();
	185	pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives ), indexer );
	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
	202	// Central location to handle gcc extension keyword for all expression types.
	203	for ( Alternative &iter: alternatives ) {
	204	iter.expr->set_extension( expr->get_extension() );
	205	} // for
[0f19d763]	206	}
[d9a0e76]	207
[b6fe7e6]	208	void AlternativeFinder::findWithAdjustment( Expression *expr, bool prune ) {
	209	find( expr, true, prune );
[d9a0e76]	210	}
[a32b204]	211
[77971f6]	212	// std::unordered_map< Expression , UniqueExpr > ;
	213
[a32b204]	214	template< typename StructOrUnionType >
[add7117]	215	void AlternativeFinder::addAggMembers( StructOrUnionType aggInst, Expression expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) {
[bf32bb8]	216	// by this point, member must be a name expr
	217	NameExpr * nameExpr = safe_dynamic_cast< NameExpr * >( member );
	218	const std::string & name = nameExpr->get_name();
	219	std::list< Declaration* > members;
	220	aggInst->lookup( name, members );
	221	for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
	222	if ( DeclarationWithType dwt = dynamic_cast< DeclarationWithType >( *i ) ) {
[d9fa60a]	223	alternatives.push_back( Alternative( new MemberExpr( dwt, expr->clone() ), env, newCost ) );
[bf32bb8]	224	renameTypes( alternatives.back().expr );
	225	} else {
	226	assert( false );
[a32b204]	227	}
	228	}
[d9a0e76]	229	}
[a32b204]	230
[848ce71]	231	void AlternativeFinder::addTupleMembers( TupleType * tupleType, Expression expr, const Cost &newCost, const TypeEnvironment & env, Expression member ) {
	232	if ( ConstantExpr * constantExpr = dynamic_cast< ConstantExpr * >( member ) ) {
	233	// get the value of the constant expression as an int, must be between 0 and the length of the tuple type to have meaning
	234	// xxx - this should be improved by memoizing the value of constant exprs
	235	// during parsing and reusing that information here.
	236	std::stringstream ss( constantExpr->get_constant()->get_value() );
	237	int val;
	238	std::string tmp;
	239	if ( ss >> val && ! (ss >> tmp) ) {
	240	if ( val >= 0 && (unsigned int)val < tupleType->size() ) {
	241	alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
	242	} // if
	243	} // if
[141b786]	244	} else if ( NameExpr * nameExpr = dynamic_cast< NameExpr * >( member ) ) {
	245	// xxx - temporary hack until 0/1 are int constants
	246	if ( nameExpr->get_name() == "0" \|\| nameExpr->get_name() == "1" ) {
	247	std::stringstream ss( nameExpr->get_name() );
	248	int val;
	249	ss >> val;
	250	alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
	251	}
[848ce71]	252	} // if
	253	}
	254
[a32b204]	255	void AlternativeFinder::visit( ApplicationExpr *applicationExpr ) {
	256	alternatives.push_back( Alternative( applicationExpr->clone(), env, Cost::zero ) );
[d9a0e76]	257	}
	258
[a32b204]	259	Cost computeConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) {
[8f7cea1]	260	ApplicationExpr appExpr = safe_dynamic_cast< ApplicationExpr >( alt.expr );
[906e24d]	261	PointerType pointer = safe_dynamic_cast< PointerType >( appExpr->get_function()->get_result() );
[8f7cea1]	262	FunctionType function = safe_dynamic_cast< FunctionType >( pointer->get_base() );
[a32b204]	263
	264	Cost convCost( 0, 0, 0 );
	265	std::list< DeclarationWithType* >& formals = function->get_parameters();
	266	std::list< DeclarationWithType* >::iterator formal = formals.begin();
	267	std::list< Expression* >& actuals = appExpr->get_args();
[0362d42]	268
[e76acbe]	269	std::list< Type * > formalTypes;
	270	std::list< Type * >::iterator formalType = formalTypes.end();
	271
[a32b204]	272	for ( std::list< Expression* >::iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) {
[e76acbe]	273
[a32b204]	274	PRINT(
[6ed1d4b]	275	std::cerr << "actual expression:" << std::endl;
	276	(*actualExpr)->print( std::cerr, 8 );
	277	std::cerr << "--- results are" << std::endl;
[906e24d]	278	(*actualExpr)->get_result()->print( std::cerr, 8 );
[7c64920]	279	)
	280	std::list< DeclarationWithType* >::iterator startFormal = formal;
[a32b204]	281	Cost actualCost;
[906e24d]	282	std::list< Type * > flatActualTypes;
	283	flatten( (*actualExpr)->get_result(), back_inserter( flatActualTypes ) );
[aa8f9df]	284	for ( std::list< Type* >::iterator actualType = flatActualTypes.begin(); actualType != flatActualTypes.end(); ++actualType ) {
	285
[e76acbe]	286
	287	// tuple handling code
	288	if ( formalType == formalTypes.end() ) {
	289	// the type of the formal parameter may be a tuple type. To make this easier to work with,
	290	// flatten the tuple type and traverse the resulting list of types, incrementing the formal
	291	// iterator once its types have been extracted. Once a particular formal parameter's type has
	292	// been exhausted load the next formal parameter's type.
	293	if ( formal == formals.end() ) {
	294	if ( function->get_isVarArgs() ) {
	295	convCost += Cost( 1, 0, 0 );
	296	break;
	297	} else {
	298	return Cost::infinity;
	299	}
[a32b204]	300	}
[e76acbe]	301	formalTypes.clear();
	302	flatten( (*formal)->get_type(), back_inserter( formalTypes ) );
	303	formalType = formalTypes.begin();
	304	++formal;
[a32b204]	305	}
[e76acbe]	306
[a32b204]	307	PRINT(
[6ed1d4b]	308	std::cerr << std::endl << "converting ";
[0362d42]	309	(*actualType)->print( std::cerr, 8 );
[6ed1d4b]	310	std::cerr << std::endl << " to ";
[7933351]	311	(*formalType)->print( std::cerr, 8 );
[7c64920]	312	)
[e76acbe]	313	Cost newCost = conversionCost( actualType, formalType, indexer, alt.env );
[a32b204]	314	PRINT(
[6ed1d4b]	315	std::cerr << std::endl << "cost is" << newCost << std::endl;
[7c64920]	316	)
[a32b204]	317
[7c64920]	318	if ( newCost == Cost::infinity ) {
	319	return newCost;
	320	}
[a32b204]	321	convCost += newCost;
	322	actualCost += newCost;
	323
[e76acbe]	324	convCost += Cost( 0, polyCost( formalType, alt.env, indexer ) + polyCost( actualType, alt.env, indexer ), 0 );
[a32b204]	325
[e76acbe]	326	formalType++;
[a32b204]	327	}
	328	if ( actualCost != Cost( 0, 0, 0 ) ) {
	329	std::list< DeclarationWithType* >::iterator startFormalPlusOne = startFormal;
	330	startFormalPlusOne++;
	331	if ( formal == startFormalPlusOne ) {
	332	// not a tuple type
	333	Type newType = (startFormal)->get_type()->clone();
	334	alt.env.apply( newType );
	335	actualExpr = new CastExpr( actualExpr, newType );
	336	} else {
	337	TupleType *newType = new TupleType( Type::Qualifiers() );
	338	for ( std::list< DeclarationWithType* >::iterator i = startFormal; i != formal; ++i ) {
	339	newType->get_types().push_back( (*i)->get_type()->clone() );
	340	}
	341	alt.env.apply( newType );
	342	actualExpr = new CastExpr( actualExpr, newType );
	343	}
	344	}
	345
[d9a0e76]	346	}
[a32b204]	347	if ( formal != formals.end() ) {
	348	return Cost::infinity;
[d9a0e76]	349	}
	350
[a32b204]	351	for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) {
	352	PRINT(
[6ed1d4b]	353	std::cerr << std::endl << "converting ";
	354	assert->second.actualType->print( std::cerr, 8 );
	355	std::cerr << std::endl << " to ";
	356	assert->second.formalType->print( std::cerr, 8 );
[02cea2d]	357	)
	358	Cost newCost = conversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env );
[a32b204]	359	PRINT(
[6ed1d4b]	360	std::cerr << std::endl << "cost of conversion is " << newCost << std::endl;
[02cea2d]	361	)
	362	if ( newCost == Cost::infinity ) {
	363	return newCost;
	364	}
[a32b204]	365	convCost += newCost;
[d9a0e76]	366
[a32b204]	367	convCost += Cost( 0, polyCost( assert->second.formalType, alt.env, indexer ) + polyCost( assert->second.actualType, alt.env, indexer ), 0 );
	368	}
[d9a0e76]	369
[a32b204]	370	return convCost;
	371	}
[d9a0e76]	372
[8c84ebd]	373	/// Adds type variables to the open variable set and marks their assertions
[a32b204]	374	void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ) {
[8c49c0e]	375	for ( Type::ForallList::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
[2c57025]	376	unifiableVars[ (tyvar)->get_name() ] = TypeDecl::Data{ tyvar };
[a32b204]	377	for ( std::list< DeclarationWithType* >::iterator assert = (tyvar)->get_assertions().begin(); assert != (tyvar)->get_assertions().end(); ++assert ) {
	378	needAssertions[ *assert ] = true;
	379	}
[d9a0e76]	380	/// needAssertions.insert( needAssertions.end(), (tyvar)->get_assertions().begin(), (tyvar)->get_assertions().end() );
	381	}
	382	}
[a32b204]	383
[aefcc3b]	384	/// instantiate a single argument by matching actuals from [actualIt, actualEnd) against formalType,
	385	/// producing expression(s) in out and their total cost in cost.
	386	template< typename AltIterator, typename OutputIterator >
	387	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 ) {
	388	if ( TupleType * tupleType = dynamic_cast< TupleType * >( formalType ) ) {
	389	// formalType is a TupleType - group actuals into a TupleExpr whose type unifies with the TupleType
	390	TupleExpr * tupleExpr = new TupleExpr();
	391	for ( Type * type : *tupleType ) {
	392	if ( ! instantiateArgument( type, defaultValue, actualIt, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( tupleExpr->get_exprs() ) ) ) {
	393	delete tupleExpr;
	394	return false;
	395	}
	396	}
	397	tupleExpr->set_result( Tuples::makeTupleType( tupleExpr->get_exprs() ) );
	398	*out++ = tupleExpr;
	399	} else if ( actualIt != actualEnd ) {
	400	// both actualType and formalType are atomic (non-tuple) types - if they unify
	401	// then accept actual as an argument, otherwise return false (fail to instantiate argument)
	402	Expression * actual = actualIt->expr;
	403	Type * actualType = actual->get_result();
	404	PRINT(
	405	std::cerr << "formal type is ";
	406	formalType->print( std::cerr );
	407	std::cerr << std::endl << "actual type is ";
	408	actualType->print( std::cerr );
	409	std::cerr << std::endl;
	410	)
	411	if ( ! unify( formalType, actualType, resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
	412	return false;
	413	}
	414	// move the expression from the alternative to the output iterator
	415	*out++ = actual;
	416	actualIt->expr = nullptr;
	417	cost += actualIt->cost;
	418	++actualIt;
	419	} else {
	420	// End of actuals - Handle default values
	421	if ( SingleInit si = dynamic_cast<SingleInit >( defaultValue )) {
	422	// so far, only constant expressions are accepted as default values
	423	if ( ConstantExpr cnstexpr = dynamic_cast<ConstantExpr >( si->get_value()) ) {
	424	if ( Constant cnst = dynamic_cast<Constant >( cnstexpr->get_constant() ) ) {
	425	if ( unify( formalType, cnst->get_type(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
	426	// xxx - Don't know if this is right
	427	*out++ = cnstexpr->clone();
	428	return true;
	429	} // if
	430	} // if
	431	} // if
	432	} // if
	433	return false;
	434	} // if
	435	return true;
	436	}
	437
	438	bool AlternativeFinder::instantiateFunction( std::list< DeclarationWithType* >& formals, const AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave, AltList & out ) {
[a32b204]	439	simpleCombineEnvironments( actuals.begin(), actuals.end(), resultEnv );
	440	// make sure we don't widen any existing bindings
	441	for ( TypeEnvironment::iterator i = resultEnv.begin(); i != resultEnv.end(); ++i ) {
	442	i->allowWidening = false;
	443	}
	444	resultEnv.extractOpenVars( openVars );
	445
[aefcc3b]	446	// flatten actuals so that each actual has an atomic (non-tuple) type
	447	AltList exploded;
[77971f6]	448	Tuples::explode( actuals, indexer, back_inserter( exploded ) );
[aefcc3b]	449
	450	AltList::iterator actualExpr = exploded.begin();
	451	AltList::iterator actualEnd = exploded.end();
	452	for ( DeclarationWithType * formal : formals ) {
	453	// match flattened actuals with formal parameters - actuals will be grouped to match
	454	// with formals as appropriate
	455	Cost cost;
	456	std::list< Expression * > newExprs;
	457	ObjectDecl * obj = safe_dynamic_cast< ObjectDecl * >( formal );
	458	if ( ! instantiateArgument( obj->get_type(), obj->get_init(), actualExpr, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( newExprs ) ) ) {
	459	deleteAll( newExprs );
	460	return false;
[a32b204]	461	}
[aefcc3b]	462	// success - produce argument as a new alternative
	463	assert( newExprs.size() == 1 );
	464	out.push_back( Alternative( newExprs.front(), resultEnv, cost ) );
[a32b204]	465	}
[aefcc3b]	466	if ( actualExpr != actualEnd ) {
	467	// there are still actuals remaining, but we've run out of formal parameters to match against
	468	// this is okay only if the function is variadic
	469	if ( ! isVarArgs ) {
	470	return false;
	471	}
	472	out.splice( out.end(), exploded, actualExpr, actualEnd );
[a32b204]	473	}
	474	return true;
[d9a0e76]	475	}
[51b7345]	476
[89b686a]	477	// /// Map of declaration uniqueIds (intended to be the assertions in an AssertionSet) to their parents and the number of times they've been included
	478	//typedef std::unordered_map< UniqueId, std::unordered_map< UniqueId, unsigned > > AssertionParentSet;
[79970ed]	479
[a1d7679]	480	static const int recursionLimit = /10/ 4; ///< Limit to depth of recursion satisfaction
[89b686a]	481	//static const unsigned recursionParentLimit = 1; ///< Limit to the number of times an assertion can recursively use itself
[51b7345]	482
[a32b204]	483	void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) {
	484	for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) {
	485	if ( i->second == true ) {
	486	i->first->accept( indexer );
	487	}
	488	}
[d9a0e76]	489	}
[79970ed]	490
[a32b204]	491	template< typename ForwardIterator, typename OutputIterator >
[79970ed]	492	void inferRecursive( ForwardIterator begin, ForwardIterator end, const Alternative &newAlt, OpenVarSet &openVars, const SymTab::Indexer &decls, const AssertionSet &newNeed, /const AssertionParentSet &needParents,/
[ebf5689]	493	int level, const SymTab::Indexer &indexer, OutputIterator out ) {
[a32b204]	494	if ( begin == end ) {
	495	if ( newNeed.empty() ) {
	496	*out++ = newAlt;
	497	return;
	498	} else if ( level >= recursionLimit ) {
	499	throw SemanticError( "Too many recursive assertions" );
	500	} else {
	501	AssertionSet newerNeed;
	502	PRINT(
	503	std::cerr << "recursing with new set:" << std::endl;
	504	printAssertionSet( newNeed, std::cerr, 8 );
[7c64920]	505	)
[89b686a]	506	inferRecursive( newNeed.begin(), newNeed.end(), newAlt, openVars, decls, newerNeed, /needParents,/ level+1, indexer, out );
[a32b204]	507	return;
	508	}
	509	}
	510
	511	ForwardIterator cur = begin++;
	512	if ( ! cur->second ) {
[89b686a]	513	inferRecursive( begin, end, newAlt, openVars, decls, newNeed, /needParents,/ level, indexer, out );
[7933351]	514	return; // xxx - should this continue? previously this wasn't here, and it looks like it should be
[a32b204]	515	}
	516	DeclarationWithType *curDecl = cur->first;
[7933351]	517
[d9a0e76]	518	PRINT(
[a32b204]	519	std::cerr << "inferRecursive: assertion is ";
	520	curDecl->print( std::cerr );
	521	std::cerr << std::endl;
[7c64920]	522	)
[0f19d763]	523	std::list< DeclarationWithType* > candidates;
[a32b204]	524	decls.lookupId( curDecl->get_name(), candidates );
[6ed1d4b]	525	/// if ( candidates.empty() ) { std::cerr << "no candidates!" << std::endl; }
[a32b204]	526	for ( std::list< DeclarationWithType* >::const_iterator candidate = candidates.begin(); candidate != candidates.end(); ++candidate ) {
	527	PRINT(
[6ed1d4b]	528	std::cerr << "inferRecursive: candidate is ";
	529	(*candidate)->print( std::cerr );
	530	std::cerr << std::endl;
[7c64920]	531	)
[79970ed]	532
[0f19d763]	533	AssertionSet newHave, newerNeed( newNeed );
[a32b204]	534	TypeEnvironment newEnv( newAlt.env );
	535	OpenVarSet newOpenVars( openVars );
	536	Type adjType = (candidate)->get_type()->clone();
	537	adjustExprType( adjType, newEnv, indexer );
	538	adjType->accept( global_renamer );
	539	PRINT(
	540	std::cerr << "unifying ";
	541	curDecl->get_type()->print( std::cerr );
	542	std::cerr << " with ";
	543	adjType->print( std::cerr );
	544	std::cerr << std::endl;
[7c64920]	545	)
[0f19d763]	546	if ( unify( curDecl->get_type(), adjType, newEnv, newerNeed, newHave, newOpenVars, indexer ) ) {
	547	PRINT(
	548	std::cerr << "success!" << std::endl;
[a32b204]	549	)
[0f19d763]	550	SymTab::Indexer newDecls( decls );
	551	addToIndexer( newHave, newDecls );
	552	Alternative newerAlt( newAlt );
	553	newerAlt.env = newEnv;
	554	assert( (*candidate)->get_uniqueId() );
[22cad76]	555	DeclarationWithType candDecl = static_cast< DeclarationWithType >( Declaration::declFromId( (*candidate)->get_uniqueId() ) );
[89b686a]	556	//AssertionParentSet newNeedParents( needParents );
[22cad76]	557	// skip repeatingly-self-recursive assertion satisfaction
[89b686a]	558	// DOESN'T WORK: grandchild nodes conflict with their cousins
	559	//if ( newNeedParents[ curDecl->get_uniqueId() ][ candDecl->get_uniqueId() ]++ > recursionParentLimit ) continue;
[22cad76]	560	Expression *varExpr = new VariableExpr( candDecl );
[906e24d]	561	delete varExpr->get_result();
	562	varExpr->set_result( adjType->clone() );
[0f19d763]	563	PRINT(
[6ed1d4b]	564	std::cerr << "satisfying assertion " << curDecl->get_uniqueId() << " ";
	565	curDecl->print( std::cerr );
	566	std::cerr << " with declaration " << (*candidate)->get_uniqueId() << " ";
	567	(*candidate)->print( std::cerr );
	568	std::cerr << std::endl;
[7c64920]	569	)
[0f19d763]	570	ApplicationExpr appExpr = static_cast< ApplicationExpr >( newerAlt.expr );
	571	// XXX: this is a memory leak, but adjType can't be deleted because it might contain assertions
	572	appExpr->get_inferParams()[ curDecl->get_uniqueId() ] = ParamEntry( (*candidate)->get_uniqueId(), adjType->clone(), curDecl->get_type()->clone(), varExpr );
[89b686a]	573	inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, /newNeedParents,/ level, indexer, out );
[0f19d763]	574	} else {
	575	delete adjType;
	576	}
[a32b204]	577	}
[d9a0e76]	578	}
	579
[a32b204]	580	template< typename OutputIterator >
	581	void AlternativeFinder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) {
[d9a0e76]	582	// PRINT(
[6ed1d4b]	583	// std::cerr << "inferParameters: assertions needed are" << std::endl;
	584	// printAll( need, std::cerr, 8 );
[d9a0e76]	585	// )
[a32b204]	586	SymTab::Indexer decls( indexer );
	587	PRINT(
[6ed1d4b]	588	std::cerr << "============= original indexer" << std::endl;
	589	indexer.print( std::cerr );
	590	std::cerr << "============= new indexer" << std::endl;
	591	decls.print( std::cerr );
[7c64920]	592	)
[0f19d763]	593	addToIndexer( have, decls );
[a32b204]	594	AssertionSet newNeed;
[89b686a]	595	//AssertionParentSet needParents;
	596	inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, /needParents,/ 0, indexer, out );
[d9a0e76]	597	// PRINT(
[6ed1d4b]	598	// std::cerr << "declaration 14 is ";
[d9a0e76]	599	// Declaration::declFromId
	600	// *out++ = newAlt;
	601	// )
	602	}
	603
[a32b204]	604	template< typename OutputIterator >
[aefcc3b]	605	void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const AltList &actualAlt, OutputIterator out ) {
[a32b204]	606	OpenVarSet openVars;
	607	AssertionSet resultNeed, resultHave;
	608	TypeEnvironment resultEnv;
	609	makeUnifiableVars( funcType, openVars, resultNeed );
[aefcc3b]	610	AltList instantiatedActuals; // filled by instantiate function
[ea83e00a]	611	if ( targetType && ! targetType->isVoid() ) {
	612	// attempt to narrow based on expected target type
	613	Type * returnType = funcType->get_returnVals().front()->get_type();
	614	if ( ! unify( returnType, targetType, resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
	615	// unification failed, don't pursue this alternative
	616	return;
	617	}
	618	}
	619
[aefcc3b]	620	if ( instantiateFunction( funcType->get_parameters(), actualAlt, funcType->get_isVarArgs(), openVars, resultEnv, resultNeed, resultHave, instantiatedActuals ) ) {
[a32b204]	621	ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
[aefcc3b]	622	Alternative newAlt( appExpr, resultEnv, sumCost( instantiatedActuals ) );
	623	makeExprList( instantiatedActuals, appExpr->get_args() );
[a32b204]	624	PRINT(
[6ed1d4b]	625	std::cerr << "need assertions:" << std::endl;
	626	printAssertionSet( resultNeed, std::cerr, 8 );
[7c64920]	627	)
[0f19d763]	628	inferParameters( resultNeed, resultHave, newAlt, openVars, out );
[d9a0e76]	629	}
	630	}
	631
[a32b204]	632	void AlternativeFinder::visit( UntypedExpr *untypedExpr ) {
	633	bool doneInit = false;
	634	AlternativeFinder funcOpFinder( indexer, env );
[d9a0e76]	635
[6ed1d4b]	636	AlternativeFinder funcFinder( indexer, env );
	637
	638	{
[70f89d00]	639	std::string fname = InitTweak::getFunctionName( untypedExpr );
	640	if ( fname == "&&" ) {
[2871210]	641	VoidType v = Type::Qualifiers(); // resolve to type void *
	642	PointerType pt( Type::Qualifiers(), v.clone() );
	643	UntypedExpr *vexpr = untypedExpr->clone();
[906e24d]	644	vexpr->set_result( pt.clone() );
[2871210]	645	alternatives.push_back( Alternative( vexpr, env, Cost()) );
[a32b204]	646	return;
	647	}
	648	}
[d9a0e76]	649
[a32b204]	650	funcFinder.findWithAdjustment( untypedExpr->get_function() );
	651	std::list< AlternativeFinder > argAlternatives;
	652	findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), back_inserter( argAlternatives ) );
[d9a0e76]	653
[a32b204]	654	std::list< AltList > possibilities;
	655	combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) );
[d9a0e76]	656
[5af62f1]	657	// take care of possible tuple assignments
	658	// if not tuple assignment, assignment is taken care of as a normal function call
	659	Tuples::handleTupleAssignment( *this, untypedExpr, possibilities );
[d9a0e76]	660
[a32b204]	661	AltList candidates;
[91b8a17]	662	SemanticError errors;
[a32b204]	663	for ( AltList::const_iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) {
[91b8a17]	664	try {
	665	PRINT(
	666	std::cerr << "working on alternative: " << std::endl;
	667	func->print( std::cerr, 8 );
	668	)
	669	// check if the type is pointer to function
	670	PointerType *pointer;
[906e24d]	671	if ( ( pointer = dynamic_cast< PointerType* >( func->expr->get_result() ) ) ) {
[91b8a17]	672	if ( FunctionType function = dynamic_cast< FunctionType >( pointer->get_base() ) ) {
	673	for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
	674	// XXX
	675	//Designators::check_alternative( function, *actualAlt );
	676	makeFunctionAlternatives( func, function, actualAlt, std::back_inserter( candidates ) );
	677	}
	678	} else if ( TypeInstType typeInst = dynamic_cast< TypeInstType >( pointer->get_base() ) ) {
	679	EqvClass eqvClass;
	680	if ( func->env.lookup( typeInst->get_name(), eqvClass ) && eqvClass.type ) {
	681	if ( FunctionType function = dynamic_cast< FunctionType >( eqvClass.type ) ) {
	682	for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
	683	makeFunctionAlternatives( func, function, actualAlt, std::back_inserter( candidates ) );
	684	} // for
	685	} // if
[a32b204]	686	} // if
	687	} // if
[91b8a17]	688	} else {
	689	// seek a function operator that's compatible
	690	if ( ! doneInit ) {
	691	doneInit = true;
	692	NameExpr *opExpr = new NameExpr( "?()" );
	693	try {
	694	funcOpFinder.findWithAdjustment( opExpr );
	695	} catch( SemanticError &e ) {
	696	// it's ok if there aren't any defined function ops
	697	}
	698	PRINT(
	699	std::cerr << "known function ops:" << std::endl;
	700	printAlts( funcOpFinder.alternatives, std::cerr, 8 );
	701	)
[a32b204]	702	}
	703
[91b8a17]	704	for ( AltList::const_iterator funcOp = funcOpFinder.alternatives.begin(); funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
	705	// check if the type is pointer to function
	706	PointerType *pointer;
[906e24d]	707	if ( ( pointer = dynamic_cast< PointerType* >( funcOp->expr->get_result() ) ) ) {
[91b8a17]	708	if ( FunctionType function = dynamic_cast< FunctionType >( pointer->get_base() ) ) {
	709	for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
	710	AltList currentAlt;
	711	currentAlt.push_back( *func );
	712	currentAlt.insert( currentAlt.end(), actualAlt->begin(), actualAlt->end() );
	713	makeFunctionAlternatives( *funcOp, function, currentAlt, std::back_inserter( candidates ) );
	714	} // for
	715	} // if
[a32b204]	716	} // if
[91b8a17]	717	} // for
	718	} // if
	719	} catch ( SemanticError &e ) {
	720	errors.append( e );
	721	}
[a32b204]	722	} // for
	723
[91b8a17]	724	// Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
	725	if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }
	726
[a32b204]	727	for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) {
	728	Cost cvtCost = computeConversionCost( *withFunc, indexer );
	729
	730	PRINT(
[8f7cea1]	731	ApplicationExpr appExpr = safe_dynamic_cast< ApplicationExpr >( withFunc->expr );
[906e24d]	732	PointerType pointer = safe_dynamic_cast< PointerType >( appExpr->get_function()->get_result() );
[8f7cea1]	733	FunctionType function = safe_dynamic_cast< FunctionType >( pointer->get_base() );
[6ed1d4b]	734	std::cerr << "Case +++++++++++++" << std::endl;
	735	std::cerr << "formals are:" << std::endl;
	736	printAll( function->get_parameters(), std::cerr, 8 );
	737	std::cerr << "actuals are:" << std::endl;
	738	printAll( appExpr->get_args(), std::cerr, 8 );
	739	std::cerr << "bindings are:" << std::endl;
	740	withFunc->env.print( std::cerr, 8 );
	741	std::cerr << "cost of conversion is:" << cvtCost << std::endl;
[7c64920]	742	)
	743	if ( cvtCost != Cost::infinity ) {
	744	withFunc->cvtCost = cvtCost;
	745	alternatives.push_back( *withFunc );
	746	} // if
[a32b204]	747	} // for
	748	candidates.clear();
	749	candidates.splice( candidates.end(), alternatives );
	750
	751	findMinCost( candidates.begin(), candidates.end(), std::back_inserter( alternatives ) );
[ea83e00a]	752
	753	if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
	754	// xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
	755	// target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
	756	// forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
	757	// const char * x = "hello world";
	758	// unsigned char ch = x[0];
	759	// Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
	760	// with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
	761	// fix this issue in a more robust way.
	762	targetType = nullptr;
	763	visit( untypedExpr );
	764	}
[a32b204]	765	}
	766
	767	bool isLvalue( Expression *expr ) {
[906e24d]	768	// xxx - recurse into tuples?
	769	return expr->has_result() && expr->get_result()->get_isLvalue();
[a32b204]	770	}
	771
	772	void AlternativeFinder::visit( AddressExpr *addressExpr ) {
	773	AlternativeFinder finder( indexer, env );
	774	finder.find( addressExpr->get_arg() );
	775	for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
	776	if ( isLvalue( i->expr ) ) {
	777	alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) );
	778	} // if
	779	} // for
	780	}
	781
	782	void AlternativeFinder::visit( CastExpr *castExpr ) {
[906e24d]	783	Type *& toType = castExpr->get_result();
[7933351]	784	assert( toType );
[906e24d]	785	toType = resolveTypeof( toType, indexer );
	786	SymTab::validateType( toType, &indexer );
	787	adjustExprType( toType, env, indexer );
[a32b204]	788
	789	AlternativeFinder finder( indexer, env );
[7933351]	790	finder.targetType = toType;
[a32b204]	791	finder.findWithAdjustment( castExpr->get_arg() );
	792
	793	AltList candidates;
	794	for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
	795	AssertionSet needAssertions, haveAssertions;
	796	OpenVarSet openVars;
	797
	798	// It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a
	799	// cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results
	800	// that are cast directly. The candidate is invalid if it has fewer results than there are types to cast
	801	// to.
[906e24d]	802	int discardedValues = (*i).expr->get_result()->size() - castExpr->get_result()->size();
[a32b204]	803	if ( discardedValues < 0 ) continue;
[7933351]	804	// xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
	805	// allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
[adcdd2f]	806	// unification run for side-effects
[906e24d]	807	unify( castExpr->get_result(), (*i).expr->get_result(), i->env, needAssertions, haveAssertions, openVars, indexer );
	808	Cost thisCost = castCost( (*i).expr->get_result(), castExpr->get_result(), indexer, i->env );
[a32b204]	809	if ( thisCost != Cost::infinity ) {
	810	// count one safe conversion for each value that is thrown away
	811	thisCost += Cost( 0, 0, discardedValues );
[7933351]	812
	813	Expression * argExpr = i->expr->clone();
	814	if ( argExpr->get_result()->size() > 1 && ! castExpr->get_result()->isVoid() ) {
	815	// Argument expression is a tuple and the target type is not void. Cast each member of the tuple
	816	// to its corresponding target type, producing the tuple of those cast expressions. If there are
	817	// more components of the tuple than components in the target type, then excess components do not
	818	// come out in the result expression (but UniqueExprs ensure that side effects will still be done).
	819	if ( Tuples::maybeImpure( argExpr ) && ! dynamic_cast< UniqueExpr * >( argExpr ) ) {
	820	// expressions which may contain side effects require a single unique instance of the expression.
	821	argExpr = new UniqueExpr( argExpr );
	822	}
	823	std::list< Expression * > componentExprs;
	824	for ( unsigned int i = 0; i < castExpr->get_result()->size(); i++ ) {
	825	// cast each component
	826	TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
	827	componentExprs.push_back( new CastExpr( idx, castExpr->get_result()->getComponent( i )->clone() ) );
	828	}
	829	delete argExpr;
	830	assert( componentExprs.size() > 0 );
	831	// produce the tuple of casts
	832	candidates.push_back( Alternative( new TupleExpr( componentExprs ), i->env, i->cost, thisCost ) );
	833	} else {
	834	// handle normally
	835	candidates.push_back( Alternative( new CastExpr( argExpr->clone(), toType->clone() ), i->env, i->cost, thisCost ) );
	836	}
[a32b204]	837	} // if
	838	} // for
	839
	840	// findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
	841	// cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice
	842	// selects first based on argument cost, then on conversion cost.
	843	AltList minArgCost;
	844	findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
	845	findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
	846	}
	847
	848	void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) {
	849	AlternativeFinder funcFinder( indexer, env );
	850	funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
	851	for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
[906e24d]	852	if ( StructInstType structInst = dynamic_cast< StructInstType >( agg->expr->get_result() ) ) {
	853	addAggMembers( structInst, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
	854	} else if ( UnionInstType unionInst = dynamic_cast< UnionInstType >( agg->expr->get_result() ) ) {
	855	addAggMembers( unionInst, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
[848ce71]	856	} else if ( TupleType * tupleType = dynamic_cast< TupleType * >( agg->expr->get_result() ) ) {
	857	addTupleMembers( tupleType, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
[a32b204]	858	} // if
	859	} // for
	860	}
	861
	862	void AlternativeFinder::visit( MemberExpr *memberExpr ) {
	863	alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
	864	}
	865
	866	void AlternativeFinder::visit( NameExpr *nameExpr ) {
	867	std::list< DeclarationWithType* > declList;
	868	indexer.lookupId( nameExpr->get_name(), declList );
	869	PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; )
[0f19d763]	870	for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) {
	871	VariableExpr newExpr( *i, nameExpr->get_argName() );
	872	alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) );
	873	PRINT(
	874	std::cerr << "decl is ";
	875	(*i)->print( std::cerr );
	876	std::cerr << std::endl;
	877	std::cerr << "newExpr is ";
	878	newExpr.print( std::cerr );
	879	std::cerr << std::endl;
[7c64920]	880	)
[0f19d763]	881	renameTypes( alternatives.back().expr );
	882	if ( StructInstType structInst = dynamic_cast< StructInstType >( (*i)->get_type() ) ) {
[3b58d91]	883	NameExpr nameExpr( "" );
[add7117]	884	addAggMembers( structInst, &newExpr, Cost( 0, 0, 1 ), env, &nameExpr );
[0f19d763]	885	} else if ( UnionInstType unionInst = dynamic_cast< UnionInstType >( (*i)->get_type() ) ) {
[3b58d91]	886	NameExpr nameExpr( "" );
[add7117]	887	addAggMembers( unionInst, &newExpr, Cost( 0, 0, 1 ), env, &nameExpr );
[0f19d763]	888	} // if
	889	} // for
[a32b204]	890	}
	891
	892	void AlternativeFinder::visit( VariableExpr *variableExpr ) {
[85517ddb]	893	// not sufficient to clone here, because variable's type may have changed
	894	// since the VariableExpr was originally created.
	895	alternatives.push_back( Alternative( new VariableExpr( variableExpr->get_var() ), env, Cost::zero ) );
[a32b204]	896	}
	897
	898	void AlternativeFinder::visit( ConstantExpr *constantExpr ) {
	899	alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
	900	}
	901
	902	void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) {
	903	if ( sizeofExpr->get_isType() ) {
[85517ddb]	904	// xxx - resolveTypeof?
[a32b204]	905	alternatives.push_back( Alternative( sizeofExpr->clone(), env, Cost::zero ) );
	906	} else {
	907	// find all alternatives for the argument to sizeof
	908	AlternativeFinder finder( indexer, env );
	909	finder.find( sizeofExpr->get_expr() );
	910	// find the lowest cost alternative among the alternatives, otherwise ambiguous
	911	AltList winners;
	912	findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
	913	if ( winners.size() != 1 ) {
	914	throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() );
	915	} // if
	916	// return the lowest cost alternative for the argument
	917	Alternative &choice = winners.front();
	918	alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
[47534159]	919	} // if
	920	}
	921
	922	void AlternativeFinder::visit( AlignofExpr *alignofExpr ) {
	923	if ( alignofExpr->get_isType() ) {
[85517ddb]	924	// xxx - resolveTypeof?
[47534159]	925	alternatives.push_back( Alternative( alignofExpr->clone(), env, Cost::zero ) );
	926	} else {
	927	// find all alternatives for the argument to sizeof
	928	AlternativeFinder finder( indexer, env );
	929	finder.find( alignofExpr->get_expr() );
	930	// find the lowest cost alternative among the alternatives, otherwise ambiguous
	931	AltList winners;
	932	findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
	933	if ( winners.size() != 1 ) {
	934	throw SemanticError( "Ambiguous expression in alignof operand: ", alignofExpr->get_expr() );
	935	} // if
	936	// return the lowest cost alternative for the argument
	937	Alternative &choice = winners.front();
	938	alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
[a32b204]	939	} // if
	940	}
	941
[2a4b088]	942	template< typename StructOrUnionType >
	943	void AlternativeFinder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
	944	std::list< Declaration* > members;
	945	aggInst->lookup( name, members );
	946	for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
	947	if ( DeclarationWithType dwt = dynamic_cast< DeclarationWithType >( *i ) ) {
[79970ed]	948	alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
[2a4b088]	949	renameTypes( alternatives.back().expr );
	950	} else {
	951	assert( false );
	952	}
	953	}
	954	}
[6ed1d4b]	955
[2a4b088]	956	void AlternativeFinder::visit( UntypedOffsetofExpr *offsetofExpr ) {
	957	AlternativeFinder funcFinder( indexer, env );
[85517ddb]	958	// xxx - resolveTypeof?
[2a4b088]	959	if ( StructInstType structInst = dynamic_cast< StructInstType >( offsetofExpr->get_type() ) ) {
	960	addOffsetof( structInst, offsetofExpr->get_member() );
	961	} else if ( UnionInstType unionInst = dynamic_cast< UnionInstType >( offsetofExpr->get_type() ) ) {
	962	addOffsetof( unionInst, offsetofExpr->get_member() );
	963	}
	964	}
[6ed1d4b]	965
[25a054f]	966	void AlternativeFinder::visit( OffsetofExpr *offsetofExpr ) {
	967	alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
[afc1045]	968	}
	969
	970	void AlternativeFinder::visit( OffsetPackExpr *offsetPackExpr ) {
	971	alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
[25a054f]	972	}
	973
[a32b204]	974	void AlternativeFinder::resolveAttr( DeclarationWithType funcDecl, FunctionType function, Type *argType, const TypeEnvironment &env ) {
	975	// assume no polymorphism
	976	// assume no implicit conversions
	977	assert( function->get_parameters().size() == 1 );
	978	PRINT(
[6ed1d4b]	979	std::cerr << "resolvAttr: funcDecl is ";
	980	funcDecl->print( std::cerr );
	981	std::cerr << " argType is ";
	982	argType->print( std::cerr );
	983	std::cerr << std::endl;
[7c64920]	984	)
	985	if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
	986	alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) );
	987	for ( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) {
[906e24d]	988	alternatives.back().expr->set_result( (*i)->get_type()->clone() );
[7c64920]	989	} // for
	990	} // if
[a32b204]	991	}
	992
	993	void AlternativeFinder::visit( AttrExpr *attrExpr ) {
	994	// assume no 'pointer-to-attribute'
	995	NameExpr nameExpr = dynamic_cast< NameExpr >( attrExpr->get_attr() );
	996	assert( nameExpr );
	997	std::list< DeclarationWithType* > attrList;
	998	indexer.lookupId( nameExpr->get_name(), attrList );
	999	if ( attrExpr->get_isType() \|\| attrExpr->get_expr() ) {
	1000	for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
	1001	// check if the type is function
	1002	if ( FunctionType function = dynamic_cast< FunctionType >( (*i)->get_type() ) ) {
	1003	// assume exactly one parameter
	1004	if ( function->get_parameters().size() == 1 ) {
	1005	if ( attrExpr->get_isType() ) {
	1006	resolveAttr( *i, function, attrExpr->get_type(), env );
	1007	} else {
	1008	AlternativeFinder finder( indexer, env );
	1009	finder.find( attrExpr->get_expr() );
	1010	for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
[906e24d]	1011	if ( choice->expr->get_result()->size() == 1 ) {
	1012	resolveAttr(*i, function, choice->expr->get_result(), choice->env );
[a32b204]	1013	} // fi
	1014	} // for
	1015	} // if
	1016	} // if
	1017	} // if
	1018	} // for
	1019	} else {
	1020	for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
	1021	VariableExpr newExpr( *i );
	1022	alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) );
	1023	renameTypes( alternatives.back().expr );
	1024	} // for
	1025	} // if
	1026	}
	1027
	1028	void AlternativeFinder::visit( LogicalExpr *logicalExpr ) {
	1029	AlternativeFinder firstFinder( indexer, env );
	1030	firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
	1031	for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
	1032	AlternativeFinder secondFinder( indexer, first->env );
	1033	secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
	1034	for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
	1035	LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() );
	1036	alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) );
[d9a0e76]	1037	}
	1038	}
	1039	}
[51b7345]	1040
[a32b204]	1041	void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) {
	1042	AlternativeFinder firstFinder( indexer, env );
	1043	firstFinder.findWithAdjustment( conditionalExpr->get_arg1() );
	1044	for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
	1045	AlternativeFinder secondFinder( indexer, first->env );
	1046	secondFinder.findWithAdjustment( conditionalExpr->get_arg2() );
	1047	for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
	1048	AlternativeFinder thirdFinder( indexer, second->env );
	1049	thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() );
	1050	for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) {
	1051	OpenVarSet openVars;
	1052	AssertionSet needAssertions, haveAssertions;
	1053	Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost );
[668e971a]	1054	Type* commonType = nullptr;
[906e24d]	1055	if ( unify( second->expr->get_result(), third->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
[a32b204]	1056	ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() );
[906e24d]	1057	newExpr->set_result( commonType ? commonType : second->expr->get_result()->clone() );
[a32b204]	1058	newAlt.expr = newExpr;
	1059	inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
	1060	} // if
	1061	} // for
	1062	} // for
	1063	} // for
	1064	}
	1065
	1066	void AlternativeFinder::visit( CommaExpr *commaExpr ) {
	1067	TypeEnvironment newEnv( env );
	1068	Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
	1069	AlternativeFinder secondFinder( indexer, newEnv );
	1070	secondFinder.findWithAdjustment( commaExpr->get_arg2() );
	1071	for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) {
	1072	alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) );
	1073	} // for
	1074	delete newFirstArg;
	1075	}
	1076
	1077	void AlternativeFinder::visit( TupleExpr *tupleExpr ) {
	1078	std::list< AlternativeFinder > subExprAlternatives;
	1079	findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) );
	1080	std::list< AltList > possibilities;
	1081	combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) );
	1082	for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) {
	1083	TupleExpr *newExpr = new TupleExpr;
	1084	makeExprList( *i, newExpr->get_exprs() );
[3c13c03]	1085	newExpr->set_result( Tuples::makeTupleType( newExpr->get_exprs() ) );
[a32b204]	1086
	1087	TypeEnvironment compositeEnv;
	1088	simpleCombineEnvironments( i->begin(), i->end(), compositeEnv );
	1089	alternatives.push_back( Alternative( newExpr, compositeEnv, sumCost( *i ) ) );
	1090	} // for
[d9a0e76]	1091	}
[dc2e7e0]	1092
	1093	void AlternativeFinder::visit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
	1094	alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
	1095	}
[b6fe7e6]	1096
	1097	void AlternativeFinder::visit( ConstructorExpr * ctorExpr ) {
	1098	AlternativeFinder finder( indexer, env );
	1099	// don't prune here, since it's guaranteed all alternatives will have the same type
	1100	// (giving the alternatives different types is half of the point of ConstructorExpr nodes)
	1101	finder.findWithAdjustment( ctorExpr->get_callExpr(), false );
	1102	for ( Alternative & alt : finder.alternatives ) {
	1103	alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
	1104	}
	1105	}
[8f7cea1]	1106
	1107	void AlternativeFinder::visit( TupleIndexExpr *tupleExpr ) {
	1108	alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
	1109	}
[aa8f9df]	1110
	1111	void AlternativeFinder::visit( TupleAssignExpr *tupleAssignExpr ) {
	1112	alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) );
	1113	}
[bf32bb8]	1114
	1115	void AlternativeFinder::visit( UniqueExpr *unqExpr ) {
	1116	AlternativeFinder finder( indexer, env );
	1117	finder.findWithAdjustment( unqExpr->get_expr() );
	1118	for ( Alternative & alt : finder.alternatives ) {
[141b786]	1119	// ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
[77971f6]	1120	UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
[141b786]	1121	alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
[bf32bb8]	1122	}
	1123	}
	1124
[722617d]	1125	void AlternativeFinder::visit( StmtExpr *stmtExpr ) {
	1126	StmtExpr * newStmtExpr = stmtExpr->clone();
	1127	ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
	1128	// xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
	1129	alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
	1130	}
	1131
[51b7345]	1132	} // namespace ResolvExpr
[a32b204]	1133
	1134	// Local Variables: //
	1135	// tab-width: 4 //
	1136	// mode: c++ //
	1137	// compile-command: "make install" //
	1138	// End: //

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

Download in other formats: