Revision control
Copy as Markdown
// Copyright (C) 2016 Intel Corporation.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
// Qt-Security score:critical reason:data-parser
#ifndef QSTRINGALGORITHMS_P_H
#define QSTRINGALGORITHMS_P_H
//
// W A R N I N G
// -------------
//
// This file is not part of the Qt API. It exists for the convenience
// of internal files. This header file may change from version to version
// without notice, or even be removed.
//
// We mean it.
//
#include <QtCore/qnamespace.h>
#include "qspan.h"
#include "qstring.h"
#include "qlocale_p.h" // for ascii_isspace
QT_BEGIN_NAMESPACE
template <typename StringType> struct QStringAlgorithms
{
typedef typename StringType::value_type Char;
typedef typename StringType::size_type size_type;
typedef typename std::remove_cv<StringType>::type NakedStringType;
using ViewType =
std::conditional_t<std::is_same_v<StringType, QString>, QStringView, QByteArrayView>;
using ViewChar = typename ViewType::storage_type;
static const bool isConst = std::is_const<StringType>::value;
static NakedStringType aligned(const StringType &txt, qsizetype width, Char fill,
Qt::AlignmentFlag align, bool truncate)
{
const auto len = txt.size();
if (len == width) // nothing to do, keep sharing
return txt;
if (len > width) { // too long
if (truncate)
return txt.left(width);
else
return txt;
}
// too short, so truncate doesn't matter
return [&] {
NakedStringType result;
result.reserve(width);
switch (align){
case Qt::AlignLeft:
result += txt;
result.resize(width, fill);
break;
case Qt::AlignRight:
result.resize(width - len, fill);
result += txt;
break;
case Qt::AlignHCenter:
case Qt::AlignJustify:
case Qt::AlignAbsolute:
case Qt::AlignHorizontal_Mask:
case Qt::AlignTop:
case Qt::AlignBottom:
case Qt::AlignVCenter:
case Qt::AlignBaseline:
case Qt::AlignVertical_Mask:
case Qt::AlignCenter:
Q_UNREACHABLE();
};
return result;
}();
}
static inline bool isSpace(char ch) { return ascii_isspace(ch); }
static inline bool isSpace(QChar ch) { return ch.isSpace(); }
// Surrogate pairs are not handled in either of the functions below. That is
// not a problem because there are no space characters (Zs, Zl, Zp) outside the
// Basic Multilingual Plane.
static inline StringType trimmed_helper_inplace(NakedStringType &str, const Char *begin, const Char *end)
{
// in-place trimming:
Char *data = const_cast<Char *>(str.cbegin());
if (begin != data)
memmove(data, begin, (end - begin) * sizeof(Char));
str.resize(end - begin);
return std::move(str);
}
static inline StringType trimmed_helper_inplace(const NakedStringType &, const Char *, const Char *)
{
// can't happen
Q_UNREACHABLE_RETURN(StringType());
}
struct TrimPositions {
const Char *begin;
const Char *end;
};
// Returns {begin, end} where:
// - "begin" refers to the first non-space character
// - if there is a sequence of one or more space chacaters at the end,
// "end" refers to the first character in that sequence, otherwise
// "end" is str.cend()
[[nodiscard]] static TrimPositions trimmed_helper_positions(const StringType &str)
{
const Char *begin = str.cbegin();
const Char *end = str.cend();
// skip white space from end
while (begin < end && isSpace(end[-1]))
--end;
// skip white space from start
while (begin < end && isSpace(*begin))
begin++;
return {begin, end};
}
static inline StringType trimmed_helper(StringType &str)
{
const auto [begin, end] = trimmed_helper_positions(str);
if (begin == str.cbegin() && end == str.cend())
return str;
if (!isConst && str.isDetached())
return trimmed_helper_inplace(str, begin, end);
return StringType(begin, end - begin);
}
static inline StringType simplified_helper(StringType &str)
{
if (str.isEmpty())
return str;
const Char *src = str.cbegin();
const Char *end = str.cend();
NakedStringType result = isConst || !str.isDetached() ?
StringType(str.size(), Qt::Uninitialized) :
std::move(str);
Char *dst = const_cast<Char *>(result.cbegin());
Char *ptr = dst;
bool unmodified = true;
while (true) {
while (src != end && isSpace(*src))
++src;
while (src != end && !isSpace(*src))
*ptr++ = *src++;
if (src == end)
break;
if (*src != QChar::Space)
unmodified = false;
*ptr++ = QChar::Space;
}
if (ptr != dst && ptr[-1] == QChar::Space)
--ptr;
qsizetype newlen = ptr - dst;
if (isConst && newlen == str.size() && unmodified) {
// nothing happened, return the original
return str;
}
result.resize(newlen);
return result;
}
static inline bool needsReallocate(const StringType &str, qsizetype newSize) noexcept
{
const auto capacityAtEnd = str.capacity() - str.data_ptr().freeSpaceAtBegin();
return newSize > capacityAtEnd;
}
static inline const ViewChar *asUnicodeChar(ViewType v)
{
if constexpr (sizeof(ViewChar) == sizeof(QChar))
return v.utf16();
else
return v.data();
}
static inline qsizetype newSize(StringType &src, qsizetype bsize,
ViewType after, QSpan<const qsizetype> indices)
{
if (bsize == after.size())
return src.size();
else if (bsize > after.size()) // shrink
return src.size() - indices.size() * (bsize - after.size());
// bsize < after.size()
const qsizetype adjust = indices.size() * (after.size() - bsize);
return src.size() + adjust;
}
// {QString,QByteArray}::resize() but without the extra checks
static inline void setSize(StringType &src, qsizetype newSize)
{
Q_ASSERT(src.isDetached());
Q_ASSERT(newSize <= src.capacity());
auto &d = src.data_ptr();
d.size = newSize;
d.data()[newSize] = '\0';
}
// Instead of detaching, i.e. copying the whole data array then performing the
// replacement, create a new buffer, copy `src` and `after` to it and swap it
// with `src`.
static inline void replace_into_copy(StringType &src, qsizetype bsize,
ViewType after, QSpan<const qsizetype> indices,
qsizetype newlen)
{
StringType tmp{newlen, Qt::Uninitialized};
auto *to = tmp.data_ptr().data();
const auto *a = asUnicodeChar(after);
auto *const begin = src.data_ptr().data();
auto *first = begin;
for (auto i : indices) {
to = std::copy(first, begin + i, to);
to = std::copy(a, a + after.size(), to);
first = begin + i + bsize;
}
std::copy(first, src.data_ptr().end(), to); // remainder
src.swap(tmp);
}
static inline void replace_equal_len(StringType &src, [[maybe_unused]] qsizetype bsize,
ViewType after, QSpan<const qsizetype> indices)
{
Q_ASSERT(bsize == after.size());
Q_ASSERT(!src.data_ptr().needsDetach());
const auto *a = asUnicodeChar(after);
auto *const begin = src.data_ptr().data();
// before and after have the same length, so no reallocation
for (auto i : indices)
std::copy(a, a + after.size(), begin + i);
}
static inline void replace_shrink(StringType &src, qsizetype bsize, ViewType after,
QSpan<const qsizetype> indices)
{
Q_ASSERT(bsize > after.size());
Q_ASSERT(!src.data_ptr().needsDetach());
const auto *a = asUnicodeChar(after);
auto *const begin = src.data_ptr().data(); // data(), without the detach() check
auto *const end = begin + src.size();
Q_ASSERT(!indices.isEmpty());
auto *to = std::copy(a, a + after.size(), begin + indices.front());
auto *first = begin + indices.front() + bsize;
for (qsizetype i = 1; i < indices.size(); ++i) {
auto *last = begin + indices[i];
to = std::copy(first, last, to);
qsizetype adjust = i * (bsize - after.size());
to = std::copy(a, a + after.size(), last - adjust);
first = begin + indices[i] + bsize;
}
to = std::copy(first, end, to);
setSize(src,to - begin);
}
static inline void replace_grow(StringType &src, qsizetype bsize, ViewType after,
QSpan<const qsizetype> indices, qsizetype newlen)
{
Q_ASSERT(after.size() > bsize);
Q_ASSERT(!src.data_ptr().needsDetach());
// replace in-place, after is longer than before, so replace from the back
const qsizetype oldlen = src.size();
const auto *a = asUnicodeChar(after);
setSize(src, newlen);
auto *const begin = src.data_ptr().data(); // data(), without the detach() check
auto *last = begin + oldlen;
auto *to = src.data_ptr().end();
for (auto i = indices.size() - 1; i >= 0; --i) {
auto *first = begin + indices[i] + bsize;
to = std::copy_backward(first, last, to);
to = std::copy_backward(a, a + after.size(), to);
last = begin + indices[i];
}
}
static inline void replace_helper(StringType &src, qsizetype bsize, ViewType after,
QSpan<const qsizetype> indices)
{
if (indices.isEmpty())
return;
const qsizetype newlen = newSize(src, bsize, after, indices);
if (src.data_ptr().needsDetach()
|| (bsize < after.size() && needsReallocate(src, newlen))) {
// Instead of detaching (which would copy the whole data array) then
// performing the replacement, allocate a new string and copy the data
// over from `src` and `after` as needed.
replace_into_copy(src, bsize, after, indices, newlen);
return;
}
// No detaching or reallocation -> change in-place
if (bsize == after.size())
replace_equal_len(src, bsize, after, indices);
else if (bsize > after.size())
replace_shrink(src, bsize, after, indices);
else // bsize < after.size()
replace_grow(src, bsize, after, indices, newlen);
}
};
QT_END_NAMESPACE
#endif // QSTRINGALGORITHMS_P_H