Changes in / [97397a26:b60f9d9]
- Location:
- src
- Files:
-
- 4 deleted
- 13 edited
-
Common/InternedString.cc (deleted)
-
Common/InternedString.h (deleted)
-
Common/PersistentDisjointSet.h (deleted)
-
Common/PersistentMap.h (deleted)
-
Common/module.mk (modified) (2 diffs)
-
GenPoly/Box.cc (modified) (2 diffs)
-
ResolvExpr/AdjustExprType.cc (modified) (2 diffs)
-
ResolvExpr/AlternativeFinder.cc (modified) (1 diff)
-
ResolvExpr/CastCost.cc (modified) (2 diffs)
-
ResolvExpr/ConversionCost.cc (modified) (3 diffs)
-
ResolvExpr/Occurs.cc (modified) (4 diffs)
-
ResolvExpr/PolyCost.cc (modified) (2 diffs)
-
ResolvExpr/PtrsAssignable.cc (modified) (3 diffs)
-
ResolvExpr/PtrsCastable.cc (modified) (3 diffs)
-
ResolvExpr/TypeEnvironment.cc (modified) (6 diffs)
-
ResolvExpr/TypeEnvironment.h (modified) (7 diffs)
-
ResolvExpr/Unify.cc (modified) (3 diffs)
Legend:
- Unmodified
- Added
- Removed
-
src/Common/module.mk
r97397a26 rb60f9d9 10 10 ## Author : Richard C. Bilson 11 11 ## Created On : Mon Jun 1 17:49:17 2015 12 ## Last Modified By : Aaron B. Moss13 ## Last Modified On : T hu Jun 14 11:15:00 201814 ## Update Count : 512 ## Last Modified By : Peter A. Buhr 13 ## Last Modified On : Tue Sep 27 11:06:38 2016 14 ## Update Count : 4 15 15 ############################################################################### 16 16 … … 20 20 Common/GC.cc \ 21 21 Common/Assert.cc \ 22 Common/InternedString.cc \23 22 Common/Heap.cc -
src/GenPoly/Box.cc
r97397a26 rb60f9d9 38 38 #include "Lvalue.h" // for generalizedLvalue 39 39 #include "Parser/LinkageSpec.h" // for C, Spec, Cforall, Intrinsic 40 #include "ResolvExpr/TypeEnvironment.h" // for EqvClass 40 41 #include "ResolvExpr/typeops.h" // for typesCompatible 41 42 #include "ScopedSet.h" // for ScopedSet, ScopedSet<>::iter... … … 591 592 // pass size/align for type variables 592 593 for ( TyVarMap::const_iterator tyParm = exprTyVars.begin(); tyParm != exprTyVars.end(); ++tyParm ) { 594 ResolvExpr::EqvClass eqvClass; 593 595 assert( env ); 594 596 if ( tyParm->second.isComplete ) { -
src/ResolvExpr/AdjustExprType.cc
r97397a26 rb60f9d9 19 19 #include "SynTree/Mutator.h" // for Mutator 20 20 #include "SynTree/Type.h" // for PointerType, TypeInstType, Type 21 #include "TypeEnvironment.h" // for ClassRef, TypeEnvironment21 #include "TypeEnvironment.h" // for EqvClass, TypeEnvironment 22 22 23 23 namespace ResolvExpr { … … 74 74 75 75 Type * AdjustExprType::postmutate( TypeInstType * typeInst ) { 76 if ( ClassRefeqvClass = env.lookup( typeInst->get_name() ) ) {77 if ( eqvClass .get_bound().data.kind == TypeDecl::Ftype ) {76 if ( const EqvClass* eqvClass = env.lookup( typeInst->get_name() ) ) { 77 if ( eqvClass->data.kind == TypeDecl::Ftype ) { 78 78 return new PointerType{ Type::Qualifiers(), typeInst }; 79 79 } -
src/ResolvExpr/AlternativeFinder.cc
r97397a26 rb60f9d9 1410 1410 } 1411 1411 } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( func->expr->get_result()->stripReferences() ) ) { // handle ftype (e.g. *? on function pointer) 1412 if ( ClassRefeqvClass = func->env.lookup( typeInst->get_name() ) ) {1413 if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass .get_bound().type ) ) {1412 if ( const EqvClass *eqvClass = func->env.lookup( typeInst->get_name() ) ) { 1413 if ( FunctionType *function = dynamic_cast< FunctionType* >( eqvClass->type ) ) { 1414 1414 Alternative newFunc( *func ); 1415 1415 referenceToRvalueConversion( newFunc.expr, newFunc.cost ); -
src/ResolvExpr/CastCost.cc
r97397a26 rb60f9d9 18 18 #include "ConversionCost.h" // for ConversionCost 19 19 #include "Cost.h" // for Cost, Cost::infinity 20 #include "ResolvExpr/TypeEnvironment.h" // for TypeEnvironment, ClassRef20 #include "ResolvExpr/TypeEnvironment.h" // for TypeEnvironment, EqvClass 21 21 #include "SymTab/Indexer.h" // for Indexer 22 22 #include "SynTree/Declaration.h" // for TypeDecl, NamedTypeDecl … … 43 43 Cost castCost( Type *src, Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env ) { 44 44 if ( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) { 45 if ( ClassRefeqvClass = env.lookup( destAsTypeInst->get_name() ) ) {46 if ( Type* boundTy = eqvClass.get_bound().type ) {47 return castCost( src, boundTy, indexer, env );45 if ( const EqvClass* eqvClass = env.lookup( destAsTypeInst->get_name() ) ) { 46 if ( eqvClass->type ) { 47 return castCost( src, eqvClass->type, indexer, env ); 48 48 } else { 49 49 return Cost::infinity; -
src/ResolvExpr/ConversionCost.cc
r97397a26 rb60f9d9 22 22 #include "Common/GC.h" // for new_static_root 23 23 #include "ResolvExpr/Cost.h" // for Cost 24 #include "ResolvExpr/TypeEnvironment.h" // for ClassRef, TypeEnvironment24 #include "ResolvExpr/TypeEnvironment.h" // for EqvClass, TypeEnvironment 25 25 #include "SymTab/Indexer.h" // for Indexer 26 26 #include "SynTree/Declaration.h" // for TypeDecl, NamedTypeDecl … … 46 46 if ( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) { 47 47 PRINT( std::cerr << "type inst " << destAsTypeInst->name; ) 48 if ( ClassRefeqvClass = env.lookup( destAsTypeInst->name ) ) {49 if ( Type* boundTy = eqvClass.get_bound().type ) {50 return conversionCost( src, boundTy, indexer, env );48 if ( const EqvClass* eqvClass = env.lookup( destAsTypeInst->name ) ) { 49 if ( eqvClass->type ) { 50 return conversionCost( src, eqvClass->type, indexer, env ); 51 51 } else { 52 52 return Cost::infinity; … … 362 362 363 363 void ConversionCost::postvisit( TypeInstType *inst ) { 364 if ( ClassRefeqvClass = env.lookup( inst->name ) ) {365 cost = costFunc( eqvClass .get_bound().type, dest, indexer, env );364 if ( const EqvClass *eqvClass = env.lookup( inst->name ) ) { 365 cost = costFunc( eqvClass->type, dest, indexer, env ); 366 366 } else if ( TypeInstType *destAsInst = dynamic_cast< TypeInstType* >( dest ) ) { 367 367 if ( inst->name == destAsInst->name ) { -
src/ResolvExpr/Occurs.cc
r97397a26 rb60f9d9 14 14 // 15 15 16 #include <set> // for set, _Rb_tree_const_iterator 16 17 #include <string> // for string 17 #include <unordered_set> // for unordered_set18 18 19 19 #include "Common/PassVisitor.h" 20 20 #include "SynTree/Type.h" // for TypeInstType, Type 21 #include "TypeEnvironment.h" // for ClassRef, TypeEnvironment21 #include "TypeEnvironment.h" // for EqvClass, TypeEnvironment 22 22 23 23 namespace ResolvExpr { … … 27 27 28 28 bool result; 29 using VarSet = std::unordered_set< std::string >; 30 VarSet eqvVars; 29 std::set< std::string > eqvVars; 31 30 const TypeEnvironment &tenv; 32 31 }; … … 39 38 40 39 Occurs::Occurs( std::string varName, const TypeEnvironment & env ) : result( false ), tenv( env ) { 41 if ( ClassRefeqvClass = tenv.lookup( varName ) ) {42 eqvVars = eqvClass .get_vars<VarSet>();40 if ( const EqvClass *eqvClass = tenv.lookup( varName ) ) { 41 eqvVars = eqvClass->vars; 43 42 } else { 44 43 eqvVars.insert( varName ); … … 52 51 if ( eqvVars.find( typeInst->get_name() ) != eqvVars.end() ) { 53 52 result = true; 54 } else if ( ClassRefeqvClass = tenv.lookup( typeInst->get_name() ) ) {55 if ( Type* boundTy = eqvClass.get_bound().type ) {53 } else if ( const EqvClass *eqvClass = tenv.lookup( typeInst->get_name() ) ) { 54 if ( eqvClass->type ) { 56 55 /// std::cerr << typeInst->get_name() << " is bound to"; 57 /// boundTy->print( std::cerr );56 /// eqvClass.type->print( std::cerr ); 58 57 /// std::cerr << std::endl; 59 boundTy->accept( *visitor );58 eqvClass->type->accept( *visitor ); 60 59 } // if 61 60 } // if -
src/ResolvExpr/PolyCost.cc
r97397a26 rb60f9d9 17 17 #include "SymTab/Indexer.h" // for Indexer 18 18 #include "SynTree/Type.h" // for TypeInstType, Type 19 #include "TypeEnvironment.h" // for ClassRef, TypeEnvironment19 #include "TypeEnvironment.h" // for EqvClass, TypeEnvironment 20 20 21 21 namespace ResolvExpr { … … 39 39 40 40 void PolyCost::previsit(TypeInstType * typeInst) { 41 if ( ClassRefeqvClass = tenv.lookup( typeInst->name ) ) {42 if ( Type* boundTy = eqvClass.get_bound().type ) {43 if ( TypeInstType * otherTypeInst = dynamic_cast< TypeInstType* >( boundTy) ) {41 if ( const EqvClass *eqvClass = tenv.lookup( typeInst->name ) ) { 42 if ( eqvClass->type ) { 43 if ( TypeInstType * otherTypeInst = dynamic_cast< TypeInstType* >( eqvClass->type ) ) { 44 44 if ( indexer.lookupType( otherTypeInst->name ) ) { 45 45 // bound to opaque type -
src/ResolvExpr/PtrsAssignable.cc
r97397a26 rb60f9d9 15 15 16 16 #include "Common/PassVisitor.h" 17 #include "ResolvExpr/TypeEnvironment.h" // for ClassRef, TypeEnvironment17 #include "ResolvExpr/TypeEnvironment.h" // for EqvClass, TypeEnvironment 18 18 #include "SynTree/Type.h" // for TypeInstType, Type, BasicType 19 19 #include "SynTree/Visitor.h" // for Visitor … … 51 51 // std::cerr << "assignable: " << src << " | " << dest << std::endl; 52 52 if ( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) { 53 if ( ClassRefeqvClass = env.lookup( destAsTypeInst->get_name() ) ) {54 return ptrsAssignable( src, eqvClass .get_bound().type, env );53 if ( const EqvClass *eqvClass = env.lookup( destAsTypeInst->get_name() ) ) { 54 return ptrsAssignable( src, eqvClass->type, env ); 55 55 } // if 56 56 } // if … … 94 94 void PtrsAssignable::postvisit( __attribute__((unused)) TraitInstType *inst ) {} 95 95 void PtrsAssignable::postvisit( TypeInstType *inst ) { 96 if ( ClassRefeqvClass = env.lookup( inst->get_name() ) ) {97 if ( Type* boundTy = eqvClass.get_bound().type ) {96 if ( const EqvClass *eqvClass = env.lookup( inst->get_name() ) ) { 97 if ( eqvClass->type ) { 98 98 // T * = S * for any S depends on the type bound to T 99 result = ptrsAssignable( boundTy, dest, env );99 result = ptrsAssignable( eqvClass->type, dest, env ); 100 100 } 101 101 } // if -
src/ResolvExpr/PtrsCastable.cc
r97397a26 rb60f9d9 15 15 16 16 #include "Common/PassVisitor.h" 17 #include "ResolvExpr/TypeEnvironment.h" // for ClassRef, TypeEnvironment17 #include "ResolvExpr/TypeEnvironment.h" // for EqvClass, TypeEnvironment 18 18 #include "SymTab/Indexer.h" // for Indexer 19 19 #include "SynTree/Declaration.h" // for TypeDecl, TypeDecl::Kind::Ftype … … 63 63 } // if 64 64 } //if 65 } else if ( ClassRefeqvClass = env.lookup( typeInst->get_name() ) ) {66 if ( eqvClass .get_bound().data.kind == TypeDecl::Ftype ) {65 } else if ( const EqvClass *eqvClass = env.lookup( typeInst->get_name() ) ) { 66 if ( eqvClass->data.kind == TypeDecl::Ftype ) { 67 67 return -1; 68 68 } // if … … 78 78 int ptrsCastable( Type *src, Type *dest, const TypeEnvironment &env, const SymTab::Indexer &indexer ) { 79 79 if ( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) { 80 if ( ClassRefeqvClass = env.lookup( destAsTypeInst->get_name() ) ) {80 if ( const EqvClass *eqvClass = env.lookup( destAsTypeInst->get_name() ) ) { 81 81 // xxx - should this be ptrsCastable? 82 return ptrsAssignable( src, eqvClass .get_bound().type, env );82 return ptrsAssignable( src, eqvClass->type, env ); 83 83 } // if 84 84 } // if -
src/ResolvExpr/TypeEnvironment.cc
r97397a26 rb60f9d9 19 19 #include <utility> // for pair, move 20 20 21 #include "Common/InternedString.h" // for interned_string22 21 #include "Common/PassVisitor.h" // for PassVisitor<GcTracer> 23 22 #include "Common/utility.h" // for maybeClone 24 #include "SymTab/Indexer.h" // for Indexer25 23 #include "SynTree/GcTracer.h" // for PassVisitor<GcTracer> 26 24 #include "SynTree/Type.h" // for Type, FunctionType, Type::Fora... 27 25 #include "SynTree/TypeSubstitution.h" // for TypeSubstitution 28 26 #include "TypeEnvironment.h" 29 #include "Unify.h" // for unifyInexact30 27 31 28 namespace ResolvExpr { … … 48 45 } 49 46 50 #if 051 47 void EqvClass::initialize( const EqvClass &src, EqvClass &dest ) { 52 48 dest.vars = src.vars; … … 56 52 } 57 53 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 ) {} 54 EqvClass::EqvClass() : type( 0 ), allowWidening( true ) { 55 } 63 56 64 57 EqvClass::EqvClass( const EqvClass &other ) { … … 98 91 return nullptr; 99 92 } 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 93 277 94 /// Removes any class from env that intersects eqvClass 278 95 void filterOverlappingClasses( std::list<EqvClass> &env, const EqvClass &eqvClass ) { … … 363 180 } 364 181 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 365 210 void TypeEnvironment::extractOpenVars( OpenVarSet &openVars ) const { 366 211 for ( std::list< EqvClass >::const_iterator eqvClass = env.begin(); eqvClass != env.end(); ++eqvClass ) { … … 386 231 return out; 387 232 } 388 #endif389 233 390 234 PassVisitor<GcTracer> & operator<<( PassVisitor<GcTracer> & gc, const TypeEnvironment & env ) { 391 for ( ClassRefc : env ) {392 maybeAccept( c. get_bound().type, gc );235 for ( const EqvClass & c : env ) { 236 maybeAccept( c.type, gc ); 393 237 } 394 238 return gc; -
src/ResolvExpr/TypeEnvironment.h
r97397a26 rb60f9d9 7 7 // TypeEnvironment.h -- 8 8 // 9 // Author : Aaron B. Moss9 // Author : Richard C. Bilson 10 10 // Created On : Sun May 17 12:24:58 2015 11 // Last Modified By : Aaron B. Moss12 // Last Modified On : Wed Jun 13 16:31:00 201813 // Update Count : 411 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Sat Jul 22 09:35:45 2017 13 // Update Count : 3 14 14 // 15 15 16 16 #pragma once 17 17 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 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 26 23 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 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 34 28 35 template< typename Pass > class PassVisitor; 29 template< typename Pass > 30 class PassVisitor; 36 31 class GcTracer; 37 namespace SymTab { class Indexer; }38 32 39 33 namespace ResolvExpr { … … 46 40 // declarations. 47 41 // 48 // I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this 49 // comparator. 42 // I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this comparator. 50 43 // 51 44 // Note: since this compares pointers for position, minor changes in the source file that affect 52 45 // memory layout can alter compilation time in unpredictable ways. For example, the placement 53 46 // of a line directive can reorder type pointers with respect to each other so that assertions 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. 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. 60 52 struct AssertCompare { 61 53 bool operator()( DeclarationWithType * d1, DeclarationWithType * d2 ) const { … … 67 59 struct AssertionSetValue { 68 60 bool isUsed; 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. 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. 73 64 std::list< UniqueId > idChain; 74 65 }; … … 79 70 void printOpenVarSet( const OpenVarSet &, std::ostream &, int indent = 0 ); 80 71 81 /// A data structure for holding all the necessary information for a type binding82 struct BoundType {83 Type* type;84 bool allowWidening;85 TypeDecl::Data data;86 };87 88 #if 089 /// An equivalence class, with its binding information90 72 struct EqvClass { 91 73 std::set< std::string > vars; … … 96 78 void initialize( const EqvClass &src, EqvClass &dest ); 97 79 EqvClass(); 98 EqvClass( std::vector<interned_string>&& vars, BoundType&& bound );99 80 EqvClass( const EqvClass &other ); 100 81 EqvClass &operator=( const EqvClass &other ); 101 82 void print( std::ostream &os, Indenter indent = {} ) const; 102 83 }; 103 #endif104 105 class TypeEnvironment;106 107 /// A reference to an equivalence class that may be used to constitute one from its environment108 class ClassRef {109 friend TypeEnvironment;110 111 const TypeEnvironment* env; ///< Containing environment112 interned_string root; ///< Name of root type113 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 root123 inline interned_string update_root();124 125 /// Gets the type variables of the referenced equivalence class, empty list for none126 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 none130 inline BoundType get_bound() const;131 132 #if 0133 /// Gets the referenced equivalence class134 inline EqvClass get_class() const;135 EqvClass operator* () const { return get_class(); }136 #endif137 138 // Check that there is a referenced typeclass139 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 };144 84 145 85 class TypeEnvironment { 146 friend ClassRef;147 148 /// Backing storage for equivalence classes149 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 name154 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 these157 /// may be null.158 Bindings* bindings;159 160 /// Merges the classes rooted at root1 and root2, returning a pair containing the root and161 /// 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 165 86 public: 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 87 const EqvClass* lookup( const std::string &var ) const; 208 88 void add( const EqvClass &eqvClass ); 209 89 void add( EqvClass &&eqvClass ); … … 213 93 template< typename SynTreeClass > int applyFree( SynTreeClass *&type ) const; 214 94 void makeSubstitution( TypeSubstitution &result ) const; 215 #endif 216 bool isEmpty() const { return classes->empty(); } 217 #if !1 95 bool isEmpty() const { return env.empty(); } 218 96 void print( std::ostream &os, Indenter indent = {} ) const; 97 void combine( const TypeEnvironment &second, Type *(*combineFunc)( Type*, Type* ) ); 219 98 void simpleCombine( const TypeEnvironment &second ); 220 99 void extractOpenVars( OpenVarSet &openVars ) const; 221 #endif222 100 TypeEnvironment *clone() const { return new TypeEnvironment( *this ); } 223 101 224 #if !1225 102 /// Iteratively adds the environment of a new actual (with allowWidening = false), 226 103 /// and extracts open variables. 227 104 void addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars ); 228 #endif229 105 230 iterator begin() { return { this, bindings->begin() }; }231 iterator end() { return { this, bindings->end() }; }232 #if 0 106 typedef std::list< EqvClass >::iterator iterator; 107 iterator begin() { return env.begin(); } 108 iterator end() { return env.end(); } 233 109 typedef std::list< EqvClass >::const_iterator const_iterator; 234 110 const_iterator begin() const { return env.begin(); } 235 111 const_iterator end() const { return env.end(); } 236 #endif 112 private: 113 std::list< EqvClass > env; 114 std::list< EqvClass >::iterator internal_lookup( const std::string &var ); 237 115 }; 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 0253 EqvClass ClassRef::get_class() const { return { get_vars(), get_bound() }; }254 #endif255 116 256 117 template< typename SynTreeClass > … … 268 129 } 269 130 270 #if !1271 131 std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env ); 272 #endif273 132 274 133 PassVisitor<GcTracer> & operator<<( PassVisitor<GcTracer> & gc, const TypeEnvironment & env ); -
src/ResolvExpr/Unify.cc
r97397a26 rb60f9d9 31 31 #include "SynTree/Visitor.h" // for Visitor 32 32 #include "Tuples/Tuples.h" // for isTtype 33 #include "TypeEnvironment.h" // for ClassRef, AssertionSet, OpenVarSet33 #include "TypeEnvironment.h" // for EqvClass, AssertionSet, OpenVarSet 34 34 #include "Unify.h" 35 35 #include "typeops.h" // for flatten, occurs, commonType … … 128 128 return typeInst->get_isFtype(); 129 129 } // 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 130 147 return false; 131 148 } … … 508 525 void premutate( TypeInstType * ) { visit_children = false; } 509 526 Type * postmutate( TypeInstType * typeInst ) { 510 if ( ClassRefeqvClass = tenv.lookup( typeInst->get_name() ) ) {527 if ( const EqvClass *eqvClass = tenv.lookup( typeInst->get_name() ) ) { 511 528 // expand ttype parameter into its actual type 512 BoundType cBound = eqvClass.get_bound(); 513 if ( cBound.data.kind == TypeDecl::Ttype && cBound.type ) { 514 return cBound.type->clone(); 529 if ( eqvClass->data.kind == TypeDecl::Ttype && eqvClass->type ) { 530 return eqvClass->type->clone(); 515 531 } 516 532 }
Note:
See TracChangeset
for help on using the changeset viewer.
