Context Navigation

source: src/ResolvExpr/Unify.cc @ f6bceeb

ADTast-experimental

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

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

Download in other formats: