Merge Sort With Rust

Little cubes of letters to indicate alphabetical sorting with a mergesort
Quick, sort; no not with quicksort, with merge sort

Another algorithm to play with. Moving on in the Algorithms book I mentioned in the last post to section 1.4 we come across the merge sort. Another fun one to play with in Rust and to learn vectors just a little better. So let’s code up a quick merge sort with Rust!

Yes, I’m That Old

My AP computer class back around the mid 1980s was in Pascal. I later learned that Pascal was never meant to be used in production – it was a purely a teaching language – even to the extent it could be taught on paper and never even compiled. How terrible it would be not to see your first programs run!

Either way, we worked on terminals and Pascal worked out just fine for me. That language led me easily to C and, though I never used C professionally, that made for an easy transition to Perl (which I have) and to Rust! It turned out, the prior few years of AP tests had been bad enough across all the high schools, they decided to omit three sections of Pascal, unless you optionally wanted to learn them and take an extra AP test, which I did. These three subjects were: recursion (the algorithms both last time and this time use recursion), linked list (that broke my brain for a little while – I was glad later on that it happened in school because it made C so much easier to learn), and sorting (without any simple, built-ins).

Merging with Rust

I am sure I learned the simple merge sort back then, 35 years ago. Heck, that means it was only 40 years old when I learned it! The book only spends a couple of pages on it – it is just another example of a recursive algorithm. It was fun in Rust though, I learned some vector methods I wasn’t aware of like the various forms of split_at and concat. Again I made a couple of very simple tests just to help show it works.




Since it is Creative Commons, I can include the pseudo-code presented in Jeff Erickson’s Algorithm book – but go check it out via his site!

Figure 1.6, Page 27 from Algorithm by Jeff Erickson
“Merge, everybody merge!” – Bryan Regan, https://www.youtube.com/watch?v=KPrSHrIvWI4

So, here is the code I came up with:

main.rs for merge sort

use std::env;

#[test]
fn check_mergesort() {
    let letters = vec!["s", "a", "m", "p", "l", "e"];
    let shouldbe = vec!["a", "e", "l", "m", "p", "s"];
    let sorted = mergesort(letters);
    assert_eq!(sorted, shouldbe);

    let words = vec![
        "now", "is", "the", "time", "for", "all", "good", "men", "to", "come", "to", "the", "aid",
        "of", "their", "country",
    ];
    let shouldbe = vec![
        "aid", "all", "come", "country", "for", "good", "is", "men", "now", "of", "the", "the",
        "their", "time", "to", "to",
    ];
    let sorted = mergesort(words);
    assert_eq!(sorted, shouldbe);
}

/// Adapted from reading "Algorithms" by Jeff Erickson
/// freely available on http://jeffe.cs.illinois.edu/teaching/algorithms/
pub fn main() {
    let args: Vec<String> = env::args().collect();

    if args.len() < 2 {
        println!(
            "Usage: {} word word [word...] (two or more words to sort)",
            args[0]
        );
        return;
    }

    let words = args.iter().skip(1).map(AsRef::as_ref).collect();
    println!("Arrived: {:?}", words);

    let sorted = mergesort(words);
    println!("Sorted: {:?}", sorted);
}

/// Mergesort
/// Section 1.4, page 27
pub fn mergesort(words: Vec<&str>) -> Vec<&str> {
    if words.len() < 2 {
        return words;
    }

    let midpoint = (words.len() + 1) / 2;
    let (left, right) = words.split_at(midpoint);

    let left = mergesort(left.to_vec());
    let right = mergesort(right.to_vec());

    let halfsort = [left, right].concat();
    let sorted = merge(halfsort, midpoint);

    return sorted;
}

pub fn merge(words: Vec<&str>, midpoint: usize) -> Vec<&str> {
    let size = words.len();
    let mut left_index = 0;
    let mut right_index = midpoint;
    let mut sorted: Vec<&str> = Vec::new();

    for _ in 0..size {
        if right_index >= size {
            sorted.push(&words[left_index]);
            left_index += 1;
        } else if left_index >= midpoint {
            sorted.push(&words[right_index]);
            right_index += 1;
        } else if words[left_index] < words[right_index] {
            sorted.push(&words[left_index]);
            left_index += 1;
        } else {
            sorted.push(&words[right_index]);
            right_index += 1;
        }
    }
    return sorted;
}

There is not really much to say about it though – unless you have questions or suggestions. Check it out in the github repo.

Algorithmic Rust

Like the famous (aren’t they all) Far Side where the flea lands on the dead whale and yells “Dibs!” (that was a Far Side, right? I can’t find it), I dive into an Algorithms book, and try to apply Rust

handheld calculator, algorithm driven by tiny solar panels
Old school – how many of these are sold these days?

