1//! Converting decimal strings into IEEE 754 binary floating point numbers.
2//!
3//! # Problem statement
4//!
5//! We are given a decimal string such as `12.34e56`. This string consists of integral (`12`),
6//! fractional (`34`), and exponent (`56`) parts. All parts are optional and interpreted as zero
7//! when missing.
8//!
9//! We seek the IEEE 754 floating point number that is closest to the exact value of the decimal
10//! string. It is well-known that many decimal strings do not have terminating representations in
11//! base two, so we round to 0.5 units in the last place (in other words, as well as possible).
12//! Ties, decimal values exactly half-way between two consecutive floats, are resolved with the
13//! half-to-even strategy, also known as banker's rounding.
14//!
15//! Needless to say, this is quite hard, both in terms of implementation complexity and in terms
16//! of CPU cycles taken.
17//!
18//! # Implementation
19//!
20//! First, we ignore signs. Or rather, we remove it at the very beginning of the conversion
21//! process and re-apply it at the very end. This is correct in all edge cases since IEEE
22//! floats are symmetric around zero, negating one simply flips the first bit.
23//!
24//! Then we remove the decimal point by adjusting the exponent: Conceptually, `12.34e56` turns
25//! into `1234e54`, which we describe with a positive integer `f = 1234` and an integer `e = 54`.
26//! The `(f, e)` representation is used by almost all code past the parsing stage.
27//!
28//! We then try a long chain of progressively more general and expensive special cases using
29//! machine-sized integers and small, fixed-sized floating point numbers (first `f32`/`f64`, then
30//! a type with 64 bit significand). The extended-precision algorithm
31//! uses the Eisel-Lemire algorithm, which uses a 128-bit (or 192-bit)
32//! representation that can accurately and quickly compute the vast majority
33//! of floats. When all these fail, we bite the bullet and resort to using
34//! a large-decimal representation, shifting the digits into range, calculating
35//! the upper significant bits and exactly round to the nearest representation.
36//!
37//! Another aspect that needs attention is the ``RawFloat`` trait by which almost all functions
38//! are parametrized. One might think that it's enough to parse to `f64` and cast the result to
39//! `f32`. Unfortunately this is not the world we live in, and this has nothing to do with using
40//! base two or half-to-even rounding.
41//!
42//! Consider for example two types `d2` and `d4` representing a decimal type with two decimal
43//! digits and four decimal digits each and take "0.01499" as input. Let's use half-up rounding.
44//! Going directly to two decimal digits gives `0.01`, but if we round to four digits first,
45//! we get `0.0150`, which is then rounded up to `0.02`. The same principle applies to other
46//! operations as well, if you want 0.5 ULP accuracy you need to do *everything* in full precision
47//! and round *exactly once, at the end*, by considering all truncated bits at once.
48//!
49//! Primarily, this module and its children implement the algorithms described in:
50//! "Number Parsing at a Gigabyte per Second", available online:
51//! <https://arxiv.org/abs/2101.11408>.
52//!
53//! # Other
54//!
55//! The conversion should *never* panic. There are assertions and explicit panics in the code,
56//! but they should never be triggered and only serve as internal sanity checks. Any panics should
57//! be considered a bug.
58//!
59//! There are unit tests but they are woefully inadequate at ensuring correctness, they only cover
60//! a small percentage of possible errors. Far more extensive tests are located in the directory
61//! `src/etc/test-float-parse` as a Python script.
62//!
63//! A note on integer overflow: Many parts of this file perform arithmetic with the decimal
64//! exponent `e`. Primarily, we shift the decimal point around: Before the first decimal digit,
65//! after the last decimal digit, and so on. This could overflow if done carelessly. We rely on
66//! the parsing submodule to only hand out sufficiently small exponents, where "sufficient" means
67//! "such that the exponent +/- the number of decimal digits fits into a 64 bit integer".
68//! Larger exponents are accepted, but we don't do arithmetic with them, they are immediately
69//! turned into {positive,negative} {zero,infinity}.
70
71#![doc(hidden)]
72#![unstable(
73 feature = "dec2flt",
74 reason = "internal routines only exposed for testing",
75 issue = "none"
76)]
77
78use crate::error::Error;
79use crate::fmt;
80use crate::str::FromStr;
81
82use self::common::BiasedFp;
83use self::float::RawFloat;
84use self::lemire::compute_float;
85use self::parse::{parse_inf_nan, parse_number};
86use self::slow::parse_long_mantissa;
87
88mod common;
89mod decimal;
90mod fpu;
91mod slow;
92mod table;
93// float is used in flt2dec, and all are used in unit tests.
94pub mod float;
95pub mod lemire;
96pub mod number;
97pub mod parse;
98
99macro_rules! from_str_float_impl {
100 ($t:ty) => {
101 #[stable(feature = "rust1", since = "1.0.0")]
102 impl FromStr for $t {
103 type Err = ParseFloatError;
104
105 /// Converts a string in base 10 to a float.
106 /// Accepts an optional decimal exponent.
107 ///
108 /// This function accepts strings such as
109 ///
110 /// * '3.14'
111 /// * '-3.14'
112 /// * '2.5E10', or equivalently, '2.5e10'
113 /// * '2.5E-10'
114 /// * '5.'
115 /// * '.5', or, equivalently, '0.5'
116 /// * 'inf', '-inf', '+infinity', 'NaN'
117 ///
118 /// Note that alphabetical characters are not case-sensitive.
119 ///
120 /// Leading and trailing whitespace represent an error.
121 ///
122 /// # Grammar
123 ///
124 /// All strings that adhere to the following [EBNF] grammar when
125 /// lowercased will result in an [`Ok`] being returned:
126 ///
127 /// ```txt
128 /// Float ::= Sign? ( 'inf' | 'infinity' | 'nan' | Number )
129 /// Number ::= ( Digit+ |
130 /// Digit+ '.' Digit* |
131 /// Digit* '.' Digit+ ) Exp?
132 /// Exp ::= 'e' Sign? Digit+
133 /// Sign ::= [+-]
134 /// Digit ::= [0-9]
135 /// ```
136 ///
137 /// [EBNF]: https://www.w3.org/TR/REC-xml/#sec-notation
138 ///
139 /// # Arguments
140 ///
141 /// * src - A string
142 ///
143 /// # Return value
144 ///
145 /// `Err(ParseFloatError)` if the string did not represent a valid
146 /// number. Otherwise, `Ok(n)` where `n` is the closest
147 /// representable floating-point number to the number represented
148 /// by `src` (following the same rules for rounding as for the
149 /// results of primitive operations).
150 // We add the `#[inline(never)]` attribute, since its content will
151 // be filled with that of `dec2flt`, which has #[inline(always)].
152 // Since `dec2flt` is generic, a normal inline attribute on this function
153 // with `dec2flt` having no attributes results in heavily repeated
154 // generation of `dec2flt`, despite the fact only a maximum of 2
155 // possible instances can ever exist. Adding #[inline(never)] avoids this.
156 #[inline(never)]
157 fn from_str(src: &str) -> Result<Self, ParseFloatError> {
158 dec2flt(src)
159 }
160 }
161 };
162}
163from_str_float_impl!(f32);
164from_str_float_impl!(f64);
165
166/// An error which can be returned when parsing a float.
167///
168/// This error is used as the error type for the [`FromStr`] implementation
169/// for [`f32`] and [`f64`].
170///
171/// # Example
172///
173/// ```
174/// use std::str::FromStr;
175///
176/// if let Err(e) = f64::from_str("a.12") {
177/// println!("Failed conversion to f64: {e}");
178/// }
179/// ```
180#[derive(Debug, Clone, PartialEq, Eq)]
181#[stable(feature = "rust1", since = "1.0.0")]
182pub struct ParseFloatError {
183 kind: FloatErrorKind,
184}
185
186#[derive(Debug, Clone, PartialEq, Eq)]
187enum FloatErrorKind {
188 Empty,
189 Invalid,
190}
191
192#[stable(feature = "rust1", since = "1.0.0")]
193impl Error for ParseFloatError {
194 #[allow(deprecated)]
195 fn description(&self) -> &str {
196 match self.kind {
197 FloatErrorKind::Empty => "cannot parse float from empty string",
198 FloatErrorKind::Invalid => "invalid float literal",
199 }
200 }
201}
202
203#[stable(feature = "rust1", since = "1.0.0")]
204impl fmt::Display for ParseFloatError {
205 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
206 #[allow(deprecated)]
207 self.description().fmt(f)
208 }
209}
210
211#[inline]
212pub(super) fn pfe_empty() -> ParseFloatError {
213 ParseFloatError { kind: FloatErrorKind::Empty }
214}
215
216// Used in unit tests, keep public.
217// This is much better than making FloatErrorKind and ParseFloatError::kind public.
218#[inline]
219pub fn pfe_invalid() -> ParseFloatError {
220 ParseFloatError { kind: FloatErrorKind::Invalid }
221}
222
223/// Converts a `BiasedFp` to the closest machine float type.
224fn biased_fp_to_float<T: RawFloat>(x: BiasedFp) -> T {
225 let mut word: u64 = x.f;
226 word |= (x.e as u64) << T::MANTISSA_EXPLICIT_BITS;
227 T::from_u64_bits(word)
228}
229
230/// Converts a decimal string into a floating point number.
231#[inline(always)] // Will be inlined into a function with `#[inline(never)]`, see above
232pub fn dec2flt<F: RawFloat>(s: &str) -> Result<F, ParseFloatError> {
233 let mut s = s.as_bytes();
234 let c = if let Some(&c) = s.first() {
235 c
236 } else {
237 return Err(pfe_empty());
238 };
239 let negative = c == b'-';
240 if c == b'-' || c == b'+' {
241 s = &s[1..];
242 }
243 if s.is_empty() {
244 return Err(pfe_invalid());
245 }
246
247 let mut num = match parse_number(s) {
248 Some(r) => r,
249 None if let Some(value) = parse_inf_nan(s, negative) => return Ok(value),
250 None => return Err(pfe_invalid()),
251 };
252 num.negative = negative;
253 if let Some(value) = num.try_fast_path::<F>() {
254 return Ok(value);
255 }
256
257 // If significant digits were truncated, then we can have rounding error
258 // only if `mantissa + 1` produces a different result. We also avoid
259 // redundantly using the Eisel-Lemire algorithm if it was unable to
260 // correctly round on the first pass.
261 let mut fp = compute_float::<F>(num.exponent, num.mantissa);
262 if num.many_digits && fp.e >= 0 && fp != compute_float::<F>(num.exponent, num.mantissa + 1) {
263 fp.e = -1;
264 }
265 // Unable to correctly round the float using the Eisel-Lemire algorithm.
266 // Fallback to a slower, but always correct algorithm.
267 if fp.e < 0 {
268 fp = parse_long_mantissa::<F>(s);
269 }
270
271 let mut float = biased_fp_to_float::<F>(fp);
272 if num.negative {
273 float = -float;
274 }
275 Ok(float)
276}
277