# 12.11.2022 - Zig/Using Zig for Advent of Code

This year, I decided to use Zig to solve Advent of Code. I started learning Zig sometime ago but took a break. 

It was not something easy from the beginning, so in the first few days, I had to use either Go or TypeScript and reimplement the solution using Zig. Starting from Day 09, I became more comfortable writing Zig code.

To learn Zig, I think the best way is to refer to both of the [language references](https://ziglang.org/documentation/master/) to learn the concepts and the [source code](https://github.com/ziglang/zig) to learn about the stdlib. Reading the code is still better than reading the [Standard Library Documentation](https://ziglang.org/documentation/master/std/#root).

Below are some notes about what I've learned during this session.

## Read input file

There are a couple of ways to read an input file in Zig, the most common way is to use [`@embedFile`](https://ziglang.org/documentation/master/#embedFile):

```js
const content = @embedFile("input.txt");
```

This function will take the file content and embed it into the source code as a string.

If you don't like the idea of embedding a file into the source code, you can try reading it at runtime:

```js
pub fn readInputFile(allocator: std.mem.Allocator) ![]const u8 {
    const file = try std.fs.cwd().openFile("input.txt", .{});
    defer file.close();
    const stat = try file.stat();
    const fileSize = stat.size;
    return try file.reader().readAllAlloc(allocator, fileSize);
}
```

## Splitting a string

In both cases, we get a string of everything in a file, and in most problems, we should split them into lines. In Zig, to split a string, we can use [`std.mem.tokenize`](https://github.com/ziglang/zig/blob/959c10c5e53d35f059dae577cd606d8c96a5feb4/lib/std/mem.zig#L1909-L1914). This will return an iterator so you can iterate and do stuff with each of the lines.

For example, we can use an [`ArrayList`](https://github.com/ziglang/zig/blob/959c10c5e53d35f059dae577cd606d8c96a5feb4/lib/std/array_list.zig#L998) to store the lines:

```js
var lines = std.ArrayList([]const u8).init(allocator);
defer lines.deinit();
var readIter = std.mem.tokenize(u8, content, "\n");
while (readIter.next()) |line| {
    try lines.append(line);
}
```

## Working with strings

You can't directly compare two `[]const u8` strings, and this must be done via the [`std.mem.eql`](https://github.com/ziglang/zig/blob/959c10c5e53d35f059dae577cd606d8c96a5feb4/lib/std/mem.zig#L579) function:

```js
const isMatch = std.mem.eql(u8, str1, str2);
```

To find out if a string is prefixed or postfixed with something, use `std.mem.startsWith` and `std.mem.endsWith`:

```js
if (std.mem.startsWith(u8, <haystack>, <needle>)) {
    ...
}
```

There are many other helpful functions that you can use like `indexOf`, `replace`, `join`,... in the `std.mem` module. And they also work for any type of slice.

## Converting between types

A string can be parsed to an integer number using the [`std.fmt.parseInt`](https://github.com/ziglang/zig/blob/959c10c5e53d35f059dae577cd606d8c96a5feb4/lib/std/fmt.zig#L1741-L1757) method:

```js
const sizeStr = "1000";
const fileSize: u64 = try std.fmt.parseInt(u64, sizeStr, 10);
```

Just like C or Go, you can convert a character into a number (for example, to use as array indexes) by subtracting it with the letter `'a'` or convert an index back to a letter:

```js
pub fn charCode(c: u8) usize {
    if (c >= 97 and c <= 122) {
        return c - 'a';
    } else {
        return c - 'A' + 26;
    }
}

pub fn codeToChar(code: usize) u8 {
    if (code < 26) {
        return 'a' + @intCast(u8, code);
    } else {
        return 'A' + @intCast(u8, code) - 26;
    }
}
```

## Initializing arrays

If you have a list in which the length is known at `comptime`, you can use arrays, and the repeating pattern is very helpful in this case:

```js
//1-dimensional array
var charFrequency: [CHAR_COUNT]usize = .{0} ** CHAR_COUNT;
//2-dimensional array
var freqs: [size][CHAR_COUNT]usize = .{.{0} ** CHAR_COUNT} ** size;
```

In the context of Advent of Code, most problems will have a known input size, which means we always have a `comptime` size:

```js
pub fn solve(inputContent: []const u8, comptime ropeLen: usize) i32 {
    const knots: [ropeLen]Point = .{ Point.new() } ** ropeLen;
    ...
}
```

For an array in which length is only known at runtime, `ArrayList` should be the solution:

```js
var list = std.ArrayList(Foo).init(allocator);
var listLen = list.items.len;

for (list.items) |item| {
    ...
}

const item = list.items[4];
```

If you really want to use an array in this case, you can allocate the array yourself:

```js
const arr = try std.heap.c_allocator.alloc(<type>, <length>);
```

Or use a classical fixed-length array with a pointer to indicate the last element's position.

```js
// Poor man's Dynamic Array - Fixed capacity
var list: [1024]u32 = .{};
var listEnd: usize = 0;
// Insertion                                       
list[listEnd] = 1; listEnd += 1;
list[listEnd] = 2; listEnd += 1;
list[listEnd] = 3; listEnd += 1;
// Access                                       
print("{any}\n", .{list[0..listEnd]});
```

## Poor man's Queue

Zig has a built-in queue as part of the `LinkedList` module called [`TailQueue`](https://github.com/ziglang/zig/blob/master/lib/std/linked_list.zig#LL160), but sometimes, if I'm in need of a handy queue and I know the set of data I'm working with is small, I'll just roll out my own "queue":

```js
// Poor man's Queue
var queue: [1024]u32 = .{};
var head: usize = 0;
var tail: usize = 0;
// Enqueue / Push back
queue[tail] = 1; tail += 1;
queue[tail] = 2; tail += 1;
queue[tail] = 3; tail += 1;
// Peek the top
print("{}\n", .{queue[head]});
// Dequeue / Pop front
head += 1;
// Peek the whole queue
print("{}\n", .{queue[head..tail]});
```

Of course, this is neither something new nor Zig-specific and there are a lot of problems with this "queue", but as I said, it works as long as the problem's requirements are small.

## Iterating over slices

By default, when you use the `for` loop to iterate over a slice, the captured value is an immutable reference of each element:

```js
for (list.items) |item| {
    // modify item will not work
    item += 10;
}
```

In order to modify the elements, you'll need to capture them as a mutable reference, and deref them with `.*` to modify:

```js
for (list.items) |*item| {
    // modify item will not work
    item.* += 10;
}
```

## Lookup table with HashMaps

Zig has many helpful built-in data structures, one of which is [`std.AutoHashMap`](https://github.com/ziglang/zig/blob/959c10c5e53d35f059dae577cd606d8c96a5feb4/lib/std/hash_map.zig#L1617-L1643).

```js
var map = std.AutoHashMap(u32, bool).init(std.testing.allocator);
defer map.deinit();

try map.put(5, true);

var it = map.iterator();
while (it.next()) |entry| {
    // entry.key
    // entry.value
}

_ = map.remove(5);
```

`std.AutoHashMap` does not support string as a key type, and in this case, you should use [`std.StringHashMap`](https://github.com/ziglang/zig/blob/959c10c5e53d35f059dae577cd606d8c96a5feb4/lib/std/hash_map.zig#L63-L68) instead.

```js
const DirectoryMap = std.StringHashMap(*FileEntry);
var dirMap = DirectoryMap.init(allocator);
try dirMap.put("/", &root);
```

You can also use [`std.ComptimeStringMap`](https://github.com/ziglang/zig/blob/959c10c5e53d35f059dae577cd606d8c96a5feb4/lib/std/comptime_string_map.zig#L86-L96) to define a string-keyed hashmap at the compile time as well:

```js
const MOVE_MAP = std.ComptimeStringMap(Point, .{
    .{ "U", .{ 0,  1} },
    .{ "D", .{ 0, -1} },
    .{ "R", .{ 1,  0} },
    .{ "L", .{-1,  0} },
});
```

`std.ComptimeStringMap` is limited to 2000 entries.

## Working with numbers

You can cast between number types using [`@intCast`](https://ziglang.org/documentation/master/#intCast):

```js
self.display[@intCast(usize, self.cycle-1)] = '$';
```

In other languages, modulo can be calculated using the `%` operator. This is not the case in Zig. You have to use the [`@mod`](https://ziglang.org/documentation/master/#mod) function instead:

```js
if (@mod(n, 2) == 0) {
    // even number!
}
```

Also, you can find the absolute value of a number using [`std.math.absCast`](https://github.com/ziglang/zig/blob/959c10c5e53d35f059dae577cd606d8c96a5feb4/lib/std/math.zig#L973-L980), which will cast and return the value right away, or use `std.math.absInt`, which will return the error if the conversion fails.

## Sorting and Searching

Zig has many interesting built-in methods to help you handle sorting and searching.

For searching, the most simple one is the [`std.mem.indexOf`](https://ziglang.org/documentation/master/std/#root;mem.indexOf) function that let you find the index of an element in a slice:

```js
const foundAt = std.mem.indexOf(u32, [_]u32{1, 2, 3, 5}, [_]u32{2});
```

Or you can use [std.sort.binarySearch](https://github.com/ziglang/zig/blob/master/lib/std/sort.zig#L7):

```js
fn order_u32(context: void, lhs: u32, rhs: u32) math.Order {
    _ = context;
    return math.order(lhs, rhs);
}

const index = binarySearch(u32, 5, &[_]u32{ 1, 2, 3, 4, 5 }, {}, S.order_u32);
```

For sorting, most of the time, you can use [std.sort.sort](https://github.com/ziglang/zig/blob/master/lib/std/sort.zig#L196-L204) method:

```js
std.sort.sort(i32, haystack, {}, std.sort.desc(i32));
```

The last parameter is the comparator function, and Zig has many built-in comparators that you can use, like [std.sort.asc](https://github.com/ziglang/zig/blob/4efdbd304488207490e9c686aae98053d258ebd4/lib/std/sort.zig#L1159), [std.sort.desc](https://github.com/ziglang/zig/blob/4efdbd304488207490e9c686aae98053d258ebd4/lib/std/sort.zig#L1171),..

---

Overall, my experience using Zig for this AoC session involved a lot of fighting with the compiler due to my lack of comprehension about `comptime`. But once I get past that, it becomes just a pleasure to write Zig code (_I know, weird_).

Zig's reference and std document are decent points to start searching for knowledge. But most of the time, they're just lacking, and most knowledge is better found by reading the std's source code. Which is also a good thing because it helps me know Zig's codebase better. Heheh.

Anyway, AoC has yet to be concluded, and so does my journey with Zig. This post will be continued to grow as I learn more stuff throughout the session. 

Thank you so much for reading. I hope you all have a great holiday!

---

After I published the article, @andrewrk commented with some suggestions about the points I made in the article:

- (1) Use `std.fs.Dir.readFileAlloc` instead of your `readInputFile` function.
- (2) No need to append lines into an array list. Just iterate over the memory directly.
- (4) `std.fmt.digitToChar`
- (6) `std.fifo.LinearFifo`
- (9) Please be aware of what `@intCast` does which is asserting that the mathematical value is representable in the destination type. Also, the `%` operator is available but only when modulus division and remainder division would yield the same result, i.e., when the inputs are unsigned.

Using Zig for Advent of Code

# 01.12.2022 - Zig/How ArenaAllocator works

`ArenaAllocator` is one of Zig's built-in allocators. It takes another allocator and wraps some code around to allow you to allocate memory without the need to free them individually. Every allocated memory will be freed at once when you call `ArenaAllocator.deinit()`.

```zig
var arena = std.heap.ArenaAllocator.init(std.heap.c_allocator);
defer arena.deinit();

// Use `arena.allocator()` and forget about freeing anything
```

This post will not go into the details of how memory allocation happens but will focus on how `ArenaAllocator` manages the memory buffers to be free in a single call.

You can find the implementation details in [lib/std/heap/arena_allocator.zig](https://github.com/ziglang/zig/blob/master/lib/std/heap/arena_allocator.zig).

Each instance of `ArenaAllocator` consists of two things:

- **A child_allocator:** is the actual allocator that does memory allocation and deallocation.
- **An internal buffer_list:** is a [singly linked list](https://github.com/ziglang/zig/blob/master/lib/std/linked_list.zig#L15) to keep track of the allocated buffers.

![](_meta/arena-allocator-struct.png)

Let's take a look at the following example, assuming we allocated two objects `A` and `C`, each one allocates some child objects:

```
├── A
│   └── B
└── C
    └── D
        └── E
```

Every time memory allocation happens, the `child_allocator` will allocate a new buffer. A node containing the pointer to this buffer will be created and prepended into the `buffer_list`.

![](_meta/arena-allocator-prepend.png)

When `ArenaAllocator.deinit()` is called, Zig traverse the `buffer_list` and free each node's buffer. The way Zig stores the nodes in `buffer_list` allows it to free every child object before freeing the parent one.

```zig
pub fn deinit(self: ArenaAllocator) void {
    var it = self.state.buffer_list.first;
    while (it) |node| {
        // this has to occur before the free because the free frees node
        const next_it = node.next;
        self.child_allocator.free(node.data);
        it = next_it;
    }
}
```

![](_meta/arena-allocator-deinit.png)

In the above example, `E`, `D` will be freed before `C`. And `B` will be freed before `A`. Hence, no orphaned memory gets leaked.



How ArenaAllocator works

# 01.11.2022 - Zig/Build system

There are 4 build modes in Zig, each can be enabled via the arguments `-O ReleaseSafe`, `-O ReleaseSmall`, and `-O ReleaseFast` when running `zig run` or `zig test`.

Depending on which mode is enabled, runtime safety checks (things like number overflow check,...) and optimizations will be enabled or disabled

|Build mode|Runtime Safety|Optimization|
|:---------|:--------------|:------------|
|Debug     |Yes            |No           |
|ReleaseSafe|Yes           |Yes, Speed   |
|ReleaseSmall|No           |Yes, Size   |
|ReleaseFast|No            |Yes, Speed   |

To build your code into an executable, use `zig build-exe`, it's also possible to cross-compile and build executable for different platforms in Zig too.

Zig also has `zig build` command, which will compile your program based on a `build.zig` file. Run `zig init-exe` or `zig init-lib` to create an empty project with `build.zig` script.

A basic Zig project will have the following structure:

```
.
├── build.zig
└── src
    └── main.zig
```

When `zig build` is triggered, the build runner will run the function `build()` in your build script as an entry point, the file look like this:

```zig
const Builder = @import("std").build.Builder;

pub fn build(b: *Builder) void {
    // Default build target and mode, will take the information
    // from the zig build command. You can override if you want.
    const target = b.standardTargetOptions(.{});
    const mode = b.standardReleaseOptions();

    // Build the executable file
    const exe = b.addExecutable("init-exe", "src/main.zig");
    exe.setTarget(target);
    exe.setBuildMode(mode);
    exe.install();

    // And run it afterwards
    const run_cmd = exe.run();
    run_cmd.step.dependOn(b.getInstallStep());

    const run_step = b.step("run", "Run the app");
    run_step.dependOn(&run_cmd.step);
}
```

The executable will be created at `./zig-cache/bin` by default.

See more details in [ZigLearn/Build system](https://ziglearn.org/chapter-3/).



Build system

# 01.10.2022 - Zig/Handling errors

A function in Zig can return either an error or an actual value, most of the time you will see something like this:

```zig
pub fn countTheSheep() !u32 {
  ...
}
```

The return type of these functions is the combination of an error set type and an expected return type, and the `!` binary operator, also called an error union type:

```
<error set>!<expected type>
```

If the error set is omited, it will be [inferred](https://ziglang.org/documentation/master/#Inferred-Error-Sets) by the compiler.

It's recommended to always use explicit error set instead of inferred.

An error set is the same as an enum, each error name will be assigned with an unsigned integer greater than 0. Each error name can have a doc comment too:

```zig
const EmotionalError = error {
  // Cuz I'm grumpy right now
  TheMusicIsTooLoud,

  TheSkyIsBlue,

  // I know, right?
  LifeIsTooHard
};
```

If you defined the same error name more than once (in two different sets — you can't define the same error in the same set), it gets assigned the same integer value:


```zig
// This won't works
const EmotionalError = error {
  TheMusicIsTooLoud,
  TheSkyIsBlue,
  LifeIsTooHard,
  TheSkyIsBlue
};

// This works
const MidlifeCrisisError = error {
  // Not again...
  LifeIsTooHard
};
```

You can merge the error sets with `||` operator, when you do so, the doc comment from the left-hand set will override the doc comment from the right-hand set:

```zig
const LifeError = EmotionalError || MidlifeCrisisError;
```

The doc comment of `LifeError.LifeIsTooHard` is `// I know, right?`.

There are a couple of ways we can handle a function with an error return type:

- Use **catch:** when you want to provide a default value in case of error, for example:

  ```zig
  fn getLen(input: [:0]const u8) !usize {
    return input.len;
  }

  var len = getLen("hello") catch 0;
  // or
  var len = getLen("hello") catch |err| {
    std.debug.print("Hey! There is an error, I'm gonna return 0");
    return 0;
  };
  ```

  If you are so sure that your code will works and the error will never happen, you can use `catch unreachable`. In this case, if you're wrong, and the program is compiled in Debug or ReleaseSafe mode, the program will panic and crash. In ReleaseFast mode, it's an undefined behavior.

- Use **try** when you want to return the same error from he caller function, otherwise, continue:

  ```zig
  var len = try getLen("hello");
  std.debug.print("It works!", .{});
  ```

  In this example, if `getLen` returns an error, the caller function will be returned with the same error. Otherwise, the execution will be continued and `"It works"` will be printed.

  You can also use `errdefer` to evaluate an expression on the exit of current code block (just like `defer`), but if and only if the error is returned from this block.

  ```zig
  var len = try getLen("hello");
  errdefer print("Len is 5, it's bad!", .{});
  if (len == 5) return error.BadLen;
  std.debug.print("It works!", .{});
  ```

- Use **if** with an error capture is also a good way in case you want to do more things depends on the result of the function:

  ```zig
  if (getLen("hello")) |len| {
    std.debug.print("Len = {}", .{len});
  } else |err| { // <-- capture err here
    std.debug.print("Oops! {}", .{err});
  }
  ```

Lastly, don't forget to check out [Zig's documentation about Errors](https://ziglang.org/documentation/master/#Errors) for more in-depth discussions about error handling!



Handling errors

# 01.09.2022 - Zig/JSON in 5 minutes

Zig has built-in support for JSON via the `std.json` module.

**To convert any object into a JSON string**, we use `std.json.stringify(<input>, <options>, <output stream>)`:

```zig
const x = Place{
  .lat = 51.997664,
  .long = -0.740687,
};

var buf: [100]u8 = undefined;
var fba = std.heap.FixedBufferAllocator.init(&buf);
var string = std.ArrayList(u8).init(fba.allocator());
try std.json.stringify(x, .{}, string.writer());
```

See [`StringifyOptions` struct](https://github.com/ziglang/zig/blob/master/lib/std/json.zig#L2841) for more details about what you can pass into the options.

**To parse a JSON string into an object**, we can do it in two ways:

- **_Parse into a pre-defined struct_** with `std.json.parse(<output type>, <tokens>, <options>)`:

  ```zig
  const Foo = struct { a: i32, b: bool };
  const s =
  	\\ {
  	\\   "a": 15, "b": true
  	\\ }
  ;
  const stream = std.json.TokenStream.init(s);
  const parsedData = try std.json.parse(Foo, &stream, .{});
  ```

  The `TokenStream` is a streaming parser that returns a stream of JSON, so we can pass them into `std.json.parse`.

  The JSON parser requires an allocator if the input JSON data contains strings or arrays, and we need to free them after use with `std.json.parseFree`:

  ```zig
  const gpa = std.heap.GeneralPurposeAllocator(.{}){};
  defer std.debug.assert(gpa.deinit());

  const Foo = struct { a: i32, b: bool, c: []u8 };
  const s =
  	\\ {
  	\\   "a": 15, "b": true,
  	\\   "c": "hello world"
  	\\ }
  ;
  const stream = std.json.TokenStream.init(s);
  const parsedData = try std.json.parse(Foo, &stream, .{
    .allocator = gpa.allocator()
  });
  defer std.json.parseFree(Foo, parsedData, .{
    .allocator = gpa.allocator()
  });
  ```

  Try comment out the `defer std.json.parseFree` statement to see how's the memory leak detection of `GeneralPurposeAllocator` works.

  Checkout [`ParseOptions` struct](https://github.com/ziglang/zig/blob/master/lib/std/json.zig#L1478) for more about what options you can pass, for example:

  - Set `ignore_unknown_fields` to `true` will not return any error if there is a mismatch between the output type and input data.
  - Set `duplicate_field_behavior` will change the default's behavior when there is a duplicate field in your JSON input.

- **_Parse into a dynamic object_** of type `std.json.ValueTree` with a non-stream parser `std.json.Parser(<allocator>, <copy input string>)`:

  ```zig
  var parser = std.json.Parser.init(allocator, false);
  defer parser.deinit();

  const s =
  	\\ {
  	\\   "a": 15, "b": true,
  	\\   "c": "hello world"
  	\\ }
  ;

  var tree = try parser.parse(s);
  defer tree.deinit();

  // @TypeOf(tree.root) == std.json.Value

  // Access the fields value via .get() method
  var a = tree.root.Object.get("a").?;
  var b = tree.root.Object.get("b").?;
  var c = tree.root.Object.get("c").?;
  ```

  There is also a `dump()` method that available on any `std.json.Value`, to stringify an object and print it out to the `stderr`, best for debugging purpose:

  ```zig
  tree.root.dump();
  ```

For more details, you should read [the implementation of `std.json` module](https://github.com/ziglang/zig/blob/master/lib/std/json.zig), also, don't skip the tests at the bottom of the source file. They're super useful!



JSON in 5 minutes

# 01.08.2022 - Zig/Case Study: Implementing a Generic Stack

Implementing a stack is one of my favorite tests when working with a new language because it will show us a lot about the language's ergonomics.

We are going to make this stack a generic data structure. By Zig's convention, it will be a function that takes a type `comptime T` for its elements and returns a `type` like this:

```zig
const std = @import("std");

pub fn Stack(comptime T: type) type {
    return struct {
    };
}
```

Our `Stack` is going to have the following methods:

- `init()`: Initialize the stack
- `deinit()`: Deinitialize the stack
- `push()`: Push a new item to the stack
- `pop()`: Remove and return the top item of the stack
- `top()`: Get the top item of the stack
- `count()`: Get the length of the items in the stack
- `isEmpty()`: Check if the stack is empty or not

We will use the built-in `std.ArrayList` to store data in our stack. It's a contiguous and growable list data structure. `ArrayList` is also a generics data structure, so it's suitable for our use case here:

```zig
const ArrayList = std.ArrayList;

...
return struct {
    stack: ArrayList(T),

    const Self = @This();
};
...
```

The `const Self = @This()` statement is another common pattern in Zig for self-reference to the current `struct`.

First, let's implement `init()` and `deinit()` methods. The `ArrayList.init` method need to receive an `Allocator` as a parameter. When writing libraries in Zig, it's best to let the user of the library decide which allocator they want to use. So, we will accept an `Allocator` parameter in our `init()` method:

```zig
pub fn init(allocator: Allocator) Self {
    return Self{ .stack = ArrayList(T).init(allocator) };
}

pub fn deinit(self: *Self) void {
    self.stack.deinit();
}
```

Before we implement the `push()` and `pop()` method, let's talk about the order of data in our `ArrayList`. There are two ways to add an item to the list:

- Add a new item to the bottom of the list with the `ArrayList.append()` method. The top item of the stack will always be `stack.items[stack.items.len - 1]`.
- Add a new item to the beginning (index 0) of the list with the `ArrayList.insert()` method. The top item of the stack will always be `stack.items[0]`.

The `ArrayList.insert()` method (called with index 0) works by increasing the length of the list and moving all the items to the right before replacing the new data into the first item. The time complexity is always `O(N)`. And we can insert the new item anywhere in the list.

The `ArrayList.append()` method always adds a new item at the end of the list and allocates a new memory as needed. So, time complexity will likely be `O(1)` for most of the time. If the `Allocator` fails to allocate new memory, this method will throw an error.

We are going to use `ArrayList.append()` for our `push()` method. The return type of this method is a union type `!void`, which means this function either returns nothing (`void`) or an `error`.

```zig
pub fn push(self: *Self, val: T) !void {
    try self.stack.append(val);
}
```

And the top item of our stack will be the last item of the list:

```zig
pub fn top(self: *Self) ?T {
    if (self.stack.items.len == 0) {
        return null;
    }
    return self.stack.items[self.stack.items.len - 1];
}
```

To implement the `pop()` method, we are going to use `ArrayList.popOrNull()`, which will either remove and return the last item in the list or just return a null value if the list is empty:

```zig
pub fn pop(self: *Self) ?T {
    return self.stack.popOrNull();
}
```

There is not much to say about `count()` and `isEmpty()` methods, so I will skip ahead and show the full implementation of our stack, as well as the tests:

```zig
const std = @import("std");
const ArrayList = std.ArrayList;
const Allocator = std.mem.Allocator;

pub fn Stack(comptime T: type) type {
    return struct {
        stack: ArrayList(T),

        const Self = @This();

        pub fn init(allocator: Allocator) Self {
            return Self{ .stack = ArrayList(T).init(allocator) };
        }

        pub fn deinit(self: *Self) void {
            self.stack.deinit();
        }

        pub fn push(self: *Self, val: T) !void {
            try self.stack.append(val);
        }

        pub fn pop(self: *Self) ?T {
            return self.stack.popOrNull();
        }

        pub fn top(self: *Self) ?T {
            if (self.stack.items.len == 0) {
                return null;
            }
            return self.stack.items[self.stack.items.len - 1];
        }

        pub fn count(self: *Self) usize {
            return self.stack.items.len;
        }

        pub fn isEmpty(self: *Self) bool {
            return self.count() == 0;
        }
    };
}
```

Some tests:

```zig
test {
    const expect = std.testing.expect;

    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer std.debug.assert(!gpa.deinit());

    const IntStack = Stack(i32);

    var stack = IntStack.init(gpa.allocator());
    defer stack.deinit();

    try stack.push(1);
    try stack.push(2);
    try stack.push(3);

    try expect(stack.isEmpty() == false);

    try expect(stack.top().? == 3);
    try expect(stack.pop().? == 3);
    try expect(stack.top().? == 2);
    try expect(stack.pop().? == 2);
    try expect(stack.top().? == 1);
    try expect(stack.pop().? == 1);

    try expect(stack.isEmpty() == true);
}
```




Case Study: Implementing a Generic Stack

# 01.07.2022 - Zig/Cross-compile C/C++ and Zig programs

Zig came with a built-in C/C++ compiler `zig cc` and `zig c++`. So you can compile and run your C/C++ code with Zig!

For example, let's compile this simple C program:

```c
#include <stdio.h>

int main() {
  printf("Hello, World!!!");
  return 0;
}
```

```
zig cc hello.c -o hello
```

What's more interesting is, cross-compiling works out of the box with Zig's C compiler, for example, you can compile the above `hello.c` program for MacOS:

```
zig cc -target x86_64-macos -o hello-mac hello.c
```

Or for Linux:

```
zig cc -target x86_64-linux-musl -o hello-linux hello.c
```

It does not just work for this toy C program, but also for many C/C++ projects, for example, Zig's author Andrew Kelley showed how he compiled LuaJIT and test them via QEMU in his article:  https://andrewkelley.me/post/zig-cc-powerful-drop-in-replacement-gcc-clang.html

And not only Zig's C/C++ compiler, but the Zig compiler itself can do cross-compile by supplying `-target` param:

```
zig build-exe -target x86_64-linux-musl hello.zig
```



Cross-compile C C++ and Zig programs

# 01.06.2022 - Zig/Comptime

One of the unique features of Zig is the ability to let us control what happens in our code, during both runtime and compile time.

For optimization, Zig implicitly performs some evaluations at compile-time, for example, in the case of const.

All numeric literals `const` is of type `comptime_int` or `comptime_float`, and when we use these variables in the program, the values will be inserted at compile time instead of the variable itself.

So we can declare numeric constants without the need to specify their type:

```zig
const foo = 1234;
const bar = 12.34;
```

For mutable variables, defined with  var, you can't do this, the following definition will lead to compile error:

```zig
var foo = 1234;
// error: variable of type 'comptime_int' must be a const or comptime
foo = 2234;
```

It's because Zig assumes that an identifier declared with var will be modified at runtime. And for some variables to be modified at runtime, Zig needs to allocate some memory area for it. An exact memory size needed for the allocation is required, so we must specify a runtime type (i32 or f32,...) for that variable.

```zig
var foo: i32 = 1234;
foo = 2234;
```

We can explicitly request Zig to compute the value of this variable (and all the modifications) at compile time instead of runtime, by appending comptime keyword before the declaration:

```zig
comptime var foo = 1234;
print("{}\n", .{foo});
foo = 2234;
print("{}\n", .{foo});
```

In the above example, the value of `foo` is now calculated and modified during compile time, any usage of `foo` in the code will be replaced by its value at each usage time.

```zig
// foo after compile
print("{}\n", .{1234})
print("{}\n", .{2234});
```

We can also use `comptime` in function parameters, this opened up a lot of possibilities.

For example, let's take a look at this **impractical** example, just to see the concept, we can catch some logic errors at compile time!

The discount function returns the discounted price from an original price and the discount percent. We can use comptime to prevent the discount function to be called with any percent larger than 100%:

```zig
fn discount(price: f32, comptime percent: f32) f32 {
	if (percent > 100) @compileError("Are you nut?");
  return price - (price * percent / 100);
}
```

Calling this function with some unreasonable discount percent will throw compile error!

```zig
var price: f32 = discount(250, 125);
// error: Are you nut?
```

Another use case of `comptime` in function parameters is to pass a type into a function, it's actually how Zig implements generics:

```zig
fn makeArray(comptime T: type, size: usize) []T {
  ...
}

const arr1 = makeArray(u8, 10);
const arr2 = makeArray(f32, 5);
const arr3 = makeArray(i32, 10);
```

For every type `T` passed to the `makeArray` function, a separate copy of `makeArray` for that type will be generated at compile time.

Since `type` is also first-class in Zig, we can define generic data structures by create a function that returns a `type`:

```zig
fn List(comptime T: type) type {
  return struct {
    items: []T,
    len: usize,
  };
}
```

`List` is called a generic data structure, and we can create new list types by calling `List(i32)`, `List(u8)`,...

```zig
const NumberList = List(i32);
var list: NumberList = ...;
```

For a more in-depth discussion about `comptime`, be sure that you check out [Zig's documentation](https://ziglang.org/documentation/0.9.0/#comptime).



Comptime

# 01.05.2022 - Zig/Where data is stored and how to choose an allocator

Zig has no runtime, hence, no automatic memory management. It's the developer's responsibility to manage the allocation/deallocation of memories. It's important to know how memory allocation works, where your data is stored, and what to do with them.

**Where data is stored in a Zig program?**

String literals, `comptime` variables, top-level `var`, struct-level `var`, and `const` declarations are stored in the global constant data section.

Function-level `var` variables are stored in the function's stack frame, once the function returns, any pointers to variables in the function's stack frame will become invalid.

So, Zig will not stop you from making mistakes like this:

```zig
fn createNode(value: i32) *Node {
  var node = Node { .value = value, .left = null, .right = null };
  return &node;
}
```

In the code above, we return a pointer to a `Node` object that was created inside the `createNode` function. This object, however, will be freed after the `createNode` function returns, and won't be valid anymore. Any dereference to this pointer will lead to undefined behavior.

This also explains why you are able to return a string literal from a function and safety get away with it:

```zig
fn sayHello() []const u8 {
    return "hello world";
}
```

**How to choose an allocator?**

In the above example, the right way to return a pointer from a function is to first allocate some memory for the pointer and initialize the `Node` struct to that pointer.

Unlike C, Zig does not come with any default allocator, so we need to determine which allocator we should use based on our use case.

It's a convention in Zig that a function or struct that needs to perform memory allocation accepts an `Allocator` parameter.

The rules of thumb to choose an allocator is:

- If we are making a library, do not specify any allocator, but let the user pass their desired `Allocator` as a parameter into our library and use it.
- If we are linking with `libc`, use `std.heap.c_allocator`.
- If the maximum memory size is known or need to be bound by any number at compile time, use `std.heap.FixedBufferAllocator` or `std.heap.ThreadSafeFixedBufferAllocator`.
- If we are making a program that runs straight from start to end, like a CLI program, and it would make sense to free everything at once at the end, use something like:

  ```zig
  var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
  defer arena.deinit();

  // pass the reference of this allocator to other struct as needed
  var allocator = &arena.allocator();
  ```

  The call to `arena.deinit()` will try to automatically traverse and free everything we allocated during the program.
- Otherwise, use `std.heap.GeneralPurposeAllocator`, this allocator gives us the ability to detect memory leak, but it does not automatically free anything.

  ```zig
  var gpa = std.heap.GeneralPurposeAllocator(.{}){};
  defer std.debug.assert(!gpa.deinit());

  // pass the reference of this allocator to other struct as needed
  var allocator = &gpa.allocator();
  ```

See [std.heap](https://ziglang.org/documentation/master/std/#std;heap) package for the details of each allocator.

We also need to handle allocation error when using allocators, most of the time, an error named `error.OutOfMemory` will be returned and must be catch:

```zig
fn createNode(allocator: *Allocator, value: i32) !*Node {
    const result = try allocator.create(Node);
    result.* = Node{ .value = value };
    return result;
}

var node = createNode(allocator, 12) catch |err| {
  std.debug.print("Error: Out of memory\n{}\n", .{err});
  return null;
};
```

Lastly, it's highly recommended to watch this great talk [What's a Memory Allocator Anyway?](https://www.youtube.com/watch?v=vHWiDx_l4V0) by Benjamin Feng.



Where data is stored and how to choose an allocator

# 01.04.2022 - Zig/Strings in 5 minutes

Just like C/C++, you can define a string in Zig with an array of bytes or as a null-terminated string literal.

```javascript
var s = "hello"; // *const [5:0]u8
var s = [_]u8{'h', 'e', 'l', 'l', 'o'}; // [5]u8
```

You can reference to any byte in the string just like an array:

```javascript
var s = "hello";
s[2] == 'l' // true
```

Or reference to a substring as a slice:

```javascript
s[1..3] == "ell"
s[1..] == "ello"
```

Note that these references are to the bytes not the characters:

```javascript
var s = "Đ";
s[0] == '\c4'
s[1] == '\90'
```

For better Unicode supports, you should look at libraries like [zigstr](https://github.com/jecolon/zigstr) and [ziglyph](https://github.com/jecolon/ziglyph).

You can use the array concatenation `++` operator to combine two strings together:

```javascript
const a = "hello";
const b = "world";
const c = a ++ b;
c == "helloworld" // true
```

Get the length of a string by `.len`:

```javascript
var len = c.len;
len == 10 // true
```

Since Zig is a very simple language, there's nothing such as built-in String type, so you gotta manipulate strings manually, just like C. But you can use some help from `std.mem`.

For example, we can use `std.mem.indexOf` to find the byte offset of some content in a string:

```javascript
var found = std.mem.indexOf(u8, c, "w");
found == 5 // true
```

Or if you want to split a string into multiple substrings, `std.mem.split` will return an iterator for it:

```javascript
var s = "hello world this is a test";
var splits = std.mem.split(u8, s, " ");
while (splits.next()) |chunk| {
  std.debug.print("{s}\n", .{chunk});
}
```

The output would be:

```
hello
world
this
is
a
test
```

When `s` is defined as a string literal, they will be stored as a null-terminated byte array in a global data section in the executable after compilation process. And what you get is a pointer to that byte array `*const [N:0]u8` (`N` is the length of the string and `:0` indicates null termination).

And you can't mutate the literal string's content like this:

```javascript
var s = "good morning";
s[0] = 'm'; // error: cannot assign to constant
```

In order to do so, you must dereference it with `.*` operator, a new copy of the string will be created as an array so you can mutate it:

```javascript
var s = "good morning".*;
s[0] = 'm';
s == "mood morning" // true
std.mem.reverse(u8, s);
s == "gninrom doom" // true
```

Also, you can dynamically create a formatted string with `std.fmt`:

```javascript
const allocator = std.heap.page_allocator;
var distance: i32 = 7857;
var str = std.fmt.allocPrint(allocator, "SJC-SGN Distance = {d} miles", .{distance}) catch "format failed";
```

---

Thank you so much, everyone on [Reddit](https://www.reddit.com/r/Zig/comments/rxmg9p/zig_strings_in_5_minutes/) and [Lobsters](https://lobste.rs/s/nimeia/zig_strings_5_minutes), for the great feedbacks and discussions that helped me improve this article!!!

