///|
/// The four B-tree page types defined by the SQLite file format.
pub(all) enum PageType {
  IndexInterior
  TableInterior
  IndexLeaf
  TableLeaf
} derive(Eq, Compare, Debug)

///|
pub fn PageType::from_flag(
  flag : Int,
  offset : Int,
) -> PageType raise ParseError {
  match flag {
    0x02 => IndexInterior
    0x05 => TableInterior
    0x0a => IndexLeaf
    0x0d => TableLeaf
    _ => raise InvalidValue(offset, "B-tree page type", flag.to_string())
  }
}

///|
pub fn PageType::flag(self : PageType) -> Int {
  match self {
    IndexInterior => 0x02
    TableInterior => 0x05
    IndexLeaf => 0x0a
    TableLeaf => 0x0d
  }
}

///|
pub fn PageType::label(self : PageType) -> String {
  match self {
    IndexInterior => "index-interior"
    TableInterior => "table-interior"
    IndexLeaf => "index-leaf"
    TableLeaf => "table-leaf"
  }
}

///|
pub fn PageType::is_interior(self : PageType) -> Bool {
  match self {
    IndexInterior | TableInterior => true
    IndexLeaf | TableLeaf => false
  }
}

///|
pub fn PageType::is_table(self : PageType) -> Bool {
  match self {
    TableInterior | TableLeaf => true
    IndexInterior | IndexLeaf => false
  }
}

///|
pub fn PageType::header_size(self : PageType) -> Int {
  if self.is_interior() {
    12
  } else {
    8
  }
}

///|
/// Immutable database image backed by the caller-provided bytes.
pub(all) struct DatabaseImage {
  data : Bytes
  header : DatabaseHeader
  page_count : UInt64
}

///|
pub fn DatabaseImage::open(data : Bytes) -> DatabaseImage raise ParseError {
  let header = parse_database_header(data)
  let page_count = (data.length() / header.page_size).to_uint64()
  guard page_count > 0UL else {
    raise UnexpectedEnd(0, header.page_size, data.length(), "SQLite page 1")
  }
  { data, header, page_count }
}

///|
pub fn DatabaseImage::file_length(self : DatabaseImage) -> Int {
  self.data.length()
}

///|
pub fn DatabaseImage::validate_page_number(
  self : DatabaseImage,
  page_number : UInt64,
) -> Unit raise ParseError {
  guard page_number >= 1UL && page_number <= self.page_count else {
    raise InvalidPageNumber(page_number, self.page_count)
  }
}

///|
pub fn DatabaseImage::page_offset(
  self : DatabaseImage,
  page_number : UInt64,
) -> Int raise ParseError {
  self.validate_page_number(page_number)
  (page_number.to_int() - 1) * self.header.page_size
}

///|
pub fn DatabaseImage::page_bytes(
  self : DatabaseImage,
  page_number : UInt64,
) -> Bytes raise ParseError {
  let offset = self.page_offset(page_number)
  Bytes::makei(self.header.page_size, fn(index) { self.data[offset + index] })
}

///|
pub fn DatabaseImage::page_reader(
  self : DatabaseImage,
  page_number : UInt64,
  context : String,
) -> BinaryReader raise ParseError {
  let offset = self.page_offset(page_number)
  BinaryReader::range(self.data, offset, self.header.page_size, context)
}

///|
/// Parsed common header of a B-tree page.
pub(all) struct BtreePageHeader {
  page_number : UInt64
  page_offset : Int
  header_offset : Int
  page_type : PageType
  first_freeblock : Int
  cell_count : Int
  cell_content_area : Int
  fragmented_free_bytes : Int
  right_most_pointer : UInt64?
  cell_pointers : Array[Int]
} derive(Eq, Debug)

///|
pub fn BtreePageHeader::header_size(self : BtreePageHeader) -> Int {
  self.page_type.header_size()
}

///|
pub fn BtreePageHeader::pointer_array_start(self : BtreePageHeader) -> Int {
  self.header_offset + self.header_size()
}

///|
pub fn BtreePageHeader::pointer_array_end(self : BtreePageHeader) -> Int {
  self.pointer_array_start() + self.cell_count * 2
}

///|
pub fn BtreePageHeader::cell_content_start(self : BtreePageHeader) -> Int {
  if self.cell_content_area == 0 {
    65536
  } else {
    self.cell_content_area
  }
}

