dependency_graph_unittest.cc 7.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219
  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. #include "components/keyed_service/core/dependency_graph.h"
  5. #include "base/bind.h"
  6. #include "base/memory/raw_ptr.h"
  7. #include "base/numerics/safe_conversions.h"
  8. #include "base/strings/string_piece.h"
  9. #include "components/keyed_service/core/dependency_node.h"
  10. #include "testing/gtest/include/gtest/gtest.h"
  11. #include "third_party/re2/src/re2/re2.h"
  12. namespace {
  13. class DependencyGraphTest : public testing::Test {};
  14. class DummyNode : public DependencyNode {
  15. public:
  16. explicit DummyNode(DependencyGraph* graph) : dependency_graph_(graph) {
  17. dependency_graph_->AddNode(this);
  18. }
  19. DummyNode(const DummyNode&) = delete;
  20. DummyNode& operator=(const DummyNode&) = delete;
  21. ~DummyNode() { dependency_graph_->RemoveNode(this); }
  22. private:
  23. raw_ptr<DependencyGraph> dependency_graph_;
  24. };
  25. // Tests that we can deal with a single component.
  26. TEST_F(DependencyGraphTest, SingleCase) {
  27. DependencyGraph graph;
  28. DummyNode node(&graph);
  29. std::vector<DependencyNode*> construction_order;
  30. EXPECT_TRUE(graph.GetConstructionOrder(&construction_order));
  31. ASSERT_EQ(1U, construction_order.size());
  32. EXPECT_EQ(&node, construction_order[0]);
  33. std::vector<DependencyNode*> destruction_order;
  34. EXPECT_TRUE(graph.GetDestructionOrder(&destruction_order));
  35. ASSERT_EQ(1U, destruction_order.size());
  36. EXPECT_EQ(&node, destruction_order[0]);
  37. }
  38. // Tests that we get a simple one component depends on the other case.
  39. TEST_F(DependencyGraphTest, SimpleDependency) {
  40. DependencyGraph graph;
  41. DummyNode parent(&graph);
  42. DummyNode child(&graph);
  43. graph.AddEdge(&parent, &child);
  44. std::vector<DependencyNode*> construction_order;
  45. EXPECT_TRUE(graph.GetConstructionOrder(&construction_order));
  46. ASSERT_EQ(2U, construction_order.size());
  47. EXPECT_EQ(&parent, construction_order[0]);
  48. EXPECT_EQ(&child, construction_order[1]);
  49. std::vector<DependencyNode*> destruction_order;
  50. EXPECT_TRUE(graph.GetDestructionOrder(&destruction_order));
  51. ASSERT_EQ(2U, destruction_order.size());
  52. EXPECT_EQ(&child, destruction_order[0]);
  53. EXPECT_EQ(&parent, destruction_order[1]);
  54. }
  55. // Tests two children, one parent.
  56. TEST_F(DependencyGraphTest, TwoChildrenOneParent) {
  57. DependencyGraph graph;
  58. DummyNode parent(&graph);
  59. DummyNode child1(&graph);
  60. DummyNode child2(&graph);
  61. graph.AddEdge(&parent, &child1);
  62. graph.AddEdge(&parent, &child2);
  63. std::vector<DependencyNode*> construction_order;
  64. EXPECT_TRUE(graph.GetConstructionOrder(&construction_order));
  65. ASSERT_EQ(3U, construction_order.size());
  66. EXPECT_EQ(&parent, construction_order[0]);
  67. EXPECT_EQ(&child1, construction_order[1]);
  68. EXPECT_EQ(&child2, construction_order[2]);
  69. std::vector<DependencyNode*> destruction_order;
  70. EXPECT_TRUE(graph.GetDestructionOrder(&destruction_order));
  71. ASSERT_EQ(3U, destruction_order.size());
  72. EXPECT_EQ(&child2, destruction_order[0]);
  73. EXPECT_EQ(&child1, destruction_order[1]);
  74. EXPECT_EQ(&parent, destruction_order[2]);
  75. }
  76. // Tests an M configuration.
  77. TEST_F(DependencyGraphTest, MConfiguration) {
  78. DependencyGraph graph;
  79. DummyNode parent1(&graph);
  80. DummyNode parent2(&graph);
  81. DummyNode child_of_1(&graph);
  82. graph.AddEdge(&parent1, &child_of_1);
  83. DummyNode child_of_12(&graph);
  84. graph.AddEdge(&parent1, &child_of_12);
  85. graph.AddEdge(&parent2, &child_of_12);
  86. DummyNode child_of_2(&graph);
  87. graph.AddEdge(&parent2, &child_of_2);
  88. std::vector<DependencyNode*> construction_order;
  89. EXPECT_TRUE(graph.GetConstructionOrder(&construction_order));
  90. ASSERT_EQ(5U, construction_order.size());
  91. EXPECT_EQ(&parent1, construction_order[0]);
  92. EXPECT_EQ(&parent2, construction_order[1]);
  93. EXPECT_EQ(&child_of_1, construction_order[2]);
  94. EXPECT_EQ(&child_of_12, construction_order[3]);
  95. EXPECT_EQ(&child_of_2, construction_order[4]);
  96. std::vector<DependencyNode*> destruction_order;
  97. EXPECT_TRUE(graph.GetDestructionOrder(&destruction_order));
  98. ASSERT_EQ(5U, destruction_order.size());
  99. EXPECT_EQ(&child_of_2, destruction_order[0]);
  100. EXPECT_EQ(&child_of_12, destruction_order[1]);
  101. EXPECT_EQ(&child_of_1, destruction_order[2]);
  102. EXPECT_EQ(&parent2, destruction_order[3]);
  103. EXPECT_EQ(&parent1, destruction_order[4]);
  104. }
  105. // Tests that it can deal with a simple diamond.
  106. TEST_F(DependencyGraphTest, DiamondConfiguration) {
  107. DependencyGraph graph;
  108. DummyNode parent(&graph);
  109. DummyNode middle1(&graph);
  110. graph.AddEdge(&parent, &middle1);
  111. DummyNode middle2(&graph);
  112. graph.AddEdge(&parent, &middle2);
  113. DummyNode bottom(&graph);
  114. graph.AddEdge(&middle1, &bottom);
  115. graph.AddEdge(&middle2, &bottom);
  116. std::vector<DependencyNode*> construction_order;
  117. EXPECT_TRUE(graph.GetConstructionOrder(&construction_order));
  118. ASSERT_EQ(4U, construction_order.size());
  119. EXPECT_EQ(&parent, construction_order[0]);
  120. EXPECT_EQ(&middle1, construction_order[1]);
  121. EXPECT_EQ(&middle2, construction_order[2]);
  122. EXPECT_EQ(&bottom, construction_order[3]);
  123. std::vector<DependencyNode*> destruction_order;
  124. EXPECT_TRUE(graph.GetDestructionOrder(&destruction_order));
  125. ASSERT_EQ(4U, destruction_order.size());
  126. EXPECT_EQ(&bottom, destruction_order[0]);
  127. EXPECT_EQ(&middle2, destruction_order[1]);
  128. EXPECT_EQ(&middle1, destruction_order[2]);
  129. EXPECT_EQ(&parent, destruction_order[3]);
  130. }
  131. std::string NodeNameProvider(const std::string& name, DependencyNode* node) {
  132. return name;
  133. }
  134. // When this returns true, then |name| is a valid ID according to the DOT
  135. // language specification [1]. Note that DOT language also allows HTML strings
  136. // as valid identifiers, but those are not used in the production code calling
  137. // the tested DumpAsGraphviz.
  138. // [1] http://www.graphviz.org/content/dot-language
  139. bool IsValidDotId(base::StringPiece name) {
  140. static const char pattern[] =
  141. "[a-zA-Z\\200-\\377_][0-9a-zA-Z\\200-\\377_]*"
  142. "|-?(?:\\.[0-9]+|[0-9]+(\\.[0-9]*)?)"
  143. "|\"(?:[^\"]|\\\")*\"";
  144. return RE2::FullMatch(
  145. re2::StringPiece(name.data(), base::checked_cast<int>(name.size())),
  146. pattern);
  147. }
  148. // Returns the source name of the first edge of the graphstr described in DOT
  149. // format in |graphstr|.
  150. base::StringPiece LocateNodeNameInGraph(base::StringPiece graphstr) {
  151. re2::StringPiece name;
  152. EXPECT_TRUE(RE2::FullMatch(
  153. re2::StringPiece(graphstr.data(),
  154. base::checked_cast<int>(graphstr.size())),
  155. "(?sm).*^[ \\t]*([^ \\t]*(?:[ \\t]+[^ \\t]+)*)[ \\t]*->.*", &name))
  156. << "graphstr=" << graphstr;
  157. return base::StringPiece(name.data(), name.size());
  158. }
  159. // Node names in the dependency graph should be properly escaped.
  160. TEST_F(DependencyGraphTest, DumpAsGraphviz_Escaping) {
  161. const char* names[] = {
  162. "namespace::Service", "justAlphabeticService",
  163. "Service_with_underscores", "AlphaNumeric123Service",
  164. "123ServiceStartingWithDigits", "service with spaces",
  165. "ServiceWith\"Quotes"};
  166. DependencyGraph graph;
  167. DummyNode parent(&graph);
  168. DummyNode child(&graph);
  169. graph.AddEdge(&parent, &child);
  170. for (const char* name : names) {
  171. SCOPED_TRACE(testing::Message("name=") << name);
  172. std::string graph_str = graph.DumpAsGraphviz(
  173. "Test", base::BindRepeating(&NodeNameProvider, name));
  174. base::StringPiece dumped_name(LocateNodeNameInGraph(graph_str));
  175. EXPECT_TRUE(IsValidDotId(dumped_name)) << "dumped_name=" << dumped_name;
  176. }
  177. }
  178. } // namespace