Changeset f89a111
- Timestamp:
- Jul 20, 2018, 4:50:02 PM (6 years ago)
- Branches:
- new-env
- Children:
- 9160cb2
- Parents:
- eff03a94
- git-author:
- Aaron Moss <a3moss@…> (07/20/18 16:43:03)
- git-committer:
- Aaron Moss <a3moss@…> (07/20/18 16:50:02)
- Location:
- src/ResolvExpr
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/TypeEnvironment.cc
reff03a94 rf89a111 17 17 #include <algorithm> // for copy, set_intersection 18 18 #include <iterator> // for ostream_iterator, insert_iterator 19 #include <list> // for list 20 #include <vector> // for vector 21 #include <unordered_map> // for unordered_map 19 22 #include <utility> // for pair, move 20 23 … … 408 411 } 409 412 413 bool TypeEnvrionment::combine( const TypeEnvironment& o, const SymTab::Indexer& indexer ) { 414 // short-circuit for empty cases 415 if ( o.isEmpty() ) return true; 416 if ( isEmpty() ) { 417 *this = o; 418 return true; 419 } 420 421 /// Edit item for path state 422 struct Edit { 423 Classes::Mode mode; ///< Type of change to a key 424 interned_string root; ///< New/Previous root, if addTo/remFrom node 425 426 Edit(Classes::Mode m, interned_string r = nullptr) : mode{m}, root{r} {} 427 }; 428 429 // track class changes 430 classes->reroot(); 431 PRE_POST_VALIDATE 432 433 using EditEntry = std::pair<interned_string, Edit>; 434 using EditList = std::list<EditEntry>; 435 using IndexedEdits = std::vector<EditList::iterator>; 436 437 EditList edits; 438 std::unordered_map<interned_string, IndexedEdits> editIndex; 439 440 // trace path from other environment 441 const Classes* oclasses = o.classes; 442 Classes::Mode omode = oclasses->get_mode(); 443 while ( omode != Classes::BASE ) { 444 interned_string key = oclasses->get_key(); 445 IndexedEdits& forKey = editIndex[ key ]; 446 447 if ( forKey.empty() ) { 448 // newly seen key, mark op 449 interned_string root = ( omode == Classes::ADD || omode == Classes::REM ) ? 450 nullptr : oclasses->get_root(); 451 auto it = edits.emplace( edits.begin(), key, Edit{ omode, root } ); 452 forKey.push_back( move(it) ); 453 } else { 454 auto next = forKey.back(); // edit next applied to this key 455 Classes::Mode nmode = next->second.mode; // next action applied 456 457 switch ( omode ) { 458 case Classes::ADD: { 459 switch ( nmode ) { 460 case Classes::REM: { 461 // later removal, no net change to classes 462 edits.erase( next ); 463 forKey.pop_back(); 464 } break; 465 case Classes::ADDTO: { 466 // later merge, prefix with this addition 467 auto it = edits.emplace( edits.begin(), key, Edit{ omode } ); 468 forKey.push_back( move(it) ); 469 } break; 470 default: assertf( false, "inconsistent mode" ); 471 } 472 } break; 473 case Classes::REM: { 474 // later addition, no net change to classes 475 assertf( nmode == Classes::ADD, "inconsistent mode" ); 476 edits.erase( next ); 477 forKey.pop_back(); 478 } break; 479 case Classes::ADDTO: { 480 // later unmerged from same class, no net change to classes 481 assume( nmode == Classes::REMFROM, "inconsistent mode" ); 482 assume( oclasses->get_root() == next->second.root, "inconsistent tree" ); 483 edits.erase( next ); 484 forKey.pop_back(); 485 } break; 486 case Classes::REMFROM: { 487 interned_string root = oclasses->get_root(); 488 switch ( nmode ) { 489 case Classes::REM: { 490 // later removal, prefix with this unmerge 491 auto it = edits.emplace( edits.begin(), key, Edit{ omode, root } ); 492 forKey.push_back( move(it) ); 493 } break; 494 case Classes::ADDTO: { 495 if ( root == next->second.root ) { 496 // later merged back into same class, no net change 497 edits.erase( next ); 498 forKey.pop_back(); 499 } else { 500 // later merged into different class, prefix with this unmerge 501 auto it = edits.emplace( 502 edits.begin(), key, Edit{ omode, root } ); 503 forKey.push_back( move(it) ); 504 } 505 } break; 506 default: assertf( false, "inconsistent mode" ); 507 } 508 } break; 509 default: assertf( false, "invalid mode" ); 510 } 511 } 512 513 oclasses = oclasses->get_base(); 514 omode = oclasses->get_mode(); 515 } 516 assertf( oclasses == classes, "classes must be versions of the same map" ); 517 518 /// Edit item for binding changes 519 struct BEdit { 520 Bindings::Mode mode; ///< Type of change to a key 521 BoundType val; ///< Updated key value, if applicable 522 523 BEdit(Bindings::Mode m) : mode{m}, val{} {} 524 BEdit(Bindings::Mode m, const BoundType& b) : mode{m}, val{b} {} 525 }; 526 527 // track binding merges 528 bindings->reroot(); 529 std::unordered_map<interned_string, BEdit> bedits; // edits to base bindings 530 531 // trace path from other environment 532 const Bindings* bbindings = o.bindings; 533 Bindings::Mode bmode = bbindings->get_mode(); 534 while ( bmode != Bindings::BASE ) { 535 interned_string key = bbindings->get_key(); 536 auto it = bedits.find( key ); 537 538 if ( it == bedits.end() ) { 539 // newly seen key, mark operation 540 if ( bmode == Bindings::REM ) { 541 bedits.emplace_back( it, key, BEdit{ bmode } ); 542 } else { 543 bedits.emplace_back( it, key, BEdit{ bmode, bbindings->get_val() } ); 544 } 545 } else { 546 Bindings::Mode& smode = it->second.mode; 547 switch ( bmode ) { 548 case Bindings::REM: { 549 // later insertion, change to update 550 assertf( smode == Bindings::INS, "inconsistent mode" ); 551 smode = Bindings::UPD; 552 } break; 553 case Bindings::INS: { 554 switch ( smode ) { 555 case Bindings::REM: { 556 // later removal, no net change to map 557 bedits.erase( it ); 558 } break; 559 case Bindings::UPD: { 560 // later update collapses to insertion 561 smode = Bindings::INS; 562 } break; 563 default: assertf( false, "inconsistent mode" ); 564 } 565 } break; 566 case Bindings::UPD: { 567 // later removal or update overrides this update 568 assertf( smode == Bindings::REM || smode == Bindings::UPD, "inconsistent mode" ); 569 } break; 570 default: assertf( false, "invalid mode" ); 571 } 572 } 573 574 bbindings = bbindings->get_base(); 575 bmode = bbindings->get_mode(); 576 } 577 assume( bbindings == bindings, "bindings must be versions of same map" ); 578 579 // merge typeclasses (always possible, can always merge all classes into one if the 580 // bindings unify) 581 for ( const EditEntry& edit : edits ) { 582 interned_string key = edit.first; 583 const Edit& e = edit.second; 584 585 switch ( e.mode ) { 586 case Classes::ADD: { 587 // add new type variable 588 classes = classes->add( key ); 589 // add binding for variable 590 auto bit = bedits.find( key ); 591 if ( bit != bedits.end() ) { 592 // take final value if it is a root in its own map 593 const BEdit& be = bit->second; 594 assertf( be.mode == Bindings::INS, "inconsistent binding" ); 595 bindings = bindings->set( key, std::move(be.val) ); 596 // remove update from edit set so that it isn't re-checked 597 bedits.erase( bit ); 598 } else { 599 // otherwise just put in default binding 600 bindings = bindings->set( key, BoundType{} ); 601 } 602 } break; 603 case Classes::REM: { 604 // do not remove type variable (merging) 605 } break; 606 case Classes::ADDTO: { 607 // if previous REMFROM on this key, or ADDTO on this root, may not match 608 // current state in `classes` 609 interned_string key_root = classes->find( key ); 610 interned_string merge_root = classes->find( e.root ); 611 // skip case where classes already merged 612 if ( key_root == merge_root ) break; 613 // merge classes and remove binding for new child 614 interned_string new_child = mergeClasses( key_root, merge_root ).second; 615 if ( bindings->count( new_child ) ) { 616 // add new insert edit to check merge with old value if needed 617 const BoundType& child_bind = bindings->get( new_child ); 618 if ( child_bind.type ) { 619 // store this insert under the original key, which must be a REM 620 // binding change if present 621 auto bit = bedits.find( key ); 622 if ( bit != bedits.end() ) { 623 BEdit& be = bit->second; 624 assertf( be.mode == Bindings::REM, "inconsistent binding" ); 625 be = BEdit{ Bindings::INS, child_bind }; 626 } else { 627 bedits.emplace_hint( bit, key, BEdit{ Bindings::INS, child_bind } ); 628 } 629 } 630 // remove child binding from map 631 bindings = bindings->erase( new_child ); 632 } 633 } break; 634 case Classes::REMFROM: { 635 // do not split classes 636 } break; 637 default: assertf( false, "invalid mode" ); 638 } 639 } 640 641 // finish merging bindings. This may fail, or may merge further classes 642 for ( const auto& entry : bedits ) { 643 interned_string key = entry.first; 644 const BEdit& e = entry.second; 645 646 // skip binding removals; the ADDTO merge has taken out all the new non-roots 647 if ( e.mode == Bindings::REM ) continue; 648 assertf( e.mode == Bindings::UPD || e.mode == Bindings::INS, "inconsistent binding" ); 649 650 // attempt binding update 651 interned_string root = classes->find( key ); 652 BoundType ebound = bindings->get( root ); 653 const BoundType& nbound = e.val; 654 655 if ( ebound.type && nbound.type ) { 656 // attempt to unify bound classes 657 Type* common = nullptr; 658 AssertionSet need, have; 659 OpenVarSet openVars; 660 if ( unifyInexact( ebound.type->clone(), nbound.type->clone(), *this, need, have, 661 openVars, WidenMode{ ebound.allowWidening, nbound.allowWidening }, 662 indexer, common ) ) { 663 // update bindings 664 ebound.allowWidening &= nbound.allowWidening; 665 if ( common ) { 666 common->get_qualifiers() = Type::Qualifiers{}; 667 ebound.type = common; 668 } 669 // reset root in case updated in course of unification 670 bindings = bindings->set( classes->find( root ), ebound ); 671 } else return false; // cannot unify bindings 672 } 673 } 674 675 return true; 676 } 677 410 678 void TypeEnvironment::extractOpenVars( OpenVarSet &openVars ) const { 411 679 bindings->for_each( [&]( interned_string root, const BoundType& bound ) { -
src/ResolvExpr/TypeEnvironment.h
reff03a94 rf89a111 221 221 /// Caller should ensure environments do not share type variables. 222 222 void simpleCombine( const TypeEnvironment &second ); 223 224 /// Combines two environments, checking compatibility. Both environments must be versioned 225 /// from the same initial environment. 226 /// Returns false if unsuccessful, but does NOT roll back partial changes 227 bool combine( const TypeEnvironment& o, const SymTab::Indexer& indexer ); 223 228 224 229 void extractOpenVars( OpenVarSet &openVars ) const;
Note: See TracChangeset
for help on using the changeset viewer.