Cyclomatic Complexity in piece of code with multiple exit points

Question

I have this method that validates a password:

/**
 * 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;
}

Let's focus on the cyclomatic complexity number: what is its value?

Metrics 1.3.6 says it's 7, but I cannot really find seven independent paths: I only find 5! And Wikipedia didn't help out much—how am I suppose to use this formula π - s + 2?

I have 2 if's, 1 for and 3 exit points but I'm stuck: do I have to count the entry point? Should I count twice the first if since it has two conditions?

EDIT:

Ok, now I found out that Cyclomatic Number is 7. This means that there are 7 independent paths and so I should be able to find 7 different test cases if I would to cover 100% of code, am I right?

Well, I still cannot found the last one! I found these:

1. Valid: asdf1234
2. Too short: asdf123
3. Too long: asdfsgihzasweruihioruldhgobaihgfuiosbhrbgtadfhsdrhuorhguozr
4. Invalid character: asdf*123
5. All-digit: 12345678
6. No-digits: asdfghjk
7. wtf???

Answer 1

I think the trick is that the logical operators are counted.

Based off of your Metrics link (http://metrics.sourceforge.net/) under the McCabe Cyclomatic Complexity section:

1 Initial flow

3 decision points (if,for,if)

3 conditional logic operators (||,||,||)

total: 7

Answer 2

I think the main thing here is that conditionals do short-circuiting, which is a form of control flow. What helps is to re-write the code to make that explicit. This sort of normalization is common when doing program analysis. Some ad-hoc normalization (not formal and a machine wouldn't generate this, but it gets the point across) would make your code look like the following:

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;
}

Notice how the || and && operators essentially just add if statements to the code. Also notice that you now have 6 if statements and one while loop! Maybe that is the 7 you were looking for?

---

About multiple exit points, that's a red herring. Consider each function as having one exit node, the end of the function. If you have multiple return statements, each return statement would draw an edge to that exit node.

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

The graph would look like this, where -----val----> EXIT means exiting the function with a value of val:

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

If you re-write the code, then you just basically add another "pre-return" node that then goes to the exit node:

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

Now it looks like this:

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

It's still as complex, and the code is just uglier.

Answer 3

As nicely explained here :

Cyclomatic Complexity = ( 2 + ifs + loops +cases - return ) where:

* 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.

As already mentioned, logical conditions are also calculated.

For example if (len < 8 || len > 20) counts as 3 conditions :

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

That means, that your code has complexity of 2 + 8 - 3 = 7, where :

• 2 - it is always there (see formula up there)
• 8 - number of branches
• 3 - number of returns