Extract DependencyGraph from ProfileDependencyManager.

chrome/browser/profiles/profile_dependency_manager.cc

Index: chrome/browser/profiles/profile_dependency_manager.cc
diff --git a/chrome/browser/profiles/profile_dependency_manager.cc b/chrome/browser/profiles/profile_dependency_manager.cc
index 4a568a78d00094676583229df1830e3602ebad6d..1fdafb22a4e199bf735da5eab68c3b364ed2d29f 100644
--- a/chrome/browser/profiles/profile_dependency_manager.cc
+++ b/chrome/browser/profiles/profile_dependency_manager.cc
@@ -131,34 +131,17 @@ class Profile;
 
 void ProfileDependencyManager::AddComponent(
     ProfileKeyedBaseFactory* component) {
-  all_components_.push_back(component);
-  destruction_order_.clear();
+  dependency_graph_.AddNode(component);
 }
 
 void ProfileDependencyManager::RemoveComponent(
     ProfileKeyedBaseFactory* component) {
-  all_components_.erase(std::remove(all_components_.begin(),
-                                    all_components_.end(),
-                                    component),
-                        all_components_.end());
-
-  // Remove all dependency edges that contain this component.
-  EdgeMap::iterator it = edges_.begin();
-  while (it != edges_.end()) {
-    EdgeMap::iterator temp = it;
-    ++it;
-
-    if (temp->first == component || temp->second == component)
-      edges_.erase(temp);
-  }
-
-  destruction_order_.clear();
+  dependency_graph_.RemoveNode(component);
 }
 
 void ProfileDependencyManager::AddEdge(ProfileKeyedBaseFactory* depended,
                                        ProfileKeyedBaseFactory* dependee) {
-  edges_.insert(std::make_pair(depended, dependee));
-  destruction_order_.clear();
+  dependency_graph_.AddEdge(depended, dependee);
 }
 
 void ProfileDependencyManager::CreateProfileServices(Profile* profile,
@@ -172,35 +155,48 @@ void ProfileDependencyManager::CreateProfileServices(Profile* profile,
 
   AssertFactoriesBuilt();
 
-  if (destruction_order_.empty())
-    BuildDestructionOrder(profile);
+  std::vector<DependencyNode*> construction_order;
+  if (!dependency_graph_.GetConstructionOrder(&construction_order)) {
+    NOTREACHED();
+  }
+
+#ifndef NDEBUG
+  DumpProfileDependencies(profile);
+#endif
+
+  for (size_t i = 0; i < construction_order.size(); i++) {
+    ProfileKeyedBaseFactory* factory =
+        static_cast<ProfileKeyedBaseFactory*>(construction_order[i]);
 
-  // Iterate in reverse destruction order for creation.
-  for (std::vector<ProfileKeyedBaseFactory*>::reverse_iterator rit =
-           destruction_order_.rbegin(); rit != destruction_order_.rend();
-       ++rit) {
     if (!profile->IsOffTheRecord()) {
       // We only register preferences on normal profiles because the incognito
       // profile shares the pref service with the normal one.
-      (*rit)->RegisterUserPrefsOnProfile(profile);
+      factory->RegisterUserPrefsOnProfile(profile);
     }
 
-    if (is_testing_profile && (*rit)->ServiceIsNULLWhileTesting()) {
-      (*rit)->SetEmptyTestingFactory(profile);
-    } else if ((*rit)->ServiceIsCreatedWithProfile()) {
+    if (is_testing_profile && factory->ServiceIsNULLWhileTesting()) {
+      factory->SetEmptyTestingFactory(profile);
+    } else if (factory->ServiceIsCreatedWithProfile()) {
       // Create the service.
-      (*rit)->CreateServiceNow(profile);
+      factory->CreateServiceNow(profile);
     }
   }
 }
 
 void ProfileDependencyManager::DestroyProfileServices(Profile* profile) {
-  if (destruction_order_.empty())
-    BuildDestructionOrder(profile);
+  std::vector<DependencyNode*> destruction_order;
+  if (!dependency_graph_.GetDestructionOrder(&destruction_order)) {
+    NOTREACHED();
+  }
 
-  for (std::vector<ProfileKeyedBaseFactory*>::const_iterator it =
-           destruction_order_.begin(); it != destruction_order_.end(); ++it) {
-    (*it)->ProfileShutdown(profile);
+#ifndef NDEBUG
+  DumpProfileDependencies(profile);
+#endif
+
+  for (size_t i = 0; i < destruction_order.size(); i++) {
+    ProfileKeyedBaseFactory* factory =
+        static_cast<ProfileKeyedBaseFactory*>(destruction_order[i]);
+    factory->ProfileShutdown(profile);
   }
 
 #ifndef NDEBUG
@@ -208,9 +204,10 @@ void ProfileDependencyManager::DestroyProfileServices(Profile* profile) {
   dead_profile_pointers_.insert(profile);
 #endif
 
-  for (std::vector<ProfileKeyedBaseFactory*>::const_iterator it =
-           destruction_order_.begin(); it != destruction_order_.end(); ++it) {
-    (*it)->ProfileDestroyed(profile);
+  for (size_t i = 0; i < destruction_order.size(); i++) {
+    ProfileKeyedBaseFactory* factory =
+        static_cast<ProfileKeyedBaseFactory*>(destruction_order[i]);
+    factory->ProfileDestroyed(profile);
   }
 }
 
@@ -230,8 +227,17 @@ ProfileDependencyManager* ProfileDependencyManager::GetInstance() {
   return Singleton<ProfileDependencyManager>::get();
 }
 
+namespace {
+
+std::string ProfileKeyedBaseFactoryGetNodeName(DependencyNode* node) {
+  return static_cast<ProfileKeyedBaseFactory*>(node)->name();
+}
+
+}  // namespace
+
 ProfileDependencyManager::ProfileDependencyManager()
-    : built_factories_(false) {
+    : built_factories_(false),
+      dependency_graph_(base::Bind(&ProfileKeyedBaseFactoryGetNodeName)) {
 }
 
 ProfileDependencyManager::~ProfileDependencyManager() {}
@@ -386,113 +392,16 @@ void ProfileDependencyManager::AssertFactoriesBuilt() {
   built_factories_ = true;
 }
 
-void ProfileDependencyManager::BuildDestructionOrder(Profile* profile) {
-#if !defined(NDEBUG)
+#ifndef NDEBUG
+void ProfileDependencyManager::DumpProfileDependencies(Profile* profile) {
   // Whenever we try to build a destruction ordering, we should also dump a
   // dependency graph to "/path/to/profile/profile-dependencies.dot".
   if (CommandLine::ForCurrentProcess()->HasSwitch(
           switches::kDumpProfileDependencyGraph)) {
     base::FilePath dot_file =
         profile->GetPath().AppendASCII("profile-dependencies.dot");
-    std::string contents = DumpGraphvizDependency();
+    std::string contents = dependency_graph_.DumpAsGraphviz("Profile");
     file_util::WriteFile(dot_file, contents.c_str(), contents.size());
   }
-#endif
-
-  // Step 1: Build a set of nodes with no incoming edges.
-  std::deque<ProfileKeyedBaseFactory*> queue;
-  std::copy(all_components_.begin(),
-            all_components_.end(),
-            std::back_inserter(queue));
-
-  std::deque<ProfileKeyedBaseFactory*>::iterator queue_end = queue.end();
-  for (EdgeMap::const_iterator it = edges_.begin();
-       it != edges_.end(); ++it) {
-    queue_end = std::remove(queue.begin(), queue_end, it->second);
-  }
-  queue.erase(queue_end, queue.end());
-
-  // Step 2: Do the Kahn topological sort.
-  std::vector<ProfileKeyedBaseFactory*> output;
-  EdgeMap edges(edges_);
-  while (!queue.empty()) {
-    ProfileKeyedBaseFactory* node = queue.front();
-    queue.pop_front();
-    output.push_back(node);
-
-    std::pair<EdgeMap::iterator, EdgeMap::iterator> range =
-        edges.equal_range(node);
-    EdgeMap::iterator it = range.first;
-    while (it != range.second) {
-      ProfileKeyedBaseFactory* dest = it->second;
-      EdgeMap::iterator temp = it;
-      it++;
-      edges.erase(temp);
-
-      bool has_incoming_edges = false;
-      for (EdgeMap::iterator jt = edges.begin(); jt != edges.end(); ++jt) {
-        if (jt->second == dest) {
-          has_incoming_edges = true;
-          break;
-        }
-      }
-
-      if (!has_incoming_edges)
-        queue.push_back(dest);
-    }
-  }
-
-  if (edges.size()) {
-    NOTREACHED() << "Dependency graph has a cycle. We are doomed.";
-  }
-
-  std::reverse(output.begin(), output.end());
-  destruction_order_ = output;
-}
-
-#if !defined(NDEBUG)
-
-std::string ProfileDependencyManager::DumpGraphvizDependency() {
-  std::string result("digraph {\n");
-
-  // Make a copy of all components.
-  std::deque<ProfileKeyedBaseFactory*> components;
-  std::copy(all_components_.begin(),
-            all_components_.end(),
-            std::back_inserter(components));
-
-  // State all dependencies and remove |second| so we don't generate an
-  // implicit dependency on the Profile hard coded node.
-  std::deque<ProfileKeyedBaseFactory*>::iterator components_end =
-      components.end();
-  result.append("  /* Dependencies */\n");
-  for (EdgeMap::const_iterator it = edges_.begin(); it != edges_.end(); ++it) {
-    result.append("  ");
-    result.append(it->second->name());
-    result.append(" -> ");
-    result.append(it->first->name());
-    result.append(";\n");
-
-    components_end = std::remove(components.begin(), components_end,
-                                 it->second);
-  }
-  components.erase(components_end, components.end());
-
-  // Every node that doesn't depend on anything else will implicitly depend on
-  // the Profile.
-  result.append("\n  /* Toplevel attachments */\n");
-  for (std::deque<ProfileKeyedBaseFactory*>::const_iterator it =
-           components.begin(); it != components.end(); ++it) {
-    result.append("  ");
-    result.append((*it)->name());
-    result.append(" -> Profile;\n");
-  }
-
-  result.append("\n  /* Toplevel profile */\n");
-  result.append("  Profile [shape=box];\n");
-
-  result.append("}\n");
-  return result;
 }
-
 #endif