source: src/ResolvExpr/TypeEnvironment.cc @ 9160cb2

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

Breadth-first assertion resolution builds, eats all the memory

  • Property mode set to 100644
File size: 25.9 KB
RevLine 
[a32b204]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//
[03da511]7// TypeEnvironment.cc --
[a32b204]8//
[b21c77a]9// Author           : Aaron B. Moss
[a32b204]10// Created On       : Sun May 17 12:19:47 2015
[d286cf68]11// Last Modified By : Aaron B. Moss
[b21c77a]12// Last Modified On : Fri Jun 29 15:51:00 2018
13// Update Count     : 5
[a32b204]14//
[51b7345]15
[ea6332d]16#include <cassert>                     // for assert
17#include <algorithm>                   // for copy, set_intersection
18#include <iterator>                    // for ostream_iterator, insert_iterator
[f89a111]19#include <list>                        // for list
20#include <vector>                      // for vector
21#include <unordered_map>               // for unordered_map
[8e18b8e]22#include <utility>                     // for pair, move
[51b7345]23
[982f95d]24#include "Common/InternedString.h"     // for interned_string
[f229fc2]25#include "Common/PassVisitor.h"        // for PassVisitor<GcTracer>
[184557e]26#include "Common/option.h"             // for option<T>
[ea6332d]27#include "Common/utility.h"            // for maybeClone
[982f95d]28#include "SymTab/Indexer.h"            // for Indexer
[f229fc2]29#include "SynTree/GcTracer.h"          // for PassVisitor<GcTracer>
[ea6332d]30#include "SynTree/Type.h"              // for Type, FunctionType, Type::Fora...
31#include "SynTree/TypeSubstitution.h"  // for TypeSubstitution
[5c14030]32#include "Tuples/Tuples.h"             // for isTtype
[51b7345]33#include "TypeEnvironment.h"
[d286cf68]34#include "typeops.h"                   // for occurs
[982f95d]35#include "Unify.h"                     // for unifyInexact
[51b7345]36
37namespace ResolvExpr {
[eff03a94]38        #if 0
[d318a18]39        #define PRE_POST_VALIDATE auto dbg = ValidateGuard{this, __func__};
40        #define PRE_POST_VALIDATE_NOM auto dbg = ValidateGuard{this};
41        struct ValidateGuard {
42                const TypeEnvironment* env;
43                const TypeEnvironment::Classes* old_classes;
44                const TypeEnvironment::Bindings* old_bindings;
45                const char* last_fn;
46
47                void validate_classes( const TypeEnvironment::Classes* c ) {
48                        typedef TypeEnvironment::Classes C;
49
50                        assertf( c != nullptr, "classes non-null" );
51                       
52                        C::Mode cmode = c->get_mode();
53                        if ( cmode == C::BASE ) {
54                                // xxx - consistency checks
55                        } else {
56                                assertf( cmode == C::ADD || cmode == C::REM || cmode == C::ADDTO || cmode == C::REMFROM, "valid classes mode" );
57                                validate_classes( c->get_base() );
58                        }
59                }
60
61                void validate_bindings( const TypeEnvironment::Bindings* b ) {
62                        typedef TypeEnvironment::Bindings B;
63
64                        assertf( b != nullptr, "bindings non-null" );
65
66                        B::Mode bmode = b->get_mode();
67                        if ( bmode == B::BASE ) {
68                                // xxx - consistency checks
69                        } else {
70                                assertf( bmode == B::REM || bmode == B::INS || bmode == B::UPD, "valid bindings mode" );
71                                validate_bindings( b->get_base() );
72                        }
73                }
74
75                void validate_env() {
76                        validate_classes( env->classes );
77                        validate_bindings( env->bindings );
78                       
79                        // xxx - joint validation
80                }
81
82                ValidateGuard(const TypeEnvironment* e)
83                        : env{e}, old_classes{e->classes}, old_bindings{e->bindings}, last_fn{e->last_fn}
84                        { validate_env(); }
85                ValidateGuard(const TypeEnvironment* e, const char* fn)
86                        : env{e}, old_classes{e->classes}, old_bindings{e->bindings}, last_fn{fn}
87                        { validate_env(); }
88                ~ValidateGuard() {
89                        validate_env();
90                        if ( env->classes != old_classes ) validate_classes( old_classes );
91                        if ( env->bindings != old_bindings ) validate_bindings( old_bindings );
92                        const_cast<TypeEnvironment*>(env)->last_fn = last_fn;
93                }
94        };
95        #else
96        #define PRE_POST_VALIDATE
97        #define PRE_POST_VALIDATE_NOM
98        #endif
99
[a32b204]100        void printAssertionSet( const AssertionSet &assertions, std::ostream &os, int indent ) {
101                for ( AssertionSet::const_iterator i = assertions.begin(); i != assertions.end(); ++i ) {
102                        i->first->print( os, indent );
[6c3a988f]103                        if ( i->second.isUsed ) {
[a32b204]104                                os << "(used)";
105                        } else {
106                                os << "(not used)";
107                        } // if
108                } // for
109        }
110
111        void printOpenVarSet( const OpenVarSet &openVars, std::ostream &os, int indent ) {
112                os << std::string( indent, ' ' );
113                for ( OpenVarSet::const_iterator i = openVars.begin(); i != openVars.end(); ++i ) {
114                        os << i->first << "(" << i->second << ") ";
115                } // for
116        }
117
[982f95d]118        std::pair<interned_string, interned_string> TypeEnvironment::mergeClasses( 
119                        interned_string root1, interned_string root2 ) {
[d318a18]120                PRE_POST_VALIDATE
[982f95d]121                // merge classes
122                Classes* newClasses = classes->merge( root1, root2 );
123
124                // determine new root
125                assertf(classes->get_mode() == Classes::REMFROM, "classes updated to REMFROM by merge");
[184557e]126                auto ret = std::make_pair( classes->get_root(), classes->get_child() );
[982f95d]127               
128                // finalize classes
129                classes = newClasses;
130                return ret;
131        }
132
133        ClassRef TypeEnvironment::lookup( interned_string var ) const {
134                interned_string root = classes->find_or_default( var, nullptr );
135                if ( root ) return { this, root };
136                else return { nullptr, var };
137        }
138
[b21c77a]139        bool isFtype( Type *type ) {
140                if ( dynamic_cast< FunctionType* >( type ) ) {
141                        return true;
142                } else if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( type ) ) {
143                        return typeInst->get_isFtype();
144                } // if
145                return false;
146        }
147
[982f95d]148        bool tyVarCompatible( const TypeDecl::Data & data, Type *type ) {
149                switch ( data.kind ) {
150                  case TypeDecl::Dtype:
151                        // to bind to an object type variable, the type must not be a function type.
152                        // if the type variable is specified to be a complete type then the incoming
153                        // type must also be complete
154                        // xxx - should this also check that type is not a tuple type and that it's not a ttype?
155                        return ! isFtype( type ) && (! data.isComplete || type->isComplete() );
156                  case TypeDecl::Ftype:
157                        return isFtype( type );
158                  case TypeDecl::Ttype:
159                        // ttype unifies with any tuple type
160                        return dynamic_cast< TupleType * >( type ) || Tuples::isTtype( type );
161                } // switch
162                return false;
163        }
164
165        bool TypeEnvironment::bindVar( TypeInstType* typeInst, Type* bindTo, 
166                        const TypeDecl::Data& data, AssertionSet& need, AssertionSet& have, 
167                        const OpenVarSet& openVars, WidenMode widenMode, const SymTab::Indexer& indexer ) {
[d318a18]168                PRE_POST_VALIDATE
[982f95d]169                // remove references from other, so that type variables can only bind to value types
170                bindTo = bindTo->stripReferences();
171               
172                auto tyVar = openVars.find( typeInst->get_name() );
173                assert( tyVar != openVars.end() );
[5c14030]174                if ( ! tyVarCompatible( tyVar->second, bindTo ) ) return false;
[982f95d]175
176                if ( occurs( bindTo, typeInst->get_name(), *this ) ) return false;
177
178                if ( ClassRef curClass = lookup( typeInst->get_name() ) ) {
179                        BoundType curData = curClass.get_bound();
180                        if ( curData.type ) {
181                                Type* common = nullptr;
182                                // attempt to unify equivalence class type (which needs its qualifiers restored)
183                                // with the target type
184                                Type* newType = curData.type->clone();
185                                newType->get_qualifiers() = typeInst->get_qualifiers();
186                                if ( unifyInexact( newType, bindTo, *this, need, have, openVars, 
187                                                widenMode & WidenMode{ curData.allowWidening, true }, indexer, common ) ) {
188                                        if ( common ) {
189                                                // update bound type to common type
190                                                common->get_qualifiers() = Type::Qualifiers{};
191                                                curData.type = common;
192                                                bindings = bindings->set( curClass.update_root(), curData );
193                                        }
194                                        return true;
195                                } else return false;
196                        } else {
197                                // update bound type to other type
198                                curData.type = bindTo->clone();
199                                curData.type->get_qualifiers() = Type::Qualifiers{};
200                                curData.allowWidening = widenMode.widenFirst && widenMode.widenSecond;
201                                bindings = bindings->set( curClass.get_root(), curData );
202                        }
203                } else {
204                        // make new class consisting entirely of this variable
[5c14030]205                        BoundType curData{ 
206                                bindTo->clone(), widenMode.widenFirst && widenMode.widenSecond, data };
[982f95d]207                        curData.type->get_qualifiers() = Type::Qualifiers{};
208                        classes = classes->add( curClass.get_root() );
209                        bindings = bindings->set( curClass.get_root(), curData );
210                }
211                return true;
212        }
213       
214        bool TypeEnvironment::bindVarToVar( TypeInstType* var1, TypeInstType* var2, 
215                        const TypeDecl::Data& data, AssertionSet& need, AssertionSet& have, 
216                        const OpenVarSet& openVars, WidenMode widenMode, const SymTab::Indexer& indexer ) {
[d318a18]217                PRE_POST_VALIDATE
[5c14030]218                ClassRef class1 = lookup( var1->get_name() );
219                ClassRef class2 = lookup( var2->get_name() );
[982f95d]220               
221                // exit early if variables already bound together
222                if ( class1 && class2 && class1 == class2 ) {
223                        BoundType data1 = class1.get_bound();
224                        // narrow the binding if needed
[5c14030]225                        if ( data1.allowWidening && widenMode.widenFirst != widenMode.widenSecond ) {
[982f95d]226                                data1.allowWidening = false;
227                                bindings = bindings->set( class1.get_root(), data1 );
228                        }
229                        return true;
230                }
231
232                BoundType data1 = class1 ? class1.get_bound() : BoundType{};
233                BoundType data2 = class2 ? class2.get_bound() : BoundType{};
234
235                bool widen1 = data1.allowWidening && widenMode.widenFirst;
236                bool widen2 = data2.allowWidening && widenMode.widenSecond;
237
238                if ( data1.type && data2.type ) {
239                        // attempt to unify bound classes
240                        Type* common = nullptr;
241                        if ( unifyInexact( data1.type->clone(), data2.type->clone(), *this, need, have, 
242                                        openVars, WidenMode{ widen1, widen2 }, indexer, common ) ) {
243                                // merge type variables
[5c14030]244                                interned_string root = 
245                                        mergeClasses( class1.update_root(), class2.update_root() ).first;
[982f95d]246                                // update bindings
247                                data1.allowWidening = widen1 && widen2;
248                                if ( common ) {
249                                        common->get_qualifiers() = Type::Qualifiers{};
250                                        data1.type = common;
251                                }
252                                bindings = bindings->set( root, data1 );
253                        } else return false;
254                } else if ( class1 && class2 ) {
255                        // both classes exist, only one bound -- merge type variables
256                        auto merged = mergeClasses( class1.get_root(), class2.get_root() );
257                        // remove subordinate binding
258                        bindings = bindings->erase( merged.second );
259                        // update root binding (narrow widening as needed, or set new binding for changed root)
260                        if ( data1.type ) {
261                                if ( data1.allowWidening != widen1 ) {
262                                        data1.allowWidening = widen1;
263                                        bindings = bindings->set( merged.first, data1 );
264                                } else if ( merged.first == class2.get_root() ) {
265                                        bindings = bindings->set( merged.first, data1 );
266                                }
267                        } else /* if ( data2.type ) */ {
268                                if ( data2.allowWidening != widen2 ) {
269                                        data2.allowWidening = widen2;
[5c14030]270                                        bindings = bindings->set( merged.first, data2 );
[982f95d]271                                } else if ( merged.first == class1.get_root() ) {
272                                        bindings = bindings->set( merged.first, data2 );
273                                }
274                        }
275                } else if ( class1 ) {
276                        // add unbound var2 to class1
277                        classes = classes->add( class2.get_root() );
278                        auto merged = mergeClasses( class1.get_root(), class2.get_root() );
279                        // update bindings (narrow as needed, or switch binding to root)
280                        if ( merged.first == class2.get_root() ) {
281                                data1.allowWidening = widen1;
282                                bindings = bindings->erase( merged.second )->set( merged.first, data1 );
283                        } else if ( data1.allowWidening != widen1 ) {
284                                bindings = bindings->set( merged.first, data1 );
285                        }
286                } else if ( class2 ) {
287                        // add unbound var1 to class1
288                        classes = classes->add( class1.get_root() );
289                        auto merged = mergeClasses( class1.get_root(), class2.get_root() );
290                        // update bindings (narrow as needed, or switch binding to root)
291                        if ( merged.first == class1.get_root() ) {
292                                data2.allowWidening = widen2;
293                                bindings = bindings->erase( merged.second )->set( merged.first, data2 );
294                        } else if ( data2.allowWidening != widen2 ) {
295                                bindings = bindings->set( merged.first, data2 );
296                        }
297                } else {
298                        // make new class with pair of unbound vars
299                        classes = classes->add( class1.get_root() )->add( class2.get_root() );
300                        auto merged = mergeClasses( class1.get_root(), class2.get_root() );
301                        bindings = bindings->set( merged.first, BoundType{ nullptr, widen1 && widen2, data } );
302                }
303                return true;
304        }
[a32b204]305
[8c49c0e]306        void TypeEnvironment::add( const Type::ForallList &tyDecls ) {
[d318a18]307                PRE_POST_VALIDATE
[8c49c0e]308                for ( Type::ForallList::const_iterator i = tyDecls.begin(); i != tyDecls.end(); ++i ) {
[184557e]309                        interned_string name = (*i)->get_name();
310                        classes = classes->add( name );
311                        bindings = bindings->set( name, *i );
[a32b204]312                } // for
313        }
314
[09c72d5]315        void TypeEnvironment::add( const TypeSubstitution & sub ) {
[d318a18]316                PRE_POST_VALIDATE
[184557e]317                interned_string not_found{nullptr};
318
[09c72d5]319                for ( auto p : sub ) {
[184557e]320                        interned_string var = p.first;
321                       
322                        // filter overlapping classes out of existing environment
[d318a18]323                        // xxx - this is a very shady assumption, but has worked for a long time...
[5c14030]324                        interned_string root = classes->find_or_default( var, not_found );
[184557e]325                        if ( root != not_found ) {
326                                classes = classes->remove_class( root );
327                                bindings = bindings->erase( root );
328                        }
329
[09c72d5]330                        // Minimal assumptions. Not technically correct, but might be good enough, and
331                        // is the best we can do at the moment since information is lost in the
332                        // transition to TypeSubstitution
[184557e]333                        TypeDecl::Data data{ TypeDecl::Dtype, false };
334
335                        // add variable to class and bindings
336                        classes = classes->add( var );
[5c14030]337                        bindings = bindings->set( var, BoundType{ p.second->clone(), false, data } );
[09c72d5]338                }
339        }
340
[a32b204]341        void TypeEnvironment::makeSubstitution( TypeSubstitution &sub ) const {
[d318a18]342                PRE_POST_VALIDATE_NOM
[5c14030]343                bindings->for_each([&]( interned_string root, const BoundType& bound ){
344                        classes->for_class(root, [&]( interned_string var ) {
[184557e]345                                if ( bound.type ) {
346                                        sub.add( var, bound.type );
347                                } else if ( var != root ) {
348                                        sub.add( var, new TypeInstType{ 
349                                                Type::Qualifiers{}, root, bound.data.kind == TypeDecl::Ftype } );
350                                }
351                        });
352                });
353
[a32b204]354                sub.normalize();
355        }
356
[50377a4]357        void TypeEnvironment::print( std::ostream &os, Indenter indent ) const {
[5c14030]358                bindings->for_each([&]( interned_string root, const BoundType& bound ) {
[184557e]359                        os << "( ";
[5c14030]360                        classes->for_class( root, [&os]( interned_string var ) { os << var << " "; } );
[184557e]361                        os << ")";
362                        if ( bound.type ) {
363                                os << " -> ";
[5c14030]364                                bound.type->print( os, indent+1 );
[184557e]365                        }
366                        if ( ! bound.allowWidening ) {
367                                os << " (no widening)";
368                        }
369                        os << std::endl;
370                });
[a32b204]371        }
372
[d318a18]373        namespace {
374                // temporary representation of an equivalence class
375                struct EqvClass {
376                        std::vector<interned_string> vars;
377                        BoundType bound;
378
379                        EqvClass() = default;
380                        EqvClass(const BoundType& b) : bound{b} {}
381                };
382        }
383
[184557e]384        void TypeEnvironment::simpleCombine( const TypeEnvironment &o ) {
[d318a18]385                PRE_POST_VALIDATE
386                // check for same environment
387                if ( classes == o.classes && bindings == o.bindings ) return;
388
389                // read out equivalence classes (avoids conflicting reroots)
390                std::vector<EqvClass> ecs;
[5c14030]391                o.bindings->for_each( [&]( interned_string root, const BoundType& bound ) {
[d318a18]392                        ecs.emplace_back(bound);
393                        o.classes->for_class( root, [&]( interned_string var ) {
394                                ecs.back().vars.push_back( var );
395                        } );
396                } );
397
398                // read equivalence classes into self
399                for ( EqvClass& ec : ecs ) {
400                        // merge vars
[184557e]401                        interned_string new_root{nullptr};
[d318a18]402                        for ( interned_string var : ec.vars ) {
403                                Classes* new_classes = classes->add( var );
404                                if ( new_classes == classes ) { var = classes->find( var ); }
405                                else { classes = new_classes; }
[184557e]406                                new_root = new_root ? mergeClasses( new_root, var ).first : var;
[d318a18]407                        }
408                        // set binding
409                        bindings = bindings->set( new_root, ec.bound );
410                }
[a32b204]411        }
412
[9160cb2]413        bool TypeEnvironment::combine( const TypeEnvironment& o, const SymTab::Indexer& indexer ) {
[f89a111]414                // short-circuit for empty cases
415                if ( o.isEmpty() ) return true;
416                if ( isEmpty() ) {
417                        *this = o;
418                        return true;
419                }
420
421                /// Edit item for path state
422                struct Edit {
423                        Classes::Mode mode;   ///< Type of change to a key
424                        interned_string root; ///< New/Previous root, if addTo/remFrom node
425
426                        Edit(Classes::Mode m, interned_string r = nullptr) : mode{m}, root{r} {}
427                };
428
429                // track class changes
430                classes->reroot();
431                PRE_POST_VALIDATE
432
433                using EditEntry = std::pair<interned_string, Edit>;
434                using EditList = std::list<EditEntry>;
435                using IndexedEdits = std::vector<EditList::iterator>;
436
437                EditList edits;
438                std::unordered_map<interned_string, IndexedEdits> editIndex;
439
440                // trace path from other environment
441                const Classes* oclasses = o.classes;
442                Classes::Mode omode = oclasses->get_mode();
443                while ( omode != Classes::BASE ) {
444                        interned_string key = oclasses->get_key();
445                        IndexedEdits& forKey = editIndex[ key ];
446
447                        if ( forKey.empty() ) {
448                                // newly seen key, mark op
449                                interned_string root = ( omode == Classes::ADD || omode == Classes::REM ) ?
450                                        nullptr : oclasses->get_root();
451                                auto it = edits.emplace( edits.begin(), key, Edit{ omode, root } );
452                                forKey.push_back( move(it) );
453                        } else {
454                                auto next = forKey.back();  // edit next applied to this key
455                                Classes::Mode nmode = next->second.mode; // next action applied
456
457                                switch ( omode ) {
458                                        case Classes::ADD: {
459                                                switch ( nmode ) {
460                                                        case Classes::REM: {
461                                                                // later removal, no net change to classes
462                                                                edits.erase( next );
463                                                                forKey.pop_back();
464                                                        } break;
465                                                        case Classes::ADDTO: {
466                                                                // later merge, prefix with this addition
467                                                                auto it = edits.emplace( edits.begin(), key, Edit{ omode } );
468                                                                forKey.push_back( move(it) );
469                                                        } break;
470                                                        default: assertf( false, "inconsistent mode" );
471                                                }
472                                        } break;
473                                        case Classes::REM: {
474                                                // later addition, no net change to classes
475                                                assertf( nmode == Classes::ADD, "inconsistent mode" );
476                                                edits.erase( next );
477                                                forKey.pop_back();
478                                        } break;
479                                        case Classes::ADDTO: {
480                                                // later unmerged from same class, no net change to classes
[9160cb2]481                                                assertf( nmode == Classes::REMFROM, "inconsistent mode" );
482                                                assertf( oclasses->get_root() == next->second.root, "inconsistent tree" );
[f89a111]483                                                edits.erase( next );
484                                                forKey.pop_back();
485                                        } break;
486                                        case Classes::REMFROM: {
487                                                interned_string root = oclasses->get_root();
488                                                switch ( nmode ) {
489                                                        case Classes::REM: {
490                                                                // later removal, prefix with this unmerge
491                                                                auto it = edits.emplace( edits.begin(), key, Edit{ omode, root } );
492                                                                forKey.push_back( move(it) );
493                                                        } break;
494                                                        case Classes::ADDTO: {
495                                                                if ( root == next->second.root ) {
496                                                                        // later merged back into same class, no net change
497                                                                        edits.erase( next );
498                                                                        forKey.pop_back();
499                                                                } else {
500                                                                        // later merged into different class, prefix with this unmerge
501                                                                        auto it = edits.emplace( 
502                                                                                edits.begin(), key, Edit{ omode, root } );
503                                                                        forKey.push_back( move(it) );
504                                                                }
505                                                        } break;
506                                                        default: assertf( false, "inconsistent mode" );
507                                                }
508                                        } break;
509                                        default: assertf( false, "invalid mode" );
510                                }
511                        }
512
513                        oclasses = oclasses->get_base();
514                        omode = oclasses->get_mode();
515                }
516                assertf( oclasses == classes, "classes must be versions of the same map" );
517
518                /// Edit item for binding changes
519                struct BEdit {
520                        Bindings::Mode mode;  ///< Type of change to a key
521                        BoundType val;        ///< Updated key value, if applicable
522
523                        BEdit(Bindings::Mode m) : mode{m}, val{} {}
524                        BEdit(Bindings::Mode m, const BoundType& b) : mode{m}, val{b} {}
525                };
526
527                // track binding merges
528                bindings->reroot();
529                std::unordered_map<interned_string, BEdit> bedits; // edits to base bindings
530
531                // trace path from other environment
532                const Bindings* bbindings = o.bindings;
533                Bindings::Mode bmode = bbindings->get_mode();
534                while ( bmode != Bindings::BASE ) {
535                        interned_string key = bbindings->get_key();
536                        auto it = bedits.find( key );
537
538                        if ( it == bedits.end() ) {
539                                // newly seen key, mark operation
540                                if ( bmode == Bindings::REM ) {
[9160cb2]541                                        bedits.emplace_hint( it, key, BEdit{ bmode } );
[f89a111]542                                } else {
[9160cb2]543                                        bedits.emplace_hint( it, key, BEdit{ bmode, bbindings->get_val() } );
[f89a111]544                                }
545                        } else {
546                                Bindings::Mode& smode = it->second.mode;
547                                switch ( bmode ) {
548                                        case Bindings::REM: {
549                                                // later insertion, change to update
550                                                assertf( smode == Bindings::INS, "inconsistent mode" );
551                                                smode = Bindings::UPD;
552                                        } break;
553                                        case Bindings::INS: {
554                                                switch ( smode ) {
555                                                        case Bindings::REM: {
556                                                                // later removal, no net change to map
557                                                                bedits.erase( it );
558                                                        } break;
559                                                        case Bindings::UPD: {
560                                                                // later update collapses to insertion
561                                                                smode = Bindings::INS;
562                                                        } break;
563                                                        default: assertf( false, "inconsistent mode" );
564                                                }
565                                        } break;
566                                        case Bindings::UPD: {
567                                                // later removal or update overrides this update
568                                                assertf( smode == Bindings::REM || smode == Bindings::UPD, "inconsistent mode" );
569                                        } break;
570                                        default: assertf( false, "invalid mode" );
571                                }
572                        }
573
574                        bbindings = bbindings->get_base();
575                        bmode = bbindings->get_mode();
576                }
[9160cb2]577                assertf( bbindings == bindings, "bindings must be versions of same map" );
[f89a111]578
579                // merge typeclasses (always possible, can always merge all classes into one if the
580                // bindings unify)
581                for ( const EditEntry& edit : edits ) {
582                        interned_string key = edit.first;
583                        const Edit& e = edit.second;
584
585                        switch ( e.mode ) {
586                                case Classes::ADD: {
587                                        // add new type variable
588                                        classes = classes->add( key );
589                                        // add binding for variable
590                                        auto bit = bedits.find( key );
591                                        if ( bit != bedits.end() ) {
592                                                // take final value if it is a root in its own map
593                                                const BEdit& be = bit->second;
594                                                assertf( be.mode == Bindings::INS, "inconsistent binding" );
595                                                bindings = bindings->set( key, std::move(be.val) );
596                                                // remove update from edit set so that it isn't re-checked
597                                                bedits.erase( bit );
598                                        } else {
599                                                // otherwise just put in default binding
600                                                bindings = bindings->set( key, BoundType{} );
601                                        }
602                                } break;
603                                case Classes::REM: {
604                                        // do not remove type variable (merging)
605                                } break;
606                                case Classes::ADDTO: {
607                                        // if previous REMFROM on this key, or ADDTO on this root, may not match
608                                        // current state in `classes`
609                                        interned_string key_root = classes->find( key );
610                                        interned_string merge_root = classes->find( e.root );
611                                        // skip case where classes already merged
612                                        if ( key_root == merge_root ) break;
613                                        // merge classes and remove binding for new child
614                                        interned_string new_child = mergeClasses( key_root, merge_root ).second;
615                                        if ( bindings->count( new_child ) ) {
616                                                // add new insert edit to check merge with old value if needed
617                                                const BoundType& child_bind = bindings->get( new_child );
618                                                if ( child_bind.type ) {
619                                                        // store this insert under the original key, which must be a REM
620                                                        // binding change if present
621                                                        auto bit = bedits.find( key );
622                                                        if ( bit != bedits.end() ) {
623                                                                BEdit& be = bit->second;
624                                                                assertf( be.mode == Bindings::REM, "inconsistent binding" );
625                                                                be = BEdit{ Bindings::INS, child_bind };
626                                                        } else {
627                                                                bedits.emplace_hint( bit, key, BEdit{ Bindings::INS, child_bind } );
628                                                        }
629                                                }
630                                                // remove child binding from map
631                                                bindings = bindings->erase( new_child );
632                                        }
633                                } break;
634                                case Classes::REMFROM: {
635                                        // do not split classes
636                                } break;
637                                default: assertf( false, "invalid mode" );
638                        }
639                }
640
641                // finish merging bindings. This may fail, or may merge further classes
642                for ( const auto& entry : bedits ) {
643                        interned_string key = entry.first;
644                        const BEdit& e = entry.second;
645
646                        // skip binding removals; the ADDTO merge has taken out all the new non-roots
647                        if ( e.mode == Bindings::REM ) continue;
648                        assertf( e.mode == Bindings::UPD || e.mode == Bindings::INS, "inconsistent binding" );
649
650                        // attempt binding update
651                        interned_string root = classes->find( key );
652                        BoundType ebound = bindings->get( root );
653                        const BoundType& nbound = e.val;
654
655                        if ( ebound.type && nbound.type ) {
656                                // attempt to unify bound classes
657                                Type* common = nullptr;
658                                AssertionSet need, have;
659                                OpenVarSet openVars;
660                                if ( unifyInexact( ebound.type->clone(), nbound.type->clone(), *this, need, have, 
661                                                openVars, WidenMode{ ebound.allowWidening, nbound.allowWidening }, 
662                                                indexer, common ) ) {
663                                        // update bindings
664                                        ebound.allowWidening &= nbound.allowWidening;
665                                        if ( common ) {
666                                                common->get_qualifiers() = Type::Qualifiers{};
667                                                ebound.type = common;
668                                        }
669                                        // reset root in case updated in course of unification
670                                        bindings = bindings->set( classes->find( root ), ebound );
671                                } else return false;  // cannot unify bindings
672                        }
673                }
674
675                return true;
676        }
677
[a32b204]678        void TypeEnvironment::extractOpenVars( OpenVarSet &openVars ) const {
[5c14030]679                bindings->for_each( [&]( interned_string root, const BoundType& bound ) {
680                        classes->for_class( root, [&openVars,&bound]( interned_string var ) {
[184557e]681                                openVars[ var ] = bound.data;
682                        } );
683                } );
[a32b204]684        }
[51b7345]685
[a585396]686        void TypeEnvironment::addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars ) {
[d318a18]687                PRE_POST_VALIDATE
688                if ( classes == actualEnv.classes && bindings == actualEnv.bindings ) {
689                        // actualEnv already the same, just need to update openVars
690                        extractOpenVars( openVars );
691                        return;
692                } else assertf(classes != actualEnv.classes && bindings != actualEnv.bindings, "classes & bindings updated together");
693
694                // read out equivalence classes (avoids conflicting reroots)
695                std::vector<EqvClass> ecs;
[5c14030]696                actualEnv.bindings->for_each( [&]( interned_string root, const BoundType& bound ) {
[d318a18]697                        ecs.emplace_back(bound);
[5c14030]698                        actualEnv.classes->for_class( root, [&]( interned_string var ) {
[d318a18]699                                ecs.back().vars.push_back( var );
[184557e]700                        } );
701                } );
[d318a18]702
703                // add members of new class, setting openVars concurrently
704                for ( EqvClass& ec : ecs ) {
705                        // merge vars
706                        interned_string new_root{nullptr};
707                        for ( interned_string var : ec.vars ) {
708                                openVars[ var ] = ec.bound.data;
709                                Classes* new_classes = classes->add( var );
710                                if ( new_classes == classes ) {
711                                        // xxx - this case is a bit sketchy, but has been working
712                                        // xxx - merging the classes is a departure from previous behaviour
713                                        var = classes->find( var );
714                                } else { classes = new_classes; }
715                                new_root = new_root ? mergeClasses( new_root, var ).first : var;
716                        }
717                        // set binding without widening
718                        bindings = bindings->set( new_root, 
719                                BoundType{ maybeClone(ec.bound.type), false, ec.bound.data } );
720                }
[184557e]721        }
722
723        void TypeEnvironment::forbidWidening() {
[d318a18]724                PRE_POST_VALIDATE
[5c14030]725                bindings = bindings->mutate_each([]( const interned_string&, BoundType& c ) {
[184557e]726                        if ( c.allowWidening ) {
727                                option<BoundType> ret = c;
728                                c.allowWidening = false;
729                                return ret;
730                        } else return option<BoundType>{};
731                });
[a585396]732        }
733
[98a249fb]734        std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env ) {
735                env.print( out );
736                return out;
737        }
[f229fc2]738
739        PassVisitor<GcTracer> & operator<<( PassVisitor<GcTracer> & gc, const TypeEnvironment & env ) {
[d318a18]740                gc.pass.visit( env );
741                // for ( ClassRef c : env ) {
742                //      maybeAccept( c.get_bound().type, gc );
743                // }
[f229fc2]744                return gc;
745        }
[51b7345]746} // namespace ResolvExpr
[a32b204]747
748// Local Variables: //
749// tab-width: 4 //
750// mode: c++ //
751// compile-command: "make install" //
752// End: //
Note: See TracBrowser for help on using the repository browser.