Changeset f89a111

Timestamp:

Jul 20, 2018, 4:50:02 PM (7 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:

• TypeEnvironment.cc (modified) (2 diffs)
• TypeEnvironment.h (modified) (1 diff)

src/ResolvExpr/TypeEnvironment.cc

@@ -17 +17 @@
 #include <algorithm>                   // for copy, set_intersection
 #include <iterator>                    // for ostream_iterator, insert_iterator
+#include <list>                        // for list
+#include <vector>                      // for vector
+#include <unordered_map>               // for unordered_map
 #include <utility>                     // for pair, move
 
@@ -408 +411 @@
         }
 
+        bool TypeEnvrionment::combine( const TypeEnvironment& o, const SymTab::Indexer& indexer ) {
+                // short-circuit for empty cases
+                if ( o.isEmpty() ) return true;
+                if ( isEmpty() ) {
+                        *this = o;
+                        return true;
+                }
+
+                /// Edit item for path state
+                struct Edit {
+                        Classes::Mode mode;   ///< Type of change to a key
+                        interned_string root; ///< New/Previous root, if addTo/remFrom node
+
+                        Edit(Classes::Mode m, interned_string r = nullptr) : mode{m}, root{r} {}
+                };
+
+                // track class changes
+                classes->reroot();
+                PRE_POST_VALIDATE
+
+                using EditEntry = std::pair<interned_string, Edit>;
+                using EditList = std::list<EditEntry>;
+                using IndexedEdits = std::vector<EditList::iterator>;
+
+                EditList edits;
+                std::unordered_map<interned_string, IndexedEdits> editIndex;
+
+                // trace path from other environment
+                const Classes* oclasses = o.classes;
+                Classes::Mode omode = oclasses->get_mode();
+                while ( omode != Classes::BASE ) {
+                        interned_string key = oclasses->get_key();
+                        IndexedEdits& forKey = editIndex[ key ];
+
+                        if ( forKey.empty() ) {
+                                // newly seen key, mark op
+                                interned_string root = ( omode == Classes::ADD || omode == Classes::REM ) ?
+                                        nullptr : oclasses->get_root();
+                                auto it = edits.emplace( edits.begin(), key, Edit{ omode, root } );
+                                forKey.push_back( move(it) );
+                        } else {
+                                auto next = forKey.back();  // edit next applied to this key
+                                Classes::Mode nmode = next->second.mode; // next action applied
+
+                                switch ( omode ) {
+                                        case Classes::ADD: {
+                                                switch ( nmode ) {
+                                                        case Classes::REM: {
+                                                                // later removal, no net change to classes
+                                                                edits.erase( next );
+                                                                forKey.pop_back();
+                                                        } break;
+                                                        case Classes::ADDTO: {
+                                                                // later merge, prefix with this addition
+                                                                auto it = edits.emplace( edits.begin(), key, Edit{ omode } );
+                                                                forKey.push_back( move(it) );
+                                                        } break;
+                                                        default: assertf( false, "inconsistent mode" );
+                                                }
+                                        } break;
+                                        case Classes::REM: {
+                                                // later addition, no net change to classes
+                                                assertf( nmode == Classes::ADD, "inconsistent mode" );
+                                                edits.erase( next );
+                                                forKey.pop_back();
+                                        } break;
+                                        case Classes::ADDTO: {
+                                                // later unmerged from same class, no net change to classes
+                                                assume( nmode == Classes::REMFROM, "inconsistent mode" );
+                                                assume( oclasses->get_root() == next->second.root, "inconsistent tree" );
+                                                edits.erase( next );
+                                                forKey.pop_back();
+                                        } break;
+                                        case Classes::REMFROM: {
+                                                interned_string root = oclasses->get_root();
+                                                switch ( nmode ) {
+                                                        case Classes::REM: {
+                                                                // later removal, prefix with this unmerge
+                                                                auto it = edits.emplace( edits.begin(), key, Edit{ omode, root } );
+                                                                forKey.push_back( move(it) );
+                                                        } break;
+                                                        case Classes::ADDTO: {
+                                                                if ( root == next->second.root ) {
+                                                                        // later merged back into same class, no net change
+                                                                        edits.erase( next );
+                                                                        forKey.pop_back();
+                                                                } else {
+                                                                        // later merged into different class, prefix with this unmerge
+                                                                        auto it = edits.emplace( 
+                                                                                edits.begin(), key, Edit{ omode, root } );
+                                                                        forKey.push_back( move(it) );
+                                                                }
+                                                        } break;
+                                                        default: assertf( false, "inconsistent mode" );
+                                                }
+                                        } break;
+                                        default: assertf( false, "invalid mode" );
+                                }
+                        }
+
+                        oclasses = oclasses->get_base();
+                        omode = oclasses->get_mode();
+                }
+                assertf( oclasses == classes, "classes must be versions of the same map" );
+
+                /// Edit item for binding changes
+                struct BEdit {
+                        Bindings::Mode mode;  ///< Type of change to a key
+                        BoundType val;        ///< Updated key value, if applicable
+
+                        BEdit(Bindings::Mode m) : mode{m}, val{} {}
+                        BEdit(Bindings::Mode m, const BoundType& b) : mode{m}, val{b} {}
+                };
+
+                // track binding merges
+                bindings->reroot();
+                std::unordered_map<interned_string, BEdit> bedits; // edits to base bindings
+
+                // trace path from other environment
+                const Bindings* bbindings = o.bindings;
+                Bindings::Mode bmode = bbindings->get_mode();
+                while ( bmode != Bindings::BASE ) {
+                        interned_string key = bbindings->get_key();
+                        auto it = bedits.find( key );
+
+                        if ( it == bedits.end() ) {
+                                // newly seen key, mark operation
+                                if ( bmode == Bindings::REM ) {
+                                        bedits.emplace_back( it, key, BEdit{ bmode } );
+                                } else {
+                                        bedits.emplace_back( it, key, BEdit{ bmode, bbindings->get_val() } );
+                                }
+                        } else {
+                                Bindings::Mode& smode = it->second.mode;
+                                switch ( bmode ) {
+                                        case Bindings::REM: {
+                                                // later insertion, change to update
+                                                assertf( smode == Bindings::INS, "inconsistent mode" );
+                                                smode = Bindings::UPD;
+                                        } break;
+                                        case Bindings::INS: {
+                                                switch ( smode ) {
+                                                        case Bindings::REM: {
+                                                                // later removal, no net change to map
+                                                                bedits.erase( it );
+                                                        } break;
+                                                        case Bindings::UPD: {
+                                                                // later update collapses to insertion
+                                                                smode = Bindings::INS;
+                                                        } break;
+                                                        default: assertf( false, "inconsistent mode" );
+                                                }
+                                        } break;
+                                        case Bindings::UPD: {
+                                                // later removal or update overrides this update
+                                                assertf( smode == Bindings::REM || smode == Bindings::UPD, "inconsistent mode" );
+                                        } break;
+                                        default: assertf( false, "invalid mode" );
+                                }
+                        }
+
+                        bbindings = bbindings->get_base();
+                        bmode = bbindings->get_mode();
+                }
+                assume( bbindings == bindings, "bindings must be versions of same map" );
+
+                // merge typeclasses (always possible, can always merge all classes into one if the 
+                // bindings unify)
+                for ( const EditEntry& edit : edits ) {
+                        interned_string key = edit.first;
+                        const Edit& e = edit.second;
+
+                        switch ( e.mode ) {
+                                case Classes::ADD: {
+                                        // add new type variable
+                                        classes = classes->add( key );
+                                        // add binding for variable
+                                        auto bit = bedits.find( key );
+                                        if ( bit != bedits.end() ) {
+                                                // take final value if it is a root in its own map
+                                                const BEdit& be = bit->second;
+                                                assertf( be.mode == Bindings::INS, "inconsistent binding" );
+                                                bindings = bindings->set( key, std::move(be.val) );
+                                                // remove update from edit set so that it isn't re-checked
+                                                bedits.erase( bit );
+                                        } else {
+                                                // otherwise just put in default binding
+                                                bindings = bindings->set( key, BoundType{} );
+                                        }
+                                } break;
+                                case Classes::REM: {
+                                        // do not remove type variable (merging)
+                                } break;
+                                case Classes::ADDTO: {
+                                        // if previous REMFROM on this key, or ADDTO on this root, may not match 
+                                        // current state in `classes`
+                                        interned_string key_root = classes->find( key );
+                                        interned_string merge_root = classes->find( e.root );
+                                        // skip case where classes already merged
+                                        if ( key_root == merge_root ) break;
+                                        // merge classes and remove binding for new child
+                                        interned_string new_child = mergeClasses( key_root, merge_root ).second;
+                                        if ( bindings->count( new_child ) ) {
+                                                // add new insert edit to check merge with old value if needed
+                                                const BoundType& child_bind = bindings->get( new_child );
+                                                if ( child_bind.type ) {
+                                                        // store this insert under the original key, which must be a REM 
+                                                        // binding change if present
+                                                        auto bit = bedits.find( key );
+                                                        if ( bit != bedits.end() ) {
+                                                                BEdit& be = bit->second;
+                                                                assertf( be.mode == Bindings::REM, "inconsistent binding" );
+                                                                be = BEdit{ Bindings::INS, child_bind };
+                                                        } else {
+                                                                bedits.emplace_hint( bit, key, BEdit{ Bindings::INS, child_bind } );
+                                                        }
+                                                }
+                                                // remove child binding from map
+                                                bindings = bindings->erase( new_child );
+                                        }
+                                } break;
+                                case Classes::REMFROM: {
+                                        // do not split classes
+                                } break;
+                                default: assertf( false, "invalid mode" );
+                        }
+                }
+
+                // finish merging bindings. This may fail, or may merge further classes
+                for ( const auto& entry : bedits ) {
+                        interned_string key = entry.first;
+                        const BEdit& e = entry.second;
+
+                        // skip binding removals; the ADDTO merge has taken out all the new non-roots
+                        if ( e.mode == Bindings::REM ) continue;
+                        assertf( e.mode == Bindings::UPD || e.mode == Bindings::INS, "inconsistent binding" );
+
+                        // attempt binding update
+                        interned_string root = classes->find( key );
+                        BoundType ebound = bindings->get( root );
+                        const BoundType& nbound = e.val;
+
+                        if ( ebound.type && nbound.type ) {
+                                // attempt to unify bound classes
+                                Type* common = nullptr;
+                                AssertionSet need, have;
+                                OpenVarSet openVars;
+                                if ( unifyInexact( ebound.type->clone(), nbound.type->clone(), *this, need, have, 
+                                                openVars, WidenMode{ ebound.allowWidening, nbound.allowWidening }, 
+                                                indexer, common ) ) {
+                                        // update bindings
+                                        ebound.allowWidening &= nbound.allowWidening;
+                                        if ( common ) {
+                                                common->get_qualifiers() = Type::Qualifiers{};
+                                                ebound.type = common;
+                                        }
+                                        // reset root in case updated in course of unification
+                                        bindings = bindings->set( classes->find( root ), ebound );
+                                } else return false;  // cannot unify bindings
+                        }
+                }
+
+                return true;
+        }
+
         void TypeEnvironment::extractOpenVars( OpenVarSet &openVars ) const {
                 bindings->for_each( [&]( interned_string root, const BoundType& bound ) {

src/ResolvExpr/TypeEnvironment.h

@@ -221 +221 @@
                 /// Caller should ensure environments do not share type variables.
                 void simpleCombine( const TypeEnvironment &second );
+
+                /// Combines two environments, checking compatibility. Both environments must be versioned 
+                /// from the same initial environment.
+                /// Returns false if unsuccessful, but does NOT roll back partial changes
+                bool combine( const TypeEnvironment& o, const SymTab::Indexer& indexer );
         
                 void extractOpenVars( OpenVarSet &openVars ) const;