Revision control
Copy as Markdown
// Copyright (C) 2023 The Qt Company Ltd.
// 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 QSTATICLATIN1STRINGMATCHER_H
#define QSTATICLATIN1STRINGMATCHER_H
#include <functional>
#include <iterator>
#include <limits>
#include <QtCore/q20algorithm.h>
#include <QtCore/qlatin1stringmatcher.h>
#include <QtCore/qstring.h>
QT_BEGIN_NAMESPACE
#ifdef Q_CC_GHS
# define QT_STATIC_BOYER_MOORE_NOT_SUPPORTED
#else
namespace QtPrivate {
template <class RandomIt1,
class Hash = std::hash<typename std::iterator_traits<RandomIt1>::value_type>,
class BinaryPredicate = std::equal_to<>>
class q_boyer_moore_searcher
{
public:
constexpr q_boyer_moore_searcher(RandomIt1 pat_first, RandomIt1 pat_last) : m_skiptable{}
{
const size_t n = std::distance(pat_first, pat_last);
constexpr auto uchar_max = (std::numeric_limits<uchar>::max)();
uchar max = n > uchar_max ? uchar_max : uchar(n);
q20::fill(std::begin(m_skiptable), std::end(m_skiptable), max);
Hash hf;
RandomIt1 pattern = pat_first + (n - max);
while (max--)
m_skiptable[hf(*pattern++)] = max;
}
template <class RandomIt2>
constexpr auto operator()(RandomIt2 first, RandomIt2 last, RandomIt1 pat_first,
RandomIt1 pat_last) const
{
struct R
{
RandomIt2 begin, end;
};
Hash hf;
BinaryPredicate pred;
auto pat_length = std::distance(pat_first, pat_last);
if (pat_length == 0)
return R{ first, first };
auto haystack_length = std::distance(first, last);
if (haystack_length < pat_length)
return R{ last, last };
const qsizetype pl_minus_one = qsizetype(pat_length - 1);
RandomIt2 current = first + pl_minus_one;
qsizetype skip = 0;
while (current < last - skip) {
current += skip;
skip = m_skiptable[hf(*current)];
if (!skip) {
// possible match
while (skip < pat_length) {
if (!pred(hf(*(current - skip)), hf(pat_first[pl_minus_one - skip])))
break;
skip++;
}
if (skip > pl_minus_one) { // we have a match
auto match = current + 1 - skip;
return R{ match, match + pat_length };
}
// If we don't have a match we are a bit inefficient as we only skip by one
// when we have the non matching char in the string.
if (m_skiptable[hf(*(current - skip))] == pat_length)
skip = pat_length - skip;
else
skip = 1;
}
}
return R{ last, last };
}
private:
alignas(16) uchar m_skiptable[256];
};
} // namespace QtPrivate
template <Qt::CaseSensitivity CS, size_t N>
class QStaticLatin1StringMatcher
{
static_assert(N > 2,
"QStaticLatin1StringMatcher makes no sense for finding a single-char pattern");
QLatin1StringView m_pattern;
using Hasher = std::conditional_t<CS == Qt::CaseSensitive, QtPrivate::QCaseSensitiveLatin1Hash,
QtPrivate::QCaseInsensitiveLatin1Hash>;
QtPrivate::q_boyer_moore_searcher<const char *, Hasher> m_searcher;
public:
explicit constexpr QStaticLatin1StringMatcher(QLatin1StringView patternToMatch) noexcept
: m_pattern(patternToMatch),
m_searcher(patternToMatch.begin(), patternToMatch.begin() + N - 1)
{
}
constexpr qsizetype indexIn(QLatin1StringView haystack, qsizetype from = 0) const noexcept
{ return indexIn_helper(haystack, from); }
constexpr qsizetype indexIn(QStringView haystack, qsizetype from = 0) const noexcept
{ return indexIn_helper(haystack, from); }
private:
template <typename String>
constexpr qsizetype indexIn_helper(String haystack, qsizetype from = 0) const noexcept
{
static_assert(QtPrivate::isLatin1OrUtf16View<String>);
if (from >= haystack.size())
return -1;
const auto start = [haystack]() constexpr {
if constexpr (std::is_same_v<String, QStringView>)
return haystack.utf16();
else
return haystack.begin();
}();
const auto begin = start + from;
const auto end = start + haystack.size();
const auto r = m_searcher(begin, end, m_pattern.begin(), m_pattern.end());
return r.begin == end ? -1 : std::distance(start, r.begin);
}
};
template <size_t N>
constexpr auto qMakeStaticCaseSensitiveLatin1StringMatcher(const char (&patternToMatch)[N]) noexcept
{
return QStaticLatin1StringMatcher<Qt::CaseSensitive, N>(
QLatin1StringView(patternToMatch, qsizetype(N) - 1));
}
template <size_t N>
constexpr auto
qMakeStaticCaseInsensitiveLatin1StringMatcher(const char (&patternToMatch)[N]) noexcept
{
return QStaticLatin1StringMatcher<Qt::CaseInsensitive, N>(
QLatin1StringView(patternToMatch, qsizetype(N) - 1));
}
#endif
QT_END_NAMESPACE
#endif // QSTATICLATIN1STRINGMATCHER_H