source: src/ResolvExpr/Unify.cc@ b0d9ff7

ADT ast-experimental pthread-emulation qualifiedEnum
Last change on this file since b0d9ff7 was b729c01, checked in by JiadaL <j82liang@…>, 3 years ago

Update enum unifier; now unifier compare types based on the enum's base
  • Property mode set to 100644
File size: 48.6 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// Unify.cc --
8//
9// Author : Richard C. Bilson
10// Created On : Sun May 17 12:27:10 2015
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Fri Dec 13 23:43:05 2019
13// Update Count : 46
14//
15
16#include "Unify.h"
17
18#include <cassert> // for assertf, assert
19#include <iterator> // for back_insert_iterator, back_inserter
20#include <map> // for _Rb_tree_const_iterator, _Rb_tree_i...
21#include <memory> // for unique_ptr
22#include <set> // for set
23#include <string> // for string, operator==, operator!=, bas...
24#include <utility> // for pair, move
25#include <vector>
26
27#include "AST/Copy.hpp"
28#include "AST/Decl.hpp"
29#include "AST/Node.hpp"
30#include "AST/Pass.hpp"
31#include "AST/Print.hpp"
32#include "AST/Type.hpp"
33#include "AST/TypeEnvironment.hpp"
34#include "Common/PassVisitor.h" // for PassVisitor
35#include "FindOpenVars.h" // for findOpenVars
36#include "SynTree/LinkageSpec.h" // for C
37#include "SynTree/Constant.h" // for Constant
38#include "SynTree/Declaration.h" // for TypeDecl, TypeDecl::Data, Declarati...
39#include "SynTree/Expression.h" // for TypeExpr, Expression, ConstantExpr
40#include "SynTree/Mutator.h" // for Mutator
41#include "SynTree/Type.h" // for Type, TypeInstType, FunctionType
42#include "SynTree/Visitor.h" // for Visitor
43#include "Tuples/Tuples.h" // for isTtype
44#include "TypeEnvironment.h" // for EqvClass, AssertionSet, OpenVarSet
45#include "typeops.h" // for flatten, occurs, commonType
46
47namespace ast {
48 class SymbolTable;
49}
50
51namespace SymTab {
52class Indexer;
53} // namespace SymTab
54
55// #define DEBUG
56
57namespace ResolvExpr {
58
59 struct Unify_old : public WithShortCircuiting {
60 Unify_old( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer );
61
62 bool get_result() const { return result; }
63
64 void previsit( BaseSyntaxNode * ) { visit_children = false; }
65
66 void postvisit( VoidType * voidType );
67 void postvisit( BasicType * basicType );
68 void postvisit( PointerType * pointerType );
69 void postvisit( ArrayType * arrayType );
70 void postvisit( ReferenceType * refType );
71 void postvisit( FunctionType * functionType );
72 void postvisit( StructInstType * aggregateUseType );
73 void postvisit( UnionInstType * aggregateUseType );
74 void postvisit( EnumInstType * aggregateUseType );
75 void postvisit( TraitInstType * aggregateUseType );
76 void postvisit( TypeInstType * aggregateUseType );
77 void postvisit( TupleType * tupleType );
78 void postvisit( VarArgsType * varArgsType );
79 void postvisit( ZeroType * zeroType );
80 void postvisit( OneType * oneType );
81
82 private:
83 template< typename RefType > void handleRefType( RefType *inst, Type *other );
84 template< typename RefType > void handleGenericRefType( RefType *inst, Type *other );
85
86 bool result;
87 Type *type2; // inherited
88 TypeEnvironment &env;
89 AssertionSet &needAssertions;
90 AssertionSet &haveAssertions;
91 const OpenVarSet &openVars;
92 WidenMode widen;
93 const SymTab::Indexer &indexer;
94 };
95
96 /// Attempts an inexact unification of type1 and type2.
97 /// Returns false if no such unification; if the types can be unified, sets common (unless they unify exactly and have identical type qualifiers)
98 bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer, Type *&common );
99 bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer );
100
101 bool unifyExact(
102 const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env,
103 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
104 WidenMode widen, const ast::SymbolTable & symtab );
105
106 bool typesCompatible( const Type * first, const Type * second, const SymTab::Indexer & indexer, const TypeEnvironment & env ) {
107 TypeEnvironment newEnv;
108 OpenVarSet openVars, closedVars; // added closedVars
109 AssertionSet needAssertions, haveAssertions;
110 Type * newFirst = first->clone(), * newSecond = second->clone();
111 env.apply( newFirst );
112 env.apply( newSecond );
113
114 // do we need to do this? Seems like we do, types should be able to be compatible if they
115 // have free variables that can unify
116 findOpenVars( newFirst, openVars, closedVars, needAssertions, haveAssertions, false );
117 findOpenVars( newSecond, openVars, closedVars, needAssertions, haveAssertions, true );
118
119 bool result = unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
120 delete newFirst;
121 delete newSecond;
122 return result;
123 }
124
125 bool typesCompatible(
126 const ast::Type * first, const ast::Type * second, const ast::SymbolTable & symtab,
127 const ast::TypeEnvironment & env ) {
128 ast::TypeEnvironment newEnv;
129 ast::OpenVarSet open, closed;
130 ast::AssertionSet need, have;
131
132 ast::ptr<ast::Type> newFirst{ first }, newSecond{ second };
133 env.apply( newFirst );
134 env.apply( newSecond );
135
136 findOpenVars( newFirst, open, closed, need, have, FirstClosed );
137 findOpenVars( newSecond, open, closed, need, have, FirstOpen );
138
139 return unifyExact(newFirst, newSecond, newEnv, need, have, open, noWiden(), symtab );
140 }
141
142 bool typesCompatibleIgnoreQualifiers( const Type * first, const Type * second, const SymTab::Indexer &indexer, const TypeEnvironment &env ) {
143 TypeEnvironment newEnv;
144 OpenVarSet openVars;
145 AssertionSet needAssertions, haveAssertions;
146 Type *newFirst = first->clone(), *newSecond = second->clone();
147 env.apply( newFirst );
148 env.apply( newSecond );
149 newFirst->get_qualifiers() = Type::Qualifiers();
150 newSecond->get_qualifiers() = Type::Qualifiers();
151
152 bool result = unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
153 delete newFirst;
154 delete newSecond;
155 return result;
156 }
157
158 bool typesCompatibleIgnoreQualifiers(
159 const ast::Type * first, const ast::Type * second, const ast::SymbolTable & symtab,
160 const ast::TypeEnvironment & env ) {
161 ast::TypeEnvironment newEnv;
162 ast::OpenVarSet open;
163 ast::AssertionSet need, have;
164
165 ast::Type * newFirst = shallowCopy( first );
166 ast::Type * newSecond = shallowCopy( second );
167 if ( auto temp = dynamic_cast<const ast::EnumInstType *>(first) ) {
168 if ( !dynamic_cast< const ast::EnumInstType * >( second ) ) {
169 const ast::EnumDecl * baseEnum = dynamic_cast<const ast::EnumDecl *>(temp->base.get());
170 if ( auto t = baseEnum->base.get() ) {
171 newFirst = ast::shallowCopy( t );
172 }
173 }
174 } else if ( auto temp = dynamic_cast<const ast::EnumInstType *>(second) ) {
175 const ast::EnumDecl * baseEnum = dynamic_cast<const ast::EnumDecl *>(temp->base.get());
176 if ( auto t = baseEnum->base.get() ) {
177 newSecond = ast::shallowCopy( t );
178 }
179 }
180
181 newFirst ->qualifiers = {};
182 newSecond->qualifiers = {};
183 ast::ptr< ast::Type > t1_(newFirst );
184 ast::ptr< ast::Type > t2_(newSecond);
185
186 ast::ptr< ast::Type > subFirst = env.apply(newFirst).node;
187 ast::ptr< ast::Type > subSecond = env.apply(newSecond).node;
188
189 return unifyExact(
190 subFirst,
191 subSecond,
192 newEnv, need, have, open, noWiden(), symtab );
193 }
194
195 bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
196 OpenVarSet closedVars;
197 findOpenVars( type1, openVars, closedVars, needAssertions, haveAssertions, false );
198 findOpenVars( type2, openVars, closedVars, needAssertions, haveAssertions, true );
199 Type *commonType = 0;
200 if ( unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType ) ) {
201 if ( commonType ) {
202 delete commonType;
203 } // if
204 return true;
205 } else {
206 return false;
207 } // if
208 }
209
210 bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer, Type *&commonType ) {
211 OpenVarSet closedVars;
212 findOpenVars( type1, openVars, closedVars, needAssertions, haveAssertions, false );
213 findOpenVars( type2, openVars, closedVars, needAssertions, haveAssertions, true );
214 return unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType );
215 }
216
217 bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ) {
218#ifdef DEBUG
219 TypeEnvironment debugEnv( env );
220#endif
221 if ( type1->get_qualifiers() != type2->get_qualifiers() ) {
222 return false;
223 }
224
225 bool result;
226 TypeInstType *var1 = dynamic_cast< TypeInstType* >( type1 );
227 TypeInstType *var2 = dynamic_cast< TypeInstType* >( type2 );
228 OpenVarSet::const_iterator entry1, entry2;
229 if ( var1 ) {
230 entry1 = openVars.find( var1->get_name() );
231 } // if
232 if ( var2 ) {
233 entry2 = openVars.find( var2->get_name() );
234 } // if
235 bool isopen1 = var1 && ( entry1 != openVars.end() );
236 bool isopen2 = var2 && ( entry2 != openVars.end() );
237
238 if ( isopen1 && isopen2 ) {
239 if ( entry1->second.kind != entry2->second.kind ) {
240 result = false;
241 } else {
242 result = env.bindVarToVar(
243 var1, var2, TypeDecl::Data{ entry1->second, entry2->second }, needAssertions,
244 haveAssertions, openVars, widen, indexer );
245 }
246 } else if ( isopen1 ) {
247 result = env.bindVar( var1, type2, entry1->second, needAssertions, haveAssertions, openVars, widen, indexer );
248 } else if ( isopen2 ) { // TODO: swap widen values in call, since type positions are flipped?
249 result = env.bindVar( var2, type1, entry2->second, needAssertions, haveAssertions, openVars, widen, indexer );
250 } else {
251 PassVisitor<Unify_old> comparator( type2, env, needAssertions, haveAssertions, openVars, widen, indexer );
252 type1->accept( comparator );
253 result = comparator.pass.get_result();
254 } // if
255#ifdef DEBUG
256 std::cerr << "============ unifyExact" << std::endl;
257 std::cerr << "type1 is ";
258 type1->print( std::cerr );
259 std::cerr << std::endl << "type2 is ";
260 type2->print( std::cerr );
261 std::cerr << std::endl << "openVars are ";
262 printOpenVarSet( openVars, std::cerr, 8 );
263 std::cerr << std::endl << "input env is " << std::endl;
264 debugEnv.print( std::cerr, 8 );
265 std::cerr << std::endl << "result env is " << std::endl;
266 env.print( std::cerr, 8 );
267 std::cerr << "result is " << result << std::endl;
268#endif
269 return result;
270 }
271
272 bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
273 return unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
274 }
275
276 bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer, Type *&common ) {
277 Type::Qualifiers tq1 = type1->get_qualifiers(), tq2 = type2->get_qualifiers();
278 type1->get_qualifiers() = Type::Qualifiers();
279 type2->get_qualifiers() = Type::Qualifiers();
280 bool result;
281#ifdef DEBUG
282 std::cerr << "unifyInexact type 1 is ";
283 type1->print( std::cerr );
284 std::cerr << " type 2 is ";
285 type2->print( std::cerr );
286 std::cerr << std::endl;
287#endif
288 if ( ! unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, widen, indexer ) ) {
289#ifdef DEBUG
290 std::cerr << "unifyInexact: no exact unification found" << std::endl;
291#endif
292 if ( ( common = commonType( type1, type2, widen.first, widen.second, indexer, env, openVars ) ) ) {
293 common->tq = tq1.unify( tq2 );
294#ifdef DEBUG
295 std::cerr << "unifyInexact: common type is ";
296 common->print( std::cerr );
297 std::cerr << std::endl;
298#endif
299 result = true;
300 } else {
301#ifdef DEBUG
302 std::cerr << "unifyInexact: no common type found" << std::endl;
303#endif
304 result = false;
305 } // if
306 } else {
307 if ( tq1 != tq2 ) {
308 if ( ( tq1 > tq2 || widen.first ) && ( tq2 > tq1 || widen.second ) ) {
309 common = type1->clone();
310 common->tq = tq1.unify( tq2 );
311 result = true;
312 } else {
313 result = false;
314 } // if
315 } else {
316 common = type1->clone();
317 common->tq = tq1.unify( tq2 );
318 result = true;
319 } // if
320 } // if
321 type1->get_qualifiers() = tq1;
322 type2->get_qualifiers() = tq2;
323 return result;
324 }
325
326 Unify_old::Unify_old( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer )
327 : result( false ), type2( type2 ), env( env ), needAssertions( needAssertions ), haveAssertions( haveAssertions ), openVars( openVars ), widen( widen ), indexer( indexer ) {
328 }
329
330 void Unify_old::postvisit( __attribute__((unused)) VoidType *voidType) {
331 result = dynamic_cast< VoidType* >( type2 );
332 }
333
334 void Unify_old::postvisit(BasicType *basicType) {
335 if ( BasicType *otherBasic = dynamic_cast< BasicType* >( type2 ) ) {
336 result = basicType->get_kind() == otherBasic->get_kind();
337 } // if
338 }
339
340 void markAssertionSet( AssertionSet &assertions, DeclarationWithType *assert ) {
341 AssertionSet::iterator i = assertions.find( assert );
342 if ( i != assertions.end() ) {
343 i->second.isUsed = true;
344 } // if
345 }
346
347 void markAssertions( AssertionSet &assertion1, AssertionSet &assertion2, Type *type ) {
348 for ( std::list< TypeDecl* >::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
349 for ( std::list< DeclarationWithType* >::const_iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) {
350 markAssertionSet( assertion1, *assert );
351 markAssertionSet( assertion2, *assert );
352 } // for
353 } // for
354 }
355
356 void Unify_old::postvisit(PointerType *pointerType) {
357 if ( PointerType *otherPointer = dynamic_cast< PointerType* >( type2 ) ) {
358 result = unifyExact( pointerType->get_base(), otherPointer->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
359 markAssertions( haveAssertions, needAssertions, pointerType );
360 markAssertions( haveAssertions, needAssertions, otherPointer );
361 } // if
362 }
363
364 void Unify_old::postvisit(ReferenceType *refType) {
365 if ( ReferenceType *otherRef = dynamic_cast< ReferenceType* >( type2 ) ) {
366 result = unifyExact( refType->get_base(), otherRef->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
367 markAssertions( haveAssertions, needAssertions, refType );
368 markAssertions( haveAssertions, needAssertions, otherRef );
369 } // if
370 }
371
372 void Unify_old::postvisit(ArrayType *arrayType) {
373 ArrayType *otherArray = dynamic_cast< ArrayType* >( type2 );
374 // to unify, array types must both be VLA or both not VLA
375 // and must both have a dimension expression or not have a dimension
376 if ( otherArray && arrayType->get_isVarLen() == otherArray->get_isVarLen() ) {
377
378 if ( ! arrayType->get_isVarLen() && ! otherArray->get_isVarLen() &&
379 arrayType->get_dimension() != 0 && otherArray->get_dimension() != 0 ) {
380 ConstantExpr * ce1 = dynamic_cast< ConstantExpr * >( arrayType->get_dimension() );
381 ConstantExpr * ce2 = dynamic_cast< ConstantExpr * >( otherArray->get_dimension() );
382 // see C11 Reference Manual 6.7.6.2.6
383 // two array types with size specifiers that are integer constant expressions are
384 // compatible if both size specifiers have the same constant value
385 if ( ce1 && ce2 ) {
386 Constant * c1 = ce1->get_constant();
387 Constant * c2 = ce2->get_constant();
388
389 if ( c1->get_value() != c2->get_value() ) {
390 // does not unify if the dimension is different
391 return;
392 }
393 }
394 }
395
396 result = unifyExact( arrayType->get_base(), otherArray->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
397 } // if
398 }
399
400 template< typename Iterator, typename Func >
401 std::unique_ptr<Type> combineTypes( Iterator begin, Iterator end, Func & toType ) {
402 std::list< Type * > types;
403 for ( ; begin != end; ++begin ) {
404 // it's guaranteed that a ttype variable will be bound to a flat tuple, so ensure that this results in a flat tuple
405 flatten( toType( *begin ), back_inserter( types ) );
406 }
407 return std::unique_ptr<Type>( new TupleType( Type::Qualifiers(), types ) );
408 }
409
410 template< typename Iterator1, typename Iterator2 >
411 bool unifyTypeList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
412 auto get_type = [](DeclarationWithType * dwt){ return dwt->get_type(); };
413 for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) {
414 Type * t1 = (*list1Begin)->get_type();
415 Type * t2 = (*list2Begin)->get_type();
416 bool isTtype1 = Tuples::isTtype( t1 );
417 bool isTtype2 = Tuples::isTtype( t2 );
418 // xxx - assumes ttype must be last parameter
419 // xxx - there may be a nice way to refactor this, but be careful because the argument positioning might matter in some cases.
420 if ( isTtype1 && ! isTtype2 ) {
421 // combine all of the things in list2, then unify
422 return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
423 } else if ( isTtype2 && ! isTtype1 ) {
424 // combine all of the things in list1, then unify
425 return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
426 } else if ( ! unifyExact( t1, t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ) ) {
427 return false;
428 } // if
429 } // for
430 // may get to the end of one argument list before the end of the other. This is only okay when the other is a ttype
431 if ( list1Begin != list1End ) {
432 // try unifying empty tuple type with ttype
433 Type * t1 = (*list1Begin)->get_type();
434 if ( Tuples::isTtype( t1 ) ) {
435 return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
436 } else return false;
437 } else if ( list2Begin != list2End ) {
438 // try unifying empty tuple type with ttype
439 Type * t2 = (*list2Begin)->get_type();
440 if ( Tuples::isTtype( t2 ) ) {
441 return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
442 } else return false;
443 } else {
444 return true;
445 } // if
446 }
447
448 /// Finds ttypes and replaces them with their expansion, if known.
449 /// This needs to be done so that satisfying ttype assertions is easier.
450 /// If this isn't done then argument lists can have wildly different
451 /// size and structure, when they should be compatible.
452 struct TtypeExpander_old : public WithShortCircuiting {
453 TypeEnvironment & tenv;
454 TtypeExpander_old( TypeEnvironment & tenv ) : tenv( tenv ) {}
455 void premutate( TypeInstType * ) { visit_children = false; }
456 Type * postmutate( TypeInstType * typeInst ) {
457 if ( const EqvClass *eqvClass = tenv.lookup( typeInst->get_name() ) ) {
458 // expand ttype parameter into its actual type
459 if ( eqvClass->data.kind == TypeDecl::Ttype && eqvClass->type ) {
460 delete typeInst;
461 return eqvClass->type->clone();
462 }
463 }
464 return typeInst;
465 }
466 };
467
468 /// flattens a list of declarations, so that each tuple type has a single declaration.
469 /// makes use of TtypeExpander to ensure ttypes are flat as well.
470 void flattenList( std::list< DeclarationWithType * > src, std::list< DeclarationWithType * > & dst, TypeEnvironment & env ) {
471 dst.clear();
472 for ( DeclarationWithType * dcl : src ) {
473 PassVisitor<TtypeExpander_old> expander( env );
474 dcl->acceptMutator( expander );
475 std::list< Type * > types;
476 flatten( dcl->get_type(), back_inserter( types ) );
477 for ( Type * t : types ) {
478 // outermost const, volatile, _Atomic qualifiers in parameters should not play a role in the unification of function types, since they do not determine whether a function is callable.
479 // Note: MUST consider at least mutex qualifier, since functions can be overloaded on outermost mutex and a mutex function has different requirements than a non-mutex function.
480 t->get_qualifiers() -= Type::Qualifiers(Type::Const | Type::Volatile | Type::Atomic);
481
482 dst.push_back( new ObjectDecl( "", Type::StorageClasses(), LinkageSpec::C, nullptr, t, nullptr ) );
483 }
484 delete dcl;
485 }
486 }
487
488 void Unify_old::postvisit(FunctionType *functionType) {
489 FunctionType *otherFunction = dynamic_cast< FunctionType* >( type2 );
490 if ( otherFunction && functionType->get_isVarArgs() == otherFunction->get_isVarArgs() ) {
491 // flatten the parameter lists for both functions so that tuple structure
492 // doesn't affect unification. Must be a clone so that the types don't change.
493 std::unique_ptr<FunctionType> flatFunc( functionType->clone() );
494 std::unique_ptr<FunctionType> flatOther( otherFunction->clone() );
495 flattenList( flatFunc->get_parameters(), flatFunc->get_parameters(), env );
496 flattenList( flatOther->get_parameters(), flatOther->get_parameters(), env );
497
498 // sizes don't have to match if ttypes are involved; need to be more precise wrt where the ttype is to prevent errors
499 if (
500 (flatFunc->parameters.size() == flatOther->parameters.size() &&
501 flatFunc->returnVals.size() == flatOther->returnVals.size())
502 || flatFunc->isTtype()
503 || flatOther->isTtype()
504 ) {
505 if ( unifyTypeList( flatFunc->parameters.begin(), flatFunc->parameters.end(), flatOther->parameters.begin(), flatOther->parameters.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
506 if ( unifyTypeList( flatFunc->returnVals.begin(), flatFunc->returnVals.end(), flatOther->returnVals.begin(), flatOther->returnVals.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
507
508 // the original types must be used in mark assertions, since pointer comparisons are used
509 markAssertions( haveAssertions, needAssertions, functionType );
510 markAssertions( haveAssertions, needAssertions, otherFunction );
511
512 result = true;
513 } // if
514 } // if
515 } // if
516 } // if
517 }
518
519 template< typename RefType >
520 void Unify_old::handleRefType( RefType *inst, Type *other ) {
521 // check that other type is compatible and named the same
522 RefType *otherStruct = dynamic_cast< RefType* >( other );
523 result = otherStruct && inst->name == otherStruct->name;
524 }
525
526 template< typename RefType >
527 void Unify_old::handleGenericRefType( RefType *inst, Type *other ) {
528 // Check that other type is compatible and named the same
529 handleRefType( inst, other );
530 if ( ! result ) return;
531 // Check that parameters of types unify, if any
532 std::list< Expression* > params = inst->parameters;
533 std::list< Expression* > otherParams = ((RefType*)other)->parameters;
534
535 std::list< Expression* >::const_iterator it = params.begin(), jt = otherParams.begin();
536 for ( ; it != params.end() && jt != otherParams.end(); ++it, ++jt ) {
537 TypeExpr *param = dynamic_cast< TypeExpr* >(*it);
538 assertf(param, "Aggregate parameters should be type expressions");
539 TypeExpr *otherParam = dynamic_cast< TypeExpr* >(*jt);
540 assertf(otherParam, "Aggregate parameters should be type expressions");
541
542 Type* paramTy = param->get_type();
543 Type* otherParamTy = otherParam->get_type();
544
545 bool tupleParam = Tuples::isTtype( paramTy );
546 bool otherTupleParam = Tuples::isTtype( otherParamTy );
547
548 if ( tupleParam && otherTupleParam ) {
549 ++it; ++jt; // skip ttype parameters for break
550 } else if ( tupleParam ) {
551 // bundle other parameters into tuple to match
552 std::list< Type * > binderTypes;
553
554 do {
555 binderTypes.push_back( otherParam->get_type()->clone() );
556 ++jt;
557
558 if ( jt == otherParams.end() ) break;
559
560 otherParam = dynamic_cast< TypeExpr* >(*jt);
561 assertf(otherParam, "Aggregate parameters should be type expressions");
562 } while (true);
563
564 otherParamTy = new TupleType{ paramTy->get_qualifiers(), binderTypes };
565 ++it; // skip ttype parameter for break
566 } else if ( otherTupleParam ) {
567 // bundle parameters into tuple to match other
568 std::list< Type * > binderTypes;
569
570 do {
571 binderTypes.push_back( param->get_type()->clone() );
572 ++it;
573
574 if ( it == params.end() ) break;
575
576 param = dynamic_cast< TypeExpr* >(*it);
577 assertf(param, "Aggregate parameters should be type expressions");
578 } while (true);
579
580 paramTy = new TupleType{ otherParamTy->get_qualifiers(), binderTypes };
581 ++jt; // skip ttype parameter for break
582 }
583
584 if ( ! unifyExact( paramTy, otherParamTy, env, needAssertions, haveAssertions, openVars, WidenMode(false, false), indexer ) ) {
585 result = false;
586 return;
587 }
588
589 // ttype parameter should be last
590 if ( tupleParam || otherTupleParam ) break;
591 }
592 result = ( it == params.end() && jt == otherParams.end() );
593 }
594
595 void Unify_old::postvisit(StructInstType *structInst) {
596 handleGenericRefType( structInst, type2 );
597 }
598
599 void Unify_old::postvisit(UnionInstType *unionInst) {
600 handleGenericRefType( unionInst, type2 );
601 }
602
603 void Unify_old::postvisit(EnumInstType *enumInst) {
604 handleRefType( enumInst, type2 );
605 }
606
607 void Unify_old::postvisit(TraitInstType *contextInst) {
608 handleRefType( contextInst, type2 );
609 }
610
611 void Unify_old::postvisit(TypeInstType *typeInst) {
612 assert( openVars.find( typeInst->get_name() ) == openVars.end() );
613 TypeInstType *otherInst = dynamic_cast< TypeInstType* >( type2 );
614 if ( otherInst && typeInst->get_name() == otherInst->get_name() ) {
615 result = true;
616/// } else {
617/// NamedTypeDecl *nt = indexer.lookupType( typeInst->get_name() );
618/// if ( nt ) {
619/// TypeDecl *type = dynamic_cast< TypeDecl* >( nt );
620/// assert( type );
621/// if ( type->get_base() ) {
622/// result = unifyExact( type->get_base(), typeInst, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
623/// }
624/// }
625 } // if
626 }
627
628 template< typename Iterator1, typename Iterator2 >
629 bool unifyList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
630 auto get_type = [](Type * t) { return t; };
631 for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) {
632 Type * t1 = *list1Begin;
633 Type * t2 = *list2Begin;
634 bool isTtype1 = Tuples::isTtype( t1 );
635 bool isTtype2 = Tuples::isTtype( t2 );
636 // xxx - assumes ttype must be last parameter
637 // xxx - there may be a nice way to refactor this, but be careful because the argument positioning might matter in some cases.
638 if ( isTtype1 && ! isTtype2 ) {
639 // combine all of the things in list2, then unify
640 return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
641 } else if ( isTtype2 && ! isTtype1 ) {
642 // combine all of the things in list1, then unify
643 return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
644 } else if ( ! unifyExact( t1, t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ) ) {
645 return false;
646 } // if
647
648 } // for
649 if ( list1Begin != list1End ) {
650 // try unifying empty tuple type with ttype
651 Type * t1 = *list1Begin;
652 if ( Tuples::isTtype( t1 ) ) {
653 return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
654 } else return false;
655 } else if ( list2Begin != list2End ) {
656 // try unifying empty tuple type with ttype
657 Type * t2 = *list2Begin;
658 if ( Tuples::isTtype( t2 ) ) {
659 return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
660 } else return false;
661 } else {
662 return true;
663 } // if
664 }
665
666 void Unify_old::postvisit(TupleType *tupleType) {
667 if ( TupleType *otherTuple = dynamic_cast< TupleType* >( type2 ) ) {
668 std::unique_ptr<TupleType> flat1( tupleType->clone() );
669 std::unique_ptr<TupleType> flat2( otherTuple->clone() );
670 std::list<Type *> types1, types2;
671
672 PassVisitor<TtypeExpander_old> expander( env );
673 flat1->acceptMutator( expander );
674 flat2->acceptMutator( expander );
675
676 flatten( flat1.get(), back_inserter( types1 ) );
677 flatten( flat2.get(), back_inserter( types2 ) );
678
679 result = unifyList( types1.begin(), types1.end(), types2.begin(), types2.end(), env, needAssertions, haveAssertions, openVars, indexer );
680 } // if
681 }
682
683 void Unify_old::postvisit( __attribute__((unused)) VarArgsType *varArgsType ) {
684 result = dynamic_cast< VarArgsType* >( type2 );
685 }
686
687 void Unify_old::postvisit( __attribute__((unused)) ZeroType *zeroType ) {
688 result = dynamic_cast< ZeroType* >( type2 );
689 }
690
691 void Unify_old::postvisit( __attribute__((unused)) OneType *oneType ) {
692 result = dynamic_cast< OneType* >( type2 );
693 }
694
695 Type * extractResultType( FunctionType * function ) {
696 if ( function->get_returnVals().size() == 0 ) {
697 return new VoidType( Type::Qualifiers() );
698 } else if ( function->get_returnVals().size() == 1 ) {
699 return function->get_returnVals().front()->get_type()->clone();
700 } else {
701 std::list< Type * > types;
702 for ( DeclarationWithType * decl : function->get_returnVals() ) {
703 types.push_back( decl->get_type()->clone() );
704 } // for
705 return new TupleType( Type::Qualifiers(), types );
706 }
707 }
708
709 class Unify_new final : public ast::WithShortCircuiting {
710 const ast::Type * type2;
711 ast::TypeEnvironment & tenv;
712 ast::AssertionSet & need;
713 ast::AssertionSet & have;
714 const ast::OpenVarSet & open;
715 WidenMode widen;
716 const ast::SymbolTable & symtab;
717 public:
718 static size_t traceId;
719 bool result;
720
721 Unify_new(
722 const ast::Type * type2, ast::TypeEnvironment & env, ast::AssertionSet & need,
723 ast::AssertionSet & have, const ast::OpenVarSet & open, WidenMode widen,
724 const ast::SymbolTable & symtab )
725 : type2(type2), tenv(env), need(need), have(have), open(open), widen(widen),
726 symtab(symtab), result(false) {}
727
728 void previsit( const ast::Node * ) { visit_children = false; }
729
730 void postvisit( const ast::VoidType * ) {
731 result = dynamic_cast< const ast::VoidType * >( type2 );
732 }
733
734 void postvisit( const ast::BasicType * basic ) {
735 if ( auto basic2 = dynamic_cast< const ast::BasicType * >( type2 ) ) {
736 result = basic->kind == basic2->kind;
737 }
738 }
739
740 void postvisit( const ast::PointerType * pointer ) {
741 if ( auto pointer2 = dynamic_cast< const ast::PointerType * >( type2 ) ) {
742 result = unifyExact(
743 pointer->base, pointer2->base, tenv, need, have, open,
744 noWiden(), symtab );
745 }
746 }
747
748 void postvisit( const ast::ArrayType * array ) {
749 auto array2 = dynamic_cast< const ast::ArrayType * >( type2 );
750 if ( ! array2 ) return;
751
752 // to unify, array types must both be VLA or both not VLA and both must have a
753 // dimension expression or not have a dimension
754 if ( array->isVarLen != array2->isVarLen ) return;
755 if ( ! array->isVarLen && ! array2->isVarLen
756 && array->dimension && array2->dimension ) {
757 auto ce1 = array->dimension.as< ast::ConstantExpr >();
758 auto ce2 = array2->dimension.as< ast::ConstantExpr >();
759
760 // see C11 Reference Manual 6.7.6.2.6
761 // two array types with size specifiers that are integer constant expressions are
762 // compatible if both size specifiers have the same constant value
763 if ( ce1 && ce2 && ce1->intValue() != ce2->intValue() ) return;
764 }
765
766 result = unifyExact(
767 array->base, array2->base, tenv, need, have, open, noWiden(),
768 symtab );
769 }
770
771 void postvisit( const ast::ReferenceType * ref ) {
772 if ( auto ref2 = dynamic_cast< const ast::ReferenceType * >( type2 ) ) {
773 result = unifyExact(
774 ref->base, ref2->base, tenv, need, have, open, noWiden(),
775 symtab );
776 }
777 }
778
779 private:
780 /// Replaces ttype variables with their bound types.
781 /// If this isn't done when satifying ttype assertions, then argument lists can have
782 /// different size and structure when they should be compatible.
783 struct TtypeExpander_new : public ast::WithShortCircuiting, public ast::PureVisitor {
784 ast::TypeEnvironment & tenv;
785
786 TtypeExpander_new( ast::TypeEnvironment & env ) : tenv( env ) {}
787
788 const ast::Type * postvisit( const ast::TypeInstType * typeInst ) {
789 if ( const ast::EqvClass * clz = tenv.lookup( *typeInst ) ) {
790 // expand ttype parameter into its actual type
791 if ( clz->data.kind == ast::TypeDecl::Ttype && clz->bound ) {
792 return clz->bound;
793 }
794 }
795 return typeInst;
796 }
797 };
798
799 /// returns flattened version of `src`
800 static std::vector< ast::ptr< ast::Type > > flattenList(
801 const std::vector< ast::ptr< ast::Type > > & src, ast::TypeEnvironment & env
802 ) {
803 std::vector< ast::ptr< ast::Type > > dst;
804 dst.reserve( src.size() );
805 for ( const auto & d : src ) {
806 ast::Pass<TtypeExpander_new> expander{ env };
807 // TtypeExpander pass is impure (may mutate nodes in place)
808 // need to make nodes shared to prevent accidental mutation
809 ast::ptr<ast::Type> dc = d->accept(expander);
810 auto types = flatten( dc );
811 for ( ast::ptr< ast::Type > & t : types ) {
812 // outermost const, volatile, _Atomic qualifiers in parameters should not play
813 // a role in the unification of function types, since they do not determine
814 // whether a function is callable.
815 // NOTE: **must** consider at least mutex qualifier, since functions can be
816 // overloaded on outermost mutex and a mutex function has different
817 // requirements than a non-mutex function
818 remove_qualifiers( t, ast::CV::Const | ast::CV::Volatile | ast::CV::Atomic );
819 dst.emplace_back( t );
820 }
821 }
822 return dst;
823 }
824
825 /// Creates a tuple type based on a list of DeclWithType
826 template< typename Iter >
827 static const ast::Type * tupleFromTypes( Iter crnt, Iter end ) {
828 std::vector< ast::ptr< ast::Type > > types;
829 while ( crnt != end ) {
830 // it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure
831 // that this results in a flat tuple
832 flatten( *crnt, types );
833
834 ++crnt;
835 }
836
837 return new ast::TupleType{ std::move(types) };
838 }
839
840 template< typename Iter >
841 static bool unifyTypeList(
842 Iter crnt1, Iter end1, Iter crnt2, Iter end2, ast::TypeEnvironment & env,
843 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
844 const ast::SymbolTable & symtab
845 ) {
846 while ( crnt1 != end1 && crnt2 != end2 ) {
847 const ast::Type * t1 = *crnt1;
848 const ast::Type * t2 = *crnt2;
849 bool isTuple1 = Tuples::isTtype( t1 );
850 bool isTuple2 = Tuples::isTtype( t2 );
851
852 // assumes here that ttype *must* be last parameter
853 if ( isTuple1 && ! isTuple2 ) {
854 // combine remainder of list2, then unify
855 return unifyExact(
856 t1, tupleFromTypes( crnt2, end2 ), env, need, have, open,
857 noWiden(), symtab );
858 } else if ( ! isTuple1 && isTuple2 ) {
859 // combine remainder of list1, then unify
860 return unifyExact(
861 tupleFromTypes( crnt1, end1 ), t2, env, need, have, open,
862 noWiden(), symtab );
863 }
864
865 if ( ! unifyExact(
866 t1, t2, env, need, have, open, noWiden(), symtab )
867 ) return false;
868
869 ++crnt1; ++crnt2;
870 }
871
872 // May get to the end of one argument list before the other. This is only okay if the
873 // other is a ttype
874 if ( crnt1 != end1 ) {
875 // try unifying empty tuple with ttype
876 const ast::Type * t1 = *crnt1;
877 if ( ! Tuples::isTtype( t1 ) ) return false;
878 return unifyExact(
879 t1, tupleFromTypes( crnt2, end2 ), env, need, have, open,
880 noWiden(), symtab );
881 } else if ( crnt2 != end2 ) {
882 // try unifying empty tuple with ttype
883 const ast::Type * t2 = *crnt2;
884 if ( ! Tuples::isTtype( t2 ) ) return false;
885 return unifyExact(
886 tupleFromTypes( crnt1, end1 ), t2, env, need, have, open,
887 noWiden(), symtab );
888 }
889
890 return true;
891 }
892
893 static bool unifyTypeList(
894 const std::vector< ast::ptr< ast::Type > > & list1,
895 const std::vector< ast::ptr< ast::Type > > & list2,
896 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
897 const ast::OpenVarSet & open, const ast::SymbolTable & symtab
898 ) {
899 return unifyTypeList(
900 list1.begin(), list1.end(), list2.begin(), list2.end(), env, need, have, open,
901 symtab );
902 }
903
904 static void markAssertionSet( ast::AssertionSet & assns, const ast::VariableExpr * assn ) {
905 auto i = assns.find( assn );
906 if ( i != assns.end() ) {
907 i->second.isUsed = true;
908 }
909 }
910
911 /// mark all assertions in `type` used in both `assn1` and `assn2`
912 static void markAssertions(
913 ast::AssertionSet & assn1, ast::AssertionSet & assn2,
914 const ast::FunctionType * type
915 ) {
916 for ( auto & assert : type->assertions ) {
917 markAssertionSet( assn1, assert );
918 markAssertionSet( assn2, assert );
919 }
920 }
921
922 public:
923 void postvisit( const ast::FunctionType * func ) {
924 auto func2 = dynamic_cast< const ast::FunctionType * >( type2 );
925 if ( ! func2 ) return;
926
927 if ( func->isVarArgs != func2->isVarArgs ) return;
928
929 // Flatten the parameter lists for both functions so that tuple structure does not
930 // affect unification. Does not actually mutate function parameters.
931 auto params = flattenList( func->params, tenv );
932 auto params2 = flattenList( func2->params, tenv );
933
934 // sizes don't have to match if ttypes are involved; need to be more precise w.r.t.
935 // where the ttype is to prevent errors
936 if (
937 ( params.size() != params2.size() || func->returns.size() != func2->returns.size() )
938 && ! func->isTtype()
939 && ! func2->isTtype()
940 ) return;
941
942 if ( ! unifyTypeList( params, params2, tenv, need, have, open, symtab ) ) return;
943 if ( ! unifyTypeList(
944 func->returns, func2->returns, tenv, need, have, open, symtab ) ) return;
945
946 markAssertions( have, need, func );
947 markAssertions( have, need, func2 );
948
949 result = true;
950 }
951
952 private:
953 // Returns: other, cast as XInstType
954 // Assigns this->result: whether types are compatible (up to generic parameters)
955 template< typename XInstType >
956 const XInstType * handleRefType( const XInstType * inst, const ast::Type * other ) {
957 // check that the other type is compatible and named the same
958 auto otherInst = dynamic_cast< const XInstType * >( other );
959 if (otherInst && inst->name == otherInst->name) this->result = otherInst;
960 return otherInst;
961 }
962
963 /// Creates a tuple type based on a list of TypeExpr
964 template< typename Iter >
965 static const ast::Type * tupleFromExprs(
966 const ast::TypeExpr * param, Iter & crnt, Iter end, ast::CV::Qualifiers qs
967 ) {
968 std::vector< ast::ptr< ast::Type > > types;
969 do {
970 types.emplace_back( param->type );
971
972 ++crnt;
973 if ( crnt == end ) break;
974 param = strict_dynamic_cast< const ast::TypeExpr * >( crnt->get() );
975 } while(true);
976
977 return new ast::TupleType{ std::move(types), qs };
978 }
979
980 template< typename XInstType >
981 void handleGenericRefType( const XInstType * inst, const ast::Type * other ) {
982 // check that other type is compatible and named the same
983 const XInstType * otherInst = handleRefType( inst, other );
984 if ( ! this->result ) return;
985
986 // check that parameters of types unify, if any
987 const std::vector< ast::ptr< ast::Expr > > & params = inst->params;
988 const std::vector< ast::ptr< ast::Expr > > & params2 = otherInst->params;
989
990 auto it = params.begin();
991 auto jt = params2.begin();
992 for ( ; it != params.end() && jt != params2.end(); ++it, ++jt ) {
993 auto param = strict_dynamic_cast< const ast::TypeExpr * >( it->get() );
994 auto param2 = strict_dynamic_cast< const ast::TypeExpr * >( jt->get() );
995
996 ast::ptr< ast::Type > pty = param->type;
997 ast::ptr< ast::Type > pty2 = param2->type;
998
999 bool isTuple = Tuples::isTtype( pty );
1000 bool isTuple2 = Tuples::isTtype( pty2 );
1001
1002 if ( isTuple && isTuple2 ) {
1003 ++it; ++jt; // skip ttype parameters before break
1004 } else if ( isTuple ) {
1005 // bundle remaining params into tuple
1006 pty2 = tupleFromExprs( param2, jt, params2.end(), pty->qualifiers );
1007 ++it; // skip ttype parameter for break
1008 } else if ( isTuple2 ) {
1009 // bundle remaining params into tuple
1010 pty = tupleFromExprs( param, it, params.end(), pty2->qualifiers );
1011 ++jt; // skip ttype parameter for break
1012 }
1013
1014 if ( ! unifyExact(
1015 pty, pty2, tenv, need, have, open, noWiden(), symtab ) ) {
1016 result = false;
1017 return;
1018 }
1019
1020 // ttype parameter should be last
1021 if ( isTuple || isTuple2 ) break;
1022 }
1023 result = it == params.end() && jt == params2.end();
1024 }
1025
1026 public:
1027 void postvisit( const ast::StructInstType * aggrType ) {
1028 handleGenericRefType( aggrType, type2 );
1029 }
1030
1031 void postvisit( const ast::UnionInstType * aggrType ) {
1032 handleGenericRefType( aggrType, type2 );
1033 }
1034
1035 void postvisit( const ast::EnumInstType * aggrType ) {
1036 handleRefType( aggrType, type2 );
1037 }
1038
1039 void postvisit( const ast::TraitInstType * aggrType ) {
1040 handleRefType( aggrType, type2 );
1041 }
1042
1043 void postvisit( const ast::TypeInstType * typeInst ) {
1044 assert( open.find( *typeInst ) == open.end() );
1045 handleRefType( typeInst, type2 );
1046 }
1047
1048 private:
1049 /// Creates a tuple type based on a list of Type
1050 static const ast::Type * tupleFromTypes(
1051 const std::vector< ast::ptr< ast::Type > > & tys
1052 ) {
1053 std::vector< ast::ptr< ast::Type > > out;
1054 for ( const ast::Type * ty : tys ) {
1055 // it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure
1056 // that this results in a flat tuple
1057 flatten( ty, out );
1058 }
1059
1060 return new ast::TupleType{ std::move(out) };
1061 }
1062
1063 static bool unifyList(
1064 const std::vector< ast::ptr< ast::Type > > & list1,
1065 const std::vector< ast::ptr< ast::Type > > & list2, ast::TypeEnvironment & env,
1066 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
1067 const ast::SymbolTable & symtab
1068 ) {
1069 auto crnt1 = list1.begin();
1070 auto crnt2 = list2.begin();
1071 while ( crnt1 != list1.end() && crnt2 != list2.end() ) {
1072 const ast::Type * t1 = *crnt1;
1073 const ast::Type * t2 = *crnt2;
1074 bool isTuple1 = Tuples::isTtype( t1 );
1075 bool isTuple2 = Tuples::isTtype( t2 );
1076
1077 // assumes ttype must be last parameter
1078 if ( isTuple1 && ! isTuple2 ) {
1079 // combine entirety of list2, then unify
1080 return unifyExact(
1081 t1, tupleFromTypes( list2 ), env, need, have, open,
1082 noWiden(), symtab );
1083 } else if ( ! isTuple1 && isTuple2 ) {
1084 // combine entirety of list1, then unify
1085 return unifyExact(
1086 tupleFromTypes( list1 ), t2, env, need, have, open,
1087 noWiden(), symtab );
1088 }
1089
1090 if ( ! unifyExact(
1091 t1, t2, env, need, have, open, noWiden(), symtab )
1092 ) return false;
1093
1094 ++crnt1; ++crnt2;
1095 }
1096
1097 if ( crnt1 != list1.end() ) {
1098 // try unifying empty tuple type with ttype
1099 const ast::Type * t1 = *crnt1;
1100 if ( ! Tuples::isTtype( t1 ) ) return false;
1101 // xxx - this doesn't generate an empty tuple, contrary to comment; both ported
1102 // from Rob's code
1103 return unifyExact(
1104 t1, tupleFromTypes( list2 ), env, need, have, open,
1105 noWiden(), symtab );
1106 } else if ( crnt2 != list2.end() ) {
1107 // try unifying empty tuple with ttype
1108 const ast::Type * t2 = *crnt2;
1109 if ( ! Tuples::isTtype( t2 ) ) return false;
1110 // xxx - this doesn't generate an empty tuple, contrary to comment; both ported
1111 // from Rob's code
1112 return unifyExact(
1113 tupleFromTypes( list1 ), t2, env, need, have, open,
1114 noWiden(), symtab );
1115 }
1116
1117 return true;
1118 }
1119
1120 public:
1121 void postvisit( const ast::TupleType * tuple ) {
1122 auto tuple2 = dynamic_cast< const ast::TupleType * >( type2 );
1123 if ( ! tuple2 ) return;
1124
1125 ast::Pass<TtypeExpander_new> expander{ tenv };
1126
1127 const ast::Type * flat = tuple->accept( expander );
1128 const ast::Type * flat2 = tuple2->accept( expander );
1129
1130 auto types = flatten( flat );
1131 auto types2 = flatten( flat2 );
1132
1133 result = unifyList( types, types2, tenv, need, have, open, symtab );
1134 }
1135
1136 void postvisit( const ast::VarArgsType * ) {
1137 result = dynamic_cast< const ast::VarArgsType * >( type2 );
1138 }
1139
1140 void postvisit( const ast::ZeroType * ) {
1141 result = dynamic_cast< const ast::ZeroType * >( type2 );
1142 }
1143
1144 void postvisit( const ast::OneType * ) {
1145 result = dynamic_cast< const ast::OneType * >( type2 );
1146 }
1147
1148 private:
1149 template< typename RefType > void handleRefType( RefType *inst, Type *other );
1150 template< typename RefType > void handleGenericRefType( RefType *inst, Type *other );
1151 };
1152
1153 // size_t Unify_new::traceId = Stats::Heap::new_stacktrace_id("Unify_new");
1154 bool unify(
1155 const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
1156 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
1157 ast::OpenVarSet & open, const ast::SymbolTable & symtab
1158 ) {
1159 ast::ptr<ast::Type> common;
1160 return unify( type1, type2, env, need, have, open, symtab, common );
1161 }
1162
1163 bool unify(
1164 const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
1165 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
1166 ast::OpenVarSet & open, const ast::SymbolTable & symtab, ast::ptr<ast::Type> & common
1167 ) {
1168 ast::OpenVarSet closed;
1169 findOpenVars( type1, open, closed, need, have, FirstClosed );
1170 findOpenVars( type2, open, closed, need, have, FirstOpen );
1171 return unifyInexact(
1172 type1, type2, env, need, have, open, WidenMode{ true, true }, symtab, common );
1173 }
1174
1175 bool unifyExact(
1176 const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env,
1177 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
1178 WidenMode widen, const ast::SymbolTable & symtab
1179 ) {
1180 if ( type1->qualifiers != type2->qualifiers ) return false;
1181
1182 auto var1 = dynamic_cast< const ast::TypeInstType * >( type1 );
1183 auto var2 = dynamic_cast< const ast::TypeInstType * >( type2 );
1184 ast::OpenVarSet::const_iterator
1185 entry1 = var1 ? open.find( *var1 ) : open.end(),
1186 entry2 = var2 ? open.find( *var2 ) : open.end();
1187 bool isopen1 = entry1 != open.end();
1188 bool isopen2 = entry2 != open.end();
1189
1190 if ( isopen1 && isopen2 ) {
1191 if ( entry1->second.kind != entry2->second.kind ) return false;
1192 return env.bindVarToVar(
1193 var1, var2, ast::TypeDecl::Data{ entry1->second, entry2->second }, need, have,
1194 open, widen, symtab );
1195 } else if ( isopen1 ) {
1196 return env.bindVar( var1, type2, entry1->second, need, have, open, widen, symtab );
1197 } else if ( isopen2 ) {
1198 return env.bindVar( var2, type1, entry2->second, need, have, open, widen, symtab );
1199 } else {
1200 ast::Pass<Unify_new> comparator{ type2, env, need, have, open, widen, symtab };
1201 type1->accept( comparator );
1202 return comparator.core.result;
1203 }
1204 }
1205
1206 bool unifyInexact(
1207 const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
1208 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
1209 const ast::OpenVarSet & open, WidenMode widen, const ast::SymbolTable & symtab,
1210 ast::ptr<ast::Type> & common
1211 ) {
1212 ast::CV::Qualifiers q1 = type1->qualifiers, q2 = type2->qualifiers;
1213
1214 // force t1 and t2 to be cloned if their qualifiers must be stripped, so that type1 and
1215 // type2 are left unchanged; calling convention forces type{1,2}->strong_ref >= 1
1216 ast::Type * t1 = shallowCopy(type1.get());
1217 ast::Type * t2 = shallowCopy(type2.get());
1218 t1->qualifiers = {};
1219 t2->qualifiers = {};
1220 ast::ptr< ast::Type > t1_(t1);
1221 ast::ptr< ast::Type > t2_(t2);
1222
1223 if ( unifyExact( t1, t2, env, need, have, open, widen, symtab ) ) {
1224 // if exact unification on unqualified types, try to merge qualifiers
1225 if ( q1 == q2 || ( ( q1 > q2 || widen.first ) && ( q2 > q1 || widen.second ) ) ) {
1226 t1->qualifiers = q1 | q2;
1227 common = t1;
1228 return true;
1229 } else {
1230 return false;
1231 }
1232
1233 } else if (( common = commonType( t1, t2, widen, symtab, env, open ) )) {
1234 // no exact unification, but common type
1235 auto c = shallowCopy(common.get());
1236 c->qualifiers = q1 | q2;
1237 common = c;
1238 return true;
1239 } else {
1240 return false;
1241 }
1242 }
1243
1244 ast::ptr<ast::Type> extractResultType( const ast::FunctionType * func ) {
1245 if ( func->returns.empty() ) return new ast::VoidType{};
1246 if ( func->returns.size() == 1 ) return func->returns[0];
1247
1248 std::vector<ast::ptr<ast::Type>> tys;
1249 for ( const auto & decl : func->returns ) {
1250 tys.emplace_back( decl );
1251 }
1252 return new ast::TupleType{ std::move(tys) };
1253 }
1254} // namespace ResolvExpr
1255
1256// Local Variables: //
1257// tab-width: 4 //
1258// mode: c++ //
1259// compile-command: "make install" //
1260// End: //
Note: See TracBrowser for help on using the repository browser.