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
5 #include "components/keyed_service/core/dependency_graph.h"
6
7 #include <algorithm>
8 #include <deque>
9 #include <iterator>
10
DependencyGraph()11 DependencyGraph::DependencyGraph() {}
12
~DependencyGraph()13 DependencyGraph::~DependencyGraph() {}
14
AddNode(DependencyNode * node)15 void DependencyGraph::AddNode(DependencyNode* node) {
16 all_nodes_.push_back(node);
17 construction_order_.clear();
18 }
19
RemoveNode(DependencyNode * node)20 void DependencyGraph::RemoveNode(DependencyNode* node) {
21 all_nodes_.erase(std::remove(all_nodes_.begin(), all_nodes_.end(), node),
22 all_nodes_.end());
23
24 // Remove all dependency edges that contain this node.
25 EdgeMap::iterator it = edges_.begin();
26 while (it != edges_.end()) {
27 EdgeMap::iterator temp = it;
28 ++it;
29
30 if (temp->first == node || temp->second == node)
31 edges_.erase(temp);
32 }
33
34 construction_order_.clear();
35 }
36
AddEdge(DependencyNode * depended,DependencyNode * dependee)37 void DependencyGraph::AddEdge(DependencyNode* depended,
38 DependencyNode* dependee) {
39 edges_.insert(std::make_pair(depended, dependee));
40 construction_order_.clear();
41 }
42
GetConstructionOrder(std::vector<DependencyNode * > * order)43 bool DependencyGraph::GetConstructionOrder(
44 std::vector<DependencyNode*>* order) {
45 if (construction_order_.empty() && !BuildConstructionOrder())
46 return false;
47
48 *order = construction_order_;
49 return true;
50 }
51
GetDestructionOrder(std::vector<DependencyNode * > * order)52 bool DependencyGraph::GetDestructionOrder(std::vector<DependencyNode*>* order) {
53 if (construction_order_.empty() && !BuildConstructionOrder())
54 return false;
55
56 *order = construction_order_;
57
58 // Destroy nodes in reverse order.
59 std::reverse(order->begin(), order->end());
60
61 return true;
62 }
63
BuildConstructionOrder()64 bool DependencyGraph::BuildConstructionOrder() {
65 // Step 1: Build a set of nodes with no incoming edges.
66 std::deque<DependencyNode*> queue;
67 std::copy(all_nodes_.begin(), all_nodes_.end(), std::back_inserter(queue));
68
69 std::deque<DependencyNode*>::iterator queue_end = queue.end();
70 for (EdgeMap::const_iterator it = edges_.begin(); it != edges_.end(); ++it) {
71 queue_end = std::remove(queue.begin(), queue_end, it->second);
72 }
73 queue.erase(queue_end, queue.end());
74
75 // Step 2: Do the Kahn topological sort.
76 std::vector<DependencyNode*> output;
77 EdgeMap edges(edges_);
78 while (!queue.empty()) {
79 DependencyNode* node = queue.front();
80 queue.pop_front();
81 output.push_back(node);
82
83 std::pair<EdgeMap::iterator, EdgeMap::iterator> range =
84 edges.equal_range(node);
85 EdgeMap::iterator it = range.first;
86 while (it != range.second) {
87 DependencyNode* dest = it->second;
88 EdgeMap::iterator temp = it;
89 it++;
90 edges.erase(temp);
91
92 bool has_incoming_edges = false;
93 for (EdgeMap::iterator jt = edges.begin(); jt != edges.end(); ++jt) {
94 if (jt->second == dest) {
95 has_incoming_edges = true;
96 break;
97 }
98 }
99
100 if (!has_incoming_edges)
101 queue.push_back(dest);
102 }
103 }
104
105 if (!edges.empty()) {
106 // Dependency graph has a cycle.
107 return false;
108 }
109
110 construction_order_ = output;
111 return true;
112 }
113
DumpAsGraphviz(const std::string & toplevel_name,const base::Callback<std::string (DependencyNode *)> & node_name_callback) const114 std::string DependencyGraph::DumpAsGraphviz(
115 const std::string& toplevel_name,
116 const base::Callback<std::string(DependencyNode*)>& node_name_callback)
117 const {
118 std::string result("digraph {\n");
119
120 // Make a copy of all nodes.
121 std::deque<DependencyNode*> nodes;
122 std::copy(all_nodes_.begin(), all_nodes_.end(), std::back_inserter(nodes));
123
124 // State all dependencies and remove |second| so we don't generate an
125 // implicit dependency on the top level node.
126 std::deque<DependencyNode*>::iterator nodes_end(nodes.end());
127 result.append(" /* Dependencies */\n");
128 for (EdgeMap::const_iterator it = edges_.begin(); it != edges_.end(); ++it) {
129 result.append(" ");
130 result.append(node_name_callback.Run(it->second));
131 result.append(" -> ");
132 result.append(node_name_callback.Run(it->first));
133 result.append(";\n");
134
135 nodes_end = std::remove(nodes.begin(), nodes_end, it->second);
136 }
137 nodes.erase(nodes_end, nodes.end());
138
139 // Every node that doesn't depend on anything else will implicitly depend on
140 // the top level node.
141 result.append("\n /* Toplevel attachments */\n");
142 for (std::deque<DependencyNode*>::const_iterator it = nodes.begin();
143 it != nodes.end();
144 ++it) {
145 result.append(" ");
146 result.append(node_name_callback.Run(*it));
147 result.append(" -> ");
148 result.append(toplevel_name);
149 result.append(";\n");
150 }
151
152 result.append("\n /* Toplevel node */\n");
153 result.append(" ");
154 result.append(toplevel_name);
155 result.append(" [shape=box];\n");
156
157 result.append("}\n");
158 return result;
159 }
160