Changeset d318a18

Timestamp:

Jul 18, 2018, 5:18:29 PM (6 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

new-env

Children:

eff03a94

Parents:

5c14030

Message:

Fix assorted memory bugs with persistent-array environment

Location:

src

Files:

• Common/GC.cc (modified) (2 diffs)
• Common/GC.h (modified) (1 diff)
• Common/PersistentDisjointSet.h (modified) (3 diffs)
• Common/PersistentMap.h (modified) (4 diffs)
• ResolvExpr/TypeEnvironment.cc (modified) (11 diffs)
• ResolvExpr/TypeEnvironment.h (modified) (3 diffs)
• SynTree/GcTracer.h (modified) (3 diffs)

src/Common/GC.cc

@@ -41 +41 @@
 
 const GC& GC::operator<< (const GC_Object* obj) const {
-        if( obj )
-        {
+        if( obj ) {
                 if( obj->mark != this->mark ) {
                         obj->mark = this->mark;
@@ -49 +48 @@
         }
         return *this;
+}
+
+bool GC::notrace_mark(const GC_Object* obj) const {
+        if ( obj && obj->mark != this->mark ) {
+                obj->mark = this->mark;
+                return true;
+        }
+        return false;
 }
 

src/Common/GC.h

@@ -38 +38 @@
         /// Traces a traceable object
         const GC& operator<< (const GC_Object*) const;
+
+        /// No-trace mark; returns true if the object exists and was not already marked
+        bool notrace_mark(const GC_Object*) const;
 
         /// Adds a new object to garbage collection

src/Common/PersistentDisjointSet.h

@@ -281 +281 @@
         const Base& rerooted() const {
                 reroot();
+                assertf(mode == BASE, "reroot results in base");
                 return as<Base>();
         }
@@ -332 +333 @@
         }
 
-        /// Adds fresh class including only one item; returns updated map
+        /// Adds fresh class including only one item; returns updated map (or self if no change)
         template<typename E>
         Self* add(E&& i) {
                 reroot();
-                
-                // transfer map to new node
-                Self* ret = new Self{ BASE, take_as<Base>() };
+
+                // add new element to node
+                Base base_map = take_as<Base>();
+                bool added = base_map.emplace( i, Node{ i } ).second;
+
+                // fail early on node already present
+                if ( ! added ) {
+                        as<Base>() = std::move(base_map);
+                        return this;
+                }
+
+                // make new return node and reset self as REM node
+                Self* ret = new Self{ BASE, std::move(base_map) };
                 reset_as_base();
-
-                // set self to REM node
                 init<Add>( ret, i );
                 mode = REM;
-                
-                // add element in returned map
-                Base& base_map = ret->as<Base>();
-                bool added = base_map.emplace( i, Node{ std::forward<E>(i) } ).second;
-                assertf(added, "added element already present in map");
 
                 return ret;
@@ -460 +464 @@
                 const Base& self = rerooted();
 
-                Elm crnt = i;
-                do {
+                // exit early if class not present
+                auto it = self.find( i );
+                if ( it == self.end() ) return;
+
+                // apply f to each member of class
+                f( i );
+                for ( Elm crnt = it->second.next; crnt != i; crnt = it->second.next ) {
                         f( crnt );
-                        auto it = self.find( crnt );
+                        it = self.find( crnt );
                         assertf( it != self.end(), "current node must exist in base" );
-                        crnt = it->second.next;
-                } while ( crnt != i );
+                }
         }
 

src/Common/PersistentMap.h

@@ -141 +141 @@
                                         gc.maybe_trace( entry.first, entry.second );
                                 }
-                                return;
-                        }
+                        } break;
                         case REM: {
                                 const Rem& self = as<Rem>();
                                 gc << self.base;
                                 gc.maybe_trace( self.key );
-                                return;
-                        }
+                        } break;
                         case INS: case UPD: {
                                 const Ins& self = as<Ins>();
                                 gc << self.base;
                                 gc.maybe_trace( self.key, self.val );
-                                return;
-                        }
+                        } break;
                         default: assertf(false, "invalid mode");
                 }
@@ -198 +195 @@
 
                                 base_map.erase( it );
