SerializeHostDescriptions ignores hosts with duplicated names

chrome/browser/devtools/serialize_host_descriptions.cc

Index: chrome/browser/devtools/serialize_host_descriptions.cc
diff --git a/chrome/browser/devtools/serialize_host_descriptions.cc b/chrome/browser/devtools/serialize_host_descriptions.cc
index 5e5c19f7825a076dff8cbf99d41501884c536fb5..370694dc156caf1f17b717eef10cf99f948522c8 100644
--- a/chrome/browser/devtools/serialize_host_descriptions.cc
+++ b/chrome/browser/devtools/serialize_host_descriptions.cc
@@ -5,6 +5,7 @@
 #include "chrome/browser/devtools/serialize_host_descriptions.h"
 
 #include <map>
+#include <unordered_set>
 #include <utility>
 
 #include "base/memory/ptr_util.h"
@@ -40,14 +41,14 @@ base::DictionaryValue Serialize(
 // Takes a vector of host description and converts it into:
 // |children|: a map from a host's representation to representations of its
 //             children,
-// |roots|: a vector of representations of hosts with no parents, and
+// |roots|: a set of representations of hosts with no parents, and
 // |representations|: a vector actually storing all those representations to
 //                    which the rest just points.
 void CreateDictionaryForest(
     std::vector<HostDescriptionNode> hosts,
     std::map<base::DictionaryValue*, std::vector<base::DictionaryValue*>>*
         children,
-    std::vector<base::DictionaryValue*>* roots,
+    std::unordered_set<base::DictionaryValue*>* roots,

[vabr (Chromium), 2017/04/23 11:47:32]

I chose unordered_set, because I don't care about the order, just uniqueness and
efficient inserting. I did not chose base::flat_set, because IIUC, that might
harm efficient inserting (O(N^2) uniqueness check on insert).

     std::vector<base::DictionaryValue>* representations) {
   representations->reserve(hosts.size());
   children->clear();
@@ -59,7 +60,17 @@ void CreateDictionaryForest(
   // First move the representations and map the names to them.
   for (HostDescriptionNode& node : hosts) {
     representations->push_back(std::move(node.representation));
-    name_to_representation[node.name] = &representations->back();
+    // If there are multiple nodes with the same name, subsequent insertions
+    // will be ignored, so only the first node with a given name will be
+    // referenced by |roots| and |children|.
+    //
+    // Note that explicitly creating a StringPiece from |node.name| is
+    // necessary, otherwise std::make_pair first creates a pair of a temporary
+    // std::string copied from |node.name|, then the pair gets implicitly cast,
+    // and the key in the map will be a StringPiece referencing the temporary
+    // copied string instead of the one in |node|.
+    name_to_representation.insert(
+        std::make_pair(base::StringPiece(node.name), &representations->back()));

[jdoerrie, 2017/04/23 18:16:11]

Recently the Linux sysroot got upgraded (crbug.com/701894), which updated GCC
4.8. This results in more support of C++11 features, in particular
std::map::emplace. This means you should be able to replace this by
|name_to_representation.emplace(node.name, &representations-back)|, since the
arguments will be perfectly forwarded (ie no temporaries) and the StringPiece in
the map will point to the correct string.

[vabr (Chromium), 2017/04/23 18:52:13]

Thanks for the information!

However, looking at https://chromium-cpp.appspot.com/, it still warns that map's
emplace might not be supported. It also points out that emplace might not always
be a readability win. I'm not sure in this case, so my feeling would be to keep
insert().

[jdoerrie, 2017/04/24 09:09:54]

Fair point, that sentence probably should be updated. I'll make a new comment in
the corresponding chromium-dev thread.

Regarding readability: Given that |std::map::emplace| was not supported until
recently, I suspect the concern was mostly regarding choosing
|std::vector::emplace_back| over |std::vector::push_back|. There it is certainly
a valid point. Further background can be found here: http://go/totw/112.

For the std::map case here I think it's both a clarity and performance win, but
that is only my personal opinion. While http://go/totw/67 tends to agree with
me, this is only an internal guideline and I'll understand if you want to stay
with |insert| here.

[vabr (Chromium), 2017/04/24 14:51:54]

Thanks! I actually like how using emplace simplified the code and removed the
comment.

   }
 
   // Now compute children.
@@ -67,12 +78,12 @@ void CreateDictionaryForest(
     base::DictionaryValue* node_rep = name_to_representation[node.name];
     base::StringPiece parent_name = node.parent_name;
     if (parent_name.empty()) {
-      roots->push_back(node_rep);
+      roots->insert(node_rep);
       continue;
     }
     auto node_it = name_to_representation.find(parent_name);
     if (node_it == name_to_representation.end()) {
-      roots->push_back(node_rep);
+      roots->insert(node_rep);
       continue;
     }
     (*children)[name_to_representation[parent_name]].push_back(node_rep);
@@ -89,7 +100,7 @@ base::ListValue SerializeHostDescriptions(
   std::vector<base::DictionaryValue> representations;
   std::map<base::DictionaryValue*, std::vector<base::DictionaryValue*>>
       children;
-  std::vector<base::DictionaryValue*> roots;
+  std::unordered_set<base::DictionaryValue*> roots;
 
   CreateDictionaryForest(std::move(hosts), &children, &roots, &representations);