Introduce SerializeDictionaryForest for devtools_target_ui

chrome/browser/devtools/devtools_targets_ui.cc

 // Copyright 2013 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/devtools_targets_ui.h"
 
 #include <memory>
 #include <utility>
 
 #include "base/location.h"
 #include "base/memory/ptr_util.h"
 #include "base/memory/weak_ptr.h"
 #include "base/single_thread_task_runner.h"
 #include "base/stl_util.h"
 #include "base/strings/string_number_conversions.h"
 #include "base/strings/stringprintf.h"
 #include "base/threading/thread_task_runner_handle.h"
 #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"
 #include "content/public/browser/devtools_agent_host.h"
 #include "content/public/browser/notification_observer.h"
 #include "content/public/browser/notification_registrar.h"
 #include "content/public/browser/notification_service.h"
 #include "content/public/browser/notification_source.h"
 #include "content/public/browser/notification_types.h"
 #include "content/public/browser/worker_service.h"
@@ skipping 195 matching lines @@
                      base::Unretained(this)),
           base::TimeDelta::FromMilliseconds(kUpdateDelay)));
 }
 
 void LocalTargetsUIHandler::UpdateTargets() {
   SendTargets(DevToolsAgentHost::GetOrCreateAll());
 }
 
 void LocalTargetsUIHandler::SendTargets(
     const content::DevToolsAgentHost::List& targets) {
-  base::ListValue list_value;
-  std::map<std::string, base::DictionaryValue*> id_to_descriptor;
+  std::vector<DictionaryForestNode> forest;
+  forest.reserve(targets.size());
 
-  targets_.clear();
-  for (scoped_refptr<DevToolsAgentHost> host : targets) {
-    targets_[host->GetId()] = host;
-    id_to_descriptor[host->GetId()] = Serialize(host).release();
-  }
+  {
+    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.

 
-  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));
+    // 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();
+    }
+
+    // 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 --------------------------------------------------------
 
 class AdbTargetsUIHandler
     : public DevToolsTargetsUIHandler,
       public DevToolsAndroidBridge::DeviceListListener {
  public:
   AdbTargetsUIHandler(const Callback& callback, Profile* profile);
   ~AdbTargetsUIHandler() override;
@@ skipping 87 matching lines @@
           kAdbBrowserChromeVersionField,
           browser->IsChrome() && !parsed.empty() ? parsed[0] : 0);
       std::string browser_id = browser->GetId();
       browser_data->SetString(kTargetIdField, browser_id);
       browser_data->SetString(kTargetSourceField, source_id());
 
       auto page_list = base::MakeUnique<base::ListValue>();
       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.
         gfx::Size screen_size = device->screen_size();
         target_data->SetInteger(kAdbScreenWidthField, screen_size.width());
         target_data->SetInteger(kAdbScreenHeightField, screen_size.height());
         targets_[host->GetId()] = host;
         page_list->Append(std::move(target_data));
       }
       browser_data->Set(kAdbPagesList, std::move(page_list));
@@ skipping 48 matching lines @@
 void DevToolsTargetsUIHandler::Open(const std::string& browser_id,
                                     const std::string& url) {
 }
 
 scoped_refptr<DevToolsAgentHost>
 DevToolsTargetsUIHandler::GetBrowserAgentHost(const std::string& browser_id) {
   return NULL;
 }
 
 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());
   target_data->SetString(kTargetTypeField, host->GetType());
   target_data->SetBoolean(kAttachedField, host->IsAttached());
   target_data->SetString(kUrlField, host->GetURL().spec());
   target_data->SetString(kNameField, host->GetTitle());
   target_data->SetString(kFaviconUrlField, host->GetFaviconURL().spec());
   target_data->SetString(kDescriptionField, host->GetDescription());
   return target_data;
@@ skipping 43 matching lines @@
     device_status_dict->SetString(kPortForwardingBrowserId,
                                   sit->first->GetId());
 
     std::string device_id = base::StringPrintf(
         kAdbDeviceIdFormat,
         sit->first->serial().c_str());
     result.Set(device_id, std::move(device_status_dict));
   }
   callback_.Run(result);
 }