bgfx/3rdparty/spirv-tools/source/diff/diff.cpp

// Copyright (c) 2022 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/diff/diff.h"

#include "source/diff/lcs.h"
#include "source/disassemble.h"
#include "source/ext_inst.h"
#include "source/latest_version_spirv_header.h"
#include "source/print.h"
#include "spirv-tools/libspirv.hpp"

namespace spvtools {
namespace diff {

namespace {

// A map from an id to the instruction that defines it.
using IdToInstructionMap = std::vector<const opt::Instruction*>;
// A map from an id to the instructions that decorate it, or name it, etc.
using IdToInfoMap = std::vector<std::vector<const opt::Instruction*>>;
// A map from an instruction to another, used for instructions without id.
using InstructionToInstructionMap =
    std::unordered_map<const opt::Instruction*, const opt::Instruction*>;
// A flat list of instructions in a function for easier iteration.
using InstructionList = std::vector<const opt::Instruction*>;
// A map from a function to its list of instructions.
using FunctionInstMap = std::map<uint32_t, InstructionList>;
// A list of ids with some similar property, for example functions with the same
// name.
using IdGroup = std::vector<uint32_t>;
// A map of names to ids with the same name.  This is an ordered map so
// different implementations produce identical results.
using IdGroupMapByName = std::map<std::string, IdGroup>;
using IdGroupMapByTypeId = std::map<uint32_t, IdGroup>;
using IdGroupMapByOp = std::map<spv::Op, IdGroup>;
using IdGroupMapByStorageClass = std::map<spv::StorageClass, IdGroup>;

// A set of potential id mappings that haven't been resolved yet.  Any id in src
// may map in any id in dst.  Note that ids are added in the same order as they
// appear in src and dst to facilitate matching dependent instructions.  For
// example, this guarantees that when matching OpTypeVector, the basic type of
// the vector is already (potentially) matched.
struct PotentialIdMap {
  std::vector<uint32_t> src_ids;
  std::vector<uint32_t> dst_ids;
};

void CompactIds(std::vector<uint32_t>& ids) {
  size_t write_index = 0;
  for (size_t i = 0; i < ids.size(); ++i) {
    if (ids[i] != 0) {
      ids[write_index++] = ids[i];
    }
  }
  ids.resize(write_index);
}

// A mapping from ids in one module to ids in the other.
//
// Differ contains two of these, for src->dst and dst->src.
class IdMap {
 public:
  IdMap(size_t id_bound) { id_map_.resize(id_bound, 0); }

  void MapIds(uint32_t from, uint32_t to) {
    assert(from != 0);
    assert(to != 0);
    assert(from < id_map_.size());
    assert(id_map_[from] == 0);

    id_map_[from] = to;
  }

  uint32_t MappedId(uint32_t from) const {
    assert(from != 0);
    return from < id_map_.size() ? id_map_[from] : 0;
  }
  const opt::Instruction* MappedInst(const opt::Instruction* from_inst) const {
    assert(from_inst != nullptr);
    assert(!from_inst->HasResultId());

    auto mapped = inst_map_.find(from_inst);
    if (mapped == inst_map_.end()) {
      return nullptr;
    }
    return mapped->second;
  }

  bool IsMapped(uint32_t from) const {
    assert(from != 0);
    return from < id_map_.size() && id_map_[from] != 0;
  }

  bool IsMapped(const opt::Instruction* from_inst) const {
    assert(from_inst != nullptr);
    assert(!from_inst->HasResultId());

    return inst_map_.find(from_inst) != inst_map_.end();
  }

  // Some instructions don't have result ids.  Those are mapped by pointer.
  void MapInsts(const opt::Instruction* from_inst,
                const opt::Instruction* to_inst) {
    assert(from_inst != nullptr);
    assert(to_inst != nullptr);
    assert(inst_map_.find(from_inst) == inst_map_.end());

    inst_map_[from_inst] = to_inst;
  }

  uint32_t IdBound() const { return static_cast<uint32_t>(id_map_.size()); }

  // Generate a fresh id in this mapping's domain.
  uint32_t MakeFreshId() {
    id_map_.push_back(0);
    return static_cast<uint32_t>(id_map_.size()) - 1;
  }

 private:
  // Given an id, returns the corresponding id in the other module, or 0 if not
  // matched yet.
  std::vector<uint32_t> id_map_;

  // Same for instructions that don't have an id.
  InstructionToInstructionMap inst_map_;
};

// Two way mapping of ids.
class SrcDstIdMap {
 public:
  SrcDstIdMap(size_t src_id_bound, size_t dst_id_bound)
      : src_to_dst_(src_id_bound), dst_to_src_(dst_id_bound) {}

  void MapIds(uint32_t src, uint32_t dst) {
    src_to_dst_.MapIds(src, dst);
    dst_to_src_.MapIds(dst, src);
  }

  uint32_t MappedDstId(uint32_t src) {
    uint32_t dst = src_to_dst_.MappedId(src);
    assert(dst == 0 || dst_to_src_.MappedId(dst) == src);
    return dst;
  }
  uint32_t MappedSrcId(uint32_t dst) {
    uint32_t src = dst_to_src_.MappedId(dst);
    assert(src == 0 || src_to_dst_.MappedId(src) == dst);
    return src;
  }

  bool IsSrcMapped(uint32_t src) { return src_to_dst_.IsMapped(src); }
  bool IsDstMapped(uint32_t dst) { return dst_to_src_.IsMapped(dst); }
  bool IsDstMapped(const opt::Instruction* dst_inst) {
    return dst_to_src_.IsMapped(dst_inst);
  }

  // Map any ids in src and dst that have not been mapped to new ids in dst and
  // src respectively. Use src_insn_defined and dst_insn_defined to ignore ids
  // that are simply never defined. (Since we assume the inputs are valid
  // SPIR-V, this implies they are also never used.)
  void MapUnmatchedIds(std::function<bool(uint32_t)> src_insn_defined,
                       std::function<bool(uint32_t)> dst_insn_defined);

  // Some instructions don't have result ids.  Those are mapped by pointer.
  void MapInsts(const opt::Instruction* src_inst,
                const opt::Instruction* dst_inst) {
    assert(src_inst->HasResultId() == dst_inst->HasResultId());
    if (src_inst->HasResultId()) {
      MapIds(src_inst->result_id(), dst_inst->result_id());
    } else {
      src_to_dst_.MapInsts(src_inst, dst_inst);
      dst_to_src_.MapInsts(dst_inst, src_inst);
    }
  }

  const IdMap& SrcToDstMap() const { return src_to_dst_; }
  const IdMap& DstToSrcMap() const { return dst_to_src_; }

 private:
  IdMap src_to_dst_;
  IdMap dst_to_src_;
};

// Mappings from ids to instructions and metadata, for a single module's ids.
struct IdInstructions {
  IdInstructions(const opt::Module* module)
      : inst_map_(module->IdBound(), nullptr),
        name_map_(module->IdBound()),
        decoration_map_(module->IdBound()),
        forward_pointer_map_(module->IdBound()) {
    // Map ids from all sections to instructions that define them.
    MapIdsToInstruction(module->ext_inst_imports());
    MapIdsToInstruction(module->debugs1());
    MapIdsToInstruction(module->debugs2());
    MapIdsToInstruction(module->debugs3());
    MapIdsToInstruction(module->ext_inst_debuginfo());
    MapIdsToInstruction(module->types_values());
    for (const opt::Function& function : *module) {
      function.ForEachInst(
          [this](const opt::Instruction* inst) {
            if (inst->HasResultId()) {
              MapIdToInstruction(inst->result_id(), inst);
            }
          },
          true, true);
    }

    // Gather decorations applied to ids that could be useful in matching them
    // between src and dst modules.
    MapIdsToInfos(module->debugs2());
    MapIdsToInfos(module->annotations());
    MapIdsToInfos(module->types_values());
  }

  void MapIdToInstruction(uint32_t id, const opt::Instruction* inst);

  // Return true if id is mapped to any instruction, false otherwise.
  bool IsDefined(uint32_t id) {
    return id < inst_map_.size() && inst_map_[id] != nullptr;
  }

  void MapIdsToInstruction(
      opt::IteratorRange<opt::Module::const_inst_iterator> section);
  void MapIdsToInfos(
      opt::IteratorRange<opt::Module::const_inst_iterator> section);

  IdToInstructionMap inst_map_;
  IdToInfoMap name_map_;
  IdToInfoMap decoration_map_;
  IdToInstructionMap forward_pointer_map_;
};

class Differ {
 public:
  Differ(opt::IRContext* src, opt::IRContext* dst, std::ostream& out,
         Options options)
      : src_context_(src),
        dst_context_(dst),
        src_(src->module()),
        dst_(dst->module()),
        options_(options),
        out_(out),
        src_id_to_(src_),
        dst_id_to_(dst_),
        id_map_(src_->IdBound(), dst_->IdBound()) {
    // Cache function bodies in canonicalization order.
    GetFunctionBodies(src_context_, &src_funcs_, &src_func_insts_);
    GetFunctionBodies(dst_context_, &dst_funcs_, &dst_func_insts_);
  }

  // Match ids or instructions of different sections.
  void MatchCapabilities();
  void MatchExtensions();
  void MatchExtInstImportIds();
  void MatchMemoryModel();
  void MatchEntryPointIds();
  void MatchExecutionModes();
  void MatchTypeForwardPointers();
  void MatchTypeIds();
  void MatchConstants();
  void MatchVariableIds();
  void MatchFunctions();

  // Debug info and annotations are matched only after ids are matched.
  void MatchDebugs1();
  void MatchDebugs2();
  void MatchDebugs3();
  void MatchExtInstDebugInfo();
  void MatchAnnotations();

  // Output the diff.
  spv_result_t Output();

  void DumpIdMap() {
    if (!options_.dump_id_map) {
      return;
    }

    out_ << " Src ->  Dst\n";
    for (uint32_t src_id = 1; src_id < src_->IdBound(); ++src_id) {
      uint32_t dst_id = id_map_.MappedDstId(src_id);
      if (src_id_to_.inst_map_[src_id] != nullptr && dst_id != 0)
        out_ << std::setw(4) << src_id << " -> " << std::setw(4) << dst_id
             << " [" << spvOpcodeString(src_id_to_.inst_map_[src_id]->opcode())
             << "]\n";
    }
  }

 private:
  // Helper functions that match ids between src and dst
  void PoolPotentialIds(
      opt::IteratorRange<opt::Module::const_inst_iterator> section,
      std::vector<uint32_t>& ids, bool is_src,
      std::function<bool(const opt::Instruction&)> filter,
      std::function<uint32_t(const opt::Instruction&)> get_id);
  void MatchIds(
      PotentialIdMap& potential,
      std::function<bool(const opt::Instruction*, const opt::Instruction*)>
          match);
  // Helper functions that match id-less instructions between src and dst.
  void MatchPreambleInstructions(
      opt::IteratorRange<opt::Module::const_inst_iterator> src_insts,
      opt::IteratorRange<opt::Module::const_inst_iterator> dst_insts);
  InstructionList SortPreambleInstructions(
      const opt::Module* module,
      opt::IteratorRange<opt::Module::const_inst_iterator> insts);
  int ComparePreambleInstructions(const opt::Instruction* a,
                                  const opt::Instruction* b,
                                  const opt::Module* src_inst_module,
                                  const opt::Module* dst_inst_module);
  // Helper functions that match debug and annotation instructions of already
  // matched ids.
  void MatchDebugAndAnnotationInstructions(
      opt::IteratorRange<opt::Module::const_inst_iterator> src_insts,
      opt::IteratorRange<opt::Module::const_inst_iterator> dst_insts);

  // Get various properties from an id.  These Helper functions are passed to
  // `GroupIds` and `GroupIdsAndMatch` below (as the `get_group` argument).
  uint32_t GroupIdsHelperGetTypeId(const IdInstructions& id_to, uint32_t id);
  uint32_t GroupIdsHelperGetFunctionTypeId(const IdInstructions& id_to,
                                           uint32_t id);
  spv::StorageClass GroupIdsHelperGetTypePointerStorageClass(
      const IdInstructions& id_to, uint32_t id);
  spv::Op GroupIdsHelperGetTypePointerTypeOp(const IdInstructions& id_to,
                                             uint32_t id);

  // Given a list of ids, groups them based on some value.  The `get_group`
  // function extracts a piece of information corresponding to each id, and the
  // ids are bucketed based on that (and output in `groups`).  This is useful to
  // attempt to match ids between src and dst only when said property is
  // identical.
  template <typename T>
  void GroupIds(const IdGroup& ids, bool is_src, std::map<T, IdGroup>* groups,
                T (Differ::*get_group)(const IdInstructions&, uint32_t));

  // Calls GroupIds to bucket ids in src and dst based on a property returned by
  // `get_group`.  This function then calls `match_group` for each bucket (i.e.
  // "group") with identical values for said property.
  //
  // For example, say src and dst ids have the following properties
  // correspondingly:
  //
  // - src ids' properties: {id0: A, id1: A, id2: B, id3: C, id4: B}
  // - dst ids' properties: {id0': B, id1': C, id2': B, id3': D, id4': B}
  //
  // Then `match_group` is called 2 times:
  //
  // - Once with: ([id2, id4], [id0', id2', id4']) corresponding to B
  // - Once with: ([id3], [id2']) corresponding to C
  //
  // Ids corresponding to A and D cannot match based on this property.
  template <typename T>
  void GroupIdsAndMatch(
      const IdGroup& src_ids, const IdGroup& dst_ids, T invalid_group_key,
      T (Differ::*get_group)(const IdInstructions&, uint32_t),
      std::function<void(const IdGroup& src_group, const IdGroup& dst_group)>
          match_group);

