123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219 |
- // Copyright 2014 The Chromium Authors. All rights reserved.
- // Use of this source code is governed by a BSD-style license that can be
- // found in the LICENSE file.
- #include "components/keyed_service/core/dependency_graph.h"
- #include "base/bind.h"
- #include "base/memory/raw_ptr.h"
- #include "base/numerics/safe_conversions.h"
- #include "base/strings/string_piece.h"
- #include "components/keyed_service/core/dependency_node.h"
- #include "testing/gtest/include/gtest/gtest.h"
- #include "third_party/re2/src/re2/re2.h"
- namespace {
- class DependencyGraphTest : public testing::Test {};
- class DummyNode : public DependencyNode {
- public:
- explicit DummyNode(DependencyGraph* graph) : dependency_graph_(graph) {
- dependency_graph_->AddNode(this);
- }
- DummyNode(const DummyNode&) = delete;
- DummyNode& operator=(const DummyNode&) = delete;
- ~DummyNode() { dependency_graph_->RemoveNode(this); }
- private:
- raw_ptr<DependencyGraph> dependency_graph_;
- };
- // Tests that we can deal with a single component.
- TEST_F(DependencyGraphTest, SingleCase) {
- DependencyGraph graph;
- DummyNode node(&graph);
- std::vector<DependencyNode*> construction_order;
- EXPECT_TRUE(graph.GetConstructionOrder(&construction_order));
- ASSERT_EQ(1U, construction_order.size());
- EXPECT_EQ(&node, construction_order[0]);
- std::vector<DependencyNode*> destruction_order;
- EXPECT_TRUE(graph.GetDestructionOrder(&destruction_order));
- ASSERT_EQ(1U, destruction_order.size());
- EXPECT_EQ(&node, destruction_order[0]);
- }
- // Tests that we get a simple one component depends on the other case.
- TEST_F(DependencyGraphTest, SimpleDependency) {
- DependencyGraph graph;
- DummyNode parent(&graph);
- DummyNode child(&graph);
- graph.AddEdge(&parent, &child);
- std::vector<DependencyNode*> construction_order;
- EXPECT_TRUE(graph.GetConstructionOrder(&construction_order));
- ASSERT_EQ(2U, construction_order.size());
- EXPECT_EQ(&parent, construction_order[0]);
- EXPECT_EQ(&child, construction_order[1]);
- std::vector<DependencyNode*> destruction_order;
- EXPECT_TRUE(graph.GetDestructionOrder(&destruction_order));
- ASSERT_EQ(2U, destruction_order.size());
- EXPECT_EQ(&child, destruction_order[0]);
- EXPECT_EQ(&parent, destruction_order[1]);
- }
- // Tests two children, one parent.
- TEST_F(DependencyGraphTest, TwoChildrenOneParent) {
- DependencyGraph graph;
- DummyNode parent(&graph);
- DummyNode child1(&graph);
- DummyNode child2(&graph);
- graph.AddEdge(&parent, &child1);
- graph.AddEdge(&parent, &child2);
- std::vector<DependencyNode*> construction_order;
- EXPECT_TRUE(graph.GetConstructionOrder(&construction_order));
- ASSERT_EQ(3U, construction_order.size());
- EXPECT_EQ(&parent, construction_order[0]);
- EXPECT_EQ(&child1, construction_order[1]);
- EXPECT_EQ(&child2, construction_order[2]);
- std::vector<DependencyNode*> destruction_order;
- EXPECT_TRUE(graph.GetDestructionOrder(&destruction_order));
- ASSERT_EQ(3U, destruction_order.size());
- EXPECT_EQ(&child2, destruction_order[0]);
- EXPECT_EQ(&child1, destruction_order[1]);
- EXPECT_EQ(&parent, destruction_order[2]);
- }
- // Tests an M configuration.
- TEST_F(DependencyGraphTest, MConfiguration) {
- DependencyGraph graph;
- DummyNode parent1(&graph);
- DummyNode parent2(&graph);
- DummyNode child_of_1(&graph);
- graph.AddEdge(&parent1, &child_of_1);
- DummyNode child_of_12(&graph);
- graph.AddEdge(&parent1, &child_of_12);
- graph.AddEdge(&parent2, &child_of_12);
- DummyNode child_of_2(&graph);
- graph.AddEdge(&parent2, &child_of_2);
- std::vector<DependencyNode*> construction_order;
- EXPECT_TRUE(graph.GetConstructionOrder(&construction_order));
- ASSERT_EQ(5U, construction_order.size());
- EXPECT_EQ(&parent1, construction_order[0]);
- EXPECT_EQ(&parent2, construction_order[1]);
- EXPECT_EQ(&child_of_1, construction_order[2]);
- EXPECT_EQ(&child_of_12, construction_order[3]);
- EXPECT_EQ(&child_of_2, construction_order[4]);
- std::vector<DependencyNode*> destruction_order;
- EXPECT_TRUE(graph.GetDestructionOrder(&destruction_order));
- ASSERT_EQ(5U, destruction_order.size());
- EXPECT_EQ(&child_of_2, destruction_order[0]);
- EXPECT_EQ(&child_of_12, destruction_order[1]);
- EXPECT_EQ(&child_of_1, destruction_order[2]);
- EXPECT_EQ(&parent2, destruction_order[3]);
- EXPECT_EQ(&parent1, destruction_order[4]);
- }
- // Tests that it can deal with a simple diamond.
- TEST_F(DependencyGraphTest, DiamondConfiguration) {
- DependencyGraph graph;
- DummyNode parent(&graph);
- DummyNode middle1(&graph);
- graph.AddEdge(&parent, &middle1);
- DummyNode middle2(&graph);
- graph.AddEdge(&parent, &middle2);
- DummyNode bottom(&graph);
- graph.AddEdge(&middle1, &bottom);
- graph.AddEdge(&middle2, &bottom);
- std::vector<DependencyNode*> construction_order;
- EXPECT_TRUE(graph.GetConstructionOrder(&construction_order));
- ASSERT_EQ(4U, construction_order.size());
- EXPECT_EQ(&parent, construction_order[0]);
- EXPECT_EQ(&middle1, construction_order[1]);
- EXPECT_EQ(&middle2, construction_order[2]);
- EXPECT_EQ(&bottom, construction_order[3]);
- std::vector<DependencyNode*> destruction_order;
- EXPECT_TRUE(graph.GetDestructionOrder(&destruction_order));
- ASSERT_EQ(4U, destruction_order.size());
- EXPECT_EQ(&bottom, destruction_order[0]);
- EXPECT_EQ(&middle2, destruction_order[1]);
- EXPECT_EQ(&middle1, destruction_order[2]);
- EXPECT_EQ(&parent, destruction_order[3]);
- }
- std::string NodeNameProvider(const std::string& name, DependencyNode* node) {
- return name;
- }
- // When this returns true, then |name| is a valid ID according to the DOT
- // language specification [1]. Note that DOT language also allows HTML strings
- // as valid identifiers, but those are not used in the production code calling
- // the tested DumpAsGraphviz.
- // [1] http://www.graphviz.org/content/dot-language
- bool IsValidDotId(base::StringPiece name) {
- static const char pattern[] =
- "[a-zA-Z\\200-\\377_][0-9a-zA-Z\\200-\\377_]*"
- "|-?(?:\\.[0-9]+|[0-9]+(\\.[0-9]*)?)"
- "|\"(?:[^\"]|\\\")*\"";
- return RE2::FullMatch(
- re2::StringPiece(name.data(), base::checked_cast<int>(name.size())),
- pattern);
- }
- // Returns the source name of the first edge of the graphstr described in DOT
- // format in |graphstr|.
- base::StringPiece LocateNodeNameInGraph(base::StringPiece graphstr) {
- re2::StringPiece name;
- EXPECT_TRUE(RE2::FullMatch(
- re2::StringPiece(graphstr.data(),
- base::checked_cast<int>(graphstr.size())),
- "(?sm).*^[ \\t]*([^ \\t]*(?:[ \\t]+[^ \\t]+)*)[ \\t]*->.*", &name))
- << "graphstr=" << graphstr;
- return base::StringPiece(name.data(), name.size());
- }
- // Node names in the dependency graph should be properly escaped.
- TEST_F(DependencyGraphTest, DumpAsGraphviz_Escaping) {
- const char* names[] = {
- "namespace::Service", "justAlphabeticService",
- "Service_with_underscores", "AlphaNumeric123Service",
- "123ServiceStartingWithDigits", "service with spaces",
- "ServiceWith\"Quotes"};
- DependencyGraph graph;
- DummyNode parent(&graph);
- DummyNode child(&graph);
- graph.AddEdge(&parent, &child);
- for (const char* name : names) {
- SCOPED_TRACE(testing::Message("name=") << name);
- std::string graph_str = graph.DumpAsGraphviz(
- "Test", base::BindRepeating(&NodeNameProvider, name));
- base::StringPiece dumped_name(LocateNodeNameInGraph(graph_str));
- EXPECT_TRUE(IsValidDotId(dumped_name)) << "dumped_name=" << dumped_name;
- }
- }
- } // namespace
|