Context Navigation

source: src/ResolvExpr/AlternativeFinder.cc @ e76acbe

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

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

Download in other formats: