Forem: Konstantin Grechishchev

Five simple steps to use any Arduino C++ library in a Rust project 🦀

Konstantin Grechishchev — Sun, 13 Nov 2022 14:27:16 +0000

Arduino helps circuit developers to build electronic projects and is, perhaps, the most used open-source hardware and software platform. It is popular across millions of hobbyists across the world. Historically, Arduino boards are programmed with C++ programming language using the Arduino IDE. The availability of powerful ARM-based Arduino-compatible boards made it possible to use python, JavaScript, or even a browser to program your circuit. While they are easier to study for a new joiner without an existing programming background, C++ stays a default language choice, especially when dealing with cheap and low-memory AVR-controller boards and having a need to run more or less complex projects.

However, the compact binary size and efficiency of compiled code is probably not the main advantage of the traditional Arduino ecosystem. If the project is more complex than blinking the led, it would likely require integration with the range of sensors, servo motors, and other third-party peripheries. Most manufacturers develop precisely C++ Arduino-compatible driver libraries to be used "out of the box".

Rust language shares all advantages of efficient C++ code. With the rust community growing year after year, more and more people try using rust to program their Arduino boards. Consequently, the Arduino Rust ecosystem have significantly developed in the last couple of years. The Hardware Abstraction Layer for AVR microcontrollers avr-hal, Rudino library and ravedude CLI utility to make Rust development for AVR microcontrollers easier are just a few examples of the solid foundation developed so far.

Third-party library availability is, however, still lagging behind. Luckily enough, Rust supports nearly seamless interaction with the C code! While it is very well possible to link almost any Arduino library to the rust project, I was not able to find any meaningful description of the steps required to do so! My best hit was the rust-arduino-helpers project. Despite that the code quality is, unfortunately, not great (it contains large fragments of commented code and was not updated for a while), it was a great help for me to find the right direction.

The absence of the well documented steps was my motivation to write this tutorial.

Project and Goals

Here is the set of steps we will cover today:

Prepare environment to program Arduino board with Rust.
Create the avr-hal based rust project and blink the led.
Compile Arduino SDK and the third-party library and link it to the rust project.
Generate rust bindings for the Arduino library.
Write the code and run it on your board!

The list of the hardware I've had in my possession for this project is the following:

Arduino Uno board
1602 LCD Display Module with I2C Interface
LED
Linux or Windows PC

What we are going to do is simply try writing a text message to the LCD Display using Rust. In order to do so, we will have to figure out how to link and use the LiquidCrystal-I2C Arduino library in our rust crate. In other words, we would like to do something like this, but in Rust.

Here is the little demonstration of the final project:

As a bonus, we will write a nice configuration file to configure Arduino dependencies to make the setup extensible and reusable.

The source code is available on GitHub. I was able to run it on both Linux and Windows PC. I would be focusing on the Linux (Fedora 35) installation steps in this tutorial, windows users could refer to the corresponding section in the readme.md file.

This article assumes the reader has the basic knowledge about Rust project setup. I also assume the reader has a rust standard development environment (rustup and cargo) configured.

Step 1: Environment setup

Compiler and Arduino IDE

Arduino IDE and Arduino libraries are intended to be used by non-professional programmers and so they are designed to just work out of the box. We will have to gain some understanding of what happens under the hood of them to be able to compile the Arduino code outside of the Arduino IDE.

First all, we would need to download and install the Arduino IDE. I am using version 2.0.1.
Linux users could install it running the following command:

curl -fsSL https://raw.githubusercontent.com/arduino/arduino-cli/master/install.sh | sh

At this point, you can run some Arduino C++ Hello World project to ensure that your board is recognized by your PC and working fine. It is also important, because it would force Arduino IDE to download require tools and libraries.

While you are there, install LiquidCrystal_I2C library to Arduino Libraries folder using Arduino IDE like how you would normally do.

Next, we need to familiarize ourselves with a set of tools used for AVR development:

avrdude is a command-line program for programming AVR chips. It allows uploading compiled sketch to your board.
avr-gcc is a compiler that takes C language high level code and creates a binary source which can be uploaded into an AVR micro controller.
avr-libc is C standard library for use with avr-gcc on Atmel AVR microcontrollers.

These tools come bundled with the Arduino IDE. On my laptop, they are installed in the ~/.arduino15/packages/arduino/tools/ folder. Despite this, I prefer to also install the system-wide copy of them from Fedora repositories to avoid adding the above folder to the %PATH manually:

sudo dnf install avrdude avr-gcc avr-libc

The above step is technically optional, I skipped it on Windows as there is no easy way to the same there.

Ravedude

We could have been just using avrdude to program our board. However since we are planning to develop in rust, ravedude would be a better alternative as we could just configure it as a runner for cargo build tool.

I had to install some dependencies to compile ravedude first:

sudo dnf install systemd-devel pkgconf-pkg-config

Installing ravedude is then as easy as running

cargo install ravedude

I also assume the reader has a rust standard development environment (rustup and cargo) configured.

Bindgen

We are planning to use rust-bindgen project to automatically generate rust bindings based on the C++ library header. We will use bindgen as rust library during the build time, however it require libclang to operate, so we have to install it:

sudo dnf install clang-devel

Cargo-generate

We would like to simply the next step and use cargo-generate tool to create our Arduino project from a template. Somehow (please, do not ask me why) it requires Perl to compile, so we have to do:

sudo dnf install perl
cargo install cargo-generate

Step 2: Project setup

As I've just mentioned, we would create out project using cargo generate command:

cargo generate --git https://github.com/Rahix/avr-hal-template.git

You will have to specify the project name and select the board type. There is an excellent creativcoder's article outlining the process step-by-step in case you would like to do project the setup manually.

Have a look to .cargo/config.toml to understand why we've installed ravedude earlier. The following section:

[target.'cfg(target_arch = "avr")']
runner = "ravedude uno -cb 57600"

passing compiled file to ravedude when you execute cargo run command, so it would be programmed to your board. ravedude would also listen the serial port to print the debug output of your sketch.

Let's update main.rs with a simple program to use the serial port and blink the LED on a pin #13:

use arduino_hal::prelude::*;
use panic_halt as _;

#[arduino_hal::entry]
unsafe fn main() -> ! {
    let dp = arduino_hal::Peripherals::take().unwrap();
    let pins = arduino_hal::pins!(dp);

    let mut serial = arduino_hal::default_serial!(dp, pins, 57600);
    let mut led = pins.d13.into_output();
    ufmt::uwriteln!(&mut serial, "Hello world\r").void_unwrap();

    loop {
        led.toggle();
        arduino_hal::delay_ms(1000);
    }
}

Simply execute

cargo run

and the above code should be running on your board.

If you are having trouble understanding the above code, consider referring to avr-hal documentation and creativcoder's article for more information.

Step 3: Compile and Link Arduino SDK and library

Arduino SDK dependency

Ok, we have a working rust project. Let's connect our I2C display to the Arduino board as explained in the article and try figure out how we can port the C++ example outlined there to rust:

#include <LiquidCrystal_I2C.h>

LiquidCrystal_I2C lcd(0x3F,16,2);  // set the LCD address to 0x3F for a 16 chars and 2 line display

void setup() {
  lcd.init();
  lcd.clear();         
  lcd.backlight();      // Make sure backlight is on

  // Print a message on both lines of the LCD.
  lcd.setCursor(2,0);   //Set cursor to character 2 on line 0
  lcd.print("Hello world!");

  lcd.setCursor(2,1);   //Move cursor to character 2 on line 1
  lcd.print("LCD Tutorial");
}

void loop() {
}

Clearly, we would like to compile LiquidCrystal_I2C, link it to our crate as a dependency and call the same functions from rust.

Ok, should be easy, right? Well, if you just have a standalone C library, compiling and calling it from rust is straightforward. Let's have a closer look at the source code of LiquidCrystal_I2C.cpp:

#include <inttypes.h>
#include <Arduino.h>
#include <Wire.h>

What are they?

Arduino.h is the main include file for the Arduino SDK
Wire.h is TWI/I2C library for Arduino & Wiring provided as part of Arduino SDK
inttypes.h is standard library header file providing the support for width-based integral types.

What does it mean? Well, it means we can't just use LiquidCrystal_I2C alone without compiling Arduino SDK.

Compiling Arduino SDK and the library

Configuring Arduino SDK location

Let's create an empty file named build.rs in the root of our project. This is where we would write steps to compile a link to Arduino dependencies.

First, we should find the location of Arduino SDK and 3rd party LiquidCrystal_I2C library installed earlier.

In my case, Arduino is installed at ~/.arduino15/, and 3rd party library folder is ~/Arduino/libraries/. We could have just hardcoded the above as a constant in our build.rs, but let's try to apply some better engineering principles and make our configuration more reusable! I propose to create a file called arduino.yaml next to the build.rs. We could then use serde_yaml to read it in the build.rs file to avoid making code changes if the location changes in the future:

arduino_home: $HOME/.arduino15
external_libraries_home: $HOME/Arduino/libraries

Now, let's locate the Arduino SDK inside the home folder of Arduino. In my case, it is ~/.arduino15/packages/arduino/hardware/avr/1.8.6/. The path is pretty standard, but the version might change in future, so we can move the version to our yaml file as well.

The Arduino SDK folder contains a set of the subfolders, but we are interested in two of them libraries and variants:

The libraries folder contains the code which can run on any Arduino board. This is where we can find Wire library we need. Nice!
The variants folder definition of the pins specific to the given board. The folder for Arduino UNO is called eightanaloginputs (again, do not ask my why please).

Finally, we would also need C standard library headers (e.g. inttypes.h) provided by the compiler. It is also installed with Arduino. In my case the path is ~/.arduino15/packages/arduino/tools/avr-gcc/7.3.0-atmel3.6.1-arduino7/avr/include/

We can now add more information to our arduino.yaml, specifying the core version, the compiler version, list of Arduino and external libraries to build:

arduino_home: $HOME/.arduino15
external_libraries_home: $HOME/Arduino/libraries
core_version: 1.8.6
variant: eightanaloginputs
avr_gcc_version: 7.3.0-atmel3.6.1-arduino7
arduino_libraries:
  - Wire
external_libraries:
  - LiquidCrystal_I2C

Reading the configuration

We can now read the above file in build.rs. In order to do some add serde_yaml compile time dependency. We would also use envmnt crate to resolve the environment variables mentioned in the file:

[build-dependencies]
envmnt = "0.10.4"
serde = { version = "1.0", features = ["derive"] }
serde_yaml = "0.9"

Then, we can define the Config struct and helper methods to construct the above path in the code

const CONFIG_FILE: &str = "arduino.yaml";

#[derive(Debug, Deserialize)]
struct Config {
    pub arduino_home: String,
    pub external_libraries_home: String,
    pub core_version: String,
    pub variant: String,
    pub avr_gcc_version: String,
    pub arduino_libraries: Vec<String>,
}

impl Config {
    fn arduino_package_path(&self) -> PathBuf {
        let expanded = envmnt::expand(&self.arduino_home, None);
        let arduino_home_path = PathBuf::from(expanded);
        arduino_home_path.join("packages").join("arduino")
    }

    fn core_path(&self) -> PathBuf {
        self.arduino_package_path()
            .join("hardware")
            .join("avr")
            .join(&self.core_version)
    }

    fn avr_gcc_homeavr_gcc_home(&self) -> PathBuf {
        self.arduino_package_path()
            .join("tools")
            .join("avr-gcc")
            .join(&self.avr_gcc_version)
    }

    fn avg_gcc(&self) -> PathBuf {
        self.avr_gcc_home().join("bin").join("avr-gcc")
    }

    fn arduino_core_path(&self) -> PathBuf {
        self.core_path().join("cores").join("arduino")
    }
}

Since we were dealing with path, we also defined the helper avg_gcc method to provide the path to the compiler binary

We can now read this file and print it to console

fn main() {
    println!("cargo:rerun-if-changed={}", CONFIG_FILE);
    let config_string = std::fs::read_to_string(CONFIG_FILE)
        .unwrap_or_else(|e| panic!("Unable to read {} file: {}", CONFIG_FILE, e));
    let config: Config = serde_yaml::from_str(&config_string)
        .unwrap_or_else(|e| panic!("Unable to parse {} file: {}", CONFIG_FILE, e));

    println!("Arduino configuration: {:#?}", config);
}

The following line ensure the project is rebuild each time the yaml file is updated.

println!("cargo:rerun-if-changed={}", CONFIG_FILE);

At this point, we can run cargo build -vv (very verbose) and be able to see the parse config printed.

Headers and sources

