What is Liveness in JavaScript?

Trying to examine intricacies of JavaScript GC, I got deep into the weeds (that is, into the ECMAScript spec). It was found by me that an object should not be collected as long as it is deemed “live”. And liveness itself is defined as follows:

At any point during evaluation, a set of objects S is considered live if either of the following conditions is met:

• Any element in S is included in any agent’s [[KeptAlive]] List.
• There exists a valid future hypothetical WeakRef-oblivious execution with respect to S that observes the Object value of any object in S.

The [[KeptAlive]] list is appended with an object once a special WeakRef is created, which (weakly) refers to it, and emptied after the current synchronous job ceases. However, as for WeakRef-oblivious execution, I fail to get my mind around what it is:

For some set of objects S, a hypothetical WeakRef-oblivious execution with respect to S is an execution whereby the abstract operation WeakRefDeref of a WeakRef whose referent is an element of S always returns undefined.

WeakRefDeref of a WeakRef returns undefined when its referent was collected already. Am I getting it right that it is implied here that all objects that make up S should be collected? So the notion of a future hypothetical WeakRef-oblivious execution is that there is still an object, an element of S, which not collected yet and observed by some WeakRef.

It all still makes little sense for me. I would appreciate some samples.

Answer

Let’s ignore the formalised, but incomplete, definitions. We find the actual meaning in the non-normative notes of that section.¹

What is Liveness in JavaScript?

Liveness is the lower bound for guaranteeing which WeakRefs an engine must not empty (note 6). So live (sets of) objects are those that must not be garbage-collected because they still will be used by the program.

However, the liveness of a set of objects does not mean that all the objects in the set must be retained. It means that there are some objects in the set that still will be used by the program, and the live set (as a whole) must not be garbage-collected. This is because the definition is used in its negated form in the garbage collector Execution algorithm²: At any time, if a set of objects S is not live, an ECMAScript implementation may³ […] atomically [remove them]. In other words, if an implementation chooses a non-live set S in which to empty WeakRefs, it must empty WeakRefs for all objects in S simultaneously (note 2).

Looking at individual objects, we can say they are not live (garbage-collectable) if there is at least one non-live set containing them; and conversely we say that an individual object is live if every set of objects containing it is live (note 3). It’s a bit weird as a “live set of objects” is basically defined as “a set of objects where any of them is live”, however the individual liveness is always “with respect to the set S“, i.e. whether these objects can be garbage-collected together.

_{1: This definitely appears to be the section with the highest notes-to-content ratio in the entire spec.
2: emphasis mine
3: From the first paragraph of the objectives: “This specification does not make any guarantees that any object will be garbage collected. Objects which are not live may be released after long periods of time, or never at all. For this reason, this specification uses the term “may” when describing behaviour triggered by garbage collection.“}

---

Now, let’s try to understand the definition.

At any point during evaluation, a set of objects S is considered live if either of the following conditions is met:

• Any element in S is included in any agent’s [[KeptAlive]] List.
• There exists a valid future hypothetical WeakRef-oblivious execution with respect to S that observes the Object value of any object in S.

The first condition is pretty clear. The [[KeptAlive]] list of an agent is representing the list of objects to be kept alive until the end of the current Job. It is cleared after a synchronous run of execution ends, and the note on WeakRef.prototype.deref⁴ provides further insight on the intention: If [WeakRefDeref] returns a target Object that is not undefined, then this target object should not be garbage collected until the current execution of ECMAScript code has completed.

The second condition however, oh well. It is not well defined what “valid”, “future execution” and “observing the Object value” mean. The intuition the second condition above intends to capture is that an object is live if its identity is observable via non-WeakRef means (note 2), aha. From my understanding, “an execution” is the execution of JavaScript code by an agent and the operations occurring during that. It is “valid” if it conforms to the ECMAScript specification. And it is “future” if it starts from the current state of the program.
An object’s identity may be observed by observing a strict equality comparison between objects or observing the object being used as key in a Map (note 4), whereby I assume that the note only gives examples and “the Object value” means “identity”. What seems to matter is whether the code does or does not care if the particular object is used, and all of that only if the result of the execution is observable (i.e. cannot be optimised away without altering the result/output of the program)⁵.
To determine liveness of objects by these means would require testing all possible future executions until the objects are no longer observable. Therefore, liveness as defined here is undecidable⁶. In practice, engines use conservative approximations such as reachability⁷ (note 6), but notice that research on more advanced garbage-collectors is under way.

