ImmutableList<T>.LastIndexOf(...) appears to be missing a guard clause

[Saborion]

Description

Searching for the last index of an item in an instance of ImmutableList<T> that holds at least one matching item can return the wrong index. This happens when the index argument passed in to ImmutableList<T>.LastIndexOf(T item, int index, int count, IEqualityComparer<T>? equalityComparer) equals the collection size, at which point the returned index will be off by one (+1), e.g. if the actual index is 2 the returned index will be 3.

Reproduction Steps

A .NET 6 console application with the following top level statements:

using System.Collections.Immutable;

var lastIndexOf = new[] { "NonMatch", "Match", "Match", "NonMatch" }
    .ToImmutableList()
    .LastIndexOf("Match", index: 3, count: 4, equalityComparer: null); // Returns 2 (correct)

var lastIndexOf2 = new[] { "NonMatch", "Match", "Match", "NonMatch" }
    .ToImmutableList()
    .LastIndexOf("Match", index: 4, count: 4, equalityComparer: null); // Returns 3 (incorrect, should throw?)

Console.WriteLine($"Last index when 'index' argument equals count - 1: {lastIndexOf}");
Console.WriteLine($"Last index when 'index' argument equals count    : {lastIndexOf2}");

Expected behavior

One of the two below:

1. ImmutableList<T>.LastIndexOf(T item, int index, int count, IEqualityComparer<T>? equalityComparer) should throw if index equals the size of the collection, the same way startIndex does for ImmutableArray<T>.LastIndexOf(T item, int startIndex, int count, IEqualityComparer<T>? equalityComparer ).
2. ImmutableList<T>.LastIndexOf(T item, int index, int count, IEqualityComparer<T>? equalityComparer) should return the correct index of the last item found when the index argument equals the size of the collection.

Actual behavior

The returned index is bigger (+1) than the correct index.

Regression?

No response

Known Workarounds

No response

Configuration

• .NET 6
• Windows 10, 64-bit
• x64
• Don't know if it is specific to this version

Other information

I suspect that the culprit is a missing guard clause for the upper boundary for the index parameter in the internal int LastIndexOf(T item, int index, int count, IEqualityComparer<T>? equalityComparer) method (line 786 as of this writing) in ImmutableList_1.Node.cs. This method is called from ImmutableList_1.cs.

Contrast the guard clause in the above mentiond method with the one from ImmutableArray_1.Builder.cs
ImmutableList<T> - Requires.Range(index >= 0, nameof(index));
vs
ImmutableArray<T> - Requires.Range(startIndex >= 0 && startIndex < this.Count, nameof(startIndex));
where the latter makes more sense.

Tagging subscribers to this area: @dotnet/area-system-collections
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Description

Searching for the last index of an item in an instance of ImmutableList<T> that holds at least one matching item can return the wrong index. This happens when the index argument passed in to ImmutableList<T>.LastIndexOf(T item, int index, int count, IEqualityComparer<T>? equalityComparer) equals the collection size, at which point the returned index will be off by one (+1), e.g. if the actual index is 2 the returned index will be 3.

Reproduction Steps

A .NET 6 console application with the following top level statements:

using System.Collections.Immutable;

var lastIndexOf = new[] { "NonMatch", "Match", "Match", "NonMatch" }
    .ToImmutableList()
    .LastIndexOf("Match", index: 3, count: 4, equalityComparer: null); // Returns 2 (correct)

var lastIndexOf2 = new[] { "NonMatch", "Match", "Match", "NonMatch" }
    .ToImmutableList()
    .LastIndexOf("Match", index: 4, count: 4, equalityComparer: null); // Returns 3 (incorrect, should throw?)

Console.WriteLine($"Last index when 'index' argument equals count - 1: {lastIndexOf}");
Console.WriteLine($"Last index when 'index' argument equals count    : {lastIndexOf2}");

Expected behavior

One of the two below:

1. ImmutableList<T>.LastIndexOf(T item, int index, int count, IEqualityComparer<T>? equalityComparer) should throw if index equals the size of the collection, the same way startIndex does for ImmutableArray<T>.LastIndexOf(T item, int startIndex, int count, IEqualityComparer<T>? equalityComparer ).
2. ImmutableList<T>.LastIndexOf(T item, int index, int count, IEqualityComparer<T>? equalityComparer) should return the correct index of the last item found when the index argument equals the size of the collection.

Actual behavior

The returned index is bigger (+1) than the correct index.

Regression?

No response

Known Workarounds

No response

Configuration

• .NET 6
• Windows 10, 64-bit
• x64
• Don't know if it is specific to this version

Other information

I suspect that the culprit is a missing guard clause for the upper boundary for the index parameter in the internal int LastIndexOf(T item, int index, int count, IEqualityComparer<T>? equalityComparer) method (line 786 as of this writing) in ImmutableList_1.Node.cs. This method is called from ImmutableList_1.cs.

Contrast the guard clause in the above mentiond method with the one from ImmutableArray_1.Builder.cs
ImmutableList<T> - Requires.Range(index >= 0, nameof(index));
vs
ImmutableArray<T> - Requires.Range(startIndex >= 0 && startIndex < this.Count, nameof(startIndex));
where the latter makes more sense.

Author:	Saborion
Assignees:	-
Labels:	area-System.Collections
Milestone:	-

[krwq]

@Saborion this looks like a bug to me. We should match behavior with whatever other collections are doing. Are you perhaps interested in making PR?

[Saborion]

@krwq Uh oh. A PR for something this important. Scary.

I'll make an attempt, sure.

[stephentoub]

By the way, ImmutableArray has the same behavior, it also returns an index in a range that may go out of array's bounds.

Can you share repro?

[quixoticaxis]

Can you share repro?

Sorry, my bad, it seems I've been executing the wrong test. I've deleted my comment above.

[quixoticaxis]

I've found that FindLastIndex is also bugged for ImmutableList<T> though.

To reproduce:

[Fact] // the test should fail, but passes
public void Index_can_be_calculated_from_beyond_the_boundary()
{
    var array = ImmutableList.Create(1, 2, 3, 4);

    var index = array.FindLastIndex(55, 4, (element) => element is 3);

    Assert.Equal(54, index);
}

Both overrides in the code of Node that take index miss the check on index being less than the length.

[Saborion]

I've found that FindLastIndex is also bugged for ImmutableList<T> though.

To reproduce:

[Fact] // the test should fail, but passes
public void Index_can_be_calculated_from_beyond_the_boundary()
{
    var array = ImmutableList.Create(1, 2, 3, 4);

    var index = array.FindLastIndex(55, 4, (element) => element is 3);

    Assert.Equal(54, index);
}

Both overrides in the code of Node that take index miss the check on index being less than the length.

Yes, good catch. I noticed that as well since I discovered the original bug when writing a wrapper. Chances are I would have missed it though.

[Saborion]

I have been busy but was just about to give this a go. Before doing so, however, I am curious. This will be a change of behavior which may have impact on existing applications, since the above mentioned methods (and potentially more) will now start to throw exceptions for previously "accepted" values.

Based on the information in breaking changes I guess the changes to the 2+ mentioned methods would fall into bucket 2, "decreasing the range of accepted values within a given parameter" and would "require talking to the repo owners first".

I am now sure how to get the repo owners input on this? Based on the bot action earlier it seems this fix is for the System.Collections area, and based on area owners the owners are @dotnet/area-system-collections?