- File:
-
- 1 edited
-
src/ResolvExpr/AlternativeFinder.cc (modified) (10 diffs)
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/AlternativeFinder.cc
rb60f9d9 r982f95d 9 9 // Author : Richard C. Bilson 10 10 // Created On : Sat May 16 23:52:08 2015 11 // Last Modified By : Aaron B. Moss12 // Last Modified On : Mon Jun 11 16:40:00201813 // Update Count : 3 411 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Sat Feb 17 11:19:39 2018 13 // Update Count : 33 14 14 // 15 15 … … 19 19 #include <iostream> // for operator<<, cerr, ostream, endl 20 20 #include <iterator> // for back_insert_iterator, back_inserter 21 #include <limits> // for numeric_limits<int>::max()22 21 #include <list> // for _List_iterator, list, _List_const_... 23 22 #include <map> // for _Rb_tree_iterator, map, _Rb_tree_c... 24 23 #include <memory> // for allocator_traits<>::value_type 25 #include <tuple> // for tuple26 24 #include <utility> // for pair 27 25 #include <vector> // for vector … … 446 444 } 447 445 448 #if 0 // cost of assertions accounted for in function creation449 446 for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) { 450 447 convCost += computeConversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env ); 451 448 } 452 #endif453 449 454 450 return convCost; … … 576 572 } 577 573 578 namespace {579 /// Information required to defer resolution of an expression580 struct AssertionPack {581 SymTab::Indexer::IdData cdata; ///< Satisfying declaration582 Type* adjType; ///< Satisfying type583 TypeEnvironment env; ///< Post-unification environment584 AssertionSet have; ///< Post-unification have-set585 AssertionSet need; ///< Post-unification need-set586 OpenVarSet openVars; ///< Post-unification open-var set587 588 AssertionPack( const SymTab::Indexer::IdData& cdata, Type* adjType,589 TypeEnvironment&& env, AssertionSet&& have, AssertionSet&& need,590 OpenVarSet&& openVars )591 : cdata(cdata), adjType(adjType), env(std::move(env)), have(std::move(have)),592 need(std::move(need)), openVars(std::move(openVars)) {}593 };594 595 /// List of deferred assertion resolutions for the same type596 using DeferList = std::vector<AssertionPack>;597 598 /// Intermediate state for assertion resolution599 struct AssertionResnState {600 using DeferItem = std::tuple<DeclarationWithType*, AssertionSetValue, DeferList>;601 602 const Alternative& alt; ///< Alternative being built from603 AssertionSet newNeed; ///< New assertions found from current assertions604 OpenVarSet openVars; ///< Open variables in current context605 std::vector<DeferItem> deferred; ///< Possible deferred assertion resolutions606 const SymTab::Indexer& indexer; ///< Name lookup607 608 AssertionResnState(const Alternative& alt, const OpenVarSet& openVars,609 const SymTab::Indexer& indexer )610 : alt{alt}, have{}, newNeed{}, openVars{openVars}, indexer{indexer} {}611 };612 613 /// Binds a single assertion from a compatible AssertionPack, updating resolution state614 /// as appropriate.615 void bindAssertion( DeclarationWithType* curDecl, AssertionSetValue& assnInfo,616 AssertionResnState& resn, AssertionPack&& match ) {617 DeclarationWithType* candidate = match.cdata.id;618 619 addToIndexer( match.have, resn.indexer );620 resn.newNeed.insert( match.need.begin(), match.need.end() );621 resn.openVars = std::move(match.openVars);622 resn.alt.env = std::move(match.env);623 624 assertf( candidate->get_uniqueId(), "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() );625 for ( auto& a : match.need ) {626 if ( a.second.idChain.empty() ) {627 a.second.idChain = assnInfo.idChain;628 a.second.idChain.push_back( curDecl->get_uniqueId() );629 }630 }631 632 Expression* varExpr = match.cdata.combine( resn.alt.cvtCost );633 varExpr->result = match.adjType;634 635 // follow the current assertion's ID chain to find the correct set of inferred636 // parameters to add the candidate o (i.e. the set of inferred parameters belonging637 // to the entity which requested the assertion parameter)638 InferredParams* inferParams = &resn.alt.expr->inferParams;639 for ( UniqueId id : assnInfo.idChain ) {640 inferParams = (*inferParams)[ id ].inferParams.get();641 }642 643 (*inferParams)[ curDecl->get_uniqueId() ] = ParamEntry{644 candidate->get_uniqueId(), match.adjType, curDecl->get_type(), varExpr };645 }646 647 /// Resolves a single assertion, returning false if no satisfying assertion, binding it648 /// if there is exactly one satisfying assertion, or adding to the defer-list if there649 /// is more than one650 bool resolveAssertion( DeclarationWithType* curDecl, AssertionSetValue& assnInfo,651 AssertionResnState& resn ) {652 // skip unused assertions653 if ( ! assnInfo.isUsed ) return true;654 655 // lookup candidates for this assertion656 std::list< SymTab::Indexer::IdData > candidates;657 decls.lookupId( curDecl->name, candidates );658 659 // find the ones that unify with the desired type660 DeferList matches;661 for ( const auto& cdata : candidates ) {662 DeclarationWithType* candidate = cdata.id;663 664 // build independent unification context for candidate665 AssertionSet have, newNeed;666 TypeEnvironment newEnv{ resn.alt.env };667 OpenVarSet newOpenVars{ resn.openVars };668 Type* adjType = candidate->get_type()->clone();669 adjustExprType( adjType, newEnv, resn.indexer );670 renameTyVars( adjType );671 672 if ( unify( curDecl->get_type(), adjType, newEnv,673 newNeed, have, newOpenVars, resn.indexer ) ) {674 matches.emplace_back( cdata, adjType, std::move(newEnv), std::move(have),675 std::move(newNeed), std::move(newOpenVars) );676 }677 }678 679 // Break if no suitable assertion680 if ( matches.empty() ) return false;681 682 // Defer if too many suitable assertions683 if ( matches.size() > 1 ) {684 resn.deferred.emplace_back( curDecl, assnInfo, std::move(matches) );685 return true;686 }687 688 // otherwise bind current match in ongoing scope689 bindAssertion( curDecl, assnInfo, resn, std::move(matches.front()) );690 691 return true;692 }693 }694 695 574 template< typename OutputIterator > 696 575 void AlternativeFinder::Finder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) { … … 707 586 // ) 708 587 addToIndexer( have, decls ); 709 710 AssertionResnState resn{ newAlt, openVars, indexer };711 712 // resolve assertions in breadth-first-order up to a limited number of levels deep713 int level;714 for ( level = 0; level < recursionLimit; ++level ) {715 // make initial pass at matching assertions716 for ( auto& assn : need ) {717 if ( ! resolveAssertion( assn.first, assn.second, resn ) ) {718 // fail early if any assertion fails to resolve719 return;720 }721 }722 723 // resolve deferred assertions by mutual compatibility and min-cost724 if ( ! resn.deferred.empty() ) {725 // TODO726 assert(false && "TODO: deferred assertions unimplemented");727 728 // reset for next round729 resn.deferred.clear();730 }731 732 // quit resolving assertions if done733 if ( resn.newNeed.empty() ) break;734 735 // otherwise start on next group of recursive assertions736 need.swap( resn.newNeed );737 resn.newNeed.clear();738 }739 if ( level >= recursionLimit ) {740 SemanticError( newAlt.expr->location, "Too many recursive assertions" );741 }742 743 // add completed assertion to output744 *out++ = newAlt;745 746 #if 0747 588 AssertionSet newNeed; 748 589 PRINT( … … 758 599 // *out++ = newAlt; 759 600 // ) 760 #endif761 601 } 762 602 … … 790 630 791 631 ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have, 792 const OpenVarSet& openVars , Cost initCost = Cost::zero)793 : parent(0), expr(nullptr), cost( initCost), env(env), need(need), have(have),632 const OpenVarSet& openVars) 633 : parent(0), expr(nullptr), cost(Cost::zero), env(env), need(need), have(have), 794 634 openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {} 795 635 … … 1083 923 } 1084 924 1085 namespace {1086 1087 struct CountSpecs : public WithVisitorRef<CountSpecs>, WithShortCircuiting {1088 1089 void postvisit(PointerType*) {1090 // mark specialization of base type1091 if ( count >= 0 ) ++count;1092 }1093 1094 void postvisit(ArrayType*) {1095 // mark specialization of base type1096 if ( count >= 0 ) ++count;1097 }1098 1099 void postvisit(ReferenceType*) {1100 // mark specialization of base type -- xxx maybe not?1101 if ( count >= 0 ) ++count;1102 }1103 1104 private:1105 // takes minimum non-negative count over parameter/return list1106 void takeminover( int& mincount, std::list<DeclarationWithType*>& dwts ) {1107 for ( DeclarationWithType* dwt : dwts ) {1108 count = -1;1109 maybeAccept( dwt->get_type(), *visitor );1110 if ( count != -1 && count < mincount ) mincount = count;1111 }1112 }1113 1114 public:1115 void previsit(FunctionType*) {1116 // override default child visiting behaviour1117 visit_children = false;1118 }1119 1120 void postvisit(FunctionType* fty) {1121 // take minimal set value of count over ->returnVals and ->parameters1122 int mincount = std::numeric_limits<int>::max();1123 takeminover( mincount, fty->parameters );1124 takeminover( mincount, fty->returnVals );1125 // add another level to mincount if set1126 count = mincount < std::numeric_limits<int>::max() ? mincount + 1 : -1;1127 }1128 1129 private:1130 // returns minimum non-negative count + 1 over type parameters (-1 if none such)1131 int minover( std::list<Expression*>& parms ) {1132 int mincount = std::numeric_limits<int>::max();1133 for ( Expression* parm : parms ) {1134 count = -1;1135 maybeAccept( parm->get_result(), *visitor );1136 if ( count != -1 && count < mincount ) mincount = count;1137 }1138 return mincount < std::numeric_limits<int>::max() ? mincount + 1 : -1;1139 }1140 1141 public:1142 void previsit(StructInstType*) {1143 // override default child behaviour1144 visit_children = false;1145 }1146 1147 void postvisit(StructInstType* sity) {1148 // look for polymorphic parameters1149 count = minover( sity->parameters );1150 }1151 1152 void previsit(UnionInstType*) {1153 // override default child behaviour1154 visit_children = false;1155 }1156 1157 void postvisit(UnionInstType* uity) {1158 // look for polymorphic parameters1159 count = minover( uity->parameters );1160 }1161 1162 void postvisit(TypeInstType*) {1163 // note polymorphic type (which may be specialized)1164 // xxx - maybe account for open/closed type variables1165 count = 0;1166 }1167 1168 void previsit(TupleType*) {1169 // override default child behaviour1170 visit_children = false;1171 }1172 1173 void postvisit(TupleType* tty) {1174 // take minimum non-negative count1175 int mincount = std::numeric_limits<int>::max();1176 for ( Type* ty : tty->types ) {1177 count = -1;1178 maybeAccept( ty, *visitor );1179 if ( count != -1 && count < mincount ) mincount = count;1180 }1181 // xxx - maybe don't increment, tuple flattening doesn't necessarily specialize1182 count = mincount < std::numeric_limits<int>::max() ? mincount + 1: -1;1183 }1184 1185 int get_count() const { return count >= 0 ? count : 0; }1186 private:1187 int count = -1;1188 };1189 1190 /// Counts the specializations in the types in a function parameter or return list1191 int countSpecs( std::list<DeclarationWithType*>& dwts ) {1192 int k = 0;1193 for ( DeclarationWithType* dwt : dwts ) {1194 PassVisitor<CountSpecs> counter;1195 maybeAccept( dwt->get_type(), *counter.pass.visitor );1196 k += counter.pass.get_count();1197 }1198 return k;1199 }1200 1201 /// Calculates the inherent costs in a function declaration; varCost for the number of1202 /// type variables and specCost for type assertions, as well as PolyType specializations1203 /// in the parameter and return lists.1204 Cost declCost( FunctionType* funcType ) {1205 Cost k = Cost::zero;1206 1207 // add cost of type variables1208 k.incVar( funcType->forall.size() );1209 1210 // subtract cost of type assertions1211 for ( TypeDecl* td : funcType->forall ) {1212 k.decSpec( td->assertions.size() );1213 }1214 1215 // count specialized polymorphic types in parameter/return lists1216 k.decSpec( countSpecs( funcType->parameters ) );1217 k.decSpec( countSpecs( funcType->returnVals ) );1218 1219 return k;1220 }1221 }1222 1223 925 template<typename OutputIterator> 1224 926 void AlternativeFinder::Finder::validateFunctionAlternative( const Alternative &func, … … 1265 967 } 1266 968 1267 // calculate declaration cost of function (+vars-spec)1268 Cost funcCost = declCost( funcType );1269 1270 969 // iteratively build matches, one parameter at a time 1271 970 std::vector<ArgPack> results; 1272 results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars , funcCost} );971 results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } ); 1273 972 std::size_t genStart = 0; 1274 973 … … 1410 1109 } 1411 1110 } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->get_result()->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer) 1412 if ( const EqvClass *eqvClass = func->env.lookup( typeInst->get_name() ) ) {1413 if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass ->type ) ) {1111 if ( ClassRef eqvClass = func->env.lookup( typeInst->get_name() ) ) { 1112 if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.get_bound().type ) ) { 1414 1113 Alternative newFunc( *func ); 1415 1114 referenceToRvalueConversion( newFunc.expr, newFunc.cost );
Note:
See TracChangeset
for help on using the changeset viewer.
