source: src/ResolvExpr/Unify.cc @ d76c588

arm-ehjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-expr
Last change on this file since d76c588 was d76c588, checked in by Aaron Moss <a3moss@…>, 3 years ago

Stubs for new resolver, implementation of new indexer, type environment

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