Context Navigation

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

Visit:

ADT ast-experimental

Last change on this file since 8e64cb4 was 93c10de, checked in by Andrew Beach <ajbeach@…>, 3 years ago
Minimal changes to pull out nested types, TypeInstType::TypeEnvKey and TypeDecl::Data (now TypeData) from there parent types. Although they do connect to the parent types they were nested in they are used on their own most of the time.
Property mode set to `100644`
File size: 47.6 KB

Rev	Line
[a32b204]	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	//
[41a2620]	7	// Unify.cc --
[a32b204]	8	//
	9	// Author : Richard C. Bilson
	10	// Created On : Sun May 17 12:27:10 2015
[07de76b]	11	// Last Modified By : Peter A. Buhr
	12	// Last Modified On : Fri Dec 13 23:43:05 2019
	13	// Update Count : 46
[a32b204]	14	//
[51b73452]	15
[f474e91]	16	#include "Unify.h"
	17
[d76c588]	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
[54e41b3]	25	#include <vector>
[51b73452]	26
[2890212]	27	#include "AST/Copy.hpp"
[f474e91]	28	#include "AST/Decl.hpp"
[54e41b3]	29	#include "AST/Node.hpp"
[f474e91]	30	#include "AST/Pass.hpp"
[2890212]	31	#include "AST/Print.hpp"
[54e41b3]	32	#include "AST/Type.hpp"
[d76c588]	33	#include "AST/TypeEnvironment.hpp"
	34	#include "Common/PassVisitor.h" // for PassVisitor
	35	#include "FindOpenVars.h" // for findOpenVars
[07de76b]	36	#include "SynTree/LinkageSpec.h" // for C
[d76c588]	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
[ea6332d]	46
[f474e91]	47	namespace ast {
	48	class SymbolTable;
	49	}
	50
[ea6332d]	51	namespace SymTab {
	52	class Indexer;
	53	} // namespace SymTab
[51b73452]	54
[1cbca6e]	55	// #define DEBUG
[51b73452]	56
	57	namespace ResolvExpr {
	58
[f474e91]	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 );
[41a2620]	61
[a32b204]	62	bool get_result() const { return result; }
	63
[36a2367]	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:
[a32b204]	83	template< typename RefType > void handleRefType( RefType inst, Type other );
[02ec390]	84	template< typename RefType > void handleGenericRefType( RefType inst, Type other );
[a32b204]	85
	86	bool result;
	87	Type *type2; // inherited
	88	TypeEnvironment &env;
	89	AssertionSet &needAssertions;
	90	AssertionSet &haveAssertions;
	91	const OpenVarSet &openVars;
[f474e91]	92	WidenMode widen;
[a32b204]	93	const SymTab::Indexer &indexer;
	94	};
	95
