Loop Testing is an advanced form of Decision/Branch Testing that focuses on testing all possible linear code paths without branching. Each of these paths is called a Linear Code Sequence and Jump (LCSAJ), matching the underlying representation of the code path in EVM opcode terms.
For advanced readers: In EVM control flow, each LCSAJ is a sequence of opcodes optionally starting with JUMPDEST ending with a JUMP / JUMPI or an execution terminating opcode like STOP .
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;
}
}In the while loop above there are two LSCAJ paths to test:
- Going through a full loop iteration and jumping to do another iteration of the loop
- Going through a full loop iteration and exiting the loop due to the loop condition.
With nested loops, break , continue statements, there could be significantly more paths between jump points.