url/grammar/lut_chars.hpp

0001 //
0002 // Copyright (c) 2021 Vinnie Falco (vinnie dot falco at gmail dot com)
0003 //
0004 // Distributed under the Boost Software License, Version 1.0. (See accompanying
0005 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 //
0007 // Official repository: https://github.com/boostorg/url
0008 //
0009
0010 #ifndef BOOST_URL_GRAMMAR_LUT_CHARS_HPP
0011 #define BOOST_URL_GRAMMAR_LUT_CHARS_HPP
0012
0013 #include <boost/url/detail/config.hpp>
0014 #include <boost/url/grammar/detail/charset.hpp>
0015 #include <cstdint>
0016 #include <type_traits>
0017
0018 // Credit to Peter Dimov for ideas regarding
0019 // SIMD constexpr, and character set masks.
0020
0021 namespace boost {
0022 namespace urls {
0023 namespace grammar {
0024
0025 #ifndef BOOST_URL_DOCS
0026 namespace detail {
0027 template<class T, class = void>
0028 struct is_pred : std::false_type {};
0029
0030 template<class T>
0031 struct is_pred<T, void_t<
0032     decltype(
0033     std::declval<bool&>() =
0034         std::declval<T const&>().operator()(
0035             std::declval<char>())
0036             ) > > : std::true_type
0037 {
0038 };
0039 } // detail
0040 #endif
0041
0042 /** A set of characters
0043
0044     The characters defined by instances of
0045     this set are provided upon construction.
0046     The `constexpr` implementation allows
0047     these to become compile-time constants.
0048
0049     @par Example
0050     Character sets are used with rules and the
0051     functions @ref find_if and @ref find_if_not.
0052     @code
0053     constexpr lut_chars vowel_chars = "AEIOU" "aeiou";
0054
0055     system::result< core::string_view > rv = parse( "Aiea", token_rule( vowel_chars ) );
0056     @endcode
0057
0058     @see
0059         @ref find_if,
0060         @ref find_if_not,
0061         @ref parse,
0062         @ref token_rule.
0063 */
0064 class lut_chars
0065 {
0066     std::uint64_t mask_[4] = {};
0067
0068     constexpr
0069     static
0070     std::uint64_t
0071     lo(char c) noexcept
0072     {
0073         return static_cast<
0074             unsigned char>(c) & 3;
0075     }
0076
0077     constexpr
0078     static
0079     std::uint64_t
0080     hi(char c) noexcept
0081     {
0082         return 1ULL << (static_cast<
0083             unsigned char>(c) >> 2);
0084     }
0085
0086     constexpr
0087     static
0088     lut_chars
0089     construct(
0090         char const* s) noexcept
0091     {
0092         return *s
0093             ? lut_chars(*s) +
0094                 construct(s+1)
0095             : lut_chars();
0096     }
0097
0098     constexpr
0099     static
0100     lut_chars
0101     construct(
0102         unsigned char ch,
0103         bool b) noexcept
0104     {
0105         return b
0106             ? lut_chars(ch)
0107             : lut_chars();
0108     }
0109
0110     template<class Pred>
0111     constexpr
0112     static
0113     lut_chars
0114     construct(
0115         Pred pred,
0116         unsigned char ch) noexcept
0117     {
0118         return ch == 255
0119             ? construct(ch, pred(static_cast<char>(ch)))
0120             : construct(ch, pred(static_cast<char>(ch))) +
0121                 construct(pred, ch + 1);
0122     }
0123
0124     constexpr
0125     lut_chars() = default;
0126
0127     constexpr
0128     lut_chars(
0129         std::uint64_t m0,
0130         std::uint64_t m1,
0131         std::uint64_t m2,
0132         std::uint64_t m3) noexcept
0133         : mask_{ m0, m1, m2, m3 }
0134     {
0135     }
0136
0137 public:
0138     /** Constructor
0139
0140         This function constructs a character
0141         set which has as a single member,
0142         the character `ch`.
0143
0144         @par Example
0145         @code
0146         constexpr lut_chars asterisk( '*' );
0147         @endcode
0148
0149         @par Complexity
0150         Constant.
0151
0152         @par Exception Safety
0153         Throws nothing.
0154
0155         @param ch A character.
0156     */
0157     constexpr
0158     lut_chars(char ch) noexcept
0159         : mask_ {
0160             lo(ch) == 0 ? hi(ch) : 0,
0161             lo(ch) == 1 ? hi(ch) : 0,
0162             lo(ch) == 2 ? hi(ch) : 0,
0163             lo(ch) == 3 ? hi(ch) : 0 }
0164     {
0165     }
0166
0167     /** Constructor
0168
0169         This function constructs a character
0170         set which has as members, all of the
0171         characters present in the null-terminated
0172         string `s`.
0173
0174         @par Example
0175         @code
0176         constexpr lut_chars digits = "0123456789";
0177         @endcode
0178
0179         @par Complexity
0180         Linear in `::strlen(s)`, or constant
0181         if `s` is a constant expression.
0182
0183         @par Exception Safety
0184         Throws nothing.
0185
0186         @param s A null-terminated string.
0187     */
0188     constexpr
0189     lut_chars(
0190         char const* s) noexcept
0191         : lut_chars(construct(s))
0192     {
0193     }
0194
0195     /** Constructor.
0196
0197         This function constructs a character
0198         set which has as members, every value
0199         of `char ch` for which the expression
0200         `pred(ch)` returns `true`.
0201
0202         @par Example
0203         @code
0204         struct is_digit
0205         {
0206             constexpr bool
0207             operator()(char c ) const noexcept
0208             {
0209                 return c >= '0' && c <= '9';
0210             }
0211         };
0212
0213         constexpr lut_chars digits( is_digit{} );
0214         @endcode
0215
0216         @par Complexity
0217         Linear in `pred`, or constant if
0218         `pred(ch)` is a constant expression.
0219
0220         @par Exception Safety
0221         Throws nothing.
0222
0223         @param pred The function object to
0224         use for determining membership in
0225         the character set.
0226     */
0227     template<class Pred
0228 #ifndef BOOST_URL_DOCS
0229         ,class = typename std::enable_if<
0230             detail::is_pred<Pred>::value &&
0231         ! std::is_base_of<
0232             lut_chars, Pred>::value>::type
0233 #endif
0234     >
0235     constexpr
0236     lut_chars(Pred const& pred) noexcept
0237         : lut_chars(
0238             construct(pred, 0))
0239     {
0240     }
0241
0242     /** Return true if ch is in the character set.
0243
0244         This function returns true if the
0245         character `ch` is in the set, otherwise
0246         it returns false.
0247
0248         @par Complexity
0249         Constant.
0250
0251         @par Exception Safety
0252         Throws nothing.
0253
0254         @param ch The character to test.
0255     */
0256     constexpr
0257     bool
0258     operator()(
0259         unsigned char ch) const noexcept
0260     {
0261         return operator()(static_cast<char>(ch));
0262     }
0263
0264     /// @copydoc operator()(unsigned char) const
0265     constexpr
0266     bool
0267     operator()(char ch) const noexcept
0268     {
0269         return mask_[lo(ch)] & hi(ch);
0270     }
0271
0272     /** Return the union of two character sets.
0273
0274         This function returns a new character
0275         set which contains all of the characters
0276         in `cs0` as well as all of the characters
0277         in `cs`.
0278
0279         @par Example
0280         This creates a character set which
0281         includes all letters and numbers
0282         @code
0283         constexpr lut_chars alpha_chars(
0284             "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
0285             "abcdefghijklmnopqrstuvwxyz");
0286
0287         constexpr lut_chars alnum_chars = alpha_chars + "0123456789";
0288         @endcode
0289
0290         @par Complexity
0291         Constant.
0292
0293         @return The new character set.
0294
0295         @param cs0 A character to join
0296
0297         @param cs1 A character to join
0298     */
0299     friend
0300     constexpr
0301     lut_chars
0302     operator+(
0303         lut_chars const& cs0,
0304         lut_chars const& cs1) noexcept
0305     {
0306         return lut_chars(
0307             cs0.mask_[0] | cs1.mask_[0],
0308             cs0.mask_[1] | cs1.mask_[1],
0309             cs0.mask_[2] | cs1.mask_[2],
0310             cs0.mask_[3] | cs1.mask_[3]);
0311     }
0312
0313     /** Return a new character set by subtracting
0314
0315         This function returns a new character
0316         set which is formed from all of the
0317         characters in `cs0` which are not in `cs`.
0318
0319         @par Example
0320         This statement declares a character set
0321         containing all the lowercase letters
0322         which are not vowels:
0323         @code
0324         constexpr lut_chars consonants = lut_chars("abcdefghijklmnopqrstuvwxyz") - "aeiou";
0325         @endcode
0326
0327         @par Complexity
0328         Constant.
0329
0330         @return The new character set.
0331
0332         @param cs0 A character set to join.
0333
0334         @param cs1 A character set to join.
0335     */
0336     friend
0337     constexpr
0338     lut_chars
0339     operator-(
0340         lut_chars const& cs0,
0341         lut_chars const& cs1) noexcept
0342     {
0343         return lut_chars(
0344             cs0.mask_[0] & ~cs1.mask_[0],
0345             cs0.mask_[1] & ~cs1.mask_[1],
0346             cs0.mask_[2] & ~cs1.mask_[2],
0347             cs0.mask_[3] & ~cs1.mask_[3]);
0348     }
0349
0350     /** Return a new character set which is the complement of another character set.
0351
0352         This function returns a new character
0353         set which contains all of the characters
0354         that are not in `*this`.
0355
0356         @par Example
0357         This statement declares a character set
0358         containing everything but vowels:
0359         @code
0360         constexpr lut_chars not_vowels = ~lut_chars( "AEIOU" "aeiou" );
0361         @endcode
0362
0363         @par Complexity
0364         Constant.
0365
0366         @par Exception Safety
0367         Throws nothing.
0368
0369         @return The new character set.
0370     */
0371     constexpr
0372     lut_chars
0373     operator~() const noexcept
0374     {
0375         return lut_chars(
0376             ~mask_[0],
0377             ~mask_[1],
0378             ~mask_[2],
0379             ~mask_[3]
0380         );
0381     }
0382
0383 #ifndef BOOST_URL_DOCS
0384 #ifdef BOOST_URL_USE_SSE2
0385     char const*
0386     find_if(
0387         char const* first,
0388         char const* last) const noexcept
0389     {
0390         return detail::find_if_pred(
0391             *this, first, last);
0392     }
0393
0394     char const*
0395     find_if_not(
0396         char const* first,
0397         char const* last) const noexcept
0398     {
0399         return detail::find_if_not_pred(
0400             *this, first, last);
0401     }
0402 #endif
0403 #endif
0404 };
0405
0406 } // grammar
0407 } // urls
0408 } // boost
0409
0410 #endif