Track implementation for MC/DC

[ZhuUx]

Introduction

Modified condition/decision coverage (MC/DC) is a code coverage criterion used widely in safety critical software components and is required by standards such as DO-178B and ISO26262.

Terminology
condition: boolean expressions that have no binary logical operators. For example, a || b is not "condition" because it has an or operator while a==b is.
decision: boolean expressions composed of conditions and binary boolean expressions.

MC/DC requires each condition in a decision is shown to independently affect the outcome of the decision.
e.g Suppose we have code like

if (a || b) && c {
    todo!();
}

Here (a || b) && c is a decision and a,b,c are conditions.

• If test cases are (a=true, b=false, c=true) and (a=false, b=false, c=true), we say a can independently affect the decision because the value of decision is changed as a changes while keep b and c unchanged. So that we get 1/3 MC/DC here (1 for a and 3 for a,b,c).
• Test cases (a=false, b=true, c=true) and (a=false, b=false, c=false) also show b can independently affect the decision because in the later case c is short-circuited and has no impacts (thus we can view it as same as c=true). However, c is not acknowledged due to change of b. Plus the two cases before we get 2/3 MC/DC.
• Test cases (a=true,b=false,c=true) and (a=true,b=false,c=false) show c can do the same. By now we get 3/3.

Notice that there are duplicate cases, so test cases collection {(a=true, b=false, c=true),(a=false, b=false, c=true),(a=false, b=true, c=true), (a=false, b=false, c=false),(a=true,b=false,c=false)} are sufficient to prove 3/3 MC/DC.
In fact we can use at least n+1 cases to prove 100% MC/DC of decision with n conditions. (In this example, {(a=true,b=false,c=true),(a=false,b=false,c=true),(a=false,b=true,c=true),(a=true,b=false,c=false)} are enough)

Progress

A basic implementation for MC/DC is filed on #123409 , which has some limits. There are still several cases need to handle:

• Support lazy boolean expressions like let val = a || b. For now this is impacted by branch coverage and work in a different style with certification standards where usually MC/DC is required. To solve this, 124120 is the prerequisite.
  Draft: (DRAFT) Proof-of-concept for instrumenting the RHS of lazy logical operators #124644

• Support if-let pattern. Ferrous suggests that refutable pattern matching should be considered as decisions, which sounds certainly reasonable as these are considered as branches too. This depends on support from branch coverage (see 124118).
  Draft: Support mcdc analysis for pattern matching #124278
  Besides, decisions in match guard might still be left to discuss.

• Support nested decisions like if (a || b) || inner_decision(c || d)

  • Implemented at MCDC coverage: support nested decision coverage #124255
  • Some cases need to be solved as llvm #91600 described. This relies on llvm so we have to wait for llvm-19 or newer.

• So far only decisions with at most 6 conditions are counted due to resource cost. This limit should be relaxed once if the llvm backend had this optimization.

Notes

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.

[ZhuUx]

@rustbot label +A-code-coverage

[workingjubilee]

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.

[RenjiSann]

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.

[workingjubilee]

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).

[ZhuUx]

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.

[ZhuUx]

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.

[RenjiSann]

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 ?

[ZhuUx]

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.

[RenjiSann]

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).

[ZhuUx]

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.

[Zalathar]

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

• coverage: Replace boolean options with a CoverageLevel enum #124507
• coverage: Avoid hard-coded values when visiting logical ops #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.
  • coverage: Split off mappings.rs from spans.rs and from_mir.rs #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.
  • coverage: Clean up creation of MC/DC condition bitmaps #124555

[Lambdaris]

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.

[ZhuUx]

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?

[ZhuUx]

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.

[RenjiSann]

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.

[Lambdaris]

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.

[ZhuUx]

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 .

[Zalathar]

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. 🤔

[RenjiSann]

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.

I have several question regarding constant folding.

First, when you say "a will be eliminated", do you mean that we choose to not instrument it for MCDC because it is uncoverable, or does it get dropped by a subsequent constant folding path ?

In the case were a is not a variable, but an expression with eventual side effects, I guess the compiler can't just drop it. So do we still choose to not instrument it ?

Also, in the cases a && TRUE and b || FALSE, the expressions are equivalent to a and b respectively.
Thus, the constants will be eliminated, so I guess that there is no way for this to be detected.

Nobody uses constants in decisions intentionnally, so we primarly need to think about generated code.
IMO, from a user point-of-view, I think that having a way to know what happened during the instrumentation would be nice.

One idea would be to write warning message saying something like "Condition X of the decision was resolved to constant False, this will make MCDC coverage impossible for conditions X,Y, Z". However, I am not really convinced by this approach, because this would introduce compilation "Warnings" that may be completely expected.

The other idea would be to add metadata in the mappings, so that llvm-cov can display a message for a specific condition.
For example:

fn foo(a: bool) {
    if a && false {
        println!("success");
    }
}

  |---> MC/DC Decision Region (LL:CC) to (LL:CC)
  |
  |  Number of Conditions: 2
  |     Condition C1 --> (LL:CC)
  |     Condition C2 --> (LL:CC)
  |
  |  Executed MC/DC Test Vectors:
  |
  |     C1, C2    Result
  |  1 { F,  F  = F      }
  |  2 { T,  F  = F      }
  |
  |  C1-Pair: Skipped: uncoverable (folded by C2)
  |  C2-Pair: Skipped: constant resolved to False
  |  MC/DC Coverage for Decision: 100%
  |
  ------------------

One question that this arises, is how we consider "skipped" conditions. Do we account for them in the whole decision validation, or do we ignore them, and consider the decision is covered if all non-skipped conditions are covered ?

Furthermore, the biggest downside of this solution is that is will probably involve a massive refactor of LLVM's ProfileData code.

What do you think ?

[Lambdaris]

  |---> MC/DC Decision Region (LL:CC) to (LL:CC)
  |
  |  Number of Conditions: 2
  |     Condition C1 --> (LL:CC)
  |     Condition C2 --> (LL:CC)
  |
  |  Executed MC/DC Test Vectors:
  |
  |     C1, C2    Result
  |  1 { F,  F  = F      }
  |  2 { T,  F  = F      }
  |
  |  C1-Pair: Skipped: uncoverable (folded by C2)
  |  C2-Pair: Skipped: constant resolved to False
  |  MC/DC Coverage for Decision: 100%
  |
  ------------------

That's what I expect: constants are marked as "Folded" while all uncoverable conditions are noted.

I've tried a bit on both rustc and llvm. It seems better to implement it on llvm side. Since in rust we know which conditions are folded after injecting statements, it's not elegant for rust to do these stuff.

[evodius96]

That's what I expect: constants are marked as "Folded" while all uncoverable conditions are noted.

It's likely I don't understand the intricacies of constant folding in rust; given its unique use cases, ultimately you can handle these however you wish. However, I want to point out that in clang, we mark conditions that are constant folded so that they can be visualized for the user (both for branch coverage and MC/DC). In MC/DC, these constant folded conditions are excluded from measurement (as you know, they're uncoverable and therefore cannot have any independence pairs).

However, a key distinction I want to make is that for MC/DC in clang, we actually do not fold the conditions (we disable this) and therefore we actually instrument the folded conditions in order to facilitate proper coverage of the other conditions in the decision. We have to do this to ensure we match the possible test vectors correctly.

[Lambdaris]

However, a key distinction I want to make is that for MC/DC in clang, we actually do not fold the conditions (we disable this) and therefore we actually instrument the folded conditions in order to facilitate proper coverage of the other conditions in the decision. We have to do this to ensure we match the possible test vectors correctly.

In my premature thoughts we can avoid remarkable divergences between rust and llvm. The changes I wish to make are:

• For now clang set both Counter and FalseCounter to Zero if the condition is folded. We can only set the counter of folded branch to Zero (like rustc does now).
• On llvm-cov side, mark a condition as folded if either of Counter and FalseCounter is Zero.
• Pick up all practical test vectors considering folded conditions, and analyze which conditions are unrecoverble or folded.

This method does not invade instruments but only effects how llvm presents for users.

For instance, suppose we have a decision a && (b || CONSTANT_TRUE || c).

With the scenario, we still have 4 mcdc branch mappings: a, b, CONSTANT_TRUE, c, in which clang and rustc mark FalseCounter of CONSTANT_TRUE as Zero. Then llvm-cov knows CONSTANT_TRUE is folded and always evaluated to true because it knows the FalseCounter is Zero.

After llvm-cov collects all test vectors, it can show practical test vectors by pick up whose folded conditions bits are expected. Say, in our example, only test vectors in this table are practical: (D means DontCare in TestVector)

a	b	CONSTANT_TRUE	c	Decision
0	D	D	D	0
1	1	D	D	1
1	0	1	D	1

As we see, the practical test vectors are whose bit for CONSTANT_TRUE is 1 or DontCare.

Next let's find which conditions are uncoverable or folded:

1. Partition all practical test vectors by value of a. We show there are different decision values for the two groups: {(0,D,D,D)} and {(1,1,D,D), (1,0,1,D)}, thus a is coverable and not folded.
2. Partition all practical test vectors by value of b (exclude DontCare), both the two group, {(1,1,D,D)} and {(1,0,1,D)} share same decision value. Thus we know b is uncoverable due to the constant because it can not change value of the decision.
3. CONSTANT_TRUE is marked as folded just as llvm-cov does now.
4. Partition all pracitcal test vectors by value of c ...... No, c is DontCare in all practical test vectors, so it's Folded by constant.

Briefly the scheme is:

1. Only set counter of the folded branch to Zero if the condition is folded in front end compilers.
2. In llvm-cov, mark a condition as folded if either of Counter or FalseCounter was Zero.
3. Pick up all "practical" test vectors, whose bit of folded condition is the practical value or DontCare.
4. For each condition, partition practical test vectors by its value to three group: true, false or DontCare
   • If either of true group or false group is empty, the condition is folded.
   • If exist tv1 in true group and tv2 in false group, tv1 and tv2 have different decision value, the condition is normal.
   • If all test vectors in true group and false group have same decision value, the condition is uncoverable.

I'm going to draft in this way hence not much of existed llvm code need to be refactored. Is it worth?

(I've opened an issue on llvm llvm #93560, we can discuss the scheme there)