Ok, we know where our dependencies are. We will need to pass them to avr-gcc compiler soon. There are 3 types of files we need to take care of:

Header files .h
C source code .c
C++ source code .cpp

Headers are the easiest to deal with. We would just pass it to the compiler using -I flag. We need 4 header folders to be included:

Arduino variant-specific header(s)
C standard library
Arduino libraries
External libraries

Let's implement the helper methods to get the paths of them:

impl Config {
    fn arduino_include_dirs(&self) -> Vec<PathBuf> {
        let variant_path = self.core_path().join("variants").join(&self.variant);
        let avr_gcc_include_path = self.avr_gcc_home().join("avr").join("include");
        vec![self.arduino_core_path(), variant_path, avr_gcc_include_path]
    }

    fn arduino_libraries_path(&self) -> Vec<PathBuf> {
        let library_root = self.core_path().join("libraries");
        let mut result = vec![];
        for library in &self.arduino_libraries {
            result.push(library_root.join(library).join("src"))
        }
        result
    }

    fn external_libraries_path(&self) -> Vec<PathBuf> {
        let expanded = envmnt::expand(&self.external_libraries_home, None);
        let external_library_root = PathBuf::from(expanded);
        let mut result = vec![];
        for library in &self.external_libraries {
            result.push(external_library_root.join(library))
        }
        result
    }

    fn include_dirs(&self) -> Vec<PathBuf> {
        let mut result = self.arduino_include_dirs();
        result.extend(self.arduino_libraries_path());
        result.extend(self.external_libraries_path());
        result
    }

}

C and C++ files would be passed to the compiler as an input one by one. The will need to be compiled with a slightly different set of the compiler flags, so let's define separate helpers to get the list of them:

impl Config {
    fn project_files(&self, patten: &str) -> Vec<PathBuf> {
        let mut result =
            files_in_folder(self.arduino_core_path().to_string_lossy().as_ref(), patten);
        let mut libraries = self.arduino_libraries_path();
        libraries.extend(self.external_libraries_path());

        let pattern = format!("**/{}", patten);
        for library in libraries {
            let lib_sources = files_in_folder(library.to_string_lossy().as_ref(), &pattern);
            result.extend(lib_sources);
        }

        result
    }

    fn cpp_files(&self) -> Vec<PathBuf> {
        self.project_files("*.cpp")
    }

    fn c_files(&self) -> Vec<PathBuf> {
        self.project_files("*.c")
    }
}

fn files_in_folder(folder: &str, pattern: &str) -> Vec<PathBuf> {
    let cpp_pattern = format!("{}/{}", folder, pattern);
    let mut results = vec![];
    for cpp_file in glob(&cpp_pattern).unwrap() {
        let file = cpp_file.unwrap();
        if !file.ends_with("main.cpp") {
            results.push(file);
        }
    }
    results
}

Here we use the glob create to look for the files recursively, so we need to also add it to Cargo.toml as a build dependency:

glob = "0.3"

Compiler flags and definitions

In order to compile for Arduino UNO, we would need to pass some board specific flags to the compiler, in paricular:

-DARDUINO=10807 -DF_CPU: 16000000L -DARDUINO_AVR_UNO=1 -DARDUINO_ARCH_AVR -mmcu=atmega328p

As they are board specific, let's move the definition of them to arduino.yaml as well:

definitions:
  ARDUINO: '10807'
  F_CPU: 16000000L
  ARDUINO_AVR_UNO: '1'
  ARDUINO_ARCH_AVR: '1'
flags:
  - '-mmcu=atmega328p'

We will also have to add corresponding fields to a Config struct

#[derive(Debug, Deserialize)]
struct Config {
    // Existing fields here
    pub definitions: HashMap<String, String>,
    pub flags: Vec<String>,
}

Compilation and linking

While it is technically possible to construct the command line to invoke compiler manually using the CC crate is a much better option. Let's add the CC dependency to Cargo.toml:

[build-dependencies]
cc = "1.0.74"

As mentioned above, C and C++ code needs be compiled with a slightly different set of flags. Let's define a helper function to define the common part of the configuration

fn configure_arduino(config: &Config) -> Build {
    let mut builder = Build::new();
    for (k, v) in &config.definitions {
        builder.define(k, v.as_str());
    }
    for flag in &config.flags {
        builder.flag(flag);
    }
    builder
        .compiler(config.avg_gcc())
        .flag("-Os")
        .cpp_set_stdlib(None)
        .flag("-fno-exceptions")
        .flag("-ffunction-sections")
        .flag("-fdata-sections");

    for include_dir in config.include_dirs() {
        builder.include(include_dir);
    }
    builder
}

Here we create CC provided builder and pass compile flags, definition and include folders.

We can then use configured build to compile C/C++ parts of Arduino standard library:

pub fn add_source_file(builder: &mut Build, files: Vec<PathBuf>) {
    for file in files {
        println!("cargo:rerun-if-changed={}", file.to_string_lossy());
        builder.file(file);
    }
}

fn compile_arduino(config: &Config) {
    let mut builder = configure_arduino(&config);
    builder
        .cpp(true)
        .flag("-std=gnu++11")
        .flag("-fpermissive")
        .flag("-fno-threadsafe-statics");
    add_source_file(&mut builder, config.cpp_files());
    builder.compile("libarduino_c++.a");


    let mut builder = configure_arduino(&config);
    builder.flag("-std=gnu11");
    add_source_file(&mut builder, config.c_files());
    builder.compile("libarduino_c.a");

    println!("cargo:rustc-link-lib=static=arduino_c++");
    println!("cargo:rustc-link-lib=static=arduino_c");
}

We simply compile each C and CPP file we can find together with the only exception of the main.cpp as the main method is defined in rust. CC crate will call avr-gcc and produce to object files: libarduino_c++.a and libarduino_c.a.

We then instruct cargo to statically link rust code with them by printing

cargo:rustc-link-lib=static=arduino_c++
cargo:rustc-link-lib=static=arduino_c

lines to the standard output.

Generate rust bindings

So far we've compiled the required dependencies with our rust project. But running cargo run still does nothing, but blinks the LED. In order to interact with the display, we need to write code to do so. But how could we call a C++ function defined in liquidcrystal_i2c.h from rust?

This is where bingen is coming to help. Bingen takes C//C++ header files as an input and generates rust definitions of the functions and types provided by them. Let's add it to our Cargo.toml as well:

[build-dependencies]
bindgen = "0.61"

First step is to define the headers files to pass to bindgen. We can just implement a small helper method to find them in the external libraries folder:

impl Config {
    fn bindgen_headers(&self) -> Vec<PathBuf> {
        let mut result = vec![];
        for library in self.external_libraries_path() {
            let lib_headers = files_in_folder(library.to_string_lossy().as_ref(), "*.h");
            result.extend(lib_headers);
        }
        result
    }
}

Next, we need to define the bingen configuration:

fn configure_bindgen_for_arduino(config: &Config) -> Builder {
    let mut builder = Builder::default();
    for (k, v) in &config.definitions {
        builder = builder.clang_arg(&format!("-D{}={}", k, v));
    }
    for flag in &config.flags {
        builder = builder.clang_arg(flag);
    }
    builder = builder
        .clang_args(&["-x", "c++", "-std=gnu++11"])
        .use_core()
        .layout_tests(false)
        .parse_callbacks(Box::new(bindgen::CargoCallbacks));

    for include_dir in config.include_dirs() {
        builder = builder.clang_arg(&format!("-I{}", include_dir.to_string_lossy()));
    }
    for header in config.bindgen_headers() {
        builder = builder.header(header.to_string_lossy());
    }
    builder
}

Note that we need to pass the same set of compiler flags and definitions to bingen as we passed to avr-gcc earlier.

Then, we can call generate method to generate the bindings and write them to src/arduino.rs file:

fn generate_bindings(config: &Config) {
    let bindings: Bindings = configure_bindgen_for_arduino(&config)
        .generate()
        .expect("Unable to generate bindings");
    let project_root = PathBuf::from(env!("CARGO_MANIFEST_DIR"))
        .join("src")
        .join("arduino.rs");
    bindings
        .write_to_file(project_root)
        .expect("Couldn't write bindings!");
}

We can now open src/arduino.rs and see generated code. A lot of generated code! This is because by default bingen goes over each header file recursively and generates bindings for every type and method. As we do not need most of them, we can configure allow and block list to exclude useless parts.

To do so, we can add a new section to arduino.yaml:

bindgen_lists:
  allowlist_function:
    - LiquidCrystal_I2C.*
  allowlist_type:
    - LiquidCrystal_I2C.*
  blocklist_function:
    - Print.*
    - String.*
  blocklist_type:
    - Print.*
    - String.*

We can then modify the config object:

#[derive(Debug, Deserialize)]
struct BindgenLists {
    pub allowlist_function: Vec<String>,
    pub allowlist_type: Vec<String>,
    pub blocklist_function: Vec<String>,
    pub blocklist_type: Vec<String>,
}

#[derive(Debug, Deserialize)]
struct Config {
    // Existing fields
    pub bindgen_lists: BindgenLists,
}

and configure_bindgen_for_arduino function to make use of them

fn configure_bindgen_for_arduino(config: &Config) -> Builder {
    // Existing code

    for item in &config.bindgen_lists.allowlist_function {
        builder = builder.allowlist_function(item);
    }
    for item in &config.bindgen_lists.allowlist_type {
        builder = builder.allowlist_type(item);
    }
    for item in &config.bindgen_lists.blocklist_function {
        builder = builder.blocklist_function(item);
    }
    for item in &config.bindgen_lists.blocklist_type {
        builder = builder.blocklist_type(item);
    }
    builder
}

arduino.rs looks so much nicer now!

Step 5: Writing and running the code

Have you ever wondered why there is no main method in the Arduino sketches? Indeed, the standard template of the Arduino file is the following:

void setup() {
  // put your setup code here, to run once:

}

void loop() {
  // put your main code here, to run repeatedly:
}

Remember the main.cpp file we've excluded in the step 3? Let's look inside (simplified code):

#include <Arduino.h>

int main(void)
{
        init();
        setup();

        for (;;) {
                loop();
                if (serialEventRun) serialEventRun();
        }
        return 0;
}

Looks like no magic at all! It just calls setup() and then loop method in the loop. We do not care about setup and loop in rust, but what is the init call?! It turns out that it is Arduino SDK provided function to initialize the board. We would need to call it in rust as well before we start using any Arduino library. We could have just generated it using bindgen, but since its signature is so simple (no arguments) we can just define it in place:

extern "C" {
    fn init();
}

Now we are ready to modify our main.rs with some code to initialize our display and print some text:

#[arduino_hal::entry]
unsafe fn main() -> ! {
    init();

    let dp = arduino_hal::Peripherals::take().unwrap();
    let pins = arduino_hal::pins!(dp);

    let mut serial = arduino_hal::default_serial!(dp, pins, 57600);

    let mut led = pins.d13.into_output();

    ufmt::uwriteln!(&mut serial, "starting on {}\r", 0x27).void_unwrap();

    let mut lcd = LiquidCrystal_I2C::new(0x27, 16, 2);

    let ferris = &[
        0b01010u8, 0b01010u8, 0b00000u8, 0b00100u8, 0b10101u8, 0b10101u8, 0b11111u8, 0b10101u8,
    ];

    lcd.begin(16, 2, 0);
    lcd.init();
    lcd.backlight();

    lcd.clear();
    lcd.printstr("Good morning\0".as_ptr().cast());
    lcd.setCursor(0, 1);
    lcd.printstr("from Rust!!\0".as_ptr().cast());

    lcd.createChar(0, ferris.as_ptr() as *mut _);
    lcd.setCursor(12, 1);

    LiquidCrystal_I2C_write((&mut lcd as *mut LiquidCrystal_I2C).cast(), 0);

    loop {
        led.toggle();
        arduino_hal::delay_ms(1000);
    }
}

Here we combine the arduino_hal method and the methods provided by LiquidCrystal_I2C library.
It is now time to run cargo run and see the message on the display! Well done!

Summary

I really hope you've learned something by reading this article! We covered the following topics today:

Rust Arduino Environment setup
Structure of Arduino SDK
Compilation Arduino library, linking it to rust crate and generation of the rust definitions for C++ methods.

If the article was useful for you, please put a reaction and start the GitHub repository.

I am also happy to hear a feedback about the arduino.yaml DSL developed as part of this article. Would it be useful to move it into separate library to be used in the build time? Is there a better way to do the same? Please share your opinion in the comments!

6 things you can do with the Cow 🐄 in Rust 🦀

