1// Copyright (C) 2023 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3// Qt-Security score:critical reason:data-parser
4
5#ifndef QSTATICLATIN1STRINGMATCHER_H
6#define QSTATICLATIN1STRINGMATCHER_H
7
8#include <functional>
9#include <iterator>
10#include <limits>
11
12#include <QtCore/q20algorithm.h>
13#include <QtCore/qlatin1stringmatcher.h>
14#include <QtCore/qstring.h>
15
16QT_BEGIN_NAMESPACE
17
18#ifdef Q_CC_GHS
19# define QT_STATIC_BOYER_MOORE_NOT_SUPPORTED
20#else
21namespace QtPrivate {
22template <class RandomIt1,
23 class Hash = std::hash<typename std::iterator_traits<RandomIt1>::value_type>,
24 class BinaryPredicate = std::equal_to<>>
25class q_boyer_moore_searcher
26{
27public:
28 constexpr q_boyer_moore_searcher(RandomIt1 pat_first, RandomIt1 pat_last) : m_skiptable{}
29 {
30 const size_t n = std::distance(pat_first, pat_last);
31 constexpr auto uchar_max = (std::numeric_limits<uchar>::max)();
32 uchar max = n > uchar_max ? uchar_max : uchar(n);
33 q20::fill(first: std::begin(arr&: m_skiptable), last: std::end(arr&: m_skiptable), value: max);
34 Hash hf;
35 RandomIt1 pattern = std::next(pat_first, n - max);
36 while (max--)
37 m_skiptable[hf(*pattern++)] = max;
38 }
39
40 template <class RandomIt2>
41 constexpr auto operator()(RandomIt2 first, RandomIt2 last, RandomIt1 pat_first,
42 RandomIt1 pat_last) const
43 {
44 struct R
45 {
46 RandomIt2 begin, end;
47 };
48 Hash hf;
49 BinaryPredicate pred;
50 auto pat_length = std::distance(pat_first, pat_last);
51 if (pat_length == 0)
52 return R{ first, first };
53
54 auto haystack_length = std::distance(first, last);
55 if (haystack_length < pat_length)
56 return R{ last, last };
57
58 const qsizetype pl_minus_one = qsizetype(pat_length - 1);
59 RandomIt2 current = first + pl_minus_one;
60
61 qsizetype skip = 0;
62 while (current < last - skip) {
63 current += skip;
64 skip = m_skiptable[hf(*current)];
65 if (!skip) {
66 // possible match
67 while (skip < pat_length) {
68 if (!pred(hf(*(current - skip)), hf(pat_first[pl_minus_one - skip])))
69 break;
70 skip++;
71 }
72 if (skip > pl_minus_one) { // we have a match
73 auto match = current + 1 - skip;
74 return R{ match, match + pat_length };
75 }
76
77 // If we don't have a match we are a bit inefficient as we only skip by one
78 // when we have the non matching char in the string.
79 if (m_skiptable[hf(*(current - skip))] == pat_length)
80 skip = pat_length - skip;
81 else
82 skip = 1;
83 }
84 }
85
86 return R{ last, last };
87 }
88
89private:
90 alignas(16) uchar m_skiptable[256];
91};
92} // namespace QtPrivate
93
94template <Qt::CaseSensitivity CS, size_t N>
95class QStaticLatin1StringMatcher
96{
97 static_assert(N > 2,
98 "QStaticLatin1StringMatcher makes no sense for finding a single-char pattern");
99
100 QLatin1StringView m_pattern;
101 using Hasher = std::conditional_t<CS == Qt::CaseSensitive, QtPrivate::QCaseSensitiveLatin1Hash,
102 QtPrivate::QCaseInsensitiveLatin1Hash>;
103 QtPrivate::q_boyer_moore_searcher<const char *, Hasher> m_searcher;
104
105public:
106 explicit constexpr QStaticLatin1StringMatcher(QLatin1StringView patternToMatch) noexcept
107 : m_pattern(patternToMatch),
108 m_searcher(patternToMatch.begin(), patternToMatch.begin() + N - 1)
109 {
110 }
111
112 constexpr qsizetype indexIn(QLatin1StringView haystack, qsizetype from = 0) const noexcept
113 { return indexIn_helper(haystack, from); }
114
115 constexpr qsizetype indexIn(QStringView haystack, qsizetype from = 0) const noexcept
116 { return indexIn_helper(haystack, from); }
117
118private:
119 template <typename String>
120 constexpr qsizetype indexIn_helper(String haystack, qsizetype from = 0) const noexcept
121 {
122 static_assert(QtPrivate::isLatin1OrUtf16View<String>);
123
124 if (from >= haystack.size())
125 return -1;
126
127 const auto start = [haystack]() constexpr {
128 if constexpr (std::is_same_v<String, QStringView>)
129 return haystack.utf16();
130 else
131 return haystack.begin();
132 }();
133 const auto begin = start + from;
134 const auto end = start + haystack.size();
135 const auto r = m_searcher(begin, end, m_pattern.begin(), m_pattern.end());
136 return r.begin == end ? -1 : std::distance(start, r.begin);
137 }
138};
139
140template <size_t N>
141constexpr auto qMakeStaticCaseSensitiveLatin1StringMatcher(const char (&patternToMatch)[N]) noexcept
142{
143 return QStaticLatin1StringMatcher<Qt::CaseSensitive, N>(
144 QLatin1StringView(patternToMatch, qsizetype(N) - 1));
145}
146
147template <size_t N>
148constexpr auto
149qMakeStaticCaseInsensitiveLatin1StringMatcher(const char (&patternToMatch)[N]) noexcept
150{
151 return QStaticLatin1StringMatcher<Qt::CaseInsensitive, N>(
152 QLatin1StringView(patternToMatch, qsizetype(N) - 1));
153}
154#endif
155
156QT_END_NAMESPACE
157
158#endif // QSTATICLATIN1STRINGMATCHER_H
159

source code of qtbase/src/corelib/text/qstaticlatin1stringmatcher.h