DEV Community: Sean Chen

Testing Leo Programs with DokoJS

Sean Chen — Fri, 06 Jun 2025 14:11:04 +0000

Leo is a programming language designed for writing scalable, verifiable, and auditable programs for the private-by-default Aleo network: testing is a crucial component in achieving these aims. The Leo environment, however, presents some hurdles that make testing Leo code less straightforward than in more mainstream programming language environments.

Enter DokoJS, a lightweight testing framework that sands down the rough edges around writing unit tests against Leo code: it makes the testing workflow as simple as testing JavaScript. The rest of this post will walk through the process of testing a Leo program using DokoJS.

This post assumes familiarity with Leo syntax: you should ideally have perused the Leo language reference beforehand.

This post also assumes familiarity with JavaScript and common unit testing conventions and patterns.

Challenges Around Testing Leo Code

Before diving in, it’s important to understand what problems DokoJS addresses. The thing is, Leo is not a general-purpose programming language. It is not Turing-complete, and its syntax must maintain semantic equivalence with the underlying zkSNARK output of the compiler. Indeed, it is a language designed specifically for writing decentralized applications that live and run on the Aleo network. Building testing capabilities directly into the Leo language and its compiler would run counter to these purposes, i.e., we cannot write tests for Leo code in Leo itself.

DokoJS addresses this limitation by generating and exposing interfaces that allow developers to programmatically interact with Leo code using JavaScript. At that point, developers are able to write tests against Leo code just like how they would write tests against JavaScript, with all of the streamlined developer experience niceties that come with such a mature testing ecosystem. With that said, let’s take a look at DokoJS in action!

Getting Started with DokoJS

Install Prerequisites

First off, make sure that Leo is already installed on your machine. If it isn’t, refer to these instructions for installing it and its dependencies. You’ll also need npm installed for the purposes of this walkthrough; you can refer here if you need to grab it. For testing purposes, you’ll also need a local testnet setup. For this, we recommend Amareleo, which is a light, fast, and easy to use Aleo development node: refer here for installation instructions.

Install DokoJS Itself

As for DokoJS itself, you can opt to either install it via npm by running npm install -g @doko-js/cli@latest, or building it from source. Note that building from source will also require pnpm, which you can install following this guide if you need to do so.

# Clone the git repository
git clone https://github.com/venture23-aleo/doko-js

cd doko-js

# Install the dependencies
pnpm install

# Build the project
npm run build

# Install the DokoJS CLI
npm run install:cli

Initializing a New Project

We can now initialize a new project called token by running dokojs init token.

Let’s highlight a few of the directories and files contained in the project we just initialized:

contract/: This directory contains base-contract.ts, which defines a BaseContract class that exposes methods that we’ll need in order to test our Leo programs.
programs/: This directory holds the Leo programs we’ll be testing.
test/: This directory holds the JavaScript/TypeScript tests written against our Leo programs.

For this walkthrough, we’ll be testing a modified version of the Token program that can be found on the Leo playground. It will require us to get familiar with how to test both public and private transactions and operations. Navigate to the playground link, and then copy and paste the playground code into the token.leo file in the programs/ directory.

Configuring DokoJS

Before continuing on, we should familiarize ourselves with how DokoJS is configured through the aleo-config.js file at the root of the project. The default config file looks like this:

import dotenv from 'dotenv';
dotenv.config();

export default {
  accounts: [process.env.ALEO_PRIVATE_KEY],
  mode: 'execute',
  mainnet: {},
  networks: {
    testnet: {
      endpoint: 'http://localhost:3030',
      accounts: [process.env.ALEO_PRIVATE_KEY_TESTNET3,
                 process.env.ALEO_DEVNET_PRIVATE_KEY2]
      priorityFee: 0.01
    },
    mainnet: {
      endpoint: 'https://api.explorer.aleo.org/v1',
      accounts: [process.env.ALEO_PRIVATE_KEY_MAINNET],
      priorityFee: 0.001
    }
  },
  defaultNetwork: 'testnet'
};

This config sets up Aleo accounts associated with private keys exposed through a .env file that comes with your newly-initialized DokoJS project, so no need to go set up your own .env file. It sets up testnet and mainnet networks (we’ll be making exclusive use of the testnet) and also declares the testing mode to be one of two possible types: execute for if we want to generate and broadcast proofs on-chain, and evaluate for if we want to skip proof generation during testing. For this walkthrough, we won’t be changing anything in this file, and will be making use of the accounts that are already configured.

Generating Leo-to-JS Bindings

With our token.leo program located in the programs/ directory, we now need to generate the bindings that will allow us to interact with our Leo program using JavaScript code. To do that, run dokojs compile. This command creates and populates an artifacts/ directory with the generated Leo-to-JS, as well as JS-to-Leo, type conversions. Note that whenever we make changes to our Leo program over the course of testing, we’ll need to re-compile these bindings.

Walking Through Our Leo Program

Type Definitions

At this point, let’s go through our token.leo program in preparation for writing tests against it. At the top of the file we have the following:

