Vulkan permits non-monotonic offsets for block members

Other environments do not.
Add tests for OpenGL 4.5 and SPIR-V universal 1.0 to ensure
they still check monotonic layout.

For universal 1.0, we're assuming it otherwise follows Vulkan
rules for block layout.

Fixes #1685

4 files changed, 117 insertions, 12 deletions

diff --git a/source/val/validation_state.cpp b/source/val/validation_state.cpp
index 6907e599..ae9ea99e 100644
--- a/source/val/validation_state.cpp
+++ b/source/val/validation_state.cpp
@@ -18,6 +18,7 @@
 #include <stack>
 
 #include "opcode.h"
+#include "spirv_target_env.h"
 #include "val/basic_block.h"
 #include "val/construct.h"
 #include "val/function.h"
@@ -168,6 +169,8 @@ ValidationState_t::ValidationState_t(const spv_const_context ctx,
       in_function_(false) {
   assert(opt && "Validator options may not be Null.");
 
+  features_.non_monotonic_struct_member_offsets =
+      spvIsVulkanEnv(context_->target_env);
   switch (context_->target_env) {
     case SPV_ENV_WEBGPU_0:
       features_.bans_op_undef = true;
diff --git a/source/val/validation_state.h b/source/val/validation_state.h
index d1b52815..61c2f675 100644
--- a/source/val/validation_state.h
+++ b/source/val/validation_state.h
@@ -81,6 +81,10 @@ class ValidationState_t {
 
     // Allow OpTypeInt with 8 bit width?
     bool declare_int8_type = false;
+
+    // Allow non-monotonic offsets for struct members?
+    // Vulkan permits this.
+    bool non_monotonic_struct_member_offsets = false;
   };
 
   ValidationState_t(const spv_const_context context,
diff --git a/source/validate_decorations.cpp b/source/validate_decorations.cpp
index 28a68659..132b5507 100644
--- a/source/validate_decorations.cpp
+++ b/source/validate_decorations.cpp
@@ -344,11 +344,19 @@ spv_result_t checkLayout(uint32_t struct_id, const char* storage_class_str,
   };
   if (vstate.options()->relax_block_layout) return SPV_SUCCESS;
   const auto& members = getStructMembers(struct_id, vstate);
-  uint32_t prevOffset = 0;
-  uint32_t nextValidOffset = 0;
+
+  // To check for member overlaps, we want to traverse the members in
+  // offset order.
+  const bool permit_non_monotonic_member_offsets =
+      vstate.features().non_monotonic_struct_member_offsets;
+  struct MemberOffsetPair {
+    uint32_t member;
+    uint32_t offset;
+  };
+  std::vector<MemberOffsetPair> member_offsets;
+  member_offsets.reserve(members.size());
   for (uint32_t memberIdx = 0, numMembers = uint32_t(members.size());
        memberIdx < numMembers; memberIdx++) {
-    auto id = members[memberIdx];
     uint32_t offset = 0xffffffff;
     for (auto& decoration : vstate.id_decorations(struct_id)) {
       if (decoration.struct_member_index() == (int)memberIdx) {
@@ -361,6 +369,23 @@ spv_result_t checkLayout(uint32_t struct_id, const char* storage_class_str,
         }
       }
     }
+    member_offsets.push_back(MemberOffsetPair{memberIdx, offset});
+  }
+  std::stable_sort(
+      member_offsets.begin(), member_offsets.end(),
+      [](const MemberOffsetPair& lhs, const MemberOffsetPair& rhs) {
+        return lhs.offset < rhs.offset;
+      });
+
+  // Now scan from lowest offest to highest offset.
+  uint32_t prevOffset = 0;
+  uint32_t nextValidOffset = 0;
+  for (size_t ordered_member_idx = 0;
+       ordered_member_idx < member_offsets.size(); ordered_member_idx++) {
+    const auto& member_offset = member_offsets[ordered_member_idx];
+    const auto memberIdx = member_offset.member;
+    const auto offset = member_offset.offset;
+    auto id = members[member_offset.member];
     const LayoutConstraints& constraint =
         constraints[make_pair(struct_id, uint32_t(memberIdx))];
     const auto alignment =
@@ -375,11 +400,18 @@ spv_result_t checkLayout(uint32_t struct_id, const char* storage_class_str,
       return fail(memberIdx)
              << "at offset " << offset << " is not aligned to " << alignment;
     // SPIR-V requires struct members to be specified in memory address order,
-    // and they should not overlap.
-    if (size > 0 && (offset + size <= prevOffset))
-      return fail(memberIdx)
-             << "at offset " << offset << " has a lower offset than member "
-             << memberIdx - 1;
+    // and they should not overlap.  Vulkan relaxes that rule.
+    if (!permit_non_monotonic_member_offsets) {
+      const auto out_of_order =
+          ordered_member_idx > 0 &&
+          (memberIdx < member_offsets[ordered_member_idx - 1].member);
+      if (out_of_order) {
+        return fail(memberIdx)
+               << "at offset " << offset << " has a higher offset than member "
+               << member_offsets[ordered_member_idx - 1].member << " at offset "
+               << prevOffset;
+      }
+    }
     if (offset < nextValidOffset)
       return fail(memberIdx) << "at offset " << offset
                              << " overlaps previous member ending at offset "
diff --git a/test/val/val_decoration_test.cpp b/test/val/val_decoration_test.cpp
index 0c591aa1..7574173a 100644
--- a/test/val/val_decoration_test.cpp
+++ b/test/val/val_decoration_test.cpp
@@ -2264,7 +2264,7 @@ TEST_F(ValidateDecorations,
           "offset 4 overlaps previous member ending at offset 15"));
 }
 
-TEST_F(ValidateDecorations, BlockLayoutOffsetOutOfOrderBad) {
+TEST_F(ValidateDecorations, BlockLayoutOffsetOutOfOrderBadUniversal1_0) {
   string spirv = R"(
                OpCapability Shader
           %1 = OpExtInstImport "GLSL.std.450"
@@ -2289,13 +2289,79 @@ TEST_F(ValidateDecorations, BlockLayoutOffsetOutOfOrderBad) {
   )";
 
   CompileSuccessfully(spirv);
-  EXPECT_EQ(SPV_ERROR_INVALID_ID, ValidateAndRetrieveValidationState());
+  EXPECT_EQ(SPV_ERROR_INVALID_ID,
+            ValidateAndRetrieveValidationState(SPV_ENV_UNIVERSAL_1_0));
   EXPECT_THAT(
       getDiagnosticString(),
       HasSubstr(
           "Structure id 3 decorated as Block for variable in Uniform storage "
-          "class must follow standard uniform buffer layout rules: member 1 at "
-          "offset 0 has a lower offset than member 0"));
+          "class must follow standard uniform buffer layout rules: member 0 at "
+          "offset 4 has a higher offset than member 1 at offset 0"));
+}
+
+TEST_F(ValidateDecorations, BlockLayoutOffsetOutOfOrderBadOpenGL4_5) {
+  string spirv = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint GLCompute %main "main"
+               OpExecutionMode %main LocalSize 1 1 1
+               OpMemberDecorate %Outer 0 Offset 4
+               OpMemberDecorate %Outer 1 Offset 0
+               OpDecorate %Outer Block
+               OpDecorate %O DescriptorSet 0
+               OpDecorate %O Binding 0
+       %void = OpTypeVoid
+          %3 = OpTypeFunction %void
+       %uint = OpTypeInt 32 0
+      %Outer = OpTypeStruct %uint %uint
+%_ptr_Uniform_Outer = OpTypePointer Uniform %Outer
+          %O = OpVariable %_ptr_Uniform_Outer Uniform
+       %main = OpFunction %void None %3
+          %5 = OpLabel
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  CompileSuccessfully(spirv);
+  EXPECT_EQ(SPV_ERROR_INVALID_ID,
+            ValidateAndRetrieveValidationState(SPV_ENV_OPENGL_4_5));
+  EXPECT_THAT(
+      getDiagnosticString(),
+      HasSubstr(
+          "Structure id 3 decorated as Block for variable in Uniform storage "
+          "class must follow standard uniform buffer layout rules: member 0 at "
+          "offset 4 has a higher offset than member 1 at offset 0"));
+}
+
+TEST_F(ValidateDecorations, BlockLayoutOffsetOutOfOrderGoodVulkan1_1) {
+  string spirv = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint GLCompute %main "main"
+               OpExecutionMode %main LocalSize 1 1 1
+               OpMemberDecorate %Outer 0 Offset 4
+               OpMemberDecorate %Outer 1 Offset 0
+               OpDecorate %Outer Block
+               OpDecorate %O DescriptorSet 0
+               OpDecorate %O Binding 0
+       %void = OpTypeVoid
+          %3 = OpTypeFunction %void
+       %uint = OpTypeInt 32 0
+      %Outer = OpTypeStruct %uint %uint
+%_ptr_Uniform_Outer = OpTypePointer Uniform %Outer
+          %O = OpVariable %_ptr_Uniform_Outer Uniform
+       %main = OpFunction %void None %3
+          %5 = OpLabel
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  CompileSuccessfully(spirv);
+  EXPECT_EQ(SPV_SUCCESS, ValidateAndRetrieveValidationState(SPV_ENV_VULKAN_1_1))
+      << getDiagnosticString();
+  EXPECT_THAT(getDiagnosticString(), Eq(""));
 }
 
 TEST_F(ValidateDecorations, BlockLayoutOffsetOverlapBad) {