components/keyed_service/core/dependency_graph_unittest.cc

   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