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