1 // Copyright 2017 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "chrome/browser/devtools/serialize_host_descriptions.h"
6
7 #include <map>
8 #include <unordered_set>
9 #include <utility>
10
11 #include "base/strings/string_piece.h"
12
13 namespace {
14
15 // Returns the serialization of |root|. It expects |children[x]| to be the
16 // vector of child nodes for all descendants |x| of |root|. The serialization
17 // consists of taking the |representation| value of each node, starting in
18 // leaves, and injecting children's representations into a ListValue under the
19 // key |child_key| in the parent's |representation|. This is desctructive to the
20 // representation stored with the nodes (which gets moved out of them).
Serialize(base::StringPiece child_key,base::DictionaryValue * root,const std::map<base::DictionaryValue *,std::vector<base::DictionaryValue * >> & children)21 base::DictionaryValue Serialize(
22 base::StringPiece child_key,
23 base::DictionaryValue* root,
24 const std::map<base::DictionaryValue*, std::vector<base::DictionaryValue*>>&
25 children) {
26 auto children_list = std::make_unique<base::ListValue>();
27 auto child_it = children.find(root);
28 if (child_it != children.end()) {
29 for (base::DictionaryValue* child : child_it->second) {
30 children_list->base::Value::Append(Serialize(child_key, child, children));
31 }
32 }
33
34 if (!children_list->empty())
35 root->Set(child_key, std::move(children_list));
36 return std::move(*root);
37 }
38
39 // Takes a vector of host description and converts it into:
40 // |children|: a map from a host's representation to representations of its
41 // children,
42 // |roots|: a set of representations of hosts with no parents, and
43 // |representations|: a vector actually storing all those representations to
44 // which the rest just points.
CreateDictionaryForest(std::vector<HostDescriptionNode> hosts,std::map<base::DictionaryValue *,std::vector<base::DictionaryValue * >> * children,std::unordered_set<base::DictionaryValue * > * roots,std::vector<base::DictionaryValue> * representations)45 void CreateDictionaryForest(
46 std::vector<HostDescriptionNode> hosts,
47 std::map<base::DictionaryValue*, std::vector<base::DictionaryValue*>>*
48 children,
49 std::unordered_set<base::DictionaryValue*>* roots,
50 std::vector<base::DictionaryValue>* representations) {
51 representations->reserve(hosts.size());
52 children->clear();
53 roots->clear();
54 representations->clear();
55
56 std::map<base::StringPiece, base::DictionaryValue*> name_to_representation;
57
58 // First move the representations and map the names to them.
59 for (HostDescriptionNode& node : hosts) {
60 representations->push_back(std::move(node.representation));
61 // If there are multiple nodes with the same name, subsequent insertions
62 // will be ignored, so only the first node with a given name will be
63 // referenced by |roots| and |children|.
64 name_to_representation.emplace(node.name, &representations->back());
65 }
66
67 // Now compute children.
68 for (HostDescriptionNode& node : hosts) {
69 base::DictionaryValue* node_rep = name_to_representation[node.name];
70 base::StringPiece parent_name = node.parent_name;
71 if (parent_name.empty()) {
72 roots->insert(node_rep);
73 continue;
74 }
75 auto node_it = name_to_representation.find(parent_name);
76 if (node_it == name_to_representation.end()) {
77 roots->insert(node_rep);
78 continue;
79 }
80 (*children)[name_to_representation[parent_name]].push_back(node_rep);
81 }
82 }
83
84 } // namespace
85
SerializeHostDescriptions(std::vector<HostDescriptionNode> hosts,base::StringPiece child_key)86 base::ListValue SerializeHostDescriptions(
87 std::vector<HostDescriptionNode> hosts,
88 base::StringPiece child_key) {
89 // |representations| must outlive |children| and |roots|, which contain
90 // pointers to objects in |representations|.
91 std::vector<base::DictionaryValue> representations;
92 std::map<base::DictionaryValue*, std::vector<base::DictionaryValue*>>
93 children;
94 std::unordered_set<base::DictionaryValue*> roots;
95
96 CreateDictionaryForest(std::move(hosts), &children, &roots, &representations);
97
98 base::ListValue list_value;
99 for (auto* root : roots) {
100 list_value.base::Value::Append(Serialize(child_key, root, children));
101 }
102 return list_value;
103 }
104