- Timestamp:
- Jun 15, 2018, 5:09:29 PM (6 years ago)
- Branches:
- new-env
- Children:
- 97397a26
- Parents:
- 1d7b0a8
- Location:
- src
- Files:
-
- 4 added
- 13 edited
Legend:
- Unmodified
- Added
- Removed
-
src/Common/module.mk
r1d7b0a8 r982f95d 10 10 ## Author : Richard C. Bilson 11 11 ## Created On : Mon Jun 1 17:49:17 2015 12 ## Last Modified By : Peter A. Buhr13 ## Last Modified On : T ue Sep 27 11:06:38 201614 ## Update Count : 412 ## Last Modified By : Aaron B. Moss 13 ## Last Modified On : Thu Jun 14 11:15:00 2018 14 ## Update Count : 5 15 15 ############################################################################### 16 16 … … 20 20 Common/GC.cc \ 21 21 Common/Assert.cc \ 22 Common/InternedString.cc \ 22 23 Common/Heap.cc -
src/GenPoly/Box.cc
r1d7b0a8 r982f95d 38 38 #include "Lvalue.h" // for generalizedLvalue 39 39 #include "Parser/LinkageSpec.h" // for C, Spec, Cforall, Intrinsic 40 #include "ResolvExpr/TypeEnvironment.h" // for EqvClass41 40 #include "ResolvExpr/typeops.h" // for typesCompatible 42 41 #include "ScopedSet.h" // for ScopedSet, ScopedSet<>::iter... … … 592 591 // pass size/align for type variables 593 592 for ( TyVarMap::const_iterator tyParm = exprTyVars.begin(); tyParm != exprTyVars.end(); ++tyParm ) { 594 ResolvExpr::EqvClass eqvClass;595 593 assert( env ); 596 594 if ( tyParm->second.isComplete ) { -
src/ResolvExpr/AdjustExprType.cc
r1d7b0a8 r982f95d 19 19 #include "SynTree/Mutator.h" // for Mutator 20 20 #include "SynTree/Type.h" // for PointerType, TypeInstType, Type 21 #include "TypeEnvironment.h" // for EqvClass, TypeEnvironment21 #include "TypeEnvironment.h" // for ClassRef, TypeEnvironment 22 22 23 23 namespace ResolvExpr { … … 74 74 75 75 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 ) { 78 78 return new PointerType{ Type::Qualifiers(), typeInst }; 79 79 } -
src/ResolvExpr/AlternativeFinder.cc
r1d7b0a8 r982f95d 1109 1109 } 1110 1110 } 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 ) ) { 1113 1113 Alternative newFunc( *func ); 1114 1114 referenceToRvalueConversion( newFunc.expr, newFunc.cost ); -
src/ResolvExpr/CastCost.cc
r1d7b0a8 r982f95d 18 18 #include "ConversionCost.h" // for ConversionCost 19 19 #include "Cost.h" // for Cost, Cost::infinity 20 #include "ResolvExpr/TypeEnvironment.h" // for TypeEnvironment, EqvClass20 #include "ResolvExpr/TypeEnvironment.h" // for TypeEnvironment, ClassRef 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 ( 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 ); 48 48 } else { 49 49 return Cost::infinity; -
src/ResolvExpr/ConversionCost.cc
r1d7b0a8 r982f95d 22 22 #include "Common/GC.h" // for new_static_root 23 23 #include "ResolvExpr/Cost.h" // for Cost 24 #include "ResolvExpr/TypeEnvironment.h" // for EqvClass, TypeEnvironment24 #include "ResolvExpr/TypeEnvironment.h" // for ClassRef, TypeEnvironment 25 25 #include "SymTab/Indexer.h" // for Indexer 26 26 #include "SynTree/Declaration.h" // for TypeDecl, NamedTypeDecl … … 44 44 if ( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) { 45 45 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 ); 49 49 } else { 50 50 return Cost::infinity; … … 360 360 361 361 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 ); 364 364 } else if ( TypeInstType *destAsInst = dynamic_cast< TypeInstType* >( dest ) ) { 365 365 if ( inst->name == destAsInst->name ) { -
src/ResolvExpr/Occurs.cc
r1d7b0a8 r982f95d 14 14 // 15 15 16 #include <set> // for set, _Rb_tree_const_iterator17 16 #include <string> // for string 17 #include <unordered_set> // for unordered_set 18 18 19 19 #include "Common/PassVisitor.h" 20 20 #include "SynTree/Type.h" // for TypeInstType, Type 21 #include "TypeEnvironment.h" // for EqvClass, TypeEnvironment21 #include "TypeEnvironment.h" // for ClassRef, TypeEnvironment 22 22 23 23 namespace ResolvExpr { … … 27 27 28 28 bool result; 29 std::set< std::string > eqvVars; 29 using VarSet = std::unordered_set< std::string >; 30 VarSet eqvVars; 30 31 const TypeEnvironment &tenv; 31 32 }; … … 38 39 39 40 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>(); 42 43 } else { 43 44 eqvVars.insert( varName ); … … 51 52 if ( eqvVars.find( typeInst->get_name() ) != eqvVars.end() ) { 52 53 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 ) { 55 56 /// std::cerr << typeInst->get_name() << " is bound to"; 56 /// eqvClass.type->print( std::cerr );57 /// boundTy->print( std::cerr ); 57 58 /// std::cerr << std::endl; 58 eqvClass->type->accept( *visitor );59 boundTy->accept( *visitor ); 59 60 } // if 60 61 } // if -
src/ResolvExpr/PolyCost.cc
r1d7b0a8 r982f95d 17 17 #include "SymTab/Indexer.h" // for Indexer 18 18 #include "SynTree/Type.h" // for TypeInstType, Type 19 #include "TypeEnvironment.h" // for EqvClass, TypeEnvironment19 #include "TypeEnvironment.h" // for ClassRef, TypeEnvironment 20 20 21 21 namespace ResolvExpr { … … 39 39 40 40 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 ) ) { 44 44 if ( indexer.lookupType( otherTypeInst->name ) ) { 45 45 // bound to opaque type -
src/ResolvExpr/PtrsAssignable.cc
r1d7b0a8 r982f95d 15 15 16 16 #include "Common/PassVisitor.h" 17 #include "ResolvExpr/TypeEnvironment.h" // for EqvClass, TypeEnvironment17 #include "ResolvExpr/TypeEnvironment.h" // for ClassRef, 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 ( 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 ); 55 55 } // if 56 56 } // if … … 94 94 void PtrsAssignable::postvisit( __attribute__((unused)) TraitInstType *inst ) {} 95 95 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 ) { 98 98 // 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 ); 100 100 } 101 101 } // if -
src/ResolvExpr/PtrsCastable.cc
r1d7b0a8 r982f95d 15 15 16 16 #include "Common/PassVisitor.h" 17 #include "ResolvExpr/TypeEnvironment.h" // for EqvClass, TypeEnvironment17 #include "ResolvExpr/TypeEnvironment.h" // for ClassRef, 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 ( 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 ) { 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 ( const EqvClass *eqvClass = env.lookup( destAsTypeInst->get_name() ) ) {80 if ( ClassRef eqvClass = env.lookup( destAsTypeInst->get_name() ) ) { 81 81 // xxx - should this be ptrsCastable? 82 return ptrsAssignable( src, eqvClass ->type, env );82 return ptrsAssignable( src, eqvClass.get_bound().type, env ); 83 83 } // if 84 84 } // if -
src/ResolvExpr/TypeEnvironment.cc
r1d7b0a8 r982f95d 19 19 #include <utility> // for pair, move 20 20 21 #include "Common/InternedString.h" // for interned_string 21 22 #include "Common/PassVisitor.h" // for PassVisitor<GcTracer> 22 23 #include "Common/utility.h" // for maybeClone 24 #include "SymTab/Indexer.h" // for Indexer 23 25 #include "SynTree/GcTracer.h" // for PassVisitor<GcTracer> 24 26 #include "SynTree/Type.h" // for Type, FunctionType, Type::Fora... 25 27 #include "SynTree/TypeSubstitution.h" // for TypeSubstitution 26 28 #include "TypeEnvironment.h" 29 #include "Unify.h" // for unifyInexact 27 30 28 31 namespace ResolvExpr { … … 45 48 } 46 49 50 #if 0 47 51 void EqvClass::initialize( const EqvClass &src, EqvClass &dest ) { 48 52 dest.vars = src.vars; … … 52 56 } 53 57 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 ) {} 56 63 57 64 EqvClass::EqvClass( const EqvClass &other ) { … … 91 98 return nullptr; 92 99 } 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 94 277 /// Removes any class from env that intersects eqvClass 95 278 void filterOverlappingClasses( std::list<EqvClass> &env, const EqvClass &eqvClass ) { … … 180 363 } 181 364 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 } // if199 } // if200 secondCopy.env.erase( secondClass );201 } // if202 } // for203 newClass.vars.insert( newVars.begin(), newVars.end() );204 } // for205 for ( std::list< EqvClass >::iterator secondClass = secondCopy.env.begin(); secondClass != secondCopy.env.end(); ++secondClass ) {206 env.push_back( *secondClass );207 } // for208 }209 210 365 void TypeEnvironment::extractOpenVars( OpenVarSet &openVars ) const { 211 366 for ( std::list< EqvClass >::const_iterator eqvClass = env.begin(); eqvClass != env.end(); ++eqvClass ) { … … 231 386 return out; 232 387 } 388 #endif 233 389 234 390 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 ); 237 393 } 238 394 return gc; -
src/ResolvExpr/TypeEnvironment.h
r1d7b0a8 r982f95d 7 7 // TypeEnvironment.h -- 8 8 // 9 // Author : Richard C. Bilson9 // Author : Aaron B. Moss 10 10 // Created On : Sun May 17 12:24:58 2015 11 // Last Modified By : Peter A. Buhr12 // Last Modified On : Sat Jul 22 09:35:45 201713 // Update Count : 311 // Last Modified By : Aaron B. Moss 12 // Last Modified On : Wed Jun 13 16:31:00 2018 13 // Update Count : 4 14 14 // 15 15 16 16 #pragma once 17 17 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 35 template< typename Pass > class PassVisitor; 31 36 class GcTracer; 37 namespace SymTab { class Indexer; } 32 38 33 39 namespace ResolvExpr { … … 40 46 // declarations. 41 47 // 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. 43 50 // 44 51 // Note: since this compares pointers for position, minor changes in the source file that affect 45 52 // memory layout can alter compilation time in unpredictable ways. For example, the placement 46 53 // 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. 52 60 struct AssertCompare { 53 61 bool operator()( DeclarationWithType * d1, DeclarationWithType * d2 ) const { … … 59 67 struct AssertionSetValue { 60 68 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. 64 73 std::list< UniqueId > idChain; 65 74 }; … … 70 79 void printOpenVarSet( const OpenVarSet &, std::ostream &, int indent = 0 ); 71 80 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 72 90 struct EqvClass { 73 91 std::set< std::string > vars; … … 78 96 void initialize( const EqvClass &src, EqvClass &dest ); 79 97 EqvClass(); 98 EqvClass( std::vector<interned_string>&& vars, BoundType&& bound ); 80 99 EqvClass( const EqvClass &other ); 81 100 EqvClass &operator=( const EqvClass &other ); 82 101 void print( std::ostream &os, Indenter indent = {} ) const; 83 102 }; 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 }; 84 144 85 145 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 86 165 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 88 208 void add( const EqvClass &eqvClass ); 89 209 void add( EqvClass &&eqvClass ); … … 93 213 template< typename SynTreeClass > int applyFree( SynTreeClass *&type ) const; 94 214 void makeSubstitution( TypeSubstitution &result ) const; 95 bool isEmpty() const { return env.empty(); } 215 #endif 216 bool isEmpty() const { return classes->empty(); } 217 #if !1 96 218 void print( std::ostream &os, Indenter indent = {} ) const; 97 void combine( const TypeEnvironment &second, Type *(*combineFunc)( Type*, Type* ) );98 219 void simpleCombine( const TypeEnvironment &second ); 99 220 void extractOpenVars( OpenVarSet &openVars ) const; 221 #endif 100 222 TypeEnvironment *clone() const { return new TypeEnvironment( *this ); } 101 223 224 #if !1 102 225 /// Iteratively adds the environment of a new actual (with allowWidening = false), 103 226 /// and extracts open variables. 104 227 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 109 233 typedef std::list< EqvClass >::const_iterator const_iterator; 110 234 const_iterator begin() const { return env.begin(); } 111 235 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 116 255 117 256 template< typename SynTreeClass > … … 129 268 } 130 269 270 #if !1 131 271 std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env ); 272 #endif 132 273 133 274 PassVisitor<GcTracer> & operator<<( PassVisitor<GcTracer> & gc, const TypeEnvironment & env ); -
src/ResolvExpr/Unify.cc
r1d7b0a8 r982f95d 31 31 #include "SynTree/Visitor.h" // for Visitor 32 32 #include "Tuples/Tuples.h" // for isTtype 33 #include "TypeEnvironment.h" // for EqvClass, AssertionSet, OpenVarSet33 #include "TypeEnvironment.h" // for ClassRef, 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 incoming138 // type must also be complete139 // 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 type145 return dynamic_cast< TupleType * >( type ) || Tuples::isTtype( type );146 } // switch147 130 return false; 148 131 } … … 525 508 void premutate( TypeInstType * ) { visit_children = false; } 526 509 Type * postmutate( TypeInstType * typeInst ) { 527 if ( const EqvClass *eqvClass = tenv.lookup( typeInst->get_name() ) ) {510 if ( ClassRef eqvClass = tenv.lookup( typeInst->get_name() ) ) { 528 511 // 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(); 531 515 } 532 516 }
Note: See TracChangeset
for help on using the changeset viewer.