///|
/// Position units are explicit: AST spans are Scalar; LSP uses Utf16.
pub(all) enum OffsetUnit {
  Scalar
  Utf16
  Utf8
} derive(Eq)

///|
pub(all) struct Position {
  line : Int32
  character : Int32
} derive(Eq)

///|
pub suberror SourceError {
  InvalidOffset(Int32)
  InvalidPosition(Int32, Int32)
  InvalidSpan(Int32, Int32)
}

///|
/// Immutable mapping over one exact source snapshot. Zero-based positions.
pub struct SourceMap {
  chars : Array[Char]
  utf16 : Array[Int32]
  utf8 : Array[Int32]
  lines : Array[Int32]
}

///|
pub fn SourceMap::new(source : String) -> SourceMap {
  let chars = source.to_array()
  let utf16 = [0]
  let utf8 = [0]
  let lines = [0]
  for i, c in chars {
    let n = c.to_int()
    utf16.push(utf16[i] + (if n > 0xFFFF { 2 } else { 1 }))
    utf8.push(
      utf8[i] +
      (if n <= 0x7F {
        1
      } else if n <= 0x7FF {
        2
      } else if n <= 0xFFFF {
        3
      } else {
        4
      }),
    )
    if c == '\n' {
      lines.push(i + 1)
    }
  }
  { chars, utf16, utf8, lines, }
}

///|
pub fn SourceMap::length(
  self : SourceMap,
  unit~ : OffsetUnit = Scalar,
) -> Int32 {
  match unit {
    Scalar => self.chars.length()
    Utf16 => self.utf16[self.chars.length()]
    Utf8 => self.utf8[self.chars.length()]
  }
}

///|
pub fn SourceMap::line_count(self : SourceMap) -> Int32 {
  self.lines.length()
}

///|
fn boundary_index(values : Array[Int32], target : Int32) -> Int32? {
  let mut low = 0
  let mut high = values.length()
  while low < high {
    let mid = low + (high - low) / 2
    if values[mid] < target {
      low = mid + 1
    } else {
      high = mid
    }
  }
  if low < values.length() && values[low] == target {
    Some(low)
  } else {
    None
  }
}

///|
/// Reject offsets inside a UTF-8 encoding or UTF-16 surrogate pair.
pub fn SourceMap::to_scalar(
  self : SourceMap,
  offset : Int32,
  unit~ : OffsetUnit = Scalar,
) -> Int32 raise SourceError {
  if offset < 0 {
    raise InvalidOffset(offset)
  }
  let result = match unit {
    Scalar => if offset <= self.chars.length() { Some(offset) } else { None }
    Utf16 => boundary_index(self.utf16, offset)
    Utf8 => boundary_index(self.utf8, offset)
  }
  match result {
    Some(n) => n
    None => raise InvalidOffset(offset)
  }
}

///|
pub fn SourceMap::from_scalar(
  self : SourceMap,
  offset : Int32,
  unit~ : OffsetUnit = Scalar,
) -> Int32 raise SourceError {
  if offset < 0 || offset > self.chars.length() {
    raise InvalidOffset(offset)
  }
  match unit {
    Scalar => offset
    Utf16 => self.utf16[offset]
    Utf8 => self.utf8[offset]
  }
}

///|
/// Map a raw offset to a line and character; CR remains a source character.
pub fn SourceMap::position(
  self : SourceMap,
  offset : Int32,
  unit~ : OffsetUnit = Utf16,
) -> Position raise SourceError {
  let scalar = self.to_scalar(offset, unit=Scalar)
  let mut low = 0
  let mut high = self.lines.length()
  while low + 1 < high {
    let mid = low + (high - low) / 2
    if self.lines[mid] <= scalar {
      low = mid
    } else {
      high = mid
    }
  }
  let character = self.from_scalar(scalar, unit~) -
    self.from_scalar(self.lines[low], unit~)
  { line: low, character, }
}

///|
/// Inverse of position. Positions on newline codepoints are accepted, not beyond.
pub fn SourceMap::offset(
  self : SourceMap,
  position : Position,
  unit~ : OffsetUnit = Utf16,
) -> Int32 raise SourceError {
  let { line, character, } = position
  if line < 0 || line >= self.lines.length() || character < 0 {
    raise InvalidPosition(line, character)
  }
  let start = self.lines[line]
  let end = if line + 1 < self.lines.length() {
    self.lines[line + 1] - 1
  } else {
    self.chars.length()
  }
  let base = self.from_scalar(start, unit~)
  let width = self.from_scalar(end, unit~) - base
  if character > width {
    raise InvalidPosition(line, character)
  }
  self.to_scalar(base + character, unit~)
}

///|
/// Slice scalar spans without accidentally using MoonBit's UTF-16 indexing.
pub fn SourceMap::slice(
  self : SourceMap,
  span : Span,
) -> String raise SourceError {
  if span.start < 0 || span.end < span.start || span.end > self.chars.length() {
    raise InvalidSpan(span.start, span.end)
  }
  let out = StringBuilder()
  for i in span.start..