Needle type

[mhofman]

The key caveat is that the needle (the subsequence being searched for) must be of the same element-type as the haystack (the TypedArray that is being searched).

What is the motivation for this? Why not accept any array-like of elements, like TypedArray.from?

[jasnell]

Primarily interpretation. If the haystack is a Float64Array and the needle is a Uint16Array, what does that actually mean, etc. Not opposed to support any array-like just think it adds a bit more complexity to deal with different interpretations of the bytes.

[jasnell]

It also makes alignment of the subsequences difficult. If the element length of the haystack is 8-bytes for instance, and the needle is 2-bytes and the length is not a multiple of 8, is the search actually meaningful?

[bakkot]

I think there's really only one way it could work, which is to coerce¹ each value in the array-like to the TA's type in the same way that TA.from does.

I am slightly in favor of allowing this just so that you don't have to materialize a TA for the needle, which can be much more expensive than using an Array (in particular I think TAs are always heap-allocated in some runtimes).

Footnotes

1. I would have it throw if any of the values in the array-like are not numbers/bigints (matching the haystack TA); by "coerce" I mean like ToInt32(number) not ToInt32(arbitrary value). ↩

[jasnell]

Yeah that could work but to be honest I'm not personally aware of significant use cases where that would be needed. In the case of Node.js' Buffer.prototype.indexOf override, it's always the same type. In the cases of subsequence search on the web (like the one in next.js) it's always the same type. I'm not strongly opposed I just think we'd need use cases given the additional complexity it would require.

[bakkot]

I think the case of searching for a TA within a TA of a different type is quite unusual, yes. The case I care about is searching for an array in a TA. Like:

let uint8Array = await (await fetch(whatever)).bytes();
let boundary = uint8Array.findSequence([0xFF, 0xDA]);

I don't want to have to allocate a Uint8Array just to hold [0xFF, 0xDA] so I can do a search.

But once you're supporting this case anyway, supporting TAs not just Arrays basically falls out for free.

[jasnell]

Ah! ok, I understand now. Sorry, brain is operating on Jet Lag Time. Ok, so yeah, absolutely valid case... hmm, going to have to think through how that could be supported while also supporting an optional implementation-defined optimization path.

[bakkot]

In practice, because the lookups in the receiver have no side effects, and because it's easy to check if lookups on an Array have no side effects, I think it is very easy to optimize anyway, without needing to do anything special in the spec. Engines can check if the argument is a same-typed TA, a different-typed TA, or a non-sparse array with no numeric getters/setters, and do the appropriate fast paths for each of those, with a slow fallback for anything else.