Context Navigation

source: src/GenPoly/GenPoly.cc @ d61d034

ADTast-experimental

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

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

Download in other formats: