include/QtCore/qstaticlatin1stringmatcher.h

0001 // Copyright (C) 2023 The Qt Company Ltd.
0002 // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
0003 // Qt-Security score:critical reason:data-parser
0004
0005 #ifndef QSTATICLATIN1STRINGMATCHER_H
0006 #define QSTATICLATIN1STRINGMATCHER_H
0007
0008 #include <functional>
0009 #include <iterator>
0010 #include <limits>
0011
0012 #include <QtCore/q20algorithm.h>
0013 #include <QtCore/qlatin1stringmatcher.h>
0014 #include <QtCore/qstring.h>
0015
0016 QT_BEGIN_NAMESPACE
0017
0018 #ifdef Q_CC_GHS
0019 #  define QT_STATIC_BOYER_MOORE_NOT_SUPPORTED
0020 #else
0021 namespace QtPrivate {
0022 template <class RandomIt1,
0023           class Hash = std::hash<typename std::iterator_traits<RandomIt1>::value_type>,
0024           class BinaryPredicate = std::equal_to<>>
0025 class q_boyer_moore_searcher
0026 {
0027 public:
0028     constexpr q_boyer_moore_searcher(RandomIt1 pat_first, RandomIt1 pat_last) : m_skiptable{}
0029     {
0030         const size_t n = std::distance(pat_first, pat_last);
0031         constexpr auto uchar_max = (std::numeric_limits<uchar>::max)();
0032         uchar max = n > uchar_max ? uchar_max : uchar(n);
0033         q20::fill(std::begin(m_skiptable), std::end(m_skiptable), max);
0034         Hash hf;
0035         RandomIt1 pattern = std::next(pat_first, n - max);
0036         while (max--)
0037             m_skiptable[hf(*pattern++)] = max;
0038     }
0039
0040     template <class RandomIt2>
0041     constexpr auto operator()(RandomIt2 first, RandomIt2 last, RandomIt1 pat_first,
0042                               RandomIt1 pat_last) const
0043     {
0044         struct R
0045         {
0046             RandomIt2 begin, end;
0047         };
0048         Hash hf;
0049         BinaryPredicate pred;
0050         auto pat_length = std::distance(pat_first, pat_last);
0051         if (pat_length == 0)
0052             return R{ first, first };
0053
0054         auto haystack_length = std::distance(first, last);
0055         if (haystack_length < pat_length)
0056             return R{ last, last };
0057
0058         const qsizetype pl_minus_one = qsizetype(pat_length - 1);
0059         RandomIt2 current = first + pl_minus_one;
0060
0061         qsizetype skip = 0;
0062         while (current < last - skip) {
0063             current += skip;
0064             skip = m_skiptable[hf(*current)];
0065             if (!skip) {
0066                 // possible match
0067                 while (skip < pat_length) {
0068                     if (!pred(hf(*(current - skip)), hf(pat_first[pl_minus_one - skip])))
0069                         break;
0070                     skip++;
0071                 }
0072                 if (skip > pl_minus_one) { // we have a match
0073                     auto match = current + 1 - skip;
0074                     return R{ match, match + pat_length };
0075                 }
0076
0077                 // If we don't have a match we are a bit inefficient as we only skip by one
0078                 // when we have the non matching char in the string.
0079                 if (m_skiptable[hf(*(current - skip))] == pat_length)
0080                     skip = pat_length - skip;
0081                 else
0082                     skip = 1;
0083             }
0084         }
0085
0086         return R{ last, last };
0087     }
0088
0089 private:
0090     alignas(16) uchar m_skiptable[256];
0091 };
0092 } // namespace QtPrivate
0093
0094 template <Qt::CaseSensitivity CS, size_t N>
0095 class QStaticLatin1StringMatcher
0096 {
0097     static_assert(N > 2,
0098                   "QStaticLatin1StringMatcher makes no sense for finding a single-char pattern");
0099
0100     QLatin1StringView m_pattern;
0101     using Hasher = std::conditional_t<CS == Qt::CaseSensitive, QtPrivate::QCaseSensitiveLatin1Hash,
0102                                       QtPrivate::QCaseInsensitiveLatin1Hash>;
0103     QtPrivate::q_boyer_moore_searcher<const char *, Hasher> m_searcher;
0104
0105 public:
0106     explicit constexpr QStaticLatin1StringMatcher(QLatin1StringView patternToMatch) noexcept
0107         : m_pattern(patternToMatch),
0108           m_searcher(patternToMatch.begin(), patternToMatch.begin() + N - 1)
0109     {
0110     }
0111
0112     constexpr qsizetype indexIn(QLatin1StringView haystack, qsizetype from = 0) const noexcept
0113     { return indexIn_helper(haystack, from); }
0114
0115     constexpr qsizetype indexIn(QStringView haystack, qsizetype from = 0) const noexcept
0116     { return indexIn_helper(haystack, from); }
0117
0118 private:
0119     template <typename String>
0120     constexpr qsizetype indexIn_helper(String haystack, qsizetype from = 0) const noexcept
0121     {
0122         static_assert(QtPrivate::isLatin1OrUtf16View<String>);
0123
0124         if (from >= haystack.size())
0125             return -1;
0126
0127         const auto start = [haystack]() constexpr {
0128             if constexpr (std::is_same_v<String, QStringView>)
0129                 return haystack.utf16();
0130             else
0131                 return haystack.begin();
0132         }();
0133         const auto begin = start + from;
0134         const auto end = start + haystack.size();
0135         const auto r = m_searcher(begin, end, m_pattern.begin(), m_pattern.end());
0136         return r.begin == end ? -1 : std::distance(start, r.begin);
0137     }
0138 };
0139
0140 template <size_t N>
0141 constexpr auto qMakeStaticCaseSensitiveLatin1StringMatcher(const char (&patternToMatch)[N]) noexcept
0142 {
0143     return QStaticLatin1StringMatcher<Qt::CaseSensitive, N>(
0144             QLatin1StringView(patternToMatch, qsizetype(N) - 1));
0145 }
0146
0147 template <size_t N>
0148 constexpr auto
0149 qMakeStaticCaseInsensitiveLatin1StringMatcher(const char (&patternToMatch)[N]) noexcept
0150 {
0151     return QStaticLatin1StringMatcher<Qt::CaseInsensitive, N>(
0152             QLatin1StringView(patternToMatch, qsizetype(N) - 1));
0153 }
0154 #endif
0155
0156 QT_END_NAMESPACE
0157
0158 #endif // QSTATICLATIN1STRINGMATCHER_H