  // Bucket `src_ids` and `dst_ids` by the key ids returned by `get_group`, and
  // then call `match_group` on pairs of buckets whose key ids are matched with
  // each other.
  //
  // For example, suppose we want to pair up groups of instructions with the
  // same type. Naturally, the source instructions refer to their types by their
  // ids in the source, and the destination instructions use destination type
  // ids, so simply comparing source and destination type ids as integers, as
  // `GroupIdsAndMatch` would do, is meaningless. But if a prior call to
  // `MatchTypeIds` has established type matches between the two modules, then
  // we can consult those to pair source and destination buckets whose types are
  // equivalent.
  //
  // Suppose our input groups are as follows:
  //
  // - src_ids: { 1 -> 100, 2 -> 300, 3 -> 100, 4 -> 200 }
  // - dst_ids: { 5 -> 10, 6 -> 20, 7 -> 10, 8 -> 300 }
  //
  // Here, `X -> Y` means that the instruction with SPIR-V id `X` is a member of
  // the group, and `Y` is the id of its type. If we use
  // `Differ::GroupIdsHelperGetTypeId` for `get_group`, then
  // `get_group(X) == Y`.
  //
  // These instructions are bucketed by type as follows:
  //
  // - source:      [1, 3] -> 100
  //                [4] -> 200
  //                [2] -> 300
  //
  // - destination: [5, 7] -> 10
  //                [6] -> 20
  //                [8] -> 300
  //
  // Now suppose that we have previously matched up src type 100 with dst type
  // 10, and src type 200 with dst type 20, but no other types are matched.
  //
  // Then `match_group` is called twice:
  // - Once with ([1,3], [5, 7]), corresponding to 100/10
  // - Once with ([4],[6]), corresponding to 200/20
  //
  // The source type 300 isn't matched with anything, so the fact that there's a
  // destination type 300 is irrelevant, and thus 2 and 8 are never passed to
  // `match_group`.
  //
  // This function isn't specific to types; it simply buckets by the ids
  // returned from `get_group`, and consults existing matches to pair up the
  // resulting buckets.
  void GroupIdsAndMatchByMappedId(
      const IdGroup& src_ids, const IdGroup& dst_ids,
      uint32_t (Differ::*get_group)(const IdInstructions&, uint32_t),
      std::function<void(const IdGroup& src_group, const IdGroup& dst_group)>
          match_group);

  // Helper functions that determine if two instructions match
  bool DoIdsMatch(uint32_t src_id, uint32_t dst_id);
  bool DoesOperandMatch(const opt::Operand& src_operand,
                        const opt::Operand& dst_operand);
  bool DoOperandsMatch(const opt::Instruction* src_inst,
                       const opt::Instruction* dst_inst,
                       uint32_t in_operand_index_start,
                       uint32_t in_operand_count);
  bool DoInstructionsMatch(const opt::Instruction* src_inst,
                           const opt::Instruction* dst_inst);
  bool DoIdsMatchFuzzy(uint32_t src_id, uint32_t dst_id);
  bool DoesOperandMatchFuzzy(const opt::Operand& src_operand,
                             const opt::Operand& dst_operand);
  bool DoInstructionsMatchFuzzy(const opt::Instruction* src_inst,
                                const opt::Instruction* dst_inst);
  bool AreIdenticalUintConstants(uint32_t src_id, uint32_t dst_id);
  bool DoDebugAndAnnotationInstructionsMatch(const opt::Instruction* src_inst,
                                             const opt::Instruction* dst_inst);
  bool AreVariablesMatchable(uint32_t src_id, uint32_t dst_id,
                             uint32_t flexibility);
  bool MatchOpTypeStruct(const opt::Instruction* src_inst,
                         const opt::Instruction* dst_inst,
                         uint32_t flexibility);
  bool MatchOpConstant(const opt::Instruction* src_inst,
                       const opt::Instruction* dst_inst, uint32_t flexibility);
  bool MatchOpSpecConstant(const opt::Instruction* src_inst,
                           const opt::Instruction* dst_inst);
  bool MatchOpVariable(const opt::Instruction* src_inst,
                       const opt::Instruction* dst_inst, uint32_t flexibility);
  bool MatchPerVertexType(uint32_t src_type_id, uint32_t dst_type_id);
  bool MatchPerVertexVariable(const opt::Instruction* src_inst,
                              const opt::Instruction* dst_inst);

  // Helper functions for matching OpTypeForwardPointer
  void MatchTypeForwardPointersByName(const IdGroup& src, const IdGroup& dst);
  void MatchTypeForwardPointersByTypeOp(const IdGroup& src, const IdGroup& dst);

  // Helper functions for function matching.
  using FunctionMap = std::map<uint32_t, const opt::Function*>;

  InstructionList GetFunctionBody(opt::IRContext* context,
                                  opt::Function& function);
  InstructionList GetFunctionHeader(const opt::Function& function);
  void GetFunctionBodies(opt::IRContext* context, FunctionMap* functions,
                         FunctionInstMap* function_insts);
  void GetFunctionHeaderInstructions(const opt::Module* module,
                                     FunctionInstMap* function_insts);
  void BestEffortMatchFunctions(const IdGroup& src_func_ids,
                                const IdGroup& dst_func_ids,
                                const FunctionInstMap& src_func_insts,
                                const FunctionInstMap& dst_func_insts);

  // Calculates the diff of two function bodies.  Note that the matched
  // instructions themselves may not be identical; output of exact matches
  // should produce the exact instruction while inexact matches should produce a
  // diff as well.
  //
  // Returns the similarity of the two bodies = 2*N_match / (N_src + N_dst)
  void MatchFunctionParamIds(const opt::Function* src_func,
                             const opt::Function* dst_func);
  float MatchFunctionBodies(const InstructionList& src_body,
                            const InstructionList& dst_body,
                            DiffMatch* src_match_result,
                            DiffMatch* dst_match_result);
  void MatchIdsInFunctionBodies(const InstructionList& src_body,
                                const InstructionList& dst_body,
                                const DiffMatch& src_match_result,
                                const DiffMatch& dst_match_result,
                                uint32_t flexibility);
  void MatchVariablesUsedByMatchedInstructions(const opt::Instruction* src_inst,
                                               const opt::Instruction* dst_inst,
                                               uint32_t flexibility);

  // Helper functions to retrieve information pertaining to an id
  const opt::Instruction* GetInst(const IdInstructions& id_to, uint32_t id);
  uint32_t GetConstantUint(const IdInstructions& id_to, uint32_t constant_id);
  spv::ExecutionModel GetExecutionModel(const opt::Module* module,
                                        uint32_t entry_point_id);
  bool HasName(const IdInstructions& id_to, uint32_t id);
  // Get the OpName associated with an id
  std::string GetName(const IdInstructions& id_to, uint32_t id, bool* has_name);
  // Get the OpName associated with an id, with argument types stripped for
  // functions.  Some tools don't encode function argument types in the OpName
  // string, and this improves diff between SPIR-V from those tools and others.
  std::string GetSanitizedName(const IdInstructions& id_to, uint32_t id);
  uint32_t GetVarTypeId(const IdInstructions& id_to, uint32_t var_id,
                        spv::StorageClass* storage_class);
  bool GetDecorationValue(const IdInstructions& id_to, uint32_t id,
                          spv::Decoration decoration,
                          uint32_t* decoration_value);
  const opt::Instruction* GetForwardPointerInst(const IdInstructions& id_to,
                                                uint32_t id);
  bool IsIntType(const IdInstructions& id_to, uint32_t type_id);
  bool IsFloatType(const IdInstructions& id_to, uint32_t type_id);
  bool IsConstantUint(const IdInstructions& id_to, uint32_t id);
  bool IsVariable(const IdInstructions& id_to, uint32_t pointer_id);
  bool IsOp(const IdInstructions& id_to, uint32_t id, spv::Op opcode);
  bool IsPerVertexType(const IdInstructions& id_to, uint32_t type_id);
  bool IsPerVertexVariable(const IdInstructions& id_to, uint32_t type_id);
  spv::StorageClass GetPerVertexStorageClass(const opt::Module* module,
                                             uint32_t type_id);
  spv_ext_inst_type_t GetExtInstType(const IdInstructions& id_to,
                                     uint32_t set_id);
  spv_number_kind_t GetNumberKind(const IdInstructions& id_to,
                                  const opt::Instruction& inst,
                                  uint32_t operand_index,
                                  uint32_t* number_bit_width);
  spv_number_kind_t GetTypeNumberKind(const IdInstructions& id_to, uint32_t id,
                                      uint32_t* number_bit_width);

  // Helper functions to output a diff line
  const opt::Instruction* MappedDstInst(const opt::Instruction* src_inst);
  const opt::Instruction* MappedSrcInst(const opt::Instruction* dst_inst);
  const opt::Instruction* MappedInstImpl(const opt::Instruction* inst,
                                         const IdMap& to_other,
                                         const IdInstructions& other_id_to);
  void OutputLine(std::function<bool()> are_lines_identical,
                  std::function<void()> output_src_line,
                  std::function<void()> output_dst_line);
  template <typename InstList>
  void OutputSection(
      const InstList& src_insts, const InstList& dst_insts,
      std::function<void(const opt::Instruction&, const IdInstructions&,
                         const opt::Instruction&)>
          write_inst);
  void ToParsedInstruction(const opt::Instruction& inst,
                           const IdInstructions& id_to,
                           const opt::Instruction& original_inst,
                           spv_parsed_instruction_t* parsed_inst,
                           std::vector<spv_parsed_operand_t>& parsed_operands,
                           std::vector<uint32_t>& inst_binary);
  opt::Instruction ToMappedSrcIds(const opt::Instruction& dst_inst);

  void OutputRed() {
    if (options_.color_output) out_ << spvtools::clr::red{true};
  }
  void OutputGreen() {
    if (options_.color_output) out_ << spvtools::clr::green{true};
  }
  void OutputResetColor() {
    if (options_.color_output) out_ << spvtools::clr::reset{true};
  }

  opt::IRContext* src_context_;
  opt::IRContext* dst_context_;
  const opt::Module* src_;
  const opt::Module* dst_;
  Options options_;
  std::ostream& out_;

  // Helpers to look up instructions based on id.
  IdInstructions src_id_to_;
  IdInstructions dst_id_to_;

  // The ids that have been matched between src and dst so far.
  SrcDstIdMap id_map_;

