// Copyright 2025 International Digital Economy Academy
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

///|
/// Minimal font system wrapper for the MoonBit cosmic-text port.
///
/// Upstream `cosmic-text` uses `fontdb` for font discovery. In this MoonBit port
/// we start with an in-memory font list backed by `moon_swash`.
pub struct FontEntry {
  id : Int
  family_name : String
  postscript_name : String
  source_data : Bytes
  source_index : Int
  font : @moon_swash.FontRef
  charmap_proxy : @moon_swash.CharmapProxy
  attributes : @moon_swash.Attributes
  is_monospace : Bool
  not_emoji : Bool
}

///|
pub fn FontEntry::id(self : FontEntry) -> Int {
  self.id
}

///|
pub fn FontEntry::family_name(self : FontEntry) -> String {
  self.family_name
}

///|
pub fn FontEntry::postscript_name(self : FontEntry) -> String {
  self.postscript_name
}

///|
pub fn FontEntry::source_data(self : FontEntry) -> Bytes {
  self.source_data
}

///|
pub fn FontEntry::source_index(self : FontEntry) -> Int {
  self.source_index
}

///|
pub fn FontEntry::font(self : FontEntry) -> @moon_swash.FontRef {
  self.font
}

///|
pub fn FontEntry::charmap_proxy(self : FontEntry) -> @moon_swash.CharmapProxy {
  self.charmap_proxy
}

///|
pub fn FontEntry::attributes(self : FontEntry) -> @moon_swash.Attributes {
  self.attributes
}

///|
pub fn FontEntry::is_monospace(self : FontEntry) -> Bool {
  self.is_monospace
}

///|
pub fn FontEntry::not_emoji(self : FontEntry) -> Bool {
  self.not_emoji
}

///|
pub struct FontSystem {
  locale : String
  fonts : Array[FontEntry]
  priv mut fallback_profile_opt : FallbackProfile?
  priv fallback_warning_handler_opt : ((String) -> Unit)?
  font_matches_cache : @hashmap.HashMap[FontMatchAttrs, Array[Int]]
  codepoint_support_cache : @hashmap.HashMap[
    Int,
    FontCachedCodepointSupportInfo,
  ]
  hb_font_cache : @hashmap.HashMap[Int, @font.Font]
  hb_shape_buffer : @buffer.Buffer
  shape_run_cache : ShapeRunCache
}

///|
pub(all) enum FallbackProfile {
  Unix
  MacOS
  Windows
  Other
}

///|
pub impl Eq for FallbackProfile with fn equal(self, other) {
  match (self, other) {
    (Unix, Unix) => true
    (MacOS, MacOS) => true
    (Windows, Windows) => true
    (Other, Other) => true
    _ => false
  }
}

///|
pub(all) enum FallbackMissingKind {
  Exhausted
  PresetFallback
  ScriptFallback
}

///|
priv struct FontFallbackMissingInfo {
  kind : FallbackMissingKind
  scripts : Array[@moon_swash.Script]
  locale : String
  word : String
  used : String?
}

///|
const FONT_MATCHES_CACHE_SIZE_LIMIT : Int = 256

///|
const CODEPOINT_SUPPORTED_PER_FONT_LIMIT : Int = 512

///|
const CODEPOINT_NOT_SUPPORTED_PER_FONT_LIMIT : Int = 1024

///|
const WEIGHT_AXIS_TAG : UInt = 0x77676874U // "wght"

///|
pub fn FontSystem::new() -> FontSystem {
  FontSystem::new_with_locale("en-US")
}

///|
pub fn FontSystem::new_with_locale(locale : String) -> FontSystem {
  FontSystem::{
    locale,
    fonts: [],
    fallback_profile_opt: None,
    fallback_warning_handler_opt: None,
    font_matches_cache: @hashmap.HashMap::default(),
    codepoint_support_cache: @hashmap.HashMap::default(),
    hb_font_cache: @hashmap.HashMap::default(),
    hb_shape_buffer: @buffer.Buffer::new(),
    shape_run_cache: ShapeRunCache::new(),
  }
}

///|
pub fn FontSystem::locale(self : FontSystem) -> String {
  self.locale
}

///|
pub fn FontSystem::fonts(self : FontSystem) -> Array[FontEntry] {
  self.fonts
}

///|
fn FontSystem::hb_font_for_entry(
  self : FontSystem,
  entry : FontEntry,
) -> @font.Font {
  match self.hb_font_cache.get(entry.id) {
    Some(font) => font
    None => {
      let font = @font.Font::new(
        @face.Face::from_bytes(entry.source_data, index=entry.source_index),
      )
      self.hb_font_cache.set(entry.id, font)
      font
    }
  }
}

///|
fn FontSystem::shape_hb_buffer(self : FontSystem) -> @buffer.Buffer {
  self.hb_shape_buffer
}

///|
fn font_family_name(font : @moon_swash.FontRef, locale : String) -> String {
  let strings = font.localized_strings()
  match strings.find_by_id(@moon_swash.StringId::Family, Some(locale)) {
    Some(s) => s.to_string()
    None =>
      match strings.find_by_id(@moon_swash.StringId::Family, None) {
        Some(s) => s.to_string()
        None => ""
      }
  }
}

///|
fn font_postscript_name(font : @moon_swash.FontRef) -> String {
  let strings = font.localized_strings()
  match strings.find_by_id(@moon_swash.StringId::PostScript, None) {
    Some(s) => s.to_string()
    None => ""
  }
}

///|
fn string_contains_ascii(haystack : String, needle : String) -> Bool {
  let hlen = haystack.length()
  let nlen = needle.length()
  if nlen == 0 {
    return true
  }
  if nlen > hlen {
    return false
  }
  for i in 0..<(hlen - nlen + 1) {
    let mut ok = true
    for j in 0.. Bool {
  match id {
    @moon_swash.StringId::Family
    | @moon_swash.StringId::TypographicFamily
    | @moon_swash.StringId::WwsFamily => true
    _ => false
  }
}

///|
fn entry_has_family_name(entry : FontEntry, family_name : String) -> Bool {
  if entry.family_name == family_name {
    return true
  }
  let strings = entry.font.localized_strings()
  for s in strings.iter() {
    if is_family_name_id(s.id()) && s.to_string() == family_name {
      return true
    }
  }
  false
}

///|
fn entry_in_forbidden_fallback(
  entry : FontEntry,
  forbidden_families : Array[String],
) -> Bool {
  for family_name in forbidden_families {
    if entry_has_family_name(entry, family_name) {
      return true
    }
  }
  false
}

///|
/// Load font data (TTF/OTF/TTC bytes) into the system.
///
/// If the bytes do not parse as a font/collection, this is a no-op.
pub fn FontSystem::load_font_data(
  self : FontSystem,
  data : Bytes,
) -> FontSystem {
  match @moon_swash.FontDataRef::from_data(data) {
    None => self
    Some(data_ref) => {
      let locale = self.locale
      let fonts = self.fonts
      let mut source_index = 0
      for f in data_ref.fonts() {
        let id = fonts.length()
        let family_name = font_family_name(f, locale)
        let postscript_name = font_postscript_name(f)
        let not_emoji = !string_contains_ascii(postscript_name, "Emoji")
        let metrics = f.metrics([])
        fonts.push(FontEntry::{
          id,
          family_name,
          postscript_name,
          source_data: data,
          source_index,
          font: f,
          charmap_proxy: @moon_swash.CharmapProxy::from_font(f),
          attributes: f.attributes(),
          is_monospace: metrics.is_monospace && not_emoji,
          not_emoji,
        })
        source_index = source_index + 1
      }
      // New fonts change candidate ordering; clear match cache.
      self.font_matches_cache.clear()
      self.shape_run_cache.clear()
      self.fallback_profile_opt = None
      FontSystem::{ ..self, fonts, }
    }
  }
}

///|
/// Find a font ID that matches the family selector (best-effort).
pub fn FontSystem::select_family(self : FontSystem, family : Family) -> Int? {
  select_family_with_weight(self, family, Weight::normal())
}

///|
fn abs_int(v : Int) -> Int {
  if v < 0 {
    0 - v
  } else {
    v
  }
}

///|
struct FontCachedCodepointSupportInfo {
  supported : Array[UInt]
  not_supported : Array[UInt]
  mut charmap_opt : @moon_swash.Charmap?
}

///|
fn FontCachedCodepointSupportInfo::new() -> FontCachedCodepointSupportInfo {
  FontCachedCodepointSupportInfo::{
    supported: [],
    not_supported: [],
    charmap_opt: None,
  }
}

///|
pub struct FontMatchAttrs {
  family : Family
  weight : Weight
  stretch : @moon_swash.Stretch
  style : @moon_swash.Style
}

///|
pub impl Eq for FontMatchAttrs with fn equal(self, other) {
  self.family == other.family &&
  self.weight == other.weight &&
  self.stretch == other.stretch &&
  self.style == other.style
}

///|
pub impl Hash for FontMatchAttrs with fn hash_combine(self, hasher) {
  self.family.hash_combine(hasher)
  self.weight.hash_combine(hasher)
  hasher.combine_int(self.stretch.raw().to_int())
  hasher.combine_string(self.style.to_string())
}

///|
fn family_matches(entry : FontEntry, family : Family) -> Bool {
  match family {
    Name(name) => entry_has_family_name(entry, name)
    Monospace | UiMonospace => entry.is_monospace
    Emoji => !entry.not_emoji
    _ => true
  }
}

///|
fn explicit_family_matches(entry : FontEntry, family : Family) -> Bool {
  match family {
    Name(name) => entry_has_family_name(entry, name)
    Monospace | UiMonospace => entry.is_monospace
    Emoji => !entry.not_emoji
    _ => false
  }
}

///|
fn fallback_profile_to_sub(
  profile : FallbackProfile,
) -> @font_fallback.FallbackProfile {
  match profile {
    Unix => @font_fallback.Unix
    MacOS => @font_fallback.MacOS
    Windows => @font_fallback.Windows
    Other => @font_fallback.Other
  }
}

///|
fn fallback_profile_from_sub(
  profile : @font_fallback.FallbackProfile,
) -> FallbackProfile {
  match profile {
    @font_fallback.Unix => Unix
    @font_fallback.MacOS => MacOS
    @font_fallback.Windows => Windows
    @font_fallback.Other => Other
  }
}

///|
fn default_fallback_profile(_fs : FontSystem) -> FallbackProfile {
  // Use explicit platform default profile. Runtime font list heuristics are
  // intentionally avoided to keep behavior deterministic.
  fallback_profile_from_sub(@font_fallback.platform_default_fallback_profile())
}

///|
fn fallback_profile(fs : FontSystem) -> FallbackProfile {
  match fs.fallback_profile_opt {
    Some(profile) => profile
    None => {
      let profile = default_fallback_profile(fs)
      fs.fallback_profile_opt = Some(profile)
      profile
    }
  }
}

///|
pub fn FontSystem::set_fallback_profile(
  self : FontSystem,
  profile : FallbackProfile,
) -> FontSystem {
  if self.fallback_profile_opt is Some(current) && current == profile {
    self
  } else {
    FontSystem::{ ..self, fallback_profile_opt: Some(profile) }
  }
}

///|
pub fn FontSystem::clear_fallback_profile(self : FontSystem) -> FontSystem {
  FontSystem::{ ..self, fallback_profile_opt: None }
}

///|
pub fn FontSystem::set_fallback_warning_handler(
  self : FontSystem,
  handler : (String) -> Unit,
) -> FontSystem {
  FontSystem::{ ..self, fallback_warning_handler_opt: Some(handler) }
}

///|
pub fn FontSystem::clear_fallback_warning_handler(
  self : FontSystem,
) -> FontSystem {
  FontSystem::{ ..self, fallback_warning_handler_opt: None }
}

///|
fn forbidden_fallback_family_names(profile : FallbackProfile) -> Array[String] {
  @font_fallback.forbidden_fallback_family_names(
    fallback_profile_to_sub(profile),
  )
}

///|
fn split_default_stage_candidates(
  fs : FontSystem,
  family : Family,
  req_weight : Weight,
  ids : Array[Int],
) -> Array[Int] {
  let defaults : Array[Int] = []
  let mut default_set = false
  for id in ids {
    if id < 0 || id >= fs.fonts.length() {
      continue
    }
    let entry = fs.fonts[id]
    if !default_set &&
      explicit_family_matches(entry, family) &&
      (
        entry_weight_diff(entry, req_weight) == 0 ||
        entry_variable_weight_match(entry, req_weight)
      ) {
      default_set = true
      defaults.push(id)
    }
  }
  defaults
}

///|
fn first_named_fallback_candidate(
  fs : FontSystem,
  req_weight : Weight,
  ids : Array[Int],
  family_name : String,
) -> Int? {
  for id in ids {
    if id < 0 || id >= fs.fonts.length() {
      continue
    }
    let entry = fs.fonts[id]
    if (
        entry_weight_diff(entry, req_weight) == 0 ||
        entry_variable_weight_match(entry, req_weight)
      ) &&
      entry_has_family_name(entry, family_name) {
      return Some(id)
    }
  }
  None
}

///|
fn common_fallback_family_names(profile : FallbackProfile) -> Array[String] {
  @font_fallback.common_fallback_family_names(fallback_profile_to_sub(profile))
}

///|
fn script_uses_fallback_stage(script : @moon_swash.Script) -> Bool {
  @font_fallback.script_uses_fallback_stage(script)
}

///|
fn script_fallback_family_names(
  script : @moon_swash.Script,
  locale : String,
  profile : FallbackProfile,
) -> Array[String] {
  @font_fallback.script_fallback_family_names(
    script,
    locale,
    fallback_profile_to_sub(profile),
  )
}

///|
fn script_in_array(
  scripts : Array[@moon_swash.Script],
  script : @moon_swash.Script,
) -> Bool {
  for s in scripts {
    if s.to_opentype() == script.to_opentype() {
      return true
    }
  }
  false
}

///|
fn entry_supports_any_script(
  entry : FontEntry,
  scripts : Array[@moon_swash.Script],
) -> Bool {
  if scripts.length() == 0 {
    return false
  }
  let systems = entry.font.writing_systems()
  for ws in systems.iter() {
    match ws.script() {
      None => ()
      Some(s) => if script_in_array(scripts, s) { return true }
    }
  }
  false
}

///|
fn better_monospace_fallback_candidate(
  cand : (Int, Bool, Int, Int, Int),
  best : (Int, Bool, Int, Int, Int),
) -> Bool {
  let cand_id = cand.0
  let cand_is_primary_default = cand.1
  let cand_weight_diff = cand.2
  let cand_non_matches = cand.3
  let cand_weight = cand.4
  let best_id = best.0
  let best_is_primary_default = best.1
  let best_weight_diff = best.2
  let best_non_matches = best.3
  let best_weight = best.4
  if cand_is_primary_default != best_is_primary_default {
    return cand_is_primary_default
  }
  if cand_weight_diff != best_weight_diff {
    return cand_weight_diff < best_weight_diff
  }
  if cand_non_matches != best_non_matches {
    return cand_non_matches < best_non_matches
  }
  if cand_weight != best_weight {
    return cand_weight < best_weight
  }
  cand_id < best_id
}

///|
fn reorder_monospace_fallback_candidates(
  fs : FontSystem,
  attrs : Attrs,
  scripts : Array[@moon_swash.Script],
  ordered : Array[Int],
  codepoints : Array[UInt],
) -> Array[Int] {
  if !(attrs.family_value() is Monospace) {
    return ordered
  }
  if codepoints.length() == 0 || ordered.length() <= 1 {
    return ordered
  }

  let req_weight = attrs.weight_value()
  let mut primary_default_mono_id : Int? = None
  for id in ordered {
    match fs.get_font_entry(id) {
      None => ()
      Some(entry) =>
        if entry.is_monospace() && entry_weight_diff(entry, req_weight) == 0 {
          primary_default_mono_id = Some(id)
          break
        }
    }
  }

  let mut has_script_specific_monospace = false
  for id in ordered {
    match fs.get_font_entry(id) {
      None => ()
      Some(entry) =>
        if entry.is_monospace() && entry_supports_any_script(entry, scripts) {
          has_script_specific_monospace = true
          break
        }
    }
  }

  let mono_candidates : Array[(Int, Bool, Int, Int, Int)] = []
  let non_mono_candidates : Array[Int] = []
  for id in ordered {
    match fs.get_font_entry(id) {
      None => non_mono_candidates.push(id)
      Some(entry) => {
        let keep_as_mono = if !entry.is_monospace() {
          false
        } else if has_script_specific_monospace {
          match primary_default_mono_id {
            Some(pid) => pid == id || entry_supports_any_script(entry, scripts)
            None => entry_supports_any_script(entry, scripts)
          }
        } else {
          true
        }
        if keep_as_mono {
          let supported = fs.count_supported_codepoints(id, codepoints)
          let info = (
            id,
            match primary_default_mono_id {
              Some(pid) => pid == id
              None => false
            },
            entry_weight_diff(entry, req_weight),
            codepoints.length() - supported,
            entry_weight_raw(entry),
          )
          mono_candidates.push(info)
        } else {
          non_mono_candidates.push(id)
        }
      }
    }
  }

  let n = mono_candidates.length()
  let used : Array[Bool] = Array::makei(n, _ => false)
  let reordered_mono : Array[Int] = []
  for _ in 0..= 0 {
      used.set(best, true)
      reordered_mono.push(mono_candidates[best].0)
    }
  }

  let reordered : Array[Int] = []
  for id in reordered_mono {
    reordered.push(id)
  }
  for id in non_mono_candidates {
    reordered.push(id)
  }
  reordered
}

///|
priv struct FontFallbackIterState {
  ids : Array[Int]
  defaults : Array[Int]
  scripts : Array[@moon_swash.Script]
  common_families : Array[String]
  forbidden_families : Array[String]
  req_weight : Weight
  locale : String
  profile : FallbackProfile
  mut default_i : Int
  mut script_i : Int
  mut script_family_i : Int
  mut common_i : Int
  mut other_i : Int
  mut end : Bool
}

///|
fn FontFallbackIterState::new(
  ids : Array[Int],
  defaults : Array[Int],
  scripts : Array[@moon_swash.Script],
  common_families : Array[String],
  forbidden_families : Array[String],
  req_weight : Weight,
  locale : String,
  profile : FallbackProfile,
) -> FontFallbackIterState {
  FontFallbackIterState::{
    ids,
    defaults,
    scripts,
    common_families,
    forbidden_families,
    req_weight,
    locale,
    profile,
    default_i: 0,
    script_i: 0,
    script_family_i: 0,
    common_i: 0,
    other_i: 0,
    end: false,
  }
}

///|
fn font_fallback_next(fs : FontSystem, state : FontFallbackIterState) -> Int? {
  if state.default_i < state.defaults.length() {
    let next = state.defaults[state.default_i]
    state.default_i = state.default_i + 1
    return Some(next)
  }

  while state.script_i < state.scripts.length() {
    let script = state.scripts[state.script_i]
    let script_families = script_fallback_family_names(
      script,
      state.locale,
      state.profile,
    )
    while state.script_family_i < script_families.length() {
      let family_name = script_families[state.script_family_i]
      state.script_family_i = state.script_family_i + 1
      match
        first_named_fallback_candidate(
          fs,
          state.req_weight,
          state.ids,
          family_name,
        ) {
        None => ()
        Some(id) => return Some(id)
      }
    }
    state.script_i = state.script_i + 1
    state.script_family_i = 0
  }

  while state.common_i < state.common_families.length() {
    let family_name = state.common_families[state.common_i]
    state.common_i = state.common_i + 1
    match
      first_named_fallback_candidate(
        fs,
        state.req_weight,
        state.ids,
        family_name,
      ) {
      None => ()
      Some(id) => return Some(id)
    }
  }

  while state.other_i < state.ids.length() {
    let id = state.ids[state.other_i]
    state.other_i = state.other_i + 1
    if id < 0 || id >= fs.fonts.length() {
      continue
    }
    let entry = fs.fonts[id]
    if !entry_in_forbidden_fallback(entry, state.forbidden_families) {
      return Some(id)
    }
  }

  state.end = true
  None
}

///|
fn font_fallback_iter_init(
  fs : FontSystem,
  attrs : Attrs,
  scripts : Array[@moon_swash.Script],
  codepoints : Array[UInt],
) -> FontFallbackIterState {
  let req_weight = attrs.weight_value()
  let profile = fallback_profile(fs)
  let ids0 = get_font_matches(fs, attrs)
  let ids = reorder_monospace_fallback_candidates(
    fs, attrs, scripts, ids0, codepoints,
  )
  let forbidden_families = forbidden_fallback_family_names(profile)
  let defaults = split_default_stage_candidates(
    fs,
    attrs.family_value(),
    req_weight,
    ids,
  )
  let seen_scripts : Array[@moon_swash.Script] = []
  for script in scripts {
    if !script_uses_fallback_stage(script) ||
      script_in_array(seen_scripts, script) {
      continue
    }
    seen_scripts.push(script)
  }
  FontFallbackIterState::new(
    ids,
    defaults,
    seen_scripts,
    common_fallback_family_names(profile),
    forbidden_families,
    req_weight,
    fs.locale,
    profile,
  )
}

///|
fn font_face_name(fs : FontSystem, id : Int) -> String {
  if id < 0 || id >= fs.fonts.length() {
    return "invalid font id"
  }
  let entry = fs.fonts[id]
  if entry.family_name != "" {
    entry.family_name
  } else {
    entry.postscript_name
  }
}

///|
fn font_fallback_check_missing(
  fs : FontSystem,
  state : FontFallbackIterState,
  word : String,
) -> FontFallbackMissingInfo? {
  if state.end {
    return Some(FontFallbackMissingInfo::{
      kind: Exhausted,
      scripts: state.scripts.copy(),
      locale: fs.locale,
      word,
      used: None,
    })
  }
  if state.other_i > 0 {
    let last_i = state.other_i - 1
    let used = if last_i >= 0 && last_i < state.ids.length() {
      Some(font_face_name(fs, state.ids[last_i]))
    } else {
      None
    }
    return Some(FontFallbackMissingInfo::{
      kind: PresetFallback,
      scripts: state.scripts.copy(),
      locale: fs.locale,
      word,
      used,
    })
  }
  if state.scripts.length() > 0 && state.common_i > 0 {
    let last_i = state.common_i - 1
    let used = if last_i >= 0 && last_i < state.common_families.length() {
      Some(state.common_families[last_i])
    } else {
      None
    }
    return Some(FontFallbackMissingInfo::{
      kind: ScriptFallback,
      scripts: state.scripts.copy(),
      locale: fs.locale,
      word,
      used,
    })
  }
  None
}

///|
fn font_fallback_missing_message(info : FontFallbackMissingInfo) -> String {
  let mut scripts = "["
  let mut i = 0
  while i < info.scripts.length() {
    if i > 0 {
      scripts = scripts + ", "
    }
    scripts = scripts + info.scripts[i].name()
    i = i + 1
  }
  scripts = scripts + "]"
  match info.kind {
    Exhausted =>
      "Failed to find any fallback for \{scripts} locale '\{info.locale}': '\{info.word}'"
    PresetFallback => {
      let used = match info.used {
        None => "invalid font id"
        Some(v) => v
      }
      "Failed to find preset fallback for \{scripts} locale '\{info.locale}', used '\{used}': '\{info.word}'"
    }
    ScriptFallback => {
      let used = match info.used {
        None => "invalid font id"
        Some(v) => v
      }
      "Failed to find script fallback for \{scripts} locale '\{info.locale}', used '\{used}': '\{info.word}'"
    }
  }
}

///|
fn font_fallback_emit_missing_warning(
  fs : FontSystem,
  info : FontFallbackMissingInfo,
) -> Unit {
  let message = font_fallback_missing_message(info)
  match fs.fallback_warning_handler_opt {
    None => ()
    Some(handler) => handler(message)
  }
}

///|
fn font_maps_codepoint(
  fs : FontSystem,
  entry : FontEntry,
  codepoint : UInt,
) -> Bool {
  match fs.codepoint_support_cache.get(entry.id) {
    Some(info) => {
      let ok = cached_codepoint_has_support(info, entry, codepoint)
      fs.codepoint_support_cache.set(entry.id, info)
      ok
    }
    None => {
      let info = FontCachedCodepointSupportInfo::new()
      let ok = cached_codepoint_has_support(info, entry, codepoint)
      fs.codepoint_support_cache.set(entry.id, info)
      ok
    }
  }
}

///|
fn sorted_search_uint(arr : Array[UInt], value : UInt) -> (Bool, Int) {
  let mut low = 0
  let mut high = arr.length()
  while low < high {
    let mid = low + (high - low) / 2
    let cur = arr[mid]
    if cur == value {
      return (true, mid)
    }
    if cur < value {
      low = mid + 1
    } else {
      high = mid
    }
  }
  (false, low)
}

///|
fn cached_codepoint_has_support(
  info : FontCachedCodepointSupportInfo,
  entry : FontEntry,
  codepoint : UInt,
) -> Bool {
  let (supported_hit, supported_insert_pos) = sorted_search_uint(
    info.supported,
    codepoint,
  )
  if supported_hit {
    return true
  }
  let (not_supported_hit, not_supported_insert_pos) = sorted_search_uint(
    info.not_supported,
    codepoint,
  )
  if not_supported_hit {
    return false
  }

  let cm = match info.charmap_opt {
    Some(cached) => cached
    None => {
      let built = entry.charmap_proxy.materialize(entry.font)
      info.charmap_opt = Some(built)
      built
    }
  }
  let ok = cm.map(codepoint) != 0
  if ok {
    if supported_insert_pos != CODEPOINT_SUPPORTED_PER_FONT_LIMIT {
      info.supported.insert(supported_insert_pos, codepoint)
      info.supported.truncate(CODEPOINT_SUPPORTED_PER_FONT_LIMIT)
    }
  } else if not_supported_insert_pos != CODEPOINT_NOT_SUPPORTED_PER_FONT_LIMIT {
    info.not_supported.insert(not_supported_insert_pos, codepoint)
    info.not_supported.truncate(CODEPOINT_NOT_SUPPORTED_PER_FONT_LIMIT)
  }
  ok
}

///|
fn entry_weight_diff(entry : FontEntry, req_weight : Weight) -> Int {
  let a = entry.attributes.weight().value.to_int()
  abs_int(a - req_weight.value)
}

///|
fn entry_weight_raw(entry : FontEntry) -> Int {
  entry.attributes.weight().value.to_int()
}

///|
fn entry_stretch_raw(entry : FontEntry) -> Int {
  entry.attributes.stretch().raw().to_int()
}

///|
fn entry_stretch_diff(
  entry : FontEntry,
  req_stretch : @moon_swash.Stretch,
) -> Int {
  abs_int(entry_stretch_raw(entry) - req_stretch.raw().to_int())
}

///|
fn style_bucket(style : @moon_swash.Style) -> Int {
  match style {
    @moon_swash.Style::Normal => 0
    @moon_swash.Style::Italic => 1
    @moon_swash.Style::Oblique(_) => 2
  }
}

///|
fn style_diff(lhs : @moon_swash.Style, rhs : @moon_swash.Style) -> Int {
  let a = style_bucket(lhs)
  let b = style_bucket(rhs)
  if a == b {
    0
  } else if (a == 1 && b == 2) || (a == 2 && b == 1) {
    1
  } else {
    2
  }
}

///|
fn entry_style_diff(entry : FontEntry, req_style : @moon_swash.Style) -> Int {
  style_diff(entry.attributes.style(), req_style)
}

///|
fn entry_variable_weight_match(entry : FontEntry, req_weight : Weight) -> Bool {
  if entry_weight_diff(entry, req_weight) == 0 ||
    !entry.attributes.has_weight_variation() {
    return false
  }
  match entry.font.variations().find_by_tag(WEIGHT_AXIS_TAG) {
    None => false
    Some(axis) => {
      let w = req_weight.value.to_double()
      let min_w = axis.min_value()
      let max_w = axis.max_value()
      w >= min_w && w <= max_w
    }
  }
}

///|
fn better_font_match(
  cand : (Int, Bool, Int, Int, Int, Int, Int, Bool),
  best : (Int, Bool, Int, Int, Int, Int, Int, Bool),
) -> Bool {
  let cand_id = cand.0
  let cand_not_emoji = cand.1
  let cand_wdiff = cand.2
  let cand_stretch_diff = cand.3
  let cand_style_diff = cand.4
  let cand_weight = cand.5
  let cand_stretch = cand.6
  let best_id = best.0
  let best_not_emoji = best.1
  let best_wdiff = best.2
  let best_stretch_diff = best.3
  let best_style_diff = best.4
  let best_weight = best.5
  let best_stretch = best.6
  if cand_not_emoji != best_not_emoji {
    // Keep the same ordering semantics as reference `FontMatchKey` derived Ord.
    return !cand_not_emoji
  }
  if cand_wdiff != best_wdiff {
    return cand_wdiff < best_wdiff
  }
  if cand_stretch_diff != best_stretch_diff {
    return cand_stretch_diff < best_stretch_diff
  }
  if cand_style_diff != best_style_diff {
    return cand_style_diff < best_style_diff
  }
  if cand_weight != best_weight {
    return cand_weight < best_weight
  }
  if cand_stretch != best_stretch {
    return cand_stretch < best_stretch
  }
  cand_id < best_id
}

///|
fn build_font_matches(fs : FontSystem, attrs : Attrs) -> Array[Int] {
  let family = attrs.family_value()
  let req_weight = attrs.weight_value()
  let req_stretch = attrs.stretch_value()
  let req_style = attrs.style_value()
  let candidates : Array[(Int, Bool, Int, Int, Int, Int, Int, Bool)] = []
  for e in fs.fonts {
    candidates.push(
      (
        e.id,
        e.not_emoji,
        entry_weight_diff(e, req_weight),
        entry_stretch_diff(e, req_stretch),
        entry_style_diff(e, req_style),
        entry_weight_raw(e),
        entry_stretch_raw(e),
        entry_variable_weight_match(e, req_weight),
      ),
    )
  }
  let n = candidates.length()
  let used : Array[Bool] = Array::makei(n, _ => false)
  let ids : Array[Int] = []
  for _ in 0..= 0 {
      used.set(best_i, true)
      ids.push(candidates[best_i].0)
    }
  }

  // Keep candidate ordering close to upstream:
  // sort globally by match score, then move query best family match to front.
  let mut preferred : (Int, Bool, Int, Int, Int, Int, Int, Bool)? = None
  for e in fs.fonts {
    if !explicit_family_matches(e, family) {
      continue
    }
    let cand = (
      e.id,
      e.not_emoji,
      entry_weight_diff(e, req_weight),
      entry_stretch_diff(e, req_stretch),
      entry_style_diff(e, req_style),
      entry_weight_raw(e),
      entry_stretch_raw(e),
      entry_variable_weight_match(e, req_weight),
    )
    match preferred {
      None => preferred = Some(cand)
      Some(best) => if better_font_match(cand, best) { preferred = Some(cand) }
    }
  }

  match preferred {
    None => ids
    Some(best) => {
      let pid = best.0
      if ids.length() == 0 || ids[0] == pid {
        return ids
      }
      let reordered : Array[Int] = [pid]
      for id in ids {
        if id != pid {
          reordered.push(id)
        }
      }
      reordered
    }
  }
}

///|
fn get_font_matches(fs : FontSystem, attrs : Attrs) -> Array[Int] {
  if fs.font_matches_cache.length() >= FONT_MATCHES_CACHE_SIZE_LIMIT {
    fs.font_matches_cache.clear()
  }
  let key = FontMatchAttrs::{
    family: attrs.family_value(),
    weight: attrs.weight_value(),
    stretch: attrs.stretch_value(),
    style: attrs.style_value(),
  }
  match fs.font_matches_cache.get(key) {
    Some(ids) => ids.copy()
    None => {
      let ids = build_font_matches(fs, attrs)
      fs.font_matches_cache.set(key, ids)
      ids.copy()
    }
  }
}

///|
fn codepoint_to_char(codepoint : UInt) -> Char? {
  if codepoint > 0x10FFFF {
    None
  } else {
    let v = codepoint.reinterpret_as_int()
    if v >= 0xD800 && v <= 0xDFFF {
      return None
    }
    Some(v.unsafe_to_char())
  }
}

///|
/// Get ordered font match candidates for attrs (cached).
pub fn FontSystem::font_matches(self : FontSystem, attrs : Attrs) -> Array[Int] {
  get_font_matches(self, attrs)
}

///|
pub fn FontSystem::font_matches_for_script(
  self : FontSystem,
  attrs : Attrs,
  script : @moon_swash.Script,
) -> Array[Int] {
  self.font_matches_for_scripts_with_codepoints(attrs, [script], [])
}

