Implement and test InitializerDependencyGraph.

An InitializerDependencyGraph is a directed acyclic graph (DAG) of named
initialization operations.  Every node in the graph has a unique name, a
behavior function, and a set of prerequisites.  The graph supports two
inspection functions, one to get the behavior function for a node with a given
name, and the other to produce a vector of node names, ordered in a manner that
does not violate any preprequisite dependneces.

InitializerDependencyGraph is exception-free, and because it is for use very
early in process startup, it does no logging itself.

This patch also introduces a utility macro, MONGO_MAKE_STRING_VECTOR, which is
useful for constructing std::vector<std::string> from a sequence of string
literals.  This patch uses it for testing, but subsequent MONGO_INIT-related
work will rely on it, as well.

Part of work on SERVER-5112.

8 files changed, 674 insertions, 3 deletions

diff --git a/src/mongo/base/SConscript b/src/mongo/base/SConscript
index bb500cd21ed..5c5f385fcac 100644
--- a/src/mongo/base/SConscript
+++ b/src/mongo/base/SConscript
@@ -2,9 +2,13 @@
 
 Import("env")
 
-env.StaticLibrary("base", ['status.cpp'])
+env.StaticLibrary('base', ['initializer_dependency_graph.cpp',
+                           'make_string_vector.cpp',
+                           'status.cpp'])
 
