From 509bd09a994365065550bcac4c821b15b8c6dbf0 Mon Sep 17 00:00:00 2001 From: Rex Kerr Date: Thu, 16 Jan 2014 08:23:24 -0800 Subject: SI-8153 Mutation is hard, let's go shopping with an empty list Changed the implementation of iterator to be more robust to mutation of the underlying ListBuffer. Added a test to make sure bug is gone. Fixed an "unsafe" usage of ListBuffer.iterator in the compiler, and added a comment explaining the (new) policy for iterating over a changing ListBuffer. The compiler now uses a synchronized-wrapped ArrayBuffer instead of ListBuffer, as that makes the (custom) units Iterator more natural to write (and avoids O(n) lookups). --- src/compiler/scala/tools/nsc/Global.scala | 30 +++++++++++++++++----- .../scala/collection/mutable/ListBuffer.scala | 27 ++++++++++--------- test/files/run/t8153.check | 1 + test/files/run/t8153.scala | 14 ++++++++++ 4 files changed, 51 insertions(+), 21 deletions(-) create mode 100644 test/files/run/t8153.check create mode 100644 test/files/run/t8153.scala diff --git a/src/compiler/scala/tools/nsc/Global.scala b/src/compiler/scala/tools/nsc/Global.scala index 1617db7517..81e96b76ac 100644 --- a/src/compiler/scala/tools/nsc/Global.scala +++ b/src/compiler/scala/tools/nsc/Global.scala @@ -1214,7 +1214,26 @@ class Global(var currentSettings: Settings, var reporter: Reporter) /** Have we already supplemented the error message of a compiler crash? */ private[nsc] final var supplementedError = false - private val unitbuf = new mutable.ListBuffer[CompilationUnit] + private class SyncedCompilationBuffer { self => + private val underlying = new mutable.ArrayBuffer[CompilationUnit] + def size = synchronized { underlying.size } + def +=(cu: CompilationUnit): this.type = { synchronized { underlying += cu }; this } + def head: CompilationUnit = synchronized{ underlying.head } + def apply(i: Int): CompilationUnit = synchronized { underlying(i) } + def iterator: Iterator[CompilationUnit] = new collection.AbstractIterator[CompilationUnit] { + private var used = 0 + def hasNext = self.synchronized{ used < underlying.size } + def next = self.synchronized { + if (!hasNext) throw new NoSuchElementException("next on empty Iterator") + used += 1 + underlying(used-1) + } + } + def toList: List[CompilationUnit] = synchronized{ underlying.toList } + } + + private val unitbuf = new SyncedCompilationBuffer + val compiledFiles = new mutable.HashSet[String] /** A map from compiled top-level symbols to their source files */ @@ -1225,9 +1244,8 @@ class Global(var currentSettings: Settings, var reporter: Reporter) private var phasec: Int = 0 // phases completed private var unitc: Int = 0 // units completed this phase - private var _unitbufSize = 0 - def size = _unitbufSize + def size = unitbuf.size override def toString = "scalac Run for:\n " + compiledFiles.toList.sorted.mkString("\n ") // Calculate where to stop based on settings -Ystop-before or -Ystop-after. @@ -1452,7 +1470,6 @@ class Global(var currentSettings: Settings, var reporter: Reporter) /** add unit to be compiled in this run */ private def addUnit(unit: CompilationUnit) { unitbuf += unit - _unitbufSize += 1 // counting as they're added so size is cheap compiledFiles += unit.source.file.path } private def checkDeprecatedSettings(unit: CompilationUnit) { @@ -1468,11 +1485,10 @@ class Global(var currentSettings: Settings, var reporter: Reporter) /* !!! Note: changing this to unitbuf.toList.iterator breaks a bunch of tests in tests/res. This is bad, it means the resident compiler relies on an iterator of a mutable data structure reflecting changes - made to the underlying structure (in whatever accidental way it is - currently depending upon.) + made to the underlying structure. */ def units: Iterator[CompilationUnit] = unitbuf.iterator - + def registerPickle(sym: Symbol): Unit = () /** does this run compile given class, module, or case factory? */ diff --git a/src/library/scala/collection/mutable/ListBuffer.scala b/src/library/scala/collection/mutable/ListBuffer.scala index 7f54692c8b..e76825cea9 100644 --- a/src/library/scala/collection/mutable/ListBuffer.scala +++ b/src/library/scala/collection/mutable/ListBuffer.scala @@ -381,6 +381,12 @@ final class ListBuffer[A] this } + /** Returns an iterator over this `ListBuffer`. The iterator will reflect + * changes made to the underlying `ListBuffer` beyond the next element; + * the next element's value is cached so that `hasNext` and `next` are + * guaranteed to be consistent. In particular, an empty `ListBuffer` + * will give an empty iterator even if the `ListBuffer` is later filled. + */ override def iterator: Iterator[A] = new AbstractIterator[A] { // Have to be careful iterating over mutable structures. // This used to have "(cursor ne last0)" as part of its hasNext @@ -389,22 +395,15 @@ final class ListBuffer[A] // a structure while iterating, but we should never return hasNext == true // on exhausted iterators (thus creating exceptions) merely because // values were changed in-place. - var cursor: List[A] = null - var delivered = 0 - - // Note: arguably this should not be a "dynamic test" against - // the present length of the buffer, but fixed at the size of the - // buffer when the iterator is created. At the moment such a - // change breaks tests: see comment on def units in Global.scala. - def hasNext: Boolean = delivered < ListBuffer.this.length + var cursor: List[A] = if (ListBuffer.this.isEmpty) Nil else start + + def hasNext: Boolean = cursor ne Nil def next(): A = - if (!hasNext) - throw new NoSuchElementException("next on empty Iterator") + if (!hasNext) throw new NoSuchElementException("next on empty Iterator") else { - if (cursor eq null) cursor = start - else cursor = cursor.tail - delivered += 1 - cursor.head + val ans = cursor.head + cursor = cursor.tail + ans } } diff --git a/test/files/run/t8153.check b/test/files/run/t8153.check new file mode 100644 index 0000000000..0cfbf08886 --- /dev/null +++ b/test/files/run/t8153.check @@ -0,0 +1 @@ +2 diff --git a/test/files/run/t8153.scala b/test/files/run/t8153.scala new file mode 100644 index 0000000000..f9b223f974 --- /dev/null +++ b/test/files/run/t8153.scala @@ -0,0 +1,14 @@ +object Test { + def f() = { + val lb = scala.collection.mutable.ListBuffer[Int](1, 2) + val it = lb.iterator + if (it.hasNext) it.next + val xs = lb.toList + lb += 3 + it.mkString + } + + def main(args: Array[String]) { + println(f()) + } +} -- cgit v1.2.3