///|
priv struct Subtag {
  text : String
  start : Int
  end : Int
}

///|
fn split_subtags(input : String) -> (Array[Subtag], Array[Diagnostic]) {
  let parts : Array[Subtag] = []
  let diags : Array[Diagnostic] = []
  if input.length() == 0 {
    diags.push(error_diag("LANG001", "empty language tag", 0, 0))
    return (parts, diags)
  }
  let mut i = 0
  while i < input.length() {
    let c = input[i]
    if c == ' ' || c == '\t' || c == '\n' || c == '\r' {
      diags.push(
        error_diag(
          "LANG002",
          "whitespace is not allowed in a language tag",
          i,
          i + 1,
        ),
      )
      return (parts, diags)
    }
    i += 1
  }
  i = 0
  while i <= input.length() {
    let start = i
    while i < input.length() && input[i] != '-' {
      i += 1
    }
    if i == start {
      diags.push(error_diag("LANG003", "empty subtag", start, start))
    } else {
      parts.push({ text: input[start:i].to_owned(), start, end: i })
    }
    if i >= input.length() {
      break
    }
    i += 1
    if i >= input.length() {
      diags.push(error_diag("LANG003", "empty subtag", i, i))
      break
    }
  }
  (parts, diags)
}

///|
fn is_language_subtag(s : String) -> Bool {
  let n = s.length()
  (n >= 2 && n <= 3 && all_alpha(s)) ||
  (n == 4 && all_alpha(s)) ||
  (n >= 5 && n <= 8 && all_alpha(s))
}

///|
fn is_extlang_subtag(s : String) -> Bool {
  s.length() == 3 && all_alpha(s)
}

///|
fn is_script_subtag(s : String) -> Bool {
  s.length() == 4 && all_alpha(s)
}

///|
fn is_region_subtag(s : String) -> Bool {
  (s.length() == 2 && all_alpha(s)) || (s.length() == 3 && all_digit(s))
}

///|
fn is_variant_subtag(s : String) -> Bool {
  let n = s.length()
  (n >= 5 && n <= 8 && all_alphanum(s)) ||
  (n == 4 && is_digit(s[0]) && all_alphanum(s))
}

///|
fn is_singleton(s : String) -> Bool {
  s.length() == 1 && is_alphanum(s[0]) && lower_ascii(s) != "x"
}

///|
fn is_extension_part(s : String) -> Bool {
  let n = s.length()
  n >= 2 && n <= 8 && all_alphanum(s)
}

///|
fn is_private_part(s : String) -> Bool {
  let n = s.length()
  n >= 1 && n <= 8 && all_alphanum(s)
}

