Context Navigation

source: src/GenPoly/GenPoly.cc@ 77de429

Visit:

ADT ast-experimental

Last change on this file since 77de429 was c8837e5, checked in by Andrew Beach <ajbeach@…>, 3 years ago
Rewrite in GenPoly to avoid mixing new AST and TyVarMap (which internally has old AST code). Some nearby functions got writen out even though they are not used, and hence not tested.
Property mode set to `100644`
File size: 31.5 KB

Rev	Line
[51587aa]	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	//
[540de412]	7	// GenPoly.cc --
[51587aa]	8	//
	9	// Author : Richard C. Bilson
	10	// Created On : Mon May 18 07:44:20 2015
[3606fe4]	11	// Last Modified By : Andrew Beach
[c8837e5]	12	// Last Modified On : Fri Oct 7 15:25:00 2022
	13	// Update Count : 16
[51587aa]	14	//
[51b73452]	15
	16	#include "GenPoly.h"
[ffad73a]	17
[08fc48f]	18	#include <cassert> // for assertf, assert
	19	#include <iostream> // for operator<<, ostream, basic_os...
	20	#include <iterator> // for back_insert_iterator, back_in...
	21	#include <list> // for list, _List_iterator, list<>:...
	22	#include <typeindex> // for type_index
	23	#include <utility> // for pair
	24	#include <vector> // for vector
	25
[d76c588]	26	#include "AST/Type.hpp"
[08fc48f]	27	#include "GenPoly/ErasableScopedMap.h" // for ErasableScopedMap<>::const_it...
	28	#include "ResolvExpr/typeops.h" // for flatten
	29	#include "SynTree/Constant.h" // for Constant
	30	#include "SynTree/Expression.h" // for Expression, TypeExpr, Constan...
	31	#include "SynTree/Type.h" // for Type, StructInstType, UnionIn...
	32	#include "SynTree/TypeSubstitution.h" // for TypeSubstitution
[51b73452]	33
[b1a6d6b]	34	using namespace std;
[51b73452]	35
	36	namespace GenPoly {
[ffad73a]	37	namespace {
[0f889a77]	38	/// Checks a parameter list for polymorphic parameters; will substitute according to env if present
	39	bool hasPolyParams( std::list< Expression* >& params, const TypeSubstitution *env ) {
	40	for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
	41	TypeExpr paramType = dynamic_cast< TypeExpr >( *param );
[7350ff97]	42	assertf(paramType, "Aggregate parameters should be type expressions");
[0f889a77]	43	if ( isPolyType( paramType->get_type(), env ) ) return true;
	44	}
	45	return false;
	46	}
	47
[490fb92e]	48	bool hasPolyParams( const std::vector<ast::ptr<ast::Expr>> & params, const ast::TypeSubstitution * env) {
	49	for (auto &param : params) {
	50	auto paramType = param.strict_as<ast::TypeExpr>();
	51	if (isPolyType(paramType->type, env)) return true;
	52	}
	53	return false;
	54	}
	55
[0f889a77]	56	/// Checks a parameter list for polymorphic parameters from tyVars; will substitute according to env if present
[ffad73a]	57	bool hasPolyParams( std::list< Expression* >& params, const TyVarMap &tyVars, const TypeSubstitution *env ) {
	58	for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
	59	TypeExpr paramType = dynamic_cast< TypeExpr >( *param );
[5a3ac84]	60	assertf(paramType, "Aggregate parameters should be type expressions");
[ffad73a]	61	if ( isPolyType( paramType->get_type(), tyVars, env ) ) return true;
	62	}
	63	return false;
	64	}
[3bb195cb]	65
	66	/// Checks a parameter list for dynamic-layout parameters from tyVars; will substitute according to env if present
	67	bool hasDynParams( std::list< Expression* >& params, const TyVarMap &tyVars, const TypeSubstitution *env ) {
	68	for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
	69	TypeExpr paramType = dynamic_cast< TypeExpr >( *param );
[5a3ac84]	70	assertf(paramType, "Aggregate parameters should be type expressions");
[3bb195cb]	71	if ( isDynType( paramType->get_type(), tyVars, env ) ) return true;
	72	}
	73	return false;
	74	}
[5a3ac84]	75
[c8837e5]	76	bool hasDynParams(
	77	const std::vector<ast::ptr<ast::Expr>> & params,
	78	const TypeVarMap & typeVars,
	79	const ast::TypeSubstitution * subst ) {
	80	for ( ast::ptr<ast::Expr> const & paramExpr : params ) {
	81	auto param = paramExpr.as<ast::TypeExpr>();
	82	assertf( param, "Aggregate parameters should be type expressions." );
	83	if ( isDynType( param->type.get(), typeVars, subst ) ) {
[3606fe4]	84	return true;
	85	}
	86	}
	87	return false;
	88	}
	89
[5a3ac84]	90	/// Checks a parameter list for inclusion of polymorphic parameters; will substitute according to env if present
	91	bool includesPolyParams( std::list< Expression* >& params, const TypeSubstitution *env ) {
	92	for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
	93	TypeExpr paramType = dynamic_cast< TypeExpr >( *param );
	94	assertf(paramType, "Aggregate parameters should be type expressions");
	95	if ( includesPolyType( paramType->get_type(), env ) ) return true;
	96	}
	97	return false;
	98	}
	99
	100	/// Checks a parameter list for inclusion of polymorphic parameters from tyVars; will substitute according to env if present
	101	bool includesPolyParams( std::list< Expression* >& params, const TyVarMap &tyVars, const TypeSubstitution *env ) {
	102	for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
	103	TypeExpr paramType = dynamic_cast< TypeExpr >( *param );
	104	assertf(paramType, "Aggregate parameters should be type expressions");
	105	if ( includesPolyType( paramType->get_type(), tyVars, env ) ) return true;
	106	}
	107	return false;
	108	}
