source: src/ResolvExpr/AlternativeFinder.cc@ 0428aad

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

fix implicit conversion to anonymous members
  • Property mode set to 100644
File size: 51.5 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// AlternativeFinder.cc --
8//
9// Author : Richard C. Bilson
10// Created On : Sat May 16 23:52:08 2015
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Fri Mar 17 09:14:17 2017
13// Update Count : 30
14//
15
16#include <list>
17#include <iterator>
18#include <algorithm>
19#include <functional>
20#include <cassert>
21#include <unordered_map>
22#include <utility>
23#include <vector>
24
25#include "AlternativeFinder.h"
26#include "Alternative.h"
27#include "Cost.h"
28#include "typeops.h"
29#include "Unify.h"
30#include "RenameVars.h"
31#include "SynTree/Type.h"
32#include "SynTree/Declaration.h"
33#include "SynTree/Expression.h"
34#include "SynTree/Initializer.h"
35#include "SynTree/Visitor.h"
36#include "SymTab/Indexer.h"
37#include "SymTab/Mangler.h"
38#include "SynTree/TypeSubstitution.h"
39#include "SymTab/Validate.h"
40#include "Tuples/Tuples.h"
41#include "Tuples/Explode.h"
42#include "Common/utility.h"
43#include "InitTweak/InitTweak.h"
44#include "InitTweak/GenInit.h"
45#include "ResolveTypeof.h"
46#include "Resolver.h"
47
48extern bool resolvep;
49#define PRINT( text ) if ( resolvep ) { text }
50//#define DEBUG_COST
51
52namespace ResolvExpr {
53 Expression *resolveInVoidContext( Expression *expr, const SymTab::Indexer &indexer, TypeEnvironment &env ) {
54 CastExpr *castToVoid = new CastExpr( expr );
55
56 AlternativeFinder finder( indexer, env );
57 finder.findWithAdjustment( castToVoid );
58
59 // it's a property of the language that a cast expression has either 1 or 0 interpretations; if it has 0
60 // interpretations, an exception has already been thrown.
61 assert( finder.get_alternatives().size() == 1 );
62 CastExpr *newExpr = dynamic_cast< CastExpr* >( finder.get_alternatives().front().expr );
63 assert( newExpr );
64 env = finder.get_alternatives().front().env;
65 return newExpr->get_arg()->clone();
66 }
67
68 Cost sumCost( const AltList &in ) {
69 Cost total;
70 for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
71 total += i->cost;
72 }
73 return total;
74 }
75
76 namespace {
77 void printAlts( const AltList &list, std::ostream &os, int indent = 0 ) {
78 for ( AltList::const_iterator i = list.begin(); i != list.end(); ++i ) {
79 i->print( os, indent );
80 os << std::endl;
81 }
82 }
83
84 void makeExprList( const AltList &in, std::list< Expression* > &out ) {
85 for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
86 out.push_back( i->expr->clone() );
87 }
88 }
89
90 struct PruneStruct {
91 bool isAmbiguous;
92 AltList::iterator candidate;
93 PruneStruct() {}
94 PruneStruct( AltList::iterator candidate ): isAmbiguous( false ), candidate( candidate ) {}
95 };
96
97 /// Prunes a list of alternatives down to those that have the minimum conversion cost for a given return type; skips ambiguous interpretations
98 template< typename InputIterator, typename OutputIterator >
99 void pruneAlternatives( InputIterator begin, InputIterator end, OutputIterator out, const SymTab::Indexer &indexer ) {
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 ), indexer );
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 AltList instantiatedActuals; // filled by instantiate function
630 if ( targetType && ! targetType->isVoid() && ! funcType->get_returnVals().empty() ) {
631 // attempt to narrow based on expected target type
632 Type * returnType = funcType->get_returnVals().front()->get_type();
633 if ( ! unify( returnType, targetType, resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
634 // unification failed, don't pursue this alternative
635 return;
636 }
637 }
638
639 if ( instantiateFunction( funcType->get_parameters(), actualAlt, funcType->get_isVarArgs(), openVars, resultEnv, resultNeed, resultHave, instantiatedActuals ) ) {
640 ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
641 Alternative newAlt( appExpr, resultEnv, sumCost( instantiatedActuals ) );
642 makeExprList( instantiatedActuals, appExpr->get_args() );
643 PRINT(
644 std::cerr << "need assertions:" << std::endl;
645 printAssertionSet( resultNeed, std::cerr, 8 );
646 )
647 inferParameters( resultNeed, resultHave, newAlt, openVars, out );
648 }
649 }
650
651 void AlternativeFinder::visit( UntypedExpr *untypedExpr ) {
652 bool doneInit = false;
653 AlternativeFinder funcOpFinder( indexer, env );
654
655 AlternativeFinder funcFinder( indexer, env );
656
657 {
658 std::string fname = InitTweak::getFunctionName( untypedExpr );
659 if ( fname == "&&" ) {
660 VoidType v = Type::Qualifiers(); // resolve to type void *
661 PointerType pt( Type::Qualifiers(), v.clone() );
662 UntypedExpr *vexpr = untypedExpr->clone();
663 vexpr->set_result( pt.clone() );
664 alternatives.push_back( Alternative( vexpr, env, Cost()) );
665 return;
666 }
667 }
668
669 funcFinder.findWithAdjustment( untypedExpr->get_function() );
670 std::list< AlternativeFinder > argAlternatives;
671 findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), back_inserter( argAlternatives ) );
672
673 std::list< AltList > possibilities;
674 combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) );
675
676 // take care of possible tuple assignments
677 // if not tuple assignment, assignment is taken care of as a normal function call
678 Tuples::handleTupleAssignment( *this, untypedExpr, possibilities );
679
680 AltList candidates;
681 SemanticError errors;
682 for ( AltList::const_iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) {
683 try {
684 PRINT(
685 std::cerr << "working on alternative: " << std::endl;
686 func->print( std::cerr, 8 );
687 )
688 // check if the type is pointer to function
689 PointerType *pointer;
690 if ( ( pointer = dynamic_cast< PointerType* >( func->expr->get_result() ) ) ) {
691 if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
692 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
693 // XXX
694 //Designators::check_alternative( function, *actualAlt );
695 makeFunctionAlternatives( *func, function, *actualAlt, std::back_inserter( candidates ) );
696 }
697 } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( pointer->get_base() ) ) {
698 EqvClass eqvClass;
699 if ( func->env.lookup( typeInst->get_name(), eqvClass ) && eqvClass.type ) {
700 if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.type ) ) {
701 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
702 makeFunctionAlternatives( *func, function, *actualAlt, std::back_inserter( candidates ) );
703 } // for
704 } // if
705 } // if
706 } // if
707 } else {
708 // seek a function operator that's compatible
709 if ( ! doneInit ) {
710 doneInit = true;
711 NameExpr *opExpr = new NameExpr( "?()" );
712 try {
713 funcOpFinder.findWithAdjustment( opExpr );
714 } catch( SemanticError &e ) {
715 // it's ok if there aren't any defined function ops
716 }
717 PRINT(
718 std::cerr << "known function ops:" << std::endl;
719 printAlts( funcOpFinder.alternatives, std::cerr, 8 );
720 )
721 }
722
723 for ( AltList::const_iterator funcOp = funcOpFinder.alternatives.begin(); funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
724 // check if the type is pointer to function
725 PointerType *pointer;
726 if ( ( pointer = dynamic_cast< PointerType* >( funcOp->expr->get_result() ) ) ) {
727 if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
728 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
729 AltList currentAlt;
730 currentAlt.push_back( *func );
731 currentAlt.insert( currentAlt.end(), actualAlt->begin(), actualAlt->end() );
732 makeFunctionAlternatives( *funcOp, function, currentAlt, std::back_inserter( candidates ) );
733 } // for
734 } // if
735 } // if
736 } // for
737 } // if
738 } catch ( SemanticError &e ) {
739 errors.append( e );
740 }
741 } // for
742
743 // Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
744 if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }
745
746 // compute conversionsion costs
747 for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) {
748 Cost cvtCost = computeConversionCost( *withFunc, indexer );
749
750 PRINT(
751 ApplicationExpr *appExpr = safe_dynamic_cast< ApplicationExpr* >( withFunc->expr );
752 PointerType *pointer = safe_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
753 FunctionType *function = safe_dynamic_cast< FunctionType* >( pointer->get_base() );
754 std::cerr << "Case +++++++++++++" << std::endl;
755 std::cerr << "formals are:" << std::endl;
756 printAll( function->get_parameters(), std::cerr, 8 );
757 std::cerr << "actuals are:" << std::endl;
758 printAll( appExpr->get_args(), std::cerr, 8 );
759 std::cerr << "bindings are:" << std::endl;
760 withFunc->env.print( std::cerr, 8 );
761 std::cerr << "cost of conversion is:" << cvtCost << std::endl;
762 )
763 if ( cvtCost != Cost::infinity ) {
764 withFunc->cvtCost = cvtCost;
765 alternatives.push_back( *withFunc );
766 } // if
767 } // for
768 // function may return struct or union value, in which case we need to add alternatives for implicit conversions to each of the anonymous members
769 for ( const Alternative & alt : alternatives ) {
770 addAnonConversions( alt );
771 }
772
773 candidates.clear();
774 candidates.splice( candidates.end(), alternatives );
775
776 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( alternatives ) );
777
778 if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
779 // xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
780 // target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
781 // forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
782 // const char * x = "hello world";
783 // unsigned char ch = x[0];
784 // Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
785 // with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
786 // fix this issue in a more robust way.
787 targetType = nullptr;
788 visit( untypedExpr );
789 }
790 }
791
792 bool isLvalue( Expression *expr ) {
793 // xxx - recurse into tuples?
794 return expr->has_result() && expr->get_result()->get_lvalue();
795 }
796
797 void AlternativeFinder::visit( AddressExpr *addressExpr ) {
798 AlternativeFinder finder( indexer, env );
799 finder.find( addressExpr->get_arg() );
800 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
801 if ( isLvalue( i->expr ) ) {
802 alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) );
803 } // if
804 } // for
805 }
806
807 void AlternativeFinder::visit( CastExpr *castExpr ) {
808 Type *& toType = castExpr->get_result();
809 assert( toType );
810 toType = resolveTypeof( toType, indexer );
811 SymTab::validateType( toType, &indexer );
812 adjustExprType( toType, env, indexer );
813
814 AlternativeFinder finder( indexer, env );
815 finder.targetType = toType;
816 finder.findWithAdjustment( castExpr->get_arg() );
817
818 AltList candidates;
819 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
820 AssertionSet needAssertions, haveAssertions;
821 OpenVarSet openVars;
822
823 // It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a
824 // cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results
825 // that are cast directly. The candidate is invalid if it has fewer results than there are types to cast
826 // to.
827 int discardedValues = (*i).expr->get_result()->size() - castExpr->get_result()->size();
828 if ( discardedValues < 0 ) continue;
829 // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
830 // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
831 // unification run for side-effects
832 unify( castExpr->get_result(), (*i).expr->get_result(), i->env, needAssertions, haveAssertions, openVars, indexer );
833 Cost thisCost = castCost( (*i).expr->get_result(), castExpr->get_result(), indexer, i->env );
834 if ( thisCost != Cost::infinity ) {
835 // count one safe conversion for each value that is thrown away
836 thisCost += Cost( 0, 0, discardedValues );
837
838 Expression * argExpr = i->expr->clone();
839 if ( argExpr->get_result()->size() > 1 && ! castExpr->get_result()->isVoid() ) {
840 // Argument expression is a tuple and the target type is not void. Cast each member of the tuple
841 // to its corresponding target type, producing the tuple of those cast expressions. If there are
842 // more components of the tuple than components in the target type, then excess components do not
843 // come out in the result expression (but UniqueExprs ensure that side effects will still be done).
844 if ( Tuples::maybeImpure( argExpr ) && ! dynamic_cast< UniqueExpr * >( argExpr ) ) {
845 // expressions which may contain side effects require a single unique instance of the expression.
846 argExpr = new UniqueExpr( argExpr );
847 }
848 std::list< Expression * > componentExprs;
849 for ( unsigned int i = 0; i < castExpr->get_result()->size(); i++ ) {
850 // cast each component
851 TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
852 componentExprs.push_back( new CastExpr( idx, castExpr->get_result()->getComponent( i )->clone() ) );
853 }
854 delete argExpr;
855 assert( componentExprs.size() > 0 );
856 // produce the tuple of casts
857 candidates.push_back( Alternative( new TupleExpr( componentExprs ), i->env, i->cost, thisCost ) );
858 } else {
859 // handle normally
860 candidates.push_back( Alternative( new CastExpr( argExpr->clone(), toType->clone() ), i->env, i->cost, thisCost ) );
861 }
862 } // if
863 } // for
864
865 // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
866 // cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice
867 // selects first based on argument cost, then on conversion cost.
868 AltList minArgCost;
869 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
870 findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
871 }
872
873 void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) {
874 AlternativeFinder funcFinder( indexer, env );
875 funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
876 for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
877 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( agg->expr->get_result() ) ) {
878 addAggMembers( structInst, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
879 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( agg->expr->get_result() ) ) {
880 addAggMembers( unionInst, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
881 } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( agg->expr->get_result() ) ) {
882 addTupleMembers( tupleType, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
883 } // if
884 } // for
885 }
886
887 void AlternativeFinder::visit( MemberExpr *memberExpr ) {
888 alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
889 }
890
891 void AlternativeFinder::visit( NameExpr *nameExpr ) {
892 std::list< DeclarationWithType* > declList;
893 indexer.lookupId( nameExpr->get_name(), declList );
894 PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; )
895 for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) {
896 VariableExpr newExpr( *i, nameExpr->get_argName() );
897 alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) );
898 PRINT(
899 std::cerr << "decl is ";
900 (*i)->print( std::cerr );
901 std::cerr << std::endl;
902 std::cerr << "newExpr is ";
903 newExpr.print( std::cerr );
904 std::cerr << std::endl;
905 )
906 renameTypes( alternatives.back().expr );
907 addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
908 } // for
909 }
910
911 void AlternativeFinder::visit( VariableExpr *variableExpr ) {
912 // not sufficient to clone here, because variable's type may have changed
913 // since the VariableExpr was originally created.
914 alternatives.push_back( Alternative( new VariableExpr( variableExpr->get_var() ), env, Cost::zero ) );
915 }
916
917 void AlternativeFinder::visit( ConstantExpr *constantExpr ) {
918 alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
919 }
920
921 void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) {
922 if ( sizeofExpr->get_isType() ) {
923 // xxx - resolveTypeof?
924 alternatives.push_back( Alternative( sizeofExpr->clone(), env, Cost::zero ) );
925 } else {
926 // find all alternatives for the argument to sizeof
927 AlternativeFinder finder( indexer, env );
928 finder.find( sizeofExpr->get_expr() );
929 // find the lowest cost alternative among the alternatives, otherwise ambiguous
930 AltList winners;
931 findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
932 if ( winners.size() != 1 ) {
933 throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() );
934 } // if
935 // return the lowest cost alternative for the argument
936 Alternative &choice = winners.front();
937 alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
938 } // if
939 }
940
941 void AlternativeFinder::visit( AlignofExpr *alignofExpr ) {
942 if ( alignofExpr->get_isType() ) {
943 // xxx - resolveTypeof?
944 alternatives.push_back( Alternative( alignofExpr->clone(), env, Cost::zero ) );
945 } else {
946 // find all alternatives for the argument to sizeof
947 AlternativeFinder finder( indexer, env );
948 finder.find( alignofExpr->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 alignof operand: ", alignofExpr->get_expr() );
954 } // if
955 // return the lowest cost alternative for the argument
956 Alternative &choice = winners.front();
957 alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
958 } // if
959 }
960
961 template< typename StructOrUnionType >
962 void AlternativeFinder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
963 std::list< Declaration* > members;
964 aggInst->lookup( name, members );
965 for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
966 if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
967 alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
968 renameTypes( alternatives.back().expr );
969 } else {
970 assert( false );
971 }
972 }
973 }
974
975 void AlternativeFinder::visit( UntypedOffsetofExpr *offsetofExpr ) {
976 AlternativeFinder funcFinder( indexer, env );
977 // xxx - resolveTypeof?
978 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) {
979 addOffsetof( structInst, offsetofExpr->get_member() );
980 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) {
981 addOffsetof( unionInst, offsetofExpr->get_member() );
982 }
983 }
984
985 void AlternativeFinder::visit( OffsetofExpr *offsetofExpr ) {
986 alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
987 }
988
989 void AlternativeFinder::visit( OffsetPackExpr *offsetPackExpr ) {
990 alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
991 }
992
993 void AlternativeFinder::resolveAttr( DeclarationWithType *funcDecl, FunctionType *function, Type *argType, const TypeEnvironment &env ) {
994 // assume no polymorphism
995 // assume no implicit conversions
996 assert( function->get_parameters().size() == 1 );
997 PRINT(
998 std::cerr << "resolvAttr: funcDecl is ";
999 funcDecl->print( std::cerr );
1000 std::cerr << " argType is ";
1001 argType->print( std::cerr );
1002 std::cerr << std::endl;
1003 )
1004 if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
1005 alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) );
1006 for ( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) {
1007 alternatives.back().expr->set_result( (*i)->get_type()->clone() );
1008 } // for
1009 } // if
1010 }
1011
1012 void AlternativeFinder::visit( AttrExpr *attrExpr ) {
1013 // assume no 'pointer-to-attribute'
1014 NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
1015 assert( nameExpr );
1016 std::list< DeclarationWithType* > attrList;
1017 indexer.lookupId( nameExpr->get_name(), attrList );
1018 if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
1019 for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1020 // check if the type is function
1021 if ( FunctionType *function = dynamic_cast< FunctionType* >( (*i)->get_type() ) ) {
1022 // assume exactly one parameter
1023 if ( function->get_parameters().size() == 1 ) {
1024 if ( attrExpr->get_isType() ) {
1025 resolveAttr( *i, function, attrExpr->get_type(), env );
1026 } else {
1027 AlternativeFinder finder( indexer, env );
1028 finder.find( attrExpr->get_expr() );
1029 for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
1030 if ( choice->expr->get_result()->size() == 1 ) {
1031 resolveAttr(*i, function, choice->expr->get_result(), choice->env );
1032 } // fi
1033 } // for
1034 } // if
1035 } // if
1036 } // if
1037 } // for
1038 } else {
1039 for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1040 VariableExpr newExpr( *i );
1041 alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) );
1042 renameTypes( alternatives.back().expr );
1043 } // for
1044 } // if
1045 }
1046
1047 void AlternativeFinder::visit( LogicalExpr *logicalExpr ) {
1048 AlternativeFinder firstFinder( indexer, env );
1049 firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
1050 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1051 AlternativeFinder secondFinder( indexer, first->env );
1052 secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
1053 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1054 LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() );
1055 alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) );
1056 }
1057 }
1058 }
1059
1060 void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) {
1061 // find alternatives for condition
1062 AlternativeFinder firstFinder( indexer, env );
1063 firstFinder.findWithAdjustment( conditionalExpr->get_arg1() );
1064 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1065 // find alternatives for true expression
1066 AlternativeFinder secondFinder( indexer, first->env );
1067 secondFinder.findWithAdjustment( conditionalExpr->get_arg2() );
1068 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1069 // find alterantives for false expression
1070 AlternativeFinder thirdFinder( indexer, second->env );
1071 thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() );
1072 for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) {
1073 // unify true and false types, then infer parameters to produce new alternatives
1074 OpenVarSet openVars;
1075 AssertionSet needAssertions, haveAssertions;
1076 Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost );
1077 Type* commonType = nullptr;
1078 if ( unify( second->expr->get_result(), third->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1079 ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() );
1080 newExpr->set_result( commonType ? commonType : second->expr->get_result()->clone() );
1081 newAlt.expr = newExpr;
1082 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1083 } // if
1084 } // for
1085 } // for
1086 } // for
1087 }
1088
1089 void AlternativeFinder::visit( CommaExpr *commaExpr ) {
1090 TypeEnvironment newEnv( env );
1091 Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
1092 AlternativeFinder secondFinder( indexer, newEnv );
1093 secondFinder.findWithAdjustment( commaExpr->get_arg2() );
1094 for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) {
1095 alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) );
1096 } // for
1097 delete newFirstArg;
1098 }
1099
1100 void AlternativeFinder::visit( RangeExpr * rangeExpr ) {
1101 // resolve low and high, accept alternatives whose low and high types unify
1102 AlternativeFinder firstFinder( indexer, env );
1103 firstFinder.findWithAdjustment( rangeExpr->get_low() );
1104 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1105 AlternativeFinder secondFinder( indexer, first->env );
1106 secondFinder.findWithAdjustment( rangeExpr->get_high() );
1107 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1108 OpenVarSet openVars;
1109 AssertionSet needAssertions, haveAssertions;
1110 Alternative newAlt( 0, second->env, first->cost + second->cost );
1111 Type* commonType = nullptr;
1112 if ( unify( first->expr->get_result(), second->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1113 RangeExpr *newExpr = new RangeExpr( first->expr->clone(), second->expr->clone() );
1114 newExpr->set_result( commonType ? commonType : first->expr->get_result()->clone() );
1115 newAlt.expr = newExpr;
1116 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1117 } // if
1118 } // for
1119 } // for
1120 }
1121
1122 void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) {
1123 std::list< AlternativeFinder > subExprAlternatives;
1124 findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) );
1125 std::list< AltList > possibilities;
1126 combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) );
1127 for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) {
1128 std::list< Expression * > exprs;
1129 makeExprList( *i, exprs );
1130
1131 TypeEnvironment compositeEnv;
1132 simpleCombineEnvironments( i->begin(), i->end(), compositeEnv );
1133 alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) );
1134 } // for
1135 }
1136
1137 void AlternativeFinder::visit( TupleExpr *tupleExpr ) {
1138 alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1139 }
1140
1141 void AlternativeFinder::visit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
1142 alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
1143 }
1144
1145 void AlternativeFinder::visit( ConstructorExpr * ctorExpr ) {
1146 AlternativeFinder finder( indexer, env );
1147 // don't prune here, since it's guaranteed all alternatives will have the same type
1148 // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
1149 finder.findWithAdjustment( ctorExpr->get_callExpr(), false );
1150 for ( Alternative & alt : finder.alternatives ) {
1151 alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
1152 }
1153 }
1154
1155 void AlternativeFinder::visit( TupleIndexExpr *tupleExpr ) {
1156 alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1157 }
1158
1159 void AlternativeFinder::visit( TupleAssignExpr *tupleAssignExpr ) {
1160 alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) );
1161 }
1162
1163 void AlternativeFinder::visit( UniqueExpr *unqExpr ) {
1164 AlternativeFinder finder( indexer, env );
1165 finder.findWithAdjustment( unqExpr->get_expr() );
1166 for ( Alternative & alt : finder.alternatives ) {
1167 // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
1168 UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
1169 alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
1170 }
1171 }
1172
1173 void AlternativeFinder::visit( StmtExpr *stmtExpr ) {
1174 StmtExpr * newStmtExpr = stmtExpr->clone();
1175 ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
1176 // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
1177 alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
1178 }
1179
1180} // namespace ResolvExpr
1181
1182// Local Variables: //
1183// tab-width: 4 //
1184// mode: c++ //
1185// compile-command: "make install" //
1186// End: //
Note: See TracBrowser for help on using the repository browser.