Ability to get sorted arrays when fuzzing

[PaulRBerg]

Component

Forge

Describe the feature you would like

As discussed in #3948, my protocol has some business logic that is dependent upon the end user sending a sorted array as a function argument.

I've been bashing my head against the wall trying to fuzz the input arrays in a way that is scalable (tests don't take ages to run), to no fruition.

I pulled together an implementation of the quicksort algorithm in Solidity based on the sources I found on the Internet. The issue is that sorting a fuzzed arrays slows down test run times.

It would be nice to be able to instruct Foundry to sort the array on our behalf. I'm thinking of something like this (echo-ing the proposal I left in #4085):

/// @custom:sort-array
function test_Something(uint256[] memory arr) external {
    // ...
}

That is, whenever the custom NatSpec tag above is specified, Foundry would provide the user with a sorted array arr, every time. It would be cheaper to let Foundry do this in Rust rather than sorting the array in memory in Solidity.

As an alternative to the above, we could consider using a specific prefix for the array variable names:

function test_Something(uint256[] memory sortedArr) external {
    // ...
}

The idea being, every time Foundry sees a function param that is an array type and its name starts with sorted, it would automatically sort the array.

Sorted arrays should be a common enough use case for a feature like this to be worth considering and implementing.

[0xMelkor]

This sounds interesting.

Technically this is feasible

We can use proptest::prop_map to generate a sorted array out of a proptest strategy.
We could also extend the input of the fuzz_param function to accept some kind of metadata associated to param.
Such metadata would let us generate more sophisticated compound strategies (i.e. for sorted arrays).

foundry/evm/src/fuzz/strategies/param.rs

Line 14 in 8307d6d

pub fn fuzz_param(param: &ParamType) -> impl Strategy<Value = Token> {

The config part

imho the NatSpec approach is probably more flexible than the param name. Given though we should define some meta language to convey strategy configs to the fuzzer i.e.

/// forge-config:fuzz:strategy:sort(arr, desc)
function test_Something(uint256[] memory arr) external {
    // ...
}

[iFrostizz]

Wondering if what lacks from current Foundry fuzz testing framework is a corpus, just like we have with libfuzzer for instance, see the Corpus enum https://docs.rs/libfuzzer-sys/latest/libfuzzer_sys/macro.fuzz_target.html
Instead of adding features top down for every strategy, just implement the corpus and it will do that for free