comparison.cc

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// -*- mode: C++ -*-
//
// Copyright 2020-2024 Google LLC
//
// Licensed under the Apache License v2.0 with LLVM Exceptions (the
// "License"); you may not use this file except in compliance with the
// License.  You may obtain a copy of the License at
//
//     https://llvm.org/LICENSE.txt
//
// 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.
//
// Author: Maria Teguiani
// Author: Giuliano Procida
// Author: Ignes Simeonova

#include "comparison.h"

#include <algorithm>
#include <array>
#include <cstddef>
#include <functional>
#include <map>
#include <optional>
#include <ostream>
#include <set>
#include <sstream>
#include <string>
#include <string_view>
#include <unordered_map>
#include <utility>
#include <vector>

#include "error.h"
#include "graph.h"
#include "order.h"
#include "runtime.h"
#include "scc.h"

namespace stg {
namespace diff {

namespace {

struct IgnoreDescriptor {
  std::string_view name;
  Ignore::Value value;
};

constexpr std::array<IgnoreDescriptor, 9> kIgnores{{
  {"type_declaration_status",  Ignore::TYPE_DECLARATION_STATUS  },
  {"symbol_type_presence",     Ignore::SYMBOL_TYPE_PRESENCE     },
  {"primitive_type_encoding",  Ignore::PRIMITIVE_TYPE_ENCODING  },
  {"member_size",              Ignore::MEMBER_SIZE              },
  {"enum_underlying_type",     Ignore::ENUM_UNDERLYING_TYPE     },
  {"qualifier",                Ignore::QUALIFIER                },
  {"linux_symbol_crc",         Ignore::SYMBOL_CRC               },
  {"interface_addition",       Ignore::INTERFACE_ADDITION       },
  {"type_definition_addition", Ignore::TYPE_DEFINITION_ADDITION },
}};

}  // namespace

std::optional<Ignore::Value> ParseIgnore(std::string_view ignore) {
  for (const auto& [name, value] : kIgnores) {
    if (name == ignore) {
      return {value};
    }
  }
  return {};
}

std::ostream& operator<<(std::ostream& os, IgnoreUsage) {
  os << "ignore options:";
  for (const auto& [name, _] : kIgnores) {
    os << ' ' << name;
  }
  return os << '\n';
}

namespace {

struct Result {
  // Used when two nodes cannot be meaningfully compared.
  Result& MarkIncomparable() {
    same = false;
    diff.has_changes = true;
    return *this;
  }

  // Used when a node attribute has changed.
  void AddNodeDiff(const std::string& text) {
    same = false;
    diff.has_changes = true;
    diff.Add(text, {});
  }

  // Used when a node attribute may have changed.
  template <typename T>
  void MaybeAddNodeDiff(
      const std::string& text, const T& before, const T& after) {
    if (before != after) {
      std::ostringstream os;
      os << text << " changed from " << before << " to " << after;
      AddNodeDiff(os.str());
    }
  }

  // Used when a node attribute may have changed, lazy version.
  template <typename T>
  void MaybeAddNodeDiff(const std::function<void(std::ostream&)>& text,
                        const T& before, const T& after) {
    if (before != after) {
      std::ostringstream os;
      text(os);
      os << " changed from " << before << " to " << after;
      AddNodeDiff(os.str());
    }
  }

  // Used when node attributes are optional values.
  template <typename T>
  void MaybeAddNodeDiff(const std::string& text, const std::optional<T>& before,
                        const std::optional<T>& after) {
    if (before && after) {
      MaybeAddNodeDiff(text, *before, *after);
    } else if (before) {
      std::ostringstream os;
      os << text << ' ' << *before << " was removed";
      AddNodeDiff(os.str());
    } else if (after) {
      std::ostringstream os;
      os << text << ' ' << *after << " was added";
      AddNodeDiff(os.str());
    }
  }

  // Used when an edge has been removed or added.
  void AddEdgeDiff(const std::string& text, const Comparison& comparison) {
    same = false;
    diff.Add(text, comparison);
  }

