Rust: A Type System You Didn't Know You Wanted

Felix Klock (@pnkfelix), Mozilla

http://is.gd/3oAeuH (Space goes to next slide; Arrows navigate; Esc gives overview.)

Rust: What? Why? (How?)

Rust: What

  • New systems programming language

    • fast; FFI interface; data layout control

    • compete (and interface with) with C/C++

  • Mix in the classic hits of PL

    • user-defined iterators, RAII, objects with vtable method dispatch, generics / F-bounded polymorphism, algebraic data types, affine types, et cetera

Rust: Where

Language and API docs

Playpen (encore)

http://play.rust-lang.org/

Motivational Demos

A taste

  • Three fast "amuse bouches"
    • not the main course
    • (not even an appetizer)

Abstraction without overhead

The below loop demo compiles down to tight code:

// sums all the positive values in `v`
fn sum_pos(v: &Vec<i32>) -> i32 {
    let mut sum = 0;
    for i in v.iter().filter(|i| **i > 0) {
        sum += *i;
    }
    sum
}

Abstraction without overhead

Generated x86_64 machine code for fn sum_pos:

    leaq    (%rdi,%rsi,4), %rcx
    xorl    %eax, %eax
    jmp .LBB5_1
.LBB5_3:
    addl    %edx, %eax
    .align  16, 0x90
.LBB5_1:
    cmpq    %rdi, %rcx
    je  .LBB5_4
    movl    (%rdi), %edx
    addq    $4, %rdi
    testl   %edx, %edx
    jle .LBB5_1
    jmp .LBB5_3
.LBB5_4:
    retq

Abstraction without overhead

Or, if the first was not high-level enough:

fn foo(v: &Vec<i32>) -> i32 {
    v.iter().filter(|i| **i > 0).map(|i| *i).sum()
}

(This second loop demo compiles down to the same tight code!)

Memory safety

Example: catches iterator invalidation bugs (aka ConcurrentModificationException - at compile-time)

fn this_wont_compile(v: &mut Vec<i32>) -> i32 {
    let mut sum = 0;
    for &i in v.iter() {
        sum += i;
        if i > 0 { v.push(0); }
        //         ~~~~~~~~~ invalid! (might realloc
        //                   the backing storage for `v`)
    }
    sum
}
error: cannot borrow `*v` as mutable because it is also borrowed
       as immutable
        if i > 0 { v.push(0); }
                   ^
note: previous borrow of `*v` occurs here; the immutable borrow
      prevents subsequent moves or mutable borrows of `*v` until
      the borrow ends
    for &i in v.iter() {
              ^

Slick, Fearless Concurrency

See also Fearless Concurrency blog post.

use std::thread;
fn par_max(data: &[u8]) -> u8 {
    if data.len() <= 4 { return seq_max(data); }
    let len_4 = data.len() / 4; // DATA = [A .., B .., C .., D..]
    let (q1, rest) = data.split_at(len_4);    // (A.. \ B..C..D..)
    let (q2, rest) = rest.split_at(len_4);    //  (B.. \ C..D..)
    let (q3, q4)   = rest.split_at(len_4);    //   (C.. \ D..)
    let t1 = thread::scoped(|| seq_max(q1));  // fork A..
    let t2 = thread::scoped(|| seq_max(q2));  // fork B..
    let t3 = thread::scoped(|| seq_max(q3));  // fork C..
    let v4 = seq_max(q4);                     // compute D..
    let (v1, v2, v3) = (t1.join(), t2.join(), t3.join()); // join!
    return seq_max(&[v1, v2, v3, v4]);
}

(caveat: above is using unstable thread::scoped API)

Rust: Why?

Rust: Why?

  • Why is Mozilla investing in this?

  • To compete

    C/C++ impedes ability to compete in the browser market

  • Fast experimentation (and deployment)

    ⇒ Competitive Advantage

Servo

browser implementation research platform

written in Rust

Experiments

  • parallel paint

  • parallel layout

  • parallel css selector matching

Rust: A note on goals

What is "soundness"?

Segfault is not okay

But: "clean" shutdown (e.g. on internal error) is okay

Rust has panic!, and atop it assert! etc

(A panic unwinds the stack, cleaning up resources)

So

Rust uses dynamic checks (and resorts to panic!) where appropriate

But

Prefers static assurances when feasible

(we are pragmatists)

Rust: How?

Rust: How? (The Big Ideas)

Ownership + Move Semantics

(explicit resource control)

Borrowing

(brings back reference semantics)

Lifetimes

(encode safety constraints between references)

Move Semantics

Create (and modify) owned:

#[test]
pub fn create_owned() {
    let mut vec = Vec::new();         //  + (`vec` created ...
    vec.push(2000);                   //  |  ... and
    vec.push( 400);                   //  |       also
    vec.push(  60);                   //  |        mutated ...
    println!("vec: {:?}", vec);       //  |
    let the_sum = sum(vec);           //  o ... and moved)
    // (starting here, access to `vec` is static error)
    println!("the_sum: {}", the_sum);
}

At scope end, clean up initialized (+ unmoved) variables

fn sum(v: Vec<i32>) -> i32 {          //  o
   let mut accum = 0;                 //  |
   for i in v.iter() { accum += *i; } //  |
   accum // (p.s. where is `return`?) //  |
}                                     //  * (`v` destroyed/freed)

Freely Copied Values versus Moved Objects

Integers, characters, etc use copy semantics

let x: i32 = calculate();
let y = x;
// can still use `x` here

Structured data uses move semantics by default

  • Compiler checks attempts to opt-in to Copy "interface"
    • ("interface", aka "trait bound" in Rust)

Moved data errors

#[test]
fn demo_owned_vs_copied() {
    let moving_value = vec![1, 2, 3];
    let copied_value = 17;
    let tuple = (moving_value, copied_value);

    println!("copied_value: {:?}", copied_value);
    println!("moving_value: {:?}", moving_value);
}
error: use of moved value: `moving_value` [E0382]
    println!("moving_value: {:?}", moving_value);
                                   ^~~~~~~~~~~~

note: `moving_value` moved here because it has type
      `collections::vec::Vec<i32>`, which is non-copyable
    let tuple = (moving_value, copied_value);
                 ^~~~~~~~~~~~

Moves insufficient on their own

Imagine programming without reuse

#[test]
fn moves_insufficient() {
    let vec = expensive_vector_computation();

    let result1 = some_vec_calculation(vec); // <-- `vec` moved here

    let result2 = other_calculation(vec); // oops, `vec` is *gone*

    combine(result1, result2);

}
error: use of moved value: `vec` [E0382]
    let result2 = other_calculation(vec); // oops
                                    ^~~
note: `vec` moved here because it has type
      `collections::vec::Vec<i32>`, which is non-copyable
    let result1 = some_vec_calculation(vec); // <-- `vec` moved here
                                       ^~~

Learning to Share

Borrowing

Lend references to values

#[test]
fn hooray_for_borrows() {
    let vec = expensive_vector_computation();

    let result1 = some_vec_calculation(&vec); // <-- lend out `vec`

    let result2 = other_calculation(&vec); // <-- lend again, no prob

    combine(result1, result2);

} // (`vec` is destroyed/freed aka "dropped" here)
                                    &vec
                                    ~~~~
                                      |
                              a borrow expression

Mo' features, mo' problems

  • Why are safety violations generally hard to detect?

  • It is due to aliasing

  • Borrows reintroduce aliasing

Q: How to ensure safety in presence of aliasing?

A: Restrict the aliasing

Restricted aliasing

Analogy: RW-lock

  • Many readers at once, or one writer with exclusive access

  • Read-only operations do not require exclusive access

  • Exclusive access requires there are no other readers

Rust uses similar model (but at compile-time) for borrows

The Family of Types

  • T: base type. Moves, unless bounded by Copy trait

  • &T: shared ref, "read-only" access; copyable

    • programmer (+ compiler) must assumed aliased

    • (i.e. "many readers")

  • &mut T: "mutable" ref, exclusive access; non-copy

    • assured unaliased

    • (i.e. "at most one writer")

Concrete Examples of Types

readin', writin', and transfer'n

fn read(v: &Vec<String>) -> String {
    let first: &String = &v[0]; // borrow ref to first elem
    println!("v[0]: {}", first);
    return first.clone();
}
fn modify(v: &mut Vec<String>, name: &str) {
    let freshly_created = format!("Hello {}", name);
    v.push(freshly_created);
}
fn consume(v: Vec<String>) -> String {
    for s in v { return s; }
    panic!("v was empty?!?");
}

Calls to the three variants

fn read(v: &Vec<String>) -> String { ... }
fn modify(v: &mut Vec<String>, name: &str) { ... }
fn consume(v: Vec<String>) -> String { ... }
fn user_input() -> String { format!("World") }

#[test]
fn demo() {
    let mut v: Vec<String> = vec![user_input()];
    let first = read(&v).clone();
    modify(&mut v, &first);
    consume(v);
}

More on Scopes

Borrowing (immutably)

#[test]
fn show_some_borrows() {

    let v1 = vec![1, 2, 3];
    let v2 = vec![4, 5, 6];

    let r1 = &v1;
    let r2 = &v2;
    foo(r1);
    foo(r2);

}
fn foo<'a>(v: &'a Vec<i32>) { println!("v[1]: {}", v[1]); }

