Rust: Tracking Issue for `once_cell`

[KodrAus]

This is a tracking issue for the RFC "standard lazy types" (rust-lang/rfcs#2788).
The feature gate for the issue is #![feature(once_cell)].

Prposed API:

mod core_lazy {
    pub struct OnceCell<T>;

    impl<T> Default for OnceCell<T> {}
    impl<T: Debug> Debug for OnceCell<T> {}
    impl<T: Clone> Clone for OnceCell<T> {}
    impl<T: PartialEq> PartialEq for OnceCell<T> {}
    impl<T: Eq> Eq for OnceCell<T> {}
    impl<T> From<T> for OnceCell<T> {}
    impl<T> OnceCell<T> {
        pub const fn new() -> OnceCell<T>;
        pub fn get(&self) -> Option<&T>;
        pub fn get_mut(&mut self) -> Option<&mut T>;
        pub fn set(&self, value: T) -> Result<(), T>;
        pub fn get_or_init<F>(&self, f: F) -> &T
        where
            F: FnOnce() -> T,
        ;
        pub fn get_or_try_init<F, E>(&self, f: F) -> Result<&T, E>
        where
            F: FnOnce() -> Result<T, E>,
        ;
        pub fn into_inner(self) -> Option<T>;
        pub fn take(&mut self) -> Option<T>;
    }

    pub struct Lazy<T, F = fn() -> T>;

    impl<T: Default> Default for Lazy<T> {}
    impl<T: fmt::Debug, F> fmt::Debug for Lazy<T, F> {}
    impl<T, F: FnOnce() -> T> Deref for Lazy<T, F> {}
    impl<T, F> Lazy<T, F> {
        pub const fn new(init: F) -> Lazy<T, F>;
    }
    impl<T, F: FnOnce() -> T> Lazy<T, F> {
        pub fn force(this: &Lazy<T, F>) -> &T;
    }
}

mod std_lazy {
    pub use core::lazy::*;

    pub struct SyncOnceCell<T>;

    unsafe impl<T: Sync + Send> Sync for SyncOnceCell<T> {}
    unsafe impl<T: Send> Send for SyncOnceCell<T> {}
    impl<T: RefUnwindSafe + UnwindSafe> RefUnwindSafe for SyncOnceCell<T> {}
    impl<T: UnwindSafe> UnwindSafe for SyncOnceCell<T> {}
    impl<T> Default for SyncOnceCell<T> {}
    impl<T: Debug> Debug for SyncOnceCell<T> {}
    impl<T: Clone> Clone for SyncOnceCell<T> {}
    impl<T> From<T> for SyncOnceCell<T> {}
    impl<T: PartialEq> PartialEq for SyncOnceCell<T> {}
    impl<T: Eq> Eq for SyncOnceCell<T> {}
    impl<T> SyncOnceCell<T> {
        pub const fn new() -> SyncOnceCell<T>;
        pub fn get(&self) -> Option<&T>;
        pub fn get_mut(&mut self) -> Option<&mut T>;
        pub fn set(&self, value: T) -> Result<(), T>;
        pub fn get_or_init<F>(&self, f: F) -> &T
        where
            F: FnOnce() -> T,
        ;
        pub fn get_or_try_init<F, E>(&self, f: F) -> Result<&T, E>
        where
            F: FnOnce() -> Result<T, E>,
        ;
        pub fn into_inner(mut self) -> Option<T>;
        pub fn take(&mut self) -> Option<T>;
    }

    pub struct SyncLazy<T, F = fn() -> T>;

    impl<T: fmt::Debug, F> fmt::Debug for SyncLazy<T, F> {}
    unsafe impl<T, F: Send> Sync for SyncLazy<T, F> where SyncOnceCell<T>: Sync {}
    impl<T, F: UnwindSafe> RefUnwindSafe for SyncLazy<T, F> where SyncOnceCell<T>: RefUnwindSafe {}
    impl<T, F: UnwindSafe> UnwindSafe for SyncLazy<T, F> where SyncOnceCell<T>: UnwindSafe {}
    impl<T, F: FnOnce() -> T> Deref for SyncLazy<T, F> {}
    impl<T: Default> Default for SyncLazy<T> {}
    impl<T, F> SyncLazy<T, F> {
        pub const fn new(f: F) -> SyncLazy<T, F>;
    }
    impl<T, F: FnOnce() -> T> SyncLazy<T, F> {
        pub fn force(this: &SyncLazy<T, F>) -> &T;
    }
}

About tracking issues

Tracking issues are used to record the overall progress of implementation.
They are also uses as hubs connecting to other relevant issues, e.g., bugs or open design questions.
A tracking issue is however not meant for large scale discussion, questions, or bug reports about a feature.
Instead, open a dedicated issue for the specific matter and add the relevant feature gate label.

Steps

• [ ] Complete the RFC process over at https://github.com/rust-lang/rfcs/pull/2788
• [ ] Adjust documentation (see instructions on rustc-dev-guide)
• [ ] Stabilization PR (see instructions on rustc-dev-guide)

Unresolved Questions

Inlined from #72414:

• [ ] Naming. I'm ok to just roll with the Sync prefix like SyncLazy for now, but have a personal preference for Atomic like AtomicLazy.
• [x] [Poisoning](https://github.com/rust-lang/rfcs/pull/2788#discussion_r366725768). It seems like there's some regret around poisoning in other std::sync types that we might want to just avoid upfront for std::lazy, especially if that would align with a future std::mutex that doesn't poison. Personally, if we're adding these types to std::lazy instead of std::sync, I'd be on-board with not worrying about poisoning in std::lazy, and potentially deprecating std::sync::Once and lazy_static in favour of std::lazy down the track if it's possible, rather than attempting to replicate their behavior. cc @Amanieu @sfackler.
• [x] [Consider makingSyncOnceCell::get blocking](https://github.com/matklad/once_cell/pull/92). There doesn't seem to be consensus in the linked PR on whether or not that's strictly better than the non-blocking variant. (resolved in https://github.com/rust-lang/rust/issues/74465#issuecomment-663414310).
• [ ] [Atomic Ordering](https://github.com/rust-lang/rfcs/pull/2788#issuecomment-570555592). the implementation currently use Release/Acquire, but it could also use the elusive Consume ordering. Should we spec that we guarantee Release/Acquire?
• [x] [Sync no_std subset](https://github.com/rust-lang/rfcs/pull/2788#issuecomment-569845023). It seems plausible that we might provide some subset of SyncOnceCell in no_std. I think there's consensus that we don't want to include "blocking" parts of API, but it's unclear if non-blocking subset (get+set) would be useful. (resolved in https://github.com/rust-lang/rust/issues/74465#issuecomment-725360596).
• [ ] [Method naming](https://github.com/rust-lang/rust/issues/74465#issuecomment-726020743) is get_or[_try]_init the best name?

Implementation history

• #68198 (closed in favor of #72414)
• #72414 initial imlementation
• #74814 fixed UnwindSafe bounds

[matklad]

Let's cross-out the "should get be blocking?" concern. I decided against this for once_cell, for the following reasons:

• it's makes Clone, Eq, Debug blocking, which is surprising
• the original issue that prompted this question used Lazy, and Lazy is immune from this issue, as it always uses blocking get_or_init.

[matklad]

Added two more open questions from the RFC.

[matklad]

I've added a summary of proposed API to the issue description.

I wonder if makes sense for @rust-lang/libs to do a sort of "API review" here: this is a pretty big chunk of API, and we tried to avoid bike shedding on the RFC.

[matklad]

Here's an interesting use-case for non-blocking subset of OnceCell -- building cyclic data structures: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=4eceeefc224cdcc719962a9a0e1f72fc

[withoutboats]

I strongly expect a method called get to be nonblocking. I am softly in favor of adding a wait API that blocks, but would prefer that it be added in a separate feature later based on demand.

[matklad]

Yeah, to be clear, there's a consensus that get should be non-blocking, the question is resolved. What is not completely solved in my mind, is where we should have core::lazy::SyncOnceCell. That's possible in theory (by only providing get and set methods), but would be hacky to implement, and of questionable usefulness. The above example is a new use-case for that thing.

[m-ou-se]

Naming. I'm ok to just roll with the Sync prefix like SyncLazy for now, but have a personal preference for Atomic like AtomicLazy.

I don't think Atomic would be the right word for these. Rust's Atomic types and operations (including Arc) never block and never involve the operating system's scheduler (they're all defined in core or alloc, not std). They're all directly based on the basic atomic operations supported by the processor architecture itself.

I'd expect something that's named AtomicLazy/AtomicOnceCell to do the same. And that's something that already exists as another valid strategy for certain Lazy/OnceCell-like types: Instead of blocking all but one thread when multiple threads encounter an 'empty' cell, it wouldn't block but run the initialization function on each of these threads. The first thread to finish atomically stores its initialized value in the cell, and the others simply drop() the value they created.

The std does something similar in a few places (although not wrapped in a type or publicly exposed). For example, here:

https://github.com/rust-lang/rust/blob/a835b483fe0418b48ca44afb65cd0dd6bad4eb9b/library/std/src/sys/windows/compat.rs#L65-L67

And here:

https://github.com/rust-lang/rust/blob/a835b483fe0418b48ca44afb65cd0dd6bad4eb9b/library/std/src/sys/windows/mutex.rs#L119-L133

And another example in parking_lot.

So, since this Lazy/OnceCell implementation does block (such that the initialization function can be FnOnce and the type doesn't have to fit in an atomic), and an alternative purely atomic strategy does exist, I'd really avoid using the word 'atomic' in the name here.

[matklad]

I've added non-blocking flavors of the primitives to the once_cell crate: https://docs.rs/once_cell/1.5.1/once_cell/race/index.html. They are restricted (can be provided only for atomic types), but are compatible with no_std.

It seems to me that "first one wins" is a better semantics if you can't block, so I am going to resolve Sync no_std subset like this:

• only std supports sync module, as it requires synchronization (std::thread)
• if you need something like OnceCell in no-std, your choices are
  
  
  
  • use race module from once_cell with different API, which might or might not be upifted to std some day
  
  
  • use some version based on spin locks (this risks @matklad crashing into issue tracker of your project with explanation of how pure spin locks are almost always wrong).
  
  

I've ticked this question's box.

[m-ou-se]

It's a bit of a shame that Lazy uses a fn() -> T by default. With that type, it needlessly stores a function pointer even if it is constant. Would it require big language changes to make it work without storing a function pointer (so, a closure as ZST), while still being as easy to use? Maybe if captureless closures would implement some kind of const Default? And some way to not have to name the full type in statics. That's probably not going to happen very soon, but it'd be a shame if this becomes possible and we can't improve Lazy because the fn() -> T version was already stabilized. Is there another way to do this?

[phil-opp]

@matklad

They are restricted (can be provided only for atomic types), but are compatible with no_std.

This seems like a very major restriction, which rules out most use cases of SyncLazy/SyncOnceCell. So I don't think that this really resolves the sync no_std use case.

• use some version based on spin locks (this risks @matklad crashing into issue tracker of your project with explanation of how pure spin locks are almost always wrong).

I agree that spinlocks have their problems, but they're still better than using static mut instead. I understand that we don't want to hardcode SyncLazy/SyncOnceCell to use a deadlock-prone spinlock on no_std, but maybe it's possible to let the user supply their own implementation of a Mutex/Once primitive?

This could be implemented using a second generic argument on the Sync* types (or maybe even on the Mutex/Once types). This way, users could specify how the synchronization should happen based on their application. A single-threaded embedded application could just disable interrupts for the critical section, a toy OS kernel could use a spinlock, and projects with their own threading system could supply a "proper" synchronization primitive. Maybe I'm missing something, but this seems like a good solution to me.

[m-ou-se]

Some thoughts about &mut self functions on (Sync)OnceCell:

These types have both &mut self and &self functions, but the &mut interface seems somewhat incomplete, and it's a bit tricky to pick names for overlapping functionality. For example, take can only be done with unique access, so fn take(&mut self) -> Option<T> makes sense. But set can be done on an empty cell through a shared reference, or on a cell in any state through an unique reference. So both fn set(&self, value: T) -> Result<&T, T>; (like Cell::set) and fn set(&mut self, value: T) -> &mut T; (like Option::insert) would make sense.

Maybe if the get_or_insert/get_or_insert_with pair already provides a 'one time set' functionality, set (or insert?) should be the &mut self version instead?

[matklad]

Unresolved question: method naming

Currently, we have get_or_init and get_or_try_init. Are those good names? Here are some alternatives (see also https://github.com/rust-lang/rust/pull/78943)

1) get_or_init, get_or_try_init
2) get_or_insert_with, try_get_or_insert_with
3) get_with, try_get_with

1. Pro: Status Quo, name specific to OnceCell (you see x.get_or_init, you know x is one cell). Con: doesn't feel like it perfectly fits with other std names.
2. Pro: matches Option::get_or_inser_with exactly. Con: for OnceCell, unlike Option, this is the core API. It's a shame that its a mouthful.
3. Pro: short, matches std conventions. Con: _with without or suggest that the closure will be always called, but it's not really the case.

I've though more about this, and I think I actually like 3 most. It's Con seems like a Pro to me. In the typical use-case, you only use _with methods:

impl Spam {
  fn get_eggs(&self) -> &Eggs {
    self.eggs.get_with(|| Eggs::cook())
  }
}

So, the closure is sort-of always called, it's just cached. Not sure if I my explanation makes sense, but I do feel that this is different from, eg, Entry::or_insert_with.

[matklad]

@phil-opp: I think it is rather certain that, even if std provides a subset of OnceCell for no_std, it will be non-blocking subset (set and get).

It certainly is possible to use spinlocks, or make sync::OnceCell parametric (compile-time or run-time) over blocking primitives. I am pretty sure that should be left for crates.io crate though.

I feel one important criterion for inclusion in std is "design space has a solution with a single canonical API". OnceCell API seem canonical. If we add paramters, the design space inflates. Even if some solution would be better, it won't be obviously canonical, and would be better left to crates.io.

[matklad]

It's a bit of a shame that Lazy uses a fn() -> T by default.

@m-ou-se yeah, totally agree that this is a hack and feels like a hack. It works well enough in practice, but there's one gotcha: specifying type for a local lazy does not work:

let x = 92;
let works1: = Lazy::new(|| x.to_string());
let broken: Lazy<String> = Lazy::new(|| x.to_string());
let works2: Lazy<String, _> =  Lazy::new(|| x.to_string());

The broken variant is something that people occasionally write, and it fails with a somewhat confusing error. If we remove the default type, it will still be broken, but folks won't have intuition that "one parameter should be enough".

One easy way out here is to stabilize only OnceCell, and punt on Lazy for the time being. OnceCell contains all the tricky bit, and Lazy is just some syntactic sugar. For me (and probably for some, but not all, other folks) writing

fn global_state() -> &'static GlobalState {
  static INSTANCE: SyncOnceCell<GlobalState> = SyncOnceCell::new();
  INSTANCE.get_or_init(GlobalState::default)
}

doesn't feel like a deal breaker.I'd prefer that to pulling a 3rd party dep (lazy_staic or once_cell).

That said, I think Lazy's hack is worth stabilizing. Even if in the future we'll be able to write:

static GLOBAL_STATE: Lazy<GlobalState, _> = Lazy::new(GlobalState::default);

I don't see a lot of practical problems with

static GLOBAL_STATE: Lazy<GlobalState> = Lazy::new(GlobalState::default);

working as well.

[nwn]

Unresolved question: method naming

1. `get_or_init`, `get_or_try_init`

2. `get_or_insert_with`, `try_get_or_insert_with`

3. `get_with`, `try_get_with`

I think 1 is the most appropriate. The init terminology makes more sense than insert in the context of a once cell. Depending on whether we expose a direct value initializer, it may be more consistent to add _with to these methods, though.

I've though more about this, and I think I actually like 3 most. It's Con seems like a Pro to me. In the typical use-case, you only use _with methods:

[...]

So, the closure is sort-of always called, it's just cached. Not sure if I my explanation makes sense, but I do feel that this is different from, eg, Entry::or_insert_with.

This doesn't seem very intuitive to me and isn't always true when there are multiple points of initialization. For example, consider:

impl Spam {
    fn get_eggs(&self, cooked: bool) -> &Eggs {
        if cooked {
            self.eggs.set(Eggs::cook());
        }
        self.eggs.get_with(|| Eggs::raw())
    }
}

In this case, the closure may not run and in fact a different value has been cached. I think get_or_init_with would make this case more clear.

[raphaelcohn]

Something I've recently got bitten by is the need to manage which memory allocator a memory uses. I've been workign wit ha design that has a different global memory allocator when running threads or coroutines (so restricting a coroutine to a maximum amount of memory). This could be thought of as a bit of a hack; one of the long-term design decisions of early Rust that still bites is not making the memory allocator type explicit in the standard collections.

With a lazy, the challenge becomes ensuring that they're all allocated using the same memory allocator.