I’ve had a couple of projects recently where I needed to work with a list that involved images. For example, choosing a series of photos to print, or making an inventory of Lego parts. I could write a simple text list, but it’s really helpful to be able to see the images as part of the list, especially when I’m working with other people. The best tool I’ve found is Google Sheets – not something I usually associate with pictures! I’m using Google Sheets, and I use the IMAGE function, which inserts an image into a cell. For example: =IMAGE("https://www.google.com/images/srpr/logo3w.png") There’s a similar function in Microsoft Excel, but not in Apple Numbers. This function can reference values in other cells, so I’ll often prepare my spreadsheet in another tool – say, a Python script – and include an image URL in one of the columns. When I import the spreadsheet into Google Sheets, I use IMAGE() to reference that column, and then I see inline images. After that, I tend to hide the column with the image URL, and resize the rows/columns containing images to make them bigger and easier to look at. I often pair this with the HYPERLINK function, which can add a clickable link to a cell. This is useful to link to the source of the image, or to more detail I can’t fit in the spredsheet. I don’t know how far this approach can scale – I’ve never tried more than a thousand or so images in a single spreadsheet – but it’s pretty cool that it works at all! Using a spreadsheet gives me a simple, lightweight interface that most people are already familiar with. It doesn’t take much work on my part, and I get useful features like sorting and filtering for “free”. Previously I’d only thought of spreadsheets as a tool for textual data, and being able to include images has made them even more powerful. [If the formatting of this post looks odd in your feed reader, visit the original article]

I’ve posted another command-line tool on GitHub: randline, which gives you a random selection of lines in a file: $ randline < /usr/share/dict/words ultraluxurious $ randline 3 < /usr/share/dict/words unexceptionably baselessness salinity There are lots of tools that solve this problem; I wrote my own as a way to get some more Rust practice and try a new-to-me technique called reservoir sampling. Existing approaches There’s a shuf command in coreutils which is designed to do this exact thing: $ shuf -n 3 /usr/share/dict/words brimstone melody's reimbursed But I don’t have coreutils on my Mac, so I can’t use shuf. You can do this in lots of other ways using tools like awk, sort and perl. If you’re interested, check out these Stack Overflow and Unix & Linux Stack Exchange threads for examples. For my needs, I wrote a tiny Python script called randline which I saved in my PATH years ago, and I haven’t thought much about since: import random import sys if __name__ == "__main__": lines = sys.stdin.read().splitlines() try: k = int(sys.argv[1]) except IndexError: k = 1 random.shuffle(lines) print("\n".join(lines[:k])) (I’m not sure why my past self decided not to use random.sample. I suspect I’d forgotten about it.) This script has worked fine, but I stumbled across it recently and it got me thinking. This approach isn’t very efficient – it has to load the whole file into memory. Can we do better? Reservoir sampling In other Python scripts, I process files as a stream – look at one line at a time, rather than loading the whole file at once. This doesn’t make much difference for small files, but it pays off when you have really big files. I couldn’t think of a good way to take a random sample of a file using streaming, and still get a uniform distribution – but smart people have already thought about this. I did some reading and I found a technique called reservoir sampling. The introduction in the Wikipedia article makes it clear this is exactly what I want: Reservoir sampling is a family of randomized algorithms for choosing a simple random sample, without replacement, of k items from a population of unknown size n in a single pass over the items. The size of the population n is not known to the algorithm and is typically too large for all n items to fit into main memory. The population is revealed to the algorithm over time, and the algorithm cannot look back at previous items. The basic idea is that rather than holding the whole file in memory at once, I can keep a fixed-sized buffer – or “reservoir” – of the items I’ve selected. As I go line-by-line through the file, I can add or remove items in this resevoir, and it will always use about the same amount of memory. I’m only holding a line in memory if it’s in the reservoir, not every line in the file. Algorithm L The Wikipedia article describes several algorithms, including a simple Algorithm R and an optimal Algorithm L. The underlying principle of Algorithm L is pretty concise: If we generate $n$ random numbers $u_1, \ldots, u_n \sim U[0,1]$ independently, then the indices of the smallest $k$ of them is a uniform sample of the $k$-subsets of $\{1, \ldots, n\}$. There’s no proof in the Wikipedia article, but I wanted to satisfy myself that this is true. If you’re happy to take it as given, you can skip the maths and go to the next section. Here’s my attempt at a justification: What we really care about is the relative ranking of the $u_1, \ldots, u_n$, not their actual values – we care whether, for example, $u_1 < u_2$, but not the exact difference between them. Because the variables are independent and they have the same distribution, every possible ranking is equally likely. Every variable is the same, so none of them can be “special” or favoured above the others. This means that each permutation of the indices $\{1, \ldots, n\}$ is equally likely. There are $n!$ such permutations, so each occurs with probability $1/n!$. For a given $k$-subset, we’re interested in permuations where this subset is the first $k$ items. This means the probability that a particular $k$-subset will be selected is a simple fraction: $$ \begin{equation*} \text{probability of selecting this }k\text{-subset} = \frac{\text{# of permutations where this subset is the first }k\text{ items}} {\text{# of permutations}} \end{equation*} $$ How many permutations are there where this $k$-subset is the first $k$ items? There are $k!$ ways to arrange this $k$-subset as the first $k$ digits, and $(n-k)!$ ways to arrange the remaining digits. This means there are $k!\left(n-k\right)!$ permutations that match, and so: $$ \begin{equation*} \text{probability of selecting this }k\text{-subset} = \frac{k!\left(n-k\right)!}{n!} \end{equation*} $$ This probability is the same for every $k$-subset, so each one is equally likely – which is the thing we care about. This was enough to give me the confidence to try implementing Algorithm L. Implementing Algorithm L in an efficient way If we don’t know $n$ upfront, we could save all the items and only then generate the random variables $u_1, \ldots, u_n \sim U[0,1]$ – but that’s precisely the sort of inefficiency I’m trying to avoid! Fortunately, we don’t need to: the nice thing about this algorithm is that we only need to track the $k$ smallest values of $u_1, \ldots, u_i$ we’ve seen so far. Once a value is larger than the $k$ smallest, we can safely discard it because we know it’ll never be used. Here’s the approach I took: Create an empty “reservoir” of $k$ items. As you get items, assign each one a “weight” and start filling the reservoir. (These weights are the random variables $u_1, \ldots, u_n$.) If you run out of items before you fill the reservoir, go to step 4. If you fill the reservoir and there are more items, calculate the largest weight of the items in the reservoir, and go to step 3. Once the reservoir is full, go through the remaining items one-by-one. For each item, assign it a weight. If the weight of this new item is larger than the largest weight already in the reservoir, discard the item. This weight isn’t in the $k$ smallest, so we don’t care about it. If the weight of this new item is smaller than the largest weight in the resevoir, then add the item to the reservoir and remove the item with the previously-largest weight. Recalculate the largest weight of the items in the reservoir. When you run out of items, go to step 4. Return the items in the reservoir. This is your random sample. This approach means we only have to hold a fixed number of items/weights in memory at a time – much more efficient, and it should scale to an arbitrarily large number of inputs. It’s a bit too much code to include here, but you can read my Rust implementation on GitHub. I wrote some tests, which include a statistical test – I run the sampling code 10,000 times, and check the results are the uniform distribution I want. What did I learn about Rust? This is only about 250 lines of Rust, but it was still good practice, and I learnt a few new things. Working with generics I’ve used generics in other languages, and I’d read about them in the Rust Book, but I’d never written my own code using generics in Rust. I used a generic to write my sampling function: fn reservoir_sample<T>( mut items: impl Iterator<Item = T>, k: usize) -> Vec<T> { … } It was straightforward, and there were no big surprises. The difference between .iter() and .into_iter() I’ve used both of these methods before, but I only understood part of the difference. When you call .iter(), you’re borrowing the vector, which means it can be used later. When you call .into_iter(), you’re consuming the vector, which means it can’t be used later. I hadn’t thought about how this affects the types. When you call .iter(), you get an iterator of references. When you call .into_iter(), you get an iterator of values. This caused me some confusion when I was writing a test. Consider the following code: fn reservoir_sample<T>( mut items: impl Iterator<Item = T>, k: usize) -> Vec<T> { … } let letters = vec!["A", "A", "A"]; let items = letters.iter(); assert_eq!(reservoir_sample(items, 1), vec!["A"]); I was trying to write a test that reservoir_sample would only return the number of items I asked for, and no more. This was my first attempt, and it doesn’t compile. When I call letters.iter(), I’m getting an iterator of string references, that is Iterator<&&str>. Then I’m comparing it to a Vec<&str>, but Rust doesn’t know how to check equality of &str and &&str, so it refuses to compile this code. There are two ways I could fix this: Use .into_iter(), so I get an iterator of string values, i.e. Iterator<&str>. let letters = vec!["A", "A", "A"]; let items = letters.into_iter(); assert_eq!(reservoir_sample(items, 1), vec!["A"]); Change the expected result so it’s a Vec<&&str>: let letters = vec!["A", "A", "A"]; let items = letters.iter(); assert_eq!(reservoir_sample(items, 1), vec![&"A"]); I used .into_iter() in my tests. This sort of distinction is probably obvious to more experienced Rust programmers, but it was new to me. I’ve read about these methods, but I only understand them by writing code. Arrays are indexed with usize I wasn’t sure what type I should use for k, the size of the random sample. It’s a positive integer, but should I use u32 or usize? I read the descriptions of both, and it wasn’t immediately obvious which was preferable. I looked to Vec::with_capacity for inspiration, because it’s one of the methods I was using and it feels similar. It takes a single argument capacity: usize. That gave me an example to follow, but I still wanted to understand why. I did some more reading, and I learned that Rust arrays are indexed with usize. It makes sense that a pointer type is used for array indexing, but it’s been a while since I used a language with pointers, and so it didn’t occur to me. There’s a lot of cool stuff in std::collections At the core of this tool, I have a reservoir of weighted items, and I want to be able to find the item with the largest weight when it gets replaced. This sounds like priority queue, and there’s an implementation of one in the Rust standard library. I was able to use BinaryHeap from the std::collections module, which saved me from writing a bunch of fiddly code myself. Here’s the broad shape of it: struct WeightedItem<T> { item: T, weight: f64, } let mut reservoir: BinaryHeap<WeightedItem<T>> = BinaryHeap::with_capacity(k); There’s a bit more code to implement Eq and Ord for WeightedItem, but that wasn’t difficult. I didn’t even need to read the documentation – the compiler error messages were so helpful, I could just follow their suggestions to get a working solution. In this sense, Rust feels very like Python – both languages have a built-in collections module with some common data structures. I need to spend more time exploring the Rust variant, and there’s a When should you use which collection? guide to help me find the useful parts. This whole project is less than 250 lines of Rust, including tests. There are plenty of other tools that do the same thing, so I doubt anybody else will want to use it. Most people should use shuf – to which Assaf Gordon added reservoir sampling nearly twelve years ago. But in case anybody is interested, I’ve put all the code on GitHub. I’ve learnt every programming language in tiny steps – a little at a time, growing slowly until I have something approximating skill. This project is the latest tiny step towards learning Rust, and now I know a little bit more than I did before. It’s over eight years since I wrote my first Rust, and I’m still a beginner, but I’m having fun learning, and I’m having fun writing it down as I go. [If the formatting of this post looks odd in your feed reader, visit the original article]

Rust has become my go-to language for my personal toolbox – small, standalone utilities like create_thumbnail, emptydir, and dominant_colours. There’s no place for Rust in my day job, so having some self-contained hobby projects means I can still have fun playing with it. I’ve been using the assert_cmd crate to test my command line tools, but I wanted to review my testing approach before I write my next utility. My old code was fine and it worked, but that’s about all you could say about it – it wasn’t clean or idiomatic Rust, and it wasn’t especially readable. My big mistake was trying to write Rust like Python. I’d written wrapper functions that would call assert_cmd and return values, then I wrote my own assertions a bit like I’d write a Python test. I missed out on the nice assertion helpers in the crate. I’d skimmed just enough of the assert_cmd documentation to get something working, but I hadn’t read it properly. As I was writing this blog post, I went back and read the documentation in more detail, to understand the right way to use the crate. Here are some examples of how I’m using it in my refreshed test suites: Testing a basic command This test calls dominant_colours with a single argument, then checks it succeeds and that a single line is printed to stdout: use assert_cmd::Command; /// If every pixel in an image is the same colour, then the image /// has a single dominant colour. #[test] fn it_prints_the_colour() { Command::cargo_bin("dominant_colours") .unwrap() .arg("./src/tests/red.png") .assert() .success() .stdout("#fe0000\n") .stderr(""); } If I have more than one argument or flag, I can replace .arg with .args to pass a list: use assert_cmd::Command; /// It picks the best colour from an image to go with a background -- /// the colour with sufficient contrast and the most saturation. #[test] fn it_chooses_the_right_colour_for_a_light_background() { Command::cargo_bin("dominant_colours") .unwrap() .args(&[ "src/tests/stripes.png", "--max-colours=5", "--best-against-bg=#fff", ]) .assert() .success() .stdout("#693900\n") .stderr(""); } Alternatively, I can omit .arg and .args if I don’t need to pass any arguments. Testing error cases Most of my tests are around error handling – call the tool with bad input, and check it returns a useful error message. I can check that the command failed, the exit code, and the error message printed to stderr: use assert_cmd::Command; /// Getting the dominant colour of a file that doesn't exist is an error. #[test] fn it_fails_if_you_pass_an_nonexistent_file() { Command::cargo_bin("dominant_colours") .unwrap() .arg("doesnotexist.jpg") .assert() .failure() .code(1) .stdout("") .stderr("No such file or directory (os error 2)\n"); } Comparing output to a regular expression All the examples so far are doing an exact match for the stdout/stderr, but sometimes I need something more flexible. Maybe I only know what part of the output will look like, or I only care about checking how it starts. If so, I can use the predicate::str::is_match predicate from the predicates crate and define a regular expression I want to match against. Here’s an example where I’m checking the output contains a version number, but not what the version number is: use assert_cmd::Command; use predicates::prelude::*; /// If I run `dominant_colours --version`, it prints the version number. #[test] fn it_prints_the_version() { // Match strings like `dominant_colours 1.2.3` let is_version_string = predicate::str::is_match(r"^dominant_colours [0-9]+\.[0-9]+\.[0-9]+\n$").unwrap(); Command::cargo_bin("dominant_colours") .unwrap() .arg("--version") .assert() .success() .stdout(is_version_string) .stderr(""); } Creating focused helper functions I have a couple of helper functions for specific test scenarios. I try to group these by common purpose – they should be testing similar behaviour. I’m trying to avoid creating helpers for the sake of reducing repetitive code. For example, I have a helper function that passes a single invalid file to dominant_colours and checks the error message is what I expect: use assert_cmd::Command; use predicates::prelude::*; /// Getting the dominant colour of a file that doesn't exist is an error. #[test] fn it_fails_if_you_pass_an_nonexistent_file() { assert_file_fails_with_error( "./doesnotexist.jpg", "No such file or directory (os error 2)\n", ); } /// Try to get the dominant colours for a file, and check it fails /// with the given error message. fn assert_file_fails_with_error( path: &str, expected_stderr: &str, ) -> assert_cmd::assert::Assert { Command::cargo_bin("dominant_colours") .unwrap() .arg(path) .assert() .failure() .code(1) .stdout("") .stderr(predicate::eq(expected_stderr)) } Initially I wrote this helper just calling .stderr(expected_stderr) to do an exact match, like in previous tests, but I got an error “expected_stderr escapes the function body here”. I’m not sure what that means – it’s something to do with borrowing – but wrapping it in a predicate seems to fix the error, so I’m happy. My test suite is a safety net, not a playground Writing this blog post has helped me refactor my tests into something that’s actually good. I’m sure there’s still room for improvement, but this is the first iteration that I feel happy with. It’s no coincidence that it looks very similar to other test suites using assert_cmd. My earlier approaches were far too clever. I was over-abstracting to hide a few lines of boilerplate, which made the tests harder to follow. I even wrote a macro with a variadic interface because of a minor annoyance, which is stretching the limits of my Rust knowledge. It was fun to write, but it would have been a pain to debug or edit later. It’s okay to have a bit of repetition in a test suite, if it makes them easier to read. I keep having to remind myself of this – I’m often tempted to create helper functions whose sole purpose is to remove boilerplate, or create some clever parametrisation which only made sense as I’m writing it. I need to resist the urge to compress my test code. My new tests are more simple and more readable. There’s a time and a place for clever code, but my test suite isn’t it. [If the formatting of this post looks odd in your feed reader, visit the original article]

