source: src/ResolvExpr/Unify.cpp @ c92bdcc

Last change on this file since c92bdcc was c92bdcc, checked in by Andrew Beach <ajbeach@…>, 5 months ago

Updated the rest of the names in src/ (except for the generated files).

  • Property mode set to 100644
File size: 24.4 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.cpp --
8//
9// Author           : Richard C. Bilson
10// Created On       : Sun May 17 12:27:10 2015
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Fri Dec 13 23:43:05 2019
13// Update Count     : 46
14//
15
16#include "Unify.hpp"
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/Eval.hpp"          // for eval
35#include "CommonType.hpp"           // for commonType
36#include "FindOpenVars.hpp"         // for findOpenVars
37#include "SpecCost.hpp"             // for SpecCost
38#include "Tuples/Tuples.hpp"        // for isTtype
39#include "Typeops.hpp"              // for flatten, occurs
40
41namespace ast {
42        class SymbolTable;
43}
44
45// #define DEBUG
46
47namespace ResolvExpr {
48
49bool typesCompatible(
50                const ast::Type * first, const ast::Type * second,
51                const ast::TypeEnvironment & env ) {
52        ast::TypeEnvironment newEnv;
53        ast::OpenVarSet open, closed;
54        ast::AssertionSet need, have;
55
56        ast::ptr<ast::Type> newFirst( first ), newSecond( second );
57        env.apply( newFirst );
58        env.apply( newSecond );
59
60        // findOpenVars( newFirst, open, closed, need, have, FirstClosed );
61        findOpenVars( newSecond, open, closed, need, have, newEnv, FirstOpen );
62
63        return unifyExact(newFirst, newSecond, newEnv, need, have, open, noWiden() );
64}
65
66bool typesCompatibleIgnoreQualifiers(
67                const ast::Type * first, const ast::Type * second,
68                const ast::TypeEnvironment & env ) {
69        ast::TypeEnvironment newEnv;
70        ast::OpenVarSet open;
71        ast::AssertionSet need, have;
72
73        ast::Type * newFirst  = shallowCopy( first  );
74        ast::Type * newSecond = shallowCopy( second );
75
76        newFirst ->qualifiers = {};
77        newSecond->qualifiers = {};
78        ast::ptr< ast::Type > t1_(newFirst );
79        ast::ptr< ast::Type > t2_(newSecond);
80
81        ast::ptr< ast::Type > subFirst = env.apply(newFirst).node;
82        ast::ptr< ast::Type > subSecond = env.apply(newSecond).node;
83
84        return unifyExact(
85                subFirst,
86                subSecond,
87                newEnv, need, have, open, noWiden() );
88}
89
90namespace {
91        /// Replaces ttype variables with their bound types.
92        /// If this isn't done when satifying ttype assertions, then argument lists can have
93        /// different size and structure when they should be compatible.
94        struct TtypeExpander : public ast::WithShortCircuiting, public ast::PureVisitor {
95                ast::TypeEnvironment & tenv;
96
97                TtypeExpander( ast::TypeEnvironment & env ) : tenv( env ) {}
98
99                const ast::Type * postvisit( const ast::TypeInstType * typeInst ) {
100                        if ( const ast::EqvClass * clz = tenv.lookup( *typeInst ) ) {
101                                // expand ttype parameter into its actual type
102                                if ( clz->data.kind == ast::TypeDecl::Ttype && clz->bound ) {
103                                        return clz->bound;
104                                }
105                        }
106                        return typeInst;
107                }
108        };
109}
110
111std::vector< ast::ptr< ast::Type > > flattenList(
112        const std::vector< ast::ptr< ast::Type > > & src, ast::TypeEnvironment & env
113) {
114        std::vector< ast::ptr< ast::Type > > dst;
115        dst.reserve( src.size() );
116        for ( const auto & d : src ) {
117                ast::Pass<TtypeExpander> expander( env );
118                // TtypeExpander pass is impure (may mutate nodes in place)
119                // need to make nodes shared to prevent accidental mutation
120                ast::ptr<ast::Type> dc = d->accept(expander);
121                auto types = flatten( dc );
122                for ( ast::ptr< ast::Type > & t : types ) {
123                        // outermost const, volatile, _Atomic qualifiers in parameters should not play
124                        // a role in the unification of function types, since they do not determine
125                        // whether a function is callable.
126                        // NOTE: **must** consider at least mutex qualifier, since functions can be
127                        // overloaded on outermost mutex and a mutex function has different
128                        // requirements than a non-mutex function
129                        remove_qualifiers( t, ast::CV::Const | ast::CV::Volatile | ast::CV::Atomic );
130                        dst.emplace_back( t );
131                }
132        }
133        return dst;
134}
135
136// Unification of Expressions
137//
138// Boolean outcome (obvious):  Are they basically spelled the same?
139// Side effect of binding variables (subtle):  if `sizeof(int)` ===_expr `sizeof(T)` then `int` ===_ty `T`
140//
141// Context:  if `float[VAREXPR1]` ===_ty `float[VAREXPR2]` then `VAREXPR1` ===_expr `VAREXPR2`
142// where the VAREXPR are meant as notational metavariables representing the fact that unification always
143// sees distinct ast::VariableExpr objects at these positions
144
145static bool unify( const ast::Expr * e1, const ast::Expr * e2, ast::TypeEnvironment & env,
146        ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
147        WidenMode widen );
148
149class UnifyExpr final : public ast::WithShortCircuiting {
150        const ast::Expr * e2;
151        ast::TypeEnvironment & tenv;
152        ast::AssertionSet & need;
153        ast::AssertionSet & have;
154        const ast::OpenVarSet & open;
155        WidenMode widen;
156public:
157        bool result;
158
159private:
160
161        void tryMatchOnStaticValue( const ast::Expr * e1 ) {
162                Evaluation r1 = eval(e1);
163                Evaluation r2 = eval(e2);
164
165                if ( !r1.hasKnownValue ) return;
166                if ( !r2.hasKnownValue ) return;
167
168                if ( r1.knownValue != r2.knownValue ) return;
169
170                visit_children = false;
171                result = true;
172        }
173
174public:
175
176        void previsit( const ast::Node * ) { assert(false); }
177
178        void previsit( const ast::Expr * e1 ) {
179                tryMatchOnStaticValue( e1 );
180                visit_children = false;
181        }
182
183        void previsit( const ast::CastExpr * e1 ) {
184                tryMatchOnStaticValue( e1 );
185
186                if ( result ) {
187                        assert( visit_children == false );
188                } else {
189                        assert( visit_children == true );
190                        visit_children = false;
191
192                        auto e2c = dynamic_cast< const ast::CastExpr * >( e2 );
193                        if ( !e2c ) return;
194
195                        // inspect casts' target types
196                        if ( !unifyExact(
197                                e1->result, e2c->result, tenv, need, have, open, widen ) ) return;
198
199                        // inspect casts' inner expressions
200                        result = unify( e1->arg, e2c->arg, tenv, need, have, open, widen );
201                }
202        }
203
204        void previsit( const ast::VariableExpr * e1 ) {
205                tryMatchOnStaticValue( e1 );
206
207                if ( result ) {
208                        assert( visit_children == false );
209                } else {
210                        assert( visit_children == true );
211                        visit_children = false;
212
213                        auto e2v = dynamic_cast< const ast::VariableExpr * >( e2 );
214                        if ( !e2v ) return;
215
216                        assert(e1->var);
217                        assert(e2v->var);
218
219                        // conservative: variable exprs match if their declarations are represented by the same C++ AST object
220                        result = (e1->var == e2v->var);
221                }
222        }
223
224        void previsit( const ast::SizeofExpr * e1 ) {
225                tryMatchOnStaticValue( e1 );
226
227                if ( result ) {
228                        assert( visit_children == false );
229                } else {
230                        assert( visit_children == true );
231                        visit_children = false;
232
233                        auto e2so = dynamic_cast< const ast::SizeofExpr * >( e2 );
234                        if ( !e2so ) return;
235
236                        assert((e1->type != nullptr) ^ (e1->expr != nullptr));
237                        assert((e2so->type != nullptr) ^ (e2so->expr != nullptr));
238                        if ( !(e1->type && e2so->type) ) return;
239
240                        // expression unification calls type unification (mutual recursion)
241                        result = unifyExact( e1->type, e2so->type, tenv, need, have, open, widen );
242                }
243        }
244
245        UnifyExpr( const ast::Expr * e2, ast::TypeEnvironment & env, ast::AssertionSet & need,
246                ast::AssertionSet & have, const ast::OpenVarSet & open, WidenMode widen )
247        : e2( e2 ), tenv(env), need(need), have(have), open(open), widen(widen), result(false) {}
248};
249
250static bool unify( const ast::Expr * e1, const ast::Expr * e2, ast::TypeEnvironment & env,
251        ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
252        WidenMode widen ) {
253        assert( e1 && e2 );
254        return ast::Pass<UnifyExpr>::read( e1, e2, env, need, have, open, widen );
255}
256
257class Unify final : public ast::WithShortCircuiting {
258        const ast::Type * type2;
259        ast::TypeEnvironment & tenv;
260        ast::AssertionSet & need;
261        ast::AssertionSet & have;
262        const ast::OpenVarSet & open;
263        WidenMode widen;
264public:
265        static size_t traceId;
266        bool result;
267
268        Unify(
269                const ast::Type * type2, ast::TypeEnvironment & env, ast::AssertionSet & need,
270                ast::AssertionSet & have, const ast::OpenVarSet & open, WidenMode widen )
271        : type2(type2), tenv(env), need(need), have(have), open(open), widen(widen),
272        result(false) {}
273
274        void previsit( const ast::Node * ) { visit_children = false; }
275
276        void postvisit( const ast::VoidType * vt) {
277                result = dynamic_cast< const ast::VoidType * >( type2 )
278                        || tryToUnifyWithEnumValue(vt, type2, tenv, need, have, open, noWiden());
279                ;
280        }
281
282        void postvisit( const ast::BasicType * basic ) {
283                if ( auto basic2 = dynamic_cast< const ast::BasicType * >( type2 ) ) {
284                        result = basic->kind == basic2->kind;
285                }
286                result = result || tryToUnifyWithEnumValue(basic, type2, tenv, need, have, open, noWiden());
287        }
288
289        void postvisit( const ast::PointerType * pointer ) {
290                if ( auto pointer2 = dynamic_cast< const ast::PointerType * >( type2 ) ) {
291                        result = unifyExact(
292                                pointer->base, pointer2->base, tenv, need, have, open,
293                                noWiden());
294                }
295                result = result || tryToUnifyWithEnumValue(pointer, type2, tenv, need, have, open, noWiden());
296        }
297
298        void postvisit( const ast::ArrayType * array ) {
299                auto array2 = dynamic_cast< const ast::ArrayType * >( type2 );
300                if ( !array2 ) return;
301
302                if ( array->isVarLen != array2->isVarLen ) return;
303                if ( (array->dimension != nullptr) != (array2->dimension != nullptr) ) return;
304
305                if ( array->dimension ) {
306                        assert( array2->dimension );
307                        // type unification calls expression unification (mutual recursion)
308                        if ( !unify(array->dimension, array2->dimension,
309                                tenv, need, have, open, widen) ) return;
310                }
311
312                result = unifyExact(
313                        array->base, array2->base, tenv, need, have, open, noWiden())
314                        || tryToUnifyWithEnumValue(array, type2, tenv, need, have, open, noWiden());
315        }
316
317        void postvisit( const ast::ReferenceType * ref ) {
318                if ( auto ref2 = dynamic_cast< const ast::ReferenceType * >( type2 ) ) {
319                        result = unifyExact(
320                                ref->base, ref2->base, tenv, need, have, open, noWiden());
321                }
322        }
323
324private:
325
326        template< typename Iter >
327        static bool unifyTypeList(
328                Iter crnt1, Iter end1, Iter crnt2, Iter end2, ast::TypeEnvironment & env,
329                ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open
330        ) {
331                while ( crnt1 != end1 && crnt2 != end2 ) {
332                        const ast::Type * t1 = *crnt1;
333                        const ast::Type * t2 = *crnt2;
334                        bool isTuple1 = Tuples::isTtype( t1 );
335                        bool isTuple2 = Tuples::isTtype( t2 );
336
337                        // assumes here that ttype *must* be last parameter
338                        if ( isTuple1 && !isTuple2 ) {
339                                // combine remainder of list2, then unify
340                                return unifyExact(
341                                        t1, tupleFromTypes( crnt2, end2 ), env, need, have, open,
342                                        noWiden() );
343                        } else if ( !isTuple1 && isTuple2 ) {
344                                // combine remainder of list1, then unify
345                                return unifyExact(
346                                        tupleFromTypes( crnt1, end1 ), t2, env, need, have, open,
347                                        noWiden() );
348                        }
349
350                        if ( !unifyExact(
351                                t1, t2, env, need, have, open, noWiden() )
352                        ) return false;
353
354                        ++crnt1; ++crnt2;
355                }
356
357                // May get to the end of one argument list before the other. This is only okay if the
358                // other is a ttype
359                if ( crnt1 != end1 ) {
360                        // try unifying empty tuple with ttype
361                        const ast::Type * t1 = *crnt1;
362                        if ( !Tuples::isTtype( t1 ) ) return false;
363                        return unifyExact(
364                                t1, tupleFromTypes( crnt2, end2 ), env, need, have, open,
365                                noWiden() );
366                } else if ( crnt2 != end2 ) {
367                        // try unifying empty tuple with ttype
368                        const ast::Type * t2 = *crnt2;
369                        if ( !Tuples::isTtype( t2 ) ) return false;
370                        return unifyExact(
371                                tupleFromTypes( crnt1, end1 ), t2, env, need, have, open,
372                                noWiden() );
373                }
374
375                return true;
376        }
377
378        static bool unifyTypeList(
379                const std::vector< ast::ptr< ast::Type > > & list1,
380                const std::vector< ast::ptr< ast::Type > > & list2,
381                ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
382                const ast::OpenVarSet & open
383        ) {
384                return unifyTypeList(
385                        list1.begin(), list1.end(), list2.begin(), list2.end(), env, need, have, open);
386        }
387
388        static void markAssertionSet( ast::AssertionSet & assns, const ast::VariableExpr * assn ) {
389                auto i = assns.find( assn );
390                if ( i != assns.end() ) {
391                        i->second.isUsed = true;
392                }
393        }
394
395        /// mark all assertions in `type` used in both `assn1` and `assn2`
396        static void markAssertions(
397                ast::AssertionSet & assn1, ast::AssertionSet & assn2,
398                const ast::FunctionType * type
399        ) {
400                for ( auto & assert : type->assertions ) {
401                        markAssertionSet( assn1, assert );
402                        markAssertionSet( assn2, assert );
403                }
404        }
405
406        bool tryToUnifyWithEnumValue( const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env,
407                ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
408                WidenMode widen) {
409                if ( auto attrType2 = dynamic_cast<const ast::EnumAttrType *>(type2)) {
410                        if (attrType2->attr == ast::EnumAttribute::Value) {
411                                return unifyExact( type1, attrType2->instance->base->base, env, need, have, open,
412                                        widen);
413                        } else if (attrType2->attr == ast::EnumAttribute::Posn) {
414                                return unifyExact( type1, attrType2->instance, env, need, have, open, widen );
415                        }
416                }
417                return false;
418        }
419
420public:
421        void postvisit( const ast::FunctionType * func ) {
422                auto func2 = dynamic_cast< const ast::FunctionType * >( type2 );
423                if ( !func2 ) return;
424
425                if ( func->isVarArgs != func2->isVarArgs ) return;
426
427                // Flatten the parameter lists for both functions so that tuple structure does not
428                // affect unification. Does not actually mutate function parameters.
429                auto params = flattenList( func->params, tenv );
430                auto params2 = flattenList( func2->params, tenv );
431
432                // sizes don't have to match if ttypes are involved; need to be more precise w.r.t.
433                // where the ttype is to prevent errors
434                if (
435                        ( params.size() != params2.size() || func->returns.size() != func2->returns.size() )
436                        && !func->isTtype()
437                        && !func2->isTtype()
438                ) return;
439
440                if ( !unifyTypeList( params, params2, tenv, need, have, open ) ) return;
441                if ( !unifyTypeList(
442                        func->returns, func2->returns, tenv, need, have, open ) ) return;
443
444                markAssertions( have, need, func );
445                markAssertions( have, need, func2 );
446
447                result = true;
448        }
449
450private:
451        // Returns: other, cast as XInstType
452        // Assigns this->result: whether types are compatible (up to generic parameters)
453        template< typename XInstType >
454        const XInstType * handleRefType( const XInstType * inst, const ast::Type * other ) {
455                // check that the other type is compatible and named the same
456                auto otherInst = dynamic_cast< const XInstType * >( other );
457                if ( otherInst && inst->name == otherInst->name ) {
458                        this->result = otherInst;
459                }
460                return otherInst;
461        }
462
463        /// Creates a tuple type based on a list of TypeExpr
464        template< typename Iter >
465        static const ast::Type * tupleFromExprs(
466                const ast::TypeExpr * param, Iter & crnt, Iter end, ast::CV::Qualifiers qs
467        ) {
468                std::vector< ast::ptr< ast::Type > > types;
469                do {
470                        types.emplace_back( param->type );
471
472                        ++crnt;
473                        if ( crnt == end ) break;
474                        param = strict_dynamic_cast< const ast::TypeExpr * >( crnt->get() );
475                } while(true);
476
477                return new ast::TupleType( std::move(types), qs );
478        }
479
480        template< typename XInstType >
481        void handleGenericRefType( const XInstType * inst, const ast::Type * other ) {
482                // check that other type is compatible and named the same
483                const XInstType * otherInst = handleRefType( inst, other );
484                if ( !this->result ) return;
485
486                // check that parameters of types unify, if any
487                const std::vector< ast::ptr< ast::Expr > > & params = inst->params;
488                const std::vector< ast::ptr< ast::Expr > > & params2 = otherInst->params;
489
490                auto it = params.begin();
491                auto jt = params2.begin();
492                for ( ; it != params.end() && jt != params2.end(); ++it, ++jt ) {
493                        auto param = strict_dynamic_cast< const ast::TypeExpr * >( it->get() );
494                        auto param2 = strict_dynamic_cast< const ast::TypeExpr * >( jt->get() );
495
496                        ast::ptr< ast::Type > pty = param->type;
497                        ast::ptr< ast::Type > pty2 = param2->type;
498
499                        bool isTuple = Tuples::isTtype( pty );
500                        bool isTuple2 = Tuples::isTtype( pty2 );
501
502                        if ( isTuple && isTuple2 ) {
503                                ++it; ++jt;  // skip ttype parameters before break
504                        } else if ( isTuple ) {
505                                // bundle remaining params into tuple
506                                pty2 = tupleFromExprs( param2, jt, params2.end(), pty->qualifiers );
507                                ++it;  // skip ttype parameter for break
508                        } else if ( isTuple2 ) {
509                                // bundle remaining params into tuple
510                                pty = tupleFromExprs( param, it, params.end(), pty2->qualifiers );
511                                ++jt;  // skip ttype parameter for break
512                        }
513
514                        if ( !unifyExact(
515                                        pty, pty2, tenv, need, have, open, noWiden() ) ) {
516                                result = false;
517                                return;
518                        }
519
520                        // ttype parameter should be last
521                        if ( isTuple || isTuple2 ) break;
522                }
523                result = it == params.end() && jt == params2.end();
524        }
525
526public:
527        void postvisit( const ast::StructInstType * aggrType ) {
528                handleGenericRefType( aggrType, type2 );
529                result = result || tryToUnifyWithEnumValue(aggrType, type2, tenv, need, have, open, noWiden());
530        }
531
532        void postvisit( const ast::UnionInstType * aggrType ) {
533                handleGenericRefType( aggrType, type2 );
534                result = result || tryToUnifyWithEnumValue(aggrType, type2, tenv, need, have, open, noWiden());
535        }
536
537        void postvisit( const ast::EnumInstType * aggrType ) {
538                handleRefType( aggrType, type2 );
539                result = result || tryToUnifyWithEnumValue(aggrType, type2, tenv, need, have, open, noWiden());
540        }
541
542        void postvisit( const ast::EnumAttrType * enumAttr ) {
543                // Lazy approach for now
544                if ( auto otherPos = dynamic_cast< const ast::EnumAttrType *>( type2 ) ) {
545                        if ( enumAttr->match(otherPos) ) {
546                                result = otherPos;
547                        }
548                }
549        }
550
551        void postvisit( const ast::TraitInstType * aggrType ) {
552                handleRefType( aggrType, type2 );
553                result = result || tryToUnifyWithEnumValue(aggrType, type2, tenv, need, have, open, noWiden());
554        }
555
556        void postvisit( const ast::TypeInstType * typeInst ) {
557                // assert( open.find( *typeInst ) == open.end() );
558                auto otherInst = dynamic_cast< const ast::TypeInstType * >( type2 );
559                if ( otherInst && typeInst->name == otherInst->name ) {
560                        this->result = otherInst;
561                }
562                result = result || tryToUnifyWithEnumValue(typeInst, type2, tenv, need, have, open, noWiden());
563        }
564
565private:
566        /// Creates a tuple type based on a list of Type
567        static bool unifyList(
568                const std::vector< ast::ptr< ast::Type > > & list1,
569                const std::vector< ast::ptr< ast::Type > > & list2, ast::TypeEnvironment & env,
570                ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open
571        ) {
572                auto crnt1 = list1.begin();
573                auto crnt2 = list2.begin();
574                while ( crnt1 != list1.end() && crnt2 != list2.end() ) {
575                        const ast::Type * t1 = *crnt1;
576                        const ast::Type * t2 = *crnt2;
577                        bool isTuple1 = Tuples::isTtype( t1 );
578                        bool isTuple2 = Tuples::isTtype( t2 );
579
580                        // assumes ttype must be last parameter
581                        if ( isTuple1 && !isTuple2 ) {
582                                // combine entirety of list2, then unify
583                                return unifyExact(
584                                        t1, tupleFromTypes( list2 ), env, need, have, open,
585                                        noWiden() );
586                        } else if ( !isTuple1 && isTuple2 ) {
587                                // combine entirety of list1, then unify
588                                return unifyExact(
589                                        tupleFromTypes( list1 ), t2, env, need, have, open,
590                                        noWiden() );
591                        }
592
593                        if ( !unifyExact(
594                                t1, t2, env, need, have, open, noWiden() )
595                        ) return false;
596
597                        ++crnt1; ++crnt2;
598                }
599
600                if ( crnt1 != list1.end() ) {
601                        // try unifying empty tuple type with ttype
602                        const ast::Type * t1 = *crnt1;
603                        if ( !Tuples::isTtype( t1 ) ) return false;
604                        // xxx - this doesn't generate an empty tuple, contrary to comment; both ported
605                        // from Rob's code
606                        return unifyExact(
607                                        t1, tupleFromTypes( list2 ), env, need, have, open,
608                                        noWiden() );
609                } else if ( crnt2 != list2.end() ) {
610                        // try unifying empty tuple with ttype
611                        const ast::Type * t2 = *crnt2;
612                        if ( !Tuples::isTtype( t2 ) ) return false;
613                        // xxx - this doesn't generate an empty tuple, contrary to comment; both ported
614                        // from Rob's code
615                        return unifyExact(
616                                        tupleFromTypes( list1 ), t2, env, need, have, open,
617                                        noWiden() );
618                }
619
620                return true;
621        }
622
623public:
624        void postvisit( const ast::TupleType * tuple ) {
625                auto tuple2 = dynamic_cast< const ast::TupleType * >( type2 );
626                if ( ! tuple2 ) return;
627
628                ast::Pass<TtypeExpander> expander{ tenv };
629
630                const ast::Type * flat = tuple->accept( expander );
631                const ast::Type * flat2 = tuple2->accept( expander );
632
633                auto types = flatten( flat );
634                auto types2 = flatten( flat2 );
635
636                result = unifyList( types, types2, tenv, need, have, open )
637                        || tryToUnifyWithEnumValue(tuple, type2, tenv, need, have, open, noWiden());
638        }
639
640        void postvisit( const ast::VarArgsType * vat) {
641                result = dynamic_cast< const ast::VarArgsType * >( type2 )
642                        || tryToUnifyWithEnumValue(vat, type2, tenv, need, have, open, noWiden());
643        }
644
645        void postvisit( const ast::ZeroType * zt) {
646                result = dynamic_cast< const ast::ZeroType * >( type2 )
647                        || tryToUnifyWithEnumValue(zt, type2, tenv, need, have, open, noWiden());
648        }
649
650        void postvisit( const ast::OneType * ot) {
651                result = dynamic_cast< const ast::OneType * >( type2 )
652                        || tryToUnifyWithEnumValue(ot, type2, tenv, need, have, open, noWiden());
653        }
654};
655
656// size_t Unify::traceId = Stats::Heap::new_stacktrace_id("Unify");
657
658bool unify(
659                const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
660                ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
661                ast::OpenVarSet & open
662) {
663        ast::ptr<ast::Type> common;
664        return unify( type1, type2, env, need, have, open, common );
665}
666
667bool unify(
668                const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
669                ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
670                ast::OpenVarSet & open, ast::ptr<ast::Type> & common
671) {
672        ast::OpenVarSet closed;
673        // findOpenVars( type1, open, closed, need, have, FirstClosed );
674        findOpenVars( type2, open, closed, need, have, env, FirstOpen );
675        return unifyInexact(
676                type1, type2, env, need, have, open, WidenMode{ true, true }, common );
677}
678
679bool unifyExact(
680                const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env,
681                ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
682                WidenMode widen
683) {
684        if ( type1->qualifiers != type2->qualifiers ) return false;
685
686        auto var1 = dynamic_cast< const ast::TypeInstType * >( type1 );
687        auto var2 = dynamic_cast< const ast::TypeInstType * >( type2 );
688        bool isopen1 = var1 && env.lookup(*var1);
689        bool isopen2 = var2 && env.lookup(*var2);
690
691        if ( isopen1 && isopen2 ) {
692                if ( var1->base->kind != var2->base->kind ) return false;
693                return env.bindVarToVar(
694                        var1, var2, ast::TypeData{ var1->base->kind, var1->base->sized||var2->base->sized }, need, have,
695                        open, widen );
696        } else if ( isopen1 ) {
697                return env.bindVar( var1, type2, ast::TypeData{var1->base}, need, have, open, widen );
698        } else if ( isopen2 ) {
699                return env.bindVar( var2, type1, ast::TypeData{var2->base}, need, have, open, widen );
700        } else {
701                return ast::Pass<Unify>::read(
702                        type1, type2, env, need, have, open, widen );
703        }
704}
705
706bool unifyInexact(
707                const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
708                ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
709                const ast::OpenVarSet & open, WidenMode widen,
710                ast::ptr<ast::Type> & common
711) {
712        ast::CV::Qualifiers q1 = type1->qualifiers, q2 = type2->qualifiers;
713
714        // force t1 and t2 to be cloned if their qualifiers must be stripped, so that type1 and
715        // type2 are left unchanged; calling convention forces type{1,2}->strong_ref >= 1
716        ast::Type * t1 = shallowCopy(type1.get());
717        ast::Type * t2 = shallowCopy(type2.get());
718        t1->qualifiers = {};
719        t2->qualifiers = {};
720        ast::ptr< ast::Type > t1_(t1);
721        ast::ptr< ast::Type > t2_(t2);
722
723        if ( unifyExact( t1, t2, env, need, have, open, widen ) ) {
724                // if exact unification on unqualified types, try to merge qualifiers
725                if ( q1 == q2 || ( ( q1 > q2 || widen.first ) && ( q2 > q1 || widen.second ) ) ) {
726                        t1->qualifiers = q1 | q2;
727                        common = t1;
728                        return true;
729                } else {
730                        return false;
731                }
732        } else if (( common = commonType( t1, t2, env, need, have, open, widen ))) {
733                // no exact unification, but common type
734                auto c = shallowCopy(common.get());
735                c->qualifiers = q1 | q2;
736                common = c;
737                return true;
738        } else {
739                return false;
740        }
741}
742
743ast::ptr<ast::Type> extractResultType( const ast::FunctionType * func ) {
744        if ( func->returns.empty() ) return new ast::VoidType();
745        if ( func->returns.size() == 1 ) return func->returns[0];
746
747        std::vector<ast::ptr<ast::Type>> tys;
748        for ( const auto & decl : func->returns ) {
749                tys.emplace_back( decl );
750        }
751        return new ast::TupleType( std::move(tys) );
752}
753
754} // namespace ResolvExpr
755
756// Local Variables: //
757// tab-width: 4 //
758// mode: c++ //
759// compile-command: "make install" //
760// End: //
Note: See TracBrowser for help on using the repository browser.