Repository: duesee/imap-codec (language: python)

Issue:
tests: Improve fuzzing throughput
Over the time, fuzzing throughput decreased. This is due to more complex `Arbitrary` implementations. Notably, `BodyStructure`, `SearchKey`, `Thread`, ... We probably want to test these in isolation at some point.

* [x] What do we want to improve? https://github.com/duesee/imap-codec/pull/459
* [x] Feature gate complex `Arbitrary` implementations https://github.com/duesee/imap-codec/pull/459


Discussion / hints:

Fix patch:
diff --git a/imap-codec/fuzz/Cargo.toml b/imap-codec/fuzz/Cargo.toml
index b50e862d..619a1280 100644
--- a/imap-codec/fuzz/Cargo.toml
+++ b/imap-codec/fuzz/Cargo.toml
@@ -10,6 +10,10 @@ license = "MIT OR Apache-2.0"
 cargo-fuzz = true
 
 [features]
+# <Forward to imap-types>
+arbitrary_simplified = ["imap-types/arbitrary_simplified"]
+# </Forward to imap-types>
+
 # <Forward to imap-codec>
 # IMAP
 starttls = ["imap-codec/starttls"]
@@ -45,6 +49,7 @@ split = []
 
 [dependencies]
 libfuzzer-sys = "0.4"
+imap-types = { path = "../../imap-types" }
 imap-codec = { path = "..", features = ["arbitrary"] }
 
 [[bin]]
diff --git a/imap-types/Cargo.toml b/imap-types/Cargo.toml
index cfc0d58b..74d43876 100644
--- a/imap-types/Cargo.toml
+++ b/imap-types/Cargo.toml
@@ -11,6 +11,7 @@ edition = "2021"
 
 [features]
 arbitrary = ["dep:arbitrary", "unvalidated", "chrono/arbitrary", "chrono/std"]
+arbitrary_simplified = ["arbitrary"]
 bounded-static = ["dep:bounded-static", "bounded-static/derive"]
 serde = ["dep:serde", "chrono/serde"]
 
diff --git a/imap-types/src/arbitrary.rs b/imap-types/src/arbitrary.rs
index 42df0d72..0d8c4558 100644
--- a/imap-types/src/arbitrary.rs
+++ b/imap-types/src/arbitrary.rs
@@ -1,23 +1,16 @@
 use arbitrary::{Arbitrary, Unstructured};
 use chrono::{FixedOffset, TimeZone};
 
