//===-- LibCxxMap.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 "LibCxx.h"

#include "Plugins/TypeSystem/Clang/TypeSystemClang.h"

#include "lldb/Core/ValueObject.h"

#include "lldb/Core/ValueObjectConstResult.h"

#include "lldb/DataFormatters/FormattersHelpers.h"

#include "lldb/Target/Target.h"

#include "lldb/Utility/DataBufferHeap.h"

#include "lldb/Utility/Endian.h"

#include "lldb/Utility/Status.h"

#include "lldb/Utility/Stream.h"

using namespace lldb;

using namespace lldb_private;

using namespace lldb_private::formatters;

class MapEntry {

public:

  MapEntry() = default;

  explicit MapEntry(ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {}

  explicit MapEntry(ValueObject *entry)

      : m_entry_sp(entry ? entry->GetSP() : 
ValueObjectSP()0
) {}

  ValueObjectSP left() const {

    static ConstString g_left("__left_");

    if (!m_entry_sp)

      return m_entry_sp;

    return m_entry_sp->GetSyntheticChildAtOffset(

        0, m_entry_sp->GetCompilerType(), true);

  }

  ValueObjectSP right() const {

    static ConstString g_right("__right_");

    if (!m_entry_sp)

      return m_entry_sp;

    return m_entry_sp->GetSyntheticChildAtOffset(

        m_entry_sp->GetProcessSP()->GetAddressByteSize(),

        m_entry_sp->GetCompilerType(), true);

  }

  ValueObjectSP parent() const {

    static ConstString g_parent("__parent_");

    if (!m_entry_sp)

      return m_entry_sp;

    return m_entry_sp->GetSyntheticChildAtOffset(

        2 * m_entry_sp->GetProcessSP()->GetAddressByteSize(),

        m_entry_sp->GetCompilerType(), true);

  }

  uint64_t value() const {

    if (!m_entry_sp)

      return 0;

    return m_entry_sp->GetValueAsUnsigned(0);

  }

  bool error() const {

    if (!m_entry_sp)

      return true;

    return m_entry_sp->GetError().Fail();

  }

  bool null() const { return (value() == 0); }

  ValueObjectSP GetEntry() const { return m_entry_sp; }

  void SetEntry(ValueObjectSP entry) { m_entry_sp = entry; }

  bool operator==(const MapEntry &rhs) const {

    return (rhs.m_entry_sp.get() == m_entry_sp.get());

  }

private:

  ValueObjectSP m_entry_sp;

};

class MapIterator {

public:

  MapIterator() = default;

  MapIterator(MapEntry entry, size_t depth = 0)

      : m_entry(std::move(entry)), m_max_depth(depth), m_error(false) {}

  MapIterator(ValueObjectSP entry, size_t depth = 0)

      : m_entry(std::move(entry)), m_max_depth(depth), m_error(false) {}

  MapIterator(const MapIterator &rhs)

      : m_entry(rhs.m_entry), m_max_depth(rhs.m_max_depth), m_error(false) {}

  MapIterator(ValueObject *entry, size_t depth = 0)

      : m_entry(entry), m_max_depth(depth), m_error(false) {}

  MapIterator &operator=(const MapIterator &) = default;

  ValueObjectSP value() { return m_entry.GetEntry(); }

  ValueObjectSP advance(size_t count) {

    ValueObjectSP fail;

    if (m_error)

      return fail;

    size_t steps = 0;

    while (count > 0) {

      next();

      count--, steps++;

      if (m_error || m_entry.null() || (steps > m_max_depth))

        return fail;

    }

    return m_entry.GetEntry();

  }

protected:

  void next() {

    if (m_entry.null())

      return;

    MapEntry right(m_entry.right());

    if (!right.null()) {

      m_entry = tree_min(std::move(right));

      return;

    }

    size_t steps = 0;

    while (!is_left_child(m_entry)) {

      if (m_entry.error()) {

        m_error = true;

        return;

      }

      m_entry.SetEntry(m_entry.parent());

      steps++;

      if (steps > m_max_depth) {

        m_entry = MapEntry();

        return;

      }

    }

    m_entry = MapEntry(m_entry.parent());

  }

private:

  MapEntry tree_min(MapEntry x) {

    if (x.null())

      return MapEntry();

    MapEntry left(x.left());

    size_t steps = 0;

    while (!left.null()) {

      if (left.error()) {

        m_error = true;

        return MapEntry();

      }

      x = left;

      left.SetEntry(x.left());

      steps++;

      if (steps > m_max_depth)

        return MapEntry();

    }

    return x;

  }

  bool is_left_child(const MapEntry &x) {

    if (x.null())

      return false;

    MapEntry rhs(x.parent());

    rhs.SetEntry(rhs.left());

    return x.value() == rhs.value();

  }

  MapEntry m_entry;

  size_t m_max_depth = 0;

  bool m_error = false;

};

namespace lldb_private {

namespace formatters {

class LibcxxStdMapSyntheticFrontEnd : public SyntheticChildrenFrontEnd {

public:

  LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp);

  ~LibcxxStdMapSyntheticFrontEnd() override = default;

  size_t CalculateNumChildren() override;

  lldb::ValueObjectSP GetChildAtIndex(size_t idx) override;

  bool Update() override;

  bool MightHaveChildren() override;

  size_t GetIndexOfChildWithName(ConstString name) override;

private:

  bool GetDataType();

  void GetValueOffset(const lldb::ValueObjectSP &node);

  ValueObject *m_tree = nullptr;

  ValueObject *m_root_node = nullptr;

  CompilerType m_element_type;

  uint32_t m_skip_size = UINT32_MAX;

  size_t m_count = UINT32_MAX;

  std::map<size_t, MapIterator> m_iterators;

};

} // namespace formatters

} // namespace lldb_private

lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::

    LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp)

    : SyntheticChildrenFrontEnd(*valobj_sp), m_element_type(), m_iterators() {

  if (valobj_sp)

    Update();

}

size_t lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::

    CalculateNumChildren() {

  if (m_count != UINT32_MAX)

    return m_count;

  if (m_tree == nullptr)

    return 0;

  ValueObjectSP m_item(m_tree->GetChildMemberWithName("__pair3_"));

  if (!m_item)

    return 0;

  switch (m_item->GetCompilerType().GetNumDirectBaseClasses()) {

  case 1:

    // Assume a pre llvm r300140 __compressed_pair implementation:

    m_item = m_item->GetChildMemberWithName("__first_");

    break;

  case 2: {

    // Assume a post llvm r300140 __compressed_pair implementation:

    ValueObjectSP first_elem_parent = m_item->GetChildAtIndex(0);

    m_item = first_elem_parent->GetChildMemberWithName("__value_");

    break;

  }

  default:

    return false;

  }

  if (!m_item)

    return 0;

  m_count = m_item->GetValueAsUnsigned(0);

  return m_count;

}

bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetDataType() {

  if (m_element_type.IsValid())

    return true;

  m_element_type.Clear();

  ValueObjectSP deref;

  Status error;

  deref = m_root_node->Dereference(error);

  if (!deref || error.Fail())

    return false;

  deref = deref->GetChildMemberWithName("__value_");

  if (deref) {

    m_element_type = deref->GetCompilerType();

    return true;

  }

  deref = m_backend.GetChildAtNamePath({"__tree_", "__pair3_"});

  if (!deref)

    return false;

  m_element_type = deref->GetCompilerType()

                       .GetTypeTemplateArgument(1)

                       .GetTypeTemplateArgument(1);

  if (m_element_type) {

    std::string name;

    uint64_t bit_offset_ptr;

    uint32_t bitfield_bit_size_ptr;

    bool is_bitfield_ptr;

    m_element_type = m_element_type.GetFieldAtIndex(

        0, name, &bit_offset_ptr, &bitfield_bit_size_ptr, &is_bitfield_ptr);

    m_element_type = m_element_type.GetTypedefedType();

    return m_element_type.IsValid();

  } else {

    m_element_type = m_backend.GetCompilerType().GetTypeTemplateArgument(0);

    return m_element_type.IsValid();

  }

}

void lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetValueOffset(

    const lldb::ValueObjectSP &node) {

  if (m_skip_size != UINT32_MAX)

    return;

  if (!node)

    return;

  CompilerType node_type(node->GetCompilerType());

  uint64_t bit_offset;

  if (node_type.GetIndexOfFieldWithName("__value_", nullptr, &bit_offset) !=

      UINT32_MAX) {

    m_skip_size = bit_offset / 8u;

  } else {

    auto ast_ctx = node_type.GetTypeSystem().dyn_cast_or_null<TypeSystemClang>();

    if (!ast_ctx)

      return;

    CompilerType tree_node_type = ast_ctx->CreateStructForIdentifier(

        llvm::StringRef(),

        {{"ptr0", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()},

         {"ptr1", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()},

         {"ptr2", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()},

         {"cw", ast_ctx->GetBasicType(lldb::eBasicTypeBool)},

         {"payload", (m_element_type.GetCompleteType(), m_element_type)}});

    std::string child_name;

    uint32_t child_byte_size;

    int32_t child_byte_offset = 0;

    uint32_t child_bitfield_bit_size;

    uint32_t child_bitfield_bit_offset;

    bool child_is_base_class;

    bool child_is_deref_of_parent;

    uint64_t language_flags;

    if (tree_node_type

            .GetChildCompilerTypeAtIndex(

                nullptr, 4, true, true, true, child_name, child_byte_size,

                child_byte_offset, child_bitfield_bit_size,

                child_bitfield_bit_offset, child_is_base_class,

                child_is_deref_of_parent, nullptr, language_flags)

            .IsValid())

      m_skip_size = (uint32_t)child_byte_offset;

  }

}

lldb::ValueObjectSP

lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetChildAtIndex(

    size_t idx) {

  static ConstString g_cc_("__cc_"), g_cc("__cc");

  static ConstString g_nc("__nc");

  if (idx >= CalculateNumChildren())

    return lldb::ValueObjectSP();

  if (m_tree == nullptr || m_root_node == nullptr)

    return lldb::ValueObjectSP();

  MapIterator iterator(m_root_node, CalculateNumChildren());

  const bool need_to_skip = (idx > 0);

  size_t actual_advancde = idx;

  if (need_to_skip) {

    auto cached_iterator = m_iterators.find(idx - 1);

    if (cached_iterator != m_iterators.end()) {

      iterator = cached_iterator->second;

      actual_advancde = 1;

    }

  }

  ValueObjectSP iterated_sp(iterator.advance(actual_advancde));

  if (!iterated_sp) {

    // this tree is garbage - stop

    m_tree =

        nullptr; // this will stop all future searches until an Update() happens

    return iterated_sp;

  }

  if (GetDataType()) {

    if (!need_to_skip) {

      Status error;

      iterated_sp = iterated_sp->Dereference(error);

      if (!iterated_sp || error.Fail()) {

        m_tree = nullptr;

        return lldb::ValueObjectSP();

      }

      GetValueOffset(iterated_sp);

      auto child_sp = iterated_sp->GetChildMemberWithName("__value_");

      if (child_sp)

        iterated_sp = child_sp;

      else

        iterated_sp = iterated_sp->GetSyntheticChildAtOffset(

            m_skip_size, m_element_type, true);

      if (!iterated_sp) {

        m_tree = nullptr;

        return lldb::ValueObjectSP();

      }

    } else {

      // because of the way our debug info is made, we need to read item 0

      // first so that we can cache information used to generate other elements

      if (m_skip_size == UINT32_MAX)

        GetChildAtIndex(0);

      if (m_skip_size == UINT32_MAX) {

        m_tree = nullptr;

        return lldb::ValueObjectSP();

      }

      iterated_sp = iterated_sp->GetSyntheticChildAtOffset(

          m_skip_size, m_element_type, true);

      if (!iterated_sp) {

        m_tree = nullptr;

        return lldb::ValueObjectSP();

      }

    }

  } else {

    m_tree = nullptr;

    return lldb::ValueObjectSP();

  }

  // at this point we have a valid

  // we need to copy current_sp into a new object otherwise we will end up with

  // all items named __value_

  StreamString name;

  name.Printf("[%" PRIu64 "]", (uint64_t)idx);

  auto potential_child_sp = iterated_sp->Clone(ConstString(name.GetString()));

  if (potential_child_sp) {

    switch (potential_child_sp->GetNumChildren()) {

    case 1: {

      auto child0_sp = potential_child_sp->GetChildAtIndex(0);

      if (child0_sp &&

          (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc))

        potential_child_sp = child0_sp->Clone(ConstString(name.GetString()));

      break;

    }

    case 2: {

      auto child0_sp = potential_child_sp->GetChildAtIndex(0);

      auto child1_sp = potential_child_sp->GetChildAtIndex(1);

      if (child0_sp &&

          (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc) &&

          
child1_sp0
 && 
child1_sp->GetName() == g_nc0
)

        potential_child_sp = child0_sp->Clone(ConstString(name.GetString()));

      break;

    }

    }

  }

  m_iterators[idx] = iterator;

  return potential_child_sp;

}

bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::Update() {

  m_count = UINT32_MAX;

  m_tree = m_root_node = nullptr;

  m_iterators.clear();

  m_tree = m_backend.GetChildMemberWithName("__tree_").get();

  if (!m_tree)

    return false;

  m_root_node = m_tree->GetChildMemberWithName("__begin_node_").get();

  return false;

}

bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::

    MightHaveChildren() {

  return true;

}

size_t lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::

    GetIndexOfChildWithName(ConstString name) {

  return ExtractIndexFromString(name.GetCString());

}

SyntheticChildrenFrontEnd *

lldb_private::formatters::LibcxxStdMapSyntheticFrontEndCreator(

    CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) {

  return (valobj_sp ? new LibcxxStdMapSyntheticFrontEnd(valobj_sp) : 
nullptr0
);

}