`SeqOps.indexOfSlice` defaults to using `this.tail` even for sequences other than `LinearSeq`!

[noresttherein]

Scala version: 2.13.16

1. Implementation of indexOfSlice in SeqOps is not overriden in IndexedSeqOps.
2. Neither it is overriden in Vector or ArraySeq
3. If either the argument's or this's knownSize is negative, the default implementation recursively calls this.tail.

Problem

The operation is needlessly expensive for anything but List, being even O(n^3) for ArraySeq!
This should be implemented using an iterator.

[SethTisue]

@scala/collections

[ansvonwa]

Afaik knownSize is overriden to be the actual size in ArraySeq and Vector (or some parent) and even List, so it cannot be negative and this case only happens if one of the sequences has no known size.
So, only things like (_: Vector).indexOfSlice(_: LazyList) would problematic cases, right?

[som-snytt]

Is this // TODO Should be implemented in a way that preserves laziness?

(Otherwise, if it requires overrides, this is better opened against Scala 3, which has different compatibility guarantees.)

[noresttherein]

It doesn't require overrides, as SeqOps already has a habit of checking if it is IndexedSeqOps and branching, instead of overrides in the latter (I presume because of binary compatibillity?). So it might just as well be done similarly here. The easiest way to implement it preserving laziness is to convert to LazyList first. Note that this does not in principle preclude use of KMP, as one might create the jump table as a 'lazy indexed sequence', that is something that internally feeds a growing array from an iterator.

[som-snytt]

I deleted a line from my previous comment about testing for subclasses, as I didn't want to sound whiny or defeatist. (There were a couple of such cases, which are squirrely maintenance burdens; but maybe Scala 3 having its own lib is an argument in favor of such hacks.) Maybe I will try this, as I've already done the wordle. Also tempted by the sunk cost of having read and written comments.

This stuff is taxing. (paulp, 2011)

Massive redesign so that: scala> "hi" == "hi".reverse.reverse gives: res0: Boolean = true (odersky, 2009)

there is still a lot of room for improvement in these classes (szeiger, 2019)

The related complaint was #11708, just to demonstrate real use cases.