[c2ad3c9]	109	}
[83de11e]	110
[c2ad3c9]	111	Type* replaceTypeInst( Type* type, const TypeSubstitution* env ) {
	112	if ( ! env ) return type;
	113	if ( TypeInstType typeInst = dynamic_cast< TypeInstType >( type ) ) {
	114	Type *newType = env->lookup( typeInst->get_name() );
	115	if ( newType ) return newType;
[e24955a]	116	}
[c2ad3c9]	117	return type;
[ffad73a]	118	}
[0f889a77]	119
[490fb92e]	120	const ast::Type * replaceTypeInst(const ast::Type * type, const ast::TypeSubstitution * env) {
	121	if (!env) return type;
	122	if (auto typeInst = dynamic_cast<const ast::TypeInstType*> (type)) {
[3e5dd913]	123	auto newType = env->lookup(typeInst);
[490fb92e]	124	if (newType) return newType;
	125	}
	126	return type;
	127	}
	128
[0f889a77]	129	Type isPolyType( Type type, const TypeSubstitution *env ) {
[e24955a]	130	type = replaceTypeInst( type, env );
[83de11e]	131
[ca35c51]	132	if ( dynamic_cast< TypeInstType * >( type ) ) {
[0f889a77]	133	return type;
[5f61546]	134	} else if ( ArrayType * arrayType = dynamic_cast< ArrayType * >( type ) ) {
	135	return isPolyType( arrayType->base, env );
[0f889a77]	136	} else if ( StructInstType structType = dynamic_cast< StructInstType >( type ) ) {
	137	if ( hasPolyParams( structType->get_parameters(), env ) ) return type;
	138	} else if ( UnionInstType unionType = dynamic_cast< UnionInstType >( type ) ) {
	139	if ( hasPolyParams( unionType->get_parameters(), env ) ) return type;
	140	}
	141	return 0;
	142	}
[540de412]	143
[490fb92e]	144	const ast::Type * isPolyType(const ast::Type * type, const ast::TypeSubstitution * env) {
	145	type = replaceTypeInst( type, env );
	146
	147	if ( dynamic_cast< const ast::TypeInstType * >( type ) ) {
	148	return type;
	149	} else if ( auto arrayType = dynamic_cast< const ast::ArrayType * >( type ) ) {
	150	return isPolyType( arrayType->base, env );
	151	} else if ( auto structType = dynamic_cast< const ast::StructInstType* >( type ) ) {
	152	if ( hasPolyParams( structType->params, env ) ) return type;
	153	} else if ( auto unionType = dynamic_cast< const ast::UnionInstType* >( type ) ) {
	154	if ( hasPolyParams( unionType->params, env ) ) return type;
	155	}
	156	return 0;
	157	}
	158
[ffad73a]	159	Type isPolyType( Type type, const TyVarMap &tyVars, const TypeSubstitution *env ) {
[e24955a]	160	type = replaceTypeInst( type, env );
[83de11e]	161
[e56cfdb0]	162	if ( TypeInstType typeInst = dynamic_cast< TypeInstType >( type ) ) {
[ffad73a]	163	if ( tyVars.find( typeInst->get_name() ) != tyVars.end() ) {
	164	return type;
[0f889a77]	165	}
[5f61546]	166	} else if ( ArrayType * arrayType = dynamic_cast< ArrayType * >( type ) ) {
	167	return isPolyType( arrayType->base, tyVars, env );
[ffad73a]	168	} else if ( StructInstType structType = dynamic_cast< StructInstType >( type ) ) {
	169	if ( hasPolyParams( structType->get_parameters(), tyVars, env ) ) return type;
	170	} else if ( UnionInstType unionType = dynamic_cast< UnionInstType >( type ) ) {
	171	if ( hasPolyParams( unionType->get_parameters(), tyVars, env ) ) return type;
	172	}
	173	return 0;
[01aeade]	174	}
[b1a6d6b]	175
[490fb92e]	176	const ast::Type * isPolyType(const ast::Type * type, const TyVarMap & tyVars, const ast::TypeSubstitution * env) {
	177	type = replaceTypeInst( type, env );
	178
	179	if ( auto typeInst = dynamic_cast< const ast::TypeInstType * >( type ) ) {
[3e5dd913]	180	return tyVars.find(typeInst->typeString()) != tyVars.end() ? type : nullptr;
[490fb92e]	181	} else if ( auto arrayType = dynamic_cast< const ast::ArrayType * >( type ) ) {
	182	return isPolyType( arrayType->base, env );
	183	} else if ( auto structType = dynamic_cast< const ast::StructInstType* >( type ) ) {
	184	if ( hasPolyParams( structType->params, env ) ) return type;
	185	} else if ( auto unionType = dynamic_cast< const ast::UnionInstType* >( type ) ) {
	186	if ( hasPolyParams( unionType->params, env ) ) return type;
	187	}
	188	return nullptr;
	189	}
	190