-                                break;
-                        }
+                        } break;
                         case INS: {
                                 Ins& self = mut_this->as<Ins>();
@@ -207 +203 @@
 
                                 base_map.emplace( std::move(self.key), std::move(self.val) );
-                                break;
-                        }
+                        } break;
                         case UPD: {
                                 Ins& self = mut_this->as<Ins>();
@@ -218 +213 @@
 
                                 it->second = std::move(self.val);
-                                break;
-                        }
+                        } break;
                         default: assertf(false, "invalid mode");
                 }

src/ResolvExpr/TypeEnvironment.cc

@@ -33 +33 @@
 
 namespace ResolvExpr {
+        #if 1
+        #define PRE_POST_VALIDATE auto dbg = ValidateGuard{this, __func__};
+        #define PRE_POST_VALIDATE_NOM auto dbg = ValidateGuard{this};
+        struct ValidateGuard {
+                const TypeEnvironment* env;
+                const TypeEnvironment::Classes* old_classes;
+                const TypeEnvironment::Bindings* old_bindings;
+                const char* last_fn;
+
+                void validate_classes( const TypeEnvironment::Classes* c ) {
+                        typedef TypeEnvironment::Classes C;
+
+                        assertf( c != nullptr, "classes non-null" );
+                        
+                        C::Mode cmode = c->get_mode();
+                        if ( cmode == C::BASE ) {
+                                // xxx - consistency checks
+                        } else {
+                                assertf( cmode == C::ADD || cmode == C::REM || cmode == C::ADDTO || cmode == C::REMFROM, "valid classes mode" );
+                                validate_classes( c->get_base() );
+                        }
+                }
+
+                void validate_bindings( const TypeEnvironment::Bindings* b ) {
+                        typedef TypeEnvironment::Bindings B;
+
+                        assertf( b != nullptr, "bindings non-null" );
+
+                        B::Mode bmode = b->get_mode();
+                        if ( bmode == B::BASE ) {
+                                // xxx - consistency checks
+                        } else {
+                                assertf( bmode == B::REM || bmode == B::INS || bmode == B::UPD, "valid bindings mode" );
+                                validate_bindings( b->get_base() );
+                        }
+                }
+
+                void validate_env() {
+                        validate_classes( env->classes );
+                        validate_bindings( env->bindings );
+                        
+                        // xxx - joint validation
+                }
+
+                ValidateGuard(const TypeEnvironment* e)
+                        : env{e}, old_classes{e->classes}, old_bindings{e->bindings}, last_fn{e->last_fn}
+                        { validate_env(); }
+                ValidateGuard(const TypeEnvironment* e, const char* fn)
+                        : env{e}, old_classes{e->classes}, old_bindings{e->bindings}, last_fn{fn} 
+                        { validate_env(); }
+                ~ValidateGuard() {
+                        validate_env();
+                        if ( env->classes != old_classes ) validate_classes( old_classes );
+                        if ( env->bindings != old_bindings ) validate_bindings( old_bindings );
+                        const_cast<TypeEnvironment*>(env)->last_fn = last_fn;
+                }
+        };
+        #else
+        #define PRE_POST_VALIDATE
+        #define PRE_POST_VALIDATE_NOM
+        #endif
+
         void printAssertionSet( const AssertionSet &assertions, std::ostream &os, int indent ) {
                 for ( AssertionSet::const_iterator i = assertions.begin(); i != assertions.end(); ++i ) {
@@ -53 +115 @@
         std::pair<interned_string, interned_string> TypeEnvironment::mergeClasses( 
                         interned_string root1, interned_string root2 ) {
+                PRE_POST_VALIDATE
                 // merge classes
                 Classes* newClasses = classes->merge( root1, root2 );
@@ -100 +163 @@
                         const TypeDecl::Data& data, AssertionSet& need, AssertionSet& have, 
                         const OpenVarSet& openVars, WidenMode widenMode, const SymTab::Indexer& indexer ) {
+                PRE_POST_VALIDATE
                 // remove references from other, so that type variables can only bind to value types
                 bindTo = bindTo->stripReferences();
@@ -148 +212 @@
                         const TypeDecl::Data& data, AssertionSet& need, AssertionSet& have, 
                         const OpenVarSet& openVars, WidenMode widenMode, const SymTab::Indexer& indexer ) {
+                PRE_POST_VALIDATE
                 ClassRef class1 = lookup( var1->get_name() );
                 ClassRef class2 = lookup( var2->get_name() );
@@ -237 +302 @@
 
         void TypeEnvironment::add( const Type::ForallList &tyDecls ) {
+                PRE_POST_VALIDATE
                 for ( Type::ForallList::const_iterator i = tyDecls.begin(); i != tyDecls.end(); ++i ) {
                         interned_string name = (*i)->get_name();
@@ -245 +311 @@
 
         void TypeEnvironment::add( const TypeSubstitution & sub ) {
+                PRE_POST_VALIDATE
                 interned_string not_found{nullptr};
 
@@ -251 +318 @@
                         
                         // filter overlapping classes out of existing environment
-                        // (this is a very shady assumption, but has worked for a long time...)
+                        // xxx - this is a very shady assumption, but has worked for a long time...
                         interned_string root = classes->find_or_default( var, not_found );
                         if ( root != not_found ) {
@@ -270 +337 @@
 
         void TypeEnvironment::makeSubstitution( TypeSubstitution &sub ) const {
+                PRE_POST_VALIDATE_NOM
                 bindings->for_each([&]( interned_string root, const BoundType& bound ){
                         classes->for_class(root, [&]( interned_string var ) {
@@ -300 +368 @@
         }
 
+        namespace {
+                // temporary representation of an equivalence class
+                struct EqvClass {
+                        std::vector<interned_string> vars;
+                        BoundType bound;
+
+                        EqvClass() = default;
+                        EqvClass(const BoundType& b) : bound{b} {}
+                };
+        }
+
         void TypeEnvironment::simpleCombine( const TypeEnvironment &o ) {
+                PRE_POST_VALIDATE
+                // check for same environment
+                if ( classes == o.classes && bindings == o.bindings ) return;
+
+                // read out equivalence classes (avoids conflicting reroots)
+                std::vector<EqvClass> ecs;
                 o.bindings->for_each( [&]( interned_string root, const BoundType& bound ) {
-                        // add members of new class
+                        ecs.emplace_back(bound);
+                        o.classes->for_class( root, [&]( interned_string var ) {
+                                ecs.back().vars.push_back( var );
+                        } );
+                } );
+
+                // read equivalence classes into self
+                for ( EqvClass& ec : ecs ) {
+                        // merge vars
                         interned_string new_root{nullptr};
-                        o.classes->for_class( root, [this,&new_root]( interned_string var ) {
-                                classes = classes->add( var );
+                        for ( interned_string var : ec.vars ) {
+                                Classes* new_classes = classes->add( var );
+                                if ( new_classes == classes ) { var = classes->find( var ); }
+                                else { classes = new_classes; }
                                 new_root = new_root ? mergeClasses( new_root, var ).first : var;
-                        });
-                        // set binding for new class
-                        bindings = bindings->set( new_root, bound );
-                });
+                        }
+                        // set binding
+                        bindings = bindings->set( new_root, ec.bound );
+                }
         }
 
@@ -322 +417 @@
 
         void TypeEnvironment::addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars ) {
+                PRE_POST_VALIDATE
+                if ( classes == actualEnv.classes && bindings == actualEnv.bindings ) {
+                        // actualEnv already the same, just need to update openVars
+                        extractOpenVars( openVars );
+                        return;
+                } else assertf(classes != actualEnv.classes && bindings != actualEnv.bindings, "classes & bindings updated together");
+
+                // read out equivalence classes (avoids conflicting reroots)
+                std::vector<EqvClass> ecs;
                 actualEnv.bindings->for_each( [&]( interned_string root, const BoundType& bound ) {
-                        // add members of new class, setting openVars concurrently
+                        ecs.emplace_back(bound);
+                        actualEnv.classes->for_class( root, [&]( interned_string var ) {
+                                ecs.back().vars.push_back( var );
+                        } );
+                } );
+
+                // add members of new class, setting openVars concurrently
+                for ( EqvClass& ec : ecs ) {
+                        // merge vars
                         interned_string new_root{nullptr};
-                        actualEnv.classes->for_class( root, [&]( interned_string var ) {
-                                classes = classes->add( var );
+                        for ( interned_string var : ec.vars ) {
+                                openVars[ var ] = ec.bound.data;
+                                Classes* new_classes = classes->add( var );
+                                if ( new_classes == classes ) {
+                                        // xxx - this case is a bit sketchy, but has been working
+                                        // xxx - merging the classes is a departure from previous behaviour
+                                        var = classes->find( var );
+                                } else { classes = new_classes; }
                                 new_root = new_root ? mergeClasses( new_root, var ).first : var;
-                                openVars[ var ] = bound.data;
-                        } );
-                        // add new type binding without widening
+                        }
+                        // set binding without widening
                         bindings = bindings->set( new_root, 
-                                BoundType{ maybeClone(bound.type), false, bound.data } );
-                } );
+                                BoundType{ maybeClone(ec.bound.type), false, ec.bound.data } );
+                }
         }
 
         void TypeEnvironment::forbidWidening() {
+                PRE_POST_VALIDATE
                 bindings = bindings->mutate_each([]( const interned_string&, BoundType& c ) {
                         if ( c.allowWidening ) {
@@ -352 +470 @@
 
         PassVisitor<GcTracer> & operator<<( PassVisitor<GcTracer> & gc, const TypeEnvironment & env ) {
-                for ( ClassRef c : env ) {
-                        maybeAccept( c.get_bound().type, gc );
-                }
+                gc.pass.visit( env );
+                // for ( ClassRef c : env ) {
+                //      maybeAccept( c.get_bound().type, gc );
+                // }
                 return gc;
         }

src/ResolvExpr/TypeEnvironment.h

@@ -138 +138 @@
         };
 
+        class ValidateGuard;
+
         class TypeEnvironment {
                 friend ClassRef;
-
+                friend GcTracer;
+                
                 /// Backing storage for equivalence classes
                 using Classes = PersistentDisjointSet<interned_string>;
@@ -152 +155 @@
                 /// may be null.
                 Bindings* bindings;
+
+                // for debugging
+                friend ValidateGuard;
+                const char* last_fn = "<none>";
 
                 /// Merges the classes rooted at root1 and root2, returning a pair containing the root and 
@@ -234 +241 @@
         T ClassRef::get_vars() const {
                 T vars;
-                if ( ! env->classes->count( root ) ) return vars;
                 env->classes->for_class( root, [&vars]( interned_string var ) {
                         vars.insert( vars.end(), var );

src/SynTree/GcTracer.h

@@ -25 +25 @@
 #include "Common/GC.h"
 #include "Common/PassVisitor.h"
-
-class Expression;
+#include "ResolvExpr/TypeEnvironment.h"
 
 /// Implements `trace` method for syntax nodes
@@ -34 +33 @@
 public:
         GcTracer( const GC& gc ) : gc(gc) {}
+
+        template<typename... Args>
+        void traceAll(Args&... args) { ::traceAll(gc, args...); }
 
         // mark node and children
@@ -151 +153 @@
                 maybeAccept( type->baseUnion, *visitor );
         }
+
+private:
+        void visit( const ResolvExpr::TypeEnvironment::Classes* c ) {
+                typedef ResolvExpr::TypeEnvironment::Classes C;
+                // trace all parent classes, short-circuiting at one traced
+                while ( gc.notrace_mark( c ) && c->get_mode() != C::BASE ) { c = c->get_base(); }
+        }
+
+        void visit( const ResolvExpr::TypeEnvironment::Bindings* b ) {
+                typedef ResolvExpr::TypeEnvironment::Bindings B;
+
+                while ( true ) {
+                        if ( ! gc.notrace_mark( b ) ) return;  // short-circuit if already traced
+
+                        if ( b->get_mode() == B::BASE ) break; // break if this is a base map
+                        
+                        if ( b->get_mode() != B::REM ) { // trace bound intermediate elements
+                                maybeAccept( b->get_val().type, *visitor );
+                        }
+
+                        b = b->get_base();
+                }
+
+                // trace bound elements in base binding
+                b->for_each( [&](interned_string, const ResolvExpr::BoundType& bound) {
+                        maybeAccept( bound.type, *visitor );  // trace bound elements
+                } );
+        }
+
+public:
+        void visit( const ResolvExpr::TypeEnvironment& env ) {
+                visit( env.classes );
+                visit( env.bindings );
+        }
 };