Changeset d0c91a6 for src/ResolvExpr/TypeEnvironment.cc

Timestamp:

Jan 15, 2019, 4:16:15 PM (7 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, no_list, persistent-indexer, pthread-emulation, qualifiedEnum

Children:

c802eb88

Parents:

5e49e47 (diff), c9aba81 (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.

Message:

Merge branch 'master' into jenkins-sandbox

File:

• src/ResolvExpr/TypeEnvironment.cc (modified) (4 diffs)

src/ResolvExpr/TypeEnvironment.cc

@@ -120 +120 @@
 
         const EqvClass* TypeEnvironment::lookup( const std::string &var ) const {
-                for ( std::list< EqvClass >::const_iterator i = env.begin(); i != env.end(); ++i ) {
+                for ( ClassList::const_iterator i = env.begin(); i != env.end(); ++i ) {
                         if ( i->vars.find( var ) != i->vars.end() ) return &*i;
                 } // for
@@ -168 +168 @@
 
         void TypeEnvironment::makeSubstitution( TypeSubstitution &sub ) const {
-                for ( std::list< EqvClass >::const_iterator theClass = env.begin(); theClass != env.end(); ++theClass ) {
+                for ( ClassList::const_iterator theClass = env.begin(); theClass != env.end(); ++theClass ) {
                         for ( std::set< std::string >::const_iterator theVar = theClass->vars.begin(); theVar != theClass->vars.end(); ++theVar ) {
                                 if ( theClass->type ) {
@@ -188 +188 @@
         }
 
-        std::list< EqvClass >::iterator TypeEnvironment::internal_lookup( const std::string &var ) {
-                for ( std::list< EqvClass >::iterator i = env.begin(); i != env.end(); ++i ) {
+        TypeEnvironment::ClassList::iterator TypeEnvironment::internal_lookup( const std::string &var ) {
+                for ( ClassList::iterator i = env.begin(); i != env.end(); ++i ) {
                         if ( i->vars.count( var ) ) return i;
                 } // for
@@ -199 +199 @@
         }
 
+        // xxx -- this should maybe be worrying about iterator invalidation (see resolv-proto)
+        bool TypeEnvironment::mergeBound( EqvClass& to, const EqvClass& from, OpenVarSet& openVars, const SymTab::Indexer& indexer ) {
+                if ( from.type ) {
+                        if ( to.type ) {
+                                // attempt to unify bound types
+                                std::unique_ptr<Type> toType{ to.type->clone() }, fromType{ from.type->clone() };
+                                WidenMode widenMode{ to.allowWidening, from.allowWidening };
+                                Type* common = nullptr;
+                                AssertionSet need, have;
+                                if ( unifyInexact( toType.get(), fromType.get(), *this, need, have, openVars, widenMode, indexer, common ) ) {
+                                        // unifies, set common type if necessary
+                                        if ( common ) {
+                                                common->get_qualifiers() = Type::Qualifiers{};
+                                                to.set_type( common );
+                                        }
+                                } else return false; // cannot unify
+                        } else {
+                                to.type = from.type->clone();
+                        }
+                }
+
+                // unify widening if matches
+                to.allowWidening &= from.allowWidening;
+                return true;
+        }
+
+        // xxx -- this should maybe be worrying about iterator invalidation (see resolv-proto)
+        bool TypeEnvironment::mergeClasses( TypeEnvironment::ClassList::iterator to, TypeEnvironment::ClassList::iterator from, OpenVarSet& openVars, const SymTab::Indexer& indexer ) {
+                EqvClass& r = *to;
+                EqvClass& s = *from;
+
+                // ensure bounds match
+                if ( ! mergeBound( r, s, openVars, indexer ) ) return false;
+
+                // check safely bindable
+                if ( r.type && occursIn( r.type, s.vars.begin(), s.vars.end(), *this ) ) return false;
+                
+                // merge classes in
+                r.vars.insert( s.vars.begin(), s.vars.end() );
+                r.allowWidening &= s.allowWidening;
+                env.erase( from );
+
+                return true;
+        }
+
+        bool TypeEnvironment::combine( const TypeEnvironment& o, OpenVarSet& openVars, const SymTab::Indexer& indexer ) {
+                // short-circuit easy cases
+                if ( o.isEmpty() ) return true;
+                if ( isEmpty() ) {
+                        simpleCombine( o );
+                        return true;
+                }
+
+                // merge classes
+                for ( auto ct = o.env.begin(); ct != o.env.end(); ++ct ) {
+                        const EqvClass& c = *ct;
+
+                        // typeclass in local environment bound to c
+                        auto rt = env.end();
+
+                        // look for first existing bound variable
+                        auto vt = c.vars.begin();
+                        for ( ; vt != c.vars.end(); ++vt ) {
+                                rt = internal_lookup( *vt );
+                                if ( rt != env.end() ) break;
+                        }
+
+                        if ( rt != env.end() ) {  // c needs to be merged into *rt
+                                EqvClass& r = *rt;
+                                // merge bindings
+                                if ( ! mergeBound( r, c, openVars, indexer ) ) return false;
+                                // merge previous unbound variables into this class, checking occurs if needed
+                                if ( r.type ) for ( auto ut = c.vars.begin(); ut != vt; ++ut ) {
+                                        if ( occurs( r.type, *ut, *this ) ) return false;
+                                        r.vars.insert( *ut );
+                                } else { r.vars.insert( c.vars.begin(), vt ); }
+                                // merge subsequent variables into this class (skipping *vt, already there)
+                                while ( ++vt != c.vars.end() ) {
+                                        auto st = internal_lookup( *vt );
+                                        if ( st == env.end() ) {
+                                                // unbound, safe to add if passes occurs
+                                                if ( r.type && occurs( r.type, *vt, *this ) ) return false;
+                                                r.vars.insert( *vt );
+                                        } else if ( st != rt ) {
+                                                // bound, but not to the same class
+                                                if ( ! mergeClasses( rt, st, openVars, indexer ) ) return false;
+                                        }   // ignore bound into the same class
+                                }
+                        } else {  // no variables in c bound; just copy up
+                                env.push_back( c );
+                        }
+                }
+
+                // merged all classes
+                return true;
+        }
+
         void TypeEnvironment::extractOpenVars( OpenVarSet &openVars ) const {
-                for ( std::list< EqvClass >::const_iterator eqvClass = env.begin(); eqvClass != env.end(); ++eqvClass ) {
+                for ( ClassList::const_iterator eqvClass = env.begin(); eqvClass != env.end(); ++eqvClass ) {
                         for ( std::set< std::string >::const_iterator var = eqvClass->vars.begin(); var != eqvClass->vars.end(); ++var ) {
                                 openVars[ *var ] = eqvClass->data;