[c8837e5]	191	const ast::Type * isPolyType( const ast::Type * type,
	192	const TypeVarMap & typeVars, const ast::TypeSubstitution * subst ) {
	193	type = replaceTypeInst( type, subst );
	194
	195	if ( auto inst = dynamic_cast< const ast::TypeInstType * >( type ) ) {
	196	if ( typeVars.find( inst->typeString() ) != typeVars.end() ) return type;
	197	} else if ( auto array = dynamic_cast< const ast::ArrayType * >( type ) ) {
	198	return isPolyType( array->base, subst );
	199	} else if ( auto sue = dynamic_cast< const ast::StructInstType * >( type ) ) {
	200	if ( hasPolyParams( sue->params, subst ) ) return type;
	201	} else if ( auto sue = dynamic_cast< const ast::UnionInstType * >( type ) ) {
	202	if ( hasPolyParams( sue->params, subst ) ) return type;
	203	}
	204	return nullptr;
	205	}
	206
[33a7b6d]	207	ReferenceToType isDynType( Type type, const TyVarMap &tyVars, const TypeSubstitution *env ) {
[3bb195cb]	208	type = replaceTypeInst( type, env );
	209
	210	if ( TypeInstType typeInst = dynamic_cast< TypeInstType >( type ) ) {
	211	auto var = tyVars.find( typeInst->get_name() );
[2c57025]	212	if ( var != tyVars.end() && var->second.isComplete ) {
[33a7b6d]	213	return typeInst;
[3bb195cb]	214	}
	215	} else if ( StructInstType structType = dynamic_cast< StructInstType >( type ) ) {
[33a7b6d]	216	if ( hasDynParams( structType->get_parameters(), tyVars, env ) ) return structType;
[3bb195cb]	217	} else if ( UnionInstType unionType = dynamic_cast< UnionInstType >( type ) ) {
[33a7b6d]	218	if ( hasDynParams( unionType->get_parameters(), tyVars, env ) ) return unionType;
[3bb195cb]	219	}
	220	return 0;
	221	}
	222
[c8837e5]	223	const ast::BaseInstType * isDynType(
	224	const ast::Type * type, const TypeVarMap & typeVars,
	225	const ast::TypeSubstitution * subst ) {
	226	type = replaceTypeInst( type, subst );
	227
	228	if ( auto inst = dynamic_cast<ast::TypeInstType const *>( type ) ) {
	229	auto var = typeVars.find( inst->name );
	230	if ( var != typeVars.end() && var->second.isComplete ) {
[3606fe4]	231
	232	}
[c8837e5]	233	} else if ( auto inst = dynamic_cast<ast::StructInstType const *>( type ) ) {
	234	if ( hasDynParams( inst->params, typeVars, subst ) ) {
	235	return inst;
	236	}
	237	} else if ( auto inst = dynamic_cast<ast::UnionInstType const *>( type ) ) {
	238	if ( hasDynParams( inst->params, typeVars, subst ) ) {
	239	return inst;
	240	}
[3606fe4]	241	}
[c8837e5]	242	return nullptr;
	243	}
[3606fe4]	244
[3bb195cb]	245	ReferenceToType isDynRet( FunctionType function, const TyVarMap &forallTypes ) {
	246	if ( function->get_returnVals().empty() ) return 0;
[8c49c0e]	247
[3bb195cb]	248	return (ReferenceToType*)isDynType( function->get_returnVals().front()->get_type(), forallTypes );
	249	}
	250
[c8837e5]	251	const ast::BaseInstType *isDynRet(
	252	const ast::FunctionType * type, const TypeVarMap & typeVars ) {
	253	if ( type->returns.empty() ) return nullptr;
	254
	255	return isDynType( type->returns.front(), typeVars );
	256	}
	257
[3bb195cb]	258	ReferenceToType isDynRet( FunctionType function ) {
	259	if ( function->get_returnVals().empty() ) return 0;
	260
[2c57025]	261	TyVarMap forallTypes( TypeDecl::Data{} );
[3bb195cb]	262	makeTyVarMap( function, forallTypes );
	263	return (ReferenceToType*)isDynType( function->get_returnVals().front()->get_type(), forallTypes );
	264	}
	265
	266	bool needsAdapter( FunctionType *adaptee, const TyVarMap &tyVars ) {
	267	// if ( ! adaptee->get_returnVals().empty() && isPolyType( adaptee->get_returnVals().front()->get_type(), tyVars ) ) {
	268	// return true;
	269	// } // if
	270	if ( isDynRet( adaptee, tyVars ) ) return true;
[8c49c0e]	271
[3bb195cb]	272	for ( std::list< DeclarationWithType* >::const_iterator innerArg = adaptee->get_parameters().begin(); innerArg != adaptee->get_parameters().end(); ++innerArg ) {
	273	// if ( isPolyType( (*innerArg)->get_type(), tyVars ) ) {
	274	if ( isDynType( (*innerArg)->get_type(), tyVars ) ) {
	275	return true;
	276	} // if
	277	} // for
	278	return false;
	279	}
	280
[c8837e5]	281	bool needsAdapter(
	282	ast::FunctionType const * adaptee, const TypeVarMap & typeVars ) {
	283	if ( isDynRet( adaptee, typeVars ) ) return true;
	284
	285	for ( auto param : adaptee->params ) {
	286	if ( isDynType( param, typeVars ) ) {
	287	return true;
	288	}
	289	}
	290	return false;
	291	}
	292
[0f889a77]	293	Type isPolyPtr( Type type, const TypeSubstitution *env ) {
[e24955a]	294	type = replaceTypeInst( type, env );
[83de11e]	295
[0f889a77]	296	if ( PointerType ptr = dynamic_cast< PointerType >( type ) ) {
	297	return isPolyType( ptr->get_base(), env );
[e24955a]	298	}
[0f889a77]	299	return 0;
	300	}
