source: src/ResolvExpr/Unify.cc @ 2890212

arm-ehjacob/cs343-translationnew-astnew-ast-unique-expr
Last change on this file since 2890212 was 2890212, checked in by Thierry Delisle <tdelisle@…>, 2 years ago

Startup.cfa now compiles with new ast

  • Property mode set to 100644
File size: 47.7 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 "Unify.h"
17
18#include <cassert>                  // for assertf, assert
19#include <iterator>                 // for back_insert_iterator, back_inserter
20#include <map>                      // for _Rb_tree_const_iterator, _Rb_tree_i...
21#include <memory>                   // for unique_ptr
22#include <set>                      // for set
23#include <string>                   // for string, operator==, operator!=, bas...
24#include <utility>                  // for pair, move
25#include <vector>
26
27#include "AST/Copy.hpp"
28#include "AST/Decl.hpp"
29#include "AST/Node.hpp"
30#include "AST/Pass.hpp"
31#include "AST/Print.hpp"
32#include "AST/Type.hpp"
33#include "AST/TypeEnvironment.hpp"
34#include "Common/PassVisitor.h"     // for PassVisitor
35#include "FindOpenVars.h"           // for findOpenVars
36#include "Parser/LinkageSpec.h"     // for C
37#include "SynTree/Constant.h"       // for Constant
38#include "SynTree/Declaration.h"    // for TypeDecl, TypeDecl::Data, Declarati...
39#include "SynTree/Expression.h"     // for TypeExpr, Expression, ConstantExpr
40#include "SynTree/Mutator.h"        // for Mutator
41#include "SynTree/Type.h"           // for Type, TypeInstType, FunctionType
42#include "SynTree/Visitor.h"        // for Visitor
43#include "Tuples/Tuples.h"          // for isTtype
44#include "TypeEnvironment.h"        // for EqvClass, AssertionSet, OpenVarSet
45#include "typeops.h"                // for flatten, occurs, commonType
46
47namespace ast {
48        class SymbolTable;
49}
50
51namespace SymTab {
52class Indexer;
53}  // namespace SymTab
54
55// #define DEBUG
56
57namespace ResolvExpr {
58
59        struct Unify_old : public WithShortCircuiting {
60                Unify_old( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer );
61
62                bool get_result() const { return result; }
63
64                void previsit( BaseSyntaxNode * ) { visit_children = false; }
65
66                void postvisit( VoidType * voidType );
67                void postvisit( BasicType * basicType );
68                void postvisit( PointerType * pointerType );
69                void postvisit( ArrayType * arrayType );
70                void postvisit( ReferenceType * refType );
71                void postvisit( FunctionType * functionType );
72                void postvisit( StructInstType * aggregateUseType );
73                void postvisit( UnionInstType * aggregateUseType );
74                void postvisit( EnumInstType * aggregateUseType );
75                void postvisit( TraitInstType * aggregateUseType );
76                void postvisit( TypeInstType * aggregateUseType );
77                void postvisit( TupleType * tupleType );
78                void postvisit( VarArgsType * varArgsType );
79                void postvisit( ZeroType * zeroType );
80                void postvisit( OneType * oneType );
81
82          private:
83                template< typename RefType > void handleRefType( RefType *inst, Type *other );
84                template< typename RefType > void handleGenericRefType( RefType *inst, Type *other );
85
86                bool result;
87                Type *type2;                            // inherited
88                TypeEnvironment &env;
89                AssertionSet &needAssertions;
90                AssertionSet &haveAssertions;
91                const OpenVarSet &openVars;
92                WidenMode widen;
93                const SymTab::Indexer &indexer;
94        };
95
96        /// Attempts an inexact unification of type1 and type2.
97        /// Returns false if no such unification; if the types can be unified, sets common (unless they unify exactly and have identical type qualifiers)
98        bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer, Type *&common );
99        bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer );
100
101        bool unifyExact(
102                const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env,
103                ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
104                WidenMode widen, const ast::SymbolTable & symtab );
105
106        bool typesCompatible( const Type * first, const Type * second, const SymTab::Indexer & indexer, const TypeEnvironment & env ) {
107                TypeEnvironment newEnv;
108                OpenVarSet openVars, closedVars; // added closedVars
109                AssertionSet needAssertions, haveAssertions;
110                Type * newFirst = first->clone(), * newSecond = second->clone();
111                env.apply( newFirst );
112                env.apply( newSecond );
113
114                // do we need to do this? Seems like we do, types should be able to be compatible if they
115                // have free variables that can unify
116                findOpenVars( newFirst, openVars, closedVars, needAssertions, haveAssertions, false );
117                findOpenVars( newSecond, openVars, closedVars, needAssertions, haveAssertions, true );
118
119                bool result = unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
120                delete newFirst;
121                delete newSecond;
122                return result;
123        }
124
125        bool typesCompatible(
126                        const ast::Type * first, const ast::Type * second, const ast::SymbolTable & symtab,
127                        const ast::TypeEnvironment & env ) {
128                ast::TypeEnvironment newEnv;
129                ast::OpenVarSet open, closed;
130                ast::AssertionSet need, have;
131
132                ast::ptr<ast::Type> newFirst{ first }, newSecond{ second };
133                env.apply( newFirst );
134                env.apply( newSecond );
135
136                findOpenVars( newFirst, open, closed, need, have, FirstClosed );
137                findOpenVars( newSecond, open, closed, need, have, FirstOpen );
138
139                return unifyExact(newFirst, newSecond, newEnv, need, have, open, noWiden(), symtab );
140        }
141
142        bool typesCompatibleIgnoreQualifiers( const Type * first, const Type * second, const SymTab::Indexer &indexer, const TypeEnvironment &env ) {
143                TypeEnvironment newEnv;
144                OpenVarSet openVars;
145                AssertionSet needAssertions, haveAssertions;
146                Type *newFirst = first->clone(), *newSecond = second->clone();
147                env.apply( newFirst );
148                env.apply( newSecond );
149                newFirst->get_qualifiers() = Type::Qualifiers();
150                newSecond->get_qualifiers() = Type::Qualifiers();
151
152                bool result = unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
153                delete newFirst;
154                delete newSecond;
155                return result;
156        }
157
158        bool typesCompatibleIgnoreQualifiers(
159                        const ast::Type * first, const ast::Type * second, const ast::SymbolTable & symtab,
160                        const ast::TypeEnvironment & env ) {
161                ast::TypeEnvironment newEnv;
162                ast::OpenVarSet open;
163                ast::AssertionSet need, have;
164
165                ast::Type * newFirst  = shallowCopy( first  );
166                ast::Type * newSecond = shallowCopy( second );
167                newFirst ->qualifiers = {};
168                newSecond->qualifiers = {};
169                #warning memory leak
170
171                return unifyExact(
172                        env.apply( newFirst  ).node,
173                        env.apply( newSecond ).node,
174                        newEnv, need, have, open, noWiden(), symtab );
175        }
176
177        bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
178                OpenVarSet closedVars;
179                findOpenVars( type1, openVars, closedVars, needAssertions, haveAssertions, false );
180                findOpenVars( type2, openVars, closedVars, needAssertions, haveAssertions, true );
181                Type *commonType = 0;
182                if ( unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType ) ) {
183                        if ( commonType ) {
184                                delete commonType;
185                        } // if
186                        return true;
187                } else {
188                        return false;
189                } // if
190        }
191
192        bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer, Type *&commonType ) {
193                OpenVarSet closedVars;
194                findOpenVars( type1, openVars, closedVars, needAssertions, haveAssertions, false );
195                findOpenVars( type2, openVars, closedVars, needAssertions, haveAssertions, true );
196                return unifyInexact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( true, true ), indexer, commonType );
197        }
198
199        bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ) {
200#ifdef DEBUG
201                TypeEnvironment debugEnv( env );
202#endif
203                if ( type1->get_qualifiers() != type2->get_qualifiers() ) {
204                        return false;
205                }
206
207                bool result;
208                TypeInstType *var1 = dynamic_cast< TypeInstType* >( type1 );
209                TypeInstType *var2 = dynamic_cast< TypeInstType* >( type2 );
210                OpenVarSet::const_iterator entry1, entry2;
211                if ( var1 ) {
212                        entry1 = openVars.find( var1->get_name() );
213                } // if
214                if ( var2 ) {
215                        entry2 = openVars.find( var2->get_name() );
216                } // if
217                bool isopen1 = var1 && ( entry1 != openVars.end() );
218                bool isopen2 = var2 && ( entry2 != openVars.end() );
219
220                if ( isopen1 && isopen2 ) {
221                        if ( entry1->second.kind != entry2->second.kind ) {
222                                result = false;
223                        } else {
224                                result = env.bindVarToVar(
225                                        var1, var2, TypeDecl::Data{ entry1->second, entry2->second }, needAssertions,
226                                        haveAssertions, openVars, widen, indexer );
227                        }
228                } else if ( isopen1 ) {
229                        result = env.bindVar( var1, type2, entry1->second, needAssertions, haveAssertions, openVars, widen, indexer );
230                } else if ( isopen2 ) { // TODO: swap widen values in call, since type positions are flipped?
231                        result = env.bindVar( var2, type1, entry2->second, needAssertions, haveAssertions, openVars, widen, indexer );
232                } else {
233                        PassVisitor<Unify_old> comparator( type2, env, needAssertions, haveAssertions, openVars, widen, indexer );
234                        type1->accept( comparator );
235                        result = comparator.pass.get_result();
236                } // if
237#ifdef DEBUG
238                std::cerr << "============ unifyExact" << std::endl;
239                std::cerr << "type1 is ";
240                type1->print( std::cerr );
241                std::cerr << std::endl << "type2 is ";
242                type2->print( std::cerr );
243                std::cerr << std::endl << "openVars are ";
244                printOpenVarSet( openVars, std::cerr, 8 );
245                std::cerr << std::endl << "input env is " << std::endl;
246                debugEnv.print( std::cerr, 8 );
247                std::cerr << std::endl << "result env is " << std::endl;
248                env.print( std::cerr, 8 );
249                std::cerr << "result is " << result << std::endl;
250#endif
251                return result;
252        }
253
254        bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
255                return unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
256        }
257
258        bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer, Type *&common ) {
259                Type::Qualifiers tq1 = type1->get_qualifiers(), tq2 = type2->get_qualifiers();
260                type1->get_qualifiers() = Type::Qualifiers();
261                type2->get_qualifiers() = Type::Qualifiers();
262                bool result;
263#ifdef DEBUG
264                std::cerr << "unifyInexact type 1 is ";
265                type1->print( std::cerr );
266                std::cerr << " type 2 is ";
267                type2->print( std::cerr );
268                std::cerr << std::endl;
269#endif
270                if ( ! unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, widen, indexer ) ) {
271#ifdef DEBUG
272                        std::cerr << "unifyInexact: no exact unification found" << std::endl;
273#endif
274                        if ( ( common = commonType( type1, type2, widen.first, widen.second, indexer, env, openVars ) ) ) {
275                                common->get_qualifiers() = tq1 | tq2;
276#ifdef DEBUG
277                                std::cerr << "unifyInexact: common type is ";
278                                common->print( std::cerr );
279                                std::cerr << std::endl;
280#endif
281                                result = true;
282                        } else {
283#ifdef DEBUG
284                                std::cerr << "unifyInexact: no common type found" << std::endl;
285#endif
286                                result = false;
287                        } // if
288                } else {
289                        if ( tq1 != tq2 ) {
290                                if ( ( tq1 > tq2 || widen.first ) && ( tq2 > tq1 || widen.second ) ) {
291                                        common = type1->clone();
292                                        common->get_qualifiers() = tq1 | tq2;
293                                        result = true;
294                                } else {
295                                        result = false;
296                                } // if
297                        } else {
298                                common = type1->clone();
299                                common->get_qualifiers() = tq1 | tq2;
300                                result = true;
301                        } // if
302                } // if
303                type1->get_qualifiers() = tq1;
304                type2->get_qualifiers() = tq2;
305                return result;
306        }
307
308        Unify_old::Unify_old( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer )
309                : result( false ), type2( type2 ), env( env ), needAssertions( needAssertions ), haveAssertions( haveAssertions ), openVars( openVars ), widen( widen ), indexer( indexer ) {
310        }
311
312        void Unify_old::postvisit( __attribute__((unused)) VoidType *voidType) {
313                result = dynamic_cast< VoidType* >( type2 );
314        }
315
316        void Unify_old::postvisit(BasicType *basicType) {
317                if ( BasicType *otherBasic = dynamic_cast< BasicType* >( type2 ) ) {
318                        result = basicType->get_kind() == otherBasic->get_kind();
319                } // if
320        }
321
322        void markAssertionSet( AssertionSet &assertions, DeclarationWithType *assert ) {
323                AssertionSet::iterator i = assertions.find( assert );
324                if ( i != assertions.end() ) {
325                        i->second.isUsed = true;
326                } // if
327        }
328
329        void markAssertions( AssertionSet &assertion1, AssertionSet &assertion2, Type *type ) {
330                for ( std::list< TypeDecl* >::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
331                        for ( std::list< DeclarationWithType* >::const_iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) {
332                                markAssertionSet( assertion1, *assert );
333                                markAssertionSet( assertion2, *assert );
334                        } // for
335                } // for
336        }
337
338        void Unify_old::postvisit(PointerType *pointerType) {
339                if ( PointerType *otherPointer = dynamic_cast< PointerType* >( type2 ) ) {
340                        result = unifyExact( pointerType->get_base(), otherPointer->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
341                        markAssertions( haveAssertions, needAssertions, pointerType );
342                        markAssertions( haveAssertions, needAssertions, otherPointer );
343                } // if
344        }
345
346        void Unify_old::postvisit(ReferenceType *refType) {
347                if ( ReferenceType *otherRef = dynamic_cast< ReferenceType* >( type2 ) ) {
348                        result = unifyExact( refType->get_base(), otherRef->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
349                        markAssertions( haveAssertions, needAssertions, refType );
350                        markAssertions( haveAssertions, needAssertions, otherRef );
351                } // if
352        }
353
354        void Unify_old::postvisit(ArrayType *arrayType) {
355                ArrayType *otherArray = dynamic_cast< ArrayType* >( type2 );
356                // to unify, array types must both be VLA or both not VLA
357                // and must both have a dimension expression or not have a dimension
358                if ( otherArray && arrayType->get_isVarLen() == otherArray->get_isVarLen() ) {
359
360                        if ( ! arrayType->get_isVarLen() && ! otherArray->get_isVarLen() &&
361                                arrayType->get_dimension() != 0 && otherArray->get_dimension() != 0 ) {
362                                ConstantExpr * ce1 = dynamic_cast< ConstantExpr * >( arrayType->get_dimension() );
363                                ConstantExpr * ce2 = dynamic_cast< ConstantExpr * >( otherArray->get_dimension() );
364                                // see C11 Reference Manual 6.7.6.2.6
365                                // two array types with size specifiers that are integer constant expressions are
366                                // compatible if both size specifiers have the same constant value
367                                if ( ce1 && ce2 ) {
368                                        Constant * c1 = ce1->get_constant();
369                                        Constant * c2 = ce2->get_constant();
370
371                                        if ( c1->get_value() != c2->get_value() ) {
372                                                // does not unify if the dimension is different
373                                                return;
374                                        }
375                                }
376                        }
377
378                        result = unifyExact( arrayType->get_base(), otherArray->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
379                } // if
380        }
381
382        template< typename Iterator, typename Func >
383        std::unique_ptr<Type> combineTypes( Iterator begin, Iterator end, Func & toType ) {
384                std::list< Type * > types;
385                for ( ; begin != end; ++begin ) {
386                        // it's guaranteed that a ttype variable will be bound to a flat tuple, so ensure that this results in a flat tuple
387                        flatten( toType( *begin ), back_inserter( types ) );
388                }
389                return std::unique_ptr<Type>( new TupleType( Type::Qualifiers(), types ) );
390        }
391
392        template< typename Iterator1, typename Iterator2 >
393        bool unifyDeclList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
394                auto get_type = [](DeclarationWithType * dwt){ return dwt->get_type(); };
395                for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) {
396                        Type * t1 = (*list1Begin)->get_type();
397                        Type * t2 = (*list2Begin)->get_type();
398                        bool isTtype1 = Tuples::isTtype( t1 );
399                        bool isTtype2 = Tuples::isTtype( t2 );
400                        // xxx - assumes ttype must be last parameter
401                        // xxx - there may be a nice way to refactor this, but be careful because the argument positioning might matter in some cases.
402                        if ( isTtype1 && ! isTtype2 ) {
403                                // combine all of the things in list2, then unify
404                                return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
405                        } else if ( isTtype2 && ! isTtype1 ) {
406                                // combine all of the things in list1, then unify
407                                return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
408                        } else if ( ! unifyExact( t1, t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ) ) {
409                                return false;
410                        } // if
411                } // for
412                // 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
413                if ( list1Begin != list1End ) {
414                        // try unifying empty tuple type with ttype
415                        Type * t1 = (*list1Begin)->get_type();
416                        if ( Tuples::isTtype( t1 ) ) {
417                                return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
418                        } else return false;
419                } else if ( list2Begin != list2End ) {
420                        // try unifying empty tuple type with ttype
421                        Type * t2 = (*list2Begin)->get_type();
422                        if ( Tuples::isTtype( t2 ) ) {
423                                return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
424                        } else return false;
425                } else {
426                        return true;
427                } // if
428        }
429
430        /// Finds ttypes and replaces them with their expansion, if known.
431        /// This needs to be done so that satisfying ttype assertions is easier.
432        /// If this isn't done then argument lists can have wildly different
433        /// size and structure, when they should be compatible.
434        struct TtypeExpander_old : public WithShortCircuiting {
435                TypeEnvironment & tenv;
436                TtypeExpander_old( TypeEnvironment & tenv ) : tenv( tenv ) {}
437                void premutate( TypeInstType * ) { visit_children = false; }
438                Type * postmutate( TypeInstType * typeInst ) {
439                        if ( const EqvClass *eqvClass = tenv.lookup( typeInst->get_name() ) ) {
440                                // expand ttype parameter into its actual type
441                                if ( eqvClass->data.kind == TypeDecl::Ttype && eqvClass->type ) {
442                                        delete typeInst;
443                                        return eqvClass->type->clone();
444                                }
445                        }
446                        return typeInst;
447                }
448        };
449
450        /// flattens a list of declarations, so that each tuple type has a single declaration.
451        /// makes use of TtypeExpander to ensure ttypes are flat as well.
452        void flattenList( std::list< DeclarationWithType * > src, std::list< DeclarationWithType * > & dst, TypeEnvironment & env ) {
453                dst.clear();
454                for ( DeclarationWithType * dcl : src ) {
455                        PassVisitor<TtypeExpander_old> expander( env );
456                        dcl->acceptMutator( expander );
457                        std::list< Type * > types;
458                        flatten( dcl->get_type(), back_inserter( types ) );
459                        for ( Type * t : types ) {
460                                // 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.
461                                // 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.
462                                t->get_qualifiers() -= Type::Qualifiers(Type::Const | Type::Volatile | Type::Atomic);
463
464                                dst.push_back( new ObjectDecl( "", Type::StorageClasses(), LinkageSpec::C, nullptr, t, nullptr ) );
465                        }
466                        delete dcl;
467                }
468        }
469
470        void Unify_old::postvisit(FunctionType *functionType) {
471                FunctionType *otherFunction = dynamic_cast< FunctionType* >( type2 );
472                if ( otherFunction && functionType->get_isVarArgs() == otherFunction->get_isVarArgs() ) {
473                        // flatten the parameter lists for both functions so that tuple structure
474                        // doesn't affect unification. Must be a clone so that the types don't change.
475                        std::unique_ptr<FunctionType> flatFunc( functionType->clone() );
476                        std::unique_ptr<FunctionType> flatOther( otherFunction->clone() );
477                        flattenList( flatFunc->get_parameters(), flatFunc->get_parameters(), env );
478                        flattenList( flatOther->get_parameters(), flatOther->get_parameters(), env );
479
480                        // sizes don't have to match if ttypes are involved; need to be more precise wrt where the ttype is to prevent errors
481                        if (
482                                        (flatFunc->parameters.size() == flatOther->parameters.size() &&
483                                                flatFunc->returnVals.size() == flatOther->returnVals.size())
484                                        || flatFunc->isTtype()
485                                        || flatOther->isTtype()
486                        ) {
487                                if ( unifyDeclList( flatFunc->parameters.begin(), flatFunc->parameters.end(), flatOther->parameters.begin(), flatOther->parameters.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
488                                        if ( unifyDeclList( flatFunc->returnVals.begin(), flatFunc->returnVals.end(), flatOther->returnVals.begin(), flatOther->returnVals.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {
489
490                                                // the original types must be used in mark assertions, since pointer comparisons are used
491                                                markAssertions( haveAssertions, needAssertions, functionType );
492                                                markAssertions( haveAssertions, needAssertions, otherFunction );
493
494                                                result = true;
495                                        } // if
496                                } // if
497                        } // if
498                } // if
499        }
500
501        template< typename RefType >
502        void Unify_old::handleRefType( RefType *inst, Type *other ) {
503                // check that other type is compatible and named the same
504                RefType *otherStruct = dynamic_cast< RefType* >( other );
505                result = otherStruct && inst->name == otherStruct->name;
506        }
507
508        template< typename RefType >
509        void Unify_old::handleGenericRefType( RefType *inst, Type *other ) {
510                // Check that other type is compatible and named the same
511                handleRefType( inst, other );
512                if ( ! result ) return;
513                // Check that parameters of types unify, if any
514                std::list< Expression* > params = inst->parameters;
515                std::list< Expression* > otherParams = ((RefType*)other)->parameters;
516
517                std::list< Expression* >::const_iterator it = params.begin(), jt = otherParams.begin();
518                for ( ; it != params.end() && jt != otherParams.end(); ++it, ++jt ) {
519                        TypeExpr *param = dynamic_cast< TypeExpr* >(*it);
520                        assertf(param, "Aggregate parameters should be type expressions");
521                        TypeExpr *otherParam = dynamic_cast< TypeExpr* >(*jt);
522                        assertf(otherParam, "Aggregate parameters should be type expressions");
523
524                        Type* paramTy = param->get_type();
525                        Type* otherParamTy = otherParam->get_type();
526
527                        bool tupleParam = Tuples::isTtype( paramTy );
528                        bool otherTupleParam = Tuples::isTtype( otherParamTy );
529
530                        if ( tupleParam && otherTupleParam ) {
531                                ++it; ++jt;  // skip ttype parameters for break
532                        } else if ( tupleParam ) {
533                                // bundle other parameters into tuple to match
534                                std::list< Type * > binderTypes;
535
536                                do {
537                                        binderTypes.push_back( otherParam->get_type()->clone() );
538                                        ++jt;
539
540                                        if ( jt == otherParams.end() ) break;
541
542                                        otherParam = dynamic_cast< TypeExpr* >(*jt);
543                                        assertf(otherParam, "Aggregate parameters should be type expressions");
544                                } while (true);
545
546                                otherParamTy = new TupleType{ paramTy->get_qualifiers(), binderTypes };
547                                ++it;  // skip ttype parameter for break
548                        } else if ( otherTupleParam ) {
549                                // bundle parameters into tuple to match other
550                                std::list< Type * > binderTypes;
551
552                                do {
553                                        binderTypes.push_back( param->get_type()->clone() );
554                                        ++it;
555
556                                        if ( it == params.end() ) break;
557
558                                        param = dynamic_cast< TypeExpr* >(*it);
559                                        assertf(param, "Aggregate parameters should be type expressions");
560                                } while (true);
561
562                                paramTy = new TupleType{ otherParamTy->get_qualifiers(), binderTypes };
563                                ++jt;  // skip ttype parameter for break
564                        }
565
566                        if ( ! unifyExact( paramTy, otherParamTy, env, needAssertions, haveAssertions, openVars, WidenMode(false, false), indexer ) ) {
567                                result = false;
568                                return;
569                        }
570
571                        // ttype parameter should be last
572                        if ( tupleParam || otherTupleParam ) break;
573                }
574                result = ( it == params.end() && jt == otherParams.end() );
575        }
576
577        void Unify_old::postvisit(StructInstType *structInst) {
578                handleGenericRefType( structInst, type2 );
579        }
580
581        void Unify_old::postvisit(UnionInstType *unionInst) {
582                handleGenericRefType( unionInst, type2 );
583        }
584
585        void Unify_old::postvisit(EnumInstType *enumInst) {
586                handleRefType( enumInst, type2 );
587        }
588
589        void Unify_old::postvisit(TraitInstType *contextInst) {
590                handleRefType( contextInst, type2 );
591        }
592
593        void Unify_old::postvisit(TypeInstType *typeInst) {
594                assert( openVars.find( typeInst->get_name() ) == openVars.end() );
595                TypeInstType *otherInst = dynamic_cast< TypeInstType* >( type2 );
596                if ( otherInst && typeInst->get_name() == otherInst->get_name() ) {
597                        result = true;
598///   } else {
599///     NamedTypeDecl *nt = indexer.lookupType( typeInst->get_name() );
600///     if ( nt ) {
601///       TypeDecl *type = dynamic_cast< TypeDecl* >( nt );
602///       assert( type );
603///       if ( type->get_base() ) {
604///         result = unifyExact( type->get_base(), typeInst, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
605///       }
606///     }
607                } // if
608        }
609
610        template< typename Iterator1, typename Iterator2 >
611        bool unifyList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) {
612                auto get_type = [](Type * t) { return t; };
613                for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) {
614                        Type * t1 = *list1Begin;
615                        Type * t2 = *list2Begin;
616                        bool isTtype1 = Tuples::isTtype( t1 );
617                        bool isTtype2 = Tuples::isTtype( t2 );
618                        // xxx - assumes ttype must be last parameter
619                        // xxx - there may be a nice way to refactor this, but be careful because the argument positioning might matter in some cases.
620                        if ( isTtype1 && ! isTtype2 ) {
621                                // combine all of the things in list2, then unify
622                                return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
623                        } else if ( isTtype2 && ! isTtype1 ) {
624                                // combine all of the things in list1, then unify
625                                return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
626                        } else if ( ! unifyExact( t1, t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ) ) {
627                                return false;
628                        } // if
629
630                } // for
631                if ( list1Begin != list1End ) {
632                        // try unifying empty tuple type with ttype
633                        Type * t1 = *list1Begin;
634                        if ( Tuples::isTtype( t1 ) ) {
635                                return unifyExact( t1, combineTypes( list2Begin, list2End, get_type ).get(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
636                        } else return false;
637                } else if ( list2Begin != list2End ) {
638                        // try unifying empty tuple type with ttype
639                        Type * t2 = *list2Begin;
640                        if ( Tuples::isTtype( t2 ) ) {
641                                return unifyExact( combineTypes( list1Begin, list1End, get_type ).get(), t2, env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer );
642                        } else return false;
643                } else {
644                        return true;
645                } // if
646        }
647
648        void Unify_old::postvisit(TupleType *tupleType) {
649                if ( TupleType *otherTuple = dynamic_cast< TupleType* >( type2 ) ) {
650                        std::unique_ptr<TupleType> flat1( tupleType->clone() );
651                        std::unique_ptr<TupleType> flat2( otherTuple->clone() );
652                        std::list<Type *> types1, types2;
653
654                        PassVisitor<TtypeExpander_old> expander( env );
655                        flat1->acceptMutator( expander );
656                        flat2->acceptMutator( expander );
657
658                        flatten( flat1.get(), back_inserter( types1 ) );
659                        flatten( flat2.get(), back_inserter( types2 ) );
660
661                        result = unifyList( types1.begin(), types1.end(), types2.begin(), types2.end(), env, needAssertions, haveAssertions, openVars, indexer );
662                } // if
663        }
664
665        void Unify_old::postvisit( __attribute__((unused)) VarArgsType *varArgsType ) {
666                result = dynamic_cast< VarArgsType* >( type2 );
667        }
668
669        void Unify_old::postvisit( __attribute__((unused)) ZeroType *zeroType ) {
670                result = dynamic_cast< ZeroType* >( type2 );
671        }
672
673        void Unify_old::postvisit( __attribute__((unused)) OneType *oneType ) {
674                result = dynamic_cast< OneType* >( type2 );
675        }
676
677        Type * extractResultType( FunctionType * function ) {
678                if ( function->get_returnVals().size() == 0 ) {
679                        return new VoidType( Type::Qualifiers() );
680                } else if ( function->get_returnVals().size() == 1 ) {
681                        return function->get_returnVals().front()->get_type()->clone();
682                } else {
683                        std::list< Type * > types;
684                        for ( DeclarationWithType * decl : function->get_returnVals() ) {
685                                types.push_back( decl->get_type()->clone() );
686                        } // for
687                        return new TupleType( Type::Qualifiers(), types );
688                }
689        }
690
691        class Unify_new final : public ast::WithShortCircuiting {
692                const ast::Type * type2;
693                ast::TypeEnvironment & tenv;
694                ast::AssertionSet & need;
695                ast::AssertionSet & have;
696                const ast::OpenVarSet & open;
697                WidenMode widen;
698                const ast::SymbolTable & symtab;
699        public:
700                bool result;
701
702                Unify_new(
703                        const ast::Type * type2, ast::TypeEnvironment & env, ast::AssertionSet & need,
704                        ast::AssertionSet & have, const ast::OpenVarSet & open, WidenMode widen,
705                        const ast::SymbolTable & symtab )
706                : type2(type2), tenv(env), need(need), have(have), open(open), widen(widen),
707                  symtab(symtab), result(false) {}
708
709                void previsit( const ast::Node * ) { visit_children = false; }
710
711                void postvisit( const ast::VoidType * ) {
712                        result = dynamic_cast< const ast::VoidType * >( type2 );
713                }
714
715                void postvisit( const ast::BasicType * basic ) {
716                        if ( auto basic2 = dynamic_cast< const ast::BasicType * >( type2 ) ) {
717                                result = basic->kind == basic2->kind;
718                        }
719                }
720
721                void postvisit( const ast::PointerType * pointer ) {
722                        if ( auto pointer2 = dynamic_cast< const ast::PointerType * >( type2 ) ) {
723                                result = unifyExact(
724                                        pointer->base, pointer2->base, tenv, need, have, open,
725                                        noWiden(), symtab );
726                        }
727                }
728
729                void postvisit( const ast::ArrayType * array ) {
730                        auto array2 = dynamic_cast< const ast::ArrayType * >( type2 );
731                        if ( ! array2 ) return;
732
733                        // to unify, array types must both be VLA or both not VLA and both must have a
734                        // dimension expression or not have a dimension
735                        if ( array->isVarLen != array2->isVarLen ) return;
736                        if ( ! array->isVarLen && ! array2->isVarLen
737                                        && array->dimension && array2->dimension ) {
738                                auto ce1 = array->dimension.as< ast::ConstantExpr >();
739                                auto ce2 = array2->dimension.as< ast::ConstantExpr >();
740
741                                // see C11 Reference Manual 6.7.6.2.6
742                                // two array types with size specifiers that are integer constant expressions are
743                                // compatible if both size specifiers have the same constant value
744                                if ( ce1 && ce2 && ce1->intValue() != ce2->intValue() ) return;
745                        }
746
747                        result = unifyExact(
748                                array->base, array2->base, tenv, need, have, open, noWiden(),
749                                symtab );
750                }
751
752                void postvisit( const ast::ReferenceType * ref ) {
753                        if ( auto ref2 = dynamic_cast< const ast::ReferenceType * >( type2 ) ) {
754                                result = unifyExact(
755                                        ref->base, ref2->base, tenv, need, have, open, noWiden(),
756                                        symtab );
757                        }
758                }
759
760        private:
761                /// Replaces ttype variables with their bound types.
762                /// If this isn't done when satifying ttype assertions, then argument lists can have
763                /// different size and structure when they should be compatible.
764                struct TtypeExpander_new : public ast::WithShortCircuiting {
765                        ast::TypeEnvironment & tenv;
766
767                        TtypeExpander_new( ast::TypeEnvironment & env ) : tenv( env ) {}
768
769                        const ast::Type * postvisit( const ast::TypeInstType * typeInst ) {
770                                if ( const ast::EqvClass * clz = tenv.lookup( typeInst->name ) ) {
771                                        // expand ttype parameter into its actual type
772                                        if ( clz->data.kind == ast::TypeVar::Ttype && clz->bound ) {
773                                                return clz->bound;
774                                        }
775                                }
776                                return typeInst;
777                        }
778                };
779
780                /// returns flattened version of `src`
781                static std::vector< ast::ptr< ast::DeclWithType > > flattenList(
782                        const std::vector< ast::ptr< ast::DeclWithType > > & src, ast::TypeEnvironment & env
783                ) {
784                        std::vector< ast::ptr< ast::DeclWithType > > dst;
785                        dst.reserve( src.size() );
786                        for ( const ast::DeclWithType * d : src ) {
787                                ast::Pass<TtypeExpander_new> expander{ env };
788                                d = d->accept( expander );
789                                auto types = flatten( d->get_type() );
790                                for ( ast::ptr< ast::Type > & t : types ) {
791                                        // outermost const, volatile, _Atomic qualifiers in parameters should not play
792                                        // a role in the unification of function types, since they do not determine
793                                        // whether a function is callable.
794                                        // NOTE: **must** consider at least mutex qualifier, since functions can be
795                                        // overloaded on outermost mutex and a mutex function has different
796                                        // requirements than a non-mutex function
797                                        remove_qualifiers( t, ast::CV::Const | ast::CV::Volatile | ast::CV::Atomic );
798                                        dst.emplace_back( new ast::ObjectDecl{ d->location, "", t } );
799                                }
800                        }
801                        return dst;
802                }
803
804                /// Creates a tuple type based on a list of DeclWithType
805                template< typename Iter >
806                static ast::ptr< ast::Type > tupleFromDecls( Iter crnt, Iter end ) {
807                        std::vector< ast::ptr< ast::Type > > types;
808                        while ( crnt != end ) {
809                                // it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure
810                                // that this results in a flat tuple
811                                flatten( (*crnt)->get_type(), types );
812
813                                ++crnt;
814                        }
815
816                        return { new ast::TupleType{ std::move(types) } };
817                }
818
819                template< typename Iter >
820                static bool unifyDeclList(
821                        Iter crnt1, Iter end1, Iter crnt2, Iter end2, ast::TypeEnvironment & env,
822                        ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
823                        const ast::SymbolTable & symtab
824                ) {
825                        while ( crnt1 != end1 && crnt2 != end2 ) {
826                                const ast::Type * t1 = (*crnt1)->get_type();
827                                const ast::Type * t2 = (*crnt2)->get_type();
828                                bool isTuple1 = Tuples::isTtype( t1 );
829                                bool isTuple2 = Tuples::isTtype( t2 );
830
831                                // assumes here that ttype *must* be last parameter
832                                if ( isTuple1 && ! isTuple2 ) {
833                                        // combine remainder of list2, then unify
834                                        return unifyExact(
835                                                t1, tupleFromDecls( crnt2, end2 ), env, need, have, open,
836                                                noWiden(), symtab );
837                                } else if ( ! isTuple1 && isTuple2 ) {
838                                        // combine remainder of list1, then unify
839                                        return unifyExact(
840                                                tupleFromDecls( crnt1, end1 ), t2, env, need, have, open,
841                                                noWiden(), symtab );
842                                }
843
844                                if ( ! unifyExact(
845                                        t1, t2, env, need, have, open, noWiden(), symtab )
846                                ) return false;
847
848                                ++crnt1; ++crnt2;
849                        }
850
851                        // May get to the end of one argument list before the other. This is only okay if the
852                        // other is a ttype
853                        if ( crnt1 != end1 ) {
854                                // try unifying empty tuple with ttype
855                                const ast::Type * t1 = (*crnt1)->get_type();
856                                if ( ! Tuples::isTtype( t1 ) ) return false;
857                                return unifyExact(
858                                        t1, tupleFromDecls( crnt2, end2 ), env, need, have, open,
859                                        noWiden(), symtab );
860                        } else if ( crnt2 != end2 ) {
861                                // try unifying empty tuple with ttype
862                                const ast::Type * t2 = (*crnt2)->get_type();
863                                if ( ! Tuples::isTtype( t2 ) ) return false;
864                                return unifyExact(
865                                        tupleFromDecls( crnt1, end1 ), t2, env, need, have, open,
866                                        noWiden(), symtab );
867                        }
868
869                        return true;
870                }
871
872                static bool unifyDeclList(
873                        const std::vector< ast::ptr< ast::DeclWithType > > & list1,
874                        const std::vector< ast::ptr< ast::DeclWithType > > & list2,
875                        ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
876                        const ast::OpenVarSet & open, const ast::SymbolTable & symtab
877                ) {
878                        return unifyDeclList(
879                                list1.begin(), list1.end(), list2.begin(), list2.end(), env, need, have, open,
880                                symtab );
881                }
882
883                static void markAssertionSet( ast::AssertionSet & assns, const ast::DeclWithType * assn ) {
884                        auto i = assns.find( assn );
885                        if ( i != assns.end() ) {
886                                i->second.isUsed = true;
887                        }
888                }
889
890                /// mark all assertions in `type` used in both `assn1` and `assn2`
891                static void markAssertions(
892                        ast::AssertionSet & assn1, ast::AssertionSet & assn2,
893                        const ast::ParameterizedType * type
894                ) {
895                        for ( const auto & tyvar : type->forall ) {
896                                for ( const ast::DeclWithType * assert : tyvar->assertions ) {
897                                        markAssertionSet( assn1, assert );
898                                        markAssertionSet( assn2, assert );
899                                }
900                        }
901                }
902
903        public:
904                void postvisit( const ast::FunctionType * func ) {
905                        auto func2 = dynamic_cast< const ast::FunctionType * >( type2 );
906                        if ( ! func2 ) return;
907
908                        if ( func->isVarArgs != func2->isVarArgs ) return;
909
910                        // Flatten the parameter lists for both functions so that tuple structure does not
911                        // affect unification. Does not actually mutate function parameters.
912                        auto params = flattenList( func->params, tenv );
913                        auto params2 = flattenList( func2->params, tenv );
914
915                        // sizes don't have to match if ttypes are involved; need to be more precise w.r.t.
916                        // where the ttype is to prevent errors
917                        if (
918                                ( params.size() != params2.size() || func->returns.size() != func2->returns.size() )
919                                && ! func->isTtype()
920                                && ! func2->isTtype()
921                        ) return;
922
923                        if ( ! unifyDeclList( params, params2, tenv, need, have, open, symtab ) ) return;
924                        if ( ! unifyDeclList(
925                                func->returns, func2->returns, tenv, need, have, open, symtab ) ) return;
926
927                        markAssertions( have, need, func );
928                        markAssertions( have, need, func2 );
929
930                        result = true;
931                }
932
933        private:
934                template< typename RefType >
935                const RefType * handleRefType( const RefType * inst, const ast::Type * other ) {
936                        // check that the other type is compatible and named the same
937                        auto otherInst = dynamic_cast< const RefType * >( other );
938                        result = otherInst && inst->name == otherInst->name;
939                        return otherInst;
940                }
941
942                /// Creates a tuple type based on a list of TypeExpr
943                template< typename Iter >
944                static const ast::Type * tupleFromExprs(
945                        const ast::TypeExpr * param, Iter & crnt, Iter end, ast::CV::Qualifiers qs
946                ) {
947                        std::vector< ast::ptr< ast::Type > > types;
948                        do {
949                                types.emplace_back( param->type );
950
951                                ++crnt;
952                                if ( crnt == end ) break;
953                                param = strict_dynamic_cast< const ast::TypeExpr * >( crnt->get() );
954                        } while(true);
955
956                        return new ast::TupleType{ std::move(types), qs };
957                }
958
959                template< typename RefType >
960                void handleGenericRefType( const RefType * inst, const ast::Type * other ) {
961                        // check that other type is compatible and named the same
962                        const RefType * inst2 = handleRefType( inst, other );
963                        if ( ! inst2 ) return;
964
965                        // check that parameters of types unify, if any
966                        const std::vector< ast::ptr< ast::Expr > > & params = inst->params;
967                        const std::vector< ast::ptr< ast::Expr > > & params2 = inst2->params;
968
969                        auto it = params.begin();
970                        auto jt = params2.begin();
971                        for ( ; it != params.end() && jt != params2.end(); ++it, ++jt ) {
972                                auto param = strict_dynamic_cast< const ast::TypeExpr * >( it->get() );
973                                auto param2 = strict_dynamic_cast< const ast::TypeExpr * >( jt->get() );
974
975                                ast::ptr< ast::Type > pty = param->type;
976                                ast::ptr< ast::Type > pty2 = param2->type;
977
978                                bool isTuple = Tuples::isTtype( pty );
979                                bool isTuple2 = Tuples::isTtype( pty2 );
980
981                                if ( isTuple && isTuple2 ) {
982                                        ++it; ++jt;  // skip ttype parameters before break
983                                } else if ( isTuple ) {
984                                        // bundle remaining params into tuple
985                                        pty2 = tupleFromExprs( param2, jt, params2.end(), pty->qualifiers );
986                                        ++it;  // skip ttype parameter for break
987                                } else if ( isTuple2 ) {
988                                        // bundle remaining params into tuple
989                                        pty = tupleFromExprs( param, it, params.end(), pty2->qualifiers );
990                                        ++jt;  // skip ttype parameter for break
991                                }
992
993                                if ( ! unifyExact(
994                                                pty, pty2, tenv, need, have, open, noWiden(), symtab ) ) {
995                                        result = false;
996                                        return;
997                                }
998
999                                // ttype parameter should be last
1000                                if ( isTuple || isTuple2 ) break;
1001                        }
1002                        result = it == params.end() && jt == params2.end();
1003                }
1004
1005        public:
1006                void postvisit( const ast::StructInstType * aggrType ) {
1007                        handleGenericRefType( aggrType, type2 );
1008                }
1009
1010                void postvisit( const ast::UnionInstType * aggrType ) {
1011                        handleGenericRefType( aggrType, type2 );
1012                }
1013
1014                void postvisit( const ast::EnumInstType * aggrType ) {
1015                        handleRefType( aggrType, type2 );
1016                }
1017
1018                void postvisit( const ast::TraitInstType * aggrType ) {
1019                        handleRefType( aggrType, type2 );
1020                }
1021
1022                void postvisit( const ast::TypeInstType * typeInst ) {
1023                        assert( open.find( typeInst->name ) == open.end() );
1024                        handleRefType( typeInst, type2 );
1025                }
1026
1027        private:
1028                /// Creates a tuple type based on a list of Type
1029                static ast::ptr< ast::Type > tupleFromTypes(
1030                        const std::vector< ast::ptr< ast::Type > > & tys
1031                ) {
1032                        std::vector< ast::ptr< ast::Type > > out;
1033                        for ( const ast::Type * ty : tys ) {
1034                                // it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure
1035                                // that this results in a flat tuple
1036                                flatten( ty, out );
1037                        }
1038
1039                        return { new ast::TupleType{ std::move(out) } };
1040                }
1041
1042                static bool unifyList(
1043                        const std::vector< ast::ptr< ast::Type > > & list1,
1044                        const std::vector< ast::ptr< ast::Type > > & list2, ast::TypeEnvironment & env,
1045                        ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
1046                        const ast::SymbolTable & symtab
1047                ) {
1048                        auto crnt1 = list1.begin();
1049                        auto crnt2 = list2.begin();
1050                        while ( crnt1 != list1.end() && crnt2 != list2.end() ) {
1051                                const ast::Type * t1 = *crnt1;
1052                                const ast::Type * t2 = *crnt2;
1053                                bool isTuple1 = Tuples::isTtype( t1 );
1054                                bool isTuple2 = Tuples::isTtype( t2 );
1055
1056                                // assumes ttype must be last parameter
1057                                if ( isTuple1 && ! isTuple2 ) {
1058                                        // combine entirety of list2, then unify
1059                                        return unifyExact(
1060                                                t1, tupleFromTypes( list2 ), env, need, have, open,
1061                                                noWiden(), symtab );
1062                                } else if ( ! isTuple1 && isTuple2 ) {
1063                                        // combine entirety of list1, then unify
1064                                        return unifyExact(
1065                                                tupleFromTypes( list1 ), t2, env, need, have, open,
1066                                                noWiden(), symtab );
1067                                }
1068
1069                                if ( ! unifyExact(
1070                                        t1, t2, env, need, have, open, noWiden(), symtab )
1071                                ) return false;
1072
1073                                ++crnt1; ++crnt2;
1074                        }
1075
1076                        if ( crnt1 != list1.end() ) {
1077                                // try unifying empty tuple type with ttype
1078                                const ast::Type * t1 = *crnt1;
1079                                if ( ! Tuples::isTtype( t1 ) ) return false;
1080                                // xxx - this doesn't generate an empty tuple, contrary to comment; both ported
1081                                // from Rob's code
1082                                return unifyExact(
1083                                                t1, tupleFromTypes( list2 ), env, need, have, open,
1084                                                noWiden(), symtab );
1085                        } else if ( crnt2 != list2.end() ) {
1086                                // try unifying empty tuple with ttype
1087                                const ast::Type * t2 = *crnt2;
1088                                if ( ! Tuples::isTtype( t2 ) ) return false;
1089                                // xxx - this doesn't generate an empty tuple, contrary to comment; both ported
1090                                // from Rob's code
1091                                return unifyExact(
1092                                                tupleFromTypes( list1 ), t2, env, need, have, open,
1093                                                noWiden(), symtab );
1094                        }
1095
1096                        return true;
1097                }
1098
1099        public:
1100                void postvisit( const ast::TupleType * tuple ) {
1101                        auto tuple2 = dynamic_cast< const ast::TupleType * >( type2 );
1102                        if ( ! tuple2 ) return;
1103
1104                        ast::Pass<TtypeExpander_new> expander{ tenv };
1105                        const ast::Type * flat = tuple->accept( expander );
1106                        const ast::Type * flat2 = tuple2->accept( expander );
1107
1108                        auto types = flatten( flat );
1109                        auto types2 = flatten( flat2 );
1110
1111                        result = unifyList( types, types2, tenv, need, have, open, symtab );
1112                }
1113
1114                void postvisit( const ast::VarArgsType * ) {
1115                        result = dynamic_cast< const ast::VarArgsType * >( type2 );
1116                }
1117
1118                void postvisit( const ast::ZeroType * ) {
1119                        result = dynamic_cast< const ast::ZeroType * >( type2 );
1120                }
1121
1122                void postvisit( const ast::OneType * ) {
1123                        result = dynamic_cast< const ast::OneType * >( type2 );
1124                }
1125
1126          private:
1127                template< typename RefType > void handleRefType( RefType *inst, Type *other );
1128                template< typename RefType > void handleGenericRefType( RefType *inst, Type *other );
1129        };
1130
1131        bool unify(
1132                        const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
1133                        ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
1134                        ast::OpenVarSet & open, const ast::SymbolTable & symtab
1135        ) {
1136                ast::ptr<ast::Type> common;
1137                return unify( type1, type2, env, need, have, open, symtab, common );
1138        }
1139
1140        bool unify(
1141                        const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
1142                        ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
1143                        ast::OpenVarSet & open, const ast::SymbolTable & symtab, ast::ptr<ast::Type> & common
1144        ) {
1145                ast::OpenVarSet closed;
1146                findOpenVars( type1, open, closed, need, have, FirstClosed );
1147                findOpenVars( type2, open, closed, need, have, FirstOpen );
1148                return unifyInexact(
1149                        type1, type2, env, need, have, open, WidenMode{ true, true }, symtab, common );
1150        }
1151
1152        bool unifyExact(
1153                        const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env,
1154                        ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
1155                        WidenMode widen, const ast::SymbolTable & symtab
1156        ) {
1157                if ( type1->qualifiers != type2->qualifiers ) return false;
1158
1159                auto var1 = dynamic_cast< const ast::TypeInstType * >( type1 );
1160                auto var2 = dynamic_cast< const ast::TypeInstType * >( type2 );
1161                ast::OpenVarSet::const_iterator
1162                        entry1 = var1 ? open.find( var1->name ) : open.end(),
1163                        entry2 = var2 ? open.find( var2->name ) : open.end();
1164                bool isopen1 = entry1 != open.end();
1165                bool isopen2 = entry2 != open.end();
1166
1167                if ( isopen1 && isopen2 ) {
1168                        if ( entry1->second.kind != entry2->second.kind ) return false;
1169                        return env.bindVarToVar(
1170                                var1, var2, ast::TypeDecl::Data{ entry1->second, entry2->second }, need, have,
1171                                open, widen, symtab );
1172                } else if ( isopen1 ) {
1173                        return env.bindVar( var1, type2, entry1->second, need, have, open, widen, symtab );
1174                } else if ( isopen2 ) {
1175                        return env.bindVar( var2, type1, entry2->second, need, have, open, widen, symtab );
1176                } else {
1177                        ast::Pass<Unify_new> comparator{ type2, env, need, have, open, widen, symtab };
1178                        type1->accept( comparator );
1179                        return comparator.pass.result;
1180                }
1181        }
1182
1183        bool unifyInexact(
1184                        const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
1185                        ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
1186                        const ast::OpenVarSet & open, WidenMode widen, const ast::SymbolTable & symtab,
1187                        ast::ptr<ast::Type> & common
1188        ) {
1189                ast::CV::Qualifiers q1 = type1->qualifiers, q2 = type2->qualifiers;
1190
1191                // force t1 and t2 to be cloned if their qualifiers must be stripped, so that type1 and
1192                // type2 are left unchanged; calling convention forces type{1,2}->strong_ref >= 1
1193                ast::Type * t1 = shallowCopy(type1.get());
1194                ast::Type * t2 = shallowCopy(type2.get());
1195                t1->qualifiers = {};
1196                t2->qualifiers = {};
1197                #warning memory leak
1198
1199                if ( unifyExact( t1, t2, env, need, have, open, widen, symtab ) ) {
1200                        // if exact unification on unqualified types, try to merge qualifiers
1201                        if ( q1 == q2 || ( ( q1 > q2 || widen.first ) && ( q2 > q1 || widen.second ) ) ) {
1202                                t1->qualifiers = q1 | q2;
1203                                common = t1;
1204                                return true;
1205                        } else {
1206                                return false;
1207                        }
1208
1209                } else if (( common = commonType( t1, t2, widen, symtab, env, open ) )) {
1210                        // no exact unification, but common type
1211                        auto c = shallowCopy(common.get());
1212                        c->qualifiers = q1 | q2;
1213                        common = c;
1214                        return true;
1215                } else {
1216                        return false;
1217                }
1218        }
1219
1220        ast::ptr<ast::Type> extractResultType( const ast::FunctionType * func ) {
1221                if ( func->returns.empty() ) return new ast::VoidType{};
1222                if ( func->returns.size() == 1 ) return func->returns[0]->get_type();
1223
1224                std::vector<ast::ptr<ast::Type>> tys;
1225                for ( const ast::DeclWithType * decl : func->returns ) {
1226                        tys.emplace_back( decl->get_type() );
1227                }
1228                return new ast::TupleType{ std::move(tys) };
1229        }
1230} // namespace ResolvExpr
1231
1232// Local Variables: //
1233// tab-width: 4 //
1234// mode: c++ //
1235// compile-command: "make install" //
1236// End: //
Note: See TracBrowser for help on using the repository browser.