Exponential time in formatting nested brackets?

[y1ca1]

In some cases, we'd like to convert between Rust enums and structural binary sum types like:

enum Either<T, U> {
    Left(T),
    Right(U),
}

pub enum Enum {
    Variant0(u32),
    Variant1(u32),
    Variant2(u32),
    Variant3(u32),
    Variant4(u32),
}

pub type EnumInner = Either<u32, Either<u32, Either<u32, Either<u32, u32>>>>;

fn convert(m: Enum) -> EnumInner {
    match m {
        Enum::Variant0(m) => Either::Left(m),
        Enum::Variant1(m) => Either::Right(Either::Left(m)),
        Enum::Variant2(m) => Either::Right(Either::Right(Either::Left(m))),
        Enum::Variant3(m) => Either::Right(Either::Right(Either::Right(Either::Left(m)))),
        Enum::Variant4(m) => Either::Right(Either::Right(Either::Right(Either::Right(m)))),
    }
}

fn convert_inv(m: EnumInner) -> Enum {
    match m {
        Either::Left(m) => Enum::Variant0(m),
        Either::Right(Either::Left(m)) => Enum::Variant1(m),
        Either::Right(Either::Right(Either::Left(m))) => Enum::Variant2(m),
        Either::Right(Either::Right(Either::Right(Either::Left(m)))) => Enum::Variant3(m),
        Either::Right(Either::Right(Either::Right(Either::Right(m)))) => Enum::Variant4(m),
    }
}

verusfmt can handle this pattern up to ~27 variants on my MacBook Pro M3. It took verusfmt ~5s to format 20 variants, and the time it took to process more variants exponentially increases henceforth.

The good news (or bad news?) is that rustfmt also timed out at ~30 variants.

You can play with it using this python script: https://github.com/secure-foundations/vest/blob/main/vest-dsl/test/test_fmt_nested.py

Usage: test_fmt_nested.py <verusfmt|rustfmt> <number_of_variants>

Also related: it seems like formatting pest's autogenerated parsers (similar to what we have for Vest) is an open issue for rustfmt: rust-lang/rustfmt#5500, rust-lang/rustfmt#4867, rust-lang/rustfmt#4476

[jaybosamiya]

Just copying over my comment from Slack to track it closer to the issue:

I personally won't be able to get to this particularly soon; could you use #[verusfmt::skip]? That'll prevent the printer from trying to actually organize that portion (it'll still parse that bit, but will just put the text verbatim for any items that have the skip attribute, so hopefully you are not hitting the exponential, but are still getting good formatting for everything else in the file). If the skipped version doesn't work to speed it up and unblock you, then let me know and I'll try to see how to get at least the skipping to be faster. Improving the non-skipped perf might be a more involved change (at least how I envision it right now).