[540de412]	301
[ffad73a]	302	Type isPolyPtr( Type type, const TyVarMap &tyVars, const TypeSubstitution *env ) {
[e24955a]	303	type = replaceTypeInst( type, env );
[83de11e]	304
[ffad73a]	305	if ( PointerType ptr = dynamic_cast< PointerType >( type ) ) {
	306	return isPolyType( ptr->get_base(), tyVars, env );
[e24955a]	307	}
[ffad73a]	308	return 0;
[bdf1954]	309	}
	310
[8488c715]	311	Type * hasPolyBase( Type type, int levels, const TypeSubstitution *env ) {
	312	int dummy;
	313	if ( ! levels ) { levels = &dummy; }
	314	*levels = 0;
	315
	316	while ( true ) {
[e24955a]	317	type = replaceTypeInst( type, env );
[83de11e]	318
[8488c715]	319	if ( PointerType ptr = dynamic_cast< PointerType >( type ) ) {
	320	type = ptr->get_base();
	321	++(*levels);
	322	} else break;
[05d47278]	323	}
	324
	325	return isPolyType( type, env );
	326	}
[540de412]	327
[8488c715]	328	Type * hasPolyBase( Type type, const TyVarMap &tyVars, int levels, const TypeSubstitution *env ) {
	329	int dummy;
	330	if ( ! levels ) { levels = &dummy; }
	331	*levels = 0;
	332
	333	while ( true ) {
[e24955a]	334	type = replaceTypeInst( type, env );
[83de11e]	335
[8488c715]	336	if ( PointerType ptr = dynamic_cast< PointerType >( type ) ) {
	337	type = ptr->get_base();
	338	++(*levels);
	339	} else break;
[05d47278]	340	}
	341
	342	return isPolyType( type, tyVars, env );
	343	}
	344
[c8837e5]	345	ast::Type const * hasPolyBase(
	346	ast::Type const * type, const TypeVarMap & typeVars,
	347	int * levels, const ast::TypeSubstitution * subst ) {
	348	int level_count = 0;
	349
	350	while ( true ) {
	351	type = replaceTypeInst( type, subst );
	352
	353	if ( auto ptr = dynamic_cast<ast::PointerType const *>( type ) ) {
	354	type = ptr->base;
	355	++level_count;
	356	} else {
	357	break;
	358	}
	359	}
	360
	361	if ( nullptr != levels ) { *levels = level_count; }
	362	return isPolyType( type, typeVars, subst );
	363	}
	364
[5a3ac84]	365	bool includesPolyType( Type type, const TypeSubstitution env ) {
	366	type = replaceTypeInst( type, env );
	367
	368	if ( dynamic_cast< TypeInstType * >( type ) ) {
	369	return true;
	370	} else if ( PointerType pointerType = dynamic_cast< PointerType >( type ) ) {
	371	if ( includesPolyType( pointerType->get_base(), env ) ) return true;
	372	} else if ( StructInstType structType = dynamic_cast< StructInstType >( type ) ) {
	373	if ( includesPolyParams( structType->get_parameters(), env ) ) return true;
	374	} else if ( UnionInstType unionType = dynamic_cast< UnionInstType >( type ) ) {
	375	if ( includesPolyParams( unionType->get_parameters(), env ) ) return true;
	376	}
	377	return false;
	378	}
	379
	380	bool includesPolyType( Type type, const TyVarMap &tyVars, const TypeSubstitution env ) {
	381	type = replaceTypeInst( type, env );
	382
	383	if ( TypeInstType typeInstType = dynamic_cast< TypeInstType >( type ) ) {
	384	if ( tyVars.find( typeInstType->get_name() ) != tyVars.end() ) {
	385	return true;
	386	}
	387	} else if ( PointerType pointerType = dynamic_cast< PointerType >( type ) ) {
	388	if ( includesPolyType( pointerType->get_base(), tyVars, env ) ) return true;
	389	} else if ( StructInstType structType = dynamic_cast< StructInstType >( type ) ) {
	390	if ( includesPolyParams( structType->get_parameters(), tyVars, env ) ) return true;
	391	} else if ( UnionInstType unionType = dynamic_cast< UnionInstType >( type ) ) {
	392	if ( includesPolyParams( unionType->get_parameters(), tyVars, env ) ) return true;
	393	}
	394	return false;
	395	}
	396
[7754cde]	397	FunctionType * getFunctionType( Type *ty ) {
	398	PointerType *ptrType;
	399	if ( ( ptrType = dynamic_cast< PointerType* >( ty ) ) ) {
	400	return dynamic_cast< FunctionType* >( ptrType->get_base() ); // pointer if FunctionType, NULL otherwise
	401	} else {
	402	return dynamic_cast< FunctionType* >( ty ); // pointer if FunctionType, NULL otherwise
	403	}
	404	}
	405
[d76c588]	406	const ast::FunctionType * getFunctionType( const ast::Type * ty ) {
	407	if ( auto pty = dynamic_cast< const ast::PointerType * >( ty ) ) {
	408	return pty->base.as< ast::FunctionType >();
	409	} else {
	410	return dynamic_cast< const ast::FunctionType * >( ty );
	411	}
	412	}
	413
