#[cfg(not(feature = "ferrocene_certified"))]

use super::TrustedLen;

/// Conversion from an [`Iterator`].

///

/// By implementing `FromIterator` for a type, you define how it will be

/// created from an iterator. This is common for types which describe a

/// collection of some kind.

///

/// If you want to create a collection from the contents of an iterator, the

/// [`Iterator::collect()`] method is preferred. However, when you need to

/// specify the container type, [`FromIterator::from_iter()`] can be more

/// readable than using a turbofish (e.g. `::<Vec<_>>()`). See the

/// [`Iterator::collect()`] documentation for more examples of its use.

///

/// See also: [`IntoIterator`].

///

/// # Examples

///

/// Basic usage:

///

/// ```

/// let five_fives = std::iter::repeat(5).take(5);

///

/// let v = Vec::from_iter(five_fives);

///

/// assert_eq!(v, vec![5, 5, 5, 5, 5]);

/// ```

///

/// Using [`Iterator::collect()`] to implicitly use `FromIterator`:

///

/// ```

/// let five_fives = std::iter::repeat(5).take(5);

///

/// let v: Vec<i32> = five_fives.collect();

///

/// assert_eq!(v, vec![5, 5, 5, 5, 5]);

/// ```

///

/// Using [`FromIterator::from_iter()`] as a more readable alternative to

/// [`Iterator::collect()`]:

///

/// ```

/// use std::collections::VecDeque;

/// let first = (0..10).collect::<VecDeque<i32>>();

/// let second = VecDeque::from_iter(0..10);

///

/// assert_eq!(first, second);

/// ```

///

/// Implementing `FromIterator` for your type:

///

/// ```

/// // A sample collection, that's just a wrapper over Vec<T>

/// #[derive(Debug)]

/// struct MyCollection(Vec<i32>);

///

/// // Let's give it some methods so we can create one and add things

/// // to it.

/// impl MyCollection {

///     fn new() -> MyCollection {

///         MyCollection(Vec::new())

///     }

///

///     fn add(&mut self, elem: i32) {

///         self.0.push(elem);

///     }

/// }

///

/// // and we'll implement FromIterator

/// impl FromIterator<i32> for MyCollection {

///     fn from_iter<I: IntoIterator<Item=i32>>(iter: I) -> Self {

///         let mut c = MyCollection::new();

///

///         for i in iter {

///             c.add(i);

///         }

///

///         c

///     }

/// }

///

/// // Now we can make a new iterator...

/// let iter = (0..5).into_iter();

///

/// // ... and make a MyCollection out of it

/// let c = MyCollection::from_iter(iter);

///

/// assert_eq!(c.0, vec![0, 1, 2, 3, 4]);

///

/// // collect works too!

///

/// let iter = (0..5).into_iter();

/// let c: MyCollection = iter.collect();

///

/// assert_eq!(c.0, vec![0, 1, 2, 3, 4]);

/// ```

#[stable(feature = "rust1", since = "1.0.0")]

#[rustc_on_unimplemented(

    on(

        Self = "&[{A}]",

        message = "a slice of type `{Self}` cannot be built since we need to store the elements somewhere",

        label = "try explicitly collecting into a `Vec<{A}>`",

    ),

    on(

        all(A = "{integer}", any(Self = "&[{integral}]",)),

        message = "a slice of type `{Self}` cannot be built since we need to store the elements somewhere",

        label = "try explicitly collecting into a `Vec<{A}>`",

    ),

    on(

        Self = "[{A}]",

        message = "a slice of type `{Self}` cannot be built since `{Self}` has no definite size",

        label = "try explicitly collecting into a `Vec<{A}>`",

    ),

    on(

        all(A = "{integer}", any(Self = "[{integral}]",)),

        message = "a slice of type `{Self}` cannot be built since `{Self}` has no definite size",

        label = "try explicitly collecting into a `Vec<{A}>`",

    ),

    on(

        Self = "[{A}; _]",

        message = "an array of type `{Self}` cannot be built directly from an iterator",

        label = "try collecting into a `Vec<{A}>`, then using `.try_into()`",

    ),

    on(

        all(A = "{integer}", any(Self = "[{integral}; _]",)),

        message = "an array of type `{Self}` cannot be built directly from an iterator",

        label = "try collecting into a `Vec<{A}>`, then using `.try_into()`",

    ),

    message = "a value of type `{Self}` cannot be built from an iterator \

               over elements of type `{A}`",

    label = "value of type `{Self}` cannot be built from `std::iter::Iterator<Item={A}>`"

)]

#[rustc_diagnostic_item = "FromIterator"]

#[cfg(not(feature = "ferrocene_certified"))]

pub trait FromIterator<A>: Sized {

    /// Creates a value from an iterator.

    ///

    /// See the [module-level documentation] for more.

    ///

    /// [module-level documentation]: crate::iter

    ///

    /// # Examples

    ///

    /// ```

    /// let five_fives = std::iter::repeat(5).take(5);

    ///

    /// let v = Vec::from_iter(five_fives);

    ///

    /// assert_eq!(v, vec![5, 5, 5, 5, 5]);

    /// ```

    #[stable(feature = "rust1", since = "1.0.0")]

    #[rustc_diagnostic_item = "from_iter_fn"]

    fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self;

}

/// Conversion into an [`Iterator`].

///

/// By implementing `IntoIterator` for a type, you define how it will be

/// converted to an iterator. This is common for types which describe a

/// collection of some kind.

///

/// One benefit of implementing `IntoIterator` is that your type will [work

/// with Rust's `for` loop syntax](crate::iter#for-loops-and-intoiterator).

///

/// See also: [`FromIterator`].

///

/// # Examples

///

/// Basic usage:

///

/// ```

/// let v = [1, 2, 3];

/// let mut iter = v.into_iter();

///

/// assert_eq!(Some(1), iter.next());

/// assert_eq!(Some(2), iter.next());

/// assert_eq!(Some(3), iter.next());

/// assert_eq!(None, iter.next());

/// ```

/// Implementing `IntoIterator` for your type:

///

/// ```

/// // A sample collection, that's just a wrapper over Vec<T>

/// #[derive(Debug)]

/// struct MyCollection(Vec<i32>);

///

/// // Let's give it some methods so we can create one and add things

/// // to it.

/// impl MyCollection {

///     fn new() -> MyCollection {

///         MyCollection(Vec::new())

///     }

///

///     fn add(&mut self, elem: i32) {

///         self.0.push(elem);

///     }

/// }

///

/// // and we'll implement IntoIterator

/// impl IntoIterator for MyCollection {

///     type Item = i32;

///     type IntoIter = std::vec::IntoIter<Self::Item>;

///

///     fn into_iter(self) -> Self::IntoIter {

///         self.0.into_iter()

///     }

/// }

///

/// // Now we can make a new collection...

/// let mut c = MyCollection::new();

///

/// // ... add some stuff to it ...

/// c.add(0);

/// c.add(1);

/// c.add(2);

///

/// // ... and then turn it into an Iterator:

/// for (i, n) in c.into_iter().enumerate() {

///     assert_eq!(i as i32, n);

/// }

/// ```

///

/// It is common to use `IntoIterator` as a trait bound. This allows

/// the input collection type to change, so long as it is still an

/// iterator. Additional bounds can be specified by restricting on

/// `Item`:

///

/// ```rust

/// fn collect_as_strings<T>(collection: T) -> Vec<String>

/// where

///     T: IntoIterator,

///     T::Item: std::fmt::Debug,

/// {

///     collection

///         .into_iter()

///         .map(|item| format!("{item:?}"))

///         .collect()

/// }

/// ```

#[rustc_diagnostic_item = "IntoIterator"]

