source: src/ResolvExpr/TypeEnvironment.h @ 1a59641

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

Fix open var handling in BF assn resolution; memory usage reasonable again

  • Property mode set to 100644
File size: 11.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.h --
8//
9// Author           : Aaron B. Moss
10// Created On       : Sun May 17 12:24:58 2015
11// Last Modified By : Aaron B. Moss
12// Last Modified On : Fri Jun 29 16:00:00 2018
13// Update Count     : 5
14//
15
16#pragma once
17
18#include <iostream>                        // for ostream
19#include <iterator>
20#include <list>                            // for list, list<>::iterator, list<>...
21#include <map>                             // for map, map<>::value_compare
22#include <set>                             // for set
23#include <string>                          // for string
24#include <utility>                         // for pair
25#include <vector>                          // for vector
26
27#include "WidenMode.h"                 // for WidenMode
28
29#include "Common/InternedString.h"         // for interned_string
30#include "Common/PersistentDisjointSet.h"  // for PersistentDisjointSet
31#include "Common/PersistentMap.h"          // for PersistentMap
32#include "SynTree/Declaration.h"           // for TypeDecl::Data, DeclarationWit...
33#include "SynTree/SynTree.h"               // for UniqueId
34#include "SynTree/Type.h"                  // for Type, TypeInstType, Type::ForallList
35#include "SynTree/TypeSubstitution.h"      // for TypeSubstitution
36
37template< typename Pass > class PassVisitor;
38class GcTracer;
39namespace SymTab { class Indexer; }
40
41namespace ResolvExpr {
42        // adding this comparison operator significantly improves assertion resolution run time for
43        // some cases. The current resolution algorithm's speed partially depends on the order of
44        // assertions. Assertions which have fewer possible matches should appear before
45        // assertions which have more possible matches. This seems to imply that this could
46        // be further improved by providing an indexer as an additional argument and ordering based
47        // on the number of matches of the same kind (object, function) for the names of the
48        // declarations.
49        //
50        // I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this
51        // comparator.
52        //
53        // Note: since this compares pointers for position, minor changes in the source file that affect
54        // memory layout can alter compilation time in unpredictable ways. For example, the placement
55        // of a line directive can reorder type pointers with respect to each other so that assertions
56        // are seen in different orders, causing a potentially different number of unification calls
57        // when resolving assertions. I've seen a TU go from 36 seconds to 27 seconds by reordering
58        // line directives alone, so it would be nice to fix this comparison so that assertions compare
59        // more consistently. I've tried to modify this to compare on mangle name instead of type as
60        // the second comparator, but this causes some assertions to never be recorded. More
61        // investigation is needed.
62        struct AssertCompare {
63                bool operator()( DeclarationWithType * d1, DeclarationWithType * d2 ) const {
64                        int cmp = d1->get_name().compare( d2->get_name() );
65                        return cmp < 0 ||
66                                ( cmp == 0 && d1->get_type() < d2->get_type() );
67                }
68        };
69        struct AssertionSetValue {
70                bool isUsed;
71                // chain of Unique IDs of the assertion declarations. The first ID in the chain is the ID
72                // of an assertion on the current type, with each successive ID being the ID of an
73                // assertion pulled in by the previous ID. The last ID in the chain is the ID of the
74                // assertion that pulled in the current assertion.
75                std::list< UniqueId > idChain;
76        };
77        typedef std::map< DeclarationWithType*, AssertionSetValue, AssertCompare > AssertionSet;
78        typedef std::map< std::string, TypeDecl::Data > OpenVarSet;
79
80        /// merges one set of open vars into another
81        static inline void mergeOpenVars( OpenVarSet& dst, const OpenVarSet& src ) {
82                for ( const auto& entry : src ) { dst[ entry.first ] = entry.second; }
83        }
84
85        void printAssertionSet( const AssertionSet &, std::ostream &, int indent = 0 );
86        void printOpenVarSet( const OpenVarSet &, std::ostream &, int indent = 0 );
87
88        /// A data structure for holding all the necessary information for a type binding
89        struct BoundType {
90                Type* type;
91                bool allowWidening;
92                TypeDecl::Data data;
93
94                BoundType() = default;
95                BoundType( TypeDecl* td ) : type{nullptr}, allowWidening{true}, data{td} {}
96                BoundType( Type* ty, bool aw, const TypeDecl::Data& td )
97                        : type{ty}, allowWidening{aw}, data{td} {}
98                BoundType( const BoundType& o )
99                        : type{maybeClone(o.type)}, allowWidening{o.allowWidening}, data{o.data} {}
100                BoundType( BoundType&& o ) = default;
101                BoundType& operator= (const BoundType& o) {
102                        if ( this == &o ) return *this;
103                        type = maybeClone( o.type );
104                        allowWidening = o.allowWidening;
105                        data = o.data;
106                        return *this;
107                }
108                BoundType& operator= (BoundType&& o) = default;
109        };
110
111        class TypeEnvironment;
112
113        /// A reference to an equivalence class that may be used to constitute one from its environment
114        class ClassRef {
115                friend TypeEnvironment;
116
117                const TypeEnvironment* env;  ///< Containing environment
118                interned_string root;        ///< Name of root type
119
120        public:
121                ClassRef() : env(nullptr), root(nullptr) {}
122                ClassRef( const TypeEnvironment* env, interned_string root ) : env(env), root(root) {}
123
124                /// Gets the root of the reference equivalence class;
125                interned_string get_root() const { return root; }
126
127                /// Ensures that root is still the representative element of this typeclass;
128                /// undefined behaviour if called without referenced typeclass; returns new root
129                inline interned_string update_root();
130
131                /// Gets the type variables of the referenced equivalence class, empty list for none
132                template<typename T = std::vector<interned_string>>
133                inline T get_vars() const;
134
135                /// Gets the bound type information of the referenced equivalence class, default if none
136                inline BoundType get_bound() const;
137
138                // Check that there is a referenced typeclass
139                explicit operator bool() const { return env != nullptr; }
140
141                bool operator== (const ClassRef& o) const { return env == o.env && root == o.root; }
142                bool operator!= (const ClassRef& o) const { return !(*this == o); }
143        };
144
145        //#define EXPENSIVE_ENV_VALIDATION
146        #ifdef EXPENSIVE_ENV_VALIDATION
147        class ValidateGuard;
148        #endif
149
150        class TypeEnvironment {
151                friend ClassRef;
152                friend GcTracer;
153               
154                /// Backing storage for equivalence classes
155                using Classes = PersistentDisjointSet<interned_string>;
156                /// Type bindings included in this environment (from class root)
157                using Bindings = PersistentMap<interned_string, BoundType>;
158
159                /// Sets of equivalent type variables, stored by name
160                Classes* classes;
161                /// Bindings from roots of equivalence classes to type binding information.
162                /// All roots have a binding so that the list of classes can be reconstituted, though these
163                /// may be null.
164                Bindings* bindings;
165
166                #ifdef EXPENSIVE_ENV_VALIDATION
167                /// for debugging
168                friend ValidateGuard;
169                const char* last_fn = "<none>";
170                #endif
171
172                /// Merges the classes rooted at root1 and root2, returning a pair containing the root and
173                /// child of the bound class. Does not check for validity of merge.
174                std::pair<interned_string, interned_string> mergeClasses( 
175                        interned_string root1, interned_string root2 );
176
177        public:
178                class iterator : public std::iterator<
179                                std::forward_iterator_tag, 
180                                ClassRef, 
181                                std::iterator_traits<Bindings::iterator>::difference_type,
182                                ClassRef,
183                                ClassRef> {
184                        friend TypeEnvironment;
185                       
186                        const TypeEnvironment* env;
187                        Bindings::iterator it;
188
189                        iterator(const TypeEnvironment* e, Bindings::iterator&& i) : env(e), it(std::move(i)) {}
190
191                        ClassRef ref() const { return { env, it->first }; }
192                public:
193                        iterator() = default;
194
195                        reference operator* () { return ref(); }
196                        pointer operator-> () { return ref(); }
197
198                        iterator& operator++ () { ++it; return *this; }
199                        iterator operator++ (int) { iterator tmp = *this; ++(*this); return tmp; }
200
201                        bool operator== (const iterator& o) const { return env == o.env && it == o.it; }
202                        bool operator!= (const iterator& o) const { return !(*this == o); }
203                };
204
205                /// Finds a reference to the class containing `var`, invalid if none such.
206                /// returned root variable will be valid regardless
207                ClassRef lookup( interned_string var ) const;
208
209                /// Binds a type variable to a type; returns false if fails
210                bool bindVar( TypeInstType* typeInst, Type* bindTo, const TypeDecl::Data& data, 
211                        AssertionSet& need, AssertionSet& have, const OpenVarSet& openVars, 
212                        WidenMode widenMode, const SymTab::Indexer& indexer );
213               
214                /// Binds two type variables together; returns false if fails
215                bool bindVarToVar( TypeInstType* var1, TypeInstType* var2, const TypeDecl::Data& data, 
216                        AssertionSet& need, AssertionSet& have, const OpenVarSet& openVars, 
217                        WidenMode widenMode, const SymTab::Indexer& indexer );
218
219        public:
220                TypeEnvironment() : classes{ new Classes{} }, bindings{ new Bindings{} } {}
221
222                void add( const Type::ForallList &tyDecls );
223                void add( const TypeSubstitution & sub );
224                template< typename SynTreeClass > int apply( SynTreeClass *&type ) const;
225                template< typename SynTreeClass > int applyFree( SynTreeClass *&type ) const;
226                void makeSubstitution( TypeSubstitution &result ) const;
227                bool isEmpty() const { return classes->empty(); }
228                void print( std::ostream &os, Indenter indent = {} ) const;
229       
230                /// Combines two environments without checking invariants.
231                /// Caller should ensure environments do not share type variables.
232                void simpleCombine( const TypeEnvironment &second );
233
234                /// Combines two environments, checking compatibility. Both environments must be versioned
235                /// from the same initial environment.
236                /// Returns false if unsuccessful, but does NOT roll back partial changes
237                bool combine( const TypeEnvironment& o, OpenVarSet& openVars, 
238                        const SymTab::Indexer& indexer );
239       
240                void extractOpenVars( OpenVarSet &openVars ) const;
241                TypeEnvironment *clone() const { return new TypeEnvironment( *this ); }
242
243                /// Iteratively adds the environment of a new actual (with allowWidening = false),
244                /// and extracts open variables.
245                void addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars );
246
247                /// Disallows widening for all bindings in the environment
248                void forbidWidening();
249
250                iterator begin() const { return { this, bindings->begin() }; }
251                iterator end() const { return { this, bindings->end() }; }
252        };
253
254        interned_string ClassRef::update_root() { return root = env->classes->find( root ); }
255
256        template<typename T>
257        T ClassRef::get_vars() const {
258                T vars;
259                env->classes->for_class( root, [&vars]( interned_string var ) {
260                        vars.insert( vars.end(), var );
261                } );
262                return vars;
263        }
264
265        BoundType ClassRef::get_bound() const {
266                return env->bindings->get_or_default( root, BoundType{} );
267        }
268
269        template< typename SynTreeClass >
270        int TypeEnvironment::apply( SynTreeClass *&type ) const {
271                TypeSubstitution sub;
272                makeSubstitution( sub );
273                return sub.apply( type );
274        }
275
276        template< typename SynTreeClass >
277        int TypeEnvironment::applyFree( SynTreeClass *&type ) const {
278                TypeSubstitution sub;
279                makeSubstitution( sub );
280                return sub.applyFree( type );
281        }
282
283        std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env );
284
285        PassVisitor<GcTracer> & operator<<( PassVisitor<GcTracer> & gc, const TypeEnvironment & env );
286} // namespace ResolvExpr
287
288// Local Variables: //
289// tab-width: 4 //
290// mode: c++ //
291// compile-command: "make install" //
292// End: //
Note: See TracBrowser for help on using the repository browser.