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

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