- Timestamp:
- Jun 17, 2023, 9:31:11 AM (16 months ago)
- Branches:
- master
- Children:
- 727c39d5
- Parents:
- 77fd9fe2 (diff), b1e21da (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)
links above to see all the changes relative to each parent. - Location:
- src
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/CandidateFinder.cpp
r77fd9fe2 r0e0f25d5 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 ast::Type * paramType, const ast::Init * init, const ExplodedArgs_new & args,318 std::vector< ArgPack > & results, std::size_t & genStart, const ast::SymbolTable & symtab,319 unsigned nTuples = 0320 ) {321 if ( auto tupleType = dynamic_cast< const ast::TupleType * >( paramType ) ) {322 // paramType is a TupleType -- group args into a TupleExpr323 ++nTuples;324 for ( const ast::Type * type : *tupleType ) {325 // xxx - dropping initializer changes behaviour from previous, but seems correct326 // ^^^ need to handle the case where a tuple has a default argument327 if ( ! instantiateArgument(328 type, nullptr, args, results, genStart, symtab, nTuples ) ) return false;329 nTuples = 0;330 }331 // re-constitute tuples for final generation332 for ( auto i = genStart; i < results.size(); ++i ) {333 results[i].endTuple( results );334 }335 return true;336 } else if ( const ast::TypeInstType * ttype = Tuples::isTtype( paramType ) ) {337 // paramType is a ttype, consumes all remaining arguments338 339 // completed tuples; will be spliced to end of results to finish340 std::vector< ArgPack > finalResults{};341 342 // iterate until all results completed343 std::size_t genEnd;344 ++nTuples;345 do {346 genEnd = results.size();347 348 // add another argument to results349 for ( std::size_t i = genStart; i < genEnd; ++i ) {350 unsigned nextArg = results[i].nextArg;351 352 // use next element of exploded tuple if present353 if ( results[i].hasExpl() ) {354 const ExplodedArg & expl = results[i].getExpl( args );355 356 unsigned nextExpl = results[i].nextExpl + 1;357 if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }358 359 results.emplace_back(360 i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ),361 copy( results[i].need ), copy( results[i].have ),362 copy( results[i].open ), nextArg, nTuples, Cost::zero, nextExpl,363 results[i].explAlt );364 365 continue;366 }367 368 // finish result when out of arguments369 if ( nextArg >= args.size() ) {370 ArgPack newResult{371 results[i].env, results[i].need, results[i].have, results[i].open };372 newResult.nextArg = nextArg;373 const ast::Type * argType = nullptr;374 375 if ( nTuples > 0 || ! results[i].expr ) {376 // first iteration or no expression to clone,377 // push empty tuple expression378 newResult.parent = i;379 newResult.expr = new ast::TupleExpr{ CodeLocation{}, {} };380 argType = newResult.expr->result;381 } else {382 // clone result to collect tuple383 newResult.parent = results[i].parent;384 newResult.cost = results[i].cost;385 newResult.tupleStart = results[i].tupleStart;386 newResult.expr = results[i].expr;387 argType = newResult.expr->result;388 389 if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {390 // the case where a ttype value is passed directly is special,391 // e.g. for argument forwarding purposes392 // xxx - what if passing multiple arguments, last of which is393 // ttype?394 // xxx - what would happen if unify was changed so that unifying395 // tuple396 // types flattened both before unifying lists? then pass in397 // TupleType (ttype) below.398 --newResult.tupleStart;399 } else {400 // collapse leftover arguments into tuple401 newResult.endTuple( results );402 argType = newResult.expr->result;403 }404 }405 406 // check unification for ttype before adding to final407 if (408 unify(409 ttype, argType, newResult.env, newResult.need, newResult.have,410 newResult.open )411 ) {412 finalResults.emplace_back( std::move( newResult ) );413 }414 415 continue;416 }417 418 // add each possible next argument419 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {420 const ExplodedArg & expl = args[nextArg][j];421 422 // fresh copies of parent parameters for this iteration423 ast::TypeEnvironment env = results[i].env;424 ast::OpenVarSet open = results[i].open;425 426 env.addActual( expl.env, open );427 428 // skip empty tuple arguments by (nearly) cloning parent into next gen429 if ( expl.exprs.empty() ) {430 results.emplace_back(431 results[i], std::move( env ), copy( results[i].need ),432 copy( results[i].have ), std::move( open ), nextArg + 1, expl.cost );433 434 continue;435 }436 437 // add new result438 results.emplace_back(439 i, expl.exprs.front(), std::move( env ), copy( results[i].need ),440 copy( results[i].have ), std::move( open ), nextArg + 1, nTuples,441 expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );442 }443 }444 445 // reset for next round446 genStart = genEnd;447 nTuples = 0;448 } while ( genEnd != results.size() );449 450 // splice final results onto results451 for ( std::size_t i = 0; i < finalResults.size(); ++i ) {452 results.emplace_back( std::move( finalResults[i] ) );453 }454 return ! finalResults.empty();455 }456 457 // iterate each current subresult458 std::size_t genEnd = results.size();459 for ( std::size_t i = genStart; i < genEnd; ++i ) {460 unsigned nextArg = results[i].nextArg;461 462 // use remainder of exploded tuple if present463 if ( results[i].hasExpl() ) {464 const ExplodedArg & expl = results[i].getExpl( args );465 const ast::Expr * expr = expl.exprs[ results[i].nextExpl ];466 467 ast::TypeEnvironment env = results[i].env;468 ast::AssertionSet need = results[i].need, have = results[i].have;469 ast::OpenVarSet open = results[i].open;470 471 const ast::Type * argType = expr->result;472 473 PRINT(474 std::cerr << "param type is ";475 ast::print( std::cerr, paramType );476 std::cerr << std::endl << "arg type is ";477 ast::print( std::cerr, argType );478 std::cerr << std::endl;479 )480 481 if ( unify( paramType, argType, env, need, have, open ) ) {482 unsigned nextExpl = results[i].nextExpl + 1;483 if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }484 485 results.emplace_back(486 i, expr, std::move( env ), std::move( need ), std::move( have ), std::move( open ), nextArg,487 nTuples, Cost::zero, nextExpl, results[i].explAlt );488 }489 490 continue;491 }492 493 // use default initializers if out of arguments494 if ( nextArg >= args.size() ) {495 if ( const ast::ConstantExpr * cnst = getDefaultValue( init ) ) {496 ast::TypeEnvironment env = results[i].env;497 ast::AssertionSet need = results[i].need, have = results[i].have;498 ast::OpenVarSet open = results[i].open;499 500 if ( unify( paramType, cnst->result, env, need, have, open ) ) {501 results.emplace_back(502 i, new ast::DefaultArgExpr{ cnst->location, cnst }, std::move( env ),503 std::move( need ), std::move( have ), std::move( open ), nextArg, nTuples );504 }505 }506 507 continue;508 }509 510 // Check each possible next argument511 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {512 const ExplodedArg & expl = args[nextArg][j];513 514 // fresh copies of parent parameters for this iteration515 ast::TypeEnvironment env = results[i].env;516 ast::AssertionSet need = results[i].need, have = results[i].have;517 ast::OpenVarSet open = results[i].open;518 519 env.addActual( expl.env, open );520 521 // skip empty tuple arguments by (nearly) cloning parent into next gen522 if ( expl.exprs.empty() ) {523 results.emplace_back(524 results[i], std::move( env ), std::move( need ), std::move( have ), std::move( open ),525 nextArg + 1, expl.cost );526 527 continue;528 }529 530 // consider only first exploded arg531 const ast::Expr * expr = expl.exprs.front();532 const ast::Type * argType = expr->result;533 534 PRINT(535 std::cerr << "param type is ";536 ast::print( std::cerr, paramType );537 std::cerr << std::endl << "arg type is ";538 ast::print( std::cerr, argType );539 std::cerr << std::endl;540 )541 542 // attempt to unify types543 if ( unify( paramType, argType, env, need, have, open ) ) {544 // add new result545 results.emplace_back(546 i, expr, std::move( env ), std::move( need ), std::move( have ), std::move( open ),547 nextArg + 1, nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );548 }549 }550 }551 552 // reset for next parameter553 genStart = genEnd;554 555 return genEnd != results.size(); // were any new results added?556 }557 558 /// Generate a cast expression from `arg` to `toType`559 const ast::Expr * restructureCast(560 ast::ptr< ast::Expr > & arg, const ast::Type * toType, ast::GeneratedFlag isGenerated = ast::GeneratedCast561 ) {562 if (563 arg->result->size() > 1564 && ! toType->isVoid()565 && ! dynamic_cast< const ast::ReferenceType * >( toType )566 ) {567 // Argument is a tuple and the target type is neither void nor a reference. Cast each568 // member of the tuple to its corresponding target type, producing the tuple of those569 // cast expressions. If there are more components of the tuple than components in the570 // target type, then excess components do not come out in the result expression (but571 // UniqueExpr ensures that the side effects will still be produced)572 if ( Tuples::maybeImpureIgnoreUnique( arg ) ) {573 // expressions which may contain side effects require a single unique instance of574 // the expression575 arg = new ast::UniqueExpr{ arg->location, arg };576 }577 std::vector< ast::ptr< ast::Expr > > components;578 for ( unsigned i = 0; i < toType->size(); ++i ) {579 // cast each component580 ast::ptr< ast::Expr > idx = new ast::TupleIndexExpr{ arg->location, arg, i };581 components.emplace_back(582 restructureCast( idx, toType->getComponent( i ), isGenerated ) );583 }584 return new ast::TupleExpr{ arg->location, std::move( components ) };585 } else {586 // handle normally587 return new ast::CastExpr{ arg->location, arg, toType, isGenerated };588 }589 }590 591 /// Gets the name from an untyped member expression (must be NameExpr)592 const std::string & getMemberName( const ast::UntypedMemberExpr * memberExpr ) {593 if ( memberExpr->member.as< ast::ConstantExpr >() ) {594 SemanticError( memberExpr, "Indexed access to struct fields unsupported: " );595 }596 597 return memberExpr->member.strict_as< ast::NameExpr >()->name;598 }599 600 /// Actually visits expressions to find their candidate interpretations601 class Finder final : public ast::WithShortCircuiting {602 const ResolveContext & context;603 const ast::SymbolTable & symtab;604 public:605 // static size_t traceId;606 CandidateFinder & selfFinder;607 CandidateList & candidates;608 const ast::TypeEnvironment & tenv;609 ast::ptr< ast::Type > & targetType;610 611 enum Errors {612 NotFound,613 NoMatch,614 ArgsToFew,615 ArgsToMany,616 RetsToFew,617 RetsToMany,618 NoReason619 };620 621 struct {622 Errors code = NotFound;623 } reason;624 625 Finder( CandidateFinder & f )626 : context( f.context ), symtab( context.symtab ), selfFinder( f ),627 candidates( f.candidates ), tenv( f.env ), targetType( f.targetType ) {}628 629 void previsit( const ast::Node * ) { visit_children = false; }630 631 /// Convenience to add candidate to list632 template<typename... Args>633 void addCandidate( Args &&... args ) {634 candidates.emplace_back( new Candidate{ std::forward<Args>( args )... } );635 reason.code = NoReason;636 }637 638 void postvisit( const ast::ApplicationExpr * applicationExpr ) {639 addCandidate( applicationExpr, tenv );640 }641 642 /// Set up candidate assertions for inference643 void inferParameters( CandidateRef & newCand, CandidateList & out ) {644 // Set need bindings for any unbound assertions645 UniqueId crntResnSlot = 0; // matching ID for this expression's assertions646 for ( auto & assn : newCand->need ) {647 // skip already-matched assertions648 if ( assn.second.resnSlot != 0 ) continue;649 // assign slot for expression if needed650 if ( crntResnSlot == 0 ) { crntResnSlot = ++globalResnSlot; }651 // fix slot to assertion652 assn.second.resnSlot = crntResnSlot;653 }654 // pair slot to expression655 if ( crntResnSlot != 0 ) {656 newCand->expr.get_and_mutate()->inferred.resnSlots().emplace_back( crntResnSlot );657 }658 659 // add to output list; assertion satisfaction will occur later660 out.emplace_back( newCand );661 }662 663 /// Completes a function candidate with arguments located664 void validateFunctionCandidate(665 const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results,666 CandidateList & out667 ) {668 ast::ApplicationExpr * appExpr =669 new ast::ApplicationExpr{ func->expr->location, func->expr };670 // sum cost and accumulate arguments671 std::deque< const ast::Expr * > args;672 Cost cost = func->cost;673 const ArgPack * pack = &result;674 while ( pack->expr ) {675 args.emplace_front( pack->expr );676 cost += pack->cost;677 pack = &results[pack->parent];678 }679 std::vector< ast::ptr< ast::Expr > > vargs( args.begin(), args.end() );680 appExpr->args = std::move( vargs );681 // build and validate new candidate682 auto newCand =683 std::make_shared<Candidate>( appExpr, result.env, result.open, result.need, cost );684 PRINT(685 std::cerr << "instantiate function success: " << appExpr << std::endl;686 std::cerr << "need assertions:" << std::endl;687 ast::print( std::cerr, result.need, 2 );688 )689 inferParameters( newCand, out );690 }691 692 /// Builds a list of candidates for a function, storing them in out693 void makeFunctionCandidates(694 const CandidateRef & func, const ast::FunctionType * funcType,695 const ExplodedArgs_new & args, CandidateList & out696 ) {697 ast::OpenVarSet funcOpen;698 ast::AssertionSet funcNeed, funcHave;699 ast::TypeEnvironment funcEnv{ func->env };700 makeUnifiableVars( funcType, funcOpen, funcNeed );701 // add all type variables as open variables now so that those not used in the702 // parameter list are still considered open703 funcEnv.add( funcType->forall );704 705 if ( targetType && ! targetType->isVoid() && ! funcType->returns.empty() ) {706 // attempt to narrow based on expected target type707 const ast::Type * returnType = funcType->returns.front();708 if ( selfFinder.strictMode ) {709 if ( ! unifyExact(710 returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen, noWiden() ) // xxx - is no widening correct?711 ) {712 // unification failed, do not pursue this candidate713 return;714 }715 }716 else {717 if ( ! unify(718 returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen )719 ) {720 // unification failed, do not pursue this candidate721 return;722 }723 }724 }725 726 // iteratively build matches, one parameter at a time727 std::vector< ArgPack > results;728 results.emplace_back( funcEnv, funcNeed, funcHave, funcOpen );729 std::size_t genStart = 0;730 731 // xxx - how to handle default arg after change to ftype representation?732 if (const ast::VariableExpr * varExpr = func->expr.as<ast::VariableExpr>()) {733 if (const ast::FunctionDecl * funcDecl = varExpr->var.as<ast::FunctionDecl>()) {734 // function may have default args only if directly calling by name735 // must use types on candidate however, due to RenameVars substitution736 auto nParams = funcType->params.size();737 738 for (size_t i=0; i<nParams; ++i) {739 auto obj = funcDecl->params[i].strict_as<ast::ObjectDecl>();740 if (!instantiateArgument(741 funcType->params[i], obj->init, args, results, genStart, symtab)) return;742 }743 goto endMatch;744 }745 }746 for ( const auto & param : funcType->params ) {747 // Try adding the arguments corresponding to the current parameter to the existing748 // matches749 // no default args for indirect calls750 if ( ! instantiateArgument(751 param, nullptr, args, results, genStart, symtab ) ) return;752 }753 754 endMatch:755 if ( funcType->isVarArgs ) {756 // append any unused arguments to vararg pack757 std::size_t genEnd;758 do {759 genEnd = results.size();760 761 // iterate results762 for ( std::size_t i = genStart; i < genEnd; ++i ) {763 unsigned nextArg = results[i].nextArg;764 765 // use remainder of exploded tuple if present766 if ( results[i].hasExpl() ) {767 const ExplodedArg & expl = results[i].getExpl( args );768 769 unsigned nextExpl = results[i].nextExpl + 1;770 if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }771 772 results.emplace_back(773 i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ),774 copy( results[i].need ), copy( results[i].have ),775 copy( results[i].open ), nextArg, 0, Cost::zero, nextExpl,776 results[i].explAlt );777 778 continue;779 }780 781 // finish result when out of arguments782 if ( nextArg >= args.size() ) {783 validateFunctionCandidate( func, results[i], results, out );784 785 continue;786 }787 788 // add each possible next argument789 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {790 const ExplodedArg & expl = args[nextArg][j];791 792 // fresh copies of parent parameters for this iteration793 ast::TypeEnvironment env = results[i].env;794 ast::OpenVarSet open = results[i].open;795 796 env.addActual( expl.env, open );797 798 // skip empty tuple arguments by (nearly) cloning parent into next gen799 if ( expl.exprs.empty() ) {800 results.emplace_back(801 results[i], std::move( env ), copy( results[i].need ),802 copy( results[i].have ), std::move( open ), nextArg + 1,803 expl.cost );804 805 continue;806 }807 808 // add new result809 results.emplace_back(810 i, expl.exprs.front(), std::move( env ), copy( results[i].need ),811 copy( results[i].have ), std::move( open ), nextArg + 1, 0, expl.cost,812 expl.exprs.size() == 1 ? 0 : 1, j );813 }814 }815 816 genStart = genEnd;817 } while( genEnd != results.size() );818 } else {819 // filter out the results that don't use all the arguments820 for ( std::size_t i = genStart; i < results.size(); ++i ) {821 ArgPack & result = results[i];822 if ( ! result.hasExpl() && result.nextArg >= args.size() ) {823 validateFunctionCandidate( func, result, results, out );824 }825 }826 }827 }828 829 /// Adds implicit struct-conversions to the alternative list830 void addAnonConversions( const CandidateRef & cand ) {831 // adds anonymous member interpretations whenever an aggregate value type is seen.832 // it's okay for the aggregate expression to have reference type -- cast it to the833 // base type to treat the aggregate as the referenced value834 ast::ptr< ast::Expr > aggrExpr( cand->expr );835 ast::ptr< ast::Type > & aggrType = aggrExpr.get_and_mutate()->result;836 cand->env.apply( aggrType );837 838 if ( aggrType.as< ast::ReferenceType >() ) {839 aggrExpr = new ast::CastExpr{ aggrExpr, aggrType->stripReferences() };840 }841 842 if ( auto structInst = aggrExpr->result.as< ast::StructInstType >() ) {843 addAggMembers( structInst, aggrExpr, *cand, Cost::unsafe, "" );844 } else if ( auto unionInst = aggrExpr->result.as< ast::UnionInstType >() ) {845 addAggMembers( unionInst, aggrExpr, *cand, Cost::unsafe, "" );846 }847 }848 849 /// Adds aggregate member interpretations850 void addAggMembers(851 const ast::BaseInstType * aggrInst, const ast::Expr * expr,852 const Candidate & cand, const Cost & addedCost, const std::string & name853 ) {854 for ( const ast::Decl * decl : aggrInst->lookup( name ) ) {855 auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( decl );856 CandidateRef newCand = std::make_shared<Candidate>(857 cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost );858 // add anonymous member interpretations whenever an aggregate value type is seen859 // as a member expression860 addAnonConversions( newCand );861 candidates.emplace_back( std::move( newCand ) );862 }863 }864 865 /// Adds tuple member interpretations866 void addTupleMembers(867 const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand,868 const Cost & addedCost, const ast::Expr * member869 ) {870 if ( auto constantExpr = dynamic_cast< const ast::ConstantExpr * >( member ) ) {871 // get the value of the constant expression as an int, must be between 0 and the872 // length of the tuple to have meaning873 long long val = constantExpr->intValue();874 if ( val >= 0 && (unsigned long long)val < tupleType->size() ) {875 addCandidate(876 cand, new ast::TupleIndexExpr{ expr->location, expr, (unsigned)val },877 addedCost );878 }879 }880 }881 882 void postvisit( const ast::UntypedExpr * untypedExpr ) {883 std::vector< CandidateFinder > argCandidates =884 selfFinder.findSubExprs( untypedExpr->args );885 886 // take care of possible tuple assignments887 // if not tuple assignment, handled as normal function call888 Tuples::handleTupleAssignment( selfFinder, untypedExpr, argCandidates );889 890 CandidateFinder funcFinder( context, tenv );891 if (auto nameExpr = untypedExpr->func.as<ast::NameExpr>()) {892 auto kind = ast::SymbolTable::getSpecialFunctionKind(nameExpr->name);893 if (kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS) {894 assertf(!argCandidates.empty(), "special function call without argument");895 for (auto & firstArgCand: argCandidates[0]) {896 ast::ptr<ast::Type> argType = firstArgCand->expr->result;897 firstArgCand->env.apply(argType);898 // strip references899 // xxx - is this correct?900 while (argType.as<ast::ReferenceType>()) argType = argType.as<ast::ReferenceType>()->base;901 902 // convert 1-tuple to plain type903 if (auto tuple = argType.as<ast::TupleType>()) {904 if (tuple->size() == 1) {905 argType = tuple->types[0];906 }907 }908 909 // if argType is an unbound type parameter, all special functions need to be searched.910 if (isUnboundType(argType)) {911 funcFinder.otypeKeys.clear();912 break;913 }914 915 if (argType.as<ast::PointerType>()) funcFinder.otypeKeys.insert(Mangle::Encoding::pointer);916 // else if (const ast::EnumInstType * enumInst = argType.as<ast::EnumInstType>()) {917 // const ast::EnumDecl * enumDecl = enumInst->base; // Here918 // if ( const ast::Type* enumType = enumDecl->base ) {919 // // instance of enum (T) is a instance of type (T)920 // funcFinder.otypeKeys.insert(Mangle::mangle(enumType, Mangle::NoGenericParams | Mangle::Type));921 // } else {922 // // instance of an untyped enum is techically int923 // funcFinder.otypeKeys.insert(Mangle::mangle(enumDecl, Mangle::NoGenericParams | Mangle::Type));924 // }925 // }926 else funcFinder.otypeKeys.insert(Mangle::mangle(argType, Mangle::NoGenericParams | Mangle::Type));927 }928 }929 }930 // if candidates are already produced, do not fail931 // xxx - is it possible that handleTupleAssignment and main finder both produce candidates?932 // this means there exists ctor/assign functions with a tuple as first parameter.933 ResolvMode mode = {934 true, // adjust935 !untypedExpr->func.as<ast::NameExpr>(), // prune if not calling by name936 selfFinder.candidates.empty() // failfast if other options are not found937 };938 funcFinder.find( untypedExpr->func, mode );939 // short-circuit if no candidates940 // if ( funcFinder.candidates.empty() ) return;941 942 reason.code = NoMatch;943 944 // find function operators945 ast::ptr< ast::Expr > opExpr = new ast::NameExpr{ untypedExpr->location, "?()" }; // ??? why not ?{}946 CandidateFinder opFinder( context, tenv );947 // okay if there aren't any function operations948 opFinder.find( opExpr, ResolvMode::withoutFailFast() );949 PRINT(950 std::cerr << "known function ops:" << std::endl;951 print( std::cerr, opFinder.candidates, 1 );952 )953 954 // pre-explode arguments955 ExplodedArgs_new argExpansions;956 for ( const CandidateFinder & args : argCandidates ) {957 argExpansions.emplace_back();958 auto & argE = argExpansions.back();959 for ( const CandidateRef & arg : args ) { argE.emplace_back( *arg, symtab ); }960 }961 962 // Find function matches963 CandidateList found;964 SemanticErrorException errors;965 for ( CandidateRef & func : funcFinder ) {966 try {967 PRINT(968 std::cerr << "working on alternative:" << std::endl;969 print( std::cerr, *func, 2 );970 )971 972 // check if the type is a pointer to function973 const ast::Type * funcResult = func->expr->result->stripReferences();974 if ( auto pointer = dynamic_cast< const ast::PointerType * >( funcResult ) ) {975 if ( auto function = pointer->base.as< ast::FunctionType >() ) {976 // if (!selfFinder.allowVoid && function->returns.empty()) continue;977 CandidateRef newFunc{ new Candidate{ *func } };978 newFunc->expr =979 referenceToRvalueConversion( newFunc->expr, newFunc->cost );980 makeFunctionCandidates( newFunc, function, argExpansions, found );981 }982 } else if (983 auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult )984 ) {985 if ( const ast::EqvClass * clz = func->env.lookup( *inst ) ) {986 if ( auto function = clz->bound.as< ast::FunctionType >() ) {987 CandidateRef newFunc{ new Candidate{ *func } };988 newFunc->expr =989 referenceToRvalueConversion( newFunc->expr, newFunc->cost );990 makeFunctionCandidates( newFunc, function, argExpansions, found );991 }992 }993 }994 } catch ( SemanticErrorException & e ) { errors.append( e ); }995 }996 997 // Find matches on function operators `?()`998 if ( ! opFinder.candidates.empty() ) {999 // add exploded function alternatives to front of argument list1000 std::vector< ExplodedArg > funcE;1001 funcE.reserve( funcFinder.candidates.size() );1002 for ( const CandidateRef & func : funcFinder ) {1003 funcE.emplace_back( *func, symtab );1004 }1005 argExpansions.emplace_front( std::move( funcE ) );1006 1007 for ( const CandidateRef & op : opFinder ) {1008 try {1009 // check if type is pointer-to-function1010 const ast::Type * opResult = op->expr->result->stripReferences();1011 if ( auto pointer = dynamic_cast< const ast::PointerType * >( opResult ) ) {1012 if ( auto function = pointer->base.as< ast::FunctionType >() ) {1013 CandidateRef newOp{ new Candidate{ *op} };1014 newOp->expr =1015 referenceToRvalueConversion( newOp->expr, newOp->cost );1016 makeFunctionCandidates( newOp, function, argExpansions, found );1017 }1018 }1019 } catch ( SemanticErrorException & e ) { errors.append( e ); }1020 }1021 }1022 1023 // Implement SFINAE; resolution errors are only errors if there aren't any non-error1024 // candidates1025 if ( found.empty() && ! errors.isEmpty() ) { throw errors; }1026 1027 // only keep the best matching intrinsic result to match C semantics (no unexpected narrowing/widening)1028 // TODO: keep one for each set of argument candidates?1029 Cost intrinsicCost = Cost::infinity;1030 CandidateList intrinsicResult;1031 1032 // Compute conversion costs1033 for ( CandidateRef & withFunc : found ) {1034 Cost cvtCost = computeApplicationConversionCost( withFunc, symtab );1035 1036 PRINT(1037 auto appExpr = withFunc->expr.strict_as< ast::ApplicationExpr >();1038 auto pointer = appExpr->func->result.strict_as< ast::PointerType >();1039 auto function = pointer->base.strict_as< ast::FunctionType >();1040 1041 std::cerr << "Case +++++++++++++ " << appExpr->func << std::endl;1042 std::cerr << "parameters are:" << std::endl;1043 ast::printAll( std::cerr, function->params, 2 );1044 std::cerr << "arguments are:" << std::endl;1045 ast::printAll( std::cerr, appExpr->args, 2 );1046 std::cerr << "bindings are:" << std::endl;1047 ast::print( std::cerr, withFunc->env, 2 );1048 std::cerr << "cost is: " << withFunc->cost << std::endl;1049 std::cerr << "cost of conversion is:" << cvtCost << std::endl;1050 )1051 1052 if ( cvtCost != Cost::infinity ) {1053 withFunc->cvtCost = cvtCost;1054 withFunc->cost += cvtCost;1055 auto func = withFunc->expr.strict_as<ast::ApplicationExpr>()->func.as<ast::VariableExpr>();1056 if (func && func->var->linkage == ast::Linkage::Intrinsic) {1057 if (withFunc->cost < intrinsicCost) {1058 intrinsicResult.clear();1059 intrinsicCost = withFunc->cost;1060 }1061 if (withFunc->cost == intrinsicCost) {1062 intrinsicResult.emplace_back(std::move(withFunc));1063 }1064 }1065 else {1066 candidates.emplace_back( std::move( withFunc ) );1067 }1068 }1069 }1070 spliceBegin( candidates, intrinsicResult );1071 found = std::move( candidates );1072 1073 // use a new list so that candidates are not examined by addAnonConversions twice1074 // CandidateList winners = findMinCost( found );1075 // promoteCvtCost( winners );1076 1077 // function may return a struct/union value, in which case we need to add candidates1078 // for implicit conversions to each of the anonymous members, which must happen after1079 // `findMinCost`, since anon conversions are never the cheapest1080 for ( const CandidateRef & c : found ) {1081 addAnonConversions( c );1082 }1083 // would this be too slow when we don't check cost anymore?1084 spliceBegin( candidates, found );1085 1086 if ( candidates.empty() && targetType && ! targetType->isVoid() && !selfFinder.strictMode ) {1087 // If resolution is unsuccessful with a target type, try again without, since it1088 // will sometimes succeed when it wouldn't with a target type binding.1089 // For example:1090 // forall( otype T ) T & ?[]( T *, ptrdiff_t );1091 // const char * x = "hello world";1092 // unsigned char ch = x[0];1093 // Fails with simple return type binding (xxx -- check this!) as follows:1094 // * T is bound to unsigned char1095 // * (x: const char *) is unified with unsigned char *, which fails1096 // xxx -- fix this better1097 targetType = nullptr;1098 postvisit( untypedExpr );1099 }1100 }1101 1102 /// true if expression is an lvalue1103 static bool isLvalue( const ast::Expr * x ) {1104 return x->result && ( x->get_lvalue() || x->result.as< ast::ReferenceType >() );1105 }1106 1107 void postvisit( const ast::AddressExpr * addressExpr ) {1108 CandidateFinder finder( context, tenv );1109 finder.find( addressExpr->arg );1110 1111 if( finder.candidates.empty() ) return;1112 1113 reason.code = NoMatch;1114 1115 for ( CandidateRef & r : finder.candidates ) {1116 if ( ! isLvalue( r->expr ) ) continue;1117 addCandidate( *r, new ast::AddressExpr{ addressExpr->location, r->expr } );1118 }1119 }1120 1121 void postvisit( const ast::LabelAddressExpr * labelExpr ) {1122 addCandidate( labelExpr, tenv );1123 }1124 1125 void postvisit( const ast::CastExpr * castExpr ) {1126 ast::ptr< ast::Type > toType = castExpr->result;1127 assert( toType );1128 toType = resolveTypeof( toType, context );1129 toType = adjustExprType( toType, tenv, symtab );1130 1131 CandidateFinder finder( context, tenv, toType );1132 if (toType->isVoid()) {1133 finder.allowVoid = true;1134 }1135 if ( castExpr->kind == ast::CastExpr::Return ) {1136 finder.strictMode = true;1137 finder.find( castExpr->arg, ResolvMode::withAdjustment() );1138 1139 // return casts are eliminated (merely selecting an overload, no actual operation)1140 candidates = std::move(finder.candidates);1141 }1142 finder.find( castExpr->arg, ResolvMode::withAdjustment() );1143 1144 if( !finder.candidates.empty() ) reason.code = NoMatch;1145 1146 CandidateList matches;1147 Cost minExprCost = Cost::infinity;1148 Cost minCastCost = Cost::infinity;1149 for ( CandidateRef & cand : finder.candidates ) {1150 ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have;1151 ast::OpenVarSet open( cand->open );1152 1153 cand->env.extractOpenVars( open );1154 1155 // It is possible that a cast can throw away some values in a multiply-valued1156 // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of the1157 // subexpression results that are cast directly. The candidate is invalid if it1158 // has fewer results than there are types to cast to.1159 int discardedValues = cand->expr->result->size() - toType->size();1160 if ( discardedValues < 0 ) continue;1161 1162 // unification run for side-effects1163 unify( toType, cand->expr->result, cand->env, need, have, open );1164 Cost thisCost =1165 (castExpr->isGenerated == ast::GeneratedFlag::GeneratedCast)1166 ? conversionCost( cand->expr->result, toType, cand->expr->get_lvalue(), symtab, cand->env )1167 : castCost( cand->expr->result, toType, cand->expr->get_lvalue(), symtab, cand->env );1168 1169 PRINT(1170 std::cerr << "working on cast with result: " << toType << std::endl;1171 std::cerr << "and expr type: " << cand->expr->result << std::endl;1172 std::cerr << "env: " << cand->env << std::endl;1173 )1174 if ( thisCost != Cost::infinity ) {1175 PRINT(1176 std::cerr << "has finite cost." << std::endl;1177 )1178 // count one safe conversion for each value that is thrown away1179 thisCost.incSafe( discardedValues );1180 // select first on argument cost, then conversion cost1181 if (cand->cost < minExprCost || cand->cost == minExprCost && thisCost < minCastCost) {1182 minExprCost = cand->cost;1183 minCastCost = thisCost;1184 matches.clear();1185 1186 1187 }1188 // ambiguous case, still output candidates to print in error message1189 if (cand->cost == minExprCost && thisCost == minCastCost) {1190 CandidateRef newCand = std::make_shared<Candidate>(1191 restructureCast( cand->expr, toType, castExpr->isGenerated ),1192 copy( cand->env ), std::move( open ), std::move( need ), cand->cost + thisCost);1193 // currently assertions are always resolved immediately so this should have no effect.1194 // if this somehow changes in the future (e.g. delayed by indeterminate return type)1195 // we may need to revisit the logic.1196 inferParameters( newCand, matches );1197 }1198 // else skip, better alternatives found1199 1200 }1201 }1202 candidates = std::move(matches);1203 1204 //CandidateList minArgCost = findMinCost( matches );1205 //promoteCvtCost( minArgCost );1206 //candidates = findMinCost( minArgCost );1207 }1208 1209 void postvisit( const ast::VirtualCastExpr * castExpr ) {1210 assertf( castExpr->result, "Implicit virtual cast targets not yet supported." );1211 CandidateFinder finder( context, tenv );1212 // don't prune here, all alternatives guaranteed to have same type1213 finder.find( castExpr->arg, ResolvMode::withoutPrune() );1214 for ( CandidateRef & r : finder.candidates ) {1215 addCandidate(1216 *r,1217 new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } );1218 }1219 }1220 1221 void postvisit( const ast::KeywordCastExpr * castExpr ) {1222 const auto & loc = castExpr->location;1223 assertf( castExpr->result, "Cast target should have been set in Validate." );1224 auto ref = castExpr->result.strict_as<ast::ReferenceType>();1225 auto inst = ref->base.strict_as<ast::StructInstType>();1226 auto target = inst->base.get();1227 1228 CandidateFinder finder( context, tenv );1229 1230 auto pick_alternatives = [target, this](CandidateList & found, bool expect_ref) {1231 for(auto & cand : found) {1232 const ast::Type * expr = cand->expr->result.get();1233 if(expect_ref) {1234 auto res = dynamic_cast<const ast::ReferenceType*>(expr);1235 if(!res) { continue; }1236 expr = res->base.get();1237 }1238 1239 if(auto insttype = dynamic_cast<const ast::TypeInstType*>(expr)) {1240 auto td = cand->env.lookup(*insttype);1241 if(!td) { continue; }1242 expr = td->bound.get();1243 }1244 1245 if(auto base = dynamic_cast<const ast::StructInstType*>(expr)) {1246 if(base->base == target) {1247 candidates.push_back( std::move(cand) );1248 reason.code = NoReason;1249 }1250 }1251 }1252 };1253 1254 try {1255 // Attempt 1 : turn (thread&)X into (thread$&)X.__thrd1256 // Clone is purely for memory management1257 std::unique_ptr<const ast::Expr> tech1 { new ast::UntypedMemberExpr(loc, new ast::NameExpr(loc, castExpr->concrete_target.field), castExpr->arg) };1258 1259 // don't prune here, since it's guaranteed all alternatives will have the same type1260 finder.find( tech1.get(), ResolvMode::withoutPrune() );1261 pick_alternatives(finder.candidates, false);1262 1263 return;1264 } catch(SemanticErrorException & ) {}1265 1266 // Fallback : turn (thread&)X into (thread$&)get_thread(X)1267 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 })) };1268 // don't prune here, since it's guaranteed all alternatives will have the same type1269 finder.find( fallback.get(), ResolvMode::withoutPrune() );1270 1271 pick_alternatives(finder.candidates, true);1272 1273 // Whatever happens here, we have no more fallbacks1274 }1275 1276 void postvisit( const ast::UntypedMemberExpr * memberExpr ) {1277 CandidateFinder aggFinder( context, tenv );1278 aggFinder.find( memberExpr->aggregate, ResolvMode::withAdjustment() );1279 for ( CandidateRef & agg : aggFinder.candidates ) {1280 // it's okay for the aggregate expression to have reference type -- cast it to the1281 // base type to treat the aggregate as the referenced value1282 Cost addedCost = Cost::zero;1283 agg->expr = referenceToRvalueConversion( agg->expr, addedCost );1284 1285 // find member of the given type1286 if ( auto structInst = agg->expr->result.as< ast::StructInstType >() ) {1287 addAggMembers(1288 structInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) );1289 } else if ( auto unionInst = agg->expr->result.as< ast::UnionInstType >() ) {1290 addAggMembers(1291 unionInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) );1292 } else if ( auto tupleType = agg->expr->result.as< ast::TupleType >() ) {1293 addTupleMembers( tupleType, agg->expr, *agg, addedCost, memberExpr->member );1294 }1295 }1296 }1297 1298 void postvisit( const ast::MemberExpr * memberExpr ) {1299 addCandidate( memberExpr, tenv );1300 }1301 1302 void postvisit( const ast::NameExpr * nameExpr ) {1303 std::vector< ast::SymbolTable::IdData > declList;1304 if (!selfFinder.otypeKeys.empty()) {1305 auto kind = ast::SymbolTable::getSpecialFunctionKind(nameExpr->name);1306 assertf(kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS, "special lookup with non-special target: %s", nameExpr->name.c_str());1307 1308 for (auto & otypeKey: selfFinder.otypeKeys) {1309 auto result = symtab.specialLookupId(kind, otypeKey);1310 declList.insert(declList.end(), std::make_move_iterator(result.begin()), std::make_move_iterator(result.end()));1311 }1312 }1313 else {1314 declList = symtab.lookupId( nameExpr->name );1315 }1316 PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; )1317 1318 if( declList.empty() ) return;1319 1320 reason.code = NoMatch;1321 1322 for ( auto & data : declList ) {1323 Cost cost = Cost::zero;1324 ast::Expr * newExpr = data.combine( nameExpr->location, cost );1325 1326 CandidateRef newCand = std::make_shared<Candidate>(1327 newExpr, copy( tenv ), ast::OpenVarSet{}, ast::AssertionSet{}, cost );1328 1329 if (newCand->expr->env) {1330 newCand->env.add(*newCand->expr->env);1331 auto mutExpr = newCand->expr.get_and_mutate();1332 mutExpr->env = nullptr;1333 newCand->expr = mutExpr;1334 }1335 1336 PRINT(1337 std::cerr << "decl is ";1338 ast::print( std::cerr, data.id );1339 std::cerr << std::endl;1340 std::cerr << "newExpr is ";1341 ast::print( std::cerr, newExpr );1342 std::cerr << std::endl;1343 )1344 newCand->expr = ast::mutate_field(1345 newCand->expr.get(), &ast::Expr::result,1346 renameTyVars( newCand->expr->result ) );1347 // add anonymous member interpretations whenever an aggregate value type is seen1348 // as a name expression1349 addAnonConversions( newCand );1350 candidates.emplace_back( std::move( newCand ) );1351 }1352 }1353 1354 void postvisit( const ast::VariableExpr * variableExpr ) {1355 // not sufficient to just pass `variableExpr` here, type might have changed since1356 // creation1357 addCandidate(1358 new ast::VariableExpr{ variableExpr->location, variableExpr->var }, tenv );1359 }1360 1361 void postvisit( const ast::ConstantExpr * constantExpr ) {1362 addCandidate( constantExpr, tenv );1363 }1364 1365 void postvisit( const ast::SizeofExpr * sizeofExpr ) {1366 if ( sizeofExpr->type ) {1367 addCandidate(1368 new ast::SizeofExpr{1369 sizeofExpr->location, resolveTypeof( sizeofExpr->type, context ) },1370 tenv );1371 } else {1372 // find all candidates for the argument to sizeof1373 CandidateFinder finder( context, tenv );1374 finder.find( sizeofExpr->expr );1375 // find the lowest-cost candidate, otherwise ambiguous1376 CandidateList winners = findMinCost( finder.candidates );1377 if ( winners.size() != 1 ) {1378 SemanticError(1379 sizeofExpr->expr.get(), "Ambiguous expression in sizeof operand: " );1380 }1381 // return the lowest-cost candidate1382 CandidateRef & choice = winners.front();1383 choice->expr = referenceToRvalueConversion( choice->expr, choice->cost );1384 choice->cost = Cost::zero;1385 addCandidate( *choice, new ast::SizeofExpr{ sizeofExpr->location, choice->expr } );1386 }1387 }1388 1389 void postvisit( const ast::AlignofExpr * alignofExpr ) {1390 if ( alignofExpr->type ) {1391 addCandidate(1392 new ast::AlignofExpr{1393 alignofExpr->location, resolveTypeof( alignofExpr->type, context ) },1394 tenv );1395 } else {1396 // find all candidates for the argument to alignof1397 CandidateFinder finder( context, tenv );1398 finder.find( alignofExpr->expr );1399 // find the lowest-cost candidate, otherwise ambiguous1400 CandidateList winners = findMinCost( finder.candidates );1401 if ( winners.size() != 1 ) {1402 SemanticError(1403 alignofExpr->expr.get(), "Ambiguous expression in alignof operand: " );1404 }1405 // return the lowest-cost candidate1406 CandidateRef & choice = winners.front();1407 choice->expr = referenceToRvalueConversion( choice->expr, choice->cost );1408 choice->cost = Cost::zero;1409 addCandidate(1410 *choice, new ast::AlignofExpr{ alignofExpr->location, choice->expr } );1411 }1412 }1413 1414 void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) {1415 const ast::BaseInstType * aggInst;1416 if (( aggInst = offsetofExpr->type.as< ast::StructInstType >() )) ;1417 else if (( aggInst = offsetofExpr->type.as< ast::UnionInstType >() )) ;1418 else return;1419 1420 for ( const ast::Decl * member : aggInst->lookup( offsetofExpr->member ) ) {1421 auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( member );1422 addCandidate(1423 new ast::OffsetofExpr{ offsetofExpr->location, aggInst, dwt }, tenv );1424 }1425 }1426 1427 void postvisit( const ast::OffsetofExpr * offsetofExpr ) {1428 addCandidate( offsetofExpr, tenv );1429 }1430 1431 void postvisit( const ast::OffsetPackExpr * offsetPackExpr ) {1432 addCandidate( offsetPackExpr, tenv );1433 }1434 1435 void postvisit( const ast::LogicalExpr * logicalExpr ) {1436 CandidateFinder finder1( context, tenv );1437 finder1.find( logicalExpr->arg1, ResolvMode::withAdjustment() );1438 if ( finder1.candidates.empty() ) return;1439 1440 CandidateFinder finder2( context, tenv );1441 finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() );1442 if ( finder2.candidates.empty() ) return;1443 1444 reason.code = NoMatch;1445 1446 for ( const CandidateRef & r1 : finder1.candidates ) {1447 for ( const CandidateRef & r2 : finder2.candidates ) {1448 ast::TypeEnvironment env{ r1->env };1449 env.simpleCombine( r2->env );1450 ast::OpenVarSet open{ r1->open };1451 mergeOpenVars( open, r2->open );1452 ast::AssertionSet need;1453 mergeAssertionSet( need, r1->need );1454 mergeAssertionSet( need, r2->need );1455 1456 addCandidate(1457 new ast::LogicalExpr{1458 logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd },1459 std::move( env ), std::move( open ), std::move( need ), r1->cost + r2->cost );1460 }1461 }1462 }1463 1464 void postvisit( const ast::ConditionalExpr * conditionalExpr ) {1465 // candidates for condition1466 CandidateFinder finder1( context, tenv );1467 finder1.find( conditionalExpr->arg1, ResolvMode::withAdjustment() );1468 if ( finder1.candidates.empty() ) return;1469 1470 // candidates for true result1471 CandidateFinder finder2( context, tenv );1472 finder2.allowVoid = true;1473 finder2.find( conditionalExpr->arg2, ResolvMode::withAdjustment() );1474 if ( finder2.candidates.empty() ) return;1475 1476 // candidates for false result1477 CandidateFinder finder3( context, tenv );1478 finder3.allowVoid = true;1479 finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() );1480 if ( finder3.candidates.empty() ) return;1481 1482 reason.code = NoMatch;1483 1484 for ( const CandidateRef & r1 : finder1.candidates ) {1485 for ( const CandidateRef & r2 : finder2.candidates ) {1486 for ( const CandidateRef & r3 : finder3.candidates ) {1487 ast::TypeEnvironment env{ r1->env };1488 env.simpleCombine( r2->env );1489 env.simpleCombine( r3->env );1490 ast::OpenVarSet open{ r1->open };1491 mergeOpenVars( open, r2->open );1492 mergeOpenVars( open, r3->open );1493 ast::AssertionSet need;1494 mergeAssertionSet( need, r1->need );1495 mergeAssertionSet( need, r2->need );1496 mergeAssertionSet( need, r3->need );1497 ast::AssertionSet have;1498 1499 // unify true and false results, then infer parameters to produce new1500 // candidates1501 ast::ptr< ast::Type > common;1502 if (1503 unify(1504 r2->expr->result, r3->expr->result, env, need, have, open,1505 common )1506 ) {1507 // generate typed expression1508 ast::ConditionalExpr * newExpr = new ast::ConditionalExpr{1509 conditionalExpr->location, r1->expr, r2->expr, r3->expr };1510 newExpr->result = common ? common : r2->expr->result;1511 // convert both options to result type1512 Cost cost = r1->cost + r2->cost + r3->cost;1513 newExpr->arg2 = computeExpressionConversionCost(1514 newExpr->arg2, newExpr->result, symtab, env, cost );1515 newExpr->arg3 = computeExpressionConversionCost(1516 newExpr->arg3, newExpr->result, symtab, env, cost );1517 // output candidate1518 CandidateRef newCand = std::make_shared<Candidate>(1519 newExpr, std::move( env ), std::move( open ), std::move( need ), cost );1520 inferParameters( newCand, candidates );1521 }1522 }1523 }1524 }1525 }1526 1527 void postvisit( const ast::CommaExpr * commaExpr ) {1528 ast::TypeEnvironment env{ tenv };1529 ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, context, env );1530 1531 CandidateFinder finder2( context, env );1532 finder2.find( commaExpr->arg2, ResolvMode::withAdjustment() );1533 1534 for ( const CandidateRef & r2 : finder2.candidates ) {1535 addCandidate( *r2, new ast::CommaExpr{ commaExpr->location, arg1, r2->expr } );1536 }1537 }1538 1539 void postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr ) {1540 addCandidate( ctorExpr, tenv );1541 }1542 1543 void postvisit( const ast::ConstructorExpr * ctorExpr ) {1544 CandidateFinder finder( context, tenv );1545 finder.allowVoid = true;1546 finder.find( ctorExpr->callExpr, ResolvMode::withoutPrune() );1547 for ( CandidateRef & r : finder.candidates ) {1548 addCandidate( *r, new ast::ConstructorExpr{ ctorExpr->location, r->expr } );1549 }1550 }1551 1552 void postvisit( const ast::RangeExpr * rangeExpr ) {1553 // resolve low and high, accept candidates where low and high types unify1554 CandidateFinder finder1( context, tenv );1555 finder1.find( rangeExpr->low, ResolvMode::withAdjustment() );1556 if ( finder1.candidates.empty() ) return;1557 1558 CandidateFinder finder2( context, tenv );1559 finder2.find( rangeExpr->high, ResolvMode::withAdjustment() );1560 if ( finder2.candidates.empty() ) return;1561 1562 reason.code = NoMatch;1563 1564 for ( const CandidateRef & r1 : finder1.candidates ) {1565 for ( const CandidateRef & r2 : finder2.candidates ) {1566 ast::TypeEnvironment env{ r1->env };1567 env.simpleCombine( r2->env );1568 ast::OpenVarSet open{ r1->open };1569 mergeOpenVars( open, r2->open );1570 ast::AssertionSet need;1571 mergeAssertionSet( need, r1->need );1572 mergeAssertionSet( need, r2->need );1573 ast::AssertionSet have;1574 1575 ast::ptr< ast::Type > common;1576 if (1577 unify(1578 r1->expr->result, r2->expr->result, env, need, have, open,1579 common )1580 ) {1581 // generate new expression1582 ast::RangeExpr * newExpr =1583 new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr };1584 newExpr->result = common ? common : r1->expr->result;1585 // add candidate1586 CandidateRef newCand = std::make_shared<Candidate>(1587 newExpr, std::move( env ), std::move( open ), std::move( need ),1588 r1->cost + r2->cost );1589 inferParameters( newCand, candidates );1590 }1591 }1592 }1593 }1594 1595 void postvisit( const ast::UntypedTupleExpr * tupleExpr ) {1596 std::vector< CandidateFinder > subCandidates =1597 selfFinder.findSubExprs( tupleExpr->exprs );1598 std::vector< CandidateList > possibilities;1599 combos( subCandidates.begin(), subCandidates.end(), back_inserter( possibilities ) );1600 1601 for ( const CandidateList & subs : possibilities ) {1602 std::vector< ast::ptr< ast::Expr > > exprs;1603 exprs.reserve( subs.size() );1604 for ( const CandidateRef & sub : subs ) { exprs.emplace_back( sub->expr ); }1605 1606 ast::TypeEnvironment env;1607 ast::OpenVarSet open;1608 ast::AssertionSet need;1609 for ( const CandidateRef & sub : subs ) {1610 env.simpleCombine( sub->env );1611 mergeOpenVars( open, sub->open );1612 mergeAssertionSet( need, sub->need );1613 }1614 1615 addCandidate(1616 new ast::TupleExpr{ tupleExpr->location, std::move( exprs ) },1617 std::move( env ), std::move( open ), std::move( need ), sumCost( subs ) );1618 }1619 }1620 1621 void postvisit( const ast::TupleExpr * tupleExpr ) {1622 addCandidate( tupleExpr, tenv );1623 }1624 1625 void postvisit( const ast::TupleIndexExpr * tupleExpr ) {1626 addCandidate( tupleExpr, tenv );1627 }1628 1629 void postvisit( const ast::TupleAssignExpr * tupleExpr ) {1630 addCandidate( tupleExpr, tenv );1631 }1632 1633 void postvisit( const ast::UniqueExpr * unqExpr ) {1634 CandidateFinder finder( context, tenv );1635 finder.find( unqExpr->expr, ResolvMode::withAdjustment() );1636 for ( CandidateRef & r : finder.candidates ) {1637 // ensure that the the id is passed on so that the expressions are "linked"1638 addCandidate( *r, new ast::UniqueExpr{ unqExpr->location, r->expr, unqExpr->id } );1639 }1640 }1641 1642 void postvisit( const ast::StmtExpr * stmtExpr ) {1643 addCandidate( resolveStmtExpr( stmtExpr, context ), tenv );1644 }1645 1646 void postvisit( const ast::UntypedInitExpr * initExpr ) {1647 // handle each option like a cast1648 CandidateList matches;1649 PRINT(1650 std::cerr << "untyped init expr: " << initExpr << std::endl;1651 )1652 // O(n^2) checks of d-types with e-types1653 for ( const ast::InitAlternative & initAlt : initExpr->initAlts ) {1654 // calculate target type1655 const ast::Type * toType = resolveTypeof( initAlt.type, context );1656 toType = adjustExprType( toType, tenv, symtab );1657 // The call to find must occur inside this loop, otherwise polymorphic return1658 // types are not bound to the initialization type, since return type variables are1659 // only open for the duration of resolving the UntypedExpr.1660 CandidateFinder finder( context, tenv, toType );1661 finder.find( initExpr->expr, ResolvMode::withAdjustment() );1662 1663 Cost minExprCost = Cost::infinity;1664 Cost minCastCost = Cost::infinity;1665 for ( CandidateRef & cand : finder.candidates ) {1666 if(reason.code == NotFound) reason.code = NoMatch;1667 1668 ast::TypeEnvironment env{ cand->env };1669 ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have;1670 ast::OpenVarSet open{ cand->open };1671 1672 PRINT(1673 std::cerr << " @ " << toType << " " << initAlt.designation << std::endl;1674 )1675 1676 // It is possible that a cast can throw away some values in a multiply-valued1677 // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of1678 // the subexpression results that are cast directly. The candidate is invalid1679 // if it has fewer results than there are types to cast to.1680 int discardedValues = cand->expr->result->size() - toType->size();1681 if ( discardedValues < 0 ) continue;1682 1683 // unification run for side-effects1684 bool canUnify = unify( toType, cand->expr->result, env, need, have, open );1685 (void) canUnify;1686 Cost thisCost = computeConversionCost( cand->expr->result, toType, cand->expr->get_lvalue(),1687 symtab, env );1688 PRINT(1689 Cost legacyCost = castCost( cand->expr->result, toType, cand->expr->get_lvalue(),1690 symtab, env );1691 std::cerr << "Considering initialization:";1692 std::cerr << std::endl << " FROM: " << cand->expr->result << std::endl;1693 std::cerr << std::endl << " TO: " << toType << std::endl;1694 std::cerr << std::endl << " Unification " << (canUnify ? "succeeded" : "failed");1695 std::cerr << std::endl << " Legacy cost " << legacyCost;1696 std::cerr << std::endl << " New cost " << thisCost;1697 std::cerr << std::endl;1698 )1699 if ( thisCost != Cost::infinity ) {1700 // count one safe conversion for each value that is thrown away1701 thisCost.incSafe( discardedValues );1702 if (cand->cost < minExprCost || cand->cost == minExprCost && thisCost < minCastCost) {1703 minExprCost = cand->cost;1704 minCastCost = thisCost;1705 matches.clear();1706 }1707 // ambiguous case, still output candidates to print in error message1708 if (cand->cost == minExprCost && thisCost == minCastCost) {1709 CandidateRef newCand = std::make_shared<Candidate>(1710 new ast::InitExpr{1711 initExpr->location, restructureCast( cand->expr, toType ),1712 initAlt.designation },1713 std::move(env), std::move( open ), std::move( need ), cand->cost + thisCost );1714 // currently assertions are always resolved immediately so this should have no effect.1715 // if this somehow changes in the future (e.g. delayed by indeterminate return type)1716 // we may need to revisit the logic.1717 inferParameters( newCand, matches );1718 }1719 1720 }1721 1722 }1723 1724 }1725 1726 // select first on argument cost, then conversion cost1727 // CandidateList minArgCost = findMinCost( matches );1728 // promoteCvtCost( minArgCost );1729 // candidates = findMinCost( minArgCost );1730 candidates = std::move(matches);1731 }1732 1733 void postvisit( const ast::InitExpr * ) {1734 assertf( false, "CandidateFinder should never see a resolved InitExpr." );1735 }1736 1737 void postvisit( const ast::DeletedExpr * ) {1738 assertf( false, "CandidateFinder should never see a DeletedExpr." );1739 }1740 1741 void postvisit( const ast::GenericExpr * ) {1742 assertf( false, "_Generic is not yet supported." );1743 }1744 };1745 1746 // size_t Finder::traceId = Stats::Heap::new_stacktrace_id("Finder");1747 /// Prunes a list of candidates down to those that have the minimum conversion cost for a given1748 /// return type. Skips ambiguous candidates.1749 1750 } // anonymous namespace1751 1752 bool CandidateFinder::pruneCandidates( CandidateList & candidates, CandidateList & out, std::vector<std::string> & errors ) {1753 struct PruneStruct {1754 CandidateRef candidate;1755 bool ambiguous;1756 1757 PruneStruct() = default;1758 PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {}1759 };1760 1761 // find lowest-cost candidate for each type1762 std::unordered_map< std::string, PruneStruct > selected;1763 // attempt to skip satisfyAssertions on more expensive alternatives if better options have been found1764 std::sort(candidates.begin(), candidates.end(), [](const CandidateRef & x, const CandidateRef & y){return x->cost < y->cost;});1765 for ( CandidateRef & candidate : candidates ) {1766 std::string mangleName;1767 {1768 ast::ptr< ast::Type > newType = candidate->expr->result;1769 assertf(candidate->expr->result, "Result of expression %p for candidate is null", candidate->expr.get());1770 candidate->env.apply( newType );1771 mangleName = Mangle::mangle( newType );1772 }1773 1774 auto found = selected.find( mangleName );1775 if (found != selected.end() && found->second.candidate->cost < candidate->cost) {1776 PRINT(1777 std::cerr << "cost " << candidate->cost << " loses to "1778 << found->second.candidate->cost << std::endl;1779 )1780 continue;1781 }1782 1783 // xxx - when do satisfyAssertions produce more than 1 result?1784 // this should only happen when initial result type contains1785 // unbound type parameters, then it should never be pruned by1786 // the previous step, since renameTyVars guarantees the mangled name1787 // is unique.1788 CandidateList satisfied;1789 bool needRecomputeKey = false;1790 if (candidate->need.empty()) {1791 satisfied.emplace_back(candidate);1792 }1793 else {1794 satisfyAssertions(candidate, context.symtab, satisfied, errors);1795 needRecomputeKey = true;1796 }1797 1798 for (auto & newCand : satisfied) {1799 // recomputes type key, if satisfyAssertions changed it1800 if (needRecomputeKey)1801 {1802 ast::ptr< ast::Type > newType = newCand->expr->result;1803 assertf(newCand->expr->result, "Result of expression %p for candidate is null", newCand->expr.get());1804 newCand->env.apply( newType );1805 mangleName = Mangle::mangle( newType );1806 }1807 auto found = selected.find( mangleName );1808 if ( found != selected.end() ) {1809 // tiebreaking by picking the lower cost on CURRENT expression1810 // NOTE: this behavior is different from C semantics.1811 // Specific remediations are performed for C operators at postvisit(UntypedExpr).1812 // Further investigations may take place.1813 if ( newCand->cost < found->second.candidate->cost1814 || (newCand->cost == found->second.candidate->cost && newCand->cvtCost < found->second.candidate->cvtCost) ) {1815 PRINT(1816 std::cerr << "cost " << newCand->cost << " beats "1817 << found->second.candidate->cost << std::endl;1818 )1819 1820 found->second = PruneStruct{ newCand };1821 } else if ( newCand->cost == found->second.candidate->cost && newCand->cvtCost == found->second.candidate->cvtCost) {1822 // if one of the candidates contains a deleted identifier, can pick the other,1823 // since deleted expressions should not be ambiguous if there is another option1824 // that is at least as good1825 if ( findDeletedExpr( newCand->expr ) ) {1826 // do nothing1827 PRINT( std::cerr << "candidate is deleted" << std::endl; )1828 } else if ( findDeletedExpr( found->second.candidate->expr ) ) {1829 PRINT( std::cerr << "current is deleted" << std::endl; )1830 found->second = PruneStruct{ newCand };1831 } else {1832 PRINT( std::cerr << "marking ambiguous" << std::endl; )1833 found->second.ambiguous = true;1834 }1835 } else {1836 // xxx - can satisfyAssertions increase the cost?1837 PRINT(1838 std::cerr << "cost " << newCand->cost << " loses to "1839 << found->second.candidate->cost << std::endl;1840 )1841 }1842 } else {1843 selected.emplace_hint( found, mangleName, newCand );1844 }1845 }1846 }1847 1848 // report unambiguous min-cost candidates1849 // CandidateList out;1850 for ( auto & target : selected ) {1851 if ( target.second.ambiguous ) continue;1852 1853 CandidateRef cand = target.second.candidate;1854 1855 ast::ptr< ast::Type > newResult = cand->expr->result;1856 cand->env.applyFree( newResult );1857 cand->expr = ast::mutate_field(1858 cand->expr.get(), &ast::Expr::result, std::move( newResult ) );1859 1860 out.emplace_back( cand );1861 }1862 // if everything is lost in satisfyAssertions, report the error1863 return !selected.empty();1864 }1865 1866 void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) {1867 // Find alternatives for expression1868 ast::Pass<Finder> finder{ *this };1869 expr->accept( finder );1870 1871 if ( mode.failFast && candidates.empty() ) {1872 switch(finder.core.reason.code) {1873 case Finder::NotFound:1874 { SemanticError( expr, "No alternatives for expression " ); break; }1875 case Finder::NoMatch:1876 { SemanticError( expr, "Invalid application of existing declaration(s) in expression " ); break; }1877 case Finder::ArgsToFew:1878 case Finder::ArgsToMany:1879 case Finder::RetsToFew:1880 case Finder::RetsToMany:1881 case Finder::NoReason:1882 default:1883 { SemanticError( expr->location, "No reasonable alternatives for expression : reasons unkown" ); }1884 }1885 }1886 1887 /*1888 if ( mode.satisfyAssns || mode.prune ) {1889 // trim candidates to just those where the assertions are satisfiable1890 // - necessary pre-requisite to pruning1891 CandidateList satisfied;1892 std::vector< std::string > errors;1893 for ( CandidateRef & candidate : candidates ) {1894 satisfyAssertions( candidate, localSyms, satisfied, errors );1895 }1896 1897 // fail early if none such1898 if ( mode.failFast && satisfied.empty() ) {1899 std::ostringstream stream;1900 stream << "No alternatives with satisfiable assertions for " << expr << "\n";1901 for ( const auto& err : errors ) {1902 stream << err;1903 }1904 SemanticError( expr->location, stream.str() );1905 }1906 1907 // reset candidates1908 candidates = move( satisfied );1909 }1910 */1911 1912 // if ( mode.prune ) {1913 // optimization: don't prune for NameExpr since it never has cost1914 if ( mode.prune && !dynamic_cast<const ast::NameExpr *>(expr)) {1915 // trim candidates to single best one1916 PRINT(1917 std::cerr << "alternatives before prune:" << std::endl;1918 print( std::cerr, candidates );1919 )1920 1921 CandidateList pruned;1922 std::vector<std::string> errors;1923 bool found = pruneCandidates( candidates, pruned, errors );1924 1925 if ( mode.failFast && pruned.empty() ) {1926 std::ostringstream stream;1927 if (found) {1928 CandidateList winners = findMinCost( candidates );1929 stream << "Cannot choose between " << winners.size() << " alternatives for "1930 "expression\n";1931 ast::print( stream, expr );1932 stream << " Alternatives are:\n";1933 print( stream, winners, 1 );1934 SemanticError( expr->location, stream.str() );1935 }1936 else {1937 stream << "No alternatives with satisfiable assertions for " << expr << "\n";1938 for ( const auto& err : errors ) {1939 stream << err;1940 }1941 SemanticError( expr->location, stream.str() );1942 }1943 }1944 1945 auto oldsize = candidates.size();1946 candidates = std::move( pruned );1947 1948 PRINT(1949 std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;1950 )1951 PRINT(1952 std::cerr << "there are " << candidates.size() << " alternatives after elimination"1953 << std::endl;1954 )1955 }1956 1957 // adjust types after pruning so that types substituted by pruneAlternatives are correctly1958 // adjusted1959 if ( mode.adjust ) {1960 for ( CandidateRef & r : candidates ) {1961 r->expr = ast::mutate_field(1962 r->expr.get(), &ast::Expr::result,1963 adjustExprType( r->expr->result, r->env, context.symtab ) );1964 }1965 }1966 1967 // Central location to handle gcc extension keyword, etc. for all expressions1968 for ( CandidateRef & r : candidates ) {1969 if ( r->expr->extension != expr->extension ) {1970 r->expr.get_and_mutate()->extension = expr->extension;1971 }1972 }1973 }1974 1975 std::vector< CandidateFinder > CandidateFinder::findSubExprs(1976 const std::vector< ast::ptr< ast::Expr > > & xs1977 ) {1978 std::vector< CandidateFinder > out;1979 1980 for ( const auto & x : xs ) {1981 out.emplace_back( context, env );1982 out.back().find( x, ResolvMode::withAdjustment() );1983 1984 PRINT(1985 std::cerr << "findSubExprs" << std::endl;1986 print( std::cerr, out.back().candidates );1987 )1988 }1989 1990 return out;1991 }1992 1993 2054 } // namespace ResolvExpr 1994 2055 -
src/Validate/Autogen.cpp
r77fd9fe2 r0e0f25d5 321 321 void FuncGenerator::produceDecl( const ast::FunctionDecl * decl ) { 322 322 assert( nullptr != decl->stmts ); 323 const auto & oldParams = getGenericParams(type); 324 assert( decl->type_params.size() == oldParams.size()); 325 326 /* 327 ast::DeclReplacer::TypeMap typeMap; 328 for (auto it = oldParams.begin(), jt = decl->type_params.begin(); it != oldParams.end(); ++it, ++jt) { 329 typeMap.emplace(*it, *jt); 330 } 331 332 const ast::FunctionDecl * mut = strict_dynamic_cast<const ast::FunctionDecl *>(ast::DeclReplacer::replace(decl, typeMap)); 333 assert (mut == decl); 334 */ 323 assert( decl->type_params.size() == getGenericParams( type ).size() ); 335 324 336 325 definitions.push_back( decl ); … … 364 353 std::vector<ast::ptr<ast::TypeDecl>> type_params; 365 354 std::vector<ast::ptr<ast::DeclWithType>> assertions; 366 367 ast::DeclReplacer::TypeMap typeMap;368 355 for ( auto & old_param : old_type_params ) { 369 356 ast::TypeDecl * decl = ast::deepCopy( old_param ); 370 357 decl->init = nullptr; 371 358 splice( assertions, decl->assertions ); 372 oldToNew.emplace( std::make_pair( old_param, decl ));359 oldToNew.emplace( old_param, decl ); 373 360 type_params.push_back( decl ); 374 typeMap.emplace(old_param, decl);375 }376 377 for (auto & param : params) {378 param = ast::DeclReplacer::replace(param, typeMap);379 }380 for (auto & param : returns) {381 param = ast::DeclReplacer::replace(param, typeMap);382 361 } 383 362 replaceAll( params, oldToNew );
Note: See TracChangeset
for help on using the changeset viewer.