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