Garbage collector does not appear to work, marks everything(?) instead

[Cuber01]

Reproduction

According to the book, running the following sample code, should clear "first value", however, it does not.

var a = "first value";
a = "updated";
// GC here.
print a;

I added collectGarbage() at line 552 in vm.c, so that the garbage collector runs every time OP_SET_GLOBAL is executed.

It does run, yet still marks "first value". Here's the relevant output:

0004    2 OP_CONSTANT         3 'updated'
          [ <script> ][ updated ]
0006    | OP_SET_GLOBAL       2 'a'
-- gc begin
0x55d0f8491c20 mark <script>
0x55d0f8491c70 mark updated
0x55d0f8491b30 mark a
0x55d0f8491800 mark clock
0x55d0f8491830 mark <native fn>
0x55d0f84916d0 mark init
0x55d0f84916d0 blacken init
0x55d0f8491830 blacken <native fn>
0x55d0f8491800 blacken clock
0x55d0f8491b30 blacken a
0x55d0f8491c70 blacken updated
0x55d0f8491c20 blacken <script>
0x55d0f8491ac0 mark <script>
0x55d0f8491ac0 blacken <script>
0x55d0f8491bd0 mark first value
0x55d0f8491bd0 blacken first value
-- gc end
   collected 0 bytes (from 769 to 769) next at 1538
          [ <script> ][ updated ]
0008    | OP_POP
          [ <script> ]
0009    4 OP_GET_GLOBAL       4 'a'
          [ <script> ][ updated ]
0011    | OP_PRINT
updated
          [ <script> ]
0012    | OP_NIL
          [ <script> ][ nil ]
0013    | OP_RETURN
0x55d0f8491c20 free type 2
0x55d0f8491c70 free type 6
0x55d0f8491bd0 free type 6
0x55d0f8491b30 free type 6
0x55d0f8491ac0 free type 3
0x55d0f8491830 free type 5
0x55d0f8491800 free type 6
0x55d0f84916d0 free type 6

What (I think) is the problem

In my own garbage collector, made mostly according to the book, I have a similar problem. Here's the cause:

In the collectGarbage->markRoots loop we mark the entire stack, including the global <script> function that gets pushed onto it at the start of execution:

for (Value* slot = vm.stack; slot < vm.stackTop; slot++)
{
    markValue(*slot); 
}

After marking our objects, in traceRefrences we do:

while (vm.grayCount > 0)
{
    Obj* object = vm.grayStack[--vm.grayCount];
    blackenObject(object);
}

and blacken object does the following to our global function:

case OBJ_FUNCTION:
{
    ObjFunction* function = (ObjFunction*)object;
    markObject((Obj*)function->name);
    markArray(&function->chunk.constants);
    break;
}

This way, we mark all constants in the global function. We also mark all constants in functions declared in the global function and so on and so on. Therefore, the garbage collector marks every single constant in the entire program, including both "first value" and "updated".

Ending remarks

This may be a misunderstanding on my part (in which case, please prove me wrong). After running a direct example from the book, using code that was also 1:1 from the book, I believe it was justified to open an issue here.

[munificent]

Yes, your understanding is correct. The memory for that string could be freed (as the text of the book says) but our actual clox implementation doesn't free in this case for the reason you describe.

[Cuber01]

Well, but in this case doesn't it render the entire garbage collector worthless? Could you share an example piece of code in which the garbage collector does free something at runtime?

This way, we mark all constants in the global function. We also mark all constants in functions declared in the global function and so on and so on.

To my understanding, pretty much everything we want to free is a constant at one point, ergo they're always marked for the reason stated above.

[HallofFamer]

It doesn’t. If you create other heap objects, the GC will free them when they are out of scope. One exception is with global variables as they are never ‘out of scope’, another exception is with strings because Lox interns every string, no string will be garbage collected. It seems you have a confusion on string interning.

[Cuber01]

I can see that now. With this in mind I managed to create a sample that actually works:

class A
{

}

A(); // instance 1

A(); // instance 2 - GC is triggered at this point and frees instance 1 

Thank you both, and thanks for the amazing book.