Track implementation for MC/DC about rust HOT 18 OPEN

I have a few cleanup steps planned for after #123409/#124255:

• #124507
• #124508
• I want to split the compiler/rustc_mir_transform/src/coverage/spans.rs file into two files, one containing the existing span-processing code, and a separate file containing BcbMapping and the code that extracts branch/mcdc info from MIR.
  • #124545
• I would like to slightly change the way that nested condition bitmaps are counted, because I think the current way makes it a bit too easy to make off-by-1 mistakes.
• Inside mcdc_parameters there's a big chunk of code inside an unsafe block, which I would like to try to split into smaller and safer pieces.
  • #124555

from rust.

We treat decisions with only one condition as normal branches now, because mcdc won't give different results from normal branch coverage on such cases. Nevertheless, it's same for decisions with only two conditions. Both a && b and a || b are decisions which have tree forms naturally, and as this paper (see the two theorems at section 5) suggests, 100% object branch coverage (what used by llvm) of such decisions implies 100% mcdc. Therefore we could also ignore decisions comprised of 2 conditions. How about doing so?

I am not really convinced that this is something we want to do.
For the 1 condition case, the user trivially understands that changing the condition changes the decision, so MC/DC is not really needed, and adding MCDC reporting anyway to these decisions would probably just bloat the report and make it harder to read.

In the 2-conditions case, even though the theorem proves it, I find it not trivial to understand that branch coverage implies MCDC.

Moreover, in the context of MCDC, I tend to define decisions as boolean expressions composed of several conditions, so in that sense, we don't have to instrument 1-condition decisions by definition, while we still have to instrument decisions with 2+ conditions.

At last, while we have historically never instrumented 1-condition decisions for successfully certified code, it may be harder to justify not instrumenting 2-cond. decisions to the certification authorities, even though, again, it is proved to be equivalent.

Also, I don't feel like this will bring a consequent improvement for either runtime speed, or memory usage, compared to the gains of not instrumenting 1-cond., mostly because I think 1-cond decisions are the most frequently encountered.

from rust.

condition: boolean expressions that have no binary operators. For example, a || b is not "condition" because it has an or operator while a==b is.

nit on the terminology, but I'd rather say that conditions are boolean expressions that have no logical operator.
cf the BinOp and LogicalOp definitions.

from rust.

nit on the terminology, but I'd rather say that conditions are boolean expressions that have no logical operator.

Thanks for correctness! I should have written "binary logical operators". It's a bit different with normal definition because I think treat conditions + unary operators as condition does not lead to different results in MC/DC.

from rust.

Upon implementing mcdc for pattern match, I found that decisions here might be confusing.
Consider pattern if let (A | B, C) = value, intuitively the decision here likes (matches(A) || matches(B)) && matches (C).
However, compiler will rearrange it and make its CFG look like matches (C) && (matches(A) || matches(B)) to reduce complexity.
This impacts mcdc analysis because the condition short-circuited is changed. We should find a way to determine the rearranged decision.

from rust.

Maybe we could do this with a flag -Z coverage-options=no-mcdc-in-pattern-matching (or smth shorter if possible).

Good idea, -no-pattern-matching may be enough since normal branch coverage might also use this option and it is mutual exclusive with mcdc to some extent for now.

from rust.

LLVM 19 has changed the start condition id from 1 to 0 at llvm #81257. This could break all mcdc tests once rustc upgraded its llvm backend. Since llvm 19 is still under development, I plan to deal with it when rust launches process to upgrade the backend .

Sounds reasonable.

Once the compiler switches over to LLVM 19, we might even want to stop supporting MC/DC on LLVM 18, to avoid the complexity of having to support big differences between 18 and 19. 🤔

from rust.

@rustbot label +A-code-coverage

from rust.

The tracking issue should probably include a (brief) definition of MCDC, as otherwise this is untrackable by anyone who does not already know what the issue is for.

from rust.

Excellent, that's much better, thank you! The teams every now and then review tracking issues and it is helpful if whoever is participating in the review can understand what the tracking issue is about without any domain expertise (even if only so they can fetch the appropriate subject-matter expert).

from rust.

I wonder how should let-chains be instrumented.

for example:

if let (A | B, C) = value && let Some(X | Y) = other && (x || y) {
}

Here, I can't decide whether we should insert 1 or 3 MCDC decision records here

• 3 decisions: 1 for each refutable pattern matching, and 1 for the top-level boolean expression
• 1 decision with

Maybe the 3 decisions would be better and easier to do, but I fear this would add a lot of verbosity to the report, and also increase the number of conditions in decisions, which therefore increase the complexity of the testing.

What do you think ?

from rust.

I wonder how should let-chains be instrumented.

