Context Navigation

source: src/GenPoly/GenPoly.cc @ 5d8dae7

ADTast-experimental

Last change on this file since 5d8dae7 was 3606fe4, checked in by Andrew Beach <ajbeach@…>, 2 years ago
Translated Instantiate Generic to the new AST. This includes various utilities and some assorted clean-up.
Property mode set to `100644`
File size: 30.2 KB

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

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

Download in other formats: