Array patterns (and varargs patterns)

[Brian Goetz]

> I recall in one of your earlier talks, (probably 
> https://www.youtube.com/watch?v=n3_8YcYKScw 
> <https://urldefense.com/v3/__https://www.youtube.com/watch?v=n3_8YcYKScw__;!!GqivPVa7Brio!NNoWuHFSTT_CWr3esqqvb8CcBj440fvfjTEkaTpudwsi8FeLitelRqFUb3xGO9CeCg$>) 
> you talked about how at runtime, switch dispatch could be implemented 
> as a decision tree with constant time (O(1)) complexity. Is this still 
> true with static patterns in the mix? I think with static patterns 
> since the method will need to be executed, from the code author's 
> perspective, it is no longer a constant time evaluation - is that fair 
> to say?
>

Your intuition is right, but we can still do a lot to minimize the 
cost.  We don't statically inline all the patterns as is done in e.g. 
this paper: https://dl.acm.org/doi/abs/10.1145/1411304.1411311 (Java is 
separately compiled), but we can at least do an O(1) dispatch on the 
type of the target, which is often enough to prune down the search space 
a lot, if not down to one candidate.  For example, in a switch with 
heterogeneous target types:

     case Point(var x, var y):
     case LocalDate(int year, int month, int day):
     case Optional.of(var x):

we can still select which of the three are candidates in O(1) time (at 
most one is), because the target type of each pattern is different 
(String, LocalDate, Optioal) and we can do a hash-based lookup on 
target.getClass().  If we fall into the `case Optional.of()` pattern, we 
still have to execute the pattern to see if there is a value present, 
and might keep going after that if there are more, but we don't have to 
backtrack.

If we had a pathological case where the target types were all the same:

     case palindromicString(var s):
     case integerString(int i):
     case floatString(float f):
     case complexNumberString(Complex c):
     ...

we would indeed have to linearly execute the patterns until we found a 
match.  But, even in this pathological case, the JIT may offer some help 
(inlining, etc) that optimizes the selection.