src/libstd/num/strconv.rs

   1 // Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 #![allow(missing_doc)]
  12
  13 use char;
  14 use clone::Clone;
  15 use container::Container;
  16 use iter::Iterator;
  17 use num::{NumCast, Zero, One, cast, Int};
  18 use num::{Float, FPNaN, FPInfinite, ToPrimitive};
  19 use num;
  20 use ops::{Add, Sub, Mul, Div, Rem, Neg};
  21 use option::{None, Option, Some};
  22 use slice::OwnedVector;
  23 use slice::{CloneableVector, ImmutableVector, MutableVector};
  24 use std::cmp::{Ord, Eq};
  25 use str::{StrSlice};
  26 use str;
  27 use vec::Vec;
  28
  29 /// A flag that specifies whether to use exponential (scientific) notation.
  30 pub enum ExponentFormat {
  31     /// Do not use exponential notation.
  32     ExpNone,
  33     /// Use exponential notation with the exponent having a base of 10 and the
  34     /// exponent sign being `e` or `E`. For example, 1000 would be printed
  35     /// 1e3.
  36     ExpDec,
  37     /// Use exponential notation with the exponent having a base of 2 and the
  38     /// exponent sign being `p` or `P`. For example, 8 would be printed 1p3.
  39     ExpBin,
  40 }
  41
  42 /// The number of digits used for emitting the fractional part of a number, if
  43 /// any.
  44 pub enum SignificantDigits {
  45     /// All calculable digits will be printed.
  46     ///
  47     /// Note that bignums or fractions may cause a surprisingly large number
  48     /// of digits to be printed.
  49     DigAll,
  50
  51     /// At most the given number of digits will be printed, truncating any
  52     /// trailing zeroes.
  53     DigMax(uint),
  54
  55     /// Precisely the given number of digits will be printed.
  56     DigExact(uint)
  57 }
  58
  59 /// How to emit the sign of a number.
  60 pub enum SignFormat {
  61     /// No sign will be printed. The exponent sign will also be emitted.
  62     SignNone,
  63     /// `-` will be printed for negative values, but no sign will be emitted
  64     /// for positive numbers.
  65     SignNeg,
  66     /// `+` will be printed for positive values, and `-` will be printed for
  67     /// negative values.
  68     SignAll,
  69 }
  70
  71 /// Encompasses functions used by the string converter.
  72 pub trait NumStrConv {
  73     /// Returns the NaN value.
  74     fn nan()      -> Option<Self>;
  75
  76     /// Returns the infinite value.
  77     fn inf()      -> Option<Self>;
  78
  79     /// Returns the negative infinite value.
  80     fn neg_inf()  -> Option<Self>;
  81
  82     /// Returns -0.0.
  83     fn neg_zero() -> Option<Self>;
  84
  85     /// Rounds the number toward zero.
  86     fn round_to_zero(&self)   -> Self;
  87
  88     /// Returns the fractional part of the number.
  89     fn fractional_part(&self) -> Self;
  90 }
  91
  92 macro_rules! impl_NumStrConv_Floating (($t:ty) => (
  93     impl NumStrConv for $t {
  94         #[inline]
  95         fn nan()      -> Option<$t> { Some( 0.0 / 0.0) }
  96         #[inline]
  97         fn inf()      -> Option<$t> { Some( 1.0 / 0.0) }
  98         #[inline]
  99         fn neg_inf()  -> Option<$t> { Some(-1.0 / 0.0) }
 100         #[inline]
 101         fn neg_zero() -> Option<$t> { Some(-0.0      ) }
 102
 103         #[inline]
 104         fn round_to_zero(&self) -> $t { self.trunc() }
 105         #[inline]
 106         fn fractional_part(&self) -> $t { self.fract() }
 107     }
 108 ))
 109
 110 macro_rules! impl_NumStrConv_Integer (($t:ty) => (
 111     impl NumStrConv for $t {
 112         #[inline] fn nan()      -> Option<$t> { None }
 113         #[inline] fn inf()      -> Option<$t> { None }
 114         #[inline] fn neg_inf()  -> Option<$t> { None }
 115         #[inline] fn neg_zero() -> Option<$t> { None }
 116
 117         #[inline] fn round_to_zero(&self)   -> $t { *self }
 118         #[inline] fn fractional_part(&self) -> $t {     0 }
 119     }
 120 ))
 121
 122 // FIXME: #4955
 123 // Replace by two generic impls for traits 'Integral' and 'Floating'
 124 impl_NumStrConv_Floating!(f32)
 125 impl_NumStrConv_Floating!(f64)
 126
 127 impl_NumStrConv_Integer!(int)
 128 impl_NumStrConv_Integer!(i8)
 129 impl_NumStrConv_Integer!(i16)
 130 impl_NumStrConv_Integer!(i32)
 131 impl_NumStrConv_Integer!(i64)
 132
 133 impl_NumStrConv_Integer!(uint)
 134 impl_NumStrConv_Integer!(u8)
 135 impl_NumStrConv_Integer!(u16)
 136 impl_NumStrConv_Integer!(u32)
 137 impl_NumStrConv_Integer!(u64)
 138
 139
 140 // Special value strings as [u8] consts.
 141 static INF_BUF:          [u8, ..3] = ['i' as u8, 'n' as u8, 'f' as u8];
 142 static POS_INF_BUF: [u8, ..4] = ['+' as u8, 'i' as u8, 'n' as u8,
 143                                       'f' as u8];
 144 static NEG_INF_BUF: [u8, ..4] = ['-' as u8, 'i' as u8, 'n' as u8,
 145                                       'f' as u8];
 146 static NAN_BUF:          [u8, ..3] = ['N' as u8, 'a' as u8, 'N' as u8];
 147
 148 /**
 149  * Converts an integral number to its string representation as a byte vector.
 150  * This is meant to be a common base implementation for all integral string
 151  * conversion functions like `to_str()` or `to_str_radix()`.
 152  *
 153  * # Arguments
 154  * - `num`           - The number to convert. Accepts any number that
 155  *                     implements the numeric traits.
 156  * - `radix`         - Base to use. Accepts only the values 2-36.
 157  * - `sign`          - How to emit the sign. Options are:
 158  *     - `SignNone`: No sign at all. Basically emits `abs(num)`.
 159  *     - `SignNeg`:  Only `-` on negative values.
 160  *     - `SignAll`:  Both `+` on positive, and `-` on negative numbers.
 161  * - `f`             - a callback which will be invoked for each ascii character
 162  *                     which composes the string representation of this integer
 163  *
 164  * # Return value
 165  * A tuple containing the byte vector, and a boolean flag indicating
 166  * whether it represents a special value like `inf`, `-inf`, `NaN` or not.
 167  * It returns a tuple because there can be ambiguity between a special value
 168  * and a number representation at higher bases.
 169  *
 170  * # Failure
 171  * - Fails if `radix` < 2 or `radix` > 36.
 172  */
 173 pub fn int_to_str_bytes_common<T: Int>(num: T, radix: uint, sign: SignFormat, f: |u8|) {
 174     assert!(2 <= radix && radix <= 36);
 175
 176     let _0: T = Zero::zero();
 177
 178     let neg = num < _0;
 179     let radix_gen: T = cast(radix).unwrap();
 180
 181     let mut deccum = num;
 182     // This is just for integral types, the largest of which is a u64. The
 183     // smallest base that we can have is 2, so the most number of digits we're
 184     // ever going to have is 64
 185     let mut buf = [0u8, ..64];
 186     let mut cur = 0;
 187
 188     // Loop at least once to make sure at least a `0` gets emitted.
 189     loop {
 190         // Calculate the absolute value of each digit instead of only
 191         // doing it once for the whole number because a
 192         // representable negative number doesn't necessary have an
 193         // representable additive inverse of the same type
 194         // (See twos complement). But we assume that for the
 195         // numbers [-35 .. 0] we always have [0 .. 35].
 196         let current_digit_signed = deccum % radix_gen;
 197         let current_digit = if current_digit_signed < _0 {
 198             -current_digit_signed
 199         } else {
 200             current_digit_signed
 201         };
 202         buf[cur] = match current_digit.to_u8().unwrap() {
 203             i @ 0..9 => '0' as u8 + i,
 204             i        => 'a' as u8 + (i - 10),
 205         };
 206         cur += 1;
 207
 208         deccum = deccum / radix_gen;
 209         // No more digits to calculate for the non-fractional part -> break
 210         if deccum == _0 { break; }
 211     }
 212
 213     // Decide what sign to put in front
 214     match sign {
 215         SignNeg | SignAll if neg => { f('-' as u8); }
 216         SignAll => { f('+' as u8); }
 217         _ => ()
 218     }
 219
 220     // We built the number in reverse order, so un-reverse it here
 221     while cur > 0 {
 222         cur -= 1;
 223         f(buf[cur]);
 224     }
 225 }
 226
 227 /**
 228  * Converts a number to its string representation as a byte vector.
 229  * This is meant to be a common base implementation for all numeric string
 230  * conversion functions like `to_str()` or `to_str_radix()`.
 231  *
 232  * # Arguments
 233  * - `num`           - The number to convert. Accepts any number that
 234  *                     implements the numeric traits.
 235  * - `radix`         - Base to use. Accepts only the values 2-36. If the exponential notation
 236  *                     is used, then this base is only used for the significand. The exponent
 237  *                     itself always printed using a base of 10.
 238  * - `negative_zero` - Whether to treat the special value `-0` as
 239  *                     `-0` or as `+0`.
 240  * - `sign`          - How to emit the sign. See `SignFormat`.
 241  * - `digits`        - The amount of digits to use for emitting the fractional
 242  *                     part, if any. See `SignificantDigits`.
 243  * - `exp_format`   - Whether or not to use the exponential (scientific) notation.
 244  *                    See `ExponentFormat`.
 245  * - `exp_capital`   - Whether or not to use a capital letter for the exponent sign, if
 246  *                     exponential notation is desired.
 247  *
 248  * # Return value
 249  * A tuple containing the byte vector, and a boolean flag indicating
 250  * whether it represents a special value like `inf`, `-inf`, `NaN` or not.
 251  * It returns a tuple because there can be ambiguity between a special value
 252  * and a number representation at higher bases.
 253  *
 254  * # Failure
 255  * - Fails if `radix` < 2 or `radix` > 36.
 256  * - Fails if `radix` > 14 and `exp_format` is `ExpDec` due to conflict
 257  *   between digit and exponent sign `'e'`.
 258  * - Fails if `radix` > 25 and `exp_format` is `ExpBin` due to conflict
 259  *   between digit and exponent sign `'p'`.
 260  */
 261 pub fn float_to_str_bytes_common<T:NumCast+Zero+One+Eq+Ord+Float+
 262                                   Div<T,T>+Neg<T>+Rem<T,T>+Mul<T,T>>(
 263         num: T, radix: uint, negative_zero: bool,
 264         sign: SignFormat, digits: SignificantDigits, exp_format: ExponentFormat, exp_upper: bool
 265         ) -> (~[u8], bool) {
 266     assert!(2 <= radix && radix <= 36);
 267     match exp_format {
 268         ExpDec if radix >= DIGIT_E_RADIX       // decimal exponent 'e'
 269           => fail!("float_to_str_bytes_common: radix {} incompatible with \
 270                     use of 'e' as decimal exponent", radix),
 271         ExpBin if radix >= DIGIT_P_RADIX       // binary exponent 'p'
 272           => fail!("float_to_str_bytes_common: radix {} incompatible with \
 273                     use of 'p' as binary exponent", radix),
 274         _ => ()
 275     }
 276
 277     let _0: T = Zero::zero();
 278     let _1: T = One::one();
 279
 280     match num.classify() {
 281         FPNaN => { return ("NaN".as_bytes().to_owned(), true); }
 282         FPInfinite if num > _0 => {
 283             return match sign {
 284                 SignAll => ("+inf".as_bytes().to_owned(), true),
 285                 _       => ("inf".as_bytes().to_owned(), true)
 286             };
 287         }
 288         FPInfinite if num < _0 => {
 289             return match sign {
 290                 SignNone => ("inf".as_bytes().to_owned(), true),
 291                 _        => ("-inf".as_bytes().to_owned(), true),
 292             };
 293         }
 294         _ => {}
 295     }
 296
 297     let neg = num < _0 || (negative_zero && _1 / num == Float::neg_infinity());
 298     let mut buf = Vec::new();
 299     let radix_gen: T   = cast(radix as int).unwrap();
 300
 301     let (num, exp) = match exp_format {
 302         ExpNone => (num, 0i32),
 303         ExpDec | ExpBin => {
 304             if num == _0 {
 305                 (num, 0i32)
 306             } else {
 307                 let (exp, exp_base) = match exp_format {
 308                     ExpDec => (num.abs().log10().floor(), cast::<f64, T>(10.0f64).unwrap()),
 309                     ExpBin => (num.abs().log2().floor(), cast::<f64, T>(2.0f64).unwrap()),
 310                     ExpNone => unreachable!()
 311                 };
 312
 313                 (num / exp_base.powf(&exp), cast::<T, i32>(exp).unwrap())
 314             }
 315         }
 316     };
 317
 318     // First emit the non-fractional part, looping at least once to make
 319     // sure at least a `0` gets emitted.
 320     let mut deccum = num.trunc();
 321     loop {
 322         // Calculate the absolute value of each digit instead of only
 323         // doing it once for the whole number because a
 324         // representable negative number doesn't necessary have an
 325         // representable additive inverse of the same type
 326         // (See twos complement). But we assume that for the
 327         // numbers [-35 .. 0] we always have [0 .. 35].
 328         let current_digit = (deccum % radix_gen).abs();
 329
 330         // Decrease the deccumulator one digit at a time
 331         deccum = deccum / radix_gen;
 332         deccum = deccum.trunc();
 333
 334         buf.push(char::from_digit(current_digit.to_int().unwrap() as uint, radix)
 335              .unwrap() as u8);
 336
 337         // No more digits to calculate for the non-fractional part -> break
 338         if deccum == _0 { break; }
 339     }
 340
 341     // If limited digits, calculate one digit more for rounding.
 342     let (limit_digits, digit_count, exact) = match digits {
 343         DigAll          => (false, 0u,      false),
 344         DigMax(count)   => (true,  count+1, false),
 345         DigExact(count) => (true,  count+1, true)
 346     };
 347
 348     // Decide what sign to put in front
 349     match sign {
 350         SignNeg | SignAll if neg => {
 351             buf.push('-' as u8);
 352         }
 353         SignAll => {
 354             buf.push('+' as u8);
 355         }
 356         _ => ()
 357     }
 358
 359     buf.reverse();
 360
 361     // Remember start of the fractional digits.
 362     // Points one beyond end of buf if none get generated,
 363     // or at the '.' otherwise.
 364     let start_fractional_digits = buf.len();
 365
 366     // Now emit the fractional part, if any
 367     deccum = num.fract();
 368     if deccum != _0 || (limit_digits && exact && digit_count > 0) {
 369         buf.push('.' as u8);
 370         let mut dig = 0u;
 371
 372         // calculate new digits while
 373         // - there is no limit and there are digits left
 374         // - or there is a limit, it's not reached yet and
 375         //   - it's exact
 376         //   - or it's a maximum, and there are still digits left
 377         while (!limit_digits && deccum != _0)
 378            || (limit_digits && dig < digit_count && (
 379                    exact
 380                 || (!exact && deccum != _0)
 381               )
 382         ) {
 383             // Shift first fractional digit into the integer part
 384             deccum = deccum * radix_gen;
 385
 386             // Calculate the absolute value of each digit.
 387             // See note in first loop.
 388             let current_digit = deccum.trunc().abs();
 389
 390             buf.push(char::from_digit(
 391                 current_digit.to_int().unwrap() as uint, radix).unwrap() as u8);
 392
 393             // Decrease the deccumulator one fractional digit at a time
 394             deccum = deccum.fract();
 395             dig += 1u;
 396         }
 397
 398         // If digits are limited, and that limit has been reached,
 399         // cut off the one extra digit, and depending on its value
 400         // round the remaining ones.
 401         if limit_digits && dig == digit_count {
 402             let ascii2value = |chr: u8| {
 403                 char::to_digit(chr as char, radix).unwrap()
 404             };
 405             let value2ascii = |val: uint| {
 406                 char::from_digit(val, radix).unwrap() as u8
 407             };
 408
 409             let extra_digit = ascii2value(buf.pop().unwrap());
 410             if extra_digit >= radix / 2 { // -> need to round
 411                 let mut i: int = buf.len() as int - 1;
 412                 loop {
 413                     // If reached left end of number, have to
 414                     // insert additional digit:
 415                     if i < 0
 416                     || *buf.get(i as uint) == '-' as u8
 417                     || *buf.get(i as uint) == '+' as u8 {
 418                         buf.insert((i + 1) as uint, value2ascii(1));
 419                         break;
 420                     }
 421
 422                     // Skip the '.'
 423                     if *buf.get(i as uint) == '.' as u8 { i -= 1; continue; }
 424
 425                     // Either increment the digit,
 426                     // or set to 0 if max and carry the 1.
 427                     let current_digit = ascii2value(*buf.get(i as uint));
 428                     if current_digit < (radix - 1) {
 429                         *buf.get_mut(i as uint) = value2ascii(current_digit+1);
 430                         break;
 431                     } else {
 432                         *buf.get_mut(i as uint) = value2ascii(0);
 433                         i -= 1;
 434                     }
 435                 }
 436             }
 437         }
 438     }
 439
 440     // if number of digits is not exact, remove all trailing '0's up to
 441     // and including the '.'
 442     if !exact {
 443         let buf_max_i = buf.len() - 1;
 444
 445         // index to truncate from
 446         let mut i = buf_max_i;
 447
 448         // discover trailing zeros of fractional part
 449         while i > start_fractional_digits && *buf.get(i) == '0' as u8 {
 450             i -= 1;
 451         }
 452
 453         // Only attempt to truncate digits if buf has fractional digits
 454         if i >= start_fractional_digits {
 455             // If buf ends with '.', cut that too.
 456             if *buf.get(i) == '.' as u8 { i -= 1 }
 457
 458             // only resize buf if we actually remove digits
 459             if i < buf_max_i {
 460                 buf = Vec::from_slice(buf.slice(0, i + 1));
 461             }
 462         }
 463     } // If exact and trailing '.', just cut that
 464     else {
 465         let max_i = buf.len() - 1;
 466         if *buf.get(max_i) == '.' as u8 {
 467             buf = Vec::from_slice(buf.slice(0, max_i));
 468         }
 469     }
 470
 471     match exp_format {
 472         ExpNone => (),
 473         _ => {
 474             buf.push(match exp_format {
 475                 ExpDec if exp_upper => 'E',
 476                 ExpDec if !exp_upper => 'e',
 477                 ExpBin if exp_upper => 'P',
 478                 ExpBin if !exp_upper => 'p',
 479                 _ => unreachable!()
 480             } as u8);
 481
 482             int_to_str_bytes_common(exp, 10, sign, |c| buf.push(c));
 483         }
 484     }
 485
 486     (buf.move_iter().collect(), false)
 487 }
 488
 489 /**
 490  * Converts a number to its string representation. This is a wrapper for
 491  * `to_str_bytes_common()`, for details see there.
 492  */
 493 #[inline]
 494 pub fn float_to_str_common<T:NumCast+Zero+One+Eq+Ord+NumStrConv+Float+
 495                              Div<T,T>+Neg<T>+Rem<T,T>+Mul<T,T>>(
 496         num: T, radix: uint, negative_zero: bool,
 497         sign: SignFormat, digits: SignificantDigits, exp_format: ExponentFormat, exp_capital: bool
 498         ) -> (~str, bool) {
 499     let (bytes, special) = float_to_str_bytes_common(num, radix,
 500                                negative_zero, sign, digits, exp_format, exp_capital);
 501     (str::from_utf8_owned(bytes).unwrap(), special)
 502 }
 503
 504 // Some constants for from_str_bytes_common's input validation,
 505 // they define minimum radix values for which the character is a valid digit.
 506 static DIGIT_P_RADIX: uint = ('p' as uint) - ('a' as uint) + 11u;
 507 static DIGIT_I_RADIX: uint = ('i' as uint) - ('a' as uint) + 11u;
 508 static DIGIT_E_RADIX: uint = ('e' as uint) - ('a' as uint) + 11u;
 509
 510 /**
 511  * Parses a byte slice as a number. This is meant to
 512  * be a common base implementation for all numeric string conversion
 513  * functions like `from_str()` or `from_str_radix()`.
 514  *
 515  * # Arguments
 516  * - `buf`        - The byte slice to parse.
 517  * - `radix`      - Which base to parse the number as. Accepts 2-36.
 518  * - `negative`   - Whether to accept negative numbers.
 519  * - `fractional` - Whether to accept numbers with fractional parts.
 520  * - `special`    - Whether to accept special values like `inf`
 521  *                  and `NaN`. Can conflict with `radix`, see Failure.
 522  * - `exponent`   - Which exponent format to accept. Options are:
 523  *     - `ExpNone`: No Exponent, accepts just plain numbers like `42` or
 524  *                  `-8.2`.
 525  *     - `ExpDec`:  Accepts numbers with a decimal exponent like `42e5` or
 526  *                  `8.2E-2`. The exponent string itself is always base 10.
 527  *                  Can conflict with `radix`, see Failure.
 528  *     - `ExpBin`:  Accepts numbers with a binary exponent like `42P-8` or
 529  *                  `FFp128`. The exponent string itself is always base 10.
 530  *                  Can conflict with `radix`, see Failure.
 531  * - `empty_zero` - Whether to accept an empty `buf` as a 0 or not.
 532  * - `ignore_underscores` - Whether all underscores within the string should
 533  *                          be ignored.
 534  *
 535  * # Return value
 536  * Returns `Some(n)` if `buf` parses to a number n without overflowing, and
 537  * `None` otherwise, depending on the constraints set by the remaining
 538  * arguments.
 539  *
 540  * # Failure
 541  * - Fails if `radix` < 2 or `radix` > 36.
 542  * - Fails if `radix` > 14 and `exponent` is `ExpDec` due to conflict
 543  *   between digit and exponent sign `'e'`.
 544  * - Fails if `radix` > 25 and `exponent` is `ExpBin` due to conflict
 545  *   between digit and exponent sign `'p'`.
 546  * - Fails if `radix` > 18 and `special == true` due to conflict
 547  *   between digit and lowest first character in `inf` and `NaN`, the `'i'`.
 548  */
 549 pub fn from_str_bytes_common<T:NumCast+Zero+One+Eq+Ord+Div<T,T>+
 550                                     Mul<T,T>+Sub<T,T>+Neg<T>+Add<T,T>+
 551                                     NumStrConv+Clone>(
 552         buf: &[u8], radix: uint, negative: bool, fractional: bool,
 553         special: bool, exponent: ExponentFormat, empty_zero: bool,
 554         ignore_underscores: bool
 555         ) -> Option<T> {
 556     match exponent {
 557         ExpDec if radix >= DIGIT_E_RADIX       // decimal exponent 'e'
 558           => fail!("from_str_bytes_common: radix {} incompatible with \
 559                     use of 'e' as decimal exponent", radix),
 560         ExpBin if radix >= DIGIT_P_RADIX       // binary exponent 'p'
 561           => fail!("from_str_bytes_common: radix {} incompatible with \
 562                     use of 'p' as binary exponent", radix),
 563         _ if special && radix >= DIGIT_I_RADIX // first digit of 'inf'
 564           => fail!("from_str_bytes_common: radix {} incompatible with \
 565                     special values 'inf' and 'NaN'", radix),
 566         _ if (radix as int) < 2
 567           => fail!("from_str_bytes_common: radix {} to low, \
 568                     must lie in the range [2, 36]", radix),
 569         _ if (radix as int) > 36
 570           => fail!("from_str_bytes_common: radix {} to high, \
 571                     must lie in the range [2, 36]", radix),
 572         _ => ()
 573     }
 574
 575     let _0: T = Zero::zero();
 576     let _1: T = One::one();
 577     let radix_gen: T = cast(radix as int).unwrap();
 578
 579     let len = buf.len();
 580
 581     if len == 0 {
 582         if empty_zero {
 583             return Some(_0);
 584         } else {
 585             return None;
 586         }
 587     }
 588
 589     if special {
 590         if buf == INF_BUF || buf == POS_INF_BUF {
 591             return NumStrConv::inf();
 592         } else if buf == NEG_INF_BUF {
 593             if negative {
 594                 return NumStrConv::neg_inf();
 595             } else {
 596                 return None;
 597             }
 598         } else if buf == NAN_BUF {
 599             return NumStrConv::nan();
 600         }
 601     }
 602
 603     let (start, accum_positive) = match buf[0] as char {
 604       '-' if !negative => return None,
 605       '-' => (1u, false),
 606       '+' => (1u, true),
 607        _  => (0u, true)
 608     };
 609
 610     // Initialize accumulator with signed zero for floating point parsing to
 611     // work
 612     let mut accum      = if accum_positive { _0.clone() } else { -_1 * _0};
 613     let mut last_accum = accum.clone(); // Necessary to detect overflow
 614     let mut i          = start;
 615     let mut exp_found  = false;
 616
 617     // Parse integer part of number
 618     while i < len {
 619         let c = buf[i] as char;
 620
 621         match char::to_digit(c, radix) {
 622             Some(digit) => {
 623                 // shift accum one digit left
 624                 accum = accum * radix_gen.clone();
 625
 626                 // add/subtract current digit depending on sign
 627                 if accum_positive {
 628                     accum = accum + cast(digit as int).unwrap();
 629                 } else {
 630                     accum = accum - cast(digit as int).unwrap();
 631                 }
 632
 633                 // Detect overflow by comparing to last value, except
 634                 // if we've not seen any non-zero digits.
 635                 if last_accum != _0 {
 636                     if accum_positive && accum <= last_accum { return NumStrConv::inf(); }
 637                     if !accum_positive && accum >= last_accum { return NumStrConv::neg_inf(); }
 638
 639                     // Detect overflow by reversing the shift-and-add proccess
 640                     if accum_positive &&
 641                         (last_accum != ((accum - cast(digit as int).unwrap())/radix_gen.clone())) {
 642                         return NumStrConv::inf();
 643                     }
 644                     if !accum_positive &&
 645                         (last_accum != ((accum + cast(digit as int).unwrap())/radix_gen.clone())) {
 646                         return NumStrConv::neg_inf();
 647                     }
 648                 }
 649                 last_accum = accum.clone();
 650             }
 651             None => match c {
 652                 '_' if ignore_underscores => {}
 653                 'e' | 'E' | 'p' | 'P' => {
 654                     exp_found = true;
 655                     break;                       // start of exponent
 656                 }
 657                 '.' if fractional => {
 658                     i += 1u;                     // skip the '.'
 659                     break;                       // start of fractional part
 660                 }
 661                 _ => return None                 // invalid number
 662             }
 663         }
 664
 665         i += 1u;
 666     }
 667
 668     // Parse fractional part of number
 669     // Skip if already reached start of exponent
 670     if !exp_found {
 671         let mut power = _1.clone();
 672
 673         while i < len {
 674             let c = buf[i] as char;
 675
 676             match char::to_digit(c, radix) {
 677                 Some(digit) => {
 678                     // Decrease power one order of magnitude
 679                     power = power / radix_gen;
 680
 681                     let digit_t: T = cast(digit).unwrap();
 682
 683                     // add/subtract current digit depending on sign
 684                     if accum_positive {
 685                         accum = accum + digit_t * power;
 686                     } else {
 687                         accum = accum - digit_t * power;
 688                     }
 689
 690                     // Detect overflow by comparing to last value
 691                     if accum_positive && accum < last_accum { return NumStrConv::inf(); }
 692                     if !accum_positive && accum > last_accum { return NumStrConv::neg_inf(); }
 693                     last_accum = accum.clone();
 694                 }
 695                 None => match c {
 696                     '_' if ignore_underscores => {}
 697                     'e' | 'E' | 'p' | 'P' => {
 698                         exp_found = true;
 699                         break;                   // start of exponent
 700                     }
 701                     _ => return None             // invalid number
 702                 }
 703             }
 704
 705             i += 1u;
 706         }
 707     }
 708
 709     // Special case: buf not empty, but does not contain any digit in front
 710     // of the exponent sign -> number is empty string
 711     if i == start {
 712         if empty_zero {
 713             return Some(_0);
 714         } else {
 715             return None;
 716         }
 717     }
 718
 719     let mut multiplier = _1.clone();
 720
 721     if exp_found {
 722         let c = buf[i] as char;
 723         let base: T = match (c, exponent) {
 724             // c is never _ so don't need to handle specially
 725             ('e', ExpDec) | ('E', ExpDec) => cast(10u).unwrap(),
 726             ('p', ExpBin) | ('P', ExpBin) => cast(2u).unwrap(),
 727             _ => return None // char doesn't fit given exponent format
 728         };
 729
 730         // parse remaining bytes as decimal integer,
 731         // skipping the exponent char
 732         let exp: Option<int> = from_str_bytes_common(
 733             buf.slice(i+1, len), 10, true, false, false, ExpNone, false,
 734             ignore_underscores);
 735
 736         match exp {
 737             Some(exp_pow) => {
 738                 multiplier = if exp_pow < 0 {
 739                     _1 / num::pow(base, (-exp_pow.to_int().unwrap()) as uint)
 740                 } else {
 741                     num::pow(base, exp_pow.to_int().unwrap() as uint)
 742                 }
 743             }
 744             None => return None // invalid exponent -> invalid number
 745         }
 746     }
 747
 748     Some(accum * multiplier)
 749 }
 750
 751 /**
 752  * Parses a string as a number. This is a wrapper for
 753  * `from_str_bytes_common()`, for details see there.
 754  */
 755 #[inline]
 756 pub fn from_str_common<T:NumCast+Zero+One+Eq+Ord+Div<T,T>+Mul<T,T>+
 757                               Sub<T,T>+Neg<T>+Add<T,T>+NumStrConv+Clone>(
 758         buf: &str, radix: uint, negative: bool, fractional: bool,
 759         special: bool, exponent: ExponentFormat, empty_zero: bool,
 760         ignore_underscores: bool
 761         ) -> Option<T> {
 762     from_str_bytes_common(buf.as_bytes(), radix, negative,
 763                           fractional, special, exponent, empty_zero,
 764                           ignore_underscores)
 765 }
 766
 767 #[cfg(test)]
 768 mod test {
 769     use super::*;
 770     use option::*;
 771
 772     #[test]
 773     fn from_str_ignore_underscores() {
 774         let s : Option<u8> = from_str_common("__1__", 2, false, false, false,
 775                                              ExpNone, false, true);
 776         assert_eq!(s, Some(1u8));
 777
 778         let n : Option<u8> = from_str_common("__1__", 2, false, false, false,
 779                                              ExpNone, false, false);
 780         assert_eq!(n, None);
 781
 782         let f : Option<f32> = from_str_common("_1_._5_e_1_", 10, false, true, false,
 783                                               ExpDec, false, true);
 784         assert_eq!(f, Some(1.5e1f32));
 785     }
 786
 787     #[test]
 788     fn from_str_issue5770() {
 789         // try to parse 0b1_1111_1111 = 511 as a u8. Caused problems
 790         // since 255*2+1 == 255 (mod 256) so the overflow wasn't
 791         // detected.
 792         let n : Option<u8> = from_str_common("111111111", 2, false, false, false,
 793                                              ExpNone, false, false);
 794         assert_eq!(n, None);
 795     }
 796
 797     #[test]
 798     fn from_str_issue7588() {
 799         let u : Option<u8> = from_str_common("1000", 10, false, false, false,
 800                                             ExpNone, false, false);
 801         assert_eq!(u, None);
 802         let s : Option<i16> = from_str_common("80000", 10, false, false, false,
 803                                              ExpNone, false, false);
 804         assert_eq!(s, None);
 805         let f : Option<f32> = from_str_common(
 806             "10000000000000000000000000000000000000000", 10, false, false, false,
 807             ExpNone, false, false);
 808         assert_eq!(f, NumStrConv::inf())
 809         let fe : Option<f32> = from_str_common("1e40", 10, false, false, false,
 810                                             ExpDec, false, false);
 811         assert_eq!(fe, NumStrConv::inf())
 812     }
 813 }
 814
 815 #[cfg(test)]
 816 mod bench {
 817     extern crate test;
 818
 819     mod uint {
 820         use super::test::Bencher;
 821         use rand::{XorShiftRng, Rng};
 822         use num::ToStrRadix;
 823
 824         #[bench]
 825         fn to_str_bin(b: &mut Bencher) {
 826             let mut rng = XorShiftRng::new().unwrap();
 827             b.iter(|| { rng.gen::<uint>().to_str_radix(2); })
 828         }
 829
 830         #[bench]
 831         fn to_str_oct(b: &mut Bencher) {
 832             let mut rng = XorShiftRng::new().unwrap();
 833             b.iter(|| { rng.gen::<uint>().to_str_radix(8); })
 834         }
 835
 836         #[bench]
 837         fn to_str_dec(b: &mut Bencher) {
 838             let mut rng = XorShiftRng::new().unwrap();
 839             b.iter(|| { rng.gen::<uint>().to_str_radix(10); })
 840         }
 841
 842         #[bench]
 843         fn to_str_hex(b: &mut Bencher) {
 844             let mut rng = XorShiftRng::new().unwrap();
 845             b.iter(|| { rng.gen::<uint>().to_str_radix(16); })
 846         }
 847
 848         #[bench]
 849         fn to_str_base_36(b: &mut Bencher) {
 850             let mut rng = XorShiftRng::new().unwrap();
 851             b.iter(|| { rng.gen::<uint>().to_str_radix(36); })
 852         }
 853     }
 854
 855     mod int {
 856         use super::test::Bencher;
 857         use rand::{XorShiftRng, Rng};
 858         use num::ToStrRadix;
 859
 860         #[bench]
 861         fn to_str_bin(b: &mut Bencher) {
 862             let mut rng = XorShiftRng::new().unwrap();
 863             b.iter(|| { rng.gen::<int>().to_str_radix(2); })
 864         }
 865
 866         #[bench]
 867         fn to_str_oct(b: &mut Bencher) {
 868             let mut rng = XorShiftRng::new().unwrap();
 869             b.iter(|| { rng.gen::<int>().to_str_radix(8); })
 870         }
 871
 872         #[bench]
 873         fn to_str_dec(b: &mut Bencher) {
 874             let mut rng = XorShiftRng::new().unwrap();
 875             b.iter(|| { rng.gen::<int>().to_str_radix(10); })
 876         }
 877
 878         #[bench]
 879         fn to_str_hex(b: &mut Bencher) {
 880             let mut rng = XorShiftRng::new().unwrap();
 881             b.iter(|| { rng.gen::<int>().to_str_radix(16); })
 882         }
 883
 884         #[bench]
 885         fn to_str_base_36(b: &mut Bencher) {
 886             let mut rng = XorShiftRng::new().unwrap();
 887             b.iter(|| { rng.gen::<int>().to_str_radix(36); })
 888         }
 889     }
 890
 891     mod f64 {
 892         use super::test::Bencher;
 893         use rand::{XorShiftRng, Rng};
 894         use f64;
 895
 896         #[bench]
 897         fn float_to_str(b: &mut Bencher) {
 898             let mut rng = XorShiftRng::new().unwrap();
 899             b.iter(|| { f64::to_str(rng.gen()); })
 900         }
 901     }
 902 }