parse.gr

// This module was based on Rust's dec2flt
// https://github.com/rust-lang/rust/blob/1cbc45942d5c0f6eb5d94e3b10762ba541958035/library/core/src/num/dec2flt/parse.rs
// Rust's MIT license is provided below:
/*
 * Permission is hereby granted, free of charge, to any
 * person obtaining a copy of this software and associated
 * documentation files (the "Software"), to deal in the
 * Software without restriction, including without
 * limitation the rights to use, copy, modify, merge,
 * publish, distribute, sublicense, and/or sell copies of
 * the Software, and to permit persons to whom the Software
 * is furnished to do so, subject to the following
 * conditions:
 *
 * The above copyright notice and this permission notice
 * shall be included in all copies or substantial portions
 * of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
 * ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
 * TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
 * PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
 * SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
 * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
*/
module Parse

from "runtime/unsafe/wasmi32" include WasmI32
from "runtime/unsafe/wasmi64" include WasmI64
from "runtime/unsafe/wasmf64" include WasmF64
from "runtime/dataStructures" include DataStructures
use DataStructures.{ newInt32, newInt64, newFloat64 }

from "runtime/atof/common" include Common
use Common.{
  _CHAR_CODE_UNDERSCORE,
  _CHAR_CODE_PLUS,
  _CHAR_CODE_MINUS,
  _CHAR_CODE_DOT,
  _CHAR_CODE_0,
  _CHAR_CODE_E,
  _CHAR_CODE_e,
  _CHAR_CODE_A,
  _CHAR_CODE_Z,
  _CHAR_CODE_a,
  _CHAR_CODE_f,
  _CHAR_CODE_i,
  _CHAR_CODE_n,
  _CHAR_CODE_t,
  _CHAR_CODE_y,
  _MIN_EXPONENT_FAST_PATH,
  _MAX_EXPONENT_DISGUISED_FAST_PATH,
  _MAX_EXPONENT_FAST_PATH,
  _MAX_MANTISSA_FAST_PATH,
  is8Digits,
  getPowers10,
  getPowers10FastPath,
  biasedFpToNumber,
  fpNan,
  fpInf,
}

from "runtime/atof/lemire" include Lemire
use Lemire.{ computeFloat }
from "runtime/atof/slow" include Slow
use Slow.{ parseLongMantissa }

// Try to parse 8 digits at a time:
// https://johnnylee-sde.github.io/Fast-numeric-string-to-int/
@unsafe
let parse8Digits = (digits: WasmI64) => {
  use WasmI64.{ (+), (-), (*), (>>>), (&), (|), (==) }

  let _MASK = 0x0000_00FF_0000_00FFN

  let a = digits - 0x3030_3030_3030_3030N
  let b = a * 10N + (a >>> 8N)
  let c = (b & _MASK) * 0x000F_4240_0000_0064N
  let d = (b >>> 16N & _MASK) * 0x0000_2710_0000_0001N

  (c + d) >>> 32N
}

@unsafe
let parseScientificExponent = (ptr: WasmI32, offset: WasmI32, len: WasmI32) => {
  use WasmI32.{ (+), (-), (*), geU as (>=), ltU as (<), (==), (!=) }

  let mut offset = offset
  let mut exponent = 0n
  let mut negative = false

  // Parse the optional leading sign
  match (WasmI32.load8U(ptr, offset)) {
    fst when fst == _CHAR_CODE_PLUS => {
      offset += 1n
      negative = false
    },
    fst when fst == _CHAR_CODE_MINUS => {
      offset += 1n
      negative = true
    },
    _ => void,
  }

  if (offset >= len) {
    Err("Invalid exponent")
  } else {
    // Parse digits '0'-'9' until we hit a non-digit byte or reach the end of the string
    while (offset < len) {
      let char = WasmI32.load8U(ptr, offset)
      let digit = char - 0x30n
      if (digit >= 0n && digit < 10n) {
        use WasmI32.{ (<) }
        if (exponent < 0x10000n) {
          exponent = digit + 10n * exponent
        }
        offset += 1n
      } else if (char == _CHAR_CODE_UNDERSCORE) {
        offset += 1n
      } else {
        break
      }
    }
    if (offset != len) {
      Err("Invalid exponent")
    } else if (negative) {
      Ok(WasmI32.toGrain(newInt32(0n - exponent)): Int32)
    } else {
      Ok(WasmI32.toGrain(newInt32(exponent)): Int32)
    }
  }
}

