qstring.cpp

Go to the documentation of this file.

/****************************************************************************
**
** Copyright (C) 2021 The Qt Company Ltd.
** Copyright (C) 2022 Intel Corporation.
** Copyright (C) 2019 Mail.ru Group.
** Contact: https://www.qt.io/licensing/
**
** This file is part of the QtCore module of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL$
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and The Qt Company. For licensing terms
** and conditions see https://www.qt.io/terms-conditions. For further
** information use the contact form at https://www.qt.io/contact-us.
**
** GNU Lesser General Public License Usage
** Alternatively, this file may be used under the terms of the GNU Lesser
** General Public License version 3 as published by the Free Software
** Foundation and appearing in the file LICENSE.LGPL3 included in the
** packaging of this file. Please review the following information to
** ensure the GNU Lesser General Public License version 3 requirements
** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 2.0 or (at your option) the GNU General
** Public license version 3 or any later version approved by the KDE Free
** Qt Foundation. The licenses are as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
** included in the packaging of this file. Please review the following
** information to ensure the GNU General Public License requirements will
** be met: https://www.gnu.org/licenses/gpl-2.0.html and
** https://www.gnu.org/licenses/gpl-3.0.html.
**
** $QT_END_LICENSE$
**
****************************************************************************/
 
#include "qstringlist.h"
#if QT_CONFIG(regularexpression)
#include "qregularexpression.h"
#endif
#include "qunicodetables_p.h"
#include <private/qstringconverter_p.h>
#include "qlocale_tools_p.h"
#include "private/qsimd_p.h"
#include <qnumeric.h>
#include <qdatastream.h>
#include <qlist.h>
#include "qlocale.h"
#include "qlocale_p.h"
#include "qstringbuilder.h"
#include "qstringmatcher.h"
#include "qvarlengtharray.h"
#include "qdebug.h"
#include "qendian.h"
#include "qcollator.h"
 
#ifdef Q_OS_MAC
#include <private/qcore_mac_p.h>
#endif
 
#include <private/qfunctions_p.h>
 
#include <limits.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#include <wchar.h>
 
#include "qchar.cpp"
#include "qstringmatcher.cpp"
#include "qstringiterator_p.h"
#include "qstringalgorithms_p.h"
#include "qthreadstorage.h"
 
#include "qbytearraymatcher.h" // Helper for comparison of QLatin1String
 
#include <algorithm>
#include <functional>
 
#ifdef Q_OS_WIN
#  include <qt_windows.h>
#endif
 
#ifdef truncate
#  undef truncate
#endif
 
#ifndef LLONG_MAX
#define LLONG_MAX qint64_C(9223372036854775807)
#endif
#ifndef LLONG_MIN
#define LLONG_MIN (-LLONG_MAX - qint64_C(1))
#endif
#ifndef ULLONG_MAX
#define ULLONG_MAX quint64_C(18446744073709551615)
#endif
 
#define IS_RAW_DATA(d) ((d.d)->flags & QArrayData::RawDataType)
#define REHASH(a) \
    if (sl_minus_1 < sizeof(std::size_t) * CHAR_BIT)  \
        hashHaystack -= std::size_t(a) << sl_minus_1; \
    hashHaystack <<= 1
 
QT_BEGIN_NAMESPACE
 
const char16_t QString::_empty = 0;
 
// in qstringmatcher.cpp
qsizetype qFindStringBoyerMoore(QStringView haystack, qsizetype from, QStringView needle, Qt::CaseSensitivity cs);
 
namespace {
inline bool qIsUpper(char ch)
{
    return ch >= 'A' && ch <= 'Z';
}
 
inline bool qIsDigit(char ch)
{
    return ch >= '0' && ch <= '9';
}
 
inline char qToLower(char ch)
{
    if (ch >= 'A' && ch <= 'Z')
        return ch - 'A' + 'a';
    else
        return ch;
}
template <typename Pointer>
char32_t foldCaseHelper(Pointer ch, Pointer start) = delete;
 
template <>
char32_t foldCaseHelper<const QChar*>(const QChar* ch, const QChar* start)
{
    return foldCase(reinterpret_cast<const char16_t*>(ch),
                    reinterpret_cast<const char16_t*>(start));
}
 
template <>
char32_t foldCaseHelper<const char*>(const char* ch, const char*)
{
    return foldCase(char16_t(uchar(*ch)));
}
 
template <typename T>
char16_t valueTypeToUtf16(T t) = delete;
 
template <>
char16_t valueTypeToUtf16<QChar>(QChar t)
{
    return t.unicode();
}
 
template <>
char16_t valueTypeToUtf16<char>(char t)
{
    return char16_t{uchar(t)};
}
 
static inline qsizetype qFindChar(QStringView str, QChar ch, qsizetype from, Qt::CaseSensitivity cs) noexcept
{
    if (-from > str.size())
        return -1;
    if (from < 0)
        from = qMax(from + str.size(), qsizetype(0));
    if (from < str.size()) {
        const char16_t *s = str.utf16();
        char16_t c = ch.unicode();
        const char16_t *n = s + from;
        const char16_t *e = s + str.size();
        if (cs == Qt::CaseSensitive) {
            n = QtPrivate::qustrchr(QStringView(n, e), c);
            if (n != e)
                return n - s;
        } else {
            c = foldCase(c);
            --n;
            while (++n != e)
                if (foldCase(*n) == c)
                    return n - s;
        }
    }
    return -1;
}
 
template <typename Haystack>
static inline qsizetype qLastIndexOf(Haystack haystack, QChar needle,
                                     qsizetype from, Qt::CaseSensitivity cs) noexcept
{
    if (haystack.size() == 0)
        return -1;
    if (from < 0)
        from += haystack.size();
    else if (std::size_t(from) > std::size_t(haystack.size()))
        from = haystack.size() - 1;
    if (from >= 0) {
        char16_t c = needle.unicode();
        const auto b = haystack.data();
        auto n = b + from;
        if (cs == Qt::CaseSensitive) {
            for (; n >= b; --n)
                if (valueTypeToUtf16(*n) == c)
                    return n - b;
        } else {
            c = foldCase(c);
            for (; n >= b; --n)
                if (foldCase(valueTypeToUtf16(*n)) == c)
                    return n - b;
        }
    }
    return -1;
}
template <> qsizetype
qLastIndexOf(QString, QChar, qsizetype, Qt::CaseSensitivity) noexcept = delete; // unwanted, would detach
 
template<typename Haystack, typename Needle>
static qsizetype qLastIndexOf(Haystack haystack0, qsizetype from,
                              Needle needle0, Qt::CaseSensitivity cs) noexcept
{
    const qsizetype sl = needle0.size();
    if (sl == 1)
        return qLastIndexOf(haystack0, needle0.front(), from, cs);
 
    const qsizetype l = haystack0.size();
    if (from < 0)
        from += l;
    if (from == l && sl == 0)
        return from;
    const qsizetype delta = l - sl;
    if (std::size_t(from) > std::size_t(l) || delta < 0)
        return -1;
    if (from > delta)
        from = delta;
 
    auto sv = [sl](const typename Haystack::value_type *v) { return Haystack(v, sl); };
 
    auto haystack = haystack0.data();
    const auto needle = needle0.data();
    const auto *end = haystack;
    haystack += from;
    const std::size_t sl_minus_1 = sl ? sl - 1 : 0;
    const auto *n = needle + sl_minus_1;
    const auto *h = haystack + sl_minus_1;
    std::size_t hashNeedle = 0, hashHaystack = 0;
 
    if (cs == Qt::CaseSensitive) {
        for (qsizetype idx = 0; idx < sl; ++idx) {
            hashNeedle = (hashNeedle << 1) + valueTypeToUtf16(*(n - idx));
            hashHaystack = (hashHaystack << 1) + valueTypeToUtf16(*(h - idx));
        }
        hashHaystack -= valueTypeToUtf16(*haystack);
 
        while (haystack >= end) {
            hashHaystack += valueTypeToUtf16(*haystack);
            if (hashHaystack == hashNeedle
                 && QtPrivate::compareStrings(needle0, sv(haystack), Qt::CaseSensitive) == 0)
                return haystack - end;
            --haystack;
            REHASH(valueTypeToUtf16(haystack[sl]));
        }
    } else {
        for (qsizetype idx = 0; idx < sl; ++idx) {
            hashNeedle = (hashNeedle << 1) + foldCaseHelper(n - idx, needle);
            hashHaystack = (hashHaystack << 1) + foldCaseHelper(h - idx, end);
        }
        hashHaystack -= foldCaseHelper(haystack, end);
 
        while (haystack >= end) {
            hashHaystack += foldCaseHelper(haystack, end);
            if (hashHaystack == hashNeedle
                 && QtPrivate::compareStrings(sv(haystack), needle0, Qt::CaseInsensitive) == 0)
                return haystack - end;
            --haystack;
            REHASH(foldCaseHelper(haystack + sl, end));
        }
    }
    return -1;
}
} // unnamed namespace
 
/*
 * Note on the use of SIMD in qstring.cpp:
 *
 * Several operations with strings are improved with the use of SIMD code,
 * since they are repetitive. For MIPS, we have hand-written assembly code
 * outside of qstring.cpp targeting MIPS DSP and MIPS DSPr2. For ARM and for
 * x86, we can only use intrinsics and therefore everything is contained in
 * qstring.cpp. We need to use intrinsics only for those platforms due to the
 * different compilers and toolchains used, which have different syntax for
 * assembly sources.
 *
 * ** SSE notes: **
 *
 * Whenever multiple alternatives are equivalent or near so, we prefer the one
 * using instructions from SSE2, since SSE2 is guaranteed to be enabled for all
 * 64-bit builds and we enable it for 32-bit builds by default. Use of higher
 * SSE versions should be done when there is a clear performance benefit and
 * requires fallback code to SSE2, if it exists.
 *
 * Performance measurement in the past shows that most strings are short in
 * size and, therefore, do not benefit from alignment prologues. That is,
 * trying to find a 16-byte-aligned boundary to operate on is often more
 * expensive than executing the unaligned operation directly. In addition, note
 * that the QString private data is designed so that the data is stored on
 * 16-byte boundaries if the system malloc() returns 16-byte aligned pointers
 * on its own (64-bit glibc on Linux does; 32-bit glibc on Linux returns them
 * 50% of the time), so skipping the alignment prologue is actually optimizing
 * for the common case.
 */
 
#if defined(__mips_dsp)
// From qstring_mips_dsp_asm.S
extern "C" void qt_fromlatin1_mips_asm_unroll4 (char16_t*, const char*, uint);
extern "C" void qt_fromlatin1_mips_asm_unroll8 (char16_t*, const char*, uint);
extern "C" void qt_toLatin1_mips_dsp_asm(uchar *dst, const char16_t *src, int length);
#endif
 
static inline bool qt_starts_with(QStringView haystack, QStringView needle, Qt::CaseSensitivity cs);
static inline bool qt_starts_with(QStringView haystack, QLatin1String needle, Qt::CaseSensitivity cs);
static inline bool qt_starts_with(QStringView haystack, QChar needle, Qt::CaseSensitivity cs);
static inline bool qt_ends_with(QStringView haystack, QStringView needle, Qt::CaseSensitivity cs);
static inline bool qt_ends_with(QStringView haystack, QLatin1String needle, Qt::CaseSensitivity cs);
static inline bool qt_ends_with(QStringView haystack, QChar needle, Qt::CaseSensitivity cs);
 
#if defined(__SSE2__) && defined(Q_CC_GNU) && !defined(Q_CC_INTEL)
#  if defined(__SANITIZE_ADDRESS__) && Q_CC_GNU < 800 && !defined(Q_CC_CLANG)
#     warning "The __attribute__ on below will likely cause a build failure with your GCC version. Your choices are:"
#     warning "1) disable ASan;"
#     warning "2) disable the optimized code in qustrlen (change __SSE2__ to anything else);"
#     warning "3) upgrade your compiler (preferred)."
#  endif
 
// We may overrun the buffer, but that's a false positive:
// this won't crash nor produce incorrect results
__attribute__((__no_sanitize_address__))
#endif
qsizetype QtPrivate::qustrlen(const char16_t *str) noexcept
{
    qsizetype result = 0;
 
#if defined(__SSE2__) && !(defined(__SANITIZE_ADDRESS__) || __has_feature(address_sanitizer))
    // find the 16-byte alignment immediately prior or equal to str
    quintptr misalignment = quintptr(str) & 0xf;
    Q_ASSERT((misalignment & 1) == 0);
    const char16_t *ptr = str - (misalignment / 2);
 
    // load 16 bytes and see if we have a null
    // (aligned loads can never segfault)
    const __m128i zeroes = _mm_setzero_si128();
    __m128i data = _mm_load_si128(reinterpret_cast<const __m128i *>(ptr));
    __m128i comparison = _mm_cmpeq_epi16(data, zeroes);
    quint32 mask = _mm_movemask_epi8(comparison);
 
    // ignore the result prior to the beginning of str
    mask >>= misalignment;
 
    // Have we found something in the first block? Need to handle it now
    // because of the left shift above.
    if (mask)
        return qCountTrailingZeroBits(quint32(mask)) / 2;
 
    do {
        ptr += 8;
        data = _mm_load_si128(reinterpret_cast<const __m128i *>(ptr));
 
        comparison = _mm_cmpeq_epi16(data, zeroes);
        mask = _mm_movemask_epi8(comparison);
    } while (mask == 0);
 
    // found a null
    uint idx = qCountTrailingZeroBits(quint32(mask));
    return ptr - str + idx / 2;
#endif
 
    if (sizeof(wchar_t) == sizeof(char16_t))
        return wcslen(reinterpret_cast<const wchar_t *>(str));
 
    while (*str++)
        ++result;
    return result;
}
 
#if !defined(__OPTIMIZE_SIZE__)
namespace {
template <uint MaxCount> struct UnrollTailLoop
{
    template <typename RetType, typename Functor1, typename Functor2, typename Number>
    static inline RetType exec(Number count, RetType returnIfExited, Functor1 loopCheck, Functor2 returnIfFailed, Number i = 0)
    {
        /* equivalent to:
         *   while (count--) {
         *       if (loopCheck(i))
         *           return returnIfFailed(i);
         *   }
         *   return returnIfExited;
         */
 
        if (!count)
            return returnIfExited;
 
        bool check = loopCheck(i);
        if (check)
            return returnIfFailed(i);
 
        return UnrollTailLoop<MaxCount - 1>::exec(count - 1, returnIfExited, loopCheck, returnIfFailed, i + 1);
    }
 
    template <typename Functor, typename Number>
    static inline void exec(Number count, Functor code)
    {
        /* equivalent to:
         *   for (Number i = 0; i < count; ++i)
         *       code(i);
         */
        exec(count, 0, [=](Number i) -> bool { code(i); return false; }, [](Number) { return 0; });
    }
};
template <> template <typename RetType, typename Functor1, typename Functor2, typename Number>
inline RetType UnrollTailLoop<0>::exec(Number, RetType returnIfExited, Functor1, Functor2, Number)
{
    return returnIfExited;
}
}
#endif
 
const char16_t *QtPrivate::qustrchr(QStringView str, char16_t c) noexcept
{
    const char16_t *n = str.utf16();
    const char16_t *e = n + str.size();
 
#ifdef __SSE2__
    bool loops = true;
    // Using the PMOVMSKB instruction, we get two bits for each character
    // we compare.
#  if defined(__AVX2__) && !defined(__OPTIMIZE_SIZE__)
    // we're going to read n[0..15] (32 bytes)
    __m256i mch256 = _mm256_set1_epi32(c | (c << 16));
    for (const char16_t *next = n + 16; next <= e; n = next, next += 16) {
        __m256i data = _mm256_loadu_si256(reinterpret_cast<const __m256i *>(n));
        __m256i result = _mm256_cmpeq_epi16(data, mch256);
        uint mask = uint(_mm256_movemask_epi8(result));
        if (mask) {
            uint idx = qCountTrailingZeroBits(mask);
            return n + idx / 2;
        }
    }
    loops = false;
    __m128i mch = _mm256_castsi256_si128(mch256);
#  else
    __m128i mch = _mm_set1_epi32(c | (c << 16));
#  endif
 
    auto hasMatch = [mch, &n](__m128i data, ushort validityMask) {
        __m128i result = _mm_cmpeq_epi16(data, mch);
        uint mask = uint(_mm_movemask_epi8(result));
        if ((mask & validityMask) == 0)
            return false;
        uint idx = qCountTrailingZeroBits(mask);
        n += idx / 2;
        return true;
    };
 
    // we're going to read n[0..7] (16 bytes)
    for (const char16_t *next = n + 8; next <= e; n = next, next += 8) {
        __m128i data = _mm_loadu_si128(reinterpret_cast<const __m128i *>(n));
        if (hasMatch(data, 0xffff))
            return n;
 
        if (!loops) {
            n += 8;
            break;
        }
    }
 
#  if !defined(__OPTIMIZE_SIZE__)
    // we're going to read n[0..3] (8 bytes)
    if (e - n > 3) {
        __m128i data = _mm_loadl_epi64(reinterpret_cast<const __m128i *>(n));
        if (hasMatch(data, 0xff))
            return n;
 
        n += 4;
    }
 
    return UnrollTailLoop<3>::exec(e - n, e,
                                   [=](int i) { return n[i] == c; },
                                   [=](int i) { return n + i; });
#  endif
#elif defined(__ARM_NEON__)
    const uint16x8_t vmask = { 1, 1 << 1, 1 << 2, 1 << 3, 1 << 4, 1 << 5, 1 << 6, 1 << 7 };
    const uint16x8_t ch_vec = vdupq_n_u16(c);
    for (const char16_t *next = n + 8; next <= e; n = next, next += 8) {
        uint16x8_t data = vld1q_u16(reinterpret_cast<const uint16_t *>(n));
        uint mask = vaddvq_u16(vandq_u16(vceqq_u16(data, ch_vec), vmask));
        if (ushort(mask)) {
            // found a match
            return n + qCountTrailingZeroBits(mask);
        }
    }
#endif // aarch64
 
    --n;
    while (++n != e)
        if (*n == c)
            return n;
 
    return n;
}
 
#ifdef __SSE2__
// Scans from \a ptr to \a end until \a maskval is non-zero. Returns true if
// the no non-zero was found. Returns false and updates \a ptr to point to the
// first 16-bit word that has any bit set (note: if the input is 8-bit, \a ptr
// may be updated to one byte short).
static bool simdTestMask(const char *&ptr, const char *end, quint32 maskval)
{
    auto updatePtr = [&](uint result) {
        // found a character matching the mask
        uint idx = qCountTrailingZeroBits(~result);
        ptr += idx;
        return false;
    };
 
#  if defined(__SSE4_1__)
    __m128i mask;
    auto updatePtrSimd = [&](__m128i data) {
        __m128i masked = _mm_and_si128(mask, data);
        __m128i comparison = _mm_cmpeq_epi16(masked, _mm_setzero_si128());
        uint result = _mm_movemask_epi8(comparison);
        return updatePtr(result);
    };
 
#    if defined(__AVX2__)
    // AVX2 implementation: test 32 bytes at a time
    const __m256i mask256 = _mm256_broadcastd_epi32(_mm_cvtsi32_si128(maskval));
    while (ptr + 32 <= end) {
        __m256i data = _mm256_loadu_si256(reinterpret_cast<const __m256i *>(ptr));
        if (!_mm256_testz_si256(mask256, data)) {
            // found a character matching the mask
            __m256i masked256 = _mm256_and_si256(mask256, data);
            __m256i comparison256 = _mm256_cmpeq_epi16(masked256, _mm256_setzero_si256());
            return updatePtr(_mm256_movemask_epi8(comparison256));
        }
        ptr += 32;
    }
 
    mask = _mm256_castsi256_si128(mask256);
#    else
    // SSE 4.1 implementation: test 32 bytes at a time (two 16-byte
    // comparisons, unrolled)
    mask = _mm_set1_epi32(maskval);
    while (ptr + 32 <= end) {
        __m128i data1 = _mm_loadu_si128(reinterpret_cast<const __m128i *>(ptr));
        __m128i data2 = _mm_loadu_si128(reinterpret_cast<const __m128i *>(ptr + 16));
        if (!_mm_testz_si128(mask, data1))
            return updatePtrSimd(data1);
 
        ptr += 16;
        if (!_mm_testz_si128(mask, data2))
            return updatePtrSimd(data2);
        ptr += 16;
    }
#    endif
 
    // AVX2 and SSE4.1: final 16-byte comparison
    if (ptr + 16 <= end) {
        __m128i data1 = _mm_loadu_si128(reinterpret_cast<const __m128i *>(ptr));
        if (!_mm_testz_si128(mask, data1))
            return updatePtrSimd(data1);
        ptr += 16;
    }
 
    // and final 8-byte comparison
    if (ptr + 8 <= end) {
        __m128i data1 = _mm_loadl_epi64(reinterpret_cast<const __m128i *>(ptr));
        if (!_mm_testz_si128(mask, data1))
            return updatePtrSimd(data1);
        ptr += 8;
    }
 
#  else
    // SSE2 implementation: test 16 bytes at a time.
    const __m128i mask = _mm_set1_epi32(maskval);
    while (ptr + 16 <= end) {
        __m128i data = _mm_loadu_si128(reinterpret_cast<const __m128i *>(ptr));
        __m128i masked = _mm_and_si128(mask, data);
        __m128i comparison = _mm_cmpeq_epi16(masked, _mm_setzero_si128());
        quint16 result = _mm_movemask_epi8(comparison);
        if (result != 0xffff)
            return updatePtr(result);
        ptr += 16;
    }
 
    // and one 8-byte comparison
    if (ptr + 8 <= end) {
        __m128i data = _mm_loadl_epi64(reinterpret_cast<const __m128i *>(ptr));
        __m128i masked = _mm_and_si128(mask, data);
        __m128i comparison = _mm_cmpeq_epi16(masked, _mm_setzero_si128());
        quint8 result = _mm_movemask_epi8(comparison);
        if (result != 0xff)
            return updatePtr(result);
        ptr += 8;
    }
#  endif
 
    return true;
}
 
static Q_ALWAYS_INLINE __m128i mm_load8_zero_extend(const void *ptr)
{
    const __m128i *dataptr = static_cast<const __m128i *>(ptr);
#if defined(__SSE4_1__)
    // use a MOVQ followed by PMOVZXBW
    // if AVX2 is present, these should combine into a single VPMOVZXBW instruction
    __m128i data = _mm_loadl_epi64(dataptr);
    return _mm_cvtepu8_epi16(data);
#  else
    // use MOVQ followed by PUNPCKLBW
    __m128i data = _mm_loadl_epi64(dataptr);
    return _mm_unpacklo_epi8(data, _mm_setzero_si128());
#  endif
}
#endif
 
// Note: ptr on output may be off by one and point to a preceding US-ASCII
// character. Usually harmless.
bool qt_is_ascii(const char *&ptr, const char *end) noexcept
{
#if defined(__SSE2__)
    // Testing for the high bit can be done efficiently with just PMOVMSKB
    bool loops = true;
#  if defined(__AVX2__)
    while (ptr + 32 <= end) {
        __m256i data = _mm256_loadu_si256(reinterpret_cast<const __m256i *>(ptr));
        quint32 mask = _mm256_movemask_epi8(data);
        if (mask) {
            uint idx = qCountTrailingZeroBits(mask);
            ptr += idx;
            return false;
        }
        ptr += 32;
    }
    loops = false;
#  endif
 
    while (ptr + 16 <= end) {
        __m128i data = _mm_loadu_si128(reinterpret_cast<const __m128i *>(ptr));
        quint32 mask = _mm_movemask_epi8(data);
        if (mask) {
            uint idx = qCountTrailingZeroBits(mask);
            ptr += idx;
            return false;
        }
        ptr += 16;
 
        if (!loops)
            break;
    }
    if (ptr + 8 <= end) {
        __m128i data = _mm_loadl_epi64(reinterpret_cast<const __m128i *>(ptr));
        quint8 mask = _mm_movemask_epi8(data);
        if (mask) {
            uint idx = qCountTrailingZeroBits(mask);
            ptr += idx;
            return false;
        }
        ptr += 8;
    }
#endif
 
    while (ptr + 4 <= end) {
        quint32 data = qFromUnaligned<quint32>(ptr);
        if (data &= 0x80808080U) {
            uint idx = QSysInfo::ByteOrder == QSysInfo::BigEndian
                    ? qCountLeadingZeroBits(data)
                    : qCountTrailingZeroBits(data);
            ptr += idx / 8;
            return false;
        }
        ptr += 4;
    }
 
    while (ptr != end) {
        if (quint8(*ptr) & 0x80)
            return false;
        ++ptr;
    }
    return true;
}
 
bool QtPrivate::isAscii(QLatin1String s) noexcept
{
    const char *ptr = s.begin();
    const char *end = s.end();
 
    return qt_is_ascii(ptr, end);
}
 
static bool isAscii_helper(const char16_t *&ptr, const char16_t *end)
{
#ifdef __SSE2__
    const char *ptr8 = reinterpret_cast<const char *>(ptr);
    const char *end8 = reinterpret_cast<const char *>(end);
    bool ok = simdTestMask(ptr8, end8, 0xff80ff80);
    ptr = reinterpret_cast<const char16_t *>(ptr8);
    if (!ok)
        return false;
#endif
 
    while (ptr != end) {
        if (*ptr & 0xff80)
            return false;
        ++ptr;
    }
    return true;
}
 
bool QtPrivate::isAscii(QStringView s) noexcept
{
    const char16_t *ptr = s.utf16();
    const char16_t *end = ptr + s.size();
 
    return isAscii_helper(ptr, end);
}
 
bool QtPrivate::isLatin1(QStringView s) noexcept
{
    const char16_t *ptr = s.utf16();
    const char16_t *end = ptr + s.size();
 
#ifdef __SSE2__
    const char *ptr8 = reinterpret_cast<const char *>(ptr);
    const char *end8 = reinterpret_cast<const char *>(end);
    if (!simdTestMask(ptr8, end8, 0xff00ff00))
        return false;
    ptr = reinterpret_cast<const char16_t *>(ptr8);
#endif
 
    while (ptr != end) {
        if (*ptr++ > 0xff)
            return false;
    }
    return true;
}
 
bool QtPrivate::isValidUtf16(QStringView s) noexcept
{
    constexpr char32_t InvalidCodePoint = UINT_MAX;
 
    QStringIterator i(s);
    while (i.hasNext()) {
        const char32_t c = i.next(InvalidCodePoint);
        if (c == InvalidCodePoint)
            return false;
    }
 
    return true;
}
 
// conversion between Latin 1 and UTF-16
Q_CORE_EXPORT void qt_from_latin1(char16_t *dst, const char *str, size_t size) noexcept
{
    /* SIMD:
     * Unpacking with SSE has been shown to improve performance on recent CPUs
     * The same method gives no improvement with NEON. On Aarch64, clang will do the vectorization
     * itself in exactly the same way as one would do it with intrinsics.
     */
#if defined(__SSE2__)
    const char *e = str + size;
    qptrdiff offset = 0;
 
    // we're going to read str[offset..offset+15] (16 bytes)
    for ( ; str + offset + 15 < e; offset += 16) {
        const __m128i chunk = _mm_loadu_si128((const __m128i*)(str + offset)); // load
#ifdef __AVX2__
        // zero extend to an YMM register
        const __m256i extended = _mm256_cvtepu8_epi16(chunk);
 
        // store
        _mm256_storeu_si256((__m256i*)(dst + offset), extended);
#else
        const __m128i nullMask = _mm_set1_epi32(0);
 
        // unpack the first 8 bytes, padding with zeros
        const __m128i firstHalf = _mm_unpacklo_epi8(chunk, nullMask);
        _mm_storeu_si128((__m128i*)(dst + offset), firstHalf); // store
 
        // unpack the last 8 bytes, padding with zeros
        const __m128i secondHalf = _mm_unpackhi_epi8 (chunk, nullMask);
        _mm_storeu_si128((__m128i*)(dst + offset + 8), secondHalf); // store
#endif
    }
 
    // we're going to read str[offset..offset+7] (8 bytes)
    if (str + offset + 7 < e) {
        const __m128i unpacked = mm_load8_zero_extend(str + offset);
        _mm_storeu_si128(reinterpret_cast<__m128i *>(dst + offset), unpacked);
        offset += 8;
    }
 
    size = size % 8;
    dst += offset;
    str += offset;
#  if !defined(__OPTIMIZE_SIZE__)
    return UnrollTailLoop<7>::exec(int(size), [=](int i) { dst[i] = (uchar)str[i]; });
#  endif
#endif
#if defined(__mips_dsp)
    if (size > 20)
        qt_fromlatin1_mips_asm_unroll8(dst, str, size);
    else
        qt_fromlatin1_mips_asm_unroll4(dst, str, size);
#else
    while (size--)
        *dst++ = (uchar)*str++;
#endif
}
 
template <bool Checked>
static void qt_to_latin1_internal(uchar *dst, const char16_t *src, qsizetype length)
{
#if defined(__SSE2__)
    uchar *e = dst + length;
    qptrdiff offset = 0;
 
#  ifdef __AVX2__
    const __m256i questionMark256 = _mm256_broadcastw_epi16(_mm_cvtsi32_si128('?'));
    const __m256i outOfRange256 = _mm256_broadcastw_epi16(_mm_cvtsi32_si128(0x100));
    const __m128i questionMark = _mm256_castsi256_si128(questionMark256);
    const __m128i outOfRange = _mm256_castsi256_si128(outOfRange256);
#  else
    const __m128i questionMark = _mm_set1_epi16('?');
    const __m128i outOfRange = _mm_set1_epi16(0x100);
#  endif
 
    auto mergeQuestionMarks = [=](__m128i chunk) {
        // SSE has no compare instruction for unsigned comparison.
# ifdef __SSE4_1__
        // We use an unsigned uc = qMin(uc, 0x100) and then compare for equality.
        chunk = _mm_min_epu16(chunk, outOfRange);
        const __m128i offLimitMask = _mm_cmpeq_epi16(chunk, outOfRange);
        chunk = _mm_blendv_epi8(chunk, questionMark, offLimitMask);
# else
        // The variables must be shiffted + 0x8000 to be compared
        const __m128i signedBitOffset = _mm_set1_epi16(short(0x8000));
        const __m128i thresholdMask = _mm_set1_epi16(short(0xff + 0x8000));
 
        const __m128i signedChunk = _mm_add_epi16(chunk, signedBitOffset);
        const __m128i offLimitMask = _mm_cmpgt_epi16(signedChunk, thresholdMask);
 
        // offLimitQuestionMark contains '?' for each 16 bits that was off-limit
        // the 16 bits that were correct contains zeros
        const __m128i offLimitQuestionMark = _mm_and_si128(offLimitMask, questionMark);
 
        // correctBytes contains the bytes that were in limit
        // the 16 bits that were off limits contains zeros
        const __m128i correctBytes = _mm_andnot_si128(offLimitMask, chunk);
 
        // merge offLimitQuestionMark and correctBytes to have the result
        chunk = _mm_or_si128(correctBytes, offLimitQuestionMark);
 
        Q_UNUSED(outOfRange);
# endif
        return chunk;
    };
 
    // we're going to write to dst[offset..offset+15] (16 bytes)
    for ( ; dst + offset + 15 < e; offset += 16) {
#  if defined(__AVX2__)
        __m256i chunk = _mm256_loadu_si256(reinterpret_cast<const __m256i *>(src + offset));
        if (Checked) {
            // See mergeQuestionMarks lambda above for details
            chunk = _mm256_min_epu16(chunk, outOfRange256);
            const __m256i offLimitMask = _mm256_cmpeq_epi16(chunk, outOfRange256);
            chunk = _mm256_blendv_epi8(chunk, questionMark256, offLimitMask);
        }
 
        const __m128i chunk2 = _mm256_extracti128_si256(chunk, 1);
        const __m128i chunk1 = _mm256_castsi256_si128(chunk);
#  else
        __m128i chunk1 = _mm_loadu_si128((const __m128i*)(src + offset)); // load
        if (Checked)
            chunk1 = mergeQuestionMarks(chunk1);
 
        __m128i chunk2 = _mm_loadu_si128((const __m128i*)(src + offset + 8)); // load
        if (Checked)
            chunk2 = mergeQuestionMarks(chunk2);
#  endif
 
        // pack the two vector to 16 x 8bits elements
        const __m128i result = _mm_packus_epi16(chunk1, chunk2);
        _mm_storeu_si128((__m128i*)(dst + offset), result); // store
    }
 
#  if !defined(__OPTIMIZE_SIZE__)
    // we're going to write to dst[offset..offset+7] (8 bytes)
    if (dst + offset + 7 < e) {
        __m128i chunk = _mm_loadu_si128(reinterpret_cast<const __m128i *>(src + offset));
        if (Checked)
            chunk = mergeQuestionMarks(chunk);
 
        // pack, where the upper half is ignored
        const __m128i result = _mm_packus_epi16(chunk, chunk);
        _mm_storel_epi64(reinterpret_cast<__m128i *>(dst + offset), result);
        offset += 8;
    }
 
    // we're going to write to dst[offset..offset+3] (4 bytes)
    if (dst + offset + 3 < e) {
        __m128i chunk = _mm_loadl_epi64(reinterpret_cast<const __m128i *>(src + offset));
        if (Checked)
            chunk = mergeQuestionMarks(chunk);
 
        // pack, we'll the upper three quarters
        const __m128i result = _mm_packus_epi16(chunk, chunk);
        qToUnaligned(_mm_cvtsi128_si32(result), dst + offset);
        offset += 4;
    }
 
    length = length % 4;
#  else
    length = length % 16;
#  endif // optimize size
 
    // advance dst, src for tail processing
    dst += offset;
    src += offset;
 
#  if !defined(__OPTIMIZE_SIZE__)
    return UnrollTailLoop<3>::exec(length, [=](int i) {
        if (Checked)
            dst[i] = (src[i]>0xff) ? '?' : (uchar) src[i];
        else
            dst[i] = src[i];
    });
#  endif
#elif defined(__ARM_NEON__)
    // Refer to the documentation of the SSE2 implementation.
    // This uses exactly the same method as for SSE except:
    // 1) neon has unsigned comparison
    // 2) packing is done to 64 bits (8 x 8bits component).
    if (length >= 16) {
        const int chunkCount = length >> 3; // divided by 8
        const uint16x8_t questionMark = vdupq_n_u16('?'); // set
        const uint16x8_t thresholdMask = vdupq_n_u16(0xff); // set
        for (int i = 0; i < chunkCount; ++i) {
            uint16x8_t chunk = vld1q_u16((uint16_t *)src); // load
            src += 8;
 
            if (Checked) {
                const uint16x8_t offLimitMask = vcgtq_u16(chunk, thresholdMask); // chunk > thresholdMask
                const uint16x8_t offLimitQuestionMark = vandq_u16(offLimitMask, questionMark); // offLimitMask & questionMark
                const uint16x8_t correctBytes = vbicq_u16(chunk, offLimitMask); // !offLimitMask & chunk
                chunk = vorrq_u16(correctBytes, offLimitQuestionMark); // correctBytes | offLimitQuestionMark
            }
            const uint8x8_t result = vmovn_u16(chunk); // narrowing move->packing
            vst1_u8(dst, result); // store
            dst += 8;
        }
        length = length % 8;
    }
#endif
#if defined(__mips_dsp)
    qt_toLatin1_mips_dsp_asm(dst, src, length);
#else
    while (length--) {
        if (Checked)
            *dst++ = (*src>0xff) ? '?' : (uchar) *src;
        else
            *dst++ = *src;
        ++src;
    }
#endif
}
 
static void qt_to_latin1(uchar *dst, const char16_t *src, qsizetype length)
{
    qt_to_latin1_internal<true>(dst, src, length);
}
 
void qt_to_latin1_unchecked(uchar *dst, const char16_t *src, qsizetype length)
{
    qt_to_latin1_internal<false>(dst, src, length);
}
 
// Unicode case-insensitive comparison
static int ucstricmp(const QChar *a, const QChar *ae, const QChar *b, const QChar *be)
{
    if (a == b)
        return (ae - be);
 
    const QChar *e = ae;
    if (be - b < ae - a)
        e = a + (be - b);
 
    char32_t alast = 0;
    char32_t blast = 0;
    while (a < e) {
//         qDebug() << Qt::hex << alast << blast;
//         qDebug() << Qt::hex << "*a=" << *a << "alast=" << alast << "folded=" << foldCase (*a, alast);
//         qDebug() << Qt::hex << "*b=" << *b << "blast=" << blast << "folded=" << foldCase (*b, blast);
        int diff = foldCase(a->unicode(), alast) - foldCase(b->unicode(), blast);
        if ((diff))
            return diff;
        ++a;
        ++b;
    }
    if (a == ae) {
        if (b == be)
            return 0;
        return -1;
    }
    return 1;
}
 
// Case-insensitive comparison between a Unicode string and a QLatin1String
static int ucstricmp(const QChar *a, const QChar *ae, const char *b, const char *be)
{
    auto e = ae;
    if (be - b < ae - a)
        e = a + (be - b);
 
    while (a < e) {
        int diff = foldCase(a->unicode()) - foldCase(char16_t{uchar(*b)});
        if ((diff))
            return diff;
        ++a;
        ++b;
    }
    if (a == ae) {
        if (b == be)
            return 0;
        return -1;
    }
    return 1;
}
 
// Case-insensitive comparison between a Unicode string and a UTF-8 string
static int ucstricmp8(const char *utf8, const char *utf8end, const QChar *utf16, const QChar *utf16end)
{
    auto src1 = reinterpret_cast<const uchar *>(utf8);
    auto end1 = reinterpret_cast<const uchar *>(utf8end);
    QStringIterator src2(utf16, utf16end);
 
    while (src1 < end1 && src2.hasNext()) {
        char32_t uc1 = 0;
        char32_t *output = &uc1;
        uchar b = *src1++;
        int res = QUtf8Functions::fromUtf8<QUtf8BaseTraits>(b, output, src1, end1);
        if (res < 0) {
            // decoding error
            uc1 = QChar::ReplacementCharacter;
        } else {
            uc1 = QChar::toCaseFolded(uc1);
        }
 
        char32_t uc2 = QChar::toCaseFolded(src2.next());
        int diff = uc1 - uc2;   // can't underflow
        if (diff)
            return diff;
    }
 
    // the shorter string sorts first
    return (end1 > src1) - int(src2.hasNext());
}
 
#if defined(__mips_dsp)
// From qstring_mips_dsp_asm.S
extern "C" int qt_ucstrncmp_mips_dsp_asm(const char16_t *a,
                                         const char16_t *b,
                                         unsigned len);
#endif
 
// Unicode case-sensitive compare two same-sized strings
static int ucstrncmp(const QChar *a, const QChar *b, size_t l)
{
#ifdef __OPTIMIZE_SIZE__
    const QChar *end = a + l;
    while (a < end) {
        if (int diff = (int)a->unicode() - (int)b->unicode())
            return diff;
        ++a;
        ++b;
    }
    return 0;
#else
#if defined(__mips_dsp)
    static_assert(sizeof(uint) == sizeof(size_t));
    if (l >= 8) {
        return qt_ucstrncmp_mips_dsp_asm(reinterpret_cast<const char16_t*>(a),
                                         reinterpret_cast<const char16_t*>(b),
                                         l);
    }
#endif // __mips_dsp
#ifdef __SSE2__
    const QChar *end = a + l;
    qptrdiff offset = 0;
 
    // Using the PMOVMSKB instruction, we get two bits for each character
    // we compare.
    int retval;
    auto isDifferent = [a, b, &offset, &retval](__m128i a_data, __m128i b_data) {
        __m128i result = _mm_cmpeq_epi16(a_data, b_data);
        uint mask = ~uint(_mm_movemask_epi8(result));
        if (ushort(mask) == 0)
            return false;
        uint idx = qCountTrailingZeroBits(mask);
        retval = a[offset + idx / 2].unicode() - b[offset + idx / 2].unicode();
        return true;
    };
 
    // we're going to read a[0..15] and b[0..15] (32 bytes)
    for ( ; end - a >= offset + 16; offset += 16) {
#ifdef __AVX2__
        __m256i a_data = _mm256_loadu_si256(reinterpret_cast<const __m256i *>(a + offset));
        __m256i b_data = _mm256_loadu_si256(reinterpret_cast<const __m256i *>(b + offset));
        __m256i result = _mm256_cmpeq_epi16(a_data, b_data);
        uint mask = _mm256_movemask_epi8(result);
#else
        __m128i a_data1 = _mm_loadu_si128(reinterpret_cast<const __m128i *>(a + offset));
        __m128i a_data2 = _mm_loadu_si128(reinterpret_cast<const __m128i *>(a + offset + 8));
        __m128i b_data1 = _mm_loadu_si128(reinterpret_cast<const __m128i *>(b + offset));
        __m128i b_data2 = _mm_loadu_si128(reinterpret_cast<const __m128i *>(b + offset + 8));
        __m128i result1 = _mm_cmpeq_epi16(a_data1, b_data1);
        __m128i result2 = _mm_cmpeq_epi16(a_data2, b_data2);
        uint mask = _mm_movemask_epi8(result1) | (_mm_movemask_epi8(result2) << 16);
#endif
        mask = ~mask;
        if (mask) {
            // found a different character
            uint idx = qCountTrailingZeroBits(mask);
            return a[offset + idx / 2].unicode() - b[offset + idx / 2].unicode();
        }
    }
 
    // we're going to read a[0..7] and b[0..7] (16 bytes)
    if (end - a >= offset + 8) {
        __m128i a_data = _mm_loadu_si128(reinterpret_cast<const __m128i *>(a + offset));
        __m128i b_data = _mm_loadu_si128(reinterpret_cast<const __m128i *>(b + offset));
        if (isDifferent(a_data, b_data))
            return retval;
 
        offset += 8;
    }
 
    // we're going to read a[0..3] and b[0..3] (8 bytes)
    if (end - a >= offset + 4) {
        __m128i a_data = _mm_loadl_epi64(reinterpret_cast<const __m128i *>(a + offset));
        __m128i b_data = _mm_loadl_epi64(reinterpret_cast<const __m128i *>(b + offset));
        if (isDifferent(a_data, b_data))
            return retval;
 
        offset += 4;
    }
 
    // reset l
    l &= 3;
 
    const auto lambda = [=](size_t i) -> int {
        return a[offset + i].unicode() - b[offset + i].unicode();
    };
    return UnrollTailLoop<3>::exec(l, 0, lambda, lambda);
#endif
#ifdef __ARM_NEON__
    if (l >= 8) {
        const QChar *end = a + l;
        const uint16x8_t mask = { 1, 1 << 1, 1 << 2, 1 << 3, 1 << 4, 1 << 5, 1 << 6, 1 << 7 };
        while (end - a > 7) {
            uint16x8_t da = vld1q_u16(reinterpret_cast<const uint16_t *>(a));
            uint16x8_t db = vld1q_u16(reinterpret_cast<const uint16_t *>(b));
 
            uint8_t r = ~(uint8_t)vaddvq_u16(vandq_u16(vceqq_u16(da, db), mask));
            if (r) {
                // found a different QChar
                uint idx = qCountTrailingZeroBits(r);
                return (int)a[idx].unicode() - (int)b[idx].unicode();
            }
            a += 8;
            b += 8;
        }
        l &= 7;
    }
    const auto lambda = [=](size_t i) -> int {
        return a[i].unicode() - b[i].unicode();
    };
    return UnrollTailLoop<7>::exec(l, 0, lambda, lambda);
#endif // __ARM_NEON__
    if (!l)
        return 0;
 
    // check alignment
    if ((reinterpret_cast<quintptr>(a) & 2) == (reinterpret_cast<quintptr>(b) & 2)) {
        // both addresses have the same alignment
        if (reinterpret_cast<quintptr>(a) & 2) {
            // both addresses are not aligned to 4-bytes boundaries
            // compare the first character
            if (*a != *b)
                return a->unicode() - b->unicode();
            --l;
            ++a;
            ++b;
 
            // now both addresses are 4-bytes aligned
        }
 
        // both addresses are 4-bytes aligned
        // do a fast 32-bit comparison
        const quint32 *da = reinterpret_cast<const quint32 *>(a);
        const quint32 *db = reinterpret_cast<const quint32 *>(b);
        const quint32 *e = da + (l >> 1);
        for ( ; da != e; ++da, ++db) {
            if (*da != *db) {
                a = reinterpret_cast<const QChar *>(da);
                b = reinterpret_cast<const QChar *>(db);
                if (*a != *b)
                    return a->unicode() - b->unicode();
                return a[1].unicode() - b[1].unicode();
            }
        }
 
        // do we have a tail?
        a = reinterpret_cast<const QChar *>(da);
        b = reinterpret_cast<const QChar *>(db);
        return (l & 1) ? a->unicode() - b->unicode() : 0;
    } else {
        // one of the addresses isn't 4-byte aligned but the other is
        const QChar *e = a + l;
        for ( ; a != e; ++a, ++b) {
            if (*a != *b)
                return a->unicode() - b->unicode();
        }
    }
    return 0;
#endif
}
 
static int ucstrncmp(const QChar *a, const uchar *c, size_t l)
{
    const char16_t *uc = reinterpret_cast<const char16_t *>(a);
    const char16_t *e = uc + l;
 
#ifdef __SSE2__
    __m128i nullmask = _mm_setzero_si128();
    qptrdiff offset = 0;
 
#  if !defined(__OPTIMIZE_SIZE__)
    // Using the PMOVMSKB instruction, we get two bits for each character
    // we compare.
    int retval;
    auto isDifferent = [uc, c, &offset, &retval](__m128i a_data, __m128i b_data) {
        __m128i result = _mm_cmpeq_epi16(a_data, b_data);
        uint mask = ~uint(_mm_movemask_epi8(result));
        if (ushort(mask) == 0)
            return false;
        uint idx = qCountTrailingZeroBits(mask);
        retval = uc[offset + idx / 2] - c[offset + idx / 2];
        return true;
    };
#  endif
 
    // we're going to read uc[offset..offset+15] (32 bytes)
    // and c[offset..offset+15] (16 bytes)
    for ( ; uc + offset + 15 < e; offset += 16) {
        // similar to fromLatin1_helper:
        // load 16 bytes of Latin 1 data
        __m128i chunk = _mm_loadu_si128((const __m128i*)(c + offset));
 
#  ifdef __AVX2__
        // expand Latin 1 data via zero extension
        __m256i ldata = _mm256_cvtepu8_epi16(chunk);
 
        // load UTF-16 data and compare
        __m256i ucdata = _mm256_loadu_si256((const __m256i*)(uc + offset));
        __m256i result = _mm256_cmpeq_epi16(ldata, ucdata);
 
        uint mask = ~_mm256_movemask_epi8(result);
#  else
        // expand via unpacking
        __m128i firstHalf = _mm_unpacklo_epi8(chunk, nullmask);
        __m128i secondHalf = _mm_unpackhi_epi8(chunk, nullmask);
 
        // load UTF-16 data and compare
        __m128i ucdata1 = _mm_loadu_si128((const __m128i*)(uc + offset));
        __m128i ucdata2 = _mm_loadu_si128((const __m128i*)(uc + offset + 8));
        __m128i result1 = _mm_cmpeq_epi16(firstHalf, ucdata1);
        __m128i result2 = _mm_cmpeq_epi16(secondHalf, ucdata2);
 
        uint mask = ~(_mm_movemask_epi8(result1) | _mm_movemask_epi8(result2) << 16);
#  endif
        if (mask) {
            // found a different character
            uint idx = qCountTrailingZeroBits(mask);
            return uc[offset + idx / 2] - c[offset + idx / 2];
        }
    }
 
#  if !defined(__OPTIMIZE_SIZE__)
    // we'll read uc[offset..offset+7] (16 bytes) and c[offset..offset+7] (8 bytes)
    if (uc + offset + 7 < e) {
        // same, but we're using an 8-byte load
        __m128i secondHalf = mm_load8_zero_extend(c + offset);
 
        __m128i ucdata = _mm_loadu_si128((const __m128i*)(uc + offset));
        if (isDifferent(ucdata, secondHalf))
            return retval;
 
        // still matched
        offset += 8;
    }
 
    enum { MaxTailLength = 3 };
    // we'll read uc[offset..offset+3] (8 bytes) and c[offset..offset+3] (4 bytes)
    if (uc + offset + 3 < e) {
        __m128i chunk = _mm_cvtsi32_si128(qFromUnaligned<int>(c + offset));
        __m128i secondHalf = _mm_unpacklo_epi8(chunk, nullmask);
 
        __m128i ucdata = _mm_loadl_epi64(reinterpret_cast<const __m128i *>(uc + offset));
        if (isDifferent(ucdata, secondHalf))
            return retval;
 
        // still matched
        offset += 4;
    }
#  endif // optimize size
 
    // reset uc and c
    uc += offset;
    c += offset;
 
#  if !defined(__OPTIMIZE_SIZE__)
    const auto lambda = [=](size_t i) { return uc[i] - char16_t(c[i]); };
    return UnrollTailLoop<MaxTailLength>::exec(e - uc, 0, lambda, lambda);
#  endif
#endif
 
    while (uc < e) {
        int diff = *uc - *c;
        if (diff)
            return diff;
        uc++, c++;
    }
 
    return 0;
}
 
constexpr int lencmp(qsizetype lhs, qsizetype rhs) noexcept
{
    return lhs == rhs ? 0 :
           lhs >  rhs ? 1 :
           /* else */  -1 ;
}
 
// Unicode case-sensitive comparison
static int ucstrcmp(const QChar *a, size_t alen, const QChar *b, size_t blen)
{
    if (a == b && alen == blen)
        return 0;
    const size_t l = qMin(alen, blen);
    int cmp = ucstrncmp(a, b, l);
    return cmp ? cmp : lencmp(alen, blen);
}
 
static int ucstrcmp(const QChar *a, size_t alen, const char *b, size_t blen)
{
    const size_t l = qMin(alen, blen);
    const int cmp = ucstrncmp(a, reinterpret_cast<const uchar*>(b), l);
    return cmp ? cmp : lencmp(alen, blen);
}
 
static constexpr uchar latin1Lower[256] = {
    0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f,
    0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,0x18,0x19,0x1a,0x1b,0x1c,0x1d,0x1e,0x1f,
    0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,0x28,0x29,0x2a,0x2b,0x2c,0x2d,0x2e,0x2f,
    0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39,0x3a,0x3b,0x3c,0x3d,0x3e,0x3f,
    0x40,0x61,0x62,0x63,0x64,0x65,0x66,0x67,0x68,0x69,0x6a,0x6b,0x6c,0x6d,0x6e,0x6f,
    0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,0x78,0x79,0x7a,0x5b,0x5c,0x5d,0x5e,0x5f,
    0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67,0x68,0x69,0x6a,0x6b,0x6c,0x6d,0x6e,0x6f,
    0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,0x78,0x79,0x7a,0x7b,0x7c,0x7d,0x7e,0x7f,
    0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87,0x88,0x89,0x8a,0x8b,0x8c,0x8d,0x8e,0x8f,
    0x90,0x91,0x92,0x93,0x94,0x95,0x96,0x97,0x98,0x99,0x9a,0x9b,0x9c,0x9d,0x9e,0x9f,
    0xa0,0xa1,0xa2,0xa3,0xa4,0xa5,0xa6,0xa7,0xa8,0xa9,0xaa,0xab,0xac,0xad,0xae,0xaf,
    0xb0,0xb1,0xb2,0xb3,0xb4,0xb5,0xb6,0xb7,0xb8,0xb9,0xba,0xbb,0xbc,0xbd,0xbe,0xbf,
    // 0xd7 (multiplication sign) and 0xdf (sz ligature) complicate life
    0xe0,0xe1,0xe2,0xe3,0xe4,0xe5,0xe6,0xe7,0xe8,0xe9,0xea,0xeb,0xec,0xed,0xee,0xef,
    0xf0,0xf1,0xf2,0xf3,0xf4,0xf5,0xf6,0xd7,0xf8,0xf9,0xfa,0xfb,0xfc,0xfd,0xfe,0xdf,
    0xe0,0xe1,0xe2,0xe3,0xe4,0xe5,0xe6,0xe7,0xe8,0xe9,0xea,0xeb,0xec,0xed,0xee,0xef,
    0xf0,0xf1,0xf2,0xf3,0xf4,0xf5,0xf6,0xf7,0xf8,0xf9,0xfa,0xfb,0xfc,0xfd,0xfe,0xff
};
static int latin1nicmp(const char *lhsChar, qsizetype lSize, const char *rhsChar, qsizetype rSize)
{
    // We're called with QLatin1String's .data() and .size():
    Q_ASSERT(lSize >= 0 && rSize >= 0);
    if (!lSize)
        return rSize ? -1 : 0;
    if (!rSize)
        return 1;
    const qsizetype size = std::min(lSize, rSize);
 
    const uchar *lhs = reinterpret_cast<const uchar *>(lhsChar);
    const uchar *rhs = reinterpret_cast<const uchar *>(rhsChar);
    Q_ASSERT(lhs && rhs); // since both lSize and rSize are positive
    for (qsizetype i = 0; i < size; i++) {
        if (int res = latin1Lower[lhs[i]] - latin1Lower[rhs[i]])
            return res;
    }
    return lencmp(lSize, rSize);
}
bool QtPrivate::equalStrings(QStringView lhs, QStringView rhs) noexcept
{
    return ucstrcmp(lhs.begin(), lhs.size(), rhs.begin(), rhs.size()) == 0;
}
 
bool QtPrivate::equalStrings(QStringView lhs, QLatin1String rhs) noexcept
{
    return ucstrcmp(lhs.begin(), lhs.size(), rhs.begin(), rhs.size()) == 0;
}
 
bool QtPrivate::equalStrings(QLatin1String lhs, QStringView rhs) noexcept
{
    return QtPrivate::equalStrings(rhs, lhs);
}
 
bool QtPrivate::equalStrings(QLatin1String lhs, QLatin1String rhs) noexcept
{
    return lhs.size() == rhs.size() && (!lhs.size() || memcmp(lhs.data(), rhs.data(), lhs.size()) == 0);
}
 
bool QtPrivate::equalStrings(QBasicUtf8StringView<false> lhs, QStringView rhs) noexcept
{
    return QUtf8::compareUtf8(lhs, rhs) == 0;
}
 
bool QtPrivate::equalStrings(QStringView lhs, QBasicUtf8StringView<false> rhs) noexcept
{
    return QtPrivate::equalStrings(rhs, lhs);
}
 
bool QtPrivate::equalStrings(QLatin1String lhs, QBasicUtf8StringView<false> rhs) noexcept
{
    QString r = rhs.toString();
    return QtPrivate::equalStrings(lhs, r); // ### optimize!
}
 
bool QtPrivate::equalStrings(QBasicUtf8StringView<false> lhs, QLatin1String rhs) noexcept
{
    return QtPrivate::equalStrings(rhs, lhs);
}
 
bool QtPrivate::equalStrings(QBasicUtf8StringView<false> lhs, QBasicUtf8StringView<false> rhs) noexcept
{
    return lhs.size() == rhs.size() && (!lhs.size() || memcmp(lhs.data(), rhs.data(), lhs.size()) == 0);
}
 
bool QAnyStringView::equal(QAnyStringView lhs, QAnyStringView rhs) noexcept
{
    if (lhs.size() != rhs.size() && lhs.isUtf8() == rhs.isUtf8())
        return false;
    return lhs.visit([rhs](auto lhs) {
        return rhs.visit([lhs](auto rhs) {
            return QtPrivate::equalStrings(lhs, rhs);
        });
    });
}
 
