Where is a struct that doesn't implement Copy allocated and how can it be returned from a function?

Question

I read that memory in Rust is allocated on the stack by default, unless explicitly telling the compiler to use the heap by using a Box or some other method.

I understand that the ownership is moved between function calls, but where is the memory for the structs actually allocated? If it was on the stack, what happens when the function exits?

#[derive(Debug)]
struct Foo(i32);

#[derive(Debug)]
struct Bar(Foo);

fn foo() -> Foo {
    Foo(42)
}

fn bar() -> Bar {
    let f = foo();
    Bar(f)
}

fn main() {
    let bar = bar();
    println!("{:?}", bar);
}

For example, on line 12, there's a Foo struct allocated in the stack frame of the bar() function. When bar() exits, the stack is unwound and the memory is reclaimed. Since the struct does not implement Copy the memory is not copied, so where does it go?

I think there's a fundamental idea here I don't understand.

Answer 1

Everything¹ is stored on the stack in some fashion. Even when you heap-allocate something, the pointer itself is stored on the stack.

Your Foo and Bar instances are stored on the stack. When the function returns the instance, the data is moved² from the inner stack frame to the outer.

Since the struct does not implement Copy the memory is not copied

That's not the meaning of the Copy trait (emphasis mine):

Types whose values can be duplicated simply by copying bits.

Everything³ in Rust can be moved. If this wasn't true, then the language would be very hard to use! Your data is moved from one stack frame to another.

The only difference between a "copy" and a "move" is a copy allows both the source and destination values to be used, while a move only allows the destination value to be used.

---

¹ — Almost everything. I'd expect that static values aren't actually stored on the stack.

² — The optimizer might actually remove the move by allocating the struct in the parent's stack frame to start with and then passing a pointer into the child. This is called return value optimization.

³ — There are pathological cases where a value can't be moved. See the "A type with a reference to itself" section of Why can't I store a value and a reference to that value in the same struct?.