Introduce SerializeDictionaryForest for devtools_target_ui

chrome/browser/devtools/serialize_dictionary_forest.cc

Index: chrome/browser/devtools/serialize_dictionary_forest.cc
diff --git a/chrome/browser/devtools/serialize_dictionary_forest.cc b/chrome/browser/devtools/serialize_dictionary_forest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..d5319541f9c8f57ce3e1aef5a8670dca5837be71
--- /dev/null
+++ b/chrome/browser/devtools/serialize_dictionary_forest.cc
@@ -0,0 +1,203 @@
+// 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/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:
+  // A range expression usable in for loops.
+  class ChildrenRange {
+   public:
+    ChildrenRange(DictionaryForestNode** begin, DictionaryForestNode** end)
+        : begin_(begin), end_(end) {}
+
+    DictionaryForestNode** begin() const { return begin_; }
+    DictionaryForestNode** end() const { return end_; }
+
+   private:
+    DictionaryForestNode** const begin_;
+    DictionaryForestNode** const end_;
+  };
+
+  // |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.
+  ChildrenRange For(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() {}
+
+ChildrenRepresentation::ChildrenRange ChildrenRepresentation::For(
+    DictionaryForestNode* node) {
+  OffsetLength ol = children_locations_.locations.at(node);
+  DictionaryForestNode** first_child = &children_locations_.children[ol.offset];
+  return ChildrenRange(first_child, first_child + ol.length);

[jdoerrie, 2017/04/18 09:57:44]

Nit: 
return {first_child, first_child + ol.length};

This matches your style in the unit test when you return DictionaryForestNodes.

[vabr (Chromium), 2017/04/19 11:03:17]

Acknowledged, but changed due to getting rid of ChildrenRange.

+}
+
+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));
+  }
+  // TODO(crbug.com/646113) Get rid of the unique_ptr once ListValue::Append
+  // takes the value directly.
+  children_weak->Append(
+      base::MakeUnique<base::Value>(std::move(child_description)));

[jdoerrie, 2017/04/19 08:35:00]

FYI, r465517 just landed, so you could get rid of the unique_ptr now:

children_weak->base::Value::GetList().push_back(std::move(child_description));

Unfortunately, currently you need to fully qualify GetList when invoking it on a
ListValue, because otherwise ListValue's own GetList methods
(https://codesearch.chromium.org/chromium/src/base/values.h?l=437,438) shadow it
and the compiler complains.

[vabr (Chromium), 2017/04/19 11:03:17]

Cool, thanks!

+}
+
+}  // 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);
+    for (DictionaryForestNode* child : children.For(node)) {
+      // Once |node| is removed, all of its children have 0 incoming edges.
+      no_incoming_edges.push_back(child);

[jdoerrie, 2017/04/18 09:57:44]

Another small suggestion:
Given that the children for a given node are contiguous in memory by
construction, you could consider dropping the for loop and ChildrenRange struct
in favor of range-based |std::vector::insert| or |std::copy|. For this to work
|For| would need to return an iterator pair. It's up to you, this code is very
clear as it is.

[vabr (Chromium), 2017/04/19 11:03:17]

I like that, ChildrenRange was too much boilerplate.

+    }
+  }
+
+  // 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 (auto node_it = sorted.rbegin(); node_it != sorted.rend(); ++node_it) {
+    DictionaryForestNode* node = *node_it;
+    DictionaryForestNode* parent = node->parent;
+    if (parent) {
+      InjectChildDescription(std::move(node->representation), parent,
+                             child_key);
+    } else {
+      // TODO(crbug.com/646113) Get rid of the unique_ptr once ListValue::Append
+      // takes the value directly.
+      roots.Append(
+          base::MakeUnique<base::Value>(std::move(node->representation)));

[jdoerrie, 2017/04/19 08:35:00]

Same here, this could be:

roots.base::Value::GetList().push_back(std::move(node->representation));

[vabr (Chromium), 2017/04/19 11:03:17]

Done.

+    }
+  }
+
+  return roots;
+}