// Copyright (c) 2018 Google LLC.

// Modifications Copyright (C) 2020 Advanced Micro Devices, Inc. All rights

// reserved.

// Copyright (C) 2026 Qualcomm Technologies, 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.

// Validates correctness of built-in variables.

#include <array>

#include <cstdint>

#include <functional>

#include <list>

#include <map>

#include <set>

#include <sstream>

#include <string>

#include <unordered_map>

#include <vector>

#include "source/opcode.h"

#include "source/spirv_target_env.h"

#include "source/val/instruction.h"

#include "source/val/validate.h"

#include "source/val/validation_state.h"

#include "spirv/unified1/spirv.hpp11"

namespace spvtools {

namespace val {

namespace {

// Returns a short textual description of the id defined by the given

// instruction.

std::string GetIdDesc(const Instruction& inst) {

  std::ostringstream ss;

  ss << "ID <" << inst.id() << "> (Op" << spvOpcodeString(inst.opcode()) << ")";

  return ss.str();

}

// Gets underlying data type which is

// - member type if instruction is OpTypeStruct

//   (member index is taken from decoration).

// - data type if id creates a pointer.

// - type of the constant if instruction is OpConst or OpSpecConst.

//

// Fails in any other case. The function is based on built-ins allowed by

// the Vulkan spec.

// TODO: If non-Vulkan validation rules are added then it might need

// to be refactored.

spv_result_t GetUnderlyingType(ValidationState_t& _,

                               const Decoration& decoration,

                               const Instruction& inst,

                               uint32_t* underlying_type) {

  if (decoration.struct_member_index() != Decoration::kInvalidMember) {

    if (inst.opcode() != spv::Op::OpTypeStruct) {

      return _.diag(SPV_ERROR_INVALID_DATA, &inst)

             << GetIdDesc(inst)

             << "Attempted to get underlying data type via member index for "

                "non-struct type.";

    }

    *underlying_type = inst.word(decoration.struct_member_index() + 2);

    return SPV_SUCCESS;

  }

  if (inst.opcode() == spv::Op::OpTypeStruct) {

    return _.diag(SPV_ERROR_INVALID_DATA, &inst)

           << GetIdDesc(inst)

           << " did not find an member index to get underlying data type for "

              "struct type.";

  }

  if (spvOpcodeIsConstant(inst.opcode())) {

    *underlying_type = inst.type_id();

    return SPV_SUCCESS;

  }

  spv::StorageClass storage_class;

  if (!_.GetPointerTypeInfo(inst.type_id(), underlying_type, &storage_class)) {

    return _.diag(SPV_ERROR_INVALID_DATA, &inst)

           << GetIdDesc(inst)

           << " is decorated with BuiltIn. BuiltIn decoration should only be "

              "applied to struct types, variables and constants.";

  }

  return SPV_SUCCESS;

}

// Returns Storage Class used by the instruction if applicable.

// Returns spv::StorageClass::Max if not.

spv::StorageClass GetStorageClass(const Instruction& inst) {

  switch (inst.opcode()) {

    case spv::Op::OpTypePointer:

    case spv::Op::OpTypeUntypedPointerKHR:

    case spv::Op::OpTypeForwardPointer: {

      return spv::StorageClass(inst.word(2));

    }

    case spv::Op::OpVariable: {

      return spv::StorageClass(inst.word(3));

    }

    case spv::Op::OpUntypedVariableKHR: {

      return spv::StorageClass(inst.word(4));

    }

    case spv::Op::OpGenericCastToPtrExplicit: {

      return spv::StorageClass(inst.word(4));

    }

    default: { break; }

  }

  return spv::StorageClass::Max;

}

typedef enum VUIDError_ {

  VUIDErrorExecutionModel = 0,

  VUIDErrorStorageClass = 1,

  VUIDErrorType = 2,

  VUIDErrorMax,

} VUIDError;

const static uint32_t NumVUIDBuiltins = 45;

typedef struct {

  spv::BuiltIn builtIn;

  uint32_t vuid[VUIDErrorMax];  // execution mode, storage class, type VUIDs

} BuiltinVUIDMapping;

// Many built-ins have the same checks (Storage Class, Type, etc)

// This table provides a nice LUT for the VUIDs

std::array<BuiltinVUIDMapping, NumVUIDBuiltins> builtinVUIDInfo = {{

    // clang-format off

    {spv::BuiltIn::SubgroupEqMask,            {0,    4370, 4371}},

    {spv::BuiltIn::SubgroupGeMask,            {0,    4372, 4373}},

    {spv::BuiltIn::SubgroupGtMask,            {0,    4374, 4375}},

    {spv::BuiltIn::SubgroupLeMask,            {0,    4376, 4377}},

    {spv::BuiltIn::SubgroupLtMask,            {0,    4378, 4379}},

    {spv::BuiltIn::SubgroupLocalInvocationId, {0,    4380, 4381}},

    {spv::BuiltIn::SubgroupSize,              {0,    4382, 4383}},

    {spv::BuiltIn::GlobalInvocationId,        {4236, 4237, 4238}},

    {spv::BuiltIn::LocalInvocationId,         {4281, 4282, 4283}},

    {spv::BuiltIn::NumWorkgroups,             {4296, 4297, 4298}},

    {spv::BuiltIn::NumSubgroups,              {4293, 4294, 4295}},

    {spv::BuiltIn::SubgroupId,                {4367, 4368, 4369}},

    {spv::BuiltIn::WorkgroupId,               {4422, 4423, 4424}},

    {spv::BuiltIn::HitKindKHR,                {4242, 4243, 4244}},

    {spv::BuiltIn::HitTNV,                    {4245, 4246, 4247}},

    {spv::BuiltIn::InstanceCustomIndexKHR,    {4251, 4252, 4253}},

    {spv::BuiltIn::InstanceId,                {4254, 4255, 4256}},

    {spv::BuiltIn::RayGeometryIndexKHR,       {4345, 4346, 4347}},

    {spv::BuiltIn::ObjectRayDirectionKHR,     {4299, 4300, 4301}},

    {spv::BuiltIn::ObjectRayOriginKHR,        {4302, 4303, 4304}},

    {spv::BuiltIn::ObjectToWorldKHR,          {4305, 4306, 4307}},

    {spv::BuiltIn::WorldToObjectKHR,          {4434, 4435, 4436}},

    {spv::BuiltIn::IncomingRayFlagsKHR,       {4248, 4249, 4250}},

    {spv::BuiltIn::RayTminKHR,                {4351, 4352, 4353}},

    {spv::BuiltIn::RayTmaxKHR,                {4348, 4349, 4350}},

    {spv::BuiltIn::WorldRayDirectionKHR,      {4428, 4429, 4430}},

    {spv::BuiltIn::WorldRayOriginKHR,         {4431, 4432, 4433}},

    {spv::BuiltIn::LaunchIdKHR,               {4266, 4267, 4268}},

    {spv::BuiltIn::LaunchSizeKHR,             {4269, 4270, 4271}},

    {spv::BuiltIn::FragInvocationCountEXT,    {4217, 4218, 4219}},

    {spv::BuiltIn::FragSizeEXT,               {4220, 4221, 4222}},

    {spv::BuiltIn::FragStencilRefEXT,         {4223, 4224, 4225}},

    {spv::BuiltIn::FullyCoveredEXT,           {4232, 4233, 4234}},

    {spv::BuiltIn::CullMaskKHR,               {6735, 6736, 6737}},

    {spv::BuiltIn::BaryCoordKHR,              {4154, 4155, 4156}},

    {spv::BuiltIn::BaryCoordNoPerspKHR,       {4160, 4161, 4162}},

    {spv::BuiltIn::LocalInvocationIndex,      {4284, 4285, 4286}},

    {spv::BuiltIn::PrimitivePointIndicesEXT,  {7041, 7043, 7044}},

    {spv::BuiltIn::PrimitiveLineIndicesEXT,   {7047, 7049, 7050}},

    {spv::BuiltIn::PrimitiveTriangleIndicesEXT, {7053, 7055, 7056}},

    {spv::BuiltIn::CullPrimitiveEXT,          {7034, 7035, 7036}},

    {spv::BuiltIn::HitTriangleVertexPositionsKHR, {8747, 8748, 8749}},

    {spv::BuiltIn::TileOffsetQCOM,    {10626, 10627, 10628}},

    {spv::BuiltIn::TileDimensionQCOM, {10629, 10630, 10631}},

    {spv::BuiltIn::TileApronSizeQCOM, {10632, 10633, 10634}},

    // clang-format on

}};

uint32_t GetVUIDForBuiltin(spv::BuiltIn builtIn, VUIDError type) {

  uint32_t vuid = 0;

  for (const auto& iter: builtinVUIDInfo) {

    if (iter.builtIn == builtIn) {

      assert(type < VUIDErrorMax);

      vuid = iter.vuid[type];

      break;

    }

  }

  return vuid;

}

bool IsExecutionModelValidForRtBuiltIn(spv::BuiltIn builtin,

                                       spv::ExecutionModel stage) {

  switch (builtin) {

    case spv::BuiltIn::HitKindKHR:

    case spv::BuiltIn::HitTNV:

    case spv::BuiltIn::HitTriangleVertexPositionsKHR:

      if (stage == spv::ExecutionModel::AnyHitKHR ||

          stage == spv::ExecutionModel::ClosestHitKHR) {

        return true;

      }

      break;

    case spv::BuiltIn::InstanceCustomIndexKHR:

    case spv::BuiltIn::InstanceId:

    case spv::BuiltIn::RayGeometryIndexKHR:

    case spv::BuiltIn::ObjectRayDirectionKHR:

    case spv::BuiltIn::ObjectRayOriginKHR:

    case spv::BuiltIn::ObjectToWorldKHR:

    case spv::BuiltIn::WorldToObjectKHR:

      switch (stage) {

        case spv::ExecutionModel::IntersectionKHR:

        case spv::ExecutionModel::AnyHitKHR:

        case spv::ExecutionModel::ClosestHitKHR:

          return true;

        default:

          return false;

      }

      break;

    case spv::BuiltIn::IncomingRayFlagsKHR:

    case spv::BuiltIn::RayTminKHR:

    case spv::BuiltIn::RayTmaxKHR:

    case spv::BuiltIn::WorldRayDirectionKHR:

    case spv::BuiltIn::WorldRayOriginKHR:

    case spv::BuiltIn::CullMaskKHR:

      switch (stage) {

        case spv::ExecutionModel::IntersectionKHR:

        case spv::ExecutionModel::AnyHitKHR:

        case spv::ExecutionModel::ClosestHitKHR:

        case spv::ExecutionModel::MissKHR:

          return true;

        default:

          return false;

      }

      break;

    case spv::BuiltIn::LaunchIdKHR:

    case spv::BuiltIn::LaunchSizeKHR:

      switch (stage) {

        case spv::ExecutionModel::RayGenerationKHR:

        case spv::ExecutionModel::IntersectionKHR:

        case spv::ExecutionModel::AnyHitKHR:

        case spv::ExecutionModel::ClosestHitKHR:

        case spv::ExecutionModel::MissKHR:

        case spv::ExecutionModel::CallableKHR:

          return true;

        default:

          return false;

      }

      break;

    default:

      break;

  }

  return false;

}

bool IsVolatileSemanticsBuiltIn(spv::BuiltIn builtin) {

  switch (builtin) {

    case spv::BuiltIn::SMIDNV:

    case spv::BuiltIn::WarpIDNV:

    case spv::BuiltIn::SubgroupSize:

    case spv::BuiltIn::SubgroupLocalInvocationId:

    case spv::BuiltIn::SubgroupEqMask:

    case spv::BuiltIn::SubgroupGeMask:

    case spv::BuiltIn::SubgroupGtMask:

    case spv::BuiltIn::SubgroupLeMask:

    case spv::BuiltIn::SubgroupLtMask:

    case spv::BuiltIn::RayTmaxKHR:

      return true;

    default:

      return false;

  }

}

// Some background: certain ray tracing inputs can change when you

// execute a "repack" instruction or cast a dependent ray or whatever.

// SPIR-V needs to have them marked as volatile so each load would actually

// load rather than use a stale cached value

//

// These stages/builtin are listed in the Vulkan Spec and found in VU

// 04678/04679

bool NeedsVolatileSemantics(spv::BuiltIn builtin, spv::ExecutionModel stage) {

  if (builtin == spv::BuiltIn::RayTmaxKHR) {

    return stage == spv::ExecutionModel::IntersectionKHR;

  }

  if (!IsVolatileSemanticsBuiltIn(builtin)) return false;

  switch (stage) {

    case spv::ExecutionModel::RayGenerationKHR:

    case spv::ExecutionModel::ClosestHitKHR:

    case spv::ExecutionModel::MissKHR:

    case spv::ExecutionModel::IntersectionKHR:

    case spv::ExecutionModel::CallableKHR:

      return true;

    default:

      return false;

  }

}

// Helper class managing validation of built-ins.

// TODO: Generic functionality of this class can be moved into

// ValidationState_t to be made available to other users.

class BuiltInsValidator {

 public:

  BuiltInsValidator(ValidationState_t& vstate) : _(vstate) {}

  // Run validation.

  spv_result_t Run();

 private:

  // Goes through all decorations in the module, if decoration is BuiltIn

  // calls ValidateSingleBuiltInAtDefinition().

  spv_result_t ValidateBuiltInsAtDefinition();

  // Validates the instruction defining an id with built-in decoration.

  // Can be called multiple times for the same id, if multiple built-ins are

  // specified. Seeds id_to_at_reference_checks_ with decorated ids if needed.

  spv_result_t ValidateSingleBuiltInAtDefinition(const Decoration& decoration,

                                                 const Instruction& inst);

  spv_result_t ValidateSingleBuiltInAtDefinitionVulkan(

      const Decoration& decoration, const Instruction& inst,

      const spv::BuiltIn label);

  // The following section contains functions which are called when id defined

  // by |inst| is decorated with BuiltIn |decoration|.

  // Most functions are specific to a single built-in and have naming scheme:

  // ValidateXYZAtDefinition. Some functions are common to multiple kinds of

  // BuiltIn.

  spv_result_t ValidateClipOrCullDistanceAtDefinition(

      const Decoration& decoration, const Instruction& inst);

  spv_result_t ValidateFragCoordAtDefinition(const Decoration& decoration,

                                             const Instruction& inst);

  spv_result_t ValidateFragDepthAtDefinition(const Decoration& decoration,

                                             const Instruction& inst);

  spv_result_t ValidateFrontFacingAtDefinition(const Decoration& decoration,

                                               const Instruction& inst);

  spv_result_t ValidateHelperInvocationAtDefinition(

      const Decoration& decoration, const Instruction& inst);

  spv_result_t ValidateInvocationIdAtDefinition(const Decoration& decoration,

                                                const Instruction& inst);

  spv_result_t ValidateInstanceIndexAtDefinition(const Decoration& decoration,

                                                 const Instruction& inst);

  spv_result_t ValidateLayerOrViewportIndexAtDefinition(

      const Decoration& decoration, const Instruction& inst);

  spv_result_t ValidatePatchVerticesAtDefinition(const Decoration& decoration,

                                                 const Instruction& inst);

  spv_result_t ValidatePointCoordAtDefinition(const Decoration& decoration,

                                              const Instruction& inst);

  spv_result_t ValidatePointSizeAtDefinition(const Decoration& decoration,

                                             const Instruction& inst);

  spv_result_t ValidatePositionAtDefinition(const Decoration& decoration,

                                            const Instruction& inst);

  spv_result_t ValidatePrimitiveIdAtDefinition(const Decoration& decoration,

                                               const Instruction& inst);

  spv_result_t ValidateSampleIdAtDefinition(const Decoration& decoration,

                                            const Instruction& inst);

  spv_result_t ValidateSampleMaskAtDefinition(const Decoration& decoration,

                                              const Instruction& inst);

  spv_result_t ValidateSamplePositionAtDefinition(const Decoration& decoration,

                                                  const Instruction& inst);

  spv_result_t ValidateTessCoordAtDefinition(const Decoration& decoration,

                                             const Instruction& inst);

  spv_result_t ValidateTessLevelOuterAtDefinition(const Decoration& decoration,

                                                  const Instruction& inst);

  spv_result_t ValidateTessLevelInnerAtDefinition(const Decoration& decoration,

                                                  const Instruction& inst);

  spv_result_t ValidateVertexIndexAtDefinition(const Decoration& decoration,

                                               const Instruction& inst);

  spv_result_t ValidateVertexIdAtDefinition(const Decoration& decoration,

                                            const Instruction& inst);

  spv_result_t ValidateLocalInvocationIndexAtDefinition(

      const Decoration& decoration, const Instruction& inst);

  spv_result_t ValidateWorkgroupSizeAtDefinition(const Decoration& decoration,

                                                 const Instruction& inst);

  spv_result_t ValidateBaseInstanceOrVertexAtDefinition(

      const Decoration& decoration, const Instruction& inst);

  spv_result_t ValidateDrawIndexAtDefinition(const Decoration& decoration,

                                             const Instruction& inst);

  spv_result_t ValidateViewIndexAtDefinition(const Decoration& decoration,

                                             const Instruction& inst);

  spv_result_t ValidateDeviceIndexAtDefinition(const Decoration& decoration,

                                               const Instruction& inst);

  spv_result_t ValidateFragInvocationCountAtDefinition(const Decoration& decoration,

                                               const Instruction& inst);

  spv_result_t ValidateFragSizeAtDefinition(const Decoration& decoration,

                                               const Instruction& inst);

  spv_result_t ValidateFragStencilRefAtDefinition(const Decoration& decoration,

                                               const Instruction& inst);

  spv_result_t ValidateFullyCoveredAtDefinition(const Decoration& decoration,

                                               const Instruction& inst);

  // Used for GlobalInvocationId, LocalInvocationId, NumWorkgroups, WorkgroupId.

  spv_result_t ValidateComputeShaderI32Vec3InputAtDefinition(

      const Decoration& decoration, const Instruction& inst);

  spv_result_t ValidateNVSMOrARMCoreBuiltinsAtDefinition(const Decoration& decoration,

                                              const Instruction& inst);

  // Used for BaryCoord, BaryCoordNoPersp.

  spv_result_t ValidateFragmentShaderF32Vec3InputAtDefinition(

      const Decoration& decoration, const Instruction& inst);

  // Used for SubgroupEqMask, SubgroupGeMask, SubgroupGtMask, SubgroupLtMask,

  // SubgroupLeMask.

  spv_result_t ValidateI32Vec4InputAtDefinition(const Decoration& decoration,

                                                const Instruction& inst);

  // Used for SubgroupLocalInvocationId, SubgroupSize.

  spv_result_t ValidateI32InputAtDefinition(const Decoration& decoration,

                                            const Instruction& inst);

  // Used for SubgroupId, NumSubgroups.

  spv_result_t ValidateComputeI32InputAtDefinition(const Decoration& decoration,

                                                   const Instruction& inst);

  spv_result_t ValidatePrimitiveShadingRateAtDefinition(

      const Decoration& decoration, const Instruction& inst);

  spv_result_t ValidateShadingRateAtDefinition(const Decoration& decoration,

                                               const Instruction& inst);

  spv_result_t ValidateDescriptorHeapAtDefinition(const Decoration& decoration,

                                                  const Instruction& inst);

  spv_result_t ValidateRayTracingBuiltinsAtDefinition(

      const Decoration& decoration, const Instruction& inst);

  spv_result_t ValidateVolatileSemantics(const Decoration& decoration,

                                         const Instruction& inst);

  spv_result_t ValidateVolatileLoads(const Decoration& decoration,

                                     const Instruction& pointer,

                                     spv::ExecutionModel stage);

  spv_result_t ValidateMeshShadingEXTBuiltinsAtDefinition(

      const Decoration& decoration, const Instruction& inst);

  spv_result_t ValidateTileQCOMBuiltinAtDefinition(const Decoration& decoration,

                                                   const Instruction& inst);

  // Used as a common method for validating MeshEXT builtins

  spv_result_t ValidateMeshBuiltinInterfaceRules(

      const Decoration& decoration, const Instruction& inst,

      spv::Op scalar_type, const Instruction& referenced_from_inst);

  spv_result_t ValidatePrimitiveShadingRateInterfaceRules(

      const Decoration& decoration, const Instruction& inst,

      const Instruction& referenced_from_inst);

  // Builtin that needs check incase **not** used with MeshEXT

  spv_result_t ValidateNonMeshInterfaceRules(

      const Decoration& decoration, const Instruction& inst,

      const Instruction& referenced_from_inst);

  // The following section contains functions which are called when id defined

  // by |referenced_inst| is

  // 1. referenced by |referenced_from_inst|

  // 2. dependent on |built_in_inst| which is decorated with BuiltIn

  // |decoration|. Most functions are specific to a single built-in and have

  // naming scheme: ValidateXYZAtReference. Some functions are common to

  // multiple kinds of BuiltIn.

  spv_result_t ValidateFragCoordAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateFragDepthAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateFrontFacingAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateHelperInvocationAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateInvocationIdAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateInstanceIndexAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidatePatchVerticesAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidatePointCoordAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidatePointSizeAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidatePositionAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidatePrimitiveIdAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateSampleIdAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateSampleMaskAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateSamplePositionAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateTessCoordAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateTessLevelAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateLocalInvocationIndexAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateVertexIndexAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateLayerOrViewportIndexAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateWorkgroupSizeAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateClipOrCullDistanceAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateBaseInstanceOrVertexAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateDrawIndexAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateViewIndexAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateDeviceIndexAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateFragInvocationCountAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateFragSizeAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateFragStencilRefAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateFullyCoveredAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  // Used for GlobalInvocationId, LocalInvocationId, NumWorkgroups, WorkgroupId.

  spv_result_t ValidateComputeShaderI32Vec3InputAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  // Used for BaryCoord, BaryCoordNoPersp.

  spv_result_t ValidateFragmentShaderF32Vec3InputAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  // Used for SubgroupId and NumSubgroups.

