# In-place initializion via outptrs

## Prior work
- [@alicerhyl's In-place initialization](https://hackmd.io/@aliceryhl/BJutRcPblx), the corresponding [lang experiment proposal](https://github.com/rust-lang/lang-team/issues/336), and [this Zulip discussion thread](https://rust-lang.zulipchat.com/#narrow/channel/213817-t-lang/topic/In-place.20initialization/near/522444283).
- Rust-for-Linux's [`pin_init` crate](https://github.com/Rust-for-Linux/pin-init)
- [`moveit::New` trait](https://docs.rs/moveit/latest/moveit/new/trait.New.html) and its descendent, [Crubit's `Ctor` trait](https://github.com/google/crubit/blob/c65afa7b2923a2d4c9528f16f7bfd4aef6c80b86/support/ctor.rs#L189-L226)

## The limitations of `-> impl Init`

[@aliceryhl's In-place initialization](https://hackmd.io/@aliceryhl/BJutRcPblx) proposal includes this (simplified) trait:

unsafe trait Init<T> {
    type Error;

    unsafe fn init(self, slot: *mut T) -> Result<(), Self::Error>;
}
// Note: references to `PinInit` have been normalized to `Init`
// in this doc in order to avoid confusion.

and this example:

struct MyStruct {
    inner: bindgen::some_c_struct,
}

impl MyStruct {
    fn new(name: &str) -> impl Init<MyStruct, Error> {
        init MyStruct {
            inner: unsafe { core::init::zeroed() },
            _: {
                let ret = unsafe {
                    bindgen::init_some_c_string(&mut inner, name)
                };

                if ret < 0 {
                    Err(Error::from_errno(ret))
                } else {
                    // Result<(), Error> is an initializer
                    // for ().
                    Ok(())
                }
            },
        }
    }   
}

The fundamental approach, shared with other ecosystem libraries, relies on returning an `-> impl Init` value that knows how to initialize the output at some later-provided `*mut T` slot. This delayed application / currying of the output pointer has two significant advantages:
1. The author and caller of `MyStruct::new` can write safe (or mostly-safe) code, leaving the unsafe pointer writes to the library code that runs the delayed `init(slot)` function.
2. The end-user API has a similar shape to regular Rust code: outputs are return values, not output arguments.

However, this approach has some limitations.

### Control flow

Similar to other `-> impl Trait` delayed bodies such as closures, coroutines, and `async` blocks, code inside an `impl Init` expression cannot `break`/`continue`/`return` as normal. That is, one cannot write the following code:

impl MyStruct {
    fn new(name: &str) -> Result<impl Init<MyStruct>, Error>  {
        Ok(init MyStruct {
            inner: unsafe { core::init::zeroed() },
            _: {
                let ret = unsafe {
                    bindgen::init_some_c_string(&mut inner, name)
                };

                if ret < 0 {
                    return Err(Error::from_errno(ret));
                }
            },
        })
    }   
}

The `return Err` above cannot return a `Result` from the top-level function because the `init` body is only ever executed after the function has returned and `Init::init` is invoked. `impl Init` is created *before* ever actually running any code inside the `init` body.

This is why the `Init` trait definition above includes a built-in error type: common usage patterns require the ability to fail midway through initialization, after an address has been chosen. Building in `Result` addresses this common issue but does not address the more general problem of control flow which travels in and out of initialization expressions, or which simply happens *prior* to the initialization expression. Other return types such as `-> Option<impl Init>` or `Either<impl Init<A>, impl Init<B>>` cannot be expressed and must be "smuggled" through a `Result` return type.

For example, the following code has two separate error conditions: one pre-initializer and one mid-initializer. Each must be handled separately:

impl MyStruct {
    fn new(name: &str) -> Result<impl Init<MyStruct, Error=Error>, Error> {
        if name.starts_with("bad") { return Err(...); }
        Ok(init MyStruct {
            inner: unsafe { core::init::zeroed() }
            _: {
                let ret = unsafe {
                    bindgen::init_some_c_string(&mut inner, name)
                };

                if ret < 0 {
                    return Err(Error::from_errno(ret));
                }
                Ok(())
        })
    }
}

This is confusing and forces the end user to consider too many details about where exactly an error may occur.

Additionally, users must understand that `init` expressions (like closures, coroutines, and async blocks, but unlike other struct expressions) capture `return` rather than allowing `return` to return out of the top-level function.

### Composition

The `impl Init` proposal offers some mechanisms for composing initializers such as `(impl Init<A>, impl Init<B>) -> impl Init<(A, B)>` via the `init` syntax:

fn make_pair<A, B, E>(
    a_init: impl Init<A, Error=E>,
    b_init: impl Init<B, Error=E>,
) -> impl Init<(A, B), Error=E> {
    init (a_init, b_init)
}

However, as in the `Result` section above, this composition builds in:
- a particular execution order of `a_init` and `b_init`
- early-return on error
- a requirement that the error types match, implying a need for `Init::map_err` or similar
- generics: the `init` functions cannot be fn pointers or `dyn` trait methods because they return some `impl Init` type of unknown size

### `dyn` safety

As with other `-> impl Trait` APIs, `-> impl Init` results in an unnameable return type of unspecified size, and so is not `dyn`-safe. The linked proposal provides a means for addressing the general problem of `-> impl Trait` in traits via vtable-stored `Layout`s, but `-> impl Init` functions themselves would still require the caller to dynamically allocate space to store the `init` captures.

This intermediate allocation of `init` captures is unnecessary given that the `init` body itself will be executed immediately afterwards when provided with the out-pointer.

## The alternative: out pointers

Here's what our original example might look like using an out-pointer-based approach:

impl MyStruct {
    fn new<'o>(
        name: &str,
        out: Uninit<'o, MyStruct>,
    ) -> Result<InPlace<'o, MyStruct>, Error> {
        let res = unsafe { bindgen::init_some_c_string(&raw out.inner, name) };
        if ret < 0 {
            return Err(Error::from_errno(ret));
        }
        Ok(unsafe { out.assume_init() })
    }
}

compared to the original:

impl MyStruct {
    fn new(name: &str) -> impl Init<MyStruct, Error> {
        init MyStruct {
            inner: unsafe { core::init::zeroed() },
            _: {
                let ret = unsafe {
                    bindgen::init_some_c_string(&mut inner, name)
                };

                if ret < 0 {
                    Err(Error::from_errno(ret))
                } else {
                    // Result<(), Error> is an initializer
                    // for ().
                    Ok(())
                }
            },
        }
    }   
}

A few things to notice:
- The function has grown an extra parameter, `outptr: Uninit<'o, MyStruct>`.
- The `Result` is now top-level, and control-flow is uninterrupted.
- We've replaced our `-> impl Init<MyStruct, Error=Error>` return type with a concrete return type, `Result<InPlace<'o, MyStruct>, Error>`.

We can also write infallible initialization examples by removing the `Result`:

impl MyStruct {
    fn new<'o>(
        name: &str,
        outptr: Uninit<'o, MyStruct>,
    ) -> InPlace<'o, MyStruct> {
        unsafe {
            init_some_c_string(&raw out.inner, name);
            outptr.assume_init()
        }
    }
}

Or we can wrap it in an `Option`:

impl MyStruct {
    fn new<'o>(
        name: &str,
        outptr: Uninit<'o, MyStruct>,
    ) -> Option<InPlace<'o, MyStruct>> {
        if !unsafe { init_some_c_string(&raw out.inner, name) } {
            return None;
        }
        Some(unsafe { out.assume_init() })
    }
}

or add a retry loop / rerun initialization, or any similar pattern.

## `Uninit<'o, T>` and `InPlace<'o, T>`

This proposal would introduce two new library types, `Uninit` and `InPlace`.
[See this playground for a minimal usable API](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2024&gist=dbfa54594ee546b266ce4a189e2b5743).

`Uninit` is a wrapper around `*mut MaybeUninit<T>` with an extra lifetime parameter,`'o`, which is tied to the output location. The above examples also assume that it implements `DerefRaw` or some similar operation so that the syntax `&raw out.field_of_t` is valid. It provides the following API:

impl<'o, T> Uninit<'o, T> {
    unsafe fn from_raw<'o>(raw: *mut T) -> Self;
    fn as_ptr(&self) -> *const T;
    fn as_mut_ptr(&mut self) -> *mut T;
    fn write(self, val: T) -> InPlace<'o, T>;
    unsafe fn assume_init(self) -> InPlace<'o, T>;
}

`InPlace<'o, T>` is a `Box<T>` whose deallocator is a no-op, as it only refers to stack-allocated data (or heap-allocated data whose allocation is externally managed):

type InPlace<'o, T> = Box<T, A=InPlaceAlloc<'o>>;

struct InPlaceAlloc<'o> {
    // Force `'o` to be invariant.
    //
    // This ensures that an `InPlaceAlloc<'o>` can only be created
    // by initializing the corresponding `Uninit<'o>`.
    marker: PhantomData<fn(&'o ()) -> &'o ()>
    
    // See "Pinning" below for details.
    initialized_without_drop: *mut bool,
}

// No-op `Allocator` implementation.
impl<'o> Allocator for InPlaceAlloc<'o> {
    fn allocate(&self, _: Layout) -> Result<NonNull<[u8]>>, AllocError> {
        AllocError
    }
    unsafe fn deallocate(&self, _: NonNull<u8>, _: Layout) {
        *initialized_without_drop = false;
    }
}

If dropped, the `InPlace<'o, T>` will destroy the underlying `T`, but will not deallocate the memory in which the `T` was stored. This is similar to previously-proposed `&own`, and can be used to provide the same behavior. See [this playground example](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2024&gist=7069dedca298afb85c0dca5e68bb2804):

fn takes_fnonce_noheap(f: InPlace<dyn FnOnce() + '_>) {
    f()
}

fn main() {
    let x = "fooey".to_string();
    let f = in_place!(|| println!("{}", x));
    takes_fnonce_noheap(f);
}

## Composition and fieldwise-initialization

The earlier `init MyStruct { ... }` proposal allows the values of fields to be provided as initializers (`impl Init<FieldTy>` values). However, this prevents field initialization from depending on the values or addresses of other fields or else requires that prior field names are added to the scope of later field expressions (the current proposal). It also bakes error / early-return behavior into the struct expression itself.

The first of these issues, fields depending on one another, could be resolved in an outptr-based solution. We can use a derive-based projection similar to what is available in `pin_project` to turn an `Uninit<Struct>` into `(Uninit<FieldOneTy>, Uninit<FieldTwoTy>` etc., and then map the resulting `(InPlace<FieldOneTy>, InPlace<FieldTwoTy>)` back into an `InPlace<Struct>`:

fn make_my_struct(out: Uninit<'_, MyStruct>) -> InPlace<'_, MyStruct> {
    MyStruct::fieldwise_init(out, |x, y| {
        let x_out = make_x_in_place(x);
        // Field `y` can depend on the address of field `x`.
        let y_out = y.write(x.as_ptr());
        (x_out, y_out)
    })
}

// autogenerated:
impl MyStruct {
    pub fn fieldwise_init(
        out: Uninit<'_, MyStruct>,
        f: impl for<'ox, 'oy> FnOnce(
            Uninit<'ox, XType>,
            Uninit<'oy, YType>,
        ) -> (InPlace<'ox, XType>, InPlace<'oy, YType>),
    ) -> InPlace<'_, MyStruct> {
        ...
    }
}

Unlike the earlier `-> impl Init` proposal, this allows fields to be initialized or reinitialized in any order, and fields can access each others addresses or (initialized) values during construction.

The downside of this approach is that wrapping in a closure limits control flow within initialization similar to the `-> impl Init` approaches. Users would need `try_` variants.

## Gradual struct initialization without closures

We can break out of the closure approach and allow a higher level of control flow by defining a macro or similar tool which creates a builder structure paired with particular outpointers via unique per-field lifetimes. Because each use of the macro results in unique per-field lifetimes, we know that the outptrs handed back to us refer to fields of the original type.

fn make_my_struct(out: Uninit<'_, MyStruct>) -> InPlace<'_, MyStruct> {
    let (builder, x_out, y_out) = build_fields_of_my_struct!(out);
    // Local types:
    // x_out: Uninit<'anon_x, X>
    // y_out: Uninit<'anon_y, Y>
    // builder: FnOnce(
    //     InPlace<'anon_x, X>,
    //     InPlace<'anon_y, Y>
    // ) -> InPlace<'_, MyStruct>
    let x_out = make_x_in_place(x);
    // Field `y` can depend on the address of field `x`.
    let y_out = y.write(x.as_ptr());
    builder(x_out, y_out)
}

This, too, can be accomplished without adding any new language features.

## Initialization inside containers

### Using `new_with`

One option would be for `Box` and other containers (e.g. `Vec`, `[T; N]`) to gain new constructor functions called `new_with`:

impl<T> Box<T> {
    fn new_with<F>(f: F) -> Self
    where
        F: impl for<'o> FnOnce(Uninit<'o, T>) -> InPlace<'o, T>;
}

Usage example:

// Given an in-place constructor function like this:
fn make_mytype(_: Uninit<'_, MyType>, some_int: usize) -> InPlace<'_, MyType> {
    ...
}

// We can construct a `Box<MyType>` like this:
let b: Box<MyType> = Box::new_with(|out| make_mytype(out, 27));`

Similarly, `Box::try_new_with(|out| try_make_mytype(out, 27))?` could be used for in-place constructor functions.

However, this would result in an explosion of new APIs-- every construction API would need to grow a new `_with` variant, and the `try_` versions compose poorly with existing `try_`-based APIs which are fallible for other reasons (e.g. `Box::try_new_in`, which fails due to allocation errors).

### Using gradual initialization for `Box`

One alternative, especially for `Box`, would be to allow gradual initialization through `Box<MaybeUninit<T>>` values:

fn make_x_in_place(out: Uninit<'_, X>) -> InPlace<'_, X> { ... }

// with non-native gradual initialization:
// This assumes some `box_into_builder!` which turns
// `Box<MaybeUninit<T>>` into
//     box_builder: impl FnOnce(InPlace<'o, T>) -> Box<T>
//     out_uninit: Uninit<'o, T>
fn make_my_struct() -> Box<MyStruct> {
    let out = Box::<MyStruct>::new_uninit();
    let (box_builder, out_uninit) = box_into_builder!(out);
    let (my_struct_builder, x_uninit, y_uninit) = my_struct_builder!(out);
    let x_out = make_x_in_place(x_uninit);
    let y_out = y_uninit.write(x_out.as_ptr());
    box_builder.build(my_struct_builder.build(x_out, y_out))
}

## Pinning
Properly supporting `Pin<InPlace<'_, T>>` requires that the contents of the `InPlace` *must* be dropped before the corresponding memory is deallocated. Other (`'static`) allocators used with `Pin<Box<T>>` accomplish this by simply leaking memory: `mem::forget(some_box)` will never deallocate, so it's not a problem that the `T` is never dropped.

However, scoped / non-`'static` allocators must ensure that all `Pin<Box<T, NonStaticA>>` drop their `T` before the allocator goes out of scope. It isn't obvious how to statically ensure this.

However, it is possible to dynamically check. Each creator of an `Uninit` can keep a drop flag indicating whether the value has been initialized and not dropped. If code in scope creates an `InPlace<T>` and then `mem::forget`s it, we can panic when exiting the scope at which the `Uninit` was created:

fn forget_pinned_struct() {
    let out = MaybeUninit::<Foo>::uninit();
    // `uninit_into_builder` creates a super-let temporary which tracks
    // the initialization state of the `foo`.
    let (box_builder, foo_uninit) = uninit_into_builder!(out);
    
    `foo_uninit.set` sets the 
    let pinned: Pin<InPlace<'_, Foo>> =
        foo_uninit.set(Foo { ... });
    ...
    mem::forget(pinned); // BAD
    
    // PANIC when the temporary from `uninit_into_builder`
    // is dropped: `foo` is initialized but was not
    // dropped or moved-from.
}

This will require that `Uninit` and `InPlace` allocators contain a pointer to their corresponding drop flags.

Note that this is not necessary for zero-sized types, as there is no underlying memory. `Allocator::deallocate` is not even invoked when `Box<Zst>` is dropped.

## Ergonomics extension: native gradual initialization

All APIs above can be implemented using existing language features (though they internally rely on existing `allocator_api` and `super let` support).

One optional addition that could improve ergonomics would be to support native gradual initialization of structures (see [this partial initialization proposal](https://github.com/rust-lang/rust/issues/54987) and [this draft PR](https://github.com/rust-lang/rust/pull/143625)).

This would be a significant benefit over both `init` and the closure or builder-based patterns above. Additionally, this could benefit non-in-place initialization that exists today.

Rust already allows delayed initialization of locals, allowing for locals to depend on one another's value or address:

let x;
let y;
x = 5;
y = &raw const x;

However, the same thing is not currently possible when working with a struct:

struct MyStruct { x: i32, y: *const i32 }

let my_struct: MyStruct;
my_struct.x = 5; // ERROR: partial initialization isn't supported
my_struct.y = &raw const my_struct.x;

Nor when working with a value behind an uninit pointer:

fn make_my_struct(out: Uninit<'_, MyStruct>) -> InPlace<'_, MyStruct> {
    out.x = 5; // ERROR
}

What we'd like is for the fields of a struct behind an `Uninit<'_, MyStruct>` to be gradually-initializable in the same fashion as locals, and for the resulting value to be convertible to an `InPlace<'_, MyStruct>` once all fields have been initialized:

fn make_my_struct(out: Uninit<'_, MyStruct>) -> InPlace<'_, MyStruct> {
    out.x = 5;
    out.y = &raw const out.x;
    declare_init!(out)
}

The `declare_init!` macro would require that all fields have been initialized and would convert an `Uninit<'_, T>` to an `InPlace<'_, T>`.

`declare_init!` could also be omitted by adding a coercion from a fully-initialized `Uninit<'_, T>` into an `InPlace<'_, T>`:

fn make_my_struct(out: Uninit<'_, MyStruct>) -> InPlace<'_, MyStruct> {
    out.x = 5;
    out.y = &raw const out.x;
    out
}

#### `Drop` glue

One thing to note is that the `Drop` impl for `MyStruct` would not run until `declare_init!` is run. This is consistent with the behavior of early-exiting before a struct initialization expression has completed.

The more complex thing to consider is when to drop the fields of a partially-initialized `Uninit`. This doc proposes that all fields of a single struct must be initialized in the same body. If a field is initialized but the parent structure is not passed to `declare_init!`, the fields which have been initialized will be dropped. This requires the compiler to track per-field drop flags, but this is already supported in the compiler today in order to allow [partially-moved-from structs](https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=51bbaed3f9ec43a61892ed18c0fe70b2).

Cross-body initialization of a struct is not allowed. Notably, the following will not work:

fn make_my_struct(out: Uninit<'_, MyStruct>) -> InPlace<'_, MyStruct> {
    out.x = String::from("foo");
    // ERROR: `out` is partially initialized
    set_y_and_init(out)
}

#### Composition using native gradual initialization

With gradual initialization, in-place construction functions could be composed by using a new `&uninit` expression to create an `Uninit<MyField>` from an `Uninit<MyStruct>`:

fn make_x_in_place(out: Uninit<'_, X>) -> InPlace<'_, X> { ... }

fn make_my_struct(out: Uninit<'_, MyStruct>) -> InPlace<'_, MyStruct> {
    out.x = make_x_in_place(&uninit out.x);
    out.y = &raw const out.x;
    out
}

`&uninit out.x` creates a new `Uninit<X>` with a unique lifetime. `out.x` can then be marked as initialized by assigning an `InPlace<X>` with the matching lifetime. This assignment has no runtime behavior, but merely marks the local as having been initialized. Besides enforcing uniqueness, an `uninit` borrow behaves similar to an exclusive `&mut` reference: only one borrow can be made a time.

## Ergonomics extension: in-place return values

`fn make_my_struct(out: Uninit<'_, MyStruct>) -> InPlace<'_, MyStruct>` is still visually cluttered and much harder to read than `fn make_my_struct() -> impl Init<Output = MyStruct>`. We could consider providing sugar like the following:

fn make_my_struct() -> in_place { out: MyStruct } {
    out.x = make_x_in_place(&uninit out.x);
    out.y = &raw const out.x;
    out
}

This would implicitly create a separate argument for every name that appears in an `in_place { ... }` brace in the return type.

The downside of this approach is that it introduces novel syntax users have to learn. Additionally, we would need to figure out how the values are bound at the call site. Named arguments make this easy, but that implies yet another language feature:

let my_struct: MyStruct;
my_struct = make_my_struct(out = &uninit my_struct);