summaryrefslogtreecommitdiffstatshomepage
path: root/3rdparty/bgfx/3rdparty/spirv-tools/source/fuzz/equivalence_relation.h
diff options
context:
space:
mode:
Diffstat (limited to '3rdparty/bgfx/3rdparty/spirv-tools/source/fuzz/equivalence_relation.h')
-rw-r--r--3rdparty/bgfx/3rdparty/spirv-tools/source/fuzz/equivalence_relation.h232
1 files changed, 232 insertions, 0 deletions
diff --git a/3rdparty/bgfx/3rdparty/spirv-tools/source/fuzz/equivalence_relation.h b/3rdparty/bgfx/3rdparty/spirv-tools/source/fuzz/equivalence_relation.h
new file mode 100644
index 00000000000..4f7eff1d409
--- /dev/null
+++ b/3rdparty/bgfx/3rdparty/spirv-tools/source/fuzz/equivalence_relation.h
@@ -0,0 +1,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_