source: src/ResolvExpr/AlternativeFinder.cc@ 579263a

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

Merge branch 'master' into designations

Conflicts:

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