• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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