SI-7838 Document the multi-threading semantics of List and Vector

Making them completely thread-safe would be too expensive (in terms
of performance of single-threaded use cases).

3 files changed, 15 insertions, 0 deletions

diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala
index c09328cae6..45b761fc00 100644
--- a/src/library/scala/collection/immutable/List.scala
+++ b/src/library/scala/collection/immutable/List.scala
@@ -25,6 +25,8 @@ import java.io.{ObjectOutputStream, ObjectInputStream}
  *  This class is optimal for last-in-first-out (LIFO), stack-like access patterns. If you need another access
  *  pattern, for example, random access or FIFO, consider using a collection more suited to this than `List`.
  *
+ *  $usesMutableState
+ *
  *  ==Performance==
  *  '''Time:''' `List` has `O(1)` prepend and head/tail access. Most other operations are `O(n)` on the number of elements in the list.
  *  This includes the index-based lookup of elements, `length`, `append` and `reverse`.
diff --git a/src/library/scala/collection/immutable/Traversable.scala b/src/library/scala/collection/immutable/Traversable.scala
index 5fc0607a00..3d4ba95a16 100644
--- a/src/library/scala/collection/immutable/Traversable.scala
+++ b/src/library/scala/collection/immutable/Traversable.scala
@@ -18,6 +18,17 @@ import mutable.Builder
 /** A trait for traversable collections that are guaranteed immutable.
  *  $traversableInfo
  *  @define mutability immutable
+ *
+ *  @define usesMutableState
+ *
+ *    Note: Despite being an immutable collection, the implementation uses mutable state internally during
+ *    construction. These state changes are invisible in single-threaded code but can lead to race conditions
+ *    in some multi-threaded scenarios. The state of a new collection instance may not have been "published"
+ *    (in the sense of the Java Memory Model specification), so that an unsynchronized non-volatile read from
+ *    another thread may observe the object in an invalid state (see
+ *    [[https://issues.scala-lang.org/browse/SI-7838 SI-7838]] for details). Note that such a read is not
+ *    guaranteed to ''ever'' see the written object at all, and should therefore not be used, regardless
+ *    of this issue. The easiest workaround is to exchange values between threads through a volatile var.
  */
 trait Traversable[+A] extends scala.collection.Traversable[A]
 //                         with GenTraversable[A]
diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala
index 539ae9c387..0d83925bb0 100644
--- a/src/library/scala/collection/immutable/Vector.scala
+++ b/src/library/scala/collection/immutable/Vector.scala
@@ -40,6 +40,8 @@ object Vector extends IndexedSeqFactory[Vector] {
  *  endian bit-mapped vector trie with a branching factor of 32.  Locality is very good, but not
  *  contiguous, which is good for very large sequences.
  *
+ *  $usesMutableState
+ *
  *  @see [[http://docs.scala-lang.org/overviews/collections/concrete-immutable-collection-classes.html#vectors "Scala's Collection Library overview"]]
  *  section on `Vectors` for more information.
  *