components/browser_context_keyed_service/dependency_graph.cc

   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
  11 DependencyGraph::DependencyGraph() {
  12 }
  13
  14 DependencyGraph::~DependencyGraph() {
  15 }
  16
  17 void DependencyGraph::AddNode(DependencyNode* node) {
  18   all_nodes_.push_back(node);
  19   construction_order_.clear();
  20 }
  21
  22 void 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
  41 void DependencyGraph::AddEdge(DependencyNode* depended,
  42                               DependencyNode* dependee) {
  43   edges_.insert(std::make_pair(depended, dependee));
  44   construction_order_.clear();
  45 }
  46
  47 bool 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
  56 bool 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
  69 bool 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
 122 std::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 }