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 -- General GenPoly utilities.
|
---|
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/Expr.hpp"
|
---|
27 | #include "AST/Type.hpp"
|
---|
28 | #include "AST/TypeSubstitution.hpp"
|
---|
29 | #include "GenPoly/ErasableScopedMap.h" // for ErasableScopedMap<>::const_it...
|
---|
30 | #include "ResolvExpr/typeops.h" // for flatten
|
---|
31 |
|
---|
32 | using namespace std;
|
---|
33 |
|
---|
34 | namespace GenPoly {
|
---|
35 |
|
---|
36 | namespace {
|
---|
37 | /// Checks a parameter list for polymorphic parameters; will substitute according to env if present.
|
---|
38 | bool hasPolyParams( const std::vector<ast::ptr<ast::Expr>> & params, const ast::TypeSubstitution * env ) {
|
---|
39 | for ( auto & param : params ) {
|
---|
40 | auto paramType = param.as<ast::TypeExpr>();
|
---|
41 | assertf( paramType, "Aggregate parameters should be type expressions" );
|
---|
42 | if ( isPolyType( paramType->type, env ) ) return true;
|
---|
43 | }
|
---|
44 | return false;
|
---|
45 | }
|
---|
46 |
|
---|
47 | /// Checks a parameter list for polymorphic parameters from typeVars; will substitute according to env if present.
|
---|
48 | bool hasPolyParams( const std::vector<ast::ptr<ast::Expr>> & params, const TypeVarMap & typeVars, const ast::TypeSubstitution * env ) {
|
---|
49 | for ( auto & param : params ) {
|
---|
50 | auto paramType = param.as<ast::TypeExpr>();
|
---|
51 | assertf( paramType, "Aggregate parameters should be type expressions" );
|
---|
52 | if ( isPolyType( paramType->type, typeVars, env ) ) return true;
|
---|
53 | }
|
---|
54 | return false;
|
---|
55 | }
|
---|
56 |
|
---|
57 | /// Checks a parameter list for dynamic-layout parameters from tyVars; will substitute according to env if present.
|
---|
58 | bool hasDynParams(
|
---|
59 | const std::vector<ast::ptr<ast::Expr>> & params,
|
---|
60 | const TypeVarMap & typeVars,
|
---|
61 | const ast::TypeSubstitution * subst ) {
|
---|
62 | for ( ast::ptr<ast::Expr> const & paramExpr : params ) {
|
---|
63 | auto param = paramExpr.as<ast::TypeExpr>();
|
---|
64 | assertf( param, "Aggregate parameters should be type expressions." );
|
---|
65 | if ( isDynType( param->type.get(), typeVars, subst ) ) {
|
---|
66 | return true;
|
---|
67 | }
|
---|
68 | }
|
---|
69 | return false;
|
---|
70 | }
|
---|
71 | } // namespace
|
---|
72 |
|
---|
73 | const ast::Type * replaceTypeInst( const ast::Type * type, const ast::TypeSubstitution * env ) {
|
---|
74 | if ( !env ) return type;
|
---|
75 | if ( auto typeInst = dynamic_cast<const ast::TypeInstType*>( type ) ) {
|
---|
76 | if ( auto newType = env->lookup( typeInst ) ) return newType;
|
---|
77 | }
|
---|
78 | return type;
|
---|
79 | }
|
---|
80 |
|
---|
81 | const ast::Type * isPolyType( const ast::Type * type, const ast::TypeSubstitution * subst ) {
|
---|
82 | type = replaceTypeInst( type, subst );
|
---|
83 |
|
---|
84 | if ( dynamic_cast< const ast::TypeInstType * >( type ) ) {
|
---|
85 | // This case is where the two variants of isPolyType differ.
|
---|
86 | return type;
|
---|
87 | } else if ( auto arrayType = dynamic_cast< const ast::ArrayType * >( type ) ) {
|
---|
88 | return isPolyType( arrayType->base, subst );
|
---|
89 | } else if ( auto structType = dynamic_cast< const ast::StructInstType* >( type ) ) {
|
---|
90 | if ( hasPolyParams( structType->params, subst ) ) return type;
|
---|
91 | } else if ( auto unionType = dynamic_cast< const ast::UnionInstType* >( type ) ) {
|
---|
92 | if ( hasPolyParams( unionType->params, subst ) ) return type;
|
---|
93 | }
|
---|
94 | return nullptr;
|
---|
95 | }
|
---|
96 |
|
---|
97 | const ast::Type * isPolyType( const ast::Type * type,
|
---|
98 | const TypeVarMap & typeVars, const ast::TypeSubstitution * subst ) {
|
---|
99 | type = replaceTypeInst( type, subst );
|
---|
100 |
|
---|
101 | if ( auto inst = dynamic_cast< const ast::TypeInstType * >( type ) ) {
|
---|
102 | if ( typeVars.contains( *inst ) ) return type;
|
---|
103 | } else if ( auto array = dynamic_cast< const ast::ArrayType * >( type ) ) {
|
---|
104 | return isPolyType( array->base, typeVars, subst );
|
---|
105 | } else if ( auto sue = dynamic_cast< const ast::StructInstType * >( type ) ) {
|
---|
106 | if ( hasPolyParams( sue->params, typeVars, subst ) ) return type;
|
---|
107 | } else if ( auto sue = dynamic_cast< const ast::UnionInstType * >( type ) ) {
|
---|
108 | if ( hasPolyParams( sue->params, typeVars, subst ) ) return type;
|
---|
109 | }
|
---|
110 | return nullptr;
|
---|
111 | }
|
---|
112 |
|
---|
113 | const ast::BaseInstType * isDynType(
|
---|
114 | const ast::Type * type, const TypeVarMap & typeVars,
|
---|
115 | const ast::TypeSubstitution * subst ) {
|
---|
116 | type = replaceTypeInst( type, subst );
|
---|
117 |
|
---|
118 | if ( auto inst = dynamic_cast<ast::TypeInstType const *>( type ) ) {
|
---|
119 | auto var = typeVars.find( *inst );
|
---|
120 | if ( var != typeVars.end() && var->second.isComplete ) {
|
---|
121 | return inst;
|
---|
122 | }
|
---|
123 | } else if ( auto inst = dynamic_cast<ast::StructInstType const *>( type ) ) {
|
---|
124 | if ( hasDynParams( inst->params, typeVars, subst ) ) return inst;
|
---|
125 | } else if ( auto inst = dynamic_cast<ast::UnionInstType const *>( type ) ) {
|
---|
126 | if ( hasDynParams( inst->params, typeVars, subst ) ) return inst;
|
---|
127 | }
|
---|
128 | return nullptr;
|
---|
129 | }
|
---|
130 |
|
---|
131 | const ast::BaseInstType *isDynRet(
|
---|
132 | const ast::FunctionType * type, const TypeVarMap & typeVars ) {
|
---|
133 | if ( type->returns.empty() ) return nullptr;
|
---|
134 |
|
---|
135 | return isDynType( type->returns.front(), typeVars );
|
---|
136 | }
|
---|
137 |
|
---|
138 | const ast::BaseInstType *isDynRet( const ast::FunctionType * func ) {
|
---|
139 | if ( func->returns.empty() ) return nullptr;
|
---|
140 |
|
---|
141 | TypeVarMap forallTypes;
|
---|
142 | makeTypeVarMap( func, forallTypes );
|
---|
143 | return isDynType( func->returns.front(), forallTypes );
|
---|
144 | }
|
---|
145 |
|
---|
146 | bool needsAdapter(
|
---|
147 | ast::FunctionType const * adaptee, const TypeVarMap & typeVars ) {
|
---|
148 | if ( isDynRet( adaptee, typeVars ) ) return true;
|
---|
149 |
|
---|
150 | for ( auto param : adaptee->params ) {
|
---|
151 | if ( isDynType( param, typeVars ) ) {
|
---|
152 | return true;
|
---|
153 | }
|
---|
154 | }
|
---|
155 | return false;
|
---|
156 | }
|
---|
157 |
|
---|
158 | const ast::Type * isPolyPtr(
|
---|
159 | const ast::Type * type, const TypeVarMap & typeVars,
|
---|
160 | const ast::TypeSubstitution * typeSubs ) {
|
---|
161 | type = replaceTypeInst( type, typeSubs );
|
---|
162 |
|
---|
163 | if ( auto * ptr = dynamic_cast<ast::PointerType const *>( type ) ) {
|
---|
164 | return isPolyType( ptr->base, typeVars, typeSubs );
|
---|
165 | }
|
---|
166 | return nullptr;
|
---|
167 | }
|
---|
168 |
|
---|
169 | ast::Type const * hasPolyBase(
|
---|
170 | ast::Type const * type, const TypeVarMap & typeVars,
|
---|
171 | int * levels, const ast::TypeSubstitution * subst ) {
|
---|
172 | int level_count = 0;
|
---|
173 |
|
---|
174 | while ( true ) {
|
---|
175 | type = replaceTypeInst( type, subst );
|
---|
176 |
|
---|
177 | if ( auto ptr = dynamic_cast<ast::PointerType const *>( type ) ) {
|
---|
178 | type = ptr->base;
|
---|
179 | ++level_count;
|
---|
180 | } else {
|
---|
181 | break;
|
---|
182 | }
|
---|
183 | }
|
---|
184 |
|
---|
185 | if ( nullptr != levels ) { *levels = level_count; }
|
---|
186 | return isPolyType( type, typeVars, subst );
|
---|
187 | }
|
---|
188 |
|
---|
189 | const ast::FunctionType * getFunctionType( const ast::Type * ty ) {
|
---|
190 | if ( auto pty = dynamic_cast< const ast::PointerType * >( ty ) ) {
|
---|
191 | return pty->base.as< ast::FunctionType >();
|
---|
192 | } else {
|
---|
193 | return dynamic_cast< const ast::FunctionType * >( ty );
|
---|
194 | }
|
---|
195 | }
|
---|
196 |
|
---|
197 | namespace {
|
---|
198 | /// Checks if is a pointer to D
|
---|
199 | template<typename D, typename B>
|
---|
200 | bool is( const B* p ) { return type_index{typeid(D)} == type_index{typeid(*p)}; }
|
---|
201 |
|
---|
202 | /// Converts to a pointer to D without checking for safety
|
---|
203 | template<typename D, typename B>
|
---|
204 | inline D* as( B* p ) { return reinterpret_cast<D*>(p); }
|
---|
205 |
|
---|
206 | template<typename D, typename B>
|
---|
207 | inline D const * as( B const * p ) {
|
---|
208 | return reinterpret_cast<D const *>( p );
|
---|
209 | }
|
---|
210 |
|
---|
211 | /// Flattens a list of types.
|
---|
212 | void flattenList( vector<ast::ptr<ast::Type>> const & src,
|
---|
213 | vector<ast::ptr<ast::Type>> & out ) {
|
---|
214 | for ( auto const & type : src ) {
|
---|
215 | ResolvExpr::flatten( type, out );
|
---|
216 | }
|
---|
217 | }
|
---|
218 |
|
---|
219 | bool paramListsPolyCompatible(
|
---|
220 | std::vector<ast::ptr<ast::Expr>> const & lparams,
|
---|
221 | std::vector<ast::ptr<ast::Expr>> const & rparams ) {
|
---|
222 | if ( lparams.size() != rparams.size() ) {
|
---|
223 | return false;
|
---|
224 | }
|
---|
225 |
|
---|
226 | for ( auto lparam = lparams.begin(), rparam = rparams.begin() ;
|
---|
227 | lparam != lparams.end() ; ++lparam, ++rparam ) {
|
---|
228 | ast::TypeExpr const * lexpr = lparam->as<ast::TypeExpr>();
|
---|
229 | assertf( lexpr, "Aggregate parameters should be type expressions" );
|
---|
230 | ast::TypeExpr const * rexpr = rparam->as<ast::TypeExpr>();
|
---|
231 | assertf( rexpr, "Aggregate parameters should be type expressions" );
|
---|
232 |
|
---|
233 | // xxx - might need to let VoidType be a wildcard here too; could have some voids
|
---|
234 | // stuffed in for dtype-statics.
|
---|
235 | // if ( is<VoidType>( lexpr->type() ) || is<VoidType>( bparam->get_type() ) ) continue;
|
---|
236 | if ( !typesPolyCompatible( lexpr->type, rexpr->type ) ) {
|
---|
237 | return false;
|
---|
238 | }
|
---|
239 | }
|
---|
240 |
|
---|
241 | return true;
|
---|
242 | }
|
---|
243 | } // namespace
|
---|
244 |
|
---|
245 | bool typesPolyCompatible( ast::Type const * lhs, ast::Type const * rhs ) {
|
---|
246 | type_index const lid = typeid(*lhs);
|
---|
247 |
|
---|
248 | // Polymorphic types always match:
|
---|
249 | if ( type_index(typeid(ast::TypeInstType)) == lid ) return true;
|
---|
250 |
|
---|
251 | type_index const rid = typeid(*rhs);
|
---|
252 | if ( type_index(typeid(ast::TypeInstType)) == rid ) return true;
|
---|
253 |
|
---|
254 | // All other types only match if they are the same type:
|
---|
255 | if ( lid != rid ) return false;
|
---|
256 |
|
---|
257 | // So remaining types can be examined case by case.
|
---|
258 | // Recurse through type structure (conditions borrowed from Unify.cc).
|
---|
259 |
|
---|
260 | if ( type_index(typeid(ast::BasicType)) == lid ) {
|
---|
261 | return as<ast::BasicType>(lhs)->kind == as<ast::BasicType>(rhs)->kind;
|
---|
262 | } else if ( type_index(typeid(ast::PointerType)) == lid ) {
|
---|
263 | ast::PointerType const * l = as<ast::PointerType>(lhs);
|
---|
264 | ast::PointerType const * r = as<ast::PointerType>(rhs);
|
---|
265 |
|
---|
266 | // void pointers should match any other pointer type.
|
---|
267 | return is<ast::VoidType>( l->base.get() )
|
---|
268 | || is<ast::VoidType>( r->base.get() )
|
---|
269 | || typesPolyCompatible( l->base.get(), r->base.get() );
|
---|
270 | } else if ( type_index(typeid(ast::ReferenceType)) == lid ) {
|
---|
271 | ast::ReferenceType const * l = as<ast::ReferenceType>(lhs);
|
---|
272 | ast::ReferenceType const * r = as<ast::ReferenceType>(rhs);
|
---|
273 |
|
---|
274 | // void references should match any other reference type.
|
---|
275 | return is<ast::VoidType>( l->base.get() )
|
---|
276 | || is<ast::VoidType>( r->base.get() )
|
---|
277 | || typesPolyCompatible( l->base.get(), r->base.get() );
|
---|
278 | } else if ( type_index(typeid(ast::ArrayType)) == lid ) {
|
---|
279 | ast::ArrayType const * l = as<ast::ArrayType>(lhs);
|
---|
280 | ast::ArrayType const * r = as<ast::ArrayType>(rhs);
|
---|
281 |
|
---|
282 | if ( l->isVarLen ) {
|
---|
283 | if ( !r->isVarLen ) return false;
|
---|
284 | } else {
|
---|
285 | if ( r->isVarLen ) return false;
|
---|
286 |
|
---|
287 | auto lc = l->dimension.as<ast::ConstantExpr>();
|
---|
288 | auto rc = r->dimension.as<ast::ConstantExpr>();
|
---|
289 | if ( lc && rc && lc->intValue() != rc->intValue() ) {
|
---|
290 | return false;
|
---|
291 | }
|
---|
292 | }
|
---|
293 |
|
---|
294 | return typesPolyCompatible( l->base.get(), r->base.get() );
|
---|
295 | } else if ( type_index(typeid(ast::FunctionType)) == lid ) {
|
---|
296 | ast::FunctionType const * l = as<ast::FunctionType>(lhs);
|
---|
297 | ast::FunctionType const * r = as<ast::FunctionType>(rhs);
|
---|
298 |
|
---|
299 | std::vector<ast::ptr<ast::Type>> lparams, rparams;
|
---|
300 | flattenList( l->params, lparams );
|
---|
301 | flattenList( r->params, rparams );
|
---|
302 | if ( lparams.size() != rparams.size() ) return false;
|
---|
303 | for ( unsigned i = 0; i < lparams.size(); ++i ) {
|
---|
304 | if ( !typesPolyCompatible( lparams[i], rparams[i] ) ) return false;
|
---|
305 | }
|
---|
306 |
|
---|
307 | std::vector<ast::ptr<ast::Type>> lrets, rrets;
|
---|
308 | flattenList( l->returns, lrets );
|
---|
309 | flattenList( r->returns, rrets );
|
---|
310 | if ( lrets.size() != rrets.size() ) return false;
|
---|
311 | for ( unsigned i = 0; i < lrets.size(); ++i ) {
|
---|
312 | if ( !typesPolyCompatible( lrets[i], rrets[i] ) ) return false;
|
---|
313 | }
|
---|
314 | return true;
|
---|
315 | } else if ( type_index(typeid(ast::StructInstType)) == lid ) {
|
---|
316 | ast::StructInstType const * l = as<ast::StructInstType>(lhs);
|
---|
317 | ast::StructInstType const * r = as<ast::StructInstType>(rhs);
|
---|
318 |
|
---|
319 | if ( l->name != r->name ) return false;
|
---|
320 | return paramListsPolyCompatible( l->params, r->params );
|
---|
321 | } else if ( type_index(typeid(ast::UnionInstType)) == lid ) {
|
---|
322 | ast::UnionInstType const * l = as<ast::UnionInstType>(lhs);
|
---|
323 | ast::UnionInstType const * r = as<ast::UnionInstType>(rhs);
|
---|
324 |
|
---|
325 | if ( l->name != r->name ) return false;
|
---|
326 | return paramListsPolyCompatible( l->params, r->params );
|
---|
327 | } else if ( type_index(typeid(ast::EnumInstType)) == lid ) {
|
---|
328 | ast::EnumInstType const * l = as<ast::EnumInstType>(lhs);
|
---|
329 | ast::EnumInstType const * r = as<ast::EnumInstType>(rhs);
|
---|
330 |
|
---|
331 | return l->name == r->name;
|
---|
332 | } else if ( type_index(typeid(ast::TraitInstType)) == lid ) {
|
---|
333 | ast::TraitInstType const * l = as<ast::TraitInstType>(lhs);
|
---|
334 | ast::TraitInstType const * r = as<ast::TraitInstType>(rhs);
|
---|
335 |
|
---|
336 | return l->name == r->name;
|
---|
337 | } else if ( type_index(typeid(ast::TupleType)) == lid ) {
|
---|
338 | ast::TupleType const * l = as<ast::TupleType>(lhs);
|
---|
339 | ast::TupleType const * r = as<ast::TupleType>(rhs);
|
---|
340 |
|
---|
341 | std::vector<ast::ptr<ast::Type>> ltypes, rtypes;
|
---|
342 | flattenList( l->types, ( ltypes ) );
|
---|
343 | flattenList( r->types, ( rtypes ) );
|
---|
344 | if ( ltypes.size() != rtypes.size() ) return false;
|
---|
345 |
|
---|
346 | for ( unsigned i = 0 ; i < ltypes.size() ; ++i ) {
|
---|
347 | if ( !typesPolyCompatible( ltypes[i], rtypes[i] ) ) return false;
|
---|
348 | }
|
---|
349 | return true;
|
---|
350 | // The remaining types (VoidType, VarArgsType, ZeroType & OneType)
|
---|
351 | // have no variation so will always be equal.
|
---|
352 | } else {
|
---|
353 | return true;
|
---|
354 | }
|
---|
355 | }
|
---|
356 |
|
---|
357 | bool needsBoxing( const ast::Type * param, const ast::Type * arg,
|
---|
358 | const TypeVarMap & typeVars, const ast::TypeSubstitution * subst ) {
|
---|
359 | // Don't need to box if the parameter is not polymorphic.
|
---|
360 | if ( !isPolyType( param, typeVars ) ) return false;
|
---|
361 |
|
---|
362 | ast::ptr<ast::Type> newType = arg;
|
---|
363 | if ( subst ) {
|
---|
364 | int count = subst->apply( newType );
|
---|
365 | (void)count;
|
---|
366 | }
|
---|
367 | // Only need to box if the argument is not also polymorphic.
|
---|
368 | return !isPolyType( newType );
|
---|
369 | }
|
---|
370 |
|
---|
371 | bool needsBoxing(
|
---|
372 | const ast::Type * param, const ast::Type * arg,
|
---|
373 | const ast::ApplicationExpr * expr,
|
---|
374 | const ast::TypeSubstitution * subst ) {
|
---|
375 | const ast::FunctionType * function = getFunctionType( expr->func->result );
|
---|
376 | assertf( function, "ApplicationExpr has non-function type: %s", toCString( expr->func->result ) );
|
---|
377 | TypeVarMap exprTyVars;
|
---|
378 | makeTypeVarMap( function, exprTyVars );
|
---|
379 | return needsBoxing( param, arg, exprTyVars, subst );
|
---|
380 | }
|
---|
381 |
|
---|
382 | void addToTypeVarMap( const ast::TypeDecl * decl, TypeVarMap & typeVars ) {
|
---|
383 | typeVars.insert( ast::TypeEnvKey( decl, 0, 0 ), ast::TypeData( decl ) );
|
---|
384 | }
|
---|
385 |
|
---|
386 | void addToTypeVarMap( const ast::TypeInstType * type, TypeVarMap & typeVars ) {
|
---|
387 | typeVars.insert( ast::TypeEnvKey( *type ), ast::TypeData( type->base ) );
|
---|
388 | }
|
---|
389 |
|
---|
390 | void makeTypeVarMap( const ast::Type * type, TypeVarMap & typeVars ) {
|
---|
391 | if ( auto func = dynamic_cast<ast::FunctionType const *>( type ) ) {
|
---|
392 | for ( auto & typeVar : func->forall ) {
|
---|
393 | assert( typeVar );
|
---|
394 | addToTypeVarMap( typeVar, typeVars );
|
---|
395 | }
|
---|
396 | }
|
---|
397 | if ( auto pointer = dynamic_cast<ast::PointerType const *>( type ) ) {
|
---|
398 | makeTypeVarMap( pointer->base, typeVars );
|
---|
399 | }
|
---|
400 | }
|
---|
401 |
|
---|
402 | void makeTypeVarMap( const ast::FunctionDecl * decl, TypeVarMap & typeVars ) {
|
---|
403 | for ( auto & typeDecl : decl->type_params ) {
|
---|
404 | addToTypeVarMap( typeDecl, typeVars );
|
---|
405 | }
|
---|
406 | }
|
---|
407 |
|
---|
408 | } // namespace GenPoly
|
---|
409 |
|
---|
410 | // Local Variables: //
|
---|
411 | // tab-width: 4 //
|
---|
412 | // mode: c++ //
|
---|
413 | // compile-command: "make install" //
|
---|
414 | // End: //
|
---|