source: src/ResolvExpr/AlternativeFinder.cc@ f8b6d921

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 f8b6d921 was 6c3a988f, checked in by Rob Schluntz <rschlunt@…>, 9 years ago

fix inferred parameter data structures to correctly associate parameters with the entity that requested them, modify tuple specialization and unification to work with self-recursive assertions
  • Property mode set to 100644
File size: 49.1 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 // so far, only constant expressions are accepted as default values
406 if ( ConstantExpr *cnstexpr = dynamic_cast<ConstantExpr *>( si->get_value()) ) {
407 if ( Constant *cnst = dynamic_cast<Constant *>( cnstexpr->get_constant() ) ) {
408 if ( unify( formalType, cnst->get_type(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
409 // xxx - Don't know if this is right
410 *out++ = cnstexpr->clone();
411 return true;
412 } // if
413 } // if
414 } // if
415 } // if
416 return false;
417 } // if
418 return true;
419 }
420
421 bool AlternativeFinder::instantiateFunction( std::list< DeclarationWithType* >& formals, const AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave, AltList & out ) {
422 simpleCombineEnvironments( actuals.begin(), actuals.end(), resultEnv );
423 // make sure we don't widen any existing bindings
424 for ( TypeEnvironment::iterator i = resultEnv.begin(); i != resultEnv.end(); ++i ) {
425 i->allowWidening = false;
426 }
427 resultEnv.extractOpenVars( openVars );
428
429 // flatten actuals so that each actual has an atomic (non-tuple) type
430 AltList exploded;
431 Tuples::explode( actuals, indexer, back_inserter( exploded ) );
432
433 AltList::iterator actualExpr = exploded.begin();
434 AltList::iterator actualEnd = exploded.end();
435 for ( DeclarationWithType * formal : formals ) {
436 // match flattened actuals with formal parameters - actuals will be grouped to match
437 // with formals as appropriate
438 Cost cost;
439 std::list< Expression * > newExprs;
440 ObjectDecl * obj = safe_dynamic_cast< ObjectDecl * >( formal );
441 if ( ! instantiateArgument( obj->get_type(), obj->get_init(), actualExpr, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( newExprs ) ) ) {
442 deleteAll( newExprs );
443 return false;
444 }
445 // success - produce argument as a new alternative
446 assert( newExprs.size() == 1 );
447 out.push_back( Alternative( newExprs.front(), resultEnv, cost ) );
448 }
449 if ( actualExpr != actualEnd ) {
450 // there are still actuals remaining, but we've run out of formal parameters to match against
451 // this is okay only if the function is variadic
452 if ( ! isVarArgs ) {
453 return false;
454 }
455 out.splice( out.end(), exploded, actualExpr, actualEnd );
456 }
457 return true;
458 }
459
460 // /// Map of declaration uniqueIds (intended to be the assertions in an AssertionSet) to their parents and the number of times they've been included
461 //typedef std::unordered_map< UniqueId, std::unordered_map< UniqueId, unsigned > > AssertionParentSet;
462
463 static const int recursionLimit = /*10*/ 4; ///< Limit to depth of recursion satisfaction
464 //static const unsigned recursionParentLimit = 1; ///< Limit to the number of times an assertion can recursively use itself
465
466 void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) {
467 for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) {
468 if ( i->second.isUsed ) {
469 i->first->accept( indexer );
470 }
471 }
472 }
473
474 template< typename ForwardIterator, typename OutputIterator >
475 void inferRecursive( ForwardIterator begin, ForwardIterator end, const Alternative &newAlt, OpenVarSet &openVars, const SymTab::Indexer &decls, const AssertionSet &newNeed, /*const AssertionParentSet &needParents,*/
476 int level, const SymTab::Indexer &indexer, OutputIterator out ) {
477 if ( begin == end ) {
478 if ( newNeed.empty() ) {
479 PRINT(
480 std::cerr << "all assertions satisfied, output alternative: ";
481 newAlt.print( std::cerr );
482 std::cerr << std::endl;
483 );
484 *out++ = newAlt;
485 return;
486 } else if ( level >= recursionLimit ) {
487 throw SemanticError( "Too many recursive assertions" );
488 } else {
489 AssertionSet newerNeed;
490 PRINT(
491 std::cerr << "recursing with new set:" << std::endl;
492 printAssertionSet( newNeed, std::cerr, 8 );
493 )
494 inferRecursive( newNeed.begin(), newNeed.end(), newAlt, openVars, decls, newerNeed, /*needParents,*/ level+1, indexer, out );
495 return;
496 }
497 }
498
499 ForwardIterator cur = begin++;
500 if ( ! cur->second.isUsed ) {
501 inferRecursive( begin, end, newAlt, openVars, decls, newNeed, /*needParents,*/ level, indexer, out );
502 return; // xxx - should this continue? previously this wasn't here, and it looks like it should be
503 }
504 DeclarationWithType *curDecl = cur->first;
505
506 PRINT(
507 std::cerr << "inferRecursive: assertion is ";
508 curDecl->print( std::cerr );
509 std::cerr << std::endl;
510 )
511 std::list< DeclarationWithType* > candidates;
512 decls.lookupId( curDecl->get_name(), candidates );
513/// if ( candidates.empty() ) { std::cerr << "no candidates!" << std::endl; }
514 for ( std::list< DeclarationWithType* >::const_iterator candidate = candidates.begin(); candidate != candidates.end(); ++candidate ) {
515 PRINT(
516 std::cerr << "inferRecursive: candidate is ";
517 (*candidate)->print( std::cerr );
518 std::cerr << std::endl;
519 )
520
521 AssertionSet newHave, newerNeed( newNeed );
522 TypeEnvironment newEnv( newAlt.env );
523 OpenVarSet newOpenVars( openVars );
524 Type *adjType = (*candidate)->get_type()->clone();
525 adjustExprType( adjType, newEnv, indexer );
526 adjType->accept( global_renamer );
527 PRINT(
528 std::cerr << "unifying ";
529 curDecl->get_type()->print( std::cerr );
530 std::cerr << " with ";
531 adjType->print( std::cerr );
532 std::cerr << std::endl;
533 )
534 if ( unify( curDecl->get_type(), adjType, newEnv, newerNeed, newHave, newOpenVars, indexer ) ) {
535 PRINT(
536 std::cerr << "success!" << std::endl;
537 )
538 SymTab::Indexer newDecls( decls );
539 addToIndexer( newHave, newDecls );
540 Alternative newerAlt( newAlt );
541 newerAlt.env = newEnv;
542 assert( (*candidate)->get_uniqueId() );
543 DeclarationWithType *candDecl = static_cast< DeclarationWithType* >( Declaration::declFromId( (*candidate)->get_uniqueId() ) );
544
545 // everything with an empty idChain was pulled in by the current assertion.
546 // add current assertion's idChain + current assertion's ID so that the correct inferParameters can be found.
547 for ( auto & a : newerNeed ) {
548 if ( a.second.idChain.empty() ) {
549 a.second.idChain = cur->second.idChain;
550 a.second.idChain.push_back( curDecl->get_uniqueId() );
551 }
552 }
553
554 //AssertionParentSet newNeedParents( needParents );
555 // skip repeatingly-self-recursive assertion satisfaction
556 // DOESN'T WORK: grandchild nodes conflict with their cousins
557 //if ( newNeedParents[ curDecl->get_uniqueId() ][ candDecl->get_uniqueId() ]++ > recursionParentLimit ) continue;
558 Expression *varExpr = new VariableExpr( candDecl );
559 delete varExpr->get_result();
560 varExpr->set_result( adjType->clone() );
561 PRINT(
562 std::cerr << "satisfying assertion " << curDecl->get_uniqueId() << " ";
563 curDecl->print( std::cerr );
564 std::cerr << " with declaration " << (*candidate)->get_uniqueId() << " ";
565 (*candidate)->print( std::cerr );
566 std::cerr << std::endl;
567 )
568 ApplicationExpr *appExpr = static_cast< ApplicationExpr* >( newerAlt.expr );
569 // 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).
570 InferredParams * inferParameters = &appExpr->get_inferParams();
571 for ( UniqueId id : cur->second.idChain ) {
572 inferParameters = (*inferParameters)[ id ].inferParams.get();
573 }
574 // XXX: this is a memory leak, but adjType can't be deleted because it might contain assertions
575 (*inferParameters)[ curDecl->get_uniqueId() ] = ParamEntry( (*candidate)->get_uniqueId(), adjType->clone(), curDecl->get_type()->clone(), varExpr );
576 inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, /*newNeedParents,*/ level, indexer, out );
577 } else {
578 delete adjType;
579 }
580 }
581 }
582
583 template< typename OutputIterator >
584 void AlternativeFinder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) {
585// PRINT(
586// std::cerr << "inferParameters: assertions needed are" << std::endl;
587// printAll( need, std::cerr, 8 );
588// )
589 SymTab::Indexer decls( indexer );
590 PRINT(
591 std::cerr << "============= original indexer" << std::endl;
592 indexer.print( std::cerr );
593 std::cerr << "============= new indexer" << std::endl;
594 decls.print( std::cerr );
595 )
596 addToIndexer( have, decls );
597 AssertionSet newNeed;
598 //AssertionParentSet needParents;
599 inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, /*needParents,*/ 0, indexer, out );
600// PRINT(
601// std::cerr << "declaration 14 is ";
602// Declaration::declFromId
603// *out++ = newAlt;
604// )
605 }
606
607 template< typename OutputIterator >
608 void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const AltList &actualAlt, OutputIterator out ) {
609 OpenVarSet openVars;
610 AssertionSet resultNeed, resultHave;
611 TypeEnvironment resultEnv;
612 makeUnifiableVars( funcType, openVars, resultNeed );
613 AltList instantiatedActuals; // filled by instantiate function
614 if ( targetType && ! targetType->isVoid() && ! funcType->get_returnVals().empty() ) {
615 // attempt to narrow based on expected target type
616 Type * returnType = funcType->get_returnVals().front()->get_type();
617 if ( ! unify( returnType, targetType, resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
618 // unification failed, don't pursue this alternative
619 return;
620 }
621 }
622
623 if ( instantiateFunction( funcType->get_parameters(), actualAlt, funcType->get_isVarArgs(), openVars, resultEnv, resultNeed, resultHave, instantiatedActuals ) ) {
624 ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
625 Alternative newAlt( appExpr, resultEnv, sumCost( instantiatedActuals ) );
626 makeExprList( instantiatedActuals, appExpr->get_args() );
627 PRINT(
628 std::cerr << "need assertions:" << std::endl;
629 printAssertionSet( resultNeed, std::cerr, 8 );
630 )
631 inferParameters( resultNeed, resultHave, newAlt, openVars, out );
632 }
633 }
634
635 void AlternativeFinder::visit( UntypedExpr *untypedExpr ) {
636 bool doneInit = false;
637 AlternativeFinder funcOpFinder( indexer, env );
638
639 AlternativeFinder funcFinder( indexer, env );
640
641 {
642 std::string fname = InitTweak::getFunctionName( untypedExpr );
643 if ( fname == "&&" ) {
644 VoidType v = Type::Qualifiers(); // resolve to type void *
645 PointerType pt( Type::Qualifiers(), v.clone() );
646 UntypedExpr *vexpr = untypedExpr->clone();
647 vexpr->set_result( pt.clone() );
648 alternatives.push_back( Alternative( vexpr, env, Cost()) );
649 return;
650 }
651 }
652
653 funcFinder.findWithAdjustment( untypedExpr->get_function() );
654 std::list< AlternativeFinder > argAlternatives;
655 findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), back_inserter( argAlternatives ) );
656
657 std::list< AltList > possibilities;
658 combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) );
659
660 // take care of possible tuple assignments
661 // if not tuple assignment, assignment is taken care of as a normal function call
662 Tuples::handleTupleAssignment( *this, untypedExpr, possibilities );
663
664 AltList candidates;
665 SemanticError errors;
666 for ( AltList::const_iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) {
667 try {
668 PRINT(
669 std::cerr << "working on alternative: " << std::endl;
670 func->print( std::cerr, 8 );
671 )
672 // check if the type is pointer to function
673 PointerType *pointer;
674 if ( ( pointer = dynamic_cast< PointerType* >( func->expr->get_result() ) ) ) {
675 if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
676 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
677 // XXX
678 //Designators::check_alternative( function, *actualAlt );
679 makeFunctionAlternatives( *func, function, *actualAlt, std::back_inserter( candidates ) );
680 }
681 } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( pointer->get_base() ) ) {
682 EqvClass eqvClass;
683 if ( func->env.lookup( typeInst->get_name(), eqvClass ) && eqvClass.type ) {
684 if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.type ) ) {
685 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
686 makeFunctionAlternatives( *func, function, *actualAlt, std::back_inserter( candidates ) );
687 } // for
688 } // if
689 } // if
690 } // if
691 } else {
692 // seek a function operator that's compatible
693 if ( ! doneInit ) {
694 doneInit = true;
695 NameExpr *opExpr = new NameExpr( "?()" );
696 try {
697 funcOpFinder.findWithAdjustment( opExpr );
698 } catch( SemanticError &e ) {
699 // it's ok if there aren't any defined function ops
700 }
701 PRINT(
702 std::cerr << "known function ops:" << std::endl;
703 printAlts( funcOpFinder.alternatives, std::cerr, 8 );
704 )
705 }
706
707 for ( AltList::const_iterator funcOp = funcOpFinder.alternatives.begin(); funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
708 // check if the type is pointer to function
709 PointerType *pointer;
710 if ( ( pointer = dynamic_cast< PointerType* >( funcOp->expr->get_result() ) ) ) {
711 if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
712 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
713 AltList currentAlt;
714 currentAlt.push_back( *func );
715 currentAlt.insert( currentAlt.end(), actualAlt->begin(), actualAlt->end() );
716 makeFunctionAlternatives( *funcOp, function, currentAlt, std::back_inserter( candidates ) );
717 } // for
718 } // if
719 } // if
720 } // for
721 } // if
722 } catch ( SemanticError &e ) {
723 errors.append( e );
724 }
725 } // for
726
727 // Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
728 if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }
729
730 for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) {
731 Cost cvtCost = computeConversionCost( *withFunc, indexer );
732
733 PRINT(
734 ApplicationExpr *appExpr = safe_dynamic_cast< ApplicationExpr* >( withFunc->expr );
735 PointerType *pointer = safe_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
736 FunctionType *function = safe_dynamic_cast< FunctionType* >( pointer->get_base() );
737 std::cerr << "Case +++++++++++++" << std::endl;
738 std::cerr << "formals are:" << std::endl;
739 printAll( function->get_parameters(), std::cerr, 8 );
740 std::cerr << "actuals are:" << std::endl;
741 printAll( appExpr->get_args(), std::cerr, 8 );
742 std::cerr << "bindings are:" << std::endl;
743 withFunc->env.print( std::cerr, 8 );
744 std::cerr << "cost of conversion is:" << cvtCost << std::endl;
745 )
746 if ( cvtCost != Cost::infinity ) {
747 withFunc->cvtCost = cvtCost;
748 alternatives.push_back( *withFunc );
749 } // if
750 } // for
751 candidates.clear();
752 candidates.splice( candidates.end(), alternatives );
753
754 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( alternatives ) );
755
756 if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
757 // xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
758 // target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
759 // forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
760 // const char * x = "hello world";
761 // unsigned char ch = x[0];
762 // Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
763 // with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
764 // fix this issue in a more robust way.
765 targetType = nullptr;
766 visit( untypedExpr );
767 }
768 }
769
770 bool isLvalue( Expression *expr ) {
771 // xxx - recurse into tuples?
772 return expr->has_result() && expr->get_result()->get_isLvalue();
773 }
774
775 void AlternativeFinder::visit( AddressExpr *addressExpr ) {
776 AlternativeFinder finder( indexer, env );
777 finder.find( addressExpr->get_arg() );
778 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
779 if ( isLvalue( i->expr ) ) {
780 alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) );
781 } // if
782 } // for
783 }
784
785 void AlternativeFinder::visit( CastExpr *castExpr ) {
786 Type *& toType = castExpr->get_result();
787 assert( toType );
788 toType = resolveTypeof( toType, indexer );
789 SymTab::validateType( toType, &indexer );
790 adjustExprType( toType, env, indexer );
791
792 AlternativeFinder finder( indexer, env );
793 finder.targetType = toType;
794 finder.findWithAdjustment( castExpr->get_arg() );
795
796 AltList candidates;
797 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
798 AssertionSet needAssertions, haveAssertions;
799 OpenVarSet openVars;
800
801 // It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a
802 // cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results
803 // that are cast directly. The candidate is invalid if it has fewer results than there are types to cast
804 // to.
805 int discardedValues = (*i).expr->get_result()->size() - castExpr->get_result()->size();
806 if ( discardedValues < 0 ) continue;
807 // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
808 // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
809 // unification run for side-effects
810 unify( castExpr->get_result(), (*i).expr->get_result(), i->env, needAssertions, haveAssertions, openVars, indexer );
811 Cost thisCost = castCost( (*i).expr->get_result(), castExpr->get_result(), indexer, i->env );
812 if ( thisCost != Cost::infinity ) {
813 // count one safe conversion for each value that is thrown away
814 thisCost += Cost( 0, 0, discardedValues );
815
816 Expression * argExpr = i->expr->clone();
817 if ( argExpr->get_result()->size() > 1 && ! castExpr->get_result()->isVoid() ) {
818 // Argument expression is a tuple and the target type is not void. Cast each member of the tuple
819 // to its corresponding target type, producing the tuple of those cast expressions. If there are
820 // more components of the tuple than components in the target type, then excess components do not
821 // come out in the result expression (but UniqueExprs ensure that side effects will still be done).
822 if ( Tuples::maybeImpure( argExpr ) && ! dynamic_cast< UniqueExpr * >( argExpr ) ) {
823 // expressions which may contain side effects require a single unique instance of the expression.
824 argExpr = new UniqueExpr( argExpr );
825 }
826 std::list< Expression * > componentExprs;
827 for ( unsigned int i = 0; i < castExpr->get_result()->size(); i++ ) {
828 // cast each component
829 TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
830 componentExprs.push_back( new CastExpr( idx, castExpr->get_result()->getComponent( i )->clone() ) );
831 }
832 delete argExpr;
833 assert( componentExprs.size() > 0 );
834 // produce the tuple of casts
835 candidates.push_back( Alternative( new TupleExpr( componentExprs ), i->env, i->cost, thisCost ) );
836 } else {
837 // handle normally
838 candidates.push_back( Alternative( new CastExpr( argExpr->clone(), toType->clone() ), i->env, i->cost, thisCost ) );
839 }
840 } // if
841 } // for
842
843 // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
844 // cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice
845 // selects first based on argument cost, then on conversion cost.
846 AltList minArgCost;
847 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
848 findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
849 }
850
851 void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) {
852 AlternativeFinder funcFinder( indexer, env );
853 funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
854 for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
855 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( agg->expr->get_result() ) ) {
856 addAggMembers( structInst, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
857 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( agg->expr->get_result() ) ) {
858 addAggMembers( unionInst, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
859 } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( agg->expr->get_result() ) ) {
860 addTupleMembers( tupleType, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
861 } // if
862 } // for
863 }
864
865 void AlternativeFinder::visit( MemberExpr *memberExpr ) {
866 alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
867 }
868
869 void AlternativeFinder::visit( NameExpr *nameExpr ) {
870 std::list< DeclarationWithType* > declList;
871 indexer.lookupId( nameExpr->get_name(), declList );
872 PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; )
873 for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) {
874 VariableExpr newExpr( *i, nameExpr->get_argName() );
875 alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) );
876 PRINT(
877 std::cerr << "decl is ";
878 (*i)->print( std::cerr );
879 std::cerr << std::endl;
880 std::cerr << "newExpr is ";
881 newExpr.print( std::cerr );
882 std::cerr << std::endl;
883 )
884 renameTypes( alternatives.back().expr );
885 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( (*i)->get_type() ) ) {
886 NameExpr nameExpr( "" );
887 addAggMembers( structInst, &newExpr, Cost( 0, 0, 1 ), env, &nameExpr );
888 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( (*i)->get_type() ) ) {
889 NameExpr nameExpr( "" );
890 addAggMembers( unionInst, &newExpr, Cost( 0, 0, 1 ), env, &nameExpr );
891 } // if
892 } // for
893 }
894
895 void AlternativeFinder::visit( VariableExpr *variableExpr ) {
896 // not sufficient to clone here, because variable's type may have changed
897 // since the VariableExpr was originally created.
898 alternatives.push_back( Alternative( new VariableExpr( variableExpr->get_var() ), env, Cost::zero ) );
899 }
900
901 void AlternativeFinder::visit( ConstantExpr *constantExpr ) {
902 alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
903 }
904
905 void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) {
906 if ( sizeofExpr->get_isType() ) {
907 // xxx - resolveTypeof?
908 alternatives.push_back( Alternative( sizeofExpr->clone(), env, Cost::zero ) );
909 } else {
910 // find all alternatives for the argument to sizeof
911 AlternativeFinder finder( indexer, env );
912 finder.find( sizeofExpr->get_expr() );
913 // find the lowest cost alternative among the alternatives, otherwise ambiguous
914 AltList winners;
915 findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
916 if ( winners.size() != 1 ) {
917 throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() );
918 } // if
919 // return the lowest cost alternative for the argument
920 Alternative &choice = winners.front();
921 alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
922 } // if
923 }
924
925 void AlternativeFinder::visit( AlignofExpr *alignofExpr ) {
926 if ( alignofExpr->get_isType() ) {
927 // xxx - resolveTypeof?
928 alternatives.push_back( Alternative( alignofExpr->clone(), env, Cost::zero ) );
929 } else {
930 // find all alternatives for the argument to sizeof
931 AlternativeFinder finder( indexer, env );
932 finder.find( alignofExpr->get_expr() );
933 // find the lowest cost alternative among the alternatives, otherwise ambiguous
934 AltList winners;
935 findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
936 if ( winners.size() != 1 ) {
937 throw SemanticError( "Ambiguous expression in alignof operand: ", alignofExpr->get_expr() );
938 } // if
939 // return the lowest cost alternative for the argument
940 Alternative &choice = winners.front();
941 alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
942 } // if
943 }
944
945 template< typename StructOrUnionType >
946 void AlternativeFinder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
947 std::list< Declaration* > members;
948 aggInst->lookup( name, members );
949 for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
950 if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
951 alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
952 renameTypes( alternatives.back().expr );
953 } else {
954 assert( false );
955 }
956 }
957 }
958
959 void AlternativeFinder::visit( UntypedOffsetofExpr *offsetofExpr ) {
960 AlternativeFinder funcFinder( indexer, env );
961 // xxx - resolveTypeof?
962 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) {
963 addOffsetof( structInst, offsetofExpr->get_member() );
964 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) {
965 addOffsetof( unionInst, offsetofExpr->get_member() );
966 }
967 }
968
969 void AlternativeFinder::visit( OffsetofExpr *offsetofExpr ) {
970 alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
971 }
972
973 void AlternativeFinder::visit( OffsetPackExpr *offsetPackExpr ) {
974 alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
975 }
976
977 void AlternativeFinder::resolveAttr( DeclarationWithType *funcDecl, FunctionType *function, Type *argType, const TypeEnvironment &env ) {
978 // assume no polymorphism
979 // assume no implicit conversions
980 assert( function->get_parameters().size() == 1 );
981 PRINT(
982 std::cerr << "resolvAttr: funcDecl is ";
983 funcDecl->print( std::cerr );
984 std::cerr << " argType is ";
985 argType->print( std::cerr );
986 std::cerr << std::endl;
987 )
988 if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
989 alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) );
990 for ( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) {
991 alternatives.back().expr->set_result( (*i)->get_type()->clone() );
992 } // for
993 } // if
994 }
995
996 void AlternativeFinder::visit( AttrExpr *attrExpr ) {
997 // assume no 'pointer-to-attribute'
998 NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
999 assert( nameExpr );
1000 std::list< DeclarationWithType* > attrList;
1001 indexer.lookupId( nameExpr->get_name(), attrList );
1002 if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
1003 for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1004 // check if the type is function
1005 if ( FunctionType *function = dynamic_cast< FunctionType* >( (*i)->get_type() ) ) {
1006 // assume exactly one parameter
1007 if ( function->get_parameters().size() == 1 ) {
1008 if ( attrExpr->get_isType() ) {
1009 resolveAttr( *i, function, attrExpr->get_type(), env );
1010 } else {
1011 AlternativeFinder finder( indexer, env );
1012 finder.find( attrExpr->get_expr() );
1013 for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
1014 if ( choice->expr->get_result()->size() == 1 ) {
1015 resolveAttr(*i, function, choice->expr->get_result(), choice->env );
1016 } // fi
1017 } // for
1018 } // if
1019 } // if
1020 } // if
1021 } // for
1022 } else {
1023 for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1024 VariableExpr newExpr( *i );
1025 alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) );
1026 renameTypes( alternatives.back().expr );
1027 } // for
1028 } // if
1029 }
1030
1031 void AlternativeFinder::visit( LogicalExpr *logicalExpr ) {
1032 AlternativeFinder firstFinder( indexer, env );
1033 firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
1034 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1035 AlternativeFinder secondFinder( indexer, first->env );
1036 secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
1037 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1038 LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() );
1039 alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) );
1040 }
1041 }
1042 }
1043
1044 void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) {
1045 AlternativeFinder firstFinder( indexer, env );
1046 firstFinder.findWithAdjustment( conditionalExpr->get_arg1() );
1047 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1048 AlternativeFinder secondFinder( indexer, first->env );
1049 secondFinder.findWithAdjustment( conditionalExpr->get_arg2() );
1050 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1051 AlternativeFinder thirdFinder( indexer, second->env );
1052 thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() );
1053 for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) {
1054 OpenVarSet openVars;
1055 AssertionSet needAssertions, haveAssertions;
1056 Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost );
1057 Type* commonType = nullptr;
1058 if ( unify( second->expr->get_result(), third->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1059 ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() );
1060 newExpr->set_result( commonType ? commonType : second->expr->get_result()->clone() );
1061 newAlt.expr = newExpr;
1062 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1063 } // if
1064 } // for
1065 } // for
1066 } // for
1067 }
1068
1069 void AlternativeFinder::visit( CommaExpr *commaExpr ) {
1070 TypeEnvironment newEnv( env );
1071 Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
1072 AlternativeFinder secondFinder( indexer, newEnv );
1073 secondFinder.findWithAdjustment( commaExpr->get_arg2() );
1074 for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) {
1075 alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) );
1076 } // for
1077 delete newFirstArg;
1078 }
1079
1080 void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) {
1081 std::list< AlternativeFinder > subExprAlternatives;
1082 findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) );
1083 std::list< AltList > possibilities;
1084 combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) );
1085 for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) {
1086 std::list< Expression * > exprs;
1087 makeExprList( *i, exprs );
1088
1089 TypeEnvironment compositeEnv;
1090 simpleCombineEnvironments( i->begin(), i->end(), compositeEnv );
1091 alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) );
1092 } // for
1093 }
1094
1095 void AlternativeFinder::visit( TupleExpr *tupleExpr ) {
1096 alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1097 }
1098
1099 void AlternativeFinder::visit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
1100 alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
1101 }
1102
1103 void AlternativeFinder::visit( ConstructorExpr * ctorExpr ) {
1104 AlternativeFinder finder( indexer, env );
1105 // don't prune here, since it's guaranteed all alternatives will have the same type
1106 // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
1107 finder.findWithAdjustment( ctorExpr->get_callExpr(), false );
1108 for ( Alternative & alt : finder.alternatives ) {
1109 alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
1110 }
1111 }
1112
1113 void AlternativeFinder::visit( TupleIndexExpr *tupleExpr ) {
1114 alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1115 }
1116
1117 void AlternativeFinder::visit( TupleAssignExpr *tupleAssignExpr ) {
1118 alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) );
1119 }
1120
1121 void AlternativeFinder::visit( UniqueExpr *unqExpr ) {
1122 AlternativeFinder finder( indexer, env );
1123 finder.findWithAdjustment( unqExpr->get_expr() );
1124 for ( Alternative & alt : finder.alternatives ) {
1125 // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
1126 UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
1127 alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
1128 }
1129 }
1130
1131 void AlternativeFinder::visit( StmtExpr *stmtExpr ) {
1132 StmtExpr * newStmtExpr = stmtExpr->clone();
1133 ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
1134 // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
1135 alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
1136 }
1137
1138} // namespace ResolvExpr
1139
1140// Local Variables: //
1141// tab-width: 4 //
1142// mode: c++ //
1143// compile-command: "make install" //
1144// End: //
Note: See TracBrowser for help on using the repository browser.