Musings

From Rust To Zig

Rust is now too mainstream. DARPA is onboard, it's making it's way into Linux, and is stable and popular. I think this is a Good Thing. But the contrarian in me knows that it's time for me to move on to something new, because what's the fun in using languages that are popular?

Enter Zig. It's been gaining traction among tech folk for having C interop, interesting features, and fast compile times. Some of the headlines:

We're going to be rewriting ver2gal, a Rust program I bashed together for a project at university. It parses a Yosys JSON netlist and creates a JEDEC fuse file to program GAL chips. When I was writing it, we were in a crunch, so I didn't have the liberty to try and think about structuring the program correctly, and I made a few mistakes:

  1. Trying to have a graph-like structure internally. Rust doesn't do graphs well, and this was a weird multi-port graph thing. I later realized a better approach.
  2. Getting too magical with serde. It was cool, but often made code clunky.
  3. getting confused with iterators/loops/maps and making a mess of the readability.
  4. No actual tests.

I'd like to fix these with the rewrite.

Rust is good

Before I get too carried away...

Rust and Zig find each other in the ring often. They're both "new-age" programming languages, which are aiming to replace C/C++. Rust is fantastic. In the vast majority of cases, Rust is the better language to use. Choosing Zig is somewhat irrational at this time, because it's unstable, has comparatively little investment from corporations, and has fewer libraries to draw from. These will all change with time, and then we could have discussions strictly about PL differences and type-expressiveness and such. If you are asking yourself this question and you want a "logical" answer for "serious" software, the only correct decision is Rust.

Reasons to choose rust (not exhaustive):

  1. It's stable
  2. Async
  3. Strong library ecosystem
  4. Easier "dynamic dispatch"
  5. More adoption across fields, such as data science (polars), RTOS (RTIC, embassy), web (leptos)

Zig lets you shoot yourself in the face

Rust's greatest feature is the borrow checker - satisfy it, and you can make assertions about your code that are nearly impossible to make in other languages. However, it has downsides; the borrow checker has false-negatives that can prevent otherwise valid and safe code from compiling, and waging a war against it is a battle of lifetimes (literally). Zig has no such feature. Instead, it includes a variety of tools to help you track memory allocation and usage:

  1. No default allocator. There are even data structures that do not store a reference to their allocator like HashMapUnmanaged, which enable a cool property where you can pass the map by itself and guarantee that the function using it cannot allocate memory.
  2. A debug allocator that tracks memory leaks.
  3. A test allocator that simulates every possible malloc failure. This makes sure that your code will not leak if it fails to allocate partway through.
  4. nice valgrind integration, where memory that is undefined is filled with 0xaa.

You can still easily make a segmentation fault, but it is also much easier to spot in code.

Too much Type

In my original implementation, I constructed a multi port graph representation of the yosys netlist. This was largely a mistake and pretty wasteful. I used too much serde and tried to fully encode the state space inside distinct types, and then write functions that operate on the union of those types:

// Define a Cell type.
#[derive(Clone, Debug, Serialize, Deserialize, PartialEq)]
#[serde(rename_all = "UPPERCASE")]
pub struct GalSopParameters {
    #[serde(deserialize_with = "from_binstr")]
    pub depth: u32,
    pub table: String,
    #[serde(deserialize_with = "from_binstr")]
    pub width: u32,
}

#[derive(Clone, Debug, Serialize, Deserialize, PartialEq)]
pub struct GalSop {
    pub name: Option<String>,
    pub connections: HashMap<String, Vec<Net>>,
    pub parameters: GalSopParameters,
}
// More like this...

#[derive(Clone, Debug, Serialize, Deserialize)]
#[serde(deny_unknown_fields)]
#[serde(tag = "type")]
pub enum YosysCell {
    #[serde(rename = "GAL_SOP", alias = "GAL_1SOP")]
    Sop(GalSop),
    #[serde(rename = "GAL_INPUT")]
    Input(GalInput),
    #[serde(rename = "GAL_OLMC")]
    OLMC(GalOLMC),
}

serde structs to deserialize JSON

While this seems nice, and gives cool autocomplete, it's not exactly great to work with. For one, even with just three cell types, we introduce a total of 7 types - the union of all cell types, each cell, and each cell's parameters. While this gives us validation for free (failure to deserialize to a concrete type), we kinda cut corners anyways, since the connections field is still a HashMap. If we were to fully commit, it would be a simple struct that would contain named fields.

