#Memory confusion

1 messages · Page 1 of 1 (latest)

stone yoke
#

This is could be a very basic thing that I still haven't got the grips of. I'm basically seeing two different outputs depending on where I log the struct, and I'm not exactly sure why.

Here's the main part of this code, and the confusion is around the output of the method next_token.

pub const Lexer = struct {
  input: string,
  position: usize = 0,
  read_position: usize = 0,
  ch: u8 = 0,

  const Self = @This();

  pub fn init(input: string) Self {
    var l = Self{
      .input = input,
    };

    l.read_char();

    return l;
  }

  // Reads the next character if possible
  fn read_char(self: *Self) void {
    if (self.read_position >= self.input.len) {
      self.ch = 0; 
    } else {
      self.ch = self.input[self.read_position];
    }

    self.position = self.read_position;
    self.read_position += 1;
  }

  fn skip_whitespace(self: *Self) void {
    while (
      self.ch == ' ' or self.ch == '\t' or self.ch == '\n' or self.ch == '\r'
    ) {
      self.read_char();
    }
  }

  pub fn next_token(self: *Self) token.Token {
    self.skip_whitespace();

    var tok = switch (self.ch) {
      // ---snip---
      ')' => new_token(token.RPAREN, self.ch),
      // ---snip---
    };
    
    self.read_char();

    std.debug.print("Before return: {any}\n", .{tok.literal});
    defer std.debug.print("After return: {any}\n", .{tok.literal});

    return tok;
  }
}

fn new_token(token_type: token.TokenType, ch: u8) token.Token {
  const literal = [_]u8{ ch };
  return token.Token{ .token_type = token_type, .literal = &literal};
}

And here's what the invocation site looks like:

pub fn main() !void {
  var my_lexer = lexer.Lexer.init(")");
  const test_token = my_lexer.next_token();
  std.debug.print("At invocation: {any}\n", .{test_token.literal});
}

And this is my output:

> zig build run
Before return: { 41 }
After return: { 41 }
At invocation: { 0 }
#

I'm not quite sure if I'm referencing something that is getting destroyed, and if so I'm not sure how to copy things properly so this doesn't happen.

high quartz
#

the ")" dies after init finishes calling

#

read_char its still alive

#

you need to use an allocator and keep the string alive

#

does that make sense? I can go into more detail

stone yoke
#

Yes please!

high quartz
#

in this specific case though, you could put:

pub fn main() !void {
  var str = ")";
  var my_lexer = lexer.Lexer.init(str);
  const test_token = my_lexer.next_token();
  std.debug.print("At invocation: {any}\n", .{test_token.literal});
}
#

and it would stay alive long enough for test_token

#

next_token*

#

the way our initial function was working, you passed a value that lives the length of init and then the data is naturally thrown away

stone yoke
#

So I've tried that before and it's still the same. I can see that the my_lexer struct still holds ")"

high quartz
#

Can you show me the TokenType enum?

stone yoke
#

I've added these debug lines:

pub fn main() !void {
  var tok = ")";
  var my_lexer = lexer.Lexer.init(tok);
  std.debug.print("My lexer before: {any}\n", .{my_lexer});
  const test_token = my_lexer.next_token();
  std.debug.print("My lexer after: {any}\n", .{my_lexer});
  std.debug.print("At invocation: {any}\n", .{test_token.literal});
}

And this is the output:

❯ zig build run
My lexer before: lexer.lexer.Lexer{ .input = { 41 }, .position = 0, .read_position = 1, .ch = 41 }
Before return: { 41 }
After return: { 41 }
My lexer after: lexer.lexer.Lexer{ .input = { 41 }, .position = 1, .read_position = 2, .ch = 0 }
At invocation: { 0 }
#

Yeah sure, gimme a sec

#

TokenType and string are just an alias to []const u8

#

I'll be honest, I'm not exactly sure if that was the right approach

high quartz
#

oh oh

#

I see the problem

#

its still a UAF problem

#

but at a diff line

# 
fn new_token(token_type: token.TokenType, ch: u8) token.Token {
  const literal = [_]u8{ ch };
  return token.Token{ .token_type = token_type, .literal = &literal};
}
#

Look at what is happening here

#

you are creating the literal slice IN new_token

#

and trying to use its pointer

#

but the slice will die after new_token ends

#

if you don't reference it as a pointer

#

you could pass the slice as a copy

#

but the pointer won't copy to the data if the data dies

#

the data is going to die no matter what, BUT if you pass the slice directly it will make a copy in token.Token

#

Also I use:

