Changeset 9ad2f9f for src

Timestamp:

Oct 3, 2018, 5:08:14 PM (6 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

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

Children:

59cf83b

Parents:

588c2b0

Message:

TypeEnvironment::combine -- compiles, untested

Location:

src/ResolvExpr

Files:

• TypeEnvironment.cc (modified) (4 diffs)
• TypeEnvironment.h (modified) (5 diffs)
• typeops.h (modified) (1 diff)

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;

src/ResolvExpr/TypeEnvironment.h

@@ -39 +39 @@
         // declarations.
         //
-        // I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this comparator.
+        // I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this 
+        // comparator.
         //
         // Note: since this compares pointers for position, minor changes in the source file that affect
         // memory layout can alter compilation time in unpredictable ways. For example, the placement
         // of a line directive can reorder type pointers with respect to each other so that assertions
-        // are seen in different orders, causing a potentially different number of unification calls when
-        // resolving assertions. I've seen a TU go from 36 seconds to 27 seconds by reordering line directives
-        // alone, so it would be nice to fix this comparison so that assertions compare more consistently.
-        // I've tried to modify this to compare on mangle name instead of type as the second comparator, but
-        // this causes some assertions to never be recorded. More investigation is needed.
+        // are seen in different orders, causing a potentially different number of unification calls 
+        // when resolving assertions. I've seen a TU go from 36 seconds to 27 seconds by reordering 
+        // line directives alone, so it would be nice to fix this comparison so that assertions compare 
+        // more consistently. I've tried to modify this to compare on mangle name instead of type as 
+        // the second comparator, but this causes some assertions to never be recorded. More 
+        // investigation is needed.
         struct AssertCompare {
                 bool operator()( DeclarationWithType * d1, DeclarationWithType * d2 ) const {
@@ -58 +60 @@
         struct AssertionSetValue {
                 bool isUsed;
-                // chain of Unique IDs of the assertion declarations. The first ID in the chain is the ID of an assertion on the current type,
-                // with each successive ID being the ID of an assertion pulled in by the previous ID. The last ID in the chain is
-                // the ID of the assertion that pulled in the current assertion.
+                // chain of Unique IDs of the assertion declarations. The first ID in the chain is the ID 
+                // of an assertion on the current type, with each successive ID being the ID of an 
+                // assertion pulled in by the previous ID. The last ID in the chain is the ID of the 
+                // assertion that pulled in the current assertion.
                 std::list< UniqueId > idChain;
         };
@@ -91 +94 @@
 
         class TypeEnvironment {
+                using ClassList = std::list< EqvClass >;
           public:
                 const EqvClass* lookup( const std::string &var ) const;
@@ -103 +107 @@
                 bool isEmpty() const { return env.empty(); }
                 void print( std::ostream &os, Indenter indent = {} ) const;
-                // void combine( const TypeEnvironment &second, Type *(*combineFunc)( Type*, Type* ) );
+                
+                /// Simply concatenate the second environment onto this one; no safety checks performed
                 void simpleCombine( const TypeEnvironment &second );
+
+          private:
+                /// Unifies the type bound of to with the type bound of from, returning false if fails
+                bool mergeBound( EqvClass& to, const EqvClass& from, OpenVarSet& openVars, const SymTab::Indexer& indexer );
+
+                /// Merges two type classes from local environment, returning false if fails
+                bool mergeClasses( ClassList::iterator to, ClassList::iterator from, OpenVarSet& openVars, const SymTab::Indexer& indexer );
+
+          public:
+                /// Merges the second environment with this one, checking compatibility.
+                /// Returns false if fails, but does NOT roll back partial changes.
+                bool combine( const TypeEnvironment& second, OpenVarSet& openVars, const SymTab::Indexer& indexer );
+                
                 void extractOpenVars( OpenVarSet &openVars ) const;
                 TypeEnvironment *clone() const { return new TypeEnvironment( *this ); }
@@ -123 +141 @@
                 void forbidWidening();
 
-                using iterator = std::list< EqvClass >::const_iterator;
+                using iterator = ClassList::const_iterator;
                 iterator begin() const { return env.begin(); }
                 iterator end() const { return env.end(); }
 
           private:
-                std::list< EqvClass > env;
+                ClassList env;
                 
-                std::list< EqvClass >::iterator internal_lookup( const std::string &var );
+                ClassList::iterator internal_lookup( const std::string &var );
         };
 

src/ResolvExpr/typeops.h

@@ -108 +108 @@
         bool occurs( Type *type, std::string varName, const TypeEnvironment &env );
 
+        template<typename Iter> 
+        bool occursIn( Type* ty, Iter begin, Iter end, const TypeEnvironment &env ) {
+                while ( begin != end ) {
+                        if ( occurs( ty, *begin, env ) ) return true;
+                        ++begin;
+                }
+                return false;
+        }
+
         // in AlternativeFinder.cc
         void referenceToRvalueConversion( Expression *& expr, Cost & cost );