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).
Consider the OpenZeppelin findUpperBound function below in the Arrays library:
/**
* @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 == 0passes and the function returns0 - Consider the array
[1, 2, 3]and the element2then: - first check fails -low = 0andhigh = 2are set -mid = 1is set -array[mid]>elementfails,low = 2now - next loop condition check fails sincelow == high- exit while loop -array[low - 1] == elementis true,low - 1is returned (1).