[eb50842]	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)
[f474e91]	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
[7870799]	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,
[f474e91]	104	WidenMode widen, const ast::SymbolTable & symtab );
[41a2620]	105
[6f096d2]	106	bool typesCompatible( const Type * first, const Type * second, const SymTab::Indexer & indexer, const TypeEnvironment & env ) {
[a32b204]	107	TypeEnvironment newEnv;
[1cbca6e]	108	OpenVarSet openVars, closedVars; // added closedVars
[a32b204]	109	AssertionSet needAssertions, haveAssertions;
[6f096d2]	110	Type * newFirst = first->clone(), * newSecond = second->clone();
[a32b204]	111	env.apply( newFirst );
	112	env.apply( newSecond );
[1cbca6e]	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
[a32b204]	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
[7870799]	125	bool typesCompatible(
	126	const ast::Type * first, const ast::Type * second, const ast::SymbolTable & symtab,
[d76c588]	127	const ast::TypeEnvironment & env ) {
[f474e91]	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
[2890212]	139	return unifyExact(newFirst, newSecond, newEnv, need, have, open, noWiden(), symtab );
[d76c588]	140	}
	141
[7870799]	142	bool typesCompatibleIgnoreQualifiers( const Type * first, const Type * second, const SymTab::Indexer &indexer, const TypeEnvironment &env ) {
[a32b204]	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();
[2890212]	151
[a32b204]	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
[7870799]	158	bool typesCompatibleIgnoreQualifiers(
	159	const ast::Type * first, const ast::Type * second, const ast::SymbolTable & symtab,
[d76c588]	160	const ast::TypeEnvironment & env ) {
[f474e91]	161	ast::TypeEnvironment newEnv;
	162	ast::OpenVarSet open;
	163	ast::AssertionSet need, have;
[7870799]	164
[2890212]	165	ast::Type * newFirst = shallowCopy( first );
	166	ast::Type * newSecond = shallowCopy( second );
[b729c01]	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
[2890212]	181	newFirst ->qualifiers = {};
	182	newSecond->qualifiers = {};
[f49b3fc]	183	ast::ptr< ast::Type > t1_(newFirst );
	184	ast::ptr< ast::Type > t2_(newSecond);
[f474e91]	185
[c7f834e]	186	ast::ptr< ast::Type > subFirst = env.apply(newFirst).node;
	187	ast::ptr< ast::Type > subSecond = env.apply(newSecond).node;
	188
[7870799]	189	return unifyExact(
[c7f834e]	190	subFirst,
	191	subSecond,
[2890212]	192	newEnv, need, have, open, noWiden(), symtab );
[d76c588]	193	}
	194
[a32b204]	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
[f474e91]	217	bool unifyExact( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ) {
[51b73452]	218	#ifdef DEBUG
[a32b204]	219	TypeEnvironment debugEnv( env );
[51b73452]	220	#endif
[eb50842]	221	if ( type1->get_qualifiers() != type2->get_qualifiers() ) {
	222	return false;
	223	}
	224
[a32b204]	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() );
[eb50842]	237
[7a63486]	238	if ( isopen1 && isopen2 ) {
	239	if ( entry1->second.kind != entry2->second.kind ) {
	240	result = false;
	241	} else {
[4139e3d]	242	result = env.bindVarToVar(
	243	var1, var2, TypeDecl::Data{ entry1->second, entry2->second }, needAssertions,
[f474e91]	244	haveAssertions, openVars, widen, indexer );
[7a63486]	245	}
[a32b204]	246	} else if ( isopen1 ) {
[f474e91]	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 );
[a32b204]	250	} else {
[f474e91]	251	PassVisitor<Unify_old> comparator( type2, env, needAssertions, haveAssertions, openVars, widen, indexer );
[a32b204]	252	type1->accept( comparator );
[36a2367]	253	result = comparator.pass.get_result();
[a32b204]	254	} // if
[51b73452]	255	#ifdef DEBUG
[2c57025]	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;
[51b73452]	268	#endif
[a32b204]	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
[f474e91]	276	bool unifyInexact( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer, Type *&common ) {
[a32b204]	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;
[51b73452]	281	#ifdef DEBUG
[2c57025]	282	std::cerr << "unifyInexact type 1 is ";
	283	type1->print( std::cerr );
[0b150ec]	284	std::cerr << " type 2 is ";
[2c57025]	285	type2->print( std::cerr );
	286	std::cerr << std::endl;
[51b73452]	287	#endif
[f474e91]	288	if ( ! unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, widen, indexer ) ) {
[51b73452]	289	#ifdef DEBUG
[2c57025]	290	std::cerr << "unifyInexact: no exact unification found" << std::endl;
[51b73452]	291	#endif
[f474e91]	292	if ( ( common = commonType( type1, type2, widen.first, widen.second, indexer, env, openVars ) ) ) {
[3315e3d]	293	common->tq = tq1.unify( tq2 );
[51b73452]	294	#ifdef DEBUG
[2c57025]	295	std::cerr << "unifyInexact: common type is ";
	296	common->print( std::cerr );
	297	std::cerr << std::endl;
[51b73452]	298	#endif
[a32b204]	299	result = true;
	300	} else {
[51b73452]	301	#ifdef DEBUG
[2c57025]	302	std::cerr << "unifyInexact: no common type found" << std::endl;
[51b73452]	303	#endif
[a32b204]	304	result = false;
	305	} // if
	306	} else {
	307	if ( tq1 != tq2 ) {
[f474e91]	308	if ( ( tq1 > tq2 \|\| widen.first ) && ( tq2 > tq1 \|\| widen.second ) ) {
[a32b204]	309	common = type1->clone();
[3315e3d]	310	common->tq = tq1.unify( tq2 );
[a32b204]	311	result = true;
	312	} else {
	313	result = false;
	314	} // if
	315	} else {
[e6cee92]	316	common = type1->clone();
[3315e3d]	317	common->tq = tq1.unify( tq2 );
[a32b204]	318	result = true;
	319	} // if
	320	} // if
	321	type1->get_qualifiers() = tq1;
	322	type2->get_qualifiers() = tq2;
	323	return result;
	324	}
	325
[f474e91]	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 ) {
[d76c588]	328	}
	329
[f474e91]	330	void Unify_old::postvisit( __attribute__((unused)) VoidType *voidType) {
[a32b204]	331	result = dynamic_cast< VoidType* >( type2 );
	332	}
	333
