Context Navigation

source: src/ResolvExpr/Unify.cc@ 2ed94a9

Visit:

ADT

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

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

Download in other formats: