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: 15 explicit DummyNode(DependencyGraph* graph) : dependency_graph_(graph) { 16 dependency_graph_->AddNode(this); 17 } 18 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. 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. 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. 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. 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. 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
