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
11DependencyGraph::DependencyGraph() {}
12
13DependencyGraph::~DependencyGraph() {}
14
15void DependencyGraph::AddNode(DependencyNode* node) {
16  all_nodes_.push_back(node);
17  construction_order_.clear();
18}
19
20void 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
37void DependencyGraph::AddEdge(DependencyNode* depended,
38                              DependencyNode* dependee) {
39  edges_.insert(std::make_pair(depended, dependee));
40  construction_order_.clear();
41}
42
43bool 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
52bool 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
64bool 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
114std::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