include/QtCore/qlatin1stringmatcher.h

0001 // Copyright (C) 2022 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 QLATIN1STRINGMATCHER_H
0006 #define QLATIN1STRINGMATCHER_H
0007
0008 #include <functional>
0009 #include <iterator>
0010 #include <limits>
0011
0012 #include <QtCore/q20algorithm.h>
0013 #include <QtCore/qstring.h>
0014
0015 QT_BEGIN_NAMESPACE
0016
0017 namespace QtPrivate {
0018 template <typename T> constexpr inline bool isLatin1OrUtf16View = false;
0019 template <> constexpr inline bool isLatin1OrUtf16View<QLatin1StringView> = true;
0020 template <> constexpr inline bool isLatin1OrUtf16View<QStringView> = true;
0021
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_hashed_needle
0026 {
0027 public:
0028     constexpr q_boyer_moore_searcher_hashed_needle(RandomIt1 pat_first, RandomIt1 pat_last)
0029         : m_skiptable{}
0030     {
0031         const size_t n = std::distance(pat_first, pat_last);
0032         constexpr auto uchar_max = (std::numeric_limits<uchar>::max)();
0033         uchar max = n > uchar_max ? uchar_max : uchar(n);
0034         q20::fill(std::begin(m_skiptable), std::end(m_skiptable), max);
0035
0036         RandomIt1 pattern = pat_first;
0037         pattern += n - max;
0038         while (max--)
0039             m_skiptable[uchar(*pattern++)] = max;
0040     }
0041
0042     template<class RandomIt2>
0043     constexpr auto operator()(RandomIt2 first, RandomIt2 last, RandomIt1 pat_first,
0044                               RandomIt1 pat_last) const
0045     {
0046         struct R
0047         {
0048             RandomIt2 begin, end;
0049         };
0050         Hash hf;
0051         BinaryPredicate pred;
0052         auto pat_length = std::distance(pat_first, pat_last);
0053         if (pat_length == 0)
0054             return R{ first, first };
0055
0056         const qsizetype pl_minus_one = qsizetype(pat_length - 1);
0057         RandomIt2 current = first + pl_minus_one;
0058
0059         while (current < last) {
0060             qsizetype skip = m_skiptable[hf(*current)];
0061             if (!skip) {
0062                 // possible match
0063                 while (skip < pat_length) {
0064                     if (!pred(hf(*(current - skip)), uchar(pat_first[pl_minus_one - skip])))
0065                         break;
0066                     skip++;
0067                 }
0068                 if (skip > pl_minus_one) { // we have a match
0069                     auto match = current - skip + 1;
0070                     return R{ match, match + pat_length };
0071                 }
0072
0073                 // If we don't have a match we are a bit inefficient as we only skip by one
0074                 // when we have the non matching char in the string.
0075                 if (m_skiptable[hf(*(current - skip))] == pat_length)
0076                     skip = pat_length - skip;
0077                 else
0078                     skip = 1;
0079             }
0080             current += skip;
0081         }
0082
0083         return R{ last, last };
0084     }
0085
0086 private:
0087     alignas(16) uchar m_skiptable[256];
0088 };
0089
0090 struct QCaseSensitiveLatin1Hash
0091 {
0092     constexpr QCaseSensitiveLatin1Hash() = default;
0093
0094     constexpr std::size_t operator()(char c) const noexcept { return std::size_t(uchar(c)); }
0095 };
0096
0097 struct QCaseInsensitiveLatin1Hash
0098 {
0099     constexpr QCaseInsensitiveLatin1Hash() = default;
0100
0101     constexpr std::size_t operator()(char c) const noexcept
0102     {
0103         return std::size_t(latin1Lower[uchar(c)]);
0104     }
0105
0106     static int difference(char lhs, char rhs)
0107     {
0108         return int(latin1Lower[uchar(lhs)]) - int(latin1Lower[uchar(rhs)]);
0109     }
0110
0111     static auto matcher(char ch)
0112     {
0113         return [sought = latin1Lower[uchar(ch)]](char other) {
0114             return latin1Lower[uchar(other)] == sought;
0115         };
0116     }
0117
0118 private:
0119     static constexpr uchar latin1Lower[256] = {
0120         0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f,
0121         0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,0x18,0x19,0x1a,0x1b,0x1c,0x1d,0x1e,0x1f,
0122         0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,0x28,0x29,0x2a,0x2b,0x2c,0x2d,0x2e,0x2f,
0123         0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39,0x3a,0x3b,0x3c,0x3d,0x3e,0x3f,
0124         0x40,0x61,0x62,0x63,0x64,0x65,0x66,0x67,0x68,0x69,0x6a,0x6b,0x6c,0x6d,0x6e,0x6f,
0125         0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,0x78,0x79,0x7a,0x5b,0x5c,0x5d,0x5e,0x5f,
0126         0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67,0x68,0x69,0x6a,0x6b,0x6c,0x6d,0x6e,0x6f,
0127         0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,0x78,0x79,0x7a,0x7b,0x7c,0x7d,0x7e,0x7f,
0128         0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87,0x88,0x89,0x8a,0x8b,0x8c,0x8d,0x8e,0x8f,
0129         0x90,0x91,0x92,0x93,0x94,0x95,0x96,0x97,0x98,0x99,0x9a,0x9b,0x9c,0x9d,0x9e,0x9f,
0130         0xa0,0xa1,0xa2,0xa3,0xa4,0xa5,0xa6,0xa7,0xa8,0xa9,0xaa,0xab,0xac,0xad,0xae,0xaf,
0131         0xb0,0xb1,0xb2,0xb3,0xb4,0xb5,0xb6,0xb7,0xb8,0xb9,0xba,0xbb,0xbc,0xbd,0xbe,0xbf,
0132         // 0xd7 (multiplication sign) and 0xdf (sz ligature) complicate life
0133         0xe0,0xe1,0xe2,0xe3,0xe4,0xe5,0xe6,0xe7,0xe8,0xe9,0xea,0xeb,0xec,0xed,0xee,0xef,
0134         0xf0,0xf1,0xf2,0xf3,0xf4,0xf5,0xf6,0xd7,0xf8,0xf9,0xfa,0xfb,0xfc,0xfd,0xfe,0xdf,
0135         0xe0,0xe1,0xe2,0xe3,0xe4,0xe5,0xe6,0xe7,0xe8,0xe9,0xea,0xeb,0xec,0xed,0xee,0xef,
0136         0xf0,0xf1,0xf2,0xf3,0xf4,0xf5,0xf6,0xf7,0xf8,0xf9,0xfa,0xfb,0xfc,0xfd,0xfe,0xff
0137     };
0138 };
0139 }
0140
0141 class QLatin1StringMatcher
0142 {
0143 public:
0144     Q_CORE_EXPORT QLatin1StringMatcher() noexcept;
0145     Q_CORE_EXPORT explicit QLatin1StringMatcher(
0146             QLatin1StringView pattern, Qt::CaseSensitivity cs = Qt::CaseSensitive) noexcept;
0147     Q_CORE_EXPORT ~QLatin1StringMatcher() noexcept;
0148
0149     Q_CORE_EXPORT void setPattern(QLatin1StringView pattern) noexcept;
0150     Q_CORE_EXPORT QLatin1StringView pattern() const noexcept;
0151     Q_CORE_EXPORT void setCaseSensitivity(Qt::CaseSensitivity cs) noexcept;
0152     Q_CORE_EXPORT Qt::CaseSensitivity caseSensitivity() const noexcept;
0153
0154     Q_CORE_EXPORT qsizetype indexIn(QLatin1StringView haystack, qsizetype from = 0) const noexcept;
0155     Q_CORE_EXPORT qsizetype indexIn(QStringView haystack, qsizetype from = 0) const noexcept;
0156
0157 private:
0158     void setSearcher() noexcept;
0159     void freeSearcher() noexcept;
0160
0161     QLatin1StringView m_pattern;
0162     Qt::CaseSensitivity m_cs;
0163     typedef QtPrivate::q_boyer_moore_searcher_hashed_needle<const char *,
0164                                                             QtPrivate::QCaseSensitiveLatin1Hash>
0165             CaseSensitiveSearcher;
0166     typedef QtPrivate::q_boyer_moore_searcher_hashed_needle<const char *,
0167                                                             QtPrivate::QCaseInsensitiveLatin1Hash>
0168             CaseInsensitiveSearcher;
0169     union {
0170         CaseSensitiveSearcher m_caseSensitiveSearcher;
0171         CaseInsensitiveSearcher m_caseInsensitiveSearcher;
0172     };
0173
0174     template <typename String>
0175     qsizetype indexIn_helper(String haystack, qsizetype from) const noexcept;
0176
0177     char m_foldBuffer[256];
0178 };
0179
0180 QT_END_NAMESPACE
0181
0182 #endif // QLATIN1MATCHER_H