/rust/registry/src/index.crates.io-1949cf8c6b5b557f/indexmap-2.8.0/src/lib.rs

Source
// We *mostly* avoid unsafe code, but `Slice` allows it for DST casting.
#![deny(unsafe_code)]
#![warn(rust_2018_idioms)]
#![no_std]

//! [`IndexMap`] is a hash table where the iteration order of the key-value
//! pairs is independent of the hash values of the keys.
//!
//! [`IndexSet`] is a corresponding hash set using the same implementation and
//! with similar properties.
//!
//! ### Highlights
//!
//! [`IndexMap`] and [`IndexSet`] are drop-in compatible with the std `HashMap`
//! and `HashSet`, but they also have some features of note:
//!
//! - The ordering semantics (see their documentation for details)
//! - Sorting methods and the [`.pop()`][IndexMap::pop] methods.
//! - The [`Equivalent`] trait, which offers more flexible equality definitions
//!   between borrowed and owned versions of keys.
//! - The [`MutableKeys`][map::MutableKeys] trait, which gives opt-in mutable
//!   access to map keys, and [`MutableValues`][set::MutableValues] for sets.
//!
//! ### Feature Flags
//!
//! To reduce the amount of compiled code in the crate by default, certain
//! features are gated behind [feature flags]. These allow you to opt in to (or
//! out of) functionality. Below is a list of the features available in this
//! crate.
//!
//! * `std`: Enables features which require the Rust standard library. For more
//!   information see the section on [`no_std`].
//! * `rayon`: Enables parallel iteration and other parallel methods.
//! * `serde`: Adds implementations for [`Serialize`] and [`Deserialize`]
//!   to [`IndexMap`] and [`IndexSet`]. Alternative implementations for
//!   (de)serializing [`IndexMap`] as an ordered sequence are available in the
//!   [`map::serde_seq`] module.
//! * `borsh`: Adds implementations for [`BorshSerialize`] and [`BorshDeserialize`]
//!   to [`IndexMap`] and [`IndexSet`]. **Note:** When this feature is enabled,
//!   you cannot enable the `derive` feature of [`borsh`] due to a cyclic
//!   dependency. Instead, add the `borsh-derive` crate as an explicit
//!   dependency in your Cargo.toml and import as e.g.
//!   `use borsh_derive::{BorshSerialize, BorshDeserialize};`.
//! * `arbitrary`: Adds implementations for the [`arbitrary::Arbitrary`] trait
//!   to [`IndexMap`] and [`IndexSet`].
//! * `quickcheck`: Adds implementations for the [`quickcheck::Arbitrary`] trait
//!   to [`IndexMap`] and [`IndexSet`].
//!
//! _Note: only the `std` feature is enabled by default._
//!
//! [feature flags]: https://doc.rust-lang.org/cargo/reference/manifest.html#the-features-section
//! [`no_std`]: #no-standard-library-targets
//! [`Serialize`]: `::serde::Serialize`
//! [`Deserialize`]: `::serde::Deserialize`
//! [`BorshSerialize`]: `::borsh::BorshSerialize`
//! [`BorshDeserialize`]: `::borsh::BorshDeserialize`
//! [`borsh`]: `::borsh`
//! [`arbitrary::Arbitrary`]: `::arbitrary::Arbitrary`
//! [`quickcheck::Arbitrary`]: `::quickcheck::Arbitrary`
//!
//! ### Alternate Hashers
//!
//! [`IndexMap`] and [`IndexSet`] have a default hasher type
//! [`S = RandomState`][std::collections::hash_map::RandomState],
//! just like the standard `HashMap` and `HashSet`, which is resistant to
//! HashDoS attacks but not the most performant. Type aliases can make it easier
//! to use alternate hashers:
//!
//! ```
//! use fnv::FnvBuildHasher;
//! use indexmap::{IndexMap, IndexSet};
//!
//! type FnvIndexMap<K, V> = IndexMap<K, V, FnvBuildHasher>;
//! type FnvIndexSet<T> = IndexSet<T, FnvBuildHasher>;
//!
//! let std: IndexSet<i32> = (0..100).collect();
//! let fnv: FnvIndexSet<i32> = (0..100).collect();
//! assert_eq!(std, fnv);
//! ```
//!
//! ### Rust Version
//!
//! This version of indexmap requires Rust 1.63 or later.
//!
//! The indexmap 2.x release series will use a carefully considered version
//! upgrade policy, where in a later 2.x version, we will raise the minimum
//! required Rust version.
//!
//! ## No Standard Library Targets
//!
//! This crate supports being built without `std`, requiring `alloc` instead.
//! This is chosen by disabling the default "std" cargo feature, by adding
//! `default-features = false` to your dependency specification.
//!
//! - Creating maps and sets using [`new`][IndexMap::new] and
//!   [`with_capacity`][IndexMap::with_capacity] is unavailable without `std`.
//!   Use methods [`IndexMap::default`], [`with_hasher`][IndexMap::with_hasher],
//!   [`with_capacity_and_hasher`][IndexMap::with_capacity_and_hasher] instead.
//!   A no-std compatible hasher will be needed as well, for example
//!   from the crate `twox-hash`.
//! - Macros [`indexmap!`] and [`indexset!`] are unavailable without `std`. Use
//!   the macros [`indexmap_with_default!`] and [`indexset_with_default!`] instead.

