source: src/ResolvExpr/AlternativeFinder.cc@ 6a36975

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 6a36975 was a5f0529, checked in by Andrew Beach <ajbeach@…>, 8 years ago

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