[8488c715]	414	VariableExpr * getBaseVar( Expression expr, int levels ) {
	415	int dummy;
	416	if ( ! levels ) { levels = &dummy; }
	417	*levels = 0;
	418
	419	while ( true ) {
	420	if ( VariableExpr varExpr = dynamic_cast< VariableExpr >( expr ) ) {
	421	return varExpr;
[d9f1b2d]	422	} else if ( MemberExpr memberExpr = dynamic_cast< MemberExpr >( expr ) ) {
	423	expr = memberExpr->get_aggregate();
[8488c715]	424	} else if ( AddressExpr addressExpr = dynamic_cast< AddressExpr >( expr ) ) {
	425	expr = addressExpr->get_arg();
	426	} else if ( UntypedExpr untypedExpr = dynamic_cast< UntypedExpr >( expr ) ) {
	427	// look for compiler-inserted dereference operator
	428	NameExpr fn = dynamic_cast< NameExpr >( untypedExpr->get_function() );
	429	if ( ! fn \|\| fn->get_name() != std::string("*?") ) return 0;
	430	expr = *untypedExpr->begin_args();
[540de412]	431	} else if ( CommaExpr commaExpr = dynamic_cast< CommaExpr >( expr ) ) {
	432	// copy constructors insert comma exprs, look at second argument which contains the variable
	433	expr = commaExpr->get_arg2();
	434	continue;
[1aa4b71]	435	} else if ( ConditionalExpr * condExpr = dynamic_cast< ConditionalExpr * >( expr ) ) {
	436	int lvl1;
	437	int lvl2;
	438	VariableExpr * var1 = getBaseVar( condExpr->get_arg2(), &lvl1 );
	439	VariableExpr * var2 = getBaseVar( condExpr->get_arg3(), &lvl2 );
	440	if ( lvl1 == lvl2 && var1 && var2 && var1->get_var() == var2->get_var() ) {
	441	*levels = lvl1;
	442	return var1;
	443	}
	444	break;
[8488c715]	445	} else break;
	446
	447	++(*levels);
	448	}
	449
	450	return 0;
[05d47278]	451	}
	452