&v1 and &v2 are borrowing v1 and v2.

Scopes and Lifetimes

#[test]
fn show_some_lifetimes() {

    let v1 = vec![1, 2, 3]; //                 +
    let v2 = vec![4, 5, 6]; //            +    |
                            //            |    |
    let r1 = &v1;           //       +    |    |
    let r2 = &v2;           //  +    |    |    |
    foo(r1);                //  |    |    |    |
    foo(r2);                // 'r2  'r1  'v2  'v1
                            //  |    |    |    |
}                           //  *    *    *    *
fn foo<'a>(v: &'a Vec<i32>) { println!("v[1]: {}", v[1]); }

Each borrow selects "appropriate" lifetime 'a.

Borrow Checking Prevents Errors

fn borrow_checking_prevents_errors() {

    let v1 = vec![1, 2, 3];      //        +
                                 //        |
    let r1 = &v1;                //  +    'v1
                                 //  |     |
    consume(v1);                 // 'r1   (moved)
    foo(r1);                     //  |
}                                //  *
    fn foo<'a>(v: &'a Vec<i32>) { println!("v[1]: {}", v[1]); }
    fn consume(v: Vec<i32>) { /* `v` *dropped* at scope end */ }

foo(r1) attempts an indirect read of v1

error: cannot move out of `v1` because it is borrowed
    consume(v1);
            ^~
note: borrow of `v1` occurs here
    let r1 = &v1;
              ^~

Lifetimes and Lexical Scope

fn borrow_checking_may_seem_simple_minded() {

    let v1 = vec![1, 2, 3];      //        +
                                 //        |
    let r1 = &v1;                //  +    'v1
                                 //  |     |
    consume(v1);                 // 'r1   (moved)
    // (no call to read)         //  |
}                                //  *
    fn foo<'a>(v: &'a Vec<i32>) { println!("v[1]: {}", v[1]); }
    fn consume(v: Vec<i32>) { }
error: cannot move out of `v1` because it is borrowed
    consume(v1);
            ^~
note: borrow of `v1` occurs here
    let r1 = &v1;
              ^~

(artifact of lexical-scope based implementation)

Built on lexical scopes, but non-trivial

#[test]
fn copying_can_extend_a_borrows_lifetime_1() {
    fn foo<'a>(v: &'a Vec<i32>) { println!("v[1]: {}", v[1]); }
    let v1 = vec![1, 2, 3]; //         +
    let v2 = vec![4, 5, 6]; //         |    +
    let r2 = {              //         |    |
        let r1 = &v1;       //  +      |    |
        //       ~~~ <--- A //  |      |    |
        foo(r1);            // 'r1     |    |
        &v2                 //  |     'v1  'v2
    };                      //  *  +   |    |
    // (maybe mutate `v1`   //     |   |    |
    // here someday?)       //     |   |    |
                            //    'r2  |    |
    foo(r2);                //     |   |    |
}                           //     *   *    *

How long should the borrow &v1 last?

Built on lexical scopes, but non-trivial

#[test]
fn copying_can_extend_a_borrows_lifetime_2() {
    fn foo<'a>(v: &'a Vec<i32>) { println!("v[1]: {}", v[1]); }
    let v1 = vec![1, 2, 3]; //         +
    let v2 = vec![4, 5, 6]; //         |    +
    let r2 = {              //         |    |
        let r1 = &v1;       //  +      |    |
        //       ~~~ <--- A //  |      |    |
        foo(r1);            // 'r1     |    |
        r1  // <--------- B //  |     'v1  'v2
    };                      //  *  +   |    |
    // (maybe mutate `v1`   //     |   |    |
    // here someday?)       //     |   |    |
                            //    'r2  |    |
    foo(r2);                //     |   |    |
}                           //     *   *    *

