arbitrary/
lib.rs

1// Copyright © 2019 The Rust Fuzz Project Developers.
2//
3// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
4// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
5// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
6// option. This file may not be copied, modified, or distributed
7// except according to those terms.
8
9//! The `Arbitrary` trait crate.
10//!
11//! This trait provides an [`Arbitrary`](./trait.Arbitrary.html) trait to
12//! produce well-typed, structured values, from raw, byte buffers. It is
13//! generally intended to be used with fuzzers like AFL or libFuzzer. See the
14//! [`Arbitrary`](./trait.Arbitrary.html) trait's documentation for details on
15//! automatically deriving, implementing, and/or using the trait.
16
17#![deny(bad_style)]
18#![deny(missing_docs)]
19#![deny(future_incompatible)]
20#![deny(nonstandard_style)]
21#![deny(rust_2018_compatibility)]
22#![deny(rust_2018_idioms)]
23#![deny(unused)]
24
25#[cfg(feature = "derive_arbitrary")]
26pub use derive_arbitrary::*;
27
28mod error;
29pub use error::*;
30
31pub mod unstructured;
32#[doc(inline)]
33pub use unstructured::Unstructured;
34
35pub mod size_hint;
36
37use core::cell::{Cell, RefCell, UnsafeCell};
38use core::iter;
39use core::mem;
40use core::num::{NonZeroI128, NonZeroI16, NonZeroI32, NonZeroI64, NonZeroI8, NonZeroIsize};
41use core::num::{NonZeroU128, NonZeroU16, NonZeroU32, NonZeroU64, NonZeroU8, NonZeroUsize};
42use core::ops::{Range, RangeBounds, RangeFrom, RangeInclusive, RangeTo, RangeToInclusive};
43use core::str;
44use core::time::Duration;
45use std::borrow::{Cow, ToOwned};
46use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque};
47use std::ffi::{CString, OsString};
48use std::hash::BuildHasher;
49use std::net::{Ipv4Addr, Ipv6Addr};
50use std::path::PathBuf;
51use std::rc::Rc;
52use std::sync::atomic::{AtomicBool, AtomicIsize, AtomicUsize};
53use std::sync::{Arc, Mutex};
54
55/// Generate arbitrary structured values from raw, unstructured data.
56///
57/// The `Arbitrary` trait allows you to generate valid structured values, like
58/// `HashMap`s, or ASTs, or `MyTomlConfig`, or any other data structure from
59/// raw, unstructured bytes provided by a fuzzer.
60///
61/// # Deriving `Arbitrary`
62///
63/// Automatically deriving the `Arbitrary` trait is the recommended way to
64/// implement `Arbitrary` for your types.
65///
66/// Using the custom derive requires that you enable the `"derive"` cargo
67/// feature in your `Cargo.toml`:
68///
69/// ```toml
70/// [dependencies]
71/// arbitrary = { version = "1", features = ["derive"] }
72/// ```
73///
74/// Then, you add the `#[derive(Arbitrary)]` annotation to your `struct` or
75/// `enum` type definition:
76///
77/// ```
78/// # #[cfg(feature = "derive")] mod foo {
79/// use arbitrary::Arbitrary;
80/// use std::collections::HashSet;
81///
82/// #[derive(Arbitrary)]
83/// pub struct AddressBook {
84///     friends: HashSet<Friend>,
85/// }
86///
87/// #[derive(Arbitrary, Hash, Eq, PartialEq)]
88/// pub enum Friend {
89///     Buddy { name: String },
90///     Pal { age: usize },
91/// }
92/// # }
93/// ```
94///
95/// Every member of the `struct` or `enum` must also implement `Arbitrary`.
96///
97/// # Implementing `Arbitrary` By Hand
98///
99/// Implementing `Arbitrary` mostly involves nested calls to other `Arbitrary`
100/// arbitrary implementations for each of your `struct` or `enum`'s members. But
101/// sometimes you need some amount of raw data, or you need to generate a
102/// variably-sized collection type, or something of that sort. The
103/// [`Unstructured`][crate::Unstructured] type helps you with these tasks.
104///
105/// ```
106/// # #[cfg(feature = "derive")] mod foo {
107/// # pub struct MyCollection<T> { _t: std::marker::PhantomData<T> }
108/// # impl<T> MyCollection<T> {
109/// #     pub fn new() -> Self { MyCollection { _t: std::marker::PhantomData } }
110/// #     pub fn insert(&mut self, element: T) {}
111/// # }
112/// use arbitrary::{Arbitrary, Result, Unstructured};
113///
114/// impl<'a, T> Arbitrary<'a> for MyCollection<T>
115/// where
116///     T: Arbitrary<'a>,
117/// {
118///     fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
119///         // Get an iterator of arbitrary `T`s.
120///         let iter = u.arbitrary_iter::<T>()?;
121///
122///         // And then create a collection!
123///         let mut my_collection = MyCollection::new();
124///         for elem_result in iter {
125///             let elem = elem_result?;
126///             my_collection.insert(elem);
127///         }
128///
129///         Ok(my_collection)
130///     }
131/// }
132/// # }
133/// ```
134pub trait Arbitrary<'a>: Sized {
135    /// Generate an arbitrary value of `Self` from the given unstructured data.
136    ///
137    /// Calling `Arbitrary::arbitrary` requires that you have some raw data,
138    /// perhaps given to you by a fuzzer like AFL or libFuzzer. You wrap this
139    /// raw data in an `Unstructured`, and then you can call `<MyType as
140    /// Arbitrary>::arbitrary` to construct an arbitrary instance of `MyType`
141    /// from that unstuctured data.
142    ///
143    /// Implementation may return an error if there is not enough data to
144    /// construct a full instance of `Self`. This is generally OK: it is better
145    /// to exit early and get the fuzzer to provide more input data, than it is
146    /// to generate default values in place of the missing data, which would
147    /// bias the distribution of generated values, and ultimately make fuzzing
148    /// less efficient.
149    ///
150    /// ```
151    /// # #[cfg(feature = "derive")] fn foo() {
152    /// use arbitrary::{Arbitrary, Unstructured};
153    ///
154    /// #[derive(Arbitrary)]
155    /// pub struct MyType {
156    ///     // ...
157    /// }
158    ///
159    /// // Get the raw data from the fuzzer or wherever else.
160    /// # let get_raw_data_from_fuzzer = || &[];
161    /// let raw_data: &[u8] = get_raw_data_from_fuzzer();
162    ///
163    /// // Wrap that raw data in an `Unstructured`.
164    /// let mut unstructured = Unstructured::new(raw_data);
165    ///
166    /// // Generate an arbitrary instance of `MyType` and do stuff with it.
167    /// if let Ok(value) = MyType::arbitrary(&mut unstructured) {
168    /// #   let do_stuff = |_| {};
169    ///     do_stuff(value);
170    /// }
171    /// # }
172    /// ```
173    ///
174    /// See also the documentation for [`Unstructured`][crate::Unstructured].
175    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self>;
176
177    /// Generate an arbitrary value of `Self` from the entirety of the given unstructured data.
178    ///
179    /// This is similar to Arbitrary::arbitrary, however it assumes that it is the
180    /// last consumer of the given data, and is thus able to consume it all if it needs.
181    /// See also the documentation for [`Unstructured`][crate::Unstructured].
182    fn arbitrary_take_rest(mut u: Unstructured<'a>) -> Result<Self> {
183        Self::arbitrary(&mut u)
184    }
185
186    /// Get a size hint for how many bytes out of an `Unstructured` this type
187    /// needs to construct itself.
188    ///
189    /// This is useful for determining how many elements we should insert when
190    /// creating an arbitrary collection.
191    ///
192    /// The return value is similar to
193    /// [`Iterator::size_hint`][iterator-size-hint]: it returns a tuple where
194    /// the first element is a lower bound on the number of bytes required, and
195    /// the second element is an optional upper bound.
196    ///
197    /// The default implementation return `(0, None)` which is correct for any
198    /// type, but not ultimately that useful. Using `#[derive(Arbitrary)]` will
199    /// create a better implementation. If you are writing an `Arbitrary`
200    /// implementation by hand, and your type can be part of a dynamically sized
201    /// collection (such as `Vec`), you are strongly encouraged to override this
202    /// default with a better implementation. The
203    /// [`size_hint`][crate::size_hint] module will help with this task.
204    ///
205    /// ## The `depth` Parameter
206    ///
207    /// If you 100% know that the type you are implementing `Arbitrary` for is
208    /// not a recursive type, or your implementation is not transitively calling
209    /// any other `size_hint` methods, you can ignore the `depth` parameter.
210    /// Note that if you are implementing `Arbitrary` for a generic type, you
211    /// cannot guarantee the lack of type recursion!
212    ///
213    /// Otherwise, you need to use
214    /// [`arbitrary::size_hint::recursion_guard(depth)`][crate::size_hint::recursion_guard]
215    /// to prevent potential infinite recursion when calculating size hints for
216    /// potentially recursive types:
217    ///
218    /// ```
219    /// use arbitrary::{Arbitrary, Unstructured, size_hint};
220    ///
221    /// // This can potentially be a recursive type if `L` or `R` contain
222    /// // something like `Box<Option<MyEither<L, R>>>`!
223    /// enum MyEither<L, R> {
224    ///     Left(L),
225    ///     Right(R),
226    /// }
227    ///
228    /// impl<'a, L, R> Arbitrary<'a> for MyEither<L, R>
229    /// where
230    ///     L: Arbitrary<'a>,
231    ///     R: Arbitrary<'a>,
232    /// {
233    ///     fn arbitrary(u: &mut Unstructured) -> arbitrary::Result<Self> {
234    ///         // ...
235    /// #       unimplemented!()
236    ///     }
237    ///
238    ///     fn size_hint(depth: usize) -> (usize, Option<usize>) {
239    ///         // Protect against potential infinite recursion with
240    ///         // `recursion_guard`.
241    ///         size_hint::recursion_guard(depth, |depth| {
242    ///             // If we aren't too deep, then `recursion_guard` calls
243    ///             // this closure, which implements the natural size hint.
244    ///             // Don't forget to use the new `depth` in all nested
245    ///             // `size_hint` calls! We recommend shadowing the
246    ///             // parameter, like what is done here, so that you can't
247    ///             // accidentally use the wrong depth.
248    ///             size_hint::or(
249    ///                 <L as Arbitrary>::size_hint(depth),
250    ///                 <R as Arbitrary>::size_hint(depth),
251    ///             )
252    ///         })
253    ///     }
254    /// }
255    /// ```
256    ///
257    /// [iterator-size-hint]: https://doc.rust-lang.org/stable/std/iter/trait.Iterator.html#method.size_hint
258    #[inline]
259    fn size_hint(depth: usize) -> (usize, Option<usize>) {
260        let _ = depth;
261        (0, None)
262    }
263}
264
265impl<'a> Arbitrary<'a> for () {
266    fn arbitrary(_: &mut Unstructured<'a>) -> Result<Self> {
267        Ok(())
268    }
269
270    #[inline]
271    fn size_hint(_depth: usize) -> (usize, Option<usize>) {
272        (0, Some(0))
273    }
274}
275
276impl<'a> Arbitrary<'a> for bool {
277    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
278        Ok(<u8 as Arbitrary<'a>>::arbitrary(u)? & 1 == 1)
279    }
280
281    #[inline]
282    fn size_hint(depth: usize) -> (usize, Option<usize>) {
283        <u8 as Arbitrary<'a>>::size_hint(depth)
284    }
285}
286
287macro_rules! impl_arbitrary_for_integers {
288    ( $( $ty:ty: $unsigned:ty; )* ) => {
289        $(
290            impl<'a> Arbitrary<'a> for $ty {
291                fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
292                    let mut buf = [0; mem::size_of::<$ty>()];
293                    u.fill_buffer(&mut buf)?;
294                    let mut x: $unsigned = 0;
295                    for i in 0..mem::size_of::<$ty>() {
296                        x |= buf[i] as $unsigned << (i * 8);
297                    }
298                    Ok(x as $ty)
299                }
300
301                #[inline]
302                fn size_hint(_depth: usize) -> (usize, Option<usize>) {
303                    let n = mem::size_of::<$ty>();
304                    (n, Some(n))
305                }
306
307            }
308        )*
309    }
310}
311
312impl_arbitrary_for_integers! {
313    u8: u8;
314    u16: u16;
315    u32: u32;
316    u64: u64;
317    u128: u128;
318    usize: usize;
319    i8: u8;
320    i16: u16;
321    i32: u32;
322    i64: u64;
323    i128: u128;
324    isize: usize;
325}
326
327macro_rules! impl_arbitrary_for_floats {
328    ( $( $ty:ident : $unsigned:ty; )* ) => {
329        $(
330            impl<'a> Arbitrary<'a> for $ty {
331                fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
332                    Ok(Self::from_bits(<$unsigned as Arbitrary<'a>>::arbitrary(u)?))
333                }
334
335                #[inline]
336                fn size_hint(depth: usize) -> (usize, Option<usize>) {
337                    <$unsigned as Arbitrary<'a>>::size_hint(depth)
338                }
339            }
340        )*
341    }
342}
343
344impl_arbitrary_for_floats! {
345    f32: u32;
346    f64: u64;
347}
348
349impl<'a> Arbitrary<'a> for char {
350    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
351        use std::char;
352        // The highest unicode code point is 0x11_FFFF
353        const CHAR_END: u32 = 0x11_0000;
354        // The size of the surrogate blocks
355        const SURROGATES_START: u32 = 0xD800;
356        let mut c = <u32 as Arbitrary<'a>>::arbitrary(u)? % CHAR_END;
357        if let Some(c) = char::from_u32(c) {
358            Ok(c)
359        } else {
360            // We found a surrogate, wrap and try again
361            c -= SURROGATES_START;
362            Ok(char::from_u32(c)
363                .expect("Generated character should be valid! This is a bug in arbitrary-rs"))
364        }
365    }
366
367    #[inline]
368    fn size_hint(depth: usize) -> (usize, Option<usize>) {
369        <u32 as Arbitrary<'a>>::size_hint(depth)
370    }
371}
372
373impl<'a> Arbitrary<'a> for AtomicBool {
374    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
375        Arbitrary::arbitrary(u).map(Self::new)
376    }
377
378    #[inline]
379    fn size_hint(depth: usize) -> (usize, Option<usize>) {
380        <bool as Arbitrary<'a>>::size_hint(depth)
381    }
382}
383
384impl<'a> Arbitrary<'a> for AtomicIsize {
385    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
386        Arbitrary::arbitrary(u).map(Self::new)
387    }
388
389    #[inline]
390    fn size_hint(depth: usize) -> (usize, Option<usize>) {
391        <isize as Arbitrary<'a>>::size_hint(depth)
392    }
393}
394
395impl<'a> Arbitrary<'a> for AtomicUsize {
396    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
397        Arbitrary::arbitrary(u).map(Self::new)
398    }
399
400    #[inline]
401    fn size_hint(depth: usize) -> (usize, Option<usize>) {
402        <usize as Arbitrary<'a>>::size_hint(depth)
403    }
404}
405
406macro_rules! impl_range {
407    (
408        $range:ty,
409        $value_closure:expr,
410        $value_ty:ty,
411        $fun:ident($fun_closure:expr),
412        $size_hint_closure:expr
413    ) => {
414        impl<'a, A> Arbitrary<'a> for $range
415        where
416            A: Arbitrary<'a> + Clone + PartialOrd,
417        {
418            fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
419                let value: $value_ty = Arbitrary::arbitrary(u)?;
420                Ok($fun(value, $fun_closure))
421            }
422
423            #[inline]
424            fn size_hint(depth: usize) -> (usize, Option<usize>) {
425                $size_hint_closure(depth)
426            }
427        }
428    };
429}
430
431impl_range!(
432    Range<A>,
433    |r: &Range<A>| (r.start.clone(), r.end.clone()),
434    (A, A),
435    bounded_range(|(a, b)| a..b),
436    |depth| crate::size_hint::and(
437        <A as Arbitrary>::size_hint(depth),
438        <A as Arbitrary>::size_hint(depth)
439    )
440);
441impl_range!(
442    RangeFrom<A>,
443    |r: &RangeFrom<A>| r.start.clone(),
444    A,
445    unbounded_range(|a| a..),
446    |depth| <A as Arbitrary>::size_hint(depth)
447);
448impl_range!(
449    RangeInclusive<A>,
450    |r: &RangeInclusive<A>| (r.start().clone(), r.end().clone()),
451    (A, A),
452    bounded_range(|(a, b)| a..=b),
453    |depth| crate::size_hint::and(
454        <A as Arbitrary>::size_hint(depth),
455        <A as Arbitrary>::size_hint(depth)
456    )
457);
458impl_range!(
459    RangeTo<A>,
460    |r: &RangeTo<A>| r.end.clone(),
461    A,
462    unbounded_range(|b| ..b),
463    |depth| <A as Arbitrary>::size_hint(depth)
464);
465impl_range!(
466    RangeToInclusive<A>,
467    |r: &RangeToInclusive<A>| r.end.clone(),
468    A,
469    unbounded_range(|b| ..=b),
470    |depth| <A as Arbitrary>::size_hint(depth)
471);
472
473pub(crate) fn bounded_range<CB, I, R>(bounds: (I, I), cb: CB) -> R
474where
475    CB: Fn((I, I)) -> R,
476    I: PartialOrd,
477    R: RangeBounds<I>,
478{
479    let (mut start, mut end) = bounds;
480    if start > end {
481        mem::swap(&mut start, &mut end);
482    }
483    cb((start, end))
484}
485
486pub(crate) fn unbounded_range<CB, I, R>(bound: I, cb: CB) -> R
487where
488    CB: Fn(I) -> R,
489    R: RangeBounds<I>,
490{
491    cb(bound)
492}
493
494impl<'a> Arbitrary<'a> for Duration {
495    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
496        Ok(Self::new(
497            <u64 as Arbitrary>::arbitrary(u)?,
498            u.int_in_range(0..=999_999_999)?,
499        ))
500    }
501
502    #[inline]
503    fn size_hint(depth: usize) -> (usize, Option<usize>) {
504        crate::size_hint::and(
505            <u64 as Arbitrary>::size_hint(depth),
506            <u32 as Arbitrary>::size_hint(depth),
507        )
508    }
509}
510
511impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for Option<A> {
512    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
513        Ok(if <bool as Arbitrary<'a>>::arbitrary(u)? {
514            Some(Arbitrary::arbitrary(u)?)
515        } else {
516            None
517        })
518    }
519
520    #[inline]
521    fn size_hint(depth: usize) -> (usize, Option<usize>) {
522        crate::size_hint::and(
523            <bool as Arbitrary>::size_hint(depth),
524            crate::size_hint::or((0, Some(0)), <A as Arbitrary>::size_hint(depth)),
525        )
526    }
527}
528
529impl<'a, A: Arbitrary<'a>, B: Arbitrary<'a>> Arbitrary<'a> for std::result::Result<A, B> {
530    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
531        Ok(if <bool as Arbitrary<'a>>::arbitrary(u)? {
532            Ok(<A as Arbitrary>::arbitrary(u)?)
533        } else {
534            Err(<B as Arbitrary>::arbitrary(u)?)
535        })
536    }
537
538    #[inline]
539    fn size_hint(depth: usize) -> (usize, Option<usize>) {
540        crate::size_hint::and(
541            <bool as Arbitrary>::size_hint(depth),
542            crate::size_hint::or(
543                <A as Arbitrary>::size_hint(depth),
544                <B as Arbitrary>::size_hint(depth),
545            ),
546        )
547    }
548}
549
550macro_rules! arbitrary_tuple {
551    () => {};
552    ($last: ident $($xs: ident)*) => {
553        arbitrary_tuple!($($xs)*);
554
555        impl<'a, $($xs: Arbitrary<'a>,)* $last: Arbitrary<'a>> Arbitrary<'a> for ($($xs,)* $last,) {
556            fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
557                Ok(($($xs::arbitrary(u)?,)* Arbitrary::arbitrary(u)?,))
558            }
559
560            #[allow(unused_mut, non_snake_case)]
561            fn arbitrary_take_rest(mut u: Unstructured<'a>) -> Result<Self> {
562                $(let $xs = $xs::arbitrary(&mut u)?;)*
563                let $last = $last::arbitrary_take_rest(u)?;
564                Ok(($($xs,)* $last,))
565            }
566
567            #[inline]
568            fn size_hint(depth: usize) -> (usize, Option<usize>) {
569                crate::size_hint::and_all(&[
570                    <$last as Arbitrary>::size_hint(depth),
571                    $( <$xs as Arbitrary>::size_hint(depth) ),*
572                ])
573            }
574        }
575    };
576}
577arbitrary_tuple!(A B C D E F G H I J K L M N O P Q R S T U V W X Y Z);
578
579// Helper to safely create arrays since the standard library doesn't
580// provide one yet. Shouldn't be necessary in the future.
581struct ArrayGuard<T, const N: usize> {
582    dst: *mut T,
583    initialized: usize,
584}
585
586impl<T, const N: usize> Drop for ArrayGuard<T, N> {
587    fn drop(&mut self) {
588        debug_assert!(self.initialized <= N);
589        let initialized_part = core::ptr::slice_from_raw_parts_mut(self.dst, self.initialized);
590        unsafe {
591            core::ptr::drop_in_place(initialized_part);
592        }
593    }
594}
595
596fn create_array<F, T, const N: usize>(mut cb: F) -> [T; N]
597where
598    F: FnMut(usize) -> T,
599{
600    let mut array: mem::MaybeUninit<[T; N]> = mem::MaybeUninit::uninit();
601    let array_ptr = array.as_mut_ptr();
602    let dst = array_ptr as _;
603    let mut guard: ArrayGuard<T, N> = ArrayGuard {
604        dst,
605        initialized: 0,
606    };
607    unsafe {
608        for (idx, value_ptr) in (&mut *array.as_mut_ptr()).iter_mut().enumerate() {
609            core::ptr::write(value_ptr, cb(idx));
610            guard.initialized += 1;
611        }
612        mem::forget(guard);
613        array.assume_init()
614    }
615}
616
617fn try_create_array<F, T, const N: usize>(mut cb: F) -> Result<[T; N]>
618where
619    F: FnMut(usize) -> Result<T>,
620{
621    let mut array: mem::MaybeUninit<[T; N]> = mem::MaybeUninit::uninit();
622    let array_ptr = array.as_mut_ptr();
623    let dst = array_ptr as _;
624    let mut guard: ArrayGuard<T, N> = ArrayGuard {
625        dst,
626        initialized: 0,
627    };
628    unsafe {
629        for (idx, value_ptr) in (&mut *array.as_mut_ptr()).iter_mut().enumerate() {
630            core::ptr::write(value_ptr, cb(idx)?);
631            guard.initialized += 1;
632        }
633        mem::forget(guard);
634        Ok(array.assume_init())
635    }
636}
637
638impl<'a, T, const N: usize> Arbitrary<'a> for [T; N]
639where
640    T: Arbitrary<'a>,
641{
642    #[inline]
643    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
644        try_create_array(|_| <T as Arbitrary<'a>>::arbitrary(u))
645    }
646
647    #[inline]
648    fn arbitrary_take_rest(mut u: Unstructured<'a>) -> Result<Self> {
649        let mut array = Self::arbitrary(&mut u)?;
650        if let Some(last) = array.last_mut() {
651            *last = Arbitrary::arbitrary_take_rest(u)?;
652        }
653        Ok(array)
654    }
655
656    #[inline]
657    fn size_hint(d: usize) -> (usize, Option<usize>) {
658        crate::size_hint::and_all(&create_array::<_, (usize, Option<usize>), N>(|_| {
659            <T as Arbitrary>::size_hint(d)
660        }))
661    }
662}
663
664impl<'a> Arbitrary<'a> for &'a [u8] {
665    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
666        let len = u.arbitrary_len::<u8>()?;
667        u.bytes(len)
668    }
669
670    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
671        Ok(u.take_rest())
672    }
673
674    #[inline]
675    fn size_hint(depth: usize) -> (usize, Option<usize>) {
676        <usize as Arbitrary>::size_hint(depth)
677    }
678}
679
680impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for Vec<A> {
681    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
682        u.arbitrary_iter()?.collect()
683    }
684
685    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
686        u.arbitrary_take_rest_iter()?.collect()
687    }
688
689    #[inline]
690    fn size_hint(depth: usize) -> (usize, Option<usize>) {
691        crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
692    }
693}
694
695impl<'a, K: Arbitrary<'a> + Ord, V: Arbitrary<'a>> Arbitrary<'a> for BTreeMap<K, V> {
696    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
697        u.arbitrary_iter()?.collect()
698    }
699
700    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
701        u.arbitrary_take_rest_iter()?.collect()
702    }
703
704    #[inline]
705    fn size_hint(depth: usize) -> (usize, Option<usize>) {
706        crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
707    }
708}
709
710impl<'a, A: Arbitrary<'a> + Ord> Arbitrary<'a> for BTreeSet<A> {
711    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
712        u.arbitrary_iter()?.collect()
713    }
714
715    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
716        u.arbitrary_take_rest_iter()?.collect()
717    }
718
719    #[inline]
720    fn size_hint(depth: usize) -> (usize, Option<usize>) {
721        crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
722    }
723}
724
725impl<'a, A: Arbitrary<'a> + Ord> Arbitrary<'a> for BinaryHeap<A> {
726    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
727        u.arbitrary_iter()?.collect()
728    }
729
730    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
731        u.arbitrary_take_rest_iter()?.collect()
732    }
733
734    #[inline]
735    fn size_hint(depth: usize) -> (usize, Option<usize>) {
736        crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
737    }
738}
739
740impl<'a, K: Arbitrary<'a> + Eq + ::std::hash::Hash, V: Arbitrary<'a>, S: BuildHasher + Default>
741    Arbitrary<'a> for HashMap<K, V, S>
742{
743    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
744        u.arbitrary_iter()?.collect()
745    }
746
747    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
748        u.arbitrary_take_rest_iter()?.collect()
749    }
750
751    #[inline]
752    fn size_hint(depth: usize) -> (usize, Option<usize>) {
753        crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
754    }
755}
756
757impl<'a, A: Arbitrary<'a> + Eq + ::std::hash::Hash, S: BuildHasher + Default> Arbitrary<'a>
758    for HashSet<A, S>
759{
760    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
761        u.arbitrary_iter()?.collect()
762    }
763
764    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
765        u.arbitrary_take_rest_iter()?.collect()
766    }
767
768    #[inline]
769    fn size_hint(depth: usize) -> (usize, Option<usize>) {
770        crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
771    }
772}
773
774impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for LinkedList<A> {
775    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
776        u.arbitrary_iter()?.collect()
777    }
778
779    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
780        u.arbitrary_take_rest_iter()?.collect()
781    }
782
783    #[inline]
784    fn size_hint(depth: usize) -> (usize, Option<usize>) {
785        crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
786    }
787}
788
789impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for VecDeque<A> {
790    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
791        u.arbitrary_iter()?.collect()
792    }
793
794    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
795        u.arbitrary_take_rest_iter()?.collect()
796    }
797
798    #[inline]
799    fn size_hint(depth: usize) -> (usize, Option<usize>) {
800        crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
801    }
802}
803
804impl<'a, A> Arbitrary<'a> for Cow<'a, A>
805where
806    A: ToOwned + ?Sized,
807    <A as ToOwned>::Owned: Arbitrary<'a>,
808{
809    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
810        Arbitrary::arbitrary(u).map(Cow::Owned)
811    }
812
813    #[inline]
814    fn size_hint(depth: usize) -> (usize, Option<usize>) {
815        crate::size_hint::recursion_guard(depth, |depth| {
816            <<A as ToOwned>::Owned as Arbitrary>::size_hint(depth)
817        })
818    }
819}
820
821impl<'a> Arbitrary<'a> for &'a str {
822    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
823        let size = u.arbitrary_len::<u8>()?;
824        match str::from_utf8(&u.peek_bytes(size).unwrap()) {
825            Ok(s) => {
826                u.bytes(size).unwrap();
827                Ok(s)
828            }
829            Err(e) => {
830                let i = e.valid_up_to();
831                let valid = u.bytes(i).unwrap();
832                let s = unsafe {
833                    debug_assert!(str::from_utf8(valid).is_ok());
834                    str::from_utf8_unchecked(valid)
835                };
836                Ok(s)
837            }
838        }
839    }
840
841    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
842        let bytes = u.take_rest();
843        str::from_utf8(bytes)
844            .map_err(|_| Error::IncorrectFormat)
845            .map(Into::into)
846    }
847
848    #[inline]
849    fn size_hint(depth: usize) -> (usize, Option<usize>) {
850        crate::size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
851    }
852}
853
854impl<'a> Arbitrary<'a> for String {
855    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
856        <&str as Arbitrary>::arbitrary(u).map(Into::into)
857    }
858
859    fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> {
860        <&str as Arbitrary>::arbitrary_take_rest(u).map(Into::into)
861    }
862
863    #[inline]
864    fn size_hint(depth: usize) -> (usize, Option<usize>) {
865        <&str as Arbitrary>::size_hint(depth)
866    }
867}
868
869impl<'a> Arbitrary<'a> for CString {
870    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
871        <Vec<u8> as Arbitrary>::arbitrary(u).map(|mut x| {
872            x.retain(|&c| c != 0);
873            Self::new(x).unwrap()
874        })
875    }
876
877    #[inline]
878    fn size_hint(depth: usize) -> (usize, Option<usize>) {
879        <Vec<u8> as Arbitrary>::size_hint(depth)
880    }
881}
882
883impl<'a> Arbitrary<'a> for OsString {
884    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
885        <String as Arbitrary>::arbitrary(u).map(From::from)
886    }
887
888    #[inline]
889    fn size_hint(depth: usize) -> (usize, Option<usize>) {
890        <String as Arbitrary>::size_hint(depth)
891    }
892}
893
894impl<'a> Arbitrary<'a> for PathBuf {
895    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
896        <OsString as Arbitrary>::arbitrary(u).map(From::from)
897    }
898
899    #[inline]
900    fn size_hint(depth: usize) -> (usize, Option<usize>) {
901        <OsString as Arbitrary>::size_hint(depth)
902    }
903}
904
905impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for Box<A> {
906    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
907        Arbitrary::arbitrary(u).map(Self::new)
908    }
909
910    #[inline]
911    fn size_hint(depth: usize) -> (usize, Option<usize>) {
912        crate::size_hint::recursion_guard(depth, <A as Arbitrary>::size_hint)
913    }
914}
915
916impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for Box<[A]> {
917    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
918        <Vec<A> as Arbitrary>::arbitrary(u).map(|x| x.into_boxed_slice())
919    }
920
921    #[inline]
922    fn size_hint(depth: usize) -> (usize, Option<usize>) {
923        <Vec<A> as Arbitrary>::size_hint(depth)
924    }
925}
926
927impl<'a> Arbitrary<'a> for Box<str> {
928    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
929        <String as Arbitrary>::arbitrary(u).map(|x| x.into_boxed_str())
930    }
931
932    #[inline]
933    fn size_hint(depth: usize) -> (usize, Option<usize>) {
934        <String as Arbitrary>::size_hint(depth)
935    }
936}
937
938// impl Arbitrary for Box<CStr> {
939//     fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
940//         <CString as Arbitrary>::arbitrary(u).map(|x| x.into_boxed_c_str())
941//     }
942// }
943
944// impl Arbitrary for Box<OsStr> {
945//     fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
946//         <OsString as Arbitrary>::arbitrary(u).map(|x| x.into_boxed_osstr())
947//
948//     }
949// }
950
951impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for Arc<A> {
952    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
953        Arbitrary::arbitrary(u).map(Self::new)
954    }
955
956    #[inline]
957    fn size_hint(depth: usize) -> (usize, Option<usize>) {
958        crate::size_hint::recursion_guard(depth, <A as Arbitrary>::size_hint)
959    }
960}
961
962impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for Rc<A> {
963    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
964        Arbitrary::arbitrary(u).map(Self::new)
965    }
966
967    #[inline]
968    fn size_hint(depth: usize) -> (usize, Option<usize>) {
969        crate::size_hint::recursion_guard(depth, <A as Arbitrary>::size_hint)
970    }
971}
972
973impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for Cell<A> {
974    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
975        Arbitrary::arbitrary(u).map(Self::new)
976    }
977
978    #[inline]
979    fn size_hint(depth: usize) -> (usize, Option<usize>) {
980        <A as Arbitrary<'a>>::size_hint(depth)
981    }
982}
983
984impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for RefCell<A> {
985    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
986        Arbitrary::arbitrary(u).map(Self::new)
987    }
988
989    #[inline]
990    fn size_hint(depth: usize) -> (usize, Option<usize>) {
991        <A as Arbitrary<'a>>::size_hint(depth)
992    }
993}
994
995impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for UnsafeCell<A> {
996    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
997        Arbitrary::arbitrary(u).map(Self::new)
998    }
999
1000    #[inline]
1001    fn size_hint(depth: usize) -> (usize, Option<usize>) {
1002        <A as Arbitrary<'a>>::size_hint(depth)
1003    }
1004}
1005
1006impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for Mutex<A> {
1007    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
1008        Arbitrary::arbitrary(u).map(Self::new)
1009    }
1010
1011    #[inline]
1012    fn size_hint(depth: usize) -> (usize, Option<usize>) {
1013        <A as Arbitrary<'a>>::size_hint(depth)
1014    }
1015}
1016
1017impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for iter::Empty<A> {
1018    fn arbitrary(_: &mut Unstructured<'a>) -> Result<Self> {
1019        Ok(iter::empty())
1020    }
1021
1022    #[inline]
1023    fn size_hint(_depth: usize) -> (usize, Option<usize>) {
1024        (0, Some(0))
1025    }
1026}
1027
1028impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for ::std::marker::PhantomData<A> {
1029    fn arbitrary(_: &mut Unstructured<'a>) -> Result<Self> {
1030        Ok(::std::marker::PhantomData)
1031    }
1032
1033    #[inline]
1034    fn size_hint(_depth: usize) -> (usize, Option<usize>) {
1035        (0, Some(0))
1036    }
1037}
1038
1039impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for ::std::num::Wrapping<A> {
1040    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
1041        Arbitrary::arbitrary(u).map(::std::num::Wrapping)
1042    }
1043
1044    #[inline]
1045    fn size_hint(depth: usize) -> (usize, Option<usize>) {
1046        <A as Arbitrary<'a>>::size_hint(depth)
1047    }
1048}
1049
1050macro_rules! implement_nonzero_int {
1051    ($nonzero:ty, $int:ty) => {
1052        impl<'a> Arbitrary<'a> for $nonzero {
1053            fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
1054                match Self::new(<$int as Arbitrary<'a>>::arbitrary(u)?) {
1055                    Some(n) => Ok(n),
1056                    None => Err(Error::IncorrectFormat),
1057                }
1058            }
1059
1060            #[inline]
1061            fn size_hint(depth: usize) -> (usize, Option<usize>) {
1062                <$int as Arbitrary<'a>>::size_hint(depth)
1063            }
1064        }
1065    };
1066}
1067
1068implement_nonzero_int! { NonZeroI8, i8 }
1069implement_nonzero_int! { NonZeroI16, i16 }
1070implement_nonzero_int! { NonZeroI32, i32 }
1071implement_nonzero_int! { NonZeroI64, i64 }
1072implement_nonzero_int! { NonZeroI128, i128 }
1073implement_nonzero_int! { NonZeroIsize, isize }
1074implement_nonzero_int! { NonZeroU8, u8 }
1075implement_nonzero_int! { NonZeroU16, u16 }
1076implement_nonzero_int! { NonZeroU32, u32 }
1077implement_nonzero_int! { NonZeroU64, u64 }
1078implement_nonzero_int! { NonZeroU128, u128 }
1079implement_nonzero_int! { NonZeroUsize, usize }
1080
1081impl<'a> Arbitrary<'a> for Ipv4Addr {
1082    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
1083        Ok(Ipv4Addr::from(u32::arbitrary(u)?))
1084    }
1085
1086    #[inline]
1087    fn size_hint(_depth: usize) -> (usize, Option<usize>) {
1088        (4, Some(4))
1089    }
1090}
1091
1092impl<'a> Arbitrary<'a> for Ipv6Addr {
1093    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
1094        Ok(Ipv6Addr::from(u128::arbitrary(u)?))
1095    }
1096
1097    #[inline]
1098    fn size_hint(_depth: usize) -> (usize, Option<usize>) {
1099        (16, Some(16))
1100    }
1101}
1102
1103#[cfg(test)]
1104mod test {
1105    use super::*;
1106
1107    #[test]
1108    fn finite_buffer_fill_buffer() {
1109        let x = [1, 2, 3, 4];
1110        let mut rb = Unstructured::new(&x);
1111        let mut z = [0; 2];
1112        rb.fill_buffer(&mut z).unwrap();
1113        assert_eq!(z, [1, 2]);
1114        rb.fill_buffer(&mut z).unwrap();
1115        assert_eq!(z, [3, 4]);
1116        rb.fill_buffer(&mut z).unwrap();
1117        assert_eq!(z, [0, 0]);
1118    }
1119
1120    #[test]
1121    fn arbitrary_for_integers() {
1122        let x = [1, 2, 3, 4];
1123        let mut buf = Unstructured::new(&x);
1124        let expected = 1 | (2 << 8) | (3 << 16) | (4 << 24);
1125        let actual = i32::arbitrary(&mut buf).unwrap();
1126        assert_eq!(expected, actual);
1127    }
1128
1129    #[test]
1130    fn arbitrary_for_bytes() {
1131        let x = [1, 2, 3, 4, 4];
1132        let mut buf = Unstructured::new(&x);
1133        let expected = &[1, 2, 3, 4];
1134        let actual = <&[u8] as Arbitrary>::arbitrary(&mut buf).unwrap();
1135        assert_eq!(expected, actual);
1136    }
1137
1138    #[test]
1139    fn arbitrary_take_rest_for_bytes() {
1140        let x = [1, 2, 3, 4];
1141        let buf = Unstructured::new(&x);
1142        let expected = &[1, 2, 3, 4];
1143        let actual = <&[u8] as Arbitrary>::arbitrary_take_rest(buf).unwrap();
1144        assert_eq!(expected, actual);
1145    }
1146
1147    #[test]
1148    fn arbitrary_collection() {
1149        let x = [
1150            1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 8,
1151        ];
1152        assert_eq!(
1153            Vec::<u8>::arbitrary(&mut Unstructured::new(&x)).unwrap(),
1154            &[2, 4, 6, 8, 1]
1155        );
1156        assert_eq!(
1157            Vec::<u32>::arbitrary(&mut Unstructured::new(&x)).unwrap(),
1158            &[84148994]
1159        );
1160        assert_eq!(
1161            String::arbitrary(&mut Unstructured::new(&x)).unwrap(),
1162            "\x01\x02\x03\x04\x05\x06\x07\x08"
1163        );
1164    }
1165
1166    #[test]
1167    fn arbitrary_take_rest() {
1168        let x = [1, 2, 3, 4];
1169        assert_eq!(
1170            Vec::<u8>::arbitrary_take_rest(Unstructured::new(&x)).unwrap(),
1171            &[1, 2, 3, 4]
1172        );
1173        assert_eq!(
1174            Vec::<u32>::arbitrary_take_rest(Unstructured::new(&x)).unwrap(),
1175            &[0x4030201]
1176        );
1177        assert_eq!(
1178            String::arbitrary_take_rest(Unstructured::new(&x)).unwrap(),
1179            "\x01\x02\x03\x04"
1180        );
1181    }
1182
1183    #[test]
1184    fn size_hint_for_tuples() {
1185        assert_eq!(
1186            (7, Some(7)),
1187            <(bool, u16, i32) as Arbitrary<'_>>::size_hint(0)
1188        );
1189        assert_eq!(
1190            (1 + mem::size_of::<usize>(), None),
1191            <(u8, Vec<u8>) as Arbitrary>::size_hint(0)
1192        );
1193    }
1194}
arbitrary/lib.rs

arbitrary/
lib.rs
