Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Proof of Concept: making Lazy<T, F> covariant in F #230

Conversation

danielhenrymantilla
Copy link
Contributor

@danielhenrymantilla danielhenrymantilla commented May 27, 2023

Proof of Concept of my idea from #167 (comment)

  • CovariantCellOption<F> is soundly covariant since the F value is never overwritten.

If this PoC were to be merged, it would fix #167.

Although it does so at the cost of loss of discriminant elision of Option<F>, which means it makes Lazys bigger. This could be deemed too high a cost for a somewhat niche feature.

  • an alternative could be to offer a LazyCovariantCtor<T, F> type which would thereby let users pick their preferred flavor.

@danielhenrymantilla danielhenrymantilla force-pushed the covariant_ctor_for_lazy branch from 5e99873 to a1f3226 Compare May 27, 2023 18:47
@matklad
Copy link
Owner

matklad commented May 29, 2023

TBH, I am off two minds here, as the following concerns conflict:

  • as a library author, I want to pull as much complexity as posible into the lib's code, so that, from the user's perspective, things "just work".
  • at the same time, I very much don't want to "go against the grain of the language", and implement clever work-arounds.

I guess, on balance, yeah, we should do that.

But before, I am curious, can we optimize this a bit? In particular, the current impl,

    pub struct Lazy<T, F = fn() -> T> {
        cell: OnceCell<T>,
        init: Cell<Option<F>>,
    }

isn't really what it should be, as we have two flags here one in OnceCell, and one in Option. And we don't share the space between T and F.

So I think ideally we want something like

struct Lazy<T, F> {
    state: enum { Init, Uninit, Poison },
    data: union {
        f: F,
        t: T,
        poison: (),
    }
}

can we make that work pedantically correct wrt variance?

@matklad
Copy link
Owner

matklad commented May 29, 2023

I guess, as another consideration here, give that std::sync::LazyLock is almost stable, I'll probably change what this crate is about, and move it from "stable foundation" to "fancy extras", as the foundational role would be subsumed by std. From this perspective, doing something more creative here also makes sense.

@danielhenrymantilla
Copy link
Contributor Author

danielhenrymantilla commented Jun 2, 2023

can we make that work pedantically correct wrt variance?

Yes, by slightly amending it 🙂:

use ManuallyDrop as MD; // <- necessary red tape

struct Lazy<T, F> {
    state: SomeMutWrapper<enum { Init, Uninit, Poison }>, // Uninit=can read `f`, Init=can read 't', Poison=cannot read either
    data: union {
        f: MD<F>,
        t: MD<UnsafeCell<T>>, // 👈 `UnsafeCell` only here
    }
}
  • e.g., the impl Drop:

    match self.state.get_mut() {
        Init => unsafe { MD::drop(&mut self.data.t) },
        Uninit => unsafe { MD::drop(&mut self.data.f) },
        Poison => {},
    }
  • takeing the f would then be a matter of setting the state to Poison, then <*const _>::read()ing the .f field like this very PR does, and writing that value to .t, and then setting the state to Init.

This has the right variance w.r.t. both F and T and would indeed allow squashing the is_some flag of .f in my PR within state. The only drawback is that it requires reïmplementing the flag-handling for Lazy, rather than being able to rely on the OnceCell<T> already existing abstraction.

  • The advantage, however, for people using Lazy with zero-sized impl Fn types (e.g., within function bodies or using TAITs), it that it would mean Lazy would be getting smaller for them as well!

    In other words, this last implementation you've suggested would be both pedantically correct w.r.t. variance, and efficient!

@danielhenrymantilla danielhenrymantilla changed the title Make Lazy<T, F> covariant in F Proof of Concept: making Lazy<T, F> covariant in F Jun 2, 2023
@danielhenrymantilla
Copy link
Contributor Author

I'm thus closing this draft PR, but may be submitting a PR implementing this for unsync::Lazy (the "easy" to write implementation of OnceCell). From there, I'll let sync-savy people follow-up on this and handle the sync flavor thereof

bors bot added a commit that referenced this pull request Jun 3, 2023
233: Make `unsync::Lazy<T, F>` covariant in `F` r=matklad a=danielhenrymantilla

"Continuation" from #230, which partially handles #167.

  - Incidentally, this also makes `unsync::Lazy` smaller in size in most cases, since `T` and `F` are now sharing the same `union` storage.

The `sync` can basically use the same logic (my PR paves the way for such a follow-up PR), only the whole thing would need to be moved to each of the possible `imp`lementations of `sync::OnceCell`, and special care to synchronization semantics will be in order, which I prefer to let somebody else do.

Co-authored-by: Daniel Henry-Mantilla <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Feature request: Make Lazy<T, F> covariant in F
2 participants