@unsafe
let parseFloatToParts = (string: String) => {
  use WasmI32.{ (+), (-), gtU as (>), geU as (>=), ltU as (<), (==), (!=) }
  use WasmI64.{ (+) as addWasmI64, (*) }

  let ptr = WasmI32.fromGrain(string)
  match (WasmI32.load(ptr, 4n)) {
    // Invalid string
    0n => Err("Invalid string"),
    // Continue to parse the string
    len => {
      let ptr = ptr + 8n

      let mut i = 0n
      let mut mantissa = 0N
      let mut exponent = 0n
      let mut numDigits = 0n
      let mut numDigitsAfterDot = 0n
      let mut manyDigits = false

      // Parse the optional leading sign
      let mut negative = false
      match (WasmI32.load8U(ptr, i)) {
        fst when fst == _CHAR_CODE_PLUS => {
          i += 1n
          negative = false
        },
        fst when fst == _CHAR_CODE_MINUS => {
          i += 1n
          negative = true
        },
        _ => void,
      }

      // Parse digits '0'-'9' until we hit a non-digit byte or reach the end of the string
      while (i < len) {
        let char = WasmI32.load8U(ptr, i)
        let digit = char - _CHAR_CODE_0
        if (digit >= 0n && digit < 10n) {
          mantissa = addWasmI64(mantissa * 10N, WasmI64.extendI32U(digit))
          numDigits += 1n
          i += 1n
        } else if (char == _CHAR_CODE_UNDERSCORE) {
          i += 1n
        } else {
          break
        }
      }

      let digitsBeforeDecimal = numDigits

      // Handle the dot
      match (WasmI32.load8U(ptr, i)) {
        c when c == _CHAR_CODE_DOT => {
          i += 1n
          let dotStartIndex = i
          // Parse chunks of 8 digits
          while (WasmI32.leU(i + 8n, len)) {
            let digits = WasmI64.load(ptr, i)
            if (is8Digits(digits)) {
              mantissa = addWasmI64(parse8Digits(digits), mantissa * 100000000N)
              i += 8n
              numDigitsAfterDot += 8n
            } else {
              break
            }
          }
          // Parse digits '0'-'9' until we hit a non-digit byte or reach the end of the string
          while (i < len) {
            let char = WasmI32.load8U(ptr, i)
            let digit = char - _CHAR_CODE_0
            if (digit >= 0n && digit < 10n) {
              mantissa = addWasmI64(WasmI64.extendI32U(digit), mantissa * 10N)
              i += 1n
              numDigitsAfterDot += 1n
            } else if (char == _CHAR_CODE_UNDERSCORE) {
              i += 1n
            } else {
              break
            }
          }
          exponent = 0n - numDigitsAfterDot
        },
        _ => void,
      }

      numDigits += numDigitsAfterDot

      match (numDigits) {
        0n => Err("Invalid float"),
        _ => {
          let _MAX_MANTISSA_DIGITS = 19n // 10^19 fits in uint64
          let _MIN_19DIGIT_INT = 100_0000_0000_0000_0000N

          // Parse scientific notation
          let exponentResult = match (WasmI32.load8U(ptr, i)) {
            c when c == _CHAR_CODE_E || c == _CHAR_CODE_e => {
              i += 1n
              parseScientificExponent(ptr, i, len)
            },
            _ => {
              if (i != len) {
                Err("Invalid float")
              } else {
                Ok(0l)
              }
            },
          }

          match (exponentResult) {
            Ok(exponentNumber) => {
              let exponentNumber = WasmI32.load(
                WasmI32.fromGrain(exponentNumber),
                4n
              )
              exponent += exponentNumber

              // Check to see if we need to truncate
              if (numDigits > _MAX_MANTISSA_DIGITS) {
                manyDigits = false
                numDigits -= _MAX_MANTISSA_DIGITS
                let mut i = 0n
                while (i < len) {
                  let c = WasmI32.load8U(ptr, i)
                  if (c == _CHAR_CODE_DOT || c == _CHAR_CODE_0) {
                    use WasmI32.{ (<), (>) }
                    let n = c - (_CHAR_CODE_0 - 1n)
                    numDigits -= if (n < 0n) {
                      0n
                    } else if (n > 255n) {
                      255n
                    } else {
                      n
                    }
                    i += 1n
                  } else if (c == _CHAR_CODE_UNDERSCORE) {
                    continue
                  } else {
                    break
                  }
                }

                // Attempt to parse 19 digits, the most that can fit in an i64
                let mut digitsParsed = 0n
                use WasmI32.{ (>) }
                if (numDigits > 0n) {
                  manyDigits = true
                  mantissa = 0N

                  let mut i = 0n
                  while (WasmI64.ltU(mantissa, _MIN_19DIGIT_INT)) {
                    if (i < len) {
                      let char = WasmI32.load8U(ptr, i)
                      let digit = char - _CHAR_CODE_0
                      if (digit >= 0n && digit < 10n) {
                        mantissa = addWasmI64(
                          mantissa * 10N,
                          WasmI64.extendI32U(digit)
                        )
                        i += 1n
                        digitsParsed += 1n
                      } else if (char == _CHAR_CODE_UNDERSCORE) {
                        i += 1n
                      } else {
                        break
                      }
                    } else {
                      break
                    }
                  }

                  exponent = if (WasmI64.geU(mantissa, _MIN_19DIGIT_INT)) {
                    digitsBeforeDecimal - digitsParsed
                  } else {
                    // From Rust: https://github.com/rust-lang/rust/blob/e960b5e7749e95c6a6b2fdec7250a48105664efb/library/core/src/num/dec2flt/parse.rs#L179
                    // the next byte must be present and be '.'
                    // We know this is true because we had more than 19
                    // digits previously, so we overflowed a 64-bit integer,
                    // but parsing only the integral digits produced less
                    // than 19 digits. That means we must have a decimal
                    // point, and at least 1 fractional digit.
                    i += 1n
                    let mut fractionalDigitsParsed = 0n
                    while (WasmI64.ltU(mantissa, _MIN_19DIGIT_INT)) {
                      if (i < len) {
                        let char = WasmI32.load8U(ptr, i)
                        let digit = char - _CHAR_CODE_0
                        if (digit < 10n) {
                          mantissa = addWasmI64(
                            mantissa * 10N,
                            WasmI64.extendI32U(digit)
                          )
                          i += 1n
                          fractionalDigitsParsed += 1n
                        } else if (char == _CHAR_CODE_UNDERSCORE) {
                          i += 1n
                        } else {
                          break
                        }
                      } else {
                        break
                      }
                    }
                    0n - fractionalDigitsParsed
                  }
                  // Add back the explicit part
                  exponent += exponentNumber
                }
                Ok(
                  (
                    WasmI32.toGrain(newInt32(exponent)): Int32,
                    WasmI32.toGrain(newInt64(mantissa)): Int64,
                    negative,
                    manyDigits,
                  ),
                )
              } else {
                Ok(
                  (
                    WasmI32.toGrain(newInt32(exponent)): Int32,
                    WasmI32.toGrain(newInt64(mantissa)): Int64,
                    negative,
                    manyDigits,
                  ),
                )
              }
            },
            Err(err) => Err(err),
          }
        },
      }
    },
  }
}