#[rustc_on_unimplemented(

    on(

        Self = "core::ops::range::RangeTo<Idx>",

        label = "if you meant to iterate until a value, add a starting value",

        note = "`..end` is a `RangeTo`, which cannot be iterated on; you might have meant to have a \

              bounded `Range`: `0..end`"

    ),

    on(

        Self = "core::ops::range::RangeToInclusive<Idx>",

        label = "if you meant to iterate until a value (including it), add a starting value",

        note = "`..=end` is a `RangeToInclusive`, which cannot be iterated on; you might have meant \

              to have a bounded `RangeInclusive`: `0..=end`"

    ),

    on(

        Self = "[]",

        label = "`{Self}` is not an iterator; try calling `.into_iter()` or `.iter()`"

    ),

    on(Self = "&[]", label = "`{Self}` is not an iterator; try calling `.iter()`"),

    on(

        Self = "alloc::vec::Vec<T, A>",

        label = "`{Self}` is not an iterator; try calling `.into_iter()` or `.iter()`"

    ),

    on(Self = "&str", label = "`{Self}` is not an iterator; try calling `.chars()` or `.bytes()`"),

    on(

        Self = "alloc::string::String",

        label = "`{Self}` is not an iterator; try calling `.chars()` or `.bytes()`"

    ),

    on(

        Self = "{integral}",

        note = "if you want to iterate between `start` until a value `end`, use the exclusive range \

              syntax `start..end` or the inclusive range syntax `start..=end`"

    ),

    on(

        Self = "{float}",

        note = "if you want to iterate between `start` until a value `end`, use the exclusive range \

              syntax `start..end` or the inclusive range syntax `start..=end`"

    ),

    label = "`{Self}` is not an iterator",

    message = "`{Self}` is not an iterator"

)]

#[rustc_skip_during_method_dispatch(array, boxed_slice)]

#[stable(feature = "rust1", since = "1.0.0")]

pub trait IntoIterator {

    /// The type of the elements being iterated over.

    #[stable(feature = "rust1", since = "1.0.0")]

    type Item;

    /// Which kind of iterator are we turning this into?

    #[stable(feature = "rust1", since = "1.0.0")]

    type IntoIter: Iterator<Item = Self::Item>;

    /// Creates an iterator from a value.

    ///

    /// See the [module-level documentation] for more.

    ///

    /// [module-level documentation]: crate::iter

    ///

    /// # Examples

    ///

    /// ```

    /// let v = [1, 2, 3];

    /// let mut iter = v.into_iter();

    ///

    /// assert_eq!(Some(1), iter.next());

    /// assert_eq!(Some(2), iter.next());

    /// assert_eq!(Some(3), iter.next());

    /// assert_eq!(None, iter.next());

    /// ```

    #[lang = "into_iter"]

    #[stable(feature = "rust1", since = "1.0.0")]

    fn into_iter(self) -> Self::IntoIter;

}

#[stable(feature = "rust1", since = "1.0.0")]

#[cfg(not(feature = "ferrocene_certified"))]

impl<I: Iterator> IntoIterator for I {

    type Item = I::Item;

    type IntoIter = I;

    #[inline]

}

/// Extend a collection with the contents of an iterator.

///

/// Iterators produce a series of values, and collections can also be thought

/// of as a series of values. The `Extend` trait bridges this gap, allowing you

/// to extend a collection by including the contents of that iterator. When

/// extending a collection with an already existing key, that entry is updated

/// or, in the case of collections that permit multiple entries with equal

/// keys, that entry is inserted.

///

/// # Examples

///

/// Basic usage:

///

/// ```

/// // You can extend a String with some chars:

/// let mut message = String::from("The first three letters are: ");

///

/// message.extend(&['a', 'b', 'c']);

///

/// assert_eq!("abc", &message[29..32]);

/// ```

///

/// Implementing `Extend`:

///

/// ```

/// // A sample collection, that's just a wrapper over Vec<T>

/// #[derive(Debug)]

/// struct MyCollection(Vec<i32>);

///

/// // Let's give it some methods so we can create one and add things

/// // to it.

/// impl MyCollection {

///     fn new() -> MyCollection {

///         MyCollection(Vec::new())

///     }

///

///     fn add(&mut self, elem: i32) {

///         self.0.push(elem);

///     }

/// }

///

/// // since MyCollection has a list of i32s, we implement Extend for i32

/// impl Extend<i32> for MyCollection {

///

///     // This is a bit simpler with the concrete type signature: we can call

///     // extend on anything which can be turned into an Iterator which gives

///     // us i32s. Because we need i32s to put into MyCollection.

///     fn extend<T: IntoIterator<Item=i32>>(&mut self, iter: T) {

///

///         // The implementation is very straightforward: loop through the

