Learning Zig by creating a parser

[opal sun]

Hello fellow Ziguanas. I am entirely new to Zig and wanted to ask for some code critique. My program compiles and runs, but this is the first time I code in a manual memory-managed language and wanted to ask how you would maybe structure things differently. I am following the book Crafting Interpreters by Robert Nystrom to create an interpreter for his made up language Lox.

Here's the code so far:
https://github.com/eikooc/lox-interpreter-zig

Things I am wondering:

• Am I reading and doing "strings" correctly?
• Am I using allocators correctly?
• Is there a better "pattern matching" way of doing long if branches?
• Could I use structs in a better way?

[mild hollow]

skimming the code-base I see you're using std.heap.page_allocator quite a bit... don't!
a page allocator does an mmap syscall whenever more memory is requested from it - it is quite slow, and very wasteful (each allocation is 4 KiB!)

usually we use a std.heap.GeneralPurposeAllocator. create one at the beginning of main, and pass an allocator argument, of type std.mem.Allocator to every function that needs it.

the page allocator is the most basic alloctor, that many other allocators wrap around.

as for file reading - your utility function readResourceFile calls readFileAlloc with the value of max_bytes being 512. this means that if your source file is longer than 512 bytes (a very common thing), the function will return error.FileTooBig.

you probably don't want to impose a maximal file size, use std.math.maxInt(usize) to get the largest possible value a usize can hold.

there are a few memory leaks I spotted... for example, in your run function you're calling scanTokens, this returns you a std.ArrayList(Token) - that array-list is never deallocated!

I don't see any use of errdefer and only two uses of defer. all the memory that isn't freed is leaked - when you switch to std.heap.GeneralPurposeAllocator it will crash at run-time whenever it detects a memory leak, not fun, but it'll help you see where you have memory errors...

understanding ownership and deallocation responsibility is a hard thing if you never used low-level languages before. I can't teach you all of it in this one message, but as a rule of thumb you should always mentally note down all of the values that you have that use any resource (allocated memory, open files, etc). you should always ask yourself: "who created this value? who uses it? when is it last used? who has the responsibility of cleaning up after? what happens if the function exited abnormally?" etc.

btw, for scanning you don't need any allocations.
Zig, in its standard library, exposes some of the compiler itself. you can look into std.zig.Tokenizer to see how they tokenise source code. notice that std.zig.Tokenizer works in an iterator approach: it has one main function (next) the retrieves the next token in the source code, advancing the tokeniser's position accordingly.

[opal sun]

Hi @mild hollow thanks for your replies 😃. I've since updated to pass the GPA around instead. Thanks for those suggestions.

Setting the readFileAlloc with the max value of a usize doesn't pre-allocate all that memory does it? And can a file be bigger than the max value of a usize so I just push the problem?

I think I fixed all the memory leaks, and yeah it is going to be an uphill battle to learn how to manage memory since I haven't used a low-level language before. That is one of the things I want to learn properly by learning Zig. I'll keep those questions close whenever I use the allocator to allocate anything. I don't quite get why using memory by creating a const doesn't allocate memory that needs to be freed, is it because you only allocate things that go on the heap and everything else goes on the stack which is not something you allocate?

I will take a look at the std.zig.Tokenizer, but then how do I pass all the tokens on to the Parser afterwards if I haven't stored all the tokens in an array? 🤔

[mild hollow]

readFileAlloc does not over-allocate. the length of the returned slice is the length of the file.
there cannot be a file longer than std.math.maxInt(usize) - the OS itself can't handle that!

as for const and var values not needing to be freed... this is a big topic, but I'll give you a rundown: the data in your program is stored in one of three places: the stack, the heap, or static memory (for pedants: not gonna get into multithreading here...).

static memory holds global variables and constants (your string literals go there!), values living in static memory have, well, static lifetime - they are accessible throughout your program.

