- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/AlternativeFinder.cc
r11094d9 rfae6f21 76 76 77 77 namespace { 78 void printAlts( const AltList &list, std::ostream &os, unsigned int indentAmt = 0 ) { 79 Indenter indent = { Indenter::tabsize, indentAmt }; 78 void printAlts( const AltList &list, std::ostream &os, int indent = 0 ) { 80 79 for ( AltList::const_iterator i = list.begin(); i != list.end(); ++i ) { 81 80 i->print( os, indent ); … … 123 122 ) 124 123 mapPlace->second.isAmbiguous = true; 125 } else {126 PRINT(127 std::cerr << "cost " << candidate->cost << " loses to " << mapPlace->second.candidate->cost << std::endl;128 )129 124 } 130 125 } else { … … 132 127 } 133 128 } 129 130 PRINT( 131 std::cerr << "there are " << selected.size() << " alternatives before elimination" << std::endl; 132 ) 134 133 135 134 // accept the alternatives that were unambiguous … … 146 145 expr->get_result()->accept( global_renamer ); 147 146 } 147 148 void referenceToRvalueConversion( Expression *& expr ) { 149 if ( dynamic_cast< ReferenceType * >( expr->get_result() ) ) { 150 // cast away reference from expr 151 expr = new CastExpr( expr, expr->get_result()->stripReferences()->clone() ); 152 } 153 } 148 154 } // namespace 149 150 void referenceToRvalueConversion( Expression *& expr ) {151 if ( dynamic_cast< ReferenceType * >( expr->get_result() ) ) {152 // cast away reference from expr153 expr = new CastExpr( expr, expr->get_result()->stripReferences()->clone() );154 }155 }156 155 157 156 template< typename InputIterator, typename OutputIterator > … … 176 175 } 177 176 178 void AlternativeFinder::find( Expression *expr, bool adjust, bool prune , bool failFast) {177 void AlternativeFinder::find( Expression *expr, bool adjust, bool prune ) { 179 178 expr->accept( *this ); 180 if ( failFast &&alternatives.empty() ) {179 if ( alternatives.empty() ) { 181 180 throw SemanticError( "No reasonable alternatives for expression ", expr ); 182 181 } 182 for ( AltList::iterator i = alternatives.begin(); i != alternatives.end(); ++i ) { 183 if ( adjust ) { 184 adjustExprType( i->expr->get_result(), i->env, indexer ); 185 } 186 } 183 187 if ( prune ) { 184 auto oldsize = alternatives.size();185 188 PRINT( 186 189 std::cerr << "alternatives before prune:" << std::endl; … … 189 192 AltList::iterator oldBegin = alternatives.begin(); 190 193 pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives ) ); 191 if ( failFast &&alternatives.begin() == oldBegin ) {194 if ( alternatives.begin() == oldBegin ) { 192 195 std::ostringstream stream; 193 196 AltList winners; 194 197 findMinCost( alternatives.begin(), alternatives.end(), back_inserter( winners ) ); 195 stream << "Cannot choose between " << winners.size() << " alternatives for expression \n";198 stream << "Cannot choose between " << winners.size() << " alternatives for expression "; 196 199 expr->print( stream ); 197 stream << "Alternatives are: \n";198 printAlts( winners, stream, 1);200 stream << "Alternatives are:"; 201 printAlts( winners, stream, 8 ); 199 202 throw SemanticError( stream.str() ); 200 203 } 201 204 alternatives.erase( oldBegin, alternatives.end() ); 202 PRINT(203 std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;204 )205 205 PRINT( 206 206 std::cerr << "there are " << alternatives.size() << " alternatives after elimination" << std::endl; 207 207 ) 208 }209 // adjust types after pruning so that types substituted by pruneAlternatives are correctly adjusted210 for ( AltList::iterator i = alternatives.begin(); i != alternatives.end(); ++i ) {211 if ( adjust ) {212 adjustExprType( i->expr->get_result(), i->env, indexer );213 }214 208 } 215 209 … … 221 215 } 222 216 223 void AlternativeFinder::findWithAdjustment( Expression *expr ) { 224 find( expr, true ); 225 } 226 227 void AlternativeFinder::findWithoutPrune( Expression * expr ) { 228 find( expr, true, false ); 229 } 230 231 void AlternativeFinder::maybeFind( Expression * expr ) { 232 find( expr, true, true, false ); 217 void AlternativeFinder::findWithAdjustment( Expression *expr, bool prune ) { 218 find( expr, true, prune ); 233 219 } 234 220 … … 313 299 Cost convCost = conversionCost( actualType, formalType, indexer, env ); 314 300 PRINT( 315 std::cerr << std::endl << "cost is 301 std::cerr << std::endl << "cost is" << convCost << std::endl; 316 302 ) 317 303 if ( convCost == Cost::infinity ) { … … 319 305 } 320 306 convCost.incPoly( polyCost( formalType, env, indexer ) + polyCost( actualType, env, indexer ) ); 321 PRINT(322 std::cerr << "cost with polycost is " << convCost << std::endl;323 )324 307 return convCost; 325 308 } … … 327 310 Cost computeExpressionConversionCost( Expression *& actualExpr, Type * formalType, const SymTab::Indexer &indexer, const TypeEnvironment & env ) { 328 311 Cost convCost = computeConversionCost( actualExpr->result, formalType, indexer, env ); 329 330 // if there is a non-zero conversion cost, ignoring poly cost, then the expression requires conversion. 331 // ignore poly cost for now, since this requires resolution of the cast to infer parameters and this 332 // does not currently work for the reason stated below. 312 // if ( convCost != Cost::zero ) { 313 314 // xxx - temporary -- ignore poly cost, since this causes some polymorphic functions to be cast, which causes the specialize 315 // pass to try to specialize them, which currently does not work. Once that is fixed, remove the next 3 lines and uncomment the 316 // previous line. 333 317 Cost tmpCost = convCost; 334 318 tmpCost.incPoly( -tmpCost.get_polyCost() ); … … 373 357 if ( function->get_isVarArgs() ) { 374 358 convCost.incUnsafe(); 375 PRINT( std::cerr << "end of formals with varargs function: inc unsafe: " << convCost << std::endl; ; )376 359 // convert reference-typed expressions to value-typed expressions 377 360 referenceToRvalueConversion( *actualExpr ); … … 382 365 } 383 366 Type * formalType = (*formal)->get_type(); 367 PRINT( 368 std::cerr << std::endl << "converting "; 369 actualType->print( std::cerr, 8 ); 370 std::cerr << std::endl << " to "; 371 formalType->print( std::cerr, 8 ); 372 std::cerr << std::endl << "environment is: "; 373 alt.env.print( std::cerr, 8 ); 374 std::cerr << std::endl; 375 ) 384 376 convCost += computeExpressionConversionCost( *actualExpr, formalType, indexer, alt.env ); 385 377 ++formal; // can't be in for-loop update because of the continue … … 489 481 Alternative newerAlt( newAlt ); 490 482 newerAlt.env = newEnv; 491 assert f( (*candidate)->get_uniqueId(), "Assertion candidate does not have a unique ID: %s", toString( *candidate ).c_str() );483 assert( (*candidate)->get_uniqueId() ); 492 484 DeclarationWithType *candDecl = static_cast< DeclarationWithType* >( Declaration::declFromId( (*candidate)->get_uniqueId() ) ); 493 485 … … 515 507 std::cerr << std::endl; 516 508 ) 509 ApplicationExpr *appExpr = static_cast< ApplicationExpr* >( newerAlt.expr ); 517 510 // follow the current assertion's ID chain to find the correct set of inferred parameters to add the candidate to (i.e. the set of inferred parameters belonging to the entity which requested the assertion parameter). 518 InferredParams * inferParameters = & newerAlt.expr->get_inferParams();511 InferredParams * inferParameters = &appExpr->get_inferParams(); 519 512 for ( UniqueId id : cur->second.idChain ) { 520 513 inferParameters = (*inferParameters)[ id ].inferParams.get(); … … 581 574 std::vector<unsigned> tupleEls; /// Number of elements in current tuple element(s) 582 575 583 ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have, 576 ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have, 584 577 const OpenVarSet& openVars) 585 578 : actuals(), env(env), need(need), have(have), openVars(openVars), nextArg(0), 586 579 expls(), nextExpl(0), tupleEls() {} 587 580 588 581 /// Starts a new tuple expression 589 582 void beginTuple() { … … 620 613 621 614 /// Instantiates an argument to match a formal, returns false if no results left 622 bool instantiateArgument( Type* formalType, Initializer* initializer, 623 const std::vector< AlternativeFinder >& args, 624 std::vector<ArgPack>& results, std::vector<ArgPack>& nextResults, 615 bool instantiateArgument( Type* formalType, Initializer* initializer, 616 const std::vector< AlternativeFinder >& args, 617 std::vector<ArgPack>& results, std::vector<ArgPack>& nextResults, 625 618 const SymTab::Indexer& indexer ) { 626 619 if ( TupleType* tupleType = dynamic_cast<TupleType*>( formalType ) ) { … … 629 622 for ( Type* type : *tupleType ) { 630 623 // xxx - dropping initializer changes behaviour from previous, but seems correct 631 if ( ! instantiateArgument( type, nullptr, args, results, nextResults, indexer ) ) 624 if ( ! instantiateArgument( type, nullptr, args, results, nextResults, indexer ) ) 632 625 return false; 633 626 } … … 658 651 Type* argType = result.actuals.back().expr->get_result(); 659 652 if ( result.tupleEls.back() == 1 && Tuples::isTtype( argType ) ) { 660 // the case where a ttype value is passed directly is special, e.g. for 653 // the case where a ttype value is passed directly is special, e.g. for 661 654 // argument forwarding purposes 662 655 // xxx - what if passing multiple arguments, last of which is ttype? 663 // xxx - what would happen if unify was changed so that unifying tuple 656 // xxx - what would happen if unify was changed so that unifying tuple 664 657 // types flattened both before unifying lists? then pass in TupleType 665 658 // (ttype) below. … … 671 664 } 672 665 // check unification for ttype before adding to final 673 if ( unify( ttype, argType, result.env, result.need, result.have, 666 if ( unify( ttype, argType, result.env, result.need, result.have, 674 667 result.openVars, indexer ) ) { 675 668 finalResults.push_back( std::move(result) ); … … 684 677 aResult.env.addActual( actual.env, aResult.openVars ); 685 678 Cost cost = actual.cost; 686 679 687 680 // explode argument 688 681 std::vector<Alternative> exploded; 689 682 Tuples::explode( actual, indexer, back_inserter( exploded ) ); 690 683 691 684 // add exploded argument to tuple 692 685 for ( Alternative& aActual : exploded ) { … … 706 699 return ! results.empty(); 707 700 } 708 701 709 702 // iterate each current subresult 710 703 for ( unsigned iResult = 0; iResult < results.size(); ++iResult ) { … … 724 717 std::cerr << std::endl; 725 718 ) 726 727 if ( unify( formalType, actualType, result.env, result.need, result.have, 719 720 if ( unify( formalType, actualType, result.env, result.need, result.have, 728 721 result.openVars, indexer ) ) { 729 722 ++result.nextExpl; … … 736 729 if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) { 737 730 if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) { 738 if ( unify( formalType, cnst->get_type(), result.env, result.need, 731 if ( unify( formalType, cnst->get_type(), result.env, result.need, 739 732 result.have, result.openVars, indexer ) ) { 740 733 nextResults.push_back( std::move(result.withArg( cnstExpr )) ); … … 791 784 results.swap( nextResults ); 792 785 nextResults.clear(); 793 786 794 787 return ! results.empty(); 795 788 } 796 789 797 790 template<typename OutputIterator> 798 void AlternativeFinder::makeFunctionAlternatives( const Alternative &func,799 FunctionType *funcType, const std::vector< AlternativeFinder > &args,791 void AlternativeFinder::makeFunctionAlternatives( const Alternative& func, 792 FunctionType* funcType, const std::vector< AlternativeFinder >& args, 800 793 OutputIterator out ) { 801 794 OpenVarSet funcOpenVars; 802 795 AssertionSet funcNeed, funcHave; 803 TypeEnvironment funcEnv ( func.env );796 TypeEnvironment funcEnv; 804 797 makeUnifiableVars( funcType, funcOpenVars, funcNeed ); 805 // add all type variables as open variables now so that those not used in the parameter 798 // add all type variables as open variables now so that those not used in the parameter 806 799 // list are still considered open. 807 800 funcEnv.add( funcType->get_forall() ); … … 809 802 if ( targetType && ! targetType->isVoid() && ! funcType->get_returnVals().empty() ) { 810 803 // attempt to narrow based on expected target type 811 Type 812 if ( ! unify( returnType, targetType, funcEnv, funcNeed, funcHave, funcOpenVars, 804 Type* returnType = funcType->get_returnVals().front()->get_type(); 805 if ( ! unify( returnType, targetType, funcEnv, funcNeed, funcHave, funcOpenVars, 813 806 indexer ) ) { 814 807 // unification failed, don't pursue this function alternative … … 822 815 for ( DeclarationWithType* formal : funcType->get_parameters() ) { 823 816 ObjectDecl* obj = strict_dynamic_cast< ObjectDecl* >( formal ); 824 if ( ! instantiateArgument( 817 if ( ! instantiateArgument( 825 818 obj->get_type(), obj->get_init(), args, results, nextResults, indexer ) ) 826 819 return; … … 904 897 905 898 std::vector< AlternativeFinder > argAlternatives; 906 findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), 899 findSubExprs( untypedExpr->begin_args(), untypedExpr->end_args(), 907 900 back_inserter( argAlternatives ) ); 908 901 … … 912 905 913 906 // find function operators 914 static NameExpr *opExpr = new NameExpr( "?()" );915 907 AlternativeFinder funcOpFinder( indexer, env ); 916 // it's ok if there aren't any defined function ops 917 funcOpFinder.maybeFind( opExpr); 908 NameExpr *opExpr = new NameExpr( "?()" ); 909 try { 910 funcOpFinder.findWithAdjustment( opExpr ); 911 } catch( SemanticError &e ) { 912 // it's ok if there aren't any defined function ops 913 } 918 914 PRINT( 919 915 std::cerr << "known function ops:" << std::endl; 920 printAlts( funcOpFinder.alternatives, std::cerr, 1);916 printAlts( funcOpFinder.alternatives, std::cerr, 8 ); 921 917 ) 922 918 … … 934 930 Alternative newFunc( *func ); 935 931 referenceToRvalueConversion( newFunc.expr ); 936 makeFunctionAlternatives( newFunc, function, argAlternatives, 932 makeFunctionAlternatives( newFunc, function, argAlternatives, 937 933 std::back_inserter( candidates ) ); 938 934 } … … 943 939 Alternative newFunc( *func ); 944 940 referenceToRvalueConversion( newFunc.expr ); 945 makeFunctionAlternatives( newFunc, function, argAlternatives, 941 makeFunctionAlternatives( newFunc, function, argAlternatives, 946 942 std::back_inserter( candidates ) ); 947 943 } // if 948 944 } // if 949 } 945 } 950 946 } catch ( SemanticError &e ) { 951 947 errors.append( e ); … … 962 958 try { 963 959 // check if type is a pointer to function 964 if ( PointerType* pointer = dynamic_cast<PointerType*>( 960 if ( PointerType* pointer = dynamic_cast<PointerType*>( 965 961 funcOp->expr->get_result()->stripReferences() ) ) { 966 if ( FunctionType* function = 962 if ( FunctionType* function = 967 963 dynamic_cast<FunctionType*>( pointer->get_base() ) ) { 968 964 Alternative newFunc( *funcOp ); 969 965 referenceToRvalueConversion( newFunc.expr ); 970 makeFunctionAlternatives( newFunc, function, argAlternatives, 966 makeFunctionAlternatives( newFunc, function, argAlternatives, 971 967 std::back_inserter( candidates ) ); 972 968 } … … 1007 1003 candidates.splice( candidates.end(), alternatives ); 1008 1004 1009 // use a new list so that alternatives are not examined by addAnonConversions twice. 1010 AltList winners; 1011 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) ); 1005 findMinCost( candidates.begin(), candidates.end(), std::back_inserter( alternatives ) ); 1012 1006 1013 1007 // function may return struct or union value, in which case we need to add alternatives for implicit 1014 1008 // conversions to each of the anonymous members, must happen after findMinCost since anon conversions 1015 1009 // are never the cheapest expression 1016 for ( const Alternative & alt : winners ) {1010 for ( const Alternative & alt : alternatives ) { 1017 1011 addAnonConversions( alt ); 1018 1012 } 1019 alternatives.splice( alternatives.begin(), winners );1020 1013 1021 1014 if ( alternatives.empty() && targetType && ! targetType->isVoid() ) { … … 1035 1028 bool isLvalue( Expression *expr ) { 1036 1029 // xxx - recurse into tuples? 1037 return expr-> result&& ( expr->get_result()->get_lvalue() || dynamic_cast< ReferenceType * >( expr->get_result() ) );1030 return expr->has_result() && ( expr->get_result()->get_lvalue() || dynamic_cast< ReferenceType * >( expr->get_result() ) ); 1038 1031 } 1039 1032 … … 1110 1103 thisCost.incSafe( discardedValues ); 1111 1104 Alternative newAlt( restructureCast( i->expr->clone(), toType ), i->env, i->cost, thisCost ); 1112 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) ); 1105 // xxx - this doesn't work at the moment, since inferParameters requires an ApplicationExpr as the alternative. 1106 // Once this works, it should be possible to infer parameters on a cast expression and specialize any function. 1107 1108 // inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) ); 1109 candidates.emplace_back( std::move( newAlt ) ); 1113 1110 } // if 1114 1111 } // for … … 1126 1123 AlternativeFinder finder( indexer, env ); 1127 1124 // don't prune here, since it's guaranteed all alternatives will have the same type 1128 finder.findWithoutPrune( castExpr->get_arg() ); 1125 // (giving the alternatives different types is half of the point of ConstructorExpr nodes) 1126 finder.findWithAdjustment( castExpr->get_arg(), false ); 1129 1127 for ( Alternative & alt : finder.alternatives ) { 1130 1128 alternatives.push_back( Alternative( … … 1165 1163 PRINT( std::cerr << "nameExpr is " << nameExpr->get_name() << std::endl; ) 1166 1164 for ( std::list< DeclarationWithType* >::iterator i = declList.begin(); i != declList.end(); ++i ) { 1167 VariableExpr newExpr( *i );1165 VariableExpr newExpr( *i, nameExpr->get_argName() ); 1168 1166 alternatives.push_back( Alternative( newExpr.clone(), env, Cost::zero ) ); 1169 1167 PRINT( … … 1400 1398 findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) ); 1401 1399 std::list< AltList > possibilities; 1400 // TODO re-write to use iterative method 1402 1401 combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) ); 1403 1402 for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) { … … 1423 1422 // don't prune here, since it's guaranteed all alternatives will have the same type 1424 1423 // (giving the alternatives different types is half of the point of ConstructorExpr nodes) 1425 finder.findWith outPrune( ctorExpr->get_callExpr());1424 finder.findWithAdjustment( ctorExpr->get_callExpr(), false ); 1426 1425 for ( Alternative & alt : finder.alternatives ) { 1427 1426 alternatives.push_back( Alternative( new ConstructorExpr( alt.expr->clone() ), alt.env, alt.cost ) ); … … 1460 1459 // O(N^2) checks of d-types with e-types 1461 1460 for ( InitAlternative & initAlt : initExpr->get_initAlts() ) { 1462 Type * toType = resolveTypeof( initAlt.type ->clone(), indexer );1461 Type * toType = resolveTypeof( initAlt.type, indexer ); 1463 1462 SymTab::validateType( toType, &indexer ); 1464 1463 adjustExprType( toType, env, indexer ); … … 1489 1488 // count one safe conversion for each value that is thrown away 1490 1489 thisCost.incSafe( discardedValues ); 1491 Alternative newAlt( new InitExpr( restructureCast( alt.expr->clone(), toType ), initAlt.designation->clone() ), newEnv, alt.cost, thisCost ); 1492 inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) ); 1490 candidates.push_back( Alternative( new InitExpr( restructureCast( alt.expr->clone(), toType ), initAlt.designation->clone() ), newEnv, alt.cost, thisCost ) ); 1493 1491 } 1494 1492 }
Note: See TracChangeset
for help on using the changeset viewer.