Seq(1).indexOfSlice(Nil, -2)==-2

[noresttherein]

Reproduction steps

Scala version: 2.13.10

Expected: 0, same as in Vector.

What's worse, Vector(1).indexOfSlice(List(1), -2) == -2, too (substitute any Seq for Vector).

[SethTisue]

@scala/collections

[som-snytt]

That is actually consistent with the precise or precious Scaladoc.

the first index >= from such that the elements of this sequence starting at this index match the elements of sequence that, or -1 if no such subsequence exists.

[som-snytt]

The PR trivially adjusts the malicious from. It would be nice if we had some sort of tool to verify that the collections satisfy a set of "laws" of some kind. In lieu of that, I augmented the unit test to exercise both paths (sizes known and unknown).

[noresttherein]

The PR trivially adjusts the malicious from. It would be nice if we had some sort of tool to verify that the collections satisfy a set of "laws" of some kind. In lieu of that, I augmented the unit test to exercise both paths (sizes known and unknown).

Will it work for Seq(1).indexOfSlice(Nil, 1), which currently returns -1 (but, correctly, 1 for Vector)?

[som-snytt]

@noresttherein see the PR comment, I went the other way, but I'm not religious about it.

[SethTisue]

It would be nice if we had some sort of tool to verify that the collections satisfy a set of "laws" of some kind

we do, scala-collection-laws: https://github.com/scala/scala-collection-laws

though the fact that they aren't in-repo leads to neglect

[som-snytt]

Thanks, Seth, for not calling out my sarcasm. I have a fork and will try again to make headway with it. The sarcasm was really my choice between sarcasm and self-deprecation, much like choosing whether to allow indexOfSlice past the last index, there is a kind of arbitrary equivalence that merely shifts the burden of awareness.

[noresttherein]

I think it is still wrong:
Seq(1).indexOfSlice(Nil, 1) should probably return 1. It does for List.

     if (from0 > l) -1 //non strict
     else if (tl < 1) from0

[som-snytt]

List is the default Seq. Did you mean Vector currently returns 1? My comment was that I changed that to work the same as List, but I'm open to whatever the community consensus is. I spent a few minutes with collections-laws, which I now refer to as claws; whatever is decided should be encoded/enshrined there.

scala> Seq(1).indexOfSlice(Nil, 1)
val res0: Int = -1

scala> List(1).indexOfSlice(Nil, 1)
val res1: Int = -1

Edit: an argument in favor of returning the last index plus one is that it is consistent with patch, which is permissive. Also lastIndexOfSlice and startsWith.

I thought indexOfSlice should return legal indices (like indexOf), something I can xs(i), but that's only true for existing elements. So probably I'll flip it to your way of thinking and see how it flies.

Welcome to Scala 2.13.10 (OpenJDK 64-Bit Server VM, Java 19).
Type in expressions for evaluation. Or try :help.

scala> val xs = (1 to 10).toList
val xs: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> xs.indexOfSlice(Nil, 10)
val res0: Int = -1

scala> xs.patch(10, List(42), 100)
val res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 42)

scala> xs.indices
val res2: scala.collection.immutable.Range = Range 0 until 10

scala> xs.lastIndexOfSlice(Nil, 10)
val res3: Int = 10

scala> xs.startsWith(Nil, 10)
val res4: Boolean = true

[sjrd]

I expect xs.indexOfSlice(Nil, i) to return i for 0 <= i <= xs.size. In particular, definitely i and not -1 when i == xs.size.

More generally, I guess a good "law" would be that xs.indexOfSlice(ys, from) returns some idx >= 0 iff idx is the smallest value such that idx >= from and xs.slice(idx, idx + ys.size) == ys (and -1 if no such idx exists).

[lrytz]

I find it confusing for an indexOfSomething method to return an invalid positive index, but there can be arguments either way. Ultimately it's a matter of agreeing on a specification. Related to #12795 (comment).

[sjrd]

But for slice, xs.size is not an invalid index. xs.slice(xs.size, xs.size) is perfectly valid. (and making it invalid for the sake of it is actively harmful in practice).

Another way to look at it is that indices never point to elements. Only ranges of indices point to elements. When we say apply(i), we are truly asking for the one element in the range [i, i+1). And that is invalid because i+1 is invalid when i == xs.size. But the range [i, i) is a valid empty range as long as 0 <= i <= xs.size.