Rung 2: Ownership and borrowing

This is the idea that makes Rust Rust. Every value has one owner. Others may borrow it: many may read at once, or one may write, never both. The compiler checks this before the program runs. It is why Gestalt's codec can read an entry straight out of the bytes it was handed, with no copies and no memory bugs.

The idea #

One owner, and moves #

let line = vec![0xa7, 0x00];
let kept = line;           // the Vec moves: `kept` owns it now
println!("{:?}", line);    // refused: `line` was moved

Passing a value to a function moves it too. In rung 1, to_hex(bytes: Vec<u8>) consumed your bytes: after calling it, they were gone. When the owner goes out of scope, the value is dropped and its memory freed. There is no garbage collector and no free to forget.

Small values like u64, u8 and bool are Copy: assigning them copies the number, and nothing moves.

Borrowing: & and &mut #

fn to_hex(bytes: &[u8]) -> String { ... }      // borrows: reads, gives back
fn append_line(log: &mut Vec<Vec<u8>>, line: &[u8]) { ... }  // may change `log`

The rule is one writer or many readers, never both. That rules out a whole class of bugs. You can't have a reference to a Vec's first byte while a push moves its memory somewhere else.

Slices: views, not copies #

&[u8] is a slice: a pointer and a length, viewing bytes someone else owns. A &Vec<u8>, an array &[1, 2, 3] and a part of either &v[1..4] can all be passed as &[u8]. Taking a slice of a slice copies nothing.

&str is the same for text: a view into UTF-8 bytes. String owns its text and can grow. The habit is to take &str and &[u8] in, and give String and Vec<u8> out when you made something new.

s.len() counts bytes, not letters: "ü".len() is 2.

Copy only when you must keep it #

.to_vec() and .to_string() make owned copies. They are right when you need to keep data after the lender is done, like a log keeping a line. Otherwise borrow. .clone() to quiet the compiler is usually the wrong fix.

Lifetimes: how long a borrow lives #

struct Reader<'a> {
    bytes: &'a [u8],
    at: usize,
}

'a is a name for "as long as the bytes live". It says the reader can't outlive the bytes. A method returning &'a [u8] hands out slices that live as long as the bytes, not just as long as the reader. Most of the time Rust works lifetimes out by itself. You write them when a struct holds a borrow, as here.

Why Gestalt cares #

• No copies on the hot path. A node reads entries all day. The decoder borrows the input and hands out slices of it, so reading an entry does not copy it.
• Memory safety is proven, not hoped for. Because the compiler checks ownership and borrowing, the kernel crates can forbid(unsafe_code). Any memory bug would need unsafe, and the purity gate refuses it. The checker is the compiler, every build.
• One writer or many readers. Rust's rule has the same shape as Gestalt's: one head orders a record's writes, while any number of copies read it.

In Gestalt's code #

encode borrows the value (&Value): it reads it and never takes it. It owns a fresh Vec, lends it to write as &mut, and hands it back. write calls itself for nested values, and they all append into the one buffer. That is exercises 5 and 6.

From engine/kernel/codec/src/cbor.rs:302:

pub fn encode(v: &Value) -> Vec<u8> {
    let mut out = Vec::new();
    write(v, &mut out);
    out
}

/// Append the canonical bytes of `v` to `out`.
pub fn write(v: &Value, out: &mut Vec<u8>) {
    match v {
        Value::U(n) => head(out, 0, *n),
        Value::T(s) => {
            head(out, 3, s.len() as u64);
            out.extend_from_slice(s.as_bytes());
        }
        // ... the other kinds

The reader is exercise 7. It is a borrowed slice and a position, and take hands out slices of the input that live as long as the input ('a). Rung 3 explains the Result in its return type.

From engine/kernel/codec/src/cbor.rs:350:

struct Reader<'a> {
    b: &'a [u8],
    at: usize,
}

impl<'a> Reader<'a> {
    fn take(&mut self, n: u64) -> Result<&'a [u8], CborError> {
        if n > self.left() as u64 {
            return Err(CborError::Truncated);
        }
        let s = &self.b[self.at..self.at + n as usize];
        self.at += n as usize;
        Ok(s)
    }

Hashing only reads, so it borrows. Every digest in Gestalt is made by this function, and none of them copies the bytes it hashes.

From engine/kernel/codec/src/hash.rs:114:

pub fn digest(d: Domain, bytes: &[u8]) -> Digest {
    let mut h = Sha256::new();
    h.update(DOMAIN_PREFIX.as_bytes());
    h.update(d.name().as_bytes());
    h.update([0u8]);
    h.update(bytes);
    Digest(h.finalize().into())
}

Exercise #

cd ~/Documents/gestalt-learn
./ladder 2

Open rungs/02-ownership/src/lib.rs. The signatures are written for you, because they are the lesson: read each one before you write the body. Eight exercises end in your own Reader reading a CBOR text string without copying a byte. The tests check that with std::ptr::eq: your result must point into the input.

Then three drills, each refused by the compiler until you fix it:

./ladder drill 2 moved
./ladder drill 2 reader_and_writer
./ladder drill 2 dangling

Read the compiler's message each time. Rust's ownership errors explain themselves well. Learning to read them is half of this rung.

Stuck? rungs/02-ownership/solution/ has one way to do it, and ./ladder solution 2 runs the tests against it.

Check yourself #

• What happens to a Vec you pass by value, and to a u64?
• Why can't you push to a Vec while holding &v[0]?
• Why does take return &'a [u8], not a slice tied to the reader?
• Why can the kernel forbid unsafe code?