1/*=============================================================================
2    Copyright (c) 1998-2003 Joel de Guzman
3    Copyright (c) 2001-2003 Hartmut Kaiser
4    http://spirit.sourceforge.net/
5
6    Use, modification and distribution is subject to the Boost Software
7    License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
8    http://www.boost.org/LICENSE_1_0.txt)
9=============================================================================*/
10#ifndef BOOST_SPIRIT_NUMERICS_IPP
11#define BOOST_SPIRIT_NUMERICS_IPP
12
13#include <boost/config/no_tr1/cmath.hpp>
14#include <limits>
15
16namespace boost { namespace spirit {
17
18BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
19
20    struct sign_parser; // forward declaration only
21
22    namespace impl
23    {
24        ///////////////////////////////////////////////////////////////////////
25        //
26        //  Extract the prefix sign (- or +)
27        //
28        ///////////////////////////////////////////////////////////////////////
29        template <typename ScannerT>
30        bool
31        extract_sign(ScannerT const& scan, std::size_t& count)
32        {
33            //  Extract the sign
34            count = 0;
35            bool neg = *scan == '-';
36            if (neg || (*scan == '+'))
37            {
38                ++scan;
39                ++count;
40                return neg;
41            }
42
43            return false;
44        }
45
46        ///////////////////////////////////////////////////////////////////////
47        //
48        //  Traits class for radix specific number conversion
49        //
50        //      Convert a digit from character representation, ch, to binary
51        //      representation, returned in val.
52        //      Returns whether the conversion was successful.
53        //
54        //        template<typename CharT> static bool digit(CharT ch, T& val);
55        //
56        ///////////////////////////////////////////////////////////////////////
57        template<const int Radix>
58        struct radix_traits;
59
60        ////////////////////////////////// Binary
61        template<>
62        struct radix_traits<2>
63        {
64            template<typename CharT, typename T>
65            static bool digit(CharT ch, T& val)
66            {
67                val = ch - '0';
68                return ('0' == ch || '1' == ch);
69            }
70        };
71
72        ////////////////////////////////// Octal
73        template<>
74        struct radix_traits<8>
75        {
76            template<typename CharT, typename T>
77            static bool digit(CharT ch, T& val)
78            {
79                val = ch - '0';
80                return ('0' <= ch && ch <= '7');
81            }
82        };
83
84        ////////////////////////////////// Decimal
85        template<>
86        struct radix_traits<10>
87        {
88            template<typename CharT, typename T>
89            static bool digit(CharT ch, T& val)
90            {
91                val = ch - '0';
92                return impl::isdigit_(ch);
93            }
94        };
95
96        ////////////////////////////////// Hexadecimal
97        template<>
98        struct radix_traits<16>
99        {
100            template<typename CharT, typename T>
101            static bool digit(CharT ch, T& val)
102            {
103                if (radix_traits<10>::digit(ch, val))
104                    return true;
105
106                CharT lc = impl::tolower_(ch);
107                if ('a' <= lc && lc <= 'f')
108                {
109                    val = lc - 'a' + 10;
110                    return true;
111                }
112                return false;
113            }
114        };
115
116        ///////////////////////////////////////////////////////////////////////
117        //
118        //      Helper templates for encapsulation of radix specific
119        //      conversion of an input string to an integral value.
120        //
121        //      main entry point:
122        //
123        //          extract_int<Radix, MinDigits, MaxDigits, Accumulate>
124        //              ::f(first, last, n, count);
125        //
126        //          The template parameter Radix represents the radix of the
127        //          number contained in the parsed string. The template
128        //          parameter MinDigits specifies the minimum digits to
129        //          accept. The template parameter MaxDigits specifies the
130        //          maximum digits to parse. A -1 value for MaxDigits will
131        //          make it parse an arbitrarilly large number as long as the
132        //          numeric type can hold it. Accumulate is either
133        //          positive_accumulate<Radix> (default) for parsing positive
134        //          numbers or negative_accumulate<Radix> otherwise.
135        //          Checking is only performed when std::numeric_limits<T>::
136        //          is_specialized is true. Otherwise, there's no way to
137        //          do the check.
138        //
139        //          scan.first and scan.last are iterators as usual (i.e.
140        //          first is mutable and is moved forward when a match is
141        //          found), n is a variable that holds the number (passed by
142        //          reference). The number of parsed characters is added to
143        //          count (also passed by reference)
144        //
145        //      NOTE:
146        //              Returns a non-match, if the number to parse
147        //              overflows (or underflows) the used type.
148        //
149        //      BEWARE:
150        //              the parameters 'n' and 'count' should be properly
151        //              initialized before calling this function.
152        //
153        ///////////////////////////////////////////////////////////////////////
154#if defined(BOOST_MSVC)
155#pragma warning(push)
156#pragma warning(disable:4127) //conditional expression is constant
157#endif
158
159        template <typename T, int Radix>
160        struct positive_accumulate
161        {
162            //  Use this accumulator if number is positive
163            static bool add(T& n, T digit)
164            {
165                if (std::numeric_limits<T>::is_specialized)
166                {
167                    static T const max = (std::numeric_limits<T>::max)();
168                    static T const max_div_radix = max/Radix;
169
170                    if (n > max_div_radix)
171                        return false;
172                    n *= Radix;
173
174                    if (n > max - digit)
175                        return false;
176                    n += digit;
177
178                    return true;
179                }
180                else
181                {
182                    n *= Radix;
183                    n += digit;
184                    return true;
185                }
186            }
187        };
188
189        template <typename T, int Radix>
190        struct negative_accumulate
191        {
192            //  Use this accumulator if number is negative
193            static bool add(T& n, T digit)
194            {
195                if (std::numeric_limits<T>::is_specialized)
196                {
197                    typedef std::numeric_limits<T> num_limits;
198                    static T const min =
199                        (!num_limits::is_integer && num_limits::is_signed && num_limits::has_denorm) ?
200                        -(num_limits::max)() : (num_limits::min)();
201                    static T const min_div_radix = min/Radix;
202
203                    if (n < min_div_radix)
204                        return false;
205                    n *= Radix;
206
207                    if (n < min + digit)
208                        return false;
209                    n -= digit;
210
211                    return true;
212                }
213                else
214                {
215                    n *= Radix;
216                    n -= digit;
217                    return true;
218                }
219            }
220        };
221
222        template <int MaxDigits>
223        inline bool allow_more_digits(std::size_t i)
224        {
225            return i < MaxDigits;
226        }
227
228        template <>
229        inline bool allow_more_digits<-1>(std::size_t)
230        {
231            return true;
232        }
233
234        //////////////////////////////////
235        template <
236            int Radix, unsigned MinDigits, int MaxDigits,
237            typename Accumulate
238        >
239        struct extract_int
240        {
241            template <typename ScannerT, typename T>
242            static bool
243            f(ScannerT& scan, T& n, std::size_t& count)
244            {
245                std::size_t i = 0;
246                T digit;
247                while( allow_more_digits<MaxDigits>(i) && !scan.at_end() &&
248                    radix_traits<Radix>::digit(*scan, digit) )
249                {
250                    if (!Accumulate::add(n, digit))
251                        return false; // Overflow
252                    ++i, ++scan, ++count;
253                }
254                return i >= MinDigits;
255            }
256        };
257
258        ///////////////////////////////////////////////////////////////////////
259        //
260        //  uint_parser_impl class
261        //
262        ///////////////////////////////////////////////////////////////////////
263        template <
264            typename T = unsigned,
265            int Radix = 10,
266            unsigned MinDigits = 1,
267            int MaxDigits = -1
268        >
269        struct uint_parser_impl
270            : parser<uint_parser_impl<T, Radix, MinDigits, MaxDigits> >
271        {
272            typedef uint_parser_impl<T, Radix, MinDigits, MaxDigits> self_t;
273
274            template <typename ScannerT>
275            struct result
276            {
277                typedef typename match_result<ScannerT, T>::type type;
278            };
279
280            template <typename ScannerT>
281            typename parser_result<self_t, ScannerT>::type
282            parse(ScannerT const& scan) const
283            {
284                if (!scan.at_end())
285                {
286                    T n = 0;
287                    std::size_t count = 0;
288                    typename ScannerT::iterator_t save = scan.first;
289                    if (extract_int<Radix, MinDigits, MaxDigits,
290                        positive_accumulate<T, Radix> >::f(scan, n, count))
291                    {
292                        return scan.create_match(count, n, save, scan.first);
293                    }
294                    // return no-match if number overflows
295                }
296                return scan.no_match();
297            }
298        };
299
300        ///////////////////////////////////////////////////////////////////////
301        //
302        //  int_parser_impl class
303        //
304        ///////////////////////////////////////////////////////////////////////
305        template <
306            typename T = unsigned,
307            int Radix = 10,
308            unsigned MinDigits = 1,
309            int MaxDigits = -1
310        >
311        struct int_parser_impl
312            : parser<int_parser_impl<T, Radix, MinDigits, MaxDigits> >
313        {
314            typedef int_parser_impl<T, Radix, MinDigits, MaxDigits> self_t;
315
316            template <typename ScannerT>
317            struct result
318            {
319                typedef typename match_result<ScannerT, T>::type type;
320            };
321
322            template <typename ScannerT>
323            typename parser_result<self_t, ScannerT>::type
324            parse(ScannerT const& scan) const
325            {
326                typedef extract_int<Radix, MinDigits, MaxDigits,
327                    negative_accumulate<T, Radix> > extract_int_neg_t;
328                typedef extract_int<Radix, MinDigits, MaxDigits,
329                    positive_accumulate<T, Radix> > extract_int_pos_t;
330
331                if (!scan.at_end())
332                {
333                    T n = 0;
334                    std::size_t count = 0;
335                    typename ScannerT::iterator_t save = scan.first;
336
337                    bool hit = impl::extract_sign(scan, count);
338
339                    if (hit)
340                        hit = extract_int_neg_t::f(scan, n, count);
341                    else
342                        hit = extract_int_pos_t::f(scan, n, count);
343
344                    if (hit)
345                        return scan.create_match(count, n, save, scan.first);
346                    else
347                        scan.first = save;
348                    // return no-match if number overflows or underflows
349                }
350                return scan.no_match();
351            }
352        };
353
354        ///////////////////////////////////////////////////////////////////////
355        //
356        //  real_parser_impl class
357        //
358        ///////////////////////////////////////////////////////////////////////
359        template <typename RT, typename T, typename RealPoliciesT>
360        struct real_parser_impl
361        {
362            typedef real_parser_impl<RT, T, RealPoliciesT> self_t;
363
364            template <typename ScannerT>
365            RT parse_main(ScannerT const& scan) const
366            {
367                if (scan.at_end())
368                    return scan.no_match();
369                typename ScannerT::iterator_t save = scan.first;
370
371                typedef typename parser_result<sign_parser, ScannerT>::type
372                    sign_match_t;
373                typedef typename parser_result<chlit<>, ScannerT>::type
374                    exp_match_t;
375
376                sign_match_t    sign_match = RealPoliciesT::parse_sign(scan);
377                std::size_t     count = sign_match ? sign_match.length() : 0;
378                bool            neg = sign_match.has_valid_attribute() ?
379                                    sign_match.value() : false;
380
381                RT              n_match = RealPoliciesT::parse_n(scan);
382                T               n = n_match.has_valid_attribute() ?
383                                    n_match.value() : T(0);
384                bool            got_a_number = n_match;
385                exp_match_t     e_hit;
386
387                if (!got_a_number && !RealPoliciesT::allow_leading_dot)
388                     return scan.no_match();
389                else
390                    count += n_match.length();
391
392                if (neg)
393                    n = -n;
394
395                if (RealPoliciesT::parse_dot(scan))
396                {
397                    //  We got the decimal point. Now we will try to parse
398                    //  the fraction if it is there. If not, it defaults
399                    //  to zero (0) only if we already got a number.
400
401                    if (RT hit = RealPoliciesT::parse_frac_n(scan))
402                    {
403#if !defined(BOOST_NO_STDC_NAMESPACE)
404                        using namespace std;  // allow for ADL to find pow()
405#endif
406                        hit.value(hit.value()
407                            * pow(T(10), T(-hit.length())));
408                        if (neg)
409                            n -= hit.value();
410                        else
411                            n += hit.value();
412                        count += hit.length() + 1;
413
414                    }
415
416                    else if (!got_a_number ||
417                        !RealPoliciesT::allow_trailing_dot)
418                        return scan.no_match();
419
420                    e_hit = RealPoliciesT::parse_exp(scan);
421                }
422                else
423                {
424                    //  We have reached a point where we
425                    //  still haven't seen a number at all.
426                    //  We return early with a no-match.
427                    if (!got_a_number)
428                        return scan.no_match();
429
430                    //  If we must expect a dot and we didn't see
431                    //  an exponent, return early with a no-match.
432                    e_hit = RealPoliciesT::parse_exp(scan);
433                    if (RealPoliciesT::expect_dot && !e_hit)
434                        return scan.no_match();
435                }
436
437                if (e_hit)
438                {
439                    //  We got the exponent prefix. Now we will try to parse the
440                    //  actual exponent. It is an error if it is not there.
441                    if (RT e_n_hit = RealPoliciesT::parse_exp_n(scan))
442                    {
443#if !defined(BOOST_NO_STDC_NAMESPACE)
444                        using namespace std;    // allow for ADL to find pow()
445#endif
446                        n *= pow(T(10), T(e_n_hit.value()));
447                        count += e_n_hit.length() + e_hit.length();
448                    }
449                    else
450                    {
451                        //  Oops, no exponent, return a no-match
452                        return scan.no_match();
453                    }
454                }
455
456                return scan.create_match(count, n, save, scan.first);
457            }
458
459            template <typename ScannerT>
460            static RT parse(ScannerT const& scan)
461            {
462                static self_t this_;
463                return impl::implicit_lexeme_parse<RT>(this_, scan, scan);
464            }
465        };
466
467#if defined(BOOST_MSVC)
468#pragma warning(pop)
469#endif
470
471    }   //  namespace impl
472
473///////////////////////////////////////////////////////////////////////////////
474BOOST_SPIRIT_CLASSIC_NAMESPACE_END
475
476}} // namespace boost::spirit
477
478#endif
479