Context Navigation

source: src/ResolvExpr/TypeEnvironment.cc @ 1a59641

new-env

Last change on this file since 1a59641 was 1a59641, checked in by Aaron Moss <a3moss@…>, 5 years ago
Fix open var handling in BF assn resolution; memory usage reasonable again
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
37	namespace ResolvExpr {
38	#ifdef EXPENSIVE_ENV_VALIDATION
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, OpenVarSet& openVars,
414	const SymTab::Indexer& indexer ) {
415	// short-circuit for empty cases
416	if ( o.isEmpty() ) return true;
417	if ( isEmpty() ) {
418	*this = o;
419	return true;
420	}
421
422	/// Edit item for path state
423	struct Edit {
424	Classes::Mode mode; ///< Type of change to a key
425	interned_string root; ///< New/Previous root, if addTo/remFrom node
426
427	Edit(Classes::Mode m, interned_string r = nullptr) : mode{m}, root{r} {}
428	};
429
430	// track class changes
431	classes->reroot();
432	PRE_POST_VALIDATE
433
434	using EditEntry = std::pair<interned_string, Edit>;
435	using EditList = std::list<EditEntry>;
436	using IndexedEdits = std::vector<EditList::iterator>;
437
438	EditList edits;
439	std::unordered_map<interned_string, IndexedEdits> editIndex;
440
441	// trace path from other environment
442	const Classes* oclasses = o.classes;
443	Classes::Mode omode = oclasses->get_mode();
444	while ( omode != Classes::BASE ) {
445	interned_string key = oclasses->get_key();
446	IndexedEdits& forKey = editIndex[ key ];
447
448	if ( forKey.empty() ) {
449	// newly seen key, mark op
450	interned_string root = ( omode == Classes::ADD \|\| omode == Classes::REM ) ?
451	nullptr : oclasses->get_root();
452	auto it = edits.emplace( edits.begin(), key, Edit{ omode, root } );
453	forKey.push_back( move(it) );
454	} else {
455	auto next = forKey.back(); // edit next applied to this key
456	Classes::Mode nmode = next->second.mode; // next action applied
457
458	switch ( omode ) {
459	case Classes::ADD: {
460	switch ( nmode ) {
461	case Classes::REM: {
462	// later removal, no net change to classes
463	edits.erase( next );
464	forKey.pop_back();
465	} break;
466	case Classes::ADDTO: {
467	// later merge, prefix with this addition
468	auto it = edits.emplace( edits.begin(), key, Edit{ omode } );
469	forKey.push_back( move(it) );
470	} break;
471	default: assertf( false, "inconsistent mode" );
472	}
473	} break;
474	case Classes::REM: {
475	// later addition, no net change to classes
476	assertf( nmode == Classes::ADD, "inconsistent mode" );
477	edits.erase( next );
478	forKey.pop_back();
479	} break;
480	case Classes::ADDTO: {
481	// later unmerged from same class, no net change to classes
482	assertf( nmode == Classes::REMFROM, "inconsistent mode" );
483	assertf( oclasses->get_root() == next->second.root, "inconsistent tree" );
484	edits.erase( next );
485	forKey.pop_back();
486	} break;
487	case Classes::REMFROM: {
488	interned_string root = oclasses->get_root();
489	switch ( nmode ) {
490	case Classes::REM: {
491	// later removal, prefix with this unmerge
492	auto it = edits.emplace( edits.begin(), key, Edit{ omode, root } );
493	forKey.push_back( move(it) );
494	} break;
495	case Classes::ADDTO: {
496	if ( root == next->second.root ) {
497	// later merged back into same class, no net change
498	edits.erase( next );
499	forKey.pop_back();
500	} else {
501	// later merged into different class, prefix with this unmerge
502	auto it = edits.emplace(
503	edits.begin(), key, Edit{ omode, root } );
504	forKey.push_back( move(it) );
505	}
506	} break;
507	default: assertf( false, "inconsistent mode" );
508	}
509	} break;
510	default: assertf( false, "invalid mode" );
511	}
512	}
513
514	oclasses = oclasses->get_base();
515	omode = oclasses->get_mode();
516	}
517	assertf( oclasses == classes, "classes must be versions of the same map" );
518
519	/// Edit item for binding changes
520	struct BEdit {
521	Bindings::Mode mode; ///< Type of change to a key
522	BoundType val; ///< Updated key value, if applicable
523
524	BEdit(Bindings::Mode m) : mode{m}, val{} {}
525	BEdit(Bindings::Mode m, const BoundType& b) : mode{m}, val{b} {}
526	};
527
528	// track binding merges
529	bindings->reroot();
530	std::unordered_map<interned_string, BEdit> bedits; // edits to base bindings
531
532	// trace path from other environment
533	const Bindings* bbindings = o.bindings;
534	Bindings::Mode bmode = bbindings->get_mode();
535	while ( bmode != Bindings::BASE ) {
536	interned_string key = bbindings->get_key();
537	auto it = bedits.find( key );
538
539	if ( it == bedits.end() ) {
540	// newly seen key, mark operation
541	if ( bmode == Bindings::REM ) {
542	bedits.emplace_hint( it, key, BEdit{ bmode } );
543	} else {
544	bedits.emplace_hint( it, key, BEdit{ bmode, bbindings->get_val() } );
545	}
546	} else {
547	Bindings::Mode& smode = it->second.mode;
548	switch ( bmode ) {
549	case Bindings::REM: {
550	// later insertion, change to update
551	assertf( smode == Bindings::INS, "inconsistent mode" );
552	smode = Bindings::UPD;
553	} break;
554	case Bindings::INS: {
555	switch ( smode ) {
556	case Bindings::REM: {
557	// later removal, no net change to map
558	bedits.erase( it );
559	} break;
560	case Bindings::UPD: {
561	// later update collapses to insertion
562	smode = Bindings::INS;
563	} break;
564	default: assertf( false, "inconsistent mode" );
565	}
566	} break;
567	case Bindings::UPD: {
568	// later removal or update overrides this update
569	assertf( smode == Bindings::REM \|\| smode == Bindings::UPD, "inconsistent mode" );
570	} break;
571	default: assertf( false, "invalid mode" );
572	}
573	}
574
575	bbindings = bbindings->get_base();
576	bmode = bbindings->get_mode();
577	}
578	assertf( bbindings == bindings, "bindings must be versions of same map" );
579
580	// merge typeclasses (always possible, can always merge all classes into one if the
581	// bindings unify)
582	for ( const EditEntry& edit : edits ) {
583	interned_string key = edit.first;
584	const Edit& e = edit.second;
585
586	switch ( e.mode ) {
587	case Classes::ADD: {
588	// add new type variable
589	classes = classes->add( key );
590	// add binding for variable
591	auto bit = bedits.find( key );
592	if ( bit != bedits.end() ) {
593	// take final value if it is a root in its own map
594	const BEdit& be = bit->second;
595	assertf( be.mode == Bindings::INS, "inconsistent binding" );
596	bindings = bindings->set( key, std::move(be.val) );
597	// remove update from edit set so that it isn't re-checked
598	bedits.erase( bit );
599	} else {
600	// otherwise just put in default binding
601	bindings = bindings->set( key, BoundType{} );
602	}
603	} break;
604	case Classes::REM: {
605	// do not remove type variable (merging)
606	} break;
607	case Classes::ADDTO: {
608	// if previous REMFROM on this key, or ADDTO on this root, may not match
609	// current state in `classes`
610	interned_string key_root = classes->find( key );
611	interned_string merge_root = classes->find( e.root );
612	// skip case where classes already merged
613	if ( key_root == merge_root ) break;
614	// merge classes and remove binding for new child
615	interned_string new_child = mergeClasses( key_root, merge_root ).second;
616	if ( bindings->count( new_child ) ) {
617	// add new insert edit to check merge with old value if needed
618	const BoundType& child_bind = bindings->get( new_child );
619	if ( child_bind.type ) {
620	// store this insert under the original key, which must be a REM
621	// binding change if present
622	auto bit = bedits.find( key );
623	if ( bit != bedits.end() ) {
624	BEdit& be = bit->second;
625	assertf( be.mode == Bindings::REM, "inconsistent binding" );
626	be = BEdit{ Bindings::INS, child_bind };
627	} else {
628	bedits.emplace_hint( bit, key, BEdit{ Bindings::INS, child_bind } );
629	}
630	}
631	// remove child binding from map
632	bindings = bindings->erase( new_child );
633	}
634	} break;
635	case Classes::REMFROM: {
636	// do not split classes
637	} break;
638	default: assertf( false, "invalid mode" );
639	}
640	}
641
642	// finish merging bindings. This may fail, or may merge further classes
643	for ( const auto& entry : bedits ) {
644	interned_string key = entry.first;
645	const BEdit& e = entry.second;
646
647	// skip binding removals; the ADDTO merge has taken out all the new non-roots
648	if ( e.mode == Bindings::REM ) continue;
649	assertf( e.mode == Bindings::UPD \|\| e.mode == Bindings::INS, "inconsistent binding" );
650
651	// attempt binding update
652	interned_string root = classes->find( key );
653	BoundType ebound = bindings->get( root );
654	const BoundType& nbound = e.val;
655
656	if ( ebound.type && nbound.type ) {
657	// attempt to unify bound classes
658	Type* common = nullptr;
659	AssertionSet need, have;
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.

Download in other formats: