1
2 /**
3 * Copyright (C) 2018-present MongoDB, Inc.
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the Server Side Public License, version 1,
7 * as published by MongoDB, Inc.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * Server Side Public License for more details.
13 *
14 * You should have received a copy of the Server Side Public License
15 * along with this program. If not, see
16 * <http://www.mongodb.com/licensing/server-side-public-license>.
17 *
18 * As a special exception, the copyright holders give permission to link the
19 * code of portions of this program with the OpenSSL library under certain
20 * conditions as described in each individual source file and distribute
21 * linked combinations including the program with the OpenSSL library. You
22 * must comply with the Server Side Public License in all respects for
23 * all of the code used other than as permitted herein. If you modify file(s)
24 * with this exception, you may extend this exception to your version of the
25 * file(s), but you are not obligated to do so. If you do not wish to do so,
26 * delete this exception statement from your version. If you delete this
27 * exception statement from all source files in the program, then also delete
28 * it in the license file.
29 */
30
31 /**
32 * Unit tests of the InitializerDependencyGraph type.
33 */
34
35 #include "mongo/base/init.h"
36 #include "mongo/base/initializer_dependency_graph.h"
37 #include "mongo/base/make_string_vector.h"
38 #include "mongo/unittest/unittest.h"
39
40 #define ADD_INITIALIZER(GRAPH, NAME, FN, PREREQS, DEPS) \
41 (GRAPH).addInitializer( \
42 (NAME), (FN), MONGO_MAKE_STRING_VECTOR PREREQS, MONGO_MAKE_STRING_VECTOR DEPS)
43
44 #define ASSERT_ADD_INITIALIZER(GRAPH, NAME, FN, PREREQS, DEPS) \
45 ASSERT_EQUALS(Status::OK(), ADD_INITIALIZER(GRAPH, NAME, FN, PREREQS, DEPS))
46
47 #define ASSERT_EXACTLY_N_IN_CONTAINER(N, CONTAINER, THING) \
48 ASSERT_EQUALS(N, std::count((CONTAINER).begin(), (CONTAINER).end(), (THING)))
49
50 #define ASSERT_AT_LEAST_N_IN_CONTAINER(N, CONTAINER, THING) \
51 ASSERT_LESS_THAN_OR_EQUALS(N, std::count((CONTAINER).begin(), (CONTAINER).end(), (THING)))
52
53 #define ASSERT_EXACTLY_ONE_IN_CONTAINER(CONTAINER, THING) \
54 ASSERT_EXACTLY_N_IN_CONTAINER(1, CONTAINER, THING)
55
56 namespace mongo {
57 namespace {
58
doNothing(InitializerContext *)59 Status doNothing(InitializerContext*) {
60 return Status::OK();
61 }
62
TEST(InitializerDependencyGraphTest,InsertNullFunctionFails)63 TEST(InitializerDependencyGraphTest, InsertNullFunctionFails) {
64 InitializerDependencyGraph graph;
65 ASSERT_EQUALS(
66 ErrorCodes::BadValue,
67 ADD_INITIALIZER(
68 graph, "A", InitializerFunction(), MONGO_NO_PREREQUISITES, MONGO_NO_DEPENDENTS));
69 }
70
TEST(InitializerDependencyGraphTest,InsertSameNameTwiceFails)71 TEST(InitializerDependencyGraphTest, InsertSameNameTwiceFails) {
72 InitializerDependencyGraph graph;
73 ASSERT_ADD_INITIALIZER(graph, "A", doNothing, MONGO_NO_PREREQUISITES, MONGO_NO_DEPENDENTS);
74 ASSERT_EQUALS(
75 ErrorCodes::DuplicateKey,
76 ADD_INITIALIZER(graph, "A", doNothing, MONGO_NO_PREREQUISITES, MONGO_NO_DEPENDENTS));
77 }
78
TEST(InitializerDependencyGraphTest,TopSortEmptyGraph)79 TEST(InitializerDependencyGraphTest, TopSortEmptyGraph) {
80 InitializerDependencyGraph graph;
81 std::vector<std::string> nodeNames;
82 ASSERT_EQUALS(Status::OK(), graph.topSort(&nodeNames));
83 ASSERT_EQUALS(0U, nodeNames.size());
84 }
85
TEST(InitializerDependencyGraphTest,TopSortGraphNoDeps)86 TEST(InitializerDependencyGraphTest, TopSortGraphNoDeps) {
87 InitializerDependencyGraph graph;
88 std::vector<std::string> nodeNames;
89 ASSERT_ADD_INITIALIZER(graph, "A", doNothing, MONGO_NO_PREREQUISITES, MONGO_NO_DEPENDENTS);
90 ASSERT_ADD_INITIALIZER(graph, "B", doNothing, MONGO_NO_PREREQUISITES, MONGO_NO_DEPENDENTS);
91 ASSERT_ADD_INITIALIZER(graph, "C", doNothing, MONGO_NO_PREREQUISITES, MONGO_NO_DEPENDENTS);
92 ASSERT_EQUALS(Status::OK(), graph.topSort(&nodeNames));
93 ASSERT_EQUALS(3U, nodeNames.size());
94 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "A");
95 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "B");
96 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "C");
97 }
98
TEST(InitializerDependencyGraphTest,TopSortWithDiamondPrerequisites)99 TEST(InitializerDependencyGraphTest, TopSortWithDiamondPrerequisites) {
100 /*
101 * This tests top-sorting a simple diamond, specified using prerequisites:
102 *
103 * B
104 * / ^
105 * v \
106 * A D
107 * ^ /
108 * \ v
109 * C
110 */
111 InitializerDependencyGraph graph;
112 std::vector<std::string> nodeNames;
113 ASSERT_ADD_INITIALIZER(graph, "A", doNothing, MONGO_NO_PREREQUISITES, MONGO_NO_DEPENDENTS);
114 ASSERT_ADD_INITIALIZER(graph, "D", doNothing, ("B", "C"), MONGO_NO_DEPENDENTS);
115 ASSERT_ADD_INITIALIZER(graph, "B", doNothing, ("A"), MONGO_NO_DEPENDENTS);
116 ASSERT_ADD_INITIALIZER(graph, "C", doNothing, ("A"), MONGO_NO_DEPENDENTS);
117 ASSERT_EQUALS(Status::OK(), graph.topSort(&nodeNames));
118 ASSERT_EQUALS(4U, nodeNames.size());
119 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "A");
120 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "B");
121 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "C");
122 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "D");
123 ASSERT_EQUALS("A", nodeNames.front());
124 ASSERT_EQUALS("D", nodeNames.back());
125 }
126
TEST(InitializerDependencyGraphTest,TopSortWithDiamondDependents)127 TEST(InitializerDependencyGraphTest, TopSortWithDiamondDependents) {
128 /*
129 * This tests top-sorting a simple diamond, specified using dependents:
130 *
131 * B
132 * / ^
133 * v \
134 * A D
135 * ^ /
136 * \ v
137 * C
138 */
139 InitializerDependencyGraph graph;
140 std::vector<std::string> nodeNames;
141 ASSERT_ADD_INITIALIZER(graph, "A", doNothing, MONGO_NO_PREREQUISITES, ("B", "C"));
142 ASSERT_ADD_INITIALIZER(graph, "D", doNothing, MONGO_NO_PREREQUISITES, MONGO_NO_DEPENDENTS);
143 ASSERT_ADD_INITIALIZER(graph, "B", doNothing, MONGO_NO_PREREQUISITES, ("D"));
144 ASSERT_ADD_INITIALIZER(graph, "C", doNothing, MONGO_NO_PREREQUISITES, ("D"));
145 ASSERT_EQUALS(Status::OK(), graph.topSort(&nodeNames));
146 ASSERT_EQUALS(4U, nodeNames.size());
147 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "A");
148 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "B");
149 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "C");
150 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "D");
151 ASSERT_EQUALS("A", nodeNames.front());
152 ASSERT_EQUALS("D", nodeNames.back());
153 }
154
TEST(InitializerDependencyGraphTest,TopSortWithDiamondGeneral1)155 TEST(InitializerDependencyGraphTest, TopSortWithDiamondGeneral1) {
156 /*
157 * This tests top-sorting a simple diamond, where B and C specify all prerequisites and
158 * dependents.
159 *
160 * B
161 * / ^
162 * v \
163 * A D
164 * ^ /
165 * \ v
166 * C
167 */
168 InitializerDependencyGraph graph;
169 std::vector<std::string> nodeNames;
170 ASSERT_ADD_INITIALIZER(graph, "A", doNothing, MONGO_NO_PREREQUISITES, MONGO_NO_DEPENDENTS);
171 ASSERT_ADD_INITIALIZER(graph, "D", doNothing, MONGO_NO_PREREQUISITES, MONGO_NO_DEPENDENTS);
172 ASSERT_ADD_INITIALIZER(graph, "B", doNothing, ("A"), ("D"));
173 ASSERT_ADD_INITIALIZER(graph, "C", doNothing, ("A"), ("D"));
174 ASSERT_EQUALS(Status::OK(), graph.topSort(&nodeNames));
175 ASSERT_EQUALS(4U, nodeNames.size());
176 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "A");
177 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "B");
178 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "C");
179 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "D");
180 ASSERT_EQUALS("A", nodeNames.front());
181 ASSERT_EQUALS("D", nodeNames.back());
182 }
183
TEST(InitializerDependencyGraphTest,TopSortWithDiamondGeneral2)184 TEST(InitializerDependencyGraphTest, TopSortWithDiamondGeneral2) {
185 /*
186 * This tests top-sorting a simple diamond, where A and D specify all prerequisites and
187 * dependents.
188 *
189 * B
190 * / ^
191 * v \
192 * A D
193 * ^ /
194 * \ v
195 * C
196 */
197 InitializerDependencyGraph graph;
198 std::vector<std::string> nodeNames;
199 ASSERT_ADD_INITIALIZER(graph, "A", doNothing, MONGO_NO_PREREQUISITES, ("B", "C"));
200 ASSERT_ADD_INITIALIZER(graph, "D", doNothing, ("C", "B"), MONGO_NO_DEPENDENTS);
201 ASSERT_ADD_INITIALIZER(graph, "B", doNothing, MONGO_NO_PREREQUISITES, MONGO_NO_DEPENDENTS);
202 ASSERT_ADD_INITIALIZER(graph, "C", doNothing, MONGO_NO_PREREQUISITES, MONGO_NO_DEPENDENTS);
203 ASSERT_EQUALS(Status::OK(), graph.topSort(&nodeNames));
204 ASSERT_EQUALS(4U, nodeNames.size());
205 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "A");
206 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "B");
207 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "C");
208 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "D");
209 ASSERT_EQUALS("A", nodeNames.front());
210 ASSERT_EQUALS("D", nodeNames.back());
211 }
212
TEST(InitializerDependencyGraphTest,TopSortWithDiamondGeneral3)213 TEST(InitializerDependencyGraphTest, TopSortWithDiamondGeneral3) {
214 /*
215 * This tests top-sorting a simple diamond, where A and D specify all prerequisites and
216 * dependents, but so do B and C.
217 *
218 * B
219 * / ^
220 * v \
221 * A D
222 * ^ /
223 * \ v
224 * C
225 */
226 InitializerDependencyGraph graph;
227 std::vector<std::string> nodeNames;
228 ASSERT_ADD_INITIALIZER(graph, "A", doNothing, MONGO_NO_PREREQUISITES, ("B", "C"));
229 ASSERT_ADD_INITIALIZER(graph, "D", doNothing, ("C", "B"), MONGO_NO_DEPENDENTS);
230 ASSERT_ADD_INITIALIZER(graph, "B", doNothing, ("A"), ("D"));
231 ASSERT_ADD_INITIALIZER(graph, "C", doNothing, ("A"), ("D"));
232 ASSERT_EQUALS(Status::OK(), graph.topSort(&nodeNames));
233 ASSERT_EQUALS(4U, nodeNames.size());
234 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "A");
235 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "B");
236 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "C");
237 ASSERT_EXACTLY_ONE_IN_CONTAINER(nodeNames, "D");
238 ASSERT_EQUALS("A", nodeNames.front());
239 ASSERT_EQUALS("D", nodeNames.back());
240 }
241
TEST(InitializerDependencyGraphTest,TopSortWithDiamondAndCycle)242 TEST(InitializerDependencyGraphTest, TopSortWithDiamondAndCycle) {
243 /*
244 * This tests top-sorting a graph with a cycle, which should fail..
245 *
246 * B <- E
247 * / ^ ^
248 * v \ /
249 * A D
250 * ^ /
251 * \ v
252 * C
253 */
254 InitializerDependencyGraph graph;
255 std::vector<std::string> nodeNames;
256 ASSERT_ADD_INITIALIZER(graph, "A", doNothing, MONGO_NO_PREREQUISITES, ("B", "C"));
257 ASSERT_ADD_INITIALIZER(graph, "D", doNothing, ("C", "B"), MONGO_NO_DEPENDENTS);
258 ASSERT_ADD_INITIALIZER(graph, "B", doNothing, MONGO_NO_PREREQUISITES, MONGO_NO_DEPENDENTS);
259 ASSERT_ADD_INITIALIZER(graph, "C", doNothing, MONGO_NO_PREREQUISITES, MONGO_NO_DEPENDENTS);
260 ASSERT_ADD_INITIALIZER(graph, "E", doNothing, ("D"), ("B"));
261 ASSERT_EQUALS(ErrorCodes::GraphContainsCycle, graph.topSort(&nodeNames));
262 ASSERT_EQUALS(4U, nodeNames.size());
263 ASSERT_EQUALS(nodeNames.front(), nodeNames.back());
264 ASSERT_AT_LEAST_N_IN_CONTAINER(1, nodeNames, "D");
265 ASSERT_AT_LEAST_N_IN_CONTAINER(1, nodeNames, "E");
266 ASSERT_AT_LEAST_N_IN_CONTAINER(1, nodeNames, "B");
267 ASSERT_EXACTLY_N_IN_CONTAINER(0, nodeNames, "A");
268 ASSERT_EXACTLY_N_IN_CONTAINER(0, nodeNames, "C");
269 }
270
TEST(InitializerDependencyGraphTest,TopSortFailsWhenMissingPrerequisite)271 TEST(InitializerDependencyGraphTest, TopSortFailsWhenMissingPrerequisite) {
272 /*
273 * If a node names a never-declared prerequisite, topSort should fail.
274 */
275 InitializerDependencyGraph graph;
276 std::vector<std::string> nodeNames;
277 ASSERT_ADD_INITIALIZER(graph, "B", doNothing, ("A"), MONGO_NO_DEPENDENTS);
278 auto status = graph.topSort(&nodeNames);
279 ASSERT_EQUALS(ErrorCodes::BadValue, status);
280 ASSERT_STRING_CONTAINS(status.reason(), "depends on missing initializer A");
281 }
282
TEST(InitializerDependencyGraphTest,TopSortFailsWhenMissingDependent)283 TEST(InitializerDependencyGraphTest, TopSortFailsWhenMissingDependent) {
284 /*
285 * If a node names a never-declared dependent, topSort should fail.
286 */
287 InitializerDependencyGraph graph;
288 std::vector<std::string> nodeNames;
289 ASSERT_ADD_INITIALIZER(graph, "A", doNothing, MONGO_NO_PREREQUISITES, ("B"));
290 auto status = graph.topSort(&nodeNames);
291 ASSERT_EQUALS(ErrorCodes::BadValue, status);
292 ASSERT_STRING_CONTAINS(status.reason(), "No implementation provided for initializer B");
293 }
294
295 } // namespace
296 } // namespace mongo
297