Monday 14 January 2013

Improving Finally Block Handling

In my last post I described a heuristic for de-duplicating finally blocks within Java bytecode. Since then I have done some more work on this which is worth writing up.

Cleaning Up My Code

My initial implementation of the heuristic I described can be seen here. This code isn't very clear at all. My initial instinct was to improve this by adding better comments. However, I recently watched a talk which was based on a book called Clean Code which made a very interesting point:

Every Comment is a Failure (This isn't quite a hard and fast rule - comments are sometimes appropriate to express high level design decisions)

In light of this I decided to avoid comments and instead focus on improving the names of types, names of variables and names of functions. Here are some of the examples of changes which I made:
List<Instruction> => Sequence
List<List<Instruction>> => Cluster
List<List<Instruction>> cluster = findCluster(clusters, p); 
=> Cluster cluster = findClusterContainingInsn(clusters, p);
The full diff can be seen here. I think the result is much easier to read but I still need to improve or ideally strip out some of my existing comments. In some places I am still trying to use a comment to describe the following block of code which suggests I should actually be extracting out more methods.

Improving Finally Block Dedup Heuristic

My initial heuristic wasn't quite good enough. Consider the following simple Java code:
    try {
      System.out.println("A");
    } catch (RuntimeException ex) {
      System.out.println("B");
    } finally {
      System.out.println("C");
    }
This compiles to the following bytecode (with catch blocks and coverage probes annotated).
 0 getstatic #16 <java/lang/System.out>
 3 ldc #22 <A>
 5 invokevirtual #24 <java/io/PrintStream.println>
 8 goto 42 (+34)

catch (RuntimeException) => 11

11 astore_1
12 getstatic #16 <java/lang/System.out>
15 ldc #30 <B>
17 invokevirtual #24 <java/io/PrintStream.println>

catch (Anything) => 31

20 getstatic #16 <java/lang/System.out>
23 ldc #32 <C>
25 invokevirtual #24 <java/io/PrintStream.println>

coverageProbe[0] = true

28 goto 50 (+22)

31 astore_2
32 getstatic #16 <java/lang/System.out>
35 ldc #32 <C>
37 invokevirtual #24 <java/io/PrintStream.println>
40 aload_2

coverageProbe[1] = true

41 athrow

42 getstatic #16 <java/lang/System.out>
45 ldc #32 <C>
47 invokevirtual #24 <java/io/PrintStream.println>

coverageProbe[2] = true

50 return
Assuming no exception was thrown coverageProbe[2] would be hit naturally. The finally block dedup heuristic would also mark coverageProbe[1] and coverageProbe[0] as hit. Working backwards from these probes would lead the RuntimeException block to be marked as covered even though no RuntimeException has been thrown.

My solution is to treat copied probes differently. For these probes coverage is only propagated up until a line where the number of Sequence duplicates changes. This prevents coverage from a finally block leaking outside the finally block. This appears to achieve the desired result.

Wednesday 9 January 2013

Java Bytecode - Finally Blocks

In my last post I talked about some new code coverage filters which I have added to my fork of the JaCoCo project. These filters are used at coverage analysis time when the recorded coverage data is analysed against the corresponding class bytecode. In the process of writing these filters I came across the grim truth behind Java finally blocks.

Finally Blocks

It turns out there is no explicit support for this Java language feature so in bytecode it's use has unfortunate consequences. Consider the following Java code:
try {
  try {
    System.out.println("A");
  } catch (RuntimeException ex) {
    System.out.println("B");
  } finally {
    System.out.println("C");
  }
} catch (RuntimeException ex) {
  System.out.println("D");
} finally {
  System.out.println("E");
}
This will end up producing the following bytecode (annotated with line numbers and exception handlers):
try{
try{
try{
try{
L3:
  0 getstatic <java/lang/System.out>
  3 ldc <A>
  5 invokevirtual <java/io/PrintStream.println>
  8 goto 42 (+34)

} catch (RuntimeException) => 11
L4:
 11 astore_1
L5:
 12 getstatic <java/lang/System.out>
 15 ldc <B>
 17 invokevirtual <java/io/PrintStream.println>
} catch (Anything) => 31
L7:
 20 getstatic <java/lang/System.out>
 23 ldc <C>
 25 invokevirtual <java/io/PrintStream.println>
 28 goto 84 (+56)

L6:
 31 astore_2
L7:
 32 getstatic <java/lang/System.out>
 35 ldc <C>
 37 invokevirtual <java/io/PrintStream.println>
L8:
 40 aload_2
 41 athrow

L7:
 42 getstatic <java/lang/System.out>
 45 ldc <C>
 47 invokevirtual <java/io/PrintStream.println>
L8:
 50 goto 84 (+34)

} catch (RuntimeException) => 53
L9:
 53 astore_1
L10:
 54 getstatic <java/lang/System.out>
 57 ldc <D>
 59 invokevirtual <java/io/PrintStream.println>
L12:
 62 getstatic <java/lang/System.out>

} catch (Anything) => 73
 65 ldc <E>
 67 invokevirtual <java/io/PrintStream.println>
 70 goto 92 (+22)

L11:
 73 astore_3
L12:
 74 getstatic <java/lang/System.out>
 77 ldc <E>
 79 invokevirtual <java/io/PrintStream.println>
L13:
 82 aload_3
 83 athrow

L12:
 84 getstatic <java/lang/System.out>
 87 ldc <E>
 89 invokevirtual <java/io/PrintStream.println>
L14:
 92 return
From a code coverage point of view this is a complete nightmare. For any branch within a finally block the number of actual branches in the bytecode is multiplied by the number of times that the finally block is duplicated (at least two). 

Technically this is correct as to cover all the possible paths through the bytecode you must consider all of the possible exception paths. However, in practice the developer is likely only concerned with ensuring that all the branches in their finally blocks are covered at least once and don't want to worry about the possible paths into the finally block. 

Implementing the filtering required to deduplicate coverage of finally blocks is made tricky by the fact that the start/end of the duplicate blocks are not explicitly annotated in any way in the bytecode. The closest I could get was to write a heuristic which works during the analysis of a method:
  • When a new line number marker is seen a new list of instructions is started.
  • Instructions are added to this list as they are seen. The instruction arguments are ignored.
  • After all the instructions in a method have been visited:
    • For each line number which was seen:
      • The instruction sequences seen with that line number are "clustered". Sequences which start with the same instruction are grouped together and assumed to be copies caused by the line being within a finally block.
    • For each covered probe:
      • Find the instruction sequence which contains the probe.
      • Mark the corresponding probe in every other sequence in the cluster as covered.
    • Run the existing probe coverage propagation.
    • For each cluster:
      • If the last instruction of any sequence in the cluster is covered, mark all other sequences in the cluster as covered.
      • Disable coverage reporting for all but one sequence.
This (relatively) simple heuristic is good enough to work in most cases. However it is straightforward to come up with code which will trip this up:
int i = 0;
for (i++; i < 10; i++) {
  System.out.println("A");
}
This produces the following bytecode:
L1:
  0 iconst_0
  1 istore_1
L2:
  2 iinc 1 by 1
  5 goto 19 (+14)
L3:
  8 getstatic #16 <java/lang/System.out>
 11 ldc #22 <A>
 13 invokevirtual #24 <java/io/PrintStream.println>
L2:
 16 iinc 1 by 1
 19 iload_1
 20 bipush 10
 22 if_icmplt 8 (-14)
L5:
 25 return
There are two blocks of code tagged as being on line 2 and they both start with the same instruction. With my heuristic in place one of these blocks will be ignored as they are assumed to be duplicates. This is a shame but in practice I have yet to think of an example of realistic code which would be matched by my heuristic.

Conclusions

I'm pleased that my heuristic works as well as it does but I would love to come up with a better mechanism. If you have any suggestions I would love to hear them!

Java Code Coverage: Filtering out the noise

Code Coverage is a measure of how much of your code has been executed. This is usually measured while running unit tests as a way of tracking how much production code is being exercised. It is important to note that high code coverage doesn't give any guarantee that the behaviour of the covered code is actually being asserted on by your unit tests but it is a useful indicative measure.

However, there are a couple of serious drawbacks with most simple code coverage tools.

Implicit Code

Java source code is compiled to bytecode before being executed. The most common mechanism for tracking Java code coverage is to instrument this bytecode. The problem with this approach is that it can lead to reporting of coverage (or lack of) for elements which are not present in the actual Java source code. This is frustrating as it either lowers the overall code coverage figure or forces a developer to write pointless extra tests.

Examples:
  • Classes without an explicit constructor have an implicit no-args constructor.
  • Enum classes have implicit values() and valueOf(String) methods.
  • Synchronized(object) {} blocks are implemented in bytecode by duplicating the instructions for releasing the lock inside and outside of a catch block. This would naively require an exception to be thrown from within every synchronized block to achieve full coverage.
  • All finally {} blocks are implemented in bytecode by duplicating blocks of instructions possibly several times. This would naively require every branch within the finally block to be exercised for every duplicate.
Uncovered Code

It is commonly acknowledged that 100% code coverage is an expensive goal to attempt to reach. This is usually because getting the final 5-10% code coverage involves writing pointless extra tests that add little real value and can require production code to be distorted to support the pointless extra tests.

JaCoCo

JaCoCo is an open source Java Code Coverage tool which is in active development. It is a mature project and since late 2011 has been the library behind the popular Eclipse plugin EclEmma.

Over the last few months I have been working to add some key features to this library to address the concerns discussed above.

I have updated JaCoCo to automatically filter out coverage of all of the following:
  • Implicit no-args constructors.
  • Implicit enum methods.
  • Synchronization exit handling.
  • Finally block code duplication.
I have also added support for source directives that allow blocks of code to be explicitly excluded from code coverage reports. This addresses the issue of uncovered code and allows developers to explicitly mark blocks of code which are deliberately not being covered by unit tests.

All of these changes are ready to try out now by downloading the release of my JaCoCo fork from the link below.

I am working with the JaCoCo developers to get my changes accepted back into the core JaCoCo project.

More Information

http://mchr3k.github.com/jacoco/