Well, I’m bored with my fake web app. Because I don’t know where to go next, because it doesn’t have a design or plan, because it is fake. I want to play (practice) writing Rust, but the weird “practice-this” sites always seem overly contrived: “replace all the capital letters in a given string with their ASCII-number”. Sigh. So, I’m trying something new – and probably will get over my head in no time. How about I dive into the world of algorithms: with Rust!

An 80’s Kid

I never had a formal computer science education – I grew up in the sweet spot of when nerdy kids just hacked on code and tried to make things work. I barely played computer games as a teenager, but it was very common for me to be up half the night typing in some code from a COMPUTE! magazine . Then, once it was finally in and working, adjusting the code to tweek how it ran. Oh wow – for instance, check out the code for RATS!. Anyway, the world is hidden with such great treasures, not all of them from the 80’s! Take, for example, a professor who, after teaching for a decade decides to revise and cleanup his lecture notes and, while doing so, turns them into a freely available book on algorithms. Sure, you can buy his book on Amazon for $30, but just visit Jeff Erickson’s site to get his 448-page PDF for free!! Little did I realize, until into the first chapter, this book/course is apparently NOT for undergraduates. Oh well, I’ll see how far I can get.

Come At Me

Anyway, as I’m reading through chapter 1 with the stress-free page turning of someone who won’t be actually tested on any of this. I come across a pseudo-code algorithm for something called “Peasant Multiplication”. But, I won’t murder the explanation here, just go download Erickson’s PDF. I will, however, show my interpretation of how to code that in Rust!




Since it is Creative Commons, I can include the pseudo-code presented in Jeff Erickson’s Algorithm book – but go check it out via his site!

Figure 0.3, Page 6 from _Algorithm_ by Jeff Erickson
How many peasants does it take to multiply? There’s a joke in there, I just know it!

So here is what I came up for the algorithm itself and wrapped it so the user can try, plus there is a simple test:

main.rs

use std::env;

#[test]
fn check_peasant_mult() {
    use rand::Rng;

    let mut rng = rand::thread_rng();
    for _ in 0..10 {
        let n1 = rng.gen_range(1, 10000);
        let n2 = rng.gen_range(1, 10000);
        assert_eq!(peasant_multiplication(n1, n2), n1 * n2);
    }
}

/// Adapted from reading "Algorithms" by Jeff Erickson
/// freely available on http://jeffe.cs.illinois.edu/teaching/algorithms/
pub fn main() {
    let args: Vec<String> = env::args().collect();

    if args.len() != 2 {
        println!("Usage: {} x y (two positive integers)", args[0]);
        return;
    }
    let x = args[1].parse::<u32>().unwrap();
    let y = args[2].parse::<u32>().unwrap();

    let answer = peasant_multiplication(x, y);
    println!("{} x {} = {}", x, y, answer);
}

/// Peasant Multiplication
/// Section 1.2, page 23
pub fn peasant_multiplication(x: u32, y: u32) -> u32 {
    if x == 0 {
        return 0;
    }
    let x_prime = x / 2;
    let y_prime = y + y;
    let mut prod = peasant_multiplication(x_prime, y_prime);
    if x % 2 > 0 {
        prod += y;
    }
    return prod;
}

I thought it would be funny for someone to notice my multiplication algorithm required a random-number-generator if they looked into my Cargo.toml file, but TIL about the [dev-dependencies] section where you can list things you only need for testing! So:

Cargo.toml

[package]
name = "peasant_mult"
version = "0.1.0"
authors = ["Jeff Culverhouse <jeff@graystorm.com>"]
edition = "2018"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]

[dev-dependencies]
rand = "0.7"

There is absolutely no reason to do multiplication this way, of course. But it let me practice my Rust WHILE learning about algorithms in computer science. It doesn’t do much, but at least it feels worthwhile and not contrived. THIS is how some people (long, long ago) did multiplication – and it was fun to reproduce it. Multiplication inside your computer’s CPU doesn’t happen the way you think either, but I don’t know anything about that so go off on a Google tangent if you like!

Anyway, this one is simple and short enough I think I’ll just leave you the exercise of getting his PDF and comparing his quick mention of Peasant Multiplication and my implementation. You probably see something to improve or ways in which I am not writing idiomatic Rust (like that for loop in the test). Feel free to suggest some changes here! Also, I put this up on github, because why not? And I have some more coming.

Giving My App Secrets to the AWS SecretsManager

Where I pull most of my secrets out of the .env file and store at AWS instead

Part of a Series: Designing a Full-Featured WebApp with Rust
Part 1: Piecing Together a Rust Web Application
Part 2: My Next Step in Rust Web Application Dev
Part 3: It’s Not a Web Application Without a Database
Part 4: Better Logging for the Web Application
Part 5: Rust Web App Session Management with AWS
Part 6: OAuth Requests, APIs, Diesel, and Sessions
Part 7: Scraping off the Dust: Redeploy of my Rust web app
Part 8: Giving My App Secrets to the AWS SecretManager

Mother telling a child a secret. Is AWS my child in this image??
Psst… want an API key?

I’m still working around my PinPointShooting app without actually making any app progress. You can go back to the start if you like or just jump in here. So far, I’ve had my app ids and secrets hidden inside a .env file, but rather than keep them so close to the code, lets move them into my Amazon Web Services (AWS) account. It will cost me an extra $2.40/month to store these 6 secrets (so far) at Amazon ($0.40/month/secret it claims), but it gets me more practice using the rusoto_core crate and its subsidiaries. So, here is how I went about giving all of my app secrets to the AWS SecretsManager.

Cargo.toml Changes

First, in Cargo.toml, I already have rusoto_core and rusoto_dynamodb for storing my session data. So I only need to add rusoto_secretsmanager:

[dependencies]
slog = "2.5.0"
slog-bunyan = "2.1.0"
base64 = "0.10.1"
rand = "0.7.0"
rand_core = "0.5.0"
rust-crypto = "0.2.36"
config = "0.9.3"
serde_json = "1.0.40"
once_cell = "0.2.2"
dotenv = "0.14.1"
rocket-slog = "0.4.0"
sha2 = "0.8.0"
rusoto_core = "0.40.0"
rusoto_dynamodb = "0.40.0"
rusoto_secretsmanager = "0.40.0"
time = "0.1.42"
google-signin = "0.3.0"

Store Those Secrets in AWS

Of course, I had to log into AWS and create these 6 new secrets. In case I need more for other applications in the future, I prefixed each of these with “PPS_”. So, I created:

Secret name
PPS_google_api_client_id
PPS_google_api_client_secret
PPS_google_maps_api_key
PPS_facebook_app_id
PPS_facebook_app_secret
PPS_database_url
List of secrets I created in my AWS account

For each, I choose the “Other type of secrets (e.g. API key)” as the type. I stored the pair as “key” and the value I wanted to protect as a secret. This becomes the very simple struct:

#[derive(Debug, Deserialize)]
struct AWSSecret {
    key: String,
}



So, instead of pulling these into my global CONFIG from the .env file, I want to pull them from AWS instead. This requires changes to the settings.rs file. First I add the requirements at the top:

use rusoto_core::Region;
use rusoto_secretsmanager::{GetSecretValueRequest, SecretsManager, SecretsManagerClient};

plus I define the AWSSecret struct I mentioned above. Now, right after I pull in all the config settings, just before I try to turn that into a Lazy::New object to initialize the CONFIG, I need to add yet another place to pull settings from. Lets loop through each of the 6 and pull them down from AWS:

Pull Into Config

 // now pull secrets from AWS
 // note, AWS secrets include PPS_ prefix for this application
 for secret in vec![
     "database_urls",
     "google_api_client_id",
     "google_api_client_secret",
     "google_maps_api_key",
     "facebook_app_id",
     "facebook_app_secret",
 ] {
     config
         .set(secret, get_secret(format!("PPS_{}", secret)).key)
         .unwrap();
 }

So, for each Config setting stored on AWS, try to get that secret, prepending a “PPS_” in front of the secret name when checking AWS. Now I just write that get_secret() function:

get_secrets stored at AWS

fn get_secret(secret: String) -> AWSSecret {
    let secrets_manager = SecretsManagerClient::new(Region::UsEast1);
    match secrets_manager
        .get_secret_value(GetSecretValueRequest {
            secret_id: secret.clone(),
            ..Default::default()
        })
        .sync()
    {
        Ok(resp) => serde_json::from_str(&resp.secret_string.unwrap()).unwrap(),
        Err(err) => panic!("Could not retrieve secret {} from AWS: {:?}", secret, err),
    }
}

I’ll probably look back on this code in 6 months or a year and cringe, but this works anyway – and dies if it fails to pull a secret, which is what I want. I guess get_secret could return Some(AWSSecret) or None… but None means something in the app will break – I might as well just panic!

Of course, my AWS credentials are still stored in the .env file. Who protects the secret the protects the secrets!? Anyway, I did update the .env.sample file to reflect the new setup:

# configure for your user and rename to .env
ROCKET_ENV=development
AWS_ACCESS_KEY_ID=your_key_here
AWS_SECRET_ACCESS_KEY=your_key_here

# store as AWS secrets: key/value
#PPS_database_url   (for example "postgres://user:password@localhost/pinpoint")
#PPS_google_api_client_id
#PPS_google_api_client_secret
#PPS_google_maps_api_key
#PPS_facebook_app_id
#PPS_facebook_app_secret

As always, see PinPointShooting.com to see just how little it does so far (if it happens to be running), or more exciting: go see the git repo itself.