[5a3ac84]	453	namespace {
	454	/// Checks if is a pointer to D
	455	template<typename D, typename B>
	456	bool is( const B* p ) { return type_index{typeid(D)} == type_index{typeid(*p)}; }
	457
	458	/// Converts to a pointer to D without checking for safety
	459	template<typename D, typename B>
	460	inline D* as( B* p ) { return reinterpret_cast<D*>(p); }
	461
[3606fe4]	462	template<typename D, typename B>
	463	inline D const * as( B const * p ) {
	464	return reinterpret_cast<D const *>( p );
	465	}
	466
[5a3ac84]	467	/// Flattens a declaration list
	468	template<typename Output>
	469	void flattenList( list< DeclarationWithType* > src, Output out ) {
	470	for ( DeclarationWithType* decl : src ) {
	471	ResolvExpr::flatten( decl->get_type(), out );
	472	}
	473	}
	474
	475	/// Flattens a list of types
	476	template<typename Output>
	477	void flattenList( list< Type* > src, Output out ) {
	478	for ( Type* ty : src ) {
	479	ResolvExpr::flatten( ty, out );
	480	}
	481	}
	482
[3606fe4]	483	void flattenList( vector<ast::ptr<ast::Type>> const & src,
	484	vector<ast::ptr<ast::Type>> & out ) {
	485	for ( auto const & type : src ) {
	486	ResolvExpr::flatten( type, out );
	487	}
	488	}
	489
[5a3ac84]	490	/// Checks if two lists of parameters are equal up to polymorphic substitution.
	491	bool paramListsPolyCompatible( const list< Expression* >& aparams, const list< Expression* >& bparams ) {
	492	if ( aparams.size() != bparams.size() ) return false;
	493
	494	for ( list< Expression* >::const_iterator at = aparams.begin(), bt = bparams.begin();
	495	at != aparams.end(); ++at, ++bt ) {
	496	TypeExpr aparam = dynamic_cast< TypeExpr >(*at);
	497	assertf(aparam, "Aggregate parameters should be type expressions");
	498	TypeExpr bparam = dynamic_cast< TypeExpr >(*bt);
	499	assertf(bparam, "Aggregate parameters should be type expressions");
	500
[cccc534]	501	// xxx - might need to let VoidType be a wildcard here too; could have some voids
[5a3ac84]	502	// stuffed in for dtype-statics.
	503	// if ( is<VoidType>( aparam->get_type() ) \|\| is<VoidType>( bparam->get_type() ) ) continue;
	504	if ( ! typesPolyCompatible( aparam->get_type(), bparam->get_type() ) ) return false;
	505	}
[cccc534]	506
[5a3ac84]	507	return true;
	508	}
[3606fe4]	509
	510	bool paramListsPolyCompatible(
	511	std::vector<ast::ptr<ast::Expr>> const & lparams,
	512	std::vector<ast::ptr<ast::Expr>> const & rparams ) {
	513	if ( lparams.size() != rparams.size() ) {
	514	return false;
	515	}
	516
	517	for ( auto lparam = lparams.begin(), rparam = rparams.begin() ;
	518	lparam != lparams.end() ; ++lparam, ++rparam ) {
	519	ast::TypeExpr const * lexpr = lparam->as<ast::TypeExpr>();
	520	assertf( lexpr, "Aggregate parameters should be type expressions" );
	521	ast::TypeExpr const * rexpr = rparam->as<ast::TypeExpr>();
	522	assertf( rexpr, "Aggregate parameters should be type expressions" );
	523
	524	// xxx - might need to let VoidType be a wildcard here too; could have some voids
	525	// stuffed in for dtype-statics.
	526	// if ( is<VoidType>( lexpr->type() ) \|\| is<VoidType>( bparam->get_type() ) ) continue;
	527	if ( !typesPolyCompatible( lexpr->type, rexpr->type ) ) {
	528	return false;
	529	}
	530	}
	531
	532	return true;
	533	}
[5a3ac84]	534	}
	535
	536	bool typesPolyCompatible( Type a, Type b ) {
	537	type_index aid{ typeid(*a) };
	538	// polymorphic types always match
	539	if ( aid == type_index{typeid(TypeInstType)} ) return true;
[cccc534]	540
[5a3ac84]	541	type_index bid{ typeid(*b) };
	542	// polymorphic types always match
	543	if ( bid == type_index{typeid(TypeInstType)} ) return true;
[cccc534]	544
[5a3ac84]	545	// can't match otherwise if different types
	546	if ( aid != bid ) return false;
	547
	548	// recurse through type structure (conditions borrowed from Unify.cc)
	549	if ( aid == type_index{typeid(BasicType)} ) {
	550	return as<BasicType>(a)->get_kind() == as<BasicType>(b)->get_kind();
	551	} else if ( aid == type_index{typeid(PointerType)} ) {
	552	PointerType ap = as<PointerType>(a), bp = as<PointerType>(b);
	553
	554	// void pointers should match any other pointer type
	555	return is<VoidType>( ap->get_base() ) \|\| is<VoidType>( bp->get_base() )
	556	\|\| typesPolyCompatible( ap->get_base(), bp->get_base() );
[682dcae]	557	} else if ( aid == type_index{typeid(ReferenceType)} ) {
	558	ReferenceType ap = as<ReferenceType>(a), bp = as<ReferenceType>(b);
	559	return is<VoidType>( ap->get_base() ) \|\| is<VoidType>( bp->get_base() )
	560	\|\| typesPolyCompatible( ap->get_base(), bp->get_base() );
[5a3ac84]	561	} else if ( aid == type_index{typeid(ArrayType)} ) {
	562	ArrayType aa = as<ArrayType>(a), ba = as<ArrayType>(b);
	563
	564	if ( aa->get_isVarLen() ) {
	565	if ( ! ba->get_isVarLen() ) return false;
	566	} else {
	567	if ( ba->get_isVarLen() ) return false;
	568
	569	ConstantExpr ad = dynamic_cast<ConstantExpr>( aa->get_dimension() );
	570	ConstantExpr bd = dynamic_cast<ConstantExpr>( ba->get_dimension() );
[cccc534]	571	if ( ad && bd
[5a3ac84]	572	&& ad->get_constant()->get_value() != bd->get_constant()->get_value() )
	573	return false;
	574	}
	575
	576	return typesPolyCompatible( aa->get_base(), ba->get_base() );
	577	} else if ( aid == type_index{typeid(FunctionType)} ) {
	578	FunctionType af = as<FunctionType>(a), bf = as<FunctionType>(b);
	579
	580	vector<Type*> aparams, bparams;
	581	flattenList( af->get_parameters(), back_inserter( aparams ) );
	582	flattenList( bf->get_parameters(), back_inserter( bparams ) );
	583	if ( aparams.size() != bparams.size() ) return false;
	584
	585	vector<Type*> areturns, breturns;
	586	flattenList( af->get_returnVals(), back_inserter( areturns ) );
	587	flattenList( bf->get_returnVals(), back_inserter( breturns ) );
	588	if ( areturns.size() != breturns.size() ) return false;
	589
	590	for ( unsigned i = 0; i < aparams.size(); ++i ) {
	591	if ( ! typesPolyCompatible( aparams[i], bparams[i] ) ) return false;
	592	}
	593	for ( unsigned i = 0; i < areturns.size(); ++i ) {
	594	if ( ! typesPolyCompatible( areturns[i], breturns[i] ) ) return false;
	595	}
	596	return true;
	597	} else if ( aid == type_index{typeid(StructInstType)} ) {
	598	StructInstType aa = as<StructInstType>(a), ba = as<StructInstType>(b);
	599
	600	if ( aa->get_name() != ba->get_name() ) return false;
	601	return paramListsPolyCompatible( aa->get_parameters(), ba->get_parameters() );
	602	} else if ( aid == type_index{typeid(UnionInstType)} ) {
	603	UnionInstType aa = as<UnionInstType>(a), ba = as<UnionInstType>(b);
	604
	605	if ( aa->get_name() != ba->get_name() ) return false;
	606	return paramListsPolyCompatible( aa->get_parameters(), ba->get_parameters() );
	607	} else if ( aid == type_index{typeid(EnumInstType)} ) {
	608	return as<EnumInstType>(a)->get_name() == as<EnumInstType>(b)->get_name();
	609	} else if ( aid == type_index{typeid(TraitInstType)} ) {
	610	return as<TraitInstType>(a)->get_name() == as<TraitInstType>(b)->get_name();
	611	} else if ( aid == type_index{typeid(TupleType)} ) {
	612	TupleType at = as<TupleType>(a), bt = as<TupleType>(b);
	613
	614	vector<Type*> atypes, btypes;
	615	flattenList( at->get_types(), back_inserter( atypes ) );
	616	flattenList( bt->get_types(), back_inserter( btypes ) );
	617	if ( atypes.size() != btypes.size() ) return false;
	618
	619	for ( unsigned i = 0; i < atypes.size(); ++i ) {
	620	if ( ! typesPolyCompatible( atypes[i], btypes[i] ) ) return false;
	621	}
	622	return true;
	623	} else return true; // VoidType, VarArgsType, ZeroType & OneType just need the same type
	624	}
	625
