Context Navigation

source: src/ResolvExpr/Unify.cc @ fed6a0f

ADTast-experimental

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

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

Download in other formats: