// FUNCTION from_chars (STRING TO FLOATING-POINT)

// C11 6.4.2.1 "General"
// digit: one of
//     0 1 2 3 4 5 6 7 8 9

// C11 6.4.4.1 "Integer constants"
// hexadecimal-digit: one of
//     0 1 2 3 4 5 6 7 8 9 a b c d e f A B C D E F

// C11 6.4.4.2 "Floating constants" (without floating-suffix, hexadecimal-prefix)
// amended by C11 7.22.1.3 "The strtod, strtof, and strtold functions" making exponents optional
// LWG-3080: "the sign '+' may only appear in the exponent part"

// digit-sequence:
//     digit
//     digit-sequence digit

// hexadecimal-digit-sequence:
//     hexadecimal-digit
//     hexadecimal-digit-sequence hexadecimal-digit

// sign: one of
//     + -

// decimal-floating-constant:
//     fractional-constant exponent-part[opt]
//     digit-sequence exponent-part[opt]

// fractional-constant:
//     digit-sequence[opt] . digit-sequence
//     digit-sequence .

// exponent-part:
//     e sign[opt] digit-sequence
//     E sign[opt] digit-sequence

// hexadecimal-floating-constant:
//     hexadecimal-fractional-constant binary-exponent-part[opt]
//     hexadecimal-digit-sequence binary-exponent-part[opt]

// hexadecimal-fractional-constant:
//     hexadecimal-digit-sequence[opt] . hexadecimal-digit-sequence
//     hexadecimal-digit-sequence .

// binary-exponent-part:
//     p sign[opt] digit-sequence
//     P sign[opt] digit-sequence