How long should the borrow &v1 last now?

imm-borrows: can be copied freely

(super super useful to be able to share readable data!)

imm-borrows: can be copied freely

Implications:

  • must assume aliased (perhaps by another thread)
  • therefore not safe to mutate in general
#[test]
fn demo_cannot_mutate_imm_borrow() {
    let mut v1 = vec![1, 2, 3];
    let b = &v1;
    let (b1, b2, b3) = (b, b, b);
    try_modify(b);
    println!("v1: {:?}", v1);
}

fn try_modify(v: &Vec<i32>) {
    v.push(4);
}
error: cannot borrow immutable borrowed content `*v` as mutable
    v.push(4);
    ^

imm-borrows: can be copied freely

Implications:

  • must assume aliased (perhaps by another thread)
  • therefore not safe to mutate in general
#[test]
fn demo_cannot_mutate_imm_borrow() {
    let mut v1 = vec![1, 2, 3];
    let b = &v1;
    let (b1, b2, b3) = (b, b, b);
    try_modify(b);
    println!("v1: {:?}", v1);
}

fn try_modify(v: &Vec<i32>) {
    v.push(4);
}
WHAT
      A
         BUMMER!!!

my precious imperative algorithms!

&mut borrows

#[test]
fn demo_can_mutate_mut_borrow() {
    let mut v1 = vec![1, 2, 3];
    modify_vec(&mut v1);
    println!("v1: {:?}", v1);
}

fn modify_vec(v: &mut Vec<i32>) {
    v.push(4);
}
v1: [1, 2, 3, 4]

What does &mut mean (crucial)

For many (but not all) types, safe mutation requires exclusive access

Any operation requiring exclusive access should either:

  • take ownership, or,

  • take an &mut-reference

Exclusive Access versus Ownership

fn take_by_value(v: Vec<i32>) { let mut v = v; v.push(4);  }
fn take_mut_borrow(b: &mut Vec<i32>) { b.push(10); }
// seemingly similar in power
#[test]
fn demo_exclusive_access_versus_ownership() {
    let (mut v1, mut v2) = (vec![1, 2, 3], vec![7, 8, 9]);
    take_by_value(v1);
    take_mut_borrow(&mut v2);
    println!("v1: {:?} v2: {:?}", v1, v2);
}
error: use of moved value: `v1` [E0382]
    println!("v1: {:?} v2: {:?}", v1, v2);
                                  ^~
note: `v1` moved here
    take_by_value(v1);
                  ^~

ownership ⇒ power + responsibility (for dropping)

&mut ⇒ power without responsibility; (can only swap)

&mut safety enforcement

Data has at most one &mut borrow

fn take2<'a>(v1: &'a mut Vec<i32>, v2: &'a Vec<i32>) { }
#[test]
fn demo_cannot_mut_borrow_multiple_times() {
    let mut v1 = vec![1, 2, 3];
    let mut v2 = vec![1, 2, 3];
    take2(&mut v1, &mut v2); // <-- this is okay
    take2(&mut v1, &mut v1);
}
error: cannot borrow `v1` as mutable more than once at a time
    take2(&mut v1, &mut v1);
                        ^~
note: previous borrow of `v1` occurs here; the mutable borrow
      prevents subsequent moves, borrows, or modification of
      `v1` until the borrow ends
    take2(&mut v1, &mut v1);
               ^~

Cannot alias &mut-borrowed data

fn take2<'a>(v1: &'a mut Vec<i32>, v2: &'a Vec<i32>) { }
#[test]
fn demo_cannot_alias_mut_borrowed_data() {
    let mut v1 = vec![1, 2, 3];
    let mut v2 = vec![1, 2, 3];
    take2(&mut v1, &v2); // <-- this is okay
    take2(&mut v1, &v1);
}
error: cannot borrow `v1` as immutable because it is also borrowed
       as mutable
    take2(&mut v1, &v1);
                    ^~
note: previous borrow of `v1` occurs here; the mutable borrow 
      prevents subsequent moves, borrows, or modification of `v1`
      until the borrow ends
    take2(&mut v1, &v1);
               ^~

&mut T is non-copy

fn take2<'a>(v1: &'a mut Vec<i32>, v2: &'a Vec<i32>) { }
#[test]
fn demo_cannot_copy_mut_borrows() {
    let mut v1 = vec![1, 2, 3];
    let b = &mut v1;
    let c = b;
    take2(b, c);
}
error: use of moved value: `*b` [E0382]
    take2(b, c);
          ^
note: `b` moved here because it has type
      `&mut collections::vec::Vec<i32>`, which is moved by default
    let c = b;
        ^

(ensures exclusive access)

Wither a.method() ?

Rust has methods too

struct Point { x: i32, y: i32 }

impl Point {
    fn distance_from_origin(&self) -> i32 {
        let Point { x, y } = *self;
        let sum = (x*x + y*y) as f64;
        sum.sqrt() as i32
    }
}

#[test]
fn demo_dist() {
    let p = Point { x: 3, y: 4 };
    assert_eq!(5, p.distance_from_origin());
}

Method signatures

  • self: consumes receiver
  • &self: accesses receiver
  • &mut self: mutates receiver

Method signatures: &self

Accesses receiver

enum Option<T> { None, Some(T) } // algebraic data! generics!

impl<T> Option<T> {
    // &Option<T> -> bool
    fn is_some(&self) -> bool {
        match *self {
            Some(_) => true,
            None => false
        }
    }

    fn is_none(&self) -> bool {
        !self.is_some()
    }
}

Method signatures: &mut self

"Mutates" receiver

enum Option<T> { None, Some(T) }

impl<T> Option<T> {
    // &mut Option<T> -> Option<T>
    fn take(&mut self) -> Option<T> {
        let mut src = None;
        swap(self, &mut src);
        src
    }
}

Method signatures: self

"Consumes" Takes ownership of receiver