@unsafe
let parseInfNan = s => {
  use WasmI32.{ (+), (-), (<), (>=), (<=), (==) }

  let ptr = WasmI32.fromGrain(s)
  match (WasmI32.load(ptr, 4n)) {
    // Invalid string
    0n => Err("Invalid string"),
    // Continue to parse
    len => {
      let ptr = ptr + 8n

      let mut i = 0n
      let mut mantissa = 0N
      let mut exponent = 0n
      let mut numDigits = 0n
      let mut numDigitsAfterDot = 0n
      let mut manyDigits = false

      // Parse the optional leading sign
      let mut negative = false
      match (WasmI32.load8U(ptr, i)) {
        fst when fst == _CHAR_CODE_PLUS => {
          i += 1n
          negative = false
        },
        fst when fst == _CHAR_CODE_MINUS => {
          i += 1n
          negative = true
        },
        _ => void,
      }

      if (len - i < 3n) {
        Err("Invalid string")
      } else {
        let mut c1 = WasmI32.load8U(ptr + i, 0n)
        if (c1 >= _CHAR_CODE_A && c1 <= _CHAR_CODE_Z) {
          c1 += 0x20n
        }
        let mut c2 = WasmI32.load8U(ptr + i, 1n)
        if (c2 >= _CHAR_CODE_A && c2 <= _CHAR_CODE_Z) {
          c2 += 0x20n
        }
        let mut c3 = WasmI32.load8U(ptr + i, 2n)
        if (c3 >= _CHAR_CODE_A && c3 <= _CHAR_CODE_Z) {
          c3 += 0x20n
        }

        if (
          len - i == 3n &&
          c1 == _CHAR_CODE_n &&
          c2 == _CHAR_CODE_a &&
          c3 == _CHAR_CODE_n
        ) {
          Ok((fpNan(), negative))
        } else if (
          c1 == _CHAR_CODE_i &&
          c2 == _CHAR_CODE_n &&
          c3 == _CHAR_CODE_f
        ) {
          if (len - i == 3n) {
            Ok((fpInf(), negative))
          } else if (len - i == 8n) {
            let mut c4 = WasmI32.load8U(ptr + i, 3n)
            if (c4 >= _CHAR_CODE_A && c4 <= _CHAR_CODE_Z) {
              c4 += 0x20n
            }
            let mut c5 = WasmI32.load8U(ptr + i, 4n)
            if (c5 >= _CHAR_CODE_A && c5 <= _CHAR_CODE_Z) {
              c5 += 0x20n
            }
            let mut c6 = WasmI32.load8U(ptr + i, 5n)
            if (c6 >= _CHAR_CODE_A && c6 <= _CHAR_CODE_Z) {
              c6 += 0x20n
            }
            let mut c7 = WasmI32.load8U(ptr + i, 6n)
            if (c7 >= _CHAR_CODE_A && c7 <= _CHAR_CODE_Z) {
              c7 += 0x20n
            }
            let mut c8 = WasmI32.load8U(ptr + i, 7n)
            if (c8 >= _CHAR_CODE_A && c8 <= _CHAR_CODE_Z) {
              c8 += 0x20n
            }

            if (
              c4 == _CHAR_CODE_i &&
              c5 == _CHAR_CODE_n &&
              c6 == _CHAR_CODE_i &&
              c7 == _CHAR_CODE_t &&
              c8 == _CHAR_CODE_y
            ) {
              Ok((fpInf(), negative))
            } else {
              Err("Invalid string")
            }
          } else {
            Err("Invalid string")
          }
        } else {
          Err("Invalid string")
        }
      }
    },
  }
}