  // Used when an edge to a possible comparison is present.
  void MaybeAddEdgeDiff(const std::string& text,
                        const std::pair<bool, Comparison>& p) {
    same &= p.first;
    const auto& comparison = p.second;
    if (comparison != Comparison{}) {
      diff.Add(text, comparison);
    }
  }

  // Used when an edge to a possible comparison is present, lazy version.
  void MaybeAddEdgeDiff(const std::function<void(std::ostream&)>& text,
                        const std::pair<bool, Comparison>& p) {
    same &= p.first;
    const auto& comparison = p.second;
    if (comparison != Comparison{}) {
      std::ostringstream os;
      text(os);
      diff.Add(os.str(), comparison);
    }
  }

  bool same = true;
  Diff diff;
};

struct ResolveTypedef {
  ResolveTypedef(const Graph& graph, Id& id, std::vector<std::string>& names)
      : graph(graph), id(id), names(names) {}

  bool operator()(const Typedef& x) const {
    id = x.referred_type_id;
    names.push_back(x.name);
    return true;
  }

  template <typename Node>
  bool operator()(const Node&) const {
    return false;
  }

  const Graph& graph;
  Id& id;
  std::vector<std::string>& names;
};

using Qualifiers = std::set<Qualifier>;

struct ResolveQualifier {
  ResolveQualifier(const Graph& graph, Id& id, Qualifiers& qualifiers)
      : graph(graph), id(id), qualifiers(qualifiers) {}

  bool operator()(const Qualified& x) const {
    id = x.qualified_type_id;
    qualifiers.insert(x.qualifier);
    return true;
  }

  bool operator()(const Array&) const {
    // There should be no qualifiers here.
    qualifiers.clear();
    return false;
  }

  bool operator()(const Function&) const {
    // There should be no qualifiers here.
    qualifiers.clear();
    return false;
  }

  template <typename Node>
  bool operator()(const Node&) const {
    return false;
  }

  const Graph& graph;
  Id& id;
  Qualifiers& qualifiers;
};

// Separate qualifiers from underlying type.
//
// The caller must always be prepared to receive a different type as qualifiers
// are sometimes discarded.
std::pair<Id, Qualifiers> ResolveQualifiers(const Graph& graph, Id id) {
  std::pair<Id, Qualifiers> result = {id, {}};
  ResolveQualifier resolve(graph, result.first, result.second);
  while (graph.Apply(resolve, result.first)) {}
  return result;
}

struct MatchingKey {
  explicit MatchingKey(const Graph& graph) : graph(graph) {}

  std::string operator()(Id id) const {
    return graph.Apply(*this, id);
  }

  std::string operator()(const BaseClass& x) const {
    return (*this)(x.type_id);
  }

  std::string operator()(const Method& x) const {
    return x.name + ',' + x.mangled_name;
  }

  std::string operator()(const Member& x) const {
    if (!x.name.empty()) {
      return x.name;
    }
    return (*this)(x.type_id);
  }

  std::string operator()(const VariantMember& x) const {
    return x.name;
  }

  std::string operator()(const StructUnion& x) const {
    if (!x.name.empty()) {
      return x.name;
    }
    if (x.definition) {
      const auto& members = x.definition->members;
      for (const auto& member : members) {
        const auto recursive = (*this)(member);
        if (!recursive.empty()) {
          return recursive + '+';
        }
      }
    }
    return {};
  }

  template <typename Node>
  std::string operator()(const Node&) const {
    return {};
  }

