List.foldRight throws StackOverflowError

[scabug]

List.foldRight is not tail recursive, so it throws StackOverflowError when called on a large list.

Example:

scala> (List.range(1, 1000000) :\ 0) (_ + _)
java.lang.StackOverflowError
        at scala.List.foldRight(List.scala:1079)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRig...
scala>

In fact, 10000 is enough on my system.

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-2818?orig=1
Reporter: NagMacFeegle (nagmacfeegle)
Assignee: @JamesIry

[scabug]

@hubertp said:
In r20248 I get something similar:

scala> (List.range(1, 1000000) :\ 0) (_ + _)
java.lang.StackOverflowError
	at scala.collection.LinearSeqLike$$class.foldRight(LinearSeqLike.scala:167)
	at scala.collection.immutable.List.foldRight(List.scala:46)
	at scala.collection.LinearSeqLike$$class.foldRight(LinearSeqLike.scala:168)
	at scala.collection.immutable.List.foldRight(List.scala:46)
	at scala.collection.LinearSeqLike$$class.foldRight(LinearSeqLike.scala:168)
	at scala.collection.immutable.List.foldRight(List.scala:46)
	at scala.collection.LinearSeqLike$$class.foldRight(LinearSeqLike.scala:168)
	at scala.collection.immutable.List.foldRight(List.scala:46)
	at scala.collection.LinearSeqLike$$class.foldRight(LinearSeqLike.scala:168)
	at scala.collection.immutable.List.foldRight(List.scala:46)
	at scala.collection.LinearSeqLike$$class.foldRight(LinearSeqLike.scala:168)
	at scala.collection.immutable.List.foldRight(List.scala:46)
	at scala.collection.LinearSeqLike$$class.foldRight(LinearSeqLike.scala:168)

[scabug]

@hubertp said:
This might be related to #1437

[scabug]

@lrytz said:
there is no straight-forward tail-recursive implementation.

[scabug]

johnconnor said:
May I suggest the following implementation: We perform the usual stack unrolling up to a point and if we reach a certain stack depth (STACK_DEPTH_LIMIT), we reverse the list (whatever is left of it) and appeal to the tail recursive foldLeft for assistance -- the stack is then unrolled and we have our answer.

def foldRight[B](z: B)(f: (A, B) => B): B = {
    val STACK_DEPTH_LIMIT = 100

    def revArgs[A1, A2, C](f: (A1, A2) => C): ((A2, A1) => C) =
      (x: A2, y: A1) => f (y, x)

    def aux(iterCnt: Int, ls: Lst[A]): B = ls match {
      case Nil => z
      case x :: xs => {
        if (iterCnt < STACK_DEPTH_LIMIT) {
          f(x, aux(iterCnt + 1, xs))
        }
        else {
          val revRest = ls reverse
          val g = revArgs(f)

          revRest.foldLeft(z)(g)
        }
      }
    }

    aux(0, this)
  }

[scabug]

NagMacFeegle (nagmacfeegle) said:
It really does not look very elegantly but I have not found a better solution.

The STACK_DEPTH_LIMIT should not be too big, because you never know where you are in the stack, but 100 seems reasonable.

Since List#reverse is linear in list size, as is foldLeft, it would probably make the implementation more elegant if "reverse" would always be used and the "small list" case would not be considered, without making it unreasonably slower.

[scabug]

@odersky said:
I think it would overcomplicate things too much. Let's leave it as it is.

[scabug]

Sean Parsons (seanparsons) said:
Following on from the discussion that has occurred here: https://groups.google.com/forum/#!topic/scala-internals/RrmfYQpTTfc/discussion

It seems sensible that List.foldRight can be implemented simply at virtually no penalty to performance (caliper based benchmarks linked in the discussion above) in the smaller cases if implemented as follows:

  override def foldRight[B](z: B)(op: (A, B) => B): B = {
    if (lengthCompare(10) < 0)  // MAX_DEPTH=10
      super.foldRight(z)(op)
    else
      reverse.foldLeft(z)((right, left) => op(left, right))
  }

This mitigates the case where a callee unwittingly does a foldRight on a type with the signature of Seq[User] for example which is actually a List.

[scabug]

Sean Parsons (seanparsons) said:
The above implementation is an adapted version of foldAlternative4 from the scala-internals discussion, with the adapted version tested minimally against the 2.10.x branch with a 20,000 item List.

[scabug]

@Blaisorblade said:
Sean, I've marked this ticket as due for 2.10.1-RC1 to hopefully get new attention to it. But I'd recommend to submit a pull request, it seems this time it's going to be accepted. But you (somebody) needs to:

• add some test case (you have a minimal one, if that fails now that's good)
• possibly, check other variations of the same bug (like reduceRight). And what about LinearSeqOptimized.fold/reduceRight? I see your point on not touching Stream, but LinearSeqOptimized is implemented by other classes, so it should also be addressed.
  If some broken use cases are left, please comment on foldRight should be documented to be unusable on long lists (if it's not fixed) #6922 so that they're documented.

[scabug]

@adriaanm said:
without further activity on this ticket this week, I'm afraid it'll have to slip to 2.10.2

[scabug]

@JamesIry said:
scala/scala#2026

[scabug]

@SethTisue said:
there is further discussion in #3295

[scabug]

@Blaisorblade said:
I just marked #3295 as duplicate :-).