1 files changed, 211 insertions, 70 deletions

diff --git a/src/corelib/tools/qstring.cpp b/src/corelib/tools/qstring.cpp
index bbb5647eea..07ca62145b 100644
--- a/src/corelib/tools/qstring.cpp
+++ b/src/corelib/tools/qstring.cpp
@@ -50,7 +50,6 @@
 #include "qstringmatcher.h"
 #include "qvarlengtharray.h"
 #include "qtools_p.h"
-#include "qhash.h"
 #include "qdebug.h"
 #include "qendian.h"
 #include "qcollator.h"
@@ -1828,6 +1827,51 @@ QString &QString::operator=(QChar ch)
 
 
 /*!
+    \fn QString& QString::insert(int position, const QStringRef &str)
+    \since 5.5
+    \overload insert()
+
+    Inserts the string reference \a str at the given index \a position and
+    returns a reference to this string.
+
+    If the given \a position is greater than size(), the array is
+    first extended using resize().
+*/
+
+
+/*!
+    \fn QString& QString::insert(int position, const char *str)
+    \since 5.5
+    \overload insert()
+
+    Inserts the C string \a str at the given index \a position and
+    returns a reference to this string.
+
+    If the given \a position is greater than size(), the array is
+    first extended using resize().
+
+    This function is not available when QT_NO_CAST_FROM_ASCII is
+    defined.
+*/
+
+
+/*!
+    \fn QString& QString::insert(int position, const QByteArray &str)
+    \since 5.5
+    \overload insert()
+
+    Inserts the byte array \a str at the given index \a position and
+    returns a reference to this string.
+
+    If the given \a position is greater than size(), the array is
+    first extended using resize().
+
+    This function is not available when QT_NO_CAST_FROM_ASCII is
+    defined.
+*/
+
+
+/*!
     \fn QString &QString::insert(int position, QLatin1String str)
     \overload insert()
 
@@ -2027,6 +2071,22 @@ QString &QString::append(QChar ch)
     Prepends the Latin-1 string \a str to this string.
 */
 
+/*! \fn QString &QString::prepend(const QChar *str, int len)
+    \since 5.5
+    \overload prepend()
+
+    Prepends \a len characters from the QChar array \a str to this string and
+    returns a reference to this string.
+*/
+
+/*! \fn QString &QString::prepend(const QStringRef &str)
+    \since 5.5
+    \overload prepend()
+
+    Prepends the string reference \a str to the beginning of this string and
+    returns a reference to this string.
+*/
+
 /*! \fn QString &QString::prepend(const QByteArray &ba)
 
     \overload prepend()
@@ -2659,9 +2719,9 @@ bool QString::operator<(QLatin1String other) const
     go through QObject::tr(), for example.
 */
 
-/*! \fn bool QString::operator<=(const QString &s1, const QString &s2)
+/*! \fn bool operator<=(const QString &s1, const QString &s2)
 
-    \relates Qstring
+    \relates QString
 
     Returns \c true if string \a s1 is lexically less than or equal to
     string \a s2; otherwise returns \c false.
@@ -2707,7 +2767,7 @@ bool QString::operator<(QLatin1String other) const
     go through QObject::tr(), for example.
 */
 