///|
fn parse_from_subtags(
  raw : String,
  parts : Array[Subtag],
  diags : Array[Diagnostic],
) -> LanguageTag? {
  if parts.length() == 0 {
    return None
  }
  if is_grandfathered(raw) {
    return Some({
      kind: Grandfathered,
      language: "",
      extlang: [],
      script: "",
      region: "",
      variants: [],
      extensions: [],
      private_use: [],
      grandfathered: grandfathered_canonical_form(raw),
    })
  }
  let first = parts[0]
  if eq_ignore_ascii(first.text, "x") {
    if parts.length() < 2 {
      diags.push(
        error_diag(
          "LANG010",
          "private-use tag requires at least one subtag after x",
          first.start,
          first.end,
        ),
      )
      return None
    }
    let pu : Array[String] = []
    let mut i = 1
    while i < parts.length() {
      let p = parts[i]
      if !is_private_part(p.text) {
        diags.push(
          error_diag("LANG011", "invalid private-use subtag", p.start, p.end),
        )
        return None
      }
      pu.push(lower_ascii(p.text))
      i += 1
    }
    return Some({
      kind: PrivateUse,
      language: "",
      extlang: [],
      script: "",
      region: "",
      variants: [],
      extensions: [],
      private_use: pu,
      grandfathered: "",
    })
  }
  if !is_language_subtag(first.text) {
    diags.push(
      error_diag(
        "LANG004",
        "invalid primary language subtag",
        first.start,
        first.end,
      ),
    )
    return None
  }
  let mut idx = 1
  let language = lower_ascii(first.text)
  let extlang : Array[String] = []
  if first.text.length() <= 3 {
    let mut ext_count = 0
    while idx < parts.length() &&
          ext_count < 3 &&
          is_extlang_subtag(parts[idx].text) {
      extlang.push(lower_ascii(parts[idx].text))
      ext_count += 1
      idx += 1
    }
  }
  let mut script = ""
  if idx < parts.length() && is_script_subtag(parts[idx].text) {
    script = title_ascii(parts[idx].text)
    idx += 1
  }
  let mut region = ""
  if idx < parts.length() && is_region_subtag(parts[idx].text) {
    if all_alpha(parts[idx].text) {
      region = upper_ascii(parts[idx].text)
    } else {
      region = parts[idx].text
    }
    idx += 1
  }
  let variants : Array[String] = []
  while idx < parts.length() && is_variant_subtag(parts[idx].text) {
    let v = lower_ascii(parts[idx].text)
    if contains_string(variants, v) {
      diags.push(
        warn_diag(
          "LANG020",
          "duplicate variant subtag",
          parts[idx].start,
          parts[idx].end,
        ),
      )
    } else {
      variants.push(v)
    }
    idx += 1
  }
  let extensions : Array[Extension] = []
  let seen_singletons : Array[String] = []
  while idx < parts.length() && is_singleton(parts[idx].text) {
    let singleton = lower_ascii(parts[idx].text)
    let start = parts[idx]
    idx += 1
    if contains_string(seen_singletons, singleton) {
      diags.push(
        error_diag(
          "LANG012",
          "duplicate extension singleton",
          start.start,
          start.end,
        ),
      )
      return None
    }
    seen_singletons.push(singleton)
    let ep : Array[String] = []
    while idx < parts.length() && is_extension_part(parts[idx].text) {
      ep.push(lower_ascii(parts[idx].text))
      idx += 1
    }
    if ep.length() == 0 {
      diags.push(
        error_diag(
          "LANG013",
          "extension singleton is missing subtags",
          start.start,
          start.end,
        ),
      )
      return None
    }
    extensions.push({ singleton, parts: ep })
  }
  let private_use : Array[String] = []
  if idx < parts.length() && eq_ignore_ascii(parts[idx].text, "x") {
    let xspan = parts[idx]
    idx += 1
    while idx < parts.length() {
      if !is_private_part(parts[idx].text) {
        diags.push(
          error_diag(
            "LANG011",
            "invalid private-use subtag",
            parts[idx].start,
            parts[idx].end,
          ),
        )
        return None
      }
      private_use.push(lower_ascii(parts[idx].text))
      idx += 1
    }
    if private_use.length() == 0 {
      diags.push(
        error_diag(
          "LANG010",
          "private-use prefix x requires at least one subtag",
          xspan.start,
          xspan.end,
        ),
      )
      return None
    }
  }
  if idx < parts.length() {
    diags.push(
      error_diag(
        "LANG005",
        "unexpected subtag for BCP 47 grammar",
        parts[idx].start,
        parts[idx].end,
      ),
    )
    return None
  }
  Some({
    kind: Regular,
    language,
    extlang,
    script,
    region,
    variants,
    extensions,
    private_use,
    grandfathered: "",
  })
}

///|
/// Parse a BCP 47 language tag. Grammar errors yield None and diagnostics.
pub fn parse_with_diagnostics(
  input : String,
) -> (LanguageTag?, Array[Diagnostic]) {
  let (parts, diags) = split_subtags(input)
  if diags.any(d => d.severity == Error) {
    return (None, diags)
  }
  let tag = parse_from_subtags(input, parts, diags)
  (tag, diags)
}

///|
pub fn parse(input : String) -> LanguageTag? {
  let (tag, diags) = parse_with_diagnostics(input)
  if diags.any(d => d.severity == Error) {
    None
  } else {
    tag
  }
}

///|
pub fn is_well_formed(input : String) -> Bool {
  match parse(input) {
    None => false
    Some(_) => true
  }
}