source: src/ResolvExpr/Unify.cc @ 53e3b4a

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since 53e3b4a was 53e3b4a, checked in by Rob Schluntz <rschlunt@…>, 8 years ago

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