Changeset 28f3a19 for src/ResolvExpr/TypeEnvironment.cc
- Timestamp:
- Jun 27, 2018, 3:28:41 PM (6 years ago)
- Branches:
- new-env, with_gc
- Children:
- b21c77a
- Parents:
- 0182bfa (diff), 63238a4 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)
links above to see all the changes relative to each parent. - File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/TypeEnvironment.cc
r0182bfa r28f3a19 9 9 // Author : Richard C. Bilson 10 10 // Created On : Sun May 17 12:19:47 2015 11 // Last Modified By : Peter A. Buhr12 // Last Modified On : Sun May 17 12:23:36 201513 // Update Count : 311 // Last Modified By : Aaron B. Moss 12 // Last Modified On : Mon Jun 18 11:58:00 2018 13 // Update Count : 4 14 14 // 15 15 … … 24 24 #include "SynTree/Type.h" // for Type, FunctionType, Type::Fora... 25 25 #include "SynTree/TypeSubstitution.h" // for TypeSubstitution 26 #include "Tuples/Tuples.h" // for isTtype 26 27 #include "TypeEnvironment.h" 28 #include "typeops.h" // for occurs 29 #include "Unify.h" // for unifyInexact 27 30 28 31 namespace ResolvExpr { … … 46 49 47 50 void EqvClass::initialize( const EqvClass &src, EqvClass &dest ) { 51 initialize( src, dest, src.type ); 52 } 53 54 void EqvClass::initialize( const EqvClass &src, EqvClass &dest, const Type *ty ) { 48 55 dest.vars = src.vars; 49 dest.type = maybeClone( src.type);56 dest.type = maybeClone( ty ); 50 57 dest.allowWidening = src.allowWidening; 51 58 dest.data = src.data; 52 59 } 53 60 54 EqvClass::EqvClass() : type( 0), allowWidening( true ) {61 EqvClass::EqvClass() : type( nullptr ), allowWidening( true ) { 55 62 } 56 63 57 64 EqvClass::EqvClass( const EqvClass &other ) { 58 65 initialize( other, *this ); 66 } 67 68 EqvClass::EqvClass( const EqvClass &other, const Type *ty ) { 69 initialize( other, *this, ty ); 70 } 71 72 EqvClass::EqvClass( EqvClass &&other ) 73 : vars{std::move(other.vars)}, type{other.type}, 74 allowWidening{std::move(other.allowWidening)}, data{std::move(other.data)} { 75 other.type = nullptr; 59 76 } 60 77 … … 64 81 return *this; 65 82 } 83 84 EqvClass &EqvClass::operator=( EqvClass &&other ) { 85 if ( this == &other ) return *this; 86 87 vars = std::move(other.vars); 88 type = other.type; 89 allowWidening = std::move(other.allowWidening); 90 data = std::move(other.data); 91 92 return *this; 93 } 94 95 void EqvClass::set_type( Type* ty ) { type = ty; } 66 96 67 97 void EqvClass::print( std::ostream &os, Indenter indent ) const { … … 81 111 const EqvClass* TypeEnvironment::lookup( const std::string &var ) const { 82 112 for ( std::list< EqvClass >::const_iterator i = env.begin(); i != env.end(); ++i ) { 83 if ( i->vars.find( var ) != i->vars.end() ) { 84 /// std::cout << var << " is in class "; 85 /// i->print( std::cout ); 86 return &*i; 87 } 88 /// std::cout << var << " is not in class "; 89 /// i->print( std::cout ); 113 if ( i->vars.find( var ) != i->vars.end() ) return &*i; 90 114 } // for 91 115 return nullptr; … … 105 129 } 106 130 107 void TypeEnvironment::add( const EqvClass &eqvClass ) {108 filterOverlappingClasses( env, eqvClass );109 env.push_back( eqvClass );110 }111 112 131 void TypeEnvironment::add( EqvClass &&eqvClass ) { 113 132 filterOverlappingClasses( env, eqvClass ); … … 120 139 newClass.vars.insert( (*i)->get_name() ); 121 140 newClass.data = TypeDecl::Data{ (*i) }; 122 env.push_back( newClass);141 env.push_back( std::move(newClass) ); 123 142 } // for 124 143 } … … 134 153 // transition to TypeSubstitution 135 154 newClass.data = TypeDecl::Data{ TypeDecl::Dtype, false }; 136 add( newClass);155 add( std::move(newClass) ); 137 156 } 138 157 } … … 141 160 for ( std::list< EqvClass >::const_iterator theClass = env.begin(); theClass != env.end(); ++theClass ) { 142 161 for ( std::set< std::string >::const_iterator theVar = theClass->vars.begin(); theVar != theClass->vars.end(); ++theVar ) { 143 /// std::cerr << "adding " << *theVar;144 162 if ( theClass->type ) { 145 /// std::cerr << " bound to ";146 /// theClass->type->print( std::cerr );147 /// std::cerr << std::endl;148 163 sub.add( *theVar, theClass->type ); 149 164 } else if ( theVar != theClass->vars.begin() ) { 150 165 TypeInstType *newTypeInst = new TypeInstType( Type::Qualifiers(), *theClass->vars.begin(), theClass->data.kind == TypeDecl::Ftype ); 151 /// std::cerr << " bound to variable " << *theClass->vars.begin() << std::endl;152 166 sub.add( *theVar, newTypeInst ); 153 167 } // if 154 168 } // for 155 169 } // for 156 /// std::cerr << "input env is:" << std::endl;157 /// print( std::cerr, 8 );158 /// std::cerr << "sub is:" << std::endl;159 /// sub.print( std::cerr, 8 );160 170 sub.normalize(); 161 171 } 162 172 163 173 void TypeEnvironment::print( std::ostream &os, Indenter indent ) const { 164 for ( std::list< EqvClass >::const_iterator i = env.begin(); i != env.end(); ++i) {165 i->print( os, indent );174 for ( const EqvClass & theClass : env ) { 175 theClass.print( os, indent ); 166 176 } // for 167 177 } … … 169 179 std::list< EqvClass >::iterator TypeEnvironment::internal_lookup( const std::string &var ) { 170 180 for ( std::list< EqvClass >::iterator i = env.begin(); i != env.end(); ++i ) { 171 if ( i->vars.find( var ) == i->vars.end() ) { 172 return i; 173 } // if 181 if ( i->vars.count( var ) ) return i; 174 182 } // for 175 183 return env.end(); … … 178 186 void TypeEnvironment::simpleCombine( const TypeEnvironment &second ) { 179 187 env.insert( env.end(), second.env.begin(), second.env.end() ); 180 }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 } // 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 188 } 209 189 … … 227 207 } 228 208 209 bool isFtype( Type *type ) { 210 if ( dynamic_cast< FunctionType* >( type ) ) { 211 return true; 212 } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( type ) ) { 213 return typeInst->get_isFtype(); 214 } // if 215 return false; 216 } 217 218 bool tyVarCompatible( const TypeDecl::Data & data, Type *type ) { 219 switch ( data.kind ) { 220 case TypeDecl::Dtype: 221 // to bind to an object type variable, the type must not be a function type. 222 // if the type variable is specified to be a complete type then the incoming 223 // type must also be complete 224 // xxx - should this also check that type is not a tuple type and that it's not a ttype? 225 return ! isFtype( type ) && (! data.isComplete || type->isComplete() ); 226 case TypeDecl::Ftype: 227 return isFtype( type ); 228 case TypeDecl::Ttype: 229 // ttype unifies with any tuple type 230 return dynamic_cast< TupleType * >( type ) || Tuples::isTtype( type ); 231 } // switch 232 return false; 233 } 234 235 bool TypeEnvironment::bindVar( TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) { 236 237 // remove references from other, so that type variables can only bind to value types 238 bindTo = bindTo->stripReferences(); 239 OpenVarSet::const_iterator tyvar = openVars.find( typeInst->get_name() ); 240 assert( tyvar != openVars.end() ); 241 if ( ! tyVarCompatible( tyvar->second, bindTo ) ) { 242 return false; 243 } // if 244 if ( occurs( bindTo, typeInst->get_name(), *this ) ) { 245 return false; 246 } // if 247 auto curClass = internal_lookup( typeInst->get_name() ); 248 if ( curClass != env.end() ) { 249 if ( curClass->type ) { 250 Type *common = 0; 251 // attempt to unify equivalence class type (which has qualifiers stripped, so they must be restored) with the type to bind to 252 Type *newType = curClass->type->clone(); 253 newType->get_qualifiers() = typeInst->get_qualifiers(); 254 if ( unifyInexact( newType, bindTo, *this, need, have, openVars, widenMode & WidenMode( curClass->allowWidening, true ), indexer, common ) ) { 255 if ( common ) { 256 common->get_qualifiers() = Type::Qualifiers{}; 257 curClass->set_type( common ); 258 } // if 259 } else return false; 260 } else { 261 Type* newType = bindTo->clone(); 262 newType->get_qualifiers() = Type::Qualifiers{}; 263 curClass->set_type( newType ); 264 curClass->allowWidening = widenMode.widenFirst && widenMode.widenSecond; 265 } // if 266 } else { 267 EqvClass newClass; 268 newClass.vars.insert( typeInst->get_name() ); 269 newClass.type = bindTo->clone(); 270 newClass.type->get_qualifiers() = Type::Qualifiers(); 271 newClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond; 272 newClass.data = data; 273 env.push_back( std::move(newClass) ); 274 } // if 275 return true; 276 } 277 278 bool TypeEnvironment::bindVarToVar( TypeInstType *var1, TypeInstType *var2, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) { 279 280 auto class1 = internal_lookup( var1->get_name() ); 281 auto class2 = internal_lookup( var2->get_name() ); 282 283 // exit early if variables already bound together 284 if ( class1 != env.end() && class1 == class2 ) { 285 class1->allowWidening &= widenMode; 286 return true; 287 } 288 289 bool widen1 = false, widen2 = false; 290 const Type *type1 = nullptr, *type2 = nullptr; 291 292 // check for existing bindings, perform occurs check 293 if ( class1 != env.end() ) { 294 if ( class1->type ) { 295 if ( occurs( class1->type, var2->get_name(), *this ) ) return false; 296 type1 = class1->type; 297 } // if 298 widen1 = widenMode.widenFirst && class1->allowWidening; 299 } // if 300 if ( class2 != env.end() ) { 301 if ( class2->type ) { 302 if ( occurs( class2->type, var1->get_name(), *this ) ) return false; 303 type2 = class2->type; 304 } // if 305 widen2 = widenMode.widenSecond && class2->allowWidening; 306 } // if 307 308 if ( type1 && type2 ) { 309 // both classes bound, merge if bound types can be unified 310 Type *newType1 = type1->clone(), *newType2 = type2->clone(); 311 WidenMode newWidenMode{ widen1, widen2 }; 312 Type *common = 0; 313 if ( unifyInexact( newType1, newType2, *this, need, have, openVars, newWidenMode, indexer, common ) ) { 314 class1->vars.insert( class2->vars.begin(), class2->vars.end() ); 315 class1->allowWidening = widen1 && widen2; 316 if ( common ) { 317 common->get_qualifiers() = Type::Qualifiers{}; 318 class1->set_type( common ); 319 } 320 env.erase( class2 ); 321 } else return false; 322 } else if ( class1 != env.end() && class2 != env.end() ) { 323 // both classes exist, at least one unbound, merge unconditionally 324 if ( type1 ) { 325 class1->vars.insert( class2->vars.begin(), class2->vars.end() ); 326 class1->allowWidening = widen1; 327 env.erase( class2 ); 328 } else { 329 class2->vars.insert( class1->vars.begin(), class1->vars.end() ); 330 class2->allowWidening = widen2; 331 env.erase( class1 ); 332 } // if 333 } else if ( class1 != env.end() ) { 334 // var2 unbound, add to class1 335 class1->vars.insert( var2->get_name() ); 336 class1->allowWidening = widen1; 337 } else if ( class2 != env.end() ) { 338 // var1 unbound, add to class2 339 class2->vars.insert( var1->get_name() ); 340 class2->allowWidening = widen2; 341 } else { 342 // neither var bound, create new class 343 EqvClass newClass; 344 newClass.vars.insert( var1->get_name() ); 345 newClass.vars.insert( var2->get_name() ); 346 newClass.allowWidening = widen1 && widen2; 347 newClass.data = data; 348 env.push_back( std::move(newClass) ); 349 } // if 350 return true; 351 } 352 353 void TypeEnvironment::forbidWidening() { 354 for ( EqvClass& c : env ) c.allowWidening = false; 355 } 356 229 357 std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env ) { 230 358 env.print( out );
Note: See TracChangeset
for help on using the changeset viewer.