///|
pub fn BtreePageHeader::unallocated_bytes(self : BtreePageHeader) -> Int {
  let value = self.cell_content_start() - self.pointer_array_end()
  if value < 0 {
    0
  } else {
    value
  }
}

///|
pub(all) struct Freeblock {
  offset : Int
  next : Int
  size : Int
} derive(Eq, Debug)

///|
pub(all) struct PageLayout {
  page_number : UInt64
  header_bytes : Int
  pointer_array_bytes : Int
  unallocated_bytes : Int
  cell_content_bytes : Int
  freeblock_bytes : Int
  fragmented_free_bytes : Int
  usable_bytes : Int
  freeblocks : Array[Freeblock]
} derive(Eq, Debug)

///|
pub fn PageLayout::total_free_bytes(self : PageLayout) -> Int {
  self.unallocated_bytes + self.freeblock_bytes + self.fragmented_free_bytes
}

///|
fn contains_int(values : Array[Int], target : Int) -> Bool {
  for value in values {
    if value == target {
      return true
    }
  }
  false
}

///|
fn parse_cell_pointers(
  page : Bytes,
  header_offset : Int,
  page_type : PageType,
  cell_count : Int,
  usable_size : Int,
  page_number : UInt64,
) -> Array[Int] raise ParseError {
  let pointer_start = header_offset + page_type.header_size()
  guard cell_count >= 0 && cell_count <= (usable_size - pointer_start) / 2 else {
    raise InvalidValue(pointer_start, "cell count", cell_count.to_string())
  }
  let reader = BinaryReader::range(
    page,
    pointer_start,
    cell_count * 2,
    "page " + page_number.to_string() + " cell pointer array",
  )
  let pointers : Array[Int] = []
  for _index = 0; _index < cell_count; _index = _index + 1 {
    let pointer = reader.read_u16_be()
    guard pointer >= 0 && pointer < usable_size else {
      raise InvalidValue(
        pointer_start + _index * 2,
        "cell pointer",
        pointer.to_string(),
      )
    }
    pointers.push(pointer)
  }
  pointers
}

///|
pub fn parse_btree_page_header(
  database : DatabaseImage,
  page_number : UInt64,
) -> BtreePageHeader raise ParseError {
  let page = database.page_bytes(page_number)
  let header_offset = if page_number == 1UL { 100 } else { 0 }
  let usable_size = database.header.usable_page_size()
  guard header_offset + 8 <= usable_size else {
    raise UnexpectedEnd(
      header_offset,
      8,
      usable_size - header_offset,
      "B-tree page header",
    )
  }
  let reader = BinaryReader::range(
    page,
    header_offset,
    usable_size - header_offset,
    "page " + page_number.to_string() + " B-tree header",
  )
  let page_type = PageType::from_flag(reader.read_u8().to_int(), header_offset)
  let first_freeblock = reader.read_u16_be()
  let cell_count = reader.read_u16_be()
  let raw_content_area = reader.read_u16_be()
  let cell_content_area = if raw_content_area == 0 &&
    database.header.page_size == 65536 {
    65536
  } else {
    raw_content_area
  }
  let fragmented_free_bytes = reader.read_u8().to_int()
  let right_most_pointer = if page_type.is_interior() {
    Some(reader.read_u32_be())
  } else {
    None
  }
  let pointers = parse_cell_pointers(
    page, header_offset, page_type, cell_count, usable_size, page_number,
  )
  let pointer_array_end = header_offset +
    page_type.header_size() +
    cell_count * 2
  guard cell_content_area >= pointer_array_end &&
    cell_content_area <= usable_size else {
    raise InvalidValue(
      header_offset + 5,
      "cell content area",
      cell_content_area.to_string(),
    )
  }
  guard fragmented_free_bytes <= 60 else {
    raise InvalidValue(
      header_offset + 7,
      "fragmented free bytes",
      fragmented_free_bytes.to_string(),
    )
  }
  if first_freeblock != 0 {
    guard first_freeblock >= pointer_array_end &&
      first_freeblock + 4 <= usable_size else {
      raise InvalidValue(
        header_offset + 1,
        "first freeblock",
        first_freeblock.to_string(),
      )
    }
  }
  {
    page_number,
    page_offset: database.page_offset(page_number),
    header_offset,
    page_type,
    first_freeblock,
    cell_count,
    cell_content_area,
    fragmented_free_bytes,
    right_most_pointer,
    cell_pointers: pointers,
  }
}

///|
pub fn parse_freeblocks(
  database : DatabaseImage,
  header : BtreePageHeader,
) -> Array[Freeblock] raise ParseError {
  let page = database.page_bytes(header.page_number)
  let usable_size = database.header.usable_page_size()
  let visited : Array[Int] = []
  let blocks : Array[Freeblock] = []
  let mut offset = header.first_freeblock
  while offset != 0 {
    guard !contains_int(visited, offset) else {
      raise InvalidValue(offset, "freeblock chain", "cycle detected")
    }
    visited.push(offset)
    guard offset >= header.pointer_array_end() && offset + 4 <= usable_size else {
      raise InvalidValue(offset, "freeblock offset", offset.to_string())
    }
    let reader = BinaryReader::range(
      page,
      offset,
      usable_size - offset,
      "page freeblock",
    )
    let next = reader.read_u16_be()
    let size = reader.read_u16_be()
    guard size >= 4 && offset + size <= usable_size else {
      raise InvalidValue(offset + 2, "freeblock size", size.to_string())
    }
    if next != 0 {
      guard next > offset && next + 4 <= usable_size else {
        raise InvalidValue(offset, "next freeblock", next.to_string())
      }
    }
    blocks.push({ offset, next, size })
    offset = next
  }
  blocks
}

///|
pub fn analyze_page_layout(
  database : DatabaseImage,
  header : BtreePageHeader,
) -> PageLayout raise ParseError {
  let usable = database.header.usable_page_size()
  let freeblocks = parse_freeblocks(database, header)
  let mut freeblock_bytes = 0
  for block in freeblocks {
    freeblock_bytes += block.size
  }
  let content_start = header.cell_content_start()
  {
    page_number: header.page_number,
    header_bytes: header.header_offset + header.header_size(),
    pointer_array_bytes: header.cell_count * 2,
    unallocated_bytes: header.unallocated_bytes(),
    cell_content_bytes: usable - content_start,
    freeblock_bytes,
    fragmented_free_bytes: header.fragmented_free_bytes,
    usable_bytes: usable,
    freeblocks,
  }
}

///|
/// Validate page-local layout facts without parsing cell payloads.
pub fn validate_page_layout(
  database : DatabaseImage,
  header : BtreePageHeader,
) -> Array[Diagnostic] {
  let diagnostics : Array[Diagnostic] = []
  let pointer_end = header.pointer_array_end()
  for index = 0; index < header.cell_pointers.length(); index = index + 1 {
    let pointer = header.cell_pointers[index]
    if pointer < header.cell_content_start() {
      diagnostics.push(
        Diagnostic::warning(
          "PAGE_CELL_BEFORE_CONTENT",
          "cell pointer " +
          index.to_string() +
          " points before the declared content area",
          offset=header.page_offset + pointer,
          page_number=header.page_number,
        ),
      )
    }
    if pointer < pointer_end {
      diagnostics.push(
        Diagnostic::error(
          "PAGE_CELL_OVERLAPS_POINTERS",
          "cell pointer overlaps the page header or pointer array",
          offset=header.page_offset + pointer,
          page_number=header.page_number,
        ),
      )
    }
  }
  if header.right_most_pointer is Some(page) &&
    (page == 0UL || page > database.page_count) {
    diagnostics.push(
      Diagnostic::error(
        "PAGE_RIGHTMOST_RANGE",
        "right-most child page is outside the database",
        offset=header.page_offset + header.header_offset + 8,
        page_number=header.page_number,
      ),
    )
  }
  diagnostics
}

///|
/// Compute the local payload length using SQLite's spill formula.
pub fn local_payload_size(
  page_type : PageType,
  payload_size : Int,
  usable_size : Int,
) -> Int raise ParseError {
  guard payload_size >= 0 && usable_size >= 480 else {
    raise InvalidValue(0, "payload calculation", "invalid size")
  }
  let min_local = (usable_size - 12) * 32 / 255 - 23
  let max_local = match page_type {
    TableLeaf => usable_size - 35
    IndexLeaf | IndexInterior => (usable_size - 12) * 64 / 255 - 23
    TableInterior => 0
  }
  if payload_size <= max_local {
    return payload_size
  }
  let candidate = min_local + (payload_size - min_local) % (usable_size - 4)
  if candidate > max_local {
    min_local
  } else {
    candidate
  }
}