Imported From: https://issues.scala-lang.org/browse/SI-10177?orig=1
Reporter: Thomas Dickerson (thomas.dickerson)
Affected Versions: 2.11.8

Thomas Dickerson (thomas.dickerson) said:
It appears that modifying _.values.headOption to _.readOnlySnapshot.values.headOption in my code fixes the problem, but it seems like highly unexpected behavior that the semantics of these differ (i.e. every iterator returned by functions on a TrieMap should be over a readOnlySnapshot, since this is the core feature advertised in the documention: {quote}It supports O(1), atomic, lock-free snapshots which are used to implement linearizable lock-free size, iterator and clear operations{quote})

@retronym said (edited on Feb 9, 2017 4:22:58 AM UTC):
Inlining some implementations of values, valuesIterator, headOption, head, and isEmpty:

  def fail[K, B](self: TrieMap[K, V]): Option[V] = {
    val v1: Iterable[V] = new AbstractIterable[V] with Iterable[V] with Serializable {
      def iterator = new AbstractIterator[V] {
        val iter = self.iterator
        def hasNext = iter.hasNext
        def next() = iter.next()._2
      }
      override def size = self.size
      override def foreach[U](f: V => U) = self.valuesIterator foreach f
    }
    if (v1.size == 0) None else Some(v1.iterator.next())
  }

Shows that the override of TrieMap#iterator as:

  def iterator: Iterator[(K, V)] =
    if (nonReadOnly) readOnlySnapshot().iterator
    else new TrieMapIterator(0, this)

Is insufficient to make .values.headOption work with a single version of the datastructure, as we end up calling TrieMap#iterator more than once within that operation.

An override like:

  override def valuesIterator: Iterator[V] = {
    if (nonReadOnly) readOnlySnapshot().valuesIterator
    else super.valuesIterator
  }

  override def keysIterator: Iterator[K] = {
    if (nonReadOnly) readOnlySnapshot().keysIterator
    else super.keysIterator
  }

WDYT, [~prokopec]?

@axel22 said (edited on Feb 9, 2017 4:14:26 PM UTC):
I though that if (v1.size == 0) None else Some(v1.iterator.next()) is where the race condition comes from, no? I mean, both size and iterator here result in calling the iterator separately.

Seems like you would have to create the snapshot in the new AbstractIterable ... only once, and use that for the iterator.

@retronym said:
@axel22 I've tried to restrict the change to TrieMap, rather than modifying MapLike.

scala/scala#5687