source: src/ResolvExpr/TypeEnvironment.cc@ 5a3e1f1

new-env
Last change on this file since 5a3e1f1 was 9160cb2, checked in by Aaron Moss <a3moss@…>, 8 years ago

Breadth-first assertion resolution builds, eats all the memory
  • Property mode set to 100644
File size: 25.9 KB
Line 
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//
7// TypeEnvironment.cc --
8//
9// Author : Aaron B. Moss
10// Created On : Sun May 17 12:19:47 2015
11// Last Modified By : Aaron B. Moss
12// Last Modified On : Fri Jun 29 15:51:00 2018
13// Update Count : 5
14//
15
16#include <cassert> // for assert
17#include <algorithm> // for copy, set_intersection
18#include <iterator> // for ostream_iterator, insert_iterator
19#include <list> // for list
20#include <vector> // for vector
21#include <unordered_map> // for unordered_map
22#include <utility> // for pair, move
23
24#include "Common/InternedString.h" // for interned_string
25#include "Common/PassVisitor.h" // for PassVisitor<GcTracer>
26#include "Common/option.h" // for option<T>
27#include "Common/utility.h" // for maybeClone
28#include "SymTab/Indexer.h" // for Indexer
29#include "SynTree/GcTracer.h" // for PassVisitor<GcTracer>
30#include "SynTree/Type.h" // for Type, FunctionType, Type::Fora...
31#include "SynTree/TypeSubstitution.h" // for TypeSubstitution
32#include "Tuples/Tuples.h" // for isTtype
33#include "TypeEnvironment.h"
34#include "typeops.h" // for occurs
35#include "Unify.h" // for unifyInexact
36
37namespace ResolvExpr {
38 #if 0
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
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 );
103 if ( i->second.isUsed ) {
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
118 std::pair<interned_string, interned_string> TypeEnvironment::mergeClasses(
119 interned_string root1, interned_string root2 ) {
120 PRE_POST_VALIDATE
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");
126 auto ret = std::make_pair( classes->get_root(), classes->get_child() );
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
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
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 ) {
168 PRE_POST_VALIDATE
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() );
174 if ( ! tyVarCompatible( tyVar->second, bindTo ) ) return false;
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
205 BoundType curData{
206 bindTo->clone(), widenMode.widenFirst && widenMode.widenSecond, data };
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 ) {
217 PRE_POST_VALIDATE
218 ClassRef class1 = lookup( var1->get_name() );
219 ClassRef class2 = lookup( var2->get_name() );
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
225 if ( data1.allowWidening && widenMode.widenFirst != widenMode.widenSecond ) {
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
244 interned_string root =
245 mergeClasses( class1.update_root(), class2.update_root() ).first;
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;
270 bindings = bindings->set( merged.first, data2 );
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 }
305
306 void TypeEnvironment::add( const Type::ForallList &tyDecls ) {
307 PRE_POST_VALIDATE
308 for ( Type::ForallList::const_iterator i = tyDecls.begin(); i != tyDecls.end(); ++i ) {
309 interned_string name = (*i)->get_name();
310 classes = classes->add( name );
311 bindings = bindings->set( name, *i );
312 } // for
313 }
314
315 void TypeEnvironment::add( const TypeSubstitution & sub ) {
316 PRE_POST_VALIDATE
317 interned_string not_found{nullptr};
318
319 for ( auto p : sub ) {
320 interned_string var = p.first;
321
322 // filter overlapping classes out of existing environment
323 // xxx - this is a very shady assumption, but has worked for a long time...
324 interned_string root = classes->find_or_default( var, not_found );
325 if ( root != not_found ) {
326 classes = classes->remove_class( root );
327 bindings = bindings->erase( root );
328 }
329
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
333 TypeDecl::Data data{ TypeDecl::Dtype, false };
334
335 // add variable to class and bindings
336 classes = classes->add( var );
337 bindings = bindings->set( var, BoundType{ p.second->clone(), false, data } );
338 }
339 }
340
341 void TypeEnvironment::makeSubstitution( TypeSubstitution &sub ) const {
342 PRE_POST_VALIDATE_NOM
343 bindings->for_each([&]( interned_string root, const BoundType& bound ){
344 classes->for_class(root, [&]( interned_string var ) {
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
354 sub.normalize();
355 }
356
357 void TypeEnvironment::print( std::ostream &os, Indenter indent ) const {
358 bindings->for_each([&]( interned_string root, const BoundType& bound ) {
359 os << "( ";
360 classes->for_class( root, [&os]( interned_string var ) { os << var << " "; } );
361 os << ")";
362 if ( bound.type ) {
363 os << " -> ";
364 bound.type->print( os, indent+1 );
365 }
366 if ( ! bound.allowWidening ) {
367 os << " (no widening)";
368 }
369 os << std::endl;
370 });
371 }
372
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
384 void TypeEnvironment::simpleCombine( const TypeEnvironment &o ) {
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;
391 o.bindings->for_each( [&]( interned_string root, const BoundType& bound ) {
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
401 interned_string new_root{nullptr};
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; }
406 new_root = new_root ? mergeClasses( new_root, var ).first : var;
407 }
408 // set binding
409 bindings = bindings->set( new_root, ec.bound );
410 }
411 }
412
413 bool TypeEnvironment::combine( const TypeEnvironment& o, const SymTab::Indexer& indexer ) {
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
481 assertf( nmode == Classes::REMFROM, "inconsistent mode" );
482 assertf( oclasses->get_root() == next->second.root, "inconsistent tree" );
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 ) {
541 bedits.emplace_hint( it, key, BEdit{ bmode } );
542 } else {
543 bedits.emplace_hint( it, key, BEdit{ bmode, bbindings->get_val() } );
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 }
577 assertf( bbindings == bindings, "bindings must be versions of same map" );
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
678 void TypeEnvironment::extractOpenVars( OpenVarSet &openVars ) const {
679 bindings->for_each( [&]( interned_string root, const BoundType& bound ) {
680 classes->for_class( root, [&openVars,&bound]( interned_string var ) {
681 openVars[ var ] = bound.data;
682 } );
683 } );
684 }
685
686 void TypeEnvironment::addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars ) {
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;
696 actualEnv.bindings->for_each( [&]( interned_string root, const BoundType& bound ) {
697 ecs.emplace_back(bound);
698 actualEnv.classes->for_class( root, [&]( interned_string var ) {
699 ecs.back().vars.push_back( var );
700 } );
701 } );
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 }
721 }
722
723 void TypeEnvironment::forbidWidening() {
724 PRE_POST_VALIDATE
725 bindings = bindings->mutate_each([]( const interned_string&, BoundType& c ) {
726 if ( c.allowWidening ) {
727 option<BoundType> ret = c;
728 c.allowWidening = false;
729 return ret;
730 } else return option<BoundType>{};
731 });
732 }
733
734 std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env ) {
735 env.print( out );
736 return out;
737 }
738
739 PassVisitor<GcTracer> & operator<<( PassVisitor<GcTracer> & gc, const TypeEnvironment & env ) {
740 gc.pass.visit( env );
741 // for ( ClassRef c : env ) {
742 // maybeAccept( c.get_bound().type, gc );
743 // }
744 return gc;
745 }
746} // namespace ResolvExpr
747
748// Local Variables: //
749// tab-width: 4 //
750// mode: c++ //
751// compile-command: "make install" //
752// End: //
Note: See TracBrowser for help on using the repository browser.