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
8 #include "include/core/SkRefCnt.h"
9 #include "include/core/SkSpan.h"
10 #include "include/core/SkTypes.h"
11 #include "include/private/base/SkTArray.h"
12 #include "src/base/SkRandom.h"
13 #include "src/gpu/ganesh/GrTTopoSort.h"
14 #include "tests/Test.h"
15 #include "tools/ToolUtils.h"
16
17 #include <cstddef>
18 #include <vector>
19
20 typedef void (*CreateGraphPF)(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph);
21
22 /* Simple diamond
23 * 3
24 * . .
25 * / \
26 * 1 2
27 * . .
28 * \ /
29 * 0
30 */
create_graph0(SkTArray<sk_sp<ToolUtils::TopoTestNode>> * graph)31 static void create_graph0(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph) {
32 ToolUtils::TopoTestNode::AllocNodes(graph, 4);
33
34 (*graph)[0]->dependsOn((*graph)[1].get());
35 (*graph)[0]->dependsOn((*graph)[2].get());
36 (*graph)[1]->dependsOn((*graph)[3].get());
37 (*graph)[2]->dependsOn((*graph)[3].get());
38 }
39
create_simple_chain(SkTArray<sk_sp<ToolUtils::TopoTestNode>> * graph,int n)40 static void create_simple_chain(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph, int n) {
41 ToolUtils::TopoTestNode::AllocNodes(graph, n);
42
43 for (int i = 0; i < n - 1; ++i) {
44 (*graph)[i+1]->dependsOn((*graph)[i].get());
45 }
46 }
47
48 /* Simple chain
49 * 0
50 * ^
51 * |
52 * 1
53 * ^
54 * |
55 * 2
56 * ^
57 * |
58 * 3
59 */
create_graph1(SkTArray<sk_sp<ToolUtils::TopoTestNode>> * graph)60 static void create_graph1(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph) {
61 create_simple_chain(graph, 4);
62 }
63
64 /* Simple Loop
65 * 2
66 * / .
67 * / \
68 * . \
69 * 0 ---> 1
70 */
create_graph2(SkTArray<sk_sp<ToolUtils::TopoTestNode>> * graph)71 static void create_graph2(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph) {
72 ToolUtils::TopoTestNode::AllocNodes(graph, 3);
73
74 (*graph)[0]->dependsOn((*graph)[1].get());
75 (*graph)[1]->dependsOn((*graph)[2].get());
76 (*graph)[2]->dependsOn((*graph)[0].get());
77 }
78
79 /* Double diamond
80 * 6
81 * . .
82 * / \
83 * 4 5
84 * . .
85 * \ /
86 * 3
87 * . .
88 * / \
89 * 1 2
90 * . .
91 * \ /
92 * 0
93 */
create_graph3(SkTArray<sk_sp<ToolUtils::TopoTestNode>> * graph)94 static void create_graph3(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph) {
95 ToolUtils::TopoTestNode::AllocNodes(graph, 7);
96
97 (*graph)[0]->dependsOn((*graph)[1].get());
98 (*graph)[0]->dependsOn((*graph)[2].get());
99 (*graph)[1]->dependsOn((*graph)[3].get());
100 (*graph)[2]->dependsOn((*graph)[3].get());
101
102 (*graph)[3]->dependsOn((*graph)[4].get());
103 (*graph)[3]->dependsOn((*graph)[5].get());
104 (*graph)[4]->dependsOn((*graph)[6].get());
105 (*graph)[5]->dependsOn((*graph)[6].get());
106 }
107
108 /* Two independent diamonds
109 * 3 7
110 * . . . .
111 * / \ / \
112 * 1 2 5 6
113 * . . . .
114 * \ / \ /
115 * 0 4
116 */
create_graph4(SkTArray<sk_sp<ToolUtils::TopoTestNode>> * graph)117 static void create_graph4(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph) {
118 ToolUtils::TopoTestNode::AllocNodes(graph, 8);
119
120 (*graph)[0]->dependsOn((*graph)[1].get());
121 (*graph)[0]->dependsOn((*graph)[2].get());
122 (*graph)[1]->dependsOn((*graph)[3].get());
123 (*graph)[2]->dependsOn((*graph)[3].get());
124
125 (*graph)[4]->dependsOn((*graph)[5].get());
126 (*graph)[4]->dependsOn((*graph)[6].get());
127 (*graph)[5]->dependsOn((*graph)[7].get());
128 (*graph)[6]->dependsOn((*graph)[7].get());
129 }
130
131 /* Two linked diamonds w/ two loops
132 * 5 6
133 * / . . \
134 * . \ / .
135 * 2 3 4
136 * \ . /
137 * . / \ .
138 * 0 1
139 */
create_graph5(SkTArray<sk_sp<ToolUtils::TopoTestNode>> * graph)140 static void create_graph5(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph) {
141 ToolUtils::TopoTestNode::AllocNodes(graph, 7);
142
143 (*graph)[0]->dependsOn((*graph)[3].get());
144 (*graph)[1]->dependsOn((*graph)[3].get());
145 (*graph)[2]->dependsOn((*graph)[0].get());
146 (*graph)[3]->dependsOn((*graph)[5].get());
147 (*graph)[3]->dependsOn((*graph)[6].get());
148 (*graph)[4]->dependsOn((*graph)[1].get());
149 (*graph)[5]->dependsOn((*graph)[2].get());
150 (*graph)[6]->dependsOn((*graph)[4].get());
151 }
152
153 /* Two disjoint loops
154 * 2 5
155 * / . / .
156 * / \ / \
157 * . \ . \
158 * 0 ---> 1 3 ---> 4
159 */
create_graph6(SkTArray<sk_sp<ToolUtils::TopoTestNode>> * graph)160 static void create_graph6(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph) {
161 ToolUtils::TopoTestNode::AllocNodes(graph, 6);
162
163 (*graph)[0]->dependsOn((*graph)[1].get());
164 (*graph)[1]->dependsOn((*graph)[2].get());
165 (*graph)[2]->dependsOn((*graph)[0].get());
166
167 (*graph)[3]->dependsOn((*graph)[4].get());
168 (*graph)[4]->dependsOn((*graph)[5].get());
169 (*graph)[5]->dependsOn((*graph)[3].get());
170 }
171
DEF_TEST(TopoSort,reporter)172 DEF_TEST(TopoSort, reporter) {
173 SkRandom rand;
174
175 struct {
176 CreateGraphPF fCreate;
177 bool fExpectedResult;
178 } tests[] = {
179 { create_graph0, true },
180 { create_graph1, true },
181 { create_graph2, false },
182 { create_graph3, true },
183 { create_graph4, true },
184 { create_graph5, false },
185 { create_graph6, false },
186 };
187
188 for (size_t i = 0; i < std::size(tests); ++i) {
189 SkTArray<sk_sp<ToolUtils::TopoTestNode>> graph;
190
191 (tests[i].fCreate)(&graph);
192
193 const int numNodes = graph.size();
194
195 ToolUtils::TopoTestNode::Shuffle(graph, &rand);
196
197 bool actualResult = GrTTopoSort<ToolUtils::TopoTestNode>(graph);
198 REPORTER_ASSERT(reporter, actualResult == tests[i].fExpectedResult);
199 REPORTER_ASSERT(reporter, numNodes == graph.size());
200
201 if (tests[i].fExpectedResult) {
202 for (const auto& node : graph) {
203 REPORTER_ASSERT(reporter, node->check());
204 }
205 } else {
206 // When the topological sort fails all the nodes should still appear in the result
207 // but their order can be somewhat arbitrary.
208 std::vector<bool> seen(numNodes, false);
209
210 for (const auto& node : graph) {
211 SkASSERT(node);
212 SkASSERT(!seen[node->id()]);
213 seen[node->id()] = true;
214 }
215 }
216
217 //SkDEBUGCODE(print(graph);)
218 }
219
220 // Some additional tests that do multiple partial sorts of graphs where we know nothing in an
221 // earlier partion depends on anything in a later partition.
222 for (int n = 2; n < 6; ++n) {
223 for (int split = 1; split < n; ++split) {
224 SkTArray<sk_sp<ToolUtils::TopoTestNode>> graph;
225 create_simple_chain(&graph, n);
226 SkSpan spanA = SkSpan(graph.begin(), split);
227 SkSpan spanB = SkSpan(graph.begin() + split, n - split);
228 ToolUtils::TopoTestNode::Shuffle(spanA, &rand);
229 ToolUtils::TopoTestNode::Shuffle(spanB, &rand);
230 bool result = GrTTopoSort(spanA);
231 if (!result) {
232 ERRORF(reporter, "Topo sort on partial chain failed.");
233 return;
234 }
235 // Nothing outside of the processed span should have been output.
236 for (const auto& node : spanB) {
237 REPORTER_ASSERT(reporter, !ToolUtils::TopoTestNode::WasOutput(node.get()));
238 }
239 result = GrTTopoSort(spanB, split);
240 if (!result) {
241 ERRORF(reporter, "Topo sort on partial chain failed.");
242 return;
243 }
244 for (const auto& node : graph) {
245 REPORTER_ASSERT(reporter, node->check());
246 }
247 }
248 }
249 }
250