///|
pub fn FontSystem::font_matches_for_scripts(
  self : FontSystem,
  attrs : Attrs,
  scripts : Array[@moon_swash.Script],
) -> Array[Int] {
  self.font_matches_for_scripts_with_codepoints(attrs, scripts, [])
}

///|
pub fn FontSystem::font_matches_for_scripts_with_codepoints(
  self : FontSystem,
  attrs : Attrs,
  scripts : Array[@moon_swash.Script],
  codepoints : Array[UInt],
) -> Array[Int] {
  let iter = font_fallback_iter_init(self, attrs, scripts, codepoints)
  let staged : Array[Int] = []
  while true {
    match font_fallback_next(self, iter) {
      None => break
      Some(id) => staged.push(id)
    }
  }
  staged
}

///|
pub fn FontSystem::count_supported_codepoints(
  self : FontSystem,
  font_id : Int,
  codepoints : Array[UInt],
) -> Int {
  if font_id < 0 || font_id >= self.fonts.length() {
    return 0
  }
  let entry = self.fonts[font_id]
  let mut count = 0
  for cp in codepoints {
    if font_maps_codepoint(self, entry, cp) {
      count = count + 1
    }
  }
  count
}

///|
fn select_family_with_weight(
  fs : FontSystem,
  family : Family,
  req_weight : Weight,
) -> Int? {
  let attrs = Attrs::new().family(family).weight(req_weight)
  let ids = get_font_matches(fs, attrs)
  for id in ids {
    if id >= 0 && id < fs.fonts.length() && family_matches(fs.fonts[id], family) {
      return Some(id)
    }
  }
  None
}

