Changeset 3c6e417 for src/ResolvExpr/CandidateFinder.cpp
- Timestamp:
- Jun 20, 2019, 1:45:01 PM (5 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 54dd994
- Parents:
- 1e5dedc4 (diff), c0f9efe (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)
links above to see all the changes relative to each parent. - File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/CandidateFinder.cpp
r1e5dedc4 r3c6e417 27 27 #include "Cost.h" 28 28 #include "ExplodedArg.hpp" 29 #include "RenameVars.h" // for renameTyVars 29 30 #include "Resolver.h" 31 #include "ResolveTypeof.h" 30 32 #include "SatisfyAssertions.hpp" 31 #include "typeops.h" // for adjustExprType 33 #include "typeops.h" // for adjustExprType, conversionCost, polyCost, specCost 32 34 #include "Unify.h" 33 35 #include "AST/Expr.hpp" … … 38 40 #include "AST/Type.hpp" 39 41 #include "SymTab/Mangler.h" 42 #include "SymTab/Validate.h" // for validateType 40 43 #include "Tuples/Tuples.h" // for handleTupleAssignment 41 44 … … 44 47 namespace ResolvExpr { 45 48 49 using std::move; 50 51 /// partner to move that copies any copyable type 52 template<typename T> 53 T copy( const T & x ) { return x; } 54 55 const ast::Expr * referenceToRvalueConversion( const ast::Expr * expr, Cost & cost ) { 56 if ( expr->result.as< ast::ReferenceType >() ) { 57 // cast away reference from expr 58 cost.incReference(); 59 return new ast::CastExpr{ expr->location, expr, expr->result->stripReferences() }; 60 } 61 62 return expr; 63 } 64 65 /// Unique identifier for matching expression resolutions to their requesting expression 66 UniqueId globalResnSlot = 0; 67 68 Cost computeConversionCost( 69 const ast::Type * argType, const ast::Type * paramType, const ast::SymbolTable & symtab, 70 const ast::TypeEnvironment & env 71 ) { 72 PRINT( 73 std::cerr << std::endl << "converting "; 74 ast::print( std::cerr, argType, 2 ); 75 std::cerr << std::endl << " to "; 76 ast::print( std::cerr, paramType, 2 ); 77 std::cerr << std::endl << "environment is: "; 78 ast::print( std::cerr, env, 2 ); 79 std::cerr << std::endl; 80 ) 81 Cost convCost = conversionCost( argType, paramType, symtab, env ); 82 PRINT( 83 std::cerr << std::endl << "cost is " << convCost << std::endl; 84 ) 85 if ( convCost == Cost::infinity ) return convCost; 86 convCost.incPoly( polyCost( paramType, symtab, env ) + polyCost( argType, symtab, env ) ); 87 PRINT( 88 std::cerr << "cost with polycost is " << convCost << std::endl; 89 ) 90 return convCost; 91 } 92 46 93 namespace { 47 48 94 /// First index is which argument, second is which alternative, third is which exploded element 49 95 using ExplodedArgs_new = std::deque< std::vector< ExplodedArg > >; … … 65 111 } 66 112 113 /// Computes conversion cost for a given expression to a given type 114 const ast::Expr * computeExpressionConversionCost( 115 const ast::Expr * arg, const ast::Type * paramType, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env, Cost & outCost 116 ) { 117 Cost convCost = computeConversionCost( arg->result, paramType, symtab, env ); 118 outCost += convCost; 119 120 // If there is a non-zero conversion cost, ignoring poly cost, then the expression requires 121 // conversion. Ignore poly cost for now, since this requires resolution of the cast to 122 // infer parameters and this does not currently work for the reason stated below 123 Cost tmpCost = convCost; 124 tmpCost.incPoly( -tmpCost.get_polyCost() ); 125 if ( tmpCost != Cost::zero ) { 126 ast::ptr< ast::Type > newType = paramType; 127 env.apply( newType ); 128 return new ast::CastExpr{ arg->location, arg, newType }; 129 130 // xxx - *should* be able to resolve this cast, but at the moment pointers are not 131 // castable to zero_t, but are implicitly convertible. This is clearly inconsistent, 132 // once this is fixed it should be possible to resolve the cast. 133 // xxx - this isn't working, it appears because type1 (parameter) is seen as widenable, 134 // but it shouldn't be because this makes the conversion from DT* to DT* since 135 // commontype(zero_t, DT*) is DT*, rather than nothing 136 137 // CandidateFinder finder{ symtab, env }; 138 // finder.find( arg, ResolvMode::withAdjustment() ); 139 // assertf( finder.candidates.size() > 0, 140 // "Somehow castable expression failed to find alternatives." ); 141 // assertf( finder.candidates.size() == 1, 142 // "Somehow got multiple alternatives for known cast expression." ); 143 // return finder.candidates.front()->expr; 144 } 145 146 return arg; 147 } 148 67 149 /// Computes conversion cost for a given candidate 68 150 Cost computeApplicationConversionCost( 69 const CandidateRef &cand, const ast::SymbolTable & symtab151 CandidateRef cand, const ast::SymbolTable & symtab 70 152 ) { 71 #warning unimplemented 72 (void)cand; (void)symtab; 73 assert(false); 74 return Cost::infinity; 153 auto appExpr = cand->expr.strict_as< ast::ApplicationExpr >(); 154 auto pointer = appExpr->func->result.strict_as< ast::PointerType >(); 155 auto function = pointer->base.strict_as< ast::FunctionType >(); 156 157 Cost convCost = Cost::zero; 158 const auto & params = function->params; 159 auto param = params.begin(); 160 auto & args = appExpr->args; 161 162 for ( unsigned i = 0; i < args.size(); ++i ) { 163 const ast::Type * argType = args[i]->result; 164 PRINT( 165 std::cerr << "arg expression:" << std::endl; 166 ast::print( std::cerr, args[i], 2 ); 167 std::cerr << "--- results are" << std::endl; 168 ast::print( std::cerr, argType, 2 ); 169 ) 170 171 if ( param == params.end() ) { 172 if ( function->isVarArgs ) { 173 convCost.incUnsafe(); 174 PRINT( std::cerr << "end of params with varargs function: inc unsafe: " 175 << convCost << std::endl; ; ) 176 // convert reference-typed expressions into value-typed expressions 177 cand->expr = ast::mutate_field_index( 178 appExpr, &ast::ApplicationExpr::args, i, 179 referenceToRvalueConversion( args[i], convCost ) ); 180 continue; 181 } else return Cost::infinity; 182 } 183 184 if ( auto def = args[i].as< ast::DefaultArgExpr >() ) { 185 // Default arguments should be free - don't include conversion cost. 186 // Unwrap them here because they are not relevant to the rest of the system 187 cand->expr = ast::mutate_field_index( 188 appExpr, &ast::ApplicationExpr::args, i, def->expr ); 189 ++param; 190 continue; 191 } 192 193 // mark conversion cost and also specialization cost of param type 194 const ast::Type * paramType = (*param)->get_type(); 195 cand->expr = ast::mutate_field_index( 196 appExpr, &ast::ApplicationExpr::args, i, 197 computeExpressionConversionCost( 198 args[i], paramType, symtab, cand->env, convCost ) ); 199 convCost.decSpec( specCost( paramType ) ); 200 ++param; // can't be in for-loop update because of the continue 201 } 202 203 if ( param != params.end() ) return Cost::infinity; 204 205 // specialization cost of return types can't be accounted for directly, it disables 206 // otherwise-identical calls, like this example based on auto-newline in the I/O lib: 207 // 208 // forall(otype OS) { 209 // void ?|?(OS&, int); // with newline 210 // OS& ?|?(OS&, int); // no newline, always chosen due to more specialization 211 // } 212 213 // mark type variable and specialization cost of forall clause 214 convCost.incVar( function->forall.size() ); 215 for ( const ast::TypeDecl * td : function->forall ) { 216 convCost.decSpec( td->assertions.size() ); 217 } 218 219 return convCost; 220 } 221 222 void makeUnifiableVars( 223 const ast::ParameterizedType * type, ast::OpenVarSet & unifiableVars, 224 ast::AssertionSet & need 225 ) { 226 for ( const ast::TypeDecl * tyvar : type->forall ) { 227 unifiableVars[ tyvar->name ] = ast::TypeDecl::Data{ tyvar }; 228 for ( const ast::DeclWithType * assn : tyvar->assertions ) { 229 need[ assn ].isUsed = true; 230 } 231 } 232 } 233 234 /// Gets a default value from an initializer, nullptr if not present 235 const ast::ConstantExpr * getDefaultValue( const ast::Init * init ) { 236 if ( auto si = dynamic_cast< const ast::SingleInit * >( init ) ) { 237 if ( auto ce = si->value.as< ast::CastExpr >() ) { 238 return ce->arg.as< ast::ConstantExpr >(); 239 } else { 240 return si->value.as< ast::ConstantExpr >(); 241 } 242 } 243 return nullptr; 244 } 245 246 /// State to iteratively build a match of parameter expressions to arguments 247 struct ArgPack { 248 std::size_t parent; ///< Index of parent pack 249 ast::ptr< ast::Expr > expr; ///< The argument stored here 250 Cost cost; ///< The cost of this argument 251 ast::TypeEnvironment env; ///< Environment for this pack 252 ast::AssertionSet need; ///< Assertions outstanding for this pack 253 ast::AssertionSet have; ///< Assertions found for this pack 254 ast::OpenVarSet open; ///< Open variables for this pack 255 unsigned nextArg; ///< Index of next argument in arguments list 256 unsigned tupleStart; ///< Number of tuples that start at this index 257 unsigned nextExpl; ///< Index of next exploded element 258 unsigned explAlt; ///< Index of alternative for nextExpl > 0 259 260 ArgPack() 261 : parent( 0 ), expr(), cost( Cost::zero ), env(), need(), have(), open(), nextArg( 0 ), 262 tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {} 263 264 ArgPack( 265 const ast::TypeEnvironment & env, const ast::AssertionSet & need, 266 const ast::AssertionSet & have, const ast::OpenVarSet & open ) 267 : parent( 0 ), expr(), cost( Cost::zero ), env( env ), need( need ), have( have ), 268 open( open ), nextArg( 0 ), tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {} 269 270 ArgPack( 271 std::size_t parent, const ast::Expr * expr, ast::TypeEnvironment && env, 272 ast::AssertionSet && need, ast::AssertionSet && have, ast::OpenVarSet && open, 273 unsigned nextArg, unsigned tupleStart = 0, Cost cost = Cost::zero, 274 unsigned nextExpl = 0, unsigned explAlt = 0 ) 275 : parent(parent), expr( expr ), cost( cost ), env( move( env ) ), need( move( need ) ), 276 have( move( have ) ), open( move( open ) ), nextArg( nextArg ), tupleStart( tupleStart ), 277 nextExpl( nextExpl ), explAlt( explAlt ) {} 278 279 ArgPack( 280 const ArgPack & o, ast::TypeEnvironment && env, ast::AssertionSet && need, 281 ast::AssertionSet && have, ast::OpenVarSet && open, unsigned nextArg, Cost added ) 282 : parent( o.parent ), expr( o.expr ), cost( o.cost + added ), env( move( env ) ), 283 need( move( need ) ), have( move( have ) ), open( move( open ) ), nextArg( nextArg ), 284 tupleStart( o.tupleStart ), nextExpl( 0 ), explAlt( 0 ) {} 285 286 /// true if this pack is in the middle of an exploded argument 287 bool hasExpl() const { return nextExpl > 0; } 288 289 /// Gets the list of exploded candidates for this pack 290 const ExplodedArg & getExpl( const ExplodedArgs_new & args ) const { 291 return args[ nextArg-1 ][ explAlt ]; 292 } 293 294 /// Ends a tuple expression, consolidating the appropriate args 295 void endTuple( const std::vector< ArgPack > & packs ) { 296 // add all expressions in tuple to list, summing cost 297 std::deque< const ast::Expr * > exprs; 298 const ArgPack * pack = this; 299 if ( expr ) { exprs.emplace_front( expr ); } 300 while ( pack->tupleStart == 0 ) { 301 pack = &packs[pack->parent]; 302 exprs.emplace_front( pack->expr ); 303 cost += pack->cost; 304 } 305 // reset pack to appropriate tuple 306 std::vector< ast::ptr< ast::Expr > > exprv( exprs.begin(), exprs.end() ); 307 expr = new ast::TupleExpr{ expr->location, move( exprv ) }; 308 tupleStart = pack->tupleStart - 1; 309 parent = pack->parent; 310 } 311 }; 312 313 /// Instantiates an argument to match a parameter, returns false if no matching results left 314 bool instantiateArgument( 315 const ast::Type * paramType, const ast::Init * init, const ExplodedArgs_new & args, 316 std::vector< ArgPack > & results, std::size_t & genStart, const ast::SymbolTable & symtab, 317 unsigned nTuples = 0 318 ) { 319 if ( auto tupleType = dynamic_cast< const ast::TupleType * >( paramType ) ) { 320 // paramType is a TupleType -- group args into a TupleExpr 321 ++nTuples; 322 for ( const ast::Type * type : *tupleType ) { 323 // xxx - dropping initializer changes behaviour from previous, but seems correct 324 // ^^^ need to handle the case where a tuple has a default argument 325 if ( ! instantiateArgument( 326 type, nullptr, args, results, genStart, symtab, nTuples ) ) return false; 327 nTuples = 0; 328 } 329 // re-constitute tuples for final generation 330 for ( auto i = genStart; i < results.size(); ++i ) { 331 results[i].endTuple( results ); 332 } 333 return true; 334 } else if ( const ast::TypeInstType * ttype = Tuples::isTtype( paramType ) ) { 335 // paramType is a ttype, consumes all remaining arguments 336 337 // completed tuples; will be spliced to end of results to finish 338 std::vector< ArgPack > finalResults{}; 339 340 // iterate until all results completed 341 std::size_t genEnd; 342 ++nTuples; 343 do { 344 genEnd = results.size(); 345 346 // add another argument to results 347 for ( std::size_t i = genStart; i < genEnd; ++i ) { 348 unsigned nextArg = results[i].nextArg; 349 350 // use next element of exploded tuple if present 351 if ( results[i].hasExpl() ) { 352 const ExplodedArg & expl = results[i].getExpl( args ); 353 354 unsigned nextExpl = results[i].nextExpl + 1; 355 if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; } 356 357 results.emplace_back( 358 i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ), 359 copy( results[i].need ), copy( results[i].have ), 360 copy( results[i].open ), nextArg, nTuples, Cost::zero, nextExpl, 361 results[i].explAlt ); 362 363 continue; 364 } 365 366 // finish result when out of arguments 367 if ( nextArg >= args.size() ) { 368 ArgPack newResult{ 369 results[i].env, results[i].need, results[i].have, results[i].open }; 370 newResult.nextArg = nextArg; 371 const ast::Type * argType = nullptr; 372 373 if ( nTuples > 0 || ! results[i].expr ) { 374 // first iteration or no expression to clone, 375 // push empty tuple expression 376 newResult.parent = i; 377 std::vector< ast::ptr< ast::Expr > > emptyList; 378 newResult.expr = 379 new ast::TupleExpr{ CodeLocation{}, move( emptyList ) }; 380 argType = newResult.expr->result; 381 } else { 382 // clone result to collect tuple 383 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 purposes 392 // xxx - what if passing multiple arguments, last of which is 393 // ttype? 394 // xxx - what would happen if unify was changed so that unifying 395 // tuple 396 // types flattened both before unifying lists? then pass in 397 // TupleType (ttype) below. 398 --newResult.tupleStart; 399 } else { 400 // collapse leftover arguments into tuple 401 newResult.endTuple( results ); 402 argType = newResult.expr->result; 403 } 404 } 405 406 // check unification for ttype before adding to final 407 if ( 408 unify( 409 ttype, argType, newResult.env, newResult.need, newResult.have, 410 newResult.open, symtab ) 411 ) { 412 finalResults.emplace_back( move( newResult ) ); 413 } 414 415 continue; 416 } 417 418 // add each possible next argument 419 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 iteration 423 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 gen 429 if ( expl.exprs.empty() ) { 430 results.emplace_back( 431 results[i], move( env ), copy( results[i].need ), 432 copy( results[i].have ), move( open ), nextArg + 1, expl.cost ); 433 434 continue; 435 } 436 437 // add new result 438 results.emplace_back( 439 i, expl.exprs.front(), move( env ), copy( results[i].need ), 440 copy( results[i].have ), move( open ), nextArg + 1, nTuples, 441 expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); 442 } 443 } 444 445 // reset for next round 446 genStart = genEnd; 447 nTuples = 0; 448 } while ( genEnd != results.size() ); 449 450 // splice final results onto results 451 for ( std::size_t i = 0; i < finalResults.size(); ++i ) { 452 results.emplace_back( move( finalResults[i] ) ); 453 } 454 return ! finalResults.empty(); 455 } 456 457 // iterate each current subresult 458 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 present 463 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, symtab ) ) { 482 unsigned nextExpl = results[i].nextExpl + 1; 483 if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; } 484 485 results.emplace_back( 486 i, expr, move( env ), move( need ), move( have ), move( open ), nextArg, 487 nTuples, Cost::zero, nextExpl, results[i].explAlt ); 488 } 489 490 continue; 491 } 492 493 // use default initializers if out of arguments 494 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, symtab ) ) { 501 results.emplace_back( 502 i, new ast::DefaultArgExpr{ cnst->location, cnst }, move( env ), 503 move( need ), move( have ), move( open ), nextArg, nTuples ); 504 } 505 } 506 507 continue; 508 } 509 510 // Check each possible next argument 511 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 iteration 515 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 gen 522 if ( expl.exprs.empty() ) { 523 results.emplace_back( 524 results[i], move( env ), move( need ), move( have ), move( open ), 525 nextArg + 1, expl.cost ); 526 527 continue; 528 } 529 530 // consider only first exploded arg 531 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 types 543 if ( unify( paramType, argType, env, need, have, open, symtab ) ) { 544 // add new result 545 results.emplace_back( 546 i, expr, move( env ), move( need ), move( have ), move( open ), 547 nextArg + 1, nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j ); 548 } 549 } 550 } 551 552 // reset for next parameter 553 genStart = genEnd; 554 555 return genEnd != results.size(); 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::GeneratedCast 561 ) { 562 if ( 563 arg->result->size() > 1 564 && ! 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 each 568 // member of the tuple to its corresponding target type, producing the tuple of those 569 // cast expressions. If there are more components of the tuple than components in the 570 // target type, then excess components do not come out in the result expression (but 571 // 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 of 574 // the expression 575 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 component 580 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, move( components ) }; 585 } else { 586 // handle normally 587 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; 75 598 } 76 599 … … 99 622 } 100 623 624 /// Set up candidate assertions for inference 625 void inferParameters( CandidateRef & newCand, CandidateList & out ) { 626 // Set need bindings for any unbound assertions 627 UniqueId crntResnSlot = 0; // matching ID for this expression's assertions 628 for ( auto & assn : newCand->need ) { 629 // skip already-matched assertions 630 if ( assn.second.resnSlot != 0 ) continue; 631 // assign slot for expression if needed 632 if ( crntResnSlot == 0 ) { crntResnSlot = ++globalResnSlot; } 633 // fix slot to assertion 634 assn.second.resnSlot = crntResnSlot; 635 } 636 // pair slot to expression 637 if ( crntResnSlot != 0 ) { 638 newCand->expr.get_and_mutate()->inferred.resnSlots().emplace_back( crntResnSlot ); 639 } 640 641 // add to output list; assertion satisfaction will occur later 642 out.emplace_back( newCand ); 643 } 644 645 /// Completes a function candidate with arguments located 646 void validateFunctionCandidate( 647 const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results, 648 CandidateList & out 649 ) { 650 ast::ApplicationExpr * appExpr = 651 new ast::ApplicationExpr{ func->expr->location, func->expr }; 652 // sum cost and accumulate arguments 653 std::deque< const ast::Expr * > args; 654 Cost cost = func->cost; 655 const ArgPack * pack = &result; 656 while ( pack->expr ) { 657 args.emplace_front( pack->expr ); 658 cost += pack->cost; 659 pack = &results[pack->parent]; 660 } 661 std::vector< ast::ptr< ast::Expr > > vargs( args.begin(), args.end() ); 662 appExpr->args = move( vargs ); 663 // build and validate new candidate 664 auto newCand = 665 std::make_shared<Candidate>( appExpr, result.env, result.open, result.need, cost ); 666 PRINT( 667 std::cerr << "instantiate function success: " << appExpr << std::endl; 668 std::cerr << "need assertions:" << std::endl; 669 ast::print( std::cerr, result.need, 2 ); 670 ) 671 inferParameters( newCand, out ); 672 } 673 101 674 /// Builds a list of candidates for a function, storing them in out 102 675 void makeFunctionCandidates( … … 104 677 const ExplodedArgs_new & args, CandidateList & out 105 678 ) { 106 #warning unimplemented 107 (void)func; (void)funcType; (void)args; (void)out; 108 assert(false); 679 ast::OpenVarSet funcOpen; 680 ast::AssertionSet funcNeed, funcHave; 681 ast::TypeEnvironment funcEnv{ func->env }; 682 makeUnifiableVars( funcType, funcOpen, funcNeed ); 683 // add all type variables as open variables now so that those not used in the parameter 684 // list are still considered open 685 funcEnv.add( funcType->forall ); 686 687 if ( targetType && ! targetType->isVoid() && ! funcType->returns.empty() ) { 688 // attempt to narrow based on expected target type 689 const ast::Type * returnType = funcType->returns.front()->get_type(); 690 if ( ! unify( 691 returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen, symtab ) 692 ) { 693 // unification failed, do not pursue this candidate 694 return; 695 } 696 } 697 698 // iteratively build matches, one parameter at a time 699 std::vector< ArgPack > results; 700 results.emplace_back( funcEnv, funcNeed, funcHave, funcOpen ); 701 std::size_t genStart = 0; 702 703 for ( const ast::DeclWithType * param : funcType->params ) { 704 auto obj = strict_dynamic_cast< const ast::ObjectDecl * >( param ); 705 // Try adding the arguments corresponding to the current parameter to the existing 706 // matches 707 if ( ! instantiateArgument( 708 obj->type, obj->init, args, results, genStart, symtab ) ) return; 709 } 710 711 if ( funcType->isVarArgs ) { 712 // append any unused arguments to vararg pack 713 std::size_t genEnd; 714 do { 715 genEnd = results.size(); 716 717 // iterate results 718 for ( std::size_t i = genStart; i < genEnd; ++i ) { 719 unsigned nextArg = results[i].nextArg; 720 721 // use remainder of exploded tuple if present 722 if ( results[i].hasExpl() ) { 723 const ExplodedArg & expl = results[i].getExpl( args ); 724 725 unsigned nextExpl = results[i].nextExpl + 1; 726 if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; } 727 728 results.emplace_back( 729 i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ), 730 copy( results[i].need ), copy( results[i].have ), 731 copy( results[i].open ), nextArg, 0, Cost::zero, nextExpl, 732 results[i].explAlt ); 733 734 continue; 735 } 736 737 // finish result when out of arguments 738 if ( nextArg >= args.size() ) { 739 validateFunctionCandidate( func, results[i], results, out ); 740 741 continue; 742 } 743 744 // add each possible next argument 745 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) { 746 const ExplodedArg & expl = args[nextArg][j]; 747 748 // fresh copies of parent parameters for this iteration 749 ast::TypeEnvironment env = results[i].env; 750 ast::OpenVarSet open = results[i].open; 751 752 env.addActual( expl.env, open ); 753 754 // skip empty tuple arguments by (nearly) cloning parent into next gen 755 if ( expl.exprs.empty() ) { 756 results.emplace_back( 757 results[i], move( env ), copy( results[i].need ), 758 copy( results[i].have ), move( open ), nextArg + 1, 759 expl.cost ); 760 761 continue; 762 } 763 764 // add new result 765 results.emplace_back( 766 i, expl.exprs.front(), move( env ), copy( results[i].need ), 767 copy( results[i].have ), move( open ), nextArg + 1, 0, expl.cost, 768 expl.exprs.size() == 1 ? 0 : 1, j ); 769 } 770 } 771 772 genStart = genEnd; 773 } while( genEnd != results.size() ); 774 } else { 775 // filter out the results that don't use all the arguments 776 for ( std::size_t i = genStart; i < results.size(); ++i ) { 777 ArgPack & result = results[i]; 778 if ( ! result.hasExpl() && result.nextArg >= args.size() ) { 779 validateFunctionCandidate( func, result, results, out ); 780 } 781 } 782 } 109 783 } 110 784 111 785 /// Adds implicit struct-conversions to the alternative list 112 786 void addAnonConversions( const CandidateRef & cand ) { 113 #warning unimplemented 114 (void)cand; 115 assert(false); 787 // adds anonymous member interpretations whenever an aggregate value type is seen. 788 // it's okay for the aggregate expression to have reference type -- cast it to the 789 // base type to treat the aggregate as the referenced value 790 ast::ptr< ast::Expr > aggrExpr( cand->expr ); 791 ast::ptr< ast::Type > & aggrType = aggrExpr.get_and_mutate()->result; 792 cand->env.apply( aggrType ); 793 794 if ( aggrType.as< ast::ReferenceType >() ) { 795 aggrExpr = 796 new ast::CastExpr{ aggrExpr->location, aggrExpr, aggrType->stripReferences() }; 797 } 798 799 if ( auto structInst = aggrExpr->result.as< ast::StructInstType >() ) { 800 addAggMembers( structInst, aggrExpr, *cand, Cost::safe, "" ); 801 } else if ( auto unionInst = aggrExpr->result.as< ast::UnionInstType >() ) { 802 addAggMembers( unionInst, aggrExpr, *cand, Cost::safe, "" ); 803 } 804 } 805 806 /// Adds aggregate member interpretations 807 void addAggMembers( 808 const ast::ReferenceToType * aggrInst, const ast::Expr * expr, 809 const Candidate & cand, const Cost & addedCost, const std::string & name 810 ) { 811 for ( const ast::Decl * decl : aggrInst->lookup( name ) ) { 812 auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( decl ); 813 CandidateRef newCand = std::make_shared<Candidate>( 814 cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost ); 815 // add anonymous member interpretations whenever an aggregate value type is seen 816 // as a member expression 817 addAnonConversions( newCand ); 818 candidates.emplace_back( move( newCand ) ); 819 } 820 } 821 822 /// Adds tuple member interpretations 823 void addTupleMembers( 824 const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand, 825 const Cost & addedCost, const ast::Expr * member 826 ) { 827 if ( auto constantExpr = dynamic_cast< const ast::ConstantExpr * >( member ) ) { 828 // get the value of the constant expression as an int, must be between 0 and the 829 // length of the tuple to have meaning 830 long long val = constantExpr->intValue(); 831 if ( val >= 0 && (unsigned long long)val < tupleType->size() ) { 832 addCandidate( 833 cand, new ast::TupleIndexExpr{ expr->location, expr, (unsigned)val }, 834 addedCost ); 835 } 836 } 116 837 } 117 838 … … 189 910 funcE.emplace_back( *func, symtab ); 190 911 } 191 argExpansions.emplace_front( std::move( funcE ) );912 argExpansions.emplace_front( move( funcE ) ); 192 913 193 914 for ( const CandidateRef & op : opFinder ) { … … 233 954 if ( cvtCost != Cost::infinity ) { 234 955 withFunc->cvtCost = cvtCost; 235 candidates.emplace_back( std::move( withFunc ) );236 } 237 } 238 found = std::move( candidates );956 candidates.emplace_back( move( withFunc ) ); 957 } 958 } 959 found = move( candidates ); 239 960 240 961 // use a new list so that candidates are not examined by addAnonConversions twice … … 285 1006 286 1007 void postvisit( const ast::CastExpr * castExpr ) { 287 #warning unimplemented 288 (void)castExpr; 289 assert(false); 1008 ast::ptr< ast::Type > toType = castExpr->result; 1009 assert( toType ); 1010 toType = resolveTypeof( toType, symtab ); 1011 toType = SymTab::validateType( toType, symtab ); 1012 toType = adjustExprType( toType, tenv, symtab ); 1013 1014 CandidateFinder finder{ symtab, tenv, toType }; 1015 finder.find( castExpr->arg, ResolvMode::withAdjustment() ); 1016 1017 CandidateList matches; 1018 for ( CandidateRef & cand : finder.candidates ) { 1019 ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have; 1020 ast::OpenVarSet open( cand->open ); 1021 1022 cand->env.extractOpenVars( open ); 1023 1024 // It is possible that a cast can throw away some values in a multiply-valued 1025 // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of the 1026 // subexpression results that are cast directly. The candidate is invalid if it 1027 // has fewer results than there are types to cast to. 1028 int discardedValues = cand->expr->result->size() - toType->size(); 1029 if ( discardedValues < 0 ) continue; 1030 1031 // unification run for side-effects 1032 unify( toType, cand->expr->result, cand->env, need, have, open, symtab ); 1033 Cost thisCost = castCost( cand->expr->result, toType, symtab, cand->env ); 1034 PRINT( 1035 std::cerr << "working on cast with result: " << toType << std::endl; 1036 std::cerr << "and expr type: " << cand->expr->result << std::endl; 1037 std::cerr << "env: " << cand->env << std::endl; 1038 ) 1039 if ( thisCost != Cost::infinity ) { 1040 PRINT( 1041 std::cerr << "has finite cost." << std::endl; 1042 ) 1043 // count one safe conversion for each value that is thrown away 1044 thisCost.incSafe( discardedValues ); 1045 CandidateRef newCand = std::make_shared<Candidate>( 1046 restructureCast( cand->expr, toType, castExpr->isGenerated ), 1047 copy( cand->env ), move( open ), move( need ), cand->cost, 1048 cand->cost + thisCost ); 1049 inferParameters( newCand, matches ); 1050 } 1051 } 1052 1053 // select first on argument cost, then conversion cost 1054 CandidateList minArgCost = findMinCost( matches ); 1055 promoteCvtCost( minArgCost ); 1056 candidates = findMinCost( minArgCost ); 290 1057 } 291 1058 … … 297 1064 for ( CandidateRef & r : finder.candidates ) { 298 1065 addCandidate( 299 *r, new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } ); 1066 *r, 1067 new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } ); 300 1068 } 301 1069 } 302 1070 303 1071 void postvisit( const ast::UntypedMemberExpr * memberExpr ) { 304 #warning unimplemented 305 (void)memberExpr; 306 assert(false); 1072 CandidateFinder aggFinder{ symtab, tenv }; 1073 aggFinder.find( memberExpr->aggregate, ResolvMode::withAdjustment() ); 1074 for ( CandidateRef & agg : aggFinder.candidates ) { 1075 // it's okay for the aggregate expression to have reference type -- cast it to the 1076 // base type to treat the aggregate as the referenced value 1077 Cost addedCost = Cost::zero; 1078 agg->expr = referenceToRvalueConversion( agg->expr, addedCost ); 1079 1080 // find member of the given type 1081 if ( auto structInst = agg->expr->result.as< ast::StructInstType >() ) { 1082 addAggMembers( 1083 structInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) ); 1084 } else if ( auto unionInst = agg->expr->result.as< ast::UnionInstType >() ) { 1085 addAggMembers( 1086 unionInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) ); 1087 } else if ( auto tupleType = agg->expr->result.as< ast::TupleType >() ) { 1088 addTupleMembers( tupleType, agg->expr, *agg, addedCost, memberExpr->member ); 1089 } 1090 } 307 1091 } 308 1092 … … 311 1095 } 312 1096 313 void postvisit( const ast::NameExpr * variableExpr ) { 314 #warning unimplemented 315 (void)variableExpr; 316 assert(false); 1097 void postvisit( const ast::NameExpr * nameExpr ) { 1098 std::vector< ast::SymbolTable::IdData > declList = symtab.lookupId( nameExpr->name ); 1099 PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; ) 1100 for ( auto & data : declList ) { 1101 Cost cost = Cost::zero; 1102 ast::Expr * newExpr = data.combine( nameExpr->location, cost ); 1103 1104 CandidateRef newCand = std::make_shared<Candidate>( 1105 newExpr, copy( tenv ), ast::OpenVarSet{}, ast::AssertionSet{}, Cost::zero, 1106 cost ); 1107 PRINT( 1108 std::cerr << "decl is "; 1109 ast::print( std::cerr, data.id ); 1110 std::cerr << std::endl; 1111 std::cerr << "newExpr is "; 1112 ast::print( std::cerr, newExpr ); 1113 std::cerr << std::endl; 1114 ) 1115 newCand->expr = ast::mutate_field( 1116 newCand->expr.get(), &ast::Expr::result, 1117 renameTyVars( newCand->expr->result ) ); 1118 // add anonymous member interpretations whenever an aggregate value type is seen 1119 // as a name expression 1120 addAnonConversions( newCand ); 1121 candidates.emplace_back( move( newCand ) ); 1122 } 317 1123 } 318 1124 … … 329 1135 330 1136 void postvisit( const ast::SizeofExpr * sizeofExpr ) { 331 #warning unimplemented 332 (void)sizeofExpr; 333 assert(false); 1137 if ( sizeofExpr->type ) { 1138 addCandidate( 1139 new ast::SizeofExpr{ 1140 sizeofExpr->location, resolveTypeof( sizeofExpr->type, symtab ) }, 1141 tenv ); 1142 } else { 1143 // find all candidates for the argument to sizeof 1144 CandidateFinder finder{ symtab, tenv }; 1145 finder.find( sizeofExpr->expr ); 1146 // find the lowest-cost candidate, otherwise ambiguous 1147 CandidateList winners = findMinCost( finder.candidates ); 1148 if ( winners.size() != 1 ) { 1149 SemanticError( 1150 sizeofExpr->expr.get(), "Ambiguous expression in sizeof operand: " ); 1151 } 1152 // return the lowest-cost candidate 1153 CandidateRef & choice = winners.front(); 1154 choice->expr = referenceToRvalueConversion( choice->expr, choice->cost ); 1155 choice->cost = Cost::zero; 1156 addCandidate( *choice, new ast::SizeofExpr{ sizeofExpr->location, choice->expr } ); 1157 } 334 1158 } 335 1159 336 1160 void postvisit( const ast::AlignofExpr * alignofExpr ) { 337 #warning unimplemented 338 (void)alignofExpr; 339 assert(false); 1161 if ( alignofExpr->type ) { 1162 addCandidate( 1163 new ast::AlignofExpr{ 1164 alignofExpr->location, resolveTypeof( alignofExpr->type, symtab ) }, 1165 tenv ); 1166 } else { 1167 // find all candidates for the argument to alignof 1168 CandidateFinder finder{ symtab, tenv }; 1169 finder.find( alignofExpr->expr ); 1170 // find the lowest-cost candidate, otherwise ambiguous 1171 CandidateList winners = findMinCost( finder.candidates ); 1172 if ( winners.size() != 1 ) { 1173 SemanticError( 1174 alignofExpr->expr.get(), "Ambiguous expression in alignof operand: " ); 1175 } 1176 // return the lowest-cost candidate 1177 CandidateRef & choice = winners.front(); 1178 choice->expr = referenceToRvalueConversion( choice->expr, choice->cost ); 1179 choice->cost = Cost::zero; 1180 addCandidate( 1181 *choice, new ast::AlignofExpr{ alignofExpr->location, choice->expr } ); 1182 } 340 1183 } 341 1184 342 1185 void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) { 343 #warning unimplemented 344 (void)offsetofExpr; 345 assert(false); 1186 const ast::ReferenceToType * aggInst; 1187 if (( aggInst = offsetofExpr->type.as< ast::StructInstType >() )) ; 1188 else if (( aggInst = offsetofExpr->type.as< ast::UnionInstType >() )) ; 1189 else return; 1190 1191 for ( const ast::Decl * member : aggInst->lookup( offsetofExpr->member ) ) { 1192 auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( member ); 1193 addCandidate( 1194 new ast::OffsetofExpr{ offsetofExpr->location, aggInst, dwt }, tenv ); 1195 } 346 1196 } 347 1197 … … 376 1226 new ast::LogicalExpr{ 377 1227 logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd }, 378 std::move( env ), std::move( open ), std::move( need ), 379 r1->cost + r2->cost ); 1228 move( env ), move( open ), move( need ), r1->cost + r2->cost ); 380 1229 } 381 1230 } … … 421 1270 common ) 422 1271 ) { 423 #warning unimplemented 424 assert(false); 1272 // generate typed expression 1273 ast::ConditionalExpr * newExpr = new ast::ConditionalExpr{ 1274 conditionalExpr->location, r1->expr, r2->expr, r3->expr }; 1275 newExpr->result = common ? common : r2->expr->result; 1276 // convert both options to result type 1277 Cost cost = r1->cost + r2->cost + r3->cost; 1278 newExpr->arg2 = computeExpressionConversionCost( 1279 newExpr->arg2, newExpr->result, symtab, env, cost ); 1280 newExpr->arg3 = computeExpressionConversionCost( 1281 newExpr->arg3, newExpr->result, symtab, env, cost ); 1282 // output candidate 1283 CandidateRef newCand = std::make_shared<Candidate>( 1284 newExpr, move( env ), move( open ), move( need ), cost ); 1285 inferParameters( newCand, candidates ); 425 1286 } 426 1287 } … … 480 1341 common ) 481 1342 ) { 1343 // generate new expression 482 1344 ast::RangeExpr * newExpr = 483 1345 new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr }; 484 1346 newExpr->result = common ? common : r1->expr->result; 485 486 #warning unimplemented 487 assert(false); 1347 // add candidate 1348 CandidateRef newCand = std::make_shared<Candidate>( 1349 newExpr, move( env ), move( open ), move( need ), 1350 r1->cost + r2->cost ); 1351 inferParameters( newCand, candidates ); 488 1352 } 489 1353 } … … 512 1376 513 1377 addCandidate( 514 new ast::TupleExpr{ tupleExpr->location, std::move( exprs ) },515 std::move( env ), std::move( open ), std::move( need ), sumCost( subs ) );1378 new ast::TupleExpr{ tupleExpr->location, move( exprs ) }, 1379 move( env ), move( open ), move( need ), sumCost( subs ) ); 516 1380 } 517 1381 } … … 539 1403 540 1404 void postvisit( const ast::StmtExpr * stmtExpr ) { 541 #warning unimplemented 542 (void)stmtExpr; 543 assert(false); 1405 addCandidate( resolveStmtExpr( stmtExpr, symtab ), tenv ); 544 1406 } 545 1407 546 1408 void postvisit( const ast::UntypedInitExpr * initExpr ) { 547 #warning unimplemented 548 (void)initExpr; 549 assert(false); 1409 // handle each option like a cast 1410 CandidateList matches; 1411 PRINT( 1412 std::cerr << "untyped init expr: " << initExpr << std::endl; 1413 ) 1414 // O(n^2) checks of d-types with e-types 1415 for ( const ast::InitAlternative & initAlt : initExpr->initAlts ) { 1416 // calculate target type 1417 const ast::Type * toType = resolveTypeof( initAlt.type, symtab ); 1418 toType = SymTab::validateType( toType, symtab ); 1419 toType = adjustExprType( toType, tenv, symtab ); 1420 // The call to find must occur inside this loop, otherwise polymorphic return 1421 // types are not bound to the initialization type, since return type variables are 1422 // only open for the duration of resolving the UntypedExpr. 1423 CandidateFinder finder{ symtab, tenv, toType }; 1424 finder.find( initExpr->expr, ResolvMode::withAdjustment() ); 1425 for ( CandidateRef & cand : finder.candidates ) { 1426 ast::TypeEnvironment env{ cand->env }; 1427 ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have; 1428 ast::OpenVarSet open{ cand->open }; 1429 1430 PRINT( 1431 std::cerr << " @ " << toType << " " << initAlt.designation << std::endl; 1432 ) 1433 1434 // It is possible that a cast can throw away some values in a multiply-valued 1435 // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of 1436 // the subexpression results that are cast directly. The candidate is invalid 1437 // if it has fewer results than there are types to cast to. 1438 int discardedValues = cand->expr->result->size() - toType->size(); 1439 if ( discardedValues < 0 ) continue; 1440 1441 // unification run for side-effects 1442 unify( toType, cand->expr->result, env, need, have, open, symtab ); 1443 Cost thisCost = castCost( cand->expr->result, toType, symtab, env ); 1444 1445 if ( thisCost != Cost::infinity ) { 1446 // count one safe conversion for each value that is thrown away 1447 thisCost.incSafe( discardedValues ); 1448 CandidateRef newCand = std::make_shared<Candidate>( 1449 new ast::InitExpr{ 1450 initExpr->location, restructureCast( cand->expr, toType ), 1451 initAlt.designation }, 1452 copy( cand->env ), move( open ), move( need ), cand->cost, thisCost ); 1453 inferParameters( newCand, matches ); 1454 } 1455 } 1456 } 1457 1458 // select first on argument cost, then conversion cost 1459 CandidateList minArgCost = findMinCost( matches ); 1460 promoteCvtCost( minArgCost ); 1461 candidates = findMinCost( minArgCost ); 550 1462 } 551 1463 … … 628 1540 cand->env.applyFree( newResult ); 629 1541 cand->expr = ast::mutate_field( 630 cand->expr.get(), &ast::Expr::result, std::move( newResult ) );1542 cand->expr.get(), &ast::Expr::result, move( newResult ) ); 631 1543 632 1544 out.emplace_back( cand ); … … 651 1563 CandidateList satisfied; 652 1564 std::vector< std::string > errors; 653 for ( auto& candidate : candidates ) {654 satisfyAssertions( *candidate, symtab, satisfied, errors );1565 for ( CandidateRef & candidate : candidates ) { 1566 satisfyAssertions( candidate, symtab, satisfied, errors ); 655 1567 } 656 1568 … … 666 1578 667 1579 // reset candidates 668 candidates = std::move( satisfied );1580 candidates = move( satisfied ); 669 1581 } 670 1582 … … 690 1602 691 1603 auto oldsize = candidates.size(); 692 candidates = std::move( pruned );1604 candidates = move( pruned ); 693 1605 694 1606 PRINT(
Note: See TracChangeset
for help on using the changeset viewer.