Changeset 64727bd for src/ResolvExpr/CandidateFinder.cpp
- Timestamp:
- Jun 16, 2023, 6:11:14 PM (14 months ago)
- Branches:
- master
- Children:
- b1e21da
- Parents:
- b96b1c0
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/CandidateFinder.cpp
rb96b1c0 r64727bd 25 25 #include "AdjustExprType.hpp" 26 26 #include "Candidate.hpp" 27 #include "CastCost.hpp" // for castCost 27 28 #include "CompilationState.h" 29 #include "ConversionCost.h" // for conversionCast 28 30 #include "Cost.h" 29 #include " CastCost.hpp"31 #include "ExplodedArg.hpp" 30 32 #include "PolyCost.hpp" 31 #include "SpecCost.hpp"32 #include "ConversionCost.h"33 #include "ExplodedArg.hpp"34 33 #include "RenameVars.h" // for renameTyVars 35 34 #include "Resolver.h" 36 35 #include "ResolveTypeof.h" 36 #include "SatisfyAssertions.hpp" 37 #include "SpecCost.hpp" 38 #include "typeops.h" // for combos 39 #include "Unify.h" 37 40 #include "WidenMode.h" 38 #include "SatisfyAssertions.hpp"39 #include "typeops.h" // for adjustExprType, conversionCost, polyCost, specCost40 #include "Unify.h"41 41 #include "AST/Expr.hpp" 42 42 #include "AST/Node.hpp" … … 56 56 namespace ResolvExpr { 57 57 58 /// Unique identifier for matching expression resolutions to their requesting expression 59 UniqueId globalResnSlot = 0; 60 61 namespace { 62 /// First index is which argument, second is which alternative, third is which exploded element 63 using ExplodedArgs_new = std::deque< std::vector< ExplodedArg > >; 64 65 /// Returns a list of alternatives with the minimum cost in the given list 66 CandidateList findMinCost( const CandidateList & candidates ) { 67 CandidateList out; 68 Cost minCost = Cost::infinity; 69 for ( const CandidateRef & r : candidates ) { 70 if ( r->cost < minCost ) { 71 minCost = r->cost; 72 out.clear(); 73 out.emplace_back( r ); 74 } else if ( r->cost == minCost ) { 75 out.emplace_back( r ); 76 } 77 } 78 return out; 79 } 80 81 /// Computes conversion cost for a given expression to a given type 82 const ast::Expr * computeExpressionConversionCost( 83 const ast::Expr * arg, const ast::Type * paramType, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env, Cost & outCost 84 ) { 85 Cost convCost = computeConversionCost( 86 arg->result, paramType, arg->get_lvalue(), symtab, env ); 87 outCost += convCost; 88 89 // If there is a non-zero conversion cost, ignoring poly cost, then the expression requires 90 // conversion. Ignore poly cost for now, since this requires resolution of the cast to 91 // infer parameters and this does not currently work for the reason stated below 92 Cost tmpCost = convCost; 93 tmpCost.incPoly( -tmpCost.get_polyCost() ); 94 if ( tmpCost != Cost::zero ) { 95 ast::ptr< ast::Type > newType = paramType; 96 env.apply( newType ); 97 return new ast::CastExpr{ arg, newType }; 98 99 // xxx - *should* be able to resolve this cast, but at the moment pointers are not 100 // castable to zero_t, but are implicitly convertible. This is clearly inconsistent, 101 // once this is fixed it should be possible to resolve the cast. 102 // xxx - this isn't working, it appears because type1 (parameter) is seen as widenable, 103 // but it shouldn't be because this makes the conversion from DT* to DT* since 104 // commontype(zero_t, DT*) is DT*, rather than nothing 105 106 // CandidateFinder finder{ symtab, env }; 107 // finder.find( arg, ResolvMode::withAdjustment() ); 108 // assertf( finder.candidates.size() > 0, 109 // "Somehow castable expression failed to find alternatives." ); 110 // assertf( finder.candidates.size() == 1, 111 // "Somehow got multiple alternatives for known cast expression." ); 112 // return finder.candidates.front()->expr; 113 } 114 115 return arg; 116 } 117 118 /// Computes conversion cost for a given candidate 119 Cost computeApplicationConversionCost( 120 CandidateRef cand, const ast::SymbolTable & symtab 121 ) { 122 auto appExpr = cand->expr.strict_as< ast::ApplicationExpr >(); 123 auto pointer = appExpr->func->result.strict_as< ast::PointerType >(); 124 auto function = pointer->base.strict_as< ast::FunctionType >(); 125 126 Cost convCost = Cost::zero; 127 const auto & params = function->params; 128 auto param = params.begin(); 129 auto & args = appExpr->args; 130 131 for ( unsigned i = 0; i < args.size(); ++i ) { 132 const ast::Type * argType = args[i]->result; 133 PRINT( 134 std::cerr << "arg expression:" << std::endl; 135 ast::print( std::cerr, args[i], 2 ); 136 std::cerr << "--- results are" << std::endl; 137 ast::print( std::cerr, argType, 2 ); 138 ) 139 140 if ( param == params.end() ) { 141 if ( function->isVarArgs ) { 142 convCost.incUnsafe(); 143 PRINT( std::cerr << "end of params with varargs function: inc unsafe: " 144 << convCost << std::endl; ; ) 145 // convert reference-typed expressions into value-typed expressions 146 cand->expr = ast::mutate_field_index( 147 appExpr, &ast::ApplicationExpr::args, i, 148 referenceToRvalueConversion( args[i], convCost ) ); 149 continue; 150 } else return Cost::infinity; 151 } 152 153 if ( auto def = args[i].as< ast::DefaultArgExpr >() ) { 154 // Default arguments should be free - don't include conversion cost. 155 // Unwrap them here because they are not relevant to the rest of the system 156 cand->expr = ast::mutate_field_index( 157 appExpr, &ast::ApplicationExpr::args, i, def->expr ); 158 ++param; 159 continue; 160 } 161 162 // mark conversion cost and also specialization cost of param type 163 // const ast::Type * paramType = (*param)->get_type(); 164 cand->expr = ast::mutate_field_index( 165 appExpr, &ast::ApplicationExpr::args, i, 166 computeExpressionConversionCost( 167 args[i], *param, symtab, cand->env, convCost ) ); 168 convCost.decSpec( specCost( *param ) ); 169 ++param; // can't be in for-loop update because of the continue 170 } 171 172 if ( param != params.end() ) return Cost::infinity; 173 174 // specialization cost of return types can't be accounted for directly, it disables 175 // otherwise-identical calls, like this example based on auto-newline in the I/O lib: 176 // 177 // forall(otype OS) { 178 // void ?|?(OS&, int); // with newline 179 // OS& ?|?(OS&, int); // no newline, always chosen due to more specialization 180 // } 181 182 // mark type variable and specialization cost of forall clause 183 convCost.incVar( function->forall.size() ); 184 convCost.decSpec( function->assertions.size() ); 185 186 return convCost; 187 } 188 189 void makeUnifiableVars( 190 const ast::FunctionType * type, ast::OpenVarSet & unifiableVars, 191 ast::AssertionSet & need 192 ) { 193 for ( auto & tyvar : type->forall ) { 194 unifiableVars[ *tyvar ] = ast::TypeData{ tyvar->base }; 195 } 196 for ( auto & assn : type->assertions ) { 197 need[ assn ].isUsed = true; 198 } 199 } 200 201 /// Gets a default value from an initializer, nullptr if not present 202 const ast::ConstantExpr * getDefaultValue( const ast::Init * init ) { 203 if ( auto si = dynamic_cast< const ast::SingleInit * >( init ) ) { 204 if ( auto ce = si->value.as< ast::CastExpr >() ) { 205 return ce->arg.as< ast::ConstantExpr >(); 206 } else { 207 return si->value.as< ast::ConstantExpr >(); 208 } 209 } 210 return nullptr; 211 } 212 213 /// State to iteratively build a match of parameter expressions to arguments 214 struct ArgPack { 215 std::size_t parent; ///< Index of parent pack 216 ast::ptr< ast::Expr > expr; ///< The argument stored here 217 Cost cost; ///< The cost of this argument 218 ast::TypeEnvironment env; ///< Environment for this pack 219 ast::AssertionSet need; ///< Assertions outstanding for this pack 220 ast::AssertionSet have; ///< Assertions found for this pack 221 ast::OpenVarSet open; ///< Open variables for this pack 222 unsigned nextArg; ///< Index of next argument in arguments list 223 unsigned tupleStart; ///< Number of tuples that start at this index 224 unsigned nextExpl; ///< Index of next exploded element 225 unsigned explAlt; ///< Index of alternative for nextExpl > 0 226 227 ArgPack() 228 : parent( 0 ), expr(), cost( Cost::zero ), env(), need(), have(), open(), nextArg( 0 ), 229 tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {} 230 231 ArgPack( 232 const ast::TypeEnvironment & env, const ast::AssertionSet & need, 233 const ast::AssertionSet & have, const ast::OpenVarSet & open ) 234 : parent( 0 ), expr(), cost( Cost::zero ), env( env ), need( need ), have( have ), 235 open( open ), nextArg( 0 ), tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {} 236 237 ArgPack( 238 std::size_t parent, const ast::Expr * expr, ast::TypeEnvironment && env, 239 ast::AssertionSet && need, ast::AssertionSet && have, ast::OpenVarSet && open, 240 unsigned nextArg, unsigned tupleStart = 0, Cost cost = Cost::zero, 241 unsigned nextExpl = 0, unsigned explAlt = 0 ) 242 : parent(parent), expr( expr ), cost( cost ), env( std::move( env ) ), need( std::move( need ) ), 243 have( std::move( have ) ), open( std::move( open ) ), nextArg( nextArg ), tupleStart( tupleStart ), 244 nextExpl( nextExpl ), explAlt( explAlt ) {} 245 246 ArgPack( 247 const ArgPack & o, ast::TypeEnvironment && env, ast::AssertionSet && need, 248 ast::AssertionSet && have, ast::OpenVarSet && open, unsigned nextArg, Cost added ) 249 : parent( o.parent ), expr( o.expr ), cost( o.cost + added ), env( std::move( env ) ), 250 need( std::move( need ) ), have( std::move( have ) ), open( std::move( open ) ), nextArg( nextArg ), 251 tupleStart( o.tupleStart ), nextExpl( 0 ), explAlt( 0 ) {} 252 253 /// true if this pack is in the middle of an exploded argument 254 bool hasExpl() const { return nextExpl > 0; } 255 256 /// Gets the list of exploded candidates for this pack 257 const ExplodedArg & getExpl( const ExplodedArgs_new & args ) const { 258 return args[ nextArg-1 ][ explAlt ]; 259 } 260 261 /// Ends a tuple expression, consolidating the appropriate args 262 void endTuple( const std::vector< ArgPack > & packs ) { 263 // add all expressions in tuple to list, summing cost 264 std::deque< const ast::Expr * > exprs; 265 const ArgPack * pack = this; 266 if ( expr ) { exprs.emplace_front( expr ); } 267 while ( pack->tupleStart == 0 ) { 268 pack = &packs[pack->parent]; 269 exprs.emplace_front( pack->expr ); 270 cost += pack->cost; 271 } 272 // reset pack to appropriate tuple 273 std::vector< ast::ptr< ast::Expr > > exprv( exprs.begin(), exprs.end() ); 274 expr = new ast::TupleExpr{ expr->location, std::move( exprv ) }; 275 tupleStart = pack->tupleStart - 1; 276 parent = pack->parent; 277 } 278 }; 279 280 /// Instantiates an argument to match a parameter, returns false if no matching results left 281 bool instantiateArgument( 282 const CodeLocation & location, 283 const ast::Type * paramType, const ast::Init * init, const ExplodedArgs_new & args, 284 std::vector< ArgPack > & results, std::size_t & genStart, const ast::SymbolTable & symtab, 285 unsigned nTuples = 0 286 ) { 287 if ( auto tupleType = dynamic_cast< const ast::TupleType * >( paramType ) ) { 288 // paramType is a TupleType -- group args into a TupleExpr 289 ++nTuples; 290 for ( const ast::Type * type : *tupleType ) { 291 // xxx - dropping initializer changes behaviour from previous, but seems correct 292 // ^^^ need to handle the case where a tuple has a default argument 293 if ( ! instantiateArgument( location, 294 type, nullptr, args, results, genStart, symtab, nTuples ) ) return false; 295 nTuples = 0; 296 } 297 // re-constitute tuples for final generation 298 for ( auto i = genStart; i < results.size(); ++i ) { 299 results[i].endTuple( results ); 300 } 301 return true; 302 } else if ( const ast::TypeInstType * ttype = Tuples::isTtype( paramType ) ) { 303 // paramType is a ttype, consumes all remaining arguments 304 305 // completed tuples; will be spliced to end of results to finish 306 std::vector< ArgPack > finalResults{}; 307 308 // iterate until all results completed 309 std::size_t genEnd; 310 ++nTuples; 311 do { 312 genEnd = results.size(); 313 314 // add another argument to results 315 for ( std::size_t i = genStart; i < genEnd; ++i ) { 316 unsigned nextArg = results[i].nextArg; 317 318 // use next element of exploded tuple if present 319 if ( results[i].hasExpl() ) { 320 const ExplodedArg & expl = results[i].getExpl( args ); 321 322 unsigned nextExpl = results[i].nextExpl + 1; 323 if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; } 324 325 results.emplace_back( 326 i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ), 327 copy( results[i].need ), copy( results[i].have ), 328 copy( results[i].open ), nextArg, nTuples, Cost::zero, nextExpl, 329 results[i].explAlt ); 330 331 continue; 332 } 333 334 // finish result when out of arguments 335 if ( nextArg >= args.size() ) { 336 ArgPack newResult{ 337 results[i].env, results[i].need, results[i].have, results[i].open }; 338 newResult.nextArg = nextArg; 339 const ast::Type * argType = nullptr; 340 341 if ( nTuples > 0 || ! results[i].expr ) { 342 // first iteration or no expression to clone, 343 // push empty tuple expression 344 newResult.parent = i; 345 newResult.expr = new ast::TupleExpr( location, {} ); 346 argType = newResult.expr->result; 347 } else { 348 // clone result to collect tuple 349 newResult.parent = results[i].parent; 350 newResult.cost = results[i].cost; 351 newResult.tupleStart = results[i].tupleStart; 352 newResult.expr = results[i].expr; 353 argType = newResult.expr->result; 354 355 if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) { 356 // the case where a ttype value is passed directly is special, 357 // e.g. for argument forwarding purposes 358 // xxx - what if passing multiple arguments, last of which is 359 // ttype? 360 // xxx - what would happen if unify was changed so that unifying 361 // tuple 362 // types flattened both before unifying lists? then pass in 363 // TupleType (ttype) below. 364 --newResult.tupleStart; 365 } else { 366 // collapse leftover arguments into tuple 367 newResult.endTuple( results ); 368 argType = newResult.expr->result; 369 } 370 } 371 372 // check unification for ttype before adding to final 373 if ( 374 unify( 375 ttype, argType, newResult.env, newResult.need, newResult.have, 376 newResult.open ) 377 ) { 378 finalResults.emplace_back( std::move( newResult ) ); 379 } 380 381 continue; 382 } 383 384 // add each possible next argument 385 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { 386 const ExplodedArg & expl = args[nextArg][j]; 387 388 // fresh copies of parent parameters for this iteration 389 ast::TypeEnvironment env = results[i].env; 390 ast::OpenVarSet open = results[i].open; 391 392 env.addActual( expl.env, open ); 393 394 // skip empty tuple arguments by (nearly) cloning parent into next gen 395 if ( expl.exprs.empty() ) { 396 results.emplace_back( 397 results[i], std::move( env ), copy( results[i].need ), 398 copy( results[i].have ), std::move( open ), nextArg + 1, expl.cost ); 399 400 continue; 401 } 402 403 // add new result 404 results.emplace_back( 405 i, expl.exprs.front(), std::move( env ), copy( results[i].need ), 406 copy( results[i].have ), std::move( open ), nextArg + 1, nTuples, 407 expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); 408 } 409 } 410 411 // reset for next round 412 genStart = genEnd; 413 nTuples = 0; 414 } while ( genEnd != results.size() ); 415 416 // splice final results onto results 417 for ( std::size_t i = 0; i < finalResults.size(); ++i ) { 418 results.emplace_back( std::move( finalResults[i] ) ); 419 } 420 return ! finalResults.empty(); 421 } 422 423 // iterate each current subresult 424 std::size_t genEnd = results.size(); 425 for ( std::size_t i = genStart; i < genEnd; ++i ) { 426 unsigned nextArg = results[i].nextArg; 427 428 // use remainder of exploded tuple if present 429 if ( results[i].hasExpl() ) { 430 const ExplodedArg & expl = results[i].getExpl( args ); 431 const ast::Expr * expr = expl.exprs[ results[i].nextExpl ]; 432 433 ast::TypeEnvironment env = results[i].env; 434 ast::AssertionSet need = results[i].need, have = results[i].have; 435 ast::OpenVarSet open = results[i].open; 436 437 const ast::Type * argType = expr->result; 438 439 PRINT( 440 std::cerr << "param type is "; 441 ast::print( std::cerr, paramType ); 442 std::cerr << std::endl << "arg type is "; 443 ast::print( std::cerr, argType ); 444 std::cerr << std::endl; 445 ) 446 447 if ( unify( paramType, argType, env, need, have, open ) ) { 448 unsigned nextExpl = results[i].nextExpl + 1; 449 if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; } 450 451 results.emplace_back( 452 i, expr, std::move( env ), std::move( need ), std::move( have ), std::move( open ), nextArg, 453 nTuples, Cost::zero, nextExpl, results[i].explAlt ); 454 } 455 456 continue; 457 } 458 459 // use default initializers if out of arguments 460 if ( nextArg >= args.size() ) { 461 if ( const ast::ConstantExpr * cnst = getDefaultValue( init ) ) { 462 ast::TypeEnvironment env = results[i].env; 463 ast::AssertionSet need = results[i].need, have = results[i].have; 464 ast::OpenVarSet open = results[i].open; 465 466 if ( unify( paramType, cnst->result, env, need, have, open ) ) { 467 results.emplace_back( 468 i, new ast::DefaultArgExpr{ cnst->location, cnst }, std::move( env ), 469 std::move( need ), std::move( have ), std::move( open ), nextArg, nTuples ); 470 } 471 } 472 473 continue; 474 } 475 476 // Check each possible next argument 477 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { 478 const ExplodedArg & expl = args[nextArg][j]; 479 480 // fresh copies of parent parameters for this iteration 481 ast::TypeEnvironment env = results[i].env; 482 ast::AssertionSet need = results[i].need, have = results[i].have; 483 ast::OpenVarSet open = results[i].open; 484 485 env.addActual( expl.env, open ); 486 487 // skip empty tuple arguments by (nearly) cloning parent into next gen 488 if ( expl.exprs.empty() ) { 489 results.emplace_back( 490 results[i], std::move( env ), std::move( need ), std::move( have ), std::move( open ), 491 nextArg + 1, expl.cost ); 492 493 continue; 494 } 495 496 // consider only first exploded arg 497 const ast::Expr * expr = expl.exprs.front(); 498 const ast::Type * argType = expr->result; 499 500 PRINT( 501 std::cerr << "param type is "; 502 ast::print( std::cerr, paramType ); 503 std::cerr << std::endl << "arg type is "; 504 ast::print( std::cerr, argType ); 505 std::cerr << std::endl; 506 ) 507 508 // attempt to unify types 509 if ( unify( paramType, argType, env, need, have, open ) ) { 510 // add new result 511 results.emplace_back( 512 i, expr, std::move( env ), std::move( need ), std::move( have ), std::move( open ), 513 nextArg + 1, nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); 514 } 515 } 516 } 517 518 // reset for next parameter 519 genStart = genEnd; 520 521 return genEnd != results.size(); // were any new results added? 522 } 523 524 /// Generate a cast expression from `arg` to `toType` 525 const ast::Expr * restructureCast( 526 ast::ptr< ast::Expr > & arg, const ast::Type * toType, ast::GeneratedFlag isGenerated = ast::GeneratedCast 527 ) { 528 if ( 529 arg->result->size() > 1 530 && ! toType->isVoid() 531 && ! dynamic_cast< const ast::ReferenceType * >( toType ) 532 ) { 533 // Argument is a tuple and the target type is neither void nor a reference. Cast each 534 // member of the tuple to its corresponding target type, producing the tuple of those 535 // cast expressions. If there are more components of the tuple than components in the 536 // target type, then excess components do not come out in the result expression (but 537 // UniqueExpr ensures that the side effects will still be produced) 538 if ( Tuples::maybeImpureIgnoreUnique( arg ) ) { 539 // expressions which may contain side effects require a single unique instance of 540 // the expression 541 arg = new ast::UniqueExpr{ arg->location, arg }; 542 } 543 std::vector< ast::ptr< ast::Expr > > components; 544 for ( unsigned i = 0; i < toType->size(); ++i ) { 545 // cast each component 546 ast::ptr< ast::Expr > idx = new ast::TupleIndexExpr{ arg->location, arg, i }; 547 components.emplace_back( 548 restructureCast( idx, toType->getComponent( i ), isGenerated ) ); 549 } 550 return new ast::TupleExpr{ arg->location, std::move( components ) }; 551 } else { 552 // handle normally 553 return new ast::CastExpr{ arg->location, arg, toType, isGenerated }; 554 } 555 } 556 557 /// Gets the name from an untyped member expression (must be NameExpr) 558 const std::string & getMemberName( const ast::UntypedMemberExpr * memberExpr ) { 559 if ( memberExpr->member.as< ast::ConstantExpr >() ) { 560 SemanticError( memberExpr, "Indexed access to struct fields unsupported: " ); 561 } 562 563 return memberExpr->member.strict_as< ast::NameExpr >()->name; 564 } 565 566 /// Actually visits expressions to find their candidate interpretations 567 class Finder final : public ast::WithShortCircuiting { 568 const ResolveContext & context; 569 const ast::SymbolTable & symtab; 570 public: 571 // static size_t traceId; 572 CandidateFinder & selfFinder; 573 CandidateList & candidates; 574 const ast::TypeEnvironment & tenv; 575 ast::ptr< ast::Type > & targetType; 576 577 enum Errors { 578 NotFound, 579 NoMatch, 580 ArgsToFew, 581 ArgsToMany, 582 RetsToFew, 583 RetsToMany, 584 NoReason 585 }; 586 587 struct { 588 Errors code = NotFound; 589 } reason; 590 591 Finder( CandidateFinder & f ) 592 : context( f.context ), symtab( context.symtab ), selfFinder( f ), 593 candidates( f.candidates ), tenv( f.env ), targetType( f.targetType ) {} 594 595 void previsit( const ast::Node * ) { visit_children = false; } 596 597 /// Convenience to add candidate to list 598 template<typename... Args> 599 void addCandidate( Args &&... args ) { 600 candidates.emplace_back( new Candidate{ std::forward<Args>( args )... } ); 601 reason.code = NoReason; 602 } 603 604 void postvisit( const ast::ApplicationExpr * applicationExpr ) { 605 addCandidate( applicationExpr, tenv ); 606 } 607 608 /// Set up candidate assertions for inference 609 void inferParameters( CandidateRef & newCand, CandidateList & out ); 610 611 /// Completes a function candidate with arguments located 612 void validateFunctionCandidate( 613 const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results, 614 CandidateList & out ); 615 616 /// Builds a list of candidates for a function, storing them in out 617 void makeFunctionCandidates( 618 const CodeLocation & location, 619 const CandidateRef & func, const ast::FunctionType * funcType, 620 const ExplodedArgs_new & args, CandidateList & out ); 621 622 /// Adds implicit struct-conversions to the alternative list 623 void addAnonConversions( const CandidateRef & cand ); 624 625 /// Adds aggregate member interpretations 626 void addAggMembers( 627 const ast::BaseInstType * aggrInst, const ast::Expr * expr, 628 const Candidate & cand, const Cost & addedCost, const std::string & name 629 ); 630 631 /// Adds tuple member interpretations 632 void addTupleMembers( 633 const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand, 634 const Cost & addedCost, const ast::Expr * member 635 ); 636 637 /// true if expression is an lvalue 638 static bool isLvalue( const ast::Expr * x ) { 639 return x->result && ( x->get_lvalue() || x->result.as< ast::ReferenceType >() ); 640 } 641 642 void postvisit( const ast::UntypedExpr * untypedExpr ); 643 void postvisit( const ast::VariableExpr * variableExpr ); 644 void postvisit( const ast::ConstantExpr * constantExpr ); 645 void postvisit( const ast::SizeofExpr * sizeofExpr ); 646 void postvisit( const ast::AlignofExpr * alignofExpr ); 647 void postvisit( const ast::AddressExpr * addressExpr ); 648 void postvisit( const ast::LabelAddressExpr * labelExpr ); 649 void postvisit( const ast::CastExpr * castExpr ); 650 void postvisit( const ast::VirtualCastExpr * castExpr ); 651 void postvisit( const ast::KeywordCastExpr * castExpr ); 652 void postvisit( const ast::UntypedMemberExpr * memberExpr ); 653 void postvisit( const ast::MemberExpr * memberExpr ); 654 void postvisit( const ast::NameExpr * nameExpr ); 655 void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ); 656 void postvisit( const ast::OffsetofExpr * offsetofExpr ); 657 void postvisit( const ast::OffsetPackExpr * offsetPackExpr ); 658 void postvisit( const ast::LogicalExpr * logicalExpr ); 659 void postvisit( const ast::ConditionalExpr * conditionalExpr ); 660 void postvisit( const ast::CommaExpr * commaExpr ); 661 void postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr ); 662 void postvisit( const ast::ConstructorExpr * ctorExpr ); 663 void postvisit( const ast::RangeExpr * rangeExpr ); 664 void postvisit( const ast::UntypedTupleExpr * tupleExpr ); 665 void postvisit( const ast::TupleExpr * tupleExpr ); 666 void postvisit( const ast::TupleIndexExpr * tupleExpr ); 667 void postvisit( const ast::TupleAssignExpr * tupleExpr ); 668 void postvisit( const ast::UniqueExpr * unqExpr ); 669 void postvisit( const ast::StmtExpr * stmtExpr ); 670 void postvisit( const ast::UntypedInitExpr * initExpr ); 671 672 void postvisit( const ast::InitExpr * ) { 673 assertf( false, "CandidateFinder should never see a resolved InitExpr." ); 674 } 675 676 void postvisit( const ast::DeletedExpr * ) { 677 assertf( false, "CandidateFinder should never see a DeletedExpr." ); 678 } 679 680 void postvisit( const ast::GenericExpr * ) { 681 assertf( false, "_Generic is not yet supported." ); 682 } 683 }; 684 685 /// Set up candidate assertions for inference 686 void Finder::inferParameters( CandidateRef & newCand, CandidateList & out ) { 687 // Set need bindings for any unbound assertions 688 UniqueId crntResnSlot = 0; // matching ID for this expression's assertions 689 for ( auto & assn : newCand->need ) { 690 // skip already-matched assertions 691 if ( assn.second.resnSlot != 0 ) continue; 692 // assign slot for expression if needed 693 if ( crntResnSlot == 0 ) { crntResnSlot = ++globalResnSlot; } 694 // fix slot to assertion 695 assn.second.resnSlot = crntResnSlot; 696 } 697 // pair slot to expression 698 if ( crntResnSlot != 0 ) { 699 newCand->expr.get_and_mutate()->inferred.resnSlots().emplace_back( crntResnSlot ); 700 } 701 702 // add to output list; assertion satisfaction will occur later 703 out.emplace_back( newCand ); 704 } 705 706 /// Completes a function candidate with arguments located 707 void Finder::validateFunctionCandidate( 708 const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results, 709 CandidateList & out 710 ) { 711 ast::ApplicationExpr * appExpr = 712 new ast::ApplicationExpr{ func->expr->location, func->expr }; 713 // sum cost and accumulate arguments 714 std::deque< const ast::Expr * > args; 715 Cost cost = func->cost; 716 const ArgPack * pack = &result; 717 while ( pack->expr ) { 718 args.emplace_front( pack->expr ); 719 cost += pack->cost; 720 pack = &results[pack->parent]; 721 } 722 std::vector< ast::ptr< ast::Expr > > vargs( args.begin(), args.end() ); 723 appExpr->args = std::move( vargs ); 724 // build and validate new candidate 725 auto newCand = 726 std::make_shared<Candidate>( appExpr, result.env, result.open, result.need, cost ); 727 PRINT( 728 std::cerr << "instantiate function success: " << appExpr << std::endl; 729 std::cerr << "need assertions:" << std::endl; 730 ast::print( std::cerr, result.need, 2 ); 731 ) 732 inferParameters( newCand, out ); 733 } 734 735 /// Builds a list of candidates for a function, storing them in out 736 void Finder::makeFunctionCandidates( 737 const CodeLocation & location, 738 const CandidateRef & func, const ast::FunctionType * funcType, 739 const ExplodedArgs_new & args, CandidateList & out 740 ) { 741 ast::OpenVarSet funcOpen; 742 ast::AssertionSet funcNeed, funcHave; 743 ast::TypeEnvironment funcEnv{ func->env }; 744 makeUnifiableVars( funcType, funcOpen, funcNeed ); 745 // add all type variables as open variables now so that those not used in the 746 // parameter list are still considered open 747 funcEnv.add( funcType->forall ); 748 749 if ( targetType && ! targetType->isVoid() && ! funcType->returns.empty() ) { 750 // attempt to narrow based on expected target type 751 const ast::Type * returnType = funcType->returns.front(); 752 if ( selfFinder.strictMode ) { 753 if ( ! unifyExact( 754 returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen, noWiden() ) // xxx - is no widening correct? 755 ) { 756 // unification failed, do not pursue this candidate 757 return; 758 } 759 } 760 else { 761 if ( ! unify( 762 returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen ) 763 ) { 764 // unification failed, do not pursue this candidate 765 return; 766 } 767 } 768 } 769 770 // iteratively build matches, one parameter at a time 771 std::vector< ArgPack > results; 772 results.emplace_back( funcEnv, funcNeed, funcHave, funcOpen ); 773 std::size_t genStart = 0; 774 775 // xxx - how to handle default arg after change to ftype representation? 776 if (const ast::VariableExpr * varExpr = func->expr.as<ast::VariableExpr>()) { 777 if (const ast::FunctionDecl * funcDecl = varExpr->var.as<ast::FunctionDecl>()) { 778 // function may have default args only if directly calling by name 779 // must use types on candidate however, due to RenameVars substitution 780 auto nParams = funcType->params.size(); 781 782 for (size_t i=0; i<nParams; ++i) { 783 auto obj = funcDecl->params[i].strict_as<ast::ObjectDecl>(); 784 if ( !instantiateArgument( location, 785 funcType->params[i], obj->init, args, results, genStart, symtab)) return; 786 } 787 goto endMatch; 788 } 789 } 790 for ( const auto & param : funcType->params ) { 791 // Try adding the arguments corresponding to the current parameter to the existing 792 // matches 793 // no default args for indirect calls 794 if ( !instantiateArgument( location, 795 param, nullptr, args, results, genStart, symtab ) ) return; 796 } 797 798 endMatch: 799 if ( funcType->isVarArgs ) { 800 // append any unused arguments to vararg pack 801 std::size_t genEnd; 802 do { 803 genEnd = results.size(); 804 805 // iterate results 806 for ( std::size_t i = genStart; i < genEnd; ++i ) { 807 unsigned nextArg = results[i].nextArg; 808 809 // use remainder of exploded tuple if present 810 if ( results[i].hasExpl() ) { 811 const ExplodedArg & expl = results[i].getExpl( args ); 812 813 unsigned nextExpl = results[i].nextExpl + 1; 814 if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; } 815 816 results.emplace_back( 817 i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ), 818 copy( results[i].need ), copy( results[i].have ), 819 copy( results[i].open ), nextArg, 0, Cost::zero, nextExpl, 820 results[i].explAlt ); 821 822 continue; 823 } 824 825 // finish result when out of arguments 826 if ( nextArg >= args.size() ) { 827 validateFunctionCandidate( func, results[i], results, out ); 828 829 continue; 830 } 831 832 // add each possible next argument 833 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { 834 const ExplodedArg & expl = args[nextArg][j]; 835 836 // fresh copies of parent parameters for this iteration 837 ast::TypeEnvironment env = results[i].env; 838 ast::OpenVarSet open = results[i].open; 839 840 env.addActual( expl.env, open ); 841 842 // skip empty tuple arguments by (nearly) cloning parent into next gen 843 if ( expl.exprs.empty() ) { 844 results.emplace_back( 845 results[i], std::move( env ), copy( results[i].need ), 846 copy( results[i].have ), std::move( open ), nextArg + 1, 847 expl.cost ); 848 849 continue; 850 } 851 852 // add new result 853 results.emplace_back( 854 i, expl.exprs.front(), std::move( env ), copy( results[i].need ), 855 copy( results[i].have ), std::move( open ), nextArg + 1, 0, expl.cost, 856 expl.exprs.size() == 1 ? 0 : 1, j ); 857 } 858 } 859 860 genStart = genEnd; 861 } while( genEnd != results.size() ); 862 } else { 863 // filter out the results that don't use all the arguments 864 for ( std::size_t i = genStart; i < results.size(); ++i ) { 865 ArgPack & result = results[i]; 866 if ( ! result.hasExpl() && result.nextArg >= args.size() ) { 867 validateFunctionCandidate( func, result, results, out ); 868 } 869 } 870 } 871 } 872 873 /// Adds implicit struct-conversions to the alternative list 874 void Finder::addAnonConversions( const CandidateRef & cand ) { 875 // adds anonymous member interpretations whenever an aggregate value type is seen. 876 // it's okay for the aggregate expression to have reference type -- cast it to the 877 // base type to treat the aggregate as the referenced value 878 ast::ptr< ast::Expr > aggrExpr( cand->expr ); 879 ast::ptr< ast::Type > & aggrType = aggrExpr.get_and_mutate()->result; 880 cand->env.apply( aggrType ); 881 882 if ( aggrType.as< ast::ReferenceType >() ) { 883 aggrExpr = new ast::CastExpr{ aggrExpr, aggrType->stripReferences() }; 884 } 885 886 if ( auto structInst = aggrExpr->result.as< ast::StructInstType >() ) { 887 addAggMembers( structInst, aggrExpr, *cand, Cost::unsafe, "" ); 888 } else if ( auto unionInst = aggrExpr->result.as< ast::UnionInstType >() ) { 889 addAggMembers( unionInst, aggrExpr, *cand, Cost::unsafe, "" ); 890 } 891 } 892 893 /// Adds aggregate member interpretations 894 void Finder::addAggMembers( 895 const ast::BaseInstType * aggrInst, const ast::Expr * expr, 896 const Candidate & cand, const Cost & addedCost, const std::string & name 897 ) { 898 for ( const ast::Decl * decl : aggrInst->lookup( name ) ) { 899 auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( decl ); 900 CandidateRef newCand = std::make_shared<Candidate>( 901 cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost ); 902 // add anonymous member interpretations whenever an aggregate value type is seen 903 // as a member expression 904 addAnonConversions( newCand ); 905 candidates.emplace_back( std::move( newCand ) ); 906 } 907 } 908 909 /// Adds tuple member interpretations 910 void Finder::addTupleMembers( 911 const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand, 912 const Cost & addedCost, const ast::Expr * member 913 ) { 914 if ( auto constantExpr = dynamic_cast< const ast::ConstantExpr * >( member ) ) { 915 // get the value of the constant expression as an int, must be between 0 and the 916 // length of the tuple to have meaning 917 long long val = constantExpr->intValue(); 918 if ( val >= 0 && (unsigned long long)val < tupleType->size() ) { 919 addCandidate( 920 cand, new ast::TupleIndexExpr{ expr->location, expr, (unsigned)val }, 921 addedCost ); 922 } 923 } 924 } 925 926 void Finder::postvisit( const ast::UntypedExpr * untypedExpr ) { 927 std::vector< CandidateFinder > argCandidates = 928 selfFinder.findSubExprs( untypedExpr->args ); 929 930 // take care of possible tuple assignments 931 // if not tuple assignment, handled as normal function call 932 Tuples::handleTupleAssignment( selfFinder, untypedExpr, argCandidates ); 933 934 CandidateFinder funcFinder( context, tenv ); 935 if (auto nameExpr = untypedExpr->func.as<ast::NameExpr>()) { 936 auto kind = ast::SymbolTable::getSpecialFunctionKind(nameExpr->name); 937 if (kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS) { 938 assertf(!argCandidates.empty(), "special function call without argument"); 939 for (auto & firstArgCand: argCandidates[0]) { 940 ast::ptr<ast::Type> argType = firstArgCand->expr->result; 941 firstArgCand->env.apply(argType); 942 // strip references 943 // xxx - is this correct? 944 while (argType.as<ast::ReferenceType>()) argType = argType.as<ast::ReferenceType>()->base; 945 946 // convert 1-tuple to plain type 947 if (auto tuple = argType.as<ast::TupleType>()) { 948 if (tuple->size() == 1) { 949 argType = tuple->types[0]; 950 } 951 } 952 953 // if argType is an unbound type parameter, all special functions need to be searched. 954 if (isUnboundType(argType)) { 955 funcFinder.otypeKeys.clear(); 956 break; 957 } 958 959 if (argType.as<ast::PointerType>()) funcFinder.otypeKeys.insert(Mangle::Encoding::pointer); 960 // else if (const ast::EnumInstType * enumInst = argType.as<ast::EnumInstType>()) { 961 // const ast::EnumDecl * enumDecl = enumInst->base; // Here 962 // if ( const ast::Type* enumType = enumDecl->base ) { 963 // // instance of enum (T) is a instance of type (T) 964 // funcFinder.otypeKeys.insert(Mangle::mangle(enumType, Mangle::NoGenericParams | Mangle::Type)); 965 // } else { 966 // // instance of an untyped enum is techically int 967 // funcFinder.otypeKeys.insert(Mangle::mangle(enumDecl, Mangle::NoGenericParams | Mangle::Type)); 968 // } 969 // } 970 else funcFinder.otypeKeys.insert(Mangle::mangle(argType, Mangle::NoGenericParams | Mangle::Type)); 971 } 972 } 973 } 974 // if candidates are already produced, do not fail 975 // xxx - is it possible that handleTupleAssignment and main finder both produce candidates? 976 // this means there exists ctor/assign functions with a tuple as first parameter. 977 ResolvMode mode = { 978 true, // adjust 979 !untypedExpr->func.as<ast::NameExpr>(), // prune if not calling by name 980 selfFinder.candidates.empty() // failfast if other options are not found 981 }; 982 funcFinder.find( untypedExpr->func, mode ); 983 // short-circuit if no candidates 984 // if ( funcFinder.candidates.empty() ) return; 985 986 reason.code = NoMatch; 987 988 // find function operators 989 ast::ptr< ast::Expr > opExpr = new ast::NameExpr{ untypedExpr->location, "?()" }; // ??? why not ?{} 990 CandidateFinder opFinder( context, tenv ); 991 // okay if there aren't any function operations 992 opFinder.find( opExpr, ResolvMode::withoutFailFast() ); 993 PRINT( 994 std::cerr << "known function ops:" << std::endl; 995 print( std::cerr, opFinder.candidates, 1 ); 996 ) 997 998 // pre-explode arguments 999 ExplodedArgs_new argExpansions; 1000 for ( const CandidateFinder & args : argCandidates ) { 1001 argExpansions.emplace_back(); 1002 auto & argE = argExpansions.back(); 1003 for ( const CandidateRef & arg : args ) { argE.emplace_back( *arg, symtab ); } 1004 } 1005 1006 // Find function matches 1007 CandidateList found; 1008 SemanticErrorException errors; 1009 for ( CandidateRef & func : funcFinder ) { 1010 try { 1011 PRINT( 1012 std::cerr << "working on alternative:" << std::endl; 1013 print( std::cerr, *func, 2 ); 1014 ) 1015 1016 // check if the type is a pointer to function 1017 const ast::Type * funcResult = func->expr->result->stripReferences(); 1018 if ( auto pointer = dynamic_cast< const ast::PointerType * >( funcResult ) ) { 1019 if ( auto function = pointer->base.as< ast::FunctionType >() ) { 1020 // if (!selfFinder.allowVoid && function->returns.empty()) continue; 1021 CandidateRef newFunc{ new Candidate{ *func } }; 1022 newFunc->expr = 1023 referenceToRvalueConversion( newFunc->expr, newFunc->cost ); 1024 makeFunctionCandidates( untypedExpr->location, 1025 newFunc, function, argExpansions, found ); 1026 } 1027 } else if ( 1028 auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult ) 1029 ) { 1030 if ( const ast::EqvClass * clz = func->env.lookup( *inst ) ) { 1031 if ( auto function = clz->bound.as< ast::FunctionType >() ) { 1032 CandidateRef newFunc( new Candidate( *func ) ); 1033 newFunc->expr = 1034 referenceToRvalueConversion( newFunc->expr, newFunc->cost ); 1035 makeFunctionCandidates( untypedExpr->location, 1036 newFunc, function, argExpansions, found ); 1037 } 1038 } 1039 } 1040 } catch ( SemanticErrorException & e ) { errors.append( e ); } 1041 } 1042 1043 // Find matches on function operators `?()` 1044 if ( ! opFinder.candidates.empty() ) { 1045 // add exploded function alternatives to front of argument list 1046 std::vector< ExplodedArg > funcE; 1047 funcE.reserve( funcFinder.candidates.size() ); 1048 for ( const CandidateRef & func : funcFinder ) { 1049 funcE.emplace_back( *func, symtab ); 1050 } 1051 argExpansions.emplace_front( std::move( funcE ) ); 1052 1053 for ( const CandidateRef & op : opFinder ) { 1054 try { 1055 // check if type is pointer-to-function 1056 const ast::Type * opResult = op->expr->result->stripReferences(); 1057 if ( auto pointer = dynamic_cast< const ast::PointerType * >( opResult ) ) { 1058 if ( auto function = pointer->base.as< ast::FunctionType >() ) { 1059 CandidateRef newOp{ new Candidate{ *op} }; 1060 newOp->expr = 1061 referenceToRvalueConversion( newOp->expr, newOp->cost ); 1062 makeFunctionCandidates( untypedExpr->location, 1063 newOp, function, argExpansions, found ); 1064 } 1065 } 1066 } catch ( SemanticErrorException & e ) { errors.append( e ); } 1067 } 1068 } 1069 1070 // Implement SFINAE; resolution errors are only errors if there aren't any non-error 1071 // candidates 1072 if ( found.empty() && ! errors.isEmpty() ) { throw errors; } 1073 1074 // only keep the best matching intrinsic result to match C semantics (no unexpected narrowing/widening) 1075 // TODO: keep one for each set of argument candidates? 1076 Cost intrinsicCost = Cost::infinity; 1077 CandidateList intrinsicResult; 1078 1079 // Compute conversion costs 1080 for ( CandidateRef & withFunc : found ) { 1081 Cost cvtCost = computeApplicationConversionCost( withFunc, symtab ); 1082 1083 PRINT( 1084 auto appExpr = withFunc->expr.strict_as< ast::ApplicationExpr >(); 1085 auto pointer = appExpr->func->result.strict_as< ast::PointerType >(); 1086 auto function = pointer->base.strict_as< ast::FunctionType >(); 1087 1088 std::cerr << "Case +++++++++++++ " << appExpr->func << std::endl; 1089 std::cerr << "parameters are:" << std::endl; 1090 ast::printAll( std::cerr, function->params, 2 ); 1091 std::cerr << "arguments are:" << std::endl; 1092 ast::printAll( std::cerr, appExpr->args, 2 ); 1093 std::cerr << "bindings are:" << std::endl; 1094 ast::print( std::cerr, withFunc->env, 2 ); 1095 std::cerr << "cost is: " << withFunc->cost << std::endl; 1096 std::cerr << "cost of conversion is:" << cvtCost << std::endl; 1097 ) 1098 1099 if ( cvtCost != Cost::infinity ) { 1100 withFunc->cvtCost = cvtCost; 1101 withFunc->cost += cvtCost; 1102 auto func = withFunc->expr.strict_as<ast::ApplicationExpr>()->func.as<ast::VariableExpr>(); 1103 if (func && func->var->linkage == ast::Linkage::Intrinsic) { 1104 if (withFunc->cost < intrinsicCost) { 1105 intrinsicResult.clear(); 1106 intrinsicCost = withFunc->cost; 1107 } 1108 if (withFunc->cost == intrinsicCost) { 1109 intrinsicResult.emplace_back(std::move(withFunc)); 1110 } 1111 } 1112 else { 1113 candidates.emplace_back( std::move( withFunc ) ); 1114 } 1115 } 1116 } 1117 spliceBegin( candidates, intrinsicResult ); 1118 found = std::move( candidates ); 1119 1120 // use a new list so that candidates are not examined by addAnonConversions twice 1121 // CandidateList winners = findMinCost( found ); 1122 // promoteCvtCost( winners ); 1123 1124 // function may return a struct/union value, in which case we need to add candidates 1125 // for implicit conversions to each of the anonymous members, which must happen after 1126 // `findMinCost`, since anon conversions are never the cheapest 1127 for ( const CandidateRef & c : found ) { 1128 addAnonConversions( c ); 1129 } 1130 // would this be too slow when we don't check cost anymore? 1131 spliceBegin( candidates, found ); 1132 1133 if ( candidates.empty() && targetType && ! targetType->isVoid() && !selfFinder.strictMode ) { 1134 // If resolution is unsuccessful with a target type, try again without, since it 1135 // will sometimes succeed when it wouldn't with a target type binding. 1136 // For example: 1137 // forall( otype T ) T & ?[]( T *, ptrdiff_t ); 1138 // const char * x = "hello world"; 1139 // unsigned char ch = x[0]; 1140 // Fails with simple return type binding (xxx -- check this!) as follows: 1141 // * T is bound to unsigned char 1142 // * (x: const char *) is unified with unsigned char *, which fails 1143 // xxx -- fix this better 1144 targetType = nullptr; 1145 postvisit( untypedExpr ); 1146 } 1147 } 1148 1149 void Finder::postvisit( const ast::AddressExpr * addressExpr ) { 1150 CandidateFinder finder( context, tenv ); 1151 finder.find( addressExpr->arg ); 1152 1153 if ( finder.candidates.empty() ) return; 1154 1155 reason.code = NoMatch; 1156 1157 for ( CandidateRef & r : finder.candidates ) { 1158 if ( ! isLvalue( r->expr ) ) continue; 1159 addCandidate( *r, new ast::AddressExpr{ addressExpr->location, r->expr } ); 1160 } 1161 } 1162 1163 void Finder::postvisit( const ast::LabelAddressExpr * labelExpr ) { 1164 addCandidate( labelExpr, tenv ); 1165 } 1166 1167 void Finder::postvisit( const ast::CastExpr * castExpr ) { 1168 ast::ptr< ast::Type > toType = castExpr->result; 1169 assert( toType ); 1170 toType = resolveTypeof( toType, context ); 1171 toType = adjustExprType( toType, tenv, symtab ); 1172 1173 CandidateFinder finder( context, tenv, toType ); 1174 if (toType->isVoid()) { 1175 finder.allowVoid = true; 1176 } 1177 if ( castExpr->kind == ast::CastExpr::Return ) { 1178 finder.strictMode = true; 1179 finder.find( castExpr->arg, ResolvMode::withAdjustment() ); 1180 1181 // return casts are eliminated (merely selecting an overload, no actual operation) 1182 candidates = std::move(finder.candidates); 1183 } 1184 finder.find( castExpr->arg, ResolvMode::withAdjustment() ); 1185 1186 if ( !finder.candidates.empty() ) reason.code = NoMatch; 1187 1188 CandidateList matches; 1189 Cost minExprCost = Cost::infinity; 1190 Cost minCastCost = Cost::infinity; 1191 for ( CandidateRef & cand : finder.candidates ) { 1192 ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have; 1193 ast::OpenVarSet open( cand->open ); 1194 1195 cand->env.extractOpenVars( open ); 1196 1197 // It is possible that a cast can throw away some values in a multiply-valued 1198 // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of the 1199 // subexpression results that are cast directly. The candidate is invalid if it 1200 // has fewer results than there are types to cast to. 1201 int discardedValues = cand->expr->result->size() - toType->size(); 1202 if ( discardedValues < 0 ) continue; 1203 1204 // unification run for side-effects 1205 unify( toType, cand->expr->result, cand->env, need, have, open ); 1206 Cost thisCost = 1207 (castExpr->isGenerated == ast::GeneratedFlag::GeneratedCast) 1208 ? conversionCost( cand->expr->result, toType, cand->expr->get_lvalue(), symtab, cand->env ) 1209 : castCost( cand->expr->result, toType, cand->expr->get_lvalue(), symtab, cand->env ); 1210 1211 PRINT( 1212 std::cerr << "working on cast with result: " << toType << std::endl; 1213 std::cerr << "and expr type: " << cand->expr->result << std::endl; 1214 std::cerr << "env: " << cand->env << std::endl; 1215 ) 1216 if ( thisCost != Cost::infinity ) { 1217 PRINT( 1218 std::cerr << "has finite cost." << std::endl; 1219 ) 1220 // count one safe conversion for each value that is thrown away 1221 thisCost.incSafe( discardedValues ); 1222 // select first on argument cost, then conversion cost 1223 if ( cand->cost < minExprCost || ( cand->cost == minExprCost && thisCost < minCastCost ) ) { 1224 minExprCost = cand->cost; 1225 minCastCost = thisCost; 1226 matches.clear(); 1227 1228 1229 } 1230 // ambiguous case, still output candidates to print in error message 1231 if ( cand->cost == minExprCost && thisCost == minCastCost ) { 1232 CandidateRef newCand = std::make_shared<Candidate>( 1233 restructureCast( cand->expr, toType, castExpr->isGenerated ), 1234 copy( cand->env ), std::move( open ), std::move( need ), cand->cost + thisCost); 1235 // currently assertions are always resolved immediately so this should have no effect. 1236 // if this somehow changes in the future (e.g. delayed by indeterminate return type) 1237 // we may need to revisit the logic. 1238 inferParameters( newCand, matches ); 1239 } 1240 // else skip, better alternatives found 1241 1242 } 1243 } 1244 candidates = std::move(matches); 1245 1246 //CandidateList minArgCost = findMinCost( matches ); 1247 //promoteCvtCost( minArgCost ); 1248 //candidates = findMinCost( minArgCost ); 1249 } 1250 1251 void Finder::postvisit( const ast::VirtualCastExpr * castExpr ) { 1252 assertf( castExpr->result, "Implicit virtual cast targets not yet supported." ); 1253 CandidateFinder finder( context, tenv ); 1254 // don't prune here, all alternatives guaranteed to have same type 1255 finder.find( castExpr->arg, ResolvMode::withoutPrune() ); 1256 for ( CandidateRef & r : finder.candidates ) { 1257 addCandidate( 1258 *r, 1259 new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } ); 1260 } 1261 } 1262 1263 void Finder::postvisit( const ast::KeywordCastExpr * castExpr ) { 1264 const auto & loc = castExpr->location; 1265 assertf( castExpr->result, "Cast target should have been set in Validate." ); 1266 auto ref = castExpr->result.strict_as<ast::ReferenceType>(); 1267 auto inst = ref->base.strict_as<ast::StructInstType>(); 1268 auto target = inst->base.get(); 1269 1270 CandidateFinder finder( context, tenv ); 1271 1272 auto pick_alternatives = [target, this](CandidateList & found, bool expect_ref) { 1273 for (auto & cand : found) { 1274 const ast::Type * expr = cand->expr->result.get(); 1275 if (expect_ref) { 1276 auto res = dynamic_cast<const ast::ReferenceType*>(expr); 1277 if (!res) { continue; } 1278 expr = res->base.get(); 1279 } 1280 1281 if (auto insttype = dynamic_cast<const ast::TypeInstType*>(expr)) { 1282 auto td = cand->env.lookup(*insttype); 1283 if (!td) { continue; } 1284 expr = td->bound.get(); 1285 } 1286 1287 if (auto base = dynamic_cast<const ast::StructInstType*>(expr)) { 1288 if (base->base == target) { 1289 candidates.push_back( std::move(cand) ); 1290 reason.code = NoReason; 1291 } 1292 } 1293 } 1294 }; 1295 1296 try { 1297 // Attempt 1 : turn (thread&)X into (thread$&)X.__thrd 1298 // Clone is purely for memory management 1299 std::unique_ptr<const ast::Expr> tech1 { new ast::UntypedMemberExpr(loc, new ast::NameExpr(loc, castExpr->concrete_target.field), castExpr->arg) }; 1300 1301 // don't prune here, since it's guaranteed all alternatives will have the same type 1302 finder.find( tech1.get(), ResolvMode::withoutPrune() ); 1303 pick_alternatives(finder.candidates, false); 1304 1305 return; 1306 } catch(SemanticErrorException & ) {} 1307 1308 // Fallback : turn (thread&)X into (thread$&)get_thread(X) 1309 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 })) }; 1310 // don't prune here, since it's guaranteed all alternatives will have the same type 1311 finder.find( fallback.get(), ResolvMode::withoutPrune() ); 1312 1313 pick_alternatives(finder.candidates, true); 1314 1315 // Whatever happens here, we have no more fallbacks 1316 } 1317 1318 void Finder::postvisit( const ast::UntypedMemberExpr * memberExpr ) { 1319 CandidateFinder aggFinder( context, tenv ); 1320 aggFinder.find( memberExpr->aggregate, ResolvMode::withAdjustment() ); 1321 for ( CandidateRef & agg : aggFinder.candidates ) { 1322 // it's okay for the aggregate expression to have reference type -- cast it to the 1323 // base type to treat the aggregate as the referenced value 1324 Cost addedCost = Cost::zero; 1325 agg->expr = referenceToRvalueConversion( agg->expr, addedCost ); 1326 1327 // find member of the given type 1328 if ( auto structInst = agg->expr->result.as< ast::StructInstType >() ) { 1329 addAggMembers( 1330 structInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) ); 1331 } else if ( auto unionInst = agg->expr->result.as< ast::UnionInstType >() ) { 1332 addAggMembers( 1333 unionInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) ); 1334 } else if ( auto tupleType = agg->expr->result.as< ast::TupleType >() ) { 1335 addTupleMembers( tupleType, agg->expr, *agg, addedCost, memberExpr->member ); 1336 } 1337 } 1338 } 1339 1340 void Finder::postvisit( const ast::MemberExpr * memberExpr ) { 1341 addCandidate( memberExpr, tenv ); 1342 } 1343 1344 void Finder::postvisit( const ast::NameExpr * nameExpr ) { 1345 std::vector< ast::SymbolTable::IdData > declList; 1346 if (!selfFinder.otypeKeys.empty()) { 1347 auto kind = ast::SymbolTable::getSpecialFunctionKind(nameExpr->name); 1348 assertf(kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS, "special lookup with non-special target: %s", nameExpr->name.c_str()); 1349 1350 for (auto & otypeKey: selfFinder.otypeKeys) { 1351 auto result = symtab.specialLookupId(kind, otypeKey); 1352 declList.insert(declList.end(), std::make_move_iterator(result.begin()), std::make_move_iterator(result.end())); 1353 } 1354 } else { 1355 declList = symtab.lookupId( nameExpr->name ); 1356 } 1357 PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; ) 1358 1359 if ( declList.empty() ) return; 1360 1361 reason.code = NoMatch; 1362 1363 for ( auto & data : declList ) { 1364 Cost cost = Cost::zero; 1365 ast::Expr * newExpr = data.combine( nameExpr->location, cost ); 1366 1367 CandidateRef newCand = std::make_shared<Candidate>( 1368 newExpr, copy( tenv ), ast::OpenVarSet{}, ast::AssertionSet{}, Cost::zero, 1369 cost ); 1370 1371 if (newCand->expr->env) { 1372 newCand->env.add(*newCand->expr->env); 1373 auto mutExpr = newCand->expr.get_and_mutate(); 1374 mutExpr->env = nullptr; 1375 newCand->expr = mutExpr; 1376 } 1377 1378 PRINT( 1379 std::cerr << "decl is "; 1380 ast::print( std::cerr, data.id ); 1381 std::cerr << std::endl; 1382 std::cerr << "newExpr is "; 1383 ast::print( std::cerr, newExpr ); 1384 std::cerr << std::endl; 1385 ) 1386 newCand->expr = ast::mutate_field( 1387 newCand->expr.get(), &ast::Expr::result, 1388 renameTyVars( newCand->expr->result ) ); 1389 // add anonymous member interpretations whenever an aggregate value type is seen 1390 // as a name expression 1391 addAnonConversions( newCand ); 1392 candidates.emplace_back( std::move( newCand ) ); 1393 } 1394 } 1395 1396 void Finder::postvisit( const ast::VariableExpr * variableExpr ) { 1397 // not sufficient to just pass `variableExpr` here, type might have changed since 1398 // creation 1399 addCandidate( 1400 new ast::VariableExpr{ variableExpr->location, variableExpr->var }, tenv ); 1401 } 1402 1403 void Finder::postvisit( const ast::ConstantExpr * constantExpr ) { 1404 addCandidate( constantExpr, tenv ); 1405 } 1406 1407 void Finder::postvisit( const ast::SizeofExpr * sizeofExpr ) { 1408 if ( sizeofExpr->type ) { 1409 addCandidate( 1410 new ast::SizeofExpr{ 1411 sizeofExpr->location, resolveTypeof( sizeofExpr->type, context ) }, 1412 tenv ); 1413 } else { 1414 // find all candidates for the argument to sizeof 1415 CandidateFinder finder( context, tenv ); 1416 finder.find( sizeofExpr->expr ); 1417 // find the lowest-cost candidate, otherwise ambiguous 1418 CandidateList winners = findMinCost( finder.candidates ); 1419 if ( winners.size() != 1 ) { 1420 SemanticError( 1421 sizeofExpr->expr.get(), "Ambiguous expression in sizeof operand: " ); 1422 } 1423 // return the lowest-cost candidate 1424 CandidateRef & choice = winners.front(); 1425 choice->expr = referenceToRvalueConversion( choice->expr, choice->cost ); 1426 choice->cost = Cost::zero; 1427 addCandidate( *choice, new ast::SizeofExpr{ sizeofExpr->location, choice->expr } ); 1428 } 1429 } 1430 1431 void Finder::postvisit( const ast::AlignofExpr * alignofExpr ) { 1432 if ( alignofExpr->type ) { 1433 addCandidate( 1434 new ast::AlignofExpr{ 1435 alignofExpr->location, resolveTypeof( alignofExpr->type, context ) }, 1436 tenv ); 1437 } else { 1438 // find all candidates for the argument to alignof 1439 CandidateFinder finder( context, tenv ); 1440 finder.find( alignofExpr->expr ); 1441 // find the lowest-cost candidate, otherwise ambiguous 1442 CandidateList winners = findMinCost( finder.candidates ); 1443 if ( winners.size() != 1 ) { 1444 SemanticError( 1445 alignofExpr->expr.get(), "Ambiguous expression in alignof operand: " ); 1446 } 1447 // return the lowest-cost candidate 1448 CandidateRef & choice = winners.front(); 1449 choice->expr = referenceToRvalueConversion( choice->expr, choice->cost ); 1450 choice->cost = Cost::zero; 1451 addCandidate( 1452 *choice, new ast::AlignofExpr{ alignofExpr->location, choice->expr } ); 1453 } 1454 } 1455 1456 void Finder::postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) { 1457 const ast::BaseInstType * aggInst; 1458 if (( aggInst = offsetofExpr->type.as< ast::StructInstType >() )) ; 1459 else if (( aggInst = offsetofExpr->type.as< ast::UnionInstType >() )) ; 1460 else return; 1461 1462 for ( const ast::Decl * member : aggInst->lookup( offsetofExpr->member ) ) { 1463 auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( member ); 1464 addCandidate( 1465 new ast::OffsetofExpr{ offsetofExpr->location, aggInst, dwt }, tenv ); 1466 } 1467 } 1468 1469 void Finder::postvisit( const ast::OffsetofExpr * offsetofExpr ) { 1470 addCandidate( offsetofExpr, tenv ); 1471 } 1472 1473 void Finder::postvisit( const ast::OffsetPackExpr * offsetPackExpr ) { 1474 addCandidate( offsetPackExpr, tenv ); 1475 } 1476 1477 void Finder::postvisit( const ast::LogicalExpr * logicalExpr ) { 1478 CandidateFinder finder1( context, tenv ); 1479 finder1.find( logicalExpr->arg1, ResolvMode::withAdjustment() ); 1480 if ( finder1.candidates.empty() ) return; 1481 1482 CandidateFinder finder2( context, tenv ); 1483 finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() ); 1484 if ( finder2.candidates.empty() ) return; 1485 1486 reason.code = NoMatch; 1487 1488 for ( const CandidateRef & r1 : finder1.candidates ) { 1489 for ( const CandidateRef & r2 : finder2.candidates ) { 1490 ast::TypeEnvironment env{ r1->env }; 1491 env.simpleCombine( r2->env ); 1492 ast::OpenVarSet open{ r1->open }; 1493 mergeOpenVars( open, r2->open ); 1494 ast::AssertionSet need; 1495 mergeAssertionSet( need, r1->need ); 1496 mergeAssertionSet( need, r2->need ); 1497 1498 addCandidate( 1499 new ast::LogicalExpr{ 1500 logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd }, 1501 std::move( env ), std::move( open ), std::move( need ), r1->cost + r2->cost ); 1502 } 1503 } 1504 } 1505 1506 void Finder::postvisit( const ast::ConditionalExpr * conditionalExpr ) { 1507 // candidates for condition 1508 CandidateFinder finder1( context, tenv ); 1509 finder1.find( conditionalExpr->arg1, ResolvMode::withAdjustment() ); 1510 if ( finder1.candidates.empty() ) return; 1511 1512 // candidates for true result 1513 CandidateFinder finder2( context, tenv ); 1514 finder2.allowVoid = true; 1515 finder2.find( conditionalExpr->arg2, ResolvMode::withAdjustment() ); 1516 if ( finder2.candidates.empty() ) return; 1517 1518 // candidates for false result 1519 CandidateFinder finder3( context, tenv ); 1520 finder3.allowVoid = true; 1521 finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() ); 1522 if ( finder3.candidates.empty() ) return; 1523 1524 reason.code = NoMatch; 1525 1526 for ( const CandidateRef & r1 : finder1.candidates ) { 1527 for ( const CandidateRef & r2 : finder2.candidates ) { 1528 for ( const CandidateRef & r3 : finder3.candidates ) { 1529 ast::TypeEnvironment env{ r1->env }; 1530 env.simpleCombine( r2->env ); 1531 env.simpleCombine( r3->env ); 1532 ast::OpenVarSet open{ r1->open }; 1533 mergeOpenVars( open, r2->open ); 1534 mergeOpenVars( open, r3->open ); 1535 ast::AssertionSet need; 1536 mergeAssertionSet( need, r1->need ); 1537 mergeAssertionSet( need, r2->need ); 1538 mergeAssertionSet( need, r3->need ); 1539 ast::AssertionSet have; 1540 1541 // unify true and false results, then infer parameters to produce new 1542 // candidates 1543 ast::ptr< ast::Type > common; 1544 if ( 1545 unify( 1546 r2->expr->result, r3->expr->result, env, need, have, open, 1547 common ) 1548 ) { 1549 // generate typed expression 1550 ast::ConditionalExpr * newExpr = new ast::ConditionalExpr{ 1551 conditionalExpr->location, r1->expr, r2->expr, r3->expr }; 1552 newExpr->result = common ? common : r2->expr->result; 1553 // convert both options to result type 1554 Cost cost = r1->cost + r2->cost + r3->cost; 1555 newExpr->arg2 = computeExpressionConversionCost( 1556 newExpr->arg2, newExpr->result, symtab, env, cost ); 1557 newExpr->arg3 = computeExpressionConversionCost( 1558 newExpr->arg3, newExpr->result, symtab, env, cost ); 1559 // output candidate 1560 CandidateRef newCand = std::make_shared<Candidate>( 1561 newExpr, std::move( env ), std::move( open ), std::move( need ), cost ); 1562 inferParameters( newCand, candidates ); 1563 } 1564 } 1565 } 1566 } 1567 } 1568 1569 void Finder::postvisit( const ast::CommaExpr * commaExpr ) { 1570 ast::TypeEnvironment env{ tenv }; 1571 ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, context, env ); 1572 1573 CandidateFinder finder2( context, env ); 1574 finder2.find( commaExpr->arg2, ResolvMode::withAdjustment() ); 1575 1576 for ( const CandidateRef & r2 : finder2.candidates ) { 1577 addCandidate( *r2, new ast::CommaExpr{ commaExpr->location, arg1, r2->expr } ); 1578 } 1579 } 1580 1581 void Finder::postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr ) { 1582 addCandidate( ctorExpr, tenv ); 1583 } 1584 1585 void Finder::postvisit( const ast::ConstructorExpr * ctorExpr ) { 1586 CandidateFinder finder( context, tenv ); 1587 finder.allowVoid = true; 1588 finder.find( ctorExpr->callExpr, ResolvMode::withoutPrune() ); 1589 for ( CandidateRef & r : finder.candidates ) { 1590 addCandidate( *r, new ast::ConstructorExpr{ ctorExpr->location, r->expr } ); 1591 } 1592 } 1593 1594 void Finder::postvisit( const ast::RangeExpr * rangeExpr ) { 1595 // resolve low and high, accept candidates where low and high types unify 1596 CandidateFinder finder1( context, tenv ); 1597 finder1.find( rangeExpr->low, ResolvMode::withAdjustment() ); 1598 if ( finder1.candidates.empty() ) return; 1599 1600 CandidateFinder finder2( context, tenv ); 1601 finder2.find( rangeExpr->high, ResolvMode::withAdjustment() ); 1602 if ( finder2.candidates.empty() ) return; 1603 1604 reason.code = NoMatch; 1605 1606 for ( const CandidateRef & r1 : finder1.candidates ) { 1607 for ( const CandidateRef & r2 : finder2.candidates ) { 1608 ast::TypeEnvironment env{ r1->env }; 1609 env.simpleCombine( r2->env ); 1610 ast::OpenVarSet open{ r1->open }; 1611 mergeOpenVars( open, r2->open ); 1612 ast::AssertionSet need; 1613 mergeAssertionSet( need, r1->need ); 1614 mergeAssertionSet( need, r2->need ); 1615 ast::AssertionSet have; 1616 1617 ast::ptr< ast::Type > common; 1618 if ( 1619 unify( 1620 r1->expr->result, r2->expr->result, env, need, have, open, 1621 common ) 1622 ) { 1623 // generate new expression 1624 ast::RangeExpr * newExpr = 1625 new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr }; 1626 newExpr->result = common ? common : r1->expr->result; 1627 // add candidate 1628 CandidateRef newCand = std::make_shared<Candidate>( 1629 newExpr, std::move( env ), std::move( open ), std::move( need ), 1630 r1->cost + r2->cost ); 1631 inferParameters( newCand, candidates ); 1632 } 1633 } 1634 } 1635 } 1636 1637 void Finder::postvisit( const ast::UntypedTupleExpr * tupleExpr ) { 1638 std::vector< CandidateFinder > subCandidates = 1639 selfFinder.findSubExprs( tupleExpr->exprs ); 1640 std::vector< CandidateList > possibilities; 1641 combos( subCandidates.begin(), subCandidates.end(), back_inserter( possibilities ) ); 1642 1643 for ( const CandidateList & subs : possibilities ) { 1644 std::vector< ast::ptr< ast::Expr > > exprs; 1645 exprs.reserve( subs.size() ); 1646 for ( const CandidateRef & sub : subs ) { exprs.emplace_back( sub->expr ); } 1647 1648 ast::TypeEnvironment env; 1649 ast::OpenVarSet open; 1650 ast::AssertionSet need; 1651 for ( const CandidateRef & sub : subs ) { 1652 env.simpleCombine( sub->env ); 1653 mergeOpenVars( open, sub->open ); 1654 mergeAssertionSet( need, sub->need ); 1655 } 1656 1657 addCandidate( 1658 new ast::TupleExpr{ tupleExpr->location, std::move( exprs ) }, 1659 std::move( env ), std::move( open ), std::move( need ), sumCost( subs ) ); 1660 } 1661 } 1662 1663 void Finder::postvisit( const ast::TupleExpr * tupleExpr ) { 1664 addCandidate( tupleExpr, tenv ); 1665 } 1666 1667 void Finder::postvisit( const ast::TupleIndexExpr * tupleExpr ) { 1668 addCandidate( tupleExpr, tenv ); 1669 } 1670 1671 void Finder::postvisit( const ast::TupleAssignExpr * tupleExpr ) { 1672 addCandidate( tupleExpr, tenv ); 1673 } 1674 1675 void Finder::postvisit( const ast::UniqueExpr * unqExpr ) { 1676 CandidateFinder finder( context, tenv ); 1677 finder.find( unqExpr->expr, ResolvMode::withAdjustment() ); 1678 for ( CandidateRef & r : finder.candidates ) { 1679 // ensure that the the id is passed on so that the expressions are "linked" 1680 addCandidate( *r, new ast::UniqueExpr{ unqExpr->location, r->expr, unqExpr->id } ); 1681 } 1682 } 1683 1684 void Finder::postvisit( const ast::StmtExpr * stmtExpr ) { 1685 addCandidate( resolveStmtExpr( stmtExpr, context ), tenv ); 1686 } 1687 1688 void Finder::postvisit( const ast::UntypedInitExpr * initExpr ) { 1689 // handle each option like a cast 1690 CandidateList matches; 1691 PRINT( 1692 std::cerr << "untyped init expr: " << initExpr << std::endl; 1693 ) 1694 // O(n^2) checks of d-types with e-types 1695 for ( const ast::InitAlternative & initAlt : initExpr->initAlts ) { 1696 // calculate target type 1697 const ast::Type * toType = resolveTypeof( initAlt.type, context ); 1698 toType = adjustExprType( toType, tenv, symtab ); 1699 // The call to find must occur inside this loop, otherwise polymorphic return 1700 // types are not bound to the initialization type, since return type variables are 1701 // only open for the duration of resolving the UntypedExpr. 1702 CandidateFinder finder( context, tenv, toType ); 1703 finder.find( initExpr->expr, ResolvMode::withAdjustment() ); 1704 1705 Cost minExprCost = Cost::infinity; 1706 Cost minCastCost = Cost::infinity; 1707 for ( CandidateRef & cand : finder.candidates ) { 1708 if (reason.code == NotFound) reason.code = NoMatch; 1709 1710 ast::TypeEnvironment env{ cand->env }; 1711 ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have; 1712 ast::OpenVarSet open{ cand->open }; 1713 1714 PRINT( 1715 std::cerr << " @ " << toType << " " << initAlt.designation << std::endl; 1716 ) 1717 1718 // It is possible that a cast can throw away some values in a multiply-valued 1719 // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of 1720 // the subexpression results that are cast directly. The candidate is invalid 1721 // if it has fewer results than there are types to cast to. 1722 int discardedValues = cand->expr->result->size() - toType->size(); 1723 if ( discardedValues < 0 ) continue; 1724 1725 // unification run for side-effects 1726 bool canUnify = unify( toType, cand->expr->result, env, need, have, open ); 1727 (void) canUnify; 1728 Cost thisCost = computeConversionCost( cand->expr->result, toType, cand->expr->get_lvalue(), 1729 symtab, env ); 1730 PRINT( 1731 Cost legacyCost = castCost( cand->expr->result, toType, cand->expr->get_lvalue(), 1732 symtab, env ); 1733 std::cerr << "Considering initialization:"; 1734 std::cerr << std::endl << " FROM: " << cand->expr->result << std::endl; 1735 std::cerr << std::endl << " TO: " << toType << std::endl; 1736 std::cerr << std::endl << " Unification " << (canUnify ? "succeeded" : "failed"); 1737 std::cerr << std::endl << " Legacy cost " << legacyCost; 1738 std::cerr << std::endl << " New cost " << thisCost; 1739 std::cerr << std::endl; 1740 ) 1741 if ( thisCost != Cost::infinity ) { 1742 // count one safe conversion for each value that is thrown away 1743 thisCost.incSafe( discardedValues ); 1744 if ( cand->cost < minExprCost || ( cand->cost == minExprCost && thisCost < minCastCost ) ) { 1745 minExprCost = cand->cost; 1746 minCastCost = thisCost; 1747 matches.clear(); 1748 } 1749 // ambiguous case, still output candidates to print in error message 1750 if ( cand->cost == minExprCost && thisCost == minCastCost ) { 1751 CandidateRef newCand = std::make_shared<Candidate>( 1752 new ast::InitExpr{ 1753 initExpr->location, 1754 restructureCast( cand->expr, toType ), 1755 initAlt.designation }, 1756 std::move(env), std::move( open ), std::move( need ), cand->cost + thisCost ); 1757 // currently assertions are always resolved immediately so this should have no effect. 1758 // if this somehow changes in the future (e.g. delayed by indeterminate return type) 1759 // we may need to revisit the logic. 1760 inferParameters( newCand, matches ); 1761 } 1762 } 1763 } 1764 } 1765 1766 // select first on argument cost, then conversion cost 1767 // CandidateList minArgCost = findMinCost( matches ); 1768 // promoteCvtCost( minArgCost ); 1769 // candidates = findMinCost( minArgCost ); 1770 candidates = std::move(matches); 1771 } 1772 1773 // size_t Finder::traceId = Stats::Heap::new_stacktrace_id("Finder"); 1774 /// Prunes a list of candidates down to those that have the minimum conversion cost for a given 1775 /// return type. Skips ambiguous candidates. 1776 1777 } // anonymous namespace 1778 1779 bool CandidateFinder::pruneCandidates( CandidateList & candidates, CandidateList & out, std::vector<std::string> & errors ) { 1780 struct PruneStruct { 1781 CandidateRef candidate; 1782 bool ambiguous; 1783 1784 PruneStruct() = default; 1785 PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {} 1786 }; 1787 1788 // find lowest-cost candidate for each type 1789 std::unordered_map< std::string, PruneStruct > selected; 1790 // attempt to skip satisfyAssertions on more expensive alternatives if better options have been found 1791 std::sort(candidates.begin(), candidates.end(), [](const CandidateRef & x, const CandidateRef & y){return x->cost < y->cost;}); 1792 for ( CandidateRef & candidate : candidates ) { 1793 std::string mangleName; 1794 { 1795 ast::ptr< ast::Type > newType = candidate->expr->result; 1796 assertf(candidate->expr->result, "Result of expression %p for candidate is null", candidate->expr.get()); 1797 candidate->env.apply( newType ); 1798 mangleName = Mangle::mangle( newType ); 1799 } 1800 1801 auto found = selected.find( mangleName ); 1802 if (found != selected.end() && found->second.candidate->cost < candidate->cost) { 1803 PRINT( 1804 std::cerr << "cost " << candidate->cost << " loses to " 1805 << found->second.candidate->cost << std::endl; 1806 ) 1807 continue; 1808 } 1809 1810 // xxx - when do satisfyAssertions produce more than 1 result? 1811 // this should only happen when initial result type contains 1812 // unbound type parameters, then it should never be pruned by 1813 // the previous step, since renameTyVars guarantees the mangled name 1814 // is unique. 1815 CandidateList satisfied; 1816 bool needRecomputeKey = false; 1817 if (candidate->need.empty()) { 1818 satisfied.emplace_back(candidate); 1819 } 1820 else { 1821 satisfyAssertions(candidate, context.symtab, satisfied, errors); 1822 needRecomputeKey = true; 1823 } 1824 1825 for (auto & newCand : satisfied) { 1826 // recomputes type key, if satisfyAssertions changed it 1827 if (needRecomputeKey) 1828 { 1829 ast::ptr< ast::Type > newType = newCand->expr->result; 1830 assertf(newCand->expr->result, "Result of expression %p for candidate is null", newCand->expr.get()); 1831 newCand->env.apply( newType ); 1832 mangleName = Mangle::mangle( newType ); 1833 } 1834 auto found = selected.find( mangleName ); 1835 if ( found != selected.end() ) { 1836 // tiebreaking by picking the lower cost on CURRENT expression 1837 // NOTE: this behavior is different from C semantics. 1838 // Specific remediations are performed for C operators at postvisit(UntypedExpr). 1839 // Further investigations may take place. 1840 if ( newCand->cost < found->second.candidate->cost 1841 || (newCand->cost == found->second.candidate->cost && newCand->cvtCost < found->second.candidate->cvtCost) ) { 1842 PRINT( 1843 std::cerr << "cost " << newCand->cost << " beats " 1844 << found->second.candidate->cost << std::endl; 1845 ) 1846 1847 found->second = PruneStruct{ newCand }; 1848 } else if ( newCand->cost == found->second.candidate->cost && newCand->cvtCost == found->second.candidate->cvtCost ) { 1849 // if one of the candidates contains a deleted identifier, can pick the other, 1850 // since deleted expressions should not be ambiguous if there is another option 1851 // that is at least as good 1852 if ( findDeletedExpr( newCand->expr ) ) { 1853 // do nothing 1854 PRINT( std::cerr << "candidate is deleted" << std::endl; ) 1855 } else if ( findDeletedExpr( found->second.candidate->expr ) ) { 1856 PRINT( std::cerr << "current is deleted" << std::endl; ) 1857 found->second = PruneStruct{ newCand }; 1858 } else { 1859 PRINT( std::cerr << "marking ambiguous" << std::endl; ) 1860 found->second.ambiguous = true; 1861 } 1862 } else { 1863 // xxx - can satisfyAssertions increase the cost? 1864 PRINT( 1865 std::cerr << "cost " << newCand->cost << " loses to " 1866 << found->second.candidate->cost << std::endl; 1867 ) 1868 } 1869 } else { 1870 selected.emplace_hint( found, mangleName, newCand ); 1871 } 1872 } 1873 } 1874 1875 // report unambiguous min-cost candidates 1876 // CandidateList out; 1877 for ( auto & target : selected ) { 1878 if ( target.second.ambiguous ) continue; 1879 1880 CandidateRef cand = target.second.candidate; 1881 1882 ast::ptr< ast::Type > newResult = cand->expr->result; 1883 cand->env.applyFree( newResult ); 1884 cand->expr = ast::mutate_field( 1885 cand->expr.get(), &ast::Expr::result, std::move( newResult ) ); 1886 1887 out.emplace_back( cand ); 1888 } 1889 // if everything is lost in satisfyAssertions, report the error 1890 return !selected.empty(); 1891 } 1892 1893 void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) { 1894 // Find alternatives for expression 1895 ast::Pass<Finder> finder{ *this }; 1896 expr->accept( finder ); 1897 1898 if ( mode.failFast && candidates.empty() ) { 1899 switch(finder.core.reason.code) { 1900 case Finder::NotFound: 1901 { SemanticError( expr, "No alternatives for expression " ); break; } 1902 case Finder::NoMatch: 1903 { SemanticError( expr, "Invalid application of existing declaration(s) in expression " ); break; } 1904 case Finder::ArgsToFew: 1905 case Finder::ArgsToMany: 1906 case Finder::RetsToFew: 1907 case Finder::RetsToMany: 1908 case Finder::NoReason: 1909 default: 1910 { SemanticError( expr->location, "No reasonable alternatives for expression : reasons unkown" ); } 1911 } 1912 } 1913 1914 /* 1915 if ( mode.satisfyAssns || mode.prune ) { 1916 // trim candidates to just those where the assertions are satisfiable 1917 // - necessary pre-requisite to pruning 1918 CandidateList satisfied; 1919 std::vector< std::string > errors; 1920 for ( CandidateRef & candidate : candidates ) { 1921 satisfyAssertions( candidate, localSyms, satisfied, errors ); 1922 } 1923 1924 // fail early if none such 1925 if ( mode.failFast && satisfied.empty() ) { 1926 std::ostringstream stream; 1927 stream << "No alternatives with satisfiable assertions for " << expr << "\n"; 1928 for ( const auto& err : errors ) { 1929 stream << err; 1930 } 1931 SemanticError( expr->location, stream.str() ); 1932 } 1933 1934 // reset candidates 1935 candidates = move( satisfied ); 1936 } 1937 */ 1938 1939 // optimization: don't prune for NameExpr since it never has cost 1940 if ( mode.prune && !dynamic_cast<const ast::NameExpr *>(expr) ) { 1941 // trim candidates to single best one 1942 PRINT( 1943 std::cerr << "alternatives before prune:" << std::endl; 1944 print( std::cerr, candidates ); 1945 ) 1946 1947 CandidateList pruned; 1948 std::vector<std::string> errors; 1949 bool found = pruneCandidates( candidates, pruned, errors ); 1950 1951 if ( mode.failFast && pruned.empty() ) { 1952 std::ostringstream stream; 1953 if (found) { 1954 CandidateList winners = findMinCost( candidates ); 1955 stream << "Cannot choose between " << winners.size() << " alternatives for " 1956 "expression\n"; 1957 ast::print( stream, expr ); 1958 stream << " Alternatives are:\n"; 1959 print( stream, winners, 1 ); 1960 SemanticError( expr->location, stream.str() ); 1961 } 1962 else { 1963 stream << "No alternatives with satisfiable assertions for " << expr << "\n"; 1964 for ( const auto& err : errors ) { 1965 stream << err; 1966 } 1967 SemanticError( expr->location, stream.str() ); 1968 } 1969 } 1970 1971 auto oldsize = candidates.size(); 1972 candidates = std::move( pruned ); 1973 1974 PRINT( 1975 std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl; 1976 ) 1977 PRINT( 1978 std::cerr << "there are " << candidates.size() << " alternatives after elimination" 1979 << std::endl; 1980 ) 1981 } 1982 1983 // adjust types after pruning so that types substituted by pruneAlternatives are correctly 1984 // adjusted 1985 if ( mode.adjust ) { 1986 for ( CandidateRef & r : candidates ) { 1987 r->expr = ast::mutate_field( 1988 r->expr.get(), &ast::Expr::result, 1989 adjustExprType( r->expr->result, r->env, context.symtab ) ); 1990 } 1991 } 1992 1993 // Central location to handle gcc extension keyword, etc. for all expressions 1994 for ( CandidateRef & r : candidates ) { 1995 if ( r->expr->extension != expr->extension ) { 1996 r->expr.get_and_mutate()->extension = expr->extension; 1997 } 1998 } 1999 } 2000 2001 std::vector< CandidateFinder > CandidateFinder::findSubExprs( 2002 const std::vector< ast::ptr< ast::Expr > > & xs 2003 ) { 2004 std::vector< CandidateFinder > out; 2005 2006 for ( const auto & x : xs ) { 2007 out.emplace_back( context, env ); 2008 out.back().find( x, ResolvMode::withAdjustment() ); 2009 2010 PRINT( 2011 std::cerr << "findSubExprs" << std::endl; 2012 print( std::cerr, out.back().candidates ); 2013 ) 2014 } 2015 2016 return out; 2017 } 2018 58 2019 const ast::Expr * referenceToRvalueConversion( const ast::Expr * expr, Cost & cost ) { 59 2020 if ( expr->result.as< ast::ReferenceType >() ) { … … 65 2026 return expr; 66 2027 } 67 68 /// Unique identifier for matching expression resolutions to their requesting expression69 UniqueId globalResnSlot = 0;70 2028 71 2029 Cost computeConversionCost( … … 94 2052 } 95 2053 96 namespace {97 /// First index is which argument, second is which alternative, third is which exploded element98 using ExplodedArgs_new = std::deque< std::vector< ExplodedArg > >;99 100 /// Returns a list of alternatives with the minimum cost in the given list101 CandidateList findMinCost( const CandidateList & candidates ) {102 CandidateList out;103 Cost minCost = Cost::infinity;104 for ( const CandidateRef & r : candidates ) {105 if ( r->cost < minCost ) {106 minCost = r->cost;107 out.clear();108 out.emplace_back( r );109 } else if ( r->cost == minCost ) {110 out.emplace_back( r );111 }112 }113 return out;114 }115 116 /// Computes conversion cost for a given expression to a given type117 const ast::Expr * computeExpressionConversionCost(118 const ast::Expr * arg, const ast::Type * paramType, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env, Cost & outCost119 ) {120 Cost convCost = computeConversionCost(121 arg->result, paramType, arg->get_lvalue(), symtab, env );122 outCost += convCost;123 124 // If there is a non-zero conversion cost, ignoring poly cost, then the expression requires125 // conversion. Ignore poly cost for now, since this requires resolution of the cast to126 // infer parameters and this does not currently work for the reason stated below127 Cost tmpCost = convCost;128 tmpCost.incPoly( -tmpCost.get_polyCost() );129 if ( tmpCost != Cost::zero ) {130 ast::ptr< ast::Type > newType = paramType;131 env.apply( newType );132 return new ast::CastExpr{ arg, newType };133 134 // xxx - *should* be able to resolve this cast, but at the moment pointers are not135 // castable to zero_t, but are implicitly convertible. This is clearly inconsistent,136 // once this is fixed it should be possible to resolve the cast.137 // xxx - this isn't working, it appears because type1 (parameter) is seen as widenable,138 // but it shouldn't be because this makes the conversion from DT* to DT* since139 // commontype(zero_t, DT*) is DT*, rather than nothing140 141 // CandidateFinder finder{ symtab, env };142 // finder.find( arg, ResolvMode::withAdjustment() );143 // assertf( finder.candidates.size() > 0,144 // "Somehow castable expression failed to find alternatives." );145 // assertf( finder.candidates.size() == 1,146 // "Somehow got multiple alternatives for known cast expression." );147 // return finder.candidates.front()->expr;148 }149 150 return arg;151 }152 153 /// Computes conversion cost for a given candidate154 Cost computeApplicationConversionCost(155 CandidateRef cand, const ast::SymbolTable & symtab156 ) {157 auto appExpr = cand->expr.strict_as< ast::ApplicationExpr >();158 auto pointer = appExpr->func->result.strict_as< ast::PointerType >();159 auto function = pointer->base.strict_as< ast::FunctionType >();160 161 Cost convCost = Cost::zero;162 const auto & params = function->params;163 auto param = params.begin();164 auto & args = appExpr->args;165 166 for ( unsigned i = 0; i < args.size(); ++i ) {167 const ast::Type * argType = args[i]->result;168 PRINT(169 std::cerr << "arg expression:" << std::endl;170 ast::print( std::cerr, args[i], 2 );171 std::cerr << "--- results are" << std::endl;172 ast::print( std::cerr, argType, 2 );173 )174 175 if ( param == params.end() ) {176 if ( function->isVarArgs ) {177 convCost.incUnsafe();178 PRINT( std::cerr << "end of params with varargs function: inc unsafe: "179 << convCost << std::endl; ; )180 // convert reference-typed expressions into value-typed expressions181 cand->expr = ast::mutate_field_index(182 appExpr, &ast::ApplicationExpr::args, i,183 referenceToRvalueConversion( args[i], convCost ) );184 continue;185 } else return Cost::infinity;186 }187 188 if ( auto def = args[i].as< ast::DefaultArgExpr >() ) {189 // Default arguments should be free - don't include conversion cost.190 // Unwrap them here because they are not relevant to the rest of the system191 cand->expr = ast::mutate_field_index(192 appExpr, &ast::ApplicationExpr::args, i, def->expr );193 ++param;194 continue;195 }196 197 // mark conversion cost and also specialization cost of param type198 // const ast::Type * paramType = (*param)->get_type();199 cand->expr = ast::mutate_field_index(200 appExpr, &ast::ApplicationExpr::args, i,201 computeExpressionConversionCost(202 args[i], *param, symtab, cand->env, convCost ) );203 convCost.decSpec( specCost( *param ) );204 ++param; // can't be in for-loop update because of the continue205 }206 207 if ( param != params.end() ) return Cost::infinity;208 209 // specialization cost of return types can't be accounted for directly, it disables210 // otherwise-identical calls, like this example based on auto-newline in the I/O lib:211 //212 // forall(otype OS) {213 // void ?|?(OS&, int); // with newline214 // OS& ?|?(OS&, int); // no newline, always chosen due to more specialization215 // }216 217 // mark type variable and specialization cost of forall clause218 convCost.incVar( function->forall.size() );219 convCost.decSpec( function->assertions.size() );220 221 return convCost;222 }223 224 void makeUnifiableVars(225 const ast::FunctionType * type, ast::OpenVarSet & unifiableVars,226 ast::AssertionSet & need227 ) {228 for ( auto & tyvar : type->forall ) {229 unifiableVars[ *tyvar ] = ast::TypeData{ tyvar->base };230 }231 for ( auto & assn : type->assertions ) {232 need[ assn ].isUsed = true;233 }234 }235 236 /// Gets a default value from an initializer, nullptr if not present237 const ast::ConstantExpr * getDefaultValue( const ast::Init * init ) {238 if ( auto si = dynamic_cast< const ast::SingleInit * >( init ) ) {239 if ( auto ce = si->value.as< ast::CastExpr >() ) {240 return ce->arg.as< ast::ConstantExpr >();241 } else {242 return si->value.as< ast::ConstantExpr >();243 }244 }245 return nullptr;246 }247 248 /// State to iteratively build a match of parameter expressions to arguments249 struct ArgPack {250 std::size_t parent; ///< Index of parent pack251 ast::ptr< ast::Expr > expr; ///< The argument stored here252 Cost cost; ///< The cost of this argument253 ast::TypeEnvironment env; ///< Environment for this pack254 ast::AssertionSet need; ///< Assertions outstanding for this pack255 ast::AssertionSet have; ///< Assertions found for this pack256 ast::OpenVarSet open; ///< Open variables for this pack257 unsigned nextArg; ///< Index of next argument in arguments list258 unsigned tupleStart; ///< Number of tuples that start at this index259 unsigned nextExpl; ///< Index of next exploded element260 unsigned explAlt; ///< Index of alternative for nextExpl > 0261 262 ArgPack()263 : parent( 0 ), expr(), cost( Cost::zero ), env(), need(), have(), open(), nextArg( 0 ),264 tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {}265 266 ArgPack(267 const ast::TypeEnvironment & env, const ast::AssertionSet & need,268 const ast::AssertionSet & have, const ast::OpenVarSet & open )269 : parent( 0 ), expr(), cost( Cost::zero ), env( env ), need( need ), have( have ),270 open( open ), nextArg( 0 ), tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {}271 272 ArgPack(273 std::size_t parent, const ast::Expr * expr, ast::TypeEnvironment && env,274 ast::AssertionSet && need, ast::AssertionSet && have, ast::OpenVarSet && open,275 unsigned nextArg, unsigned tupleStart = 0, Cost cost = Cost::zero,276 unsigned nextExpl = 0, unsigned explAlt = 0 )277 : parent(parent), expr( expr ), cost( cost ), env( std::move( env ) ), need( std::move( need ) ),278 have( std::move( have ) ), open( std::move( open ) ), nextArg( nextArg ), tupleStart( tupleStart ),279 nextExpl( nextExpl ), explAlt( explAlt ) {}280 281 ArgPack(282 const ArgPack & o, ast::TypeEnvironment && env, ast::AssertionSet && need,283 ast::AssertionSet && have, ast::OpenVarSet && open, unsigned nextArg, Cost added )284 : parent( o.parent ), expr( o.expr ), cost( o.cost + added ), env( std::move( env ) ),285 need( std::move( need ) ), have( std::move( have ) ), open( std::move( open ) ), nextArg( nextArg ),286 tupleStart( o.tupleStart ), nextExpl( 0 ), explAlt( 0 ) {}287 288 /// true if this pack is in the middle of an exploded argument289 bool hasExpl() const { return nextExpl > 0; }290 291 /// Gets the list of exploded candidates for this pack292 const ExplodedArg & getExpl( const ExplodedArgs_new & args ) const {293 return args[ nextArg-1 ][ explAlt ];294 }295 296 /// Ends a tuple expression, consolidating the appropriate args297 void endTuple( const std::vector< ArgPack > & packs ) {298 // add all expressions in tuple to list, summing cost299 std::deque< const ast::Expr * > exprs;300 const ArgPack * pack = this;301 if ( expr ) { exprs.emplace_front( expr ); }302 while ( pack->tupleStart == 0 ) {303 pack = &packs[pack->parent];304 exprs.emplace_front( pack->expr );305 cost += pack->cost;306 }307 // reset pack to appropriate tuple308 std::vector< ast::ptr< ast::Expr > > exprv( exprs.begin(), exprs.end() );309 expr = new ast::TupleExpr{ expr->location, std::move( exprv ) };310 tupleStart = pack->tupleStart - 1;311 parent = pack->parent;312 }313 };314 315 /// Instantiates an argument to match a parameter, returns false if no matching results left316 bool instantiateArgument(317 const CodeLocation & location,318 const ast::Type * paramType, const ast::Init * init, const ExplodedArgs_new & args,319 std::vector< ArgPack > & results, std::size_t & genStart, const ast::SymbolTable & symtab,320 unsigned nTuples = 0321 ) {322 if ( auto tupleType = dynamic_cast< const ast::TupleType * >( paramType ) ) {323 // paramType is a TupleType -- group args into a TupleExpr324 ++nTuples;325 for ( const ast::Type * type : *tupleType ) {326 // xxx - dropping initializer changes behaviour from previous, but seems correct327 // ^^^ need to handle the case where a tuple has a default argument328 if ( ! instantiateArgument( location,329 type, nullptr, args, results, genStart, symtab, nTuples ) ) return false;330 nTuples = 0;331 }332 // re-constitute tuples for final generation333 for ( auto i = genStart; i < results.size(); ++i ) {334 results[i].endTuple( results );335 }336 return true;337 } else if ( const ast::TypeInstType * ttype = Tuples::isTtype( paramType ) ) {338 // paramType is a ttype, consumes all remaining arguments339 340 // completed tuples; will be spliced to end of results to finish341 std::vector< ArgPack > finalResults{};342 343 // iterate until all results completed344 std::size_t genEnd;345 ++nTuples;346 do {347 genEnd = results.size();348 349 // add another argument to results350 for ( std::size_t i = genStart; i < genEnd; ++i ) {351 unsigned nextArg = results[i].nextArg;352 353 // use next element of exploded tuple if present354 if ( results[i].hasExpl() ) {355 const ExplodedArg & expl = results[i].getExpl( args );356 357 unsigned nextExpl = results[i].nextExpl + 1;358 if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }359 360 results.emplace_back(361 i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ),362 copy( results[i].need ), copy( results[i].have ),363 copy( results[i].open ), nextArg, nTuples, Cost::zero, nextExpl,364 results[i].explAlt );365 366 continue;367 }368 369 // finish result when out of arguments370 if ( nextArg >= args.size() ) {371 ArgPack newResult{372 results[i].env, results[i].need, results[i].have, results[i].open };373 newResult.nextArg = nextArg;374 const ast::Type * argType = nullptr;375 376 if ( nTuples > 0 || ! results[i].expr ) {377 // first iteration or no expression to clone,378 // push empty tuple expression379 newResult.parent = i;380 newResult.expr = new ast::TupleExpr( location, {} );381 argType = newResult.expr->result;382 } else {383 // clone result to collect tuple384 newResult.parent = results[i].parent;385 newResult.cost = results[i].cost;386 newResult.tupleStart = results[i].tupleStart;387 newResult.expr = results[i].expr;388 argType = newResult.expr->result;389 390 if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {391 // the case where a ttype value is passed directly is special,392 // e.g. for argument forwarding purposes393 // xxx - what if passing multiple arguments, last of which is394 // ttype?395 // xxx - what would happen if unify was changed so that unifying396 // tuple397 // types flattened both before unifying lists? then pass in398 // TupleType (ttype) below.399 --newResult.tupleStart;400 } else {401 // collapse leftover arguments into tuple402 newResult.endTuple( results );403 argType = newResult.expr->result;404 }405 }406 407 // check unification for ttype before adding to final408 if (409 unify(410 ttype, argType, newResult.env, newResult.need, newResult.have,411 newResult.open )412 ) {413 finalResults.emplace_back( std::move( newResult ) );414 }415 416 continue;417 }418 419 // add each possible next argument420 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {421 const ExplodedArg & expl = args[nextArg][j];422 423 // fresh copies of parent parameters for this iteration424 ast::TypeEnvironment env = results[i].env;425 ast::OpenVarSet open = results[i].open;426 427 env.addActual( expl.env, open );428 429 // skip empty tuple arguments by (nearly) cloning parent into next gen430 if ( expl.exprs.empty() ) {431 results.emplace_back(432 results[i], std::move( env ), copy( results[i].need ),433 copy( results[i].have ), std::move( open ), nextArg + 1, expl.cost );434 435 continue;436 }437 438 // add new result439 results.emplace_back(440 i, expl.exprs.front(), std::move( env ), copy( results[i].need ),441 copy( results[i].have ), std::move( open ), nextArg + 1, nTuples,442 expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );443 }444 }445 446 // reset for next round447 genStart = genEnd;448 nTuples = 0;449 } while ( genEnd != results.size() );450 451 // splice final results onto results452 for ( std::size_t i = 0; i < finalResults.size(); ++i ) {453 results.emplace_back( std::move( finalResults[i] ) );454 }455 return ! finalResults.empty();456 }457 458 // iterate each current subresult459 std::size_t genEnd = results.size();460 for ( std::size_t i = genStart; i < genEnd; ++i ) {461 unsigned nextArg = results[i].nextArg;462 463 // use remainder of exploded tuple if present464 if ( results[i].hasExpl() ) {465 const ExplodedArg & expl = results[i].getExpl( args );466 const ast::Expr * expr = expl.exprs[ results[i].nextExpl ];467 468 ast::TypeEnvironment env = results[i].env;469 ast::AssertionSet need = results[i].need, have = results[i].have;470 ast::OpenVarSet open = results[i].open;471 472 const ast::Type * argType = expr->result;473 474 PRINT(475 std::cerr << "param type is ";476 ast::print( std::cerr, paramType );477 std::cerr << std::endl << "arg type is ";478 ast::print( std::cerr, argType );479 std::cerr << std::endl;480 )481 482 if ( unify( paramType, argType, env, need, have, open ) ) {483 unsigned nextExpl = results[i].nextExpl + 1;484 if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }485 486 results.emplace_back(487 i, expr, std::move( env ), std::move( need ), std::move( have ), std::move( open ), nextArg,488 nTuples, Cost::zero, nextExpl, results[i].explAlt );489 }490 491 continue;492 }493 494 // use default initializers if out of arguments495 if ( nextArg >= args.size() ) {496 if ( const ast::ConstantExpr * cnst = getDefaultValue( init ) ) {497 ast::TypeEnvironment env = results[i].env;498 ast::AssertionSet need = results[i].need, have = results[i].have;499 ast::OpenVarSet open = results[i].open;500 501 if ( unify( paramType, cnst->result, env, need, have, open ) ) {502 results.emplace_back(503 i, new ast::DefaultArgExpr{ cnst->location, cnst }, std::move( env ),504 std::move( need ), std::move( have ), std::move( open ), nextArg, nTuples );505 }506 }507 508 continue;509 }510 511 // Check each possible next argument512 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {513 const ExplodedArg & expl = args[nextArg][j];514 515 // fresh copies of parent parameters for this iteration516 ast::TypeEnvironment env = results[i].env;517 ast::AssertionSet need = results[i].need, have = results[i].have;518 ast::OpenVarSet open = results[i].open;519 520 env.addActual( expl.env, open );521 522 // skip empty tuple arguments by (nearly) cloning parent into next gen523 if ( expl.exprs.empty() ) {524 results.emplace_back(525 results[i], std::move( env ), std::move( need ), std::move( have ), std::move( open ),526 nextArg + 1, expl.cost );527 528 continue;529 }530 531 // consider only first exploded arg532 const ast::Expr * expr = expl.exprs.front();533 const ast::Type * argType = expr->result;534 535 PRINT(536 std::cerr << "param type is ";537 ast::print( std::cerr, paramType );538 std::cerr << std::endl << "arg type is ";539 ast::print( std::cerr, argType );540 std::cerr << std::endl;541 )542 543 // attempt to unify types544 if ( unify( paramType, argType, env, need, have, open ) ) {545 // add new result546 results.emplace_back(547 i, expr, std::move( env ), std::move( need ), std::move( have ), std::move( open ),548 nextArg + 1, nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );549 }550 }551 }552 553 // reset for next parameter554 genStart = genEnd;555 556 return genEnd != results.size(); // were any new results added?557 }558 559 /// Generate a cast expression from `arg` to `toType`560 const ast::Expr * restructureCast(561 ast::ptr< ast::Expr > & arg, const ast::Type * toType, ast::GeneratedFlag isGenerated = ast::GeneratedCast562 ) {563 if (564 arg->result->size() > 1565 && ! toType->isVoid()566 && ! dynamic_cast< const ast::ReferenceType * >( toType )567 ) {568 // Argument is a tuple and the target type is neither void nor a reference. Cast each569 // member of the tuple to its corresponding target type, producing the tuple of those570 // cast expressions. If there are more components of the tuple than components in the571 // target type, then excess components do not come out in the result expression (but572 // UniqueExpr ensures that the side effects will still be produced)573 if ( Tuples::maybeImpureIgnoreUnique( arg ) ) {574 // expressions which may contain side effects require a single unique instance of575 // the expression576 arg = new ast::UniqueExpr{ arg->location, arg };577 }578 std::vector< ast::ptr< ast::Expr > > components;579 for ( unsigned i = 0; i < toType->size(); ++i ) {580 // cast each component581 ast::ptr< ast::Expr > idx = new ast::TupleIndexExpr{ arg->location, arg, i };582 components.emplace_back(583 restructureCast( idx, toType->getComponent( i ), isGenerated ) );584 }585 return new ast::TupleExpr{ arg->location, std::move( components ) };586 } else {587 // handle normally588 return new ast::CastExpr{ arg->location, arg, toType, isGenerated };589 }590 }591 592 /// Gets the name from an untyped member expression (must be NameExpr)593 const std::string & getMemberName( const ast::UntypedMemberExpr * memberExpr ) {594 if ( memberExpr->member.as< ast::ConstantExpr >() ) {595 SemanticError( memberExpr, "Indexed access to struct fields unsupported: " );596 }597 598 return memberExpr->member.strict_as< ast::NameExpr >()->name;599 }600 601 /// Actually visits expressions to find their candidate interpretations602 class Finder final : public ast::WithShortCircuiting {603 const ResolveContext & context;604 const ast::SymbolTable & symtab;605 public:606 // static size_t traceId;607 CandidateFinder & selfFinder;608 CandidateList & candidates;609 const ast::TypeEnvironment & tenv;610 ast::ptr< ast::Type > & targetType;611 612 enum Errors {613 NotFound,614 NoMatch,615 ArgsToFew,616 ArgsToMany,617 RetsToFew,618 RetsToMany,619 NoReason620 };621 622 struct {623 Errors code = NotFound;624 } reason;625 626 Finder( CandidateFinder & f )627 : context( f.context ), symtab( context.symtab ), selfFinder( f ),628 candidates( f.candidates ), tenv( f.env ), targetType( f.targetType ) {}629 630 void previsit( const ast::Node * ) { visit_children = false; }631 632 /// Convenience to add candidate to list633 template<typename... Args>634 void addCandidate( Args &&... args ) {635 candidates.emplace_back( new Candidate{ std::forward<Args>( args )... } );636 reason.code = NoReason;637 }638 639 void postvisit( const ast::ApplicationExpr * applicationExpr ) {640 addCandidate( applicationExpr, tenv );641 }642 643 /// Set up candidate assertions for inference644 void inferParameters( CandidateRef & newCand, CandidateList & out ) {645 // Set need bindings for any unbound assertions646 UniqueId crntResnSlot = 0; // matching ID for this expression's assertions647 for ( auto & assn : newCand->need ) {648 // skip already-matched assertions649 if ( assn.second.resnSlot != 0 ) continue;650 // assign slot for expression if needed651 if ( crntResnSlot == 0 ) { crntResnSlot = ++globalResnSlot; }652 // fix slot to assertion653 assn.second.resnSlot = crntResnSlot;654 }655 // pair slot to expression656 if ( crntResnSlot != 0 ) {657 newCand->expr.get_and_mutate()->inferred.resnSlots().emplace_back( crntResnSlot );658 }659 660 // add to output list; assertion satisfaction will occur later661 out.emplace_back( newCand );662 }663 664 /// Completes a function candidate with arguments located665 void validateFunctionCandidate(666 const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results,667 CandidateList & out668 ) {669 ast::ApplicationExpr * appExpr =670 new ast::ApplicationExpr{ func->expr->location, func->expr };671 // sum cost and accumulate arguments672 std::deque< const ast::Expr * > args;673 Cost cost = func->cost;674 const ArgPack * pack = &result;675 while ( pack->expr ) {676 args.emplace_front( pack->expr );677 cost += pack->cost;678 pack = &results[pack->parent];679 }680 std::vector< ast::ptr< ast::Expr > > vargs( args.begin(), args.end() );681 appExpr->args = std::move( vargs );682 // build and validate new candidate683 auto newCand =684 std::make_shared<Candidate>( appExpr, result.env, result.open, result.need, cost );685 PRINT(686 std::cerr << "instantiate function success: " << appExpr << std::endl;687 std::cerr << "need assertions:" << std::endl;688 ast::print( std::cerr, result.need, 2 );689 )690 inferParameters( newCand, out );691 }692 693 /// Builds a list of candidates for a function, storing them in out694 void makeFunctionCandidates(695 const CodeLocation & location,696 const CandidateRef & func, const ast::FunctionType * funcType,697 const ExplodedArgs_new & args, CandidateList & out698 ) {699 ast::OpenVarSet funcOpen;700 ast::AssertionSet funcNeed, funcHave;701 ast::TypeEnvironment funcEnv{ func->env };702 makeUnifiableVars( funcType, funcOpen, funcNeed );703 // add all type variables as open variables now so that those not used in the704 // parameter list are still considered open705 funcEnv.add( funcType->forall );706 707 if ( targetType && ! targetType->isVoid() && ! funcType->returns.empty() ) {708 // attempt to narrow based on expected target type709 const ast::Type * returnType = funcType->returns.front();710 if ( selfFinder.strictMode ) {711 if ( ! unifyExact(712 returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen, noWiden() ) // xxx - is no widening correct?713 ) {714 // unification failed, do not pursue this candidate715 return;716 }717 }718 else {719 if ( ! unify(720 returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen )721 ) {722 // unification failed, do not pursue this candidate723 return;724 }725 }726 }727 728 // iteratively build matches, one parameter at a time729 std::vector< ArgPack > results;730 results.emplace_back( funcEnv, funcNeed, funcHave, funcOpen );731 std::size_t genStart = 0;732 733 // xxx - how to handle default arg after change to ftype representation?734 if (const ast::VariableExpr * varExpr = func->expr.as<ast::VariableExpr>()) {735 if (const ast::FunctionDecl * funcDecl = varExpr->var.as<ast::FunctionDecl>()) {736 // function may have default args only if directly calling by name737 // must use types on candidate however, due to RenameVars substitution738 auto nParams = funcType->params.size();739 740 for (size_t i=0; i<nParams; ++i) {741 auto obj = funcDecl->params[i].strict_as<ast::ObjectDecl>();742 if ( !instantiateArgument( location,743 funcType->params[i], obj->init, args, results, genStart, symtab)) return;744 }745 goto endMatch;746 }747 }748 for ( const auto & param : funcType->params ) {749 // Try adding the arguments corresponding to the current parameter to the existing750 // matches751 // no default args for indirect calls752 if ( !instantiateArgument( location,753 param, nullptr, args, results, genStart, symtab ) ) return;754 }755 756 endMatch:757 if ( funcType->isVarArgs ) {758 // append any unused arguments to vararg pack759 std::size_t genEnd;760 do {761 genEnd = results.size();762 763 // iterate results764 for ( std::size_t i = genStart; i < genEnd; ++i ) {765 unsigned nextArg = results[i].nextArg;766 767 // use remainder of exploded tuple if present768 if ( results[i].hasExpl() ) {769 const ExplodedArg & expl = results[i].getExpl( args );770 771 unsigned nextExpl = results[i].nextExpl + 1;772 if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }773 774 results.emplace_back(775 i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ),776 copy( results[i].need ), copy( results[i].have ),777 copy( results[i].open ), nextArg, 0, Cost::zero, nextExpl,778 results[i].explAlt );779 780 continue;781 }782 783 // finish result when out of arguments784 if ( nextArg >= args.size() ) {785 validateFunctionCandidate( func, results[i], results, out );786 787 continue;788 }789 790 // add each possible next argument791 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {792 const ExplodedArg & expl = args[nextArg][j];793 794 // fresh copies of parent parameters for this iteration795 ast::TypeEnvironment env = results[i].env;796 ast::OpenVarSet open = results[i].open;797 798 env.addActual( expl.env, open );799 800 // skip empty tuple arguments by (nearly) cloning parent into next gen801 if ( expl.exprs.empty() ) {802 results.emplace_back(803 results[i], std::move( env ), copy( results[i].need ),804 copy( results[i].have ), std::move( open ), nextArg + 1,805 expl.cost );806 807 continue;808 }809 810 // add new result811 results.emplace_back(812 i, expl.exprs.front(), std::move( env ), copy( results[i].need ),813 copy( results[i].have ), std::move( open ), nextArg + 1, 0, expl.cost,814 expl.exprs.size() == 1 ? 0 : 1, j );815 }816 }817 818 genStart = genEnd;819 } while( genEnd != results.size() );820 } else {821 // filter out the results that don't use all the arguments822 for ( std::size_t i = genStart; i < results.size(); ++i ) {823 ArgPack & result = results[i];824 if ( ! result.hasExpl() && result.nextArg >= args.size() ) {825 validateFunctionCandidate( func, result, results, out );826 }827 }828 }829 }830 831 /// Adds implicit struct-conversions to the alternative list832 void addAnonConversions( const CandidateRef & cand ) {833 // adds anonymous member interpretations whenever an aggregate value type is seen.834 // it's okay for the aggregate expression to have reference type -- cast it to the835 // base type to treat the aggregate as the referenced value836 ast::ptr< ast::Expr > aggrExpr( cand->expr );837 ast::ptr< ast::Type > & aggrType = aggrExpr.get_and_mutate()->result;838 cand->env.apply( aggrType );839 840 if ( aggrType.as< ast::ReferenceType >() ) {841 aggrExpr = new ast::CastExpr{ aggrExpr, aggrType->stripReferences() };842 }843 844 if ( auto structInst = aggrExpr->result.as< ast::StructInstType >() ) {845 addAggMembers( structInst, aggrExpr, *cand, Cost::unsafe, "" );846 } else if ( auto unionInst = aggrExpr->result.as< ast::UnionInstType >() ) {847 addAggMembers( unionInst, aggrExpr, *cand, Cost::unsafe, "" );848 }849 }850 851 /// Adds aggregate member interpretations852 void addAggMembers(853 const ast::BaseInstType * aggrInst, const ast::Expr * expr,854 const Candidate & cand, const Cost & addedCost, const std::string & name855 ) {856 for ( const ast::Decl * decl : aggrInst->lookup( name ) ) {857 auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( decl );858 CandidateRef newCand = std::make_shared<Candidate>(859 cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost );860 // add anonymous member interpretations whenever an aggregate value type is seen861 // as a member expression862 addAnonConversions( newCand );863 candidates.emplace_back( std::move( newCand ) );864 }865 }866 867 /// Adds tuple member interpretations868 void addTupleMembers(869 const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand,870 const Cost & addedCost, const ast::Expr * member871 ) {872 if ( auto constantExpr = dynamic_cast< const ast::ConstantExpr * >( member ) ) {873 // get the value of the constant expression as an int, must be between 0 and the874 // length of the tuple to have meaning875 long long val = constantExpr->intValue();876 if ( val >= 0 && (unsigned long long)val < tupleType->size() ) {877 addCandidate(878 cand, new ast::TupleIndexExpr{ expr->location, expr, (unsigned)val },879 addedCost );880 }881 }882 }883 884 void postvisit( const ast::UntypedExpr * untypedExpr ) {885 std::vector< CandidateFinder > argCandidates =886 selfFinder.findSubExprs( untypedExpr->args );887 888 // take care of possible tuple assignments889 // if not tuple assignment, handled as normal function call890 Tuples::handleTupleAssignment( selfFinder, untypedExpr, argCandidates );891 892 CandidateFinder funcFinder( context, tenv );893 if (auto nameExpr = untypedExpr->func.as<ast::NameExpr>()) {894 auto kind = ast::SymbolTable::getSpecialFunctionKind(nameExpr->name);895 if (kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS) {896 assertf(!argCandidates.empty(), "special function call without argument");897 for (auto & firstArgCand: argCandidates[0]) {898 ast::ptr<ast::Type> argType = firstArgCand->expr->result;899 firstArgCand->env.apply(argType);900 // strip references901 // xxx - is this correct?902 while (argType.as<ast::ReferenceType>()) argType = argType.as<ast::ReferenceType>()->base;903 904 // convert 1-tuple to plain type905 if (auto tuple = argType.as<ast::TupleType>()) {906 if (tuple->size() == 1) {907 argType = tuple->types[0];908 }909 }910 911 // if argType is an unbound type parameter, all special functions need to be searched.912 if (isUnboundType(argType)) {913 funcFinder.otypeKeys.clear();914 break;915 }916 917 if (argType.as<ast::PointerType>()) funcFinder.otypeKeys.insert(Mangle::Encoding::pointer);918 // else if (const ast::EnumInstType * enumInst = argType.as<ast::EnumInstType>()) {919 // const ast::EnumDecl * enumDecl = enumInst->base; // Here920 // if ( const ast::Type* enumType = enumDecl->base ) {921 // // instance of enum (T) is a instance of type (T)922 // funcFinder.otypeKeys.insert(Mangle::mangle(enumType, Mangle::NoGenericParams | Mangle::Type));923 // } else {924 // // instance of an untyped enum is techically int925 // funcFinder.otypeKeys.insert(Mangle::mangle(enumDecl, Mangle::NoGenericParams | Mangle::Type));926 // }927 // }928 else funcFinder.otypeKeys.insert(Mangle::mangle(argType, Mangle::NoGenericParams | Mangle::Type));929 }930 }931 }932 // if candidates are already produced, do not fail933 // xxx - is it possible that handleTupleAssignment and main finder both produce candidates?934 // this means there exists ctor/assign functions with a tuple as first parameter.935 ResolvMode mode = {936 true, // adjust937 !untypedExpr->func.as<ast::NameExpr>(), // prune if not calling by name938 selfFinder.candidates.empty() // failfast if other options are not found939 };940 funcFinder.find( untypedExpr->func, mode );941 // short-circuit if no candidates942 // if ( funcFinder.candidates.empty() ) return;943 944 reason.code = NoMatch;945 946 // find function operators947 ast::ptr< ast::Expr > opExpr = new ast::NameExpr{ untypedExpr->location, "?()" }; // ??? why not ?{}948 CandidateFinder opFinder( context, tenv );949 // okay if there aren't any function operations950 opFinder.find( opExpr, ResolvMode::withoutFailFast() );951 PRINT(952 std::cerr << "known function ops:" << std::endl;953 print( std::cerr, opFinder.candidates, 1 );954 )955 956 // pre-explode arguments957 ExplodedArgs_new argExpansions;958 for ( const CandidateFinder & args : argCandidates ) {959 argExpansions.emplace_back();960 auto & argE = argExpansions.back();961 for ( const CandidateRef & arg : args ) { argE.emplace_back( *arg, symtab ); }962 }963 964 // Find function matches965 CandidateList found;966 SemanticErrorException errors;967 for ( CandidateRef & func : funcFinder ) {968 try {969 PRINT(970 std::cerr << "working on alternative:" << std::endl;971 print( std::cerr, *func, 2 );972 )973 974 // check if the type is a pointer to function975 const ast::Type * funcResult = func->expr->result->stripReferences();976 if ( auto pointer = dynamic_cast< const ast::PointerType * >( funcResult ) ) {977 if ( auto function = pointer->base.as< ast::FunctionType >() ) {978 // if (!selfFinder.allowVoid && function->returns.empty()) continue;979 CandidateRef newFunc{ new Candidate{ *func } };980 newFunc->expr =981 referenceToRvalueConversion( newFunc->expr, newFunc->cost );982 makeFunctionCandidates( untypedExpr->location,983 newFunc, function, argExpansions, found );984 }985 } else if (986 auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult )987 ) {988 if ( const ast::EqvClass * clz = func->env.lookup( *inst ) ) {989 if ( auto function = clz->bound.as< ast::FunctionType >() ) {990 CandidateRef newFunc( new Candidate( *func ) );991 newFunc->expr =992 referenceToRvalueConversion( newFunc->expr, newFunc->cost );993 makeFunctionCandidates( untypedExpr->location,994 newFunc, function, argExpansions, found );995 }996 }997 }998 } catch ( SemanticErrorException & e ) { errors.append( e ); }999 }1000 1001 // Find matches on function operators `?()`1002 if ( ! opFinder.candidates.empty() ) {1003 // add exploded function alternatives to front of argument list1004 std::vector< ExplodedArg > funcE;1005 funcE.reserve( funcFinder.candidates.size() );1006 for ( const CandidateRef & func : funcFinder ) {1007 funcE.emplace_back( *func, symtab );1008 }1009 argExpansions.emplace_front( std::move( funcE ) );1010 1011 for ( const CandidateRef & op : opFinder ) {1012 try {1013 // check if type is pointer-to-function1014 const ast::Type * opResult = op->expr->result->stripReferences();1015 if ( auto pointer = dynamic_cast< const ast::PointerType * >( opResult ) ) {1016 if ( auto function = pointer->base.as< ast::FunctionType >() ) {1017 CandidateRef newOp{ new Candidate{ *op} };1018 newOp->expr =1019 referenceToRvalueConversion( newOp->expr, newOp->cost );1020 makeFunctionCandidates( untypedExpr->location,1021 newOp, function, argExpansions, found );1022 }1023 }1024 } catch ( SemanticErrorException & e ) { errors.append( e ); }1025 }1026 }1027 1028 // Implement SFINAE; resolution errors are only errors if there aren't any non-error1029 // candidates1030 if ( found.empty() && ! errors.isEmpty() ) { throw errors; }1031 1032 // only keep the best matching intrinsic result to match C semantics (no unexpected narrowing/widening)1033 // TODO: keep one for each set of argument candidates?1034 Cost intrinsicCost = Cost::infinity;1035 CandidateList intrinsicResult;1036 1037 // Compute conversion costs1038 for ( CandidateRef & withFunc : found ) {1039 Cost cvtCost = computeApplicationConversionCost( withFunc, symtab );1040 1041 PRINT(1042 auto appExpr = withFunc->expr.strict_as< ast::ApplicationExpr >();1043 auto pointer = appExpr->func->result.strict_as< ast::PointerType >();1044 auto function = pointer->base.strict_as< ast::FunctionType >();1045 1046 std::cerr << "Case +++++++++++++ " << appExpr->func << std::endl;1047 std::cerr << "parameters are:" << std::endl;1048 ast::printAll( std::cerr, function->params, 2 );1049 std::cerr << "arguments are:" << std::endl;1050 ast::printAll( std::cerr, appExpr->args, 2 );1051 std::cerr << "bindings are:" << std::endl;1052 ast::print( std::cerr, withFunc->env, 2 );1053 std::cerr << "cost is: " << withFunc->cost << std::endl;1054 std::cerr << "cost of conversion is:" << cvtCost << std::endl;1055 )1056 1057 if ( cvtCost != Cost::infinity ) {1058 withFunc->cvtCost = cvtCost;1059 withFunc->cost += cvtCost;1060 auto func = withFunc->expr.strict_as<ast::ApplicationExpr>()->func.as<ast::VariableExpr>();1061 if (func && func->var->linkage == ast::Linkage::Intrinsic) {1062 if (withFunc->cost < intrinsicCost) {1063 intrinsicResult.clear();1064 intrinsicCost = withFunc->cost;1065 }1066 if (withFunc->cost == intrinsicCost) {1067 intrinsicResult.emplace_back(std::move(withFunc));1068 }1069 }1070 else {1071 candidates.emplace_back( std::move( withFunc ) );1072 }1073 }1074 }1075 spliceBegin( candidates, intrinsicResult );1076 found = std::move( candidates );1077 1078 // use a new list so that candidates are not examined by addAnonConversions twice1079 // CandidateList winners = findMinCost( found );1080 // promoteCvtCost( winners );1081 1082 // function may return a struct/union value, in which case we need to add candidates1083 // for implicit conversions to each of the anonymous members, which must happen after1084 // `findMinCost`, since anon conversions are never the cheapest1085 for ( const CandidateRef & c : found ) {1086 addAnonConversions( c );1087 }1088 // would this be too slow when we don't check cost anymore?1089 spliceBegin( candidates, found );1090 1091 if ( candidates.empty() && targetType && ! targetType->isVoid() && !selfFinder.strictMode ) {1092 // If resolution is unsuccessful with a target type, try again without, since it1093 // will sometimes succeed when it wouldn't with a target type binding.1094 // For example:1095 // forall( otype T ) T & ?[]( T *, ptrdiff_t );1096 // const char * x = "hello world";1097 // unsigned char ch = x[0];1098 // Fails with simple return type binding (xxx -- check this!) as follows:1099 // * T is bound to unsigned char1100 // * (x: const char *) is unified with unsigned char *, which fails1101 // xxx -- fix this better1102 targetType = nullptr;1103 postvisit( untypedExpr );1104 }1105 }1106 1107 /// true if expression is an lvalue1108 static bool isLvalue( const ast::Expr * x ) {1109 return x->result && ( x->get_lvalue() || x->result.as< ast::ReferenceType >() );1110 }1111 1112 void postvisit( const ast::AddressExpr * addressExpr ) {1113 CandidateFinder finder( context, tenv );1114 finder.find( addressExpr->arg );1115 1116 if( finder.candidates.empty() ) return;1117 1118 reason.code = NoMatch;1119 1120 for ( CandidateRef & r : finder.candidates ) {1121 if ( ! isLvalue( r->expr ) ) continue;1122 addCandidate( *r, new ast::AddressExpr{ addressExpr->location, r->expr } );1123 }1124 }1125 1126 void postvisit( const ast::LabelAddressExpr * labelExpr ) {1127 addCandidate( labelExpr, tenv );1128 }1129 1130 void postvisit( const ast::CastExpr * castExpr ) {1131 ast::ptr< ast::Type > toType = castExpr->result;1132 assert( toType );1133 toType = resolveTypeof( toType, context );1134 toType = adjustExprType( toType, tenv, symtab );1135 1136 CandidateFinder finder( context, tenv, toType );1137 if (toType->isVoid()) {1138 finder.allowVoid = true;1139 }1140 if ( castExpr->kind == ast::CastExpr::Return ) {1141 finder.strictMode = true;1142 finder.find( castExpr->arg, ResolvMode::withAdjustment() );1143 1144 // return casts are eliminated (merely selecting an overload, no actual operation)1145 candidates = std::move(finder.candidates);1146 }1147 finder.find( castExpr->arg, ResolvMode::withAdjustment() );1148 1149 if( !finder.candidates.empty() ) reason.code = NoMatch;1150 1151 CandidateList matches;1152 Cost minExprCost = Cost::infinity;1153 Cost minCastCost = Cost::infinity;1154 for ( CandidateRef & cand : finder.candidates ) {1155 ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have;1156 ast::OpenVarSet open( cand->open );1157 1158 cand->env.extractOpenVars( open );1159 1160 // It is possible that a cast can throw away some values in a multiply-valued1161 // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of the1162 // subexpression results that are cast directly. The candidate is invalid if it1163 // has fewer results than there are types to cast to.1164 int discardedValues = cand->expr->result->size() - toType->size();1165 if ( discardedValues < 0 ) continue;1166 1167 // unification run for side-effects1168 unify( toType, cand->expr->result, cand->env, need, have, open );1169 Cost thisCost =1170 (castExpr->isGenerated == ast::GeneratedFlag::GeneratedCast)1171 ? conversionCost( cand->expr->result, toType, cand->expr->get_lvalue(), symtab, cand->env )1172 : castCost( cand->expr->result, toType, cand->expr->get_lvalue(), symtab, cand->env );1173 1174 PRINT(1175 std::cerr << "working on cast with result: " << toType << std::endl;1176 std::cerr << "and expr type: " << cand->expr->result << std::endl;1177 std::cerr << "env: " << cand->env << std::endl;1178 )1179 if ( thisCost != Cost::infinity ) {1180 PRINT(1181 std::cerr << "has finite cost." << std::endl;1182 )1183 // count one safe conversion for each value that is thrown away1184 thisCost.incSafe( discardedValues );1185 // select first on argument cost, then conversion cost1186 if ( cand->cost < minExprCost || ( cand->cost == minExprCost && thisCost < minCastCost ) ) {1187 minExprCost = cand->cost;1188 minCastCost = thisCost;1189 matches.clear();1190 1191 1192 }1193 // ambiguous case, still output candidates to print in error message1194 if ( cand->cost == minExprCost && thisCost == minCastCost ) {1195 CandidateRef newCand = std::make_shared<Candidate>(1196 restructureCast( cand->expr, toType, castExpr->isGenerated ),1197 copy( cand->env ), std::move( open ), std::move( need ), cand->cost + thisCost);1198 // currently assertions are always resolved immediately so this should have no effect.1199 // if this somehow changes in the future (e.g. delayed by indeterminate return type)1200 // we may need to revisit the logic.1201 inferParameters( newCand, matches );1202 }1203 // else skip, better alternatives found1204 1205 }1206 }1207 candidates = std::move(matches);1208 1209 //CandidateList minArgCost = findMinCost( matches );1210 //promoteCvtCost( minArgCost );1211 //candidates = findMinCost( minArgCost );1212 }1213 1214 void postvisit( const ast::VirtualCastExpr * castExpr ) {1215 assertf( castExpr->result, "Implicit virtual cast targets not yet supported." );1216 CandidateFinder finder( context, tenv );1217 // don't prune here, all alternatives guaranteed to have same type1218 finder.find( castExpr->arg, ResolvMode::withoutPrune() );1219 for ( CandidateRef & r : finder.candidates ) {1220 addCandidate(1221 *r,1222 new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } );1223 }1224 }1225 1226 void postvisit( const ast::KeywordCastExpr * castExpr ) {1227 const auto & loc = castExpr->location;1228 assertf( castExpr->result, "Cast target should have been set in Validate." );1229 auto ref = castExpr->result.strict_as<ast::ReferenceType>();1230 auto inst = ref->base.strict_as<ast::StructInstType>();1231 auto target = inst->base.get();1232 1233 CandidateFinder finder( context, tenv );1234 1235 auto pick_alternatives = [target, this](CandidateList & found, bool expect_ref) {1236 for(auto & cand : found) {1237 const ast::Type * expr = cand->expr->result.get();1238 if(expect_ref) {1239 auto res = dynamic_cast<const ast::ReferenceType*>(expr);1240 if(!res) { continue; }1241 expr = res->base.get();1242 }1243 1244 if(auto insttype = dynamic_cast<const ast::TypeInstType*>(expr)) {1245 auto td = cand->env.lookup(*insttype);1246 if(!td) { continue; }1247 expr = td->bound.get();1248 }1249 1250 if(auto base = dynamic_cast<const ast::StructInstType*>(expr)) {1251 if(base->base == target) {1252 candidates.push_back( std::move(cand) );1253 reason.code = NoReason;1254 }1255 }1256 }1257 };1258 1259 try {1260 // Attempt 1 : turn (thread&)X into (thread$&)X.__thrd1261 // Clone is purely for memory management1262 std::unique_ptr<const ast::Expr> tech1 { new ast::UntypedMemberExpr(loc, new ast::NameExpr(loc, castExpr->concrete_target.field), castExpr->arg) };1263 1264 // don't prune here, since it's guaranteed all alternatives will have the same type1265 finder.find( tech1.get(), ResolvMode::withoutPrune() );1266 pick_alternatives(finder.candidates, false);1267 1268 return;1269 } catch(SemanticErrorException & ) {}1270 1271 // Fallback : turn (thread&)X into (thread$&)get_thread(X)1272 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 })) };1273 // don't prune here, since it's guaranteed all alternatives will have the same type1274 finder.find( fallback.get(), ResolvMode::withoutPrune() );1275 1276 pick_alternatives(finder.candidates, true);1277 1278 // Whatever happens here, we have no more fallbacks1279 }1280 1281 void postvisit( const ast::UntypedMemberExpr * memberExpr ) {1282 CandidateFinder aggFinder( context, tenv );1283 aggFinder.find( memberExpr->aggregate, ResolvMode::withAdjustment() );1284 for ( CandidateRef & agg : aggFinder.candidates ) {1285 // it's okay for the aggregate expression to have reference type -- cast it to the1286 // base type to treat the aggregate as the referenced value1287 Cost addedCost = Cost::zero;1288 agg->expr = referenceToRvalueConversion( agg->expr, addedCost );1289 1290 // find member of the given type1291 if ( auto structInst = agg->expr->result.as< ast::StructInstType >() ) {1292 addAggMembers(1293 structInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) );1294 } else if ( auto unionInst = agg->expr->result.as< ast::UnionInstType >() ) {1295 addAggMembers(1296 unionInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) );1297 } else if ( auto tupleType = agg->expr->result.as< ast::TupleType >() ) {1298 addTupleMembers( tupleType, agg->expr, *agg, addedCost, memberExpr->member );1299 }1300 }1301 }1302 1303 void postvisit( const ast::MemberExpr * memberExpr ) {1304 addCandidate( memberExpr, tenv );1305 }1306 1307 void postvisit( const ast::NameExpr * nameExpr ) {1308 std::vector< ast::SymbolTable::IdData > declList;1309 if (!selfFinder.otypeKeys.empty()) {1310 auto kind = ast::SymbolTable::getSpecialFunctionKind(nameExpr->name);1311 assertf(kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS, "special lookup with non-special target: %s", nameExpr->name.c_str());1312 1313 for (auto & otypeKey: selfFinder.otypeKeys) {1314 auto result = symtab.specialLookupId(kind, otypeKey);1315 declList.insert(declList.end(), std::make_move_iterator(result.begin()), std::make_move_iterator(result.end()));1316 }1317 }1318 else {1319 declList = symtab.lookupId( nameExpr->name );1320 }1321 PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; )1322 1323 if( declList.empty() ) return;1324 1325 reason.code = NoMatch;1326 1327 for ( auto & data : declList ) {1328 Cost cost = Cost::zero;1329 ast::Expr * newExpr = data.combine( nameExpr->location, cost );1330 1331 CandidateRef newCand = std::make_shared<Candidate>(1332 newExpr, copy( tenv ), ast::OpenVarSet{}, ast::AssertionSet{}, cost );1333 1334 if (newCand->expr->env) {1335 newCand->env.add(*newCand->expr->env);1336 auto mutExpr = newCand->expr.get_and_mutate();1337 mutExpr->env = nullptr;1338 newCand->expr = mutExpr;1339 }1340 1341 PRINT(1342 std::cerr << "decl is ";1343 ast::print( std::cerr, data.id );1344 std::cerr << std::endl;1345 std::cerr << "newExpr is ";1346 ast::print( std::cerr, newExpr );1347 std::cerr << std::endl;1348 )1349 newCand->expr = ast::mutate_field(1350 newCand->expr.get(), &ast::Expr::result,1351 renameTyVars( newCand->expr->result ) );1352 // add anonymous member interpretations whenever an aggregate value type is seen1353 // as a name expression1354 addAnonConversions( newCand );1355 candidates.emplace_back( std::move( newCand ) );1356 }1357 }1358 1359 void postvisit( const ast::VariableExpr * variableExpr ) {1360 // not sufficient to just pass `variableExpr` here, type might have changed since1361 // creation1362 addCandidate(1363 new ast::VariableExpr{ variableExpr->location, variableExpr->var }, tenv );1364 }1365 1366 void postvisit( const ast::ConstantExpr * constantExpr ) {1367 addCandidate( constantExpr, tenv );1368 }1369 1370 void postvisit( const ast::SizeofExpr * sizeofExpr ) {1371 if ( sizeofExpr->type ) {1372 addCandidate(1373 new ast::SizeofExpr{1374 sizeofExpr->location, resolveTypeof( sizeofExpr->type, context ) },1375 tenv );1376 } else {1377 // find all candidates for the argument to sizeof1378 CandidateFinder finder( context, tenv );1379 finder.find( sizeofExpr->expr );1380 // find the lowest-cost candidate, otherwise ambiguous1381 CandidateList winners = findMinCost( finder.candidates );1382 if ( winners.size() != 1 ) {1383 SemanticError(1384 sizeofExpr->expr.get(), "Ambiguous expression in sizeof operand: " );1385 }1386 // return the lowest-cost candidate1387 CandidateRef & choice = winners.front();1388 choice->expr = referenceToRvalueConversion( choice->expr, choice->cost );1389 choice->cost = Cost::zero;1390 addCandidate( *choice, new ast::SizeofExpr{ sizeofExpr->location, choice->expr } );1391 }1392 }1393 1394 void postvisit( const ast::AlignofExpr * alignofExpr ) {1395 if ( alignofExpr->type ) {1396 addCandidate(1397 new ast::AlignofExpr{1398 alignofExpr->location, resolveTypeof( alignofExpr->type, context ) },1399 tenv );1400 } else {1401 // find all candidates for the argument to alignof1402 CandidateFinder finder( context, tenv );1403 finder.find( alignofExpr->expr );1404 // find the lowest-cost candidate, otherwise ambiguous1405 CandidateList winners = findMinCost( finder.candidates );1406 if ( winners.size() != 1 ) {1407 SemanticError(1408 alignofExpr->expr.get(), "Ambiguous expression in alignof operand: " );1409 }1410 // return the lowest-cost candidate1411 CandidateRef & choice = winners.front();1412 choice->expr = referenceToRvalueConversion( choice->expr, choice->cost );1413 choice->cost = Cost::zero;1414 addCandidate(1415 *choice, new ast::AlignofExpr{ alignofExpr->location, choice->expr } );1416 }1417 }1418 1419 void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) {1420 const ast::BaseInstType * aggInst;1421 if (( aggInst = offsetofExpr->type.as< ast::StructInstType >() )) ;1422 else if (( aggInst = offsetofExpr->type.as< ast::UnionInstType >() )) ;1423 else return;1424 1425 for ( const ast::Decl * member : aggInst->lookup( offsetofExpr->member ) ) {1426 auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( member );1427 addCandidate(1428 new ast::OffsetofExpr{ offsetofExpr->location, aggInst, dwt }, tenv );1429 }1430 }1431 1432 void postvisit( const ast::OffsetofExpr * offsetofExpr ) {1433 addCandidate( offsetofExpr, tenv );1434 }1435 1436 void postvisit( const ast::OffsetPackExpr * offsetPackExpr ) {1437 addCandidate( offsetPackExpr, tenv );1438 }1439 1440 void postvisit( const ast::LogicalExpr * logicalExpr ) {1441 CandidateFinder finder1( context, tenv );1442 finder1.find( logicalExpr->arg1, ResolvMode::withAdjustment() );1443 if ( finder1.candidates.empty() ) return;1444 1445 CandidateFinder finder2( context, tenv );1446 finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() );1447 if ( finder2.candidates.empty() ) return;1448 1449 reason.code = NoMatch;1450 1451 for ( const CandidateRef & r1 : finder1.candidates ) {1452 for ( const CandidateRef & r2 : finder2.candidates ) {1453 ast::TypeEnvironment env{ r1->env };1454 env.simpleCombine( r2->env );1455 ast::OpenVarSet open{ r1->open };1456 mergeOpenVars( open, r2->open );1457 ast::AssertionSet need;1458 mergeAssertionSet( need, r1->need );1459 mergeAssertionSet( need, r2->need );1460 1461 addCandidate(1462 new ast::LogicalExpr{1463 logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd },1464 std::move( env ), std::move( open ), std::move( need ), r1->cost + r2->cost );1465 }1466 }1467 }1468 1469 void postvisit( const ast::ConditionalExpr * conditionalExpr ) {1470 // candidates for condition1471 CandidateFinder finder1( context, tenv );1472 finder1.find( conditionalExpr->arg1, ResolvMode::withAdjustment() );1473 if ( finder1.candidates.empty() ) return;1474 1475 // candidates for true result1476 CandidateFinder finder2( context, tenv );1477 finder2.allowVoid = true;1478 finder2.find( conditionalExpr->arg2, ResolvMode::withAdjustment() );1479 if ( finder2.candidates.empty() ) return;1480 1481 // candidates for false result1482 CandidateFinder finder3( context, tenv );1483 finder3.allowVoid = true;1484 finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() );1485 if ( finder3.candidates.empty() ) return;1486 1487 reason.code = NoMatch;1488 1489 for ( const CandidateRef & r1 : finder1.candidates ) {1490 for ( const CandidateRef & r2 : finder2.candidates ) {1491 for ( const CandidateRef & r3 : finder3.candidates ) {1492 ast::TypeEnvironment env{ r1->env };1493 env.simpleCombine( r2->env );1494 env.simpleCombine( r3->env );1495 ast::OpenVarSet open{ r1->open };1496 mergeOpenVars( open, r2->open );1497 mergeOpenVars( open, r3->open );1498 ast::AssertionSet need;1499 mergeAssertionSet( need, r1->need );1500 mergeAssertionSet( need, r2->need );1501 mergeAssertionSet( need, r3->need );1502 ast::AssertionSet have;1503 1504 // unify true and false results, then infer parameters to produce new1505 // candidates1506 ast::ptr< ast::Type > common;1507 if (1508 unify(1509 r2->expr->result, r3->expr->result, env, need, have, open,1510 common )1511 ) {1512 // generate typed expression1513 ast::ConditionalExpr * newExpr = new ast::ConditionalExpr{1514 conditionalExpr->location, r1->expr, r2->expr, r3->expr };1515 newExpr->result = common ? common : r2->expr->result;1516 // convert both options to result type1517 Cost cost = r1->cost + r2->cost + r3->cost;1518 newExpr->arg2 = computeExpressionConversionCost(1519 newExpr->arg2, newExpr->result, symtab, env, cost );1520 newExpr->arg3 = computeExpressionConversionCost(1521 newExpr->arg3, newExpr->result, symtab, env, cost );1522 // output candidate1523 CandidateRef newCand = std::make_shared<Candidate>(1524 newExpr, std::move( env ), std::move( open ), std::move( need ), cost );1525 inferParameters( newCand, candidates );1526 }1527 }1528 }1529 }1530 }1531 1532 void postvisit( const ast::CommaExpr * commaExpr ) {1533 ast::TypeEnvironment env{ tenv };1534 ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, context, env );1535 1536 CandidateFinder finder2( context, env );1537 finder2.find( commaExpr->arg2, ResolvMode::withAdjustment() );1538 1539 for ( const CandidateRef & r2 : finder2.candidates ) {1540 addCandidate( *r2, new ast::CommaExpr{ commaExpr->location, arg1, r2->expr } );1541 }1542 }1543 1544 void postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr ) {1545 addCandidate( ctorExpr, tenv );1546 }1547 1548 void postvisit( const ast::ConstructorExpr * ctorExpr ) {1549 CandidateFinder finder( context, tenv );1550 finder.allowVoid = true;1551 finder.find( ctorExpr->callExpr, ResolvMode::withoutPrune() );1552 for ( CandidateRef & r : finder.candidates ) {1553 addCandidate( *r, new ast::ConstructorExpr{ ctorExpr->location, r->expr } );1554 }1555 }1556 1557 void postvisit( const ast::RangeExpr * rangeExpr ) {1558 // resolve low and high, accept candidates where low and high types unify1559 CandidateFinder finder1( context, tenv );1560 finder1.find( rangeExpr->low, ResolvMode::withAdjustment() );1561 if ( finder1.candidates.empty() ) return;1562 1563 CandidateFinder finder2( context, tenv );1564 finder2.find( rangeExpr->high, ResolvMode::withAdjustment() );1565 if ( finder2.candidates.empty() ) return;1566 1567 reason.code = NoMatch;1568 1569 for ( const CandidateRef & r1 : finder1.candidates ) {1570 for ( const CandidateRef & r2 : finder2.candidates ) {1571 ast::TypeEnvironment env{ r1->env };1572 env.simpleCombine( r2->env );1573 ast::OpenVarSet open{ r1->open };1574 mergeOpenVars( open, r2->open );1575 ast::AssertionSet need;1576 mergeAssertionSet( need, r1->need );1577 mergeAssertionSet( need, r2->need );1578 ast::AssertionSet have;1579 1580 ast::ptr< ast::Type > common;1581 if (1582 unify(1583 r1->expr->result, r2->expr->result, env, need, have, open,1584 common )1585 ) {1586 // generate new expression1587 ast::RangeExpr * newExpr =1588 new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr };1589 newExpr->result = common ? common : r1->expr->result;1590 // add candidate1591 CandidateRef newCand = std::make_shared<Candidate>(1592 newExpr, std::move( env ), std::move( open ), std::move( need ),1593 r1->cost + r2->cost );1594 inferParameters( newCand, candidates );1595 }1596 }1597 }1598 }1599 1600 void postvisit( const ast::UntypedTupleExpr * tupleExpr ) {1601 std::vector< CandidateFinder > subCandidates =1602 selfFinder.findSubExprs( tupleExpr->exprs );1603 std::vector< CandidateList > possibilities;1604 combos( subCandidates.begin(), subCandidates.end(), back_inserter( possibilities ) );1605 1606 for ( const CandidateList & subs : possibilities ) {1607 std::vector< ast::ptr< ast::Expr > > exprs;1608 exprs.reserve( subs.size() );1609 for ( const CandidateRef & sub : subs ) { exprs.emplace_back( sub->expr ); }1610 1611 ast::TypeEnvironment env;1612 ast::OpenVarSet open;1613 ast::AssertionSet need;1614 for ( const CandidateRef & sub : subs ) {1615 env.simpleCombine( sub->env );1616 mergeOpenVars( open, sub->open );1617 mergeAssertionSet( need, sub->need );1618 }1619 1620 addCandidate(1621 new ast::TupleExpr{ tupleExpr->location, std::move( exprs ) },1622 std::move( env ), std::move( open ), std::move( need ), sumCost( subs ) );1623 }1624 }1625 1626 void postvisit( const ast::TupleExpr * tupleExpr ) {1627 addCandidate( tupleExpr, tenv );1628 }1629 1630 void postvisit( const ast::TupleIndexExpr * tupleExpr ) {1631 addCandidate( tupleExpr, tenv );1632 }1633 1634 void postvisit( const ast::TupleAssignExpr * tupleExpr ) {1635 addCandidate( tupleExpr, tenv );1636 }1637 1638 void postvisit( const ast::UniqueExpr * unqExpr ) {1639 CandidateFinder finder( context, tenv );1640 finder.find( unqExpr->expr, ResolvMode::withAdjustment() );1641 for ( CandidateRef & r : finder.candidates ) {1642 // ensure that the the id is passed on so that the expressions are "linked"1643 addCandidate( *r, new ast::UniqueExpr{ unqExpr->location, r->expr, unqExpr->id } );1644 }1645 }1646 1647 void postvisit( const ast::StmtExpr * stmtExpr ) {1648 addCandidate( resolveStmtExpr( stmtExpr, context ), tenv );1649 }1650 1651 void postvisit( const ast::UntypedInitExpr * initExpr ) {1652 // handle each option like a cast1653 CandidateList matches;1654 PRINT(1655 std::cerr << "untyped init expr: " << initExpr << std::endl;1656 )1657 // O(n^2) checks of d-types with e-types1658 for ( const ast::InitAlternative & initAlt : initExpr->initAlts ) {1659 // calculate target type1660 const ast::Type * toType = resolveTypeof( initAlt.type, context );1661 toType = adjustExprType( toType, tenv, symtab );1662 // The call to find must occur inside this loop, otherwise polymorphic return1663 // types are not bound to the initialization type, since return type variables are1664 // only open for the duration of resolving the UntypedExpr.1665 CandidateFinder finder( context, tenv, toType );1666 finder.find( initExpr->expr, ResolvMode::withAdjustment() );1667 1668 Cost minExprCost = Cost::infinity;1669 Cost minCastCost = Cost::infinity;1670 for ( CandidateRef & cand : finder.candidates ) {1671 if(reason.code == NotFound) reason.code = NoMatch;1672 1673 ast::TypeEnvironment env{ cand->env };1674 ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have;1675 ast::OpenVarSet open{ cand->open };1676 1677 PRINT(1678 std::cerr << " @ " << toType << " " << initAlt.designation << std::endl;1679 )1680 1681 // It is possible that a cast can throw away some values in a multiply-valued1682 // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of1683 // the subexpression results that are cast directly. The candidate is invalid1684 // if it has fewer results than there are types to cast to.1685 int discardedValues = cand->expr->result->size() - toType->size();1686 if ( discardedValues < 0 ) continue;1687 1688 // unification run for side-effects1689 bool canUnify = unify( toType, cand->expr->result, env, need, have, open );1690 (void) canUnify;1691 Cost thisCost = computeConversionCost( cand->expr->result, toType, cand->expr->get_lvalue(),1692 symtab, env );1693 PRINT(1694 Cost legacyCost = castCost( cand->expr->result, toType, cand->expr->get_lvalue(),1695 symtab, env );1696 std::cerr << "Considering initialization:";1697 std::cerr << std::endl << " FROM: " << cand->expr->result << std::endl;1698 std::cerr << std::endl << " TO: " << toType << std::endl;1699 std::cerr << std::endl << " Unification " << (canUnify ? "succeeded" : "failed");1700 std::cerr << std::endl << " Legacy cost " << legacyCost;1701 std::cerr << std::endl << " New cost " << thisCost;1702 std::cerr << std::endl;1703 )1704 if ( thisCost != Cost::infinity ) {1705 // count one safe conversion for each value that is thrown away1706 thisCost.incSafe( discardedValues );1707 if ( cand->cost < minExprCost || ( cand->cost == minExprCost && thisCost < minCastCost ) ) {1708 minExprCost = cand->cost;1709 minCastCost = thisCost;1710 matches.clear();1711 }1712 // ambiguous case, still output candidates to print in error message1713 if ( cand->cost == minExprCost && thisCost == minCastCost ) {1714 CandidateRef newCand = std::make_shared<Candidate>(1715 new ast::InitExpr{1716 initExpr->location, restructureCast( cand->expr, toType ),1717 initAlt.designation },1718 std::move(env), std::move( open ), std::move( need ), cand->cost + thisCost );1719 // currently assertions are always resolved immediately so this should have no effect.1720 // if this somehow changes in the future (e.g. delayed by indeterminate return type)1721 // we may need to revisit the logic.1722 inferParameters( newCand, matches );1723 }1724 1725 }1726 1727 }1728 1729 }1730 1731 // select first on argument cost, then conversion cost1732 // CandidateList minArgCost = findMinCost( matches );1733 // promoteCvtCost( minArgCost );1734 // candidates = findMinCost( minArgCost );1735 candidates = std::move(matches);1736 }1737 1738 void postvisit( const ast::InitExpr * ) {1739 assertf( false, "CandidateFinder should never see a resolved InitExpr." );1740 }1741 1742 void postvisit( const ast::DeletedExpr * ) {1743 assertf( false, "CandidateFinder should never see a DeletedExpr." );1744 }1745 1746 void postvisit( const ast::GenericExpr * ) {1747 assertf( false, "_Generic is not yet supported." );1748 }1749 };1750 1751 // size_t Finder::traceId = Stats::Heap::new_stacktrace_id("Finder");1752 /// Prunes a list of candidates down to those that have the minimum conversion cost for a given1753 /// return type. Skips ambiguous candidates.1754 1755 } // anonymous namespace1756 1757 bool CandidateFinder::pruneCandidates( CandidateList & candidates, CandidateList & out, std::vector<std::string> & errors ) {1758 struct PruneStruct {1759 CandidateRef candidate;1760 bool ambiguous;1761 1762 PruneStruct() = default;1763 PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {}1764 };1765 1766 // find lowest-cost candidate for each type1767 std::unordered_map< std::string, PruneStruct > selected;1768 // attempt to skip satisfyAssertions on more expensive alternatives if better options have been found1769 std::sort(candidates.begin(), candidates.end(), [](const CandidateRef & x, const CandidateRef & y){return x->cost < y->cost;});1770 for ( CandidateRef & candidate : candidates ) {1771 std::string mangleName;1772 {1773 ast::ptr< ast::Type > newType = candidate->expr->result;1774 assertf(candidate->expr->result, "Result of expression %p for candidate is null", candidate->expr.get());1775 candidate->env.apply( newType );1776 mangleName = Mangle::mangle( newType );1777 }1778 1779 auto found = selected.find( mangleName );1780 if (found != selected.end() && found->second.candidate->cost < candidate->cost) {1781 PRINT(1782 std::cerr << "cost " << candidate->cost << " loses to "1783 << found->second.candidate->cost << std::endl;1784 )1785 continue;1786 }1787 1788 // xxx - when do satisfyAssertions produce more than 1 result?1789 // this should only happen when initial result type contains1790 // unbound type parameters, then it should never be pruned by1791 // the previous step, since renameTyVars guarantees the mangled name1792 // is unique.1793 CandidateList satisfied;1794 bool needRecomputeKey = false;1795 if (candidate->need.empty()) {1796 satisfied.emplace_back(candidate);1797 }1798 else {1799 satisfyAssertions(candidate, context.symtab, satisfied, errors);1800 needRecomputeKey = true;1801 }1802 1803 for (auto & newCand : satisfied) {1804 // recomputes type key, if satisfyAssertions changed it1805 if (needRecomputeKey)1806 {1807 ast::ptr< ast::Type > newType = newCand->expr->result;1808 assertf(newCand->expr->result, "Result of expression %p for candidate is null", newCand->expr.get());1809 newCand->env.apply( newType );1810 mangleName = Mangle::mangle( newType );1811 }1812 auto found = selected.find( mangleName );1813 if ( found != selected.end() ) {1814 // tiebreaking by picking the lower cost on CURRENT expression1815 // NOTE: this behavior is different from C semantics.1816 // Specific remediations are performed for C operators at postvisit(UntypedExpr).1817 // Further investigations may take place.1818 if ( newCand->cost < found->second.candidate->cost1819 || (newCand->cost == found->second.candidate->cost && newCand->cvtCost < found->second.candidate->cvtCost) ) {1820 PRINT(1821 std::cerr << "cost " << newCand->cost << " beats "1822 << found->second.candidate->cost << std::endl;1823 )1824 1825 found->second = PruneStruct{ newCand };1826 } else if ( newCand->cost == found->second.candidate->cost && newCand->cvtCost == found->second.candidate->cvtCost) {1827 // if one of the candidates contains a deleted identifier, can pick the other,1828 // since deleted expressions should not be ambiguous if there is another option1829 // that is at least as good1830 if ( findDeletedExpr( newCand->expr ) ) {1831 // do nothing1832 PRINT( std::cerr << "candidate is deleted" << std::endl; )1833 } else if ( findDeletedExpr( found->second.candidate->expr ) ) {1834 PRINT( std::cerr << "current is deleted" << std::endl; )1835 found->second = PruneStruct{ newCand };1836 } else {1837 PRINT( std::cerr << "marking ambiguous" << std::endl; )1838 found->second.ambiguous = true;1839 }1840 } else {1841 // xxx - can satisfyAssertions increase the cost?1842 PRINT(1843 std::cerr << "cost " << newCand->cost << " loses to "1844 << found->second.candidate->cost << std::endl;1845 )1846 }1847 } else {1848 selected.emplace_hint( found, mangleName, newCand );1849 }1850 }1851 }1852 1853 // report unambiguous min-cost candidates1854 // CandidateList out;1855 for ( auto & target : selected ) {1856 if ( target.second.ambiguous ) continue;1857 1858 CandidateRef cand = target.second.candidate;1859 1860 ast::ptr< ast::Type > newResult = cand->expr->result;1861 cand->env.applyFree( newResult );1862 cand->expr = ast::mutate_field(1863 cand->expr.get(), &ast::Expr::result, std::move( newResult ) );1864 1865 out.emplace_back( cand );1866 }1867 // if everything is lost in satisfyAssertions, report the error1868 return !selected.empty();1869 }1870 1871 void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) {1872 // Find alternatives for expression1873 ast::Pass<Finder> finder{ *this };1874 expr->accept( finder );1875 1876 if ( mode.failFast && candidates.empty() ) {1877 switch(finder.core.reason.code) {1878 case Finder::NotFound:1879 { SemanticError( expr, "No alternatives for expression " ); break; }1880 case Finder::NoMatch:1881 { SemanticError( expr, "Invalid application of existing declaration(s) in expression " ); break; }1882 case Finder::ArgsToFew:1883 case Finder::ArgsToMany:1884 case Finder::RetsToFew:1885 case Finder::RetsToMany:1886 case Finder::NoReason:1887 default:1888 { SemanticError( expr->location, "No reasonable alternatives for expression : reasons unkown" ); }1889 }1890 }1891 1892 /*1893 if ( mode.satisfyAssns || mode.prune ) {1894 // trim candidates to just those where the assertions are satisfiable1895 // - necessary pre-requisite to pruning1896 CandidateList satisfied;1897 std::vector< std::string > errors;1898 for ( CandidateRef & candidate : candidates ) {1899 satisfyAssertions( candidate, localSyms, satisfied, errors );1900 }1901 1902 // fail early if none such1903 if ( mode.failFast && satisfied.empty() ) {1904 std::ostringstream stream;1905 stream << "No alternatives with satisfiable assertions for " << expr << "\n";1906 for ( const auto& err : errors ) {1907 stream << err;1908 }1909 SemanticError( expr->location, stream.str() );1910 }1911 1912 // reset candidates1913 candidates = move( satisfied );1914 }1915 */1916 1917 // if ( mode.prune ) {1918 // optimization: don't prune for NameExpr since it never has cost1919 if ( mode.prune && !dynamic_cast<const ast::NameExpr *>(expr)) {1920 // trim candidates to single best one1921 PRINT(1922 std::cerr << "alternatives before prune:" << std::endl;1923 print( std::cerr, candidates );1924 )1925 1926 CandidateList pruned;1927 std::vector<std::string> errors;1928 bool found = pruneCandidates( candidates, pruned, errors );1929 1930 if ( mode.failFast && pruned.empty() ) {1931 std::ostringstream stream;1932 if (found) {1933 CandidateList winners = findMinCost( candidates );1934 stream << "Cannot choose between " << winners.size() << " alternatives for "1935 "expression\n";1936 ast::print( stream, expr );1937 stream << " Alternatives are:\n";1938 print( stream, winners, 1 );1939 SemanticError( expr->location, stream.str() );1940 }1941 else {1942 stream << "No alternatives with satisfiable assertions for " << expr << "\n";1943 for ( const auto& err : errors ) {1944 stream << err;1945 }1946 SemanticError( expr->location, stream.str() );1947 }1948 }1949 1950 auto oldsize = candidates.size();1951 candidates = std::move( pruned );1952 1953 PRINT(1954 std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;1955 )1956 PRINT(1957 std::cerr << "there are " << candidates.size() << " alternatives after elimination"1958 << std::endl;1959 )1960 }1961 1962 // adjust types after pruning so that types substituted by pruneAlternatives are correctly1963 // adjusted1964 if ( mode.adjust ) {1965 for ( CandidateRef & r : candidates ) {1966 r->expr = ast::mutate_field(1967 r->expr.get(), &ast::Expr::result,1968 adjustExprType( r->expr->result, r->env, context.symtab ) );1969 }1970 }1971 1972 // Central location to handle gcc extension keyword, etc. for all expressions1973 for ( CandidateRef & r : candidates ) {1974 if ( r->expr->extension != expr->extension ) {1975 r->expr.get_and_mutate()->extension = expr->extension;1976 }1977 }1978 }1979 1980 std::vector< CandidateFinder > CandidateFinder::findSubExprs(1981 const std::vector< ast::ptr< ast::Expr > > & xs1982 ) {1983 std::vector< CandidateFinder > out;1984 1985 for ( const auto & x : xs ) {1986 out.emplace_back( context, env );1987 out.back().find( x, ResolvMode::withAdjustment() );1988 1989 PRINT(1990 std::cerr << "findSubExprs" << std::endl;1991 print( std::cerr, out.back().candidates );1992 )1993 }1994 1995 return out;1996 }1997 1998 2054 } // namespace ResolvExpr 1999 2055
Note: See TracChangeset
for help on using the changeset viewer.