source: src/AST/TypeEnvironment.cpp @ de8dfac2

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since de8dfac2 was ee574a2, checked in by Aaron Moss <a3moss@…>, 5 years ago

Port CommonType? to new AST

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