impl<T> Option<T> {
    // Option<T> -> T
    fn unwrap_or(self, default: T) -> T {
        match self {
            Some(x) => x,
            None => default
        }
    } // one of `self` or `default` dropped at end
}
impl<T> Option<T> {
    fn is_some(&self) -> bool { ... }
    fn is_none(&self) -> bool { ... }
    fn take(&mut self) -> Option<T> { ... }
    fn unwrap_or(self, default: T) -> T { ... }
}

Some magic: method invocations automatically do borrows and derefs as necessary on the receiver ("auto-ref").

fn demo_subroutine(name: String) {
    let mut hi = Some(format!("Hello {}", &name));
    assert!(hi.is_some());   // this is an `&hi`

    let grabbed = hi.take(); // this is an `&mut hi`
    assert!(hi.is_none());   // this is an `&hi`

    // and this consumes `grabbed`
    assert!(&grabbed.unwrap_or(name)[0..5] == "Hello");
}

For the C++ fans in the audience: Smart Pointers

"Smart" "Pointers"

  • Box<T>: unique reference to T on (malloc/free-style) heap

  • Rc<T>: shared ownership, thread-local

  • Arc<T>: shared ownership, safe across threads

All of above deref to &T

Deref works here too

#[test]
fn demo_rc_of_point() {
    use std::rc::Rc;
    let p1 = Rc::new(Point { x: 3, y: 4 });
    let p2 = p1.clone();
    assert_eq!(5, p1.distance_from_origin());
    assert_eq!(5, p2.distance_from_origin());

    // p1.x = 6; // (STATIC ERROR; cannot assign Rc contents)
}

Other Deref fun

Box<T>, Rc<T>, Arc<T> all deref to &T

But we also have things like this:

pub enum Cow<'a, B> where B: ToOwned {
    Borrowed(&'a B),
    Owned(<B as ToOwned>::Owned)
}

which derefs to &B, even if it is in the Owned variant.

(Useful for APIs that want to delay the decision of whether to return an owned value or a borrowed reference.)

Lifetime Bindings

Lifetime Bindings 1

We saw this kind of thing before:

#[test]
fn explicit_lifetime_binding_1() {
    fn print<'a>(ints: &'a Vec<i32>) {
        println!("v_1: {}", ints[1]);
    }
    let v1 = vec![1, 2, 3];
    print(&v1)
}

Lifetime Bindings 2

You can bind distinct lifetimes:

#[test]
fn explicit_lifetime_binding_2() {
    fn print<'a, 'b>(ptrs: &'a Vec<&'b i32>) {
        println!("v_1: {}", ptrs[1]);

    }
    let one = 1;
    let two = 2;
    let three = 3;
    let four = 4;
    let v1 = vec![&one, &two, &three];
    print(&v1)
}

Lifetime Bindings 3

Encode constraints by reusing same lifetime:

#[test]
fn explicit_lifetime_binding_3() {
    fn print<'a, 'b>(ptrs: &'a mut Vec<&'b i32>, ptr: &'b i32) {
        println!("v_1: {}", ptrs[1]);
        ptrs.push(ptr);
    }
    let one = 1;
    let two = 2;
    let three = 3;
    let four = 4;
    let mut v1 = vec![&one, &two, &three];
    print(&mut v1, &four);
}

Lifetime Bindings 4

Encode constraints by reusing same lifetime:

#[test]
fn explicit_lifetime_binding_4() {
    fn print<'a, 'b>(ptrs: &'a mut Vec<&'b i32>, ptr: &'b i32) {
        println!("v_1: {}", ptrs[1]);//~~~            ~~~
        ptrs.push(ptr);            //   |              |
    }                              // this must match that,
    let one = 1;                   // otherwise push is bogus
    let two = 2;
    let three = 3;
    let four = 4;
    let mut v1 = vec![&one, &two, &three];
    print(&mut v1, &four);
}

Lifetime Bindings 5

Compiler catches missing necessary constraints:

#[test]
fn explicit_lifetime_binding_5() {
    fn print<'a, 'b, 'c>(ptrs: &'a mut Vec<&'b i32>, ptr: &'c i32) {
        println!("v_1: {}", ptrs[1]);  //  ~~~            ~~~
        ptrs.push(ptr);                //   |              |
    }                                  // this must match that,
    let one = 1;                       // otherwise push is bogus
}
error: cannot infer an appropriate lifetime for automatic coercion
       due to conflicting requirements
        ptrs.push(ptr);
                  ^~~
help: consider using an explicit lifetime parameter as shown:
    fn print<'a, 'b>(ptrs: &'a mut Vec<&'b i32>, ptr: &'b i32)

Borrowed return values 1

fn first_n_last<'a>(ints: &'a Vec<i32>) -> (&'a i32, &'a i32) {
    //                                      ~~~~~~~  ~~~~~~~
    (&ints[0], &ints[ints.len() - 1])
}
#[test]
fn demo_borrowed_return_values() {
    let v = vec![1, 2, 3, 4];
    let (first, fourth) = first_n_last(&v);
    assert_eq!(*first, 1);
    assert_eq!(*fourth, 4);
}

(compiler ensures borrow &v lasts long enough to satisfy reads of first and fourth)

Borrowed return values 2

fn first_n_last<'a>(ints: Vec<i32>) -> (&'a i32, &'a i32) {
    //                    ~~~~~~~~ (hint)
    (&ints[0], &ints[ints.len() - 1])
}

Why doesn't this work?

error: `ints` does not live long enough
    (&ints[0], &ints[ints.len() - 1])
      ^~~~
note: reference must be valid for the lifetime 'a ...
note: ...but borrowed value is only valid for the scope of
note:    parameters for function

caller chooses 'a; fn body must work for any such choice

(Parameters dropped at scope end; won't live long enough)

Lifetime Elision

All the 'a, 'b, ... are ugly

Lifetime Elision 1

#[test]
fn lifetime_elision_1() {
    fn print1<'a>(ints: &'a Vec<i32>) {
        println!("v_1: {}", ints[1]);
    }
    fn print2<'a, 'b>(ptrs: &'a Vec<&'b i32>) {
        println!("v_1: {}", ptrs[1]);

    }
    fn print3<'a, 'b>(ptrs: &'a mut Vec<&'b i32>, ptr: &'b i32) {
        println!("v_1: {}", ptrs[1]);
        ptrs.push(ptr);
    }
}

Lifetime Elision 2