template <class _Floating>
_NODISCARD from_chars_result _Ordinary_floating_from_chars(const char* const _First, const char* const _Last,
    _Floating& _Value, const chars_format _Fmt, const bool _Minus_sign, const char* _Next) noexcept {
    // vvvvvvvvvv DERIVED FROM corecrt_internal_strtox.h WITH SIGNIFICANT MODIFICATIONS vvvvvvvvvv

    const bool _Is_hexadecimal = _Fmt == chars_format::hex;
    const int _Base{_Is_hexadecimal ? 16 : 10};

    // PERFORMANCE NOTE: _Fp_string is intentionally left uninitialized. Zero-initialization is quite expensive
    // and is unnecessary. The benefit of not zero-initializing is greatest for short inputs.
    _Floating_point_string _Fp_string;

    // Record the optional minus sign:
    _Fp_string._Myis_negative = _Minus_sign;

    uint8_t* const _Mantissa_first = _Fp_string._Mymantissa;
    uint8_t* const _Mantissa_last  = _STD end(_Fp_string._Mymantissa);
    uint8_t* _Mantissa_it          = _Mantissa_first;

    // [_Whole_begin, _Whole_end) will contain 0 or more digits/hexits
    const char* const _Whole_begin = _Next;

    // Skip past any leading zeroes in the mantissa:
    for (; _Next != _Last && *_Next == '0'; ++_Next) {
    }
    const char* const _Leading_zero_end = _Next;

    // Scan the integer part of the mantissa:
    for (; _Next != _Last; ++_Next) {
        const unsigned char _Digit_value = _Digit_from_char(*_Next);

        if (_Digit_value >= _Base) {
            break;
        }

        if (_Mantissa_it != _Mantissa_last) {
            *_Mantissa_it++ = _Digit_value;
        }
    }
    const char* const _Whole_end = _Next;

    // Defend against _Exponent_adjustment integer overflow. (These values don't need to be strict.)
    constexpr ptrdiff_t _Maximum_adjustment = 1'000'000;
    constexpr ptrdiff_t _Minimum_adjustment = -1'000'000;

    // The exponent adjustment holds the number of digits in the mantissa buffer that appeared before the radix point.
    // It can be negative, and leading zeroes in the integer part are ignored. Examples:
    // For "03333.111", it is 4.
    // For "00000.111", it is 0.
    // For "00000.001", it is -2.
    int _Exponent_adjustment = static_cast<int>((_STD min)(_Whole_end - _Leading_zero_end, _Maximum_adjustment));

    // [_Whole_end, _Dot_end) will contain 0 or 1 '.' characters
    if (_Next != _Last && *_Next == '.') {
        ++_Next;
    }
    const char* const _Dot_end = _Next;

    // [_Dot_end, _Frac_end) will contain 0 or more digits/hexits

    // If we haven't yet scanned any nonzero digits, continue skipping over zeroes,
    // updating the exponent adjustment to account for the zeroes we are skipping:
    if (_Exponent_adjustment == 0) {
        for (; _Next != _Last && *_Next == '0'; ++_Next) {
        }

        _Exponent_adjustment = static_cast<int>((_STD max)(_Dot_end - _Next, _Minimum_adjustment));
    }

    // Scan the fractional part of the mantissa:
    bool _Has_zero_tail = true;

    for (; _Next != _Last; ++_Next) {
        const unsigned char _Digit_value = _Digit_from_char(*_Next);

        if (_Digit_value >= _Base) {
            break;
        }

        if (_Mantissa_it != _Mantissa_last) {
            *_Mantissa_it++ = _Digit_value;
        } else {
            _Has_zero_tail = _Has_zero_tail && _Digit_value == 0;
        }
    }
    const char* const _Frac_end = _Next;

    // We must have at least 1 digit/hexit
    if (_Whole_begin == _Whole_end && _Dot_end == _Frac_end) {
        return {_First, errc::invalid_argument};
    }

    const char _Exponent_prefix{_Is_hexadecimal ? 'p' : 'e'};

    bool _Exponent_is_negative = false;
    int _Exponent              = 0;

    constexpr int _Maximum_temporary_decimal_exponent = 5200;
    constexpr int _Minimum_temporary_decimal_exponent = -5200;

    if (_Fmt != chars_format::fixed // N4713 23.20.3 [charconv.from.chars]/7.3
                                    // "if fmt has chars_format::fixed set but not chars_format::scientific,
                                    // the optional exponent part shall not appear"
        && _Next != _Last && (static_cast<unsigned char>(*_Next) | 0x20) == _Exponent_prefix) { // found exponent prefix
        const char* _Unread = _Next + 1;

        if (_Unread != _Last && (*_Unread == '+' || *_Unread == '-')) { // found optional sign
            _Exponent_is_negative = *_Unread == '-';
            ++_Unread;
        }

        while (_Unread != _Last) {
            const unsigned char _Digit_value = _Digit_from_char(*_Unread);

            if (_Digit_value >= 10) {
                break;
            }

            // found decimal digit

            if (_Exponent <= _Maximum_temporary_decimal_exponent) {
                _Exponent = _Exponent * 10 + _Digit_value;
            }

            ++_Unread;
            _Next = _Unread; // consume exponent-part/binary-exponent-part
        }

        if (_Exponent_is_negative) {
            _Exponent = -_Exponent;
        }
    }

    // [_Frac_end, _Exponent_end) will either be empty or contain "[EPep] sign[opt] digit-sequence"
    const char* const _Exponent_end = _Next;

    if (_Fmt == chars_format::scientific
        && _Frac_end == _Exponent_end) { // N4713 23.20.3 [charconv.from.chars]/7.2
                                         // "if fmt has chars_format::scientific set but not chars_format::fixed,
                                         // the otherwise optional exponent part shall appear"
        return {_First, errc::invalid_argument};
    }

    // Remove trailing zeroes from mantissa:
    while (_Mantissa_it != _Mantissa_first && *(_Mantissa_it - 1) == 0) {
        --_Mantissa_it;
    }

    // If the mantissa buffer is empty, the mantissa was composed of all zeroes (so the mantissa is 0).
    // All such strings have the value zero, regardless of what the exponent is (because 0 * b^n == 0 for all b and n).
    // We can return now. Note that we defer this check until after we scan the exponent, so that we can correctly
    // update _Next to point past the end of the exponent.
    if (_Mantissa_it == _Mantissa_first) {
        _STL_INTERNAL_CHECK(_Has_zero_tail);
        _Assemble_floating_point_zero(_Fp_string._Myis_negative, _Value);
        return {_Next, errc{}};
    }

    // Before we adjust the exponent, handle the case where we detected a wildly
    // out of range exponent during parsing and clamped the value:
    if (_Exponent > _Maximum_temporary_decimal_exponent) {
        _Assemble_floating_point_infinity(_Fp_string._Myis_negative, _Value);
        return {_Next, errc::result_out_of_range}; // Overflow example: "1e+9999"
    }

    if (_Exponent < _Minimum_temporary_decimal_exponent) {
        _Assemble_floating_point_zero(_Fp_string._Myis_negative, _Value);
        return {_Next, errc::result_out_of_range}; // Underflow example: "1e-9999"
    }

    // In hexadecimal floating constants, the exponent is a base 2 exponent. The exponent adjustment computed during
    // parsing has the same base as the mantissa (so, 16 for hexadecimal floating constants).
    // We therefore need to scale the base 16 multiplier to base 2 by multiplying by log2(16):
    const int _Exponent_adjustment_multiplier{_Is_hexadecimal ? 4 : 1};

    _Exponent += _Exponent_adjustment * _Exponent_adjustment_multiplier;

    // Verify that after adjustment the exponent isn't wildly out of range (if it is, it isn't representable
    // in any supported floating-point format).
    if (_Exponent > _Maximum_temporary_decimal_exponent) {
        _Assemble_floating_point_infinity(_Fp_string._Myis_negative, _Value);
        return {_Next, errc::result_out_of_range}; // Overflow example: "10e+5199"
    }

    if (_Exponent < _Minimum_temporary_decimal_exponent) {
        _Assemble_floating_point_zero(_Fp_string._Myis_negative, _Value);
        return {_Next, errc::result_out_of_range}; // Underflow example: "0.001e-5199"
    }

    _Fp_string._Myexponent       = _Exponent;
    _Fp_string._Mymantissa_count = static_cast<uint32_t>(_Mantissa_it - _Mantissa_first);

    if (_Is_hexadecimal) {
        const errc _Ec = _Convert_hexadecimal_string_to_floating_type(_Fp_string, _Value, _Has_zero_tail);
        return {_Next, _Ec};
    } else {
        const errc _Ec = _Convert_decimal_string_to_floating_type(_Fp_string, _Value, _Has_zero_tail);
        return {_Next, _Ec};
    }

    // ^^^^^^^^^^ DERIVED FROM corecrt_internal_strtox.h WITH SIGNIFICANT MODIFICATIONS ^^^^^^^^^^
}