///         // iterator, and add() each element to ourselves.

///         for elem in iter {

///             self.add(elem);

///         }

///     }

/// }

///

/// let mut c = MyCollection::new();

///

/// c.add(5);

/// c.add(6);

/// c.add(7);

///

/// // let's extend our collection with three more numbers

/// c.extend(vec![1, 2, 3]);

///

/// // we've added these elements onto the end

/// assert_eq!("MyCollection([5, 6, 7, 1, 2, 3])", format!("{c:?}"));

/// ```

#[stable(feature = "rust1", since = "1.0.0")]

#[cfg(not(feature = "ferrocene_certified"))]

pub trait Extend<A> {

    /// Extends a collection with the contents of an iterator.

    ///

    /// As this is the only required method for this trait, the [trait-level] docs

    /// contain more details.

    ///

    /// [trait-level]: Extend

    ///

    /// # Examples

    ///

    /// ```

    /// // You can extend a String with some chars:

    /// let mut message = String::from("abc");

    ///

    /// message.extend(['d', 'e', 'f'].iter());

    ///

    /// assert_eq!("abcdef", &message);

    /// ```

    #[stable(feature = "rust1", since = "1.0.0")]

    fn extend<T: IntoIterator<Item = A>>(&mut self, iter: T);

    /// Extends a collection with exactly one element.

    #[unstable(feature = "extend_one", issue = "72631")]

    fn extend_one(&mut self, item: A) {

        self.extend(Some(item));

    }

    /// Reserves capacity in a collection for the given number of additional elements.

    ///

    /// The default implementation does nothing.

    #[unstable(feature = "extend_one", issue = "72631")]

    fn extend_reserve(&mut self, additional: usize) {

        let _ = additional;

    }

    /// Extends a collection with one element, without checking there is enough capacity for it.

    ///

    /// # Safety

    ///

    /// **For callers:** This must only be called when we know the collection has enough capacity

    /// to contain the new item, for example because we previously called `extend_reserve`.

    ///

    /// **For implementors:** For a collection to unsafely rely on this method's safety precondition (that is,

    /// invoke UB if they are violated), it must implement `extend_reserve` correctly. In other words,

    /// callers may assume that if they `extend_reserve`ed enough space they can call this method.

    // This method is for internal usage only. It is only on the trait because of specialization's limitations.

    #[unstable(feature = "extend_one_unchecked", issue = "none")]

    #[doc(hidden)]

    unsafe fn extend_one_unchecked(&mut self, item: A)

    where

        Self: Sized,

    {

        self.extend_one(item);

    }

}

#[stable(feature = "extend_for_unit", since = "1.28.0")]

#[cfg(not(feature = "ferrocene_certified"))]

impl Extend<()> for () {

    fn extend<T: IntoIterator<Item = ()>>(&mut self, iter: T) {

        iter.into_iter().for_each(drop)

    }

    fn extend_one(&mut self, _item: ()) {}

}

