CS 242: Lab 2

This lab will introduce you to the logistics of programming in Rust. To get the starter code for this lab, go to the assignments repository and run git pull, then go into the lab2 directory.

Installation

First, you need to get Rust installed on your computer. Follow the instructions at rustup.rs to get the latest verison of the Rust compiler and its package manager, Cargo.

Then, install a Rust package for your favorite code editor: Vim, Emacs, Atom, Sublime, Visual Studio Code, IntelliJ.

You’re set up! Too easy.

Running code

Rust has no interpreter, so you’ll have to run code by compiling it and executing the resultant binary. You can do this in one of two ways. Option 1 is rustc:

$ cat test.rs
fn main() {
  println!("Hello, world!");
}
$ rustc test.rs
$ ./test
Hello, world!

Like gcc, this takes as input a Rust source file with a main function and outputs a binary that runs the main function. Your other option is Cargo:

$ cargo new foobar
     Created binary (application) `foobar` project
$ cd foobar
$ cargo run
   Compiling foobar v0.1.0 (file:///Users/will/Code/cs242-f18/site/labs/foobar)
    Finished dev [unoptimized + debuginfo] target(s) in 1.18s
     Running `target/debug/foobar`
Hello, world!

Cargo allows you to define “crates” (Rust projects) that have dependencies on other Rust code. In the example project, we now have a file foobar/Cargo.toml containing:

[package]
name = "foobar"
version = "0.1.0"
authors = ["Will Crichton <wcrichto@cs.stanford.edu>"]

[dependencies]

See crates.io for a full list of the publicly available Rust crates. Let’s say we want to get a random number using the rand crate. We can add rand = "0.5" under [dependencies] in the manifest file, change foobar/src/main.rs to:

extern crate rand;
use rand::prelude::*;

fn main() {
    println!("Random: {}", random::<u8>());
}

Then run:

$ cargo run
    Updating registry `https://github.com/rust-lang/crates.io-index`
 Downloading rand_core v0.2.2
 Downloading rand_core v0.3.0
   Compiling rand_core v0.3.0
   Compiling libc v0.2.43
   Compiling rand_core v0.2.2
   Compiling rand v0.5.5
   Compiling foobar v0.1.0 (file:///Users/will/Code/cs242-f18/site/labs/foobar)
    Finished dev [unoptimized + debuginfo] target(s) in 0.40s
     Running `target/debug/foobar`
Random: 213

Basics

fn main() {
  // Variable binding.
  let n: i32 = 1;

  // Binding with type inference.
  let n = 1;

  // Variable shadowing (a la OCaml).
  let n = n + 1;

  // Mutable values.
  let mut n = 0;
  n = n + 1;

  // String literals are immutable pointers.
  let s: &str = "Hello world";

  // String objects you can mutate.
  let mut s: String = String::from("Hello ");
  s.push_str("world!");

  // Named product type (struct) type definition.
  struct Point { x: f32, y: f32 };

  // Struct constructor.
  let p: Point = Point { x: 1.0, y: 2.0 };

  // Struct accessor.
  println!("({}, {})", p.x, p.y);

  // Polymorphic named sum type (enum) type definition.
  enum Option<T> { None, Some(T) }

  // Enum constructor.
  let opt: Option<i32> = Option::Some(1);

  // Match statements.
  println!("{}", match opt {
    Option::Some(n) => n,
    Option::None => -1
  });

  // Built-in vector type.
  let mut v: Vec<i32> = Vec::new();
  v.push(2);
  v.push(3);

  // Iterators.
  for i in v.iter() {
    println!("{}", i);
  }

  // Infinite loops (while true).
  let mut i = 0;
  loop {
    i += 1;
    if i == 10 { break; }
  }

  // While loops.
  while i < 20 {
    i += 1;
  }
}

// Functions.
fn fib(n: i32) -> i32 {
  if n <= 1 { n } else { fib(n-1) + fib(n-2) }
}

Exercises, part 1

All exercises below are in src/part1.rs. Before you start, uncomment the line mod part1 in src/main.rs. You can run tests for the part by running cargo test.

Implement a password checker, innovating on your design from last lab by printing out the number of guesses at each step until the password is guessed. For example, if the program is:
```
fn main() { part1::password_checker(String::from("Password1")); }
```
Then the desired interaction is:
```
$ cargo test password_checker
Foobar
Guesses: 1
Password
Guesses: 2
Password1
You guessed it!
```
Implement two function that add a constant to each element of a vector. First, add_n returns a new vector, and second, add_n_inplace modifies the input in-place, returning nothing.

You can either use for loops or the iterator API.

Implement a function that reverses a vector in-place. For example, here’s a way to do it if you can clone elements:

fn reverse_clone<T: Clone>(v: &mut Vec<T>) {
    let n = v.len();
    for i in 0..n/2 {
        let x: T = v[i].clone();
        v[i] = v[n-i-1].clone();
        v[n-i-1] = x;
    }
}

Instead, implement it in-place (without clones) using unsafe code with std::ptr::swap.

Ownership

fn main() {
  // Immutable and mutable references (or borrows).
  let mut n: i32 = 1;
  {
    let nptr: &i32 = &n;
    // n = 2; <- invalid!
  }
  n = 2; // ok!
  {
    let nptr: &mut i32 = &mut n;
    *nptr = 3;
    // n = 2; <- still invalid!
  }

  // Ownership.
  let mut s: String = String::from("Hello");
  s.push_str(" world!"); // Owner can mutate its value
  let s2 = s; // Pass off ownership
  // println!("{}", s); <- invalid! s has moved
  println!("{}", s2);

  let s4 = {
    let s3 = s2 + " Nice to see you again!";
    s3 // Pass ownership by returning from a scope
  };
  // Note that s, s2, s3 are all moved or inaccessible at this point.
  // Only s4 is live.

  let s5 = s4.clone(); // Deep copy
  println!("{}, {}", s4, s5); // No problem.

  // More complex examples of borrow checking with data structures.


  let mut v: Vec<i32> = vec![1, 2, 3];
  let n: &i32 = &v[1]; // A pointer to an element of a vec is like an iterator
  // v.push(5); <- invalid! cannot mutate v while any element is borrowed

  // Independent borrows on struct fields.
  struct Point { x: f32, y : f32 }
  let mut p = Point { x: 0.0, y: 0.0 };
  {
    let n: &f32 = &p.x;
    // This is actually ok! Can borrow x and y separately, as changing one
    // will never affect the other.
    let m: &mut f32 = &mut p.y;
    *m = 1.1;
  }

  // Different kinds of borrows in implementation.
  impl Point {
    // &self means p.print() immutably borrows p.
    fn print(&self) {
      println!("({}, {})", self.x, self.y);
    }

    // &mut self means p.incr_x() mutably borrows p.
    fn incr_x(&mut self) {
      self.x += 1.0;
    }

    // self means p.consume() moves p.
    fn consume(self) {}
  }

  p.print();
  p.incr_x();
  p.consume();
  // p.print(); <- invalid! p has moved

  // Borrowing inner fields of enums.
  enum List<T> { Nil, Cons(T, Box<List<T>>) }
  let mut l: List<i32> = List::Cons(3, Box::new(List::Nil));
  match &l {
    List::Cons(n, _) => {
      // *n = 3; <- invalid! cannot assign to immutable borrowed content
      println!("{}", *n);
    }
    List::Nil => {}
  }
}

Exercises, part 2

Do these three short exercises from the rustlings list: one, two, three.
Uncomment the mod part2 in src/main.rs. Then in src/part2.rs, your task is to fill out a simple Event interface with two functions: has_conflict that should take another event and returns if they occur on the same date, and update_event that takes an event and shifts up over by one day. See test_event for sample usage. You need to both fill out the argument/return types for these functions as well as the implementation.
For your last and largest challenge, you will implement a trie. As a refresher, see the helpful diagram on Wikipedia. Tries are a tree-based index over a set of strings, where each node is a single character. In Rust, this is represented as a recursive struct:
```
struct Trie {
  chr: char,
  has: bool,
  children: Vec<Trie>,
}
```
For example, the strings “a”, “cc”, and “ab” would become (roughly):
```
{'\0', false, [
  {'a', true, [{'b', true, []}]},
  {'c', false, [{'c', true, []}]}
]}
```
Your task is to implement a build and contains function that construct and search the trie, respectively. Make sure you do this without ever cloning a string!

Lab 2 - Rust