source: src/ResolvExpr/Unify.cc @ 8a25be9

ADTarm-ehast-experimentalcleanup-dtorsenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 8a25be9 was d286cf68, checked in by Aaron Moss <a3moss@…>, 6 years ago

Fix TypeEnvironment? bind algorithms
  • Property mode set to 100644
File size: 28.2 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 : Aaron B. Moss
12// Last Modified On : Mon Jun 18 11:58:00 2018
13// Update Count     : 43
14//
15
16#include <cassert>                // for assertf, assert
17#include <iterator>               // for back_insert_iterator, back_inserter
18#include <map>                    // for _Rb_tree_const_iterator, _Rb_tree_i...
19#include <memory>                 // for unique_ptr
20#include <set>                    // for set
21#include <string>                 // for string, operator==, operator!=, bas...
22#include <utility>                // for pair, move
23
24#include "Common/PassVisitor.h"   // for PassVisitor
25#include "FindOpenVars.h"         // for findOpenVars
26#include "Parser/LinkageSpec.h"   // for C
27#include "SynTree/Constant.h"     // for Constant
28#include "SynTree/Declaration.h"  // for TypeDecl, TypeDecl::Data, Declarati...
29#include "SynTree/Expression.h"   // for TypeExpr, Expression, ConstantExpr
30#include "SynTree/Mutator.h"      // for Mutator
31#include "SynTree/Type.h"         // for Type, TypeInstType, FunctionType
32#include "SynTree/Visitor.h"      // for Visitor
33#include "Tuples/Tuples.h"        // for isTtype
34#include "TypeEnvironment.h"      // for EqvClass, AssertionSet, OpenVarSet
35#include "Unify.h"
36#include "typeops.h"              // for flatten, occurs, commonType
37
38namespace SymTab {
39class Indexer;
40}  // namespace SymTab
41
42// #define DEBUG
43
44namespace ResolvExpr {
45
46        struct Unify : public WithShortCircuiting {
47                Unify( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
48
49                bool get_result() const { return result; }
50
51                void previsit( BaseSyntaxNode * ) { visit_children = false; }
52
53                void postvisit( VoidType * voidType );
54                void postvisit( BasicType * basicType );
55                void postvisit( PointerType * pointerType );
56                void postvisit( ArrayType * arrayType );
57                void postvisit( ReferenceType * refType );
58                void postvisit( FunctionType * functionType );
59                void postvisit( StructInstType * aggregateUseType );
60                void postvisit( UnionInstType * aggregateUseType );
61                void postvisit( EnumInstType * aggregateUseType );
62                void postvisit( TraitInstType * aggregateUseType );
63                void postvisit( TypeInstType * aggregateUseType );
64                void postvisit( TupleType * tupleType );
65                void postvisit( VarArgsType * varArgsType );
66                void postvisit( ZeroType * zeroType );
67                void postvisit( OneType * oneType );
68
69          private:
70                template< typename RefType > void handleRefType( RefType *inst, Type *other );
71                template< typename RefType > void handleGenericRefType( RefType *inst, Type *other );
72
73                bool result;
74                Type *type2;                            // inherited
75                TypeEnvironment &env;
76                AssertionSet &needAssertions;
77                AssertionSet &haveAssertions;
78                const OpenVarSet &openVars;
79                WidenMode widenMode;
80                const SymTab::Indexer &indexer;
81        };
82
83        /// Attempts an inexact unification of type1 and type2.
84        /// Returns false if no such unification; if the types can be unified, sets common (unless they unify exactly and have identical type qualifiers)
85        bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer, Type *&common );
86        bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
87
88        bool typesCompatible( Type *first, Type *second, const SymTab::Indexer &indexer, const TypeEnvironment &env ) {
89                TypeEnvironment newEnv;
90                OpenVarSet openVars, closedVars; // added closedVars
91                AssertionSet needAssertions, haveAssertions;
92                Type *newFirst = first->clone(), *newSecond = second->clone();
93                env.apply( newFirst );
94                env.apply( newSecond );
95
96                // do we need to do this? Seems like we do, types should be able to be compatible if they
97                // have free variables that can unify
98                findOpenVars( newFirst, openVars, closedVars, needAssertions, haveAssertions, false );
99                findOpenVars( newSecond, openVars, closedVars, needAssertions, haveAssertions, true );
100
101                bool result = unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
102                delete newFirst;
103                delete newSecond;
104                return result;
105        }
106
107        bool typesCompatibleIgnoreQualifiers( Type *first, Type *second, const SymTab::Indexer &indexer, const TypeEnvironment &env ) {
108                TypeEnvironment newEnv;
109                OpenVarSet openVars;
110                AssertionSet needAssertions, haveAssertions;
111                Type *newFirst = first->clone(), *newSecond = second->clone();
112                env.apply( newFirst );
113                env.apply( newSecond );
114                newFirst->get_qualifiers() = Type::Qualifiers();
115                newSecond->get_qualifiers() = Type::Qualifiers();
116///   std::cerr << "first is ";
117///   first->print( std::cerr );
118///   std::cerr << std::endl << "second is ";
119///   second->print( std::cerr );
120///   std::cerr << std::endl << "newFirst is ";
121///   newFirst->print( std::cerr );
122///   std::cerr << std::endl << "newSecond is ";
123///   newSecond->print( std::cerr );
124///   std::cerr << std::endl;
125                bool result = unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
126                delete newFirst;
127                delete newSecond;
128                return result;
129        }
130
131        bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
132                OpenVarSet closedVars;
133                findOpenVars( type1, openVars, closedVars, needAssertions, haveAssertions, false );
134                findOpenVars( type2, openVars, closedVars, needAssertions, haveAssertions, true );
135                Type *commonType = 0;
136                if ( unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType ) ) {
137                        if ( commonType ) {
138                                delete commonType;
139                        } // if
140                        return true;
141                } else {
142                        return false;
143                } // if
144        }
145
146        bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer, Type *&commonType ) {
147                OpenVarSet closedVars;
148                findOpenVars( type1, openVars, closedVars, needAssertions, haveAssertions, false );
149                findOpenVars( type2, openVars, closedVars, needAssertions, haveAssertions, true );
150                return unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType );
151        }
152
153        bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) {
154#ifdef DEBUG
155                TypeEnvironment debugEnv( env );
156#endif
157                if ( type1->get_qualifiers() != type2->get_qualifiers() ) {
158                        return false;
159                }
160
161                bool result;
162                TypeInstType *var1 = dynamic_cast< TypeInstType* >( type1 );
163                TypeInstType *var2 = dynamic_cast< TypeInstType* >( type2 );
164                OpenVarSet::const_iterator entry1, entry2;
165                if ( var1 ) {
166                        entry1 = openVars.find( var1->get_name() );
167                } // if
168                if ( var2 ) {
169                        entry2 = openVars.find( var2->get_name() );
170                } // if
171                bool isopen1 = var1 && ( entry1 != openVars.end() );
172                bool isopen2 = var2 && ( entry2 != openVars.end() );
173
174                if ( isopen1 && isopen2 && entry1->second == entry2->second ) {
175                        result = env.bindVarToVar( var1, var2, entry1->second, needAssertions, haveAssertions, openVars, widenMode, indexer );
176                } else if ( isopen1 ) {
177                        result = env.bindVar( var1, type2, entry1->second, needAssertions, haveAssertions, openVars, widenMode, indexer );
178                } else if ( isopen2 ) { // TODO: swap widenMode values in call, since type positions are flipped?
179                        result = env.bindVar( var2, type1, entry2->second, needAssertions, haveAssertions, openVars, widenMode, indexer );
180                } else {
181                        PassVisitor<Unify> comparator( type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer );
182                        type1->accept( comparator );
183                        result = comparator.pass.get_result();
184                } // if
185#ifdef DEBUG
186                std::cerr << "============ unifyExact" << std::endl;
187                std::cerr << "type1 is ";
188                type1->print( std::cerr );
189                std::cerr << std::endl << "type2 is ";
190                type2->print( std::cerr );
191                std::cerr << std::endl << "openVars are ";
192                printOpenVarSet( openVars, std::cerr, 8 );
193                std::cerr << std::endl << "input env is " << std::endl;
194                debugEnv.print( std::cerr, 8 );
195                std::cerr << std::endl << "result env is " << std::endl;
196                env.print( std::cerr, 8 );
197                std::cerr << "result is " << result << std::endl;
198#endif
199                return result;
200        }
201
202        bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
203                return unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
204        }
205
206        bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer, Type *&common ) {
207                Type::Qualifiers tq1 = type1->get_qualifiers(), tq2 = type2->get_qualifiers();
208                type1->get_qualifiers() = Type::Qualifiers();
209                type2->get_qualifiers() = Type::Qualifiers();
210                bool result;
211#ifdef DEBUG
212                std::cerr << "unifyInexact type 1 is ";
213                type1->print( std::cerr );
214                std::cerr << " type 2 is ";
215                type2->print( std::cerr );
216                std::cerr << std::endl;
217#endif
218                if ( ! unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer ) ) {
219#ifdef DEBUG
220                        std::cerr << "unifyInexact: no exact unification found" << std::endl;
221#endif
222                        if ( ( common = commonType( type1, type2, widenMode.widenFirst, widenMode.widenSecond, indexer, env, openVars ) ) ) {
223                                common->get_qualifiers() = tq1 | tq2;
224#ifdef DEBUG
225                                std::cerr << "unifyInexact: common type is ";
226                                common->print( std::cerr );
227                                std::cerr << std::endl;
228#endif
229                                result = true;
230                        } else {
231#ifdef DEBUG
232                                std::cerr << "unifyInexact: no common type found" << std::endl;
233#endif
234                                result = false;
235                        } // if
236                } else {
237                        if ( tq1 != tq2 ) {
238                                if ( ( tq1 > tq2 || widenMode.widenFirst ) && ( tq2 > tq1 || widenMode.widenSecond ) ) {
239                                        common = type1->clone();
240                                        common->get_qualifiers() = tq1 | tq2;
241                                        result = true;
242                                } else {
243                                        result = false;
244                                } // if
245                        } else {
246                                common = type1->clone();
247                                common->get_qualifiers() = tq1 | tq2;
248                                result = true;
249                        } // if
250                } // if
251                type1->get_qualifiers() = tq1;
252                type2->get_qualifiers() = tq2;
253                return result;
254        }
255
256        Unify::Unify( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer )
257                : result( false ), type2( type2 ), env( env ), needAssertions( needAssertions ), haveAssertions( haveAssertions ), openVars( openVars ), widenMode( widenMode ), indexer( indexer ) {
258        }
259
260        void Unify::postvisit( __attribute__((unused)) VoidType *voidType) {
261                result = dynamic_cast< VoidType* >( type2 );
262        }
263
264        void Unify::postvisit(BasicType *basicType) {
265                if ( BasicType *otherBasic = dynamic_cast< BasicType* >( type2 ) ) {
266                        result = basicType->get_kind() == otherBasic->get_kind();
267                } // if
268        }
269
270        void markAssertionSet( AssertionSet &assertions, DeclarationWithType *assert ) {
271///   std::cerr << "assertion set is" << std::endl;
272///   printAssertionSet( assertions, std::cerr, 8 );
273///   std::cerr << "looking for ";
274///   assert->print( std::cerr );
275///   std::cerr << std::endl;
276                AssertionSet::iterator i = assertions.find( assert );
277                if ( i != assertions.end() ) {
278///     std::cerr << "found it!" << std::endl;
279                        i->second.isUsed = true;
280                } // if
281        }
282
283        void markAssertions( AssertionSet &assertion1, AssertionSet &assertion2, Type *type ) {
284                for ( std::list< TypeDecl* >::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
285                        for ( std::list< DeclarationWithType* >::const_iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) {
286                                markAssertionSet( assertion1, *assert );
287                                markAssertionSet( assertion2, *assert );
288                        } // for
289                } // for
290        }
291
292        void Unify::postvisit(PointerType *pointerType) {
293                if ( PointerType *otherPointer = dynamic_cast< PointerType* >( type2 ) ) {
294                        result = unifyExact( pointerType->get_base(), otherPointer->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
295                        markAssertions( haveAssertions, needAssertions, pointerType );
296                        markAssertions( haveAssertions, needAssertions, otherPointer );
297                } // if
298        }
299
300        void Unify::postvisit(ReferenceType *refType) {
301                if ( ReferenceType *otherRef = dynamic_cast< ReferenceType* >( type2 ) ) {
302                        result = unifyExact( refType->get_base(), otherRef->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
303                        markAssertions( haveAssertions, needAssertions, refType );
304                        markAssertions( haveAssertions, needAssertions, otherRef );
305                } // if
306        }
307
308        void Unify::postvisit(ArrayType *arrayType) {
309                ArrayType *otherArray = dynamic_cast< ArrayType* >( type2 );
310                // to unify, array types must both be VLA or both not VLA
311                // and must both have a dimension expression or not have a dimension
312                if ( otherArray && arrayType->get_isVarLen() == otherArray->get_isVarLen() ) {
313
314                        if ( ! arrayType->get_isVarLen() && ! otherArray->get_isVarLen() &&
315                                arrayType->get_dimension() != 0 && otherArray->get_dimension() != 0 ) {
316                                ConstantExpr * ce1 = dynamic_cast< ConstantExpr * >( arrayType->get_dimension() );
317                                ConstantExpr * ce2 = dynamic_cast< ConstantExpr * >( otherArray->get_dimension() );
318                                // see C11 Reference Manual 6.7.6.2.6
319                                // two array types with size specifiers that are integer constant expressions are
320                                // compatible if both size specifiers have the same constant value
321                                if ( ce1 && ce2 ) {
322                                        Constant * c1 = ce1->get_constant();
323                                        Constant * c2 = ce2->get_constant();
324
325                                        if ( c1->get_value() != c2->get_value() ) {
326                                                // does not unify if the dimension is different
327                                                return;
328                                        }
329                                }
330                        }
331
332                        result = unifyExact( arrayType->get_base(), otherArray->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
333                } // if
334        }
335
336        template< typename Iterator, typename Func >
337        std::unique_ptr<Type> combineTypes( Iterator begin, Iterator end, Func & toType ) {
338                std::list< Type * > types;
339                for ( ; begin != end; ++begin ) {
340                        // it's guaranteed that a ttype variable will be bound to a flat tuple, so ensure that this results in a flat tuple
341                        flatten( toType( *begin ), back_inserter( types ) );
342                }
343                return std::unique_ptr<Type>( new TupleType( Type::Qualifiers(), types ) );
344        }
345
346        template< typename Iterator1, typename Iterator2 >
347        bool unifyDeclList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
348                auto get_type = [](DeclarationWithType * dwt){ return dwt->get_type(); };
349                for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) {
350                        Type * t1 = (*list1Begin)->get_type();
351                        Type * t2 = (*list2Begin)->get_type();
352                        bool isTtype1 = Tuples::isTtype( t1 );
353                        bool isTtype2 = Tuples::isTtype( t2 );
354                        // xxx - assumes ttype must be last parameter
355                        // xxx - there may be a nice way to refactor this, but be careful because the argument positioning might matter in some cases.
356                        if ( isTtype1 && ! isTtype2 ) {
357                                // combine all of the things in list2, then unify
358                                return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
359                        } else if ( isTtype2 && ! isTtype1 ) {
360                                // combine all of the things in list1, then unify
361                                return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
362                        } else if ( ! unifyExact( t1, t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ) ) {
363                                return false;
364                        } // if
365                } // for
366                // 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
367                if ( list1Begin != list1End ) {
368                        // try unifying empty tuple type with ttype
369                        Type * t1 = (*list1Begin)->get_type();
370                        if ( Tuples::isTtype( t1 ) ) {
371                                return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
372                        } else return false;
373                } else if ( list2Begin != list2End ) {
374                        // try unifying empty tuple type with ttype
375                        Type * t2 = (*list2Begin)->get_type();
376                        if ( Tuples::isTtype( t2 ) ) {
377                                return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
378                        } else return false;
379                } else {
380                        return true;
381                } // if
382        }
383
384        /// Finds ttypes and replaces them with their expansion, if known.
385        /// This needs to be done so that satisfying ttype assertions is easier.
386        /// If this isn't done then argument lists can have wildly different
387        /// size and structure, when they should be compatible.
388        struct TtypeExpander : public WithShortCircuiting {
389                TypeEnvironment & tenv;
390                TtypeExpander( TypeEnvironment & tenv ) : tenv( tenv ) {}
391                void premutate( TypeInstType * ) { visit_children = false; }
392                Type * postmutate( TypeInstType * typeInst ) {
393                        if ( const EqvClass *eqvClass = tenv.lookup( typeInst->get_name() ) ) {
394                                // expand ttype parameter into its actual type
395                                if ( eqvClass->data.kind == TypeDecl::Ttype && eqvClass->type ) {
396                                        delete typeInst;
397                                        return eqvClass->type->clone();
398                                }
399                        }
400                        return typeInst;
401                }
402        };
403
404        /// flattens a list of declarations, so that each tuple type has a single declaration.
405        /// makes use of TtypeExpander to ensure ttypes are flat as well.
406        void flattenList( std::list< DeclarationWithType * > src, std::list< DeclarationWithType * > & dst, TypeEnvironment & env ) {
407                dst.clear();
408                for ( DeclarationWithType * dcl : src ) {
409                        PassVisitor<TtypeExpander> expander( env );
410                        dcl->acceptMutator( expander );
411                        std::list< Type * > types;
412                        flatten( dcl->get_type(), back_inserter( types ) );
413                        for ( Type * t : types ) {
414                                // 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.
415                                // 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.
416                                t->get_qualifiers() -= Type::Qualifiers(Type::Const | Type::Volatile | Type::Atomic);
417
418                                dst.push_back( new ObjectDecl( "", Type::StorageClasses(), LinkageSpec::C, nullptr, t, nullptr ) );
419                        }
420                        delete dcl;
421                }
422        }
423
424        void Unify::postvisit(FunctionType *functionType) {
425                FunctionType *otherFunction = dynamic_cast< FunctionType* >( type2 );
426                if ( otherFunction && functionType->get_isVarArgs() == otherFunction->get_isVarArgs() ) {
427                        // flatten the parameter lists for both functions so that tuple structure
428                        // doesn't affect unification. Must be a clone so that the types don't change.
429                        std::unique_ptr<FunctionType> flatFunc( functionType->clone() );
430                        std::unique_ptr<FunctionType> flatOther( otherFunction->clone() );
431                        flattenList( flatFunc->get_parameters(), flatFunc->get_parameters(), env );
432                        flattenList( flatOther->get_parameters(), flatOther->get_parameters(), env );
433
434                        // sizes don't have to match if ttypes are involved; need to be more precise wrt where the ttype is to prevent errors
435                        if ( (flatFunc->parameters.size() == flatOther->parameters.size() && flatFunc->returnVals.size() == flatOther->returnVals.size()) || flatFunc->isTtype() || flatOther->isTtype() ) {
436                                if ( unifyDeclList( flatFunc->parameters.begin(), flatFunc->parameters.end(), flatOther->parameters.begin(), flatOther->parameters.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
437                                        if ( unifyDeclList( flatFunc->returnVals.begin(), flatFunc->returnVals.end(), flatOther->returnVals.begin(), flatOther->returnVals.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
438
439                                                // the original types must be used in mark assertions, since pointer comparisons are used
440                                                markAssertions( haveAssertions, needAssertions, functionType );
441                                                markAssertions( haveAssertions, needAssertions, otherFunction );
442
443                                                result = true;
444                                        } // if
445                                } // if
446                        } // if
447                } // if
448        }
449
450        template< typename RefType >
451        void Unify::handleRefType( RefType *inst, Type *other ) {
452                // check that other type is compatible and named the same
453                RefType *otherStruct = dynamic_cast< RefType* >( other );
454                result = otherStruct && inst->name == otherStruct->name;
455        }
456
457        template< typename RefType >
458        void Unify::handleGenericRefType( RefType *inst, Type *other ) {
459                // Check that other type is compatible and named the same
460                handleRefType( inst, other );
461                if ( ! result ) return;
462                // Check that parameters of types unify, if any
463                std::list< Expression* > params = inst->parameters;
464                std::list< Expression* > otherParams = ((RefType*)other)->parameters;
465
466                std::list< Expression* >::const_iterator it = params.begin(), jt = otherParams.begin();
467                for ( ; it != params.end() && jt != otherParams.end(); ++it, ++jt ) {
468                        TypeExpr *param = dynamic_cast< TypeExpr* >(*it);
469                        assertf(param, "Aggregate parameters should be type expressions");
470                        TypeExpr *otherParam = dynamic_cast< TypeExpr* >(*jt);
471                        assertf(otherParam, "Aggregate parameters should be type expressions");
472
473                        Type* paramTy = param->get_type();
474                        Type* otherParamTy = otherParam->get_type();
475
476                        bool tupleParam = Tuples::isTtype( paramTy );
477                        bool otherTupleParam = Tuples::isTtype( otherParamTy );
478
479                        if ( tupleParam && otherTupleParam ) {
480                                ++it; ++jt;  // skip ttype parameters for break
481                        } else if ( tupleParam ) {
482                                // bundle other parameters into tuple to match
483                                std::list< Type * > binderTypes;
484
485                                do {
486                                        binderTypes.push_back( otherParam->get_type()->clone() );
487                                        ++jt;
488
489                                        if ( jt == otherParams.end() ) break;
490
491                                        otherParam = dynamic_cast< TypeExpr* >(*jt);
492                                        assertf(otherParam, "Aggregate parameters should be type expressions");
493                                } while (true);
494
495                                otherParamTy = new TupleType{ paramTy->get_qualifiers(), binderTypes };
496                                ++it;  // skip ttype parameter for break
497                        } else if ( otherTupleParam ) {
498                                // bundle parameters into tuple to match other
499                                std::list< Type * > binderTypes;
500
501                                do {
502                                        binderTypes.push_back( param->get_type()->clone() );
503                                        ++it;
504
505                                        if ( it == params.end() ) break;
506
507                                        param = dynamic_cast< TypeExpr* >(*it);
508                                        assertf(param, "Aggregate parameters should be type expressions");
509                                } while (true);
510
511                                paramTy = new TupleType{ otherParamTy->get_qualifiers(), binderTypes };
512                                ++jt;  // skip ttype parameter for break
513                        }
514
515                        if ( ! unifyExact( paramTy, otherParamTy, env, needAssertions, haveAssertions, openVars, WidenMode(false, false), indexer ) ) {
516                                result = false;
517                                return;
518                        }
519
520                        // ttype parameter should be last
521                        if ( tupleParam || otherTupleParam ) break;
522                }
523                result = ( it == params.end() && jt == otherParams.end() );
524        }
525
526        void Unify::postvisit(StructInstType *structInst) {
527                handleGenericRefType( structInst, type2 );
528        }
529
530        void Unify::postvisit(UnionInstType *unionInst) {
531                handleGenericRefType( unionInst, type2 );
532        }
533
534        void Unify::postvisit(EnumInstType *enumInst) {
535                handleRefType( enumInst, type2 );
536        }
537
538        void Unify::postvisit(TraitInstType *contextInst) {
539                handleRefType( contextInst, type2 );
540        }
541
542        void Unify::postvisit(TypeInstType *typeInst) {
543                assert( openVars.find( typeInst->get_name() ) == openVars.end() );
544                TypeInstType *otherInst = dynamic_cast< TypeInstType* >( type2 );
545                if ( otherInst && typeInst->get_name() == otherInst->get_name() ) {
546                        result = true;
547///   } else {
548///     NamedTypeDecl *nt = indexer.lookupType( typeInst->get_name() );
549///     if ( nt ) {
550///       TypeDecl *type = dynamic_cast< TypeDecl* >( nt );
551///       assert( type );
552///       if ( type->get_base() ) {
553///         result = unifyExact( type->get_base(), typeInst, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
554///       }
555///     }
556                } // if
557        }
558
559        template< typename Iterator1, typename Iterator2 >
560        bool unifyList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
561                auto get_type = [](Type * t) { return t; };
562                for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) {
563                        Type * t1 = *list1Begin;
564                        Type * t2 = *list2Begin;
565                        bool isTtype1 = Tuples::isTtype( t1 );
566                        bool isTtype2 = Tuples::isTtype( t2 );
567                        // xxx - assumes ttype must be last parameter
568                        // xxx - there may be a nice way to refactor this, but be careful because the argument positioning might matter in some cases.
569                        if ( isTtype1 && ! isTtype2 ) {
570                                // combine all of the things in list2, then unify
571                                return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
572                        } else if ( isTtype2 && ! isTtype1 ) {
573                                // combine all of the things in list1, then unify
574                                return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
575                        } else if ( ! unifyExact( t1, t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ) ) {
576                                return false;
577                        } // if
578
579                } // for
580                if ( list1Begin != list1End ) {
581                        // try unifying empty tuple type with ttype
582                        Type * t1 = *list1Begin;
583                        if ( Tuples::isTtype( t1 ) ) {
584                                return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
585                        } else return false;
586                } else if ( list2Begin != list2End ) {
587                        // try unifying empty tuple type with ttype
588                        Type * t2 = *list2Begin;
589                        if ( Tuples::isTtype( t2 ) ) {
590                                return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
591                        } else return false;
592                } else {
593                        return true;
594                } // if
595        }
596
597        void Unify::postvisit(TupleType *tupleType) {
598                if ( TupleType *otherTuple = dynamic_cast< TupleType* >( type2 ) ) {
599                        std::unique_ptr<TupleType> flat1( tupleType->clone() );
600                        std::unique_ptr<TupleType> flat2( otherTuple->clone() );
601                        std::list<Type *> types1, types2;
602
603                        PassVisitor<TtypeExpander> expander( env );
604                        flat1->acceptMutator( expander );
605                        flat2->acceptMutator( expander );
606
607                        flatten( flat1.get(), back_inserter( types1 ) );
608                        flatten( flat2.get(), back_inserter( types2 ) );
609
610                        result = unifyList( types1.begin(), types1.end(), types2.begin(), types2.end(), env, needAssertions, haveAssertions, openVars, indexer );
611                } // if
612        }
613
614        void Unify::postvisit( __attribute__((unused)) VarArgsType *varArgsType ) {
615                result = dynamic_cast< VarArgsType* >( type2 );
616        }
617
618        void Unify::postvisit( __attribute__((unused)) ZeroType *zeroType ) {
619                result = dynamic_cast< ZeroType* >( type2 );
620        }
621
622        void Unify::postvisit( __attribute__((unused)) OneType *oneType ) {
623                result = dynamic_cast< OneType* >( type2 );
624        }
625
626        // xxx - compute once and store in the FunctionType?
627        Type * extractResultType( FunctionType * function ) {
628                if ( function->get_returnVals().size() == 0 ) {
629                        return new VoidType( Type::Qualifiers() );
630                } else if ( function->get_returnVals().size() == 1 ) {
631                        return function->get_returnVals().front()->get_type()->clone();
632                } else {
633                        std::list< Type * > types;
634                        for ( DeclarationWithType * decl : function->get_returnVals() ) {
635                                types.push_back( decl->get_type()->clone() );
636                        } // for
637                        return new TupleType( Type::Qualifiers(), types );
638                }
639        }
640} // namespace ResolvExpr
641
642// Local Variables: //
643// tab-width: 4 //
644// mode: c++ //
645// compile-command: "make install" //
646// End: //
Note: See TracBrowser for help on using the repository browser.