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