• Application memory is just array of bytes on low level.
• Operating environment usually segments that, amongst others, into:
  • stack (small, low-overhead memory,¹ most variables go here),
  • heap (large, flexible memory, but always handled via stack proxy like Box<T>),
  • static (most commonly used as resting place for str part of &str),
  • code (where bitcode of your functions reside).
• Most tricky part is tied to how stack evolves, which is our focus.

let t = S(1);

• Reserves memory location with name t of type S and the value S(1) stored inside.
• If declared with let that location lives on stack. ¹
• Note the linguistic ambiguity, in the term variable, it can mean the:
  1. name of the location in the source file ("rename that variable"),
  2. location in a compiled app, 0x7 ("tell me the address of that variable"),
  3. value contained within, S(1) ("increment that variable").
• Specifically towards the compiler t can mean location of t, here 0x7, and value within t, here S(1).

let a = t;

• This will move value within t to location of a, or copy it, if S is Copy.
• After move location t is invalid and cannot be read anymore.
  • Technically the bits at that location are not really empty, but undefined.
  • If you still had access to t (via unsafe) they might still look like valid S, but any attempt to use them as valid S is undefined behavior. ^↓
• We do not cover Copy types explicitly here. They change the rules a bit, but not much:
  • They won't be dropped.
  • They never leave behind an 'empty' variable location.

let c: S = M::new();

• The type of a variable serves multiple important purposes, it:
  1. dictates how the underlying bits are to be interpreted,
  2. allows only well-defined operations on these bits
  3. prevents random other values or bits from being written to that location.
• Here assignment fails to compile since the bytes of M::new() cannot be converted to form of type S.
• Conversions between types will always fail in general, unless explicit rule allows it (coercion, cast, …).

{
    let mut c = S(2);
    c = S(3);  // <- Drop called on `c` before assignment.
    let t = S(1);
    let a = t;
}   // <- Scope of `a`, `t`, `c` ends here, drop called on `a`, `c`.

• Once the 'name' of a non-vacated variable goes out of (drop-)scope, the contained value is dropped.
  • Rule of thumb: execution reaches point where name of variable leaves {}-block it was defined in
  • In detail more tricky, esp. temporaries, …
• Drop also invoked when new value assigned to existing variable location.
• In that case Drop::drop() is called on the location of that value.
  • In the example above drop() is called on a, twice on c, but not on t.
• Most non-Copy values get dropped most of the time; exceptions include mem::forget(), Rc cycles, abort().

fn f(x: S) { … }

let a = S(1); // <- We are here
f(a);

• When a function is called, memory for parameters (and return values) are reserved on stack.¹
• Here before f is invoked value in a is moved to 'agreed upon' location on stack, and during f works like 'local variable' x.

fn f(x: S) {
    if once() { f(x) } // <- We are here (before recursion)
}

let a = S(1);
f(a);

• Recursively calling functions, or calling other functions, likewise extends the stack frame.
• Nesting too many invocations (esp. via unbounded recursion) will cause stack to grow, and eventually to overflow, terminating the app.

fn f(x: S) {
    if once() { f(x) }
    let m = M::new() // <- We are here (after recursion)
}

let a = S(1);
f(a);

• Stack that previously held a certain type will be repurposed across (even within) functions.
• Here, recursing on f produced second x, which after recursion was partially reused for m.

Key take away so far, there are multiple ways how memory locations that previously held a valid value of a certain type stopped doing so in the meantime. As we will see shortly, this has implications for pointers.

let a = S(1);
let r: &S = &a;

• A reference type such as &S or &mut S can hold the location of some s.
• Here type &S, bound as name r, holds location of variable a (0x3), that must be type S, obtained via &a.
• If you think of variable c as specific location, reference r is a switchboard for locations.
• The type of the reference, like all other types, can often be inferred, so we might omit it from now on:

  let r: &S = &a;
  let r = &a;
  

let mut a = S(1);
let r = &mut a;
let d = r.clone();  // Valid to clone (or copy) from r-target.
*r = S(2);          // Valid to set new S value to r-target.

• References can read from (&S) and also write to (&mut S) locations they point to.
• The dereference *r means to use the location r points to (not the location of or value within r itself)
• In the example, clone d is created from *r, and S(2) written to *r.
  • We assume S implements Clone, and r.clone() clones target-of-r, not r itself.
  • On assignment *r = … old value in location also dropped (not shown above).

let mut a = …;
let r = &mut a;
let d = *r;       // Invalid to move out value, `a` would be empty.
*r = M::new();    // invalid to store non S value, doesn't make sense.

