Changeset d318a18


Ignore:
Timestamp:
Jul 18, 2018, 5:18:29 PM (3 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:
7 edited

Legend:

Unmodified
Added
Removed
  • src/Common/GC.cc

    r5c14030 rd318a18  
    4141
    4242const GC& GC::operator<< (const GC_Object* obj) const {
    43         if( obj )
    44         {
     43        if( obj ) {
    4544                if( obj->mark != this->mark ) {
    4645                        obj->mark = this->mark;
     
    4948        }
    5049        return *this;
     50}
     51
     52bool GC::notrace_mark(const GC_Object* obj) const {
     53        if ( obj && obj->mark != this->mark ) {
     54                obj->mark = this->mark;
     55                return true;
     56        }
     57        return false;
    5158}
    5259
  • src/Common/GC.h

    r5c14030 rd318a18  
    3838        /// Traces a traceable object
    3939        const GC& operator<< (const GC_Object*) const;
     40
     41        /// No-trace mark; returns true if the object exists and was not already marked
     42        bool notrace_mark(const GC_Object*) const;
    4043
    4144        /// Adds a new object to garbage collection
  • src/Common/PersistentDisjointSet.h

    r5c14030 rd318a18  
    281281        const Base& rerooted() const {
    282282                reroot();
     283                assertf(mode == BASE, "reroot results in base");
    283284                return as<Base>();
    284285        }
     
    332333        }
    333334
    334         /// Adds fresh class including only one item; returns updated map
     335        /// Adds fresh class including only one item; returns updated map (or self if no change)
    335336        template<typename E>
    336337        Self* add(E&& i) {
    337338                reroot();
    338                
    339                 // transfer map to new node
    340                 Self* ret = new Self{ BASE, take_as<Base>() };
     339
     340                // add new element to node
     341                Base base_map = take_as<Base>();
     342                bool added = base_map.emplace( i, Node{ i } ).second;
     343
     344                // fail early on node already present
     345                if ( ! added ) {
     346                        as<Base>() = std::move(base_map);
     347                        return this;
     348                }
     349
     350                // make new return node and reset self as REM node
     351                Self* ret = new Self{ BASE, std::move(base_map) };
    341352                reset_as_base();
    342 
    343                 // set self to REM node
    344353                init<Add>( ret, i );
    345354                mode = REM;
    346                
    347                 // add element in returned map
    348                 Base& base_map = ret->as<Base>();
    349                 bool added = base_map.emplace( i, Node{ std::forward<E>(i) } ).second;
    350                 assertf(added, "added element already present in map");
    351355
    352356                return ret;
     
    460464                const Base& self = rerooted();
    461465
    462                 Elm crnt = i;
    463                 do {
     466                // exit early if class not present
     467                auto it = self.find( i );
     468                if ( it == self.end() ) return;
     469
     470                // apply f to each member of class
     471                f( i );
     472                for ( Elm crnt = it->second.next; crnt != i; crnt = it->second.next ) {
    464473                        f( crnt );
    465                         auto it = self.find( crnt );
     474                        it = self.find( crnt );
    466475                        assertf( it != self.end(), "current node must exist in base" );
    467                         crnt = it->second.next;
    468                 } while ( crnt != i );
     476                }
    469477        }
    470478
  • src/Common/PersistentMap.h

    r5c14030 rd318a18  
    141141                                        gc.maybe_trace( entry.first, entry.second );
    142142                                }
    143                                 return;
    144                         }
     143                        } break;
    145144                        case REM: {
    146145                                const Rem& self = as<Rem>();
    147146                                gc << self.base;
    148147                                gc.maybe_trace( self.key );
    149                                 return;
    150                         }
     148                        } break;
    151149                        case INS: case UPD: {
    152150                                const Ins& self = as<Ins>();
    153151                                gc << self.base;
    154152                                gc.maybe_trace( self.key, self.val );
    155                                 return;
    156                         }
     153                        } break;
    157154                        default: assertf(false, "invalid mode");
    158155                }
     
    198195
    199196                                base_map.erase( it );
    200                                 break;
    201                         }
     197                        } break;
    202198                        case INS: {
    203199                                Ins& self = mut_this->as<Ins>();
     
    207203
    208204                                base_map.emplace( std::move(self.key), std::move(self.val) );
    209                                 break;
    210                         }
     205                        } break;
    211206                        case UPD: {
    212207                                Ins& self = mut_this->as<Ins>();
     
    218213
    219214                                it->second = std::move(self.val);
    220                                 break;
    221                         }
     215                        } break;
    222216                        default: assertf(false, "invalid mode");
    223217                }
  • src/ResolvExpr/TypeEnvironment.cc

    r5c14030 rd318a18  
    3333
    3434namespace ResolvExpr {
     35        #if 1
     36        #define PRE_POST_VALIDATE auto dbg = ValidateGuard{this, __func__};
     37        #define PRE_POST_VALIDATE_NOM auto dbg = ValidateGuard{this};
     38        struct ValidateGuard {
     39                const TypeEnvironment* env;
     40                const TypeEnvironment::Classes* old_classes;
     41                const TypeEnvironment::Bindings* old_bindings;
     42                const char* last_fn;
     43
     44                void validate_classes( const TypeEnvironment::Classes* c ) {
     45                        typedef TypeEnvironment::Classes C;
     46
     47                        assertf( c != nullptr, "classes non-null" );
     48                       
     49                        C::Mode cmode = c->get_mode();
     50                        if ( cmode == C::BASE ) {
     51                                // xxx - consistency checks
     52                        } else {
     53                                assertf( cmode == C::ADD || cmode == C::REM || cmode == C::ADDTO || cmode == C::REMFROM, "valid classes mode" );
     54                                validate_classes( c->get_base() );
     55                        }
     56                }
     57
     58                void validate_bindings( const TypeEnvironment::Bindings* b ) {
     59                        typedef TypeEnvironment::Bindings B;
     60
     61                        assertf( b != nullptr, "bindings non-null" );
     62
     63                        B::Mode bmode = b->get_mode();
     64                        if ( bmode == B::BASE ) {
     65                                // xxx - consistency checks
     66                        } else {
     67                                assertf( bmode == B::REM || bmode == B::INS || bmode == B::UPD, "valid bindings mode" );
     68                                validate_bindings( b->get_base() );
     69                        }
     70                }
     71
     72                void validate_env() {
     73                        validate_classes( env->classes );
     74                        validate_bindings( env->bindings );
     75                       
     76                        // xxx - joint validation
     77                }
     78
     79                ValidateGuard(const TypeEnvironment* e)
     80                        : env{e}, old_classes{e->classes}, old_bindings{e->bindings}, last_fn{e->last_fn}
     81                        { validate_env(); }
     82                ValidateGuard(const TypeEnvironment* e, const char* fn)
     83                        : env{e}, old_classes{e->classes}, old_bindings{e->bindings}, last_fn{fn}
     84                        { validate_env(); }
     85                ~ValidateGuard() {
     86                        validate_env();
     87                        if ( env->classes != old_classes ) validate_classes( old_classes );
     88                        if ( env->bindings != old_bindings ) validate_bindings( old_bindings );
     89                        const_cast<TypeEnvironment*>(env)->last_fn = last_fn;
     90                }
     91        };
     92        #else
     93        #define PRE_POST_VALIDATE
     94        #define PRE_POST_VALIDATE_NOM
     95        #endif
     96
    3597        void printAssertionSet( const AssertionSet &assertions, std::ostream &os, int indent ) {
    3698                for ( AssertionSet::const_iterator i = assertions.begin(); i != assertions.end(); ++i ) {
     
    53115        std::pair<interned_string, interned_string> TypeEnvironment::mergeClasses(
    54116                        interned_string root1, interned_string root2 ) {
     117                PRE_POST_VALIDATE
    55118                // merge classes
    56119                Classes* newClasses = classes->merge( root1, root2 );
     
    100163                        const TypeDecl::Data& data, AssertionSet& need, AssertionSet& have,
    101164                        const OpenVarSet& openVars, WidenMode widenMode, const SymTab::Indexer& indexer ) {
     165                PRE_POST_VALIDATE
    102166                // remove references from other, so that type variables can only bind to value types
    103167                bindTo = bindTo->stripReferences();
     
    148212                        const TypeDecl::Data& data, AssertionSet& need, AssertionSet& have,
    149213                        const OpenVarSet& openVars, WidenMode widenMode, const SymTab::Indexer& indexer ) {
     214                PRE_POST_VALIDATE
    150215                ClassRef class1 = lookup( var1->get_name() );
    151216                ClassRef class2 = lookup( var2->get_name() );
     
    237302
    238303        void TypeEnvironment::add( const Type::ForallList &tyDecls ) {
     304                PRE_POST_VALIDATE
    239305                for ( Type::ForallList::const_iterator i = tyDecls.begin(); i != tyDecls.end(); ++i ) {
    240306                        interned_string name = (*i)->get_name();
     
    245311
    246312        void TypeEnvironment::add( const TypeSubstitution & sub ) {
     313                PRE_POST_VALIDATE
    247314                interned_string not_found{nullptr};
    248315
     
    251318                       
    252319                        // filter overlapping classes out of existing environment
    253                         // (this is a very shady assumption, but has worked for a long time...)
     320                        // xxx - this is a very shady assumption, but has worked for a long time...
    254321                        interned_string root = classes->find_or_default( var, not_found );
    255322                        if ( root != not_found ) {
     
    270337
    271338        void TypeEnvironment::makeSubstitution( TypeSubstitution &sub ) const {
     339                PRE_POST_VALIDATE_NOM
    272340                bindings->for_each([&]( interned_string root, const BoundType& bound ){
    273341                        classes->for_class(root, [&]( interned_string var ) {
     
    300368        }
    301369
     370        namespace {
     371                // temporary representation of an equivalence class
     372                struct EqvClass {
     373                        std::vector<interned_string> vars;
     374                        BoundType bound;
     375
     376                        EqvClass() = default;
     377                        EqvClass(const BoundType& b) : bound{b} {}
     378                };
     379        }
     380
    302381        void TypeEnvironment::simpleCombine( const TypeEnvironment &o ) {
     382                PRE_POST_VALIDATE
     383                // check for same environment
     384                if ( classes == o.classes && bindings == o.bindings ) return;
     385
     386                // read out equivalence classes (avoids conflicting reroots)
     387                std::vector<EqvClass> ecs;
    303388                o.bindings->for_each( [&]( interned_string root, const BoundType& bound ) {
    304                         // add members of new class
     389                        ecs.emplace_back(bound);
     390                        o.classes->for_class( root, [&]( interned_string var ) {
     391                                ecs.back().vars.push_back( var );
     392                        } );
     393                } );
     394
     395                // read equivalence classes into self
     396                for ( EqvClass& ec : ecs ) {
     397                        // merge vars
    305398                        interned_string new_root{nullptr};
    306                         o.classes->for_class( root, [this,&new_root]( interned_string var ) {
    307                                 classes = classes->add( var );
     399                        for ( interned_string var : ec.vars ) {
     400                                Classes* new_classes = classes->add( var );
     401                                if ( new_classes == classes ) { var = classes->find( var ); }
     402                                else { classes = new_classes; }
    308403                                new_root = new_root ? mergeClasses( new_root, var ).first : var;
    309                         });
    310                         // set binding for new class
    311                         bindings = bindings->set( new_root, bound );
    312                 });
     404                        }
     405                        // set binding
     406                        bindings = bindings->set( new_root, ec.bound );
     407                }
    313408        }
    314409
     
    322417
    323418        void TypeEnvironment::addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars ) {
     419                PRE_POST_VALIDATE
     420                if ( classes == actualEnv.classes && bindings == actualEnv.bindings ) {
     421                        // actualEnv already the same, just need to update openVars
     422                        extractOpenVars( openVars );
     423                        return;
     424                } else assertf(classes != actualEnv.classes && bindings != actualEnv.bindings, "classes & bindings updated together");
     425
     426                // read out equivalence classes (avoids conflicting reroots)
     427                std::vector<EqvClass> ecs;
    324428                actualEnv.bindings->for_each( [&]( interned_string root, const BoundType& bound ) {
    325                         // add members of new class, setting openVars concurrently
     429                        ecs.emplace_back(bound);
     430                        actualEnv.classes->for_class( root, [&]( interned_string var ) {
     431                                ecs.back().vars.push_back( var );
     432                        } );
     433                } );
     434
     435                // add members of new class, setting openVars concurrently
     436                for ( EqvClass& ec : ecs ) {
     437                        // merge vars
    326438                        interned_string new_root{nullptr};
    327                         actualEnv.classes->for_class( root, [&]( interned_string var ) {
    328                                 classes = classes->add( var );
     439                        for ( interned_string var : ec.vars ) {
     440                                openVars[ var ] = ec.bound.data;
     441                                Classes* new_classes = classes->add( var );
     442                                if ( new_classes == classes ) {
     443                                        // xxx - this case is a bit sketchy, but has been working
     444                                        // xxx - merging the classes is a departure from previous behaviour
     445                                        var = classes->find( var );
     446                                } else { classes = new_classes; }
    329447                                new_root = new_root ? mergeClasses( new_root, var ).first : var;
    330                                 openVars[ var ] = bound.data;
    331                         } );
    332                         // add new type binding without widening
     448                        }
     449                        // set binding without widening
    333450                        bindings = bindings->set( new_root,
    334                                 BoundType{ maybeClone(bound.type), false, bound.data } );
    335                 } );
     451                                BoundType{ maybeClone(ec.bound.type), false, ec.bound.data } );
     452                }
    336453        }
    337454
    338455        void TypeEnvironment::forbidWidening() {
     456                PRE_POST_VALIDATE
    339457                bindings = bindings->mutate_each([]( const interned_string&, BoundType& c ) {
    340458                        if ( c.allowWidening ) {
     
    352470
    353471        PassVisitor<GcTracer> & operator<<( PassVisitor<GcTracer> & gc, const TypeEnvironment & env ) {
    354                 for ( ClassRef c : env ) {
    355                         maybeAccept( c.get_bound().type, gc );
    356                 }
     472                gc.pass.visit( env );
     473                // for ( ClassRef c : env ) {
     474                //      maybeAccept( c.get_bound().type, gc );
     475                // }
    357476                return gc;
    358477        }
  • src/ResolvExpr/TypeEnvironment.h

    r5c14030 rd318a18  
    138138        };
    139139
     140        class ValidateGuard;
     141
    140142        class TypeEnvironment {
    141143                friend ClassRef;
    142 
     144                friend GcTracer;
     145               
    143146                /// Backing storage for equivalence classes
    144147                using Classes = PersistentDisjointSet<interned_string>;
     
    152155                /// may be null.
    153156                Bindings* bindings;
     157
     158                // for debugging
     159                friend ValidateGuard;
     160                const char* last_fn = "<none>";
    154161
    155162                /// Merges the classes rooted at root1 and root2, returning a pair containing the root and
     
    234241        T ClassRef::get_vars() const {
    235242                T vars;
    236                 if ( ! env->classes->count( root ) ) return vars;
    237243                env->classes->for_class( root, [&vars]( interned_string var ) {
    238244                        vars.insert( vars.end(), var );
  • src/SynTree/GcTracer.h

    r5c14030 rd318a18  
    2525#include "Common/GC.h"
    2626#include "Common/PassVisitor.h"
    27 
    28 class Expression;
     27#include "ResolvExpr/TypeEnvironment.h"
    2928
    3029/// Implements `trace` method for syntax nodes
     
    3433public:
    3534        GcTracer( const GC& gc ) : gc(gc) {}
     35
     36        template<typename... Args>
     37        void traceAll(Args&... args) { ::traceAll(gc, args...); }
    3638
    3739        // mark node and children
     
    151153                maybeAccept( type->baseUnion, *visitor );
    152154        }
     155
     156private:
     157        void visit( const ResolvExpr::TypeEnvironment::Classes* c ) {
     158                typedef ResolvExpr::TypeEnvironment::Classes C;
     159                // trace all parent classes, short-circuiting at one traced
     160                while ( gc.notrace_mark( c ) && c->get_mode() != C::BASE ) { c = c->get_base(); }
     161        }
     162
     163        void visit( const ResolvExpr::TypeEnvironment::Bindings* b ) {
     164                typedef ResolvExpr::TypeEnvironment::Bindings B;
     165
     166                while ( true ) {
     167                        if ( ! gc.notrace_mark( b ) ) return;  // short-circuit if already traced
     168
     169                        if ( b->get_mode() == B::BASE ) break; // break if this is a base map
     170                       
     171                        if ( b->get_mode() != B::REM ) { // trace bound intermediate elements
     172                                maybeAccept( b->get_val().type, *visitor );
     173                        }
     174
     175                        b = b->get_base();
     176                }
     177
     178                // trace bound elements in base binding
     179                b->for_each( [&](interned_string, const ResolvExpr::BoundType& bound) {
     180                        maybeAccept( bound.type, *visitor );  // trace bound elements
     181                } );
     182        }
     183
     184public:
     185        void visit( const ResolvExpr::TypeEnvironment& env ) {
     186                visit( env.classes );
     187                visit( env.bindings );
     188        }
    153189};
    154190
Note: See TracChangeset for help on using the changeset viewer.