Changeset 9ad2f9f


Ignore:
Timestamp:
Oct 3, 2018, 5:08:14 PM (3 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, no_list, persistent-indexer
Children:
59cf83b
Parents:
588c2b0
Message:

TypeEnvironment::combine -- compiles, untested

Location:
src/ResolvExpr
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • src/ResolvExpr/TypeEnvironment.cc

    r588c2b0 r9ad2f9f  
    120120
    121121        const EqvClass* TypeEnvironment::lookup( const std::string &var ) const {
    122                 for ( std::list< EqvClass >::const_iterator i = env.begin(); i != env.end(); ++i ) {
     122                for ( ClassList::const_iterator i = env.begin(); i != env.end(); ++i ) {
    123123                        if ( i->vars.find( var ) != i->vars.end() ) return &*i;
    124124                } // for
     
    168168
    169169        void TypeEnvironment::makeSubstitution( TypeSubstitution &sub ) const {
    170                 for ( std::list< EqvClass >::const_iterator theClass = env.begin(); theClass != env.end(); ++theClass ) {
     170                for ( ClassList::const_iterator theClass = env.begin(); theClass != env.end(); ++theClass ) {
    171171                        for ( std::set< std::string >::const_iterator theVar = theClass->vars.begin(); theVar != theClass->vars.end(); ++theVar ) {
    172172                                if ( theClass->type ) {
     
    188188        }
    189189
    190         std::list< EqvClass >::iterator TypeEnvironment::internal_lookup( const std::string &var ) {
    191                 for ( std::list< EqvClass >::iterator i = env.begin(); i != env.end(); ++i ) {
     190        TypeEnvironment::ClassList::iterator TypeEnvironment::internal_lookup( const std::string &var ) {
     191                for ( ClassList::iterator i = env.begin(); i != env.end(); ++i ) {
    192192                        if ( i->vars.count( var ) ) return i;
    193193                } // for
     
    199199        }
    200200
     201        // xxx -- this should maybe be worrying about iterator invalidation (see resolv-proto)
     202        bool TypeEnvironment::mergeBound( EqvClass& to, const EqvClass& from, OpenVarSet& openVars, const SymTab::Indexer& indexer ) {
     203                if ( from.type ) {
     204                        if ( to.type ) {
     205                                // attempt to unify bound types
     206                                std::unique_ptr<Type> toType{ to.type->clone() }, fromType{ from.type->clone() };
     207                                WidenMode widenMode{ to.allowWidening, from.allowWidening };
     208                                Type* common = nullptr;
     209                                AssertionSet need, have;
     210                                if ( unifyInexact( toType.get(), fromType.get(), *this, need, have, openVars, widenMode, indexer, common ) ) {
     211                                        // unifies, set common type if necessary
     212                                        if ( common ) {
     213                                                common->get_qualifiers() = Type::Qualifiers{};
     214                                                to.set_type( common );
     215                                        }
     216                                } else return false; // cannot unify
     217                        } else {
     218                                to.type = from.type->clone();
     219                        }
     220                }
     221
     222                // unify widening if matches
     223                to.allowWidening &= from.allowWidening;
     224                return true;
     225        }
     226
     227        // xxx -- this should maybe be worrying about iterator invalidation (see resolv-proto)
     228        bool TypeEnvironment::mergeClasses( TypeEnvironment::ClassList::iterator to, TypeEnvironment::ClassList::iterator from, OpenVarSet& openVars, const SymTab::Indexer& indexer ) {
     229                EqvClass& r = *to;
     230                EqvClass& s = *from;
     231
     232                // ensure bounds match
     233                if ( ! mergeBound( r, s, openVars, indexer ) ) return false;
     234
     235                // check safely bindable
     236                if ( r.type && occursIn( r.type, s.vars.begin(), s.vars.end(), *this ) ) return false;
     237               
     238                // merge classes in
     239                r.vars.insert( s.vars.begin(), s.vars.end() );
     240                r.allowWidening &= s.allowWidening;
     241                env.erase( from );
     242
     243                return true;
     244        }
     245
     246        bool TypeEnvironment::combine( const TypeEnvironment& o, OpenVarSet& openVars, const SymTab::Indexer& indexer ) {
     247                // short-circuit easy cases
     248                if ( o.isEmpty() ) return true;
     249                if ( isEmpty() ) {
     250                        simpleCombine( o );
     251                        return true;
     252                }
     253
     254                // merge classes
     255                for ( auto ct = o.env.begin(); ct != o.env.end(); ++ct ) {
     256                        const EqvClass& c = *ct;
     257
     258                        // typeclass in local environment bound to c
     259                        auto rt = env.end();
     260
     261                        // look for first existing bound variable
     262                        auto vt = c.vars.begin();
     263                        for ( ; vt != c.vars.end(); ++vt ) {
     264                                rt = internal_lookup( *vt );
     265                                if ( rt != env.end() ) break;
     266                        }
     267
     268                        if ( rt != env.end() ) {  // c needs to be merged into *rt
     269                                EqvClass& r = *rt;
     270                                // merge bindings
     271                                if ( ! mergeBound( r, c, openVars, indexer ) ) return false;
     272                                // merge previous unbound variables into this class, checking occurs if needed
     273                                if ( r.type ) for ( auto ut = c.vars.begin(); ut != vt; ++ut ) {
     274                                        if ( occurs( r.type, *ut, *this ) ) return false;
     275                                        r.vars.insert( *ut );
     276                                } else { r.vars.insert( c.vars.begin(), vt ); }
     277                                // merge subsequent variables into this class (skipping *vt, already there)
     278                                while ( ++vt != c.vars.end() ) {
     279                                        auto st = internal_lookup( *vt );
     280                                        if ( st == env.end() ) {
     281                                                // unbound, safe to add if passes occurs
     282                                                if ( r.type && occurs( r.type, *vt, *this ) ) return false;
     283                                                r.vars.insert( *vt );
     284                                        } else if ( st != rt ) {
     285                                                // bound, but not to the same class
     286                                                if ( ! mergeClasses( rt, st, openVars, indexer ) ) return false;
     287                                        }   // ignore bound into the same class
     288                                }
     289                        } else {  // no variables in c bound; just copy up
     290                                env.push_back( c );
     291                        }
     292                }
     293
     294                // merged all classes
     295                return true;
     296        }
     297
    201298        void TypeEnvironment::extractOpenVars( OpenVarSet &openVars ) const {
    202                 for ( std::list< EqvClass >::const_iterator eqvClass = env.begin(); eqvClass != env.end(); ++eqvClass ) {
     299                for ( ClassList::const_iterator eqvClass = env.begin(); eqvClass != env.end(); ++eqvClass ) {
    203300                        for ( std::set< std::string >::const_iterator var = eqvClass->vars.begin(); var != eqvClass->vars.end(); ++var ) {
    204301                                openVars[ *var ] = eqvClass->data;
  • src/ResolvExpr/TypeEnvironment.h

    r588c2b0 r9ad2f9f  
    3939        // declarations.
    4040        //
    41         // I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this comparator.
     41        // I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this
     42        // comparator.
    4243        //
    4344        // Note: since this compares pointers for position, minor changes in the source file that affect
    4445        // memory layout can alter compilation time in unpredictable ways. For example, the placement
    4546        // of a line directive can reorder type pointers with respect to each other so that assertions
    46         // are seen in different orders, causing a potentially different number of unification calls when
    47         // resolving assertions. I've seen a TU go from 36 seconds to 27 seconds by reordering line directives
    48         // alone, so it would be nice to fix this comparison so that assertions compare more consistently.
    49         // I've tried to modify this to compare on mangle name instead of type as the second comparator, but
    50         // this causes some assertions to never be recorded. More investigation is needed.
     47        // are seen in different orders, causing a potentially different number of unification calls
     48        // when resolving assertions. I've seen a TU go from 36 seconds to 27 seconds by reordering
     49        // line directives alone, so it would be nice to fix this comparison so that assertions compare
     50        // more consistently. I've tried to modify this to compare on mangle name instead of type as
     51        // the second comparator, but this causes some assertions to never be recorded. More
     52        // investigation is needed.
    5153        struct AssertCompare {
    5254                bool operator()( DeclarationWithType * d1, DeclarationWithType * d2 ) const {
     
    5860        struct AssertionSetValue {
    5961                bool isUsed;
    60                 // chain of Unique IDs of the assertion declarations. The first ID in the chain is the ID of an assertion on the current type,
    61                 // with each successive ID being the ID of an assertion pulled in by the previous ID. The last ID in the chain is
    62                 // the ID of the assertion that pulled in the current assertion.
     62                // chain of Unique IDs of the assertion declarations. The first ID in the chain is the ID
     63                // of an assertion on the current type, with each successive ID being the ID of an
     64                // assertion pulled in by the previous ID. The last ID in the chain is the ID of the
     65                // assertion that pulled in the current assertion.
    6366                std::list< UniqueId > idChain;
    6467        };
     
    9194
    9295        class TypeEnvironment {
     96                using ClassList = std::list< EqvClass >;
    9397          public:
    9498                const EqvClass* lookup( const std::string &var ) const;
     
    103107                bool isEmpty() const { return env.empty(); }
    104108                void print( std::ostream &os, Indenter indent = {} ) const;
    105                 // void combine( const TypeEnvironment &second, Type *(*combineFunc)( Type*, Type* ) );
     109               
     110                /// Simply concatenate the second environment onto this one; no safety checks performed
    106111                void simpleCombine( const TypeEnvironment &second );
     112
     113          private:
     114                /// Unifies the type bound of to with the type bound of from, returning false if fails
     115                bool mergeBound( EqvClass& to, const EqvClass& from, OpenVarSet& openVars, const SymTab::Indexer& indexer );
     116
     117                /// Merges two type classes from local environment, returning false if fails
     118                bool mergeClasses( ClassList::iterator to, ClassList::iterator from, OpenVarSet& openVars, const SymTab::Indexer& indexer );
     119
     120          public:
     121                /// Merges the second environment with this one, checking compatibility.
     122                /// Returns false if fails, but does NOT roll back partial changes.
     123                bool combine( const TypeEnvironment& second, OpenVarSet& openVars, const SymTab::Indexer& indexer );
     124               
    107125                void extractOpenVars( OpenVarSet &openVars ) const;
    108126                TypeEnvironment *clone() const { return new TypeEnvironment( *this ); }
     
    123141                void forbidWidening();
    124142
    125                 using iterator = std::list< EqvClass >::const_iterator;
     143                using iterator = ClassList::const_iterator;
    126144                iterator begin() const { return env.begin(); }
    127145                iterator end() const { return env.end(); }
    128146
    129147          private:
    130                 std::list< EqvClass > env;
     148                ClassList env;
    131149               
    132                 std::list< EqvClass >::iterator internal_lookup( const std::string &var );
     150                ClassList::iterator internal_lookup( const std::string &var );
    133151        };
    134152
  • src/ResolvExpr/typeops.h

    r588c2b0 r9ad2f9f  
    108108        bool occurs( Type *type, std::string varName, const TypeEnvironment &env );
    109109
     110        template<typename Iter>
     111        bool occursIn( Type* ty, Iter begin, Iter end, const TypeEnvironment &env ) {
     112                while ( begin != end ) {
     113                        if ( occurs( ty, *begin, env ) ) return true;
     114                        ++begin;
     115                }
     116                return false;
     117        }
     118
    110119        // in AlternativeFinder.cc
    111120        void referenceToRvalueConversion( Expression *& expr, Cost & cost );
Note: See TracChangeset for help on using the changeset viewer.