source: src/AST/TypeEnvironment.cpp @ 361bf01

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since 361bf01 was 361bf01, checked in by Fangren Yu <f37yu@…>, 11 months ago

remove ParameterizedType? and put content into FunctionType?

  • Property mode set to 100644
File size: 13.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// TypeEnvironment.cpp --
8//
9// Author           : Aaron B. Moss
10// Created On       : Wed May 29 11:00:00 2019
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Wed Dec 11 21:49:13 2019
13// Update Count     : 4
14//
15
16#include "TypeEnvironment.hpp"
17
18#include <algorithm>  // for copy
19#include <cassert>
20#include <iterator>   // for ostream_iterator
21#include <iostream>
22#include <string>
23#include <utility>    // for move
24#include <vector>
25
26#include "Decl.hpp"
27#include "Node.hpp"
28#include "Pass.hpp"
29#include "Print.hpp"
30#include "Type.hpp"
31#include "Common/Indenter.h"
32#include "ResolvExpr/typeops.h"    // for occurs
33#include "ResolvExpr/WidenMode.h"
34#include "ResolvExpr/Unify.h"      // for unifyInexact
35#include "Tuples/Tuples.h"         // for isTtype
36#include "CompilationState.h"
37
38using ResolvExpr::WidenMode;
39
40namespace ast {
41
42void print( std::ostream & out, const AssertionSet & assns, Indenter indent ) {
43        for ( const auto & i : assns ) {
44                print( out, i.first, indent );
45                out << ( i.second.isUsed ? " (used)" : " (not used)" );
46        }
47}
48
49void print( std::ostream & out, const OpenVarSet & open, Indenter indent ) {
50        out << indent;
51        bool first = true;
52        for ( const auto & i : open ) {
53                if ( first ) { first = false; } else { out << ' '; }
54                out << i.first << "(" << i.second << ")";
55        }
56}
57
58void print( std::ostream & out, const EqvClass & clz, Indenter indent ) {
59        out << "(";
60        bool first = true;
61        for(const auto & var : clz.vars) {
62                if(first) first = false;
63                else out << " ";
64                if( deterministic_output && isUnboundType(var) ) out << "[unbound]";
65                else out << var;
66        }
67        out << ")";
68
69        if ( clz.bound ) {
70                out << " -> ";
71                print( out, clz.bound, indent+1 );
72        }
73
74        if ( ! clz.allowWidening ) {
75                out << " (no widening)";
76        }
77
78        out << std::endl;
79}
80
81const EqvClass * TypeEnvironment::lookup( const std::string & var ) const {
82        for ( ClassList::const_iterator i = env.begin(); i != env.end(); ++i ) {
83                if ( i->vars.find( var ) != i->vars.end() ) return &*i;
84        }
85        return nullptr;
86}
87
88namespace {
89        /// Removes any class from env that intersects eqvClass
90        void filterOverlappingClasses( std::list<EqvClass> & env, const EqvClass & eqvClass ) {
91                auto i = env.begin();
92                while ( i != env.end() ) {
93                        auto next = i; ++next;  // save next node in case of erasure
94
95                        for ( const auto & v : eqvClass.vars ) {
96                                if ( i->vars.count( v ) ) {
97                                        env.erase( i );  // remove overlapping class
98                                        break;           // done with this class
99                                }
100                        }
101
102                        i = next;  // go to next node even if this removed
103                }
104        }
105}
106
107void TypeEnvironment::add( const FunctionType::ForallList & tyDecls ) {
108        for ( const TypeDecl * tyDecl : tyDecls ) {
109                env.emplace_back( tyDecl );
110        }
111}
112
113void TypeEnvironment::add( const TypeSubstitution & sub ) {
114        for ( const auto p : sub ) {
115                add( EqvClass{ p.first, p.second } );
116        }
117}
118
119void TypeEnvironment::writeToSubstitution( TypeSubstitution & sub ) const {
120        for ( const auto & clz : env ) {
121                std::string clzRep;
122                for ( const auto & var : clz.vars ) {
123                        if ( clz.bound ) {
124                                sub.add( var, clz.bound );
125                        } else if ( clzRep.empty() ) {
126                                clzRep = var;
127                        } else {
128                                sub.add( var, new TypeInstType{ clzRep, clz.data.kind } );
129                        }
130                }
131        }
132        sub.normalize();
133}
134
135void TypeEnvironment::simpleCombine( const TypeEnvironment & o ) {
136        env.insert( env.end(), o.env.begin(), o.env.end() );
137}
138
139namespace {
140        /// Implements occurs check by traversing type
141        struct Occurs : public ast::WithVisitorRef<Occurs> {
142                bool result;
143                std::set< std::string > vars;
144                const TypeEnvironment & tenv;
145
146                Occurs( const std::string & var, const TypeEnvironment & env )
147                : result( false ), vars(), tenv( env ) {
148                        if ( const EqvClass * clz = tenv.lookup( var ) ) {
149                                vars = clz->vars;
150                        } else {
151                                vars.emplace( var );
152                        }
153                }
154
155                void previsit( const TypeInstType * typeInst ) {
156                        if ( vars.count( typeInst->name ) ) {
157                                result = true;
158                        } else if ( const EqvClass * clz = tenv.lookup( typeInst->name ) ) {
159                                if ( clz->bound ) {
160                                        clz->bound->accept( *visitor );
161                                }
162                        }
163                }
164        };
165
166        /// true if `var` occurs in `ty` under `env`
167        bool occurs( const Type * ty, const std::string & var, const TypeEnvironment & env ) {
168                Pass<Occurs> occur{ var, env };
169                maybe_accept( ty, occur );
170                return occur.core.result;
171        }
172}
173
174bool TypeEnvironment::combine(
175                const TypeEnvironment & o, OpenVarSet & open, const SymbolTable & symtab ) {
176        // short-circuit easy cases
177        if ( o.empty() ) return true;
178        if ( empty() ) {
179                simpleCombine( o );
180                return true;
181        }
182
183        // merge classes
184        for ( const EqvClass & c : o.env ) {
185                // index of typeclass in local environment bound to c
186                auto rt = env.end();
187
188                // look for first existing bound variable
189                auto vt = c.vars.begin();
190                for ( ; vt != c.vars.end(); ++vt ) {
191                        rt = internal_lookup( *vt );
192                        if ( rt != env.end() ) break;
193                }
194
195                if ( rt != env.end() ) {  // c needs to be merged into *rt
196                        EqvClass & r = *rt;
197                        // merge bindings
198                        if ( ! mergeBound( r, c, open, symtab ) ) return false;
199                        // merge previous unbound variables into this class, checking occurs if needed
200                        if ( r.bound ) for ( const auto & u : c.vars ) {
201                                if ( occurs( r.bound, u, *this ) ) return false;
202                                r.vars.emplace( u );
203                        } else { r.vars.insert( c.vars.begin(), vt ); }
204                        // merge subsequent variables into this class (skipping *vt, already there)
205                        while ( ++vt != c.vars.end() ) {
206                                auto st = internal_lookup( *vt );
207                                if ( st == env.end() ) {
208                                        // unbound, safe to add if occurs
209                                        if ( r.bound && occurs( r.bound, *vt, *this ) ) return false;
210                                        r.vars.emplace( *vt );
211                                } else if ( st != rt ) {
212                                        // bound, but not to the same class
213                                        if ( ! mergeClasses( rt, st, open, symtab ) ) return false;
214                                }       // ignore bound into the same class
215                        }
216                } else {  // no variables in c bound; just copy up
217                        env.emplace_back( c );
218                }
219        }
220
221        // merged all classes
222        return true;
223}
224
225void TypeEnvironment::extractOpenVars( OpenVarSet & open ) const {
226        for ( const auto & clz : env ) {
227                for ( const auto & var : clz.vars ) {
228                        open[ var ] = clz.data;
229                }
230        }
231}
232
233void TypeEnvironment::addActual( const TypeEnvironment & actualEnv, OpenVarSet & open ) {
234        for ( const auto & clz : actualEnv ) {
235                EqvClass c = clz;
236                c.allowWidening = false;
237                for ( const auto & var : c.vars ) {
238                        open[ var ] = c.data;
239                }
240                env.emplace_back( std::move(c) );
241        }
242}
243
244/// true if a type is a function type
245bool isFtype( const Type * type ) {
246        if ( dynamic_cast< const FunctionType * >( type ) ) {
247                return true;
248        } else if ( auto typeInst = dynamic_cast< const TypeInstType * >( type ) ) {
249                return typeInst->kind == TypeDecl::Ftype;
250        } else return false;
251}
252
253namespace {
254        /// true if the given type can be bound to the given type variable
255        bool tyVarCompatible( const TypeDecl::Data & data, const Type * type ) {
256                switch ( data.kind ) {
257                  case TypeDecl::Dtype:
258                        // to bind to an object type variable, the type must not be a function type.
259                        // if the type variable is specified to be a complete type then the incoming
260                        // type must also be complete
261                        // xxx - should this also check that type is not a tuple type and that it's not a ttype?
262                        return ! isFtype( type ) && ( ! data.isComplete || type->isComplete() );
263                  case TypeDecl::Ftype:
264                        return isFtype( type );
265                  case TypeDecl::Ttype:
266                        // ttype unifies with any tuple type
267                        return dynamic_cast< const TupleType * >( type ) || Tuples::isTtype( type );
268                  default:
269                        assertf(false, "Unhandled tyvar kind: %d", data.kind);
270                        return false;
271                }
272        }
273}
274
275bool TypeEnvironment::bindVar(
276                const TypeInstType * typeInst, const Type * bindTo, const TypeDecl::Data & data,
277                AssertionSet & need, AssertionSet & have, const OpenVarSet & open, WidenMode widen,
278                const SymbolTable & symtab
279) {
280        // remove references from bound type, so that type variables can only bind to value types
281        ptr<Type> target = bindTo->stripReferences();
282        auto tyvar = open.find( typeInst->name );
283        assert( tyvar != open.end() );
284        if ( ! tyVarCompatible( tyvar->second, target ) ) return false;
285        if ( occurs( target, typeInst->name, *this ) ) return false;
286
287        auto it = internal_lookup( typeInst->name );
288        if ( it != env.end() ) {
289                if ( it->bound ) {
290                        // attempt to unify equivalence class type with type to bind to.
291                        // equivalence class type has stripped qualifiers which must be restored
292                        ptr<Type> common;
293                        ptr<Type> newType = it->bound;
294                        reset_qualifiers( newType, typeInst->qualifiers );
295                        if ( unifyInexact(
296                                        newType, target, *this, need, have, open,
297                                        widen & WidenMode{ it->allowWidening, true }, symtab, common ) ) {
298                                if ( common ) {
299                                        it->bound = std::move(common);
300                                        reset_qualifiers( it->bound );
301                                }
302                        } else return false;
303                } else {
304                        it->bound = std::move(target);
305                        reset_qualifiers( it->bound );
306                        it->allowWidening = widen.first && widen.second;
307                }
308        } else {
309                env.emplace_back(
310                        typeInst->name, target, widen.first && widen.second, data );
311        }
312        return true;
313}
314
315bool TypeEnvironment::bindVarToVar(
316                const TypeInstType * var1, const TypeInstType * var2, TypeDecl::Data && data,
317                AssertionSet & need, AssertionSet & have, const OpenVarSet & open,
318                WidenMode widen, const SymbolTable & symtab
319) {
320        auto c1 = internal_lookup( var1->name );
321        auto c2 = internal_lookup( var2->name );
322
323        // exit early if variables already bound together
324        if ( c1 != env.end() && c1 == c2 ) {
325                c1->allowWidening &= widen;
326                return true;
327        }
328
329        bool widen1 = false, widen2 = false;
330        const Type * type1 = nullptr, * type2 = nullptr;
331
332        // check for existing bindings, perform occurs check
333        if ( c1 != env.end() ) {
334                if ( c1->bound ) {
335                        if ( occurs( c1->bound, var2->name, *this ) ) return false;
336                        type1 = c1->bound;
337                }
338                widen1 = widen.first && c1->allowWidening;
339        }
340        if ( c2 != env.end() ) {
341                if ( c2->bound ) {
342                        if ( occurs( c2->bound, var1->name, *this ) ) return false;
343                        type2 = c2->bound;
344                }
345                widen2 = widen.second && c2->allowWidening;
346        }
347
348        if ( type1 && type2 ) {
349                // both classes bound, merge if bound types can be unified
350                ptr<Type> newType1{ type1 }, newType2{ type2 };
351                WidenMode newWidenMode{ widen1, widen2 };
352                ptr<Type> common;
353
354                if ( unifyInexact(
355                                newType1, newType2, *this, need, have, open, newWidenMode, symtab, common ) ) {
356                        c1->vars.insert( c2->vars.begin(), c2->vars.end() );
357                        c1->allowWidening = widen1 && widen2;
358                        if ( common ) {
359                                c1->bound = std::move(common);
360                                reset_qualifiers( c1->bound );
361                        }
362                        c1->data.isComplete |= data.isComplete;
363                        env.erase( c2 );
364                } else return false;
365        } else if ( c1 != env.end() && c2 != env.end() ) {
366                // both classes exist, at least one unbound, merge unconditionally
367                if ( type1 ) {
368                        c1->vars.insert( c2->vars.begin(), c2->vars.end() );
369                        c1->allowWidening = widen1;
370                        c1->data.isComplete |= data.isComplete;
371                        env.erase( c2 );
372                } else {
373                        c2->vars.insert( c1->vars.begin(), c1->vars.end() );
374                        c2->allowWidening = widen2;
375                        c2->data.isComplete |= data.isComplete;
376                        env.erase( c1 );
377                }
378        } else if ( c1 != env.end() ) {
379                // var2 unbound, add to env[c1]
380                c1->vars.emplace( var2->name );
381                c1->allowWidening = widen1;
382                c1->data.isComplete |= data.isComplete;
383        } else if ( c2 != env.end() ) {
384                // var1 unbound, add to env[c2]
385                c2->vars.emplace( var1->name );
386                c2->allowWidening = widen2;
387                c2->data.isComplete |= data.isComplete;
388        } else {
389                // neither var bound, create new class
390                env.emplace_back( var1->name, var2->name, widen1 && widen2, data );
391        }
392
393        return true;
394}
395
396void TypeEnvironment::forbidWidening() {
397        for ( EqvClass& c : env ) c.allowWidening = false;
398}
399
400void TypeEnvironment::add( EqvClass && eqvClass ) {
401        filterOverlappingClasses( env, eqvClass );
402        env.emplace_back( std::move(eqvClass) );
403}
404
405bool TypeEnvironment::mergeBound(
406                EqvClass & to, const EqvClass & from, OpenVarSet & open, const SymbolTable & symtab ) {
407        if ( from.bound ) {
408                if ( to.bound ) {
409                        // attempt to unify bound types
410                        ptr<Type> toType{ to.bound }, fromType{ from.bound };
411                        WidenMode widen{ to.allowWidening, from.allowWidening };
412                        ptr<Type> common;
413                        AssertionSet need, have;
414
415                        if ( unifyInexact(
416                                        toType, fromType, *this, need, have, open, widen, symtab, common ) ) {
417                                // unifies, set common type if necessary
418                                if ( common ) {
419                                        to.bound = std::move(common);
420                                        reset_qualifiers( to.bound );
421                                }
422                        } else return false; // cannot unify
423                } else {
424                        to.bound = from.bound;
425                }
426        }
427
428        // unify widening if matches
429        to.allowWidening &= from.allowWidening;
430        return true;
431}
432
433bool TypeEnvironment::mergeClasses(
434        ClassList::iterator to, ClassList::iterator from, OpenVarSet & open, const SymbolTable & symtab
435) {
436        EqvClass & r = *to, & s = *from;
437
438        // ensure bounds match
439        if ( ! mergeBound( r, s, open, symtab ) ) return false;
440
441        // check safely bindable
442        if ( r.bound ) {
443                for ( const auto & v : s.vars ) if ( occurs( r.bound, v, *this ) ) return false;
444        }
445
446        // merge classes
447        r.vars.insert( s.vars.begin(), s.vars.end() );
448        r.allowWidening &= s.allowWidening;
449        env.erase( from );
450
451        return true;
452}
453
454TypeEnvironment::ClassList::iterator TypeEnvironment::internal_lookup( const std::string & var ) {
455        for ( ClassList::iterator i = env.begin(); i != env.end(); ++i ) {
456                if ( i->vars.count( var ) ) return i;
457        }
458        return env.end();
459}
460
461void print( std::ostream & out, const TypeEnvironment & env, Indenter indent ) {
462        for ( const auto & clz : env ) {
463                print( out, clz, indent );
464        }
465}
466
467std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env ) {
468        print( out, env );
469        return out;
470}
471
472}
473
474// Local Variables: //
475// tab-width: 4 //
476// mode: c++ //
477// compile-command: "make install" //
478// End: //
Note: See TracBrowser for help on using the repository browser.