#[test]
fn lifetime_elision_2() {
    fn print1    (ints: &   Vec<i32>) {
        println!("v_1: {}", ints[1]);
    }
    fn print2        (ptrs: &   Vec<&   i32>) {
        println!("v_1: {}", ptrs[1]);

    }
    fn print3<    'b>(ptrs: &   mut Vec<&'b i32>, ptr: &'b i32) {
        println!("v_1: {}", ptrs[1]);
        ptrs.push(ptr);
    }
}

Lifetime Elision 3

#[test]
fn lifetime_elision_3() {
    fn print1(ints: &Vec<i32>) {
        println!("v_1: {}", ints[1]);
    }
    fn print2(ptrs: &Vec<&i32>) {
        println!("v_1: {}", ptrs[1]);

    }
    fn print3<'b>(ptrs: &mut Vec<&'b i32>, ptr: &'b i32) {
        println!("v_1: {}", ptrs[1]);
        ptrs.push(ptr);
    }
}

Generic items

Generic items 1

#[test]
fn generic_items_1() {
    fn push_twice<'b>(ptrs: &mut Vec<&'b i32>, ptr: &'b i32) {
        ptrs.push(ptr);
        ptrs.push(ptr);
    }
    let (one, two, three, four) = (1, 2, 3, 4);
    let mut v = vec![&one, &two, &three];
    push_twice(&mut v, &four);
}

This obviously generalizes beyond i32!

Generic items 2

#[test]
fn generic_items_2() {
    fn push_twice<'b, T>(ptrs: &mut Vec<&'b T>, ptr: &'b T) {
        ptrs.push(ptr);
        ptrs.push(ptr);
    }
    let (one, two, three, four) = (1, 2, 3, 4);
    let mut v = vec![&one, &two, &three];
    push_twice(&mut v, &four);
}

This is going so smoothly; lets try printing v_1 again!

Generic items 3

#[test]
fn generic_items_3() {
    fn push_twice<'b, T>(ptrs: &mut Vec<&'b T>, ptr: &'b T) {
        println!("v_1: {}", ptrs[1]);
        ptrs.push(ptr);
        ptrs.push(ptr);
    }
    let (one, two, three, four) = (1, 2, 3, 4);
    let mut v = vec![&one, &two, &three];
    push_twice(&mut v, &four);
}
error: trait `core::fmt::Display` not implemented for the type `T`
        println!("v_1: {}", ptrs[1]);
                            ^~~~~~~

(Reminder: Rust is not C++)

Trait-bounded polymorphism

Trait-bounded polymorphism

trait Dimensioned {
    fn height(&self) -> u32;
    fn width(&self) -> u32;
}

fn stacked_height<S>(v: &[S]) -> u32 where S: Dimensioned {
    let mut accum = 0;
    for s in v { accum += s.height() }
    accum
}

Trait Impls

struct Rect { w: u32, h: u32 }
struct Circle { r: u32 }

impl Dimensioned for Rect {
    fn height(&self) -> u32 { self.h }
    fn width(&self) -> u32 { self.w }
}

impl Dimensioned for Circle {
    fn height(&self) -> u32 { self.r * 2 }
    fn width(&self) -> u32 { self.r * 2 }
}

Traits in Action

impl Rect {
    fn square(l: u32) -> Rect { Rect { w: l, h: l } }
}
impl Circle {
    fn with_radius(r: u32) -> Circle { Circle { r: r } }
}

#[test]
fn trait_bounded_polymorphism() {
    let squares = [ Rect::square(1), Rect::square(2) ];
    let circles = [ Circle::with_radius(1), Circle::with_radius(2)];
    assert_eq!(stacked_height(&squares), 3);
    assert_eq!(stacked_height(&circles), 6);
}

Generics do not suffice

Generics do not suffice

#[test]
fn parametric_fail() {
    let shapes = [Rect::square(1), Circle::with_radius(2)];
    assert_eq!(stacked_height(&shapes), 5);
}
error: mismatched types:
 expected `Rect`,
    found `Circle`
    let shapes = [Rect::square(1), Circle::with_radius(2)];
                                   ^~~~~~~~~~~~~~~~~~~~~~

Uniformity of T in Vec<T> is why

struct Rect { w: u32, h: u32 }
struct Circle { r: u32 }

fn parametric_fail() {
    let shapes = [Rect::square(1), Circle::with_radius(2)];
    //  ~~~~~~    ~~~~~~~~~~~~~~~  ~~~~~~~~~~~~~~~~~~~~~~
    //    |              |                    |
    //    |       This is 8 bytes     This is 4-bytes
    //    |
    //  There's no uniform array
    //  type to hold both in-line.
}

This is a job for ...

Object-Oriented Programming!

Traits as Objects 1

fn stacked_obj_refs(v: &[&Dimensioned]) -> u32 {
    let mut accum = 0;
    for s in v { accum += s.height() }
    accum
}

#[test]
fn demo_objs_1() {
    let r = Rect::square(1);
    let c = Circle::with_radius(2);
    let shapes: [&Dimensioned; 2] = [&r, &c];
    assert_eq!(stacked_obj_refs(&shapes), 5);
}

Traits as Objects 2

fn stacked_obj_boxes(v: &[Box<Dimensioned>]) -> u32 {
    let mut accum = 0;
    for s in v { accum += s.height() }
    accum
}

#[test]
fn demo_objs_2() {
    let shapes: [Box<Dimensioned>; 2] =
        [Box::new(Rect::square(1)), Box::new(Circle::with_radius(2))];
    assert_eq!(stacked_obj_boxes(&shapes), 5);
}

OOP is nice; how about Functional Programming?

Closures 1

  • Can pass functions around as first class entities

  • Functions can close over externally defined state

Reminder from Javascript:

closures.js

function add3(x) { return x + 3; }

// take function as parameter:
function do_twice(f, y) { return f(f(y)); }

// return function that references outer parameter `z`
function make_adder(z) {
    return function(w) { return w + z; };
}

var add4 = make_adder(4);
var ten = do_twice(add4, 2);

Closures 2

  • In (classic) Javascript, closure syntax is:

    function (args, ...) { body; ... }

    where body can refer to things from outside.

  • In Rust, the analogous closure expression syntax is:

    |args, ...| { body; ... }

    with a few extra details:

  • opt. move (forces capture-by-move)

  • opt. arg. and return types (inferred when omitted)

Closures 3

