IncrTopoSortTest.cpp 16 KB

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