#![cfg_attr(docsrs, feature(doc_cfg))]

extern crate alloc;

#[cfg(feature = "std")]
#[macro_use]
extern crate std;

use alloc::vec::{self, Vec};

mod arbitrary;
#[macro_use]
mod macros;
#[cfg(feature = "borsh")]
mod borsh;
#[cfg(feature = "serde")]
mod serde;
mod util;

pub mod map;
pub mod set;

// Placed after `map` and `set` so new `rayon` methods on the types
// are documented after the "normal" methods.
#[cfg(feature = "rayon")]
mod rayon;

pub use crate::map::IndexMap;
pub use crate::set::IndexSet;
pub use equivalent::Equivalent;

// shared private items

/// Hash value newtype. Not larger than usize, since anything larger
/// isn't used for selecting position anyway.
#[derive(Clone, Copy, Debug, PartialEq)]
struct HashValue(usize);

impl HashValue {
    #[inline(always)]
    fn get(self) -> u64 {
        self.0 as u64
    }
}

#[derive(Copy, Debug)]
struct Bucket<K, V> {
    hash: HashValue,
    key: K,
    value: V,
}

impl<K, V> Clone for Bucket<K, V>
where
    K: Clone,
    V: Clone,
{
    fn clone(&self) -> Self {
        Bucket {
            hash: self.hash,
            key: self.key.clone(),
            value: self.value.clone(),
        }
    }

    fn clone_from(&mut self, other: &Self) {
        self.hash = other.hash;
        self.key.clone_from(&other.key);
        self.value.clone_from(&other.value);
    }
}

impl<K, V> Bucket<K, V> {
    // field accessors -- used for `f` instead of closures in `.map(f)`
    fn key_ref(&self) -> &K {
        &self.key
    }
    fn value_ref(&self) -> &V {
        &self.value
    }
    fn value_mut(&mut self) -> &mut V {
        &mut self.value
    }
    fn key(self) -> K {
        self.key
    }
    fn value(self) -> V {
        self.value
    }
    fn key_value(self) -> (K, V) {
        (self.key, self.value)
    }
    fn refs(&self) -> (&K, &V) {
        (&self.key, &self.value)
    }
    fn ref_mut(&mut self) -> (&K, &mut V) {
        (&self.key, &mut self.value)
    }
    fn muts(&mut self) -> (&mut K, &mut V) {
        (&mut self.key, &mut self.value)
    }
}

trait Entries {
    type Entry;
    fn into_entries(self) -> Vec<Self::Entry>;
    fn as_entries(&self) -> &[Self::Entry];
    fn as_entries_mut(&mut self) -> &mut [Self::Entry];
    fn with_entries<F>(&mut self, f: F)
    where
        F: FnOnce(&mut [Self::Entry]);
}

/// The error type for [`try_reserve`][IndexMap::try_reserve] methods.
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct TryReserveError {
    kind: TryReserveErrorKind,
}

#[derive(Clone, PartialEq, Eq, Debug)]
enum TryReserveErrorKind {
    // The standard library's kind is currently opaque to us, otherwise we could unify this.
    Std(alloc::collections::TryReserveError),
    CapacityOverflow,
    AllocError { layout: alloc::alloc::Layout },
}

// These are not `From` so we don't expose them in our public API.
impl TryReserveError {
    fn from_alloc(error: alloc::collections::TryReserveError) -> Self {
        Self {
            kind: TryReserveErrorKind::Std(error),
        }
    }

    fn from_hashbrown(error: hashbrown::TryReserveError) -> Self {
        Self {
            kind: match error {
                hashbrown::TryReserveError::CapacityOverflow => {
                    TryReserveErrorKind::CapacityOverflow
                }
                hashbrown::TryReserveError::AllocError { layout } => {
                    TryReserveErrorKind::AllocError { layout }
                }
            },
        }
    }
}

impl core::fmt::Display for TryReserveError {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        let reason = match &self.kind {
            TryReserveErrorKind::Std(e) => return core::fmt::Display::fmt(e, f),
            TryReserveErrorKind::CapacityOverflow => {
                " because the computed capacity exceeded the collection's maximum"
            }
            TryReserveErrorKind::AllocError { .. } => {
                " because the memory allocator returned an error"
            }
        };
        f.write_str("memory allocation failed")?;
        f.write_str(reason)
    }
}

#[cfg(feature = "std")]
#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
impl std::error::Error for TryReserveError {}

Coverage Report

Created: 2025-10-10 07:11

