Add support for branch coverage in source-based coverage

Similarly to what is being done in LLVM and Clang: https://reviews.llvm.org/D84467.

@richkadel

cc @richkadel you might want to include it in #79121

Actually, at last I checked, this is not in any stable version of LLVM yet. I think it's feasible to stabilize Rust coverage in rustc, based on the current feature of LLVM InstrProf, without depending on proposed future LLVM features. So, IMO, I don't think we should add this to the tracking issue, as a dependency. In fact, until this capability is stabilized in LLVM, and available in a version of LLVM that's supported by rustc, I think it makes sense to keep this as a stand-alone feature request / enhancement.

Let me know if any of my assumptions are incorrect.

@tmandry

Cc @tmandry

I have no idea how adding features like that works, I thought it will be available right away in LLVM 12 around March.

Neat. This would certainly improve the way we present coverage for these things, and might make it possible to be more intuitive about how we handle closing braces.

Just to throw it out there, since I'm thinking about async/await right now: This does offer an intriguing possibility of measuring drops at await points. It's possible for buggy code to assume it will never get canceled at an await point, when in fact that's part of the contract. It would be nice if we could highlight this in coverage results. Though explicitly testing cancelation at every await point sounds daunting...

It should be there in the next major version of LLVM, whenever that is.

Looks like this feature was released in LLVM 12.0.0:
https://releases.llvm.org/12.0.0/docs/CoverageMappingFormat.html

14.0.0 was released 2022 March. Similar to the approved suggestion in other issues, where it was decided that an LLVM 11 feature could be used once LLVM 13 was released, could the requirement for code coverage working now be LLVM 12?

I see the original umbrella tracking issue for standardized Rust coverage options still has a few issues open, but it otherwise looks stable and settled.

I should have posted this comment a while ago. (It was discussed when upgrading the coverage mapping format to version 6, in PR #91207).

Before anyone puts much effort into implementing LLVM "branch coverage", I recommend writing a test program that demonstrates where the existing Rust coverage region report would be improved with branch coverage. It's possible that branch coverage adds no value.

Rusts existing coverage regions include counters for both sides of a branch condition, even when implied. For example, an if with no else still generates a coverage region and reported counter for both true and false results. The code region for the false branch is typically shown in a coverage region report as a count one character beyond the if block's closing brace. Something like:

63    if some_condition {
42        statements();
63    }
       ^21

So from this you can already tell that some_condition was true 42 times and false 21 times.

(I think Clang's coverage may not have reported the implied else counts this way, so branch coverage may have closed a gap in Clang's reporting.)

Adding branch coverage support to Rust may or may not be worth the effort, but if someone wants to implement it, I'm happy to provide some guidance or answer questions.

I think the main benefit of branch coverage, and what I as a potential user of it would like to see, is that it will point directly to the source region corresponding to the branching condition.

Implementation (MIR) wise, all the counters are there. https://rustc-dev-guide.rust-lang.org/llvm-coverage-instrumentation.html is very detailed about how this all works. And in theory, implementing branch coverage would consist of introducing new counters that just "reference" existing counters for the true/false branch.

But to repeat, I think this is rather a tooling and DX thing. Having a "zero-width" marker after the closing brace that happens to have 0 hits does not mean anything to developers. They want to see clearly that some_condition was never false.
The way the counter is being reported is unintuitive and does not provide as much value to developers as clearly flagging the branching condition would.

Before anyone puts much effort into implementing LLVM "branch coverage", I recommend writing a test program that demonstrates where the existing Rust coverage region report would be improved with branch coverage. It's possible that branch coverage adds no value.

Here is a possible example, I created exper-code-coverage, where I was comparing cargo-tarpaulin and cargo-llvm-cov crates. I created short_circuit_and() and if_short_circuit_and() with identical tests and if I run cargo llvm-cov I get 100% coverage, as expected:

wink@3900x 22-08-15T00:05:12.879Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cat -n src/if_short_circuit_and.rs 
     1  pub fn if_short_circuit_and(a: i32, b: i32, c: i32, d: i32) -> bool {
     2      if a < b {
     3          c < d
     4      } else {
     5          false
     6      }
     7  }
     8
     9  #[cfg(test)]
    10  mod tests {
    11      use super::*;
    12
    13      // llvm-cov 100% if all are enabled.
    14
    15      // llvm-cov 85.71% if only this is enabled.
    16      #[test]
    17      pub fn test_short_circuit_and_first_false() {
    18          assert_eq!(if_short_circuit_and(20, 10, 30, 40), false);
    19      }
    20
    21      // llvm-cov 85.71% if only this is enabled
    22      #[test]
    23      pub fn test_short_circuit_and_both_true() {
    24          assert_eq!(if_short_circuit_and(10, 20, 30, 40), true);
    25      }
    26  }
wink@3900x 22-08-15T00:05:19.936Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cat -n src/short_circuit_and.rs 
     1  pub fn short_circuit_and(a: i32, b: i32, c: i32, d: i32) -> bool {
     2      a < b && c < d
     3  }
     4
     5  #[cfg(test)]
     6  mod tests {
     7      use super::*;
     8
     9      // llvm-cov 100% if all are enabled.
    10
    11      // llvm-cov 83.33% if only this is enabled
    12      #[test]
    13      pub fn test_short_circuit_and_first_false() {
    14          assert_eq!(short_circuit_and(20, 10, 30, 40), false);
    15      }
    16
    17      // llvm-cov 100% if only this is enabled
    18      #[test]
    19      pub fn test_short_circuit_and_both_true() {
    20          assert_eq!(short_circuit_and(10, 20, 30, 40), true);
    21      }
    22  }
wink@3900x 22-08-15T00:05:24.119Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cargo llvm-cov
   Compiling exper-code-coverage v0.2.0 (/home/wink/prgs/rust/myrepos/exper-code-coverage)
    Finished test [unoptimized + debuginfo] target(s) in 0.68s
     Running unittests src/lib.rs (target/llvm-cov-target/debug/deps/exper_code_coverage-f4d7ca3a8a720d31)

running 4 tests
test if_short_circuit_and::tests::test_short_circuit_and_both_true ... ok
test short_circuit_and::tests::test_short_circuit_and_both_true ... ok
test if_short_circuit_and::tests::test_short_circuit_and_first_false ... ok
test short_circuit_and::tests::test_short_circuit_and_first_false ... ok

test result: ok. 4 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running unittests src/main.rs (target/llvm-cov-target/debug/deps/exper_code_coverage-c502fcb0cc109ca3)

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running tests/cli.rs (target/llvm-cov-target/debug/deps/cli-55e882f44094d43e)

running 1 test
test test_no_params ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

Filename                      Regions    Missed Regions     Cover   Functions  Missed Functions  Executed       Lines      Missed Lines     Cover    Branches   Missed Branches     Cover
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
if_short_circuit_and.rs            10                 0   100.00%           5                 0   100.00%          13                 0   100.00%           0                 0         -
lib.rs                              1                 0   100.00%           1                 0   100.00%           1                 0   100.00%           0                 0         -
main.rs                             2                 0   100.00%           2                 0   100.00%           4                 0   100.00%           0                 0         -
short_circuit_and.rs                9                 0   100.00%           5                 0   100.00%          11                 0   100.00%           0                 0         -
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
TOTAL                              22                 0   100.00%          13                 0   100.00%          29                 0   100.00%           0                 0         -

If I only include the first test, test_short_circuit_and_first_false() I don't get 100% coverage for either if_short_circuit_and.rs or short_circuit_and.rs, which is also as expected:

wink@3900x 22-08-15T00:08:33.760Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cat -n src/if_short_circuit_and.rs 
     1  pub fn if_short_circuit_and(a: i32, b: i32, c: i32, d: i32) -> bool {
     2      if a < b {
     3          c < d
     4      } else {
     5          false
     6      }
     7  }
     8
     9  #[cfg(test)]
    10  mod tests {
    11      use super::*;
    12
    13      // llvm-cov 100% if all are enabled.
    14
    15      // llvm-cov 85.71% if only this is enabled.
    16      #[test]
    17      pub fn test_short_circuit_and_first_false() {
    18          assert_eq!(if_short_circuit_and(20, 10, 30, 40), false);
    19      }
    20
    21      //// llvm-cov 85.71% if only this is enabled
    22      //#[test]
    23      //pub fn test_short_circuit_and_both_true() {
    24      //    assert_eq!(if_short_circuit_and(10, 20, 30, 40), true);
    25      //}
    26  }
wink@3900x 22-08-15T00:08:35.296Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cat -n src/short_circuit_and.rs 
     1  pub fn short_circuit_and(a: i32, b: i32, c: i32, d: i32) -> bool {
     2      a < b && c < d
     3  }
     4
     5  #[cfg(test)]
     6  mod tests {
     7      use super::*;
     8
     9      // llvm-cov 100% if all are enabled.
    10
    11      // llvm-cov 83.33% if only this is enabled
    12      #[test]
    13      pub fn test_short_circuit_and_first_false() {
    14          assert_eq!(short_circuit_and(20, 10, 30, 40), false);
    15      }
    16
    17      //// llvm-cov 100% if only this is enabled
    18      //#[test]
    19      //pub fn test_short_circuit_and_both_true() {
    20      //    assert_eq!(short_circuit_and(10, 20, 30, 40), true);
    21      //}
    22  }
wink@3900x 22-08-15T00:08:37.294Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cargo llvm-cov
   Compiling exper-code-coverage v0.2.0 (/home/wink/prgs/rust/myrepos/exper-code-coverage)
    Finished test [unoptimized + debuginfo] target(s) in 0.67s
     Running unittests src/lib.rs (target/llvm-cov-target/debug/deps/exper_code_coverage-f4d7ca3a8a720d31)

running 2 tests
test short_circuit_and::tests::test_short_circuit_and_first_false ... ok
test if_short_circuit_and::tests::test_short_circuit_and_first_false ... ok

test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running unittests src/main.rs (target/llvm-cov-target/debug/deps/exper_code_coverage-c502fcb0cc109ca3)

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running tests/cli.rs (target/llvm-cov-target/debug/deps/cli-55e882f44094d43e)

running 1 test
test test_no_params ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

Filename                      Regions    Missed Regions     Cover   Functions  Missed Functions  Executed       Lines      Missed Lines     Cover    Branches   Missed Branches     Cover
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
if_short_circuit_and.rs             7                 1    85.71%           3                 0   100.00%           9                 1    88.89%           0                 0         -
lib.rs                              1                 0   100.00%           1                 0   100.00%           1                 0   100.00%           0                 0         -
main.rs                             2                 0   100.00%           2                 0   100.00%           4                 0   100.00%           0                 0         -
short_circuit_and.rs                6                 1    83.33%           3                 0   100.00%           7                 0   100.00%           0                 0         -
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
TOTAL                              16                 2    87.50%           9                 0   100.00%          21                 1    95.24%           0                 0         -

But, if I only include the last test I get less than 100% for if_short_circuit_and.rs, but 100% coverage for short_circuit_and.rs, this is not expected:

wink@3900x 22-08-15T00:10:59.494Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cat -n src/if_short_circuit_and.rs 
     1  pub fn if_short_circuit_and(a: i32, b: i32, c: i32, d: i32) -> bool {
     2      if a < b {
     3          c < d
     4      } else {
     5          false
     6      }
     7  }
     8
     9  #[cfg(test)]
    10  mod tests {
    11      use super::*;
    12
    13      // llvm-cov 100% if all are enabled.
    14
    15      // llvm-cov 85.71% if only this is enabled.
    16      //#[test]
    17      //pub fn test_short_circuit_and_first_false() {
    18      //    assert_eq!(if_short_circuit_and(20, 10, 30, 40), false);
    19      //}
    20
    21      // llvm-cov 85.71% if only this is enabled
    22      #[test]
    23      pub fn test_short_circuit_and_both_true() {
    24          assert_eq!(if_short_circuit_and(10, 20, 30, 40), true);
    25      }
    26  }
wink@3900x 22-08-15T00:11:00.865Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cat -n src/short_circuit_and.rs 
     1  pub fn short_circuit_and(a: i32, b: i32, c: i32, d: i32) -> bool {
     2      a < b && c < d
     3  }
     4
     5  #[cfg(test)]
     6  mod tests {
     7      use super::*;
     8
     9      // llvm-cov 100% if all are enabled.
    10
    11      //// llvm-cov 83.33% if only this is enabled
    12      //#[test]
    13      //pub fn test_short_circuit_and_first_false() {
    14      //    assert_eq!(short_circuit_and(20, 10, 30, 40), false);
    15      //}
    16
    17      // llvm-cov 100% if only this is enabled
    18      #[test]
    19      pub fn test_short_circuit_and_both_true() {
    20          assert_eq!(short_circuit_and(10, 20, 30, 40), true);
    21      }
    22  }
wink@3900x 22-08-15T00:11:02.440Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cargo llvm-cov
   Compiling exper-code-coverage v0.2.0 (/home/wink/prgs/rust/myrepos/exper-code-coverage)
    Finished test [unoptimized + debuginfo] target(s) in 0.68s
     Running unittests src/lib.rs (target/llvm-cov-target/debug/deps/exper_code_coverage-f4d7ca3a8a720d31)

running 2 tests
test if_short_circuit_and::tests::test_short_circuit_and_both_true ... ok
test short_circuit_and::tests::test_short_circuit_and_both_true ... ok

test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running unittests src/main.rs (target/llvm-cov-target/debug/deps/exper_code_coverage-c502fcb0cc109ca3)

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running tests/cli.rs (target/llvm-cov-target/debug/deps/cli-55e882f44094d43e)

running 1 test
test test_no_params ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

Filename                      Regions    Missed Regions     Cover   Functions  Missed Functions  Executed       Lines      Missed Lines     Cover    Branches   Missed Branches     Cover
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
if_short_circuit_and.rs             7                 1    85.71%           3                 0   100.00%           9                 1    88.89%           0                 0         -
lib.rs                              1                 0   100.00%           1                 0   100.00%           1                 0   100.00%           0                 0         -
main.rs                             2                 0   100.00%           2                 0   100.00%           4                 0   100.00%           0                 0         -
short_circuit_and.rs                6                 0   100.00%           3                 0   100.00%           7                 0   100.00%           0                 0         -
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
TOTAL                              16                 1    93.75%           9                 0   100.00%          21                 1    95.24%           0                 0         -

I've now dug a little deeper and used cargo asm to look at the generated code. It seems build in debug mode the code for if_short_circuit_and() and short_circuit_and() are basically the same code. And in release mode they are actually the same code, see details below.

Based on this I conclude that this example provides an indication that "branch coverage" should be an improvement.

Details

Here is the asm code for if_short_circuit_and():

wink@3900x 22-08-15T19:52:28.139Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cargo asm --build-type debug --asm-style=att exper_code_coverage::if_short_circuit_and::if_short_circuit_and
exper_code_coverage::if_short_circuit_and::if_short_circuit_and (src/if_short_circuit_and.rs:1):
 subq    $28, %rsp
 movl    %edx, (%rsp)
 movl    %ecx, 4(%rsp)
 movl    %edi, 12(%rsp)
 movl    %esi, 16(%rsp)
 movl    %edx, 20(%rsp)
 movl    %ecx, 24(%rsp)
 cmpl    %esi, %edi
 jl      .LBB0_2
 movb    $0, 11(%rsp)
 jmp     .LBB0_3
.LBB0_2:
 movl    (%rsp), %eax
 movl    4(%rsp), %ecx
 cmpl    %ecx, %eax
 setl    %al
 andb    $1, %al
 movb    %al, 11(%rsp)
.LBB0_3:
 movb    11(%rsp), %al
 andb    $1, %al
 movzbl  %al, %eax
 addq    $28, %rsp
 retq

And here it is for short_circuit_and():

wink@3900x 22-08-15T19:52:32.960Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cargo asm --build-type debug --asm-style=att exper_code_coverage::short_circuit_and::short_circuit_and
exper_code_coverage::short_circuit_and::short_circuit_and (src/short_circuit_and.rs:1):
 subq    $28, %rsp
 movl    %edx, (%rsp)
 movl    %ecx, 4(%rsp)
 movl    %edi, 12(%rsp)
 movl    %esi, 16(%rsp)
 movl    %edx, 20(%rsp)
 movl    %ecx, 24(%rsp)
 cmpl    %esi, %edi
 jl      .LBB1_2
 movb    $0, 11(%rsp)
 jmp     .LBB1_3
.LBB1_2:
 movl    (%rsp), %eax
 movl    4(%rsp), %ecx
 cmpl    %ecx, %eax
 setl    %al
 andb    $1, %al
 movb    %al, 11(%rsp)
.LBB1_3:
 movb    11(%rsp), %al
 andb    $1, %al
 movzbl  %al, %eax
 addq    $28, %rsp
 retq

I piped these to .s files and the only differences are the labels:

wink@3900x 22-08-15T19:53:58.046Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ diff *.s
1c1
< exper_code_coverage::if_short_circuit_and::if_short_circuit_and (src/if_short_circuit_and.rs:1):
---
> exper_code_coverage::short_circuit_and::short_circuit_and (src/short_circuit_and.rs:1):
10c10
<  jl      .LBB0_2
---
>  jl      .LBB1_2
12,13c12,13
<  jmp     .LBB0_3
< .LBB0_2:
---
>  jmp     .LBB1_3
> .LBB1_2:
20c20
< .LBB0_3:
---
> .LBB1_3:

I then created the release version and if_short_circuit_and() is not mentioned as being generated, we only see short_circuit_and():

wink@3900x 22-08-15T20:01:27.012Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cargo clean
wink@3900x 22-08-15T20:01:29.623Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cargo asm --build-type release --asm-style=att
core::ops::function::FnOnce::call_once{{vtable.shim}}
core::ptr::drop_in_place<std::rt::lang_start<()>::{{closure}}>
exper_code_coverage::main
exper_code_coverage::short_circuit_and::short_circuit_and
std::rt::lang_start
std::rt::lang_start::{{closure}}
std::sys_common::backtrace::__rust_begin_short_backtrace

Wondering what happened to it, I looked at the generated code and there are two .s files and short_circuit_and() is in target/release/deps/exper_code_coverage-865a6210cdb565bc.s. Looking at that code we find that at line 21 if_short_circuit_and is "set" to short_circuit_and. So the code if_short_circuit_and() has been optimized away:

$ fd --glob '*.s' target
target/release/deps/exper_code_coverage-865a6210cdb565bc.s
target/release/deps/exper_code_coverage-c551574da956536f.s
wink@3900x 22-08-15T20:02:02.209Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cat -n target/release/deps/exper_code_coverage-865a6210cdb565bc.s
     1          .text
     2          .file   "exper_code_coverage.210b8923-cgu.0"
     3          .section        .text._ZN19exper_code_coverage17short_circuit_and17short_circuit_and17h626fd720e3a99931E,"ax",@progbits
     4          .globl  _ZN19exper_code_coverage17short_circuit_and17short_circuit_and17h626fd720e3a99931E
     5          .p2align        4, 0x90
     6          .type   _ZN19exper_code_coverage17short_circuit_and17short_circuit_and17h626fd720e3a99931E,@function
     7  _ZN19exper_code_coverage17short_circuit_and17short_circuit_and17h626fd720e3a99931E:
     8          .cfi_startproc
     9          cmpl    %esi, %edi
    10          setl    %sil
    11          cmpl    %ecx, %edx
    12          setl    %al
    13          andb    %sil, %al
    14          retq
    15  .Lfunc_end0:
    16          .size   _ZN19exper_code_coverage17short_circuit_and17short_circuit_and17h626fd720e3a99931E, .Lfunc_end0-_ZN19exper_code_coverage17short_circuit_and17short_circuit_and17h626fd720e3a99931E
    17          .cfi_endproc
    18
    19          .globl  _ZN19exper_code_coverage20if_short_circuit_and20if_short_circuit_and17h996a8c765e790e2dE
    20          .type   _ZN19exper_code_coverage20if_short_circuit_and20if_short_circuit_and17h996a8c765e790e2dE,@function
    21  .set _ZN19exper_code_coverage20if_short_circuit_and20if_short_circuit_and17h996a8c765e790e2dE, _ZN19exper_code_coverage17short_circuit_and17short_circuit_and17h626fd720e3a99931E
    22          .section        ".note.GNU-stack","",@progbits

doc: Add a note about branch coverage in rust

maint/CI ~ convert to instrumented/source-based coverage calculation

I'm surprised to hear that clang treats a || b as two branches. I assume that in doing so, it inserts a synthetic control-flow branch on b so that the underlying counters are updated appropriately?

Effectively, this is true for clang -- the goal was to provide a consistent metric for all conditions in an expression in the source code, though technically you're correct that condition b in this case would not result in a branch. This also aligns to what I've seen other vendors show (e.g. LDRA, LCOV).

(Actually for clang, a synthetic control-flow branch is inserted for the last condition on all boolean expressions in order to ensure a final count, even though this is obviously not necessary, given that, for example, in an if-stmt, we can instead use the counter measuring the then block. I anticipated that this can be better optimized in a later clang patch.

I don't see contradiction in the expression a || b how counting work/doesn't work as I see this simple expression in a more complex implementation (imaginary, as I don't know actual internals of rust and clang to advise or anything):

When a or b are constants, we know the result on compile time. Thus there would be no branching => no real coverage. Example: a || true
When a AND b are variables it's faster to calculate the result rather than doing if-branching. Example: let c = a || b;
When a is an expression and b is a variable as we know a value of a at the end of calculation as variable value (could be stored in a register) we can return to a case when both a and b are variables, instead of branching. Example: let c = (t == 0) || b
Otherwise branching is required. Example: let c = (t == 0) || (d == 5).

Based on this, I take line "in boolean expression second argument won't be calculated if first is true" with a grain of salt as a mind shortcut.

Thus, I don't expect counting to work the same way in every single situation, as situations are actually different even visually they're the same.

PS: braces added for clarity.

The instrument behavior for branches containing | patterns may worth to discuss. It makes a difference on branch coverage as well as mcdc.

The question is: how to determine false branches in pattern Opt::A | Opt::B ? This pattern can be tested in a single basic block with terminator in the form of switchInt(move _dis) -> [0: bb2, 1: bb3, otherwise: bb1] with current rustc. Suppose bb2 is the branch for matching Opt::A, bb3 is for matching Opt::B and bb1 is for matching neither.

The first view is that take it as is(Opt::A) || is(Opt::B). Thus the false branch of is(Opt::A) should contain the true branch of is(Opt::B). That says, the false count of Opt::A shall be sum of execution number of bb3 and bb1, while false count of Opt::B is just the execution number of bb1.

The first opinion might be intuitive. However, one can argue that there is a key difference between or patterns and boolean or expressions: when we write a || b, a and b can both are right, while only at most one of matching A and B can be true in pattern A | B. As a result, we can say A | B is equivalent to B | A but undoubtedly b || a is not same as a || b. This view shows its contradiction on generating different reports for expressions meaning exactly the same.

As an opposition, the second proposal assigns Opt::A and Opt::B symmetric positions: false count of Opt::A is execution number of bb3 plus that of bb1, while false count of Opt::B is sum of execution number of bb2 and bb1. By this way we can keep consistency with commutativity and associativity of or patterns (what a pity this is not an abelian group due to the lack of an identity element 😔) but users may feel confused at first sight. Besides, if we adopt this view we also need to discuss how to determine the false next of Opt::A and Opt::B in mcdc.
The third proposal modifies the second a bit: false count of Opt::A and Opt::B both only count execution number of bb1, thus matching Opt::A does not mean false of Opt::B and vice versa. Someone might like this because in this way test case foo(Opt::A) gives result Opt::A: true count 1, false count 0; Opt::B: true count 0, false count 0 where Opt::B is irrelevant.

For now I have implemented the first proposal at #124278 but tend to the second in mcdc. And normal branch coverage may need to consider this too so I present it here to collect some advice or other views.

For branch coverage (or at least the basic level of branch coverage), my current thinking is that Opt::A | Opt::B should have one combined true branch, and one combined false branch, with no way to count the occurrences of A vs B.

Of course, that wouldn't be appropriate for MC/DC coverage (or a more detailed level of branch coverage), where users would probably need more detail in order to satisfy their testing/documentation requirements.

I vaguely remember hearing that someone had been doing some work on defining precisely what MC/DC should mean in the context of Rust (with things like pattern-matching and or-patterns), but I don't have any of the details at hand.

Auto merge of rust-lang#124507 - Zalathar:coverage-level, r=compiler-…

@ZhuUx

@ZhuUx: However, one can argue that there is a key difference between or patterns and boolean or expressions: when we write a || b, a and b can both are right, while only at most one of matching A and B can be true in pattern A | B. As a result, we can say A | B is equivalent to B | A but undoubtedly b || a is not same as a || b. This view shows its contradiction on generating different reports for expressions meaning exactly the same.

I agree here, we shouldn't treat or patterns like short-circuiting boolean expressions. The way I'd see them is like two separate decisions to reach the same branch.

@ZhuUx: For now I have implemented the first proposal at #124278 but tend to the second in mcdc. And normal branch coverage may need to consider this too so I present it here to collect some advice or other views.

@Zalathar: For branch coverage (or at least the basic level of branch coverage), my current thinking is that Opt::A | Opt::B should have one combined true branch, and one combined false branch, with no way to count the occurrences of A vs B.

I think for branch coverage @Zalathar's approach is the best, while for MC/DC I'd go with @ZhuUx's second proposal.

@Zalathar: I vaguely remember hearing that someone had been doing some work on defining precisely what MC/DC should mean in the context of Rust (with things like pattern-matching and or-patterns), but I don't have any of the details at hand.

We (Ferrous Systems) wrote that paper with DLR. It's still not published (we're submitting it to an academic conference), but if you need a copy of the pre-print for the implementation of branch or MC/DC coverage reach out at pietro.albini@ferrous-systems.com and I'll happily send you a copy!

Auto merge of #124507 - Zalathar:coverage-level, r=compiler-errors

@evodius96

@evodius96
Would have a question need to be verified. Does the assignment of condition id shall keep with some order?
Found that for code like

fn foo(a: bool, b: bool) {
    if a && b {
        // ...
    }
}

fn main() {
    foo(true, false)
}

If the condition id of a is 2 while the id of b is 1, llvm panics with Assertion !TestVectors[Idx].empty() && "Test Vector doesn't exist." failed.
It is not problem for normal two way branch. Only for pattern matching in rust we get such assignment due to the special evaluating order (very likely not to be same with boolean expressions). I guess the condition specified with id 1 must be the first condition to be evaluated? Or are there any other constrictions?

@evodius96

@evodius96 Would have a question need to be verified. Does the assignment of condition id shall keep with some order?

For MC/DC, the order doesn't matter, but the order has to be consistent such that once a node gets an ID, it doesn't change. During llvm-cov visualization, where the conditions are counted according to their left-to-right ordinal position, a mapping is maintained to track a condition's ordinal position and the ID it has.

In clang, the ID is assigned by the node visitor during a recursive AST walk (See struct MCDCCoverageBuilder in CoverageMappingGen.cpp). Here, an ID is simply an ID and doesn't represent a meaningful order. This is the ID that gets encoded into the branch region (allowing llvm-cov to reconstruct the control flow and thereby the possible test vectors), and it's also used during instrumentation as the condition index into the condition bitmap, indicating conditions that evaluate to TRUE. This is used to calculate the indices of all actual executed test vectors.

The TestVectors[Idx] you see in the assertion is a vector of all possible TestVectors. As you can surmise, the assertion fails if llvm-cov sees an executed test vector that doesn't match one of the possible test vectors it knows. So either the global bitmap (indicated executed test vectors) is wrong (most likely), which points to a bug in instrumentation, or the calculated set of possible test vectors is wrong, indicating a bug in the branch region encoding used for MC/DC.

The TestVectors[Idx] you see in the assertion is a vector of all possible TestVectors. As you can surmise, the assertion fails if llvm-cov sees an executed test vector that doesn't match one of the possible test vectors it knows.

Ah Exactly that's what happened if the id of entry condition is not 1. Assertions fail at different locations between llvm 18 and 19.
In llvm 18, the function MCDCRecordProcessor::buildTestVector (in CoverageMapping.cpp) looks like:

  void buildTestVector(MCDCRecord::TestVector &TV, unsigned ID = 1) {
    shouldCopyOffTestVectorForTruePath(TV, ID);
    shouldCopyOffTestVectorForFalsePath(TV, ID);

    // Reset back to DontCare.
    TV[ID - 1] = MCDCRecord::MCDC_DontCare;
  }

It constructs all possible test vectors and is called first at processMCDCRecord() with default ID. Thus once the id of a was 2 and the id of b was 1, this function checked b at start and found that it has no next (on such occasion mapping of a was {id: 2, true_next: 1, false_next: 0}, and that of b was {id: 1, true_next: 0, false_next: 0}). As a result, only [T, -] and [F, -] for [b, a] are recorded in TestVectors, though the executed vector may be [F, T].

As for llvm 19, llvm-cov would panic at assert(Nodes[0].InCount == 0) in mcdc::TVIdxBuilder::TVIdxBuilder. This again because Node[0], which represents entry (or top) node in the decision tree and shall not have any "parent" nodes, comes from the condition with ID 1 and is successor of Node[1] in the example function.

Hence there is an implicit rule suggested by implementation that the entry condition of decision should be fixed with condition id 1. I think this is relatively fair so we (or any other compilers implementing mcdc based on llvm) would better respect it. At least it is not difficult for rust to find a way to regulate the condition id assignment of pattern matching.

docs(coverage): document nightly-Rust toolchain choice for coverage jobs

fix(ci): drop --branch from coverage pipeline to dodge LLVM #189169

fix(ci): drop --branch from coverage pipeline to dodge LLVM #189169 (#…

Branch coverage is a helpful feature. It would probably save rustup a significant amount of bandwidth (in CI jobs) to not require rust nightly just to get --branch coverage.

ci: measure coverage and gate Code Health at 10.0

Navigation Menu

Repository navigation

Add support for branch coverage in source-based coverage #79649

Details

24 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Add support for branch coverage in source-based coverage #79649

Description

Activity

mati865 commented on Jan 8, 2021

richkadel commented on Jan 8, 2021

richkadel commented on Jan 8, 2021

mati865 commented on Jan 8, 2021

tmandry commented on Jan 9, 2021

matthargett commented on May 6, 2022

richkadel commented on May 6, 2022

Swatinem commented on May 9, 2022

winksaville commented on Aug 15, 2022

winksaville commented on Aug 15, 2022

Details

24 remaining items

evodius96 commented on Apr 18, 2024

eirnym commented on Apr 20, 2024

ZhuUx commented on Apr 28, 2024

Zalathar commented on Apr 28, 2024

emilyalbini commented on May 2, 2024

ZhuUx commented on May 7, 2024

evodius96 commented on May 7, 2024

ZhuUx commented on May 8, 2024

westurner commented on Jun 29, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions