Home | History | Annotate | Download | only in core 
      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 }
    160