Scala Programming Language
  1. Scala Programming Language
  2. SI-5377

Stream#permutations could produce incorrect value of Iterator[Stream]

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: Scala 2.9.1
    • Fix Version/s: Scala 2.10.0
    • Component/s: Collections
    • Labels:
    • Environment:

      Scala 2.9.1.final(scalac), Java HotSpot(TM) 64-Bit Server VM(1.6.0_26), Windows 7 Home Premium 64 bit

      Description

      I wrote following program to check behavior of Stream#permutations() and it compiled with scalac.

      StreamPermutationBug.scala
      object StreamPermutationBug {
        def main(args: Array[String]) {
          val list = List(1, 2)
          println("from: " + list)
      
          // expected result
          list.permutations.map(_.toList).foreach(println)
      
          println("---")
      
          println("from: " + list.toStream)
          // unexpected result
          list.toStream.permutations.map(_.toList).foreach(println)
      
          println("---")
      
          val range = Range(1, 3)
          println("from: " + range) 
          // unexpected result
          range.toStream.permutations.map(_.toList).foreach(println) 
        }
      }
      

      However, the output of this program is unexpected:

      Expected Result

      from: List(1, 2)
      List(1, 2)
      List(2, 1)

      from: Stream(1, ?)
      List(1, 2)
      List(2, 1)

      from: Range(1, 2)
      List(1, 2)
      List(2, 1)

      Actual Result(unexpected)

      from: List(1, 2)
      List(1, 2) // expected
      List(2, 1)

      from: Stream(1, ?)
      List(1, 1) // unexpected!
      List(2, 1)

      from: Range(1, 2)
      List(1, 1) // unexpected!
      List(2, 1)

      It seems that application of "permutations" method to Stream instances could produce incorrect value of Iterator of Stream.
      This problem is reproducable in REPL, too.

        Activity

        Hide
        Aleksandar Prokopec added a comment -

        Another stream-related source of fun - the permutations iterator constructs the collection by adding the current elements of the buffer into a builder. If the builder is lazy, it will add the elements from the buffer into the collection only after the elements in the buffer get swapped around.

        Show
        Aleksandar Prokopec added a comment - Another stream-related source of fun - the permutations iterator constructs the collection by adding the current elements of the buffer into a builder. If the builder is lazy, it will add the elements from the buffer into the collection only after the elements in the buffer get swapped around.
        Hide
        Kota Mizushima added a comment -

        Note that the fix on this issue (I wrote) was marged into master branch already:

        commit 26afbf85bf17e3839f03cb9e2d981cdccdd2ee69
        Author: Kota Mizushima <mizukota@gmail.com>
        Date: Mon Jan 16 23:20:07 2012 +0900

        Fixed a bug SI-5377 (https://issues.scala-lang.org/browse/SI-5377).

        Added test cases for SI-5377.

        Show
        Kota Mizushima added a comment - Note that the fix on this issue (I wrote) was marged into master branch already: commit 26afbf85bf17e3839f03cb9e2d981cdccdd2ee69 Author: Kota Mizushima <mizukota@gmail.com> Date: Mon Jan 16 23:20:07 2012 +0900 Fixed a bug SI-5377 ( https://issues.scala-lang.org/browse/SI-5377 ). Added test cases for SI-5377 .

          People

          • Assignee:
            Aleksandar Prokopec
            Reporter:
            Kota Mizushima
          • Votes:
            0 Vote for this issue
            Watchers:
            6 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development