source: translator/ResolvExpr/Unify.cc@ 643a2e1

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors ctor deferred_resn demangler enum forall-pointer-decay gc_noraii jacob/cs343-translation jenkins-sandbox memory new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new string with_gc
Last change on this file since 643a2e1 was 51b73452, checked in by Peter A. Buhr <pabuhr@…>, 11 years ago

initial commit
  • Property mode set to 100644
File size: 19.9 KB
Line 
1/*
2 * This file is part of the Cforall project
3 *
4 * $Id: Unify.cc,v 1.14 2005/08/29 20:14:16 rcbilson Exp $
5 *
6 */
7
8#include <set>
9#include <memory>
10
11#include "Unify.h"
12#include "TypeEnvironment.h"
13#include "typeops.h"
14#include "FindOpenVars.h"
15#include "SynTree/Visitor.h"
16#include "SynTree/Type.h"
17#include "SynTree/Declaration.h"
18#include "SymTab/Indexer.h"
19#include "utility.h"
20
21
22//#define DEBUG
23
24namespace ResolvExpr {
25
26struct WidenMode
27{
28 WidenMode( bool widenFirst, bool widenSecond ): widenFirst( widenFirst ), widenSecond( widenSecond ) {}
29 WidenMode &operator|=( const WidenMode &other ) { widenFirst |= other.widenFirst; widenSecond |= other.widenSecond; return *this; }
30 WidenMode &operator&=( const WidenMode &other ) { widenFirst &= other.widenFirst; widenSecond &= other.widenSecond; return *this; }
31 WidenMode operator|( const WidenMode &other ) { WidenMode newWM( *this ); newWM |= other; return newWM; }
32 WidenMode operator&( const WidenMode &other ) { WidenMode newWM( *this ); newWM &= other; return newWM; }
33 operator bool() { return widenFirst && widenSecond; }
34
35 bool widenFirst : 1, widenSecond : 1;
36};
37
38class Unify : public Visitor
39{
40public:
41 Unify( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
42
43 bool get_result() const { return result; }
44
45private:
46 virtual void visit(VoidType *voidType);
47 virtual void visit(BasicType *basicType);
48 virtual void visit(PointerType *pointerType);
49 virtual void visit(ArrayType *arrayType);
50 virtual void visit(FunctionType *functionType);
51 virtual void visit(StructInstType *aggregateUseType);
52 virtual void visit(UnionInstType *aggregateUseType);
53 virtual void visit(EnumInstType *aggregateUseType);
54 virtual void visit(ContextInstType *aggregateUseType);
55 virtual void visit(TypeInstType *aggregateUseType);
56 virtual void visit(TupleType *tupleType);
57
58 template< typename RefType > void handleRefType( RefType *inst, Type *other );
59
60 bool result;
61 Type *type2; // inherited
62 TypeEnvironment &env;
63 AssertionSet &needAssertions;
64 AssertionSet &haveAssertions;
65 const OpenVarSet &openVars;
66 WidenMode widenMode;
67 Type *commonType;
68 const SymTab::Indexer &indexer;
69};
70
71bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer, Type *&common );
72bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
73
74bool
75typesCompatible( Type *first, Type *second, const SymTab::Indexer &indexer, const TypeEnvironment &env )
76{
77 TypeEnvironment newEnv;
78 OpenVarSet openVars;
79 AssertionSet needAssertions, haveAssertions;
80 Type *newFirst = first->clone(), *newSecond = second->clone();
81 env.apply( newFirst );
82 env.apply( newSecond );
83 bool result = unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
84 delete newFirst;
85 delete newSecond;
86 return result;
87}
88
89bool
90typesCompatibleIgnoreQualifiers( Type *first, Type *second, const SymTab::Indexer &indexer, const TypeEnvironment &env )
91{
92 TypeEnvironment newEnv;
93 OpenVarSet openVars;
94 AssertionSet needAssertions, haveAssertions;
95 Type *newFirst = first->clone(), *newSecond = second->clone();
96 env.apply( newFirst );
97 env.apply( newSecond );
98 newFirst->get_qualifiers() = Type::Qualifiers();
99 newSecond->get_qualifiers() = Type::Qualifiers();
100/// std::cout << "first is ";
101/// first->print( std::cout );
102/// std::cout << std::endl << "second is ";
103/// second->print( std::cout );
104/// std::cout << std::endl << "newFirst is ";
105/// newFirst->print( std::cout );
106/// std::cout << std::endl << "newSecond is ";
107/// newSecond->print( std::cout );
108/// std::cout << std::endl;
109 bool result = unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
110 delete newFirst;
111 delete newSecond;
112 return result;
113}
114
115bool
116isFtype( Type *type, const SymTab::Indexer &indexer )
117{
118 if( dynamic_cast< FunctionType* >( type ) ) {
119 return true;
120 } else if( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( type ) ) {
121 return typeInst->get_isFtype();
122 }
123 return false;
124}
125
126bool
127tyVarCompatible( TypeDecl::Kind kind, Type *type, const SymTab::Indexer &indexer )
128{
129 switch( kind ) {
130 case TypeDecl::Any:
131 case TypeDecl::Dtype:
132 return !isFtype( type, indexer );
133
134 case TypeDecl::Ftype:
135 return isFtype( type, indexer );
136 }
137 assert( false );
138 return false;
139}
140
141bool
142bindVar( TypeInstType *typeInst, Type *other, TypeDecl::Kind kind, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer )
143{
144 OpenVarSet::const_iterator tyvar = openVars.find( typeInst->get_name() );
145 assert( tyvar != openVars.end() );
146 if( !tyVarCompatible( tyvar->second, other, indexer ) ) {
147 return false;
148 }
149 if( occurs( other, typeInst->get_name(), env ) ) {
150 return false;
151 }
152 EqvClass curClass;
153 if( env.lookup( typeInst->get_name(), curClass ) ) {
154 if( curClass.type ) {
155 Type *common = 0;
156 std::auto_ptr< Type > newType( curClass.type->clone() );
157 if( unifyInexact( newType.get(), other, env, needAssertions, haveAssertions, openVars, widenMode & WidenMode( curClass.allowWidening, true ), indexer, common ) ) {
158 if( common ) {
159 common->get_qualifiers() = Type::Qualifiers();
160 delete curClass.type;
161 curClass.type = common;
162 env.add( curClass );
163 }
164 return true;
165 } else {
166 return false;
167 }
168 } else {
169 curClass.type = other->clone();
170 curClass.type->get_qualifiers() = Type::Qualifiers();
171 curClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond;
172 env.add( curClass );
173 }
174 } else {
175 EqvClass newClass;
176 newClass.vars.insert( typeInst->get_name() );
177 newClass.type = other->clone();
178 newClass.type->get_qualifiers() = Type::Qualifiers();
179 newClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond;
180 newClass.kind = kind;
181 env.add( newClass );
182 }
183 return true;
184}
185
186bool
187bindVarToVar( TypeInstType *var1, TypeInstType *var2, TypeDecl::Kind kind, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer )
188{
189 bool result = true;
190 EqvClass class1, class2;
191 bool hasClass1 = false, hasClass2 = false;
192 bool widen1 = false, widen2 = false;
193 Type *type1 = 0, *type2 = 0;
194
195 if( env.lookup( var1->get_name(), class1 ) ) {
196 hasClass1 = true;
197 if( class1.type ) {
198 if( occurs( class1.type, var2->get_name(), env ) ) {
199 return false;
200 }
201 type1 = class1.type->clone();
202 }
203 widen1 = widenMode.widenFirst && class1.allowWidening;
204 }
205 if( env.lookup( var2->get_name(), class2 ) ) {
206 hasClass2 = true;
207 if( class2.type ) {
208 if( occurs( class2.type, var1->get_name(), env ) ) {
209 return false;
210 }
211 type2 = class2.type->clone();
212 }
213 widen2 = widenMode.widenSecond && class2.allowWidening;
214 }
215
216 if( type1 && type2 ) {
217// std::cout << "has type1 && type2" << std::endl;
218 WidenMode newWidenMode ( widen1, widen2 );
219 Type *common = 0;
220 if( unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, newWidenMode, indexer, common ) ) {
221 class1.vars.insert( class2.vars.begin(), class2.vars.end() );
222 class1.allowWidening = widen1 && widen2;
223 if( common ) {
224 common->get_qualifiers() = Type::Qualifiers();
225 delete class1.type;
226 class1.type = common;
227 }
228 env.add( class1 );
229 } else {
230 result = false;
231 }
232 } else if( hasClass1 && hasClass2 ) {
233 if( type1 ) {
234 class1.vars.insert( class2.vars.begin(), class2.vars.end() );
235 class1.allowWidening = widen1;
236 env.add( class1 );
237 } else {
238 class2.vars.insert( class1.vars.begin(), class1.vars.end() );
239 class2.allowWidening = widen2;
240 env.add( class2 );
241 }
242 } else if( hasClass1 ) {
243 class1.vars.insert( var2->get_name() );
244 class1.allowWidening = widen1;
245 env.add( class1 );
246 } else if( hasClass2 ) {
247 class2.vars.insert( var1->get_name() );
248 class2.allowWidening = widen2;
249 env.add( class2 );
250 } else {
251 EqvClass newClass;
252 newClass.vars.insert( var1->get_name() );
253 newClass.vars.insert( var2->get_name() );
254 newClass.allowWidening = widen1 && widen2;
255 newClass.kind = kind;
256 env.add( newClass );
257 }
258 delete type1;
259 delete type2;
260 return result;
261}
262
263bool
264unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer )
265{
266 OpenVarSet closedVars;
267 findOpenVars( type1, openVars, closedVars, needAssertions, haveAssertions, false );
268 findOpenVars( type2, openVars, closedVars, needAssertions, haveAssertions, true );
269 Type *commonType = 0;
270 if( unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType ) ) {
271 if( commonType ) {
272 delete commonType;
273 }
274 return true;
275 } else {
276 return false;
277 }
278}
279
280bool
281unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer, Type *&commonType )
282{
283 OpenVarSet closedVars;
284 findOpenVars( type1, openVars, closedVars, needAssertions, haveAssertions, false );
285 findOpenVars( type2, openVars, closedVars, needAssertions, haveAssertions, true );
286 return unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType );
287}
288
289bool
290unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer )
291{
292#ifdef DEBUG
293 TypeEnvironment debugEnv( env );
294#endif
295 bool result;
296 TypeInstType *var1 = dynamic_cast< TypeInstType* >( type1 );
297 TypeInstType *var2 = dynamic_cast< TypeInstType* >( type2 );
298 OpenVarSet::const_iterator entry1, entry2;
299 if( var1 ) {
300 entry1 = openVars.find( var1->get_name() );
301 }
302 if( var2 ) {
303 entry2 = openVars.find( var2->get_name() );
304 }
305 bool isopen1 = var1 && ( entry1 != openVars.end() );
306 bool isopen2 = var2 && ( entry2 != openVars.end() );
307 if( type1->get_qualifiers() != type2->get_qualifiers() ) {
308 return false;
309 } else if( isopen1 && isopen2 && entry1->second == entry2->second ) {
310 result = bindVarToVar( var1, var2, entry1->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
311 } else if( isopen1 ) {
312 result = bindVar( var1, type2, entry1->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
313 } else if( isopen2 ) {
314 result = bindVar( var2, type1, entry2->second, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
315 } else {
316 Unify comparator( type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
317 type1->accept( comparator );
318 result = comparator.get_result();
319 }
320#ifdef DEBUG
321 std::cout << "============ unifyExact" << std::endl;
322 std::cout << "type1 is ";
323 type1->print( std::cout );
324 std::cout << std::endl << "type2 is ";
325 type2->print( std::cout );
326 std::cout << std::endl << "openVars are ";
327 printOpenVarSet( openVars, std::cout, 8 );
328 std::cout << std::endl << "input env is " << std::endl;
329 debugEnv.print( std::cout, 8 );
330 std::cout << std::endl << "result env is " << std::endl;
331 env.print( std::cout, 8 );
332 std::cout << "result is " << result << std::endl;
333#endif
334 return result;
335}
336
337bool
338unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer )
339{
340 return unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
341}
342
343bool
344unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer, Type *&common )
345{
346 Type::Qualifiers tq1 = type1->get_qualifiers(), tq2 = type2->get_qualifiers();
347 type1->get_qualifiers() = Type::Qualifiers();
348 type2->get_qualifiers() = Type::Qualifiers();
349 bool result;
350#ifdef DEBUG
351 std::cout << "unifyInexact type 1 is ";
352 type1->print( std::cout );
353 std::cout << "type 2 is ";
354 type2->print( std::cout );
355 std::cout << std::endl;
356#endif
357 if( !unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer ) ) {
358#ifdef DEBUG
359 std::cout << "unifyInexact: no exact unification found" << std::endl;
360#endif
361 if( ( common = commonType( type1, type2, widenMode.widenFirst, widenMode.widenSecond, indexer, env, openVars ) ) ) {
362 common->get_qualifiers() = tq1 + tq2;
363#ifdef DEBUG
364 std::cout << "unifyInexact: common type is ";
365 common->print( std::cout );
366 std::cout << std::endl;
367#endif
368 result = true;
369 } else {
370#ifdef DEBUG
371 std::cout << "unifyInexact: no common type found" << std::endl;
372#endif
373 result = false;
374 }
375 } else {
376 if( tq1 != tq2 ) {
377 if( ( tq1 > tq2 || widenMode.widenFirst ) && ( tq2 > tq1 || widenMode.widenSecond ) ) {
378 common = type1->clone();
379 common->get_qualifiers() = tq1 + tq2;
380 result = true;
381 } else {
382 result = false;
383 }
384 } else {
385 result = true;
386 }
387 }
388 type1->get_qualifiers() = tq1;
389 type2->get_qualifiers() = tq2;
390 return result;
391}
392
393Unify::Unify( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer )
394 : result( false ), type2( type2 ), env( env ), needAssertions( needAssertions ), haveAssertions( haveAssertions ), openVars( openVars ), widenMode( widenMode ), indexer( indexer )
395{
396}
397
398void
399Unify::visit(VoidType *voidType)
400{
401 result = dynamic_cast< VoidType* >( type2 );
402}
403
404void
405Unify::visit(BasicType *basicType)
406{
407 if( BasicType *otherBasic = dynamic_cast< BasicType* >( type2 ) ) {
408 result = basicType->get_kind() == otherBasic->get_kind();
409 }
410}
411
412void
413markAssertionSet( AssertionSet &assertions, DeclarationWithType *assert )
414{
415/// std::cout << "assertion set is" << std::endl;
416/// printAssertionSet( assertions, std::cout, 8 );
417/// std::cout << "looking for ";
418/// assert->print( std::cout );
419/// std::cout << std::endl;
420 AssertionSet::iterator i = assertions.find( assert );
421 if( i != assertions.end() ) {
422/// std::cout << "found it!" << std::endl;
423 i->second = true;
424 }
425}
426
427void
428markAssertions( AssertionSet &assertion1, AssertionSet &assertion2, Type *type )
429{
430 for( std::list< TypeDecl* >::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
431 for( std::list< DeclarationWithType* >::const_iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) {
432 markAssertionSet( assertion1, *assert );
433 markAssertionSet( assertion2, *assert );
434 }
435 }
436}
437
438void
439Unify::visit(PointerType *pointerType)
440{
441 if( PointerType *otherPointer = dynamic_cast< PointerType* >( type2 ) ) {
442 result = unifyExact( pointerType->get_base(), otherPointer->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
443 markAssertions( haveAssertions, needAssertions, pointerType );
444 markAssertions( haveAssertions, needAssertions, otherPointer );
445 }
446}
447
448void
449Unify::visit(ArrayType *arrayType)
450{
451 // XXX -- compare array dimension
452 ArrayType *otherArray = dynamic_cast< ArrayType* >( type2 );
453 if( otherArray && arrayType->get_isVarLen() == otherArray->get_isVarLen() ) {
454 result = unifyExact( arrayType->get_base(), otherArray->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
455 }
456}
457
458template< typename Iterator1, typename Iterator2 >
459bool
460unifyDeclList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
461 for( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) {
462 if( !unifyExact( (*list1Begin)->get_type(), (*list2Begin)->get_type(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ) ) {
463 return false;
464 }
465 }
466 if( list1Begin != list1End || list2Begin != list2End ) {
467 return false;
468 } else {
469 return true;
470 }
471}
472
473void
474Unify::visit(FunctionType *functionType)
475{
476 FunctionType *otherFunction = dynamic_cast< FunctionType* >( type2 );
477 if( otherFunction && functionType->get_isVarArgs() == otherFunction->get_isVarArgs() ) {
478
479 if( unifyDeclList( functionType->get_parameters().begin(), functionType->get_parameters().end(), otherFunction->get_parameters().begin(), otherFunction->get_parameters().end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
480
481 if( unifyDeclList( functionType->get_returnVals().begin(), functionType->get_returnVals().end(), otherFunction->get_returnVals().begin(), otherFunction->get_returnVals().end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
482
483 markAssertions( haveAssertions, needAssertions, functionType );
484 markAssertions( haveAssertions, needAssertions, otherFunction );
485
486 result = true;
487 }
488 }
489 }
490}
491
492template< typename RefType >
493void
494Unify::handleRefType( RefType *inst, Type *other )
495{
496 RefType *otherStruct = dynamic_cast< RefType* >( other );
497 result = otherStruct && inst->get_name() == otherStruct->get_name();
498}
499
500void
501Unify::visit(StructInstType *structInst)
502{
503 handleRefType( structInst, type2 );
504}
505
506void
507Unify::visit(UnionInstType *unionInst)
508{
509 handleRefType( unionInst, type2 );
510}
511
512void
513Unify::visit(EnumInstType *enumInst)
514{
515 handleRefType( enumInst, type2 );
516}
517
518void
519Unify::visit(ContextInstType *contextInst)
520{
521 handleRefType( contextInst, type2 );
522}
523
524void
525Unify::visit(TypeInstType *typeInst)
526{
527 assert( openVars.find( typeInst->get_name() ) == openVars.end() );
528 TypeInstType *otherInst = dynamic_cast< TypeInstType* >( type2 );
529 if( otherInst && typeInst->get_name() == otherInst->get_name() ) {
530 result = true;
531/// } else {
532/// NamedTypeDecl *nt = indexer.lookupType( typeInst->get_name() );
533/// if( nt ) {
534/// TypeDecl *type = dynamic_cast< TypeDecl* >( nt );
535/// assert( type );
536/// if( type->get_base() ) {
537/// result = unifyExact( type->get_base(), typeInst, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
538/// }
539/// }
540 }
541}
542
543template< typename Iterator1, typename Iterator2 >
544bool
545unifyList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
546 for( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) {
547 Type *commonType = 0;
548 if( !unifyInexact( *list1Begin, *list2Begin, env, needAssertions, haveAssertions, openVars, widenMode, indexer, commonType ) ) {
549 return false;
550 }
551 delete commonType;
552 }
553 if( list1Begin != list1End || list2Begin != list2End ) {
554 return false;
555 } else {
556 return true;
557 }
558}
559
560void
561Unify::visit(TupleType *tupleType)
562{
563 if( TupleType *otherTuple = dynamic_cast< TupleType* >( type2 ) ) {
564 result = unifyList( tupleType->get_types().begin(), tupleType->get_types().end(), otherTuple->get_types().begin(), otherTuple->get_types().end(), env, needAssertions, haveAssertions, openVars, widenMode, indexer );
565 }
566}
567
568} // namespace ResolvExpr
Note: See TracBrowser for help on using the repository browser.