///|
/// Resolve a font ID for a specific codepoint (best-effort).
///
/// This prefers the requested family (when present) and then minimizes weight
/// difference, falling back to any loaded font that supports the codepoint.
pub fn FontSystem::resolve_for_codepoint(
  self : FontSystem,
  attrs : Attrs,
  codepoint : UInt,
) -> Int? {
  let scripts : Array[@moon_swash.Script] = []
  match codepoint_to_char(codepoint) {
    None => ()
    Some(ch) =>
      scripts.push(@moon_swash.CharInfo::from_char(ch).properties().script())
  }
  let matches = if scripts.length() > 0 {
    self.font_matches_for_scripts(attrs, scripts)
  } else {
    get_font_matches(self, attrs)
  }
  for id in matches {
    if id < 0 || id >= self.fonts.length() {
      continue
    }
    let e = self.fonts[id]
    if font_maps_codepoint(self, e, codepoint) {
      return Some(id)
    }
  }
  self.resolve(attrs)
}

///|
/// Resolve a font ID for the given attrs (best-effort).
pub fn FontSystem::resolve(self : FontSystem, attrs : Attrs) -> Int? {
  let matches = get_font_matches(self, attrs)
  if matches.length() > 0 {
    Some(matches[0])
  } else if self.fonts.length() > 0 {
    Some(0)
  } else {
    None
  }
}

///|
pub fn FontSystem::get_font(
  self : FontSystem,
  font_id : Int,
) -> @moon_swash.FontRef? {
  if font_id < 0 || font_id >= self.fonts.length() {
    return None
  }
  Some(self.fonts[font_id].font)
}

///|
/// Get the full FontEntry for a font_id (useful for downstream rasterization with TTC collections).
pub fn FontSystem::get_font_entry(
  self : FontSystem,
  font_id : Int,
) -> FontEntry? {
  if font_id < 0 || font_id >= self.fonts.length() {
    return None
  }
  Some(self.fonts[font_id])
}