Add SkTTopoSort

BUG=skia:4094

Review URL: https://codereview.chromium.org/1414503003

5 files changed, 426 insertions, 0 deletions

diff --git a/bench/TopoSortBench.cpp b/bench/TopoSortBench.cpp
new file mode 100644
index 0000000000..3fa1c0ff97
--- /dev/null
+++ b/bench/TopoSortBench.cpp
@@ -0,0 +1,79 @@
+/*
+ * Copyright 2015 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "Benchmark.h"
+#include "SkRandom.h"
+#include "SkString.h"
+#include "SkTTopoSort.h"
+
+#include "sk_tool_utils.h"
+
+class TopoSortBench : public Benchmark {
+public:
+    TopoSortBench() { }
+
+    ~TopoSortBench() override {
+        sk_tool_utils::TopoTestNode::DeallocNodes(&fGraph);
+    }
+
+    bool isSuitableFor(Backend backend) override {
+        return kNonRendering_Backend == backend;
+    }
+
+protected:
+    const char* onGetName() override {
+        return "sort_topo_rand";
+    }
+
+    // Delayed initialization only done if onDraw will be called.
+    void onDelayedSetup() override {
+        sk_tool_utils::TopoTestNode::AllocNodes(&fGraph, kNumElements);
+
+        for (int i = kNumElements-1; i > 0; --i) {
+            int numEdges = fRand.nextU() % (kMaxEdges+1);
+
+            for (int j = 0; j < numEdges; ++j) {
+                int dep = fRand.nextU() % i;
+
+                fGraph[i]->dependsOn(fGraph[dep]);
+            }
+        }
+    }
+
+    void onDraw(int loops, SkCanvas*) override {
+        for (int i = 0; i < loops; ++i) {
+            for (int j = 0; j < fGraph.count(); ++j) {
+                fGraph[j]->reset();
+            }
+
+            sk_tool_utils::TopoTestNode::Shuffle(&fGraph, &fRand);
+
+            SkDEBUGCODE(bool actualResult =) SkTTopoSort<sk_tool_utils::TopoTestNode>(&fGraph);
+            SkASSERT(actualResult);
+
+#ifdef SK_DEBUG
+            for (int j = 0; j < fGraph.count(); ++j) {
+                SkASSERT(fGraph[j]->check());
+            }
+#endif
+        }
+    }
+
+private:
+    static const int kNumElements = 1000;
+    static const int kMaxEdges = 5;
+
+    SkTDArray<sk_tool_utils::TopoTestNode*> fGraph;
+    SkRandom fRand;
+
+    typedef Benchmark INHERITED;
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+DEF_BENCH( return new TopoSortBench(); )
+
diff --git a/gyp/core.gypi b/gyp/core.gypi
index 089a8c02db..c71ea317c7 100644
--- a/gyp/core.gypi
+++ b/gyp/core.gypi
@@ -275,6 +275,7 @@
         '<(skia_src_path)/core/SkTraceEventCommon.h',
         '<(skia_src_path)/core/SkTSearch.cpp',
         '<(skia_src_path)/core/SkTSort.h',
+        '<(skia_src_path)/core/SkTTopoSort.h',
         '<(skia_src_path)/core/SkTypeface.cpp',
         '<(skia_src_path)/core/SkTypefaceCache.cpp',
         '<(skia_src_path)/core/SkTypefaceCache.h',
diff --git a/src/core/SkTTopoSort.h b/src/core/SkTTopoSort.h
new file mode 100644
index 0000000000..35b85eeb81
--- /dev/null
+++ b/src/core/SkTTopoSort.h
@@ -0,0 +1,112 @@
+/*
+ * Copyright 2015 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkTTopoSort_DEFINED
+#define SkTTopoSort_DEFINED
+
+#include "SkTDArray.h"
+
+#ifdef SK_DEBUG
+template <typename T, typename Traits = T>
+void SkTTopoSort_CheckAllUnmarked(const SkTDArray<T*>& graph) {
+    for (int i = 0; i < graph.count(); ++i) {
+        SkASSERT(!Traits::IsTempMarked(graph[i]));
+        SkASSERT(!Traits::WasOutput(graph[i]));
+    }
+}
+
+template <typename T, typename Traits = T>
+void SkTTopoSort_CleanExit(const SkTDArray<T*>& graph) {
+    for (int i = 0; i < graph.count(); ++i) {
+        SkASSERT(!Traits::IsTempMarked(graph[i]));
+        SkASSERT(Traits::WasOutput(graph[i]));
+    }
+}
+#endif
+
+// Recursively visit a node and all the other nodes it depends on.
+// Return false if there is a loop.
+template <typename T, typename Traits = T>
+bool SkTTopoSort_Visit(T* node, SkTDArray<T*>* result) {
+    if (Traits::IsTempMarked(node)) {
+        // There is a loop.
+        return false;
+    }
+
+    // If the node under consideration has been already been output it means it
+    // (and all the nodes it depends on) are already in 'result'.
+    if (!Traits::WasOutput(node)) {
+        // This node hasn't been output yet. Recursively assess all the
+        // nodes it depends on outputing them first.
+        Traits::SetTempMark(node);
+        for (int i = 0; i < Traits::NumDependencies(node); ++i) {
+            if (!SkTTopoSort_Visit<T, Traits>(Traits::Dependency(node, i), result)) {
+                return false;
+            }
+        }
+        Traits::Output(node, result->count()); // mark this node as output
+        Traits::ResetTempMark(node);
+
+        *result->append() = node;
+    }
+
+    return true;
+}
+
+// Topologically sort the nodes in 'graph'. For this sort, when node 'i' depends
+// on node 'j' it means node 'j' must appear in the result before node 'i'.
+// A false return value means there was a loop and the contents of 'graph' will
+// be in some arbitrary state.
+//
+// Traits requires:
+//   static void Output(T* t, int index) { ... }  // 'index' is 't's position in the result
+//   static bool WasOutput(const T* t) { ... }
+//
+//   static void SetTempMark(T* t) { ... }        // transiently used during toposort
+//   static void ResetTempMark(T* t) { ... }
+//   static bool IsTempMarked(const T* t) { ... }
+//
+//   static int NumDependencies(const T* t) { ... } // 't' will be output after all the other -
+//   static T* Dependency(T* t, int index) { ... }  // nodes on which it depends
+// We'll look on T for these by default, or you can pass a custom Traits type.
+//
+// TODO: potentially add a version that takes a seed node and just outputs that
+// node and all the nodes on which it depends. This could be used to partially
+// flush a drawTarget DAG.
+template <typename T, typename Traits = T>
+bool SkTTopoSort(SkTDArray<T*>* graph) {
+    SkTDArray<T*> result;
+
+#ifdef SK_DEBUG
+    SkTTopoSort_CheckAllUnmarked<T, Traits>(*graph);
+#endif
+
+    result.setReserve(graph->count());
+
+    for (int i = 0; i < graph->count(); ++i) {
+        if (Traits::WasOutput((*graph)[i])) {
+            // This node was depended on by some earlier node and has already
+            // been output
+            continue;
+        }
+
+        // Output this node after all the nodes it depends on have been output.
+        if (!SkTTopoSort_Visit<T, Traits>((*graph)[i], &result)) {
+            return false;
+        }
+    }
+
+    SkASSERT(graph->count() == result.count());
+    graph->swap(result);
+
+#ifdef SK_DEBUG
+    SkTTopoSort_CleanExit<T, Traits>(*graph);
+#endif
+    return true;
+}
+
+#endif
diff --git a/tests/TopoSortTest.cpp b/tests/TopoSortTest.cpp
new file mode 100644
index 0000000000..358cd8dbad
--- /dev/null
+++ b/tests/TopoSortTest.cpp
@@ -0,0 +1,142 @@
+/*
+ * Copyright 2015 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkRandom.h"
+#include "SkTTopoSort.h"
+#include "Test.h"
+
+#include "sk_tool_utils.h"
+
+typedef void (*CreateGraphPF)(SkTDArray<sk_tool_utils::TopoTestNode*>* graph);
+
+/* Simple diamond
+ *       3
+ *     /   \
+ *    1     2
+ *     \   /
+ *       0
+ */
+static void create_graph0(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
+    sk_tool_utils::TopoTestNode::AllocNodes(graph, 4);
+
+    (*graph)[0]->dependsOn((*graph)[1]);
+    (*graph)[0]->dependsOn((*graph)[2]);
+    (*graph)[1]->dependsOn((*graph)[3]);
+    (*graph)[2]->dependsOn((*graph)[3]);
+}
+
+/* Simple chain
+ *     3
+ *     |
+ *     2
+ *     |
+ *     1
+ *     |
+ *     0
+ */
+static void create_graph1(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
+    sk_tool_utils::TopoTestNode::AllocNodes(graph, 4);
+
+    (*graph)[0]->dependsOn((*graph)[1]);
+    (*graph)[1]->dependsOn((*graph)[2]);
+    (*graph)[2]->dependsOn((*graph)[3]);
+}
+
+/* Loop
+ *       2
+ *     /   \
+ *    0 --- 1
+ */
+static void create_graph2(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
+    sk_tool_utils::TopoTestNode::AllocNodes(graph, 3);
+
+    (*graph)[0]->dependsOn((*graph)[1]);
+    (*graph)[1]->dependsOn((*graph)[2]);
+    (*graph)[2]->dependsOn((*graph)[0]);
+}
+
+/* Double diamond
+ *       6
+ *     /   \
+ *    4     5
+ *     \   /
+ *       3
+ *     /   \
+ *    1     2
+ *     \   /
+ *       0
+ */
+static void create_graph3(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
+    sk_tool_utils::TopoTestNode::AllocNodes(graph, 7);
+
+    (*graph)[0]->dependsOn((*graph)[1]);
+    (*graph)[0]->dependsOn((*graph)[2]);
+    (*graph)[1]->dependsOn((*graph)[3]);
+    (*graph)[2]->dependsOn((*graph)[3]);
+
+    (*graph)[3]->dependsOn((*graph)[4]);
+    (*graph)[3]->dependsOn((*graph)[5]);
+    (*graph)[4]->dependsOn((*graph)[6]);
+    (*graph)[5]->dependsOn((*graph)[6]);
+}
+
+/* Two independent diamonds
+ *       3           7
+ *     /   \       /   \
+ *    1     2     5     6
+ *     \   /       \   /
+ *       0           4
+ */
+static void create_graph4(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
+    sk_tool_utils::TopoTestNode::AllocNodes(graph, 8);
+
+    (*graph)[0]->dependsOn((*graph)[1]);
+    (*graph)[0]->dependsOn((*graph)[2]);
+    (*graph)[1]->dependsOn((*graph)[3]);
+    (*graph)[2]->dependsOn((*graph)[3]);
+
+    (*graph)[4]->dependsOn((*graph)[5]);
+    (*graph)[4]->dependsOn((*graph)[6]);
+    (*graph)[5]->dependsOn((*graph)[7]);
+    (*graph)[6]->dependsOn((*graph)[7]);
+}
+
+DEF_TEST(TopoSort, reporter) {
+    SkRandom rand;
+
+    struct {
+        CreateGraphPF fCreate;
+        bool          fExpectedResult;
+    } tests[] = {
+        { create_graph0, true  },
+        { create_graph1, true  },
+        { create_graph2, false },
+        { create_graph3, true  },
+        { create_graph4, true  },
+    };
+
+    for (size_t i = 0; i < SK_ARRAY_COUNT(tests); ++i) {
+        SkTDArray<sk_tool_utils::TopoTestNode*> graph;
+        
+        (tests[i].fCreate)(&graph);
+
+        sk_tool_utils::TopoTestNode::Shuffle(&graph, &rand);
+
+        bool actualResult = SkTTopoSort<sk_tool_utils::TopoTestNode>(&graph);
+        REPORTER_ASSERT(reporter, actualResult == tests[i].fExpectedResult);
+
+        if (tests[i].fExpectedResult) {
+            for (int j = 0; j < graph.count(); ++j) {
+                REPORTER_ASSERT(reporter, graph[j]->check());
+            }
+        }
+
+        //SkDEBUGCODE(print(graph);)
+        sk_tool_utils::TopoTestNode::DeallocNodes(&graph);
+    }
+}
+
diff --git a/tools/sk_tool_utils.h b/tools/sk_tool_utils.h
index 052bade6a7..67fd869a87 100644
--- a/tools/sk_tool_utils.h
+++ b/tools/sk_tool_utils.h
@@ -12,6 +12,8 @@
 #include "SkImageEncoder.h"
 #include "SkImageInfo.h"
 #include "SkPixelSerializer.h"
+#include "SkRandom.h"
+#include "SkTDArray.h"
 #include "SkTypeface.h"
 
 class SkBitmap;
@@ -140,6 +142,96 @@ namespace sk_tool_utils {
     // so it is slow!
     SkBitmap slow_blur(const SkBitmap& src, float sigma);
 
+    // A helper object to test the topological sorting code (TopoSortBench.cpp & TopoSortTest.cpp)
+    class TopoTestNode {
+    public:
+        TopoTestNode(int id) : fID(id), fOutputPos(-1), fTempMark(false) { }
+
+        void dependsOn(TopoTestNode* src) {
+            *fDependencies.append() = src;
+        }
+
+        int id() const { return fID; }
+        void reset() { fOutputPos = -1; }
+
+        int outputPos() const { return fOutputPos; }
+
+        // check that the topological sort is valid for this node
+        bool check() {
+            if (-1 == fOutputPos) {
+                return false;
+            }
+
+            for (int i = 0; i < fDependencies.count(); ++i) {
+                if (-1 == fDependencies[i]->outputPos()) {
+                    return false;
+                }
+                // This node should've been output after all the nodes on which it depends
+                if (fOutputPos < fDependencies[i]->outputPos()) {
+                    return false;
+                }
+            }
+
+            return true;
+        }
+
+        // The following 7 methods are needed by the topological sort
+        static void SetTempMark(TopoTestNode* node) { node->fTempMark = true; }
+        static void ResetTempMark(TopoTestNode* node) { node->fTempMark = false; }
+        static bool IsTempMarked(TopoTestNode* node) { return node->fTempMark; }
+        static void Output(TopoTestNode* node, int outputPos) { 
+            SkASSERT(-1 != outputPos);
+            node->fOutputPos = outputPos; 
+        }
+        static bool WasOutput(TopoTestNode* node) { return (-1 != node->fOutputPos); }
+        static int NumDependencies(TopoTestNode* node) { return node->fDependencies.count(); }
+        static TopoTestNode* Dependency(TopoTestNode* node, int index) { 
+            return node->fDependencies[index];
+        }
+
+        // Helper functions for TopoSortBench & TopoSortTest
+        static void AllocNodes(SkTDArray<TopoTestNode*>* graph, int num) {
+            graph->setReserve(num);
+
+            for (int i = 0; i < num; ++i) {
+                *graph->append() = new TopoTestNode(i);
+            }
+        }
+
+        static void DeallocNodes(SkTDArray<TopoTestNode*>* graph) {
+            for (int i = 0; i < graph->count(); ++i) {
+                delete (*graph)[i];
+            }
+        }
+
+        #ifdef SK_DEBUG
+        static void Print(const SkTDArray<TopoTestNode*>& graph) {
+            for (int i = 0; i < graph.count(); ++i) {
+                SkDebugf("%d, ", graph[i]->id());
+            }
+            SkDebugf("\n");
+        }
+        #endif
+
+        // randomize the array
+        static void Shuffle(SkTDArray<TopoTestNode*>* graph, SkRandom* rand) {
+            for (int i = graph->count()-1; i > 0; --i) {
+                int swap = rand->nextU() % (i+1);
+
+                TopoTestNode* tmp = (*graph)[i];
+                (*graph)[i] = (*graph)[swap];
+                (*graph)[swap] = tmp;
+            }
+        }
+
+    private:
+        int  fID;
+        int  fOutputPos;
+        bool fTempMark;
+
+        SkTDArray<TopoTestNode*> fDependencies;
+    };
+
 }  // namespace sk_tool_utils
 
 #endif  // sk_tool_utils_DEFINED