-/*! \fn bool QString::operator>(const QString &s1, const QString &s2)
+/*! \fn bool operator>(const QString &s1, const QString &s2)
     \relates QString
 
     Returns \c true if string \a s1 is lexically greater than string \a s2;
@@ -3939,10 +3999,9 @@ int QString::count(const QRegularExpression &re) const
 
 QString QString::section(const QString &sep, int start, int end, SectionFlags flags) const
 {
-    QStringList sections = split(sep, KeepEmptyParts,
-                                 (flags & SectionCaseInsensitiveSeps) ? Qt::CaseInsensitive : Qt::CaseSensitive);
+    const QVector<QStringRef> sections = splitRef(sep, KeepEmptyParts,
+                                                  (flags & SectionCaseInsensitiveSeps) ? Qt::CaseInsensitive : Qt::CaseSensitive);
     const int sectionsSize = sections.size();
-
     if (!(flags & SectionSkipEmpty)) {
         if (start < 0)
             start += sectionsSize;
@@ -3962,11 +4021,10 @@ QString QString::section(const QString &sep, int start, int end, SectionFlags fl
     if (start >= sectionsSize || end < 0 || start > end)
         return QString();
 
-    int x = 0;
     QString ret;
     int first_i = start, last_i = end;
-    for (int i = 0; x <= end && i < sectionsSize; ++i) {
-        QString section = sections.at(i);
+    for (int x = 0, i = 0; x <= end && i < sectionsSize; ++i) {
+        const QStringRef &section = sections.at(i);
         const bool empty = section.isEmpty();
         if (x >= start) {
             if(x == start)
@@ -3991,9 +4049,9 @@ QString QString::section(const QString &sep, int start, int end, SectionFlags fl
 class qt_section_chunk {
 public:
     qt_section_chunk() {}
-    qt_section_chunk(int l, QString s) : length(l), string(qMove(s)) {}
+    qt_section_chunk(int l, QStringRef s) : length(l), string(qMove(s)) {}
     int length;
-    QString string;
+    QStringRef string;
 };
 Q_DECLARE_TYPEINFO(qt_section_chunk, Q_MOVABLE_TYPE);
 
@@ -4086,12 +4144,12 @@ QString QString::section(const QRegExp &reg, int start, int end, SectionFlags fl
     QVector<qt_section_chunk> sections;
     int n = length(), m = 0, last_m = 0, last_len = 0;
     while ((m = sep.indexIn(*this, m)) != -1) {
-        sections.append(qt_section_chunk(last_len, QString(uc + last_m, m - last_m)));
+        sections.append(qt_section_chunk(last_len, QStringRef(this, last_m, m - last_m)));
         last_m = m;
         last_len = sep.matchedLength();
         m += qMax(sep.matchedLength(), 1);
     }
-    sections.append(qt_section_chunk(last_len, QString(uc + last_m, n - last_m)));
+    sections.append(qt_section_chunk(last_len, QStringRef(this, last_m, n - last_m)));
 
     return extractSections(sections, start, end, flags);
 }
@@ -4134,11 +4192,11 @@ QString QString::section(const QRegularExpression &re, int start, int end, Secti
     while (iterator.hasNext()) {
         QRegularExpressionMatch match = iterator.next();
         m = match.capturedStart();
-        sections.append(qt_section_chunk(last_len, QString(uc + last_m, m - last_m)));
+        sections.append(qt_section_chunk(last_len, QStringRef(this, last_m, m - last_m)));
         last_m = m;
         last_len = match.capturedLength();
     }
-    sections.append(qt_section_chunk(last_len, QString(uc + last_m, n - last_m)));
+    sections.append(qt_section_chunk(last_len, QStringRef(this, last_m, n - last_m)));
 
     return extractSections(sections, start, end, flags);
 }
@@ -4822,7 +4880,7 @@ modifiable reference.
 
     If \a position is negative, it is equivalent to passing zero.
 
-    \sa chop(), resize(), left()
+    \sa chop(), resize(), left(), QStringRef::truncate()
 */
 
 void QString::truncate(int pos)
@@ -7622,86 +7680,155 @@ static int getEscape(const QChar *uc, int *pos, int len, int maxNumber = 999)
     return -1;
 }
 