@unsafe
provide let isFastPath = (
  exponent: WasmI32,
  mantissa: WasmI64,
  negative: Bool,
  manyDigits: Bool,
) => {
  use WasmI32.{ (<=) }
  use WasmI64.{ (<<) }

  _MIN_EXPONENT_FAST_PATH <= exponent &&
    exponent <= _MAX_EXPONENT_DISGUISED_FAST_PATH &&
    WasmI64.leU(mantissa, _MAX_MANTISSA_FAST_PATH) &&
    !manyDigits
}

@unsafe
provide let parseFloat = (string: String) => {
  use WasmI32.{ (!=), (*) }
  match (parseFloatToParts(string)) {
    Ok((exponent, mantissa, negative, manyDigits)) => {
      use WasmI64.{ (+), (>) }
      let exponent = WasmI32.load(WasmI32.fromGrain(exponent), 4n)
      let mantissa = WasmI64.load(WasmI32.fromGrain(mantissa), 8n)
      let floatOpt = if (isFastPath(exponent, mantissa, negative, manyDigits)) {
        use WasmI32.{ (<=) }
        if (exponent <= _MAX_EXPONENT_FAST_PATH) {
          // normal fast path
          use WasmF64.{ (/), (*) }
          use WasmI32.{ (<) }
          let mantissa = WasmF64.convertI64U(mantissa)
          let n = if (exponent < 0n) {
            use WasmI32.{ (*) }
            mantissa / getPowers10FastPath(exponent * -1n)
          } else {
            mantissa * getPowers10FastPath(exponent)
          }
          if (negative) {
            Some(WasmI32.toGrain(newFloat64(n * -1.0W)): Number)
          } else {
            Some(WasmI32.toGrain(newFloat64(n)): Number)
          }
        } else {
          // disguised fast path
          use WasmI32.{ (-) }
          use WasmI64.{ (*), (<=) }

          let shift = exponent - _MAX_EXPONENT_FAST_PATH

          let mantissa = mantissa * WasmI64.extendI32U(getPowers10(shift))
          if (mantissa > _MAX_MANTISSA_FAST_PATH) {
            None
          } else {
            use WasmF64.{ (*) }

            let mantissa = WasmF64.convertI64U(mantissa)
            let n = mantissa * getPowers10FastPath(_MAX_EXPONENT_FAST_PATH)
            if (negative) {
              Some(WasmI32.toGrain(newFloat64(n * -1.0W)): Number)
            } else {
              Some(WasmI32.toGrain(newFloat64(n)): Number)
            }
          }
        }
      } else {
        None
      }
      // Check if fast path worked
      match (floatOpt) {
        Some(n) => Ok(n),
        None => {
          use WasmI32.{ (<), (>=) }
          // From Rust:
          // If significant digits were truncated, then we can have rounding error
          // only if `mantissa + 1` produces a different result. We also avoid
          // redundantly using the Eisel-Lemire algorithm if it was unable to
          // correctly round on the first pass.

          let mut fp = computeFloat(WasmI64.extendI32S(exponent), mantissa)
          let f = WasmI64.load(WasmI32.fromGrain(fp.f), 8n)
          let e = WasmI32.load(WasmI32.fromGrain(fp.e), 4n)
          if (manyDigits && e >= 0n) {
            use WasmI64.{ (!=) as neWasmI64 }
            let fp2 = computeFloat(WasmI64.extendI32S(exponent), mantissa + 1N)
            let f2 = WasmI64.load(WasmI32.fromGrain(fp2.f), 8n)
            let e2 = WasmI32.load(WasmI32.fromGrain(fp2.e), 4n)
            if (e != e2 || neWasmI64(f, f2)) {
              fp.e = -1l
            }
          }

          // Unable to correctly round the float using the Eisel-Lemire algorithm.
          // Fallback to a slower, but always correct algorithm.
          let e = WasmI32.load(WasmI32.fromGrain(fp.e), 4n)
          if (e < 0n) {
            fp = parseLongMantissa(string)
          }

          Ok(biasedFpToNumber(fp, negative))
        },
      }
    },
    Err(str) => {
      match (parseInfNan(string)) {
        Ok((fp, negative)) => Ok(biasedFpToNumber(fp, negative)),
        _ => Err(str),
      }
    },
  }
}