robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2015 Google Inc. |
| 3 | * |
| 4 | * Use of this source code is governed by a BSD-style license that can be |
| 5 | * found in the LICENSE file. |
| 6 | */ |
| 7 | |
Mike Klein | c0bd9f9 | 2019-04-23 12:05:21 -0500 | [diff] [blame] | 8 | #include "include/utils/SkRandom.h" |
Robert Phillips | fbbc3bb | 2020-11-16 14:58:56 -0500 | [diff] [blame] | 9 | #include "src/gpu/GrTTopoSort.h" |
Mike Klein | c0bd9f9 | 2019-04-23 12:05:21 -0500 | [diff] [blame] | 10 | #include "tests/Test.h" |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 11 | |
Mike Klein | c0bd9f9 | 2019-04-23 12:05:21 -0500 | [diff] [blame] | 12 | #include "tools/ToolUtils.h" |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 13 | |
Mike Klein | ea3f014 | 2019-03-20 11:12:10 -0500 | [diff] [blame] | 14 | typedef void (*CreateGraphPF)(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 15 | |
| 16 | /* Simple diamond |
| 17 | * 3 |
Robert Phillips | a186c35 | 2020-11-17 13:22:05 -0500 | [diff] [blame] | 18 | * . . |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 19 | * / \ |
| 20 | * 1 2 |
Robert Phillips | a186c35 | 2020-11-17 13:22:05 -0500 | [diff] [blame] | 21 | * . . |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 22 | * \ / |
| 23 | * 0 |
| 24 | */ |
Mike Klein | ea3f014 | 2019-03-20 11:12:10 -0500 | [diff] [blame] | 25 | static void create_graph0(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph) { |
| 26 | ToolUtils::TopoTestNode::AllocNodes(graph, 4); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 27 | |
Robert Phillips | 4150eea | 2018-02-07 17:08:21 -0500 | [diff] [blame] | 28 | (*graph)[0]->dependsOn((*graph)[1].get()); |
| 29 | (*graph)[0]->dependsOn((*graph)[2].get()); |
| 30 | (*graph)[1]->dependsOn((*graph)[3].get()); |
| 31 | (*graph)[2]->dependsOn((*graph)[3].get()); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 32 | } |
| 33 | |
| 34 | /* Simple chain |
| 35 | * 3 |
Robert Phillips | a186c35 | 2020-11-17 13:22:05 -0500 | [diff] [blame] | 36 | * ^ |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 37 | * | |
| 38 | * 2 |
Robert Phillips | a186c35 | 2020-11-17 13:22:05 -0500 | [diff] [blame] | 39 | * ^ |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 40 | * | |
| 41 | * 1 |
Robert Phillips | a186c35 | 2020-11-17 13:22:05 -0500 | [diff] [blame] | 42 | * ^ |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 43 | * | |
| 44 | * 0 |
| 45 | */ |
Mike Klein | ea3f014 | 2019-03-20 11:12:10 -0500 | [diff] [blame] | 46 | static void create_graph1(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph) { |
| 47 | ToolUtils::TopoTestNode::AllocNodes(graph, 4); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 48 | |
Robert Phillips | 4150eea | 2018-02-07 17:08:21 -0500 | [diff] [blame] | 49 | (*graph)[0]->dependsOn((*graph)[1].get()); |
| 50 | (*graph)[1]->dependsOn((*graph)[2].get()); |
| 51 | (*graph)[2]->dependsOn((*graph)[3].get()); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 52 | } |
| 53 | |
Robert Phillips | a186c35 | 2020-11-17 13:22:05 -0500 | [diff] [blame] | 54 | /* Simple Loop |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 55 | * 2 |
Robert Phillips | a186c35 | 2020-11-17 13:22:05 -0500 | [diff] [blame] | 56 | * / . |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 57 | * / \ |
Robert Phillips | a186c35 | 2020-11-17 13:22:05 -0500 | [diff] [blame] | 58 | * . \ |
| 59 | * 0 ---> 1 |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 60 | */ |
Mike Klein | ea3f014 | 2019-03-20 11:12:10 -0500 | [diff] [blame] | 61 | static void create_graph2(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph) { |
| 62 | ToolUtils::TopoTestNode::AllocNodes(graph, 3); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 63 | |
Robert Phillips | 4150eea | 2018-02-07 17:08:21 -0500 | [diff] [blame] | 64 | (*graph)[0]->dependsOn((*graph)[1].get()); |
| 65 | (*graph)[1]->dependsOn((*graph)[2].get()); |
| 66 | (*graph)[2]->dependsOn((*graph)[0].get()); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 67 | } |
| 68 | |
| 69 | /* Double diamond |
| 70 | * 6 |
Robert Phillips | a186c35 | 2020-11-17 13:22:05 -0500 | [diff] [blame] | 71 | * . . |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 72 | * / \ |
| 73 | * 4 5 |
Robert Phillips | a186c35 | 2020-11-17 13:22:05 -0500 | [diff] [blame] | 74 | * . . |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 75 | * \ / |
| 76 | * 3 |
Robert Phillips | a186c35 | 2020-11-17 13:22:05 -0500 | [diff] [blame] | 77 | * . . |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 78 | * / \ |
| 79 | * 1 2 |
Robert Phillips | a186c35 | 2020-11-17 13:22:05 -0500 | [diff] [blame] | 80 | * . . |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 81 | * \ / |
| 82 | * 0 |
| 83 | */ |
Mike Klein | ea3f014 | 2019-03-20 11:12:10 -0500 | [diff] [blame] | 84 | static void create_graph3(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph) { |
| 85 | ToolUtils::TopoTestNode::AllocNodes(graph, 7); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 86 | |
Robert Phillips | 4150eea | 2018-02-07 17:08:21 -0500 | [diff] [blame] | 87 | (*graph)[0]->dependsOn((*graph)[1].get()); |
| 88 | (*graph)[0]->dependsOn((*graph)[2].get()); |
| 89 | (*graph)[1]->dependsOn((*graph)[3].get()); |
| 90 | (*graph)[2]->dependsOn((*graph)[3].get()); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 91 | |
Robert Phillips | 4150eea | 2018-02-07 17:08:21 -0500 | [diff] [blame] | 92 | (*graph)[3]->dependsOn((*graph)[4].get()); |
| 93 | (*graph)[3]->dependsOn((*graph)[5].get()); |
| 94 | (*graph)[4]->dependsOn((*graph)[6].get()); |
| 95 | (*graph)[5]->dependsOn((*graph)[6].get()); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 96 | } |
| 97 | |
| 98 | /* Two independent diamonds |
| 99 | * 3 7 |
Robert Phillips | a186c35 | 2020-11-17 13:22:05 -0500 | [diff] [blame] | 100 | * . . . . |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 101 | * / \ / \ |
| 102 | * 1 2 5 6 |
Robert Phillips | a186c35 | 2020-11-17 13:22:05 -0500 | [diff] [blame] | 103 | * . . . . |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 104 | * \ / \ / |
| 105 | * 0 4 |
| 106 | */ |
Mike Klein | ea3f014 | 2019-03-20 11:12:10 -0500 | [diff] [blame] | 107 | static void create_graph4(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph) { |
| 108 | ToolUtils::TopoTestNode::AllocNodes(graph, 8); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 109 | |
Robert Phillips | 4150eea | 2018-02-07 17:08:21 -0500 | [diff] [blame] | 110 | (*graph)[0]->dependsOn((*graph)[1].get()); |
| 111 | (*graph)[0]->dependsOn((*graph)[2].get()); |
| 112 | (*graph)[1]->dependsOn((*graph)[3].get()); |
| 113 | (*graph)[2]->dependsOn((*graph)[3].get()); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 114 | |
Robert Phillips | 4150eea | 2018-02-07 17:08:21 -0500 | [diff] [blame] | 115 | (*graph)[4]->dependsOn((*graph)[5].get()); |
| 116 | (*graph)[4]->dependsOn((*graph)[6].get()); |
| 117 | (*graph)[5]->dependsOn((*graph)[7].get()); |
| 118 | (*graph)[6]->dependsOn((*graph)[7].get()); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 119 | } |
| 120 | |
Robert Phillips | a186c35 | 2020-11-17 13:22:05 -0500 | [diff] [blame] | 121 | /* Two linked diamonds w/ two loops |
| 122 | * 5 6 |
| 123 | * / . . \ |
| 124 | * . \ / . |
| 125 | * 2 3 4 |
| 126 | * \ . / |
| 127 | * . / \ . |
| 128 | * 0 1 |
| 129 | */ |
| 130 | static void create_graph5(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph) { |
| 131 | ToolUtils::TopoTestNode::AllocNodes(graph, 7); |
| 132 | |
| 133 | (*graph)[0]->dependsOn((*graph)[3].get()); |
| 134 | (*graph)[1]->dependsOn((*graph)[3].get()); |
| 135 | (*graph)[2]->dependsOn((*graph)[0].get()); |
| 136 | (*graph)[3]->dependsOn((*graph)[5].get()); |
| 137 | (*graph)[3]->dependsOn((*graph)[6].get()); |
| 138 | (*graph)[4]->dependsOn((*graph)[1].get()); |
| 139 | (*graph)[5]->dependsOn((*graph)[2].get()); |
| 140 | (*graph)[6]->dependsOn((*graph)[4].get()); |
| 141 | } |
| 142 | |
| 143 | /* Two disjoint loops |
| 144 | * 2 5 |
| 145 | * / . / . |
| 146 | * / \ / \ |
| 147 | * . \ . \ |
| 148 | * 0 ---> 1 3 ---> 4 |
| 149 | */ |
| 150 | static void create_graph6(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph) { |
| 151 | ToolUtils::TopoTestNode::AllocNodes(graph, 6); |
| 152 | |
| 153 | (*graph)[0]->dependsOn((*graph)[1].get()); |
| 154 | (*graph)[1]->dependsOn((*graph)[2].get()); |
| 155 | (*graph)[2]->dependsOn((*graph)[0].get()); |
| 156 | |
| 157 | (*graph)[3]->dependsOn((*graph)[4].get()); |
| 158 | (*graph)[4]->dependsOn((*graph)[5].get()); |
| 159 | (*graph)[5]->dependsOn((*graph)[3].get()); |
| 160 | } |
| 161 | |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 162 | DEF_TEST(TopoSort, reporter) { |
| 163 | SkRandom rand; |
| 164 | |
| 165 | struct { |
| 166 | CreateGraphPF fCreate; |
| 167 | bool fExpectedResult; |
| 168 | } tests[] = { |
| 169 | { create_graph0, true }, |
| 170 | { create_graph1, true }, |
| 171 | { create_graph2, false }, |
| 172 | { create_graph3, true }, |
| 173 | { create_graph4, true }, |
Robert Phillips | a186c35 | 2020-11-17 13:22:05 -0500 | [diff] [blame] | 174 | { create_graph5, false }, |
| 175 | { create_graph6, false }, |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 176 | }; |
| 177 | |
| 178 | for (size_t i = 0; i < SK_ARRAY_COUNT(tests); ++i) { |
Mike Klein | ea3f014 | 2019-03-20 11:12:10 -0500 | [diff] [blame] | 179 | SkTArray<sk_sp<ToolUtils::TopoTestNode>> graph; |
halcanary | 9d524f2 | 2016-03-29 09:03:52 -0700 | [diff] [blame] | 180 | |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 181 | (tests[i].fCreate)(&graph); |
| 182 | |
Robert Phillips | a186c35 | 2020-11-17 13:22:05 -0500 | [diff] [blame] | 183 | const int numNodes = graph.count(); |
| 184 | |
Mike Klein | ea3f014 | 2019-03-20 11:12:10 -0500 | [diff] [blame] | 185 | ToolUtils::TopoTestNode::Shuffle(&graph, &rand); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 186 | |
Robert Phillips | fbbc3bb | 2020-11-16 14:58:56 -0500 | [diff] [blame] | 187 | bool actualResult = GrTTopoSort<ToolUtils::TopoTestNode>(&graph); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 188 | REPORTER_ASSERT(reporter, actualResult == tests[i].fExpectedResult); |
Robert Phillips | a186c35 | 2020-11-17 13:22:05 -0500 | [diff] [blame] | 189 | REPORTER_ASSERT(reporter, numNodes == graph.count()); |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 190 | |
| 191 | if (tests[i].fExpectedResult) { |
Robert Phillips | a186c35 | 2020-11-17 13:22:05 -0500 | [diff] [blame] | 192 | for (const auto& node : graph) { |
| 193 | REPORTER_ASSERT(reporter, node->check()); |
| 194 | } |
| 195 | } else { |
| 196 | // When the topological sort fails all the nodes should still appear in the result |
| 197 | // but their order can be somewhat arbitrary. |
| 198 | std::vector<bool> seen(numNodes, false); |
| 199 | |
| 200 | for (const auto& node : graph) { |
| 201 | SkASSERT(node); |
| 202 | SkASSERT(!seen[node->id()]); |
| 203 | seen[node->id()] = true; |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 204 | } |
| 205 | } |
| 206 | |
| 207 | //SkDEBUGCODE(print(graph);) |
robertphillips | 423f646 | 2015-10-19 12:15:55 -0700 | [diff] [blame] | 208 | } |
| 209 | } |