Initial implementation

In which we see the first few requests!

Don’t be scared by the length of the scroll bar, there are a lot of code blocks.

Back-end

We’ll begin by writing the back-end, since that’s intended to be reusable. We’ll also make a simplistic (placeholder) front-end to check that it works correctly.

First, let’s design the common interface to all caches. We’ll need to create a cache from nothing, that’s a given.

trait Cache {
	fn new() -> Self;
}

We’ll also need at least to obtain fib(n); but, which types should we use? Either we enforce them in the interface, or we make them generic. This is a library, so genericity makes the interface more flexible, which is good. Plus, generic types in Rust don’t cost much.

We also know we’ll need functionality for the other route, so let’s specify reverse as well.

pub trait Cache<K, V> { // Key, Value
	fn new() -> Self;

	fn fib(&mut self, n: K) -> V;
	fn reverse(&mut self, v: V) -> K;
}

Excellent! We can now implement our first Cache. It will cache every number computed, so we’ll use a Vec. Again, we’ll keep the types generic as much as possible.

#[derive(Debug)]
pub struct SimpleCache<V>(Vec<V>);

impl<K, V> Cache<K, V> for SimpleCache<V> {
	fn new() -> Self {
		Self(Vec::new())
	}

	fn fib(&mut self, n: K) -> V {
		todo!()
	}

	fn reverse(&mut self, v: V) -> K {
		todo!()
	}
}

Another thing that I like in Rust is built-in support for “semantic” TODO… Executing one of these todo!()s would cause the program to panic with a “not yet implemented” message.

Let’s init the Vec with the base cases…

fn new() -> Self {
	let mut cache = Vec::new();
	cache.push(0); // fib(0)
	cache.push(1); // fib(1)
	Self(cache)
}

… and compile.

(On that note, rustc error messages tend to be really friendly.)

The problem is essentially that 0 and 1 may not be valid for V… I don’t know how to specify that, so I’ll have to force the stored type. I could keep SimpleCache generic, but I currently don’t see the point.

Since Fibonacci numbers grow fast (quadratically, according to Binet’s formula), I’ll pick the largest type Rust provides, u64. Due to other errors that I’m skipping for brevity, I will also need to constrain the key type to usize.

pub struct SimpleCache(Vec<u64>);

impl Cache<usize, u64> for SimpleCache {
	// ...
}

As for fib, for now, only try to return the base cases.

fn fib(&mut self, n: K) -> u64 {
	self.0[n]
}

Now, let’s write a placeholder front-end, to see our back-working running for a spin.

use fibrs_lib::caches::SimpleCache;
use fibrs_lib::Cache;

fn main() {
    let mut cache = SimpleCache::new();
    println!("{}", cache.fib(0));
    println!("{}", cache.fib(1));
    println!("{}", cache.fib(2));
}

cargo run nets us this:

Great! We got the base cases covered, now we need to populate the cache on demand. I could write that code in a manner closer to the mathematical expression, but I will instead tread a path without recursion. We have this invariant that all numbers in the Vec have been cached; so, either the number we’re looking for is already in the cache, or we’ll need to compute every number before it as well. Due to the way numbers are computed, we can simply grow the Vec until it’s full enough to serve the desired number.

fn fib(&mut self, n: usize) -> u64 {
    // Populate the cache with entries up to the one requested
    for i in self.0.len()..=n {
        let sum = self.0[i - 1] + self.0[i - 2];
        self.0.push(sum);
    }
    self.0[n]
}

(Side note, since self.0.len returns a usize, we need n to have that type too.)

By the way, it may seem weird to an end user that fib, essentially a getter, requires mutating the object. This may arguably be leaky, but Rust offers separate mechanisms for encapsulating such “interior mutability” (see std::cell), and we should keep our scope small. If needed, we can make more multithreading-friendly wrappers later on.

Nice! We can even run for a few more values, and check that they are correct. This might be a good time to add a test!

// Check the first few in the sequence, which should be a good indication that the algorithm is good
#[test]
fn first_13() {
    let mut cache = SimpleCache::new();
    let expected = vec![0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144];
    let first_13: Vec<_> = (0..expected.len()).map(|n| cache.fib(n)).collect();
    assert_eq!(first_13, expected);
}

If you aren’t fluent in Rust, the let first_13 line begins with the Range 0..expected.len(). Ranges are Iterators, so we can map the closure (lambda) |n| cache.fib(n) on it. Rust doesn’t allow .map(cache.fib), but given how light the closure syntax is, I’m fine with that.

