How does JTombstone work?

Java class files, regardless of what machine they are compiled or run on, have a well know format, specified in the Java VM Spec. JTombstone reads each of the class files used by a program, and finds all the references between classes and methods. Part of the input given to the program is a list of root methods. Starting with this list as a base, it tries to find all the methods that get called at one point or another. Anything that is found by this method is assumed to be dead.

In fact, the method it uses is a bit more complex than that. It actually keeps two lists of methods - rooted methods those on the list of root methods, or who are called via a simple chain of calls, and inherited methods, those that are called via an instance method that is subclassed. An example of this would be a call to String.equals. Depending on the calling code, the call may appear as a call to Object.equals, but if the object is of type String, then String.equals will get called. In this case JTombstone would say that if any String constructor was called that String.equals is an inherited method. Note that JTombstone does not count calls to constructors from subclass constructors as creating an instance of the superclass.

There is another categorization of liveliness, which is detected when the class files are read in, namely constant. Java compilers are allowed to, and typically do compile out references to static final member data initialized by a constant (e.g. static final String myString = "abc";). If this member is not private, and is referred to by another class, the class may indeed be alive, even though there is no evidence in any of the class files to support this. Classes with such data members are marked as having life type constant, unless they have method or member data references that qualify them to be rooted or inherited.

The algorithm works as follows:

1. The list of rooted members is defined to be the list of root members. All of these members are marked as unchecked. The list of inherited members is initially empty.
2. The list of methods that are called from one unchecked method are used to find other rooted and inherited methods. A member once on the inherited list may be moved to the rooted list, but once a member has been established to be rooted it is always rooted. Newly found members are marked as unchecked. After all calls to other methods have been analyzed, a method is marked as checked.
3. Repeat step 2 until all rooted members have been checked.
4. Repeat step 2 for inherited members, until they all have been checked. This time any method found is assumed to be inherited, since it is connected via an inherited method.

Any method not found by the above algorithm is assumed to be dead.

Some additional rules are used to classify methods, and, in particular classes.

1. If a method is found to have a given type of life, its class will have that type of life or higher.
2. If a class is found to be inherited or rooted, then the following are as well.
   1. Its static constructor.
   2. All imported classes (this handles member data references).
   3. All superclasses.
   4. All implemented interfaces.

This algorithm does a far from perfect job of finding dead code. See the Limitations page.

JTombstone Home