layers: Give compatible DSL unique ids

Store compatible DescriptorSetLayout definitions in a dictionary with
unique IDs.  Use IDs for trivial accept compatibility validation.

Change-Id: I1085a354d36d1a733f79adb4459decf8cf0a55c1

4 files changed, 224 insertions, 3 deletions

diff --git a/layers/descriptor_sets.cpp b/layers/descriptor_sets.cpp
index 96b75023..9f4d3a42 100644
--- a/layers/descriptor_sets.cpp
+++ b/layers/descriptor_sets.cpp
@@ -23,6 +23,7 @@
 #define NOMINMAX
 
 #include "descriptor_sets.h"
+#include "hash_vk_types.h"
 #include "vk_enum_string_helper.h"
 #include "vk_safe_struct.h"
 #include "buffer_validation.h"
@@ -36,6 +37,31 @@ struct BindingNumCmp {
     }
 };
 
+using DescriptorSetLayoutDef = cvdescriptorset::DescriptorSetLayoutDef;
+using DescriptorSetLayoutId = cvdescriptorset::DescriptorSetLayoutId;
+
+namespace std {
+template <>
+struct hash<DescriptorSetLayoutDef> : public hash_util::HasHashMember<DescriptorSetLayoutDef> {};
+}  // namespace std
+
+// Note: std::equal_to is looking for operator == to be defined in the innermost namespace enclosing DescriptorSetLayoutDef
+//       (i.e. cvdescriptorset) or in the class, base, or containing classes, and does *not* look in :: for it.
+static std::unordered_map<DescriptorSetLayoutDef, DescriptorSetLayoutId, std::hash<DescriptorSetLayoutDef>,
+                          std::equal_to<DescriptorSetLayoutDef>>
+    descriptor_set_layout_dict;
+
+DescriptorSetLayoutId get_definition_id(const VkDescriptorSetLayoutCreateInfo *p_create_info) {
+    DescriptorSetLayoutId from_input = std::make_shared<DescriptorSetLayoutDef>(p_create_info);
+
+    // Insert takes care of the "unique" id part by rejecting the insert if a key matching the DSL def exists, but returning us
+    // the entry with the extant shared_pointer(id->def) instead.
+    auto insert_pair = descriptor_set_layout_dict.insert({*from_input, from_input});
+
+    // This *awful* syntax takes the Iterator from the <It, bool> pair returned by insert, and extracts the value from the
+    // <key, value> pair of the Iterator
+    return insert_pair.first->second;
+}
 // Construct DescriptorSetLayout instance from given create info
 // Proactively reserve and resize as possible, as the reallocation was visible in profiling
 cvdescriptorset::DescriptorSetLayoutDef::DescriptorSetLayoutDef(const VkDescriptorSetLayoutCreateInfo *p_create_info)
@@ -101,6 +127,14 @@ cvdescriptorset::DescriptorSetLayoutDef::DescriptorSetLayoutDef(const VkDescript
     }
 }
 
+size_t cvdescriptorset::DescriptorSetLayoutDef::hash() const {
+    hash_util::HashCombiner hc;
+    hc << flags_;
+    hc.Combine(bindings_);
+    return hc.Value();
+}
+//
+
 // Return valid index or "end" i.e. binding_count_;
 // The asserts in "Get" are reduced to the set where no valid answer(like null or 0) could be given
 // Common code for all binding lookups.
@@ -190,8 +224,12 @@ bool cvdescriptorset::DescriptorSetLayout::IsCompatible(DescriptorSetLayout cons
                                                         std::string *error_msg) const {
     // Trivial case
     if (layout_ == rh_ds_layout->GetDescriptorSetLayout()) return true;
-    return get_layout_def()->IsCompatible(layout_, rh_ds_layout->GetDescriptorSetLayout(), rh_ds_layout->get_layout_def(),
-                                          error_msg);
+    if (get_layout_def() == rh_ds_layout->get_layout_def()) return true;
+    bool detailed_compat_check =
+        get_layout_def()->IsCompatible(layout_, rh_ds_layout->GetDescriptorSetLayout(), rh_ds_layout->get_layout_def(), error_msg);
+    // The detailed check should never tell us mismatching DSL are compatible
+    assert(!detailed_compat_check);
+    return detailed_compat_check;
 }
 
 bool cvdescriptorset::DescriptorSetLayoutDef::IsCompatible(VkDescriptorSetLayout ds_layout, VkDescriptorSetLayout rh_ds_layout,
@@ -205,6 +243,7 @@ bool cvdescriptorset::DescriptorSetLayoutDef::IsCompatible(VkDescriptorSetLayout
         *error_msg = error_str.str();
         return false;  // trivial fail case
     }
+
     // Descriptor counts match so need to go through bindings one-by-one
     //  and verify that type and stageFlags match
     for (auto binding : bindings_) {
@@ -299,7 +338,7 @@ bool cvdescriptorset::DescriptorSetLayoutDef::VerifyUpdateConsistency(uint32_t c
 // handle invariant portion
 cvdescriptorset::DescriptorSetLayout::DescriptorSetLayout(const VkDescriptorSetLayoutCreateInfo *p_create_info,
                                                           const VkDescriptorSetLayout layout)
-    : layout_(layout), layout_destroyed_(false), layout_id_(std::make_shared<DescriptorSetLayoutDef>(p_create_info)) {}
+    : layout_(layout), layout_destroyed_(false), layout_id_(get_definition_id(p_create_info)) {}
 
 // Validate descriptor set layout create info
 bool cvdescriptorset::DescriptorSetLayout::ValidateCreateInfo(const debug_report_data *report_data,
diff --git a/layers/descriptor_sets.h b/layers/descriptor_sets.h
index a20d602d..aa11c524 100644
--- a/layers/descriptor_sets.h
+++ b/layers/descriptor_sets.h
@@ -24,6 +24,7 @@
 #include "core_validation_error_enums.h"
 #include "vk_validation_error_messages.h"
 #include "core_validation_types.h"
+#include "hash_vk_types.h"
 #include "vk_layer_logging.h"
 #include "vk_layer_utils.h"
 #include "vk_safe_struct.h"
@@ -173,6 +174,10 @@ class DescriptorSetLayoutDef {
     BindingTypeStats binding_type_stats_;
 };
 
+static bool operator==(const DescriptorSetLayoutDef &lhs, const DescriptorSetLayoutDef &rhs) {
+    return (lhs.GetCreateFlags() == rhs.GetCreateFlags()) && (lhs.GetBindings() == rhs.GetBindings());
+}
+
 using DescriptorSetLayoutId = std::shared_ptr<DescriptorSetLayoutDef>;
 
 class DescriptorSetLayout {
diff --git a/layers/hash_util.h b/layers/hash_util.h
new file mode 100644
index 00000000..e5f995a1
--- /dev/null
+++ b/layers/hash_util.h
@@ -0,0 +1,114 @@
+/* Copyright (c) 2015-2016 The Khronos Group Inc.
+ * Copyright (c) 2015-2016 Valve Corporation
+ * Copyright (c) 2015-2016 LunarG, Inc.
+ * Copyright (C) 2015-2016 Google Inc.
+ *
+ * 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.
+ *
+ * Author: John Zulauf <jzulauf@lunarg.com>
+ */
+#ifndef HASH_UTIL_H_
+#define HASH_UTIL_H_
+
+#define NOMINMAX
+#include <cstdint>
+#include <functional>
+#include <limits>
+#include <type_traits>
+#include <vector>
+
+// Hash and equality utilities for supporting hashing containers (e.g. unordered_set, unordered_map)
+namespace hash_util {
+
+// True iff both pointers are null or both are non-null
+template <typename T>
+bool similar_for_nullity(const T *const lhs, const T *const rhs) {
+    return ((lhs != nullptr) && (rhs != nullptr)) || ((lhs == nullptr) && (rhs == nullptr));
+}
+
+// Wrap std hash to avoid manual casts for the holes in std::hash (in C++11)
+template <typename Value>
+size_t HashWithUnderlying(Value value, typename std::enable_if<!std::is_enum<Value>::value, void *>::type = nullptr) {
+    return std::hash<Value>()(value);
+}
+
+template <typename Value>
+size_t HashWithUnderlying(Value value, typename std::enable_if<std::is_enum<Value>::value, void *>::type = nullptr) {
+    using Underlying = typename std::underlying_type<Value>::type;
+    return std::hash<Underlying>()(static_cast<const Underlying &>(value));
+}
+
+class HashCombiner {
+   public:
+    using Key = size_t;
+
+    template <typename Value>
+    struct WrappedHash {
+        size_t operator()(const Value &value) const { return HashWithUnderlying(value); }
+    };
+
+    HashCombiner(Key combined = 0) : combined_(combined) {}
+    // magic and combination algorithm based on boost::hash_combine
+    // http://www.boost.org/doc/libs/1_43_0/doc/html/hash/reference.html#boost.hash_combine
+    // Magic value is 2^size / ((1-sqrt(5)/2)
+    static const uint64_t kMagic = sizeof(Key) > 4 ? Key(0x9e3779b97f4a7c16UL) : Key(0x9e3779b9U);
+
+    // If you need to override the default hash
+    template <typename Value, typename Hasher = WrappedHash<Value>>
+    HashCombiner &Combine(const Value &value) {
+        combined_ ^= Hasher()(value) + kMagic + (combined_ << 6) + (combined_ >> 2);
+        return *this;
+    }
+
+    template <typename Iterator, typename Hasher = WrappedHash<typename std::iterator_traits<Iterator>::value_type>>
+    HashCombiner &Combine(Iterator first, Iterator end) {
+        using Value = typename std::iterator_traits<Iterator>::value_type;
+        auto current = first;
+        for (; current != end; ++current) {
+            Combine<Value, Hasher>(*current);
+        }
+        return *this;
+    }
+
+    template <typename Value, typename Hasher = WrappedHash<Value>>
+    HashCombiner &Combine(const std::vector<Value> &vector) {
+        return Combine(vector.cbegin(), vector.cend());
+    }
+
+    template <typename Value>
+    HashCombiner &operator<<(const Value &value) {
+        return Combine(value);
+    }
+
+    Key Value() const { return combined_; }
+    void Reset(Key combined = 0) { combined_ = combined; }
+
+   private:
+    Key combined_;
+};
+
+// A template to inherit std::hash overloads from when T::hash() is defined
+template <typename T>
+struct HasHashMember {
+    size_t operator()(const T &value) const { return value.hash(); }
+};
+
+// A template to inherit std::hash overloads from when is an *ordered* constainer
+template <typename T>
+struct IsOrderedContainer {
+    size_t operator()(const T &value) const { return HashCombiner().Combine(value.cbegin(), value.cend()).Value(); }
+};
+
+}  // namespace hash_util
+
+#endif  // HASH_UTILS_H_
diff --git a/layers/hash_vk_types.h b/layers/hash_vk_types.h
new file mode 100644
index 00000000..871396e8
--- /dev/null
+++ b/layers/hash_vk_types.h
@@ -0,0 +1,63 @@
+/* Copyright (c) 2018 The Khronos Group Inc.
+ * Copyright (c) 2018 Valve Corporation
+ * Copyright (c) 2018 LunarG, Inc.
+ *
+ * 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.
+ *
+ * Author: John Zulauf <jzulauf@lunarg.com>
+ */
+#ifndef HASH_VK_TYPES_H_
+#define HASH_VK_TYPES_H_
+
+// Includes everything needed for overloading std::hash
+#include "hash_util.h"
+
+#include <vulkan/vulkan.h>
+#include "vk_safe_struct.h"
+
+// Hash and equality and/or compare functions for selected Vk types (and useful collections thereof)
+
+// VkDescriptorSetLayoutBinding
+static bool operator==(const safe_VkDescriptorSetLayoutBinding &lhs, const safe_VkDescriptorSetLayoutBinding &rhs) {
+    if ((lhs.binding != rhs.binding) || (lhs.descriptorType != rhs.descriptorType) ||
+        (lhs.descriptorCount != rhs.descriptorCount) || (lhs.stageFlags != rhs.stageFlags) ||
+        !hash_util::similar_for_nullity(lhs.pImmutableSamplers, rhs.pImmutableSamplers)) {
+        return false;
+    }
+    if (lhs.pImmutableSamplers) {  // either one will do as they *are* similar for nullity (i.e. either both null or both non-null)
+        for (uint32_t samp = 0; samp < lhs.descriptorCount; samp++) {
+            if (lhs.pImmutableSamplers[samp] != rhs.pImmutableSamplers[samp]) {
+                return false;
+            }
+        }
+    }
+    return true;
+}
+
+namespace std {
+template <>
+struct hash<safe_VkDescriptorSetLayoutBinding> {
+    size_t operator()(const safe_VkDescriptorSetLayoutBinding &value) const {
+        hash_util::HashCombiner hc;
+        hc << value.binding << value.descriptorType << value.descriptorCount << value.stageFlags;
+        if (value.pImmutableSamplers) {
+            for (uint32_t samp = 0; samp < value.descriptorCount; samp++) {
+                hc << value.pImmutableSamplers[samp];
+            }
+        }
+        return hc.Value();
+    }
+};
+}  // namespace std
+
+#endif  // HASH_VK_TYPES_H_