String::append: Avoid growing list more than necessary

To visit all nodes, we should need at most depth of the rope many
entries. So far, we might however have added more nodes, as we
immediately pushed both the left and the right child. By storing a
marker together with the node, we can avoid populating the list with
both the left and right subtree at the same time.

Change-Id: Ife095c439bb20a7cf5546c31918d19869263ece1
Reviewed-by: Ulf Hermann <ulf.hermann@qt.io>
Reviewed-by: Olivier De Cannière <olivier.decanniere@qt.io>

1 files changed, 23 insertions, 8 deletions

diff --git a/src/qml/jsruntime/qv4string.cpp b/src/qml/jsruntime/qv4string.cpp
index 118382d5dc..8b5594b43b 100644
--- a/src/qml/jsruntime/qv4string.cpp
+++ b/src/qml/jsruntime/qv4string.cpp
@@ -170,23 +170,38 @@ bool Heap::String::startsWithUpper() const
 
 void Heap::String::append(const String *data, QChar *ch)
 {
-    std::vector<const String *> worklist;
+    // in-order visitation with explicit stack
+    // where leaf nodes are "real" strings that get appended to ch
+
+    enum StatusTag : bool { NotVisited, Visited };
+    using Pointer = QTaggedPointer<const String, StatusTag>;
+
+    std::vector<Pointer> worklist;
     worklist.reserve(32);
-    worklist.push_back(data);
+    worklist.push_back(Pointer(data));
 
     while (!worklist.empty()) {
-        const String *item = worklist.back();
-        worklist.pop_back();
+        Pointer item = worklist.back();
+        if (item.tag() == Visited) {
+            Q_ASSERT(item->subtype == StringType_AddedString);
+            const ComplexString *cs = static_cast<const ComplexString *>(item.data());
+            worklist.pop_back();
+            worklist.push_back(Pointer(cs->right));
+            continue;
+        }
 
         if (item->subtype == StringType_AddedString) {
-            const ComplexString *cs = static_cast<const ComplexString *>(item);
-            worklist.push_back(cs->right);
-            worklist.push_back(cs->left);
+            // we need to keep the node in the worklist, as we still need to handle "right"
+            worklist.back().setTag(Visited);
+            const ComplexString *cs = static_cast<const ComplexString *>(item.data());
+            worklist.push_back(Pointer(cs->left));
         } else if (item->subtype == StringType_SubString) {
-            const ComplexString *cs = static_cast<const ComplexString *>(item);
+            worklist.pop_back();
+            const ComplexString *cs = static_cast<const ComplexString *>(item.data());
             memcpy(ch, cs->left->toQString().constData() + cs->from, cs->len*sizeof(QChar));
             ch += cs->len;
         } else {
+            worklist.pop_back();
             memcpy(static_cast<void *>(ch), item->text().data(), item->text().size * sizeof(QChar));
             ch += item->text().size;
         }