[3606fe4]	626	bool typesPolyCompatible( ast::Type const * lhs, ast::Type const * rhs ) {
	627	type_index const lid = typeid(*lhs);
	628
	629	// Polymorphic types always match:
	630	if ( type_index(typeid(ast::TypeInstType)) == lid ) return true;
	631
	632	type_index const rid = typeid(*rhs);
	633	if ( type_index(typeid(ast::TypeInstType)) == rid ) return true;
	634
	635	// All other types only match if they are the same type:
	636	if ( lid != rid ) return false;
	637
	638	// So remaining types can be examined case by case.
	639	// Recurse through type structure (conditions borrowed from Unify.cc).
	640
	641	if ( type_index(typeid(ast::BasicType)) == lid ) {
	642	return as<ast::BasicType>(lhs)->kind == as<ast::BasicType>(rhs)->kind;
	643	} else if ( type_index(typeid(ast::PointerType)) == lid ) {
	644	ast::PointerType const * l = as<ast::PointerType>(lhs);
	645	ast::PointerType const * r = as<ast::PointerType>(rhs);
	646
	647	// void pointers should match any other pointer type.
	648	return is<ast::VoidType>( l->base.get() )
	649	\|\| is<ast::VoidType>( r->base.get() )
	650	\|\| typesPolyCompatible( l->base.get(), r->base.get() );
	651	} else if ( type_index(typeid(ast::ReferenceType)) == lid ) {
	652	ast::ReferenceType const * l = as<ast::ReferenceType>(lhs);
	653	ast::ReferenceType const * r = as<ast::ReferenceType>(rhs);
	654
	655	// void references should match any other reference type.
	656	return is<ast::VoidType>( l->base.get() )
	657	\|\| is<ast::VoidType>( r->base.get() )
	658	\|\| typesPolyCompatible( l->base.get(), r->base.get() );
	659	} else if ( type_index(typeid(ast::ArrayType)) == lid ) {
	660	ast::ArrayType const * l = as<ast::ArrayType>(lhs);
	661	ast::ArrayType const * r = as<ast::ArrayType>(rhs);
	662
	663	if ( l->isVarLen ) {
	664	if ( !r->isVarLen ) return false;
	665	} else {
	666	if ( r->isVarLen ) return false;
	667
	668	auto lc = l->dimension.as<ast::ConstantExpr>();
	669	auto rc = r->dimension.as<ast::ConstantExpr>();
	670	if ( lc && rc && lc->intValue() != rc->intValue() ) {
	671	return false;
	672	}
	673	}
	674
	675	return typesPolyCompatible( l->base.get(), r->base.get() );
	676	} else if ( type_index(typeid(ast::FunctionType)) == lid ) {
	677	ast::FunctionType const * l = as<ast::FunctionType>(lhs);
	678	ast::FunctionType const * r = as<ast::FunctionType>(rhs);
	679
	680	std::vector<ast::ptr<ast::Type>> lparams, rparams;
	681	flattenList( l->params, lparams );
	682	flattenList( r->params, rparams );
	683	if ( lparams.size() != rparams.size() ) return false;
	684	for ( unsigned i = 0; i < lparams.size(); ++i ) {
	685	if ( !typesPolyCompatible( lparams[i], rparams[i] ) ) return false;
	686	}
	687
	688	std::vector<ast::ptr<ast::Type>> lrets, rrets;
	689	flattenList( l->returns, lrets );
	690	flattenList( r->returns, rrets );
	691	if ( lrets.size() != rrets.size() ) return false;
	692	for ( unsigned i = 0; i < lrets.size(); ++i ) {
	693	if ( !typesPolyCompatible( lrets[i], rrets[i] ) ) return false;
	694	}
	695	return true;
	696	} else if ( type_index(typeid(ast::StructInstType)) == lid ) {
	697	ast::StructInstType const * l = as<ast::StructInstType>(lhs);
	698	ast::StructInstType const * r = as<ast::StructInstType>(rhs);
	699
	700	if ( l->name != r->name ) return false;
	701	return paramListsPolyCompatible( l->params, r->params );
	702	} else if ( type_index(typeid(ast::UnionInstType)) == lid ) {
	703	ast::UnionInstType const * l = as<ast::UnionInstType>(lhs);
	704	ast::UnionInstType const * r = as<ast::UnionInstType>(rhs);
	705
	706	if ( l->name != r->name ) return false;
	707	return paramListsPolyCompatible( l->params, r->params );
	708	} else if ( type_index(typeid(ast::EnumInstType)) == lid ) {
	709	ast::EnumInstType const * l = as<ast::EnumInstType>(lhs);
	710	ast::EnumInstType const * r = as<ast::EnumInstType>(rhs);
	711
	712	return l->name == r->name;
	713	} else if ( type_index(typeid(ast::TraitInstType)) == lid ) {
	714	ast::TraitInstType const * l = as<ast::TraitInstType>(lhs);
	715	ast::TraitInstType const * r = as<ast::TraitInstType>(rhs);
	716
	717	return l->name == r->name;
	718	} else if ( type_index(typeid(ast::TupleType)) == lid ) {
	719	ast::TupleType const * l = as<ast::TupleType>(lhs);
	720	ast::TupleType const * r = as<ast::TupleType>(rhs);
	721
	722	std::vector<ast::ptr<ast::Type>> ltypes, rtypes;
	723	flattenList( l->types, ( ltypes ) );
	724	flattenList( r->types, ( rtypes ) );
	725	if ( ltypes.size() != rtypes.size() ) return false;
	726
	727	for ( unsigned i = 0 ; i < ltypes.size() ; ++i ) {
	728	if ( !typesPolyCompatible( ltypes[i], rtypes[i] ) ) return false;
	729	}
	730	return true;
	731	// The remaining types (VoidType, VarArgsType, ZeroType & OneType)
	732	// have no variation so will always be equal.
	733	} else {
	734	return true;
	735	}
	736	}
	737
