Java branch coverage gives wrong results with finally blocks.

[c-mita]

Branch coverage results may not be consistent when branches in a finally bock exist.

Consider the following:

static int secret = 0;

public static int foo(int x) {
  try {
    if (x == 1 || x == -1) {
      throw new RuntimeException();
    }
    if (x % 2 == 0) return 2 * x;
    else return 2 * x + 1;
  } finally {
    if (x >=0) secret++;
    else secret--;
  } 
}

There are three sets of branches - four for the first if (call it line 5), two for the second if (line 8), and 6 for the if in the finally block (line 11). (The reason there are 6 for the finally block is because it is duplicated by the java compiler to account for the three possible paths into it).

A coverage run when this is called with foo(-1) should cause two branches in the first if block to be taken (the second and third), none in the second if block, and one in the final if block. That is, we expect the following result:

BRDA:5,0,0,0
BRDA:5,0,1,1
BRDA:5,0,2,1
BRDA:5,0,3,0
BRDA:8,0,0,-
BRDA:8,0,1,-
BRDA:11,0,0,0
BRDA:11,0,1,0
BRDA:11,0,2,0
BRDA:11,0,3,0
BRDA:11,0,4,0
BRDA:11,0,5,1
BRF:12
BRH:3

Instead, the following is observed:

BRDA:5,0,0,0
BRDA:5,0,1,1
BRDA:5,0,2,1
BRDA:5,0,3,1
BRDA:8,0,0,0
BRDA:8,0,1,1
BRDA:11,0,0,0
BRDA:11,0,1,0
BRDA:11,0,2,0
BRDA:11,0,3,0
BRDA:11,0,4,0
BRDA:11,0,5,1
BRF:12
BRH:5

This report suggests that a branch in the middle if block is being taken, and that three of the branches in the first are being taken, that we simultaneously satisfy x == -1 and x != 1 && x != -1 (which is obviously incorrect).

The line coverage part of the report (the DA lines) are reported correctly; this only affects the branch coverage part of the report.

A simple reproduction is here: https://github.com/c-mita/bazel_issues/tree/master/java_try_finally_coverage/foo (added in c-mita/bazel_issues@8d10f8d)

[c-mita]

I believe the problem lies here:
https://cs.opensource.google/bazel/bazel/+/0741ccd274a16c7b26548a6e6c924d52aa1fea56:src/java_tools/junitrunner/java/com/google/testing/coverage/MethodProbesMapper.java;l=427

That is, the merging of BranchExp objects within a line is done in place. What follows is me trying to explain why I think this is wrong.

Instruction objects (representing Java bytecode instructions) are mapped to CovExp objects.

A CovExp is either a ProbeExp (representing an single Jacoco probe which, when evaluated, returns True or False depending on whether the probe was hit during execution) or a BranchExp (representing a set of branches which evaluates to True if any of its children evaluate to True).

A BranchExp is essentially a list of CovExp objects representing the individual branches and forms a tree if any of the CovExp objects are also BranchExp objects.

The initial construction of these objects is not important (and appears to be done correctly). A second merging step occurs to create a single BranchExp for each source line with a branch; here is when things go wrong.

Initially we might have trees that looks like this:

# For line 8 (the second if block)
BranchExp( # representing branch on line 8)
  Probe, # indicating we satisfied the if condition)
  BranchExp( # representing branch on line 11)
    Probe, # first branch taken in first copy of finally block)
    Probe, # second branch taken in first copy finally block)

# For line 16 (the if block in the finally block)
BranchExp( # representing branch on line 16)
  Probe, # first branch in first copy)
  Probe, # second branch in first copy)
  Probe, # first branch in second copy)
  Probe, # second branch in second copy)
  Probe, # first branch in third copy)
  Probe, # second branch in third copy)

Note that there are two distinct branch expressions for the if statement on line 11. The expression for the second branch in line 8 must only consider the first two probes in the finally block, since the others represent conceptually distinct blocks that are not reached via that code path.

However, during the merging step, all BranchExp objects for a given line are merged together and inserted into a map of lineNumber -> BranchExp; this is fine from the point of view of a branch information on a given line but, because the merging is done in place, it also corrupts the trees rooted at those lines. In our example, the tree rooted at line 8 will become:

# For line 8 (the second if block)
BranchExp( # representing branch on line 8
  Probe, # indicating we satisfied the if condition
  BranchExp( # representing branch on line 11
    Probe, # first branch in first copy
    Probe, # second branch in first copy
    Probe, # first branch in second copy
    Probe, # second branch in second copy
    Probe, # first branch in third copy
    Probe, # second branch in third copy

And since the final probe is hit (because it represents the x < 0 evaluation of the if block for when an exception is thrown), we end up recording the branch on line 8 as evaluated; indeed it is evaluated as BranchExp(False, True).