Anyway, <Range as Iterator>::map also returns an Iterator; if we want to “collect” all of its values into a collection, we just… call collect. After that, we assert that both collections are equal; if they aren’t, assert_eq! will print an error messages that includes each’s debugging representation, and then panic, failing the test. Neat!

Iterator::collect is generic on the returned type, as long as it’s a collection; in this case, it’s not clear which type we want to collect to. It’s either possible to directly specify the target parameter using the “turbofish” syntax ::<>, or specify the target type and let type inference to the rest; the documentation on Iterator::collect will tell you more if you want.

As you can see from the above, I prefer the latter. Note that I don’t need to specify the type contained in the Vec, Rust is able to infer that. I prefer to avoid specifying types when I can, so that I have to change less code when making modifications, which means less inertia to change.

Note also that I made the amount of generated values depend on expected.len(), so that modifying the test would only require changing the vec![] line, and not updating a length elsewhere.

Anyway:

Oh yeah, this is running the tests for the binary crate, whereas this test was written for the library. I could cd (or better, pushd) into the library’s directory, but as a programmer, I don’t like to move, so:

\o/

Alright, we have something workable. Let’s move on to implementing an actual front-end.

Front-end

HTTP is a complex spec, so I don’t want to handle it myself. Given how much use it gets, it’s certainly a solved problem, so let’s use some libraries.

lib.rs has a section on HTTP servers, one of the first entries being actix-web. Seems to support a lot of features (transparent gzipping? Hell yeah!), handle routing (perfect for my use case), boast good performance, and appears mature. Perusing the documentation, it does seem like a good fit. Let’s jump in!

[dependencies]
actix-web = "3"

First, we’ll only implement the /status route, which will return a static 200 response with an empty body.

use actix_web::{get, web, App, HttpResponse, HttpServer, Responder};
use std::io;

#[get("/status")]
async fn status() -> impl Responder {
    HttpResponse::Ok()
}

#[actix_web::main]
async fn main() -> io::Result<()> {
    // TODO: catch panics in the lib...
    HttpServer::new(move || {
        App::new()
            .service(status)
    })
    // TODO: allow specifying a different address & port
    .bind("127.0.0.1:4000")?
    .run()
    .await
}

The program runs without errors, so let’s use good old curl to test it!

200 OK, content-length: 0, all seems right!

Let’s work on adding support for /fib, then. First, we’ll need to have some state shared across requests. To test it, let’s have /fib return, statically, fib(12), computed using a cache global to the application.

#[derive(Debug)]
struct AppState {
    cache: Mutex<SimpleCache>,
}

#[get("/fib")]
async fn get_fib(data: web::Data<AppState>) -> String {
    // TODO: do not unwrap directly
    let mut cache = data.cache.lock().unwrap();
    // TODO: u64 doesn't work, figure out why
    format!("{}", cache.fib(12))
}

#[actix_web::main]
async fn main() -> io::Result<()> {
    // Data shared by all applications
    let data = web::Data::new(AppState {
        cache: Mutex::new(SimpleCache::new())
    });

    // TODO: catch panics in the lib...
    HttpServer::new(move || {
        App::new()
            .app_data(data.clone())
            .service(status)
            .service(get_fib)
    })
    .bind("127.0.0.1:4000")?
    .run()
    .await
}

Let’s test it!

(The additional % at the end was added by zsh because of the lack of newline, don’t worry)

Sure, the API isn’t doing much, but we’re definitely getting somewhere.

Let’s take parameters! Since this is a GET request, we’ll want the parameter to be part of the path. Since this is a common thing to do, you bet Actix has features to facilitate this!

#[get("/fib/{n}")]
async fn get_fib(web::Path(n): web::Path<usize>, app_data: web::Data<AppState>) -> String {
    // TODO: do not unwrap directly
    let mut cache = app_data.cache.lock().unwrap();
    // TODO: u64 doesn't work, figure out why
    format!("{}", cache.fib(n))
}

Here’s the obligatory demonstration, scripted because that’s how we roll around here 😎

Great! See you in tomorrow’s part, where we will implement /rev. It will be much simpler and shorter.

By the way, since including actix, compiling fibrs, even in debug mode, is starting to take upwards of 30 seconds… oh boy.

Compiling!
Image courtesy of the one and only XKCD.