The advantage here is that we move some of the validation into the deserialization process. This sounds nice, but I actually think it's an anti-pattern. The deserializer should only be concerned with the abstract structure of the data. Validation should be a discrete process, because some validation steps are annoying to encode for serde. Consider a validation where we check that the cell's output net is not the same as any of it's inputs. This is not possible to easily encode for serde. Instead we would have to create a custom deserializer just to check for this validation state, or have an additional validation function, which would put our validation logic in two places.

zig fix

Instead of parsing to distinct cell types in a union, I wrote a generic yosys cell struct:

/// Yosys Netlist Cell type.
pub const Cell = struct {
    const Self = @This();
    const PropType = enum {
        attr,
        param,
    };
    /// Cell type. Index into modules to find the root cell.
    type: []const u8,
    /// Parameters of this instance of the cell.
    parameters: JsonStringMap,
    /// misc attributes of the cell
    attributes: JsonStringMap,
    /// Connections on ports of this cell.
    connections: json.ArrayHashMap(BitVector),

    port_directions: json.ArrayHashMap(PortDirection),

    // methods omitted...

};

The Cell structure in Zig

The JsonStringMap for parameters and attributes is basically a HashMap<String, String>. Yosys always uses strings here, and writes numbers into strings of binary for consistent parsing. To make it easier to read, I added the getProp call, which is our first use of comptime that I discovered. Actually, the second, but you'll see the first one shortly.

pub const Cell = struct {
    // ... fields omitted

    /// Attempt to read a value from the properties of the cell.
    /// T must be []const u8 or an unsigned integer (see strtob)
    pub fn getProp(self: Self, comptime T: type, prop: PropType, name: []const u8) ?T {
        return switch (prop) {
            .attr => readProperty(T, self.attributes, name),
            .param => readProperty(T, self.parameters, name),
        };
    }
}

the getProp method

We pass it a type. The code notes that the type must be a string ([]const u8) or a uint. The proptype is used to determine if we're reading from properties or attributes, which are different. I declared a small enum within the struct that encodes the options.

readProperty is pretty simple:

pub fn readProperty(comptime T: type, map: JsonStringMap, prop: []const u8) ?T {
    const val = map.map.get(prop) orelse return null;

    if (T == []const u8) {
        return val;
    } else {
        return strtob(T, val) catch null;
    }
}

The most comptime-ish part is strtob, which actually does things by inspecting the type:

/// convert the yosys string-of-bits to a given integer type.
/// Note that the lengths must be exact, i.e if a string is shorter than
/// the container, it will still error.
pub fn strtob(comptime T: type, str: []const u8) !T {
    const info = @typeInfo(T);
    if (info != .int or info.int.signedness != .unsigned) {
        @compileError("strtob only accepts unsigned integer types");
    }
    const n_bits = info.int.bits;

    // check that our target uint is big enough to hold the string.
    // note that technically we could find the most significant 1 bit,
    // but that's complex and probably means the program has a bug.
    if (str.len > n_bits) {
        return error.SizeMismatch;
    }

    var result: T = 0;

    for (str, 0..) |c, i| {
        if (c == '1') {
            result |= @as(T, 1) << @intCast(str.len - i - 1);
        } else if (c != '0') {
            // not 0 or 1, so error
            return error.InvalidChar;
        }
    }
    return result;
}

This was my first actual non-toy comptime usage. This function determines the number of bits from the integer, and uses that to compare the length of the bit-string from yosys. Yosys pads the strings with zeros to a certain length to enforce the correct sizing, so we want to make sure that the integer is large enough to store the largest value that Yosys could give us. Then we iterate through the string and set each bit.

Compare this to the Rust version:

fn from_binstr<'de, D>(deserializer: D) -> Result<u32, D::Error>
where
    D: Deserializer<'de>,
{
    let s = String::deserialize(deserializer)?;
    u32::from_str_radix(s.as_str(), 2).map_err(D::Error::custom)
}

While this seems simpler in terms of content, what the actual hell am I writing? The introduction of a lifetime parameter on top of a type trait bound that uses the lifetime parameter makes this code rather difficult to understand. Additionally I have to annotate (which is another weird thing) struct fields with #[serde(deserialize_with = "from_binstr")] to use this custom deserializer. Additionally, this only works with 32-bit integers. Adding support for any size of integer would be an additional challenge.

While it would be possible to take a similar approach in Rust, it really drives you towards these complex type scenarios if you're not careful. I've seen newcomers to Rust struggle to understand the paradigm shift that comes with a strong and sophisticated type system.

Graphs

This was another design failure that's mostly my fault, I would make the argument that some of Rust's features also negatively influenced the design.

