///|
/// One SQLite freelist trunk page and the leaf page numbers stored on it.
pub(all) struct FreelistTrunk {
  page_number : UInt64
  next_trunk_page : UInt64
  leaf_count : Int
  leaf_pages : Array[UInt64]
} derive(Eq, Debug)

///|
/// A complete walk of the freelist rooted in the database header.
pub(all) struct FreelistReport {
  trunks : Array[FreelistTrunk]
  trunk_pages : Array[UInt64]
  leaf_pages : Array[UInt64]
  diagnostics : Array[Diagnostic]
  declared_page_count : UInt64
} derive(Debug)

///|
pub fn FreelistReport::observed_page_count(self : FreelistReport) -> Int {
  self.trunk_pages.length() + self.leaf_pages.length()
}

///|
fn page_list_contains(pages : Array[UInt64], wanted : UInt64) -> Bool {
  for page in pages {
    if page == wanted {
      return true
    }
  }
  false
}

///|
/// Decode a single freelist trunk. Leaf pages are references only: their
/// contents are intentionally not read because SQLite assigns them no format.
pub fn parse_freelist_trunk(
  database : DatabaseImage,
  page_number : UInt64,
) -> FreelistTrunk raise ParseError {
  database.validate_page_number(page_number)
  let usable = database.header.usable_page_size()
  guard usable >= 8 else {
    raise InvalidValue(
      database.page_offset(page_number),
      "freelist trunk usable size",
      usable.to_string(),
    )
  }
  let reader = database.page_reader(page_number, "freelist trunk page")
  let next_trunk_page = reader.read_u32_be()
  let raw_leaf_count = reader.read_u32_be()
  let capacity = usable / 4 - 2
  guard raw_leaf_count <= capacity.to_uint64() else {
    raise InvalidValue(
      database.page_offset(page_number) + 4,
      "freelist leaf count",
      raw_leaf_count.to_string() + " exceeds capacity " + capacity.to_string(),
    )
  }
  let leaf_count = raw_leaf_count.to_int()
  let leaf_pages : Array[UInt64] = []
  for index = 0; index < leaf_count; index = index + 1 {
    let leaf = reader.read_u32_be()
    guard leaf != 0UL else {
      raise InvalidValue(
        database.page_offset(page_number) + 8 + index * 4,
        "freelist leaf page",
        "page number is zero",
      )
    }
    guard leaf <= database.page_count else {
      raise InvalidPageNumber(leaf, database.page_count)
    }
    leaf_pages.push(leaf)
  }
  if next_trunk_page != 0UL {
    database.validate_page_number(next_trunk_page)
  }
  { page_number, next_trunk_page, leaf_count, leaf_pages }
}

///|
/// Walk every trunk and validate page references, loops, duplicates and the
/// freelist count declared by the 100-byte database header.
pub fn analyze_freelist(database : DatabaseImage) -> FreelistReport {
  let trunks : Array[FreelistTrunk] = []
  let trunk_pages : Array[UInt64] = []
  let leaf_pages : Array[UInt64] = []
  let diagnostics : Array[Diagnostic] = []
  let declared = database.header.total_freelist_pages
  let mut next = database.header.first_freelist_trunk_page
  if next == 0UL && declared == 0UL {
    return {
      trunks,
      trunk_pages,
      leaf_pages,
      diagnostics,
      declared_page_count: declared,
    }
  }
  if next == 0UL {
    diagnostics.push(
      Diagnostic::error(
        "FREELIST_ROOT_MISSING", "header declares freelist pages but has no first trunk page",
      ),
    )
  }
  while next != 0UL {
    if page_list_contains(trunk_pages, next) {
      diagnostics.push(
        Diagnostic::error(
          "FREELIST_TRUNK_LOOP",
          "freelist trunk chain contains a loop",
          page_number=next,
        ),
      )
      break
    }
    if page_list_contains(leaf_pages, next) {
      diagnostics.push(
        Diagnostic::error(
          "FREELIST_PAGE_REUSED",
          "a freelist trunk page was already referenced as a leaf",
          page_number=next,
        ),
      )
      break
    }
    let parsed : FreelistTrunk? = Some(parse_freelist_trunk(database, next)) catch {
      error => {
        diagnostics.push(
          Diagnostic::error(
            "FREELIST_TRUNK_INVALID",
            error.message(),
            page_number=next,
          ),
        )
        None
      }
    }
    guard parsed is Some(trunk) else { break }
    trunk_pages.push(next)
    trunks.push(trunk)
    for leaf in trunk.leaf_pages {
      if leaf == trunk.page_number ||
        page_list_contains(trunk_pages, leaf) ||
        page_list_contains(leaf_pages, leaf) {
        diagnostics.push(
          Diagnostic::error(
            "FREELIST_PAGE_REUSED",
            "freelist page is referenced more than once",
            page_number=leaf,
          ),
        )
      } else {
        leaf_pages.push(leaf)
      }
    }
    next = trunk.next_trunk_page
  }
  let observed = trunk_pages.length() + leaf_pages.length()
  if observed.to_uint64() != declared {
    diagnostics.push(
      Diagnostic::warning(
        "FREELIST_COUNT_MISMATCH",
        "header declares " +
        declared.to_string() +
        " freelist page(s), but traversal found " +
        observed.to_string(),
      ),
    )
  }
  {
    trunks,
    trunk_pages,
    leaf_pages,
    diagnostics,
    declared_page_count: declared,
  }
}