Now for the interesting bit: what makes an execution “hypothetical WeakRef-oblivious with respect to a set of object S“? It means an execution under the hypothesis that all WeakRefs to objects in S are already cleared⁸. We assume that during the future execution, the abstract operation WeakRefDeref of a WeakRef whose referent is an element of S always returns undefined (def), and then work back whether it still might observe an element of the set. If none of the objects to be can be observed after all weak references to them are cleared, they may be garbage-collected. Otherwise, S is considered live, the objects cannot be garbage-collected and the weak references to them must not be cleared.

_{4: See the whole note for an example. Interestingly, also the new WeakRef(obj) constructor adds obj to the [[KeptAlive]] list.
5: Unfortunately, “the notion of what constitutes an “observation” is intentionally left vague” according to this very interesting es-discourse thread.
6: While it appears to be useless to specify undecidable properties, it actually isn’t. Specifying a worse approximation, e.g. said reachability, would preclude some optimisations that are possible in practice, even if it is impossible to implement a generic 100% optimiser. The case is similar for dead code elimination.
7: Specifying the concept of reachability would actually be much more complicated than describing liveness. See Note 5, which gives examples of structures where objects are reachable through internal slots and specification type fields but should be garbage-collected nonetheless.
8: See also issue 179 in the proposal and the corresponding PR for why sets of objects were introduced.}

---

Example time!

It is hard to me to recognize how livenesses of several objects may affect each other.

WeakRef-obliviousness, together with liveness, capture[s the notion] that a WeakRef itself does not keep an object alive (note 1). This is pretty much the purpose of a WeakRef, but let’s see an example anyway:

{
    const o = {};
    const w = new WeakRef(o);
    t = setInterval(() => {
        console.log(`Weak reference was ${w.deref() ? "kept" : "cleared"}.`)
    }, 1000);
}

^{(You can run this in the console, then force garbage collection, then clearInterval(t);)}

[The second notion is] that cycles in liveness does not imply that an object is live (note 1). This one is a bit tougher to show, but see this example:

{
    const o = {};
    const w = new WeakRef(o);
    setTimeout(() => {
        console.log(w.deref() && w.deref() === o ? "kept" : "cleared")
    }, 1000);
}

Here, we clearly do observe the identity of o. So it must be alive? Only if the w that holds o is not cleared, as otherwise … === o is not evaluated. So the liveness of (the set containing) o depends on itself, with circular reasoning, and a clever garbage collector is actually allowed to collect it regardless of the closure.

To be concrete, if determining obj's liveness depends on determining the liveness of another WeakRef referent, obj2, obj2‘s liveness cannot assume obj's liveness, which would be circular reasoning (note 1). Let’s try to make an example with two objects that depend on each other:

{
    const a = {}, b = {};
    const wa = new WeakRef(a), wb = new WeakRef(b);
    const lookup = new WeakMap([[a, "b kept"], [b, "a kept"]]);
    setTimeout(() => {
        console.log(wa.deref() ? lookup.get(b) : "a cleared");
        console.log(wb.deref() ? lookup.get(a) : "b cleared");
    }, 1000);
}

The WeakMap primarily serves as something that would observe the identity of the two objects. Here, if a is kept so wa.deref() would return it, b is observed; and if b is kept so wb.deref() would return it, a is observed. Their liveness depends on each other, but we must not do circular reasoning. A garbage-collector may clear both wa and wb at the same time, but not only one of them.

Chrome does currently checks for reachability through the closure so the above snippet doesn’t work, but we can remove those references by introducing a circular dependency between the objects:

{
    const a = {}, b = {};
    a.b = b; b.a = a;
    const wa = new WeakRef(a), wb = new WeakRef(b);
    const lookup = new WeakMap([[a, "b kept"], [b, "a kept"]]);
    t = setInterval(() => {
        console.log(wa.deref() ? lookup.get(wa.deref().b) : "a cleared");
        console.log(wb.deref() ? lookup.get(wb.deref().a) : "b cleared");
    }, 1000);
}

To me, note 2 (WeakRef-obliviousness is defined on sets of objects instead of individual objects to account for cycles. If it were defined on individual objects, then an object in a cycle will be considered live even though its Object value is only observed via WeakRefs of other objects in the cycle.) seems to say the exact same thing. The note was introduced to fix the definition of liveness to handle cycles, that issue also includes some interesting examples.