source: src/ResolvExpr/AlternativeFinder.cc@ d2d50d7

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors deferred_resn demangler enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new with_gc
Last change on this file since d2d50d7 was 7faab5e, checked in by Aaron Moss <a3moss@…>, 8 years ago

[fixes #71]
  • Property mode set to 100644
File size: 69.9 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 Aug 28 13:47:24 2017
13// Update Count : 32
14//
15
16#include <algorithm> // for copy
17#include <cassert> // for strict_dynamic_cast, assert, assertf
18#include <cstddef> // for size_t
19#include <iostream> // for operator<<, cerr, ostream, endl
20#include <iterator> // for back_insert_iterator, back_inserter
21#include <list> // for _List_iterator, list, _List_const_...
22#include <map> // for _Rb_tree_iterator, map, _Rb_tree_c...
23#include <memory> // for allocator_traits<>::value_type, unique_ptr
24#include <utility> // for pair
25#include <vector> // for vector
26
27#include "Alternative.h" // for AltList, Alternative
28#include "AlternativeFinder.h"
29#include "Common/SemanticError.h" // for SemanticError
30#include "Common/utility.h" // for deleteAll, printAll, CodeLocation
31#include "Cost.h" // for Cost, Cost::zero, operator<<, Cost...
32#include "ExplodedActual.h" // for ExplodedActual
33#include "InitTweak/InitTweak.h" // for getFunctionName
34#include "RenameVars.h" // for RenameVars, global_renamer
35#include "ResolveTypeof.h" // for resolveTypeof
36#include "Resolver.h" // for resolveStmtExpr
37#include "SymTab/Indexer.h" // for Indexer
38#include "SymTab/Mangler.h" // for Mangler
39#include "SymTab/Validate.h" // for validateType
40#include "SynTree/Constant.h" // for Constant
41#include "SynTree/Declaration.h" // for DeclarationWithType, TypeDecl, Dec...
42#include "SynTree/Expression.h" // for Expression, CastExpr, NameExpr
43#include "SynTree/Initializer.h" // for SingleInit, operator<<, Designation
44#include "SynTree/SynTree.h" // for UniqueId
45#include "SynTree/Type.h" // for Type, FunctionType, PointerType
46#include "Tuples/Explode.h" // for explode
47#include "Tuples/Tuples.h" // for isTtype, handleTupleAssignment
48#include "Unify.h" // for unify
49#include "typeops.h" // for adjustExprType, polyCost, castCost
50
51extern bool resolvep;
52#define PRINT( text ) if ( resolvep ) { text }
53//#define DEBUG_COST
54
55using std::move;
56
57/// copies any copyable type
58template<typename T>
59T copy(const T& x) { return x; }
60
61namespace ResolvExpr {
62 Expression *resolveInVoidContext( Expression *expr, const SymTab::Indexer &indexer, TypeEnvironment &env ) {
63 CastExpr *castToVoid = new CastExpr( expr );
64
65 AlternativeFinder finder( indexer, env );
66 finder.findWithAdjustment( castToVoid );
67
68 // it's a property of the language that a cast expression has either 1 or 0 interpretations; if it has 0
69 // interpretations, an exception has already been thrown.
70 assert( finder.get_alternatives().size() == 1 );
71 CastExpr *newExpr = dynamic_cast< CastExpr* >( finder.get_alternatives().front().expr );
72 assert( newExpr );
73 env = finder.get_alternatives().front().env;
74 return newExpr->get_arg()->clone();
75 }
76
77 Cost sumCost( const AltList &in ) {
78 Cost total = Cost::zero;
79 for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
80 total += i->cost;
81 }
82 return total;
83 }
84
85 void printAlts( const AltList &list, std::ostream &os, unsigned int indentAmt ) {
86 Indenter indent = { Indenter::tabsize, indentAmt };
87 for ( AltList::const_iterator i = list.begin(); i != list.end(); ++i ) {
88 i->print( os, indent );
89 os << std::endl;
90 }
91 }
92
93 namespace {
94 void makeExprList( const AltList &in, std::list< Expression* > &out ) {
95 for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
96 out.push_back( i->expr->clone() );
97 }
98 }
99
100 struct PruneStruct {
101 bool isAmbiguous;
102 AltList::iterator candidate;
103 PruneStruct() {}
104 PruneStruct( AltList::iterator candidate ): isAmbiguous( false ), candidate( candidate ) {}
105 };
106
107 /// Prunes a list of alternatives down to those that have the minimum conversion cost for a given return type; skips ambiguous interpretations
108 template< typename InputIterator, typename OutputIterator >
109 void pruneAlternatives( InputIterator begin, InputIterator end, OutputIterator out ) {
110 // select the alternatives that have the minimum conversion cost for a particular set of result types
111 std::map< std::string, PruneStruct > selected;
112 for ( AltList::iterator candidate = begin; candidate != end; ++candidate ) {
113 PruneStruct current( candidate );
114 std::string mangleName;
115 {
116 Type * newType = candidate->expr->get_result()->clone();
117 candidate->env.apply( newType );
118 mangleName = SymTab::Mangler::mangle( newType );
119 delete newType;
120 }
121 std::map< std::string, PruneStruct >::iterator mapPlace = selected.find( mangleName );
122 if ( mapPlace != selected.end() ) {
123 if ( candidate->cost < mapPlace->second.candidate->cost ) {
124 PRINT(
125 std::cerr << "cost " << candidate->cost << " beats " << mapPlace->second.candidate->cost << std::endl;
126 )
127 selected[ mangleName ] = current;
128 } else if ( candidate->cost == mapPlace->second.candidate->cost ) {
129 PRINT(
130 std::cerr << "marking ambiguous" << std::endl;
131 )
132 mapPlace->second.isAmbiguous = true;
133 } else {
134 PRINT(
135 std::cerr << "cost " << candidate->cost << " loses to " << mapPlace->second.candidate->cost << std::endl;
136 )
137 }
138 } else {
139 selected[ mangleName ] = current;
140 }
141 }
142
143 // accept the alternatives that were unambiguous
144 for ( std::map< std::string, PruneStruct >::iterator target = selected.begin(); target != selected.end(); ++target ) {
145 if ( ! target->second.isAmbiguous ) {
146 Alternative &alt = *target->second.candidate;
147 alt.env.applyFree( alt.expr->get_result() );
148 *out++ = alt;
149 }
150 }
151 }
152
153 void renameTypes( Expression *expr ) {
154 expr->get_result()->accept( global_renamer );
155 }
156 } // namespace
157
158 void referenceToRvalueConversion( Expression *& expr ) {
159 if ( dynamic_cast< ReferenceType * >( expr->get_result() ) ) {
160 // cast away reference from expr
161 expr = new CastExpr( expr, expr->get_result()->stripReferences()->clone() );
162 }
163 }
164
165 template< typename InputIterator, typename OutputIterator >
166 void AlternativeFinder::findSubExprs( InputIterator begin, InputIterator end, OutputIterator out ) {
167 while ( begin != end ) {
168 AlternativeFinder finder( indexer, env );
169 finder.findWithAdjustment( *begin );
170 // XXX either this
171 //Designators::fixDesignations( finder, (*begin++)->get_argName() );
172 // or XXX this
173 begin++;
174 PRINT(
175 std::cerr << "findSubExprs" << std::endl;
176 printAlts( finder.alternatives, std::cerr );
177 )
178 *out++ = finder;
179 }
180 }
181
182 AlternativeFinder::AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env )
183 : indexer( indexer ), env( env ) {
184 }
185
186 void AlternativeFinder::find( Expression *expr, bool adjust, bool prune, bool failFast ) {
187 expr->accept( *this );
188 if ( failFast && alternatives.empty() ) {
189 PRINT(
190 std::cerr << "No reasonable alternatives for expression " << expr << std::endl;
191 )
192 throw SemanticError( "No reasonable alternatives for expression ", expr );
193 }
194 if ( prune ) {
195 auto oldsize = alternatives.size();
196 PRINT(
197 std::cerr << "alternatives before prune:" << std::endl;
198 printAlts( alternatives, std::cerr );
199 )
200 AltList pruned;
201 pruneAlternatives( alternatives.begin(), alternatives.end(), back_inserter( pruned ) );
202 if ( failFast && pruned.empty() ) {
203 std::ostringstream stream;
204 AltList winners;
205 findMinCost( alternatives.begin(), alternatives.end(), back_inserter( winners ) );
206 stream << "Cannot choose between " << winners.size() << " alternatives for expression\n";
207 expr->print( stream );
208 stream << "Alternatives are:\n";
209 printAlts( winners, stream, 1 );
210 throw SemanticError( stream.str() );
211 }
212 alternatives = move(pruned);
213 PRINT(
214 std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
215 )
216 PRINT(
217 std::cerr << "there are " << alternatives.size() << " alternatives after elimination" << std::endl;
218 )
219 }
220 // adjust types after pruning so that types substituted by pruneAlternatives are correctly adjusted
221 for ( AltList::iterator i = alternatives.begin(); i != alternatives.end(); ++i ) {
222 if ( adjust ) {
223 adjustExprType( i->expr->get_result(), i->env, indexer );
224 }
225 }
226
227 // Central location to handle gcc extension keyword, etc. for all expression types.
228 for ( Alternative &iter: alternatives ) {
229 iter.expr->set_extension( expr->get_extension() );
230 iter.expr->location = expr->location;
231 } // for
232 }
233
234 void AlternativeFinder::findWithAdjustment( Expression *expr ) {
235 find( expr, true );
236 }
237
238 void AlternativeFinder::findWithoutPrune( Expression * expr ) {
239 find( expr, true, false );
240 }
241
242 void AlternativeFinder::maybeFind( Expression * expr ) {
243 find( expr, true, true, false );
244 }
245
246 void AlternativeFinder::addAnonConversions( const Alternative & alt ) {
247 // adds anonymous member interpretations whenever an aggregate value type is seen.
248 // it's okay for the aggregate expression to have reference type -- cast it to the base type to treat the aggregate as the referenced value
249 std::unique_ptr<Expression> aggrExpr( alt.expr->clone() );
250 alt.env.apply( aggrExpr->get_result() );
251 Type * aggrType = aggrExpr->get_result();
252 if ( dynamic_cast< ReferenceType * >( aggrType ) ) {
253 aggrType = aggrType->stripReferences();
254 aggrExpr.reset( new CastExpr( aggrExpr.release(), aggrType->clone() ) );
255 }
256
257 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) {
258 NameExpr nameExpr( "" );
259 addAggMembers( structInst, aggrExpr.get(), alt.cost+Cost::safe, alt.env, &nameExpr );
260 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) {
261 NameExpr nameExpr( "" );
262 addAggMembers( unionInst, aggrExpr.get(), alt.cost+Cost::safe, alt.env, &nameExpr );
263 } // if
264 }
265
266 template< typename StructOrUnionType >
267 void AlternativeFinder::addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) {
268 // by this point, member must be a name expr
269 NameExpr * nameExpr = dynamic_cast< NameExpr * >( member );
270 if ( ! nameExpr ) return;
271 const std::string & name = nameExpr->get_name();
272 std::list< Declaration* > members;
273 aggInst->lookup( name, members );
274
275 for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
276 if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
277 alternatives.push_back( Alternative( new MemberExpr( dwt, expr->clone() ), env, newCost ) );
278 renameTypes( alternatives.back().expr );
279 addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a member expression.
280 } else {
281 assert( false );
282 }
283 }
284 }
285
286 void AlternativeFinder::addTupleMembers( TupleType * tupleType, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) {
287 if ( ConstantExpr * constantExpr = dynamic_cast< ConstantExpr * >( member ) ) {
288 // get the value of the constant expression as an int, must be between 0 and the length of the tuple type to have meaning
289 // xxx - this should be improved by memoizing the value of constant exprs
290 // during parsing and reusing that information here.
291 std::stringstream ss( constantExpr->get_constant()->get_value() );
292 int val = 0;
293 std::string tmp;
294 if ( ss >> val && ! (ss >> tmp) ) {
295 if ( val >= 0 && (unsigned int)val < tupleType->size() ) {
296 alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
297 } // if
298 } // if
299 } else if ( NameExpr * nameExpr = dynamic_cast< NameExpr * >( member ) ) {
300 // xxx - temporary hack until 0/1 are int constants
301 if ( nameExpr->get_name() == "0" || nameExpr->get_name() == "1" ) {
302 std::stringstream ss( nameExpr->get_name() );
303 int val;
304 ss >> val;
305 alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
306 }
307 } // if
308 }
309
310 void AlternativeFinder::visit( ApplicationExpr *applicationExpr ) {
311 alternatives.push_back( Alternative( applicationExpr->clone(), env, Cost::zero ) );
312 }
313
314 Cost computeConversionCost( Type * actualType, Type * formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) {
315 PRINT(
316 std::cerr << std::endl << "converting ";
317 actualType->print( std::cerr, 8 );
318 std::cerr << std::endl << " to ";
319 formalType->print( std::cerr, 8 );
320 std::cerr << std::endl << "environment is: ";
321 env.print( std::cerr, 8 );
322 std::cerr << std::endl;
323 )
324 Cost convCost = conversionCost( actualType, formalType, indexer, env );
325 PRINT(
326 std::cerr << std::endl << "cost is " << convCost << std::endl;
327 )
328 if ( convCost == Cost::infinity ) {
329 return convCost;
330 }
331 convCost.incPoly( polyCost( formalType, env, indexer ) + polyCost( actualType, env, indexer ) );
332 PRINT(
333 std::cerr << "cost with polycost is " << convCost << std::endl;
334 )
335 return convCost;
336 }
337
338 Cost computeExpressionConversionCost( Expression *& actualExpr, Type * formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) {
339 Cost convCost = computeConversionCost( actualExpr->result, formalType, indexer, env );
340
341 // if there is a non-zero conversion cost, ignoring poly cost, then the expression requires conversion.
342 // ignore poly cost for now, since this requires resolution of the cast to infer parameters and this
343 // does not currently work for the reason stated below.
344 Cost tmpCost = convCost;
345 tmpCost.incPoly( -tmpCost.get_polyCost() );
346 if ( tmpCost != Cost::zero ) {
347 Type *newType = formalType->clone();
348 env.apply( newType );
349 actualExpr = new CastExpr( actualExpr, newType );
350 // xxx - SHOULD be able to resolve this cast, but at the moment pointers are not castable to zero_t, but are implicitly convertible. This is clearly
351 // inconsistent, once this is fixed it should be possible to resolve the cast.
352 // xxx - this isn't working, it appears because type1 (the formal type) is seen as widenable, but it shouldn't be, because this makes the conversion from DT* to DT* since commontype(zero_t, DT*) is DT*, rather than just nothing.
353
354 // AlternativeFinder finder( indexer, env );
355 // finder.findWithAdjustment( actualExpr );
356 // assertf( finder.get_alternatives().size() > 0, "Somehow castable expression failed to find alternatives." );
357 // assertf( finder.get_alternatives().size() == 1, "Somehow got multiple alternatives for known cast expression." );
358 // Alternative & alt = finder.get_alternatives().front();
359 // delete actualExpr;
360 // actualExpr = alt.expr->clone();
361 }
362 return convCost;
363 }
364
365 Cost computeApplicationConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) {
366 ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( alt.expr );
367 PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
368 FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() );
369
370 Cost convCost = Cost::zero;
371 std::list< DeclarationWithType* >& formals = function->get_parameters();
372 std::list< DeclarationWithType* >::iterator formal = formals.begin();
373 std::list< Expression* >& actuals = appExpr->get_args();
374
375 for ( std::list< Expression* >::iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) {
376 Type * actualType = (*actualExpr)->get_result();
377 PRINT(
378 std::cerr << "actual expression:" << std::endl;
379 (*actualExpr)->print( std::cerr, 8 );
380 std::cerr << "--- results are" << std::endl;
381 actualType->print( std::cerr, 8 );
382 )
383 if ( formal == formals.end() ) {
384 if ( function->get_isVarArgs() ) {
385 convCost.incUnsafe();
386 PRINT( std::cerr << "end of formals with varargs function: inc unsafe: " << convCost << std::endl; ; )
387 // convert reference-typed expressions to value-typed expressions
388 referenceToRvalueConversion( *actualExpr );
389 continue;
390 } else {
391 return Cost::infinity;
392 }
393 }
394 Type * formalType = (*formal)->get_type();
395 convCost += computeExpressionConversionCost( *actualExpr, formalType, indexer, alt.env );
396 ++formal; // can't be in for-loop update because of the continue
397 }
398 if ( formal != formals.end() ) {
399 return Cost::infinity;
400 }
401
402 for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) {
403 convCost += computeConversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env );
404 }
405
406 return convCost;
407 }
408
409 /// Adds type variables to the open variable set and marks their assertions
410 void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ) {
411 for ( Type::ForallList::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
412 unifiableVars[ (*tyvar)->get_name() ] = TypeDecl::Data{ *tyvar };
413 for ( std::list< DeclarationWithType* >::iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) {
414 needAssertions[ *assert ].isUsed = true;
415 }
416/// needAssertions.insert( needAssertions.end(), (*tyvar)->get_assertions().begin(), (*tyvar)->get_assertions().end() );
417 }
418 }
419
420 // /// Map of declaration uniqueIds (intended to be the assertions in an AssertionSet) to their parents and the number of times they've been included
421 //typedef std::unordered_map< UniqueId, std::unordered_map< UniqueId, unsigned > > AssertionParentSet;
422
423 static const int recursionLimit = /*10*/ 4; ///< Limit to depth of recursion satisfaction
424 //static const unsigned recursionParentLimit = 1; ///< Limit to the number of times an assertion can recursively use itself
425
426 void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) {
427 for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) {
428 if ( i->second.isUsed ) {
429 indexer.addId( i->first );
430 }
431 }
432 }
433
434 template< typename ForwardIterator, typename OutputIterator >
435 void inferRecursive( ForwardIterator begin, ForwardIterator end, const Alternative &newAlt, OpenVarSet &openVars, const SymTab::Indexer &decls, const AssertionSet &newNeed, /*const AssertionParentSet &needParents,*/
436 int level, const SymTab::Indexer &indexer, OutputIterator out ) {
437 if ( begin == end ) {
438 if ( newNeed.empty() ) {
439 PRINT(
440 std::cerr << "all assertions satisfied, output alternative: ";
441 newAlt.print( std::cerr );
442 std::cerr << std::endl;
443 );
444 *out++ = newAlt;
445 return;
446 } else if ( level >= recursionLimit ) {
447 throw SemanticError( "Too many recursive assertions" );
448 } else {
449 AssertionSet newerNeed;
450 PRINT(
451 std::cerr << "recursing with new set:" << std::endl;
452 printAssertionSet( newNeed, std::cerr, 8 );
453 )
454 inferRecursive( newNeed.begin(), newNeed.end(), newAlt, openVars, decls, newerNeed, /*needParents,*/ level+1, indexer, out );
455 return;
456 }
457 }
458
459 ForwardIterator cur = begin++;
460 if ( ! cur->second.isUsed ) {
461 inferRecursive( begin, end, newAlt, openVars, decls, newNeed, /*needParents,*/ level, indexer, out );
462 return; // xxx - should this continue? previously this wasn't here, and it looks like it should be
463 }
464 DeclarationWithType *curDecl = cur->first;
465
466 PRINT(
467 std::cerr << "inferRecursive: assertion is ";
468 curDecl->print( std::cerr );
469 std::cerr << std::endl;
470 )
471 std::list< SymTab::Indexer::IdData > candidates;
472 decls.lookupId( curDecl->get_name(), candidates );
473/// if ( candidates.empty() ) { std::cerr << "no candidates!" << std::endl; }
474 for ( const auto & data : candidates ) {
475 DeclarationWithType * candidate = data.id;
476 PRINT(
477 std::cerr << "inferRecursive: candidate is ";
478 candidate->print( std::cerr );
479 std::cerr << std::endl;
480 )
481
482 AssertionSet newHave, newerNeed( newNeed );
483 TypeEnvironment newEnv( newAlt.env );
484 OpenVarSet newOpenVars( openVars );
485 Type *adjType = candidate->get_type()->clone();
486 adjustExprType( adjType, newEnv, indexer );
487 adjType->accept( global_renamer );
488 PRINT(
489 std::cerr << "unifying ";
490 curDecl->get_type()->print( std::cerr );
491 std::cerr << " with ";
492 adjType->print( std::cerr );
493 std::cerr << std::endl;
494 )
495 if ( unify( curDecl->get_type(), adjType, newEnv, newerNeed, newHave, newOpenVars, indexer ) ) {
496 PRINT(
497 std::cerr << "success!" << std::endl;
498 )
499 SymTab::Indexer newDecls( decls );
500 addToIndexer( newHave, newDecls );
501 Alternative newerAlt( newAlt );
502 newerAlt.env = newEnv;
503 assertf( candidate->get_uniqueId(), "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() );
504
505 // everything with an empty idChain was pulled in by the current assertion.
506 // add current assertion's idChain + current assertion's ID so that the correct inferParameters can be found.
507 for ( auto & a : newerNeed ) {
508 if ( a.second.idChain.empty() ) {
509 a.second.idChain = cur->second.idChain;
510 a.second.idChain.push_back( curDecl->get_uniqueId() );
511 }
512 }
513
514 //AssertionParentSet newNeedParents( needParents );
515 // skip repeatingly-self-recursive assertion satisfaction
516 // DOESN'T WORK: grandchild nodes conflict with their cousins
517 //if ( newNeedParents[ curDecl->get_uniqueId() ][ candDecl->get_uniqueId() ]++ > recursionParentLimit ) continue;
518 Expression *varExpr = data.combine();
519 delete varExpr->get_result();
520 varExpr->set_result( adjType->clone() );
521 PRINT(
522 std::cerr << "satisfying assertion " << curDecl->get_uniqueId() << " ";
523 curDecl->print( std::cerr );
524 std::cerr << " with declaration " << candidate->get_uniqueId() << " ";
525 candidate->print( std::cerr );
526 std::cerr << std::endl;
527 )
528 // follow the current assertion's ID chain to find the correct set of inferred parameters to add the candidate to (i.e. the set of inferred parameters belonging to the entity which requested the assertion parameter).
529 InferredParams * inferParameters = &newerAlt.expr->get_inferParams();
530 for ( UniqueId id : cur->second.idChain ) {
531 inferParameters = (*inferParameters)[ id ].inferParams.get();
532 }
533 // XXX: this is a memory leak, but adjType can't be deleted because it might contain assertions
534 (*inferParameters)[ curDecl->get_uniqueId() ] = ParamEntry( candidate->get_uniqueId(), adjType->clone(), curDecl->get_type()->clone(), varExpr );
535 inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, /*newNeedParents,*/ level, indexer, out );
536 } else {
537 delete adjType;
538 }
539 }
540 }
541
542 template< typename OutputIterator >
543 void AlternativeFinder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) {
544// PRINT(
545// std::cerr << "inferParameters: assertions needed are" << std::endl;
546// printAll( need, std::cerr, 8 );
547// )
548 SymTab::Indexer decls( indexer );
549 // PRINT(
550 // std::cerr << "============= original indexer" << std::endl;
551 // indexer.print( std::cerr );
552 // std::cerr << "============= new indexer" << std::endl;
553 // decls.print( std::cerr );
554 // )
555 addToIndexer( have, decls );
556 AssertionSet newNeed;
557 //AssertionParentSet needParents;
558 PRINT(
559 std::cerr << "env is: " << std::endl;
560 newAlt.env.print( std::cerr, 0 );
561 std::cerr << std::endl;
562 )
563
564 inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, /*needParents,*/ 0, indexer, out );
565// PRINT(
566// std::cerr << "declaration 14 is ";
567// Declaration::declFromId
568// *out++ = newAlt;
569// )
570 }
571
572 /// Gets a default value from an initializer, nullptr if not present
573 ConstantExpr* getDefaultValue( Initializer* init ) {
574 if ( SingleInit* si = dynamic_cast<SingleInit*>( init ) ) {
575 if ( CastExpr* ce = dynamic_cast<CastExpr*>( si->get_value() ) ) {
576 return dynamic_cast<ConstantExpr*>( ce->get_arg() );
577 }
578 }
579 return nullptr;
580 }
581
582 /// State to iteratively build a match of parameter expressions to arguments
583 struct ArgPack {
584 std::size_t parent; ///< Index of parent pack
585 std::unique_ptr<Expression> expr; ///< The argument stored here
586 Cost cost; ///< The cost of this argument
587 TypeEnvironment env; ///< Environment for this pack
588 AssertionSet need; ///< Assertions outstanding for this pack
589 AssertionSet have; ///< Assertions found for this pack
590 OpenVarSet openVars; ///< Open variables for this pack
591 unsigned nextArg; ///< Index of next argument in arguments list
592 unsigned tupleStart; ///< Number of tuples that start at this index
593 unsigned nextExpl; ///< Index of next exploded element
594 unsigned explAlt; ///< Index of alternative for nextExpl > 0
595
596 ArgPack()
597 : parent(0), expr(), cost(Cost::zero), env(), need(), have(), openVars(), nextArg(0),
598 tupleStart(0), nextExpl(0), explAlt(0) {}
599
600 ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have,
601 const OpenVarSet& openVars)
602 : parent(0), expr(), cost(Cost::zero), env(env), need(need), have(have),
603 openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {}
604
605 ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need,
606 AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg,
607 unsigned tupleStart = 0, Cost cost = Cost::zero, unsigned nextExpl = 0,
608 unsigned explAlt = 0 )
609 : parent(parent), expr(expr->clone()), cost(cost), env(move(env)), need(move(need)),
610 have(move(have)), openVars(move(openVars)), nextArg(nextArg), tupleStart(tupleStart),
611 nextExpl(nextExpl), explAlt(explAlt) {}
612
613 ArgPack(const ArgPack& o, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have,
614 OpenVarSet&& openVars, unsigned nextArg, Cost added )
615 : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), cost(o.cost + added),
616 env(move(env)), need(move(need)), have(move(have)), openVars(move(openVars)),
617 nextArg(nextArg), tupleStart(o.tupleStart), nextExpl(0), explAlt(0) {}
618
619 /// true iff this pack is in the middle of an exploded argument
620 bool hasExpl() const { return nextExpl > 0; }
621
622 /// Gets the list of exploded alternatives for this pack
623 const ExplodedActual& getExpl( const ExplodedArgs& args ) const {
624 return args[nextArg-1][explAlt];
625 }
626
627 /// Ends a tuple expression, consolidating the appropriate actuals
628 void endTuple( const std::vector<ArgPack>& packs ) {
629 // add all expressions in tuple to list, summing cost
630 std::list<Expression*> exprs;
631 const ArgPack* pack = this;
632 if ( expr ) { exprs.push_front( expr.release() ); }
633 while ( pack->tupleStart == 0 ) {
634 pack = &packs[pack->parent];
635 exprs.push_front( pack->expr->clone() );
636 cost += pack->cost;
637 }
638 // reset pack to appropriate tuple
639 expr.reset( new TupleExpr( exprs ) );
640 tupleStart = pack->tupleStart - 1;
641 parent = pack->parent;
642 }
643 };
644
645 /// Instantiates an argument to match a formal, returns false if no results left
646 bool instantiateArgument( Type* formalType, Initializer* initializer,
647 const ExplodedArgs& args, std::vector<ArgPack>& results, std::size_t& genStart,
648 const SymTab::Indexer& indexer, unsigned nTuples = 0 ) {
649 if ( TupleType* tupleType = dynamic_cast<TupleType*>( formalType ) ) {
650 // formalType is a TupleType - group actuals into a TupleExpr
651 ++nTuples;
652 for ( Type* type : *tupleType ) {
653 // xxx - dropping initializer changes behaviour from previous, but seems correct
654 if ( ! instantiateArgument(
655 type, nullptr, args, results, genStart, indexer, nTuples ) )
656 return false;
657 nTuples = 0;
658 }
659 // re-consititute tuples for final generation
660 for ( auto i = genStart; i < results.size(); ++i ) {
661 results[i].endTuple( results );
662 }
663 return true;
664 } else if ( TypeInstType* ttype = Tuples::isTtype( formalType ) ) {
665 // formalType is a ttype, consumes all remaining arguments
666 // xxx - mixing default arguments with variadic??
667
668 // completed tuples; will be spliced to end of results to finish
669 std::vector<ArgPack> finalResults{};
670
671 // iterate until all results completed
672 std::size_t genEnd;
673 ++nTuples;
674 do {
675 genEnd = results.size();
676
677 // add another argument to results
678 for ( std::size_t i = genStart; i < genEnd; ++i ) {
679 auto nextArg = results[i].nextArg;
680
681 // use next element of exploded tuple if present
682 if ( results[i].hasExpl() ) {
683 const ExplodedActual& expl = results[i].getExpl( args );
684
685 unsigned nextExpl = results[i].nextExpl + 1;
686 if ( nextExpl == expl.exprs.size() ) {
687 nextExpl = 0;
688 }
689
690 results.emplace_back(
691 i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env),
692 copy(results[i].need), copy(results[i].have),
693 copy(results[i].openVars), nextArg, nTuples, Cost::zero, nextExpl,
694 results[i].explAlt );
695
696 continue;
697 }
698
699 // finish result when out of arguments
700 if ( nextArg >= args.size() ) {
701 ArgPack newResult{
702 results[i].env, results[i].need, results[i].have,
703 results[i].openVars };
704 newResult.nextArg = nextArg;
705 Type* argType;
706
707 if ( nTuples > 0 || ! results[i].expr ) {
708 // first iteration or no expression to clone,
709 // push empty tuple expression
710 newResult.parent = i;
711 std::list<Expression*> emptyList;
712 newResult.expr.reset( new TupleExpr( emptyList ) );
713 argType = newResult.expr->get_result();
714 } else {
715 // clone result to collect tuple
716 newResult.parent = results[i].parent;
717 newResult.cost = results[i].cost;
718 newResult.tupleStart = results[i].tupleStart;
719 newResult.expr.reset( results[i].expr->clone() );
720 argType = newResult.expr->get_result();
721
722 if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {
723 // the case where a ttype value is passed directly is special,
724 // e.g. for argument forwarding purposes
725 // xxx - what if passing multiple arguments, last of which is
726 // ttype?
727 // xxx - what would happen if unify was changed so that unifying
728 // tuple
729 // types flattened both before unifying lists? then pass in
730 // TupleType (ttype) below.
731 --newResult.tupleStart;
732 } else {
733 // collapse leftover arguments into tuple
734 newResult.endTuple( results );
735 argType = newResult.expr->get_result();
736 }
737 }
738
739 // check unification for ttype before adding to final
740 if ( unify( ttype, argType, newResult.env, newResult.need, newResult.have,
741 newResult.openVars, indexer ) ) {
742 finalResults.push_back( move(newResult) );
743 }
744
745 continue;
746 }
747
748 // add each possible next argument
749 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
750 const ExplodedActual& expl = args[nextArg][j];
751
752 // fresh copies of parent parameters for this iteration
753 TypeEnvironment env = results[i].env;
754 OpenVarSet openVars = results[i].openVars;
755
756 env.addActual( expl.env, openVars );
757
758 // skip empty tuple arguments by (near-)cloning parent into next gen
759 if ( expl.exprs.empty() ) {
760 results.emplace_back(
761 results[i], move(env), copy(results[i].need),
762 copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
763
764 continue;
765 }
766
767 // add new result
768 results.emplace_back(
769 i, expl.exprs.front().get(), move(env), copy(results[i].need),
770 copy(results[i].have), move(openVars), nextArg + 1,
771 nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
772 }
773 }
774
775 // reset for next round
776 genStart = genEnd;
777 nTuples = 0;
778 } while ( genEnd != results.size() );
779
780 // splice final results onto results
781 for ( std::size_t i = 0; i < finalResults.size(); ++i ) {
782 results.push_back( move(finalResults[i]) );
783 }
784 return ! finalResults.empty();
785 }
786
787 // iterate each current subresult
788 std::size_t genEnd = results.size();
789 for ( std::size_t i = genStart; i < genEnd; ++i ) {
790 auto nextArg = results[i].nextArg;
791
792 // use remainder of exploded tuple if present
793 if ( results[i].hasExpl() ) {
794 const ExplodedActual& expl = results[i].getExpl( args );
795 Expression* expr = expl.exprs[results[i].nextExpl].get();
796
797 TypeEnvironment env = results[i].env;
798 AssertionSet need = results[i].need, have = results[i].have;
799 OpenVarSet openVars = results[i].openVars;
800
801 Type* actualType = expr->get_result();
802
803 PRINT(
804 std::cerr << "formal type is ";
805 formalType->print( std::cerr );
806 std::cerr << std::endl << "actual type is ";
807 actualType->print( std::cerr );
808 std::cerr << std::endl;
809 )
810
811 if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
812 unsigned nextExpl = results[i].nextExpl + 1;
813 if ( nextExpl == expl.exprs.size() ) {
814 nextExpl = 0;
815 }
816
817 results.emplace_back(
818 i, expr, move(env), move(need), move(have), move(openVars), nextArg,
819 nTuples, Cost::zero, nextExpl, results[i].explAlt );
820 }
821
822 continue;
823 }
824
825 // use default initializers if out of arguments
826 if ( nextArg >= args.size() ) {
827 if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) {
828 if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) {
829 TypeEnvironment env = results[i].env;
830 AssertionSet need = results[i].need, have = results[i].have;
831 OpenVarSet openVars = results[i].openVars;
832
833 if ( unify( formalType, cnst->get_type(), env, need, have, openVars,
834 indexer ) ) {
835 results.emplace_back(
836 i, cnstExpr, move(env), move(need), move(have),
837 move(openVars), nextArg, nTuples );
838 }
839 }
840 }
841
842 continue;
843 }
844
845 // Check each possible next argument
846 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
847 const ExplodedActual& expl = args[nextArg][j];
848
849 // fresh copies of parent parameters for this iteration
850 TypeEnvironment env = results[i].env;
851 AssertionSet need = results[i].need, have = results[i].have;
852 OpenVarSet openVars = results[i].openVars;
853
854 env.addActual( expl.env, openVars );
855
856 // skip empty tuple arguments by (near-)cloning parent into next gen
857 if ( expl.exprs.empty() ) {
858 results.emplace_back(
859 results[i], move(env), move(need), move(have), move(openVars),
860 nextArg + 1, expl.cost );
861
862 continue;
863 }
864
865 // consider only first exploded actual
866 Expression* expr = expl.exprs.front().get();
867 Type* actualType = expr->get_result()->clone();
868
869 PRINT(
870 std::cerr << "formal type is ";
871 formalType->print( std::cerr );
872 std::cerr << std::endl << "actual type is ";
873 actualType->print( std::cerr );
874 std::cerr << std::endl;
875 )
876
877 // attempt to unify types
878 if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) {
879 // add new result
880 results.emplace_back(
881 i, expr, move(env), move(need), move(have), move(openVars), nextArg + 1,
882 nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
883 }
884 }
885 }
886
887 // reset for next parameter
888 genStart = genEnd;
889
890 return genEnd != results.size();
891 }
892
893 template<typename OutputIterator>
894 void AlternativeFinder::validateFunctionAlternative( const Alternative &func, ArgPack& result,
895 const std::vector<ArgPack>& results, OutputIterator out ) {
896 ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
897 // sum cost and accumulate actuals
898 std::list<Expression*>& args = appExpr->get_args();
899 Cost cost = func.cost;
900 const ArgPack* pack = &result;
901 while ( pack->expr ) {
902 args.push_front( pack->expr->clone() );
903 cost += pack->cost;
904 pack = &results[pack->parent];
905 }
906 // build and validate new alternative
907 Alternative newAlt( appExpr, result.env, cost );
908 PRINT(
909 std::cerr << "instantiate function success: " << appExpr << std::endl;
910 std::cerr << "need assertions:" << std::endl;
911 printAssertionSet( result.need, std::cerr, 8 );
912 )
913 inferParameters( result.need, result.have, newAlt, result.openVars, out );
914 }
915
916 template<typename OutputIterator>
917 void AlternativeFinder::makeFunctionAlternatives( const Alternative &func,
918 FunctionType *funcType, const ExplodedArgs &args, OutputIterator out ) {
919 OpenVarSet funcOpenVars;
920 AssertionSet funcNeed, funcHave;
921 TypeEnvironment funcEnv( func.env );
922 makeUnifiableVars( funcType, funcOpenVars, funcNeed );
923 // add all type variables as open variables now so that those not used in the parameter
924 // list are still considered open.
925 funcEnv.add( funcType->get_forall() );
926
927 if ( targetType && ! targetType->isVoid() && ! funcType->get_returnVals().empty() ) {
928 // attempt to narrow based on expected target type
929 Type * returnType = funcType->get_returnVals().front()->get_type();
930 if ( ! unify( returnType, targetType, funcEnv, funcNeed, funcHave, funcOpenVars,
931 indexer ) ) {
932 // unification failed, don't pursue this function alternative
933 return;
934 }
935 }
936
937 // iteratively build matches, one parameter at a time
938 std::vector<ArgPack> results;
939 results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } );
940 std::size_t genStart = 0;
941
942 for ( DeclarationWithType* formal : funcType->get_parameters() ) {
943 ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal );
944 if ( ! instantiateArgument(
945 obj->get_type(), obj->get_init(), args, results, genStart, indexer ) )
946 return;
947 }
948
949 if ( funcType->get_isVarArgs() ) {
950 // append any unused arguments to vararg pack
951 std::size_t genEnd;
952 do {
953 genEnd = results.size();
954
955 // iterate results
956 for ( std::size_t i = genStart; i < genEnd; ++i ) {
957 auto nextArg = results[i].nextArg;
958
959 // use remainder of exploded tuple if present
960 if ( results[i].hasExpl() ) {
961 const ExplodedActual& expl = results[i].getExpl( args );
962
963 unsigned nextExpl = results[i].nextExpl + 1;
964 if ( nextExpl == expl.exprs.size() ) {
965 nextExpl = 0;
966 }
967
968 results.emplace_back(
969 i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env),
970 copy(results[i].need), copy(results[i].have),
971 copy(results[i].openVars), nextArg, 0, Cost::zero, nextExpl,
972 results[i].explAlt );
973
974 continue;
975 }
976
977 // finish result when out of arguments
978 if ( nextArg >= args.size() ) {
979 validateFunctionAlternative( func, results[i], results, out );
980
981 continue;
982 }
983
984 // add each possible next argument
985 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
986 const ExplodedActual& expl = args[nextArg][j];
987
988 // fresh copies of parent parameters for this iteration
989 TypeEnvironment env = results[i].env;
990 OpenVarSet openVars = results[i].openVars;
991
992 env.addActual( expl.env, openVars );
993
994 // skip empty tuple arguments by (near-)cloning parent into next gen
995 if ( expl.exprs.empty() ) {
996 results.emplace_back(
997 results[i], move(env), copy(results[i].need),
998 copy(results[i].have), move(openVars), nextArg + 1, expl.cost );
999
1000 continue;
1001 }
1002
1003 // add new result
1004 results.emplace_back(
1005 i, expl.exprs.front().get(), move(env), copy(results[i].need),
1006 copy(results[i].have), move(openVars), nextArg + 1, 0,
1007 expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
1008 }
1009 }
1010
1011 genStart = genEnd;
1012 } while ( genEnd != results.size() );
1013 } else {
1014 // filter out results that don't use all the arguments
1015 for ( std::size_t i = genStart; i < results.size(); ++i ) {
1016 ArgPack& result = results[i];
1017 if ( ! result.hasExpl() && result.nextArg >= args.size() ) {
1018 validateFunctionAlternative( func, result, results, out );
1019 }
1020 }
1021 }
1022 }
1023
1024 void AlternativeFinder::visit( UntypedExpr *untypedExpr ) {
1025 AlternativeFinder funcFinder( indexer, env );
1026 funcFinder.findWithAdjustment( untypedExpr->get_function() );
1027 // if there are no function alternatives, then proceeding is a waste of time.
1028 if ( funcFinder.alternatives.empty() ) return;
1029
1030 std::vector< AlternativeFinder > argAlternatives;
1031 findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(),
1032 back_inserter( argAlternatives ) );
1033
1034 // take care of possible tuple assignments
1035 // if not tuple assignment, assignment is taken care of as a normal function call
1036 Tuples::handleTupleAssignment( *this, untypedExpr, argAlternatives );
1037
1038 // find function operators
1039 static NameExpr *opExpr = new NameExpr( "?()" );
1040 AlternativeFinder funcOpFinder( indexer, env );
1041 // it's ok if there aren't any defined function ops
1042 funcOpFinder.maybeFind( opExpr);
1043 PRINT(
1044 std::cerr << "known function ops:" << std::endl;
1045 printAlts( funcOpFinder.alternatives, std::cerr, 1 );
1046 )
1047
1048 // pre-explode arguments
1049 ExplodedArgs argExpansions;
1050 argExpansions.reserve( argAlternatives.size() );
1051
1052 for ( const AlternativeFinder& arg : argAlternatives ) {
1053 argExpansions.emplace_back();
1054 auto& argE = argExpansions.back();
1055 argE.reserve( arg.alternatives.size() );
1056
1057 for ( const Alternative& actual : arg ) {
1058 argE.emplace_back( actual, indexer );
1059 }
1060 }
1061
1062 AltList candidates;
1063 SemanticError errors;
1064 for ( AltList::iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) {
1065 try {
1066 PRINT(
1067 std::cerr << "working on alternative: " << std::endl;
1068 func->print( std::cerr, 8 );
1069 )
1070 // check if the type is pointer to function
1071 if ( PointerType *pointer = dynamic_cast< PointerType* >( func->expr->get_result()->stripReferences() ) ) {
1072 if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
1073 Alternative newFunc( *func );
1074 referenceToRvalueConversion( newFunc.expr );
1075 makeFunctionAlternatives( newFunc, function, argExpansions,
1076 std::back_inserter( candidates ) );
1077 }
1078 } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->get_result()->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer)
1079 EqvClass eqvClass;
1080 if ( func->env.lookup( typeInst->get_name(), eqvClass ) && eqvClass.type ) {
1081 if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.type ) ) {
1082 Alternative newFunc( *func );
1083 referenceToRvalueConversion( newFunc.expr );
1084 makeFunctionAlternatives( newFunc, function, argExpansions,
1085 std::back_inserter( candidates ) );
1086 } // if
1087 } // if
1088 }
1089 } catch ( SemanticError &e ) {
1090 errors.append( e );
1091 }
1092 } // for
1093
1094 // try each function operator ?() with each function alternative
1095 if ( ! funcOpFinder.alternatives.empty() ) {
1096 // add exploded function alternatives to front of argument list
1097 std::vector<ExplodedActual> funcE;
1098 funcE.reserve( funcFinder.alternatives.size() );
1099 for ( const Alternative& actual : funcFinder ) {
1100 funcE.emplace_back( actual, indexer );
1101 }
1102 argExpansions.insert( argExpansions.begin(), move(funcE) );
1103
1104 for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin();
1105 funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
1106 try {
1107 // check if type is a pointer to function
1108 if ( PointerType* pointer = dynamic_cast<PointerType*>(
1109 funcOp->expr->get_result()->stripReferences() ) ) {
1110 if ( FunctionType* function =
1111 dynamic_cast<FunctionType*>( pointer->get_base() ) ) {
1112 Alternative newFunc( *funcOp );
1113 referenceToRvalueConversion( newFunc.expr );
1114 makeFunctionAlternatives( newFunc, function, argExpansions,
1115 std::back_inserter( candidates ) );
1116 }
1117 }
1118 } catch ( SemanticError &e ) {
1119 errors.append( e );
1120 }
1121 }
1122 }
1123
1124 // Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
1125 if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }
1126
1127 // compute conversionsion costs
1128 for ( Alternative& withFunc : candidates ) {
1129 Cost cvtCost = computeApplicationConversionCost( withFunc, indexer );
1130
1131 PRINT(
1132 ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc.expr );
1133 PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
1134 FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() );
1135 std::cerr << "Case +++++++++++++ " << appExpr->get_function() << std::endl;
1136 std::cerr << "formals are:" << std::endl;
1137 printAll( function->get_parameters(), std::cerr, 8 );
1138 std::cerr << "actuals are:" << std::endl;
1139 printAll( appExpr->get_args(), std::cerr, 8 );
1140 std::cerr << "bindings are:" << std::endl;
1141 withFunc.env.print( std::cerr, 8 );
1142 std::cerr << "cost of conversion is:" << cvtCost << std::endl;
1143 )
1144 if ( cvtCost != Cost::infinity ) {
1145 withFunc.cvtCost = cvtCost;
1146 alternatives.push_back( withFunc );
1147 } // if
1148 } // for
1149
1150 candidates = move(alternatives);
1151
1152 // use a new list so that alternatives are not examined by addAnonConversions twice.
1153 AltList winners;
1154 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) );
1155
1156 // function may return struct or union value, in which case we need to add alternatives
1157 // for implicitconversions to each of the anonymous members, must happen after findMinCost
1158 // since anon conversions are never the cheapest expression
1159 for ( const Alternative & alt : winners ) {
1160 addAnonConversions( alt );
1161 }
1162 spliceBegin( alternatives, winners );
1163
1164 if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
1165 // xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
1166 // target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
1167 // forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
1168 // const char * x = "hello world";
1169 // unsigned char ch = x[0];
1170 // Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
1171 // with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
1172 // fix this issue in a more robust way.
1173 targetType = nullptr;
1174 visit( untypedExpr );
1175 }
1176 }
1177
1178 bool isLvalue( Expression *expr ) {
1179 // xxx - recurse into tuples?
1180 return expr->result && ( expr->get_result()->get_lvalue() || dynamic_cast< ReferenceType * >( expr->get_result() ) );
1181 }
1182
1183 void AlternativeFinder::visit( AddressExpr *addressExpr ) {
1184 AlternativeFinder finder( indexer, env );
1185 finder.find( addressExpr->get_arg() );
1186 for ( Alternative& alt : finder.alternatives ) {
1187 if ( isLvalue( alt.expr ) ) {
1188 alternatives.push_back(
1189 Alternative{ new AddressExpr( alt.expr->clone() ), alt.env, alt.cost } );
1190 } // if
1191 } // for
1192 }
1193
1194 void AlternativeFinder::visit( LabelAddressExpr * expr ) {
1195 alternatives.push_back( Alternative{ expr->clone(), env, Cost::zero } );
1196 }
1197
1198 Expression * restructureCast( Expression * argExpr, Type * toType ) {
1199 if ( argExpr->get_result()->size() > 1 && ! toType->isVoid() && ! dynamic_cast<ReferenceType *>( toType ) ) {
1200 // Argument expression is a tuple and the target type is not void and not a reference type.
1201 // Cast each member of the tuple to its corresponding target type, producing the tuple of those
1202 // cast expressions. If there are more components of the tuple than components in the target type,
1203 // then excess components do not come out in the result expression (but UniqueExprs ensure that
1204 // side effects will still be done).
1205 if ( Tuples::maybeImpureIgnoreUnique( argExpr ) ) {
1206 // expressions which may contain side effects require a single unique instance of the expression.
1207 argExpr = new UniqueExpr( argExpr );
1208 }
1209 std::list< Expression * > componentExprs;
1210 for ( unsigned int i = 0; i < toType->size(); i++ ) {
1211 // cast each component
1212 TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
1213 componentExprs.push_back( restructureCast( idx, toType->getComponent( i ) ) );
1214 }
1215 delete argExpr;
1216 assert( componentExprs.size() > 0 );
1217 // produce the tuple of casts
1218 return new TupleExpr( componentExprs );
1219 } else {
1220 // handle normally
1221 return new CastExpr( argExpr, toType->clone() );
1222 }
1223 }
1224
1225 void AlternativeFinder::visit( CastExpr *castExpr ) {
1226 Type *& toType = castExpr->get_result();
1227 assert( toType );
1228 toType = resolveTypeof( toType, indexer );
1229 SymTab::validateType( toType, &indexer );
1230 adjustExprType( toType, env, indexer );
1231
1232 AlternativeFinder finder( indexer, env );
1233 finder.targetType = toType;
1234 finder.findWithAdjustment( castExpr->get_arg() );
1235
1236 AltList candidates;
1237 for ( Alternative & alt : finder.alternatives ) {
1238 AssertionSet needAssertions, haveAssertions;
1239 OpenVarSet openVars;
1240
1241 // It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a
1242 // cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results
1243 // that are cast directly. The candidate is invalid if it has fewer results than there are types to cast
1244 // to.
1245 int discardedValues = alt.expr->get_result()->size() - castExpr->get_result()->size();
1246 if ( discardedValues < 0 ) continue;
1247 // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1248 // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1249 // unification run for side-effects
1250 unify( castExpr->get_result(), alt.expr->get_result(), alt.env, needAssertions,
1251 haveAssertions, openVars, indexer );
1252 Cost thisCost = castCost( alt.expr->get_result(), castExpr->get_result(), indexer,
1253 alt.env );
1254 PRINT(
1255 std::cerr << "working on cast with result: " << castExpr->result << std::endl;
1256 std::cerr << "and expr type: " << alt.expr->result << std::endl;
1257 std::cerr << "env: " << alt.env << std::endl;
1258 )
1259 if ( thisCost != Cost::infinity ) {
1260 PRINT(
1261 std::cerr << "has finite cost." << std::endl;
1262 )
1263 // count one safe conversion for each value that is thrown away
1264 thisCost.incSafe( discardedValues );
1265 Alternative newAlt( restructureCast( alt.expr->clone(), toType ), alt.env,
1266 alt.cost, thisCost );
1267 inferParameters( needAssertions, haveAssertions, newAlt, openVars,
1268 back_inserter( candidates ) );
1269 } // if
1270 } // for
1271
1272 // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1273 // cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice
1274 // selects first based on argument cost, then on conversion cost.
1275 AltList minArgCost;
1276 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1277 findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1278 }
1279
1280 void AlternativeFinder::visit( VirtualCastExpr * castExpr ) {
1281 assertf( castExpr->get_result(), "Implicate virtual cast targets not yet supported." );
1282 AlternativeFinder finder( indexer, env );
1283 // don't prune here, since it's guaranteed all alternatives will have the same type
1284 finder.findWithoutPrune( castExpr->get_arg() );
1285 for ( Alternative & alt : finder.alternatives ) {
1286 alternatives.push_back( Alternative(
1287 new VirtualCastExpr( alt.expr->clone(), castExpr->get_result()->clone() ),
1288 alt.env, alt.cost ) );
1289 }
1290 }
1291
1292 void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) {
1293 AlternativeFinder funcFinder( indexer, env );
1294 funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
1295 for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
1296 // it's okay for the aggregate expression to have reference type -- cast it to the base type to treat the aggregate as the referenced value
1297 std::unique_ptr<Expression> aggrExpr( agg->expr->clone() );
1298 Type * aggrType = aggrExpr->get_result();
1299 if ( dynamic_cast< ReferenceType * >( aggrType ) ) {
1300 aggrType = aggrType->stripReferences();
1301 aggrExpr.reset( new CastExpr( aggrExpr.release(), aggrType->clone() ) );
1302 }
1303 // find member of the given type
1304 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( aggrExpr->get_result() ) ) {
1305 addAggMembers( structInst, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
1306 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( aggrExpr->get_result() ) ) {
1307 addAggMembers( unionInst, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
1308 } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( aggrExpr->get_result() ) ) {
1309 addTupleMembers( tupleType, aggrExpr.get(), agg->cost, agg->env, memberExpr->get_member() );
1310 } // if
1311 } // for
1312 }
1313
1314 void AlternativeFinder::visit( MemberExpr *memberExpr ) {
1315 alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
1316 }
1317
1318 void AlternativeFinder::visit( NameExpr *nameExpr ) {
1319 std::list< SymTab::Indexer::IdData > declList;
1320 indexer.lookupId( nameExpr->get_name(), declList );
1321 PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; )
1322 for ( auto & data : declList ) {
1323 Expression * newExpr = data.combine();
1324 // xxx - add in extra cost for with-statement exprs?
1325 alternatives.push_back( Alternative( newExpr, env, Cost::zero ) );
1326 PRINT(
1327 std::cerr << "decl is ";
1328 data.id->print( std::cerr );
1329 std::cerr << std::endl;
1330 std::cerr << "newExpr is ";
1331 newExpr->print( std::cerr );
1332 std::cerr << std::endl;
1333 )
1334 renameTypes( alternatives.back().expr );
1335 addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
1336 } // for
1337 }
1338
1339 void AlternativeFinder::visit( VariableExpr *variableExpr ) {
1340 // not sufficient to clone here, because variable's type may have changed
1341 // since the VariableExpr was originally created.
1342 alternatives.push_back( Alternative( new VariableExpr( variableExpr->get_var() ), env, Cost::zero ) );
1343 }
1344
1345 void AlternativeFinder::visit( ConstantExpr *constantExpr ) {
1346 alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
1347 }
1348
1349 void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) {
1350 if ( sizeofExpr->get_isType() ) {
1351 Type * newType = sizeofExpr->get_type()->clone();
1352 alternatives.push_back( Alternative( new SizeofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1353 } else {
1354 // find all alternatives for the argument to sizeof
1355 AlternativeFinder finder( indexer, env );
1356 finder.find( sizeofExpr->get_expr() );
1357 // find the lowest cost alternative among the alternatives, otherwise ambiguous
1358 AltList winners;
1359 findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1360 if ( winners.size() != 1 ) {
1361 throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() );
1362 } // if
1363 // return the lowest cost alternative for the argument
1364 Alternative &choice = winners.front();
1365 referenceToRvalueConversion( choice.expr );
1366 alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
1367 } // if
1368 }
1369
1370 void AlternativeFinder::visit( AlignofExpr *alignofExpr ) {
1371 if ( alignofExpr->get_isType() ) {
1372 Type * newType = alignofExpr->get_type()->clone();
1373 alternatives.push_back( Alternative( new AlignofExpr( resolveTypeof( newType, indexer ) ), env, Cost::zero ) );
1374 } else {
1375 // find all alternatives for the argument to sizeof
1376 AlternativeFinder finder( indexer, env );
1377 finder.find( alignofExpr->get_expr() );
1378 // find the lowest cost alternative among the alternatives, otherwise ambiguous
1379 AltList winners;
1380 findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
1381 if ( winners.size() != 1 ) {
1382 throw SemanticError( "Ambiguous expression in alignof operand: ", alignofExpr->get_expr() );
1383 } // if
1384 // return the lowest cost alternative for the argument
1385 Alternative &choice = winners.front();
1386 referenceToRvalueConversion( choice.expr );
1387 alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
1388 } // if
1389 }
1390
1391 template< typename StructOrUnionType >
1392 void AlternativeFinder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
1393 std::list< Declaration* > members;
1394 aggInst->lookup( name, members );
1395 for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
1396 if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
1397 alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
1398 renameTypes( alternatives.back().expr );
1399 } else {
1400 assert( false );
1401 }
1402 }
1403 }
1404
1405 void AlternativeFinder::visit( UntypedOffsetofExpr *offsetofExpr ) {
1406 AlternativeFinder funcFinder( indexer, env );
1407 // xxx - resolveTypeof?
1408 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) {
1409 addOffsetof( structInst, offsetofExpr->get_member() );
1410 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) {
1411 addOffsetof( unionInst, offsetofExpr->get_member() );
1412 }
1413 }
1414
1415 void AlternativeFinder::visit( OffsetofExpr *offsetofExpr ) {
1416 alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
1417 }
1418
1419 void AlternativeFinder::visit( OffsetPackExpr *offsetPackExpr ) {
1420 alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
1421 }
1422
1423 namespace {
1424 void resolveAttr( SymTab::Indexer::IdData data, FunctionType *function, Type *argType, const TypeEnvironment &env, AlternativeFinder & finder ) {
1425 // assume no polymorphism
1426 // assume no implicit conversions
1427 assert( function->get_parameters().size() == 1 );
1428 PRINT(
1429 std::cerr << "resolvAttr: funcDecl is ";
1430 data.id->print( std::cerr );
1431 std::cerr << " argType is ";
1432 argType->print( std::cerr );
1433 std::cerr << std::endl;
1434 )
1435 const SymTab::Indexer & indexer = finder.get_indexer();
1436 AltList & alternatives = finder.get_alternatives();
1437 if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
1438 alternatives.push_back( Alternative( new AttrExpr( data.combine(), argType->clone() ), env, Cost::zero ) );
1439 for ( DeclarationWithType * retVal : function->returnVals ) {
1440 alternatives.back().expr->result = retVal->get_type()->clone();
1441 } // for
1442 } // if
1443 }
1444 }
1445
1446 void AlternativeFinder::visit( AttrExpr *attrExpr ) {
1447 // assume no 'pointer-to-attribute'
1448 NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
1449 assert( nameExpr );
1450 std::list< SymTab::Indexer::IdData > attrList;
1451 indexer.lookupId( nameExpr->get_name(), attrList );
1452 if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
1453 for ( auto & data : attrList ) {
1454 DeclarationWithType * id = data.id;
1455 // check if the type is function
1456 if ( FunctionType *function = dynamic_cast< FunctionType* >( id->get_type() ) ) {
1457 // assume exactly one parameter
1458 if ( function->get_parameters().size() == 1 ) {
1459 if ( attrExpr->get_isType() ) {
1460 resolveAttr( data, function, attrExpr->get_type(), env, *this );
1461 } else {
1462 AlternativeFinder finder( indexer, env );
1463 finder.find( attrExpr->get_expr() );
1464 for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
1465 if ( choice->expr->get_result()->size() == 1 ) {
1466 resolveAttr(data, function, choice->expr->get_result(), choice->env, *this );
1467 } // fi
1468 } // for
1469 } // if
1470 } // if
1471 } // if
1472 } // for
1473 } else {
1474 for ( auto & data : attrList ) {
1475 alternatives.push_back( Alternative( data.combine(), env, Cost::zero ) );
1476 renameTypes( alternatives.back().expr );
1477 } // for
1478 } // if
1479 }
1480
1481 void AlternativeFinder::visit( LogicalExpr *logicalExpr ) {
1482 AlternativeFinder firstFinder( indexer, env );
1483 firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
1484 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1485 AlternativeFinder secondFinder( indexer, first->env );
1486 secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
1487 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1488 LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() );
1489 alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) );
1490 }
1491 }
1492 }
1493
1494 void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) {
1495 // find alternatives for condition
1496 AlternativeFinder firstFinder( indexer, env );
1497 firstFinder.findWithAdjustment( conditionalExpr->get_arg1() );
1498 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1499 // find alternatives for true expression
1500 AlternativeFinder secondFinder( indexer, first->env );
1501 secondFinder.findWithAdjustment( conditionalExpr->get_arg2() );
1502 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1503 // find alterantives for false expression
1504 AlternativeFinder thirdFinder( indexer, second->env );
1505 thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() );
1506 for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) {
1507 // unify true and false types, then infer parameters to produce new alternatives
1508 OpenVarSet openVars;
1509 AssertionSet needAssertions, haveAssertions;
1510 Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost );
1511 Type* commonType = nullptr;
1512 if ( unify( second->expr->get_result(), third->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1513 ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() );
1514 newExpr->set_result( commonType ? commonType : second->expr->get_result()->clone() );
1515 // convert both options to the conditional result type
1516 newAlt.cost += computeExpressionConversionCost( newExpr->arg2, newExpr->result, indexer, newAlt.env );
1517 newAlt.cost += computeExpressionConversionCost( newExpr->arg3, newExpr->result, indexer, newAlt.env );
1518 newAlt.expr = newExpr;
1519 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1520 } // if
1521 } // for
1522 } // for
1523 } // for
1524 }
1525
1526 void AlternativeFinder::visit( CommaExpr *commaExpr ) {
1527 TypeEnvironment newEnv( env );
1528 Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
1529 AlternativeFinder secondFinder( indexer, newEnv );
1530 secondFinder.findWithAdjustment( commaExpr->get_arg2() );
1531 for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) {
1532 alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) );
1533 } // for
1534 delete newFirstArg;
1535 }
1536
1537 void AlternativeFinder::visit( RangeExpr * rangeExpr ) {
1538 // resolve low and high, accept alternatives whose low and high types unify
1539 AlternativeFinder firstFinder( indexer, env );
1540 firstFinder.findWithAdjustment( rangeExpr->get_low() );
1541 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1542 AlternativeFinder secondFinder( indexer, first->env );
1543 secondFinder.findWithAdjustment( rangeExpr->get_high() );
1544 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1545 OpenVarSet openVars;
1546 AssertionSet needAssertions, haveAssertions;
1547 Alternative newAlt( 0, second->env, first->cost + second->cost );
1548 Type* commonType = nullptr;
1549 if ( unify( first->expr->get_result(), second->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1550 RangeExpr *newExpr = new RangeExpr( first->expr->clone(), second->expr->clone() );
1551 newExpr->set_result( commonType ? commonType : first->expr->get_result()->clone() );
1552 newAlt.expr = newExpr;
1553 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1554 } // if
1555 } // for
1556 } // for
1557 }
1558
1559 void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) {
1560 std::vector< AlternativeFinder > subExprAlternatives;
1561 findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(),
1562 back_inserter( subExprAlternatives ) );
1563 std::vector< AltList > possibilities;
1564 combos( subExprAlternatives.begin(), subExprAlternatives.end(),
1565 back_inserter( possibilities ) );
1566 for ( const AltList& alts : possibilities ) {
1567 std::list< Expression * > exprs;
1568 makeExprList( alts, exprs );
1569
1570 TypeEnvironment compositeEnv;
1571 simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
1572 alternatives.push_back(
1573 Alternative{ new TupleExpr( exprs ), compositeEnv, sumCost( alts ) } );
1574 } // for
1575 }
1576
1577 void AlternativeFinder::visit( TupleExpr *tupleExpr ) {
1578 alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1579 }
1580
1581 void AlternativeFinder::visit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
1582 alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
1583 }
1584
1585 void AlternativeFinder::visit( ConstructorExpr * ctorExpr ) {
1586 AlternativeFinder finder( indexer, env );
1587 // don't prune here, since it's guaranteed all alternatives will have the same type
1588 // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
1589 finder.findWithoutPrune( ctorExpr->get_callExpr() );
1590 for ( Alternative & alt : finder.alternatives ) {
1591 alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
1592 }
1593 }
1594
1595 void AlternativeFinder::visit( TupleIndexExpr *tupleExpr ) {
1596 alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1597 }
1598
1599 void AlternativeFinder::visit( TupleAssignExpr *tupleAssignExpr ) {
1600 alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) );
1601 }
1602
1603 void AlternativeFinder::visit( UniqueExpr *unqExpr ) {
1604 AlternativeFinder finder( indexer, env );
1605 finder.findWithAdjustment( unqExpr->get_expr() );
1606 for ( Alternative & alt : finder.alternatives ) {
1607 // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
1608 UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
1609 alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
1610 }
1611 }
1612
1613 void AlternativeFinder::visit( StmtExpr *stmtExpr ) {
1614 StmtExpr * newStmtExpr = stmtExpr->clone();
1615 ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
1616 // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
1617 alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
1618 }
1619
1620 void AlternativeFinder::visit( UntypedInitExpr *initExpr ) {
1621 // handle each option like a cast
1622 AltList candidates;
1623 PRINT( std::cerr << "untyped init expr: " << initExpr << std::endl; )
1624 // O(N^2) checks of d-types with e-types
1625 for ( InitAlternative & initAlt : initExpr->get_initAlts() ) {
1626 Type * toType = resolveTypeof( initAlt.type->clone(), indexer );
1627 SymTab::validateType( toType, &indexer );
1628 adjustExprType( toType, env, indexer );
1629 // Ideally the call to findWithAdjustment could be moved out of the loop, but unfortunately it currently has to occur inside or else
1630 // polymorphic return types are not properly bound to the initialization type, since return type variables are only open for the duration of resolving
1631 // the UntypedExpr. This is only actually an issue in initialization contexts that allow more than one possible initialization type, but it is still suboptimal.
1632 AlternativeFinder finder( indexer, env );
1633 finder.targetType = toType;
1634 finder.findWithAdjustment( initExpr->get_expr() );
1635 for ( Alternative & alt : finder.get_alternatives() ) {
1636 TypeEnvironment newEnv( alt.env );
1637 AssertionSet needAssertions, haveAssertions;
1638 OpenVarSet openVars; // find things in env that don't have a "representative type" and claim those are open vars?
1639 PRINT( std::cerr << " @ " << toType << " " << initAlt.designation << std::endl; )
1640 // It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a
1641 // cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results
1642 // that are cast directly. The candidate is invalid if it has fewer results than there are types to cast
1643 // to.
1644 int discardedValues = alt.expr->get_result()->size() - toType->size();
1645 if ( discardedValues < 0 ) continue;
1646 // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1647 // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1648 // unification run for side-effects
1649 unify( toType, alt.expr->get_result(), newEnv, needAssertions, haveAssertions, openVars, indexer ); // xxx - do some inspecting on this line... why isn't result bound to initAlt.type??
1650
1651 Cost thisCost = castCost( alt.expr->get_result(), toType, indexer, newEnv );
1652 if ( thisCost != Cost::infinity ) {
1653 // count one safe conversion for each value that is thrown away
1654 thisCost.incSafe( discardedValues );
1655 Alternative newAlt( new InitExpr( restructureCast( alt.expr->clone(), toType ), initAlt.designation->clone() ), newEnv, alt.cost, thisCost );
1656 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) );
1657 }
1658 }
1659 }
1660
1661 // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1662 // cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice
1663 // selects first based on argument cost, then on conversion cost.
1664 AltList minArgCost;
1665 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1666 findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1667 }
1668} // namespace ResolvExpr
1669
1670// Local Variables: //
1671// tab-width: 4 //
1672// mode: c++ //
1673// compile-command: "make install" //
1674// End: //
Note: See TracBrowser for help on using the repository browser.