Context Navigation

source: src/ResolvExpr/AlternativeFinder.cc @ 24bc651

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 24bc651 was b6fe7e6, checked in by Rob Schluntz <rschlunt@…>, 8 years ago
make constructor expressions work, fix bug with using the wrong TypeEnvironment? on member exprs, remove many unnecessary ctor/dtors from the prelude
Property mode set to `100644`
File size: 43.1 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"
	40	#include "Tuples/TupleAssignment.h"
	41	#include "Tuples/NameMatcher.h"
[d3b7937]	42	#include "Common/utility.h"
[70f89d00]	43	#include "InitTweak/InitTweak.h"
[85517ddb]	44	#include "ResolveTypeof.h"
[51b7345]	45
[b87a5ed]	46	extern bool resolvep;
[6ed1d4b]	47	#define PRINT( text ) if ( resolvep ) { text }
[51b7345]	48	//#define DEBUG_COST
	49
	50	namespace ResolvExpr {
[a32b204]	51	Expression resolveInVoidContext( Expression expr, const SymTab::Indexer &indexer, TypeEnvironment &env ) {
	52	CastExpr *castToVoid = new CastExpr( expr );
	53
	54	AlternativeFinder finder( indexer, env );
	55	finder.findWithAdjustment( castToVoid );
	56
	57	// it's a property of the language that a cast expression has either 1 or 0 interpretations; if it has 0
	58	// interpretations, an exception has already been thrown.
	59	assert( finder.get_alternatives().size() == 1 );
	60	CastExpr newExpr = dynamic_cast< CastExpr >( finder.get_alternatives().front().expr );
	61	assert( newExpr );
	62	env = finder.get_alternatives().front().env;
	63	return newExpr->get_arg()->clone();
	64	}
	65
	66	namespace {
	67	void printAlts( const AltList &list, std::ostream &os, int indent = 0 ) {
	68	for ( AltList::const_iterator i = list.begin(); i != list.end(); ++i ) {
	69	i->print( os, indent );
	70	os << std::endl;
	71	}
	72	}
[d9a0e76]	73
[a32b204]	74	void makeExprList( const AltList &in, std::list< Expression* > &out ) {
	75	for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
	76	out.push_back( i->expr->clone() );
	77	}
	78	}
[d9a0e76]	79
[a32b204]	80	Cost sumCost( const AltList &in ) {
	81	Cost total;
	82	for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
	83	total += i->cost;
	84	}
	85	return total;
	86	}
[d9a0e76]	87
[a32b204]	88	struct PruneStruct {
	89	bool isAmbiguous;
	90	AltList::iterator candidate;
	91	PruneStruct() {}
	92	PruneStruct( AltList::iterator candidate ): isAmbiguous( false ), candidate( candidate ) {}
	93	};
	94
[0f19d763]	95	/// Prunes a list of alternatives down to those that have the minimum conversion cost for a given return type; skips ambiguous interpretations
[a32b204]	96	template< typename InputIterator, typename OutputIterator >
	97	void pruneAlternatives( InputIterator begin, InputIterator end, OutputIterator out, const SymTab::Indexer &indexer ) {
	98	// select the alternatives that have the minimum conversion cost for a particular set of result types
	99	std::map< std::string, PruneStruct > selected;
	100	for ( AltList::iterator candidate = begin; candidate != end; ++candidate ) {
	101	PruneStruct current( candidate );
	102	std::string mangleName;
	103	for ( std::list< Type* >::const_iterator retType = candidate->expr->get_results().begin(); retType != candidate->expr->get_results().end(); ++retType ) {
	104	Type newType = (retType)->clone();
	105	candidate->env.apply( newType );
	106	mangleName += SymTab::Mangler::mangle( newType );
	107	delete newType;
	108	}
	109	std::map< std::string, PruneStruct >::iterator mapPlace = selected.find( mangleName );
	110	if ( mapPlace != selected.end() ) {
	111	if ( candidate->cost < mapPlace->second.candidate->cost ) {
	112	PRINT(
[6ed1d4b]	113	std::cerr << "cost " << candidate->cost << " beats " << mapPlace->second.candidate->cost << std::endl;
[7c64920]	114	)
[0f19d763]	115	selected[ mangleName ] = current;
[a32b204]	116	} else if ( candidate->cost == mapPlace->second.candidate->cost ) {
	117	PRINT(
[6ed1d4b]	118	std::cerr << "marking ambiguous" << std::endl;
[7c64920]	119	)
[0f19d763]	120	mapPlace->second.isAmbiguous = true;
[a32b204]	121	}
	122	} else {
	123	selected[ mangleName ] = current;
	124	}
	125	}
[d9a0e76]	126
	127	PRINT(
[6ed1d4b]	128	std::cerr << "there are " << selected.size() << " alternatives before elimination" << std::endl;
[7c64920]	129	)
[a32b204]	130
[0f19d763]	131	// accept the alternatives that were unambiguous
	132	for ( std::map< std::string, PruneStruct >::iterator target = selected.begin(); target != selected.end(); ++target ) {
	133	if ( ! target->second.isAmbiguous ) {
	134	Alternative &alt = *target->second.candidate;
	135	for ( std::list< Type* >::iterator result = alt.expr->get_results().begin(); result != alt.expr->get_results().end(); ++result ) {
	136	alt.env.applyFree( *result );
[a32b204]	137	}
[0f19d763]	138	*out++ = alt;
[a32b204]	139	}
[0f19d763]	140	}
[a32b204]	141
[d9a0e76]	142	}
[a32b204]	143
	144	template< typename InputIterator, typename OutputIterator >
	145	void findMinCost( InputIterator begin, InputIterator end, OutputIterator out ) {
	146	AltList alternatives;
	147
	148	// select the alternatives that have the minimum parameter cost
	149	Cost minCost = Cost::infinity;
	150	for ( AltList::iterator i = begin; i != end; ++i ) {
	151	if ( i->cost < minCost ) {
	152	minCost = i->cost;
	153	i->cost = i->cvtCost;
	154	alternatives.clear();
	155	alternatives.push_back( *i );
	156	} else if ( i->cost == minCost ) {
	157	i->cost = i->cvtCost;
	158	alternatives.push_back( *i );
	159	}
	160	}
	161	std::copy( alternatives.begin(), alternatives.end(), out );
[d9a0e76]	162	}
	163
[a32b204]	164	template< typename InputIterator >
	165	void simpleCombineEnvironments( InputIterator begin, InputIterator end, TypeEnvironment &result ) {
	166	while ( begin != end ) {
	167	result.simpleCombine( (*begin++).env );
	168	}
	169	}
[d9a0e76]	170
[a32b204]	171	void renameTypes( Expression *expr ) {
	172	for ( std::list< Type* >::iterator i = expr->get_results().begin(); i != expr->get_results().end(); ++i ) {
	173	(*i)->accept( global_renamer );
	174	}
[d9a0e76]	175	}
	176	}
	177
[a32b204]	178	template< typename InputIterator, typename OutputIterator >
	179	void AlternativeFinder::findSubExprs( InputIterator begin, InputIterator end, OutputIterator out ) {
	180	while ( begin != end ) {
	181	AlternativeFinder finder( indexer, env );
	182	finder.findWithAdjustment( *begin );
	183	// XXX either this
	184	//Designators::fixDesignations( finder, (*begin++)->get_argName() );
	185	// or XXX this
	186	begin++;
	187	PRINT(
[6ed1d4b]	188	std::cerr << "findSubExprs" << std::endl;
	189	printAlts( finder.alternatives, std::cerr );
[7c64920]	190	)
[0f19d763]	191	*out++ = finder;
[a32b204]	192	}
[d9a0e76]	193	}
	194
[a32b204]	195	AlternativeFinder::AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env )
	196	: indexer( indexer ), env( env ) {
[d9a0e76]	197	}
[51b7345]	198
[b6fe7e6]	199	void AlternativeFinder::find( Expression *expr, bool adjust, bool prune ) {
[a32b204]	200	expr->accept( *this );
	201	if ( alternatives.empty() ) {
	202	throw SemanticError( "No reasonable alternatives for expression ", expr );
	203	}
	204	for ( AltList::iterator i = alternatives.begin(); i != alternatives.end(); ++i ) {
	205	if ( adjust ) {
	206	adjustExprTypeList( i->expr->get_results().begin(), i->expr->get_results().end(), i->env, indexer );
	207	}
	208	}
[b6fe7e6]	209	if ( prune ) {
	210	PRINT(
	211	std::cerr << "alternatives before prune:" << std::endl;
	212	printAlts( alternatives, std::cerr );
	213	)
	214	AltList::iterator oldBegin = alternatives.begin();
	215	pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives ), indexer );
	216	if ( alternatives.begin() == oldBegin ) {
	217	std::ostringstream stream;
	218	stream << "Can't choose between alternatives for expression ";
	219	expr->print( stream );
	220	stream << "Alternatives are:";
	221	AltList winners;
	222	findMinCost( alternatives.begin(), alternatives.end(), back_inserter( winners ) );
	223	printAlts( winners, stream, 8 );
	224	throw SemanticError( stream.str() );
	225	}
	226	alternatives.erase( oldBegin, alternatives.end() );
	227	PRINT(
	228	std::cerr << "there are " << alternatives.size() << " alternatives after elimination" << std::endl;
	229	)
[a32b204]	230	}
[8e9cbb2]	231
	232	// Central location to handle gcc extension keyword for all expression types.
	233	for ( Alternative &iter: alternatives ) {
	234	iter.expr->set_extension( expr->get_extension() );
	235	} // for
[0f19d763]	236	}
[d9a0e76]	237
[b6fe7e6]	238	void AlternativeFinder::findWithAdjustment( Expression *expr, bool prune ) {
	239	find( expr, true, prune );
[d9a0e76]	240	}
[a32b204]	241
	242	template< typename StructOrUnionType >
[b6fe7e6]	243	void AlternativeFinder::addAggMembers( StructOrUnionType aggInst, Expression expr, const Cost &newCost, const TypeEnvironment & env, const std::string &name ) {
[a32b204]	244	std::list< Declaration* > members;
	245	aggInst->lookup( name, members );
	246	for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
	247	if ( DeclarationWithType dwt = dynamic_cast< DeclarationWithType >( *i ) ) {
[79970ed]	248	alternatives.push_back( Alternative( new MemberExpr( dwt, expr->clone() ), env, newCost ) );
[a32b204]	249	renameTypes( alternatives.back().expr );
	250	} else {
	251	assert( false );
	252	}
	253	}
[d9a0e76]	254	}
[a32b204]	255
	256	void AlternativeFinder::visit( ApplicationExpr *applicationExpr ) {
	257	alternatives.push_back( Alternative( applicationExpr->clone(), env, Cost::zero ) );
[d9a0e76]	258	}
	259
[a32b204]	260	Cost computeConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) {
	261	ApplicationExpr appExpr = dynamic_cast< ApplicationExpr >( alt.expr );
	262	assert( appExpr );
	263	PointerType pointer = dynamic_cast< PointerType >( appExpr->get_function()->get_results().front() );
	264	assert( pointer );
	265	FunctionType function = dynamic_cast< FunctionType >( pointer->get_base() );
	266	assert( function );
	267
	268	Cost convCost( 0, 0, 0 );
	269	std::list< DeclarationWithType* >& formals = function->get_parameters();
	270	std::list< DeclarationWithType* >::iterator formal = formals.begin();
	271	std::list< Expression* >& actuals = appExpr->get_args();
	272	for ( std::list< Expression* >::iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) {
	273	PRINT(
[6ed1d4b]	274	std::cerr << "actual expression:" << std::endl;
	275	(*actualExpr)->print( std::cerr, 8 );
	276	std::cerr << "--- results are" << std::endl;
	277	printAll( (*actualExpr)->get_results(), std::cerr, 8 );
[7c64920]	278	)
	279	std::list< DeclarationWithType* >::iterator startFormal = formal;
[a32b204]	280	Cost actualCost;
	281	for ( std::list< Type* >::iterator actual = (actualExpr)->get_results().begin(); actual != (actualExpr)->get_results().end(); ++actual ) {
	282	if ( formal == formals.end() ) {
	283	if ( function->get_isVarArgs() ) {
	284	convCost += Cost( 1, 0, 0 );
	285	break;
	286	} else {
	287	return Cost::infinity;
	288	}
	289	}
	290	PRINT(
[6ed1d4b]	291	std::cerr << std::endl << "converting ";
	292	(*actual)->print( std::cerr, 8 );
	293	std::cerr << std::endl << " to ";
	294	(*formal)->get_type()->print( std::cerr, 8 );
[7c64920]	295	)
	296	Cost newCost = conversionCost( actual, (formal)->get_type(), indexer, alt.env );
[a32b204]	297	PRINT(
[6ed1d4b]	298	std::cerr << std::endl << "cost is" << newCost << std::endl;
[7c64920]	299	)
[a32b204]	300
[7c64920]	301	if ( newCost == Cost::infinity ) {
	302	return newCost;
	303	}
[a32b204]	304	convCost += newCost;
	305	actualCost += newCost;
	306
	307	convCost += Cost( 0, polyCost( (formal)->get_type(), alt.env, indexer ) + polyCost( actual, alt.env, indexer ), 0 );
	308
	309	formal++;
	310	}
	311	if ( actualCost != Cost( 0, 0, 0 ) ) {
	312	std::list< DeclarationWithType* >::iterator startFormalPlusOne = startFormal;
	313	startFormalPlusOne++;
	314	if ( formal == startFormalPlusOne ) {
	315	// not a tuple type
	316	Type newType = (startFormal)->get_type()->clone();
	317	alt.env.apply( newType );
	318	actualExpr = new CastExpr( actualExpr, newType );
	319	} else {
	320	TupleType *newType = new TupleType( Type::Qualifiers() );
	321	for ( std::list< DeclarationWithType* >::iterator i = startFormal; i != formal; ++i ) {
	322	newType->get_types().push_back( (*i)->get_type()->clone() );
	323	}
	324	alt.env.apply( newType );
	325	actualExpr = new CastExpr( actualExpr, newType );
	326	}
	327	}
	328
[d9a0e76]	329	}
[a32b204]	330	if ( formal != formals.end() ) {
	331	return Cost::infinity;
[d9a0e76]	332	}
	333
[a32b204]	334	for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) {
	335	PRINT(
[6ed1d4b]	336	std::cerr << std::endl << "converting ";
	337	assert->second.actualType->print( std::cerr, 8 );
	338	std::cerr << std::endl << " to ";
	339	assert->second.formalType->print( std::cerr, 8 );
[02cea2d]	340	)
	341	Cost newCost = conversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env );
[a32b204]	342	PRINT(
[6ed1d4b]	343	std::cerr << std::endl << "cost of conversion is " << newCost << std::endl;
[02cea2d]	344	)
	345	if ( newCost == Cost::infinity ) {
	346	return newCost;
	347	}
[a32b204]	348	convCost += newCost;
[d9a0e76]	349
[a32b204]	350	convCost += Cost( 0, polyCost( assert->second.formalType, alt.env, indexer ) + polyCost( assert->second.actualType, alt.env, indexer ), 0 );
	351	}
[d9a0e76]	352
[a32b204]	353	return convCost;
	354	}
[d9a0e76]	355
[8c84ebd]	356	/// Adds type variables to the open variable set and marks their assertions
[a32b204]	357	void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ) {
	358	for ( std::list< TypeDecl* >::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
	359	unifiableVars[ (tyvar)->get_name() ] = (tyvar)->get_kind();
	360	for ( std::list< DeclarationWithType* >::iterator assert = (tyvar)->get_assertions().begin(); assert != (tyvar)->get_assertions().end(); ++assert ) {
	361	needAssertions[ *assert ] = true;
	362	}
[d9a0e76]	363	/// needAssertions.insert( needAssertions.end(), (tyvar)->get_assertions().begin(), (tyvar)->get_assertions().end() );
	364	}
	365	}
[a32b204]	366
	367	bool AlternativeFinder::instantiateFunction( std::list< DeclarationWithType* >& formals, /const/ AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave ) {
	368	simpleCombineEnvironments( actuals.begin(), actuals.end(), resultEnv );
	369	// make sure we don't widen any existing bindings
	370	for ( TypeEnvironment::iterator i = resultEnv.begin(); i != resultEnv.end(); ++i ) {
	371	i->allowWidening = false;
	372	}
	373	resultEnv.extractOpenVars( openVars );
	374
	375	/*
	376	Tuples::NameMatcher matcher( formals );
	377	try {
	378	matcher.match( actuals );
	379	} catch ( Tuples::NoMatch &e ) {
	380	std::cerr << "Alternative doesn't match: " << e.message << std::endl;
	381	}
	382	*/
	383	std::list< DeclarationWithType* >::iterator formal = formals.begin();
	384	for ( AltList::const_iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) {
	385	for ( std::list< Type* >::iterator actual = actualExpr->expr->get_results().begin(); actual != actualExpr->expr->get_results().end(); ++actual ) {
	386	if ( formal == formals.end() ) {
	387	return isVarArgs;
	388	}
	389	PRINT(
	390	std::cerr << "formal type is ";
	391	(*formal)->get_type()->print( std::cerr );
	392	std::cerr << std::endl << "actual type is ";
	393	(*actual)->print( std::cerr );
	394	std::cerr << std::endl;
[7c64920]	395	)
[0f19d763]	396	if ( ! unify( (formal)->get_type(), actual, resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
	397	return false;
	398	}
[d9a0e76]	399	formal++;
[a32b204]	400	}
	401	}
	402	// Handling of default values
	403	while ( formal != formals.end() ) {
	404	if ( ObjectDecl od = dynamic_cast<ObjectDecl >( *formal ) )
	405	if ( SingleInit si = dynamic_cast<SingleInit >( od->get_init() ))
	406	// so far, only constant expressions are accepted as default values
	407	if ( ConstantExpr cnstexpr = dynamic_cast<ConstantExpr >( si->get_value()) )
	408	if ( Constant cnst = dynamic_cast<Constant >( cnstexpr->get_constant() ) )
	409	if ( unify( (*formal)->get_type(), cnst->get_type(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
	410	// XXX Don't know if this is right
	411	actuals.push_back( Alternative( cnstexpr->clone(), env, Cost::zero ) );
	412	formal++;
	413	if ( formal == formals.end()) break;
	414	}
	415	return false;
	416	}
	417	return true;
[d9a0e76]	418	}
[51b7345]	419
[89b686a]	420	// /// Map of declaration uniqueIds (intended to be the assertions in an AssertionSet) to their parents and the number of times they've been included
	421	//typedef std::unordered_map< UniqueId, std::unordered_map< UniqueId, unsigned > > AssertionParentSet;
[79970ed]	422
[a1d7679]	423	static const int recursionLimit = /10/ 4; ///< Limit to depth of recursion satisfaction
[89b686a]	424	//static const unsigned recursionParentLimit = 1; ///< Limit to the number of times an assertion can recursively use itself
[51b7345]	425
[a32b204]	426	void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) {
	427	for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) {
	428	if ( i->second == true ) {
	429	i->first->accept( indexer );
	430	}
	431	}
[d9a0e76]	432	}
[79970ed]	433
[a32b204]	434	template< typename ForwardIterator, typename OutputIterator >
[79970ed]	435	void inferRecursive( ForwardIterator begin, ForwardIterator end, const Alternative &newAlt, OpenVarSet &openVars, const SymTab::Indexer &decls, const AssertionSet &newNeed, /const AssertionParentSet &needParents,/
[ebf5689]	436	int level, const SymTab::Indexer &indexer, OutputIterator out ) {
[a32b204]	437	if ( begin == end ) {
	438	if ( newNeed.empty() ) {
	439	*out++ = newAlt;
	440	return;
	441	} else if ( level >= recursionLimit ) {
	442	throw SemanticError( "Too many recursive assertions" );
	443	} else {
	444	AssertionSet newerNeed;
	445	PRINT(
	446	std::cerr << "recursing with new set:" << std::endl;
	447	printAssertionSet( newNeed, std::cerr, 8 );
[7c64920]	448	)
[89b686a]	449	inferRecursive( newNeed.begin(), newNeed.end(), newAlt, openVars, decls, newerNeed, /needParents,/ level+1, indexer, out );
[a32b204]	450	return;
	451	}
	452	}
	453
	454	ForwardIterator cur = begin++;
	455	if ( ! cur->second ) {
[89b686a]	456	inferRecursive( begin, end, newAlt, openVars, decls, newNeed, /needParents,/ level, indexer, out );
[a32b204]	457	}
	458	DeclarationWithType *curDecl = cur->first;
[d9a0e76]	459	PRINT(
[a32b204]	460	std::cerr << "inferRecursive: assertion is ";
	461	curDecl->print( std::cerr );
	462	std::cerr << std::endl;
[7c64920]	463	)
[0f19d763]	464	std::list< DeclarationWithType* > candidates;
[a32b204]	465	decls.lookupId( curDecl->get_name(), candidates );
[6ed1d4b]	466	/// if ( candidates.empty() ) { std::cerr << "no candidates!" << std::endl; }
[a32b204]	467	for ( std::list< DeclarationWithType* >::const_iterator candidate = candidates.begin(); candidate != candidates.end(); ++candidate ) {
	468	PRINT(
[6ed1d4b]	469	std::cerr << "inferRecursive: candidate is ";
	470	(*candidate)->print( std::cerr );
	471	std::cerr << std::endl;
[7c64920]	472	)
[79970ed]	473
[0f19d763]	474	AssertionSet newHave, newerNeed( newNeed );
[a32b204]	475	TypeEnvironment newEnv( newAlt.env );
	476	OpenVarSet newOpenVars( openVars );
	477	Type adjType = (candidate)->get_type()->clone();
	478	adjustExprType( adjType, newEnv, indexer );
	479	adjType->accept( global_renamer );
	480	PRINT(
	481	std::cerr << "unifying ";
	482	curDecl->get_type()->print( std::cerr );
	483	std::cerr << " with ";
	484	adjType->print( std::cerr );
	485	std::cerr << std::endl;
[7c64920]	486	)
[0f19d763]	487	if ( unify( curDecl->get_type(), adjType, newEnv, newerNeed, newHave, newOpenVars, indexer ) ) {
	488	PRINT(
	489	std::cerr << "success!" << std::endl;
[a32b204]	490	)
[0f19d763]	491	SymTab::Indexer newDecls( decls );
	492	addToIndexer( newHave, newDecls );
	493	Alternative newerAlt( newAlt );
	494	newerAlt.env = newEnv;
	495	assert( (*candidate)->get_uniqueId() );
[22cad76]	496	DeclarationWithType candDecl = static_cast< DeclarationWithType >( Declaration::declFromId( (*candidate)->get_uniqueId() ) );
[89b686a]	497	//AssertionParentSet newNeedParents( needParents );
[22cad76]	498	// skip repeatingly-self-recursive assertion satisfaction
[89b686a]	499	// DOESN'T WORK: grandchild nodes conflict with their cousins
	500	//if ( newNeedParents[ curDecl->get_uniqueId() ][ candDecl->get_uniqueId() ]++ > recursionParentLimit ) continue;
[22cad76]	501	Expression *varExpr = new VariableExpr( candDecl );
[0f19d763]	502	deleteAll( varExpr->get_results() );
	503	varExpr->get_results().clear();
	504	varExpr->get_results().push_front( adjType->clone() );
	505	PRINT(
[6ed1d4b]	506	std::cerr << "satisfying assertion " << curDecl->get_uniqueId() << " ";
	507	curDecl->print( std::cerr );
	508	std::cerr << " with declaration " << (*candidate)->get_uniqueId() << " ";
	509	(*candidate)->print( std::cerr );
	510	std::cerr << std::endl;
[7c64920]	511	)
[0f19d763]	512	ApplicationExpr appExpr = static_cast< ApplicationExpr >( newerAlt.expr );
	513	// XXX: this is a memory leak, but adjType can't be deleted because it might contain assertions
	514	appExpr->get_inferParams()[ curDecl->get_uniqueId() ] = ParamEntry( (*candidate)->get_uniqueId(), adjType->clone(), curDecl->get_type()->clone(), varExpr );
[89b686a]	515	inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, /newNeedParents,/ level, indexer, out );
[0f19d763]	516	} else {
	517	delete adjType;
	518	}
[a32b204]	519	}
[d9a0e76]	520	}
	521
[a32b204]	522	template< typename OutputIterator >
	523	void AlternativeFinder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) {
[d9a0e76]	524	// PRINT(
[6ed1d4b]	525	// std::cerr << "inferParameters: assertions needed are" << std::endl;
	526	// printAll( need, std::cerr, 8 );
[d9a0e76]	527	// )
[a32b204]	528	SymTab::Indexer decls( indexer );
	529	PRINT(
[6ed1d4b]	530	std::cerr << "============= original indexer" << std::endl;
	531	indexer.print( std::cerr );
	532	std::cerr << "============= new indexer" << std::endl;
	533	decls.print( std::cerr );
[7c64920]	534	)
[0f19d763]	535	addToIndexer( have, decls );
[a32b204]	536	AssertionSet newNeed;
[89b686a]	537	//AssertionParentSet needParents;
	538	inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, /needParents,/ 0, indexer, out );
[d9a0e76]	539	// PRINT(
[6ed1d4b]	540	// std::cerr << "declaration 14 is ";
[d9a0e76]	541	// Declaration::declFromId
	542	// *out++ = newAlt;
	543	// )
	544	}
	545
[a32b204]	546	template< typename OutputIterator >
	547	void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, AltList &actualAlt, OutputIterator out ) {
	548	OpenVarSet openVars;
	549	AssertionSet resultNeed, resultHave;
	550	TypeEnvironment resultEnv;
	551	makeUnifiableVars( funcType, openVars, resultNeed );
	552	if ( instantiateFunction( funcType->get_parameters(), actualAlt, funcType->get_isVarArgs(), openVars, resultEnv, resultNeed, resultHave ) ) {
	553	ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
	554	Alternative newAlt( appExpr, resultEnv, sumCost( actualAlt ) );
	555	makeExprList( actualAlt, appExpr->get_args() );
	556	PRINT(
[6ed1d4b]	557	std::cerr << "need assertions:" << std::endl;
	558	printAssertionSet( resultNeed, std::cerr, 8 );
[7c64920]	559	)
[0f19d763]	560	inferParameters( resultNeed, resultHave, newAlt, openVars, out );
[d9a0e76]	561	}
	562	}
	563
[a32b204]	564	void AlternativeFinder::visit( UntypedExpr *untypedExpr ) {
	565	bool doneInit = false;
	566	AlternativeFinder funcOpFinder( indexer, env );
[d9a0e76]	567
[6ed1d4b]	568	AlternativeFinder funcFinder( indexer, env );
	569
	570	{
[70f89d00]	571	std::string fname = InitTweak::getFunctionName( untypedExpr );
	572	if ( fname == "&&" ) {
[2871210]	573	VoidType v = Type::Qualifiers(); // resolve to type void *
	574	PointerType pt( Type::Qualifiers(), v.clone() );
	575	UntypedExpr *vexpr = untypedExpr->clone();
	576	vexpr->get_results().push_front( pt.clone() );
	577	alternatives.push_back( Alternative( vexpr, env, Cost()) );
[a32b204]	578	return;
	579	}
	580	}
[d9a0e76]	581
[a32b204]	582	funcFinder.findWithAdjustment( untypedExpr->get_function() );
	583	std::list< AlternativeFinder > argAlternatives;
	584	findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), back_inserter( argAlternatives ) );
[d9a0e76]	585
[a32b204]	586	std::list< AltList > possibilities;
	587	combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) );
[d9a0e76]	588
[a32b204]	589	Tuples::TupleAssignSpotter tassign( this );
	590	if ( tassign.isTupleAssignment( untypedExpr, possibilities ) ) {
	591	// take care of possible tuple assignments, or discard expression
	592	return;
	593	} // else ...
[d9a0e76]	594
[a32b204]	595	AltList candidates;
[91b8a17]	596	SemanticError errors;
[d9a0e76]	597
[a32b204]	598	for ( AltList::const_iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) {
[91b8a17]	599	try {
	600	PRINT(
	601	std::cerr << "working on alternative: " << std::endl;
	602	func->print( std::cerr, 8 );
	603	)
	604	// check if the type is pointer to function
	605	PointerType *pointer;
	606	if ( func->expr->get_results().size() == 1 && ( pointer = dynamic_cast< PointerType* >( func->expr->get_results().front() ) ) ) {
	607	if ( FunctionType function = dynamic_cast< FunctionType >( pointer->get_base() ) ) {
	608	for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
	609	// XXX
	610	//Designators::check_alternative( function, *actualAlt );
	611	makeFunctionAlternatives( func, function, actualAlt, std::back_inserter( candidates ) );
	612	}
	613	} else if ( TypeInstType typeInst = dynamic_cast< TypeInstType >( pointer->get_base() ) ) {
	614	EqvClass eqvClass;
	615	if ( func->env.lookup( typeInst->get_name(), eqvClass ) && eqvClass.type ) {
	616	if ( FunctionType function = dynamic_cast< FunctionType >( eqvClass.type ) ) {
	617	for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
	618	makeFunctionAlternatives( func, function, actualAlt, std::back_inserter( candidates ) );
	619	} // for
	620	} // if
[a32b204]	621	} // if
	622	} // if
[91b8a17]	623	} else {
	624	// seek a function operator that's compatible
	625	if ( ! doneInit ) {
	626	doneInit = true;
	627	NameExpr *opExpr = new NameExpr( "?()" );
	628	try {
	629	funcOpFinder.findWithAdjustment( opExpr );
	630	} catch( SemanticError &e ) {
	631	// it's ok if there aren't any defined function ops
	632	}
	633	PRINT(
	634	std::cerr << "known function ops:" << std::endl;
	635	printAlts( funcOpFinder.alternatives, std::cerr, 8 );
	636	)
[a32b204]	637	}
	638
[91b8a17]	639	for ( AltList::const_iterator funcOp = funcOpFinder.alternatives.begin(); funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
	640	// check if the type is pointer to function
	641	PointerType *pointer;
	642	if ( funcOp->expr->get_results().size() == 1
	643	&& ( pointer = dynamic_cast< PointerType* >( funcOp->expr->get_results().front() ) ) ) {
	644	if ( FunctionType function = dynamic_cast< FunctionType >( pointer->get_base() ) ) {
	645	for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
	646	AltList currentAlt;
	647	currentAlt.push_back( *func );
	648	currentAlt.insert( currentAlt.end(), actualAlt->begin(), actualAlt->end() );
	649	makeFunctionAlternatives( *funcOp, function, currentAlt, std::back_inserter( candidates ) );
	650	} // for
	651	} // if
[a32b204]	652	} // if
[91b8a17]	653	} // for
	654	} // if
	655	} catch ( SemanticError &e ) {
	656	errors.append( e );
	657	}
[a32b204]	658	} // for
	659
[91b8a17]	660	// Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
	661	if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }
	662
[a32b204]	663	for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) {
	664	Cost cvtCost = computeConversionCost( *withFunc, indexer );
	665
	666	PRINT(
	667	ApplicationExpr appExpr = dynamic_cast< ApplicationExpr >( withFunc->expr );
	668	assert( appExpr );
	669	PointerType pointer = dynamic_cast< PointerType >( appExpr->get_function()->get_results().front() );
	670	assert( pointer );
	671	FunctionType function = dynamic_cast< FunctionType >( pointer->get_base() );
	672	assert( function );
[6ed1d4b]	673	std::cerr << "Case +++++++++++++" << std::endl;
	674	std::cerr << "formals are:" << std::endl;
	675	printAll( function->get_parameters(), std::cerr, 8 );
	676	std::cerr << "actuals are:" << std::endl;
	677	printAll( appExpr->get_args(), std::cerr, 8 );
	678	std::cerr << "bindings are:" << std::endl;
	679	withFunc->env.print( std::cerr, 8 );
	680	std::cerr << "cost of conversion is:" << cvtCost << std::endl;
[7c64920]	681	)
	682	if ( cvtCost != Cost::infinity ) {
	683	withFunc->cvtCost = cvtCost;
	684	alternatives.push_back( *withFunc );
	685	} // if
[a32b204]	686	} // for
	687	candidates.clear();
	688	candidates.splice( candidates.end(), alternatives );
	689
	690	findMinCost( candidates.begin(), candidates.end(), std::back_inserter( alternatives ) );
	691	}
	692
	693	bool isLvalue( Expression *expr ) {
	694	for ( std::list< Type* >::const_iterator i = expr->get_results().begin(); i != expr->get_results().end(); ++i ) {
	695	if ( !(*i)->get_isLvalue() ) return false;
	696	} // for
	697	return true;
	698	}
	699
	700	void AlternativeFinder::visit( AddressExpr *addressExpr ) {
	701	AlternativeFinder finder( indexer, env );
	702	finder.find( addressExpr->get_arg() );
	703	for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
	704	if ( isLvalue( i->expr ) ) {
	705	alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) );
	706	} // if
	707	} // for
	708	}
	709
	710	void AlternativeFinder::visit( CastExpr *castExpr ) {
	711	for ( std::list< Type* >::iterator i = castExpr->get_results().begin(); i != castExpr->get_results().end(); ++i ) {
[85517ddb]	712	i = resolveTypeof( i, indexer );
[a32b204]	713	SymTab::validateType( *i, &indexer );
	714	adjustExprType( *i, env, indexer );
	715	} // for
	716
	717	AlternativeFinder finder( indexer, env );
	718	finder.findWithAdjustment( castExpr->get_arg() );
	719
	720	AltList candidates;
	721	for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
	722	AssertionSet needAssertions, haveAssertions;
	723	OpenVarSet openVars;
	724
	725	// It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a
	726	// cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results
	727	// that are cast directly. The candidate is invalid if it has fewer results than there are types to cast
	728	// to.
	729	int discardedValues = (*i).expr->get_results().size() - castExpr->get_results().size();
	730	if ( discardedValues < 0 ) continue;
	731	std::list< Type* >::iterator candidate_end = (*i).expr->get_results().begin();
	732	std::advance( candidate_end, castExpr->get_results().size() );
[adcdd2f]	733	// unification run for side-effects
	734	unifyList( castExpr->get_results().begin(), castExpr->get_results().end(),
	735	(*i).expr->get_results().begin(), candidate_end,
	736	i->env, needAssertions, haveAssertions, openVars, indexer );
[a32b204]	737	Cost thisCost = castCostList( (*i).expr->get_results().begin(), candidate_end,
[adcdd2f]	738	castExpr->get_results().begin(), castExpr->get_results().end(),
	739	indexer, i->env );
[a32b204]	740	if ( thisCost != Cost::infinity ) {
	741	// count one safe conversion for each value that is thrown away
	742	thisCost += Cost( 0, 0, discardedValues );
	743	CastExpr *newExpr = castExpr->clone();
	744	newExpr->set_arg( i->expr->clone() );
	745	candidates.push_back( Alternative( newExpr, i->env, i->cost, thisCost ) );
	746	} // if
	747	} // for
	748
	749	// findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
	750	// cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice
	751	// selects first based on argument cost, then on conversion cost.
	752	AltList minArgCost;
	753	findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
	754	findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
	755	}
	756
	757	void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) {
	758	AlternativeFinder funcFinder( indexer, env );
	759	funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
	760
	761	for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
	762	if ( agg->expr->get_results().size() == 1 ) {
	763	if ( StructInstType structInst = dynamic_cast< StructInstType >( agg->expr->get_results().front() ) ) {
[b6fe7e6]	764	addAggMembers( structInst, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
[a32b204]	765	} else if ( UnionInstType unionInst = dynamic_cast< UnionInstType >( agg->expr->get_results().front() ) ) {
[b6fe7e6]	766	addAggMembers( unionInst, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
[a32b204]	767	} // if
	768	} // if
	769	} // for
	770	}
	771
	772	void AlternativeFinder::visit( MemberExpr *memberExpr ) {
	773	alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
	774	}
	775
	776	void AlternativeFinder::visit( NameExpr *nameExpr ) {
	777	std::list< DeclarationWithType* > declList;
	778	indexer.lookupId( nameExpr->get_name(), declList );
	779	PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; )
[0f19d763]	780	for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) {
	781	VariableExpr newExpr( *i, nameExpr->get_argName() );
	782	alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) );
	783	PRINT(
	784	std::cerr << "decl is ";
	785	(*i)->print( std::cerr );
	786	std::cerr << std::endl;
	787	std::cerr << "newExpr is ";
	788	newExpr.print( std::cerr );
	789	std::cerr << std::endl;
[7c64920]	790	)
[0f19d763]	791	renameTypes( alternatives.back().expr );
	792	if ( StructInstType structInst = dynamic_cast< StructInstType >( (*i)->get_type() ) ) {
[b6fe7e6]	793	addAggMembers( structInst, &newExpr, Cost( 0, 0, 1 ), env, "" );
[0f19d763]	794	} else if ( UnionInstType unionInst = dynamic_cast< UnionInstType >( (*i)->get_type() ) ) {
[b6fe7e6]	795	addAggMembers( unionInst, &newExpr, Cost( 0, 0, 1 ), env, "" );
[0f19d763]	796	} // if
	797	} // for
[a32b204]	798	}
	799
	800	void AlternativeFinder::visit( VariableExpr *variableExpr ) {
[85517ddb]	801	// not sufficient to clone here, because variable's type may have changed
	802	// since the VariableExpr was originally created.
	803	alternatives.push_back( Alternative( new VariableExpr( variableExpr->get_var() ), env, Cost::zero ) );
[a32b204]	804	}
	805
	806	void AlternativeFinder::visit( ConstantExpr *constantExpr ) {
	807	alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
	808	}
	809
	810	void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) {
	811	if ( sizeofExpr->get_isType() ) {
[85517ddb]	812	// xxx - resolveTypeof?
[a32b204]	813	alternatives.push_back( Alternative( sizeofExpr->clone(), env, Cost::zero ) );
	814	} else {
	815	// find all alternatives for the argument to sizeof
	816	AlternativeFinder finder( indexer, env );
	817	finder.find( sizeofExpr->get_expr() );
	818	// find the lowest cost alternative among the alternatives, otherwise ambiguous
	819	AltList winners;
	820	findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
	821	if ( winners.size() != 1 ) {
	822	throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() );
	823	} // if
	824	// return the lowest cost alternative for the argument
	825	Alternative &choice = winners.front();
	826	alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
[47534159]	827	} // if
	828	}
	829
	830	void AlternativeFinder::visit( AlignofExpr *alignofExpr ) {
	831	if ( alignofExpr->get_isType() ) {
[85517ddb]	832	// xxx - resolveTypeof?
[47534159]	833	alternatives.push_back( Alternative( alignofExpr->clone(), env, Cost::zero ) );
	834	} else {
	835	// find all alternatives for the argument to sizeof
	836	AlternativeFinder finder( indexer, env );
	837	finder.find( alignofExpr->get_expr() );
	838	// find the lowest cost alternative among the alternatives, otherwise ambiguous
	839	AltList winners;
	840	findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
	841	if ( winners.size() != 1 ) {
	842	throw SemanticError( "Ambiguous expression in alignof operand: ", alignofExpr->get_expr() );
	843	} // if
	844	// return the lowest cost alternative for the argument
	845	Alternative &choice = winners.front();
	846	alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
[a32b204]	847	} // if
	848	}
	849
[2a4b088]	850	template< typename StructOrUnionType >
	851	void AlternativeFinder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
	852	std::list< Declaration* > members;
	853	aggInst->lookup( name, members );
	854	for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
	855	if ( DeclarationWithType dwt = dynamic_cast< DeclarationWithType >( *i ) ) {
[79970ed]	856	alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
[2a4b088]	857	renameTypes( alternatives.back().expr );
	858	} else {
	859	assert( false );
	860	}
	861	}
	862	}
[6ed1d4b]	863
[2a4b088]	864	void AlternativeFinder::visit( UntypedOffsetofExpr *offsetofExpr ) {
	865	AlternativeFinder funcFinder( indexer, env );
[85517ddb]	866	// xxx - resolveTypeof?
[2a4b088]	867	if ( StructInstType structInst = dynamic_cast< StructInstType >( offsetofExpr->get_type() ) ) {
	868	addOffsetof( structInst, offsetofExpr->get_member() );
	869	} else if ( UnionInstType unionInst = dynamic_cast< UnionInstType >( offsetofExpr->get_type() ) ) {
	870	addOffsetof( unionInst, offsetofExpr->get_member() );
	871	}
	872	}
[6ed1d4b]	873
[25a054f]	874	void AlternativeFinder::visit( OffsetofExpr *offsetofExpr ) {
	875	alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
[afc1045]	876	}
	877
	878	void AlternativeFinder::visit( OffsetPackExpr *offsetPackExpr ) {
	879	alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
[25a054f]	880	}
	881
[a32b204]	882	void AlternativeFinder::resolveAttr( DeclarationWithType funcDecl, FunctionType function, Type *argType, const TypeEnvironment &env ) {
	883	// assume no polymorphism
	884	// assume no implicit conversions
	885	assert( function->get_parameters().size() == 1 );
	886	PRINT(
[6ed1d4b]	887	std::cerr << "resolvAttr: funcDecl is ";
	888	funcDecl->print( std::cerr );
	889	std::cerr << " argType is ";
	890	argType->print( std::cerr );
	891	std::cerr << std::endl;
[7c64920]	892	)
	893	if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
	894	alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) );
	895	for ( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) {
	896	alternatives.back().expr->get_results().push_back( (*i)->get_type()->clone() );
	897	} // for
	898	} // if
