1 // Copyright 2014 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/keyed_service/core/dependency_graph.h"
6 #include "components/keyed_service/core/dependency_node.h"
7 #include "testing/gtest/include/gtest/gtest.h"
8
9 namespace {
10
11 class DependencyGraphTest : public testing::Test {};
12
13 class DummyNode : public DependencyNode {
14 public:
DummyNode(DependencyGraph * graph)15 explicit DummyNode(DependencyGraph* graph) : dependency_graph_(graph) {
16 dependency_graph_->AddNode(this);
17 }
18
~DummyNode()19 ~DummyNode() { dependency_graph_->RemoveNode(this); }
20
21 private:
22 DependencyGraph* dependency_graph_;
23
24 DISALLOW_COPY_AND_ASSIGN(DummyNode);
25 };
26
27 // Tests that we can deal with a single component.
TEST_F(DependencyGraphTest,SingleCase)28 TEST_F(DependencyGraphTest, SingleCase) {
29 DependencyGraph graph;
30 DummyNode node(&graph);
31
32 std::vector<DependencyNode*> construction_order;
33 EXPECT_TRUE(graph.GetConstructionOrder(&construction_order));
34 ASSERT_EQ(1U, construction_order.size());
35 EXPECT_EQ(&node, construction_order[0]);
36
37 std::vector<DependencyNode*> destruction_order;
38 EXPECT_TRUE(graph.GetDestructionOrder(&destruction_order));
39 ASSERT_EQ(1U, destruction_order.size());
40 EXPECT_EQ(&node, destruction_order[0]);
41 }
42
43 // Tests that we get a simple one component depends on the other case.
TEST_F(DependencyGraphTest,SimpleDependency)44 TEST_F(DependencyGraphTest, SimpleDependency) {
45 DependencyGraph graph;
46 DummyNode parent(&graph);
47 DummyNode child(&graph);
48
49 graph.AddEdge(&parent, &child);
50
51 std::vector<DependencyNode*> construction_order;
52 EXPECT_TRUE(graph.GetConstructionOrder(&construction_order));
53 ASSERT_EQ(2U, construction_order.size());
54 EXPECT_EQ(&parent, construction_order[0]);
55 EXPECT_EQ(&child, construction_order[1]);
56
57 std::vector<DependencyNode*> destruction_order;
58 EXPECT_TRUE(graph.GetDestructionOrder(&destruction_order));
59 ASSERT_EQ(2U, destruction_order.size());
60 EXPECT_EQ(&child, destruction_order[0]);
61 EXPECT_EQ(&parent, destruction_order[1]);
62 }
63
64 // Tests two children, one parent.
TEST_F(DependencyGraphTest,TwoChildrenOneParent)65 TEST_F(DependencyGraphTest, TwoChildrenOneParent) {
66 DependencyGraph graph;
67 DummyNode parent(&graph);
68 DummyNode child1(&graph);
69 DummyNode child2(&graph);
70
71 graph.AddEdge(&parent, &child1);
72 graph.AddEdge(&parent, &child2);
73
74 std::vector<DependencyNode*> construction_order;
75 EXPECT_TRUE(graph.GetConstructionOrder(&construction_order));
76 ASSERT_EQ(3U, construction_order.size());
77 EXPECT_EQ(&parent, construction_order[0]);
78 EXPECT_EQ(&child1, construction_order[1]);
79 EXPECT_EQ(&child2, construction_order[2]);
80
81 std::vector<DependencyNode*> destruction_order;
82 EXPECT_TRUE(graph.GetDestructionOrder(&destruction_order));
83 ASSERT_EQ(3U, destruction_order.size());
84 EXPECT_EQ(&child2, destruction_order[0]);
85 EXPECT_EQ(&child1, destruction_order[1]);
86 EXPECT_EQ(&parent, destruction_order[2]);
87 }
88
89 // Tests an M configuration.
TEST_F(DependencyGraphTest,MConfiguration)90 TEST_F(DependencyGraphTest, MConfiguration) {
91 DependencyGraph graph;
92
93 DummyNode parent1(&graph);
94 DummyNode parent2(&graph);
95
96 DummyNode child_of_1(&graph);
97 graph.AddEdge(&parent1, &child_of_1);
98
99 DummyNode child_of_12(&graph);
100 graph.AddEdge(&parent1, &child_of_12);
101 graph.AddEdge(&parent2, &child_of_12);
102
103 DummyNode child_of_2(&graph);
104 graph.AddEdge(&parent2, &child_of_2);
105
106 std::vector<DependencyNode*> construction_order;
107 EXPECT_TRUE(graph.GetConstructionOrder(&construction_order));
108 ASSERT_EQ(5U, construction_order.size());
109 EXPECT_EQ(&parent1, construction_order[0]);
110 EXPECT_EQ(&parent2, construction_order[1]);
111 EXPECT_EQ(&child_of_1, construction_order[2]);
112 EXPECT_EQ(&child_of_12, construction_order[3]);
113 EXPECT_EQ(&child_of_2, construction_order[4]);
114
115 std::vector<DependencyNode*> destruction_order;
116 EXPECT_TRUE(graph.GetDestructionOrder(&destruction_order));
117 ASSERT_EQ(5U, destruction_order.size());
118 EXPECT_EQ(&child_of_2, destruction_order[0]);
119 EXPECT_EQ(&child_of_12, destruction_order[1]);
120 EXPECT_EQ(&child_of_1, destruction_order[2]);
121 EXPECT_EQ(&parent2, destruction_order[3]);
122 EXPECT_EQ(&parent1, destruction_order[4]);
123 }
124
125 // Tests that it can deal with a simple diamond.
TEST_F(DependencyGraphTest,DiamondConfiguration)126 TEST_F(DependencyGraphTest, DiamondConfiguration) {
127 DependencyGraph graph;
128
129 DummyNode parent(&graph);
130
131 DummyNode middle1(&graph);
132 graph.AddEdge(&parent, &middle1);
133
134 DummyNode middle2(&graph);
135 graph.AddEdge(&parent, &middle2);
136
137 DummyNode bottom(&graph);
138 graph.AddEdge(&middle1, &bottom);
139 graph.AddEdge(&middle2, &bottom);
140
141 std::vector<DependencyNode*> construction_order;
142 EXPECT_TRUE(graph.GetConstructionOrder(&construction_order));
143 ASSERT_EQ(4U, construction_order.size());
144 EXPECT_EQ(&parent, construction_order[0]);
145 EXPECT_EQ(&middle1, construction_order[1]);
146 EXPECT_EQ(&middle2, construction_order[2]);
147 EXPECT_EQ(&bottom, construction_order[3]);
148
149 std::vector<DependencyNode*> destruction_order;
150 EXPECT_TRUE(graph.GetDestructionOrder(&destruction_order));
151 ASSERT_EQ(4U, destruction_order.size());
152 EXPECT_EQ(&bottom, destruction_order[0]);
153 EXPECT_EQ(&middle2, destruction_order[1]);
154 EXPECT_EQ(&middle1, destruction_order[2]);
155 EXPECT_EQ(&parent, destruction_order[3]);
156 }
157
158 } // namespace
159