_NODISCARD inline bool _Starts_with_case_insensitive(
    const char* _First, const char* const _Last, const char* _Lowercase) noexcept {
    // pre: _Lowercase contains only ['a', 'z'] and is null-terminated
    for (; _First != _Last && *_Lowercase != '\0'; ++_First, ++_Lowercase) {
        if ((static_cast<unsigned char>(*_First) | 0x20) != *_Lowercase) {
            return false;
        }
    }

    return *_Lowercase == '\0';
}

template <class _Floating>
_NODISCARD from_chars_result _Infinity_from_chars(const char* const _First, const char* const _Last, _Floating& _Value,
    const bool _Minus_sign, const char* _Next) noexcept {
    // pre: _Next points at 'i' (case-insensitively)
    if (!_Starts_with_case_insensitive(_Next + 1, _Last, "nf")) { // definitely invalid
        return {_First, errc::invalid_argument};
    }

    // definitely inf
    _Next += 3;

    if (_Starts_with_case_insensitive(_Next, _Last, "inity")) { // definitely infinity
        _Next += 5;
    }

    _Assemble_floating_point_infinity(_Minus_sign, _Value);

    return {_Next, errc{}};
}

template <class _Floating>
_NODISCARD from_chars_result _Nan_from_chars(const char* const _First, const char* const _Last, _Floating& _Value,
    bool _Minus_sign, const char* _Next) noexcept {
    // pre: _Next points at 'n' (case-insensitively)
    if (!_Starts_with_case_insensitive(_Next + 1, _Last, "an")) { // definitely invalid
        return {_First, errc::invalid_argument};
    }

    // definitely nan
    _Next += 3;

    bool _Quiet = true;

    if (_Next != _Last && *_Next == '(') { // possibly nan(n-char-sequence[opt])
        const char* const _Seq_begin = _Next + 1;

        for (const char* _Temp = _Seq_begin; _Temp != _Last; ++_Temp) {
            if (*_Temp == ')') { // definitely nan(n-char-sequence[opt])
                _Next = _Temp + 1;

                if (_Temp - _Seq_begin == 3
                    && _Starts_with_case_insensitive(_Seq_begin, _Temp, "ind")) { // definitely nan(ind)
                    // The UCRT considers indeterminate NaN to be negative quiet NaN with no payload bits set.
                    // It parses "nan(ind)" and "-nan(ind)" identically.
                    _Minus_sign = true;
                } else if (_Temp - _Seq_begin == 4
                           && _Starts_with_case_insensitive(_Seq_begin, _Temp, "snan")) { // definitely nan(snan)
                    _Quiet = false;
                }

                break;
            } else if (*_Temp == '_' || ('0' <= *_Temp && *_Temp <= '9') || ('A' <= *_Temp && *_Temp <= 'Z')
                       || ('a' <= *_Temp && *_Temp <= 'z')) { // possibly nan(n-char-sequence[opt]), keep going
            } else { // definitely nan, not nan(n-char-sequence[opt])
                break;
            }
        }
    }

    // Intentional behavior difference between the UCRT and the STL:
    // strtod()/strtof() parse plain "nan" as being a quiet NaN with all payload bits set.
    // numeric_limits::quiet_NaN() returns a quiet NaN with no payload bits set.
    // This implementation of from_chars() has chosen to be consistent with numeric_limits.

    using _Traits    = _Floating_type_traits<_Floating>;
    using _Uint_type = typename _Traits::_Uint_type;

    _Uint_type _Uint_value = _Traits::_Shifted_exponent_mask;

    if (_Minus_sign) {
        _Uint_value |= _Traits::_Shifted_sign_mask;
    }

    if (_Quiet) {
        _Uint_value |= _Traits::_Special_nan_mantissa_mask;
    } else {
        _Uint_value |= 1;
    }

    _Value = _Bit_cast<_Floating>(_Uint_value);

    return {_Next, errc{}};
}

template <class _Floating>
_NODISCARD from_chars_result _Floating_from_chars(
    const char* const _First, const char* const _Last, _Floating& _Value, const chars_format _Fmt) noexcept {
    _Adl_verify_range(_First, _Last);

    _STL_ASSERT(_Fmt == chars_format::general || _Fmt == chars_format::scientific || _Fmt == chars_format::fixed
                    || _Fmt == chars_format::hex,
        "invalid format in from_chars()");

    bool _Minus_sign = false;

    const char* _Next = _First;

    if (_Next == _Last) {
        return {_First, errc::invalid_argument};
    }

    if (*_Next == '-') {
        _Minus_sign = true;
        ++_Next;

        if (_Next == _Last) {
            return {_First, errc::invalid_argument};
        }
    }

    // Distinguish ordinary numbers versus inf/nan with a single test.
    // ordinary numbers start with ['.'] ['0', '9'] ['A', 'F'] ['a', 'f']
    // inf/nan start with ['I'] ['N'] ['i'] ['n']
    // All other starting characters are invalid.
    // Setting the 0x20 bit folds these ranges in a useful manner.
    // ordinary (and some invalid) starting characters are folded to ['.'] ['0', '9'] ['a', 'f']
    // inf/nan starting characters are folded to ['i'] ['n']
    // These are ordered: ['.'] ['0', '9'] ['a', 'f'] < ['i'] ['n']
    // Note that invalid starting characters end up on both sides of this test.
    const unsigned char _Folded_start = static_cast<unsigned char>(static_cast<unsigned char>(*_Next) | 0x20);

    if (_Folded_start <= 'f') { // possibly an ordinary number
        return _Ordinary_floating_from_chars(_First, _Last, _Value, _Fmt, _Minus_sign, _Next);
    } else if (_Folded_start == 'i') { // possibly inf
        return _Infinity_from_chars(_First, _Last, _Value, _Minus_sign, _Next);
    } else if (_Folded_start == 'n') { // possibly nan
        return _Nan_from_chars(_First, _Last, _Value, _Minus_sign, _Next);
    } else { // definitely invalid
        return {_First, errc::invalid_argument};
    }
}