Main Content

Number of Paths

Estimated static path count

Description

This metric measures the number of static paths in a function.

The recommended upper limit for this metric is 80. If the number of paths is high, the code is difficult to read and can cause more orange checks. Try to limit the value of this metric.

To enforce limits on metrics, see Compute Code Complexity Metrics Using Polyspace.

Computation Details

The number of paths is calculated according to these rules:

  • If the statements in a function do not break the control flow, the number of paths is one.

    Even an empty statement such as ; or empty block such as {} counts as one path.

  • A control flow statement introduces branches and adds to the original one path.

    • if-else if-else: Each if keyword introduces a new branch. The contribution from an if-else if-else block is the number of branches plus one (the original path). If a catch-all else is present, all paths go through the block; otherwise, one path bypasses the block.

      For instance, a function with an if(..) {} else if(..) {} else {} statement has three paths. A function with one if() {} only has two paths, one that goes through the if block and one that bypasses the block.

    • switch-case: Each case label introduces a new branch. The contribution from a switch block is the number of case labels plus one (the original path). If a catch-all default is present, all paths go through the block; otherwise, one path bypasses the block.

      For instance, a function with a statement switch (var) { case 1: .. break; case 2: .. break; default: .. } has three paths, all going through the switch block. If you omit the default, the function still has three paths, two going through the switch block and one bypassing the block.

    • for and while: Each loop statement introduces a new branch. The contribution from a loop is two - a path that goes through the loop and a path that bypasses the loop.

    • do-while: Each do-while statement introduces a new branch except when the condition of the while statement is explicitly false. Statements written as do{/*..*/}while(0) do not function as loops. Such statements are often used for enclosing multiple lines of macros within braces. For instance, this do-while statement serves to encapsulate the multiline macro rather than create a new path:

      #define myfunc(x) do{ ...\\
                            ...\\
                            ...}while(0);
      Polyspace® considers such statements to be a single path.

    Note that a statement with a ternary operator such as

    result = a > b ? a : b;
    is not considered as a statement that breaks the control flow.

  • If more than one control flow statement are present in a sequence without any nesting, the number of paths is the product of the contributions from each control flow statement.

    For instance, if a function has three for loops and two if-else blocks, one after another, the number of paths is 2 × 2 × 2 × 2 × 2 = 32.

    If many control flow statements are present in a function, the number of paths can be large. Nested control flow statements reduce the number of paths at the cost of increasing the depth of nesting. For an example, see Function with Nested Control Flow Statements.

  • The software displays specific values in cases where the metric is not calculated:

    • If goto statements are present in the body of the function, Polyspace cannot calculate the number of paths and shows the number of paths as Not Computed instead.

    • If the number of paths reaches an upper limit of 1,000,000,000, Polyspace stops the calculation and displays just the upper limit. The actual value might be higher.

  • The number of path is calculated statically. This statically calculated number represents the upper limit of the possible path in a function. Typically, the number of possible path during run time is lower than the number Polyspace reports.

  • Polyspace ignores compiler generated conditional statements in C++ when calculating the number of paths. The compiler might generate implicit conditional statements in operations such as initializing static variables or calling virtual functions.

Examples

expand all

int func(int ch) {
    return (ch * 2);
}

In this example, func has one path.

void func(int ch) {
    switch (ch)
    {
    case 1:
        break;
    case 2:
        break;
    case 3:
        break;
    case 4:
        break;
    default:
    }
}

In this example, func has five paths. Apart from the path that goes through the default, each case label followed by a statement causes the creation of a new path.

void func()
{
    int i = 0, j = 0, k = 0;
    for (i=0; i<10; i++)
    {
        for (j=0; j<10; j++)
        {
            for (k=0; k<10; k++)
            {
                if (i < 2 )
                    ;
                else
                {
                    if (i > 5)
                        ;
                    else
                        ;
                }
            }
        }
    }
}

In this example, func has six paths: three from the for statements, two from the if statements plus the original path that bypasses all control flow statements.

int look_up(int a, int b){
	if(a==b){
		return 1;
	}
	if(a>b+2){
		return 2;
	}
	if((a+b) < 10){
		return 3;
	}
	if((a+b) > 11){
		return 4;
	}
	if((a+b) >20 && (b-a)!=0){
		return 3;
	}
}

In this example, there are five if statements in sequence. Each if statements introduces two possible execution path. The total number of path is 2 × 2 × 2 × 2 × 2 = 32. Control statements in sequence increases the number of path quickly. If the number of path is higher than acceptable, consider refactoring your function.

Metric Information

Group: Function
Acronym: PATH
HIS Metric: Yes