#[test]
fn demo_closure() {
    fn add3(x: i32) -> i32 { x + 3 } // <- fn, *not* a closure
    fn do_twice1<F:Fn(i32) -> i32>(f: F, x: i32) -> i32 { f(f(x)) }
    //             ~~~~~~~~~~~~~~ closure type
    fn do_twice2(f: &Fn(i32) -> i32, x: i32) -> i32 { f(f(x)) }

    fn make_adder(y: i32) -> Box<Fn(i32) -> i32> {
        Box::new(move |x| { x + y })
            //   ~~~~~~~~~~~~~~~~~~ closure expression
    }

    let add4 = make_adder(4);
    let six = do_twice1(&add3, 0); let ten = do_twice1(&*add4, 2);
    assert_eq!((six, ten), (6, 10));
    let six = do_twice2(&add3, 0); let ten = do_twice2(&*add4, 2);
    assert_eq!((six, ten), (6, 10));
}

Interior Mutability

What about mutation outside of &mut?

Interior Mutability: Cell and RefCell structs

  • Both types have mutator methods that take &self

    • not &mut self

  • Cell<T>: has get and set methods, but only accepts T:Copy

  • RefCell<T> handles all types T, but dynamically enforces the rules.

    • borrow method returns read-only Ref (many-readers), and panic!'s on outstanding mut-borrow

    • borrow_mut method returns read/write RefMut, and panic!'s on any outstanding borrow.

Demos of Cell and RefCell types

Cell working:

#[test]
fn demo_cell() {
    use std::cell::Cell;
    let c = Cell::new(3);
    let p1: &Cell<i32> = &c;
    let p2: &Cell<i32> = &c;
    assert_eq!(p2.get(), 3);
    p1.set(4);
    assert_eq!(p2.get(), 4);
}

Cell cannot hold non-Copy data

#[test]
fn demo_cell_vec_no_work() {
    use std::cell::Cell;
    let c = Cell::new(vec![1,2,3]);
    let p1: &Cell<Vec<i32>> = &c;
    let p2: &Cell<Vec<i32>> = &c;
    assert_eq!(p2.get(), [1,2,3]);
    p1.set(vec![4,5,6]);
    assert_eq!(p2.get(), [4,5,6]);
}
error: the trait `core::marker::Copy` is not implemented
       for the type `collections::vec::Vec<_>` [E0277]
    let c = Cell::new(vec![1,2,3]);
            ^~~~~~~~~

RefCell handles all data

#[test]
fn demo_refcell_vec() {
    use std::cell::RefCell;
    let c = RefCell::new(vec![1,2,3]);
    let p1: &RefCell<Vec<i32>> = &c;
    let p2: &RefCell<Vec<i32>> = &c;
    assert_eq!(*p2.borrow(), [1,2,3]);
    p1.borrow_mut().push(4);
    assert_eq!(*p2.borrow(), [1,2,3,4]);
}

RefCell dynamically errors if misused

#[test]
fn demo_refcell_vec_no_work() {
    use std::cell::RefCell;
    let c = RefCell::new(vec![1,2,3]);
    let p1: &RefCell<Vec<i32>> = &c;
    let p2: &RefCell<Vec<i32>> = &c;
    let b2 = p2.borrow();
    assert_eq!(*b2, [1,2,3]);
    p1.borrow_mut().push(4);
    assert_eq!(*b2, [1,2,3,4]);
}
---- a01_start::demo_refcell_vec_no_work stdout ----
    thread 'a01_start::demo_refcell_vec_no_work' panicked
        at 'RefCell<T> already borrowed'

(This is not unsound!)

Destructors

The Drop trait

If a data-type is represents some resource with associated cleanup actions, then it should implement Drop

struct Yell { name: &'static str }
impl Drop for Yell {
    fn drop(&mut self) {
        println!("My name is {}; ", self.name);
    }
}

Silly example of Yelling

fn main() {
    let bob = Yell { name: "Bob" };
    let carol = Yell {
        name: {
            let carols_dad = Yell { name: "David" };
            "Carol"
        } // end of scope: carols_dad is dropped
    };
    let ed = Yell { name: "Ed" };
    let frank = Yell { name: panic!("What is Frank's name?") };
    println!("We never get to Gregor");
    let gregor = Yell { name: "Gregor" };
}

prints:

My name is David;
thread '<main>' panicked at 'What is Frank's name?', <anon>:16
My name is Ed;
My name is Carol;
My name is Bob;

More realistic example: Rc implementation

struct RcBox<T> { strong: Cell<usize>, value: T }
pub struct Rc<T> { _ptr: NonZero<*mut RcBox<T>> }

impl<T: ?Sized> Clone for Rc<T> {
    fn clone(&self) -> Rc<T> {
        self.inc_strong();
        Rc { _ptr: self._ptr }
    }
}

impl<T> Drop for Rc<T> {
    fn drop(&mut self) {
        unsafe {
            let ptr = *self._ptr;
            self.decrement_count();
            if self.current_count() == 0 {
                drop_in_place(&mut (*ptr).value);
                deallocate(ptr);
            }
        }
    }
}

Concurrency

Concurrency

Rust's killer feature:

Data-race freedom

built atop same foundation as memory safety

Here's what one concurrency API looks like

thread::spawn

pub fn main() {
    use std::thread;
    let al = "long lost pal";
    thread::spawn(move || {

        println!("i can be your {}", al);
    });

    println!("why am i soft in the middle");
    // Note: might exit before spawned thread gets chance to print
}

channels for message passing

#[test] fn demo_channel() {
    fn fib(x: i64) -> (i64, i64) { // returns `(x, fib(x))`
        if x <= 1 { (x,1) } else { (x, fib(x-1).1 + fib(x-2).1) }
    }
    use std::thread;
    use std::sync::mpsc::channel;
    let (tx, rx) = channel(); // tx: "transmit", rx: "receive"
    let al = "al";
    thread::spawn(move || {
        tx.send(fib(10)).unwrap();
        println!("you can call me {}", al);
    });
    let f_15 = fib(15).1;
    println!("why am i short of attention");
    let f_10 = rx.recv().unwrap().1; // (this blocks to await data)
    assert_eq!((f_10, f_15), (89, 987));
}

channels are abstraction, data-race free

No data races: What about our precious mutation?

No data races 1: "direct" assign

#[test] fn demo_catch_direct() {
    fn fib(x: i64) -> (i64, i64) { // returns `(x, fib(x))`
        if x <= 1 { (x,1) } else { (x, fib(x-1).1 + fib(x-2).1) }
    }
    use std::thread;
    let al = "al";
    let mut f_10_recv = (0, 0);

    thread::spawn(move || {
        f_10_recv = fib(10);
        println!("you can call me {}", al);
    });
    let f_15 = fib(15).1;
    while f_10_recv.0 == 0 { }  // <-- many alarm bells
    let f_10 = f_10_recv.1;
    println!("why am i short of attention");
    assert_eq!((f_10, f_15), (89, 987));
}

compiles; does not work (no actual communication; implicit copying)

No data races 2: mut-ref

#[test] fn demo_catch_mutref() {
    fn fib(x: i64) -> (i64, i64) { // returns `(x, fib(x))`
        if x <= 1 { (x,1) } else { (x, fib(x-1).1 + fib(x-2).1) }
    }
    use std::thread;
    let al = "al";
    let mut f_10_recv = (0, 0);
    let ptr_recv = &mut f_10_recv; // <-- Okay, say what we meant
    thread::spawn(move || {
        *ptr_recv = fib(10);
        println!("you can call me {}", al);
    });
    let f_15 = fib(15).1;
    while f_10_recv.0 == 0 { }  // <-- many alarm bells
    let f_10 = f_10_recv.1;
    println!("why am i short of attention");
    assert_eq!((f_10, f_15), (89, 987));
}

does not compile: spawn can't share ref to stack-local

Concurrency as a library concern

Libraries can provide new APIs

New system interfaces

New abstractions

Concurrency: New system interfaces

New system interfaces

e.g., Apple's Grand Central Dispatch

Rust wrapper developed by 3rd party contributor

dispatch (from crates.io)
dispatch (from crates.io)

New system interfaces

Cargo.toml

[dependencies]
dispatch = "0.0.1"
fn demo_gcd() {
    use dispatch::{Queue, QueuePriority};
    let queue = Queue::global(QueuePriority::Default);
    let mut nums = vec![1, 2];
    queue.apply(&mut nums, |x| *x += 1);
    assert!(nums == [2, 3]);
    let nums = queue.map(nums, |x| x.to_string());
    assert!(nums[0] == "2");
}

Implementation almost certainly relies on unsafe code

"buyer beware" (i.e. audit, in some manner)

Demo: dispatch misuse, caught!

fn demo_gcd2() {
    use dispatch::{Queue, QueuePriority};
    let queue = Queue::global(QueuePriority::Default);
    let mut indices = vec![1, 0];
    let mut nums = vec![1, 2];
    queue.apply(&mut indices, |i| nums[*i] += 1);
    assert!(nums == [2, 3]);
    let nums = queue.map(nums, |x| x.to_string());
    assert!(nums[0] == "2");
}

(Type system catches above attempt to close over &mut-references in a closure that is not allowed carry such.)

Concurrency: New abstractions

New abstractions

Old: thread::spawn

  • child and parent proceed independently

    • (parent can wait for the child, but not required to)

New: Fork-join parallelism

  • parent can share stack-local state with child thread(s)

    • parent must wait for child (since it shared local state on stack frame)

New abstractions: Constraints

  • thread::spawn: child and parent cannot share stack state

  • fork-join: parent must wait for children before returning

We can encode both constraints in Rust

  • Ensures clients obey the relevant protocol!

Demo of (unstable, unsound) fork join API

thread::scoped

fn seq_max(partial_data: &[u8]) -> u8 {
    *partial_data.iter().max().unwrap()
}

fn par_max(data: &[u8]) -> u8 {
    if data.len() <= 4 { return seq_max(data); }
    let len_4 = data.len() / 4; // DATA = [A..B..C..D..]
    let (q1, rest) = data.split_at(len_4); // (A.. \ B..C..D..)
    let (q2, rest) = rest.split_at(len_4); //  (B.. \ C..D..)
    let (q3, q4)   = rest.split_at(len_4); //   (C.. \ D..)
    let t1 = ::std::thread::scoped(|| seq_max(q1)); // fork A..
    let t2 = ::std::thread::scoped(|| seq_max(q2)); // fork B..
    let t3 = ::std::thread::scoped(|| seq_max(q3)); // fork C..
    let v4 = seq_max(q4); //                        compute D..
    let (v1, v2, v3) = (t1.join(), t2.join(), t3.join()); // join!
    return seq_max(&[v1, v2, v3, v4]);
}

thread::scoped shows a new trick

  • thread::spawn disallowed passing refs to stack-local data

  • Allowing that is the whole point of thread::scoped

    • (caveat: thread::scoped API is unstable, and undergoing revision due to subtle soundness issue)

Benchmarking par_max 1

extern crate test; use std::iter;
const LIL: usize = 20 * 1024;
const BIG: usize = LIL * 1024;

fn make_data(count: usize) -> Vec<u8> {
    let mut data: Vec<u8> = iter::repeat(10).take(count).collect();
    data.push(200); data.push(3); return data;
}

#[bench] fn bench_big_seq(b: &mut test::Bencher) {
    let data = make_data(BIG);
    b.iter(|| assert_eq!(seq_max(&data), 200));
}
#[bench] fn bench_big_par(b: &mut test::Bencher) {
    let data = make_data(BIG);
    b.iter(|| assert_eq!(par_max(&data), 200));
}
bench_big_par ... bench:   3,763,711 ns/iter (+/- 1,140,321)
bench_big_seq ... bench:  21,633,799 ns/iter (+/- 2,522,262)

Benchmarking par_max 2

const LIL: usize = 20 * 1024;
const BIG: usize = LIL * 1024;
bench_big_par ... bench:   3,763,711 ns/iter (+/- 1,140,321)
bench_big_seq ... bench:  21,633,799 ns/iter (+/- 2,522,262)
#[bench] fn bench_lil_seq(b: &mut test::Bencher) {
    let data = make_data(LIL);
    b.iter(|| assert_eq!(seq_max(&data), 200));
}
#[bench] fn bench_lil_par(b: &mut test::Bencher) {
    let data = make_data(LIL);
    b.iter(|| assert_eq!(par_max(&data), 200));
}
bench_lil_par ... bench:      59,274 ns/iter (+/- 7,756)
bench_lil_seq ... bench:      15,432 ns/iter (+/- 1,961)

(fn par_max could tune threshold for seq. path)

What was that about preventing data races?

Send, Sync

  • If S: Send, then passing (e.g. moving) a S to another thread is safe.

  • If T: Sync, then copying a &T to another thread is safe.

  • (For Rust, "safe" includes "no data races exposed.")

