| OLD | NEW |
| 1 // Copyright 2014 The Chromium Authors. All rights reserved. | 1 // Copyright 2014 The Chromium Authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include "components/keyed_service/core/dependency_graph.h" | 5 #include "components/keyed_service/core/dependency_graph.h" |
| 6 | 6 |
| 7 #include <algorithm> | 7 #include <algorithm> |
| 8 #include <deque> | 8 #include <deque> |
| 9 #include <iterator> | 9 #include <iterator> |
| 10 | 10 |
| 11 #include "base/strings/string_piece.h" | |
| 12 | |
| 13 namespace { | |
| 14 | |
| 15 // Escapes |id| to be a valid ID in the DOT format [1]. This is implemented as | |
| 16 // enclosing the string in quotation marks, and escaping any quotation marks | |
| 17 // found with backslashes. | |
| 18 // [1] http://www.graphviz.org/content/dot-language | |
| 19 std::string Escape(base::StringPiece id) { | |
| 20 std::string result = "\""; | |
| 21 result.reserve(id.size() + 2); // +2 for the enclosing quotes. | |
| 22 size_t after_last_quot = 0; | |
| 23 size_t next_quot = id.find('"'); | |
| 24 while (next_quot != base::StringPiece::npos) { | |
| 25 result.append(id.data() + after_last_quot, next_quot - after_last_quot); | |
| 26 result.append("\""); | |
| 27 after_last_quot = next_quot + 1; | |
| 28 next_quot = id.find('"', after_last_quot); | |
| 29 } | |
| 30 result.append(id.data() + after_last_quot, id.size() - after_last_quot); | |
| 31 result.append("\""); | |
| 32 return result; | |
| 33 } | |
| 34 | |
| 35 } // namespace | |
| 36 | |
| 37 DependencyGraph::DependencyGraph() {} | 11 DependencyGraph::DependencyGraph() {} |
| 38 | 12 |
| 39 DependencyGraph::~DependencyGraph() {} | 13 DependencyGraph::~DependencyGraph() {} |
| 40 | 14 |
| 41 void DependencyGraph::AddNode(DependencyNode* node) { | 15 void DependencyGraph::AddNode(DependencyNode* node) { |
| 42 all_nodes_.push_back(node); | 16 all_nodes_.push_back(node); |
| 43 construction_order_.clear(); | 17 construction_order_.clear(); |
| 44 } | 18 } |
| 45 | 19 |
| 46 void DependencyGraph::RemoveNode(DependencyNode* node) { | 20 void DependencyGraph::RemoveNode(DependencyNode* node) { |
| (...skipping 88 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 135 | 109 |
| 136 construction_order_ = output; | 110 construction_order_ = output; |
| 137 return true; | 111 return true; |
| 138 } | 112 } |
| 139 | 113 |
| 140 std::string DependencyGraph::DumpAsGraphviz( | 114 std::string DependencyGraph::DumpAsGraphviz( |
| 141 const std::string& toplevel_name, | 115 const std::string& toplevel_name, |
| 142 const base::Callback<std::string(DependencyNode*)>& node_name_callback) | 116 const base::Callback<std::string(DependencyNode*)>& node_name_callback) |
| 143 const { | 117 const { |
| 144 std::string result("digraph {\n"); | 118 std::string result("digraph {\n"); |
| 145 std::string escaped_toplevel_name = Escape(toplevel_name); | |
| 146 | 119 |
| 147 // Make a copy of all nodes. | 120 // Make a copy of all nodes. |
| 148 std::deque<DependencyNode*> nodes; | 121 std::deque<DependencyNode*> nodes; |
| 149 std::copy(all_nodes_.begin(), all_nodes_.end(), std::back_inserter(nodes)); | 122 std::copy(all_nodes_.begin(), all_nodes_.end(), std::back_inserter(nodes)); |
| 150 | 123 |
| 151 // State all dependencies and remove |second| so we don't generate an | 124 // State all dependencies and remove |second| so we don't generate an |
| 152 // implicit dependency on the top level node. | 125 // implicit dependency on the top level node. |
| 153 std::deque<DependencyNode*>::iterator nodes_end(nodes.end()); | 126 std::deque<DependencyNode*>::iterator nodes_end(nodes.end()); |
| 154 result.append(" /* Dependencies */\n"); | 127 result.append(" /* Dependencies */\n"); |
| 155 for (EdgeMap::const_iterator it = edges_.begin(); it != edges_.end(); ++it) { | 128 for (EdgeMap::const_iterator it = edges_.begin(); it != edges_.end(); ++it) { |
| 156 result.append(" "); | 129 result.append(" "); |
| 157 result.append(Escape(node_name_callback.Run(it->second))); | 130 result.append(node_name_callback.Run(it->second)); |
| 158 result.append(" -> "); | 131 result.append(" -> "); |
| 159 result.append(Escape(node_name_callback.Run(it->first))); | 132 result.append(node_name_callback.Run(it->first)); |
| 160 result.append(";\n"); | 133 result.append(";\n"); |
| 161 | 134 |
| 162 nodes_end = std::remove(nodes.begin(), nodes_end, it->second); | 135 nodes_end = std::remove(nodes.begin(), nodes_end, it->second); |
| 163 } | 136 } |
| 164 nodes.erase(nodes_end, nodes.end()); | 137 nodes.erase(nodes_end, nodes.end()); |
| 165 | 138 |
| 166 // Every node that doesn't depend on anything else will implicitly depend on | 139 // Every node that doesn't depend on anything else will implicitly depend on |
| 167 // the top level node. | 140 // the top level node. |
| 168 result.append("\n /* Toplevel attachments */\n"); | 141 result.append("\n /* Toplevel attachments */\n"); |
| 169 for (std::deque<DependencyNode*>::const_iterator it = nodes.begin(); | 142 for (std::deque<DependencyNode*>::const_iterator it = nodes.begin(); |
| 170 it != nodes.end(); | 143 it != nodes.end(); |
| 171 ++it) { | 144 ++it) { |
| 172 result.append(" "); | 145 result.append(" "); |
| 173 result.append(Escape(node_name_callback.Run(*it))); | 146 result.append(node_name_callback.Run(*it)); |
| 174 result.append(" -> "); | 147 result.append(" -> "); |
| 175 result.append(escaped_toplevel_name); | 148 result.append(toplevel_name); |
| 176 result.append(";\n"); | 149 result.append(";\n"); |
| 177 } | 150 } |
| 178 | 151 |
| 179 result.append("\n /* Toplevel node */\n"); | 152 result.append("\n /* Toplevel node */\n"); |
| 180 result.append(" "); | 153 result.append(" "); |
| 181 result.append(escaped_toplevel_name); | 154 result.append(toplevel_name); |
| 182 result.append(" [shape=box];\n"); | 155 result.append(" [shape=box];\n"); |
| 183 | 156 |
| 184 result.append("}\n"); | 157 result.append("}\n"); |
| 185 return result; | 158 return result; |
| 186 } | 159 } |
| OLD | NEW |