Konstantin Grechishchev — Sun, 02 Oct 2022 18:37:02 +0000

The Cow type is a mystery even for some intermediate-level Rust developers. Despite being defined as a simple two-variant enum

pub enum Cow<'a, B> 
where
    B: 'a + ToOwned + ?Sized, 
{
    Borrowed(&'a B),
    Owned(<B as ToOwned>::Owned),
}

, it challenges the developers to understand the ownership and lifetimes, as well yet another mystery Borrow and ToOwned traits. As a result, programmers avoid using Cow, which often leads to extra memory allocations (which are not cheap) and less efficient software.

What are the situations when you might consider using Cow? Why does it have such a strange name? Let's try to find some answers today!

A function rarely modifying the data

Let's start with the most common and straightforward use case for Cow type. It is a good illustration of the situation when most developers (including me!) encounter the Cow for the first time.

Consider the following function accepting and modifying the borrowed data (in this case &str):

fn remove_whitespaces(s: &str) -> String {
    s.to_string().replace(' ', "")
}

fn main() {
    let value = remove_whitespaces("Hello world!");
    println!("{}", value);
}

As you can see, it does nothing but removes all white spaces from the string. What is wrong with it? What if in 99.9% of calls the string contains no white spaces? Or slight modification of the method when spaces should be removed based on some other condition.

In such cases, we could avoid to_string() call and creation an unnecessary copy of the string. However, if we are to implement such logic, we can use neither String no &str type: the first one forces the memory allocation and the last is immutable.

This is the moment when Cow plays its role. We can return Cow::Owned when the string is modified and Cow::Borrowed(s) otherwise:

use std::borrow::Cow;

fn remove_whitespaces(s: &str) -> Cow<str> {
    if s.contains(' ') {
        Cow::Owned(s.to_string().replace(' ', ""))
    } else {
        Cow::Borrowed(s)
    }
}

fn main() {
    let value = remove_whitespaces("Hello world!");
    println!("{}", value);
}

The nice thing about Cow<str> is that it could always be dereferenced into &str later or converted into String by calling into_owned. The into_owned only allocates the memory if the string was originally borrowed.

A struct optionally owning the data

We often need to store references inside the structs. If we have no such need, you are likely ending up cloning data unnecessarily.

Consider

struct User<'a> {
    first_name: &'a str,
    last_name: &'a str,
}

Would not it be nice to be able to create a user with a static lifetime User<'static> owning its own data? This way we could implement the method do_something_with_user(user) accepting the same struct regardless of whether the data is cloned or borrowed. Unfortunately, the only way to create User<'static> is by using &'static str.

But what if we have a String? We can solve the problem by storing not &'a str, but Cow<'a, str> inside the struct:

use std::borrow::Cow;

struct User<'a> {
    first_name: Cow<'a, str>,
    last_name: Cow<'a, str>,
}

This way, we can construct both owned and borrowed version of the User struct:

impl<'a> User<'a> {

    pub fn new_owned(first_name: String, last_name: String) -> User<'static> {
        User {
            first_name: Cow::Owned(first_name),
            last_name: Cow::Owned(last_name),
        }
    }

    pub fn new_borrowed(first_name: &'a str, last_name: &'a str) -> Self {
        Self {
            first_name: Cow::Borrowed(first_name),
            last_name: Cow::Borrowed(last_name),
        }
    }


    pub fn first_name(&self) -> &str {
        &self.first_name
    }
    pub fn last_name(&self) -> &str {
        &self.last_name
    }
}


fn main() {
    // Static lifetime as it owns the data
    let user: User<'static> = User::new_owned("James".to_owned(), "Bond".to_owned());
    println!("Name: {} {}", user.first_name, user.last_name);

    // Static lifetime as it borrows 'static data
    let user: User<'static> = User::new_borrowed("Felix", "Leiter");
    println!("Name: {} {}", user.first_name, user.last_name);

    let first_name = "Eve".to_owned();
    let last_name = "Moneypenny".to_owned();

    // Non-static lifetime as it borrows the data
    let user= User::new_borrowed(&first_name, &last_name);
    println!("Name: {} {}", user.first_name, user.last_name);
}

A clone on write struct

The examples above illustrate only one side of the Cow: the ability to represent the data which borrowed or owned status is figured in not in compile time, but in runtime.

But why was it named Cow then? Cow stands for copy on write. The examples above illustrate only one side of the Cow: the ability to represent the data which borrowed or owned status is figured in not in compile time, but in runtime.

The true power of Cow comes with to_mut method. If the Cow is owned, it simply returns the pointer to the underlying data, however if it is borrowed, the data is first cloned to the owned from.

It allows you to implement an interface based on the structures, lazily storing the references to the data and cloning it only if (and for the first time) the mutation is required.

Consider the code which receives the buffer of data in the form of &[u8]. We would like to pass it over some logic, conditionally modifying the data (e.g. appending a few bytes) and consume the buffer as &[u8]. Similar to the example above, we can't keep the buffer as &[u8] as we won't be able to modify it, but converting it to Vec would lead to the copy being made every time.

We can achieve the required behavior by representing the data as Cow<[u8]>:

use std::borrow::Cow;

struct LazyBuffer<'a> {
    data: Cow<'a, [u8]>,
}

impl<'a> LazyBuffer<'a> {

    pub fn new(data: &'a[u8]) -> Self {
        Self {
            data: Cow::Borrowed(data),
        }
    }

    pub fn data(&self) -> &[u8] {
        &self.data
    }

    pub fn append(&mut self, data: &[u8]) {
        self.data.to_mut().extend(data)
    }
}

This way we can pass borrowed data around without cloning up until the moment when (and if) we need to modify it:

fn main() {
    let data = vec![0u8; 10];

    // No memory copied yet
    let mut buffer = LazyBuffer::new(&data);
    println!("{:?}", buffer.data());

    // The data is cloned
    buffer.append(&[1, 2, 3]);
    println!("{:?}", buffer.data());

    // The data is not cloned on further attempts
    buffer.append(&[4, 5, 6]);
    println!("{:?}", buffer.data());
}

Keep your own type inside it

Most likely you would end up using Cow<str> or Cow<[u8]>, but there are cases when you might want to store your own type inside it.

In order to use the Cow with a user defined type, you would need to implemented owned and borrowed version of it. The owned and borrowed version must by tied together by the following trait boundaries:

Owned version should implement the Borrow trait to produced a reference to the borrowed type
The borrowed version should implement ToOwned trait to produce the owned type.

Implementation of the the Borrow trait is tricky and often unsafe. Indeed, in order for the fn borrow(&self) -> &Borrowed; function to return a reference to Borrowed typed, this reference should either be stored inside &self or produced unsafely.

The above often means that the borrowed type is an unsized (also know as dynamically sized type. Their size is not known at compile time, so they can only exist as a pointer or a reference.

Have you ever wondered why we use &str everywhere and nearly never use str? You can't find the definition of the str type in the standard library, it is a primitive type (part of the language). Since str is a dynamically sized type, it can only be instantiated through a pointer type, such as &str. Trait object dyn T is another example of the dynamically sized type.

Imagine you would like to implement your own version of String and str type.

use std::borrow::{Borrow, Cow};
use std::ops::Deref;

#[derive(Debug)]
struct MyString {
    data: String
}

#[derive(Debug)]
#[repr(transparent)]
struct MyStr {
    data: str,
}

Since str is unsized, so is MyStr. You can then bound MyString and MyStr same way as String and str are bounded:

impl Borrow<MyStr> for MyString {
    fn borrow(&self) -> &MyStr {
        unsafe { &*(self.data.as_str() as *const str as *const MyStr) }
    }
}

impl ToOwned for MyStr {
    type Owned = MyString;

    fn to_owned(&self) -> MyString {
        MyString {
            data: self.data.to_owned()
        }
    }
}

The unsafe pointer case inside the borrow method has probably drawn your attention. While looking scary, it is the usual pattern in the standard library (have a look at e.g. Path type implementation). Since MyStr is a single field struct annotated with #[repr(transparent)], it is guarantied to have zero cost compile-time representation. It means we can safely cast the valid pointer to str to the pointer to MyStr and then convert it to a reference.

We could also optionally implement the Deref trait for convenience and store MyString and MyStr into cow as well, taking all advantages provided.

impl Deref for MyString {
    type Target = MyStr;

    fn deref(&self) -> &Self::Target {
        self.borrow()
    }
}


fn main()  {
    let data = MyString { data: "Hello world".to_owned() };

    let borrowed_cow: Cow<'_, MyStr> = Cow::Borrowed(&data);
    println!("{:?}", borrowed_cow);

    let owned_cow: Cow<'_, MyStr> = Cow::Owned(data);
    println!("{:?}", owned_cow);
}

Borrow the type as dyn Trait

As mentioned above, the trait object is another example of dynamically sized type. Somewhat surprising, we can use Cow in a similar manner to implement dynamic dispatch, similarly to Box<dyn Trait> and Arc<dyn Trait>.

Consider the following trait and struct implementations:

use std::borrow::{Borrow, Cow};
use std::fmt::Debug;
use std::ops::Deref;

trait MyTrait: Debug {
    fn data(&self) -> &str;
}

#[derive(Debug)]
struct MyString {
    data: String
}

impl MyTrait for MyString {
    fn data(&self) -> &str {
        &self.data
    }
}

As MyString implements MyTrait, we can borrow &MyString as &dyn MyTrait:

impl<'a> Borrow<dyn MyTrait + 'a> for MyString {
    fn borrow(&self) -> &(dyn MyTrait + 'a) {
        self
    }
}

We can also convert any MyTrait implementation to MyString:

impl ToOwned for dyn MyTrait {
    type Owned = MyString;

    fn to_owned(&self) -> MyString {
        MyString {
            data: self.data().to_owned()
        }
    }
}

Since we have defined Borrow and ToOwned, we can now put MyString into Cow<dyn MyTrait>:

fn main()  {
    let data = MyString { data: "Hello world".to_owned() };

    let borrowed_cow: Cow<'_, dyn MyTrait> = Cow::Borrowed(&data);
    println!("{:?}", borrowed_cow);

    let owned_cow: Cow<'_, dyn MyTrait> = Cow::Owned(data);
    println!("{:?}", owned_cow);
}

The above could be useful to implement, e.g. the mutable vector of the trait objects:

fn main()  {
    let data = MyString { data: "Hello world".to_owned() };
    let cow1: Cow<'_, dyn MyTrait> = Cow::Borrowed(&data);

    let data = MyString { data: "Hello world".to_owned() };
    let cow2: Cow<'_, dyn MyTrait> = Cow::Owned(data);

    let mut vector: Vec<Cow<'_, dyn MyTrait>> = vec![cow1, cow2];
}

Implement safe wrapper over FFI type

The above MyString example is exciting but somewhat artificial. Let's consider the real-life pattern when you would like to store your own type inside the Cow.

Imagine you are using the C library in your rust project. Let's say you receive a buffer of data from the C code in the form of the pointer *const u8 and length usize. Say you would like to pass the data around the layer of the rust logic, possibly modifying it (does it trigger you to think about Cow?). Finally, you might want to access the data (modified or not) in rust as &[u8] or pass into another C function as the pointer *const u8 and length usize.(Here we assume that this C function would not release the memory. If this assumption surprises you, consider reading 7 ways to pass a string between 🦀 Rust and C article)

As we would like to avoid cloning the data unnecessarily, we would represent the buffer as the following struct:

use std::borrow::{Borrow, Cow};
use std::fmt::{Debug, Formatter};
use std::ops::Deref;

struct NativeBuffer {
    pub ptr: *const u8,
    pub len: usize
}

This struct does not own its data, it borrows it from the C pointer with an unknown lifetime.

For convince only, we can implement the traits to access the buffer as &[u8] slice and print it:

impl Borrow<[u8]> for NativeBuffer {
    fn borrow(&self) -> &[u8] {
        unsafe {
            std::slice::from_raw_parts(self.ptr, self.len)
        }
    }
}

impl Deref for NativeBuffer {
    type Target = [u8];

    fn deref(&self) -> &Self::Target {
        self.borrow()
    }
}

impl Debug for NativeBuffer {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        let data: &[u8] = self.borrow();
        write!(f, "NativeBuffer {{ data: {:?}, len: {} }}", data, self.len)
    }
}

In order to store the NativeBuffer in the Cow we first need to define the owning version of it:

#[derive(Debug)]
struct OwnedBuffer {
    owned_data: Vec<u8>,
    native_proxy: NativeBuffer,
}

impl ToOwned for NativeBuffer {
    type Owned = OwnedBuffer;

    fn to_owned(&self) -> OwnedBuffer {
        let slice: &[u8] = self.borrow();
        let owned_data = slice.to_vec();
        let native_proxy = NativeBuffer {
            ptr: owned_data.as_ptr(),
            len: owned_data.len()
        };
        OwnedBuffer {
            owned_data,
            native_proxy,
        }
    }
}

The trick is to borrow the data as a slice and convert it to Vec. We also need to store the NativeBuffer inside OwnedBuffer. It contains a pointer to the data inside the vector and the length of it, so we could implement the Borrow trait:

impl Borrow<NativeBuffer> for OwnedBuffer {
    fn borrow(&self) -> &NativeBuffer {
        &self.native_proxy
    }
}

We can now define the method to mutate the data:

impl OwnedBuffer {

    pub fn append(&mut self, data: &[u8]) {
        self.owned_data.extend(data);
        self.native_proxy = NativeBuffer {
            ptr: self.owned_data.as_ptr(),
            len: self.owned_data.len()
        };
    }
}

It is important to ensure to keep the native buffer pointers up to date.

We can finally put our borrowed buffer in the Cow and implement the conditional mutation logic, for example:

fn main() {
    // Simulates the data coming across FFI (from C)
    let data = vec![1, 2, 3];
    let ptr = data.as_ptr();
    let len = data.len();

    let native_buffer = NativeBuffer { ptr, len};
    let mut buffer = Cow::Borrowed(&native_buffer);
    // NativeBuffer { data: [1, 2, 3], len: 3 }
    println!("{:?}", buffer);

    // No data cloned
    assert_eq!(buffer.ptr, ptr);
    assert_eq!(buffer.len, len);

    if buffer.len > 1 {
        buffer.to_mut().append(&[4, 5, 6]);
        // OwnedBuffer { owned_data: [1, 2, 3, 4, 5, 6], native_proxy: NativeBuffer { data: [1, 2, 3, 4, 5, 6], len: 6 } }
        println!("{:?}", buffer);

        // Data is cloned
        assert_ne!(buffer.ptr, ptr);
        assert_eq!(buffer.len, len + 3);
    }

    let slice: &[u8] = &buffer;
    // [1, 2, 3, 4, 5, 6]
    println!("{:?}", slice);
}

The buffer is only cloned if the length of it is bigger than 1.

Summary

I sincerely hope that this post helped to demystify the Cow type and increase its adoption among the rust community! If you like the article, please put your reaction up and consider reading my other posts!

Writing a new programming language. Part IV: Boolean expressions and if statements

Konstantin Grechishchev — Thu, 18 Aug 2022 21:40:00 +0000

It was pleasing to see the number of reactions and reads on the last part of the tutorial! As promised, I am publishing part IV, where we will look into boolean type support and more complex programs with if statements!

Goal for today

We have two goals for today:

Extend LR-language to support boolean type as well as boolean operations, such as <, <=, >, >=, ==, !=, &&, || and !.
Add the support of the if statements. We would like to be able to run the following program as the result of today's excise:

{
    let pi: Float = 3.14;
    let r: Int = 5;
    let square: Float = 2 * pi * r * r;
    let value: String = "The square of the circle with the r = " + r + " is " + square + ".";
    if square > 100.0 && square <= 300.0 {
        value = value + " It is > 100.";
        if square <= 200.0 {
            value = value + " It is <= 200.";
        } else {
            value = value + " It is > 200.";
        }
    } else {
        value = value + " It is <= 100.";
    }
}

Let's start!

Boolean type and operations

Boolean expressions are required to implement conditions and loops (coming soon!). There are a few main challenges we have to address to support boolean logic in LR-language:

Introduce the boolean type itself
Support parsing, representation in the syntax tree, and execution of a decent amount of boolean operations (see above)
Ensure we respect the expression precedence rules between among operations and existing arithmetical operations. For example, for expression 2 + 2 == 4 && 5 > 2 * 4, we need to ensure to compute * and + first, follow with == and > and execute conjunction as the last step.

Despite it looking like a lot of work, I'll try not to spend a lot of time on it. My main reason is that boolean implementation is just a bit more complex version of the work we've done in parts II and III of this tutorial. I will only cover the main ideas behind the implementation to help you to navigate through the code on your own. You can see all the changes required to be made in this commit.

Boolean type

Adding the new type is no different compared to the work we've done last time. We just have to do the following steps:

Make changes to Value and Type enums to have a new variant for the type called Value::Bool and Type::Bool.
Modify the grammar to recognize true and false terminals and boolean literals and add the

BoolLiteral => Box::new(Expr::Constant(Value::Bool(<>)))

line to make use of them in expressions.

Make changes to existing implementations of the Add, Sub, Mul and Div traits to support Value::Bool variant. Lucky it is not a lot of effort as most of the operations are not defined for the boolean types, except probably a concatenation with a string.

Expressions

We can continue with parsing and execution of the operations once the type is defined. It is important to define the operator precedence correctly. We are not going to reinvent the wheel and will just use the same precedence used in rust:

The ! operator is the top priority
After that, we need to take care of existing math operations
Next, we evaluate comparison operations <, <=, >, >=, ==, !=
Finally, we have conjunction operator (and) && followed by disjunction (or) ||.

Negation operation

Here is the first real challenge. Negation operator ! accepts only one operand and so far we can only represent the expressions containing two operands and an operation between them! In order to overcome it, we rename the existing Opcode struct to BinaryOpcode and introduce a new one:

#[derive(PartialEq, Eq, Hash, Debug, Clone, Copy)]
pub enum UnaryOpcode {
    Not,
}

We can then make the changes to Expr enum to represent both unary and binary operations:

pub enum Expr {
    Constant(Value),
    Identifier(String),
    BinaryOp(Box<Expr>, BinaryOpcode, Box<Expr>),
    UnaryOp(UnaryOpcode, Box<Expr>),
}

We are now forced to introduce the new match branch to the evalutate_expression function in order to make the code to compile after the above change:

Expr::UnaryOp(op, exp) => {
    let result = match op {
        UnaryOpcode::Not => !evalutate_expression(frame, exp)?,
    };
    result.map_err(|e| ExpressionError::OperationError(expr.to_string(), e))
}

Note that we apply the ! operator to Value struct here. Rust will only allow us to do so if we implement the Not trait for it:

impl Not for Value {
    type Output = Result<Value, OperationError>;

    fn not(self) -> Self::Output {
        match self {
            Value::Int(v) => Ok(Value::Int(!v)),
            Value::Float(_) => unary_error!(Not, Float),
            Value::String(_) => unary_error!(Not, String),
            Value::Bool(v) => Ok(Value::Bool(!v)),
        }
    }
}

As a bonus, we've made ! to work as a bitwise negation for Int type. The unary_error is a tiny helper macro to return an error.

Finally, we modify our grammar to be able to parse ! unary operation:

UnaryResult: Box<Expr> = {
    UnaryOp Term => Box::new(Expr::UnaryOp(<>)),
    Term,
};

UnaryOp: UnaryOpcode = {
    "!" => UnaryOpcode::Not,
}

Comparison and logical operations

We are going to apply the same trick as in part II to implement the operator precedence correctly. As a reminder, the idea is to avoid the necessity to deal with the ordering in runtime and instead take care of it at the phase of parsing.

First, let's rename existing Expr non-terminal into Sum to better reflect the meaning of it. We would then apply the following induction rules:

The result of comparison is either just a single Sum or two Sum with a compassion operator in between
The conjunction is either just a single Comparison or a conjunction followed by && and followed by Comparison.
Finally, the disjunction is either just a single Conjunction or a disjunction followed by || and followed by Conjunction.

This is how the AST for 1 + 2 == 3 && 4 < 5 * 6 expression could be visualized as graph:

The above idea could be expressed in the formar grammar in the following way:

pub Expr: Box<Expr> = {
    Disjunction
}

Disjunction: Box<Expr> = {
    Disjunction DisjOp Conjunction => Box::new(Expr::BinaryOp(<>)),
    Conjunction,
};

DisjOp: BinaryOpcode = {
    "||" => BinaryOpcode::Disj,
}

Conjunction: Box<Expr> = {
    Conjunction ConjOp Comparison => Box::new(Expr::BinaryOp(<>)),
    Comparison,
};

ConjOp: BinaryOpcode = {
    "&&" => BinaryOpcode::Conj,
}

Comparison: Box<Expr> = {
    Summ CompareOp Summ => Box::new(Expr::BinaryOp(<>)),
    Summ,
};

CompareOp: BinaryOpcode = {
    "==" => BinaryOpcode::Equals,
    "!=" => BinaryOpcode::NotEquals,
    "<" => BinaryOpcode::Lower,
    ">" => BinaryOpcode::Greater,
    "<=" => BinaryOpcode::LowerEquals,
    ">=" => BinaryOpcode::GreaterEquals,
}

The reason this grammar enforces the construction of the above graph is that to produce, for example, Comparison we first produce two Summ involved. This way, the Expr for Comparison would be applied to the result of the Sum expressions evaluation as operands.

We are able to parse new expressions now, but not yet able to evaluate them. You might expect to see implementations of a few other rust traits (like PartialEq) to define required operations, however there are a few problems with this approach. First, rust does not allow to redefine && and || operations. Second, unlike Add, Sub, Mul and Div traits, the PartialEq does not allow to use Result as a return type. In other words, PartialEq expects the comparison not to fail, which is not true for our case.

Luckily enough, we have no need to implement the traits! We can just define functions for required operations and called them instead in the evalutate_expression method:

BinaryOpcode::Conj => conjunction(value_1, value_2),
BinaryOpcode::Disj => disjunction(value_1, value_2),
BinaryOpcode::Equals => equals(value_1, value_2),
BinaryOpcode::NotEquals => not_equals(value_1, value_2),
BinaryOpcode::Greater => greater(value_1, value_2),
BinaryOpcode::GreaterEquals => greater_equals(value_1, value_2),
BinaryOpcode::Lower => lower(value_1, value_2),
BinaryOpcode::LowerEquals => lower_equals(value_1, value_2),

To keep this tutorial short, I avoid providing the implementation of the above functions here. You can find it in the operations/logical.rs file in this commit.

Nested code blocks

Before we jump into the implementation of the condition operator, we have to solve another problem with our code. Do you remember an optional parent: Option<Box<Frame>> field inside the Frame struct which we've planned for the parent frame variables lookup? So far we never had a need to support nested frames and never set it to Some. Let's fix it!

In order to do so, we introduce a new structure called Block and consider the block as one variant of the statement enum:

Statement: Statement = {
    "let" <Identifier> ":" <Type> "=" <Expr> ";" => Statement::new_definition(<>),
    <Identifier> "=" <Expr> ";" => Statement::new_assignment(<>),
    Block => Statement::new_block(<>)
};

Block: Block = {
    "{" <Statements> "}" => Block::new_statements(<>),
}

The execute_statement match should be now extended to have a new branch:

Statement::Block(block) => {
    frame = execute_block(frame, block)?;
    Ok(frame)
}

To execute the block, we first create a new child frame with the current frame as a parent, execute the statements of the block using a new frame and get the (possibly modified) parent frame back:

pub fn execute_block(frame: Frame, block: &Block) -> Result<Frame, RuntimeError> {
    match block {
        Block::StatementsBlock(statements) => {
            let mut block_frame = Frame::new(Box::new(frame));
            block_frame = execute_statements(block_frame, statements)?;
            Ok(*block_frame.take_parent().unwrap())
        }
    }
}

If Statements

It is time to implement the main concept of today's tutorial! We are going to support the following syntax:

if expression { statements } else { statements }

The { and } are mandatory (for simplicity) and the else branch is optional.

The representation of the above using the grammar is the following:

Block: Block = {
    "{" <Statements> "}" => Block::new_statements(<>),
    "if" <Expr> "{" <Statements> "}" => Block::new_condition(<>, None),
    "if" <exp:Expr> "{" <thn:Statements> "}" "else" "{" <els:Statements> "}" => Block::new_condition(exp, thn, Some(els)),
}

Here is the final code of the Block struct:

pub enum Block {
    StatementsBlock(Vec<Statement>),
    Condition {
        expression: Box<Expr>,
        then_block: Vec<Statement>,
        else_block: Option<Vec<Statement>>,
    },
}

Since we've added a new Condition variant, we need to update execute_block again:

pub fn execute_block(frame: Frame, block: &Block) -> Result<Frame, RuntimeError> {
    match block {
        Block::StatementsBlock(statements) => {
            // Existing code
        }
        Block::Condition {
            expression,
            then_block,
            else_block,
        } => execute_condition(frame, expression.as_ref(), then_block, else_block),
    }
}

