- File:
-
- 1 edited
-
src/ResolvExpr/AlternativeFinder.cc (modified) (19 diffs)
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/AlternativeFinder.cc
r62194cb rd06c808 16 16 #include <algorithm> // for copy 17 17 #include <cassert> // for strict_dynamic_cast, assert, assertf 18 #include <cstddef> // for size_t19 18 #include <iostream> // for operator<<, cerr, ostream, endl 20 19 #include <iterator> // for back_insert_iterator, back_inserter 21 20 #include <list> // for _List_iterator, list, _List_const_... 22 21 #include <map> // for _Rb_tree_iterator, map, _Rb_tree_c... 23 #include <memory> // for allocator_traits<>::value_type , unique_ptr22 #include <memory> // for allocator_traits<>::value_type 24 23 #include <utility> // for pair 25 #include <vector> // for vector26 24 27 25 #include "Alternative.h" // for AltList, Alternative … … 30 28 #include "Common/utility.h" // for deleteAll, printAll, CodeLocation 31 29 #include "Cost.h" // for Cost, Cost::zero, operator<<, Cost... 32 #include "ExplodedActual.h" // for ExplodedActual33 30 #include "InitTweak/InitTweak.h" // for getFunctionName 34 31 #include "RenameVars.h" // for RenameVars, global_renamer … … 52 49 #define PRINT( text ) if ( resolvep ) { text } 53 50 //#define DEBUG_COST 54 55 using std::move;56 57 /// copies any copyable type58 template<typename T>59 T copy(const T& x) { return x; }60 51 61 52 namespace ResolvExpr { … … 195 186 printAlts( alternatives, std::cerr ); 196 187 ) 197 AltList pruned;198 pruneAlternatives( alternatives.begin(), alternatives.end(), back_inserter( pruned) );199 if ( failFast && pruned.empty()) {188 AltList::iterator oldBegin = alternatives.begin(); 189 pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives ) ); 190 if ( failFast && alternatives.begin() == oldBegin ) { 200 191 std::ostringstream stream; 201 192 AltList winners; … … 207 198 throw SemanticError( stream.str() ); 208 199 } 209 alternatives = move(pruned);200 alternatives.erase( oldBegin, alternatives.end() ); 210 201 PRINT( 211 202 std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl; … … 342 333 tmpCost.incPoly( -tmpCost.get_polyCost() ); 343 334 if ( tmpCost != Cost::zero ) { 335 // if ( convCost != Cost::zero ) { 344 336 Type *newType = formalType->clone(); 345 337 env.apply( newType ); … … 413 405 /// needAssertions.insert( needAssertions.end(), (*tyvar)->get_assertions().begin(), (*tyvar)->get_assertions().end() ); 414 406 } 407 } 408 409 /// instantiate a single argument by matching actuals from [actualIt, actualEnd) against formalType, 410 /// producing expression(s) in out and their total cost in cost. 411 template< typename AltIterator, typename OutputIterator > 412 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 ) { 413 if ( TupleType * tupleType = dynamic_cast< TupleType * >( formalType ) ) { 414 // formalType is a TupleType - group actuals into a TupleExpr whose type unifies with the TupleType 415 std::list< Expression * > exprs; 416 for ( Type * type : *tupleType ) { 417 if ( ! instantiateArgument( type, defaultValue, actualIt, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( exprs ) ) ) { 418 deleteAll( exprs ); 419 return false; 420 } 421 } 422 *out++ = new TupleExpr( exprs ); 423 } else if ( TypeInstType * ttype = Tuples::isTtype( formalType ) ) { 424 // xxx - mixing default arguments with variadic?? 425 std::list< Expression * > exprs; 426 for ( ; actualIt != actualEnd; ++actualIt ) { 427 exprs.push_back( actualIt->expr->clone() ); 428 cost += actualIt->cost; 429 } 430 Expression * arg = nullptr; 431 if ( exprs.size() == 1 && Tuples::isTtype( exprs.front()->get_result() ) ) { 432 // the case where a ttype value is passed directly is special, e.g. for argument forwarding purposes 433 // xxx - what if passing multiple arguments, last of which is ttype? 434 // xxx - what would happen if unify was changed so that unifying tuple types flattened both before unifying lists? then pass in TupleType(ttype) below. 435 arg = exprs.front(); 436 } else { 437 arg = new TupleExpr( exprs ); 438 } 439 assert( arg && arg->get_result() ); 440 if ( ! unify( ttype, arg->get_result(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) { 441 return false; 442 } 443 *out++ = arg; 444 } else if ( actualIt != actualEnd ) { 445 // both actualType and formalType are atomic (non-tuple) types - if they unify 446 // then accept actual as an argument, otherwise return false (fail to instantiate argument) 447 Expression * actual = actualIt->expr; 448 Type * actualType = actual->get_result(); 449 450 PRINT( 451 std::cerr << "formal type is "; 452 formalType->print( std::cerr ); 453 std::cerr << std::endl << "actual type is "; 454 actualType->print( std::cerr ); 455 std::cerr << std::endl; 456 ) 457 if ( ! unify( formalType, actualType, resultEnv, resultNeed, resultHave, openVars, indexer ) ) { 458 // std::cerr << "unify failed" << std::endl; 459 return false; 460 } 461 // move the expression from the alternative to the output iterator 462 *out++ = actual; 463 actualIt->expr = nullptr; 464 cost += actualIt->cost; 465 ++actualIt; 466 } else { 467 // End of actuals - Handle default values 468 if ( SingleInit *si = dynamic_cast<SingleInit *>( defaultValue )) { 469 if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( si->get_value() ) ) { 470 // so far, only constant expressions are accepted as default values 471 if ( ConstantExpr *cnstexpr = dynamic_cast<ConstantExpr *>( castExpr->get_arg() ) ) { 472 if ( Constant *cnst = dynamic_cast<Constant *>( cnstexpr->get_constant() ) ) { 473 if ( unify( formalType, cnst->get_type(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) { 474 *out++ = cnstexpr->clone(); 475 return true; 476 } // if 477 } // if 478 } // if 479 } 480 } // if 481 return false; 482 } // if 483 return true; 484 } 485 486 bool AlternativeFinder::instantiateFunction( std::list< DeclarationWithType* >& formals, const AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave, AltList & out ) { 487 simpleCombineEnvironments( actuals.begin(), actuals.end(), resultEnv ); 488 // make sure we don't widen any existing bindings 489 for ( TypeEnvironment::iterator i = resultEnv.begin(); i != resultEnv.end(); ++i ) { 490 i->allowWidening = false; 491 } 492 resultEnv.extractOpenVars( openVars ); 493 494 // flatten actuals so that each actual has an atomic (non-tuple) type 495 AltList exploded; 496 Tuples::explode( actuals, indexer, back_inserter( exploded ) ); 497 498 AltList::iterator actualExpr = exploded.begin(); 499 AltList::iterator actualEnd = exploded.end(); 500 for ( DeclarationWithType * formal : formals ) { 501 // match flattened actuals with formal parameters - actuals will be grouped to match 502 // with formals as appropriate 503 Cost cost = Cost::zero; 504 std::list< Expression * > newExprs; 505 ObjectDecl * obj = strict_dynamic_cast< ObjectDecl * >( formal ); 506 if ( ! instantiateArgument( obj->get_type(), obj->get_init(), actualExpr, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( newExprs ) ) ) { 507 deleteAll( newExprs ); 508 return false; 509 } 510 // success - produce argument as a new alternative 511 assert( newExprs.size() == 1 ); 512 out.push_back( Alternative( newExprs.front(), resultEnv, cost ) ); 513 } 514 if ( actualExpr != actualEnd ) { 515 // there are still actuals remaining, but we've run out of formal parameters to match against 516 // this is okay only if the function is variadic 517 if ( ! isVarArgs ) { 518 return false; 519 } 520 out.splice( out.end(), exploded, actualExpr, actualEnd ); 521 } 522 return true; 415 523 } 416 524 … … 567 675 } 568 676 569 /// Gets a default value from an initializer, nullptr if not present 570 ConstantExpr* getDefaultValue( Initializer* init ) { 571 if ( SingleInit* si = dynamic_cast<SingleInit*>( init ) ) { 572 if ( CastExpr* ce = dynamic_cast<CastExpr*>( si->get_value() ) ) { 573 return dynamic_cast<ConstantExpr*>( ce->get_arg() ); 574 } 575 } 576 return nullptr; 577 } 578 579 /// State to iteratively build a match of parameter expressions to arguments 580 struct ArgPack { 581 std::size_t parent; ///< Index of parent pack 582 std::unique_ptr<Expression> expr; ///< The argument stored here 583 Cost cost; ///< The cost of this argument 584 TypeEnvironment env; ///< Environment for this pack 585 AssertionSet need; ///< Assertions outstanding for this pack 586 AssertionSet have; ///< Assertions found for this pack 587 OpenVarSet openVars; ///< Open variables for this pack 588 unsigned nextArg; ///< Index of next argument in arguments list 589 unsigned tupleStart; ///< Number of tuples that start at this index 590 unsigned nextExpl; ///< Index of next exploded element 591 unsigned explAlt; ///< Index of alternative for nextExpl > 0 592 593 ArgPack() 594 : parent(0), expr(), cost(Cost::zero), env(), need(), have(), openVars(), nextArg(0), 595 tupleStart(0), nextExpl(0), explAlt(0) {} 596 597 ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have, 598 const OpenVarSet& openVars) 599 : parent(0), expr(), cost(Cost::zero), env(env), need(need), have(have), 600 openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {} 601 602 ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need, 603 AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg, 604 unsigned tupleStart = 0, Cost cost = Cost::zero, unsigned nextExpl = 0, 605 unsigned explAlt = 0 ) 606 : parent(parent), expr(expr->clone()), cost(cost), env(move(env)), need(move(need)), 607 have(move(have)), openVars(move(openVars)), nextArg(nextArg), tupleStart(tupleStart), 608 nextExpl(nextExpl), explAlt(explAlt) {} 609 610 ArgPack(const ArgPack& o, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have, 611 OpenVarSet&& openVars, unsigned nextArg, Cost added ) 612 : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), cost(o.cost + added), 613 env(move(env)), need(move(need)), have(move(have)), openVars(move(openVars)), 614 nextArg(nextArg), tupleStart(o.tupleStart), nextExpl(0), explAlt(0) {} 615 616 /// true iff this pack is in the middle of an exploded argument 617 bool hasExpl() const { return nextExpl > 0; } 618 619 /// Gets the list of exploded alternatives for this pack 620 const ExplodedActual& getExpl( const ExplodedArgs& args ) const { 621 return args[nextArg-1][explAlt]; 622 } 623 624 /// Ends a tuple expression, consolidating the appropriate actuals 625 void endTuple( const std::vector<ArgPack>& packs ) { 626 // add all expressions in tuple to list, summing cost 627 std::list<Expression*> exprs; 628 const ArgPack* pack = this; 629 if ( expr ) { exprs.push_front( expr.release() ); } 630 while ( pack->tupleStart == 0 ) { 631 pack = &packs[pack->parent]; 632 exprs.push_front( pack->expr->clone() ); 633 cost += pack->cost; 634 } 635 // reset pack to appropriate tuple 636 expr.reset( new TupleExpr( exprs ) ); 637 tupleStart = pack->tupleStart - 1; 638 parent = pack->parent; 639 } 640 }; 641 642 /// Instantiates an argument to match a formal, returns false if no results left 643 bool instantiateArgument( Type* formalType, Initializer* initializer, 644 const ExplodedArgs& args, std::vector<ArgPack>& results, std::size_t& genStart, 645 const SymTab::Indexer& indexer, unsigned nTuples = 0 ) { 646 if ( TupleType* tupleType = dynamic_cast<TupleType*>( formalType ) ) { 647 // formalType is a TupleType - group actuals into a TupleExpr 648 ++nTuples; 649 for ( Type* type : *tupleType ) { 650 // xxx - dropping initializer changes behaviour from previous, but seems correct 651 if ( ! instantiateArgument( 652 type, nullptr, args, results, genStart, indexer, nTuples ) ) 653 return false; 654 nTuples = 0; 655 } 656 // re-consititute tuples for final generation 657 for ( auto i = genStart; i < results.size(); ++i ) { 658 results[i].endTuple( results ); 659 } 660 return true; 661 } else if ( TypeInstType* ttype = Tuples::isTtype( formalType ) ) { 662 // formalType is a ttype, consumes all remaining arguments 663 // xxx - mixing default arguments with variadic?? 664 665 // completed tuples; will be spliced to end of results to finish 666 std::vector<ArgPack> finalResults{}; 667 668 // iterate until all results completed 669 std::size_t genEnd; 670 ++nTuples; 671 do { 672 genEnd = results.size(); 673 674 // add another argument to results 675 for ( std::size_t i = genStart; i < genEnd; ++i ) { 676 auto nextArg = results[i].nextArg; 677 678 // use next element of exploded tuple if present 679 if ( results[i].hasExpl() ) { 680 const ExplodedActual& expl = results[i].getExpl( args ); 681 682 unsigned nextExpl = results[i].nextExpl + 1; 683 if ( nextExpl == expl.exprs.size() ) { 684 nextExpl = 0; 685 } 686 687 results.emplace_back( 688 i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env), 689 copy(results[i].need), copy(results[i].have), 690 copy(results[i].openVars), nextArg, nTuples, Cost::zero, nextExpl, 691 results[i].explAlt ); 692 693 continue; 694 } 695 696 // finish result when out of arguments 697 if ( nextArg >= args.size() ) { 698 ArgPack newResult{ 699 results[i].env, results[i].need, results[i].have, 700 results[i].openVars }; 701 newResult.nextArg = nextArg; 702 Type* argType; 703 704 if ( nTuples > 0 ) { 705 // first iteration, push empty tuple expression 706 newResult.parent = i; 707 std::list<Expression*> emptyList; 708 newResult.expr.reset( new TupleExpr( emptyList ) ); 709 argType = newResult.expr->get_result(); 710 } else { 711 // clone result to collect tuple 712 newResult.parent = results[i].parent; 713 newResult.cost = results[i].cost; 714 newResult.tupleStart = results[i].tupleStart; 715 newResult.expr.reset( results[i].expr->clone() ); 716 argType = newResult.expr->get_result(); 717 718 if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) { 719 // the case where a ttype value is passed directly is special, 720 // e.g. for argument forwarding purposes 721 // xxx - what if passing multiple arguments, last of which is 722 // ttype? 723 // xxx - what would happen if unify was changed so that unifying 724 // tuple 725 // types flattened both before unifying lists? then pass in 726 // TupleType (ttype) below. 727 --newResult.tupleStart; 728 } else { 729 // collapse leftover arguments into tuple 730 newResult.endTuple( results ); 731 argType = newResult.expr->get_result(); 732 } 733 } 734 735 // check unification for ttype before adding to final 736 if ( unify( ttype, argType, newResult.env, newResult.need, newResult.have, 737 newResult.openVars, indexer ) ) { 738 finalResults.push_back( move(newResult) ); 739 } 740 741 continue; 742 } 743 744 // add each possible next argument 745 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { 746 const ExplodedActual& expl = args[nextArg][j]; 747 748 // fresh copies of parent parameters for this iteration 749 TypeEnvironment env = results[i].env; 750 OpenVarSet openVars = results[i].openVars; 751 752 env.addActual( expl.env, openVars ); 753 754 // skip empty tuple arguments by (near-)cloning parent into next gen 755 if ( expl.exprs.empty() ) { 756 results.emplace_back( 757 results[i], move(env), copy(results[i].need), 758 copy(results[i].have), move(openVars), nextArg + 1, expl.cost ); 759 760 continue; 761 } 762 763 // add new result 764 results.emplace_back( 765 i, expl.exprs.front().get(), move(env), copy(results[i].need), 766 copy(results[i].have), move(openVars), nextArg + 1, 767 nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); 768 } 769 } 770 771 // reset for next round 772 genStart = genEnd; 773 nTuples = 0; 774 } while ( genEnd != results.size() ); 775 776 // splice final results onto results 777 for ( std::size_t i = 0; i < finalResults.size(); ++i ) { 778 results.push_back( move(finalResults[i]) ); 779 } 780 return ! finalResults.empty(); 781 } 782 783 // iterate each current subresult 784 std::size_t genEnd = results.size(); 785 for ( std::size_t i = genStart; i < genEnd; ++i ) { 786 auto nextArg = results[i].nextArg; 787 788 // use remainder of exploded tuple if present 789 if ( results[i].hasExpl() ) { 790 const ExplodedActual& expl = results[i].getExpl( args ); 791 Expression* expr = expl.exprs[results[i].nextExpl].get(); 792 793 TypeEnvironment env = results[i].env; 794 AssertionSet need = results[i].need, have = results[i].have; 795 OpenVarSet openVars = results[i].openVars; 796 797 Type* actualType = expr->get_result(); 798 799 PRINT( 800 std::cerr << "formal type is "; 801 formalType->print( std::cerr ); 802 std::cerr << std::endl << "actual type is "; 803 actualType->print( std::cerr ); 804 std::cerr << std::endl; 805 ) 806 807 if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) { 808 unsigned nextExpl = results[i].nextExpl + 1; 809 if ( nextExpl == expl.exprs.size() ) { 810 nextExpl = 0; 811 } 812 813 results.emplace_back( 814 i, expr, move(env), move(need), move(have), move(openVars), nextArg, 815 nTuples, Cost::zero, nextExpl, results[i].explAlt ); 816 } 817 818 continue; 819 } 820 821 // use default initializers if out of arguments 822 if ( nextArg >= args.size() ) { 823 if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) { 824 if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) { 825 TypeEnvironment env = results[i].env; 826 AssertionSet need = results[i].need, have = results[i].have; 827 OpenVarSet openVars = results[i].openVars; 828 829 if ( unify( formalType, cnst->get_type(), env, need, have, openVars, 830 indexer ) ) { 831 results.emplace_back( 832 i, cnstExpr, move(env), move(need), move(have), 833 move(openVars), nextArg, nTuples ); 834 } 835 } 836 } 837 838 continue; 839 } 840 841 // Check each possible next argument 842 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { 843 const ExplodedActual& expl = args[nextArg][j]; 844 845 // fresh copies of parent parameters for this iteration 846 TypeEnvironment env = results[i].env; 847 AssertionSet need = results[i].need, have = results[i].have; 848 OpenVarSet openVars = results[i].openVars; 849 850 env.addActual( expl.env, openVars ); 851 852 // skip empty tuple arguments by (near-)cloning parent into next gen 853 if ( expl.exprs.empty() ) { 854 results.emplace_back( 855 results[i], move(env), move(need), move(have), move(openVars), 856 nextArg + 1, expl.cost ); 857 858 continue; 859 } 860 861 // consider only first exploded actual 862 Expression* expr = expl.exprs.front().get(); 863 Type* actualType = expr->get_result()->clone(); 864 865 PRINT( 866 std::cerr << "formal type is "; 867 formalType->print( std::cerr ); 868 std::cerr << std::endl << "actual type is "; 869 actualType->print( std::cerr ); 870 std::cerr << std::endl; 871 ) 872 873 // attempt to unify types 874 if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) { 875 // add new result 876 results.emplace_back( 877 i, expr, move(env), move(need), move(have), move(openVars), nextArg + 1, 878 nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); 879 } 880 } 881 } 882 883 // reset for next parameter 884 genStart = genEnd; 885 886 return genEnd != results.size(); 887 } 888 889 template<typename OutputIterator> 890 void AlternativeFinder::validateFunctionAlternative( const Alternative &func, ArgPack& result, 891 const std::vector<ArgPack>& results, OutputIterator out ) { 892 ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() ); 893 // sum cost and accumulate actuals 894 std::list<Expression*>& args = appExpr->get_args(); 895 Cost cost = Cost::zero; 896 const ArgPack* pack = &result; 897 while ( pack->expr ) { 898 args.push_front( pack->expr->clone() ); 899 cost += pack->cost; 900 pack = &results[pack->parent]; 901 } 902 // build and validate new alternative 903 Alternative newAlt( appExpr, result.env, cost ); 904 PRINT( 905 std::cerr << "instantiate function success: " << appExpr << std::endl; 906 std::cerr << "need assertions:" << std::endl; 907 printAssertionSet( result.need, std::cerr, 8 ); 908 ) 909 inferParameters( result.need, result.have, newAlt, result.openVars, out ); 910 } 911 912 template<typename OutputIterator> 913 void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, 914 FunctionType *funcType, const ExplodedArgs &args, OutputIterator out ) { 915 OpenVarSet funcOpenVars; 916 AssertionSet funcNeed, funcHave; 917 TypeEnvironment funcEnv( func.env ); 918 makeUnifiableVars( funcType, funcOpenVars, funcNeed ); 919 // add all type variables as open variables now so that those not used in the parameter 920 // list are still considered open. 921 funcEnv.add( funcType->get_forall() ); 922 677 template< typename OutputIterator > 678 void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const AltList &actualAlt, OutputIterator out ) { 679 OpenVarSet openVars; 680 AssertionSet resultNeed, resultHave; 681 TypeEnvironment resultEnv( func.env ); 682 makeUnifiableVars( funcType, openVars, resultNeed ); 683 resultEnv.add( funcType->get_forall() ); // add all type variables as open variables now so that those not used in the parameter list are still considered open 684 AltList instantiatedActuals; // filled by instantiate function 923 685 if ( targetType && ! targetType->isVoid() && ! funcType->get_returnVals().empty() ) { 924 686 // attempt to narrow based on expected target type 925 687 Type * returnType = funcType->get_returnVals().front()->get_type(); 926 if ( ! unify( returnType, targetType, funcEnv, funcNeed, funcHave, funcOpenVars, 927 indexer ) ) { 928 // unification failed, don't pursue this function alternative 688 if ( ! unify( returnType, targetType, resultEnv, resultNeed, resultHave, openVars, indexer ) ) { 689 // unification failed, don't pursue this alternative 929 690 return; 930 691 } 931 692 } 932 693 933 // iteratively build matches, one parameter at a time 934 std::vector<ArgPack> results; 935 results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } ); 936 std::size_t genStart = 0; 937 938 for ( DeclarationWithType* formal : funcType->get_parameters() ) { 939 ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal ); 940 if ( ! instantiateArgument( 941 obj->get_type(), obj->get_init(), args, results, genStart, indexer ) ) 942 return; 943 } 944 945 if ( funcType->get_isVarArgs() ) { 946 // append any unused arguments to vararg pack 947 std::size_t genEnd; 948 do { 949 genEnd = results.size(); 950 951 // iterate results 952 for ( std::size_t i = genStart; i < genEnd; ++i ) { 953 auto nextArg = results[i].nextArg; 954 955 // use remainder of exploded tuple if present 956 if ( results[i].hasExpl() ) { 957 const ExplodedActual& expl = results[i].getExpl( args ); 958 959 unsigned nextExpl = results[i].nextExpl + 1; 960 if ( nextExpl == expl.exprs.size() ) { 961 nextExpl = 0; 962 } 963 964 results.emplace_back( 965 i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env), 966 copy(results[i].need), copy(results[i].have), 967 copy(results[i].openVars), nextArg, 0, Cost::zero, nextExpl, 968 results[i].explAlt ); 969 970 continue; 971 } 972 973 // finish result when out of arguments 974 if ( nextArg >= args.size() ) { 975 validateFunctionAlternative( func, results[i], results, out ); 976 977 continue; 978 } 979 980 // add each possible next argument 981 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { 982 const ExplodedActual& expl = args[nextArg][j]; 983 984 // fresh copies of parent parameters for this iteration 985 TypeEnvironment env = results[i].env; 986 OpenVarSet openVars = results[i].openVars; 987 988 env.addActual( expl.env, openVars ); 989 990 // skip empty tuple arguments by (near-)cloning parent into next gen 991 if ( expl.exprs.empty() ) { 992 results.emplace_back( 993 results[i], move(env), copy(results[i].need), 994 copy(results[i].have), move(openVars), nextArg + 1, expl.cost ); 995 996 continue; 997 } 998 999 // add new result 1000 results.emplace_back( 1001 i, expl.exprs.front().get(), move(env), copy(results[i].need), 1002 copy(results[i].have), move(openVars), nextArg + 1, 0, 1003 expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); 1004 } 1005 } 1006 1007 genStart = genEnd; 1008 } while ( genEnd != results.size() ); 1009 } else { 1010 // filter out results that don't use all the arguments 1011 for ( std::size_t i = genStart; i < results.size(); ++i ) { 1012 ArgPack& result = results[i]; 1013 if ( ! result.hasExpl() && result.nextArg >= args.size() ) { 1014 validateFunctionAlternative( func, result, results, out ); 1015 } 1016 } 694 if ( instantiateFunction( funcType->get_parameters(), actualAlt, funcType->get_isVarArgs(), openVars, resultEnv, resultNeed, resultHave, instantiatedActuals ) ) { 695 ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() ); 696 Alternative newAlt( appExpr, resultEnv, sumCost( instantiatedActuals ) ); 697 makeExprList( instantiatedActuals, appExpr->get_args() ); 698 PRINT( 699 std::cerr << "instantiate function success: " << appExpr << std::endl; 700 std::cerr << "need assertions:" << std::endl; 701 printAssertionSet( resultNeed, std::cerr, 8 ); 702 ) 703 inferParameters( resultNeed, resultHave, newAlt, openVars, out ); 1017 704 } 1018 705 } … … 1024 711 if ( funcFinder.alternatives.empty() ) return; 1025 712 1026 std::vector< AlternativeFinder > argAlternatives; 1027 findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), 1028 back_inserter( argAlternatives ) ); 713 std::list< AlternativeFinder > argAlternatives; 714 findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), back_inserter( argAlternatives ) ); 715 716 std::list< AltList > possibilities; 717 combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) ); 1029 718 1030 719 // take care of possible tuple assignments 1031 720 // if not tuple assignment, assignment is taken care of as a normal function call 1032 Tuples::handleTupleAssignment( *this, untypedExpr, argAlternatives );721 Tuples::handleTupleAssignment( *this, untypedExpr, possibilities ); 1033 722 1034 723 // find function operators … … 1041 730 printAlts( funcOpFinder.alternatives, std::cerr, 1 ); 1042 731 ) 1043 1044 // pre-explode arguments1045 ExplodedArgs argExpansions;1046 argExpansions.reserve( argAlternatives.size() );1047 1048 for ( const AlternativeFinder& arg : argAlternatives ) {1049 argExpansions.emplace_back();1050 auto& argE = argExpansions.back();1051 argE.reserve( arg.alternatives.size() );1052 1053 for ( const Alternative& actual : arg ) {1054 argE.emplace_back( actual, indexer );1055 }1056 }1057 732 1058 733 AltList candidates; … … 1069 744 Alternative newFunc( *func ); 1070 745 referenceToRvalueConversion( newFunc.expr ); 1071 makeFunctionAlternatives( newFunc, function, argExpansions, 1072 std::back_inserter( candidates ) ); 746 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) { 747 // XXX 748 //Designators::check_alternative( function, *actualAlt ); 749 makeFunctionAlternatives( newFunc, function, *actualAlt, std::back_inserter( candidates ) ); 750 } 1073 751 } 1074 752 } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->get_result()->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer) … … 1078 756 Alternative newFunc( *func ); 1079 757 referenceToRvalueConversion( newFunc.expr ); 1080 makeFunctionAlternatives( newFunc, function, argExpansions, 1081 std::back_inserter( candidates ) ); 758 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) { 759 makeFunctionAlternatives( newFunc, function, *actualAlt, std::back_inserter( candidates ) ); 760 } // for 1082 761 } // if 1083 762 } // if 1084 763 } 764 765 // try each function operator ?() with the current function alternative and each of the argument combinations 766 for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin(); funcOp != funcOpFinder.alternatives.end(); ++funcOp ) { 767 // check if the type is pointer to function 768 if ( PointerType *pointer = dynamic_cast< PointerType* >( funcOp->expr->get_result()->stripReferences() ) ) { 769 if ( FunctionType *function = dynamic_cast< FunctionType* >( pointer->get_base() ) ) { 770 Alternative newFunc( *funcOp ); 771 referenceToRvalueConversion( newFunc.expr ); 772 for ( std::list< AltList >::iterator actualAlt = possibilities.begin(); actualAlt != possibilities.end(); ++actualAlt ) { 773 AltList currentAlt; 774 currentAlt.push_back( *func ); 775 currentAlt.insert( currentAlt.end(), actualAlt->begin(), actualAlt->end() ); 776 makeFunctionAlternatives( newFunc, function, currentAlt, std::back_inserter( candidates ) ); 777 } // for 778 } // if 779 } // if 780 } // for 1085 781 } catch ( SemanticError &e ) { 1086 782 errors.append( e ); … … 1088 784 } // for 1089 785 1090 // try each function operator ?() with each function alternative1091 if ( ! funcOpFinder.alternatives.empty() ) {1092 // add exploded function alternatives to front of argument list1093 std::vector<ExplodedActual> funcE;1094 funcE.reserve( funcFinder.alternatives.size() );1095 for ( const Alternative& actual : funcFinder ) {1096 funcE.emplace_back( actual, indexer );1097 }1098 argExpansions.insert( argExpansions.begin(), move(funcE) );1099 1100 for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin();1101 funcOp != funcOpFinder.alternatives.end(); ++funcOp ) {1102 try {1103 // check if type is a pointer to function1104 if ( PointerType* pointer = dynamic_cast<PointerType*>(1105 funcOp->expr->get_result()->stripReferences() ) ) {1106 if ( FunctionType* function =1107 dynamic_cast<FunctionType*>( pointer->get_base() ) ) {1108 Alternative newFunc( *funcOp );1109 referenceToRvalueConversion( newFunc.expr );1110 makeFunctionAlternatives( newFunc, function, argExpansions,1111 std::back_inserter( candidates ) );1112 }1113 }1114 } catch ( SemanticError &e ) {1115 errors.append( e );1116 }1117 }1118 }1119 1120 786 // Implement SFINAE; resolution errors are only errors if there aren't any non-erroneous resolutions 1121 787 if ( candidates.empty() && ! errors.isEmpty() ) { throw errors; } 1122 788 1123 789 // compute conversionsion costs 1124 for ( Alt ernative& withFunc : candidates) {1125 Cost cvtCost = computeApplicationConversionCost( withFunc, indexer );790 for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) { 791 Cost cvtCost = computeApplicationConversionCost( *withFunc, indexer ); 1126 792 1127 793 PRINT( 1128 ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc .expr );794 ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc->expr ); 1129 795 PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() ); 1130 796 FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() ); … … 1135 801 printAll( appExpr->get_args(), std::cerr, 8 ); 1136 802 std::cerr << "bindings are:" << std::endl; 1137 withFunc .env.print( std::cerr, 8 );803 withFunc->env.print( std::cerr, 8 ); 1138 804 std::cerr << "cost of conversion is:" << cvtCost << std::endl; 1139 805 ) 1140 806 if ( cvtCost != Cost::infinity ) { 1141 withFunc .cvtCost = cvtCost;1142 alternatives.push_back( withFunc );807 withFunc->cvtCost = cvtCost; 808 alternatives.push_back( *withFunc ); 1143 809 } // if 1144 810 } // for 1145 811 1146 candidates = move(alternatives); 1147 1148 // use a new list so that alternatives are not examined by addAnonConversions twice. 1149 AltList winners; 1150 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) ); 1151 1152 // function may return struct or union value, in which case we need to add alternatives 1153 // for implicitconversions to each of the anonymous members, must happen after findMinCost 1154 // since anon conversions are never the cheapest expression 1155 for ( const Alternative & alt : winners ) { 812 candidates.clear(); 813 candidates.splice( candidates.end(), alternatives ); 814 815 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( alternatives ) ); 816 817 // function may return struct or union value, in which case we need to add alternatives for implicit 818 // conversions to each of the anonymous members, must happen after findMinCost since anon conversions 819 // are never the cheapest expression 820 for ( const Alternative & alt : alternatives ) { 1156 821 addAnonConversions( alt ); 1157 822 } 1158 spliceBegin( alternatives, winners );1159 823 1160 824 if ( alternatives.empty() && targetType && ! targetType->isVoid() ) { … … 1180 844 AlternativeFinder finder( indexer, env ); 1181 845 finder.find( addressExpr->get_arg() ); 1182 for ( Alternative& alt : finder.alternatives ) { 1183 if ( isLvalue( alt.expr ) ) { 1184 alternatives.push_back( 1185 Alternative{ new AddressExpr( alt.expr->clone() ), alt.env, alt.cost } ); 846 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) { 847 if ( isLvalue( i->expr ) ) { 848 alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) ); 1186 849 } // if 1187 850 } // for … … 1189 852 1190 853 void AlternativeFinder::visit( LabelAddressExpr * expr ) { 1191 alternatives.push_back( Alternative { expr->clone(), env, Cost::zero });854 alternatives.push_back( Alternative( expr->clone(), env, Cost::zero) ); 1192 855 } 1193 856 … … 1231 894 1232 895 AltList candidates; 1233 for ( Alternative& alt : finder.alternatives) {896 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) { 1234 897 AssertionSet needAssertions, haveAssertions; 1235 898 OpenVarSet openVars; … … 1239 902 // that are cast directly. The candidate is invalid if it has fewer results than there are types to cast 1240 903 // to. 1241 int discardedValues = alt.expr->get_result()->size() - castExpr->get_result()->size();904 int discardedValues = i->expr->get_result()->size() - castExpr->get_result()->size(); 1242 905 if ( discardedValues < 0 ) continue; 1243 906 // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not 1244 907 // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3])) 1245 908 // unification run for side-effects 1246 unify( castExpr->get_result(), alt.expr->get_result(), alt.env, needAssertions, 1247 haveAssertions, openVars, indexer ); 1248 Cost thisCost = castCost( alt.expr->get_result(), castExpr->get_result(), indexer, 1249 alt.env ); 909 unify( castExpr->get_result(), i->expr->get_result(), i->env, needAssertions, haveAssertions, openVars, indexer ); 910 Cost thisCost = castCost( i->expr->get_result(), castExpr->get_result(), indexer, i->env ); 1250 911 if ( thisCost != Cost::infinity ) { 1251 912 // count one safe conversion for each value that is thrown away 1252 913 thisCost.incSafe( discardedValues ); 1253 Alternative newAlt( restructureCast( alt.expr->clone(), toType ), alt.env, 1254 alt.cost, thisCost ); 1255 inferParameters( needAssertions, haveAssertions, newAlt, openVars, 1256 back_inserter( candidates ) ); 914 Alternative newAlt( restructureCast( i->expr->clone(), toType ), i->env, i->cost, thisCost ); 915 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) ); 1257 916 } // if 1258 917 } // for … … 1541 1200 1542 1201 void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) { 1543 std::vector< AlternativeFinder > subExprAlternatives; 1544 findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), 1545 back_inserter( subExprAlternatives ) ); 1546 std::vector< AltList > possibilities; 1547 combos( subExprAlternatives.begin(), subExprAlternatives.end(), 1548 back_inserter( possibilities ) ); 1549 for ( const AltList& alts : possibilities ) { 1202 std::list< AlternativeFinder > subExprAlternatives; 1203 findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) ); 1204 std::list< AltList > possibilities; 1205 combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) ); 1206 for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) { 1550 1207 std::list< Expression * > exprs; 1551 makeExprList( alts, exprs );1208 makeExprList( *i, exprs ); 1552 1209 1553 1210 TypeEnvironment compositeEnv; 1554 simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv ); 1555 alternatives.push_back( 1556 Alternative{ new TupleExpr( exprs ), compositeEnv, sumCost( alts ) } ); 1211 simpleCombineEnvironments( i->begin(), i->end(), compositeEnv ); 1212 alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) ); 1557 1213 } // for 1558 1214 }
Note:
See TracChangeset
for help on using the changeset viewer.
