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 9 namespace { 10 11 class DependencyGraphTest : public testing::Test { 12 }; 13 14 class 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. 31 TEST_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. 47 TEST_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. 68 TEST_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. 93 TEST_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. 129 TEST_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