///|
fn sort_extensions(exts : Array[Extension]) -> Array[Extension] {
  let out = exts.copy()
  let mut i = 0
  while i < out.length() {
    let mut j = i + 1
    while j < out.length() {
      if out[j].singleton < out[i].singleton {
        let tmp = out[i]
        out[i] = out[j]
        out[j] = tmp
      }
      j += 1
    }
    i += 1
  }
  out
}

///|
/// RFC 5646 4.5 canonicalization: preferred values, suppress-script, extension order, case.
pub fn canonicalize(tag : LanguageTag) -> LanguageTag {
  match tag.kind {
    Grandfathered => {
      let preferred = preferred_value(tag.grandfathered)
      if lower_ascii(preferred) == lower_ascii(tag.grandfathered) {
        {
          kind: Grandfathered,
          language: "",
          extlang: [],
          script: "",
          region: "",
          variants: [],
          extensions: [],
          private_use: [],
          grandfathered: grandfathered_canonical_form(tag.grandfathered),
        }
      } else {
        match parse(preferred) {
          None => tag
          Some(next) => canonicalize(next)
        }
      }
    }
    PrivateUse =>
      {
        kind: PrivateUse,
        language: "",
        extlang: [],
        script: "",
        region: "",
        variants: [],
        extensions: [],
        private_use: tag.private_use.map(s => lower_ascii(s)),
        grandfathered: "",
      }
    Regular => {
      let language = lower_ascii(preferred_language(tag.language))
      let extlang = tag.extlang.map(s => lower_ascii(s))
      let mut script = if tag.script.length() == 0 {
        ""
      } else {
        title_ascii(tag.script)
      }
      let suppress = suppress_script_for(language)
      if script.length() > 0 && eq_ignore_ascii(script, suppress) {
        script = ""
      }
      let mut region = tag.region
      if region.length() > 0 {
        if all_alpha(region) {
          region = upper_ascii(preferred_region(region))
        }
      }
      let variants = tag.variants.map(s => lower_ascii(s))
      let extensions = sort_extensions(
        tag.extensions.map(e => {
          singleton: lower_ascii(e.singleton),
          parts: e.parts.map(p => lower_ascii(p)),
        }),
      )
      let private_use = tag.private_use.map(s => lower_ascii(s))
      {
        kind: Regular,
        language,
        extlang,
        script,
        region,
        variants,
        extensions,
        private_use,
        grandfathered: "",
      }
    }
  }
}

///|
pub fn canonicalize_text(input : String) -> String? {
  match parse(input) {
    None => None
    Some(tag) => Some(format(canonicalize(tag)))
  }
}