source: src/ResolvExpr/AlternativeFinder.cc@ 6182039

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

fix anonymous member conversions on function calls
  • Property mode set to 100644
File size: 51.6 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// AlternativeFinder.cc --
8//
9// Author : Richard C. Bilson
10// Created On : Sat May 16 23:52:08 2015
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Fri Mar 17 09:14:17 2017
13// Update Count : 30
14//
15
16#include <list>
17#include <iterator>
18#include <algorithm>
19#include <functional>
20#include <cassert>
21#include <unordered_map>
22#include <utility>
23#include <vector>
24
25#include "AlternativeFinder.h"
26#include "Alternative.h"
27#include "Cost.h"
28#include "typeops.h"
29#include "Unify.h"
30#include "RenameVars.h"
31#include "SynTree/Type.h"
32#include "SynTree/Declaration.h"
33#include "SynTree/Expression.h"
34#include "SynTree/Initializer.h"
35#include "SynTree/Visitor.h"
36#include "SymTab/Indexer.h"
37#include "SymTab/Mangler.h"
38#include "SynTree/TypeSubstitution.h"
39#include "SymTab/Validate.h"
40#include "Tuples/Tuples.h"
41#include "Tuples/Explode.h"
42#include "Common/utility.h"
43#include "InitTweak/InitTweak.h"
44#include "InitTweak/GenInit.h"
45#include "ResolveTypeof.h"
46#include "Resolver.h"
47
48extern bool resolvep;
49#define PRINT( text ) if ( resolvep ) { text }
50//#define DEBUG_COST
51
52namespace ResolvExpr {
53 Expression *resolveInVoidContext( Expression *expr, const SymTab::Indexer &indexer, TypeEnvironment &env ) {
54 CastExpr *castToVoid = new CastExpr( expr );
55
56 AlternativeFinder finder( indexer, env );
57 finder.findWithAdjustment( castToVoid );
58
59 // it's a property of the language that a cast expression has either 1 or 0 interpretations; if it has 0
60 // interpretations, an exception has already been thrown.
61 assert( finder.get_alternatives().size() == 1 );
62 CastExpr *newExpr = dynamic_cast< CastExpr* >( finder.get_alternatives().front().expr );
63 assert( newExpr );
64 env = finder.get_alternatives().front().env;
65 return newExpr->get_arg()->clone();
66 }
67
68 Cost sumCost( const AltList &in ) {
69 Cost total;
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
769 candidates.clear();
770 candidates.splice( candidates.end(), alternatives );
771
772 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( alternatives ) );
773
774 // function may return struct or union value, in which case we need to add alternatives for implicit
775 // conversions to each of the anonymous members, must happen after findMinCost since anon conversions
776 // are never the cheapest expression
777 for ( const Alternative & alt : alternatives ) {
778 addAnonConversions( alt );
779 }
780
781 if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
782 // xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
783 // target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
784 // forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
785 // const char * x = "hello world";
786 // unsigned char ch = x[0];
787 // Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
788 // with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
789 // fix this issue in a more robust way.
790 targetType = nullptr;
791 visit( untypedExpr );
792 }
793 }
794
795 bool isLvalue( Expression *expr ) {
796 // xxx - recurse into tuples?
797 return expr->has_result() && expr->get_result()->get_lvalue();
798 }
799
800 void AlternativeFinder::visit( AddressExpr *addressExpr ) {
801 AlternativeFinder finder( indexer, env );
802 finder.find( addressExpr->get_arg() );
803 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
804 if ( isLvalue( i->expr ) ) {
805 alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) );
806 } // if
807 } // for
808 }
809
810 void AlternativeFinder::visit( CastExpr *castExpr ) {
811 Type *& toType = castExpr->get_result();
812 assert( toType );
813 toType = resolveTypeof( toType, indexer );
814 SymTab::validateType( toType, &indexer );
815 adjustExprType( toType, env, indexer );
816
817 AlternativeFinder finder( indexer, env );
818 finder.targetType = toType;
819 finder.findWithAdjustment( castExpr->get_arg() );
820
821 AltList candidates;
822 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
823 AssertionSet needAssertions, haveAssertions;
824 OpenVarSet openVars;
825
826 // It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a
827 // cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results
828 // that are cast directly. The candidate is invalid if it has fewer results than there are types to cast
829 // to.
830 int discardedValues = (*i).expr->get_result()->size() - castExpr->get_result()->size();
831 if ( discardedValues < 0 ) continue;
832 // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
833 // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
834 // unification run for side-effects
835 unify( castExpr->get_result(), (*i).expr->get_result(), i->env, needAssertions, haveAssertions, openVars, indexer );
836 Cost thisCost = castCost( (*i).expr->get_result(), castExpr->get_result(), indexer, i->env );
837 if ( thisCost != Cost::infinity ) {
838 // count one safe conversion for each value that is thrown away
839 thisCost += Cost( 0, 0, discardedValues );
840
841 Expression * argExpr = i->expr->clone();
842 if ( argExpr->get_result()->size() > 1 && ! castExpr->get_result()->isVoid() ) {
843 // Argument expression is a tuple and the target type is not void. Cast each member of the tuple
844 // to its corresponding target type, producing the tuple of those cast expressions. If there are
845 // more components of the tuple than components in the target type, then excess components do not
846 // come out in the result expression (but UniqueExprs ensure that side effects will still be done).
847 if ( Tuples::maybeImpure( argExpr ) && ! dynamic_cast< UniqueExpr * >( argExpr ) ) {
848 // expressions which may contain side effects require a single unique instance of the expression.
849 argExpr = new UniqueExpr( argExpr );
850 }
851 std::list< Expression * > componentExprs;
852 for ( unsigned int i = 0; i < castExpr->get_result()->size(); i++ ) {
853 // cast each component
854 TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
855 componentExprs.push_back( new CastExpr( idx, castExpr->get_result()->getComponent( i )->clone() ) );
856 }
857 delete argExpr;
858 assert( componentExprs.size() > 0 );
859 // produce the tuple of casts
860 candidates.push_back( Alternative( new TupleExpr( componentExprs ), i->env, i->cost, thisCost ) );
861 } else {
862 // handle normally
863 candidates.push_back( Alternative( new CastExpr( argExpr->clone(), toType->clone() ), i->env, i->cost, thisCost ) );
864 }
865 } // if
866 } // for
867
868 // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
869 // cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice
870 // selects first based on argument cost, then on conversion cost.
871 AltList minArgCost;
872 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
873 findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
874 }
875
876 void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) {
877 AlternativeFinder funcFinder( indexer, env );
878 funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
879 for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
880 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( agg->expr->get_result() ) ) {
881 addAggMembers( structInst, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
882 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( agg->expr->get_result() ) ) {
883 addAggMembers( unionInst, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
884 } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( agg->expr->get_result() ) ) {
885 addTupleMembers( tupleType, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
886 } // if
887 } // for
888 }
889
890 void AlternativeFinder::visit( MemberExpr *memberExpr ) {
891 alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
892 }
893
894 void AlternativeFinder::visit( NameExpr *nameExpr ) {
895 std::list< DeclarationWithType* > declList;
896 indexer.lookupId( nameExpr->get_name(), declList );
897 PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; )
898 for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) {
899 VariableExpr newExpr( *i, nameExpr->get_argName() );
900 alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) );
901 PRINT(
902 std::cerr << "decl is ";
903 (*i)->print( std::cerr );
904 std::cerr << std::endl;
905 std::cerr << "newExpr is ";
906 newExpr.print( std::cerr );
907 std::cerr << std::endl;
908 )
909 renameTypes( alternatives.back().expr );
910 addAnonConversions( alternatives.back() ); // add anonymous member interpretations whenever an aggregate value type is seen as a name expression.
911 } // for
912 }
913
914 void AlternativeFinder::visit( VariableExpr *variableExpr ) {
915 // not sufficient to clone here, because variable's type may have changed
916 // since the VariableExpr was originally created.
917 alternatives.push_back( Alternative( new VariableExpr( variableExpr->get_var() ), env, Cost::zero ) );
918 }
919
920 void AlternativeFinder::visit( ConstantExpr *constantExpr ) {
921 alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
922 }
923
924 void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) {
925 if ( sizeofExpr->get_isType() ) {
926 // xxx - resolveTypeof?
927 alternatives.push_back( Alternative( sizeofExpr->clone(), env, Cost::zero ) );
928 } else {
929 // find all alternatives for the argument to sizeof
930 AlternativeFinder finder( indexer, env );
931 finder.find( sizeofExpr->get_expr() );
932 // find the lowest cost alternative among the alternatives, otherwise ambiguous
933 AltList winners;
934 findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
935 if ( winners.size() != 1 ) {
936 throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() );
937 } // if
938 // return the lowest cost alternative for the argument
939 Alternative &choice = winners.front();
940 alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
941 } // if
942 }
943
944 void AlternativeFinder::visit( AlignofExpr *alignofExpr ) {
945 if ( alignofExpr->get_isType() ) {
946 // xxx - resolveTypeof?
947 alternatives.push_back( Alternative( alignofExpr->clone(), env, Cost::zero ) );
948 } else {
949 // find all alternatives for the argument to sizeof
950 AlternativeFinder finder( indexer, env );
951 finder.find( alignofExpr->get_expr() );
952 // find the lowest cost alternative among the alternatives, otherwise ambiguous
953 AltList winners;
954 findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
955 if ( winners.size() != 1 ) {
956 throw SemanticError( "Ambiguous expression in alignof operand: ", alignofExpr->get_expr() );
957 } // if
958 // return the lowest cost alternative for the argument
959 Alternative &choice = winners.front();
960 alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
961 } // if
962 }
963
964 template< typename StructOrUnionType >
965 void AlternativeFinder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
966 std::list< Declaration* > members;
967 aggInst->lookup( name, members );
968 for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
969 if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
970 alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
971 renameTypes( alternatives.back().expr );
972 } else {
973 assert( false );
974 }
975 }
976 }
977
978 void AlternativeFinder::visit( UntypedOffsetofExpr *offsetofExpr ) {
979 AlternativeFinder funcFinder( indexer, env );
980 // xxx - resolveTypeof?
981 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) {
982 addOffsetof( structInst, offsetofExpr->get_member() );
983 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) {
984 addOffsetof( unionInst, offsetofExpr->get_member() );
985 }
986 }
987
988 void AlternativeFinder::visit( OffsetofExpr *offsetofExpr ) {
989 alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
990 }
991
992 void AlternativeFinder::visit( OffsetPackExpr *offsetPackExpr ) {
993 alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
994 }
995
996 void AlternativeFinder::resolveAttr( DeclarationWithType *funcDecl, FunctionType *function, Type *argType, const TypeEnvironment &env ) {
997 // assume no polymorphism
998 // assume no implicit conversions
999 assert( function->get_parameters().size() == 1 );
1000 PRINT(
1001 std::cerr << "resolvAttr: funcDecl is ";
1002 funcDecl->print( std::cerr );
1003 std::cerr << " argType is ";
1004 argType->print( std::cerr );
1005 std::cerr << std::endl;
1006 )
1007 if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
1008 alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) );
1009 for ( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) {
1010 alternatives.back().expr->set_result( (*i)->get_type()->clone() );
1011 } // for
1012 } // if
1013 }
1014
1015 void AlternativeFinder::visit( AttrExpr *attrExpr ) {
1016 // assume no 'pointer-to-attribute'
1017 NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
1018 assert( nameExpr );
1019 std::list< DeclarationWithType* > attrList;
1020 indexer.lookupId( nameExpr->get_name(), attrList );
1021 if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
1022 for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1023 // check if the type is function
1024 if ( FunctionType *function = dynamic_cast< FunctionType* >( (*i)->get_type() ) ) {
1025 // assume exactly one parameter
1026 if ( function->get_parameters().size() == 1 ) {
1027 if ( attrExpr->get_isType() ) {
1028 resolveAttr( *i, function, attrExpr->get_type(), env );
1029 } else {
1030 AlternativeFinder finder( indexer, env );
1031 finder.find( attrExpr->get_expr() );
1032 for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
1033 if ( choice->expr->get_result()->size() == 1 ) {
1034 resolveAttr(*i, function, choice->expr->get_result(), choice->env );
1035 } // fi
1036 } // for
1037 } // if
1038 } // if
1039 } // if
1040 } // for
1041 } else {
1042 for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1043 VariableExpr newExpr( *i );
1044 alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) );
1045 renameTypes( alternatives.back().expr );
1046 } // for
1047 } // if
1048 }
1049
1050 void AlternativeFinder::visit( LogicalExpr *logicalExpr ) {
1051 AlternativeFinder firstFinder( indexer, env );
1052 firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
1053 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1054 AlternativeFinder secondFinder( indexer, first->env );
1055 secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
1056 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1057 LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() );
1058 alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) );
1059 }
1060 }
1061 }
1062
1063 void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) {
1064 // find alternatives for condition
1065 AlternativeFinder firstFinder( indexer, env );
1066 firstFinder.findWithAdjustment( conditionalExpr->get_arg1() );
1067 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1068 // find alternatives for true expression
1069 AlternativeFinder secondFinder( indexer, first->env );
1070 secondFinder.findWithAdjustment( conditionalExpr->get_arg2() );
1071 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1072 // find alterantives for false expression
1073 AlternativeFinder thirdFinder( indexer, second->env );
1074 thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() );
1075 for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) {
1076 // unify true and false types, then infer parameters to produce new alternatives
1077 OpenVarSet openVars;
1078 AssertionSet needAssertions, haveAssertions;
1079 Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost );
1080 Type* commonType = nullptr;
1081 if ( unify( second->expr->get_result(), third->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1082 ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() );
1083 newExpr->set_result( commonType ? commonType : second->expr->get_result()->clone() );
1084 newAlt.expr = newExpr;
1085 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1086 } // if
1087 } // for
1088 } // for
1089 } // for
1090 }
1091
1092 void AlternativeFinder::visit( CommaExpr *commaExpr ) {
1093 TypeEnvironment newEnv( env );
1094 Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
1095 AlternativeFinder secondFinder( indexer, newEnv );
1096 secondFinder.findWithAdjustment( commaExpr->get_arg2() );
1097 for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) {
1098 alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) );
1099 } // for
1100 delete newFirstArg;
1101 }
1102
1103 void AlternativeFinder::visit( RangeExpr * rangeExpr ) {
1104 // resolve low and high, accept alternatives whose low and high types unify
1105 AlternativeFinder firstFinder( indexer, env );
1106 firstFinder.findWithAdjustment( rangeExpr->get_low() );
1107 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1108 AlternativeFinder secondFinder( indexer, first->env );
1109 secondFinder.findWithAdjustment( rangeExpr->get_high() );
1110 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1111 OpenVarSet openVars;
1112 AssertionSet needAssertions, haveAssertions;
1113 Alternative newAlt( 0, second->env, first->cost + second->cost );
1114 Type* commonType = nullptr;
1115 if ( unify( first->expr->get_result(), second->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
1116 RangeExpr *newExpr = new RangeExpr( first->expr->clone(), second->expr->clone() );
1117 newExpr->set_result( commonType ? commonType : first->expr->get_result()->clone() );
1118 newAlt.expr = newExpr;
1119 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1120 } // if
1121 } // for
1122 } // for
1123 }
1124
1125 void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) {
1126 std::list< AlternativeFinder > subExprAlternatives;
1127 findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) );
1128 std::list< AltList > possibilities;
1129 combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) );
1130 for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) {
1131 std::list< Expression * > exprs;
1132 makeExprList( *i, exprs );
1133
1134 TypeEnvironment compositeEnv;
1135 simpleCombineEnvironments( i->begin(), i->end(), compositeEnv );
1136 alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) );
1137 } // for
1138 }
1139
1140 void AlternativeFinder::visit( TupleExpr *tupleExpr ) {
1141 alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1142 }
1143
1144 void AlternativeFinder::visit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
1145 alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
1146 }
1147
1148 void AlternativeFinder::visit( ConstructorExpr * ctorExpr ) {
1149 AlternativeFinder finder( indexer, env );
1150 // don't prune here, since it's guaranteed all alternatives will have the same type
1151 // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
1152 finder.findWithAdjustment( ctorExpr->get_callExpr(), false );
1153 for ( Alternative & alt : finder.alternatives ) {
1154 alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
1155 }
1156 }
1157
1158 void AlternativeFinder::visit( TupleIndexExpr *tupleExpr ) {
1159 alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1160 }
1161
1162 void AlternativeFinder::visit( TupleAssignExpr *tupleAssignExpr ) {
1163 alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) );
1164 }
1165
1166 void AlternativeFinder::visit( UniqueExpr *unqExpr ) {
1167 AlternativeFinder finder( indexer, env );
1168 finder.findWithAdjustment( unqExpr->get_expr() );
1169 for ( Alternative & alt : finder.alternatives ) {
1170 // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
1171 UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
1172 alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
1173 }
1174 }
1175
1176 void AlternativeFinder::visit( StmtExpr *stmtExpr ) {
1177 StmtExpr * newStmtExpr = stmtExpr->clone();
1178 ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
1179 // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
1180 alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
1181 }
1182
1183} // namespace ResolvExpr
1184
1185// Local Variables: //
1186// tab-width: 4 //
1187// mode: c++ //
1188// compile-command: "make install" //
1189// End: //
Note: See TracBrowser for help on using the repository browser.