[f474e91]	334	void Unify_old::postvisit(BasicType *basicType) {
[a32b204]	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() ) {
[6c3a988f]	343	i->second.isUsed = true;
[a32b204]	344	} // if
	345	}
	346
	347	void markAssertions( AssertionSet &assertion1, AssertionSet &assertion2, Type *type ) {
[aefcc3b]	348	for ( std::list< TypeDecl* >::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
[a32b204]	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
[f474e91]	356	void Unify_old::postvisit(PointerType *pointerType) {
[a32b204]	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
[f474e91]	364	void Unify_old::postvisit(ReferenceType *refType) {
[ce8c12f]	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
[f474e91]	372	void Unify_old::postvisit(ArrayType *arrayType) {
[a32b204]	373	ArrayType otherArray = dynamic_cast< ArrayType >( type2 );
[1cbca6e]	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
[41a2620]	376	if ( otherArray && arrayType->get_isVarLen() == otherArray->get_isVarLen() ) {
[1cbca6e]	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() );
[41a2620]	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	}
[1cbca6e]	393	}
	394	}
	395
[a32b204]	396	result = unifyExact( arrayType->get_base(), otherArray->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
	397	} // if
	398	}
	399
[f3b0a07]	400	template< typename Iterator, typename Func >
	401	std::unique_ptr<Type> combineTypes( Iterator begin, Iterator end, Func & toType ) {
[53e3b4a]	402	std::list< Type * > types;
	403	for ( ; begin != end; ++begin ) {
[64eae56]	404	// it's guaranteed that a ttype variable will be bound to a flat tuple, so ensure that this results in a flat tuple
[f3b0a07]	405	flatten( toType( *begin ), back_inserter( types ) );
[53e3b4a]	406	}
[6c3a988f]	407	return std::unique_ptr<Type>( new TupleType( Type::Qualifiers(), types ) );
[53e3b4a]	408	}
	409
[a32b204]	410	template< typename Iterator1, typename Iterator2 >
[954c954]	411	bool unifyTypeList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
[f3b0a07]	412	auto get_type = [](DeclarationWithType * dwt){ return dwt->get_type(); };
[a32b204]	413	for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) {
[53e3b4a]	414	Type * t1 = (*list1Begin)->get_type();
	415	Type * t2 = (*list2Begin)->get_type();
	416	bool isTtype1 = Tuples::isTtype( t1 );
	417	bool isTtype2 = Tuples::isTtype( t2 );
[6c3a988f]	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.
[53e3b4a]	420	if ( isTtype1 && ! isTtype2 ) {
	421	// combine all of the things in list2, then unify
[f3b0a07]	422	return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
[53e3b4a]	423	} else if ( isTtype2 && ! isTtype1 ) {
	424	// combine all of the things in list1, then unify
[f3b0a07]	425	return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
[53e3b4a]	426	} else if ( ! unifyExact( t1, t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ) ) {
[a32b204]	427	return false;
	428	} // if
	429	} // for
[6c3a988f]	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
[4c8621ac]	431	if ( list1Begin != list1End ) {
	432	// try unifying empty tuple type with ttype
	433	Type * t1 = (*list1Begin)->get_type();
	434	if ( Tuples::isTtype( t1 ) ) {
[f3b0a07]	435	return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
[4c8621ac]	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 ) ) {
[f3b0a07]	441	return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
[4c8621ac]	442	} else return false;
[a32b204]	443	} else {
	444	return true;
	445	} // if
	446	}
	447
[6c3a988f]	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.
[f474e91]	452	struct TtypeExpander_old : public WithShortCircuiting {
[3096ec1]	453	TypeEnvironment & tenv;
[f474e91]	454	TtypeExpander_old( TypeEnvironment & tenv ) : tenv( tenv ) {}
[3096ec1]	455	void premutate( TypeInstType * ) { visit_children = false; }
	456	Type * postmutate( TypeInstType * typeInst ) {
[00ac42e]	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();
[6c3a988f]	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 ) {
[f474e91]	473	PassVisitor<TtypeExpander_old> expander( env );
[6c3a988f]	474	dcl->acceptMutator( expander );
	475	std::list< Type * > types;
	476	flatten( dcl->get_type(), back_inserter( types ) );
	477	for ( Type * t : types ) {
[1dcd52a3]	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
[68fe077a]	482	dst.push_back( new ObjectDecl( "", Type::StorageClasses(), LinkageSpec::C, nullptr, t, nullptr ) );
[6c3a988f]	483	}
	484	delete dcl;
	485	}
	486	}
	487
[f474e91]	488	void Unify_old::postvisit(FunctionType *functionType) {
[a32b204]	489	FunctionType otherFunction = dynamic_cast< FunctionType >( type2 );
	490	if ( otherFunction && functionType->get_isVarArgs() == otherFunction->get_isVarArgs() ) {
[6c3a988f]	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
[53e3b4a]	498	// sizes don't have to match if ttypes are involved; need to be more precise wrt where the ttype is to prevent errors
[7870799]	499	if (
	500	(flatFunc->parameters.size() == flatOther->parameters.size() &&
	501	flatFunc->returnVals.size() == flatOther->returnVals.size())
	502	\|\| flatFunc->isTtype()
	503	\|\| flatOther->isTtype()
[f474e91]	504	) {
[954c954]	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 ) ) {
[1cbca6e]	507
[6c3a988f]	508	// the original types must be used in mark assertions, since pointer comparisons are used
[03da511]	509	markAssertions( haveAssertions, needAssertions, functionType );
	510	markAssertions( haveAssertions, needAssertions, otherFunction );
[41a2620]	511
[03da511]	512	result = true;
	513	} // if
[a32b204]	514	} // if
	515	} // if
	516	} // if
	517	}
	518
	519	template< typename RefType >
