Context Navigation

source: src/ResolvExpr/AlternativeFinder.cc @ ea83e00a

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc

Last change on this file since ea83e00a was ea83e00a, checked in by Rob Schluntz <rschlunt@…>, 5 years ago
attempt to narrow resolution of function calls based on return type if a cast is applied
Property mode set to `100644`
File size: 48.2 KB

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

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

Download in other formats: