- File:
-
- 1 edited
-
src/ResolvExpr/AlternativeFinder.cc (modified) (21 diffs)
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/AlternativeFinder.cc
r83882e9 r11094d9 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 24 #include <vector> // for vector … … 52 51 //#define DEBUG_COST 53 52 54 using std::move;55 56 /// copies any copyable type57 template<typename T>58 T copy(const T& x) { return x; }59 60 53 namespace ResolvExpr { 61 54 Expression *resolveInVoidContext( Expression *expr, const SymTab::Indexer &indexer, TypeEnvironment &env ) { … … 186 179 expr->accept( *this ); 187 180 if ( failFast && alternatives.empty() ) { 188 PRINT(189 std::cerr << "No reasonable alternatives for expression " << expr << std::endl;190 )191 181 throw SemanticError( "No reasonable alternatives for expression ", expr ); 192 182 } … … 197 187 printAlts( alternatives, std::cerr ); 198 188 ) 199 AltList pruned;200 pruneAlternatives( alternatives.begin(), alternatives.end(), back_inserter( pruned) );201 if ( failFast && pruned.empty()) {189 AltList::iterator oldBegin = alternatives.begin(); 190 pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives ) ); 191 if ( failFast && alternatives.begin() == oldBegin ) { 202 192 std::ostringstream stream; 203 193 AltList winners; … … 209 199 throw SemanticError( stream.str() ); 210 200 } 211 alternatives = move(pruned);201 alternatives.erase( oldBegin, alternatives.end() ); 212 202 PRINT( 213 203 std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl; … … 581 571 /// State to iteratively build a match of parameter expressions to arguments 582 572 struct ArgPack { 583 std::size_t parent; ///< Index of parent pack 584 std::unique_ptr<Expression> expr; ///< The argument stored here 585 Cost cost; ///< The cost of this argument 586 TypeEnvironment env; ///< Environment for this pack 587 AssertionSet need; ///< Assertions outstanding for this pack 588 AssertionSet have; ///< Assertions found for this pack 589 OpenVarSet openVars; ///< Open variables for this pack 590 unsigned nextArg; ///< Index of next argument in arguments list 591 unsigned tupleStart; ///< Number of tuples that start at this index 592 // TODO fix this somehow 593 std::vector<Alternative> expls; ///< Exploded actuals left over from last match 594 595 ArgPack() 596 : parent(0), expr(), cost(Cost::zero), env(), need(), have(), openVars(), nextArg(0), 597 tupleStart(0), expls() {} 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) 598 582 599 583 ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have, 600 584 const OpenVarSet& openVars) 601 : parent(0), expr(), cost(Cost::zero), env(env), need(need), have(have), 602 openVars(openVars), nextArg(0), tupleStart(0), expls() {} 603 604 ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need, 605 AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg, 606 unsigned tupleStart = 0, Cost cost = Cost::zero, 607 std::vector<Alternative>&& expls = std::vector<Alternative>{} ) 608 : parent(parent), expr(expr->clone()), cost(cost), env(move(env)), need(move(need)), 609 have(move(have)), openVars(move(openVars)), nextArg(nextArg), tupleStart(tupleStart), 610 expls(move(expls)) {} 611 612 ArgPack(const ArgPack& o, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have, 613 OpenVarSet&& openVars, unsigned nextArg, Cost added ) 614 : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), cost(o.cost + added), 615 env(move(env)), need(move(need)), have(move(have)), openVars(move(openVars)), 616 nextArg(nextArg), tupleStart(o.tupleStart), expls() {} 617 618 619 // ArgPack(const ArgPack& o) 620 // : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), env(o.env), 621 // need(o.need), have(o.have), openVars(o.openVars), nextArg(o.nextArg), 622 // tupleStart(o.tupleStart), expls(o.expls) {} 623 624 // ArgPack(ArgPack&&) = default; 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 } 625 593 626 594 /// Ends a tuple expression, consolidating the appropriate actuals 627 void endTuple( const std::vector<ArgPack>& packs) {628 // add all expressions in tuple to list, summing cost595 void endTuple() { 596 // set up new Tuple alternative 629 597 std::list<Expression*> exprs; 630 const ArgPack* pack = this; 631 if ( expr ) { exprs.push_front( expr.release() ); } 632 while ( pack->tupleStart == 0 ) { 633 pack = &packs[pack->parent]; 634 exprs.push_front( pack->expr->clone() ); 635 cost += pack->cost; 636 } 637 // reset pack to appropriate tuple 638 expr.reset( new TupleExpr( exprs ) ); 639 tupleStart = pack->tupleStart - 1; 640 parent = pack->parent; 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; 641 618 } 642 619 }; … … 644 621 /// Instantiates an argument to match a formal, returns false if no results left 645 622 bool instantiateArgument( Type* formalType, Initializer* initializer, 646 const std::vector< AlternativeFinder >& args, std::vector<ArgPack>& results, 647 std::size_t& genStart, const SymTab::Indexer& indexer, unsigned nTuples = 0 ) { 623 const std::vector< AlternativeFinder >& args, 624 std::vector<ArgPack>& results, std::vector<ArgPack>& nextResults, 625 const SymTab::Indexer& indexer ) { 648 626 if ( TupleType* tupleType = dynamic_cast<TupleType*>( formalType ) ) { 649 627 // formalType is a TupleType - group actuals into a TupleExpr 650 ++nTuples;628 for ( ArgPack& result : results ) { result.beginTuple(); } 651 629 for ( Type* type : *tupleType ) { 652 630 // xxx - dropping initializer changes behaviour from previous, but seems correct 653 if ( ! instantiateArgument( 654 type, nullptr, args, results, genStart, indexer, nTuples ) ) 631 if ( ! instantiateArgument( type, nullptr, args, results, nextResults, indexer ) ) 655 632 return false; 656 nTuples = 0; 657 } 658 // re-consititute tuples for final generation 659 for ( auto i = genStart; i < results.size(); ++i ) { 660 results[i].endTuple( results ); 661 } 633 } 634 for ( ArgPack& result : results ) { result.endTuple(); } 662 635 return true; 663 636 } else if ( TypeInstType* ttype = Tuples::isTtype( formalType ) ) { 664 637 // formalType is a ttype, consumes all remaining arguments 665 638 // xxx - mixing default arguments with variadic?? 666 667 // completed tuples; will be spliced to end of results to finish 668 std::vector<ArgPack> finalResults{}; 669 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 } 670 652 // iterate until all results completed 671 std::size_t genEnd; 672 ++nTuples; 673 do { 674 genEnd = results.size(); 675 653 while ( ! results.empty() ) { 676 654 // add another argument to results 677 for ( std::size_t i = genStart; i < genEnd; ++i ) { 678 // use remainder of exploded tuple if present 679 if ( ! results[i].expls.empty() ) { 680 const Alternative& actual = results[i].expls.front(); 681 682 TypeEnvironment env = results[i].env; 683 OpenVarSet openVars = results[i].openVars; 684 685 env.addActual( actual.env, openVars ); 686 687 std::vector<Alternative> newExpls( 688 std::next( results[i].expls.begin() ), results[i].expls.end() ); 689 results.emplace_back( 690 i, actual.expr, move(env), copy(results[i].need), 691 copy(results[i].have), move(openVars), results[i].nextArg, nTuples, 692 Cost::zero, move(newExpls) ); 693 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 } 694 677 continue; 695 678 } 696 679 697 // finish result when out of arguments698 if ( results[i].nextArg >= args.size() ) {699 ArgPack newResult{700 results[i].env, results[i].need, results[i].have,701 results[i].openVars };702 newResult.nextArg = results[i].nextArg;703 Type* argType;704 705 if ( nTuples > 0 ) {706 // first iteration, push empty tuple expression707 newResult.parent = i;708 std::list<Expression*> emptyList;709 newResult.expr.reset( new TupleExpr( emptyList ) );710 argType = newResult.expr->get_result();711 } else {712 // clone result to collect tuple713 newResult.parent = results[i].parent;714 newResult.cost = results[i].cost;715 newResult.tupleStart = results[i].tupleStart;716 newResult.expr.reset( results[i].expr->clone() );717 argType = newResult.expr->get_result();718 719 if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {720 // the case where a ttype value is passed directly is special,721 // e.g. for argument forwarding purposes722 // xxx - what if passing multiple arguments, last of which is723 // ttype?724 // xxx - what would happen if unify was changed so that unifying725 // tuple726 // types flattened both before unifying lists? then pass in727 // TupleType (ttype) below.728 --newResult.tupleStart;729 } else {730 // collapse leftover arguments into tuple731 newResult.endTuple( results );732 argType = newResult.expr->get_result();733 }734 }735 736 // check unification for ttype before adding to final737 if ( unify( ttype, argType, newResult.env, newResult.need, newResult.have,738 newResult.openVars, indexer ) ) {739 finalResults.push_back( move(newResult) );740 }741 742 continue;743 }744 745 680 // add each possible next argument 746 auto j = results[i].nextArg; 747 for ( const Alternative& actual : args[j] ) { 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( actual.env, openVars ); 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; 753 686 754 687 // explode argument 755 688 std::vector<Alternative> exploded; 756 689 Tuples::explode( actual, indexer, back_inserter( exploded ) ); 757 if ( exploded.empty() ) { 758 // skip empty tuple arguments by (near-)cloning parent into next gen 759 results.emplace_back( 760 results[i], move(env), copy(results[i].need), 761 copy(results[i].have), move(openVars), j + 1, actual.cost ); 762 763 continue; 690 691 // add exploded argument to tuple 692 for ( Alternative& aActual : exploded ) { 693 aResult.withArg( aActual.expr, cost ); 694 cost = Cost::zero; 764 695 } 765 766 // trim first element from exploded 767 std::vector<Alternative> newExpls; 768 newExpls.reserve( exploded.size() - 1 ); 769 for ( std::size_t i = 1; i < exploded.size(); ++i ) { 770 newExpls.push_back( move(exploded[i]) ); 771 } 772 // add new result 773 results.emplace_back( 774 i, exploded.front().expr, move(env), copy(results[i].need), 775 copy(results[i].have), move(openVars), results[i].nextArg + 1, 776 nTuples, actual.cost, move(newExpls) ); 696 ++aResult.nextArg; 697 nextResults.push_back( std::move(aResult) ); 777 698 } 778 699 } 779 700 780 701 // reset for next round 781 genStart = genEnd; 782 nTuples = 0; 783 } while ( genEnd != results.size() ); 784 785 // splice final results onto results 786 for ( std::size_t i = 0; i < finalResults.size(); ++i ) { 787 results.push_back( move(finalResults[i]) ); 788 } 789 return ! finalResults.empty(); 702 results.swap( nextResults ); 703 nextResults.clear(); 704 } 705 results.swap( finalResults ); 706 return ! results.empty(); 790 707 } 791 708 792 709 // iterate each current subresult 793 std::size_t genEnd = results.size(); 794 for ( std::size_t i = genStart; i < genEnd; ++i ) { 795 // use remainder of exploded tuple if present 796 if ( ! results[i].expls.empty() ) { 797 const Alternative& actual = results[i].expls.front(); 798 799 TypeEnvironment env = results[i].env; 800 AssertionSet need = results[i].need, have = results[i].have; 801 OpenVarSet openVars = results[i].openVars; 802 803 env.addActual( actual.env, openVars ); 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 ); 804 717 Type* actualType = actual.expr->get_result(); 805 718 … … 812 725 ) 813 726 814 if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) { 815 std::vector<Alternative> newExpls( 816 std::next( results[i].expls.begin() ), results[i].expls.end() ); 817 results.emplace_back( 818 i, actual.expr, move(env), move(need), move(have), move(openVars), 819 results[i].nextArg, nTuples, Cost::zero, move(newExpls) );; 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 )) ); 820 731 } 821 732 822 733 continue; 823 } 824 825 // use default initializers if out of arguments 826 if ( results[i].nextArg >= args.size() ) { 734 } else if ( result.nextArg >= args.size() ) { 735 // use default initializers if out of arguments 827 736 if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) { 828 737 if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) { 829 TypeEnvironment env = results[i].env; 830 AssertionSet need = results[i].need, have = results[i].have; 831 OpenVarSet openVars = results[i].openVars; 832 833 if ( unify( formalType, cnst->get_type(), env, need, have, openVars, 834 indexer ) ) { 835 results.emplace_back( 836 i, cnstExpr, move(env), move(need), move(have), 837 move(openVars), results[i].nextArg, nTuples ); 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 )) ); 838 741 } 839 742 } 840 743 } 841 842 744 continue; 843 745 } 844 746 845 747 // Check each possible next argument 846 auto j = results[i].nextArg; 847 for ( const Alternative& actual : args[j] ) { 848 // fresh copies of parent parameters for this iteration 849 TypeEnvironment env = results[i].env; 850 AssertionSet need = results[i].need, have = results[i].have; 851 OpenVarSet openVars = results[i].openVars; 852 853 env.addActual( actual.env, openVars ); 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 ); 854 752 855 753 // explode argument … … 857 755 Tuples::explode( actual, indexer, back_inserter( exploded ) ); 858 756 if ( exploded.empty() ) { 859 // skip empty tuple arguments by (near-)cloning parent into next gen 860 results.emplace_back( 861 results[i], move(env), move(need), move(have), move(openVars), j + 1, 862 actual.cost ); 863 757 // skip empty tuple arguments 758 ++aResult.nextArg; 759 results.push_back( std::move(aResult) ); 864 760 continue; 865 761 } … … 878 774 879 775 // attempt to unify types 880 if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) { 881 // trim first element from exploded 882 std::vector<Alternative> newExpls; 883 newExpls.reserve( exploded.size() - 1 ); 884 for ( std::size_t i = 1; i < exploded.size(); ++i ) { 885 newExpls.push_back( move(exploded[i]) ); 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; 886 784 } 887 // add new result 888 results.emplace_back( 889 i, aActual.expr, move(env), move(need), move(have), move(openVars), 890 j + 1, nTuples, actual.cost, move(newExpls) ); 785 nextResults.push_back( std::move(aResult) ); 891 786 } 892 787 } … … 894 789 895 790 // reset for next parameter 896 genStart = genEnd; 897 898 return genEnd != results.size(); 899 } 900 901 template<typename OutputIterator> 902 void AlternativeFinder::validateFunctionAlternative( const Alternative &func, ArgPack& result, 903 const std::vector<ArgPack>& results, OutputIterator out ) { 904 ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() ); 905 // sum cost and accumulate actuals 906 std::list<Expression*>& args = appExpr->get_args(); 907 Cost cost = Cost::zero; 908 const ArgPack* pack = &result; 909 while ( pack->expr ) { 910 args.push_front( pack->expr->clone() ); 911 cost += pack->cost; 912 pack = &results[pack->parent]; 913 } 914 // build and validate new alternative 915 Alternative newAlt( appExpr, result.env, cost ); 916 PRINT( 917 std::cerr << "instantiate function success: " << appExpr << std::endl; 918 std::cerr << "need assertions:" << std::endl; 919 printAssertionSet( result.need, std::cerr, 8 ); 920 ) 921 inferParameters( result.need, result.have, newAlt, result.openVars, out ); 791 results.swap( nextResults ); 792 nextResults.clear(); 793 794 return ! results.empty(); 922 795 } 923 796 … … 945 818 946 819 // iteratively build matches, one parameter at a time 947 std::vector<ArgPack> results; 948 results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } ); 949 std::size_t genStart = 0; 950 820 std::vector<ArgPack> results{ ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } }; 821 std::vector<ArgPack> nextResults{}; 951 822 for ( DeclarationWithType* formal : funcType->get_parameters() ) { 952 823 ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal ); 953 824 if ( ! instantiateArgument( 954 obj->get_type(), obj->get_init(), args, results, genStart, indexer ) )825 obj->get_type(), obj->get_init(), args, results, nextResults, indexer ) ) 955 826 return; 956 827 } 957 828 829 // filter out results that don't use all the arguments, and aren't variadic 830 std::vector<ArgPack> finalResults{}; 958 831 if ( funcType->get_isVarArgs() ) { 959 // append any unused arguments to vararg pack 960 std::size_t genEnd; 961 do { 962 genEnd = results.size(); 963 964 // iterate results 965 for ( std::size_t i = genStart; i < genEnd; ++i ) { 966 // use remainder of exploded tuple if present 967 if ( ! results[i].expls.empty() ) { 968 const Alternative& actual = results[i].expls.front(); 969 970 TypeEnvironment env = results[i].env; 971 OpenVarSet openVars = results[i].openVars; 972 973 env.addActual( actual.env, openVars ); 974 975 std::vector<Alternative> newExpls( 976 std::next( results[i].expls.begin() ), results[i].expls.end() ); 977 results.emplace_back( 978 i, actual.expr, move(env), copy(results[i].need), 979 copy(results[i].have), move(openVars), results[i].nextArg, 0, 980 Cost::zero, move(newExpls) ); 981 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) ); 982 848 continue; 983 849 } 984 850 985 // finish result when out of arguments986 if ( results[i].nextArg >= args.size() ) {987 validateFunctionAlternative( func, results[i], results, out );988 989 continue;990 }991 992 851 // add each possible next argument 993 auto j = results[i].nextArg; 994 for ( const Alternative& actual : args[j] ) { 995 // fresh copies of parent parameters for this iteration 996 TypeEnvironment env = results[i].env; 997 OpenVarSet openVars = results[i].openVars; 998 999 env.addActual( actual.env, openVars ); 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; 1000 857 1001 858 // explode argument 1002 859 std::vector<Alternative> exploded; 1003 860 Tuples::explode( actual, indexer, back_inserter( exploded ) ); 1004 if ( exploded.empty() ) { 1005 // skip empty tuple arguments by (near-)cloning parent into next gen 1006 results.emplace_back( 1007 results[i], move(env), copy(results[i].need), 1008 copy(results[i].have), move(openVars), j + 1, actual.cost ); 1009 continue; 861 862 // add exploded argument to arg list 863 for ( Alternative& aActual : exploded ) { 864 aResult.withArg( aActual.expr, cost ); 865 cost = Cost::zero; 1010 866 } 1011 1012 // trim first element from exploded 1013 std::vector<Alternative> newExpls; 1014 newExpls.reserve( exploded.size() - 1 ); 1015 for ( std::size_t i = 1; i < exploded.size(); ++i ) { 1016 newExpls.push_back( move(exploded[i]) ); 1017 } 1018 // add new result 1019 results.emplace_back( 1020 i, exploded.front().expr, move(env), copy(results[i].need), 1021 copy(results[i].have), move(openVars), j + 1, 0, 1022 actual.cost, move(newExpls) ); 867 ++aResult.nextArg; 868 nextResults.push_back( std::move(aResult) ); 1023 869 } 1024 870 } 1025 871 1026 genStart = genEnd; 1027 } while ( genEnd != results.size() ); 872 // reset for next round 873 results.swap( nextResults ); 874 nextResults.clear(); 875 } 1028 876 } else { 1029 877 // filter out results that don't use all the arguments 1030 for ( std::size_t i = genStart; i < results.size(); ++i ) { 1031 ArgPack& result = results[i]; 1032 if ( result.expls.empty() && result.nextArg >= args.size() ) { 1033 validateFunctionAlternative( func, result, results, out ); 1034 } 1035 } 878 for ( ArgPack& result : results ) { 879 if ( result.nextExpl >= result.expls.size() && result.nextArg >= args.size() ) { 880 finalResults.push_back( std::move(result) ); 881 } 882 } 883 } 884 885 // validate matching combos, add to final result list 886 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 ); 1036 896 } 1037 897 } … … 1096 956 if ( ! funcOpFinder.alternatives.empty() ) { 1097 957 // add function alternatives to front of argument list 1098 argAlternatives.insert( argAlternatives.begin(), move(funcFinder) );958 argAlternatives.insert( argAlternatives.begin(), std::move(funcFinder) ); 1099 959 1100 960 for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin(); … … 1122 982 1123 983 // compute conversionsion costs 1124 for ( Alt ernative& withFunc : candidates) {1125 Cost cvtCost = computeApplicationConversionCost( withFunc, indexer );984 for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) { 985 Cost cvtCost = computeApplicationConversionCost( *withFunc, indexer ); 1126 986 1127 987 PRINT( 1128 ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc .expr );988 ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc->expr ); 1129 989 PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() ); 1130 990 FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() ); … … 1135 995 printAll( appExpr->get_args(), std::cerr, 8 ); 1136 996 std::cerr << "bindings are:" << std::endl; 1137 withFunc .env.print( std::cerr, 8 );997 withFunc->env.print( std::cerr, 8 ); 1138 998 std::cerr << "cost of conversion is:" << cvtCost << std::endl; 1139 999 ) 1140 1000 if ( cvtCost != Cost::infinity ) { 1141 withFunc .cvtCost = cvtCost;1142 alternatives.push_back( withFunc );1001 withFunc->cvtCost = cvtCost; 1002 alternatives.push_back( *withFunc ); 1143 1003 } // if 1144 1004 } // for 1145 1005 1146 candidates = move(alternatives); 1006 candidates.clear(); 1007 candidates.splice( candidates.end(), alternatives ); 1147 1008 1148 1009 // use a new list so that alternatives are not examined by addAnonConversions twice. … … 1150 1011 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) ); 1151 1012 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 findMinCost1154 // since anon conversionsare never the cheapest expression1013 // function may return struct or union value, in which case we need to add alternatives for implicit 1014 // conversions to each of the anonymous members, must happen after findMinCost since anon conversions 1015 // are never the cheapest expression 1155 1016 for ( const Alternative & alt : winners ) { 1156 1017 addAnonConversions( alt ); 1157 1018 } 1158 spliceBegin( alternatives, winners );1019 alternatives.splice( alternatives.begin(), winners ); 1159 1020 1160 1021 if ( alternatives.empty() && targetType && ! targetType->isVoid() ) { … … 1180 1041 AlternativeFinder finder( indexer, env ); 1181 1042 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 } ); 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 ) ); 1186 1046 } // if 1187 1047 } // for … … 1189 1049 1190 1050 void AlternativeFinder::visit( LabelAddressExpr * expr ) { 1191 alternatives.push_back( Alternative { expr->clone(), env, Cost::zero });1051 alternatives.push_back( Alternative( expr->clone(), env, Cost::zero) ); 1192 1052 } 1193 1053 … … 1231 1091 1232 1092 AltList candidates; 1233 for ( Alternative & alt : finder.alternatives) {1093 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) { 1234 1094 AssertionSet needAssertions, haveAssertions; 1235 1095 OpenVarSet openVars; … … 1239 1099 // that are cast directly. The candidate is invalid if it has fewer results than there are types to cast 1240 1100 // to. 1241 int discardedValues = alt.expr->get_result()->size() - castExpr->get_result()->size();1101 int discardedValues = i->expr->get_result()->size() - castExpr->get_result()->size(); 1242 1102 if ( discardedValues < 0 ) continue; 1243 1103 // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not 1244 1104 // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3])) 1245 1105 // 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 ); 1250 PRINT( 1251 std::cerr << "working on cast with result: " << castExpr->result << std::endl; 1252 std::cerr << "and expr type: " << alt.expr->result << std::endl; 1253 std::cerr << "env: " << alt.env << std::endl; 1254 ) 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 ); 1255 1108 if ( thisCost != Cost::infinity ) { 1256 PRINT(1257 std::cerr << "has finite cost." << std::endl;1258 )1259 1109 // count one safe conversion for each value that is thrown away 1260 1110 thisCost.incSafe( discardedValues ); 1261 Alternative newAlt( restructureCast( alt.expr->clone(), toType ), alt.env, 1262 alt.cost, thisCost ); 1263 inferParameters( needAssertions, haveAssertions, newAlt, openVars, 1264 back_inserter( candidates ) ); 1111 Alternative newAlt( restructureCast( i->expr->clone(), toType ), i->env, i->cost, thisCost ); 1112 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) ); 1265 1113 } // if 1266 1114 } // for … … 1549 1397 1550 1398 void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) { 1551 std::vector< AlternativeFinder > subExprAlternatives; 1552 findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), 1553 back_inserter( subExprAlternatives ) ); 1554 std::vector< AltList > possibilities; 1555 combos( subExprAlternatives.begin(), subExprAlternatives.end(), 1556 back_inserter( possibilities ) ); 1557 for ( const AltList& alts : possibilities ) { 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 ) { 1558 1404 std::list< Expression * > exprs; 1559 makeExprList( alts, exprs );1405 makeExprList( *i, exprs ); 1560 1406 1561 1407 TypeEnvironment compositeEnv; 1562 simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv ); 1563 alternatives.push_back( 1564 Alternative{ new TupleExpr( exprs ), compositeEnv, sumCost( alts ) } ); 1408 simpleCombineEnvironments( i->begin(), i->end(), compositeEnv ); 1409 alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) ); 1565 1410 } // for 1566 1411 }
Note:
See TracChangeset
for help on using the changeset viewer.