+/*
+    Algorithm for multiArg:
+
+    1. Parse the string as a sequence of verbatim text and placeholders (%L?\d{,3}).
+       The L is parsed and accepted for compatibility with non-multi-arg, but since
+       multiArg only accepts strings as replacements, the localization request can
+       be safely ignored.
+    2. The result of step (1) is a list of (string-ref,int)-tuples. The string-ref
+       either points at text to be copied verbatim (in which case the int is -1),
+       or, initially, at the textual representation of the placeholder. In that case,
+       the int contains the numerical number as parsed from the placeholder.
+    3. Next, collect all the non-negative ints found, sort them in ascending order and
+       remove duplicates.
+       3a. If the result has more entires than multiArg() was given replacement strings,
+           we have found placeholders we can't satisfy with replacement strings. That is
+           fine (there could be another .arg() call coming after this one), so just
+           truncate the result to the number of actual multiArg() replacement strings.
+       3b. If the result has less entries than multiArg() was given replacement strings,
+           the string is missing placeholders. This is an error that the user should be
+           warned about.
+    4. The result of step (3) is a mapping from the index of any replacement string to
+       placeholder number. This is the wrong way around, but since placeholder
+       numbers could get as large as 999, while we typically don't have more than 9
+       replacement strings, we trade 4K of sparsely-used memory for doing a reverse lookup
+       each time we need to map a placeholder number to a replacement string index
+       (that's a linear search; but still *much* faster than using an associative container).
+    5. Next, for each of the tuples found in step (1), do the following:
+       5a. If the int is negative, do nothing.
+       5b. Otherwise, if the int is found in the result of step (3) at index I, replace
+           the string-ref with a string-ref for the (complete) I'th replacement string.
+       5c. Otherwise, do nothing.
+    6. Concatenate all string refs into a single result string.
+*/
+
 namespace {
-class ArgMapper {
-    QVarLengthArray<int, 16> argPosToNumberMap; // maps from argument position to number
-public:
-    void found(int n) { argPosToNumberMap.push_back(n); }
+struct Part
+{
+    Part() : stringRef(), number(0) {}
+    Part(const QString &s, int pos, int len, int num = -1) Q_DECL_NOTHROW
+        : stringRef(&s, pos, len), number(num) {}
 
-    struct AssignmentResult {
-        int numArgs;
-        int lastNumber;
-    };
+    QStringRef stringRef;
+    int number;
+};
+} // unnamed namespace
 
-    AssignmentResult assignArgumentNumberToEachOfTheNs(int numArgs)
-    {
-        std::sort(argPosToNumberMap.begin(), argPosToNumberMap.end());
-        argPosToNumberMap.erase(std::unique(argPosToNumberMap.begin(), argPosToNumberMap.end()),
-                                argPosToNumberMap.end());
+template <>
+class QTypeInfo<Part> : public QTypeInfoMerger<Part, QStringRef, int> {}; // Q_DECLARE_METATYPE
 
-        if (argPosToNumberMap.size() > numArgs)
-            argPosToNumberMap.resize(numArgs);
 
-        int lastNumber = argPosToNumberMap.empty() ? -1 : argPosToNumberMap.back();
-        int arg = argPosToNumberMap.size();
+namespace {
 
-        const AssignmentResult result = {arg, lastNumber};
-        return result;
-    }
+enum { ExpectedParts = 32 };
 
-    int numberToArgsIndex(int number) const
-    {
-        if (number != -1) {
-            const int * const it = std::find(argPosToNumberMap.begin(), argPosToNumberMap.end(), number);
-            return it == argPosToNumberMap.end() ? -1 : it - argPosToNumberMap.begin();
-        } else {
-            return -1;
-        }
-    }
-};
-} // unnamed namespace
+typedef QVarLengthArray<Part, ExpectedParts> ParseResult;
+typedef QVarLengthArray<int, ExpectedParts/2> ArgIndexToPlaceholderMap;
 