• While bindings guarantee to always hold valid data, references guarantee to always point to valid data.
• Esp. &mut T must provide same guarantees as variables, and some more as they can't dissolve the target:
  • They do not allow writing invalid data.
  • They do not allow moving out data (would leave target empty w/o owner knowing).

let p: *const S = questionable_origin();

• In contrast to references, pointers come with almost no guarantees.
• They may point to invalid or non-existent data.
• Dereferencing them is unsafe, and treating an invalid *p as if it were valid is undefined behavior. ^↓

• Every entity in a program has some (temporal / spatial) extent where it is relevant, i.e., alive.
• Loosely speaking, this alive time can be¹
  1. the LOC (lines of code) where an item is available (e.g., a module name).
  2. the LOC between when a location is initialized with a value, and when the location is abandoned.
  3. the LOC between when a location is first used in a certain way, and when that usage stops.
  4. the LOC (or actual time) between when a value is created, and when that value is dropped.
• Within the rest of this section, we will refer to the items above as the:
  1. scope of that item, irrelevant here.
  2. scope of that variable or location.
  3. lifetime² of that usage.
  4. lifetime of that value, might be useful when discussing open file descriptors, but also irrelevant here.
• Likewise, lifetime parameters in code, e.g., r: &'a S, are
  • concerned with LOC any location r points to needs to be accessible or locked;
  • unrelated to the 'existence time' (as LOC) of r itself (well, it needs to exist shorter, that's it).
• &'static S means address must be valid during all lines of code.

¹ There is sometimes ambiguity in the docs differentiating the various scopes and lifetimes. We try to be pragmatic here, but suggestions are welcome.

² Live lines might have been a more appropriate term …

• Assume you got a r: &'c S from somewhere it means:
  • r holds an address of some S,
  • any address r points to must and will exist for at least 'c,
  • the variable r itself cannot live longer than 'c.

{
    let b = S(3);
    {
        let c = S(2);
        let r: &'c S = &c;      // Does not quite work since we can't name lifetimes of local
        {                       // variables in a function body, but very same principle applies
            let a = S(0);       // to functions next page.

            r = &a;             // Location of `a` does not live sufficient many lines -> not ok.
            r = &b;             // Location of `b` lives all lines of `c` and more -> ok.
        }
    }
}

• Assume you got a mut r: &mut 'c S from somewhere.
  • That is, a mutable location that can hold a mutable reference.
• As mentioned, that reference must guard the targeted memory.
• However, the 'c part, like a type, also guards what is allowed into r.
• Here assigning &b (0x6) to r is valid, but &a (0x3) would not, as only &b lives equal or longer than &c.

let mut b = S(0);
let r = &mut b;

b = S(4);   // Will fail since `b` in borrowed state.

print_byte(r);

• Once the address of a variable is taken via &b or &mut b the variable is marked as borrowed.
• While borrowed, the content of the address cannot be modified anymore via original binding b.
• Once address taken via &b or &mut b stops being used (in terms of LOC) original binding b works again.

fn f(x: &S, y:&S) -> &u8 { … }

let b = S(1);
let c = S(2);

let r = f(&b, &c);

• When calling functions that take and return references two interesting things happen:
  • The used local variables are placed in a borrowed state,
  • But it is during compilation unknown which address will be returned.

let b = S(1);
let c = S(2);

let r = f(&b, &c);

let a = b;   // Are we allowed to do this?
let a = c;   // Which one is _really_ borrowed?

print_byte(r);

• Since f can return only one address, not in all cases b and c need to stay locked.
• In many cases we can get quality-of-life improvements.
  • Notably, when we know one parameter couldn't have been used in return value anymore.

fn f<'b, 'c>(x: &'b S, y: &'c S) -> &'c u8 { … }

let b = S(1);
let c = S(2);

let r = f(&b, &c); // We know returned reference is `c`-based, which must stay locked,
                   // while `b` is free to move.

let a = b;

print_byte(r);

• Lifetime parameters in signatures, like 'c above, solve that problem.
• Their primary purpose is:
  • outside the function, to explain based on which input address an output address could be generated,
  • within the function, to guarantee only addresses that live at least 'c are assigned.
• The actual lifetimes 'b, 'c are transparently picked by the compiler at call site, based on the borrowed variables the developer gave.
• They are not equal to the scope (which would be LOC from initialization to destruction) of b or c, but only a minimal subset of their scope called lifetime, that is, a minmal set of LOC based on how long b and c need to be borrowed to perform this call and use the obtained result.
• In some cases, like if f had 'c: 'b instead, we still couldn't distinguish and both needed to stay locked.

let mut c = S(2);

let r = f(&c);
let s = r;
                    // <- Not here, `s` prolongs locking of `c`.

print_byte(s);

let a = c;          // <- But here, no more use of `r` or `s`.

• A variable location is unlocked again once the last use of any reference that may point to it ends.

// Return short ('b) reference
fn f1sr<'b, 'a>(rb: &'b     &'a     S) -> &'b     S { *rb }
fn f2sr<'b, 'a>(rb: &'b     &'a mut S) -> &'b     S { *rb }
fn f3sr<'b, 'a>(rb: &'b mut &'a     S) -> &'b     S { *rb }
fn f4sr<'b, 'a>(rb: &'b mut &'a mut S) -> &'b     S { *rb }

// Return short ('b) mutable reference.
// f1sm<'b, 'a>(rb: &'b     &'a     S) -> &'b mut S { *rb } // M
// f2sm<'b, 'a>(rb: &'b     &'a mut S) -> &'b mut S { *rb } // M
// f3sm<'b, 'a>(rb: &'b mut &'a     S) -> &'b mut S { *rb } // M
fn f4sm<'b, 'a>(rb: &'b mut &'a mut S) -> &'b mut S { *rb }

// Return long ('a) reference.
fn f1lr<'b, 'a>(rb: &'b     &'a     S) -> &'a     S { *rb }
// f2lr<'b, 'a>(rb: &'b     &'a mut S) -> &'a     S { *rb } // L
fn f3lr<'b, 'a>(rb: &'b mut &'a     S) -> &'a     S { *rb }
// f4lr<'b, 'a>(rb: &'b mut &'a mut S) -> &'a     S { *rb } // L

// Return long ('a) mutable reference.
// f1lm<'b, 'a>(rb: &'b     &'a     S) -> &'a mut S { *rb } // M
// f2lm<'b, 'a>(rb: &'b     &'a mut S) -> &'a mut S { *rb } // M
// f3lm<'b, 'a>(rb: &'b mut &'a     S) -> &'a mut S { *rb } // M
// f4lm<'b, 'a>(rb: &'b mut &'a mut S) -> &'a mut S { *rb } // L

// Now assume we have a `ra` somewhere
let mut ra: &'a mut S = …;

let rval = f1sr(&&*ra);       // OK
let rval = f2sr(&&mut *ra);
let rval = f3sr(&mut &*ra);
let rval = f4sr(&mut ra);

//  rval = f1sm(&&*ra);       // Would be bad, since rval would be mutable
//  rval = f2sm(&&mut *ra);   // reference obtained from broken mutability
//  rval = f3sm(&mut &*ra);   // chain.
let rval = f4sm(&mut ra);

let rval = f1lr(&&*ra);
//  rval = f2lr(&&mut *ra);   // If this worked we'd have `rval` and `ra` …
let rval = f3lr(&mut &*ra);
//  rval = f4lr(&mut ra);     // … now (mut) aliasing `S` in compute below.

//  rval = f1lm(&&*ra);       // Same as above, fails for mut-chain reasons.
//  rval = f2lm(&&mut *ra);   //                    "
//  rval = f3lm(&mut &*ra);   //                    "
//  rval = f4lm(&mut ra);     // Same as above, fails for aliasing reasons.

// Some fictitious place where we use `ra` and `rval`, both alive.
compute(ra, rval);

• f_sr cases always work, short reference (only living 'b) can always be produced.
• f_sm cases usually fail simply because mutable chain to S needed to return &mut S.
• f_lr cases can fail because returning &'a S from &'a mut S to caller means there would now exist two references (one mutable) to same S which is illegal.
• f_lm cases always fail for combination of reasons above.

Note: This example is about the f functions, not compute. You can assume it to be defined as fn compute(x: &S, y: &S) {}. In that case the ra parameter would be automatically coerced ^↓ from &mut S to &S, since you can't have a shared and a mutable reference to the same target.

{
    let f = |x, y| (S(x), S(y)); // Function returning two 'Droppables'.

    let (    x1, y) = f(1, 4);  // S(1) - Scope   S(4) - Scope
    let (    x2, _) = f(2, 5);  // S(2) - Scope   S(5) - Immediately
    let (ref x3, _) = f(3, 6);  // S(3) - Scope   S(6) - Scope

    println!("…");
}

• Functions or expressions producing movable values must be handled by callee.
• Values stores in 'normal' bindings are kept until end of scope, then dropped.
• Values stored in _ bindings are usually dropped right away.
• However, sometimes references (e.g., ref x3) can keep value (e.g., the tuple (S(3), S(6))) around for longer, so S(6), being part of that tuple can only be dropped once reference to its S(3) sibling disappears).