program token.aleo {
    mapping account: address => u64;

    record token {
        owner: adddress,
        balance: u64,
    }

    ...

We start off by declaring the program ID, token.aleo, as well as defining a mapping and a record. Mappings in Leo define on-chain state in the form of key-value pairs: we’ll be using this account mapping to associate Aleo account addresses with token amounts in the form of u64s.

Next up, we have the token record, which will be used as a receipt for confirming private transactions. Each record keeps track of the token owner’s address, as well as their token balance. Because we did not declare the fields of the token record to be public, they are private by default. Think of it like this: the mapping type keeps track of all public state changes and transactions while the record type confirms all private transactions.

Minting Functions

Next up we have functions and transitions for performing public and private mint transactions:

async transition mint_pub(public receiver: address, public amount: u64) -> Future {
    return finalize_increment_account(receiver, amount);
}

async function finalize_increment_account(public addr: address, public amount: u64) {
    let addr_amount: u64 = Mapping::get_or_use(account, addr, 0u64);
    Mapping::set(account, addr, addr_amount + amount);
}

transition mint_priv(receiver: address, amount: u64) -> token {
    return token {
        owner: receiver,
        balance: amount,
    };
}

The mint_priv transition function simply returns a new token record indicating that the receiver's balance has been set to the input amount.

The mint_pub transition calls finalize_increment_account, which fetches the account mapping associated with the addr address if it already exists, or initializes it with a balance of 0 if it doesn’t. This avoids the possibility of this transaction failing due to a non-existent account. The receivers account mapping is then incremented by the specified amount.

Leo’s Async Programming Model

Let’s make note of some of the distinctive differences between how the public logic is written compared to how the private logic is written. First off, the mint_priv transition is not marked as async: due to the private nature of this transaction, it is not making any on-chain state changes, only returning an off-chain record that will not be visible on-chain. Conversely, the mint_pub transition is marked as async precisely because it calls another async function. finalize_increment_account must itself be marked as async because it is performing some on-chain state change.

Note as well that the calling async transition must explicitly return a Future: when the mint_pub transition is called, the returned Future must be awaited to be resolved, similar to how promises in JavaScript are awaited and resolved when executing asynchronous code.

But wait a minute, why do we need to define an async transition in the first place? Why don’t we just have the async function on its own, since it is what is performing the actual logic? This is because only transitions can be exported and called outside of the defining program. Leo functions cannot be exported or called externally, they exist purely for encapsulating and abstracting logic. So we’ll need this functionality to be exposed by defining it within a transition that we’ll then be able to call externally in order to test its behavior.

Rest assured, we’ll be seeing much more of this pattern later on in our program.

Transfer Functions

Now that we have the ability to publicly and privately mint tokens, let’s take a look at the logic for transferring them. transfer_pub accesses self.caller's account mapping and decrements their token balance by amount. Simultaneously, it accesses receiver's account mapping and increments their token balance by that same amount.

In a similar vein,transfer_priv produces and returns two token records, one for the sender, whose balance has been decremented by amount, and one for the receiver, whose balance has been set to that amount:

async transition transfer_pub(public receiver: address, public amount: u64) -> Future {
    return finalize_transfer_pub(self.caller, receiver, amount);
}

async function finalize_transfer_pub(public sender: address, public receiver: address, public amount: u64) {
    let sender_amount: u64 = Mapping::get_or_use(account, sender, 0u64);
    Mapping::set(account, sender, sender_amount - amount);

    let receiver_amount: u64 = Mapping::get_or_use(account, receiver, 0u64);
    Mapping::set(account, receiver, receiver_amount + amount);
}

transition transfer_priv(sender: token, receiver: address, amount: u64) -> (token, token) {
    let difference: u64 = sender.balance - amount;

    let remaining: token = token {
        owner: sender.owner,
        balance: difference,
    };

    let transferred: token = token {
        owner: receiver,
        balance: amount,
    };

    return (remaining, transferred);
}

Indeed, the transfer functions adhere to the same async pattern that we saw with the mint functions: transfer_pub is marked as async, it calls an async function finalize_transfer_pub which performs the on-chain state changes, and it returns a Future for awaiting and resolving the asynchronous execution.

transfer_priv does none of this, eschewing asynchronous behavior and instead opting to perform all of its logic off-chain in order to preserve privacy.

The observant reader will notice that we defined a separate finalize_transfer_pub function that is called by transfer_pub as opposed to having transfer_pub call our finalize_increment_account and finalize_decrement_account. This is done for a few reasons:

We cannot call both finalize_increment_account and finalize_decrement_account in transfer_pub due to the fact that async transitions can only return at most one Future; we cannot return something like (Future, Future)currently, though we would need to if we wanted to call two async functions within an async transition.

We cannot call both finalize_increment_account and finalize_decrement_account in finalize_transfer_pub either, due to the fact that Leo requires async functions to be called from async transitions. Doing it this way does result in some code duplication, but given Leo’s rules around its async programming model, this is how our code must be organized.

Public-to-Private and Private-to-Public Transfers

Lastly, we have logic for performing a public-to-private transfer, as well as the inverse, a private-to-public transfer. Let’s take a look at the former first:

async transition transfer_pub_to_priv(public sender: address, public receiver: address, public amount: u64) -> (token, Future) {
    let transferred: token = token {
        owner: receiver,
        balance: amount,
    };

    return (transferred, finalize_decrement_account(sender, amount));
}

We can see that this functionality is an amalgamation of the public and private logic and patterns we’ve been seeing thus far. A private token record is created representing the transfer from the receiver’s perspective. Additionally, the sender's account mapping is fetched and their balance is decremented by the sent amount. On-chain, we would see that the sender performed a transfer operation, along with the amount that was transferred out of their account, but we would not see anything about the receiving account on the other side.

Finally, the inverse transfer_priv_to_pub function does the opposite:

async transition transfer_priv_to_pub(sender: token, public receiver: address, public amount: u64) -> (token, Future) {
    assert_eq(self.caller, sender.owner);

    let difference: u64 = sender.balance - amount;

    let remaining: token = token {
        owner: sender.owner,
        balance: difference,
    };

    return (remaining, finalize_increment_account(receiver, amount));
}

It creates a token record for the sender, reflecting their decremented account balance. It also updates the receiver's account mapping with their incremented balance. On-chain, we’d see that the receiver received an injection of tokens, but not the source of those tokens.

Test Helpers

We’ll also need to add a transition function for testing purposes:

async transition reset_account(public addr: address) -> Future {
    return finalize_reset_account(addr);
}

async function finalize_reset_account(public addr: address) {
    Mapping::set(account, addr, 0u64);
}

At this point, this code should be pretty self-explanatory. We’ll need these functions in order to reset the state of our account mappings back to 0 after every test, so that every test run starts with a clean slate.

Our Leo program is now complete! The next step is to call dokojs compile to generate the necessary bindings and types that we’ll need in order to call our Leo functions from JavaScript.

Writing Our Tests

Phew! With all that preamble out of the way, we are now finally ready to write tests for our token program with DokoJS.

We’ll start with a blank token.test.ts file in the test/ directory.

Setting Up Dependencies, Constants, and Helpers

We’ll add the following at the top of token.test.ts:

import { ExecutionMode } from '@doko-js/core';
import { TokenContract } from '../artifacts/js/token';
import { decrypttoken } from '../artifacts/js/leo2js/token';

const TIMEOUT = 200_000;

const mode = ExecutionMode.SnarkExecute;
const contract = new TokenContract({ mode });

const [admin, recipient] = contract.getAccounts();

We define a TIMEOUT constant as an upper bound for how long our tests can run. We also instantiate a TokenContract with our choice of mode, ExecutionMode in this case, as per what we specified in our aleo-config.js file. The TokenContract exposes the transition functions defined in our Leo program (and only the transition functions), as well as many other helpful functions we’ll need throughout the course of our testing; indeed, this type is the lynchpin upon which our entire testing strategy relies on. The decrypttoken function will be used to decrypt encrypted token records, which we’ll need in order to test our private transition functions. We also initialize two accounts, admin and recipient, that are associated with two of the private keys specified in aleo-config.js: these will act as our sender and receiver accounts throughout our testing flows.

Next, we’ll define beforeAll and beforeEach functions:

beforeAll(async () => {
  const tx = await contract.deploy();
  await tx.wait();
}, TIMEOUT);

beforeEach(async () => {
  const resetAdmin = await contract.reset_account(admin);
  const resetRecipient = await contract.reset_account(recipient);

  await resetAdmin.wait();
  await resetRecipient.wait();
}, TIMEOUT);

describe('tests', () => {
    ...

If you’re familiar with JavaScript testing practices, you’ll know that beforeAll runs once before the test suite is run, so it’s the perfect place for adding any one-time initialization logic that the tests may need. Here, we’re deploying our Leo program, via contract.deploy, to our testnet that will be accessible on localhost:3030. Like other asynchronous code that we’ll be executing, contract.deploy returns a Future that we must await on for it to resolve.

We also define a beforeEach helper, which runs before every test, ensuring that our admin and recipient accounts always start with a balance of 0; this is so that we won’t have to deal with inconsistent account state due to a previous test manipulating said state.

Testing Public Minting

When it comes to testing public minting functionality, we’ll simply mint some amount to an account, and then assert that that account’s balance equals the amount we minted:

test('public mint', async () => {
  const actualAmount = BigInt(300000);

  const mintTx = await contract.mint_pub(admin, actualAmount);
  await mintTx.wait();

  const expected = await contract.account(admin);
  expect(expected).toBe(actualAmount);
}, TIMEOUT);

We initialize an actualAmount value, passing it to contract.mint_pub along with the admin account address. Our mint_pub code should then increment admin's account mapping by actualAmount. We then read the value of admin's account balance via a call to contract.account, passing in the address of the mapping we want to fetch. We then assert that the balance we got back matches the amount we minted, actualAmount.

Now that we have our first official test, let’s make sure it passes.

Running Our Tests

The first thing we’ll need to do before we can run our tests is start up our amareleo node in a separate terminal instance. Without performing this step, if you try to run the tests, you should see that you get a DokoJSError: DOKOJS105: Deployment check failed error due to localhost:3030 not actively listening for our requests. Starting the amareleo node with amareleo-chain start will alleviate this problem.

Once the amareleo node is running and localhost:3030 is listening for our requests, run the test suite with npm run test. You should see our single test asserting that our public minting functionality works as intended passes. If it doesn’t, make sure that you don’t have any typos or inconsistencies in your code before trying again.

Before re-running the test suite again, you’ll need to cancel and restart the amareleo node process as well.

Testing Private Minting

Testing our private functions requires a little bit more effort than testing our public functions. Chiefly, we can’t just inspect public state by fetching account mappings. Instead, we’ll have to decrypt token records before we can inspect and assert their state. Our private mint test looks like this:

test('private mint', async () => {
  const actualAmount = BigInt(100000);

  const tx = await contract.mint_priv(recipient, actualAmount);
  const [record1] = await tx.wait();

  const recipientKey = contract.getPrivateKey(recipient);
  const decryptedRecord = decrypttoken(record1, recipientKey);

    expect(decryptedRecord.owner).toBe(recipient);
  expect(decryptedRecord.balance).toBe(actualAmount);
}, TIMEOUT);

Our first deviation from our public mint test can be found right after calling contract.mint_priv: we're getting back an encrypted token record from this call. In order to check that this token record is as we expect, we’ll need to decrypt it by fetching the recipient account’s view key by calling contract.getPrivateKey. We then pass this view key, along with the encrypted record, to the decrypttoken function, which decrypts it, allowing us to now assert that the owner and balance are what we expect them to be.

Testing Public Transfer

Now that we’re confident our minting functionality works, we can test our transfer functionality, starting with the public version. The idea of our transfer tests is to mint some tokens to an account, and then transfer some of those tokens to another account. At that point, we’ll assert that the sender’s account balance is the amount we minted for them less the amount that they transferred, and that the receiver’s account balance is the amount that was transferred to them:

test('public transfer', async () => {
  const amount1 = BigInt(100000);
  const amount2 = BigInt(30000);

  const mintTx = await contract.mint_pub(admin, amount1);
  await mintTx.wait();

  let adminAmount = await contract.account(admin);
  expect(adminAmount).toBe(amount1);

  const transferTx = await contract.transfer_pub(recipient, amount2);
  await transferTx.wait();

  adminAmount = await contract.account(admin);
  const recipientAmount = await contract.account(recipient);

  expect(adminAmount).toBe(amount1 - amount2);
  expect(recipientAmount).toBe(amount2);
}, TIMEOUT);

Hopefully you’re starting to get the hang of the patterns and concepts that we’re seeing in the tests; there shouldn’t be anything new here that we haven’t seen already.

Testing Private Transfer

The test for our private transfer functionality follows the same general idea as our public transfer test. Again, the only additional wrinkle is working with encrypted token records that we’ll need to decrypt, just like how we did it in our private mint test:

test('private transfer', async () => {
  const adminKey = contract.getPrivateKey(admin);
  const recipientKey = contract.getPrivateKey(recipient);

  const amount1 = BigInt(1000000000);
  const amount2 = BigInt(100000000);

  const mintTx = await contract.mint_priv(admin, amount1);
  const [encryptedToken] = await mintTx.wait();

  const decryptedRecord = decrypttoken(encryptedToken, adminKey);

  const transferTx = await contract.transfer_priv(decryptedRecord, recipient, amount2);
  const [encryptedAdminRecord, encryptedRecipientRecord] = await transferTx.wait();

  const adminRecord = decrypttoken(encryptedAdminRecord, adminKey);
  const recipientRecord = decrypttoken(encryptedRecipientRecord, recipientKey);

  expect(adminRecord.owner).toBe(admin);
  expect(adminRecord.balance).toBe(amount1 - amount2);

  expect(recipientRecord.owner).toBe(recipient);
  expect(recipientRecord.balance).toBe(amount2);
}, TIMEOUT);

Note that we need to decrypt the token record that contract.mint_priv returns before we’re able to pass it as an input to transfer_priv. From there, we get back two more encrypted token records, one representing the sender’s view of the transaction, the other representing the receiver’s view of the same transaction

Testing Public-to-Private Transfer

Now that we’ve seen how to test both public and private transfers, testing public-to-private and private-to-public transfers will simply be an amalgamation of the same techniques we’ve been using:

test('public to private transfer', async () => {
  const recipientKey = contract.getPrivateKey(recipient);

  const amount1 = BigInt(500000);
  const amount2 = BigInt(100000);

  const mintTx = await contract.mint_pub(admin, amount1);
  await mintTx.wait();

  let adminAmount = await contract.account(admin);
  expect(adminAmount).toBe(amount1);

  const transferTx = await contract.transfer_pub_to_priv(admin, recipient, amount2);
  const [record] = await transferTx.wait();

  adminAmount = await contract.account(admin);

  const decryptedRecord = decrypttoken(record, recipientKey);

  expect(adminAmount).toBe(amount1 - amount2);

  expect(decryptedRecord.owner).toBe(recipient);
  expect(decryptedRecord.balance).toBe(amount2);
}, TIMEOUT);

With the public-to-private transfer, the sender’s view of the transaction is public, while the recipient’s view of it is private. So we’ll only need to get the recipient’s view key, as only their parts of the transaction will need to be decrypted.

Testing Private-to-Public Transfer

And finally, the test for the private-to-public transfer will be the inverse of the public-to-private transfer test:

test('private to public transfer', async () => {
  const adminKey = contract.getPrivateKey(admin);

  const amount1 = BigInt(600000);
  const amount2 = BigInt(500000);

  const mintTx = await contract.mint_priv(admin, amount1);
  const [encryptedToken] = await mintTx.wait();

  const decryptedToken = decrypttoken(encryptedToken, adminKey)
  expect(decryptedToken.balance).toBe(amount1);

  const transferTx = await contract.transfer_priv_to_pub(decryptedToken, recipient, amount2);
  const [record] = await transferTx.wait();

  const recipientAmount = await contract.account(recipient);
  const decryptedRecord = decrypttoken(record, adminKey);

  expect(recipientAmount).toBe(amount2);

  expect(decryptedRecord.owner).toBe(admin);
  expect(decryptedRecord.balance).toBe(amount1 - amount2);
}, TIMEOUT);

The sender’s view of the transfer is private, so we’ll need their view key to be able to decrypt their part of the transaction. The receiver’s view of the transfer is public, and so can be asserted as such.

In Summary

And there we have it! We’ve written a pretty comprehensive set of tests for our token program. If you made it this far, you should have a solid grasp of the basics when it comes to testing Leo programs with DokoJS. Even for such a simple token program as this one, there’s a lot more edge cases that we could test. For example, we could write an additional test asserting that transfer_priv_to_pub throws an error when it is called by an account other than the sender of the transaction. But we’ll leave that as an exercise for the reader!

While writing programmatic unit and integration tests using a testing framework like DokoJS is an extremely powerful technique for building confidence in our code’s correctness, it has its limitations (like being able to only directly test Leo transitions); it should not be the only testing tool in a developer’s toolbox. The Leo ecosystem makes available many other useful tools when it comes to testing, such as the Leo debugger for stepping through code execution, as well as the Aleoscan block explorer, which allows you to get a much more macro-level view of what happened when a transaction failed. It behooves any developer aiming to develop private applications atop the Aleo network to get familiar and comfortable with utilizing all of these complementary testing tools in appropriate situations.

If you’re interested in taking a look at the accompanying project code, you can find it at this GitHub repo.

To bring it all back, DokoJS, by exposing Leo programs as JavaScript-consumable types and interfaces, makes testing accessible to any developer who is familiar with JS. At the end of the day, it offers a developer-friendly testing experience for those keen on building atop the Aleo network.

A Beginner's Guide to Handling Errors in Rust

Sean Chen — Tue, 06 Apr 2021 21:15:45 +0000

The example projects in The Rust Programming Language are great for introducing new would-be Rustaceans to different aspects and features of Rust. In this post, we'll be looking at some different ways of implementing a more robust error handling infrastructure by extending the minigrep project from The Rust Programming Language.

The minigrep project is introduced in chapter 12 and walks the reader through building a simple version of the grep command line tool, which is a utility for searching through text. For example, you'd pass in a query, the text you're searching for, along with the file name where the text lives, and get back all of the lines that contain the query text.

The goal of this post is to extend the book's minigrep implementation with more robust error handling patterns so that you'll have a better idea of different ways to handle errors in a Rust project.

For reference, you can find the final code for the book's version of minigrep here.

Error handling use cases

A common pattern when it comes to structuring Rust projects is to have a "library" portion where the primary data structures, functions, and logic live and an "application" portion that ties the library functions together.

You can see this in the file structure of the original minigrep code: the application logic lives inside of the src/bin/main.rs file, and it's merely a thin wrapper around data structures and functions that are defined in the src/lib.rs file; all the main function does is call minigrep::run.

This is important to point out because depending on whether we're building an application or a library changes how we approach error handling.

When it comes to an application, the end user most likely doesn't want to know about the nitty gritty details of what caused an error. Indeed, the end user of an application probably only ought to be notified of an error in the event that the error is unrecoverable. In this case, it's also useful to provide details on why the unrecoverable error occurred, especially if it has to do with user input. If some sort of recoverable error happened in the background, the consumer of an application probably doesn't need to know about it.

Conversely, when it comes to a library, the end users are other developers who are using the library and building something on top of it. In this case, we'd like to give as many relevant details about any errors that occurred in our library as possible. The consumer of the library will then decide how they want to handle those errors.

So how do these two approaches play together when we have both a library portion and an application portion in our project? The main function executes the minigrep::run function and outputs any errors that crop up as a result. So most of our error handling efforts will be focused on the library portion.

Surfacing library errors

In src/lib.rs, we have two functions, Config::new and run, which might return errors:

impl Config {
    pub fn new(mut args: env::Args) -> Result<Config, &'static str> {
        args.next();

    let query = match args.next() {
        Some(arg) => arg,
        None => return Err("Didn't get a query string"),
    };

    let filename = match args.next() {
        Some(arg) => arg,
        None => return Err("Didn't get a file name"),
    };

    let case_sensitive = env::var("CASE_INSENSITIVE").is_err();

    Ok(Config {
        query,
        filename,
        case_sensitive,
    })
}

pub fn run(config: Config) -> Result<(), Box<dyn Error>> {
    let contents = fs::read_to_string(config.filename)?;

    let results = if config.case_sensitive {
        search(&config.query, &contents)
    } else {
        search_case_insensitive(&config.query, &contents)
    };

    for line in results {
        println!("{}", line);
    }

    Ok(())
}

There are exactly three spots where errors are being returned: two errors occur in the Config::new function, which returns a Result<Config, &'static str>. In this case, the error variant of the Result is a static string slice.

Here we return an error when a query is not provided by the user.

let query = match args.next() {
    Some(arg) => arg,
    None => return Err("Didn't get a query string"),
};

Here we return an error when a filename is not provided by the user.

let filename = match args.next() {
    Some(arg) => arg,
    None => return Err("Didn't get a file name"),
};

The main problem with structuring our errors in this way as static strings is that the error messages are not located in a central spot where we can easily refactor them should we need to. It also makes it more difficult to keep our error messages consistent between the same types of errors.

The third error occurs at the top of run function, which returns a Result<(), Box<dyn Error>>. The error variant in this case is a trait object that implements the Error trait. In other words, the error variant for this function is any instance of a type that implements the Error trait.

Here we bubble up any errors that might have occurred as a result of calling fs::read_to_string.

let contents = fs::read_to_string(config.filename)?;

This works for the errors that might crop up as a result of calling fs::read_to_string since this function is capable of returning multiple types of errors. Therefore, we need a way to generically represent those different possible error types; the commonality between them all is the fact that they all implement the Error trait!

Ultimately, what we want to do is define all of these different types of errors in a central location and have them all be variants of a single type.

Defining error variants in a central type

We'll create a new src/error.rs file and define an enum AppError, deriving the Debug trait in the process so that we can get a debug representation should we need it. We'll name each of the variants of this enum in such a way that they appropriately represent each of the three types of errors:

#[derive(Debug)]
pub enum AppError {
    MissingQuery,
    MissingFilename,
    ConfigLoad,
}

The third variant, ConfigLoad, maps to the error that might crop up when calling fs::read_to_string in the Config::run function. This might seem a bit out of place at first, since if an error occurs with that function, it would be some sort of I/O problem reading the provided config file. So why didn't we name it IOError or something like that?

In this case, since we're surfacing an error from a standard library function, it's more relevant to our application to describe how the surfaced error affects it, instead of simply reiterating it. When an error occurs with fs::read_to_string, that prevents our Config from loading, so that's why we named it ConfigLoad.

Now that we have this type, we need to update all of the spots in our code where we return errors to utilize this AppError enum.

Returning variants of our `AppError`

At the top of our src/lib.rs file, we need to declare our error module and bring error::AppError into scope:

mod error;

use error::AppError;

In our Config::new function, we need to update the spots where we were returning static string slices as errors, as well as the return type of the function itself:

- pub fn new(mut args: env::Args) -> Result<Config, &'static str>
+ pub fn new(mut args: env::Args) -> Result<Config, AppError>
    // --snip--

    let query = match args.next() {
        Some(arg) => arg,
-       None => return Err("Didn't get a query string"),
+       None => return Err(AppError::MissingQuery),
    };

    let filename = match args.next() {
        Some(arg) => arg,
-       None => return Err("Didn't get a file name"),
+       None => return Err(AppError::MissingFilename),
    };

    // --snip--

The third error in the run function only requires us to update its return type, since the ? operator is already taking care of bubbling the error up and returning it should it occur.

- pub fn run(config: Config) -> Result<(), Box<dyn Error>>
+ pub fn run(config: Config) -> Result<(), AppError>

Ok, so we're now making use of our error variants, which, should they occur, are being surfaced to our main function and printed out. But we no longer have the actual error messages that we had before defined anywhere!

Annotating error variants with `thiserror`

The thiserror crate is one that is commonly used to provide an ergonomic way to format error messages in a Rust library.

It allows us to annotate each of the variants in our AppError enum with the actual error message that we want displayed to the end user.

Let's add it as a dependency in our Cargo.toml:

[dependencies]
thiserror = "1"

In src/error.rs we'll bring the thiserror::Error trait into scope and have our AppError type derive it. We need this trait derived in order to annotate each enum variant with an #[error] block. Now we specify the error message that we want displayed for each particular variant:

+ use std::io;

+ use thiserror::Error;

- #[derive(Debug)]
+ #[derive(Debug, Error)]
pub enum AppError {
+   #[error("Didn't get a query string")]
    MissingQuery,
+   #[error("Didn't get a file name")]
    MissingFilename,
+   #[error("Could not load config")]
    ConfigLoad {
+       #[from] 
+       source: io::Error,
+   }
}

What's all the extra stuff was added to the ConfigLoad variant? Since a ConfigLoad error only occurs when there's an underlying error with the call to fs::read_to_string, what the ConfigLoad variant is actually doing is providing extra context around the underlying I/O error.

thiserror allows us to wrap a lower-level error in additional context by annotating it with a #[from] in order to convert the source into our homebrew error type. In this way, when an I/O error occurs (like when we specify a file to search through that doesn't actually exist), we get an error like this:

Could not load config: Os { code: 2, kind: NotFound, message: "No such file or directory" }

Without it, the resulting error message looks like this:

Os { code: 2, kind: NotFound, message: "No such file or directory" }

To a consumer of our library, it's harder to figure out the source of this error; the additional context helps a lot.

You can find the version of minigrep that uses thiserror here.

A more manual approach

Now we'll switch gears and look out how we might achieve the same results that thiserror provides us, but without bringing it in as a dependency.

Under the hood, thiserror performs some magic with procedural macros, which can have a noticeable effect on compilation speeds. In the case of minigrep, we have very few error variants and the project is so small that a dependency on thiserror really won't introduce much of an increase in compilation time, but it could be a consideration in a much larger and more complex project.

So on that note, we'll wrap up this post by ripping it out and replacing it with our own hand-rolled implementation. The nice thing about going down this route is that we'll only need to make changes to the src/error.rs file to implement all of the necessary changes (besides, of course, removing thiserror from our Cargo.toml).

[dependencies]
- thiserror = "1"

Let's remove all of the annotations that thiserror was providing us. We'll also replace the thiserror::Error trait with the std::error::Error trait:

- use thiserror::Error;
+ use std::error::Error;

- #[derive(Debug, Error)]
+ #[derive(Error)]
pub enum AppError {
-   #[error("Didn't get a query string")]
    MissingQuery,
-   #[error("Didn't get a file name")]
    MissingFilename,
-   #[error("Could not load config")]
    ConfigLoad {
-      #[from]
       source: io::Error,
    }
}

In order to get back all of the functionality we just wiped, we'll need to do three things:

Implement the Display trait for AppError so that our error variants can be displayed to the user.
Implement the Error trait for AppError. This trait represents the basic expectations of an error type, namely that they implement Display and Debug, plus the capability to fetch the underlying source or cause of the error.
Implement From<io::Error> for AppError. This is required so that we can convert an I/O error returned from fs::read_to_string into an instance of AppError.

Here's our implementation of the Display trait for our AppError. It maps each error variant to an string and writes it to the Display formatter.

use std::fmt;

impl fmt::Display for AppError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::MissingQuery => f.write_str("Didn't get a query string"),
            Self::MissingFilename => f.write_str("Didn't get a file name"),
            Self::ConfigLoad { source } => write!(f, "Could not load config: {}", source),
        }
    }
}

