Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Appending a ListBuffer to itself causes endless loop #3088

Closed
scabug opened this issue Feb 22, 2010 · 8 comments · Fixed by scala/scala#9174
Closed

Appending a ListBuffer to itself causes endless loop #3088

scabug opened this issue Feb 22, 2010 · 8 comments · Fixed by scala/scala#9174

Comments

@scabug
Copy link

scabug commented Feb 22, 2010

scala> val b = new ListBuffer[Int]
scala> b += 1
scala> b ++= b
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at java.util.Arrays.copyOf(Arrays.java:2882)
	at java.lang.AbstractStringBuilder.expandCapacity(AbstractStringBuilder.java:100)
	at java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:390)

If LB doesn't support self-append, then it should throw IllegalArgumentException if passed an instance of itself. But maybe a better fix would be to look at the number of elements in the LB at the start of the append, and just append that many.

The easy "fix" is to add something to the Javadoc or assume that users will be able to diagnose the OutOfMemoryError that results, but the self-append may not be so obvious as the one in this example and could lead to a OutOfMemoryError in a production system, potentially taking the whole system down instead of just one thread. Imagine if this happened on a web server. If ListBuffer threw IllegalArgumentException, then just the one request would fail. If it instead allocates all the available memory, then it will grind the CPU for a while, slowing down everything else, and potentially cause other requests that need memory to fail too.

I think that the same issue probably affects the prepend operations.

@scabug
Copy link
Author

scabug commented Feb 22, 2010

Imported From: https://issues.scala-lang.org/browse/SI-3088?orig=1
Reporter: Willis Blackburn (willisblackburn)

@scabug
Copy link
Author

scabug commented Feb 24, 2010

@axel22 said:
(In r20977) Fixes #3088. No review.

@scabug
Copy link
Author

scabug commented Feb 25, 2010

@axel22 said:
(In r20986) Fixes #3088. No review.

@scabug
Copy link
Author

scabug commented Mar 19, 2010

@paulp said:
Reopening because ++=(Iterator) still loops. I have a fix for this implemented but am awaiting martin's opinion (see my email to scala-internals.)

@scabug
Copy link
Author

scabug commented Sep 15, 2010

@paulp said:
In r22946 martin got the lb ++= lb case, and it looks like I'll have to live with lb ++= lb.iterator case looping for now. I'm enclosing my proposed implementation for the record and closing this as fixed.
{code}
override def iterator = new Iterator[A] {
private var elementsRemaining = size
private var cursor: List[A] = null

def hasNext: Boolean = !start.isEmpty && (cursor ne last0) && (elementsRemaining > 0)
def next(): A =
if (!hasNext) throw new NoSuchElementException("next on empty Iterator")
else {
elementsRemaining -= 1
cursor = if (cursor eq null) start else cursor.tail
cursor.head
}
}

@scabug
Copy link
Author

scabug commented Sep 15, 2010

@paulp said:
(In r23001) Test for already closed #3088. No review.

[Editorial correction: r23000 was submitted by Johannes Rudolph
and my name inadvertently replaced his in the windy path from git
to svn. The comments and code are his. Posterity, take note!]

@NthPortal
Copy link

NthPortal commented Aug 18, 2020

anyone know where the fix for this is? I can't find it

@NthPortal
Copy link

NthPortal commented Aug 18, 2020

update: it actually re-emerged at some point during or before 2.13. it just so happens that the test only checks when the ListBuffer has a single element, which happens to work because the iterator exhausts itself before returning. with more elements, it hangs

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants