Introduce SerializeDictionaryForest for devtools_target_ui

chrome/browser/devtools/devtools_targets_ui.cc

Index: chrome/browser/devtools/devtools_targets_ui.cc
diff --git a/chrome/browser/devtools/devtools_targets_ui.cc b/chrome/browser/devtools/devtools_targets_ui.cc
index f45c2fbf353c7d13b5ac2caf149a229ea76eff5d..c199dd22fce74e2588130cf6d7a82876028ec62f 100644
--- a/chrome/browser/devtools/devtools_targets_ui.cc
+++ b/chrome/browser/devtools/devtools_targets_ui.cc
@@ -18,6 +18,7 @@
 #include "base/values.h"
 #include "base/version.h"
 #include "chrome/browser/devtools/device/devtools_android_bridge.h"
+#include "chrome/browser/devtools/serialize_dictionary_forest.h"
 #include "content/public/browser/browser_child_process_observer.h"
 #include "content/public/browser/browser_thread.h"
 #include "content/public/browser/child_process_data.h"
@@ -233,35 +234,34 @@ void LocalTargetsUIHandler::UpdateTargets() {
 
 void LocalTargetsUIHandler::SendTargets(
     const content::DevToolsAgentHost::List& targets) {
-  base::ListValue list_value;
-  std::map<std::string, base::DictionaryValue*> id_to_descriptor;
-
-  targets_.clear();
-  for (scoped_refptr<DevToolsAgentHost> host : targets) {
-    targets_[host->GetId()] = host;
-    id_to_descriptor[host->GetId()] = Serialize(host).release();
-  }
+  std::vector<DictionaryForestNode> forest;
+  forest.reserve(targets.size());
+
+  {
+    std::map<std::string, DictionaryForestNode*> id_to_node;

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

Small suggestion:
Given that you care about performance and don't use the sorted-ness of the map
you could consider replacing std::map with std::unordered_map or base::flat_map.
This applies to the other usages of std::map in serialize_dictionary_forest.cc
as well.

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

Thanks!

What I'm reading in the description of base::flat_set (which should also apply
to flat_map), is that the continguous storage (vector instead of the search
tree) is beneficial for iteration and copying of such maps. However, what I do
with id_to_node and also locations and free_slots (the only maps in
serialize_dictionary_forest.cc) is mostly insertion and retrieval, for which
having the storage in a search tree seems better to me. Did I misunderstood the
advantages of the flat containers?

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

No, you are right, the main advantages of flat containers do not apply here.
Nevertheless, std::unordered_map should be better (at least asymptotically), but
I never actually checked whether there is a significant difference in practice.
So leaving std::map is definitely fine.

+
+    // Reset |targets_| and fill the forest with nodes without edges.
+    targets_.clear();
+    for (const scoped_refptr<DevToolsAgentHost>& host : targets) {
+      targets_[host->GetId()] = host;
+      forest.push_back({nullptr, *Serialize(host.get())});
+      id_to_node[host->GetId()] = &forest.back();
+    }
 
-  for (auto& it : targets_) {
-    scoped_refptr<DevToolsAgentHost> host = it.second;
-    base::DictionaryValue* descriptor = id_to_descriptor[host->GetId()];
-    DCHECK(descriptor);
-    std::string parent_id = host->GetParentId();
-    if (parent_id.empty() || id_to_descriptor.count(parent_id) == 0) {
-      list_value.Append(base::WrapUnique(descriptor));
-    } else {
-      base::DictionaryValue* parent = id_to_descriptor[parent_id];
-      base::ListValue* guests_weak = NULL;
-      if (!parent->GetList(kGuestList, &guests_weak)) {
-        auto guests = base::MakeUnique<base::ListValue>();
-        guests_weak = guests.get();
-        parent->Set(kGuestList, std::move(guests));
-      }
-      guests_weak->Append(base::WrapUnique(descriptor));
+    // Now add the edges.
+    for (const scoped_refptr<DevToolsAgentHost>& host : targets) {
+      std::string parent_id = host->GetParentId();
+      if (parent_id.empty())
+        continue;
+      auto node_it = id_to_node.find(parent_id);
+      if (node_it == id_to_node.end())
+        continue;
+      id_to_node[host->GetId()]->parent = node_it->second;
     }
   }
 
-  SendSerializedTargets(list_value);
+  SendSerializedTargets(
+      SerializeDictionaryForest(std::move(forest), kGuestList));

[dgozman, 2017/04/17 21:22:43]

Since there could be no more than one parent, I have a feeling this could be
done in less complicated manner by traversing hosts from parent to children.
WDYT?

map<string, vector<host>> children;
map<string, host> roots;
for host: targets
  if host.parent
    children[host.parent.id].push_back(host)
  else
    roots.push_back(host)
for root : roots:
  list_value.append(serialize(root, children))  
SendSerializedTargets(list_value)


serialize(host, children):
  append data to dictionary
  for child : children[host.id]
    children_list.append(serialize(child, children))
  if children_list.length
    dictionary.set(kGuestList, children_list)
  return dictionary

[vabr (Chromium), 2017/04/18 08:52:49]

Thanks for the suggestion.

One thing which is less complicated in your suggestion is keeping the whole code
here in LocalTargetsUIHandler::SendTargets and dealing with DevToolsAgentsHost
directly. In my code I pulled that out into SerializeDictionaryForest and used
the DictionaryForestNode abstraction to be able to unittest this properly. I
would like to keep that testability, because I suspect it was the absence of
unittests which let the bug creep in unnoticed.

Another simplification is using the map<..., vector<>> to compute children. In
my current CL I use the ChildrenRepresentation object. The latter is slightly
more complicated, but well encapsulated (i.e., does not interfere with the rest)
and more efficient -- instead of allocating tiny vectors for every parent node,
it uses one big vector to store all children. I'm happy to replace
ChildrenRepresentation with the inlined map and for-loop if you feel that the
clarity win is substantial enough and beats the performance.

A third simplification would be to replace Kahn's algorithm with the recursive
"serialize" function performing the DFS, as you suggest. Both are performing a
topological sort; in the current CL I separate the sorting from the processing
to make it easier to prove correctness of each of them. Avoiding the non-tail
recursion in "serialize" is also better for performance.

I'd like to hear your opinion about the above parts of the suggested change to
the current code. You are the code OWNER, so I will follow your advice, as long
as you considered the known pros and cons and the resulting code is (easily)
unit-tested.

 }
 
 // AdbTargetsUIHandler --------------------------------------------------------
@@ -369,7 +369,8 @@ void AdbTargetsUIHandler::DeviceListChanged(
       remote_browsers_[browser_id] = browser;
       for (const auto& page : browser->pages()) {
         scoped_refptr<DevToolsAgentHost> host = page->CreateTarget();
-        std::unique_ptr<base::DictionaryValue> target_data = Serialize(host);
+        std::unique_ptr<base::DictionaryValue> target_data =
+            Serialize(host.get());
         // Pass the screen size in the target object to make sure that
         // the caching logic does not prevent the target item from updating
         // when the screen size changes.
@@ -438,7 +439,7 @@ DevToolsTargetsUIHandler::GetBrowserAgentHost(const std::string& browser_id) {
 }
 
 std::unique_ptr<base::DictionaryValue> DevToolsTargetsUIHandler::Serialize(
-    scoped_refptr<DevToolsAgentHost> host) {
+    DevToolsAgentHost* host) {
   auto target_data = base::MakeUnique<base::DictionaryValue>();
   target_data->SetString(kTargetSourceField, source_id_);
   target_data->SetString(kTargetIdField, host->GetId());