And here's our implementation of the Error trait. The main method to be implemented is the Error::source method, which is meant to provide information about the source of an error. For our AppError type, only ConfigLoad exposes any underlying source information, namely the I/O error that might happen as a result of calling fs::read_to_string. There's no underlying source information to expose in the case of the other error variants.

use std::error;

impl error::Error for AppError {
    fn source(&self) -> Option<&(dyn Error + 'static)> {
        match self {
            Self::ConfigLoad { source } => Some(source),
            _ => None,
        }
    }
}

The &(dyn Error + 'static) part of the return type is similar to the Box<dyn Error> trait object that we saw earlier. The main difference here is that the trait object is behind an immutable reference instead of a Box pointer. The 'static lifetime here means the trait object itself only contains owned values, i.e., it doesn't store any references internally. This is necessary in order to assuage the compiler that there's no chance of a dangling pointer here.

Lastly, we need a way to convert an io::Error into an AppError. We'll do this by impling From<io::error> for AppError.

impl From<io::Error> for AppError {
    fn from(source: io::Error) -> Self {
        Self::ConfigLoad { source }
    }
}

There's not much to this one. If we get an io::Error, all we do to convert it to an AppError is wrap it in a ConfigLoad variant.

And that's all folks! You can find this version of our minigrep implementation here.

Summary

In closing, we discussed how the original minigrep implementation presented in The Rust Programming Language book is a bit lacking in the error handling department, as well as how to think about different error handling use cases.

From there, we showcased how to use the thiserror crate to centralize all of the possible error variants into a single type.

Finally, we peeled back the veneer that thiserror provides and showed how to replicate the same functionality manually.

I hope you all learned something from this post! 🙂

Implementing an LRU Cache in Rust

Sean Chen — Wed, 27 Jan 2021 20:50:23 +0000

The original version of this post can be found on my developer blog at https://seanchen1991.github.io/posts/lru-cache/.

Note: This post assumes familiarity with traits in Rust. If you aren’t familiar with them, I’d recommend reading more about them. The chapter in the official Rust book is as good a place as any 🙂

LRU caches are one of my favorite data structures to teach. One way of implementing an LRU cache (in Python, the language that I teach in) requires combining two separate data structures: a hash map in order to enable efficient access via hashing of keys, and a doubly-linked list in order to maintain the ordering of cache elements.

However, structuring an LRU cache implementation in the same way in Rust would likely make it really clunky and difficult, since implementing doubly linked lists in Rust is hard. We’ll need to come up with a different strategy when we get around to implementing it Rust. But first, let’s see the Python implementation.

Note: I’m aware that Python’s dictionary implementation orders key-value pairs by insertion order, so we could just take advantage of that feature in our LRU cache implementation as a way to keep track of the order of cache entries. However, this would obviate the learning exercise. We’ll be disregarding this feature for our Python implementation.

Coming up with Requirements for our Cache

The job of a cache is to store data and/or objects such that subsequent accesses are performed more quickly than the initial access. By design, caches are meant to be kept small in order to speed up read operations. An important question then when designing a cache is “what gets kept and what gets evicted when the cache reaches capacity?”.

An LRU (or Least Recently Used) cache employs a fairly straightforward strategy: the data that was accessed the longest time ago is what is evicted from the cache. In order to do this, our LRU cache needs to keep track of the order in which elements (which take the form of key-value pairs) it holds are inserted and fetched.

Whenever an element is inserted into or fetched from the cache, that element becomes the newest element in the cache. Additionally, if the cache is already at max capacity when we insert a new element, then the eviction routine needs to be executed in order to remove the oldest cache element and make room for the new cache element.

So our LRU cache will need an insert operation as well as a fetch operation. It will also need an evict operation, though we’ll opt to not expose this method as part of our cache’s public API.

Our Python Implementation

With a loose specification of the requirements of our LRU cache, we can define the constructor as such:

from doubly_linked_list import DoublyLinkedList

class LRUCache:
    def __init__(self, capacity=100):
        # the max number of entries the cache can hold
        self.capacity = capacity
        # the hash map for storing entries as key-value pairs 
        # it’s what allows us to efficiently fetch entries 
        self.storage = dict()
        # a doubly linked list for keeping track of the order
        # of elements in our cache 
        self.order = DoublyLinkedList()

Note: We won’t be going over the design and implementation of the DoublyLinkedList that we’re using here, though its code is included in the GitHub repo should you wish to take a look.

Our cache’s constructor receives a single optional parameter specifying the maximum number of entries that the cache can hold, which is stored in the self.capacity variable. The self.storage dictionary associates keys with the contents of the cache that we actually care about. self.order stores a DoublyLinkedList whose sole job is to keep track of the order of entries in the cache: the newest entry in the list will always be at the head of the list, and the oldest entry will always be at the tail.

Let’s first define our insert method. It takes a key-value pair, where the value is the actual cached content that we care about, and the key is some sort of key that allows us to access the cached content. If the key isn’t already contained in the cache, it needs to be added to the self.storage dictionary, and we’ll also add the key as a node at the head of the self.order linked list. However, if the key already exists in the cache, then we want to only overwrite its value instead of re-inserting the key into the cache with a new value.

Additionally, if it turns out the cache is already at max capacity, we’ll need to evict the oldest entry in the cache:

    def insert(self, key, value):
        # if the key is already in the cache, overwrite 
        # its value 
        if key in self.storage:
            entry = self.storage[key]
            entry.data = (key, value)
            # touch this entry to move it to the head of 
            # the linked list
            self.touch(entry)
            return

        # check if our cache is at max capacity to see
        # if we need to evict the oldest entry 
        if len(self.storage) == self.capacity:
            self.evict()

        # add the key and value as a node at the 
        # head of our doubly linked list 
        self.order.add_to_head((key, value))
        # add the linked list node as the value of 
        # the key in our storage dictionary
        self.storage[key] = self.order.head

Each linked list node is storing a tuple of the key and the value. Each key-value pair in self.storage consists of the key as its key and a linked list node as its value:

Let’s implement the touch method, which is responsible for moving an entry in our cache to the most-recently-added spot in our cache. Our doubly linked list implementation has a method move_to_front that takes a node and does the work of moving it from wherever it is in the list to the head; we’ll use it here in our touch implementation:

    def touch(self, entry):
        self.order.move_to_front(entry)

The evict method is responsible for removing the oldest entry in the cache and is called only when we attempt to insert into the cache when it is already at max capacity. It needs to remove the node at the tail of the linked list, as well as make sure the key that referred to the oldest entry is also removed from self.storage:

    def evict(self):
        # delete the key-value pair from the storage dict 
        # we can get the oldest entry’s key by accessing 
        # it from the tail of the linked list 
        key_to_delete = self.order.tail.data[0]
        del self.storage[key_to_delete]

        # remove the tail entry from our linked list 
        self.order.remove_from_tail()

Now we need to implement the fetch method which accepts a key to an entry in the cache, checks whether the key exists, then returns the value associated with the key. This method also moves the entry to the head of the linked list as this entry is now the most-recently-used entry in the cache.

    def fetch(self, key):
        if key not in self.storage:
            return 

        entry = self.storage[key]
        self.touch(entry)
        return entry.data[1]

The full code for the Python implementation, as well as a suite of tests, can be found here.

Transitioning to a Rust Implementation

Our Python implementation liberally allocates objects in memory, most notably the two distinct data structures, a dictionary and a doubly linked list (which itself allocates lots of linked list nodes), with linked list nodes referring to one another, along with the dictionary referring to these nodes as well. This is an example of what Jim Blandy and Jason Orendorff call a “sea of objects” in their book Programming Rust:

Automatic memory management makes this kind of memory architecture tenable: cyclical references are handled by the garbage collector. The tradeoff here is that programmers are able to develop working software without having to do as much up-front planning, at the cost of taking a performance hit due to the garbage collection process.

When it comes to implementing this same data structure in Rust, opting to go with the same high-level design of using a doubly linked list to keep track of the order of cache entries and then storing those linked list nodes as values in a dictionary for efficient access will lead to very messy and clunky code in the best case, and unsafe code in the worst case. Implementing a doubly linked list in Rust, at least in the “traditional” way, is, as we mentioned earlier, not straightforward.

So we’ll need to go back to the drawing board and come up with a different architecture. Of the two data structures we used in our Python implementation, the doubly linked list is certainly the more vital of the two: it maintains the order of cache entries, is cheap to insert into and remove from, and provides us direct access to the most-recently- and least-recently-used entries in the cache so long as we maintain the invariant that these entries live at the ends of the linked list.

But wait, didn’t we just mention that doubly linked lists are a pain to implement in Rust?

Well, I said that they’re a pain to implement in Rust in the “traditional” way, using nodes and references between those nodes. The reason why is due to the ownership system that dictates that every heap-allocated memory object can only have one owner at any point in time. Doubly linked lists buck this rule since each node, by design, is referred to by two nodes at once. Thus, implementing a node-based doubly linked list either requires liberal use of Rcs (which impose runtime checks) or unsafety.

But wait! There’s actually a third route we could take that circumvents these issues. We’ll implement our doubly linked list using an array 🙂

Each “node” in our array-backed doubly linked list, instead of referencing other node objects directly, will instead refer to the array indices where the node’s previous and next nodes reside in the array. This is certainly a more abstract way to implement a doubly linked list, though it gets the job done and has some important benefits for our use case, most notably that introducing an extra level of indirection by having each linked list node reference the array index of another linked list node completely circumvents the multiple owners issue that comes with the territory of doubly linked lists.

Now, since all of our cache entries are being stored in an array, it would be straightforward to layer on a HashMap as part of our implementation where we store keys that are associated with a particular cache entry’s index in the array.

However, instead of opting for this design, which would map relatively closely with the design of our Python implementation, we’re going to ditch the inclusion of a HashMap and actually just use our array-backed doubly linked list for our Rust implementation. This design decision means that we’re going to lose the ability to access arbitrary cache entries in constant time, but on the plus side, our cache will have a smaller memory footprint since we aren’t using another data structure.

Implementing the Rust Version of our Cache

Let’s start off by defining an Entry type inside the src/lib.rs file of a new Rust project. This type will represent every entry in our cache and wrap some arbitrary piece of data that we want stored in the cache. Note that this type also doubles as our linked list node type as it refers to the previous and next entries in the cache.

pub struct Entry<T> {
    /// The value stored in this entry
    val: T,
    /// Index of the previous entry in the cache
    prev: usize,
    /// Index of the next entry in the cache
    next: usize,
}

Next, our LRUCache type, which is responsible for storing an array of Entrys, as well as head and tail indices where the most-recently-used and least-recently-used Entrys are stored, respectively. The array will have a fixed size that can be specified when the LRUCache is initialized. Rust’s vanilla array type doesn’t actually satisfy this requirement (yet), so we’ll need to import a crate that provides us with this capability, namely the ArrayVec crate.

Bringing in `ArrayVec` as a Dependency

First, add it as a dependency in your project’s Cargo.toml file:

[dependencies]
arrayvec = “0.5.2”

Then in src/lib.rs:

use arrayvec::ArrayVec;

pub struct LRUCache {
    /// Our `ArrayVec` will be storing `Entry`s 
    entries: ArrayVec<Entry>,
    /// Index of the first entry in the cache
    head: usize,
    /// Index of the last entry in the cache
    tail: usize,
    /// The number of entries in the cache
    length: usize,
}

If you try compiling what we have so far with cargo build, you should get an error like this:

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> src/main.rs:11:23
   |
11 |     entries: ArrayVec<Entry>,
   |                       ^^^^^ expected 1 type argument

error: aborting due to previous error

To figure out what’s wrong here, we can look at ArrayVec’s documentation. One of the code snippets that demonstrates how to initialize a new ArrayVec instance looks like this:

use arrayvec::ArrayVec;

let mut array = ArrayVec::<[_; 16]>::new();

The <[_; 16]> in this initialization is specifying up-front that the new ArrayVec will have a capacity of 16 and hold some unknown type (denoted by the _) that the compiler should infer later. This is the piece we’re missing in our code. But the whole point of bringing in and using ArrayVec was so that we could generalize over the capacity. How do we do that?

If you search around ArrayVec’s docs, you might come across the Array trait. This is what will allow us to generalize over the capacity of a new ArrayVec instance. When we go to initialize a new LRUCache instance, we can do so with something like this:

// An `LRUCache` that holds at most 4 `Entry<i32>`s
let cache = LRUCache<[Entry<i32>; 4]>;

You can think of the Array trait as a kind of placeholder that ensures that when it’s time to initialize an instance of our LRUCache, that the user specifies the type the cache will be holding and its capacity.

We’ll change our code to use this trait:

use arrayvec::{Array, ArrayVec};  // new import here

// we’re saying here that any type our cache stores 
// must implement the `Array` trait
pub struct LRUCache<A: Array> {
    entries: ArrayVec<A>,  // add the type parameter here 
    head: usize,
    tail: usize,
    length: usize,
}

With these changes in place, our code should compile successfully!

Implementing Methods for our Cache

We’ll start off with implementing a way to initialize a new LRUCache instance. The way we’ll opt to do this is by implementing the Default trait for our LRUCache. Normally, Default is implemented when you want to provide a method to initialize a type with a default set of field values or configuration. Here though, we’re going to have users of our cache always initialize an LRUCache instance by using the same syntax that ArrayVec uses. So you can think of it as we’re providing one default way to initialize an LRUCache instance.

// the ‘default’ way to initialize an LRUCache instance 
// is by using specifying a type that implements the 
// `Array` trait, namely `<[type; capacity]>`
impl<A: Array> Default for LRUCache<A> {
    fn default() -> Self {
        let cache = LRUCache {
            entries: ArrayVec::new(),
            head: 0,
            tail: 0,
            length: 0,
        };

        // check to make sure that the capacity provided by
        // the user is valid 
        assert!(
            cache.entries.capacity() < usize::max_value(),
            “Capacity overflow”
        );

        cache
    }
}

Implementing `IterMut`

Since we’ve decided that we aren’t going to use a HashMap in our implementation, we don’t have the capability to directly access any cache entries besides the head and tail entries. We’ll have to iterate through our list of entries to find a particular value to fetch from our cache. On that note, it behooves us to implement the Iterator trait for our cache.

We could opt to implement both mutable and immutable iteration, but, thinking about the use case of our cache, it won’t be uncommon for users to want to mutate cache entries. So we’ll just take the lazy route and only implement an iterator that hands out mutable references to cache entries.

The first thing we need to do is define a type that keeps track of the state of the iterator. Most importantly, the position of where the iterator is at any point in time:

// keeps track of where we currently are over 
// the course of iteration 
struct IterMut<‘a, A: ‘a + Array> {
    cache: &’a mut LRUCache<A>,
    pos: usize,
    done: bool,
}

Our IterMut struct needs a mutable reference to our cache itself so that mutable references can be handed out from it. This mutable reference to the cache needs to be valid for at least as long as the LRUCache itself is valid, which is what the ‘a lifetime is specifying.

Starting off the Iterator implementation for our IterMut type, we continue to use the ’a lifetime to specify that T (which the type that is being stored in our Entrys) and the underlying Array type that our LRUCache wraps both live at least as long as our IterMut type.

impl<‘a, T, A> Iterator for IterMut<‘a, A>
where
    T: ‘a,
    A: ‘a + Array<Item = Entry<T>>,
{
    type Item = (usize, &’a mut T);
}

The type Item = (usize, &’a mut T); line indicates that each iteration yields a tuple with the position of the yielded entry, and a mutable reference to the underlying type that the entry was wrapping.

To complete our IterMut implementation, the only method we need to implement is a next method that either returns an Item or None if there are no more items to be yielded from the iteration:

    fn next(&mut self) -> Option<Self::Item> {
        // check if we’ve iterated through all entries 
        if self.done {
            return None;
        }

        // get the current entry and index
        let entry = self.cache.entries[self.pos];
        let index = self.pos;

        // we’re done iterating once we reach the tail entry
        if self.pos == self.cache.tail {
            self.done = true;
        }

        // increment our position
        self.pos = entry.next;

        Some((index, &mut entry.val))
    }

However, if you try to compile this code, you’ll get the following errors:

error[E0508]: cannot move out of type `[Entry<T>]`, a non-copy slice
   --> src/lib.rs:258:21
    |
258 |         let entry = self.cache.entries[self.pos];
    |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |                     |
    |                     cannot move out of here
    |                     move occurs because value has type `Entry<T>`, which does not implement the `Copy` trait
    |                     help: consider borrowing here: `&self.cache.entries[self.pos]`

error[E0515]: cannot return value referencing local data `entry.val`
   --> src/lib.rs:268:9
    |
268 |         Some((index, &mut entry.val))
    |         ^^^^^^^^^^^^^--------------^^
    |         |            |
    |         |            `entry.val` is borrowed here
    |         returns a value referencing data owned by the current function

error[E0596]: cannot borrow `entry.val` as mutable, as `entry` is not declared as mutable
   --> src/lib.rs:268:22
    |
258 |         let entry = self.cache.entries[self.pos];
    |             ----- help: consider changing this to be mutable: `mut entry`
...
268 |         Some((index, &mut entry.val))
    |                      ^^^^^^^^^^^^^^ cannot borrow as mutable

error: aborting due to 3 previous errors

Here, we’re getting a compiler error because our code is saying that our IterMut type is taking ownership of the cache entry, which would mean that the entry is no longer owned by the cache itself! The effect of this, if the compiler allowed us to follow through with it, is that iterating through all of the cache’s entries would move all of those entries out of the cache, leaving the cache with no entries after a single iteration pass! That’s... certainly not what we want.

Let’s try changing the line this to take a mutable reference to the current entry instead, which is what our IterMut type is looking to do anyway:

    let entry = &mut self.cache.entries[self.pos];

This change yields a different error:

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
   --> src/lib.rs:258:26
    |
258 |         let entry = &mut self.cache.entries[self.pos];
    |                          ^^^^^^^^^^^^^^^^^^
    |

The compiler cannot adequately prove that these borrows to each cache entry will not live longer than the cache itself. The caller of the iter_mut method is free to do whatever they wish with the mutable references that are handed out.

Moreover, the compiler also cannot prove that subsequent next calls won’t see us handing out a second mutable reference to an entry that already has a mutable reference referring to it. However, this is a consequence of the compiler not being smart enough to figure this out on its own. We, the programmer, know that subsequent next calls will advance the iterator forward to the next entry, so there will always exist at most one mutable reference to each cache entry at a time.

In order to resolve this, we’re going to tell the compiler to trust us and opt for the backdoor option of dipping into some unsafe code here. We’ll take a raw pointer to each cache entry, which is essentially us telling the compiler that whatever this raw pointer refers to will not cause undefined behavior, because we know that it won’t, so long as we use IterMut in the intended way.

    let entry = unsafe { &mut *(&mut self.cache.entries[self.pos] as *mut Entry<T>) };

If this makes you uneasy (and honestly, it probably should at least a little bit), well, you can at least take some solace in that fact that this isn’t production code that has any possibility of causing actual problems of consequence down the line 🙂

But with that change, our code should compile without issue!

Implementing Actual Cache Functionality

We’ll start off by getting the easy methods out of the way:

// we need to bring the types that our `LRUCache` is 
// parameterized over into our `impl` block
impl<T, A> LRUCache<A>
where
    A: Array<Item = Entry<T>>,
{
    /// Returns the number of entries in the cache
    pub fn len(&self) -> usize {
        self.length
    }   

    /// Indicates whether the cache is empty or not 
    pub fn is_empty(&self) -> bool {
        self.length == 0
    }

    /// Returns an instance of our `IterMut` type 
    /// We’ll keep this function private to minimize
    /// the chance of mutable references to cache 
    /// entries being used incorrectly 
    fn iter_mut(&mut self) -> IterMut<A> {
        IterMut {
            pos: self.head,
            done: self.is_empty(),
            cache: self,
        }
    }

    /// Clears the cache of all entries 
    pub fn clear(&mut self) {
        self.entries.clear();
        self.head = 0;
        self.tail = 0;
        self.length = 0;
    }
}

It will be convenient to add some methods for manipulating elements in our linked list, such as being able to add an entry to the head of the list or to the tail of the list. Let’s add those:

    /// Returns a reference to the element stored at 
    /// the head of the list 
    pub fn front(&self) -> Option&T> {
        // fetch the head entry and return a 
        // reference to the inner value 
        self.entries.get(self.head).map(|e| &e.val)
    }

    /// Returns a mutable reference to the element stored 
    // at the head of the list 
    pub fn front_mut(&mut self) -> Option<&mut T> {
        // fetch the head entry mutably and return a 
        // mutable reference to the inner value
        self.entries.get_mut(self.head).map(|e| &mut e.val)
    }

    /// Takes an entry that has been added to the linked 
    /// list and moves the head to the entry’s position 
    fn push_front(&mut self, index: usize) {
        if self.entries.len() == 1 {
            self.tail = index;
        } else {
            self.entries[index].next = self.head;
            self.entries[self.head].prev = index;
        }

        self.head = index;
    }

    /// Remove the last entry from the list and returns
    /// the index of the removed entry. Note that this 
    /// only unlinks the entry from the list, it doesn’t
    /// remove it from the array.
    fn pop_back(&mut self) -> usize {
        let old_tail = self.tail;
        let new_tail = self.entries[old_tail].prev;
        self.tail = new_tail;
        old_tail
    }

We’ll add one more method, remove, that takes as input an index into our array-backed linked list and “removes” the entry at that index. Note that this method actually only unlinks the entry from the linked list without actually removing it from the array. This is to avoid the runtime overhead of having to shift subsequent array elements forward to fill in the empty slot.

    fn remove(&mut self, index: usize) {
        assert!(self.length > 0);

        let prev = self.entries[index].prev;
        let next = self.entries[index].next;

        if index == self.head {
            self.head = next;
        } else {
            self.entries[prev].next = next;
        }

        if index == self.tail {
            self.tail = prev;
        } else {
            self.entries[next].prev = prev;
        }

        self.length -= 1;
    }

Touching our Entries

With those out of the way, we can now implement the functionality that makes up the main attraction. We’ll start with the touch method, which is responsible for finding an entry and moving it from its initial position in the cache to the head of the linked list.

In our Python implementation, we could conveniently access any entry in the cache via its associated key in the dictionary. Here, we opted to forgo that convenience. We’ll have to iterate over each entry and determine if it’s the entry we’re looking to move; only then will we have the index of the entry and can actually move it.

Let’s first define a helper method called touch_index that will receive an index to an entry in our cache and move it to the head of the linked list:

    /// Touch a given entry at the given index, putting it 
    /// first in the list.
    fn touch_index(&mut self, index: usize) {
        if index != self.head {
            self.remove(index);

            // need to increment `self.length` here since 
            // `remove` decrements it 
            self.length += 1;
            self.push_front(index);
        }
    }

With that, we can now implement touch. We’ll specify that the predicate must implement the FnMut trait, which, according to the docs, fits our use-case nicely:

Use FnMut as a bound when you want to accept a parameter of function-like type and need to call it repeatedly, while allowing it to mutate state.

We’re more concerned with being able to “call it [the predicate] repeatedly” rather than having it mutate state (which the predicate shouldn’t be doing).

Our touch method iterates over the entries in our cache (using our iter_mut method) and finds the first entry whose value matches the predicate. We then pass the index associated with the found entry to our touch_index method, which handles moving the entry to the head of the list:

    /// Touches the first entry in the cache that matches the
    /// given predicate. Returns `true` on a hit and `false`
    /// if no match is found.
    pub fn touch<F>(&mut self, mut pred: F) -> bool
    where
        F: FnMut(&T) -> bool,
    {
        match self.iter_mut().find(|&(_, ref x)| pred(x)) {
            Some((i, _)) => {
                self.touch_index(i);
                true
            },
            None => false,
        }
    }

We can implement a similar method, lookup, which will essentially do the same thing as what our touch method is doing, but instead of returning a boolean indicating whether an entry matching the input predicate was found or not, lookup instead returns the found entry’s value or None.

    pub fn lookup<F, R>(&mut self, mut pred: F) -> Option<R>
    where
        F: FnMut(&mut T) -> Option<R>,
    {
        let mut result = None;

        // iterate through our entries, testing each 
        // using the predicate
        for (i, entry) in self.iter_mut() {
            if let Some(r) = pred(entry) {
                result = Some((i, r));
                break;
            }
        }

        // once we’ve iterated through all entries, match 
        // on the result to move it to the head of the list
        // if necessary
        match result {
            None => None,
            Some((i, r)) => {
                self.touch_index(i);
                Some(r)
            }
        }
    }

Inserting New Entries

We can now fetch existing entries from our cache, and those entries will be moved to the head of the list when they are fetched. Let’s add an insert method that will take some val of arbitrary type and add it to the head of the linked list:

    fn insert(&mut self, val: T) {
        let entry = Entry {
            val,
            prev: 0,
            next: 0,
        };

        // check if the cache is at full capacity 
        let new_head = if self.length == self.entries.capacity() {
            // get the index of the oldest entry
            let last_index = self.pop_back();
            // overwrite the oldest entry with the new entry
            self.entries[last_index] = entry;
            // return the index of the newly-overwritten entry
            last_index
        } else {
            self.entries.push(entry);
            self.length += 1;
            self.entries.len() - 1
        };

        self.push_front(new_head);
    }

With that, our cache is feature-complete! You can find the full code here, complete with tests as well as some additional miscellaneous trait implementations.

In Summary

I had a lot of fun transposing a Python data structure implementation that I’m quite familiar with into a Rust version. Clearly, the fact that Python and Rust belong in such different paradigms contributes significantly to how these implementations turned out.

However, we did inject some of our own design decisions into the Rust implementation as well (opting to forgo including a HashMap as part of the design), and that too contributed in part to the data structure’s design being so different between the two languages.

I hope you had fun learning about LRU caches as well! 🙂

Why I'm Switching from VSCode to OniVim

Sean Chen — Wed, 19 Aug 2020 05:24:58 +0000

The original version of this post can be found on my developer blog at https://seanchen1991.github.io/posts/onivim2/.

As someone interested in open source sustainability, I recently heard about a very interesting open source licensing scheme that a project called OniVim 2 uses. The central premise of the project itself is to combine the efficient modal editing functionality of Vim with a modern text editor UI.

How OniVim’s Licensing Scheme Works

The OniVim 2 editor is currently under active development by Outrun Labs. Any updates pushed to the project by them go under a commercial license; this is the closed source half of the scheme. Conversely, any updates merged into the project from outside Outrun go under an MIT license; this is the open source half of the scheme. Lastly, any code licensed under the commercial license is transferred over to the MIT license after an 18 month window.

Anyone can freely use the 18-month-old version of the project. For those who wish use the up-to-date version, a commercial license must be purchased.

You can read more about the why and how of this scheme here.

The Vim Editor I Never Knew I Needed

I’ve been trying to embrace Vim for years, but have, up to this point, been mostly unsuccessful. I’ve internalized the fundamental Vim keybindings, but have never gotten much further than that. I would always become overwhelmed with the sheer amount of freedom and choice when it came to how much you could customize your Vim experience through plugins and other customizations.

Certainly there are people who love the level of customizability that Vim provides. I prefer something sensible out-of-the-box that doesn’t require ~~any~~ much fiddling, with the option for configurability should the need arise (this is probably why I'll likely never migrate off of OSX).

For a long time I defaulted to VSCode with the Vim keybindings plugin enabled. However, this always felt like a subpar compromise; VSCode is clearly not built with Vim keybindings in mind.

The first time I fired up an instance of OniVim 2, I was blown away by the snappiness of it. That, and the fact that it is very clearly designed around the modal editing experience, prompted me to shell out for a commercial license right then and there.

OniVim 2 is a “batteries included” editor from the get-go, but one of its most powerful extensibility features is the fact that it allows users to hook into the VSCode plugin ecosystem. As a result, installing and enabling useful extensions will be just as easy with OniVim 2 as it is with VSCode.

There’s certainly a lot of potential here, but at the same time, keep in mind that the project is still in an alpha stage. There are many key features still missing at this point, such as an autosave feature (so you have to keep typing :w every so often), as well as being able to pull in your .vimrc file for further customization (this is super important as it will enable a more seamless transition for vim/neovim users). I also ran into an issue where a missing extension file needed for Haskell syntax highlighting caused the entire program to crash.

Despite these issues, I’m very much looking forward to following along with OniVim’s development as time goes on and seeing the incremental improvements to the overall editing experience!

Some Reasons Why Open Source Isn’t Sustainable

In addition to having the potential to become an editor that I can see myself adopting as my go-to, I’m also really interested in seeing how things shake out for OniVim on the sustainability front.

Nadia Eghbal, in her new book Working in Public, argues that the widespread notion that the main problems open source communities face is a lack of contributors and/or a lack of funding don’t reveal the whole scope of the problem.

She makes the point that in recent years, contributing to open source projects has become very frictionless, due in large part to the proliferation and innovations of GitHub. But this ends up resulting in very high turnover rate for open source projects.

Maintainers end up having to spend a lot of time interfacing with the revolving door of casual contributors looking to submit a PR or two to their project. Ultimately, this is work that most maintainers do not want to be doing in their spare time, which is a recipe for maintainer burnout.

How OniVim’s Licensing Scheme (Partly) Addresses These Issues

One possible way to address the unsustainable nature of open source, according to Nadia in her book, is to make it harder for people to contribute to open source projects. The idea being that committed users and contributors are more invested in a project, which often leads to higher-quality contributions.

The really cool thing about OniVim’s licensing scheme is the fact that it kills two birds with one stone. On the one hand, charging for commercial licenses means the project has some funding that benefits the maintainers. One the other hand, it also provides a way to filter for the more committed users!

The maintainers of OniVim mention here that, as the project attracts more users, issues will be prioritized based on whether it was logged by a user who owns a commercial license. This means they’ll be spending less time triaging and responding to issues, and more time iterating on the project itself.

Some open questions in my mind include:

Will it lead to a more sustainable workflow for the maintainers down the line? Will prioritizing the issues raised by paying users lead the project down a good direction? Will the financials and the economics end up working out?

With all that being said, I’m really curious to see how this licensing scheme works out for the OniVim maintainers long term!

Haskell::From(Rust) I: Infix Notation and Currying

Sean Chen — Mon, 20 Jul 2020 23:29:24 +0000

The original version of this post can be found on my developer blog at https://seanchen1991.github.io/posts/haskell-from-rust-i/.

Prelude

I’ve been meaning to learn Haskell for a while now. Most people who write Rust likely have had at least a background-level exposure to Haskell (if they hadn’t already encountered/learned the language on their own prior). Since the language (along with ML and possibly OCaml?) had such an effect on Rust’s development, digging into it will likely pay dividends in the form of improving my understanding of Rust.

This Haskell::From(Rust) series will chronicle some of the learnings I glean from learning Haskell, as well as the takeaways that can be applied to write better code in Rust.

The Setup

While working through Exercism’s Haskell track, specifically the problem asking you to implement a pangram checker, I encountered a confusion point regarding infix functions. From what I can gather, this is not an uncommon sticking point for those who are new to Haskell.

In order to solve this pangram problem, I opted to sort the input string and filter out any duplicates:

isPangram text = [‘a’..’z’] == (List.nub . List.filter (/=‘ ‘) . List.sort $ text)

Afterwards, I browsed some others’ implementations and came across this one:

isPangram text = all (`elem` lowercased) [‘a’..’z’]
    where lowercased = map toLower text

The Turn

I read (`elem` lowercased) [‘a’..’z’] as checking that the first element in the lowercased string is a member of the set [‘a’..’z’]. The all function then facilitates iterating through all of the characters of lowercased, ensuring that no iterations return false.

In short, I thought this line checked that every character in the input string was a lower-cased letter. But that shouldn’t be sufficient for implementing a pangram function. Upon testing out the code, it did indeed work (passing it an input string that didn’t contain all of the English letters caused it to return false), so clearly there was a hole in my understanding of this logic.

The Prestige

After doing some research and posting my question on Haskell forums, I found an explanation that clicked:

Any operator (including foo) can be written in prefix notation by surrounding it with parentheses: (+), (==), (`div`). These are called sections, and they’re regular functions like map and sin. For example, instead of 2 + 2, you can write (+) 2 2. You can even leave off either the left or right operand to curry an operator. For example, (`div` 0) is a function that takes one argument and divides it by zero.

Haskell: The Confusing Parts 1

The last sentence is what made it click for me: this was an example of currying. Essentially, (`elem` lowercased) leveraged currying to define a new function that takes one argument and checks that that argument is an element of lowercased. My understanding had been flipped based off of how I read the function, which was heavily influenced by what programming languages I’d had prior experience with.

Clearly, if one comes from an imperative or OOP background, this sort of syntax can be strange. Even Rust, with its relatively strong emphasis on functional norms (especially when it comes to chaining iterator adapters), isn’t nearly as expressive when it comes to the number of ways in which functions can be defined in comparison to Haskell.

This is, however, a feature of Haskell that I find quite enticing. I’m looking forward to learning more and digging in deeper!

Before We Part Ways

I couldn’t leave my dear readers without at least a bit of Rust code. That’d be inexcusable!

Using the same pieces present in the Haskell implementation, we can implement a pangram function in Rust like this:

fn is_pangram(text: &str) -> bool {
    // maps to `[‘a’..’z’]`
    let alphabet = “abcdefghijklmnopqrstuvwxyz”;

    // maps to `where lowercased = map toLower text`
    let lowercased = text.to_lowercase();

    // maps to `all (`elem` lowercased)`
    alphabet.chars().all(|letter| lowercased.contains(letter))
}

Not as elegant as the Haskell version, but also not too far off in my opinion.

Edit

A reader, Maxwell Orok, reached out to me to let me know that char ranges are a thing in Rust now as of version 1.45. This is great, as it allows us to clean up the Rust implementation a bit:

fn is_pangram(text: &str) -> bool {
    // maps to `[‘a’..’z’]`
    // We can now collect into a `String` from a `Range`
    // instead of having to hard code the string
    let alphabet: String = ('a'..='z').collect();

    // maps to `where lowercased = map toLower text`
    let lowercased = text.to_lowercase();

    // maps to `all (`elem` lowercased)`
    alphabet.chars().all(|letter| lowercased.contains(letter))
}

Definitely much better in my opinion!

Some Learnings from Implementing a Normalizing Rust Representer

Sean Chen — Mon, 13 Jul 2020 19:31:31 +0000

I’ve been helping out and contributing to exercism.io for the past few months. As an open source platform for learning programming languages that supports Rust, Exercism aligns very well with all the things I’m currently passionate about: open source, teaching, and Rust.

One of the most challenging hurdles the Exercism platform faces is the fact that students who opt in to receive mentor feedback on their work have to wait for a live person to get around to reviewing their submission. Decreasing wait times for students is thus an important metric to optimize for in order to improve the overall student experience on the platform.

In this post I’ll be talking about a project I’ve been working on that aims to address this problem. I’ll also be discussing the learnings I’ve been taking away from working on this project, as it’s my first non-toy Rust project that I’ve undertaken.

How Do We Decrease Wait Times for Students?

There are a couple of factors that contribute to longer waiting times for students on the Exercism platform: the availability of mentors, the number of pending submissions in the queue, and how much time it takes for a mentor to compose their feedback response to any one exercise.

Perhaps in the future, there will be a purely-autonomous system that is able to provide high quality tailored feedback in response to a student’s code submission. However, at this point in time, when it comes to giving human-centric feedback, I don’t believe computers are up to snuff yet.

So the question becomes: how do we streamline the process through which Exercism mentors provide feedback to students?

One thing that would help would be to reduce the set of possible configurations of student submissions, at least from the perspective of mentors. Submissions can be normalized by stripping away trivial aspects, such as formatting, comments, and variable names, that don’t contribute to making a submission unique as far as its logical approach.

For example, given the following student implementation of an Exercism exercise called two-fer

fn twofer(name: &str) -> String {
    match name {
        "" => "One for you, one for me.".to_string(),
        // use the `format!` macro to return a formatted String
        _ => format!("One for {}, one for me.", name),
    }
}

would be transformed into the following:

fn PLACEHOLDER_1(PLACEHOLDER_2: &str) -> String {
    match PLACEHOLDER_2 {
        "" => "One for you, one for me.".to_string(),
        _ => format!("One for {}, one for me.", PLACEHOLDER_2),
    }
}

The idea is that the transformed "normalized" representation highlights the students' high level approach by removing comments, variable and function names, and things like that that don't strictly have anything to do with the approach the student took to solve the problem.

In the normalized output in the above example, we still have the function's signature, we can still see that the student opted to use a match on the input, that they used the format! macro to perform string interpolation, and that they're taking advantage of Rust's implicit return syntax. Overall, mentors should still be able to see whether a student is writing idiomatic, well-structured code to solve any given Exercism problem.

Performing this normalization on an input program is the job of a representer. In Exercism, each language track will have its own representer to handle submissions for that particular track. When I noticed that the Rust track didn’t yet have a representer that was being worked on, I jumped at the chance to work on it!

Implementing a Rust Representer

At a high level, the steps a normalizing representer needs to take are the following:

Parse the source code into an abstract syntax tree.
Apply transformations to the appropriate tree nodes.
Turn the tree back into a string representing the transformed source code.

The syn crate is perhaps one of the most robust libraries available in the Rust ecosystem for parsing and transforming Rust code. It’s primary use-case is as a utility for implementing procedural macros in Rust, but judging from its thorough documentation, it seemed full-featured enough to handle the use-case I had in mind.

The first step I took was to use the functionality provided by syn to parse some source code into an AST, print the AST, and then turn that AST back into a string:

use std::env;
use std::fs::File;
use std::io::prelude::*;
use std::io::Read;
use std::process;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let output_path = “./output.rs”;
    let mut args = env::args();
    let _ = args.next();

    let filename = match (args.next(), args.next()) {
        (Some(filename), None) => filename,
        _ => {
            eprintln!(“Usage: representer path/to/filename.rs”);
            process::exit(1);
        }
    };

    let mut input = File::open(&filename)?;
    let mut src = String::new();
    input.read_to_string(&mut src)?;

    let syntax = syn::parse_file(&src)?;
    println!(“{:?}”, syntax);

    let mut output = File::create(output_path)?;
    output.write(syntax.to_string().as_bytes())?;

    Ok(())
}

Starting off with this sets up a nice boundary in which we can work within; we have the first step and the last step in place. Now we’ll need to work out how we’ll traverse the AST and transform the relevant tree nodes.

`syn`’s `VisitMut` Trait

The syn crate provides an extremely handy trait called VisitMut, which provides the user with a lot of flexibility when it comes to traversing and mutating AST nodes in-place. The VisitMut trait exposes a whole slew of methods for accessing every type of AST node that syn differentiates.

A logical first place to start would be replacing the identifier name of a let binding, taking something as simple as

let x = 5;

and transforming it into

let PLACEHOLDER = 5;

The visit_pat_ident_mut method is what we’re looking for. It gives us access to AST nodes that represent variable binding patterns, of which let bindings are one of.

Since visit_pat_ident_mut is a trait method, we need to implement the VisitMut trait on a type so that the method’s behavior can be overwritten. To start off with, I defined an empty struct for this purpose:

use proc_macro2::{Ident, Span};
use syn::visit_mut::VisitMut;

struct IdentVisitor;

impl VisitMut for IdentVisitor {
    fn visit_pat_ident_mut(&mut self, node: &mut PatIdent) {
        // replace the node’s `ident` field with “PLACEHOLDER”
        self.ident = Ident::new(“PLACEHOLDER”, Span::call_site());
    }
}

Lo and behold, this simple logic worked! Top-level let bindings were traversed, with their variable names replaced with "PLACEHOLDER".

Generating Placeholder IDs

Turning our attention to replacing multiple variable names, we’ll need to generate IDs for each placeholder, so that mentors are able to differentiate between bindings with different patterns in the original submission.

One way to accommodate this is to store a global HashMap of all the generated mappings. This way, we can tell if an identifier has been encountered before, in which case we’ll re-use the same generated placeholder; otherwise a new placeholder will be generated.

This is where our thus-far empty IdentVisitor struct comes in handy: we’ll define the hash map as a field on it.

...
use std::collections::HashMap;
use std::collections::hash_map::Entry;

const PLACEHOLDER: &str = “PLACEHOLDER_”;

struct IdentVisitor {
    mappings: HashMap<String, u32>,
    // a monotonically-increasing counter for new placeholders
    uid: u32,
}

impl IdentVisitor {
    fn new() -> Self {
        IdentVisitor {
            mappings: HashMap::new(),
            uid: 0,
        }
    }

We’ll then also add a method to either fetch a pre-existing placeholder, or generate a new one if the identifier doesn’t yet exist as a mapping:

impl IdentVisitor {
    ...

    fn get_or_insert_mapping(&mut self, ident: String) -> String {
        let uid = match self.mappings.entry(ident) {
            Entry::Occupied(o) => o.into_mut(),
            Entry::Vacant(v) => {
                self.uid += 1;
                v.insert(self.uid);
            }
        };

        format!(“{}{}”, PLACEHOLDER, uid)
    }
}

We can now refactor our visit_pat_ident_mut method to use get_or_insert_mapping:

impl VisitMut for IdentVisitor {
    fn visit_pat_ident_mut(&mut self, node: &mut PatIdent) {
        let placeholder = self.get_or_insert_mapping(node.ident.to_string());
        self.ident = Ident::new(placeholder, Span::call_site());
    }
}

Huzzah! Multiple let bindings are now replaced with placeholders that each have a different ID:

let PLACEHOLDER_1 = 5;
let mut PLACEHOLDER_2 = 15;

Eliminating Duplicated Code with Traits

With variable bindings out of the way, much of the way forward involves accessing every other type of AST node that contains identifiers that we’d like to replace: struct names, enum names, user-defined types, function definitions, etc.

Struct names can be accessed via the visit_item_struct_mut method. Recycling the same logic we used for transforming let binding identifiers, we can write:

impl VisitMut for IdentVisitor {
    ...

    fn visit_item_struct_mut(&mut self, node: &mut ItemStruct) {
        let placeholder = self.get_or_insert_mapping(node.ident.to_string());
        self.ident = Ident::new(placeholder, Span::call_site());    
    }
}

For certain types of AST nodes (such as the Expr type that encapsulates Rust expressions), the logic can certainly get more complicated, but this is the general gist of the overall pattern.

One piece of advice I was given by a much more experienced Rust developer was to implement a new trait to represent the ability of certain nodes to have their identifier replaced. While doing such a thing won’t actually allow us to significantly reduce the total SLOCs of the implementation as it stands now, it will improve future maintainability of the codebase. Plus, I’d never really been presented with a relevant opportunity to implement a Rust trait, so I jumped at the chance to do it in a “real” Rust project.

The trait I ended up implementing exposes two methods: ident_string, which ensures that the AST node has an identifier that can be replaced, and set_ident, which replaces the node’s identifier with a specified string:

trait ReplaceIdentifier {
    fn ident_string(&self) -> String;
    fn set_ident(&mut self, ident: String);
}

Now, we’ll implement this trait on nodes that have an identifier, which include the aforementioned PatIdent and ItemStruct types, as well as many others:

impl ReplaceIdentifier for PatIdent {
    fn ident_string(&self) -> String {
        self.ident.to_string()
    }

    fn set_ident(&mut self, ident: String) {
        self.ident = Ident::new(ident, Span::call_site());
    }
}

impl ReplaceIdentifier for ItemStruct {
    fn ident_string(&self) -> String {
        self.ident.to_string()
    }

    fn set_ident(&mut self, ident: String) {
        self.ident = Ident::new(ident, Span::call_site());
    }
}

I then opted to implement a replace_identifier method for any type that implements the ReplaceIdentifier trait:

impl IdentVisitor {
    ...

    fn replace_identifier<Node: ReplaceIdentifier>(&mut self, node: Node) {
        let ident_string = node.ident_string();
        let identifier = self.get_or_insert_mapping(ident_string);
        node.set_ident(identifier);
    }
}

Following this, we’ll change our various visit_mut methods to utilize replace_identifier:

impl IdentVisitor {
  ...

  fn visit_pat_ident_mut(&mut self, node: &mut PatIdent) {
      self.replace_identifier(node);
  }

  fn visit_item_struct_mut(&mut self, node: &mut ItemStruct) {
      self.replace_identifier(node);
  }
}

Refactoring the code in this way clearly separates concerns: the visit_mut methods access the AST nodes we care about, the ReplaceIdentifier trait lays out the contract that nodes need to adhere to, which the replace_identifier method can then act upon.

It was so cool for me to have gotten an opportunity to utilize traits in such a way when implementing this project. Before this, I’d only ever had a vague understanding of traits. Using them in this way in this project really served to hammer home the point of why traits are useful and when are appropriate times to use them.

In Closing

While the portrait of the representer that I’ve painted in this post is quite simplified (some types of Rust syntax, such as expressions, are a bit more complex to handle), it preserves the kernel of how the representer functions. If you’re interested, you can take a look at the actual implementation here to see additional gory details.

After hitting the initial MVP, I've since stepped away working on the Rust representer and handed off maintenance to the other Exercism Rust maintainers. One feature extension I've thought of has to do with all of the redundant boilerplate that exists to implement the ReplaceIdentifier trait for different AST nodes; if you take a look at it here, you'll notice almost all of the trait implementations are identical. A procedural macro could be defined to generate this boilerplate, such that we'd simply be able to annotate the different AST node types, which would be pretty slick:

#[derive(ReplaceIdentifier)]
use syn::PatIdent;

If you’re interested in contributing to this sort of project, or helping out as a mentor for those looking to sharpen their programming skills, Exercism is always looking for more open source contributors, maintainers, and mentors, especially with our in-progress V3 push!

The Story of Tail Call Optimizations in Rust

Sean Chen — Sun, 07 Jun 2020 18:56:06 +0000

I think tail call optimizations are pretty neat, particularly how they work to solve a fundamental issue with how recursive function calls execute. Functional languages like Haskell and those of the Lisp family, as well as logic languages (of which Prolog is probably the most well-known exemplar) emphasize recursive ways of thinking about problems. These languages have much to gain performance-wise by taking advantage of tail call optimizations.

Note: I don't go into excruciating details on how tail calls work in this post. If you feel like you need/want some more background on them, here are a few awesome resources:

The YouTube channel Computerphile has a video where they walk through examples of tail-recursive functions in painstaking detail.

A detailed explanation on Stack Overflow on the concept of tail recursion.

With the recent trend over the last few years of emphasizing functional paradigms and idioms in the programming community, you would think that tail call optimizations show up in many compiler/interpreter implementations. And yet, it turns out that many of these popular languages don’t implement tail call optimization. JavaScript had it up till a few years ago, when it removed support for it 1. Python doesn’t support it 2. Neither does Rust.

Before we dig into the story of why that is the case, let’s briefly summarize the idea behind tail call optimizations.

How Tail Call Optimizations Work (In Theory)

Tail-recursive functions, if run in an environment that doesn’t support TCO, exhibit linear memory growth relative to the function’s input size. This is because each recursive call allocates an additional stack frame to the call stack. The goal of TCO is to eliminate this linear memory usage by running tail-recursive functions in such a way that a new stack frame doesn’t need to be allocated for each call.

One way to achieve this is to have the compiler, once it realizes it needs to perform TCO, transform the tail-recursive function execution to instead use something more akin to an iterative loop in the background. The effect of this is that the result of the tail-recursive function is calculated using just a single stack frame. Ta-da! Constant memory usage.

With that, let’s get back to the question of why Rust doesn’t exhibit TCO.

Going Through the Rust Wayback Machine

The earliest references to tail call optimizations in Rust I could dig up go all the way back to the Rust project’s inception. I found this mailing list thread from 2013, where Graydon Hoare enumerates his points for why he didn’t think tail call optimizations belonged in Rust:

That mailing list thread refers to this GitHub issue, circa 2011, when the initial authors of the project were grappling with how to implement TCO in the then-budding compiler. The heart of the problem seemed to be due to incompatibilities with LLVM at the time; to be fair, a lot of what they’re talking about in the issue goes over my head.

What I find so interesting though is that, despite this initial grim prognosis that TCO wouldn’t be implemented in Rust (from the original authors too, no doubt), people to this day still haven’t stopped trying to inplement TCO in the Rust compiler.

Subsequent Proposals for Adding TCO into the Rust Compiler

In May of 2014, this PR was opened, citing that LLVM was now able to support TCO in response to the earlier mailing list thread. More specifically, this PR sought to enable on-demand TCO by introducing a new keyword become, which would prompt the compiler to perform TCO on the specified tail recursive function execution.

Over the course of the PR’s lifetime, it was pointed out that the Rust compiler could, in certain situations, infer when TCO was appropriate and perform it 3. The proposed become keyword would thus be similar in spirit to the unsafe keyword, but specifically for TCO. Needless to say, this PR didn't end up getting accepted and merged.

A subsequent RFC was opened in February of 2017, very much in the same vein as the previous proposal. Interestingly, the author notes that some of the biggest hurdles to getting tail call optimizations (what are referred to as “proper tail calls”) merged were:

Portability issues; LLVM at the time didn’t support proper tail calls when targeting certain architectures, notably MIPS and WebAssembly.
The fact that proper tail calls in LLVM were actually likely to cause a performance penalty due to how they were implemented at the time.
TCO makes debugging more difficult since it overwrites stack values.

Indeed, the author of the RFC admits that Rust has gotten on perfectly fine thus far without TCO, and that it will certainly continue on just fine without it.

Thus far, explicit user-controlled TCO hasn’t made it into the Rust compiler.

Enabling TCO via a Library

However, many of the issues that bog down TCO RFCs and proposals can be sidestepped to an extent. Several homebrew solutions for adding explicit TCO to Rust exist.

The general idea with these is to implement what is called a “trampoline”. This refers to the abstraction that actually takes a tail-recursive function and transforms it to use an iterative loop instead.

How about we first implement this with a trampoline as a slow cross-platform fallback implementation, and then successively implement faster methods for each architecture/platform?
This way the feature can be ready quite quickly, so people can use it for elegant programming. In a future version of rustc such code will magically become fast.
@ConnyOnny, 4

Bruno Corrêa Zimmermann’s tramp.rs library is probably the most high-profile of these library solutions. Let’s take a peek under the hood and see how it works.

Diving into tramp.rs

The tramp.rs library exports two macros, rec_call! and rec_ret!, that facilitate the same behavior as what the proposed become keyword would do: it allows the programmer to prompt the Rust runtime to execute the specified tail-recursive function via an iterative loop, thereby decreasing the memory cost of the function to a constant.

The rec_call! macro is what kicks this process off, and is most analogous to what the become keyword would have done if it had been introduced into the Rust compiler back in 2014:

macro_rules! rec_call {
    ($call:expr) => {
        return BorrowRec::Call(Thunk::new(move || $call));
    };
}

rec_call! makes use of two additional important constructs, BorrowRec and Thunk.

enum BorrowRec<'a, T> {
    Ret(T),
    Call(Thunk<'a, BorrowRec<'a, T>>),
}

The BorrowRec enum represents two possible states a tail-recursive function call can be in at any one time: either it hasn’t reached its base case yet, in which case we’re still in the BorrowRec::Call state, or it has reached a base case and has produced its final value(s), in which case we’ve arrived at the BorrowRec::Ret state.

The Call variant of the BorrowRec enum contains the following definition for a Thunk:

struct Thunk<'a, T> {
    fun: Box<FnThunk<Out = T> + 'a>,
}