Line	Count	Source
1		// We mostly avoid unsafe code, but `Slice` allows it for DST casting.
2		#![deny(unsafe_code)]
3		#![warn(rust_2018_idioms)]
4		#![no_std]
5
6		//! [`IndexMap`] is a hash table where the iteration order of the key-value
7		//! pairs is independent of the hash values of the keys.
8		//!
9		//! [`IndexSet`] is a corresponding hash set using the same implementation and
10		//! with similar properties.
11		//!
12		//! ### Highlights
13		//!
14		//! [`IndexMap`] and [`IndexSet`] are drop-in compatible with the std `HashMap`
15		//! and `HashSet`, but they also have some features of note:
16		//!
17		//! - The ordering semantics (see their documentation for details)
18		//! - Sorting methods and the [`.pop()`][IndexMap::pop] methods.
19		//! - The [`Equivalent`] trait, which offers more flexible equality definitions
20		//! between borrowed and owned versions of keys.
21		//! - The [`MutableKeys`][map::MutableKeys] trait, which gives opt-in mutable
22		//! access to map keys, and [`MutableValues`][set::MutableValues] for sets.
23		//!
24		//! ### Feature Flags
25		//!
26		//! To reduce the amount of compiled code in the crate by default, certain
27		//! features are gated behind [feature flags]. These allow you to opt in to (or
28		//! out of) functionality. Below is a list of the features available in this
29		//! crate.
30		//!
31		//! * `std`: Enables features which require the Rust standard library. For more
32		//! information see the section on [`no_std`].
33		//! * `rayon`: Enables parallel iteration and other parallel methods.
34		//! * `serde`: Adds implementations for [`Serialize`] and [`Deserialize`]
35		//! to [`IndexMap`] and [`IndexSet`]. Alternative implementations for
36		//! (de)serializing [`IndexMap`] as an ordered sequence are available in the
37		//! [`map::serde_seq`] module.
38		//! * `borsh`: Adds implementations for [`BorshSerialize`] and [`BorshDeserialize`]
39		//! to [`IndexMap`] and [`IndexSet`]. Note: When this feature is enabled,
40		//! you cannot enable the `derive` feature of [`borsh`] due to a cyclic
41		//! dependency. Instead, add the `borsh-derive` crate as an explicit
42		//! dependency in your Cargo.toml and import as e.g.
43		//! `use borsh_derive::{BorshSerialize, BorshDeserialize};`.
44		//! * `arbitrary`: Adds implementations for the [`arbitrary::Arbitrary`] trait
45		//! to [`IndexMap`] and [`IndexSet`].
46		//! * `quickcheck`: Adds implementations for the [`quickcheck::Arbitrary`] trait
47		//! to [`IndexMap`] and [`IndexSet`].
48		//!
49		//! _Note: only the `std` feature is enabled by default._
50		//!
51		//! [feature flags]: https://doc.rust-lang.org/cargo/reference/manifest.html#the-features-section
52		//! [`no_std`]: #no-standard-library-targets
53		//! [`Serialize`]: `::serde::Serialize`
54		//! [`Deserialize`]: `::serde::Deserialize`
55		//! [`BorshSerialize`]: `::borsh::BorshSerialize`
56		//! [`BorshDeserialize`]: `::borsh::BorshDeserialize`
57		//! [`borsh`]: `::borsh`
58		//! [`arbitrary::Arbitrary`]: `::arbitrary::Arbitrary`
59		//! [`quickcheck::Arbitrary`]: `::quickcheck::Arbitrary`
60		//!
61		//! ### Alternate Hashers
62		//!
63		//! [`IndexMap`] and [`IndexSet`] have a default hasher type
64		//! [`S = RandomState`][std::collections::hash_map::RandomState],
65		//! just like the standard `HashMap` and `HashSet`, which is resistant to
66		//! HashDoS attacks but not the most performant. Type aliases can make it easier
67		//! to use alternate hashers:
68		//!
69		//! ```
70		//! use fnv::FnvBuildHasher;
71		//! use indexmap::{IndexMap, IndexSet};
72		//!
73		//! type FnvIndexMap<K, V> = IndexMap<K, V, FnvBuildHasher>;
74		//! type FnvIndexSet<T> = IndexSet<T, FnvBuildHasher>;
75		//!
76		//! let std: IndexSet<i32> = (0..100).collect();
77		//! let fnv: FnvIndexSet<i32> = (0..100).collect();
78		//! assert_eq!(std, fnv);
79		//! ```
80		//!
81		//! ### Rust Version
82		//!
83		//! This version of indexmap requires Rust 1.63 or later.
84		//!
85		//! The indexmap 2.x release series will use a carefully considered version
86		//! upgrade policy, where in a later 2.x version, we will raise the minimum
87		//! required Rust version.
88		//!
89		//! ## No Standard Library Targets
90		//!
91		//! This crate supports being built without `std`, requiring `alloc` instead.
92		//! This is chosen by disabling the default "std" cargo feature, by adding
93		//! `default-features = false` to your dependency specification.
94		//!
95		//! - Creating maps and sets using [`new`][IndexMap::new] and
96		//! [`with_capacity`][IndexMap::with_capacity] is unavailable without `std`.
97		//! Use methods [`IndexMap::default`], [`with_hasher`][IndexMap::with_hasher],
98		//! [`with_capacity_and_hasher`][IndexMap::with_capacity_and_hasher] instead.
99		//! A no-std compatible hasher will be needed as well, for example
100		//! from the crate `twox-hash`.
101		//! - Macros [`indexmap!`] and [`indexset!`] are unavailable without `std`. Use
102		//! the macros [`indexmap_with_default!`] and [`indexset_with_default!`] instead.
103
104		#![cfg_attr(docsrs, feature(doc_cfg))]
105
106		extern crate alloc;
107
108		#[cfg(feature = "std")]
109		#[macro_use]
110		extern crate std;
111
112		use alloc::vec::{self, Vec};
113
114		mod arbitrary;
115		#[macro_use]
116		mod macros;
117		#[cfg(feature = "borsh")]
118		mod borsh;
119		#[cfg(feature = "serde")]
120		mod serde;
121		mod util;
122
123		pub mod map;
124		pub mod set;
125
126		// Placed after `map` and `set` so new `rayon` methods on the types
127		// are documented after the "normal" methods.
128		#[cfg(feature = "rayon")]
129		mod rayon;
130
131		pub use crate::map::IndexMap;
132		pub use crate::set::IndexSet;
133		pub use equivalent::Equivalent;
134
135		// shared private items
136
137		/// Hash value newtype. Not larger than usize, since anything larger
138		/// isn't used for selecting position anyway.
139		#[derive(Clone, Copy, Debug, PartialEq)]
140		struct HashValue(usize);
141
142		impl HashValue {
143		#[inline(always)]
144	0	fn get(self) -> u64 {
145	0	self.0 as u64
146	0	}
147		}
148
149		#[derive(Copy, Debug)]
150		struct Bucket<K, V> {
151		hash: HashValue,
152		key: K,
153		value: V,
154		}
155
156		impl<K, V> Clone for Bucket<K, V>
157		where
158		K: Clone,
159		V: Clone,
160		{
161	0	fn clone(&self) -> Self {
162	0	Bucket {
163	0	hash: self.hash,
164	0	key: self.key.clone(),
165	0	value: self.value.clone(),
166	0	}
167	0	} Unexecuted instantiation: <indexmap::Bucket<async_graphql_value::Name, async_graphql_value::ConstValue> as core::clone::Clone>::clone Unexecuted instantiation: <indexmap::Bucket<async_graphql_value::Name, async_graphql_value::Value> as core::clone::Clone>::clone Unexecuted instantiation: <indexmap::Bucket<alloc::string::String, async_graphql_value::ConstValue> as core::clone::Clone>::clone Unexecuted instantiation: <indexmap::Bucket<alloc::string::String, ()> as core::clone::Clone>::clone
168
169	0	fn clone_from(&mut self, other: &Self) {
170	0	self.hash = other.hash;
171	0	self.key.clone_from(&other.key);
172	0	self.value.clone_from(&other.value);
173	0	} Unexecuted instantiation: <indexmap::Bucket<async_graphql_value::Name, async_graphql_value::ConstValue> as core::clone::Clone>::clone_from Unexecuted instantiation: <indexmap::Bucket<async_graphql_value::Name, async_graphql_value::Value> as core::clone::Clone>::clone_from Unexecuted instantiation: <indexmap::Bucket<alloc::string::String, async_graphql_value::ConstValue> as core::clone::Clone>::clone_from Unexecuted instantiation: <indexmap::Bucket<alloc::string::String, ()> as core::clone::Clone>::clone_from
174		}
175
176		impl<K, V> Bucket<K, V> {
177		// field accessors -- used for `f` instead of closures in `.map(f)`
178	0	fn key_ref(&self) -> &K {
179	0	&self.key
180	0	} Unexecuted instantiation: <indexmap::Bucket<async_graphql_value::Name, async_graphql_value::ConstValue>>::key_ref Unexecuted instantiation: <indexmap::Bucket<alloc::string::String, async_graphql::registry::MetaField>>::key_ref Unexecuted instantiation: <indexmap::Bucket<alloc::string::String, ()>>::key_ref
181	0	fn value_ref(&self) -> &V {
182	0	&self.value
183	0	} Unexecuted instantiation: <indexmap::Bucket<async_graphql_value::Name, async_graphql_value::Value>>::value_ref Unexecuted instantiation: <indexmap::Bucket<alloc::string::String, async_graphql::registry::MetaEnumValue>>::value_ref Unexecuted instantiation: <indexmap::Bucket<alloc::string::String, async_graphql::registry::MetaInputValue>>::value_ref Unexecuted instantiation: <indexmap::Bucket<alloc::string::String, async_graphql::registry::MetaField>>::value_ref Unexecuted instantiation: <indexmap::Bucket<alloc::string::String, async_graphql::dynamic::input_value::InputValue>>::value_ref Unexecuted instantiation: <indexmap::Bucket<alloc::string::String, async_graphql::dynamic::subscription::SubscriptionField>>::value_ref Unexecuted instantiation: <indexmap::Bucket<alloc::string::String, async_graphql::dynamic::enum::EnumItem>>::value_ref Unexecuted instantiation: <indexmap::Bucket<alloc::string::String, async_graphql::dynamic::type::Type>>::value_ref Unexecuted instantiation: <indexmap::Bucket<alloc::string::String, async_graphql::dynamic::field::Field>>::value_ref Unexecuted instantiation: <indexmap::Bucket<alloc::string::String, async_graphql::dynamic::interface::InterfaceField>>::value_ref
184		fn value_mut(&mut self) -> &mut V {
185		&mut self.value
186		}
187		fn key(self) -> K {
188		self.key
189		}
190		fn value(self) -> V {
191		self.value
192		}
193	0	fn key_value(self) -> (K, V) {
194	0	(self.key, self.value)
195	0	} Unexecuted instantiation: <indexmap::Bucket<async_graphql_value::Name, async_graphql_value::ConstValue>>::key_value Unexecuted instantiation: <indexmap::Bucket<async_graphql_value::Name, async_graphql_value::Value>>::key_value
196	0	fn refs(&self) -> (&K, &V) {
197	0	(&self.key, &self.value)
198	0	} Unexecuted instantiation: <indexmap::Bucket<h2::frame::stream_id::StreamId, h2::proto::streams::store::SlabIndex>>::refs Unexecuted instantiation: <indexmap::Bucket<alloc::string::String, async_graphql_value::ConstValue>>::refs Unexecuted instantiation: <indexmap::Bucket<alloc::string::String, async_graphql::registry::MetaInputValue>>::refs Unexecuted instantiation: <indexmap::Bucket<alloc::string::String, async_graphql::dynamic::input_value::InputValue>>::refs Unexecuted instantiation: <indexmap::Bucket<alloc::string::String, async_graphql::dynamic::type::Type>>::refs Unexecuted instantiation: <indexmap::Bucket<async_graphql_value::Name, async_graphql_value::ConstValue>>::refs Unexecuted instantiation: <indexmap::Bucket<async_graphql_value::Name, async_graphql_value::Value>>::refs
199		fn ref_mut(&mut self) -> (&K, &mut V) {
200		(&self.key, &mut self.value)
201		}
202		fn muts(&mut self) -> (&mut K, &mut V) {
203		(&mut self.key, &mut self.value)
204		}
205		}
206
207		trait Entries {
208		type Entry;
209		fn into_entries(self) -> Vec<Self::Entry>;
210		fn as_entries(&self) -> &[Self::Entry];
211		fn as_entries_mut(&mut self) -> &mut [Self::Entry];
212		fn with_entries<F>(&mut self, f: F)
213		where
214		F: FnOnce(&mut [Self::Entry]);
215		}
216
217		/// The error type for [`try_reserve`][IndexMap::try_reserve] methods.
218		#[derive(Clone, PartialEq, Eq, Debug)]
219		pub struct TryReserveError {
220		kind: TryReserveErrorKind,
221		}
222
223		#[derive(Clone, PartialEq, Eq, Debug)]
224		enum TryReserveErrorKind {
225		// The standard library's kind is currently opaque to us, otherwise we could unify this.
226		Std(alloc::collections::TryReserveError),
227		CapacityOverflow,
228		AllocError { layout: alloc::alloc::Layout },
229		}
230
231		// These are not `From` so we don't expose them in our public API.
232		impl TryReserveError {
233		fn from_alloc(error: alloc::collections::TryReserveError) -> Self {
234		Self {
235		kind: TryReserveErrorKind::Std(error),
236		}
237		}
238
239		fn from_hashbrown(error: hashbrown::TryReserveError) -> Self {
240		Self {
241		kind: match error {
242		hashbrown::TryReserveError::CapacityOverflow => {
243		TryReserveErrorKind::CapacityOverflow
244		}
245		hashbrown::TryReserveError::AllocError { layout } => {
246		TryReserveErrorKind::AllocError { layout }
247		}
248		},
249		}
250		}
251		}
252
253		impl core::fmt::Display for TryReserveError {
254		fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
255		let reason = match &self.kind {
256		TryReserveErrorKind::Std(e) => return core::fmt::Display::fmt(e, f),
257		TryReserveErrorKind::CapacityOverflow => {
258		" because the computed capacity exceeded the collection's maximum"
259		}
260		TryReserveErrorKind::AllocError { .. } => {
261		" because the memory allocator returned an error"
262		}
263		};
264		f.write_str("memory allocation failed")?;
265		f.write_str(reason)
266		}
267		}
268
269		#[cfg(feature = "std")]
270		#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
271		impl std::error::Error for TryReserveError {}