获得圈复杂度

Question

我正在研究使用 Rascal 计算 java 方法的圈复杂度。

一种方法是：

• 从方法中获取 AST
• 在这棵树上使用访问模式
• 检查以下所有增加 CC 的关键字：case, catch, do, while, if, for,foreach

另一种是使用图论并使用公式 e-n+2。使用 rascal 函数可以很容易地获得 e 和 n。我的问题是如何构建控制流图，我发现了以下模块： analysis::flow::ControlFlow这似乎是朝着正确方向迈出的一步，但我完全不知道从哪里开始。

Answer 1

最简单的方法确实是计算 AST 上的分叉节点。

在我们解释 SLOC 和 CC 彼此之间没有强相关性的出版物（预印本）中，我们还共享了我们的 rascal 代码来计算 CC（见图 2）。

下面是从文章中提取的代码，首先使用 m3创建文件的AST，并搜索文件中的所有方法/代码块。每个方法你调用这个访问 AST 并计算某些节点的 rascal 函数。

int calcCC(Statement impl) {
    int result = 1;
    visit (impl) {
        case \if(_,_) : result += 1;
        case \if(_,_,_) : result += 1;
        case \case(_) : result += 1;
        case \do(_,_) : result += 1;
        case \while(_,_) : result += 1;
        case \for(_,_,_) : result += 1;
        case \for(_,_,_,_) : result += 1;
        case \foreach(_,_,_) : result += 1;
        case \catch(_,_): result += 1;
        case \conditional(_,_,_): result += 1;
        case \infix(_,"&&",_) : result += 1;
        case \infix(_,"||",_) : result += 1;
    }
    return result;
}