Changeset 184557e


Ignore:
Timestamp:
Jul 6, 2018, 5:10:14 PM (3 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
new-env
Children:
5c14030
Parents:
b21c77a
Message:

First draft of persistent-hash-based TypeEnvironment?

Location:
src
Files:
1 added
4 edited

Legend:

Unmodified
Added
Removed
  • src/Common/PersistentDisjointSet.h

    rb21c77a r184557e  
    128128                }
    129129        }
     130
     131        /// Non-initializing constructor; should call init() before use
     132        PersistentDisjointSet( Mode m ) : data(), mode(m) {}
    130133
    131134        PersistentDisjointSet( Mode m, Base&& b ) : data(), mode(m) {
     
    291294        size_type count(Elm i) const { return rerooted().count( i ); }
    292295
    293         /// Finds root for element i, assertfs i is present
     296        /// Finds root for element i, undefined behaviour if i is not present
    294297        Elm find(Elm i) const {
    295298                const Base& self = rerooted();
     
    375378        }
    376379
    377         /// Reports all members of a class to `out`; none if i does not exist in map
    378         template<typename OutputIterator>
    379         void find_class(Elm i, OutputIterator&& out) const {
     380private:
     381        /// Removes the children of the tree rooted at `root` as `root_node`, returning a new
     382        /// uninitialized node and editing `next_edit` to point toward this new node.
     383        static Self* remove_children(Elm root, Node& root_node, Base& base_map, Self* next_edit) {
     384                // Invariant: root.next is *always* a pointer to a leaf of the most-recently added
     385                // subtree.
     386                //
     387                // Proof: By induction on height:
     388                // * height == 0: root.next == root, trivially true
     389                // * added.height < root.height: true by ind. hyp.
     390                // * added.height == root.height: no node may have a child the same height, ergo
     391                //   property holds for added, therefore root.
     392                //
     393                // Corollary: next of most-recently-added subtree root is previously added subtree
     394
     395                // remove all subtrees
     396                while ( root != root_node.next ) {
     397                        // find added child
     398                        auto it = base_map.find( root_node.next );
     399                        while ( it->second.parent != root ) it = base_map.find( it->second.parent );
     400                        Elm added = it->first;
     401                        Node& added_node = it->second;
     402
     403                        // unlink subtree and set up previous map as ADDTO new map
     404                        std::swap( root_node.next, added_node.next );
     405                        Self* new_edit = new Self{ BASE };
     406                        next_edit->init<AddTo>( new_edit, root, added, false );  // assume unchanged root height
     407                        next_edit->mode = ADDTO;
     408
     409                        // remove subtree children from map
     410                        next_edit = remove_children( added, added_node, base_map, new_edit );
     411
     412                        // remove subtree root from map and set up previous map as ADD to new map
     413                        base_map.erase( added );
     414                        new_edit = new Self{ BASE };
     415                        next_edit->init<Add>( new_edit, added );
     416                        next_edit->mode = ADD;
     417
     418                        next_edit = new_edit;
     419                }
     420
     421                return next_edit;
     422        }
     423
     424public:
     425        /// Removes all elements of a class given by its root; returns updated map.
     426        Self* remove_class(Elm root) {
     427                reroot();
     428
     429                // remove map from self
     430                Base base_map = take_as<Base>();
     431                reset_as_base();
     432
     433                // find root node and remove children
     434                auto it = base_map.find( root );
     435                assertf(it != base_map.end(), "root node must exist in map");
     436                Self* next_edit = remove_children( root, it->second, base_map, this);
     437
     438                // root is alone in class, remove from map
     439                base_map.erase( root );
     440                Self* ret = new Self{ BASE, std::move(base_map) };
     441                // reinitialize previous node as ADD to new map
     442                next_edit->init<Add>( ret, root );
     443                next_edit->mode = ADD;
     444
     445                return ret;
     446        }
     447
     448        /// Applies `f` to all members of a class containing `i` (undefined behaviour if not present).
     449        /// `f` should take members by const reference or copy
     450        template<typename F>
     451        void apply_to_class(Elm i, F&& f) const {
    380452                const Base& self = rerooted();
    381 
    382                 // skip empty classes
    383                 if ( ! self.count( i ) ) return;
    384453
    385454                Elm crnt = i;
    386455                do {
    387                         *out++ = crnt;
     456                        f( crnt );
    388457                        auto it = self.find( crnt );
    389458                        assertf( it != self.end(), "current node must exist in base" );
  • src/Common/PersistentMap.h

    rb21c77a r184557e  
    114114        }
    115115
     116        /// Non-initializing constructor; should call init() before use
     117        PersistentMap( Mode m ) : data(), mode(m) {}
     118
    116119        PersistentMap( Mode m, Base&& b ) : data(), mode(m) {
    117120                assertf(m == BASE, "invalid mode");
     
    420423                }
    421424        }
     425
     426        /// Applies the function `f` to all elements of the map, returning a pointer to the updated map.
     427        /// `f` should take two parameters, `const Key&` and `Val&`, returning option<Val> filled with
     428        /// the previous value if mutated, an empty option<Val> otherwise.
     429        /// NOTE: when porting to C++17, this should work fine with std::optional
     430        template<typename F>
     431        Self* apply_to_all(F&& f) {
     432                // reset to root and exit early if no change
     433                if ( rerooted().empty() ) return this;
     434
     435                // remove map from self
     436                Base base_map = take_as<Base>();
     437                reset_as_base();
     438
     439                // apply all edits
     440                Self* next_edit = this;
     441                for ( auto& entry : base_map ) {
     442                        auto res = f( entry.first, entry.second );
     443                        if ( res ) {
     444                                // entry has been mutated; reset next_edit node as mutation
     445                                Self* new_node = new Self{ BASE };
     446                                next_edit->init<Ins>( new_node, entry.first, *std::move(res) );
     447                                next_edit->mode = UPD;
     448                                next_edit = new_node;
     449                        }
     450                }
     451
     452                // set map into final node and return
     453                next_edit->init<Base>( std::move(base_map) );
     454                return next_edit;
     455        }
     456
     457        /// Applies the function `f` to all elements of the map.
     458        /// `f` should take two parameters, `const Key&` and `const Val&`.
     459        template<typename F>
     460        void apply_to_all(F&& f) const {
     461                for ( const auto& entry : rerooted() ) { f( entry.first, entry.second ); }
     462        }
    422463};
    423464
  • src/ResolvExpr/TypeEnvironment.cc

    rb21c77a r184557e  
    2121#include "Common/InternedString.h"     // for interned_string
    2222#include "Common/PassVisitor.h"        // for PassVisitor<GcTracer>
     23#include "Common/option.h"             // for option<T>
    2324#include "Common/utility.h"            // for maybeClone
    2425#include "SymTab/Indexer.h"            // for Indexer
     
    4950        }
    5051
    51 #if 0
    52         void EqvClass::initialize( const EqvClass &src, EqvClass &dest ) {
    53                 initialize( src, dest, src.type );
    54         }
    55 
    56         void EqvClass::initialize( const EqvClass &src, EqvClass &dest, const Type *ty ) {
    57                 dest.vars = src.vars;
    58                 dest.type = maybeClone( ty );
    59                 dest.allowWidening = src.allowWidening;
    60                 dest.data = src.data;
    61         }
    62 
    63         EqvClass::EqvClass() : type( nullptr ), allowWidening( true ) {
    64         }
    65 
    66         EqvClass::EqvClass( const EqvClass &other ) {
    67                 initialize( other, *this );
    68         }
    69 
    70         EqvClass::EqvClass( const EqvClass &other, const Type *ty ) {
    71                 initialize( other, *this, ty );
    72         }
    73 
    74         EqvClass::EqvClass( EqvClass &&other )
    75         : vars{std::move(other.vars)}, type{other.type},
    76           allowWidening{std::move(other.allowWidening)}, data{std::move(other.data)} {
    77                   other.type = nullptr;
    78         }
    79 
    80         EqvClass &EqvClass::operator=( const EqvClass &other ) {
    81                 if ( this == &other ) return *this;
    82                 initialize( other, *this );
    83                 return *this;
    84         }
    85 
    86         EqvClass &EqvClass::operator=( EqvClass &&other ) {
    87                 if ( this == &other ) return *this;
    88                
    89                 vars = std::move(other.vars);
    90                 type = other.type;
    91                 allowWidening = std::move(other.allowWidening);
    92                 data = std::move(other.data);
    93 
    94                 return *this;
    95         }
    96 
    97         void EqvClass::set_type( Type* ty ) { type = ty; }
    98 
    99         void EqvClass::print( std::ostream &os, Indenter indent ) const {
    100                 os << "( ";
    101                 std::copy( vars.begin(), vars.end(), std::ostream_iterator< std::string >( os, " " ) );
    102                 os << ")";
    103                 if ( type ) {
    104                         os << " -> ";
    105                         type->print( os, indent+1 );
    106                 } // if
    107                 if ( ! allowWidening ) {
    108                         os << " (no widening)";
    109                 } // if
    110                 os << std::endl;
    111         }
    112 
    113         const EqvClass* TypeEnvironment::lookup( const std::string &var ) const {
    114                 for ( std::list< EqvClass >::const_iterator i = env.begin(); i != env.end(); ++i ) {
    115                         if ( i->vars.find( var ) != i->vars.end() ) return &*i;
    116                 } // for
    117                 return nullptr;
    118         }
    119 #endif
    120 
    12152        std::pair<interned_string, interned_string> TypeEnvironment::mergeClasses(
    12253                        interned_string root1, interned_string root2 ) {
     
    12657                // determine new root
    12758                assertf(classes->get_mode() == Classes::REMFROM, "classes updated to REMFROM by merge");
    128                 auto ret = std::make_pair( classes->get_root(), classes->get_child );
     59                auto ret = std::make_pair( classes->get_root(), classes->get_child() );
    12960               
    13061                // finalize classes
     
    302233        }
    303234
    304 #if !1
    305         /// Removes any class from env that intersects eqvClass
    306         void filterOverlappingClasses( std::list<EqvClass> &env, const EqvClass &eqvClass ) {
    307                 for ( auto i = env.begin(); i != env.end(); ) {
    308                         auto next = i;
    309                         ++next;
    310                         std::set<std::string> intersection;
    311                         std::set_intersection( i->vars.begin(), i->vars.end(), eqvClass.vars.begin(), eqvClass.vars.end(),
    312                                 std::inserter( intersection, intersection.begin() ) );
    313                         if ( ! intersection.empty() ) { env.erase( i ); }
    314                         i = next;
    315                 }
    316         }
    317 
    318         void TypeEnvironment::add( EqvClass &&eqvClass ) {
    319                 filterOverlappingClasses( env, eqvClass );
    320                 env.push_back( std::move(eqvClass) );
    321         }
    322 
    323235        void TypeEnvironment::add( const Type::ForallList &tyDecls ) {
    324236                for ( Type::ForallList::const_iterator i = tyDecls.begin(); i != tyDecls.end(); ++i ) {
    325                         EqvClass newClass;
    326                         newClass.vars.insert( (*i)->get_name() );
    327                         newClass.data = TypeDecl::Data{ (*i) };
    328                         env.push_back( std::move(newClass) );
     237                        interned_string name = (*i)->get_name();
     238                        classes = classes->add( name );
     239                        bindings = bindings->set( name, *i );
    329240                } // for
    330241        }
    331242
    332243        void TypeEnvironment::add( const TypeSubstitution & sub ) {
    333                 EqvClass newClass;
     244                interned_string not_found{nullptr};
     245
    334246                for ( auto p : sub ) {
    335                         newClass.vars.insert( p.first );
    336                         newClass.type = p.second->clone();
    337                         newClass.allowWidening = false;
     247                        interned_string var = p.first;
     248                       
     249                        // filter overlapping classes out of existing environment
     250                        // (this is a very shady assumption, but has worked for a long time...)
     251                        interned_string root = classes->find_or_default( v, not_found );
     252                        if ( root != not_found ) {
     253                                classes = classes->remove_class( root );
     254                                bindings = bindings->erase( root );
     255                        }
     256
    338257                        // Minimal assumptions. Not technically correct, but might be good enough, and
    339258                        // is the best we can do at the moment since information is lost in the
    340259                        // transition to TypeSubstitution
    341                         newClass.data = TypeDecl::Data{ TypeDecl::Dtype, false };
    342                         add( std::move(newClass) );
     260                        TypeDecl::Data data{ TypeDecl::Dtype, false };
     261
     262                        // add variable to class and bindings
     263                        classes = classes->add( var );
     264                        bindings = bindings->set( var, BoundType{ p.second->clone, false, data } );
    343265                }
    344266        }
    345267
    346268        void TypeEnvironment::makeSubstitution( TypeSubstitution &sub ) const {
    347                 for ( std::list< EqvClass >::const_iterator theClass = env.begin(); theClass != env.end(); ++theClass ) {
    348                         for ( std::set< std::string >::const_iterator theVar = theClass->vars.begin(); theVar != theClass->vars.end(); ++theVar ) {
    349                                 if ( theClass->type ) {
    350                                         sub.add( *theVar, theClass->type );
    351                                 } else if ( theVar != theClass->vars.begin() ) {
    352                                         TypeInstType *newTypeInst = new TypeInstType( Type::Qualifiers(), *theClass->vars.begin(), theClass->data.kind == TypeDecl::Ftype );
    353                                         sub.add( *theVar, newTypeInst );
    354                                 } // if
    355                         } // for
    356                 } // for
     269                bindings->apply_to_all([classes, &sub]( interned_string root, const BoundType& bound ){
     270                        classes->apply_to_class(root, [&]( interned_string var ) {
     271                                if ( bound.type ) {
     272                                        sub.add( var, bound.type );
     273                                } else if ( var != root ) {
     274                                        sub.add( var, new TypeInstType{
     275                                                Type::Qualifiers{}, root, bound.data.kind == TypeDecl::Ftype } );
     276                                }
     277                        });
     278                });
     279
    357280                sub.normalize();
    358281        }
    359282
    360283        void TypeEnvironment::print( std::ostream &os, Indenter indent ) const {
    361                 for ( const EqvClass & theClass : env ) {
    362                         theClass.print( os, indent );
    363                 } // for
    364         }
    365 
    366         std::list< EqvClass >::iterator TypeEnvironment::internal_lookup( const std::string &var ) {
    367                 for ( std::list< EqvClass >::iterator i = env.begin(); i != env.end(); ++i ) {
    368                         if ( i->vars.count( var ) ) return i;
    369                 } // for
    370                 return env.end();
    371         }
    372 
    373         void TypeEnvironment::simpleCombine( const TypeEnvironment &second ) {
    374                 env.insert( env.end(), second.env.begin(), second.env.end() );
     284                bindings->apply_to_all([classes,&]( interned_string root, const BoundType& bound ) {
     285                        os << "( ";
     286                        classes->apply_to_class( root, [&os]( interned_string var ) { os << var << " "; } );
     287                        os << ")";
     288                        if ( bound.type ) {
     289                                os << " -> ";
     290                                type->print( os, indent+1 );
     291                        }
     292                        if ( ! bound.allowWidening ) {
     293                                os << " (no widening)";
     294                        }
     295                        os << std::endl;
     296                });
     297        }
     298
     299        void TypeEnvironment::simpleCombine( const TypeEnvironment &o ) {
     300                o.bindings->apply_to_all( [&]( interned_string root, const BoundType& bound ) {
     301                        // add members of new class
     302                        interned_string new_root{nullptr};
     303                        o.classes->apply_to_class( root, [this,&new_root]( interned_string var ) {
     304                                classes = classes->add( var );
     305                                new_root = new_root ? mergeClasses( new_root, var ).first : var;
     306                        });
     307                        // set binding for new class
     308                        bindings = bindings->set( new_root, bound );
     309                });
    375310        }
    376311
    377312        void TypeEnvironment::extractOpenVars( OpenVarSet &openVars ) const {
    378                 for ( std::list< EqvClass >::const_iterator eqvClass = env.begin(); eqvClass != env.end(); ++eqvClass ) {
    379                         for ( std::set< std::string >::const_iterator var = eqvClass->vars.begin(); var != eqvClass->vars.end(); ++var ) {
    380                                 openVars[ *var ] = eqvClass->data;
    381                         } // for
    382                 } // for
     313                bindings->apply_to_all( [classes,&openVars]( interned_string root, const BoundType& bound ) {
     314                        classes->apply_to_class( root, [&openVars,&bound]( interned_string var ) {
     315                                openVars[ var ] = bound.data;
     316                        } );
     317                } );
    383318        }
    384319
    385320        void TypeEnvironment::addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars ) {
    386                 for ( const EqvClass& c : actualEnv ) {
    387                         EqvClass c2 = c;
    388                         c2.allowWidening = false;
    389                         for ( const std::string& var : c2.vars ) {
    390                                 openVars[ var ] = c2.data;
    391                         }
    392                         env.push_back( std::move(c2) );
    393                 }
     321                actualEnv.bindings->apply_to_all( [&]( interned_string root, const BoundType& bound ) {
     322                        // add members of new class, setting openVars concurrently
     323                        interned_string new_root{nullptr};
     324                        actualEnv.classes->apply_to_class( root, [&]( interned_string var ) {
     325                                classes = classes->add( var );
     326                                new_root = new_root ? mergeClasses( new_root, var ).first : var;
     327                                openVars[ var ] = bound.data;
     328                        } );
     329                        // add new type binding without widening
     330                        bindings = bindings->set( new_root,
     331                                BoundType{ maybeClone(bound.type), false, bound.data } );
     332                } );
     333        }
     334
     335        void TypeEnvironment::forbidWidening() {
     336                bindings = bindings->apply_to_all([]( const interned_string& k, BoundType& c ) {
     337                        if ( c.allowWidening ) {
     338                                option<BoundType> ret = c;
     339                                c.allowWidening = false;
     340                                return ret;
     341                        } else return option<BoundType>{};
     342                });
    394343        }
    395344
     
    398347                return out;
    399348        }
    400 #endif
    401349
    402350        PassVisitor<GcTracer> & operator<<( PassVisitor<GcTracer> & gc, const TypeEnvironment & env ) {
  • src/ResolvExpr/TypeEnvironment.h

    rb21c77a r184557e  
    8686                bool allowWidening;
    8787                TypeDecl::Data data;
    88         };
    89 
    90 #if 0
    91         /// An equivalence class, with its binding information
    92         struct EqvClass {
    93                 std::set< std::string > vars;
    94                 Type *type;
    95                 bool allowWidening;
    96                 TypeDecl::Data data;
    97 
    98                 void initialize( const EqvClass &src, EqvClass &dest );
    99                 void initialize( const EqvClass &src, EqvClass &dest, const Type *ty );
    100                 EqvClass();
    101                 EqvClass( const EqvClass &other );
    102                 EqvClass( const EqvClass &other, const Type *ty );
    103                 EqvClass( EqvClass &&other );
    104                 EqvClass &operator=( const EqvClass &other );
    105                 EqvClass &operator=( EqvClass &&other );
    106                 void print( std::ostream &os, Indenter indent = {} ) const;
    107 
    108                 /// Takes ownership of `ty`, freeing old `type`
    109                 void set_type(Type* ty);
    110         };
    111 #endif
    112        
     88
     89                BoundType() = default;
     90                BoundType( TypeDecl* td ) : type{nullptr}, allowWidening{true}, data{td} {}
     91                BoundType( Type* ty, bool aw, const TypeDecl::Data& td )
     92                        : type{ty}, allowWidening{aw}, data{td} {}
     93                BoundType( const BoundType& o )
     94                        : type{maybeClone(o.type)}, allowWidening{o.allowWidening}, data{o.data} {}
     95                BoundType( BoundType&& o ) = default;
     96                BoundType& operator= (const BoundType& o) {
     97                        if ( this == &o ) return *this;
     98                        type = maybeClone( o.type );
     99                        allowWidening = o.allowWidening;
     100                        data = o.data;
     101                        return *this;
     102                }
     103                BoundType& operator= (BoundType&& o) = default;
     104        };
     105
    113106        class TypeEnvironment;
    114107
     
    137130                /// Gets the bound type information of the referenced equivalence class, default if none
    138131                inline BoundType get_bound() const;
    139 
    140 #if 0
    141                 /// Gets the referenced equivalence class
    142                 inline EqvClass get_class() const;
    143                 EqvClass operator* () const { return get_class(); }
    144 #endif
    145132
    146133                // Check that there is a referenced typeclass
     
    171158                        interned_string root1, interned_string root2 );
    172159
    173           public:
     160        public:
    174161                class iterator : public std::iterator<
    175162                                std::forward_iterator_tag,
     
    213200                        AssertionSet& need, AssertionSet& have, const OpenVarSet& openVars,
    214201                        WidenMode widenMode, const SymTab::Indexer& indexer );
    215 #if !1
    216         private:
    217                 void add( EqvClass &&eqvClass );
     202
    218203        public:
    219204                void add( const Type::ForallList &tyDecls );
     
    222207                template< typename SynTreeClass > int applyFree( SynTreeClass *&type ) const;
    223208                void makeSubstitution( TypeSubstitution &result ) const;
    224 #endif
    225209                bool isEmpty() const { return classes->empty(); }
    226 #if !1
    227210                void print( std::ostream &os, Indenter indent = {} ) const;
     211       
     212                /// Combines two environments without checking invariants.
     213                /// Caller should ensure environments do not share type variables.
    228214                void simpleCombine( const TypeEnvironment &second );
     215       
    229216                void extractOpenVars( OpenVarSet &openVars ) const;
    230 #endif
    231217                TypeEnvironment *clone() const { return new TypeEnvironment( *this ); }
    232218
    233 #if !1
    234219                /// Iteratively adds the environment of a new actual (with allowWidening = false),
    235220                /// and extracts open variables.
     
    238223                /// Disallows widening for all bindings in the environment
    239224                void forbidWidening();
    240 #endif
    241225
    242226                iterator begin() { return { this, bindings->begin() }; }
     
    244228        };
    245229
    246         void ClassRef::update_root() { return root = env->classes->find( root ); }
     230        interned_string ClassRef::update_root() { return root = env->classes->find( root ); }
    247231
    248232        template<typename T>
    249233        T ClassRef::get_vars() const {
    250234                T vars;
    251                 env->classes->find_class( root, std::inserter(vars, vars.end()) );
     235                if ( ! env->classes->count( root ) ) return vars;
     236                env->classes->apply_to_class( root, [&vars]( interned_string var ) {
     237                        vars.insert( vars.end(), var );
     238                } );
    252239                return vars;
    253240        }
     
    256243                return env->bindings->get_or_default( root, BoundType{} );
    257244        }
    258 
    259 #if 0
    260         EqvClass ClassRef::get_class() const { return { get_vars(), get_bound() }; }
    261 #endif
    262245
    263246        template< typename SynTreeClass >
     
    275258        }
    276259
    277 #if !1
    278260        std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env );
    279 #endif
    280261
    281262        PassVisitor<GcTracer> & operator<<( PassVisitor<GcTracer> & gc, const TypeEnvironment & env );
Note: See TracChangeset for help on using the changeset viewer.