-#[cfg(feature = "ext_sort_thread")]
-use crate::extensions::{
-    sort::SortAlgorithm,
-    thread::{Thread, ThreadingAlgorithm},
-};
 use crate::{
     auth::AuthMechanism,
     body::{
-        BasicFields, Body, BodyExtension, BodyStructure, MultiPartExtensionData,
-        SinglePartExtensionData, SpecificFields,
+        BasicFields, Body, BodyExtension, BodyStructure, SinglePartExtensionData, SpecificFields,
     },
     core::{
         AString, Atom, AtomExt, IString, Literal, LiteralMode, NString, Quoted, QuotedChar, Tag,
         Text, Vec1, Vec2,
     },
     datetime::{DateTime, NaiveDate},
-    envelope::Envelope,
     extensions::{enable::CapabilityEnable, quota::Resource},
     flag::{Flag, FlagNameAttribute},
     mailbox::{ListCharString, Mailbox, MailboxOther},
@@ -28,8 +21,10 @@ use crate::{
     search::SearchKey,
     sequence::SequenceSet,
 };
+#[cfg(not(feature = "arbitrary_simplified"))]
+use crate::{body::MultiPartExtensionData, envelope::Envelope};
 
-macro_rules! implement_tryfrom {
+macro_rules! impl_arbitrary_try_from {
     ($target:ty, $from:ty) => {
         impl<'a> Arbitrary<'a> for $target {
             fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
@@ -42,7 +37,9 @@ macro_rules! implement_tryfrom {
     };
 }
 
-macro_rules! implement_tryfrom_t {
+pub(crate) use impl_arbitrary_try_from;
+
+macro_rules! impl_arbitrary_try_from_t {
     ($target:ty, $from:ty) => {
         impl<'a, T> Arbitrary<'a> for $target
         where
@@ -58,27 +55,23 @@ macro_rules! implement_tryfrom_t {
     };
 }
 
-implement_tryfrom! { Atom<'a>, &str }
-implement_tryfrom! { AtomExt<'a>, &str }
-implement_tryfrom! { Quoted<'a>, &str }
-implement_tryfrom! { Tag<'a>, &str }
-implement_tryfrom! { Text<'a>, &str }
-implement_tryfrom! { ListCharString<'a>, &str }
-implement_tryfrom! { QuotedChar, char }
-implement_tryfrom! { Mailbox<'a>, &str }
-implement_tryfrom! { Capability<'a>, Atom<'a> }
-implement_tryfrom! { Flag<'a>, &str }
-implement_tryfrom! { FlagNameAttribute<'a>, Atom<'a> }
-implement_tryfrom! { MailboxOther<'a>, AString<'a> }
-implement_tryfrom! { CapabilityEnable<'a>, &str }
-implement_tryfrom! { Resource<'a>, &str }
-implement_tryfrom! { AuthMechanism<'a>, &str }
-#[cfg(feature = "ext_sort_thread")]
-implement_tryfrom! { SortAlgorithm<'a>, Atom<'a> }
-implement_tryfrom_t! { Vec1<T>, Vec<T> }
-implement_tryfrom_t! { Vec2<T>, Vec<T> }
-#[cfg(feature = "ext_sort_thread")]
-implement_tryfrom! { ThreadingAlgorithm<'a>, Atom<'a> }
+impl_arbitrary_try_from! { Atom<'a>, &str }
+impl_arbitrary_try_from! { AtomExt<'a>, &str }
+impl_arbitrary_try_from! { Quoted<'a>, &str }
+impl_arbitrary_try_from! { Tag<'a>, &str }
+impl_arbitrary_try_from! { Text<'a>, &str }
+impl_arbitrary_try_from! { ListCharString<'a>, &str }
+impl_arbitrary_try_from! { QuotedChar, char }
+impl_arbitrary_try_from! { Mailbox<'a>, &str }
+impl_arbitrary_try_from! { Capability<'a>, Atom<'a> }
+impl_arbitrary_try_from! { Flag<'a>, &str }
+impl_arbitrary_try_from! { FlagNameAttribute<'a>, Atom<'a> }
+impl_arbitrary_try_from! { MailboxOther<'a>, AString<'a> }
+impl_arbitrary_try_from! { CapabilityEnable<'a>, &str }
+impl_arbitrary_try_from! { Resource<'a>, &str }
+impl_arbitrary_try_from! { AuthMechanism<'a>, &str }
+impl_arbitrary_try_from_t! { Vec1<T>, Vec<T> }
+impl_arbitrary_try_from_t! { Vec2<T>, Vec<T> }
 
 impl<'a> Arbitrary<'a> for CommandContinuationRequestBasic<'a> {
     fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
@@ -187,254 +180,266 @@ impl<'a> Arbitrary<'a> for CodeOther<'a> {
 
 impl<'a> Arbitrary<'a> for SearchKey<'a> {
     fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
-        fn make_search_key<'a>(u: &mut Unstructured<'a>) -> arbitrary::Result<SearchKey<'a>> {
-            Ok(match u.int_in_range(0u8..=33)? {
-                0 => SearchKey::SequenceSet(SequenceSet::arbitrary(u)?),
-                1 => SearchKey::All,
-                2 => SearchKey::Answered,
-                3 => SearchKey::Bcc(AString::arbitrary(u)?),
-                4 => SearchKey::Before(NaiveDate::arbitrary(u)?),
-                5 => SearchKey::Body(AString::arbitrary(u)?),
-                6 => SearchKey::Cc(AString::arbitrary(u)?),
-                7 => SearchKey::Deleted,
-                8 => SearchKey::Draft,
-                9 => SearchKey::Flagged,
-                10 => SearchKey::From(AString::arbitrary(u)?),
-                11 => SearchKey::Header(AString::arbitrary(u)?, AString::arbitrary(u)?),
-                12 => SearchKey::Keyword(Atom::arbitrary(u)?),
-                13 => SearchKey::Larger(u32::arbitrary(u)?),
-                14 => SearchKey::New,
-                15 => SearchKey::Old,
-                16 => SearchKey::On(NaiveDate::arbitrary(u)?),
-                17 => SearchKey::Recent,
-                18 => SearchKey::Seen,
-                19 => SearchKey::SentBefore(NaiveDate::arbitrary(u)?),
-                20 => SearchKey::SentOn(NaiveDate::arbitrary(u)?),
-                21 => SearchKey::SentSince(NaiveDate::arbitrary(u)?),
-                22 => SearchKey::Since(NaiveDate::arbitrary(u)?),
-                23 => SearchKey::Smaller(u32::arbitrary(u)?),
-                24 => SearchKey::Subject(AString::arbitrary(u)?),
-                25 => SearchKey::Text(AString::arbitrary(u)?),
-                26 => SearchKey::To(AString::arbitrary(u)?),
-                27 => SearchKey::Uid(SequenceSet::arbitrary(u)?),
-                28 => SearchKey::Unanswered,
-                29 => SearchKey::Undeleted,
-                30 => SearchKey::Undraft,
-                31 => SearchKey::Unflagged,
-                32 => SearchKey::Unkeyword(Atom::arbitrary(u)?),
-                33 => SearchKey::Unseen,
-                _ => unreachable!(),
-            })
-        }
+        #[cfg(not(feature = "arbitrary_simplified"))]
+        return arbitrary_search_key_limited(u, 7);
+        #[cfg(feature = "arbitrary_simplified")]
+        return arbitrary_search_key_leaf(u);
+    }
+}
 
-        fn make_search_key_rec<'a>(
-            u: &mut Unstructured<'a>,
-            depth: u8,
-        ) -> arbitrary::Result<SearchKey<'a>> {
-            if depth == 0 {
-                return make_search_key(u);
-            }
+#[cfg(not(feature = "arbitrary_simplified"))]
+fn arbitrary_search_key_limited<'a>(
+    u: &mut Unstructured<'a>,
+    depth: u8,
+) -> arbitrary::Result<SearchKey<'a>> {
+    if depth == 0 {
+        return arbitrary_search_key_leaf(u);
+    }
 
-            Ok(match u.int_in_range(0u8..=36)? {
-                0 => SearchKey::And({
-                    let keys = {
-                        let len = u.arbitrary_len::<SearchKey>()?;
-                        let mut tmp = Vec::with_capacity(len);
+    Ok(match u.int_in_range(0u8..=36)? {
+        0 => SearchKey::And({
+            let keys = {
+                let len = u.arbitrary_len::<SearchKey>()?;
+                let mut tmp = Vec::with_capacity(len);
 
-                        for _ in 0..len {
-                            tmp.push(make_search_key_rec(u, depth - 1)?);
-                        }
+                for _ in 0..len {
+                    tmp.push(arbitrary_search_key_limited(u, depth - 1)?);
+                }
 
-                        tmp
-                    };
+                tmp
+            };
 
-                    if !keys.is_empty() {
-                        Vec1::try_from(keys).unwrap()
-                    } else {
-                        Vec1::from(make_search_key(u)?)
-                    }
-                }),
-                1 => SearchKey::SequenceSet(SequenceSet::arbitrary(u)?),
-                2 => SearchKey::All,
-                3 => SearchKey::Answered,
-                4 => SearchKey::Bcc(AString::arbitrary(u)?),
-                5 => SearchKey::Before(NaiveDate::arbitrary(u)?),
-                6 => SearchKey::Body(AString::arbitrary(u)?),
-                7 => SearchKey::Cc(AString::arbitrary(u)?),
-                8 => SearchKey::Deleted,
-                9 => SearchKey::Draft,
-                10 => SearchKey::Flagged,
-                11 => SearchKey::From(AString::arbitrary(u)?),
-                12 => SearchKey::Header(AString::arbitrary(u)?, AString::arbitrary(u)?),
-                13 => SearchKey::Keyword(Atom::arbitrary(u)?),
-                14 => SearchKey::Larger(u32::arbitrary(u)?),
-                15 => SearchKey::New,
-                16 => SearchKey::Not(Box::new(make_search_key_rec(u, depth - 1)?)),
-                17 => SearchKey::Old,
-                18 => SearchKey::On(NaiveDate::arbitrary(u)?),
-                19 => SearchKey::Or(
-                    Box::new(make_search_key_rec(u, depth - 1)?),
-                    Box::new(make_search_key_rec(u, depth - 1)?),
-                ),
-                20 => SearchKey::Recent,
-                21 => SearchKey::Seen,
-                22 => SearchKey::SentBefore(NaiveDate::arbitrary(u)?),
-                23 => SearchKey::SentOn(NaiveDate::arbitrary(u)?),
-                24 => SearchKey::SentSince(NaiveDate::arbitrary(u)?),
-                25 => SearchKey::Since(NaiveDate::arbitrary(u)?),
-                26 => SearchKey::Smaller(u32::arbitrary(u)?),
-                27 => SearchKey::Subject(AString::arbitrary(u)?),
-                28 => SearchKey::Text(AString::arbitrary(u)?),
-                29 => SearchKey::To(AString::arbitrary(u)?),
-                30 => SearchKey::Uid(SequenceSet::arbitrary(u)?),
-                31 => SearchKey::Unanswered,
-                32 => SearchKey::Undeleted,
-                33 => SearchKey::Undraft,
-                34 => SearchKey::Unflagged,
-                35 => SearchKey::Unkeyword(Atom::arbitrary(u)?),
-                36 => SearchKey::Unseen,
-                _ => unreachable!(),
-            })
-        }
+            if !keys.is_empty() {
+                Vec1::try_from(keys).unwrap()
+            } else {
+                Vec1::from(arbitrary_search_key_leaf(u)?)
+            }
+        }),
+        1 => SearchKey::SequenceSet(SequenceSet::arbitrary(u)?),
+        2 => SearchKey::All,
+        3 => SearchKey::Answered,
+        4 => SearchKey::Bcc(AString::arbitrary(u)?),
+        5 => SearchKey::Before(NaiveDate::arbitrary(u)?),
+        6 => SearchKey::Body(AString::arbitrary(u)?),
+        7 => SearchKey::Cc(AString::arbitrary(u)?),
+        8 => SearchKey::Deleted,
+        9 => SearchKey::Draft,
+        10 => SearchKey::Flagged,
+        11 => SearchKey::From(AString::arbitrary(u)?),
+        12 => SearchKey::Header(AString::arbitrary(u)?, AString::arbitrary(u)?),
+        13 => SearchKey::Keyword(Atom::arbitrary(u)?),
+        14 => SearchKey::Larger(u32::arbitrary(u)?),
+        15 => SearchKey::New,
+        16 => SearchKey::Not(Box::new(arbitrary_search_key_limited(u, depth - 1)?)),
+        17 => SearchKey::Old,
+        18 => SearchKey::On(NaiveDate::arbitrary(u)?),
+        19 => SearchKey::Or(
+            Box::new(arbitrary_search_key_limited(u, depth - 1)?),
+            Box::new(arbitrary_search_key_limited(u, depth - 1)?),
+        ),
+        20 => SearchKey::Recent,
+        21 => SearchKey::Seen,
+        22 => SearchKey::SentBefore(NaiveDate::arbitrary(u)?),
+        23 => SearchKey::SentOn(NaiveDate::arbitrary(u)?),
+        24 => SearchKey::SentSince(NaiveDate::arbitrary(u)?),
+        25 => SearchKey::Since(NaiveDate::arbitrary(u)?),
+        26 => SearchKey::Smaller(u32::arbitrary(u)?),
+        27 => SearchKey::Subject(AString::arbitrary(u)?),
+        28 => SearchKey::Text(AString::arbitrary(u)?),
+        29 => SearchKey::To(AString::arbitrary(u)?),
+        30 => SearchKey::Uid(SequenceSet::arbitrary(u)?),
+        31 => SearchKey::Unanswered,
+        32 => SearchKey::Undeleted,
+        33 => SearchKey::Undraft,
+        34 => SearchKey::Unflagged,
+        35 => SearchKey::Unkeyword(Atom::arbitrary(u)?),
+        36 => SearchKey::Unseen,
+        _ => unreachable!(),
+    })
+}
 
-        make_search_key_rec(u, 7)
-    }
+fn arbitrary_search_key_leaf<'a>(u: &mut Unstructured<'a>) -> arbitrary::Result<SearchKey<'a>> {
+    Ok(match u.int_in_range(0u8..=33)? {
+        0 => SearchKey::SequenceSet(SequenceSet::arbitrary(u)?),
+        1 => SearchKey::All,
+        2 => SearchKey::Answered,
+        3 => SearchKey::Bcc(AString::arbitrary(u)?),
+        4 => SearchKey::Before(NaiveDate::arbitrary(u)?),
+        5 => SearchKey::Body(AString::arbitrary(u)?),
+        6 => SearchKey::Cc(AString::arbitrary(u)?),
+        7 => SearchKey::Deleted,
+        8 => SearchKey::Draft,
+        9 => SearchKey::Flagged,
+        10 => SearchKey::From(AString::arbitrary(u)?),
+        11 => SearchKey::Header(AString::arbitrary(u)?, AString::arbitrary(u)?),
+        12 => SearchKey::Keyword(Atom::arbitrary(u)?),
+        13 => SearchKey::Larger(u32::arbitrary(u)?),
+        14 => SearchKey::New,
+        15 => SearchKey::Old,
+        16 => SearchKey::On(NaiveDate::arbitrary(u)?),
+        17 => SearchKey::Recent,
+        18 => SearchKey::Seen,
+        19 => SearchKey::SentBefore(NaiveDate::arbitrary(u)?),
+        20 => SearchKey::SentOn(NaiveDate::arbitrary(u)?),
+        21 => SearchKey::SentSince(NaiveDate::arbitrary(u)?),
+        22 => SearchKey::Since(NaiveDate::arbitrary(u)?),
+        23 => SearchKey::Smaller(u32::arbitrary(u)?),
+        24 => SearchKey::Subject(AString::arbitrary(u)?),
+        25 => SearchKey::Text(AString::arbitrary(u)?),
+        26 => SearchKey::To(AString::arbitrary(u)?),
+        27 => SearchKey::Uid(SequenceSet::arbitrary(u)?),
+        28 => SearchKey::Unanswered,
+        29 => SearchKey::Undeleted,
+        30 => SearchKey::Undraft,
+        31 => SearchKey::Unflagged,
+        32 => SearchKey::Unkeyword(Atom::arbitrary(u)?),
+        33 => SearchKey::Unseen,
+        _ => unreachable!(),
+    })
 }
 
 impl<'a> Arbitrary<'a> for BodyStructure<'a> {
     fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
-        fn make_body_structure_terminator<'a>(
-            u: &mut Unstructured<'a>,
-        ) -> arbitrary::Result<BodyStructure<'a>> {
-            Ok(BodyStructure::Single {
-                body: Body {
-                    basic: BasicFields::arbitrary(u)?,
-                    specific: match u.int_in_range(1..=2)? {
-                        1 => SpecificFields::Basic {
-                            r#type: IString::arbitrary(u)?,
-                            subtype: IString::arbitrary(u)?,
-                        },
-                        // No SpecificFields::Message because it would recurse.
-                        2 => SpecificFields::Text {
-                            subtype: IString::arbitrary(u)?,
-                            number_of_lines: u32::arbitrary(u)?,
-                        },
-                        _ => unreachable!(),
+        #[cfg(not(feature = "arbitrary_simplified"))]
+        return arbitrary_body_structure_limited(u, 3);
+        #[cfg(feature = "arbitrary_simplified")]
+        return arbitrary_body_structure_leaf(u);
+    }
+}
+
+#[cfg(not(feature = "arbitrary_simplified"))]
+fn arbitrary_body_structure_limited<'a>(
+    u: &mut Unstructured<'a>,
+    depth: u8,
+) -> arbitrary::Result<BodyStructure<'a>> {
+    if depth == 0 {
+        return arbitrary_body_structure_leaf(u);
+    }
+
+    Ok(match u.int_in_range(1..=2)? {
+        1 => BodyStructure::Single {
+            body: Body {
+                basic: BasicFields::arbitrary(u)?,
+                specific: match u.int_in_range(1..=3)? {
+                    1 => SpecificFields::Basic {
+                        r#type: IString::arbitrary(u)?,
+                        subtype: IString::arbitrary(u)?,
+                    },
+                    2 => SpecificFields::Message {
+                        envelope: Box::<Envelope>::arbitrary(u)?,
+                        body_structure: Box::new(arbitrary_body_structure_limited(u, depth - 1)?),
+                        number_of_lines: u32::arbitrary(u)?,
                     },
+                    3 => SpecificFields::Text {
+                        subtype: IString::arbitrary(u)?,
+                        number_of_lines: u32::arbitrary(u)?,
+                    },
+                    _ => unreachable!(),
                 },
-                extension_data: Option::<SinglePartExtensionData>::arbitrary(u)?,
-            })
-        }
+            },
+            extension_data: Option::<SinglePartExtensionData>::arbitrary(u)?,
+        },
+        2 => BodyStructure::Multi {
+            bodies: {
+                let bodies = {
+                    let len = u.arbitrary_len::<BodyStructure>()?;
+                    let mut tmp = Vec::with_capacity(len);
+
+                    for _ in 0..len {
+                        tmp.push(arbitrary_body_structure_limited(u, depth - 1)?);
+                    }
 
-        fn make_body_structure_rec<'a>(
-            u: &mut Unstructured<'a>,
-            depth: u8,
-        ) -> arbitrary::Result<BodyStructure<'a>> {
-            if depth == 0 {
-                return make_body_structure_terminator(u);
-            }
+                    tmp
+                };
 
-            Ok(match u.int_in_range(1..=2)? {
-                1 => BodyStructure::Single {
-                    body: Body {
-                        basic: BasicFields::arbitrary(u)?,
-                        specific: match u.int_in_range(1..=3)? {
-                            1 => SpecificFields::Basic {
-                                r#type: IString::arbitrary(u)?,
-                                subtype: IString::arbitrary(u)?,
-                            },
-                            2 => SpecificFields::Message {
-                                envelope: Box::<Envelope>::arbitrary(u)?,
-                                body_structure: Box::new(make_body_structure_rec(u, depth - 1)?),
-                                number_of_lines: u32::arbitrary(u)?,
-                            },
-                            3 => SpecificFields::Text {
-                                subtype: IString::arbitrary(u)?,
-                                number_of_lines: u32::arbitrary(u)?,
-                            },
-                            _ => unreachable!(),
-                        },
-                    },
-                    extension_data: Option::<SinglePartExtensionData>::arbitrary(u)?,
+                if !bodies.is_empty() {
+                    Vec1::try_from(bodies).unwrap()
+                } else {
+                    Vec1::from(arbitrary_body_structure_leaf(u)?)
+                }
+            },
+            subtype: IString::arbitrary(u)?,
+            extension_data: Option::<MultiPartExtensionData>::arbitrary(u)?,
+        },
+        _ => unreachable!(),
+    })
+}
+
+fn arbitrary_body_structure_leaf<'a>(
+    u: &mut Unstructured<'a>,
+) -> arbitrary::Result<BodyStructure<'a>> {
+    Ok(BodyStructure::Single {
+        body: Body {
+            basic: BasicFields::arbitrary(u)?,
+            specific: match u.int_in_range(1..=2)? {
+                1 => SpecificFields::Basic {
+                    r#type: IString::arbitrary(u)?,
+                    subtype: IString::arbitrary(u)?,
                 },
-                2 => BodyStructure::Multi {
-                    bodies: {
-                        let bodies = {
-                            let len = u.arbitrary_len::<BodyStructure>()?;
-                            let mut tmp = Vec::with_capacity(len);
-
-                            for _ in 0..len {
-                                tmp.push(make_body_structure_rec(u, depth - 1)?);
-                            }
-
-                            tmp
-                        };
-
-                        if !bodies.is_empty() {
-                            Vec1::try_from(bodies).unwrap()
-                        } else {
-                            Vec1::from(make_body_structure_terminator(u)?)
-                        }
-                    },
+                // No SpecificFields::Message because it would recurse.
+                2 => SpecificFields::Text {
                     subtype: IString::arbitrary(u)?,
-                    extension_data: Option::<MultiPartExtensionData>::arbitrary(u)?,
+                    number_of_lines: u32::arbitrary(u)?,
                 },
                 _ => unreachable!(),
-            })
-        }
-
-        make_body_structure_rec(u, 3)
-    }
+            },
+        },
+        extension_data: Option::<SinglePartExtensionData>::arbitrary(u)?,
+    })
 }
 
 impl<'a> Arbitrary<'a> for BodyExtension<'a> {
     fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
-        fn make_body_extension_terminator<'a>(
-            u: &mut Unstructured<'a>,
-        ) -> arbitrary::Result<BodyExtension<'a>> {
-            Ok(match u.int_in_range(1..=2)? {
-                1 => BodyExtension::NString(NString::arbitrary(u)?),
-                2 => BodyExtension::Number(u32::arbitrary(u)?),
-                // No `BodyExtension::List` because it could recurse.
-                _ => unreachable!(),
-            })
-        }
+        #[cfg(not(feature = "arbitrary_simplified"))]
+        return arbitrary_body_extension_limited(u, 3);
+        #[cfg(feature = "arbitrary_simplified")]
+        return arbitrary_body_extension_leaf(u);
+    }
+}
 
-        fn make_body_extension_rec<'a>(
-            u: &mut Unstructured<'a>,
-            depth: u8,
-        ) -> arbitrary::Result<BodyExtension<'a>> {
-            if depth == 0 {
-                return make_body_extension_terminator(u);
-            }
+#[cfg(not(feature = "arbitrary_simplified"))]
+fn arbitrary_body_extension_limited<'a>(
+    u: &mut Unstructured<'a>,
+    depth: u8,
+) -> arbitrary::Result<BodyExtension<'a>> {
+    if depth == 0 {
+        return arbitrary_body_extension_leaf(u);
+    }
 
-            Ok(match u.int_in_range(1..=2)? {
-                1 => BodyExtension::NString(NString::arbitrary(u)?),
-                2 => BodyExtension::Number(u32::arbitrary(u)?),
-                3 => BodyExtension::List({
-                    let body_extensions = {
-                        let len = u.arbitrary_len::<BodyExtension>()?;
-                        let mut tmp = Vec::with_capacity(len);
+    Ok(match u.int_in_range(1..=2)? {
+        1 => BodyExtension::NString(NString::arbitrary(u)?),
+        2 => BodyExtension::Number(u32::arbitrary(u)?),
+        3 => BodyExtension::List({
+            let body_extensions = {
+                let len = u.arbitrary_len::<BodyExtension>()?;
+                let mut tmp = Vec::with_capacity(len);
 
-                        for _ in 0..len {
-                            tmp.push(make_body_extension_rec(u, depth - 1)?);
-                        }
+                for _ in 0..len {
+                    tmp.push(arbitrary_body_extension_limited(u, depth - 1)?);
+                }
 
-                        tmp
-                    };
+                tmp
+            };
 
-                    if !body_extensions.is_empty() {
-                        Vec1::try_from(body_extensions).unwrap()
-                    } else {
-                        Vec1::from(make_body_extension_terminator(u)?)
-                    }
-                }),
-                _ => unreachable!(),
-            })
-        }
+            if !body_extensions.is_empty() {
+                Vec1::try_from(body_extensions).unwrap()
+            } else {
+                Vec1::from(arbitrary_body_extension_leaf(u)?)
+            }
+        }),
+        _ => unreachable!(),
+    })
+}
 
-        make_body_extension_rec(u, 3)
-    }
+fn arbitrary_body_extension_leaf<'a>(
+    u: &mut Unstructured<'a>,
+) -> arbitrary::Result<BodyExtension<'a>> {
+    Ok(match u.int_in_range(1..=2)? {
+        1 => BodyExtension::NString(NString::arbitrary(u)?),
+        2 => BodyExtension::Number(u32::arbitrary(u)?),
+        // No `BodyExtension::List` because it could recurse.
+        _ => unreachable!(),
+    })
 }
 
 impl<'a> Arbitrary<'a> for DateTime {
@@ -472,40 +477,6 @@ impl<'a> Arbitrary<'a> for NaiveDate {
     }
 }
 