macro_rules! spec_tuple_impl {

    (

        (

            $ty_name:ident, $var_name:ident, $extend_ty_name: ident,

            $trait_name:ident, $default_fn_name:ident, $cnt:tt

        ),

    ) => {

        spec_tuple_impl!(

            $trait_name,

            $default_fn_name,

            #[doc(fake_variadic)]

            #[doc = "This trait is implemented for tuples up to twelve items long. The `impl`s for \

                     1- and 3- through 12-ary tuples were stabilized after 2-tuples, in \

                     1.85.0."]

            => ($ty_name, $var_name, $extend_ty_name, $cnt),

        );

    };

    (

        (

            $ty_name:ident, $var_name:ident, $extend_ty_name: ident,

            $trait_name:ident, $default_fn_name:ident, $cnt:tt

        ),

        $(

            (

                $ty_names:ident, $var_names:ident,  $extend_ty_names:ident,

                $trait_names:ident, $default_fn_names:ident, $cnts:tt

            ),

        )*

    ) => {

        spec_tuple_impl!(

            $(

                (

                    $ty_names, $var_names, $extend_ty_names,

                    $trait_names, $default_fn_names, $cnts

                ),

            )*

        );

        spec_tuple_impl!(

            $trait_name,

            $default_fn_name,

            #[doc(hidden)]

            => (

                $ty_name, $var_name, $extend_ty_name, $cnt

            ),

            $(

                (

                    $ty_names, $var_names, $extend_ty_names, $cnts

                ),

            )*

        );

    };

    (

        $trait_name:ident, $default_fn_name:ident, #[$meta:meta]

        $(#[$doctext:meta])? => $(

            (

                $ty_names:ident, $var_names:ident, $extend_ty_names:ident, $cnts:tt

            ),

        )*

    ) => {

        #[$meta]

        $(#[$doctext])?

        #[stable(feature = "extend_for_tuple", since = "1.56.0")]

        #[cfg(not(feature = "ferrocene_certified"))]

        impl<$($ty_names,)* $($extend_ty_names,)*> Extend<($($ty_names,)*)> for ($($extend_ty_names,)*)

        where

            $($extend_ty_names: Extend<$ty_names>,)*

        {

            /// Allows to `extend` a tuple of collections that also implement `Extend`.

            ///

            /// See also: [`Iterator::unzip`]

            ///

            /// # Examples

            /// ```

            /// // Example given for a 2-tuple, but 1- through 12-tuples are supported

            /// let mut tuple = (vec![0], vec![1]);

            /// tuple.extend([(2, 3), (4, 5), (6, 7)]);

            /// assert_eq!(tuple.0, [0, 2, 4, 6]);

            /// assert_eq!(tuple.1, [1, 3, 5, 7]);

            ///

            /// // also allows for arbitrarily nested tuples as elements

            /// let mut nested_tuple = (vec![1], (vec![2], vec![3]));

            /// nested_tuple.extend([(4, (5, 6)), (7, (8, 9))]);

            ///

            /// let (a, (b, c)) = nested_tuple;

            /// assert_eq!(a, [1, 4, 7]);

            /// assert_eq!(b, [2, 5, 8]);

            /// assert_eq!(c, [3, 6, 9]);

            /// ```

            fn extend<T: IntoIterator<Item = ($($ty_names,)*)>>(&mut self, into_iter: T) {

                let ($($var_names,)*) = self;

                let iter = into_iter.into_iter();

                $trait_name::extend(iter, $($var_names,)*);

            }

            fn extend_one(&mut self, item: ($($ty_names,)*)) {

                $(self.$cnts.extend_one(item.$cnts);)*

            }

            fn extend_reserve(&mut self, additional: usize) {

                $(self.$cnts.extend_reserve(additional);)*

            }

            unsafe fn extend_one_unchecked(&mut self, item: ($($ty_names,)*)) {

                // SAFETY: Those are our safety preconditions, and we correctly forward `extend_reserve`.

                unsafe {

                     $(self.$cnts.extend_one_unchecked(item.$cnts);)*

                }

            }

        }

        #[cfg(not(feature = "ferrocene_certified"))]

        trait $trait_name<$($ty_names),*> {

            fn extend(self, $($var_names: &mut $ty_names,)*);

        }

        #[cfg(not(feature = "ferrocene_certified"))]

        fn $default_fn_name<$($ty_names,)* $($extend_ty_names,)*>(

            iter: impl Iterator<Item = ($($ty_names,)*)>,

            $($var_names: &mut $extend_ty_names,)*

        ) where

            $($extend_ty_names: Extend<$ty_names>,)*

        {

            fn extend<'a, $($ty_names,)*>(

                $($var_names: &'a mut impl Extend<$ty_names>,)*

            ) -> impl FnMut((), ($($ty_names,)*)) + 'a {

                #[allow(non_snake_case)]

                move |(), ($($extend_ty_names,)*)| {

                    $($var_names.extend_one($extend_ty_names);)*

                }

            }

            let (lower_bound, _) = iter.size_hint();

            if lower_bound > 0 {

                $($var_names.extend_reserve(lower_bound);)*

            }

            iter.fold((), extend($($var_names,)*));

        }

        #[cfg(not(feature = "ferrocene_certified"))]

        impl<$($ty_names,)* $($extend_ty_names,)* Iter> $trait_name<$($extend_ty_names),*> for Iter

        where

            $($extend_ty_names: Extend<$ty_names>,)*

            Iter: Iterator<Item = ($($ty_names,)*)>,

        {

            default fn extend(self, $($var_names: &mut $extend_ty_names),*) {

                $default_fn_name(self, $($var_names),*);

            }

        }

        #[cfg(not(feature = "ferrocene_certified"))]

        impl<$($ty_names,)* $($extend_ty_names,)* Iter> $trait_name<$($extend_ty_names),*> for Iter

        where

            $($extend_ty_names: Extend<$ty_names>,)*

            Iter: TrustedLen<Item = ($($ty_names,)*)>,

        {

            fn extend(self, $($var_names: &mut $extend_ty_names,)*) {

                fn extend<'a, $($ty_names,)*>(

                    $($var_names: &'a mut impl Extend<$ty_names>,)*

                ) -> impl FnMut((), ($($ty_names,)*)) + 'a {

                    #[allow(non_snake_case)]

                    // SAFETY: We reserve enough space for the `size_hint`, and the iterator is

                    // `TrustedLen` so its `size_hint` is exact.

                    move |(), ($($extend_ty_names,)*)| unsafe {

                        $($var_names.extend_one_unchecked($extend_ty_names);)*

                    }

                }

                let (lower_bound, upper_bound) = self.size_hint();

                if upper_bound.is_none() {

                    // We cannot reserve more than `usize::MAX` items, and this is likely to go out of memory anyway.

                    $default_fn_name(self, $($var_names,)*);

                    return;

                }

                if lower_bound > 0 {

                    $($var_names.extend_reserve(lower_bound);)*

                }

                self.fold((), extend($($var_names,)*));

            }

        }

        /// This implementation turns an iterator of tuples into a tuple of types which implement

        /// [`Default`] and [`Extend`].

        ///

        /// This is similar to [`Iterator::unzip`], but is also composable with other [`FromIterator`]

        /// implementations:

        ///

        /// ```rust

        /// # fn main() -> Result<(), core::num::ParseIntError> {

        /// let string = "1,2,123,4";

        ///

        /// // Example given for a 2-tuple, but 1- through 12-tuples are supported

        /// let (numbers, lengths): (Vec<_>, Vec<_>) = string

        ///     .split(',')

        ///     .map(|s| s.parse().map(|n: u32| (n, s.len())))

        ///     .collect::<Result<_, _>>()?;

        ///

        /// assert_eq!(numbers, [1, 2, 123, 4]);

        /// assert_eq!(lengths, [1, 1, 3, 1]);

        /// # Ok(()) }

        /// ```

        #[$meta]

        $(#[$doctext])?

        #[stable(feature = "from_iterator_for_tuple", since = "1.79.0")]

        #[cfg(not(feature = "ferrocene_certified"))]

        impl<$($ty_names,)* $($extend_ty_names,)*> FromIterator<($($extend_ty_names,)*)> for ($($ty_names,)*)

        where

            $($ty_names: Default + Extend<$extend_ty_names>,)*

        {

            fn from_iter<Iter: IntoIterator<Item = ($($extend_ty_names,)*)>>(iter: Iter) -> Self {

                let mut res = <($($ty_names,)*)>::default();

                res.extend(iter);

                res

            }

        }

    };

}

spec_tuple_impl!(

    (L, l, EL, TraitL, default_extend_tuple_l, 11),

    (K, k, EK, TraitK, default_extend_tuple_k, 10),

    (J, j, EJ, TraitJ, default_extend_tuple_j, 9),

    (I, i, EI, TraitI, default_extend_tuple_i, 8),

    (H, h, EH, TraitH, default_extend_tuple_h, 7),

    (G, g, EG, TraitG, default_extend_tuple_g, 6),

    (F, f, EF, TraitF, default_extend_tuple_f, 5),

    (E, e, EE, TraitE, default_extend_tuple_e, 4),

    (D, d, ED, TraitD, default_extend_tuple_d, 3),

    (C, c, EC, TraitC, default_extend_tuple_c, 2),

    (B, b, EB, TraitB, default_extend_tuple_b, 1),

    (A, a, EA, TraitA, default_extend_tuple_a, 0),

);