source: src/ResolvExpr/AlternativeFinder.cc@ a8b27c6

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 a8b27c6 was a8b27c6, checked in by Aaron Moss <a3moss@…>, 8 years ago

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