-#[cfg(feature = "ext_sort_thread")]
-impl<'a> Arbitrary<'a> for Thread {
-    fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
-        // We cheat a bit: Start from a leaf ...
-        let mut current = Thread::Members {
-            prefix: Arbitrary::arbitrary(u)?,
-            answers: None,
-        };
-
-        // ... and build up the thread to the top (with max depth == 8)
-        for _ in 0..7 {
-            match u.int_in_range(0..=2)? {
-                0 => {
-                    current = Thread::Members {
-                        prefix: Arbitrary::arbitrary(u)?,
-                        answers: Some(Vec2::unvalidated(vec![current.clone(), current])),
-                    };
-                }
-                1 => {
-                    current = Thread::Nested {
-                        answers: Vec2::unvalidated(vec![current.clone(), current]),
-                    };
-                }
-                2 => {
-                    return Ok(current);
-                }
-                _ => unreachable!(),
-            }
-        }
-
-        Ok(current)
-    }
-}
-
 #[cfg(test)]
 mod tests {
     use arbitrary::{Arbitrary, Error, Unstructured};
@@ -565,16 +536,16 @@ mod tests {
 
     #[test]
     fn test_arbitrary_greeting() {
-        impl_test_arbitrary! {Greeting};
+        impl_test_arbitrary! {Greeting}
     }
 
     #[test]
     fn test_arbitrary_command() {
-        impl_test_arbitrary! {Command};
+        impl_test_arbitrary! {Command}
     }
 
     #[test]
     fn test_arbitrary_response() {
-        impl_test_arbitrary! {Response};
+        impl_test_arbitrary! {Response}
     }
 }
diff --git a/imap-types/src/extensions/sort.rs b/imap-types/src/extensions/sort.rs
index c25abd5c..cbd32552 100644
--- a/imap-types/src/extensions/sort.rs
+++ b/imap-types/src/extensions/sort.rs
@@ -1,12 +1,14 @@
 use std::fmt::{Display, Formatter};
 
 #[cfg(feature = "arbitrary")]
-use arbitrary::Arbitrary;
+use arbitrary::{Arbitrary, Unstructured};
 #[cfg(feature = "bounded-static")]
 use bounded_static::ToStatic;
 #[cfg(feature = "serde")]
 use serde::{Deserialize, Serialize};
 
+#[cfg(feature = "arbitrary")]
+use crate::arbitrary::impl_arbitrary_try_from;
 use crate::core::Atom;
 
 #[cfg_attr(feature = "bounded-static", derive(ToStatic))]
@@ -35,6 +37,9 @@ impl Display for SortAlgorithm<'_> {
     }
 }
 
