blob: 849c20ac6fb5fe0ee40bf54f3924bb166dd867d5 [file] [log] [blame]
Robert Phillipsf5402002018-08-07 15:16:54 -04001/*
2 * Copyright 2018 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 "SkRefCnt.h"
9#include "SkTSort.h"
10#include "Test.h"
11
12#include "sk_tool_utils.h"
13
14// A node in the graph. This corresponds to an opList in the MDB world.
15class Node : public SkRefCnt {
16public:
17 char id() const { return fID; }
18 int indexInSort() const { SkASSERT(fIndexInSort >= 0); return fIndexInSort; }
19 bool visited() const { return fVisited; }
20
21#ifdef SK_DEBUG
22 void print() const {
23 SkDebugf("%d: id %c", fIndexInSort, fID);
24 if (fNodesIDependOn.count()) {
25 SkDebugf(" I depend on (%d): ", fNodesIDependOn.count());
26 for (Node* tmp : fNodesIDependOn) {
27 SkDebugf("%c, ", tmp->id());
28 }
29 }
30 if (fNodesThatDependOnMe.count()) {
31 SkDebugf(" (%d) depend on me: ", fNodesThatDependOnMe.count());
32 for (Node* tmp : fNodesThatDependOnMe) {
33 SkDebugf("%c, ", tmp->id());
34 }
35 }
36 SkDebugf("\n");
37 }
38#endif
39
40 void validate(skiatest::Reporter* reporter) const {
41 for (Node* dependedOn : fNodesIDependOn) {
42 REPORTER_ASSERT(reporter, dependedOn->indexInSort() < this->indexInSort());
43 }
44 for (Node* dependent : fNodesThatDependOnMe) {
45 REPORTER_ASSERT(reporter, this->indexInSort() < dependent->indexInSort());
46 }
47 REPORTER_ASSERT(reporter, !fVisited); // this flag should only be true w/in depEdges()
48 }
49
50 static bool CompareIndicesGT(Node* const& a, Node* const& b) {
51 return a->indexInSort() > b->indexInSort();
52 }
53
54 int numDependents() const { return fNodesThatDependOnMe.count(); }
55 Node* dependent(int index) const {
56 SkASSERT(0 <= index && index < fNodesThatDependOnMe.count());
57 return fNodesThatDependOnMe[index];
58 }
59
60private:
61 friend class Graph;
62
63 explicit Node(char id) : fID(id), fIndexInSort(-1), fVisited(false) {}
64
65 void setIndexInSort(int indexInSort) { fIndexInSort = indexInSort; }
66 void setVisited(bool visited) { fVisited = visited; }
67 void addDependency(Node* dependedOn) {
Mike Reedb5475792018-08-08 16:17:42 -040068 fNodesIDependOn.push_back(dependedOn);
Robert Phillipsf5402002018-08-07 15:16:54 -040069
70 dependedOn->addDependent(this);
71 }
72 void addDependent(Node* dependent) {
Mike Reedb5475792018-08-08 16:17:42 -040073 fNodesThatDependOnMe.push_back(dependent);
Robert Phillipsf5402002018-08-07 15:16:54 -040074 }
75
76 char fID;
77 SkTDArray<Node*> fNodesIDependOn; // These nodes must appear before this one in the sort
78 SkTDArray<Node*> fNodesThatDependOnMe; // These ones must appear after this one
79 int fIndexInSort;
80 bool fVisited; // only used in addEdges()
81};
82
83// The DAG driving the incremental topological sort. This corresponds to the opList DAG in
84// the MDB world.
85class Graph {
86public:
87 Graph(int numNodesToReserve, skiatest::Reporter* reporter)
88 : fNodes(numNodesToReserve)
89 , fReporter(reporter) {
90 }
91
92 Node* addNode(uint32_t id) {
93 this->validate();
94 sk_sp<Node> tmp(new Node(id));
95
96 fNodes.push_back(tmp); // The graph gets the creation ref
97 tmp->setIndexInSort(fNodes.count()-1);
98 this->validate();
99 return tmp.get();
100 }
101
102 // 'dependedOn' must appear before 'dependent' in the sort
103 void addEdge(Node* dependedOn, Node* dependent) {
104 // TODO: this would be faster if all the SkTDArray code was stripped out of
105 // addEdges but, when used in MDB sorting, this entry point will never be used.
106 SkTDArray<Node*> tmp(&dependedOn, 1);
107 this->addEdges(&tmp, dependent);
108 }
109
110 // All the nodes in 'dependedOn' must appear before 'dependent' in the sort.
111 // This is O(v + e + cost_of_sorting(b)) where:
112 // v: number of nodes
113 // e: number of edges
114 // b: number of new edges in 'dependedOn'
115 //
116 // The algorithm works by first finding the "affected region" that contains all the
117 // nodes whose position in the topological sort is invalidated by the addition of the new
118 // edges. It then traverses the affected region from left to right, temporarily removing
119 // invalid nodes from 'fNodes' and shifting valid nodes left to fill in the gaps. In this
120 // left to right traversal, when a node is shifted to the left the current set of invalid
121 // nodes is examined to see if any needed to be moved to the right of that node. If so,
122 // they are reintroduced to the 'fNodes' array but now in the appropriate position. The
123 // separation of the algorithm into search (the dfs method) and readjustment (the shift
124 // method) means that each node affected by the new edges is only ever moved once.
125 void addEdges(SkTDArray<Node*>* dependedOn, Node* dependent) {
126 this->validate();
127
128 // remove any of the new dependencies that are already satisfied
129 for (int i = 0; i < dependedOn->count(); ++i) {
130 if ((*dependedOn)[i]->indexInSort() < dependent->indexInSort()) {
131 dependent->addDependency((*dependedOn)[i]);
132 dependedOn->removeShuffle(i);
133 i--;
134 } else {
135 dependent->addDependency((*dependedOn)[i]);
136 }
137 }
138
139 if (dependedOn->isEmpty()) {
140 return;
141 }
142
143 // Sort the remaining dependencies into descending order based on their indices in the
144 // sort. This means that we will be proceeding from right to left in the sort when
145 // correcting the order.
146 // TODO: QSort is waaay overkill here!
147 SkTQSort<Node*>(dependedOn->begin(), dependedOn->end() - 1, Node::CompareIndicesGT);
148
149 // TODO: although this is the general algorithm, I think this can be simplified for our
150 // use case (i.e., the same dependent for all the new edges).
151
152 int lowerBound = fNodes.count(); // 'lowerBound' tracks the left of the affected region
153 for (int i = 0; i < dependedOn->count(); ++i) {
154 if ((*dependedOn)[i]->indexInSort() < lowerBound) {
155 this->shift(lowerBound);
156 }
157
158 if (!dependent->visited()) {
159 this->dfs(dependent, (*dependedOn)[i]->indexInSort());
160 }
161
162 lowerBound = SkTMin(dependent->indexInSort(), lowerBound);
163 }
164
165 this->shift(lowerBound);
166
167 this->validate();
168 }
169
170 // Get the list of node ids in the current sorted order
171 void getActual(SkString* actual) const {
172 this->validate();
173
174 for (int i = 0; i < fNodes.count(); ++i) {
175 (*actual) += fNodes[i]->id();
176 if (i < fNodes.count()-1) {
177 (*actual) += ',';
178 }
179 }
180 }
181
182#ifdef SK_DEBUG
183 void print() const {
184 SkDebugf("-------------------\n");
185 for (int i = 0; i < fNodes.count(); ++i) {
186 if (fNodes[i]) {
187 SkDebugf("%c ", fNodes[i]->id());
188 } else {
189 SkDebugf("0 ");
190 }
191 }
192 SkDebugf("\n");
193
194 for (int i = 0; i < fNodes.count(); ++i) {
195 if (fNodes[i]) {
196 fNodes[i]->print();
197 }
198 }
199
200 SkDebugf("Stack: ");
201 for (int i = 0; i < fStack.count(); ++i) {
202 SkDebugf("%c/%c ", fStack[i].fNode->id(), fStack[i].fDest->id());
203 }
204 SkDebugf("\n");
205 }
206#endif
207
208private:
209 void validate() const {
210 REPORTER_ASSERT(fReporter, fStack.empty());
211
212 for (int i = 0; i < fNodes.count(); ++i) {
213 REPORTER_ASSERT(fReporter, fNodes[i]->indexInSort() == i);
214
215 fNodes[i]->validate(fReporter);
216 }
217
218 // All the nodes in the Queue had better have been marked as visited
219 for (int i = 0; i < fStack.count(); ++i) {
220 SkASSERT(fStack[i].fNode->visited());
221 }
222 }
223
224 // Collect the nodes that need to be moved within the affected region. All the nodes found
225 // to be in violation of the topological constraints are placed in 'fStack'.
226 void dfs(Node* node, int upperBound) {
227 node->setVisited(true);
228
229 for (int i = 0; i < node->numDependents(); ++i) {
230 Node* dependent = node->dependent(i);
231
232 SkASSERT(dependent->indexInSort() != upperBound); // this would be a cycle
233
234 if (!dependent->visited() && dependent->indexInSort() < upperBound) {
235 this->dfs(dependent, upperBound);
236 }
237 }
238
239 fStack.push_back({ sk_ref_sp(node), fNodes[upperBound].get() });
240 }
241
242 // Move 'node' to the index-th slot of the sort. The index-th slot should not have a current
243 // occupant.
244 void moveNodeInSort(sk_sp<Node> node, int index) {
245 SkASSERT(!fNodes[index]);
246 fNodes[index] = node;
247 node->setIndexInSort(index);
248 }
249
250#ifdef SK_DEBUG
251 // Does 'fStack' have 'node'? That is, was 'node' discovered to be in violation of the
252 // topological constraints?
253 bool stackContains(Node* node) {
254 for (int i = 0; i < fStack.count(); ++i) {
255 if (node == fStack[i].fNode.get()) {
256 return true;
257 }
258 }
259 return false;
260 }
261#endif
262
263 // The 'shift' method iterates through the affected area from left to right moving Nodes that
264 // were found to be in violation of the topological order (i.e., in 'fStack') to their correct
265 // locations and shifting the non-violating nodes left, into the holes the violating nodes left
266 // behind.
267 void shift(int index) {
268 int numRemoved = 0;
269 while (!fStack.empty()) {
270 sk_sp<Node> node = fNodes[index];
271
272 if (node->visited()) {
273 // This node is in 'fStack' and was found to be in violation of the topological
274 // constraints. Remove it from 'fNodes' so non-violating nodes can be shifted
275 // left.
276 SkASSERT(this->stackContains(node.get()));
277 node->setVisited(false); // reset for future use
278 fNodes[index] = nullptr;
279 numRemoved++;
280 } else {
281 // This node was found to not be in violation of any topological constraints but
282 // must be moved left to fill in for those that were.
283 SkASSERT(!this->stackContains(node.get()));
284 SkASSERT(numRemoved); // should be moving left
285
286 this->moveNodeInSort(node, index - numRemoved);
287 fNodes[index] = nullptr;
288 }
289
290 while (!fStack.empty() && node.get() == fStack.back().fDest) {
291 // The left to right loop has finally encountered the destination for one or more
292 // of the nodes in 'fStack'. Place them to the right of 'node' in the sort. Note
293 // that because the violating nodes were already removed from 'fNodes' there
294 // should be enough empty space for them to be placed now.
295 numRemoved--;
296
297 this->moveNodeInSort(fStack.back().fNode, index - numRemoved);
298
299 fStack.pop_back();
300 }
301
302 index++;
303 }
304 }
305
306 SkTArray<sk_sp<Node>> fNodes;
307
308 struct StackInfo {
309 sk_sp<Node> fNode; // This gets a ref bc, in 'shift' it will be pulled out of 'fNodes'
310 Node* fDest;
311 };
312
313 SkTArray<StackInfo> fStack; // only used in addEdges()
314
315 skiatest::Reporter* fReporter;
316};
317
318// This test adds a single invalidating edge.
319static void test_1(skiatest::Reporter* reporter) {
320 Graph g(10, reporter);
321
322 Node* nodeQ = g.addNode('q');
323 Node* nodeY = g.addNode('y');
324 Node* nodeA = g.addNode('a');
325 Node* nodeZ = g.addNode('z');
326 Node* nodeB = g.addNode('b');
327 /*Node* nodeC =*/ g.addNode('c');
328 Node* nodeW = g.addNode('w');
329 Node* nodeD = g.addNode('d');
330 Node* nodeX = g.addNode('x');
331 Node* nodeR = g.addNode('r');
332
333 // All these edge are non-invalidating
334 g.addEdge(nodeD, nodeR);
335 g.addEdge(nodeZ, nodeW);
336 g.addEdge(nodeA, nodeB);
337 g.addEdge(nodeY, nodeZ);
338 g.addEdge(nodeQ, nodeA);
339
340 {
341 const SkString kExpectedInitialState("q,y,a,z,b,c,w,d,x,r");
342 SkString actualInitialState;
343 g.getActual(&actualInitialState);
344 REPORTER_ASSERT(reporter, kExpectedInitialState == actualInitialState);
345 }
346
347 // Add the invalidating edge
348 g.addEdge(nodeX, nodeY);
349
350 {
351 const SkString kExpectedFinalState("q,a,b,c,d,x,y,z,w,r");
352 SkString actualFinalState;
353 g.getActual(&actualFinalState);
354 REPORTER_ASSERT(reporter, kExpectedFinalState == actualFinalState);
355 }
356}
357
358// This test adds two invalidating edge sequentially
359static void test_2(skiatest::Reporter* reporter) {
360 Graph g(10, reporter);
361
362 Node* nodeY = g.addNode('y');
363 /*Node* nodeA =*/ g.addNode('a');
364 Node* nodeW = g.addNode('w');
365 /*Node* nodeB =*/ g.addNode('b');
366 Node* nodeZ = g.addNode('z');
367 Node* nodeU = g.addNode('u');
368 /*Node* nodeC =*/ g.addNode('c');
369 Node* nodeX = g.addNode('x');
370 /*Node* nodeD =*/ g.addNode('d');
371 Node* nodeV = g.addNode('v');
372
373 // All these edge are non-invalidating
374 g.addEdge(nodeU, nodeX);
375 g.addEdge(nodeW, nodeU);
376 g.addEdge(nodeW, nodeZ);
377 g.addEdge(nodeY, nodeZ);
378
379 {
380 const SkString kExpectedInitialState("y,a,w,b,z,u,c,x,d,v");
381 SkString actualInitialState;
382 g.getActual(&actualInitialState);
383 REPORTER_ASSERT(reporter, kExpectedInitialState == actualInitialState);
384 }
385
386 // Add the first invalidating edge
387 g.addEdge(nodeX, nodeY);
388
389 {
390 const SkString kExpectedFirstState("a,w,b,u,c,x,y,z,d,v");
391 SkString actualFirstState;
392 g.getActual(&actualFirstState);
393 REPORTER_ASSERT(reporter, kExpectedFirstState == actualFirstState);
394 }
395
396 // Add the second invalidating edge
397 g.addEdge(nodeV, nodeW);
398
399 {
400 const SkString kExpectedSecondState("a,b,c,d,v,w,u,x,y,z");
401 SkString actualSecondState;
402 g.getActual(&actualSecondState);
403 REPORTER_ASSERT(reporter, kExpectedSecondState == actualSecondState);
404 }
405}
406
407static void test_diamond(skiatest::Reporter* reporter) {
408 Graph g(4, reporter);
409
410 /* Create the graph (the '.' is the pointy side of the arrow):
411 * b
412 * . \
413 * / .
414 * a d
415 * \ .
416 * . /
417 * c
418 * Possible topological orders are [a,c,b,d] and [a,b,c,d].
419 */
420
421 Node* nodeD = g.addNode('d');
422 Node* nodeC = g.addNode('c');
423 Node* nodeB = g.addNode('b');
424
425 {
426 SkTDArray<Node*> dependedOn;
Mike Reedb5475792018-08-08 16:17:42 -0400427 dependedOn.push_back(nodeB);
428 dependedOn.push_back(nodeC);
Robert Phillipsf5402002018-08-07 15:16:54 -0400429
430 g.addEdges(&dependedOn, nodeD); // nodes B and C must come before node D
431 }
432
433 Node* nodeA = g.addNode('a');
434 g.addEdge(nodeA, nodeB); // node A must come before node B
435 g.addEdge(nodeA, nodeC); // node A must come before node C
436
437 const SkString kExpected0("a,c,b,d");
438 const SkString kExpected1("a,b,c,d");
439 SkString actual;
440 g.getActual(&actual);
441
442 REPORTER_ASSERT(reporter, kExpected0 == actual || kExpected1 == actual);
443}
444
445static void test_lopsided_binary_tree(skiatest::Reporter* reporter) {
446 Graph g(7, reporter);
447
448 /* Create the graph (the '.' is the pointy side of the arrow):
449 * a
450 * / \
451 * . .
452 * b c
453 * / \
454 * . .
455 * d e
456 * / \
457 * . .
458 * f g
459 *
460 * Possible topological order is: [a,b,c,d,e,f,g].
461 */
462
463 Node* nodeG = g.addNode('g');
464 Node* nodeF = g.addNode('f');
465 Node* nodeE = g.addNode('e');
466 Node* nodeD = g.addNode('d');
467 Node* nodeC = g.addNode('c');
468 Node* nodeB = g.addNode('b');
469 Node* nodeA = g.addNode('a');
470
471 g.addEdge(nodeE, nodeG);
472 g.addEdge(nodeE, nodeF);
473 g.addEdge(nodeC, nodeE);
474 g.addEdge(nodeC, nodeD);
475 g.addEdge(nodeA, nodeC);
476 g.addEdge(nodeA, nodeB);
477
478 const SkString kExpected("a,b,c,d,e,f,g");
479 SkString actual;
480 g.getActual(&actual);
481
482 REPORTER_ASSERT(reporter, kExpected == actual);
483}
484
485DEF_TEST(IncrTopoSort, reporter) {
486 test_1(reporter);
487 test_2(reporter);
488 test_diamond(reporter);
489 test_lopsided_binary_tree(reporter);
490}