[f474e91]	520	void Unify_old::handleRefType( RefType inst, Type other ) {
[02ec390]	521	// check that other type is compatible and named the same
[a32b204]	522	RefType otherStruct = dynamic_cast< RefType >( other );
[538334a]	523	result = otherStruct && inst->name == otherStruct->name;
[02ec390]	524	}
	525
	526	template< typename RefType >
[f474e91]	527	void Unify_old::handleGenericRefType( RefType inst, Type other ) {
[02ec390]	528	// Check that other type is compatible and named the same
	529	handleRefType( inst, other );
	530	if ( ! result ) return;
[f5234f3]	531	// Check that parameters of types unify, if any
[538334a]	532	std::list< Expression* > params = inst->parameters;
	533	std::list< Expression* > otherParams = ((RefType*)other)->parameters;
[f5234f3]	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);
[b2daebd4]	538	assertf(param, "Aggregate parameters should be type expressions");
[f5234f3]	539	TypeExpr otherParam = dynamic_cast< TypeExpr >(*jt);
[b2daebd4]	540	assertf(otherParam, "Aggregate parameters should be type expressions");
[ce8c12f]	541
[b2daebd4]	542	Type* paramTy = param->get_type();
	543	Type* otherParamTy = otherParam->get_type();
[f5234f3]	544
[b2daebd4]	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
[62423350]	552	std::list< Type * > binderTypes;
[b2daebd4]	553
	554	do {
[62423350]	555	binderTypes.push_back( otherParam->get_type()->clone() );
[b2daebd4]	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
[62423350]	564	otherParamTy = new TupleType{ paramTy->get_qualifiers(), binderTypes };
[b2daebd4]	565	++it; // skip ttype parameter for break
	566	} else if ( otherTupleParam ) {
	567	// bundle parameters into tuple to match other
[62423350]	568	std::list< Type * > binderTypes;
[b2daebd4]	569
	570	do {
[62423350]	571	binderTypes.push_back( param->get_type()->clone() );
[b2daebd4]	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
[62423350]	580	paramTy = new TupleType{ otherParamTy->get_qualifiers(), binderTypes };
[b2daebd4]	581	++jt; // skip ttype parameter for break
	582	}
	583
	584	if ( ! unifyExact( paramTy, otherParamTy, env, needAssertions, haveAssertions, openVars, WidenMode(false, false), indexer ) ) {
[02ec390]	585	result = false;
	586	return;
	587	}
[b2daebd4]	588
	589	// ttype parameter should be last
	590	if ( tupleParam \|\| otherTupleParam ) break;
[02ec390]	591	}
[f5234f3]	592	result = ( it == params.end() && jt == otherParams.end() );
[02ec390]	593	}
[a32b204]	594
[f474e91]	595	void Unify_old::postvisit(StructInstType *structInst) {
[02ec390]	596	handleGenericRefType( structInst, type2 );
[a32b204]	597	}
	598
[f474e91]	599	void Unify_old::postvisit(UnionInstType *unionInst) {
[02ec390]	600	handleGenericRefType( unionInst, type2 );
[a32b204]	601	}
	602
[f474e91]	603	void Unify_old::postvisit(EnumInstType *enumInst) {
[a32b204]	604	handleRefType( enumInst, type2 );
	605	}
	606
[f474e91]	607	void Unify_old::postvisit(TraitInstType *contextInst) {
[a32b204]	608	handleRefType( contextInst, type2 );
	609	}
	610
[f474e91]	611	void Unify_old::postvisit(TypeInstType *typeInst) {
[a32b204]	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;
[51b73452]	616	/// } else {
	617	/// NamedTypeDecl *nt = indexer.lookupType( typeInst->get_name() );
[a32b204]	618	/// if ( nt ) {
[51b73452]	619	/// TypeDecl type = dynamic_cast< TypeDecl >( nt );
	620	/// assert( type );
[a32b204]	621	/// if ( type->get_base() ) {
[51b73452]	622	/// result = unifyExact( type->get_base(), typeInst, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
	623	/// }
	624	/// }
[a32b204]	625	} // if
	626	}
	627
	628	template< typename Iterator1, typename Iterator2 >
