Repository: jhy/jsoup
Issue: Element.clone() causes StackOverflowError when the element has excessively stacked children

This is similar to the issue I previously opened and was subsequently fixed in 1.7.2.

Excessively stacked elements contained in a parent element, such as a couple hundred `<i>` tags wrapped around some text, cause `Element.clone()` to throw a `StackOverflowError` in `Node.doClone()` 

Consider this page: http://m.gamefaqs.com/boards/577800-one-man-and-his-droid/64768563

In that page's source, you can see this:

```
<blockquote><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i><i>censor f***ing bypass</i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></i></blockquote>
```

Now clearly, something like this isn't normal. And it isn't going to happen often. But, while this page is a recreation of the issue, it did occur naturally on a different board (I don't have access to this separate board, hence why it was recreated)

This is on an Android device, where per-app stack allocation might be smaller than on a desktop or laptop.


Changed files:
src/main/java/org/jsoup/nodes/Node.java, src/test/java/org/jsoup/nodes/DocumentTest.java

diff --git a/src/main/java/org/jsoup/nodes/Node.java b/src/main/java/org/jsoup/nodes/Node.java
index f3411a75..41a13fbf 100644
--- a/src/main/java/org/jsoup/nodes/Node.java
+++ b/src/main/java/org/jsoup/nodes/Node.java
@@ -10,6 +10,7 @@ import java.net.MalformedURLException;
 import java.net.URL;
 import java.util.ArrayList;
 import java.util.Collections;
+import java.util.LinkedList;
 import java.util.List;
 
 /**
@@ -593,11 +594,32 @@ public abstract class Node implements Cloneable {
      */
     @Override
     public Node clone() {
-        return doClone(null); // splits for orphan
+        Node thisClone = doClone(null); // splits for orphan
+
+        // Queue up nodes that need their children cloned (BFS).
+        LinkedList<Node> nodesToProcess = new LinkedList<Node>();
+        nodesToProcess.add(thisClone);
+
+        while (!nodesToProcess.isEmpty()) {
+            Node currParent = nodesToProcess.remove();
+
+            for (int i = 0; i < currParent.childNodes.size(); i++) {
+                Node childClone = currParent.childNodes.get(i).doClone(currParent);
+                currParent.childNodes.set(i, childClone);
+                nodesToProcess.add(childClone);
+            }
+        }
+
+        return thisClone;
     }
 
+    /*
+     * Return a clone of the node using the given parent (which can be null).
+     * Not a deep copy of children.
+     */
     protected Node doClone(Node parent) {
         Node clone;
+
         try {
             clone = (Node) super.clone();
         } catch (CloneNotSupportedException e) {
@@ -609,8 +631,9 @@ public abstract class Node implements Cloneable {
         clone.attributes = attributes != null ? attributes.clone() : null;
         clone.baseUri = baseUri;
         clone.childNodes = new ArrayList<Node>(childNodes.size());
+
         for (Node child: childNodes)
-            clone.childNodes.add(child.doClone(clone)); // clone() creates orphans, doClone() keeps parent
+            clone.childNodes.add(child);
 
         return clone;
     }
diff --git a/src/test/java/org/jsoup/nodes/DocumentTest.java b/src/test/java/org/jsoup/nodes/DocumentTest.java
index e5b50d12..fc58b894 100644
--- a/src/test/java/org/jsoup/nodes/DocumentTest.java
+++ b/src/test/java/org/jsoup/nodes/DocumentTest.java
@@ -3,6 +3,7 @@ package org.jsoup.nodes;
 import org.jsoup.Jsoup;
 import org.jsoup.TextUtil;
 import org.junit.Test;
+import org.junit.Ignore;
 
 import static org.junit.Assert.*;
 
@@ -82,4 +83,16 @@ public class DocumentTest {
                 TextUtil.stripNewlines(clone.html()));
     }
 
+    // Ignored since this test can take awhile to run.
+    @Ignore
+    @Test public void testOverflowClone() {
+        StringBuilder builder = new StringBuilder();
+        for (int i = 0; i < 100000; i++) {
+            builder.insert(0, "<i>");
+            builder.append("</i>");
+        }
+
+        Document doc = Jsoup.parse(builder.toString());
+        doc.clone();
+    }
 }