Basically, the Yosys Netlist gives us a hashmap of cells, which have nets (which are just sequential integers). We can easily go from cell -> net using this structure, but can't go from net -> cell(s). This is complicated by the fact that cells have multiple ports, each with a direction and 1 or more nets on them. Additionally we can't just point directly to the cell, because then there's ownership issues, and I don't want to deal with those (moving at a hackathon-level pace). The simplest way to do this in rust is to introduce an adjacency list based graph structure:

#[derive(Default, Debug)]
pub struct Graph {
    pub nodelist: Vec<Node>,
    pub adjlist: Vec<NetAdjPair>,
    pub ports: Vec<NamedPort>,
}

This is a classic graph representation - two lists, one of nodes, and another of adjacency pairs. The pairs will use indices into the node list to point to individual nodes, rather than pointers. We can attach additional data to the pairs, like the port of each side of the connection, and the net that it is part of.

This is fine, but the access patterns aren't great. We have to filter through the massive adjacency list to find adjacencies for a single net, which makes the Cell -> Net -> Cell lookup slower. The motivation for this design is the lack of pointer types. If I had pointer types, I could make a list of Net -> Vec<*Cell> which would solve most of the issues. This is still possible in Rust, but you have to start messing with lifetimes, which is not what I wanted to do.

In zig, there are no such restrictions. I can simply make a pointer and I'm on my own. I create my NetCellMap which is essentially HashMap<Net, Vec<CellMember>> where CellMember is a simple struct which contains information about the Cell that connects to it:

pub const NetCellMember = struct {
    cell: *const Cell,
    port: []const u8,
    direction: PortDirection,
};

This makes it easy to find i.e the driver of a net - I iterate on the CellMembers and return the first one with .direction == .output || .direction == .inout. Then I can directly access the underlying Cell without needing to go through another layer of indirection. I allocate the whole thing on an arena so I don't have to worry about use-after-free.Rust does have arenas, but they still complicate lifetimes, especially with self-reference loops.

With these constructs I can "dance" along the graph from any Cell by finding the appropriate port and getting the nets from it, and then using the NetCellMap to find other cells that are on that net.

Footgun: Copying Arenas

It wouldn't be fair if I only proselytize the nice parts of zig, would it?

This was one problem that stumped me for a while. I would try to allocate an array of booleans only to have the values randomly get changed later. I bashed my head against the wall. Why was this array being modified? Eventually I asked in #zig and got my answer. Can you spot it?

/// Create a GAL representation of the given chip.
pub fn init(allocator: Allocator, chip: ChipType) !GAL {
    var arena = ArenaAllocator.init(allocator);
    const spec = chip.getSpec();
    const olmcs = try arena.allocator().alloc(OLMC, spec.olmcs.len);
    var result: GAL = .{
        .arena = arena,
        .chip = chip,
        .olmcs = olmcs,
        // there are other fields that are default null or 0
    };
    // use registered mode on both chips
    switch (chip) {
        .gal22v10 => {},
        .gal16v8 => {
            const pt: []bool = try arena.allocator().alloc(bool, 64);
            @memset(pt, true);
            result.pt = pt;
            // omitted...

The arena gets copied when I make the result struct. This means that when I use the plain arena later on line 16, the indexes overlap and they'll modify the same memory. Copying when you should have taken a pointer or constructed in place is probably the largest footgun I've encountered so far, and will continue with the 0.15 "Writergate" changes. The effects are very subtle here.

Of course, the more correct approach is to instantiate the arena inside the result struct. But this doesn't work here because I want to allocate my OLMCs before constructing.

But actually, I don't need to do that at all. Even though I must provide a value for olmcs in the struct, I could make it undefined, which is a semi-valid value in zig:

pub fn init(allocator: Allocator, chip: ChipType) !GAL {
    const spec = chip.getSpec();

    var result: GAL = .{
        .arena = ArenaAllocator.init(allocator),
        .chip = chip,
        .olmcs = undefined,
    };
    result.olmcs = try result.arena.allocator().alloc(OLMC, spec.olmcs.len);
    for (spec.olmcs, 0..) |*olmc_spec, idx| {
        result.olmcs[idx] = .{ .spec = olmc_spec };
    }

Using undefined to defer allocation

undefined in Zig means that the value is uninitialized. In Debug or ReleaseSafe modes, attempts to access it are trapped and will crash. However, we initialize it right away afterwards, so this isn't an issue. Now the arena is only accessible inside the result struct. This prevents the misuse of the allocator (since it can't be copied) while still allowing us to have non-null struct members that rely on said allocator!