The Thunk struct holds on to a reference to the tail-recursive function, which is represented by the FnThunk trait.

Lastly, this is all tied together with the tramp function:

fn tramp<'a, T>(mut res: BorrowRec<'a, T>) -> T {
    loop {
        match res {
            BorrowRec::Ret(x) => break x,
            BorrowRec::Call(thunk) => res = thunk.compute(),
        }
    }
}

This receives as input a tail-recursive function contained in a BorrowRec instance, and continually calls the function so long as the BorrowRec remains in the Call state. Otherwise, when the recursive function arrives at the Ret state with its final computed value, that final value is returned via the rec_ret! macro.

Are We TCO Yet?

So that’s it right? tramp.rs is the hero we all needed to enable on-demand TCO in our Rust programs, right?

I’m afraid not.

While I really like how the idea of trampolining as a way to incrementally introduce TCO is presented in this implementation, benchmarks that @timthelion has graciously already run indicate that using tramp.rs leads to a slight regression in performance compared to manually converting the tail-recursive function to an iterative loop.

Part of what contributes to the slowdown of tramp.rs’s performance is likely, as @jonhoo points out, the fact that each rec_call! call allocates memory on the heap due to it calling Thunk::new:

So it turns that tramp.rs’s trampolining implementation doesn’t even actually achieve the constant memory usage that TCO promises!

Ah well. Perhaps on-demand TCO will be added to the Rust compiler in the future. Or maybe not; the Rust ecosystem has gotten by just fine without it thus far.

Links and Citations

1: https://stackoverflow.com/questions/42788139/es6-tail-recursion-optimisation-stack-overflow

2: http://neopythonic.blogspot.com/2009/04/final-words-on-tail-calls.html

3: https://github.com/rust-lang/rfcs/issues/271#issuecomment-271161622

4: https://github.com/rust-lang/rfcs/issues/271#issuecomment-269255176

DEV Community: Sean Chen

Testing Leo Programs with DokoJS

Challenges Around Testing Leo Code

Getting Started with DokoJS

Install Prerequisites

Install DokoJS Itself

Initializing a New Project

Configuring DokoJS

Generating Leo-to-JS Bindings

Walking Through Our Leo Program

Type Definitions

Minting Functions

Transfer Functions

Public-to-Private and Private-to-Public Transfers

Test Helpers

Writing Our Tests

Setting Up Dependencies, Constants, and Helpers

Testing Public Minting

Running Our Tests

Testing Private Minting

Testing Public Transfer

Testing Private Transfer

Testing Public-to-Private Transfer

Testing Private-to-Public Transfer

In Summary

A Beginner's Guide to Handling Errors in Rust

