// Copyright 2019 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include <lib/fit/optional.h>
#include <lib/inspect/cpp/reader.h>
#include <lib/inspect/cpp/vmo/block.h>
#include <lib/inspect/cpp/vmo/scanner.h>
#include <lib/inspect/cpp/vmo/snapshot.h>

#include <iterator>
#include <set>
#include <stack>
#include <unordered_map>

using inspect::internal::BlockIndex;
using inspect::internal::SnapshotTree;

namespace inspect {

namespace {

// Traverses the given hierarchy and passes pointers to any hierarchy containing a link to the
// callback.
//
// The callback is called before the passed hierarchy is traversed into, so it may be modified in
// the context of the callback.
void VisitHierarchiesWithLink(Hierarchy* root, fit::function<void(Hierarchy*)> callback) {
  root->Visit([&](const std::vector<std::string>& path, Hierarchy* hierarchy) {
    if (!hierarchy->node().links().empty()) {
      callback(hierarchy);
    }
    return true;
  });
}

// Iteratively snapshot individual inspectors and then snapshot the children of those inspectors,
// collecting the results in a single SnapshotTree.
//
// Consistency of individual Snapshots is guaranteed.
//
// Child Snapshots are guaranteed only to be taken consistently after their parent Snapshot.
//
// Between the initial Snapshot and reading lazy children, it is possible that the lazy child was
// deleted. In this case, the child snapshot will be missing.
fit::promise<SnapshotTree> SnapshotTreeFromInspector(Inspector insp) {
  SnapshotTree ret;
  if (ZX_OK != Snapshot::Create(insp.DuplicateVmo(), &ret.snapshot)) {
    return fit::make_result_promise<SnapshotTree>(fit::error());
  }

  // Sequence all promises to ensure depth-first traversal. Otherwise traversal may cause
  // all children for a Snapshot to be instantiated simultaneously.
  fit::sequencer seq;
  std::vector<fit::promise<SnapshotTree>> promises;
  auto child_names = insp.GetChildNames();
  for (const auto& child_name : child_names) {
    promises.emplace_back(
        insp.OpenChild(child_name)
            .and_then([](Inspector& insp) { return SnapshotTreeFromInspector(std::move(insp)); })
            .wrap_with(seq));
  }

  return fit::join_promise_vector(std::move(promises))
      .and_then([ret = std::move(ret), names = std::move(child_names)](
                    std::vector<fit::result<SnapshotTree>>& children) mutable
                -> fit::result<SnapshotTree> {
        ZX_ASSERT(names.size() == children.size());

        for (size_t i = 0; i < names.size(); i++) {
          if (children[i].is_ok()) {
            ret.children.emplace(std::move(names[i]), children[i].take_value());
          }
        }

        return fit::ok(std::move(ret));
      });
}

}  // namespace

namespace internal {

// A ParsedNode contains parsed information for a node.
// It is built iteratively as children and values are discovered.
//
// A ParsedNode is valid only if it has been initialized with a name and
// parent index (which happens when its OBJECT_VALUE block is read).
//
// A ParsedNode is "complete" when the number of children in the parsed
// hierarchy matches an expected count. At this point the Hierarchy may be
// removed and the ParsedNode discarded.
struct ParsedNode {
  // The node hierarchy being parsed out of the buffer.
  // Propertys and properties are parsed into here as they are read.
  Hierarchy hierarchy;

  // The number of children expected for this node.
  // The node is considered "complete" once the number of children in the
  // hierarchy matches this count.
  size_t children_count = 0;

  // The index of the parent, only valid if this node is initialized.
  BlockIndex parent;

  // Initializes the stored node with the given name and parent.
  void InitializeNode(std::string name, BlockIndex new_parent) {
    hierarchy.node_ptr()->set_name(std::move(name));
    parent = new_parent;
    initialized_ = true;
  }

  explicit operator bool() { return initialized_; }

  bool is_complete() { return hierarchy.children().size() == children_count; }

