How to deinit a mutually recursive data structure?

Help
1

Hi!

I’ve been playing around with Zig and it’s been a really nice experience.

Although, I’m now facing a problem that seems like a good opportunity to reach out to the community.

I’m struggling writing the deinit function for a tree-like data structure (a very simple AST to be exact).

The AST is implemented as a mutually recursive pair of data structures: a struct Node and a union Ast tagged with leaf and node (I’m open to suggestions if it is not the best/more idiomatic way of implementing an AST in Zig).

My understanding is that I have to recursively free the sub-trees before freeing a node. So far I think I’ve managed through the error messages about freeing the sub-trees (although it is not really tested yet). Somehow, I can’t figure out how to free the data stored in the current node: an operator implemented as an enum.

Here is the code I have so far:

const std = @import("std");

pub const Operator = enum { seq, par, con, dis, };

pub const Node = struct {
    const Self = @This();
    operator: Operator,
    left: ?*const Ast,
    right: ?*const Ast,

    fn init(allocator: std.mem.Allocator, operator: Operator) !Self {

        const node = try allocator.create(Node);
        node.* = .{ .operator = operator, .left = null, .right = null };
        return node.*;
    }
    fn deinit(self: *Self, allocator: std.mem.Allocator) void {
        if (self.left) |left| {
            switch (left.*) {
                .leaf => |leaf| allocator.free(leaf),
                .node => |node| node.deinit(allocator),
            }
        }
        if (self.right) |right| {
            switch (right.*) {
                .leaf => |leaf| allocator.free(leaf),
                .node => |node| node.deinit(allocator),
            }
        }
        allocator.free(self.*.operator);
        self.* = undefined;
    }
};

pub const NodeTag = enum { leaf, node };
pub const Ast = union(NodeTag) {
    leaf: [][]u8,
    node: *Node,
};

test "Node" {
    const allocator = std.testing.allocator;
    var node = try Node.init(allocator, Operator.con);
    defer node.deinit(allocator);
}

I end up with the following error message (line number are wrong as I’ve removed irrelevant parts):

$ zig test src/ast.zig
truncated/bin/zig/lib/std/mem/Allocator.zig:439:45: error: access of union field 'pointer' while field 'enum' is active
    const Slice = @typeInfo(@TypeOf(memory)).pointer;
                  ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
truncated/bin/zig/lib/std/builtin.zig:550:18: note: union declared here
pub const Type = union(enum) {
                 ^~~~~
referenced by:
    deinit: src/ast.zig:84:23
    test.Node: src/ast.zig:101:22
  • deinit: src/ast.zig:84: allocator.free(self.*.operator);

I’m working with version 0.16.0-dev.2261+d6b3dd25a (0.16 from a few weeks back).

2

One way is to not sweat it at all. Everything in the AST is allocated in an arena and after you’re finished with it, you toss the whole thing with one call to deinit the arena.

3

Why are you freeing the operator field? It doesn’t look like it was allocated. Does Operator have a deinit method that should be called instead?

2 Likes
4

The operator member of node is just an enum that is not allocated independently, so it disappears when you deallocate the node. So deiniting it is not a problem you need to solve.

5

I had an error message about leaking memory, so I figured I have to free this field too.

6

You can’t free what was not allocated.

That error message (the full stack trace) will tell us where the leak is, i.e, where the call is that allocates memory, that has no matching deallocate.

7

Unlike other languages, Zig has no hidden allocations. You only need to free a thing you alloc’d. Your leak is something else.

8

OK. So IIUC, the logic is to recursively free the sub-trees and then free the node itself.

Now If I put a allocator.free(self); in place of mistakenly freeing the operator, I have:

λ zig test src/ast.zig -freference-trace=3
/home/nicolas/.local/bin/zig/lib/std/meta.zig:117:5: error: Expected pointer, slice, array or vector type, found '*ast.Node'
    @compileError("Expected pointer, slice, array or vector type, found '" ++ @typeName(T) ++ "'");
    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/nicolas/.local/bin/zig/lib/std/mem.zig:4669:30: note: called at comptime here
    if (@sizeOf(std.meta.Elem(Slice)) == 0) return &[0]u8{};
                ~~~~~~~~~~~~~^~~~~~~
referenced by:
    free__anon_6210: /home/nicolas/.local/bin/zig/lib/std/mem/Allocator.zig:440:35
    deinit: src/ast.zig:79:23
    test.Node: src/ast.zig:93:22
9

The stack trace was indeed pointing to allocator.create(Node).

10

The problem with the Node.init function is: you allocate a node on the heap, fill it in, but then return the node as value, which means it’s copied to the caller of the function. This is the source of the memory leak because you lose the location of the allocated memory.

You have to decide if you want Node.init to return a node as value, or as a pointer to a heap allocated object.

3 Likes
11

Your call to allocator.create(Node) returns a pointer. It is that pointer you pass to allocator.destroy. So the *Node must be freed in whatever level of your code has that pointer.

12

I indeed don’t want to copy the node on the stack!

1 Like
13

It works with the allocator.destroy rather than allocator.free.

Thanks everyone. I understand a bit better what’s going on, and I’m going to read more thoroughly the alocator API :slight_smile:

2 Likes