[c77fd8b]	629	bool unifyList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
[f3b0a07]	630	auto get_type = [](Type * t) { return t; };
[a32b204]	631	for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) {
[f3b0a07]	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 ) ) {
[a32b204]	645	return false;
[f3b0a07]	646	} // if
	647
[a32b204]	648	} // for
[f3b0a07]	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;
[a32b204]	661	} else {
	662	return true;
[f3b0a07]	663	} // if
[a32b204]	664	}
	665
[f474e91]	666	void Unify_old::postvisit(TupleType *tupleType) {
[a32b204]	667	if ( TupleType otherTuple = dynamic_cast< TupleType >( type2 ) ) {
[f3b0a07]	668	std::unique_ptr<TupleType> flat1( tupleType->clone() );
	669	std::unique_ptr<TupleType> flat2( otherTuple->clone() );
	670	std::list<Type *> types1, types2;
	671
[f474e91]	672	PassVisitor<TtypeExpander_old> expander( env );
[f3b0a07]	673	flat1->acceptMutator( expander );
	674	flat2->acceptMutator( expander );
	675
	676	flatten( flat1.get(), back_inserter( types1 ) );
	677	flatten( flat2.get(), back_inserter( types2 ) );
	678
[c77fd8b]	679	result = unifyList( types1.begin(), types1.end(), types2.begin(), types2.end(), env, needAssertions, haveAssertions, openVars, indexer );
[a32b204]	680	} // if
	681	}
[51b73452]	682
[f474e91]	683	void Unify_old::postvisit( __attribute__((unused)) VarArgsType *varArgsType ) {
[44b7088]	684	result = dynamic_cast< VarArgsType* >( type2 );
	685	}
	686
[f474e91]	687	void Unify_old::postvisit( __attribute__((unused)) ZeroType *zeroType ) {
[89e6ffc]	688	result = dynamic_cast< ZeroType* >( type2 );
	689	}
	690
[f474e91]	691	void Unify_old::postvisit( __attribute__((unused)) OneType *oneType ) {
[89e6ffc]	692	result = dynamic_cast< OneType* >( type2 );
	693	}
	694
[906e24d]	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 {
[62423350]	701	std::list< Type * > types;
[906e24d]	702	for ( DeclarationWithType * decl : function->get_returnVals() ) {
[62423350]	703	types.push_back( decl->get_type()->clone() );
[906e24d]	704	} // for
[62423350]	705	return new TupleType( Type::Qualifiers(), types );
[906e24d]	706	}
	707	}
