android/vendor/regex-automata-0.4.6/src/util/lazy.rs - toolchain/cargo-deny - Git at Google

 /*!
 A lazily initialized value for safe sharing between threads.

 The principal type in this module is `Lazy`, which makes it easy to construct
 values that are shared safely across multiple threads simultaneously.
 */

 use core::fmt;

 /// A lazily initialized value that implements `Deref` for `T`.
 ///
 /// A `Lazy` takes an initialization function and permits callers from any
 /// thread to access the result of that initialization function in a safe
 /// manner. In effect, this permits one-time initialization of global resources
 /// in a (possibly) multi-threaded program.
 ///
 /// This type and its functionality are available even when neither the `alloc`
 /// nor the `std` features are enabled. In exchange, a `Lazy` does **not**
 /// guarantee that the given `create` function is called at most once. It
 /// might be called multiple times. Moreover, a call to `Lazy::get` (either
 /// explicitly or implicitly via `Lazy`'s `Deref` impl) may block until a `T`
 /// is available.
 ///
 /// This is very similar to `lazy_static` or `once_cell`, except it doesn't
 /// guarantee that the initialization function will be run once and it works
 /// in no-alloc no-std environments. With that said, if you need stronger
 /// guarantees or a more flexible API, then it is recommended to use either
 /// `lazy_static` or `once_cell`.
 ///
 /// # Warning: may use a spin lock
 ///
 /// When this crate is compiled _without_ the `alloc` feature, then this type
 /// may used a spin lock internally. This can have subtle effects that may
 /// be undesirable. See [Spinlocks Considered Harmful][spinharm] for a more
 /// thorough treatment of this topic.
 ///
 /// [spinharm]: https://matklad.github.io/2020/01/02/spinlocks-considered-harmful.html
 ///
 /// # Example
 ///
 /// This type is useful for creating regexes once, and then using them from
 /// multiple threads simultaneously without worrying about synchronization.
 ///
 /// ```
 /// use regex_automata::{dfa::regex::Regex, util::lazy::Lazy, Match};
 ///
 /// static RE: Lazy<Regex> = Lazy::new(|| Regex::new("foo[0-9]+bar").unwrap());
 ///
 /// let expected = Some(Match::must(0, 3..14));
 /// assert_eq!(expected, RE.find(b"zzzfoo12345barzzz"));
 /// ```
 pub struct Lazy<T, F = fn() -> T>(lazy::Lazy<T, F>);

 impl<T, F> Lazy<T, F> {
     /// Create a new `Lazy` value that is initialized via the given function.
     ///
     /// The `T` type is automatically inferred from the return type of the
     /// `create` function given.
     pub const fn new(create: F) -> Lazy<T, F> {
         Lazy(lazy::Lazy::new(create))
     }
 }

 impl<T, F: Fn() -> T> Lazy<T, F> {
     /// Return a reference to the lazily initialized value.
     ///
     /// This routine may block if another thread is initializing a `T`.
     ///
     /// Note that given a `x` which has type `Lazy`, this must be called via
     /// `Lazy::get(x)` and not `x.get()`. This routine is defined this way
     /// because `Lazy` impls `Deref` with a target of `T`.
     ///
     /// # Panics
     ///
     /// This panics if the `create` function inside this lazy value panics.
     /// If the panic occurred in another thread, then this routine _may_ also
     /// panic (but is not guaranteed to do so).
     pub fn get(this: &Lazy<T, F>) -> &T {
         this.0.get()
     }
 }

 impl<T, F: Fn() -> T> core::ops::Deref for Lazy<T, F> {
     type Target = T;

     fn deref(&self) -> &T {
         Lazy::get(self)
     }
 }

 impl<T: fmt::Debug, F: Fn() -> T> fmt::Debug for Lazy<T, F> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         self.0.fmt(f)
     }
 }

 #[cfg(feature = "alloc")]
 mod lazy {
     use core::{
         fmt,
         marker::PhantomData,
         sync::atomic::{AtomicPtr, Ordering},
     };

     use alloc::boxed::Box;

     /// A non-std lazy initialized value.
     ///
     /// This might run the initialization function more than once, but will
     /// never block.
     ///
     /// I wish I could get these semantics into the non-alloc non-std Lazy
     /// type below, but I'm not sure how to do it. If you can do an alloc,
     /// then the implementation becomes very simple if you don't care about
     /// redundant work precisely because a pointer can be atomically swapped.
     ///
     /// Perhaps making this approach work in the non-alloc non-std case
     /// requires asking the caller for a pointer? It would make the API less
     /// convenient I think.
     pub(super) struct Lazy<T, F> {
         data: AtomicPtr<T>,
         create: F,
         // This indicates to the compiler that this type can drop T. It's not
         // totally clear how the absence of this marker could lead to trouble,
         // but putting here doesn't have any downsides so we hedge until somone
         // can from the Unsafe Working Group can tell us definitively that we
         // don't need it.
         //
         // See: https://github.com/BurntSushi/regex-automata/issues/30
         owned: PhantomData<Box<T>>,
     }

     // SAFETY: So long as T and &T (and F and &F) can themselves be safely
     // shared among threads, so to can a Lazy<T, _>. Namely, the Lazy API only
     // permits accessing a &T and initialization is free of data races. So if T
     // is thread safe, then so to is Lazy<T, _>.
     //
     // We specifically require that T: Send in order for Lazy<T> to be Sync.
     // Without that requirement, it's possible to send a T from one thread to
     // another via Lazy's destructor.
     //
     // It's not clear whether we need F: Send+Sync for Lazy to be Sync. But
     // we're conservative for now and keep both.
     unsafe impl<T: Send + Sync, F: Send + Sync> Sync for Lazy<T, F> {}

     impl<T, F> Lazy<T, F> {
         /// Create a new alloc but non-std lazy value that is racily
         /// initialized. That is, the 'create' function may be called more than
         /// once.
         pub(super) const fn new(create: F) -> Lazy<T, F> {
             Lazy {
                 data: AtomicPtr::new(core::ptr::null_mut()),
                 create,
                 owned: PhantomData,
             }
         }
     }

     impl<T, F: Fn() -> T> Lazy<T, F> {
         /// Get the underlying lazy value. If it hasn't been initialized
         /// yet, then always attempt to initialize it (even if some other
         /// thread is initializing it) and atomically attach it to this lazy
         /// value before returning it.
         pub(super) fn get(&self) -> &T {
             if let Some(data) = self.poll() {
                 return data;
             }
             let data = (self.create)();
             let mut ptr = Box::into_raw(Box::new(data));
             // We attempt to stuff our initialized value into our atomic
             // pointer. Upon success, we don't need to do anything. But if
             // someone else beat us to the punch, then we need to make sure
             // our newly created value is dropped.
             let result = self.data.compare_exchange(
                 core::ptr::null_mut(),
                 ptr,
                 Ordering::AcqRel,
                 Ordering::Acquire,
             );
             if let Err(old) = result {
                 // SAFETY: We created 'ptr' via Box::into_raw above, so turning
                 // it back into a Box via from_raw is safe.
                 drop(unsafe { Box::from_raw(ptr) });
                 ptr = old;
             }
             // SAFETY: We just set the pointer above to a non-null value, even
             // in the error case, and set it to a fully initialized value
             // returned by 'create'.
             unsafe { &*ptr }
         }

         /// If this lazy value has been initialized successfully, then return
         /// that value. Otherwise return None immediately. This never attempts
         /// to run initialization itself.
         fn poll(&self) -> Option<&T> {
             let ptr = self.data.load(Ordering::Acquire);
             if ptr.is_null() {
                 return None;
             }
             // SAFETY: We just checked that the pointer is not null. Since it's
             // not null, it must have been fully initialized by 'get' at some
             // point.
             Some(unsafe { &*ptr })
         }
     }

     impl<T: fmt::Debug, F: Fn() -> T> fmt::Debug for Lazy<T, F> {
         fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
             f.debug_struct("Lazy").field("data", &self.poll()).finish()
         }
     }

     impl<T, F> Drop for Lazy<T, F> {
         fn drop(&mut self) {
             let ptr = *self.data.get_mut();
             if !ptr.is_null() {
                 // SAFETY: We just checked that 'ptr' is not null. And since
                 // we have exclusive access, there are no races to worry about.
                 drop(unsafe { Box::from_raw(ptr) });
             }
         }
     }
 }

 #[cfg(not(feature = "alloc"))]
 mod lazy {
     use core::{
         cell::Cell,
         fmt,
         mem::MaybeUninit,
         panic::{RefUnwindSafe, UnwindSafe},
         sync::atomic::{AtomicU8, Ordering},
     };

     /// Our 'Lazy' value can be in one of three states:
     ///
     /// * INIT is where it starts, and also ends up back here if the
     /// 'create' routine panics.
     /// * BUSY is where it sits while initialization is running in exactly
     /// one thread.
     /// * DONE is where it sits after 'create' has completed and 'data' has
     /// been fully initialized.
     const LAZY_STATE_INIT: u8 = 0;
     const LAZY_STATE_BUSY: u8 = 1;
     const LAZY_STATE_DONE: u8 = 2;

     /// A non-alloc non-std lazy initialized value.
     ///
     /// This guarantees initialization only happens once, but uses a spinlock
     /// to block in the case of simultaneous access. Blocking occurs so that
     /// one thread waits while another thread initializes the value.
     ///
     /// I would much rather have the semantics of the 'alloc' Lazy type above.
     /// Namely, that we might run the initialization function more than once,
     /// but we never otherwise block. However, I don't know how to do that in
     /// a non-alloc non-std context.
     pub(super) struct Lazy<T, F> {
         state: AtomicU8,
         create: Cell<Option<F>>,
         data: Cell<MaybeUninit<T>>,
     }

     // SAFETY: So long as T and &T (and F and &F) can themselves be safely
     // shared among threads, so to can a Lazy<T, _>. Namely, the Lazy API only
     // permits accessing a &T and initialization is free of data races. So if T
     // is thread safe, then so to is Lazy<T, _>.
     unsafe impl<T: Send + Sync, F: Send + Sync> Sync for Lazy<T, F> {}
     // A reference to a Lazy is unwind safe because we specifically take
     // precautions to poison all accesses to a Lazy if the caller-provided
     // 'create' function panics.
     impl<T: UnwindSafe, F: UnwindSafe + RefUnwindSafe> RefUnwindSafe
         for Lazy<T, F>
     {
     }

     impl<T, F> Lazy<T, F> {
         /// Create a new non-alloc non-std lazy value that is initialized
         /// exactly once on first use using the given function.
         pub(super) const fn new(create: F) -> Lazy<T, F> {
             Lazy {
                 state: AtomicU8::new(LAZY_STATE_INIT),
                 create: Cell::new(Some(create)),
                 data: Cell::new(MaybeUninit::uninit()),
             }
         }
     }

     impl<T, F: FnOnce() -> T> Lazy<T, F> {
         /// Get the underlying lazy value. If it isn't been initialized
         /// yet, then either initialize it or block until some other thread
         /// initializes it. If the 'create' function given to Lazy::new panics
         /// (even in another thread), then this panics too.
         pub(super) fn get(&self) -> &T {
             // This is effectively a spinlock. We loop until we enter a DONE
             // state, and if possible, initialize it ourselves. The only way
             // we exit the loop is if 'create' panics, we initialize 'data' or
             // some other thread initializes 'data'.
             //
             // Yes, I have read spinlocks considered harmful[1]. And that
             // article is why this spinlock is only active when 'alloc' isn't
             // enabled. I did this because I don't think there is really
             // another choice without 'alloc', other than not providing this at
             // all. But I think that's a big bummer.
             //
             // [1]: https://matklad.github.io/2020/01/02/spinlocks-considered-harmful.html
             while self.state.load(Ordering::Acquire) != LAZY_STATE_DONE {
                 // Check if we're the first ones to get here. If so, we'll be
                 // the ones who initialize.
                 let result = self.state.compare_exchange(
                     LAZY_STATE_INIT,
                     LAZY_STATE_BUSY,
                     Ordering::AcqRel,
                     Ordering::Acquire,
                 );
                 // This means we saw the INIT state and nobody else can. So we
                 // must take responsibility for initializing. And by virtue of
                 // observing INIT, we have also told anyone else trying to
                 // get here that we are BUSY. If someone else sees BUSY, then
                 // they will spin until we finish initialization.
                 if let Ok(_) = result {
                     // Since we are guaranteed to be the only ones here, we
                     // know that 'create' is there... Unless someone else got
                     // here before us and 'create' panicked. In which case,
                     // 'self.create' is now 'None' and we forward the panic
                     // to the caller. (i.e., We implement poisoning.)
                     //
                     // SAFETY: Our use of 'self.state' guarantees that we are
                     // the only thread executing this line, and thus there are
                     // no races.
                     let create = unsafe {
                         (*self.create.as_ptr()).take().expect(
                             "Lazy's create function panicked, \
                              preventing initialization,
                              poisoning current thread",
                         )
                     };
                     let guard = Guard { state: &self.state };
                     // SAFETY: Our use of 'self.state' guarantees that we are
                     // the only thread executing this line, and thus there are
                     // no races.
                     unsafe {
                         (*self.data.as_ptr()).as_mut_ptr().write(create());
                     }
                     // All is well. 'self.create' ran successfully, so we
                     // forget the guard.
                     core::mem::forget(guard);
                     // Everything is initialized, so we can declare success.
                     self.state.store(LAZY_STATE_DONE, Ordering::Release);
                     break;
                 }
                 core::hint::spin_loop();
             }
             // We only get here if data is fully initialized, and thus poll
             // will always return something.
             self.poll().unwrap()
         }

         /// If this lazy value has been initialized successfully, then return
         /// that value. Otherwise return None immediately. This never blocks.
         fn poll(&self) -> Option<&T> {
             if self.state.load(Ordering::Acquire) == LAZY_STATE_DONE {
                 // SAFETY: The DONE state only occurs when data has been fully
                 // initialized.
                 Some(unsafe { &*(*self.data.as_ptr()).as_ptr() })
             } else {
                 None
             }
         }
     }

     impl<T: fmt::Debug, F: FnMut() -> T> fmt::Debug for Lazy<T, F> {
         fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
             f.debug_struct("Lazy")
                 .field("state", &self.state.load(Ordering::Acquire))
                 .field("create", &"<closure>")
                 .field("data", &self.poll())
                 .finish()
         }
     }

     impl<T, F> Drop for Lazy<T, F> {
         fn drop(&mut self) {
             if *self.state.get_mut() == LAZY_STATE_DONE {
                 // SAFETY: state is DONE if and only if data has been fully
                 // initialized. At which point, it is safe to drop.
                 unsafe {
                     self.data.get_mut().assume_init_drop();
                 }
             }
         }
     }

     /// A guard that will reset a Lazy's state back to INIT when dropped. The
     /// idea here is to 'forget' this guard on success. On failure (when a
     /// panic occurs), the Drop impl runs and causes all in-progress and future
     /// 'get' calls to panic. Without this guard, all in-progress and future
     /// 'get' calls would spin forever. Crashing is much better than getting
     /// stuck in an infinite loop.
     struct Guard<'a> {
         state: &'a AtomicU8,
     }

     impl<'a> Drop for Guard<'a> {
         fn drop(&mut self) {
             // We force ourselves back into an INIT state. This will in turn
             // cause any future 'get' calls to attempt calling 'self.create'
             // again which will in turn panic because 'self.create' will now
             // be 'None'.
             self.state.store(LAZY_STATE_INIT, Ordering::Release);
         }
     }
 }

 #[cfg(test)]
 mod tests {
     use super::*;

     fn assert_send<T: Send>() {}
     fn assert_sync<T: Sync>() {}
     fn assert_unwind<T: core::panic::UnwindSafe>() {}
     fn assert_refunwind<T: core::panic::RefUnwindSafe>() {}

     #[test]
     fn oibits() {
         assert_send::<Lazy<u64>>();
         assert_sync::<Lazy<u64>>();
         assert_unwind::<Lazy<u64>>();
         assert_refunwind::<Lazy<u64>>();
     }

     // This is a regression test because we used to rely on the inferred Sync
     // impl for the Lazy type defined above (for 'alloc' mode). In the
     // inferred impl, it only requires that T: Sync for Lazy<T>: Sync. But
     // if we have that, we can actually make use of the fact that Lazy<T> drops
     // T to create a value on one thread and drop it on another. This *should*
     // require T: Send, but our missing bounds before let it sneak by.
     //
     // Basically, this test should not compile, so we... comment it out. We
     // don't have a great way of testing compile-fail tests right now.
     //
     // See: https://github.com/BurntSushi/regex-automata/issues/30
     /*
     #[test]
     fn sync_not_send() {
         #[allow(dead_code)]
         fn inner<T: Sync + Default>() {
             let lazy = Lazy::new(move || T::default());
             std::thread::scope(|scope| {
                 scope.spawn(|| {
                     Lazy::get(&lazy); // We create T in this thread
                 });
             });
             // And drop in this thread.
             drop(lazy);
             // So we have send a !Send type over threads. (with some more
             // legwork, its possible to even sneak the value out of drop
             // through thread local)
         }
     }
     */
 }
	/*!
	A lazily initialized value for safe sharing between threads.

	The principal type in this module is `Lazy`, which makes it easy to construct
	values that are shared safely across multiple threads simultaneously.
	*/

	use core::fmt;

	/// A lazily initialized value that implements `Deref` for `T`.
	///
	/// A `Lazy` takes an initialization function and permits callers from any
	/// thread to access the result of that initialization function in a safe
	/// manner. In effect, this permits one-time initialization of global resources
	/// in a (possibly) multi-threaded program.
	///
	/// This type and its functionality are available even when neither the `alloc`
	/// nor the `std` features are enabled. In exchange, a `Lazy` does not
	/// guarantee that the given `create` function is called at most once. It
	/// might be called multiple times. Moreover, a call to `Lazy::get` (either
	/// explicitly or implicitly via `Lazy`'s `Deref` impl) may block until a `T`
	/// is available.
	///
	/// This is very similar to `lazy_static` or `once_cell`, except it doesn't
	/// guarantee that the initialization function will be run once and it works
	/// in no-alloc no-std environments. With that said, if you need stronger
	/// guarantees or a more flexible API, then it is recommended to use either
	/// `lazy_static` or `once_cell`.
	///
	/// # Warning: may use a spin lock
	///
	/// When this crate is compiled _without_ the `alloc` feature, then this type
	/// may used a spin lock internally. This can have subtle effects that may
	/// be undesirable. See [Spinlocks Considered Harmful][spinharm] for a more
	/// thorough treatment of this topic.
	///
	/// [spinharm]: https://matklad.github.io/2020/01/02/spinlocks-considered-harmful.html
	///
	/// # Example
	///
	/// This type is useful for creating regexes once, and then using them from
	/// multiple threads simultaneously without worrying about synchronization.
	///
	/// ```
	/// use regex_automata::{dfa::regex::Regex, util::lazy::Lazy, Match};
	///
	/// static RE: Lazy<Regex> = Lazy::new(\|\| Regex::new("foo[0-9]+bar").unwrap());
	///
	/// let expected = Some(Match::must(0, 3..14));
	/// assert_eq!(expected, RE.find(b"zzzfoo12345barzzz"));
	/// ```
	pub struct Lazy<T, F = fn() -> T>(lazy::Lazy<T, F>);

	impl<T, F> Lazy<T, F> {
	/// Create a new `Lazy` value that is initialized via the given function.
	///
	/// The `T` type is automatically inferred from the return type of the
	/// `create` function given.
	pub const fn new(create: F) -> Lazy<T, F> {
	Lazy(lazy::Lazy::new(create))
	}
	}

	impl<T, F: Fn() -> T> Lazy<T, F> {
	/// Return a reference to the lazily initialized value.
	///
	/// This routine may block if another thread is initializing a `T`.
	///
	/// Note that given a `x` which has type `Lazy`, this must be called via
	/// `Lazy::get(x)` and not `x.get()`. This routine is defined this way
	/// because `Lazy` impls `Deref` with a target of `T`.
	///
	/// # Panics
	///
	/// This panics if the `create` function inside this lazy value panics.
	/// If the panic occurred in another thread, then this routine _may_ also
	/// panic (but is not guaranteed to do so).
	pub fn get(this: &Lazy<T, F>) -> &T {
	this.0.get()
	}
	}

	impl<T, F: Fn() -> T> core::ops::Deref for Lazy<T, F> {
	type Target = T;

	fn deref(&self) -> &T {
	Lazy::get(self)
	}
	}

	impl<T: fmt::Debug, F: Fn() -> T> fmt::Debug for Lazy<T, F> {
	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
	self.0.fmt(f)
	}
	}

	#[cfg(feature = "alloc")]
	mod lazy {
	use core::{
	fmt,
	marker::PhantomData,
	sync::atomic::{AtomicPtr, Ordering},
	};

	use alloc::boxed::Box;

	/// A non-std lazy initialized value.
	///
	/// This might run the initialization function more than once, but will
	/// never block.
	///
	/// I wish I could get these semantics into the non-alloc non-std Lazy
	/// type below, but I'm not sure how to do it. If you can do an alloc,
	/// then the implementation becomes very simple if you don't care about
	/// redundant work precisely because a pointer can be atomically swapped.
	///
	/// Perhaps making this approach work in the non-alloc non-std case
	/// requires asking the caller for a pointer? It would make the API less
	/// convenient I think.
	pub(super) struct Lazy<T, F> {
	data: AtomicPtr<T>,
	create: F,
	// This indicates to the compiler that this type can drop T. It's not
	// totally clear how the absence of this marker could lead to trouble,
	// but putting here doesn't have any downsides so we hedge until somone
	// can from the Unsafe Working Group can tell us definitively that we
	// don't need it.
	//
	// See: https://github.com/BurntSushi/regex-automata/issues/30
	owned: PhantomData<Box<T>>,
	}

	// SAFETY: So long as T and &T (and F and &F) can themselves be safely
	// shared among threads, so to can a Lazy<T, _>. Namely, the Lazy API only
	// permits accessing a &T and initialization is free of data races. So if T
	// is thread safe, then so to is Lazy<T, _>.
	//
	// We specifically require that T: Send in order for Lazy<T> to be Sync.
	// Without that requirement, it's possible to send a T from one thread to
	// another via Lazy's destructor.
	//
	// It's not clear whether we need F: Send+Sync for Lazy to be Sync. But
	// we're conservative for now and keep both.
	unsafe impl<T: Send + Sync, F: Send + Sync> Sync for Lazy<T, F> {}

	impl<T, F> Lazy<T, F> {
	/// Create a new alloc but non-std lazy value that is racily
	/// initialized. That is, the 'create' function may be called more than
	/// once.
	pub(super) const fn new(create: F) -> Lazy<T, F> {
	Lazy {
	data: AtomicPtr::new(core::ptr::null_mut()),
	create,
	owned: PhantomData,
	}
	}
	}

	impl<T, F: Fn() -> T> Lazy<T, F> {
	/// Get the underlying lazy value. If it hasn't been initialized
	/// yet, then always attempt to initialize it (even if some other
	/// thread is initializing it) and atomically attach it to this lazy
	/// value before returning it.
	pub(super) fn get(&self) -> &T {
	if let Some(data) = self.poll() {
	return data;
	}
	let data = (self.create)();
	let mut ptr = Box::into_raw(Box::new(data));
	// We attempt to stuff our initialized value into our atomic
	// pointer. Upon success, we don't need to do anything. But if
	// someone else beat us to the punch, then we need to make sure
	// our newly created value is dropped.
	let result = self.data.compare_exchange(
	core::ptr::null_mut(),
	ptr,
	Ordering::AcqRel,
	Ordering::Acquire,
	);
	if let Err(old) = result {
	// SAFETY: We created 'ptr' via Box::into_raw above, so turning
	// it back into a Box via from_raw is safe.
	drop(unsafe { Box::from_raw(ptr) });
	ptr = old;
	}
	// SAFETY: We just set the pointer above to a non-null value, even
	// in the error case, and set it to a fully initialized value
	// returned by 'create'.
	unsafe { &*ptr }
	}

	/// If this lazy value has been initialized successfully, then return
	/// that value. Otherwise return None immediately. This never attempts
	/// to run initialization itself.
	fn poll(&self) -> Option<&T> {
	let ptr = self.data.load(Ordering::Acquire);
	if ptr.is_null() {
	return None;
	}
	// SAFETY: We just checked that the pointer is not null. Since it's
	// not null, it must have been fully initialized by 'get' at some
	// point.
	Some(unsafe { &*ptr })
	}
	}

	impl<T: fmt::Debug, F: Fn() -> T> fmt::Debug for Lazy<T, F> {
	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
	f.debug_struct("Lazy").field("data", &self.poll()).finish()
	}
	}

	impl<T, F> Drop for Lazy<T, F> {
	fn drop(&mut self) {
	let ptr = *self.data.get_mut();
	if !ptr.is_null() {
	// SAFETY: We just checked that 'ptr' is not null. And since
	// we have exclusive access, there are no races to worry about.
	drop(unsafe { Box::from_raw(ptr) });
	}
	}
	}
	}

	#[cfg(not(feature = "alloc"))]
	mod lazy {
	use core::{
	cell::Cell,
	fmt,
	mem::MaybeUninit,
	panic::{RefUnwindSafe, UnwindSafe},
	sync::atomic::{AtomicU8, Ordering},
	};

	/// Our 'Lazy' value can be in one of three states:
	///
	/// * INIT is where it starts, and also ends up back here if the
	/// 'create' routine panics.
	/// * BUSY is where it sits while initialization is running in exactly
	/// one thread.
	/// * DONE is where it sits after 'create' has completed and 'data' has
	/// been fully initialized.
	const LAZY_STATE_INIT: u8 = 0;
	const LAZY_STATE_BUSY: u8 = 1;
	const LAZY_STATE_DONE: u8 = 2;

	/// A non-alloc non-std lazy initialized value.
	///
	/// This guarantees initialization only happens once, but uses a spinlock
	/// to block in the case of simultaneous access. Blocking occurs so that
	/// one thread waits while another thread initializes the value.
	///
	/// I would much rather have the semantics of the 'alloc' Lazy type above.
	/// Namely, that we might run the initialization function more than once,
	/// but we never otherwise block. However, I don't know how to do that in
	/// a non-alloc non-std context.
	pub(super) struct Lazy<T, F> {
	state: AtomicU8,
	create: Cell<Option<F>>,
	data: Cell<MaybeUninit<T>>,
	}

	// SAFETY: So long as T and &T (and F and &F) can themselves be safely
	// shared among threads, so to can a Lazy<T, _>. Namely, the Lazy API only
	// permits accessing a &T and initialization is free of data races. So if T
	// is thread safe, then so to is Lazy<T, _>.
	unsafe impl<T: Send + Sync, F: Send + Sync> Sync for Lazy<T, F> {}
	// A reference to a Lazy is unwind safe because we specifically take
	// precautions to poison all accesses to a Lazy if the caller-provided
	// 'create' function panics.
	impl<T: UnwindSafe, F: UnwindSafe + RefUnwindSafe> RefUnwindSafe
	for Lazy<T, F>
	{
	}

	impl<T, F> Lazy<T, F> {
	/// Create a new non-alloc non-std lazy value that is initialized
	/// exactly once on first use using the given function.
	pub(super) const fn new(create: F) -> Lazy<T, F> {
	Lazy {
	state: AtomicU8::new(LAZY_STATE_INIT),
	create: Cell::new(Some(create)),
	data: Cell::new(MaybeUninit::uninit()),
	}
	}
	}

	impl<T, F: FnOnce() -> T> Lazy<T, F> {
	/// Get the underlying lazy value. If it isn't been initialized
	/// yet, then either initialize it or block until some other thread
	/// initializes it. If the 'create' function given to Lazy::new panics
	/// (even in another thread), then this panics too.
	pub(super) fn get(&self) -> &T {
	// This is effectively a spinlock. We loop until we enter a DONE
	// state, and if possible, initialize it ourselves. The only way
	// we exit the loop is if 'create' panics, we initialize 'data' or
	// some other thread initializes 'data'.
	//
	// Yes, I have read spinlocks considered harmful[1]. And that
	// article is why this spinlock is only active when 'alloc' isn't
	// enabled. I did this because I don't think there is really
	// another choice without 'alloc', other than not providing this at
	// all. But I think that's a big bummer.
	//
	// [1]: https://matklad.github.io/2020/01/02/spinlocks-considered-harmful.html
	while self.state.load(Ordering::Acquire) != LAZY_STATE_DONE {
	// Check if we're the first ones to get here. If so, we'll be
	// the ones who initialize.
	let result = self.state.compare_exchange(
	LAZY_STATE_INIT,
	LAZY_STATE_BUSY,
	Ordering::AcqRel,
	Ordering::Acquire,
	);
	// This means we saw the INIT state and nobody else can. So we
	// must take responsibility for initializing. And by virtue of
	// observing INIT, we have also told anyone else trying to
	// get here that we are BUSY. If someone else sees BUSY, then
	// they will spin until we finish initialization.
	if let Ok(_) = result {
	// Since we are guaranteed to be the only ones here, we
	// know that 'create' is there... Unless someone else got
	// here before us and 'create' panicked. In which case,
	// 'self.create' is now 'None' and we forward the panic
	// to the caller. (i.e., We implement poisoning.)
	//
	// SAFETY: Our use of 'self.state' guarantees that we are
	// the only thread executing this line, and thus there are
	// no races.
	let create = unsafe {
	(*self.create.as_ptr()).take().expect(
	"Lazy's create function panicked, \
	preventing initialization,
	poisoning current thread",
	)
	};
	let guard = Guard { state: &self.state };
	// SAFETY: Our use of 'self.state' guarantees that we are
	// the only thread executing this line, and thus there are
	// no races.
	unsafe {
	(*self.data.as_ptr()).as_mut_ptr().write(create());
	}
	// All is well. 'self.create' ran successfully, so we
	// forget the guard.
	core::mem::forget(guard);
	// Everything is initialized, so we can declare success.
	self.state.store(LAZY_STATE_DONE, Ordering::Release);
	break;
	}
	core::hint::spin_loop();
	}
	// We only get here if data is fully initialized, and thus poll
	// will always return something.
	self.poll().unwrap()
	}

	/// If this lazy value has been initialized successfully, then return
	/// that value. Otherwise return None immediately. This never blocks.
	fn poll(&self) -> Option<&T> {
	if self.state.load(Ordering::Acquire) == LAZY_STATE_DONE {
	// SAFETY: The DONE state only occurs when data has been fully
	// initialized.
	Some(unsafe { &(self.data.as_ptr()).as_ptr() })
	} else {
	None
	}
	}
	}

	impl<T: fmt::Debug, F: FnMut() -> T> fmt::Debug for Lazy<T, F> {
	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
	f.debug_struct("Lazy")
	.field("state", &self.state.load(Ordering::Acquire))
	.field("create", &"<closure>")
	.field("data", &self.poll())
	.finish()
	}
	}

	impl<T, F> Drop for Lazy<T, F> {
	fn drop(&mut self) {
	if *self.state.get_mut() == LAZY_STATE_DONE {
	// SAFETY: state is DONE if and only if data has been fully
	// initialized. At which point, it is safe to drop.
	unsafe {
	self.data.get_mut().assume_init_drop();
	}
	}
	}
	}

	/// A guard that will reset a Lazy's state back to INIT when dropped. The
	/// idea here is to 'forget' this guard on success. On failure (when a
	/// panic occurs), the Drop impl runs and causes all in-progress and future
	/// 'get' calls to panic. Without this guard, all in-progress and future
	/// 'get' calls would spin forever. Crashing is much better than getting
	/// stuck in an infinite loop.
	struct Guard<'a> {
	state: &'a AtomicU8,
	}

	impl<'a> Drop for Guard<'a> {
	fn drop(&mut self) {
	// We force ourselves back into an INIT state. This will in turn
	// cause any future 'get' calls to attempt calling 'self.create'
	// again which will in turn panic because 'self.create' will now
	// be 'None'.
	self.state.store(LAZY_STATE_INIT, Ordering::Release);
	}
	}
	}

	#[cfg(test)]
	mod tests {
	use super::*;

	fn assert_send<T: Send>() {}
	fn assert_sync<T: Sync>() {}
	fn assert_unwind<T: core::panic::UnwindSafe>() {}
	fn assert_refunwind<T: core::panic::RefUnwindSafe>() {}

	#[test]
	fn oibits() {
	assert_send::<Lazy<u64>>();
	assert_sync::<Lazy<u64>>();
	assert_unwind::<Lazy<u64>>();
	assert_refunwind::<Lazy<u64>>();
	}

	// This is a regression test because we used to rely on the inferred Sync
	// impl for the Lazy type defined above (for 'alloc' mode). In the
	// inferred impl, it only requires that T: Sync for Lazy<T>: Sync. But
	// if we have that, we can actually make use of the fact that Lazy<T> drops
	// T to create a value on one thread and drop it on another. This should
	// require T: Send, but our missing bounds before let it sneak by.
	//
	// Basically, this test should not compile, so we... comment it out. We
	// don't have a great way of testing compile-fail tests right now.
	//
	// See: https://github.com/BurntSushi/regex-automata/issues/30
	/*
	#[test]
	fn sync_not_send() {
	#[allow(dead_code)]
	fn inner<T: Sync + Default>() {
	let lazy = Lazy::new(move \|\| T::default());
	std::thread::scope(\|scope\| {
	scope.spawn(\|\| {
	Lazy::get(&lazy); // We create T in this thread
	});
	});
	// And drop in this thread.
	drop(lazy);
	// So we have send a !Send type over threads. (with some more
	// legwork, its possible to even sneak the value out of drop
	// through thread local)
	}
	}
	*/
	}