  const Graph& graph;
};

using KeyIndexPairs = std::vector<std::pair<std::string, size_t>>;

KeyIndexPairs MatchingKeys(const Graph& graph, const std::vector<Id>& ids) {
  KeyIndexPairs keys;
  const auto size = ids.size();
  keys.reserve(size);
  size_t anonymous_ix = 0;
  for (size_t ix = 0; ix < size; ++ix) {
    auto key = MatchingKey(graph)(ids[ix]);
    if (key.empty()) {
      key = "#anon#" + std::to_string(anonymous_ix++);
    }
    keys.emplace_back(key, ix);
  }
  std::stable_sort(keys.begin(), keys.end());
  return keys;
}

KeyIndexPairs MatchingKeys(const Enumeration::Enumerators& enums) {
  KeyIndexPairs names;
  const auto size = enums.size();
  names.reserve(size);
  for (size_t ix = 0; ix < size; ++ix) {
    const auto& name = enums[ix].first;
    names.emplace_back(name, ix);
  }
  std::stable_sort(names.begin(), names.end());
  return names;
}

using MatchedPairs =
    std::vector<std::pair<std::optional<size_t>, std::optional<size_t>>>;

MatchedPairs PairUp(const KeyIndexPairs& keys1, const KeyIndexPairs& keys2) {
  MatchedPairs pairs;
  pairs.reserve(std::max(keys1.size(), keys2.size()));
  auto it1 = keys1.begin();
  auto it2 = keys2.begin();
  const auto end1 = keys1.end();
  const auto end2 = keys2.end();
  while (it1 != end1 || it2 != end2) {
    if (it2 == end2 || (it1 != end1 && it1->first < it2->first)) {
      // removed
      pairs.push_back({{it1->second}, {}});
      ++it1;
    } else if (it1 == end1 || (it2 != end2 && it1->first > it2->first)) {
      // added
      pairs.push_back({{}, {it2->second}});
      ++it2;
    } else {
      // in both
      pairs.push_back({{it1->second}, {it2->second}});
      ++it1;
      ++it2;
    }
  }
  return pairs;
}

std::string QualifiersMessage(Qualifier qualifier, const std::string& action) {
  std::ostringstream os;
  os << "qualifier " << qualifier << ' ' << action;
  return os.str();
}

struct CompareWorker {
  CompareWorker(Runtime& runtime, const Ignore& ignore, const Graph& graph,
                Outcomes& outcomes)
      : ignore(ignore), graph(graph), outcomes(outcomes),
        queried(runtime, "compare.queried"),
        already_compared(runtime, "compare.already_compared"),
        being_compared(runtime, "compare.being_compared"),
        really_compared(runtime, "compare.really_compared"),
        equivalent(runtime, "compare.equivalent"),
        inequivalent(runtime, "compare.inequivalent"),
        scc_size(runtime, "compare.scc_size") {}

  /*
   * We compute a diff for every visited node.
   *
   * Each node has one of:
   *
   * * same == true; perhaps only tentative edge differences
   * * same == false; at least one definitive node or edge difference
   *
   * On the first visit to a node, the value of same is determined via recursive
   * comparison and the diff may contain local and edge differences. If an SCC
   * contains only internal edge differences (and equivalently same is true)
   * then the differences can all (eventually) be discarded.
   *
   * On exit from the first visit to a node, same reflects the tree of
   * comparisons below that node in the DFS and similarly, the diff graph
   * starting from the node contains a subtree of this tree plus potentially
   * edges to existing nodes to the side or below (already visited SCCs,
   * sharing), or above (back links forming cycles).
   *
   * When an SCC is closed, same is true results in the deletion of all the
   * nodes' diffs. The value of same is recorded for all nodes in the SCC.
   *
   * On other visits to a node, there are 2 cases. The node is still open
   * (meaning a recursive visit): return true and an edge diff. The node is
   * closed (meaning a repeat visit): return the stored value and an edge diff.
   */
  std::pair<bool, Comparison> operator()(Id id1, Id id2) {
    const Comparison comparison{{id1}, {id2}};
    ++queried;

    // Check if the comparison has an already known result.
    const auto already_known = known.find(comparison);
    if (already_known != known.end()) {
      // Already visited and closed.
      ++already_compared;
      return already_known->second
          ? std::make_pair(true, Comparison{})
          : std::make_pair(false, comparison);
    }
    // The comparison is either already open or has not been visited at all.

    // Record the comparison with the Strongly-Connected Component finder.
    const auto handle = scc.Open(comparison);
    if (!handle) {
      // Already open.
      //
      // Return a dummy true outcome and some tentative diffs. The diffs may end
      // up not being used and, while it would be nice to be lazier, they encode
      // all the cycling-breaking edges needed to recreate a full diff
      // structure.
      ++being_compared;
      return {true, comparison};
    }
    // The comparison has now been opened, we must close it before returning.

    // Really compare.
    ++really_compared;
    const auto [same, diff] = CompareWithResolution(id1, id2);

    // Record the result and check for a complete Strongly-Connected Component.
    outcomes.insert({comparison, diff});
    const auto comparisons = scc.Close(*handle);
    if (comparisons.empty()) {
      // Open SCC.
      //
      // Note that both same and diff are tentative as comparison is still
      // open.
      return {same, comparison};
    }
    // Closed SCC.
    //
    // Note that same and diff now include every inequality and difference in
    // the SCC via the DFS spanning tree.
    const auto size = comparisons.size();
    scc_size.Add(size);
    (same ? equivalent : inequivalent) += size;
    for (const auto& c : comparisons) {
      // Record equality / inequality.
      known.insert({c, same});
      if (same) {
        // Discard provisional diff.
        outcomes.erase(c);
      }
    }
    return same
        ? std::make_pair(true, Comparison{})
        : std::make_pair(false, comparison);
  }

