//===-- LVRange.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
//
//===----------------------------------------------------------------------===//
//
// This implements the LVRange class.
//
//===----------------------------------------------------------------------===//

#include "llvm/DebugInfo/LogicalView/Core/LVRange.h"
#include "llvm/DebugInfo/LogicalView/Core/LVLocation.h"
#include "llvm/DebugInfo/LogicalView/Core/LVOptions.h"

using namespace llvm;
using namespace llvm::logicalview;

#define DEBUG_TYPE "Range"

void LVRange::startSearch() {
  RangesTree.clear();

  LLVM_DEBUG({ dbgs() << "\nRanges Tree entries:\n"; });

  // Traverse the ranges and store them into the interval tree.
  for (LVRangeEntry &RangeEntry : RangeEntries) {
    LLVM_DEBUG({
      LVScope *Scope = RangeEntry.scope();
      dbgs() << "Scope: " << format_decimal(Scope->getLevel(), 5) << " "
             << "Range: [" << hexValue(RangeEntry.lower()) << ":"
             << hexValue(RangeEntry.upper()) << "]\n";
    });

    RangesTree.insert(RangeEntry.lower(), RangeEntry.upper(),
                      RangeEntry.scope());
  }

  // Create the interval tree.
  RangesTree.create();

  LLVM_DEBUG({
    dbgs() << "\nRanges Tree:\n";
    RangesTree.print(dbgs());
  });
}

// Add the pair in an ascending order, with the smallest ranges at the
// start; in that way, enclosing scopes ranges are at the end of the
// list; we assume that low <= high.
void LVRange::addEntry(LVScope *Scope, LVAddress LowerAddress,
                       LVAddress UpperAddress) {
  // We assume the low <= high.
  if (LowerAddress > UpperAddress)
    std::swap(LowerAddress, UpperAddress);

  // Record the lowest and highest seen addresses.
  if (LowerAddress < Lower)
    Lower = LowerAddress;
  if (UpperAddress > Upper)
    Upper = UpperAddress;

  // Just add the scope and range pair, in no particular order.
  RangeEntries.emplace_back(LowerAddress, UpperAddress, Scope);
}

void LVRange::addEntry(LVScope *Scope) {
  assert(Scope && "Scope must not be nullptr");
  // Traverse the ranges and update the ranges set only if the ranges
  // values are not already recorded.
  if (const LVLocations *Locations = Scope->getRanges())
    for (const LVLocation *Location : *Locations) {
      LVAddress LowPC = Location->getLowerAddress();
      LVAddress HighPC = Location->getUpperAddress();
      if (!hasEntry(LowPC, HighPC))
        // Add the pair of addresses.
        addEntry(Scope, LowPC, HighPC);
    }
}

// Get the scope associated with the input address.
LVScope *LVRange::getEntry(LVAddress Address) const {
  LLVM_DEBUG({ dbgs() << format("Searching: 0x%08x\nFound: ", Address); });

  LVScope *Target = nullptr;
  LVLevel TargetLevel = 0;
  LVLevel Level = 0;
  LVScope *Scope = nullptr;
  for (LVRangesTree::find_iterator Iter = RangesTree.find(Address),
                                   End = RangesTree.find_end();
       Iter != End; ++Iter) {
    LLVM_DEBUG(
        { dbgs() << format("[0x%08x,0x%08x] ", Iter->left(), Iter->right()); });
    Scope = Iter->value();
    Level = Scope->getLevel();
    if (Level > TargetLevel) {
      TargetLevel = Level;
      Target = Scope;
    }
  }

  LLVM_DEBUG({ dbgs() << (Scope ? "\n" : "None\n"); });

  return Target;
}

// Find the associated Scope for the given ranges values.
LVScope *LVRange::getEntry(LVAddress LowerAddress,
                           LVAddress UpperAddress) const {
  for (const LVRangeEntry &RangeEntry : RangeEntries)
    if (LowerAddress >= RangeEntry.lower() && UpperAddress < RangeEntry.upper())
      return RangeEntry.scope();
  return nullptr;
}

// True if the range addresses contain the pair [LowerAddress, UpperAddress].
bool LVRange::hasEntry(LVAddress LowerAddress, LVAddress UpperAddress) const {
  for (const LVRangeEntry &RangeEntry : RangeEntries)
    if (LowerAddress == RangeEntry.lower() &&
        UpperAddress == RangeEntry.upper())
      return true;
  return false;
}

// Sort the range elements for the whole Compile Unit.
void LVRange::sort() {
  auto CompareRangeEntry = [](const LVRangeEntry &lhs,
                              const LVRangeEntry &rhs) -> bool {
    if (lhs.lower() < rhs.lower())
      return true;

    // If the lower address is the same, use the upper address value in
    // order to put first the smallest interval.
    if (lhs.lower() == rhs.lower())
      return lhs.upper() < rhs.upper();

    return false;
  };

  // Sort the ranges using low address and range size.
  std::stable_sort(RangeEntries.begin(), RangeEntries.end(), CompareRangeEntry);
}

void LVRange::print(raw_ostream &OS, bool Full) const {
  size_t Indentation = 0;
  for (const LVRangeEntry &RangeEntry : RangeEntries) {
    LVScope *Scope = RangeEntry.scope();
    Scope->printAttributes(OS, Full);
    Indentation = options().indentationSize();
    if (Indentation)
      OS << " ";
    OS << format("[0x%08x,0x%08x] ", RangeEntry.lower(), RangeEntry.upper())
       << formattedKind(Scope->kind()) << " " << formattedName(Scope->getName())
       << "\n";
  }
  printExtra(OS, Full);
}