Context Navigation

source: src/ResolvExpr/Unify.cc @ 7de2affc

ADTast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum

Last change on this file since 7de2affc was 302ef2a, checked in by Fangren Yu <f37yu@…>, 4 years ago
smart pointer memory safety
Property mode set to `100644`
File size: 48.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 : Fri Dec 13 23:43:05 2019
13	// Update Count : 46
14	//
15
16	#include "Unify.h"
17
18	#include <cassert> // for assertf, assert
19	#include <iterator> // for back_insert_iterator, back_inserter
20	#include <map> // for _Rb_tree_const_iterator, _Rb_tree_i...
21	#include <memory> // for unique_ptr
22	#include <set> // for set
23	#include <string> // for string, operator==, operator!=, bas...
24	#include <utility> // for pair, move
25	#include <vector>
26
27	#include "AST/Copy.hpp"
28	#include "AST/Decl.hpp"
29	#include "AST/Node.hpp"
30	#include "AST/Pass.hpp"
31	#include "AST/Print.hpp"
32	#include "AST/Type.hpp"
33	#include "AST/TypeEnvironment.hpp"
34	#include "Common/PassVisitor.h" // for PassVisitor
35	#include "FindOpenVars.h" // for findOpenVars
36	#include "SynTree/LinkageSpec.h" // for C
37	#include "SynTree/Constant.h" // for Constant
38	#include "SynTree/Declaration.h" // for TypeDecl, TypeDecl::Data, Declarati...
39	#include "SynTree/Expression.h" // for TypeExpr, Expression, ConstantExpr
40	#include "SynTree/Mutator.h" // for Mutator
41	#include "SynTree/Type.h" // for Type, TypeInstType, FunctionType
42	#include "SynTree/Visitor.h" // for Visitor
43	#include "Tuples/Tuples.h" // for isTtype
44	#include "TypeEnvironment.h" // for EqvClass, AssertionSet, OpenVarSet
45	#include "typeops.h" // for flatten, occurs, commonType
46
47	namespace ast {
48	class SymbolTable;
49	}
50
51	namespace SymTab {
52	class Indexer;
53	} // namespace SymTab
54
55	// #define DEBUG
56
57	namespace ResolvExpr {
58
59	struct Unify_old : public WithShortCircuiting {
60	Unify_old( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer );
61
62	bool get_result() const { return result; }
63
64	void previsit( BaseSyntaxNode * ) { visit_children = false; }
65
66	void postvisit( VoidType * voidType );
67	void postvisit( BasicType * basicType );
68	void postvisit( PointerType * pointerType );
69	void postvisit( ArrayType * arrayType );
70	void postvisit( ReferenceType * refType );
71	void postvisit( FunctionType * functionType );
72	void postvisit( StructInstType * aggregateUseType );
73	void postvisit( UnionInstType * aggregateUseType );
74	void postvisit( EnumInstType * aggregateUseType );
75	void postvisit( TraitInstType * aggregateUseType );
76	void postvisit( TypeInstType * aggregateUseType );
77	void postvisit( TupleType * tupleType );
78	void postvisit( VarArgsType * varArgsType );
79	void postvisit( ZeroType * zeroType );
80	void postvisit( OneType * oneType );
81
82	private:
83	template< typename RefType > void handleRefType( RefType inst, Type other );
84	template< typename RefType > void handleGenericRefType( RefType inst, Type other );
85
86	bool result;
87	Type *type2; // inherited
88	TypeEnvironment &env;
89	AssertionSet &needAssertions;
90	AssertionSet &haveAssertions;
91	const OpenVarSet &openVars;
92	WidenMode widen;
93	const SymTab::Indexer &indexer;
94	};
95
96	/// Attempts an inexact unification of type1 and type2.
97	/// Returns false if no such unification; if the types can be unified, sets common (unless they unify exactly and have identical type qualifiers)
98	bool unifyInexact( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer, Type *&common );
99	bool unifyExact( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer );
100
101	bool unifyExact(
102	const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env,
103	ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
104	WidenMode widen, const ast::SymbolTable & symtab );
105
106	bool typesCompatible( const Type * first, const Type * second, const SymTab::Indexer & indexer, const TypeEnvironment & env ) {
107	TypeEnvironment newEnv;
108	OpenVarSet openVars, closedVars; // added closedVars
109	AssertionSet needAssertions, haveAssertions;
110	Type * newFirst = first->clone(), * newSecond = second->clone();
111	env.apply( newFirst );
112	env.apply( newSecond );
113
114	// do we need to do this? Seems like we do, types should be able to be compatible if they
115	// have free variables that can unify
116	findOpenVars( newFirst, openVars, closedVars, needAssertions, haveAssertions, false );
117	findOpenVars( newSecond, openVars, closedVars, needAssertions, haveAssertions, true );
118
119	bool result = unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
120	delete newFirst;
121	delete newSecond;
122	return result;
123	}
124
125	bool typesCompatible(
126	const ast::Type * first, const ast::Type * second, const ast::SymbolTable & symtab,
127	const ast::TypeEnvironment & env ) {
128	ast::TypeEnvironment newEnv;
129	ast::OpenVarSet open, closed;
130	ast::AssertionSet need, have;
131
132	ast::ptr<ast::Type> newFirst{ first }, newSecond{ second };
133	env.apply( newFirst );
134	env.apply( newSecond );
135
136	findOpenVars( newFirst, open, closed, need, have, FirstClosed );
137	findOpenVars( newSecond, open, closed, need, have, FirstOpen );
138
139	return unifyExact(newFirst, newSecond, newEnv, need, have, open, noWiden(), symtab );
140	}
141
142	bool typesCompatibleIgnoreQualifiers( const Type * first, const Type * second, const SymTab::Indexer &indexer, const TypeEnvironment &env ) {
143	TypeEnvironment newEnv;
144	OpenVarSet openVars;
145	AssertionSet needAssertions, haveAssertions;
146	Type newFirst = first->clone(), newSecond = second->clone();
147	env.apply( newFirst );
148	env.apply( newSecond );
149	newFirst->get_qualifiers() = Type::Qualifiers();
150	newSecond->get_qualifiers() = Type::Qualifiers();
151
152	bool result = unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
153	delete newFirst;
154	delete newSecond;
155	return result;
156	}
157
158	bool typesCompatibleIgnoreQualifiers(
159	const ast::Type * first, const ast::Type * second, const ast::SymbolTable & symtab,
160	const ast::TypeEnvironment & env ) {
161	ast::TypeEnvironment newEnv;
162	ast::OpenVarSet open;
163	ast::AssertionSet need, have;
164
165	ast::Type * newFirst = shallowCopy( first );
166	ast::Type * newSecond = shallowCopy( second );
167	newFirst ->qualifiers = {};
168	newSecond->qualifiers = {};
169	ast::ptr< ast::Type > t1_(newFirst );
170	ast::ptr< ast::Type > t2_(newSecond);
171
172	ast::ptr< ast::Type > subFirst = env.apply(newFirst).node;
173	ast::ptr< ast::Type > subSecond = env.apply(newSecond).node;
174
175	return unifyExact(
176	subFirst,
177	subSecond,
178	newEnv, need, have, open, noWiden(), symtab );
179	}
180
181	bool unify( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
182	OpenVarSet closedVars;
183	findOpenVars( type1, openVars, closedVars, needAssertions, haveAssertions, false );
184	findOpenVars( type2, openVars, closedVars, needAssertions, haveAssertions, true );
185	Type *commonType = 0;
186	if ( unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType ) ) {
187	if ( commonType ) {
188	delete commonType;
189	} // if
190	return true;
191	} else {
192	return false;
193	} // if
194	}
195
196	bool unify( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer, Type *&commonType ) {
197	OpenVarSet closedVars;
198	findOpenVars( type1, openVars, closedVars, needAssertions, haveAssertions, false );
199	findOpenVars( type2, openVars, closedVars, needAssertions, haveAssertions, true );
200	return unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType );
201	}
202
203	bool unifyExact( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ) {
204	#ifdef DEBUG
205	TypeEnvironment debugEnv( env );
206	#endif
207	if ( type1->get_qualifiers() != type2->get_qualifiers() ) {
208	return false;
209	}
210
211	bool result;
212	TypeInstType var1 = dynamic_cast< TypeInstType >( type1 );
213	TypeInstType var2 = dynamic_cast< TypeInstType >( type2 );
214	OpenVarSet::const_iterator entry1, entry2;
215	if ( var1 ) {
216	entry1 = openVars.find( var1->get_name() );
217	} // if
218	if ( var2 ) {
219	entry2 = openVars.find( var2->get_name() );
220	} // if
221	bool isopen1 = var1 && ( entry1 != openVars.end() );
222	bool isopen2 = var2 && ( entry2 != openVars.end() );
223
224	if ( isopen1 && isopen2 ) {
225	if ( entry1->second.kind != entry2->second.kind ) {
226	result = false;
227	} else {
228	result = env.bindVarToVar(
229	var1, var2, TypeDecl::Data{ entry1->second, entry2->second }, needAssertions,
230	haveAssertions, openVars, widen, indexer );
231	}
232	} else if ( isopen1 ) {
233	result = env.bindVar( var1, type2, entry1->second, needAssertions, haveAssertions, openVars, widen, indexer );
234	} else if ( isopen2 ) { // TODO: swap widen values in call, since type positions are flipped?
235	result = env.bindVar( var2, type1, entry2->second, needAssertions, haveAssertions, openVars, widen, indexer );
236	} else {
237	PassVisitor<Unify_old> comparator( type2, env, needAssertions, haveAssertions, openVars, widen, indexer );
238	type1->accept( comparator );
239	result = comparator.pass.get_result();
240	} // if
241	#ifdef DEBUG
242	std::cerr << "============ unifyExact" << std::endl;
243	std::cerr << "type1 is ";
244	type1->print( std::cerr );
245	std::cerr << std::endl << "type2 is ";
246	type2->print( std::cerr );
247	std::cerr << std::endl << "openVars are ";
248	printOpenVarSet( openVars, std::cerr, 8 );
249	std::cerr << std::endl << "input env is " << std::endl;
250	debugEnv.print( std::cerr, 8 );
251	std::cerr << std::endl << "result env is " << std::endl;
252	env.print( std::cerr, 8 );
253	std::cerr << "result is " << result << std::endl;
254	#endif
255	return result;
256	}
257
258	bool unifyExact( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
259	return unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
260	}
261
262	bool unifyInexact( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer, Type *&common ) {
263	Type::Qualifiers tq1 = type1->get_qualifiers(), tq2 = type2->get_qualifiers();
264	type1->get_qualifiers() = Type::Qualifiers();
265	type2->get_qualifiers() = Type::Qualifiers();
266	bool result;
267	#ifdef DEBUG
268	std::cerr << "unifyInexact type 1 is ";
269	type1->print( std::cerr );
270	std::cerr << " type 2 is ";
271	type2->print( std::cerr );
272	std::cerr << std::endl;
273	#endif
274	if ( ! unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, widen, indexer ) ) {
275	#ifdef DEBUG
276	std::cerr << "unifyInexact: no exact unification found" << std::endl;
277	#endif
278	if ( ( common = commonType( type1, type2, widen.first, widen.second, indexer, env, openVars ) ) ) {
279	common->tq = tq1.unify( tq2 );
280	#ifdef DEBUG
281	std::cerr << "unifyInexact: common type is ";
282	common->print( std::cerr );
283	std::cerr << std::endl;
284	#endif
285	result = true;
286	} else {
287	#ifdef DEBUG
288	std::cerr << "unifyInexact: no common type found" << std::endl;
289	#endif
290	result = false;
291	} // if
292	} else {
293	if ( tq1 != tq2 ) {
294	if ( ( tq1 > tq2 \|\| widen.first ) && ( tq2 > tq1 \|\| widen.second ) ) {
295	common = type1->clone();
296	common->tq = tq1.unify( tq2 );
297	result = true;
298	} else {
299	result = false;
300	} // if
301	} else {
302	common = type1->clone();
303	common->tq = tq1.unify( tq2 );
304	result = true;
305	} // if
306	} // if
307	type1->get_qualifiers() = tq1;
308	type2->get_qualifiers() = tq2;
309	return result;
310	}
311
312	Unify_old::Unify_old( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer )
313	: result( false ), type2( type2 ), env( env ), needAssertions( needAssertions ), haveAssertions( haveAssertions ), openVars( openVars ), widen( widen ), indexer( indexer ) {
314	}
315
316	void Unify_old::postvisit( __attribute__((unused)) VoidType *voidType) {
317	result = dynamic_cast< VoidType* >( type2 );
318	}
319
320	void Unify_old::postvisit(BasicType *basicType) {
321	if ( BasicType otherBasic = dynamic_cast< BasicType >( type2 ) ) {
322	result = basicType->get_kind() == otherBasic->get_kind();
323	} // if
324	}
325
326	void markAssertionSet( AssertionSet &assertions, DeclarationWithType *assert ) {
327	AssertionSet::iterator i = assertions.find( assert );
328	if ( i != assertions.end() ) {
329	i->second.isUsed = true;
330	} // if
331	}
332
333	void markAssertions( AssertionSet &assertion1, AssertionSet &assertion2, Type *type ) {
334	for ( std::list< TypeDecl* >::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
335	for ( std::list< DeclarationWithType* >::const_iterator assert = (tyvar)->get_assertions().begin(); assert != (tyvar)->get_assertions().end(); ++assert ) {
336	markAssertionSet( assertion1, *assert );
337	markAssertionSet( assertion2, *assert );
338	} // for
339	} // for
340	}
341
342	void Unify_old::postvisit(PointerType *pointerType) {
343	if ( PointerType otherPointer = dynamic_cast< PointerType >( type2 ) ) {
344	result = unifyExact( pointerType->get_base(), otherPointer->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
345	markAssertions( haveAssertions, needAssertions, pointerType );
346	markAssertions( haveAssertions, needAssertions, otherPointer );
347	} // if
348	}
349
350	void Unify_old::postvisit(ReferenceType *refType) {
351	if ( ReferenceType otherRef = dynamic_cast< ReferenceType >( type2 ) ) {
352	result = unifyExact( refType->get_base(), otherRef->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
353	markAssertions( haveAssertions, needAssertions, refType );
354	markAssertions( haveAssertions, needAssertions, otherRef );
355	} // if
356	}
357
358	void Unify_old::postvisit(ArrayType *arrayType) {
359	ArrayType otherArray = dynamic_cast< ArrayType >( type2 );
360	// to unify, array types must both be VLA or both not VLA
361	// and must both have a dimension expression or not have a dimension
362	if ( otherArray && arrayType->get_isVarLen() == otherArray->get_isVarLen() ) {
363
364	if ( ! arrayType->get_isVarLen() && ! otherArray->get_isVarLen() &&
365	arrayType->get_dimension() != 0 && otherArray->get_dimension() != 0 ) {
366	ConstantExpr * ce1 = dynamic_cast< ConstantExpr * >( arrayType->get_dimension() );
367	ConstantExpr * ce2 = dynamic_cast< ConstantExpr * >( otherArray->get_dimension() );
368	// see C11 Reference Manual 6.7.6.2.6
369	// two array types with size specifiers that are integer constant expressions are
370	// compatible if both size specifiers have the same constant value
371	if ( ce1 && ce2 ) {
372	Constant * c1 = ce1->get_constant();
373	Constant * c2 = ce2->get_constant();
374
375	if ( c1->get_value() != c2->get_value() ) {
376	// does not unify if the dimension is different
377	return;
378	}
379	}
380	}
381
382	result = unifyExact( arrayType->get_base(), otherArray->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
383	} // if
384	}
385
386	template< typename Iterator, typename Func >
387	std::unique_ptr<Type> combineTypes( Iterator begin, Iterator end, Func & toType ) {
388	std::list< Type * > types;
389	for ( ; begin != end; ++begin ) {
390	// it's guaranteed that a ttype variable will be bound to a flat tuple, so ensure that this results in a flat tuple
391	flatten( toType( *begin ), back_inserter( types ) );
392	}
393	return std::unique_ptr<Type>( new TupleType( Type::Qualifiers(), types ) );
394	}
395
396	template< typename Iterator1, typename Iterator2 >
397	bool unifyTypeList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
398	auto get_type = [](DeclarationWithType * dwt){ return dwt->get_type(); };
399	for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) {
400	Type * t1 = (*list1Begin)->get_type();
401	Type * t2 = (*list2Begin)->get_type();
402	bool isTtype1 = Tuples::isTtype( t1 );
403	bool isTtype2 = Tuples::isTtype( t2 );
404	// xxx - assumes ttype must be last parameter
405	// xxx - there may be a nice way to refactor this, but be careful because the argument positioning might matter in some cases.
406	if ( isTtype1 && ! isTtype2 ) {
407	// combine all of the things in list2, then unify
408	return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
409	} else if ( isTtype2 && ! isTtype1 ) {
410	// combine all of the things in list1, then unify
411	return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
412	} else if ( ! unifyExact( t1, t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ) ) {
413	return false;
414	} // if
415	} // for
416	// 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
417	if ( list1Begin != list1End ) {
418	// try unifying empty tuple type with ttype
419	Type * t1 = (*list1Begin)->get_type();
420	if ( Tuples::isTtype( t1 ) ) {
421	return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
422	} else return false;
423	} else if ( list2Begin != list2End ) {
424	// try unifying empty tuple type with ttype
425	Type * t2 = (*list2Begin)->get_type();
426	if ( Tuples::isTtype( t2 ) ) {
427	return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
428	} else return false;
429	} else {
430	return true;
431	} // if
432	}
433
434	/// Finds ttypes and replaces them with their expansion, if known.
435	/// This needs to be done so that satisfying ttype assertions is easier.
436	/// If this isn't done then argument lists can have wildly different
437	/// size and structure, when they should be compatible.
438	struct TtypeExpander_old : public WithShortCircuiting {
439	TypeEnvironment & tenv;
440	TtypeExpander_old( TypeEnvironment & tenv ) : tenv( tenv ) {}
441	void premutate( TypeInstType * ) { visit_children = false; }
442	Type * postmutate( TypeInstType * typeInst ) {
443	if ( const EqvClass *eqvClass = tenv.lookup( typeInst->get_name() ) ) {
444	// expand ttype parameter into its actual type
445	if ( eqvClass->data.kind == TypeDecl::Ttype && eqvClass->type ) {
446	delete typeInst;
447	return eqvClass->type->clone();
448	}
449	}
450	return typeInst;
451	}
452	};
453
454	/// flattens a list of declarations, so that each tuple type has a single declaration.
455	/// makes use of TtypeExpander to ensure ttypes are flat as well.
456	void flattenList( std::list< DeclarationWithType * > src, std::list< DeclarationWithType * > & dst, TypeEnvironment & env ) {
457	dst.clear();
458	for ( DeclarationWithType * dcl : src ) {
459	PassVisitor<TtypeExpander_old> expander( env );
460	dcl->acceptMutator( expander );
461	std::list< Type * > types;
462	flatten( dcl->get_type(), back_inserter( types ) );
463	for ( Type * t : types ) {
464	// 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.
465	// 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.
466	t->get_qualifiers() -= Type::Qualifiers(Type::Const \| Type::Volatile \| Type::Atomic);
467
468	dst.push_back( new ObjectDecl( "", Type::StorageClasses(), LinkageSpec::C, nullptr, t, nullptr ) );
469	}
470	delete dcl;
471	}
472	}
473
474	void Unify_old::postvisit(FunctionType *functionType) {
475	FunctionType otherFunction = dynamic_cast< FunctionType >( type2 );
476	if ( otherFunction && functionType->get_isVarArgs() == otherFunction->get_isVarArgs() ) {
477	// flatten the parameter lists for both functions so that tuple structure
478	// doesn't affect unification. Must be a clone so that the types don't change.
479	std::unique_ptr<FunctionType> flatFunc( functionType->clone() );
480	std::unique_ptr<FunctionType> flatOther( otherFunction->clone() );
481	flattenList( flatFunc->get_parameters(), flatFunc->get_parameters(), env );
482	flattenList( flatOther->get_parameters(), flatOther->get_parameters(), env );
483
484	// sizes don't have to match if ttypes are involved; need to be more precise wrt where the ttype is to prevent errors
485	if (
486	(flatFunc->parameters.size() == flatOther->parameters.size() &&
487	flatFunc->returnVals.size() == flatOther->returnVals.size())
488	\|\| flatFunc->isTtype()
489	\|\| flatOther->isTtype()
490	) {
491	if ( unifyTypeList( flatFunc->parameters.begin(), flatFunc->parameters.end(), flatOther->parameters.begin(), flatOther->parameters.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
492	if ( unifyTypeList( flatFunc->returnVals.begin(), flatFunc->returnVals.end(), flatOther->returnVals.begin(), flatOther->returnVals.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
493
494	// the original types must be used in mark assertions, since pointer comparisons are used
495	markAssertions( haveAssertions, needAssertions, functionType );
496	markAssertions( haveAssertions, needAssertions, otherFunction );
497
498	result = true;
499	} // if
500	} // if
501	} // if
502	} // if
503	}
504
505	template< typename RefType >
506	void Unify_old::handleRefType( RefType inst, Type other ) {
507	// check that other type is compatible and named the same
508	RefType otherStruct = dynamic_cast< RefType >( other );
509	result = otherStruct && inst->name == otherStruct->name;
510	}
511
512	template< typename RefType >
513	void Unify_old::handleGenericRefType( RefType inst, Type other ) {
514	// Check that other type is compatible and named the same
515	handleRefType( inst, other );
516	if ( ! result ) return;
517	// Check that parameters of types unify, if any
518	std::list< Expression* > params = inst->parameters;
519	std::list< Expression* > otherParams = ((RefType*)other)->parameters;
520
521	std::list< Expression* >::const_iterator it = params.begin(), jt = otherParams.begin();
522	for ( ; it != params.end() && jt != otherParams.end(); ++it, ++jt ) {
523	TypeExpr param = dynamic_cast< TypeExpr >(*it);
524	assertf(param, "Aggregate parameters should be type expressions");
525	TypeExpr otherParam = dynamic_cast< TypeExpr >(*jt);
526	assertf(otherParam, "Aggregate parameters should be type expressions");
527
528	Type* paramTy = param->get_type();
529	Type* otherParamTy = otherParam->get_type();
530
531	bool tupleParam = Tuples::isTtype( paramTy );
532	bool otherTupleParam = Tuples::isTtype( otherParamTy );
533
534	if ( tupleParam && otherTupleParam ) {
535	++it; ++jt; // skip ttype parameters for break
536	} else if ( tupleParam ) {
537	// bundle other parameters into tuple to match
538	std::list< Type * > binderTypes;
539
540	do {
541	binderTypes.push_back( otherParam->get_type()->clone() );
542	++jt;
543
544	if ( jt == otherParams.end() ) break;
545
546	otherParam = dynamic_cast< TypeExpr* >(*jt);
547	assertf(otherParam, "Aggregate parameters should be type expressions");
548	} while (true);
549
550	otherParamTy = new TupleType{ paramTy->get_qualifiers(), binderTypes };
551	++it; // skip ttype parameter for break
552	} else if ( otherTupleParam ) {
553	// bundle parameters into tuple to match other
554	std::list< Type * > binderTypes;
555
556	do {
557	binderTypes.push_back( param->get_type()->clone() );
558	++it;
559
560	if ( it == params.end() ) break;
561
562	param = dynamic_cast< TypeExpr* >(*it);
563	assertf(param, "Aggregate parameters should be type expressions");
564	} while (true);
565
566	paramTy = new TupleType{ otherParamTy->get_qualifiers(), binderTypes };
567	++jt; // skip ttype parameter for break
568	}
569
570	if ( ! unifyExact( paramTy, otherParamTy, env, needAssertions, haveAssertions, openVars, WidenMode(false, false), indexer ) ) {
571	result = false;
572	return;
573	}
574
575	// ttype parameter should be last
576	if ( tupleParam \|\| otherTupleParam ) break;
577	}
578	result = ( it == params.end() && jt == otherParams.end() );
579	}
580
581	void Unify_old::postvisit(StructInstType *structInst) {
582	handleGenericRefType( structInst, type2 );
583	}
584
585	void Unify_old::postvisit(UnionInstType *unionInst) {
586	handleGenericRefType( unionInst, type2 );
587	}
588
589	void Unify_old::postvisit(EnumInstType *enumInst) {
590	handleRefType( enumInst, type2 );
591	}
592
593	void Unify_old::postvisit(TraitInstType *contextInst) {
594	handleRefType( contextInst, type2 );
595	}
596
597	void Unify_old::postvisit(TypeInstType *typeInst) {
598	assert( openVars.find( typeInst->get_name() ) == openVars.end() );
599	TypeInstType otherInst = dynamic_cast< TypeInstType >( type2 );
600	if ( otherInst && typeInst->get_name() == otherInst->get_name() ) {
601	result = true;
602	/// } else {
603	/// NamedTypeDecl *nt = indexer.lookupType( typeInst->get_name() );
604	/// if ( nt ) {
605	/// TypeDecl type = dynamic_cast< TypeDecl >( nt );
606	/// assert( type );
607	/// if ( type->get_base() ) {
608	/// result = unifyExact( type->get_base(), typeInst, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
609	/// }
610	/// }
611	} // if
612	}
613
614	template< typename Iterator1, typename Iterator2 >
615	bool unifyList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
616	auto get_type = [](Type * t) { return t; };
617	for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) {
618	Type * t1 = *list1Begin;
619	Type * t2 = *list2Begin;
620	bool isTtype1 = Tuples::isTtype( t1 );
621	bool isTtype2 = Tuples::isTtype( t2 );
622	// xxx - assumes ttype must be last parameter
623	// xxx - there may be a nice way to refactor this, but be careful because the argument positioning might matter in some cases.
624	if ( isTtype1 && ! isTtype2 ) {
625	// combine all of the things in list2, then unify
626	return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
627	} else if ( isTtype2 && ! isTtype1 ) {
628	// combine all of the things in list1, then unify
629	return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
630	} else if ( ! unifyExact( t1, t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ) ) {
631	return false;
632	} // if
633
634	} // for
635	if ( list1Begin != list1End ) {
636	// try unifying empty tuple type with ttype
637	Type * t1 = *list1Begin;
638	if ( Tuples::isTtype( t1 ) ) {
639	return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
640	} else return false;
641	} else if ( list2Begin != list2End ) {
642	// try unifying empty tuple type with ttype
643	Type * t2 = *list2Begin;
644	if ( Tuples::isTtype( t2 ) ) {
645	return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
646	} else return false;
647	} else {
648	return true;
649	} // if
650	}
651
652	void Unify_old::postvisit(TupleType *tupleType) {
653	if ( TupleType otherTuple = dynamic_cast< TupleType >( type2 ) ) {
654	std::unique_ptr<TupleType> flat1( tupleType->clone() );
655	std::unique_ptr<TupleType> flat2( otherTuple->clone() );
656	std::list<Type *> types1, types2;
657
658	PassVisitor<TtypeExpander_old> expander( env );
659	flat1->acceptMutator( expander );
660	flat2->acceptMutator( expander );
661
662	flatten( flat1.get(), back_inserter( types1 ) );
663	flatten( flat2.get(), back_inserter( types2 ) );
664
665	result = unifyList( types1.begin(), types1.end(), types2.begin(), types2.end(), env, needAssertions, haveAssertions, openVars, indexer );
666	} // if
667	}
668
669	void Unify_old::postvisit( __attribute__((unused)) VarArgsType *varArgsType ) {
670	result = dynamic_cast< VarArgsType* >( type2 );
671	}
672
673	void Unify_old::postvisit( __attribute__((unused)) ZeroType *zeroType ) {
674	result = dynamic_cast< ZeroType* >( type2 );
675	}
676
677	void Unify_old::postvisit( __attribute__((unused)) OneType *oneType ) {
678	result = dynamic_cast< OneType* >( type2 );
679	}
680
681	Type * extractResultType( FunctionType * function ) {
682	if ( function->get_returnVals().size() == 0 ) {
683	return new VoidType( Type::Qualifiers() );
684	} else if ( function->get_returnVals().size() == 1 ) {
685	return function->get_returnVals().front()->get_type()->clone();
686	} else {
687	std::list< Type * > types;
688	for ( DeclarationWithType * decl : function->get_returnVals() ) {
689	types.push_back( decl->get_type()->clone() );
690	} // for
691	return new TupleType( Type::Qualifiers(), types );
692	}
693	}
694
695	class Unify_new final : public ast::WithShortCircuiting {
696	const ast::Type * type2;
697	ast::TypeEnvironment & tenv;
698	ast::AssertionSet & need;
699	ast::AssertionSet & have;
700	const ast::OpenVarSet & open;
701	WidenMode widen;
702	const ast::SymbolTable & symtab;
703	public:
704	static size_t traceId;
705	bool result;
706
707	Unify_new(
708	const ast::Type * type2, ast::TypeEnvironment & env, ast::AssertionSet & need,
709	ast::AssertionSet & have, const ast::OpenVarSet & open, WidenMode widen,
710	const ast::SymbolTable & symtab )
711	: type2(type2), tenv(env), need(need), have(have), open(open), widen(widen),
712	symtab(symtab), result(false) {}
713
714	void previsit( const ast::Node * ) { visit_children = false; }
715
716	void postvisit( const ast::VoidType * ) {
717	result = dynamic_cast< const ast::VoidType * >( type2 );
718	}
719
720	void postvisit( const ast::BasicType * basic ) {
721	if ( auto basic2 = dynamic_cast< const ast::BasicType * >( type2 ) ) {
722	result = basic->kind == basic2->kind;
723	}
724	}
725
726	void postvisit( const ast::PointerType * pointer ) {
727	if ( auto pointer2 = dynamic_cast< const ast::PointerType * >( type2 ) ) {
728	result = unifyExact(
729	pointer->base, pointer2->base, tenv, need, have, open,
730	noWiden(), symtab );
731	}
732	}
733
734	void postvisit( const ast::ArrayType * array ) {
735	auto array2 = dynamic_cast< const ast::ArrayType * >( type2 );
736	if ( ! array2 ) return;
737
738	// to unify, array types must both be VLA or both not VLA and both must have a
739	// dimension expression or not have a dimension
740	if ( array->isVarLen != array2->isVarLen ) return;
741	if ( ! array->isVarLen && ! array2->isVarLen
742	&& array->dimension && array2->dimension ) {
743	auto ce1 = array->dimension.as< ast::ConstantExpr >();
744	auto ce2 = array2->dimension.as< ast::ConstantExpr >();
745
746	// see C11 Reference Manual 6.7.6.2.6
747	// two array types with size specifiers that are integer constant expressions are
748	// compatible if both size specifiers have the same constant value
749	if ( ce1 && ce2 && ce1->intValue() != ce2->intValue() ) return;
750	}
751
752	result = unifyExact(
753	array->base, array2->base, tenv, need, have, open, noWiden(),
754	symtab );
755	}
756
757	void postvisit( const ast::ReferenceType * ref ) {
758	if ( auto ref2 = dynamic_cast< const ast::ReferenceType * >( type2 ) ) {
759	result = unifyExact(
760	ref->base, ref2->base, tenv, need, have, open, noWiden(),
761	symtab );
762	}
763	}
764
765	private:
766	/// Replaces ttype variables with their bound types.
767	/// If this isn't done when satifying ttype assertions, then argument lists can have
768	/// different size and structure when they should be compatible.
769	struct TtypeExpander_new : public ast::WithShortCircuiting, public ast::PureVisitor {
770	ast::TypeEnvironment & tenv;
771
772	TtypeExpander_new( ast::TypeEnvironment & env ) : tenv( env ) {}
773
774	const ast::Type * postvisit( const ast::TypeInstType * typeInst ) {
775	if ( const ast::EqvClass * clz = tenv.lookup( *typeInst ) ) {
776	// expand ttype parameter into its actual type
777	if ( clz->data.kind == ast::TypeDecl::Ttype && clz->bound ) {
778	return clz->bound;
779	}
780	}
781	return typeInst;
782	}
783	};
784
785	/// returns flattened version of `src`
786	static std::vector< ast::ptr< ast::Type > > flattenList(
787	const std::vector< ast::ptr< ast::Type > > & src, ast::TypeEnvironment & env
788	) {
789	std::vector< ast::ptr< ast::Type > > dst;
790	dst.reserve( src.size() );
791	for ( const auto & d : src ) {
792	ast::Pass<TtypeExpander_new> expander{ env };
793	// TtypeExpander pass is impure (may mutate nodes in place)
794	// need to make nodes shared to prevent accidental mutation
795	ast::ptr<ast::Type> dc = d->accept(expander);
796	auto types = flatten( dc );
797	for ( ast::ptr< ast::Type > & t : types ) {
798	// outermost const, volatile, _Atomic qualifiers in parameters should not play
799	// a role in the unification of function types, since they do not determine
800	// whether a function is callable.
801	// NOTE: must consider at least mutex qualifier, since functions can be
802	// overloaded on outermost mutex and a mutex function has different
803	// requirements than a non-mutex function
804	remove_qualifiers( t, ast::CV::Const \| ast::CV::Volatile \| ast::CV::Atomic );
805	dst.emplace_back( t );
806	}
807	}
808	return dst;
809	}
810
811	/// Creates a tuple type based on a list of DeclWithType
812	template< typename Iter >
813	static const ast::Type * tupleFromTypes( Iter crnt, Iter end ) {
814	std::vector< ast::ptr< ast::Type > > types;
815	while ( crnt != end ) {
816	// it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure
817	// that this results in a flat tuple
818	flatten( *crnt, types );
819
820	++crnt;
821	}
822
823	return new ast::TupleType{ std::move(types) };
824	}
825
826	template< typename Iter >
827	static bool unifyTypeList(
828	Iter crnt1, Iter end1, Iter crnt2, Iter end2, ast::TypeEnvironment & env,
829	ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
830	const ast::SymbolTable & symtab
831	) {
832	while ( crnt1 != end1 && crnt2 != end2 ) {
833	const ast::Type * t1 = *crnt1;
834	const ast::Type * t2 = *crnt2;
835	bool isTuple1 = Tuples::isTtype( t1 );
836	bool isTuple2 = Tuples::isTtype( t2 );
837
838	// assumes here that ttype must be last parameter
839	if ( isTuple1 && ! isTuple2 ) {
840	// combine remainder of list2, then unify
841	return unifyExact(
842	t1, tupleFromTypes( crnt2, end2 ), env, need, have, open,
843	noWiden(), symtab );
844	} else if ( ! isTuple1 && isTuple2 ) {
845	// combine remainder of list1, then unify
846	return unifyExact(
847	tupleFromTypes( crnt1, end1 ), t2, env, need, have, open,
848	noWiden(), symtab );
849	}
850
851	if ( ! unifyExact(
852	t1, t2, env, need, have, open, noWiden(), symtab )
853	) return false;
854
855	++crnt1; ++crnt2;
856	}
857
858	// May get to the end of one argument list before the other. This is only okay if the
859	// other is a ttype
860	if ( crnt1 != end1 ) {
861	// try unifying empty tuple with ttype
862	const ast::Type * t1 = *crnt1;
863	if ( ! Tuples::isTtype( t1 ) ) return false;
864	return unifyExact(
865	t1, tupleFromTypes( crnt2, end2 ), env, need, have, open,
866	noWiden(), symtab );
867	} else if ( crnt2 != end2 ) {
868	// try unifying empty tuple with ttype
869	const ast::Type * t2 = *crnt2;
870	if ( ! Tuples::isTtype( t2 ) ) return false;
871	return unifyExact(
872	tupleFromTypes( crnt1, end1 ), t2, env, need, have, open,
873	noWiden(), symtab );
874	}
875
876	return true;
877	}
878
879	static bool unifyTypeList(
880	const std::vector< ast::ptr< ast::Type > > & list1,
881	const std::vector< ast::ptr< ast::Type > > & list2,
882	ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
883	const ast::OpenVarSet & open, const ast::SymbolTable & symtab
884	) {
885	return unifyTypeList(
886	list1.begin(), list1.end(), list2.begin(), list2.end(), env, need, have, open,
887	symtab );
888	}
889
890	static void markAssertionSet( ast::AssertionSet & assns, const ast::VariableExpr * assn ) {
891	auto i = assns.find( assn );
892	if ( i != assns.end() ) {
893	i->second.isUsed = true;
894	}
895	}
896
897	/// mark all assertions in `type` used in both `assn1` and `assn2`
898	static void markAssertions(
899	ast::AssertionSet & assn1, ast::AssertionSet & assn2,
900	const ast::FunctionType * type
901	) {
902	for ( auto & assert : type->assertions ) {
903	markAssertionSet( assn1, assert );
904	markAssertionSet( assn2, assert );
905	}
906	}
907
908	public:
909	void postvisit( const ast::FunctionType * func ) {
910	auto func2 = dynamic_cast< const ast::FunctionType * >( type2 );
911	if ( ! func2 ) return;
912
913	if ( func->isVarArgs != func2->isVarArgs ) return;
914
915	// Flatten the parameter lists for both functions so that tuple structure does not
916	// affect unification. Does not actually mutate function parameters.
917	auto params = flattenList( func->params, tenv );
918	auto params2 = flattenList( func2->params, tenv );
919
920	// sizes don't have to match if ttypes are involved; need to be more precise w.r.t.
921	// where the ttype is to prevent errors
922	if (
923	( params.size() != params2.size() \|\| func->returns.size() != func2->returns.size() )
924	&& ! func->isTtype()
925	&& ! func2->isTtype()
926	) return;
927
928	if ( ! unifyTypeList( params, params2, tenv, need, have, open, symtab ) ) return;
929	if ( ! unifyTypeList(
930	func->returns, func2->returns, tenv, need, have, open, symtab ) ) return;
931
932	markAssertions( have, need, func );
933	markAssertions( have, need, func2 );
934
935	result = true;
936	}
937
938	private:
939	// Returns: other, cast as XInstType
940	// Assigns this->result: whether types are compatible (up to generic parameters)
941	template< typename XInstType >
942	const XInstType * handleRefType( const XInstType * inst, const ast::Type * other ) {
943	// check that the other type is compatible and named the same
944	auto otherInst = dynamic_cast< const XInstType * >( other );
945	this->result = otherInst && inst->name == otherInst->name;
946	return otherInst;
947	}
948
949	/// Creates a tuple type based on a list of TypeExpr
950	template< typename Iter >
951	static const ast::Type * tupleFromExprs(
952	const ast::TypeExpr * param, Iter & crnt, Iter end, ast::CV::Qualifiers qs
953	) {
954	std::vector< ast::ptr< ast::Type > > types;
955	do {
956	types.emplace_back( param->type );
957
958	++crnt;
959	if ( crnt == end ) break;
960	param = strict_dynamic_cast< const ast::TypeExpr * >( crnt->get() );
961	} while(true);
962
963	return new ast::TupleType{ std::move(types), qs };
964	}
965
966	template< typename XInstType >
967	void handleGenericRefType( const XInstType * inst, const ast::Type * other ) {
968	// check that other type is compatible and named the same
969	const XInstType * otherInst = handleRefType( inst, other );
970	if ( ! this->result ) return;
971
972	// check that parameters of types unify, if any
973	const std::vector< ast::ptr< ast::Expr > > & params = inst->params;
974	const std::vector< ast::ptr< ast::Expr > > & params2 = otherInst->params;
975
976	auto it = params.begin();
977	auto jt = params2.begin();
978	for ( ; it != params.end() && jt != params2.end(); ++it, ++jt ) {
979	auto param = strict_dynamic_cast< const ast::TypeExpr * >( it->get() );
980	auto param2 = strict_dynamic_cast< const ast::TypeExpr * >( jt->get() );
981
982	ast::ptr< ast::Type > pty = param->type;
983	ast::ptr< ast::Type > pty2 = param2->type;
984
985	bool isTuple = Tuples::isTtype( pty );
986	bool isTuple2 = Tuples::isTtype( pty2 );
987
988	if ( isTuple && isTuple2 ) {
989	++it; ++jt; // skip ttype parameters before break
990	} else if ( isTuple ) {
991	// bundle remaining params into tuple
992	pty2 = tupleFromExprs( param2, jt, params2.end(), pty->qualifiers );
993	++it; // skip ttype parameter for break
994	} else if ( isTuple2 ) {
995	// bundle remaining params into tuple
996	pty = tupleFromExprs( param, it, params.end(), pty2->qualifiers );
997	++jt; // skip ttype parameter for break
998	}
999
1000	if ( ! unifyExact(
1001	pty, pty2, tenv, need, have, open, noWiden(), symtab ) ) {
1002	result = false;
1003	return;
1004	}
1005
1006	// ttype parameter should be last
1007	if ( isTuple \|\| isTuple2 ) break;
1008	}
1009	result = it == params.end() && jt == params2.end();
1010	}
1011
1012	public:
1013	void postvisit( const ast::StructInstType * aggrType ) {
1014	handleGenericRefType( aggrType, type2 );
1015	}
1016
1017	void postvisit( const ast::UnionInstType * aggrType ) {
1018	handleGenericRefType( aggrType, type2 );
1019	}
1020
1021	void postvisit( const ast::EnumInstType * aggrType ) {
1022	handleRefType( aggrType, type2 );
1023	}
1024
1025	void postvisit( const ast::TraitInstType * aggrType ) {
1026	handleRefType( aggrType, type2 );
1027	}
1028
1029	void postvisit( const ast::TypeInstType * typeInst ) {
1030	assert( open.find( *typeInst ) == open.end() );
1031	handleRefType( typeInst, type2 );
1032	}
1033
1034	private:
1035	/// Creates a tuple type based on a list of Type
1036	static const ast::Type * tupleFromTypes(
1037	const std::vector< ast::ptr< ast::Type > > & tys
1038	) {
1039	std::vector< ast::ptr< ast::Type > > out;
1040	for ( const ast::Type * ty : tys ) {
1041	// it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure
1042	// that this results in a flat tuple
1043	flatten( ty, out );
1044	}
1045
1046	return { new ast::TupleType{ std::move(out) } };
1047	}
1048
1049	static bool unifyList(
1050	const std::vector< ast::ptr< ast::Type > > & list1,
1051	const std::vector< ast::ptr< ast::Type > > & list2, ast::TypeEnvironment & env,
1052	ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
1053	const ast::SymbolTable & symtab
1054	) {
1055	auto crnt1 = list1.begin();
1056	auto crnt2 = list2.begin();
1057	while ( crnt1 != list1.end() && crnt2 != list2.end() ) {
1058	const ast::Type * t1 = *crnt1;
1059	const ast::Type * t2 = *crnt2;
1060	bool isTuple1 = Tuples::isTtype( t1 );
1061	bool isTuple2 = Tuples::isTtype( t2 );
1062
1063	// assumes ttype must be last parameter
1064	if ( isTuple1 && ! isTuple2 ) {
1065	// combine entirety of list2, then unify
1066	return unifyExact(
1067	t1, tupleFromTypes( list2 ), env, need, have, open,
1068	noWiden(), symtab );
1069	} else if ( ! isTuple1 && isTuple2 ) {
1070	// combine entirety of list1, then unify
1071	return unifyExact(
1072	tupleFromTypes( list1 ), t2, env, need, have, open,
1073	noWiden(), symtab );
1074	}
1075
1076	if ( ! unifyExact(
1077	t1, t2, env, need, have, open, noWiden(), symtab )
1078	) return false;
1079
1080	++crnt1; ++crnt2;
1081	}
1082
1083	if ( crnt1 != list1.end() ) {
1084	// try unifying empty tuple type with ttype
1085	const ast::Type * t1 = *crnt1;
1086	if ( ! Tuples::isTtype( t1 ) ) return false;
1087	// xxx - this doesn't generate an empty tuple, contrary to comment; both ported
1088	// from Rob's code
1089	return unifyExact(
1090	t1, tupleFromTypes( list2 ), env, need, have, open,
1091	noWiden(), symtab );
1092	} else if ( crnt2 != list2.end() ) {
1093	// try unifying empty tuple with ttype
1094	const ast::Type * t2 = *crnt2;
1095	if ( ! Tuples::isTtype( t2 ) ) return false;
1096	// xxx - this doesn't generate an empty tuple, contrary to comment; both ported
1097	// from Rob's code
1098	return unifyExact(
1099	tupleFromTypes( list1 ), t2, env, need, have, open,
1100	noWiden(), symtab );
1101	}
1102
1103	return true;
1104	}
1105
1106	public:
1107	void postvisit( const ast::TupleType * tuple ) {
1108	auto tuple2 = dynamic_cast< const ast::TupleType * >( type2 );
1109	if ( ! tuple2 ) return;
1110
1111	ast::Pass<TtypeExpander_new> expander{ tenv };
1112
1113	const ast::Type * flat = tuple->accept( expander );
1114	const ast::Type * flat2 = tuple2->accept( expander );
1115
1116	auto types = flatten( flat );
1117	auto types2 = flatten( flat2 );
1118
1119	result = unifyList( types, types2, tenv, need, have, open, symtab );
1120	}
1121
1122	void postvisit( const ast::VarArgsType * ) {
1123	result = dynamic_cast< const ast::VarArgsType * >( type2 );
1124	}
1125
1126	void postvisit( const ast::ZeroType * ) {
1127	result = dynamic_cast< const ast::ZeroType * >( type2 );
1128	}
1129
1130	void postvisit( const ast::OneType * ) {
1131	result = dynamic_cast< const ast::OneType * >( type2 );
1132	}
1133
1134	private:
1135	template< typename RefType > void handleRefType( RefType inst, Type other );
1136	template< typename RefType > void handleGenericRefType( RefType inst, Type other );
1137	};
1138
1139	// size_t Unify_new::traceId = Stats::Heap::new_stacktrace_id("Unify_new");
1140	bool unify(
1141	const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
1142	ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
1143	ast::OpenVarSet & open, const ast::SymbolTable & symtab
1144	) {
1145	ast::ptr<ast::Type> common;
1146	return unify( type1, type2, env, need, have, open, symtab, common );
1147	}
1148
1149	bool unify(
1150	const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
1151	ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
1152	ast::OpenVarSet & open, const ast::SymbolTable & symtab, ast::ptr<ast::Type> & common
1153	) {
1154	ast::OpenVarSet closed;
1155	findOpenVars( type1, open, closed, need, have, FirstClosed );
1156	findOpenVars( type2, open, closed, need, have, FirstOpen );
1157	return unifyInexact(
1158	type1, type2, env, need, have, open, WidenMode{ true, true }, symtab, common );
1159	}
1160
1161	bool unifyExact(
1162	const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env,
1163	ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
1164	WidenMode widen, const ast::SymbolTable & symtab
1165	) {
1166	if ( type1->qualifiers != type2->qualifiers ) return false;
1167
1168	auto var1 = dynamic_cast< const ast::TypeInstType * >( type1 );
1169	auto var2 = dynamic_cast< const ast::TypeInstType * >( type2 );
1170	ast::OpenVarSet::const_iterator
1171	entry1 = var1 ? open.find( *var1 ) : open.end(),
1172	entry2 = var2 ? open.find( *var2 ) : open.end();
1173	bool isopen1 = entry1 != open.end();
1174	bool isopen2 = entry2 != open.end();
1175
1176	if ( isopen1 && isopen2 ) {
1177	if ( entry1->second.kind != entry2->second.kind ) return false;
1178	return env.bindVarToVar(
1179	var1, var2, ast::TypeDecl::Data{ entry1->second, entry2->second }, need, have,
1180	open, widen, symtab );
1181	} else if ( isopen1 ) {
1182	return env.bindVar( var1, type2, entry1->second, need, have, open, widen, symtab );
1183	} else if ( isopen2 ) {
1184	return env.bindVar( var2, type1, entry2->second, need, have, open, widen, symtab );
1185	} else {
1186	ast::Pass<Unify_new> comparator{ type2, env, need, have, open, widen, symtab };
1187	type1->accept( comparator );
1188	return comparator.core.result;
1189	}
1190	}
1191
1192	bool unifyInexact(
1193	const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
1194	ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
1195	const ast::OpenVarSet & open, WidenMode widen, const ast::SymbolTable & symtab,
1196	ast::ptr<ast::Type> & common
1197	) {
1198	ast::CV::Qualifiers q1 = type1->qualifiers, q2 = type2->qualifiers;
1199
1200	// force t1 and t2 to be cloned if their qualifiers must be stripped, so that type1 and
1201	// type2 are left unchanged; calling convention forces type{1,2}->strong_ref >= 1
1202	ast::Type * t1 = shallowCopy(type1.get());
1203	ast::Type * t2 = shallowCopy(type2.get());
1204	t1->qualifiers = {};
1205	t2->qualifiers = {};
1206	ast::ptr< ast::Type > t1_(t1);
1207	ast::ptr< ast::Type > t2_(t2);
1208
1209	if ( unifyExact( t1, t2, env, need, have, open, widen, symtab ) ) {
1210	// if exact unification on unqualified types, try to merge qualifiers
1211	if ( q1 == q2 \|\| ( ( q1 > q2 \|\| widen.first ) && ( q2 > q1 \|\| widen.second ) ) ) {
1212	t1->qualifiers = q1 \| q2;
1213	common = t1;
1214	return true;
1215	} else {
1216	return false;
1217	}
1218
1219	} else if (( common = commonType( t1, t2, widen, symtab, env, open ) )) {
1220	// no exact unification, but common type
1221	auto c = shallowCopy(common.get());
1222	c->qualifiers = q1 \| q2;
1223	common = c;
1224	return true;
1225	} else {
1226	return false;
1227	}
1228	}
1229
1230	ast::ptr<ast::Type> extractResultType( const ast::FunctionType * func ) {
1231	if ( func->returns.empty() ) return new ast::VoidType{};
1232	if ( func->returns.size() == 1 ) return func->returns[0];
1233
1234	std::vector<ast::ptr<ast::Type>> tys;
1235	for ( const auto & decl : func->returns ) {
1236	tys.emplace_back( decl );
1237	}
1238	return new ast::TupleType{ std::move(tys) };
1239	}
1240	} // namespace ResolvExpr
1241
1242	// Local Variables: //
1243	// tab-width: 4 //
1244	// mode: c++ //
1245	// compile-command: "make install" //
1246	// End: //

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

Download in other formats: