source: src/ResolvExpr/AlternativeFinder.cc@ 946bcca

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 946bcca was 946bcca, checked in by Rob Schluntz <rschlunt@…>, 8 years ago

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