Optionally extend branch coverage to instrument the last operand of lazy boolean expressions

[RenjiSann]

This issue aims to be a discussion about the implementation of branch coverage, to follow up the discussions in #79649 and #124118.

In the following code example, the current implementation of branch coverage does not instrument the outcome of b in the indirect function, because it has no impact on the control flow of the program and is just assigned to v. a, however, creates a conditional evaluation of b because of the short circuits semantics and thus creates a branch in the control flow.

fn direct(a: bool, b: bool) {
    if a || b { 
        println!("success");
    }
}

fn indirect(a: bool, b: bool) {
    let v = a || b;
    if v { 
        println!("success");
    }
}

#[coverage(off)]
fn main() {
    direct(true, false);
    direct(false, false);

    indirect(true, false);
    indirect(false, false);
}

Even though this instrumentation is "branch coverage" according to the definition, there are several reasons for which one would expect b to be instrumented as well :

• The current behavior may be found counter-intuitive, as illustrated by the question in Add support for branch coverage in source-based coverage #79649.
• This is the behavior adopted in clang/LLVM.
• MC/DC coverage instrumentation depends on branch coverage, and in certification context, MC/DC coverage implies that all the conditions in all the boolean expressions with 2+ operands are instrumented.

@Zalathar gave pertinent reasons on why the "instrument b" behavior might not suit everyone's needs, one being that it implies inserting branches in the MIR that are not here by default. Roughly speaking, this would imply that the MIR of the expression would look like the one of let x = if a || b { true } else { false }; rather than let x = if a { b } else { false };.

---

In order to give the choice to the user, I think we could implement this behavior under another compilation flags: -Z coverage-options=condition.
This idea is that condition coverage instruments the outcome of each condition inside boolean expressions:

• when the expression has 2+ conditions and is outside of a control flow structure
• anytime the expression is in a control flow structure.

Basically, this is branch coverage with the special case of b being instrumented.

In terms of implementation, I think the easiest would be to make condition imply branch coverage, and treat the special case only when condition is enabled.

[Zalathar]

@rustbot label +A-code-coverage

[Zalathar]

There's a similar concern for some other boolean expressions that don't directly participate in a branch. For example:

// Non-lazy logical operators:
a | b
a & b

// Branch hidden in a standard-library function:
b.then_some(x)

So any mode that tries to instrument boolean expressions probably needs to consider whether/how to handle cases like these, too.

[Zalathar]

In terms of implementation, I think the easiest would be to make condition imply branch coverage, and treat the special case only when condition is enabled.

When I originally designed -Zcoverage-options, I imagined that it would mostly consist of individual boolean flags.

But with branch coverage, I think what we're seeing is closer to an enum-valued setting with multiple levels, e.g.:

• branch=off
• branch=basic (alias: branch, branch=on)
• branch=condition (alias: condition)
• branch=mcdc (alias: mcdc)

That might relieve the awkwardness of having so many “independent” flags that actually do depend on each other.

[Lambdaris]

Based on #124217 we could accept it in mcdc first as they are required on the same occasion mostly.
If we do that we probably get different results of llvm-cov --show-branches=count between --coverage-options=branch and --coverage-options=mcdc.
What's more, since LLVM also produces branch coverage reports with MappingKind::MCDCBranch, we can view --coverage-options=mcdc as another "branch coverage" and make them mutually exclusive temporarily.

[RenjiSann]

I am unsure about how this should be implemented.
Shall we

1. insert an actual "useless" branch and instrument it no matter what;
2. or maybe be we could read the assigned result and update the corresponding counter/condition bitmap for MCDC.

Solution 1. is probably the simplest to implement, at the cost of small runtime bloat.
Solution 2. may involve harder implementations of the next steps.

I would rather go with solution 1, because again, slowdown is expected when instrumenting for code coverage

[RenjiSann]

In terms of implementation, I think the easiest would be to make condition imply branch coverage, and treat the special case only when condition is enabled.

When I originally designed -Zcoverage-options, I imagined that it would mostly consist of individual boolean flags.

But with branch coverage, I think what we're seeing is closer to an enum-valued setting with multiple levels, e.g.:

• branch=off
• branch=basic (alias: branch, branch=on)
• branch=condition (alias: condition)
• branch=mcdc (alias: mcdc)

That might relieve the awkwardness of having so many “independent” flags that actually do depend on each other.

Yes, we definitely need a better way to organize all the options.
However, I am not convinced by the name branch=*, as MC/DC and Branch coverage are clearly different things.

Maybe we could use -Z coverage-level=(statement (default) | branch | condition | mcdc), and -Z coverage-options= could be used for things like no-pattern-matching

[Zalathar]

I still don't understand the motivation for wanting to instrument the RHS of lazy boolean operators specifically, but then not also instrument other boolean-valued expressions.

Because if instrumenting all booleans is the goal, then I don't think focusing on lazy booleans specifically is a good intermediate step.

[RenjiSann]

I still don't understand the motivation for wanting to instrument the RHS of lazy boolean operators specifically, but then not also instrument other boolean-valued expressions.

Because if instrumenting all booleans is the goal, then I don't think focusing on lazy booleans specifically is a good intermediate step.

Condition coverage would really only be meant as a building block for MC/DC.

The MC/DC criterion only makes sense for boolean expressions with at least two operands, so tracking branch coverage for simple boolean expressions isn't really relevant.
We do need to track the valuation of all operands, however, as otherwise it would be too easy to cheese the criteria (even for branch coverage). Instead of requiring 4 tests to show full MC/DC coverage (and same for branch coverage, due to the short circuit operators) for

if (a && b && c) { ... }

We could rewrite this as `

let tmp1 = a && b;
let tmp2 = tmp1 && c;
if (tmp2) { ... }

Then, by only testing with a == True and a == False, all other variables being True we'd get 100% branch coverage.

The reason why we don't want to instrument all booleans (including simple assignements like let x: bool = a) is because it produces an overwhelming quantity of coverage information which is not very relevant for certification contexts

For example:

fn foo(a: bool) {
	let x = a;  // 2. check
	if x {      // 3. check
		...
	}
}

fn main() {
	let res = foo(true); // 1. check
}

In this example. if we were to instrument all boolean values, we would end up with 3 tests for the exact same value, when the 3rd one would be enough.

Regarding the instrumentation of short-circuit operators only, there are seemingly 2 reasons for that:

• llvm-cov builds the expressions BDD (binary decision diagram) from the mappings present in the binary. From what I understood, it assumes that operators are short-circuits, and will consider short-circuited conditions as DONT_CARE when performing analysis, no matter what the actual operators are. I am not sure how this can interfere with the actual correctness of the analysis.
• The MC/DC criterion is easier to fulfill for short-circuited expressions, for the DONT_CARE reason. Also, legacy MCDC analysis solutions (including gnatcov) were based on tracing the branches in assembly at runtime, thus it was only possible to track the execution of short-circuit operands. Also, these solutions needed a -fpreserve-control-flow flag to be passed to the compiler to instrument the last conditions as well.

[Zalathar]

Condition coverage would really only be meant as a building block for MC/DC.

I've been thinking some more about whether we should have a separate condition mode at all (instead of just having it be a part of mcdc), and I think my conclusion for now is that I'm reluctantly OK with it.

My main concern is that I want to avoid a proliferation of modes that complicate and weaken testing, especially if they'll be contentious to remove later on.

On the other hand, I do recognise the implementation benefits of having a separate tier on a temporary basis, so that it can be developed and tested separately from the full complexity of MC/DC, without affecting the main branch coverage mode.

So I'd like to suggest that we primarily think of the condition mode as a temporary implementation detail that will eventually go away once the MC/DC mode is more mature, unless there turns out to be real end-user demand for it.

Does that sound OK?

[RenjiSann]

Does that sound OK?

Yes that sounds good. No need to keep condition AND branch coverage available to the user in the long term, as it will likely create confusion.