+#[cfg(feature = "arbitrary")]
+impl_arbitrary_try_from! { SortAlgorithm<'a>, Atom<'a> }
+
 #[cfg_attr(feature = "bounded-static", derive(ToStatic))]
 #[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
diff --git a/imap-types/src/extensions/thread.rs b/imap-types/src/extensions/thread.rs
index 741fb77b..5a336073 100644
--- a/imap-types/src/extensions/thread.rs
+++ b/imap-types/src/extensions/thread.rs
@@ -3,11 +3,15 @@ use std::{
     num::NonZeroU32,
 };
 
+#[cfg(feature = "arbitrary")]
+use arbitrary::{Arbitrary, Unstructured};
 #[cfg(feature = "bounded-static")]
 use bounded_static::ToStatic;
 #[cfg(feature = "serde")]
 use serde::{Deserialize, Serialize};
 
+#[cfg(feature = "arbitrary")]
+use crate::arbitrary::impl_arbitrary_try_from;
 use crate::core::{Atom, Vec1, Vec2};
 
 #[cfg_attr(feature = "bounded-static", derive(ToStatic))]
@@ -90,6 +94,56 @@ fn write_prefix(f: &mut Formatter, prefix: &Vec1<NonZeroU32>) -> std::fmt::Resul
     Ok(())
 }
 
+#[cfg(feature = "arbitrary")]
+impl<'a> Arbitrary<'a> for Thread {
+    fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
+        #[cfg(not(feature = "arbitrary_simplified"))]
+        return arbitrary_thread_limited(u, 7);
+        #[cfg(feature = "arbitrary_simplified")]
+        return arbitrary_thread_leaf(u);
+    }
+}
+
+#[cfg(all(feature = "arbitrary", not(feature = "arbitrary_simplified")))]
+fn arbitrary_thread_limited<'a>(
+    u: &mut Unstructured<'a>,
+    depth: usize,
+) -> arbitrary::Result<Thread> {
+    // We cheat a bit: Start from a leaf ...
+    let mut current = arbitrary_thread_leaf(u)?;
+
+    // ... and build up the thread to the top (with max depth == 8)
+    for _ in 0..depth {
+        match u.int_in_range(0..=2)? {
+            0 => {
+                current = Thread::Members {
+                    prefix: Arbitrary::arbitrary(u)?,
+                    answers: Some(Vec2::unvalidated(vec![current.clone(), current])),
+                };
+            }
+            1 => {
+                current = Thread::Nested {
+                    answers: Vec2::unvalidated(vec![current.clone(), current]),
+                };
+            }
+            2 => {
+                return Ok(current);
+            }
+            _ => unreachable!(),
+        }
+    }
+
+    Ok(current)
+}
+
+#[cfg(feature = "arbitrary")]
+fn arbitrary_thread_leaf<'a>(u: &mut Unstructured<'a>) -> arbitrary::Result<Thread> {
+    Ok(Thread::Members {
+        prefix: Arbitrary::arbitrary(u)?,
+        answers: None,
+    })
+}
+
 #[cfg_attr(feature = "bounded-static", derive(ToStatic))]
 #[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
@@ -119,6 +173,9 @@ impl Display for ThreadingAlgorithm<'_> {
     }
 }
 
+#[cfg(feature = "arbitrary")]
+impl_arbitrary_try_from! { ThreadingAlgorithm<'a>, Atom<'a> }
+
 #[cfg_attr(feature = "bounded-static", derive(ToStatic))]
 #[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]


Test patch:
diff --git a/.github/workflows/build_and_test.yml b/.github/workflows/build_and_test.yml
index 6ece8ad0..23da2e27 100644
--- a/.github/workflows/build_and_test.yml
+++ b/.github/workflows/build_and_test.yml
@@ -100,7 +100,7 @@ jobs:
           for fuzz_target in $(cargo +nightly fuzz list);
           do
           echo "# Fuzzing ${fuzz_target}";
-          cargo +nightly fuzz run --features=ext ${fuzz_target} -- -dict=fuzz/terminals.dict -max_len=256 -only_ascii=1 -runs=25000
+          cargo +nightly fuzz run --features=ext,arbitrary_simplified ${fuzz_target} -- -dict=fuzz/terminals.dict -max_len=256 -only_ascii=1 -runs=25000
           done
 
   minimal-versions: