Context Navigation

source: src/ResolvExpr/Unify.cc @ 9191a8e

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc

Last change on this file since 9191a8e was e6cee92, checked in by Rob Schluntz <rschlunt@…>, 7 years ago
Fix TupleAssignment? code for references
Property mode set to `100644`
File size: 31.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
[4040425]	11	// Last Modified By : Peter A. Buhr
[6f95000]	12	// Last Modified On : Thu Mar 16 16:22:54 2017
	13	// Update Count : 42
[a32b204]	14	//
[51b7345]	15
	16	#include <set>
	17	#include <memory>
	18
	19	#include "Unify.h"
	20	#include "TypeEnvironment.h"
	21	#include "typeops.h"
	22	#include "FindOpenVars.h"
	23	#include "SynTree/Visitor.h"
	24	#include "SynTree/Type.h"
	25	#include "SynTree/Declaration.h"
	26	#include "SymTab/Indexer.h"
[d3b7937]	27	#include "Common/utility.h"
[53e3b4a]	28	#include "Tuples/Tuples.h"
[51b7345]	29
[1cbca6e]	30	// #define DEBUG
[51b7345]	31
	32	namespace ResolvExpr {
	33
[a32b204]	34	class Unify : public Visitor {
	35	public:
	36	Unify( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
[41a2620]	37
[a32b204]	38	bool get_result() const { return result; }
	39	private:
	40	virtual void visit(VoidType *voidType);
	41	virtual void visit(BasicType *basicType);
	42	virtual void visit(PointerType *pointerType);
	43	virtual void visit(ArrayType *arrayType);
[ce8c12f]	44	virtual void visit(ReferenceType *refType);
[a32b204]	45	virtual void visit(FunctionType *functionType);
	46	virtual void visit(StructInstType *aggregateUseType);
	47	virtual void visit(UnionInstType *aggregateUseType);
	48	virtual void visit(EnumInstType *aggregateUseType);
[4040425]	49	virtual void visit(TraitInstType *aggregateUseType);
[a32b204]	50	virtual void visit(TypeInstType *aggregateUseType);
	51	virtual void visit(TupleType *tupleType);
[44b7088]	52	virtual void visit(VarArgsType *varArgsType);
[89e6ffc]	53	virtual void visit(ZeroType *zeroType);
	54	virtual void visit(OneType *oneType);
[a32b204]	55
	56	template< typename RefType > void handleRefType( RefType inst, Type other );
[02ec390]	57	template< typename RefType > void handleGenericRefType( RefType inst, Type other );
[a32b204]	58
	59	bool result;
	60	Type *type2; // inherited
	61	TypeEnvironment &env;
	62	AssertionSet &needAssertions;
	63	AssertionSet &haveAssertions;
	64	const OpenVarSet &openVars;
	65	WidenMode widenMode;
	66	const SymTab::Indexer &indexer;
	67	};
	68
[eb50842]	69	/// Attempts an inexact unification of type1 and type2.
	70	/// Returns false if no such unification; if the types can be unified, sets common (unless they unify exactly and have identical type qualifiers)
[a32b204]	71	bool unifyInexact( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer, Type *&common );
	72	bool unifyExact( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
[41a2620]	73
[a32b204]	74	bool typesCompatible( Type first, Type second, const SymTab::Indexer &indexer, const TypeEnvironment &env ) {
	75	TypeEnvironment newEnv;
[1cbca6e]	76	OpenVarSet openVars, closedVars; // added closedVars
[a32b204]	77	AssertionSet needAssertions, haveAssertions;
	78	Type newFirst = first->clone(), newSecond = second->clone();
	79	env.apply( newFirst );
	80	env.apply( newSecond );
[1cbca6e]	81
	82	// do we need to do this? Seems like we do, types should be able to be compatible if they
	83	// have free variables that can unify
	84	findOpenVars( newFirst, openVars, closedVars, needAssertions, haveAssertions, false );
	85	findOpenVars( newSecond, openVars, closedVars, needAssertions, haveAssertions, true );
	86
[a32b204]	87	bool result = unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
	88	delete newFirst;
	89	delete newSecond;
	90	return result;
	91	}
	92
	93	bool typesCompatibleIgnoreQualifiers( Type first, Type second, const SymTab::Indexer &indexer, const TypeEnvironment &env ) {
	94	TypeEnvironment newEnv;
	95	OpenVarSet openVars;
	96	AssertionSet needAssertions, haveAssertions;
	97	Type newFirst = first->clone(), newSecond = second->clone();
	98	env.apply( newFirst );
	99	env.apply( newSecond );
	100	newFirst->get_qualifiers() = Type::Qualifiers();
	101	newSecond->get_qualifiers() = Type::Qualifiers();
[2c57025]	102	/// std::cerr << "first is ";
	103	/// first->print( std::cerr );
	104	/// std::cerr << std::endl << "second is ";
	105	/// second->print( std::cerr );
	106	/// std::cerr << std::endl << "newFirst is ";
	107	/// newFirst->print( std::cerr );
	108	/// std::cerr << std::endl << "newSecond is ";
	109	/// newSecond->print( std::cerr );
	110	/// std::cerr << std::endl;
[a32b204]	111	bool result = unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
	112	delete newFirst;
	113	delete newSecond;
	114	return result;
	115	}
	116
[d7dc824]	117	bool isFtype( Type *type ) {
[a32b204]	118	if ( dynamic_cast< FunctionType* >( type ) ) {
	119	return true;
	120	} else if ( TypeInstType typeInst = dynamic_cast< TypeInstType >( type ) ) {
	121	return typeInst->get_isFtype();
	122	} // if
	123	return false;
	124	}
	125
[d7dc824]	126	bool tyVarCompatible( const TypeDecl::Data & data, Type *type ) {
[2c57025]	127	switch ( data.kind ) {
[a32b204]	128	case TypeDecl::Any:
	129	case TypeDecl::Dtype:
[2c57025]	130	// to bind to an object type variable, the type must not be a function type.
	131	// if the type variable is specified to be a complete type then the incoming
	132	// type must also be complete
[6c3a988f]	133	// xxx - should this also check that type is not a tuple type and that it's not a ttype?
[d7dc824]	134	return ! isFtype( type ) && (! data.isComplete \|\| type->isComplete() );
[a32b204]	135	case TypeDecl::Ftype:
[d7dc824]	136	return isFtype( type );
[b2daebd4]	137	case TypeDecl::Ttype:
[6c3a988f]	138	// ttype unifies with any tuple type
[f3b0a07]	139	return dynamic_cast< TupleType * >( type ) \|\| Tuples::isTtype( type );
[a32b204]	140	} // switch
	141	return false;
	142	}
	143
[2c57025]	144	bool bindVar( TypeInstType typeInst, Type other, const TypeDecl::Data & data, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
[a32b204]	145	OpenVarSet::const_iterator tyvar = openVars.find( typeInst->get_name() );
	146	assert( tyvar != openVars.end() );
[d7dc824]	147	if ( ! tyVarCompatible( tyvar->second, other ) ) {
[a32b204]	148	return false;
	149	} // if
	150	if ( occurs( other, typeInst->get_name(), env ) ) {
	151	return false;
	152	} // if
	153	EqvClass curClass;
	154	if ( env.lookup( typeInst->get_name(), curClass ) ) {
	155	if ( curClass.type ) {
	156	Type *common = 0;
[eb50842]	157	// attempt to unify equivalence class type (which has qualifiers stripped, so they must be restored) with the type to bind to
[a32b204]	158	std::auto_ptr< Type > newType( curClass.type->clone() );
[721f17a]	159	newType->get_qualifiers() = typeInst->get_qualifiers();
[a32b204]	160	if ( unifyInexact( newType.get(), other, env, needAssertions, haveAssertions, openVars, widenMode & WidenMode( curClass.allowWidening, true ), indexer, common ) ) {
	161	if ( common ) {
	162	common->get_qualifiers() = Type::Qualifiers();
	163	delete curClass.type;
	164	curClass.type = common;
	165	env.add( curClass );
	166	} // if
	167	return true;
	168	} else {
	169	return false;
	170	} // if
	171	} else {
	172	curClass.type = other->clone();
	173	curClass.type->get_qualifiers() = Type::Qualifiers();
	174	curClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond;
	175	env.add( curClass );
	176	} // if
	177	} else {
	178	EqvClass newClass;
	179	newClass.vars.insert( typeInst->get_name() );
	180	newClass.type = other->clone();
	181	newClass.type->get_qualifiers() = Type::Qualifiers();
	182	newClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond;
[2c57025]	183	newClass.data = data;
[a32b204]	184	env.add( newClass );
	185	} // if
	186	return true;
	187	}
	188
[2c57025]	189	bool bindVarToVar( TypeInstType var1, TypeInstType var2, const TypeDecl::Data & data, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
[a32b204]	190	bool result = true;
	191	EqvClass class1, class2;
	192	bool hasClass1 = false, hasClass2 = false;
	193	bool widen1 = false, widen2 = false;
	194	Type type1 = 0, type2 = 0;
[41a2620]	195
[a32b204]	196	if ( env.lookup( var1->get_name(), class1 ) ) {
	197	hasClass1 = true;
	198	if ( class1.type ) {
	199	if ( occurs( class1.type, var2->get_name(), env ) ) {
	200	return false;
	201	} // if
	202	type1 = class1.type->clone();
	203	} // if
	204	widen1 = widenMode.widenFirst && class1.allowWidening;
	205	} // if
	206	if ( env.lookup( var2->get_name(), class2 ) ) {
	207	hasClass2 = true;
	208	if ( class2.type ) {
	209	if ( occurs( class2.type, var1->get_name(), env ) ) {
	210	return false;
	211	} // if
	212	type2 = class2.type->clone();
	213	} // if
	214	widen2 = widenMode.widenSecond && class2.allowWidening;
	215	} // if
[41a2620]	216
[a32b204]	217	if ( type1 && type2 ) {
[2c57025]	218	// std::cerr << "has type1 && type2" << std::endl;
[a32b204]	219	WidenMode newWidenMode ( widen1, widen2 );
	220	Type *common = 0;
	221	if ( unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, newWidenMode, indexer, common ) ) {
	222	class1.vars.insert( class2.vars.begin(), class2.vars.end() );
	223	class1.allowWidening = widen1 && widen2;
	224	if ( common ) {
	225	common->get_qualifiers() = Type::Qualifiers();
	226	delete class1.type;
	227	class1.type = common;
	228	} // if
	229	env.add( class1 );
	230	} else {
	231	result = false;
	232	} // if
	233	} else if ( hasClass1 && hasClass2 ) {
	234	if ( type1 ) {
	235	class1.vars.insert( class2.vars.begin(), class2.vars.end() );
	236	class1.allowWidening = widen1;
	237	env.add( class1 );
	238	} else {
	239	class2.vars.insert( class1.vars.begin(), class1.vars.end() );
	240	class2.allowWidening = widen2;
	241	env.add( class2 );
	242	} // if
	243	} else if ( hasClass1 ) {
	244	class1.vars.insert( var2->get_name() );
	245	class1.allowWidening = widen1;
	246	env.add( class1 );
	247	} else if ( hasClass2 ) {
	248	class2.vars.insert( var1->get_name() );
	249	class2.allowWidening = widen2;
	250	env.add( class2 );
	251	} else {
	252	EqvClass newClass;
	253	newClass.vars.insert( var1->get_name() );
	254	newClass.vars.insert( var2->get_name() );
	255	newClass.allowWidening = widen1 && widen2;
[2c57025]	256	newClass.data = data;
[a32b204]	257	env.add( newClass );
	258	} // if
	259	delete type1;
	260	delete type2;
	261	return result;
	262	}
	263
	264	bool unify( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
	265	OpenVarSet closedVars;
	266	findOpenVars( type1, openVars, closedVars, needAssertions, haveAssertions, false );
	267	findOpenVars( type2, openVars, closedVars, needAssertions, haveAssertions, true );
	268	Type *commonType = 0;
	269	if ( unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType ) ) {
	270	if ( commonType ) {
	271	delete commonType;
	272	} // if
	273	return true;
	274	} else {
	275	return false;
	276	} // if
	277	}
	278
	279	bool unify( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer, Type *&commonType ) {
	280	OpenVarSet closedVars;
	281	findOpenVars( type1, openVars, closedVars, needAssertions, haveAssertions, false );
	282	findOpenVars( type2, openVars, closedVars, needAssertions, haveAssertions, true );
	283	return unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType );
	284	}
	285
	286	bool unifyExact( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
[51b7345]	287	#ifdef DEBUG
[a32b204]	288	TypeEnvironment debugEnv( env );
[51b7345]	289	#endif
[eb50842]	290	if ( type1->get_qualifiers() != type2->get_qualifiers() ) {
	291	return false;
	292	}
	293
[a32b204]	294	bool result;
	295	TypeInstType var1 = dynamic_cast< TypeInstType >( type1 );
	296	TypeInstType var2 = dynamic_cast< TypeInstType >( type2 );
	297	OpenVarSet::const_iterator entry1, entry2;
	298	if ( var1 ) {
	299	entry1 = openVars.find( var1->get_name() );
	300	} // if
	301	if ( var2 ) {
	302	entry2 = openVars.find( var2->get_name() );
	303	} // if
	304	bool isopen1 = var1 && ( entry1 != openVars.end() );
	305	bool isopen2 = var2 && ( entry2 != openVars.end() );
[eb50842]	306
	307	if ( isopen1 && isopen2 && entry1->second == entry2->second ) {
[a32b204]	308	result = bindVarToVar( var1, var2, entry1->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
	309	} else if ( isopen1 ) {
	310	result = bindVar( var1, type2, entry1->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
	311	} else if ( isopen2 ) {
	312	result = bindVar( var2, type1, entry2->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
	313	} else {
	314	Unify comparator( type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
	315	type1->accept( comparator );
	316	result = comparator.get_result();
	317	} // if
[51b7345]	318	#ifdef DEBUG
[2c57025]	319	std::cerr << "============ unifyExact" << std::endl;
	320	std::cerr << "type1 is ";
	321	type1->print( std::cerr );
	322	std::cerr << std::endl << "type2 is ";
	323	type2->print( std::cerr );
	324	std::cerr << std::endl << "openVars are ";
	325	printOpenVarSet( openVars, std::cerr, 8 );
	326	std::cerr << std::endl << "input env is " << std::endl;
	327	debugEnv.print( std::cerr, 8 );
	328	std::cerr << std::endl << "result env is " << std::endl;
	329	env.print( std::cerr, 8 );
	330	std::cerr << "result is " << result << std::endl;
[51b7345]	331	#endif
[a32b204]	332	return result;
	333	}
	334
	335	bool unifyExact( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
	336	return unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
	337	}
	338
	339	bool unifyInexact( Type type1, Type type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer, Type *&common ) {
	340	Type::Qualifiers tq1 = type1->get_qualifiers(), tq2 = type2->get_qualifiers();
	341	type1->get_qualifiers() = Type::Qualifiers();
	342	type2->get_qualifiers() = Type::Qualifiers();
	343	bool result;
[51b7345]	344	#ifdef DEBUG
[2c57025]	345	std::cerr << "unifyInexact type 1 is ";
	346	type1->print( std::cerr );
[0b150ec]	347	std::cerr << " type 2 is ";
[2c57025]	348	type2->print( std::cerr );
	349	std::cerr << std::endl;
[51b7345]	350	#endif
[a32b204]	351	if ( ! unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer ) ) {
[51b7345]	352	#ifdef DEBUG
[2c57025]	353	std::cerr << "unifyInexact: no exact unification found" << std::endl;
[51b7345]	354	#endif
[a32b204]	355	if ( ( common = commonType( type1, type2, widenMode.widenFirst, widenMode.widenSecond, indexer, env, openVars ) ) ) {
[6f95000]	356	common->get_qualifiers() = tq1 \| tq2;
[51b7345]	357	#ifdef DEBUG
[2c57025]	358	std::cerr << "unifyInexact: common type is ";
	359	common->print( std::cerr );
	360	std::cerr << std::endl;
[51b7345]	361	#endif
[a32b204]	362	result = true;
	363	} else {
[51b7345]	364	#ifdef DEBUG
[2c57025]	365	std::cerr << "unifyInexact: no common type found" << std::endl;
[51b7345]	366	#endif
[a32b204]	367	result = false;
	368	} // if
	369	} else {
	370	if ( tq1 != tq2 ) {
	371	if ( ( tq1 > tq2 \|\| widenMode.widenFirst ) && ( tq2 > tq1 \|\| widenMode.widenSecond ) ) {
	372	common = type1->clone();
[6f95000]	373	common->get_qualifiers() = tq1 \| tq2;
[a32b204]	374	result = true;
	375	} else {
	376	result = false;
	377	} // if
	378	} else {
[e6cee92]	379	common = type1->clone();
	380	common->get_qualifiers() = tq1 \| tq2;
[a32b204]	381	result = true;
	382	} // if
	383	} // if
	384	type1->get_qualifiers() = tq1;
	385	type2->get_qualifiers() = tq2;
	386	return result;
	387	}
	388
	389	Unify::Unify( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer )
	390	: result( false ), type2( type2 ), env( env ), needAssertions( needAssertions ), haveAssertions( haveAssertions ), openVars( openVars ), widenMode( widenMode ), indexer( indexer ) {
	391	}
	392
[af397ef8]	393	void Unify::visit( __attribute__((unused)) VoidType *voidType) {
[a32b204]	394	result = dynamic_cast< VoidType* >( type2 );
	395	}
	396
	397	void Unify::visit(BasicType *basicType) {
	398	if ( BasicType otherBasic = dynamic_cast< BasicType >( type2 ) ) {
	399	result = basicType->get_kind() == otherBasic->get_kind();
	400	} // if
	401	}
	402
	403	void markAssertionSet( AssertionSet &assertions, DeclarationWithType *assert ) {
[2c57025]	404	/// std::cerr << "assertion set is" << std::endl;
	405	/// printAssertionSet( assertions, std::cerr, 8 );
	406	/// std::cerr << "looking for ";
	407	/// assert->print( std::cerr );
	408	/// std::cerr << std::endl;
[a32b204]	409	AssertionSet::iterator i = assertions.find( assert );
	410	if ( i != assertions.end() ) {
[2c57025]	411	/// std::cerr << "found it!" << std::endl;
[6c3a988f]	412	i->second.isUsed = true;
[a32b204]	413	} // if
	414	}
	415
	416	void markAssertions( AssertionSet &assertion1, AssertionSet &assertion2, Type *type ) {
[aefcc3b]	417	for ( std::list< TypeDecl* >::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
[a32b204]	418	for ( std::list< DeclarationWithType* >::const_iterator assert = (tyvar)->get_assertions().begin(); assert != (tyvar)->get_assertions().end(); ++assert ) {
	419	markAssertionSet( assertion1, *assert );
	420	markAssertionSet( assertion2, *assert );
	421	} // for
	422	} // for
	423	}
	424
	425	void Unify::visit(PointerType *pointerType) {
	426	if ( PointerType otherPointer = dynamic_cast< PointerType >( type2 ) ) {
	427	result = unifyExact( pointerType->get_base(), otherPointer->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
	428	markAssertions( haveAssertions, needAssertions, pointerType );
	429	markAssertions( haveAssertions, needAssertions, otherPointer );
	430	} // if
	431	}
	432
[ce8c12f]	433	void Unify::visit(ReferenceType *refType) {
	434	if ( ReferenceType otherRef = dynamic_cast< ReferenceType >( type2 ) ) {
	435	result = unifyExact( refType->get_base(), otherRef->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
	436	markAssertions( haveAssertions, needAssertions, refType );
	437	markAssertions( haveAssertions, needAssertions, otherRef );
	438	} // if
	439	}
	440
[a32b204]	441	void Unify::visit(ArrayType *arrayType) {
	442	ArrayType otherArray = dynamic_cast< ArrayType >( type2 );
[1cbca6e]	443	// to unify, array types must both be VLA or both not VLA
	444	// and must both have a dimension expression or not have a dimension
[41a2620]	445	if ( otherArray && arrayType->get_isVarLen() == otherArray->get_isVarLen() ) {
[1cbca6e]	446
	447	// not positive this is correct in all cases, but it's needed for typedefs
	448	if ( arrayType->get_isVarLen() \|\| otherArray->get_isVarLen() ) {
	449	return;
	450	}
	451
	452	if ( ! arrayType->get_isVarLen() && ! otherArray->get_isVarLen() &&
	453	arrayType->get_dimension() != 0 && otherArray->get_dimension() != 0 ) {
	454	ConstantExpr * ce1 = dynamic_cast< ConstantExpr * >( arrayType->get_dimension() );
	455	ConstantExpr * ce2 = dynamic_cast< ConstantExpr * >( otherArray->get_dimension() );
[41a2620]	456	// see C11 Reference Manual 6.7.6.2.6
	457	// two array types with size specifiers that are integer constant expressions are
	458	// compatible if both size specifiers have the same constant value
	459	if ( ce1 && ce2 ) {
	460	Constant * c1 = ce1->get_constant();
	461	Constant * c2 = ce2->get_constant();
	462
	463	if ( c1->get_value() != c2->get_value() ) {
	464	// does not unify if the dimension is different
	465	return;
	466	}
[1cbca6e]	467	}
	468	}
	469
[a32b204]	470	result = unifyExact( arrayType->get_base(), otherArray->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
	471	} // if
	472	}
	473
[f3b0a07]	474	template< typename Iterator, typename Func >
	475	std::unique_ptr<Type> combineTypes( Iterator begin, Iterator end, Func & toType ) {
[53e3b4a]	476	std::list< Type * > types;
	477	for ( ; begin != end; ++begin ) {
[64eae56]	478	// it's guaranteed that a ttype variable will be bound to a flat tuple, so ensure that this results in a flat tuple
[f3b0a07]	479	flatten( toType( *begin ), back_inserter( types ) );
[53e3b4a]	480	}
[6c3a988f]	481	return std::unique_ptr<Type>( new TupleType( Type::Qualifiers(), types ) );
[53e3b4a]	482	}
	483
[a32b204]	484	template< typename Iterator1, typename Iterator2 >
	485	bool unifyDeclList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
[f3b0a07]	486	auto get_type = [](DeclarationWithType * dwt){ return dwt->get_type(); };
[a32b204]	487	for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) {
[53e3b4a]	488	Type * t1 = (*list1Begin)->get_type();
	489	Type * t2 = (*list2Begin)->get_type();
	490	bool isTtype1 = Tuples::isTtype( t1 );
	491	bool isTtype2 = Tuples::isTtype( t2 );
[6c3a988f]	492	// xxx - assumes ttype must be last parameter
	493	// xxx - there may be a nice way to refactor this, but be careful because the argument positioning might matter in some cases.
[53e3b4a]	494	if ( isTtype1 && ! isTtype2 ) {
	495	// combine all of the things in list2, then unify
[f3b0a07]	496	return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
[53e3b4a]	497	} else if ( isTtype2 && ! isTtype1 ) {
	498	// combine all of the things in list1, then unify
[f3b0a07]	499	return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
[53e3b4a]	500	} else if ( ! unifyExact( t1, t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ) ) {
[a32b204]	501	return false;
	502	} // if
	503	} // for
[6c3a988f]	504	// 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]	505	if ( list1Begin != list1End ) {
	506	// try unifying empty tuple type with ttype
	507	Type * t1 = (*list1Begin)->get_type();
	508	if ( Tuples::isTtype( t1 ) ) {
[f3b0a07]	509	return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
[4c8621ac]	510	} else return false;
	511	} else if ( list2Begin != list2End ) {
	512	// try unifying empty tuple type with ttype
	513	Type * t2 = (*list2Begin)->get_type();
	514	if ( Tuples::isTtype( t2 ) ) {
[f3b0a07]	515	return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
[4c8621ac]	516	} else return false;
[a32b204]	517	} else {
	518	return true;
	519	} // if
	520	}
	521
[6c3a988f]	522	/// Finds ttypes and replaces them with their expansion, if known.
	523	/// This needs to be done so that satisfying ttype assertions is easier.
	524	/// If this isn't done then argument lists can have wildly different
	525	/// size and structure, when they should be compatible.
	526	struct TtypeExpander : public Mutator {
	527	TypeEnvironment & env;
	528	TtypeExpander( TypeEnvironment & env ) : env( env ) {}
	529	Type * mutate( TypeInstType * typeInst ) {
	530	EqvClass eqvClass;
	531	if ( env.lookup( typeInst->get_name(), eqvClass ) ) {
	532	if ( eqvClass.data.kind == TypeDecl::Ttype ) {
	533	// expand ttype parameter into its actual type
	534	if ( eqvClass.type ) {
	535	delete typeInst;
	536	return eqvClass.type->clone();
	537	}
	538	}
	539	}
	540	return typeInst;
	541	}
	542	};
	543
	544	/// flattens a list of declarations, so that each tuple type has a single declaration.
	545	/// makes use of TtypeExpander to ensure ttypes are flat as well.
	546	void flattenList( std::list< DeclarationWithType * > src, std::list< DeclarationWithType * > & dst, TypeEnvironment & env ) {
	547	dst.clear();
	548	for ( DeclarationWithType * dcl : src ) {
	549	TtypeExpander expander( env );
	550	dcl->acceptMutator( expander );
	551	std::list< Type * > types;
	552	flatten( dcl->get_type(), back_inserter( types ) );
	553	for ( Type * t : types ) {
[68fe077a]	554	dst.push_back( new ObjectDecl( "", Type::StorageClasses(), LinkageSpec::C, nullptr, t, nullptr ) );
[6c3a988f]	555	}
	556	delete dcl;
	557	}
	558	}
	559
[a32b204]	560	void Unify::visit(FunctionType *functionType) {
	561	FunctionType otherFunction = dynamic_cast< FunctionType >( type2 );
	562	if ( otherFunction && functionType->get_isVarArgs() == otherFunction->get_isVarArgs() ) {
[6c3a988f]	563	// flatten the parameter lists for both functions so that tuple structure
	564	// doesn't affect unification. Must be a clone so that the types don't change.
	565	std::unique_ptr<FunctionType> flatFunc( functionType->clone() );
	566	std::unique_ptr<FunctionType> flatOther( otherFunction->clone() );
	567	flattenList( flatFunc->get_parameters(), flatFunc->get_parameters(), env );
	568	flattenList( flatOther->get_parameters(), flatOther->get_parameters(), env );
	569
[53e3b4a]	570	// sizes don't have to match if ttypes are involved; need to be more precise wrt where the ttype is to prevent errors
[6c3a988f]	571	if ( (flatFunc->get_parameters().size() == flatOther->get_parameters().size() && flatFunc->get_returnVals().size() == flatOther->get_returnVals().size()) \|\| flatFunc->isTtype() \|\| flatOther->isTtype() ) {
	572	if ( unifyDeclList( flatFunc->get_parameters().begin(), flatFunc->get_parameters().end(), flatOther->get_parameters().begin(), flatOther->get_parameters().end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
	573	if ( unifyDeclList( flatFunc->get_returnVals().begin(), flatFunc->get_returnVals().end(), flatOther->get_returnVals().begin(), flatOther->get_returnVals().end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
[1cbca6e]	574
[6c3a988f]	575	// the original types must be used in mark assertions, since pointer comparisons are used
[03da511]	576	markAssertions( haveAssertions, needAssertions, functionType );
	577	markAssertions( haveAssertions, needAssertions, otherFunction );
[41a2620]	578
[03da511]	579	result = true;
	580	} // if
[a32b204]	581	} // if
	582	} // if
	583	} // if
	584	}
	585
	586	template< typename RefType >
[02ec390]	587	void Unify::handleRefType( RefType inst, Type other ) {
	588	// check that other type is compatible and named the same
[a32b204]	589	RefType otherStruct = dynamic_cast< RefType >( other );
	590	result = otherStruct && inst->get_name() == otherStruct->get_name();
[02ec390]	591	}
	592
	593	template< typename RefType >
	594	void Unify::handleGenericRefType( RefType inst, Type other ) {
	595	// Check that other type is compatible and named the same
	596	handleRefType( inst, other );
	597	if ( ! result ) return;
[f5234f3]	598	// Check that parameters of types unify, if any
[02ec390]	599	std::list< Expression* > params = inst->get_parameters();
[f5234f3]	600	std::list< Expression* > otherParams = ((RefType*)other)->get_parameters();
	601
	602	std::list< Expression* >::const_iterator it = params.begin(), jt = otherParams.begin();
	603	for ( ; it != params.end() && jt != otherParams.end(); ++it, ++jt ) {
	604	TypeExpr param = dynamic_cast< TypeExpr >(*it);
[b2daebd4]	605	assertf(param, "Aggregate parameters should be type expressions");
[f5234f3]	606	TypeExpr otherParam = dynamic_cast< TypeExpr >(*jt);
[b2daebd4]	607	assertf(otherParam, "Aggregate parameters should be type expressions");
[ce8c12f]	608
[b2daebd4]	609	Type* paramTy = param->get_type();
	610	Type* otherParamTy = otherParam->get_type();
[f5234f3]	611
[b2daebd4]	612	bool tupleParam = Tuples::isTtype( paramTy );
	613	bool otherTupleParam = Tuples::isTtype( otherParamTy );
	614
	615	if ( tupleParam && otherTupleParam ) {
	616	++it; ++jt; // skip ttype parameters for break
	617	} else if ( tupleParam ) {
	618	// bundle other parameters into tuple to match
[62423350]	619	std::list< Type * > binderTypes;
[b2daebd4]	620
	621	do {
[62423350]	622	binderTypes.push_back( otherParam->get_type()->clone() );
[b2daebd4]	623	++jt;
	624
	625	if ( jt == otherParams.end() ) break;
	626
	627	otherParam = dynamic_cast< TypeExpr* >(*jt);
	628	assertf(otherParam, "Aggregate parameters should be type expressions");
	629	} while (true);
	630
[62423350]	631	otherParamTy = new TupleType{ paramTy->get_qualifiers(), binderTypes };
[b2daebd4]	632	++it; // skip ttype parameter for break
	633	} else if ( otherTupleParam ) {
	634	// bundle parameters into tuple to match other
[62423350]	635	std::list< Type * > binderTypes;
[b2daebd4]	636
	637	do {
[62423350]	638	binderTypes.push_back( param->get_type()->clone() );
[b2daebd4]	639	++it;
	640
	641	if ( it == params.end() ) break;
	642
	643	param = dynamic_cast< TypeExpr* >(*it);
	644	assertf(param, "Aggregate parameters should be type expressions");
	645	} while (true);
	646
[62423350]	647	paramTy = new TupleType{ otherParamTy->get_qualifiers(), binderTypes };
[b2daebd4]	648	++jt; // skip ttype parameter for break
	649	}
	650
	651	if ( ! unifyExact( paramTy, otherParamTy, env, needAssertions, haveAssertions, openVars, WidenMode(false, false), indexer ) ) {
[02ec390]	652	result = false;
	653	return;
	654	}
[b2daebd4]	655
	656	// ttype parameter should be last
	657	if ( tupleParam \|\| otherTupleParam ) break;
[02ec390]	658	}
[f5234f3]	659	result = ( it == params.end() && jt == otherParams.end() );
[02ec390]	660	}
[a32b204]	661
	662	void Unify::visit(StructInstType *structInst) {
[02ec390]	663	handleGenericRefType( structInst, type2 );
[a32b204]	664	}
	665
	666	void Unify::visit(UnionInstType *unionInst) {
[02ec390]	667	handleGenericRefType( unionInst, type2 );
[a32b204]	668	}
	669
	670	void Unify::visit(EnumInstType *enumInst) {
	671	handleRefType( enumInst, type2 );
	672	}
	673
[4040425]	674	void Unify::visit(TraitInstType *contextInst) {
[a32b204]	675	handleRefType( contextInst, type2 );
	676	}
	677
	678	void Unify::visit(TypeInstType *typeInst) {
	679	assert( openVars.find( typeInst->get_name() ) == openVars.end() );
	680	TypeInstType otherInst = dynamic_cast< TypeInstType >( type2 );
	681	if ( otherInst && typeInst->get_name() == otherInst->get_name() ) {
	682	result = true;
[51b7345]	683	/// } else {
	684	/// NamedTypeDecl *nt = indexer.lookupType( typeInst->get_name() );
[a32b204]	685	/// if ( nt ) {
[51b7345]	686	/// TypeDecl type = dynamic_cast< TypeDecl >( nt );
	687	/// assert( type );
[a32b204]	688	/// if ( type->get_base() ) {
[51b7345]	689	/// result = unifyExact( type->get_base(), typeInst, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
	690	/// }
	691	/// }
[a32b204]	692	} // if
	693	}
	694
	695	template< typename Iterator1, typename Iterator2 >
[c77fd8b]	696	bool unifyList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
[f3b0a07]	697	auto get_type = [](Type * t) { return t; };
[a32b204]	698	for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) {
[f3b0a07]	699	Type * t1 = *list1Begin;
	700	Type * t2 = *list2Begin;
	701	bool isTtype1 = Tuples::isTtype( t1 );
	702	bool isTtype2 = Tuples::isTtype( t2 );
	703	// xxx - assumes ttype must be last parameter
	704	// xxx - there may be a nice way to refactor this, but be careful because the argument positioning might matter in some cases.
	705	if ( isTtype1 && ! isTtype2 ) {
	706	// combine all of the things in list2, then unify
	707	return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
	708	} else if ( isTtype2 && ! isTtype1 ) {
	709	// combine all of the things in list1, then unify
	710	return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
	711	} else if ( ! unifyExact( t1, t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ) ) {
[a32b204]	712	return false;
[f3b0a07]	713	} // if
	714
[a32b204]	715	} // for
[f3b0a07]	716	if ( list1Begin != list1End ) {
	717	// try unifying empty tuple type with ttype
	718	Type * t1 = *list1Begin;
	719	if ( Tuples::isTtype( t1 ) ) {
	720	return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
	721	} else return false;
	722	} else if ( list2Begin != list2End ) {
	723	// try unifying empty tuple type with ttype
	724	Type * t2 = *list2Begin;
	725	if ( Tuples::isTtype( t2 ) ) {
	726	return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
	727	} else return false;
[a32b204]	728	} else {
	729	return true;
[f3b0a07]	730	} // if
[a32b204]	731	}
	732
	733	void Unify::visit(TupleType *tupleType) {
	734	if ( TupleType otherTuple = dynamic_cast< TupleType >( type2 ) ) {
[f3b0a07]	735	std::unique_ptr<TupleType> flat1( tupleType->clone() );
	736	std::unique_ptr<TupleType> flat2( otherTuple->clone() );
	737	std::list<Type *> types1, types2;
	738
	739	TtypeExpander expander( env );
	740	flat1->acceptMutator( expander );
	741	flat2->acceptMutator( expander );
	742
	743	flatten( flat1.get(), back_inserter( types1 ) );
	744	flatten( flat2.get(), back_inserter( types2 ) );
	745
[c77fd8b]	746	result = unifyList( types1.begin(), types1.end(), types2.begin(), types2.end(), env, needAssertions, haveAssertions, openVars, indexer );
[a32b204]	747	} // if
	748	}
[51b7345]	749
[af397ef8]	750	void Unify::visit( __attribute__((unused)) VarArgsType *varArgsType ) {
[44b7088]	751	result = dynamic_cast< VarArgsType* >( type2 );
	752	}
	753
[af397ef8]	754	void Unify::visit( __attribute__((unused)) ZeroType *zeroType ) {
[89e6ffc]	755	result = dynamic_cast< ZeroType* >( type2 );
	756	}
	757
[af397ef8]	758	void Unify::visit( __attribute__((unused)) OneType *oneType ) {
[89e6ffc]	759	result = dynamic_cast< OneType* >( type2 );
	760	}
	761
[906e24d]	762	// xxx - compute once and store in the FunctionType?
	763	Type * extractResultType( FunctionType * function ) {
	764	if ( function->get_returnVals().size() == 0 ) {
	765	return new VoidType( Type::Qualifiers() );
	766	} else if ( function->get_returnVals().size() == 1 ) {
	767	return function->get_returnVals().front()->get_type()->clone();
	768	} else {
[62423350]	769	std::list< Type * > types;
[906e24d]	770	for ( DeclarationWithType * decl : function->get_returnVals() ) {
[62423350]	771	types.push_back( decl->get_type()->clone() );
[906e24d]	772	} // for
[62423350]	773	return new TupleType( Type::Qualifiers(), types );
[906e24d]	774	}
	775	}
[51b7345]	776	} // namespace ResolvExpr
[a32b204]	777
	778	// Local Variables: //
	779	// tab-width: 4 //
	780	// mode: c++ //
	781	// compile-command: "make install" //
	782	// End: //

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

Download in other formats: