source: src/ResolvExpr/Unify.cpp @ 822332e

Last change on this file since 822332e was 822332e, checked in by Andrew Beach <ajbeach@…>, 7 weeks ago

It seems clang uses different scoping rules for the trailing return of a scoped runction declaration. This form seems compatable with clang and gcc. Since I switched over to clang for testing I also cleaned up all errors that clang or gcc mentioned.

  • Property mode set to 100644
File size: 23.1 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 * ) {
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
406public:
407        void postvisit( const ast::FunctionType * func ) {
408                auto func2 = dynamic_cast< const ast::FunctionType * >( type2 );
409                if ( !func2 ) return;
410
411                if ( func->isVarArgs != func2->isVarArgs ) return;
412
413                // Flatten the parameter lists for both functions so that tuple structure does not
414                // affect unification. Does not actually mutate function parameters.
415                auto params = flattenList( func->params, tenv );
416                auto params2 = flattenList( func2->params, tenv );
417
418                // sizes don't have to match if ttypes are involved; need to be more precise w.r.t.
419                // where the ttype is to prevent errors
420                if (
421                        ( params.size() != params2.size() || func->returns.size() != func2->returns.size() )
422                        && !func->isTtype()
423                        && !func2->isTtype()
424                ) return;
425
426                if ( !unifyTypeList( params, params2, tenv, need, have, open ) ) return;
427                if ( !unifyTypeList(
428                        func->returns, func2->returns, tenv, need, have, open ) ) return;
429
430                markAssertions( have, need, func );
431                markAssertions( have, need, func2 );
432
433                result = true;
434        }
435
436private:
437        // Returns: other, cast as XInstType
438        // Assigns this->result: whether types are compatible (up to generic parameters)
439        template< typename XInstType >
440        const XInstType * handleRefType( const XInstType * inst, const ast::Type * other ) {
441                // check that the other type is compatible and named the same
442                auto otherInst = dynamic_cast< const XInstType * >( other );
443                if ( otherInst && inst->name == otherInst->name ) {
444                        this->result = otherInst;
445                }
446                return otherInst;
447        }
448
449        /// Creates a tuple type based on a list of TypeExpr
450        template< typename Iter >
451        static const ast::Type * tupleFromExprs(
452                const ast::TypeExpr * param, Iter & crnt, Iter end, ast::CV::Qualifiers qs
453        ) {
454                std::vector< ast::ptr< ast::Type > > types;
455                do {
456                        types.emplace_back( param->type );
457
458                        ++crnt;
459                        if ( crnt == end ) break;
460                        param = strict_dynamic_cast< const ast::TypeExpr * >( crnt->get() );
461                } while(true);
462
463                return new ast::TupleType( std::move(types), qs );
464        }
465
466        template< typename XInstType >
467        void handleGenericRefType( const XInstType * inst, const ast::Type * other ) {
468                // check that other type is compatible and named the same
469                const XInstType * otherInst = handleRefType( inst, other );
470                if ( !this->result ) return;
471
472                // check that parameters of types unify, if any
473                const std::vector< ast::ptr< ast::Expr > > & params = inst->params;
474                const std::vector< ast::ptr< ast::Expr > > & params2 = otherInst->params;
475
476                auto it = params.begin();
477                auto jt = params2.begin();
478                for ( ; it != params.end() && jt != params2.end(); ++it, ++jt ) {
479                        auto param = strict_dynamic_cast< const ast::TypeExpr * >( it->get() );
480                        auto param2 = strict_dynamic_cast< const ast::TypeExpr * >( jt->get() );
481
482                        ast::ptr< ast::Type > pty = param->type;
483                        ast::ptr< ast::Type > pty2 = param2->type;
484
485                        bool isTuple = Tuples::isTtype( pty );
486                        bool isTuple2 = Tuples::isTtype( pty2 );
487
488                        if ( isTuple && isTuple2 ) {
489                                ++it; ++jt;  // skip ttype parameters before break
490                        } else if ( isTuple ) {
491                                // bundle remaining params into tuple
492                                pty2 = tupleFromExprs( param2, jt, params2.end(), pty->qualifiers );
493                                ++it;  // skip ttype parameter for break
494                        } else if ( isTuple2 ) {
495                                // bundle remaining params into tuple
496                                pty = tupleFromExprs( param, it, params.end(), pty2->qualifiers );
497                                ++jt;  // skip ttype parameter for break
498                        }
499
500                        if ( !unifyExact(
501                                        pty, pty2, tenv, need, have, open, noWiden() ) ) {
502                                result = false;
503                                return;
504                        }
505
506                        // ttype parameter should be last
507                        if ( isTuple || isTuple2 ) break;
508                }
509                result = it == params.end() && jt == params2.end();
510        }
511
512public:
513        void postvisit( const ast::StructInstType * aggrType ) {
514                handleGenericRefType( aggrType, type2 );
515        }
516
517        void postvisit( const ast::UnionInstType * aggrType ) {
518                handleGenericRefType( aggrType, type2 );
519        }
520
521        void postvisit( const ast::EnumInstType * aggrType ) {
522                handleRefType( aggrType, type2 );
523        }
524
525        void postvisit( const ast::TraitInstType * aggrType ) {
526                handleRefType( aggrType, type2 );
527        }
528
529        void postvisit( const ast::TypeInstType * typeInst ) {
530                // assert( open.find( *typeInst ) == open.end() );
531                auto otherInst = dynamic_cast< const ast::TypeInstType * >( type2 );
532                if ( otherInst && typeInst->name == otherInst->name ) {
533                        this->result = otherInst;
534                }
535        }
536
537private:
538        /// Creates a tuple type based on a list of Type
539        static bool unifyList(
540                const std::vector< ast::ptr< ast::Type > > & list1,
541                const std::vector< ast::ptr< ast::Type > > & list2, ast::TypeEnvironment & env,
542                ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open
543        ) {
544                auto crnt1 = list1.begin();
545                auto crnt2 = list2.begin();
546                while ( crnt1 != list1.end() && crnt2 != list2.end() ) {
547                        const ast::Type * t1 = *crnt1;
548                        const ast::Type * t2 = *crnt2;
549                        bool isTuple1 = Tuples::isTtype( t1 );
550                        bool isTuple2 = Tuples::isTtype( t2 );
551
552                        // assumes ttype must be last parameter
553                        if ( isTuple1 && !isTuple2 ) {
554                                // combine entirety of list2, then unify
555                                return unifyExact(
556                                        t1, tupleFromTypes( list2 ), env, need, have, open,
557                                        noWiden() );
558                        } else if ( !isTuple1 && isTuple2 ) {
559                                // combine entirety of list1, then unify
560                                return unifyExact(
561                                        tupleFromTypes( list1 ), t2, env, need, have, open,
562                                        noWiden() );
563                        }
564
565                        if ( !unifyExact(
566                                t1, t2, env, need, have, open, noWiden() )
567                        ) return false;
568
569                        ++crnt1; ++crnt2;
570                }
571
572                if ( crnt1 != list1.end() ) {
573                        // try unifying empty tuple type with ttype
574                        const ast::Type * t1 = *crnt1;
575                        if ( !Tuples::isTtype( t1 ) ) return false;
576                        // xxx - this doesn't generate an empty tuple, contrary to comment; both ported
577                        // from Rob's code
578                        return unifyExact(
579                                        t1, tupleFromTypes( list2 ), env, need, have, open,
580                                        noWiden() );
581                } else if ( crnt2 != list2.end() ) {
582                        // try unifying empty tuple with ttype
583                        const ast::Type * t2 = *crnt2;
584                        if ( !Tuples::isTtype( t2 ) ) return false;
585                        // xxx - this doesn't generate an empty tuple, contrary to comment; both ported
586                        // from Rob's code
587                        return unifyExact(
588                                        tupleFromTypes( list1 ), t2, env, need, have, open,
589                                        noWiden() );
590                }
591
592                return true;
593        }
594
595public:
596        void postvisit( const ast::TupleType * tuple ) {
597                auto tuple2 = dynamic_cast< const ast::TupleType * >( type2 );
598                if ( ! tuple2 ) return;
599
600                ast::Pass<TtypeExpander> expander{ tenv };
601
602                const ast::Type * flat = tuple->accept( expander );
603                const ast::Type * flat2 = tuple2->accept( expander );
604
605                auto types = flatten( flat );
606                auto types2 = flatten( flat2 );
607
608                result = unifyList( types, types2, tenv, need, have, open );
609                        // || tryToUnifyWithEnumValue(tuple, type2, tenv, need, have, open, noWiden());
610        }
611
612        void postvisit( const ast::VarArgsType * ) {
613                result = dynamic_cast< const ast::VarArgsType * >( type2 );
614                        // || tryToUnifyWithEnumValue(vat, type2, tenv, need, have, open, noWiden());
615        }
616
617        void postvisit( const ast::ZeroType * ) {
618                result = dynamic_cast< const ast::ZeroType * >( type2 );
619                        // || tryToUnifyWithEnumValue(zt, type2, tenv, need, have, open, noWiden());
620        }
621
622        void postvisit( const ast::OneType * ) {
623                result = dynamic_cast< const ast::OneType * >( type2 );
624                        // || tryToUnifyWithEnumValue(ot, type2, tenv, need, have, open, noWiden());
625        }
626};
627
628// size_t Unify::traceId = Stats::Heap::new_stacktrace_id("Unify");
629
630bool unify(
631                const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
632                ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
633                ast::OpenVarSet & open
634) {
635        ast::ptr<ast::Type> common;
636        return unify( type1, type2, env, need, have, open, common );
637}
638
639bool unify(
640                const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
641                ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
642                ast::OpenVarSet & open, ast::ptr<ast::Type> & common
643) {
644        ast::OpenVarSet closed;
645        // findOpenVars( type1, open, closed, need, have, FirstClosed );
646        findOpenVars( type2, open, closed, need, have, env, FirstOpen );
647        return unifyInexact(
648                type1, type2, env, need, have, open, WidenMode{ true, true }, common );
649}
650
651bool unifyExact(
652                const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env,
653                ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
654                WidenMode widen
655) {
656        if ( type1->qualifiers != type2->qualifiers ) return false;
657
658        auto var1 = dynamic_cast< const ast::TypeInstType * >( type1 );
659        auto var2 = dynamic_cast< const ast::TypeInstType * >( type2 );
660        bool isopen1 = var1 && env.lookup(*var1);
661        bool isopen2 = var2 && env.lookup(*var2);
662
663        if ( isopen1 && isopen2 ) {
664                if ( var1->base->kind != var2->base->kind ) return false;
665                return env.bindVarToVar(
666                        var1, var2, ast::TypeData{ var1->base->kind, var1->base->sized||var2->base->sized }, need, have,
667                        open, widen );
668        } else if ( isopen1 ) {
669                return env.bindVar( var1, type2, ast::TypeData{var1->base}, need, have, open, widen );
670        } else if ( isopen2 ) {
671                return env.bindVar( var2, type1, ast::TypeData{var2->base}, need, have, open, widen );
672        } else {
673                return ast::Pass<Unify>::read(
674                        type1, type2, env, need, have, open, widen );
675        }
676}
677
678bool unifyInexact(
679                const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2,
680                ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have,
681                const ast::OpenVarSet & open, WidenMode widen,
682                ast::ptr<ast::Type> & common
683) {
684        ast::CV::Qualifiers q1 = type1->qualifiers, q2 = type2->qualifiers;
685
686        // force t1 and t2 to be cloned if their qualifiers must be stripped, so that type1 and
687        // type2 are left unchanged; calling convention forces type{1,2}->strong_ref >= 1
688        ast::Type * t1 = shallowCopy(type1.get());
689        ast::Type * t2 = shallowCopy(type2.get());
690        t1->qualifiers = {};
691        t2->qualifiers = {};
692        ast::ptr< ast::Type > t1_(t1);
693        ast::ptr< ast::Type > t2_(t2);
694
695        if ( unifyExact( t1, t2, env, need, have, open, widen ) ) {
696                // if exact unification on unqualified types, try to merge qualifiers
697                if ( q1 == q2 || ( ( q1 > q2 || widen.first ) && ( q2 > q1 || widen.second ) ) ) {
698                        t1->qualifiers = q1 | q2;
699                        common = t1;
700                        return true;
701                } else {
702                        return false;
703                }
704        } else if (( common = commonType( t1, t2, env, need, have, open, widen ))) {
705                // no exact unification, but common type
706                auto c = shallowCopy(common.get());
707                c->qualifiers = q1 | q2;
708                common = c;
709                return true;
710        } else {
711                return false;
712        }
713}
714
715ast::ptr<ast::Type> extractResultType( const ast::FunctionType * func ) {
716        if ( func->returns.empty() ) return new ast::VoidType();
717        if ( func->returns.size() == 1 ) return func->returns[0];
718
719        std::vector<ast::ptr<ast::Type>> tys;
720        for ( const auto & decl : func->returns ) {
721                tys.emplace_back( decl );
722        }
723        return new ast::TupleType( std::move(tys) );
724}
725
726} // namespace ResolvExpr
727
728// Local Variables: //
729// tab-width: 4 //
730// mode: c++ //
731// compile-command: "make install" //
732// End: //
Note: See TracBrowser for help on using the repository browser.