source: src/ResolvExpr/AlternativeFinder.cc@ 4fbdfae0

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

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