//===- DWARFUnitIndex.cpp -------------------------------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//

#include "llvm/DebugInfo/DWARF/DWARFUnitIndex.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Support/DataExtractor.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/raw_ostream.h"
#include <cinttypes>
#include <cstdint>

using namespace llvm;

namespace {

enum class DWARFSectionKindV2 {
  DW_SECT_INFO = 1,
  DW_SECT_TYPES = 2,
  DW_SECT_ABBREV = 3,
  DW_SECT_LINE = 4,
  DW_SECT_LOC = 5,
  DW_SECT_STR_OFFSETS = 6,
  DW_SECT_MACINFO = 7,
  DW_SECT_MACRO = 8,
};

} // namespace

// Return true if the section identifier is defined in the DWARFv5 standard.
constexpr bool isKnownV5SectionID(uint32_t ID) {
  return ID >= DW_SECT_INFO && ID <= DW_SECT_RNGLISTS &&
         ID != DW_SECT_EXT_TYPES;
}

uint32_t llvm::serializeSectionKind(DWARFSectionKind Kind,
                                    unsigned IndexVersion) {
  if (IndexVersion == 5) {
    assert(isKnownV5SectionID(Kind));
    return static_cast<uint32_t>(Kind);
  }
  assert(IndexVersion == 2);
  switch (Kind) {
#define CASE(S,T) \
  case DW_SECT_##S: \
    return static_cast<uint32_t>(DWARFSectionKindV2::DW_SECT_##T)
  CASE(INFO, INFO);
  CASE(EXT_TYPES, TYPES);
  CASE(ABBREV, ABBREV);
  CASE(LINE, LINE);
  CASE(EXT_LOC, LOC);
  CASE(STR_OFFSETS, STR_OFFSETS);
  CASE(EXT_MACINFO, MACINFO);
  CASE(MACRO, MACRO);
#undef CASE
  default:
    // All other section kinds have no corresponding values in v2 indexes.
    llvm_unreachable("Invalid DWARFSectionKind");
  }
}

DWARFSectionKind llvm::deserializeSectionKind(uint32_t Value,
                                              unsigned IndexVersion) {
  if (IndexVersion == 5)
    return isKnownV5SectionID(Value)
               ? static_cast<DWARFSectionKind>(Value)
               : DW_SECT_EXT_unknown;
  assert(IndexVersion == 2);
  switch (static_cast<DWARFSectionKindV2>(Value)) {
#define CASE(S,T) \
  case DWARFSectionKindV2::DW_SECT_##S: \
    return DW_SECT_##T
  CASE(INFO, INFO);
  CASE(TYPES, EXT_TYPES);
  CASE(ABBREV, ABBREV);
  CASE(LINE, LINE);
  CASE(LOC, EXT_LOC);
  CASE(STR_OFFSETS, STR_OFFSETS);
  CASE(MACINFO, EXT_MACINFO);
  CASE(MACRO, MACRO);
#undef CASE
  }
  return DW_SECT_EXT_unknown;
}

bool DWARFUnitIndex::Header::parse(DataExtractor IndexData,
                                   uint64_t *OffsetPtr) {
  const uint64_t BeginOffset = *OffsetPtr;
  if (!IndexData.isValidOffsetForDataOfSize(*OffsetPtr, 16))
    return false;
  // GCC Debug Fission defines the version as an unsigned 32-bit field
  // with value of 2, https://gcc.gnu.org/wiki/DebugFissionDWP.
  // DWARFv5 defines the same space as an uhalf version field with value of 5
  // and a 2 bytes long padding, see Section 7.3.5.3.
  Version = IndexData.getU32(OffsetPtr);
  if (Version != 2) {
    *OffsetPtr = BeginOffset;
    Version = IndexData.getU16(OffsetPtr);
    if (Version != 5)
      return false;
    *OffsetPtr += 2; // Skip padding.
  }
  NumColumns = IndexData.getU32(OffsetPtr);
  NumUnits = IndexData.getU32(OffsetPtr);
  NumBuckets = IndexData.getU32(OffsetPtr);
  return true;
}

void DWARFUnitIndex::Header::dump(raw_ostream &OS) const {
  OS << format("version = %u, units = %u, slots = %u\n\n", Version, NumUnits, NumBuckets);
}

bool DWARFUnitIndex::parse(DataExtractor IndexData) {
  bool b = parseImpl(IndexData);
  if (!b) {
    // Make sure we don't try to dump anything
    Header.NumBuckets = 0;
    // Release any partially initialized data.
    ColumnKinds.reset();
    Rows.reset();
  }
  return b;
}

bool DWARFUnitIndex::parseImpl(DataExtractor IndexData) {
  uint64_t Offset = 0;
  if (!Header.parse(IndexData, &Offset))
    return false;

  // Fix InfoColumnKind: in DWARFv5, type units are in .debug_info.dwo.
  if (Header.Version == 5)
    InfoColumnKind = DW_SECT_INFO;

  if (!IndexData.isValidOffsetForDataOfSize(
          Offset, Header.NumBuckets * (8 + 4) +
                      (2 * Header.NumUnits + 1) * 4 * Header.NumColumns))
    return false;

  Rows = std::make_unique<Entry[]>(Header.NumBuckets);
  auto Contribs =
      std::make_unique<Entry::SectionContribution *[]>(Header.NumUnits);
  ColumnKinds = std::make_unique<DWARFSectionKind[]>(Header.NumColumns);
  RawSectionIds = std::make_unique<uint32_t[]>(Header.NumColumns);

  // Read Hash Table of Signatures
  for (unsigned i = 0; i != Header.NumBuckets; ++i)
    Rows[i].Signature = IndexData.getU64(&Offset);

  // Read Parallel Table of Indexes
  for (unsigned i = 0; i != Header.NumBuckets; ++i) {
    auto Index = IndexData.getU32(&Offset);
    if (!Index)
      continue;
    Rows[i].Index = this;
    Rows[i].Contributions =
        std::make_unique<Entry::SectionContribution[]>(Header.NumColumns);
    Contribs[Index - 1] = Rows[i].Contributions.get();
  }

  // Read the Column Headers
  for (unsigned i = 0; i != Header.NumColumns; ++i) {
    RawSectionIds[i] = IndexData.getU32(&Offset);
    ColumnKinds[i] = deserializeSectionKind(RawSectionIds[i], Header.Version);
    if (ColumnKinds[i] == InfoColumnKind) {
      if (InfoColumn != -1)
        return false;
      InfoColumn = i;
    }
  }

  if (InfoColumn == -1)
    return false;

  // Read Table of Section Offsets
  for (unsigned i = 0; i != Header.NumUnits; ++i) {
    auto *Contrib = Contribs[i];
    for (unsigned i = 0; i != Header.NumColumns; ++i)
      Contrib[i].Offset = IndexData.getU32(&Offset);
  }

  // Read Table of Section Sizes
  for (unsigned i = 0; i != Header.NumUnits; ++i) {
    auto *Contrib = Contribs[i];
    for (unsigned i = 0; i != Header.NumColumns; ++i)
      Contrib[i].Length = IndexData.getU32(&Offset);
  }

  return true;
}

StringRef DWARFUnitIndex::getColumnHeader(DWARFSectionKind DS) {
  switch (DS) {
#define HANDLE_DW_SECT(ID, NAME)                                               \
  case DW_SECT_##NAME:                                                         \
    return #NAME;
#include "llvm/BinaryFormat/Dwarf.def"
  case DW_SECT_EXT_TYPES:
    return "TYPES";
  case DW_SECT_EXT_LOC:
    return "LOC";
  case DW_SECT_EXT_MACINFO:
    return "MACINFO";
  case DW_SECT_EXT_unknown:
    return StringRef();
  }
  llvm_unreachable("Unknown DWARFSectionKind");
}

void DWARFUnitIndex::dump(raw_ostream &OS) const {
  if (!*this)
    return;

  Header.dump(OS);
  OS << "Index Signature         ";
  for (unsigned i = 0; i != Header.NumColumns; ++i) {
    DWARFSectionKind Kind = ColumnKinds[i];
    StringRef Name = getColumnHeader(Kind);
    if (!Name.empty())
      OS << ' ' << left_justify(Name, 24);
    else
      OS << format(" Unknown: %-15" PRIu32, RawSectionIds[i]);
  }
  OS << "\n----- ------------------";
  for (unsigned i = 0; i != Header.NumColumns; ++i)
    OS << " ------------------------";
  OS << '\n';
  for (unsigned i = 0; i != Header.NumBuckets; ++i) {
    auto &Row = Rows[i];
    if (auto *Contribs = Row.Contributions.get()) {
      OS << format("%5u 0x%016" PRIx64 " ", i + 1, Row.Signature);
      for (unsigned i = 0; i != Header.NumColumns; ++i) {
        auto &Contrib = Contribs[i];
        OS << format("[0x%08x, 0x%08x) ", Contrib.Offset,
                     Contrib.Offset + Contrib.Length);
      }
      OS << '\n';
    }
  }
}

const DWARFUnitIndex::Entry::SectionContribution *
DWARFUnitIndex::Entry::getContribution(DWARFSectionKind Sec) const {
  uint32_t i = 0;
  for (; i != Index->Header.NumColumns; ++i)
    if (Index->ColumnKinds[i] == Sec)
      return &Contributions[i];
  return nullptr;
}

const DWARFUnitIndex::Entry::SectionContribution *
DWARFUnitIndex::Entry::getContribution() const {
  return &Contributions[Index->InfoColumn];
}

const DWARFUnitIndex::Entry *
DWARFUnitIndex::getFromOffset(uint32_t Offset) const {
  if (OffsetLookup.empty()) {
    for (uint32_t i = 0; i != Header.NumBuckets; ++i)
      if (Rows[i].Contributions)
        OffsetLookup.push_back(&Rows[i]);
    llvm::sort(OffsetLookup, [&](Entry *E1, Entry *E2) {
      return E1->Contributions[InfoColumn].Offset <
             E2->Contributions[InfoColumn].Offset;
    });
  }
  auto I = partition_point(OffsetLookup, [&](Entry *E2) {
    return E2->Contributions[InfoColumn].Offset <= Offset;
  });
  if (I == OffsetLookup.begin())
    return nullptr;
  --I;
  const auto *E = *I;
  const auto &InfoContrib = E->Contributions[InfoColumn];
  if ((InfoContrib.Offset + InfoContrib.Length) <= Offset)
    return nullptr;
  return E;
}

const DWARFUnitIndex::Entry *DWARFUnitIndex::getFromHash(uint64_t S) const {
  uint64_t Mask = Header.NumBuckets - 1;

  auto H = S & Mask;
  auto HP = ((S >> 32) & Mask) | 1;
  // The spec says "while 0 is a valid hash value, the row index in a used slot
  // will always be non-zero". Loop until we find a match or an empty slot.
  while (Rows[H].getSignature() != S && Rows[H].Index != nullptr)
    H = (H + HP) & Mask;

  // If the slot is empty, we don't care whether the signature matches (it could
  // be zero and still match the zeros in the empty slot).
  if (Rows[H].Index == nullptr)
    return nullptr;

  return &Rows[H];
}