Concurrency: How?

Crucial trick: Send and Sync traits

If S: Send, can transfer S across thread boundaries

OTOH: A type T implementing Sync or might might not be sendable...

...but &T is always Send for a T: Sync (!)

(This is what makes Sync interesting)

Rust compiler automatically marks types as Send or Sync, based on a recursive analysis of their structure

Examples

Rust compiler automatically marks types as Send or Sync, based on a recursive analysis of their structure

e.g.:

  • i32 is Send.

  • Vec<T>: Send iff T: Send

  • Box<T> (owned): Send iff T: Send, Sync iff T: Sync

    • Why Send rule? because can move T out of a (consumed) box.

  • Rc<T> (shared): neither Send nor Sync (for any T)

  • Arc<T> (shared): always requires T: Send + Sync

(remember that Rc<T> and Arc<T> do not allow &mut access to T itself)

Send/Sync demo: Box/Rc/Arc

fn is_sync<T:Sync>(t: T) {} // Felix: too lazy to construct
fn is_send<T:Send>(t: T) {} //   appropriate channels

#[test]
fn demo_send_sync_vals_refs_box_rc_arc() {
    use std::rc::Rc;
    use std::sync::Arc;
    is_sync(3);
    is_sync(vec![1,2,3]);
    is_send(3);
    is_send(&vec![1,2,3]);

    is_sync(&3);
    is_sync(&vec![1,2,3]);
    is_send(&3);
    is_send(&vec![1,2,3]);

    is_sync(Box::new(3));
    is_sync(Box::new(vec![1,2,3]));
    is_send(Box::new(3));
    is_send(Box::new(vec![1,2,3]));
}

Send/Sync demo: Box Rules

#[test]
fn demo_send_sync_box_rules() {
    fn take_send<T:Send+Clone>(t: T) {
        // is_sync(Box::new(t.clone())); // (STATIC ERROR)
        is_send(Box::new(t.clone()));
        // is_sync(&Box::new(t.clone())); // (STATIC ERROR)
        // is_send(&Box::new(t.clone())); // (STATIC ERROR)
    }
    fn take_sync<T:Sync+Clone>(t: T) {
        is_sync(Box::new(t.clone()));
        // is_send(Box::new(t.clone())); // (STATIC ERROR)
        is_sync(&Box::new(t.clone()));
        is_send(&Box::new(t.clone()));
    }
    fn take_send_sync<T:Send+Sync+Clone>(t: T) {
        is_sync(Box::new(t.clone()));
        is_send(Box::new(t.clone()));
        is_sync(&Box::new(t.clone()));
        is_send(&Box::new(t.clone()));
    }
}

Send/Sync demo: Rc values

#[test]
fn demo_send_sync_rc() {
    use std::rc::Rc;

    // is_sync(Rc::new(3)); // (STATIC ERROR)
    // is_sync(Rc::new(vec![1,2,3])); // (STATIC ERROR)
    // is_send(Rc::new(3)); // (STATIC ERROR)
    // is_send(Rc::new(vec![1,2,3])); // (STATIC ERROR)

    // is_sync(vec![Rc::new(1)]); // (STATIC ERROR)
    // is_send(vec![Rc::new(1)]); // (STATIC ERROR)
    // is_sync(&vec![Rc::new(1)]); // (STATIC ERROR)
    // is_send(&vec![Rc::new(1)]); // (STATIC ERROR)

    // is_sync(Box::new(Rc::new(1))); // (STATIC ERROR)
    // is_send(Box::new(Rc::new(1))); // (STATIC ERROR)
    // is_sync(&Box::new(Rc::new(1))); // (STATIC ERROR)
    // is_send(&Box::new(Rc::new(1))); // (STATIC ERROR)
}

Send/Sync demo: Arc values

#[test]
fn demo_send_sync_arc() {
    use std::sync::Arc;
    is_sync(vec![Arc::new(1)]);
    is_send(vec![Arc::new(1)]);
    is_sync(&vec![Arc::new(1)]);
    is_send(&vec![Arc::new(1)]);

    is_sync(Arc::new(3));
    is_sync(Arc::new(vec![1,2,3]));
    is_send(Arc::new(3));
    is_send(Arc::new(vec![1,2,3]));
}

Send/Sync demo: Arc rules

#[test]
fn demo_send_sync_arc_rules() {
    use std::sync::Arc;
    fn take_send<T:Send+Clone>(t: T) {
        // is_sync(Arc::new(t.clone())); // (STATIC ERROR)
        // is_send(Arc::new(t.clone())); // (STATIC ERROR)
        // is_sync(&Arc::new(t.clone())); // (STATIC ERROR)
        // is_send(&Arc::new(t.clone())); // (STATIC ERROR)
    }
    fn take_sync<T:Sync+Clone>(t: T) {
        // is_sync(Arc::new(t.clone())); // (STATIC ERROR)
        // is_send(Arc::new(t.clone())); // (STATIC ERROR)
        // is_sync(&Arc::new(t.clone())); // (STATIC ERROR)
        // is_send(&Arc::new(t.clone())); // (STATIC ERROR)
    }
    fn take_send_sync<T:Send+Sync+Clone>(t: T) {
        is_sync(Arc::new(t.clone()));
        is_send(Arc::new(t.clone()));
        is_sync(&Arc::new(t.clone()));
        is_send(&Arc::new(t.clone()));
    }
}

Send/Sync demo: Cell and RefCell values

#[test]
fn demo_send_sync_cell_refcell() {
    use std::cell::Cell;
    use std::cell::RefCell;

    // is_sync(Cell::new(3)); // (STATIC ERROR)
    // Cell::new(vec![1,2,3]);
    is_send(Cell::new(3));

    // is_sync(&Cell::new(3)); // (STATIC ERROR)
    // is_send(&Cell::new(3)); // (STATIC ERROR)

    // is_sync(RefCell::new(3)); // (STATIC ERROR)
    // is_sync(RefCell::new(vec![1,2,3])); // (STATIC ERROR)
    is_send(RefCell::new(3));
    is_send(RefCell::new(vec![1,2,3]));
}

Conclusion

Rust

  • Access to (many!) safe concurrency primitives

  • Access arbitrary native services

  • Ownership and Borrowing are deep parts of language

  • rustc catches bugs!

  • HACK WITHOUT FEAR!

Thanks everyone for listening and participating!

Thanks!