Improve performance of `formatter` fuzz target

[john-h-kastner-aws]

Category

DRT target(s)

Describe the feature you'd like to request

This DRT target is regularly generating "slow units" in our nightly testing. Unlike with some other targets, these are easily reproducible from the recorded test files.

on the current HEAD:

base64 --decode > slow_unit <<EOF
/wEm//8BAABH////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////MjIy3jAyMjIv
MgAyMjIx2sUy////////////////////////////////////jo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6O
jo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6O
jo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo6Ojo7/////
//////////////////////////////////////////////+Ojo6Ojo6OjuHh4f////8Q1tbW1tbW
1tbW1tbW1tbW1tbW1tbW1tbW1tbW1tDW1gAAAAAAHDMAFAAr/////////w8AfzMzOA==
EOF
cargo fuzz run -s none formatter slow_unit

should output something like

fuzz/target/x86_64-unknown-linux-gnu/release/formatter: Running 1 inputs 1 time(s) each.
Running: slow_unit
Executed slow_unit in 16102 ms

I believe there are two issues here:

1. The Cedar policy generated by this test case is large, and takes some significant time to format. Formatting this policy file takes ~1.5 seconds while just checking that it parses only takes ~0.1 seconds (measured from the CLI). This still leaves most of the time unaccounted for.
2. The formater targets inject uids into comments in the policy, and then checks if each of those is still present after formatting to ensure that comments are not deleted. We check for the uid with a linear scan, and add it looks like we add O(policy_size) uid comments, so this whole check is O(policy_size^2), which could quickly start to take a while. Commenting out this check reduces the total time for the test case to 3859 ms.

Describe alternatives you've considered

.

Additional context

No response

Is this something that you'd be interested in working on?

• 👋 I may be able to implement this feature request
• ⚠️ This feature might incur a breaking change

[shaobo-he-aws]

Nice analysis.

[john-h-kastner-aws]

Possibly resolved by #318, pending some fuzzing runs to see if still get slow units

[john-h-kastner-aws]

Closing this as fixed by #318. I haven't seen any slow units since merging