Context Navigation

source: src/ResolvExpr/Unify.cc @ 68f9c43

new-envwith_gc

Last change on this file since 68f9c43 was 68f9c43, checked in by Aaron Moss <a3moss@…>, 6 years ago
First pass at delete removal
Property mode set to `100644`
File size: 33.0 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	// Unify.cc --
8	//
9	// Author : Richard C. Bilson
10	// Created On : Sun May 17 12:27:10 2015
11	// Last Modified By : Peter A. Buhr
12	// Last Modified On : Thu Mar 16 16:22:54 2017
13	// Update Count : 42
14	//
15
16	#include <cassert> // for assertf, assert
17	#include <iterator> // for back_insert_iterator, back_inserter
18	#include <map> // for _Rb_tree_const_iterator, _Rb_tree_i...
19	#include <memory> // for unique_ptr
20	#include <set> // for set
21	#include <string> // for string, operator==, operator!=, bas...
22	#include <utility> // for pair
23
24	#include "Common/PassVisitor.h" // for PassVisitor
25	#include "FindOpenVars.h" // for findOpenVars
26	#include "Parser/LinkageSpec.h" // for C
27	#include "SynTree/Constant.h" // for Constant
28	#include "SynTree/Declaration.h" // for TypeDecl, TypeDecl::Data, Declarati...
29	#include "SynTree/Expression.h" // for TypeExpr, Expression, ConstantExpr
30	#include "SynTree/Mutator.h" // for Mutator
31	#include "SynTree/Type.h" // for Type, TypeInstType, FunctionType
32	#include "SynTree/Visitor.h" // for Visitor
33	#include "Tuples/Tuples.h" // for isTtype
34	#include "TypeEnvironment.h" // for EqvClass, AssertionSet, OpenVarSet
35	#include "Unify.h"
36	#include "typeops.h" // for flatten, occurs, commonType
37
38	namespace SymTab {
39	class Indexer;
40	} // namespace SymTab
41
42	// #define DEBUG
43
44	namespace ResolvExpr {
45
46	struct Unify : public WithShortCircuiting {
47	Unify( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
48
49	bool get_result() const { return result; }
50
51	void previsit( BaseSyntaxNode * ) { visit_children = false; }
52
53	void postvisit( VoidType * voidType );
54	void postvisit( BasicType * basicType );
55	void postvisit( PointerType * pointerType );
56	void postvisit( ArrayType * arrayType );
57	void postvisit( ReferenceType * refType );
58	void postvisit( FunctionType * functionType );
59	void postvisit( StructInstType * aggregateUseType );
60	void postvisit( UnionInstType * aggregateUseType );
61	void postvisit( EnumInstType * aggregateUseType );
62	void postvisit( TraitInstType * aggregateUseType );
63	void postvisit( TypeInstType * aggregateUseType );
64	void postvisit( TupleType * tupleType );
65	void postvisit( VarArgsType * varArgsType );
66	void postvisit( ZeroType * zeroType );
67	void postvisit( OneType * oneType );
68
69	private:
70	template< typename RefType > void handleRefType( RefType inst, Type other );
71	template< typename RefType > void handleGenericRefType( RefType inst, Type other );
72
73	bool result;
74	Type *type2; // inherited
75	TypeEnvironment &env;
76	AssertionSet &needAssertions;
77	AssertionSet &haveAssertions;
78	const OpenVarSet &openVars;
79	WidenMode widenMode;
80	const SymTab::Indexer &indexer;
81	};
82
83	/// Attempts an inexact unification of type1 and type2.
84	/// Returns false if no such unification; if the types can be unified, sets common (unless they unify exactly and have identical type qualifiers)
85	bool unifyInexact( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer, Type *&common );
86	bool unifyExact( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
87
88	bool typesCompatible( Type first, Type second, const SymTab::Indexer &indexer, const TypeEnvironment &env ) {
89	TypeEnvironment newEnv;
90	OpenVarSet openVars, closedVars; // added closedVars
91	AssertionSet needAssertions, haveAssertions;
92	Type newFirst = first->clone(), newSecond = second->clone();
93	env.apply( newFirst );
94	env.apply( newSecond );
95
96	// do we need to do this? Seems like we do, types should be able to be compatible if they
97	// have free variables that can unify
98	findOpenVars( newFirst, openVars, closedVars, needAssertions, haveAssertions, false );
99	findOpenVars( newSecond, openVars, closedVars, needAssertions, haveAssertions, true );
100
101	return unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
102	}
103
104	bool typesCompatibleIgnoreQualifiers( Type first, Type second, const SymTab::Indexer &indexer, const TypeEnvironment &env ) {
105	TypeEnvironment newEnv;
106	OpenVarSet openVars;
107	AssertionSet needAssertions, haveAssertions;
108	Type newFirst = first->clone(), newSecond = second->clone();
109	env.apply( newFirst );
110	env.apply( newSecond );
111	newFirst->get_qualifiers() = Type::Qualifiers();
112	newSecond->get_qualifiers() = Type::Qualifiers();
113	/// std::cerr << "first is ";
114	/// first->print( std::cerr );
115	/// std::cerr << std::endl << "second is ";
116	/// second->print( std::cerr );
117	/// std::cerr << std::endl << "newFirst is ";
118	/// newFirst->print( std::cerr );
119	/// std::cerr << std::endl << "newSecond is ";
120	/// newSecond->print( std::cerr );
121	/// std::cerr << std::endl;
122	return unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
123	}
124
125	bool isFtype( Type *type ) {
126	if ( dynamic_cast< FunctionType* >( type ) ) {
127	return true;
128	} else if ( TypeInstType typeInst = dynamic_cast< TypeInstType >( type ) ) {
129	return typeInst->get_isFtype();
130	} // if
131	return false;
132	}
133
134	bool tyVarCompatible( const TypeDecl::Data & data, Type *type ) {
135	switch ( data.kind ) {
136	case TypeDecl::Dtype:
137	// to bind to an object type variable, the type must not be a function type.
138	// if the type variable is specified to be a complete type then the incoming
139	// type must also be complete
140	// xxx - should this also check that type is not a tuple type and that it's not a ttype?
141	return ! isFtype( type ) && (! data.isComplete \|\| type->isComplete() );
142	case TypeDecl::Ftype:
143	return isFtype( type );
144	case TypeDecl::Ttype:
145	// ttype unifies with any tuple type
146	return dynamic_cast< TupleType * >( type ) \|\| Tuples::isTtype( type );
147	} // switch
148	return false;
149	}
150
151	bool bindVar( TypeInstType typeInst, Type other, const TypeDecl::Data & data, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
152	// remove references from other, so that type variables can only bind to value types
153	other = other->stripReferences();
154	OpenVarSet::const_iterator tyvar = openVars.find( typeInst->get_name() );
155	assert( tyvar != openVars.end() );
156	if ( ! tyVarCompatible( tyvar->second, other ) ) {
157	return false;
158	} // if
159	if ( occurs( other, typeInst->get_name(), env ) ) {
160	return false;
161	} // if
162	EqvClass curClass;
163	if ( env.lookup( typeInst->get_name(), curClass ) ) {
164	if ( curClass.type ) {
165	Type *common = 0;
166	// attempt to unify equivalence class type (which has qualifiers stripped, so they must be restored) with the type to bind to
167	std::unique_ptr< Type > newType( curClass.type->clone() );
168	newType->get_qualifiers() = typeInst->get_qualifiers();
169	if ( unifyInexact( newType.get(), other, env, needAssertions, haveAssertions, openVars, widenMode & WidenMode( curClass.allowWidening, true ), indexer, common ) ) {
170	if ( common ) {
171	common->get_qualifiers() = Type::Qualifiers();
172	curClass.type = common;
173	env.add( curClass );
174	} // if
175	return true;
176	} else {
177	return false;
178	} // if
179	} else {
180	curClass.type = other->clone();
181	curClass.type->get_qualifiers() = Type::Qualifiers();
182	curClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond;
183	env.add( curClass );
184	} // if
185	} else {
186	EqvClass newClass;
187	newClass.vars.insert( typeInst->get_name() );
188	newClass.type = other->clone();
189	newClass.type->get_qualifiers() = Type::Qualifiers();
190	newClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond;
191	newClass.data = data;
192	env.add( newClass );
193	} // if
194	return true;
195	}
196
197	bool bindVarToVar( TypeInstType var1, TypeInstType var2, const TypeDecl::Data & data, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
198	bool result = true;
199	EqvClass class1, class2;
200	bool hasClass1 = false, hasClass2 = false;
201	bool widen1 = false, widen2 = false;
202	Type type1 = 0, type2 = 0;
203
204	if ( env.lookup( var1->get_name(), class1 ) ) {
205	hasClass1 = true;
206	if ( class1.type ) {
207	if ( occurs( class1.type, var2->get_name(), env ) ) {
208	return false;
209	} // if
210	type1 = class1.type->clone();
211	} // if
212	widen1 = widenMode.widenFirst && class1.allowWidening;
213	} // if
214	if ( env.lookup( var2->get_name(), class2 ) ) {
215	hasClass2 = true;
216	if ( class2.type ) {
217	if ( occurs( class2.type, var1->get_name(), env ) ) {
218	return false;
219	} // if
220	type2 = class2.type->clone();
221	} // if
222	widen2 = widenMode.widenSecond && class2.allowWidening;
223	} // if
224
225	if ( type1 && type2 ) {
226	// std::cerr << "has type1 && type2" << std::endl;
227	WidenMode newWidenMode ( widen1, widen2 );
228	Type *common = 0;
229	if ( unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, newWidenMode, indexer, common ) ) {
230	class1.vars.insert( class2.vars.begin(), class2.vars.end() );
231	class1.allowWidening = widen1 && widen2;
232	if ( common ) {
233	common->get_qualifiers() = Type::Qualifiers();
234	class1.type = common;
235	} // if
236	env.add( class1 );
237	} else {
238	result = false;
239	} // if
240	} else if ( hasClass1 && hasClass2 ) {
241	if ( type1 ) {
242	class1.vars.insert( class2.vars.begin(), class2.vars.end() );
243	class1.allowWidening = widen1;
244	env.add( class1 );
245	} else {
246	class2.vars.insert( class1.vars.begin(), class1.vars.end() );
247	class2.allowWidening = widen2;
248	env.add( class2 );
249	} // if
250	} else if ( hasClass1 ) {
251	class1.vars.insert( var2->get_name() );
252	class1.allowWidening = widen1;
253	env.add( class1 );
254	} else if ( hasClass2 ) {
255	class2.vars.insert( var1->get_name() );
256	class2.allowWidening = widen2;
257	env.add( class2 );
258	} else {
259	EqvClass newClass;
260	newClass.vars.insert( var1->get_name() );
261	newClass.vars.insert( var2->get_name() );
262	newClass.allowWidening = widen1 && widen2;
263	newClass.data = data;
264	env.add( newClass );
265	} // if
266	return result;
267	}
268
269	bool unify( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
270	OpenVarSet closedVars;
271	findOpenVars( type1, openVars, closedVars, needAssertions, haveAssertions, false );
272	findOpenVars( type2, openVars, closedVars, needAssertions, haveAssertions, true );
273	Type *commonType = 0;
274	return unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType );
275	}
276
277	bool unify( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer, Type *&commonType ) {
278	OpenVarSet closedVars;
279	findOpenVars( type1, openVars, closedVars, needAssertions, haveAssertions, false );
280	findOpenVars( type2, openVars, closedVars, needAssertions, haveAssertions, true );
281	return unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType );
282	}
283
284	bool unifyExact( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
285	#ifdef DEBUG
286	TypeEnvironment debugEnv( env );
287	#endif
288	if ( type1->get_qualifiers() != type2->get_qualifiers() ) {
289	return false;
290	}
291
292	bool result;
293	TypeInstType var1 = dynamic_cast< TypeInstType >( type1 );
294	TypeInstType var2 = dynamic_cast< TypeInstType >( type2 );
295	OpenVarSet::const_iterator entry1, entry2;
296	if ( var1 ) {
297	entry1 = openVars.find( var1->get_name() );
298	} // if
299	if ( var2 ) {
300	entry2 = openVars.find( var2->get_name() );
301	} // if
302	bool isopen1 = var1 && ( entry1 != openVars.end() );
303	bool isopen2 = var2 && ( entry2 != openVars.end() );
304
305	if ( isopen1 && isopen2 && entry1->second == entry2->second ) {
306	result = bindVarToVar( var1, var2, entry1->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
307	} else if ( isopen1 ) {
308	result = bindVar( var1, type2, entry1->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
309	} else if ( isopen2 ) {
310	result = bindVar( var2, type1, entry2->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
311	} else {
312	PassVisitor<Unify> comparator( type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
313	type1->accept( comparator );
314	result = comparator.pass.get_result();
315	} // if
316	#ifdef DEBUG
317	std::cerr << "============ unifyExact" << std::endl;
318	std::cerr << "type1 is ";
319	type1->print( std::cerr );
320	std::cerr << std::endl << "type2 is ";
321	type2->print( std::cerr );
322	std::cerr << std::endl << "openVars are ";
323	printOpenVarSet( openVars, std::cerr, 8 );
324	std::cerr << std::endl << "input env is " << std::endl;
325	debugEnv.print( std::cerr, 8 );
326	std::cerr << std::endl << "result env is " << std::endl;
327	env.print( std::cerr, 8 );
328	std::cerr << "result is " << result << std::endl;
329	#endif
330	return result;
331	}
332
333	bool unifyExact( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
334	return unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
335	}
336
337	bool unifyInexact( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer, Type *&common ) {
338	Type::Qualifiers tq1 = type1->get_qualifiers(), tq2 = type2->get_qualifiers();
339	type1->get_qualifiers() = Type::Qualifiers();
340	type2->get_qualifiers() = Type::Qualifiers();
341	bool result;
342	#ifdef DEBUG
343	std::cerr << "unifyInexact type 1 is ";
344	type1->print( std::cerr );
345	std::cerr << " type 2 is ";
346	type2->print( std::cerr );
347	std::cerr << std::endl;
348	#endif
349	if ( ! unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer ) ) {
350	#ifdef DEBUG
351	std::cerr << "unifyInexact: no exact unification found" << std::endl;
352	#endif
353	if ( ( common = commonType( type1, type2, widenMode.widenFirst, widenMode.widenSecond, indexer, env, openVars ) ) ) {
354	common->get_qualifiers() = tq1 \| tq2;
355	#ifdef DEBUG
356	std::cerr << "unifyInexact: common type is ";
357	common->print( std::cerr );
358	std::cerr << std::endl;
359	#endif
360	result = true;
361	} else {
362	#ifdef DEBUG
363	std::cerr << "unifyInexact: no common type found" << std::endl;
364	#endif
365	result = false;
366	} // if
367	} else {
368	if ( tq1 != tq2 ) {
369	if ( ( tq1 > tq2 \|\| widenMode.widenFirst ) && ( tq2 > tq1 \|\| widenMode.widenSecond ) ) {
370	common = type1->clone();
371	common->get_qualifiers() = tq1 \| tq2;
372	result = true;
373	} else {
374	result = false;
375	} // if
376	} else {
377	common = type1->clone();
378	common->get_qualifiers() = tq1 \| tq2;
379	result = true;
380	} // if
381	} // if
382	type1->get_qualifiers() = tq1;
383	type2->get_qualifiers() = tq2;
384	return result;
385	}
386
387	Unify::Unify( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer )
388	: result( false ), type2( type2 ), env( env ), needAssertions( needAssertions ), haveAssertions( haveAssertions ), openVars( openVars ), widenMode( widenMode ), indexer( indexer ) {
389	}
390
391	void Unify::postvisit( __attribute__((unused)) VoidType *voidType) {
392	result = dynamic_cast< VoidType* >( type2 );
393	}
394
395	void Unify::postvisit(BasicType *basicType) {
396	if ( BasicType otherBasic = dynamic_cast< BasicType >( type2 ) ) {
397	result = basicType->get_kind() == otherBasic->get_kind();
398	} // if
399	}
400
401	void markAssertionSet( AssertionSet &assertions, DeclarationWithType *assert ) {
402	/// std::cerr << "assertion set is" << std::endl;
403	/// printAssertionSet( assertions, std::cerr, 8 );
404	/// std::cerr << "looking for ";
405	/// assert->print( std::cerr );
406	/// std::cerr << std::endl;
407	AssertionSet::iterator i = assertions.find( assert );
408	if ( i != assertions.end() ) {
409	/// std::cerr << "found it!" << std::endl;
410	i->second.isUsed = true;
411	} // if
412	}
413
414	void markAssertions( AssertionSet &assertion1, AssertionSet &assertion2, Type *type ) {
415	for ( std::list< TypeDecl* >::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
416	for ( std::list< DeclarationWithType* >::const_iterator assert = (tyvar)->get_assertions().begin(); assert != (tyvar)->get_assertions().end(); ++assert ) {
417	markAssertionSet( assertion1, *assert );
418	markAssertionSet( assertion2, *assert );
419	} // for
420	} // for
421	}
422
423	void Unify::postvisit(PointerType *pointerType) {
424	if ( PointerType otherPointer = dynamic_cast< PointerType >( type2 ) ) {
425	result = unifyExact( pointerType->get_base(), otherPointer->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
426	markAssertions( haveAssertions, needAssertions, pointerType );
427	markAssertions( haveAssertions, needAssertions, otherPointer );
428	} // if
429	}
430
431	void Unify::postvisit(ReferenceType *refType) {
432	if ( ReferenceType otherRef = dynamic_cast< ReferenceType >( type2 ) ) {
433	result = unifyExact( refType->get_base(), otherRef->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
434	markAssertions( haveAssertions, needAssertions, refType );
435	markAssertions( haveAssertions, needAssertions, otherRef );
436	} // if
437	}
438
439	void Unify::postvisit(ArrayType *arrayType) {
440	ArrayType otherArray = dynamic_cast< ArrayType >( type2 );
441	// to unify, array types must both be VLA or both not VLA
442	// and must both have a dimension expression or not have a dimension
443	if ( otherArray && arrayType->get_isVarLen() == otherArray->get_isVarLen() ) {
444
445	if ( ! arrayType->get_isVarLen() && ! otherArray->get_isVarLen() &&
446	arrayType->get_dimension() != 0 && otherArray->get_dimension() != 0 ) {
447	ConstantExpr * ce1 = dynamic_cast< ConstantExpr * >( arrayType->get_dimension() );
448	ConstantExpr * ce2 = dynamic_cast< ConstantExpr * >( otherArray->get_dimension() );
449	// see C11 Reference Manual 6.7.6.2.6
450	// two array types with size specifiers that are integer constant expressions are
451	// compatible if both size specifiers have the same constant value
452	if ( ce1 && ce2 ) {
453	Constant * c1 = ce1->get_constant();
454	Constant * c2 = ce2->get_constant();
455
456	if ( c1->get_value() != c2->get_value() ) {
457	// does not unify if the dimension is different
458	return;
459	}
460	}
461	}
462
463	result = unifyExact( arrayType->get_base(), otherArray->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
464	} // if
465	}
466
467	template< typename Iterator, typename Func >
468	std::unique_ptr<Type> combineTypes( Iterator begin, Iterator end, Func & toType ) {
469	std::list< Type * > types;
470	for ( ; begin != end; ++begin ) {
471	// it's guaranteed that a ttype variable will be bound to a flat tuple, so ensure that this results in a flat tuple
472	flatten( toType( *begin ), back_inserter( types ) );
473	}
474	return std::unique_ptr<Type>( new TupleType( Type::Qualifiers(), types ) );
475	}
476
477	template< typename Iterator1, typename Iterator2 >
478	bool unifyDeclList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
479	auto get_type = [](DeclarationWithType * dwt){ return dwt->get_type(); };
480	for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) {
481	Type * t1 = (*list1Begin)->get_type();
482	Type * t2 = (*list2Begin)->get_type();
483	bool isTtype1 = Tuples::isTtype( t1 );
484	bool isTtype2 = Tuples::isTtype( t2 );
485	// xxx - assumes ttype must be last parameter
486	// xxx - there may be a nice way to refactor this, but be careful because the argument positioning might matter in some cases.
487	if ( isTtype1 && ! isTtype2 ) {
488	// combine all of the things in list2, then unify
489	return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
490	} else if ( isTtype2 && ! isTtype1 ) {
491	// combine all of the things in list1, then unify
492	return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
493	} else if ( ! unifyExact( t1, t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ) ) {
494	return false;
495	} // if
496	} // for
497	// may get to the end of one argument list before the end of the other. This is only okay when the other is a ttype
498	if ( list1Begin != list1End ) {
499	// try unifying empty tuple type with ttype
500	Type * t1 = (*list1Begin)->get_type();
501	if ( Tuples::isTtype( t1 ) ) {
502	return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
503	} else return false;
504	} else if ( list2Begin != list2End ) {
505	// try unifying empty tuple type with ttype
506	Type * t2 = (*list2Begin)->get_type();
507	if ( Tuples::isTtype( t2 ) ) {
508	return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
509	} else return false;
510	} else {
511	return true;
512	} // if
513	}
514
515	/// Finds ttypes and replaces them with their expansion, if known.
516	/// This needs to be done so that satisfying ttype assertions is easier.
517	/// If this isn't done then argument lists can have wildly different
518	/// size and structure, when they should be compatible.
519	struct TtypeExpander : public WithShortCircuiting {
520	TypeEnvironment & tenv;
521	TtypeExpander( TypeEnvironment & tenv ) : tenv( tenv ) {}
522	void premutate( TypeInstType * ) { visit_children = false; }
523	Type * postmutate( TypeInstType * typeInst ) {
524	EqvClass eqvClass;
525	if ( tenv.lookup( typeInst->get_name(), eqvClass ) ) {
526	if ( eqvClass.data.kind == TypeDecl::Ttype ) {
527	// expand ttype parameter into its actual type
528	if ( eqvClass.type ) {
529	return eqvClass.type->clone();
530	}
531	}
532	}
533	return typeInst;
534	}
535	};
536
537	/// flattens a list of declarations, so that each tuple type has a single declaration.
538	/// makes use of TtypeExpander to ensure ttypes are flat as well.
539	void flattenList( std::list< DeclarationWithType * > src, std::list< DeclarationWithType * > & dst, TypeEnvironment & env ) {
540	dst.clear();
541	for ( DeclarationWithType * dcl : src ) {
542	PassVisitor<TtypeExpander> expander( env );
543	dcl->acceptMutator( expander );
544	std::list< Type * > types;
545	flatten( dcl->get_type(), back_inserter( types ) );
546	for ( Type * t : types ) {
547	// outermost const, volatile, _Atomic qualifiers in parameters should not play a role in the unification of function types, since they do not determine whether a function is callable.
548	// Note: MUST consider at least mutex qualifier, since functions can be overloaded on outermost mutex and a mutex function has different requirements than a non-mutex function.
549	t->get_qualifiers() -= Type::Qualifiers(Type::Const \| Type::Volatile \| Type::Atomic);
550
551	dst.push_back( new ObjectDecl( "", Type::StorageClasses(), LinkageSpec::C, nullptr, t, nullptr ) );
552	}
553	}
554	}
555
556	void Unify::postvisit(FunctionType *functionType) {
557	FunctionType otherFunction = dynamic_cast< FunctionType >( type2 );
558	if ( otherFunction && functionType->get_isVarArgs() == otherFunction->get_isVarArgs() ) {
559	// flatten the parameter lists for both functions so that tuple structure
560	// doesn't affect unification. Must be a clone so that the types don't change.
561	std::unique_ptr<FunctionType> flatFunc( functionType->clone() );
562	std::unique_ptr<FunctionType> flatOther( otherFunction->clone() );
563	flattenList( flatFunc->get_parameters(), flatFunc->get_parameters(), env );
564	flattenList( flatOther->get_parameters(), flatOther->get_parameters(), env );
565
566	// sizes don't have to match if ttypes are involved; need to be more precise wrt where the ttype is to prevent errors
567	if ( (flatFunc->parameters.size() == flatOther->parameters.size() && flatFunc->returnVals.size() == flatOther->returnVals.size()) \|\| flatFunc->isTtype() \|\| flatOther->isTtype() ) {
568	if ( unifyDeclList( flatFunc->parameters.begin(), flatFunc->parameters.end(), flatOther->parameters.begin(), flatOther->parameters.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
569	if ( unifyDeclList( flatFunc->returnVals.begin(), flatFunc->returnVals.end(), flatOther->returnVals.begin(), flatOther->returnVals.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
570
571	// the original types must be used in mark assertions, since pointer comparisons are used
572	markAssertions( haveAssertions, needAssertions, functionType );
573	markAssertions( haveAssertions, needAssertions, otherFunction );
574
575	result = true;
576	} // if
577	} // if
578	} // if
579	} // if
580	}
581
582	template< typename RefType >
583	void Unify::handleRefType( RefType inst, Type other ) {
584	// check that other type is compatible and named the same
585	RefType otherStruct = dynamic_cast< RefType >( other );
586	result = otherStruct && inst->name == otherStruct->name;
587	}
588
589	template< typename RefType >
590	void Unify::handleGenericRefType( RefType inst, Type other ) {
591	// Check that other type is compatible and named the same
592	handleRefType( inst, other );
593	if ( ! result ) return;
594	// Check that parameters of types unify, if any
595	std::list< Expression* > params = inst->parameters;
596	std::list< Expression* > otherParams = ((RefType*)other)->parameters;
597
598	std::list< Expression* >::const_iterator it = params.begin(), jt = otherParams.begin();
599	for ( ; it != params.end() && jt != otherParams.end(); ++it, ++jt ) {
600	TypeExpr param = dynamic_cast< TypeExpr >(*it);
601	assertf(param, "Aggregate parameters should be type expressions");
602	TypeExpr otherParam = dynamic_cast< TypeExpr >(*jt);
603	assertf(otherParam, "Aggregate parameters should be type expressions");
604
605	Type* paramTy = param->get_type();
606	Type* otherParamTy = otherParam->get_type();
607
608	bool tupleParam = Tuples::isTtype( paramTy );
609	bool otherTupleParam = Tuples::isTtype( otherParamTy );
610
611	if ( tupleParam && otherTupleParam ) {
612	++it; ++jt; // skip ttype parameters for break
613	} else if ( tupleParam ) {
614	// bundle other parameters into tuple to match
615	std::list< Type * > binderTypes;
616
617	do {
618	binderTypes.push_back( otherParam->get_type()->clone() );
619	++jt;
620
621	if ( jt == otherParams.end() ) break;
622
623	otherParam = dynamic_cast< TypeExpr* >(*jt);
624	assertf(otherParam, "Aggregate parameters should be type expressions");
625	} while (true);
626
627	otherParamTy = new TupleType{ paramTy->get_qualifiers(), binderTypes };
628	++it; // skip ttype parameter for break
629	} else if ( otherTupleParam ) {
630	// bundle parameters into tuple to match other
631	std::list< Type * > binderTypes;
632
633	do {
634	binderTypes.push_back( param->get_type()->clone() );
635	++it;
636
637	if ( it == params.end() ) break;
638
639	param = dynamic_cast< TypeExpr* >(*it);
640	assertf(param, "Aggregate parameters should be type expressions");
641	} while (true);
642
643	paramTy = new TupleType{ otherParamTy->get_qualifiers(), binderTypes };
644	++jt; // skip ttype parameter for break
645	}
646
647	if ( ! unifyExact( paramTy, otherParamTy, env, needAssertions, haveAssertions, openVars, WidenMode(false, false), indexer ) ) {
648	result = false;
649	return;
650	}
651
652	// ttype parameter should be last
653	if ( tupleParam \|\| otherTupleParam ) break;
654	}
655	result = ( it == params.end() && jt == otherParams.end() );
656	}
657
658	void Unify::postvisit(StructInstType *structInst) {
659	handleGenericRefType( structInst, type2 );
660	}
661
662	void Unify::postvisit(UnionInstType *unionInst) {
663	handleGenericRefType( unionInst, type2 );
664	}
665
666	void Unify::postvisit(EnumInstType *enumInst) {
667	handleRefType( enumInst, type2 );
668	}
669
670	void Unify::postvisit(TraitInstType *contextInst) {
671	handleRefType( contextInst, type2 );
672	}
673
674	void Unify::postvisit(TypeInstType *typeInst) {
675	assert( openVars.find( typeInst->get_name() ) == openVars.end() );
676	TypeInstType otherInst = dynamic_cast< TypeInstType >( type2 );
677	if ( otherInst && typeInst->get_name() == otherInst->get_name() ) {
678	result = true;
679	/// } else {
680	/// NamedTypeDecl *nt = indexer.lookupType( typeInst->get_name() );
681	/// if ( nt ) {
682	/// TypeDecl type = dynamic_cast< TypeDecl >( nt );
683	/// assert( type );
684	/// if ( type->get_base() ) {
685	/// result = unifyExact( type->get_base(), typeInst, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
686	/// }
687	/// }
688	} // if
689	}
690
691	template< typename Iterator1, typename Iterator2 >
692	bool unifyList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
693	auto get_type = [](Type * t) { return t; };
694	for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) {
695	Type * t1 = *list1Begin;
696	Type * t2 = *list2Begin;
697	bool isTtype1 = Tuples::isTtype( t1 );
698	bool isTtype2 = Tuples::isTtype( t2 );
699	// xxx - assumes ttype must be last parameter
700	// xxx - there may be a nice way to refactor this, but be careful because the argument positioning might matter in some cases.
701	if ( isTtype1 && ! isTtype2 ) {
702	// combine all of the things in list2, then unify
703	return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
704	} else if ( isTtype2 && ! isTtype1 ) {
705	// combine all of the things in list1, then unify
706	return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
707	} else if ( ! unifyExact( t1, t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ) ) {
708	return false;
709	} // if
710
711	} // for
712	if ( list1Begin != list1End ) {
713	// try unifying empty tuple type with ttype
714	Type * t1 = *list1Begin;
715	if ( Tuples::isTtype( t1 ) ) {
716	return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
717	} else return false;
718	} else if ( list2Begin != list2End ) {
719	// try unifying empty tuple type with ttype
720	Type * t2 = *list2Begin;
721	if ( Tuples::isTtype( t2 ) ) {
722	return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
723	} else return false;
724	} else {
725	return true;
726	} // if
727	}
728
729	void Unify::postvisit(TupleType *tupleType) {
730	if ( TupleType otherTuple = dynamic_cast< TupleType >( type2 ) ) {
731	std::unique_ptr<TupleType> flat1( tupleType->clone() );
732	std::unique_ptr<TupleType> flat2( otherTuple->clone() );
733	std::list<Type *> types1, types2;
734
735	PassVisitor<TtypeExpander> expander( env );
736	flat1->acceptMutator( expander );
737	flat2->acceptMutator( expander );
738
739	flatten( flat1.get(), back_inserter( types1 ) );
740	flatten( flat2.get(), back_inserter( types2 ) );
741
742	result = unifyList( types1.begin(), types1.end(), types2.begin(), types2.end(), env, needAssertions, haveAssertions, openVars, indexer );
743	} // if
744	}
745
746	void Unify::postvisit( __attribute__((unused)) VarArgsType *varArgsType ) {
747	result = dynamic_cast< VarArgsType* >( type2 );
748	}
749
750	void Unify::postvisit( __attribute__((unused)) ZeroType *zeroType ) {
751	result = dynamic_cast< ZeroType* >( type2 );
752	}
753
754	void Unify::postvisit( __attribute__((unused)) OneType *oneType ) {
755	result = dynamic_cast< OneType* >( type2 );
756	}
757
758	// xxx - compute once and store in the FunctionType?
759	Type * extractResultType( FunctionType * function ) {
760	if ( function->get_returnVals().size() == 0 ) {
761	return new VoidType( Type::Qualifiers() );
762	} else if ( function->get_returnVals().size() == 1 ) {
763	return function->get_returnVals().front()->get_type()->clone();
764	} else {
765	std::list< Type * > types;
766	for ( DeclarationWithType * decl : function->get_returnVals() ) {
767	types.push_back( decl->get_type()->clone() );
768	} // for
769	return new TupleType( Type::Qualifiers(), types );
770	}
771	}
772	} // namespace ResolvExpr
773
774	// Local Variables: //
775	// tab-width: 4 //
776	// mode: c++ //
777	// compile-command: "make install" //
778	// End: //

Note: See TracBrowser for help on using the repository browser.

Download in other formats: