source: src/ResolvExpr/AlternativeFinder.cc@ 2463d0e

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

Resolve member expression with reference type aggregates

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