int QtPrivate::compareStrings(QStringView lhs, QStringView rhs, Qt::CaseSensitivity cs) noexcept
{
    if (cs == Qt::CaseSensitive)
        return ucstrcmp(lhs.begin(), lhs.size(), rhs.begin(), rhs.size());
    return ucstricmp(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}
 
int QtPrivate::compareStrings(QStringView lhs, QLatin1String rhs, Qt::CaseSensitivity cs) noexcept
{
    if (cs == Qt::CaseSensitive)
        return ucstrcmp(lhs.begin(), lhs.size(), rhs.begin(), rhs.size());
    return ucstricmp(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}
 
int QtPrivate::compareStrings(QStringView lhs, QBasicUtf8StringView<false> rhs, Qt::CaseSensitivity cs) noexcept
{
    return -compareStrings(rhs, lhs, cs);
}
 
int QtPrivate::compareStrings(QLatin1String lhs, QStringView rhs, Qt::CaseSensitivity cs) noexcept
{
    return -compareStrings(rhs, lhs, cs);
}
 
int QtPrivate::compareStrings(QLatin1String lhs, QLatin1String rhs, Qt::CaseSensitivity cs) noexcept
{
    if (lhs.isEmpty())
        return lencmp(qsizetype(0), rhs.size());
    if (cs == Qt::CaseInsensitive)
        return latin1nicmp(lhs.data(), lhs.size(), rhs.data(), rhs.size());
    const auto l = std::min(lhs.size(), rhs.size());
    int r = memcmp(lhs.data(), rhs.data(), l);
    return r ? r : lencmp(lhs.size(), rhs.size());
}
 
int QtPrivate::compareStrings(QLatin1String lhs, QBasicUtf8StringView<false> rhs, Qt::CaseSensitivity cs) noexcept
{
    return compareStrings(lhs, rhs.toString(), cs); // ### optimize!
}
 
int QtPrivate::compareStrings(QBasicUtf8StringView<false> lhs, QStringView rhs, Qt::CaseSensitivity cs) noexcept
{
    if (cs == Qt::CaseSensitive)
        return QUtf8::compareUtf8(lhs, rhs);
    return ucstricmp8(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}
 
int QtPrivate::compareStrings(QBasicUtf8StringView<false> lhs, QLatin1String rhs, Qt::CaseSensitivity cs) noexcept
{
    return -compareStrings(rhs, lhs, cs);
}
 
int QtPrivate::compareStrings(QBasicUtf8StringView<false> lhs, QBasicUtf8StringView<false> rhs, Qt::CaseSensitivity cs) noexcept
{
    if (lhs.isEmpty())
        return lencmp(0, rhs.size());
    if (cs == Qt::CaseInsensitive)
        return compareStrings(lhs.toString(), rhs.toString(), cs); // ### optimize!
    const auto l = std::min(lhs.size(), rhs.size());
    int r = memcmp(lhs.data(), rhs.data(), l);
    return r ? r : lencmp(lhs.size(), rhs.size());
}
 
int QAnyStringView::compare(QAnyStringView lhs, QAnyStringView rhs, Qt::CaseSensitivity cs) noexcept
{
    return lhs.visit([rhs, cs](auto lhs) {
        return rhs.visit([lhs, cs](auto rhs) {
            return QtPrivate::compareStrings(lhs, rhs, cs);
        });
    });
}
 
// ### Qt 7: do not allow anything but ASCII digits
// in arg()'s replacements.
#if QT_VERSION < QT_VERSION_CHECK(7, 0, 0)
static bool supportUnicodeDigitValuesInArg()
{
    static const bool result = []() {
        static const char supportUnicodeDigitValuesEnvVar[]
                = "QT_USE_UNICODE_DIGIT_VALUES_IN_STRING_ARG";
 
        if (qEnvironmentVariableIsSet(supportUnicodeDigitValuesEnvVar))
            return qEnvironmentVariableIntValue(supportUnicodeDigitValuesEnvVar) != 0;
 
#if QT_VERSION < QT_VERSION_CHECK(6, 6, 0) // keep it in sync with the test
        return true;
#else
        return false;
#endif
    }();
 
    return result;
}
#endif
 
static int qArgDigitValue(QChar ch) noexcept
{
#if QT_VERSION < QT_VERSION_CHECK(7, 0, 0)
    if (supportUnicodeDigitValuesInArg())
        return ch.digitValue();
#endif
    if (ch >= u'0' && ch <= u'9')
        return int(ch.unicode() - u'0');
    return -1;
}
 
 
 
 
qsizetype QString::toUcs4_helper(const ushort *uc, qsizetype length, uint *out)
{
    qsizetype count = 0;
 
    QStringIterator i(QStringView(uc, length));
    while (i.hasNext())
        out[count++] = i.next();
 
    return count;
}
 
QString::QString(const QChar *unicode, qsizetype size)
{
    if (!unicode) {
        d.clear();
    } else {
        if (size < 0) {
            size = 0;
            while (!unicode[size].isNull())
                ++size;
        }
        if (!size) {
            d = DataPointer::fromRawData(&_empty, 0);
        } else {
            d = DataPointer(Data::allocate(size), size);
            Q_CHECK_PTR(d.data());
            memcpy(d.data(), unicode, size * sizeof(QChar));
            d.data()[size] = '\0';
        }
    }
}
 
QString::QString(qsizetype size, QChar ch)
{
    if (size <= 0) {
        d = DataPointer::fromRawData(&_empty, 0);
    } else {
        d = DataPointer(Data::allocate(size), size);
        Q_CHECK_PTR(d.data());
        d.data()[size] = '\0';
        char16_t *i = d.data() + size;
        char16_t *b = d.data();
        const char16_t value = ch.unicode();
        while (i != b)
           *--i = value;
    }
}
 
QString::QString(qsizetype size, Qt::Initialization)
{
    if (size <= 0) {
        d = DataPointer::fromRawData(&_empty, 0);
    } else {
        d = DataPointer(Data::allocate(size), size);
        Q_CHECK_PTR(d.data());
        d.data()[size] = '\0';
    }
}
 
QString::QString(QChar ch)
{
    d = DataPointer(Data::allocate(1), 1);
    Q_CHECK_PTR(d.data());
    d.data()[0] = ch.unicode();
    d.data()[1] = '\0';
}
 
void QString::resize(qsizetype size)
{
    if (size < 0)
        size = 0;
 
    const auto capacityAtEnd = capacity() - d.freeSpaceAtBegin();
    if (d->needsDetach() || size > capacityAtEnd)
        reallocData(size, QArrayData::Grow);
    d.size = size;
    if (d->allocatedCapacity())
        d.data()[size] = 0;
}
 
void QString::resize(qsizetype size, QChar fillChar)
{
    const qsizetype oldSize = length();
    resize(size);
    const qsizetype difference = length() - oldSize;
    if (difference > 0)
        std::fill_n(d.data() + oldSize, difference, fillChar.unicode());
}
 
void QString::reallocData(qsizetype alloc, QArrayData::AllocationOption option)
{
    if (!alloc) {
        d = DataPointer::fromRawData(&_empty, 0);
        return;
    }
 
    // don't use reallocate path when reducing capacity and there's free space
    // at the beginning: might shift data pointer outside of allocated space
    const bool cannotUseReallocate = d.freeSpaceAtBegin() > 0;
 
    if (d->needsDetach() || cannotUseReallocate) {
        DataPointer dd(Data::allocate(alloc, option), qMin(alloc, d.size));
        Q_CHECK_PTR(dd.data());
        if (dd.size > 0)
            ::memcpy(dd.data(), d.data(), dd.size * sizeof(QChar));
        dd.data()[dd.size] = 0;
        d = dd;
    } else {
        d->reallocate(alloc, option);
    }
}
 
void QString::reallocGrowData(qsizetype n)
{
    if (!n)  // expected to always allocate
        n = 1;
 
    if (d->needsDetach()) {
        DataPointer dd(DataPointer::allocateGrow(d, n, QArrayData::GrowsAtEnd));
        Q_CHECK_PTR(dd.data());
        dd->copyAppend(d.data(), d.data() + d.size);
        dd.data()[dd.size] = 0;
        d = dd;
    } else {
        d->reallocate(d.constAllocatedCapacity() + n, QArrayData::Grow);
    }
}
 
QString &QString::operator=(const QString &other) noexcept
{
    d = other.d;
    return *this;
}
 
QString &QString::operator=(QLatin1String other)
{
    const qsizetype capacityAtEnd = capacity() - d.freeSpaceAtBegin();
    if (isDetached() && other.size() <= capacityAtEnd) { // assumes d->alloc == 0 -> !isDetached() (sharedNull)
        d.size = other.size();
        d.data()[other.size()] = 0;
        qt_from_latin1(d.data(), other.latin1(), other.size());
    } else {
        *this = fromLatin1(other.latin1(), other.size());
    }
    return *this;
}
 
QString &QString::operator=(QChar ch)
{
    const qsizetype capacityAtEnd = capacity() - d.freeSpaceAtBegin();
    if (isDetached() && capacityAtEnd >= 1) { // assumes d->alloc == 0 -> !isDetached() (sharedNull)
        // re-use existing capacity:
        d.data()[0] = ch.unicode();
        d.data()[1] = 0;
        d.size = 1;
    } else {
        operator=(QString(ch));
    }
    return *this;
}
 
 
 
QString &QString::insert(qsizetype i, QLatin1String str)
{
    const char *s = str.latin1();
    if (i < 0 || !s || !(*s))
        return *this;
 
    qsizetype len = str.size();
    qsizetype difference = 0;
    if (Q_UNLIKELY(i > size()))
        difference = i - size();
    d.detachAndGrow(Data::GrowsAtEnd, difference + len, nullptr, nullptr);
    Q_CHECK_PTR(d.data());
    d->copyAppend(difference, u' ');
    d.size += len;
 
    ::memmove(d.data() + i + len, d.data() + i, (d.size - i - len) * sizeof(QChar));
    qt_from_latin1(d.data() + i, s, size_t(len));
    d.data()[d.size] = u'\0';
    return *this;
}
 
QString& QString::insert(qsizetype i, const QChar *unicode, qsizetype size)
{
    if (i < 0 || size <= 0)
        return *this;
 
    const char16_t *s = reinterpret_cast<const char16_t *>(unicode);
 
    // handle this specially, as QArrayDataOps::insert() doesn't handle out of
    // bounds positions
    if (i >= d->size) {
        // In case when data points into the range or is == *this, we need to
        // defer a call to free() so that it comes after we copied the data from
        // the old memory:
        DataPointer detached{};  // construction is free
        d.detachAndGrow(Data::GrowsAtEnd, (i - d.size) + size, &s, &detached);
        Q_CHECK_PTR(d.data());
        d->copyAppend(i - d->size, u' ');
        d->copyAppend(s, s + size);
        d.data()[d.size] = u'\0';
        return *this;
    }
 
    if (!d->needsDetach() && QtPrivate::q_points_into_range(s, d.data(), d.data() + d.size))
        return insert(i, QStringView{QVarLengthArray(s, s + size)});
 
    d->insert(i, s, size);
    d.data()[d.size] = u'\0';
    return *this;
}
 
QString& QString::insert(qsizetype i, QChar ch)
{
    if (i < 0)
        i += d.size;
    return insert(i, &ch, 1);
}
 
QString &QString::append(const QString &str)
{
    if (!str.isNull()) {
        if (isNull()) {
            operator=(str);
        } else if (str.size()) {
            append(str.constData(), str.size());
        }
    }
    return *this;
}
 
QString &QString::append(const QChar *str, qsizetype len)
{
    if (str && len > 0) {
        static_assert(sizeof(QChar) == sizeof(char16_t), "Unexpected difference in sizes");
        // the following should be safe as QChar uses char16_t as underlying data
        const char16_t *char16String = reinterpret_cast<const char16_t *>(str);
        d->growAppend(char16String, char16String + len);
        d.data()[d.size] = u'\0';
    }
    return *this;
}
 
QString &QString::append(QLatin1String str)
{
    const char *s = str.latin1();
    const qsizetype len = str.size();
    if (s && len > 0) {
        d.detachAndGrow(Data::GrowsAtEnd, len, nullptr, nullptr);
        Q_CHECK_PTR(d.data());
        Q_ASSERT(len <= d->freeSpaceAtEnd());
        char16_t *i = d.data() + d.size;
        qt_from_latin1(i, s, size_t(len));
        d.size += len;
        d.data()[d.size] = '\0';
    } else if (d.isNull() && !str.isNull()) { // special case
        d = DataPointer::fromRawData(&_empty, 0);
    }
    return *this;
}
 
QString &QString::append(QChar ch)
{
    d.detachAndGrow(QArrayData::GrowsAtEnd, 1, nullptr, nullptr);
    d->copyAppend(1, ch.unicode());
    d.data()[d.size] = '\0';
    return *this;
}
 
 
 
QString &QString::remove(qsizetype pos, qsizetype len)
{
    if (pos < 0)  // count from end of string
        pos += size();
    if (size_t(pos) >= size_t(size())) {
        // range problems
    } else if (len >= size() - pos) {
        resize(pos); // truncate
    } else if (len > 0) {
        detach();
        d->erase(d.begin() + pos, len);
        d.data()[d.size] = u'\0';
    }
    return *this;
}
 
template<typename T>
static void removeStringImpl(QString &s, const T &needle, Qt::CaseSensitivity cs)
{
    const auto needleSize = needle.size();
    if (!needleSize)
        return;
 
    // avoid detach if nothing to do:
    qsizetype i = s.indexOf(needle, 0, cs);
    if (i < 0)
        return;
 
    const auto beg = s.begin(); // detaches
    auto dst = beg + i;
    auto src = beg + i + needleSize;
    const auto end = s.end();
    // loop invariant: [beg, dst[ is partial result
    //                 [src, end[ still to be checked for needles
    while (src < end) {
        const auto i = s.indexOf(needle, src - beg, cs);
        const auto hit = i == -1 ? end : beg + i;
        const auto skipped = hit - src;
        memmove(dst, src, skipped * sizeof(QChar));
        dst += skipped;
        src = hit + needleSize;
    }
    s.truncate(dst - beg);
}
 
QString &QString::remove(const QString &str, Qt::CaseSensitivity cs)
{
    const auto s = str.d.data();
    if (QtPrivate::q_points_into_range(s, d.data(), d.data() + d.size))
        removeStringImpl(*this, QStringView{QVarLengthArray(s, s + str.size())}, cs);
    else
        removeStringImpl(*this, qToStringViewIgnoringNull(str), cs);
    return *this;
}
 
QString &QString::remove(QLatin1String str, Qt::CaseSensitivity cs)
{
    removeStringImpl(*this, str, cs);
    return *this;
}
 
QString &QString::remove(QChar ch, Qt::CaseSensitivity cs)
{
    const qsizetype idx = indexOf(ch, 0, cs);
    if (idx != -1) {
        const auto first = begin(); // implicit detach()
        auto last = end();
        if (cs == Qt::CaseSensitive) {
            last = std::remove(first + idx, last, ch);
        } else {
            const QChar c = ch.toCaseFolded();
            auto caseInsensEqual = [c](QChar x) {
                return c == x.toCaseFolded();
            };
            last = std::remove_if(first + idx, last, caseInsensEqual);
        }
        resize(last - first);
    }
    return *this;
}
 
QString &QString::replace(qsizetype pos, qsizetype len, const QString &after)
{
    return replace(pos, len, after.constData(), after.length());
}
 
QString &QString::replace(qsizetype pos, qsizetype len, const QChar *unicode, qsizetype size)
{
    if (size_t(pos) > size_t(this->size()))
        return *this;
    if (len > this->size() - pos)
        len = this->size() - pos;
 
    size_t index = pos;
    replace_helper(&index, 1, len, unicode, size);
    return *this;
}
 
QString &QString::replace(qsizetype pos, qsizetype len, QChar after)
{
    return replace(pos, len, &after, 1);
}
 
QString &QString::replace(const QString &before, const QString &after, Qt::CaseSensitivity cs)
{
    return replace(before.constData(), before.size(), after.constData(), after.size(), cs);
}
 
namespace { // helpers for replace and its helper:
QChar *textCopy(const QChar *start, qsizetype len)
{
    const size_t size = len * sizeof(QChar);
    QChar *const copy = static_cast<QChar *>(::malloc(size));
    Q_CHECK_PTR(copy);
    ::memcpy(copy, start, size);
    return copy;
}
 
static bool pointsIntoRange(const QChar *ptr, const char16_t *base, qsizetype len)
{
    const QChar *const start = reinterpret_cast<const QChar *>(base);
    const std::less<const QChar *> less;
    return !less(ptr, start) && less(ptr, start + len);
}
} // end namespace
 
void QString::replace_helper(size_t *indices, qsizetype nIndices, qsizetype blen, const QChar *after, qsizetype alen)
{
    // Copy after if it lies inside our own d.b area (which we could
    // possibly invalidate via a realloc or modify by replacement).
    QChar *afterBuffer = nullptr;
    if (pointsIntoRange(after, d.data(), d.size)) // Use copy in place of vulnerable original:
        after = afterBuffer = textCopy(after, alen);
 
    QT_TRY {
        if (blen == alen) {
            // replace in place
            detach();
            for (qsizetype i = 0; i < nIndices; ++i)
                memcpy(d.data() + indices[i], after, alen * sizeof(QChar));
        } else if (alen < blen) {
            // replace from front
            detach();
            size_t to = indices[0];
            if (alen)
                memcpy(d.data()+to, after, alen*sizeof(QChar));
            to += alen;
            size_t movestart = indices[0] + blen;
            for (qsizetype i = 1; i < nIndices; ++i) {
                qsizetype msize = indices[i] - movestart;
                if (msize > 0) {
                    memmove(d.data() + to, d.data() + movestart, msize * sizeof(QChar));
                    to += msize;
                }
                if (alen) {
                    memcpy(d.data() + to, after, alen * sizeof(QChar));
                    to += alen;
                }
                movestart = indices[i] + blen;
            }
            qsizetype msize = d.size - movestart;
            if (msize > 0)
                memmove(d.data() + to, d.data() + movestart, msize * sizeof(QChar));
            resize(d.size - nIndices*(blen-alen));
        } else {
            // replace from back
            qsizetype adjust = nIndices*(alen-blen);
            qsizetype newLen = d.size + adjust;
            qsizetype moveend = d.size;
            resize(newLen);
 
            while (nIndices) {
                --nIndices;
                qsizetype movestart = indices[nIndices] + blen;
                qsizetype insertstart = indices[nIndices] + nIndices*(alen-blen);
                qsizetype moveto = insertstart + alen;
                memmove(d.data() + moveto, d.data() + movestart,
                        (moveend - movestart)*sizeof(QChar));
                memcpy(d.data() + insertstart, after, alen * sizeof(QChar));
                moveend = movestart-blen;
            }
        }
    } QT_CATCH(const std::bad_alloc &) {
        ::free(afterBuffer);
        QT_RETHROW;
    }
    ::free(afterBuffer);
}
 
QString &QString::replace(const QChar *before, qsizetype blen,
                          const QChar *after, qsizetype alen,
                          Qt::CaseSensitivity cs)
{
    if (d.size == 0) {
        if (blen)
            return *this;
    } else {
        if (cs == Qt::CaseSensitive && before == after && blen == alen)
            return *this;
    }
    if (alen == 0 && blen == 0)
        return *this;
 
    QStringMatcher matcher(before, blen, cs);
    QChar *beforeBuffer = nullptr, *afterBuffer = nullptr;
 
    qsizetype index = 0;
    while (1) {
        size_t indices[1024];
        size_t pos = 0;
        while (pos < 1024) {
            index = matcher.indexIn(*this, index);
            if (index == -1)
                break;
            indices[pos++] = index;
            if (blen) // Step over before:
                index += blen;
            else // Only count one instance of empty between any two characters:
                index++;
        }
        if (!pos) // Nothing to replace
            break;
 
        if (Q_UNLIKELY(index != -1)) {
            /*
              We're about to change data, that before and after might point
              into, and we'll need that data for our next batch of indices.
            */
            if (!afterBuffer && pointsIntoRange(after, d.data(), d.size))
                after = afterBuffer = textCopy(after, alen);
 
            if (!beforeBuffer && pointsIntoRange(before, d.data(), d.size)) {
                beforeBuffer = textCopy(before, blen);
                matcher = QStringMatcher(beforeBuffer, blen, cs);
            }
        }
 
        replace_helper(indices, pos, blen, after, alen);
 
        if (Q_LIKELY(index == -1)) // Nothing left to replace
            break;
        // The call to replace_helper just moved what index points at:
        index += pos*(alen-blen);
    }
    ::free(afterBuffer);
    ::free(beforeBuffer);
 
    return *this;
}
 
QString& QString::replace(QChar ch, const QString &after, Qt::CaseSensitivity cs)
{
    if (after.size() == 0)
        return remove(ch, cs);
 
    if (after.size() == 1)
        return replace(ch, after.front(), cs);
 
    if (size() == 0)
        return *this;
 
    char16_t cc = (cs == Qt::CaseSensitive ? ch.unicode() : ch.toCaseFolded().unicode());
 
    qsizetype index = 0;
    while (1) {
        size_t indices[1024];
        size_t pos = 0;
        if (cs == Qt::CaseSensitive) {
            while (pos < 1024 && index < size()) {
                if (d.data()[index] == cc)
                    indices[pos++] = index;
                index++;
            }
        } else {
            while (pos < 1024 && index < size()) {
                if (QChar::toCaseFolded(d.data()[index]) == cc)
                    indices[pos++] = index;
                index++;
            }
        }
        if (!pos) // Nothing to replace
            break;
 
        replace_helper(indices, pos, 1, after.constData(), after.size());
 
        if (Q_LIKELY(index == size())) // Nothing left to replace
            break;
        // The call to replace_helper just moved what index points at:
        index += pos*(after.size() - 1);
    }
    return *this;
}
 
QString& QString::replace(QChar before, QChar after, Qt::CaseSensitivity cs)
{
    if (d.size) {
        const qsizetype idx = indexOf(before, 0, cs);
        if (idx != -1) {
            detach();
            const char16_t a = after.unicode();
            char16_t *i = d.data();
            char16_t *const e = i + d.size;
            i += idx;
            *i = a;
            if (cs == Qt::CaseSensitive) {
                const char16_t b = before.unicode();
                while (++i != e) {
                    if (*i == b)
                        *i = a;
                }
            } else {
                const char16_t b = foldCase(before.unicode());
                while (++i != e) {
                    if (foldCase(*i) == b)
                        *i = a;
                }
            }
        }
    }
    return *this;
}
 
QString &QString::replace(QLatin1String before, QLatin1String after, Qt::CaseSensitivity cs)
{
    qsizetype alen = after.size();
    qsizetype blen = before.size();
    QVarLengthArray<char16_t> a(alen);
    QVarLengthArray<char16_t> b(blen);
    qt_from_latin1(a.data(), after.latin1(), alen);
    qt_from_latin1(b.data(), before.latin1(), blen);
    return replace((const QChar *)b.data(), blen, (const QChar *)a.data(), alen, cs);
}
 
QString &QString::replace(QLatin1String before, const QString &after, Qt::CaseSensitivity cs)
{
    qsizetype blen = before.size();
    QVarLengthArray<char16_t> b(blen);
    qt_from_latin1(b.data(), before.latin1(), blen);
    return replace((const QChar *)b.data(), blen, after.constData(), after.d.size, cs);
}
 
QString &QString::replace(const QString &before, QLatin1String after, Qt::CaseSensitivity cs)
{
    qsizetype alen = after.size();
    QVarLengthArray<char16_t> a(alen);
    qt_from_latin1(a.data(), after.latin1(), alen);
    return replace(before.constData(), before.d.size, (const QChar *)a.data(), alen, cs);
}
 
QString &QString::replace(QChar c, QLatin1String after, Qt::CaseSensitivity cs)
{
    qsizetype alen = after.size();
    QVarLengthArray<char16_t> a(alen);
    qt_from_latin1(a.data(), after.latin1(), alen);
    return replace(&c, 1, (const QChar *)a.data(), alen, cs);
}
 
 
#if QT_STRINGVIEW_LEVEL < 2
qsizetype QString::indexOf(const QString &str, qsizetype from, Qt::CaseSensitivity cs) const
{
    return QtPrivate::findString(QStringView(unicode(), length()), from, QStringView(str.unicode(), str.length()), cs);
}
#endif  // QT_STRINGVIEW_LEVEL < 2
 
qsizetype QString::indexOf(QLatin1String str, qsizetype from, Qt::CaseSensitivity cs) const
{
    return QtPrivate::findString(QStringView(unicode(), size()), from, str, cs);
}
 
qsizetype QString::indexOf(QChar ch, qsizetype from, Qt::CaseSensitivity cs) const
{
    return qFindChar(QStringView(unicode(), length()), ch, from, cs);
}
 
#if QT_STRINGVIEW_LEVEL < 2
qsizetype QString::lastIndexOf(const QString &str, qsizetype from, Qt::CaseSensitivity cs) const
{
    return QtPrivate::lastIndexOf(QStringView(*this), from, str, cs);
}
 
#endif // QT_STRINGVIEW_LEVEL < 2
 
qsizetype QString::lastIndexOf(QLatin1String str, qsizetype from, Qt::CaseSensitivity cs) const
{
    return QtPrivate::lastIndexOf(*this, from, str, cs);
}
 
qsizetype QString::lastIndexOf(QChar ch, qsizetype from, Qt::CaseSensitivity cs) const
{
    return qLastIndexOf(QStringView(*this), ch, from, cs);
}
 
#if QT_CONFIG(regularexpression)
struct QStringCapture
{
    qsizetype pos;
    qsizetype len;
    int no;
};
Q_DECLARE_TYPEINFO(QStringCapture, Q_PRIMITIVE_TYPE);
 
QString &QString::replace(const QRegularExpression &re, const QString &after)
{
    if (!re.isValid()) {
        qWarning("QString::replace: invalid QRegularExpression object");
        return *this;
    }
 
    const QString copy(*this);
    QRegularExpressionMatchIterator iterator = re.globalMatch(copy);
    if (!iterator.hasNext()) // no matches at all
        return *this;
 
    reallocData(d.size, QArrayData::KeepSize);
 
    qsizetype numCaptures = re.captureCount();
 
    // 1. build the backreferences list, holding where the backreferences
    // are in the replacement string
    QList<QStringCapture> backReferences;
    const qsizetype al = after.length();
    const QChar *ac = after.unicode();
 
    for (qsizetype i = 0; i < al - 1; i++) {
        if (ac[i] == QLatin1Char('\\')) {
            int no = ac[i + 1].digitValue();
            if (no > 0 && no <= numCaptures) {
                QStringCapture backReference;
                backReference.pos = i;
                backReference.len = 2;
 
                if (i < al - 2) {
                    int secondDigit = ac[i + 2].digitValue();
                    if (secondDigit != -1 && ((no * 10) + secondDigit) <= numCaptures) {
                        no = (no * 10) + secondDigit;
                        ++backReference.len;
                    }
                }
 
                backReference.no = no;
                backReferences.append(backReference);
            }
        }
    }
 
    // 2. iterate on the matches. For every match, copy in chunks
    // - the part before the match
    // - the after string, with the proper replacements for the backreferences
 
    qsizetype newLength = 0; // length of the new string, with all the replacements
    qsizetype lastEnd = 0;
    QList<QStringView> chunks;
    const QStringView copyView{ copy }, afterView{ after };
    while (iterator.hasNext()) {
        QRegularExpressionMatch match = iterator.next();
        qsizetype len;
        // add the part before the match
        len = match.capturedStart() - lastEnd;
        if (len > 0) {
            chunks << copyView.mid(lastEnd, len);
            newLength += len;
        }
 
        lastEnd = 0;
        // add the after string, with replacements for the backreferences
        for (const QStringCapture &backReference : qAsConst(backReferences)) {
            // part of "after" before the backreference
            len = backReference.pos - lastEnd;
            if (len > 0) {
                chunks << afterView.mid(lastEnd, len);
                newLength += len;
            }
 
            // backreference itself
            len = match.capturedLength(backReference.no);
            if (len > 0) {
                chunks << copyView.mid(match.capturedStart(backReference.no), len);
                newLength += len;
            }
 
            lastEnd = backReference.pos + backReference.len;
        }
 
        // add the last part of the after string
        len = afterView.length() - lastEnd;
        if (len > 0) {
            chunks << afterView.mid(lastEnd, len);
            newLength += len;
        }
 
        lastEnd = match.capturedEnd();
    }
 
    // 3. trailing string after the last match
    if (copyView.length() > lastEnd) {
        chunks << copyView.mid(lastEnd);
        newLength += copyView.length() - lastEnd;
    }
 
    // 4. assemble the chunks together
    resize(newLength);
    qsizetype i = 0;
    QChar *uc = data();
    for (const QStringView &chunk : qAsConst(chunks)) {
        qsizetype len = chunk.length();
        memcpy(uc + i, chunk.constData(), len * sizeof(QChar));
        i += len;
    }
 
    return *this;
}
#endif // QT_CONFIG(regularexpression)
 
qsizetype QString::count(const QString &str, Qt::CaseSensitivity cs) const
{
    return QtPrivate::count(QStringView(unicode(), size()), QStringView(str.unicode(), str.size()), cs);
}
 
qsizetype QString::count(QChar ch, Qt::CaseSensitivity cs) const
{
    return QtPrivate::count(QStringView(unicode(), size()), ch, cs);
}
 
qsizetype QString::count(QStringView str, Qt::CaseSensitivity cs) const
{
    return QtPrivate::count(*this, str, cs);
}
 
#if QT_STRINGVIEW_LEVEL < 2
#endif // QT_STRINGVIEW_LEVEL < 2
 
#if QT_CONFIG(regularexpression)
qsizetype QString::indexOf(const QRegularExpression &re, qsizetype from, QRegularExpressionMatch *rmatch) const
{
    return QtPrivate::indexOf(QStringView(*this), re, from, rmatch);
}
 
qsizetype QString::lastIndexOf(const QRegularExpression &re, qsizetype from, QRegularExpressionMatch *rmatch) const
{
    return QtPrivate::lastIndexOf(QStringView(*this), re, from, rmatch);
}
 
bool QString::contains(const QRegularExpression &re, QRegularExpressionMatch *rmatch) const
{
    return QtPrivate::contains(QStringView(*this), re, rmatch);
}
 
qsizetype QString::count(const QRegularExpression &re) const
{
    return QtPrivate::count(QStringView(*this), re);
}
#endif // QT_CONFIG(regularexpression)
 
QString QString::section(const QString &sep, qsizetype start, qsizetype end, SectionFlags flags) const
{
    const QList<QStringView> sections = QStringView{ *this }.split(
            sep, Qt::KeepEmptyParts, (flags & SectionCaseInsensitiveSeps) ? Qt::CaseInsensitive : Qt::CaseSensitive);
    const qsizetype sectionsSize = sections.size();
    if (!(flags & SectionSkipEmpty)) {
        if (start < 0)
            start += sectionsSize;
        if (end < 0)
            end += sectionsSize;
    } else {
        qsizetype skip = 0;
        for (qsizetype k = 0; k < sectionsSize; ++k) {
            if (sections.at(k).isEmpty())
                skip++;
        }
        if (start < 0)
            start += sectionsSize - skip;
        if (end < 0)
            end += sectionsSize - skip;
    }
    if (start >= sectionsSize || end < 0 || start > end)
        return QString();
 
    QString ret;
    qsizetype first_i = start, last_i = end;
    for (qsizetype x = 0, i = 0; x <= end && i < sectionsSize; ++i) {
        const QStringView &section = sections.at(i);
        const bool empty = section.isEmpty();
        if (x >= start) {
            if (x == start)
                first_i = i;
            if (x == end)
                last_i = i;
            if (x > start && i > 0)
                ret += sep;
            ret += section;
        }
        if (!empty || !(flags & SectionSkipEmpty))
            x++;
    }
    if ((flags & SectionIncludeLeadingSep) && first_i > 0)
        ret.prepend(sep);
    if ((flags & SectionIncludeTrailingSep) && last_i < sectionsSize - 1)
        ret += sep;
    return ret;
}
 
#if QT_CONFIG(regularexpression)
class qt_section_chunk {
public:
    qt_section_chunk() {}
    qt_section_chunk(qsizetype l, QStringView s) : length(l), string(std::move(s)) {}
    qsizetype length;
    QStringView string;
};
Q_DECLARE_TYPEINFO(qt_section_chunk, Q_RELOCATABLE_TYPE);
 
static QString extractSections(const QList<qt_section_chunk> &sections, qsizetype start, qsizetype end,
                               QString::SectionFlags flags)
{
    const qsizetype sectionsSize = sections.size();
 
    if (!(flags & QString::SectionSkipEmpty)) {
        if (start < 0)
            start += sectionsSize;
        if (end < 0)
            end += sectionsSize;
    } else {
        qsizetype skip = 0;
        for (qsizetype k = 0; k < sectionsSize; ++k) {
            const qt_section_chunk &section = sections.at(k);
            if (section.length == section.string.length())
                skip++;
        }
        if (start < 0)
            start += sectionsSize - skip;
        if (end < 0)
            end += sectionsSize - skip;
    }
    if (start >= sectionsSize || end < 0 || start > end)
        return QString();
 
    QString ret;
    qsizetype x = 0;
    qsizetype first_i = start, last_i = end;
    for (qsizetype i = 0; x <= end && i < sectionsSize; ++i) {
        const qt_section_chunk &section = sections.at(i);
        const bool empty = (section.length == section.string.length());
        if (x >= start) {
            if (x == start)
                first_i = i;
            if (x == end)
                last_i = i;
            if (x != start)
                ret += section.string;
            else
                ret += section.string.mid(section.length);
        }
        if (!empty || !(flags & QString::SectionSkipEmpty))
            x++;
    }
 
    if ((flags & QString::SectionIncludeLeadingSep) && first_i >= 0) {
        const qt_section_chunk &section = sections.at(first_i);
        ret.prepend(section.string.left(section.length));
    }
 
    if ((flags & QString::SectionIncludeTrailingSep)
        && last_i < sectionsSize - 1) {
        const qt_section_chunk &section = sections.at(last_i+1);
        ret += section.string.left(section.length);
    }
 
    return ret;
}
 
QString QString::section(const QRegularExpression &re, qsizetype start, qsizetype end, SectionFlags flags) const
{
    if (!re.isValid()) {
        qWarning("QString::section: invalid QRegularExpression object");
        return QString();
    }
 
    const QChar *uc = unicode();
    if (!uc)
        return QString();
 
    QRegularExpression sep(re);
    if (flags & SectionCaseInsensitiveSeps)
        sep.setPatternOptions(sep.patternOptions() | QRegularExpression::CaseInsensitiveOption);
 
    QList<qt_section_chunk> sections;
    qsizetype n = length(), m = 0, last_m = 0, last_len = 0;
    QRegularExpressionMatchIterator iterator = sep.globalMatch(*this);
    while (iterator.hasNext()) {
        QRegularExpressionMatch match = iterator.next();
        m = match.capturedStart();
        sections.append(qt_section_chunk(last_len, QStringView{ *this }.sliced(last_m, m - last_m)));
        last_m = m;
        last_len = match.capturedLength();
    }
    sections.append(qt_section_chunk(last_len, QStringView{ *this }.sliced(last_m, n - last_m)));
 
    return extractSections(sections, start, end, flags);
}
#endif // QT_CONFIG(regularexpression)
 
QString QString::left(qsizetype n)  const
{
    if (size_t(n) >= size_t(size()))
        return *this;
    return QString((const QChar*) d.data(), n);
}
 
QString QString::right(qsizetype n) const
{
    if (size_t(n) >= size_t(size()))
        return *this;
    return QString(constData() + size() - n, n);
}
 
QString QString::mid(qsizetype position, qsizetype n) const
{
    qsizetype p = position;
    qsizetype l = n;
    using namespace QtPrivate;
    switch (QContainerImplHelper::mid(size(), &p, &l)) {
    case QContainerImplHelper::Null:
        return QString();
    case QContainerImplHelper::Empty:
        return QString(DataPointer::fromRawData(&_empty, 0));
    case QContainerImplHelper::Full:
        return *this;
    case QContainerImplHelper::Subset:
        return QString(constData() + p, l);
    }
    Q_UNREACHABLE();
    return QString();
}
 
#if QT_STRINGVIEW_LEVEL < 2
bool QString::startsWith(const QString& s, Qt::CaseSensitivity cs) const
{
    return qt_starts_with(*this, s, cs);
}
#endif
 
bool QString::startsWith(QLatin1String s, Qt::CaseSensitivity cs) const
{
    return qt_starts_with(*this, s, cs);
}
 
bool QString::startsWith(QChar c, Qt::CaseSensitivity cs) const
{
    return qt_starts_with(*this, c, cs);
}
 
#if QT_STRINGVIEW_LEVEL < 2
bool QString::endsWith(const QString &s, Qt::CaseSensitivity cs) const
{
    return qt_ends_with(*this, s, cs);
}
#endif // QT_STRINGVIEW_LEVEL < 2
 
bool QString::endsWith(QLatin1String s, Qt::CaseSensitivity cs) const
{
    return qt_ends_with(*this, s, cs);
}
 
bool QString::endsWith(QChar c, Qt::CaseSensitivity cs) const
{
    return qt_ends_with(*this, c, cs);
}
 
bool QString::isUpper() const
{
    QStringIterator it(*this);
 
    while (it.hasNext()) {
        const char32_t uc = it.next();
        if (qGetProp(uc)->cases[QUnicodeTables::UpperCase].diff)
            return false;
    }
 
    return true;
}
 
bool QString::isLower() const
{
    QStringIterator it(*this);
 
    while (it.hasNext()) {
        const char32_t uc = it.next();
        if (qGetProp(uc)->cases[QUnicodeTables::LowerCase].diff)
            return false;
    }
 
    return true;
}
 
static QByteArray qt_convert_to_latin1(QStringView string);
 
QByteArray QString::toLatin1_helper(const QString &string)
{
    return qt_convert_to_latin1(string);
}
 
QString QtPrivate::convertToQString(QAnyStringView string)
{
    return string.visit([] (auto string) { return string.toString(); });
}
 
QByteArray QtPrivate::convertToLatin1(QStringView string)
{
    return qt_convert_to_latin1(string);
}
 
static QByteArray qt_convert_to_latin1(QStringView string)
{
    if (Q_UNLIKELY(string.isNull()))
        return QByteArray();
 
    QByteArray ba(string.length(), Qt::Uninitialized);
 
    // since we own the only copy, we're going to const_cast the constData;
    // that avoids an unnecessary call to detach() and expansion code that will never get used
    qt_to_latin1(reinterpret_cast<uchar *>(const_cast<char *>(ba.constData())),
                 string.utf16(), string.size());
    return ba;
}
 
QByteArray QString::toLatin1_helper_inplace(QString &s)
{
    if (!s.isDetached())
        return qt_convert_to_latin1(s);
 
    // We can return our own buffer to the caller.
    // Conversion to Latin-1 always shrinks the buffer by half.
    const char16_t *data = s.d.data();
    qsizetype length = s.d.size;
 
    // Move the d pointer over to the bytearray.
    // Kids, avert your eyes. Don't try this at home.
 
    // this relies on the fact that we use QArrayData for everything behind the scenes which has the same layout
    static_assert(sizeof(QByteArray::DataPointer) == sizeof(QString::DataPointer), "sizes have to be equal");
    QByteArray::DataPointer ba_d(reinterpret_cast<QByteArray::Data *>(s.d.d_ptr()), reinterpret_cast<char *>(s.d.data()), length);
    ba_d.ref();
    s.clear();
 
    char *ddata = ba_d.data();
 
    // multiply the allocated capacity by sizeof(char16_t)
    ba_d.d_ptr()->alloc *= sizeof(char16_t);
 
    // do the in-place conversion
    qt_to_latin1(reinterpret_cast<uchar *>(ddata), data, length);
    ddata[length] = '\0';
    return QByteArray(ba_d);
}
 
static QByteArray qt_convert_to_local_8bit(QStringView string);
 
QByteArray QString::toLocal8Bit_helper(const QChar *data, qsizetype size)
{
    return qt_convert_to_local_8bit(QStringView(data, size));
}
 
static QByteArray qt_convert_to_local_8bit(QStringView string)
{
    if (string.isNull())
        return QByteArray();
    QStringEncoder fromUtf16(QStringEncoder::System, QStringEncoder::Flag::Stateless);
    return fromUtf16(string);
}
 
QByteArray QtPrivate::convertToLocal8Bit(QStringView string)
{
    return qt_convert_to_local_8bit(string);
}
 
static QByteArray qt_convert_to_utf8(QStringView str);
 
QByteArray QString::toUtf8_helper(const QString &str)
{
    return qt_convert_to_utf8(str);
}
 
static QByteArray qt_convert_to_utf8(QStringView str)
{
    if (str.isNull())
        return QByteArray();
 
    return QUtf8::convertFromUnicode(str);
}
 
QByteArray QtPrivate::convertToUtf8(QStringView string)
{
    return qt_convert_to_utf8(string);
}
 
static QList<uint> qt_convert_to_ucs4(QStringView string);
 
QList<uint> QString::toUcs4() const
{
    return qt_convert_to_ucs4(*this);
}
 
static QList<uint> qt_convert_to_ucs4(QStringView string)
{
    QList<uint> v(string.length());
    uint *a = const_cast<uint*>(v.constData());
    QStringIterator it(string);
    while (it.hasNext())
        *a++ = it.next();
    v.resize(a - v.constData());
    return v;
}
 
QList<uint> QtPrivate::convertToUcs4(QStringView string)
{
    return qt_convert_to_ucs4(string);
}
 
QString QString::fromLatin1(QByteArrayView ba)
{
    DataPointer d;
    if (!ba.data()) {
        // nothing to do
    } else if (ba.size() == 0) {
        d = DataPointer::fromRawData(&_empty, 0);
    } else {
        d = DataPointer(Data::allocate(ba.size()), ba.size());
        Q_CHECK_PTR(d.data());
        d.data()[ba.size()] = '\0';
        char16_t *dst = d.data();
 
        qt_from_latin1(dst, ba.data(), size_t(ba.size()));
    }
    return QString(std::move(d));
}
 
QString QString::fromLocal8Bit(QByteArrayView ba)
{
    if (ba.isNull())
        return QString();
    if (ba.isEmpty())
        return QString(DataPointer::fromRawData(&_empty, 0));
    QStringDecoder toUtf16(QStringDecoder::System, QStringDecoder::Flag::Stateless);
    return toUtf16(ba);
}
 
QString QString::fromUtf8(QByteArrayView ba)
{
    if (ba.isNull())
        return QString();
    if (ba.isEmpty())
        return QString(DataPointer::fromRawData(&_empty, 0));
    return QUtf8::convertToUnicode(ba);
}
 
QString QString::fromUtf16(const char16_t *unicode, qsizetype size)
{
    if (!unicode)
        return QString();
    if (size < 0)
        size = QtPrivate::qustrlen(unicode);
    QStringDecoder toUtf16(QStringDecoder::Utf16, QStringDecoder::Flag::Stateless);
    return toUtf16(QByteArrayView(reinterpret_cast<const char *>(unicode), size * 2));
}
 
QString QString::fromUcs4(const char32_t *unicode, qsizetype size)
{
    if (!unicode)
        return QString();
    if (size < 0) {
        size = 0;
        while (unicode[size] != 0)
            ++size;
    }
    QStringDecoder toUtf16(QStringDecoder::Utf32, QStringDecoder::Flag::Stateless);
    return toUtf16(QByteArrayView(reinterpret_cast<const char *>(unicode), size * 4));
}
 
 
QString& QString::setUnicode(const QChar *unicode, qsizetype size)
{
     resize(size);
     if (unicode && size)
         memcpy(d.data(), unicode, size * sizeof(QChar));
     return *this;
}
 
QString QString::simplified_helper(const QString &str)
{
    return QStringAlgorithms<const QString>::simplified_helper(str);
}
 
QString QString::simplified_helper(QString &str)
{
    return QStringAlgorithms<QString>::simplified_helper(str);
}
 
namespace {
    template <typename StringView>
    StringView qt_trimmed(StringView s) noexcept
    {
        auto begin = s.begin();
        auto end = s.end();
        QStringAlgorithms<const StringView>::trimmed_helper_positions(begin, end);
        return StringView{begin, end};
    }
}
 
QStringView QtPrivate::trimmed(QStringView s) noexcept
{
    return qt_trimmed(s);
}
 
QLatin1String QtPrivate::trimmed(QLatin1String s) noexcept
{
    return qt_trimmed(s);
}
 
QString QString::trimmed_helper(const QString &str)
{
    return QStringAlgorithms<const QString>::trimmed_helper(str);
}
 
QString QString::trimmed_helper(QString &str)
{
    return QStringAlgorithms<QString>::trimmed_helper(str);
}
 
void QString::truncate(qsizetype pos)
{
    if (pos < size())
        resize(pos);
}
 
 
void QString::chop(qsizetype n)
{
    if (n > 0)
        resize(d.size - n);
}
 
QString& QString::fill(QChar ch, qsizetype size)
{
    resize(size < 0 ? d.size : size);
    if (d.size) {
        QChar *i = (QChar*)d.data() + d.size;
        QChar *b = (QChar*)d.data();
        while (i != b)
           *--i = ch;
    }
    return *this;
}
 
#if QT_STRINGVIEW_LEVEL < 2
int QString::compare(const QString &other, Qt::CaseSensitivity cs) const noexcept
{
    return QtPrivate::compareStrings(*this, other, cs);
}
#endif
 
int QString::compare_helper(const QChar *data1, qsizetype length1, const QChar *data2, qsizetype length2,
                            Qt::CaseSensitivity cs) noexcept
{
    Q_ASSERT(length1 >= 0);
    Q_ASSERT(length2 >= 0);
    Q_ASSERT(data1 || length1 == 0);
    Q_ASSERT(data2 || length2 == 0);
    return QtPrivate::compareStrings(QStringView(data1, length1), QStringView(data2, length2), cs);
}
 
int QString::compare(QLatin1String other, Qt::CaseSensitivity cs) const noexcept
{
    return QtPrivate::compareStrings(*this, other, cs);
}
 
int QString::compare_helper(const QChar *data1, qsizetype length1, const char *data2, qsizetype length2,
                            Qt::CaseSensitivity cs) noexcept
{
    Q_ASSERT(length1 >= 0);
    Q_ASSERT(data1 || length1 == 0);
    if (!data2)
        return length1;
    if (Q_UNLIKELY(length2 < 0))
        length2 = qsizetype(strlen(data2));
    return QtPrivate::compareStrings(QStringView(data1, length1),
                                     QUtf8StringView(data2, length2), cs);
}
 
int QLatin1String::compare_helper(const QChar *data1, qsizetype length1, QLatin1String s2,
                                  Qt::CaseSensitivity cs) noexcept
{
    Q_ASSERT(length1 >= 0);
    Q_ASSERT(data1 || length1 == 0);
    return QtPrivate::compareStrings(QStringView(data1, length1), s2, cs);
}
 
#if !defined(CSTR_LESS_THAN)
#define CSTR_LESS_THAN    1
#define CSTR_EQUAL        2
#define CSTR_GREATER_THAN 3
#endif
 
int QString::localeAwareCompare(const QString &other) const
{
    return localeAwareCompare_helper(constData(), length(), other.constData(), other.length());
}
 
int QString::localeAwareCompare_helper(const QChar *data1, qsizetype length1,
                                       const QChar *data2, qsizetype length2)
{
    Q_ASSERT(length1 >= 0);
    Q_ASSERT(data1 || length1 == 0);
    Q_ASSERT(length2 >= 0);
    Q_ASSERT(data2 || length2 == 0);
 
    // do the right thing for null and empty
    if (length1 == 0 || length2 == 0)
        return QtPrivate::compareStrings(QStringView(data1, length1), QStringView(data2, length2),
                               Qt::CaseSensitive);
 
#if QT_CONFIG(icu)
    return QCollator::defaultCompare(QStringView(data1, length1), QStringView(data2, length2));
#else
    const QString lhs = QString::fromRawData(data1, length1).normalized(QString::NormalizationForm_C);
    const QString rhs = QString::fromRawData(data2, length2).normalized(QString::NormalizationForm_C);
#  if defined(Q_OS_WIN)
    int res = CompareStringEx(LOCALE_NAME_USER_DEFAULT, 0, (LPWSTR)lhs.constData(), lhs.length(), (LPWSTR)rhs.constData(), rhs.length(), NULL, NULL, 0);
 
    switch (res) {
    case CSTR_LESS_THAN:
        return -1;
    case CSTR_GREATER_THAN:
        return 1;
    default:
        return 0;
    }
#  elif defined (Q_OS_DARWIN)
    // Use CFStringCompare for comparing strings on Mac. This makes Qt order
    // strings the same way as native applications do, and also respects
    // the "Order for sorted lists" setting in the International preferences
    // panel.
    const CFStringRef thisString =
        CFStringCreateWithCharactersNoCopy(kCFAllocatorDefault,
            reinterpret_cast<const UniChar *>(lhs.constData()), lhs.length(), kCFAllocatorNull);
    const CFStringRef otherString =
        CFStringCreateWithCharactersNoCopy(kCFAllocatorDefault,
            reinterpret_cast<const UniChar *>(rhs.constData()), rhs.length(), kCFAllocatorNull);
 
    const int result = CFStringCompare(thisString, otherString, kCFCompareLocalized);
    CFRelease(thisString);
    CFRelease(otherString);
    return result;
#  elif defined(Q_OS_UNIX)
    // declared in <string.h> (no better than QtPrivate::compareStrings() on Android, sadly)
    return strcoll(lhs.toLocal8Bit().constData(), rhs.toLocal8Bit().constData());
#  else
#     error "This case shouldn't happen"
    return QtPrivate::compareStrings(lhs, rhs, Qt::CaseSensitive);
#  endif
#endif // !QT_CONFIG(icu)
}
 
 
const ushort *QString::utf16() const
{
    if (!d->isMutable()) {
        // ensure '\0'-termination for ::fromRawData strings
        const_cast<QString*>(this)->reallocData(d.size, QArrayData::KeepSize);
    }
    return reinterpret_cast<const ushort *>(d.data());
}
 
QString QString::leftJustified(qsizetype width, QChar fill, bool truncate) const
{
    QString result;
    qsizetype len = length();
    qsizetype padlen = width - len;
    if (padlen > 0) {
        result.resize(len+padlen);
        if (len)
            memcpy(result.d.data(), d.data(), sizeof(QChar)*len);
        QChar *uc = (QChar*)result.d.data() + len;
        while (padlen--)
           * uc++ = fill;
    } else {
        if (truncate)
            result = left(width);
        else
            result = *this;
    }
    return result;
}
 
QString QString::rightJustified(qsizetype width, QChar fill, bool truncate) const
{
    QString result;
    qsizetype len = length();
    qsizetype padlen = width - len;
    if (padlen > 0) {
        result.resize(len+padlen);
        QChar *uc = (QChar*)result.d.data();
        while (padlen--)
           * uc++ = fill;
        if (len)
          memcpy(static_cast<void *>(uc), static_cast<const void *>(d.data()), sizeof(QChar)*len);
    } else {
        if (truncate)
            result = left(width);
        else
            result = *this;
    }
    return result;
}
 
namespace QUnicodeTables {
/*
    \internal
    Converts the \a str string starting from the position pointed to by the \a
    it iterator, using the Unicode case traits \c Traits, and returns the
    result. The input string must not be empty (the convertCase function below
    guarantees that).
 
    The string type \c{T} is also a template and is either \c{const QString} or
    \c{QString}. This function can do both copy-conversion and in-place
    conversion depending on the state of the \a str parameter:
    \list
       \li \c{T} is \c{const QString}: copy-convert
       \li \c{T} is \c{QString} and its refcount != 1: copy-convert
       \li \c{T} is \c{QString} and its refcount == 1: in-place convert
    \endlist
 
    In copy-convert mode, the local variable \c{s} is detached from the input
    \a str. In the in-place convert mode, \a str is in moved-from state and
    \c{s} contains the only copy of the string, without reallocation (thus,
    \a it is still valid).
 
    There is one pathological case left: when the in-place conversion needs to
    reallocate memory to grow the buffer. In that case, we need to adjust the \a
    it pointer.
 */
template <typename T>
Q_NEVER_INLINE
static QString detachAndConvertCase(T &str, QStringIterator it, QUnicodeTables::Case which)
{
    Q_ASSERT(!str.isEmpty());
    QString s = std::move(str);         // will copy if T is const QString
    QChar *pp = s.begin() + it.index(); // will detach if necessary
 
    do {
        const auto folded = fullConvertCase(it.next(), which);
        if (Q_UNLIKELY(folded.size() > 1)) {
            if (folded.chars[0] == *pp && folded.size() == 2) {
                // special case: only second actually changed (e.g. surrogate pairs),
                // avoid slow case
                ++pp;
                *pp++ = folded.chars[1];
            } else {
                // slow path: the string is growing
                qsizetype inpos = it.index() - 1;
                qsizetype outpos = pp - s.constBegin();
 
                s.replace(outpos, 1, reinterpret_cast<const QChar *>(folded.data()), folded.size());
                pp = const_cast<QChar *>(s.constBegin()) + outpos + folded.size();
 
                // Adjust the input iterator if we are performing an in-place conversion
                if constexpr (!std::is_const<T>::value)
                    it = QStringIterator(s.constBegin(), inpos + folded.size(), s.constEnd());
            }
        } else {
            *pp++ = folded.chars[0];
        }
    } while (it.hasNext());
 
    return s;
}
 
template <typename T>
static QString convertCase(T &str, QUnicodeTables::Case which)
{
    const QChar *p = str.constBegin();
    const QChar *e = p + str.size();
 
    // this avoids out of bounds check in the loop
    while (e != p && e[-1].isHighSurrogate())
        --e;
 
    QStringIterator it(p, e);
    while (it.hasNext()) {
        const char32_t uc = it.next();
        if (qGetProp(uc)->cases[which].diff) {
            it.recede();
            return detachAndConvertCase(str, it, which);
        }
    }
    return std::move(str);
}
} // namespace QUnicodeTables
 
QString QString::toLower_helper(const QString &str)
{
    return QUnicodeTables::convertCase(str, QUnicodeTables::LowerCase);
}
 
QString QString::toLower_helper(QString &str)
{
    return QUnicodeTables::convertCase(str, QUnicodeTables::LowerCase);
}
 
QString QString::toCaseFolded_helper(const QString &str)
{
    return QUnicodeTables::convertCase(str, QUnicodeTables::CaseFold);
}
 
QString QString::toCaseFolded_helper(QString &str)
{
    return QUnicodeTables::convertCase(str, QUnicodeTables::CaseFold);
}
 
QString QString::toUpper_helper(const QString &str)
{
    return QUnicodeTables::convertCase(str, QUnicodeTables::UpperCase);
}
 
QString QString::toUpper_helper(QString &str)
{
    return QUnicodeTables::convertCase(str, QUnicodeTables::UpperCase);
}
 
QString QString::asprintf(const char *cformat, ...)
{
    va_list ap;
    va_start(ap, cformat);
    const QString s = vasprintf(cformat, ap);
    va_end(ap);
    return s;
}
 
static void append_utf8(QString &qs, const char *cs, int len)
{
    const int oldSize = qs.size();
    qs.resize(oldSize + len);
    const QChar *newEnd = QUtf8::convertToUnicode(qs.data() + oldSize, QByteArrayView(cs, len));
    qs.resize(newEnd - qs.constData());
}
 
static uint parse_flag_characters(const char * &c) noexcept
{
    uint flags = QLocaleData::ZeroPadExponent;
    while (true) {
        switch (*c) {
        case '#':
            flags |= QLocaleData::ShowBase | QLocaleData::AddTrailingZeroes
                    | QLocaleData::ForcePoint;
            break;
        case '0': flags |= QLocaleData::ZeroPadded; break;
        case '-': flags |= QLocaleData::LeftAdjusted; break;
        case ' ': flags |= QLocaleData::BlankBeforePositive; break;
        case '+': flags |= QLocaleData::AlwaysShowSign; break;
        case '\'': flags |= QLocaleData::GroupDigits; break;
        default: return flags;
        }
        ++c;
    }
}
 
static int parse_field_width(const char *&c, qsizetype size)
{
    Q_ASSERT(qIsDigit(*c));
    const char *const stop = c + size;
 
    // can't be negative - started with a digit
    // contains at least one digit
    const char *endp;
    bool ok;
    const qulonglong result = qstrntoull(c, size, &endp, 10, &ok);
    c = endp;
    // preserve Qt 5.5 behavior of consuming all digits, no matter how many
    while (c < stop && qIsDigit(*c))
        ++c;
    return ok && result < qulonglong(std::numeric_limits<int>::max()) ? int(result) : 0;
}
 
enum LengthMod { lm_none, lm_hh, lm_h, lm_l, lm_ll, lm_L, lm_j, lm_z, lm_t };
 
static inline bool can_consume(const char * &c, char ch) noexcept
{
    if (*c == ch) {
        ++c;
        return true;
    }
    return false;
}
 
static LengthMod parse_length_modifier(const char * &c) noexcept
{
    switch (*c++) {
    case 'h': return can_consume(c, 'h') ? lm_hh : lm_h;
    case 'l': return can_consume(c, 'l') ? lm_ll : lm_l;
    case 'L': return lm_L;
    case 'j': return lm_j;
    case 'z':
    case 'Z': return lm_z;
    case 't': return lm_t;
    }
    --c; // don't consume *c - it wasn't a flag
    return lm_none;
}
 
QString QString::vasprintf(const char *cformat, va_list ap)
{
    if (!cformat || !*cformat) {
        // Qt 1.x compat
        return fromLatin1("");
    }
 
    // Parse cformat
 
    QString result;
    const char *c = cformat;
    const char *formatEnd = cformat + qstrlen(cformat);
    for (;;) {
        // Copy non-escape chars to result
        const char *cb = c;
        while (*c != '\0' && *c != '%')
            c++;
        append_utf8(result, cb, qsizetype(c - cb));
 
        if (*c == '\0')
            break;
 
        // Found '%'
        const char *escape_start = c;
        ++c;
 
        if (*c == '\0') {
            result.append(QLatin1Char('%')); // a % at the end of the string - treat as non-escape text
            break;
        }
        if (*c == '%') {
            result.append(QLatin1Char('%')); // %%
            ++c;
            continue;
        }
 
        uint flags = parse_flag_characters(c);
 
        if (*c == '\0') {
            result.append(QLatin1String(escape_start)); // incomplete escape, treat as non-escape text
            break;
        }
 
        // Parse field width
        int width = -1; // -1 means unspecified
        if (qIsDigit(*c)) {
            width = parse_field_width(c, formatEnd - c);
        } else if (*c == '*') { // can't parse this in another function, not portably, at least
            width = va_arg(ap, int);
            if (width < 0)
                width = -1; // treat all negative numbers as unspecified
            ++c;
        }
 
        if (*c == '\0') {
            result.append(QLatin1String(escape_start)); // incomplete escape, treat as non-escape text
            break;
        }
 
        // Parse precision
        int precision = -1; // -1 means unspecified
        if (*c == '.') {
            ++c;
            if (qIsDigit(*c)) {
                precision = parse_field_width(c, formatEnd - c);
            } else if (*c == '*') { // can't parse this in another function, not portably, at least
                precision = va_arg(ap, int);
                if (precision < 0)
                    precision = -1; // treat all negative numbers as unspecified
                ++c;
            }
        }
 
        if (*c == '\0') {
            result.append(QLatin1String(escape_start)); // incomplete escape, treat as non-escape text
            break;
        }
 
        const LengthMod length_mod = parse_length_modifier(c);
 
        if (*c == '\0') {
            result.append(QLatin1String(escape_start)); // incomplete escape, treat as non-escape text
            break;
        }
 
        // Parse the conversion specifier and do the conversion
        QString subst;
        switch (*c) {
            case 'd':
            case 'i': {
                qint64 i;
                switch (length_mod) {
                    case lm_none: i = va_arg(ap, int); break;
                    case lm_hh: i = va_arg(ap, int); break;
                    case lm_h: i = va_arg(ap, int); break;
                    case lm_l: i = va_arg(ap, long int); break;
                    case lm_ll: i = va_arg(ap, qint64); break;
                    case lm_j: i = va_arg(ap, long int); break;
 
                    /* ptrdiff_t actually, but it should be the same for us */
                    case lm_z: i = va_arg(ap, qsizetype); break;
                    case lm_t: i = va_arg(ap, qsizetype); break;
                    default: i = 0; break;
                }
                subst = QLocaleData::c()->longLongToString(i, precision, 10, width, flags);
                ++c;
                break;
            }
            case 'o':
            case 'u':
            case 'x':
            case 'X': {
                quint64 u;
                switch (length_mod) {
                    case lm_none: u = va_arg(ap, uint); break;
                    case lm_hh: u = va_arg(ap, uint); break;
                    case lm_h: u = va_arg(ap, uint); break;
                    case lm_l: u = va_arg(ap, ulong); break;
                    case lm_ll: u = va_arg(ap, quint64); break;
                    case lm_t: u = va_arg(ap, size_t); break;
                    case lm_z: u = va_arg(ap, size_t); break;
                    default: u = 0; break;
                }
 
                if (qIsUpper(*c))
                    flags |= QLocaleData::CapitalEorX;
 
                int base = 10;
                switch (qToLower(*c)) {
                    case 'o':
                        base = 8; break;
                    case 'u':
                        base = 10; break;
                    case 'x':
                        base = 16; break;
                    default: break;
                }
                subst = QLocaleData::c()->unsLongLongToString(u, precision, base, width, flags);
                ++c;
                break;
            }
            case 'E':
            case 'e':
            case 'F':
            case 'f':
            case 'G':
            case 'g':
            case 'A':
            case 'a': {
                double d;
                if (length_mod == lm_L)
                    d = va_arg(ap, long double); // not supported - converted to a double
                else
                    d = va_arg(ap, double);
 
                if (qIsUpper(*c))
                    flags |= QLocaleData::CapitalEorX;
 
                QLocaleData::DoubleForm form = QLocaleData::DFDecimal;
                switch (qToLower(*c)) {
                    case 'e': form = QLocaleData::DFExponent; break;
                    case 'a':                             // not supported - decimal form used instead
                    case 'f': form = QLocaleData::DFDecimal; break;
                    case 'g': form = QLocaleData::DFSignificantDigits; break;
                    default: break;
                }
                subst = QLocaleData::c()->doubleToString(d, precision, form, width, flags);
                ++c;
                break;
            }
            case 'c': {
                if (length_mod == lm_l)
                    subst = QChar::fromUcs2(va_arg(ap, int));
                else
                    subst = QLatin1Char((uchar) va_arg(ap, int));
                ++c;
                break;
            }
            case 's': {
                if (length_mod == lm_l) {
                    const ushort *buff = va_arg(ap, const ushort*);
                    const ushort *ch = buff;
                    while (precision != 0 && *ch != 0) {
                        ++ch;
                        --precision;
                    }
                    subst.setUtf16(buff, ch - buff);
                } else if (precision == -1) {
                    subst = QString::fromUtf8(va_arg(ap, const char*));
                } else {
                    const char *buff = va_arg(ap, const char*);
                    subst = QString::fromUtf8(buff, qstrnlen(buff, precision));
                }
                ++c;
                break;
            }
            case 'p': {
                void *arg = va_arg(ap, void*);
                const quint64 i = reinterpret_cast<quintptr>(arg);
                flags |= QLocaleData::ShowBase;
                subst = QLocaleData::c()->unsLongLongToString(i, precision, 16, width, flags);
                ++c;
                break;
            }
            case 'n':
                switch (length_mod) {
                    case lm_hh: {
                        signed char *n = va_arg(ap, signed char*);
                        *n = result.length();
                        break;
                    }
                    case lm_h: {
                        short int *n = va_arg(ap, short int*);
                        *n = result.length();
                            break;
                    }
                    case lm_l: {
                        long int *n = va_arg(ap, long int*);
                        *n = result.length();
                        break;
                    }
                    case lm_ll: {
                        qint64 *n = va_arg(ap, qint64*);
                        *n = result.length();
                        break;
                    }
                    default: {
                        int *n = va_arg(ap, int*);
                        *n = result.length();
                        break;
                    }
                }
                ++c;
                break;
 
            default: // bad escape, treat as non-escape text
                for (const char *cc = escape_start; cc != c; ++cc)
                    result.append(QLatin1Char(*cc));
                continue;
        }
 
        if (flags & QLocaleData::LeftAdjusted)
            result.append(subst.leftJustified(width));
        else
            result.append(subst.rightJustified(width));
    }
 
    return result;
}
 
qint64 QString::toLongLong(bool *ok, int base) const
{
    return toIntegral_helper<qlonglong>(*this, ok, base);
}
 
qlonglong QString::toIntegral_helper(QStringView string, bool *ok, int base)
{
#if defined(QT_CHECK_RANGE)
    if (base != 0 && (base < 2 || base > 36)) {
        qWarning("QString::toULongLong: Invalid base (%d)", base);
        base = 10;
    }
#endif
 
    return QLocaleData::c()->stringToLongLong(string, base, ok, QLocale::RejectGroupSeparator);
}
 
 
quint64 QString::toULongLong(bool *ok, int base) const
{
    return toIntegral_helper<qulonglong>(*this, ok, base);
}
 
qulonglong QString::toIntegral_helper(QStringView string, bool *ok, uint base)
{
#if defined(QT_CHECK_RANGE)
    if (base != 0 && (base < 2 || base > 36)) {
        qWarning("QString::toULongLong: Invalid base (%d)", base);
        base = 10;
    }
#endif
 
    return QLocaleData::c()->stringToUnsLongLong(string, base, ok, QLocale::RejectGroupSeparator);
}
 
double QString::toDouble(bool *ok) const
{
    return QLocaleData::c()->stringToDouble(*this, ok, QLocale::RejectGroupSeparator);
}
 
float QString::toFloat(bool *ok) const
{
    return QLocaleData::convertDoubleToFloat(toDouble(ok), ok);
}
 
QString &QString::setNum(qlonglong n, int base)
{
    return *this = number(n, base);
}
 
QString &QString::setNum(qulonglong n, int base)
{
    return *this = number(n, base);
}
 
QString &QString::setNum(double n, char format, int precision)
{
    return *this = number(n, format, precision);
}
 
QString QString::number(long n, int base)
{
    return number(qlonglong(n), base);
}
 
QString QString::number(ulong n, int base)
{
    return number(qulonglong(n), base);
}
 
QString QString::number(int n, int base)
{
    return number(qlonglong(n), base);
}
 
QString QString::number(uint n, int base)
{
    return number(qulonglong(n), base);
}
 
QString QString::number(qlonglong n, int base)
{
#if defined(QT_CHECK_RANGE)
    if (base < 2 || base > 36) {
        qWarning("QString::setNum: Invalid base (%d)", base);
        base = 10;
    }
#endif
    bool negative = n < 0;
    /*
      Negating std::numeric_limits<qlonglong>::min() hits undefined behavior, so
      taking an absolute value has to take a slight detour.
    */
    return qulltoBasicLatin(negative ? 1u + qulonglong(-(n + 1)) : qulonglong(n), base, negative);
}
 
QString QString::number(qulonglong n, int base)
{
#if defined(QT_CHECK_RANGE)
    if (base < 2 || base > 36) {
        qWarning("QString::setNum: Invalid base (%d)", base);
        base = 10;
    }
#endif
    return qulltoBasicLatin(n, base, false);
}
 
 
QString QString::number(double n, char format, int precision)
{
    QLocaleData::DoubleForm form = QLocaleData::DFDecimal;
 
    switch (qToLower(format)) {
        case 'f':
            form = QLocaleData::DFDecimal;
            break;
        case 'e':
            form = QLocaleData::DFExponent;
            break;
        case 'g':
            form = QLocaleData::DFSignificantDigits;
            break;
        default:
#if defined(QT_CHECK_RANGE)
            qWarning("QString::setNum: Invalid format char '%c'", format);
#endif
            break;
    }
 
    return qdtoBasicLatin(n, form, precision, qIsUpper(format));
}
 
namespace {
template<class ResultList, class StringSource>
static ResultList splitString(const StringSource &source, QStringView sep,
                              Qt::SplitBehavior behavior, Qt::CaseSensitivity cs)
{
    ResultList list;
    typename StringSource::size_type start = 0;
    typename StringSource::size_type end;
    typename StringSource::size_type extra = 0;
    while ((end = QtPrivate::findString(QStringView(source.constData(), source.size()), start + extra, sep, cs)) != -1) {
        if (start != end || behavior == Qt::KeepEmptyParts)
            list.append(source.sliced(start, end - start));
        start = end + sep.size();
        extra = (sep.size() == 0 ? 1 : 0);
    }
    if (start != source.size() || behavior == Qt::KeepEmptyParts)
        list.append(source.sliced(start));
    return list;
}
 
} // namespace
 
QStringList QString::split(const QString &sep, Qt::SplitBehavior behavior, Qt::CaseSensitivity cs) const
{
    return splitString<QStringList>(*this, sep, behavior, cs);
}
 
QStringList QString::split(QChar sep, Qt::SplitBehavior behavior, Qt::CaseSensitivity cs) const
{
    return splitString<QStringList>(*this, QStringView(&sep, 1), behavior, cs);
}
 
QList<QStringView> QStringView::split(QStringView sep, Qt::SplitBehavior behavior, Qt::CaseSensitivity cs) const
{
    return splitString<QList<QStringView>>(QStringView(*this), sep, behavior, cs);
}
 
QList<QStringView> QStringView::split(QChar sep, Qt::SplitBehavior behavior, Qt::CaseSensitivity cs) const
{
    return split(QStringView(&sep, 1), behavior, cs);
}
 
#if QT_CONFIG(regularexpression)
namespace {
template<class ResultList, typename String>
static ResultList splitString(const String &source, const QRegularExpression &re,
                              Qt::SplitBehavior behavior)
{
    ResultList list;
    if (!re.isValid()) {
        qWarning("QString::split: invalid QRegularExpression object");
        return list;
    }
 
    qsizetype start = 0;
    qsizetype end = 0;
    QRegularExpressionMatchIterator iterator = re.globalMatch(source);
    while (iterator.hasNext()) {
        QRegularExpressionMatch match = iterator.next();
        end = match.capturedStart();
        if (start != end || behavior == Qt::KeepEmptyParts)
            list.append(source.sliced(start, end - start));
        start = match.capturedEnd();
    }
 
    if (start != source.size() || behavior == Qt::KeepEmptyParts)
        list.append(source.sliced(start));
 
    return list;
}
} // namespace
 
QStringList QString::split(const QRegularExpression &re, Qt::SplitBehavior behavior) const
{
    return splitString<QStringList>(*this, re, behavior);
}
 
QList<QStringView> QStringView::split(const QRegularExpression &re, Qt::SplitBehavior behavior) const
{
    return splitString<QList<QStringView>>(*this, re, behavior);
}
 
#endif // QT_CONFIG(regularexpression)
 
QString QString::repeated(qsizetype times) const
{
    if (d.size == 0)
        return *this;
 
    if (times <= 1) {
        if (times == 1)
            return *this;
        return QString();
    }
 
    const qsizetype resultSize = times * d.size;
 
    QString result;
    result.reserve(resultSize);
    if (result.capacity() != resultSize)
        return QString(); // not enough memory
 
    memcpy(result.d.data(), d.data(), d.size * sizeof(QChar));
 
    qsizetype sizeSoFar = d.size;
    char16_t *end = result.d.data() + sizeSoFar;
 
    const qsizetype halfResultSize = resultSize >> 1;
    while (sizeSoFar <= halfResultSize) {
        memcpy(end, result.d.data(), sizeSoFar * sizeof(QChar));
        end += sizeSoFar;
        sizeSoFar <<= 1;
    }
    memcpy(end, result.d.data(), (resultSize - sizeSoFar) * sizeof(QChar));
    result.d.data()[resultSize] = '\0';
    result.d.size = resultSize;
    return result;
}
 
void qt_string_normalize(QString *data, QString::NormalizationForm mode, QChar::UnicodeVersion version, qsizetype from)
{
    {
        // check if it's fully ASCII first, because then we have no work
        auto start = reinterpret_cast<const char16_t *>(data->constData());
        const char16_t *p = start + from;
        if (isAscii_helper(p, p + data->length() - from))
            return;
        if (p > start + from)
            from = p - start - 1;        // need one before the non-ASCII to perform NFC
    }
 
    if (version == QChar::Unicode_Unassigned) {
        version = QChar::currentUnicodeVersion();
    } else if (int(version) <= NormalizationCorrectionsVersionMax) {
        const QString &s = *data;
        QChar *d = nullptr;
        for (int i = 0; i < NumNormalizationCorrections; ++i) {
            const NormalizationCorrection &n = uc_normalization_corrections[i];
            if (n.version > version) {
                qsizetype pos = from;
                if (QChar::requiresSurrogates(n.ucs4)) {
                    char16_t ucs4High = QChar::highSurrogate(n.ucs4);
                    char16_t ucs4Low = QChar::lowSurrogate(n.ucs4);
                    char16_t oldHigh = QChar::highSurrogate(n.old_mapping);
                    char16_t oldLow = QChar::lowSurrogate(n.old_mapping);
                    while (pos < s.length() - 1) {
                        if (s.at(pos).unicode() == ucs4High && s.at(pos + 1).unicode() == ucs4Low) {
                            if (!d)
                                d = data->data();
                            d[pos] = QChar(oldHigh);
                            d[++pos] = QChar(oldLow);
                        }
                        ++pos;
                    }
                } else {
                    while (pos < s.length()) {
                        if (s.at(pos).unicode() == n.ucs4) {
                            if (!d)
                                d = data->data();
                            d[pos] = QChar(n.old_mapping);
                        }
                        ++pos;
                    }
                }
            }
        }
    }
 
    if (normalizationQuickCheckHelper(data, mode, from, &from))
        return;
 
    decomposeHelper(data, mode < QString::NormalizationForm_KD, version, from);
 
    canonicalOrderHelper(data, version, from);
 
    if (mode == QString::NormalizationForm_D || mode == QString::NormalizationForm_KD)
        return;
 
    composeHelper(data, version, from);
}
 
QString QString::normalized(QString::NormalizationForm mode, QChar::UnicodeVersion version) const
{
    QString copy = *this;
    qt_string_normalize(&copy, mode, version, 0);
    return copy;
}
 
#if QT_VERSION < QT_VERSION_CHECK(7, 0, 0)
static void checkArgEscape(QStringView s)
{
    // If we're in here, it means that qArgDigitValue has accepted the
    // digit. We can skip the check in case we already know it will
    // succeed.
    if (!supportUnicodeDigitValuesInArg())
        return;
 
    const auto isNonAsciiDigit = [](QChar c) {
        return c.unicode() < u'0' || c.unicode() > u'9';
    };
 
    if (std::any_of(s.begin(), s.end(), isNonAsciiDigit)) {
        const auto accumulateDigit = [](int partial, QChar digit) {
            return partial * 10 + digit.digitValue();
        };
        const int parsedNumber = std::accumulate(s.begin(), s.end(), 0, accumulateDigit);
 
        qWarning("QString::arg(): the replacement \"%%%ls\" contains non-ASCII digits;\n"
                 "    it is currently being interpreted as the %d-th substitution.\n"
                 "    This is deprecated; support for non-ASCII digits will be dropped\n"
                 "    in a future version of Qt.",
                 qUtf16Printable(s.toString()),
                 parsedNumber);
    }
}
#endif
 
struct ArgEscapeData
{
    int min_escape;            // lowest escape sequence number
    int occurrences;           // number of occurrences of the lowest escape sequence number
    int locale_occurrences;    // number of occurrences of the lowest escape sequence number that
                               // contain 'L'
    int escape_len;            // total length of escape sequences which will be replaced
};
 
static ArgEscapeData findArgEscapes(QStringView s)
{
    const QChar *uc_begin = s.begin();
    const QChar *uc_end = s.end();
 
    ArgEscapeData d;
 
    d.min_escape = INT_MAX;
    d.occurrences = 0;
    d.escape_len = 0;
    d.locale_occurrences = 0;
 
    const QChar *c = uc_begin;
    while (c != uc_end) {
        while (c != uc_end && c->unicode() != '%')
            ++c;
 
        if (c == uc_end)
            break;
        const QChar *escape_start = c;
        if (++c == uc_end)
            break;
 
        bool locale_arg = false;
        if (c->unicode() == 'L') {
            locale_arg = true;
            if (++c == uc_end)
                break;
        }
 
        int escape = qArgDigitValue(*c);
        if (escape == -1)
            continue;
 
        // ### Qt 7: do not allow anything but ASCII digits
        // in arg()'s replacements.
#if QT_VERSION <= QT_VERSION_CHECK(7, 0, 0)
        const QChar *escapeBegin = c;
        const QChar *escapeEnd = escapeBegin + 1;
#endif
 
        ++c;
 
        if (c != uc_end) {
            const int next_escape = qArgDigitValue(*c);
            if (next_escape != -1) {
                escape = (10 * escape) + next_escape;
                ++c;
#if QT_VERSION <= QT_VERSION_CHECK(7, 0, 0)
                ++escapeEnd;
#endif
            }
        }
 
#if QT_VERSION <= QT_VERSION_CHECK(7, 0, 0)
        checkArgEscape(QStringView(escapeBegin, escapeEnd));
#endif
 
        if (escape > d.min_escape)
            continue;
 
        if (escape < d.min_escape) {
            d.min_escape = escape;
            d.occurrences = 0;
            d.escape_len = 0;
            d.locale_occurrences = 0;
        }
 
        ++d.occurrences;
        if (locale_arg)
            ++d.locale_occurrences;
        d.escape_len += c - escape_start;
    }
    return d;
}
 
static QString replaceArgEscapes(QStringView s, const ArgEscapeData &d, qsizetype field_width,
                                 QStringView arg, QStringView larg, QChar fillChar)
{
    // Negative field-width for right-padding, positive for left-padding:
    const qsizetype abs_field_width = qAbs(field_width);
    const qsizetype result_len =
            s.length() - d.escape_len
            + (d.occurrences - d.locale_occurrences) * qMax(abs_field_width, arg.length())
            + d.locale_occurrences * qMax(abs_field_width, larg.length());
 
    QString result(result_len, Qt::Uninitialized);
    QChar *rc = const_cast<QChar *>(result.unicode());
    QChar *const result_end = rc + result_len;
    int repl_cnt = 0;
 
    const QChar *c = s.begin();
    const QChar *const uc_end = s.end();
    while (c != uc_end) {
        Q_ASSERT(d.occurrences > repl_cnt);
        /* We don't have to check increments of c against uc_end because, as
           long as d.occurrences > repl_cnt, we KNOW there are valid escape
           sequences remaining. */
 
        const QChar *text_start = c;
        while (c->unicode() != '%')
            ++c;
 
        const QChar *escape_start = c++;
        const bool localize = c->unicode() == 'L';
        if (localize)
            ++c;
 
        int escape = qArgDigitValue(*c);
        if (escape != -1 && c + 1 != uc_end) {
            const int digit = qArgDigitValue(c[1]);
            if (digit != -1) {
                ++c;
                escape = 10 * escape + digit;
            }
        }
 
        if (escape != d.min_escape) {
            memcpy(rc, text_start, (c - text_start) * sizeof(QChar));
            rc += c - text_start;
        } else {
            ++c;
 
            memcpy(rc, text_start, (escape_start - text_start) * sizeof(QChar));
            rc += escape_start - text_start;
 
            const QStringView use = localize ? larg : arg;
            const qsizetype pad_chars = abs_field_width - use.length();
            // (If negative, relevant loops are no-ops: no need to check.)
 
            if (field_width > 0) { // left padded
                for (qsizetype i = 0; i < pad_chars; ++i)
                    *rc++ = fillChar;
            }
 
            memcpy(rc, use.data(), use.length() * sizeof(QChar));
            rc += use.length();
 
            if (field_width < 0) { // right padded
                for (qsizetype i = 0; i < pad_chars; ++i)
                    *rc++ = fillChar;
            }
 
            if (++repl_cnt == d.occurrences) {
                memcpy(rc, c, (uc_end - c) * sizeof(QChar));
                rc += uc_end - c;
                Q_ASSERT(rc == result_end);
                c = uc_end;
            }
        }
    }
    Q_ASSERT(rc == result_end);
 
    return result;
}
 
#if QT_STRINGVIEW_LEVEL < 2
QString QString::arg(const QString &a, int fieldWidth, QChar fillChar) const
{
    return arg(qToStringViewIgnoringNull(a), fieldWidth, fillChar);
}
#endif // QT_STRINGVIEW_LEVEL < 2
 
QString QString::arg(QStringView a, int fieldWidth, QChar fillChar) const
{
    ArgEscapeData d = findArgEscapes(*this);
 
    if (Q_UNLIKELY(d.occurrences == 0)) {
        qWarning("QString::arg: Argument missing: %ls, %ls", qUtf16Printable(*this),
                  qUtf16Printable(a.toString()));
        return *this;
    }
    return replaceArgEscapes(*this, d, fieldWidth, a, a, fillChar);
}
 
QString QString::arg(QLatin1String a, int fieldWidth, QChar fillChar) const
{
    QVarLengthArray<char16_t> utf16(a.size());
    qt_from_latin1(utf16.data(), a.data(), a.size());
    return arg(QStringView(utf16.data(), utf16.size()), fieldWidth, fillChar);
}
 
QString QString::arg(qlonglong a, int fieldWidth, int base, QChar fillChar) const
{
    ArgEscapeData d = findArgEscapes(*this);
 
    if (d.occurrences == 0) {
        qWarning() << "QString::arg: Argument missing:" << *this << ',' << a;
        return *this;
    }
 
    unsigned flags = QLocaleData::NoFlags;
    // ZeroPadded sorts out left-padding when the fill is zero, to the right of sign:
    if (fillChar == QLatin1Char('0'))
        flags = QLocaleData::ZeroPadded;
 
    QString arg;
    if (d.occurrences > d.locale_occurrences) {
        arg = QLocaleData::c()->longLongToString(a, -1, base, fieldWidth, flags);
        Q_ASSERT(fillChar != QLatin1Char('0') || !qIsFinite(a)
                 || fieldWidth <= arg.length());
    }
 
    QString localeArg;
    if (d.locale_occurrences > 0) {
        QLocale locale;
        if (!(locale.numberOptions() & QLocale::OmitGroupSeparator))
            flags |= QLocaleData::GroupDigits;
        localeArg = locale.d->m_data->longLongToString(a, -1, base, fieldWidth, flags);
        Q_ASSERT(fillChar != QLatin1Char('0') || !qIsFinite(a)
                 || fieldWidth <= localeArg.length());
    }
 
    return replaceArgEscapes(*this, d, fieldWidth, arg, localeArg, fillChar);
}
 
QString QString::arg(qulonglong a, int fieldWidth, int base, QChar fillChar) const
{
    ArgEscapeData d = findArgEscapes(*this);
 
    if (d.occurrences == 0) {
        qWarning() << "QString::arg: Argument missing:" << *this << ',' << a;
        return *this;
    }
 
    unsigned flags = QLocaleData::NoFlags;
    // ZeroPadded sorts out left-padding when the fill is zero, to the right of sign:
    if (fillChar == QLatin1Char('0'))
        flags = QLocaleData::ZeroPadded;
 
    QString arg;
    if (d.occurrences > d.locale_occurrences) {
        arg = QLocaleData::c()->unsLongLongToString(a, -1, base, fieldWidth, flags);
        Q_ASSERT(fillChar != QLatin1Char('0') || !qIsFinite(a)
                 || fieldWidth <= arg.length());
    }
 
    QString localeArg;
    if (d.locale_occurrences > 0) {
        QLocale locale;
        if (!(locale.numberOptions() & QLocale::OmitGroupSeparator))
            flags |= QLocaleData::GroupDigits;
        localeArg = locale.d->m_data->unsLongLongToString(a, -1, base, fieldWidth, flags);
        Q_ASSERT(fillChar != QLatin1Char('0') || !qIsFinite(a)
                 || fieldWidth <= localeArg.length());
    }
 
    return replaceArgEscapes(*this, d, fieldWidth, arg, localeArg, fillChar);
}
 
QString QString::arg(QChar a, int fieldWidth, QChar fillChar) const
{
    return arg(QStringView{&a, 1}, fieldWidth, fillChar);
}
 
QString QString::arg(char a, int fieldWidth, QChar fillChar) const
{
    return arg(QLatin1Char(a), fieldWidth, fillChar);
}
 
QString QString::arg(double a, int fieldWidth, char format, int precision, QChar fillChar) const
{
    ArgEscapeData d = findArgEscapes(*this);
 
    if (d.occurrences == 0) {
        qWarning("QString::arg: Argument missing: %s, %g", toLocal8Bit().data(), a);
        return *this;
    }
 
    unsigned flags = QLocaleData::NoFlags;
    // ZeroPadded sorts out left-padding when the fill is zero, to the right of sign:
    if (fillChar == QLatin1Char('0'))
        flags |= QLocaleData::ZeroPadded;
 
    if (qIsUpper(format))
        flags |= QLocaleData::CapitalEorX;
 
    QLocaleData::DoubleForm form = QLocaleData::DFDecimal;
    switch (qToLower(format)) {
    case 'f':
        form = QLocaleData::DFDecimal;
        break;
    case 'e':
        form = QLocaleData::DFExponent;
        break;
    case 'g':
        form = QLocaleData::DFSignificantDigits;
        break;
    default:
#if defined(QT_CHECK_RANGE)
        qWarning("QString::arg: Invalid format char '%c'", format);
#endif
        break;
    }
 
    QString arg;
    if (d.occurrences > d.locale_occurrences) {
        arg = QLocaleData::c()->doubleToString(a, precision, form, fieldWidth,
                                               flags | QLocaleData::ZeroPadExponent);
        Q_ASSERT(fillChar != QLatin1Char('0') || !qIsFinite(a)
                 || fieldWidth <= arg.length());
    }
 
    QString localeArg;
    if (d.locale_occurrences > 0) {
        QLocale locale;
 
        const QLocale::NumberOptions numberOptions = locale.numberOptions();
        if (!(numberOptions & QLocale::OmitGroupSeparator))
            flags |= QLocaleData::GroupDigits;
        if (!(numberOptions & QLocale::OmitLeadingZeroInExponent))
            flags |= QLocaleData::ZeroPadExponent;
        if (numberOptions & QLocale::IncludeTrailingZeroesAfterDot)
            flags |= QLocaleData::AddTrailingZeroes;
        localeArg = locale.d->m_data->doubleToString(a, precision, form, fieldWidth, flags);
        Q_ASSERT(fillChar != QLatin1Char('0') || !qIsFinite(a)
                 || fieldWidth <= localeArg.length());
    }
 
    return replaceArgEscapes(*this, d, fieldWidth, arg, localeArg, fillChar);
}
 
static inline char16_t to_unicode(const QChar c) { return c.unicode(); }
static inline char16_t to_unicode(const char c) { return QLatin1Char{c}.unicode(); }
 
template <typename Char>
static int getEscape(const Char *uc, qsizetype *pos, qsizetype len, int maxNumber = 999)
{
    int i = *pos;
    ++i;
    if (i < len && uc[i] == QLatin1Char('L'))
        ++i;
    if (i < len) {
        int escape = to_unicode(uc[i]) - '0';
        if (uint(escape) >= 10U)
            return -1;
        ++i;
        while (i < len) {
            int digit = to_unicode(uc[i]) - '0';
            if (uint(digit) >= 10U)
                break;
            escape = (escape * 10) + digit;
            ++i;
        }
        if (escape <= maxNumber) {
            *pos = i;
            return escape;
        }
    }
    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 entries 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 {
struct Part
{
    Part() = default; // for QVarLengthArray; do not use
    constexpr Part(QStringView s, int num = -1)
        : tag{QtPrivate::ArgBase::U16}, number{num}, data{s.utf16()}, size{s.size()} {}
    constexpr Part(QLatin1String s, int num = -1)
        : tag{QtPrivate::ArgBase::L1}, number{num}, data{s.data()}, size{s.size()} {}
 
    void reset(QStringView s) noexcept { *this = {s, number}; }
    void reset(QLatin1String s) noexcept { *this = {s, number}; }
 
    QtPrivate::ArgBase::Tag tag;
    int number;
    const void *data;
    qsizetype size;
};
} // unnamed namespace
 
Q_DECLARE_TYPEINFO(Part, Q_PRIMITIVE_TYPE);
 
namespace {
 
enum { ExpectedParts = 32 };
 
typedef QVarLengthArray<Part, ExpectedParts> ParseResult;
typedef QVarLengthArray<int, ExpectedParts/2> ArgIndexToPlaceholderMap;
 
template <typename StringView>
static ParseResult parseMultiArgFormatString(StringView s)
{
    ParseResult result;
 
    const auto uc = s.data();
    const auto len = s.size();
    const auto end = len - 1;
    qsizetype i = 0;
    qsizetype last = 0;
 
    while (i < end) {
        if (uc[i] == QLatin1Char('%')) {
            qsizetype percent = i;
            int number = getEscape(uc, &i, len);
            if (number != -1) {
                if (last != percent)
                    result.push_back(Part{s.sliced(last, percent - last)}); // literal text (incl. failed placeholders)
                result.push_back(Part{s.sliced(percent, i - percent), number});  // parsed placeholder
                last = i;
                continue;
            }
        }
        ++i;
    }
 
    if (last < len)
        result.push_back(Part{s.sliced(last, len - last)}); // trailing literal text
 
    return result;
}
 
static ArgIndexToPlaceholderMap makeArgIndexToPlaceholderMap(const ParseResult &parts)
{
    ArgIndexToPlaceholderMap result;
 
    for (Part part : parts) {
        if (part.number >= 0)
            result.push_back(part.number);
    }
 
    std::sort(result.begin(), result.end());
    result.erase(std::unique(result.begin(), result.end()),
                 result.end());
 
    return result;
}
 
static qsizetype resolveStringRefsAndReturnTotalSize(ParseResult &parts, const ArgIndexToPlaceholderMap &argIndexToPlaceholderMap, const QtPrivate::ArgBase *args[])
{
    using namespace QtPrivate;
    qsizetype totalSize = 0;
    for (Part &part : parts) {
        if (part.number != -1) {
            const auto it = std::find(argIndexToPlaceholderMap.begin(), argIndexToPlaceholderMap.end(), part.number);
            if (it != argIndexToPlaceholderMap.end()) {
                const auto &arg = *args[it - argIndexToPlaceholderMap.begin()];
                switch (arg.tag) {
                case ArgBase::L1:
                    part.reset(static_cast<const QLatin1StringArg&>(arg).string);
                    break;
                case ArgBase::U8:
                    Q_UNREACHABLE(); // waiting for QUtf8String...
                    break;
                case ArgBase::U16:
                    part.reset(static_cast<const QStringViewArg&>(arg).string);
                    break;
                }
            }
        }
        totalSize += part.size;
    }
    return totalSize;
}
 
} // unnamed namespace
 
Q_ALWAYS_INLINE QString to_string(QLatin1String s) noexcept { return s; }
Q_ALWAYS_INLINE QString to_string(QStringView s) noexcept { return s.toString(); }
 
template <typename StringView>
static QString argToQStringImpl(StringView pattern, size_t numArgs, const QtPrivate::ArgBase **args)
{
    // Step 1-2 above
    ParseResult parts = parseMultiArgFormatString(pattern);
 
    // 3-4
    ArgIndexToPlaceholderMap argIndexToPlaceholderMap = makeArgIndexToPlaceholderMap(parts);
 
    if (static_cast<size_t>(argIndexToPlaceholderMap.size()) > numArgs) // 3a
        argIndexToPlaceholderMap.resize(qsizetype(numArgs));
    else if (Q_UNLIKELY(static_cast<size_t>(argIndexToPlaceholderMap.size()) < numArgs)) // 3b
        qWarning("QString::arg: %d argument(s) missing in %ls",
                 int(numArgs - argIndexToPlaceholderMap.size()), qUtf16Printable(to_string(pattern)));
 
    // 5
    const qsizetype totalSize = resolveStringRefsAndReturnTotalSize(parts, argIndexToPlaceholderMap, args);
 
    // 6:
    QString result(totalSize, Qt::Uninitialized);
    auto out = const_cast<QChar*>(result.constData());
 
    for (Part part : parts) {
        switch (part.tag) {
        case QtPrivate::ArgBase::L1:
            if (part.size) {
                qt_from_latin1(reinterpret_cast<char16_t*>(out),
                               reinterpret_cast<const char*>(part.data), part.size);
            }
            break;
        case QtPrivate::ArgBase::U8:
            Q_UNREACHABLE(); // waiting for QUtf8String
            break;
        case QtPrivate::ArgBase::U16:
            if (part.size)
                memcpy(out, part.data, part.size * sizeof(QChar));
            break;
        }
        out += part.size;
    }
 
    return result;
}
 
QString QtPrivate::argToQString(QStringView pattern, size_t n, const ArgBase **args)
{
    return argToQStringImpl(pattern, n, args);
}
 
QString QtPrivate::argToQString(QLatin1String pattern, size_t n, const ArgBase **args)
{
    return argToQStringImpl(pattern, n, args);
}
 
bool QString::isSimpleText() const
{
    const char16_t *p = d.data();
    const char16_t * const end = p + d.size;
    while (p < end) {
        char16_t uc = *p;
        // sort out regions of complex text formatting
        if (uc > 0x058f && (uc < 0x1100 || uc > 0xfb0f)) {
            return false;
        }
        p++;
    }
 
    return true;
}
 
bool QString::isRightToLeft() const
{
    return QtPrivate::isRightToLeft(QStringView(*this));
}
 
QString::iterator QString::erase(QString::const_iterator first, QString::const_iterator last)
{
    const auto start = std::distance(cbegin(), first);
    const auto len = std::distance(first, last);
    remove(start, len);
    return begin() + start;
}
 
QString QString::fromRawData(const QChar *unicode, qsizetype size)
{
    return QString(DataPointer::fromRawData(const_cast<char16_t *>(reinterpret_cast<const char16_t *>(unicode)), size));
}
 
QString &QString::setRawData(const QChar *unicode, qsizetype size)
{
    if (!unicode || !size) {
        clear();
    }
    *this = fromRawData(unicode, size);
    return *this;
}
 
#if !defined(QT_NO_DATASTREAM) || defined(QT_BOOTSTRAPPED)
QDataStream &operator<<(QDataStream &out, const QString &str)
{
    if (out.version() == 1) {
        out << str.toLatin1();
    } else {
        if (!str.isNull() || out.version() < 3) {
            if ((out.byteOrder() == QDataStream::BigEndian) == (QSysInfo::ByteOrder == QSysInfo::BigEndian)) {
                out.writeBytes(reinterpret_cast<const char *>(str.unicode()),
                               static_cast<uint>(sizeof(QChar) * str.length()));
            } else {
                QVarLengthArray<char16_t> buffer(str.length());
                qbswap<sizeof(char16_t)>(str.constData(), str.length(), buffer.data());
                out.writeBytes(reinterpret_cast<const char *>(buffer.data()),
                               static_cast<uint>(sizeof(char16_t) * buffer.size()));
            }
        } else {
            // write null marker
            out << (quint32)0xffffffff;
        }
    }
    return out;
}
 
QDataStream &operator>>(QDataStream &in, QString &str)
{
    if (in.version() == 1) {
        QByteArray l;
        in >> l;
        str = QString::fromLatin1(l);
    } else {
        quint32 bytes = 0;
        in >> bytes;                                  // read size of string
        if (bytes == 0xffffffff) {                    // null string
            str.clear();
        } else if (bytes > 0) {                       // not empty
            if (bytes & 0x1) {
                str.clear();
                in.setStatus(QDataStream::ReadCorruptData);
                return in;
            }
 
            const quint32 Step = 1024 * 1024;
            quint32 len = bytes / 2;
            quint32 allocated = 0;
 
            while (allocated < len) {
                int blockSize = qMin(Step, len - allocated);
                str.resize(allocated + blockSize);
                if (in.readRawData(reinterpret_cast<char *>(str.data()) + allocated * 2,
                                   blockSize * 2) != blockSize * 2) {
                    str.clear();
                    in.setStatus(QDataStream::ReadPastEnd);
                    return in;
                }
                allocated += blockSize;
            }
 
            if ((in.byteOrder() == QDataStream::BigEndian)
                    != (QSysInfo::ByteOrder == QSysInfo::BigEndian)) {
                char16_t *data = reinterpret_cast<char16_t *>(str.data());
                qbswap<sizeof(*data)>(data, len, data);
            }
        } else {
            str = QString(QLatin1String(""));
        }
    }
    return in;
}
#endif // QT_NO_DATASTREAM
 
bool QtPrivate::isRightToLeft(QStringView string) noexcept
{
    int isolateLevel = 0;
 
    for (QStringIterator i(string); i.hasNext();) {
        const char32_t c = i.next();
 
        switch (QChar::direction(c)) {
        case QChar::DirRLI:
        case QChar::DirLRI:
        case QChar::DirFSI:
            ++isolateLevel;
            break;
        case QChar::DirPDI:
            if (isolateLevel)
                --isolateLevel;
            break;
        case QChar::DirL:
            if (isolateLevel)
                break;
            return false;
        case QChar::DirR:
        case QChar::DirAL:
            if (isolateLevel)
                break;
            return true;
        case QChar::DirEN:
        case QChar::DirES:
        case QChar::DirET:
        case QChar::DirAN:
        case QChar::DirCS:
        case QChar::DirB:
        case QChar::DirS:
        case QChar::DirWS:
        case QChar::DirON:
        case QChar::DirLRE:
        case QChar::DirLRO:
        case QChar::DirRLE:
        case QChar::DirRLO:
        case QChar::DirPDF:
        case QChar::DirNSM:
        case QChar::DirBN:
            break;
        }
    }
    return false;
}
 
qsizetype QtPrivate::count(QStringView haystack, QStringView needle, Qt::CaseSensitivity cs) noexcept
{
    qsizetype num = 0;
    qsizetype i = -1;
    if (haystack.size() > 500 && needle.size() > 5) {
        QStringMatcher matcher(needle, cs);
        while ((i = matcher.indexIn(haystack, i + 1)) != -1)
            ++num;
    } else {
        while ((i = QtPrivate::findString(haystack, i + 1, needle, cs)) != -1)
            ++num;
    }
    return num;
}
 
qsizetype QtPrivate::count(QStringView haystack, QChar ch, Qt::CaseSensitivity cs) noexcept
{
    qsizetype num = 0;
    if (cs == Qt::CaseSensitive) {
        for (QChar c : haystack) {
            if (c == ch)
                ++num;
        }
    } else {
        ch = foldCase(ch);
        for (QChar c : haystack) {
            if (foldCase(c) == ch)
                ++num;
        }
    }
    return num;
}
 
template <typename Haystack, typename Needle>
bool qt_starts_with_impl(Haystack haystack, Needle needle, Qt::CaseSensitivity cs) noexcept
{
    if (haystack.isNull())
        return needle.isNull();
    const auto haystackLen = haystack.size();
    const auto needleLen = needle.size();
    if (haystackLen == 0)
        return needleLen == 0;
    if (needleLen > haystackLen)
        return false;
 
    return QtPrivate::compareStrings(haystack.left(needleLen), needle, cs) == 0;
}
 
static inline bool qt_starts_with(QStringView haystack, QStringView needle, Qt::CaseSensitivity cs)
{
    return qt_starts_with_impl(haystack, needle, cs);
}
 
static inline bool qt_starts_with(QStringView haystack, QLatin1String needle, Qt::CaseSensitivity cs)
{
    return qt_starts_with_impl(haystack, needle, cs);
}
 
static inline bool qt_starts_with(QStringView haystack, QChar needle, Qt::CaseSensitivity cs)
{
    return haystack.size()
           && (cs == Qt::CaseSensitive ? haystack.front() == needle
                                       : foldCase(haystack.front()) == foldCase(needle));
}
 
bool QtPrivate::startsWith(QStringView haystack, QStringView needle, Qt::CaseSensitivity cs) noexcept
{
    return qt_starts_with_impl(haystack, needle, cs);
}
 
bool QtPrivate::startsWith(QStringView haystack, QLatin1String needle, Qt::CaseSensitivity cs) noexcept
{
    return qt_starts_with_impl(haystack, needle, cs);
}
 
bool QtPrivate::startsWith(QLatin1String haystack, QStringView needle, Qt::CaseSensitivity cs) noexcept
{
    return qt_starts_with_impl(haystack, needle, cs);
}
 
bool QtPrivate::startsWith(QLatin1String haystack, QLatin1String needle, Qt::CaseSensitivity cs) noexcept
{
    return qt_starts_with_impl(haystack, needle, cs);
}
 
template <typename Haystack, typename Needle>
bool qt_ends_with_impl(Haystack haystack, Needle needle, Qt::CaseSensitivity cs) noexcept
{
    if (haystack.isNull())
        return needle.isNull();
    const auto haystackLen = haystack.size();
    const auto needleLen = needle.size();
    if (haystackLen == 0)
        return needleLen == 0;
    if (haystackLen < needleLen)
        return false;
 
    return QtPrivate::compareStrings(haystack.right(needleLen), needle, cs) == 0;
}
 
static inline bool qt_ends_with(QStringView haystack, QStringView needle, Qt::CaseSensitivity cs)
{
    return qt_ends_with_impl(haystack, needle, cs);
}
 
static inline bool qt_ends_with(QStringView haystack, QLatin1String needle, Qt::CaseSensitivity cs)
{
    return qt_ends_with_impl(haystack, needle, cs);
}
 
static inline bool qt_ends_with(QStringView haystack, QChar needle, Qt::CaseSensitivity cs)
{
    return haystack.size()
           && (cs == Qt::CaseSensitive ? haystack.back() == needle
                                       : foldCase(haystack.back()) == foldCase(needle));
}
 
bool QtPrivate::endsWith(QStringView haystack, QStringView needle, Qt::CaseSensitivity cs) noexcept
{
    return qt_ends_with_impl(haystack, needle, cs);
}
 
bool QtPrivate::endsWith(QStringView haystack, QLatin1String needle, Qt::CaseSensitivity cs) noexcept
{
    return qt_ends_with_impl(haystack, needle, cs);
}
 
bool QtPrivate::endsWith(QLatin1String haystack, QStringView needle, Qt::CaseSensitivity cs) noexcept
{
    return qt_ends_with_impl(haystack, needle, cs);
}
 
bool QtPrivate::endsWith(QLatin1String haystack, QLatin1String needle, Qt::CaseSensitivity cs) noexcept
{
    return qt_ends_with_impl(haystack, needle, cs);
}
 
qsizetype QtPrivate::findString(QStringView haystack0, qsizetype from, QStringView needle0, Qt::CaseSensitivity cs) noexcept
{
    const qsizetype l = haystack0.size();
    const qsizetype sl = needle0.size();
    if (from < 0)
        from += l;
    if (std::size_t(sl + from) > std::size_t(l))
        return -1;
    if (!sl)
        return from;
    if (!l)
        return -1;
 
    if (sl == 1)
        return qFindChar(haystack0, needle0[0], from, cs);
 
    /*
        We use the Boyer-Moore algorithm in cases where the overhead
        for the skip table should pay off, otherwise we use a simple
        hash function.
    */
    if (l > 500 && sl > 5)
        return qFindStringBoyerMoore(haystack0, from, needle0, cs);
 
    auto sv = [sl](const char16_t *v) { return QStringView(v, sl); };
    /*
        We use some hashing for efficiency's sake. Instead of
        comparing strings, we compare the hash value of str with that
        of a part of this QString. Only if that matches, we call
        qt_string_compare().
    */
    const char16_t *needle = needle0.utf16();
    const char16_t *haystack = haystack0.utf16() + from;
    const char16_t *end = haystack0.utf16() + (l - sl);
    const std::size_t sl_minus_1 = sl - 1;
    std::size_t hashNeedle = 0, hashHaystack = 0;
    qsizetype idx;
 
    if (cs == Qt::CaseSensitive) {
        for (idx = 0; idx < sl; ++idx) {
            hashNeedle = ((hashNeedle<<1) + needle[idx]);
            hashHaystack = ((hashHaystack<<1) + haystack[idx]);
        }
        hashHaystack -= haystack[sl_minus_1];
 
        while (haystack <= end) {
            hashHaystack += haystack[sl_minus_1];
            if (hashHaystack == hashNeedle
                 && QtPrivate::compareStrings(needle0, sv(haystack), Qt::CaseSensitive) == 0)
                return haystack - haystack0.utf16();
 
            REHASH(*haystack);
            ++haystack;
        }
    } else {
        const char16_t *haystack_start = haystack0.utf16();
        for (idx = 0; idx < sl; ++idx) {
            hashNeedle = (hashNeedle<<1) + foldCase(needle + idx, needle);
            hashHaystack = (hashHaystack<<1) + foldCase(haystack + idx, haystack_start);
        }
        hashHaystack -= foldCase(haystack + sl_minus_1, haystack_start);
 
        while (haystack <= end) {
            hashHaystack += foldCase(haystack + sl_minus_1, haystack_start);
            if (hashHaystack == hashNeedle
                 && QtPrivate::compareStrings(needle0, sv(haystack), Qt::CaseInsensitive) == 0)
                return haystack - haystack0.utf16();
 
            REHASH(foldCase(haystack, haystack_start));
            ++haystack;
        }
    }
    return -1;
}
 
qsizetype QtPrivate::findString(QStringView haystack, qsizetype from, QLatin1String needle, Qt::CaseSensitivity cs) noexcept
{
    if (haystack.size() < needle.size())
        return -1;
 
    QVarLengthArray<char16_t> s(needle.size());
    qt_from_latin1(s.data(), needle.latin1(), needle.size());
    return QtPrivate::findString(haystack, from, QStringView(reinterpret_cast<const QChar*>(s.constData()), s.size()), cs);
}
 
qsizetype QtPrivate::findString(QLatin1String haystack, qsizetype from, QStringView needle, Qt::CaseSensitivity cs) noexcept
{
    if (haystack.size() < needle.size())
        return -1;
 
    if (!QtPrivate::isLatin1(needle)) // won't find non-L1 UTF-16 needles in a L1 haystack!
        return -1;
 
    if (needle.size() == 1) {
        const char n = needle.front().toLatin1();
        return QtPrivate::findString(haystack, from, QLatin1String(&n, 1), cs);
    }
 
    QVarLengthArray<char> s(needle.size());
    qt_to_latin1_unchecked(reinterpret_cast<uchar *>(s.data()), needle.utf16(), needle.size());
    return QtPrivate::findString(haystack, from, QLatin1String(s.data(), s.size()), cs);
}
 
qsizetype QtPrivate::findString(QLatin1String haystack, qsizetype from, QLatin1String needle, Qt::CaseSensitivity cs) noexcept
{
    if (from < 0)
        from += haystack.size();
    if (from < 0)
        return -1;
    qsizetype adjustedSize = haystack.size() - from;
    if (adjustedSize < needle.size())
        return -1;
    if (needle.size() == 0)
        return from;
 
    if (cs == Qt::CaseSensitive) {
 
        if (needle.size() == 1) {
            Q_ASSUME(haystack.data() != nullptr); // see size check above
            if (auto it = memchr(haystack.data() + from, needle.front().toLatin1(), adjustedSize))
                return static_cast<const char *>(it) - haystack.data();
            return -1;
        }
 
        const QByteArrayMatcher matcher(needle);
        return matcher.indexIn(haystack, from);
    }
 
    // If the needle is sufficiently small we simply iteratively search through
    // the haystack. When the needle is too long we use a boyer-moore searcher
    // from the standard library, if available. If it is not available then the
    // QLatin1Strings are converted to QString and compared as such. Though
    // initialization is slower the boyer-moore search it employs still makes up
    // for it when haystack and needle are sufficiently long.
    // The needle size was chosen by testing various lengths using the
    // qstringtokenizer benchmark with the
    // "tokenize_qlatin1string_qlatin1string" test.
#ifdef Q_CC_MSVC
    const qsizetype threshold = 1;
#else
    const qsizetype threshold = 13;
#endif
    if (needle.size() <= threshold) {
        const auto begin = haystack.begin();
        const auto end = haystack.end() - needle.size() + 1;
        const uchar needle1 = latin1Lower[uchar(needle[0].toLatin1())];
        auto ciMatch = [needle1](const char ch) {
            return latin1Lower[uchar(ch)] == needle1;
        };
        const qsizetype nlen1 = needle.size() - 1;
        for (auto it = std::find_if(begin + from, end, ciMatch); it < end;
             it = std::find_if(it + 1, end, ciMatch)) {
            // In this comparison we skip the first character because we know it's a match
            if (!nlen1 || QLatin1String(it + 1, nlen1).compare(needle.sliced(1), cs) == 0)
                return std::distance(begin, it);
        }
        return -1;
    }
 
#ifdef __cpp_lib_boyer_moore_searcher
    const auto ciHasher = [](char a) { return latin1Lower[uchar(a)]; };
    const auto ciEqual = [](char a, char b) {
        return latin1Lower[uchar(a)] == latin1Lower[uchar(b)];
    };
    const auto it =
            std::search(haystack.begin() + from, haystack.end(),
                        std::boyer_moore_searcher(needle.begin(), needle.end(), ciHasher, ciEqual));
    return it == haystack.end() ? -1 : std::distance(haystack.begin(), it);
#else
    QVarLengthArray<char16_t> h(adjustedSize);
    const auto begin = haystack.end() - adjustedSize;
    qt_from_latin1(h.data(), begin, adjustedSize);
    QVarLengthArray<char16_t> n(needle.size());
    qt_from_latin1(n.data(), needle.latin1(), needle.size());
    qsizetype res = QtPrivate::findString(QStringView(h.constData(), h.size()), 0,
                                          QStringView(n.constData(), n.size()), cs);
    if (res == -1)
        return -1;
    return res + std::distance(haystack.begin(), begin);
#endif
}
 
qsizetype QtPrivate::lastIndexOf(QStringView haystack, qsizetype from, QStringView needle, Qt::CaseSensitivity cs) noexcept
{
    return qLastIndexOf(haystack, from, needle, cs);
}
 
qsizetype QtPrivate::lastIndexOf(QStringView haystack, qsizetype from, QLatin1String needle, Qt::CaseSensitivity cs) noexcept
{
    return qLastIndexOf(haystack, from, needle, cs);
}
 
qsizetype QtPrivate::lastIndexOf(QLatin1String haystack, qsizetype from, QStringView needle, Qt::CaseSensitivity cs) noexcept
{
    return qLastIndexOf(haystack, from, needle, cs);
}
 
qsizetype QtPrivate::lastIndexOf(QLatin1String haystack, qsizetype from, QLatin1String needle, Qt::CaseSensitivity cs) noexcept
{
    return qLastIndexOf(haystack, from, needle, cs);
}
 
#if QT_CONFIG(regularexpression)
qsizetype QtPrivate::indexOf(QStringView haystack, const QRegularExpression &re, qsizetype from, QRegularExpressionMatch *rmatch)
{
    if (!re.isValid()) {
        qWarning("QString(View)::indexOf: invalid QRegularExpression object");
        return -1;
    }
 
    QRegularExpressionMatch match = re.match(haystack, from);
    if (match.hasMatch()) {
        const qsizetype ret = match.capturedStart();
        if (rmatch)
            *rmatch = std::move(match);
        return ret;
    }
 
    return -1;
}
 
qsizetype QtPrivate::lastIndexOf(QStringView haystack, const QRegularExpression &re, qsizetype from, QRegularExpressionMatch *rmatch)
{
    if (!re.isValid()) {
        qWarning("QString(View)::lastIndexOf: invalid QRegularExpression object");
        return -1;
    }
 
    qsizetype endpos = (from < 0) ? (haystack.size() + from + 1) : (from + 1);
    QRegularExpressionMatchIterator iterator = re.globalMatch(haystack);
    qsizetype lastIndex = -1;
    while (iterator.hasNext()) {
        QRegularExpressionMatch match = iterator.next();
        qsizetype start = match.capturedStart();
        if (start < endpos) {
            lastIndex = start;
            if (rmatch)
                *rmatch = std::move(match);
        } else {
            break;
        }
    }
 
    return lastIndex;
}
 
bool QtPrivate::contains(QStringView haystack, const QRegularExpression &re, QRegularExpressionMatch *rmatch)
{
    if (!re.isValid()) {
        qWarning("QString(View)::contains: invalid QRegularExpression object");
        return false;
    }
    QRegularExpressionMatch m = re.match(haystack);
    bool hasMatch = m.hasMatch();
    if (hasMatch && rmatch)
        *rmatch = std::move(m);
    return hasMatch;
}
 
qsizetype QtPrivate::count(QStringView haystack, const QRegularExpression &re)
{
    if (!re.isValid()) {
        qWarning("QString(View)::count: invalid QRegularExpression object");
        return 0;
    }
    qsizetype count = 0;
    qsizetype index = -1;
    qsizetype len = haystack.length();
    while (index <= len - 1) {
        QRegularExpressionMatch match = re.match(haystack, index + 1);
        if (!match.hasMatch())
            break;
        index = match.capturedStart();
        count++;
    }
    return count;
}
 
#endif // QT_CONFIG(regularexpression)
 
QString QString::toHtmlEscaped() const
{
    QString rich;
    const int len = length();
    rich.reserve(qsizetype(len * 1.1));
    for (int i = 0; i < len; ++i) {
        if (at(i) == QLatin1Char('<'))
            rich += QLatin1String("&lt;");
        else if (at(i) == QLatin1Char('>'))
            rich += QLatin1String("&gt;");
        else if (at(i) == QLatin1Char('&'))
            rich += QLatin1String("&amp;");
        else if (at(i) == QLatin1Char('"'))
            rich += QLatin1String("&quot;");
        else
            rich += at(i);
    }
    rich.squeeze();
    return rich;
}
 
void QAbstractConcatenable::appendLatin1To(QLatin1String in, QChar *out) noexcept
{
    qt_from_latin1(reinterpret_cast<char16_t *>(out), in.data(), size_t(in.size()));
}
 
double QStringView::toDouble(bool *ok) const
{
    return QLocaleData::c()->stringToDouble(*this, ok, QLocale::RejectGroupSeparator);
}
 
float QStringView::toFloat(bool *ok) const
{
    return QLocaleData::convertDoubleToFloat(toDouble(ok), ok);
}
 
QT_END_NAMESPACE