///|
fn skip_ows(s : String, i : Int) -> Int {
  let mut n = i
  while n < s.length() && (s[n] == ' ' || s[n] == '\t') {
    n += 1
  }
  n
}

///|
fn parse_q(raw : String) -> Int? {
  let s = lower_ascii(raw)
  if s == "0" || s == "0.0" || s == "0.00" || s == "0.000" {
    return Some(0)
  }
  if s == "1" || s == "1.0" || s == "1.00" || s == "1.000" {
    return Some(1000)
  }
  if s.length() >= 2 && s[0] == '0' && s[1] == '.' {
    let mut milli = 0
    let mut k = 2
    let mut digits = 0
    while k < s.length() {
      if !is_digit(s[k]) || digits >= 3 {
        return None
      }
      milli = milli * 10 + digit_value(s[k])
      digits += 1
      k += 1
    }
    while digits < 3 {
      milli = milli * 10
      digits += 1
    }
    return Some(milli)
  }
  None
}

///|
/// Parse RFC 4647 / HTTP Accept-Language lists such as `fr-CH, fr;q=0.9, en;q=0.8, *;q=0.1`.
pub fn parse_accept_language(
  header : String,
) -> (Array[LanguageRange], Array[Diagnostic]) {
  let ranges : Array[LanguageRange] = []
  let diags : Array[Diagnostic] = []
  let mut i = 0
  while i < header.length() {
    i = skip_ows(header, i)
    if i >= header.length() {
      break
    }
    let start = i
    while i < header.length() &&
          header[i] != ',' &&
          header[i] != ';' &&
          header[i] != ' ' &&
          header[i] != '\t' {
      i += 1
    }
    if i == start {
      diags.push(error_diag("LANG030", "empty language range", start, start))
      break
    }
    let range = header[start:i].to_owned()
    if range != "*" && !is_well_formed(range) {
      diags.push(
        error_diag(
          "LANG031", "language range is not a well-formed tag or *", start, i,
        ),
      )
    }
    i = skip_ows(header, i)
    let mut q = 1000
    if i < header.length() && header[i] == ';' {
      i += 1
      i = skip_ows(header, i)
      if i + 1 < header.length() &&
        (header[i] == 'q' || header[i] == 'Q') &&
        header[i + 1] == '=' {
        i += 2
        let qstart = i
        while i < header.length() &&
              header[i] != ',' &&
              header[i] != ' ' &&
              header[i] != '\t' {
          i += 1
        }
        match parse_q(header[qstart:i].to_owned()) {
          None =>
            diags.push(error_diag("LANG032", "invalid q-value", qstart, i))
          Some(v) => q = v
        }
      } else {
        diags.push(error_diag("LANG032", "expected q= after ';'", i, i))
      }
    }
    i = skip_ows(header, i)
    if i < header.length() && header[i] == ',' {
      i += 1
    }
    if range == "*" || is_well_formed(range) {
      ranges.push({
        range,
        q_milli: q,
        span: make_span(start, start + range.length()),
      })
    }
  }
  (ranges, diags)
}

///|
fn sort_ranges(ranges : Array[LanguageRange]) -> Array[LanguageRange] {
  let out = ranges.copy()
  let mut i = 0
  while i < out.length() {
    let mut j = i + 1
    while j < out.length() {
      if out[j].q_milli > out[i].q_milli {
        let tmp = out[i]
        out[i] = out[j]
        out[j] = tmp
      }
      j += 1
    }
    i += 1
  }
  out
}

///|
/// Choose the best available tag for an Accept-Language header.
pub fn negotiate(header : String, available : Array[String]) -> String? {
  let (ranges, _) = parse_accept_language(header)
  let ordered = sort_ranges(ranges)
  let mut i = 0
  while i < ordered.length() {
    let matched = basic_filter(ordered[i].range, available)
    if matched.length() > 0 {
      return Some(matched[0])
    }
    i += 1
  }
  None
}