source: src/ResolvExpr/Unify.cc @ 982f95d

new-env
Last change on this file since 982f95d was 982f95d, checked in by Aaron Moss <a3moss@…>, 6 years ago

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