[54e41b3]	708
[ef1da0e2]	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	}
[0bd46fd]	729
[ef1da0e2]	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
[ee574a2]	755	class Unify_new final : public ast::WithShortCircuiting {
[f474e91]	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:
[c15085d]	764	static size_t traceId;
[f474e91]	765	bool result;
	766
[7870799]	767	Unify_new(
	768	const ast::Type * type2, ast::TypeEnvironment & env, ast::AssertionSet & need,
	769	ast::AssertionSet & have, const ast::OpenVarSet & open, WidenMode widen,
[f474e91]	770	const ast::SymbolTable & symtab )
[7870799]	771	: type2(type2), tenv(env), need(need), have(have), open(open), widen(widen),
[f474e91]	772	symtab(symtab), result(false) {}
	773
	774	void previsit( const ast::Node * ) { visit_children = false; }
[7870799]	775
[ee574a2]	776	void postvisit( const ast::VoidType * ) {
[f474e91]	777	result = dynamic_cast< const ast::VoidType * >( type2 );
	778	}
	779
[ee574a2]	780	void postvisit( const ast::BasicType * basic ) {
[f474e91]	781	if ( auto basic2 = dynamic_cast< const ast::BasicType * >( type2 ) ) {
	782	result = basic->kind == basic2->kind;
	783	}
	784	}
	785
[ee574a2]	786	void postvisit( const ast::PointerType * pointer ) {
[f474e91]	787	if ( auto pointer2 = dynamic_cast< const ast::PointerType * >( type2 ) ) {
[7870799]	788	result = unifyExact(
	789	pointer->base, pointer2->base, tenv, need, have, open,
[ee574a2]	790	noWiden(), symtab );
[f474e91]	791	}
	792	}
	793
[ee574a2]	794	void postvisit( const ast::ArrayType * array ) {
[f474e91]	795	auto array2 = dynamic_cast< const ast::ArrayType * >( type2 );
	796	if ( ! array2 ) return;
	797
[7870799]	798	// to unify, array types must both be VLA or both not VLA and both must have a
[f474e91]	799	// dimension expression or not have a dimension
	800	if ( array->isVarLen != array2->isVarLen ) return;
[7870799]	801	if ( ! array->isVarLen && ! array2->isVarLen
[f474e91]	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
[7870799]	807	// two array types with size specifiers that are integer constant expressions are
[f474e91]	808	// compatible if both size specifiers have the same constant value
	809	if ( ce1 && ce2 && ce1->intValue() != ce2->intValue() ) return;
	810	}
	811
[7870799]	812	result = unifyExact(
	813	array->base, array2->base, tenv, need, have, open, noWiden(),
[f474e91]	814	symtab );
	815	}
	816
[ee574a2]	817	void postvisit( const ast::ReferenceType * ref ) {
[f474e91]	818	if ( auto ref2 = dynamic_cast< const ast::ReferenceType * >( type2 ) ) {
[7870799]	819	result = unifyExact(
	820	ref->base, ref2->base, tenv, need, have, open, noWiden(),
[f474e91]	821	symtab );
	822	}
	823	}
	824
	825	private:
	826
	827	template< typename Iter >
[954c954]	828	static bool unifyTypeList(
[7870799]	829	Iter crnt1, Iter end1, Iter crnt2, Iter end2, ast::TypeEnvironment & env,
	830	ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
[f474e91]	831	const ast::SymbolTable & symtab
	832	) {
	833	while ( crnt1 != end1 && crnt2 != end2 ) {
[954c954]	834	const ast::Type * t1 = *crnt1;
	835	const ast::Type * t2 = *crnt2;
[f474e91]	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
[7870799]	842	return unifyExact(
[954c954]	843	t1, tupleFromTypes( crnt2, end2 ), env, need, have, open,
[ee574a2]	844	noWiden(), symtab );
[f474e91]	845	} else if ( ! isTuple1 && isTuple2 ) {
	846	// combine remainder of list1, then unify
[7870799]	847	return unifyExact(
[954c954]	848	tupleFromTypes( crnt1, end1 ), t2, env, need, have, open,
[ee574a2]	849	noWiden(), symtab );
[f474e91]	850	}
	851
[7870799]	852	if ( ! unifyExact(
	853	t1, t2, env, need, have, open, noWiden(), symtab )
[f474e91]	854	) return false;
	855
	856	++crnt1; ++crnt2;
	857	}
	858
[7870799]	859	// May get to the end of one argument list before the other. This is only okay if the
[f474e91]	860	// other is a ttype
	861	if ( crnt1 != end1 ) {
	862	// try unifying empty tuple with ttype
[954c954]	863	const ast::Type * t1 = *crnt1;
[f474e91]	864	if ( ! Tuples::isTtype( t1 ) ) return false;
[7870799]	865	return unifyExact(
[954c954]	866	t1, tupleFromTypes( crnt2, end2 ), env, need, have, open,
[ee574a2]	867	noWiden(), symtab );
[f474e91]	868	} else if ( crnt2 != end2 ) {
	869	// try unifying empty tuple with ttype
[954c954]	870	const ast::Type * t2 = *crnt2;
[f474e91]	871	if ( ! Tuples::isTtype( t2 ) ) return false;
[7870799]	872	return unifyExact(
[954c954]	873	tupleFromTypes( crnt1, end1 ), t2, env, need, have, open,
[ee574a2]	874	noWiden(), symtab );
[f474e91]	875	}
	876
	877	return true;
	878	}
	879
[954c954]	880	static bool unifyTypeList(
	881	const std::vector< ast::ptr< ast::Type > > & list1,
	882	const std::vector< ast::ptr< ast::Type > > & list2,
[7870799]	883	ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
[f474e91]	884	const ast::OpenVarSet & open, const ast::SymbolTable & symtab
	885	) {
[954c954]	886	return unifyTypeList(
[7870799]	887	list1.begin(), list1.end(), list2.begin(), list2.end(), env, need, have, open,
[f474e91]	888	symtab );
	889	}
	890
