Index: src/ResolvExpr/TypeEnvironment.cc =================================================================== --- src/ResolvExpr/TypeEnvironment.cc (revision eff03a94a7c9efb0da9adc3ba0df25839eeaed04) +++ src/ResolvExpr/TypeEnvironment.cc (revision f89a1117ebfa413600d50598186beaf567f673bf) @@ -17,4 +17,7 @@ #include // for copy, set_intersection #include // for ostream_iterator, insert_iterator +#include // for list +#include // for vector +#include // for unordered_map #include // for pair, move @@ -408,4 +411,269 @@ } + 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; + using EditList = std::list; + using IndexedEdits = std::vector; + + EditList edits; + std::unordered_map 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 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 ) { Index: src/ResolvExpr/TypeEnvironment.h =================================================================== --- src/ResolvExpr/TypeEnvironment.h (revision eff03a94a7c9efb0da9adc3ba0df25839eeaed04) +++ src/ResolvExpr/TypeEnvironment.h (revision f89a1117ebfa413600d50598186beaf567f673bf) @@ -221,4 +221,9 @@ /// 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;