Changeset 178e4ec for src/ResolvExpr/AlternativeFinder.cc
- Timestamp:
- Nov 23, 2017, 5:12:22 PM (6 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:
- 3787dc1
- Parents:
- 8dceeb7 (diff), 62194cb (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. - File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/AlternativeFinder.cc
r8dceeb7 r178e4ec 30 30 #include "Common/utility.h" // for deleteAll, printAll, CodeLocation 31 31 #include "Cost.h" // for Cost, Cost::zero, operator<<, Cost... 32 #include "ExplodedActual.h" // for ExplodedActual 32 33 #include "InitTweak/InitTweak.h" // for getFunctionName 33 34 #include "RenameVars.h" // for RenameVars, global_renamer … … 590 591 unsigned nextArg; ///< Index of next argument in arguments list 591 592 unsigned tupleStart; ///< Number of tuples that start at this index 592 // TODO fix this somehow593 std::vector<Alternative> expls; ///< Exploded actuals left over from last match593 unsigned nextExpl; ///< Index of next exploded element 594 unsigned explAlt; ///< Index of alternative for nextExpl > 0 594 595 595 596 ArgPack() 596 597 : parent(0), expr(), cost(Cost::zero), env(), need(), have(), openVars(), nextArg(0), 597 tupleStart(0), expls() {} 598 599 tupleStart(0), nextExpl(0), explAlt(0) {} 598 600 599 601 ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have, 600 602 const OpenVarSet& openVars) 601 603 : parent(0), expr(), cost(Cost::zero), env(env), need(need), have(have), 602 openVars(openVars), nextArg(0), tupleStart(0), expls() {}604 openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {} 603 605 604 606 ArgPack(std::size_t parent, Expression* expr, TypeEnvironment&& env, AssertionSet&& need, 605 607 AssertionSet&& have, OpenVarSet&& openVars, unsigned nextArg, 606 unsigned tupleStart = 0, Cost cost = Cost::zero, 607 std::vector<Alternative>&& expls = std::vector<Alternative>{})608 unsigned tupleStart = 0, Cost cost = Cost::zero, unsigned nextExpl = 0, 609 unsigned explAlt = 0 ) 608 610 : parent(parent), expr(expr->clone()), cost(cost), env(move(env)), need(move(need)), 609 611 have(move(have)), openVars(move(openVars)), nextArg(nextArg), tupleStart(tupleStart), 610 expls(move(expls)) {}612 nextExpl(nextExpl), explAlt(explAlt) {} 611 613 612 614 ArgPack(const ArgPack& o, TypeEnvironment&& env, AssertionSet&& need, AssertionSet&& have, … … 614 616 : parent(o.parent), expr(o.expr ? o.expr->clone() : nullptr), cost(o.cost + added), 615 617 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;618 nextArg(nextArg), tupleStart(o.tupleStart), nextExpl(0), explAlt(0) {} 619 620 /// true iff this pack is in the middle of an exploded argument 621 bool hasExpl() const { return nextExpl > 0; } 622 623 /// Gets the list of exploded alternatives for this pack 624 const ExplodedActual& getExpl( const ExplodedArgs& args ) const { 625 return args[nextArg-1][explAlt]; 626 } 625 627 626 628 /// Ends a tuple expression, consolidating the appropriate actuals … … 644 646 /// Instantiates an argument to match a formal, returns false if no results left 645 647 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 ) {648 const ExplodedArgs& args, std::vector<ArgPack>& results, std::size_t& genStart, 649 const SymTab::Indexer& indexer, unsigned nTuples = 0 ) { 648 650 if ( TupleType* tupleType = dynamic_cast<TupleType*>( formalType ) ) { 649 651 // formalType is a TupleType - group actuals into a TupleExpr … … 676 678 // add another argument to results 677 679 for ( std::size_t i = genStart; i < genEnd; ++i ) { 678 // use remainder of exploded tuple if present679 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() ); 680 auto nextArg = results[i].nextArg; 681 682 // use next element of exploded tuple if present 683 if ( results[i].hasExpl() ) { 684 const ExplodedActual& expl = results[i].getExpl( args ); 685 686 unsigned nextExpl = results[i].nextExpl + 1; 687 if ( nextExpl == expl.exprs.size() ) { 688 nextExpl = 0; 689 } 690 689 691 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) ); 692 i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env), 693 copy(results[i].need), copy(results[i].have), 694 copy(results[i].openVars), nextArg, nTuples, Cost::zero, nextExpl, 695 results[i].explAlt ); 693 696 694 697 continue; … … 696 699 697 700 // finish result when out of arguments 698 if ( results[i].nextArg >= args.size() ) {701 if ( nextArg >= args.size() ) { 699 702 ArgPack newResult{ 700 703 results[i].env, results[i].need, results[i].have, 701 704 results[i].openVars }; 702 newResult.nextArg = results[i].nextArg;705 newResult.nextArg = nextArg; 703 706 Type* argType; 704 707 … … 744 747 745 748 // add each possible next argument 746 auto j = results[i].nextArg; 747 for ( const Alternative& actual : args[j] ) { 749 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { 750 const ExplodedActual& expl = args[nextArg][j]; 751 748 752 // fresh copies of parent parameters for this iteration 749 753 TypeEnvironment env = results[i].env; 750 754 OpenVarSet openVars = results[i].openVars; 751 755 752 env.addActual( actual.env, openVars ); 753 754 // explode argument 755 std::vector<Alternative> exploded; 756 Tuples::explode( actual, indexer, back_inserter( exploded ) ); 757 if ( exploded.empty() ) { 758 // skip empty tuple arguments by (near-)cloning parent into next gen 756 env.addActual( expl.env, openVars ); 757 758 // skip empty tuple arguments by (near-)cloning parent into next gen 759 if ( expl.exprs.empty() ) { 759 760 results.emplace_back( 760 761 results[i], move(env), copy(results[i].need), 761 copy(results[i].have), move(openVars), j + 1, actual.cost );762 copy(results[i].have), move(openVars), nextArg + 1, expl.cost ); 762 763 763 764 continue; 764 765 } 765 766 766 // trim first element from exploded767 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 767 // add new result 773 768 results.emplace_back( 774 i, expl oded.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));769 i, expl.exprs.front().get(), move(env), copy(results[i].need), 770 copy(results[i].have), move(openVars), nextArg + 1, 771 nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); 777 772 } 778 773 } … … 793 788 std::size_t genEnd = results.size(); 794 789 for ( std::size_t i = genStart; i < genEnd; ++i ) { 790 auto nextArg = results[i].nextArg; 791 795 792 // use remainder of exploded tuple if present 796 if ( ! results[i].expls.empty() ) { 797 const Alternative& actual = results[i].expls.front(); 793 if ( results[i].hasExpl() ) { 794 const ExplodedActual& expl = results[i].getExpl( args ); 795 Expression* expr = expl.exprs[results[i].nextExpl].get(); 798 796 799 797 TypeEnvironment env = results[i].env; … … 801 799 OpenVarSet openVars = results[i].openVars; 802 800 803 env.addActual( actual.env, openVars ); 804 Type* actualType = actual.expr->get_result(); 801 Type* actualType = expr->get_result(); 805 802 806 803 PRINT( … … 813 810 814 811 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() ); 812 unsigned nextExpl = results[i].nextExpl + 1; 813 if ( nextExpl == expl.exprs.size() ) { 814 nextExpl = 0; 815 } 816 817 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) );;818 i, expr, move(env), move(need), move(have), move(openVars), nextArg, 819 nTuples, Cost::zero, nextExpl, results[i].explAlt ); 820 820 } 821 821 … … 824 824 825 825 // use default initializers if out of arguments 826 if ( results[i].nextArg >= args.size() ) {826 if ( nextArg >= args.size() ) { 827 827 if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) { 828 828 if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) { … … 835 835 results.emplace_back( 836 836 i, cnstExpr, move(env), move(need), move(have), 837 move(openVars), results[i].nextArg, nTuples );837 move(openVars), nextArg, nTuples ); 838 838 } 839 839 } … … 844 844 845 845 // Check each possible next argument 846 auto j = results[i].nextArg; 847 for ( const Alternative& actual : args[j] ) { 846 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { 847 const ExplodedActual& expl = args[nextArg][j]; 848 848 849 // fresh copies of parent parameters for this iteration 849 850 TypeEnvironment env = results[i].env; … … 851 852 OpenVarSet openVars = results[i].openVars; 852 853 853 env.addActual( actual.env, openVars ); 854 855 // explode argument 856 std::vector<Alternative> exploded; 857 Tuples::explode( actual, indexer, back_inserter( exploded ) ); 858 if ( exploded.empty() ) { 859 // skip empty tuple arguments by (near-)cloning parent into next gen 854 env.addActual( expl.env, openVars ); 855 856 // skip empty tuple arguments by (near-)cloning parent into next gen 857 if ( expl.exprs.empty() ) { 860 858 results.emplace_back( 861 results[i], move(env), move(need), move(have), move(openVars), j + 1,862 actual.cost );859 results[i], move(env), move(need), move(have), move(openVars), 860 nextArg + 1, expl.cost ); 863 861 864 862 continue; … … 866 864 867 865 // consider only first exploded actual 868 const Alternative& aActual = exploded.front();869 Type* actualType = aActual.expr->get_result()->clone();866 Expression* expr = expl.exprs.front().get(); 867 Type* actualType = expr->get_result()->clone(); 870 868 871 869 PRINT( … … 879 877 // attempt to unify types 880 878 if ( unify( formalType, actualType, env, need, have, openVars, indexer ) ) { 881 // trim first element from exploded882 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]) );886 }887 879 // add new result 888 880 results.emplace_back( 889 i, aActual.expr, move(env), move(need), move(have), move(openVars),890 j + 1, nTuples, actual.cost, move(newExpls));881 i, expr, move(env), move(need), move(have), move(openVars), nextArg + 1, 882 nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); 891 883 } 892 884 } … … 924 916 template<typename OutputIterator> 925 917 void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, 926 FunctionType *funcType, const std::vector< AlternativeFinder > &args, 927 OutputIterator out ) { 918 FunctionType *funcType, const ExplodedArgs &args, OutputIterator out ) { 928 919 OpenVarSet funcOpenVars; 929 920 AssertionSet funcNeed, funcHave; … … 964 955 // iterate results 965 956 for ( std::size_t i = genStart; i < genEnd; ++i ) { 957 auto nextArg = results[i].nextArg; 958 966 959 // 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() ); 960 if ( results[i].hasExpl() ) { 961 const ExplodedActual& expl = results[i].getExpl( args ); 962 963 unsigned nextExpl = results[i].nextExpl + 1; 964 if ( nextExpl == expl.exprs.size() ) { 965 nextExpl = 0; 966 } 967 977 968 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) ); 969 i, expl.exprs[results[i].nextExpl].get(), copy(results[i].env), 970 copy(results[i].need), copy(results[i].have), 971 copy(results[i].openVars), nextArg, 0, Cost::zero, nextExpl, 972 results[i].explAlt ); 981 973 982 974 continue; … … 984 976 985 977 // finish result when out of arguments 986 if ( results[i].nextArg >= args.size() ) {978 if ( nextArg >= args.size() ) { 987 979 validateFunctionAlternative( func, results[i], results, out ); 988 980 … … 991 983 992 984 // add each possible next argument 993 auto j = results[i].nextArg; 994 for ( const Alternative& actual : args[j] ) { 985 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { 986 const ExplodedActual& expl = args[nextArg][j]; 987 995 988 // fresh copies of parent parameters for this iteration 996 989 TypeEnvironment env = results[i].env; 997 990 OpenVarSet openVars = results[i].openVars; 998 991 999 env.addActual( actual.env, openVars ); 1000 1001 // explode argument 1002 std::vector<Alternative> exploded; 1003 Tuples::explode( actual, indexer, back_inserter( exploded ) ); 1004 if ( exploded.empty() ) { 1005 // skip empty tuple arguments by (near-)cloning parent into next gen 992 env.addActual( expl.env, openVars ); 993 994 // skip empty tuple arguments by (near-)cloning parent into next gen 995 if ( expl.exprs.empty() ) { 1006 996 results.emplace_back( 1007 997 results[i], move(env), copy(results[i].need), 1008 copy(results[i].have), move(openVars), j + 1, actual.cost ); 998 copy(results[i].have), move(openVars), nextArg + 1, expl.cost ); 999 1009 1000 continue; 1010 1001 } 1011 1002 1012 // trim first element from exploded1013 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 1003 // add new result 1019 1004 results.emplace_back( 1020 i, expl oded.front().expr, move(env), copy(results[i].need),1021 copy(results[i].have), move(openVars), j+ 1, 0,1022 actual.cost, move(newExpls));1005 i, expl.exprs.front().get(), move(env), copy(results[i].need), 1006 copy(results[i].have), move(openVars), nextArg + 1, 0, 1007 expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); 1023 1008 } 1024 1009 } … … 1030 1015 for ( std::size_t i = genStart; i < results.size(); ++i ) { 1031 1016 ArgPack& result = results[i]; 1032 if ( result.expls.empty() && result.nextArg >= args.size() ) {1017 if ( ! result.hasExpl() && result.nextArg >= args.size() ) { 1033 1018 validateFunctionAlternative( func, result, results, out ); 1034 1019 } … … 1060 1045 printAlts( funcOpFinder.alternatives, std::cerr, 1 ); 1061 1046 ) 1047 1048 // pre-explode arguments 1049 ExplodedArgs argExpansions; 1050 argExpansions.reserve( argAlternatives.size() ); 1051 1052 for ( const AlternativeFinder& arg : argAlternatives ) { 1053 argExpansions.emplace_back(); 1054 auto& argE = argExpansions.back(); 1055 argE.reserve( arg.alternatives.size() ); 1056 1057 for ( const Alternative& actual : arg ) { 1058 argE.emplace_back( actual, indexer ); 1059 } 1060 } 1062 1061 1063 1062 AltList candidates; … … 1074 1073 Alternative newFunc( *func ); 1075 1074 referenceToRvalueConversion( newFunc.expr ); 1076 makeFunctionAlternatives( newFunc, function, arg Alternatives,1075 makeFunctionAlternatives( newFunc, function, argExpansions, 1077 1076 std::back_inserter( candidates ) ); 1078 1077 } … … 1083 1082 Alternative newFunc( *func ); 1084 1083 referenceToRvalueConversion( newFunc.expr ); 1085 makeFunctionAlternatives( newFunc, function, arg Alternatives,1084 makeFunctionAlternatives( newFunc, function, argExpansions, 1086 1085 std::back_inserter( candidates ) ); 1087 1086 } // if … … 1095 1094 // try each function operator ?() with each function alternative 1096 1095 if ( ! funcOpFinder.alternatives.empty() ) { 1097 // add function alternatives to front of argument list 1098 argAlternatives.insert( argAlternatives.begin(), move(funcFinder) ); 1096 // add exploded function alternatives to front of argument list 1097 std::vector<ExplodedActual> funcE; 1098 funcE.reserve( funcFinder.alternatives.size() ); 1099 for ( const Alternative& actual : funcFinder ) { 1100 funcE.emplace_back( actual, indexer ); 1101 } 1102 argExpansions.insert( argExpansions.begin(), move(funcE) ); 1099 1103 1100 1104 for ( AltList::iterator funcOp = funcOpFinder.alternatives.begin(); … … 1108 1112 Alternative newFunc( *funcOp ); 1109 1113 referenceToRvalueConversion( newFunc.expr ); 1110 makeFunctionAlternatives( newFunc, function, arg Alternatives,1114 makeFunctionAlternatives( newFunc, function, argExpansions, 1111 1115 std::back_inserter( candidates ) ); 1112 1116 }
Note: See TracChangeset
for help on using the changeset viewer.