Changeset b067d9b for src/ResolvExpr/TypeEnvironment.h

Timestamp:

Oct 29, 2019, 4:01:24 PM (6 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

773db65, 9421f3d8

Parents:

7951100 (diff), 8364209 (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' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:

• src/ResolvExpr/TypeEnvironment.h (modified) (8 diffs)

src/ResolvExpr/TypeEnvironment.h

@@ -9 +9 @@
 // Author           : Richard C. Bilson
 // Created On       : Sun May 17 12:24:58 2015
-// Last Modified By : Peter A. Buhr
-// Last Modified On : Sat Jul 22 09:35:45 2017
-// Update Count     : 3
+// Last Modified By : Andrew Beach
+// Last Modified On : Fri Jul 19 17:00:10 2019
+// Update Count     : 10
 //
 
@@ -18 +18 @@
 #include <iostream>                    // for ostream
 #include <list>                        // for list, list<>::iterator, list<>...
-#include <map>                         // for map, map<>::value_compare
-#include <set>                         // for set
+#include <map>                                             // for map, map<>::value_compare
+#include <unordered_map>
+#include <set>                                             // for set
 #include <string>                      // for string
+#include <utility>                     // for move, swap
+
+#include "WidenMode.h"                 // for WidenMode
 
 #include "SynTree/Declaration.h"       // for TypeDecl::Data, DeclarationWit...
@@ -36 +40 @@
         // 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 {
+                bool operator()( const DeclarationWithType * d1, const DeclarationWithType * d2 ) const {
                         int cmp = d1->get_name().compare( d2->get_name() );
                         return cmp < 0 ||
@@ -54 +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.
-                std::list< UniqueId > idChain;
+                bool isUsed;        ///< True if assertion needs to be resolved
+                UniqueId resnSlot;  ///< ID of slot assertion belongs to
+
+                AssertionSetValue() : isUsed(false), resnSlot(0) {}
         };
-        typedef std::map< DeclarationWithType*, AssertionSetValue, AssertCompare > AssertionSet;
-        typedef std::map< std::string, TypeDecl::Data > OpenVarSet;
+        typedef std::map< const DeclarationWithType *, AssertionSetValue, AssertCompare > AssertionSet;
+        typedef std::unordered_map< std::string, TypeDecl::Data > OpenVarSet;
+
+        /// merges one set of open vars into another
+        static inline void mergeOpenVars( OpenVarSet& dst, const OpenVarSet& src ) {
+                for ( const auto& entry : src ) { dst[ entry.first ] = entry.second; }
+        }
 
         void printAssertionSet( const AssertionSet &, std::ostream &, int indent = 0 );
@@ -68 +78 @@
         struct EqvClass {
                 std::set< std::string > vars;
-                Type *type;
+                Type * type;
                 bool allowWidening;
                 TypeDecl::Data data;
@@ -77 +87 @@
                 EqvClass( const EqvClass &other );
                 EqvClass( const EqvClass &other, const Type *ty );
+                EqvClass( EqvClass &&other );
                 EqvClass &operator=( const EqvClass &other );
+                EqvClass &operator=( EqvClass &&other );
                 ~EqvClass();
                 void print( std::ostream &os, Indenter indent = {} ) const;
+
+                /// Takes ownership of `ty`, freeing old `type`
+                void set_type(Type* ty);
         };
 
         class TypeEnvironment {
+                using ClassList = std::list< EqvClass >;
           public:
                 const EqvClass* lookup( const std::string &var ) const;
-                void add( const EqvClass &eqvClass );
+          private:
                 void add( EqvClass &&eqvClass  );
+          public:
                 void add( const Type::ForallList &tyDecls );
                 void add( const TypeSubstitution & sub );
@@ -94 +111 @@
                 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 ); }
@@ -103 +134 @@
                 void addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars );
 
-                typedef std::list< EqvClass >::iterator iterator;
-                iterator begin() { return env.begin(); }
-                iterator end() { return env.end(); }
-                typedef std::list< EqvClass >::const_iterator const_iterator;
-                const_iterator begin() const { return env.begin(); }
-                const_iterator end() const { return env.end(); }
+                /// Binds the type class represented by `typeInst` to the type `bindTo`; will add
+                /// the class if needed. Returns false on failure.
+                bool bindVar( const TypeInstType * typeInst, Type * bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer );
+
+                /// Binds the type classes represented by `var1` and `var2` together; will add
+                /// one or both classes if needed. Returns false on failure.
+                bool bindVarToVar( const TypeInstType * var1, const TypeInstType * var2, TypeDecl::Data && data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer );
+
+                /// Disallows widening for all bindings in the environment
+                void forbidWidening();
+
+                using iterator = ClassList::const_iterator;
+                iterator begin() const { return env.begin(); }
+                iterator end() const { return env.end(); }
+
           private:
-                std::list< EqvClass > env;
-                std::list< EqvClass >::iterator internal_lookup( const std::string &var );
+                ClassList env;
+
+                ClassList::iterator internal_lookup( const std::string &var );
         };