[3e5dd913]	891	static void markAssertionSet( ast::AssertionSet & assns, const ast::VariableExpr * assn ) {
[f474e91]	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`
[7870799]	899	static void markAssertions(
	900	ast::AssertionSet & assn1, ast::AssertionSet & assn2,
[361bf01]	901	const ast::FunctionType * type
[f474e91]	902	) {
[3e5dd913]	903	for ( auto & assert : type->assertions ) {
	904	markAssertionSet( assn1, assert );
	905	markAssertionSet( assn2, assert );
[f474e91]	906	}
	907	}
	908
	909	public:
[ee574a2]	910	void postvisit( const ast::FunctionType * func ) {
[f474e91]	911	auto func2 = dynamic_cast< const ast::FunctionType * >( type2 );
	912	if ( ! func2 ) return;
	913
	914	if ( func->isVarArgs != func2->isVarArgs ) return;
[7870799]	915
	916	// Flatten the parameter lists for both functions so that tuple structure does not
[f474e91]	917	// affect unification. Does not actually mutate function parameters.
	918	auto params = flattenList( func->params, tenv );
	919	auto params2 = flattenList( func2->params, tenv );
	920
[7870799]	921	// sizes don't have to match if ttypes are involved; need to be more precise w.r.t.
[f474e91]	922	// where the ttype is to prevent errors
[7870799]	923	if (
[f474e91]	924	( params.size() != params2.size() \|\| func->returns.size() != func2->returns.size() )
	925	&& ! func->isTtype()
	926	&& ! func2->isTtype()
	927	) return;
	928
[954c954]	929	if ( ! unifyTypeList( params, params2, tenv, need, have, open, symtab ) ) return;
	930	if ( ! unifyTypeList(
[f474e91]	931	func->returns, func2->returns, tenv, need, have, open, symtab ) ) return;
[7870799]	932
[f474e91]	933	markAssertions( have, need, func );
	934	markAssertions( have, need, func2 );
	935
	936	result = true;
	937	}
[7870799]	938
[f474e91]	939	private:
[90ce35aa]	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 ) {
[f474e91]	944	// check that the other type is compatible and named the same
[90ce35aa]	945	auto otherInst = dynamic_cast< const XInstType * >( other );
[9d8124f]	946	if (otherInst && inst->name == otherInst->name) this->result = otherInst;
[f474e91]	947	return otherInst;
	948	}
	949
	950	/// Creates a tuple type based on a list of TypeExpr
	951	template< typename Iter >
[7870799]	952	static const ast::Type * tupleFromExprs(
[f474e91]	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
[90ce35aa]	967	template< typename XInstType >
	968	void handleGenericRefType( const XInstType * inst, const ast::Type * other ) {
[f474e91]	969	// check that other type is compatible and named the same
[90ce35aa]	970	const XInstType * otherInst = handleRefType( inst, other );
	971	if ( ! this->result ) return;
[7870799]	972
[f474e91]	973	// check that parameters of types unify, if any
	974	const std::vector< ast::ptr< ast::Expr > > & params = inst->params;
[90ce35aa]	975	const std::vector< ast::ptr< ast::Expr > > & params2 = otherInst->params;
[f474e91]	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
[0bd46fd]	991	} else if ( isTuple ) {
[f474e91]	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
[7870799]	1001	if ( ! unifyExact(
[ee574a2]	1002	pty, pty2, tenv, need, have, open, noWiden(), symtab ) ) {
[f474e91]	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:
[ee574a2]	1014	void postvisit( const ast::StructInstType * aggrType ) {
[f474e91]	1015	handleGenericRefType( aggrType, type2 );
	1016	}
	1017
[ee574a2]	1018	void postvisit( const ast::UnionInstType * aggrType ) {
[f474e91]	1019	handleGenericRefType( aggrType, type2 );
	1020	}
	1021
[ee574a2]	1022	void postvisit( const ast::EnumInstType * aggrType ) {
[f474e91]	1023	handleRefType( aggrType, type2 );
	1024	}
	1025
[ee574a2]	1026	void postvisit( const ast::TraitInstType * aggrType ) {
[f474e91]	1027	handleRefType( aggrType, type2 );
	1028	}
	1029
[ee574a2]	1030	void postvisit( const ast::TypeInstType * typeInst ) {
[3e5dd913]	1031	assert( open.find( *typeInst ) == open.end() );
[f474e91]	1032	handleRefType( typeInst, type2 );
	1033	}
	1034
	1035	private:
	1036	/// Creates a tuple type based on a list of Type
[0bd46fd]	1037
[7870799]	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,
[f474e91]	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
[7870799]	1055	return unifyExact(
	1056	t1, tupleFromTypes( list2 ), env, need, have, open,
[ee574a2]	1057	noWiden(), symtab );
[f474e91]	1058	} else if ( ! isTuple1 && isTuple2 ) {
	1059	// combine entirety of list1, then unify
	1060	return unifyExact(
[7870799]	1061	tupleFromTypes( list1 ), t2, env, need, have, open,
[ee574a2]	1062	noWiden(), symtab );
[f474e91]	1063	}
	1064
[7870799]	1065	if ( ! unifyExact(
	1066	t1, t2, env, need, have, open, noWiden(), symtab )
[f474e91]	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;
[7870799]	1076	// xxx - this doesn't generate an empty tuple, contrary to comment; both ported
[f474e91]	1077	// from Rob's code
[7870799]	1078	return unifyExact(
	1079	t1, tupleFromTypes( list2 ), env, need, have, open,
[ee574a2]	1080	noWiden(), symtab );
[f474e91]	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;
[7870799]	1085	// xxx - this doesn't generate an empty tuple, contrary to comment; both ported
[f474e91]	1086	// from Rob's code
	1087	return unifyExact(
[7870799]	1088	tupleFromTypes( list1 ), t2, env, need, have, open,
[ee574a2]	1089	noWiden(), symtab );
[f474e91]	1090	}
	1091
	1092	return true;
	1093	}
	1094
	1095	public:
[ee574a2]	1096	void postvisit( const ast::TupleType * tuple ) {
[f474e91]	1097	auto tuple2 = dynamic_cast< const ast::TupleType * >( type2 );
	1098	if ( ! tuple2 ) return;
	1099
	1100	ast::Pass<TtypeExpander_new> expander{ tenv };
[ef9988b]	1101
[d3aa64f1]	1102	const ast::Type * flat = tuple->accept( expander );
	1103	const ast::Type * flat2 = tuple2->accept( expander );
[f474e91]	1104
	1105	auto types = flatten( flat );
	1106	auto types2 = flatten( flat2 );
	1107
	1108	result = unifyList( types, types2, tenv, need, have, open, symtab );
	1109	}
	1110
[ee574a2]	1111	void postvisit( const ast::VarArgsType * ) {
[f474e91]	1112	result = dynamic_cast< const ast::VarArgsType * >( type2 );
	1113	}
	1114
[ee574a2]	1115	void postvisit( const ast::ZeroType * ) {
[f474e91]	1116	result = dynamic_cast< const ast::ZeroType * >( type2 );
	1117	}
	1118
[ee574a2]	1119	void postvisit( const ast::OneType * ) {
[f474e91]	1120	result = dynamic_cast< const ast::OneType * >( type2 );
[7870799]	1121	}
[f474e91]	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
[0d070ca]	1128	// size_t Unify_new::traceId = Stats::Heap::new_stacktrace_id("Unify_new");
[7870799]	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,
[2773ab8]	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
[7870799]	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
[ee574a2]	1142	) {
	1143	ast::OpenVarSet closed;
	1144	findOpenVars( type1, open, closed, need, have, FirstClosed );
	1145	findOpenVars( type2, open, closed, need, have, FirstOpen );
[7870799]	1146	return unifyInexact(
[ee574a2]	1147	type1, type2, env, need, have, open, WidenMode{ true, true }, symtab, common );
	1148	}
	1149
[7870799]	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,
[f474e91]	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 );
[7870799]	1159	ast::OpenVarSet::const_iterator
[3e5dd913]	1160	entry1 = var1 ? open.find( *var1 ) : open.end(),
	1161	entry2 = var2 ? open.find( *var2 ) : open.end();
[f474e91]	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;
[7870799]	1167	return env.bindVarToVar(
[93c10de]	1168	var1, var2, ast::TypeData{ entry1->second, entry2->second }, need, have,
[f474e91]	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 {
[5d8dae7]	1175	return ast::Pass<Unify_new>::read(
	1176	type1, type2, env, need, have, open, widen, symtab );
[f474e91]	1177	}
	1178	}
	1179
[7870799]	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
[f474e91]	1185	) {
	1186	ast::CV::Qualifiers q1 = type1->qualifiers, q2 = type2->qualifiers;
[7870799]	1187
	1188	// force t1 and t2 to be cloned if their qualifiers must be stripped, so that type1 and
[f474e91]	1189	// type2 are left unchanged; calling convention forces type{1,2}->strong_ref >= 1
[2890212]	1190	ast::Type * t1 = shallowCopy(type1.get());
	1191	ast::Type * t2 = shallowCopy(type2.get());
	1192	t1->qualifiers = {};
	1193	t2->qualifiers = {};
[f49b3fc]	1194	ast::ptr< ast::Type > t1_(t1);
	1195	ast::ptr< ast::Type > t2_(t2);
[7870799]	1196
[f474e91]	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 ) ) ) {
[2890212]	1200	t1->qualifiers = q1 \| q2;
	1201	common = t1;
[f474e91]	1202	return true;
	1203	} else {
	1204	return false;
	1205	}
	1206
[0bd46fd]	1207	} else if (( common = commonType( t1, t2, env, need, have, open, widen, symtab ))) {
[f474e91]	1208	// no exact unification, but common type
[2890212]	1209	auto c = shallowCopy(common.get());
	1210	c->qualifiers = q1 \| q2;
	1211	common = c;
[f474e91]	1212	return true;
	1213	} else {
	1214	return false;
	1215	}
	1216	}
	1217
[54e41b3]	1218	ast::ptr<ast::Type> extractResultType( const ast::FunctionType * func ) {
[4139e3d]	1219	if ( func->returns.empty() ) return new ast::VoidType{};
[954c954]	1220	if ( func->returns.size() == 1 ) return func->returns[0];
[4139e3d]	1221
	1222	std::vector<ast::ptr<ast::Type>> tys;
[954c954]	1223	for ( const auto & decl : func->returns ) {
	1224	tys.emplace_back( decl );
[4139e3d]	1225	}
	1226	return new ast::TupleType{ std::move(tys) };
[54e41b3]	1227	}
[51b73452]	1228	} // namespace ResolvExpr
[a32b204]	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: