CoverageMapping.h

Go to the documentation of this file.

//===- CoverageMapping.h - Code coverage mapping support --------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Code coverage mapping data is generated by clang and read by
// llvm-cov to show code coverage statistics for a file.
//
//===----------------------------------------------------------------------===//
 
#ifndef LLVM_PROFILEDATA_COVERAGE_COVERAGEMAPPING_H
#define LLVM_PROFILEDATA_COVERAGE_COVERAGEMAPPING_H
 
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/iterator.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Object/BuildID.h"
#include "llvm/ProfileData/Coverage/MCDCTypes.h"
#include "llvm/ProfileData/InstrProf.h"
#include "llvm/Support/Alignment.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Endian.h"
#include "llvm/Support/Error.h"
#include "llvm/Support/VirtualFileSystemFwd.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <map>
#include <memory>
#include <optional>
#include <sstream>
#include <string>
#include <system_error>
#include <utility>
#include <vector>
 
namespace llvm {
 
class IndexedInstrProfReader;
 
namespace object {
class BuildIDFetcher;
} // namespace object
 
namespace coverage {
 
class CoverageMappingReader;
struct CoverageMappingRecord;
 
enum class coveragemap_error {
  success = 0,
  eof,
  no_data_found,
  unsupported_version,
  truncated,
  malformed,
  decompression_failed,
  invalid_or_missing_arch_specifier
};
 
LLVM_ABI const std::error_category &coveragemap_category();
 
inline std::error_code make_error_code(coveragemap_error E) {
  return std::error_code(static_cast<int>(E), coveragemap_category());
}
 
class LLVM_ABI CoverageMapError : public ErrorInfo<CoverageMapError> {
public:
  CoverageMapError(coveragemap_error Err, const Twine &ErrStr = Twine())
      : Err(Err), Msg(ErrStr.str()) {
    assert(Err != coveragemap_error::success && "Not an error");
  }
 
  std::string message() const override;
 
  void log(raw_ostream &OS) const override { OS << message(); }
 
  std::error_code convertToErrorCode() const override {
    return make_error_code(Err);
  }
 
  coveragemap_error get() const { return Err; }
  const std::string &getMessage() const { return Msg; }
 
  static char ID;
 
private:
  coveragemap_error Err;
  std::string Msg;
};
 
/// A Counter is an abstract value that describes how to compute the
/// execution count for a region of code using the collected profile count data.
struct Counter {
  /// The CounterExpression kind (Add or Subtract) is encoded in bit 0 next to
  /// the CounterKind. This means CounterKind has to leave bit 0 free.
  enum CounterKind { Zero, CounterValueReference, Expression };
  static const unsigned EncodingTagBits = 2;
  static const unsigned EncodingTagMask = 0x3;
  static const unsigned EncodingCounterTagAndExpansionRegionTagBits =
      EncodingTagBits + 1;
 
private:
  CounterKind Kind = Zero;
  unsigned ID = 0;
 
  Counter(CounterKind Kind, unsigned ID) : Kind(Kind), ID(ID) {}
 
public:
  Counter() = default;
 
  CounterKind getKind() const { return Kind; }
 
  bool isZero() const { return Kind == Zero; }
 
  bool isExpression() const { return Kind == Expression; }
 
  unsigned getCounterID() const { return ID; }
 
  unsigned getExpressionID() const { return ID; }
 
  friend bool operator==(const Counter &LHS, const Counter &RHS) {
    return LHS.Kind == RHS.Kind && LHS.ID == RHS.ID;
  }
 
  friend bool operator!=(const Counter &LHS, const Counter &RHS) {
    return !(LHS == RHS);
  }
 
  friend bool operator<(const Counter &LHS, const Counter &RHS) {
    return std::tie(LHS.Kind, LHS.ID) < std::tie(RHS.Kind, RHS.ID);
  }
 
  /// Return the counter that represents the number zero.
  static Counter getZero() { return Counter(); }
 
  /// Return the counter that corresponds to a specific profile counter.
  static Counter getCounter(unsigned CounterId) {
    return Counter(CounterValueReference, CounterId);
  }
 
  /// Return the counter that corresponds to a specific addition counter
  /// expression.
  static Counter getExpression(unsigned ExpressionId) {
    return Counter(Expression, ExpressionId);
  }
};
 
/// A Counter expression is a value that represents an arithmetic operation
/// with two counters.
struct CounterExpression {
  enum ExprKind { Subtract, Add };
  ExprKind Kind;
  Counter LHS, RHS;
 
  CounterExpression(ExprKind Kind, Counter LHS, Counter RHS)
      : Kind(Kind), LHS(LHS), RHS(RHS) {}
};
 
/// A Counter expression builder is used to construct the counter expressions.
/// It avoids unnecessary duplication and simplifies algebraic expressions.
class CounterExpressionBuilder {
  /// A list of all the counter expressions
  std::vector<CounterExpression> Expressions;
 
  /// A lookup table for the index of a given expression.
  DenseMap<CounterExpression, unsigned> ExpressionIndices;
 
  /// Return the counter which corresponds to the given expression.
  ///
  /// If the given expression is already stored in the builder, a counter
  /// that references that expression is returned. Otherwise, the given
  /// expression is added to the builder's collection of expressions.
  Counter get(const CounterExpression &E);
 
  /// Represents a term in a counter expression tree.
  struct Term {
    unsigned CounterID;
    int Factor;
 
    Term(unsigned CounterID, int Factor)
        : CounterID(CounterID), Factor(Factor) {}
  };
 
  /// Gather the terms of the expression tree for processing.
  ///
  /// This collects each addition and subtraction referenced by the counter into
  /// a sequence that can be sorted and combined to build a simplified counter
  /// expression.
  void extractTerms(Counter C, int Sign, SmallVectorImpl<Term> &Terms);
 
  /// Simplifies the given expression tree
  /// by getting rid of algebraically redundant operations.
  Counter simplify(Counter ExpressionTree);
 
public:
  ArrayRef<CounterExpression> getExpressions() const { return Expressions; }
 
  /// Return a counter that represents the expression that adds LHS and RHS.
  LLVM_ABI Counter add(Counter LHS, Counter RHS, bool Simplify = true);
 
  /// Return a counter that represents the expression that subtracts RHS from
  /// LHS.
  LLVM_ABI Counter subtract(Counter LHS, Counter RHS, bool Simplify = true);
 
  /// K to V map. K will be Counter in most cases. V may be Counter or
  /// Expression.
  using SubstMap = std::map<Counter, Counter>;
 
  /// \return A counter equivalent to \C, with each term in its
  /// expression replaced with term from \p Map.
  LLVM_ABI Counter subst(Counter C, const SubstMap &Map);
};
 
using LineColPair = std::pair<unsigned, unsigned>;
 
/// A Counter mapping region associates a source range with a specific counter.
struct CounterMappingRegion {
  enum RegionKind {
    /// A CodeRegion associates some code with a counter
    CodeRegion,
 
    /// An ExpansionRegion represents a file expansion region that associates
    /// a source range with the expansion of a virtual source file, such as
    /// for a macro instantiation or #include file.
    ExpansionRegion,
 
    /// A SkippedRegion represents a source range with code that was skipped
    /// by a preprocessor or similar means.
    SkippedRegion,
 
    /// A GapRegion is like a CodeRegion, but its count is only set as the
    /// line execution count when its the only region in the line.
    GapRegion,
 
    /// A BranchRegion represents leaf-level boolean expressions and is
    /// associated with two counters, each representing the number of times the
    /// expression evaluates to true or false.
    BranchRegion,
 
    /// A DecisionRegion represents a top-level boolean expression and is
    /// associated with a variable length bitmap index and condition number.
    MCDCDecisionRegion,
 
    /// A Branch Region can be extended to include IDs to facilitate MC/DC.
    MCDCBranchRegion
  };
 
  /// Primary Counter that is also used for Branch Regions (TrueCount).
  Counter Count;
 
  /// Secondary Counter used for Branch Regions (FalseCount).
  Counter FalseCount;
 
  /// Parameters used for Modified Condition/Decision Coverage
  mcdc::Parameters MCDCParams;
 
  const auto &getDecisionParams() const {
    return mcdc::getParams<const mcdc::DecisionParameters>(MCDCParams);
  }
 
  const auto &getBranchParams() const {
    return mcdc::getParams<const mcdc::BranchParameters>(MCDCParams);
  }
 
  unsigned FileID = 0;
  unsigned ExpandedFileID = 0;
  unsigned LineStart, ColumnStart, LineEnd, ColumnEnd;
 
  RegionKind Kind;
 
  bool isBranch() const {
    return (Kind == BranchRegion || Kind == MCDCBranchRegion);
  }
 
  CounterMappingRegion(Counter Count, unsigned FileID, unsigned ExpandedFileID,
                       unsigned LineStart, unsigned ColumnStart,
                       unsigned LineEnd, unsigned ColumnEnd, RegionKind Kind)
      : Count(Count), FileID(FileID), ExpandedFileID(ExpandedFileID),
        LineStart(LineStart), ColumnStart(ColumnStart), LineEnd(LineEnd),
        ColumnEnd(ColumnEnd), Kind(Kind) {}
 
  CounterMappingRegion(Counter Count, Counter FalseCount, unsigned FileID,
                       unsigned ExpandedFileID, unsigned LineStart,
                       unsigned ColumnStart, unsigned LineEnd,
                       unsigned ColumnEnd, RegionKind Kind,
                       const mcdc::Parameters &MCDCParams = std::monostate())
      : Count(Count), FalseCount(FalseCount), MCDCParams(MCDCParams),
        FileID(FileID), ExpandedFileID(ExpandedFileID), LineStart(LineStart),
        ColumnStart(ColumnStart), LineEnd(LineEnd), ColumnEnd(ColumnEnd),
        Kind(Kind) {}
 
  CounterMappingRegion(const mcdc::DecisionParameters &MCDCParams,
                       unsigned FileID, unsigned LineStart,
                       unsigned ColumnStart, unsigned LineEnd,
                       unsigned ColumnEnd, RegionKind Kind)
      : MCDCParams(MCDCParams), FileID(FileID), LineStart(LineStart),
        ColumnStart(ColumnStart), LineEnd(LineEnd), ColumnEnd(ColumnEnd),
        Kind(Kind) {}
 
  static CounterMappingRegion
  makeRegion(Counter Count, unsigned FileID, unsigned LineStart,
             unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) {
    return CounterMappingRegion(Count, FileID, 0, LineStart, ColumnStart,
                                LineEnd, ColumnEnd, CodeRegion);
  }
 
  static CounterMappingRegion
  makeExpansion(unsigned FileID, unsigned ExpandedFileID, unsigned LineStart,
                unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) {
    return CounterMappingRegion(Counter(), FileID, ExpandedFileID, LineStart,
                                ColumnStart, LineEnd, ColumnEnd,
                                ExpansionRegion);
  }
 
  static CounterMappingRegion
  makeSkipped(unsigned FileID, unsigned LineStart, unsigned ColumnStart,
              unsigned LineEnd, unsigned ColumnEnd) {
    return CounterMappingRegion(Counter(), FileID, 0, LineStart, ColumnStart,
                                LineEnd, ColumnEnd, SkippedRegion);
  }
 
  static CounterMappingRegion
  makeGapRegion(Counter Count, unsigned FileID, unsigned LineStart,
                unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) {
    return CounterMappingRegion(Count, FileID, 0, LineStart, ColumnStart,
                                LineEnd, (1U << 31) | ColumnEnd, GapRegion);
  }
 
  static CounterMappingRegion
  makeBranchRegion(Counter Count, Counter FalseCount, unsigned FileID,
                   unsigned LineStart, unsigned ColumnStart, unsigned LineEnd,
                   unsigned ColumnEnd,
                   const mcdc::Parameters &MCDCParams = std::monostate()) {
    return CounterMappingRegion(
        Count, FalseCount, FileID, 0, LineStart, ColumnStart, LineEnd,
        ColumnEnd,
        (std::get_if<mcdc::BranchParameters>(&MCDCParams) ? MCDCBranchRegion
                                                          : BranchRegion),
        MCDCParams);
  }
 
  static CounterMappingRegion
  makeDecisionRegion(const mcdc::DecisionParameters &MCDCParams,
                     unsigned FileID, unsigned LineStart, unsigned ColumnStart,
                     unsigned LineEnd, unsigned ColumnEnd) {
    return CounterMappingRegion(MCDCParams, FileID, LineStart, ColumnStart,
                                LineEnd, ColumnEnd, MCDCDecisionRegion);
  }
 
  inline LineColPair startLoc() const {
    return LineColPair(LineStart, ColumnStart);
  }
 
  inline LineColPair endLoc() const { return LineColPair(LineEnd, ColumnEnd); }
};
 
/// Associates a source range with an execution count.
struct CountedRegion : public CounterMappingRegion {
  uint64_t ExecutionCount;
  uint64_t FalseExecutionCount;
  bool TrueFolded;
  bool FalseFolded;
 
  CountedRegion(const CounterMappingRegion &R, uint64_t ExecutionCount)
      : CounterMappingRegion(R), ExecutionCount(ExecutionCount),
        FalseExecutionCount(0), TrueFolded(false), FalseFolded(true) {}
 
  CountedRegion(const CounterMappingRegion &R, uint64_t ExecutionCount,
                uint64_t FalseExecutionCount)
      : CounterMappingRegion(R), ExecutionCount(ExecutionCount),
        FalseExecutionCount(FalseExecutionCount), TrueFolded(false),
        FalseFolded(false) {}
};
 
/// MCDC Record grouping all information together.
struct MCDCRecord {
  /// CondState represents the evaluation of a condition in an executed test
  /// vector, which can be True or False. A DontCare is used to mask an
  /// unevaluatable condition resulting from short-circuit behavior of logical
  /// operators in languages like C/C++. When comparing the evaluation of a
  /// condition across executed test vectors, comparisons against a DontCare
  /// are effectively ignored.
  enum CondState { MCDC_DontCare = -1, MCDC_False = 0, MCDC_True = 1 };
 
  /// Emulate SmallVector<CondState> with a pair of BitVector.
  ///
  ///          True  False DontCare (Impossible)
  /// Values:  True  False False    True
  /// Visited: True  True  False    False
  class TestVector {
    BitVector Values;  /// True/False (False when DontCare)
    BitVector Visited; /// ~DontCare
 
  public:
    /// Default values are filled with DontCare.
    TestVector(unsigned N) : Values(N), Visited(N) {}
 
    /// Emulate RHS SmallVector::operator[]
    CondState operator[](int I) const {
      return (Visited[I] ? (Values[I] ? MCDC_True : MCDC_False)
                         : MCDC_DontCare);
    }
 
    /// Equivalent to buildTestVector's Index.
    auto getIndex() const { return Values.getData()[0]; }
 
    /// Set the condition \p Val at position \p I.
    /// This emulates LHS SmallVector::operator[].
    void set(int I, CondState Val) {
      Visited[I] = (Val != MCDC_DontCare);
      Values[I] = (Val == MCDC_True);
    }
 
    /// Emulate SmallVector::push_back.
    void push_back(CondState Val) {
      Visited.push_back(Val != MCDC_DontCare);
      Values.push_back(Val == MCDC_True);
      assert(Values.size() == Visited.size());
    }
 
    /// For each element:
    /// - False if either is DontCare
    /// - False if both have the same value
    /// - True if both have the opposite value
    /// ((A.Values ^ B.Values) & A.Visited & B.Visited)
    /// Dedicated to findIndependencePairs().
    auto getDifferences(const TestVector &B) const {
      const auto &A = *this;
      BitVector AB = A.Values;
      AB ^= B.Values;
      AB &= A.Visited;
      AB &= B.Visited;
      return AB;
    }
  };
 
  using TestVectors = llvm::SmallVector<std::pair<TestVector, CondState>>;
  using BoolVector = std::array<BitVector, 2>;
  using TVRowPair = std::pair<unsigned, unsigned>;
  using TVPairMap = llvm::DenseMap<unsigned, TVRowPair>;
  using CondIDMap = llvm::DenseMap<unsigned, unsigned>;
  using LineColPairMap = llvm::DenseMap<unsigned, LineColPair>;
 
private:
  CounterMappingRegion Region;
  TestVectors TV;
  TestVectors NotExecutedTV;
  std::optional<TVPairMap> IndependencePairs;
  BoolVector Folded;
  CondIDMap PosToID;
  LineColPairMap CondLoc;
 
  std::string formatTestVectorRow(const TestVector &Vec, CondState Result,
                                  unsigned DisplayRowNumber) const {
    std::ostringstream OS;
    const auto NumConditions = getNumConditions();
    // Add individual condition values to the string.
    OS << "  " << DisplayRowNumber << " { ";
    for (unsigned Condition = 0; Condition < NumConditions; Condition++) {
      if (isCondFolded(Condition))
        OS << "C";
      else {
        auto It = PosToID.find(Condition);
        assert(It != PosToID.end() && "Ordinal without CondID mapping");
        switch (Vec[It->second]) {
        case MCDC_DontCare:
          OS << "-";
          break;
        case MCDC_True:
          OS << "T";
          break;
        case MCDC_False:
          OS << "F";
          break;
        }
      }
      if (Condition != NumConditions - 1)
        OS << ",  ";
    }
 
    // Add result value to the string.
    OS << "  = ";
    if (Result == MCDC_True)
      OS << "T";
    else
      OS << "F";
    OS << "      }\n";
    return OS.str();
  }
 
public:
  MCDCRecord(const CounterMappingRegion &Region, TestVectors &&TV,
             TestVectors &&NotExecutedTV, BoolVector &&Folded,
             CondIDMap &&PosToID, LineColPairMap &&CondLoc)
      : Region(Region), TV(std::move(TV)),
        NotExecutedTV(std::move(NotExecutedTV)), Folded(std::move(Folded)),
        PosToID(std::move(PosToID)), CondLoc(std::move(CondLoc)) {
    findIndependencePairs();
  }
 
  // Compare executed test vectors against each other to find an independence
  // pairs for each condition.  This processing takes the most time.
  LLVM_ABI void findIndependencePairs();
 
  const CounterMappingRegion &getDecisionRegion() const { return Region; }
  unsigned getNumConditions() const {
    return Region.getDecisionParams().NumConditions;
  }
  unsigned getNumTestVectors() const { return TV.size(); }
  unsigned getNumNotExecutedTestVectors() const { return NotExecutedTV.size(); }
 
  bool isCondFolded(unsigned Condition) const {
    return Folded[false][Condition] || Folded[true][Condition];
  }
 
  /// Return the evaluation of a condition (indicated by Condition) in an
  /// executed test vector (indicated by TestVectorIndex), which will be True,
  /// False, or DontCare if the condition is unevaluatable. Because condition
  /// IDs are not associated based on their position in the expression,
  /// accessing conditions in the TestVectors requires a translation from a
  /// ordinal position to actual condition ID. This is done via PosToID[].
  CondState getTVCondition(unsigned TestVectorIndex, unsigned Condition) {
    return TV[TestVectorIndex].first[PosToID[Condition]];
  }
 
  CondState getNotExecutedTVCondition(unsigned NotExecutedIndex,
                                      unsigned Condition) {
    return NotExecutedTV[NotExecutedIndex].first[PosToID[Condition]];
  }
 
  /// Return the number of True and False decisions for all executed test
  /// vectors.
  std::pair<unsigned, unsigned> getDecisions() const {
    const unsigned TrueDecisions =
        llvm::count(llvm::make_second_range(TV), CondState::MCDC_True);
 
    return {TrueDecisions, TV.size() - TrueDecisions};
  }
 
  /// Return the Result evaluation for an executed test vector.
  /// See MCDCRecordProcessor::RecordTestVector().
  CondState getTVResult(unsigned TestVectorIndex) {
    return TV[TestVectorIndex].second;
  }
 
  CondState getNotExecutedTVResult(unsigned NotExecutedIndex) {
    return NotExecutedTV[NotExecutedIndex].second;
  }
 
  /// Determine whether a given condition (indicated by Condition) is covered
  /// by an Independence Pair. Because condition IDs are not associated based
  /// on their position in the expression, accessing conditions in the
  /// TestVectors requires a translation from a ordinal position to actual
  /// condition ID. This is done via PosToID[].
  bool isConditionIndependencePairCovered(unsigned Condition) const {
    assert(IndependencePairs);
    auto It = PosToID.find(Condition);
    assert(It != PosToID.end() && "Condition ID without an Ordinal mapping");
    return IndependencePairs->contains(It->second);
  }
 
  /// Return the Independence Pair that covers the given condition. Because
  /// condition IDs are not associated based on their position in the
  /// expression, accessing conditions in the TestVectors requires a
  /// translation from a ordinal position to actual condition ID. This is done
  /// via PosToID[].
  TVRowPair getConditionIndependencePair(unsigned Condition) {
    assert(isConditionIndependencePairCovered(Condition));
    assert(IndependencePairs);
    return (*IndependencePairs)[PosToID[Condition]];
  }
 
  float getPercentCovered() const {
    unsigned Folded = 0;
    unsigned Covered = 0;
    for (unsigned C = 0; C < getNumConditions(); C++) {
      if (isCondFolded(C))
        Folded++;
      else if (isConditionIndependencePairCovered(C))
        Covered++;
    }
 
    unsigned Total = getNumConditions() - Folded;
    if (Total == 0)
      return 0.0;
    return (static_cast<double>(Covered) / static_cast<double>(Total)) * 100.0;
  }
 
  std::string getConditionHeaderString(unsigned Condition) {
    std::ostringstream OS;
    const auto &[Line, Col] = CondLoc[Condition];
    OS << "Condition C" << Condition + 1 << " --> (" << Line << ":" << Col
       << ")\n";
    return OS.str();
  }
 
  std::string getTestVectorHeaderString() const {
    std::ostringstream OS;
    if (getNumTestVectors() == 0 && getNumNotExecutedTestVectors() == 0) {
      OS << "None.\n";
      return OS.str();
    }
    const auto NumConditions = getNumConditions();
    for (unsigned I = 0; I < NumConditions; I++) {
      OS << "C" << I + 1;
      if (I != NumConditions - 1)
        OS << ", ";
    }
    OS << "    Result\n";
    return OS.str();
  }
 
  std::string getTestVectorString(unsigned TestVectorIndex) {
    assert(TestVectorIndex < getNumTestVectors() &&
           "TestVector index out of bounds!");
    const auto &[Vec, Res] = TV[TestVectorIndex];
    return formatTestVectorRow(Vec, Res, TestVectorIndex + 1);
  }
 
  std::string getNotExecutedTestVectorString(unsigned NotExecutedIndex) {
    assert(NotExecutedIndex < getNumNotExecutedTestVectors() &&
           "Not-executed test vector index out of bounds!");
    const auto &[Vec, Res] = NotExecutedTV[NotExecutedIndex];
    return formatTestVectorRow(Vec, Res,
                               getNumTestVectors() + NotExecutedIndex + 1);
  }
 
  std::string getConditionCoverageString(unsigned Condition) {
    assert(Condition < getNumConditions() &&
           "Condition index is out of bounds!");
    std::ostringstream OS;
 
    OS << "  C" << Condition + 1 << "-Pair: ";
    if (isCondFolded(Condition)) {
      OS << "constant folded\n";
    } else if (isConditionIndependencePairCovered(Condition)) {
      TVRowPair rows = getConditionIndependencePair(Condition);
      OS << "covered: (" << rows.first << ",";
      OS << rows.second << ")\n";
    } else
      OS << "not covered\n";
 
    return OS.str();
  }
};
 
namespace mcdc {
/// Compute TestVector Indices "TVIdx" from the Conds graph.
///
/// Clang CodeGen handles the bitmap index based on TVIdx.
/// llvm-cov reconstructs conditions from TVIdx.
///
/// For each leaf "The final decision",
/// - TVIdx should be unique.
/// - TVIdx has the Width.
///   - The width represents the number of possible paths.
///   - The minimum width is 1 "deterministic".
/// - The order of leaves are sorted by Width DESC. It expects
///   latter TVIdx(s) (with Width=1) could be pruned and altered to
///   other simple branch conditions.
///
class TVIdxBuilder {
public:
  struct MCDCNode {
    int InCount = 0; /// Reference count; temporary use
    int Width;       /// Number of accumulated paths (>= 1)
    ConditionIDs NextIDs;
  };
 
#ifndef NDEBUG
  /// This is no longer needed after the assignment.
  /// It may be used in assert() for reconfirmation.
  SmallVector<MCDCNode> SavedNodes;
#endif
 
  /// Output: Index for TestVectors bitmap (These are not CondIDs)
  SmallVector<std::array<int, 2>> Indices;
 
  /// Output: The number of test vectors.
  /// Error with HardMaxTVs if the number has exploded.
  int NumTestVectors;
 
  /// Hard limit of test vectors
  static constexpr auto HardMaxTVs =
      std::numeric_limits<decltype(NumTestVectors)>::max();
 
public:
  /// Calculate and assign Indices
  /// \param NextIDs The list of {FalseID, TrueID} indexed by ID
  ///        The first element [0] should be the root node.
  /// \param Offset Offset of index to final decisions.
  LLVM_ABI TVIdxBuilder(const SmallVectorImpl<ConditionIDs> &NextIDs,
                        int Offset = 0);
};
} // namespace mcdc
 
/// A Counter mapping context is used to connect the counters, expressions
/// and the obtained counter values.
class CounterMappingContext {
  ArrayRef<CounterExpression> Expressions;
  ArrayRef<uint64_t> CounterValues;
  BitVector Bitmap;
 
public:
  CounterMappingContext(ArrayRef<CounterExpression> Expressions,
                        ArrayRef<uint64_t> CounterValues = {})
      : Expressions(Expressions), CounterValues(CounterValues) {}
 
  void setCounts(ArrayRef<uint64_t> Counts) { CounterValues = Counts; }
  void setBitmap(BitVector &&Bitmap_) { Bitmap = std::move(Bitmap_); }
 
  LLVM_ABI void dump(const Counter &C, raw_ostream &OS) const;
  void dump(const Counter &C) const { dump(C, dbgs()); }
 
  /// Return the number of times that a region of code associated with this
  /// counter was executed.
  LLVM_ABI Expected<int64_t> evaluate(const Counter &C) const;
 
  /// Return an MCDC record that indicates executed test vectors and condition
  /// pairs.
  LLVM_ABI Expected<MCDCRecord>
  evaluateMCDCRegion(const CounterMappingRegion &Region,
                     ArrayRef<const CounterMappingRegion *> Branches,
                     bool IsVersion11);
 
  LLVM_ABI unsigned getMaxCounterID(const Counter &C) const;
};
 
/// Code coverage information for a single function.
struct FunctionRecord {
  /// Raw function name.
  std::string Name;
  /// Mapping from FileID (i.e. vector index) to filename. Used to support
  /// macro expansions within a function in which the macro and function are
  /// defined in separate files.
  ///
  /// TODO: Uniquing filenames across all function records may be a performance
  /// optimization.
  std::vector<std::string> Filenames;
  /// Regions in the function along with their counts.
  std::vector<CountedRegion> CountedRegions;
  /// Branch Regions in the function along with their counts.
  std::vector<CountedRegion> CountedBranchRegions;
  /// MCDC Records record a DecisionRegion and associated BranchRegions.
  std::vector<MCDCRecord> MCDCRecords;
  /// The number of times this function was executed.
  uint64_t ExecutionCount = 0;
 
  FunctionRecord(StringRef Name, ArrayRef<StringRef> Filenames)
      : Name(Name), Filenames(Filenames.begin(), Filenames.end()) {}
 
  FunctionRecord(FunctionRecord &&FR) = default;
  FunctionRecord &operator=(FunctionRecord &&) = default;
 
  void pushMCDCRecord(MCDCRecord &&Record) {
    MCDCRecords.push_back(std::move(Record));
  }
 
  void pushRegion(CounterMappingRegion Region, uint64_t Count,
                  uint64_t FalseCount) {
    if (Region.isBranch()) {
      CountedBranchRegions.emplace_back(Region, Count, FalseCount);
      // If either counter is hard-coded to zero, then this region represents a
      // constant-folded branch.
      CountedBranchRegions.back().TrueFolded = Region.Count.isZero();
      CountedBranchRegions.back().FalseFolded = Region.FalseCount.isZero();
      return;
    }
    if (CountedRegions.empty())
      ExecutionCount = Count;
    CountedRegions.emplace_back(Region, Count, FalseCount);
  }
};
 
/// Iterator over Functions, optionally filtered to a single file.
/// When filtering to a single file, the iterator requires a list of potential
/// indices where to find the desired records to avoid quadratic behavior when
/// repeatedly iterating over functions from different files.
class FunctionRecordIterator
    : public iterator_facade_base<FunctionRecordIterator,
                                  std::forward_iterator_tag, FunctionRecord> {
  ArrayRef<FunctionRecord> Records;
  ArrayRef<unsigned> RecordIndices;
  ArrayRef<unsigned>::iterator CurrentIndex;
  ArrayRef<FunctionRecord>::iterator Current;
  StringRef Filename;
 
  /// Skip records whose primary file is not \c Filename.
  LLVM_ABI void skipOtherFiles();
 
public:
  FunctionRecordIterator(ArrayRef<FunctionRecord> Records_,
                         StringRef Filename = "",
                         ArrayRef<unsigned> RecordIndices_ = {})
      : Records(Records_), RecordIndices(RecordIndices_),
        CurrentIndex(RecordIndices.begin()),
        // If `RecordIndices` is provided, we can skip directly to the first
        // index it provides.
        Current(CurrentIndex == RecordIndices.end() ? Records.begin()
                                                    : &Records[*CurrentIndex]),
        Filename(Filename) {
    assert(Filename.empty() == RecordIndices_.empty() &&
           "If `Filename` is specified, `RecordIndices` must also be provided");
    skipOtherFiles();
  }
 
  FunctionRecordIterator() : Current(Records.begin()) {}
 
  bool operator==(const FunctionRecordIterator &RHS) const {
    return Current == RHS.Current && Filename == RHS.Filename;
  }
 
  const FunctionRecord &operator*() const { return *Current; }
 
  FunctionRecordIterator &operator++() {
    advanceOne();
    skipOtherFiles();
    return *this;
  }
 
private:
  void advanceOne() {
    if (RecordIndices.empty()) {
      // Iteration over all entries, advance in the list of records.
      assert(Current != Records.end() && "incremented past end");
      ++Current;
    } else {
      // Iterator over entries filtered by file name. Advance in the list of
      // indices, and adjust the cursor in the list of records accordingly.
      assert(CurrentIndex != RecordIndices.end() && "incremented past end");
      ++CurrentIndex;
      if (CurrentIndex == RecordIndices.end()) {
        Current = Records.end();
      } else {
        Current = &Records[*CurrentIndex];
      }
    }
  }
};
 
/// Coverage information for a macro expansion or #included file.
///
/// When covered code has pieces that can be expanded for more detail, such as a
/// preprocessor macro use and its definition, these are represented as
/// expansions whose coverage can be looked up independently.
struct ExpansionRecord {
  /// The abstract file this expansion covers.
  unsigned FileID;
  /// The region that expands to this record.
  const CountedRegion &Region;
  /// Coverage for the expansion.
  const FunctionRecord &Function;
 
  ExpansionRecord(const CountedRegion &Region,
                  const FunctionRecord &Function)
      : FileID(Region.ExpandedFileID), Region(Region), Function(Function) {}
};
 
/// The execution count information starting at a point in a file.
///
/// A sequence of CoverageSegments gives execution counts for a file in format
/// that's simple to iterate through for processing.
struct CoverageSegment {
  /// The line where this segment begins.
  unsigned Line;
  /// The column where this segment begins.
  unsigned Col;
  /// The execution count, or zero if no count was recorded.
  uint64_t Count;
  /// When false, the segment was uninstrumented or skipped.
  bool HasCount;
  /// Whether this enters a new region or returns to a previous count.
  bool IsRegionEntry;
  /// Whether this enters a gap region.
  bool IsGapRegion;
 
  CoverageSegment(unsigned Line, unsigned Col, bool IsRegionEntry)
      : Line(Line), Col(Col), Count(0), HasCount(false),
        IsRegionEntry(IsRegionEntry), IsGapRegion(false) {}
 
  CoverageSegment(unsigned Line, unsigned Col, uint64_t Count,
                  bool IsRegionEntry, bool IsGapRegion = false,
                  bool IsBranchRegion = false)
      : Line(Line), Col(Col), Count(Count), HasCount(true),
        IsRegionEntry(IsRegionEntry), IsGapRegion(IsGapRegion) {}
 
  friend bool operator==(const CoverageSegment &L, const CoverageSegment &R) {
    return std::tie(L.Line, L.Col, L.Count, L.HasCount, L.IsRegionEntry,
                    L.IsGapRegion) == std::tie(R.Line, R.Col, R.Count,
                                               R.HasCount, R.IsRegionEntry,
                                               R.IsGapRegion);
  }
};
 
/// An instantiation group contains a \c FunctionRecord list, such that each
/// record corresponds to a distinct instantiation of the same function.
///
/// Note that it's possible for a function to have more than one instantiation
/// (consider C++ template specializations or static inline functions).
class InstantiationGroup {
  friend class CoverageMapping;
 
  unsigned Line;
  unsigned Col;
  std::vector<const FunctionRecord *> Instantiations;
 
  InstantiationGroup(unsigned Line, unsigned Col,
                     std::vector<const FunctionRecord *> Instantiations)
      : Line(Line), Col(Col), Instantiations(std::move(Instantiations)) {}
 
public:
  InstantiationGroup(const InstantiationGroup &) = delete;
  InstantiationGroup(InstantiationGroup &&) = default;
 
  /// Get the number of instantiations in this group.
  size_t size() const { return Instantiations.size(); }
 
  /// Get the line where the common function was defined.
  unsigned getLine() const { return Line; }
 
  /// Get the column where the common function was defined.
  unsigned getColumn() const { return Col; }
 
  /// Check if the instantiations in this group have a common mangled name.
  bool hasName() const {
    for (unsigned I = 1, E = Instantiations.size(); I < E; ++I)
      if (Instantiations[I]->Name != Instantiations[0]->Name)
        return false;
    return true;
  }
 
  /// Get the common mangled name for instantiations in this group.
  StringRef getName() const {
    assert(hasName() && "Instantiations don't have a shared name");
    return Instantiations[0]->Name;
  }
 
  /// Get the total execution count of all instantiations in this group.
  uint64_t getTotalExecutionCount() const {
    uint64_t Count = 0;
    for (const FunctionRecord *F : Instantiations)
      Count += F->ExecutionCount;
    return Count;
  }
 
  /// Get the instantiations in this group.
  ArrayRef<const FunctionRecord *> getInstantiations() const {
    return Instantiations;
  }
};
 
/// Coverage information to be processed or displayed.
///
/// This represents the coverage of an entire file, expansion, or function. It
/// provides a sequence of CoverageSegments to iterate through, as well as the
/// list of expansions that can be further processed.
class CoverageData {
  friend class CoverageMapping;
 
protected:
  std::string Filename;
  std::vector<CoverageSegment> Segments;
  std::vector<ExpansionRecord> Expansions;
  std::vector<CountedRegion> BranchRegions;
  std::vector<MCDCRecord> MCDCRecords;
 
  bool SingleByteCoverage = false;
 
public:
  CoverageData() = default;
 
  CoverageData(bool Single, StringRef Filename)
      : Filename(Filename), SingleByteCoverage(Single) {}
 
  CoverageData(CoverageData &&RHS) = default;
 
  /// Get the name of the file this data covers.
  StringRef getFilename() const { return Filename; }
 
  bool getSingleByteCoverage() const { return SingleByteCoverage; }
 
  /// Get an iterator over the coverage segments for this object. The segments
  /// are guaranteed to be uniqued and sorted by location.
  std::vector<CoverageSegment>::const_iterator begin() const {
    return Segments.begin();
  }
 
  std::vector<CoverageSegment>::const_iterator end() const {
    return Segments.end();
  }
 
  bool empty() const { return Segments.empty(); }
 
  /// Expansions that can be further processed.
  ArrayRef<ExpansionRecord> getExpansions() const { return Expansions; }
 
  /// Branches that can be further processed.
  ArrayRef<CountedRegion> getBranches() const { return BranchRegions; }
 
  /// MCDC Records that can be further processed.
  ArrayRef<MCDCRecord> getMCDCRecords() const { return MCDCRecords; }
};
 
/// The mapping of profile information to coverage data.
///
/// This is the main interface to get coverage information, using a profile to
/// fill out execution counts.
class CoverageMapping {
  DenseMap<size_t, DenseSet<size_t>> RecordProvenance;
  std::vector<FunctionRecord> Functions;
  DenseMap<size_t, SmallVector<unsigned, 0>> FilenameHash2RecordIndices;
  std::vector<std::pair<std::string, uint64_t>> FuncHashMismatches;
 
  std::optional<bool> SingleByteCoverage;
 
  CoverageMapping() = default;
 
  // Load coverage records from readers.
  static Error loadFromReaders(
      ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders,
      std::optional<std::reference_wrapper<IndexedInstrProfReader>>
          &ProfileReader,
      CoverageMapping &Coverage);
 
  // Load coverage records from file.
  static Error
  loadFromFile(StringRef Filename, StringRef Arch, StringRef CompilationDir,
               std::optional<std::reference_wrapper<IndexedInstrProfReader>>
                   &ProfileReader,
               CoverageMapping &Coverage, bool &DataFound,
               SmallVectorImpl<object::BuildID> *FoundBinaryIDs = nullptr);
 
  /// Add a function record corresponding to \p Record.
  Error loadFunctionRecord(
      const CoverageMappingRecord &Record,
      const std::optional<std::reference_wrapper<IndexedInstrProfReader>>
          &ProfileReader);
 
  /// Look up the indices for function records which are at least partially
  /// defined in the specified file. This is guaranteed to return a superset of
  /// such records: extra records not in the file may be included if there is
  /// a hash collision on the filename. Clients must be robust to collisions.
  LLVM_ABI ArrayRef<unsigned>
  getImpreciseRecordIndicesForFilename(StringRef Filename) const;
 
public:
  CoverageMapping(const CoverageMapping &) = delete;
  CoverageMapping &operator=(const CoverageMapping &) = delete;
 
  /// Load the coverage mapping using the given readers.
  LLVM_ABI static Expected<std::unique_ptr<CoverageMapping>>
  load(ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders,
       std::optional<std::reference_wrapper<IndexedInstrProfReader>>
           &ProfileReader);
 
  /// Load the coverage mapping from the given object files and profile. If
  /// \p Arches is non-empty, it must specify an architecture for each object.
  /// Ignores non-instrumented object files unless all are not instrumented.
  LLVM_ABI static Expected<std::unique_ptr<CoverageMapping>>
  load(ArrayRef<StringRef> ObjectFilenames,
       std::optional<StringRef> ProfileFilename, vfs::FileSystem &FS,
       ArrayRef<StringRef> Arches = {}, StringRef CompilationDir = "",
       const object::BuildIDFetcher *BIDFetcher = nullptr,
       bool CheckBinaryIDs = false);
 
  /// The number of functions that couldn't have their profiles mapped.
  ///
  /// This is a count of functions whose profile is out of date or otherwise
  /// can't be associated with any coverage information.
  unsigned getMismatchedCount() const { return FuncHashMismatches.size(); }
 
  /// A hash mismatch occurs when a profile record for a symbol does not have
  /// the same hash as a coverage mapping record for the same symbol. This
  /// returns a list of hash mismatches, where each mismatch is a pair of the
  /// symbol name and its coverage mapping hash.
  ArrayRef<std::pair<std::string, uint64_t>> getHashMismatches() const {
    return FuncHashMismatches;
  }
 
  /// Returns a lexicographically sorted, unique list of files that are
  /// covered.
  LLVM_ABI std::vector<StringRef> getUniqueSourceFiles() const;
 
  /// Get the coverage for a particular file.
  ///
  /// The given filename must be the name as recorded in the coverage
  /// information. That is, only names returned from getUniqueSourceFiles will
  /// yield a result.
  LLVM_ABI CoverageData getCoverageForFile(StringRef Filename) const;
 
  /// Get the coverage for a particular function.
  LLVM_ABI CoverageData
  getCoverageForFunction(const FunctionRecord &Function) const;
 
  /// Get the coverage for an expansion within a coverage set.
  LLVM_ABI CoverageData
  getCoverageForExpansion(const ExpansionRecord &Expansion) const;
 
  /// Gets all of the functions covered by this profile.
  iterator_range<FunctionRecordIterator> getCoveredFunctions() const {
    return make_range(FunctionRecordIterator(Functions),
                      FunctionRecordIterator());
  }
 
  /// Gets all of the functions in a particular file.
  iterator_range<FunctionRecordIterator>
  getCoveredFunctions(StringRef Filename) const {
    return make_range(
        FunctionRecordIterator(Functions, Filename,
                               getImpreciseRecordIndicesForFilename(Filename)),
        FunctionRecordIterator());
  }
 
  /// Get the list of function instantiation groups in a particular file.
  ///
  /// Every instantiation group in a program is attributed to exactly one file:
  /// the file in which the definition for the common function begins.
  LLVM_ABI std::vector<InstantiationGroup>
  getInstantiationGroups(StringRef Filename) const;
};
 
/// Coverage statistics for a single line.
class LineCoverageStats {
  uint64_t ExecutionCount;
  bool HasMultipleRegions;
  bool Mapped;
  unsigned Line;
  ArrayRef<const CoverageSegment *> LineSegments;
  const CoverageSegment *WrappedSegment;
 
  friend class LineCoverageIterator;
  LineCoverageStats() = default;
 
public:
  LLVM_ABI LineCoverageStats(ArrayRef<const CoverageSegment *> LineSegments,
                             const CoverageSegment *WrappedSegment,
                             unsigned Line);
 
  uint64_t getExecutionCount() const { return ExecutionCount; }
 
  bool hasMultipleRegions() const { return HasMultipleRegions; }
 
  bool isMapped() const { return Mapped; }
 
  unsigned getLine() const { return Line; }
 
  ArrayRef<const CoverageSegment *> getLineSegments() const {
    return LineSegments;
  }
 
  const CoverageSegment *getWrappedSegment() const { return WrappedSegment; }
};
 
/// An iterator over the \c LineCoverageStats objects for lines described by
/// a \c CoverageData instance.
class LineCoverageIterator
    : public iterator_facade_base<LineCoverageIterator,
                                  std::forward_iterator_tag,
                                  const LineCoverageStats> {
public:
  LineCoverageIterator(const CoverageData &CD)
      : LineCoverageIterator(CD, CD.begin()->Line) {}
 
  LineCoverageIterator(const CoverageData &CD, unsigned Line)
      : CD(CD), WrappedSegment(nullptr), Next(CD.begin()), Ended(false),
        Line(Line) {
    this->operator++();
  }
 
  bool operator==(const LineCoverageIterator &R) const {
    return &CD == &R.CD && Next == R.Next && Ended == R.Ended;
  }
 
  const LineCoverageStats &operator*() const { return Stats; }
 
  LLVM_ABI LineCoverageIterator &operator++();
 
  LineCoverageIterator getEnd() const {
    auto EndIt = *this;
    EndIt.Next = CD.end();
    EndIt.Ended = true;
    return EndIt;
  }
 
private:
  const CoverageData &CD;
  const CoverageSegment *WrappedSegment;
  std::vector<CoverageSegment>::const_iterator Next;
  bool Ended;
  unsigned Line;
  SmallVector<const CoverageSegment *, 4> Segments;
  LineCoverageStats Stats;
};
 
/// Get a \c LineCoverageIterator range for the lines described by \p CD.
static inline iterator_range<LineCoverageIterator>
getLineCoverageStats(const coverage::CoverageData &CD) {
  auto Begin = LineCoverageIterator(CD);
  auto End = Begin.getEnd();
  return make_range(Begin, End);
}
 
// Coverage mappping data (V2) has the following layout:
// IPSK_covmap:
//   [CoverageMapFileHeader]
//   [ArrayStart]
//    [CovMapFunctionRecordV2]
//    [CovMapFunctionRecordV2]
//    ...
//   [ArrayEnd]
//   [Encoded Filenames and Region Mapping Data]
//
// Coverage mappping data (V3) has the following layout:
// IPSK_covmap:
//   [CoverageMapFileHeader]
//   [Encoded Filenames]
// IPSK_covfun:
//   [ArrayStart]
//     odr_name_1: [CovMapFunctionRecordV3]
//     odr_name_2: [CovMapFunctionRecordV3]
//     ...
//   [ArrayEnd]
//
// Both versions of the coverage mapping format encode the same information,
// but the V3 format does so more compactly by taking advantage of linkonce_odr
// semantics (it allows exactly 1 function record per name reference).
 
/// This namespace defines accessors shared by different versions of coverage
/// mapping records.
namespace accessors {
 
/// Return the structural hash associated with the function.
template <class FuncRecordTy, llvm::endianness Endian>
uint64_t getFuncHash(const FuncRecordTy *Record) {
  return support::endian::byte_swap<uint64_t>(Record->FuncHash, Endian);
}
 
/// Return the coverage map data size for the function.
template <class FuncRecordTy, llvm::endianness Endian>
uint64_t getDataSize(const FuncRecordTy *Record) {
  return support::endian::byte_swap<uint32_t>(Record->DataSize, Endian);
}
 
/// Return the function lookup key. The value is considered opaque.
template <class FuncRecordTy, llvm::endianness Endian>
uint64_t getFuncNameRef(const FuncRecordTy *Record) {
  return support::endian::byte_swap<uint64_t>(Record->NameRef, Endian);
}
 
/// Return the PGO name of the function. Used for formats in which the name is
/// a hash.
template <class FuncRecordTy, llvm::endianness Endian>
Error getFuncNameViaRef(const FuncRecordTy *Record,
                        InstrProfSymtab &ProfileNames, StringRef &FuncName) {
  uint64_t NameRef = getFuncNameRef<FuncRecordTy, Endian>(Record);
  FuncName = ProfileNames.getFuncOrVarName(NameRef);
  return Error::success();
}
 
/// Read coverage mapping out-of-line, from \p MappingBuf. This is used when the
/// coverage mapping is attached to the file header, instead of to the function
/// record.
template <class FuncRecordTy, llvm::endianness Endian>
StringRef getCoverageMappingOutOfLine(const FuncRecordTy *Record,
                                      const char *MappingBuf) {
  return {MappingBuf, size_t(getDataSize<FuncRecordTy, Endian>(Record))};
}
 
/// Advance to the next out-of-line coverage mapping and its associated
/// function record.
template <class FuncRecordTy, llvm::endianness Endian>
std::pair<const char *, const FuncRecordTy *>
advanceByOneOutOfLine(const FuncRecordTy *Record, const char *MappingBuf) {
  return {MappingBuf + getDataSize<FuncRecordTy, Endian>(Record), Record + 1};
}
 
} // end namespace accessors
 
LLVM_PACKED_START
template <class IntPtrT>
struct CovMapFunctionRecordV1 {
  using ThisT = CovMapFunctionRecordV1<IntPtrT>;
 
#define COVMAP_V1
#define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name;
#include "llvm/ProfileData/InstrProfData.inc"
#undef COVMAP_V1
  CovMapFunctionRecordV1() = delete;
 
  template <llvm::endianness Endian> uint64_t getFuncHash() const {
    return accessors::getFuncHash<ThisT, Endian>(this);
  }
 
  template <llvm::endianness Endian> uint64_t getDataSize() const {
    return accessors::getDataSize<ThisT, Endian>(this);
  }
 
  /// Return function lookup key. The value is consider opaque.
  template <llvm::endianness Endian> IntPtrT getFuncNameRef() const {
    return support::endian::byte_swap<IntPtrT>(NamePtr, Endian);
  }
 
  /// Return the PGO name of the function.
  template <llvm::endianness Endian>
  Error getFuncName(InstrProfSymtab &ProfileNames, StringRef &FuncName) const {
    IntPtrT NameRef = getFuncNameRef<Endian>();
    uint32_t NameS = support::endian::byte_swap<uint32_t>(NameSize, Endian);
    FuncName = ProfileNames.getFuncName(NameRef, NameS);
    if (NameS && FuncName.empty())
      return make_error<CoverageMapError>(coveragemap_error::malformed,
                                          "function name is empty");
    return Error::success();
  }
 
  template <llvm::endianness Endian>
  std::pair<const char *, const ThisT *>
  advanceByOne(const char *MappingBuf) const {
    return accessors::advanceByOneOutOfLine<ThisT, Endian>(this, MappingBuf);
  }
 
  template <llvm::endianness Endian> uint64_t getFilenamesRef() const {
    llvm_unreachable("V1 function format does not contain a filenames ref");
  }
 
  template <llvm::endianness Endian>
  StringRef getCoverageMapping(const char *MappingBuf) const {
    return accessors::getCoverageMappingOutOfLine<ThisT, Endian>(this,
                                                                 MappingBuf);
  }
};
 
struct CovMapFunctionRecordV2 {
  using ThisT = CovMapFunctionRecordV2;
 
#define COVMAP_V2
#define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name;
#include "llvm/ProfileData/InstrProfData.inc"
#undef COVMAP_V2
  CovMapFunctionRecordV2() = delete;
 
  template <llvm::endianness Endian> uint64_t getFuncHash() const {
    return accessors::getFuncHash<ThisT, Endian>(this);
  }
 
  template <llvm::endianness Endian> uint64_t getDataSize() const {
    return accessors::getDataSize<ThisT, Endian>(this);
  }
 
  template <llvm::endianness Endian> uint64_t getFuncNameRef() const {
    return accessors::getFuncNameRef<ThisT, Endian>(this);
  }
 
  template <llvm::endianness Endian>
  Error getFuncName(InstrProfSymtab &ProfileNames, StringRef &FuncName) const {
    return accessors::getFuncNameViaRef<ThisT, Endian>(this, ProfileNames,
                                                       FuncName);
  }
 
  template <llvm::endianness Endian>
  std::pair<const char *, const ThisT *>
  advanceByOne(const char *MappingBuf) const {
    return accessors::advanceByOneOutOfLine<ThisT, Endian>(this, MappingBuf);
  }
 
  template <llvm::endianness Endian> uint64_t getFilenamesRef() const {
    llvm_unreachable("V2 function format does not contain a filenames ref");
  }
 
  template <llvm::endianness Endian>
  StringRef getCoverageMapping(const char *MappingBuf) const {
    return accessors::getCoverageMappingOutOfLine<ThisT, Endian>(this,
                                                                 MappingBuf);
  }
};
 
struct CovMapFunctionRecordV3 {
  using ThisT = CovMapFunctionRecordV3;
 
#define COVMAP_V3
#define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name;
#include "llvm/ProfileData/InstrProfData.inc"
#undef COVMAP_V3
  CovMapFunctionRecordV3() = delete;
 
  template <llvm::endianness Endian> uint64_t getFuncHash() const {
    return accessors::getFuncHash<ThisT, Endian>(this);
  }
 
  template <llvm::endianness Endian> uint64_t getDataSize() const {
    return accessors::getDataSize<ThisT, Endian>(this);
  }
 
  template <llvm::endianness Endian> uint64_t getFuncNameRef() const {
    return accessors::getFuncNameRef<ThisT, Endian>(this);
  }
 
  template <llvm::endianness Endian>
  Error getFuncName(InstrProfSymtab &ProfileNames, StringRef &FuncName) const {
    return accessors::getFuncNameViaRef<ThisT, Endian>(this, ProfileNames,
                                                       FuncName);
  }
 
  /// Get the filename set reference.
  template <llvm::endianness Endian> uint64_t getFilenamesRef() const {
    return support::endian::byte_swap<uint64_t>(FilenamesRef, Endian);
  }
 
  /// Read the inline coverage mapping. Ignore the buffer parameter, it is for
  /// out-of-line coverage mapping data only.
  template <llvm::endianness Endian>
  StringRef getCoverageMapping(const char *) const {
    return StringRef(&CoverageMapping, getDataSize<Endian>());
  }
 
  // Advance to the next inline coverage mapping and its associated function
  // record. Ignore the out-of-line coverage mapping buffer.
  template <llvm::endianness Endian>
  std::pair<const char *, const CovMapFunctionRecordV3 *>
  advanceByOne(const char *) const {
    assert(isAddrAligned(Align(8), this) && "Function record not aligned");
    const char *Next = ((const char *)this) + sizeof(CovMapFunctionRecordV3) -
                       sizeof(char) + getDataSize<Endian>();
    // Each function record has an alignment of 8, so we need to adjust
    // alignment before reading the next record.
    Next += offsetToAlignedAddr(Next, Align(8));
    return {nullptr, reinterpret_cast<const CovMapFunctionRecordV3 *>(Next)};
  }
};
 
// Per module coverage mapping data header, i.e. CoverageMapFileHeader
// documented above.
struct CovMapHeader {
#define COVMAP_HEADER(Type, LLVMType, Name, Init) Type Name;
#include "llvm/ProfileData/InstrProfData.inc"
  template <llvm::endianness Endian> uint32_t getNRecords() const {
    return support::endian::byte_swap<uint32_t>(NRecords, Endian);
  }
 
  template <llvm::endianness Endian> uint32_t getFilenamesSize() const {
    return support::endian::byte_swap<uint32_t>(FilenamesSize, Endian);
  }
 
  template <llvm::endianness Endian> uint32_t getCoverageSize() const {
    return support::endian::byte_swap<uint32_t>(CoverageSize, Endian);
  }
 
  template <llvm::endianness Endian> uint32_t getVersion() const {
    return support::endian::byte_swap<uint32_t>(Version, Endian);
  }
};
 
LLVM_PACKED_END
 
enum CovMapVersion {
  Version1 = 0,
  // Function's name reference from CovMapFuncRecord is changed from raw
  // name string pointer to MD5 to support name section compression. Name
  // section is also compressed.
  Version2 = 1,
  // A new interpretation of the columnEnd field is added in order to mark
  // regions as gap areas.
  Version3 = 2,
  // Function records are named, uniqued, and moved to a dedicated section.
  Version4 = 3,
  // Branch regions referring to two counters are added
  Version5 = 4,
  // Compilation directory is stored separately and combined with relative
  // filenames to produce an absolute file path.
  Version6 = 5,
  // Branch regions extended and Decision Regions added for MC/DC.
  Version7 = 6,
  // The current version is Version7.
  CurrentVersion = INSTR_PROF_COVMAP_VERSION
};
 
// Correspond to "llvmcovm", in little-endian.
constexpr uint64_t TestingFormatMagic = 0x6d766f636d766c6c;
 
enum class TestingFormatVersion : uint64_t {
  // The first version's number corresponds to the string "testdata" in
  // little-endian. This is for a historical reason.
  Version1 = 0x6174616474736574,
  // Version1 has a defect that it can't store multiple file records. Version2
  // fix this problem by adding a new field before the file records section.
  Version2 = 1,
  // The current testing format version is Version2.
  CurrentVersion = Version2
};
 
template <int CovMapVersion, class IntPtrT> struct CovMapTraits {
  using CovMapFuncRecordType = CovMapFunctionRecordV3;
  using NameRefType = uint64_t;
};
 
template <class IntPtrT> struct CovMapTraits<CovMapVersion::Version3, IntPtrT> {
  using CovMapFuncRecordType = CovMapFunctionRecordV2;
  using NameRefType = uint64_t;
};
 
template <class IntPtrT> struct CovMapTraits<CovMapVersion::Version2, IntPtrT> {
  using CovMapFuncRecordType = CovMapFunctionRecordV2;
  using NameRefType = uint64_t;
};
 
template <class IntPtrT> struct CovMapTraits<CovMapVersion::Version1, IntPtrT> {
  using CovMapFuncRecordType = CovMapFunctionRecordV1<IntPtrT>;
  using NameRefType = IntPtrT;
};
 
} // end namespace coverage
 
/// Provide DenseMapInfo for CounterExpression
template <> struct DenseMapInfo<coverage::CounterExpression> {
  static unsigned getHashValue(const coverage::CounterExpression &V) {
    return static_cast<unsigned>(
        hash_combine(V.Kind, V.LHS.getKind(), V.LHS.getCounterID(),
                     V.RHS.getKind(), V.RHS.getCounterID()));
  }
 
  static bool isEqual(const coverage::CounterExpression &LHS,
                      const coverage::CounterExpression &RHS) {
    return LHS.Kind == RHS.Kind && LHS.LHS == RHS.LHS && LHS.RHS == RHS.RHS;
  }
};
 
} // end namespace llvm
 
#endif // LLVM_PROFILEDATA_COVERAGE_COVERAGEMAPPING_H