source: src/ResolvExpr/TypeEnvironment.h @ f89a111

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

Ported combine function into new environment

  • Property mode set to 100644
File size: 10.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.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        void printAssertionSet( const AssertionSet &, std::ostream &, int indent = 0 );
81        void printOpenVarSet( const OpenVarSet &, std::ostream &, int indent = 0 );
82
83        /// A data structure for holding all the necessary information for a type binding
84        struct BoundType {
85                Type* type;
86                bool allowWidening;
87                TypeDecl::Data data;
88
89                BoundType() = default;
90                BoundType( TypeDecl* td ) : type{nullptr}, allowWidening{true}, data{td} {}
91                BoundType( Type* ty, bool aw, const TypeDecl::Data& td )
92                        : type{ty}, allowWidening{aw}, data{td} {}
93                BoundType( const BoundType& o )
94                        : type{maybeClone(o.type)}, allowWidening{o.allowWidening}, data{o.data} {}
95                BoundType( BoundType&& o ) = default;
96                BoundType& operator= (const BoundType& o) {
97                        if ( this == &o ) return *this;
98                        type = maybeClone( o.type );
99                        allowWidening = o.allowWidening;
100                        data = o.data;
101                        return *this;
102                }
103                BoundType& operator= (BoundType&& o) = default;
104        };
105
106        class TypeEnvironment;
107
108        /// A reference to an equivalence class that may be used to constitute one from its environment
109        class ClassRef {
110                friend TypeEnvironment;
111
112                const TypeEnvironment* env;  ///< Containing environment
113                interned_string root;        ///< Name of root type
114
115        public:
116                ClassRef() : env(nullptr), root(nullptr) {}
117                ClassRef( const TypeEnvironment* env, interned_string root ) : env(env), root(root) {}
118
119                /// Gets the root of the reference equivalence class;
120                interned_string get_root() const { return root; }
121
122                /// Ensures that root is still the representative element of this typeclass;
123                /// undefined behaviour if called without referenced typeclass; returns new root
124                inline interned_string update_root();
125
126                /// Gets the type variables of the referenced equivalence class, empty list for none
127                template<typename T = std::vector<interned_string>>
128                inline T get_vars() const;
129
130                /// Gets the bound type information of the referenced equivalence class, default if none
131                inline BoundType get_bound() const;
132
133                // Check that there is a referenced typeclass
134                explicit operator bool() const { return env != nullptr; }
135
136                bool operator== (const ClassRef& o) const { return env == o.env && root == o.root; }
137                bool operator!= (const ClassRef& o) const { return !(*this == o); }
138        };
139
140        class ValidateGuard;
141
142        class TypeEnvironment {
143                friend ClassRef;
144                friend GcTracer;
145               
146                /// Backing storage for equivalence classes
147                using Classes = PersistentDisjointSet<interned_string>;
148                /// Type bindings included in this environment (from class root)
149                using Bindings = PersistentMap<interned_string, BoundType>;
150
151                /// Sets of equivalent type variables, stored by name
152                Classes* classes;
153                /// Bindings from roots of equivalence classes to type binding information.
154                /// All roots have a binding so that the list of classes can be reconstituted, though these
155                /// may be null.
156                Bindings* bindings;
157
158                // for debugging
159                friend ValidateGuard;
160                const char* last_fn = "<none>";
161
162                /// Merges the classes rooted at root1 and root2, returning a pair containing the root and
163                /// child of the bound class. Does not check for validity of merge.
164                std::pair<interned_string, interned_string> mergeClasses( 
165                        interned_string root1, interned_string root2 );
166
167        public:
168                class iterator : public std::iterator<
169                                std::forward_iterator_tag, 
170                                ClassRef, 
171                                std::iterator_traits<Bindings::iterator>::difference_type,
172                                ClassRef,
173                                ClassRef> {
174                        friend TypeEnvironment;
175                       
176                        const TypeEnvironment* env;
177                        Bindings::iterator it;
178
179                        iterator(const TypeEnvironment* e, Bindings::iterator&& i) : env(e), it(std::move(i)) {}
180
181                        ClassRef ref() const { return { env, it->first }; }
182                public:
183                        iterator() = default;
184
185                        reference operator* () { return ref(); }
186                        pointer operator-> () { return ref(); }
187
188                        iterator& operator++ () { ++it; return *this; }
189                        iterator operator++ (int) { iterator tmp = *this; ++(*this); return tmp; }
190
191                        bool operator== (const iterator& o) const { return env == o.env && it == o.it; }
192                        bool operator!= (const iterator& o) const { return !(*this == o); }
193                };
194
195                /// Finds a reference to the class containing `var`, invalid if none such.
196                /// returned root variable will be valid regardless
197                ClassRef lookup( interned_string var ) const;
198
199                /// Binds a type variable to a type; returns false if fails
200                bool bindVar( TypeInstType* typeInst, Type* bindTo, const TypeDecl::Data& data, 
201                        AssertionSet& need, AssertionSet& have, const OpenVarSet& openVars, 
202                        WidenMode widenMode, const SymTab::Indexer& indexer );
203               
204                /// Binds two type variables together; returns false if fails
205                bool bindVarToVar( TypeInstType* var1, TypeInstType* var2, const TypeDecl::Data& data, 
206                        AssertionSet& need, AssertionSet& have, const OpenVarSet& openVars, 
207                        WidenMode widenMode, const SymTab::Indexer& indexer );
208
209        public:
210                TypeEnvironment() : classes{ new Classes{} }, bindings{ new Bindings{} } {}
211
212                void add( const Type::ForallList &tyDecls );
213                void add( const TypeSubstitution & sub );
214                template< typename SynTreeClass > int apply( SynTreeClass *&type ) const;
215                template< typename SynTreeClass > int applyFree( SynTreeClass *&type ) const;
216                void makeSubstitution( TypeSubstitution &result ) const;
217                bool isEmpty() const { return classes->empty(); }
218                void print( std::ostream &os, Indenter indent = {} ) const;
219       
220                /// Combines two environments without checking invariants.
221                /// Caller should ensure environments do not share type variables.
222                void simpleCombine( const TypeEnvironment &second );
223
224                /// Combines two environments, checking compatibility. Both environments must be versioned
225                /// from the same initial environment.
226                /// Returns false if unsuccessful, but does NOT roll back partial changes
227                bool combine( const TypeEnvironment& o, const SymTab::Indexer& indexer );
228       
229                void extractOpenVars( OpenVarSet &openVars ) const;
230                TypeEnvironment *clone() const { return new TypeEnvironment( *this ); }
231
232                /// Iteratively adds the environment of a new actual (with allowWidening = false),
233                /// and extracts open variables.
234                void addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars );
235
236                /// Disallows widening for all bindings in the environment
237                void forbidWidening();
238
239                iterator begin() const { return { this, bindings->begin() }; }
240                iterator end() const { return { this, bindings->end() }; }
241        };
242
243        interned_string ClassRef::update_root() { return root = env->classes->find( root ); }
244
245        template<typename T>
246        T ClassRef::get_vars() const {
247                T vars;
248                env->classes->for_class( root, [&vars]( interned_string var ) {
249                        vars.insert( vars.end(), var );
250                } );
251                return vars;
252        }
253
254        BoundType ClassRef::get_bound() const {
255                return env->bindings->get_or_default( root, BoundType{} );
256        }
257
258        template< typename SynTreeClass >
259        int TypeEnvironment::apply( SynTreeClass *&type ) const {
260                TypeSubstitution sub;
261                makeSubstitution( sub );
262                return sub.apply( type );
263        }
264
265        template< typename SynTreeClass >
266        int TypeEnvironment::applyFree( SynTreeClass *&type ) const {
267                TypeSubstitution sub;
268                makeSubstitution( sub );
269                return sub.applyFree( type );
270        }
271
272        std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env );
273
274        PassVisitor<GcTracer> & operator<<( PassVisitor<GcTracer> & gc, const TypeEnvironment & env );
275} // namespace ResolvExpr
276
277// Local Variables: //
278// tab-width: 4 //
279// mode: c++ //
280// compile-command: "make install" //
281// End: //
Note: See TracBrowser for help on using the repository browser.