  Result CompareWithResolution(Id id1, Id id2) {
    const auto [unqualified1, qualifiers1] = ResolveQualifiers(graph, id1);
    const auto [unqualified2, qualifiers2] = ResolveQualifiers(graph, id2);
    if (!qualifiers1.empty() || !qualifiers2.empty()) {
      // Qualified type difference.
      Result result;
      auto it1 = qualifiers1.begin();
      auto it2 = qualifiers2.begin();
      const auto end1 = qualifiers1.end();
      const auto end2 = qualifiers2.end();
      while (it1 != end1 || it2 != end2) {
        if (it2 == end2 || (it1 != end1 && *it1 < *it2)) {
          if (!ignore.Test(Ignore::QUALIFIER)) {
            result.AddNodeDiff(QualifiersMessage(*it1, "removed"));
          }
          ++it1;
        } else if (it1 == end1 || (it2 != end2 && *it1 > *it2)) {
          if (!ignore.Test(Ignore::QUALIFIER)) {
            result.AddNodeDiff(QualifiersMessage(*it2, "added"));
          }
          ++it2;
        } else {
          ++it1;
          ++it2;
        }
      }
      result.MaybeAddEdgeDiff("underlying",
                              (*this)(unqualified1, unqualified2));
      return result;
    }

    const auto [resolved1, typedefs1] = ResolveTypedefs(graph, unqualified1);
    const auto [resolved2, typedefs2] = ResolveTypedefs(graph, unqualified2);
    if (unqualified1 != resolved1 || unqualified2 != resolved2) {
      // Typedef difference.
      Result result;
      result.diff.holds_changes = !typedefs1.empty() && !typedefs2.empty()
                                  && typedefs1[0] == typedefs2[0];
      result.MaybeAddEdgeDiff("resolved", (*this)(resolved1, resolved2));
      return result;
    }

    // Compare nodes directly.
    return graph.Apply2(*this, unqualified1, unqualified2);
  }

  Comparison Removed(Id id) {
    Comparison comparison{{id}, {}};
    outcomes.insert({comparison, {}});
    return comparison;
  }

  Comparison Added(Id id) {
    Comparison comparison{{}, {id}};
    outcomes.insert({comparison, {}});
    return comparison;
  }

  void Defined(bool defined1, bool defined2, Result& result) {
    if (defined1 != defined2) {
      if (!ignore.Test(Ignore::TYPE_DECLARATION_STATUS)
          && !(ignore.Test(Ignore::TYPE_DEFINITION_ADDITION) && defined2)) {
        std::ostringstream os;
        os << "was " << (defined1 ? "fully defined" : "only declared")
           << ", is now " << (defined2 ? "fully defined" : "only declared");
        result.AddNodeDiff(os.str());
      }
    }
  }

  void Nodes(const std::vector<Id>& ids1, const std::vector<Id>& ids2,
             Result& result) {
    const auto keys1 = MatchingKeys(graph, ids1);
    const auto keys2 = MatchingKeys(graph, ids2);
    auto pairs = PairUp(keys1, keys2);
    Reorder(pairs);
    for (const auto& [index1, index2] : pairs) {
      if (index1 && !index2) {
        // removed
        const auto& x1 = ids1[*index1];
        result.AddEdgeDiff("", Removed(x1));
      } else if (!index1 && index2) {
        // added
        const auto& x2 = ids2[*index2];
        result.AddEdgeDiff("", Added(x2));
      } else if (index1 && index2) {
        // in both
        const auto& x1 = ids1[*index1];
        const auto& x2 = ids2[*index2];
        result.MaybeAddEdgeDiff("", (*this)(x1, x2));
      } else {
        Die() << "CompareWorker::Nodes: impossible pair";
      }
    }
  }

  void Nodes(const std::map<std::string, Id>& x1,
             const std::map<std::string, Id>& x2,
             bool ignore_added, Result& result) {
    // Group diffs into removed, added and changed symbols for readability.
    std::vector<Id> removed;
    std::vector<Id> added;
    std::vector<std::pair<Id, Id>> in_both;

    auto it1 = x1.begin();
    auto it2 = x2.begin();
    const auto end1 = x1.end();
    const auto end2 = x2.end();
    while (it1 != end1 || it2 != end2) {
      if (it2 == end2 || (it1 != end1 && it1->first < it2->first)) {
        // removed
        removed.push_back(it1->second);
        ++it1;
      } else if (it1 == end1 || (it2 != end2 && it1->first > it2->first)) {
        // added
        if (!ignore_added) {
          added.push_back(it2->second);
        }
        ++it2;
      } else {
        // in both
        in_both.emplace_back(it1->second, it2->second);
        ++it1;
        ++it2;
      }
    }

    for (const auto symbol1 : removed) {
      result.AddEdgeDiff("", Removed(symbol1));
    }
    for (const auto symbol2 : added) {
      result.AddEdgeDiff("", Added(symbol2));
    }
    for (const auto& [symbol1, symbol2] : in_both) {
      result.MaybeAddEdgeDiff("", (*this)(symbol1, symbol2));
    }
  }

  Result Mismatch() {
    return Result().MarkIncomparable();
  }

  Result operator()(const Special& x1, const Special& x2) {
    Result result;
    if (x1.kind != x2.kind) {
      return result.MarkIncomparable();
    }
    return result;
  }

  Result operator()(const PointerReference& x1, const PointerReference& x2) {
    Result result;
    if (x1.kind != x2.kind) {
      return result.MarkIncomparable();
    }
    const auto type_diff = (*this)(x1.pointee_type_id, x2.pointee_type_id);
    const char* text = x1.kind == PointerReference::Kind::POINTER
                       ? "pointed-to" : "referred-to";
    result.MaybeAddEdgeDiff(text, type_diff);
    return result;
  }

  Result operator()(const PointerToMember& x1, const PointerToMember& x2) {
    Result result;
    result.MaybeAddEdgeDiff(
        "containing", (*this)(x1.containing_type_id, x2.containing_type_id));
    result.MaybeAddEdgeDiff(
        "", (*this)(x1.pointee_type_id, x2.pointee_type_id));
    return result;
  }

  Result operator()(const Typedef&, const Typedef&) {
    // Compare will never attempt to directly compare Typedefs.
    Die() << "internal error: CompareWorker(Typedef)";
  }

  Result operator()(const Qualified&, const Qualified&) {
    // Compare will never attempt to directly compare Qualifiers.
    Die() << "internal error: CompareWorker(Qualified)";
  }

  Result operator()(const Primitive& x1, const Primitive& x2) {
    Result result;
    if (x1.name != x2.name) {
      return result.MarkIncomparable();
    }
    result.diff.holds_changes = !x1.name.empty();
    if (!ignore.Test(Ignore::PRIMITIVE_TYPE_ENCODING)) {
      result.MaybeAddNodeDiff("encoding", x1.encoding, x2.encoding);
    }
    result.MaybeAddNodeDiff("byte size", x1.bytesize, x2.bytesize);
    return result;
  }

  Result operator()(const Array& x1, const Array& x2) {
    Result result;
    result.MaybeAddNodeDiff("number of elements",
                            x1.number_of_elements, x2.number_of_elements);
    const auto type_diff = (*this)(x1.element_type_id, x2.element_type_id);
    result.MaybeAddEdgeDiff("element", type_diff);
    return result;
  }

  Result operator()(const BaseClass& x1, const BaseClass& x2) {
    Result result;
    result.MaybeAddNodeDiff("inheritance", x1.inheritance, x2.inheritance);
    result.MaybeAddNodeDiff("offset", x1.offset, x2.offset);
    result.MaybeAddEdgeDiff("", (*this)(x1.type_id, x2.type_id));
    return result;
  }

  Result operator()(const Method& x1, const Method& x2) {
    Result result;
    result.MaybeAddNodeDiff(
        "vtable offset", x1.vtable_offset, x2.vtable_offset);
    result.MaybeAddEdgeDiff("", (*this)(x1.type_id, x2.type_id));
    return result;
  }

  Result operator()(const Member& x1, const Member& x2) {
    Result result;
    result.MaybeAddNodeDiff("offset", x1.offset, x2.offset);
    if (!ignore.Test(Ignore::MEMBER_SIZE)) {
      const bool bitfield1 = x1.bitsize > 0;
      const bool bitfield2 = x2.bitsize > 0;
      if (bitfield1 != bitfield2) {
        std::ostringstream os;
        os << "was " << (bitfield1 ? "a bit-field" : "not a bit-field")
           << ", is now " << (bitfield2 ? "a bit-field" : "not a bit-field");
        result.AddNodeDiff(os.str());
      } else {
        result.MaybeAddNodeDiff("bit-field size", x1.bitsize, x2.bitsize);
      }
    }
    result.MaybeAddEdgeDiff("", (*this)(x1.type_id, x2.type_id));
    return result;
  }

  Result operator()(const VariantMember& x1, const VariantMember& x2) {
    Result result;
    result.MaybeAddNodeDiff("discriminant", x1.discriminant_value,
                            x2.discriminant_value);
    result.MaybeAddEdgeDiff("", (*this)(x1.type_id, x2.type_id));
    return result;
  }

  Result operator()(const StructUnion& x1, const StructUnion& x2) {
    Result result;
    // Compare two anonymous types recursively, not holding diffs.
    // Compare two identically named types recursively, holding diffs.
    // Everything else treated as distinct. No recursion.
    if (x1.kind != x2.kind || x1.name != x2.name) {
      return result.MarkIncomparable();
    }
    result.diff.holds_changes = !x1.name.empty();

    const auto& definition1 = x1.definition;
    const auto& definition2 = x2.definition;
    Defined(definition1.has_value(), definition2.has_value(), result);

    if (definition1.has_value() && definition2.has_value()) {
      result.MaybeAddNodeDiff(
          "byte size", definition1->bytesize, definition2->bytesize);
      Nodes(definition1->base_classes, definition2->base_classes, result);
      Nodes(definition1->methods, definition2->methods, result);
      Nodes(definition1->members, definition2->members, result);
    }

    return result;
  }

  Result operator()(const Enumeration& x1, const Enumeration& x2) {
    Result result;
    // Compare two anonymous types recursively, not holding diffs.
    // Compare two identically named types recursively, holding diffs.
    // Everything else treated as distinct. No recursion.
    if (x1.name != x2.name) {
      return result.MarkIncomparable();
    }
    result.diff.holds_changes = !x1.name.empty();

    const auto& definition1 = x1.definition;
    const auto& definition2 = x2.definition;
    Defined(definition1.has_value(), definition2.has_value(), result);

    if (definition1.has_value() && definition2.has_value()) {
      if (!ignore.Test(Ignore::ENUM_UNDERLYING_TYPE)) {
        const auto type_diff = (*this)(definition1->underlying_type_id,
                                       definition2->underlying_type_id);
        result.MaybeAddEdgeDiff("underlying", type_diff);
      }

      const auto enums1 = definition1->enumerators;
      const auto enums2 = definition2->enumerators;
      const auto keys1 = MatchingKeys(enums1);
      const auto keys2 = MatchingKeys(enums2);
      auto pairs = PairUp(keys1, keys2);
      Reorder(pairs);
      for (const auto& [index1, index2] : pairs) {
        if (index1 && !index2) {
          // removed
          const auto& enum1 = enums1[*index1];
          std::ostringstream os;
          os << "enumerator '" << enum1.first
             << "' (" << enum1.second << ") was removed";
          result.AddNodeDiff(os.str());
        } else if (!index1 && index2) {
          // added
          const auto& enum2 = enums2[*index2];
          std::ostringstream os;
          os << "enumerator '" << enum2.first
             << "' (" << enum2.second << ") was added";
          result.AddNodeDiff(os.str());
        } else if (index1 && index2) {
          // in both
          const auto& enum1 = enums1[*index1];
          const auto& enum2 = enums2[*index2];
          result.MaybeAddNodeDiff(
              [&](std::ostream& os) {
                os << "enumerator '" << enum1.first << "' value";
              },
              enum1.second, enum2.second);
        } else {
          Die() << "CompareWorker(Enumeration): impossible pair";
        }
      }
    }

    return result;
  }

  Result operator()(const Variant& x1, const Variant& x2) {
    Result result;
    // Compare two identically named variants recursively, holding diffs.
    // Everything else treated as distinct. No recursion.
    if (x1.name != x2.name) {
      return result.MarkIncomparable();
    }
    result.diff.holds_changes = true;  // Anonymous variants are not allowed.

    result.MaybeAddNodeDiff("bytesize", x1.bytesize, x2.bytesize);
    if (x1.discriminant.has_value() && x2.discriminant.has_value()) {
      const auto type_diff =
          (*this)(x1.discriminant.value(), x2.discriminant.value());
      result.MaybeAddEdgeDiff("discriminant", type_diff);
    } else if (x1.discriminant.has_value()) {
      result.AddEdgeDiff("", Removed(x1.discriminant.value()));
    } else if (x2.discriminant.has_value()) {
      result.AddEdgeDiff("", Added(x2.discriminant.value()));
    }
    Nodes(x1.members, x2.members, result);
    return result;
  }

  Result operator()(const Function& x1, const Function& x2) {
    Result result;
    const auto type_diff = (*this)(x1.return_type_id, x2.return_type_id);
    result.MaybeAddEdgeDiff("return", type_diff);

    const auto& parameters1 = x1.parameters;
    const auto& parameters2 = x2.parameters;
    const size_t min = std::min(parameters1.size(), parameters2.size());
    for (size_t i = 0; i < min; ++i) {
      const Id p1 = parameters1.at(i);
      const Id p2 = parameters2.at(i);
      result.MaybeAddEdgeDiff(
          [&](std::ostream& os) {
            os << "parameter " << i + 1;
          },
          (*this)(p1, p2));
    }

    const bool added = parameters1.size() < parameters2.size();
    const auto& which = added ? x2 : x1;
    const auto& parameters = which.parameters;
    for (size_t i = min; i < parameters.size(); ++i) {
      const Id parameter = parameters.at(i);
      std::ostringstream os;
      os << "parameter " << i + 1 << " of";
      auto diff = added ? Added(parameter) : Removed(parameter);
      result.AddEdgeDiff(os.str(), diff);
    }

    return result;
  }

  Result operator()(const ElfSymbol& x1, const ElfSymbol& x2) {
    // ELF symbols have a lot of different attributes that can impact ABI
    // compatibility and others that either cannot or are subsumed by
    // information elsewhere.
    //
    // Not all attributes are exposed by elf_symbol and fewer still in ABI XML.
    //
    // name - definitely part of the key
    //
    // type - (ELF symbol type, not C type) one important distinction here would
    // be global vs thread-local variables
    //
    // section - not exposed (modulo aliasing information) and don't care
    //
    // value (address, usually) - not exposed (modulo aliasing information) and
    // don't care
    //
    // size - don't care (for variables, subsumed by type information)
    //
    // binding - global vs weak vs unique vs local
    //
    // visibility - default > protected > hidden > internal
    //
    // version / is-default-version - in theory the "hidden" bit (separate from
    // hidden and local above) can be set independently of the version, but in
    // practice at most one version of given name is non-hidden; version
    // (including its presence or absence) is definitely part of the key; we
    // should probably treat is-default-version as a non-key attribute
    //
    // defined - rather fundamental; libabigail currently doesn't track
    // undefined symbols but we should obviously be prepared in case it does

    // There are also some externalities which libabigail cares about, which may
    // or may not be exposed in the XML
    //
    // index - don't care
    //
    // is-common and friends - don't care
    //
    // aliases - exposed, but we don't really care; however we should see what
    // compilers do, if anything, in terms of propagating type information to
    // aliases

    // Linux kernel things.
    //
    // MODVERSIONS CRC - fundamental to ABI compatibility, if present
    //
    // Symbol namespace - fundamental to ABI compatibility, if present

    Result result;
    result.MaybeAddNodeDiff("name", x1.symbol_name, x2.symbol_name);

    if (x1.version_info && x2.version_info) {
      result.MaybeAddNodeDiff("version", x1.version_info->name,
                              x2.version_info->name);
      result.MaybeAddNodeDiff("default version", x1.version_info->is_default,
                              x2.version_info->is_default);
    } else {
      result.MaybeAddNodeDiff("has version", x1.version_info.has_value(),
                              x2.version_info.has_value());
    }

    result.MaybeAddNodeDiff("defined", x1.is_defined, x2.is_defined);
    result.MaybeAddNodeDiff("symbol type", x1.symbol_type, x2.symbol_type);
    result.MaybeAddNodeDiff("binding", x1.binding, x2.binding);
    result.MaybeAddNodeDiff("visibility", x1.visibility, x2.visibility);
    if (!ignore.Test(Ignore::SYMBOL_CRC)) {
      result.MaybeAddNodeDiff("CRC", x1.crc, x2.crc);
    }
    result.MaybeAddNodeDiff("namespace", x1.ns, x2.ns);

    if (x1.type_id && x2.type_id) {
      result.MaybeAddEdgeDiff("", (*this)(*x1.type_id, *x2.type_id));
    } else if (x1.type_id) {
      if (!ignore.Test(Ignore::SYMBOL_TYPE_PRESENCE)) {
        result.AddEdgeDiff("", Removed(*x1.type_id));
      }
    } else if (x2.type_id) {
      if (!ignore.Test(Ignore::SYMBOL_TYPE_PRESENCE)) {
        result.AddEdgeDiff("", Added(*x2.type_id));
      }
    } else {
      // both types missing, we have nothing to say
    }

    return result;
  }

  Result operator()(const Interface& x1, const Interface& x2) {
    Result result;
    result.diff.holds_changes = true;
    const bool ignore_added = ignore.Test(Ignore::INTERFACE_ADDITION);
    Nodes(x1.symbols, x2.symbols, ignore_added, result);
    Nodes(x1.types, x2.types, ignore_added, result);
    return result;
  }

  const Ignore ignore;
  const Graph& graph;
  Outcomes& outcomes;
  std::unordered_map<Comparison, bool, HashComparison> known;
  SCC<Comparison, HashComparison> scc;
  Counter queried;
  Counter already_compared;
  Counter being_compared;
  Counter really_compared;
  Counter equivalent;
  Counter inequivalent;
  Histogram scc_size;
};

}  // namespace

std::pair<Id, std::vector<std::string>> ResolveTypedefs(
    const Graph& graph, Id id) {
  std::pair<Id, std::vector<std::string>> result = {id, {}};
  ResolveTypedef resolve(graph, result.first, result.second);
  while (graph.Apply(resolve, result.first)) {}
  return result;
}

Comparison Compare(Runtime& runtime, Ignore ignore, const Graph& graph,
                   Id root1, Id root2, Outcomes& outcomes) {
  // The root node (Comparison{{id1}, {id2}}) must be the last node to be
  // completely visited by the SCC finder and the SCC finder state must be empty
  // on return from this function call. In particular, the returns where the SCC
  // is "open" are impossible. The remaining cases (of which one is impossible
  // for the root node) both have the same two possible return values:
  //
  // * (true, Comparison{})
  // * (false, Comparison{{id1}, {id2}}
  //
  // So the invariant value.first == (value.second == Comparison{}) holds and we
  // can unambiguously return value.second.
  return CompareWorker(runtime, ignore, graph, outcomes)(root1, root2).second;
}

}  // namespace diff
}  // namespace stg