third_party/rust/id-arena/src/lib.rs

   1 //! [![](https://img.shields.io/crates/v/id-arena.svg)](https://crates.io/crates/id-arena)
   2 //! [![](https://img.shields.io/crates/d/id-arena.svg)](https://crates.io/crates/id-arena)
   3 //! [![Travis CI Build Status](https://travis-ci.org/fitzgen/id-arena.svg?branch=master)](https://travis-ci.org/fitzgen/id-arena)
   4 //!
   5 //! A simple, id-based arena.
   6 //!
   7 //! ## Id-based
   8 //!
   9 //! Allocate objects and get an identifier for that object back, *not* a
  10 //! reference to the allocated object. Given an id, you can get a shared or
  11 //! exclusive reference to the allocated object from the arena. This id-based
  12 //! approach is useful for constructing mutable graph data structures.
  13 //!
  14 //! If you want allocation to return a reference, consider [the `typed-arena`
  15 //! crate](https://github.com/SimonSapin/rust-typed-arena/) instead.
  16 //!
  17 //! ## No Deletion
  18 //!
  19 //! This arena does not support deletion, which makes its implementation simple
  20 //! and allocation fast. If you want deletion, you need a way to solve the ABA
  21 //! problem. Consider using [the `generational-arena`
  22 //! crate](https://github.com/fitzgen/generational-arena) instead.
  23 //!
  24 //! ## Homogeneous
  25 //!
  26 //! This crate's arenas can only contain objects of a single type `T`. If you
  27 //! need an arena of objects with heterogeneous types, consider another crate.
  28 //!
  29 //! ## `#![no_std]` Support
  30 //!
  31 //! Requires the `alloc` nightly feature. Disable the on-by-default `"std"` feature:
  32 //!
  33 //! ```toml
  34 //! [dependencies.id-arena]
  35 //! version = "2"
  36 //! default-features = false
  37 //! ```
  38 //!
  39 //! ## `rayon` Support
  40 //!
  41 //! If the `rayon` feature of this crate is activated:
  42 //!
  43 //! ```toml
  44 //! [dependencies]
  45 //! id-arena = { version = "2", features = ["rayon"] }
  46 //! ```
  47 //!
  48 //! then you can use [`rayon`](https://crates.io/crates/rayon)'s support for
  49 //! parallel iteration. The `Arena` type will have a `par_iter` family of
  50 //! methods where appropriate.
  51 //!
  52 //! ## Example
  53 //!
  54 //! ```rust
  55 //! use id_arena::{Arena, Id};
  56 //!
  57 //! type AstNodeId = Id<AstNode>;
  58 //!
  59 //! #[derive(Debug, Eq, PartialEq)]
  60 //! pub enum AstNode {
  61 //!     Const(i64),
  62 //!     Var(String),
  63 //!     Add {
  64 //!         lhs: AstNodeId,
  65 //!         rhs: AstNodeId,
  66 //!     },
  67 //!     Sub {
  68 //!         lhs: AstNodeId,
  69 //!         rhs: AstNodeId,
  70 //!     },
  71 //!     Mul {
  72 //!         lhs: AstNodeId,
  73 //!         rhs: AstNodeId,
  74 //!     },
  75 //!     Div {
  76 //!         lhs: AstNodeId,
  77 //!         rhs: AstNodeId,
  78 //!     },
  79 //! }
  80 //!
  81 //! let mut ast_nodes = Arena::<AstNode>::new();
  82 //!
  83 //! // Create the AST for `a * (b + 3)`.
  84 //! let three = ast_nodes.alloc(AstNode::Const(3));
  85 //! let b = ast_nodes.alloc(AstNode::Var("b".into()));
  86 //! let b_plus_three = ast_nodes.alloc(AstNode::Add {
  87 //!     lhs: b,
  88 //!     rhs: three,
  89 //! });
  90 //! let a = ast_nodes.alloc(AstNode::Var("a".into()));
  91 //! let a_times_b_plus_three = ast_nodes.alloc(AstNode::Mul {
  92 //!     lhs: a,
  93 //!     rhs: b_plus_three,
  94 //! });
  95 //!
  96 //! // Can use indexing to access allocated nodes.
  97 //! assert_eq!(ast_nodes[three], AstNode::Const(3));
  98 //! ```
  99
 100 #![forbid(unsafe_code)]
 101 #![deny(missing_debug_implementations)]
 102 #![deny(missing_docs)]
 103 // In no-std mode, use the alloc crate to get `Vec`.
 104 #![no_std]
 105 #![cfg_attr(not(feature = "std"), feature(alloc))]
 106
 107 use core::cmp::Ordering;
 108 use core::fmt;
 109 use core::hash::{Hash, Hasher};
 110 use core::iter;
 111 use core::marker::PhantomData;
 112 use core::ops;
 113 use core::slice;
 114 use core::sync::atomic::{self, AtomicUsize, ATOMIC_USIZE_INIT};
 115
 116 #[cfg(not(feature = "std"))]
 117 extern crate alloc;
 118 #[cfg(not(feature = "std"))]
 119 use alloc::vec::{self, Vec};
 120
 121 #[cfg(feature = "std")]
 122 extern crate std;
 123 #[cfg(feature = "std")]
 124 use std::vec::{self, Vec};
 125
 126 #[cfg(feature = "rayon")]
 127 mod rayon;
 128 #[cfg(feature = "rayon")]
 129 pub use rayon::*;
 130
 131 /// A trait representing the implementation behavior of an arena and how
 132 /// identifiers are represented.
 133 ///
 134 /// ## When should I implement `ArenaBehavior` myself?
 135 ///
 136 /// Usually, you should just use `DefaultArenaBehavior`, which is simple and
 137 /// correct. However, there are some scenarios where you might want to implement
 138 /// `ArenaBehavior` yourself:
 139 ///
 140 /// * **Space optimizations:** The default identifier is two words in size,
 141 /// which is larger than is usually necessary. For example, if you know that an
 142 /// arena *cannot* contain more than 256 items, you could make your own
 143 /// identifier type that stores the index as a `u8` and then you can save some
 144 /// space.
 145 ///
 146 /// * **Trait Coherence:** If you need to implement an upstream crate's traits
 147 /// for identifiers, then defining your own identifier type allows you to work
 148 /// with trait coherence rules.
 149 ///
 150 /// * **Share identifiers across arenas:** You can coordinate and share
 151 /// identifiers across different arenas to enable a "struct of arrays" style
 152 /// data representation.
 153 pub trait ArenaBehavior {
 154     /// The identifier type.
 155     type Id: Copy;
 156
 157     /// Construct a new object identifier from the given index and arena
 158     /// identifier.
 159     ///
 160     /// ## Panics
 161     ///
 162     /// Implementations are allowed to panic if the given index is larger than
 163     /// the underlying storage (e.g. the implementation uses a `u8` for storing
 164     /// indices and the given index value is larger than 255).
 165     fn new_id(arena_id: u32, index: usize) -> Self::Id;
 166
 167     /// Get the given identifier's index.
 168     fn index(Self::Id) -> usize;
 169
 170     /// Get the given identifier's arena id.
 171     fn arena_id(Self::Id) -> u32;
 172
 173     /// Construct a new arena identifier.
 174     ///
 175     /// This is used to disambiguate `Id`s across different arenas. To make
 176     /// identifiers with the same index from different arenas compare false for
 177     /// equality, return a unique `u32` on every invocation. This is the
 178     /// default, provided implementation's behavior.
 179     ///
 180     /// To make identifiers with the same index from different arenas compare
 181     /// true for equality, return the same `u32` on every invocation.
 182     fn new_arena_id() -> u32 {
 183         static ARENA_COUNTER: AtomicUsize = ATOMIC_USIZE_INIT;
 184         ARENA_COUNTER.fetch_add(1, atomic::Ordering::SeqCst) as u32
 185     }
 186 }
 187
 188 /// An identifier for an object allocated within an arena.
 189 pub struct Id<T> {
 190     idx: usize,
 191     arena_id: u32,
 192     _ty: PhantomData<fn() -> T>,
 193 }
 194
 195 impl<T> fmt::Debug for Id<T> {
 196     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 197         f.debug_struct("Id").field("idx", &self.idx).finish()
 198     }
 199 }
 200
 201 impl<T> Copy for Id<T> {}
 202
 203 impl<T> Clone for Id<T> {
 204     #[inline]
 205     fn clone(&self) -> Id<T> {
 206         *self
 207     }
 208 }
 209
 210 impl<T> PartialEq for Id<T> {
 211     #[inline]
 212     fn eq(&self, rhs: &Self) -> bool {
 213         self.arena_id == rhs.arena_id && self.idx == rhs.idx
 214     }
 215 }
 216
 217 impl<T> Eq for Id<T> {}
 218
 219 impl<T> Hash for Id<T> {
 220     #[inline]
 221     fn hash<H: Hasher>(&self, h: &mut H) {
 222         self.arena_id.hash(h);
 223         self.idx.hash(h);
 224     }
 225 }
 226
 227 impl<T> PartialOrd for Id<T> {
 228     fn partial_cmp(&self, rhs: &Self) -> Option<Ordering> {
 229         Some(self.cmp(rhs))
 230     }
 231 }
 232
 233 impl<T> Ord for Id<T> {
 234     fn cmp(&self, rhs: &Self) -> Ordering {
 235         self.arena_id
 236             .cmp(&rhs.arena_id)
 237             .then(self.idx.cmp(&rhs.idx))
 238     }
 239 }
 240
 241 impl<T> Id<T> {
 242     /// Get the index within the arena that this id refers to.
 243     #[inline]
 244     pub fn index(&self) -> usize {
 245         self.idx
 246     }
 247 }
 248
 249 /// The default `ArenaBehavior` implementation.
 250 #[derive(Clone, Debug, PartialEq, Eq)]
 251 pub struct DefaultArenaBehavior<T> {
 252     _phantom: PhantomData<fn() -> T>,
 253 }
 254
 255 impl<T> ArenaBehavior for DefaultArenaBehavior<T> {
 256     type Id = Id<T>;
 257
 258     #[inline]
 259     fn new_id(arena_id: u32, idx: usize) -> Self::Id {
 260         Id {
 261             idx,
 262             arena_id,
 263             _ty: PhantomData,
 264         }
 265     }
 266
 267     #[inline]
 268     fn index(id: Self::Id) -> usize {
 269         id.idx
 270     }
 271
 272     #[inline]
 273     fn arena_id(id: Self::Id) -> u32 {
 274         id.arena_id
 275     }
 276 }
 277
 278 /// An arena of objects of type `T`.
 279 ///
 280 /// ```
 281 /// use id_arena::Arena;
 282 ///
 283 /// let mut arena = Arena::<&str>::new();
 284 ///
 285 /// let a = arena.alloc("Albert");
 286 /// assert_eq!(arena[a], "Albert");
 287 ///
 288 /// arena[a] = "Alice";
 289 /// assert_eq!(arena[a], "Alice");
 290 /// ```
 291 #[derive(Clone, Debug, PartialEq, Eq)]
 292 pub struct Arena<T, A = DefaultArenaBehavior<T>> {
 293     arena_id: u32,
 294     items: Vec<T>,
 295     _phantom: PhantomData<fn() -> A>,
 296 }
 297
 298 impl<T, A> Default for Arena<T, A>
 299 where
 300     A: ArenaBehavior,
 301 {
 302     #[inline]
 303     fn default() -> Arena<T, A> {
 304         Arena {
 305             arena_id: A::new_arena_id(),
 306             items: Vec::new(),
 307             _phantom: PhantomData,
 308         }
 309     }
 310 }
 311
 312 impl<T, A> Arena<T, A>
 313 where
 314     A: ArenaBehavior,
 315 {
 316     /// Construct a new, empty `Arena`.
 317     ///
 318     /// ```
 319     /// use id_arena::Arena;
 320     ///
 321     /// let mut arena = Arena::<usize>::new();
 322     /// arena.alloc(42);
 323     /// ```
 324     #[inline]
 325     pub fn new() -> Arena<T, A> {
 326         Default::default()
 327     }
 328
 329     /// Construct a new, empty `Arena` with capacity for the given number of
 330     /// elements.
 331     ///
 332     /// ```
 333     /// use id_arena::Arena;
 334     ///
 335     /// let mut arena = Arena::<usize>::with_capacity(100);
 336     /// for x in 0..100 {
 337     ///     arena.alloc(x * x);
 338     /// }
 339     /// ```
 340     #[inline]
 341     pub fn with_capacity(capacity: usize) -> Arena<T, A> {
 342         Arena {
 343             arena_id: A::new_arena_id(),
 344             items: Vec::with_capacity(capacity),
 345             _phantom: PhantomData,
 346         }
 347     }
 348
 349     /// Allocate `item` within this arena and return its id.
 350     ///
 351     /// ```
 352     /// use id_arena::Arena;
 353     ///
 354     /// let mut arena = Arena::<usize>::new();
 355     /// let _id = arena.alloc(42);
 356     /// ```
 357     ///
 358     /// ## Panics
 359     ///
 360     /// Panics if the number of elements in the arena overflows a `usize` or
 361     /// `Id`'s index storage representation.
 362     #[inline]
 363     pub fn alloc(&mut self, item: T) -> A::Id {
 364         let id = self.next_id();
 365         self.items.push(item);
 366         id
 367     }
 368
 369     /// Allocate an item with the id that it will be assigned.
 370     ///
 371     /// This is useful for structures that want to store their id as their own
 372     /// member.
 373     ///
 374     /// ```
 375     /// use id_arena::{Arena, Id};
 376     ///
 377     /// struct Cat {
 378     ///     id: Id<Cat>,
 379     /// }
 380     ///
 381     /// let mut arena = Arena::<Cat>::new();
 382     ///
 383     /// let kitty = arena.alloc_with_id(|id| Cat { id });
 384     /// assert_eq!(arena[kitty].id, kitty);
 385     /// ```
 386     #[inline]
 387     pub fn alloc_with_id(&mut self, f: impl FnOnce(A::Id) -> T) -> A::Id {
 388         let id = self.next_id();
 389         let val = f(id);
 390         self.alloc(val)
 391     }
 392
 393     /// Get the id that will be used for the next item allocated into this
 394     /// arena.
 395     ///
 396     /// If you are allocating a `struct` that wants to have its id as a member
 397     /// of itself, prefer the less error-prone `Arena::alloc_with_id` method.
 398     #[inline]
 399     pub fn next_id(&self) -> A::Id {
 400         let arena_id = self.arena_id;
 401         let idx = self.items.len();
 402         A::new_id(arena_id, idx)
 403     }
 404
 405     /// Get a shared reference to the object associated with the given `id` if
 406     /// it exists.
 407     ///
 408     /// If there is no object associated with `id` (for example, it might
 409     /// reference an object allocated within a different arena) then return
 410     /// `None`.
 411     ///
 412     /// ```
 413     /// use id_arena::Arena;
 414     ///
 415     /// let mut arena = Arena::<usize>::new();
 416     /// let id = arena.alloc(42);
 417     /// assert!(arena.get(id).is_some());
 418     ///
 419     /// let other_arena = Arena::<usize>::new();
 420     /// assert!(other_arena.get(id).is_none());
 421     /// ```
 422     #[inline]
 423     pub fn get(&self, id: A::Id) -> Option<&T> {
 424         if A::arena_id(id) != self.arena_id {
 425             None
 426         } else {
 427             self.items.get(A::index(id))
 428         }
 429     }
 430
 431     /// Get an exclusive reference to the object associated with the given `id`
 432     /// if it exists.
 433     ///
 434     /// If there is no object associated with `id` (for example, it might
 435     /// reference an object allocated within a different arena) then return
 436     /// `None`.
 437     ///
 438     /// ```
 439     /// use id_arena::Arena;
 440     ///
 441     /// let mut arena = Arena::<usize>::new();
 442     /// let id = arena.alloc(42);
 443     /// assert!(arena.get_mut(id).is_some());
 444     ///
 445     /// let mut other_arena = Arena::<usize>::new();
 446     /// assert!(other_arena.get_mut(id).is_none());
 447     /// ```
 448     #[inline]
 449     pub fn get_mut(&mut self, id: A::Id) -> Option<&mut T> {
 450         if A::arena_id(id) != self.arena_id {
 451             None
 452         } else {
 453             self.items.get_mut(A::index(id))
 454         }
 455     }
 456
 457     /// Iterate over this arena's items and their ids.
 458     ///
 459     /// ```
 460     /// use id_arena::Arena;
 461     ///
 462     /// let mut arena = Arena::<&str>::new();
 463     ///
 464     /// arena.alloc("hello");
 465     /// arena.alloc("hi");
 466     /// arena.alloc("yo");
 467     ///
 468     /// for (id, s) in arena.iter() {
 469     ///     assert_eq!(arena.get(id).unwrap(), s);
 470     ///     println!("{:?} -> {}", id, s);
 471     /// }
 472     /// ```
 473     #[inline]
 474     pub fn iter(&self) -> Iter<T, A> {
 475         IntoIterator::into_iter(self)
 476     }
 477
 478     /// Iterate over this arena's items and their ids, allowing mutation of each
 479     /// item.
 480     #[inline]
 481     pub fn iter_mut(&mut self) -> IterMut<T, A> {
 482         IntoIterator::into_iter(self)
 483     }
 484
 485     /// Get the number of objects allocated in this arena.
 486     ///
 487     /// ```
 488     /// use id_arena::Arena;
 489     ///
 490     /// let mut arena = Arena::<&str>::new();
 491     ///
 492     /// arena.alloc("hello");
 493     /// arena.alloc("hi");
 494     ///
 495     /// assert_eq!(arena.len(), 2);
 496     /// ```
 497     #[inline]
 498     pub fn len(&self) -> usize {
 499         self.items.len()
 500     }
 501 }
 502
 503 impl<T, A> ops::Index<A::Id> for Arena<T, A>
 504 where
 505     A: ArenaBehavior,
 506 {
 507     type Output = T;
 508
 509     #[inline]
 510     fn index(&self, id: A::Id) -> &T {
 511         assert_eq!(self.arena_id, A::arena_id(id));
 512         &self.items[A::index(id)]
 513     }
 514 }
 515
 516 impl<T, A> ops::IndexMut<A::Id> for Arena<T, A>
 517 where
 518     A: ArenaBehavior,
 519 {
 520     #[inline]
 521     fn index_mut(&mut self, id: A::Id) -> &mut T {
 522         assert_eq!(self.arena_id, A::arena_id(id));
 523         &mut self.items[A::index(id)]
 524     }
 525 }
 526
 527 fn add_id<A, T>(item: Option<(usize, T)>, arena_id: u32) -> Option<(A::Id, T)>
 528 where
 529     A: ArenaBehavior,
 530 {
 531     item.map(|(idx, item)| (A::new_id(arena_id, idx), item))
 532 }
 533
 534 /// An iterator over `(Id, &T)` pairs in an arena.
 535 ///
 536 /// See [the `Arena::iter()` method](./struct.Arena.html#method.iter) for details.
 537 #[derive(Debug)]
 538 pub struct Iter<'a, T: 'a, A: 'a> {
 539     arena_id: u32,
 540     iter: iter::Enumerate<slice::Iter<'a, T>>,
 541     _phantom: PhantomData<fn() -> A>,
 542 }
 543
 544 impl<'a, T: 'a, A: 'a> Iterator for Iter<'a, T, A>
 545 where
 546     A: ArenaBehavior,
 547 {
 548     type Item = (A::Id, &'a T);
 549
 550     #[inline]
 551     fn next(&mut self) -> Option<Self::Item> {
 552         add_id::<A, _>(self.iter.next(), self.arena_id)
 553     }
 554
 555     fn size_hint(&self) -> (usize, Option<usize>) {
 556         self.iter.size_hint()
 557     }
 558 }
 559
 560 impl<'a, T: 'a, A: 'a> DoubleEndedIterator for Iter<'a, T, A>
 561 where
 562     A: ArenaBehavior,
 563 {
 564     fn next_back(&mut self) -> Option<Self::Item> {
 565         add_id::<A, _>(self.iter.next_back(), self.arena_id)
 566     }
 567 }
 568
 569 impl<'a, T: 'a, A: 'a> ExactSizeIterator for Iter<'a, T, A>
 570 where
 571     A: ArenaBehavior,
 572 {
 573     fn len(&self) -> usize {
 574         self.iter.len()
 575     }
 576 }
 577
 578 impl<'a, T, A> IntoIterator for &'a Arena<T, A>
 579 where
 580     A: ArenaBehavior,
 581 {
 582     type Item = (A::Id, &'a T);
 583     type IntoIter = Iter<'a, T, A>;
 584
 585     #[inline]
 586     fn into_iter(self) -> Iter<'a, T, A> {
 587         Iter {
 588             arena_id: self.arena_id,
 589             iter: self.items.iter().enumerate(),
 590             _phantom: PhantomData,
 591         }
 592     }
 593 }
 594
 595 /// An iterator over `(Id, &mut T)` pairs in an arena.
 596 ///
 597 /// See [the `Arena::iter_mut()` method](./struct.Arena.html#method.iter_mut)
 598 /// for details.
 599 #[derive(Debug)]
 600 pub struct IterMut<'a, T: 'a, A: 'a> {
 601     arena_id: u32,
 602     iter: iter::Enumerate<slice::IterMut<'a, T>>,
 603     _phantom: PhantomData<fn() -> A>,
 604 }
 605
 606 impl<'a, T: 'a, A: 'a> Iterator for IterMut<'a, T, A>
 607 where
 608     A: ArenaBehavior,
 609 {
 610     type Item = (A::Id, &'a mut T);
 611
 612     #[inline]
 613     fn next(&mut self) -> Option<Self::Item> {
 614         add_id::<A, _>(self.iter.next(), self.arena_id)
 615     }
 616
 617     fn size_hint(&self) -> (usize, Option<usize>) {
 618         self.iter.size_hint()
 619     }
 620 }
 621
 622 impl<'a, T: 'a, A: 'a> DoubleEndedIterator for IterMut<'a, T, A>
 623 where
 624     A: ArenaBehavior,
 625 {
 626     fn next_back(&mut self) -> Option<Self::Item> {
 627         add_id::<A, _>(self.iter.next_back(), self.arena_id)
 628     }
 629 }
 630
 631 impl<'a, T: 'a, A: 'a> ExactSizeIterator for IterMut<'a, T, A>
 632 where
 633     A: ArenaBehavior,
 634 {
 635     fn len(&self) -> usize {
 636         self.iter.len()
 637     }
 638 }
 639
 640 impl<'a, T, A> IntoIterator for &'a mut Arena<T, A>
 641 where
 642     A: ArenaBehavior,
 643 {
 644     type Item = (A::Id, &'a mut T);
 645     type IntoIter = IterMut<'a, T, A>;
 646
 647     #[inline]
 648     fn into_iter(self) -> IterMut<'a, T, A> {
 649         IterMut {
 650             arena_id: self.arena_id,
 651             iter: self.items.iter_mut().enumerate(),
 652             _phantom: PhantomData,
 653         }
 654     }
 655 }
 656
 657 /// An iterator over `(Id, T)` pairs in an arena.
 658 #[derive(Debug)]
 659 pub struct IntoIter<T, A> {
 660     arena_id: u32,
 661     iter: iter::Enumerate<vec::IntoIter<T>>,
 662     _phantom: PhantomData<fn() -> A>,
 663 }
 664
 665 impl<T, A> Iterator for IntoIter<T, A>
 666 where
 667     A: ArenaBehavior,
 668 {
 669     type Item = (A::Id, T);
 670
 671     #[inline]
 672     fn next(&mut self) -> Option<Self::Item> {
 673         add_id::<A, _>(self.iter.next(), self.arena_id)
 674     }
 675
 676     fn size_hint(&self) -> (usize, Option<usize>) {
 677         self.iter.size_hint()
 678     }
 679 }
 680
 681 impl<T, A> DoubleEndedIterator for IntoIter<T, A>
 682 where
 683     A: ArenaBehavior,
 684 {
 685     fn next_back(&mut self) -> Option<Self::Item> {
 686         add_id::<A, _>(self.iter.next_back(), self.arena_id)
 687     }
 688 }
 689
 690 impl<T, A> ExactSizeIterator for IntoIter<T, A>
 691 where
 692     A: ArenaBehavior,
 693 {
 694     fn len(&self) -> usize {
 695         self.iter.len()
 696     }
 697 }
 698
 699 impl<T, A> IntoIterator for Arena<T, A>
 700 where
 701     A: ArenaBehavior,
 702 {
 703     type Item = (A::Id, T);
 704     type IntoIter = IntoIter<T, A>;
 705
 706     #[inline]
 707     fn into_iter(self) -> IntoIter<T, A> {
 708         IntoIter {
 709             arena_id: self.arena_id,
 710             iter: self.items.into_iter().enumerate(),
 711             _phantom: PhantomData,
 712         }
 713     }
 714 }
 715
 716 #[cfg(test)]
 717 mod tests {
 718     use super::*;
 719
 720     #[test]
 721     fn ids_are_send_sync() {
 722         fn assert_send_sync<T: Send + Sync>() {}
 723         struct Foo;
 724         assert_send_sync::<Id<Foo>>();
 725     }
 726 }