Unreachable conditional branch in RBDeleteFixup (file RbTree.cs)
- Dominant language
- C#
- Stars
- 18.3k
- Forks
- 5.6k
- PR merge metrics
- PR metrics pending
Description
### Describe
While reviewing the Red-Black tree deletion fixup implementation (`RBDeleteFixup`), I noticed a logical contradiction that results in dead code when handling the right-child case.
https://github.com/dotnet/runtime/blob/98bfa17c9f3910eec30099b7ac140d8a09df6227/src/libraries/System.Data.Common/src/System/Data/RbTree.cs#L1158-L1163
### Problem Details
Inside a conditional block that explicitly guards against `NIL` values:
```csharp
if (x_id != NIL)
{
// ...
// code containing: (x_id == NIL) ? Left(px_id) : Left(Parent(x_id))
}
```
The ternary check `(x_id == NIL)` is nested within the `if (x_id != NIL)` check. Because of this, `x_id == NIL` will **always evaluate to false**.
Consequently, the `Left(px_id)` branch is completely unreachable (dead code), and the expression redundantly evaluates to `Left(Parent(x_id))` every time.
### Suggested Action
Is it safe to remove the ternary operator and leave the code as follows?
```csharp
if (x_id != NIL)
{
SetColor(px_id, NodeColor.red);
root_id = RightRotate(root_id, px_id, mainTreeNodeID);
w_id = Left(Parent(x_id));
}
```
Thank you!
Found by Linux Verification Center (linuxtesting.org) with SVACE.
Contributor guide
Assessment
This issue has not been assessed yet.