java - 具有多个退出点的代码段中的圈复杂度

Question

我有这个验证密码的方法：

/**
 * Checks if the given password is valid.
 * 
 * @param password The password to validate.
 * @return {@code true} if the password is valid, {@code false} otherwise.
 */
public static boolean validatePassword(String password) {
    int len = password.length();
    if (len < 8 || len > 20)
        return false;
    boolean hasLetters = false;
    boolean hasDigits = false;
    for (int i=0; i<len; i++) {
        if (!Character.isLetterOrDigit(password.charAt(i)))
            return false;
        hasDigits = hasDigits || Character.isDigit(password.charAt(i));
        hasLetters = hasLetters || Character.isLetter(password.charAt(i));
    }
    return hasDigits && hasLetters;
}

让我们关注圈复杂度数：它的价值是什么？

Metrics 1.3.6说是 7，但我真的找不到 7 条独立路径：我只找到 5 条！维基百科也帮不上什么忙——我想怎么用这个公式π - s + 2？

我有 2 个if、1 个for和 3 个出口点，但我被卡住了：我必须计算入口点吗？我应该先计算两次，if因为它有两个条件吗？

编辑：

好的，现在我发现圈数是 7。这意味着有 7 个独立的路径，所以如果我想覆盖 100% 的代码，我应该能够找到 7 个不同的测试用例，对吗？

好吧，我仍然找不到最后一个！我发现了这些：

1. 有效：asdf1234
2. 太短：asdf123
3. 太长：asdfsgihzasweruihioruldhgobaihgfuiosbhrbgtadfhsdrhuorhguozr
4. 无效字符：asdf*123
5. 全数字：12345678
6. 无数字：asdfghjk
7. 呜呜呜？？？

Answer 1

我认为诀窍是计算逻辑运算符。

根据McCabe Cyclomatic Complexity 部分下的Metrics 链接 ( http://metrics.sourceforge.net/ )：

1 初始流程

3 个决策点（如果、为、如果）

3 个条件逻辑运算符 (||,||,||)

总数：7

Answer 2

我认为这里主要是条件句做短路，这是控制流的一种形式。有帮助的是重新编写代码以使其明确。在进行程序分析时，这种归一化很常见。一些特别的规范化（不是正式的，机器不会生成这个，但它明白了这一点）将使您的代码如下所示：

public static boolean validatePassword(String password) {
    int len = password.length();

    //evaluate 'len < 8 || len > 20'
    bool cond1 = len < 8;
    if (!cond1) cond1 = len > 20;
    //do the if test
    if (cond1)
        return false;

    boolean hasLetters = false;
    boolean hasDigits = false;
    //for loops are equivalent to while loops
    int i = 0;
    while(i < len) {
        if (!Character.isLetterOrDigit(password.charAt(i)))
            return false;

        //evaluate 'hasDigits || Character.isDigit(password.charAt(i))'
        bool hasDigitsVal = hasDigits;
        if (!hasDigitsVal) hasDigitsVal = Character.isDigit(password.charAt(i));
        //hasDigits = ...
        hasDigits = hasDigitsVal

        //evaluate 'hasLetters || Character.isLetter(password.charAt(i))'
        bool hasLettersVal = hasLetters;
        if (!hasLettersVal) hasLettersVal = Character.isLetter(password.charAt(i));
        //hasLetters = ...
        hasLetters = hasLettersVal;

        i++;
    }

    //evaluate 'hasDigits && hasLetters'
    bool cond2 = hasDigits;
    if (cond2) cond2 = hasLetters;
    //return ...
    return cond2;
}

请注意||and&&运算符本质上只是将if语句添加到代码中。另请注意，您现在有 6 个if语句和 1 个while循环！也许这就是你要找的7？

---

关于多个出口点，这是一个红鲱鱼。将每个函数视为具有一个退出节点，即函数的结尾。如果您有多个return语句，则每个return语句都会在该退出节点上绘制一条边。

void foo() {
    if (cond1) return a;
    if (cond2) return b;
    return c;
}

该图看起来像这样，其中-----val----> EXIT意味着以 的值退出函数val：

START -> cond1 ------------------------a------------> EXIT
           |                                            |
         cond2 ------------------------b----------------+
           |                                            |
         return -----------------------c----------------|

如果您重新编写代码，那么您基本上只需添加另一个“预返回”节点，然后转到退出节点：

void foo() {
    int val;
    if (cond1) {
        val= a;
    }
    else {
        if (cond2) {
            val= b;
        }
        else {
            val= c;
        }
    }
    return val;
}

现在看起来像这样：

START -> cond1 ---> val=a --------------------------> return ----val----> EXIT
           |                                            |
         cond2 ---> val=b ------------------------------+
           |                                            |
           + -----> val=c ------------------------------+

它仍然很复杂，而且代码更丑陋。

Answer 3

正如这里很好解释的那样：

圈复杂度 = ( 2 + ifs + loops +cases - return ) 其中：

* ifs is the number of IF operators in the function,
* loops is the number of loops in the function,
* cases is the number of switch branches in the function (without default), and
* return is the number of return operators in the function.

如前所述，还计算了逻辑条件。

例如if (len < 8 || len > 20)算作 3 个条件：

1. if
2. len<8
3. len > 20

这意味着，您的代码具有 的复杂性2 + 8 - 3 = 7，其中：

• 2 - 它总是在那里（见那里的公式）
• 8 - 分支数
• 3 - 退货数量