dependency_graph.cc 5.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180
  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
  3. // found in the LICENSE file.
  4. #include "components/keyed_service/core/dependency_graph.h"
  5. #include <stddef.h>
  6. #include <algorithm>
  7. #include <iterator>
  8. #include "base/containers/circular_deque.h"
  9. #include "base/containers/cxx20_erase.h"
  10. #include "base/strings/string_piece.h"
  11. namespace {
  12. // Escapes |id| to be a valid ID in the DOT format [1]. This is implemented as
  13. // enclosing the string in quotation marks, and escaping any quotation marks
  14. // found with backslashes.
  15. // [1] http://www.graphviz.org/content/dot-language
  16. std::string Escape(base::StringPiece id) {
  17. std::string result = "\"";
  18. result.reserve(id.size() + 2); // +2 for the enclosing quotes.
  19. size_t after_last_quot = 0;
  20. size_t next_quot = id.find('"');
  21. while (next_quot != base::StringPiece::npos) {
  22. result.append(id.data() + after_last_quot, next_quot - after_last_quot);
  23. result.append("\"");
  24. after_last_quot = next_quot + 1;
  25. next_quot = id.find('"', after_last_quot);
  26. }
  27. result.append(id.data() + after_last_quot, id.size() - after_last_quot);
  28. result.append("\"");
  29. return result;
  30. }
  31. } // namespace
  32. DependencyGraph::DependencyGraph() {}
  33. DependencyGraph::~DependencyGraph() {}
  34. void DependencyGraph::AddNode(DependencyNode* node) {
  35. all_nodes_.push_back(node);
  36. construction_order_.clear();
  37. }
  38. void DependencyGraph::RemoveNode(DependencyNode* node) {
  39. base::Erase(all_nodes_, node);
  40. // Remove all dependency edges that contain this node.
  41. auto it = edges_.begin();
  42. while (it != edges_.end()) {
  43. auto temp = it;
  44. ++it;
  45. if (temp->first == node || temp->second == node)
  46. edges_.erase(temp);
  47. }
  48. construction_order_.clear();
  49. }
  50. void DependencyGraph::AddEdge(DependencyNode* depended,
  51. DependencyNode* dependee) {
  52. edges_.insert(std::make_pair(depended, dependee));
  53. construction_order_.clear();
  54. }
  55. bool DependencyGraph::GetConstructionOrder(
  56. std::vector<DependencyNode*>* order) {
  57. if (construction_order_.empty() && !BuildConstructionOrder())
  58. return false;
  59. *order = construction_order_;
  60. return true;
  61. }
  62. bool DependencyGraph::GetDestructionOrder(std::vector<DependencyNode*>* order) {
  63. if (construction_order_.empty() && !BuildConstructionOrder())
  64. return false;
  65. *order = construction_order_;
  66. // Destroy nodes in reverse order.
  67. std::reverse(order->begin(), order->end());
  68. return true;
  69. }
  70. bool DependencyGraph::BuildConstructionOrder() {
  71. // Step 1: Build a set of nodes with no incoming edges.
  72. base::circular_deque<DependencyNode*> queue(all_nodes_.begin(),
  73. all_nodes_.end());
  74. for (const auto& pair : edges_)
  75. base::Erase(queue, pair.second);
  76. // Step 2: Do the Kahn topological sort.
  77. std::vector<DependencyNode*> output;
  78. EdgeMap edges(edges_);
  79. while (!queue.empty()) {
  80. DependencyNode* node = queue.front();
  81. queue.pop_front();
  82. output.push_back(node);
  83. std::pair<EdgeMap::iterator, EdgeMap::iterator> range =
  84. edges.equal_range(node);
  85. auto it = range.first;
  86. while (it != range.second) {
  87. DependencyNode* dest = it->second;
  88. auto temp = it;
  89. it++;
  90. edges.erase(temp);
  91. bool has_incoming_edges = false;
  92. for (auto jt = edges.begin(); jt != edges.end(); ++jt) {
  93. if (jt->second == dest) {
  94. has_incoming_edges = true;
  95. break;
  96. }
  97. }
  98. if (!has_incoming_edges)
  99. queue.push_back(dest);
  100. }
  101. }
  102. if (!edges.empty()) {
  103. // Dependency graph has a cycle.
  104. return false;
  105. }
  106. construction_order_ = output;
  107. return true;
  108. }
  109. std::string DependencyGraph::DumpAsGraphviz(
  110. const std::string& toplevel_name,
  111. const base::RepeatingCallback<std::string(DependencyNode*)>&
  112. node_name_callback) const {
  113. std::string result("digraph {\n");
  114. std::string escaped_toplevel_name = Escape(toplevel_name);
  115. // Make a copy of all nodes.
  116. base::circular_deque<DependencyNode*> nodes(all_nodes_.begin(),
  117. all_nodes_.end());
  118. // State all dependencies and remove |second| so we don't generate an
  119. // implicit dependency on the top level node.
  120. result.append(" /* Dependencies */\n");
  121. for (const auto& pair : edges_) {
  122. result.append(" ");
  123. result.append(Escape(node_name_callback.Run(pair.second)));
  124. result.append(" -> ");
  125. result.append(Escape(node_name_callback.Run(pair.first)));
  126. result.append(";\n");
  127. base::Erase(nodes, pair.second);
  128. }
  129. // Every node that doesn't depend on anything else will implicitly depend on
  130. // the top level node.
  131. result.append("\n /* Toplevel attachments */\n");
  132. for (DependencyNode* node : nodes) {
  133. result.append(" ");
  134. result.append(Escape(node_name_callback.Run(node)));
  135. result.append(" -> ");
  136. result.append(escaped_toplevel_name);
  137. result.append(";\n");
  138. }
  139. result.append("\n /* Toplevel node */\n");
  140. result.append(" ");
  141. result.append(escaped_toplevel_name);
  142. result.append(" [shape=box];\n");
  143. result.append("}\n");
  144. return result;
  145. }