[a32b204]	899	}
	900
	901	void AlternativeFinder::visit( AttrExpr *attrExpr ) {
	902	// assume no 'pointer-to-attribute'
	903	NameExpr nameExpr = dynamic_cast< NameExpr >( attrExpr->get_attr() );
	904	assert( nameExpr );
	905	std::list< DeclarationWithType* > attrList;
	906	indexer.lookupId( nameExpr->get_name(), attrList );
	907	if ( attrExpr->get_isType() \|\| attrExpr->get_expr() ) {
	908	for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
	909	// check if the type is function
	910	if ( FunctionType function = dynamic_cast< FunctionType >( (*i)->get_type() ) ) {
	911	// assume exactly one parameter
	912	if ( function->get_parameters().size() == 1 ) {
	913	if ( attrExpr->get_isType() ) {
	914	resolveAttr( *i, function, attrExpr->get_type(), env );
	915	} else {
	916	AlternativeFinder finder( indexer, env );
	917	finder.find( attrExpr->get_expr() );
	918	for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
	919	if ( choice->expr->get_results().size() == 1 ) {
	920	resolveAttr(*i, function, choice->expr->get_results().front(), choice->env );
	921	} // fi
	922	} // for
	923	} // if
	924	} // if
	925	} // if
	926	} // for
	927	} else {
	928	for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
	929	VariableExpr newExpr( *i );
	930	alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) );
	931	renameTypes( alternatives.back().expr );
	932	} // for
	933	} // if
	934	}
	935
	936	void AlternativeFinder::visit( LogicalExpr *logicalExpr ) {
	937	AlternativeFinder firstFinder( indexer, env );
	938	firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
	939	for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
	940	AlternativeFinder secondFinder( indexer, first->env );
	941	secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
	942	for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
	943	LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() );
	944	alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) );
[d9a0e76]	945	}
	946	}
	947	}
[51b7345]	948
[a32b204]	949	void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) {
	950	AlternativeFinder firstFinder( indexer, env );
	951	firstFinder.findWithAdjustment( conditionalExpr->get_arg1() );
	952	for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
	953	AlternativeFinder secondFinder( indexer, first->env );
	954	secondFinder.findWithAdjustment( conditionalExpr->get_arg2() );
	955	for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
	956	AlternativeFinder thirdFinder( indexer, second->env );
	957	thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() );
	958	for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) {
	959	OpenVarSet openVars;
	960	AssertionSet needAssertions, haveAssertions;
	961	Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost );
	962	std::list< Type* > commonTypes;
	963	if ( unifyList( second->expr->get_results().begin(), second->expr->get_results().end(), third->expr->get_results().begin(), third->expr->get_results().end(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonTypes ) ) {
	964	ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() );
	965	std::list< Type* >::const_iterator original = second->expr->get_results().begin();
	966	std::list< Type* >::const_iterator commonType = commonTypes.begin();
	967	for ( ; original != second->expr->get_results().end() && commonType != commonTypes.end(); ++original, ++commonType ) {
	968	if ( *commonType ) {
	969	newExpr->get_results().push_back( *commonType );
	970	} else {
	971	newExpr->get_results().push_back( (*original)->clone() );
	972	} // if
	973	} // for
	974	newAlt.expr = newExpr;
	975	inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
	976	} // if
	977	} // for
	978	} // for
	979	} // for
	980	}
	981
	982	void AlternativeFinder::visit( CommaExpr *commaExpr ) {
	983	TypeEnvironment newEnv( env );
	984	Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
	985	AlternativeFinder secondFinder( indexer, newEnv );
	986	secondFinder.findWithAdjustment( commaExpr->get_arg2() );
	987	for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) {
	988	alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) );
	989	} // for
	990	delete newFirstArg;
	991	}
	992
	993	void AlternativeFinder::visit( TupleExpr *tupleExpr ) {
	994	std::list< AlternativeFinder > subExprAlternatives;
	995	findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) );
	996	std::list< AltList > possibilities;
	997	combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) );
	998	for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) {
	999	TupleExpr *newExpr = new TupleExpr;
	1000	makeExprList( *i, newExpr->get_exprs() );
	1001	for ( std::list< Expression* >::const_iterator resultExpr = newExpr->get_exprs().begin(); resultExpr != newExpr->get_exprs().end(); ++resultExpr ) {
	1002	for ( std::list< Type* >::const_iterator resultType = (resultExpr)->get_results().begin(); resultType != (resultExpr)->get_results().end(); ++resultType ) {
	1003	newExpr->get_results().push_back( (*resultType)->clone() );
	1004	} // for
	1005	} // for
	1006
	1007	TypeEnvironment compositeEnv;
	1008	simpleCombineEnvironments( i->begin(), i->end(), compositeEnv );
	1009	alternatives.push_back( Alternative( newExpr, compositeEnv, sumCost( *i ) ) );
	1010	} // for
[d9a0e76]	1011	}
[dc2e7e0]	1012
	1013	void AlternativeFinder::visit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
	1014	alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
	1015	}
[b6fe7e6]	1016
	1017	void AlternativeFinder::visit( ConstructorExpr * ctorExpr ) {
	1018	AlternativeFinder finder( indexer, env );
	1019	// don't prune here, since it's guaranteed all alternatives will have the same type
	1020	// (giving the alternatives different types is half of the point of ConstructorExpr nodes)
	1021	finder.findWithAdjustment( ctorExpr->get_callExpr(), false );
	1022	for ( Alternative & alt : finder.alternatives ) {
	1023	alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
	1024	}
	1025	}
[51b7345]	1026	} // namespace ResolvExpr
[a32b204]	1027
	1028	// Local Variables: //
	1029	// tab-width: 4 //
	1030	// mode: c++ //
	1031	// compile-command: "make install" //
	1032	// End: //

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

Download in other formats: