Path Testing is a heuristic to identify possible test cases by looking at code paths. A given code path is a sequence of statements from the point of entry to the point of exit (e.g., for a function).
The number of possible paths can be very large, so several techniques can be used to narrow down the types of paths to check:
- Check only intersting/unique paths (e.g., minimal path, path where each loop is iterated once)
- Check extreme paths (e.g., large amounts of loop iterations, deep nesting)
- Bound the number of loop iterations overall (e.g., 3 loop iterations at most in the path).
### Worked example
Consider the OpenZeppelin `findUpperBound` function below in the `Arrays` library:
-- CODE language-solidity --
/**
* @dev Searches a sorted `array` and returns the first index that contains
* a value greater or equal to `element`. If no such index exists (i.e. all
* values in the array are strictly less than `element`), the array length is
* returned. Time complexity O(log n).
*
* `array` is expected to be sorted in ascending order, and to contain no
* repeated elements.
*/
function findUpperBound(uint256[] storage array, uint256 element) internal view returns (uint256) {
if (array.length == 0) {
return 0;
}
uint256 low = 0;
uint256 high = array.length;
while (low < high) {
uint256 mid = Math.average(low, high);
// Note that mid will always be strictly less than high (i.e. it will be a valid array index)
// because Math.average rounds down (it does integer division with truncation).
if (array[mid] > element) {
high = mid;
} else {
low = mid + 1;
}
}
// At this point `low` is the exclusive upper bound. We will return the inclusive upper bound.
if (low > 0 && array[low - 1] == element) {
return low - 1;
} else {
return low;
}
}
Here are two possible paths through the code:
- For an empty array, first condition `array.length == 0` passes and the function returns `0`
- Consider the array `[1, 2, 3]` and the element `2` then:
- first check fails
- `low = 0` and `high = 2` are set
- `mid = 1` is set
- `array[mid]` > `element` fails, `low = 2` now
- next loop condition check fails since `low == high`
- exit while loop
- `array[low - 1] == element` is true, `low - 1` is returned (`1`).
