- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/AlternativeFinder.cc
r11094d9 r62194cb 16 16 #include <algorithm> // for copy 17 17 #include <cassert> // for strict_dynamic_cast, assert, assertf 18 #include <cstddef> // for size_t 18 19 #include <iostream> // for operator<<, cerr, ostream, endl 19 20 #include <iterator> // for back_insert_iterator, back_inserter 20 21 #include <list> // for _List_iterator, list, _List_const_... 21 22 #include <map> // for _Rb_tree_iterator, map, _Rb_tree_c... 22 #include <memory> // for allocator_traits<>::value_type 23 #include <memory> // for allocator_traits<>::value_type, unique_ptr 23 24 #include <utility> // for pair 24 25 #include <vector> // for vector … … 29 30 #include "Common/utility.h" // for deleteAll, printAll, CodeLocation 30 31 #include "Cost.h" // for Cost, Cost::zero, operator<<, Cost... 32 #include "ExplodedActual.h" // for ExplodedActual 31 33 #include "InitTweak/InitTweak.h" // for getFunctionName 32 34 #include "RenameVars.h" // for RenameVars, global_renamer … … 50 52 #define PRINT( text ) if ( resolvep ) { text } 51 53 //#define DEBUG_COST 54 55 using std::move; 56 57 /// copies any copyable type 58 template<typename T> 59 T copy(const T& x) { return x; } 52 60 53 61 namespace ResolvExpr { … … 187 195 printAlts( alternatives, std::cerr ); 188 196 ) 189 AltList ::iterator oldBegin = alternatives.begin();190 pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives) );191 if ( failFast && alternatives.begin() == oldBegin) {197 AltList pruned; 198 pruneAlternatives( alternatives.begin(), alternatives.end(), back_inserter( pruned ) ); 199 if ( failFast && pruned.empty() ) { 192 200 std::ostringstream stream; 193 201 AltList winners; … … 199 207 throw SemanticError( stream.str() ); 200 208 } 201 alternatives .erase( oldBegin, alternatives.end());209 alternatives = move(pruned); 202 210 PRINT( 203 211 std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl; … … 571 579 /// State to iteratively build a match of parameter expressions to arguments 572 580 struct ArgPack { 573 AltList actuals; ///< Arguments included in this pack 574 TypeEnvironment env; ///< Environment for this pack 575 AssertionSet need; ///< Assertions outstanding for this pack 576 AssertionSet have; ///< Assertions found for this pack 577 OpenVarSet openVars; ///< Open variables for this pack 578 unsigned nextArg; ///< Index of next argument in arguments list 579 std::vector<Alternative> expls; ///< Exploded actuals left over from last match 580 unsigned nextExpl; ///< Index of next exploded alternative to use 581 std::vector<unsigned> tupleEls; /// Number of elements in current tuple element(s) 582 583 ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have, 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, 584 598 const OpenVarSet& openVars) 585 : actuals(), env(env), need(need), have(have), openVars(openVars), nextArg(0), 586 expls(), nextExpl(0), tupleEls() {} 587 588 /// Starts a new tuple expression 589 void beginTuple() { 590 if ( ! tupleEls.empty() ) ++tupleEls.back(); 591 tupleEls.push_back(0); 592 } 593 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 594 624 /// Ends a tuple expression, consolidating the appropriate actuals 595 void endTuple( ) {596 // set up new Tuple alternative625 void endTuple( const std::vector<ArgPack>& packs ) { 626 // add all expressions in tuple to list, summing cost 597 627 std::list<Expression*> exprs; 598 Cost cost = Cost::zero; 599 600 // transfer elements into alternative 601 for (unsigned i = 0; i < tupleEls.back(); ++i) { 602 exprs.push_front( actuals.back().expr ); 603 actuals.back().expr = nullptr; 604 cost += actuals.back().cost; 605 actuals.pop_back(); 606 } 607 tupleEls.pop_back(); 608 609 // build new alternative 610 actuals.emplace_back( new TupleExpr( exprs ), this->env, cost ); 611 } 612 613 /// Clones and adds an actual, returns this 614 ArgPack& withArg( Expression* expr, Cost cost = Cost::zero ) { 615 actuals.emplace_back( expr->clone(), this->env, cost ); 616 if ( ! tupleEls.empty() ) ++tupleEls.back(); 617 return *this; 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; 618 639 } 619 640 }; 620 641 621 642 /// Instantiates an argument to match a formal, returns false if no results left 622 bool instantiateArgument( Type* formalType, Initializer* initializer, 623 const std::vector< AlternativeFinder >& args, 624 std::vector<ArgPack>& results, std::vector<ArgPack>& nextResults, 625 const SymTab::Indexer& indexer ) { 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 ) { 626 646 if ( TupleType* tupleType = dynamic_cast<TupleType*>( formalType ) ) { 627 647 // formalType is a TupleType - group actuals into a TupleExpr 628 for ( ArgPack& result : results ) { result.beginTuple(); }648 ++nTuples; 629 649 for ( Type* type : *tupleType ) { 630 650 // xxx - dropping initializer changes behaviour from previous, but seems correct 631 if ( ! instantiateArgument( type, nullptr, args, results, nextResults, indexer ) ) 651 if ( ! instantiateArgument( 652 type, nullptr, args, results, genStart, indexer, nTuples ) ) 632 653 return false; 633 } 634 for ( ArgPack& result : results ) { result.endTuple(); } 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 } 635 660 return true; 636 661 } else if ( TypeInstType* ttype = Tuples::isTtype( formalType ) ) { 637 662 // formalType is a ttype, consumes all remaining arguments 638 663 // xxx - mixing default arguments with variadic?? 639 std::vector<ArgPack> finalResults{}; /// list of completed tuples 640 // start tuples 641 for ( ArgPack& result : results ) { 642 result.beginTuple(); 643 644 // use rest of exploded tuple if present 645 while ( result.nextExpl < result.expls.size() ) { 646 const Alternative& actual = result.expls[result.nextExpl]; 647 result.env.addActual( actual.env, result.openVars ); 648 result.withArg( actual.expr ); 649 ++result.nextExpl; 650 } 651 } 664 665 // completed tuples; will be spliced to end of results to finish 666 std::vector<ArgPack> finalResults{}; 667 652 668 // iterate until all results completed 653 while ( ! results.empty() ) { 669 std::size_t genEnd; 670 ++nTuples; 671 do { 672 genEnd = results.size(); 673 654 674 // add another argument to results 655 for ( ArgPack& result : results ) { 656 // finish result when out of arguments 657 if ( result.nextArg >= args.size() ) { 658 Type* argType = result.actuals.back().expr->get_result(); 659 if ( result.tupleEls.back() == 1 && Tuples::isTtype( argType ) ) { 660 // the case where a ttype value is passed directly is special, e.g. for 661 // argument forwarding purposes 662 // xxx - what if passing multiple arguments, last of which is ttype? 663 // xxx - what would happen if unify was changed so that unifying tuple 664 // types flattened both before unifying lists? then pass in TupleType 665 // (ttype) below. 666 result.tupleEls.pop_back(); 667 } else { 668 // collapse leftover arguments into tuple 669 result.endTuple(); 670 argType = result.actuals.back().expr->get_result(); 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; 671 685 } 672 // check unification for ttype before adding to final 673 if ( unify( ttype, argType, result.env, result.need, result.have, 674 result.openVars, indexer ) ) { 675 finalResults.push_back( std::move(result) ); 676 } 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 677 693 continue; 678 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 } 679 743 680 744 // add each possible next argument 681 for ( const Alternative& actual : args[result.nextArg] ) { 682 ArgPack aResult = result; // copy to clone everything 683 // add details of actual to result 684 aResult.env.addActual( actual.env, aResult.openVars ); 685 Cost cost = actual.cost; 686 687 // explode argument 688 std::vector<Alternative> exploded; 689 Tuples::explode( actual, indexer, back_inserter( exploded ) ); 690 691 // add exploded argument to tuple 692 for ( Alternative& aActual : exploded ) { 693 aResult.withArg( aActual.expr, cost ); 694 cost = Cost::zero; 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; 695 761 } 696 ++aResult.nextArg; 697 nextResults.push_back( std::move(aResult) ); 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 ); 698 768 } 699 769 } 700 770 701 771 // reset for next round 702 results.swap( nextResults ); 703 nextResults.clear(); 704 } 705 results.swap( finalResults ); 706 return ! results.empty(); 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(); 707 781 } 708 782 709 783 // iterate each current subresult 710 for ( unsigned iResult = 0; iResult < results.size(); ++iResult ) { 711 ArgPack& result = results[iResult]; 712 713 if ( result.nextExpl < result.expls.size() ) { 714 // use remainder of exploded tuple if present 715 const Alternative& actual = result.expls[result.nextExpl]; 716 result.env.addActual( actual.env, result.openVars ); 717 Type* actualType = actual.expr->get_result(); 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(); 718 798 719 799 PRINT( … … 724 804 std::cerr << std::endl; 725 805 ) 726 727 if ( unify( formalType, actualType, result.env, result.need, result.have, 728 result.openVars, indexer ) ) { 729 ++result.nextExpl; 730 nextResults.push_back( std::move(result.withArg( actual.expr )) ); 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 ); 731 816 } 732 817 733 818 continue; 734 } else if ( result.nextArg >= args.size() ) { 735 // use default initializers if out of arguments 819 } 820 821 // use default initializers if out of arguments 822 if ( nextArg >= args.size() ) { 736 823 if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) { 737 824 if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) { 738 if ( unify( formalType, cnst->get_type(), result.env, result.need, 739 result.have, result.openVars, indexer ) ) { 740 nextResults.push_back( std::move(result.withArg( cnstExpr )) ); 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 ); 741 834 } 742 835 } 743 836 } 837 744 838 continue; 745 839 } 746 840 747 841 // Check each possible next argument 748 for ( const Alternative& actual : args[result.nextArg] ) { 749 ArgPack aResult = result; // copy to clone everything 750 // add details of actual to result 751 aResult.env.addActual( actual.env, aResult.openVars ); 752 753 // explode argument 754 std::vector<Alternative> exploded; 755 Tuples::explode( actual, indexer, back_inserter( exploded ) ); 756 if ( exploded.empty() ) { 757 // skip empty tuple arguments 758 ++aResult.nextArg; 759 results.push_back( std::move(aResult) ); 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 760 858 continue; 761 859 } 762 860 763 861 // consider only first exploded actual 764 const Alternative& aActual = exploded.front();765 Type* actualType = aActual.expr->get_result()->clone();862 Expression* expr = expl.exprs.front().get(); 863 Type* actualType = expr->get_result()->clone(); 766 864 767 865 PRINT( … … 774 872 775 873 // attempt to unify types 776 if ( unify( formalType, actualType, aResult.env, aResult.need, aResult.have, aResult.openVars, indexer ) ) { 777 // add argument 778 aResult.withArg( aActual.expr, actual.cost ); 779 ++aResult.nextArg; 780 if ( exploded.size() > 1 ) { 781 // other parts of tuple left over 782 aResult.expls = std::move( exploded ); 783 aResult.nextExpl = 1; 784 } 785 nextResults.push_back( std::move(aResult) ); 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 ); 786 879 } 787 880 } … … 789 882 790 883 // reset for next parameter 791 results.swap( nextResults ); 792 nextResults.clear(); 793 794 return ! results.empty(); 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 ); 795 910 } 796 911 797 912 template<typename OutputIterator> 798 913 void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, 799 FunctionType *funcType, const std::vector< AlternativeFinder > &args, 800 OutputIterator out ) { 914 FunctionType *funcType, const ExplodedArgs &args, OutputIterator out ) { 801 915 OpenVarSet funcOpenVars; 802 916 AssertionSet funcNeed, funcHave; … … 818 932 819 933 // iteratively build matches, one parameter at a time 820 std::vector<ArgPack> results{ ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } }; 821 std::vector<ArgPack> nextResults{}; 934 std::vector<ArgPack> results; 935 results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } ); 936 std::size_t genStart = 0; 937 822 938 for ( DeclarationWithType* formal : funcType->get_parameters() ) { 823 939 ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal ); 824 if ( ! instantiateArgument( 825 obj->get_type(), obj->get_init(), args, results, nextResults, indexer ) )940 if ( ! instantiateArgument( 941 obj->get_type(), obj->get_init(), args, results, genStart, indexer ) ) 826 942 return; 827 943 } 828 944 829 // filter out results that don't use all the arguments, and aren't variadic830 std::vector<ArgPack> finalResults{};831 945 if ( funcType->get_isVarArgs() ) { 832 for ( ArgPack& result : results ) { 833 // use rest of exploded tuple if present 834 while ( result.nextExpl < result.expls.size() ) { 835 const Alternative& actual = result.expls[result.nextExpl]; 836 result.env.addActual( actual.env, result.openVars ); 837 result.withArg( actual.expr ); 838 ++result.nextExpl; 839 } 840 } 841 842 while ( ! results.empty() ) { 843 // build combinations for all remaining arguments 844 for ( ArgPack& result : results ) { 845 // keep if used all arguments 846 if ( result.nextArg >= args.size() ) { 847 finalResults.push_back( std::move(result) ); 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 848 970 continue; 849 971 } 850 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 851 980 // add each possible next argument 852 for ( const Alternative& actual : args[result.nextArg] ) { 853 ArgPack aResult = result; // copy to clone everything 854 // add details of actual to result 855 aResult.env.addActual( actual.env, aResult.openVars ); 856 Cost cost = actual.cost; 857 858 // explode argument 859 std::vector<Alternative> exploded; 860 Tuples::explode( actual, indexer, back_inserter( exploded ) ); 861 862 // add exploded argument to arg list 863 for ( Alternative& aActual : exploded ) { 864 aResult.withArg( aActual.expr, cost ); 865 cost = Cost::zero; 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; 866 997 } 867 ++aResult.nextArg; 868 nextResults.push_back( std::move(aResult) ); 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 ); 869 1004 } 870 1005 } 871 1006 872 // reset for next round 873 results.swap( nextResults ); 874 nextResults.clear(); 875 } 1007 genStart = genEnd; 1008 } while ( genEnd != results.size() ); 876 1009 } else { 877 1010 // filter out results that don't use all the arguments 878 for ( ArgPack& result : results ) { 879 if ( result.nextExpl >= result.expls.size() && result.nextArg >= args.size() ) { 880 finalResults.push_back( std::move(result) ); 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 ); 881 1015 } 882 1016 } 883 }884 885 // validate matching combos, add to final result list886 for ( ArgPack& result : finalResults ) {887 ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() );888 Alternative newAlt( appExpr, result.env, sumCost( result.actuals ) );889 makeExprList( result.actuals, appExpr->get_args() );890 PRINT(891 std::cerr << "instantiate function success: " << appExpr << std::endl;892 std::cerr << "need assertions:" << std::endl;893 printAssertionSet( result.need, std::cerr, 8 );894 )895 inferParameters( result.need, result.have, newAlt, result.openVars, out );896 1017 } 897 1018 } … … 920 1041 printAlts( funcOpFinder.alternatives, std::cerr, 1 ); 921 1042 ) 1043 1044 // pre-explode arguments 1045 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 } 922 1057 923 1058 AltList candidates; … … 934 1069 Alternative newFunc( *func ); 935 1070 referenceToRvalueConversion( newFunc.expr ); 936 makeFunctionAlternatives( newFunc, function, arg Alternatives,1071 makeFunctionAlternatives( newFunc, function, argExpansions, 937 1072 std::back_inserter( candidates ) ); 938 1073 } … … 943 1078 Alternative newFunc( *func ); 944 1079 referenceToRvalueConversion( newFunc.expr ); 945 makeFunctionAlternatives( newFunc, function, arg Alternatives,1080 makeFunctionAlternatives( newFunc, function, argExpansions, 946 1081 std::back_inserter( candidates ) ); 947 1082 } // if … … 955 1090 // try each function operator ?() with each function alternative 956 1091 if ( ! funcOpFinder.alternatives.empty() ) { 957 // add function alternatives to front of argument list 958 argAlternatives.insert( argAlternatives.begin(), std::move(funcFinder) ); 1092 // add exploded function alternatives to front of argument list 1093 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) ); 959 1099 960 1100 for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin(); … … 968 1108 Alternative newFunc( *funcOp ); 969 1109 referenceToRvalueConversion( newFunc.expr ); 970 makeFunctionAlternatives( newFunc, function, arg Alternatives,1110 makeFunctionAlternatives( newFunc, function, argExpansions, 971 1111 std::back_inserter( candidates ) ); 972 1112 } … … 982 1122 983 1123 // compute conversionsion costs 984 for ( Alt List::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc) {985 Cost cvtCost = computeApplicationConversionCost( *withFunc, indexer );1124 for ( Alternative& withFunc : candidates ) { 1125 Cost cvtCost = computeApplicationConversionCost( withFunc, indexer ); 986 1126 987 1127 PRINT( 988 ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc ->expr );1128 ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc.expr ); 989 1129 PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() ); 990 1130 FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() ); … … 995 1135 printAll( appExpr->get_args(), std::cerr, 8 ); 996 1136 std::cerr << "bindings are:" << std::endl; 997 withFunc ->env.print( std::cerr, 8 );1137 withFunc.env.print( std::cerr, 8 ); 998 1138 std::cerr << "cost of conversion is:" << cvtCost << std::endl; 999 1139 ) 1000 1140 if ( cvtCost != Cost::infinity ) { 1001 withFunc ->cvtCost = cvtCost;1002 alternatives.push_back( *withFunc );1141 withFunc.cvtCost = cvtCost; 1142 alternatives.push_back( withFunc ); 1003 1143 } // if 1004 1144 } // for 1005 1145 1006 candidates.clear(); 1007 candidates.splice( candidates.end(), alternatives ); 1146 candidates = move(alternatives); 1008 1147 1009 1148 // use a new list so that alternatives are not examined by addAnonConversions twice. … … 1011 1150 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) ); 1012 1151 1013 // function may return struct or union value, in which case we need to add alternatives for implicit1014 // conversions to each of the anonymous members, must happen after findMinCost since anon conversions1015 // are never the cheapest expression1152 // 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 1016 1155 for ( const Alternative & alt : winners ) { 1017 1156 addAnonConversions( alt ); 1018 1157 } 1019 alternatives.splice( alternatives.begin(), winners );1158 spliceBegin( alternatives, winners ); 1020 1159 1021 1160 if ( alternatives.empty() && targetType && ! targetType->isVoid() ) { … … 1041 1180 AlternativeFinder finder( indexer, env ); 1042 1181 finder.find( addressExpr->get_arg() ); 1043 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) { 1044 if ( isLvalue( i->expr ) ) { 1045 alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) ); 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 } ); 1046 1186 } // if 1047 1187 } // for … … 1049 1189 1050 1190 void AlternativeFinder::visit( LabelAddressExpr * expr ) { 1051 alternatives.push_back( Alternative ( expr->clone(), env, Cost::zero));1191 alternatives.push_back( Alternative{ expr->clone(), env, Cost::zero } ); 1052 1192 } 1053 1193 … … 1091 1231 1092 1232 AltList candidates; 1093 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i) {1233 for ( Alternative& alt : finder.alternatives ) { 1094 1234 AssertionSet needAssertions, haveAssertions; 1095 1235 OpenVarSet openVars; … … 1099 1239 // that are cast directly. The candidate is invalid if it has fewer results than there are types to cast 1100 1240 // to. 1101 int discardedValues = i->expr->get_result()->size() - castExpr->get_result()->size();1241 int discardedValues = alt.expr->get_result()->size() - castExpr->get_result()->size(); 1102 1242 if ( discardedValues < 0 ) continue; 1103 1243 // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not 1104 1244 // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3])) 1105 1245 // unification run for side-effects 1106 unify( castExpr->get_result(), i->expr->get_result(), i->env, needAssertions, haveAssertions, openVars, indexer ); 1107 Cost thisCost = castCost( i->expr->get_result(), castExpr->get_result(), indexer, i->env ); 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 ); 1108 1250 if ( thisCost != Cost::infinity ) { 1109 1251 // count one safe conversion for each value that is thrown away 1110 1252 thisCost.incSafe( discardedValues ); 1111 Alternative newAlt( restructureCast( i->expr->clone(), toType ), i->env, i->cost, thisCost ); 1112 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) ); 1253 Alternative newAlt( restructureCast( alt.expr->clone(), toType ), alt.env, 1254 alt.cost, thisCost ); 1255 inferParameters( needAssertions, haveAssertions, newAlt, openVars, 1256 back_inserter( candidates ) ); 1113 1257 } // if 1114 1258 } // for … … 1397 1541 1398 1542 void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) { 1399 std::list< AlternativeFinder > subExprAlternatives; 1400 findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) ); 1401 std::list< AltList > possibilities; 1402 combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) ); 1403 for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) { 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 ) { 1404 1550 std::list< Expression * > exprs; 1405 makeExprList( *i, exprs );1551 makeExprList( alts, exprs ); 1406 1552 1407 1553 TypeEnvironment compositeEnv; 1408 simpleCombineEnvironments( i->begin(), i->end(), compositeEnv ); 1409 alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) ); 1554 simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv ); 1555 alternatives.push_back( 1556 Alternative{ new TupleExpr( exprs ), compositeEnv, sumCost( alts ) } ); 1410 1557 } // for 1411 1558 }
Note: See TracChangeset
for help on using the changeset viewer.