Changeset f89a111


Ignore:
Timestamp:
Jul 20, 2018, 4:50:02 PM (3 years ago)
Author:
Aaron Moss <a3moss@…>
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)
Message:

Ported combine function into new environment

Location:
src/ResolvExpr
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/ResolvExpr/TypeEnvironment.cc

    reff03a94 rf89a111  
    1717#include <algorithm>                   // for copy, set_intersection
    1818#include <iterator>                    // for ostream_iterator, insert_iterator
     19#include <list>                        // for list
     20#include <vector>                      // for vector
     21#include <unordered_map>               // for unordered_map
    1922#include <utility>                     // for pair, move
    2023
     
    408411        }
    409412
     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
    410678        void TypeEnvironment::extractOpenVars( OpenVarSet &openVars ) const {
    411679                bindings->for_each( [&]( interned_string root, const BoundType& bound ) {
  • src/ResolvExpr/TypeEnvironment.h

    reff03a94 rf89a111  
    221221                /// Caller should ensure environments do not share type variables.
    222222                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 );
    223228       
    224229                void extractOpenVars( OpenVarSet &openVars ) const;
Note: See TracChangeset for help on using the changeset viewer.