Changeset 21300d7 for src/ResolvExpr/CandidateFinder.cpp
- Timestamp:
- Jun 12, 2019, 4:06:37 PM (5 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 462a7c7, d60780c
- Parents:
- aaeacf4 (diff), 6625727 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)
links above to see all the changes relative to each parent. - File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/CandidateFinder.cpp
raaeacf4 r21300d7 16 16 #include "CandidateFinder.hpp" 17 17 18 #include <deque> 19 #include <iterator> // for back_inserter 20 #include <sstream> 21 #include <string> 22 #include <unordered_map> 23 #include <vector> 24 25 #include "Candidate.hpp" 26 #include "CompilationState.h" 27 #include "Cost.h" 28 #include "ExplodedArg.hpp" 29 #include "Resolver.h" 30 #include "SatisfyAssertions.hpp" 31 #include "typeops.h" // for adjustExprType 32 #include "Unify.h" 18 33 #include "AST/Expr.hpp" 34 #include "AST/Node.hpp" 35 #include "AST/Pass.hpp" 36 #include "AST/Print.hpp" 37 #include "AST/SymbolTable.hpp" 38 #include "AST/Type.hpp" 39 #include "SymTab/Mangler.h" 40 #include "Tuples/Tuples.h" // for handleTupleAssignment 41 42 #define PRINT( text ) if ( resolvep ) { text } 19 43 20 44 namespace ResolvExpr { 21 45 46 namespace { 47 48 /// First index is which argument, second is which alternative, third is which exploded element 49 using ExplodedArgs_new = std::deque< std::vector< ExplodedArg > >; 50 51 /// Returns a list of alternatives with the minimum cost in the given list 52 CandidateList findMinCost( const CandidateList & candidates ) { 53 CandidateList out; 54 Cost minCost = Cost::infinity; 55 for ( const CandidateRef & r : candidates ) { 56 if ( r->cost < minCost ) { 57 minCost = r->cost; 58 out.clear(); 59 out.emplace_back( r ); 60 } else if ( r->cost == minCost ) { 61 out.emplace_back( r ); 62 } 63 } 64 return out; 65 } 66 67 /// Computes conversion cost for a given candidate 68 Cost computeApplicationConversionCost( 69 const CandidateRef & cand, const ast::SymbolTable & symtab 70 ) { 71 #warning unimplemented 72 (void)cand; (void)symtab; 73 assert(false); 74 return Cost::infinity; 75 } 76 77 /// Actually visits expressions to find their candidate interpretations 78 struct Finder final : public ast::WithShortCircuiting { 79 CandidateFinder & selfFinder; 80 const ast::SymbolTable & symtab; 81 CandidateList & candidates; 82 const ast::TypeEnvironment & tenv; 83 ast::ptr< ast::Type > & targetType; 84 85 Finder( CandidateFinder & f ) 86 : selfFinder( f ), symtab( f.symtab ), candidates( f.candidates ), tenv( f.env ), 87 targetType( f.targetType ) {} 88 89 void previsit( const ast::Node * ) { visit_children = false; } 90 91 /// Convenience to add candidate to list 92 template<typename... Args> 93 void addCandidate( Args &&... args ) { 94 candidates.emplace_back( new Candidate{ std::forward<Args>( args )... } ); 95 } 96 97 void postvisit( const ast::ApplicationExpr * applicationExpr ) { 98 addCandidate( applicationExpr, tenv ); 99 } 100 101 /// Builds a list of candidates for a function, storing them in out 102 void makeFunctionCandidates( 103 const CandidateRef & func, const ast::FunctionType * funcType, 104 const ExplodedArgs_new & args, CandidateList & out 105 ) { 106 #warning unimplemented 107 (void)func; (void)funcType; (void)args; (void)out; 108 assert(false); 109 } 110 111 /// Adds implicit struct-conversions to the alternative list 112 void addAnonConversions( const CandidateRef & cand ) { 113 #warning unimplemented 114 (void)cand; 115 assert(false); 116 } 117 118 void postvisit( const ast::UntypedExpr * untypedExpr ) { 119 CandidateFinder funcFinder{ symtab, tenv }; 120 funcFinder.find( untypedExpr->func, ResolvMode::withAdjustment() ); 121 // short-circuit if no candidates 122 if ( funcFinder.candidates.empty() ) return; 123 124 std::vector< CandidateFinder > argCandidates = 125 selfFinder.findSubExprs( untypedExpr->args ); 126 127 // take care of possible tuple assignments 128 // if not tuple assignment, handled as normal function call 129 Tuples::handleTupleAssignment( selfFinder, untypedExpr, argCandidates ); 130 131 // find function operators 132 ast::ptr< ast::Expr > opExpr = new ast::NameExpr{ untypedExpr->location, "?()" }; 133 CandidateFinder opFinder{ symtab, tenv }; 134 // okay if there aren't any function operations 135 opFinder.find( opExpr, ResolvMode::withoutFailFast() ); 136 PRINT( 137 std::cerr << "known function ops:" << std::endl; 138 print( std::cerr, opFinder.candidates, 1 ); 139 ) 140 141 // pre-explode arguments 142 ExplodedArgs_new argExpansions; 143 for ( const CandidateFinder & args : argCandidates ) { 144 argExpansions.emplace_back(); 145 auto & argE = argExpansions.back(); 146 for ( const CandidateRef & arg : args ) { argE.emplace_back( *arg, symtab ); } 147 } 148 149 // Find function matches 150 CandidateList found; 151 SemanticErrorException errors; 152 for ( CandidateRef & func : funcFinder ) { 153 try { 154 PRINT( 155 std::cerr << "working on alternative:" << std::endl; 156 print( std::cerr, *func, 2 ); 157 ) 158 159 // check if the type is a pointer to function 160 const ast::Type * funcResult = func->expr->result->stripReferences(); 161 if ( auto pointer = dynamic_cast< const ast::PointerType * >( funcResult ) ) { 162 if ( auto function = pointer->base.as< ast::FunctionType >() ) { 163 CandidateRef newFunc{ new Candidate{ *func } }; 164 newFunc->expr = 165 referenceToRvalueConversion( newFunc->expr, newFunc->cost ); 166 makeFunctionCandidates( newFunc, function, argExpansions, found ); 167 } 168 } else if ( 169 auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult ) 170 ) { 171 if ( const ast::EqvClass * clz = func->env.lookup( inst->name ) ) { 172 if ( auto function = clz->bound.as< ast::FunctionType >() ) { 173 CandidateRef newFunc{ new Candidate{ *func } }; 174 newFunc->expr = 175 referenceToRvalueConversion( newFunc->expr, newFunc->cost ); 176 makeFunctionCandidates( newFunc, function, argExpansions, found ); 177 } 178 } 179 } 180 } catch ( SemanticErrorException & e ) { errors.append( e ); } 181 } 182 183 // Find matches on function operators `?()` 184 if ( ! opFinder.candidates.empty() ) { 185 // add exploded function alternatives to front of argument list 186 std::vector< ExplodedArg > funcE; 187 funcE.reserve( funcFinder.candidates.size() ); 188 for ( const CandidateRef & func : funcFinder ) { 189 funcE.emplace_back( *func, symtab ); 190 } 191 argExpansions.emplace_front( std::move( funcE ) ); 192 193 for ( const CandidateRef & op : opFinder ) { 194 try { 195 // check if type is pointer-to-function 196 const ast::Type * opResult = op->expr->result->stripReferences(); 197 if ( auto pointer = dynamic_cast< const ast::PointerType * >( opResult ) ) { 198 if ( auto function = pointer->base.as< ast::FunctionType >() ) { 199 CandidateRef newOp{ new Candidate{ *op} }; 200 newOp->expr = 201 referenceToRvalueConversion( newOp->expr, newOp->cost ); 202 makeFunctionCandidates( newOp, function, argExpansions, found ); 203 } 204 } 205 } catch ( SemanticErrorException & e ) { errors.append( e ); } 206 } 207 } 208 209 // Implement SFINAE; resolution errors are only errors if there aren't any non-error 210 // candidates 211 if ( found.empty() && ! errors.isEmpty() ) { throw errors; } 212 213 // Compute conversion costs 214 for ( CandidateRef & withFunc : found ) { 215 Cost cvtCost = computeApplicationConversionCost( withFunc, symtab ); 216 217 PRINT( 218 auto appExpr = withFunc->expr.strict_as< ast::ApplicationExpr >(); 219 auto pointer = appExpr->func->result.strict_as< ast::PointerType >(); 220 auto function = pointer->base.strict_as< ast::FunctionType >(); 221 222 std::cerr << "Case +++++++++++++ " << appExpr->func << std::endl; 223 std::cerr << "parameters are:" << std::endl; 224 ast::printAll( std::cerr, function->params, 2 ); 225 std::cerr << "arguments are:" << std::endl; 226 ast::printAll( std::cerr, appExpr->args, 2 ); 227 std::cerr << "bindings are:" << std::endl; 228 ast::print( std::cerr, withFunc->env, 2 ); 229 std::cerr << "cost is: " << withFunc->cost << std::endl; 230 std::cerr << "cost of conversion is:" << cvtCost << std::endl; 231 ) 232 233 if ( cvtCost != Cost::infinity ) { 234 withFunc->cvtCost = cvtCost; 235 candidates.emplace_back( std::move( withFunc ) ); 236 } 237 } 238 found = std::move( candidates ); 239 240 // use a new list so that candidates are not examined by addAnonConversions twice 241 CandidateList winners = findMinCost( found ); 242 promoteCvtCost( winners ); 243 244 // function may return a struct/union value, in which case we need to add candidates 245 // for implicit conversions to each of the anonymous members, which must happen after 246 // `findMinCost`, since anon conversions are never the cheapest 247 for ( const CandidateRef & c : winners ) { 248 addAnonConversions( c ); 249 } 250 spliceBegin( candidates, winners ); 251 252 if ( candidates.empty() && targetType && ! targetType->isVoid() ) { 253 // If resolution is unsuccessful with a target type, try again without, since it 254 // will sometimes succeed when it wouldn't with a target type binding. 255 // For example: 256 // forall( otype T ) T & ?[]( T *, ptrdiff_t ); 257 // const char * x = "hello world"; 258 // unsigned char ch = x[0]; 259 // Fails with simple return type binding (xxx -- check this!) as follows: 260 // * T is bound to unsigned char 261 // * (x: const char *) is unified with unsigned char *, which fails 262 // xxx -- fix this better 263 targetType = nullptr; 264 postvisit( untypedExpr ); 265 } 266 } 267 268 /// true if expression is an lvalue 269 static bool isLvalue( const ast::Expr * x ) { 270 return x->result && ( x->result->is_lvalue() || x->result.as< ast::ReferenceType >() ); 271 } 272 273 void postvisit( const ast::AddressExpr * addressExpr ) { 274 CandidateFinder finder{ symtab, tenv }; 275 finder.find( addressExpr->arg ); 276 for ( CandidateRef & r : finder.candidates ) { 277 if ( ! isLvalue( r->expr ) ) continue; 278 addCandidate( *r, new ast::AddressExpr{ addressExpr->location, r->expr } ); 279 } 280 } 281 282 void postvisit( const ast::LabelAddressExpr * labelExpr ) { 283 addCandidate( labelExpr, tenv ); 284 } 285 286 void postvisit( const ast::CastExpr * castExpr ) { 287 #warning unimplemented 288 (void)castExpr; 289 assert(false); 290 } 291 292 void postvisit( const ast::VirtualCastExpr * castExpr ) { 293 assertf( castExpr->result, "Implicit virtual cast targets not yet supported." ); 294 CandidateFinder finder{ symtab, tenv }; 295 // don't prune here, all alternatives guaranteed to have same type 296 finder.find( castExpr->arg, ResolvMode::withoutPrune() ); 297 for ( CandidateRef & r : finder.candidates ) { 298 addCandidate( 299 *r, new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } ); 300 } 301 } 302 303 void postvisit( const ast::UntypedMemberExpr * memberExpr ) { 304 #warning unimplemented 305 (void)memberExpr; 306 assert(false); 307 } 308 309 void postvisit( const ast::MemberExpr * memberExpr ) { 310 addCandidate( memberExpr, tenv ); 311 } 312 313 void postvisit( const ast::NameExpr * variableExpr ) { 314 #warning unimplemented 315 (void)variableExpr; 316 assert(false); 317 } 318 319 void postvisit( const ast::VariableExpr * variableExpr ) { 320 // not sufficient to just pass `variableExpr` here, type might have changed since 321 // creation 322 addCandidate( 323 new ast::VariableExpr{ variableExpr->location, variableExpr->var }, tenv ); 324 } 325 326 void postvisit( const ast::ConstantExpr * constantExpr ) { 327 addCandidate( constantExpr, tenv ); 328 } 329 330 void postvisit( const ast::SizeofExpr * sizeofExpr ) { 331 #warning unimplemented 332 (void)sizeofExpr; 333 assert(false); 334 } 335 336 void postvisit( const ast::AlignofExpr * alignofExpr ) { 337 #warning unimplemented 338 (void)alignofExpr; 339 assert(false); 340 } 341 342 void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) { 343 #warning unimplemented 344 (void)offsetofExpr; 345 assert(false); 346 } 347 348 void postvisit( const ast::OffsetofExpr * offsetofExpr ) { 349 addCandidate( offsetofExpr, tenv ); 350 } 351 352 void postvisit( const ast::OffsetPackExpr * offsetPackExpr ) { 353 addCandidate( offsetPackExpr, tenv ); 354 } 355 356 void postvisit( const ast::LogicalExpr * logicalExpr ) { 357 CandidateFinder finder1{ symtab, tenv }; 358 finder1.find( logicalExpr->arg1, ResolvMode::withAdjustment() ); 359 if ( finder1.candidates.empty() ) return; 360 361 CandidateFinder finder2{ symtab, tenv }; 362 finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() ); 363 if ( finder2.candidates.empty() ) return; 364 365 for ( const CandidateRef & r1 : finder1.candidates ) { 366 for ( const CandidateRef & r2 : finder2.candidates ) { 367 ast::TypeEnvironment env{ r1->env }; 368 env.simpleCombine( r2->env ); 369 ast::OpenVarSet open{ r1->open }; 370 mergeOpenVars( open, r2->open ); 371 ast::AssertionSet need; 372 mergeAssertionSet( need, r1->need ); 373 mergeAssertionSet( need, r2->need ); 374 375 addCandidate( 376 new ast::LogicalExpr{ 377 logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd }, 378 std::move( env ), std::move( open ), std::move( need ), 379 r1->cost + r2->cost ); 380 } 381 } 382 } 383 384 void postvisit( const ast::ConditionalExpr * conditionalExpr ) { 385 // candidates for condition 386 CandidateFinder finder1{ symtab, tenv }; 387 finder1.find( conditionalExpr->arg1, ResolvMode::withAdjustment() ); 388 if ( finder1.candidates.empty() ) return; 389 390 // candidates for true result 391 CandidateFinder finder2{ symtab, tenv }; 392 finder2.find( conditionalExpr->arg2, ResolvMode::withAdjustment() ); 393 if ( finder2.candidates.empty() ) return; 394 395 // candidates for false result 396 CandidateFinder finder3{ symtab, tenv }; 397 finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() ); 398 if ( finder3.candidates.empty() ) return; 399 400 for ( const CandidateRef & r1 : finder1.candidates ) { 401 for ( const CandidateRef & r2 : finder2.candidates ) { 402 for ( const CandidateRef & r3 : finder3.candidates ) { 403 ast::TypeEnvironment env{ r1->env }; 404 env.simpleCombine( r2->env ); 405 env.simpleCombine( r3->env ); 406 ast::OpenVarSet open{ r1->open }; 407 mergeOpenVars( open, r2->open ); 408 mergeOpenVars( open, r3->open ); 409 ast::AssertionSet need; 410 mergeAssertionSet( need, r1->need ); 411 mergeAssertionSet( need, r2->need ); 412 mergeAssertionSet( need, r3->need ); 413 ast::AssertionSet have; 414 415 // unify true and false results, then infer parameters to produce new 416 // candidates 417 ast::ptr< ast::Type > common; 418 if ( 419 unify( 420 r2->expr->result, r3->expr->result, env, need, have, open, symtab, 421 common ) 422 ) { 423 #warning unimplemented 424 assert(false); 425 } 426 } 427 } 428 } 429 } 430 431 void postvisit( const ast::CommaExpr * commaExpr ) { 432 ast::TypeEnvironment env{ tenv }; 433 ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, symtab, env ); 434 435 CandidateFinder finder2{ symtab, env }; 436 finder2.find( commaExpr->arg2, ResolvMode::withAdjustment() ); 437 438 for ( const CandidateRef & r2 : finder2.candidates ) { 439 addCandidate( *r2, new ast::CommaExpr{ commaExpr->location, arg1, r2->expr } ); 440 } 441 } 442 443 void postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr ) { 444 addCandidate( ctorExpr, tenv ); 445 } 446 447 void postvisit( const ast::ConstructorExpr * ctorExpr ) { 448 CandidateFinder finder{ symtab, tenv }; 449 finder.find( ctorExpr->callExpr, ResolvMode::withoutPrune() ); 450 for ( CandidateRef & r : finder.candidates ) { 451 addCandidate( *r, new ast::ConstructorExpr{ ctorExpr->location, r->expr } ); 452 } 453 } 454 455 void postvisit( const ast::RangeExpr * rangeExpr ) { 456 // resolve low and high, accept candidates where low and high types unify 457 CandidateFinder finder1{ symtab, tenv }; 458 finder1.find( rangeExpr->low, ResolvMode::withAdjustment() ); 459 if ( finder1.candidates.empty() ) return; 460 461 CandidateFinder finder2{ symtab, tenv }; 462 finder2.find( rangeExpr->high, ResolvMode::withAdjustment() ); 463 if ( finder2.candidates.empty() ) return; 464 465 for ( const CandidateRef & r1 : finder1.candidates ) { 466 for ( const CandidateRef & r2 : finder2.candidates ) { 467 ast::TypeEnvironment env{ r1->env }; 468 env.simpleCombine( r2->env ); 469 ast::OpenVarSet open{ r1->open }; 470 mergeOpenVars( open, r2->open ); 471 ast::AssertionSet need; 472 mergeAssertionSet( need, r1->need ); 473 mergeAssertionSet( need, r2->need ); 474 ast::AssertionSet have; 475 476 ast::ptr< ast::Type > common; 477 if ( 478 unify( 479 r1->expr->result, r2->expr->result, env, need, have, open, symtab, 480 common ) 481 ) { 482 ast::RangeExpr * newExpr = 483 new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr }; 484 newExpr->result = common ? common : r1->expr->result; 485 486 #warning unimplemented 487 assert(false); 488 } 489 } 490 } 491 } 492 493 void postvisit( const ast::UntypedTupleExpr * tupleExpr ) { 494 std::vector< CandidateFinder > subCandidates = 495 selfFinder.findSubExprs( tupleExpr->exprs ); 496 std::vector< CandidateList > possibilities; 497 combos( subCandidates.begin(), subCandidates.end(), back_inserter( possibilities ) ); 498 499 for ( const CandidateList & subs : possibilities ) { 500 std::vector< ast::ptr< ast::Expr > > exprs; 501 exprs.reserve( subs.size() ); 502 for ( const CandidateRef & sub : subs ) { exprs.emplace_back( sub->expr ); } 503 504 ast::TypeEnvironment env; 505 ast::OpenVarSet open; 506 ast::AssertionSet need; 507 for ( const CandidateRef & sub : subs ) { 508 env.simpleCombine( sub->env ); 509 mergeOpenVars( open, sub->open ); 510 mergeAssertionSet( need, sub->need ); 511 } 512 513 addCandidate( 514 new ast::TupleExpr{ tupleExpr->location, std::move( exprs ) }, 515 std::move( env ), std::move( open ), std::move( need ), sumCost( subs ) ); 516 } 517 } 518 519 void postvisit( const ast::TupleExpr * tupleExpr ) { 520 addCandidate( tupleExpr, tenv ); 521 } 522 523 void postvisit( const ast::TupleIndexExpr * tupleExpr ) { 524 addCandidate( tupleExpr, tenv ); 525 } 526 527 void postvisit( const ast::TupleAssignExpr * tupleExpr ) { 528 addCandidate( tupleExpr, tenv ); 529 } 530 531 void postvisit( const ast::UniqueExpr * unqExpr ) { 532 CandidateFinder finder{ symtab, tenv }; 533 finder.find( unqExpr->expr, ResolvMode::withAdjustment() ); 534 for ( CandidateRef & r : finder.candidates ) { 535 // ensure that the the id is passed on so that the expressions are "linked" 536 addCandidate( *r, new ast::UniqueExpr{ unqExpr->location, r->expr, unqExpr->id } ); 537 } 538 } 539 540 void postvisit( const ast::StmtExpr * stmtExpr ) { 541 #warning unimplemented 542 (void)stmtExpr; 543 assert(false); 544 } 545 546 void postvisit( const ast::UntypedInitExpr * initExpr ) { 547 #warning unimplemented 548 (void)initExpr; 549 assert(false); 550 } 551 552 void postvisit( const ast::InitExpr * ) { 553 assertf( false, "CandidateFinder should never see a resolved InitExpr." ); 554 } 555 556 void postvisit( const ast::DeletedExpr * ) { 557 assertf( false, "CandidateFinder should never see a DeletedExpr." ); 558 } 559 560 void postvisit( const ast::GenericExpr * ) { 561 assertf( false, "_Generic is not yet supported." ); 562 } 563 }; 564 565 /// Prunes a list of candidates down to those that have the minimum conversion cost for a given 566 /// return type. Skips ambiguous candidates. 567 CandidateList pruneCandidates( CandidateList & candidates ) { 568 struct PruneStruct { 569 CandidateRef candidate; 570 bool ambiguous; 571 572 PruneStruct() = default; 573 PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {} 574 }; 575 576 // find lowest-cost candidate for each type 577 std::unordered_map< std::string, PruneStruct > selected; 578 for ( CandidateRef & candidate : candidates ) { 579 std::string mangleName; 580 { 581 ast::ptr< ast::Type > newType = candidate->expr->result; 582 candidate->env.apply( newType ); 583 mangleName = Mangle::mangle( newType ); 584 } 585 586 auto found = selected.find( mangleName ); 587 if ( found != selected.end() ) { 588 if ( candidate->cost < found->second.candidate->cost ) { 589 PRINT( 590 std::cerr << "cost " << candidate->cost << " beats " 591 << found->second.candidate->cost << std::endl; 592 ) 593 594 found->second = PruneStruct{ candidate }; 595 } else if ( candidate->cost == found->second.candidate->cost ) { 596 // if one of the candidates contains a deleted identifier, can pick the other, 597 // since deleted expressions should not be ambiguous if there is another option 598 // that is at least as good 599 if ( findDeletedExpr( candidate->expr ) ) { 600 // do nothing 601 PRINT( std::cerr << "candidate is deleted" << std::endl; ) 602 } else if ( findDeletedExpr( found->second.candidate->expr ) ) { 603 PRINT( std::cerr << "current is deleted" << std::endl; ) 604 found->second = PruneStruct{ candidate }; 605 } else { 606 PRINT( std::cerr << "marking ambiguous" << std::endl; ) 607 found->second.ambiguous = true; 608 } 609 } else { 610 PRINT( 611 std::cerr << "cost " << candidate->cost << " loses to " 612 << found->second.candidate->cost << std::endl; 613 ) 614 } 615 } else { 616 selected.emplace_hint( found, mangleName, candidate ); 617 } 618 } 619 620 // report unambiguous min-cost candidates 621 CandidateList out; 622 for ( auto & target : selected ) { 623 if ( target.second.ambiguous ) continue; 624 625 CandidateRef cand = target.second.candidate; 626 627 ast::ptr< ast::Type > newResult = cand->expr->result; 628 cand->env.applyFree( newResult ); 629 cand->expr = ast::mutate_field( 630 cand->expr.get(), &ast::Expr::result, std::move( newResult ) ); 631 632 out.emplace_back( cand ); 633 } 634 return out; 635 } 636 637 } // anonymous namespace 638 22 639 void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) { 23 #warning unimplemented 24 (void)expr; (void)mode; 25 assert(false); 640 // Find alternatives for expression 641 ast::Pass<Finder> finder{ *this }; 642 expr->accept( finder ); 643 644 if ( mode.failFast && candidates.empty() ) { 645 SemanticError( expr, "No reasonable alternatives for expression " ); 646 } 647 648 if ( mode.satisfyAssns || mode.prune ) { 649 // trim candidates to just those where the assertions are satisfiable 650 // - necessary pre-requisite to pruning 651 CandidateList satisfied; 652 std::vector< std::string > errors; 653 for ( auto & candidate : candidates ) { 654 satisfyAssertions( *candidate, symtab, satisfied, errors ); 655 } 656 657 // fail early if none such 658 if ( mode.failFast && satisfied.empty() ) { 659 std::ostringstream stream; 660 stream << "No alternatives with satisfiable assertions for " << expr << "\n"; 661 for ( const auto& err : errors ) { 662 stream << err; 663 } 664 SemanticError( expr->location, stream.str() ); 665 } 666 667 // reset candidates 668 candidates = std::move( satisfied ); 669 } 670 671 if ( mode.prune ) { 672 // trim candidates to single best one 673 PRINT( 674 std::cerr << "alternatives before prune:" << std::endl; 675 print( std::cerr, candidates ); 676 ) 677 678 CandidateList pruned = pruneCandidates( candidates ); 679 680 if ( mode.failFast && pruned.empty() ) { 681 std::ostringstream stream; 682 CandidateList winners = findMinCost( candidates ); 683 stream << "Cannot choose between " << winners.size() << " alternatives for " 684 "expression\n"; 685 ast::print( stream, expr ); 686 stream << " Alternatives are:\n"; 687 print( stream, winners, 1 ); 688 SemanticError( expr->location, stream.str() ); 689 } 690 691 auto oldsize = candidates.size(); 692 candidates = std::move( pruned ); 693 694 PRINT( 695 std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl; 696 ) 697 PRINT( 698 std::cerr << "there are " << candidates.size() << " alternatives after elimination" 699 << std::endl; 700 ) 701 } 702 703 // adjust types after pruning so that types substituted by pruneAlternatives are correctly 704 // adjusted 705 if ( mode.adjust ) { 706 for ( CandidateRef & r : candidates ) { 707 r->expr = ast::mutate_field( 708 r->expr.get(), &ast::Expr::result, 709 adjustExprType( r->expr->result, r->env, symtab ) ); 710 } 711 } 712 713 // Central location to handle gcc extension keyword, etc. for all expressions 714 for ( CandidateRef & r : candidates ) { 715 if ( r->expr->extension != expr->extension ) { 716 r->expr.get_and_mutate()->extension = expr->extension; 717 } 718 } 719 } 720 721 std::vector< CandidateFinder > CandidateFinder::findSubExprs( 722 const std::vector< ast::ptr< ast::Expr > > & xs 723 ) { 724 std::vector< CandidateFinder > out; 725 726 for ( const auto & x : xs ) { 727 out.emplace_back( symtab, env ); 728 out.back().find( x, ResolvMode::withAdjustment() ); 729 730 PRINT( 731 std::cerr << "findSubExprs" << std::endl; 732 print( std::cerr, out.back().candidates ); 733 ) 734 } 735 736 return out; 26 737 } 27 738
Note: See TracChangeset
for help on using the changeset viewer.