Task: Backport AlternateLookup for IEqualityComparer<T> and ReadOnlySpan<T> #169
Description
Microsoft came up with a powerful design for looking up dictionary and hash set keys based on ReadOnlySpan<T>, however they modified the compiler to provide an allows ref struct constraint which does not work prior to .NET 9. So, we will need to take a different approach.
Since we only need to support ReadOnlySpan<T> for alternate keys, we will use a narrower scope for the design.
Design Proposal
The backport will consist of a few different parts.
Interface
Much like the original IAlternateEqualityComparer<TAlternate, T> design, we will implement the same 3 members, but shift the ReadOnlySpan<T> to the interface definition so it will compile on older target frameworks.
namespace J2N.Collections.Generic
{
public interface ISpanAlternateEqualityComparer<TAlternateSpan, T>
{
bool Equals(ReadOnlySpan<TAlternateSpan> alternate, T other);
int GetHashCode(ReadOnlySpan<TAlternateSpan> alternate);
T Create(ReadOnlySpan<TAlternateSpan> alternate);
}
}Note that we can copy the documentation from upstream and alter it slightly for our use case.
SpanAlternateLookup<TAlternateSpan> Structs
This will basically be a copy of the AlternateLookup<TAlternate> structs for Dictionary<TKey, TValue>, OrderedDictionary<TKey, TValue>, HashSet<T> and OrderedHashSet<T>, also shifting the ReadOnlySpan<T> to each member rather than making them purely generic.
However, unlike the original design, we don't have to conditionally compile for older target frameworks because we are targeting our own alternate comparer interface and we are not using an allows ref struct constraint.
namespace J2N.Collections.Generic
{
public class Dictionary<TKey, TValue>
{
public SpanAlternateLookup<TAlternateKeySpan> GetSpanAlternateLookup<TAlternateKeySpan>();
public bool TryGetSpanAlternateLookup<TAlternateKeySpan>(out SpanAlternateLookup<TAlternateKeySpan> lookup);
public readonly struct SpanAlternateLookup<TAlternateKeySpan>
{
public Dictionary<TKey, TValue> Dictionary { get; }
public TValue this[ReadOnlySpan<TAlternateKeySpan> key] { get; set; }
public bool TryGetValue(ReadOnlySpan<TAlternateKeySpan> key, [MaybeNullWhen(false)] out TValue value);
public bool TryGetValue(ReadOnlySpan<TAlternateKeySpan> key, [MaybeNullWhen(false)] out TKey actualKey, [MaybeNullWhen(false)] out TValue value);
public bool ContainsKey(ReadOnlySpan<TAlternateKeySpan> key);
public bool Remove(ReadOnlySpan<TAlternateKeySpan> key);
public bool Remove(ReadOnlySpan<TAlternateKeySpan> key, [MaybeNullWhen(false)] out TKey actualKey, [MaybeNullWhen(false)] out TValue value);
public bool TryAdd(ReadOnlySpan<TAlternateKeySpan> key, TValue value);
}
}
public class OrderedDictionary<TKey, TValue>
{
public SpanAlternateLookup<TAlternateKeySpan> GetSpanAlternateLookup<TAlternateKeySpan>();
public bool TryGetSpanAlternateLookup<TAlternateKeySpan>(out SpanAlternateLookup<TAlternateKeySpan> lookup);
public readonly struct SpanAlternateLookup<TAlternateKeySpan>
{
public OrderedDictionary<TKey, TValue> Dictionary { get; }
public TValue this[ReadOnlySpan<TAlternateKeySpan> key] { get; set; }
public bool TryGetValue(ReadOnlySpan<TAlternateKeySpan> key, [MaybeNullWhen(false)] out TValue value);
public bool TryGetValue(ReadOnlySpan<TAlternateKeySpan> key, [MaybeNullWhen(false)] out TKey actualKey, [MaybeNullWhen(false)] out TValue value);
public bool ContainsKey(ReadOnlySpan<TAlternateKeySpan> key);
public bool Remove(ReadOnlySpan<TAlternateKeySpan> key);
public bool Remove(ReadOnlySpan<TAlternateKeySpan> key, [MaybeNullWhen(false)] out TKey actualKey, [MaybeNullWhen(false)] out TValue value);
public int IndexOf(ReadOnlySpan<TAlternateKeySpan> key);
public bool TryAdd(ReadOnlySpan<TAlternateKeySpan> key, TValue value);
}
}
public class HashSet<T>
{
public SpanAlternateLookup<TAlternateSpan> GetSpanAlternateLookup<TAlternateSpan>();
public bool TryGetSpanAlternateLookup<TAlternateSpan>(out SpanAlternateLookup<TAlternateSpan> lookup);
public readonly struct SpanAlternateLookup<TAlternateSpan>
{
public HashSet<T> Set { get; }
public bool Add(ReadOnlySpan<TAlternateSpan> item);
public bool Remove(ReadOnlySpan<TAlternateSpan> item);
public bool Contains(ReadOnlySpan<TAlternateSpan> item);
public bool TryGetValue(ReadOnlySpan<TAlternateSpan> equalValue, [MaybeNullWhen(false)] out T actualValue);
}
}
public class OrderedHashSet<T>
{
public SpanAlternateLookup<TAlternateSpan> GetSpanAlternateLookup<TAlternateSpan>();
public bool TryGetSpanAlternateLookup<TAlternateSpan>(out SpanAlternateLookup<TAlternateSpan> lookup);
public readonly struct SpanAlternateLookup<TAlternateSpan>
{
public OrderedHashSet<T> Set { get; }
public bool Add(ReadOnlySpan<TAlternateSpan> item);
public bool Remove(ReadOnlySpan<TAlternateSpan> item);
public bool Contains(ReadOnlySpan<TAlternateSpan> item);
public bool TryGetValue(ReadOnlySpan<TAlternateSpan> equalValue, [MaybeNullWhen(false)] out T actualValue);
public int IndexOf(ReadOnlySpan<TAlternateSpan> value);
}
}
}CollectionMarshal Support
Much like the original design, we will need new members on CollectionMarshal for supporting low-level code.
namespace J2N.Runtime.InteropServices
{
public static class CollectionMarshal
{
public static ref TValue GetValueRefOrNullRef<TKey, TValue, TAlternateKeySpan>(Dictionary<TKey, TValue>.SpanAlternateLookup<TAlternateKeySpan> dictionary, ReadOnlySpan<TAlternateKeySpan> key);
public static ref TValue GetValueRefOrNullRef<TKey, TValue, TAlternateKeySpan>(OrderedDictionary<TKey, TValue>.SpanAlternateLookup<TAlternateKeySpan> dictionary, ReadOnlySpan<TAlternateKeySpan> key);
public static ref TValue? GetValueRefOrAddDefault<TKey, TValue, TAlternateKeySpan>(Dictionary<TKey, TValue>.SpanAlternateLookup<TAlternateKeySpan> dictionary, ReadOnlySpan<TAlternateKeySpan> key, out bool exists);
public static ref TValue? GetValueRefOrAddDefault<TKey, TValue, TAlternateKeySpan>(OrderedDictionary<TKey, TValue>.SpanAlternateLookup<TAlternateKeySpan> dictionary, ReadOnlySpan<TAlternateKeySpan> key, out bool exists);
}
}String Comparer Wrappers
We will also need to add support for the ISpanAlternateEqualityComparer<TAlternateSpan, T> interface in our internal wrappers. This should be all that is required to support the BCL string comparers, but we will need tests to confirm the functionality works.
namespace J2N.Collections.Generic
{
internal class NonRandomizedStringEqualityComparer
{
private sealed class OrdinalComparer : NonRandomizedStringEqualityComparer, ISpanAlternateEqualityComparer<char, string?>
#if FEATURE_IALTERNATEEQUALITYCOMPARER
, IAlternateEqualityComparer<ReadOnlySpan<char>, string?>
#endif
{
int ISpanAlternateEqualityComparer<char, string?>.GetHashCode(ReadOnlySpan<char> span);
bool ISpanAlternateEqualityComparer<char, string?>.Equals(ReadOnlySpan<char> span, string? target);
string ISpanAlternateEqualityComparer<char, string?>.Create(ReadOnlySpan<char> span);
}
private sealed class OrdinalIgnoreCaseComparer : NonRandomizedStringEqualityComparer, ISpanAlternateEqualityComparer<char, string?>
#if FEATURE_IALTERNATEEQUALITYCOMPARER
, IAlternateEqualityComparer<ReadOnlySpan<char>, string?>
#endif
{
int ISpanAlternateEqualityComparer<char, string?>.GetHashCode(ReadOnlySpan<char> span);
bool ISpanAlternateEqualityComparer<char, string?>.Equals(ReadOnlySpan<char> span, string? target);
string ISpanAlternateEqualityComparer<char, string?>.Create(ReadOnlySpan<char> span);
}
}
internal class RandomizedStringEqualityComparer
{
private sealed class OrdinalComparer : NonRandomizedStringEqualityComparer, ISpanAlternateEqualityComparer<char, string?>
#if FEATURE_IALTERNATEEQUALITYCOMPARER
, IAlternateEqualityComparer<ReadOnlySpan<char>, string?>
#endif
{
int ISpanAlternateEqualityComparer<char, string?>.GetHashCode(ReadOnlySpan<char> alternate);
bool ISpanAlternateEqualityComparer<char, string?>.Equals(ReadOnlySpan<char> alternate, string? other);
string ISpanAlternateEqualityComparer<char, string?>.Create(ReadOnlySpan<char> span);
}
private sealed class OrdinalIgnoreCaseComparer : NonRandomizedStringEqualityComparer, ISpanAlternateEqualityComparer<char, string?>
#if FEATURE_IALTERNATEEQUALITYCOMPARER
, IAlternateEqualityComparer<ReadOnlySpan<char>, string?>
#endif
{
int ISpanAlternateEqualityComparer<char, string?>.GetHashCode(ReadOnlySpan<char> alternate);
bool ISpanAlternateEqualityComparer<char, string?>.Equals(ReadOnlySpan<char> alternate, string? other);
string ISpanAlternateEqualityComparer<char, string?>.Create(ReadOnlySpan<char> span);
}
}
}Related Work
This is being described here to put it into context, but this work should not be part of this PR.
- Add AlternateLookup for
IComparer<T>andReadOnlySpan<T>-SortedDictionary<TKey, TValue>andSortedSet<T>depend onIComparer<T>to do lookups, so we will need anISpanAlternateComparer<TAlternateSpan, T>interface to handle that case. TheUnicodeSettype depends on this and needs to supportReadOnlySpan<char>. - Extension methods on
IDictionary<TKey, TValue>andISet<T>for alternate lookup. I am still debating whether it makes more sense to put these in J2N and have them gracefully degrade for unsupported collection types or to put these in Lucene.NET and ICU4N and have them throwNotSupportedExceptionif we accidentally plug in an unsupported collection type.