source: translator/ResolvExpr/AlternativeFinder.cc@ fe3b61b

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors ctor deferred_resn demangler enum forall-pointer-decay gc_noraii jacob/cs343-translation jenkins-sandbox memory new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new string with_gc
Last change on this file since fe3b61b was d9a0e76, checked in by Peter A. Buhr <pabuhr@…>, 11 years ago

remove Parser.old, add -XCFA to driver, copy ptrdiff_t from stddef.h in preclude, remove casts from initialization constants, adjust formatting
  • Property mode set to 100644
File size: 36.9 KB
RevLine 
[51b73452]1#include <list>
2#include <iterator>
3#include <algorithm>
4#include <functional>
5#include <cassert>
6
7#include "AlternativeFinder.h"
8#include "Alternative.h"
9#include "Cost.h"
10#include "typeops.h"
11#include "Unify.h"
12#include "RenameVars.h"
13#include "SynTree/Type.h"
14#include "SynTree/Declaration.h"
15#include "SynTree/Expression.h"
16#include "SynTree/Initializer.h"
17#include "SynTree/Visitor.h"
18#include "SymTab/Indexer.h"
19#include "SymTab/Mangler.h"
20#include "SynTree/TypeSubstitution.h"
21#include "SymTab/Validate.h"
22#include "Designators/Processor.h"
23#include "Tuples/TupleAssignment.h"
24#include "Tuples/NameMatcher.h"
25#include "utility.h"
26
[d9a0e76]27extern bool resolveVerbose;
28#define PRINT( text ) if ( resolveVerbose ) { text }
[51b73452]29//#define DEBUG_COST
30
31namespace ResolvExpr {
[d9a0e76]32 Expression *resolveInVoidContext( Expression *expr, const SymTab::Indexer &indexer, TypeEnvironment &env ) {
33 CastExpr *castToVoid = new CastExpr( expr );
34
35 AlternativeFinder finder( indexer, env );
36 finder.findWithAdjustment( castToVoid );
37
38 // it's a property of the language that a cast expression has either 1 or 0 interpretations; if it has 0
39 // interpretations, an exception has already been thrown.
40 assert( finder.get_alternatives().size() == 1 );
41 CastExpr *newExpr = dynamic_cast< CastExpr* >( finder.get_alternatives().front().expr );
42 assert( newExpr );
43 env = finder.get_alternatives().front().env;
44 return newExpr->get_arg()->clone();
[51b73452]45 }
46
[d9a0e76]47 namespace {
48 void printAlts( const AltList &list, std::ostream &os, int indent = 0 ) {
49 for ( AltList::const_iterator i = list.begin(); i != list.end(); ++i ) {
50 i->print( os, indent );
51 os << std::endl;
52 }
53 }
54
55 void makeExprList( const AltList &in, std::list< Expression* > &out ) {
56 for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
57 out.push_back( i->expr->clone() );
58 }
59 }
60
61 Cost sumCost( const AltList &in ) {
62 Cost total;
63 for ( AltList::const_iterator i = in.begin(); i != in.end(); ++i ) {
64 total += i->cost;
65 }
66 return total;
67 }
68
69 struct PruneStruct {
70 bool isAmbiguous;
71 AltList::iterator candidate;
72 PruneStruct() {}
73 PruneStruct( AltList::iterator candidate ): isAmbiguous( false ), candidate( candidate ) {}
74 };
75
76 template< typename InputIterator, typename OutputIterator >
77 void pruneAlternatives( InputIterator begin, InputIterator end, OutputIterator out, const SymTab::Indexer &indexer ) {
78 // select the alternatives that have the minimum conversion cost for a particular set of result types
79 std::map< std::string, PruneStruct > selected;
80 for ( AltList::iterator candidate = begin; candidate != end; ++candidate ) {
81 PruneStruct current( candidate );
82 std::string mangleName;
83 for ( std::list< Type* >::const_iterator retType = candidate->expr->get_results().begin(); retType != candidate->expr->get_results().end(); ++retType ) {
84 Type *newType = (*retType)->clone();
85 candidate->env.apply( newType );
86 mangleName += SymTab::Mangler::mangle( newType );
87 delete newType;
88 }
89 std::map< std::string, PruneStruct >::iterator mapPlace = selected.find( mangleName );
90 if ( mapPlace != selected.end() ) {
91 if ( candidate->cost < mapPlace->second.candidate->cost ) {
92 PRINT(
93 std::cout << "cost " << candidate->cost << " beats " << mapPlace->second.candidate->cost << std::endl;
94 )
95 selected[ mangleName ] = current;
96 } else if ( candidate->cost == mapPlace->second.candidate->cost ) {
97 PRINT(
98 std::cout << "marking ambiguous" << std::endl;
99 )
100 mapPlace->second.isAmbiguous = true;
101 }
102 } else {
103 selected[ mangleName ] = current;
104 }
105 }
106
107 PRINT(
108 std::cout << "there are " << selected.size() << " alternatives before elimination" << std::endl;
109 )
110
111 // accept the alternatives that were unambiguous
112 for ( std::map< std::string, PruneStruct >::iterator target = selected.begin(); target != selected.end(); ++target ) {
113 if ( !target->second.isAmbiguous ) {
114 Alternative &alt = *target->second.candidate;
115 for ( std::list< Type* >::iterator result = alt.expr->get_results().begin(); result != alt.expr->get_results().end(); ++result ) {
116 alt.env.applyFree( *result );
117 }
118 *out++ = alt;
119 }
120 }
121
122 }
123
124 template< typename InputIterator, typename OutputIterator >
125 void findMinCost( InputIterator begin, InputIterator end, OutputIterator out ) {
126 AltList alternatives;
127
128 // select the alternatives that have the minimum parameter cost
129 Cost minCost = Cost::infinity;
130 for ( AltList::iterator i = begin; i != end; ++i ) {
131 if ( i->cost < minCost ) {
132 minCost = i->cost;
133 i->cost = i->cvtCost;
134 alternatives.clear();
135 alternatives.push_back( *i );
136 } else if ( i->cost == minCost ) {
137 i->cost = i->cvtCost;
138 alternatives.push_back( *i );
139 }
140 }
141 std::copy( alternatives.begin(), alternatives.end(), out );
142 }
143
144 template< typename InputIterator >
145 void simpleCombineEnvironments( InputIterator begin, InputIterator end, TypeEnvironment &result ) {
146 while ( begin != end ) {
147 result.simpleCombine( (*begin++).env );
148 }
149 }
150
151 void renameTypes( Expression *expr ) {
152 for ( std::list< Type* >::iterator i = expr->get_results().begin(); i != expr->get_results().end(); ++i ) {
153 (*i)->accept( global_renamer );
154 }
155 }
[51b73452]156 }
157
[d9a0e76]158 template< typename InputIterator, typename OutputIterator >
159 void AlternativeFinder::findSubExprs( InputIterator begin, InputIterator end, OutputIterator out ) {
160 while ( begin != end ) {
161 AlternativeFinder finder( indexer, env );
162 finder.findWithAdjustment( *begin );
163 // XXX either this
164 //Designators::fixDesignations( finder, (*begin++)->get_argName() );
165 // or XXX this
166 begin++;
167 PRINT(
168 std::cout << "findSubExprs" << std::endl;
169 printAlts( finder.alternatives, std::cout );
170 )
171 *out++ = finder;
172 }
[51b73452]173 }
174
[d9a0e76]175 AlternativeFinder::AlternativeFinder( const SymTab::Indexer &indexer, const TypeEnvironment &env )
176 : indexer( indexer ), env( env ) {
[51b73452]177 }
[d9a0e76]178
179 void AlternativeFinder::find( Expression *expr, bool adjust ) {
180 expr->accept( *this );
181 if ( alternatives.empty() ) {
182 throw SemanticError( "No reasonable alternatives for expression ", expr );
183 }
184 for ( AltList::iterator i = alternatives.begin(); i != alternatives.end(); ++i ) {
185 if ( adjust ) {
186 adjustExprTypeList( i->expr->get_results().begin(), i->expr->get_results().end(), i->env, indexer );
187 }
188 }
189 PRINT(
190 std::cout << "alternatives before prune:" << std::endl;
191 printAlts( alternatives, std::cout );
192 )
193 AltList::iterator oldBegin = alternatives.begin();
194 pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives ), indexer );
195 if ( alternatives.begin() == oldBegin ) {
196 std::ostrstream stream;
197 stream << "Can't choose between alternatives for expression ";
198 expr->print( stream );
199 stream << "Alternatives are:";
200 AltList winners;
201 findMinCost( alternatives.begin(), alternatives.end(), back_inserter( winners ) );
202 printAlts( winners, stream, 8 );
203 throw SemanticError( std::string( stream.str(), stream.pcount() ) );
204 }
205 alternatives.erase( oldBegin, alternatives.end() );
206 PRINT(
207 std::cout << "there are " << alternatives.size() << " alternatives after elimination" << std::endl;
208 )
[51b73452]209 }
210
[d9a0e76]211 void AlternativeFinder::findWithAdjustment( Expression *expr ) {
212 find( expr, true );
[51b73452]213 }
[d9a0e76]214
215 template< typename StructOrUnionType >
216 void AlternativeFinder::addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const std::string &name ) {
217 std::list< Declaration* > members;
218 aggInst->lookup( name, members );
219 for ( std::list< Declaration* >::const_iterator i = members.begin(); i != members.end(); ++i ) {
220 if ( DeclarationWithType *dwt = dynamic_cast< DeclarationWithType* >( *i ) ) {
221 alternatives.push_back( Alternative( new MemberExpr( dwt->clone(), expr->clone() ), env, newCost ) );
222 renameTypes( alternatives.back().expr );
223 } else {
224 assert( false );
225 }
226 }
[51b73452]227 }
[d9a0e76]228
229 void AlternativeFinder::visit( ApplicationExpr *applicationExpr ) {
230 alternatives.push_back( Alternative( applicationExpr->clone(), env, Cost::zero ) );
[51b73452]231 }
[d9a0e76]232
233 Cost computeConversionCost( Alternative &alt, const SymTab::Indexer &indexer ) {
234 ApplicationExpr *appExpr = dynamic_cast< ApplicationExpr* >( alt.expr );
235 assert( appExpr );
236 PointerType *pointer = dynamic_cast< PointerType* >( appExpr->get_function()->get_results().front() );
237 assert( pointer );
238 FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() );
239 assert( function );
240
241 Cost convCost( 0, 0, 0 );
242 std::list< DeclarationWithType* >& formals = function->get_parameters();
243 std::list< DeclarationWithType* >::iterator formal = formals.begin();
244 std::list< Expression* >& actuals = appExpr->get_args();
245 for ( std::list< Expression* >::iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) {
246 PRINT(
247 std::cout << "actual expression:" << std::endl;
248 (*actualExpr)->print( std::cout, 8 );
249 std::cout << "--- results are" << std::endl;
250 printAll( (*actualExpr)->get_results(), std::cout, 8 );
251 )
252 std::list< DeclarationWithType* >::iterator startFormal = formal;
253 Cost actualCost;
254 for ( std::list< Type* >::iterator actual = (*actualExpr)->get_results().begin(); actual != (*actualExpr)->get_results().end(); ++actual ) {
255 if ( formal == formals.end() ) {
256 if ( function->get_isVarArgs() ) {
257 convCost += Cost( 1, 0, 0 );
258 break;
259 } else {
260 return Cost::infinity;
261 }
262 }
263 PRINT(
264 std::cout << std::endl << "converting ";
265 (*actual)->print( std::cout, 8 );
266 std::cout << std::endl << " to ";
267 (*formal)->get_type()->print( std::cout, 8 );
268 )
269 Cost newCost = conversionCost( *actual, (*formal)->get_type(), indexer, alt.env );
270 PRINT(
271 std::cout << std::endl << "cost is" << newCost << std::endl;
272 )
273
274 if ( newCost == Cost::infinity ) {
275 return newCost;
276 }
277 convCost += newCost;
278 actualCost += newCost;
279
280 convCost += Cost( 0, polyCost( (*formal)->get_type(), alt.env, indexer ) + polyCost( *actual, alt.env, indexer ), 0 );
281
282 formal++;
283 }
284 if ( actualCost != Cost( 0, 0, 0 ) ) {
285 std::list< DeclarationWithType* >::iterator startFormalPlusOne = startFormal;
286 startFormalPlusOne++;
287 if ( formal == startFormalPlusOne ) {
288 // not a tuple type
289 Type *newType = (*startFormal)->get_type()->clone();
290 alt.env.apply( newType );
291 *actualExpr = new CastExpr( *actualExpr, newType );
292 } else {
293 TupleType *newType = new TupleType( Type::Qualifiers() );
294 for ( std::list< DeclarationWithType* >::iterator i = startFormal; i != formal; ++i ) {
295 newType->get_types().push_back( (*i)->get_type()->clone() );
296 }
297 alt.env.apply( newType );
298 *actualExpr = new CastExpr( *actualExpr, newType );
299 }
300 }
301
302 }
303 if ( formal != formals.end() ) {
304 return Cost::infinity;
305 }
306
307 for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) {
308 PRINT(
309 std::cout << std::endl << "converting ";
310 assert->second.actualType->print( std::cout, 8 );
311 std::cout << std::endl << " to ";
312 assert->second.formalType->print( std::cout, 8 );
313 )
314 Cost newCost = conversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env );
315 PRINT(
316 std::cout << std::endl << "cost of conversion is " << newCost << std::endl;
317 )
318 if ( newCost == Cost::infinity ) {
319 return newCost;
320 }
321 convCost += newCost;
322
323 convCost += Cost( 0, polyCost( assert->second.formalType, alt.env, indexer ) + polyCost( assert->second.actualType, alt.env, indexer ), 0 );
324 }
325
326 return convCost;
[51b73452]327 }
[d9a0e76]328
329 void makeUnifiableVars( Type *type, OpenVarSet &unifiableVars, AssertionSet &needAssertions ) {
330 for ( std::list< TypeDecl* >::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
331 unifiableVars[ (*tyvar)->get_name() ] = (*tyvar)->get_kind();
332 for ( std::list< DeclarationWithType* >::iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) {
333 needAssertions[ *assert ] = true;
334 }
335/// needAssertions.insert( needAssertions.end(), (*tyvar)->get_assertions().begin(), (*tyvar)->get_assertions().end() );
336 }
[51b73452]337 }
338
[d9a0e76]339 bool AlternativeFinder::instantiateFunction( std::list< DeclarationWithType* >& formals, /*const*/ AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave ) {
340 std::list< TypeEnvironment > toBeDone;
341 simpleCombineEnvironments( actuals.begin(), actuals.end(), resultEnv );
342 // make sure we don't widen any existing bindings
343 for ( TypeEnvironment::iterator i = resultEnv.begin(); i != resultEnv.end(); ++i ) {
344 i->allowWidening = false;
345 }
346 resultEnv.extractOpenVars( openVars );
347
348 /*
349 Tuples::NameMatcher matcher( formals );
350 try {
351 matcher.match( actuals );
352 } catch ( Tuples::NoMatch &e ) {
353 std::cerr << "Alternative doesn't match: " << e.message << std::endl;
354 }
355 */
356 std::list< DeclarationWithType* >::iterator formal = formals.begin();
357 for ( AltList::const_iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) {
358 for ( std::list< Type* >::iterator actual = actualExpr->expr->get_results().begin(); actual != actualExpr->expr->get_results().end(); ++actual ) {
359 if ( formal == formals.end() ) {
360 return isVarArgs;
361 }
362 PRINT(
363 std::cerr << "formal type is ";
364 (*formal)->get_type()->print( std::cerr );
365 std::cerr << std::endl << "actual type is ";
366 (*actual)->print( std::cerr );
367 std::cerr << std::endl;
368 )
369 if ( !unify( (*formal)->get_type(), *actual, resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
370 return false;
371 }
372 formal++;
373 }
374 }
375 // Handling of default values
376 while ( formal != formals.end() ) {
377 if ( ObjectDecl *od = dynamic_cast<ObjectDecl *>( *formal ) )
378 if ( SingleInit *si = dynamic_cast<SingleInit *>( od->get_init() ))
379 // so far, only constant expressions are accepted as default values
380 if ( ConstantExpr *cnstexpr = dynamic_cast<ConstantExpr *>( si->get_value()) )
381 if ( Constant *cnst = dynamic_cast<Constant *>( cnstexpr->get_constant() ) )
382 if ( unify( (*formal)->get_type(), cnst->get_type(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) {
383 // XXX Don't know if this is right
384 actuals.push_back( Alternative( cnstexpr->clone(), env, Cost::zero ) );
385 formal++;
386 if ( formal == formals.end()) break;
387 }
388 return false;
389 }
390 return true;
[51b73452]391 }
392
[d9a0e76]393 static const int recursionLimit = 10;
[51b73452]394
[d9a0e76]395 void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) {
396 for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) {
397 if ( i->second == true ) {
398 i->first->accept( indexer );
399 }
400 }
401 }
[51b73452]402
[d9a0e76]403 template< typename ForwardIterator, typename OutputIterator >
404 void inferRecursive( ForwardIterator begin, ForwardIterator end, const Alternative &newAlt, OpenVarSet &openVars, const SymTab::Indexer &decls, const AssertionSet &newNeed, int level, const SymTab::Indexer &indexer, OutputIterator out ) {
405 if ( begin == end ) {
406 if ( newNeed.empty() ) {
407 *out++ = newAlt;
408 return;
409 } else if ( level >= recursionLimit ) {
410 throw SemanticError( "Too many recursive assertions" );
411 } else {
412 AssertionSet newerNeed;
413 PRINT(
414 std::cerr << "recursing with new set:" << std::endl;
415 printAssertionSet( newNeed, std::cerr, 8 );
416 )
417 inferRecursive( newNeed.begin(), newNeed.end(), newAlt, openVars, decls, newerNeed, level+1, indexer, out );
418 return;
419 }
420 }
421
422 ForwardIterator cur = begin++;
423 if ( !cur->second ) {
424 inferRecursive( begin, end, newAlt, openVars, decls, newNeed, level, indexer, out );
425 }
426 DeclarationWithType *curDecl = cur->first;
427 PRINT(
428 std::cerr << "inferRecursive: assertion is ";
429 curDecl->print( std::cerr );
430 std::cerr << std::endl;
431 )
432 std::list< DeclarationWithType* > candidates;
433 decls.lookupId( curDecl->get_name(), candidates );
434/// if ( candidates.empty() ) { std::cout << "no candidates!" << std::endl; }
435 for ( std::list< DeclarationWithType* >::const_iterator candidate = candidates.begin(); candidate != candidates.end(); ++candidate ) {
436 PRINT(
437 std::cout << "inferRecursive: candidate is ";
438 (*candidate)->print( std::cout );
439 std::cout << std::endl;
440 )
441 AssertionSet newHave, newerNeed( newNeed );
442 TypeEnvironment newEnv( newAlt.env );
443 OpenVarSet newOpenVars( openVars );
444 Type *adjType = (*candidate)->get_type()->clone();
445 adjustExprType( adjType, newEnv, indexer );
446 adjType->accept( global_renamer );
447 PRINT(
448 std::cerr << "unifying ";
449 curDecl->get_type()->print( std::cerr );
450 std::cerr << " with ";
451 adjType->print( std::cerr );
452 std::cerr << std::endl;
453 )
454 if ( unify( curDecl->get_type(), adjType, newEnv, newerNeed, newHave, newOpenVars, indexer ) ) {
455 PRINT(
456 std::cerr << "success!" << std::endl;
457 )
458 SymTab::Indexer newDecls( decls );
459 addToIndexer( newHave, newDecls );
460 Alternative newerAlt( newAlt );
461 newerAlt.env = newEnv;
462 assert( (*candidate)->get_uniqueId() );
463 Expression *varExpr = new VariableExpr( static_cast< DeclarationWithType* >( Declaration::declFromId( (*candidate)->get_uniqueId() ) ) );
464 deleteAll( varExpr->get_results() );
465 varExpr->get_results().clear();
466 varExpr->get_results().push_front( adjType->clone() );
467 PRINT(
468 std::cout << "satisfying assertion " << curDecl->get_uniqueId() << " ";
469 curDecl->print( std::cout );
470 std::cout << " with declaration " << (*candidate)->get_uniqueId() << " ";
471 (*candidate)->print( std::cout );
472 std::cout << std::endl;
473 )
474 ApplicationExpr *appExpr = static_cast< ApplicationExpr* >( newerAlt.expr );
475 // XXX: this is a memory leak, but adjType can't be deleted because it might contain assertions
476 appExpr->get_inferParams()[ curDecl->get_uniqueId() ] = ParamEntry( (*candidate)->get_uniqueId(), adjType->clone(), curDecl->get_type()->clone(), varExpr );
477 inferRecursive( begin, end, newerAlt, newOpenVars, newDecls, newerNeed, level, indexer, out );
478 } else {
479 delete adjType;
480 }
481 }
[51b73452]482 }
[d9a0e76]483
484 template< typename OutputIterator >
485 void AlternativeFinder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) {
486// PRINT(
487// std::cout << "inferParameters: assertions needed are" << std::endl;
488// printAll( need, std::cout, 8 );
489// )
490 SymTab::Indexer decls( indexer );
491 PRINT(
492 std::cout << "============= original indexer" << std::endl;
493 indexer.print( std::cout );
494 std::cout << "============= new indexer" << std::endl;
495 decls.print( std::cout );
496 )
497 addToIndexer( have, decls );
498 AssertionSet newNeed;
499 inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, 0, indexer, out );
500// PRINT(
501// std::cout << "declaration 14 is ";
502// Declaration::declFromId
503// *out++ = newAlt;
504// )
[51b73452]505 }
[d9a0e76]506
507 template< typename OutputIterator >
508 void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, AltList &actualAlt, OutputIterator out ) {
509 OpenVarSet openVars;
510 AssertionSet resultNeed, resultHave;
511 TypeEnvironment resultEnv;
512 makeUnifiableVars( funcType, openVars, resultNeed );
513 if ( instantiateFunction( funcType->get_parameters(), actualAlt, funcType->get_isVarArgs(), openVars, resultEnv, resultNeed, resultHave ) ) {
514 ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );
515 Alternative newAlt( appExpr, resultEnv, sumCost( actualAlt ) );
516 makeExprList( actualAlt, appExpr->get_args() );
517 PRINT(
518 std::cout << "need assertions:" << std::endl;
519 printAssertionSet( resultNeed, std::cout, 8 );
520 )
521 inferParameters( resultNeed, resultHave, newAlt, openVars, out );
522 }
[51b73452]523 }
[d9a0e76]524
525 void AlternativeFinder::visit( UntypedExpr *untypedExpr ) {
526 bool doneInit = false;
527 AlternativeFinder funcOpFinder( indexer, env );
528
529 AlternativeFinder funcFinder( indexer, env ); {
530 NameExpr *fname;
531 if ( ( fname = dynamic_cast<NameExpr *>( untypedExpr->get_function()))
532 && ( fname->get_name() == std::string("LabAddress")) ) {
533 alternatives.push_back( Alternative( untypedExpr, env, Cost()) );
534 return;
535 }
536 }
537
538 funcFinder.findWithAdjustment( untypedExpr->get_function() );
539 std::list< AlternativeFinder > argAlternatives;
540 findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), back_inserter( argAlternatives ) );
541
542 std::list< AltList > possibilities;
543 combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) );
544
545 Tuples::TupleAssignSpotter tassign( this );
546 if ( tassign.isTupleAssignment( untypedExpr, possibilities ) ) {
547 // take care of possible tuple assignments, or discard expression
548 return;
549 } // else ...
550
551 AltList candidates;
552
553 for ( AltList::const_iterator func = funcFinder.alternatives.begin(); func != funcFinder.alternatives.end(); ++func ) {
554 PRINT(
555 std::cout << "working on alternative: " << std::endl;
556 func->print( std::cout, 8 );
557 )
558 // check if the type is pointer to function
559 PointerType *pointer;
560 if ( func->expr->get_results().size() == 1 && ( pointer = dynamic_cast< PointerType* >( func->expr->get_results().front() ) ) ) {
561 if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
562 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
563 // XXX
564 //Designators::check_alternative( function, *actualAlt );
565 makeFunctionAlternatives( *func, function, *actualAlt, std::back_inserter( candidates ) );
566 }
567 } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( pointer->get_base() ) ) {
568 EqvClass eqvClass;
569 if ( func->env.lookup( typeInst->get_name(), eqvClass ) && eqvClass.type ) {
570 if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.type ) ) {
571 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
572 makeFunctionAlternatives( *func, function, *actualAlt, std::back_inserter( candidates ) );
573 }
574 }
575 }
576 }
577 } else {
578 // seek a function operator that's compatible
579 if ( !doneInit ) {
580 doneInit = true;
581 NameExpr *opExpr = new NameExpr( "?()" );
582 try {
583 funcOpFinder.findWithAdjustment( opExpr );
584 } catch( SemanticError &e ) {
585 // it's ok if there aren't any defined function ops
586 }
587 PRINT(
588 std::cout << "known function ops:" << std::endl;
589 printAlts( funcOpFinder.alternatives, std::cout, 8 );
590 )
591 }
592
593 for ( AltList::const_iterator funcOp = funcOpFinder.alternatives.begin(); funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {
594 // check if the type is pointer to function
595 PointerType *pointer;
596 if ( funcOp->expr->get_results().size() == 1
597 && ( pointer = dynamic_cast< PointerType* >( funcOp->expr->get_results().front() ) ) ) {
598 if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) {
599 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) {
600 AltList currentAlt;
601 currentAlt.push_back( *func );
602 currentAlt.insert( currentAlt.end(), actualAlt->begin(), actualAlt->end() );
603 makeFunctionAlternatives( *funcOp, function, currentAlt, std::back_inserter( candidates ) );
604 }
605 }
606 }
607 }
608 }
609 }
610
611 for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) {
612 Cost cvtCost = computeConversionCost( *withFunc, indexer );
613
614 PRINT(
615 ApplicationExpr *appExpr = dynamic_cast< ApplicationExpr* >( withFunc->expr );
616 assert( appExpr );
617 PointerType *pointer = dynamic_cast< PointerType* >( appExpr->get_function()->get_results().front() );
618 assert( pointer );
619 FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() );
620 assert( function );
621 std::cout << "Case +++++++++++++" << std::endl;
622 std::cout << "formals are:" << std::endl;
623 printAll( function->get_parameters(), std::cout, 8 );
624 std::cout << "actuals are:" << std::endl;
625 printAll( appExpr->get_args(), std::cout, 8 );
626 std::cout << "bindings are:" << std::endl;
627 withFunc->env.print( std::cout, 8 );
628 std::cout << "cost of conversion is:" << cvtCost << std::endl;
629 )
630 if ( cvtCost != Cost::infinity ) {
631 withFunc->cvtCost = cvtCost;
632 alternatives.push_back( *withFunc );
633 }
634 }
635 candidates.clear();
636 candidates.splice( candidates.end(), alternatives );
637
638 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( alternatives ) );
[51b73452]639 }
[d9a0e76]640
641 bool isLvalue( Expression *expr ) {
642 for ( std::list< Type* >::const_iterator i = expr->get_results().begin(); i != expr->get_results().end(); ++i ) {
643 if ( !(*i)->get_isLvalue() ) return false;
644 }
645 return true;
[51b73452]646 }
[d9a0e76]647
648 void AlternativeFinder::visit( AddressExpr *addressExpr ) {
649 AlternativeFinder finder( indexer, env );
650 finder.find( addressExpr->get_arg() );
651 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
652 if ( isLvalue( i->expr ) ) {
653 alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) );
654 }
655 }
[51b73452]656 }
[d9a0e76]657
658 void AlternativeFinder::visit( CastExpr *castExpr ) {
659 for ( std::list< Type* >::iterator i = castExpr->get_results().begin(); i != castExpr->get_results().end(); ++i ) {
660 SymTab::validateType( *i, &indexer );
661 adjustExprType( *i, env, indexer );
662 }
663
664 AlternativeFinder finder( indexer, env );
665 finder.findWithAdjustment( castExpr->get_arg() );
666
667 AltList candidates;
668 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) {
669 AssertionSet needAssertions, haveAssertions;
670 OpenVarSet openVars;
671
672 // It's possible that a cast can throw away some values in a multiply-valued expression. (An example is a
673 // cast-to-void, which casts from one value to zero.) Figure out the prefix of the subexpression results
674 // that are cast directly. The candidate is invalid if it has fewer results than there are types to cast
675 // to.
676 int discardedValues = (*i).expr->get_results().size() - castExpr->get_results().size();
677 if ( discardedValues < 0 ) continue;
678 std::list< Type* >::iterator candidate_end = (*i).expr->get_results().begin();
679 std::advance( candidate_end, castExpr->get_results().size() );
680 if ( !unifyList( (*i).expr->get_results().begin(), candidate_end,
681 castExpr->get_results().begin(), castExpr->get_results().end(), i->env, needAssertions, haveAssertions, openVars, indexer ) ) continue;
682 Cost thisCost = castCostList( (*i).expr->get_results().begin(), candidate_end,
683 castExpr->get_results().begin(), castExpr->get_results().end(), indexer, i->env );
684 if ( thisCost != Cost::infinity ) {
685 // count one safe conversion for each value that is thrown away
686 thisCost += Cost( 0, 0, discardedValues );
687 CastExpr *newExpr = castExpr->clone();
688 newExpr->set_arg( i->expr->clone() );
689 candidates.push_back( Alternative( newExpr, i->env, i->cost, thisCost ) );
690 }
691 }
692
693 // findMinCost selects the alternatives with the lowest "cost" members, but has the side effect of copying the
694 // cvtCost member to the cost member (since the old cost is now irrelevant). Thus, calling findMinCost twice
695 // selects first based on argument cost, then on conversion cost.
696 AltList minArgCost;
697 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( minArgCost ) );
698 findMinCost( minArgCost.begin(), minArgCost.end(), std::back_inserter( alternatives ) );
[51b73452]699 }
[d9a0e76]700
701 void AlternativeFinder::visit( UntypedMemberExpr *memberExpr ) {
702 AlternativeFinder funcFinder( indexer, env );
703 funcFinder.findWithAdjustment( memberExpr->get_aggregate() );
704
705 for ( AltList::const_iterator agg = funcFinder.alternatives.begin(); agg != funcFinder.alternatives.end(); ++agg ) {
706 if ( agg->expr->get_results().size() == 1 ) {
707 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( agg->expr->get_results().front() ) ) {
708 addAggMembers( structInst, agg->expr, agg->cost, memberExpr->get_member() );
709 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( agg->expr->get_results().front() ) ) {
710 addAggMembers( unionInst, agg->expr, agg->cost, memberExpr->get_member() );
711 }
712 }
713 }
[51b73452]714 }
[d9a0e76]715
716 void AlternativeFinder::visit( MemberExpr *memberExpr ) {
717 alternatives.push_back( Alternative( memberExpr->clone(), env, Cost::zero ) );
[51b73452]718 }
[d9a0e76]719
720 void AlternativeFinder::visit( NameExpr *nameExpr ) {
721 std::list< DeclarationWithType* > declList;
722 indexer.lookupId( nameExpr->get_name(), declList );
723 PRINT(
724 std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl;
725 )
726 for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) {
727 VariableExpr newExpr( *i, nameExpr->get_argName() );
728 alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) );
729 PRINT(
730 std::cerr << "decl is ";
731 (*i)->print( std::cerr );
732 std::cerr << std::endl;
733 std::cerr << "newExpr is ";
734 newExpr.print( std::cerr );
735 std::cerr << std::endl;
736 )
737 renameTypes( alternatives.back().expr );
738 if ( StructInstType *structInst = dynamic_cast< StructInstType* >( (*i)->get_type() ) ) {
739 addAggMembers( structInst, &newExpr, Cost( 0, 0, 1 ), "" );
740 } else if ( UnionInstType *unionInst = dynamic_cast< UnionInstType* >( (*i)->get_type() ) ) {
741 addAggMembers( unionInst, &newExpr, Cost( 0, 0, 1 ), "" );
742 }
743 }
[51b73452]744 }
[d9a0e76]745
746 void AlternativeFinder::visit( VariableExpr *variableExpr ) {
747 alternatives.push_back( Alternative( variableExpr->clone(), env, Cost::zero ) );
[51b73452]748 }
[d9a0e76]749
750 void AlternativeFinder::visit( ConstantExpr *constantExpr ) {
751 alternatives.push_back( Alternative( constantExpr->clone(), env, Cost::zero ) );
[51b73452]752 }
[d9a0e76]753
754 void AlternativeFinder::visit( SizeofExpr *sizeofExpr ) {
755 if ( sizeofExpr->get_isType() ) {
756 alternatives.push_back( Alternative( sizeofExpr->clone(), env, Cost::zero ) );
757 } else {
758 AlternativeFinder finder( indexer, env );
759 finder.find( sizeofExpr->get_expr() );
760 if ( finder.alternatives.size() != 1 ) {
761 throw SemanticError( "Ambiguous expression in sizeof operand: ", sizeofExpr->get_expr() );
762 }
763 Alternative &choice = finder.alternatives.front();
764 alternatives.push_back( Alternative( new SizeofExpr( choice.expr->clone() ), choice.env, Cost::zero ) );
765 }
[51b73452]766 }
[d9a0e76]767
768 void AlternativeFinder::resolveAttr( DeclarationWithType *funcDecl, FunctionType *function, Type *argType, const TypeEnvironment &env ) {
769 // assume no polymorphism
770 // assume no implicit conversions
771 assert( function->get_parameters().size() == 1 );
772 PRINT(
773 std::cout << "resolvAttr: funcDecl is ";
774 funcDecl->print( std::cout );
775 std::cout << " argType is ";
776 argType->print( std::cout );
777 std::cout << std::endl;
778 )
779 if ( typesCompatibleIgnoreQualifiers( argType, function->get_parameters().front()->get_type(), indexer, env ) ) {
780 alternatives.push_back( Alternative( new AttrExpr( new VariableExpr( funcDecl ), argType->clone() ), env, Cost::zero ) );
781 for ( std::list< DeclarationWithType* >::iterator i = function->get_returnVals().begin(); i != function->get_returnVals().end(); ++i ) {
782 alternatives.back().expr->get_results().push_back( (*i)->get_type()->clone() );
783 }
784 }
[51b73452]785 }
[d9a0e76]786
787 void AlternativeFinder::visit( AttrExpr *attrExpr ) {
788 // assume no 'pointer-to-attribute'
789 NameExpr *nameExpr = dynamic_cast< NameExpr* >( attrExpr->get_attr() );
790 assert( nameExpr );
791 std::list< DeclarationWithType* > attrList;
792 indexer.lookupId( nameExpr->get_name(), attrList );
793 if ( attrExpr->get_isType() || attrExpr->get_expr() ) {
794 for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
795 // check if the type is function
796 if ( FunctionType *function = dynamic_cast< FunctionType* >( (*i)->get_type() ) ) {
797 // assume exactly one parameter
798 if ( function->get_parameters().size() == 1 ) {
799 if ( attrExpr->get_isType() ) {
800 resolveAttr( *i, function, attrExpr->get_type(), env );
801 } else {
802 AlternativeFinder finder( indexer, env );
803 finder.find( attrExpr->get_expr() );
804 for ( AltList::iterator choice = finder.alternatives.begin(); choice != finder.alternatives.end(); ++choice ) {
805 if ( choice->expr->get_results().size() == 1 ) {
806 resolveAttr(*i, function, choice->expr->get_results().front(), choice->env );
807 }
808 }
809 }
810 }
811 }
812 }
813 } else {
814 for ( std::list< DeclarationWithType* >::iterator i = attrList.begin(); i != attrList.end(); ++i ) {
815 VariableExpr newExpr( *i );
816 alternatives.push_back( Alternative( newExpr.clone(), env, Cost() ) );
817 renameTypes( alternatives.back().expr );
818 }
819 }
[51b73452]820 }
[d9a0e76]821
822 void AlternativeFinder::visit( LogicalExpr *logicalExpr ) {
823 AlternativeFinder firstFinder( indexer, env );
824 firstFinder.findWithAdjustment( logicalExpr->get_arg1() );
825 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
826 AlternativeFinder secondFinder( indexer, first->env );
827 secondFinder.findWithAdjustment( logicalExpr->get_arg2() );
828 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
829 LogicalExpr *newExpr = new LogicalExpr( first->expr->clone(), second->expr->clone(), logicalExpr->get_isAnd() );
830 alternatives.push_back( Alternative( newExpr, second->env, first->cost + second->cost ) );
831 }
832 }
[51b73452]833 }
[d9a0e76]834
835 void AlternativeFinder::visit( ConditionalExpr *conditionalExpr ) {
836 AlternativeFinder firstFinder( indexer, env );
837 firstFinder.findWithAdjustment( conditionalExpr->get_arg1() );
838 for ( AltList::const_iterator first = firstFinder.alternatives.begin(); first != firstFinder.alternatives.end(); ++first ) {
839 AlternativeFinder secondFinder( indexer, first->env );
840 secondFinder.findWithAdjustment( conditionalExpr->get_arg2() );
841 for ( AltList::const_iterator second = secondFinder.alternatives.begin(); second != secondFinder.alternatives.end(); ++second ) {
842 AlternativeFinder thirdFinder( indexer, second->env );
843 thirdFinder.findWithAdjustment( conditionalExpr->get_arg3() );
844 for ( AltList::const_iterator third = thirdFinder.alternatives.begin(); third != thirdFinder.alternatives.end(); ++third ) {
845 OpenVarSet openVars;
846 AssertionSet needAssertions, haveAssertions;
847 Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost );
848 std::list< Type* > commonTypes;
849 if ( unifyList( second->expr->get_results().begin(), second->expr->get_results().end(), third->expr->get_results().begin(), third->expr->get_results().end(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonTypes ) ) {
850 ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() );
851 std::list< Type* >::const_iterator original = second->expr->get_results().begin();
852 std::list< Type* >::const_iterator commonType = commonTypes.begin();
853 for ( ; original != second->expr->get_results().end() && commonType != commonTypes.end(); ++original, ++commonType ) {
854 if ( *commonType ) {
855 newExpr->get_results().push_back( *commonType );
856 } else {
857 newExpr->get_results().push_back( (*original)->clone() );
858 }
859 }
860 newAlt.expr = newExpr;
861 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( alternatives ) );
862 }
863 }
864 }
865 }
[51b73452]866 }
[d9a0e76]867
868 void AlternativeFinder::visit( CommaExpr *commaExpr ) {
869 TypeEnvironment newEnv( env );
870 Expression *newFirstArg = resolveInVoidContext( commaExpr->get_arg1(), indexer, newEnv );
871 AlternativeFinder secondFinder( indexer, newEnv );
872 secondFinder.findWithAdjustment( commaExpr->get_arg2() );
873 for ( AltList::const_iterator alt = secondFinder.alternatives.begin(); alt != secondFinder.alternatives.end(); ++alt ) {
874 alternatives.push_back( Alternative( new CommaExpr( newFirstArg->clone(), alt->expr->clone() ), alt->env, alt->cost ) );
875 }
876 delete newFirstArg;
[51b73452]877 }
878
[d9a0e76]879 void AlternativeFinder::visit( TupleExpr *tupleExpr ) {
880 std::list< AlternativeFinder > subExprAlternatives;
881 findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) );
882 std::list< AltList > possibilities;
883 combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) );
884 for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) {
885 TupleExpr *newExpr = new TupleExpr;
886 makeExprList( *i, newExpr->get_exprs() );
887 for ( std::list< Expression* >::const_iterator resultExpr = newExpr->get_exprs().begin(); resultExpr != newExpr->get_exprs().end(); ++resultExpr ) {
888 for ( std::list< Type* >::const_iterator resultType = (*resultExpr)->get_results().begin(); resultType != (*resultExpr)->get_results().end(); ++resultType ) {
889 newExpr->get_results().push_back( (*resultType)->clone() );
890 }
891 }
[51b73452]892
[d9a0e76]893 TypeEnvironment compositeEnv;
894 simpleCombineEnvironments( i->begin(), i->end(), compositeEnv );
895 alternatives.push_back( Alternative( newExpr, compositeEnv, sumCost( *i ) ) );
896 }
897 }
[51b73452]898} // namespace ResolvExpr
Note: See TracBrowser for help on using the repository browser.