'''ts

to add color as it makes it 10x easier to read

#

anytime you want to manipulate/use data with pointers, make sure the data itself lives at a higher level than than a function call or any { bracket use.

#

Also another gotcha:
If you are using an allocator with something like ArrayList(u8). any resize kind of function like arrayList.append(5) (assuming the capacity has to grow) the pointers will all become invalid.

stone yoke
stone yoke
stone yoke
#

Also, do you reckon that the string literal implementation is the best way forward or should I look to use a proper heap allocated String (not sure how to do this since I’ve always had access to something like this working in c++, rust and other higher level languages)

median marsh
#

Craig is correct with the &literal diagnosis I think, but there is no way to pass a slice to a function without pointing to something - and in your case, you can't do that without putting aside some space for it.

#

In this particular case, you could do one of two things.

  1. const lit = try allocator.alloc(u8, 1); lit[0] = ch; return Token{ .literal = lit };
  2. Intern all characters that you want to be able to return (or at least ASCII ones) and then always return a string that comes from the interned data.
    In this case, you could do something like this for the interner:
const chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
// This string has every letter of the ASCII alphabet.

pub fn charToString(c: u8) []const u8 {
    for (chars, 0..) |e, i| {
        if (e == c) {
            return chars[i..][0..1];
        }
    }
    @panic("charToString(): letter is not part of ASCII");
}
#

You could imagine trying to use the ordinal values instead of using a loop to scan for the character.

stone yoke
#

Would the allocator approach be the equivalent of using a heap allocated string in other languages?

#

I’ve not written any C so I don’t yet have an intuition of what to use where and how to structure the code

#

Would the allocator approach be the equivalent of using a heap allocated string in other languages?
For example, if this is the approach then where would I put the allocator? Would it have to be in main and get passed in to the Lexer.init? Or would I pass it into the next_token method?

median marsh
#

Allocator doesn't define where the memory that it returns can come from; so you can make an allocator that returns stack memory, for example.

#

As such, "heap allocations" is only really useful to describe allocation requests that you put to the OS itself - which is a small part of what an Allocator can do in Zig.

#

But yes - a good rule of thumb is that if you use an allocator, you give the Lexer an allocator when you init one, and then it uses that allocator for whatever it needs to.
You then might provide a Lexer.deinit which will deallocate everything that it allocated.

#

What I like about the charToString approach though, is that none of those returned strings will be allocated; they all point to memory that is static - that lives for the entire duration of the exe. And thus, basically avoids the need for any memory management.

#

The other thing in general, is that you should generally avoid allocating a lot of small things, because that makes for a harder, and slower, memory management solution.
In GC'd languages, they just do 1,000 frees, if you allocate 1,000 things. (Not quite - but you get the idea.)
NOTE: Anything with RAII also suffers this problem, incidentally; potentially even worse, depending on how its done.
The simplest way to make things faster, is to allocate large blocks of memory, and then divvy it up afterwards instead, as this means that you only need one free in order to destroy everything within that block.

stone yoke
#

Ah I see I see! That’s extremely insightful thank you

median marsh
#

In the charToString case, as I said, no memory allocation - thus no freeing.
But if the possible characters were hypothetically picked at runtime, then you could allocate a block big enough to hold them all, and just use that block instead of the static string. And now you just free that one string (read: block) at the end, instead of making a one-char-long string for each one, and freeing each one individually at the end.

#

Each allocation request involves doing a bunch of work, and thus, is generally slow - and thus you want to avoid it; batch them up into bigger blocks, as I said.
Even more so if you're asking the OS itself every time, of course.

median marsh
#

Though, to be clear, this is unnecessary if the chars that this func is dealing with will only ever be ASCII.

median marsh
# median marsh The other thing in general, is that you should generally avoid allocating a lot ...

Speaking to this further, the primary purpose of having different allocator types that you can use (Allocator is not an allocator itself; merely the 'interface value' that you can use in order to interact with one) -- the primary purpose is to allow you to switch up the allocation strategy at will, to suit your usecase; allocating in big blocks is a simple example, but so is "I want to know if I haven't freed all my shit", or ["I want to be able to allocate and free in a random order,"], or "I want to allocate a bunch, compute a result, and free everything at the end", etc.

#

[The latter is a particularly good example of such a strategy, and it] is typically called an "arena", which can be found in Zig's stdlib as std.heap.ArenaAllocator.
It's ultimately all about tradeoffs, and knowing which ones you want to make.
In arena's case:

  • Cheap to allocate. (Not thread safe, and the algorithm to allocate is simple and fast; there's minimal bookkeeping.)
  • Cannot free or resize an individual allocation, unless it's the very latest one you've made.
#

About that thread-safety one, incidentally: It's much slower to have it, you don't typically need this, and can always add it on yourself, externally, if needed.

#

Arena's are also useful in that they can be reset, which doesn't free the memory block they allocated, but means that future allocations will reuse that block of memory; as if any previous allocations with that arena never happened.
Very useful if you have a main loop and want to store some stuff that's temporary, for example; things like that FPS: 32 in games.

#

But now I'm rambling - hopefully it makes sense 🤣

stone yoke
#

I picked up Zig thinking it’d be very similar to Rust and I suppose you could do the things you can do in Zig there but it feels so much deeper on day 1 (it’s literally my first whole day with it 😅)

#

It’s both overwhelming and very refreshing because it feels like everything is on the surface

#

And the community! God maybe if I had this kind of help with my very noobish questions when I started with Rust m, I’d be further along (not a dig at them or anything, I’m finding the Zig community really welcoming and friendly)

#

Thank you so much for being patient with me and expanding on things so much! I’ve learnt so much already ❤️

median marsh
stone yoke
#

Ah fair fair

median marsh
#

Zig just assumes you are going to be doing memory unsafe things because you know what you're doing. Though, it does have some safety features that are more oriented to that case.
Things like uninitialized values being memset to 0xaa "screaming bytes" in debug and release-safe build modes, for example.

median marsh
stone yoke
stone yoke
median marsh
#

One thing I actually would say is that Zig has non-null pointers by default.
However, I would make the observation that almost all of the pointer-related problems that I have in real code, are invalid pointers, not null pointers.
Not that they aren't useful though; it does make the code self-documenting to an extent, and there is nice syntax for handling nulls - if it could be somehow extended to invalid ones though, that'd be cool. 😄

stone yoke
#

What are non-null pointers?

median marsh
median marsh
#

But invalid pointers point to a non-zero address - it's just that address doesn't actually have what it claims to anymore, for some reason.

#

Like if it's been freed, for example.

stone yoke
#

Does that mean pointers have a default value?

median marsh
#

Pointers don't have in Zig; indeed, nothing in Zig has a default value.

#

You cannot do the equivalent of let v; in Rust.

stone yoke
median marsh
#

A pointer type is just *T, but an optional one is ?*T.
And optional just means can be null, or contain a value.

#

Zig actually has several different kinds of pointer types; the *T is the simplest: a single-item pointer, which points to one thing, and one thing only.

#

There's also multi-item pointers, which just point to, say, the first item out of ten items, somewhere in memory.

#

Multi-item pointers can be indexed, as a result.

#

But they don't have any bounds checking.

#

Slices are a structure, like Go, that consist of a multi-item pointer, and a usize; the element count - and they do have bounds checking, using that count.

stone yoke
median marsh
#

But yeah - ?T is semantically the same as Option<T>.
Though, ?*T and *T are special-cased to be the same in memory. (Same if it's a multi-pointer.)
Whereas T vs ?T are different in memory.

stone yoke
median marsh
#

And there's also .? for .unwrap().

#

You can also use if (optional) |inner| {} as well, of course.

stone yoke
median marsh
#

Which is the same as if let Some(inner) = optional in Rust.

median marsh
median marsh
#

In Rust, it---to my knowledge---always panics in Rust if its empty.

#

In Zig, it is logically orelse unreachable.

#

unreachable is UB in unsafe modes, ReleaseFast and ReleaseSmall.

#

But it is a panic in Debug and ReleaseSafe.

#

UB, because the optimizer is instructed to use it.

stone yoke
#

What’s UB?

median marsh
#

Undefined Behaviour.

stone yoke
#

Ahhh!

median marsh
#

It means, "the optimizer is allowed to assume this won't ever happen."

stone yoke
#

Makes sense

stone yoke
median marsh
#

Personally, I'd probably have preferred that Zig didn't do this -- I generally think that hardware-defined behaviour, or OS-defined behaviour, is the worst you should do, but still. 😄

stone yoke
#

If the whole function returned a Result, you could just use “?” Instead of unwrap and it’ll return the error

median marsh
#

Right - Rust's 'try' operator works on optionals too, eh.

#

Zig's try only works on error unions.

stone yoke
#

I think so

#

Sorry to use you as the docs (I’m finding it a tad tricky to navigate that because I don’t have the language down to search for what I want), but what does it mean when a function returns “!u8” or “anyerror!u8”?

#

What does the exclamation mean? Does it mean that it can potentially throw?

median marsh
#

The thing on the left is the errorset, the set of all errors that can be returned.

#

This is used for exhaustive switching on the error if there is one.

#

If you just have !u8, then it means that the set is inferred based on what is tryd in the body.

#

An errorset looks like error{A,B,C,D} if you write one out explicitly, and an error is literally just a u16 behind the scenes.

#

The design comes from the idea that in C, you often return an error code as your only return value.

#

It's basically just an enum.

#

You can also make a set that combines multiple others using error{A,B} || error{C,D}.

stone yoke
#

Ah okay cool cool! That makes sense

#

That is what I suspected but I couldn't yet find an explanation for it in the official documentation

stone yoke
#

One tiny thing that I noticed was the indexed for loop syntax no longer worked and I had to just use for (chars) |e, i| { ... }. Do you think I should raise a PR for this to update the docs? https://ziglang.org/documentation/master/#for

median marsh
median marsh
#

When I said about how you want to minimize allocations, that of course is even better when they are completely eliminated - as they are in that approach - which is nice too!

stone yoke
#

Has it been changed for the test version up?

median marsh
#

Yeah - it's a master feature; the syntax you gave used to be correct, but multi-object for loops were added, so it became ambiguous.

stone yoke