Changeset 58fe85a for src/ResolvExpr/CandidateFinder.cpp
- Timestamp:
- Jan 7, 2021, 3:27:00 PM (5 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 2b4daf2, 64aeca0
- Parents:
- 3c64c668 (diff), eef8dfb (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)links above to see all the changes relative to each parent. - File:
-
- 1 edited
-
src/ResolvExpr/CandidateFinder.cpp (modified) (89 diffs)
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/CandidateFinder.cpp
r3c64c668 r58fe85a 9 9 // Author : Aaron B. Moss 10 10 // Created On : Wed Jun 5 14:30:00 2019 11 // Last Modified By : A aron B. Moss12 // Last Modified On : Wed Jun 5 14:30:00 201913 // Update Count : 111 // Last Modified By : Andrew Beach 12 // Last Modified On : Tue Oct 1 14:55:00 2019 13 // Update Count : 2 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 getPointerBase 46 47 #include "Common/Stats/Counter.h" 45 48 46 49 #define PRINT( text ) if ( resolvep ) { text } … … 54 57 return new ast::CastExpr{ expr, expr->result->stripReferences() }; 55 58 } 56 59 57 60 return expr; 58 61 } … … 61 64 UniqueId globalResnSlot = 0; 62 65 63 Cost computeConversionCost( 64 const ast::Type * argType, const ast::Type * paramType, const ast::SymbolTable & symtab,65 const ast:: TypeEnvironment & env66 Cost computeConversionCost( 67 const ast::Type * argType, const ast::Type * paramType, bool argIsLvalue, 68 const ast::SymbolTable & symtab, const ast::TypeEnvironment & env 66 69 ) { 67 70 PRINT( … … 74 77 std::cerr << std::endl; 75 78 ) 76 Cost convCost = conversionCost( argType, paramType, symtab, env );79 Cost convCost = conversionCost( argType, paramType, argIsLvalue, symtab, env ); 77 80 PRINT( 78 81 std::cerr << std::endl << "cost is " << convCost << std::endl; … … 107 110 108 111 /// Computes conversion cost for a given expression to a given type 109 const ast::Expr * computeExpressionConversionCost( 110 const ast::Expr * arg, const ast::Type * paramType, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env, Cost & outCost 112 const ast::Expr * computeExpressionConversionCost( 113 const ast::Expr * arg, const ast::Type * paramType, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env, Cost & outCost 111 114 ) { 112 Cost convCost = computeConversionCost( arg->result, paramType, symtab, env ); 115 Cost convCost = computeConversionCost( 116 arg->result, paramType, arg->get_lvalue(), symtab, env ); 113 117 outCost += convCost; 114 118 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 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 117 121 // infer parameters and this does not currently work for the reason stated below 118 122 Cost tmpCost = convCost; … … 123 127 return new ast::CastExpr{ arg, newType }; 124 128 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, 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, 127 131 // once this is fixed it should be possible to resolve the cast. 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 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 130 134 // commontype(zero_t, DT*) is DT*, rather than nothing 131 135 132 136 // CandidateFinder finder{ symtab, env }; 133 137 // finder.find( arg, ResolvMode::withAdjustment() ); 134 // assertf( finder.candidates.size() > 0, 138 // assertf( finder.candidates.size() > 0, 135 139 // "Somehow castable expression failed to find alternatives." ); 136 // assertf( finder.candidates.size() == 1, 140 // assertf( finder.candidates.size() == 1, 137 141 // "Somehow got multiple alternatives for known cast expression." ); 138 142 // return finder.candidates.front()->expr; … … 143 147 144 148 /// Computes conversion cost for a given candidate 145 Cost computeApplicationConversionCost( 146 CandidateRef cand, const ast::SymbolTable & symtab 149 Cost computeApplicationConversionCost( 150 CandidateRef cand, const ast::SymbolTable & symtab 147 151 ) { 148 152 auto appExpr = cand->expr.strict_as< ast::ApplicationExpr >(); … … 167 171 if ( function->isVarArgs ) { 168 172 convCost.incUnsafe(); 169 PRINT( std::cerr << "end of params with varargs function: inc unsafe: " 173 PRINT( std::cerr << "end of params with varargs function: inc unsafe: " 170 174 << convCost << std::endl; ; ) 171 175 // convert reference-typed expressions into value-typed expressions 172 cand->expr = ast::mutate_field_index( 173 appExpr, &ast::ApplicationExpr::args, i, 176 cand->expr = ast::mutate_field_index( 177 appExpr, &ast::ApplicationExpr::args, i, 174 178 referenceToRvalueConversion( args[i], convCost ) ); 175 179 continue; … … 180 184 // Default arguments should be free - don't include conversion cost. 181 185 // Unwrap them here because they are not relevant to the rest of the system 182 cand->expr = ast::mutate_field_index( 186 cand->expr = ast::mutate_field_index( 183 187 appExpr, &ast::ApplicationExpr::args, i, def->expr ); 184 188 ++param; … … 187 191 188 192 // mark conversion cost and also specialization cost of param type 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) );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 ) ); 195 199 ++param; // can't be in for-loop update because of the continue 196 200 } … … 198 202 if ( param != params.end() ) return Cost::infinity; 199 203 200 // specialization cost of return types can't be accounted for directly, it disables 204 // specialization cost of return types can't be accounted for directly, it disables 201 205 // otherwise-identical calls, like this example based on auto-newline in the I/O lib: 202 206 // … … 208 212 // mark type variable and specialization cost of forall clause 209 213 convCost.incVar( function->forall.size() ); 210 for ( const ast::TypeDecl * td : function->forall ) { 211 convCost.decSpec( td->assertions.size() ); 212 } 214 convCost.decSpec( function->assertions.size() ); 213 215 214 216 return convCost; 215 217 } 216 218 217 void makeUnifiableVars( 218 const ast:: ParameterizedType * type, ast::OpenVarSet & unifiableVars,219 ast::AssertionSet & need 219 void makeUnifiableVars( 220 const ast::FunctionType * type, ast::OpenVarSet & unifiableVars, 221 ast::AssertionSet & need 220 222 ) { 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 }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; 226 228 } 227 229 } … … 254 256 255 257 ArgPack() 256 : parent( 0 ), expr(), cost( Cost::zero ), env(), need(), have(), open(), nextArg( 0 ), 258 : parent( 0 ), expr(), cost( Cost::zero ), env(), need(), have(), open(), nextArg( 0 ), 257 259 tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {} 258 259 ArgPack( 260 const ast::TypeEnvironment & env, const ast::AssertionSet & need, 260 261 ArgPack( 262 const ast::TypeEnvironment & env, const ast::AssertionSet & need, 261 263 const ast::AssertionSet & have, const ast::OpenVarSet & open ) 262 : parent( 0 ), expr(), cost( Cost::zero ), env( env ), need( need ), have( have ), 264 : parent( 0 ), expr(), cost( Cost::zero ), env( env ), need( need ), have( have ), 263 265 open( open ), nextArg( 0 ), tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {} 264 266 265 267 ArgPack( 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, 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, 269 271 unsigned nextExpl = 0, unsigned explAlt = 0 ) 270 272 : parent(parent), expr( expr ), cost( cost ), env( move( env ) ), need( move( need ) ), 271 273 have( move( have ) ), open( move( open ) ), nextArg( nextArg ), tupleStart( tupleStart ), 272 274 nextExpl( nextExpl ), explAlt( explAlt ) {} 273 275 274 276 ArgPack( 275 const ArgPack & o, ast::TypeEnvironment && env, ast::AssertionSet && need, 277 const ArgPack & o, ast::TypeEnvironment && env, ast::AssertionSet && need, 276 278 ast::AssertionSet && have, ast::OpenVarSet && open, unsigned nextArg, Cost added ) 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 ), 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 ), 279 281 tupleStart( o.tupleStart ), nextExpl( 0 ), explAlt( 0 ) {} 280 282 281 283 /// true if this pack is in the middle of an exploded argument 282 284 bool hasExpl() const { return nextExpl > 0; } … … 286 288 return args[ nextArg-1 ][ explAlt ]; 287 289 } 288 290 289 291 /// Ends a tuple expression, consolidating the appropriate args 290 292 void endTuple( const std::vector< ArgPack > & packs ) { … … 307 309 308 310 /// Instantiates an argument to match a parameter, returns false if no matching results left 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 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 313 315 ) { 314 316 if ( auto tupleType = dynamic_cast< const ast::TupleType * >( paramType ) ) { … … 318 320 // xxx - dropping initializer changes behaviour from previous, but seems correct 319 321 // ^^^ need to handle the case where a tuple has a default argument 320 if ( ! instantiateArgument( 322 if ( ! instantiateArgument( 321 323 type, nullptr, args, results, genStart, symtab, nTuples ) ) return false; 322 324 nTuples = 0; … … 329 331 } else if ( const ast::TypeInstType * ttype = Tuples::isTtype( paramType ) ) { 330 332 // paramType is a ttype, consumes all remaining arguments 331 333 332 334 // completed tuples; will be spliced to end of results to finish 333 335 std::vector< ArgPack > finalResults{}; … … 342 344 for ( std::size_t i = genStart; i < genEnd; ++i ) { 343 345 unsigned nextArg = results[i].nextArg; 344 346 345 347 // use next element of exploded tuple if present 346 348 if ( results[i].hasExpl() ) { … … 352 354 results.emplace_back( 353 355 i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ), 354 copy( results[i].need ), copy( results[i].have ), 356 copy( results[i].need ), copy( results[i].have ), 355 357 copy( results[i].open ), nextArg, nTuples, Cost::zero, nextExpl, 356 358 results[i].explAlt ); … … 370 372 // push empty tuple expression 371 373 newResult.parent = i; 372 std::vector< ast::ptr< ast::Expr > > emptyList; 373 newResult.expr = 374 new ast::TupleExpr{ CodeLocation{}, move( emptyList ) }; 374 newResult.expr = new ast::TupleExpr{ CodeLocation{}, {} }; 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(); 550 return genEnd != results.size(); // were any new results added? 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 struct Finder final : public ast::WithShortCircuiting { 596 class Finder final : public ast::WithShortCircuiting { 597 const ast::SymbolTable & symtab; 598 public: 599 static size_t traceId; 597 600 CandidateFinder & selfFinder; 598 const ast::SymbolTable & symtab;599 601 CandidateList & candidates; 600 602 const ast::TypeEnvironment & tenv; 601 603 ast::ptr< ast::Type > & targetType; 602 604 605 enum Errors { 606 NotFound, 607 NoMatch, 608 ArgsToFew, 609 ArgsToMany, 610 RetsToFew, 611 RetsToMany, 612 NoReason 613 }; 614 615 struct { 616 Errors code = NotFound; 617 } reason; 618 603 619 Finder( CandidateFinder & f ) 604 : s elfFinder( f ), symtab( f.symtab ), candidates( f.candidates ), tenv( f.env ),620 : symtab( f.localSyms ), selfFinder( f ), candidates( f.candidates ), tenv( f.env ), 605 621 targetType( f.targetType ) {} 606 622 607 623 void previsit( const ast::Node * ) { visit_children = false; } 608 624 … … 611 627 void addCandidate( Args &&... args ) { 612 628 candidates.emplace_back( new Candidate{ std::forward<Args>( args )... } ); 629 reason.code = NoReason; 613 630 } 614 631 … … 639 656 640 657 /// Completes a function candidate with arguments located 641 void validateFunctionCandidate( 642 const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results, 643 CandidateList & out 658 void validateFunctionCandidate( 659 const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results, 660 CandidateList & out 644 661 ) { 645 ast::ApplicationExpr * appExpr = 662 ast::ApplicationExpr * appExpr = 646 663 new ast::ApplicationExpr{ func->expr->location, func->expr }; 647 664 // sum cost and accumulate arguments … … 657 674 appExpr->args = move( vargs ); 658 675 // build and validate new candidate 659 auto newCand = 676 auto newCand = 660 677 std::make_shared<Candidate>( appExpr, result.env, result.open, result.need, cost ); 661 678 PRINT( … … 669 686 /// Builds a list of candidates for a function, storing them in out 670 687 void makeFunctionCandidates( 671 const CandidateRef & func, const ast::FunctionType * funcType, 688 const CandidateRef & func, const ast::FunctionType * funcType, 672 689 const ExplodedArgs_new & args, CandidateList & out 673 690 ) { … … 676 693 ast::TypeEnvironment funcEnv{ func->env }; 677 694 makeUnifiableVars( funcType, funcOpen, funcNeed ); 678 // add all type variables as open variables now so that those not used in the parameter679 // list are still considered open695 // add all type variables as open variables now so that those not used in the 696 // parameter list are still considered open 680 697 funcEnv.add( funcType->forall ); 681 698 682 699 if ( targetType && ! targetType->isVoid() && ! funcType->returns.empty() ) { 683 700 // attempt to narrow based on expected target type 684 const ast::Type * returnType = funcType->returns.front() ->get_type();685 if ( ! unify( 686 returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen, symtab ) 701 const ast::Type * returnType = funcType->returns.front(); 702 if ( ! unify( 703 returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen, symtab ) 687 704 ) { 688 705 // unification failed, do not pursue this candidate … … 696 713 std::size_t genStart = 0; 697 714 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 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 701 732 // matches 702 if ( ! instantiateArgument( 703 obj->type, obj->init, args, results, genStart, symtab ) ) return; 704 } 705 733 // no default args for indirect calls 734 if ( ! instantiateArgument( 735 param, nullptr, args, results, genStart, symtab ) ) return; 736 } 737 738 endMatch: 706 739 if ( funcType->isVarArgs ) { 707 740 // append any unused arguments to vararg pack … … 750 783 if ( expl.exprs.empty() ) { 751 784 results.emplace_back( 752 results[i], move( env ), copy( results[i].need ), 753 copy( results[i].have ), move( open ), nextArg + 1, 785 results[i], move( env ), copy( results[i].need ), 786 copy( results[i].have ), move( open ), nextArg + 1, 754 787 expl.cost ); 755 788 … … 760 793 results.emplace_back( 761 794 i, expl.exprs.front(), move( env ), copy( results[i].need ), 762 copy( results[i].have ), move( open ), nextArg + 1, 0, expl.cost, 795 copy( results[i].have ), move( open ), nextArg + 1, 0, expl.cost, 763 796 expl.exprs.size() == 1 ? 0 : 1, j ); 764 797 } … … 780 813 /// Adds implicit struct-conversions to the alternative list 781 814 void addAnonConversions( const CandidateRef & cand ) { 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 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 784 817 // base type to treat the aggregate as the referenced value 785 818 ast::ptr< ast::Expr > aggrExpr( cand->expr ); 786 819 ast::ptr< ast::Type > & aggrType = aggrExpr.get_and_mutate()->result; 787 820 cand->env.apply( aggrType ); 788 821 789 822 if ( aggrType.as< ast::ReferenceType >() ) { 790 823 aggrExpr = new ast::CastExpr{ aggrExpr, aggrType->stripReferences() }; … … 799 832 800 833 /// Adds aggregate member interpretations 801 void addAggMembers( 802 const ast:: ReferenceToType * aggrInst, const ast::Expr * expr,803 const Candidate & cand, const Cost & addedCost, const std::string & name 834 void addAggMembers( 835 const ast::BaseInstType * aggrInst, const ast::Expr * expr, 836 const Candidate & cand, const Cost & addedCost, const std::string & name 804 837 ) { 805 838 for ( const ast::Decl * decl : aggrInst->lookup( name ) ) { 806 839 auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( decl ); 807 CandidateRef newCand = std::make_shared<Candidate>( 840 CandidateRef newCand = std::make_shared<Candidate>( 808 841 cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost ); 809 // add anonymous member interpretations whenever an aggregate value type is seen 842 // add anonymous member interpretations whenever an aggregate value type is seen 810 843 // as a member expression 811 844 addAnonConversions( newCand ); … … 815 848 816 849 /// Adds tuple member interpretations 817 void addTupleMembers( 818 const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand, 819 const Cost & addedCost, const ast::Expr * member 850 void addTupleMembers( 851 const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand, 852 const Cost & addedCost, const ast::Expr * member 820 853 ) { 821 854 if ( auto constantExpr = dynamic_cast< const ast::ConstantExpr * >( member ) ) { 822 // get the value of the constant expression as an int, must be between 0 and the 855 // get the value of the constant expression as an int, must be between 0 and the 823 856 // length of the tuple to have meaning 824 857 long long val = constantExpr->intValue(); 825 858 if ( val >= 0 && (unsigned long long)val < tupleType->size() ) { 826 859 addCandidate( 827 cand, new ast::TupleIndexExpr{ expr->location, expr, (unsigned)val }, 860 cand, new ast::TupleIndexExpr{ expr->location, expr, (unsigned)val }, 828 861 addedCost ); 829 862 } … … 832 865 833 866 void postvisit( const ast::UntypedExpr * untypedExpr ) { 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 = 867 std::vector< CandidateFinder > argCandidates = 840 868 selfFinder.findSubExprs( untypedExpr->args ); 841 869 842 870 // take care of possible tuple assignments 843 871 // if not tuple assignment, handled as normal function call 844 872 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 references 883 // xxx - is this correct? 884 while (argType.as<ast::ReferenceType>()) argType = argType.as<ast::ReferenceType>()->base; 885 886 // convert 1-tuple to plain type 887 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 fail 905 // 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, // adjust 909 !untypedExpr->func.as<ast::NameExpr>(), // prune if not calling by name 910 selfFinder.candidates.empty() // failfast if other options are not found 911 }; 912 funcFinder.find( untypedExpr->func, mode ); 913 // short-circuit if no candidates 914 // if ( funcFinder.candidates.empty() ) return; 915 916 reason.code = NoMatch; 845 917 846 918 // find function operators … … 877 949 if ( auto function = pointer->base.as< ast::FunctionType >() ) { 878 950 CandidateRef newFunc{ new Candidate{ *func } }; 879 newFunc->expr = 951 newFunc->expr = 880 952 referenceToRvalueConversion( newFunc->expr, newFunc->cost ); 881 953 makeFunctionCandidates( newFunc, function, argExpansions, found ); 882 954 } 883 } else if ( 884 auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult ) 955 } else if ( 956 auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult ) 885 957 ) { 886 if ( const ast::EqvClass * clz = func->env.lookup( inst->name) ) {958 if ( const ast::EqvClass * clz = func->env.lookup( *inst ) ) { 887 959 if ( auto function = clz->bound.as< ast::FunctionType >() ) { 888 960 CandidateRef newFunc{ new Candidate{ *func } }; 889 newFunc->expr = 961 newFunc->expr = 890 962 referenceToRvalueConversion( newFunc->expr, newFunc->cost ); 891 963 makeFunctionCandidates( newFunc, function, argExpansions, found ); … … 901 973 std::vector< ExplodedArg > funcE; 902 974 funcE.reserve( funcFinder.candidates.size() ); 903 for ( const CandidateRef & func : funcFinder ) { 975 for ( const CandidateRef & func : funcFinder ) { 904 976 funcE.emplace_back( *func, symtab ); 905 977 } … … 913 985 if ( auto function = pointer->base.as< ast::FunctionType >() ) { 914 986 CandidateRef newOp{ new Candidate{ *op} }; 915 newOp->expr = 987 newOp->expr = 916 988 referenceToRvalueConversion( newOp->expr, newOp->cost ); 917 989 makeFunctionCandidates( newOp, function, argExpansions, found ); … … 922 994 } 923 995 924 // Implement SFINAE; resolution errors are only errors if there aren't any non-error 996 // Implement SFINAE; resolution errors are only errors if there aren't any non-error 925 997 // candidates 926 998 if ( found.empty() && ! errors.isEmpty() ) { throw errors; } … … 934 1006 auto pointer = appExpr->func->result.strict_as< ast::PointerType >(); 935 1007 auto function = pointer->base.strict_as< ast::FunctionType >(); 936 1008 937 1009 std::cerr << "Case +++++++++++++ " << appExpr->func << std::endl; 938 1010 std::cerr << "parameters are:" << std::endl; … … 957 1029 promoteCvtCost( winners ); 958 1030 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 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 961 1033 // `findMinCost`, since anon conversions are never the cheapest 962 1034 for ( const CandidateRef & c : winners ) { … … 966 1038 967 1039 if ( candidates.empty() && targetType && ! targetType->isVoid() ) { 968 // If resolution is unsuccessful with a target type, try again without, since it 1040 // If resolution is unsuccessful with a target type, try again without, since it 969 1041 // will sometimes succeed when it wouldn't with a target type binding. 970 1042 // For example: … … 983 1055 /// true if expression is an lvalue 984 1056 static bool isLvalue( const ast::Expr * x ) { 985 return x->result && ( x-> result->is_lvalue() || x->result.as< ast::ReferenceType >() );1057 return x->result && ( x->get_lvalue() || x->result.as< ast::ReferenceType >() ); 986 1058 } 987 1059 … … 989 1061 CandidateFinder finder{ symtab, tenv }; 990 1062 finder.find( addressExpr->arg ); 1063 1064 if( finder.candidates.empty() ) return; 1065 1066 reason.code = NoMatch; 1067 991 1068 for ( CandidateRef & r : finder.candidates ) { 992 1069 if ( ! isLvalue( r->expr ) ) continue; … … 1003 1080 assert( toType ); 1004 1081 toType = resolveTypeof( toType, symtab ); 1005 toType = SymTab::validateType( castExpr->location, toType, symtab );1082 // toType = SymTab::validateType( castExpr->location, toType, symtab ); 1006 1083 toType = adjustExprType( toType, tenv, symtab ); 1007 1084 1008 1085 CandidateFinder finder{ symtab, tenv, toType }; 1009 1086 finder.find( castExpr->arg, ResolvMode::withAdjustment() ); 1087 1088 if( !finder.candidates.empty() ) reason.code = NoMatch; 1010 1089 1011 1090 CandidateList matches; … … 1016 1095 cand->env.extractOpenVars( open ); 1017 1096 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 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 1021 1100 // has fewer results than there are types to cast to. 1022 1101 int discardedValues = cand->expr->result->size() - toType->size(); … … 1025 1104 // unification run for side-effects 1026 1105 unify( toType, cand->expr->result, cand->env, need, have, open, symtab ); 1027 Cost thisCost = castCost( cand->expr->result, toType, symtab, cand->env ); 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 1028 1111 PRINT( 1029 1112 std::cerr << "working on cast with result: " << toType << std::endl; … … 1037 1120 // count one safe conversion for each value that is thrown away 1038 1121 thisCost.incSafe( discardedValues ); 1039 CandidateRef newCand = std::make_shared<Candidate>( 1040 restructureCast( cand->expr, toType, castExpr->isGenerated ), 1041 copy( cand->env ), move( open ), move( need ), cand->cost, 1122 CandidateRef newCand = std::make_shared<Candidate>( 1123 restructureCast( cand->expr, toType, castExpr->isGenerated ), 1124 copy( cand->env ), move( open ), move( need ), cand->cost, 1042 1125 cand->cost + thisCost ); 1043 1126 inferParameters( newCand, matches ); … … 1057 1140 finder.find( castExpr->arg, ResolvMode::withoutPrune() ); 1058 1141 for ( CandidateRef & r : finder.candidates ) { 1059 addCandidate( 1060 *r, 1142 addCandidate( 1143 *r, 1061 1144 new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } ); 1062 1145 } 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.__thrd 1183 // Clone is purely for memory management 1184 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 type 1187 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 type 1196 finder.find( fallback.get(), ResolvMode::withoutPrune() ); 1197 1198 pick_alternatives(finder.candidates, true); 1199 1200 // Whatever happens here, we have no more fallbacks 1063 1201 } 1064 1202 … … 1067 1205 aggFinder.find( memberExpr->aggregate, ResolvMode::withAdjustment() ); 1068 1206 for ( CandidateRef & agg : aggFinder.candidates ) { 1069 // it's okay for the aggregate expression to have reference type -- cast it to the 1207 // it's okay for the aggregate expression to have reference type -- cast it to the 1070 1208 // base type to treat the aggregate as the referenced value 1071 1209 Cost addedCost = Cost::zero; … … 1074 1212 // find member of the given type 1075 1213 if ( auto structInst = agg->expr->result.as< ast::StructInstType >() ) { 1076 addAggMembers( 1214 addAggMembers( 1077 1215 structInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) ); 1078 1216 } else if ( auto unionInst = agg->expr->result.as< ast::UnionInstType >() ) { 1079 addAggMembers( 1217 addAggMembers( 1080 1218 unionInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) ); 1081 1219 } else if ( auto tupleType = agg->expr->result.as< ast::TupleType >() ) { … … 1090 1228 1091 1229 void postvisit( const ast::NameExpr * nameExpr ) { 1092 std::vector< ast::SymbolTable::IdData > declList = symtab.lookupId( nameExpr->name ); 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 } 1093 1243 PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; ) 1244 1245 if( declList.empty() ) return; 1246 1247 reason.code = NoMatch; 1248 1094 1249 for ( auto & data : declList ) { 1095 1250 Cost cost = Cost::zero; … … 1097 1252 1098 1253 CandidateRef newCand = std::make_shared<Candidate>( 1099 newExpr, copy( tenv ), ast::OpenVarSet{}, ast::AssertionSet{}, Cost::zero, 1254 newExpr, copy( tenv ), ast::OpenVarSet{}, ast::AssertionSet{}, Cost::zero, 1100 1255 cost ); 1101 1256 PRINT( … … 1107 1262 std::cerr << std::endl; 1108 1263 ) 1109 newCand->expr = ast::mutate_field( 1110 newCand->expr.get(), &ast::Expr::result, 1264 newCand->expr = ast::mutate_field( 1265 newCand->expr.get(), &ast::Expr::result, 1111 1266 renameTyVars( newCand->expr->result ) ); 1112 // add anonymous member interpretations whenever an aggregate value type is seen 1267 // add anonymous member interpretations whenever an aggregate value type is seen 1113 1268 // as a name expression 1114 1269 addAnonConversions( newCand ); … … 1120 1275 // not sufficient to just pass `variableExpr` here, type might have changed since 1121 1276 // creation 1122 addCandidate( 1277 addCandidate( 1123 1278 new ast::VariableExpr{ variableExpr->location, variableExpr->var }, tenv ); 1124 1279 } … … 1130 1285 void postvisit( const ast::SizeofExpr * sizeofExpr ) { 1131 1286 if ( sizeofExpr->type ) { 1132 addCandidate( 1133 new ast::SizeofExpr{ 1134 sizeofExpr->location, resolveTypeof( sizeofExpr->type, symtab ) }, 1287 addCandidate( 1288 new ast::SizeofExpr{ 1289 sizeofExpr->location, resolveTypeof( sizeofExpr->type, symtab ) }, 1135 1290 tenv ); 1136 1291 } else { … … 1141 1296 CandidateList winners = findMinCost( finder.candidates ); 1142 1297 if ( winners.size() != 1 ) { 1143 SemanticError( 1298 SemanticError( 1144 1299 sizeofExpr->expr.get(), "Ambiguous expression in sizeof operand: " ); 1145 1300 } … … 1154 1309 void postvisit( const ast::AlignofExpr * alignofExpr ) { 1155 1310 if ( alignofExpr->type ) { 1156 addCandidate( 1157 new ast::AlignofExpr{ 1158 alignofExpr->location, resolveTypeof( alignofExpr->type, symtab ) }, 1311 addCandidate( 1312 new ast::AlignofExpr{ 1313 alignofExpr->location, resolveTypeof( alignofExpr->type, symtab ) }, 1159 1314 tenv ); 1160 1315 } else { … … 1165 1320 CandidateList winners = findMinCost( finder.candidates ); 1166 1321 if ( winners.size() != 1 ) { 1167 SemanticError( 1322 SemanticError( 1168 1323 alignofExpr->expr.get(), "Ambiguous expression in alignof operand: " ); 1169 1324 } … … 1172 1327 choice->expr = referenceToRvalueConversion( choice->expr, choice->cost ); 1173 1328 choice->cost = Cost::zero; 1174 addCandidate( 1329 addCandidate( 1175 1330 *choice, new ast::AlignofExpr{ alignofExpr->location, choice->expr } ); 1176 1331 } … … 1178 1333 1179 1334 void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) { 1180 const ast:: ReferenceToType * aggInst;1335 const ast::BaseInstType * aggInst; 1181 1336 if (( aggInst = offsetofExpr->type.as< ast::StructInstType >() )) ; 1182 1337 else if (( aggInst = offsetofExpr->type.as< ast::UnionInstType >() )) ; … … 1185 1340 for ( const ast::Decl * member : aggInst->lookup( offsetofExpr->member ) ) { 1186 1341 auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( member ); 1187 addCandidate( 1342 addCandidate( 1188 1343 new ast::OffsetofExpr{ offsetofExpr->location, aggInst, dwt }, tenv ); 1189 1344 } … … 1206 1361 finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() ); 1207 1362 if ( finder2.candidates.empty() ) return; 1363 1364 reason.code = NoMatch; 1208 1365 1209 1366 for ( const CandidateRef & r1 : finder1.candidates ) { … … 1218 1375 1219 1376 addCandidate( 1220 new ast::LogicalExpr{ 1377 new ast::LogicalExpr{ 1221 1378 logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd }, 1222 1379 move( env ), move( open ), move( need ), r1->cost + r2->cost ); … … 1240 1397 finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() ); 1241 1398 if ( finder3.candidates.empty() ) return; 1399 1400 reason.code = NoMatch; 1242 1401 1243 1402 for ( const CandidateRef & r1 : finder1.candidates ) { … … 1256 1415 ast::AssertionSet have; 1257 1416 1258 // unify true and false results, then infer parameters to produce new 1417 // unify true and false results, then infer parameters to produce new 1259 1418 // candidates 1260 1419 ast::ptr< ast::Type > common; 1261 if ( 1262 unify( 1263 r2->expr->result, r3->expr->result, env, need, have, open, symtab, 1264 common ) 1420 if ( 1421 unify( 1422 r2->expr->result, r3->expr->result, env, need, have, open, symtab, 1423 common ) 1265 1424 ) { 1266 1425 // generate typed expression 1267 ast::ConditionalExpr * newExpr = new ast::ConditionalExpr{ 1426 ast::ConditionalExpr * newExpr = new ast::ConditionalExpr{ 1268 1427 conditionalExpr->location, r1->expr, r2->expr, r3->expr }; 1269 1428 newExpr->result = common ? common : r2->expr->result; 1270 1429 // convert both options to result type 1271 1430 Cost cost = r1->cost + r2->cost + r3->cost; 1272 newExpr->arg2 = computeExpressionConversionCost( 1431 newExpr->arg2 = computeExpressionConversionCost( 1273 1432 newExpr->arg2, newExpr->result, symtab, env, cost ); 1274 1433 newExpr->arg3 = computeExpressionConversionCost( … … 1287 1446 ast::TypeEnvironment env{ tenv }; 1288 1447 ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, symtab, env ); 1289 1448 1290 1449 CandidateFinder finder2{ symtab, env }; 1291 1450 finder2.find( commaExpr->arg2, ResolvMode::withAdjustment() ); … … 1317 1476 finder2.find( rangeExpr->high, ResolvMode::withAdjustment() ); 1318 1477 if ( finder2.candidates.empty() ) return; 1478 1479 reason.code = NoMatch; 1319 1480 1320 1481 for ( const CandidateRef & r1 : finder1.candidates ) { … … 1330 1491 1331 1492 ast::ptr< ast::Type > common; 1332 if ( 1333 unify( 1334 r1->expr->result, r2->expr->result, env, need, have, open, symtab, 1335 common ) 1493 if ( 1494 unify( 1495 r1->expr->result, r2->expr->result, env, need, have, open, symtab, 1496 common ) 1336 1497 ) { 1337 1498 // generate new expression 1338 ast::RangeExpr * newExpr = 1499 ast::RangeExpr * newExpr = 1339 1500 new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr }; 1340 1501 newExpr->result = common ? common : r1->expr->result; 1341 1502 // add candidate 1342 1503 CandidateRef newCand = std::make_shared<Candidate>( 1343 newExpr, move( env ), move( open ), move( need ), 1504 newExpr, move( env ), move( open ), move( need ), 1344 1505 r1->cost + r2->cost ); 1345 1506 inferParameters( newCand, candidates ); … … 1350 1511 1351 1512 void postvisit( const ast::UntypedTupleExpr * tupleExpr ) { 1352 std::vector< CandidateFinder > subCandidates = 1513 std::vector< CandidateFinder > subCandidates = 1353 1514 selfFinder.findSubExprs( tupleExpr->exprs ); 1354 1515 std::vector< CandidateList > possibilities; … … 1370 1531 1371 1532 addCandidate( 1372 new ast::TupleExpr{ tupleExpr->location, move( exprs ) }, 1533 new ast::TupleExpr{ tupleExpr->location, move( exprs ) }, 1373 1534 move( env ), move( open ), move( need ), sumCost( subs ) ); 1374 1535 } … … 1410 1571 // calculate target type 1411 1572 const ast::Type * toType = resolveTypeof( initAlt.type, symtab ); 1412 toType = SymTab::validateType( initExpr->location, toType, symtab );1573 // toType = SymTab::validateType( initExpr->location, toType, symtab ); 1413 1574 toType = adjustExprType( toType, tenv, symtab ); 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. 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. 1417 1578 CandidateFinder finder{ symtab, tenv, toType }; 1418 1579 finder.find( initExpr->expr, ResolvMode::withAdjustment() ); 1419 1580 for ( CandidateRef & cand : finder.candidates ) { 1581 if(reason.code == NotFound) reason.code = NoMatch; 1582 1420 1583 ast::TypeEnvironment env{ cand->env }; 1421 1584 ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have; … … 1426 1589 ) 1427 1590 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 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 1431 1594 // if it has fewer results than there are types to cast to. 1432 1595 int discardedValues = cand->expr->result->size() - toType->size(); … … 1434 1597 1435 1598 // unification run for side-effects 1436 unify( toType, cand->expr->result, env, need, have, open, symtab ); 1437 Cost thisCost = castCost( cand->expr->result, toType, symtab, env ); 1438 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 ) 1439 1614 if ( thisCost != Cost::infinity ) { 1440 1615 // count one safe conversion for each value that is thrown away 1441 1616 thisCost.incSafe( discardedValues ); 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 );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 ); 1447 1622 inferParameters( newCand, matches ); 1448 1623 } 1449 1624 } 1625 1450 1626 } 1451 1627 … … 1469 1645 }; 1470 1646 1471 /// Prunes a list of candidates down to those that have the minimum conversion cost for a given 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 1472 1649 /// return type. Skips ambiguous candidates. 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; 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) 1486 1702 { 1487 ast::ptr< ast::Type > newType = candidate->expr->result; 1488 candidate->env.apply( newType ); 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 ); 1489 1706 mangleName = Mangle::mangle( newType ); 1490 1707 } 1491 1492 1708 auto found = selected.find( mangleName ); 1493 1709 if ( found != selected.end() ) { 1494 if ( candidate->cost < found->second.candidate->cost ) {1710 if ( newCand->cost < found->second.candidate->cost ) { 1495 1711 PRINT( 1496 std::cerr << "cost " << candidate->cost << " beats "1712 std::cerr << "cost " << newCand->cost << " beats " 1497 1713 << found->second.candidate->cost << std::endl; 1498 1714 ) 1499 1715 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 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 1504 1720 // that is at least as good 1505 if ( findDeletedExpr( candidate->expr ) ) {1721 if ( findDeletedExpr( newCand->expr ) ) { 1506 1722 // do nothing 1507 1723 PRINT( std::cerr << "candidate is deleted" << std::endl; ) 1508 1724 } else if ( findDeletedExpr( found->second.candidate->expr ) ) { 1509 1725 PRINT( std::cerr << "current is deleted" << std::endl; ) 1510 found->second = PruneStruct{ candidate};1726 found->second = PruneStruct{ newCand }; 1511 1727 } else { 1512 1728 PRINT( std::cerr << "marking ambiguous" << std::endl; ) 1513 1729 found->second.ambiguous = true; 1514 1730 } 1515 } else { 1731 } else { 1732 // xxx - can satisfyAssertions increase the cost? 1516 1733 PRINT( 1517 std::cerr << "cost " << candidate->cost << " loses to "1734 std::cerr << "cost " << newCand->cost << " loses to " 1518 1735 << found->second.candidate->cost << std::endl; 1519 ) 1736 ) 1520 1737 } 1521 1738 } else { 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; 1739 selected.emplace_hint( found, mangleName, newCand ); 1740 } 1741 } 1541 1742 } 1542 1743 1543 } // anonymous namespace 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 } 1544 1761 1545 1762 void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) { … … 1549 1766 1550 1767 if ( mode.failFast && candidates.empty() ) { 1551 SemanticError( expr, "No reasonable alternatives for expression " ); 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 } 1552 1781 } 1553 1782 1783 /* 1554 1784 if ( mode.satisfyAssns || mode.prune ) { 1555 1785 // trim candidates to just those where the assertions are satisfiable … … 1558 1788 std::vector< std::string > errors; 1559 1789 for ( CandidateRef & candidate : candidates ) { 1560 satisfyAssertions( candidate, symtab, satisfied, errors );1790 satisfyAssertions( candidate, localSyms, satisfied, errors ); 1561 1791 } 1562 1792 … … 1574 1804 candidates = move( satisfied ); 1575 1805 } 1806 */ 1576 1807 1577 1808 if ( mode.prune ) { … … 1582 1813 ) 1583 1814 1584 CandidateList pruned = pruneCandidates( candidates ); 1585 1815 CandidateList pruned; 1816 std::vector<std::string> errors; 1817 bool found = pruneCandidates( candidates, pruned, errors ); 1818 1586 1819 if ( mode.failFast && pruned.empty() ) { 1587 1820 std::ostringstream stream; 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() ); 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 } 1595 1837 } 1596 1838 … … 1602 1844 ) 1603 1845 PRINT( 1604 std::cerr << "there are " << candidates.size() << " alternatives after elimination" 1846 std::cerr << "there are " << candidates.size() << " alternatives after elimination" 1605 1847 << std::endl; 1606 1848 ) 1607 1849 } 1608 1850 1609 // adjust types after pruning so that types substituted by pruneAlternatives are correctly 1851 // adjust types after pruning so that types substituted by pruneAlternatives are correctly 1610 1852 // adjusted 1611 1853 if ( mode.adjust ) { 1612 1854 for ( CandidateRef & r : candidates ) { 1613 r->expr = ast::mutate_field( 1614 r->expr.get(), &ast::Expr::result, 1615 adjustExprType( r->expr->result, r->env, symtab) );1855 r->expr = ast::mutate_field( 1856 r->expr.get(), &ast::Expr::result, 1857 adjustExprType( r->expr->result, r->env, localSyms ) ); 1616 1858 } 1617 1859 } … … 1625 1867 } 1626 1868 1627 std::vector< CandidateFinder > CandidateFinder::findSubExprs( 1628 const std::vector< ast::ptr< ast::Expr > > & xs 1869 std::vector< CandidateFinder > CandidateFinder::findSubExprs( 1870 const std::vector< ast::ptr< ast::Expr > > & xs 1629 1871 ) { 1630 1872 std::vector< CandidateFinder > out; 1631 1873 1632 1874 for ( const auto & x : xs ) { 1633 out.emplace_back( symtab, env );1875 out.emplace_back( localSyms, env ); 1634 1876 out.back().find( x, ResolvMode::withAdjustment() ); 1635 1877 1636 1878 PRINT( 1637 1879 std::cerr << "findSubExprs" << std::endl;
Note:
See TracChangeset
for help on using the changeset viewer.