for example:

if let (A | B, C) = value && let Some(X | Y) = other && (x || y) {
}

Here, I can't decide whether we should insert 1 or 3 MCDC decision records here

* 3 decisions: 1 for each refutable pattern matching, and 1 for the top-level boolean expression

* 1 decision with

Maybe the 3 decisions would be better and easier to do, but I fear this would add a lot of verbosity to the report, and also increase the number of conditions in decisions, which therefore increase the complexity of the testing.

What do you think ?

I'd tend to 3 decisions as it's more clear and easy to be implemented.
I have managed to construct decisions for refutable pattern matching and found it is very different with normal boolean expressions (eg. rustc does not promise evaluated order of pattern matching). Thus I'd rather view refutable pattern matching as something like try_extract_data_from(&mut bindings...) -> bool.

Besides, if we want to present consistent results in mcdc, we would better take all refutable pattern matching as decisions or not, otherwise we might face paradox like branch coverage in lazy expressions now.

from rust.

I'd tend to 3 decisions as it's more clear and easy to be implemented.
I have managed to construct decisions for refutable pattern matching and found it is very different with normal boolean expressions (eg. rustc does not promise evaluated order of pattern matching). Thus I'd rather view refutable pattern matching as something like try_extract_data_from(&mut bindings...) -> bool.

That makes sense, indeed. Let's go with this strategy then :)

Also, I think it would make sense to allow the user to disable pattern matching instrumentation if needed (for example to reduce the binary size if needed). Maybe we could do this with a flag -Z coverage-options=no-mcdc-in-pattern-matching (or smth shorter if possible).

from rust.

Nested decisions might lead to unexpected results due to sorting mappings happened in llvm. See this patch to llvm for details. Let-chains for pattern matching is affected by this most.

from rust.

We treat decisions with only one condition as normal branches now, because mcdc won't give different results from normal branch coverage on such cases.
Nevertheless, it's same for decisions with only two conditions. Both a && b and a || b are decisions which have tree forms naturally, and as this paper (see the two theorems at section 5) suggests, 100% object branch coverage (what used by llvm) of such decisions implies 100% mcdc.
Therefore we could also ignore decisions comprised of 2 conditions. How about doing so?

from rust.

I should write something to clarify thoughts on designing mcdc for pattern matching in case someone felt confused about the behaviors.

Coverage results of pattern conditions seems to be wrong/unexpected.
This can occur when we check patterns containing or |. Briefly speaking, rustc can rearrange the evaluating order to reduce complexity of control flow and or patterns usually are checked at last. For example, with pattern if let (A | B, C) = tuple, rustc would check is_C(tuple.1) first and then is_A(tuple.0) || is_B(tuple.0). Also in match guards

match tuple {
  (A(Some(_)), B | C) => { /*...*/ },
  (B | C, A(_)) => { /*...*/ },
  (A(None), _) => { /*...*/ },
  _ => { /*...*/ }
}

rustc would check the first and the third arm first. The coverage results are derived from the actual control flow generated by the compiler, which might be not same as intuition.

Why no mcdc for match guards.
Because decisions for irrefutable patterns are never be false. Though we can take each arm as a decision, due to the reorder of conditions, we can hardly determine which conditions a decision contains in view of control flow (one condition might impacts two or more decisions). Still we might find some way to deal with it however.
EDIT: Now it is possible.

from rust.

We might need to make decisions about how to deal with constant folding.
LLVM has already supported ignoring conditions that can be evaluated constantly to some extent. For instance,

const CONSTANT_BOOL: bool = true;
fn foo(a: bool) {
    if a && CONSTANT_BOOL {
          /*...*/
    }
}

In such case llvm shows 100% coverage once a is covered. (For now it's not true for rustc due to a minor divergence on CovTerm which can be fixed very easily, we can check it with clang)

But once if we changed CONSTANT_BOOL to false, we can never get covered conditions because the decision is always false.
Such constants may come from template parameters or some values determined by targets.

I'd propose to eliminate these conditions and all other conditions effected by them from MCDC. That says,

• For a && CONST, if CONST==false, condition a is treated as folded because it would never be covered in mcdc.
• For a || CONST, if CONST==true, a will be also eliminated.
• For a && (b || CONST), if CONST==true, b will be eliminated.

And if a decision was always evaluated to solitary value, we remove it and transform its all conditions to normal branches.
We can work on either rustc or llvm to implement this method.

Let's request some nice insights.

from rust.

LLVM 19 has changed the start condition id from 1 to 0 at llvm #81257. This could break all mcdc tests once rustc upgraded its llvm backend. Since llvm 19 is still under development, I plan to deal with it when rust launches process to upgrade the backend .

from rust.