I'm getting a lot of memory leaks and I don't know how to fix it

[sharp bridge]

Hey so this is my first language where I don't have a gc, before this I have used rust (which i know also not have a gc but hey we ball) so I don't know how to free stuffs okay? so basically I'm building an interpreted language, and for the BinaryExpression parser I want to make it so that the lhs expression keep holding a reference to itself. now when de-initializing the parser I am recursively freeing every single element of that Expression struct BUT I'M STILL GETTING A GAZZILION OF MEMORY LEAKS AND DOUBLE FREES AND WHAT NOT can someone help me?

This is how I'm creating a binary Expression

    fn createBinaryExpression(self: *Parser, comptime precedentFn: fn (*Parser) anyerror!ParserTypes.Expression, comptime tokens: []const LexerTypes.TokenType) !ParserTypes.Expression {
        var lhs_ptr = try self.allocator.create(ParserTypes.Expression);
        errdefer self.allocator.destroy(lhs_ptr);
        lhs_ptr.* = try precedentFn(self);

        while (self.matchTokens(tokens)) {
            self.currentIndex += 1;
            const operator = self.tokens.items[self.currentIndex].tokenType;
            self.currentIndex += 1;

            const rhs_ptr = try self.allocator.create(ParserTypes.Expression);
            errdefer self.allocator.destroy(rhs_ptr);
            rhs_ptr.* = try precedentFn(self);

            const binary_expr = try self.allocator.create(ParserTypes.Expression);
            errdefer self.allocator.destroy(binary_expr);

            const binaryExprType = try self.allocator.create(ParserTypes.BinaryExpressionType);
            errdefer self.allocator.destroy(binaryExprType);

            binaryExprType.* = .{
                .left = lhs_ptr,
                .right = rhs_ptr,
                .operator = operator,
            };

            binary_expr.* = .{
                .BinaryExpression = binaryExprType,
            };

            lhs_ptr = binary_expr;
        }

        return lhs_ptr.*;
    }

and these are my struct definitions:

const std = @import("std");
const LexerTypes = @import("../lexer/lexer.types.zig");

pub const LiteralExpressionType = union(enum) {
    Number: LexerTypes.Token,
    pub fn deinit(self: *const LiteralExpressionType, allocator: std.mem.Allocator) void {
        defer allocator.destroy(self);
    }
};

pub const BinaryExpressionType = struct {
    left: *Expression,
    right: *Expression,
    operator: LexerTypes.TokenType,

    pub fn deinit(self: *const BinaryExpressionType, allocator: std.mem.Allocator) void {
        self.left.*.deinit(allocator);
        allocator.destroy(self.left);

        self.right.*.deinit(allocator);
        allocator.destroy(self.right);

        allocator.destroy(self);
    }
};

pub const Expression = union(enum) {
    LiteralExpression: *LiteralExpressionType,
    BinaryExpression: *BinaryExpressionType,
    pub fn deinit(self: *const Expression, allocator: std.mem.Allocator) void {
        std.debug.print("FREEING: {} {s}\n", .{ self, @tagName(self.*) });

        switch (self.*) {
            .LiteralExpression => |l| {
                l.deinit(allocator);
            },
            .BinaryExpression => |b| {
                b.deinit(allocator);
            },
        }

        std.debug.print("destroying self: {s}\n", .{@tagName(self.*)});
        allocator.destroy(self);
        std.debug.print("destroyed\n", .{});
    }
};

this also includes how I'm freeing stuffs

[kind island]

You can remove the allocator.destroy(self.left); and allocator.destroy(self.right); in BinaryExpressionType.deinit because Expression.deinit already destroy them

Modified the code a tiny bit and added some prints to showcase what's happening:

const std = @import("std");

pub const LiteralExpressionType = union(enum) {
    Number: i32,
    pub fn deinit(self: *const LiteralExpressionType, allocator: std.mem.Allocator) void {
        std.debug.print("Deinit LiteralExpressionType({*})\n", .{self});
        allocator.destroy(self);
    }
};

pub const BinaryExpressionType = struct {
    left: *Expression,
    right: *Expression,
    operator: i32,

    pub fn deinit(self: *const BinaryExpressionType, allocator: std.mem.Allocator) void {
        std.debug.print("Deinit BinaryExpressionType({*})\n", .{self});
        self.left.*.deinit(allocator);
        std.debug.print("Destroy Expression({*}) is redundant\n", .{self.left});
        //allocator.destroy(self.left);

        self.right.*.deinit(allocator);
        //allocator.destroy(self.right);
        std.debug.print("Destroy Expression({*}) is redundant\n", .{self.right});
        allocator.destroy(self); // Frees self first
    }
};

