source: src/ResolvExpr/AlternativeFinder.cc@ 88d1066

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 88d1066 was 32b8144, checked in by Rob Schluntz <rschlunt@…>, 9 years ago

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