[a32b204] | 1 | // |
---|
| 2 | // Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo |
---|
| 3 | // |
---|
| 4 | // The contents of this file are covered under the licence agreement in the |
---|
| 5 | // file "LICENCE" distributed with Cforall. |
---|
| 6 | // |
---|
[03da511] | 7 | // TypeEnvironment.cc -- |
---|
[a32b204] | 8 | // |
---|
[b21c77a] | 9 | // Author : Aaron B. Moss |
---|
[a32b204] | 10 | // Created On : Sun May 17 12:19:47 2015 |
---|
[d286cf68] | 11 | // Last Modified By : Aaron B. Moss |
---|
[b21c77a] | 12 | // Last Modified On : Fri Jun 29 15:51:00 2018 |
---|
| 13 | // Update Count : 5 |
---|
[a32b204] | 14 | // |
---|
[51b7345] | 15 | |
---|
[ea6332d] | 16 | #include <cassert> // for assert |
---|
| 17 | #include <algorithm> // for copy, set_intersection |
---|
| 18 | #include <iterator> // for ostream_iterator, insert_iterator |
---|
[f89a111] | 19 | #include <list> // for list |
---|
| 20 | #include <vector> // for vector |
---|
| 21 | #include <unordered_map> // for unordered_map |
---|
[8e18b8e] | 22 | #include <utility> // for pair, move |
---|
[51b7345] | 23 | |
---|
[982f95d] | 24 | #include "Common/InternedString.h" // for interned_string |
---|
[f229fc2] | 25 | #include "Common/PassVisitor.h" // for PassVisitor<GcTracer> |
---|
[184557e] | 26 | #include "Common/option.h" // for option<T> |
---|
[ea6332d] | 27 | #include "Common/utility.h" // for maybeClone |
---|
[982f95d] | 28 | #include "SymTab/Indexer.h" // for Indexer |
---|
[f229fc2] | 29 | #include "SynTree/GcTracer.h" // for PassVisitor<GcTracer> |
---|
[ea6332d] | 30 | #include "SynTree/Type.h" // for Type, FunctionType, Type::Fora... |
---|
| 31 | #include "SynTree/TypeSubstitution.h" // for TypeSubstitution |
---|
[5c14030] | 32 | #include "Tuples/Tuples.h" // for isTtype |
---|
[51b7345] | 33 | #include "TypeEnvironment.h" |
---|
[d286cf68] | 34 | #include "typeops.h" // for occurs |
---|
[982f95d] | 35 | #include "Unify.h" // for unifyInexact |
---|
[51b7345] | 36 | |
---|
| 37 | namespace ResolvExpr { |
---|
[eff03a94] | 38 | #if 0 |
---|
[d318a18] | 39 | #define PRE_POST_VALIDATE auto dbg = ValidateGuard{this, __func__}; |
---|
| 40 | #define PRE_POST_VALIDATE_NOM auto dbg = ValidateGuard{this}; |
---|
| 41 | struct ValidateGuard { |
---|
| 42 | const TypeEnvironment* env; |
---|
| 43 | const TypeEnvironment::Classes* old_classes; |
---|
| 44 | const TypeEnvironment::Bindings* old_bindings; |
---|
| 45 | const char* last_fn; |
---|
| 46 | |
---|
| 47 | void validate_classes( const TypeEnvironment::Classes* c ) { |
---|
| 48 | typedef TypeEnvironment::Classes C; |
---|
| 49 | |
---|
| 50 | assertf( c != nullptr, "classes non-null" ); |
---|
| 51 | |
---|
| 52 | C::Mode cmode = c->get_mode(); |
---|
| 53 | if ( cmode == C::BASE ) { |
---|
| 54 | // xxx - consistency checks |
---|
| 55 | } else { |
---|
| 56 | assertf( cmode == C::ADD || cmode == C::REM || cmode == C::ADDTO || cmode == C::REMFROM, "valid classes mode" ); |
---|
| 57 | validate_classes( c->get_base() ); |
---|
| 58 | } |
---|
| 59 | } |
---|
| 60 | |
---|
| 61 | void validate_bindings( const TypeEnvironment::Bindings* b ) { |
---|
| 62 | typedef TypeEnvironment::Bindings B; |
---|
| 63 | |
---|
| 64 | assertf( b != nullptr, "bindings non-null" ); |
---|
| 65 | |
---|
| 66 | B::Mode bmode = b->get_mode(); |
---|
| 67 | if ( bmode == B::BASE ) { |
---|
| 68 | // xxx - consistency checks |
---|
| 69 | } else { |
---|
| 70 | assertf( bmode == B::REM || bmode == B::INS || bmode == B::UPD, "valid bindings mode" ); |
---|
| 71 | validate_bindings( b->get_base() ); |
---|
| 72 | } |
---|
| 73 | } |
---|
| 74 | |
---|
| 75 | void validate_env() { |
---|
| 76 | validate_classes( env->classes ); |
---|
| 77 | validate_bindings( env->bindings ); |
---|
| 78 | |
---|
| 79 | // xxx - joint validation |
---|
| 80 | } |
---|
| 81 | |
---|
| 82 | ValidateGuard(const TypeEnvironment* e) |
---|
| 83 | : env{e}, old_classes{e->classes}, old_bindings{e->bindings}, last_fn{e->last_fn} |
---|
| 84 | { validate_env(); } |
---|
| 85 | ValidateGuard(const TypeEnvironment* e, const char* fn) |
---|
| 86 | : env{e}, old_classes{e->classes}, old_bindings{e->bindings}, last_fn{fn} |
---|
| 87 | { validate_env(); } |
---|
| 88 | ~ValidateGuard() { |
---|
| 89 | validate_env(); |
---|
| 90 | if ( env->classes != old_classes ) validate_classes( old_classes ); |
---|
| 91 | if ( env->bindings != old_bindings ) validate_bindings( old_bindings ); |
---|
| 92 | const_cast<TypeEnvironment*>(env)->last_fn = last_fn; |
---|
| 93 | } |
---|
| 94 | }; |
---|
| 95 | #else |
---|
| 96 | #define PRE_POST_VALIDATE |
---|
| 97 | #define PRE_POST_VALIDATE_NOM |
---|
| 98 | #endif |
---|
| 99 | |
---|
[a32b204] | 100 | void printAssertionSet( const AssertionSet &assertions, std::ostream &os, int indent ) { |
---|
| 101 | for ( AssertionSet::const_iterator i = assertions.begin(); i != assertions.end(); ++i ) { |
---|
| 102 | i->first->print( os, indent ); |
---|
[6c3a988f] | 103 | if ( i->second.isUsed ) { |
---|
[a32b204] | 104 | os << "(used)"; |
---|
| 105 | } else { |
---|
| 106 | os << "(not used)"; |
---|
| 107 | } // if |
---|
| 108 | } // for |
---|
| 109 | } |
---|
| 110 | |
---|
| 111 | void printOpenVarSet( const OpenVarSet &openVars, std::ostream &os, int indent ) { |
---|
| 112 | os << std::string( indent, ' ' ); |
---|
| 113 | for ( OpenVarSet::const_iterator i = openVars.begin(); i != openVars.end(); ++i ) { |
---|
| 114 | os << i->first << "(" << i->second << ") "; |
---|
| 115 | } // for |
---|
| 116 | } |
---|
| 117 | |
---|
[982f95d] | 118 | std::pair<interned_string, interned_string> TypeEnvironment::mergeClasses( |
---|
| 119 | interned_string root1, interned_string root2 ) { |
---|
[d318a18] | 120 | PRE_POST_VALIDATE |
---|
[982f95d] | 121 | // merge classes |
---|
| 122 | Classes* newClasses = classes->merge( root1, root2 ); |
---|
| 123 | |
---|
| 124 | // determine new root |
---|
| 125 | assertf(classes->get_mode() == Classes::REMFROM, "classes updated to REMFROM by merge"); |
---|
[184557e] | 126 | auto ret = std::make_pair( classes->get_root(), classes->get_child() ); |
---|
[982f95d] | 127 | |
---|
| 128 | // finalize classes |
---|
| 129 | classes = newClasses; |
---|
| 130 | return ret; |
---|
| 131 | } |
---|
| 132 | |
---|
| 133 | ClassRef TypeEnvironment::lookup( interned_string var ) const { |
---|
| 134 | interned_string root = classes->find_or_default( var, nullptr ); |
---|
| 135 | if ( root ) return { this, root }; |
---|
| 136 | else return { nullptr, var }; |
---|
| 137 | } |
---|
| 138 | |
---|
[b21c77a] | 139 | bool isFtype( Type *type ) { |
---|
| 140 | if ( dynamic_cast< FunctionType* >( type ) ) { |
---|
| 141 | return true; |
---|
| 142 | } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( type ) ) { |
---|
| 143 | return typeInst->get_isFtype(); |
---|
| 144 | } // if |
---|
| 145 | return false; |
---|
| 146 | } |
---|
| 147 | |
---|
[982f95d] | 148 | bool tyVarCompatible( const TypeDecl::Data & data, Type *type ) { |
---|
| 149 | switch ( data.kind ) { |
---|
| 150 | case TypeDecl::Dtype: |
---|
| 151 | // to bind to an object type variable, the type must not be a function type. |
---|
| 152 | // if the type variable is specified to be a complete type then the incoming |
---|
| 153 | // type must also be complete |
---|
| 154 | // xxx - should this also check that type is not a tuple type and that it's not a ttype? |
---|
| 155 | return ! isFtype( type ) && (! data.isComplete || type->isComplete() ); |
---|
| 156 | case TypeDecl::Ftype: |
---|
| 157 | return isFtype( type ); |
---|
| 158 | case TypeDecl::Ttype: |
---|
| 159 | // ttype unifies with any tuple type |
---|
| 160 | return dynamic_cast< TupleType * >( type ) || Tuples::isTtype( type ); |
---|
| 161 | } // switch |
---|
| 162 | return false; |
---|
| 163 | } |
---|
| 164 | |
---|
| 165 | bool TypeEnvironment::bindVar( TypeInstType* typeInst, Type* bindTo, |
---|
| 166 | const TypeDecl::Data& data, AssertionSet& need, AssertionSet& have, |
---|
| 167 | const OpenVarSet& openVars, WidenMode widenMode, const SymTab::Indexer& indexer ) { |
---|
[d318a18] | 168 | PRE_POST_VALIDATE |
---|
[982f95d] | 169 | // remove references from other, so that type variables can only bind to value types |
---|
| 170 | bindTo = bindTo->stripReferences(); |
---|
| 171 | |
---|
| 172 | auto tyVar = openVars.find( typeInst->get_name() ); |
---|
| 173 | assert( tyVar != openVars.end() ); |
---|
[5c14030] | 174 | if ( ! tyVarCompatible( tyVar->second, bindTo ) ) return false; |
---|
[982f95d] | 175 | |
---|
| 176 | if ( occurs( bindTo, typeInst->get_name(), *this ) ) return false; |
---|
| 177 | |
---|
| 178 | if ( ClassRef curClass = lookup( typeInst->get_name() ) ) { |
---|
| 179 | BoundType curData = curClass.get_bound(); |
---|
| 180 | if ( curData.type ) { |
---|
| 181 | Type* common = nullptr; |
---|
| 182 | // attempt to unify equivalence class type (which needs its qualifiers restored) |
---|
| 183 | // with the target type |
---|
| 184 | Type* newType = curData.type->clone(); |
---|
| 185 | newType->get_qualifiers() = typeInst->get_qualifiers(); |
---|
| 186 | if ( unifyInexact( newType, bindTo, *this, need, have, openVars, |
---|
| 187 | widenMode & WidenMode{ curData.allowWidening, true }, indexer, common ) ) { |
---|
| 188 | if ( common ) { |
---|
| 189 | // update bound type to common type |
---|
| 190 | common->get_qualifiers() = Type::Qualifiers{}; |
---|
| 191 | curData.type = common; |
---|
| 192 | bindings = bindings->set( curClass.update_root(), curData ); |
---|
| 193 | } |
---|
| 194 | return true; |
---|
| 195 | } else return false; |
---|
| 196 | } else { |
---|
| 197 | // update bound type to other type |
---|
| 198 | curData.type = bindTo->clone(); |
---|
| 199 | curData.type->get_qualifiers() = Type::Qualifiers{}; |
---|
| 200 | curData.allowWidening = widenMode.widenFirst && widenMode.widenSecond; |
---|
| 201 | bindings = bindings->set( curClass.get_root(), curData ); |
---|
| 202 | } |
---|
| 203 | } else { |
---|
| 204 | // make new class consisting entirely of this variable |
---|
[5c14030] | 205 | BoundType curData{ |
---|
| 206 | bindTo->clone(), widenMode.widenFirst && widenMode.widenSecond, data }; |
---|
[982f95d] | 207 | curData.type->get_qualifiers() = Type::Qualifiers{}; |
---|
| 208 | classes = classes->add( curClass.get_root() ); |
---|
| 209 | bindings = bindings->set( curClass.get_root(), curData ); |
---|
| 210 | } |
---|
| 211 | return true; |
---|
| 212 | } |
---|
| 213 | |
---|
| 214 | bool TypeEnvironment::bindVarToVar( TypeInstType* var1, TypeInstType* var2, |
---|
| 215 | const TypeDecl::Data& data, AssertionSet& need, AssertionSet& have, |
---|
| 216 | const OpenVarSet& openVars, WidenMode widenMode, const SymTab::Indexer& indexer ) { |
---|
[d318a18] | 217 | PRE_POST_VALIDATE |
---|
[5c14030] | 218 | ClassRef class1 = lookup( var1->get_name() ); |
---|
| 219 | ClassRef class2 = lookup( var2->get_name() ); |
---|
[982f95d] | 220 | |
---|
| 221 | // exit early if variables already bound together |
---|
| 222 | if ( class1 && class2 && class1 == class2 ) { |
---|
| 223 | BoundType data1 = class1.get_bound(); |
---|
| 224 | // narrow the binding if needed |
---|
[5c14030] | 225 | if ( data1.allowWidening && widenMode.widenFirst != widenMode.widenSecond ) { |
---|
[982f95d] | 226 | data1.allowWidening = false; |
---|
| 227 | bindings = bindings->set( class1.get_root(), data1 ); |
---|
| 228 | } |
---|
| 229 | return true; |
---|
| 230 | } |
---|
| 231 | |
---|
| 232 | BoundType data1 = class1 ? class1.get_bound() : BoundType{}; |
---|
| 233 | BoundType data2 = class2 ? class2.get_bound() : BoundType{}; |
---|
| 234 | |
---|
| 235 | bool widen1 = data1.allowWidening && widenMode.widenFirst; |
---|
| 236 | bool widen2 = data2.allowWidening && widenMode.widenSecond; |
---|
| 237 | |
---|
| 238 | if ( data1.type && data2.type ) { |
---|
| 239 | // attempt to unify bound classes |
---|
| 240 | Type* common = nullptr; |
---|
| 241 | if ( unifyInexact( data1.type->clone(), data2.type->clone(), *this, need, have, |
---|
| 242 | openVars, WidenMode{ widen1, widen2 }, indexer, common ) ) { |
---|
| 243 | // merge type variables |
---|
[5c14030] | 244 | interned_string root = |
---|
| 245 | mergeClasses( class1.update_root(), class2.update_root() ).first; |
---|
[982f95d] | 246 | // update bindings |
---|
| 247 | data1.allowWidening = widen1 && widen2; |
---|
| 248 | if ( common ) { |
---|
| 249 | common->get_qualifiers() = Type::Qualifiers{}; |
---|
| 250 | data1.type = common; |
---|
| 251 | } |
---|
| 252 | bindings = bindings->set( root, data1 ); |
---|
| 253 | } else return false; |
---|
| 254 | } else if ( class1 && class2 ) { |
---|
| 255 | // both classes exist, only one bound -- merge type variables |
---|
| 256 | auto merged = mergeClasses( class1.get_root(), class2.get_root() ); |
---|
| 257 | // remove subordinate binding |
---|
| 258 | bindings = bindings->erase( merged.second ); |
---|
| 259 | // update root binding (narrow widening as needed, or set new binding for changed root) |
---|
| 260 | if ( data1.type ) { |
---|
| 261 | if ( data1.allowWidening != widen1 ) { |
---|
| 262 | data1.allowWidening = widen1; |
---|
| 263 | bindings = bindings->set( merged.first, data1 ); |
---|
| 264 | } else if ( merged.first == class2.get_root() ) { |
---|
| 265 | bindings = bindings->set( merged.first, data1 ); |
---|
| 266 | } |
---|
| 267 | } else /* if ( data2.type ) */ { |
---|
| 268 | if ( data2.allowWidening != widen2 ) { |
---|
| 269 | data2.allowWidening = widen2; |
---|
[5c14030] | 270 | bindings = bindings->set( merged.first, data2 ); |
---|
[982f95d] | 271 | } else if ( merged.first == class1.get_root() ) { |
---|
| 272 | bindings = bindings->set( merged.first, data2 ); |
---|
| 273 | } |
---|
| 274 | } |
---|
| 275 | } else if ( class1 ) { |
---|
| 276 | // add unbound var2 to class1 |
---|
| 277 | classes = classes->add( class2.get_root() ); |
---|
| 278 | auto merged = mergeClasses( class1.get_root(), class2.get_root() ); |
---|
| 279 | // update bindings (narrow as needed, or switch binding to root) |
---|
| 280 | if ( merged.first == class2.get_root() ) { |
---|
| 281 | data1.allowWidening = widen1; |
---|
| 282 | bindings = bindings->erase( merged.second )->set( merged.first, data1 ); |
---|
| 283 | } else if ( data1.allowWidening != widen1 ) { |
---|
| 284 | bindings = bindings->set( merged.first, data1 ); |
---|
| 285 | } |
---|
| 286 | } else if ( class2 ) { |
---|
| 287 | // add unbound var1 to class1 |
---|
| 288 | classes = classes->add( class1.get_root() ); |
---|
| 289 | auto merged = mergeClasses( class1.get_root(), class2.get_root() ); |
---|
| 290 | // update bindings (narrow as needed, or switch binding to root) |
---|
| 291 | if ( merged.first == class1.get_root() ) { |
---|
| 292 | data2.allowWidening = widen2; |
---|
| 293 | bindings = bindings->erase( merged.second )->set( merged.first, data2 ); |
---|
| 294 | } else if ( data2.allowWidening != widen2 ) { |
---|
| 295 | bindings = bindings->set( merged.first, data2 ); |
---|
| 296 | } |
---|
| 297 | } else { |
---|
| 298 | // make new class with pair of unbound vars |
---|
| 299 | classes = classes->add( class1.get_root() )->add( class2.get_root() ); |
---|
| 300 | auto merged = mergeClasses( class1.get_root(), class2.get_root() ); |
---|
| 301 | bindings = bindings->set( merged.first, BoundType{ nullptr, widen1 && widen2, data } ); |
---|
| 302 | } |
---|
| 303 | return true; |
---|
| 304 | } |
---|
[a32b204] | 305 | |
---|
[8c49c0e] | 306 | void TypeEnvironment::add( const Type::ForallList &tyDecls ) { |
---|
[d318a18] | 307 | PRE_POST_VALIDATE |
---|
[8c49c0e] | 308 | for ( Type::ForallList::const_iterator i = tyDecls.begin(); i != tyDecls.end(); ++i ) { |
---|
[184557e] | 309 | interned_string name = (*i)->get_name(); |
---|
| 310 | classes = classes->add( name ); |
---|
| 311 | bindings = bindings->set( name, *i ); |
---|
[a32b204] | 312 | } // for |
---|
| 313 | } |
---|
| 314 | |
---|
[09c72d5] | 315 | void TypeEnvironment::add( const TypeSubstitution & sub ) { |
---|
[d318a18] | 316 | PRE_POST_VALIDATE |
---|
[184557e] | 317 | interned_string not_found{nullptr}; |
---|
| 318 | |
---|
[09c72d5] | 319 | for ( auto p : sub ) { |
---|
[184557e] | 320 | interned_string var = p.first; |
---|
| 321 | |
---|
| 322 | // filter overlapping classes out of existing environment |
---|
[d318a18] | 323 | // xxx - this is a very shady assumption, but has worked for a long time... |
---|
[5c14030] | 324 | interned_string root = classes->find_or_default( var, not_found ); |
---|
[184557e] | 325 | if ( root != not_found ) { |
---|
| 326 | classes = classes->remove_class( root ); |
---|
| 327 | bindings = bindings->erase( root ); |
---|
| 328 | } |
---|
| 329 | |
---|
[09c72d5] | 330 | // Minimal assumptions. Not technically correct, but might be good enough, and |
---|
| 331 | // is the best we can do at the moment since information is lost in the |
---|
| 332 | // transition to TypeSubstitution |
---|
[184557e] | 333 | TypeDecl::Data data{ TypeDecl::Dtype, false }; |
---|
| 334 | |
---|
| 335 | // add variable to class and bindings |
---|
| 336 | classes = classes->add( var ); |
---|
[5c14030] | 337 | bindings = bindings->set( var, BoundType{ p.second->clone(), false, data } ); |
---|
[09c72d5] | 338 | } |
---|
| 339 | } |
---|
| 340 | |
---|
[a32b204] | 341 | void TypeEnvironment::makeSubstitution( TypeSubstitution &sub ) const { |
---|
[d318a18] | 342 | PRE_POST_VALIDATE_NOM |
---|
[5c14030] | 343 | bindings->for_each([&]( interned_string root, const BoundType& bound ){ |
---|
| 344 | classes->for_class(root, [&]( interned_string var ) { |
---|
[184557e] | 345 | if ( bound.type ) { |
---|
| 346 | sub.add( var, bound.type ); |
---|
| 347 | } else if ( var != root ) { |
---|
| 348 | sub.add( var, new TypeInstType{ |
---|
| 349 | Type::Qualifiers{}, root, bound.data.kind == TypeDecl::Ftype } ); |
---|
| 350 | } |
---|
| 351 | }); |
---|
| 352 | }); |
---|
| 353 | |
---|
[a32b204] | 354 | sub.normalize(); |
---|
| 355 | } |
---|
| 356 | |
---|
[50377a4] | 357 | void TypeEnvironment::print( std::ostream &os, Indenter indent ) const { |
---|
[5c14030] | 358 | bindings->for_each([&]( interned_string root, const BoundType& bound ) { |
---|
[184557e] | 359 | os << "( "; |
---|
[5c14030] | 360 | classes->for_class( root, [&os]( interned_string var ) { os << var << " "; } ); |
---|
[184557e] | 361 | os << ")"; |
---|
| 362 | if ( bound.type ) { |
---|
| 363 | os << " -> "; |
---|
[5c14030] | 364 | bound.type->print( os, indent+1 ); |
---|
[184557e] | 365 | } |
---|
| 366 | if ( ! bound.allowWidening ) { |
---|
| 367 | os << " (no widening)"; |
---|
| 368 | } |
---|
| 369 | os << std::endl; |
---|
| 370 | }); |
---|
[a32b204] | 371 | } |
---|
| 372 | |
---|
[d318a18] | 373 | namespace { |
---|
| 374 | // temporary representation of an equivalence class |
---|
| 375 | struct EqvClass { |
---|
| 376 | std::vector<interned_string> vars; |
---|
| 377 | BoundType bound; |
---|
| 378 | |
---|
| 379 | EqvClass() = default; |
---|
| 380 | EqvClass(const BoundType& b) : bound{b} {} |
---|
| 381 | }; |
---|
| 382 | } |
---|
| 383 | |
---|
[184557e] | 384 | void TypeEnvironment::simpleCombine( const TypeEnvironment &o ) { |
---|
[d318a18] | 385 | PRE_POST_VALIDATE |
---|
| 386 | // check for same environment |
---|
| 387 | if ( classes == o.classes && bindings == o.bindings ) return; |
---|
| 388 | |
---|
| 389 | // read out equivalence classes (avoids conflicting reroots) |
---|
| 390 | std::vector<EqvClass> ecs; |
---|
[5c14030] | 391 | o.bindings->for_each( [&]( interned_string root, const BoundType& bound ) { |
---|
[d318a18] | 392 | ecs.emplace_back(bound); |
---|
| 393 | o.classes->for_class( root, [&]( interned_string var ) { |
---|
| 394 | ecs.back().vars.push_back( var ); |
---|
| 395 | } ); |
---|
| 396 | } ); |
---|
| 397 | |
---|
| 398 | // read equivalence classes into self |
---|
| 399 | for ( EqvClass& ec : ecs ) { |
---|
| 400 | // merge vars |
---|
[184557e] | 401 | interned_string new_root{nullptr}; |
---|
[d318a18] | 402 | for ( interned_string var : ec.vars ) { |
---|
| 403 | Classes* new_classes = classes->add( var ); |
---|
| 404 | if ( new_classes == classes ) { var = classes->find( var ); } |
---|
| 405 | else { classes = new_classes; } |
---|
[184557e] | 406 | new_root = new_root ? mergeClasses( new_root, var ).first : var; |
---|
[d318a18] | 407 | } |
---|
| 408 | // set binding |
---|
| 409 | bindings = bindings->set( new_root, ec.bound ); |
---|
| 410 | } |
---|
[a32b204] | 411 | } |
---|
| 412 | |
---|
[9160cb2] | 413 | bool TypeEnvironment::combine( const TypeEnvironment& o, const SymTab::Indexer& indexer ) { |
---|
[f89a111] | 414 | // short-circuit for empty cases |
---|
| 415 | if ( o.isEmpty() ) return true; |
---|
| 416 | if ( isEmpty() ) { |
---|
| 417 | *this = o; |
---|
| 418 | return true; |
---|
| 419 | } |
---|
| 420 | |
---|
| 421 | /// Edit item for path state |
---|
| 422 | struct Edit { |
---|
| 423 | Classes::Mode mode; ///< Type of change to a key |
---|
| 424 | interned_string root; ///< New/Previous root, if addTo/remFrom node |
---|
| 425 | |
---|
| 426 | Edit(Classes::Mode m, interned_string r = nullptr) : mode{m}, root{r} {} |
---|
| 427 | }; |
---|
| 428 | |
---|
| 429 | // track class changes |
---|
| 430 | classes->reroot(); |
---|
| 431 | PRE_POST_VALIDATE |
---|
| 432 | |
---|
| 433 | using EditEntry = std::pair<interned_string, Edit>; |
---|
| 434 | using EditList = std::list<EditEntry>; |
---|
| 435 | using IndexedEdits = std::vector<EditList::iterator>; |
---|
| 436 | |
---|
| 437 | EditList edits; |
---|
| 438 | std::unordered_map<interned_string, IndexedEdits> editIndex; |
---|
| 439 | |
---|
| 440 | // trace path from other environment |
---|
| 441 | const Classes* oclasses = o.classes; |
---|
| 442 | Classes::Mode omode = oclasses->get_mode(); |
---|
| 443 | while ( omode != Classes::BASE ) { |
---|
| 444 | interned_string key = oclasses->get_key(); |
---|
| 445 | IndexedEdits& forKey = editIndex[ key ]; |
---|
| 446 | |
---|
| 447 | if ( forKey.empty() ) { |
---|
| 448 | // newly seen key, mark op |
---|
| 449 | interned_string root = ( omode == Classes::ADD || omode == Classes::REM ) ? |
---|
| 450 | nullptr : oclasses->get_root(); |
---|
| 451 | auto it = edits.emplace( edits.begin(), key, Edit{ omode, root } ); |
---|
| 452 | forKey.push_back( move(it) ); |
---|
| 453 | } else { |
---|
| 454 | auto next = forKey.back(); // edit next applied to this key |
---|
| 455 | Classes::Mode nmode = next->second.mode; // next action applied |
---|
| 456 | |
---|
| 457 | switch ( omode ) { |
---|
| 458 | case Classes::ADD: { |
---|
| 459 | switch ( nmode ) { |
---|
| 460 | case Classes::REM: { |
---|
| 461 | // later removal, no net change to classes |
---|
| 462 | edits.erase( next ); |
---|
| 463 | forKey.pop_back(); |
---|
| 464 | } break; |
---|
| 465 | case Classes::ADDTO: { |
---|
| 466 | // later merge, prefix with this addition |
---|
| 467 | auto it = edits.emplace( edits.begin(), key, Edit{ omode } ); |
---|
| 468 | forKey.push_back( move(it) ); |
---|
| 469 | } break; |
---|
| 470 | default: assertf( false, "inconsistent mode" ); |
---|
| 471 | } |
---|
| 472 | } break; |
---|
| 473 | case Classes::REM: { |
---|
| 474 | // later addition, no net change to classes |
---|
| 475 | assertf( nmode == Classes::ADD, "inconsistent mode" ); |
---|
| 476 | edits.erase( next ); |
---|
| 477 | forKey.pop_back(); |
---|
| 478 | } break; |
---|
| 479 | case Classes::ADDTO: { |
---|
| 480 | // later unmerged from same class, no net change to classes |
---|
[9160cb2] | 481 | assertf( nmode == Classes::REMFROM, "inconsistent mode" ); |
---|
| 482 | assertf( oclasses->get_root() == next->second.root, "inconsistent tree" ); |
---|
[f89a111] | 483 | edits.erase( next ); |
---|
| 484 | forKey.pop_back(); |
---|
| 485 | } break; |
---|
| 486 | case Classes::REMFROM: { |
---|
| 487 | interned_string root = oclasses->get_root(); |
---|
| 488 | switch ( nmode ) { |
---|
| 489 | case Classes::REM: { |
---|
| 490 | // later removal, prefix with this unmerge |
---|
| 491 | auto it = edits.emplace( edits.begin(), key, Edit{ omode, root } ); |
---|
| 492 | forKey.push_back( move(it) ); |
---|
| 493 | } break; |
---|
| 494 | case Classes::ADDTO: { |
---|
| 495 | if ( root == next->second.root ) { |
---|
| 496 | // later merged back into same class, no net change |
---|
| 497 | edits.erase( next ); |
---|
| 498 | forKey.pop_back(); |
---|
| 499 | } else { |
---|
| 500 | // later merged into different class, prefix with this unmerge |
---|
| 501 | auto it = edits.emplace( |
---|
| 502 | edits.begin(), key, Edit{ omode, root } ); |
---|
| 503 | forKey.push_back( move(it) ); |
---|
| 504 | } |
---|
| 505 | } break; |
---|
| 506 | default: assertf( false, "inconsistent mode" ); |
---|
| 507 | } |
---|
| 508 | } break; |
---|
| 509 | default: assertf( false, "invalid mode" ); |
---|
| 510 | } |
---|
| 511 | } |
---|
| 512 | |
---|
| 513 | oclasses = oclasses->get_base(); |
---|
| 514 | omode = oclasses->get_mode(); |
---|
| 515 | } |
---|
| 516 | assertf( oclasses == classes, "classes must be versions of the same map" ); |
---|
| 517 | |
---|
| 518 | /// Edit item for binding changes |
---|
| 519 | struct BEdit { |
---|
| 520 | Bindings::Mode mode; ///< Type of change to a key |
---|
| 521 | BoundType val; ///< Updated key value, if applicable |
---|
| 522 | |
---|
| 523 | BEdit(Bindings::Mode m) : mode{m}, val{} {} |
---|
| 524 | BEdit(Bindings::Mode m, const BoundType& b) : mode{m}, val{b} {} |
---|
| 525 | }; |
---|
| 526 | |
---|
| 527 | // track binding merges |
---|
| 528 | bindings->reroot(); |
---|
| 529 | std::unordered_map<interned_string, BEdit> bedits; // edits to base bindings |
---|
| 530 | |
---|
| 531 | // trace path from other environment |
---|
| 532 | const Bindings* bbindings = o.bindings; |
---|
| 533 | Bindings::Mode bmode = bbindings->get_mode(); |
---|
| 534 | while ( bmode != Bindings::BASE ) { |
---|
| 535 | interned_string key = bbindings->get_key(); |
---|
| 536 | auto it = bedits.find( key ); |
---|
| 537 | |
---|
| 538 | if ( it == bedits.end() ) { |
---|
| 539 | // newly seen key, mark operation |
---|
| 540 | if ( bmode == Bindings::REM ) { |
---|
[9160cb2] | 541 | bedits.emplace_hint( it, key, BEdit{ bmode } ); |
---|
[f89a111] | 542 | } else { |
---|
[9160cb2] | 543 | bedits.emplace_hint( it, key, BEdit{ bmode, bbindings->get_val() } ); |
---|
[f89a111] | 544 | } |
---|
| 545 | } else { |
---|
| 546 | Bindings::Mode& smode = it->second.mode; |
---|
| 547 | switch ( bmode ) { |
---|
| 548 | case Bindings::REM: { |
---|
| 549 | // later insertion, change to update |
---|
| 550 | assertf( smode == Bindings::INS, "inconsistent mode" ); |
---|
| 551 | smode = Bindings::UPD; |
---|
| 552 | } break; |
---|
| 553 | case Bindings::INS: { |
---|
| 554 | switch ( smode ) { |
---|
| 555 | case Bindings::REM: { |
---|
| 556 | // later removal, no net change to map |
---|
| 557 | bedits.erase( it ); |
---|
| 558 | } break; |
---|
| 559 | case Bindings::UPD: { |
---|
| 560 | // later update collapses to insertion |
---|
| 561 | smode = Bindings::INS; |
---|
| 562 | } break; |
---|
| 563 | default: assertf( false, "inconsistent mode" ); |
---|
| 564 | } |
---|
| 565 | } break; |
---|
| 566 | case Bindings::UPD: { |
---|
| 567 | // later removal or update overrides this update |
---|
| 568 | assertf( smode == Bindings::REM || smode == Bindings::UPD, "inconsistent mode" ); |
---|
| 569 | } break; |
---|
| 570 | default: assertf( false, "invalid mode" ); |
---|
| 571 | } |
---|
| 572 | } |
---|
| 573 | |
---|
| 574 | bbindings = bbindings->get_base(); |
---|
| 575 | bmode = bbindings->get_mode(); |
---|
| 576 | } |
---|
[9160cb2] | 577 | assertf( bbindings == bindings, "bindings must be versions of same map" ); |
---|
[f89a111] | 578 | |
---|
| 579 | // merge typeclasses (always possible, can always merge all classes into one if the |
---|
| 580 | // bindings unify) |
---|
| 581 | for ( const EditEntry& edit : edits ) { |
---|
| 582 | interned_string key = edit.first; |
---|
| 583 | const Edit& e = edit.second; |
---|
| 584 | |
---|
| 585 | switch ( e.mode ) { |
---|
| 586 | case Classes::ADD: { |
---|
| 587 | // add new type variable |
---|
| 588 | classes = classes->add( key ); |
---|
| 589 | // add binding for variable |
---|
| 590 | auto bit = bedits.find( key ); |
---|
| 591 | if ( bit != bedits.end() ) { |
---|
| 592 | // take final value if it is a root in its own map |
---|
| 593 | const BEdit& be = bit->second; |
---|
| 594 | assertf( be.mode == Bindings::INS, "inconsistent binding" ); |
---|
| 595 | bindings = bindings->set( key, std::move(be.val) ); |
---|
| 596 | // remove update from edit set so that it isn't re-checked |
---|
| 597 | bedits.erase( bit ); |
---|
| 598 | } else { |
---|
| 599 | // otherwise just put in default binding |
---|
| 600 | bindings = bindings->set( key, BoundType{} ); |
---|
| 601 | } |
---|
| 602 | } break; |
---|
| 603 | case Classes::REM: { |
---|
| 604 | // do not remove type variable (merging) |
---|
| 605 | } break; |
---|
| 606 | case Classes::ADDTO: { |
---|
| 607 | // if previous REMFROM on this key, or ADDTO on this root, may not match |
---|
| 608 | // current state in `classes` |
---|
| 609 | interned_string key_root = classes->find( key ); |
---|
| 610 | interned_string merge_root = classes->find( e.root ); |
---|
| 611 | // skip case where classes already merged |
---|
| 612 | if ( key_root == merge_root ) break; |
---|
| 613 | // merge classes and remove binding for new child |
---|
| 614 | interned_string new_child = mergeClasses( key_root, merge_root ).second; |
---|
| 615 | if ( bindings->count( new_child ) ) { |
---|
| 616 | // add new insert edit to check merge with old value if needed |
---|
| 617 | const BoundType& child_bind = bindings->get( new_child ); |
---|
| 618 | if ( child_bind.type ) { |
---|
| 619 | // store this insert under the original key, which must be a REM |
---|
| 620 | // binding change if present |
---|
| 621 | auto bit = bedits.find( key ); |
---|
| 622 | if ( bit != bedits.end() ) { |
---|
| 623 | BEdit& be = bit->second; |
---|
| 624 | assertf( be.mode == Bindings::REM, "inconsistent binding" ); |
---|
| 625 | be = BEdit{ Bindings::INS, child_bind }; |
---|
| 626 | } else { |
---|
| 627 | bedits.emplace_hint( bit, key, BEdit{ Bindings::INS, child_bind } ); |
---|
| 628 | } |
---|
| 629 | } |
---|
| 630 | // remove child binding from map |
---|
| 631 | bindings = bindings->erase( new_child ); |
---|
| 632 | } |
---|
| 633 | } break; |
---|
| 634 | case Classes::REMFROM: { |
---|
| 635 | // do not split classes |
---|
| 636 | } break; |
---|
| 637 | default: assertf( false, "invalid mode" ); |
---|
| 638 | } |
---|
| 639 | } |
---|
| 640 | |
---|
| 641 | // finish merging bindings. This may fail, or may merge further classes |
---|
| 642 | for ( const auto& entry : bedits ) { |
---|
| 643 | interned_string key = entry.first; |
---|
| 644 | const BEdit& e = entry.second; |
---|
| 645 | |
---|
| 646 | // skip binding removals; the ADDTO merge has taken out all the new non-roots |
---|
| 647 | if ( e.mode == Bindings::REM ) continue; |
---|
| 648 | assertf( e.mode == Bindings::UPD || e.mode == Bindings::INS, "inconsistent binding" ); |
---|
| 649 | |
---|
| 650 | // attempt binding update |
---|
| 651 | interned_string root = classes->find( key ); |
---|
| 652 | BoundType ebound = bindings->get( root ); |
---|
| 653 | const BoundType& nbound = e.val; |
---|
| 654 | |
---|
| 655 | if ( ebound.type && nbound.type ) { |
---|
| 656 | // attempt to unify bound classes |
---|
| 657 | Type* common = nullptr; |
---|
| 658 | AssertionSet need, have; |
---|
| 659 | OpenVarSet openVars; |
---|
| 660 | if ( unifyInexact( ebound.type->clone(), nbound.type->clone(), *this, need, have, |
---|
| 661 | openVars, WidenMode{ ebound.allowWidening, nbound.allowWidening }, |
---|
| 662 | indexer, common ) ) { |
---|
| 663 | // update bindings |
---|
| 664 | ebound.allowWidening &= nbound.allowWidening; |
---|
| 665 | if ( common ) { |
---|
| 666 | common->get_qualifiers() = Type::Qualifiers{}; |
---|
| 667 | ebound.type = common; |
---|
| 668 | } |
---|
| 669 | // reset root in case updated in course of unification |
---|
| 670 | bindings = bindings->set( classes->find( root ), ebound ); |
---|
| 671 | } else return false; // cannot unify bindings |
---|
| 672 | } |
---|
| 673 | } |
---|
| 674 | |
---|
| 675 | return true; |
---|
| 676 | } |
---|
| 677 | |
---|
[a32b204] | 678 | void TypeEnvironment::extractOpenVars( OpenVarSet &openVars ) const { |
---|
[5c14030] | 679 | bindings->for_each( [&]( interned_string root, const BoundType& bound ) { |
---|
| 680 | classes->for_class( root, [&openVars,&bound]( interned_string var ) { |
---|
[184557e] | 681 | openVars[ var ] = bound.data; |
---|
| 682 | } ); |
---|
| 683 | } ); |
---|
[a32b204] | 684 | } |
---|
[51b7345] | 685 | |
---|
[a585396] | 686 | void TypeEnvironment::addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars ) { |
---|
[d318a18] | 687 | PRE_POST_VALIDATE |
---|
| 688 | if ( classes == actualEnv.classes && bindings == actualEnv.bindings ) { |
---|
| 689 | // actualEnv already the same, just need to update openVars |
---|
| 690 | extractOpenVars( openVars ); |
---|
| 691 | return; |
---|
| 692 | } else assertf(classes != actualEnv.classes && bindings != actualEnv.bindings, "classes & bindings updated together"); |
---|
| 693 | |
---|
| 694 | // read out equivalence classes (avoids conflicting reroots) |
---|
| 695 | std::vector<EqvClass> ecs; |
---|
[5c14030] | 696 | actualEnv.bindings->for_each( [&]( interned_string root, const BoundType& bound ) { |
---|
[d318a18] | 697 | ecs.emplace_back(bound); |
---|
[5c14030] | 698 | actualEnv.classes->for_class( root, [&]( interned_string var ) { |
---|
[d318a18] | 699 | ecs.back().vars.push_back( var ); |
---|
[184557e] | 700 | } ); |
---|
| 701 | } ); |
---|
[d318a18] | 702 | |
---|
| 703 | // add members of new class, setting openVars concurrently |
---|
| 704 | for ( EqvClass& ec : ecs ) { |
---|
| 705 | // merge vars |
---|
| 706 | interned_string new_root{nullptr}; |
---|
| 707 | for ( interned_string var : ec.vars ) { |
---|
| 708 | openVars[ var ] = ec.bound.data; |
---|
| 709 | Classes* new_classes = classes->add( var ); |
---|
| 710 | if ( new_classes == classes ) { |
---|
| 711 | // xxx - this case is a bit sketchy, but has been working |
---|
| 712 | // xxx - merging the classes is a departure from previous behaviour |
---|
| 713 | var = classes->find( var ); |
---|
| 714 | } else { classes = new_classes; } |
---|
| 715 | new_root = new_root ? mergeClasses( new_root, var ).first : var; |
---|
| 716 | } |
---|
| 717 | // set binding without widening |
---|
| 718 | bindings = bindings->set( new_root, |
---|
| 719 | BoundType{ maybeClone(ec.bound.type), false, ec.bound.data } ); |
---|
| 720 | } |
---|
[184557e] | 721 | } |
---|
| 722 | |
---|
| 723 | void TypeEnvironment::forbidWidening() { |
---|
[d318a18] | 724 | PRE_POST_VALIDATE |
---|
[5c14030] | 725 | bindings = bindings->mutate_each([]( const interned_string&, BoundType& c ) { |
---|
[184557e] | 726 | if ( c.allowWidening ) { |
---|
| 727 | option<BoundType> ret = c; |
---|
| 728 | c.allowWidening = false; |
---|
| 729 | return ret; |
---|
| 730 | } else return option<BoundType>{}; |
---|
| 731 | }); |
---|
[a585396] | 732 | } |
---|
| 733 | |
---|
[98a249fb] | 734 | std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env ) { |
---|
| 735 | env.print( out ); |
---|
| 736 | return out; |
---|
| 737 | } |
---|
[f229fc2] | 738 | |
---|
| 739 | PassVisitor<GcTracer> & operator<<( PassVisitor<GcTracer> & gc, const TypeEnvironment & env ) { |
---|
[d318a18] | 740 | gc.pass.visit( env ); |
---|
| 741 | // for ( ClassRef c : env ) { |
---|
| 742 | // maybeAccept( c.get_bound().type, gc ); |
---|
| 743 | // } |
---|
[f229fc2] | 744 | return gc; |
---|
| 745 | } |
---|
[51b7345] | 746 | } // namespace ResolvExpr |
---|
[a32b204] | 747 | |
---|
| 748 | // Local Variables: // |
---|
| 749 | // tab-width: 4 // |
---|
| 750 | // mode: c++ // |
---|
| 751 | // compile-command: "make install" // |
---|
| 752 | // End: // |
---|