source: src/ResolvExpr/AlternativeFinder.cc@ f7cb0bc

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

Big push on designations and initialization: works with generic types, tuples, arrays, tests pass.
Refactor guard_value_impl.
Add list of declarations to TupleType.
  • Property mode set to 100644
File size: 54.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 ) {
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 Expression * restructureCast( Expression * argExpr, Type * toType ) {
812 if ( argExpr->get_result()->size() > 1 && ! toType->isVoid() ) {
813 // Argument expression is a tuple and the target type is not void. Cast each member of the tuple
814 // to its corresponding target type, producing the tuple of those cast expressions. If there are
815 // more components of the tuple than components in the target type, then excess components do not
816 // come out in the result expression (but UniqueExprs ensure that side effects will still be done).
817 if ( Tuples::maybeImpure( argExpr ) && ! dynamic_cast< UniqueExpr * >( argExpr ) ) {
818 // expressions which may contain side effects require a single unique instance of the expression.
819 argExpr = new UniqueExpr( argExpr );
820 }
821 std::list< Expression * > componentExprs;
822 for ( unsigned int i = 0; i < toType->size(); i++ ) {
823 // cast each component
824 TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
825 componentExprs.push_back( restructureCast( idx, toType->getComponent( i ) ) );
826 }
827 delete argExpr;
828 assert( componentExprs.size() > 0 );
829 // produce the tuple of casts
830 return new TupleExpr( componentExprs );
831 } else {
832 // handle normally
833 return new CastExpr( argExpr, toType->clone() );
834 }
835 }
836
837 void AlternativeFinder::visit( CastExpr *castExpr ) {
838 Type *& toType = castExpr->get_result();
839 assert( toType );
840 toType = resolveTypeof( toType, indexer );
841 SymTab::validateType( toType, &indexer );
842 adjustExprType( toType, env, indexer );
843
844 AlternativeFinder finder( indexer, env );
845 finder.targetType = toType;
846 finder.findWithAdjustment( castExpr->get_arg() );
847
848 AltList candidates;
849 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
850 AssertionSet needAssertions, haveAssertions;
851 OpenVarSet openVars;
852
853 // It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a
854 // cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results
855 // that are cast directly. The candidate is invalid if it has fewer results than there are types to cast
856 // to.
857 int discardedValues = (*i).expr->get_result()->size() - castExpr->get_result()->size();
858 if ( discardedValues < 0 ) continue;
859 // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
860 // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
861 // unification run for side-effects
862 unify( castExpr->get_result(), (*i).expr->get_result(), i->env, needAssertions, haveAssertions, openVars, indexer );
863 Cost thisCost = castCost( (*i).expr->get_result(), castExpr->get_result(), indexer, i->env );
864 if ( thisCost != Cost::infinity ) {
865 // count one safe conversion for each value that is thrown away
866 thisCost += Cost( 0, 0, discardedValues );
867
868 candidates.push_back( Alternative( restructureCast( i->expr->clone(), toType ), i->env, i->cost, thisCost ) );
869 } // if
870 } // for
871
872 // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
873 // cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice
874 // selects first based on argument cost, then on conversion cost.
875 AltList minArgCost;
876 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
877 findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
878 }
879
880 void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) {
881 AlternativeFinder funcFinder( indexer, env );
882 funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
883 for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
884 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( agg->expr->get_result() ) ) {
885 addAggMembers( structInst, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
886 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( agg->expr->get_result() ) ) {
887 addAggMembers( unionInst, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
888 } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( agg->expr->get_result() ) ) {
889 addTupleMembers( tupleType, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
890 } // if
891 } // for
892 }
893
894 void AlternativeFinder::visit( MemberExpr *memberExpr ) {
895 alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
896 }
897
898 void AlternativeFinder::visit( NameExpr *nameExpr ) {
899 std::list< DeclarationWithType* > declList;
900 indexer.lookupId( nameExpr->get_name(), declList );
901 PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; )
902 for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) {
903 VariableExpr newExpr( *i, nameExpr->get_argName() );
904 alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) );
905 PRINT(
906 std::cerr << "decl is ";
907 (*i)->print( std::cerr );
908 std::cerr << std::endl;
909 std::cerr << "newExpr is ";
910 newExpr.print( std::cerr );
911 std::cerr << std::endl;
912 )
913 renameTypes( alternatives.back().expr );
914 addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
915 } // for
916 }
917
918 void AlternativeFinder::visit( VariableExpr *variableExpr ) {
919 // not sufficient to clone here, because variable's type may have changed
920 // since the VariableExpr was originally created.
921 alternatives.push_back( Alternative( new VariableExpr( variableExpr->get_var() ), env, Cost::zero ) );
922 }
923
924 void AlternativeFinder::visit( ConstantExpr *constantExpr ) {
925 alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
926 }
927
928 void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) {
929 if ( sizeofExpr->get_isType() ) {
930 // xxx - resolveTypeof?
931 alternatives.push_back( Alternative( sizeofExpr->clone(), env, Cost::zero ) );
932 } else {
933 // find all alternatives for the argument to sizeof
934 AlternativeFinder finder( indexer, env );
935 finder.find( sizeofExpr->get_expr() );
936 // find the lowest cost alternative among the alternatives, otherwise ambiguous
937 AltList winners;
938 findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
939 if ( winners.size() != 1 ) {
940 throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() );
941 } // if
942 // return the lowest cost alternative for the argument
943 Alternative &choice = winners.front();
944 alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
945 } // if
946 }
947
948 void AlternativeFinder::visit( AlignofExpr *alignofExpr ) {
949 if ( alignofExpr->get_isType() ) {
950 // xxx - resolveTypeof?
951 alternatives.push_back( Alternative( alignofExpr->clone(), env, Cost::zero ) );
952 } else {
953 // find all alternatives for the argument to sizeof
954 AlternativeFinder finder( indexer, env );
955 finder.find( alignofExpr->get_expr() );
956 // find the lowest cost alternative among the alternatives, otherwise ambiguous
957 AltList winners;
958 findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
959 if ( winners.size() != 1 ) {
960 throw SemanticError( "Ambiguous expression in alignof operand: ", alignofExpr->get_expr() );
961 } // if
962 // return the lowest cost alternative for the argument
963 Alternative &choice = winners.front();
964 alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
965 } // if
966 }
967
968 template< typename StructOrUnionType >
969 void AlternativeFinder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
970 std::list< Declaration* > members;
971 aggInst->lookup( name, members );
972 for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
973 if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
974 alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
975 renameTypes( alternatives.back().expr );
976 } else {
977 assert( false );
978 }
979 }
980 }
981
982 void AlternativeFinder::visit( UntypedOffsetofExpr *offsetofExpr ) {
983 AlternativeFinder funcFinder( indexer, env );
984 // xxx - resolveTypeof?
985 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) {
986 addOffsetof( structInst, offsetofExpr->get_member() );
987 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) {
988 addOffsetof( unionInst, offsetofExpr->get_member() );
989 }
990 }
991
992 void AlternativeFinder::visit( OffsetofExpr *offsetofExpr ) {
993 alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
994 }
995
996 void AlternativeFinder::visit( OffsetPackExpr *offsetPackExpr ) {
997 alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
998 }
999
1000 void AlternativeFinder::resolveAttr( DeclarationWithType *funcDecl, FunctionType *function, Type *argType, const TypeEnvironment &env ) {
1001 // assume no polymorphism
1002 // assume no implicit conversions
1003 assert( function->get_parameters().size() == 1 );
1004 PRINT(
1005 std::cerr << "resolvAttr: funcDecl is ";
1006 funcDecl->print( std::cerr );
1007 std::cerr << " argType is ";
1008 argType->print( std::cerr );
1009 std::cerr << std::endl;
1010 )
1011 if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
1012 alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) );
1013 for ( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) {
1014 alternatives.back().expr->set_result( (*i)->get_type()->clone() );
1015 } // for
1016 } // if
1017 }
1018
1019 void AlternativeFinder::visit( AttrExpr *attrExpr ) {
1020 // assume no 'pointer-to-attribute'
1021 NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
1022 assert( nameExpr );
1023 std::list< DeclarationWithType* > attrList;
1024 indexer.lookupId( nameExpr->get_name(), attrList );
1025 if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
1026 for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1027 // check if the type is function
1028 if ( FunctionType *function = dynamic_cast< FunctionType* >( (*i)->get_type() ) ) {
1029 // assume exactly one parameter
1030 if ( function->get_parameters().size() == 1 ) {
1031 if ( attrExpr->get_isType() ) {
1032 resolveAttr( *i, function, attrExpr->get_type(), env );
1033 } else {
1034 AlternativeFinder finder( indexer, env );
1035 finder.find( attrExpr->get_expr() );
1036 for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
1037 if ( choice->expr->get_result()->size() == 1 ) {
1038 resolveAttr(*i, function, choice->expr->get_result(), choice->env );
1039 } // fi
1040 } // for
1041 } // if
1042 } // if
1043 } // if
1044 } // for
1045 } else {
1046 for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1047 VariableExpr newExpr( *i );
1048 alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) );
1049 renameTypes( alternatives.back().expr );
1050 } // for
1051 } // if
1052 }
1053
1054 void AlternativeFinder::visit( LogicalExpr *logicalExpr ) {
1055 AlternativeFinder firstFinder( indexer, env );
1056 firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
1057 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1058 AlternativeFinder secondFinder( indexer, first->env );
1059 secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
1060 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1061 LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() );
1062 alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) );
1063 }
1064 }
1065 }
1066
1067 void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) {
1068 // find alternatives for condition
1069 AlternativeFinder firstFinder( indexer, env );
1070 firstFinder.findWithAdjustment( conditionalExpr->get_arg1() );
1071 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1072 // find alternatives for true expression
1073 AlternativeFinder secondFinder( indexer, first->env );
1074 secondFinder.findWithAdjustment( conditionalExpr->get_arg2() );
1075 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1076 // find alterantives for false expression
1077 AlternativeFinder thirdFinder( indexer, second->env );
1078 thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() );
1079 for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) {
1080 // unify true and false types, then infer parameters to produce new alternatives
1081 OpenVarSet openVars;
1082 AssertionSet needAssertions, haveAssertions;
1083 Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost );
1084 Type* commonType = nullptr;
1085 if ( unify( second->expr->get_result(), third->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1086 ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() );
1087 newExpr->set_result( commonType ? commonType : second->expr->get_result()->clone() );
1088 newAlt.expr = newExpr;
1089 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1090 } // if
1091 } // for
1092 } // for
1093 } // for
1094 }
1095
1096 void AlternativeFinder::visit( CommaExpr *commaExpr ) {
1097 TypeEnvironment newEnv( env );
1098 Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
1099 AlternativeFinder secondFinder( indexer, newEnv );
1100 secondFinder.findWithAdjustment( commaExpr->get_arg2() );
1101 for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) {
1102 alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) );
1103 } // for
1104 delete newFirstArg;
1105 }
1106
1107 void AlternativeFinder::visit( RangeExpr * rangeExpr ) {
1108 // resolve low and high, accept alternatives whose low and high types unify
1109 AlternativeFinder firstFinder( indexer, env );
1110 firstFinder.findWithAdjustment( rangeExpr->get_low() );
1111 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1112 AlternativeFinder secondFinder( indexer, first->env );
1113 secondFinder.findWithAdjustment( rangeExpr->get_high() );
1114 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1115 OpenVarSet openVars;
1116 AssertionSet needAssertions, haveAssertions;
1117 Alternative newAlt( 0, second->env, first->cost + second->cost );
1118 Type* commonType = nullptr;
1119 if ( unify( first->expr->get_result(), second->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1120 RangeExpr *newExpr = new RangeExpr( first->expr->clone(), second->expr->clone() );
1121 newExpr->set_result( commonType ? commonType : first->expr->get_result()->clone() );
1122 newAlt.expr = newExpr;
1123 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1124 } // if
1125 } // for
1126 } // for
1127 }
1128
1129 void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) {
1130 std::list< AlternativeFinder > subExprAlternatives;
1131 findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) );
1132 std::list< AltList > possibilities;
1133 combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) );
1134 for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) {
1135 std::list< Expression * > exprs;
1136 makeExprList( *i, exprs );
1137
1138 TypeEnvironment compositeEnv;
1139 simpleCombineEnvironments( i->begin(), i->end(), compositeEnv );
1140 alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) );
1141 } // for
1142 }
1143
1144 void AlternativeFinder::visit( TupleExpr *tupleExpr ) {
1145 alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1146 }
1147
1148 void AlternativeFinder::visit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
1149 alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
1150 }
1151
1152 void AlternativeFinder::visit( ConstructorExpr * ctorExpr ) {
1153 AlternativeFinder finder( indexer, env );
1154 // don't prune here, since it's guaranteed all alternatives will have the same type
1155 // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
1156 finder.findWithAdjustment( ctorExpr->get_callExpr(), false );
1157 for ( Alternative & alt : finder.alternatives ) {
1158 alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
1159 }
1160 }
1161
1162 void AlternativeFinder::visit( TupleIndexExpr *tupleExpr ) {
1163 alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1164 }
1165
1166 void AlternativeFinder::visit( TupleAssignExpr *tupleAssignExpr ) {
1167 alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) );
1168 }
1169
1170 void AlternativeFinder::visit( UniqueExpr *unqExpr ) {
1171 AlternativeFinder finder( indexer, env );
1172 finder.findWithAdjustment( unqExpr->get_expr() );
1173 for ( Alternative & alt : finder.alternatives ) {
1174 // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
1175 UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
1176 alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
1177 }
1178 }
1179
1180 void AlternativeFinder::visit( StmtExpr *stmtExpr ) {
1181 StmtExpr * newStmtExpr = stmtExpr->clone();
1182 ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
1183 // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
1184 alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
1185 }
1186
1187 void AlternativeFinder::visit( UntypedInitExpr *initExpr ) {
1188 // handle each option like a cast
1189 AltList candidates;
1190 PRINT( std::cerr << "untyped init expr: " << initExpr << std::endl; )
1191 // O(N^2) checks of d-types with e-types
1192 for ( InitAlternative & initAlt : initExpr->get_initAlts() ) {
1193 Type * toType = resolveTypeof( initAlt.type, indexer );
1194 SymTab::validateType( toType, &indexer );
1195 adjustExprType( toType, env, indexer );
1196 // Ideally the call to findWithAdjustment could be moved out of the loop, but unfortunately it currently has to occur inside or else
1197 // polymorphic return types are not properly bound to the initialization type, since return type variables are only open for the duration of resolving
1198 // the UntypedExpr. This is only actually an issue in initialization contexts that allow more than one possible initialization type, but it is still suboptimal.
1199 AlternativeFinder finder( indexer, env );
1200 finder.targetType = toType;
1201 finder.findWithAdjustment( initExpr->get_expr() );
1202 for ( Alternative & alt : finder.get_alternatives() ) {
1203 TypeEnvironment newEnv( alt.env );
1204 AssertionSet needAssertions, haveAssertions;
1205 OpenVarSet openVars; // find things in env that don't have a "representative type" and claim those are open vars?
1206 PRINT( std::cerr << " @ " << toType << " " << initAlt.designation << std::endl; )
1207 // It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a
1208 // cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results
1209 // that are cast directly. The candidate is invalid if it has fewer results than there are types to cast
1210 // to.
1211 int discardedValues = alt.expr->get_result()->size() - toType->size();
1212 if ( discardedValues < 0 ) continue;
1213 // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
1214 // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
1215 // unification run for side-effects
1216 unify( toType, alt.expr->get_result(), newEnv, needAssertions, haveAssertions, openVars, indexer ); // xxx - do some inspecting on this line... why isn't result bound to initAlt.type??
1217
1218 Cost thisCost = castCost( alt.expr->get_result(), toType, indexer, newEnv );
1219 if ( thisCost != Cost::infinity ) {
1220 // count one safe conversion for each value that is thrown away
1221 thisCost += Cost( 0, 0, discardedValues );
1222 candidates.push_back( Alternative( new InitExpr( restructureCast( alt.expr->clone(), toType ), initAlt.designation->clone() ), newEnv, alt.cost, thisCost ) );
1223 }
1224 }
1225 }
1226
1227 // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
1228 // cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice
1229 // selects first based on argument cost, then on conversion cost.
1230 AltList minArgCost;
1231 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
1232 findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
1233 }
1234} // namespace ResolvExpr
1235
1236// Local Variables: //
1237// tab-width: 4 //
1238// mode: c++ //
1239// compile-command: "make install" //
1240// End: //
Note: See TracBrowser for help on using the repository browser.