1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
|
// Copyright (c) 2019 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#ifndef SOURCE_FUZZ_EQUIVALENCE_RELATION_H_
#define SOURCE_FUZZ_EQUIVALENCE_RELATION_H_
#include <memory>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include "source/util/make_unique.h"
namespace spvtools {
namespace fuzz {
// A class for representing an equivalence relation on objects of type |T|,
// which should be a value type. The type |T| is required to have a copy
// constructor, and |PointerHashT| and |PointerEqualsT| must be functors
// providing hashing and equality testing functionality for pointers to objects
// of type |T|.
//
// A disjoint-set (a.k.a. union-find or merge-find) data structure is used to
// represent the equivalence relation. Path compression is used. Union by
// rank/size is not used.
//
// Each disjoint set is represented as a tree, rooted at the representative
// of the set.
//
// Getting the representative of a value simply requires chasing parent pointers
// from the value until you reach the root.
//
// Checking equivalence of two elements requires checking that the
// representatives are equal.
//
// Traversing the tree rooted at a value's representative visits the value's
// equivalence class.
//
// |PointerHashT| and |PointerEqualsT| are used to define *equality* between
// values, and otherwise are *not* used to define the equivalence relation
// (except that equal values are equivalent). The equivalence relation is
// constructed by repeatedly adding pairs of (typically non-equal) values that
// are deemed to be equivalent.
//
// For example in an equivalence relation on integers, 1 and 5 might be added
// as equivalent, so that IsEquivalent(1, 5) holds, because they represent
// IDs in a SPIR-V binary that are known to contain the same value at run time,
// but clearly 1 != 5. Since 1 and 1 are equal, IsEquivalent(1, 1) will also
// hold.
//
// Each unique (up to equality) value added to the relation is copied into
// |owned_values_|, so there is one canonical memory address per unique value.
// Uniqueness is ensured by storing (and checking) a set of pointers to these
// values in |value_set_|, which uses |PointerHashT| and |PointerEqualsT|.
//
// |parent_| and |children_| encode the equivalence relation, i.e., the trees.
template <typename T, typename PointerHashT, typename PointerEqualsT>
class EquivalenceRelation {
public:
// Merges the equivalence classes associated with |value1| and |value2|.
// If any of these values was not previously in the equivalence relation, it
// is added to the pool of values known to be in the relation.
void MakeEquivalent(const T& value1, const T& value2) {
// Register each value if necessary.
for (auto value : {value1, value2}) {
if (!Exists(value)) {
// Register the value in the equivalence relation. This relies on
// T having a copy constructor.
auto unique_pointer_to_value = MakeUnique<T>(value);
auto pointer_to_value = unique_pointer_to_value.get();
owned_values_.push_back(std::move(unique_pointer_to_value));
value_set_.insert(pointer_to_value);
// Initially say that the value is its own parent and that it has no
// children.
assert(pointer_to_value && "Representatives should never be null.");
parent_[pointer_to_value] = pointer_to_value;
children_[pointer_to_value] = std::unordered_set<const T*>();
}
}
// Look up canonical pointers to each of the values in the value pool.
const T* value1_ptr = *value_set_.find(&value1);
const T* value2_ptr = *value_set_.find(&value2);
// If the values turn out to be identical, they are already in the same
// equivalence class so there is nothing to do.
if (value1_ptr == value2_ptr) {
return;
}
// Find the representative for each value's equivalence class, and if they
// are not already in the same class, make one the parent of the other.
const T* representative1 = Find(value1_ptr);
const T* representative2 = Find(value2_ptr);
assert(representative1 && "Representatives should never be null.");
assert(representative2 && "Representatives should never be null.");
if (representative1 != representative2) {
parent_[representative1] = representative2;
children_[representative2].insert(representative1);
}
}
// Returns exactly one representative per equivalence class.
std::vector<const T*> GetEquivalenceClassRepresentatives() const {
std::vector<const T*> result;
for (auto& value : owned_values_) {
if (parent_[value.get()] == value.get()) {
result.push_back(value.get());
}
}
return result;
}
// Returns pointers to all values in the equivalence class of |value|, which
// must already be part of the equivalence relation.
std::vector<const T*> GetEquivalenceClass(const T& value) const {
assert(Exists(value));
std::vector<const T*> result;
// Traverse the tree of values rooted at the representative of the
// equivalence class to which |value| belongs, and collect up all the values
// that are encountered. This constitutes the whole equivalence class.
std::vector<const T*> stack;
stack.push_back(Find(*value_set_.find(&value)));
while (!stack.empty()) {
const T* item = stack.back();
result.push_back(item);
stack.pop_back();
for (auto child : children_[item]) {
stack.push_back(child);
}
}
return result;
}
// Returns true if and only if |value1| and |value2| are in the same
// equivalence class. Both values must already be known to the equivalence
// relation.
bool IsEquivalent(const T& value1, const T& value2) const {
return Find(&value1) == Find(&value2);
}
// Returns all values known to be part of the equivalence relation.
std::vector<const T*> GetAllKnownValues() const {
std::vector<const T*> result;
for (auto& value : owned_values_) {
result.push_back(value.get());
}
return result;
}
// Returns true if and only if |value| is known to be part of the equivalence
// relation.
bool Exists(const T& value) const {
return value_set_.find(&value) != value_set_.end();
}
private:
// Returns the representative of the equivalence class of |value|, which must
// already be known to the equivalence relation. This is the 'Find' operation
// in a classic union-find data structure.
const T* Find(const T* value) const {
assert(Exists(*value));
// Get the canonical pointer to the value from the value pool.
const T* known_value = *value_set_.find(value);
assert(parent_[known_value] && "Every known value should have a parent.");
// Compute the result by chasing parents until we find a value that is its
// own parent.
const T* result = known_value;
while (parent_[result] != result) {
result = parent_[result];
}
assert(result && "Representatives should never be null.");
// At this point, |result| is the representative of the equivalence class.
// Now perform the 'path compression' optimization by doing another pass up
// the parent chain, setting the parent of each node to be the
// representative, and rewriting children correspondingly.
const T* current = known_value;
while (parent_[current] != result) {
const T* next = parent_[current];
parent_[current] = result;
children_[result].insert(current);
children_[next].erase(current);
current = next;
}
return result;
}
// Maps every value to a parent. The representative of an equivalence class
// is its own parent. A value's representative can be found by walking its
// chain of ancestors.
//
// Mutable because the intuitively const method, 'Find', performs path
// compression.
mutable std::unordered_map<const T*, const T*> parent_;
// Stores the children of each value. This allows the equivalence class of
// a value to be calculated by traversing all descendents of the class's
// representative.
//
// Mutable because the intuitively const method, 'Find', performs path
// compression.
mutable std::unordered_map<const T*, std::unordered_set<const T*>> children_;
// The values known to the equivalence relation are alloacated in
// |owned_values_|, and |value_pool_| provides (via |PointerHashT| and
// |PointerEqualsT|) a means for mapping a value of interest to a pointer
// into an equivalent value in |owned_values_|.
std::unordered_set<const T*, PointerHashT, PointerEqualsT> value_set_;
std::vector<std::unique_ptr<T>> owned_values_;
};
} // namespace fuzz
} // namespace spvtools
#endif // SOURCE_FUZZ_EQUIVALENCE_RELATION_H_
|