Robert Phillips | f540200 | 2018-08-07 15:16:54 -0400 | [diff] [blame] | 1 | /* |
| 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. |
| 15 | class Node : public SkRefCnt { |
| 16 | public: |
| 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 | |
| 60 | private: |
| 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 Reed | b547579 | 2018-08-08 16:17:42 -0400 | [diff] [blame^] | 68 | fNodesIDependOn.push_back(dependedOn); |
Robert Phillips | f540200 | 2018-08-07 15:16:54 -0400 | [diff] [blame] | 69 | |
| 70 | dependedOn->addDependent(this); |
| 71 | } |
| 72 | void addDependent(Node* dependent) { |
Mike Reed | b547579 | 2018-08-08 16:17:42 -0400 | [diff] [blame^] | 73 | fNodesThatDependOnMe.push_back(dependent); |
Robert Phillips | f540200 | 2018-08-07 15:16:54 -0400 | [diff] [blame] | 74 | } |
| 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. |
| 85 | class Graph { |
| 86 | public: |
| 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 | |
| 208 | private: |
| 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. |
| 319 | static 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 |
| 359 | static 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 | |
| 407 | static 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 Reed | b547579 | 2018-08-08 16:17:42 -0400 | [diff] [blame^] | 427 | dependedOn.push_back(nodeB); |
| 428 | dependedOn.push_back(nodeC); |
Robert Phillips | f540200 | 2018-08-07 15:16:54 -0400 | [diff] [blame] | 429 | |
| 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 | |
| 445 | static 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 | |
| 485 | DEF_TEST(IncrTopoSort, reporter) { |
| 486 | test_1(reporter); |
| 487 | test_2(reporter); |
| 488 | test_diamond(reporter); |
| 489 | test_lopsided_binary_tree(reporter); |
| 490 | } |