Introduce SerializeDictionaryForest for devtools_target_ui

chrome/browser/devtools/serialize_dictionary_forest.cc

+// Copyright 2017 The Chromium 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 "chrome/browser/devtools/serialize_dictionary_forest.h"
+
+#include <map>
+#include <utility>
+
+#include "base/containers/adapters.h"
+#include "base/macros.h"
+#include "base/memory/ptr_util.h"
+
+namespace {
+
+// Helper class; takes a forest represented by nodes with pointers from
+// children to parents and computes a representation allowing to iterate over
+// children of a given parent efficiently.
+class ChildrenRepresentation {
+ public:
+  using ChildIter = std::vector<DictionaryForestNode*>::iterator;

[jdoerrie, 2017/04/19 11:45:51]

nit: This could be a const_iterator.

Also some pointers in the code below could be const, but I'm not sure whether
this is worth the effort in this case.

[vabr (Chromium), 2017/04/19 16:25:49]

[EDIT: This is now obsolete, the code has changed.]

You are right, the compiler is fine with this being const_iterator.

With the const pointers, if you meant switching to const DictionaryForstNode*,
I'm not so sure -- ultimately they end up being passed to |sorted|, from where
the nodes are indeed modified.

+
+  // |forest| must outlive this class.
+  explicit ChildrenRepresentation(std::vector<DictionaryForestNode>* forest);
+
+  ~ChildrenRepresentation();
+
+  // Returns a range with all nodes from |forest_| which have |node| as parent.
+  std::pair<ChildIter, ChildIter> Children(DictionaryForestNode* node);
+
+ private:
+  // Just a named pair of offset and length.
+  struct OffsetLength {
+    size_t offset = 0;
+    size_t length = 0;
+  };
+
+  // Another named pair:
+  // |children| stores pointers to nodes in consecutive blocks, such that
+  // within each block, all nodes have the same parent. |locations| maps
+  // parents to offset and length of the corresponding block of children in
+  // |children|.
+  struct ChildrenLocations {
+    std::vector<DictionaryForestNode*> children;
+    std::map<DictionaryForestNode*, OffsetLength> locations;
+  };
+
+  // Used by the constructor to compute the edges from parents to children in
+  // |forest|.
+  static ChildrenLocations InitFromForest(
+      std::vector<DictionaryForestNode>* forest);
+
+  ChildrenLocations children_locations_;
+
+  DISALLOW_COPY_AND_ASSIGN(ChildrenRepresentation);
+};
+
+ChildrenRepresentation::ChildrenRepresentation(
+    std::vector<DictionaryForestNode>* forest)
+    : children_locations_(InitFromForest(forest)) {}
+
+ChildrenRepresentation::~ChildrenRepresentation() {}
+
+std::pair<ChildrenRepresentation::ChildIter, ChildrenRepresentation::ChildIter>
+ChildrenRepresentation::Children(DictionaryForestNode* node) {
+  OffsetLength ol = children_locations_.locations.at(node);
+  ChildIter first_child = children_locations_.children.begin() + ol.offset;
+  return std::make_pair(first_child, first_child + ol.length);
+}
+
+ChildrenRepresentation::ChildrenLocations
+ChildrenRepresentation::InitFromForest(
+    std::vector<DictionaryForestNode>* forest) {
+  ChildrenLocations result;
+  // There are always less children than all nodes in the |forest|, so resizing
+  // the vector below is a little wasteful. But it keeps the code simple.
+  result.children.resize(forest->size());
+
+  // In the first pass, only count the number of children.
+  for (DictionaryForestNode& node : *forest) {
+    DictionaryForestNode* parent = node.parent;
+    if (!parent)
+      continue;
+    ++result.locations[parent].length;
+  }
+
+  // In the second pass, allocate the offsets and initialize |free_slots|,
+  // which tells for every node where to put its next child in
+  // |result.children|.
+  size_t next_free = 0;
+  std::map<DictionaryForestNode*, size_t> free_slots;
+  for (DictionaryForestNode& node : *forest) {
+    result.locations[&node].offset = next_free;
+    free_slots[&node] = next_free;
+    next_free += result.locations[&node].length;
+  }
+
+  // In the last pass, populate |result.children|.
+  for (DictionaryForestNode& node : *forest) {
+    DictionaryForestNode* parent = node.parent;
+    if (!parent)
+      continue;
+    const size_t offset = free_slots[parent];
+    ++free_slots[parent];
+    result.children[offset] = &node;
+  }
+
+  return result;
+}
+
+// Appends |child_description| to a ListValue under key |child_key| in
+// |parent->representation|, creating said ListValue if needed.
+void InjectChildDescription(base::DictionaryValue child_description,
+                            DictionaryForestNode* parent,
+                            base::StringPiece child_key) {
+  base::ListValue* children_weak = nullptr;
+  base::DictionaryValue* parent_rep = &parent->representation;
+  if (!parent_rep->GetList(child_key, &children_weak)) {
+    auto children = base::MakeUnique<base::ListValue>();
+    children_weak = children.get();
+    parent_rep->Set(child_key, std::move(children));
+  }
+  children_weak->base::Value::GetList().push_back(std::move(child_description));
+}
+
+}  // namespace
+
+base::ListValue SerializeDictionaryForest(
+    std::vector<DictionaryForestNode> forest,
+    base::StringPiece child_key) {
+  // To serialize |forest|, DictionaryValue descriptions of child nodes need to
+  // be injected into DictionaryValue descriptions of their parents. That means
+  // the forest needs to be processed in topological order, understanding the
+  // direction of edges to go from child to parent.
+  //
+  // However, computing a topological order using Kahn's algorithm is easier
+  // for forests where the edge direction goes from parents to children: the
+  // condition for inserting a node into the resulting sorted list, "if node
+  // has no other incoming edges", is trivial, because every node has at most
+  // one parent and hence at most one incoming edge.
+  //
+  // Luckily, the reverse of a topological order of a graph is a topological
+  // order of the same graph with edges reversed. So here first the easy
+  // topological order for (parent -> child) edges is computed, and then
+  // processed in reverse to serialize the forest.
+  ChildrenRepresentation children(&forest);
+
+  std::vector<DictionaryForestNode*> sorted;
+  sorted.reserve(forest.size());
+
+  // Initialize the algorithm with nodes which come first in topological order.
+  std::vector<DictionaryForestNode*> no_incoming_edges;
+  no_incoming_edges.reserve(forest.size());
+  for (DictionaryForestNode& node : forest) {
+    if (!node.parent)
+      no_incoming_edges.push_back(&node);
+  }
+
+  // Iteratively add more nodes, respecting the topological order.
+  while (!no_incoming_edges.empty()) {
+    DictionaryForestNode* node = no_incoming_edges.back();
+    no_incoming_edges.pop_back();
+    sorted.push_back(node);
+    // Once |node| is removed, all of its children have 0 incoming edges.
+    auto child_range = children.Children(node);
+    no_incoming_edges.insert(no_incoming_edges.end(), child_range.first,
+                             child_range.second);
+  }
+
+  // Now let's build the representation: injecting DictionaryValues of children
+  // into those of their parents, and adding the roots to the returned
+  // ListValue.
+  base::ListValue roots;
+  for (DictionaryForestNode* node : base::Reversed(sorted)) {
+    DictionaryForestNode* parent = node->parent;
+    if (parent) {
+      InjectChildDescription(std::move(node->representation), parent,
+                             child_key);
+    } else {
+      roots.base::Value::GetList().push_back(std::move(node->representation));
+    }
+  }
+
+  return roots;
+}