source: src/ResolvExpr/Unify.cc@ 0e76cf4f

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors deferred_resn demangler enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new with_gc
Last change on this file since 0e76cf4f was b726084, checked in by Rob Schluntz <rschlunt@…>, 9 years ago

Merge branch 'master' into tuples

Conflicts:

src/ControlStruct/LabelTypeChecker.cc
src/InitTweak/FixInit.cc
src/ResolvExpr/Resolver.cc
src/Tuples/TupleAssignment.cc
src/Tuples/TupleAssignment.h
  • Property mode set to 100644
File size: 24.7 KB
RevLine 
[a32b204]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//
[41a2620]7// Unify.cc --
[a32b204]8//
9// Author : Richard C. Bilson
10// Created On : Sun May 17 12:27:10 2015
[4040425]11// Last Modified By : Peter A. Buhr
12// Last Modified On : Wed Mar 2 17:37:05 2016
13// Update Count : 37
[a32b204]14//
[51b73452]15
16#include <set>
17#include <memory>
18
19#include "Unify.h"
20#include "TypeEnvironment.h"
21#include "typeops.h"
22#include "FindOpenVars.h"
23#include "SynTree/Visitor.h"
24#include "SynTree/Type.h"
25#include "SynTree/Declaration.h"
26#include "SymTab/Indexer.h"
[d3b7937]27#include "Common/utility.h"
[51b73452]28
29
[1cbca6e]30// #define DEBUG
[51b73452]31
32namespace ResolvExpr {
[a32b204]33 struct WidenMode {
34 WidenMode( bool widenFirst, bool widenSecond ): widenFirst( widenFirst ), widenSecond( widenSecond ) {}
35 WidenMode &operator|=( const WidenMode &other ) { widenFirst |= other.widenFirst; widenSecond |= other.widenSecond; return *this; }
36 WidenMode &operator&=( const WidenMode &other ) { widenFirst &= other.widenFirst; widenSecond &= other.widenSecond; return *this; }
37 WidenMode operator|( const WidenMode &other ) { WidenMode newWM( *this ); newWM |= other; return newWM; }
38 WidenMode operator&( const WidenMode &other ) { WidenMode newWM( *this ); newWM &= other; return newWM; }
39 operator bool() { return widenFirst && widenSecond; }
[41a2620]40
[a32b204]41 bool widenFirst : 1, widenSecond : 1;
42 };
[51b73452]43
[a32b204]44 class Unify : public Visitor {
45 public:
46 Unify( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
[41a2620]47
[a32b204]48 bool get_result() const { return result; }
49 private:
50 virtual void visit(VoidType *voidType);
51 virtual void visit(BasicType *basicType);
52 virtual void visit(PointerType *pointerType);
53 virtual void visit(ArrayType *arrayType);
54 virtual void visit(FunctionType *functionType);
55 virtual void visit(StructInstType *aggregateUseType);
56 virtual void visit(UnionInstType *aggregateUseType);
57 virtual void visit(EnumInstType *aggregateUseType);
[4040425]58 virtual void visit(TraitInstType *aggregateUseType);
[a32b204]59 virtual void visit(TypeInstType *aggregateUseType);
60 virtual void visit(TupleType *tupleType);
[44b7088]61 virtual void visit(VarArgsType *varArgsType);
[89e6ffc]62 virtual void visit(ZeroType *zeroType);
63 virtual void visit(OneType *oneType);
[a32b204]64
65 template< typename RefType > void handleRefType( RefType *inst, Type *other );
[02ec390]66 template< typename RefType > void handleGenericRefType( RefType *inst, Type *other );
[a32b204]67
68 bool result;
69 Type *type2; // inherited
70 TypeEnvironment &env;
71 AssertionSet &needAssertions;
72 AssertionSet &haveAssertions;
73 const OpenVarSet &openVars;
74 WidenMode widenMode;
75 const SymTab::Indexer &indexer;
76 };
77
[eb50842]78 /// Attempts an inexact unification of type1 and type2.
79 /// Returns false if no such unification; if the types can be unified, sets common (unless they unify exactly and have identical type qualifiers)
[a32b204]80 bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer, Type *&common );
81 bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
[41a2620]82
[a32b204]83 bool typesCompatible( Type *first, Type *second, const SymTab::Indexer &indexer, const TypeEnvironment &env ) {
84 TypeEnvironment newEnv;
[1cbca6e]85 OpenVarSet openVars, closedVars; // added closedVars
[a32b204]86 AssertionSet needAssertions, haveAssertions;
87 Type *newFirst = first->clone(), *newSecond = second->clone();
88 env.apply( newFirst );
89 env.apply( newSecond );
[1cbca6e]90
91 // do we need to do this? Seems like we do, types should be able to be compatible if they
92 // have free variables that can unify
93 findOpenVars( newFirst, openVars, closedVars, needAssertions, haveAssertions, false );
94 findOpenVars( newSecond, openVars, closedVars, needAssertions, haveAssertions, true );
95
[a32b204]96 bool result = unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
97 delete newFirst;
98 delete newSecond;
99 return result;
100 }
101
102 bool typesCompatibleIgnoreQualifiers( Type *first, Type *second, const SymTab::Indexer &indexer, const TypeEnvironment &env ) {
103 TypeEnvironment newEnv;
104 OpenVarSet openVars;
105 AssertionSet needAssertions, haveAssertions;
106 Type *newFirst = first->clone(), *newSecond = second->clone();
107 env.apply( newFirst );
108 env.apply( newSecond );
109 newFirst->get_qualifiers() = Type::Qualifiers();
110 newSecond->get_qualifiers() = Type::Qualifiers();
[51b73452]111/// std::cout << "first is ";
112/// first->print( std::cout );
113/// std::cout << std::endl << "second is ";
114/// second->print( std::cout );
115/// std::cout << std::endl << "newFirst is ";
116/// newFirst->print( std::cout );
117/// std::cout << std::endl << "newSecond is ";
118/// newSecond->print( std::cout );
119/// std::cout << std::endl;
[a32b204]120 bool result = unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
121 delete newFirst;
122 delete newSecond;
123 return result;
124 }
125
126 bool isFtype( Type *type, const SymTab::Indexer &indexer ) {
127 if ( dynamic_cast< FunctionType* >( type ) ) {
128 return true;
129 } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( type ) ) {
130 return typeInst->get_isFtype();
131 } // if
132 return false;
133 }
134
135 bool tyVarCompatible( TypeDecl::Kind kind, Type *type, const SymTab::Indexer &indexer ) {
136 switch ( kind ) {
137 case TypeDecl::Any:
138 case TypeDecl::Dtype:
139 return ! isFtype( type, indexer );
[41a2620]140
[a32b204]141 case TypeDecl::Ftype:
142 return isFtype( type, indexer );
143 } // switch
144 assert( false );
145 return false;
146 }
147
148 bool bindVar( TypeInstType *typeInst, Type *other, TypeDecl::Kind kind, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
149 OpenVarSet::const_iterator tyvar = openVars.find( typeInst->get_name() );
150 assert( tyvar != openVars.end() );
151 if ( ! tyVarCompatible( tyvar->second, other, indexer ) ) {
152 return false;
153 } // if
154 if ( occurs( other, typeInst->get_name(), env ) ) {
155 return false;
156 } // if
157 EqvClass curClass;
158 if ( env.lookup( typeInst->get_name(), curClass ) ) {
159 if ( curClass.type ) {
160 Type *common = 0;
[eb50842]161 // attempt to unify equivalence class type (which has qualifiers stripped, so they must be restored) with the type to bind to
[a32b204]162 std::auto_ptr< Type > newType( curClass.type->clone() );
[721f17a]163 newType->get_qualifiers() = typeInst->get_qualifiers();
[a32b204]164 if ( unifyInexact( newType.get(), other, env, needAssertions, haveAssertions, openVars, widenMode & WidenMode( curClass.allowWidening, true ), indexer, common ) ) {
165 if ( common ) {
166 common->get_qualifiers() = Type::Qualifiers();
167 delete curClass.type;
168 curClass.type = common;
169 env.add( curClass );
170 } // if
171 return true;
172 } else {
173 return false;
174 } // if
175 } else {
176 curClass.type = other->clone();
177 curClass.type->get_qualifiers() = Type::Qualifiers();
178 curClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond;
179 env.add( curClass );
180 } // if
181 } else {
182 EqvClass newClass;
183 newClass.vars.insert( typeInst->get_name() );
184 newClass.type = other->clone();
185 newClass.type->get_qualifiers() = Type::Qualifiers();
186 newClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond;
187 newClass.kind = kind;
188 env.add( newClass );
189 } // if
190 return true;
191 }
192
193 bool bindVarToVar( TypeInstType *var1, TypeInstType *var2, TypeDecl::Kind kind, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
194 bool result = true;
195 EqvClass class1, class2;
196 bool hasClass1 = false, hasClass2 = false;
197 bool widen1 = false, widen2 = false;
198 Type *type1 = 0, *type2 = 0;
[41a2620]199
[a32b204]200 if ( env.lookup( var1->get_name(), class1 ) ) {
201 hasClass1 = true;
202 if ( class1.type ) {
203 if ( occurs( class1.type, var2->get_name(), env ) ) {
204 return false;
205 } // if
206 type1 = class1.type->clone();
207 } // if
208 widen1 = widenMode.widenFirst && class1.allowWidening;
209 } // if
210 if ( env.lookup( var2->get_name(), class2 ) ) {
211 hasClass2 = true;
212 if ( class2.type ) {
213 if ( occurs( class2.type, var1->get_name(), env ) ) {
214 return false;
215 } // if
216 type2 = class2.type->clone();
217 } // if
218 widen2 = widenMode.widenSecond && class2.allowWidening;
219 } // if
[41a2620]220
[a32b204]221 if ( type1 && type2 ) {
[51b73452]222// std::cout << "has type1 && type2" << std::endl;
[a32b204]223 WidenMode newWidenMode ( widen1, widen2 );
224 Type *common = 0;
225 if ( unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, newWidenMode, indexer, common ) ) {
226 class1.vars.insert( class2.vars.begin(), class2.vars.end() );
227 class1.allowWidening = widen1 && widen2;
228 if ( common ) {
229 common->get_qualifiers() = Type::Qualifiers();
230 delete class1.type;
231 class1.type = common;
232 } // if
233 env.add( class1 );
234 } else {
235 result = false;
236 } // if
237 } else if ( hasClass1 && hasClass2 ) {
238 if ( type1 ) {
239 class1.vars.insert( class2.vars.begin(), class2.vars.end() );
240 class1.allowWidening = widen1;
241 env.add( class1 );
242 } else {
243 class2.vars.insert( class1.vars.begin(), class1.vars.end() );
244 class2.allowWidening = widen2;
245 env.add( class2 );
246 } // if
247 } else if ( hasClass1 ) {
248 class1.vars.insert( var2->get_name() );
249 class1.allowWidening = widen1;
250 env.add( class1 );
251 } else if ( hasClass2 ) {
252 class2.vars.insert( var1->get_name() );
253 class2.allowWidening = widen2;
254 env.add( class2 );
255 } else {
256 EqvClass newClass;
257 newClass.vars.insert( var1->get_name() );
258 newClass.vars.insert( var2->get_name() );
259 newClass.allowWidening = widen1 && widen2;
260 newClass.kind = kind;
261 env.add( newClass );
262 } // if
263 delete type1;
264 delete type2;
265 return result;
266 }
267
268 bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
269 OpenVarSet closedVars;
270 findOpenVars( type1, openVars, closedVars, needAssertions, haveAssertions, false );
271 findOpenVars( type2, openVars, closedVars, needAssertions, haveAssertions, true );
272 Type *commonType = 0;
273 if ( unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType ) ) {
274 if ( commonType ) {
275 delete commonType;
276 } // if
277 return true;
278 } else {
279 return false;
280 } // if
281 }
282
283 bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer, Type *&commonType ) {
284 OpenVarSet closedVars;
285 findOpenVars( type1, openVars, closedVars, needAssertions, haveAssertions, false );
286 findOpenVars( type2, openVars, closedVars, needAssertions, haveAssertions, true );
287 return unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType );
288 }
289
290 bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
[51b73452]291#ifdef DEBUG
[a32b204]292 TypeEnvironment debugEnv( env );
[51b73452]293#endif
[eb50842]294 if ( type1->get_qualifiers() != type2->get_qualifiers() ) {
295 return false;
296 }
297
[a32b204]298 bool result;
299 TypeInstType *var1 = dynamic_cast< TypeInstType* >( type1 );
300 TypeInstType *var2 = dynamic_cast< TypeInstType* >( type2 );
301 OpenVarSet::const_iterator entry1, entry2;
302 if ( var1 ) {
303 entry1 = openVars.find( var1->get_name() );
304 } // if
305 if ( var2 ) {
306 entry2 = openVars.find( var2->get_name() );
307 } // if
308 bool isopen1 = var1 && ( entry1 != openVars.end() );
309 bool isopen2 = var2 && ( entry2 != openVars.end() );
[eb50842]310
311 if ( isopen1 && isopen2 && entry1->second == entry2->second ) {
[a32b204]312 result = bindVarToVar( var1, var2, entry1->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
313 } else if ( isopen1 ) {
314 result = bindVar( var1, type2, entry1->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
315 } else if ( isopen2 ) {
316 result = bindVar( var2, type1, entry2->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
317 } else {
318 Unify comparator( type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
319 type1->accept( comparator );
320 result = comparator.get_result();
321 } // if
[51b73452]322#ifdef DEBUG
[a32b204]323 std::cout << "============ unifyExact" << std::endl;
324 std::cout << "type1 is ";
325 type1->print( std::cout );
326 std::cout << std::endl << "type2 is ";
327 type2->print( std::cout );
328 std::cout << std::endl << "openVars are ";
329 printOpenVarSet( openVars, std::cout, 8 );
330 std::cout << std::endl << "input env is " << std::endl;
331 debugEnv.print( std::cout, 8 );
332 std::cout << std::endl << "result env is " << std::endl;
333 env.print( std::cout, 8 );
334 std::cout << "result is " << result << std::endl;
[51b73452]335#endif
[a32b204]336 return result;
337 }
338
339 bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
340 return unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
341 }
342
343 bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer, Type *&common ) {
344 Type::Qualifiers tq1 = type1->get_qualifiers(), tq2 = type2->get_qualifiers();
345 type1->get_qualifiers() = Type::Qualifiers();
346 type2->get_qualifiers() = Type::Qualifiers();
347 bool result;
[51b73452]348#ifdef DEBUG
[a32b204]349 std::cout << "unifyInexact type 1 is ";
350 type1->print( std::cout );
351 std::cout << "type 2 is ";
352 type2->print( std::cout );
353 std::cout << std::endl;
[51b73452]354#endif
[a32b204]355 if ( ! unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer ) ) {
[51b73452]356#ifdef DEBUG
[a32b204]357 std::cout << "unifyInexact: no exact unification found" << std::endl;
[51b73452]358#endif
[a32b204]359 if ( ( common = commonType( type1, type2, widenMode.widenFirst, widenMode.widenSecond, indexer, env, openVars ) ) ) {
360 common->get_qualifiers() = tq1 + tq2;
[51b73452]361#ifdef DEBUG
[a32b204]362 std::cout << "unifyInexact: common type is ";
363 common->print( std::cout );
364 std::cout << std::endl;
[51b73452]365#endif
[a32b204]366 result = true;
367 } else {
[51b73452]368#ifdef DEBUG
[a32b204]369 std::cout << "unifyInexact: no common type found" << std::endl;
[51b73452]370#endif
[a32b204]371 result = false;
372 } // if
373 } else {
374 if ( tq1 != tq2 ) {
375 if ( ( tq1 > tq2 || widenMode.widenFirst ) && ( tq2 > tq1 || widenMode.widenSecond ) ) {
376 common = type1->clone();
377 common->get_qualifiers() = tq1 + tq2;
378 result = true;
379 } else {
380 result = false;
381 } // if
382 } else {
383 result = true;
384 } // if
385 } // if
386 type1->get_qualifiers() = tq1;
387 type2->get_qualifiers() = tq2;
388 return result;
389 }
390
391 Unify::Unify( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer )
392 : result( false ), type2( type2 ), env( env ), needAssertions( needAssertions ), haveAssertions( haveAssertions ), openVars( openVars ), widenMode( widenMode ), indexer( indexer ) {
393 }
394
395 void Unify::visit(VoidType *voidType) {
396 result = dynamic_cast< VoidType* >( type2 );
397 }
398
399 void Unify::visit(BasicType *basicType) {
400 if ( BasicType *otherBasic = dynamic_cast< BasicType* >( type2 ) ) {
401 result = basicType->get_kind() == otherBasic->get_kind();
402 } // if
403 }
404
405 void markAssertionSet( AssertionSet &assertions, DeclarationWithType *assert ) {
[51b73452]406/// std::cout << "assertion set is" << std::endl;
407/// printAssertionSet( assertions, std::cout, 8 );
408/// std::cout << "looking for ";
409/// assert->print( std::cout );
410/// std::cout << std::endl;
[a32b204]411 AssertionSet::iterator i = assertions.find( assert );
412 if ( i != assertions.end() ) {
[51b73452]413/// std::cout << "found it!" << std::endl;
[a32b204]414 i->second = true;
415 } // if
416 }
417
418 void markAssertions( AssertionSet &assertion1, AssertionSet &assertion2, Type *type ) {
[aefcc3b]419 for ( std::list< TypeDecl* >::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
[a32b204]420 for ( std::list< DeclarationWithType* >::const_iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) {
421 markAssertionSet( assertion1, *assert );
422 markAssertionSet( assertion2, *assert );
423 } // for
424 } // for
425 }
426
427 void Unify::visit(PointerType *pointerType) {
428 if ( PointerType *otherPointer = dynamic_cast< PointerType* >( type2 ) ) {
429 result = unifyExact( pointerType->get_base(), otherPointer->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
430 markAssertions( haveAssertions, needAssertions, pointerType );
431 markAssertions( haveAssertions, needAssertions, otherPointer );
432 } // if
433 }
434
435 void Unify::visit(ArrayType *arrayType) {
436 ArrayType *otherArray = dynamic_cast< ArrayType* >( type2 );
[1cbca6e]437 // to unify, array types must both be VLA or both not VLA
438 // and must both have a dimension expression or not have a dimension
[41a2620]439 if ( otherArray && arrayType->get_isVarLen() == otherArray->get_isVarLen() ) {
[1cbca6e]440
441 // not positive this is correct in all cases, but it's needed for typedefs
442 if ( arrayType->get_isVarLen() || otherArray->get_isVarLen() ) {
443 return;
444 }
445
446 if ( ! arrayType->get_isVarLen() && ! otherArray->get_isVarLen() &&
447 arrayType->get_dimension() != 0 && otherArray->get_dimension() != 0 ) {
448 ConstantExpr * ce1 = dynamic_cast< ConstantExpr * >( arrayType->get_dimension() );
449 ConstantExpr * ce2 = dynamic_cast< ConstantExpr * >( otherArray->get_dimension() );
[41a2620]450 // see C11 Reference Manual 6.7.6.2.6
451 // two array types with size specifiers that are integer constant expressions are
452 // compatible if both size specifiers have the same constant value
453 if ( ce1 && ce2 ) {
454 Constant * c1 = ce1->get_constant();
455 Constant * c2 = ce2->get_constant();
456
457 if ( c1->get_value() != c2->get_value() ) {
458 // does not unify if the dimension is different
459 return;
460 }
[1cbca6e]461 }
462 }
463
[a32b204]464 result = unifyExact( arrayType->get_base(), otherArray->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
465 } // if
466 }
467
468 template< typename Iterator1, typename Iterator2 >
469 bool unifyDeclList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
470 for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) {
[1cbca6e]471 // Type * commonType;
472 // if ( ! unifyInexact( (*list1Begin)->get_type(), (*list2Begin)->get_type(), env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType ) ) {
[a32b204]473 if ( ! unifyExact( (*list1Begin)->get_type(), (*list2Begin)->get_type(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ) ) {
474 return false;
475 } // if
476 } // for
477 if ( list1Begin != list1End || list2Begin != list2End ) {
478 return false;
479 } else {
480 return true;
481 } // if
482 }
483
484 void Unify::visit(FunctionType *functionType) {
485 FunctionType *otherFunction = dynamic_cast< FunctionType* >( type2 );
486 if ( otherFunction && functionType->get_isVarArgs() == otherFunction->get_isVarArgs() ) {
[03da511]487 if ( functionType->get_parameters().size() == otherFunction->get_parameters().size() && functionType->get_returnVals().size() == otherFunction->get_returnVals().size() ) {
488 if ( unifyDeclList( functionType->get_parameters().begin(), functionType->get_parameters().end(), otherFunction->get_parameters().begin(), otherFunction->get_parameters().end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
489 if ( unifyDeclList( functionType->get_returnVals().begin(), functionType->get_returnVals().end(), otherFunction->get_returnVals().begin(), otherFunction->get_returnVals().end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
[1cbca6e]490
[03da511]491 markAssertions( haveAssertions, needAssertions, functionType );
492 markAssertions( haveAssertions, needAssertions, otherFunction );
[41a2620]493
[03da511]494 result = true;
495 } // if
[a32b204]496 } // if
497 } // if
498 } // if
499 }
500
501 template< typename RefType >
[02ec390]502 void Unify::handleRefType( RefType *inst, Type *other ) {
503 // check that other type is compatible and named the same
[a32b204]504 RefType *otherStruct = dynamic_cast< RefType* >( other );
505 result = otherStruct && inst->get_name() == otherStruct->get_name();
[02ec390]506 }
507
508 template< typename RefType >
509 void Unify::handleGenericRefType( RefType *inst, Type *other ) {
510 // Check that other type is compatible and named the same
511 handleRefType( inst, other );
512 if ( ! result ) return;
[f5234f3]513 // Check that parameters of types unify, if any
[02ec390]514 std::list< Expression* > params = inst->get_parameters();
[f5234f3]515 std::list< Expression* > otherParams = ((RefType*)other)->get_parameters();
516
517 std::list< Expression* >::const_iterator it = params.begin(), jt = otherParams.begin();
518 for ( ; it != params.end() && jt != otherParams.end(); ++it, ++jt ) {
519 TypeExpr *param = dynamic_cast< TypeExpr* >(*it);
520 assert(param && "Aggregate parameters should be type expressions");
521 TypeExpr *otherParam = dynamic_cast< TypeExpr* >(*jt);
522 assert(otherParam && "Aggregate parameters should be type expressions");
523
524 if ( ! unifyExact( param->get_type(), otherParam->get_type(), env, needAssertions, haveAssertions, openVars, WidenMode(false, false), indexer ) ) {
[02ec390]525 result = false;
526 return;
527 }
528 }
[f5234f3]529 result = ( it == params.end() && jt == otherParams.end() );
[02ec390]530 }
[a32b204]531
532 void Unify::visit(StructInstType *structInst) {
[02ec390]533 handleGenericRefType( structInst, type2 );
[a32b204]534 }
535
536 void Unify::visit(UnionInstType *unionInst) {
[02ec390]537 handleGenericRefType( unionInst, type2 );
[a32b204]538 }
539
540 void Unify::visit(EnumInstType *enumInst) {
541 handleRefType( enumInst, type2 );
542 }
543
[4040425]544 void Unify::visit(TraitInstType *contextInst) {
[a32b204]545 handleRefType( contextInst, type2 );
546 }
547
548 void Unify::visit(TypeInstType *typeInst) {
549 assert( openVars.find( typeInst->get_name() ) == openVars.end() );
550 TypeInstType *otherInst = dynamic_cast< TypeInstType* >( type2 );
551 if ( otherInst && typeInst->get_name() == otherInst->get_name() ) {
552 result = true;
[51b73452]553/// } else {
554/// NamedTypeDecl *nt = indexer.lookupType( typeInst->get_name() );
[a32b204]555/// if ( nt ) {
[51b73452]556/// TypeDecl *type = dynamic_cast< TypeDecl* >( nt );
557/// assert( type );
[a32b204]558/// if ( type->get_base() ) {
[51b73452]559/// result = unifyExact( type->get_base(), typeInst, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
560/// }
561/// }
[a32b204]562 } // if
563 }
564
565 template< typename Iterator1, typename Iterator2 >
566 bool unifyList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
567 for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) {
568 Type *commonType = 0;
569 if ( ! unifyInexact( *list1Begin, *list2Begin, env, needAssertions, haveAssertions, openVars, widenMode, indexer, commonType ) ) {
570 return false;
571 }
572 delete commonType;
573 } // for
574 if ( list1Begin != list1End || list2Begin != list2End ) {
575 return false;
576 } else {
577 return true;
578 } //if
579 }
580
581 void Unify::visit(TupleType *tupleType) {
582 if ( TupleType *otherTuple = dynamic_cast< TupleType* >( type2 ) ) {
583 result = unifyList( tupleType->get_types().begin(), tupleType->get_types().end(), otherTuple->get_types().begin(), otherTuple->get_types().end(), env, needAssertions, haveAssertions, openVars, widenMode, indexer );
584 } // if
585 }
[51b73452]586
[44b7088]587 void Unify::visit(VarArgsType *varArgsType) {
588 result = dynamic_cast< VarArgsType* >( type2 );
589 }
590
[89e6ffc]591 void Unify::visit(ZeroType *zeroType) {
592 result = dynamic_cast< ZeroType* >( type2 );
593 }
594
595 void Unify::visit(OneType *oneType) {
596 result = dynamic_cast< OneType* >( type2 );
597 }
598
[906e24d]599 // xxx - compute once and store in the FunctionType?
600 Type * extractResultType( FunctionType * function ) {
601 if ( function->get_returnVals().size() == 0 ) {
602 return new VoidType( Type::Qualifiers() );
603 } else if ( function->get_returnVals().size() == 1 ) {
604 return function->get_returnVals().front()->get_type()->clone();
605 } else {
606 TupleType * tupleType = new TupleType( Type::Qualifiers() );
607 for ( DeclarationWithType * decl : function->get_returnVals() ) {
608 tupleType->get_types().push_back( decl->get_type()->clone() );
609 } // for
610 return tupleType;
611 }
612 }
[51b73452]613} // namespace ResolvExpr
[a32b204]614
615// Local Variables: //
616// tab-width: 4 //
617// mode: c++ //
618// compile-command: "make install" //
619// End: //
Note: See TracBrowser for help on using the repository browser.