Changeset 403b388
- Timestamp:
- Nov 20, 2017, 2:07:19 PM (7 years ago)
- Branches:
- ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
- Children:
- a94b829
- Parents:
- 6d2386e
- Location:
- src/ResolvExpr
- Files:
-
- 2 edited
-
AlternativeFinder.cc (modified) (9 diffs)
-
AlternativeFinder.h (modified) (2 diffs)
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/AlternativeFinder.cc
r6d2386e r403b388 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 … … 50 51 #define PRINT( text ) if ( resolvep ) { text } 51 52 //#define DEBUG_COST 53 54 using std::move; 55 56 /// copies any copyable type 57 template<typename T> 58 T copy(const T& x) { return x; } 52 59 53 60 namespace ResolvExpr { … … 571 578 /// State to iteratively build a match of parameter expressions to arguments 572 579 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 580 std::size_t parent; ///< Index of parent pack 581 std::unique_ptr<Expression> expr; ///< The argument stored here 582 Cost cost; ///< The cost of this argument 583 TypeEnvironment env; ///< Environment for this pack 584 AssertionSet need; ///< Assertions outstanding for this pack 585 AssertionSet have; ///< Assertions found for this pack 586 OpenVarSet openVars; ///< Open variables for this pack 587 unsigned nextArg; ///< Index of next argument in arguments list 588 unsigned tupleStart; ///< Number of tuples that start at this index 589 // TODO fix this somehow 590 std::vector<Alternative> expls; ///< Exploded actuals left over from last match 591 592 ArgPack() 593 : parent(0), expr(), cost(Cost::zero), env(), need(), have(), openVars(), nextArg(0), 594 tupleStart(0), expls() {} 595 583 596 ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have, 584 597 const OpenVarSet& openVars) 585 : actuals(), env(env), need(need), have(have), openVars(openVars), nextArg(0),586 expls(), nextExpl(0), tupleEls() {}598 : parent(0), expr(), cost(Cost::zero), env(env), need(need), have(have), 599 openVars(openVars), nextArg(0), tupleStart(0), expls() {} 587 600 588 /// Starts a new tuple expression 589 void beginTuple() { 590 if ( ! tupleEls.empty() ) ++tupleEls.back(); 591 tupleEls.push_back(0); 592 } 593 601 ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need, 602 AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg, 603 unsigned tupleStart = 0, Cost cost = Cost::zero, 604 std::vector<Alternative>&& expls = std::vector<Alternative>{} ) 605 : parent(parent), expr(expr->clone()), cost(cost), env(move(env)), need(move(need)), 606 have(move(have)), openVars(move(openVars)), nextArg(nextArg), tupleStart(tupleStart), 607 expls(move(expls)) {} 608 609 // ArgPack(const ArgPack& o) 610 // : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), env(o.env), 611 // need(o.need), have(o.have), openVars(o.openVars), nextArg(o.nextArg), 612 // tupleStart(o.tupleStart), expls(o.expls) {} 613 614 // ArgPack(ArgPack&&) = default; 615 594 616 /// Ends a tuple expression, consolidating the appropriate actuals 595 void endTuple( ) {596 // set up new Tuple alternative617 void endTuple( const std::vector<ArgPack>& packs ) { 618 // add all expressions in tuple to list, summing cost 597 619 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; 620 const ArgPack* pack = this; 621 if ( expr ) { exprs.push_front( expr.release() ); } 622 while ( pack->tupleStart == 0 ) { 623 pack = &packs[pack->parent]; 624 exprs.push_front( pack->expr->clone() ); 625 cost += pack->cost; 626 } 627 // reset pack to appropriate tuple 628 expr.reset( new TupleExpr( exprs ) ); 629 tupleStart = pack->tupleStart - 1; 630 parent = pack->parent; 618 631 } 619 632 }; … … 621 634 /// Instantiates an argument to match a formal, returns false if no results left 622 635 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 ) { 636 const std::vector< AlternativeFinder >& args, std::vector<ArgPack>& results, 637 std::size_t& genStart, const SymTab::Indexer& indexer, unsigned nTuples = 0 ) { 626 638 if ( TupleType* tupleType = dynamic_cast<TupleType*>( formalType ) ) { 627 639 // formalType is a TupleType - group actuals into a TupleExpr 628 for ( ArgPack& result : results ) { result.beginTuple(); }640 ++nTuples; 629 641 for ( Type* type : *tupleType ) { 630 642 // xxx - dropping initializer changes behaviour from previous, but seems correct 631 if ( ! instantiateArgument( type, nullptr, args, results, nextResults, indexer ) ) 643 if ( ! instantiateArgument( 644 type, nullptr, args, results, genStart, indexer, nTuples ) ) 632 645 return false; 633 } 634 for ( ArgPack& result : results ) { result.endTuple(); } 646 nTuples = 0; 647 } 648 // re-consititute tuples for final generation 649 for ( auto i = genStart; i < results.size(); ++i ) { 650 results[i].endTuple( results ); 651 } 635 652 return true; 636 653 } else if ( TypeInstType* ttype = Tuples::isTtype( formalType ) ) { 637 654 // formalType is a ttype, consumes all remaining arguments 638 655 // 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 } 656 657 // completed tuples; will be spliced to end of results to finish 658 std::vector<ArgPack> finalResults{}; 659 652 660 // iterate until all results completed 653 while ( ! results.empty() ) { 661 std::size_t genEnd; 662 ++nTuples; 663 do { 664 genEnd = results.size(); 665 654 666 // 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(); 671 } 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 } 667 for ( std::size_t i = genStart; i < genEnd; ++i ) { 668 // use remainder of exploded tuple if present 669 if ( ! results[i].expls.empty() ) { 670 const Alternative& actual = results[i].expls.front(); 671 672 TypeEnvironment env = results[i].env; 673 OpenVarSet openVars = results[i].openVars; 674 675 env.addActual( actual.env, openVars ); 676 677 std::vector<Alternative> newExpls( 678 std::next( results[i].expls.begin() ), results[i].expls.end() ); 679 results.emplace_back( 680 i, actual.expr, move(env), copy(results[i].need), 681 copy(results[i].have), move(openVars), results[i].nextArg, nTuples, 682 Cost::zero, move(newExpls) ); 683 677 684 continue; 678 685 } 686 687 // finish result when out of arguments 688 if ( results[i].nextArg >= args.size() ) { 689 ArgPack newResult{ 690 results[i].env, results[i].need, results[i].have, 691 results[i].openVars }; 692 newResult.nextArg = results[i].nextArg; 693 Type* argType; 694 695 if ( nTuples > 0 ) { 696 // first iteration, push empty tuple expression 697 newResult.parent = i; 698 std::list<Expression*> emptyList; 699 newResult.expr.reset( new TupleExpr( emptyList ) ); 700 argType = newResult.expr->get_result(); 701 } else { 702 // clone result to collect tuple 703 newResult.parent = results[i].parent; 704 newResult.cost = results[i].cost; 705 newResult.tupleStart = results[i].tupleStart; 706 newResult.expr.reset( results[i].expr->clone() ); 707 argType = newResult.expr->get_result(); 708 709 if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) { 710 // the case where a ttype value is passed directly is special, 711 // e.g. for argument forwarding purposes 712 // xxx - what if passing multiple arguments, last of which is 713 // ttype? 714 // xxx - what would happen if unify was changed so that unifying 715 // tuple 716 // types flattened both before unifying lists? then pass in 717 // TupleType (ttype) below. 718 --newResult.tupleStart; 719 } else { 720 // collapse leftover arguments into tuple 721 newResult.endTuple( results ); 722 argType = newResult.expr->get_result(); 723 } 724 } 725 726 // check unification for ttype before adding to final 727 if ( unify( ttype, argType, newResult.env, newResult.need, newResult.have, 728 newResult.openVars, indexer ) ) { 729 finalResults.push_back( move(newResult) ); 730 } 731 732 continue; 733 } 679 734 680 735 // 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 736 auto j = results[i].nextArg; 737 for ( const Alternative& actual : args[j] ) { 738 // fresh copies of parent parameters for this iteration 739 TypeEnvironment env = results[i].env; 740 OpenVarSet openVars = results[i].openVars; 741 742 env.addActual( actual.env, openVars ); 743 687 744 // explode argument 688 745 std::vector<Alternative> exploded; 689 746 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; 747 if ( exploded.empty() ) { 748 // skip empty tuple arguments by (near-)cloning parent into next gen 749 results.emplace_back( 750 results[i].parent, results[i].expr.get(), move(env), 751 copy(results[i].need), copy(results[i].have), move(openVars), 752 j + 1, results[i].tupleStart, actual.cost + results[i].cost ); 753 continue; 695 754 } 696 ++aResult.nextArg; 697 nextResults.push_back( std::move(aResult) ); 755 756 // trim first element from exploded 757 std::vector<Alternative> newExpls; 758 newExpls.reserve( exploded.size() - 1 ); 759 for ( std::size_t i = 1; i < exploded.size(); ++i ) { 760 newExpls.push_back( move(exploded[i]) ); 761 } 762 // add new result 763 results.emplace_back( 764 i, actual.expr, move(env), copy(results[i].need), 765 copy(results[i].have), move(openVars), results[i].nextArg + 1, 766 nTuples, actual.cost, move(newExpls) ); 698 767 } 699 768 } 700 769 701 770 // reset for next round 702 results.swap( nextResults ); 703 nextResults.clear(); 704 } 705 results.swap( finalResults ); 706 return ! results.empty(); 771 genStart = genEnd; 772 nTuples = 0; 773 } while ( genEnd != results.size() ); 774 775 // splice final results onto results 776 for ( std::size_t i = 0; i < finalResults.size(); ++i ) { 777 results.push_back( move(finalResults[i]) ); 778 } 779 return ! finalResults.empty(); 707 780 } 708 781 709 782 // 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 ); 783 std::size_t genEnd = results.size(); 784 for ( std::size_t i = genStart; i < genEnd; ++i ) { 785 // use remainder of exploded tuple if present 786 if ( ! results[i].expls.empty() ) { 787 const Alternative& actual = results[i].expls.front(); 788 789 TypeEnvironment env = results[i].env; 790 AssertionSet need = results[i].need, have = results[i].have; 791 OpenVarSet openVars = results[i].openVars; 792 793 env.addActual( actual.env, openVars ); 717 794 Type* actualType = actual.expr->get_result(); 718 795 … … 725 802 ) 726 803 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 )) ); 804 if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) { 805 std::vector<Alternative> newExpls( 806 std::next( results[i].expls.begin() ), results[i].expls.end() ); 807 results.emplace_back( 808 i, actual.expr, move(env), move(need), move(have), move(openVars), 809 results[i].nextArg, nTuples, Cost::zero, move(newExpls) );; 731 810 } 732 811 733 812 continue; 734 } else if ( result.nextArg >= args.size() ) { 735 // use default initializers if out of arguments 813 } 814 815 // use default initializers if out of arguments 816 if ( results[i].nextArg >= args.size() ) { 736 817 if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) { 737 818 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 )) ); 819 TypeEnvironment env = results[i].env; 820 AssertionSet need = results[i].need, have = results[i].have; 821 OpenVarSet openVars = results[i].openVars; 822 823 if ( unify( formalType, cnst->get_type(), env, need, have, openVars, 824 indexer ) ) { 825 results.emplace_back( 826 i, cnstExpr, move(env), move(need), move(have), 827 move(openVars), results[i].nextArg, nTuples ); 741 828 } 742 829 } 743 830 } 831 744 832 continue; 745 833 } 746 834 747 835 // 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 836 auto j = results[i].nextArg; 837 for ( const Alternative& actual : args[j] ) { 838 // fresh copies of parent parameters for this iteration 839 TypeEnvironment env = results[i].env; 840 AssertionSet need = results[i].need, have = results[i].have; 841 OpenVarSet openVars = results[i].openVars; 842 843 env.addActual( actual.env, openVars ); 844 753 845 // explode argument 754 846 std::vector<Alternative> exploded; 755 847 Tuples::explode( actual, indexer, back_inserter( exploded ) ); 756 848 if ( exploded.empty() ) { 757 // skip empty tuple arguments 758 ++aResult.nextArg; 759 results.push_back( std::move(aResult) ); 849 // skip empty tuple arguments by (near-)cloning parent into next gen 850 results.emplace_back( 851 results[i].parent, results[i].expr.get(), move(env), move(need), 852 move(have), move(openVars), j + 1, results[i].tupleStart, 853 actual.cost + results[i].cost ); 760 854 continue; 761 855 } … … 774 868 775 869 // 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; 870 if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) { 871 // trim first element from exploded 872 std::vector<Alternative> newExpls; 873 newExpls.reserve( exploded.size() - 1 ); 874 for ( std::size_t i = 1; i < exploded.size(); ++i ) { 875 newExpls.push_back( move(exploded[i]) ); 784 876 } 785 nextResults.push_back( std::move(aResult) ); 877 // add new result 878 results.emplace_back( 879 i, aActual.expr, move(env), move(need), move(have), move(openVars), 880 j + 1, nTuples, actual.cost, move(newExpls) ); 786 881 } 787 882 } … … 789 884 790 885 // reset for next parameter 791 results.swap( nextResults ); 792 nextResults.clear(); 886 genStart = genEnd; 793 887 794 return ! results.empty(); 795 } 888 return genEnd != results.size(); 889 } 890 891 template<typename OutputIterator> 892 void AlternativeFinder::validateFunctionAlternative( const Alternative &func, ArgPack& result, 893 const std::vector<ArgPack>& results, OutputIterator out ) { 894 ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() ); 895 // sum cost and accumulate actuals 896 std::list<Expression*>& args = appExpr->get_args(); 897 Cost cost = Cost::zero; 898 const ArgPack* pack = &result; 899 while ( pack->expr ) { 900 args.push_front( pack->expr->clone() ); 901 cost += pack->cost; 902 pack = &results[pack->parent]; 903 } 904 // build and validate new alternative 905 Alternative newAlt( appExpr, result.env, cost ); 906 PRINT( 907 std::cerr << "instantiate function success: " << appExpr << std::endl; 908 std::cerr << "need assertions:" << std::endl; 909 printAssertionSet( result.need, std::cerr, 8 ); 910 ) 911 inferParameters( result.need, result.have, newAlt, result.openVars, out ); 912 } 796 913 797 914 template<typename OutputIterator> … … 818 935 819 936 // iteratively build matches, one parameter at a time 820 std::vector<ArgPack> results{ ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } }; 821 std::vector<ArgPack> nextResults{}; 937 std::vector<ArgPack> results; 938 results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } ); 939 std::size_t genStart = 0; 940 822 941 for ( DeclarationWithType* formal : funcType->get_parameters() ) { 823 942 ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal ); 824 943 if ( ! instantiateArgument( 825 obj->get_type(), obj->get_init(), args, results, nextResults, indexer ) )944 obj->get_type(), obj->get_init(), args, results, genStart, indexer ) ) 826 945 return; 827 946 } 828 947 829 // filter out results that don't use all the arguments, and aren't variadic830 std::vector<ArgPack> finalResults{};831 948 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) ); 949 // append any unused arguments to vararg pack 950 std::size_t genEnd; 951 do { 952 genEnd = results.size(); 953 954 // iterate results 955 for ( std::size_t i = genStart; i < genEnd; ++i ) { 956 // use remainder of exploded tuple if present 957 if ( ! results[i].expls.empty() ) { 958 const Alternative& actual = results[i].expls.front(); 959 960 TypeEnvironment env = results[i].env; 961 OpenVarSet openVars = results[i].openVars; 962 963 env.addActual( actual.env, openVars ); 964 965 std::vector<Alternative> newExpls( 966 std::next( results[i].expls.begin() ), results[i].expls.end() ); 967 results.emplace_back( 968 i, actual.expr, move(env), copy(results[i].need), 969 copy(results[i].have), move(openVars), results[i].nextArg, 0, 970 Cost::zero, move(newExpls) ); 971 848 972 continue; 849 973 } 850 974 975 // finish result when out of arguments 976 if ( results[i].nextArg >= args.size() ) { 977 validateFunctionAlternative( func, results[i], results, out ); 978 979 continue; 980 } 981 851 982 // 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; 983 auto j = results[i].nextArg; 984 for ( const Alternative& actual : args[j] ) { 985 // fresh copies of parent parameters for this iteration 986 TypeEnvironment env = results[i].env; 987 OpenVarSet openVars = results[i].openVars; 988 989 env.addActual( actual.env, openVars ); 857 990 858 991 // explode argument 859 992 std::vector<Alternative> exploded; 860 993 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; 994 if ( exploded.empty() ) { 995 // skip empty tuple arguments by (near-)cloning parent into next gen 996 results.emplace_back( 997 results[i].parent, results[i].expr.get(), move(env), 998 copy(results[i].need), copy(results[i].have), move(openVars), 999 j + 1, results[i].tupleStart, actual.cost + results[i].cost ); 1000 continue; 866 1001 } 867 ++aResult.nextArg; 868 nextResults.push_back( std::move(aResult) ); 1002 1003 // trim first element from exploded 1004 std::vector<Alternative> newExpls; 1005 newExpls.reserve( exploded.size() - 1 ); 1006 for ( std::size_t i = 1; i < exploded.size(); ++i ) { 1007 newExpls.push_back( move(exploded[i]) ); 1008 } 1009 // add new result 1010 results.emplace_back( 1011 i, actual.expr, move(env), copy(results[i].need), 1012 copy(results[i].have), move(openVars), j + 1, 0, 1013 actual.cost, move(newExpls) ); 869 1014 } 870 1015 } 871 1016 872 // reset for next round 873 results.swap( nextResults ); 874 nextResults.clear(); 875 } 1017 genStart = genEnd; 1018 } while ( genEnd != results.size() ); 876 1019 } else { 877 1020 // 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) ); 1021 for ( std::size_t i = genStart; i < results.size(); ++i ) { 1022 ArgPack& result = results[i]; 1023 if ( result.expls.empty() && result.nextArg >= args.size() ) { 1024 validateFunctionAlternative( func, result, results, out ); 881 1025 } 882 1026 } 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 1027 } 897 1028 } … … 956 1087 if ( ! funcOpFinder.alternatives.empty() ) { 957 1088 // add function alternatives to front of argument list 958 argAlternatives.insert( argAlternatives.begin(), std::move(funcFinder) );1089 argAlternatives.insert( argAlternatives.begin(), move(funcFinder) ); 959 1090 960 1091 for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin(); -
src/ResolvExpr/AlternativeFinder.h
r6d2386e r403b388 31 31 32 32 namespace ResolvExpr { 33 class ArgPack; 34 33 35 class AlternativeFinder : public Visitor { 34 36 public: … … 126 128 /// Adds alternatives for offsetof expressions, given the base type and name of the member 127 129 template< typename StructOrUnionType > void addOffsetof( StructOrUnionType *aggInst, const std::string &name ); 130 /// Takes a final result and checks if its assertions can be satisfied 131 template<typename OutputIterator> 132 void validateFunctionAlternative( const Alternative &func, ArgPack& result, const std::vector<ArgPack>& results, OutputIterator out ); 133 /// Finds matching alternatives for a function, given a set of arguments 128 134 template<typename OutputIterator> 129 135 void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const std::vector< AlternativeFinder >& args, OutputIterator out ); 136 /// Checks if assertion parameters match for a new alternative 130 137 template< typename OutputIterator > 131 138 void inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out );
Note: See TracChangeset
for help on using the changeset viewer.
