Editing Tracing garbage collection (section)

== Reachability of an object ==

<ref name=":0" />Informally, an object is reachable if it is referenced by at least one variable in the program, either directly or through references from other reachable objects. More precisely, objects can be reachable in only two ways:
# A distinguished set of roots: objects that are assumed to be reachable. Typically, these include all the objects referenced from anywhere in the [[call stack]] (that is, all [[local variable]]s and [[Parameter (computer science)|parameters]] in the functions currently being invoked), and any [[global variable]]s.
# Anything referenced from a reachable object is itself reachable; more formally, reachability is a [[transitive closure]].

The reachability definition of "garbage" is not optimal, insofar as the last time a program uses an object could be long before that object falls out of the environment scope. A distinction is sometimes drawn between [[syntactic garbage]], those objects the program cannot possibly reach, and [[semantic garbage]], those objects the program will in fact never again use. For example:
<syntaxhighlight lang="java">
Object x = new Foo();
Object y = new Bar();
x = new Quux();
/* At this point, we know that the Foo object 
 * originally assigned to x will never be
 * accessed: it is syntactic garbage.
 */

/* In the following block, y *could* be semantic garbage;
 * but we won't know until x.check_something() returns
 * some value -- if it returns at all.
 */
if (x.check_something()) {
    x.do_something(y);
}
System.exit(0);
</syntaxhighlight>

The problem of precisely identifying semantic garbage can easily be shown to be [[decision problem|partially decidable]]: a program that allocates an object <math>X</math>, runs an arbitrary input program <math>P</math>, and uses <math>X</math> if and only if <math>P</math> finishes would require a semantic garbage collector to solve the [[halting problem]]. Although conservative heuristic methods for semantic garbage detection remain an active research area, essentially all practical garbage collectors focus on syntactic garbage.{{Citation needed|date=September 2008}}

Another complication with this approach is that, in languages with both [[reference type]]s and unboxed [[value type]]s, the garbage collector needs to somehow be able to distinguish which variables on the stack or fields in an object are regular values and which are references: in memory, an integer and a reference might look alike. The garbage collector then needs to know whether to treat the element as a reference and follow it, or whether it is a primitive value. One common solution is the use of [[tagged pointer]]s.