The main logic is hidden in the execute_condition method:

pub fn execute_condition(
    mut frame: Frame,
    expr: &Expr,
    then_block: &[Statement],
    else_block: &Option<Vec<Statement>>,
) -> Result<Frame, RuntimeError> {
    let value = evalutate_expression(&mut frame, expr)?;
    if let Value::Bool(value) = value {
        let mut block_frame = Frame::new(Box::new(frame));
        if value {
            block_frame = execute_statements(block_frame, then_block)?;
        } else if let Some(else_block) = else_block {
            block_frame = execute_statements(block_frame, else_block)?;
        }
        Ok(*block_frame.take_parent().unwrap())
    } else {
        Err(RuntimeError::NonBooleanCondition(
            expr.to_string(),
            (&value).into(),
        ))
    }
}

We evaluate the condition expression, ensure that the result is boolean and execute then or else branch (if define) depending on the condition value.

Summary

We've done it! The LR-Language supports if statements now! Here is how the main frame of the above program looks after the execution:

Frame {
    parent: None,
    local_variables: {
        "pi": Float(
            3.14,
        ),
        "r": Int(
            5,
        ),
        "value": String(
            "The square of the circle with the r = 5 is 157. It is > 100. It is <= 200.",
        ),
        "square": Float(
            157.0,
        ),
    },
}

Please stay in touch for Part V, where I plan to implement for and while loops! I will publish it if this post gets 30 reactions!

The state of the source code after this part could be found in the part_4 branch of the GitHub repository!

Writing a new programming language. Part III: Type System

Konstantin Grechishchev — Sat, 13 Aug 2022 11:19:00 +0000

Hello everyone!

Welcome to the third part of the new LR-language tutorial series. Here is the link for Part II. Last time we've successfully implemented the first version of the LR-language interpreter. We were able to write programs with variables of the integer type and use them in the arithmetical expressions, assigning the results to other variables.

The state of the code by the end of this tutorial could be found in the part_3 branch of the GitHub repository. The changes made today could be seen in the e5e04bc commit

Goal for today

The goal for today is to extend the language to support String and float types as well! We will also improve runtime error reporting a bit. We would like to enhance LR-language to be able to run the following program:

{
    let hello: String = "Hello";
    let world: String = "World";
    let hello_word: String = hello + " " + world;

    let pi: Float = 3.14;
    let r: Int = 5;
    let square: Float = 2 * pi * r * r;
    let value: String = "The square of the circle with the r = " + r + " is " + square;
}

Representing values and types

Values

As a recall, here is our current representation of the expression in the AST:

pub enum Expr {
    Number(i32),
    Identifier(String),
    Op(Box<Expr>, Opcode, Box<Expr>),
}

The Number(i32) is the topic of today's discussion. It is produced every time we see a numeric literal in the LR-program code:

Num: i32 = {
    r"-?[0-9]+" => i32::from_str(<>).unwrap()
};
Term: Box<Expr> = {
    Num => Box::new(Expr::Number(<>)),
    Identifier => Box::new(Expr::Identifier(<>)),
    "(" <Expr> ")"
};

However, we would like to support more types now, so it would make sense to rename Number to Constant. The i32 type as a value would nigher work any longer, so we replace it with the following enum:

pub enum Value {
    Int(i32),
    Float(f32),
    String(String),
}

The updated section of the grammar looks like the following:

IntNum: i32 = {
    r"-?[0-9]+" => i32::from_str(<>).unwrap()
};

FloatNum: f32 = {
    r"-?[0-9]+\.[0-9]+" => f32::from_str(<>).unwrap()
};

StringLiteral: String = {
    r#""[^"]*""# => <>[1..<>.len() - 1].to_owned()
};

Term: Box<Expr> = {
    IntNum => Box::new(Expr::Constant(Value::Int(<>))),
    FloatNum => Box::new(Expr::Constant(Value::Float(<>))),
    StringLiteral => Box::new(Expr::Constant(Value::String(<>))),
    Identifier => Box::new(Expr::Identifier(<>)),
    "(" <Expr> ")"
};

We introduce 2 new types of literals: the number containing a dot (FloatNum) and any characters in double quotes (StringLiteral). The weird <>[1..<>.len() - 1] expression simply removes the first and last character of the literal as we would like to get the string literal inside double quotes, but without them.

Types

There are two ways to deal with variable types. The first option is to derive them based on the value assigned. The second is to explicitly specify the type when you declare a variable. The first one is often the variation of the second with the type specifier being optional, so to keep it simple, we will implement option 2 for now.

First, we need to define the Type enum:

pub enum Type {
    Int,
    Float,
    String,
}

and the grammar for it:

Type: Type = {
    "Int" => Type::Int,
    "String" => Type::String,
    "Float" => Type::Float,
}

Nothing special here.

As the next step, we make a slight modification to the Statement production rule

Statement: Statement = {
    "let" <Identifier> ":" <Type> "=" <Expr> ";" => Statement::new_definition(<>),
    <Identifier> "=" <Expr> ";" => Statement::new_assignment(<>)
};

While we keep the assignment rule the same, we make it mandatory to specify the type when declaring a variable. The <> operator will now pass 3 arguments to the new_definition method, so we have to modify it as well:

pub enum Statement {
    Assignment {
        identifier: String,
        expression: Box<Expr>,
    },
    Definition {
        identifier: String,
        expression: Box<Expr>,
        value_type: Type,
    },
}

impl Statement {
    pub fn new_assignment(identifier: String, expression: Box<Expr>) -> Self {
        Self::Assignment {
            identifier,
            expression,
        }
    }

    pub fn new_definition(identifier: String, value_type: Type, expression: Box<Expr>) -> Self {
        Self::Definition {
            identifier,
            value_type,
            expression,
        }
    }
}

The StatementBody struct cannot be reused any longer, so we just get rid of it.

Display traits

These are the only changes we had to make to add type system support to our grammar and syntax tree. Before we start making changes to the interpreter part, let's implement the Display for our AST structs. This would help to print them using {} in a human-readable form and allow us to create nice runtime error messages. Here is an example of the Display trait implementation for Expr enum:

impl Display for Expr {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        match self {
            Expr::Constant(v) => write!(f, "{}", v),
            Expr::Identifier(id) => write!(f, "{}", id),
            Expr::Op(e1, op, e2) => write!(f, "({} {} {})", e1, op, e2),
        }
    }
}

The implementation of it for other types looks very similar, so I omit it here, but you can find them in the GitHub repository.

Update the interpreter

The grammar and AST are ready, however, our code does not yet compile, because we need to make changes to the Frame struct to store value type as well as implement the arithmetical expressions for the new enum.

Variable storage

We start with a trivial change to replace the type of local_variables field HashMap<String, i32> with local_variables: HashMap<String, Value>. All the methods of the Frame struct should now accept and return Value instead of i32 correspondingly.

We should also perform an extra check in the assign_value and define_variable methods: we don't want to allow assigning the value of, let's say, String type to the variable declared as Integer:

pub fn assign_value(&mut self, variable_name: &str, value: Value) -> Result<(), VariableError> {
    if let Some(variable) = self.local_variables.get_mut(variable_name) {
        if Type::from(variable.deref()) == Type::from(&value) {
            *variable = value;
            Ok(())
        } else {
            Err(VariableError::TypeMismatch(
                Type::from(&value),
                variable_name.to_owned(),
                Type::from(variable.deref()),
            ))
        }
    } else if let Some(parent) = self.parent.as_mut() {
        parent.assign_value(variable_name, value)
    } else {
        Err(VariableError::UndefinedVariable(variable_name.to_owned()))
    }
}

In order to represent this type of error, we introduce the new error enum VariableError and also move the UndefinedVariable error type to it:

#[derive(Error, Debug)]
pub enum VariableError {
    #[error("Variable {0} is not defined")]
    UndefinedVariable(String),
    #[error("Unable to assign the value of type {0} to variable '{1}' of type {2}")]
    TypeMismatch(Type, String, Type),
}

Please refer to the frame.rs to see the full source code of the updated Frame struct

Arithmetic operations

If we try to compile the code now, the rust compiler will return us an error explaining that it does not know how to apply the +, -, * and / between the instances of Value enum. Fortunately, all we have to do is to implement Add, Sub, Mul and Div traits for it!

The main problem to solve here is to figure out the result type of the operation. It is obvious that 5 + 5 is 10, but what should happen when you write 5 + "hello"? Shall it be an error or shall it return a string containing 5hello?

Let's establish the following rules:

The result of the Int division is Int, the % remainder operations in not supported for now.
For any operation involving float and int, the result type should be float and we would cast int to float before the operation.
Addition of anything to the string results in a new string. No other operations except + are supported for a string.

With this in mind, we can implement the Add trait for the Value:

impl Add for Value {
    type Output = Result<Value, OperationError>;

    fn add(self, other: Self) -> Self::Output {
        let value = match self {
            Value::Int(v1) => match other {
                Value::Int(v2) => Value::Int(v1 + v2),
                Value::Float(v2) => Value::Float(v1 as f32 + v2),
                Value::String(v2) => Value::String(v1.to_string() + v2.as_str()),
            },
            Value::Float(v1) => match other {
                Value::Int(v2) => Value::Float(v1 + v2 as f32),
                Value::Float(v2) => Value::Float(v1 + v2),
                Value::String(v2) => Value::String(v1.to_string() + v2.as_str()),
            },
            Value::String(v1) => match other {
                Value::Int(v2) => Value::String(v1 + v2.to_string().as_str()),
                Value::Float(v2) => Value::String(v1 + v2.to_string().as_str()),
                Value::String(v2) => Value::String(v1 + v2.as_str()),
            },
        };
        Ok(value)
    }
}

Note that despite add is never returning an error, the return type of it is still Result<Value, OperationError>. The reason for it is to keep it consistent with other traits implementations and avoid making changes to the method signature when we add new types in the future.

The error enum is having only one variant for now:

#[derive(Error, Debug)]
pub enum OperationError {
    #[error("Operation {0} {1} {2} is not defined")]
    IncompatibleTypes(Type, Opcode, Type),
}

We also define a helpful macro to produce the error in the operations which could fail:

macro_rules! error {
    ($type_1:ident, $op:ident, $type_2:ident) => {
        Err(OperationError::IncompatibleTypes(
            Type::$type_1,
            Opcode::$op,
            Type::$type_2,
        ))
    };
}

We can use it to implement e.g. a multiplication operation:

impl Mul for Value {
    type Output = Result<Value, OperationError>;

    fn mul(self, other: Self) -> Self::Output {
        match self {
            Value::Int(v1) => match other {
                Value::Int(v2) => Ok(Value::Int(v1 * v2)),
                Value::Float(v2) => Ok(Value::Float(v1 as f32 * v2)),
                Value::String(_) => error!(Int, Mul, String),
            },
            Value::Float(v1) => match other {
                Value::Int(v2) => Ok(Value::Float(v1 * v2 as f32)),
                Value::Float(v2) => Ok(Value::Float(v1 * v2)),
                Value::String(_) => error!(Float, Mul, String),
            },
            Value::String(_) => match other {
                Value::Int(_) => error!(String, Mul, Int),
                Value::Float(_) => error!(String, Mul, Float),
                Value::String(_) => error!(String, Mul, String),
            },
        }
    }
}

I omit implementations of Sub and Div traits as they are identical to the above. You can refer to the operations.rs file to have a look at them.

Putting everything together

The only part left is to make a set of "cosmetic" changes to the evalutate_expression method. Here is the updated code of it:

#[derive(Error, Debug)]
pub enum ExpressionError {
    #[error("Unable to evalutate expression {0}: {1}")]
    VariableError(String, VariableError),
    #[error("Unable to evalutate expression {0}: {1}")]
    OperationError(String, OperationError),
}

pub fn evalutate_expression(frame: &mut Frame, expr: &Expr) -> Result<Value, ExpressionError> {
    match expr {
        Expr::Constant(n) => Ok(n.clone()),
        Expr::Op(exp1, opcode, exp2) => {
            let result = match opcode {
                Opcode::Mul => {
                    evalutate_expression(frame, exp1)? * evalutate_expression(frame, exp2)?
                }
                Opcode::Div => {
                    evalutate_expression(frame, exp1)? / evalutate_expression(frame, exp2)?
                }
                Opcode::Add => {
                    evalutate_expression(frame, exp1)? + evalutate_expression(frame, exp2)?
                }
                Opcode::Sub => {
                    evalutate_expression(frame, exp1)? - evalutate_expression(frame, exp2)?
                }
            };
            result.map_err(|e| ExpressionError::OperationError(expr.to_string(), e))
        }
        Expr::Identifier(variable) => frame
            .variable_value(variable)
            .map_err(|e| ExpressionError::VariableError(expr.to_string(), e)),
    }
}

