Home | History | Annotate | Download | only in browser_context_keyed_service 
      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 }
    167