-QString QString::multiArg(int numArgs, const QString **args) const
+static ParseResult parseMultiArgFormatString(const QString &s)
 {
-    QString result;
-    ArgMapper mapper;
-    const QChar *uc = (const QChar *) d->data();
-    const int len = d->size;
+    ParseResult result;
+
+    const QChar *uc = s.constData();
+    const int len = s.size();
     const int end = len - 1;
     int i = 0;
+    int last = 0;
 
-    // populate the arg-mapper with the %n's that actually occur in the string
     while (i < end) {
         if (uc[i] == QLatin1Char('%')) {
+            int percent = i;
             int number = getEscape(uc, &i, len);
             if (number != -1) {
-                mapper.found(number);
+                if (last != percent)
+                    result.push_back(Part(s, last, percent - last)); // literal text (incl. failed placeholders)
+                result.push_back(Part(s, percent, i - percent, number));  // parsed placeholder
+                last = i;
                 continue;
             }
         }
         ++i;
     }
 
-    const ArgMapper::AssignmentResult r = mapper.assignArgumentNumberToEachOfTheNs(numArgs);
+    if (last < len)
+        result.push_back(Part(s, last, len - last)); // trailing literal text
 
-    // sanity
-    if (numArgs > r.numArgs) {
-        qWarning("QString::arg: %d argument(s) missing in %s", numArgs - r.numArgs, toLocal8Bit().data());
-        numArgs = r.numArgs;
+    return result;
+}
+
+static ArgIndexToPlaceholderMap makeArgIndexToPlaceholderMap(const ParseResult &parts)
+{
+    ArgIndexToPlaceholderMap result;
+
+    for (ParseResult::const_iterator it = parts.begin(), end = parts.end(); it != end; ++it) {
+        if (it->number >= 0)
+            result.push_back(it->number);
     }
 
-    i = 0;
-    while (i < len) {
-        if (uc[i] == QLatin1Char('%') && i != end) {
-            int number = getEscape(uc, &i, len, r.lastNumber);
-            int arg = mapper.numberToArgsIndex(number);
-            if (number != -1 && arg != -1) {
-                result += *args[arg];
-                continue;
-            }
+    std::sort(result.begin(), result.end());
+    result.erase(std::unique(result.begin(), result.end()),
+                 result.end());
+
+    return result;
+}
+
+static int resolveStringRefsAndReturnTotalSize(ParseResult &parts, const ArgIndexToPlaceholderMap &argIndexToPlaceholderMap, const QString *args[])
+{
+    int totalSize = 0;
+    for (ParseResult::iterator pit = parts.begin(), end = parts.end(); pit != end; ++pit) {
+        if (pit->number != -1) {
+            const ArgIndexToPlaceholderMap::const_iterator ait
+                    = std::find(argIndexToPlaceholderMap.begin(), argIndexToPlaceholderMap.end(), pit->number);
+            if (ait != argIndexToPlaceholderMap.end())
+                pit->stringRef = QStringRef(args[ait - argIndexToPlaceholderMap.begin()]);
         }
-        result += uc[i++];
+        totalSize += pit->stringRef.size();
     }
+    return totalSize;
+}
+
+} // unnamed namespace
+
+QString QString::multiArg(int numArgs, const QString **args) const
+{
+    // Step 1-2 above
+    ParseResult parts = parseMultiArgFormatString(*this);
+
+    // 3-4
+    ArgIndexToPlaceholderMap argIndexToPlaceholderMap = makeArgIndexToPlaceholderMap(parts);
+
+    if (argIndexToPlaceholderMap.size() > numArgs) // 3a
+        argIndexToPlaceholderMap.resize(numArgs);
+    else if (argIndexToPlaceholderMap.size() < numArgs) // 3b
+        qWarning("QString::arg: %d argument(s) missing in %s",
+                 numArgs - argIndexToPlaceholderMap.size(), toLocal8Bit().data());
+
+    // 5
+    const int totalSize = resolveStringRefsAndReturnTotalSize(parts, argIndexToPlaceholderMap, args);
+
+    // 6:
+    QString result(totalSize, Qt::Uninitialized);
+    QChar *out = result.data();
+
+    for (ParseResult::const_iterator it = parts.begin(), end = parts.end(); it != end; ++it) {
+        if (const int sz = it->stringRef.size()) {
+            memcpy(out, it->stringRef.constData(), sz * sizeof(QChar));
+            out += sz;
+        }
+    }
+
     return result;
 }
 
@@ -9268,6 +9395,20 @@ QStringRef QString::midRef(int position, int n) const
 }
 
 /*!
+    \fn void QStringRef::truncate(int position)
+    \since 5.6
+
+    Truncates the string at the given \a position index.
+
+    If the specified \a position index is beyond the end of the
+    string, nothing happens.
+
+    If \a position is negative, it is equivalent to passing zero.
+
+    \sa QString::truncate()
+*/
+
+/*!
   \since 4.8
 
   Returns the index position of the first occurrence of the string \a