Changeset 452747a for src/ResolvExpr
- Timestamp:
- Nov 22, 2017, 3:43:50 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:
- 5fe35d6
- Parents:
- 7e4c4f4 (diff), c2c6177 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)links above to see all the changes relative to each parent. - Location:
- src/ResolvExpr
- Files:
-
- 6 edited
-
Alternative.cc (modified) (2 diffs)
-
Alternative.h (modified) (3 diffs)
-
AlternativeFinder.cc (modified) (21 diffs)
-
AlternativeFinder.h (modified) (4 diffs)
-
Resolver.cc (modified) (2 diffs)
-
typeops.h (modified) (3 diffs)
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/Alternative.cc
r7e4c4f4 r452747a 18 18 #include <ostream> // for operator<<, ostream, basic_o... 19 19 #include <string> // for operator<<, char_traits, string 20 #include <utility> // for move 20 21 21 22 #include "Common/utility.h" // for maybeClone … … 81 82 os << std::endl; 82 83 } 84 85 void splice( AltList& dst, AltList& src ) { 86 dst.reserve( dst.size() + src.size() ); 87 for ( Alternative& alt : src ) { 88 dst.push_back( std::move(alt) ); 89 } 90 src.clear(); 91 } 92 93 void spliceBegin( AltList& dst, AltList& src ) { 94 splice( src, dst ); 95 dst.swap( src ); 96 } 97 83 98 } // namespace ResolvExpr 84 99 -
src/ResolvExpr/Alternative.h
r7e4c4f4 r452747a 17 17 18 18 #include <iosfwd> // for ostream 19 #include < list> // for list19 #include <vector> // for vector 20 20 21 21 #include "Cost.h" // for Cost … … 25 25 26 26 namespace ResolvExpr { 27 struct Alternative;28 29 typedef std::list< Alternative > AltList;30 31 27 struct Alternative { 32 28 Alternative(); … … 46 42 TypeEnvironment env; 47 43 }; 44 45 typedef std::vector< Alternative > AltList; 46 47 /// Moves all elements from src to the end of dst 48 void splice( AltList& dst, AltList& src ); 49 50 /// Moves all elements from src to the beginning of dst 51 void spliceBegin( AltList& dst, AltList& src ); 48 52 } // namespace ResolvExpr 49 53 -
src/ResolvExpr/AlternativeFinder.cc
r7e4c4f4 r452747a 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 { … … 187 194 printAlts( alternatives, std::cerr ); 188 195 ) 189 AltList ::iterator oldBegin = alternatives.begin();190 pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives) );191 if ( failFast && alternatives.begin() == oldBegin) {196 AltList pruned; 197 pruneAlternatives( alternatives.begin(), alternatives.end(), back_inserter( pruned ) ); 198 if ( failFast && pruned.empty() ) { 192 199 std::ostringstream stream; 193 200 AltList winners; … … 199 206 throw SemanticError( stream.str() ); 200 207 } 201 alternatives .erase( oldBegin, alternatives.end());208 alternatives = move(pruned); 202 209 PRINT( 203 210 std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl; … … 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) 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() {} 582 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() {} 587 588 /// Starts a new tuple expression 589 void beginTuple() { 590 if ( ! tupleEls.empty() ) ++tupleEls.back(); 591 tupleEls.push_back(0); 592 } 598 : parent(0), expr(), cost(Cost::zero), env(env), need(need), have(have), 599 openVars(openVars), nextArg(0), tupleStart(0), expls() {} 600 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, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have, 610 OpenVarSet&& openVars, unsigned nextArg, Cost added ) 611 : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), cost(o.cost + added), 612 env(move(env)), need(move(need)), have(move(have)), openVars(move(openVars)), 613 nextArg(nextArg), tupleStart(o.tupleStart), expls() {} 614 615 616 // ArgPack(const ArgPack& o) 617 // : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), env(o.env), 618 // need(o.need), have(o.have), openVars(o.openVars), nextArg(o.nextArg), 619 // tupleStart(o.tupleStart), expls(o.expls) {} 620 621 // ArgPack(ArgPack&&) = default; 593 622 594 623 /// Ends a tuple expression, consolidating the appropriate actuals 595 void endTuple( ) {596 // set up new Tuple alternative624 void endTuple( const std::vector<ArgPack>& packs ) { 625 // add all expressions in tuple to list, summing cost 597 626 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; 627 const ArgPack* pack = this; 628 if ( expr ) { exprs.push_front( expr.release() ); } 629 while ( pack->tupleStart == 0 ) { 630 pack = &packs[pack->parent]; 631 exprs.push_front( pack->expr->clone() ); 632 cost += pack->cost; 633 } 634 // reset pack to appropriate tuple 635 expr.reset( new TupleExpr( exprs ) ); 636 tupleStart = pack->tupleStart - 1; 637 parent = pack->parent; 618 638 } 619 639 }; … … 621 641 /// Instantiates an argument to match a formal, returns false if no results left 622 642 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 const std::vector< AlternativeFinder >& args, std::vector<ArgPack>& results, 644 std::size_t& genStart, const SymTab::Indexer& indexer, unsigned nTuples = 0 ) { 626 645 if ( TupleType* tupleType = dynamic_cast<TupleType*>( formalType ) ) { 627 646 // formalType is a TupleType - group actuals into a TupleExpr 628 for ( ArgPack& result : results ) { result.beginTuple(); }647 ++nTuples; 629 648 for ( Type* type : *tupleType ) { 630 649 // xxx - dropping initializer changes behaviour from previous, but seems correct 631 if ( ! instantiateArgument( type, nullptr, args, results, nextResults, indexer ) ) 650 if ( ! instantiateArgument( 651 type, nullptr, args, results, genStart, indexer, nTuples ) ) 632 652 return false; 633 } 634 for ( ArgPack& result : results ) { result.endTuple(); } 653 nTuples = 0; 654 } 655 // re-consititute tuples for final generation 656 for ( auto i = genStart; i < results.size(); ++i ) { 657 results[i].endTuple( results ); 658 } 635 659 return true; 636 660 } else if ( TypeInstType* ttype = Tuples::isTtype( formalType ) ) { 637 661 // formalType is a ttype, consumes all remaining arguments 638 662 // 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 } 663 664 // completed tuples; will be spliced to end of results to finish 665 std::vector<ArgPack> finalResults{}; 666 652 667 // iterate until all results completed 653 while ( ! results.empty() ) { 668 std::size_t genEnd; 669 ++nTuples; 670 do { 671 genEnd = results.size(); 672 654 673 // 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 } 674 for ( std::size_t i = genStart; i < genEnd; ++i ) { 675 // use remainder of exploded tuple if present 676 if ( ! results[i].expls.empty() ) { 677 const Alternative& actual = results[i].expls.front(); 678 679 TypeEnvironment env = results[i].env; 680 OpenVarSet openVars = results[i].openVars; 681 682 env.addActual( actual.env, openVars ); 683 684 std::vector<Alternative> newExpls( 685 std::next( results[i].expls.begin() ), results[i].expls.end() ); 686 results.emplace_back( 687 i, actual.expr, move(env), copy(results[i].need), 688 copy(results[i].have), move(openVars), results[i].nextArg, nTuples, 689 Cost::zero, move(newExpls) ); 690 677 691 continue; 678 692 } 679 693 694 // finish result when out of arguments 695 if ( results[i].nextArg >= args.size() ) { 696 ArgPack newResult{ 697 results[i].env, results[i].need, results[i].have, 698 results[i].openVars }; 699 newResult.nextArg = results[i].nextArg; 700 Type* argType; 701 702 if ( nTuples > 0 ) { 703 // first iteration, push empty tuple expression 704 newResult.parent = i; 705 std::list<Expression*> emptyList; 706 newResult.expr.reset( new TupleExpr( emptyList ) ); 707 argType = newResult.expr->get_result(); 708 } else { 709 // clone result to collect tuple 710 newResult.parent = results[i].parent; 711 newResult.cost = results[i].cost; 712 newResult.tupleStart = results[i].tupleStart; 713 newResult.expr.reset( results[i].expr->clone() ); 714 argType = newResult.expr->get_result(); 715 716 if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) { 717 // the case where a ttype value is passed directly is special, 718 // e.g. for argument forwarding purposes 719 // xxx - what if passing multiple arguments, last of which is 720 // ttype? 721 // xxx - what would happen if unify was changed so that unifying 722 // tuple 723 // types flattened both before unifying lists? then pass in 724 // TupleType (ttype) below. 725 --newResult.tupleStart; 726 } else { 727 // collapse leftover arguments into tuple 728 newResult.endTuple( results ); 729 argType = newResult.expr->get_result(); 730 } 731 } 732 733 // check unification for ttype before adding to final 734 if ( unify( ttype, argType, newResult.env, newResult.need, newResult.have, 735 newResult.openVars, indexer ) ) { 736 finalResults.push_back( move(newResult) ); 737 } 738 739 continue; 740 } 741 680 742 // 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; 743 auto j = results[i].nextArg; 744 for ( const Alternative& actual : args[j] ) { 745 // fresh copies of parent parameters for this iteration 746 TypeEnvironment env = results[i].env; 747 OpenVarSet openVars = results[i].openVars; 748 749 env.addActual( actual.env, openVars ); 686 750 687 751 // explode argument 688 752 std::vector<Alternative> exploded; 689 753 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; 754 if ( exploded.empty() ) { 755 // skip empty tuple arguments by (near-)cloning parent into next gen 756 results.emplace_back( 757 results[i], move(env), copy(results[i].need), 758 copy(results[i].have), move(openVars), j + 1, actual.cost ); 759 760 continue; 695 761 } 696 ++aResult.nextArg; 697 nextResults.push_back( std::move(aResult) ); 762 763 // trim first element from exploded 764 std::vector<Alternative> newExpls; 765 newExpls.reserve( exploded.size() - 1 ); 766 for ( std::size_t i = 1; i < exploded.size(); ++i ) { 767 newExpls.push_back( move(exploded[i]) ); 768 } 769 // add new result 770 results.emplace_back( 771 i, exploded.front().expr, move(env), copy(results[i].need), 772 copy(results[i].have), move(openVars), results[i].nextArg + 1, 773 nTuples, actual.cost, move(newExpls) ); 698 774 } 699 775 } 700 776 701 777 // reset for next round 702 results.swap( nextResults ); 703 nextResults.clear(); 704 } 705 results.swap( finalResults ); 706 return ! results.empty(); 778 genStart = genEnd; 779 nTuples = 0; 780 } while ( genEnd != results.size() ); 781 782 // splice final results onto results 783 for ( std::size_t i = 0; i < finalResults.size(); ++i ) { 784 results.push_back( move(finalResults[i]) ); 785 } 786 return ! finalResults.empty(); 707 787 } 708 788 709 789 // 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 ); 790 std::size_t genEnd = results.size(); 791 for ( std::size_t i = genStart; i < genEnd; ++i ) { 792 // use remainder of exploded tuple if present 793 if ( ! results[i].expls.empty() ) { 794 const Alternative& actual = results[i].expls.front(); 795 796 TypeEnvironment env = results[i].env; 797 AssertionSet need = results[i].need, have = results[i].have; 798 OpenVarSet openVars = results[i].openVars; 799 800 env.addActual( actual.env, openVars ); 717 801 Type* actualType = actual.expr->get_result(); 718 802 … … 725 809 ) 726 810 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 )) ); 811 if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) { 812 std::vector<Alternative> newExpls( 813 std::next( results[i].expls.begin() ), results[i].expls.end() ); 814 results.emplace_back( 815 i, actual.expr, move(env), move(need), move(have), move(openVars), 816 results[i].nextArg, nTuples, Cost::zero, move(newExpls) );; 731 817 } 732 818 733 819 continue; 734 } else if ( result.nextArg >= args.size() ) { 735 // use default initializers if out of arguments 820 } 821 822 // use default initializers if out of arguments 823 if ( results[i].nextArg >= args.size() ) { 736 824 if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) { 737 825 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 )) ); 826 TypeEnvironment env = results[i].env; 827 AssertionSet need = results[i].need, have = results[i].have; 828 OpenVarSet openVars = results[i].openVars; 829 830 if ( unify( formalType, cnst->get_type(), env, need, have, openVars, 831 indexer ) ) { 832 results.emplace_back( 833 i, cnstExpr, move(env), move(need), move(have), 834 move(openVars), results[i].nextArg, nTuples ); 741 835 } 742 836 } 743 837 } 838 744 839 continue; 745 840 } 746 841 747 842 // 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 ); 843 auto j = results[i].nextArg; 844 for ( const Alternative& actual : args[j] ) { 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( actual.env, openVars ); 752 851 753 852 // explode argument … … 755 854 Tuples::explode( actual, indexer, back_inserter( exploded ) ); 756 855 if ( exploded.empty() ) { 757 // skip empty tuple arguments 758 ++aResult.nextArg; 759 results.push_back( std::move(aResult) ); 856 // skip empty tuple arguments by (near-)cloning parent into next gen 857 results.emplace_back( 858 results[i], move(env), move(need), move(have), move(openVars), j + 1, 859 actual.cost ); 860 760 861 continue; 761 862 } … … 774 875 775 876 // 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; 877 if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) { 878 // trim first element from exploded 879 std::vector<Alternative> newExpls; 880 newExpls.reserve( exploded.size() - 1 ); 881 for ( std::size_t i = 1; i < exploded.size(); ++i ) { 882 newExpls.push_back( move(exploded[i]) ); 784 883 } 785 nextResults.push_back( std::move(aResult) ); 884 // add new result 885 results.emplace_back( 886 i, aActual.expr, move(env), move(need), move(have), move(openVars), 887 j + 1, nTuples, actual.cost, move(newExpls) ); 786 888 } 787 889 } … … 789 891 790 892 // reset for next parameter 791 results.swap( nextResults ); 792 nextResults.clear(); 793 794 return ! results.empty(); 893 genStart = genEnd; 894 895 return genEnd != results.size(); 896 } 897 898 template<typename OutputIterator> 899 void AlternativeFinder::validateFunctionAlternative( const Alternative &func, ArgPack& result, 900 const std::vector<ArgPack>& results, OutputIterator out ) { 901 ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() ); 902 // sum cost and accumulate actuals 903 std::list<Expression*>& args = appExpr->get_args(); 904 Cost cost = Cost::zero; 905 const ArgPack* pack = &result; 906 while ( pack->expr ) { 907 args.push_front( pack->expr->clone() ); 908 cost += pack->cost; 909 pack = &results[pack->parent]; 910 } 911 // build and validate new alternative 912 Alternative newAlt( appExpr, result.env, cost ); 913 PRINT( 914 std::cerr << "instantiate function success: " << appExpr << std::endl; 915 std::cerr << "need assertions:" << std::endl; 916 printAssertionSet( result.need, std::cerr, 8 ); 917 ) 918 inferParameters( result.need, result.have, newAlt, result.openVars, out ); 795 919 } 796 920 … … 818 942 819 943 // iteratively build matches, one parameter at a time 820 std::vector<ArgPack> results{ ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } }; 821 std::vector<ArgPack> nextResults{}; 944 std::vector<ArgPack> results; 945 results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } ); 946 std::size_t genStart = 0; 947 822 948 for ( DeclarationWithType* formal : funcType->get_parameters() ) { 823 949 ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal ); 824 950 if ( ! instantiateArgument( 825 obj->get_type(), obj->get_init(), args, results, nextResults, indexer ) )951 obj->get_type(), obj->get_init(), args, results, genStart, indexer ) ) 826 952 return; 827 953 } 828 954 829 // filter out results that don't use all the arguments, and aren't variadic830 std::vector<ArgPack> finalResults{};831 955 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) ); 956 // append any unused arguments to vararg pack 957 std::size_t genEnd; 958 do { 959 genEnd = results.size(); 960 961 // iterate results 962 for ( std::size_t i = genStart; i < genEnd; ++i ) { 963 // use remainder of exploded tuple if present 964 if ( ! results[i].expls.empty() ) { 965 const Alternative& actual = results[i].expls.front(); 966 967 TypeEnvironment env = results[i].env; 968 OpenVarSet openVars = results[i].openVars; 969 970 env.addActual( actual.env, openVars ); 971 972 std::vector<Alternative> newExpls( 973 std::next( results[i].expls.begin() ), results[i].expls.end() ); 974 results.emplace_back( 975 i, actual.expr, move(env), copy(results[i].need), 976 copy(results[i].have), move(openVars), results[i].nextArg, 0, 977 Cost::zero, move(newExpls) ); 978 848 979 continue; 849 980 } 850 981 982 // finish result when out of arguments 983 if ( results[i].nextArg >= args.size() ) { 984 validateFunctionAlternative( func, results[i], results, out ); 985 986 continue; 987 } 988 851 989 // 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; 990 auto j = results[i].nextArg; 991 for ( const Alternative& actual : args[j] ) { 992 // fresh copies of parent parameters for this iteration 993 TypeEnvironment env = results[i].env; 994 OpenVarSet openVars = results[i].openVars; 995 996 env.addActual( actual.env, openVars ); 857 997 858 998 // explode argument 859 999 std::vector<Alternative> exploded; 860 1000 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; 1001 if ( exploded.empty() ) { 1002 // skip empty tuple arguments by (near-)cloning parent into next gen 1003 results.emplace_back( 1004 results[i], move(env), copy(results[i].need), 1005 copy(results[i].have), move(openVars), j + 1, actual.cost ); 1006 continue; 866 1007 } 867 ++aResult.nextArg; 868 nextResults.push_back( std::move(aResult) ); 1008 1009 // trim first element from exploded 1010 std::vector<Alternative> newExpls; 1011 newExpls.reserve( exploded.size() - 1 ); 1012 for ( std::size_t i = 1; i < exploded.size(); ++i ) { 1013 newExpls.push_back( move(exploded[i]) ); 1014 } 1015 // add new result 1016 results.emplace_back( 1017 i, exploded.front().expr, move(env), copy(results[i].need), 1018 copy(results[i].have), move(openVars), j + 1, 0, 1019 actual.cost, move(newExpls) ); 869 1020 } 870 1021 } 871 1022 872 // reset for next round 873 results.swap( nextResults ); 874 nextResults.clear(); 875 } 1023 genStart = genEnd; 1024 } while ( genEnd != results.size() ); 876 1025 } else { 877 1026 // 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) ); 1027 for ( std::size_t i = genStart; i < results.size(); ++i ) { 1028 ArgPack& result = results[i]; 1029 if ( result.expls.empty() && result.nextArg >= args.size() ) { 1030 validateFunctionAlternative( func, result, results, out ); 881 1031 } 882 1032 } 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 1033 } 897 1034 } … … 956 1093 if ( ! funcOpFinder.alternatives.empty() ) { 957 1094 // add function alternatives to front of argument list 958 argAlternatives.insert( argAlternatives.begin(), std::move(funcFinder) );1095 argAlternatives.insert( argAlternatives.begin(), move(funcFinder) ); 959 1096 960 1097 for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin(); … … 982 1119 983 1120 // compute conversionsion costs 984 for ( Alt List::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc) {985 Cost cvtCost = computeApplicationConversionCost( *withFunc, indexer );1121 for ( Alternative& withFunc : candidates ) { 1122 Cost cvtCost = computeApplicationConversionCost( withFunc, indexer ); 986 1123 987 1124 PRINT( 988 ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc ->expr );1125 ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc.expr ); 989 1126 PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() ); 990 1127 FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() ); … … 995 1132 printAll( appExpr->get_args(), std::cerr, 8 ); 996 1133 std::cerr << "bindings are:" << std::endl; 997 withFunc ->env.print( std::cerr, 8 );1134 withFunc.env.print( std::cerr, 8 ); 998 1135 std::cerr << "cost of conversion is:" << cvtCost << std::endl; 999 1136 ) 1000 1137 if ( cvtCost != Cost::infinity ) { 1001 withFunc ->cvtCost = cvtCost;1002 alternatives.push_back( *withFunc );1138 withFunc.cvtCost = cvtCost; 1139 alternatives.push_back( withFunc ); 1003 1140 } // if 1004 1141 } // for 1005 1142 1006 candidates.clear(); 1007 candidates.splice( candidates.end(), alternatives ); 1143 candidates = move(alternatives); 1008 1144 1009 1145 // use a new list so that alternatives are not examined by addAnonConversions twice. … … 1011 1147 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) ); 1012 1148 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 expression1149 // function may return struct or union value, in which case we need to add alternatives 1150 // for implicitconversions to each of the anonymous members, must happen after findMinCost 1151 // since anon conversions are never the cheapest expression 1016 1152 for ( const Alternative & alt : winners ) { 1017 1153 addAnonConversions( alt ); 1018 1154 } 1019 alternatives.splice( alternatives.begin(), winners );1155 spliceBegin( alternatives, winners ); 1020 1156 1021 1157 if ( alternatives.empty() && targetType && ! targetType->isVoid() ) { … … 1041 1177 AlternativeFinder finder( indexer, env ); 1042 1178 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 ) ); 1179 for ( Alternative& alt : finder.alternatives ) { 1180 if ( isLvalue( alt.expr ) ) { 1181 alternatives.push_back( 1182 Alternative{ new AddressExpr( alt.expr->clone() ), alt.env, alt.cost } ); 1046 1183 } // if 1047 1184 } // for … … 1049 1186 1050 1187 void AlternativeFinder::visit( LabelAddressExpr * expr ) { 1051 alternatives.push_back( Alternative ( expr->clone(), env, Cost::zero));1188 alternatives.push_back( Alternative{ expr->clone(), env, Cost::zero } ); 1052 1189 } 1053 1190 … … 1091 1228 1092 1229 AltList candidates; 1093 for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i) {1230 for ( Alternative & alt : finder.alternatives ) { 1094 1231 AssertionSet needAssertions, haveAssertions; 1095 1232 OpenVarSet openVars; … … 1099 1236 // that are cast directly. The candidate is invalid if it has fewer results than there are types to cast 1100 1237 // to. 1101 int discardedValues = i->expr->get_result()->size() - castExpr->get_result()->size();1238 int discardedValues = alt.expr->get_result()->size() - castExpr->get_result()->size(); 1102 1239 if ( discardedValues < 0 ) continue; 1103 1240 // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not 1104 1241 // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3])) 1105 1242 // 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 ); 1243 unify( castExpr->get_result(), alt.expr->get_result(), alt.env, needAssertions, 1244 haveAssertions, openVars, indexer ); 1245 Cost thisCost = castCost( alt.expr->get_result(), castExpr->get_result(), indexer, 1246 alt.env ); 1108 1247 PRINT( 1109 1248 std::cerr << "working on cast with result: " << castExpr->result << std::endl; 1110 std::cerr << "and expr type: " << i->expr->result << std::endl;1111 std::cerr << "env: " << i->env << std::endl;1249 std::cerr << "and expr type: " << alt.expr->result << std::endl; 1250 std::cerr << "env: " << alt.env << std::endl; 1112 1251 ) 1113 1252 if ( thisCost != Cost::infinity ) { … … 1117 1256 // count one safe conversion for each value that is thrown away 1118 1257 thisCost.incSafe( discardedValues ); 1119 Alternative newAlt( restructureCast( i->expr->clone(), toType ), i->env, i->cost, thisCost ); 1120 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) ); 1258 Alternative newAlt( restructureCast( alt.expr->clone(), toType ), alt.env, 1259 alt.cost, thisCost ); 1260 inferParameters( needAssertions, haveAssertions, newAlt, openVars, 1261 back_inserter( candidates ) ); 1121 1262 } // if 1122 1263 } // for … … 1405 1546 1406 1547 void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) { 1407 std::list< AlternativeFinder > subExprAlternatives; 1408 findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) ); 1409 std::list< AltList > possibilities; 1410 combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) ); 1411 for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) { 1548 std::vector< AlternativeFinder > subExprAlternatives; 1549 findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), 1550 back_inserter( subExprAlternatives ) ); 1551 std::vector< AltList > possibilities; 1552 combos( subExprAlternatives.begin(), subExprAlternatives.end(), 1553 back_inserter( possibilities ) ); 1554 for ( const AltList& alts : possibilities ) { 1412 1555 std::list< Expression * > exprs; 1413 makeExprList( *i, exprs );1556 makeExprList( alts, exprs ); 1414 1557 1415 1558 TypeEnvironment compositeEnv; 1416 simpleCombineEnvironments( i->begin(), i->end(), compositeEnv ); 1417 alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) ); 1559 simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv ); 1560 alternatives.push_back( 1561 Alternative{ new TupleExpr( exprs ), compositeEnv, sumCost( alts ) } ); 1418 1562 } // for 1419 1563 } -
src/ResolvExpr/AlternativeFinder.h
r7e4c4f4 r452747a 31 31 32 32 namespace ResolvExpr { 33 struct ArgPack; 34 33 35 class AlternativeFinder : public Visitor { 34 36 public: … … 36 38 37 39 AlternativeFinder( const AlternativeFinder& o ) 38 : indexer(o.indexer), alternatives(o.alternatives), env(o.env), 40 : indexer(o.indexer), alternatives(o.alternatives), env(o.env), 39 41 targetType(o.targetType) {} 40 42 41 43 AlternativeFinder( AlternativeFinder&& o ) 42 : indexer(o.indexer), alternatives(std::move(o.alternatives)), env(o.env), 44 : indexer(o.indexer), alternatives(std::move(o.alternatives)), env(o.env), 43 45 targetType(o.targetType) {} 44 46 45 47 AlternativeFinder& operator= ( const AlternativeFinder& o ) { 46 48 if (&o == this) return *this; 47 49 48 50 // horrific nasty hack to rebind references... 49 51 alternatives.~AltList(); … … 54 56 AlternativeFinder& operator= ( AlternativeFinder&& o ) { 55 57 if (&o == this) return *this; 56 58 57 59 // horrific nasty hack to rebind references... 58 60 alternatives.~AltList(); … … 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 ); -
src/ResolvExpr/Resolver.cc
r7e4c4f4 r452747a 18 18 #include <memory> // for allocator, allocator_traits<... 19 19 #include <tuple> // for get 20 #include <vector> 20 21 21 22 #include "Alternative.h" // for Alternative, AltList … … 411 412 412 413 // Find all alternatives for all arguments in canonical form 413 std:: list< AlternativeFinder > argAlternatives;414 std::vector< AlternativeFinder > argAlternatives; 414 415 funcFinder.findSubExprs( clause.target.arguments.begin(), clause.target.arguments.end(), back_inserter( argAlternatives ) ); 415 416 416 417 // List all combinations of arguments 417 std:: list< AltList > possibilities;418 std::vector< AltList > possibilities; 418 419 combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) ); 419 420 -
src/ResolvExpr/typeops.h
r7e4c4f4 r452747a 16 16 #pragma once 17 17 18 #include <vector> 19 18 20 #include "SynTree/SynTree.h" 19 21 #include "SynTree/Type.h" … … 28 30 void combos( InputIterator begin, InputIterator end, OutputIterator out ) { 29 31 typedef typename InputIterator::value_type SetType; 30 typedef typename std:: list< typename SetType::value_type > ListType;32 typedef typename std::vector< typename SetType::value_type > ListType; 31 33 32 34 if ( begin == end ) { … … 38 40 begin++; 39 41 40 std:: list< ListType > recursiveResult;42 std::vector< ListType > recursiveResult; 41 43 combos( begin, end, back_inserter( recursiveResult ) ); 42 44 43 for ( typename std::list< ListType >::const_iterator i = recursiveResult.begin(); i != recursiveResult.end(); ++i ) { 44 for ( typename ListType::const_iterator j = current->begin(); j != current->end(); ++j ) { 45 ListType result; 46 std::back_insert_iterator< ListType > inserter = back_inserter( result ); 47 *inserter++ = *j; 48 std::copy( i->begin(), i->end(), inserter ); 49 *out++ = result; 50 } // for 51 } // for 45 for ( const auto& i : recursiveResult ) for ( const auto& j : *current ) { 46 ListType result; 47 std::back_insert_iterator< ListType > inserter = back_inserter( result ); 48 *inserter++ = j; 49 std::copy( i.begin(), i.end(), inserter ); 50 *out++ = result; 51 } 52 52 } 53 53
Note: See TracChangeset
for help on using the changeset viewer.
