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 | |
---|
37 | template< typename Pass > class PassVisitor; |
---|
38 | class GcTracer; |
---|
39 | namespace SymTab { class Indexer; } |
---|
40 | |
---|
41 | namespace 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: // |
---|