  spv_result_t ValidateComputeI32InputAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateNVSMOrARMCoreBuiltinsAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidatePrimitiveShadingRateAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateShadingRateAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateRayTracingBuiltinsAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateMeshShadingEXTBuiltinsAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  spv_result_t ValidateTileQCOMBuiltinAtReference(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  // Validates that |built_in_inst| is not (even indirectly) referenced from

  // within a function which can be called with |execution_model|.

  //

  // |vuid| - Vulkan ID for the error, or a negative value if none.

  // |comment| - text explaining why the restriction was imposed.

  // |decoration| - BuiltIn decoration which causes the restriction.

  // |referenced_inst| - instruction which is dependent on |built_in_inst| and

  //                     defines the id which was referenced.

  // |referenced_from_inst| - instruction which references id defined by

  //                          |referenced_inst| from within a function.

  spv_result_t ValidateNotCalledWithExecutionModel(

      int vuid, const char* comment, spv::ExecutionModel execution_model,

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst);

  // The following section contains functions which check that the decorated

  // variable has the type specified in the function name. |diag| would be

  // called with a corresponding error message, if validation is not successful.

  spv_result_t ValidateBool(

      const Decoration& decoration, const Instruction& inst,

      const std::function<spv_result_t(const std::string& message)>& diag);

  spv_result_t ValidateBlockTypeOrArrayedType(

      const Decoration& decoration, const Instruction& inst,

      bool& present_in_block, spv::Op expected_scalar_type,

      const std::function<spv_result_t(const std::string& message)>& diag);

  spv_result_t ValidateI(

      const Decoration& decoration, const Instruction& inst,

      const std::function<spv_result_t(const std::string& message)>& diag);

  spv_result_t ValidateI32(

      const Decoration& decoration, const Instruction& inst,

      const std::function<spv_result_t(const std::string& message)>& diag);

  spv_result_t ValidateI32Vec(

      const Decoration& decoration, const Instruction& inst,

      uint32_t num_components,

      const std::function<spv_result_t(const std::string& message)>& diag);

  spv_result_t ValidateU32Vec(

      const Decoration& decoration, const Instruction& inst,

      uint32_t num_components,

      const std::function<spv_result_t(const std::string& message)>& diag);

  spv_result_t ValidateI32Arr(

      const Decoration& decoration, const Instruction& inst,

      const std::function<spv_result_t(const std::string& message)>& diag);

  spv_result_t ValidateArrayedI32Vec(

      const Decoration& decoration, const Instruction& inst,

      uint32_t num_components,

      const std::function<spv_result_t(const std::string& message)>& diag);

  spv_result_t ValidateOptionalArrayedI32(

      const Decoration& decoration, const Instruction& inst,

      const std::function<spv_result_t(const std::string& message)>& diag);

  spv_result_t ValidateI32Helper(

      const Decoration& decoration, const Instruction& inst,

      const std::function<spv_result_t(const std::string& message)>& diag,

      uint32_t underlying_type);

  spv_result_t ValidateF32(

      const Decoration& decoration, const Instruction& inst,

      const std::function<spv_result_t(const std::string& message)>& diag);

  spv_result_t ValidateOptionalArrayedF32(

      const Decoration& decoration, const Instruction& inst,

      const std::function<spv_result_t(const std::string& message)>& diag);

  spv_result_t ValidateF32Helper(

      const Decoration& decoration, const Instruction& inst,

      const std::function<spv_result_t(const std::string& message)>& diag,

      uint32_t underlying_type);

  spv_result_t ValidateF32Vec(

      const Decoration& decoration, const Instruction& inst,

      uint32_t num_components,

      const std::function<spv_result_t(const std::string& message)>& diag);

  spv_result_t ValidateOptionalArrayedF32Vec(

      const Decoration& decoration, const Instruction& inst,

      uint32_t num_components,

      const std::function<spv_result_t(const std::string& message)>& diag);

  spv_result_t ValidateArrayedF32Vec(

      const Decoration& decoration, const Instruction& inst,

      uint32_t num_components, uint32_t array_length,

      const std::function<spv_result_t(const std::string& message)>& diag);

  spv_result_t ValidateF32VecHelper(

      const Decoration& decoration, const Instruction& inst,

      uint32_t num_components,

      const std::function<spv_result_t(const std::string& message)>& diag,

      uint32_t underlying_type);

  // If |num_components| is zero, the number of components is not checked.

  spv_result_t ValidateF32Arr(

      const Decoration& decoration, const Instruction& inst,

      uint32_t num_components,

      const std::function<spv_result_t(const std::string& message)>& diag);

  spv_result_t ValidateOptionalArrayedF32Arr(

      const Decoration& decoration, const Instruction& inst,

      uint32_t num_components,

      const std::function<spv_result_t(const std::string& message)>& diag);

  spv_result_t ValidateF32ArrHelper(

      const Decoration& decoration, const Instruction& inst,

      uint32_t num_components,

      const std::function<spv_result_t(const std::string& message)>& diag,

      uint32_t underlying_type);

  spv_result_t ValidateF32Mat(

      const Decoration& decoration, const Instruction& inst,

      uint32_t req_num_rows, uint32_t req_num_columns,

      const std::function<spv_result_t(const std::string& message)>& diag);

  // Generates strings like "Member #0 of struct ID <2>".

  std::string GetDefinitionDesc(const Decoration& decoration,

                                const Instruction& inst) const;

  // Generates strings like "ID <51> (OpTypePointer) is referencing ID <2>

  // (OpTypeStruct) which is decorated with BuiltIn Position".

  std::string GetReferenceDesc(

      const Decoration& decoration, const Instruction& built_in_inst,

      const Instruction& referenced_inst,

      const Instruction& referenced_from_inst,

      spv::ExecutionModel execution_model = spv::ExecutionModel::Max) const;

  // Generates strings like "ID <51> (OpTypePointer) uses storage class

  // UniformConstant".

  std::string GetStorageClassDesc(const Instruction& inst) const;

  uint64_t GetArrayLength(uint32_t interface_var_id);

  // Updates inner working of the class. Is called sequentially for every

  // instruction.

  void Update(const Instruction& inst);

  bool IsBulitinInEntryPoint(const Instruction& inst, uint32_t entry_point) {

    auto get_underlying_type_id = [&](const Instruction* ifx_var) {

      auto pointer_type_inst = _.FindDef(ifx_var->type_id());

      auto type_inst = _.FindDef(pointer_type_inst->GetOperandAs<uint32_t>(2));

      while (type_inst->opcode() == spv::Op::OpTypeArray) {

        type_inst = _.FindDef(type_inst->GetOperandAs<uint32_t>(1));

      };

      return type_inst->id();

    };

    for (const auto& desc : _.entry_point_descriptions(entry_point)) {

      for (auto interface : desc.interfaces) {

        if (inst.opcode() == spv::Op::OpTypeStruct) {

          auto varInst = _.FindDef(interface);

          if (inst.id() == get_underlying_type_id(varInst)) {

            return true;

          }

        } else if (inst.id() == interface) {

          return true;

        }

      }

    }

    return false;

  }

  // Check if "inst" is an interface variable or type of a interface varibale

  // of any mesh entry point. Populate entry_point_interface_id with all

  // entry points and interface variables that refer to the "inst"

  bool IsMeshInterfaceVar(

      const Instruction& inst,

      std::map<uint32_t, uint32_t>& entry_point_interface_id) {

    auto get_underlying_type_id = [&](const Instruction* ifx_var) {

      auto pointer_type_inst = _.FindDef(ifx_var->type_id());

      auto type_inst = _.FindDef(pointer_type_inst->GetOperandAs<uint32_t>(2));

      while (type_inst->opcode() == spv::Op::OpTypeArray) {

        type_inst = _.FindDef(type_inst->GetOperandAs<uint32_t>(1));

      };

      return type_inst->id();

    };

    for (const uint32_t entry_point : _.entry_points()) {

      const auto* models = _.GetExecutionModels(entry_point);

      if (models->find(spv::ExecutionModel::MeshEXT) != models->end() ||

          models->find(spv::ExecutionModel::MeshNV) != models->end()) {

        for (const auto& desc : _.entry_point_descriptions(entry_point)) {

          for (auto interface : desc.interfaces) {

            if (inst.opcode() == spv::Op::OpTypeStruct) {

              auto varInst = _.FindDef(interface);

              if (inst.id() == get_underlying_type_id(varInst)) {

                entry_point_interface_id[entry_point] = interface;

                break;

              }

            } else if (inst.id() == interface) {

              entry_point_interface_id[entry_point] = interface;

              break;

            }

          }

        }

      }

    }

    return !entry_point_interface_id.empty();

  }

  ValidationState_t& _;

  // Mapping id -> list of rules which validate instruction referencing the

  // id. Rules can create new rules and add them to this container.

  // Using std::map, and not std::unordered_map to avoid iterator invalidation

  // during rehashing.

  std::map<uint32_t, std::list<std::function<spv_result_t(const Instruction&)>>>

      id_to_at_reference_checks_;

  // Id of the function we are currently inside. 0 if not inside a function.

  uint32_t function_id_ = 0;

  // Entry points which can (indirectly) call the current function.

  // The pointer either points to a vector inside to function_to_entry_points_

  // or to no_entry_points_. The pointer is guaranteed to never be null.

  const std::vector<uint32_t> no_entry_points;

  const std::vector<uint32_t>* entry_points_ = &no_entry_points;

  // Execution models with which the current function can be called.

  std::set<spv::ExecutionModel> execution_models_;

  // Execution modes with which the current function can be called.

  std::set<spv::ExecutionMode> execution_modes_;

  // For Builtin that can only be declared once in an entry point, keep track if

  // the entry point has it already

  std::set<uint32_t> cull_primitive_entry_points_;

};

void BuiltInsValidator::Update(const Instruction& inst) {

  const spv::Op opcode = inst.opcode();

  if (opcode == spv::Op::OpFunction) {

    // Entering a function.

    assert(function_id_ == 0);

    function_id_ = inst.id();

    execution_models_.clear();

    execution_modes_.clear();

    entry_points_ = &_.FunctionEntryPoints(function_id_);

    // Collect execution models from all entry points from which the current

    // function can be called.

    for (const uint32_t entry_point : *entry_points_) {

      if (const auto* models = _.GetExecutionModels(entry_point)) {

        execution_models_.insert(models->begin(), models->end());

      }

      if (const auto* modes = _.GetExecutionModes(entry_point)) {

        execution_modes_.insert(modes->begin(), modes->end());

      }

    }

  }

  if (opcode == spv::Op::OpFunctionEnd) {

    // Exiting a function.

    assert(function_id_ != 0);

    function_id_ = 0;

    entry_points_ = &no_entry_points;

    execution_models_.clear();

    execution_modes_.clear();

  }

}

std::string BuiltInsValidator::GetDefinitionDesc(

    const Decoration& decoration, const Instruction& inst) const {

  std::ostringstream ss;

  if (decoration.struct_member_index() != Decoration::kInvalidMember) {

    assert(inst.opcode() == spv::Op::OpTypeStruct);

    ss << "Member #" << decoration.struct_member_index();

    ss << " of struct ID <" << inst.id() << ">";

  } else {

    ss << GetIdDesc(inst);

  }

  return ss.str();

}

std::string BuiltInsValidator::GetReferenceDesc(

    const Decoration& decoration, const Instruction& built_in_inst,

    const Instruction& referenced_inst, const Instruction& referenced_from_inst,

    spv::ExecutionModel execution_model) const {

  std::ostringstream ss;

  ss << GetIdDesc(referenced_from_inst) << " is referencing "

     << GetIdDesc(referenced_inst);

  if (built_in_inst.id() != referenced_inst.id()) {

    ss << " which is dependent on " << GetIdDesc(built_in_inst);

  }

  ss << " which is decorated with BuiltIn ";

  ss << _.grammar().lookupOperandName(SPV_OPERAND_TYPE_BUILT_IN,

                                      (uint32_t)decoration.builtin());

  if (function_id_) {

    ss << " in function <" << function_id_ << ">";

    if (execution_model != spv::ExecutionModel::Max) {

      ss << " called with execution model ";

      ss << _.grammar().lookupOperandName(SPV_OPERAND_TYPE_EXECUTION_MODEL,

                                          uint32_t(execution_model));

    }

  }

  ss << ".";

  return ss.str();

}

std::string BuiltInsValidator::GetStorageClassDesc(

    const Instruction& inst) const {

  std::ostringstream ss;

  ss << GetIdDesc(inst) << " uses storage class ";

  ss << _.grammar().lookupOperandName(SPV_OPERAND_TYPE_STORAGE_CLASS,

                                      uint32_t(GetStorageClass(inst)));

  ss << ".";

  return ss.str();

}

uint64_t BuiltInsValidator::GetArrayLength(uint32_t interface_var_id) {

  uint32_t underlying_type;

  spv::StorageClass storage_class;

  uint64_t array_len = -1;

  const Instruction* inst = _.FindDef(interface_var_id);

  if (inst->opcode() != spv::Op::OpVariable) {

    return -1;

  }

  if (!_.GetPointerTypeInfo(inst->type_id(), &underlying_type,

                            &storage_class)) {

    return 0;

  }

  if (_.GetIdOpcode(underlying_type) == spv::Op::OpTypeArray) {

    // Get the array length

    const auto length_id = _.FindDef(underlying_type)->word(3u);

    if (!_.EvalConstantValUint64(length_id, &array_len)) {

      return 0;

    }

  }

  return array_len;

}

spv_result_t BuiltInsValidator::ValidateBool(

    const Decoration& decoration, const Instruction& inst,

    const std::function<spv_result_t(const std::string& message)>& diag) {

  uint32_t underlying_type = 0;

  if (spv_result_t error =

          GetUnderlyingType(_, decoration, inst, &underlying_type)) {

    return error;

  }

  if (!_.IsBoolScalarType(underlying_type)) {

    return diag(GetDefinitionDesc(decoration, inst) + " is not a bool scalar.");

  }

  return SPV_SUCCESS;

}

spv_result_t BuiltInsValidator::ValidateBlockTypeOrArrayedType(

    const Decoration& decoration, const Instruction& inst, bool& isBlock,

    spv::Op expected_scalar_type,

    const std::function<spv_result_t(const std::string& message)>& diag) {

  uint32_t underlying_type = 0;

  int64_t array_len = -1;

  isBlock = true;

  if (spv_result_t error =

          GetUnderlyingType(_, decoration, inst, &underlying_type)) {

    return error;

  }

  // Strip the array, if present.

  if (_.GetIdOpcode(underlying_type) == spv::Op::OpTypeArray) {

    // Get the array length

    const auto length_id = _.FindDef(underlying_type)->word(3u);

    if (!_.EvalConstantValInt64(length_id, &array_len)) {

      return diag(GetDefinitionDesc(decoration, inst) +

                  " Failed to find the array length.");

    }

    underlying_type = _.FindDef(underlying_type)->word(2u);

    isBlock = false;

  } else if (!_.HasDecoration(inst.id(), spv::Decoration::Block)) {

    // If not in array, and bool is in a struct, must be in a Block struct

    return diag(GetDefinitionDesc(decoration, inst) +

                " Scalar boolean must be in a Block.");

  }

  switch (expected_scalar_type) {

    case spv::Op::OpTypeBool:

      if (!_.IsBoolScalarType(underlying_type)) {