Context Navigation

source: src/ResolvExpr/AlternativeFinder.cc @ f4903df

memory

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

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

Download in other formats: