// 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.

#include "source/fuzz/fuzzer_pass_donate_modules.h"

#include <map>
#include <queue>
#include <set>

#include "source/fuzz/instruction_message.h"
#include "source/fuzz/transformation_add_constant_boolean.h"
#include "source/fuzz/transformation_add_constant_composite.h"
#include "source/fuzz/transformation_add_constant_scalar.h"
#include "source/fuzz/transformation_add_function.h"
#include "source/fuzz/transformation_add_global_undef.h"
#include "source/fuzz/transformation_add_global_variable.h"
#include "source/fuzz/transformation_add_type_array.h"
#include "source/fuzz/transformation_add_type_boolean.h"
#include "source/fuzz/transformation_add_type_float.h"
#include "source/fuzz/transformation_add_type_function.h"
#include "source/fuzz/transformation_add_type_int.h"
#include "source/fuzz/transformation_add_type_matrix.h"
#include "source/fuzz/transformation_add_type_pointer.h"
#include "source/fuzz/transformation_add_type_struct.h"
#include "source/fuzz/transformation_add_type_vector.h"

namespace spvtools {
namespace fuzz {

FuzzerPassDonateModules::FuzzerPassDonateModules(
    opt::IRContext* ir_context, FactManager* fact_manager,
    FuzzerContext* fuzzer_context,
    protobufs::TransformationSequence* transformations,
    const std::vector<fuzzerutil::ModuleSupplier>& donor_suppliers)
    : FuzzerPass(ir_context, fact_manager, fuzzer_context, transformations),
      donor_suppliers_(donor_suppliers) {}

FuzzerPassDonateModules::~FuzzerPassDonateModules() = default;

void FuzzerPassDonateModules::Apply() {
  // If there are no donor suppliers, this fuzzer pass is a no-op.
  if (donor_suppliers_.empty()) {
    return;
  }

  // Donate at least one module, and probabilistically decide when to stop
  // donating modules.
  do {
    // Choose a donor supplier at random, and get the module that it provides.
    std::unique_ptr<opt::IRContext> donor_ir_context = donor_suppliers_.at(
        GetFuzzerContext()->RandomIndex(donor_suppliers_))();
    assert(donor_ir_context != nullptr && "Supplying of donor failed");
    // Donate the supplied module.
    //
    // Randomly decide whether to make the module livesafe (see
    // FactFunctionIsLivesafe); doing so allows it to be used for live code
    // injection but restricts its behaviour to allow this, and means that its
    // functions cannot be transformed as if they were arbitrary dead code.
    bool make_livesafe = GetFuzzerContext()->ChoosePercentage(
        GetFuzzerContext()->ChanceOfMakingDonorLivesafe());
    DonateSingleModule(donor_ir_context.get(), make_livesafe);
  } while (GetFuzzerContext()->ChoosePercentage(
      GetFuzzerContext()->GetChanceOfDonatingAdditionalModule()));
}

void FuzzerPassDonateModules::DonateSingleModule(
    opt::IRContext* donor_ir_context, bool make_livesafe) {
  // The ids used by the donor module may very well clash with ids defined in
  // the recipient module.  Furthermore, some instructions defined in the donor
  // module will be equivalent to instructions defined in the recipient module,
  // and it is not always legal to re-declare equivalent instructions.  For
  // example, OpTypeVoid cannot be declared twice.
  //
  // To handle this, we maintain a mapping from an id used in the donor module
  // to the corresponding id that will be used by the donated code when it
  // appears in the recipient module.
  //
  // This mapping is populated in two ways:
  // (1) by mapping a donor instruction's result id to the id of some equivalent
  //     existing instruction in the recipient (e.g. this has to be done for
  //     OpTypeVoid)
  // (2) by mapping a donor instruction's result id to a freshly chosen id that
  //     is guaranteed to be different from any id already used by the recipient
  //     (or from any id already chosen to handle a previous donor id)
  std::map<uint32_t, uint32_t> original_id_to_donated_id;

  HandleExternalInstructionImports(donor_ir_context,
                                   &original_id_to_donated_id);
  HandleTypesAndValues(donor_ir_context, &original_id_to_donated_id);
  HandleFunctions(donor_ir_context, &original_id_to_donated_id, make_livesafe);

  // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3115) Handle some
  //  kinds of decoration.
}

SpvStorageClass FuzzerPassDonateModules::AdaptStorageClass(
    SpvStorageClass donor_storage_class) {
  switch (donor_storage_class) {
    case SpvStorageClassFunction:
    case SpvStorageClassPrivate:
      // We leave these alone
      return donor_storage_class;
    case SpvStorageClassInput:
    case SpvStorageClassOutput:
    case SpvStorageClassUniform:
    case SpvStorageClassUniformConstant:
    case SpvStorageClassPushConstant:
      // We change these to Private
      return SpvStorageClassPrivate;
    default:
      // Handle other cases on demand.
      assert(false && "Currently unsupported storage class.");
      return SpvStorageClassMax;
  }
}

void FuzzerPassDonateModules::HandleExternalInstructionImports(
    opt::IRContext* donor_ir_context,
    std::map<uint32_t, uint32_t>* original_id_to_donated_id) {
  // Consider every external instruction set import in the donor module.
  for (auto& donor_import : donor_ir_context->module()->ext_inst_imports()) {
    const auto& donor_import_name_words = donor_import.GetInOperand(0).words;
    // Look for an identical import in the recipient module.
    for (auto& existing_import : GetIRContext()->module()->ext_inst_imports()) {
      const auto& existing_import_name_words =
          existing_import.GetInOperand(0).words;
      if (donor_import_name_words == existing_import_name_words) {
        // A matching import has found.  Map the result id for the donor import
        // to the id of the existing import, so that when donor instructions
        // rely on the import they will be rewritten to use the existing import.
        original_id_to_donated_id->insert(
            {donor_import.result_id(), existing_import.result_id()});
        break;
      }
    }
    // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3116): At present
    //  we do not handle donation of instruction imports, i.e. we do not allow
    //  the donor to import instruction sets that the recipient did not already
    //  import.  It might be a good idea to allow this, but it requires some
    //  thought.
    assert(original_id_to_donated_id->count(donor_import.result_id()) &&
           "Donation of imports is not yet supported.");
  }
}

void FuzzerPassDonateModules::HandleTypesAndValues(
    opt::IRContext* donor_ir_context,
    std::map<uint32_t, uint32_t>* original_id_to_donated_id) {
  // Consider every type/global/constant/undef in the module.
  for (auto& type_or_value : donor_ir_context->module()->types_values()) {
    // Each such instruction generates a result id, and as part of donation we
    // need to associate the donor's result id with a new result id.  That new
    // result id will either be the id of some existing instruction, or a fresh
    // id.  This variable captures it.
    uint32_t new_result_id;

    // Decide how to handle each kind of instruction on a case-by-case basis.
    //
    // Because the donor module is required to be valid, when we encounter a
    // type comprised of component types (e.g. an aggregate or pointer), we know
    // that its component types will have been considered previously, and that
    // |original_id_to_donated_id| will already contain an entry for them.
    switch (type_or_value.opcode()) {
      case SpvOpTypeVoid: {
        // Void has to exist already in order for us to have an entry point.
        // Get the existing id of void.
        opt::analysis::Void void_type;
        new_result_id = GetIRContext()->get_type_mgr()->GetId(&void_type);
        assert(new_result_id &&
               "The module being transformed will always have 'void' type "
               "declared.");
      } break;
      case SpvOpTypeBool: {
        // Bool cannot be declared multiple times, so use its existing id if
        // present, or add a declaration of Bool with a fresh id if not.
        opt::analysis::Bool bool_type;
        auto bool_type_id = GetIRContext()->get_type_mgr()->GetId(&bool_type);
        if (bool_type_id) {
          new_result_id = bool_type_id;
        } else {
          new_result_id = GetFuzzerContext()->GetFreshId();
          ApplyTransformation(TransformationAddTypeBoolean(new_result_id));
        }
      } break;
      case SpvOpTypeInt: {
        // Int cannot be declared multiple times with the same width and
        // signedness, so check whether an existing identical Int type is
        // present and use its id if so.  Otherwise add a declaration of the
        // Int type used by the donor, with a fresh id.
        const uint32_t width = type_or_value.GetSingleWordInOperand(0);
        const bool is_signed =
            static_cast<bool>(type_or_value.GetSingleWordInOperand(1));
        opt::analysis::Integer int_type(width, is_signed);
        auto int_type_id = GetIRContext()->get_type_mgr()->GetId(&int_type);
        if (int_type_id) {
          new_result_id = int_type_id;
        } else {
          new_result_id = GetFuzzerContext()->GetFreshId();
          ApplyTransformation(
              TransformationAddTypeInt(new_result_id, width, is_signed));
        }
      } break;
      case SpvOpTypeFloat: {
        // Similar to SpvOpTypeInt.
        const uint32_t width = type_or_value.GetSingleWordInOperand(0);
        opt::analysis::Float float_type(width);
        auto float_type_id = GetIRContext()->get_type_mgr()->GetId(&float_type);
        if (float_type_id) {
          new_result_id = float_type_id;
        } else {
          new_result_id = GetFuzzerContext()->GetFreshId();
          ApplyTransformation(TransformationAddTypeFloat(new_result_id, width));
        }
      } break;
      case SpvOpTypeVector: {
        // It is not legal to have two Vector type declarations with identical
        // element types and element counts, so check whether an existing
        // identical Vector type is present and use its id if so.  Otherwise add
        // a declaration of the Vector type used by the donor, with a fresh id.

        // When considering the vector's component type id, we look up the id
        // use in the donor to find the id to which this has been remapped.
        uint32_t component_type_id = original_id_to_donated_id->at(
            type_or_value.GetSingleWordInOperand(0));
        auto component_type =
            GetIRContext()->get_type_mgr()->GetType(component_type_id);
        assert(component_type && "The base type should be registered.");
        auto component_count = type_or_value.GetSingleWordInOperand(1);
        opt::analysis::Vector vector_type(component_type, component_count);
        auto vector_type_id =
            GetIRContext()->get_type_mgr()->GetId(&vector_type);
        if (vector_type_id) {
          new_result_id = vector_type_id;
        } else {
          new_result_id = GetFuzzerContext()->GetFreshId();
          ApplyTransformation(TransformationAddTypeVector(
              new_result_id, component_type_id, component_count));
        }
      } break;
      case SpvOpTypeMatrix: {
        // Similar to SpvOpTypeVector.
        uint32_t column_type_id = original_id_to_donated_id->at(
            type_or_value.GetSingleWordInOperand(0));
        auto column_type =
            GetIRContext()->get_type_mgr()->GetType(column_type_id);
        assert(column_type && column_type->AsVector() &&
               "The column type should be a registered vector type.");
        auto column_count = type_or_value.GetSingleWordInOperand(1);
        opt::analysis::Matrix matrix_type(column_type, column_count);
        auto matrix_type_id =
            GetIRContext()->get_type_mgr()->GetId(&matrix_type);
        if (matrix_type_id) {
          new_result_id = matrix_type_id;
        } else {
          new_result_id = GetFuzzerContext()->GetFreshId();
          ApplyTransformation(TransformationAddTypeMatrix(
              new_result_id, column_type_id, column_count));
        }

      } break;
      case SpvOpTypeArray: {
        // It is OK to have multiple structurally identical array types, so
        // we go ahead and add a remapped version of the type declared by the
        // donor.
        new_result_id = GetFuzzerContext()->GetFreshId();
        ApplyTransformation(TransformationAddTypeArray(
            new_result_id,
            original_id_to_donated_id->at(
                type_or_value.GetSingleWordInOperand(0)),
            original_id_to_donated_id->at(
                type_or_value.GetSingleWordInOperand(1))));
      } break;
      case SpvOpTypeStruct: {
        // Similar to SpvOpTypeArray.
        new_result_id = GetFuzzerContext()->GetFreshId();
        std::vector<uint32_t> member_type_ids;
        type_or_value.ForEachInId(
            [&member_type_ids,
             &original_id_to_donated_id](const uint32_t* component_type_id) {
              member_type_ids.push_back(
                  original_id_to_donated_id->at(*component_type_id));
            });
        ApplyTransformation(
            TransformationAddTypeStruct(new_result_id, member_type_ids));
      } break;
      case SpvOpTypePointer: {
        // Similar to SpvOpTypeArray.
        new_result_id = GetFuzzerContext()->GetFreshId();
        ApplyTransformation(TransformationAddTypePointer(
            new_result_id,
            AdaptStorageClass(static_cast<SpvStorageClass>(
                type_or_value.GetSingleWordInOperand(0))),
            original_id_to_donated_id->at(
                type_or_value.GetSingleWordInOperand(1))));
      } break;
      case SpvOpTypeFunction: {
        // It is not OK to have multiple function types that use identical ids
        // for their return and parameter types.  We thus go through all
        // existing function types to look for a match.  We do not use the
        // type manager here because we want to regard two function types that
        // are structurally identical but that differ with respect to the
        // actual ids used for pointer types as different.
        //
        // Example:
        //
        // %1 = OpTypeVoid
        // %2 = OpTypeInt 32 0
        // %3 = OpTypePointer Function %2
        // %4 = OpTypePointer Function %2
        // %5 = OpTypeFunction %1 %3
        // %6 = OpTypeFunction %1 %4
        //
        // We regard %5 and %6 as distinct function types here, even though
        // they both have the form "uint32* -> void"

        std::vector<uint32_t> return_and_parameter_types;
        for (uint32_t i = 0; i < type_or_value.NumInOperands(); i++) {
          return_and_parameter_types.push_back(original_id_to_donated_id->at(
              type_or_value.GetSingleWordInOperand(i)));
        }
        uint32_t existing_function_id = fuzzerutil::FindFunctionType(
            GetIRContext(), return_and_parameter_types);
        if (existing_function_id) {
          new_result_id = existing_function_id;
        } else {
          // No match was found, so add a remapped version of the function type
          // to the module, with a fresh id.
          new_result_id = GetFuzzerContext()->GetFreshId();
          std::vector<uint32_t> argument_type_ids;
          for (uint32_t i = 1; i < type_or_value.NumInOperands(); i++) {
            argument_type_ids.push_back(original_id_to_donated_id->at(
                type_or_value.GetSingleWordInOperand(i)));
          }
          ApplyTransformation(TransformationAddTypeFunction(
              new_result_id,
              original_id_to_donated_id->at(
                  type_or_value.GetSingleWordInOperand(0)),
              argument_type_ids));
        }
      } break;
      case SpvOpConstantTrue:
      case SpvOpConstantFalse: {
        // It is OK to have duplicate definitions of True and False, so add
        // these to the module, using a remapped Bool type.
        new_result_id = GetFuzzerContext()->GetFreshId();
        ApplyTransformation(TransformationAddConstantBoolean(
            new_result_id, type_or_value.opcode() == SpvOpConstantTrue));
      } break;
      case SpvOpConstant: {
        // It is OK to have duplicate constant definitions, so add this to the
        // module using a remapped result type.
        new_result_id = GetFuzzerContext()->GetFreshId();
        std::vector<uint32_t> data_words;
        type_or_value.ForEachInOperand(
            [&data_words](const uint32_t* in_operand) {
              data_words.push_back(*in_operand);
            });
        ApplyTransformation(TransformationAddConstantScalar(
            new_result_id,
            original_id_to_donated_id->at(type_or_value.type_id()),
            data_words));
      } break;
      case SpvOpConstantComposite: {
        // It is OK to have duplicate constant composite definitions, so add
        // this to the module using remapped versions of all consituent ids and
        // the result type.
        new_result_id = GetFuzzerContext()->GetFreshId();
        std::vector<uint32_t> constituent_ids;
        type_or_value.ForEachInId(
            [&constituent_ids,
             &original_id_to_donated_id](const uint32_t* constituent_id) {
              constituent_ids.push_back(
                  original_id_to_donated_id->at(*constituent_id));
            });
        ApplyTransformation(TransformationAddConstantComposite(
            new_result_id,
            original_id_to_donated_id->at(type_or_value.type_id()),
            constituent_ids));
      } break;
      case SpvOpVariable: {
        // This is a global variable that could have one of various storage
        // classes.  However, we change all global variable pointer storage
        // classes (such as Uniform, Input and Output) to private when donating
        // pointer types.  Thus this variable's pointer type is guaranteed to
        // have storage class private.  As a result, we simply add a Private
        // storage class global variable, using remapped versions of the result
        // type and initializer ids for the global variable in the donor.
        //
        // We regard the added variable as having an irrelevant value.  This
        // means that future passes can add stores to the variable in any
        // way they wish, and pass them as pointer parameters to functions
        // without worrying about whether their data might get modified.
        new_result_id = GetFuzzerContext()->GetFreshId();
        uint32_t remapped_pointer_type =
            original_id_to_donated_id->at(type_or_value.type_id());
        uint32_t initializer_id;
        if (type_or_value.NumInOperands() == 1) {
          // The variable did not have an initializer; initialize it to zero.
          // This is to limit problems associated with uninitialized data.
          initializer_id = FindOrCreateZeroConstant(
              fuzzerutil::GetPointeeTypeIdFromPointerType(
                  GetIRContext(), remapped_pointer_type));
        } else {
          // The variable already had an initializer; use its remapped id.
          initializer_id = original_id_to_donated_id->at(
              type_or_value.GetSingleWordInOperand(1));
        }
        ApplyTransformation(TransformationAddGlobalVariable(
            new_result_id, remapped_pointer_type, initializer_id, true));
      } break;
      case SpvOpUndef: {
        // It is fine to have multiple Undef instructions of the same type, so
        // we just add this to the recipient module.
        new_result_id = GetFuzzerContext()->GetFreshId();
        ApplyTransformation(TransformationAddGlobalUndef(
            new_result_id,
            original_id_to_donated_id->at(type_or_value.type_id())));
      } break;
      default: {
        assert(0 && "Unknown type/value.");
        new_result_id = 0;
      } break;
    }
    // Update the id mapping to associate the instruction's result id with its
    // corresponding id in the recipient.
    original_id_to_donated_id->insert(
        {type_or_value.result_id(), new_result_id});
  }
}

void FuzzerPassDonateModules::HandleFunctions(
    opt::IRContext* donor_ir_context,
    std::map<uint32_t, uint32_t>* original_id_to_donated_id,
    bool make_livesafe) {
  // Get the ids of functions in the donor module, topologically sorted
  // according to the donor's call graph.
  auto topological_order =
      GetFunctionsInCallGraphTopologicalOrder(donor_ir_context);

  // Donate the functions in reverse topological order.  This ensures that a
  // function gets donated before any function that depends on it.  This allows
  // donation of the functions to be separated into a number of transformations,
  // each adding one function, such that every prefix of transformations leaves
  // the module valid.
  for (auto function_id = topological_order.rbegin();
       function_id != topological_order.rend(); ++function_id) {
    // Find the function to be donated.
    opt::Function* function_to_donate = nullptr;
    for (auto& function : *donor_ir_context->module()) {
      if (function.result_id() == *function_id) {
        function_to_donate = &function;
        break;
      }
    }
    assert(function_to_donate && "Function to be donated was not found.");

    // We will collect up protobuf messages representing the donor function's
    // instructions here, and use them to create an AddFunction transformation.
    std::vector<protobufs::Instruction> donated_instructions;

    // Scan through the function, remapping each result id that it generates to
    // a fresh id.  This is necessary because functions include forward
    // references, e.g. to labels.
    function_to_donate->ForEachInst([this, &original_id_to_donated_id](
                                        const opt::Instruction* instruction) {
      if (instruction->result_id()) {
        original_id_to_donated_id->insert(
            {instruction->result_id(), GetFuzzerContext()->GetFreshId()});
      }
    });

    // Consider every instruction of the donor function.
    function_to_donate->ForEachInst([this, &donated_instructions,
                                     &original_id_to_donated_id](
                                        const opt::Instruction* instruction) {
      // Get the instruction's input operands into donation-ready form,
      // remapping any id uses in the process.
      opt::Instruction::OperandList input_operands;

      // Consider each input operand in turn.
      for (uint32_t in_operand_index = 0;
           in_operand_index < instruction->NumInOperands();
           in_operand_index++) {
        std::vector<uint32_t> operand_data;
        const opt::Operand& in_operand =
            instruction->GetInOperand(in_operand_index);
        switch (in_operand.type) {
          case SPV_OPERAND_TYPE_ID:
          case SPV_OPERAND_TYPE_TYPE_ID:
          case SPV_OPERAND_TYPE_RESULT_ID:
          case SPV_OPERAND_TYPE_MEMORY_SEMANTICS_ID:
          case SPV_OPERAND_TYPE_SCOPE_ID:
            // This is an id operand - it consists of a single word of data,
            // which needs to be remapped so that it is replaced with the
            // donated form of the id.
            operand_data.push_back(
                original_id_to_donated_id->at(in_operand.words[0]));
            break;
          default:
            // For non-id operands, we just add each of the data words.
            for (auto word : in_operand.words) {
              operand_data.push_back(word);
            }
            break;
        }
        input_operands.push_back({in_operand.type, operand_data});
      }

      if (instruction->opcode() == SpvOpVariable &&
          instruction->NumInOperands() == 1) {
        // This is an uninitialized local variable.  Initialize it to zero.
        input_operands.push_back(
            {SPV_OPERAND_TYPE_ID,
             {FindOrCreateZeroConstant(
                 fuzzerutil::GetPointeeTypeIdFromPointerType(
                     GetIRContext(),
                     original_id_to_donated_id->at(instruction->type_id())))}});
      }

      // Remap the result type and result id (if present) of the
      // instruction, and turn it into a protobuf message.
      donated_instructions.push_back(MakeInstructionMessage(
          instruction->opcode(),
          instruction->type_id()
              ? original_id_to_donated_id->at(instruction->type_id())
              : 0,
          instruction->result_id()
              ? original_id_to_donated_id->at(instruction->result_id())
              : 0,
          input_operands));
    });

    if (make_livesafe) {
      // Various types and constants must be in place for a function to be made
      // live-safe.  Add them if not already present.
      FindOrCreateBoolType();  // Needed for comparisons
      FindOrCreatePointerTo32BitIntegerType(
          false, SpvStorageClassFunction);  // Needed for adding loop limiters
      FindOrCreate32BitIntegerConstant(
          0, false);  // Needed for initializing loop limiters
      FindOrCreate32BitIntegerConstant(
          1, false);  // Needed for incrementing loop limiters

      // Get a fresh id for the variable that will be used as a loop limiter.
      const uint32_t loop_limiter_variable_id =
          GetFuzzerContext()->GetFreshId();
      // Choose a random loop limit, and add the required constant to the
      // module if not already there.
      const uint32_t loop_limit = FindOrCreate32BitIntegerConstant(
          GetFuzzerContext()->GetRandomLoopLimit(), false);

      // Consider every loop header in the function to donate, and create a
      // structure capturing the ids to be used for manipulating the loop
      // limiter each time the loop is iterated.
      std::vector<protobufs::LoopLimiterInfo> loop_limiters;
      for (auto& block : *function_to_donate) {
        if (block.IsLoopHeader()) {
          protobufs::LoopLimiterInfo loop_limiter;
          // Grab the loop header's id, mapped to its donated value.
          loop_limiter.set_loop_header_id(
              original_id_to_donated_id->at(block.id()));
          // Get fresh ids that will be used to load the loop limiter, increment
          // it, compare it with the loop limit, and an id for a new block that
          // will contain the loop's original terminator.
          loop_limiter.set_load_id(GetFuzzerContext()->GetFreshId());
          loop_limiter.set_increment_id(GetFuzzerContext()->GetFreshId());
          loop_limiter.set_compare_id(GetFuzzerContext()->GetFreshId());
          loop_limiter.set_logical_op_id(GetFuzzerContext()->GetFreshId());
          loop_limiters.emplace_back(loop_limiter);
        }
      }

      // Consider every access chain in the function to donate, and create a
      // structure containing the ids necessary to clamp the access chain
      // indices to be in-bounds.
      std::vector<protobufs::AccessChainClampingInfo>
          access_chain_clamping_info;
      for (auto& block : *function_to_donate) {
        for (auto& inst : block) {
          switch (inst.opcode()) {
            case SpvOpAccessChain:
            case SpvOpInBoundsAccessChain: {
              protobufs::AccessChainClampingInfo clamping_info;
              clamping_info.set_access_chain_id(
                  original_id_to_donated_id->at(inst.result_id()));

              auto base_object = donor_ir_context->get_def_use_mgr()->GetDef(
                  inst.GetSingleWordInOperand(0));
              assert(base_object && "The base object must exist.");
              auto pointer_type = donor_ir_context->get_def_use_mgr()->GetDef(
                  base_object->type_id());
              assert(pointer_type &&
                     pointer_type->opcode() == SpvOpTypePointer &&
                     "The base object must have pointer type.");

              auto should_be_composite_type =
                  donor_ir_context->get_def_use_mgr()->GetDef(
                      pointer_type->GetSingleWordInOperand(1));

              // Walk the access chain, creating fresh ids to facilitate
              // clamping each index.  For simplicity we do this for every
              // index, even though constant indices will not end up being
              // clamped.
              for (uint32_t index = 1; index < inst.NumInOperands(); index++) {
                auto compare_and_select_ids =
                    clamping_info.add_compare_and_select_ids();
                compare_and_select_ids->set_first(
                    GetFuzzerContext()->GetFreshId());
                compare_and_select_ids->set_second(
                    GetFuzzerContext()->GetFreshId());

                // Get the bound for the component being indexed into.
                uint32_t bound =
                    TransformationAddFunction::GetBoundForCompositeIndex(
                        donor_ir_context, *should_be_composite_type);
                const uint32_t index_id = inst.GetSingleWordInOperand(index);
                auto index_inst =
                    donor_ir_context->get_def_use_mgr()->GetDef(index_id);
                auto index_type_inst =
                    donor_ir_context->get_def_use_mgr()->GetDef(
                        index_inst->type_id());
                assert(index_type_inst->opcode() == SpvOpTypeInt);
                assert(index_type_inst->GetSingleWordInOperand(0) == 32);
                opt::analysis::Integer* index_int_type =
                    donor_ir_context->get_type_mgr()
                        ->GetType(index_type_inst->result_id())
                        ->AsInteger();
                if (index_inst->opcode() != SpvOpConstant) {
                  // We will have to clamp this index, so we need a constant
                  // whose value is one less than the bound, to compare
                  // against and to use as the clamped value.
                  FindOrCreate32BitIntegerConstant(bound - 1,
                                                   index_int_type->IsSigned());
                }
                should_be_composite_type =
                    TransformationAddFunction::FollowCompositeIndex(
                        donor_ir_context, *should_be_composite_type, index_id);
              }
              access_chain_clamping_info.push_back(clamping_info);
              break;
            }
            default:
              break;
          }
        }
      }

      // If the function contains OpKill or OpUnreachable instructions, and has
      // non-void return type, then we need a value %v to use in order to turn
      // these into instructions of the form OpReturn %v.
      uint32_t kill_unreachable_return_value_id;
      auto function_return_type_inst =
          donor_ir_context->get_def_use_mgr()->GetDef(
              function_to_donate->type_id());
      if (function_return_type_inst->opcode() == SpvOpTypeVoid) {
        // The return type is void, so we don't need a return value.
        kill_unreachable_return_value_id = 0;
      } else {
        // We do need a return value; we use OpUndef.
        kill_unreachable_return_value_id =
            FindOrCreateGlobalUndef(function_return_type_inst->type_id());
      }
      // Add the function in a livesafe manner.
      ApplyTransformation(TransformationAddFunction(
          donated_instructions, loop_limiter_variable_id, loop_limit,
          loop_limiters, kill_unreachable_return_value_id,
          access_chain_clamping_info));
    } else {
      // Add the function in a non-livesafe manner.
      ApplyTransformation(TransformationAddFunction(donated_instructions));
    }
  }
}

std::vector<uint32_t>
FuzzerPassDonateModules::GetFunctionsInCallGraphTopologicalOrder(
    opt::IRContext* context) {
  // This is an implementation of Kahn’s algorithm for topological sorting.

  // For each function id, stores the number of distinct functions that call
  // the function.
  std::map<uint32_t, uint32_t> function_in_degree;

  // We first build a call graph for the module, and compute the in-degree for
  // each function in the process.
  // TODO(afd): If there is functionality elsewhere in the SPIR-V tools
  //  framework to construct call graphs it could be nice to re-use it here.
  std::map<uint32_t, std::set<uint32_t>> call_graph_edges;

  // Initialize function in-degree and call graph edges to 0 and empty.
  for (auto& function : *context->module()) {
    function_in_degree[function.result_id()] = 0;
    call_graph_edges[function.result_id()] = std::set<uint32_t>();
  }

  // Consider every function.
  for (auto& function : *context->module()) {
    // Avoid considering the same callee of this function multiple times by
    // recording known callees.
    std::set<uint32_t> known_callees;
    // Consider every function call instruction in every block.
    for (auto& block : function) {
      for (auto& instruction : block) {
        if (instruction.opcode() != SpvOpFunctionCall) {
          continue;
        }
        // Get the id of the function being called.
        uint32_t callee = instruction.GetSingleWordInOperand(0);
        if (known_callees.count(callee)) {
          // We have already considered a call to this function - ignore it.
          continue;
        }
        // Increase the callee's in-degree and add an edge to the call graph.
        function_in_degree[callee]++;
        call_graph_edges[function.result_id()].insert(callee);
        // Mark the callee as 'known'.
        known_callees.insert(callee);
      }
    }
  }

  // This is the sorted order of function ids that we will eventually return.
  std::vector<uint32_t> result;

  // Populate a queue with all those function ids with in-degree zero.
  std::queue<uint32_t> queue;
  for (auto& entry : function_in_degree) {
    if (entry.second == 0) {
      queue.push(entry.first);
    }
  }

  // Pop ids from the queue, adding them to the sorted order and decreasing the
  // in-degrees of their successors.  A successor who's in-degree becomes zero
  // gets added to the queue.
  while (!queue.empty()) {
    auto next = queue.front();
    queue.pop();
    result.push_back(next);
    for (auto successor : call_graph_edges.at(next)) {
      assert(function_in_degree.at(successor) > 0 &&
             "The in-degree cannot be zero if the function is a successor.");
      function_in_degree[successor] = function_in_degree.at(successor) - 1;
      if (function_in_degree.at(successor) == 0) {
        queue.push(successor);
      }
    }
  }

  assert(result.size() == function_in_degree.size() &&
         "Every function should appear in the sort.");

  return result;
}

}  // namespace fuzz
}  // namespace spvtools