1// Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Marc Mutz <marc.mutz@kdab.com>
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 QSTRINGTOKENIZER_H
6#define QSTRINGTOKENIZER_H
7
8#include <QtCore/qnamespace.h>
9#include <QtCore/qcontainerfwd.h>
10#include <iterator>
11
12QT_BEGIN_NAMESPACE
13
14template <typename, typename> class QStringBuilder;
15
16class QStringTokenizerBaseBase
17{
18protected:
19 ~QStringTokenizerBaseBase() = default;
20 constexpr QStringTokenizerBaseBase(Qt::SplitBehavior sb, Qt::CaseSensitivity cs) noexcept
21 : m_sb{sb}, m_cs{cs} {}
22
23 struct tokenizer_state {
24 qsizetype start, end, extra;
25 friend constexpr bool operator==(tokenizer_state lhs, tokenizer_state rhs) noexcept
26 { return lhs.start == rhs.start && lhs.end == rhs.end && lhs.extra == rhs.extra; }
27 friend constexpr bool operator!=(tokenizer_state lhs, tokenizer_state rhs) noexcept
28 { return !operator==(lhs, rhs); }
29 };
30
31 Qt::SplitBehavior m_sb;
32 Qt::CaseSensitivity m_cs;
33};
34
35template <typename Haystack, typename Needle>
36class QStringTokenizerBase : protected QStringTokenizerBaseBase
37{
38 struct next_result {
39 Haystack value;
40 bool ok;
41 tokenizer_state state;
42 };
43 inline next_result next(tokenizer_state state) const noexcept;
44 inline next_result toFront() const noexcept { return next(state: {}); }
45public:
46 constexpr explicit QStringTokenizerBase(Haystack haystack, Needle needle, Qt::SplitBehavior sb, Qt::CaseSensitivity cs) noexcept
47 : QStringTokenizerBaseBase{sb, cs}, m_haystack{haystack}, m_needle{needle} {}
48
49 class iterator;
50 friend class iterator;
51 class sentinel {
52 friend constexpr bool operator==(sentinel, sentinel) noexcept { return true; }
53 friend constexpr bool operator!=(sentinel, sentinel) noexcept { return false; }
54 };
55 class iterator {
56 const QStringTokenizerBase *tokenizer;
57 next_result current;
58 friend class QStringTokenizerBase;
59 explicit iterator(const QStringTokenizerBase &t) noexcept
60 : tokenizer{&t}, current{t.toFront()} {}
61 public:
62 using difference_type = qsizetype;
63 using value_type = Haystack;
64 using pointer = const value_type*;
65 using reference = const value_type&;
66 using iterator_category = std::forward_iterator_tag;
67
68 iterator() noexcept = default;
69
70 // violates std::forward_iterator (returns a reference into the iterator)
71 [[nodiscard]] constexpr const Haystack* operator->() const { return Q_ASSERT(current.ok), &current.value; }
72 [[nodiscard]] constexpr const Haystack& operator*() const { return *operator->(); }
73
74 iterator& operator++() { advance(); return *this; }
75 iterator operator++(int) { auto tmp = *this; advance(); return tmp; }
76
77 friend constexpr bool operator==(const iterator &lhs, sentinel) noexcept
78 { return !lhs.current.ok; }
79 friend constexpr bool operator!=(const iterator &lhs, sentinel) noexcept
80 { return !operator==(lhs, sentinel{}); }
81 friend constexpr bool operator==(sentinel, const iterator &rhs) noexcept
82 { return !rhs.current.ok; }
83 friend constexpr bool operator!=(sentinel, const iterator &rhs) noexcept
84 { return !operator==(sentinel{}, rhs); }
85 private:
86 void advance() {
87 Q_ASSERT(current.ok);
88 current = tokenizer->next(state: current.state);
89 }
90 };
91 using const_iterator = iterator;
92
93 using size_type = std::size_t;
94 using difference_type = typename iterator::difference_type;
95 using value_type = typename iterator::value_type;
96 using pointer = typename iterator::pointer;
97 using const_pointer = pointer;
98 using reference = typename iterator::reference;
99 using const_reference = reference;
100
101 [[nodiscard]] iterator begin() const noexcept { return iterator{*this}; }
102 [[nodiscard]] iterator cbegin() const noexcept { return begin(); }
103 [[nodiscard]] constexpr sentinel end() const noexcept { return {}; }
104 [[nodiscard]] constexpr sentinel cend() const noexcept { return {}; }
105
106private:
107 Haystack m_haystack;
108 Needle m_needle;
109};
110
111QT_BEGIN_INCLUDE_NAMESPACE
112#include <QtCore/qstringview.h>
113QT_END_INCLUDE_NAMESPACE
114
115namespace QtPrivate {
116namespace Tok {
117
118 constexpr qsizetype tokenSize(QChar) noexcept { return 1; }
119 template <typename String>
120 constexpr qsizetype tokenSize(const String &s) noexcept { return static_cast<qsizetype>(s.size()); }
121
122 template <typename String> struct ViewForImpl {};
123 template <> struct ViewForImpl<QStringView> { using type = QStringView; };
124 template <> struct ViewForImpl<QLatin1StringView> { using type = QLatin1StringView; };
125 template <> struct ViewForImpl<QChar> { using type = QChar; };
126 template <> struct ViewForImpl<QString> : ViewForImpl<QStringView> {};
127 template <> struct ViewForImpl<QLatin1Char> : ViewForImpl<QChar> {};
128 template <> struct ViewForImpl<char16_t> : ViewForImpl<QChar> {};
129 template <> struct ViewForImpl<char16_t*> : ViewForImpl<QStringView> {};
130 template <> struct ViewForImpl<const char16_t*> : ViewForImpl<QStringView> {};
131 template <typename LHS, typename RHS>
132 struct ViewForImpl<QStringBuilder<LHS, RHS>> : ViewForImpl<typename QStringBuilder<LHS,RHS>::ConvertTo> {};
133 template <typename Char, typename...Args>
134 struct ViewForImpl<std::basic_string<Char, Args...>> : ViewForImpl<Char*> {};
135#ifdef __cpp_lib_string_view
136 template <typename Char, typename...Args>
137 struct ViewForImpl<std::basic_string_view<Char, Args...>> : ViewForImpl<Char*> {};
138#endif
139
140 // This metafunction maps a StringLike to a View (currently, QChar,
141 // QStringView, QLatin1StringView). This is what QStringTokenizerBase
142 // operates on. QStringTokenizer adds pinning to keep rvalues alive
143 // for the duration of the algorithm.
144 template <typename String>
145 using ViewFor = typename ViewForImpl<typename std::decay<String>::type>::type;
146
147 // Pinning:
148 // rvalues of owning string types need to be moved into QStringTokenizer
149 // to keep them alive for the lifetime of the tokenizer. For lvalues, we
150 // assume the user takes care of that.
151
152 // default: don't pin anything (characters are pinned implicitly)
153 template <typename String>
154 struct PinForImpl { using type = ViewFor<String>; };
155
156 // rvalue QString -> QString
157 template <>
158 struct PinForImpl<QString> { using type = QString; };
159
160 // rvalue std::basic_string -> basic_string
161 template <typename Char, typename...Args>
162 struct PinForImpl<std::basic_string<Char, Args...>>
163 { using type = std::basic_string<Char, Args...>; };
164
165 // rvalue QStringBuilder -> pin as the nested ConvertTo type
166 template <typename LHS, typename RHS>
167 struct PinForImpl<QStringBuilder<LHS, RHS>>
168 : PinForImpl<typename QStringBuilder<LHS, RHS>::ConvertTo> {};
169
170 template <typename StringLike>
171 using PinFor = typename PinForImpl<typename std::remove_cv<StringLike>::type>::type;
172
173 template <typename T> struct is_owning_string_type : std::false_type {};
174 template <> struct is_owning_string_type<QString> : std::true_type {};
175 template <typename...Args> struct is_owning_string_type<std::basic_string<Args...>> : std::true_type {};
176
177 // unpinned
178 template <typename T, bool pinned = is_owning_string_type<T>::value>
179 struct Pinning
180 {
181 // this is the storage for non-pinned types - no storage
182 constexpr Pinning(const T&) noexcept {}
183 // Since we don't store something, the view() method needs to be
184 // given something it can return.
185 constexpr T view(T t) const noexcept { return t; }
186 };
187
188 // pinned
189 template <typename T>
190 struct Pinning<T, true>
191 {
192 T m_string;
193 // specialisation for owning string types (QString, std::u16string):
194 // stores the string:
195 constexpr Pinning(T &&s) noexcept : m_string{std::move(s)} {}
196 // ... and thus view() uses that instead of the argument passed in:
197 constexpr QStringView view(const T&) const noexcept { return m_string; }
198 };
199
200 // NeedlePinning and HaystackPinning are there to distinguish them as
201 // base classes of QStringTokenizer. We use inheritance to reap the
202 // empty base class optimization.
203 template <typename T>
204 struct NeedlePinning : Pinning<T>
205 {
206 using Pinning<T>::Pinning;
207 template <typename Arg>
208 constexpr auto needleView(Arg &&a) noexcept
209 -> decltype(this->view(std::forward<Arg>(a)))
210 { return this->view(std::forward<Arg>(a)); }
211 };
212
213 template <typename T>
214 struct HaystackPinning : Pinning<T>
215 {
216 using Pinning<T>::Pinning;
217 template <typename Arg>
218 constexpr auto haystackView(Arg &&a) noexcept
219 -> decltype(this->view(std::forward<Arg>(a)))
220 { return this->view(std::forward<Arg>(a)); }
221 };
222
223 // The Base of a QStringTokenizer is QStringTokenizerBase for the views
224 // corresponding to the Haystack and Needle template arguments
225 //
226 // ie. QStringTokenizer<QString, QString>
227 // : QStringTokenizerBase<QStringView, QStringView> (+ pinning)
228 template <typename Haystack, typename Needle>
229 using TokenizerBase = QStringTokenizerBase<ViewFor<Haystack>, ViewFor<Needle>>;
230} // namespace Tok
231} // namespace QtPrivate
232
233template <typename Haystack, typename Needle>
234class QStringTokenizer
235 : private QtPrivate::Tok::HaystackPinning<Haystack>,
236 private QtPrivate::Tok::NeedlePinning<Needle>,
237 public QtPrivate::Tok::TokenizerBase<Haystack, Needle>
238{
239 using HPin = QtPrivate::Tok::HaystackPinning<Haystack>;
240 using NPin = QtPrivate::Tok::NeedlePinning<Needle>;
241 using Base = QtPrivate::Tok::TokenizerBase<Haystack, Needle>;
242 template <typename Container, typename HPin>
243 struct if_haystack_not_pinned_impl : std::enable_if<std::is_empty<HPin>::value, bool> {};
244 template <typename Container>
245 using if_haystack_not_pinned = typename if_haystack_not_pinned_impl<Container, HPin>::type;
246 template <typename Container, typename Iterator = decltype(std::begin(std::declval<Container>()))>
247 using if_compatible_container = typename std::enable_if<
248 std::is_convertible<
249 typename Base::value_type,
250 typename std::iterator_traits<Iterator>::value_type
251 >::value,
252 bool
253 >::type;
254public:
255 using value_type = typename Base::value_type;
256 using difference_type = typename Base::difference_type;
257 using size_type = typename Base::size_type;
258 using reference = typename Base::reference;
259 using const_reference = typename Base::const_reference;
260 using pointer = typename Base::pointer;
261 using const_pointer = typename Base::const_pointer;
262 using iterator = typename Base::iterator;
263 using const_iterator = typename Base::const_iterator;
264 using sentinel = typename Base::sentinel;
265
266#ifdef Q_QDOC
267 [[nodiscard]] iterator begin() const noexcept { return Base::begin(); }
268 [[nodiscard]] iterator cbegin() const noexcept { return begin(); }
269 [[nodiscard]] constexpr sentinel end() const noexcept { return {}; }
270 [[nodiscard]] constexpr sentinel cend() const noexcept { return {}; }
271#endif
272
273 constexpr explicit QStringTokenizer(Haystack haystack, Needle needle,
274 Qt::CaseSensitivity cs,
275 Qt::SplitBehavior sb = Qt::KeepEmptyParts)
276 noexcept(std::is_nothrow_copy_constructible<QStringTokenizer>::value)
277 // here, we present the haystack to Pinning<>, for optional storing.
278 // If it did store, haystack is moved-from and mustn't be touched
279 // any longer, which is why view() for these Pinning<>s ignores the
280 // argument.
281 : HPin{std::forward<Haystack>(haystack)},
282 NPin{std::forward<Needle>(needle)},
283 // If Pinning<> didn't store, we pass the haystack (ditto needle)
284 // to view() again, so it can be copied from there.
285 Base{this->haystackView(haystack),
286 this->needleView(needle), sb, cs}
287 {}
288 constexpr explicit QStringTokenizer(Haystack haystack, Needle needle,
289 Qt::SplitBehavior sb = Qt::KeepEmptyParts,
290 Qt::CaseSensitivity cs = Qt::CaseSensitive)
291 noexcept(std::is_nothrow_copy_constructible<QStringTokenizer>::value)
292 : HPin{std::forward<Haystack>(haystack)},
293 NPin{std::forward<Needle>(needle)},
294 Base{this->haystackView(haystack),
295 this->needleView(needle), sb, cs}
296 {}
297
298#ifdef Q_QDOC
299 template<typename LContainer> LContainer toContainer(LContainer &&c = {}) const & {}
300 template<typename RContainer> RContainer toContainer(RContainer &&c = {}) const && {}
301#else
302 template<typename Container = QList<value_type>, if_compatible_container<Container> = true>
303 Container toContainer(Container &&c = {}) const &
304 {
305 for (auto e : *this)
306 c.emplace_back(e);
307 return std::forward<Container>(c);
308 }
309 template<typename Container = QList<value_type>, if_compatible_container<Container> = true,
310 if_haystack_not_pinned<Container> = true>
311 Container toContainer(Container &&c = {}) const &&
312 {
313 for (auto e : *this)
314 c.emplace_back(e);
315 return std::forward<Container>(c);
316 }
317#endif
318};
319
320namespace QtPrivate {
321namespace Tok {
322// This meta function just calculated the template arguments for the
323// QStringTokenizer (not -Base), based on the actual arguments passed
324// to qTokenize() (or the ctor, with CTAD). It basically detects rvalue
325// QString and std::basic_string and otherwise decays the arguments to
326// the respective view type.
327//
328// #define works around a C++ restriction: [temp.deduct.guide]/3 seems
329// to ask for the simple-template-id following the `->` of a deduction
330// guide to be identical to the class name for which we guide deduction.
331// In particular, Clang rejects a template alias there, while GCC accepts
332// it.
333#define Q_TOK_RESULT \
334 QStringTokenizer< \
335 QtPrivate::Tok::PinFor<Haystack>, \
336 QtPrivate::Tok::PinFor<Needle> \
337 > \
338 /*end*/
339template <typename Haystack, typename Needle>
340using TokenizerResult = Q_TOK_RESULT;
341template <typename Haystack, typename Needle>
342using is_nothrow_constructible_from = std::is_nothrow_copy_constructible<TokenizerResult<Haystack, Needle>>;
343}
344}
345
346#ifdef __cpp_deduction_guides
347// these tell the compiler how to determine the QStringTokenizer
348// template arguments based on the constructor arguments (CTAD):
349template <typename Haystack, typename Needle>
350QStringTokenizer(Haystack&&, Needle&&)
351 -> Q_TOK_RESULT;
352template <typename Haystack, typename Needle>
353QStringTokenizer(Haystack&&, Needle&&, Qt::SplitBehavior)
354 -> Q_TOK_RESULT;
355template <typename Haystack, typename Needle>
356QStringTokenizer(Haystack&&, Needle&&, Qt::SplitBehavior, Qt::CaseSensitivity)
357 -> Q_TOK_RESULT;
358template <typename Haystack, typename Needle>
359QStringTokenizer(Haystack&&, Needle&&, Qt::CaseSensitivity)
360 -> Q_TOK_RESULT;
361template <typename Haystack, typename Needle>
362QStringTokenizer(Haystack&&, Needle&&, Qt::CaseSensitivity, Qt::SplitBehavior)
363 -> Q_TOK_RESULT;
364#endif
365
366#undef Q_TOK_RESULT
367
368template <typename Haystack, typename Needle, typename...Flags>
369[[nodiscard]] constexpr auto
370qTokenize(Haystack &&h, Needle &&n, Flags...flags)
371 noexcept(QtPrivate::Tok::is_nothrow_constructible_from<Haystack, Needle>::value)
372 -> decltype(QtPrivate::Tok::TokenizerResult<Haystack, Needle>{std::forward<Haystack>(h),
373 std::forward<Needle>(n), flags...})
374{ return QtPrivate::Tok::TokenizerResult<Haystack, Needle>{std::forward<Haystack>(h),
375 std::forward<Needle>(n),
376 flags...}; }
377
378template <typename Haystack, typename Needle>
379auto QStringTokenizerBase<Haystack, Needle>::next(tokenizer_state state) const noexcept -> next_result
380{
381 while (true) {
382 if (state.end < 0) {
383 // already at end:
384 return {{}, false, state};
385 }
386 state.end = m_haystack.indexOf(m_needle, state.start + state.extra, m_cs);
387 Haystack result;
388 if (state.end >= 0) {
389 // token separator found => return intermediate element:
390 result = m_haystack.sliced(state.start, state.end - state.start);
391 const auto ns = QtPrivate::Tok::tokenSize(m_needle);
392 state.start = state.end + ns;
393 state.extra = (ns == 0 ? 1 : 0);
394 } else {
395 // token separator not found => return final element:
396 result = m_haystack.sliced(state.start);
397 }
398 if ((m_sb & Qt::SkipEmptyParts) && result.isEmpty())
399 continue;
400 return {result, true, state};
401 }
402}
403
404QT_END_NAMESPACE
405
406#endif /* QSTRINGTOKENIZER_H */
407

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