dotnet / dotnet/runtime

Unreachable conditional branch in RBDeleteFixup (file RbTree.cs)

Open
#129,419 2 comments 0 reactions 0 assignees View on GitHub
area-System.Data
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.