Changeset d318a18 for src/ResolvExpr

Timestamp:

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

Author:

Aaron Moss <a3moss@…>

Branches:

new-env

Children:

eff03a94

Parents:

5c14030

Message:

Fix assorted memory bugs with persistent-array environment

Location:

src/ResolvExpr

Files:

• TypeEnvironment.cc (modified) (11 diffs)
• TypeEnvironment.h (modified) (3 diffs)

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 );