- File:
-
- 1 edited
-
src/ResolvExpr/CandidateFinder.cpp (modified) (89 diffs)
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/CandidateFinder.cpp
r0536c03 r18e683b 9 9 // Author : Aaron B. Moss 10 10 // Created On : Wed Jun 5 14:30:00 2019 11 // Last Modified By : A ndrew Beach12 // Last Modified On : Tue Oct 1 14:55:00 201913 // Update Count : 211 // Last Modified By : Aaron B. Moss 12 // Last Modified On : Wed Jun 5 14:30:00 2019 13 // Update Count : 1 14 14 // 15 15 … … 43 43 #include "SymTab/Validate.h" // for validateType 44 44 #include "Tuples/Tuples.h" // for handleTupleAssignment 45 #include "InitTweak/InitTweak.h" // for getPointerBase46 47 #include "Common/Stats/Counter.h"48 45 49 46 #define PRINT( text ) if ( resolvep ) { text } … … 57 54 return new ast::CastExpr{ expr, expr->result->stripReferences() }; 58 55 } 59 56 60 57 return expr; 61 58 } … … 64 61 UniqueId globalResnSlot = 0; 65 62 66 Cost computeConversionCost( 67 const ast::Type * argType, const ast::Type * paramType, bool argIsLvalue,68 const ast:: SymbolTable & symtab, const ast::TypeEnvironment & env63 Cost computeConversionCost( 64 const ast::Type * argType, const ast::Type * paramType, const ast::SymbolTable & symtab, 65 const ast::TypeEnvironment & env 69 66 ) { 70 67 PRINT( … … 77 74 std::cerr << std::endl; 78 75 ) 79 Cost convCost = conversionCost( argType, paramType, argIsLvalue,symtab, env );76 Cost convCost = conversionCost( argType, paramType, symtab, env ); 80 77 PRINT( 81 78 std::cerr << std::endl << "cost is " << convCost << std::endl; … … 110 107 111 108 /// Computes conversion cost for a given expression to a given type 112 const ast::Expr * computeExpressionConversionCost( 113 const ast::Expr * arg, const ast::Type * paramType, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env, Cost & outCost 109 const ast::Expr * computeExpressionConversionCost( 110 const ast::Expr * arg, const ast::Type * paramType, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env, Cost & outCost 114 111 ) { 115 Cost convCost = computeConversionCost( 116 arg->result, paramType, arg->get_lvalue(), symtab, env ); 112 Cost convCost = computeConversionCost( arg->result, paramType, symtab, env ); 117 113 outCost += convCost; 118 114 119 // If there is a non-zero conversion cost, ignoring poly cost, then the expression requires 120 // conversion. Ignore poly cost for now, since this requires resolution of the cast to 115 // If there is a non-zero conversion cost, ignoring poly cost, then the expression requires 116 // conversion. Ignore poly cost for now, since this requires resolution of the cast to 121 117 // infer parameters and this does not currently work for the reason stated below 122 118 Cost tmpCost = convCost; … … 127 123 return new ast::CastExpr{ arg, newType }; 128 124 129 // xxx - *should* be able to resolve this cast, but at the moment pointers are not 130 // castable to zero_t, but are implicitly convertible. This is clearly inconsistent, 125 // xxx - *should* be able to resolve this cast, but at the moment pointers are not 126 // castable to zero_t, but are implicitly convertible. This is clearly inconsistent, 131 127 // once this is fixed it should be possible to resolve the cast. 132 // xxx - this isn't working, it appears because type1 (parameter) is seen as widenable, 133 // but it shouldn't be because this makes the conversion from DT* to DT* since 128 // xxx - this isn't working, it appears because type1 (parameter) is seen as widenable, 129 // but it shouldn't be because this makes the conversion from DT* to DT* since 134 130 // commontype(zero_t, DT*) is DT*, rather than nothing 135 131 136 132 // CandidateFinder finder{ symtab, env }; 137 133 // finder.find( arg, ResolvMode::withAdjustment() ); 138 // assertf( finder.candidates.size() > 0, 134 // assertf( finder.candidates.size() > 0, 139 135 // "Somehow castable expression failed to find alternatives." ); 140 // assertf( finder.candidates.size() == 1, 136 // assertf( finder.candidates.size() == 1, 141 137 // "Somehow got multiple alternatives for known cast expression." ); 142 138 // return finder.candidates.front()->expr; … … 147 143 148 144 /// Computes conversion cost for a given candidate 149 Cost computeApplicationConversionCost( 150 CandidateRef cand, const ast::SymbolTable & symtab 145 Cost computeApplicationConversionCost( 146 CandidateRef cand, const ast::SymbolTable & symtab 151 147 ) { 152 148 auto appExpr = cand->expr.strict_as< ast::ApplicationExpr >(); … … 171 167 if ( function->isVarArgs ) { 172 168 convCost.incUnsafe(); 173 PRINT( std::cerr << "end of params with varargs function: inc unsafe: " 169 PRINT( std::cerr << "end of params with varargs function: inc unsafe: " 174 170 << convCost << std::endl; ; ) 175 171 // convert reference-typed expressions into value-typed expressions 176 cand->expr = ast::mutate_field_index( 177 appExpr, &ast::ApplicationExpr::args, i, 172 cand->expr = ast::mutate_field_index( 173 appExpr, &ast::ApplicationExpr::args, i, 178 174 referenceToRvalueConversion( args[i], convCost ) ); 179 175 continue; … … 184 180 // Default arguments should be free - don't include conversion cost. 185 181 // Unwrap them here because they are not relevant to the rest of the system 186 cand->expr = ast::mutate_field_index( 182 cand->expr = ast::mutate_field_index( 187 183 appExpr, &ast::ApplicationExpr::args, i, def->expr ); 188 184 ++param; … … 191 187 192 188 // mark conversion cost and also specialization cost of param type 193 //const ast::Type * paramType = (*param)->get_type();194 cand->expr = ast::mutate_field_index( 195 appExpr, &ast::ApplicationExpr::args, i, 196 computeExpressionConversionCost( 197 args[i], *param, symtab, cand->env, convCost ) );198 convCost.decSpec( specCost( *param) );189 const ast::Type * paramType = (*param)->get_type(); 190 cand->expr = ast::mutate_field_index( 191 appExpr, &ast::ApplicationExpr::args, i, 192 computeExpressionConversionCost( 193 args[i], paramType, symtab, cand->env, convCost ) ); 194 convCost.decSpec( specCost( paramType ) ); 199 195 ++param; // can't be in for-loop update because of the continue 200 196 } … … 202 198 if ( param != params.end() ) return Cost::infinity; 203 199 204 // specialization cost of return types can't be accounted for directly, it disables 200 // specialization cost of return types can't be accounted for directly, it disables 205 201 // otherwise-identical calls, like this example based on auto-newline in the I/O lib: 206 202 // … … 212 208 // mark type variable and specialization cost of forall clause 213 209 convCost.incVar( function->forall.size() ); 214 convCost.decSpec( function->assertions.size() ); 210 for ( const ast::TypeDecl * td : function->forall ) { 211 convCost.decSpec( td->assertions.size() ); 212 } 215 213 216 214 return convCost; 217 215 } 218 216 219 void makeUnifiableVars( 220 const ast:: FunctionType * type, ast::OpenVarSet & unifiableVars,221 ast::AssertionSet & need 217 void makeUnifiableVars( 218 const ast::ParameterizedType * type, ast::OpenVarSet & unifiableVars, 219 ast::AssertionSet & need 222 220 ) { 223 for ( auto &tyvar : type->forall ) {224 unifiableVars[ *tyvar ] = ast::TypeDecl::Data{ tyvar->base};225 }226 for ( auto & assn : type->assertions ) {227 need[ assn ].isUsed = true;221 for ( const ast::TypeDecl * tyvar : type->forall ) { 222 unifiableVars[ tyvar->name ] = ast::TypeDecl::Data{ tyvar }; 223 for ( const ast::DeclWithType * assn : tyvar->assertions ) { 224 need[ assn ].isUsed = true; 225 } 228 226 } 229 227 } … … 256 254 257 255 ArgPack() 258 : parent( 0 ), expr(), cost( Cost::zero ), env(), need(), have(), open(), nextArg( 0 ), 256 : parent( 0 ), expr(), cost( Cost::zero ), env(), need(), have(), open(), nextArg( 0 ), 259 257 tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {} 260 258 259 ArgPack( 260 const ast::TypeEnvironment & env, const ast::AssertionSet & need, 261 const ast::AssertionSet & have, const ast::OpenVarSet & open ) 262 : parent( 0 ), expr(), cost( Cost::zero ), env( env ), need( need ), have( have ), 263 open( open ), nextArg( 0 ), tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {} 264 261 265 ArgPack( 262 const ast::TypeEnvironment & env, const ast::AssertionSet & need, 263 const ast::AssertionSet & have, const ast::OpenVarSet & open ) 264 : parent( 0 ), expr(), cost( Cost::zero ), env( env ), need( need ), have( have ), 265 open( open ), nextArg( 0 ), tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {} 266 267 ArgPack( 268 std::size_t parent, const ast::Expr * expr, ast::TypeEnvironment && env, 269 ast::AssertionSet && need, ast::AssertionSet && have, ast::OpenVarSet && open, 270 unsigned nextArg, unsigned tupleStart = 0, Cost cost = Cost::zero, 266 std::size_t parent, const ast::Expr * expr, ast::TypeEnvironment && env, 267 ast::AssertionSet && need, ast::AssertionSet && have, ast::OpenVarSet && open, 268 unsigned nextArg, unsigned tupleStart = 0, Cost cost = Cost::zero, 271 269 unsigned nextExpl = 0, unsigned explAlt = 0 ) 272 270 : parent(parent), expr( expr ), cost( cost ), env( move( env ) ), need( move( need ) ), 273 271 have( move( have ) ), open( move( open ) ), nextArg( nextArg ), tupleStart( tupleStart ), 274 272 nextExpl( nextExpl ), explAlt( explAlt ) {} 275 273 276 274 ArgPack( 277 const ArgPack & o, ast::TypeEnvironment && env, ast::AssertionSet && need, 275 const ArgPack & o, ast::TypeEnvironment && env, ast::AssertionSet && need, 278 276 ast::AssertionSet && have, ast::OpenVarSet && open, unsigned nextArg, Cost added ) 279 : parent( o.parent ), expr( o.expr ), cost( o.cost + added ), env( move( env ) ), 280 need( move( need ) ), have( move( have ) ), open( move( open ) ), nextArg( nextArg ), 277 : parent( o.parent ), expr( o.expr ), cost( o.cost + added ), env( move( env ) ), 278 need( move( need ) ), have( move( have ) ), open( move( open ) ), nextArg( nextArg ), 281 279 tupleStart( o.tupleStart ), nextExpl( 0 ), explAlt( 0 ) {} 282 280 283 281 /// true if this pack is in the middle of an exploded argument 284 282 bool hasExpl() const { return nextExpl > 0; } … … 288 286 return args[ nextArg-1 ][ explAlt ]; 289 287 } 290 288 291 289 /// Ends a tuple expression, consolidating the appropriate args 292 290 void endTuple( const std::vector< ArgPack > & packs ) { … … 309 307 310 308 /// Instantiates an argument to match a parameter, returns false if no matching results left 311 bool instantiateArgument( 312 const ast::Type * paramType, const ast::Init * init, const ExplodedArgs_new & args, 313 std::vector< ArgPack > & results, std::size_t & genStart, const ast::SymbolTable & symtab, 314 unsigned nTuples = 0 309 bool instantiateArgument( 310 const ast::Type * paramType, const ast::Init * init, const ExplodedArgs_new & args, 311 std::vector< ArgPack > & results, std::size_t & genStart, const ast::SymbolTable & symtab, 312 unsigned nTuples = 0 315 313 ) { 316 314 if ( auto tupleType = dynamic_cast< const ast::TupleType * >( paramType ) ) { … … 320 318 // xxx - dropping initializer changes behaviour from previous, but seems correct 321 319 // ^^^ need to handle the case where a tuple has a default argument 322 if ( ! instantiateArgument( 320 if ( ! instantiateArgument( 323 321 type, nullptr, args, results, genStart, symtab, nTuples ) ) return false; 324 322 nTuples = 0; … … 331 329 } else if ( const ast::TypeInstType * ttype = Tuples::isTtype( paramType ) ) { 332 330 // paramType is a ttype, consumes all remaining arguments 333 331 334 332 // completed tuples; will be spliced to end of results to finish 335 333 std::vector< ArgPack > finalResults{}; … … 344 342 for ( std::size_t i = genStart; i < genEnd; ++i ) { 345 343 unsigned nextArg = results[i].nextArg; 346 344 347 345 // use next element of exploded tuple if present 348 346 if ( results[i].hasExpl() ) { … … 354 352 results.emplace_back( 355 353 i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ), 356 copy( results[i].need ), copy( results[i].have ), 354 copy( results[i].need ), copy( results[i].have ), 357 355 copy( results[i].open ), nextArg, nTuples, Cost::zero, nextExpl, 358 356 results[i].explAlt ); … … 372 370 // push empty tuple expression 373 371 newResult.parent = i; 374 newResult.expr = new ast::TupleExpr{ CodeLocation{}, {} }; 372 std::vector< ast::ptr< ast::Expr > > emptyList; 373 newResult.expr = 374 new ast::TupleExpr{ CodeLocation{}, move( emptyList ) }; 375 375 argType = newResult.expr->result; 376 376 } else { … … 400 400 401 401 // check unification for ttype before adding to final 402 if ( 403 unify( 402 if ( 403 unify( 404 404 ttype, argType, newResult.env, newResult.need, newResult.have, 405 newResult.open, symtab ) 405 newResult.open, symtab ) 406 406 ) { 407 407 finalResults.emplace_back( move( newResult ) ); … … 424 424 if ( expl.exprs.empty() ) { 425 425 results.emplace_back( 426 results[i], move( env ), copy( results[i].need ), 426 results[i], move( env ), copy( results[i].need ), 427 427 copy( results[i].have ), move( open ), nextArg + 1, expl.cost ); 428 428 429 429 continue; 430 430 } … … 432 432 // add new result 433 433 results.emplace_back( 434 i, expl.exprs.front(), move( env ), copy( results[i].need ), 435 copy( results[i].have ), move( open ), nextArg + 1, nTuples, 434 i, expl.exprs.front(), move( env ), copy( results[i].need ), 435 copy( results[i].have ), move( open ), nextArg + 1, nTuples, 436 436 expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); 437 437 } … … 479 479 480 480 results.emplace_back( 481 i, expr, move( env ), move( need ), move( have ), move( open ), nextArg, 481 i, expr, move( env ), move( need ), move( have ), move( open ), nextArg, 482 482 nTuples, Cost::zero, nextExpl, results[i].explAlt ); 483 483 } … … 495 495 if ( unify( paramType, cnst->result, env, need, have, open, symtab ) ) { 496 496 results.emplace_back( 497 i, new ast::DefaultArgExpr{ cnst->location, cnst }, move( env ), 497 i, new ast::DefaultArgExpr{ cnst->location, cnst }, move( env ), 498 498 move( need ), move( have ), move( open ), nextArg, nTuples ); 499 499 } … … 517 517 if ( expl.exprs.empty() ) { 518 518 results.emplace_back( 519 results[i], move( env ), move( need ), move( have ), move( open ), 519 results[i], move( env ), move( need ), move( have ), move( open ), 520 520 nextArg + 1, expl.cost ); 521 521 522 522 continue; 523 523 } … … 539 539 // add new result 540 540 results.emplace_back( 541 i, expr, move( env ), move( need ), move( have ), move( open ), 541 i, expr, move( env ), move( need ), move( have ), move( open ), 542 542 nextArg + 1, nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); 543 543 } … … 548 548 genStart = genEnd; 549 549 550 return genEnd != results.size(); // were any new results added?550 return genEnd != results.size(); 551 551 } 552 552 553 553 /// Generate a cast expression from `arg` to `toType` 554 const ast::Expr * restructureCast( 554 const ast::Expr * restructureCast( 555 555 ast::ptr< ast::Expr > & arg, const ast::Type * toType, ast::GeneratedFlag isGenerated = ast::GeneratedCast 556 556 ) { 557 if ( 558 arg->result->size() > 1 559 && ! toType->isVoid() 560 && ! dynamic_cast< const ast::ReferenceType * >( toType ) 557 if ( 558 arg->result->size() > 1 559 && ! toType->isVoid() 560 && ! dynamic_cast< const ast::ReferenceType * >( toType ) 561 561 ) { 562 // Argument is a tuple and the target type is neither void nor a reference. Cast each 563 // member of the tuple to its corresponding target type, producing the tuple of those 564 // cast expressions. If there are more components of the tuple than components in the 565 // target type, then excess components do not come out in the result expression (but 562 // Argument is a tuple and the target type is neither void nor a reference. Cast each 563 // member of the tuple to its corresponding target type, producing the tuple of those 564 // cast expressions. If there are more components of the tuple than components in the 565 // target type, then excess components do not come out in the result expression (but 566 566 // UniqueExpr ensures that the side effects will still be produced) 567 567 if ( Tuples::maybeImpureIgnoreUnique( arg ) ) { 568 // expressions which may contain side effects require a single unique instance of 568 // expressions which may contain side effects require a single unique instance of 569 569 // the expression 570 570 arg = new ast::UniqueExpr{ arg->location, arg }; … … 574 574 // cast each component 575 575 ast::ptr< ast::Expr > idx = new ast::TupleIndexExpr{ arg->location, arg, i }; 576 components.emplace_back( 576 components.emplace_back( 577 577 restructureCast( idx, toType->getComponent( i ), isGenerated ) ); 578 578 } … … 594 594 595 595 /// Actually visits expressions to find their candidate interpretations 596 class Finder final : public ast::WithShortCircuiting { 596 struct Finder final : public ast::WithShortCircuiting { 597 CandidateFinder & selfFinder; 597 598 const ast::SymbolTable & symtab; 598 public:599 static size_t traceId;600 CandidateFinder & selfFinder;601 599 CandidateList & candidates; 602 600 const ast::TypeEnvironment & tenv; 603 601 ast::ptr< ast::Type > & targetType; 604 602 605 enum Errors {606 NotFound,607 NoMatch,608 ArgsToFew,609 ArgsToMany,610 RetsToFew,611 RetsToMany,612 NoReason613 };614 615 struct {616 Errors code = NotFound;617 } reason;618 619 603 Finder( CandidateFinder & f ) 620 : s ymtab( f.localSyms ), selfFinder( f ), candidates( f.candidates ), tenv( f.env ),604 : selfFinder( f ), symtab( f.symtab ), candidates( f.candidates ), tenv( f.env ), 621 605 targetType( f.targetType ) {} 622 606 623 607 void previsit( const ast::Node * ) { visit_children = false; } 624 608 … … 627 611 void addCandidate( Args &&... args ) { 628 612 candidates.emplace_back( new Candidate{ std::forward<Args>( args )... } ); 629 reason.code = NoReason;630 613 } 631 614 … … 656 639 657 640 /// Completes a function candidate with arguments located 658 void validateFunctionCandidate( 659 const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results, 660 CandidateList & out 641 void validateFunctionCandidate( 642 const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results, 643 CandidateList & out 661 644 ) { 662 ast::ApplicationExpr * appExpr = 645 ast::ApplicationExpr * appExpr = 663 646 new ast::ApplicationExpr{ func->expr->location, func->expr }; 664 647 // sum cost and accumulate arguments … … 674 657 appExpr->args = move( vargs ); 675 658 // build and validate new candidate 676 auto newCand = 659 auto newCand = 677 660 std::make_shared<Candidate>( appExpr, result.env, result.open, result.need, cost ); 678 661 PRINT( … … 686 669 /// Builds a list of candidates for a function, storing them in out 687 670 void makeFunctionCandidates( 688 const CandidateRef & func, const ast::FunctionType * funcType, 671 const CandidateRef & func, const ast::FunctionType * funcType, 689 672 const ExplodedArgs_new & args, CandidateList & out 690 673 ) { … … 693 676 ast::TypeEnvironment funcEnv{ func->env }; 694 677 makeUnifiableVars( funcType, funcOpen, funcNeed ); 695 // add all type variables as open variables now so that those not used in the 696 // parameterlist are still considered open678 // add all type variables as open variables now so that those not used in the parameter 679 // list are still considered open 697 680 funcEnv.add( funcType->forall ); 698 681 699 682 if ( targetType && ! targetType->isVoid() && ! funcType->returns.empty() ) { 700 683 // attempt to narrow based on expected target type 701 const ast::Type * returnType = funcType->returns.front() ;702 if ( ! unify( 703 returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen, symtab ) 684 const ast::Type * returnType = funcType->returns.front()->get_type(); 685 if ( ! unify( 686 returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen, symtab ) 704 687 ) { 705 688 // unification failed, do not pursue this candidate … … 713 696 std::size_t genStart = 0; 714 697 715 // xxx - how to handle default arg after change to ftype representation? 716 if (const ast::VariableExpr * varExpr = func->expr.as<ast::VariableExpr>()) { 717 if (const ast::FunctionDecl * funcDecl = varExpr->var.as<ast::FunctionDecl>()) { 718 // function may have default args only if directly calling by name 719 // must use types on candidate however, due to RenameVars substitution 720 auto nParams = funcType->params.size(); 721 722 for (size_t i=0; i<nParams; ++i) { 723 auto obj = funcDecl->params[i].strict_as<ast::ObjectDecl>(); 724 if (!instantiateArgument( 725 funcType->params[i], obj->init, args, results, genStart, symtab)) return; 726 } 727 goto endMatch; 728 } 729 } 730 for ( const auto & param : funcType->params ) { 731 // Try adding the arguments corresponding to the current parameter to the existing 698 for ( const ast::DeclWithType * param : funcType->params ) { 699 auto obj = strict_dynamic_cast< const ast::ObjectDecl * >( param ); 700 // Try adding the arguments corresponding to the current parameter to the existing 732 701 // matches 733 // no default args for indirect calls 734 if ( ! instantiateArgument( 735 param, nullptr, args, results, genStart, symtab ) ) return; 736 } 737 738 endMatch: 702 if ( ! instantiateArgument( 703 obj->type, obj->init, args, results, genStart, symtab ) ) return; 704 } 705 739 706 if ( funcType->isVarArgs ) { 740 707 // append any unused arguments to vararg pack … … 783 750 if ( expl.exprs.empty() ) { 784 751 results.emplace_back( 785 results[i], move( env ), copy( results[i].need ), 786 copy( results[i].have ), move( open ), nextArg + 1, 752 results[i], move( env ), copy( results[i].need ), 753 copy( results[i].have ), move( open ), nextArg + 1, 787 754 expl.cost ); 788 755 … … 793 760 results.emplace_back( 794 761 i, expl.exprs.front(), move( env ), copy( results[i].need ), 795 copy( results[i].have ), move( open ), nextArg + 1, 0, expl.cost, 762 copy( results[i].have ), move( open ), nextArg + 1, 0, expl.cost, 796 763 expl.exprs.size() == 1 ? 0 : 1, j ); 797 764 } … … 813 780 /// Adds implicit struct-conversions to the alternative list 814 781 void addAnonConversions( const CandidateRef & cand ) { 815 // adds anonymous member interpretations whenever an aggregate value type is seen. 816 // it's okay for the aggregate expression to have reference type -- cast it to the 782 // adds anonymous member interpretations whenever an aggregate value type is seen. 783 // it's okay for the aggregate expression to have reference type -- cast it to the 817 784 // base type to treat the aggregate as the referenced value 818 785 ast::ptr< ast::Expr > aggrExpr( cand->expr ); 819 786 ast::ptr< ast::Type > & aggrType = aggrExpr.get_and_mutate()->result; 820 787 cand->env.apply( aggrType ); 821 788 822 789 if ( aggrType.as< ast::ReferenceType >() ) { 823 790 aggrExpr = new ast::CastExpr{ aggrExpr, aggrType->stripReferences() }; … … 832 799 833 800 /// Adds aggregate member interpretations 834 void addAggMembers( 835 const ast:: BaseInstType * aggrInst, const ast::Expr * expr,836 const Candidate & cand, const Cost & addedCost, const std::string & name 801 void addAggMembers( 802 const ast::ReferenceToType * aggrInst, const ast::Expr * expr, 803 const Candidate & cand, const Cost & addedCost, const std::string & name 837 804 ) { 838 805 for ( const ast::Decl * decl : aggrInst->lookup( name ) ) { 839 806 auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( decl ); 840 CandidateRef newCand = std::make_shared<Candidate>( 807 CandidateRef newCand = std::make_shared<Candidate>( 841 808 cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost ); 842 // add anonymous member interpretations whenever an aggregate value type is seen 809 // add anonymous member interpretations whenever an aggregate value type is seen 843 810 // as a member expression 844 811 addAnonConversions( newCand ); … … 848 815 849 816 /// Adds tuple member interpretations 850 void addTupleMembers( 851 const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand, 852 const Cost & addedCost, const ast::Expr * member 817 void addTupleMembers( 818 const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand, 819 const Cost & addedCost, const ast::Expr * member 853 820 ) { 854 821 if ( auto constantExpr = dynamic_cast< const ast::ConstantExpr * >( member ) ) { 855 // get the value of the constant expression as an int, must be between 0 and the 822 // get the value of the constant expression as an int, must be between 0 and the 856 823 // length of the tuple to have meaning 857 824 long long val = constantExpr->intValue(); 858 825 if ( val >= 0 && (unsigned long long)val < tupleType->size() ) { 859 826 addCandidate( 860 cand, new ast::TupleIndexExpr{ expr->location, expr, (unsigned)val }, 827 cand, new ast::TupleIndexExpr{ expr->location, expr, (unsigned)val }, 861 828 addedCost ); 862 829 } … … 865 832 866 833 void postvisit( const ast::UntypedExpr * untypedExpr ) { 867 std::vector< CandidateFinder > argCandidates = 834 CandidateFinder funcFinder{ symtab, tenv }; 835 funcFinder.find( untypedExpr->func, ResolvMode::withAdjustment() ); 836 // short-circuit if no candidates 837 if ( funcFinder.candidates.empty() ) return; 838 839 std::vector< CandidateFinder > argCandidates = 868 840 selfFinder.findSubExprs( untypedExpr->args ); 869 841 870 842 // take care of possible tuple assignments 871 843 // if not tuple assignment, handled as normal function call 872 844 Tuples::handleTupleAssignment( selfFinder, untypedExpr, argCandidates ); 873 874 CandidateFinder funcFinder{ symtab, tenv };875 if (auto nameExpr = untypedExpr->func.as<ast::NameExpr>()) {876 auto kind = ast::SymbolTable::getSpecialFunctionKind(nameExpr->name);877 if (kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS) {878 assertf(!argCandidates.empty(), "special function call without argument");879 for (auto & firstArgCand: argCandidates[0]) {880 ast::ptr<ast::Type> argType = firstArgCand->expr->result;881 firstArgCand->env.apply(argType);882 // strip references883 // xxx - is this correct?884 while (argType.as<ast::ReferenceType>()) argType = argType.as<ast::ReferenceType>()->base;885 886 // convert 1-tuple to plain type887 if (auto tuple = argType.as<ast::TupleType>()) {888 if (tuple->size() == 1) {889 argType = tuple->types[0];890 }891 }892 893 // if argType is an unbound type parameter, all special functions need to be searched.894 if (isUnboundType(argType)) {895 funcFinder.otypeKeys.clear();896 break;897 }898 899 if (argType.as<ast::PointerType>()) funcFinder.otypeKeys.insert(Mangle::Encoding::pointer);900 else funcFinder.otypeKeys.insert(Mangle::mangle(argType, Mangle::NoGenericParams | Mangle::Type));901 }902 }903 }904 // if candidates are already produced, do not fail905 // xxx - is it possible that handleTupleAssignment and main finder both produce candidates?906 // this means there exists ctor/assign functions with a tuple as first parameter.907 ResolvMode mode = {908 true, // adjust909 !untypedExpr->func.as<ast::NameExpr>(), // prune if not calling by name910 selfFinder.candidates.empty() // failfast if other options are not found911 };912 funcFinder.find( untypedExpr->func, mode );913 // short-circuit if no candidates914 // if ( funcFinder.candidates.empty() ) return;915 916 reason.code = NoMatch;917 845 918 846 // find function operators … … 949 877 if ( auto function = pointer->base.as< ast::FunctionType >() ) { 950 878 CandidateRef newFunc{ new Candidate{ *func } }; 951 newFunc->expr = 879 newFunc->expr = 952 880 referenceToRvalueConversion( newFunc->expr, newFunc->cost ); 953 881 makeFunctionCandidates( newFunc, function, argExpansions, found ); 954 882 } 955 } else if ( 956 auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult ) 883 } else if ( 884 auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult ) 957 885 ) { 958 if ( const ast::EqvClass * clz = func->env.lookup( *inst) ) {886 if ( const ast::EqvClass * clz = func->env.lookup( inst->name ) ) { 959 887 if ( auto function = clz->bound.as< ast::FunctionType >() ) { 960 888 CandidateRef newFunc{ new Candidate{ *func } }; 961 newFunc->expr = 889 newFunc->expr = 962 890 referenceToRvalueConversion( newFunc->expr, newFunc->cost ); 963 891 makeFunctionCandidates( newFunc, function, argExpansions, found ); … … 973 901 std::vector< ExplodedArg > funcE; 974 902 funcE.reserve( funcFinder.candidates.size() ); 975 for ( const CandidateRef & func : funcFinder ) { 903 for ( const CandidateRef & func : funcFinder ) { 976 904 funcE.emplace_back( *func, symtab ); 977 905 } … … 985 913 if ( auto function = pointer->base.as< ast::FunctionType >() ) { 986 914 CandidateRef newOp{ new Candidate{ *op} }; 987 newOp->expr = 915 newOp->expr = 988 916 referenceToRvalueConversion( newOp->expr, newOp->cost ); 989 917 makeFunctionCandidates( newOp, function, argExpansions, found ); … … 994 922 } 995 923 996 // Implement SFINAE; resolution errors are only errors if there aren't any non-error 924 // Implement SFINAE; resolution errors are only errors if there aren't any non-error 997 925 // candidates 998 926 if ( found.empty() && ! errors.isEmpty() ) { throw errors; } … … 1006 934 auto pointer = appExpr->func->result.strict_as< ast::PointerType >(); 1007 935 auto function = pointer->base.strict_as< ast::FunctionType >(); 1008 936 1009 937 std::cerr << "Case +++++++++++++ " << appExpr->func << std::endl; 1010 938 std::cerr << "parameters are:" << std::endl; … … 1029 957 promoteCvtCost( winners ); 1030 958 1031 // function may return a struct/union value, in which case we need to add candidates 1032 // for implicit conversions to each of the anonymous members, which must happen after 959 // function may return a struct/union value, in which case we need to add candidates 960 // for implicit conversions to each of the anonymous members, which must happen after 1033 961 // `findMinCost`, since anon conversions are never the cheapest 1034 962 for ( const CandidateRef & c : winners ) { … … 1038 966 1039 967 if ( candidates.empty() && targetType && ! targetType->isVoid() ) { 1040 // If resolution is unsuccessful with a target type, try again without, since it 968 // If resolution is unsuccessful with a target type, try again without, since it 1041 969 // will sometimes succeed when it wouldn't with a target type binding. 1042 970 // For example: … … 1055 983 /// true if expression is an lvalue 1056 984 static bool isLvalue( const ast::Expr * x ) { 1057 return x->result && ( x-> get_lvalue() || x->result.as< ast::ReferenceType >() );985 return x->result && ( x->result->is_lvalue() || x->result.as< ast::ReferenceType >() ); 1058 986 } 1059 987 … … 1061 989 CandidateFinder finder{ symtab, tenv }; 1062 990 finder.find( addressExpr->arg ); 1063 1064 if( finder.candidates.empty() ) return;1065 1066 reason.code = NoMatch;1067 1068 991 for ( CandidateRef & r : finder.candidates ) { 1069 992 if ( ! isLvalue( r->expr ) ) continue; … … 1080 1003 assert( toType ); 1081 1004 toType = resolveTypeof( toType, symtab ); 1082 //toType = SymTab::validateType( castExpr->location, toType, symtab );1005 toType = SymTab::validateType( castExpr->location, toType, symtab ); 1083 1006 toType = adjustExprType( toType, tenv, symtab ); 1084 1007 1085 1008 CandidateFinder finder{ symtab, tenv, toType }; 1086 1009 finder.find( castExpr->arg, ResolvMode::withAdjustment() ); 1087 1088 if( !finder.candidates.empty() ) reason.code = NoMatch;1089 1010 1090 1011 CandidateList matches; … … 1095 1016 cand->env.extractOpenVars( open ); 1096 1017 1097 // It is possible that a cast can throw away some values in a multiply-valued 1098 // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of the 1099 // subexpression results that are cast directly. The candidate is invalid if it 1018 // It is possible that a cast can throw away some values in a multiply-valued 1019 // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of the 1020 // subexpression results that are cast directly. The candidate is invalid if it 1100 1021 // has fewer results than there are types to cast to. 1101 1022 int discardedValues = cand->expr->result->size() - toType->size(); … … 1104 1025 // unification run for side-effects 1105 1026 unify( toType, cand->expr->result, cand->env, need, have, open, symtab ); 1106 Cost thisCost = 1107 (castExpr->isGenerated == ast::GeneratedFlag::GeneratedCast) 1108 ? conversionCost( cand->expr->result, toType, cand->expr->get_lvalue(), symtab, cand->env ) 1109 : castCost( cand->expr->result, toType, cand->expr->get_lvalue(), symtab, cand->env ); 1110 1027 Cost thisCost = castCost( cand->expr->result, toType, symtab, cand->env ); 1111 1028 PRINT( 1112 1029 std::cerr << "working on cast with result: " << toType << std::endl; … … 1120 1037 // count one safe conversion for each value that is thrown away 1121 1038 thisCost.incSafe( discardedValues ); 1122 CandidateRef newCand = std::make_shared<Candidate>( 1123 restructureCast( cand->expr, toType, castExpr->isGenerated ), 1124 copy( cand->env ), move( open ), move( need ), cand->cost, 1039 CandidateRef newCand = std::make_shared<Candidate>( 1040 restructureCast( cand->expr, toType, castExpr->isGenerated ), 1041 copy( cand->env ), move( open ), move( need ), cand->cost, 1125 1042 cand->cost + thisCost ); 1126 1043 inferParameters( newCand, matches ); … … 1140 1057 finder.find( castExpr->arg, ResolvMode::withoutPrune() ); 1141 1058 for ( CandidateRef & r : finder.candidates ) { 1142 addCandidate( 1143 *r, 1059 addCandidate( 1060 *r, 1144 1061 new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } ); 1145 1062 } 1146 }1147 1148 void postvisit( const ast::KeywordCastExpr * castExpr ) {1149 const auto & loc = castExpr->location;1150 assertf( castExpr->result, "Cast target should have been set in Validate." );1151 auto ref = castExpr->result.strict_as<ast::ReferenceType>();1152 auto inst = ref->base.strict_as<ast::StructInstType>();1153 auto target = inst->base.get();1154 1155 CandidateFinder finder{ symtab, tenv };1156 1157 auto pick_alternatives = [target, this](CandidateList & found, bool expect_ref) {1158 for(auto & cand : found) {1159 const ast::Type * expr = cand->expr->result.get();1160 if(expect_ref) {1161 auto res = dynamic_cast<const ast::ReferenceType*>(expr);1162 if(!res) { continue; }1163 expr = res->base.get();1164 }1165 1166 if(auto insttype = dynamic_cast<const ast::TypeInstType*>(expr)) {1167 auto td = cand->env.lookup(*insttype);1168 if(!td) { continue; }1169 expr = td->bound.get();1170 }1171 1172 if(auto base = dynamic_cast<const ast::StructInstType*>(expr)) {1173 if(base->base == target) {1174 candidates.push_back( std::move(cand) );1175 reason.code = NoReason;1176 }1177 }1178 }1179 };1180 1181 try {1182 // Attempt 1 : turn (thread&)X into ($thread&)X.__thrd1183 // Clone is purely for memory management1184 std::unique_ptr<const ast::Expr> tech1 { new ast::UntypedMemberExpr(loc, new ast::NameExpr(loc, castExpr->concrete_target.field), castExpr->arg) };1185 1186 // don't prune here, since it's guaranteed all alternatives will have the same type1187 finder.find( tech1.get(), ResolvMode::withoutPrune() );1188 pick_alternatives(finder.candidates, false);1189 1190 return;1191 } catch(SemanticErrorException & ) {}1192 1193 // Fallback : turn (thread&)X into ($thread&)get_thread(X)1194 std::unique_ptr<const ast::Expr> fallback { ast::UntypedExpr::createDeref(loc, new ast::UntypedExpr(loc, new ast::NameExpr(loc, castExpr->concrete_target.getter), { castExpr->arg })) };1195 // don't prune here, since it's guaranteed all alternatives will have the same type1196 finder.find( fallback.get(), ResolvMode::withoutPrune() );1197 1198 pick_alternatives(finder.candidates, true);1199 1200 // Whatever happens here, we have no more fallbacks1201 1063 } 1202 1064 … … 1205 1067 aggFinder.find( memberExpr->aggregate, ResolvMode::withAdjustment() ); 1206 1068 for ( CandidateRef & agg : aggFinder.candidates ) { 1207 // it's okay for the aggregate expression to have reference type -- cast it to the 1069 // it's okay for the aggregate expression to have reference type -- cast it to the 1208 1070 // base type to treat the aggregate as the referenced value 1209 1071 Cost addedCost = Cost::zero; … … 1212 1074 // find member of the given type 1213 1075 if ( auto structInst = agg->expr->result.as< ast::StructInstType >() ) { 1214 addAggMembers( 1076 addAggMembers( 1215 1077 structInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) ); 1216 1078 } else if ( auto unionInst = agg->expr->result.as< ast::UnionInstType >() ) { 1217 addAggMembers( 1079 addAggMembers( 1218 1080 unionInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) ); 1219 1081 } else if ( auto tupleType = agg->expr->result.as< ast::TupleType >() ) { … … 1228 1090 1229 1091 void postvisit( const ast::NameExpr * nameExpr ) { 1230 std::vector< ast::SymbolTable::IdData > declList; 1231 if (!selfFinder.otypeKeys.empty()) { 1232 auto kind = ast::SymbolTable::getSpecialFunctionKind(nameExpr->name); 1233 assertf(kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS, "special lookup with non-special target: %s", nameExpr->name.c_str()); 1234 1235 for (auto & otypeKey: selfFinder.otypeKeys) { 1236 auto result = symtab.specialLookupId(kind, otypeKey); 1237 declList.insert(declList.end(), std::make_move_iterator(result.begin()), std::make_move_iterator(result.end())); 1238 } 1239 } 1240 else { 1241 declList = symtab.lookupId( nameExpr->name ); 1242 } 1092 std::vector< ast::SymbolTable::IdData > declList = symtab.lookupId( nameExpr->name ); 1243 1093 PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; ) 1244 1245 if( declList.empty() ) return;1246 1247 reason.code = NoMatch;1248 1249 1094 for ( auto & data : declList ) { 1250 1095 Cost cost = Cost::zero; … … 1252 1097 1253 1098 CandidateRef newCand = std::make_shared<Candidate>( 1254 newExpr, copy( tenv ), ast::OpenVarSet{}, ast::AssertionSet{}, Cost::zero, 1099 newExpr, copy( tenv ), ast::OpenVarSet{}, ast::AssertionSet{}, Cost::zero, 1255 1100 cost ); 1256 1101 PRINT( … … 1262 1107 std::cerr << std::endl; 1263 1108 ) 1264 newCand->expr = ast::mutate_field( 1265 newCand->expr.get(), &ast::Expr::result, 1109 newCand->expr = ast::mutate_field( 1110 newCand->expr.get(), &ast::Expr::result, 1266 1111 renameTyVars( newCand->expr->result ) ); 1267 // add anonymous member interpretations whenever an aggregate value type is seen 1112 // add anonymous member interpretations whenever an aggregate value type is seen 1268 1113 // as a name expression 1269 1114 addAnonConversions( newCand ); … … 1275 1120 // not sufficient to just pass `variableExpr` here, type might have changed since 1276 1121 // creation 1277 addCandidate( 1122 addCandidate( 1278 1123 new ast::VariableExpr{ variableExpr->location, variableExpr->var }, tenv ); 1279 1124 } … … 1285 1130 void postvisit( const ast::SizeofExpr * sizeofExpr ) { 1286 1131 if ( sizeofExpr->type ) { 1287 addCandidate( 1288 new ast::SizeofExpr{ 1289 sizeofExpr->location, resolveTypeof( sizeofExpr->type, symtab ) }, 1132 addCandidate( 1133 new ast::SizeofExpr{ 1134 sizeofExpr->location, resolveTypeof( sizeofExpr->type, symtab ) }, 1290 1135 tenv ); 1291 1136 } else { … … 1296 1141 CandidateList winners = findMinCost( finder.candidates ); 1297 1142 if ( winners.size() != 1 ) { 1298 SemanticError( 1143 SemanticError( 1299 1144 sizeofExpr->expr.get(), "Ambiguous expression in sizeof operand: " ); 1300 1145 } … … 1309 1154 void postvisit( const ast::AlignofExpr * alignofExpr ) { 1310 1155 if ( alignofExpr->type ) { 1311 addCandidate( 1312 new ast::AlignofExpr{ 1313 alignofExpr->location, resolveTypeof( alignofExpr->type, symtab ) }, 1156 addCandidate( 1157 new ast::AlignofExpr{ 1158 alignofExpr->location, resolveTypeof( alignofExpr->type, symtab ) }, 1314 1159 tenv ); 1315 1160 } else { … … 1320 1165 CandidateList winners = findMinCost( finder.candidates ); 1321 1166 if ( winners.size() != 1 ) { 1322 SemanticError( 1167 SemanticError( 1323 1168 alignofExpr->expr.get(), "Ambiguous expression in alignof operand: " ); 1324 1169 } … … 1327 1172 choice->expr = referenceToRvalueConversion( choice->expr, choice->cost ); 1328 1173 choice->cost = Cost::zero; 1329 addCandidate( 1174 addCandidate( 1330 1175 *choice, new ast::AlignofExpr{ alignofExpr->location, choice->expr } ); 1331 1176 } … … 1333 1178 1334 1179 void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) { 1335 const ast:: BaseInstType * aggInst;1180 const ast::ReferenceToType * aggInst; 1336 1181 if (( aggInst = offsetofExpr->type.as< ast::StructInstType >() )) ; 1337 1182 else if (( aggInst = offsetofExpr->type.as< ast::UnionInstType >() )) ; … … 1340 1185 for ( const ast::Decl * member : aggInst->lookup( offsetofExpr->member ) ) { 1341 1186 auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( member ); 1342 addCandidate( 1187 addCandidate( 1343 1188 new ast::OffsetofExpr{ offsetofExpr->location, aggInst, dwt }, tenv ); 1344 1189 } … … 1361 1206 finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() ); 1362 1207 if ( finder2.candidates.empty() ) return; 1363 1364 reason.code = NoMatch;1365 1208 1366 1209 for ( const CandidateRef & r1 : finder1.candidates ) { … … 1375 1218 1376 1219 addCandidate( 1377 new ast::LogicalExpr{ 1220 new ast::LogicalExpr{ 1378 1221 logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd }, 1379 1222 move( env ), move( open ), move( need ), r1->cost + r2->cost ); … … 1397 1240 finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() ); 1398 1241 if ( finder3.candidates.empty() ) return; 1399 1400 reason.code = NoMatch;1401 1242 1402 1243 for ( const CandidateRef & r1 : finder1.candidates ) { … … 1415 1256 ast::AssertionSet have; 1416 1257 1417 // unify true and false results, then infer parameters to produce new 1258 // unify true and false results, then infer parameters to produce new 1418 1259 // candidates 1419 1260 ast::ptr< ast::Type > common; 1420 if ( 1421 unify( 1422 r2->expr->result, r3->expr->result, env, need, have, open, symtab, 1423 common ) 1261 if ( 1262 unify( 1263 r2->expr->result, r3->expr->result, env, need, have, open, symtab, 1264 common ) 1424 1265 ) { 1425 1266 // generate typed expression 1426 ast::ConditionalExpr * newExpr = new ast::ConditionalExpr{ 1267 ast::ConditionalExpr * newExpr = new ast::ConditionalExpr{ 1427 1268 conditionalExpr->location, r1->expr, r2->expr, r3->expr }; 1428 1269 newExpr->result = common ? common : r2->expr->result; 1429 1270 // convert both options to result type 1430 1271 Cost cost = r1->cost + r2->cost + r3->cost; 1431 newExpr->arg2 = computeExpressionConversionCost( 1272 newExpr->arg2 = computeExpressionConversionCost( 1432 1273 newExpr->arg2, newExpr->result, symtab, env, cost ); 1433 1274 newExpr->arg3 = computeExpressionConversionCost( … … 1446 1287 ast::TypeEnvironment env{ tenv }; 1447 1288 ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, symtab, env ); 1448 1289 1449 1290 CandidateFinder finder2{ symtab, env }; 1450 1291 finder2.find( commaExpr->arg2, ResolvMode::withAdjustment() ); … … 1476 1317 finder2.find( rangeExpr->high, ResolvMode::withAdjustment() ); 1477 1318 if ( finder2.candidates.empty() ) return; 1478 1479 reason.code = NoMatch;1480 1319 1481 1320 for ( const CandidateRef & r1 : finder1.candidates ) { … … 1491 1330 1492 1331 ast::ptr< ast::Type > common; 1493 if ( 1494 unify( 1495 r1->expr->result, r2->expr->result, env, need, have, open, symtab, 1496 common ) 1332 if ( 1333 unify( 1334 r1->expr->result, r2->expr->result, env, need, have, open, symtab, 1335 common ) 1497 1336 ) { 1498 1337 // generate new expression 1499 ast::RangeExpr * newExpr = 1338 ast::RangeExpr * newExpr = 1500 1339 new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr }; 1501 1340 newExpr->result = common ? common : r1->expr->result; 1502 1341 // add candidate 1503 1342 CandidateRef newCand = std::make_shared<Candidate>( 1504 newExpr, move( env ), move( open ), move( need ), 1343 newExpr, move( env ), move( open ), move( need ), 1505 1344 r1->cost + r2->cost ); 1506 1345 inferParameters( newCand, candidates ); … … 1511 1350 1512 1351 void postvisit( const ast::UntypedTupleExpr * tupleExpr ) { 1513 std::vector< CandidateFinder > subCandidates = 1352 std::vector< CandidateFinder > subCandidates = 1514 1353 selfFinder.findSubExprs( tupleExpr->exprs ); 1515 1354 std::vector< CandidateList > possibilities; … … 1531 1370 1532 1371 addCandidate( 1533 new ast::TupleExpr{ tupleExpr->location, move( exprs ) }, 1372 new ast::TupleExpr{ tupleExpr->location, move( exprs ) }, 1534 1373 move( env ), move( open ), move( need ), sumCost( subs ) ); 1535 1374 } … … 1571 1410 // calculate target type 1572 1411 const ast::Type * toType = resolveTypeof( initAlt.type, symtab ); 1573 //toType = SymTab::validateType( initExpr->location, toType, symtab );1412 toType = SymTab::validateType( initExpr->location, toType, symtab ); 1574 1413 toType = adjustExprType( toType, tenv, symtab ); 1575 // The call to find must occur inside this loop, otherwise polymorphic return 1576 // types are not bound to the initialization type, since return type variables are 1577 // only open for the duration of resolving the UntypedExpr. 1414 // The call to find must occur inside this loop, otherwise polymorphic return 1415 // types are not bound to the initialization type, since return type variables are 1416 // only open for the duration of resolving the UntypedExpr. 1578 1417 CandidateFinder finder{ symtab, tenv, toType }; 1579 1418 finder.find( initExpr->expr, ResolvMode::withAdjustment() ); 1580 1419 for ( CandidateRef & cand : finder.candidates ) { 1581 if(reason.code == NotFound) reason.code = NoMatch;1582 1583 1420 ast::TypeEnvironment env{ cand->env }; 1584 1421 ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have; … … 1589 1426 ) 1590 1427 1591 // It is possible that a cast can throw away some values in a multiply-valued 1592 // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of 1593 // the subexpression results that are cast directly. The candidate is invalid 1428 // It is possible that a cast can throw away some values in a multiply-valued 1429 // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of 1430 // the subexpression results that are cast directly. The candidate is invalid 1594 1431 // if it has fewer results than there are types to cast to. 1595 1432 int discardedValues = cand->expr->result->size() - toType->size(); … … 1597 1434 1598 1435 // unification run for side-effects 1599 bool canUnify = unify( toType, cand->expr->result, env, need, have, open, symtab ); 1600 (void) canUnify; 1601 Cost thisCost = computeConversionCost( cand->expr->result, toType, cand->expr->get_lvalue(), 1602 symtab, env ); 1603 PRINT( 1604 Cost legacyCost = castCost( cand->expr->result, toType, cand->expr->get_lvalue(), 1605 symtab, env ); 1606 std::cerr << "Considering initialization:"; 1607 std::cerr << std::endl << " FROM: " << cand->expr->result << std::endl; 1608 std::cerr << std::endl << " TO: " << toType << std::endl; 1609 std::cerr << std::endl << " Unification " << (canUnify ? "succeeded" : "failed"); 1610 std::cerr << std::endl << " Legacy cost " << legacyCost; 1611 std::cerr << std::endl << " New cost " << thisCost; 1612 std::cerr << std::endl; 1613 ) 1436 unify( toType, cand->expr->result, env, need, have, open, symtab ); 1437 Cost thisCost = castCost( cand->expr->result, toType, symtab, env ); 1438 1614 1439 if ( thisCost != Cost::infinity ) { 1615 1440 // count one safe conversion for each value that is thrown away 1616 1441 thisCost.incSafe( discardedValues ); 1617 CandidateRef newCand = std::make_shared<Candidate>( 1618 new ast::InitExpr{ 1619 initExpr->location, restructureCast( cand->expr, toType ), 1620 initAlt.designation }, 1621 move(env), move( open ), move( need ), cand->cost, thisCost );1442 CandidateRef newCand = std::make_shared<Candidate>( 1443 new ast::InitExpr{ 1444 initExpr->location, restructureCast( cand->expr, toType ), 1445 initAlt.designation }, 1446 copy( cand->env ), move( open ), move( need ), cand->cost, thisCost ); 1622 1447 inferParameters( newCand, matches ); 1623 1448 } 1624 1449 } 1625 1626 1450 } 1627 1451 … … 1645 1469 }; 1646 1470 1647 // size_t Finder::traceId = Stats::Heap::new_stacktrace_id("Finder"); 1648 /// Prunes a list of candidates down to those that have the minimum conversion cost for a given 1471 /// Prunes a list of candidates down to those that have the minimum conversion cost for a given 1649 1472 /// return type. Skips ambiguous candidates. 1650 1651 } // anonymous namespace 1652 1653 bool CandidateFinder::pruneCandidates( CandidateList & candidates, CandidateList & out, std::vector<std::string> & errors ) { 1654 struct PruneStruct { 1655 CandidateRef candidate; 1656 bool ambiguous; 1657 1658 PruneStruct() = default; 1659 PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {} 1660 }; 1661 1662 // find lowest-cost candidate for each type 1663 std::unordered_map< std::string, PruneStruct > selected; 1664 // attempt to skip satisfyAssertions on more expensive alternatives if better options have been found 1665 std::sort(candidates.begin(), candidates.end(), [](const CandidateRef & x, const CandidateRef & y){return x->cost < y->cost;}); 1666 for ( CandidateRef & candidate : candidates ) { 1667 std::string mangleName; 1668 { 1669 ast::ptr< ast::Type > newType = candidate->expr->result; 1670 assertf(candidate->expr->result, "Result of expression %p for candidate is null", candidate->expr.get()); 1671 candidate->env.apply( newType ); 1672 mangleName = Mangle::mangle( newType ); 1673 } 1674 1675 auto found = selected.find( mangleName ); 1676 if (found != selected.end() && found->second.candidate->cost < candidate->cost) { 1677 PRINT( 1678 std::cerr << "cost " << candidate->cost << " loses to " 1679 << found->second.candidate->cost << std::endl; 1680 ) 1681 continue; 1682 } 1683 1684 // xxx - when do satisfyAssertions produce more than 1 result? 1685 // this should only happen when initial result type contains 1686 // unbound type parameters, then it should never be pruned by 1687 // the previous step, since renameTyVars guarantees the mangled name 1688 // is unique. 1689 CandidateList satisfied; 1690 bool needRecomputeKey = false; 1691 if (candidate->need.empty()) { 1692 satisfied.emplace_back(candidate); 1693 } 1694 else { 1695 satisfyAssertions(candidate, localSyms, satisfied, errors); 1696 needRecomputeKey = true; 1697 } 1698 1699 for (auto & newCand : satisfied) { 1700 // recomputes type key, if satisfyAssertions changed it 1701 if (needRecomputeKey) 1473 CandidateList pruneCandidates( CandidateList & candidates ) { 1474 struct PruneStruct { 1475 CandidateRef candidate; 1476 bool ambiguous; 1477 1478 PruneStruct() = default; 1479 PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {} 1480 }; 1481 1482 // find lowest-cost candidate for each type 1483 std::unordered_map< std::string, PruneStruct > selected; 1484 for ( CandidateRef & candidate : candidates ) { 1485 std::string mangleName; 1702 1486 { 1703 ast::ptr< ast::Type > newType = newCand->expr->result; 1704 assertf(newCand->expr->result, "Result of expression %p for candidate is null", newCand->expr.get()); 1705 newCand->env.apply( newType ); 1487 ast::ptr< ast::Type > newType = candidate->expr->result; 1488 candidate->env.apply( newType ); 1706 1489 mangleName = Mangle::mangle( newType ); 1707 1490 } 1491 1708 1492 auto found = selected.find( mangleName ); 1709 1493 if ( found != selected.end() ) { 1710 if ( newCand->cost < found->second.candidate->cost ) {1494 if ( candidate->cost < found->second.candidate->cost ) { 1711 1495 PRINT( 1712 std::cerr << "cost " << newCand->cost << " beats "1496 std::cerr << "cost " << candidate->cost << " beats " 1713 1497 << found->second.candidate->cost << std::endl; 1714 1498 ) 1715 1499 1716 found->second = PruneStruct{ newCand};1717 } else if ( newCand->cost == found->second.candidate->cost ) {1718 // if one of the candidates contains a deleted identifier, can pick the other, 1719 // since deleted expressions should not be ambiguous if there is another option 1500 found->second = PruneStruct{ candidate }; 1501 } else if ( candidate->cost == found->second.candidate->cost ) { 1502 // if one of the candidates contains a deleted identifier, can pick the other, 1503 // since deleted expressions should not be ambiguous if there is another option 1720 1504 // that is at least as good 1721 if ( findDeletedExpr( newCand->expr ) ) {1505 if ( findDeletedExpr( candidate->expr ) ) { 1722 1506 // do nothing 1723 1507 PRINT( std::cerr << "candidate is deleted" << std::endl; ) 1724 1508 } else if ( findDeletedExpr( found->second.candidate->expr ) ) { 1725 1509 PRINT( std::cerr << "current is deleted" << std::endl; ) 1726 found->second = PruneStruct{ newCand};1510 found->second = PruneStruct{ candidate }; 1727 1511 } else { 1728 1512 PRINT( std::cerr << "marking ambiguous" << std::endl; ) 1729 1513 found->second.ambiguous = true; 1730 1514 } 1731 } else { 1732 // xxx - can satisfyAssertions increase the cost? 1515 } else { 1733 1516 PRINT( 1734 std::cerr << "cost " << newCand->cost << " loses to "1517 std::cerr << "cost " << candidate->cost << " loses to " 1735 1518 << found->second.candidate->cost << std::endl; 1736 ) 1519 ) 1737 1520 } 1738 1521 } else { 1739 selected.emplace_hint( found, mangleName, newCand ); 1740 } 1741 } 1522 selected.emplace_hint( found, mangleName, candidate ); 1523 } 1524 } 1525 1526 // report unambiguous min-cost candidates 1527 CandidateList out; 1528 for ( auto & target : selected ) { 1529 if ( target.second.ambiguous ) continue; 1530 1531 CandidateRef cand = target.second.candidate; 1532 1533 ast::ptr< ast::Type > newResult = cand->expr->result; 1534 cand->env.applyFree( newResult ); 1535 cand->expr = ast::mutate_field( 1536 cand->expr.get(), &ast::Expr::result, move( newResult ) ); 1537 1538 out.emplace_back( cand ); 1539 } 1540 return out; 1742 1541 } 1743 1542 1744 // report unambiguous min-cost candidates 1745 // CandidateList out; 1746 for ( auto & target : selected ) { 1747 if ( target.second.ambiguous ) continue; 1748 1749 CandidateRef cand = target.second.candidate; 1750 1751 ast::ptr< ast::Type > newResult = cand->expr->result; 1752 cand->env.applyFree( newResult ); 1753 cand->expr = ast::mutate_field( 1754 cand->expr.get(), &ast::Expr::result, move( newResult ) ); 1755 1756 out.emplace_back( cand ); 1757 } 1758 // if everything is lost in satisfyAssertions, report the error 1759 return !selected.empty(); 1760 } 1543 } // anonymous namespace 1761 1544 1762 1545 void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) { … … 1766 1549 1767 1550 if ( mode.failFast && candidates.empty() ) { 1768 switch(finder.core.reason.code) { 1769 case Finder::NotFound: 1770 { SemanticError( expr, "No alternatives for expression " ); break; } 1771 case Finder::NoMatch: 1772 { SemanticError( expr, "Invalid application of existing declaration(s) in expression " ); break; } 1773 case Finder::ArgsToFew: 1774 case Finder::ArgsToMany: 1775 case Finder::RetsToFew: 1776 case Finder::RetsToMany: 1777 case Finder::NoReason: 1778 default: 1779 { SemanticError( expr->location, "No reasonable alternatives for expression : reasons unkown" ); } 1780 } 1551 SemanticError( expr, "No reasonable alternatives for expression " ); 1781 1552 } 1782 1553 1783 /*1784 1554 if ( mode.satisfyAssns || mode.prune ) { 1785 1555 // trim candidates to just those where the assertions are satisfiable … … 1788 1558 std::vector< std::string > errors; 1789 1559 for ( CandidateRef & candidate : candidates ) { 1790 satisfyAssertions( candidate, localSyms, satisfied, errors );1560 satisfyAssertions( candidate, symtab, satisfied, errors ); 1791 1561 } 1792 1562 … … 1804 1574 candidates = move( satisfied ); 1805 1575 } 1806 */1807 1576 1808 1577 if ( mode.prune ) { … … 1813 1582 ) 1814 1583 1815 CandidateList pruned; 1816 std::vector<std::string> errors; 1817 bool found = pruneCandidates( candidates, pruned, errors ); 1818 1584 CandidateList pruned = pruneCandidates( candidates ); 1585 1819 1586 if ( mode.failFast && pruned.empty() ) { 1820 1587 std::ostringstream stream; 1821 if (found) { 1822 CandidateList winners = findMinCost( candidates ); 1823 stream << "Cannot choose between " << winners.size() << " alternatives for " 1824 "expression\n"; 1825 ast::print( stream, expr ); 1826 stream << " Alternatives are:\n"; 1827 print( stream, winners, 1 ); 1828 SemanticError( expr->location, stream.str() ); 1829 } 1830 else { 1831 stream << "No alternatives with satisfiable assertions for " << expr << "\n"; 1832 for ( const auto& err : errors ) { 1833 stream << err; 1834 } 1835 SemanticError( expr->location, stream.str() ); 1836 } 1588 CandidateList winners = findMinCost( candidates ); 1589 stream << "Cannot choose between " << winners.size() << " alternatives for " 1590 "expression\n"; 1591 ast::print( stream, expr ); 1592 stream << " Alternatives are:\n"; 1593 print( stream, winners, 1 ); 1594 SemanticError( expr->location, stream.str() ); 1837 1595 } 1838 1596 … … 1844 1602 ) 1845 1603 PRINT( 1846 std::cerr << "there are " << candidates.size() << " alternatives after elimination" 1604 std::cerr << "there are " << candidates.size() << " alternatives after elimination" 1847 1605 << std::endl; 1848 1606 ) 1849 1607 } 1850 1608 1851 // adjust types after pruning so that types substituted by pruneAlternatives are correctly 1609 // adjust types after pruning so that types substituted by pruneAlternatives are correctly 1852 1610 // adjusted 1853 1611 if ( mode.adjust ) { 1854 1612 for ( CandidateRef & r : candidates ) { 1855 r->expr = ast::mutate_field( 1856 r->expr.get(), &ast::Expr::result, 1857 adjustExprType( r->expr->result, r->env, localSyms) );1613 r->expr = ast::mutate_field( 1614 r->expr.get(), &ast::Expr::result, 1615 adjustExprType( r->expr->result, r->env, symtab ) ); 1858 1616 } 1859 1617 } … … 1867 1625 } 1868 1626 1869 std::vector< CandidateFinder > CandidateFinder::findSubExprs( 1870 const std::vector< ast::ptr< ast::Expr > > & xs 1627 std::vector< CandidateFinder > CandidateFinder::findSubExprs( 1628 const std::vector< ast::ptr< ast::Expr > > & xs 1871 1629 ) { 1872 1630 std::vector< CandidateFinder > out; 1873 1631 1874 1632 for ( const auto & x : xs ) { 1875 out.emplace_back( localSyms, env );1633 out.emplace_back( symtab, env ); 1876 1634 out.back().find( x, ResolvMode::withAdjustment() ); 1877 1635 1878 1636 PRINT( 1879 1637 std::cerr << "findSubExprs" << std::endl;
Note:
See TracChangeset
for help on using the changeset viewer.
