Context Navigation

source: src/ResolvExpr/Unify.cc @ 8c91088

ADTast-experimental

Last change on this file since 8c91088 was 5d8dae7, checked in by Andrew Beach <ajbeach@…>, 20 months ago
Used Pass::read in Unify in one place.
Property mode set to `100644`
File size: 47.6 KB

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

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

Download in other formats: