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/utils/SkRandom.h"
9 #include "src/gpu/GrTTopoSort.h"
10 #include "tests/Test.h"
11
12 #include "tools/ToolUtils.h"
13
14 typedef void (*CreateGraphPF)(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph);
15
16 /* Simple diamond
17 * 3
18 * . .
19 * / \
20 * 1 2
21 * . .
22 * \ /
23 * 0
24 */
create_graph0(SkTArray<sk_sp<ToolUtils::TopoTestNode>> * graph)25 static void create_graph0(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph) {
26 ToolUtils::TopoTestNode::AllocNodes(graph, 4);
27
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());
32 }
33
34 /* Simple chain
35 * 3
36 * ^
37 * |
38 * 2
39 * ^
40 * |
41 * 1
42 * ^
43 * |
44 * 0
45 */
create_graph1(SkTArray<sk_sp<ToolUtils::TopoTestNode>> * graph)46 static void create_graph1(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph) {
47 ToolUtils::TopoTestNode::AllocNodes(graph, 4);
48
49 (*graph)[0]->dependsOn((*graph)[1].get());
50 (*graph)[1]->dependsOn((*graph)[2].get());
51 (*graph)[2]->dependsOn((*graph)[3].get());
52 }
53
54 /* Simple Loop
55 * 2
56 * / .
57 * / \
58 * . \
59 * 0 ---> 1
60 */
create_graph2(SkTArray<sk_sp<ToolUtils::TopoTestNode>> * graph)61 static void create_graph2(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph) {
62 ToolUtils::TopoTestNode::AllocNodes(graph, 3);
63
64 (*graph)[0]->dependsOn((*graph)[1].get());
65 (*graph)[1]->dependsOn((*graph)[2].get());
66 (*graph)[2]->dependsOn((*graph)[0].get());
67 }
68
69 /* Double diamond
70 * 6
71 * . .
72 * / \
73 * 4 5
74 * . .
75 * \ /
76 * 3
77 * . .
78 * / \
79 * 1 2
80 * . .
81 * \ /
82 * 0
83 */
create_graph3(SkTArray<sk_sp<ToolUtils::TopoTestNode>> * graph)84 static void create_graph3(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph) {
85 ToolUtils::TopoTestNode::AllocNodes(graph, 7);
86
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());
91
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());
96 }
97
98 /* Two independent diamonds
99 * 3 7
100 * . . . .
101 * / \ / \
102 * 1 2 5 6
103 * . . . .
104 * \ / \ /
105 * 0 4
106 */
create_graph4(SkTArray<sk_sp<ToolUtils::TopoTestNode>> * graph)107 static void create_graph4(SkTArray<sk_sp<ToolUtils::TopoTestNode>>* graph) {
108 ToolUtils::TopoTestNode::AllocNodes(graph, 8);
109
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());
114
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());
119 }
120
121 /* Two linked diamonds w/ two loops
122 * 5 6
123 * / . . \
124 * . \ / .
125 * 2 3 4
126 * \ . /
127 * . / \ .
128 * 0 1
129 */
create_graph5(SkTArray<sk_sp<ToolUtils::TopoTestNode>> * graph)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 */
create_graph6(SkTArray<sk_sp<ToolUtils::TopoTestNode>> * graph)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
DEF_TEST(TopoSort,reporter)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 },
174 { create_graph5, false },
175 { create_graph6, false },
176 };
177
178 for (size_t i = 0; i < SK_ARRAY_COUNT(tests); ++i) {
179 SkTArray<sk_sp<ToolUtils::TopoTestNode>> graph;
180
181 (tests[i].fCreate)(&graph);
182
183 const int numNodes = graph.count();
184
185 ToolUtils::TopoTestNode::Shuffle(&graph, &rand);
186
187 bool actualResult = GrTTopoSort<ToolUtils::TopoTestNode>(&graph);
188 REPORTER_ASSERT(reporter, actualResult == tests[i].fExpectedResult);
189 REPORTER_ASSERT(reporter, numNodes == graph.count());
190
191 if (tests[i].fExpectedResult) {
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;
204 }
205 }
206
207 //SkDEBUGCODE(print(graph);)
208 }
209 }
210