Context Navigation

source: src/ResolvExpr/Unify.cc@ fed6a0f

Visit:

ADT ast-experimental

Last change on this file since fed6a0f was e563edf, checked in by Andrew Beach <ajbeach@…>, 3 years ago
Header Clean-up: Clearing out typeops, moving things to Unify because that header already exist.
Property mode set to `100644`
File size: 48.9 KB

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

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

Download in other formats: