SerializeHostDescriptions ignores hosts with duplicated names

chrome/browser/devtools/serialize_host_descriptions.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_host_descriptions.h"
 
 #include <map>
+#include <unordered_set>
 #include <utility>
 
 #include "base/memory/ptr_util.h"
 #include "base/strings/string_piece.h"
 
 namespace {
 
 // Returns the serialization of |root|. It expects |children[x]| to be the
 // vector of child nodes for all descendants |x| of |root|. The serialization
 // consists of taking the |representation| value of each node, starting in
@@ skipping 15 matching lines @@
   }
 
   if (!children_list->empty())
     root->Set(child_key, std::move(children_list));
   return std::move(*root);
 }
 
 // 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();
   roots->clear();
   representations->clear();
 
   std::map<base::StringPiece, base::DictionaryValue*> name_to_representation;
 
   // 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.
   for (HostDescriptionNode& node : hosts) {
     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);
   }
 }
 
 }  // namespace
 
 base::ListValue SerializeHostDescriptions(
     std::vector<HostDescriptionNode> hosts,
     base::StringPiece child_key) {
   // |representations| must outlive |children| and |roots|, which contain
   // pointers to objects in |representations|.
   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);
 
   base::ListValue list_value;
   for (auto* root : roots) {
     list_value.base::Value::GetList().push_back(
         Serialize(child_key, root, children));
   }
   return list_value;
 }