a value defined locally in a function, with const or var lives on the stack (except for consts that are evaluated at compile-time, those go in static memory) - these values have lifetime beginning at their declaration and until the end of the scope they're in (the closing }); the memory they take up is automatically discarded and is available for reuse at scope's end.

the problem with the first two places is that the size of the values they hold needs to be known at compile-time (for pedants: not gonna talk about alloca!), so we can't for example store a file's contents in there - we don't know its length! and so we use the 3rd place, the heap.

the heap is a storage place, growable by asking nicely from the OS, in which values can be stored for a dynamic time period. std.heap.page_allocator is a thin wrapper around this ask-the-OS-for-more-heap, and std.heap.GeneralPurposeAllocator (with default settings...) is a wrapper around that. whenever you allocate some memory from the allocator it searches for a place in the heap to, well, allocate to you (asking the OS for more heap if no space was found). it returns you a pointer to that memory.
after you're done with the memory you must tell the allocator about this, so that it'll be able to reuse the memory for some other allocation.

using a value after its lifetime is a memory error (use after free), freeing a piece of memory twice is an error (double free), forgetting to free an allocated piece of memory is an error (resource leak).

but yeah, that's why only data on the heap (and types that wrap around data on the heap e.g. std.ArrayList) need explicit freeing.

as for the tokeniser... if you think about the process of building the AST, after the tokeniser has ran, you'll see that at any given moment the only thing the AST builder needs is knowledge of the next handful of tokens (the exact amount depends on the langauge's grammar)...

a type providing a way to consume the pending token (next) and a way to peek at the next handful of tokens (peek) is enough to build the AST - and nowhere in there you need to allocate a std.ArrayList(Token) to store all of the tokens!

[opal sun]

Wow, thanks for that lengthy explanation. That makes a ton of sense, I didn't know that the stack can only contain compile-time known lengths of things. So basically your program "knows" when it runs how much memory to pre-allocate and it reserves that memory on the stack as it launches?

Ahh, it also makes sense now with the AST builder being able to have a constant size array/buffer that it can use to store the next few tokens. I just read about how left-recursive grammars are harder to implement and this is one such example I guess. Making it right-recursive allows us to only look at the next few tokens

[mild hollow]

kinda...
the amount of stack memory used changes at runtime (if you think about recursive functions you'll see that one can use as much stack as they wish!).
whenever a function gets called the stack grows by the amount the function needs (this new space is called the function's frame). when a function returns that frame gets popped off, and the stack shrinks back.

in practice there is a limit to the stack's size, and if you use too much you'll get a Stack Overflow error.

we prefer the stack over the heap because it's easier to deal with (no deinit!) and much faster. higher-level programming languages use heap memory all the time - at a (sometimes unacceptable) performance penalty

[opal sun]

Hmm, alright. I am rolling back my thought there. I'll have to look deeper into why some things can be pushed to the stack and others can't I guess. If it is something your program can just ask for more of until getting a Stack Overflow then I guess I don't see why we can't try to read a file into that space. I will research, thanks for the explanations.

The reason why I thought it made sense with the "everything is known in advance" is because I heard a talk from the guys at TigerBeetle and they mentioned they have everything preallocated, so when the program starts up they know exactly how much memory it will use and it will never use more. Thus being a good citizen on the computer it is running on. And also eliminating problems by other programs gobbling up memory it would want to use

[honest sapphire]

google says windows stack is like 1mb and my linux's stack is 8mb according to ulimit -s

[mild hollow]

the stack is better thought about as functions' scratch space for internal calculation. their arguments are passed in, some computation occurs, and then the result is given back to the caller.

because the stack frame is static and known (not gonna talk about alloca!), access to items on the stack is very easy and fast.

accessing heap items (usually) takes longer because of CPUs' caching, allocating and freeing memory is even worse, because the allocator must manage the heap, and search for a location to be provided...

in theory, if you only need to read a chunk of the file at a time, that chunk having known length - you can do it without using the heap at all (though there is no too-good-of-a-reason to do that...)