Error handling use cases

Surfacing library errors

Defining error variants in a central type

Returning variants of our AppError

Annotating error variants with thiserror

A more manual approach

Summary

Implementing an LRU Cache in Rust

Coming up with Requirements for our Cache

Our Python Implementation

Transitioning to a Rust Implementation

Implementing the Rust Version of our Cache

Bringing in ArrayVec as a Dependency

Implementing Methods for our Cache

Implementing IterMut

Implementing Actual Cache Functionality

Touching our Entries

Inserting New Entries

In Summary

Why I'm Switching from VSCode to OniVim

How OniVim’s Licensing Scheme Works

The Vim Editor I Never Knew I Needed

Some Reasons Why Open Source Isn’t Sustainable

How OniVim’s Licensing Scheme (Partly) Addresses These Issues

Haskell::From(Rust) I: Infix Notation and Currying

Prelude

The Setup

The Turn

The Prestige

Before We Part Ways

Some Learnings from Implementing a Normalizing Rust Representer

How Do We Decrease Wait Times for Students?

Implementing a Rust Representer

syn’s VisitMut Trait

Generating Placeholder IDs

Eliminating Duplicated Code with Traits

In Closing

The Story of Tail Call Optimizations in Rust

How Tail Call Optimizations Work (In Theory)

Going Through the Rust Wayback Machine

Subsequent Proposals for Adding TCO into the Rust Compiler

Enabling TCO via a Library

Diving into tramp.rs

Are We TCO Yet?

Links and Citations

Returning variants of our `AppError`

Annotating error variants with `thiserror`

Bringing in `ArrayVec` as a Dependency

Implementing `IterMut`

`syn`’s `VisitMut` Trait