Switching ReadOnlySpan<char> with constant strings

[Happypig375]

Speclet: https://github.com/dotnet/csharplang/blob/main/proposals/csharp-11.0/pattern-match-span-of-char-on-string.md

With the recent addition of Spans, we can reduce a lot of allocations when dealing with strings. For example, substrings can be replaced with slices. However, there is one place where using strings is better:

string str = ...;
switch (str)
{
    case "string 1":
        break;
    case "string 2":
        break;
    case "string 3":
        break;
    case "string 4":
        break;
}

With spans, you are forced to write boilerplate code:

ReadOnlySpan<char> span = ...;
switch (span)
{
    case var _ where span == "string 1":
        break;
    case var _ where span == "string 2":
        break;
    case var _ where span == "string 3":
        break;
    case var _ where span == "string 4":
        break;
}

Which is identical to the if-else mess that switches aim to solve.

ReadOnlySpan<char> span = ...;
if (span == "string 1")
else if (span == "string 2")
else if (span == "string 3")
else if (span == "string 4")

It would be better if spans can be switched with constant strings.

ReadOnlySpan<char> span = ...;
switch (span)
{
    case "string 1":
        break;
    case "string 2":
        break;
    case "string 3":
        break;
    case "string 4":
        break;
}

Special-casing spans as a compiler-known type already have precedent in stackalloc expressions, it can also be done here.
Possible extension to regular Span<char> can also be considered, but it is not as important as ReadOnlySpan<char>. We could also enable this with ReadOnlyMemory<char> and Memory<char>.

More possible extensions: switching (ReadOnly)Span<char> with char, (ReadOnly)Span<T> with T where T is a constant type.

Design meetings

https://github.com/dotnet/csharplang/blob/main/meetings/2022/LDM-2022-02-23.md#pattern-matching-over-spanchar

[agocke]

This does seem really annoying. I'm not sure I have a language proposal that would fix this, but it would be something I'd like to address.

The obvious route would be something like an implicit conversion on string to ReadOnlySpan<char>. I'm not sure if that would work.

[Happypig375]

The obvious route would be something like an implicit conversion on string to ReadOnlySpan<char>. I'm not sure if that would work.

Yes it does exist in .NET Core 2.1 (NOT with the portable version!!)
However, it is not considered to be a constant conversion (e.g. int → byte). The compiler prohibits that inside switch statements.

If this was implemented, this should work with the portable version too.

[CyrusNajmabadi]

Note: is there an idea on what the codegen here would actually be? The normal string-switch works by building a dictionary and switching on that. That likely wouldn't work for ReadOnlySpans. Perhaps emitting code for an inline-trie might be appropriate?

[svick]

@CyrusNajmabadi

The normal string-switch works by building a dictionary and switching on that. That likely wouldn't work for ReadOnlySpans.

Why not? As far as I can tell, it doesn't actually use Dictionary. Instead it computes the hash code (using Roslyn-generated method) and then uses binary search on that. I think all of that should work for ROS.

[scalablecory]

@CyrusNajmabadi @svick Dictionary was generated back in the day. hash-based switch was introduced with the Roslyn migration.

[scalablecory]

I'd like for switch to be extended to support ReadOnlySpan. Seems like low-hanging fruit.

[CyrusNajmabadi]

Oh terrific. Good to know!

It does seem a bit interesting to me that it both has to scan the string to produce the hash, and then has to do the equality check again. It feels like a double pass of the string, when only one would be necessary since you're generating the code here manually.

But maybe it would be a bit too much codebloat, or too branchy, when this can be very simple codegen.

[scalablecory]

@CyrusNajmabadi the comparison is necessary. you can make a perfect hash function to avoid collisions among your cases, but it's still possible for your input string to not be one of the switch options.

We'd need something akin to VC++'s __assume(0).

[CyrusNajmabadi]

@scalablecory I understand the need for the compare if you go the hash route.

I was saying that i was suprised that the hash-route was used in the first place, isntead of just codegening something like a trie.

[Happypig375]

https://visualstudiomagazine.com/Articles/2015/10/20/Text-Pattern-Search-Trie-Class-NET.aspx?m=1&Page=2

It states that a trie would be slower than a HashSet when searching entire strings. A trie would be faster if we are using pattern searching, but switches are not for that.

[HaloFour]

@Happypig375

The trie clearly searches more efficiently but loses the battle in the Insertion operation.

There would be no insertion operations. The compiler wouldn't be populating a generic trie container, it would be generating the trie-comparisons directly based on the literal strings provided.

[CyrusNajmabadi]

Your link says this:

The trie clearly searches more efficiently but loses the battle in the Insertion operation. But as I noted earlier, if you know you'll get frequent search operations instead of frequent insertion/deletion operations, it definitely pays off to implement the trie.

[CyrusNajmabadi]

it would be generating the trie-comparisons directly based on the literal strings provided.

yes. that's what i'm trying to say. Effectivley, right now the compiler has to walk every character of the string, to produce the hash. It then has to switch on the hash, and once done, the runtime has to then walk every character of the string a second time.

This is basically the poster case for when you want a trie. Instead of having two loops of the string, you just walk each character of it one at a time, and you either end up exactly in the matching branch, or you fall out into the default branch label.

[Happypig375]

@HaloFour @CyrusNajmabadi
Only Figure 7 in the link is relevant to my point. The rest are irrelevant.

I am talking about trie vs HashSet, not trie vs List or trie vs SortedList!!!