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