source: src/ResolvExpr/TypeEnvironment.cc @ eff03a94

new-env
Last change on this file since eff03a94 was eff03a94, checked in by Aaron Moss <a3moss@…>, 5 years ago

Fixed infinite loop bugs

  • Property mode set to 100644
File size: 16.9 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.cc --
8//
9// Author           : Aaron B. Moss
10// Created On       : Sun May 17 12:19:47 2015
11// Last Modified By : Aaron B. Moss
12// Last Modified On : Fri Jun 29 15:51:00 2018
13// Update Count     : 5
14//
15
16#include <cassert>                     // for assert
17#include <algorithm>                   // for copy, set_intersection
18#include <iterator>                    // for ostream_iterator, insert_iterator
19#include <utility>                     // for pair, move
20
21#include "Common/InternedString.h"     // for interned_string
22#include "Common/PassVisitor.h"        // for PassVisitor<GcTracer>
23#include "Common/option.h"             // for option<T>
24#include "Common/utility.h"            // for maybeClone
25#include "SymTab/Indexer.h"            // for Indexer
26#include "SynTree/GcTracer.h"          // for PassVisitor<GcTracer>
27#include "SynTree/Type.h"              // for Type, FunctionType, Type::Fora...
28#include "SynTree/TypeSubstitution.h"  // for TypeSubstitution
29#include "Tuples/Tuples.h"             // for isTtype
30#include "TypeEnvironment.h"
31#include "typeops.h"                   // for occurs
32#include "Unify.h"                     // for unifyInexact
33
34namespace ResolvExpr {
35        #if 0
36        #define PRE_POST_VALIDATE auto dbg = ValidateGuard{this, __func__};
37        #define PRE_POST_VALIDATE_NOM auto dbg = ValidateGuard{this};
38        struct ValidateGuard {
39                const TypeEnvironment* env;
40                const TypeEnvironment::Classes* old_classes;
41                const TypeEnvironment::Bindings* old_bindings;
42                const char* last_fn;
43
44                void validate_classes( const TypeEnvironment::Classes* c ) {
45                        typedef TypeEnvironment::Classes C;
46
47                        assertf( c != nullptr, "classes non-null" );
48                       
49                        C::Mode cmode = c->get_mode();
50                        if ( cmode == C::BASE ) {
51                                // xxx - consistency checks
52                        } else {
53                                assertf( cmode == C::ADD || cmode == C::REM || cmode == C::ADDTO || cmode == C::REMFROM, "valid classes mode" );
54                                validate_classes( c->get_base() );
55                        }
56                }
57
58                void validate_bindings( const TypeEnvironment::Bindings* b ) {
59                        typedef TypeEnvironment::Bindings B;
60
61                        assertf( b != nullptr, "bindings non-null" );
62
63                        B::Mode bmode = b->get_mode();
64                        if ( bmode == B::BASE ) {
65                                // xxx - consistency checks
66                        } else {
67                                assertf( bmode == B::REM || bmode == B::INS || bmode == B::UPD, "valid bindings mode" );
68                                validate_bindings( b->get_base() );
69                        }
70                }
71
72                void validate_env() {
73                        validate_classes( env->classes );
74                        validate_bindings( env->bindings );
75                       
76                        // xxx - joint validation
77                }
78
79                ValidateGuard(const TypeEnvironment* e)
80                        : env{e}, old_classes{e->classes}, old_bindings{e->bindings}, last_fn{e->last_fn}
81                        { validate_env(); }
82                ValidateGuard(const TypeEnvironment* e, const char* fn)
83                        : env{e}, old_classes{e->classes}, old_bindings{e->bindings}, last_fn{fn}
84                        { validate_env(); }
85                ~ValidateGuard() {
86                        validate_env();
87                        if ( env->classes != old_classes ) validate_classes( old_classes );
88                        if ( env->bindings != old_bindings ) validate_bindings( old_bindings );
89                        const_cast<TypeEnvironment*>(env)->last_fn = last_fn;
90                }
91        };
92        #else
93        #define PRE_POST_VALIDATE
94        #define PRE_POST_VALIDATE_NOM
95        #endif
96
97        void printAssertionSet( const AssertionSet &assertions, std::ostream &os, int indent ) {
98                for ( AssertionSet::const_iterator i = assertions.begin(); i != assertions.end(); ++i ) {
99                        i->first->print( os, indent );
100                        if ( i->second.isUsed ) {
101                                os << "(used)";
102                        } else {
103                                os << "(not used)";
104                        } // if
105                } // for
106        }
107
108        void printOpenVarSet( const OpenVarSet &openVars, std::ostream &os, int indent ) {
109                os << std::string( indent, ' ' );
110                for ( OpenVarSet::const_iterator i = openVars.begin(); i != openVars.end(); ++i ) {
111                        os << i->first << "(" << i->second << ") ";
112                } // for
113        }
114
115        std::pair<interned_string, interned_string> TypeEnvironment::mergeClasses( 
116                        interned_string root1, interned_string root2 ) {
117                PRE_POST_VALIDATE
118                // merge classes
119                Classes* newClasses = classes->merge( root1, root2 );
120
121                // determine new root
122                assertf(classes->get_mode() == Classes::REMFROM, "classes updated to REMFROM by merge");
123                auto ret = std::make_pair( classes->get_root(), classes->get_child() );
124               
125                // finalize classes
126                classes = newClasses;
127                return ret;
128        }
129
130        ClassRef TypeEnvironment::lookup( interned_string var ) const {
131                interned_string root = classes->find_or_default( var, nullptr );
132                if ( root ) return { this, root };
133                else return { nullptr, var };
134        }
135
136        bool isFtype( Type *type ) {
137                if ( dynamic_cast< FunctionType* >( type ) ) {
138                        return true;
139                } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( type ) ) {
140                        return typeInst->get_isFtype();
141                } // if
142                return false;
143        }
144
145        bool tyVarCompatible( const TypeDecl::Data & data, Type *type ) {
146                switch ( data.kind ) {
147                  case TypeDecl::Dtype:
148                        // to bind to an object type variable, the type must not be a function type.
149                        // if the type variable is specified to be a complete type then the incoming
150                        // type must also be complete
151                        // xxx - should this also check that type is not a tuple type and that it's not a ttype?
152                        return ! isFtype( type ) && (! data.isComplete || type->isComplete() );
153                  case TypeDecl::Ftype:
154                        return isFtype( type );
155                  case TypeDecl::Ttype:
156                        // ttype unifies with any tuple type
157                        return dynamic_cast< TupleType * >( type ) || Tuples::isTtype( type );
158                } // switch
159                return false;
160        }
161
162        bool TypeEnvironment::bindVar( TypeInstType* typeInst, Type* bindTo, 
163                        const TypeDecl::Data& data, AssertionSet& need, AssertionSet& have, 
164                        const OpenVarSet& openVars, WidenMode widenMode, const SymTab::Indexer& indexer ) {
165                PRE_POST_VALIDATE
166                // remove references from other, so that type variables can only bind to value types
167                bindTo = bindTo->stripReferences();
168               
169                auto tyVar = openVars.find( typeInst->get_name() );
170                assert( tyVar != openVars.end() );
171                if ( ! tyVarCompatible( tyVar->second, bindTo ) ) return false;
172
173                if ( occurs( bindTo, typeInst->get_name(), *this ) ) return false;
174
175                if ( ClassRef curClass = lookup( typeInst->get_name() ) ) {
176                        BoundType curData = curClass.get_bound();
177                        if ( curData.type ) {
178                                Type* common = nullptr;
179                                // attempt to unify equivalence class type (which needs its qualifiers restored)
180                                // with the target type
181                                Type* newType = curData.type->clone();
182                                newType->get_qualifiers() = typeInst->get_qualifiers();
183                                if ( unifyInexact( newType, bindTo, *this, need, have, openVars, 
184                                                widenMode & WidenMode{ curData.allowWidening, true }, indexer, common ) ) {
185                                        if ( common ) {
186                                                // update bound type to common type
187                                                common->get_qualifiers() = Type::Qualifiers{};
188                                                curData.type = common;
189                                                bindings = bindings->set( curClass.update_root(), curData );
190                                        }
191                                        return true;
192                                } else return false;
193                        } else {
194                                // update bound type to other type
195                                curData.type = bindTo->clone();
196                                curData.type->get_qualifiers() = Type::Qualifiers{};
197                                curData.allowWidening = widenMode.widenFirst && widenMode.widenSecond;
198                                bindings = bindings->set( curClass.get_root(), curData );
199                        }
200                } else {
201                        // make new class consisting entirely of this variable
202                        BoundType curData{ 
203                                bindTo->clone(), widenMode.widenFirst && widenMode.widenSecond, data };
204                        curData.type->get_qualifiers() = Type::Qualifiers{};
205                        classes = classes->add( curClass.get_root() );
206                        bindings = bindings->set( curClass.get_root(), curData );
207                }
208                return true;
209        }
210       
211        bool TypeEnvironment::bindVarToVar( TypeInstType* var1, TypeInstType* var2, 
212                        const TypeDecl::Data& data, AssertionSet& need, AssertionSet& have, 
213                        const OpenVarSet& openVars, WidenMode widenMode, const SymTab::Indexer& indexer ) {
214                PRE_POST_VALIDATE
215                ClassRef class1 = lookup( var1->get_name() );
216                ClassRef class2 = lookup( var2->get_name() );
217               
218                // exit early if variables already bound together
219                if ( class1 && class2 && class1 == class2 ) {
220                        BoundType data1 = class1.get_bound();
221                        // narrow the binding if needed
222                        if ( data1.allowWidening && widenMode.widenFirst != widenMode.widenSecond ) {
223                                data1.allowWidening = false;
224                                bindings = bindings->set( class1.get_root(), data1 );
225                        }
226                        return true;
227                }
228
229                BoundType data1 = class1 ? class1.get_bound() : BoundType{};
230                BoundType data2 = class2 ? class2.get_bound() : BoundType{};
231
232                bool widen1 = data1.allowWidening && widenMode.widenFirst;
233                bool widen2 = data2.allowWidening && widenMode.widenSecond;
234
235                if ( data1.type && data2.type ) {
236                        // attempt to unify bound classes
237                        Type* common = nullptr;
238                        if ( unifyInexact( data1.type->clone(), data2.type->clone(), *this, need, have, 
239                                        openVars, WidenMode{ widen1, widen2 }, indexer, common ) ) {
240                                // merge type variables
241                                interned_string root = 
242                                        mergeClasses( class1.update_root(), class2.update_root() ).first;
243                                // update bindings
244                                data1.allowWidening = widen1 && widen2;
245                                if ( common ) {
246                                        common->get_qualifiers() = Type::Qualifiers{};
247                                        data1.type = common;
248                                }
249                                bindings = bindings->set( root, data1 );
250                        } else return false;
251                } else if ( class1 && class2 ) {
252                        // both classes exist, only one bound -- merge type variables
253                        auto merged = mergeClasses( class1.get_root(), class2.get_root() );
254                        // remove subordinate binding
255                        bindings = bindings->erase( merged.second );
256                        // update root binding (narrow widening as needed, or set new binding for changed root)
257                        if ( data1.type ) {
258                                if ( data1.allowWidening != widen1 ) {
259                                        data1.allowWidening = widen1;
260                                        bindings = bindings->set( merged.first, data1 );
261                                } else if ( merged.first == class2.get_root() ) {
262                                        bindings = bindings->set( merged.first, data1 );
263                                }
264                        } else /* if ( data2.type ) */ {
265                                if ( data2.allowWidening != widen2 ) {
266                                        data2.allowWidening = widen2;
267                                        bindings = bindings->set( merged.first, data2 );
268                                } else if ( merged.first == class1.get_root() ) {
269                                        bindings = bindings->set( merged.first, data2 );
270                                }
271                        }
272                } else if ( class1 ) {
273                        // add unbound var2 to class1
274                        classes = classes->add( class2.get_root() );
275                        auto merged = mergeClasses( class1.get_root(), class2.get_root() );
276                        // update bindings (narrow as needed, or switch binding to root)
277                        if ( merged.first == class2.get_root() ) {
278                                data1.allowWidening = widen1;
279                                bindings = bindings->erase( merged.second )->set( merged.first, data1 );
280                        } else if ( data1.allowWidening != widen1 ) {
281                                bindings = bindings->set( merged.first, data1 );
282                        }
283                } else if ( class2 ) {
284                        // add unbound var1 to class1
285                        classes = classes->add( class1.get_root() );
286                        auto merged = mergeClasses( class1.get_root(), class2.get_root() );
287                        // update bindings (narrow as needed, or switch binding to root)
288                        if ( merged.first == class1.get_root() ) {
289                                data2.allowWidening = widen2;
290                                bindings = bindings->erase( merged.second )->set( merged.first, data2 );
291                        } else if ( data2.allowWidening != widen2 ) {
292                                bindings = bindings->set( merged.first, data2 );
293                        }
294                } else {
295                        // make new class with pair of unbound vars
296                        classes = classes->add( class1.get_root() )->add( class2.get_root() );
297                        auto merged = mergeClasses( class1.get_root(), class2.get_root() );
298                        bindings = bindings->set( merged.first, BoundType{ nullptr, widen1 && widen2, data } );
299                }
300                return true;
301        }
302
303        void TypeEnvironment::add( const Type::ForallList &tyDecls ) {
304                PRE_POST_VALIDATE
305                for ( Type::ForallList::const_iterator i = tyDecls.begin(); i != tyDecls.end(); ++i ) {
306                        interned_string name = (*i)->get_name();
307                        classes = classes->add( name );
308                        bindings = bindings->set( name, *i );
309                } // for
310        }
311
312        void TypeEnvironment::add( const TypeSubstitution & sub ) {
313                PRE_POST_VALIDATE
314                interned_string not_found{nullptr};
315
316                for ( auto p : sub ) {
317                        interned_string var = p.first;
318                       
319                        // filter overlapping classes out of existing environment
320                        // xxx - this is a very shady assumption, but has worked for a long time...
321                        interned_string root = classes->find_or_default( var, not_found );
322                        if ( root != not_found ) {
323                                classes = classes->remove_class( root );
324                                bindings = bindings->erase( root );
325                        }
326
327                        // Minimal assumptions. Not technically correct, but might be good enough, and
328                        // is the best we can do at the moment since information is lost in the
329                        // transition to TypeSubstitution
330                        TypeDecl::Data data{ TypeDecl::Dtype, false };
331
332                        // add variable to class and bindings
333                        classes = classes->add( var );
334                        bindings = bindings->set( var, BoundType{ p.second->clone(), false, data } );
335                }
336        }
337
338        void TypeEnvironment::makeSubstitution( TypeSubstitution &sub ) const {
339                PRE_POST_VALIDATE_NOM
340                bindings->for_each([&]( interned_string root, const BoundType& bound ){
341                        classes->for_class(root, [&]( interned_string var ) {
342                                if ( bound.type ) {
343                                        sub.add( var, bound.type );
344                                } else if ( var != root ) {
345                                        sub.add( var, new TypeInstType{ 
346                                                Type::Qualifiers{}, root, bound.data.kind == TypeDecl::Ftype } );
347                                }
348                        });
349                });
350
351                sub.normalize();
352        }
353
354        void TypeEnvironment::print( std::ostream &os, Indenter indent ) const {
355                bindings->for_each([&]( interned_string root, const BoundType& bound ) {
356                        os << "( ";
357                        classes->for_class( root, [&os]( interned_string var ) { os << var << " "; } );
358                        os << ")";
359                        if ( bound.type ) {
360                                os << " -> ";
361                                bound.type->print( os, indent+1 );
362                        }
363                        if ( ! bound.allowWidening ) {
364                                os << " (no widening)";
365                        }
366                        os << std::endl;
367                });
368        }
369
370        namespace {
371                // temporary representation of an equivalence class
372                struct EqvClass {
373                        std::vector<interned_string> vars;
374                        BoundType bound;
375
376                        EqvClass() = default;
377                        EqvClass(const BoundType& b) : bound{b} {}
378                };
379        }
380
381        void TypeEnvironment::simpleCombine( const TypeEnvironment &o ) {
382                PRE_POST_VALIDATE
383                // check for same environment
384                if ( classes == o.classes && bindings == o.bindings ) return;
385
386                // read out equivalence classes (avoids conflicting reroots)
387                std::vector<EqvClass> ecs;
388                o.bindings->for_each( [&]( interned_string root, const BoundType& bound ) {
389                        ecs.emplace_back(bound);
390                        o.classes->for_class( root, [&]( interned_string var ) {
391                                ecs.back().vars.push_back( var );
392                        } );
393                } );
394
395                // read equivalence classes into self
396                for ( EqvClass& ec : ecs ) {
397                        // merge vars
398                        interned_string new_root{nullptr};
399                        for ( interned_string var : ec.vars ) {
400                                Classes* new_classes = classes->add( var );
401                                if ( new_classes == classes ) { var = classes->find( var ); }
402                                else { classes = new_classes; }
403                                new_root = new_root ? mergeClasses( new_root, var ).first : var;
404                        }
405                        // set binding
406                        bindings = bindings->set( new_root, ec.bound );
407                }
408        }
409
410        void TypeEnvironment::extractOpenVars( OpenVarSet &openVars ) const {
411                bindings->for_each( [&]( interned_string root, const BoundType& bound ) {
412                        classes->for_class( root, [&openVars,&bound]( interned_string var ) {
413                                openVars[ var ] = bound.data;
414                        } );
415                } );
416        }
417
418        void TypeEnvironment::addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars ) {
419                PRE_POST_VALIDATE
420                if ( classes == actualEnv.classes && bindings == actualEnv.bindings ) {
421                        // actualEnv already the same, just need to update openVars
422                        extractOpenVars( openVars );
423                        return;
424                } else assertf(classes != actualEnv.classes && bindings != actualEnv.bindings, "classes & bindings updated together");
425
426                // read out equivalence classes (avoids conflicting reroots)
427                std::vector<EqvClass> ecs;
428                actualEnv.bindings->for_each( [&]( interned_string root, const BoundType& bound ) {
429                        ecs.emplace_back(bound);
430                        actualEnv.classes->for_class( root, [&]( interned_string var ) {
431                                ecs.back().vars.push_back( var );
432                        } );
433                } );
434
435                // add members of new class, setting openVars concurrently
436                for ( EqvClass& ec : ecs ) {
437                        // merge vars
438                        interned_string new_root{nullptr};
439                        for ( interned_string var : ec.vars ) {
440                                openVars[ var ] = ec.bound.data;
441                                Classes* new_classes = classes->add( var );
442                                if ( new_classes == classes ) {
443                                        // xxx - this case is a bit sketchy, but has been working
444                                        // xxx - merging the classes is a departure from previous behaviour
445                                        var = classes->find( var );
446                                } else { classes = new_classes; }
447                                new_root = new_root ? mergeClasses( new_root, var ).first : var;
448                        }
449                        // set binding without widening
450                        bindings = bindings->set( new_root, 
451                                BoundType{ maybeClone(ec.bound.type), false, ec.bound.data } );
452                }
453        }
454
455        void TypeEnvironment::forbidWidening() {
456                PRE_POST_VALIDATE
457                bindings = bindings->mutate_each([]( const interned_string&, BoundType& c ) {
458                        if ( c.allowWidening ) {
459                                option<BoundType> ret = c;
460                                c.allowWidening = false;
461                                return ret;
462                        } else return option<BoundType>{};
463                });
464        }
465
466        std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env ) {
467                env.print( out );
468                return out;
469        }
470
471        PassVisitor<GcTracer> & operator<<( PassVisitor<GcTracer> & gc, const TypeEnvironment & env ) {
472                gc.pass.visit( env );
473                // for ( ClassRef c : env ) {
474                //      maybeAccept( c.get_bound().type, gc );
475                // }
476                return gc;
477        }
478} // namespace ResolvExpr
479
480// Local Variables: //
481// tab-width: 4 //
482// mode: c++ //
483// compile-command: "make install" //
484// End: //
Note: See TracBrowser for help on using the repository browser.