source: src/ResolvExpr/AlternativeFinder.cc@ 0c286cf

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 0c286cf was 53e3b4a, checked in by Rob Schluntz <rschlunt@…>, 9 years ago

refactored computeConversionCost, add ttype parameter handling to instantiate argument, add simple ttype handling code to Unify
  • Property mode set to 100644
File size: 48.0 KB
RevLine 
[a32b204]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//
[6ed1d4b]7// AlternativeFinder.cc --
[a32b204]8//
9// Author : Richard C. Bilson
10// Created On : Sat May 16 23:52:08 2015
[e04ef3a]11// Last Modified By : Peter A. Buhr
[8e9cbb2]12// Last Modified On : Mon Jul 4 17:02:51 2016
13// Update Count : 29
[a32b204]14//
15
[51b73452]16#include <list>
17#include <iterator>
18#include <algorithm>
19#include <functional>
20#include <cassert>
[ebf5689]21#include <unordered_map>
22#include <utility>
23#include <vector>
[51b73452]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"
[6eb8948]40#include "Tuples/Tuples.h"
[141b786]41#include "Tuples/Explode.h"
[d3b7937]42#include "Common/utility.h"
[70f89d00]43#include "InitTweak/InitTweak.h"
[77971f6]44#include "InitTweak/GenInit.h"
[85517ddb]45#include "ResolveTypeof.h"
[722617d]46#include "Resolver.h"
[51b73452]47
[b87a5ed]48extern bool resolvep;
[6ed1d4b]49#define PRINT( text ) if ( resolvep ) { text }
[51b73452]50//#define DEBUG_COST
51
52namespace ResolvExpr {
[a32b204]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
[908cc83]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
[a32b204]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 }
[d9a0e76]83
[a32b204]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 }
[d9a0e76]89
[a32b204]90 struct PruneStruct {
91 bool isAmbiguous;
92 AltList::iterator candidate;
93 PruneStruct() {}
94 PruneStruct( AltList::iterator candidate ): isAmbiguous( false ), candidate( candidate ) {}
95 };
96
[0f19d763]97 /// Prunes a list of alternatives down to those that have the minimum conversion cost for a given return type; skips ambiguous interpretations
[a32b204]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;
[906e24d]105 {
106 Type * newType = candidate->expr->get_result()->clone();
[a32b204]107 candidate->env.apply( newType );
[906e24d]108 mangleName = SymTab::Mangler::mangle( newType );
[a32b204]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(
[6ed1d4b]115 std::cerr << "cost " << candidate->cost << " beats " << mapPlace->second.candidate->cost << std::endl;
[7c64920]116 )
[0f19d763]117 selected[ mangleName ] = current;
[a32b204]118 } else if ( candidate->cost == mapPlace->second.candidate->cost ) {
119 PRINT(
[6ed1d4b]120 std::cerr << "marking ambiguous" << std::endl;
[7c64920]121 )
[0f19d763]122 mapPlace->second.isAmbiguous = true;
[a32b204]123 }
124 } else {
125 selected[ mangleName ] = current;
126 }
127 }
[d9a0e76]128
129 PRINT(
[6ed1d4b]130 std::cerr << "there are " << selected.size() << " alternatives before elimination" << std::endl;
[7c64920]131 )
[a32b204]132
[0f19d763]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;
[906e24d]137 alt.env.applyFree( alt.expr->get_result() );
[0f19d763]138 *out++ = alt;
[a32b204]139 }
[0f19d763]140 }
[d9a0e76]141 }
[a32b204]142
143 void renameTypes( Expression *expr ) {
[906e24d]144 expr->get_result()->accept( global_renamer );
[e76acbe]145 }
[d9a0e76]146 }
147
[a32b204]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(
[6ed1d4b]158 std::cerr << "findSubExprs" << std::endl;
159 printAlts( finder.alternatives, std::cerr );
[7c64920]160 )
[0f19d763]161 *out++ = finder;
[a32b204]162 }
[d9a0e76]163 }
164
[a32b204]165 AlternativeFinder::AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env )
166 : indexer( indexer ), env( env ) {
[d9a0e76]167 }
[51b73452]168
[b6fe7e6]169 void AlternativeFinder::find( Expression *expr, bool adjust, bool prune ) {
[a32b204]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 ) {
[906e24d]176 adjustExprType( i->expr->get_result(), i->env, indexer );
[a32b204]177 }
178 }
[b6fe7e6]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;
[7933351]188 stream << "Can't choose between " << alternatives.size() << " alternatives for expression ";
[b6fe7e6]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 )
[a32b204]200 }
[8e9cbb2]201
202 // Central location to handle gcc extension keyword for all expression types.
203 for ( Alternative &iter: alternatives ) {
204 iter.expr->set_extension( expr->get_extension() );
205 } // for
[0f19d763]206 }
[d9a0e76]207
[b6fe7e6]208 void AlternativeFinder::findWithAdjustment( Expression *expr, bool prune ) {
209 find( expr, true, prune );
[d9a0e76]210 }
[a32b204]211
[77971f6]212 // std::unordered_map< Expression *, UniqueExpr * > ;
213
[a32b204]214 template< typename StructOrUnionType >
[add7117]215 void AlternativeFinder::addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) {
[bf32bb8]216 // by this point, member must be a name expr
217 NameExpr * nameExpr = safe_dynamic_cast< NameExpr * >( member );
218 const std::string & name = nameExpr->get_name();
219 std::list< Declaration* > members;
220 aggInst->lookup( name, members );
221 for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
222 if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
[d9fa60a]223 alternatives.push_back( Alternative( new MemberExpr( dwt, expr->clone() ), env, newCost ) );
[bf32bb8]224 renameTypes( alternatives.back().expr );
225 } else {
226 assert( false );
[a32b204]227 }
228 }
[d9a0e76]229 }
[a32b204]230
[848ce71]231 void AlternativeFinder::addTupleMembers( TupleType * tupleType, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) {
232 if ( ConstantExpr * constantExpr = dynamic_cast< ConstantExpr * >( member ) ) {
233 // get the value of the constant expression as an int, must be between 0 and the length of the tuple type to have meaning
234 // xxx - this should be improved by memoizing the value of constant exprs
235 // during parsing and reusing that information here.
236 std::stringstream ss( constantExpr->get_constant()->get_value() );
237 int val;
238 std::string tmp;
239 if ( ss >> val && ! (ss >> tmp) ) {
240 if ( val >= 0 && (unsigned int)val < tupleType->size() ) {
241 alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
242 } // if
243 } // if
[141b786]244 } else if ( NameExpr * nameExpr = dynamic_cast< NameExpr * >( member ) ) {
245 // xxx - temporary hack until 0/1 are int constants
246 if ( nameExpr->get_name() == "0" || nameExpr->get_name() == "1" ) {
247 std::stringstream ss( nameExpr->get_name() );
248 int val;
249 ss >> val;
250 alternatives.push_back( Alternative( new TupleIndexExpr( expr->clone(), val ), env, newCost ) );
251 }
[848ce71]252 } // if
253 }
254
[a32b204]255 void AlternativeFinder::visit( ApplicationExpr *applicationExpr ) {
256 alternatives.push_back( Alternative( applicationExpr->clone(), env, Cost::zero ) );
[d9a0e76]257 }
258
[a32b204]259 Cost computeConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) {
[8f7cea1]260 ApplicationExpr *appExpr = safe_dynamic_cast< ApplicationExpr* >( alt.expr );
[906e24d]261 PointerType *pointer = safe_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
[8f7cea1]262 FunctionType *function = safe_dynamic_cast< FunctionType* >( pointer->get_base() );
[a32b204]263
264 Cost convCost( 0, 0, 0 );
265 std::list< DeclarationWithType* >& formals = function->get_parameters();
266 std::list< DeclarationWithType* >::iterator formal = formals.begin();
267 std::list< Expression* >& actuals = appExpr->get_args();
[0362d42]268
[a32b204]269 for ( std::list< Expression* >::iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) {
[53e3b4a]270 Type * actualType = (*actualExpr)->get_result();
[a32b204]271 PRINT(
[6ed1d4b]272 std::cerr << "actual expression:" << std::endl;
273 (*actualExpr)->print( std::cerr, 8 );
274 std::cerr << "--- results are" << std::endl;
[53e3b4a]275 actualType->print( std::cerr, 8 );
[7c64920]276 )
[a32b204]277 Cost actualCost;
[53e3b4a]278 if ( formal == formals.end() ) {
279 if ( function->get_isVarArgs() ) {
280 convCost += Cost( 1, 0, 0 );
281 continue;
282 } else {
283 return Cost::infinity;
[7c64920]284 }
[53e3b4a]285 }
286 Type * formalType = (*formal)->get_type();
287 PRINT(
288 std::cerr << std::endl << "converting ";
289 actualType->print( std::cerr, 8 );
290 std::cerr << std::endl << " to ";
291 formalType->print( std::cerr, 8 );
292 )
293 Cost newCost = conversionCost( actualType, formalType, indexer, alt.env );
294 PRINT(
295 std::cerr << std::endl << "cost is" << newCost << std::endl;
296 )
[a32b204]297
[53e3b4a]298 if ( newCost == Cost::infinity ) {
299 return newCost;
[a32b204]300 }
[53e3b4a]301 convCost += newCost;
302 actualCost += newCost;
[a32b204]303 if ( actualCost != Cost( 0, 0, 0 ) ) {
[53e3b4a]304 Type *newType = formalType->clone();
305 alt.env.apply( newType );
306 *actualExpr = new CastExpr( *actualExpr, newType );
[a32b204]307 }
[53e3b4a]308 convCost += Cost( 0, polyCost( formalType, alt.env, indexer ) + polyCost( actualType, alt.env, indexer ), 0 );
309 ++formal; // can't be in for-loop update because of the continue
[d9a0e76]310 }
[a32b204]311 if ( formal != formals.end() ) {
312 return Cost::infinity;
[d9a0e76]313 }
314
[a32b204]315 for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) {
316 PRINT(
[6ed1d4b]317 std::cerr << std::endl << "converting ";
318 assert->second.actualType->print( std::cerr, 8 );
319 std::cerr << std::endl << " to ";
320 assert->second.formalType->print( std::cerr, 8 );
[02cea2d]321 )
322 Cost newCost = conversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env );
[a32b204]323 PRINT(
[6ed1d4b]324 std::cerr << std::endl << "cost of conversion is " << newCost << std::endl;
[02cea2d]325 )
326 if ( newCost == Cost::infinity ) {
327 return newCost;
328 }
[a32b204]329 convCost += newCost;
330 convCost += Cost( 0, polyCost( assert->second.formalType, alt.env, indexer ) + polyCost( assert->second.actualType, alt.env, indexer ), 0 );
331 }
[d9a0e76]332
[a32b204]333 return convCost;
334 }
[d9a0e76]335
[8c84ebd]336 /// Adds type variables to the open variable set and marks their assertions
[a32b204]337 void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ) {
[8c49c0e]338 for ( Type::ForallList::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
[2c57025]339 unifiableVars[ (*tyvar)->get_name() ] = TypeDecl::Data{ *tyvar };
[a32b204]340 for ( std::list< DeclarationWithType* >::iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) {
341 needAssertions[ *assert ] = true;
342 }
[d9a0e76]343/// needAssertions.insert( needAssertions.end(), (*tyvar)->get_assertions().begin(), (*tyvar)->get_assertions().end() );
344 }
345 }
[a32b204]346
[aefcc3b]347 /// instantiate a single argument by matching actuals from [actualIt, actualEnd) against formalType,
348 /// producing expression(s) in out and their total cost in cost.
349 template< typename AltIterator, typename OutputIterator >
350 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 ) {
351 if ( TupleType * tupleType = dynamic_cast< TupleType * >( formalType ) ) {
352 // formalType is a TupleType - group actuals into a TupleExpr whose type unifies with the TupleType
353 TupleExpr * tupleExpr = new TupleExpr();
354 for ( Type * type : *tupleType ) {
355 if ( ! instantiateArgument( type, defaultValue, actualIt, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( tupleExpr->get_exprs() ) ) ) {
356 delete tupleExpr;
357 return false;
358 }
359 }
360 tupleExpr->set_result( Tuples::makeTupleType( tupleExpr->get_exprs() ) );
361 *out++ = tupleExpr;
362 } else if ( actualIt != actualEnd ) {
[53e3b4a]363 if ( TypeInstType * ttype = Tuples::isTtype( formalType ) ) {
364 // xxx - mixing default arguments with variadic??
365 if ( ! Tuples::isTtype( actualIt->expr->get_result() ) ) {
366 // xxx - what if passing multiple arguments, last of which is ttype?
367
368 // consume all remaining arguments, variadic style
369 std::list< Expression * > exprs;
370 for ( ; actualIt != actualEnd; ++actualIt ) {
371 exprs.push_back( actualIt->expr->clone() );
372 cost += actualIt->cost;
373 }
374 TupleExpr * arg = new TupleExpr( exprs );
375 assert( arg->get_result() );
376 // unification run for side effects
377 bool unifyResult = unify( ttype, arg->get_result(), resultEnv, resultNeed, resultHave, openVars, indexer );
378 assertf( unifyResult, "Somehow unifying ttype failed..." );
379 *out++ = arg;
380 return true;
381 }
382 }
[aefcc3b]383 // both actualType and formalType are atomic (non-tuple) types - if they unify
384 // then accept actual as an argument, otherwise return false (fail to instantiate argument)
385 Expression * actual = actualIt->expr;
386 Type * actualType = actual->get_result();
387 PRINT(
388 std::cerr << "formal type is ";
389 formalType->print( std::cerr );
390 std::cerr << std::endl << "actual type is ";
391 actualType->print( std::cerr );
392 std::cerr << std::endl;
393 )
394 if ( ! unify( formalType, actualType, resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
395 return false;
396 }
397 // move the expression from the alternative to the output iterator
398 *out++ = actual;
399 actualIt->expr = nullptr;
400 cost += actualIt->cost;
401 ++actualIt;
402 } else {
403 // End of actuals - Handle default values
404 if ( SingleInit *si = dynamic_cast<SingleInit *>( defaultValue )) {
405 // so far, only constant expressions are accepted as default values
406 if ( ConstantExpr *cnstexpr = dynamic_cast<ConstantExpr *>( si->get_value()) ) {
407 if ( Constant *cnst = dynamic_cast<Constant *>( cnstexpr->get_constant() ) ) {
408 if ( unify( formalType, cnst->get_type(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
409 // xxx - Don't know if this is right
410 *out++ = cnstexpr->clone();
411 return true;
412 } // if
413 } // if
414 } // if
415 } // if
416 return false;
417 } // if
418 return true;
419 }
420
421 bool AlternativeFinder::instantiateFunction( std::list< DeclarationWithType* >& formals, const AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave, AltList & out ) {
[a32b204]422 simpleCombineEnvironments( actuals.begin(), actuals.end(), resultEnv );
423 // make sure we don't widen any existing bindings
424 for ( TypeEnvironment::iterator i = resultEnv.begin(); i != resultEnv.end(); ++i ) {
425 i->allowWidening = false;
426 }
427 resultEnv.extractOpenVars( openVars );
428
[aefcc3b]429 // flatten actuals so that each actual has an atomic (non-tuple) type
430 AltList exploded;
[77971f6]431 Tuples::explode( actuals, indexer, back_inserter( exploded ) );
[aefcc3b]432
433 AltList::iterator actualExpr = exploded.begin();
434 AltList::iterator actualEnd = exploded.end();
435 for ( DeclarationWithType * formal : formals ) {
436 // match flattened actuals with formal parameters - actuals will be grouped to match
437 // with formals as appropriate
438 Cost cost;
439 std::list< Expression * > newExprs;
440 ObjectDecl * obj = safe_dynamic_cast< ObjectDecl * >( formal );
441 if ( ! instantiateArgument( obj->get_type(), obj->get_init(), actualExpr, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( newExprs ) ) ) {
442 deleteAll( newExprs );
443 return false;
[a32b204]444 }
[aefcc3b]445 // success - produce argument as a new alternative
446 assert( newExprs.size() == 1 );
447 out.push_back( Alternative( newExprs.front(), resultEnv, cost ) );
[a32b204]448 }
[aefcc3b]449 if ( actualExpr != actualEnd ) {
450 // there are still actuals remaining, but we've run out of formal parameters to match against
451 // this is okay only if the function is variadic
452 if ( ! isVarArgs ) {
453 return false;
454 }
455 out.splice( out.end(), exploded, actualExpr, actualEnd );
[a32b204]456 }
457 return true;
[d9a0e76]458 }
[51b73452]459
[89b686a]460 // /// Map of declaration uniqueIds (intended to be the assertions in an AssertionSet) to their parents and the number of times they've been included
461 //typedef std::unordered_map< UniqueId, std::unordered_map< UniqueId, unsigned > > AssertionParentSet;
[79970ed]462
[a1d7679]463 static const int recursionLimit = /*10*/ 4; ///< Limit to depth of recursion satisfaction
[89b686a]464 //static const unsigned recursionParentLimit = 1; ///< Limit to the number of times an assertion can recursively use itself
[51b73452]465
[a32b204]466 void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) {
467 for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) {
468 if ( i->second == true ) {
469 i->first->accept( indexer );
470 }
471 }
[d9a0e76]472 }
[79970ed]473
[a32b204]474 template< typename ForwardIterator, typename OutputIterator >
[79970ed]475 void inferRecursive( ForwardIterator begin, ForwardIterator end, const Alternative &newAlt, OpenVarSet &openVars, const SymTab::Indexer &decls, const AssertionSet &newNeed, /*const AssertionParentSet &needParents,*/
[ebf5689]476 int level, const SymTab::Indexer &indexer, OutputIterator out ) {
[a32b204]477 if ( begin == end ) {
478 if ( newNeed.empty() ) {
479 *out++ = newAlt;
480 return;
481 } else if ( level >= recursionLimit ) {
482 throw SemanticError( "Too many recursive assertions" );
483 } else {
484 AssertionSet newerNeed;
485 PRINT(
486 std::cerr << "recursing with new set:" << std::endl;
487 printAssertionSet( newNeed, std::cerr, 8 );
[7c64920]488 )
[89b686a]489 inferRecursive( newNeed.begin(), newNeed.end(), newAlt, openVars, decls, newerNeed, /*needParents,*/ level+1, indexer, out );
[a32b204]490 return;
491 }
492 }
493
494 ForwardIterator cur = begin++;
495 if ( ! cur->second ) {
[89b686a]496 inferRecursive( begin, end, newAlt, openVars, decls, newNeed, /*needParents,*/ level, indexer, out );
[7933351]497 return; // xxx - should this continue? previously this wasn't here, and it looks like it should be
[a32b204]498 }
499 DeclarationWithType *curDecl = cur->first;
[7933351]500
[d9a0e76]501 PRINT(
[a32b204]502 std::cerr << "inferRecursive: assertion is ";
503 curDecl->print( std::cerr );
504 std::cerr << std::endl;
[7c64920]505 )
[0f19d763]506 std::list< DeclarationWithType* > candidates;
[a32b204]507 decls.lookupId( curDecl->get_name(), candidates );
[6ed1d4b]508/// if ( candidates.empty() ) { std::cerr << "no candidates!" << std::endl; }
[a32b204]509 for ( std::list< DeclarationWithType* >::const_iterator candidate = candidates.begin(); candidate != candidates.end(); ++candidate ) {
510 PRINT(
[6ed1d4b]511 std::cerr << "inferRecursive: candidate is ";
512 (*candidate)->print( std::cerr );
513 std::cerr << std::endl;
[7c64920]514 )
[79970ed]515
[0f19d763]516 AssertionSet newHave, newerNeed( newNeed );
[a32b204]517 TypeEnvironment newEnv( newAlt.env );
518 OpenVarSet newOpenVars( openVars );
519 Type *adjType = (*candidate)->get_type()->clone();
520 adjustExprType( adjType, newEnv, indexer );
521 adjType->accept( global_renamer );
522 PRINT(
523 std::cerr << "unifying ";
524 curDecl->get_type()->print( std::cerr );
525 std::cerr << " with ";
526 adjType->print( std::cerr );
527 std::cerr << std::endl;
[7c64920]528 )
[0f19d763]529 if ( unify( curDecl->get_type(), adjType, newEnv, newerNeed, newHave, newOpenVars, indexer ) ) {
530 PRINT(
531 std::cerr << "success!" << std::endl;
[a32b204]532 )
[0f19d763]533 SymTab::Indexer newDecls( decls );
534 addToIndexer( newHave, newDecls );
535 Alternative newerAlt( newAlt );
536 newerAlt.env = newEnv;
537 assert( (*candidate)->get_uniqueId() );
[22cad76]538 DeclarationWithType *candDecl = static_cast< DeclarationWithType* >( Declaration::declFromId( (*candidate)->get_uniqueId() ) );
[89b686a]539 //AssertionParentSet newNeedParents( needParents );
[22cad76]540 // skip repeatingly-self-recursive assertion satisfaction
[89b686a]541 // DOESN'T WORK: grandchild nodes conflict with their cousins
542 //if ( newNeedParents[ curDecl->get_uniqueId() ][ candDecl->get_uniqueId() ]++ > recursionParentLimit ) continue;
[22cad76]543 Expression *varExpr = new VariableExpr( candDecl );
[906e24d]544 delete varExpr->get_result();
545 varExpr->set_result( adjType->clone() );
[0f19d763]546 PRINT(
[6ed1d4b]547 std::cerr << "satisfying assertion " << curDecl->get_uniqueId() << " ";
548 curDecl->print( std::cerr );
549 std::cerr << " with declaration " << (*candidate)->get_uniqueId() << " ";
550 (*candidate)->print( std::cerr );
551 std::cerr << std::endl;
[7c64920]552 )
[0f19d763]553 ApplicationExpr *appExpr = static_cast< ApplicationExpr* >( newerAlt.expr );
554 // XXX: this is a memory leak, but adjType can't be deleted because it might contain assertions
555 appExpr->get_inferParams()[ curDecl->get_uniqueId() ] = ParamEntry( (*candidate)->get_uniqueId(), adjType->clone(), curDecl->get_type()->clone(), varExpr );
[89b686a]556 inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, /*newNeedParents,*/ level, indexer, out );
[0f19d763]557 } else {
558 delete adjType;
559 }
[a32b204]560 }
[d9a0e76]561 }
562
[a32b204]563 template< typename OutputIterator >
564 void AlternativeFinder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) {
[d9a0e76]565// PRINT(
[6ed1d4b]566// std::cerr << "inferParameters: assertions needed are" << std::endl;
567// printAll( need, std::cerr, 8 );
[d9a0e76]568// )
[a32b204]569 SymTab::Indexer decls( indexer );
570 PRINT(
[6ed1d4b]571 std::cerr << "============= original indexer" << std::endl;
572 indexer.print( std::cerr );
573 std::cerr << "============= new indexer" << std::endl;
574 decls.print( std::cerr );
[7c64920]575 )
[0f19d763]576 addToIndexer( have, decls );
[a32b204]577 AssertionSet newNeed;
[89b686a]578 //AssertionParentSet needParents;
579 inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, /*needParents,*/ 0, indexer, out );
[d9a0e76]580// PRINT(
[6ed1d4b]581// std::cerr << "declaration 14 is ";
[d9a0e76]582// Declaration::declFromId
583// *out++ = newAlt;
584// )
585 }
586
[a32b204]587 template< typename OutputIterator >
[aefcc3b]588 void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const AltList &actualAlt, OutputIterator out ) {
[a32b204]589 OpenVarSet openVars;
590 AssertionSet resultNeed, resultHave;
591 TypeEnvironment resultEnv;
592 makeUnifiableVars( funcType, openVars, resultNeed );
[aefcc3b]593 AltList instantiatedActuals; // filled by instantiate function
[53e3b4a]594 if ( targetType && ! targetType->isVoid() && ! funcType->get_returnVals().empty() ) {
[ea83e00a]595 // attempt to narrow based on expected target type
596 Type * returnType = funcType->get_returnVals().front()->get_type();
597 if ( ! unify( returnType, targetType, resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
598 // unification failed, don't pursue this alternative
599 return;
600 }
601 }
602
[aefcc3b]603 if ( instantiateFunction( funcType->get_parameters(), actualAlt, funcType->get_isVarArgs(), openVars, resultEnv, resultNeed, resultHave, instantiatedActuals ) ) {
[a32b204]604 ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
[aefcc3b]605 Alternative newAlt( appExpr, resultEnv, sumCost( instantiatedActuals ) );
606 makeExprList( instantiatedActuals, appExpr->get_args() );
[a32b204]607 PRINT(
[6ed1d4b]608 std::cerr << "need assertions:" << std::endl;
609 printAssertionSet( resultNeed, std::cerr, 8 );
[7c64920]610 )
[0f19d763]611 inferParameters( resultNeed, resultHave, newAlt, openVars, out );
[d9a0e76]612 }
613 }
614
[a32b204]615 void AlternativeFinder::visit( UntypedExpr *untypedExpr ) {
616 bool doneInit = false;
617 AlternativeFinder funcOpFinder( indexer, env );
[d9a0e76]618
[6ed1d4b]619 AlternativeFinder funcFinder( indexer, env );
620
621 {
[70f89d00]622 std::string fname = InitTweak::getFunctionName( untypedExpr );
623 if ( fname == "&&" ) {
[2871210]624 VoidType v = Type::Qualifiers(); // resolve to type void *
625 PointerType pt( Type::Qualifiers(), v.clone() );
626 UntypedExpr *vexpr = untypedExpr->clone();
[906e24d]627 vexpr->set_result( pt.clone() );
[2871210]628 alternatives.push_back( Alternative( vexpr, env, Cost()) );
[a32b204]629 return;
630 }
631 }
[d9a0e76]632
[a32b204]633 funcFinder.findWithAdjustment( untypedExpr->get_function() );
634 std::list< AlternativeFinder > argAlternatives;
635 findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), back_inserter( argAlternatives ) );
[d9a0e76]636
[a32b204]637 std::list< AltList > possibilities;
638 combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) );
[d9a0e76]639
[5af62f1]640 // take care of possible tuple assignments
641 // if not tuple assignment, assignment is taken care of as a normal function call
642 Tuples::handleTupleAssignment( *this, untypedExpr, possibilities );
[d9a0e76]643
[a32b204]644 AltList candidates;
[91b8a17]645 SemanticError errors;
[a32b204]646 for ( AltList::const_iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) {
[91b8a17]647 try {
648 PRINT(
649 std::cerr << "working on alternative: " << std::endl;
650 func->print( std::cerr, 8 );
651 )
652 // check if the type is pointer to function
653 PointerType *pointer;
[906e24d]654 if ( ( pointer = dynamic_cast< PointerType* >( func->expr->get_result() ) ) ) {
[91b8a17]655 if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
656 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
657 // XXX
658 //Designators::check_alternative( function, *actualAlt );
659 makeFunctionAlternatives( *func, function, *actualAlt, std::back_inserter( candidates ) );
660 }
661 } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( pointer->get_base() ) ) {
662 EqvClass eqvClass;
663 if ( func->env.lookup( typeInst->get_name(), eqvClass ) && eqvClass.type ) {
664 if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.type ) ) {
665 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
666 makeFunctionAlternatives( *func, function, *actualAlt, std::back_inserter( candidates ) );
667 } // for
668 } // if
[a32b204]669 } // if
670 } // if
[91b8a17]671 } else {
672 // seek a function operator that's compatible
673 if ( ! doneInit ) {
674 doneInit = true;
675 NameExpr *opExpr = new NameExpr( "?()" );
676 try {
677 funcOpFinder.findWithAdjustment( opExpr );
678 } catch( SemanticError &e ) {
679 // it's ok if there aren't any defined function ops
680 }
681 PRINT(
682 std::cerr << "known function ops:" << std::endl;
683 printAlts( funcOpFinder.alternatives, std::cerr, 8 );
684 )
[a32b204]685 }
686
[91b8a17]687 for ( AltList::const_iterator funcOp = funcOpFinder.alternatives.begin(); funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
688 // check if the type is pointer to function
689 PointerType *pointer;
[906e24d]690 if ( ( pointer = dynamic_cast< PointerType* >( funcOp->expr->get_result() ) ) ) {
[91b8a17]691 if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
692 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
693 AltList currentAlt;
694 currentAlt.push_back( *func );
695 currentAlt.insert( currentAlt.end(), actualAlt->begin(), actualAlt->end() );
696 makeFunctionAlternatives( *funcOp, function, currentAlt, std::back_inserter( candidates ) );
697 } // for
698 } // if
[a32b204]699 } // if
[91b8a17]700 } // for
701 } // if
702 } catch ( SemanticError &e ) {
703 errors.append( e );
704 }
[a32b204]705 } // for
706
[91b8a17]707 // Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions
708 if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; }
709
[a32b204]710 for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) {
711 Cost cvtCost = computeConversionCost( *withFunc, indexer );
712
713 PRINT(
[8f7cea1]714 ApplicationExpr *appExpr = safe_dynamic_cast< ApplicationExpr* >( withFunc->expr );
[906e24d]715 PointerType *pointer = safe_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() );
[8f7cea1]716 FunctionType *function = safe_dynamic_cast< FunctionType* >( pointer->get_base() );
[6ed1d4b]717 std::cerr << "Case +++++++++++++" << std::endl;
718 std::cerr << "formals are:" << std::endl;
719 printAll( function->get_parameters(), std::cerr, 8 );
720 std::cerr << "actuals are:" << std::endl;
721 printAll( appExpr->get_args(), std::cerr, 8 );
722 std::cerr << "bindings are:" << std::endl;
723 withFunc->env.print( std::cerr, 8 );
724 std::cerr << "cost of conversion is:" << cvtCost << std::endl;
[7c64920]725 )
726 if ( cvtCost != Cost::infinity ) {
727 withFunc->cvtCost = cvtCost;
728 alternatives.push_back( *withFunc );
729 } // if
[a32b204]730 } // for
731 candidates.clear();
732 candidates.splice( candidates.end(), alternatives );
733
734 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( alternatives ) );
[ea83e00a]735
736 if ( alternatives.empty() && targetType && ! targetType->isVoid() ) {
737 // xxx - this is a temporary hack. If resolution is unsuccessful with a target type, try again without a
738 // target type, since it will sometimes succeed when it wouldn't easily with target type binding. For example,
739 // forall( otype T ) lvalue T ?[?]( T *, ptrdiff_t );
740 // const char * x = "hello world";
741 // unsigned char ch = x[0];
742 // Fails with simple return type binding. First, T is bound to unsigned char, then (x: const char *) is unified
743 // with unsigned char *, which fails because pointer base types must be unified exactly. The new resolver should
744 // fix this issue in a more robust way.
745 targetType = nullptr;
746 visit( untypedExpr );
747 }
[a32b204]748 }
749
750 bool isLvalue( Expression *expr ) {
[906e24d]751 // xxx - recurse into tuples?
752 return expr->has_result() && expr->get_result()->get_isLvalue();
[a32b204]753 }
754
755 void AlternativeFinder::visit( AddressExpr *addressExpr ) {
756 AlternativeFinder finder( indexer, env );
757 finder.find( addressExpr->get_arg() );
758 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
759 if ( isLvalue( i->expr ) ) {
760 alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) );
761 } // if
762 } // for
763 }
764
765 void AlternativeFinder::visit( CastExpr *castExpr ) {
[906e24d]766 Type *& toType = castExpr->get_result();
[7933351]767 assert( toType );
[906e24d]768 toType = resolveTypeof( toType, indexer );
769 SymTab::validateType( toType, &indexer );
770 adjustExprType( toType, env, indexer );
[a32b204]771
772 AlternativeFinder finder( indexer, env );
[7933351]773 finder.targetType = toType;
[a32b204]774 finder.findWithAdjustment( castExpr->get_arg() );
775
776 AltList candidates;
777 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
778 AssertionSet needAssertions, haveAssertions;
779 OpenVarSet openVars;
780
781 // It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a
782 // cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results
783 // that are cast directly. The candidate is invalid if it has fewer results than there are types to cast
784 // to.
[906e24d]785 int discardedValues = (*i).expr->get_result()->size() - castExpr->get_result()->size();
[a32b204]786 if ( discardedValues < 0 ) continue;
[7933351]787 // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not
788 // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3]))
[adcdd2f]789 // unification run for side-effects
[906e24d]790 unify( castExpr->get_result(), (*i).expr->get_result(), i->env, needAssertions, haveAssertions, openVars, indexer );
791 Cost thisCost = castCost( (*i).expr->get_result(), castExpr->get_result(), indexer, i->env );
[a32b204]792 if ( thisCost != Cost::infinity ) {
793 // count one safe conversion for each value that is thrown away
794 thisCost += Cost( 0, 0, discardedValues );
[7933351]795
796 Expression * argExpr = i->expr->clone();
797 if ( argExpr->get_result()->size() > 1 && ! castExpr->get_result()->isVoid() ) {
798 // Argument expression is a tuple and the target type is not void. Cast each member of the tuple
799 // to its corresponding target type, producing the tuple of those cast expressions. If there are
800 // more components of the tuple than components in the target type, then excess components do not
801 // come out in the result expression (but UniqueExprs ensure that side effects will still be done).
802 if ( Tuples::maybeImpure( argExpr ) && ! dynamic_cast< UniqueExpr * >( argExpr ) ) {
803 // expressions which may contain side effects require a single unique instance of the expression.
804 argExpr = new UniqueExpr( argExpr );
805 }
806 std::list< Expression * > componentExprs;
807 for ( unsigned int i = 0; i < castExpr->get_result()->size(); i++ ) {
808 // cast each component
809 TupleIndexExpr * idx = new TupleIndexExpr( argExpr->clone(), i );
810 componentExprs.push_back( new CastExpr( idx, castExpr->get_result()->getComponent( i )->clone() ) );
811 }
812 delete argExpr;
813 assert( componentExprs.size() > 0 );
814 // produce the tuple of casts
815 candidates.push_back( Alternative( new TupleExpr( componentExprs ), i->env, i->cost, thisCost ) );
816 } else {
817 // handle normally
818 candidates.push_back( Alternative( new CastExpr( argExpr->clone(), toType->clone() ), i->env, i->cost, thisCost ) );
819 }
[a32b204]820 } // if
821 } // for
822
823 // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
824 // cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice
825 // selects first based on argument cost, then on conversion cost.
826 AltList minArgCost;
827 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
828 findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
829 }
830
831 void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) {
832 AlternativeFinder funcFinder( indexer, env );
833 funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
834 for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
[906e24d]835 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( agg->expr->get_result() ) ) {
836 addAggMembers( structInst, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
837 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( agg->expr->get_result() ) ) {
838 addAggMembers( unionInst, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
[848ce71]839 } else if ( TupleType * tupleType = dynamic_cast< TupleType * >( agg->expr->get_result() ) ) {
840 addTupleMembers( tupleType, agg->expr, agg->cost, agg->env, memberExpr->get_member() );
[a32b204]841 } // if
842 } // for
843 }
844
845 void AlternativeFinder::visit( MemberExpr *memberExpr ) {
846 alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
847 }
848
849 void AlternativeFinder::visit( NameExpr *nameExpr ) {
850 std::list< DeclarationWithType* > declList;
851 indexer.lookupId( nameExpr->get_name(), declList );
852 PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; )
[0f19d763]853 for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) {
854 VariableExpr newExpr( *i, nameExpr->get_argName() );
855 alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) );
856 PRINT(
857 std::cerr << "decl is ";
858 (*i)->print( std::cerr );
859 std::cerr << std::endl;
860 std::cerr << "newExpr is ";
861 newExpr.print( std::cerr );
862 std::cerr << std::endl;
[7c64920]863 )
[0f19d763]864 renameTypes( alternatives.back().expr );
865 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( (*i)->get_type() ) ) {
[3b58d91]866 NameExpr nameExpr( "" );
[add7117]867 addAggMembers( structInst, &newExpr, Cost( 0, 0, 1 ), env, &nameExpr );
[0f19d763]868 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( (*i)->get_type() ) ) {
[3b58d91]869 NameExpr nameExpr( "" );
[add7117]870 addAggMembers( unionInst, &newExpr, Cost( 0, 0, 1 ), env, &nameExpr );
[0f19d763]871 } // if
872 } // for
[a32b204]873 }
874
875 void AlternativeFinder::visit( VariableExpr *variableExpr ) {
[85517ddb]876 // not sufficient to clone here, because variable's type may have changed
877 // since the VariableExpr was originally created.
878 alternatives.push_back( Alternative( new VariableExpr( variableExpr->get_var() ), env, Cost::zero ) );
[a32b204]879 }
880
881 void AlternativeFinder::visit( ConstantExpr *constantExpr ) {
882 alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
883 }
884
885 void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) {
886 if ( sizeofExpr->get_isType() ) {
[85517ddb]887 // xxx - resolveTypeof?
[a32b204]888 alternatives.push_back( Alternative( sizeofExpr->clone(), env, Cost::zero ) );
889 } else {
890 // find all alternatives for the argument to sizeof
891 AlternativeFinder finder( indexer, env );
892 finder.find( sizeofExpr->get_expr() );
893 // find the lowest cost alternative among the alternatives, otherwise ambiguous
894 AltList winners;
895 findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
896 if ( winners.size() != 1 ) {
897 throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() );
898 } // if
899 // return the lowest cost alternative for the argument
900 Alternative &choice = winners.front();
901 alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
[47534159]902 } // if
903 }
904
905 void AlternativeFinder::visit( AlignofExpr *alignofExpr ) {
906 if ( alignofExpr->get_isType() ) {
[85517ddb]907 // xxx - resolveTypeof?
[47534159]908 alternatives.push_back( Alternative( alignofExpr->clone(), env, Cost::zero ) );
909 } else {
910 // find all alternatives for the argument to sizeof
911 AlternativeFinder finder( indexer, env );
912 finder.find( alignofExpr->get_expr() );
913 // find the lowest cost alternative among the alternatives, otherwise ambiguous
914 AltList winners;
915 findMinCost( finder.alternatives.begin(), finder.alternatives.end(), back_inserter( winners ) );
916 if ( winners.size() != 1 ) {
917 throw SemanticError( "Ambiguous expression in alignof operand: ", alignofExpr->get_expr() );
918 } // if
919 // return the lowest cost alternative for the argument
920 Alternative &choice = winners.front();
921 alternatives.push_back( Alternative( new AlignofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
[a32b204]922 } // if
923 }
924
[2a4b088]925 template< typename StructOrUnionType >
926 void AlternativeFinder::addOffsetof( StructOrUnionType *aggInst, const std::string &name ) {
927 std::list< Declaration* > members;
928 aggInst->lookup( name, members );
929 for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
930 if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
[79970ed]931 alternatives.push_back( Alternative( new OffsetofExpr( aggInst->clone(), dwt ), env, Cost::zero ) );
[2a4b088]932 renameTypes( alternatives.back().expr );
933 } else {
934 assert( false );
935 }
936 }
937 }
[6ed1d4b]938
[2a4b088]939 void AlternativeFinder::visit( UntypedOffsetofExpr *offsetofExpr ) {
940 AlternativeFinder funcFinder( indexer, env );
[85517ddb]941 // xxx - resolveTypeof?
[2a4b088]942 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( offsetofExpr->get_type() ) ) {
943 addOffsetof( structInst, offsetofExpr->get_member() );
944 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( offsetofExpr->get_type() ) ) {
945 addOffsetof( unionInst, offsetofExpr->get_member() );
946 }
947 }
[6ed1d4b]948
[25a054f]949 void AlternativeFinder::visit( OffsetofExpr *offsetofExpr ) {
950 alternatives.push_back( Alternative( offsetofExpr->clone(), env, Cost::zero ) );
[afc1045]951 }
952
953 void AlternativeFinder::visit( OffsetPackExpr *offsetPackExpr ) {
954 alternatives.push_back( Alternative( offsetPackExpr->clone(), env, Cost::zero ) );
[25a054f]955 }
956
[a32b204]957 void AlternativeFinder::resolveAttr( DeclarationWithType *funcDecl, FunctionType *function, Type *argType, const TypeEnvironment &env ) {
958 // assume no polymorphism
959 // assume no implicit conversions
960 assert( function->get_parameters().size() == 1 );
961 PRINT(
[6ed1d4b]962 std::cerr << "resolvAttr: funcDecl is ";
963 funcDecl->print( std::cerr );
964 std::cerr << " argType is ";
965 argType->print( std::cerr );
966 std::cerr << std::endl;
[7c64920]967 )
968 if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
969 alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) );
970 for ( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) {
[906e24d]971 alternatives.back().expr->set_result( (*i)->get_type()->clone() );
[7c64920]972 } // for
973 } // if
[a32b204]974 }
975
976 void AlternativeFinder::visit( AttrExpr *attrExpr ) {
977 // assume no 'pointer-to-attribute'
978 NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
979 assert( nameExpr );
980 std::list< DeclarationWithType* > attrList;
981 indexer.lookupId( nameExpr->get_name(), attrList );
982 if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
983 for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
984 // check if the type is function
985 if ( FunctionType *function = dynamic_cast< FunctionType* >( (*i)->get_type() ) ) {
986 // assume exactly one parameter
987 if ( function->get_parameters().size() == 1 ) {
988 if ( attrExpr->get_isType() ) {
989 resolveAttr( *i, function, attrExpr->get_type(), env );
990 } else {
991 AlternativeFinder finder( indexer, env );
992 finder.find( attrExpr->get_expr() );
993 for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
[906e24d]994 if ( choice->expr->get_result()->size() == 1 ) {
995 resolveAttr(*i, function, choice->expr->get_result(), choice->env );
[a32b204]996 } // fi
997 } // for
998 } // if
999 } // if
1000 } // if
1001 } // for
1002 } else {
1003 for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
1004 VariableExpr newExpr( *i );
1005 alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) );
1006 renameTypes( alternatives.back().expr );
1007 } // for
1008 } // if
1009 }
1010
1011 void AlternativeFinder::visit( LogicalExpr *logicalExpr ) {
1012 AlternativeFinder firstFinder( indexer, env );
1013 firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
1014 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1015 AlternativeFinder secondFinder( indexer, first->env );
1016 secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
1017 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1018 LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() );
1019 alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) );
[d9a0e76]1020 }
1021 }
1022 }
[51b73452]1023
[a32b204]1024 void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) {
1025 AlternativeFinder firstFinder( indexer, env );
1026 firstFinder.findWithAdjustment( conditionalExpr->get_arg1() );
1027 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
1028 AlternativeFinder secondFinder( indexer, first->env );
1029 secondFinder.findWithAdjustment( conditionalExpr->get_arg2() );
1030 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
1031 AlternativeFinder thirdFinder( indexer, second->env );
1032 thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() );
1033 for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) {
1034 OpenVarSet openVars;
1035 AssertionSet needAssertions, haveAssertions;
1036 Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost );
[668e971a]1037 Type* commonType = nullptr;
[906e24d]1038 if ( unify( second->expr->get_result(), third->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
[a32b204]1039 ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() );
[906e24d]1040 newExpr->set_result( commonType ? commonType : second->expr->get_result()->clone() );
[a32b204]1041 newAlt.expr = newExpr;
1042 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
1043 } // if
1044 } // for
1045 } // for
1046 } // for
1047 }
1048
1049 void AlternativeFinder::visit( CommaExpr *commaExpr ) {
1050 TypeEnvironment newEnv( env );
1051 Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
1052 AlternativeFinder secondFinder( indexer, newEnv );
1053 secondFinder.findWithAdjustment( commaExpr->get_arg2() );
1054 for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) {
1055 alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) );
1056 } // for
1057 delete newFirstArg;
1058 }
1059
1060 void AlternativeFinder::visit( TupleExpr *tupleExpr ) {
1061 std::list< AlternativeFinder > subExprAlternatives;
1062 findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) );
1063 std::list< AltList > possibilities;
1064 combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) );
1065 for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) {
1066 TupleExpr *newExpr = new TupleExpr;
1067 makeExprList( *i, newExpr->get_exprs() );
[3c13c03]1068 newExpr->set_result( Tuples::makeTupleType( newExpr->get_exprs() ) );
[a32b204]1069
1070 TypeEnvironment compositeEnv;
1071 simpleCombineEnvironments( i->begin(), i->end(), compositeEnv );
1072 alternatives.push_back( Alternative( newExpr, compositeEnv, sumCost( *i ) ) );
1073 } // for
[d9a0e76]1074 }
[dc2e7e0]1075
1076 void AlternativeFinder::visit( ImplicitCopyCtorExpr * impCpCtorExpr ) {
1077 alternatives.push_back( Alternative( impCpCtorExpr->clone(), env, Cost::zero ) );
1078 }
[b6fe7e6]1079
1080 void AlternativeFinder::visit( ConstructorExpr * ctorExpr ) {
1081 AlternativeFinder finder( indexer, env );
1082 // don't prune here, since it's guaranteed all alternatives will have the same type
1083 // (giving the alternatives different types is half of the point of ConstructorExpr nodes)
1084 finder.findWithAdjustment( ctorExpr->get_callExpr(), false );
1085 for ( Alternative & alt : finder.alternatives ) {
1086 alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) );
1087 }
1088 }
[8f7cea1]1089
1090 void AlternativeFinder::visit( TupleIndexExpr *tupleExpr ) {
1091 alternatives.push_back( Alternative( tupleExpr->clone(), env, Cost::zero ) );
1092 }
[aa8f9df]1093
1094 void AlternativeFinder::visit( TupleAssignExpr *tupleAssignExpr ) {
1095 alternatives.push_back( Alternative( tupleAssignExpr->clone(), env, Cost::zero ) );
1096 }
[bf32bb8]1097
1098 void AlternativeFinder::visit( UniqueExpr *unqExpr ) {
1099 AlternativeFinder finder( indexer, env );
1100 finder.findWithAdjustment( unqExpr->get_expr() );
1101 for ( Alternative & alt : finder.alternatives ) {
[141b786]1102 // ensure that the id is passed on to the UniqueExpr alternative so that the expressions are "linked"
[77971f6]1103 UniqueExpr * newUnqExpr = new UniqueExpr( alt.expr->clone(), unqExpr->get_id() );
[141b786]1104 alternatives.push_back( Alternative( newUnqExpr, alt.env, alt.cost ) );
[bf32bb8]1105 }
1106 }
1107
[722617d]1108 void AlternativeFinder::visit( StmtExpr *stmtExpr ) {
1109 StmtExpr * newStmtExpr = stmtExpr->clone();
1110 ResolvExpr::resolveStmtExpr( newStmtExpr, indexer );
1111 // xxx - this env is almost certainly wrong, and needs to somehow contain the combined environments from all of the statements in the stmtExpr...
1112 alternatives.push_back( Alternative( newStmtExpr, env, Cost::zero ) );
1113 }
1114
[51b73452]1115} // namespace ResolvExpr
[a32b204]1116
1117// Local Variables: //
1118// tab-width: 4 //
1119// mode: c++ //
1120// compile-command: "make install" //
1121// End: //
Note: See TracBrowser for help on using the repository browser.