  // List of instructions in function bodies after canonicalization.  Cached
  // here to avoid duplicate work.  More importantly, some maps use
  // opt::Instruction pointers so they need to be unique.
  FunctionInstMap src_func_insts_;
  FunctionInstMap dst_func_insts_;
  FunctionMap src_funcs_;
  FunctionMap dst_funcs_;
};

void SrcDstIdMap::MapUnmatchedIds(
    std::function<bool(uint32_t)> src_insn_defined,
    std::function<bool(uint32_t)> dst_insn_defined) {
  const uint32_t src_id_bound = static_cast<uint32_t>(src_to_dst_.IdBound());
  const uint32_t dst_id_bound = static_cast<uint32_t>(dst_to_src_.IdBound());

  for (uint32_t src_id = 1; src_id < src_id_bound; ++src_id) {
    if (!src_to_dst_.IsMapped(src_id) && src_insn_defined(src_id)) {
      uint32_t fresh_dst_id = dst_to_src_.MakeFreshId();
      MapIds(src_id, fresh_dst_id);
    }
  }

  for (uint32_t dst_id = 1; dst_id < dst_id_bound; ++dst_id) {
    if (!dst_to_src_.IsMapped(dst_id) && dst_insn_defined(dst_id)) {
      uint32_t fresh_src_id = src_to_dst_.MakeFreshId();
      MapIds(fresh_src_id, dst_id);
    }
  }
}

void IdInstructions::MapIdToInstruction(uint32_t id,
                                        const opt::Instruction* inst) {
  assert(id != 0);
  assert(id < inst_map_.size());
  assert(inst_map_[id] == nullptr);

  inst_map_[id] = inst;
}

void IdInstructions::MapIdsToInstruction(
    opt::IteratorRange<opt::Module::const_inst_iterator> section) {
  for (const opt::Instruction& inst : section) {
    uint32_t result_id = inst.result_id();
    if (result_id == 0) {
      continue;
    }

    MapIdToInstruction(result_id, &inst);
  }
}

void IdInstructions::MapIdsToInfos(
    opt::IteratorRange<opt::Module::const_inst_iterator> section) {
  for (const opt::Instruction& inst : section) {
    IdToInfoMap* info_map = nullptr;
    uint32_t id_operand = 0;

    switch (inst.opcode()) {
      case spv::Op::OpName:
        info_map = &name_map_;
        break;
      case spv::Op::OpMemberName:
        info_map = &name_map_;
        break;
      case spv::Op::OpDecorate:
        info_map = &decoration_map_;
        break;
      case spv::Op::OpMemberDecorate:
        info_map = &decoration_map_;
        break;
      case spv::Op::OpTypeForwardPointer: {
        uint32_t id = inst.GetSingleWordOperand(0);
        assert(id != 0);

        assert(id < forward_pointer_map_.size());
        forward_pointer_map_[id] = &inst;
        continue;
      }
      default:
        // Currently unsupported instruction, don't attempt to use it for
        // matching.
        break;
    }

    if (info_map == nullptr) {
      continue;
    }

    uint32_t id = inst.GetOperand(id_operand).AsId();
    assert(id != 0);

    assert(id < info_map->size());
    assert(std::find((*info_map)[id].begin(), (*info_map)[id].end(), &inst) ==
           (*info_map)[id].end());

    (*info_map)[id].push_back(&inst);
  }
}

void Differ::PoolPotentialIds(
    opt::IteratorRange<opt::Module::const_inst_iterator> section,
    std::vector<uint32_t>& ids, bool is_src,
    std::function<bool(const opt::Instruction&)> filter,
    std::function<uint32_t(const opt::Instruction&)> get_id) {
  for (const opt::Instruction& inst : section) {
    if (!filter(inst)) {
      continue;
    }

    uint32_t result_id = get_id(inst);
    assert(result_id != 0);

    assert(std::find(ids.begin(), ids.end(), result_id) == ids.end());

    // Don't include ids that are already matched, for example through
    // OpTypeForwardPointer.
    const bool is_matched = is_src ? id_map_.IsSrcMapped(result_id)
                                   : id_map_.IsDstMapped(result_id);
    if (is_matched) {
      continue;
    }

    ids.push_back(result_id);
  }
}

void Differ::MatchIds(
    PotentialIdMap& potential,
    std::function<bool(const opt::Instruction*, const opt::Instruction*)>
        match) {
  for (size_t src_index = 0; src_index < potential.src_ids.size();
       ++src_index) {
    for (size_t dst_index = 0; dst_index < potential.dst_ids.size();
         ++dst_index) {
      const uint32_t src_id = potential.src_ids[src_index];
      const uint32_t dst_id = potential.dst_ids[dst_index];

      if (dst_id == 0) {
        // Already matched.
        continue;
      }

      const opt::Instruction* src_inst = src_id_to_.inst_map_[src_id];
      const opt::Instruction* dst_inst = dst_id_to_.inst_map_[dst_id];

      if (match(src_inst, dst_inst)) {
        id_map_.MapIds(src_id, dst_id);

        // Remove the ids from the potential list.
        potential.src_ids[src_index] = 0;
        potential.dst_ids[dst_index] = 0;

        // Find a match for the next src id.
        break;
      }
    }
  }

  // Remove matched ids to make the next iteration faster.
  CompactIds(potential.src_ids);
  CompactIds(potential.dst_ids);
}

void Differ::MatchPreambleInstructions(
    opt::IteratorRange<opt::Module::const_inst_iterator> src_insts,
    opt::IteratorRange<opt::Module::const_inst_iterator> dst_insts) {
  // First, pool all instructions from each section and sort them.
  InstructionList sorted_src_insts = SortPreambleInstructions(src_, src_insts);
  InstructionList sorted_dst_insts = SortPreambleInstructions(dst_, dst_insts);

  // Then walk and match them.
  size_t src_cur = 0;
  size_t dst_cur = 0;

  while (src_cur < sorted_src_insts.size() &&
         dst_cur < sorted_dst_insts.size()) {
    const opt::Instruction* src_inst = sorted_src_insts[src_cur];
    const opt::Instruction* dst_inst = sorted_dst_insts[dst_cur];

    int compare = ComparePreambleInstructions(src_inst, dst_inst, src_, dst_);
    if (compare == 0) {
      id_map_.MapInsts(src_inst, dst_inst);
    }
    if (compare <= 0) {
      ++src_cur;
    }
    if (compare >= 0) {
      ++dst_cur;
    }
  }
}

InstructionList Differ::SortPreambleInstructions(
    const opt::Module* module,
    opt::IteratorRange<opt::Module::const_inst_iterator> insts) {
  InstructionList sorted;
  for (const opt::Instruction& inst : insts) {
    sorted.push_back(&inst);
  }
  std::sort(
      sorted.begin(), sorted.end(),
      [this, module](const opt::Instruction* a, const opt::Instruction* b) {
        return ComparePreambleInstructions(a, b, module, module) < 0;
      });
  return sorted;
}

int Differ::ComparePreambleInstructions(const opt::Instruction* a,
                                        const opt::Instruction* b,
                                        const opt::Module* src_inst_module,
                                        const opt::Module* dst_inst_module) {
  assert(a->opcode() == b->opcode());
  assert(!a->HasResultId());
  assert(!a->HasResultType());

  const uint32_t a_operand_count = a->NumOperands();
  const uint32_t b_operand_count = b->NumOperands();

  if (a_operand_count < b_operand_count) {
    return -1;
  }
  if (a_operand_count > b_operand_count) {
    return 1;
  }

  // Instead of comparing OpExecutionMode entry point ids as ids, compare them
  // through their corresponding execution model.  This simplifies traversing
  // the sorted list of instructions between src and dst modules.
  if (a->opcode() == spv::Op::OpExecutionMode) {
    const spv::ExecutionModel src_model =
        GetExecutionModel(src_inst_module, a->GetSingleWordOperand(0));
    const spv::ExecutionModel dst_model =
        GetExecutionModel(dst_inst_module, b->GetSingleWordOperand(0));

    if (src_model < dst_model) {
      return -1;
    }
    if (src_model > dst_model) {
      return 1;
    }
  }

  // Match every operand of the instruction.
  for (uint32_t operand_index = 0; operand_index < a_operand_count;
       ++operand_index) {
    const opt::Operand& a_operand = a->GetOperand(operand_index);
    const opt::Operand& b_operand = b->GetOperand(operand_index);

    if (a_operand.type < b_operand.type) {
      return -1;
    }
    if (a_operand.type > b_operand.type) {
      return 1;
    }

    switch (a_operand.type) {
      case SPV_OPERAND_TYPE_ID:
        // Don't compare ids, there can't be multiple instances of the
        // OpExecutionMode with different ids of the same execution model.
        break;
      case SPV_OPERAND_TYPE_TYPE_ID:
      case SPV_OPERAND_TYPE_MEMORY_SEMANTICS_ID:
      case SPV_OPERAND_TYPE_SCOPE_ID:
        assert(false && "Unreachable");
        break;
      case SPV_OPERAND_TYPE_LITERAL_STRING: {
        int str_compare =
            strcmp(a_operand.AsString().c_str(), b_operand.AsString().c_str());
        if (str_compare != 0) {
          return str_compare;
        }
        break;
      }
      default:
        // Expect literal values to match.
        assert(a_operand.words.size() == 1);
        assert(b_operand.words.size() == 1);

        if (a_operand.words[0] < b_operand.words[0]) {
          return -1;
        }
        if (a_operand.words[0] > b_operand.words[0]) {
          return 1;
        }
        break;
    }
  }

  return 0;
}

void Differ::MatchDebugAndAnnotationInstructions(
    opt::IteratorRange<opt::Module::const_inst_iterator> src_insts,
    opt::IteratorRange<opt::Module::const_inst_iterator> dst_insts) {
  for (const opt::Instruction& src_inst : src_insts) {
    for (const opt::Instruction& dst_inst : dst_insts) {
      if (MappedSrcInst(&dst_inst) != nullptr) {
        continue;
      }

      // Map instructions as soon as they match.  Debug and annotation
      // instructions are matched such that there can't be multiple matches.
      if (DoDebugAndAnnotationInstructionsMatch(&src_inst, &dst_inst)) {
        id_map_.MapInsts(&src_inst, &dst_inst);
        break;
      }
    }
  }
}

uint32_t Differ::GroupIdsHelperGetTypeId(const IdInstructions& id_to,
                                         uint32_t id) {
  return GetInst(id_to, id)->type_id();
}

// Return an `OpFunction` instruction's full `OpTypeFunction` type,
// which includes parameter types.
//
// `GroupIdsHelperGetTypeId` applied to an `OpFunction` only gets the
// function's return type, so this is a slightly more precise way to
// match up functions by signature.
uint32_t Differ::GroupIdsHelperGetFunctionTypeId(const IdInstructions& id_to,
                                                 uint32_t id) {
  return GetInst(id_to, id)->GetSingleWordOperand(3);
}

spv::StorageClass Differ::GroupIdsHelperGetTypePointerStorageClass(
    const IdInstructions& id_to, uint32_t id) {
  const opt::Instruction* inst = GetInst(id_to, id);
  assert(inst && inst->opcode() == spv::Op::OpTypePointer);
  return spv::StorageClass(inst->GetSingleWordInOperand(0));
}

spv::Op Differ::GroupIdsHelperGetTypePointerTypeOp(const IdInstructions& id_to,
                                                   uint32_t id) {
  const opt::Instruction* inst = GetInst(id_to, id);
  assert(inst && inst->opcode() == spv::Op::OpTypePointer);

  const uint32_t type_id = inst->GetSingleWordInOperand(1);
  const opt::Instruction* type_inst = GetInst(id_to, type_id);
  assert(type_inst);

  return type_inst->opcode();
}

// Group unmatched ids in `ids` according to some characteristic,
// determined by `get_group`.
//
// Using `get_group` to compute some sort of key for each id, set
// `groups` to map each key to all the ids that have that key.
//
// For example, to group ids by name, pass `Differ::GetName` as
// `get_group`. This will fill `groups` with a map from each name to
// all the ids with that name.
//
// Under the assumption that we're trying to establish new pairings,
// ids that are already paired are omitted from `groups`.
//
// The `is_src` parameter indicates whether `ids` are drawn from the
// source module or the destination module.
//
// The template parameter `T` is the key type, like `std::string` or
// `uint32_t`.
template <typename T>
void Differ::GroupIds(const IdGroup& ids, bool is_src,
                      std::map<T, IdGroup>* groups,
                      T (Differ::*get_group)(const IdInstructions&, uint32_t)) {
  assert(groups->empty());

  const IdInstructions& id_to = is_src ? src_id_to_ : dst_id_to_;

  for (const uint32_t id : ids) {
    // Don't include ids that are already matched, for example through
    // OpEntryPoint.
    const bool is_matched =
        is_src ? id_map_.IsSrcMapped(id) : id_map_.IsDstMapped(id);
    if (is_matched) {
      continue;
    }

    T group = (this->*get_group)(id_to, id);
    (*groups)[group].push_back(id);
  }
}

// Group `src_ids` and `dst_ids` according to `get_group`, and then use
// `match_group` to pair up ids in corresponding groups.
//
// Don't try to pair ids in groups whose key is `invalid_group_key`.
template <typename T>
void Differ::GroupIdsAndMatch(
    const IdGroup& src_ids, const IdGroup& dst_ids, T invalid_group_key,
    T (Differ::*get_group)(const IdInstructions&, uint32_t),
    std::function<void(const IdGroup& src_group, const IdGroup& dst_group)>
        match_group) {
  // Group the ids based on a key (get_group)
  std::map<T, IdGroup> src_groups;
  std::map<T, IdGroup> dst_groups;

  GroupIds<T>(src_ids, true, &src_groups, get_group);
  GroupIds<T>(dst_ids, false, &dst_groups, get_group);

  // Iterate over the groups, and match those with identical keys
  for (const auto& iter : src_groups) {
    const T& key = iter.first;
    const IdGroup& src_group = iter.second;

    if (key == invalid_group_key) {
      continue;
    }

    const IdGroup& dst_group = dst_groups[key];

    // Let the caller match the groups as appropriate.
    match_group(src_group, dst_group);
  }
}

void Differ::GroupIdsAndMatchByMappedId(
    const IdGroup& src_ids, const IdGroup& dst_ids,
    uint32_t (Differ::*get_group)(const IdInstructions&, uint32_t),
    std::function<void(const IdGroup& src_group, const IdGroup& dst_group)>
        match_group) {
  // Group the ids based on a key (get_group)
  std::map<uint32_t, IdGroup> src_groups;
  std::map<uint32_t, IdGroup> dst_groups;

  GroupIds<uint32_t>(src_ids, true, &src_groups, get_group);
  GroupIds<uint32_t>(dst_ids, false, &dst_groups, get_group);

  // Iterate over pairs of groups whose keys map to each other.
  for (const auto& iter : src_groups) {
    const uint32_t& src_key = iter.first;
    const IdGroup& src_group = iter.second;

    if (src_key == 0) {
      continue;
    }

    if (id_map_.IsSrcMapped(src_key)) {
      const uint32_t& dst_key = id_map_.MappedDstId(src_key);
      const IdGroup& dst_group = dst_groups[dst_key];

      // Let the caller match the groups as appropriate.
      match_group(src_group, dst_group);
    }
  }
}

bool Differ::DoIdsMatch(uint32_t src_id, uint32_t dst_id) {
  assert(dst_id != 0);
  return id_map_.MappedDstId(src_id) == dst_id;
}

bool Differ::DoesOperandMatch(const opt::Operand& src_operand,
                              const opt::Operand& dst_operand) {
  assert(src_operand.type == dst_operand.type);

  switch (src_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:
      // Match ids only if they are already matched in the id map.
      return DoIdsMatch(src_operand.AsId(), dst_operand.AsId());
    case SPV_OPERAND_TYPE_LITERAL_STRING:
      return src_operand.AsString() == dst_operand.AsString();
    default:
      // Otherwise expect them to match exactly.
      assert(src_operand.type != SPV_OPERAND_TYPE_LITERAL_STRING);
      if (src_operand.words.size() != dst_operand.words.size()) {
        return false;
      }
      for (size_t i = 0; i < src_operand.words.size(); ++i) {
        if (src_operand.words[i] != dst_operand.words[i]) {
          return false;
        }
      }
      return true;
  }
}

bool Differ::DoOperandsMatch(const opt::Instruction* src_inst,
                             const opt::Instruction* dst_inst,
                             uint32_t in_operand_index_start,
                             uint32_t in_operand_count) {
  // Caller should have returned early for instructions with different opcode.
  assert(src_inst->opcode() == dst_inst->opcode());

  bool match = true;
  for (uint32_t i = 0; i < in_operand_count; ++i) {
    const uint32_t in_operand_index = in_operand_index_start + i;

    const opt::Operand& src_operand = src_inst->GetInOperand(in_operand_index);
    const opt::Operand& dst_operand = dst_inst->GetInOperand(in_operand_index);

    match = match && DoesOperandMatch(src_operand, dst_operand);
  }

  return match;
}

bool Differ::DoInstructionsMatch(const opt::Instruction* src_inst,
                                 const opt::Instruction* dst_inst) {
  // Check whether the two instructions are identical, that is the instructions
  // themselves are matched, every id is matched, and every other value is
  // identical.
  if (MappedDstInst(src_inst) != dst_inst) {
    return false;
  }

  assert(src_inst->opcode() == dst_inst->opcode());
  if (src_inst->NumOperands() != dst_inst->NumOperands()) {
    return false;
  }

  for (uint32_t operand_index = 0; operand_index < src_inst->NumOperands();
       ++operand_index) {
    const opt::Operand& src_operand = src_inst->GetOperand(operand_index);
    const opt::Operand& dst_operand = dst_inst->GetOperand(operand_index);

    if (!DoesOperandMatch(src_operand, dst_operand)) {
      return false;
    }
  }

  return true;
}

bool Differ::DoIdsMatchFuzzy(uint32_t src_id, uint32_t dst_id) {
  assert(dst_id != 0);
  const uint32_t mapped_dst_id = id_map_.MappedDstId(src_id);

  // Consider unmatched ids as a match.  In function bodies, no result id is
  // matched yet and thus they are excluded from instruction matching when used
  // as parameters in subsequent instructions.
  if (mapped_dst_id == 0 || mapped_dst_id == dst_id) {
    return true;
  }

  // Int and Uint constants are interchangeable, match them in that case.
  if (AreIdenticalUintConstants(src_id, dst_id)) {
    return true;
  }

  return false;
}

bool Differ::DoesOperandMatchFuzzy(const opt::Operand& src_operand,
                                   const opt::Operand& dst_operand) {
  if (src_operand.type != dst_operand.type) {
    return false;
  }

  assert(src_operand.type != SPV_OPERAND_TYPE_RESULT_ID);
  assert(dst_operand.type != SPV_OPERAND_TYPE_RESULT_ID);

  switch (src_operand.type) {
    case SPV_OPERAND_TYPE_ID:
    case SPV_OPERAND_TYPE_TYPE_ID:
    case SPV_OPERAND_TYPE_MEMORY_SEMANTICS_ID:
    case SPV_OPERAND_TYPE_SCOPE_ID:
      // Match id operands only if they are already matched in the id map.
      return DoIdsMatchFuzzy(src_operand.AsId(), dst_operand.AsId());
    default:
      // Otherwise allow everything to match.
      return true;
  }
}

bool Differ::DoInstructionsMatchFuzzy(const opt::Instruction* src_inst,
                                      const opt::Instruction* dst_inst) {
  // Similar to DoOperandsMatch, but only checks that ids that have already been
  // matched are identical.  Ids that are unknown are allowed to match, as well
  // as any non-id operand.
  if (src_inst->opcode() != dst_inst->opcode()) {
    return false;
  }
  // For external instructions, make sure the set and opcode of the external
  // instruction matches too.
  if (src_inst->opcode() == spv::Op::OpExtInst) {
    if (!DoOperandsMatch(src_inst, dst_inst, 0, 2)) {
      return false;
    }
  }

  assert(src_inst->HasResultType() == dst_inst->HasResultType());
  if (src_inst->HasResultType() &&
      !DoIdsMatchFuzzy(src_inst->type_id(), dst_inst->type_id())) {
    return false;
  }

  // TODO: allow some instructions to match with different instruction lengths,
  // for example OpImage* with additional operands.
  if (src_inst->NumInOperandWords() != dst_inst->NumInOperandWords()) {
    return false;
  }

  bool match = true;
  for (uint32_t in_operand_index = 0;
       in_operand_index < src_inst->NumInOperandWords(); ++in_operand_index) {
    const opt::Operand& src_operand = src_inst->GetInOperand(in_operand_index);
    const opt::Operand& dst_operand = dst_inst->GetInOperand(in_operand_index);

    match = match && DoesOperandMatchFuzzy(src_operand, dst_operand);
  }

  return match;
}

bool Differ::AreIdenticalUintConstants(uint32_t src_id, uint32_t dst_id) {
  return IsConstantUint(src_id_to_, src_id) &&
         IsConstantUint(dst_id_to_, dst_id) &&
         GetConstantUint(src_id_to_, src_id) ==
             GetConstantUint(dst_id_to_, dst_id);
}

bool Differ::DoDebugAndAnnotationInstructionsMatch(
    const opt::Instruction* src_inst, const opt::Instruction* dst_inst) {
  if (src_inst->opcode() != dst_inst->opcode()) {
    return false;
  }

  switch (src_inst->opcode()) {
    case spv::Op::OpString:
    case spv::Op::OpSourceExtension:
    case spv::Op::OpModuleProcessed:
      return DoesOperandMatch(src_inst->GetOperand(0), dst_inst->GetOperand(0));
    case spv::Op::OpSource:
      return DoOperandsMatch(src_inst, dst_inst, 0, 2);
    case spv::Op::OpSourceContinued:
      return true;
    case spv::Op::OpName:
      return DoOperandsMatch(src_inst, dst_inst, 0, 1);
    case spv::Op::OpMemberName:
      return DoOperandsMatch(src_inst, dst_inst, 0, 2);
    case spv::Op::OpDecorate:
      return DoOperandsMatch(src_inst, dst_inst, 0, 2);
    case spv::Op::OpMemberDecorate:
      return DoOperandsMatch(src_inst, dst_inst, 0, 3);
    case spv::Op::OpExtInst:
    case spv::Op::OpDecorationGroup:
    case spv::Op::OpGroupDecorate:
    case spv::Op::OpGroupMemberDecorate:
      return false;
    default:
      return false;
  }
}

bool Differ::AreVariablesMatchable(uint32_t src_id, uint32_t dst_id,
                                   uint32_t flexibility) {
  // Variables must match by their built-in decorations.
  uint32_t src_built_in_decoration = 0, dst_built_in_decoration = 0;
  const bool src_is_built_in = GetDecorationValue(
      src_id_to_, src_id, spv::Decoration::BuiltIn, &src_built_in_decoration);
  const bool dst_is_built_in = GetDecorationValue(
      dst_id_to_, dst_id, spv::Decoration::BuiltIn, &dst_built_in_decoration);

  if (src_is_built_in != dst_is_built_in) {
    return false;
  }
  if (src_is_built_in && src_built_in_decoration != dst_built_in_decoration) {
    return false;
  }

  // Check their types and storage classes.
  spv::StorageClass src_storage_class, dst_storage_class;
  const uint32_t src_type_id =
      GetVarTypeId(src_id_to_, src_id, &src_storage_class);
  const uint32_t dst_type_id =
      GetVarTypeId(dst_id_to_, dst_id, &dst_storage_class);

  if (!DoIdsMatch(src_type_id, dst_type_id)) {
    return false;
  }
  switch (flexibility) {
    case 0:
      if (src_storage_class != dst_storage_class) {
        return false;
      }
      break;
    case 1:
      if (src_storage_class != dst_storage_class) {
        // Allow one of the two to be Private while the other is Input or
        // Output, this allows matching in/out variables that have been turned
        // global as part of linking two stages (as done in ANGLE).
        const bool src_is_io = src_storage_class == spv::StorageClass::Input ||
                               src_storage_class == spv::StorageClass::Output;
        const bool dst_is_io = dst_storage_class == spv::StorageClass::Input ||
                               dst_storage_class == spv::StorageClass::Output;
        const bool src_is_private =
            src_storage_class == spv::StorageClass::Private;
        const bool dst_is_private =
            dst_storage_class == spv::StorageClass::Private;

        if (!((src_is_io && dst_is_private) || (src_is_private && dst_is_io))) {
          return false;
        }
      }
      break;
    default:
      assert(false && "Unreachable");
      return false;
  }

  // TODO: Is there any other way to check compatiblity of the variables?  It's
  // easy to tell when the variables definitely don't match, but there's little
  // information that can be used for a definite match.
  return true;
}

bool Differ::MatchOpTypeStruct(const opt::Instruction* src_inst,
                               const opt::Instruction* dst_inst,
                               uint32_t flexibility) {
  const uint32_t src_type_id = src_inst->result_id();
  const uint32_t dst_type_id = dst_inst->result_id();

  bool src_has_name = false, dst_has_name = false;
  std::string src_name = GetName(src_id_to_, src_type_id, &src_has_name);
  std::string dst_name = GetName(dst_id_to_, dst_type_id, &dst_has_name);

  // If debug info is present, always match the structs by name.
  if (src_has_name && dst_has_name) {
    if (src_name != dst_name) {
      return false;
    }

    // For gl_PerVertex, find the type pointer of this type (array) and make
    // sure the storage classes of src and dst match; geometry and tessellation
    // shaders have two instances of gl_PerVertex.
    if (src_name == "gl_PerVertex") {
      return MatchPerVertexType(src_type_id, dst_type_id);
    }

    return true;
  }

  // If debug info is not present, match the structs by their type.

  // For gl_PerVertex, find the type pointer of this type (array) and match by
  // storage class. The gl_PerVertex struct is itself found by the BuiltIn
  // decorations applied to its members.
  const bool src_is_per_vertex = IsPerVertexType(src_id_to_, src_type_id);
  const bool dst_is_per_vertex = IsPerVertexType(dst_id_to_, dst_type_id);
  if (src_is_per_vertex != dst_is_per_vertex) {
    return false;
  }

  if (src_is_per_vertex) {
    return MatchPerVertexType(src_type_id, dst_type_id);
  }

  switch (flexibility) {
    case 0:
      if (src_inst->NumInOperandWords() != dst_inst->NumInOperandWords()) {
        return false;
      }
      return DoOperandsMatch(src_inst, dst_inst, 0,
                             src_inst->NumInOperandWords());
    case 1:
      // TODO: match by taking a diff of the fields, and see if there's a >75%
      // match.  Need to then make sure OpMemberName, OpMemberDecorate,
      // OpAccessChain etc are aware of the struct field matching.
      return false;
    default:
      assert(false && "Unreachable");
      return false;
  }
}

bool Differ::MatchOpConstant(const opt::Instruction* src_inst,
                             const opt::Instruction* dst_inst,
                             uint32_t flexibility) {
  // The constants' type must match.  In flexibility == 1, match constants of
  // int and uint, as they are generally interchangeable.
  switch (flexibility) {
    case 0:
      if (!DoesOperandMatch(src_inst->GetOperand(0), dst_inst->GetOperand(0))) {
        return false;
      }
      break;
    case 1:
      if (!IsIntType(src_id_to_, src_inst->type_id()) ||
          !IsIntType(dst_id_to_, dst_inst->type_id())) {
        return false;
      }
      break;
    default:
      assert(false && "Unreachable");
      return false;
  }

  const opt::Operand& src_value_operand = src_inst->GetOperand(2);
  const opt::Operand& dst_value_operand = dst_inst->GetOperand(2);

  const uint64_t src_value = src_value_operand.AsLiteralUint64();
  const uint64_t dst_value = dst_value_operand.AsLiteralUint64();

  // If values are identical, it's a match.
  if (src_value == dst_value) {
    return true;
  }

  // Otherwise, only allow flexibility for float types.
  if (IsFloatType(src_id_to_, src_inst->type_id()) && flexibility == 1) {
    // Tolerance is:
    //
    // - For float: allow 4 bits of mantissa as error
    // - For double: allow 6 bits of mantissa as error
    //
    // TODO: the above values are arbitrary and a placeholder; investigate the
    // amount of error resulting from using `printf("%f", f)` and `printf("%lf",
    // d)` and having glslang parse them.
    const uint64_t tolerance = src_value_operand.words.size() == 1 ? 16 : 64;
    return src_value - dst_value < tolerance ||
           dst_value - src_value < tolerance;
  }

  return false;
}

bool Differ::MatchOpSpecConstant(const opt::Instruction* src_inst,
                                 const opt::Instruction* dst_inst) {
  const uint32_t src_id = src_inst->result_id();
  const uint32_t dst_id = dst_inst->result_id();

  bool src_has_name = false, dst_has_name = false;
  std::string src_name = GetName(src_id_to_, src_id, &src_has_name);
  std::string dst_name = GetName(dst_id_to_, dst_id, &dst_has_name);

  // If debug info is present, always match the spec consts by name.
  if (src_has_name && dst_has_name) {
    return src_name == dst_name;
  }

  // Otherwise, match them by SpecId.
  uint32_t src_spec_id, dst_spec_id;

  if (GetDecorationValue(src_id_to_, src_id, spv::Decoration::SpecId,
                         &src_spec_id) &&
      GetDecorationValue(dst_id_to_, dst_id, spv::Decoration::SpecId,
                         &dst_spec_id)) {
    return src_spec_id == dst_spec_id;
  }

  // There is no SpecId decoration, while not practical, still valid.
  // SpecConstantOp don't have SpecId and can be matched by operands
  if (src_inst->opcode() == spv::Op::OpSpecConstantOp) {
    if (src_inst->NumInOperandWords() == dst_inst->NumInOperandWords()) {
      return DoOperandsMatch(src_inst, dst_inst, 0,
                             src_inst->NumInOperandWords());
    }
  }

  return false;
}

bool Differ::MatchOpVariable(const opt::Instruction* src_inst,
                             const opt::Instruction* dst_inst,
                             uint32_t flexibility) {
  const uint32_t src_id = src_inst->result_id();
  const uint32_t dst_id = dst_inst->result_id();

  const bool src_is_pervertex = IsPerVertexVariable(src_id_to_, src_id);
  const bool dst_is_pervertex = IsPerVertexVariable(dst_id_to_, dst_id);

  // For gl_PerVertex, make sure the input and output instances are matched
  // correctly.
  if (src_is_pervertex != dst_is_pervertex) {
    return false;
  }
  if (src_is_pervertex) {
    return MatchPerVertexVariable(src_inst, dst_inst);
  }

  bool src_has_name = false, dst_has_name = false;
  std::string src_name = GetName(src_id_to_, src_id, &src_has_name);
  std::string dst_name = GetName(dst_id_to_, dst_id, &dst_has_name);

  // If debug info is present, always match the variables by name.
  if (src_has_name && dst_has_name) {
    return src_name == dst_name;
  }

  // If debug info is not present, see if the variables can be matched by their
  // built-in decorations.
  uint32_t src_built_in_decoration;
  const bool src_is_built_in = GetDecorationValue(
      src_id_to_, src_id, spv::Decoration::BuiltIn, &src_built_in_decoration);

  if (src_is_built_in && AreVariablesMatchable(src_id, dst_id, flexibility)) {
    return true;
  }

  spv::StorageClass src_storage_class, dst_storage_class;
  GetVarTypeId(src_id_to_, src_id, &src_storage_class);
  GetVarTypeId(dst_id_to_, dst_id, &dst_storage_class);

  if (src_storage_class != dst_storage_class) {
    return false;
  }

  // If variables are decorated with set/binding, match by the value of those
  // decorations.
  if (!options_.ignore_set_binding) {
    uint32_t src_set = 0, dst_set = 0;
    uint32_t src_binding = 0, dst_binding = 0;

    const bool src_has_set = GetDecorationValue(
        src_id_to_, src_id, spv::Decoration::DescriptorSet, &src_set);
    const bool dst_has_set = GetDecorationValue(
        dst_id_to_, dst_id, spv::Decoration::DescriptorSet, &dst_set);
    const bool src_has_binding = GetDecorationValue(
        src_id_to_, src_id, spv::Decoration::Binding, &src_set);
    const bool dst_has_binding = GetDecorationValue(
        dst_id_to_, dst_id, spv::Decoration::Binding, &dst_set);

    if (src_has_set && dst_has_set && src_has_binding && dst_has_binding) {
      return src_set == dst_set && src_binding == dst_binding;
    }
  }

  // If variables are decorated with location, match by the value of that
  // decoration.
  if (!options_.ignore_location) {
    uint32_t src_location, dst_location;

    const bool src_has_location = GetDecorationValue(
        src_id_to_, src_id, spv::Decoration::Location, &src_location);
    const bool dst_has_location = GetDecorationValue(
        dst_id_to_, dst_id, spv::Decoration::Location, &dst_location);

    if (src_has_location && dst_has_location) {
      return src_location == dst_location;
    }
  }

  // Currently, there's no other way to match variables.
  return false;
}

bool Differ::MatchPerVertexType(uint32_t src_type_id, uint32_t dst_type_id) {
  // For gl_PerVertex, find the type pointer of this type (array) and make sure
  // the storage classes of src and dst match; geometry and tessellation shaders
  // have two instances of gl_PerVertex.
  spv::StorageClass src_storage_class =
      GetPerVertexStorageClass(src_, src_type_id);
  spv::StorageClass dst_storage_class =
      GetPerVertexStorageClass(dst_, dst_type_id);

  assert(src_storage_class == spv::StorageClass::Input ||
         src_storage_class == spv::StorageClass::Output);
  assert(dst_storage_class == spv::StorageClass::Input ||
         dst_storage_class == spv::StorageClass::Output);

  return src_storage_class == dst_storage_class;
}

bool Differ::MatchPerVertexVariable(const opt::Instruction* src_inst,
                                    const opt::Instruction* dst_inst) {
  spv::StorageClass src_storage_class =
      spv::StorageClass(src_inst->GetSingleWordInOperand(0));
  spv::StorageClass dst_storage_class =
      spv::StorageClass(dst_inst->GetSingleWordInOperand(0));

  return src_storage_class == dst_storage_class;
}

void Differ::MatchTypeForwardPointersByName(const IdGroup& src,
                                            const IdGroup& dst) {
  // Given two sets of compatible groups of OpTypeForwardPointer instructions,
  // attempts to match them by name.

  // Group them by debug info and loop over them.
  GroupIdsAndMatch<std::string>(
      src, dst, "", &Differ::GetSanitizedName,
      [this](const IdGroup& src_group, const IdGroup& dst_group) {
        // Match only if there's a unique forward declaration with this debug
        // name.
        if (src_group.size() == 1 && dst_group.size() == 1) {
          id_map_.MapIds(src_group[0], dst_group[0]);
        }
      });
}

void Differ::MatchTypeForwardPointersByTypeOp(const IdGroup& src,
                                              const IdGroup& dst) {
  // Given two sets of compatible groups of OpTypeForwardPointer instructions,
  // attempts to match them by type op.  Must be called after
  // MatchTypeForwardPointersByName to match as many as possible by debug info.

  // Remove ids that are matched with debug info in
  // MatchTypeForwardPointersByName.
  IdGroup src_unmatched_ids;
  IdGroup dst_unmatched_ids;

  std::copy_if(src.begin(), src.end(), std::back_inserter(src_unmatched_ids),
               [this](uint32_t id) { return !id_map_.IsSrcMapped(id); });
  std::copy_if(dst.begin(), dst.end(), std::back_inserter(dst_unmatched_ids),
               [this](uint32_t id) { return !id_map_.IsDstMapped(id); });

  // Match only if there's a unique forward declaration with this
  // storage class and type opcode.  If both have debug info, they
  // must not have been matchable.
  if (src_unmatched_ids.size() == 1 && dst_unmatched_ids.size() == 1) {
    uint32_t src_id = src_unmatched_ids[0];
    uint32_t dst_id = dst_unmatched_ids[0];
    if (!HasName(src_id_to_, src_id) || !HasName(dst_id_to_, dst_id)) {
      id_map_.MapIds(src_id, dst_id);
    }
  }
}

InstructionList Differ::GetFunctionBody(opt::IRContext* context,
                                        opt::Function& function) {
  // Canonicalize the blocks of the function to produce better diff, for example
  // to not produce any diff if the src and dst have the same switch/case blocks
  // but with the cases simply reordered.
  std::list<opt::BasicBlock*> order;
  context->cfg()->ComputeStructuredOrder(&function, &*function.begin(), &order);

  // Go over the instructions of the function and add the instructions to a flat
  // list to simplify future iterations.
  InstructionList body;
  for (opt::BasicBlock* block : order) {
    block->ForEachInst(
        [&body](const opt::Instruction* inst) { body.push_back(inst); }, true);
  }
  body.push_back(function.EndInst());

  return body;
}

InstructionList Differ::GetFunctionHeader(const opt::Function& function) {
  // Go over the instructions of the function and add the header instructions to
  // a flat list to simplify diff generation.
  InstructionList body;
  function.WhileEachInst(
      [&body](const opt::Instruction* inst) {
        if (inst->opcode() == spv::Op::OpLabel) {
          return false;
        }
        body.push_back(inst);
        return true;
      },
      true, true);

  return body;
}

void Differ::GetFunctionBodies(opt::IRContext* context, FunctionMap* functions,
                               FunctionInstMap* function_insts) {
  for (opt::Function& function : *context->module()) {
    uint32_t id = function.result_id();
    assert(functions->find(id) == functions->end());
    assert(function_insts->find(id) == function_insts->end());

    (*functions)[id] = &function;

    InstructionList body = GetFunctionBody(context, function);
    (*function_insts)[id] = std::move(body);
  }
}

void Differ::GetFunctionHeaderInstructions(const opt::Module* module,
                                           FunctionInstMap* function_insts) {
  for (opt::Function& function : *module) {
    InstructionList body = GetFunctionHeader(function);
    (*function_insts)[function.result_id()] = std::move(body);
  }
}

void Differ::BestEffortMatchFunctions(const IdGroup& src_func_ids,
                                      const IdGroup& dst_func_ids,
                                      const FunctionInstMap& src_func_insts,
                                      const FunctionInstMap& dst_func_insts) {
  struct MatchResult {
    uint32_t src_id;
    uint32_t dst_id;
    DiffMatch src_match;
    DiffMatch dst_match;
    float match_rate;
    bool operator<(const MatchResult& other) const {
      return match_rate > other.match_rate;
    }
  };
  std::vector<MatchResult> all_match_results;

  for (const uint32_t src_func_id : src_func_ids) {
    if (id_map_.IsSrcMapped(src_func_id)) {
      continue;
    }
    const std::string src_name = GetSanitizedName(src_id_to_, src_func_id);

    for (const uint32_t dst_func_id : dst_func_ids) {
      if (id_map_.IsDstMapped(dst_func_id)) {
        continue;
      }

      // Don't match functions that are named, but the names are different.
      const std::string dst_name = GetSanitizedName(dst_id_to_, dst_func_id);
      if (src_name != "" && dst_name != "" && src_name != dst_name) {
        continue;
      }

      DiffMatch src_match_result, dst_match_result;
      float match_rate = MatchFunctionBodies(
          src_func_insts.at(src_func_id), dst_func_insts.at(dst_func_id),
          &src_match_result, &dst_match_result);

      // Only consider the functions a match if there's at least 60% match.
      // This is an arbitrary limit that should be tuned.
      constexpr float pass_match_rate = 0.6f;
      if (match_rate >= pass_match_rate) {
        all_match_results.emplace_back(
            MatchResult{src_func_id, dst_func_id, std::move(src_match_result),
                        std::move(dst_match_result), match_rate});
      }
    }
  }

  std::sort(all_match_results.begin(), all_match_results.end());

  for (const MatchResult& match_result : all_match_results) {
    if (id_map_.IsSrcMapped(match_result.src_id) ||
        id_map_.IsDstMapped(match_result.dst_id)) {
      continue;
    }

    id_map_.MapIds(match_result.src_id, match_result.dst_id);

    MatchFunctionParamIds(src_funcs_[match_result.src_id],
                          dst_funcs_[match_result.dst_id]);
    MatchIdsInFunctionBodies(src_func_insts.at(match_result.src_id),
                             dst_func_insts.at(match_result.dst_id),
                             match_result.src_match, match_result.dst_match, 0);
  }
}

void Differ::MatchFunctionParamIds(const opt::Function* src_func,
                                   const opt::Function* dst_func) {
  IdGroup src_params;
  IdGroup dst_params;
  src_func->ForEachParam(
      [&src_params](const opt::Instruction* param) {
        src_params.push_back(param->result_id());
      },
      false);
  dst_func->ForEachParam(
      [&dst_params](const opt::Instruction* param) {
        dst_params.push_back(param->result_id());
      },
      false);

  GroupIdsAndMatch<std::string>(
      src_params, dst_params, "", &Differ::GetSanitizedName,
      [this](const IdGroup& src_group, const IdGroup& dst_group) {
        // There shouldn't be two parameters with the same name, so the ids
        // should match. There is nothing restricting the SPIR-V however to have
        // two parameters with the same name, so be resilient against that.
        if (src_group.size() == 1 && dst_group.size() == 1) {
          id_map_.MapIds(src_group[0], dst_group[0]);
        }
      });

  // Then match the parameters by their type.  If there are multiple of them,
  // match them by their order.
  GroupIdsAndMatchByMappedId(
      src_params, dst_params, &Differ::GroupIdsHelperGetTypeId,
      [this](const IdGroup& src_group_by_type_id,
             const IdGroup& dst_group_by_type_id) {
        const size_t shared_param_count =
            std::min(src_group_by_type_id.size(), dst_group_by_type_id.size());

        for (size_t param_index = 0; param_index < shared_param_count;
             ++param_index) {
          id_map_.MapIds(src_group_by_type_id[param_index],
                         dst_group_by_type_id[param_index]);
        }
      });
}

float Differ::MatchFunctionBodies(const InstructionList& src_body,
                                  const InstructionList& dst_body,
                                  DiffMatch* src_match_result,
                                  DiffMatch* dst_match_result) {
  LongestCommonSubsequence<std::vector<const opt::Instruction*>> lcs(src_body,
                                                                     dst_body);

  uint32_t best_match_length = lcs.Get<const opt::Instruction*>(
      [this](const opt::Instruction* src_inst,
             const opt::Instruction* dst_inst) {
        return DoInstructionsMatchFuzzy(src_inst, dst_inst);
      },
      src_match_result, dst_match_result);

  // TODO: take the gaps in between matches and match those again with a relaxed
  // instruction-and-type-only comparison.  This can produce a better diff for
  // example if an array index is changed, causing the OpAccessChain id to not
  // match and subsequently every operation that's derived from that id.
  // Usually this mismatch cascades until the next OpStore which doesn't produce
  // an id.

  return static_cast<float>(best_match_length) * 2.0f /
         static_cast<float>(src_body.size() + dst_body.size());
}

void Differ::MatchIdsInFunctionBodies(const InstructionList& src_body,
                                      const InstructionList& dst_body,
                                      const DiffMatch& src_match_result,
                                      const DiffMatch& dst_match_result,
                                      uint32_t flexibility) {
  size_t src_cur = 0;
  size_t dst_cur = 0;

  while (src_cur < src_body.size() && dst_cur < dst_body.size()) {
    if (src_match_result[src_cur] && dst_match_result[dst_cur]) {
      // Match instructions the src and dst instructions.
      //
      // TODO: count the matchings between variables discovered this way and
      // choose the "best match" after all functions have been diffed and all
      // instructions analyzed.
      const opt::Instruction* src_inst = src_body[src_cur++];
      const opt::Instruction* dst_inst = dst_body[dst_cur++];

      // Record the matching between the instructions.  This is done only once
      // (hence flexibility == 0).  Calls with non-zero flexibility values will
      // only deal with matching other ids based on the operands.
      if (flexibility == 0) {
        id_map_.MapInsts(src_inst, dst_inst);
      }

      // Match any unmatched variables referenced by the instructions.
      MatchVariablesUsedByMatchedInstructions(src_inst, dst_inst, flexibility);
      continue;
    }
    if (!src_match_result[src_cur]) {
      ++src_cur;
    }
    if (!dst_match_result[dst_cur]) {
      ++dst_cur;
    }
  }
}

void Differ::MatchVariablesUsedByMatchedInstructions(
    const opt::Instruction* src_inst, const opt::Instruction* dst_inst,
    uint32_t flexibility) {
  // For OpAccessChain, OpLoad and OpStore instructions that reference unmatched
  // variables, match them as a best effort.
  assert(src_inst->opcode() == dst_inst->opcode());
  switch (src_inst->opcode()) {
    default:
      // TODO: match functions based on OpFunctionCall?
      break;
    case spv::Op::OpAccessChain:
    case spv::Op::OpInBoundsAccessChain:
    case spv::Op::OpPtrAccessChain:
    case spv::Op::OpInBoundsPtrAccessChain:
    case spv::Op::OpLoad:
    case spv::Op::OpStore:
      const uint32_t src_pointer_id = src_inst->GetSingleWordInOperand(0);
      const uint32_t dst_pointer_id = dst_inst->GetSingleWordInOperand(0);
      if (IsVariable(src_id_to_, src_pointer_id) &&
          IsVariable(dst_id_to_, dst_pointer_id) &&
          !id_map_.IsSrcMapped(src_pointer_id) &&
          !id_map_.IsDstMapped(dst_pointer_id) &&
          AreVariablesMatchable(src_pointer_id, dst_pointer_id, flexibility)) {
        id_map_.MapIds(src_pointer_id, dst_pointer_id);
      }
      break;
  }
}

const opt::Instruction* Differ::GetInst(const IdInstructions& id_to,
                                        uint32_t id) {
  assert(id != 0);
  assert(id < id_to.inst_map_.size());

  const opt::Instruction* inst = id_to.inst_map_[id];
  assert(inst != nullptr);

  return inst;
}

uint32_t Differ::GetConstantUint(const IdInstructions& id_to,
                                 uint32_t constant_id) {
  const opt::Instruction* constant_inst = GetInst(id_to, constant_id);
  assert(constant_inst->opcode() == spv::Op::OpConstant);
  assert(GetInst(id_to, constant_inst->type_id())->opcode() ==
         spv::Op::OpTypeInt);

  return constant_inst->GetSingleWordInOperand(0);
}

spv::ExecutionModel Differ::GetExecutionModel(const opt::Module* module,
                                              uint32_t entry_point_id) {
  for (const opt::Instruction& inst : module->entry_points()) {
    assert(inst.opcode() == spv::Op::OpEntryPoint);
    if (inst.GetSingleWordOperand(1) == entry_point_id) {
      return spv::ExecutionModel(inst.GetSingleWordOperand(0));
    }
  }

  assert(false && "Unreachable");
  return spv::ExecutionModel(0xFFF);
}

bool Differ::HasName(const IdInstructions& id_to, uint32_t id) {
  assert(id != 0);
  assert(id < id_to.name_map_.size());

  for (const opt::Instruction* inst : id_to.name_map_[id]) {
    if (inst->opcode() == spv::Op::OpName) {
      return true;
    }
  }

  return false;
}

std::string Differ::GetName(const IdInstructions& id_to, uint32_t id,
                            bool* has_name) {
  assert(id != 0);
  assert(id < id_to.name_map_.size());

  for (const opt::Instruction* inst : id_to.name_map_[id]) {
    if (inst->opcode() == spv::Op::OpName) {
      *has_name = true;
      return inst->GetOperand(1).AsString();
    }
  }

  *has_name = false;
  return "";
}

std::string Differ::GetSanitizedName(const IdInstructions& id_to, uint32_t id) {
  bool has_name = false;
  std::string name = GetName(id_to, id, &has_name);

  if (!has_name) {
    return "";
  }

  // Remove args from the name, in case this is a function name
  return name.substr(0, name.find('('));
}

uint32_t Differ::GetVarTypeId(const IdInstructions& id_to, uint32_t var_id,
                              spv::StorageClass* storage_class) {
  const opt::Instruction* var_inst = GetInst(id_to, var_id);
  assert(var_inst->opcode() == spv::Op::OpVariable);

  *storage_class = spv::StorageClass(var_inst->GetSingleWordInOperand(0));

  // Get the type pointer from the variable.
  const uint32_t type_pointer_id = var_inst->type_id();
  const opt::Instruction* type_pointer_inst = GetInst(id_to, type_pointer_id);

  // Get the type from the type pointer.
  return type_pointer_inst->GetSingleWordInOperand(1);
}

bool Differ::GetDecorationValue(const IdInstructions& id_to, uint32_t id,
                                spv::Decoration decoration,
                                uint32_t* decoration_value) {
  assert(id != 0);
  assert(id < id_to.decoration_map_.size());

  for (const opt::Instruction* inst : id_to.decoration_map_[id]) {
    if (inst->opcode() == spv::Op::OpDecorate &&
        inst->GetSingleWordOperand(0) == id &&
        spv::Decoration(inst->GetSingleWordOperand(1)) == decoration) {
      *decoration_value = inst->GetSingleWordOperand(2);
      return true;
    }
  }

  return false;
}

const opt::Instruction* Differ::GetForwardPointerInst(
    const IdInstructions& id_to, uint32_t id) {
  assert(id != 0);
  assert(id < id_to.forward_pointer_map_.size());
  return id_to.forward_pointer_map_[id];
}

bool Differ::IsIntType(const IdInstructions& id_to, uint32_t type_id) {
  return IsOp(id_to, type_id, spv::Op::OpTypeInt);
}

bool Differ::IsFloatType(const IdInstructions& id_to, uint32_t type_id) {
  return IsOp(id_to, type_id, spv::Op::OpTypeFloat);
}

bool Differ::IsConstantUint(const IdInstructions& id_to, uint32_t id) {
  const opt::Instruction* constant_inst = GetInst(id_to, id);
  if (constant_inst->opcode() != spv::Op::OpConstant) {
    return false;
  }

  const opt::Instruction* type_inst = GetInst(id_to, constant_inst->type_id());
  return type_inst->opcode() == spv::Op::OpTypeInt;
}

bool Differ::IsVariable(const IdInstructions& id_to, uint32_t pointer_id) {
  return IsOp(id_to, pointer_id, spv::Op::OpVariable);
}

bool Differ::IsOp(const IdInstructions& id_to, uint32_t id, spv::Op op) {
  return GetInst(id_to, id)->opcode() == op;
}

bool Differ::IsPerVertexType(const IdInstructions& id_to, uint32_t type_id) {
  assert(type_id != 0);
  assert(type_id < id_to.decoration_map_.size());

  for (const opt::Instruction* inst : id_to.decoration_map_[type_id]) {
    if (inst->opcode() == spv::Op::OpMemberDecorate &&
        inst->GetSingleWordOperand(0) == type_id &&
        spv::Decoration(inst->GetSingleWordOperand(2)) ==
            spv::Decoration::BuiltIn) {
      spv::BuiltIn built_in = spv::BuiltIn(inst->GetSingleWordOperand(3));

      // Only gl_PerVertex can have, and it can only have, the following
      // built-in decorations.
      return built_in == spv::BuiltIn::Position ||
             built_in == spv::BuiltIn::PointSize ||
             built_in == spv::BuiltIn::ClipDistance ||
             built_in == spv::BuiltIn::CullDistance;
    }
  }

  return false;
}

bool Differ::IsPerVertexVariable(const IdInstructions& id_to, uint32_t var_id) {
  // Get the type from the type pointer.
  spv::StorageClass storage_class;
  uint32_t type_id = GetVarTypeId(id_to, var_id, &storage_class);
  const opt::Instruction* type_inst = GetInst(id_to, type_id);

  // If array, get the element type.
  if (type_inst->opcode() == spv::Op::OpTypeArray) {
    type_id = type_inst->GetSingleWordInOperand(0);
  }

  // Now check if the type is gl_PerVertex.
  return IsPerVertexType(id_to, type_id);
}

spv::StorageClass Differ::GetPerVertexStorageClass(const opt::Module* module,
                                                   uint32_t type_id) {
  for (const opt::Instruction& inst : module->types_values()) {
    switch (inst.opcode()) {
      case spv::Op::OpTypeArray:
        // The gl_PerVertex instance could be an array, look for a variable of
        // the array type instead.
        if (inst.GetSingleWordInOperand(0) == type_id) {
          type_id = inst.result_id();
        }
        break;
      case spv::Op::OpTypePointer:
        // Find the storage class of the pointer to this type.
        if (inst.GetSingleWordInOperand(1) == type_id) {
          return spv::StorageClass(inst.GetSingleWordInOperand(0));
        }
        break;
      default:
        break;
    }
  }

  // gl_PerVertex is declared, but is unused.  Return either of Input or Output
  // classes just so it matches one in the other module.  This should be highly
  // unlikely, perhaps except for ancient GS-used-to-emulate-CS scenarios.
  return spv::StorageClass::Output;
}

spv_ext_inst_type_t Differ::GetExtInstType(const IdInstructions& id_to,
                                           uint32_t set_id) {
  const opt::Instruction* set_inst = GetInst(id_to, set_id);
  return spvExtInstImportTypeGet(set_inst->GetInOperand(0).AsString().c_str());
}

spv_number_kind_t Differ::GetNumberKind(const IdInstructions& id_to,
                                        const opt::Instruction& inst,
                                        uint32_t operand_index,
                                        uint32_t* number_bit_width) {
  const opt::Operand& operand = inst.GetOperand(operand_index);
  *number_bit_width = 0;

  // A very limited version of Parser::parseOperand.
  switch (operand.type) {
    case SPV_OPERAND_TYPE_LITERAL_INTEGER:
    case SPV_OPERAND_TYPE_OPTIONAL_LITERAL_INTEGER:
      // Always unsigned integers.
      *number_bit_width = 32;
      return SPV_NUMBER_UNSIGNED_INT;
    case SPV_OPERAND_TYPE_LITERAL_FLOAT:
      // Always float.
      *number_bit_width = 32;
      return SPV_NUMBER_FLOATING;
    case SPV_OPERAND_TYPE_TYPED_LITERAL_NUMBER:
    case SPV_OPERAND_TYPE_OPTIONAL_TYPED_LITERAL_INTEGER:
      switch (inst.opcode()) {
        case spv::Op::OpSwitch:
        case spv::Op::OpConstant:
        case spv::Op::OpSpecConstant:
          // Same kind of number as the selector (OpSwitch) or the type
          // (Op*Constant).
          return GetTypeNumberKind(id_to, inst.GetSingleWordOperand(0),
                                   number_bit_width);
        default:
          assert(false && "Unreachable");
          break;
      }
      break;
    default:
      break;
  }

  return SPV_NUMBER_NONE;
}

spv_number_kind_t Differ::GetTypeNumberKind(const IdInstructions& id_to,
                                            uint32_t id,
                                            uint32_t* number_bit_width) {
  const opt::Instruction* type_inst = GetInst(id_to, id);
  if (!spvOpcodeIsScalarType(type_inst->opcode())) {
    type_inst = GetInst(id_to, type_inst->type_id());
  }

  switch (type_inst->opcode()) {
    case spv::Op::OpTypeInt:
      *number_bit_width = type_inst->GetSingleWordOperand(1);
      return type_inst->GetSingleWordOperand(2) == 0 ? SPV_NUMBER_UNSIGNED_INT
                                                     : SPV_NUMBER_SIGNED_INT;
      break;
    case spv::Op::OpTypeFloat:
      *number_bit_width = type_inst->GetSingleWordOperand(1);
      return SPV_NUMBER_FLOATING;
    default:
      assert(false && "Unreachable");
      return SPV_NUMBER_NONE;
  }
}

void Differ::MatchCapabilities() {
  MatchPreambleInstructions(src_->capabilities(), dst_->capabilities());
}

void Differ::MatchExtensions() {
  MatchPreambleInstructions(src_->extensions(), dst_->extensions());
}

void Differ::MatchExtInstImportIds() {
  // Bunch all of this section's ids as potential matches.
  PotentialIdMap potential_id_map;
  auto get_result_id = [](const opt::Instruction& inst) {
    return inst.result_id();
  };
  auto accept_all = [](const opt::Instruction&) { return true; };

  PoolPotentialIds(src_->ext_inst_imports(), potential_id_map.src_ids, true,
                   accept_all, get_result_id);
  PoolPotentialIds(dst_->ext_inst_imports(), potential_id_map.dst_ids, false,
                   accept_all, get_result_id);

  // Then match the ids.
  MatchIds(potential_id_map, [](const opt::Instruction* src_inst,
                                const opt::Instruction* dst_inst) {
    // Match OpExtInstImport by exact name, which is operand 1
    const opt::Operand& src_name = src_inst->GetOperand(1);
    const opt::Operand& dst_name = dst_inst->GetOperand(1);

    return src_name.AsString() == dst_name.AsString();
  });
}
void Differ::MatchMemoryModel() {
  // Always match the memory model instructions, there is always a single one of
  // it.
  id_map_.MapInsts(src_->GetMemoryModel(), dst_->GetMemoryModel());
}

void Differ::MatchEntryPointIds() {
  // Match OpEntryPoint ids (at index 1) by ExecutionModel (at index 0) and
  // possibly name (at index 2).  OpEntryPoint doesn't produce a result id, so
  // this function doesn't use the helpers the other functions use.

  // Map from execution model to OpEntryPoint instructions of that model.
  using ExecutionModelMap =
      std::unordered_map<uint32_t, std::vector<const opt::Instruction*>>;
  ExecutionModelMap src_entry_points_map;
  ExecutionModelMap dst_entry_points_map;
  std::set<uint32_t> all_execution_models;

  for (const opt::Instruction& src_inst : src_->entry_points()) {
    uint32_t execution_model = src_inst.GetSingleWordOperand(0);
    src_entry_points_map[execution_model].push_back(&src_inst);
    all_execution_models.insert(execution_model);
  }
  for (const opt::Instruction& dst_inst : dst_->entry_points()) {
    uint32_t execution_model = dst_inst.GetSingleWordOperand(0);
    dst_entry_points_map[execution_model].push_back(&dst_inst);
    all_execution_models.insert(execution_model);
  }

  // Go through each model and match the ids.
  for (const uint32_t execution_model : all_execution_models) {
    auto& src_insts = src_entry_points_map[execution_model];
    auto& dst_insts = dst_entry_points_map[execution_model];

    // If there is only one entry point in src and dst with that model, match
    // them unconditionally.
    if (src_insts.size() == 1 && dst_insts.size() == 1) {
      uint32_t src_id = src_insts[0]->GetSingleWordOperand(1);
      uint32_t dst_id = dst_insts[0]->GetSingleWordOperand(1);
      id_map_.MapIds(src_id, dst_id);
      id_map_.MapInsts(src_insts[0], dst_insts[0]);
      continue;
    }

    // Otherwise match them by name.
    for (const opt::Instruction* src_inst : src_insts) {
      for (const opt::Instruction* dst_inst : dst_insts) {
        if (id_map_.IsDstMapped(dst_inst)) continue;

        const opt::Operand& src_name = src_inst->GetOperand(2);
        const opt::Operand& dst_name = dst_inst->GetOperand(2);

        if (src_name.AsString() == dst_name.AsString()) {
          uint32_t src_id = src_inst->GetSingleWordOperand(1);
          uint32_t dst_id = dst_inst->GetSingleWordOperand(1);
          id_map_.MapIds(src_id, dst_id);
          id_map_.MapInsts(src_inst, dst_inst);
          break;
        }
      }
    }
  }
}

void Differ::MatchExecutionModes() {
  MatchPreambleInstructions(src_->execution_modes(), dst_->execution_modes());
}

void Differ::MatchTypeForwardPointers() {
  // Bunch all of type forward pointers as potential matches.
  PotentialIdMap potential_id_map;
  auto get_pointer_type_id = [](const opt::Instruction& inst) {
    return inst.GetSingleWordOperand(0);
  };
  auto accept_type_forward_pointer_ops = [](const opt::Instruction& inst) {
    return inst.opcode() == spv::Op::OpTypeForwardPointer;
  };

  PoolPotentialIds(src_->types_values(), potential_id_map.src_ids, true,
                   accept_type_forward_pointer_ops, get_pointer_type_id);
  PoolPotentialIds(dst_->types_values(), potential_id_map.dst_ids, false,
                   accept_type_forward_pointer_ops, get_pointer_type_id);

  // Matching types with cyclical references (i.e. in the style of linked lists)
  // can get very complex.  Currently, the diff tool matches types bottom up, so
  // on every instruction it expects to know if its operands are already matched
  // or not.  With cyclical references, it cannot know that.  Type matching may
  // need significant modifications to be able to support this use case.
  //
  // Currently, forwarded types are only matched by storage class and debug
  // info, with minimal matching of the type being forwarded:
  //
  // - Group by class
  //   - Group by OpType being pointed to
  //     - Group by debug info
  //       - If same name and unique, match
  //     - If leftover is unique, match

  // Group forwarded pointers by storage class first and loop over them.
  GroupIdsAndMatch<spv::StorageClass>(
      potential_id_map.src_ids, potential_id_map.dst_ids,
      spv::StorageClass::Max, &Differ::GroupIdsHelperGetTypePointerStorageClass,
      [this](const IdGroup& src_group_by_storage_class,
             const IdGroup& dst_group_by_storage_class) {
        // Group them further by the type they are pointing to and loop over
        // them.
        GroupIdsAndMatch<spv::Op>(
            src_group_by_storage_class, dst_group_by_storage_class,
            spv::Op::Max, &Differ::GroupIdsHelperGetTypePointerTypeOp,
            [this](const IdGroup& src_group_by_type_op,
                   const IdGroup& dst_group_by_type_op) {
              // Group them even further by debug info, if possible and match by
              // debug name.
              MatchTypeForwardPointersByName(src_group_by_type_op,
                                             dst_group_by_type_op);

              // Match the leftovers only if they lack debug info and there is
              // only one instance of them.
              MatchTypeForwardPointersByTypeOp(src_group_by_type_op,
                                               dst_group_by_type_op);
            });
      });

  // Match the instructions that forward declare the same type themselves
  for (uint32_t src_id : potential_id_map.src_ids) {
    uint32_t dst_id = id_map_.MappedDstId(src_id);
    if (dst_id == 0) continue;

    const opt::Instruction* src_forward_inst =
        GetForwardPointerInst(src_id_to_, src_id);
    const opt::Instruction* dst_forward_inst =
        GetForwardPointerInst(dst_id_to_, dst_id);

    assert(src_forward_inst);
    assert(dst_forward_inst);

    id_map_.MapInsts(src_forward_inst, dst_forward_inst);
  }
}

void Differ::MatchTypeIds() {
  // Bunch all of type ids as potential matches.
  PotentialIdMap potential_id_map;
  auto get_result_id = [](const opt::Instruction& inst) {
    return inst.result_id();
  };
  auto accept_type_ops = [](const opt::Instruction& inst) {
    return spvOpcodeGeneratesType(inst.opcode());
  };

  PoolPotentialIds(src_->types_values(), potential_id_map.src_ids, true,
                   accept_type_ops, get_result_id);
  PoolPotentialIds(dst_->types_values(), potential_id_map.dst_ids, false,
                   accept_type_ops, get_result_id);

  // Then match the ids.  Start with exact matches, then match the leftover with
  // gradually loosening degrees of strictness.  For example, in the absence of
  // debug info, two block types will be matched if they differ only in a few of
  // the fields.
  for (uint32_t flexibility = 0; flexibility < 2; ++flexibility) {
    MatchIds(potential_id_map, [this, flexibility](
                                   const opt::Instruction* src_inst,
                                   const opt::Instruction* dst_inst) {
      const spv::Op src_op = src_inst->opcode();
      const spv::Op dst_op = dst_inst->opcode();

      // Don't match if the opcode is not the same.
      if (src_op != dst_op) {
        return false;
      }

      switch (src_op) {
        case spv::Op::OpTypeVoid:
        case spv::Op::OpTypeBool:
        case spv::Op::OpTypeSampler:
        case spv::Op::OpTypeAccelerationStructureNV:
        case spv::Op::OpTypeRayQueryKHR:
          // the above types have no operands and are unique, match them.
          return true;
        case spv::Op::OpTypeInt:
        case spv::Op::OpTypeFloat:
        case spv::Op::OpTypeVector:
        case spv::Op::OpTypeMatrix:
        case spv::Op::OpTypeSampledImage:
        case spv::Op::OpTypeRuntimeArray:
        case spv::Op::OpTypePointer:
          // Match these instructions when all operands match.
          assert(src_inst->NumInOperandWords() ==
                 dst_inst->NumInOperandWords());
          return DoOperandsMatch(src_inst, dst_inst, 0,
                                 src_inst->NumInOperandWords());

        case spv::Op::OpTypeFunction:
        case spv::Op::OpTypeImage:
          // Match function types only if they have the same number of operands,
          // and they all match.
          // Match image types similarly, expecting the optional final parameter
          // to match (if provided in both)
          if (src_inst->NumInOperandWords() != dst_inst->NumInOperandWords()) {
            return false;
          }
          return DoOperandsMatch(src_inst, dst_inst, 0,
                                 src_inst->NumInOperandWords());

        case spv::Op::OpTypeArray:
          // Match arrays only if the element type and length match.  The length
          // is an id of a constant, so the actual constant it's defining is
          // compared instead.
          if (!DoOperandsMatch(src_inst, dst_inst, 0, 1)) {
            return false;
          }

          if (AreIdenticalUintConstants(src_inst->GetSingleWordInOperand(1),
                                        dst_inst->GetSingleWordInOperand(1))) {
            return true;
          }

          // If size is not OpConstant, expect the ids to match exactly (for
          // example if a spec contant is used).
          return DoOperandsMatch(src_inst, dst_inst, 1, 1);

        case spv::Op::OpTypeStruct:
          return MatchOpTypeStruct(src_inst, dst_inst, flexibility);

        default:
          return false;
      }
    });
  }
}

void Differ::MatchConstants() {
  // Bunch all of constant ids as potential matches.
  PotentialIdMap potential_id_map;
  auto get_result_id = [](const opt::Instruction& inst) {
    return inst.result_id();
  };
  auto accept_type_ops = [](const opt::Instruction& inst) {
    return spvOpcodeIsConstant(inst.opcode());
  };

  PoolPotentialIds(src_->types_values(), potential_id_map.src_ids, true,
                   accept_type_ops, get_result_id);
  PoolPotentialIds(dst_->types_values(), potential_id_map.dst_ids, false,
                   accept_type_ops, get_result_id);

  // Then match the ids.  Constants are matched exactly, except for float types
  // that are first matched exactly, then leftovers are matched with a small
  // error.
  for (uint32_t flexibility = 0; flexibility < 2; ++flexibility) {
    MatchIds(potential_id_map, [this, flexibility](
                                   const opt::Instruction* src_inst,
                                   const opt::Instruction* dst_inst) {
      const spv::Op src_op = src_inst->opcode();
      const spv::Op dst_op = dst_inst->opcode();

      // Don't match if the opcode is not the same.
      if (src_op != dst_op) {
        return false;
      }

      switch (src_op) {
        case spv::Op::OpConstantTrue:
        case spv::Op::OpConstantFalse:
          // true and false are unique, match them.
          return true;
        case spv::Op::OpConstant:
          return MatchOpConstant(src_inst, dst_inst, flexibility);
        case spv::Op::OpConstantComposite:
        case spv::Op::OpSpecConstantComposite:
          // Composite constants must match in type and value.
          //
          // TODO: match OpConstantNull with OpConstantComposite with all zeros
          // at flexibility == 1
          // TODO: match constants from structs that have been flexibly-matched.
          if (src_inst->NumInOperandWords() != dst_inst->NumInOperandWords()) {
            return false;
          }
          return DoesOperandMatch(src_inst->GetOperand(0),
                                  dst_inst->GetOperand(0)) &&
                 DoOperandsMatch(src_inst, dst_inst, 0,
                                 src_inst->NumInOperandWords());
        case spv::Op::OpConstantSampler:
          // Match sampler constants exactly.
          // TODO: Allow flexibility in parameters to better diff shaders where
          // the sampler param has changed.
          assert(src_inst->NumInOperandWords() ==
                 dst_inst->NumInOperandWords());
          return DoOperandsMatch(src_inst, dst_inst, 0,
                                 src_inst->NumInOperandWords());
        case spv::Op::OpConstantNull:
          // Match null constants as long as the type matches.
          return DoesOperandMatch(src_inst->GetOperand(0),
                                  dst_inst->GetOperand(0));

        case spv::Op::OpSpecConstantTrue:
        case spv::Op::OpSpecConstantFalse:
        case spv::Op::OpSpecConstant:
        case spv::Op::OpSpecConstantOp:
          // Match spec constants by name if available, then by the SpecId
          // decoration.
          return MatchOpSpecConstant(src_inst, dst_inst);

        default:
          return false;
      }
    });
  }
}

void Differ::MatchVariableIds() {
  // Bunch all of variable ids as potential matches.
  PotentialIdMap potential_id_map;
  auto get_result_id = [](const opt::Instruction& inst) {
    return inst.result_id();
  };
  auto accept_type_ops = [](const opt::Instruction& inst) {
    return inst.opcode() == spv::Op::OpVariable;
  };

  PoolPotentialIds(src_->types_values(), potential_id_map.src_ids, true,
                   accept_type_ops, get_result_id);
  PoolPotentialIds(dst_->types_values(), potential_id_map.dst_ids, false,
                   accept_type_ops, get_result_id);

  // Then match the ids.  Start with exact matches, then match the leftover with
  // gradually loosening degrees of strictness.  For example, in the absence of
  // debug info, two otherwise identical variables will be matched if one of
  // them has a Private storage class and the other doesn't.
  for (uint32_t flexibility = 0; flexibility < 2; ++flexibility) {
    MatchIds(potential_id_map,
             [this, flexibility](const opt::Instruction* src_inst,
                                 const opt::Instruction* dst_inst) {
               assert(src_inst->opcode() == spv::Op::OpVariable);
               assert(dst_inst->opcode() == spv::Op::OpVariable);

               return MatchOpVariable(src_inst, dst_inst, flexibility);
             });
  }
}

void Differ::MatchFunctions() {
  IdGroup src_func_ids;
  IdGroup dst_func_ids;

  for (const auto& func : src_funcs_) {
    src_func_ids.push_back(func.first);
  }
  for (const auto& func : dst_funcs_) {
    dst_func_ids.push_back(func.first);
  }

  // Base the matching of functions on debug info when available.
  GroupIdsAndMatch<std::string>(
      src_func_ids, dst_func_ids, "", &Differ::GetSanitizedName,
      [this](const IdGroup& src_group, const IdGroup& dst_group) {
        // If there is a single function with this name in src and dst, it's a
        // definite match.
        if (src_group.size() == 1 && dst_group.size() == 1) {
          id_map_.MapIds(src_group[0], dst_group[0]);
          return;
        }

        // If there are multiple functions with the same name, group them by
        // type, and match only if the types match (and are unique).
        GroupIdsAndMatchByMappedId(src_group, dst_group,
                                   &Differ::GroupIdsHelperGetTypeId,
                                   [this](const IdGroup& src_group_by_type_id,
                                          const IdGroup& dst_group_by_type_id) {
                                     if (src_group_by_type_id.size() == 1 &&
                                         dst_group_by_type_id.size() == 1) {
                                       id_map_.MapIds(src_group_by_type_id[0],
                                                      dst_group_by_type_id[0]);
                                     }
                                   });
      });

  // Any functions that are left are pooled together and matched as if unnamed,
  // with the only exception that two functions with mismatching names are not
  // matched.
  //
  // Before that however, the diff of the functions that are matched are taken
  // and processed, so that more of the global variables can be matched before
  // attempting to match the rest of the functions.  They can contribute to the
  // precision of the diff of those functions.
  for (const uint32_t src_func_id : src_func_ids) {
    const uint32_t dst_func_id = id_map_.MappedDstId(src_func_id);
    if (dst_func_id == 0) {
      continue;
    }

    // Since these functions are definite matches, match their parameters for a
    // better diff.
    MatchFunctionParamIds(src_funcs_[src_func_id], dst_funcs_[dst_func_id]);

    // Take the diff of the two functions.
    DiffMatch src_match_result, dst_match_result;
    MatchFunctionBodies(src_func_insts_[src_func_id],
                        dst_func_insts_[dst_func_id], &src_match_result,
                        &dst_match_result);

    // Match ids between the two function bodies; which can also result in
    // global variables getting matched.
    MatchIdsInFunctionBodies(src_func_insts_[src_func_id],
                             dst_func_insts_[dst_func_id], src_match_result,
                             dst_match_result, 0);
  }

  // Best effort match functions with matching return and argument types.
  GroupIdsAndMatchByMappedId(
      src_func_ids, dst_func_ids, &Differ::GroupIdsHelperGetFunctionTypeId,
      [this](const IdGroup& src_group_by_func_type_id,
             const IdGroup& dst_group_by_func_type_id) {
        BestEffortMatchFunctions(src_group_by_func_type_id,
                                 dst_group_by_func_type_id, src_func_insts_,
                                 dst_func_insts_);
      });

  // Best effort match functions with matching return types.
  GroupIdsAndMatchByMappedId(
      src_func_ids, dst_func_ids, &Differ::GroupIdsHelperGetTypeId,
      [this](const IdGroup& src_group_by_type_id,
             const IdGroup& dst_group_by_type_id) {
        BestEffortMatchFunctions(src_group_by_type_id, dst_group_by_type_id,
                                 src_func_insts_, dst_func_insts_);
      });

  // Any function that's left, best effort match them.
  BestEffortMatchFunctions(src_func_ids, dst_func_ids, src_func_insts_,
                           dst_func_insts_);
}

void Differ::MatchDebugs1() {
  // This section in cludes: OpString, OpSourceExtension, OpSource,
  // OpSourceContinued
  MatchDebugAndAnnotationInstructions(src_->debugs1(), dst_->debugs1());
}

void Differ::MatchDebugs2() {
  // This section includes: OpName, OpMemberName
  MatchDebugAndAnnotationInstructions(src_->debugs2(), dst_->debugs2());
}

void Differ::MatchDebugs3() {
  // This section includes: OpModuleProcessed
  MatchDebugAndAnnotationInstructions(src_->debugs3(), dst_->debugs3());
}

void Differ::MatchExtInstDebugInfo() {
  // This section includes OpExtInst for DebugInfo extension
  MatchDebugAndAnnotationInstructions(src_->ext_inst_debuginfo(),
                                      dst_->ext_inst_debuginfo());
}

void Differ::MatchAnnotations() {
  // This section includes OpDecorate and family.
  MatchDebugAndAnnotationInstructions(src_->annotations(), dst_->annotations());
}

const opt::Instruction* Differ::MappedDstInst(
    const opt::Instruction* src_inst) {
  return MappedInstImpl(src_inst, id_map_.SrcToDstMap(), dst_id_to_);
}

const opt::Instruction* Differ::MappedSrcInst(
    const opt::Instruction* dst_inst) {
  return MappedInstImpl(dst_inst, id_map_.DstToSrcMap(), src_id_to_);
}

const opt::Instruction* Differ::MappedInstImpl(
    const opt::Instruction* inst, const IdMap& to_other,
    const IdInstructions& other_id_to) {
  if (inst->HasResultId()) {
    if (to_other.IsMapped(inst->result_id())) {
      const uint32_t other_result_id = to_other.MappedId(inst->result_id());

      assert(other_result_id < other_id_to.inst_map_.size());
      return other_id_to.inst_map_[other_result_id];
    }

    return nullptr;
  }

  return to_other.MappedInst(inst);
}

void Differ::OutputLine(std::function<bool()> are_lines_identical,
                        std::function<void()> output_src_line,
                        std::function<void()> output_dst_line) {
  if (are_lines_identical()) {
    out_ << " ";
    output_src_line();
  } else {
    OutputRed();
    out_ << "-";
    output_src_line();

    OutputGreen();
    out_ << "+";
    output_dst_line();

    OutputResetColor();
  }
}

const opt::Instruction* IterInst(opt::Module::const_inst_iterator& iter) {
  return &*iter;
}

const opt::Instruction* IterInst(InstructionList::const_iterator& iter) {
  return *iter;
}

template <typename InstList>
void Differ::OutputSection(
    const InstList& src_insts, const InstList& dst_insts,
    std::function<void(const opt::Instruction&, const IdInstructions&,
                       const opt::Instruction&)>
        write_inst) {
  auto src_iter = src_insts.begin();
  auto dst_iter = dst_insts.begin();

  // - While src_inst doesn't have a match, output it with -
  // - While dst_inst doesn't have a match, output it with +
  // - Now src_inst and dst_inst both have matches; might not match each other!
  //   * If section is unordered, just process src_inst and its match (dst_inst
  //   or not),
  //     dst_inst will eventually be processed when its match is seen.
  //   * If section is ordered, also just process src_inst and its match.  Its
  //   match must
  //     necessarily be dst_inst.
  while (src_iter != src_insts.end() || dst_iter != dst_insts.end()) {
    OutputRed();
    while (src_iter != src_insts.end() &&
           MappedDstInst(IterInst(src_iter)) == nullptr) {
      out_ << "-";
      write_inst(*IterInst(src_iter), src_id_to_, *IterInst(src_iter));
      ++src_iter;
    }
    OutputGreen();
    while (dst_iter != dst_insts.end() &&
           MappedSrcInst(IterInst(dst_iter)) == nullptr) {
      out_ << "+";
      write_inst(ToMappedSrcIds(*IterInst(dst_iter)), dst_id_to_,
                 *IterInst(dst_iter));
      ++dst_iter;
    }
    OutputResetColor();

    if (src_iter != src_insts.end() && dst_iter != dst_insts.end()) {
      const opt::Instruction* src_inst = IterInst(src_iter);
      const opt::Instruction* matched_dst_inst = MappedDstInst(src_inst);

      assert(matched_dst_inst != nullptr);
      assert(MappedSrcInst(IterInst(dst_iter)) != nullptr);

      OutputLine(
          [this, src_inst, matched_dst_inst]() {
            return DoInstructionsMatch(src_inst, matched_dst_inst);
          },
          [this, src_inst, &write_inst]() {
            write_inst(*src_inst, src_id_to_, *src_inst);
          },
          [this, matched_dst_inst, &write_inst]() {
            write_inst(ToMappedSrcIds(*matched_dst_inst), dst_id_to_,
                       *matched_dst_inst);
          });

      ++src_iter;
      ++dst_iter;
    }
  }
}

void Differ::ToParsedInstruction(
    const opt::Instruction& inst, const IdInstructions& id_to,
    const opt::Instruction& original_inst,
    spv_parsed_instruction_t* parsed_inst,
    std::vector<spv_parsed_operand_t>& parsed_operands,
    std::vector<uint32_t>& inst_binary) {
  inst.ToBinaryWithoutAttachedDebugInsts(&inst_binary);
  parsed_operands.resize(inst.NumOperands());

  parsed_inst->words = inst_binary.data();
  parsed_inst->num_words = static_cast<uint16_t>(inst_binary.size());
  parsed_inst->opcode = static_cast<uint16_t>(inst.opcode());
  parsed_inst->ext_inst_type =
      inst.opcode() == spv::Op::OpExtInst
          ? GetExtInstType(id_to, original_inst.GetSingleWordInOperand(0))
          : SPV_EXT_INST_TYPE_NONE;
  parsed_inst->type_id =
      inst.HasResultType() ? inst.GetSingleWordOperand(0) : 0;
  parsed_inst->result_id = inst.HasResultId() ? inst.result_id() : 0;
  parsed_inst->operands = parsed_operands.data();
  parsed_inst->num_operands = static_cast<uint16_t>(parsed_operands.size());

  // Word 0 is always op and num_words, so operands start at offset 1.
  uint32_t offset = 1;
  for (uint16_t operand_index = 0; operand_index < parsed_inst->num_operands;
       ++operand_index) {
    const opt::Operand& operand = inst.GetOperand(operand_index);
    spv_parsed_operand_t& parsed_operand = parsed_operands[operand_index];

    parsed_operand.offset = static_cast<uint16_t>(offset);
    parsed_operand.num_words = static_cast<uint16_t>(operand.words.size());
    parsed_operand.type = operand.type;
    parsed_operand.number_kind = GetNumberKind(
        id_to, original_inst, operand_index, &parsed_operand.number_bit_width);

    offset += parsed_operand.num_words;
  }
}

opt::Instruction Differ::ToMappedSrcIds(const opt::Instruction& dst_inst) {
  // Create an identical instruction to dst_inst, except ids are changed to the
  // mapped one.
  opt::Instruction mapped_inst = dst_inst;

  for (uint32_t operand_index = 0; operand_index < mapped_inst.NumOperands();
       ++operand_index) {
    opt::Operand& operand = mapped_inst.GetOperand(operand_index);

    if (spvIsIdType(operand.type)) {
      assert(id_map_.IsDstMapped(operand.AsId()));
      operand.words[0] = id_map_.MappedSrcId(operand.AsId());
    }
  }

  return mapped_inst;
}

spv_result_t Differ::Output() {
  id_map_.MapUnmatchedIds(
      [this](uint32_t src_id) { return src_id_to_.IsDefined(src_id); },
      [this](uint32_t dst_id) { return dst_id_to_.IsDefined(dst_id); });
  src_id_to_.inst_map_.resize(id_map_.SrcToDstMap().IdBound(), nullptr);
  dst_id_to_.inst_map_.resize(id_map_.DstToSrcMap().IdBound(), nullptr);

  const spv_target_env target_env = SPV_ENV_UNIVERSAL_1_6;
  spv_opcode_table opcode_table;
  spv_operand_table operand_table;
  spv_ext_inst_table ext_inst_table;
  spv_result_t result;

  result = spvOpcodeTableGet(&opcode_table, target_env);
  if (result != SPV_SUCCESS) return result;

  result = spvOperandTableGet(&operand_table, target_env);
  if (result != SPV_SUCCESS) return result;

  result = spvExtInstTableGet(&ext_inst_table, target_env);
  if (result != SPV_SUCCESS) return result;

  spv_context_t context{
      target_env,
      opcode_table,
      operand_table,
      ext_inst_table,
  };

  const AssemblyGrammar grammar(&context);
  if (!grammar.isValid()) return SPV_ERROR_INVALID_TABLE;

  uint32_t disassembly_options = SPV_BINARY_TO_TEXT_OPTION_PRINT;
  if (options_.indent) {
    disassembly_options |= SPV_BINARY_TO_TEXT_OPTION_INDENT;
  }

  NameMapper name_mapper = GetTrivialNameMapper();
  disassemble::InstructionDisassembler dis(grammar, out_, disassembly_options,
                                           name_mapper);

  if (!options_.no_header) {
    // Output the header
    // TODO: when using diff with text, the assembler overrides the version and
    // generator, so these aren't reflected correctly in the output.  Could
    // potentially extract this info from the header comment.
    OutputLine([]() { return true; }, [&dis]() { dis.EmitHeaderSpirv(); },
               []() { assert(false && "Unreachable"); });
    OutputLine([this]() { return src_->version() == dst_->version(); },
               [this, &dis]() { dis.EmitHeaderVersion(src_->version()); },
               [this, &dis]() { dis.EmitHeaderVersion(dst_->version()); });
    OutputLine([this]() { return src_->generator() == dst_->generator(); },
               [this, &dis]() { dis.EmitHeaderGenerator(src_->generator()); },
               [this, &dis]() { dis.EmitHeaderGenerator(dst_->generator()); });
    OutputLine(
        [this]() { return src_->IdBound() == id_map_.SrcToDstMap().IdBound(); },
        [this, &dis]() { dis.EmitHeaderIdBound(src_->IdBound()); },
        [this, &dis]() {
          dis.EmitHeaderIdBound(id_map_.SrcToDstMap().IdBound());
        });
    OutputLine([this]() { return src_->schema() == dst_->schema(); },
               [this, &dis]() { dis.EmitHeaderSchema(src_->schema()); },
               [this, &dis]() { dis.EmitHeaderSchema(dst_->schema()); });
  }

  // For each section, iterate both modules and output the disassembly.
  auto write_inst = [this, &dis](const opt::Instruction& inst,
                                 const IdInstructions& id_to,
                                 const opt::Instruction& original_inst) {
    spv_parsed_instruction_t parsed_inst;
    std::vector<spv_parsed_operand_t> parsed_operands;
    std::vector<uint32_t> inst_binary;

    ToParsedInstruction(inst, id_to, original_inst, &parsed_inst,
                        parsed_operands, inst_binary);

    dis.EmitInstruction(parsed_inst, 0);
  };

  OutputSection(src_->capabilities(), dst_->capabilities(), write_inst);
  OutputSection(src_->extensions(), dst_->extensions(), write_inst);
  OutputSection(src_->ext_inst_imports(), dst_->ext_inst_imports(), write_inst);

  // There is only one memory model.
  OutputLine(
      [this]() {
        return DoInstructionsMatch(src_->GetMemoryModel(),
                                   dst_->GetMemoryModel());
      },
      [this, &write_inst]() {
        write_inst(*src_->GetMemoryModel(), src_id_to_,
                   *src_->GetMemoryModel());
      },
      [this, &write_inst]() {
        write_inst(*dst_->GetMemoryModel(), dst_id_to_,
                   *dst_->GetMemoryModel());
      });

  OutputSection(src_->entry_points(), dst_->entry_points(), write_inst);
  OutputSection(src_->execution_modes(), dst_->execution_modes(), write_inst);
  OutputSection(src_->debugs1(), dst_->debugs1(), write_inst);
  OutputSection(src_->debugs2(), dst_->debugs2(), write_inst);
  OutputSection(src_->debugs3(), dst_->debugs3(), write_inst);
  OutputSection(src_->ext_inst_debuginfo(), dst_->ext_inst_debuginfo(),
                write_inst);
  OutputSection(src_->annotations(), dst_->annotations(), write_inst);
  OutputSection(src_->types_values(), dst_->types_values(), write_inst);

  // Get the body of all the functions.
  FunctionInstMap src_func_header_insts;
  FunctionInstMap dst_func_header_insts;

  GetFunctionHeaderInstructions(src_, &src_func_header_insts);
  GetFunctionHeaderInstructions(dst_, &dst_func_header_insts);

  for (const auto& src_func : src_func_insts_) {
    const uint32_t src_func_id = src_func.first;
    const InstructionList& src_insts = src_func.second;
    const InstructionList& src_header_insts =
        src_func_header_insts[src_func_id];

    const uint32_t dst_func_id = id_map_.MappedDstId(src_func_id);
    if (dst_func_insts_.find(dst_func_id) == dst_func_insts_.end()) {
      OutputSection(src_header_insts, InstructionList(), write_inst);
      OutputSection(src_insts, InstructionList(), write_inst);
      continue;
    }

    const InstructionList& dst_insts = dst_func_insts_[dst_func_id];
    const InstructionList& dst_header_insts =
        dst_func_header_insts[dst_func_id];
    OutputSection(src_header_insts, dst_header_insts, write_inst);
    OutputSection(src_insts, dst_insts, write_inst);
  }

  for (const auto& dst_func : dst_func_insts_) {
    const uint32_t dst_func_id = dst_func.first;
    const InstructionList& dst_insts = dst_func.second;
    const InstructionList& dst_header_insts =
        dst_func_header_insts[dst_func_id];

    const uint32_t src_func_id = id_map_.MappedSrcId(dst_func_id);
    if (src_func_insts_.find(src_func_id) == src_func_insts_.end()) {
      OutputSection(InstructionList(), dst_header_insts, write_inst);
      OutputSection(InstructionList(), dst_insts, write_inst);
    }
  }

  out_ << std::flush;

  return SPV_SUCCESS;
}

}  // anonymous namespace

spv_result_t Diff(opt::IRContext* src, opt::IRContext* dst, std::ostream& out,
                  Options options) {
  // High level algorithm:
  //
  // - Some sections of SPIR-V don't deal with ids; instructions in those
  //   sections are matched identically.  For example OpCapability instructions.
  // - Some sections produce ids, and they can be trivially matched by their
  //   parameters.  For example OpExtInstImport instructions.
  // - Some sections annotate ids.  These are matched at the end, after the ids
  //   themselves are matched.  For example OpName or OpDecorate instructions.
  // - Some sections produce ids that depend on other ids and they can be
  //   recursively matched.  For example OpType* instructions.
  // - Some sections produce ids that are not trivially matched.  For these ids,
  //   the debug info is used when possible, or a best guess (such as through
  //   decorations) is used.  For example OpVariable instructions.
  // - Matching functions is done with multiple attempts:
  //   * Functions with identical debug names are matched if there are no
  //     overloads.
  //   * Otherwise, functions with identical debug names and types are matched.
  //   * The rest of the functions are best-effort matched, first in groups of
  //     identical type, then any with any.
  //     * The best-effort matching takes the diff of every pair of functions in
  //       a group and selects the top matches that also meet a similarity
  //       index.
  //   * Once a pair of functions are matched, the fuzzy diff of the
  //     instructions is used to match the instructions in the function body.
  //     The fuzzy diff makes sure that sufficiently similar instructions are
  //     matched and that yet-to-be-matched result ids don't result in a larger
  //     diff.
  //
  // Once the instructions are matched between the src and dst SPIR-V, the src
  // is traversed and its disassembly is output.  In the process, any unmatched
  // instruction is prefixed with -, and any unmatched instruction in dst in the
  // same section is output prefixed with +.  To avoid confusion, the
  // instructions in dst are output with matching ids in src so the output
  // assembly is consistent.

  Differ differ(src, dst, out, options);

  // First, match instructions between the different non-annotation sections of
  // the SPIR-V.
  differ.MatchCapabilities();
  differ.MatchExtensions();
  differ.MatchExtInstImportIds();
  differ.MatchMemoryModel();
  differ.MatchEntryPointIds();
  differ.MatchExecutionModes();
  differ.MatchTypeForwardPointers();
  differ.MatchTypeIds();
  differ.MatchConstants();
  differ.MatchVariableIds();
  differ.MatchFunctions();

  // Match instructions that annotate previously-matched ids.
  differ.MatchDebugs1();
  differ.MatchDebugs2();
  differ.MatchDebugs3();
  differ.MatchExtInstDebugInfo();
  differ.MatchAnnotations();

  // Show the disassembly with the diff.
  //
  // TODO: Based on an option, output either based on src or dst, i.e. the diff
  // can show the ids and instruction/function order either from src or dst.
  spv_result_t result = differ.Output();

  differ.DumpIdMap();

  return result;
}

}  // namespace diff
}  // namespace spvtools