TopoSortTest.cpp File Reference

#include "include/core/SkRefCnt.h"
#include "include/core/SkSpan.h"
#include "include/core/SkTypes.h"
#include "include/private/base/SkTArray.h"
#include "src/base/SkRandom.h"
#include "src/gpu/ganesh/GrTTopoSort.h"
#include "tests/Test.h"
#include "tools/ToolUtils.h"
#include <cstddef>
#include <vector>

Go to the source code of this file.

Typedefs
typedef void(*	CreateGraphPF) (TArray< sk_sp< ToolUtils::TopoTestNode > > *graph)

Functions
static void	create_graph0 (TArray< sk_sp< ToolUtils::TopoTestNode > > *graph)
static void	create_simple_chain (TArray< sk_sp< ToolUtils::TopoTestNode > > *graph, int n)
static void	create_graph1 (TArray< sk_sp< ToolUtils::TopoTestNode > > *graph)
static void	create_graph2 (TArray< sk_sp< ToolUtils::TopoTestNode > > *graph)
static void	create_graph3 (TArray< sk_sp< ToolUtils::TopoTestNode > > *graph)
static void	create_graph4 (TArray< sk_sp< ToolUtils::TopoTestNode > > *graph)
static void	create_graph5 (TArray< sk_sp< ToolUtils::TopoTestNode > > *graph)
static void	create_graph6 (TArray< sk_sp< ToolUtils::TopoTestNode > > *graph)
	DEF_TEST (TopoSort, reporter)

Typedef Documentation

CreateGraphPF

typedef void(* CreateGraphPF) (TArray< sk_sp< ToolUtils::TopoTestNode > > *graph)

Definition at line 22 of file TopoSortTest.cpp.

Function Documentation

create_graph0()

static void create_graph0 ( TArray< sk_sp< ToolUtils::TopoTestNode > > *  graph )

static

Definition at line 33 of file TopoSortTest.cpp.

                                                                       {
    ToolUtils::TopoTestNode::AllocNodes(graph, 4);
 
    (*graph)[0]->dependsOn((*graph)[1].get());
    (*graph)[0]->dependsOn((*graph)[2].get());
    (*graph)[1]->dependsOn((*graph)[3].get());
    (*graph)[2]->dependsOn((*graph)[3].get());
}

create_graph1()

static void create_graph1 ( TArray< sk_sp< ToolUtils::TopoTestNode > > *  graph )

static

Definition at line 62 of file TopoSortTest.cpp.

                                                                       {
    create_simple_chain(graph, 4);
}

create_graph2()

static void create_graph2 ( TArray< sk_sp< ToolUtils::TopoTestNode > > *  graph )

static

Definition at line 73 of file TopoSortTest.cpp.

                                                                       {
    ToolUtils::TopoTestNode::AllocNodes(graph, 3);
 
    (*graph)[0]->dependsOn((*graph)[1].get());
    (*graph)[1]->dependsOn((*graph)[2].get());
    (*graph)[2]->dependsOn((*graph)[0].get());
}

create_graph3()

static void create_graph3 ( TArray< sk_sp< ToolUtils::TopoTestNode > > *  graph )

static

Definition at line 96 of file TopoSortTest.cpp.

                                                                       {
    ToolUtils::TopoTestNode::AllocNodes(graph, 7);
 
    (*graph)[0]->dependsOn((*graph)[1].get());
    (*graph)[0]->dependsOn((*graph)[2].get());
    (*graph)[1]->dependsOn((*graph)[3].get());
    (*graph)[2]->dependsOn((*graph)[3].get());
 
    (*graph)[3]->dependsOn((*graph)[4].get());
    (*graph)[3]->dependsOn((*graph)[5].get());
    (*graph)[4]->dependsOn((*graph)[6].get());
    (*graph)[5]->dependsOn((*graph)[6].get());
}

create_graph4()

static void create_graph4 ( TArray< sk_sp< ToolUtils::TopoTestNode > > *  graph )

static

Definition at line 119 of file TopoSortTest.cpp.

                                                                       {
    ToolUtils::TopoTestNode::AllocNodes(graph, 8);
 
    (*graph)[0]->dependsOn((*graph)[1].get());
    (*graph)[0]->dependsOn((*graph)[2].get());
    (*graph)[1]->dependsOn((*graph)[3].get());
    (*graph)[2]->dependsOn((*graph)[3].get());
 
    (*graph)[4]->dependsOn((*graph)[5].get());
    (*graph)[4]->dependsOn((*graph)[6].get());
    (*graph)[5]->dependsOn((*graph)[7].get());
    (*graph)[6]->dependsOn((*graph)[7].get());
}

create_graph5()

static void create_graph5 ( TArray< sk_sp< ToolUtils::TopoTestNode > > *  graph )

static

Definition at line 142 of file TopoSortTest.cpp.

                                                                       {
    ToolUtils::TopoTestNode::AllocNodes(graph, 7);
 
    (*graph)[0]->dependsOn((*graph)[3].get());
    (*graph)[1]->dependsOn((*graph)[3].get());
    (*graph)[2]->dependsOn((*graph)[0].get());
    (*graph)[3]->dependsOn((*graph)[5].get());
    (*graph)[3]->dependsOn((*graph)[6].get());
    (*graph)[4]->dependsOn((*graph)[1].get());
    (*graph)[5]->dependsOn((*graph)[2].get());
    (*graph)[6]->dependsOn((*graph)[4].get());
}

create_graph6()

static void create_graph6 ( TArray< sk_sp< ToolUtils::TopoTestNode > > *  graph )

static

Definition at line 162 of file TopoSortTest.cpp.

                                                                       {
    ToolUtils::TopoTestNode::AllocNodes(graph, 6);
 
    (*graph)[0]->dependsOn((*graph)[1].get());
    (*graph)[1]->dependsOn((*graph)[2].get());
    (*graph)[2]->dependsOn((*graph)[0].get());
 
    (*graph)[3]->dependsOn((*graph)[4].get());
    (*graph)[4]->dependsOn((*graph)[5].get());
    (*graph)[5]->dependsOn((*graph)[3].get());
}

create_simple_chain()

static void create_simple_chain ( TArray< sk_sp< ToolUtils::TopoTestNode > > *  graph, int  n  )

static

Definition at line 42 of file TopoSortTest.cpp.

                                                                                    {
    ToolUtils::TopoTestNode::AllocNodes(graph, n);
 
    for (int i = 0; i < n - 1; ++i) {
        (*graph)[i+1]->dependsOn((*graph)[i].get());
    }
}

DEF_TEST()

DEF_TEST	(	TopoSort	,
		reporter
	)

Definition at line 174 of file TopoSortTest.cpp.

                             {
    SkRandom rand;
 
    struct {
        CreateGraphPF fCreate;
        bool          fExpectedResult;
    } tests[] = {
        { create_graph0, true  },
        { create_graph1, true  },
        { create_graph2, false },
        { create_graph3, true  },
        { create_graph4, true  },
        { create_graph5, false },
        { create_graph6, false },
    };
 
    for (size_t i = 0; i < std::size(tests); ++i) {
        TArray<sk_sp<ToolUtils::TopoTestNode>> graph;
 
        (tests[i].fCreate)(&graph);
 
        const int numNodes = graph.size();
 
        ToolUtils::TopoTestNode::Shuffle(graph, &rand);
 
        bool actualResult = GrTTopoSort<ToolUtils::TopoTestNode>(graph);
        REPORTER_ASSERT(reporter, actualResult == tests[i].fExpectedResult);
        REPORTER_ASSERT(reporter, numNodes == graph.size());
 
        if (tests[i].fExpectedResult) {
            for (const auto& node : graph) {
                REPORTER_ASSERT(reporter, node->check());
            }
        } else {
            // When the topological sort fails all the nodes should still appear in the result
            // but their order can be somewhat arbitrary.
            std::vector<bool> seen(numNodes, false);
 
            for (const auto& node : graph) {
                SkASSERT(node);
                SkASSERT(!seen[node->id()]);
                seen[node->id()] = true;
            }
        }
 
        //SkDEBUGCODE(print(graph);)
    }
 
    // Some additional tests that do multiple partial sorts of graphs where we know nothing in an
    // earlier partion depends on anything in a later partition.
    for (int n = 2; n < 6; ++n) {
        for (int split = 1; split < n; ++split) {
            TArray<sk_sp<ToolUtils::TopoTestNode>> graph;
            create_simple_chain(&graph, n);
            SkSpan spanA = SkSpan(graph.begin(), split);
            SkSpan spanB = SkSpan(graph.begin() + split, n - split);
            ToolUtils::TopoTestNode::Shuffle(spanA, &rand);
            ToolUtils::TopoTestNode::Shuffle(spanB, &rand);
            bool result = GrTTopoSort(spanA);
            if (!result) {
                ERRORF(reporter, "Topo sort on partial chain failed.");
                return;
            }
            // Nothing outside of the processed span should have been output.
            for (const auto& node : spanB) {
                REPORTER_ASSERT(reporter, !ToolUtils::TopoTestNode::WasOutput(node.get()));
            }
            result = GrTTopoSort(spanB, split);
            if (!result) {
                ERRORF(reporter, "Topo sort on partial chain failed.");
                return;
            }
            for (const auto& node : graph) {
                REPORTER_ASSERT(reporter, node->check());
            }
        }
    }
}