pub const Expression = union(enum) {
    LiteralExpression: *LiteralExpressionType,
    BinaryExpression: *BinaryExpressionType,
    pub fn deinit(self: *const Expression, allocator: std.mem.Allocator) void {
        std.debug.print("Deinit Expression({*})\n", .{self});
        switch (self.*) {
            .LiteralExpression => |l| {
                l.deinit(allocator);
            },
            .BinaryExpression => |b| {
                b.deinit(allocator);
            },
        }

        std.debug.print("Destroy Expression({*})\n", .{self});
        allocator.destroy(self); // Frees self again
    }
};

[sharp bridge]

even after doing so I'm still getting A LOTTTTT of memory leaks and stuff

[kind island]

With the simple example:

            BinaryExpressionType
           /                    \
          /                      \
LiteralExpressionType    LiteralExpressionType

Deinit Expression(main1.Expression@19a10910020)
Deinit BinaryExpressionType(main1.BinaryExpressionType@19a10a30000)
Deinit Expression(main1.Expression@19a10910000)
Deinit LiteralExpressionType(main1.LiteralExpressionType@19a10a20000)
Destroy Expression(main1.Expression@19a10910000)
Destroy Expression(main1.Expression@19a10910000) is redundant
Deinit Expression(main1.Expression@19a10910010)
Deinit LiteralExpressionType(main1.LiteralExpressionType@19a10a20004)
Destroy Expression(main1.Expression@19a10910010)
Destroy Expression(main1.Expression@19a10910010) is redundant
Destroy Expression(main1.Expression@19a10910020

Destroy Expression is called multiple times on the same pointer:

Destroy Expression(main1.Expression@19a10910000)
Destroy Expression(main1.Expression@19a10910000) is redundant

Well, I might allocate things differently. Can I look at the entire code somewhere (github maybe) ?

[sharp bridge]

yeah sure

https://github.com/ohayouarmaan/flamingo-zig-port

@kind island

[kind island]

Thanks, i'll take a look at it

[sharp bridge]

thanks a lot :D

until then I'll also try to look what's up

[kind island]

How many errors do you get, I only get 1 Invalid Free

[sharp bridge]

yes

same

only 1 invalid free

okay now it's only 1

before it was a lot

lol

[kind island]

still not the best

[sharp bridge]

idk what's up I tried a lot offfff things, I even whipped out gdb to see what's up but I can see that the nodes are being freed in order

[sharp bridge]

yea

:/

I was trying to see which node isn't being freed using gdb and no luck doing that either

[kind island]

On a side note, you probably could reduce the number of pointers imo

[sharp bridge]

OwO I'll keep that in mind

[remote oak]

why not use an arena allocator?

[sharp bridge]

1. because I don't know much about it, and I don't know if using that is the best option here or not
2. I just went with GeneralPurposeAllocator because yeah 😭 It sounded pretty general-purpose to me

[kind island]

That's a good idea @remote oak, but at the same time since he comes from languages with GC I feel like it's a good exercise to understand pointers and such

or i'm maybe wrong ? @sharp bridge

[sharp bridge]

oh so i read a little about it and apparently arenas is basically you putting stuffs in the pool and once you free the allocator everything in it gets freed right?

[remote oak]

A memory arena is like a pool of allocation that you can then allocate all at once. It's a good idea to use one when a lot of allocations have the same lifetime

[remote oak]

yes

[sharp bridge]

I'm pretty comfortable with pointers, but It's my first time dealing with freeing them 😭 before this I had a borrow checker to take care of the lifetime and such

[remote oak]

its actually what is best to use in at least 80% of cases in my experience

[sharp bridge]

OwO

I'll use that as my last resort to be honest, but even right now I don't understand why there are memory leaks :/

[kind island]

Well, not it's not a leak anymore. We free one time more time that we should

[remote oak]

das a double free :D

[sharp bridge]

oh

yeah

makes sense

also

I just changed my gpa to use arena and somehow the errors are gone 😭

[remote oak]

yeah with an arena a free does nothing so you cant have double frees

[sharp bridge]

but that also kind of makes it weird because then we are basically just putting everything in a pool and not freeing it until the end of the execution right? so doesn't that make it kinda bad

[remote oak]

depends on the architecture of the code

[sharp bridge]

okayyy makes sense

[kind island]

I KNOW !!!!

[sharp bridge]

so so so in this kind of case is it a good practice to have a arena for parser separately and freeing it once we don't need it? or should we have a arena throughout the program?

[kind island]

pub const Parser = struct {
    tokens: *const std.ArrayList(LexerTypes.Token),
    program: ParserTypes.Expression, \\ <- This should be a pointer
    allocator: std.mem.Allocator,
    currentIndex: usize,

[sharp bridge]

oh

OH

OH

[kind island]

we are trying to free a stack variable or uninvalid address :')

[sharp bridge]

wait

I'M SO DUMB

WAIT

LEMME TRY IT WITH GPA

[kind island]

Still after that you can use a Arena

[remote oak]

No usually youll have multiple arenas throught your program
basically for short-lived data

[kind island]

you could have arena per file for instance so you can free the all AST in one go

[remote oak]

for example for a video game you might create (or reset) an arena every frame for all the temporary allocations
arena allocations are much cheaper than gpa allocations

[sharp bridge]

oh okayyy makes sense, so basically I can use 1 arena for the whole parser and free it once I am done with the use of AST

and and and once the generation of ast is done I can also memcopy it to some other place and then free the arena which includes other junk data which i don't need

[sharp bridge]

oh okay

makes sense

THANKS A LOT EVERYBODY :D

[kind island]

no problem

That's your toy language ?

[sharp bridge]

OH

WAIT

so so so

even if make that

program as a heap variable

wait

I'm kinda confused

we are returning the value inside of the pointer so we don't have the pointer in the program

self.program is the actual expression

[sharp bridge]

yeah :D I wanna compile it to native assembly in future :3

[kind island]

But self.program.deinit(allocator) expected a allocated pointer to free allocator.destroy(self) in deinit

[sharp bridge]

I had an interpreted version of this written in python

[sharp bridge]

so if i change it to allocator.destroy(&self) it should work?

[kind island]

nope

You should return lhs_ptr not its dereferenced

[sharp bridge]

oh and since I'm returning the inside value of lhs_ptr I'm loosing the reference to it's reference

is that the memory leak?

[kind island]

Yep

Cause lhs_ptr.* returns a copy of the value, "it looses the pointer"

[sharp bridge]

yesssss makes so much sense omg

Thanks a lott :D

[kind island]

can't really do a rust comparaison, haven't done any yet :')

[sharp bridge]

lol I get it dw

THANK YOU SO MUCH

:D

@kind island @remote oak You guys helped a lot :)

[kind island]

If you want, I might have an AST implementation somewhere that I can share with you @sharp bridge. (In my graveyard of projects 🥲)

[sharp bridge]

okay so basically if I'm using a single arena for the parser, I don't really need a deinit function i can just deinit the arena when I'm done right?

I wanna know is it a good practice?

[sharp bridge]

HEY THAT'S SO COOL! I ALSO LOVE TO MAKE LANGUAGES :D IT'S SO FUN

[kind island]

Yep, I'd still include the deinit function if you decide to change allocator later

https://github.com/QuentinTessier/ShadingLanguage/tree/main
https://github.com/QuentinTessier/ShadingLanguage/tree/main/src/AST

Project uses a custom made parser combinator library so the parsing code might be a bit thought to understand but you can go in the Expression.zig file

In AST

[sharp bridge]

what kind of allocator did you use @kind island

[kind island]

Arena

[sharp bridge]

oh

[sharp bridge]

This looks so cool, what is it made for?

[kind island]

Actually, that's old code and I didn't there but I should :')

[kind island]

That's how I structured my AST

The parser searchs for statement first and then expressions

Since Expression will always be allocated, I don't make it's fields pointers

pub const Expression = union(enum(u32)) {
    integer: IntegerLiteral,
    float: FloatLiteral,
    identifier: []u8,
    binary: BinaryExpression,
    prefixUnary: PrefixUnaryExpression,
    postfixUnary: PostfixUnaryExpression,
};

And all nodes express dependency to another node throught a *Expression

pub const PostfixUnaryExpression = struct {
    kind: PostfixUnaryExpressionKind,
    rhs: *Expression,
    type: LazyType,
};

[sharp bridge]

shouldn't the binary be a pointer? because it can hold a reference to another Expression?

[kind island]

Doesn't need to be

[hard oasis]

In his BinaryExpression lhs and rhs are pointers to Expression so it's fine, if it wasn't a pointer type it would not compile

[kind island]

Since you allocate *Expression, you already have the space to store pointer to its children be it a BinaryExpression or a PostfixUnaryExpression ... You don't need to reallocate BinaryExpression inside of the Expression itself