add libcore from 2016-04-11 nightly

1 files changed, 662 insertions, 0 deletions

diff --git a/libcore/num/flt2dec/mod.rs b/libcore/num/flt2dec/mod.rs
new file mode 100644
index 0000000..b549f33
--- /dev/null
+++ b/libcore/num/flt2dec/mod.rs
@@ -0,0 +1,662 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+/*!
+
+Floating-point number to decimal conversion routines.
+
+# Problem statement
+
+We are given the floating-point number `v = f * 2^e` with an integer `f`,
+and its bounds `minus` and `plus` such that any number between `v - minus` and
+`v + plus` will be rounded to `v`. For the simplicity we assume that
+this range is exclusive. Then we would like to get the unique decimal
+representation `V = 0.d[0..n-1] * 10^k` such that:
+
+- `d[0]` is non-zero.
+
+- It's correctly rounded when parsed back: `v - minus < V < v + plus`.
+  Furthermore it is shortest such one, i.e. there is no representation
+  with less than `n` digits that is correctly rounded.
+
+- It's closest to the original value: `abs(V - v) <= 10^(k-n) / 2`. Note that
+  there might be two representations satisfying this uniqueness requirement,
+  in which case some tie-breaking mechanism is used.
+
+We will call this mode of operation as to the *shortest* mode. This mode is used
+when there is no additional constraint, and can be thought as a "natural" mode
+as it matches the ordinary intuition (it at least prints `0.1f32` as "0.1").
+
+We have two more modes of operation closely related to each other. In these modes
+we are given either the number of significant digits `n` or the last-digit
+limitation `limit` (which determines the actual `n`), and we would like to get
+the representation `V = 0.d[0..n-1] * 10^k` such that:
+
+- `d[0]` is non-zero, unless `n` was zero in which case only `k` is returned.
+
+- It's closest to the original value: `abs(V - v) <= 10^(k-n) / 2`. Again,
+  there might be some tie-breaking mechanism.
+
+When `limit` is given but not `n`, we set `n` such that `k - n = limit`
+so that the last digit `d[n-1]` is scaled by `10^(k-n) = 10^limit`.
+If such `n` is negative, we clip it to zero so that we will only get `k`.
+We are also limited by the supplied buffer. This limitation is used to print
+the number up to given number of fractional digits without knowing
+the correct `k` beforehand.
+
+We will call the mode of operation requiring `n` as to the *exact* mode,
+and one requiring `limit` as to the *fixed* mode. The exact mode is a subset of
+the fixed mode: the sufficiently large last-digit limitation will eventually fill
+the supplied buffer and let the algorithm to return.
+
+# Implementation overview
+
+It is easy to get the floating point printing correct but slow (Russ Cox has
+[demonstrated](http://research.swtch.com/ftoa) how it's easy), or incorrect but
+fast (naïve division and modulo). But it is surprisingly hard to print
+floating point numbers correctly *and* efficiently.
+
+There are two classes of algorithms widely known to be correct.
+
+- The "Dragon" family of algorithm is first described by Guy L. Steele Jr. and
+  Jon L. White. They rely on the fixed-size big integer for their correctness.
+  A slight improvement was found later, which is posthumously described by
+  Robert G. Burger and R. Kent Dybvig. David Gay's `dtoa.c` routine is
+  a popular implementation of this strategy.
+
+- The "Grisu" family of algorithm is first described by Florian Loitsch.
+  They use very cheap integer-only procedure to determine the close-to-correct
+  representation which is at least guaranteed to be shortest. The variant,
+  Grisu3, actively detects if the resulting representation is incorrect.
+
+We implement both algorithms with necessary tweaks to suit our requirements.
+In particular, published literatures are short of the actual implementation
+difficulties like how to avoid arithmetic overflows. Each implementation,
+available in `strategy::dragon` and `strategy::grisu` respectively,
+extensively describes all necessary justifications and many proofs for them.
+(It is still difficult to follow though. You have been warned.)
+
+Both implementations expose two public functions:
+
+- `format_shortest(decoded, buf)`, which always needs at least
+  `MAX_SIG_DIGITS` digits of buffer. Implements the shortest mode.
+
+- `format_exact(decoded, buf, limit)`, which accepts as small as
+  one digit of buffer. Implements exact and fixed modes.
+
+They try to fill the `u8` buffer with digits and returns the number of digits
+written and the exponent `k`. They are total for all finite `f32` and `f64`
+inputs (Grisu internally falls back to Dragon if necessary).
+
+The rendered digits are formatted into the actual string form with
+four functions:
+
+- `to_shortest_str` prints the shortest representation, which can be padded by
+  zeroes to make *at least* given number of fractional digits.
+
+- `to_shortest_exp_str` prints the shortest representation, which can be
+  padded by zeroes when its exponent is in the specified ranges,
+  or can be printed in the exponential form such as `1.23e45`.
+
+- `to_exact_exp_str` prints the exact representation with given number of
+  digits in the exponential form.
+
+- `to_exact_fixed_str` prints the fixed representation with *exactly*
+  given number of fractional digits.
+
+They all return a slice of preallocated `Part` array, which corresponds to
+the individual part of strings: a fixed string, a part of rendered digits,
+a number of zeroes or a small (`u16`) number. The caller is expected to
+provide a large enough buffer and `Part` array, and to assemble the final
+string from resulting `Part`s itself.
+
+All algorithms and formatting functions are accompanied by extensive tests
+in `coretest::num::flt2dec` module. It also shows how to use individual
+functions.
+
+*/
+
+// while this is extensively documented, this is in principle private which is
+// only made public for testing. do not expose us.
+#![doc(hidden)]
+#![unstable(feature = "flt2dec",
+            reason = "internal routines only exposed for testing",
+            issue = "0")]
+
+use prelude::v1::*;
+use i16;
+pub use self::decoder::{decode, DecodableFloat, FullDecoded, Decoded};
+
+pub mod estimator;
+pub mod decoder;
+
+/// Digit-generation algorithms.
+pub mod strategy {
+    pub mod dragon;
+    pub mod grisu;
+}
+
+/// The minimum size of buffer necessary for the shortest mode.
+///
+/// It is a bit non-trivial to derive, but this is one plus the maximal number of
+/// significant decimal digits from formatting algorithms with the shortest result.
+/// The exact formula is `ceil(# bits in mantissa * log_10 2 + 1)`.
+pub const MAX_SIG_DIGITS: usize = 17;
+
+/// When `d[..n]` contains decimal digits, increase the last digit and propagate carry.
+/// Returns a next digit when it causes the length change.
+#[doc(hidden)]
+pub fn round_up(d: &mut [u8], n: usize) -> Option<u8> {
+    match d[..n].iter().rposition(|&c| c != b'9') {
+        Some(i) => { // d[i+1..n] is all nines
+            d[i] += 1;
+            for j in i+1..n { d[j] = b'0'; }
+            None
+        }
+        None if n > 0 => { // 999..999 rounds to 1000..000 with an increased exponent
+            d[0] = b'1';
+            for j in 1..n { d[j] = b'0'; }
+            Some(b'0')
+        }
+        None => { // an empty buffer rounds up (a bit strange but reasonable)
+            Some(b'1')
+        }
+    }
+}
+
+/// Formatted parts.
+#[derive(Copy, Clone, PartialEq, Eq, Debug)]
+pub enum Part<'a> {
+    /// Given number of zero digits.
+    Zero(usize),
+    /// A literal number up to 5 digits.
+    Num(u16),
+    /// A verbatim copy of given bytes.
+    Copy(&'a [u8]),
+}
+
+impl<'a> Part<'a> {
+    /// Returns the exact byte length of given part.
+    pub fn len(&self) -> usize {
+        match *self {
+            Part::Zero(nzeroes) => nzeroes,
+            Part::Num(v) => if v < 1_000 { if v < 10 { 1 } else if v < 100 { 2 } else { 3 } }
+                            else { if v < 10_000 { 4 } else { 5 } },
+            Part::Copy(buf) => buf.len(),
+        }
+    }
+
+    /// Writes a part into the supplied buffer.
+    /// Returns the number of written bytes, or `None` if the buffer is not enough.
+    /// (It may still leave partially written bytes in the buffer; do not rely on that.)
+    pub fn write(&self, out: &mut [u8]) -> Option<usize> {
+        let len = self.len();
+        if out.len() >= len {
+            match *self {
+                Part::Zero(nzeroes) => {
+                    for c in &mut out[..nzeroes] { *c = b'0'; }
+                }
+                Part::Num(mut v) => {
+                    for c in out[..len].iter_mut().rev() {
+                        *c = b'0' + (v % 10) as u8;
+                        v /= 10;
+                    }
+                }
+                Part::Copy(buf) => {
+                    out[..buf.len()].copy_from_slice(buf);
+                }
+            }
+            Some(len)
+        } else {
+            None
+        }
+    }
+}
+
+/// Formatted result containing one or more parts.
+/// This can be written to the byte buffer or converted to the allocated string.
+#[allow(missing_debug_implementations)]
+#[derive(Clone)]
+pub struct Formatted<'a> {
+    /// A byte slice representing a sign, either `""`, `"-"` or `"+"`.
+    pub sign: &'static [u8],
+    /// Formatted parts to be rendered after a sign and optional zero padding.
+    pub parts: &'a [Part<'a>],
+}
+
+impl<'a> Formatted<'a> {
+    /// Returns the exact byte length of combined formatted result.
+    pub fn len(&self) -> usize {
+        let mut len = self.sign.len();
+        for part in self.parts {
+            len += part.len();
+        }
+        len
+    }
+
+    /// Writes all formatted parts into the supplied buffer.
+    /// Returns the number of written bytes, or `None` if the buffer is not enough.
+    /// (It may still leave partially written bytes in the buffer; do not rely on that.)
+    pub fn write(&self, out: &mut [u8]) -> Option<usize> {
+        if out.len() < self.sign.len() { return None; }
+        out[..self.sign.len()].copy_from_slice(self.sign);
+
+        let mut written = self.sign.len();
+        for part in self.parts {
+            match part.write(&mut out[written..]) {
+                Some(len) => { written += len; }
+                None => { return None; }
+            }
+        }
+        Some(written)
+    }
+}
+
+/// Formats given decimal digits `0.<...buf...> * 10^exp` into the decimal form
+/// with at least given number of fractional digits. The result is stored to
+/// the supplied parts array and a slice of written parts is returned.
+///
+/// `frac_digits` can be less than the number of actual fractional digits in `buf`;
+/// it will be ignored and full digits will be printed. It is only used to print
+/// additional zeroes after rendered digits. Thus `frac_digits` of 0 means that
+/// it will only print given digits and nothing else.
+fn digits_to_dec_str<'a>(buf: &'a [u8], exp: i16, frac_digits: usize,
+                         parts: &'a mut [Part<'a>]) -> &'a [Part<'a>] {
+    assert!(!buf.is_empty());
+    assert!(buf[0] > b'0');
+    assert!(parts.len() >= 4);
+
+    // if there is the restriction on the last digit position, `buf` is assumed to be
+    // left-padded with the virtual zeroes. the number of virtual zeroes, `nzeroes`,
+    // equals to `max(0, exp + frac_digits - buf.len())`, so that the position of
+    // the last digit `exp - buf.len() - nzeroes` is no more than `-frac_digits`:
+    //
+    //                       |<-virtual->|
+    //       |<---- buf ---->|  zeroes   |     exp
+    //    0. 1 2 3 4 5 6 7 8 9 _ _ _ _ _ _ x 10
+    //    |                  |           |
+    // 10^exp    10^(exp-buf.len())   10^(exp-buf.len()-nzeroes)
+    //
+    // `nzeroes` is individually calculated for each case in order to avoid overflow.
+
+    if exp <= 0 {
+        // the decimal point is before rendered digits: [0.][000...000][1234][____]
+        let minus_exp = -(exp as i32) as usize;
+        parts[0] = Part::Copy(b"0.");
+        parts[1] = Part::Zero(minus_exp);
+        parts[2] = Part::Copy(buf);
+        if frac_digits > buf.len() && frac_digits - buf.len() > minus_exp {
+            parts[3] = Part::Zero((frac_digits - buf.len()) - minus_exp);
+            &parts[..4]
+        } else {
+            &parts[..3]
+        }
+    } else {
+        let exp = exp as usize;
+        if exp < buf.len() {
+            // the decimal point is inside rendered digits: [12][.][34][____]
+            parts[0] = Part::Copy(&buf[..exp]);
+            parts[1] = Part::Copy(b".");
+            parts[2] = Part::Copy(&buf[exp..]);
+            if frac_digits > buf.len() - exp {
+                parts[3] = Part::Zero(frac_digits - (buf.len() - exp));
+                &parts[..4]
+            } else {
+                &parts[..3]
+            }
+        } else {
+            // the decimal point is after rendered digits: [1234][____0000] or [1234][__][.][__].
+            parts[0] = Part::Copy(buf);
+            parts[1] = Part::Zero(exp - buf.len());
+            if frac_digits > 0 {
+                parts[2] = Part::Copy(b".");
+                parts[3] = Part::Zero(frac_digits);
+                &parts[..4]
+            } else {
+                &parts[..2]
+            }
+        }
+    }
+}
+
+/// Formats given decimal digits `0.<...buf...> * 10^exp` into the exponential form
+/// with at least given number of significant digits. When `upper` is true,
+/// the exponent will be prefixed by `E`; otherwise that's `e`. The result is
+/// stored to the supplied parts array and a slice of written parts is returned.
+///
+/// `min_digits` can be less than the number of actual significant digits in `buf`;
+/// it will be ignored and full digits will be printed. It is only used to print
+/// additional zeroes after rendered digits. Thus `min_digits` of 0 means that
+/// it will only print given digits and nothing else.
+fn digits_to_exp_str<'a>(buf: &'a [u8], exp: i16, min_ndigits: usize, upper: bool,
+                         parts: &'a mut [Part<'a>]) -> &'a [Part<'a>] {
+    assert!(!buf.is_empty());
+    assert!(buf[0] > b'0');
+    assert!(parts.len() >= 6);
+
+    let mut n = 0;
+
+    parts[n] = Part::Copy(&buf[..1]);
+    n += 1;
+
+    if buf.len() > 1 || min_ndigits > 1 {
+        parts[n] = Part::Copy(b".");
+        parts[n + 1] = Part::Copy(&buf[1..]);
+        n += 2;
+        if min_ndigits > buf.len() {
+            parts[n] = Part::Zero(min_ndigits - buf.len());
+            n += 1;
+        }
+    }
+
+    // 0.1234 x 10^exp = 1.234 x 10^(exp-1)
+    let exp = exp as i32 - 1; // avoid underflow when exp is i16::MIN
+    if exp < 0 {
+        parts[n] = Part::Copy(if upper { b"E-" } else { b"e-" });
+        parts[n + 1] = Part::Num(-exp as u16);
+    } else {
+        parts[n] = Part::Copy(if upper { b"E" } else { b"e" });
+        parts[n + 1] = Part::Num(exp as u16);
+    }
+    &parts[..n + 2]
+}
+
+/// Sign formatting options.
+#[derive(Copy, Clone, PartialEq, Eq, Debug)]
+pub enum Sign {
+    /// Prints `-` only for the negative non-zero values.
+    Minus,        // -inf -1  0  0  1  inf nan
+    /// Prints `-` only for any negative values (including the negative zero).
+    MinusRaw,     // -inf -1 -0  0  1  inf nan
+    /// Prints `-` for the negative non-zero values, or `+` otherwise.
+    MinusPlus,    // -inf -1 +0 +0 +1 +inf nan
+    /// Prints `-` for any negative values (including the negative zero), or `+` otherwise.
+    MinusPlusRaw, // -inf -1 -0 +0 +1 +inf nan
+}
+
+/// Returns the static byte string corresponding to the sign to be formatted.
+/// It can be either `b""`, `b"+"` or `b"-"`.
+fn determine_sign(sign: Sign, decoded: &FullDecoded, negative: bool) -> &'static [u8] {
+    match (*decoded, sign) {
+        (FullDecoded::Nan, _) => b"",
+        (FullDecoded::Zero, Sign::Minus) => b"",
+        (FullDecoded::Zero, Sign::MinusRaw) => if negative { b"-" } else { b"" },
+        (FullDecoded::Zero, Sign::MinusPlus) => b"+",
+        (FullDecoded::Zero, Sign::MinusPlusRaw) => if negative { b"-" } else { b"+" },
+        (_, Sign::Minus) | (_, Sign::MinusRaw) => if negative { b"-" } else { b"" },
+        (_, Sign::MinusPlus) | (_, Sign::MinusPlusRaw) => if negative { b"-" } else { b"+" },
+    }
+}
+
+/// Formats given floating point number into the decimal form with at least
+/// given number of fractional digits. The result is stored to the supplied parts
+/// array while utilizing given byte buffer as a scratch. `upper` is currently
+/// unused but left for the future decision to change the case of non-finite values,
+/// i.e. `inf` and `nan`. The first part to be rendered is always a `Part::Sign`
+/// (which can be an empty string if no sign is rendered).
+///
+/// `format_shortest` should be the underlying digit-generation function.
+/// You probably would want `strategy::grisu::format_shortest` for this.
+///
+/// `frac_digits` can be less than the number of actual fractional digits in `v`;
+/// it will be ignored and full digits will be printed. It is only used to print
+/// additional zeroes after rendered digits. Thus `frac_digits` of 0 means that
+/// it will only print given digits and nothing else.
+///
+/// The byte buffer should be at least `MAX_SIG_DIGITS` bytes long.
+/// There should be at least 5 parts available, due to the worst case like
+/// `[+][0.][0000][45][0000]` with `frac_digits = 10`.
+pub fn to_shortest_str<'a, T, F>(mut format_shortest: F, v: T,
+                                 sign: Sign, frac_digits: usize, _upper: bool,
+                                 buf: &'a mut [u8], parts: &'a mut [Part<'a>]) -> Formatted<'a>
+        where T: DecodableFloat, F: FnMut(&Decoded, &mut [u8]) -> (usize, i16) {
+    assert!(parts.len() >= 4);
+    assert!(buf.len() >= MAX_SIG_DIGITS);
+
+    let (negative, full_decoded) = decode(v);
+    let sign = determine_sign(sign, &full_decoded, negative);
+    match full_decoded {
+        FullDecoded::Nan => {
+            parts[0] = Part::Copy(b"NaN");
+            Formatted { sign: sign, parts: &parts[..1] }
+        }
+        FullDecoded::Infinite => {
+            parts[0] = Part::Copy(b"inf");
+            Formatted { sign: sign, parts: &parts[..1] }
+        }
+        FullDecoded::Zero => {
+            if frac_digits > 0 { // [0.][0000]
+                parts[0] = Part::Copy(b"0.");
+                parts[1] = Part::Zero(frac_digits);
+                Formatted { sign: sign, parts: &parts[..2] }
+            } else {
+                parts[0] = Part::Copy(b"0");
+                Formatted { sign: sign, parts: &parts[..1] }
+            }
+        }
+        FullDecoded::Finite(ref decoded) => {
+            let (len, exp) = format_shortest(decoded, buf);
+            Formatted { sign: sign,
+                        parts: digits_to_dec_str(&buf[..len], exp, frac_digits, parts) }
+        }
+    }
+}
+
+/// Formats given floating point number into the decimal form or
+/// the exponential form, depending on the resulting exponent. The result is
+/// stored to the supplied parts array while utilizing given byte buffer
+/// as a scratch. `upper` is used to determine the case of non-finite values
+/// (`inf` and `nan`) or the case of the exponent prefix (`e` or `E`).
+/// The first part to be rendered is always a `Part::Sign` (which can be
+/// an empty string if no sign is rendered).
+///
+/// `format_shortest` should be the underlying digit-generation function.
+/// You probably would want `strategy::grisu::format_shortest` for this.
+///
+/// The `dec_bounds` is a tuple `(lo, hi)` such that the number is formatted
+/// as decimal only when `10^lo <= V < 10^hi`. Note that this is the *apparent* `V`
+/// instead of the actual `v`! Thus any printed exponent in the exponential form
+/// cannot be in this range, avoiding any confusion.
+///
+/// The byte buffer should be at least `MAX_SIG_DIGITS` bytes long.
+/// There should be at least 7 parts available, due to the worst case like
+/// `[+][1][.][2345][e][-][67]`.
+pub fn to_shortest_exp_str<'a, T, F>(mut format_shortest: F, v: T,
+                                     sign: Sign, dec_bounds: (i16, i16), upper: bool,
+                                     buf: &'a mut [u8], parts: &'a mut [Part<'a>]) -> Formatted<'a>
+        where T: DecodableFloat, F: FnMut(&Decoded, &mut [u8]) -> (usize, i16) {
+    assert!(parts.len() >= 6);
+    assert!(buf.len() >= MAX_SIG_DIGITS);
+    assert!(dec_bounds.0 <= dec_bounds.1);
+
+    let (negative, full_decoded) = decode(v);
+    let sign = determine_sign(sign, &full_decoded, negative);
+    match full_decoded {
+        FullDecoded::Nan => {
+            parts[0] = Part::Copy(b"NaN");
+            Formatted { sign: sign, parts: &parts[..1] }
+        }
+        FullDecoded::Infinite => {
+            parts[0] = Part::Copy(b"inf");
+            Formatted { sign: sign, parts: &parts[..1] }
+        }
+        FullDecoded::Zero => {
+            parts[0] = if dec_bounds.0 <= 0 && 0 < dec_bounds.1 {
+                Part::Copy(b"0")
+            } else {
+                Part::Copy(if upper { b"0E0" } else { b"0e0" })
+            };
+            Formatted { sign: sign, parts: &parts[..1] }
+        }
+        FullDecoded::Finite(ref decoded) => {
+            let (len, exp) = format_shortest(decoded, buf);
+            let vis_exp = exp as i32 - 1;
+            let parts = if dec_bounds.0 as i32 <= vis_exp && vis_exp < dec_bounds.1 as i32 {
+                digits_to_dec_str(&buf[..len], exp, 0, parts)
+            } else {
+                digits_to_exp_str(&buf[..len], exp, 0, upper, parts)
+            };
+            Formatted { sign: sign, parts: parts }
+        }
+    }
+}
+
+/// Returns rather crude approximation (upper bound) for the maximum buffer size
+/// calculated from the given decoded exponent.
+///
+/// The exact limit is:
+///
+/// - when `exp < 0`, the maximum length is `ceil(log_10 (5^-exp * (2^64 - 1)))`.
+/// - when `exp >= 0`, the maximum length is `ceil(log_10 (2^exp * (2^64 - 1)))`.
+///
+/// `ceil(log_10 (x^exp * (2^64 - 1)))` is less than `ceil(log_10 (2^64 - 1)) +
+/// ceil(exp * log_10 x)`, which is in turn less than `20 + (1 + exp * log_10 x)`.
+/// We use the facts that `log_10 2 < 5/16` and `log_10 5 < 12/16`, which is
+/// enough for our purposes.
+///
+/// Why do we need this? `format_exact` functions will fill the entire buffer
+/// unless limited by the last digit restriction, but it is possible that
+/// the number of digits requested is ridiculously large (say, 30,000 digits).
+/// The vast majority of buffer will be filled with zeroes, so we don't want to
+/// allocate all the buffer beforehand. Consequently, for any given arguments,
+/// 826 bytes of buffer should be sufficient for `f64`. Compare this with
+/// the actual number for the worst case: 770 bytes (when `exp = -1074`).
+fn estimate_max_buf_len(exp: i16) -> usize {
+    21 + ((if exp < 0 { -12 } else { 5 } * exp as i32) as usize >> 4)
+}
+
+/// Formats given floating point number into the exponential form with
+/// exactly given number of significant digits. The result is stored to
+/// the supplied parts array while utilizing given byte buffer as a scratch.
+/// `upper` is used to determine the case of the exponent prefix (`e` or `E`).
+/// The first part to be rendered is always a `Part::Sign` (which can be
+/// an empty string if no sign is rendered).
+///
+/// `format_exact` should be the underlying digit-generation function.
+/// You probably would want `strategy::grisu::format_exact` for this.
+///
+/// The byte buffer should be at least `ndigits` bytes long unless `ndigits` is
+/// so large that only the fixed number of digits will be ever written.
+/// (The tipping point for `f64` is about 800, so 1000 bytes should be enough.)
+/// There should be at least 7 parts available, due to the worst case like
+/// `[+][1][.][2345][e][-][67]`.
+pub fn to_exact_exp_str<'a, T, F>(mut format_exact: F, v: T,
+                                  sign: Sign, ndigits: usize, upper: bool,
+                                  buf: &'a mut [u8], parts: &'a mut [Part<'a>]) -> Formatted<'a>
+        where T: DecodableFloat, F: FnMut(&Decoded, &mut [u8], i16) -> (usize, i16) {
+    assert!(parts.len() >= 6);
+    assert!(ndigits > 0);
+
+    let (negative, full_decoded) = decode(v);
+    let sign = determine_sign(sign, &full_decoded, negative);
+    match full_decoded {
+        FullDecoded::Nan => {
+            parts[0] = Part::Copy(b"NaN");
+            Formatted { sign: sign, parts: &parts[..1] }
+        }
+        FullDecoded::Infinite => {
+            parts[0] = Part::Copy(b"inf");
+            Formatted { sign: sign, parts: &parts[..1] }
+        }
+        FullDecoded::Zero => {
+            if ndigits > 1 { // [0.][0000][e0]
+                parts[0] = Part::Copy(b"0.");
+                parts[1] = Part::Zero(ndigits - 1);
+                parts[2] = Part::Copy(if upper { b"E0" } else { b"e0" });
+                Formatted { sign: sign, parts: &parts[..3] }
+            } else {
+                parts[0] = Part::Copy(if upper { b"0E0" } else { b"0e0" });
+                Formatted { sign: sign, parts: &parts[..1] }
+            }
+        }
+        FullDecoded::Finite(ref decoded) => {
+            let maxlen = estimate_max_buf_len(decoded.exp);
+            assert!(buf.len() >= ndigits || buf.len() >= maxlen);
+
+            let trunc = if ndigits < maxlen { ndigits } else { maxlen };
+            let (len, exp) = format_exact(decoded, &mut buf[..trunc], i16::MIN);
+            Formatted { sign: sign,
+                        parts: digits_to_exp_str(&buf[..len], exp, ndigits, upper, parts) }
+        }
+    }
+}
+
+/// Formats given floating point number into the decimal form with exactly
+/// given number of fractional digits. The result is stored to the supplied parts
+/// array while utilizing given byte buffer as a scratch. `upper` is currently
+/// unused but left for the future decision to change the case of non-finite values,
+/// i.e. `inf` and `nan`. The first part to be rendered is always a `Part::Sign`
+/// (which can be an empty string if no sign is rendered).
+///
+/// `format_exact` should be the underlying digit-generation function.
+/// You probably would want `strategy::grisu::format_exact` for this.
+///
+/// The byte buffer should be enough for the output unless `frac_digits` is
+/// so large that only the fixed number of digits will be ever written.
+/// (The tipping point for `f64` is about 800, and 1000 bytes should be enough.)
+/// There should be at least 5 parts available, due to the worst case like
+/// `[+][0.][0000][45][0000]` with `frac_digits = 10`.
+pub fn to_exact_fixed_str<'a, T, F>(mut format_exact: F, v: T,
+                                    sign: Sign, frac_digits: usize, _upper: bool,
+                                    buf: &'a mut [u8], parts: &'a mut [Part<'a>]) -> Formatted<'a>
+        where T: DecodableFloat, F: FnMut(&Decoded, &mut [u8], i16) -> (usize, i16) {
+    assert!(parts.len() >= 4);
+
+    let (negative, full_decoded) = decode(v);
+    let sign = determine_sign(sign, &full_decoded, negative);
+    match full_decoded {
+        FullDecoded::Nan => {
+            parts[0] = Part::Copy(b"NaN");
+            Formatted { sign: sign, parts: &parts[..1] }
+        }
+        FullDecoded::Infinite => {
+            parts[0] = Part::Copy(b"inf");
+            Formatted { sign: sign, parts: &parts[..1] }
+        }
+        FullDecoded::Zero => {
+            if frac_digits > 0 { // [0.][0000]
+                parts[0] = Part::Copy(b"0.");
+                parts[1] = Part::Zero(frac_digits);
+                Formatted { sign: sign, parts: &parts[..2] }
+            } else {
+                parts[0] = Part::Copy(b"0");
+                Formatted { sign: sign, parts: &parts[..1] }
+            }
+        }
+        FullDecoded::Finite(ref decoded) => {
+            let maxlen = estimate_max_buf_len(decoded.exp);
+            assert!(buf.len() >= maxlen);
+
+            // it *is* possible that `frac_digits` is ridiculously large.
+            // `format_exact` will end rendering digits much earlier in this case,
+            // because we are strictly limited by `maxlen`.
+            let limit = if frac_digits < 0x8000 { -(frac_digits as i16) } else { i16::MIN };
+            let (len, exp) = format_exact(decoded, &mut buf[..maxlen], limit);
+            if exp <= limit {
+                // the restriction couldn't been met, so this should render like zero no matter
+                // `exp` was. this does not include the case that the restriction has been met
+                // only after the final rounding-up; it's a regular case with `exp = limit + 1`.
+                debug_assert_eq!(len, 0);
+                if frac_digits > 0 { // [0.][0000]
+                    parts[0] = Part::Copy(b"0.");
+                    parts[1] = Part::Zero(frac_digits);
+                    Formatted { sign: sign, parts: &parts[..2] }
+                } else {
+                    parts[0] = Part::Copy(b"0");
+                    Formatted { sign: sign, parts: &parts[..1] }
+                }
+            } else {
+                Formatted { sign: sign,
+                            parts: digits_to_dec_str(&buf[..len], exp, frac_digits, parts) }
+            }
+        }
+    }
+}
+