[02fdb8e]	738	bool needsBoxing( Type * param, Type * arg, const TyVarMap &exprTyVars, const TypeSubstitution * env ) {
[ae1b9ea]	739	// is parameter is not polymorphic, don't need to box
	740	if ( ! isPolyType( param, exprTyVars ) ) return false;
	741	Type * newType = arg->clone();
	742	if ( env ) env->apply( newType );
	743	std::unique_ptr<Type> manager( newType );
	744	// if the argument's type is polymorphic, we don't need to box again!
	745	return ! isPolyType( newType );
	746	}
	747
[c8837e5]	748	bool needsBoxing( const ast::Type * param, const ast::Type * arg,
	749	const TypeVarMap & typeVars, const ast::TypeSubstitution * subst ) {
	750	// Don't need to box if the parameter is not polymorphic.
	751	if ( !isPolyType( param, typeVars ) ) return false;
	752
	753	ast::ptr<ast::Type> newType = arg;
	754	if ( subst ) {
	755	int count = subst->apply( newType );
	756	(void)count;
[490fb92e]	757	}
[c8837e5]	758	// Only need to box if the argument is not also polymorphic.
	759	return !isPolyType( newType );
	760	}
[490fb92e]	761
[02fdb8e]	762	bool needsBoxing( Type * param, Type * arg, ApplicationExpr * appExpr, const TypeSubstitution * env ) {
[ae1b9ea]	763	FunctionType * function = getFunctionType( appExpr->function->result );
	764	assertf( function, "ApplicationExpr has non-function type: %s", toString( appExpr->function->result ).c_str() );
	765	TyVarMap exprTyVars( TypeDecl::Data{} );
	766	makeTyVarMap( function, exprTyVars );
	767	return needsBoxing( param, arg, exprTyVars, env );
	768	}
	769
[c8837e5]	770	bool needsBoxing(
	771	const ast::Type * param, const ast::Type * arg,
	772	const ast::ApplicationExpr * expr,
	773	const ast::TypeSubstitution * subst ) {
	774	const ast::FunctionType * function = getFunctionType( expr->func->result );
	775	assertf( function, "ApplicationExpr has non-function type: %s", toString( expr->func->result ).c_str() );
	776	TypeVarMap exprTyVars = { ast::TypeDecl::Data() };
	777	makeTypeVarMap( function, exprTyVars );
	778	return needsBoxing( param, arg, exprTyVars, subst );
	779	}
[490fb92e]	780
[2c57025]	781	void addToTyVarMap( TypeDecl * tyVar, TyVarMap &tyVarMap ) {
[7ba1324]	782	tyVarMap.insert( tyVar->name, TypeDecl::Data{ tyVar } );
[2c57025]	783	}
	784
[c8837e5]	785	void addToTypeVarMap( const ast::TypeInstType * type, TypeVarMap & typeVars ) {
	786	typeVars.insert( type->typeString(), ast::TypeDecl::Data( type->base ) );
	787	}
[490fb92e]	788
[aadc9a4]	789	void makeTyVarMap( Type *type, TyVarMap &tyVarMap ) {
[8c49c0e]	790	for ( Type::ForallList::const_iterator tyVar = type->get_forall().begin(); tyVar != type->get_forall().end(); ++tyVar ) {
[aadc9a4]	791	assert( *tyVar );
[2c57025]	792	addToTyVarMap( *tyVar, tyVarMap );
[aadc9a4]	793	}
	794	if ( PointerType pointer = dynamic_cast< PointerType >( type ) ) {
	795	makeTyVarMap( pointer->get_base(), tyVarMap );
	796	}
	797	}
[540de412]	798
[c8837e5]	799	void makeTypeVarMap( const ast::Type * type, TypeVarMap & typeVars ) {
	800	if ( auto func = dynamic_cast<ast::FunctionType const *>( type ) ) {
	801	for ( auto & typeVar : func->forall ) {
	802	assert( typeVar );
	803	addToTypeVarMap( typeVar, typeVars );
[490fb92e]	804	}
	805	}
[c8837e5]	806	if ( auto pointer = dynamic_cast<ast::PointerType const *>( type ) ) {
	807	makeTypeVarMap( pointer->base, typeVars );
	808	}
	809	}
[490fb92e]	810
[01aeade]	811	void printTyVarMap( std::ostream &os, const TyVarMap &tyVarMap ) {
	812	for ( TyVarMap::const_iterator i = tyVarMap.begin(); i != tyVarMap.end(); ++i ) {
	813	os << i->first << " (" << i->second << ") ";
	814	} // for
	815	os << std::endl;
	816	}
[ffad73a]	817
[c8837e5]	818	void printTypeVarMap( std::ostream &os, const TypeVarMap & typeVars ) {
	819	for ( auto const & pair : typeVars ) {
	820	os << pair.first << " (" << pair.second << ") ";
	821	} // for
	822	os << std::endl;
	823	}
	824
[51b73452]	825	} // namespace GenPoly
[01aeade]	826
[51587aa]	827	// Local Variables: //
	828	// tab-width: 4 //
	829	// mode: c++ //
	830	// compile-command: "make install" //
	831	// End: //

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

Download in other formats: