File indexing completed on 2024-05-12 03:47:19
0001 /**************************************************************************** 0002 ** MIT License 0003 ** 0004 ** Copyright (C) 2020-2022 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Marc Mutz <marc.mutz@kdab.com> 0005 ** 0006 ** This file is part of KDToolBox (https://github.com/KDAB/KDToolBox). 0007 ** 0008 ** Permission is hereby granted, free of charge, to any person obtaining a copy 0009 ** of this software and associated documentation files (the "Software"), to deal 0010 ** in the Software without restriction, including without limitation the rights 0011 ** to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 0012 ** copies of the Software, ** and to permit persons to whom the Software is 0013 ** furnished to do so, subject to the following conditions: 0014 ** 0015 ** The above copyright notice and this permission notice (including the next paragraph) 0016 ** shall be included in all copies or substantial portions of the Software. 0017 ** 0018 ** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 0019 ** IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 0020 ** FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 0021 ** AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 0022 ** LIABILITY, WHETHER IN AN ACTION OF ** CONTRACT, TORT OR OTHERWISE, 0023 ** ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 0024 ** DEALINGS IN THE SOFTWARE. 0025 ****************************************************************************/ 0026 #ifndef QSTRINGTOKENIZER_H 0027 #define QSTRINGTOKENIZER_H 0028 0029 #include <QtCore/qnamespace.h> 0030 0031 QT_BEGIN_NAMESPACE 0032 0033 template <typename, typename> class QStringBuilder; 0034 template <typename> class QVector; 0035 0036 QT_END_NAMESPACE 0037 0038 #if defined(Q_QDOC) || (defined(__cpp_range_based_for) && __cpp_range_based_for >= 201603) 0039 # define Q_STRINGTOKENIZER_USE_SENTINEL 0040 #endif 0041 0042 class QStringTokenizerBaseBase 0043 { 0044 protected: 0045 ~QStringTokenizerBaseBase() = default; 0046 Q_DECL_CONSTEXPR QStringTokenizerBaseBase(Qt::SplitBehavior sb, Qt::CaseSensitivity cs) noexcept 0047 : m_sb{sb}, m_cs{cs} {} 0048 0049 struct tokenizer_state { 0050 qsizetype start, end, extra; 0051 friend constexpr bool operator==(tokenizer_state lhs, tokenizer_state rhs) noexcept // clazy:exclude=function-args-by-ref 0052 { return lhs.start == rhs.start && lhs.end == rhs.end && lhs.extra == rhs.extra; } 0053 friend constexpr bool operator!=(tokenizer_state lhs, tokenizer_state rhs) noexcept // clazy:exclude=function-args-by-ref 0054 { return !operator==(lhs, rhs); } 0055 }; 0056 0057 Qt::SplitBehavior m_sb; 0058 Qt::CaseSensitivity m_cs; 0059 }; 0060 0061 template <typename Haystack, typename Needle> 0062 class QStringTokenizerBase : protected QStringTokenizerBaseBase 0063 { 0064 struct next_result { 0065 Haystack value; 0066 bool ok; 0067 tokenizer_state state; 0068 }; 0069 inline next_result next(tokenizer_state state) const noexcept; 0070 inline next_result toFront() const noexcept { return next({}); } 0071 public: 0072 constexpr explicit QStringTokenizerBase(Haystack haystack, Needle needle, Qt::SplitBehavior sb, Qt::CaseSensitivity cs) noexcept 0073 : QStringTokenizerBaseBase{sb, cs}, m_haystack{haystack}, m_needle{needle} {} 0074 0075 class iterator; 0076 friend class iterator; 0077 #ifdef Q_STRINGTOKENIZER_USE_SENTINEL 0078 class sentinel { 0079 friend constexpr bool operator==(sentinel, sentinel) noexcept { return true; } 0080 friend constexpr bool operator!=(sentinel, sentinel) noexcept { return false; } 0081 }; 0082 #else 0083 using sentinel = iterator; 0084 #endif 0085 class iterator { 0086 const QStringTokenizerBase *tokenizer; 0087 next_result current; 0088 friend class QStringTokenizerBase; 0089 explicit iterator(const QStringTokenizerBase &t) noexcept 0090 : tokenizer{&t}, current{t.toFront()} {} 0091 public: 0092 using difference_type = qsizetype; 0093 using value_type = Haystack; 0094 using pointer = const value_type*; 0095 using reference = const value_type&; 0096 using iterator_category = std::forward_iterator_tag; 0097 0098 iterator() noexcept = default; 0099 0100 // violates std::forward_iterator (returns a reference into the iterator) 0101 Q_REQUIRED_RESULT constexpr const Haystack* operator->() const { return Q_ASSERT(current.ok), ¤t.value; } 0102 Q_REQUIRED_RESULT constexpr const Haystack& operator*() const { return *operator->(); } 0103 0104 iterator& operator++() { advance(); return *this; } 0105 iterator operator++(int) { auto tmp = *this; advance(); return tmp; } 0106 0107 friend constexpr bool operator==(const iterator &lhs, const iterator &rhs) noexcept 0108 { return lhs.current.ok == rhs.current.ok && (!lhs.current.ok || (Q_ASSERT(lhs.tokenizer == rhs.tokenizer), lhs.current.state == rhs.current.state)); } 0109 friend constexpr bool operator!=(const iterator &lhs, const iterator &rhs) noexcept 0110 { return !operator==(lhs, rhs); } 0111 #ifdef Q_STRINGTOKENIZER_USE_SENTINEL 0112 friend constexpr bool operator==(const iterator &lhs, sentinel) noexcept 0113 { return !lhs.current.ok; } 0114 friend constexpr bool operator!=(const iterator &lhs, sentinel) noexcept 0115 { return !operator==(lhs, sentinel{}); } 0116 friend constexpr bool operator==(sentinel, const iterator &rhs) noexcept 0117 { return !rhs.current.ok; } 0118 friend constexpr bool operator!=(sentinel, const iterator &rhs) noexcept 0119 { return !operator==(sentinel{}, rhs); } 0120 #endif 0121 private: 0122 void advance() { 0123 Q_ASSERT(current.ok); 0124 current = tokenizer->next(current.state); 0125 } 0126 }; 0127 using const_iterator = iterator; 0128 0129 using size_type = std::size_t; 0130 using difference_type = typename iterator::difference_type; 0131 using value_type = typename iterator::value_type; 0132 using pointer = typename iterator::pointer; 0133 using const_pointer = pointer; 0134 using reference = typename iterator::reference; 0135 using const_reference = reference; 0136 0137 Q_REQUIRED_RESULT iterator begin() const noexcept { return iterator{*this}; } 0138 Q_REQUIRED_RESULT iterator cbegin() const noexcept { return begin(); } 0139 template <bool = std::is_same<iterator, sentinel>::value> // ODR protection 0140 Q_REQUIRED_RESULT constexpr sentinel end() const noexcept { return {}; } 0141 template <bool = std::is_same<iterator, sentinel>::value> // ODR protection 0142 Q_REQUIRED_RESULT constexpr sentinel cend() const noexcept { return {}; } 0143 0144 private: 0145 Haystack m_haystack; 0146 Needle m_needle; 0147 }; 0148 0149 #include <QtCore/qstringview.h> 0150 0151 namespace QtPrivate { 0152 namespace Tok { 0153 0154 Q_DECL_CONSTEXPR qsizetype size(QChar) noexcept { return 1; } 0155 template <typename String> 0156 constexpr qsizetype size(const String &s) noexcept { return static_cast<qsizetype>(s.size()); } 0157 0158 template <typename String> struct ViewForImpl {}; 0159 template <> struct ViewForImpl<QStringView> { using type = QStringView; }; 0160 template <> struct ViewForImpl<QLatin1String> { using type = QLatin1String; }; 0161 template <> struct ViewForImpl<QChar> { using type = QChar; }; 0162 template <> struct ViewForImpl<QString> : ViewForImpl<QStringView> {}; 0163 template <> struct ViewForImpl<QStringRef> : ViewForImpl<QStringView> {}; 0164 template <> struct ViewForImpl<QLatin1Char> : ViewForImpl<QChar> {}; 0165 template <> struct ViewForImpl<char16_t> : ViewForImpl<QChar> {}; 0166 template <> struct ViewForImpl<char16_t*> : ViewForImpl<QStringView> {}; 0167 template <> struct ViewForImpl<const char16_t*> : ViewForImpl<QStringView> {}; 0168 #if QT_VERSION >= QT_VERSION_CHECK(5, 15, 0) 0169 template <typename LHS, typename RHS> 0170 struct ViewForImpl<QStringBuilder<LHS, RHS>> : ViewForImpl<typename QStringBuilder<LHS,RHS>::ConvertTo> {}; 0171 #endif 0172 template <typename Char, typename...Args> 0173 struct ViewForImpl<std::basic_string<Char, Args...>> : ViewForImpl<Char*> {}; 0174 #ifdef __cpp_lib_string_view 0175 template <typename Char, typename...Args> 0176 struct ViewForImpl<std::basic_string_view<Char, Args...>> : ViewForImpl<Char*> {}; 0177 #endif 0178 0179 // This metafunction maps a StringLike to a View (currently, QChar, 0180 // QStringView, QLatin1String). This is what QStringTokenizerBase 0181 // operates on. QStringTokenizer adds pinning to keep rvalues alive 0182 // for the duration of the algorithm. 0183 template <typename String> 0184 using ViewFor = typename ViewForImpl<typename std::decay<String>::type>::type; 0185 0186 // Pinning: 0187 // rvalues of owning string types need to be moved into QStringTokenizer 0188 // to keep them alive for the lifetime of the tokenizer. For lvalues, we 0189 // assume the user takes care of that. 0190 0191 // default: don't pin anything (characters are pinned implicitly) 0192 template <typename String> 0193 struct PinForImpl { using type = ViewFor<String>; }; 0194 0195 // rvalue QString -> QString 0196 template <> 0197 struct PinForImpl<QString> { using type = QString; }; 0198 0199 // rvalue std::basic_string -> basic_string 0200 template <typename Char, typename...Args> 0201 struct PinForImpl<std::basic_string<Char, Args...>> 0202 { using type = std::basic_string<Char, Args...>; }; 0203 0204 // rvalue QStringBuilder -> pin as the nested ConvertTo type 0205 template <typename LHS, typename RHS> 0206 struct PinForImpl<QStringBuilder<LHS, RHS>> 0207 : PinForImpl<typename QStringBuilder<LHS, RHS>::ConvertTo> {}; 0208 0209 template <typename StringLike> 0210 using PinFor = typename PinForImpl<typename std::remove_cv<StringLike>::type>::type; 0211 0212 template <typename T> struct is_owning_string_type : std::false_type {}; 0213 template <> struct is_owning_string_type<QString> : std::true_type {}; 0214 template <typename...Args> struct is_owning_string_type<std::basic_string<Args...>> : std::true_type {}; 0215 0216 // unpinned 0217 template <typename T, bool pinned = is_owning_string_type<T>::value> 0218 struct Pinning 0219 { 0220 // this is the storage for non-pinned types - no storage 0221 constexpr Pinning(const T&) noexcept {} 0222 // Since we don't store something, the view() method needs to be 0223 // given something it can return. 0224 constexpr T view(T t) const noexcept { return t; } 0225 }; 0226 0227 // pinned 0228 template <typename T> 0229 struct Pinning<T, true> 0230 { 0231 T m_string; 0232 // specialisation for owning string types (QString, std::u16string): 0233 // stores the string: 0234 constexpr Pinning(T &&s) noexcept : m_string{std::move(s)} {} 0235 // ... and thus view() uses that instead of the argument passed in: 0236 constexpr QStringView view(const T&) const noexcept { return m_string; } 0237 }; 0238 0239 // NeedlePinning and HaystackPinning are there to distinguish them as 0240 // base classes of QStringTokenizer. We use inheritance to reap the 0241 // empty base class optimization. 0242 template <typename T> 0243 struct NeedlePinning : Pinning<T> 0244 { 0245 using Pinning<T>::Pinning; 0246 template <typename Arg> 0247 constexpr auto needleView(Arg &&a) const noexcept 0248 -> decltype(this->view(std::forward<Arg>(a))) 0249 { return this->view(std::forward<Arg>(a)); } 0250 }; 0251 0252 template <typename T> 0253 struct HaystackPinning : Pinning<T> 0254 { 0255 using Pinning<T>::Pinning; 0256 template <typename Arg> 0257 constexpr auto haystackView(Arg &&a) const noexcept 0258 -> decltype(this->view(std::forward<Arg>(a))) 0259 { return this->view(std::forward<Arg>(a)); } 0260 }; 0261 0262 // The Base of a QStringTokenizer is QStringTokenizerBase for the views 0263 // corresponding to the Haystack and Needle template arguments 0264 // 0265 // ie. QStringTokenizer<QString, QString> 0266 // : QStringTokenizerBase<QStringView, QStringView> (+ pinning) 0267 template <typename Haystack, typename Needle> 0268 using TokenizerBase = QStringTokenizerBase<ViewFor<Haystack>, ViewFor<Needle>>; 0269 } // namespace Tok 0270 } // namespace QtPrivate 0271 0272 template <typename Haystack, typename Needle> 0273 class QStringTokenizer 0274 : private QtPrivate::Tok::HaystackPinning<Haystack>, 0275 private QtPrivate::Tok::NeedlePinning<Needle>, 0276 public QtPrivate::Tok::TokenizerBase<Haystack, Needle> 0277 { 0278 using HPin = QtPrivate::Tok::HaystackPinning<Haystack>; 0279 using NPin = QtPrivate::Tok::NeedlePinning<Needle>; 0280 using Base = QtPrivate::Tok::TokenizerBase<Haystack, Needle>; 0281 template <typename Container, typename HPin> 0282 struct if_haystack_not_pinned_impl : std::enable_if<std::is_empty<HPin>::value, bool> {}; 0283 template <typename Container> 0284 using if_haystack_not_pinned = typename if_haystack_not_pinned_impl<Container, HPin>::type; 0285 template <typename Container, typename Iterator = decltype(std::begin(std::declval<Container>()))> 0286 using if_compatible_container = typename std::enable_if< 0287 std::is_same< 0288 typename Base::value_type, 0289 typename std::iterator_traits<Iterator>::value_type 0290 >::value, 0291 bool 0292 >::type; 0293 public: 0294 using value_type = typename Base::value_type; 0295 0296 constexpr explicit QStringTokenizer(Haystack haystack, Needle needle, 0297 Qt::CaseSensitivity cs, 0298 Qt::SplitBehavior sb = Qt::KeepEmptyParts) 0299 // here, we present the haystack to Pinning<>, for optional storing. 0300 // If it did store, haystack is moved-from and mustn't be touched 0301 // any longer, which is why view() for these Pinning<>s ignores the 0302 // argument. 0303 : HPin{std::forward<Haystack>(haystack)}, 0304 NPin{std::forward<Needle>(needle)}, 0305 // If Pinning<> didn't store, we pass the haystack (ditto needle) 0306 // to view() again, so it can be copied from there. 0307 Base{this->haystackView(haystack), 0308 this->needleView(needle), sb, cs} 0309 {} 0310 constexpr explicit QStringTokenizer(Haystack haystack, Needle needle, 0311 Qt::SplitBehavior sb = Qt::KeepEmptyParts, 0312 Qt::CaseSensitivity cs = Qt::CaseSensitive) 0313 : HPin{std::forward<Haystack>(haystack)}, 0314 NPin{std::forward<Needle>(needle)}, 0315 Base{this->haystackView(haystack), 0316 this->needleView(needle), sb, cs} 0317 {} 0318 0319 template <typename Container = QVector<value_type>, 0320 if_compatible_container<Container> = true> 0321 Container toContainer(Container &&c = {}) const & 0322 { 0323 for (auto e : *this) 0324 c.push_back(e); 0325 return std::forward<Container>(c); 0326 } 0327 0328 template <typename Container = QVector<value_type>, 0329 if_compatible_container<Container> = true, 0330 if_haystack_not_pinned<Container> = true> 0331 Container toContainer(Container &&c = {}) const && 0332 { 0333 for (auto e : *this) 0334 c.push_back(e); 0335 return std::forward<Container>(c); 0336 } 0337 }; 0338 0339 namespace QtPrivate { 0340 namespace Tok { 0341 // This meta function just calculated the template arguments for the 0342 // QStringTokenizer (not -Base), based on the actual arguments passed 0343 // to qTokenize() (or the ctor, with CTAD). It basically detects rvalue 0344 // QString and std::basic_string and otherwise decays the arguments to 0345 // the respective view type. 0346 // 0347 // #define works around a C++ restriction: [temp.deduct.guide]/3 seems 0348 // to ask for the simple-template-id following the `->` of a deduction 0349 // guide to be identical to the class name for which we guide deduction. 0350 // In particular, Clang rejects a template alias there, while GCC accepts 0351 // it. 0352 #define Q_TOK_RESULT \ 0353 QStringTokenizer< \ 0354 QtPrivate::Tok::PinFor<Haystack>, \ 0355 QtPrivate::Tok::PinFor<Needle> \ 0356 > \ 0357 /*end*/ 0358 template <typename Haystack, typename Needle> 0359 using TokenizerResult = Q_TOK_RESULT; 0360 template <typename Haystack, typename Needle> 0361 using is_nothrow_constructible_from = std::is_nothrow_copy_constructible<TokenizerResult<Haystack, Needle>>; 0362 } 0363 } 0364 0365 #ifdef __cpp_deduction_guides 0366 // these tell the compiler how to determine the QStringTokenizer 0367 // template arguments based on the constructor arguments (CTAD): 0368 template <typename Haystack, typename Needle> 0369 QStringTokenizer(Haystack&&, Needle&&) 0370 -> Q_TOK_RESULT; 0371 template <typename Haystack, typename Needle> 0372 QStringTokenizer(Haystack&&, Needle&&, Qt::SplitBehavior) 0373 -> Q_TOK_RESULT; 0374 template <typename Haystack, typename Needle> 0375 QStringTokenizer(Haystack&&, Needle&&, Qt::SplitBehavior, Qt::CaseSensitivity) 0376 -> Q_TOK_RESULT; 0377 template <typename Haystack, typename Needle> 0378 QStringTokenizer(Haystack&&, Needle&&, Qt::CaseSensitivity) 0379 -> Q_TOK_RESULT; 0380 template <typename Haystack, typename Needle> 0381 QStringTokenizer(Haystack&&, Needle&&, Qt::CaseSensitivity, Qt::SplitBehavior) 0382 -> Q_TOK_RESULT; 0383 #endif 0384 0385 #undef Q_TOK_RESULT 0386 0387 template <typename Haystack, typename Needle, typename...Flags> 0388 Q_REQUIRED_RESULT constexpr auto 0389 qTokenize(Haystack &&h, Needle &&n, Flags...flags) 0390 -> decltype(QtPrivate::Tok::TokenizerResult<Haystack, Needle>{std::forward<Haystack>(h), 0391 std::forward<Needle>(n), flags...}) 0392 { return QtPrivate::Tok::TokenizerResult<Haystack, Needle>{std::forward<Haystack>(h), 0393 std::forward<Needle>(n), 0394 flags...}; } 0395 0396 template <typename Haystack, typename Needle> 0397 auto QStringTokenizerBase<Haystack, Needle>::next(tokenizer_state state) const noexcept -> next_result 0398 { 0399 while (true) { 0400 if (state.end < 0) { 0401 // already at end: 0402 return {{}, false, state}; 0403 } 0404 state.end = m_haystack.indexOf(m_needle, state.start + state.extra, m_cs); 0405 Haystack result; 0406 if (state.end >= 0) { 0407 // token separator found => return intermediate element: 0408 result = m_haystack.mid(state.start, state.end - state.start); 0409 const auto ns = QtPrivate::Tok::size(m_needle); 0410 state.start = state.end + ns; 0411 state.extra = (ns == 0 ? 1 : 0); 0412 } else { 0413 // token separator not found => return final element: 0414 result = m_haystack.mid(state.start); 0415 } 0416 if ((m_sb & Qt::SkipEmptyParts) && result.isEmpty()) 0417 continue; 0418 return {result, true, state}; 0419 } 0420 } 0421 0422 #endif /* QSTRINGTOKENIZER_H */