NoSuchElementException throw from lastOption

[JoeCqupt]

Reproduction steps

Scala version: 2.13.x

  def main(args: Array[String]): Unit = {


    val map: ConcurrentSkipListMap[Int, Int] = new ConcurrentSkipListMap[Int, Int]();
    map.put(1, 1);
    map.put(2, 3);
    map.put(3, 4);
    val subMap = map.subMap(1, 3)
    val values = subMap.values().asScala
    
    // Thead-A 
    values.lastOption.get

    // Thead-B 
    map.clear()
  }

it will occur under specific circumstances....... (Not necessarily)

Problem

when i use concurrent data structure, Iterable#lastOption maybe throw NoSuchElementException

According to the note of method, it did not declare will throw NoSuchElementException. i think we should avoid that

[JoeCqupt]

#9992 i make a pr to fix it

[som-snytt]

The doc on non-current adapters says handling non-atomic operations is on you.

This is a bit tricky, but it seems kind of obvious to just wrap it in Try(last).toOption.

I wouldn't expect the proposed solution to make a difference, as hasNext/next() is non-atomic.

The failing test is weird. I see that it uses a View. Does this mean we have to learn how views work?

[som-snytt]

scala>   val fs = List(failer, succeeder, failer, failer, succeeder, failer, failer, failer, succeeder)
val fs: List[() => Option[Int]] = List($Lambda$1024/1901663135@65bcf7c2, $Lambda$1039/1018742990@1fde0371, $Lambda$1024/1901663135@65bcf7c2, $Lambda$1024/1901663135@65bcf7c2, $Lambda$1039/1018742990@1fde0371, $Lambda$1024/1901663135@65bcf7c2, $Lambda$1024/1901663135@65bcf7c2, $Lambda$1024/1901663135@65bcf7c2, $Lambda$1039/1018742990@1fde0371)

scala> def f0 = fs.view flatMap (f => f())
def f0: scala.collection.View[Int]

scala> f0.lastOption
fail
success
fail
success
fail
fail
success
fail
fail
fail
success
val res0: Option[Int] = Some(5)

There are 9 "actions" in the list, but 11 outputs in the current code.
Expected:

scala> def gs = fs.flatMap (f => f())
def gs: List[Int]

scala> gs.lastOption
fail
success
fail
fail
success
fail
fail
fail
success
val res2: Option[Int] = Some(5)

[JoeCqupt]

CI shows a test failure in run/view-headoption.scala

Before code alter （ Original implementation）：

def lastOption: Option[A] = if (isEmpty) None else Some(last)

it will invoke method isEmpty, this method will invoke iterator.hasNext

def isEmpty: Boolean = !iterator.hasNext

hasNext inner wil invoke method nextCur, it will cause item of iterator apply to param function until result iterator hasNext is True.

isEmpty method will cause console output:

fail
success

After code alter :

def lastOption: Option[A] = {
    val it = iterator
    if (!it.hasNext) {
      None
    } else {
      var lst = it.next()
      while (it.hasNext) lst = it.next()
      Some(lst)
    }
  }

i do not invoke method isEmpty. so the output of console will not match !!

i think we should update test/files/run/view-headoption.check file

@som-snytt

[som-snytt]

Thanks, I think that must be a bug, as one expects a view to be lazy and also not evaluate more than required.

I still assume your PR doesn't address this ticket. But since you already have a test case, you could try the fix locally.

[JoeCqupt]

I wouldn't expect the proposed solution to make a difference, as hasNext/next() is non-atomic.

Before code alter （ Original implementation）：

def lastOption: Option[A] = if (isEmpty) None else Some(last)

it will invoke method isEmpty, this method has many implementations, eg:

  case class JCollectionWrapper[A](underlying: ju.Collection[A])
    extends AbstractIterable[A]
      with StrictOptimizedIterableOps[A, Iterable, Iterable[A]]
      with Serializable {
    def iterator = underlying.iterator.asScala
    override def size = underlying.size
    override def knownSize: Int = if (underlying.isEmpty) 0 else super.knownSize
    override def isEmpty = underlying.isEmpty
    override def iterableFactory = mutable.ArrayBuffer
  }

  @SerialVersionUID(3L)
  case class JIterableWrapper[A](underlying: jl.Iterable[A])
    extends AbstractIterable[A]
      with StrictOptimizedIterableOps[A, Iterable, Iterable[A]]
      with Serializable {
    def iterator = underlying.iterator.asScala
    override def iterableFactory = mutable.ArrayBuffer
    override def isEmpty: Boolean = !underlying.iterator().hasNext
  }

JIterableWrapper will use iterator to judge .

if the result of judgement is true

the next step invoke method: last

  def last: A = {
    val it = iterator
    var lst = it.next()
    while (it.hasNext) lst = it.next()
    lst
  }

it will get the other iterator to use. the two step do not use a same iterator.

meanwhile please refer the implementation of headOption. it use one iterator

  def headOption: Option[A] = {
    val it = iterator
    if(it.hasNext) Some(it.next()) else None
  }

use one iterator will avoid NoSuchElementException

[som-snytt]

I also looked at the wrappers, there's the concurrent wrapper; but whether you do values.asScala.last or map.asScala.values.last, I assume that you have hasNext on one thread, followed by possible clear on another, before you get to do next.

I think it's easier just to if isEmpty then None else Try(next).toOption. Or only handle no such element, etc. But I haven't looked at JiterableWrapper yet.

[som-snytt]

I wouldn't expect the proposed solution to make a difference, as hasNext/next() is non-atomic.

My previous expectation was mistaken. The underlying iterator ensures hasNext and next are consistent, even if the underlying map is cleared.