First, we introduce an ExpressionError enum to wrap new types of errors defined above. Note that we use the Display traits implemented for AST structs to form an error message. It allows us to return nice runtime errors to a user, for example:

Unable to evaluate expression ("hello" / 5): Operation String / Int is not defined"

Second, the variable_value method and arithmetic operation could now return an error, so we need to handle it and cast to ExpressionError.

Summary

That is it! We can now run the program mentioned above. Here is how the stack frame looks after the execution:

Frame {
    parent: None,
    local_variables: {
        "r": Int(
            5,
        ),
        "hello_word": String(
            "Hello World",
        ),
        "square": Float(
            157.0,
        ),
        "world": String(
            "World",
        ),
        "pi": Float(
            3.14,
        ),
        "value": String(
            "The square of the circle with the r = 5 is 157",
        ),
        "hello": String(
            "Hello",
        ),
    },
}

Amazing, isn't it?

The plan for part IV is to add support for the boolean type and to implement the if statements!

I'll publish it if this post gets 15 reactions!

Stay in touch!

Writing a new programming language. Part II: Variables and expressions

Konstantin Grechishchev — Wed, 10 Aug 2022 19:49:00 +0000

Hello everyone! Welcome to the second part of the new LR-language tutorial series. Here is the link for the Part I. So far we've completed a little formal grammar crash course and it is now time to try it out in action using Rust!

Goal for today

We are going to implement the formal grammar, generate the parser and write the first version of the LR-Language interpreter by the end of this tutorial.

The goal is to be able to run the most simple program using the LR-language, like this one:

{
    let my_variable = 5;
    let my_variable_1 = my_variable;

    let sum = my_variable_1 + 5;
    let mult = sum * 120;
    let div = mult / 10;
    div = div / 2;
    let expression = 2 * div + 10 / 2;
}

I would like to keep things simple today, so we will only support variables of the single type - integer.

Project setup

We are going to implement our language using rust, so I'll be following the standard rust project setup. If you are new to rust, please refer to the rust book which is a great resource to learn it.

The dependencies section of the project would look as following:

[build-dependencies]
lalrpop = { version = "0.19", features = ["lexer"] }

[dependencies]
clap = { version = "3.2", features = [ "derive" ]}
lalrpop-util = "0.19"
regex = "1"
thiserror = "1.0"

[dev-dependencies]
rstest = "0.15.0"

The key point here is that we are going to depend on the lalrpop library to generate the parser based on the formal grammar we define. Note that we have it as part of the [build-dependencies] section and we only depend on a tiny utility crate called lalrpop-util at runtime. The reason for that is the main lalrpop "magic" would happen during the crate compilation (in the build.rs file) when lalrpop would generate the deterministic pushdown automaton based on our grammar. The code generation logic is not required to be part of our interpreter, we only need a few utility methods from the lalrpop-util for the automaton to operate. You might have noticed that we also enable the lexer feature of lalrpop, because we are going to use lexer provided by lalrpop as well (please refer to the Part I if you do not know what the lexer is).

The next step is to add a tiny build.rs file:

extern crate lalrpop;

fn main() {
    lalrpop::process_root().unwrap();
}

This is a pretty standard setup, suggested by the lalrpop documentation. The function process_root processes our src directory, converting all lalrpop files into rust files containing the code of the generated automaton. We don't have any grammar files yet, so let's create a new lr_lang.lalrpop file inside the src/ folder.

Defining the formal grammar

Terminals

As discussed in Part I, the first phase of the grammar processing is converting the program text into the sequence of the terminal symbols using lexer. We've enabled lalrpop's lexer feature in our Cargo.toml file so that we can use the lexer provided out of the box. LALRPOP's lexer generator section of the lalrpop documentation explains how it works in an outstanding level of detail. The default lexer automatically converts all string literals and regular expressions used in the grammar to terminals. It is doing so without requiring you to write any extra code (unless you need to resolve ambiguities between regular expressions, in this case, you would like to use the match statement). In fact, you might not even notice the lexer's existence unless you know about it. The space and \n symbol are treated as the separator by the lexer, which works fine for the most cases

Deriving first non-terminals

The Parsing parenthesized numbers section of the lalrpop manual is a good resource to start.

Let's define our first non-terminal symbols, Identifier and Num, representing a variable name and a numeric constant correspondingly by adding the following lines into the lr_lang.lalrpop file:

use std::str::FromStr;

grammar;

Identifier: String = {
    <s:r"[a-zA-Z][a-zA-z_0-9]*"> => s.to_owned()
};

Num: i32 = {
    <s:r"[0-9]+"> => i32::from_str(s).unwrap();
};

The lalrpop file syntax is the mix of rust language code and lalrpop-specific syntax to describe production rules using Backus normal form. The grammar keyword separates rust use statements and the rules.

Every rule starts with the unique name of the non-terminal character followed by the resulting non-generated rust type to represent this non-terminal in the abstract syntax tree. In this case, the identifier type is just a string and the numeric literal is i32. This is the left side of the production rule. Lalrpop allows you to describe the context-free grammar only, that is why every production rule is only allowed to contain a single non-terminal on the left side.

The curly bracket block after the equal sign contains one or multiple right parts forming production rules for a given non-terminal. Non-terminals are allowed to be mixed with terminals in any order here, however, we don't yet have any non-terminals defined, so we'll put the regular expressions instead.

Behind the scene, the regular expressions are going to be picked by the lexer. The lexer defines the terminal symbol type for each regular expression. The program code would be converted to the sequence of the tokens before any production rule is applied. Since the regular expression is defined in place, generated terminal won't have the name and its type would be &str. Lalrpop, however, is able to track each unique regular expression and constant string and correctly apply production rules. The s: prefix before the expression defines the name of the rust variable containing the terminal or non-terminal value, which we can refer to in the action code.

The last part of the rule, located after =>, is called the action code. This is a block of rust code containing the set of instructions to convert the terminal in the right part of the rule to the rust type defined in the left part.

Defining the prefix s: for every symbol in the rule is often too verbose. Lalrpop offers a shorter form to make the rules more compact. The <> expression behavior is well-described in the Type inference of the documentation. Here is how the same rules would look like in the short form:

Identifier: String = {
    r"[a-zA-Z][a-zA-z_0-9]*" => <>.to_owned()
};

Num: i32 = {
    r"-?[0-9]+" => i32::from_str(<>).unwrap()
};

Expressions

Our grammar is capable to recognize numbers and variables now. It is time to make use of them in arithmetical expressions.

Lalrpop documentation contains a great tutorial about it! Expression parsing code for LR-language is just a slightly modified version of the example outlined in Handling full expressions and Building ASTs sections of the manual. Please go over them before reading further. (Bonus: I've also made the russian-spoken YouTube video about the same a few years ago)

The only change we need to do to the above example is to include variables support in the AST. To do that, we add an additional Identifier variant to the Expr enum:

#[derive(PartialEq, Eq, Hash, Debug)]
pub enum Expr {
    Number(i32),
    Identifier(String),
    Op(Box<Expr>, Opcode, Box<Expr>),
}

We also need to handle it in the corresponding grammar rule:

Term: Box<Expr> = {
    Num => Box::new(Expr::Number(<>)),
    Identifier => Box::new(Expr::Identifier(<>)),
    "(" <Expr> ")"
};

Statements

Since expressions could be represented by our language AST it would be good to assign the result of their computation to a variable, wouldn't it?

Let's support the following two types of statements:

Variable definition with the assignment:

let variable = expression;

Assignment of the value to an existing variable:

variable = expression;

It is the same, but without the let keyword. Every statement in the LR-language must terminate with a semicolon.

The above idea could easily be expressed as a production rule:

Statement: Statement = {
    "let" <Identifier> "=" <Expr> ";" => Statement::new_definition(<>),
    <Identifier> "=" <Expr> ";" => Statement::new_assignment(<>)
};

Of course, we need to define the data structure for a statement as well:

use crate::ast::expression::Expr;

pub struct StatementBody {
    pub identifier: String,
    pub expression: Box<Expr>,
}

pub enum Statement {
    Assignment(StatementBody),
    Definition(StatementBody),
}

impl Statement {
    pub fn new_assignment(identifier: String, expression: Box<Expr>) -> Self {
        Self::Assignment(StatementBody {
            identifier,
            expression,
        })
    }

    pub fn new_definition(identifier: String, expression: Box<Expr>) -> Self {
        Self::Definition(StatementBody {
            identifier,
            expression,
        })
    }
}

It is worth noting that I deliberately am not trying to handle semantic errors here to keep the code simpler. Thus, the grammar allows to assign the value to the non-declared variable and such a program would be parsed correctly. We would capture this error during the program execution as many interpreted languages do.

Program

For now, we would represent our program in the simplest possible way: as the list of statements in between curly braces like in the example above. You can think about it as the body of the main function without function arguments and signature.

First, we need to model the list of statements using the standard induction pattern. First, we consider the single statement as a single element list of statements. Second, if the list is followed by a statement, we append a new statement to the list, eventually consuming all of them:

Statements: Vec<Statement> = {
    Statement => vec![<>],
    Statements Statement => append(<>),
};

Finally, the program is just the list of statements in the curly braces:

pub Program: Program = {
 "{" <Statements> "}" => Program::new(<>)
}

The AST data structure for it is trivial as well:

pub struct Program {
    pub statements: Vec<Statement>,
}

impl Program {
    pub fn new(statements: Vec<Statement>) -> Self {
        Self { statements }
    }
}

Implementing the interpreter

We've done the main part of the job! We can now use the generated parse to produce the LR-language program AST based on the program source code:

let program = ast::lr_lang::ProgramParser::new()
    .parse(&program_text)
    .expect("Unable to parse the program file");

The program here is the instance of the Program struct, containing the vector of Statement and so on.
However it is not fun on it's own, we would like to run it now!

The stack frame

Right we don't have functions or even blocks of operations in our program, but we would like to make our interpreter extendable for future changes. Real programming languages implement the concept of the variable scope. The scope is the portion of the code where the variable could be accessed. It is often a function body, the body of the loop, the branch of the if statement, or even just a piece of code in between { and }. In most of the above examples, apart from probably function body, you can refer to the variables defined in the parent scope as well. Thus, the body of the loop can change the variable declared somewhere above.

We will model the above concept using the Frame data structure. For simplicity, the frame contains the hash table of all variable values and the pointer to the parent frame:

#[derive(Debug, Default)]
pub struct Frame {
    parent: Option<Box<Frame>>,
    local_variables: HashMap<String, i32>,
}

We can now implement the method to define a new variable with some value:

pub fn define_variable(&mut self, variable_name: String, value: i32) {
    if let Some(variable) = self.local_variables.get_mut(&variable_name) {
        *variable = value;
    } else {
        self.local_variables.insert(variable_name, value);
    }
}

Note that we would like to allow the programmer to redefine variable, so the below code is valid and just assigns a to a new value:

let a = 0;
let a = 1;

At the moment the second statement is identical to a = 1, but once we support different types let would allow changing the type. Variable definition method never fails.

Assignment of the new value to a variable is similar, but a bit more complex:

pub fn assign_value(&mut self, variable_name: &str, value: i32) -> Result<(), RuntimeError> {
    if let Some(variable) = self.local_variables.get_mut(variable_name) {
        *variable = value;
        Ok(())
    } else if let Some(parent) = self.parent.as_mut() {
        parent.assign_value(variable_name, value)
    } else {
        Err(RuntimeError::UndefinedVariable(variable_name.to_owned()))
    }
}

We first look for the variable with a given name in this frame. If it is not found, we check it in the parent frame. If it is missing everywhere, then it was not yet defined, which indicates a runtime error!

Finally, we follow the same idea to get the existing value of the variable:

pub fn variable_value(&self, variable_name: &str) -> Result<i32, RuntimeError> {
    if let Some(&value) = self.local_variables.get(variable_name) {
        Ok(value)
    } else if let Some(parent) = self.parent.as_ref() {
        parent.variable_value(variable_name)
    } else {
        Err(RuntimeError::UndefinedVariable(variable_name.to_owned()))
    }
}

Executor

With the concept of the scope and the place to store variables values introduced to the LR-language interpreter, we can now implement the last missing piece - the logic to traverse the AST and update the variables.

First, we define the logic to evaluate expressions:

pub fn evalutate_expression(frame: &mut Frame, expr: &Expr) -> Result<i32, RuntimeError> {
    let value = match expr {
        Expr::Number(n) => *n,
        Expr::Op(exp1, opcode, exp2) => match opcode {
            Opcode::Mul => evalutate_expression(frame, exp1)? * evalutate_expression(frame, exp2)?,
            Opcode::Div => evalutate_expression(frame, exp1)? / evalutate_expression(frame, exp2)?,
            Opcode::Add => evalutate_expression(frame, exp1)? + evalutate_expression(frame, exp2)?,
            Opcode::Sub => evalutate_expression(frame, exp1)? - evalutate_expression(frame, exp2)?,
        },
        Expr::Identifier(variable) => frame.variable_value(variable)?,
    };
    Ok(value)
}

If the expression is the number or identifier, then we just return their value. Otherwise, we recursively evaluate operands and apply the operation. The operator precedence is already represented in the AST, so we have no need to worry about the order between e.g. * and +.

The execution of the statement is quite simple as well. We simply evaluate the statement expression and then update the value in the frame:

pub fn execute_statement(frame: &mut Frame, statement: &Statement) -> Result<(), RuntimeError> {
    match statement {
        Statement::Assignment(body) => {
            let value = evalutate_expression(frame, &body.expression)?;
            frame.assign_value(&body.identifier, value)?;
        }
        Statement::Definition(body) => {
            let value = evalutate_expression(frame, &body.expression)?;
            frame.define_variable(body.identifier.clone(), value);
        }
    }
    Ok(())
}

The program execution is just a for loop, executing every expression one after another:

pub fn execute_program(frame: &mut Frame, program: &Program) -> Result<(), RuntimeError> {
    for statement in &program.statements {
        execute_statement(frame, statement)?
    }
    Ok(())
}

Running it!

This is how the main function of the interpreter binary looks like:

fn main() {
    let args: Args = Args::parse();
    println!("Running program {}", args.program_file);

    let program_text =
        fs::read_to_string(args.program_file).expect("Unable to read the program file");
    let program = ast::lr_lang::ProgramParser::new()
        .parse(&program_text)
        .expect("Unable to parse the program file");
    let mut root_frame = Frame::default();
    execute_program(&mut root_frame, &program).unwrap();
    println!("Main frame: {:#?}", root_frame);
}

We parse the program, create the root frame for it, and simply call execute_program method. Since LR-language does not yet support any input/output operations, we will just print the stack state after the executions. This is how it looks after the execution of the simple program, mentioned at the beginning of the article:

Main frame: Frame {
    parent: None,
    local_variables: {
        "mult": 1200,
        "expression": 125,
        "div": 60,
        "sum": 10,
        "my_variable": 5,
        "my_variable_1": 5,
    },
}

Summary

It was quite a journey today! We've implemented the first version of the context-free grammar for the LR-language, structures to represent the language AST and core components to interpret the program.

You can find the state of the source code in the part_2 branch of the kgrech/lr-lang github repo.

I would like to implement the support of String and float data types as part of the next tutorial. I will publish it if this post gets at least 10 reactions!

Stay in touch!

Writing a new programming language. Part I: a bit of boring theory

Konstantin Grechishchev — Sat, 06 Aug 2022 15:43:00 +0000

Introduction

Every serious software engineer should make an attempt to write their own programming language at least once. Apart from the set of knowledge obtained, it could be a fun process! I feel like it is now time for me to try this challenge.

I would like to challenge myself to write a series of tutorials to help the reader to learn about formal grammars, and LR parsers and get some practical skills to be applied in their project.

I don't have a goal to write a new programming language to be used anywhere for any specific purpose. In fact, I highly discourage anyone from using it :). I am not planning to make this language compile, instead, we would write the interpreter to run the programs written in it.

I am hoping to implement the support of expressions, if statements, basic loops, and functions, however exact feature set and the number of tutorials would depend on audience interest (number of reads, comments, and amount of reactions to the posts). I'll keep all my code in the kgrech/lr-lang with a branch pointing to the commit representing the code state by end of every tutorial.

I'll name the language I am writing as LR-language, simply because we are going to use LR parser to parse its grammar and because I was not able to come up with any better name.

Useful knowledge

I would be writing the language in Rust, so knowledge of the syntax and Rust skills would help. Rust book is a good resource to learn.

I'll be using the lalrpop parser generation library, so keep to documentation for it handy.

Some understanding of Chomsky grammar hierarchy, LR Parsers and Backus normal form (BNF) would be definitely useful, however, I intentionally do not plan to dive deep into the theory as I don't think I have enough theoretical background myself. There are good books to learn it. Instead, I'll focus on the practical aspects of it, while I have to spend some time explaining a theory in the first tutorial so that unprepared readers have an idea about what is going on. If you are not interested in this, please jump right away to Part II!

Formal grammars (crash course)

Terminal symbols and tokenization

The program written in our language consists of so-called terminal and non-terminal symbols. The terminal symbols are known and defined in advance and usually are just one character or a sequence of characters. For example, the terminal symbol is one of the following:

Letters, digits, underscores.
Expression operations (+, -, *, /, <, >, <=, >=).
Language keywords (for, if, else, let).

The first step of the program "compilation" is tokenization. The tokenization is usually performed by the component called lexer. Lexer's duty is to read the text of the program and convert it to the sequence of the terminal symbols with their values attached to them. The sequence of the terminal symbols are then processed by the component call parser to derive non-terminal symbols and produce the abstract syntax tree (AST).

You don't really need the formal grammar to implement the lexer. In fact, the example of the simplest lexer is just the split by whitespace function. In practice the lexers are more complex, but typically could be configured using a set of string literal and regulars expressions (this is how it is done in lalrpop library).

The examples above might look a bit contradictory as language keywords contain letters on their own. E.g. "for" consists of 3 letters. Are they 3 terminal symbols ('f', 'o', and 'r') or 1 terminal symbol (for)? This is called lexer ambiguity and there are different ways to resolve it. A typical strategy is to consider everything which matches language keywords as a single terminal symbol and split everything else. This is why you can not use keywords as the variable name in most of the programming languages. And yes, the variable name is an example of the non-terminal symbol.

Formal grammars

Formal grammar is the way to give meaning to the sequence of the terminal symbols. The grammar consists of the finite set of so-called "production rules". You can think about them as the set of rules defining how can we "replace" a sequence of the terminal and non-terminal symbols with a new non-terminal symbol (while technically you can replace it with a sequence of them, it makes everything a lot more complex).

The most common way to write such rules is called Backus–Naur form. The exact syntax of the rule is different based on the parser generation library used, but the idea could be illustrate by the following example:

<digit> = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9
<number> = <digit> | <digit> <number>

The words in triangular brackets are called non-terminal symbols, "|" and "=" are the meta symbols and everything else is the terminal symbol.

So, non-terminal symbols are received by replacement of some terminals and non-terminal according to the production rule.

The hierarchy of grammars was proposed by Noam Chomsky in 1950-th. Chomsky divided all grammars into four types (from simplest to more complex):

Regular.
Context-free.
Context-sensitive.
Recursively enumerable.

The difference between them is what kind of rules are allowed in each. We are mainly interested in the first two as there are well-know ways to implement parser for them. We will skip the last two as they are the way too complex to parse and hence they are not so useful.

Regular grammars

A well-known example of regular grammar is regular expressions (yes, that is why they are called this way) available in the standard library of most languages. The key property of the regular grammar described language is that it can be decided (parsed) by a finite state automaton. That means that no matter how long the program is, it would take a constant amount of memory to parse it.

In case of regular expressions:

Each character is the terminal symbol.
The regular expression is the grammar (written not in Backus–Naur form by the way).
The terminal symbols are captured groups.
The "program" is the string.

Unfortunately, regular grammar rules are too simple to express most of the programming languages including our baby LR-Language. So we will have to use context-free grammar!

Context-free grammars

Formally speaking, context-free grammar is the one allowing the single non-terminal symbol to appear in the left part of the rule and the sequence of one or more terminals and/or non-terminals in the right part of it in any order. In other words, the right side of the rule is not restricted. This is not true for the regular grammar, which has restrictions on the order of the terminals/non-terminals on the right side. Attentive readers could spot that every regular grammar is context-free, but not vice-versa.

Context-free grammars could be parsed by the deterministic pushdown automaton.

Abstract syntax tree

The main reason to define and apply the production rules is to build the so-called abstract syntax tree (AST). The AST is a set of data structures that represent the parsed language. It is a tree because one data structure contains (points) to another. The AST structures are written in one of the existing programming languages (we will call it target language), i.e. in the language the compiler and parser are written. In our case target language is Rust, because the parser of our LR-language is written in rust.

When the parser parses the program it applies production rules one by one. The first rule would only take a set of terminal symbols as there were non-terminals produced yet.

Most of the parser generation libraries allow you to write a piece code in the target language next to the rule. This could converts the rule input into the data structure representing a non-terminal symbol. For the first rule, the input would be just a set of terminal symbol strings. If there is some rule containing the non-terminal symbol produced above on the right side, the associated target language code for this rule must accept the above data structure as an input.

This way, when we apply a rule by rule, we nest one non-terminal data structure into other forming the abstract syntax tree.

The interpreter can then traverse this tree and execute the program.

Next steps

You've reached here? Good job on reading all of the above!

We will apply the above theory in the next part of the tutorial and write the first part of our language. We are going to define the first version of the formal grammar using the lalrpop parser generation library, generate deterministic pushdown automaton in rust and write the interpreter to run our first program written in LR-language.

Stay in touch!

Bonus: Russian-speaking readers are welcome to watch my youtube video about formal grammars.

7 ways to pass a string between 🦀 Rust and C

Konstantin Grechishchev — Sat, 30 Jul 2022 13:06:00 +0000

Interoperability with C is one of the most incredible things in Rust. The ability to call safe Rust code from C and use well-known libraries with a C interface from Rust is a crucial reason for the fast adoption of Rust across the industry. It also allows us to distribute the code better by implementing C interfaces for the rust crate, so it could be used by the software written in any language capable of calling C.

Writing the FFI interface is also quite confusing and hard to get correct on the first attempt. How to deal with all these into_raw and as_ptr methods without leaking the memory and causing the security vulnerability? It scares people as well: the usage of the unsafe keyword is nearly inevitable.

I'll try to shine some light on the memory aspects of the FFI interfaces and provide a few hopefully useful patterns I've used in my projects.

NOTE: I would be using strings here as an example, however, the technics decried are applicable to transfer the byte arrays or pointers to the structs on the heap in Box or Arc types as well.

Things to know before we jump into coding

I would like to talk about a few essential rules before we implement our first FFI function. It is important to keep them in mind during the design as missing one of them would likely lead to the bug in the form of a crash or a memory leak.

Rule #1: One pointer - one allocator

You might think that allocation of the memory is nothing but a call to some magical operation system API. The reality is that getting a chunk of memory to write your buffer to is a sophisticated (and expensive!) operation. Compilers and library developers are tempted to apply all sorts of optimizations (like getting a bigger chunk of memory to avoid often calls to the operating system) to optimize it and they implement it differently!

You should make no assumptions about the type of memory allocator used by the caller of your library. They don't have to use malloc and are free from the libc! In other words, the memory allocated by the rust code should be deleted by the rust code and the pointers obtained over the FFI boundary should be returned back to be released. If you've allocated memory using malloc, do not try to convert it to Box and drop it! Do not try callingfree on the pointer obtained by calling Box::into_raw()!

Rule #2: Think about the ownership

Rust is a memory-safe language and it is explicit about ownership. When you see Box<dyn Any> in your code, you know that the memory to store Any would be released as soon as you drop the Box. In contrast, when you see void*, you do not right away have an idea whether you should call free on it or would someone else do it (or maybe it is not even required as it points to the stack)?

Rust have a naming convention for the methods to convert the struct to the raw pointer. Standard library structs like Box, Arc, CStr and CString provide as_ptr and pair of the into_raw and from_raw methods. Not every struct provides all three of them, which makes them even more confusing. They are so crucial, that it is worth spending some time discussing them here.

Let's look into the CString as it has all three of the above. Both as_ptr and into_raw methods provide you a pointer of the same type. However, like a void* mentioned above, these pointers are different in terms of ownership.

The as_ptr method takes &self by reference. It means that the CString instance exists on a stack after as_ptr returns and keeps the ownership of the data. In other words, the pointer returned points to the data still owned by the CString instance. Dropping the instance would keep the pointer dangling (pointing to bad memory). You should never use this pointer after the CString instance is dropped. In safe rust, this property of the pointer is represented by the lifetime of the reference (analogs to pointer) and controlled by the compiler but with a raw pointer, all bets are off.

Unlike as_ptr, the into_raw accepts the self by value and destroys it. Wait, would not destroy release the memory? It turns out that into_raw does not call the drop method! It creates an owning pointer and "leaks" the block of memory provided by the rust allocator out of the rust compiler control. You introduce the memory leak if you simply drop this pointer without calling the from_raw method on it. However, it would never dangle (unless you change it or clone before calling from_raw).

You should use as_ptr if you would like to let C temporarily "borrow" the rust memory. This has a huge advantage, because the C code does not need to worry about releasing it, but it also limits the pointer lifetime. It is probably a bad idea to save this pointer in some global struct or pass it to another thread. Returning such pointer as the result of the function call is likely a bad idea as well!

The into_raw method moves the ownership of the data to C. It gives a lot of freedom to keep the pointer around for as long as the code needs, but it is important to make sure that it is transferred back to rust to be removed at some point!

Memory representation of the String

Unfortunately, rust and C represent strings differently. The c string is usually a char* pointer pointing to the array of char with /0 in the end. Rust stores the array of chars and the length of it instead.

Due to the above reason, you should not convert rust String and str type directly to raw pointers and back. You would like to use CString and CStr intermediate types to achieve it. Usually, CString is used to pass the rust string to C code, and CStr is used to convert C string to rust &str. Note that this conversion is not always causing the copy of the underlying data. Such, the &str obtained from CStr will keep internally pointing to C allocated array and its lifetime is bound to the lifetime of the pointer.

NOTE: String:new copies the data, but CStr::new does not!

Project setup

How to link rust and C together

There are plenty of materials online devoted to building the C code and linking it to the rust crate using build.rs file, however I significantly fewer articles about adding rust code to the C project. In contrast, I would like to implement the main function of my example project in C language and use CMake as the build system. I would the CMake project to use the rust crate as a library and generate C header files based on the rust code. The source code of the complete project is in github.

Running Cargo from CMake

I've stated with generating simple CMake 3 console application project.

The first thing we need to do is to define the command to build the rust library and the location of the rust artifacts:

if (CMAKE_BUILD_TYPE STREQUAL "Debug")
    set(CARGO_CMD RUSTFLAGS=-Zsanitizer=address cargo build -Zbuild-std --target x86_64-unknown-linux-gnu)
    set(TARGET_DIR "x86_64-unknown-linux-gnu/debug")
else ()
    set(CARGO_CMD cargo build --release)
    set(TARGET_DIR "release")
endif ()
SET(LIB_FILE "${CMAKE_CURRENT_BINARY_DIR}/${TARGET_DIR}/librust_lib.a")

The command to build the debug version of crate would probably look a bit awkward for people familiar with rust. It could very well be replaced with just cargo build, however, I would like to make use of rust unstable address sanitizer feature to ensure the absence of the memory leaks.

Second, we need to define the custom command and custom target to depend on the command output. We can then define a static imported library called rust_lib and make it depending on the target to build it:

add_custom_command(OUTPUT ${LIB_FILE}
        COMMENT "Compiling rust module"
        COMMAND CARGO_TARGET_DIR=${CMAKE_CURRENT_BINARY_DIR} ${CARGO_CMD}
        WORKING_DIRECTORY ${CMAKE_CURRENT_SOURCE_DIR}/rust_lib)

add_custom_target(rust_lib_target DEPENDS ${LIB_FILE})
add_library(rust_lib STATIC IMPORTED GLOBAL)
add_dependencies(rust_lib rust_lib_target)

Finally, we can link our binary together with a rust library (and other system libraries required). We also enable address sanitizer for C code:

target_compile_options(rust_c_interop PRIVATE -fno-omit-frame-pointer -fsanitize=address)
target_link_libraries(rust_c_interop PRIVATE Threads::Threads rust_lib ${CMAKE_DL_LIBS} -fno-omit-frame-pointer -fsanitize=address)

Running the CMake build will now build the rust create automatically and link with it. However we have to way to call rust methods from C yet.

Generating C headers and adding them to the CMake project

The easiest way to obtain the headers for the rust code is to use the cbingen library.

We can then add the following code to the build.rs file of our crate to detect all extern "C" functions defined in rust and generate a header for them in the header file under include/ directory:

let crate_dir = env::var("CARGO_MANIFEST_DIR").unwrap();
let package_name = env::var("CARGO_PKG_NAME").unwrap();
let output_file = PathBuf::from(&crate_dir)
    .join("include")
    .join(format!("{}.h", package_name));

cbindgen::generate(&crate_dir)
    .unwrap()
    .write_to_file(output_file);

We should also create the cbindgen.toml file in the root folder of the rust crate and add the language = "C" line into it.

The only thing left to do is to ask CMake to look for the headers in the include folder of the rust crate:

SET(LIB_HEADER_FOLDER "${CMAKE_CURRENT_SOURCE_DIR}/rust_lib/include")
set_target_properties(rust_lib
        PROPERTIES
        IMPORTED_LOCATION ${LIB_FILE}
        INTERFACE_INCLUDE_DIRECTORIES ${LIB_HEADER_FOLDER})

5 ways to pass the Rust string to C

Finally we are all set. Imagine we now want to get some string from data from rust and use it in C (just to print to console). How can we do it safely and without leaking the RAM?

Option #1: Provide create and delete methods

Use this method when we don't know how long the C code would like to be able to access the string. A good indication of it is that we would like to return a pointer out of the rust method. We would transfer the ownership to C by constructing the CString object and casting it to the pointer using into_raw. The free method needs to just construct CString back and drop it to release the RAM:

#[no_mangle]
pub extern fn create_string() -> *const c_char {
    let c_string = CString::new(STRING).expect("CString::new failed");
    c_string.into_raw() // Move ownership to C
}

/// # Safety
/// The ptr should be a valid pointer to the string allocated by rust
#[no_mangle]
pub unsafe extern fn free_string(ptr: *const c_char) {
    // Take the ownership back to rust and drop the owner
    let _ = CString::from_raw(ptr as *mut _);
}

It is crucial to call free_string at some point to avoid the leak:

const char* rust_string = create_string();
printf("1. Printed from C: %s\n", rust_string);
free_string(rust_string);

Do not call libc free method on the string and do not try to modify the content pointed by such pointer!

The above works well, but what if we want to unload the rust library while we are using the ram or want to release it in the part of the code which is not aware of the rust library? We should be able to achieve by using one of the below 3 options.

Option #2: Allocate the buffer and copy the data

Remember the rule #1? If we would like to release the memory in C using, let's say free method, we should allocate it using malloc. But how would the rust know about malloc? One solution is to "ask" rust how much memory does it need and then allocate a buffer for it:

size_t len = get_string_len();
char *buffer = malloc(len);
copy_string(buffer);
printf("4. Printed from C: %s\n", buffer);
free(buffer);

Rust just needs tell the right buffer size and carefully copy the rust string into it (without missing the 0 byte!):

#[no_mangle]
pub extern fn get_string_len() -> usize {
    STRING.as_bytes().len() + 1
}

/// # Safety
/// The ptr should be a valid pointer to the buffer of required size
#[no_mangle]
pub unsafe extern fn copy_string(ptr: *mut c_char) {
    let bytes = STRING.as_bytes();
    let len = bytes.len();
    std::ptr::copy(STRING.as_bytes().as_ptr().cast(), ptr, len);
    std::ptr::write(ptr.offset(len as isize) as *mut u8, 0u8);
}

This is great as we don't have to implement the free_string and just use free instead. Another great advantage is that C code is allowed to modify the buffer as it wants (that is why we use *mut c_char and not *const c_char).

The problem is we still need to implement the additional method get_string_len and the solution still allocates a new block of memory and copies the data (but CString::new also does it).

We can also use this method if you would like to move rust string to buffer allocated on the stack of the C function, but we should ensure it has enough space!

Option #3: Pass the memory allocator method to rust

Ok, we remember rule #1, but can we avoid get_string_len method and find some way to allocate memory in rust instead? It turns out we can! One way is to simply pass the function to allocate ram to rust:

type Allocator = unsafe extern fn(usize) -> *mut c_void;

/// # Safety
/// The allocator function should return a pointer to a valid buffer
#[no_mangle]
pub unsafe extern fn get_string_with_allocator(allocator: Allocator) -> *mut c_char {
    let ptr: *mut c_char = allocator(get_string_len()).cast();
    copy_string(ptr);
    ptr
}

Here and below we use copy_string form the example above. We can now then use the get_string_with_allocator as following:

char* rust_string_3 = get_string_with_allocator(malloc);
printf("3. Printed from C: %s\n", rust_string_3);
free(rust_string_3);

The solution is identical to the option #2, and has the same pros and cons.

But we now have to pass additional allocator parameter. We can probably optimize it a bit and avoid passing it to every function, but register it in some global variable instead.

Option #4: Call glibc from rust

Ok, what if we are sure that our C code would use a given version of malloc/free only to allocate memory (are we ever sure about anything like that is out of the scope of the article)? Well, in this case we are brave enough to use libc crate in our rust code:

#[no_mangle]
pub unsafe extern fn get_string_with_malloc() -> *mut c_char {
    let ptr: *mut c_char = libc::malloc(get_string_len()).cast();
    copy_string(ptr);
    ptr
}

The C code stays pretty much the same:

char* rust_string_4 = get_string_with_malloc();
printf("4. Printed from C: %s\n", rust_string_4);
free(rust_string_4);

This way we don't need to provide the allocator method, but we've significantly limited the C code as well. We better document it very well and avoid using this option unless we are 100% sure it is safe!

Option #5: Borrow the rust string

So far we were always passing the ownership of the data to C. But what if we don't need to do it? An example of this situation is when the rust code needs to call some synchronous C method and pass some data to it. The as_ptr method of CString would help us:

type Callback = unsafe extern fn(*const c_char);

#[no_mangle]
pub unsafe extern fn get_string_in_callback(callback: Callback) {
    let c_string = CString::new(STRING).expect("CString::new failed");
    // as_ptr() keeps ownership in rust unlike into_raw()
    callback(c_string.as_ptr())
}

Unfortunately, even in this case CString:new will copy the data (as it needs to put zero byte in the end).

The C code would look like this:

void callback(const char* string) {
    printf("5. Printed from C: %s\n", string);
}

int main() {
    get_string_in_callback(callback);
    return 0;
}

We should always prefer this way when we have a known lifetime of the C pointer as it guarantees the absence of memory leaks.

Two ways to pass the C string to Rust

In conclusion, I would like to speak about the vice versa operation of converting the C string to rust types. There are 2 options available:

Convert it to &str without copying the data
Copy the data and receive the String.

I'll have the same example for both since they are very similar and in fact, option #2 requires option #1 to be used first

Here is our C code. We allocate the data on the heap, but we could also pass the pointer to the stack:

char *test = (char*) malloc(13*sizeof(char));
strcpy(test, "Hello from C");
print_c_string(test);
free(test);

The rust implementation looks as following:

#[no_mangle]
/// # Safety
/// The ptr should be a pointer to valid String
pub unsafe extern fn print_c_string(ptr: *const c_char) {
    let c_str = CStr::from_ptr(ptr);
    let rust_str = c_str.to_str().expect("Bad encoding");
    // calling libc::free(ptr as *mut _); causes use after free vulnerability
    println!("1. Printed from rust: {}", rust_str);
    let owned = rust_str.to_owned();
    // calling libc::free(ptr as *mut _); does not cause after free vulnerability
    println!("2. Printed from rust: {}", owned);
}

Note that we use CStr here instead of CString. Do not try calling the CString:from_raw method on the pointer not created by CString::into_raw!

It is also important to note here that the &str reference will have a lifetime bound to the lifetime of the c_str object method and not a 'static lifetime. Rust compiler is trying to prevent you to avoid returning the &str out of the method or moving it to a global variable/another thread, because the &str reference becomes invalid as soon as C code frees the memory.

If you need to keep the ownership of the data in rust for a long time, simply call to_owned() to obtain a copy of the string! If we would like to avoid copying, we are free to carry CStr around, but we should make sure that C code does not frees the memory while we are using it!

Summary

We've talked about rust and C interoperability today and considered different ways to pass the data across the FFI boundary. As mentioned above, the concepts could be applied to transfer other data types as well and to FFI bridges to other programming languages.

I really hope you've found the above tips beneficial and practical and welcome any questions and feedback.

Source code.
Please react to the article and star the repository if it was useful!