 private:
  bool initialized_ = false;
};

// The |Reader| supports reading the contents of a |Snapshot|.
// This class constructs a hierarchy of nodes contained in the snapshot
// if the snapshot is valid.
class Reader {
 public:
  Reader(Snapshot snapshot) : snapshot_(std::move(snapshot)) {}

  // Read the contents of the snapshot and return the root node.
  fit::result<Hierarchy> Read();

 private:
  // Gets a pointer to the ParsedNode for the given index. A new ParsedObject
  // is created if one did not exist previously for the index.
  ParsedNode* GetOrCreate(BlockIndex index);

  void InnerScanBlocks();

  // Initialize an Object for the given BlockIndex.
  void InnerCreateObject(BlockIndex index, const Block* block);

  // Parse a numeric property block and attach it to the given parent.
  void InnerParseNumericProperty(ParsedNode* parent, const Block* block);

  // Parse a property block and attach it to the given parent.
  void InnerParseProperty(ParsedNode* parent, const Block* block);

  // Parse a link block and attach it to the given parent.
  void InnerParseLink(ParsedNode* parent, const Block* block);

  // Helper to interpret the given block as a NAME block and return a
  // copy of the name contents.
  fit::optional<std::string> GetAndValidateName(BlockIndex index);

  // Contents of the read VMO.
  Snapshot snapshot_;

  // Map of block index to the parsed node being constructed for that address.
  std::unordered_map<BlockIndex, ParsedNode> parsed_nodes_;
};

fit::optional<std::string> Reader::GetAndValidateName(BlockIndex index) {
  const Block* block = internal::GetBlock(&snapshot_, index);
  if (!block) {
    return {};
  }

  size_t capacity = PayloadCapacity(GetOrder(block));
  auto len = NameBlockFields::Length::Get<size_t>(block->header);
  // Do not parse the name if the declared length is greater than what the block can hold.
  if (len > capacity) {
    return {};
  }

  return std::string(block->payload_ptr(), len);
}

void Reader::InnerScanBlocks() {
  ScanBlocks(snapshot_.data(), snapshot_.size(), [this](BlockIndex index, const Block* block) {
    BlockType type = GetType(block);
    if (index == 0) {
      if (type != BlockType::kHeader) {
        return false;
      }
    } else if (type == BlockType::kNodeValue) {
      // This block defines an Object, use the value to fill out the name of
      // the ParsedNode.
      InnerCreateObject(index, block);
    } else if (type == BlockType::kIntValue || type == BlockType::kUintValue ||
               type == BlockType::kDoubleValue || type == BlockType::kArrayValue ||
               type == BlockType::kBoolValue) {
      // This block defines a numeric property for an Object, parse the
      // property into the properties field of the ParsedNode.
      auto parent_index = ValueBlockFields::ParentIndex::Get<BlockIndex>(block->header);
      InnerParseNumericProperty(GetOrCreate(parent_index), block);
    } else if (type == BlockType::kBufferValue) {
      // This block defines a property for an Object, parse the property
      // into the properties field of the ParsedNode.
      auto parent_index = ValueBlockFields::ParentIndex::Get<BlockIndex>(block->header);
      InnerParseProperty(GetOrCreate(parent_index), block);
    } else if (type == BlockType::kLinkValue) {
      // This block defines a link to an adjacent hierarchy stored outside the currently parsed one.
      // For now we parse and store the contents of the link with the NodeValue, and we will handle
      // merging trees in a separate step.
      auto parent_index = ValueBlockFields::ParentIndex::Get<BlockIndex>(block->header);
      InnerParseLink(GetOrCreate(parent_index), block);
    }

    return true;
  });
}

fit::result<Hierarchy> Reader::Read() {
  if (!snapshot_) {
    // Snapshot is invalid, return an error.
    return fit::error();
  }

  // Initialize the implicit root node, which uses index 0.
  ParsedNode root;
  root.InitializeNode("root", 0);
  parsed_nodes_.emplace(0, std::move(root));

  // Scan blocks into the parsed_node map. This creates ParsedNodes with
  // properties and an accurate count of the number of expected
  // children. ParsedNodes with a valid OBJECT_VALUE block are initialized
  // with a name and parent index.
  InnerScanBlocks();

  // Stack of completed nodes to process. Entries consist of the completed
  // Hierarchy and the block index of their parent.
  std::stack<std::pair<Hierarchy, BlockIndex>> complete_nodes;

  // Iterate over the map of parsed nodes and find those nodes that are
  // already "complete." These nodes are moved to the complete_nodes map for
  // bottom-up processing.
  for (auto it = parsed_nodes_.begin(); it != parsed_nodes_.end();) {
    if (!it->second) {
      // The node is not valid, ignore.
      it = parsed_nodes_.erase(it);
      continue;
    }

    if (it->second.is_complete()) {
      if (it->first == 0) {
        // The root is complete, return it.
        return fit::ok(std::move(it->second.hierarchy));
      }

      // The node is valid and complete, push it onto the stack.
      complete_nodes.push(std::make_pair(std::move(it->second.hierarchy), it->second.parent));
      it = parsed_nodes_.erase(it);
      continue;
    }

    ++it;
  }

  // Construct a valid hierarchy from the bottom up by attaching completed
  // nodes to their parent node. Once a parent becomes complete, add it to
  // the stack to recursively bubble the completed children towards the root.
  while (!complete_nodes.empty()) {
    auto obj = std::move(complete_nodes.top());
    complete_nodes.pop();

    // Get the parent node, which was created during block scanning.
    auto it = parsed_nodes_.find(obj.second);
    if (it == parsed_nodes_.end()) {
      // Parent node did not exist, ignore this node.
      continue;
    }
    auto* parent = &it->second;
    parent->hierarchy.add_child(std::move(obj.first));
    if (parent->is_complete()) {
      if (obj.second == 0) {
        // This was the last node that needed to be added to the root to complete it.
        // Return the root.
        return fit::ok(std::move(parent->hierarchy));
      }

      // The parent node is now complete, push it onto the stack.
      complete_nodes.push(std::make_pair(std::move(parent->hierarchy), parent->parent));
      parsed_nodes_.erase(it);
    }
  }

  // We processed all completed nodes but could not find a complete root,
  // return an error.
  return fit::error();
}

ParsedNode* Reader::GetOrCreate(BlockIndex index) {
  return &parsed_nodes_.emplace(index, ParsedNode()).first->second;
}

ArrayDisplayFormat ArrayBlockFormatToDisplay(ArrayBlockFormat format) {
  switch (format) {
    case ArrayBlockFormat::kLinearHistogram:
      return ArrayDisplayFormat::kLinearHistogram;
    case ArrayBlockFormat::kExponentialHistogram:
      return ArrayDisplayFormat::kExponentialHistogram;
    default:
      return ArrayDisplayFormat::kFlat;
  }
}

void Reader::InnerParseNumericProperty(ParsedNode* parent, const Block* block) {
  auto name = GetAndValidateName(ValueBlockFields::NameIndex::Get<size_t>(block->header));
  if (!name.has_value()) {
    return;
  }

  auto* parent_node = parent->hierarchy.node_ptr();

  BlockType type = GetType(block);
  switch (type) {
    case BlockType::kIntValue:
      parent_node->add_property(
          PropertyValue(std::move(name.value()), IntPropertyValue(block->payload.i64)));
      return;
    case BlockType::kUintValue:
      parent_node->add_property(
          PropertyValue(std::move(name.value()), UintPropertyValue(block->payload.u64)));
      return;
    case BlockType::kDoubleValue:
      parent_node->add_property(
          PropertyValue(std::move(name.value()), DoublePropertyValue(block->payload.f64)));
      return;
    case BlockType::kBoolValue:
      parent_node->add_property(
          PropertyValue(std::move(name.value()), BoolPropertyValue(block->payload.u64)));
      return;
    case BlockType::kArrayValue: {
      auto entry_type = ArrayBlockPayload::EntryType::Get<BlockType>(block->payload.u64);
      auto count = ArrayBlockPayload::Count::Get<uint8_t>(block->payload.u64);
      if (GetArraySlot<const int64_t>(block, count - 1) == nullptr) {
        // Block does not store the entire array.
        return;
      }

      auto array_format = ArrayBlockFormatToDisplay(
          ArrayBlockPayload::Flags::Get<ArrayBlockFormat>(block->payload.u64));

      if (entry_type == BlockType::kIntValue) {
        std::vector<int64_t> values;
        std::copy(GetArraySlot<const int64_t>(block, 0), GetArraySlot<const int64_t>(block, count),
                  std::back_inserter(values));
        parent_node->add_property(
            PropertyValue(std::move(name.value()), IntArrayValue(std::move(values), array_format)));
      } else if (entry_type == BlockType::kUintValue) {
        std::vector<uint64_t> values;
        std::copy(GetArraySlot<const uint64_t>(block, 0),
                  GetArraySlot<const uint64_t>(block, count), std::back_inserter(values));
        parent_node->add_property(PropertyValue(std::move(name.value()),
                                                UintArrayValue(std::move(values), array_format)));
      } else if (entry_type == BlockType::kDoubleValue) {
        std::vector<double> values;
        std::copy(GetArraySlot<const double>(block, 0), GetArraySlot<const double>(block, count),
                  std::back_inserter(values));
        parent_node->add_property(PropertyValue(std::move(name.value()),
                                                DoubleArrayValue(std::move(values), array_format)));
      }
      return;
    }
    default:
      return;
  }
}

void Reader::InnerParseProperty(ParsedNode* parent, const Block* block) {
  auto name = GetAndValidateName(ValueBlockFields::NameIndex::Get<size_t>(block->header));
  if (!name.has_value()) {
    return;
  }

  // Do not allow reading more bytes than exist in the buffer for any property. This safeguards
  // against cycles and excessive memory usage.
  size_t remaining_length = std::min(
      snapshot_.size(), PropertyBlockPayload::TotalLength::Get<size_t>(block->payload.u64));
  size_t current_offset = 0;
  std::vector<uint8_t> buf;

  BlockIndex cur_extent = PropertyBlockPayload::ExtentIndex::Get<BlockIndex>(block->payload.u64);
  auto* extent = internal::GetBlock(&snapshot_, cur_extent);
  while (remaining_length > 0) {
    if (!extent || GetType(extent) != BlockType::kExtent) {
      break;
    }
    size_t len = std::min(remaining_length, PayloadCapacity(GetOrder(extent)));
    buf.insert(buf.end(), extent->payload_ptr(), extent->payload_ptr() + len);
    remaining_length -= len;
    current_offset += len;

    BlockIndex next_extent = ExtentBlockFields::NextExtentIndex::Get<BlockIndex>(extent->header);

    extent = internal::GetBlock(&snapshot_, next_extent);
  }

  auto* parent_node = parent->hierarchy.node_ptr();
  if (PropertyBlockPayload::Flags::Get<uint8_t>(block->payload.u64) &
      static_cast<uint8_t>(PropertyBlockFormat::kBinary)) {
    parent_node->add_property(
        inspect::PropertyValue(std::move(name.value()), inspect::ByteVectorPropertyValue(buf)));
  } else {
    parent_node->add_property(
        inspect::PropertyValue(std::move(name.value()),
                               inspect::StringPropertyValue(std::string(buf.begin(), buf.end()))));
  }
}

void Reader::InnerParseLink(ParsedNode* parent, const Block* block) {
  auto name = GetAndValidateName(ValueBlockFields::NameIndex::Get<size_t>(block->header));
  if (name->empty()) {
    return;
  }

  auto content =
      GetAndValidateName(LinkBlockPayload::ContentIndex::Get<size_t>(block->payload.u64));
  if (content->empty()) {
    return;
  }

  LinkDisposition disposition;
  switch (LinkBlockPayload::Flags::Get<LinkBlockDisposition>(block->payload.u64)) {
    case LinkBlockDisposition::kChild:
      disposition = LinkDisposition::kChild;
      break;
    case LinkBlockDisposition::kInline:
      disposition = LinkDisposition::kInline;
      break;
  }

  parent->hierarchy.node_ptr()->add_link(
      LinkValue(std::move(name.value()), std::move(content.value()), disposition));
}

void Reader::InnerCreateObject(BlockIndex index, const Block* block) {
  auto name = GetAndValidateName(ValueBlockFields::NameIndex::Get<BlockIndex>(block->header));
  if (!name.has_value()) {
    return;
  }
  auto* parsed_node = GetOrCreate(index);
  auto parent_index = ValueBlockFields::ParentIndex::Get<BlockIndex>(block->header);
  parsed_node->InitializeNode(std::move(name.value()), parent_index);
  if (parent_index != index) {
    // Only link to a parent if the parent can be valid (not index 0).
    auto* parent = GetOrCreate(parent_index);
    parent->children_count += 1;
  }
}

fit::result<Hierarchy> ReadFromSnapshotTree(const SnapshotTree& tree) {
  auto read_result = internal::Reader(tree.snapshot).Read();
  if (!read_result.is_ok()) {
    return read_result;
  }

  auto ret = read_result.take_value();

  VisitHierarchiesWithLink(&ret, [&](Hierarchy* cur) {
    for (const auto& link : cur->node().links()) {
      auto it = tree.children.find(link.content());
      if (it == tree.children.end()) {
        cur->add_missing_value(MissingValueReason::kLinkNotFound, link.name());
        continue;
      }

      // TODO(crjohns): Remove recursion, or limit depth.
      auto next_result = ReadFromSnapshotTree(it->second);
      if (!next_result.is_ok()) {
        cur->add_missing_value(MissingValueReason::kLinkHierarchyParseFailure, link.name());
        continue;
      }

      if (link.disposition() == LinkDisposition::kChild) {
        // The linked hierarchy is a child of this node, add it to the list of children.
        next_result.value().node_ptr()->set_name(link.name());
        cur->add_child(next_result.take_value());
      } else if (link.disposition() == LinkDisposition::kInline) {
        // The linked hierarchy is meant to have its contents inlined into this node.
        auto next = next_result.take_value();

        // Move properties into this node.
        for (auto& prop : next.node_ptr()->take_properties()) {
          cur->node_ptr()->add_property(std::move(prop));
        }

        // Move children into this node.
        for (auto& child : next.take_children()) {
          cur->add_child(std::move(child));
        }

        // Copy missing values.
        for (const auto& missing : next.missing_values()) {
          cur->add_missing_value(missing.reason, missing.name);
        }

        // There will be no further links that have not already been processed, since we recursively
        // get the hierarchy from a SnapshotTree.
      } else {
        cur->add_missing_value(MissingValueReason::kLinkInvalid, link.name());
      }
    }
  });

  return fit::ok(std::move(ret));
}

}  // namespace internal

fit::result<Hierarchy> ReadFromSnapshot(Snapshot snapshot) {
  internal::Reader reader(std::move(snapshot));
  return reader.Read();
}

fit::result<Hierarchy> ReadFromVmo(const zx::vmo& vmo) {
  inspect::Snapshot snapshot;
  if (inspect::Snapshot::Create(std::move(vmo), &snapshot) != ZX_OK) {
    return fit::error();
  }
  return ReadFromSnapshot(std::move(snapshot));
}

fit::result<Hierarchy> ReadFromBuffer(std::vector<uint8_t> buffer) {
  inspect::Snapshot snapshot;
  if (inspect::Snapshot::Create(std::move(buffer), &snapshot) != ZX_OK) {
    // TODO(CF-865): Best-effort read of invalid snapshots.
    return fit::error();
  }
  return ReadFromSnapshot(std::move(snapshot));
}

fit::promise<Hierarchy> ReadFromInspector(Inspector inspector) {
  return SnapshotTreeFromInspector(std::move(inspector)).and_then(internal::ReadFromSnapshotTree);
}

}  // namespace inspect