components/keyed_service/core/dependency_graph.cc

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