Changeset 982f95d


Ignore:
Timestamp:
Jun 15, 2018, 5:09:29 PM (3 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
new-env
Children:
97397a26
Parents:
1d7b0a8
Message:

Start of new environment implementation; terribly broken

Location:
src
Files:
4 added
13 edited

Legend:

Unmodified
Added
Removed
  • src/Common/module.mk

    r1d7b0a8 r982f95d  
    1010## Author           : Richard C. Bilson
    1111## Created On       : Mon Jun  1 17:49:17 2015
    12 ## Last Modified By : Peter A. Buhr
    13 ## Last Modified On : Tue Sep 27 11:06:38 2016
    14 ## Update Count     : 4
     12## Last Modified By : Aaron B. Moss
     13## Last Modified On : Thu Jun 14 11:15:00 2018
     14## Update Count     : 5
    1515###############################################################################
    1616
     
    2020       Common/GC.cc \
    2121       Common/Assert.cc \
     22       Common/InternedString.cc \
    2223       Common/Heap.cc
  • src/GenPoly/Box.cc

    r1d7b0a8 r982f95d  
    3838#include "Lvalue.h"                      // for generalizedLvalue
    3939#include "Parser/LinkageSpec.h"          // for C, Spec, Cforall, Intrinsic
    40 #include "ResolvExpr/TypeEnvironment.h"  // for EqvClass
    4140#include "ResolvExpr/typeops.h"          // for typesCompatible
    4241#include "ScopedSet.h"                   // for ScopedSet, ScopedSet<>::iter...
     
    592591                        // pass size/align for type variables
    593592                        for ( TyVarMap::const_iterator tyParm = exprTyVars.begin(); tyParm != exprTyVars.end(); ++tyParm ) {
    594                                 ResolvExpr::EqvClass eqvClass;
    595593                                assert( env );
    596594                                if ( tyParm->second.isComplete ) {
  • src/ResolvExpr/AdjustExprType.cc

    r1d7b0a8 r982f95d  
    1919#include "SynTree/Mutator.h"      // for Mutator
    2020#include "SynTree/Type.h"         // for PointerType, TypeInstType, Type
    21 #include "TypeEnvironment.h"      // for EqvClass, TypeEnvironment
     21#include "TypeEnvironment.h"      // for ClassRef, TypeEnvironment
    2222
    2323namespace ResolvExpr {
     
    7474
    7575        Type * AdjustExprType::postmutate( TypeInstType * typeInst ) {
    76                 if ( const EqvClass* eqvClass = env.lookup( typeInst->get_name() ) ) {
    77                         if ( eqvClass->data.kind == TypeDecl::Ftype ) {
     76                if ( ClassRef eqvClass = env.lookup( typeInst->get_name() ) ) {
     77                        if ( eqvClass.get_bound().data.kind == TypeDecl::Ftype ) {
    7878                                return new PointerType{ Type::Qualifiers(), typeInst };
    7979                        }
  • src/ResolvExpr/AlternativeFinder.cc

    r1d7b0a8 r982f95d  
    11091109                                        }
    11101110                                } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->get_result()->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer)
    1111                                         if ( const EqvClass *eqvClass = func->env.lookup( typeInst->get_name() ) ) {
    1112                                                 if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass->type ) ) {
     1111                                        if ( ClassRef eqvClass = func->env.lookup( typeInst->get_name() ) ) {
     1112                                                if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass.get_bound().type ) ) {
    11131113                                                        Alternative newFunc( *func );
    11141114                                                        referenceToRvalueConversion( newFunc.expr, newFunc.cost );
  • src/ResolvExpr/CastCost.cc

    r1d7b0a8 r982f95d  
    1818#include "ConversionCost.h"              // for ConversionCost
    1919#include "Cost.h"                        // for Cost, Cost::infinity
    20 #include "ResolvExpr/TypeEnvironment.h"  // for TypeEnvironment, EqvClass
     20#include "ResolvExpr/TypeEnvironment.h"  // for TypeEnvironment, ClassRef
    2121#include "SymTab/Indexer.h"              // for Indexer
    2222#include "SynTree/Declaration.h"         // for TypeDecl, NamedTypeDecl
     
    4343        Cost castCost( Type *src, Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env ) {
    4444                if ( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) {
    45                         if ( const EqvClass* eqvClass = env.lookup( destAsTypeInst->get_name() ) ) {
    46                                 if ( eqvClass->type ) {
    47                                         return castCost( src, eqvClass->type, indexer, env );
     45                        if ( ClassRef eqvClass = env.lookup( destAsTypeInst->get_name() ) ) {
     46                                if ( Type* boundTy = eqvClass.get_bound().type ) {
     47                                        return castCost( src, boundTy, indexer, env );
    4848                                } else {
    4949                                        return Cost::infinity;
  • src/ResolvExpr/ConversionCost.cc

    r1d7b0a8 r982f95d  
    2222#include "Common/GC.h"                   // for new_static_root
    2323#include "ResolvExpr/Cost.h"             // for Cost
    24 #include "ResolvExpr/TypeEnvironment.h"  // for EqvClass, TypeEnvironment
     24#include "ResolvExpr/TypeEnvironment.h"  // for ClassRef, TypeEnvironment
    2525#include "SymTab/Indexer.h"              // for Indexer
    2626#include "SynTree/Declaration.h"         // for TypeDecl, NamedTypeDecl
     
    4444                if ( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) {
    4545                        PRINT( std::cerr << "type inst " << destAsTypeInst->name; )
    46                         if ( const EqvClass* eqvClass = env.lookup( destAsTypeInst->name ) ) {
    47                                 if ( eqvClass->type ) {
    48                                         return conversionCost( src, eqvClass->type, indexer, env );
     46                        if ( ClassRef eqvClass = env.lookup( destAsTypeInst->name ) ) {
     47                                if ( Type* boundTy = eqvClass.get_bound().type ) {
     48                                        return conversionCost( src, boundTy, indexer, env );
    4949                                } else {
    5050                                        return Cost::infinity;
     
    360360
    361361        void ConversionCost::postvisit( TypeInstType *inst ) {
    362                 if ( const EqvClass *eqvClass = env.lookup( inst->name ) ) {
    363                         cost = costFunc( eqvClass->type, dest, indexer, env );
     362                if ( ClassRef eqvClass = env.lookup( inst->name ) ) {
     363                        cost = costFunc( eqvClass.get_bound().type, dest, indexer, env );
    364364                } else if ( TypeInstType *destAsInst = dynamic_cast< TypeInstType* >( dest ) ) {
    365365                        if ( inst->name == destAsInst->name ) {
  • src/ResolvExpr/Occurs.cc

    r1d7b0a8 r982f95d  
    1414//
    1515
    16 #include <set>                // for set, _Rb_tree_const_iterator
    1716#include <string>             // for string
     17#include <unordered_set>      // for unordered_set
    1818
    1919#include "Common/PassVisitor.h"
    2020#include "SynTree/Type.h"     // for TypeInstType, Type
    21 #include "TypeEnvironment.h"  // for EqvClass, TypeEnvironment
     21#include "TypeEnvironment.h"  // for ClassRef, TypeEnvironment
    2222
    2323namespace ResolvExpr {
     
    2727
    2828                bool result;
    29                 std::set< std::string > eqvVars;
     29                using VarSet = std::unordered_set< std::string >;
     30                VarSet eqvVars;
    3031                const TypeEnvironment &tenv;
    3132        };
     
    3839
    3940        Occurs::Occurs( std::string varName, const TypeEnvironment & env ) : result( false ), tenv( env ) {
    40                 if ( const EqvClass *eqvClass = tenv.lookup( varName ) ) {
    41                         eqvVars = eqvClass->vars;
     41                if ( ClassRef eqvClass = tenv.lookup( varName ) ) {
     42                        eqvVars = eqvClass.get_vars<VarSet>();
    4243                } else {
    4344                        eqvVars.insert( varName );
     
    5152                if ( eqvVars.find( typeInst->get_name() ) != eqvVars.end() ) {
    5253                        result = true;
    53                 } else if ( const EqvClass *eqvClass = tenv.lookup( typeInst->get_name() ) ) {
    54                         if ( eqvClass->type ) {
     54                } else if ( ClassRef eqvClass = tenv.lookup( typeInst->get_name() ) ) {
     55                        if ( Type* boundTy = eqvClass.get_bound().type ) {
    5556///       std::cerr << typeInst->get_name() << " is bound to";
    56 ///       eqvClass.type->print( std::cerr );
     57///       boundTy->print( std::cerr );
    5758///       std::cerr << std::endl;
    58                                 eqvClass->type->accept( *visitor );
     59                                boundTy->accept( *visitor );
    5960                        } // if
    6061                } // if
  • src/ResolvExpr/PolyCost.cc

    r1d7b0a8 r982f95d  
    1717#include "SymTab/Indexer.h"   // for Indexer
    1818#include "SynTree/Type.h"     // for TypeInstType, Type
    19 #include "TypeEnvironment.h"  // for EqvClass, TypeEnvironment
     19#include "TypeEnvironment.h"  // for ClassRef, TypeEnvironment
    2020
    2121namespace ResolvExpr {
     
    3939
    4040        void PolyCost::previsit(TypeInstType * typeInst) {
    41                 if ( const EqvClass *eqvClass = tenv.lookup( typeInst->name ) ) {
    42                         if ( eqvClass->type ) {
    43                                 if ( TypeInstType * otherTypeInst = dynamic_cast< TypeInstType* >( eqvClass->type ) ) {
     41                if ( ClassRef eqvClass = tenv.lookup( typeInst->name ) ) {
     42                        if ( Type* boundTy = eqvClass.get_bound().type ) {
     43                                if ( TypeInstType * otherTypeInst = dynamic_cast< TypeInstType* >( boundTy ) ) {
    4444                                        if ( indexer.lookupType( otherTypeInst->name ) ) {
    4545                                                // bound to opaque type
  • src/ResolvExpr/PtrsAssignable.cc

    r1d7b0a8 r982f95d  
    1515
    1616#include "Common/PassVisitor.h"
    17 #include "ResolvExpr/TypeEnvironment.h"  // for EqvClass, TypeEnvironment
     17#include "ResolvExpr/TypeEnvironment.h"  // for ClassRef, TypeEnvironment
    1818#include "SynTree/Type.h"                // for TypeInstType, Type, BasicType
    1919#include "SynTree/Visitor.h"             // for Visitor
     
    5151                // std::cerr << "assignable: " << src << " | " << dest << std::endl;
    5252                if ( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) {
    53                         if ( const EqvClass *eqvClass = env.lookup( destAsTypeInst->get_name() ) ) {
    54                                 return ptrsAssignable( src, eqvClass->type, env );
     53                        if ( ClassRef eqvClass = env.lookup( destAsTypeInst->get_name() ) ) {
     54                                return ptrsAssignable( src, eqvClass.get_bound().type, env );
    5555                        } // if
    5656                } // if
     
    9494        void PtrsAssignable::postvisit(  __attribute__((unused)) TraitInstType *inst ) {}
    9595        void PtrsAssignable::postvisit( TypeInstType *inst ) {
    96                 if ( const EqvClass *eqvClass = env.lookup( inst->get_name() ) ) {
    97                         if ( eqvClass->type ) {
     96                if ( ClassRef eqvClass = env.lookup( inst->get_name() ) ) {
     97                        if ( Type* boundTy = eqvClass.get_bound().type ) {
    9898                                // T * = S * for any S depends on the type bound to T
    99                                 result = ptrsAssignable( eqvClass->type, dest, env );
     99                                result = ptrsAssignable( boundTy, dest, env );
    100100                        }
    101101                } // if
  • src/ResolvExpr/PtrsCastable.cc

    r1d7b0a8 r982f95d  
    1515
    1616#include "Common/PassVisitor.h"
    17 #include "ResolvExpr/TypeEnvironment.h"  // for EqvClass, TypeEnvironment
     17#include "ResolvExpr/TypeEnvironment.h"  // for ClassRef, TypeEnvironment
    1818#include "SymTab/Indexer.h"              // for Indexer
    1919#include "SynTree/Declaration.h"         // for TypeDecl, TypeDecl::Kind::Ftype
     
    6363                                                } // if
    6464                                        } //if
    65                                 } else if ( const EqvClass *eqvClass = env.lookup( typeInst->get_name() ) ) {
    66                                         if ( eqvClass->data.kind == TypeDecl::Ftype ) {
     65                                } else if ( ClassRef eqvClass = env.lookup( typeInst->get_name() ) ) {
     66                                        if ( eqvClass.get_bound().data.kind == TypeDecl::Ftype ) {
    6767                                                return -1;
    6868                                        } // if
     
    7878        int ptrsCastable( Type *src, Type *dest, const TypeEnvironment &env, const SymTab::Indexer &indexer ) {
    7979                if ( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) {
    80                         if ( const EqvClass *eqvClass = env.lookup( destAsTypeInst->get_name() ) ) {
     80                        if ( ClassRef eqvClass = env.lookup( destAsTypeInst->get_name() ) ) {
    8181                                // xxx - should this be ptrsCastable?
    82                                 return ptrsAssignable( src, eqvClass->type, env );
     82                                return ptrsAssignable( src, eqvClass.get_bound().type, env );
    8383                        } // if
    8484                } // if
  • src/ResolvExpr/TypeEnvironment.cc

    r1d7b0a8 r982f95d  
    1919#include <utility>                     // for pair, move
    2020
     21#include "Common/InternedString.h"     // for interned_string
    2122#include "Common/PassVisitor.h"        // for PassVisitor<GcTracer>
    2223#include "Common/utility.h"            // for maybeClone
     24#include "SymTab/Indexer.h"            // for Indexer
    2325#include "SynTree/GcTracer.h"          // for PassVisitor<GcTracer>
    2426#include "SynTree/Type.h"              // for Type, FunctionType, Type::Fora...
    2527#include "SynTree/TypeSubstitution.h"  // for TypeSubstitution
    2628#include "TypeEnvironment.h"
     29#include "Unify.h"                     // for unifyInexact
    2730
    2831namespace ResolvExpr {
     
    4548        }
    4649
     50#if 0
    4751        void EqvClass::initialize( const EqvClass &src, EqvClass &dest ) {
    4852                dest.vars = src.vars;
     
    5256        }
    5357
    54         EqvClass::EqvClass() : type( 0 ), allowWidening( true ) {
    55         }
     58        EqvClass::EqvClass() : vars(), type( 0 ), allowWidening( true ), data() {}
     59
     60        EqvClass::EqvClass( std::vector<interned_string>&& vs, BoundType&& bound )
     61                : vars( vs.begin(), vs.end() ), type( maybeClone( bound.type ) ),
     62                  allowWidening( bound.allowWidening ), data( bound.data ) {}
    5663
    5764        EqvClass::EqvClass( const EqvClass &other ) {
     
    9198                return nullptr;
    9299        }
    93 
     100#endif
     101
     102        std::pair<interned_string, interned_string> TypeEnvironment::mergeClasses(
     103                        interned_string root1, interned_string root2 ) {
     104                // merge classes
     105                Classes* newClasses = classes->merge( root1, root2 );
     106
     107                // determine new root
     108                assertf(classes->get_mode() == Classes::REMFROM, "classes updated to REMFROM by merge");
     109                auto ret = std::make_pair( classes->get_root(), classes->get_child );
     110               
     111                // finalize classes
     112                classes = newClasses;
     113                return ret;
     114        }
     115
     116        ClassRef TypeEnvironment::lookup( interned_string var ) const {
     117                interned_string root = classes->find_or_default( var, nullptr );
     118                if ( root ) return { this, root };
     119                else return { nullptr, var };
     120        }
     121
     122        bool tyVarCompatible( const TypeDecl::Data & data, Type *type ) {
     123                switch ( data.kind ) {
     124                  case TypeDecl::Dtype:
     125                        // to bind to an object type variable, the type must not be a function type.
     126                        // if the type variable is specified to be a complete type then the incoming
     127                        // type must also be complete
     128                        // xxx - should this also check that type is not a tuple type and that it's not a ttype?
     129                        return ! isFtype( type ) && (! data.isComplete || type->isComplete() );
     130                  case TypeDecl::Ftype:
     131                        return isFtype( type );
     132                  case TypeDecl::Ttype:
     133                        // ttype unifies with any tuple type
     134                        return dynamic_cast< TupleType * >( type ) || Tuples::isTtype( type );
     135                } // switch
     136                return false;
     137        }
     138
     139        bool TypeEnvironment::bindVar( TypeInstType* typeInst, Type* bindTo,
     140                        const TypeDecl::Data& data, AssertionSet& need, AssertionSet& have,
     141                        const OpenVarSet& openVars, WidenMode widenMode, const SymTab::Indexer& indexer ) {
     142                // remove references from other, so that type variables can only bind to value types
     143                bindTo = bindTo->stripReferences();
     144               
     145                auto tyVar = openVars.find( typeInst->get_name() );
     146                assert( tyVar != openVars.end() );
     147                if ( ! tyVarCompatible( tyVar->second, other ) ) return false;
     148
     149                if ( occurs( bindTo, typeInst->get_name(), *this ) ) return false;
     150
     151                if ( ClassRef curClass = lookup( typeInst->get_name() ) ) {
     152                        BoundType curData = curClass.get_bound();
     153                        if ( curData.type ) {
     154                                Type* common = nullptr;
     155                                // attempt to unify equivalence class type (which needs its qualifiers restored)
     156                                // with the target type
     157                                Type* newType = curData.type->clone();
     158                                newType->get_qualifiers() = typeInst->get_qualifiers();
     159                                if ( unifyInexact( newType, bindTo, *this, need, have, openVars,
     160                                                widenMode & WidenMode{ curData.allowWidening, true }, indexer, common ) ) {
     161                                        if ( common ) {
     162                                                // update bound type to common type
     163                                                common->get_qualifiers() = Type::Qualifiers{};
     164                                                curData.type = common;
     165                                                bindings = bindings->set( curClass.update_root(), curData );
     166                                        }
     167                                        return true;
     168                                } else return false;
     169                        } else {
     170                                // update bound type to other type
     171                                curData.type = bindTo->clone();
     172                                curData.type->get_qualifiers() = Type::Qualifiers{};
     173                                curData.allowWidening = widenMode.widenFirst && widenMode.widenSecond;
     174                                bindings = bindings->set( curClass.get_root(), curData );
     175                        }
     176                } else {
     177                        // make new class consisting entirely of this variable
     178                        BoundType curData{ bindTo->clone(), widenMode.first && widenMode.second, data };
     179                        curData.type->get_qualifiers() = Type::Qualifiers{};
     180                        classes = classes->add( curClass.get_root() );
     181                        bindings = bindings->set( curClass.get_root(), curData );
     182                }
     183                return true;
     184        }
     185       
     186        bool TypeEnvironment::bindVarToVar( TypeInstType* var1, TypeInstType* var2,
     187                        const TypeDecl::Data& data, AssertionSet& need, AssertionSet& have,
     188                        const OpenVarSet& openVars, WidenMode widenMode, const SymTab::Indexer& indexer ) {
     189                ClassRef class1 = env.lookup( var1->get_name() );
     190                ClassRef class2 = env.lookup( var2->get_name() );
     191               
     192                // exit early if variables already bound together
     193                if ( class1 && class2 && class1 == class2 ) {
     194                        BoundType data1 = class1.get_bound();
     195                        // narrow the binding if needed
     196                        if ( data1.allowWidening && widenMode.first != widenMode.second ) {
     197                                data1.allowWidening = false;
     198                                bindings = bindings->set( class1.get_root(), data1 );
     199                        }
     200                        return true;
     201                }
     202
     203                BoundType data1 = class1 ? class1.get_bound() : BoundType{};
     204                BoundType data2 = class2 ? class2.get_bound() : BoundType{};
     205
     206                bool widen1 = data1.allowWidening && widenMode.widenFirst;
     207                bool widen2 = data2.allowWidening && widenMode.widenSecond;
     208
     209                if ( data1.type && data2.type ) {
     210                        // attempt to unify bound classes
     211                        Type* common = nullptr;
     212                        if ( unifyInexact( data1.type->clone(), data2.type->clone(), *this, need, have,
     213                                        openVars, WidenMode{ widen1, widen2 }, indexer, common ) ) {
     214                                // merge type variables
     215                                interned_string root = mergeClasses( class1.update_root(), class2.update_root() );
     216                                // update bindings
     217                                data1.allowWidening = widen1 && widen2;
     218                                if ( common ) {
     219                                        common->get_qualifiers() = Type::Qualifiers{};
     220                                        data1.type = common;
     221                                }
     222                                bindings = bindings->set( root, data1 );
     223                        } else return false;
     224                } else if ( class1 && class2 ) {
     225                        // both classes exist, only one bound -- merge type variables
     226                        auto merged = mergeClasses( class1.get_root(), class2.get_root() );
     227                        // remove subordinate binding
     228                        bindings = bindings->erase( merged.second );
     229                        // update root binding (narrow widening as needed, or set new binding for changed root)
     230                        if ( data1.type ) {
     231                                if ( data1.allowWidening != widen1 ) {
     232                                        data1.allowWidening = widen1;
     233                                        bindings = bindings->set( merged.first, data1 );
     234                                } else if ( merged.first == class2.get_root() ) {
     235                                        bindings = bindings->set( merged.first, data1 );
     236                                }
     237                        } else /* if ( data2.type ) */ {
     238                                if ( data2.allowWidening != widen2 ) {
     239                                        data2.allowWidening = widen2;
     240                                        bindings = bindings->set( root, data2 );
     241                                } else if ( merged.first == class1.get_root() ) {
     242                                        bindings = bindings->set( merged.first, data2 );
     243                                }
     244                        }
     245                } else if ( class1 ) {
     246                        // add unbound var2 to class1
     247                        classes = classes->add( class2.get_root() );
     248                        auto merged = mergeClasses( class1.get_root(), class2.get_root() );
     249                        // update bindings (narrow as needed, or switch binding to root)
     250                        if ( merged.first == class2.get_root() ) {
     251                                data1.allowWidening = widen1;
     252                                bindings = bindings->erase( merged.second )->set( merged.first, data1 );
     253                        } else if ( data1.allowWidening != widen1 ) {
     254                                bindings = bindings->set( merged.first, data1 );
     255                        }
     256                } else if ( class2 ) {
     257                        // add unbound var1 to class1
     258                        classes = classes->add( class1.get_root() );
     259                        auto merged = mergeClasses( class1.get_root(), class2.get_root() );
     260                        // update bindings (narrow as needed, or switch binding to root)
     261                        if ( merged.first == class1.get_root() ) {
     262                                data2.allowWidening = widen2;
     263                                bindings = bindings->erase( merged.second )->set( merged.first, data2 );
     264                        } else if ( data2.allowWidening != widen2 ) {
     265                                bindings = bindings->set( merged.first, data2 );
     266                        }
     267                } else {
     268                        // make new class with pair of unbound vars
     269                        classes = classes->add( class1.get_root() )->add( class2.get_root() );
     270                        auto merged = mergeClasses( class1.get_root(), class2.get_root() );
     271                        bindings = bindings->set( merged.first, BoundType{ nullptr, widen1 && widen2, data } );
     272                }
     273                return true;
     274        }
     275
     276#if !1
    94277        /// Removes any class from env that intersects eqvClass
    95278        void filterOverlappingClasses( std::list<EqvClass> &env, const EqvClass &eqvClass ) {
     
    180363        }
    181364
    182         void TypeEnvironment::combine( const TypeEnvironment &second, Type *(*combineFunc)( Type*, Type* ) ) {
    183                 TypeEnvironment secondCopy( second );
    184                 for ( std::list< EqvClass >::iterator firstClass = env.begin(); firstClass != env.end(); ++firstClass ) {
    185                         EqvClass &newClass = *firstClass;
    186                         std::set< std::string > newVars;
    187                         for ( std::set< std::string >::const_iterator var = firstClass->vars.begin(); var != firstClass->vars.end(); ++var ) {
    188                                 std::list< EqvClass >::iterator secondClass = secondCopy.internal_lookup( *var );
    189                                 if ( secondClass != secondCopy.env.end() ) {
    190                                         newVars.insert( secondClass->vars.begin(), secondClass->vars.end() );
    191                                         if ( secondClass->type ) {
    192                                                 if ( newClass.type ) {
    193                                                         newClass.type = combineFunc( newClass.type, secondClass->type );
    194                                                         newClass.allowWidening = newClass.allowWidening && secondClass->allowWidening;
    195                                                 } else {
    196                                                         newClass.type = secondClass->type->clone();
    197                                                         newClass.allowWidening = secondClass->allowWidening;
    198                                                 } // if
    199                                         } // if
    200                                         secondCopy.env.erase( secondClass );
    201                                 } // if
    202                         } // for
    203                         newClass.vars.insert( newVars.begin(), newVars.end() );
    204                 } // for
    205                 for ( std::list< EqvClass >::iterator secondClass = secondCopy.env.begin(); secondClass != secondCopy.env.end(); ++secondClass ) {
    206                         env.push_back( *secondClass );
    207                 } // for
    208         }
    209 
    210365        void TypeEnvironment::extractOpenVars( OpenVarSet &openVars ) const {
    211366                for ( std::list< EqvClass >::const_iterator eqvClass = env.begin(); eqvClass != env.end(); ++eqvClass ) {
     
    231386                return out;
    232387        }
     388#endif
    233389
    234390        PassVisitor<GcTracer> & operator<<( PassVisitor<GcTracer> & gc, const TypeEnvironment & env ) {
    235                 for ( const EqvClass & c : env ) {
    236                         maybeAccept( c.type, gc );
     391                for ( ClassRef c : env ) {
     392                        maybeAccept( c.get_bound().type, gc );
    237393                }
    238394                return gc;
  • src/ResolvExpr/TypeEnvironment.h

    r1d7b0a8 r982f95d  
    77// TypeEnvironment.h --
    88//
    9 // Author           : Richard C. Bilson
     9// Author           : Aaron B. Moss
    1010// Created On       : Sun May 17 12:24:58 2015
    11 // Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sat Jul 22 09:35:45 2017
    13 // Update Count     : 3
     11// Last Modified By : Aaron B. Moss
     12// Last Modified On : Wed Jun 13 16:31:00 2018
     13// Update Count     : 4
    1414//
    1515
    1616#pragma once
    1717
    18 #include <iostream>                    // for ostream
    19 #include <list>                        // for list, list<>::iterator, list<>...
    20 #include <map>                         // for map, map<>::value_compare
    21 #include <set>                         // for set
    22 #include <string>                      // for string
    23 
    24 #include "SynTree/Declaration.h"       // for TypeDecl::Data, DeclarationWit...
    25 #include "SynTree/SynTree.h"           // for UniqueId
    26 #include "SynTree/Type.h"              // for Type, Type::ForallList
    27 #include "SynTree/TypeSubstitution.h"  // for TypeSubstitution
    28 
    29 template< typename Pass >
    30 class PassVisitor;
     18#include <iostream>                        // for ostream
     19#include <iterator>
     20#include <list>                            // for list, list<>::iterator, list<>...
     21#include <map>                             // for map, map<>::value_compare
     22#include <set>                             // for set
     23#include <string>                          // for string
     24#include <utility>                         // for pair
     25#include <vector>                          // for vector
     26
     27#include "Common/InternedString.h"         // for interned_string
     28#include "Common/PersistentDisjointSet.h"  // for PersistentDisjointSet
     29#include "Common/PersistentMap.h"          // for PersistentMap
     30#include "SynTree/Declaration.h"           // for TypeDecl::Data, DeclarationWit...
     31#include "SynTree/SynTree.h"               // for UniqueId
     32#include "SynTree/Type.h"                  // for Type, TypeInstType, Type::ForallList
     33#include "SynTree/TypeSubstitution.h"      // for TypeSubstitution
     34
     35template< typename Pass > class PassVisitor;
    3136class GcTracer;
     37namespace SymTab { class Indexer; }
    3238
    3339namespace ResolvExpr {
     
    4046        // declarations.
    4147        //
    42         // I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this comparator.
     48        // I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this
     49        // comparator.
    4350        //
    4451        // Note: since this compares pointers for position, minor changes in the source file that affect
    4552        // memory layout can alter compilation time in unpredictable ways. For example, the placement
    4653        // of a line directive can reorder type pointers with respect to each other so that assertions
    47         // are seen in different orders, causing a potentially different number of unification calls when
    48         // resolving assertions. I've seen a TU go from 36 seconds to 27 seconds by reordering line directives
    49         // alone, so it would be nice to fix this comparison so that assertions compare more consistently.
    50         // I've tried to modify this to compare on mangle name instead of type as the second comparator, but
    51         // this causes some assertions to never be recorded. More investigation is needed.
     54        // are seen in different orders, causing a potentially different number of unification calls
     55        // when resolving assertions. I've seen a TU go from 36 seconds to 27 seconds by reordering
     56        // line directives alone, so it would be nice to fix this comparison so that assertions compare
     57        // more consistently. I've tried to modify this to compare on mangle name instead of type as
     58        // the second comparator, but this causes some assertions to never be recorded. More
     59        // investigation is needed.
    5260        struct AssertCompare {
    5361                bool operator()( DeclarationWithType * d1, DeclarationWithType * d2 ) const {
     
    5967        struct AssertionSetValue {
    6068                bool isUsed;
    61                 // chain of Unique IDs of the assertion declarations. The first ID in the chain is the ID of an assertion on the current type,
    62                 // with each successive ID being the ID of an assertion pulled in by the previous ID. The last ID in the chain is
    63                 // the ID of the assertion that pulled in the current assertion.
     69                // chain of Unique IDs of the assertion declarations. The first ID in the chain is the ID
     70                // of an assertion on the current type, with each successive ID being the ID of an
     71                // assertion pulled in by the previous ID. The last ID in the chain is the ID of the
     72                // assertion that pulled in the current assertion.
    6473                std::list< UniqueId > idChain;
    6574        };
     
    7079        void printOpenVarSet( const OpenVarSet &, std::ostream &, int indent = 0 );
    7180
     81        /// A data structure for holding all the necessary information for a type binding
     82        struct BoundType {
     83                Type* type;
     84                bool allowWidening;
     85                TypeDecl::Data data;
     86        };
     87
     88#if 0
     89        /// An equivalence class, with its binding information
    7290        struct EqvClass {
    7391                std::set< std::string > vars;
     
    7896                void initialize( const EqvClass &src, EqvClass &dest );
    7997                EqvClass();
     98                EqvClass( std::vector<interned_string>&& vars, BoundType&& bound );
    8099                EqvClass( const EqvClass &other );
    81100                EqvClass &operator=( const EqvClass &other );
    82101                void print( std::ostream &os, Indenter indent = {} ) const;
    83102        };
     103#endif
     104
     105        class TypeEnvironment;
     106
     107        /// A reference to an equivalence class that may be used to constitute one from its environment
     108        class ClassRef {
     109                friend TypeEnvironment;
     110
     111                const TypeEnvironment* env;  ///< Containing environment
     112                interned_string root;        ///< Name of root type
     113
     114        public:
     115                ClassRef() : env(nullptr), root(nullptr) {}
     116                ClassRef( const TypeEnvironment* env, interned_string root ) : env(env), root(root) {}
     117
     118                /// Gets the root of the reference equivalence class;
     119                interned_string get_root() const { return root; }
     120
     121                /// Ensures that root is still the representative element of this typeclass;
     122                /// undefined behaviour if called without referenced typeclass; returns new root
     123                inline interned_string update_root();
     124
     125                /// Gets the type variables of the referenced equivalence class, empty list for none
     126                template<typename T = std::vector<interned_string>>
     127                inline T get_vars() const;
     128
     129                /// Gets the bound type information of the referenced equivalence class, default if none
     130                inline BoundType get_bound() const;
     131
     132#if 0
     133                /// Gets the referenced equivalence class
     134                inline EqvClass get_class() const;
     135                EqvClass operator* () const { return get_class(); }
     136#endif
     137
     138                // Check that there is a referenced typeclass
     139                explicit operator bool() const { return env != nullptr; }
     140
     141                bool operator== (const ClassRef& o) const { return env == o.env && root == o.root; }
     142                bool operator!= (const ClassRef& o) const { return !(*this == o); }
     143        };
    84144
    85145        class TypeEnvironment {
     146                friend ClassRef;
     147
     148                /// Backing storage for equivalence classes
     149                using Classes = PersistentDisjointSet<interned_string>;
     150                /// Type bindings included in this environment (from class root)
     151                using Bindings = PersistentMap<interned_string, BoundType>;
     152
     153                /// Sets of equivalent type variables, stored by name
     154                Classes* classes;
     155                /// Bindings from roots of equivalence classes to type binding information.
     156                /// All roots have a binding so that the list of classes can be reconstituted, though these
     157                /// may be null.
     158                Bindings* bindings;
     159
     160                /// Merges the classes rooted at root1 and root2, returning a pair containing the root and
     161                /// child of the bound class. Does not check for validity of merge.
     162                std::pair<interned_string, interned_string> mergeClasses(
     163                        interned_string root1, interned_string root2 );
     164
    86165          public:
    87                 const EqvClass* lookup( const std::string &var ) const;
     166                class iterator : public std::iterator<
     167                                std::forward_iterator_tag,
     168                                ClassRef,
     169                                std::iterator_traits<Bindings::iterator>::difference_type,
     170                                ClassRef,
     171                                ClassRef> {
     172                        friend TypeEnvironment;
     173                       
     174                        const TypeEnvironment* env;
     175                        Bindings::iterator it;
     176
     177                        iterator(const TypeEnvironment* e, Bindings::iterator&& i) : env(e), it(std::move(i)) {}
     178
     179                        ClassRef ref() const { return { env, it->first }; }
     180                public:
     181                        iterator() = default;
     182
     183                        reference operator* () { return ref(); }
     184                        pointer operator-> () { return ref(); }
     185
     186                        iterator& operator++ () { ++it; return *this; }
     187                        iterator operator++ (int) { iterator tmp = *this; ++(*this); return tmp; }
     188
     189                        bool operator== (const iterator& o) const { return env == o.env && it == o.it; }
     190                        bool operator!= (const iterator& o) const { return !(*this == o); }
     191                };
     192
     193                /// Finds a reference to the class containing `var`, invalid if none such.
     194                /// returned root variable will be valid regardless
     195                ClassRef lookup( interned_string var ) const;
     196                ClassRef lookup( const std::string &var ) const { return lookup( var ); }
     197
     198                /// Binds a type variable to a type; returns false if fails
     199                bool bindVar( TypeInstType* typeInst, Type* bindTo, const TypeDecl::Data& data,
     200                        AssertionSet& need, AssertionSet& have, const OpenVarSet& openVars,
     201                        WidenMode widenMode, const SymTab::Indexer& indexer );
     202               
     203                /// Binds two type variables together; returns false if fails
     204                bool bindVarToVar( TypeInstType* var1, TypeInstType* var2, const TypeDecl::Data& data,
     205                        AssertionSet& need, AssertionSet& have, const OpenVarSet& openVars,
     206                        WidenMode widenMode, const SymTab::Indexer& indexer );
     207#if !1
    88208                void add( const EqvClass &eqvClass );
    89209                void add( EqvClass &&eqvClass  );
     
    93213                template< typename SynTreeClass > int applyFree( SynTreeClass *&type ) const;
    94214                void makeSubstitution( TypeSubstitution &result ) const;
    95                 bool isEmpty() const { return env.empty(); }
     215#endif
     216                bool isEmpty() const { return classes->empty(); }
     217#if !1
    96218                void print( std::ostream &os, Indenter indent = {} ) const;
    97                 void combine( const TypeEnvironment &second, Type *(*combineFunc)( Type*, Type* ) );
    98219                void simpleCombine( const TypeEnvironment &second );
    99220                void extractOpenVars( OpenVarSet &openVars ) const;
     221#endif
    100222                TypeEnvironment *clone() const { return new TypeEnvironment( *this ); }
    101223
     224#if !1
    102225                /// Iteratively adds the environment of a new actual (with allowWidening = false),
    103226                /// and extracts open variables.
    104227                void addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars );
    105 
    106                 typedef std::list< EqvClass >::iterator iterator;
    107                 iterator begin() { return env.begin(); }
    108                 iterator end() { return env.end(); }
     228#endif
     229
     230                iterator begin() { return { this, bindings->begin() }; }
     231                iterator end() { return { this, bindings->end() }; }
     232#if 0
    109233                typedef std::list< EqvClass >::const_iterator const_iterator;
    110234                const_iterator begin() const { return env.begin(); }
    111235                const_iterator end() const { return env.end(); }
    112           private:
    113                 std::list< EqvClass > env;
    114                 std::list< EqvClass >::iterator internal_lookup( const std::string &var );
    115         };
     236#endif
     237        };
     238
     239        void ClassRef::update_root() { return root = env->classes->find( root ); }
     240
     241        template<typename T>
     242        T ClassRef::get_vars() const {
     243                T vars;
     244                env->classes->find_class( root, std::inserter(vars, vars.end()) );
     245                return vars;
     246        }
     247
     248        BoundType ClassRef::get_bound() const {
     249                return env->bindings->get_or_default( root, BoundType{} );
     250        }
     251
     252#if 0
     253        EqvClass ClassRef::get_class() const { return { get_vars(), get_bound() }; }
     254#endif
    116255
    117256        template< typename SynTreeClass >
     
    129268        }
    130269
     270#if !1
    131271        std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env );
     272#endif
    132273
    133274        PassVisitor<GcTracer> & operator<<( PassVisitor<GcTracer> & gc, const TypeEnvironment & env );
  • src/ResolvExpr/Unify.cc

    r1d7b0a8 r982f95d  
    3131#include "SynTree/Visitor.h"      // for Visitor
    3232#include "Tuples/Tuples.h"        // for isTtype
    33 #include "TypeEnvironment.h"      // for EqvClass, AssertionSet, OpenVarSet
     33#include "TypeEnvironment.h"      // for ClassRef, AssertionSet, OpenVarSet
    3434#include "Unify.h"
    3535#include "typeops.h"              // for flatten, occurs, commonType
     
    128128                        return typeInst->get_isFtype();
    129129                } // if
    130                 return false;
    131         }
    132 
    133         bool tyVarCompatible( const TypeDecl::Data & data, Type *type ) {
    134                 switch ( data.kind ) {
    135                   case TypeDecl::Dtype:
    136                         // to bind to an object type variable, the type must not be a function type.
    137                         // if the type variable is specified to be a complete type then the incoming
    138                         // type must also be complete
    139                         // xxx - should this also check that type is not a tuple type and that it's not a ttype?
    140                         return ! isFtype( type ) && (! data.isComplete || type->isComplete() );
    141                   case TypeDecl::Ftype:
    142                         return isFtype( type );
    143                   case TypeDecl::Ttype:
    144                         // ttype unifies with any tuple type
    145                         return dynamic_cast< TupleType * >( type ) || Tuples::isTtype( type );
    146                 } // switch
    147130                return false;
    148131        }
     
    525508                void premutate( TypeInstType * ) { visit_children = false; }
    526509                Type * postmutate( TypeInstType * typeInst ) {
    527                         if ( const EqvClass *eqvClass = tenv.lookup( typeInst->get_name() ) ) {
     510                        if ( ClassRef eqvClass = tenv.lookup( typeInst->get_name() ) ) {
    528511                                // expand ttype parameter into its actual type
    529                                 if ( eqvClass->data.kind == TypeDecl::Ttype && eqvClass->type ) {
    530                                         return eqvClass->type->clone();
     512                                BoundType cBound = eqvClass.get_bound();
     513                                if ( cBound.data.kind == TypeDecl::Ttype && cBound.type ) {
     514                                        return cBound.type->clone();
    531515                                }
    532516                        }
Note: See TracChangeset for help on using the changeset viewer.