Adding validation code for OpTypeStruct.

According to the Data Rules section of 2.16.1. Universal Validation
Rules of the SPIR-V Spec:

Forward reference operands in an OpTypeStruct
* must be later declared with OpTypePointer
* the type pointed to must be an OpTypeStruct
* had an earlier OpTypeForwardPointer forward reference to the same <id>

6 files changed, 153 insertions, 5 deletions

diff --git a/source/val/validation_state.cpp b/source/val/validation_state.cpp
index 11096bc3..05720e1a 100644
--- a/source/val/validation_state.cpp
+++ b/source/val/validation_state.cpp
@@ -207,6 +207,15 @@ spv_result_t ValidationState_t::RemoveIfForwardDeclared(uint32_t id) {
   return SPV_SUCCESS;
 }
 
+spv_result_t ValidationState_t::RegisterForwardPointer(uint32_t id) {
+  forward_pointer_ids_.insert(id);
+  return SPV_SUCCESS;
+}
+
+bool ValidationState_t::IsForwardPointer(uint32_t id) const {
+  return (forward_pointer_ids_.find(id) != forward_pointer_ids_.end());
+}
+
 void ValidationState_t::AssignNameToId(uint32_t id, string name) {
   operand_names_[id] = name;
 }
diff --git a/source/val/validation_state.h b/source/val/validation_state.h
index 006f0556..cc00b84f 100644
--- a/source/val/validation_state.h
+++ b/source/val/validation_state.h
@@ -64,6 +64,12 @@ class ValidationState_t {
   /// Removes a forward declared ID if it has been defined
   spv_result_t RemoveIfForwardDeclared(uint32_t id);
 
+  /// Registers an ID as a forward pointer
+  spv_result_t RegisterForwardPointer(uint32_t id);
+
+  /// Returns whether or not an ID is a forward pointer
+  bool IsForwardPointer(uint32_t id) const;
+
   /// Assigns a name to an ID
   void AssignNameToId(uint32_t id, std::string name);
 
@@ -184,6 +190,9 @@ class ValidationState_t {
   /// IDs which have been forward declared but have not been defined
   std::unordered_set<uint32_t> unresolved_forward_ids_;
 
+  /// IDs that have been declared as forward pointers.
+  std::unordered_set<uint32_t> forward_pointer_ids_;
+
   /// A map of operand IDs and their names defined by the OpName instruction
   std::unordered_map<uint32_t, std::string> operand_names_;
 
diff --git a/source/validate.cpp b/source/validate.cpp
index 28984971..402bb109 100644
--- a/source/validate.cpp
+++ b/source/validate.cpp
@@ -230,7 +230,7 @@ spv_result_t spvValidateBinary(const spv_const_context context,
 
     auto id_str = ss.str();
     return vstate.diag(SPV_ERROR_INVALID_ID)
-           << "The following forward referenced IDs have not be defined:\n"
+           << "The following forward referenced IDs have not been defined:\n"
            << id_str.substr(0, id_str.size() - 1);
   }
 
diff --git a/source/validate_datarules.cpp b/source/validate_datarules.cpp
index d1062378..3d50328c 100644
--- a/source/validate_datarules.cpp
+++ b/source/validate_datarules.cpp
@@ -190,6 +190,33 @@ spv_result_t ValidateSpecConstBoolean(ValidationState_t& _,
   return SPV_SUCCESS;
 }
 
+// Records the <id> of the forward pointer to be used for validation.
+spv_result_t ValidateForwardPointer(ValidationState_t& _,
+                                    const spv_parsed_instruction_t* inst) {
+  // Record the <id> (which is operand 0) to ensure it's used properly.
+  // OpTypeStruct can only include undefined pointers that are
+  // previously declared as a ForwardPointer
+  return (_.RegisterForwardPointer(inst->words[inst->operands[0].offset]));
+}
+
+// Validates that any undefined component of the struct is a forward pointer.
+// It is valid to declare a forward pointer, and use its <id> as one of the
+// components of a struct.
+spv_result_t ValidateStruct(ValidationState_t& _,
+                            const spv_parsed_instruction_t* inst) {
+  // Struct components are operands 1, 2, etc.
+  for (unsigned i = 1; i < inst->num_operands; i++) {
+    auto type_id = inst->words[inst->operands[i].offset];
+    auto type_instruction = _.FindDef(type_id);
+    if (type_instruction == nullptr && !_.IsForwardPointer(type_id)) {
+      return _.diag(SPV_ERROR_INVALID_ID)
+             << "Forward reference operands in an OpTypeStruct must first be "
+                "declared using OpTypeForwardPointer.";
+    }
+  }
+  return SPV_SUCCESS;
+}
+
 }  // anonymous namespace
 
 namespace libspirv {
@@ -227,6 +254,14 @@ spv_result_t DataRulesPass(ValidationState_t& _,
       if (auto error = ValidateSpecConstBoolean(_, inst)) return error;
       break;
     }
+    case SpvOpTypeForwardPointer: {
+      if (auto error = ValidateForwardPointer(_, inst)) return error;
+      break;
+    }
+    case SpvOpTypeStruct: {
+      if (auto error = ValidateStruct(_, inst)) return error;
+      break;
+    }
     // TODO(ehsan): add more data rules validation here.
     default: { break; }
   }
diff --git a/source/validate_id.cpp b/source/validate_id.cpp
index f603a065..ae4b793f 100644
--- a/source/validate_id.cpp
+++ b/source/validate_id.cpp
@@ -355,13 +355,35 @@ bool idUsage::isValid<SpvOpTypeStruct>(const spv_instruction_t* inst,
                                        const spv_opcode_desc) {
   for (size_t memberTypeIndex = 2; memberTypeIndex < inst->words.size();
        ++memberTypeIndex) {
-    auto memberType = module_.FindDef(inst->words[memberTypeIndex]);
+    auto memberTypeId = inst->words[memberTypeIndex];
+    auto memberType = module_.FindDef(memberTypeId);
     if (!memberType || !spvOpcodeGeneratesType(memberType->opcode())) {
       DIAG(memberTypeIndex) << "OpTypeStruct Member Type <id> '"
                             << inst->words[memberTypeIndex]
                             << "' is not a type.";
       return false;
     }
+    if (memberType && module_.IsForwardPointer(memberTypeId)) {
+      if (memberType->opcode() != SpvOpTypePointer) {
+        DIAG(memberTypeIndex) << "Found a forward reference to a non-pointer "
+                                 "type in OpTypeStruct instruction.";
+        return false;
+      }
+      // If we're dealing with a forward pointer:
+      // Find out the type that the pointer is pointing to (must be struct)
+      // word 3 is the <id> of the type being pointed to.
+      auto typePointingTo = module_.FindDef(memberType->words()[3]);
+      if (typePointingTo && typePointingTo->opcode() != SpvOpTypeStruct) {
+        // Forward declared operands of a struct may only point to a struct.
+        DIAG(memberTypeIndex)
+            << "A forward reference operand in an OpTypeStruct must be an "
+               "OpTypePointer that points to an OpTypeStruct. "
+               "Found OpTypePointer that points to Op"
+            << spvOpcodeString(static_cast<SpvOp>(typePointingTo->opcode()))
+            << ".";
+        return false;
+      }
+    }
   }
   return true;
 }
@@ -591,7 +613,8 @@ bool idUsage::isValid<SpvOpConstantComposite>(const spv_instruction_t* inst,
            constituentIndex < inst->words.size();
            constituentIndex++, memberIndex++) {
         auto constituent = module_.FindDef(inst->words[constituentIndex]);
-        if (!constituent || !spvOpcodeIsConstantOrUndef(constituent->opcode())) {
+        if (!constituent ||
+            !spvOpcodeIsConstantOrUndef(constituent->opcode())) {
           DIAG(constituentIndex) << "OpConstantComposite Constituent <id> '"
                                  << inst->words[constituentIndex]
                                  << "' is not a constant or undef.";
@@ -2384,8 +2407,8 @@ function<bool(unsigned)> getCanBeForwardDeclaredFunction(SpvOp opcode) {
       // The Invoke parameter.
       out = [](unsigned index) { return index == 2; };
       break;
-      case SpvOpTypeForwardPointer:
-        out = [](unsigned index) { return index == 0; };
+    case SpvOpTypeForwardPointer:
+      out = [](unsigned index) { return index == 0; };
       break;
     default:
       out = [](unsigned) { return false; };
diff --git a/test/val/val_data_test.cpp b/test/val/val_data_test.cpp
index 1eafe6cc..656abce9 100644
--- a/test/val/val_data_test.cpp
+++ b/test/val/val_data_test.cpp
@@ -36,6 +36,12 @@ string header = R"(
      OpMemoryModel Logical GLSL450
 %1 = OpTypeFloat 32
 )";
+string header_with_addresses = R"(
+     OpCapability Addresses
+     OpCapability Kernel
+     OpCapability GenericPointer
+     OpMemoryModel Physical32 OpenCL
+)";
 string header_with_vec16_cap = R"(
      OpCapability Shader
      OpCapability Vector16
@@ -390,3 +396,69 @@ TEST_F(ValidateData, specialize_boolean_to_int) {
   EXPECT_THAT(getDiagnosticString(),
               HasSubstr("Specialization constant must be a boolean"));
 }
+
+TEST_F(ValidateData, missing_forward_pointer_decl) {
+  string str = header_with_addresses + R"(
+%uintt = OpTypeInt 32 0
+%3 = OpTypeStruct %fwd_ptrt %uintt
+)";
+  CompileSuccessfully(str.c_str());
+  ASSERT_EQ(SPV_ERROR_INVALID_ID, ValidateInstructions());
+  EXPECT_THAT(getDiagnosticString(),
+              HasSubstr("must first be declared using OpTypeForwardPointer"));
+}
+
+TEST_F(ValidateData, forward_pointer_missing_definition) {
+  string str = header_with_addresses + R"(
+OpTypeForwardPointer %_ptr_Generic_struct_A Generic
+%uintt = OpTypeInt 32 0
+%struct_B = OpTypeStruct %uintt %_ptr_Generic_struct_A
+)";
+  CompileSuccessfully(str.c_str());
+  ASSERT_EQ(SPV_ERROR_INVALID_ID, ValidateInstructions());
+  EXPECT_THAT(getDiagnosticString(),
+              HasSubstr("forward referenced IDs have not been defined"));
+}
+
+TEST_F(ValidateData, forward_ref_bad_type) {
+  string str = header_with_addresses + R"(
+OpTypeForwardPointer %_ptr_Generic_struct_A Generic
+%uintt = OpTypeInt 32 0
+%struct_B = OpTypeStruct %uintt %_ptr_Generic_struct_A
+%_ptr_Generic_struct_A = OpTypeFloat 32
+)";
+  CompileSuccessfully(str.c_str());
+  ASSERT_EQ(SPV_ERROR_INVALID_ID, ValidateInstructions());
+  EXPECT_THAT(getDiagnosticString(),
+              HasSubstr("Found a forward reference to a non-pointer type in "
+                        "OpTypeStruct instruction."));
+}
+
+TEST_F(ValidateData, forward_ref_points_to_non_struct) {
+  string str = header_with_addresses + R"(
+OpTypeForwardPointer %_ptr_Generic_struct_A Generic
+%uintt = OpTypeInt 32 0
+%struct_B = OpTypeStruct %uintt %_ptr_Generic_struct_A
+%_ptr_Generic_struct_A = OpTypePointer Generic %uintt
+)";
+  CompileSuccessfully(str.c_str());
+  ASSERT_EQ(SPV_ERROR_INVALID_ID, ValidateInstructions());
+  EXPECT_THAT(getDiagnosticString(),
+              HasSubstr("A forward reference operand in an OpTypeStruct must "
+                        "be an OpTypePointer that points to an OpTypeStruct. "
+                        "Found OpTypePointer that points to OpTypeInt."));
+}
+
+TEST_F(ValidateData, struct_forward_pointer_good) {
+  string str = header_with_addresses + R"(
+OpTypeForwardPointer %_ptr_Generic_struct_A Generic
+%uintt = OpTypeInt 32 0
+%struct_B = OpTypeStruct %uintt %_ptr_Generic_struct_A
+%struct_C = OpTypeStruct %uintt %struct_B
+%struct_A = OpTypeStruct %uintt %struct_C
+%_ptr_Generic_struct_A = OpTypePointer Generic %struct_C
+)";
+  CompileSuccessfully(str.c_str());
+  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
+}
+