I use 1Password to store the passwords for my online accounts, and I’ve been reviewing it as a new year cleanup task. I’ve been deleting unused accounts, changing old passwords which were weak, and making sure I’ve enabled multi-factor authentication for key accounts. Each 1Password item has a notes field, and I use it to record extra information about each account. I’ve never seen anybody else talk about these notes, or how they use them, but I find it invaluable, so I thought it’d be worth explaining what I do. (This is different from the Secure Notes feature – I’m talking about the notes attached to other 1Password items, not standalone notes.) Lots of password managers have a notes field, so you can keep notes even if you don’t use 1Password. I use the notes field as a mini-changelog, where I write dated entries to track the history of each account. Here’s some of the stuff I write down: Why did I create this account? If the purpose of an account isn’t obvious, I write a note that explains why I created it. This happens more often than you might think. For example, there are lots of ticketing websites that don’t allow a guest checkout – you have to make an account. If I’m only booking a single event, I’ll save the account in 1Password, and without a note it would be easy to forget why the account exists. Why did I make significant changes? I write down the date and details of anything important I change in an account, like: Updating the email address Changing the password Adding or removing authentication methods like passkeys Enabling multi-factor authentication If it’s useful, I include an explanation of why I made a change, not just what it was. For example, when I change a password: was it because the old password was weak, because the site forced a reset, or because I thought a password might be compromised? Somebody recently tried to hack into my broadband account, so I reset the password as a precaution. I wrote a note about it, so if I see signs of another hacking attempt, I’ll remember what happened the first time. Why is it set up in an unusual way? There are a small number of accounts that I set up in a different way to the rest of my accounts. I write down the reason, so my future self knows why and doesn’t try to “fix” the account later. For example, most of my accounts are linked to my @alexwlchan.net email address – but a small number of them are tied to other email addresses. When I do this, I wrote a note explaining why I deliberately linked that account to another email. The most common reason I do this is because the account is particularly important, and if I lost access to my @alexwlchan.net email, I wouldn’t want to lose access to that account at the same time. What are the password rules? I write down any frustrating password rules I discover. This is particularly valuable if those rules aren’t explicitly documented, and you can only discover them by trial and error. I include a date with each of these rules, in case they change later. These notes reduce confusion and annoyance if I ever have to change the password. It also means that when I’m reviewing my passwords later, I know that there’s a reason I picked a fairly weak password – I’d done the best I could given the site’s requirements. Here’s a real example: “the password reset UI won’t tell you this, but passwords longer than 16 characters are silently truncated, and must be alphanumeric only”. Do I have multi-factor authentication? I enable multi-factor authentication (MFA) for important accounts, but I don’t put the MFA codes in 1Password. Keeping the password and MFA code in the same app is collapsing multiple authentication factors back into one. If I do enable MFA, I write a note in 1Password that says when I enabled it, where to find my MFA codes, and where to find my account recovery codes. For example, when I used hardware security keys at work, I wrote notes about where the keys were stored (“in the fire safe, ask Jane Smith in IT to unlock”) and how to identify different keys (“pink ribbon = workflow account”). These details weren’t sensitive security information, but they were easy to forget. Sometimes I choose not to enable MFA even though it’s available, and I write a note about that as well. For example, Wikipedia supports MFA but it’s described as “experimental and optional”, so I’ve decided not to enable it on my account yet. Why doesn’t this account exist any more? When I deactivate an account, I don’t delete it from 1Password. Instead, I write a final note explaining why and how I deactivated it, and then I move it to the Archive. I prefer this to deleting the entry – it means I still have some record that the account existed, and I can see how long it existed for. I’ve only had to retrieve something from the archive a handful of times, but I was glad I could do so, and I don’t see any downside to having a large archive. I also use the archive for accounts that I can’t delete, but are probably gone. For example, I have old accounts with utility companies that have been acquired or gone bust, and their website no longer exists. My account is probably gone, but I have no way of verifying that. Moving it to the archive gets it out of the way, and I still have the password if it ever comes back. What am I going to forget? I’m not trying to create a comprehensive audit trail of my online accounts – I’m just writing down stuff I think will be helpful later, and which I know I’m likely to forget. It only takes a few seconds to write each note. Writing notes is always a tricky balance. You want to capture the useful information, but you don’t want the note-taking to become a chore, or for the finished notes to be overwhelming. I’ve only been writing notes in my password manager for a few years, so I might not have the right balance yet – but I’m almost certainly better off than I was before, when I wasn’t writing any. I’m really glad I started keeping notes in my password manager, and if you’ve never done it, I’d encourage you to try it. [If the formatting of this post looks odd in your feed reader, visit the original article]