primitives/impl/numerics.ipp

0001 /*=============================================================================
0002     Copyright (c) 1998-2003 Joel de Guzman
0003     Copyright (c) 2001-2003 Hartmut Kaiser
0004     http://spirit.sourceforge.net/
0005
0006     Use, modification and distribution is subject to the Boost Software
0007     License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0008     http://www.boost.org/LICENSE_1_0.txt)
0009 =============================================================================*/
0010 #ifndef BOOST_SPIRIT_NUMERICS_IPP
0011 #define BOOST_SPIRIT_NUMERICS_IPP
0012
0013 #include <boost/config/no_tr1/cmath.hpp>
0014 #include <limits>
0015
0016 namespace boost { namespace spirit {
0017
0018 BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
0019
0020     struct sign_parser; // forward declaration only
0021
0022     namespace impl
0023     {
0024         ///////////////////////////////////////////////////////////////////////
0025         //
0026         //  Extract the prefix sign (- or +)
0027         //
0028         ///////////////////////////////////////////////////////////////////////
0029         template <typename ScannerT>
0030         bool
0031         extract_sign(ScannerT const& scan, std::size_t& count)
0032         {
0033             //  Extract the sign
0034             count = 0;
0035             bool neg = *scan == '-';
0036             if (neg || (*scan == '+'))
0037             {
0038                 ++scan;
0039                 ++count;
0040                 return neg;
0041             }
0042
0043             return false;
0044         }
0045
0046         ///////////////////////////////////////////////////////////////////////
0047         //
0048         //  Traits class for radix specific number conversion
0049         //
0050         //      Convert a digit from character representation, ch, to binary
0051         //      representation, returned in val.
0052         //      Returns whether the conversion was successful.
0053         //
0054         //        template<typename CharT> static bool digit(CharT ch, T& val);
0055         //
0056         ///////////////////////////////////////////////////////////////////////
0057         template<const int Radix>
0058         struct radix_traits;
0059
0060         ////////////////////////////////// Binary
0061         template<>
0062         struct radix_traits<2>
0063         {
0064             template<typename CharT, typename T>
0065             static bool digit(CharT ch, T& val)
0066             {
0067                 val = ch - '0';
0068                 return ('0' == ch || '1' == ch);
0069             }
0070         };
0071
0072         ////////////////////////////////// Octal
0073         template<>
0074         struct radix_traits<8>
0075         {
0076             template<typename CharT, typename T>
0077             static bool digit(CharT ch, T& val)
0078             {
0079                 val = ch - '0';
0080                 return ('0' <= ch && ch <= '7');
0081             }
0082         };
0083
0084         ////////////////////////////////// Decimal
0085         template<>
0086         struct radix_traits<10>
0087         {
0088             template<typename CharT, typename T>
0089             static bool digit(CharT ch, T& val)
0090             {
0091                 val = ch - '0';
0092                 return impl::isdigit_(ch);
0093             }
0094         };
0095
0096         ////////////////////////////////// Hexadecimal
0097         template<>
0098         struct radix_traits<16>
0099         {
0100             template<typename CharT, typename T>
0101             static bool digit(CharT ch, T& val)
0102             {
0103                 if (radix_traits<10>::digit(ch, val))
0104                     return true;
0105
0106                 CharT lc = impl::tolower_(ch);
0107                 if ('a' <= lc && lc <= 'f')
0108                 {
0109                     val = lc - 'a' + 10;
0110                     return true;
0111                 }
0112                 return false;
0113             }
0114         };
0115
0116         ///////////////////////////////////////////////////////////////////////
0117         //
0118         //      Helper templates for encapsulation of radix specific
0119         //      conversion of an input string to an integral value.
0120         //
0121         //      main entry point:
0122         //
0123         //          extract_int<Radix, MinDigits, MaxDigits, Accumulate>
0124         //              ::f(first, last, n, count);
0125         //
0126         //          The template parameter Radix represents the radix of the
0127         //          number contained in the parsed string. The template
0128         //          parameter MinDigits specifies the minimum digits to
0129         //          accept. The template parameter MaxDigits specifies the
0130         //          maximum digits to parse. A -1 value for MaxDigits will
0131         //          make it parse an arbitrarilly large number as long as the
0132         //          numeric type can hold it. Accumulate is either
0133         //          positive_accumulate<Radix> (default) for parsing positive
0134         //          numbers or negative_accumulate<Radix> otherwise.
0135         //          Checking is only performed when std::numeric_limits<T>::
0136         //          is_specialized is true. Otherwise, there's no way to
0137         //          do the check.
0138         //
0139         //          scan.first and scan.last are iterators as usual (i.e.
0140         //          first is mutable and is moved forward when a match is
0141         //          found), n is a variable that holds the number (passed by
0142         //          reference). The number of parsed characters is added to
0143         //          count (also passed by reference)
0144         //
0145         //      NOTE:
0146         //              Returns a non-match, if the number to parse
0147         //              overflows (or underflows) the used type.
0148         //
0149         //      BEWARE:
0150         //              the parameters 'n' and 'count' should be properly
0151         //              initialized before calling this function.
0152         //
0153         ///////////////////////////////////////////////////////////////////////
0154 #if defined(BOOST_MSVC)
0155 #pragma warning(push)
0156 #pragma warning(disable:4127) //conditional expression is constant
0157 #endif
0158
0159         template <typename T, int Radix>
0160         struct positive_accumulate
0161         {
0162             //  Use this accumulator if number is positive
0163             static bool add(T& n, T digit)
0164             {
0165                 if (std::numeric_limits<T>::is_specialized)
0166                 {
0167                     static T const max = (std::numeric_limits<T>::max)();
0168                     static T const max_div_radix = max/Radix;
0169
0170                     if (n > max_div_radix)
0171                         return false;
0172                     n *= Radix;
0173
0174                     if (n > max - digit)
0175                         return false;
0176                     n += digit;
0177
0178                     return true;
0179                 }
0180                 else
0181                 {
0182                     n *= Radix;
0183                     n += digit;
0184                     return true;
0185                 }
0186             }
0187         };
0188
0189         template <typename T, int Radix>
0190         struct negative_accumulate
0191         {
0192             //  Use this accumulator if number is negative
0193             static bool add(T& n, T digit)
0194             {
0195                 if (std::numeric_limits<T>::is_specialized)
0196                 {
0197                     typedef std::numeric_limits<T> num_limits;
0198                     static T const min =
0199                         (!num_limits::is_integer && num_limits::is_signed && num_limits::has_denorm) ?
0200                         -(num_limits::max)() : (num_limits::min)();
0201                     static T const min_div_radix = min/Radix;
0202
0203                     if (n < min_div_radix)
0204                         return false;
0205                     n *= Radix;
0206
0207                     if (n < min + digit)
0208                         return false;
0209                     n -= digit;
0210
0211                     return true;
0212                 }
0213                 else
0214                 {
0215                     n *= Radix;
0216                     n -= digit;
0217                     return true;
0218                 }
0219             }
0220         };
0221
0222         template <int MaxDigits>
0223         inline bool allow_more_digits(std::size_t i)
0224         {
0225             return i < MaxDigits;
0226         }
0227
0228         template <>
0229         inline bool allow_more_digits<-1>(std::size_t)
0230         {
0231             return true;
0232         }
0233
0234         //////////////////////////////////
0235         template <
0236             int Radix, unsigned MinDigits, int MaxDigits,
0237             typename Accumulate
0238         >
0239         struct extract_int
0240         {
0241             template <typename ScannerT, typename T>
0242             static bool
0243             f(ScannerT& scan, T& n, std::size_t& count)
0244             {
0245                 std::size_t i = 0;
0246                 T digit;
0247                 while( allow_more_digits<MaxDigits>(i) && !scan.at_end() &&
0248                     radix_traits<Radix>::digit(*scan, digit) )
0249                 {
0250                     if (!Accumulate::add(n, digit))
0251                         return false; // Overflow
0252                     ++i, ++scan, ++count;
0253                 }
0254                 return i >= MinDigits;
0255             }
0256         };
0257
0258         ///////////////////////////////////////////////////////////////////////
0259         //
0260         //  uint_parser_impl class
0261         //
0262         ///////////////////////////////////////////////////////////////////////
0263         template <
0264             typename T = unsigned,
0265             int Radix = 10,
0266             unsigned MinDigits = 1,
0267             int MaxDigits = -1
0268         >
0269         struct uint_parser_impl
0270             : parser<uint_parser_impl<T, Radix, MinDigits, MaxDigits> >
0271         {
0272             typedef uint_parser_impl<T, Radix, MinDigits, MaxDigits> self_t;
0273
0274             template <typename ScannerT>
0275             struct result
0276             {
0277                 typedef typename match_result<ScannerT, T>::type type;
0278             };
0279
0280             template <typename ScannerT>
0281             typename parser_result<self_t, ScannerT>::type
0282             parse(ScannerT const& scan) const
0283             {
0284                 if (!scan.at_end())
0285                 {
0286                     T n = 0;
0287                     std::size_t count = 0;
0288                     typename ScannerT::iterator_t save = scan.first;
0289                     if (extract_int<Radix, MinDigits, MaxDigits,
0290                         positive_accumulate<T, Radix> >::f(scan, n, count))
0291                     {
0292                         return scan.create_match(count, n, save, scan.first);
0293                     }
0294                     // return no-match if number overflows
0295                 }
0296                 return scan.no_match();
0297             }
0298         };
0299
0300         ///////////////////////////////////////////////////////////////////////
0301         //
0302         //  int_parser_impl class
0303         //
0304         ///////////////////////////////////////////////////////////////////////
0305         template <
0306             typename T = unsigned,
0307             int Radix = 10,
0308             unsigned MinDigits = 1,
0309             int MaxDigits = -1
0310         >
0311         struct int_parser_impl
0312             : parser<int_parser_impl<T, Radix, MinDigits, MaxDigits> >
0313         {
0314             typedef int_parser_impl<T, Radix, MinDigits, MaxDigits> self_t;
0315
0316             template <typename ScannerT>
0317             struct result
0318             {
0319                 typedef typename match_result<ScannerT, T>::type type;
0320             };
0321
0322             template <typename ScannerT>
0323             typename parser_result<self_t, ScannerT>::type
0324             parse(ScannerT const& scan) const
0325             {
0326                 typedef extract_int<Radix, MinDigits, MaxDigits,
0327                     negative_accumulate<T, Radix> > extract_int_neg_t;
0328                 typedef extract_int<Radix, MinDigits, MaxDigits,
0329                     positive_accumulate<T, Radix> > extract_int_pos_t;
0330
0331                 if (!scan.at_end())
0332                 {
0333                     T n = 0;
0334                     std::size_t count = 0;
0335                     typename ScannerT::iterator_t save = scan.first;
0336
0337                     bool hit = impl::extract_sign(scan, count);
0338
0339                     if (hit)
0340                         hit = extract_int_neg_t::f(scan, n, count);
0341                     else
0342                         hit = extract_int_pos_t::f(scan, n, count);
0343
0344                     if (hit)
0345                         return scan.create_match(count, n, save, scan.first);
0346                     else
0347                         scan.first = save;
0348                     // return no-match if number overflows or underflows
0349                 }
0350                 return scan.no_match();
0351             }
0352         };
0353
0354         ///////////////////////////////////////////////////////////////////////
0355         //
0356         //  real_parser_impl class
0357         //
0358         ///////////////////////////////////////////////////////////////////////
0359         template <typename RT, typename T, typename RealPoliciesT>
0360         struct real_parser_impl
0361         {
0362             typedef real_parser_impl<RT, T, RealPoliciesT> self_t;
0363
0364             template <typename ScannerT>
0365             RT parse_main(ScannerT const& scan) const
0366             {
0367                 if (scan.at_end())
0368                     return scan.no_match();
0369                 typename ScannerT::iterator_t save = scan.first;
0370
0371                 typedef typename parser_result<sign_parser, ScannerT>::type
0372                     sign_match_t;
0373                 typedef typename parser_result<chlit<>, ScannerT>::type
0374                     exp_match_t;
0375
0376                 sign_match_t    sign_match = RealPoliciesT::parse_sign(scan);
0377                 std::size_t     count = sign_match ? sign_match.length() : 0;
0378                 bool            neg = sign_match.has_valid_attribute() ?
0379                                     sign_match.value() : false;
0380
0381                 RT              n_match = RealPoliciesT::parse_n(scan);
0382                 T               n = n_match.has_valid_attribute() ?
0383                                     n_match.value() : T(0);
0384                 bool            got_a_number = n_match;
0385                 exp_match_t     e_hit;
0386
0387                 if (!got_a_number && !RealPoliciesT::allow_leading_dot)
0388                      return scan.no_match();
0389                 else
0390                     count += n_match.length();
0391
0392                 if (neg)
0393                     n = -n;
0394
0395                 if (RealPoliciesT::parse_dot(scan))
0396                 {
0397                     //  We got the decimal point. Now we will try to parse
0398                     //  the fraction if it is there. If not, it defaults
0399                     //  to zero (0) only if we already got a number.
0400
0401                     if (RT hit = RealPoliciesT::parse_frac_n(scan))
0402                     {
0403 #if !defined(BOOST_NO_STDC_NAMESPACE)
0404                         using namespace std;  // allow for ADL to find pow()
0405 #endif
0406                         hit.value(hit.value()
0407                             * pow(T(10), T(-hit.length())));
0408                         if (neg)
0409                             n -= hit.value();
0410                         else
0411                             n += hit.value();
0412                         count += hit.length() + 1;
0413
0414                     }
0415
0416                     else if (!got_a_number ||
0417                         !RealPoliciesT::allow_trailing_dot)
0418                         return scan.no_match();
0419
0420                     e_hit = RealPoliciesT::parse_exp(scan);
0421                 }
0422                 else
0423                 {
0424                     //  We have reached a point where we
0425                     //  still haven't seen a number at all.
0426                     //  We return early with a no-match.
0427                     if (!got_a_number)
0428                         return scan.no_match();
0429
0430                     //  If we must expect a dot and we didn't see
0431                     //  an exponent, return early with a no-match.
0432                     e_hit = RealPoliciesT::parse_exp(scan);
0433                     if (RealPoliciesT::expect_dot && !e_hit)
0434                         return scan.no_match();
0435                 }
0436
0437                 if (e_hit)
0438                 {
0439                     //  We got the exponent prefix. Now we will try to parse the
0440                     //  actual exponent. It is an error if it is not there.
0441                     if (RT e_n_hit = RealPoliciesT::parse_exp_n(scan))
0442                     {
0443 #if !defined(BOOST_NO_STDC_NAMESPACE)
0444                         using namespace std;    // allow for ADL to find pow()
0445 #endif
0446                         n *= pow(T(10), T(e_n_hit.value()));
0447                         count += e_n_hit.length() + e_hit.length();
0448                     }
0449                     else
0450                     {
0451                         //  Oops, no exponent, return a no-match
0452                         return scan.no_match();
0453                     }
0454                 }
0455
0456                 return scan.create_match(count, n, save, scan.first);
0457             }
0458
0459             template <typename ScannerT>
0460             static RT parse(ScannerT const& scan)
0461             {
0462                 static self_t this_;
0463                 return impl::implicit_lexeme_parse<RT>(this_, scan, scan);
0464             }
0465         };
0466
0467 #if defined(BOOST_MSVC)
0468 #pragma warning(pop)
0469 #endif
0470
0471     }   //  namespace impl
0472
0473 ///////////////////////////////////////////////////////////////////////////////
0474 BOOST_SPIRIT_CLASSIC_NAMESPACE_END
0475
0476 }} // namespace boost::spirit
0477
0478 #endif