Extract DependencyGraph from ProfileDependencyManager.

chrome/browser/profiles/dependency_graph.h

+// Copyright 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CHROME_BROWSER_PROFILES_DEPENDENCY_GRAPH_H_
+#define CHROME_BROWSER_PROFILES_DEPENDENCY_GRAPH_H_
+
+#include <map>
+#include <string>
+#include <vector>
+
+#include "base/callback.h"
+#include "base/compiler_specific.h"
+
+class DependencyGraph {
+ public:
+  typedef base::Callback<std::string(void*)> GetNodeNameCallback;
+
+  explicit DependencyGraph(const GetNodeNameCallback& callback);
+  ~DependencyGraph();
+
+  // Adds/Removes a node from our list of live nodes. Removing will
+  // also remove live dependency links.
+  void AddNode(void* node);
+  void RemoveNode(void* node);
+
+  // Adds a dependency between two nodes.
+  void AddEdge(void* depended, void* dependee);

[Elliot Glaysher, 2013/04/05 23:44:15]

I'd prefer it if you got rid of these void pointers and replaced this with an
empty class which every Node had to derive from.

Theoretically, the Google style guide bans multiple inheritance. In practice,
especially in the UI code, we use it all over the place and there's historically
been lots of errors where the use of a void* or a static_cast<> has kept the C++
compiler from doing the correct pointer offset behaviour and I'd like to be
defensive here. Please define a DependencyNode class (or whatnot).

[Paweł Hajdan Jr., 2013/04/08 20:26:43]

Glad to see a concern for safety and correctness.

I was thinking about the best way to address that too, and one thing I'm trying
to do is to remove the need for the class being a node to know in any way about
DependencyGraph.

I was considering a template-based solution to provide type safety. What do you
think about that? Convert everything to template, or just a templated wrapper
around void* ?

[Elliot Glaysher, 2013/04/11 20:09:28]

So what's the motivation for doing that? Creating a base node is straightforward
enough and doesn't make us depend on templates.

+
+  // Topologically sorts nodes to produce a safe construction order
+  // (all nodes after their dependees).
+  bool GetConstructionOrder(std::vector<void*>* order) WARN_UNUSED_RESULT;
+
+  // Topologically sorts nodes to produce a safe destruction order
+  // (all nodes before their dependees).
+  bool GetDestructionOrder(std::vector<void*>* order) WARN_UNUSED_RESULT;
+
+  // Returns representation of the dependency graph in graphviz format.
+  std::string DumpAsGraphviz(const std::string& toplevel_name);
+
+ private:
+  typedef std::multimap<void*, void*> EdgeMap;
+
+  bool BuildConstructionOrder() WARN_UNUSED_RESULT;
+
+  std::vector<void*> all_nodes_;
+
+  EdgeMap edges_;
+
+  std::vector<void*> construction_order_;
+
+  GetNodeNameCallback get_node_name_callback_;
+
+  DISALLOW_COPY_AND_ASSIGN(DependencyGraph);
+};
+
+#endif  // CHROME_BROWSER_PROFILES_DEPENDENCY_GRAPH_H_