基于有向图的测试用例依赖检测

Posted by on August 09, 2018

背景

近期在实施一套测试自动化平台的项目,遇到一个工程问题:平台支持断言、用例参数的动态化,支持从历史用例、前置动作里获取结果,也支持实时运行依赖的用例。这样的功能带来一个问题,如果两个用例之间互相依赖,如A依赖B,B又反过来依赖A,将会导致这个测试集死循环。

思路与基础知识

这是一个典型的依赖检查,可以考虑用图来解决,对应的是有向图(Directed Graph)。

图的定义:是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V, E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。按照边的有无方向性分为无向图和有向图。

在有向图中,无法从某个顶点出发经过若干条边回到该点,则这个图是一个有向无环图(DAG图),见下图。

最终我们只要在添加顶点时与边时,时刻检查图是否有环,即可完成依赖检测。

工具库与代码编写

Google Guava里提供了图相关的库可以使用,所以基于Guava进行开发。代码非常简洁,主要根据TestNG的不同suite,缓存了不同的图。

public final class TestCaseCycleChecker {
    private static ConcurrentHashMap<String, MutableGraph<Integer>> graphs = new ConcurrentHashMap<>();

    public static void addNode(String suite, Integer testCaseId) {
        getOrCreateGraph(suite).addNode(testCaseId);
    }

    public static void addEdge(String suite, Integer nodeU, Integer nodeV) {
        getOrCreateGraph(suite).putEdge(nodeU, nodeV);
    }

    public static boolean checkCycle(String suite) {
        return Graphs.hasCycle(getOrCreateGraph(suite));
    }

    private static MutableGraph<Integer> getOrCreateGraph(String suite) {
        MutableGraph<Integer> graph = graphs.getOrDefault(suite, null);
        if (null == graph) {
            graph = GraphBuilder
                    .directed()
                    .allowsSelfLoops(true)
                    .build();
            graphs.put(suite, graph);
        }
        return graph;
    }
}

无环测试:

String suite = "uncycled";
TestCaseCycleChecker.addNode(suite, 1);
TestCaseCycleChecker.addNode(suite, 2);
TestCaseCycleChecker.addNode(suite, 3);
TestCaseCycleChecker.addEdge(suite, 1, 2);
TestCaseCycleChecker.addEdge(suite, 2, 3);
TestCaseCycleChecker.addEdge(suite, 1, 3);
Assert.assertTrue(!TestCaseCycleChecker.checkCycle(suite));

有环测试:

String suite = "cycled";
TestCaseCycleChecker.addNode(suite, 1);
TestCaseCycleChecker.addNode(suite, 2);
TestCaseCycleChecker.addNode(suite, 3);
TestCaseCycleChecker.addEdge(suite, 1, 2);
TestCaseCycleChecker.addEdge(suite, 2, 3);
TestCaseCycleChecker.addEdge(suite, 3, 1);
Assert.assertTrue(TestCaseCycleChecker.checkCycle(suite));