1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
//! 将十进制字符串转换为 IEEE 754 二进制浮点数。
//!
//! # 问题陈述
//!
//! 我们给了一个十进制字符串,例如 `12.34e56`。
//! 该字符串由整数 (`12`),小数 (`34`) 和指数 (`56`) 组成。所有部分都是可选的,缺少则解释为零。
//!
//! 我们寻求最接近十进制字符串确切值的 IEEE 754 浮点数。
//! 众所周知,许多十进制字符串在基数 2 中都没有终止表示,因此我们将 0.5 单位最后舍入 (换句话说,尽可能)。
//! 领带 (精确到两个连续浮点之间的中间的十进制值) 通过半对偶策略 (也称为银行家舍入) 来解决。
//!
//! 不用说,这在实现复杂性和所用的 CPU 周期方面都相当困难。
//!
//! # Implementation
//!
//! 首先,我们忽略迹象。或者更确切地说,我们在转换过程的开始就将其删除,然后在结束时将其重新应用。
//! 这在所有 edge 情况下都是正确的,因为 IEEE 浮点数对称于零左右,取反则仅翻转第一位。
//!
//! 然后,我们通过调整指数来删除小数点: 从概念上讲,`12.34e56` 变为 `1234e54`,我们用正整数 `f = 1234` 和整数 `e = 54` 对其进行描述。
//! 在解析阶段之后,几乎所有代码都使用 `(f, e)` 表示形式。
//!
//! 然后,我们尝试使用机器大小的整数和固定大小的小浮点数 (首先是 `f32`/`f64`,然后是具有 64 位有效数的类型) 的一长串越来越普遍和昂贵的特殊情况。
//!
//! 扩展精度算法使用 Eisel-Lemire 算法,该算法使用 128 位 (或 192 位) 表示,可以准确快速地计算绝大多数浮点数。
//! 当所有这些都失败时,我们硬着头皮求助于使用大十进制表示,将数字移入范围,计算高位有效位并精确四舍五入到最近的表示。
//!
//! 需要注意的另一个方面是 ``RawFloat`` trait,几乎所有函数都通过 ``RawFloat`` trait 进行了参数化。有人可能认为解析为 `f64` 并将结果转换为 `f32` 就足够了。
//! 不幸的是,这不是我们生活的世界,这与使用基数二进位或半到四舍五入四舍五入无关。
//!
//! 例如,考虑两种类型的 `d2` 和 `d4`,它们代表具有两个十进制数字和四个十进制数字的十进制类型,并以 "0.01499" 作为输入。让我们使用上半舍入。
//! 直接转到两位十进制数字将得到 `0.01`,但是如果我们首先四舍五入到四位数字,则会得到 `0.0150`,然后将其四舍五入为 `0.02`。
//! 同样的原理也适用于其他操作,如果要获得 0.5 ULP 精度,则需要 *进行全精度的所有操作,并在末尾将* exactly once 舍入*,同时考虑所有截断的位。
//!
//! 首先,此模块及其子级实现以下算法:
//! "Number Parsing at a Gigabyte per Second", 在线提供: <https://arxiv.org/abs/2101.11408>.
//!
//! # Other
//!
//! 转换应 *从不* panic。
//! 在代码中有断言和显式的 panics,但是它们绝不应该被触发,而仅用作内部的健全性检查。任何 panics 都应视为错误。
//!
//! 虽然有单元测试,但它们在确保正确性上还远远不够,它们只覆盖了很小一部分可能的错误。
//! 更广泛的测试作为 Python 脚本位于目录 `src/etc/test-float-parse` 中。
//!
//! 关于整型溢出的注意事项: 该文件的许多部分都使用十进制指数 `e` 来执行算术运算。
//! 首先,我们将小数点移动: 在第一个十进制数字之前,在最后一个十进制数字之后,依此类推。如果不小心这样做可能会溢出。
//! 我们依靠解析子模块仅分发足够小的指数,其中 "sufficient" 表示 "such that the exponent +/- the number of decimal digits fits into a 64 bit integer"。
//! 较大的指数被接受,但是我们不对它们进行算术运算,它们立即变成 {positive,negative} {zero,infinity}。
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!

#![doc(hidden)]
#![unstable(
    feature = "dec2flt",
    reason = "internal routines only exposed for testing",
    issue = "none"
)]

use crate::fmt;
use crate::str::FromStr;

use self::common::{BiasedFp, ByteSlice};
use self::float::RawFloat;
use self::lemire::compute_float;
use self::parse::{parse_inf_nan, parse_number};
use self::slow::parse_long_mantissa;

mod common;
mod decimal;
mod fpu;
mod slow;
mod table;
// 在 flt2dec 中使用 float,在单元测试中全部使用。
pub mod float;
pub mod lemire;
pub mod number;
pub mod parse;

macro_rules! from_str_float_impl {
    ($t:ty) => {
        #[stable(feature = "rust1", since = "1.0.0")]
        impl FromStr for $t {
            type Err = ParseFloatError;

            /// 将以 10 为底的字符串转换为浮点数。
            /// 接受可选的十进制指数。
            ///
            /// 该函数接受诸如以下的字符串
            ///
            /// * '3.14'
            /// * '-3.14'
            /// * '2.5E10', 或等效地, '2.5e10'
            /// * '2.5E-10'
            /// * '5.'
            /// * '.5', 或者,等效地, '0.5'
            /// * 'inf', '-inf', 'NaN'
            ///
            /// 前导和尾随空格表示错误。
            ///
            /// # Grammar
            ///
            /// 遵循以下 [EBNF] 语法的所有字符串都将导致返回 [`Ok`]:
            ///
            ///
            /// ```txt
            /// Float  ::= Sign? ( 'inf' | 'NaN' | Number )
            /// Number ::= ( Digit+ |
            ///              Digit+ '.' Digit* |
            ///              Digit* '.' Digit+ ) Exp?
            /// Exp    ::= [eE] Sign? Digit+
            /// Sign   ::= [+-]
            /// Digit  ::= [0-9]
            /// ```
            ///
            /// [EBNF]: https://www.w3.org/TR/REC-xml/#sec-notation
            ///
            /// # Arguments
            ///
            /// * src - 字符串
            ///
            /// # 返回值
            ///
            /// `Err(ParseFloatError)` 如果字符串不代表有效数字。
            /// 否则,为 `Ok(n)`,其中 `n` 是 `src` 表示的浮点数。
            ///
            #[inline]
            fn from_str(src: &str) -> Result<Self, ParseFloatError> {
                dec2flt(src)
            }
        }
    };
}
from_str_float_impl!(f32);
from_str_float_impl!(f64);

/// 解析浮点数时可以返回的错误。
///
/// 该错误用作 [`f32`] 和 [`f64`] 的 [`FromStr`] 实现的错误类型。
///
///
/// # Example
///
/// ```
/// use std::str::FromStr;
///
/// if let Err(e) = f64::from_str("a.12") {
///     println!("Failed conversion to f64: {}", e);
/// }
/// ```
#[derive(Debug, Clone, PartialEq, Eq)]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct ParseFloatError {
    kind: FloatErrorKind,
}

#[derive(Debug, Clone, PartialEq, Eq)]
enum FloatErrorKind {
    Empty,
    Invalid,
}

impl ParseFloatError {
    #[unstable(
        feature = "int_error_internals",
        reason = "available through Error trait and this method should \
                  not be exposed publicly",
        issue = "none"
    )]
    #[doc(hidden)]
    pub fn __description(&self) -> &str {
        match self.kind {
            FloatErrorKind::Empty => "cannot parse float from empty string",
            FloatErrorKind::Invalid => "invalid float literal",
        }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl fmt::Display for ParseFloatError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        self.__description().fmt(f)
    }
}

pub(super) fn pfe_empty() -> ParseFloatError {
    ParseFloatError { kind: FloatErrorKind::Empty }
}

// 用于单元测试,保持公开。
// 这比公开 FloatErrorKind 和 ParseFloatError::kind 好得多。
pub fn pfe_invalid() -> ParseFloatError {
    ParseFloatError { kind: FloatErrorKind::Invalid }
}

/// 将 `BiasedFp` 转换为最接近的机器浮点类型。
fn biased_fp_to_float<T: RawFloat>(x: BiasedFp) -> T {
    let mut word = x.f;
    word |= (x.e as u64) << T::MANTISSA_EXPLICIT_BITS;
    T::from_u64_bits(word)
}

/// 将十进制字符串转换为浮点数。
pub fn dec2flt<F: RawFloat>(s: &str) -> Result<F, ParseFloatError> {
    let mut s = s.as_bytes();
    let c = if let Some(&c) = s.first() {
        c
    } else {
        return Err(pfe_empty());
    };
    let negative = c == b'-';
    if c == b'-' || c == b'+' {
        s = s.advance(1);
    }
    if s.is_empty() {
        return Err(pfe_invalid());
    }

    let num = match parse_number(s, negative) {
        Some(r) => r,
        None => {
            if let Some(value) = parse_inf_nan(s, negative) {
                return Ok(value);
            } else {
                return Err(pfe_invalid());
            }
        }
    };
    if let Some(value) = num.try_fast_path::<F>() {
        return Ok(value);
    }

    // 如果有效数字被截断,那么只有当 `mantissa + 1` 产生不同的结果时,我们才会有舍入错误。
    // 如果 Eisel-Lemire 算法无法在第一次通过时正确取整,我们也会避免使用多余的 Eisel-Lemire 算法。
    //
    //
    let mut fp = compute_float::<F>(num.exponent, num.mantissa);
    if num.many_digits && fp.e >= 0 && fp != compute_float::<F>(num.exponent, num.mantissa + 1) {
        fp.e = -1;
    }
    // 无法使用 Eisel-Lemire 算法正确舍入浮点数。
    // 回退到较慢但始终正确的算法。
    if fp.e < 0 {
        fp = parse_long_mantissa::<F>(s);
    }

    let mut float = biased_fp_to_float::<F>(fp);
    if num.negative {
        float = -float;
    }
    Ok(float)
}