Split up String type into a regular and a ComplexString

Saves some memory for many cases, and will allow re-using the
String itself as an identifier

Change-Id: I462d63bc6f113dff1dce0de28ee4eea3949a4b95
Reviewed-by: Simon Hausmann <simon.hausmann@qt.io>

4 files changed, 73 insertions, 61 deletions

diff --git a/src/qml/jsruntime/qv4runtime.cpp b/src/qml/jsruntime/qv4runtime.cpp
index 93d538127b..e7a104af66 100644
--- a/src/qml/jsruntime/qv4runtime.cpp
+++ b/src/qml/jsruntime/qv4runtime.cpp
@@ -532,7 +532,7 @@ QV4::ReturnedValue RuntimeHelpers::addHelper(ExecutionEngine *engine, const Valu
         if (!sright->d()->length())
             return sleft->asReturnedValue();
         MemoryManager *mm = engine->memoryManager;
-        return (mm->alloc<String>(sleft->d(), sright->d()))->asReturnedValue();
+        return (mm->alloc<ComplexString>(sleft->d(), sright->d()))->asReturnedValue();
     }
     double x = RuntimeHelpers::toNumber(pleft);
     double y = RuntimeHelpers::toNumber(pright);
diff --git a/src/qml/jsruntime/qv4string.cpp b/src/qml/jsruntime/qv4string.cpp
index b38b01c9f7..bdfb8af3f6 100644
--- a/src/qml/jsruntime/qv4string.cpp
+++ b/src/qml/jsruntime/qv4string.cpp
@@ -55,10 +55,12 @@ using namespace QV4;
 void Heap::String::markObjects(Heap::Base *that, MarkStack *markStack)
 {
     String *s = static_cast<String *>(that);
-    if (s->largestSubLength) {
-        s->left->mark(markStack);
-        s->right->mark(markStack);
-    }
+    if (s->subtype < StringType_Complex)
+        return;
+
+    ComplexString *cs = static_cast<ComplexString *>(s);
+    cs->left->mark(markStack);
+    cs->right->mark(markStack);
 }
 
 DEFINE_MANAGED_VTABLE(String);
@@ -84,29 +86,25 @@ void Heap::String::init(const QString &t)
 
     text = const_cast<QString &>(t).data_ptr();
     text->ref.ref();
-    identifier = 0;
-    stringHash = UINT_MAX;
-    largestSubLength = 0;
-    len = text->size;
 }
 
-void Heap::String::init(String *l, String *r)
+void Heap::ComplexString::init(String *l, String *r)
 {
     Base::init();
 
-    subtype = String::StringType_Unknown;
+    subtype = String::StringType_AddedString;
 
     left = l;
     right = r;
-    stringHash = UINT_MAX;
-    largestSubLength = qMax(l->largestSubLength, r->largestSubLength);
-    len = l->len + r->len;
-    Q_ASSERT(largestSubLength <= len);
-
-    if (!l->largestSubLength && l->len > largestSubLength)
-        largestSubLength = l->len;
-    if (!r->largestSubLength && r->len > largestSubLength)
-        largestSubLength = r->len;
+    len = left->length() + right->length();
+    if (left->subtype >= StringType_Complex)
+        largestSubLength = static_cast<ComplexString *>(left)->largestSubLength;
+    else
+        largestSubLength = left->length();
+    if (right->subtype >= StringType_Complex)
+        largestSubLength = qMax(largestSubLength, static_cast<ComplexString *>(right)->largestSubLength);
+    else
+        largestSubLength = qMax(largestSubLength, right->length());
 
     // make sure we don't get excessive depth in our strings
     if (len > 256 && len >= 2*largestSubLength)
@@ -114,7 +112,7 @@ void Heap::String::init(String *l, String *r)
 }
 
 void Heap::String::destroy() {
-    if (!largestSubLength) {
+    if (text) {
         internalClass->engine->memoryManager->changeUnmanagedHeapSizeUsage(qptrdiff(-text->size) * (int)sizeof(QChar));
         if (!text->ref.deref())
             QStringData::deallocate(text);
@@ -142,15 +140,15 @@ uint String::toUInt(bool *ok) const
 
 void String::makeIdentifierImpl() const
 {
-    if (d()->largestSubLength)
+    if (!d()->text)
         d()->simplifyString();
-    Q_ASSERT(!d()->largestSubLength);
+    Q_ASSERT(d()->text);
     engine()->identifierTable->identifier(this);
 }
 
 void Heap::String::simplifyString() const
 {
-    Q_ASSERT(largestSubLength);
+    Q_ASSERT(!text);
 
     int l = length();
     QString result(l, Qt::Uninitialized);
@@ -159,8 +157,8 @@ void Heap::String::simplifyString() const
     text = result.data_ptr();
     text->ref.ref();
     identifier = 0;
-    largestSubLength = 0;
     internalClass->engine->memoryManager->changeUnmanagedHeapSizeUsage(qptrdiff(text->size) * (qptrdiff)sizeof(QChar));
+    subtype = StringType_Unknown;
 }
 
 void Heap::String::append(const String *data, QChar *ch)
@@ -173,9 +171,10 @@ void Heap::String::append(const String *data, QChar *ch)
         const String *item = worklist.back();
         worklist.pop_back();
 
-        if (item->largestSubLength) {
-            worklist.push_back(item->right);
-            worklist.push_back(item->left);
+        if (item->subtype >= StringType_Complex) {
+            const ComplexString *cs = static_cast<const ComplexString *>(item);
+            worklist.push_back(cs->right);
+            worklist.push_back(cs->left);
         } else {
             memcpy(ch, item->text->data(), item->text->size * sizeof(QChar));
             ch += item->text->size;
@@ -185,9 +184,9 @@ void Heap::String::append(const String *data, QChar *ch)
 
 void Heap::String::createHashValue() const
 {
-    if (largestSubLength)
+    if (!text)
         simplifyString();
-    Q_ASSERT(!largestSubLength);
+    Q_ASSERT(text);
     const QChar *ch = reinterpret_cast<const QChar *>(text->data());
     const QChar *end = ch + text->size;
     stringHash = QV4::String::calculateHashValue(ch, end, &subtype);
diff --git a/src/qml/jsruntime/qv4string_p.h b/src/qml/jsruntime/qv4string_p.h
index 1acdbf3e4b..d1b38f4336 100644
--- a/src/qml/jsruntime/qv4string_p.h
+++ b/src/qml/jsruntime/qv4string_p.h
@@ -67,35 +67,31 @@ namespace Heap {
 struct Q_QML_PRIVATE_EXPORT String : Base {
     static void markObjects(Heap::Base *that, MarkStack *markStack);
     enum StringType {
-        StringType_Unknown,
         StringType_Regular,
-        StringType_ArrayIndex
+        StringType_ArrayIndex,
+        StringType_Unknown,
+        StringType_AddedString,
+        StringType_Complex = StringType_AddedString
     };
 
 #ifndef V4_BOOTSTRAP
     void init(const QString &text);
-    void init(String *l, String *n);
     void destroy();
     void simplifyString() const;
-    int length() const {
-        Q_ASSERT((largestSubLength &&
-                  (len == left->len + right->len)) ||
-                 len == (uint)text->size);
-        return len;
-    }
+    int length() const;
     std::size_t retainedTextSize() const {
-        return largestSubLength ? 0 : (std::size_t(text->size) * sizeof(QChar));
+        return subtype >= StringType_Complex ? 0 : (std::size_t(text->size) * sizeof(QChar));
     }
     void createHashValue() const;
     inline unsigned hashValue() const {
-        if (subtype == StringType_Unknown)
+        if (subtype >= StringType_Unknown)
             createHashValue();
-        Q_ASSERT(!largestSubLength);
+        Q_ASSERT(subtype < StringType_Complex);
 
         return stringHash;
     }
     inline QString toQString() const {
-        if (largestSubLength)
+        if (subtype >= StringType_Complex)
             simplifyString();
         QStringDataPtr ptr = { text };
         text->ref.ref();
@@ -106,7 +102,7 @@ struct Q_QML_PRIVATE_EXPORT String : Base {
             return true;
         if (hashValue() != other->hashValue())
             return false;
-        Q_ASSERT(!largestSubLength);
+        Q_ASSERT(subtype < StringType_Complex);
         if (identifier && identifier == other->identifier)
             return true;
         if (subtype == Heap::String::StringType_ArrayIndex && other->subtype == Heap::String::StringType_ArrayIndex)
@@ -115,24 +111,33 @@ struct Q_QML_PRIVATE_EXPORT String : Base {
         return toQString() == other->toQString();
     }
 
-    union {
-        mutable QStringData *text;
-        mutable String *left;
-    };
-    union {
-        mutable Identifier *identifier;
-        mutable String *right;
-    };
+    mutable QStringData *text;
+    mutable Identifier *identifier;
     mutable uint subtype;
     mutable uint stringHash;
-    mutable uint largestSubLength;
-    uint len;
 private:
     static void append(const String *data, QChar *ch);
 #endif
 };
 Q_STATIC_ASSERT(std::is_trivial< String >::value);
 
+#ifndef V4_BOOTSTRAP
+struct ComplexString : String {
+    void init(String *l, String *n);
+    mutable uint nestingLevel;
+    mutable String *left;
+    mutable String *right;
+    mutable int largestSubLength;
+    int len;
+};
+Q_STATIC_ASSERT(std::is_trivial< ComplexString >::value);
+
+inline
+int String::length() const {
+    return text ? text->size : static_cast<const ComplexString *>(this)->len;
+}
+#endif
+
 }
 
 struct Q_QML_PRIVATE_EXPORT String : public Managed {
@@ -169,7 +174,7 @@ struct Q_QML_PRIVATE_EXPORT String : public Managed {
     uint asArrayIndex() const {
         if (subtype() == Heap::String::StringType_Unknown)
             d()->createHashValue();
-        Q_ASSERT(!d()->largestSubLength);
+        Q_ASSERT(d()->subtype < Heap::String::StringType_Complex);
         if (subtype() == Heap::String::StringType_ArrayIndex)
             return d()->stringHash;
         return UINT_MAX;
@@ -198,10 +203,8 @@ struct Q_QML_PRIVATE_EXPORT String : public Managed {
     }
 
     bool startsWithUpper() const {
-        const String::Data *l = d();
-        while (l->largestSubLength)
-            l = l->left;
-        return l->text->size && QChar::isUpper(l->text->data()[0]);
+        Q_ASSERT(d()->subtype < Heap::String::StringType_Complex);
+        return d()->text->size && QChar::isUpper(d()->text->data()[0]);
     }
 
     Identifier *identifier() const { return d()->identifier; }
@@ -263,12 +266,22 @@ public:
     }
 };
 
+#ifndef V4_BOOTSTRAP
+struct ComplexString : String {
+    typedef QV4::Heap::ComplexString Data;
+    QV4::Heap::ComplexString *d_unchecked() const { return static_cast<QV4::Heap::ComplexString *>(m()); }
+    QV4::Heap::ComplexString *d() const {
+        QV4::Heap::ComplexString *dptr = d_unchecked();
+        dptr->_checkIsInitialized();
+        return dptr;
+    }
+};
+
 template<>
 inline const String *Value::as() const {
     return isManaged() && m()->vtable()->isString ? static_cast<const String *>(this) : 0;
 }
 
-#ifndef V4_BOOTSTRAP
 template<>
 inline ReturnedValue value_convert<String>(ExecutionEngine *e, const Value &v)
 {
diff --git a/src/qml/jsruntime/qv4stringobject.cpp b/src/qml/jsruntime/qv4stringobject.cpp
index efab51ec53..b4c50170cf 100644
--- a/src/qml/jsruntime/qv4stringobject.cpp
+++ b/src/qml/jsruntime/qv4stringobject.cpp
@@ -92,7 +92,7 @@ Heap::String *Heap::StringObject::getIndex(uint index) const
 
 uint Heap::StringObject::length() const
 {
-    return string->len;
+    return string->length();
 }
 
 bool StringObject::deleteIndexedProperty(Managed *m, uint index)