-env.CppUnitTest('status_test', 'status_test.cpp',
+env.CppUnitTest('initializer_dependency_graph_test',
+                ['initializer_dependency_graph_test.cpp'],
                 LIBDEPS=['base'])
 
-
+env.CppUnitTest('status_test', 'status_test.cpp',
+                LIBDEPS=['base'])
diff --git a/src/mongo/base/initializer_dependency_graph.cpp b/src/mongo/base/initializer_dependency_graph.cpp
new file mode 100644
index 00000000000..90e259167f4
--- /dev/null
+++ b/src/mongo/base/initializer_dependency_graph.cpp
@@ -0,0 +1,149 @@
+/*    Copyright 2012 10gen Inc.
+ *
+ *    Licensed under the Apache License, Version 2.0 (the "License");
+ *    you may not use this file except in compliance with the License.
+ *    You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *    Unless required by applicable law or agreed to in writing, software
+ *    distributed under the License is distributed on an "AS IS" BASIS,
+ *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *    See the License for the specific language governing permissions and
+ *    limitations under the License.
+ */
+
+#include "mongo/base/initializer_dependency_graph.h"
+
+#include <algorithm>
+#include <iterator>
+
+namespace mongo {
+
+    InitializerDependencyGraph::InitializerDependencyGraph() {}
+    InitializerDependencyGraph::~InitializerDependencyGraph() {}
+
+    Status InitializerDependencyGraph::addInitializer(const std::string& name,
+                                                      const InitializerFunction& fn,
+                                                      const std::vector<std::string>& prerequisites,
+                                                      const std::vector<std::string>& dependents) {
+        if (!fn)
+            return Status(ErrorCodes::BadValue, "Illegal to supply a NULL function");
+
+        NodeData& newNode = _nodes[name];
+        if (newNode.fn) {
+            return Status(ErrorCodes::DuplicateKey, name);
+        }
+
+        newNode.fn = fn;
+
+        for (size_t i = 0; i < prerequisites.size(); ++i) {
+            newNode.prerequisites.insert(prerequisites[i]);
+        }
+
+        for (size_t i = 0; i < dependents.size(); ++i) {
+            _nodes[dependents[i]].prerequisites.insert(name);
+        }
+
+        return Status::OK;
+    }
+
+    InitializerFunction InitializerDependencyGraph::getInitializerFunction(
+            const std::string& name) const {
+
+        NodeMap::const_iterator iter = _nodes.find(name);
+        if (iter == _nodes.end())
+            return InitializerFunction();
+        return iter->second.fn;
+    }
+
+    Status InitializerDependencyGraph::topSort(std::vector<std::string>* sortedNames) const {
+        /*
+         * This top-sort is implemented by performing a depth-first traversal of the dependency
+         * graph, once for each node.  "visitedNodeNames" tracks the set of node names ever visited,
+         * and it is used to prune each DFS.  A node that has been visited once on any DFS is never
+         * visited again.  Complexity of this implementation is O(n+m) where "n" is the number of
+         * nodes and "m" is the number of prerequisite edges.  Space complexity is O(n), in both
+         * stack space and size of the "visitedNodeNames" set.
+         *
+         * "inProgressNodeNames" is used to detect and report cycles.
+         */
+
+        std::vector<std::string> inProgressNodeNames;
+        unordered_set<std::string> visitedNodeNames;
+
+        sortedNames->clear();
+        for (NodeMap::const_iterator iter = _nodes.begin(), end = _nodes.end();
+             iter != end; ++iter) {
+
+            Status status = recursiveTopSort(_nodes,
+                                             *iter,
+                                             &inProgressNodeNames,
+                                             &visitedNodeNames,
+                                             sortedNames);
+            if (Status::OK != status)
+                return status;
+        }
+        return Status::OK;
+    }
+
+    Status InitializerDependencyGraph::recursiveTopSort(
+            const NodeMap& nodeMap,
+            const Node& currentNode,
+            std::vector<std::string>* inProgressNodeNames,
+            unordered_set<std::string>* visitedNodeNames,
+            std::vector<std::string>* sortedNames) {
+
+        /*
+         * The top sort is performed by depth-first traversal starting at each node in the
+         * dependency graph, short-circuited any time a node is seen that has already been visited
+         * in any traversal.  "visitedNodeNames" is the set of nodes that have been successfully
+         * visited, while "inProgressNodeNames" are nodes currently in the exploration chain.  This
+         * structure is kept explicitly to facilitate cycle detection.
+         *
+         * This function implements a depth-first traversal, and is called once for each node in the
+         * graph by topSort(), above.
+         */
+
+        if ((*visitedNodeNames).count(currentNode.first))
+            return Status::OK;
+
+        if (!currentNode.second.fn)
+            return Status(ErrorCodes::BadValue, currentNode.first);
+
+        inProgressNodeNames->push_back(currentNode.first);
+
+        std::vector<std::string>::iterator firstOccurence = std::find(
+                inProgressNodeNames->begin(), inProgressNodeNames->end(), currentNode.first);
+        if (firstOccurence + 1 != inProgressNodeNames->end()) {
+            sortedNames->clear();
+            std::copy(firstOccurence, inProgressNodeNames->end(), std::back_inserter(*sortedNames));
+            return Status(ErrorCodes::GraphContainsCycle, "Cycle in dependency graph");
+        }
+
+        for (unordered_set<std::string>::const_iterator
+                 iter = currentNode.second.prerequisites.begin(),
+                 end = currentNode.second.prerequisites.end();
+             iter != end; ++iter) {
+
+            NodeMap::const_iterator nextNode = nodeMap.find(*iter);
+            if (nextNode == nodeMap.end())
+                return Status(ErrorCodes::BadValue, *iter);
+
+            Status status = recursiveTopSort(nodeMap,
+                                             *nextNode,
+                                             inProgressNodeNames,
+                                             visitedNodeNames,
+                                             sortedNames);
+            if (Status::OK != status)
+                return status;
+        }
+        sortedNames->push_back(currentNode.first);
+        if (inProgressNodeNames->back() != currentNode.first)
+            return Status(ErrorCodes::InternalError, "inProgressNodeNames stack corrupt");
+        inProgressNodeNames->pop_back();
+        visitedNodeNames->insert(currentNode.first);
+        return Status::OK;
+    }
+
+}  // namespace mongo
diff --git a/src/mongo/base/initializer_dependency_graph.h b/src/mongo/base/initializer_dependency_graph.h
new file mode 100644
index 00000000000..9bcf0c750ef
--- /dev/null
+++ b/src/mongo/base/initializer_dependency_graph.h
@@ -0,0 +1,118 @@
+/*    Copyright 2012 10gen Inc.
+ *
+ *    Licensed under the Apache License, Version 2.0 (the "License");
+ *    you may not use this file except in compliance with the License.
+ *    You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *    Unless required by applicable law or agreed to in writing, software
+ *    distributed under the License is distributed on an "AS IS" BASIS,
+ *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *    See the License for the specific language governing permissions and
+ *    limitations under the License.
+ */
+
+#pragma once
+
+#include <string>
+#include <vector>
+#include <utility>
+
+#include "mongo/base/disallow_copying.h"
+#include "mongo/base/initializer_function.h"
+#include "mongo/base/status.h"
+#include "mongo/platform/unordered_map.h"
+#include "mongo/platform/unordered_set.h"
+
+namespace mongo {
+
+    /**
+     * Representation of a dependency graph of "initialization operations."
+     *
+     * Each operation has a unique name, a function object implementing the operation's behavior,
+     * and a set of prerequisite operations, which may be empty.  A legal graph contains no cycles.
+     *
+     * Instances of this class are used in two phases.  In the first phase, the graph is constructed
+     * by repeated calls to addInitializer().  In the second phase, a user calls the topSort()
+     * method to produce an initialization order that respects the dependences among operations, and
+     * then uses the getInitializerFunction() to get the behavior function for each operation, in
+     * turn.
+     *
+     * Concurrency Notes: The user is responsible for synchronization.  Multiple threads may
+     * simultaneously call the const functions, getInitializerFunction and topSort, on the same
+     * instance of InitializerDependencyGraph.  However, no thread may call addInitializer while any
+     * thread is executing those functions or addInitializer on the same instance.
+     */
+    class InitializerDependencyGraph {
+        MONGO_DISALLOW_COPYING(InitializerDependencyGraph);
+
+    public:
+        InitializerDependencyGraph();
+        ~InitializerDependencyGraph();
+
+        /**
+         * Add a new initializer node, named "name", to the dependency graph, with the given
+         * behavior, "fn", and the given "prerequisites" (input dependences) and "dependents"
+         * (output dependences).
+         *
+         * If "!fn" (fn is NULL in function pointer parlance), returns status with code
+         * ErrorCodes::badValue.  If "name" is a duplicate of a name already present in the graph,
+         * returns "ErrorCodes::duplicateKey".  Otherwise, returns Status::OK and adds the new node
+         * to the graph.  Note that cycles in the dependency graph are not discovered in this phase.
+         * Rather, they're discovered by topSort, below.
+         */
+        Status addInitializer(const std::string& name,
+                              const InitializerFunction& fn,
+                              const std::vector<std::string>& prerequisites,
+                              const std::vector<std::string>& dependents);
+
+        /**
+         * Given a dependency operation node named "name", return its behavior function.  Returns
+         * a value that evaluates to "false" in boolean context, otherwise.
+         */
+        InitializerFunction getInitializerFunction(const std::string& name) const;
+
+        /**
+         * Construct a topological sort of the dependency graph, and store that order into
+         * "sortedNames".  Returns Status::OK on success.
+         *
+         * If the graph contains a cycle, returns ErrorCodes::graphContainsCycle, and "sortedNames"
+         * is an ordered sequence of nodes involved in a cycle.  In this case, the first and last
+         * element of "sortedNames" will be equal.
+         *
+         * If any node in the graph names a prerequisite that was never added to the graph via
+         * addInitializer, this function will return ErrorCodes::badValue.
+         *
+         * Any other return value indicates an internal error, and should not occur.
+         */
+        Status topSort(std::vector<std::string>* sortedNames) const;
+
+    private:
+        struct NodeData {
+            InitializerFunction fn;
+            unordered_set<std::string> prerequisites;
+        };
+
+        typedef unordered_map<std::string, NodeData> NodeMap;
+        typedef NodeMap::value_type Node;
+
+        /**
+         * Helper function to recursively top-sort a graph.  Used by topSort().
+         */
+        static Status recursiveTopSort(
+                const NodeMap& nodeMap,
+                const Node& currentNode,
+                std::vector<std::string>* inProgressNodeNames,
+                unordered_set<std::string>* visitedNodeNames,
+                std::vector<std::string>* sortedNames);
+
+        /**
+         * Map of all named nodes.  Nodes named as prerequisites or dependents but not explicitly
+         * added via addInitializer will either be absent from this map or be present with
+         * NodeData::fn set to a false-ish value.
+         */
+        NodeMap _nodes;
+    };
+
+}  // namespace mongo
diff --git a/src/mongo/base/initializer_dependency_graph_test.cpp b/src/mongo/base/initializer_dependency_graph_test.cpp
new file mode 100644
index 00000000000..b8d565db364
--- /dev/null
+++ b/src/mongo/base/initializer_dependency_graph_test.cpp
@@ -0,0 +1,273 @@
+/*    Copyright 2012 10gen Inc.
+ *
+ *    Licensed under the Apache License, Version 2.0 (the "License");
+ *    you may not use this file except in compliance with the License.
+ *    You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *    Unless required by applicable law or agreed to in writing, software
+ *    distributed under the License is distributed on an "AS IS" BASIS,
+ *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *    See the License for the specific language governing permissions and
+ *    limitations under the License.
+ */
+
+/**
+ * Unit tests of the InitializerDependencyGraph type.
+ */
+
+#include "mongo/base/initializer_dependency_graph.h"
+#include "mongo/base/make_string_vector.h"
+#include "mongo/unittest/unittest.h"
+
+#define ADD_INITIALIZER(GRAPH, NAME, FN, PREREQS, DEPS)                 \
+    (GRAPH).addInitializer(                                             \
+            (NAME),                                                     \
+            (FN),                                                       \
+            MONGO_MAKE_STRING_VECTOR PREREQS,                           \
+            MONGO_MAKE_STRING_VECTOR DEPS)
+
+#define ASSERT_ADD_INITIALIZER(GRAPH, NAME, FN, PREREQS, DEPS)  \
+    ASSERT_EQUALS(Status::OK, ADD_INITIALIZER(GRAPH, NAME, FN, PREREQS, DEPS))
+
+#define ASSERT_EXACTLY_N_IN_CONTAINER(N, CONTAINER, THING)               \
+    ASSERT_EQUALS(N, std::count((CONTAINER).begin(), (CONTAINER).end(), (THING)))
+
+#define ASSERT_AT_LEAST_N_IN_CONTAINER(N, CONTAINER, THING)             \
+    ASSERT_LESS_THAN_OR_EQUALS(N, std::count((CONTAINER).begin(), (CONTAINER).end(), (THING)))
+
+#define ASSERT_EXACTLY_ONE_IN_CONTAINER(CONTAINER, THING)               \
+    ASSERT_EXACTLY_N_IN_CONTAINER(1, CONTAINER, THING)
+
+namespace mongo {
+namespace {
+
+    Status doNothing(InitializationContext*) { return Status::OK; }
+
+    TEST(InitializerDependencyGraphTest, InsertNullFunctionFails) {
+        InitializerDependencyGraph graph;
+        ASSERT_EQUALS(ErrorCodes::BadValue, ADD_INITIALIZER(graph, "A", InitializerFunction(), (), ()));
+    }
+
+    TEST(InitializerDependencyGraphTest, InsertSameNameTwiceFails) {
+        InitializerDependencyGraph graph;
+        ASSERT_ADD_INITIALIZER(graph, "A", doNothing, (), ());
+        ASSERT_EQUALS(ErrorCodes::DuplicateKey, ADD_INITIALIZER(graph, "A", doNothing, (), ()));
+    }
+
+    TEST(InitializerDependencyGraphTest, TopSortEmptyGraph) {
+        InitializerDependencyGraph graph;
+        std::vector<std::string> nodeNames;
+        ASSERT_EQUALS(Status::OK, graph.topSort(&nodeNames));
+        ASSERT_EQUALS(0U, nodeNames.size());
+    }
+
+    TEST(InitializerDependencyGraphTest, TopSortGraphNoDeps) {
+        InitializerDependencyGraph graph;
+        std::vector<std::string> nodeNames;
+        ASSERT_ADD_INITIALIZER(graph, "A", doNothing, (), ());
+        ASSERT_ADD_INITIALIZER(graph, "B", doNothing, (), ());
+        ASSERT_ADD_INITIALIZER(graph, "C", doNothing, (), ());
+        ASSERT_EQUALS(Status::OK, graph.topSort(&nodeNames));
+        ASSERT_EQUALS(3U, nodeNames.size());
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "A");
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "B");
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "C");
+    }
+
+    TEST(InitializerDependencyGraphTest, TopSortWithDiamondPrerequisites) {
+        /*
+         * This tests top-sorting a simple diamond, specified using prerequisites:
+         *
+         *     B
+         *   /  ^
+         *  v    \ 
+         * A      D
+         *  ^   /
+         *   \ v
+         *    C
+         */
+        InitializerDependencyGraph graph;
+        std::vector<std::string> nodeNames;
+        ASSERT_ADD_INITIALIZER(graph, "A", doNothing, (), ());
+        ASSERT_ADD_INITIALIZER(graph, "D", doNothing, ("B", "C"), ());
+        ASSERT_ADD_INITIALIZER(graph, "B", doNothing, ("A"), ());
+        ASSERT_ADD_INITIALIZER(graph, "C", doNothing, ("A"), ());
+        ASSERT_EQUALS(Status::OK, graph.topSort(&nodeNames));
+        ASSERT_EQUALS(4U, nodeNames.size());
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "A");
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "B");
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "C");
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "D");
+        ASSERT_EQUALS("A", nodeNames.front());
+        ASSERT_EQUALS("D", nodeNames.back());
+    }
+
+    TEST(InitializerDependencyGraphTest, TopSortWithDiamondDependents) {
+        /*
+         * This tests top-sorting a simple diamond, specified using dependents:
+         *
+         *     B
+         *   /  ^
+         *  v    \ 
+         * A      D
+         *  ^   /
+         *   \ v
+         *    C
+         */
+        InitializerDependencyGraph graph;
+        std::vector<std::string> nodeNames;
+        ASSERT_ADD_INITIALIZER(graph, "A", doNothing, (), ("B", "C"));
+        ASSERT_ADD_INITIALIZER(graph, "D", doNothing, (), ());
+        ASSERT_ADD_INITIALIZER(graph, "B", doNothing, (), ("D"));
+        ASSERT_ADD_INITIALIZER(graph, "C", doNothing, (), ("D"));
+        ASSERT_EQUALS(Status::OK, graph.topSort(&nodeNames));
+        ASSERT_EQUALS(4U, nodeNames.size());
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "A");
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "B");
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "C");
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "D");
+        ASSERT_EQUALS("A", nodeNames.front());
+        ASSERT_EQUALS("D", nodeNames.back());
+    }
+
+    TEST(InitializerDependencyGraphTest, TopSortWithDiamondGeneral1) {
+        /*
+         * This tests top-sorting a simple diamond, where B and C specify all prerequisites and
+         * dependents.
+         *
+         *     B
+         *   /  ^
+         *  v    \ 
+         * A      D
+         *  ^   /
+         *   \ v
+         *    C
+         */
+        InitializerDependencyGraph graph;
+        std::vector<std::string> nodeNames;
+        ASSERT_ADD_INITIALIZER(graph, "A", doNothing, (), ());
+        ASSERT_ADD_INITIALIZER(graph, "D", doNothing, (), ());
+        ASSERT_ADD_INITIALIZER(graph, "B", doNothing, ("A"), ("D"));
+        ASSERT_ADD_INITIALIZER(graph, "C", doNothing, ("A"), ("D"));
+        ASSERT_EQUALS(Status::OK, graph.topSort(&nodeNames));
+        ASSERT_EQUALS(4U, nodeNames.size());
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "A");
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "B");
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "C");
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "D");
+        ASSERT_EQUALS("A", nodeNames.front());
+        ASSERT_EQUALS("D", nodeNames.back());
+    }
+
+    TEST(InitializerDependencyGraphTest, TopSortWithDiamondGeneral2) {
+        /*
+         * This tests top-sorting a simple diamond, where A and D specify all prerequisites and
+         * dependents.
+         *
+         *     B
+         *   /  ^
+         *  v    \ 
+         * A      D
+         *  ^   /
+         *   \ v
+         *    C
+         */
+        InitializerDependencyGraph graph;
+        std::vector<std::string> nodeNames;
+        ASSERT_ADD_INITIALIZER(graph, "A", doNothing, (), ("B", "C"));
+        ASSERT_ADD_INITIALIZER(graph, "D", doNothing, ("C", "B"), ());
+        ASSERT_ADD_INITIALIZER(graph, "B", doNothing, (), ());
+        ASSERT_ADD_INITIALIZER(graph, "C", doNothing, (), ());
+        ASSERT_EQUALS(Status::OK, graph.topSort(&nodeNames));
+        ASSERT_EQUALS(4U, nodeNames.size());
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "A");
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "B");
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "C");
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "D");
+        ASSERT_EQUALS("A", nodeNames.front());
+        ASSERT_EQUALS("D", nodeNames.back());
+    }
+
+    TEST(InitializerDependencyGraphTest, TopSortWithDiamondGeneral3) {
+        /*
+         * This tests top-sorting a simple diamond, where A and D specify all prerequisites and
+         * dependents, but so do B and C.
+         *
+         *     B
+         *   /  ^
+         *  v    \ 
+         * A      D
+         *  ^   /
+         *   \ v
+         *    C
+         */
+        InitializerDependencyGraph graph;
+        std::vector<std::string> nodeNames;
+        ASSERT_ADD_INITIALIZER(graph, "A", doNothing, (), ("B", "C"));
+        ASSERT_ADD_INITIALIZER(graph, "D", doNothing, ("C", "B"), ());
+        ASSERT_ADD_INITIALIZER(graph, "B", doNothing, ("A"), ("D"));
+        ASSERT_ADD_INITIALIZER(graph, "C", doNothing, ("A"), ("D"));
+        ASSERT_EQUALS(Status::OK, graph.topSort(&nodeNames));
+        ASSERT_EQUALS(4U, nodeNames.size());
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "A");
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "B");
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "C");
+        ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "D");
+        ASSERT_EQUALS("A", nodeNames.front());
+        ASSERT_EQUALS("D", nodeNames.back());
+    }
+
+    TEST(InitializerDependencyGraphTest, TopSortWithDiamondAndCycle) {
+        /*
+         * This tests top-sorting a graph with a cycle, which should fail..
+         *
+         *     B <- E
+         *   /  ^   ^
+         *  v    \ /
+         * A      D
+         *  ^   /
+         *   \ v
+         *    C
+         */
+        InitializerDependencyGraph graph;
+        std::vector<std::string> nodeNames;
+        ASSERT_ADD_INITIALIZER(graph, "A", doNothing, (), ("B", "C"));
+        ASSERT_ADD_INITIALIZER(graph, "D", doNothing, ("C", "B"), ());
+        ASSERT_ADD_INITIALIZER(graph, "B", doNothing, (), ());
+        ASSERT_ADD_INITIALIZER(graph, "C", doNothing, (), ());
+        ASSERT_ADD_INITIALIZER(graph, "E", doNothing, ("D"), ("B"));
+        ASSERT_EQUALS(ErrorCodes::GraphContainsCycle, graph.topSort(&nodeNames));
+        ASSERT_EQUALS(4U, nodeNames.size());
+        ASSERT_EQUALS(nodeNames.front(), nodeNames.back());
+        ASSERT_AT_LEAST_N_IN_CONTAINER(1, nodeNames, "D");
+        ASSERT_AT_LEAST_N_IN_CONTAINER(1, nodeNames, "E");
+        ASSERT_AT_LEAST_N_IN_CONTAINER(1, nodeNames, "B");
+        ASSERT_EXACTLY_N_IN_CONTAINER(0, nodeNames, "A");
+        ASSERT_EXACTLY_N_IN_CONTAINER(0, nodeNames, "C");
+    }
+
+    TEST(InitializerDependencyGraphTest, TopSortFailsWhenMissingPrerequisite) {
+        /*
+         * If a node names a never-declared prerequisite, topSort should fail.
+         */
+        InitializerDependencyGraph graph;
+        std::vector<std::string> nodeNames;
+        ASSERT_ADD_INITIALIZER(graph, "B", doNothing, ("A"), ());
+        ASSERT_EQUALS(ErrorCodes::BadValue, graph.topSort(&nodeNames));
+    }
+
+    TEST(InitializerDependencyGraphTest, TopSortFailsWhenMissingDependent) {
+        /*
+         * If a node names a never-declared dependent, topSort should fail.
+         */
+        InitializerDependencyGraph graph;
+        std::vector<std::string> nodeNames;
+        ASSERT_ADD_INITIALIZER(graph, "A", doNothing, (), ("B"));
+        ASSERT_EQUALS(ErrorCodes::BadValue, graph.topSort(&nodeNames));
+    }
+
+}  // namespace
+}  // namespace mongo
+
diff --git a/src/mongo/base/initializer_function.h b/src/mongo/base/initializer_function.h
new file mode 100644
index 00000000000..cb12af35085
--- /dev/null
+++ b/src/mongo/base/initializer_function.h
@@ -0,0 +1,34 @@
+/*    Copyright 2012 10gen Inc.
+ *
+ *    Licensed under the Apache License, Version 2.0 (the "License");
+ *    you may not use this file except in compliance with the License.
+ *    You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *    Unless required by applicable law or agreed to in writing, software
+ *    distributed under the License is distributed on an "AS IS" BASIS,
+ *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *    See the License for the specific language governing permissions and
+ *    limitations under the License.
+ */
+
+#pragma once
+
+#include <boost/function.hpp>
+
+#include "mongo/base/status.h"
+
+namespace mongo {
+
+    class InitializationContext;
+
+    /**
+     * An InitializerFunction implements the behavior of an initialization operation.
+     *
+     * On successful execution, an InitializerFunction returns Status::OK.  It may
+     * inspect and mutate the supplied InitializationContext.
+     */
+    typedef boost::function<Status (InitializationContext*)> InitializerFunction;
+
+}  // namespace mongo
diff --git a/src/mongo/base/make_string_vector.cpp b/src/mongo/base/make_string_vector.cpp
new file mode 100644
index 00000000000..9634f9499cd
--- /dev/null
+++ b/src/mongo/base/make_string_vector.cpp
@@ -0,0 +1,39 @@
+/*    Copyright 2012 10gen Inc.
+ *
+ *    Licensed under the Apache License, Version 2.0 (the "License");
+ *    you may not use this file except in compliance with the License.
+ *    You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *    Unless required by applicable law or agreed to in writing, software
+ *    distributed under the License is distributed on an "AS IS" BASIS,
+ *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *    See the License for the specific language governing permissions and
+ *    limitations under the License.
+ */
+
+#include "mongo/base/make_string_vector.h"
+
+#include <cstdlib>
+#include <iostream>
+#include <stdarg.h>
+
+namespace mongo {
+
+    std::vector<std::string> _makeStringVector(int ignored, ...) {
+        va_list ap;
+        va_start(ap, ignored);
+        const char* arg = va_arg(ap, const char *);
+        if (arg) {
+            std::cerr << "Internal error!\n";
+            std::abort();
+        }
+        std::vector<std::string> result;
+        while ((arg = va_arg(ap, const char *)))
+            result.push_back(arg);
+        va_end(ap);
+        return result;
+    }
+
+}  // namspace mongo
diff --git a/src/mongo/base/make_string_vector.h b/src/mongo/base/make_string_vector.h
new file mode 100644
index 00000000000..39c5167641e
--- /dev/null
+++ b/src/mongo/base/make_string_vector.h
@@ -0,0 +1,46 @@
+/*    Copyright 2012 10gen Inc.
+ *
+ *    Licensed under the Apache License, Version 2.0 (the "License");
+ *    you may not use this file except in compliance with the License.
+ *    You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *    Unless required by applicable law or agreed to in writing, software
+ *    distributed under the License is distributed on an "AS IS" BASIS,
+ *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *    See the License for the specific language governing permissions and
+ *    limitations under the License.
+ */
+
+#pragma once
+
+#include <string>
+#include <vector>
+
+/**
+ * Utility macro to construct a std::vector<std::string> from a sequence of C-style
+ * strings.
+ *
+ * Usage:  MONGO_MAKE_STRING_VECTOR("a", "b", "c") returns a vector containing
+ * std::strings "a", "b", "c", in that order.
+ */
+#define MONGO_MAKE_STRING_VECTOR(...) ::mongo::_makeStringVector(0, NULL, ##__VA_ARGS__, NULL)
+
+namespace mongo {
+
+    /**
+     * Create a vector of strings from varargs of C-style strings.
+     *
+     * WARNING: Only intended for use by MONGO_MAKE_STRING_VECTOR macro, defined above.  Aborts
+     * ungracefully if you misuse it, so stick to the macro.
+     *
+     * The first parameter is ignored in all circumstances.  The second parameter must be NULL, as
+     * must be the last parameter.  The third through penultimate parameters should be const char*
+     * C-style strings.
+     *
+     * Returns a vector of std::strings.
+     */
+    std::vector<std::string> _makeStringVector(int ignored, ...);
+
+}  // namespace mongo
diff --git a/src/mongo/base/status.h b/src/mongo/base/status.h
index 616055bbbf8..088dd5483ba 100644
--- a/src/mongo/base/status.h
+++ b/src/mongo/base/status.h
@@ -114,6 +114,14 @@ namespace mongo {
         static void unref(ErrorInfo* error);
     };
 
+    static inline bool operator==(const ErrorCodes::Error lhs, const Status& rhs) {
+        return rhs == lhs;
+    }
+
+    static inline bool operator!=(const ErrorCodes::Error lhs, const Status& rhs) {
+        return rhs != lhs;
+    }
+
     //
     // Convenience method for unittest code. Please use accessors otherwise.
     //