/******************************************************************************
               __               ____                __
              / /   ___  ____ _/ __/_____________ _/ /__
             / /   / _ \/ __ `/ /_/ ___/ ___/ __ `/ / _ \
            / /___/  __/ /_/ / __(__  ) /__/ /_/ / /  __/
           /_____/\___/\__,_/_/ /____/\___/\__,_/_/\___/

   (C)opyright 2025, Leafscale, LLC -  https://www.leafscale.com

   Project: Zygaena
  Filename: pkgdb.reef
   Authors: Chris Tusa <chris.tusa@leafscale.com>
   License: <see LICENSE file included with this source code>
Description: MsgPack-based package database for fast lookups

    The package database provides fast indexed access to:
    - Installed packages (packages.db)
    - File ownership (files.db)

    Source of truth remains in /var/lib/coral/installed/<pkg>/pkg.toml
    These indexes can be rebuilt with 'coral db rebuild'

    Index files are stored as Base64-encoded MsgPack data for compatibility
    with Reef's string-based file I/O.

******************************************************************************/

module core.pkgdb

import types
import io.file
import io.dir
import io.path
import core.str
import core.database
import encoding.msgpack
import encoding.base64

export
    // Package index entry (for packages.db)
    type PkgIndexEntry

    // Initialize/ensure db directory exists
    fn init_db(): bool

    // Check if indexes exist and are valid
    fn indexes_exist(): bool

    // Get package count from index (fast)
    fn get_package_count(): int

    // List all packages from index (fast)
    fn list_packages(names: [string], versions: [string], max_count: int): int

    // Check if package is in index
    fn is_indexed(name: string): bool

    // Get package info from index
    fn get_indexed_package(name: string): PkgIndexEntry

    // Find file owner from index (fast)
    fn find_file_owner(file_path: string): string

    // Update index when package is installed
    fn index_add_package(name: string, version: string, release: int, description: string): bool

    // Update index when package is removed
    fn index_remove_package(name: string): bool

    // Add files to file index
    fn index_add_files(pkg_name: string, files: [string], file_count: int): bool

    // Remove files from file index
    fn index_remove_files(pkg_name: string): bool

    // Rebuild all indexes from installed packages (source of truth)
    fn rebuild_indexes(): bool

    // Get index statistics
    fn get_index_stats(): IndexStats

    // Root-aware versions for alternate root
    fn init_db_rooted(root: string): bool
    fn indexes_exist_rooted(root: string): bool
    fn rebuild_indexes_rooted(root: string): bool
    fn get_index_stats_rooted(root: string): IndexStats
    fn find_file_owner_rooted(file_path: string, root: string): string

    // Debug: dump files index contents
    fn dump_files_index_rooted(root: string, paths: [string], owners: [string], max_count: int): int

    type IndexStats
end export

// ============================================================================
// Types
// ============================================================================

type PkgIndexEntry = struct
    name: string
    version: string
    release: int
    description: string
    installed_date: string
    file_count: int
    found: bool
end PkgIndexEntry

type IndexStats = struct
    package_count: int
    file_count: int
    packages_db_size: int
    files_db_size: int
    last_updated: string
end IndexStats

// Loaded packages index (deserialized from packages.db)
type PackagesIndex = struct
    version: int
    generated: string
    package_count: int
    entries: [PkgIndexEntry]
    loaded: bool
end PackagesIndex

// Loaded files index (deserialized from files.db)
// Uses parallel arrays for binary search capability
type FilesIndex = struct
    version: int
    generated: string
    file_count: int
    file_paths: [string]    // Sorted alphabetically for binary search
    owners: [string]        // Package name at same index as file_paths
    loaded: bool
end FilesIndex

// ============================================================================
// Constants
// ============================================================================

const INDEX_VERSION: int = 1
const MAX_PACKAGES: int = 2048
const MAX_FILES: int = 131072  // 128K files max

// ============================================================================
// Path Constants
// ============================================================================

fn db_dir(): string
    return types.get_index_dir()
end db_dir

fn packages_db_path(): string
    return types.get_index_dir() + "/packages.db"
end packages_db_path

fn files_db_path(): string
    return types.get_index_dir() + "/files.db"
end files_db_path

// ============================================================================
// Buffer Size Estimation Helpers
// ============================================================================

// Estimate buffer size needed for packages.db
fn estimate_packages_buffer_size(pkg_count: int): int
    // Header overhead: ~100 bytes
    // Per package: ~200 bytes (name, version, description, dates)
    return 100 + (pkg_count * 200)
end estimate_packages_buffer_size

// Estimate buffer size needed for files.db
fn estimate_files_buffer_size(file_count: int): int
    // Header overhead: ~100 bytes
    // Per file: ~100 bytes (path + package name)
    return 100 + (file_count * 100)
end estimate_files_buffer_size

// Get current timestamp as string
fn get_timestamp(): string
    // Simple timestamp - just use a placeholder for now
    // In production would use sys.time module
    return "2026-01-29"
end get_timestamp

// ============================================================================
// Empty/Default Constructors
// ============================================================================

fn empty_packages_index(): PackagesIndex
    return PackagesIndex{
        version: 0,
        generated: "",
        package_count: 0,
        entries: new [PkgIndexEntry](MAX_PACKAGES),
        loaded: false
    }
end empty_packages_index

fn empty_files_index(): FilesIndex
    return FilesIndex{
        version: 0,
        generated: "",
        file_count: 0,
        file_paths: new [string](MAX_FILES),
        owners: new [string](MAX_FILES),
        loaded: false
    }
end empty_files_index

fn empty_pkg_entry(): PkgIndexEntry
    return PkgIndexEntry{
        name: "",
        version: "",
        release: 0,
        description: "",
        installed_date: "",
        file_count: 0,
        found: false
    }
end empty_pkg_entry

// Get just the header size for a map (not the entire map contents)
fn map_header_size(buf: [int], offset: int): int
    let b = buf[offset] & 255
    // Fixmap (0x80-0x8F): 1 byte header
    if (b & 0xF0) == 0x80
        return 1
    // map16 (0xDE): 3 byte header
    elif b == 0xDE
        return 3
    // map32 (0xDF): 5 byte header
    elif b == 0xDF
        return 5
    end if
    return 1  // Default
end map_header_size

// Get just the header size for an array (not the entire array contents)
fn array_header_size(buf: [int], offset: int): int
    let b = buf[offset] & 255
    // Fixarray (0x90-0x9F): 1 byte header
    if (b & 0xF0) == 0x90
        return 1
    // array16 (0xDC): 3 byte header
    elif b == 0xDC
        return 3
    // array32 (0xDD): 5 byte header
    elif b == 0xDD
        return 5
    end if
    return 1  // Default
end array_header_size

// ============================================================================
// MsgPack Deserialization
// ============================================================================

// Load packages index from disk
fn load_packages_index_rooted(root: string): PackagesIndex
    mut index = empty_packages_index()

    // Check if file exists
    let db_path = packages_db_path_rooted(root)
    if not file.fileExists(db_path)
        return index
    end if

    // Read base64-encoded content
    let encoded = file.readFile(db_path)
    if str.length(encoded) == 0
        return index
    end if

    // Decode base64 to buffer
    let buf_size = str.length(encoded)  // Decoded will be smaller
    mut buf: [int] = new [int](buf_size)
    let buf_len = base64.base64_decode_bytes(encoded, buf, buf_size)

    if buf_len == 0
        return index
    end if

    // Parse MsgPack structure
    mut offset = 0

    // Expect map header
    if not msgpack.msgpack_is_map(buf, offset)
        return index
    end if

    let map_len = msgpack.msgpack_unpack_map_len(buf, offset)
    offset = offset + map_header_size(buf, offset)

    // Iterate through map entries
    mut entry_idx = 0
    while entry_idx < map_len and offset < buf_len
        // Get key
        let key = msgpack.msgpack_unpack_string(buf, offset)
        offset = offset + msgpack.msgpack_value_size(buf, offset)

        if str.equals(key, "version")
            index.version = msgpack.msgpack_unpack_int(buf, offset)
            offset = offset + msgpack.msgpack_value_size(buf, offset)
        elif str.equals(key, "generated")
            index.generated = msgpack.msgpack_unpack_string(buf, offset)
            offset = offset + msgpack.msgpack_value_size(buf, offset)
        elif str.equals(key, "package_count")
            index.package_count = msgpack.msgpack_unpack_int(buf, offset)
            offset = offset + msgpack.msgpack_value_size(buf, offset)
        elif str.equals(key, "packages")
            // Parse packages array
            let arr_len = msgpack.msgpack_unpack_array_len(buf, offset)
            offset = offset + array_header_size(buf, offset)

            mut pkg_idx = 0
            while pkg_idx < arr_len and pkg_idx < MAX_PACKAGES and offset < buf_len
                // Each package is a map
                let pkg_map_len = msgpack.msgpack_unpack_map_len(buf, offset)
                offset = offset + map_header_size(buf, offset)

                mut entry = empty_pkg_entry()
                entry.found = true

                mut pkg_field = 0
                while pkg_field < pkg_map_len and offset < buf_len
                    let field_key = msgpack.msgpack_unpack_string(buf, offset)
                    offset = offset + msgpack.msgpack_value_size(buf, offset)

                    if str.equals(field_key, "name")
                        entry.name = msgpack.msgpack_unpack_string(buf, offset)
                    elif str.equals(field_key, "version")
                        entry.version = msgpack.msgpack_unpack_string(buf, offset)
                    elif str.equals(field_key, "release")
                        entry.release = msgpack.msgpack_unpack_int(buf, offset)
                    elif str.equals(field_key, "description")
                        entry.description = msgpack.msgpack_unpack_string(buf, offset)
                    elif str.equals(field_key, "installed_date")
                        entry.installed_date = msgpack.msgpack_unpack_string(buf, offset)
                    elif str.equals(field_key, "file_count")
                        entry.file_count = msgpack.msgpack_unpack_int(buf, offset)
                    end if
                    offset = offset + msgpack.msgpack_value_size(buf, offset)

                    pkg_field = pkg_field + 1
                end while

                index.entries[pkg_idx] = entry
                pkg_idx = pkg_idx + 1
            end while
        else
            // Skip unknown key's value
            offset = offset + msgpack.msgpack_value_size(buf, offset)
        end if

        entry_idx = entry_idx + 1
    end while

    index.loaded = true
    return index
end load_packages_index_rooted

// Load files index from disk
fn load_files_index_rooted(root: string): FilesIndex
    mut index = empty_files_index()

    // Check if file exists
    let db_path = files_db_path_rooted(root)
    if not file.fileExists(db_path)
        return index
    end if

    // Read base64-encoded content
    let encoded = file.readFile(db_path)
    let encoded_len = str.length(encoded)
    if encoded_len == 0
        return index
    end if

    // Decode base64 to buffer
    let buf_size = encoded_len  // Decoded will be smaller
    mut buf: [int] = new [int](buf_size)
    let buf_len = base64.base64_decode_bytes(encoded, buf, buf_size)

    if buf_len <= 0
        return index
    end if

    // Parse MsgPack structure
    mut offset = 0

    // Expect map header
    if not msgpack.msgpack_is_map(buf, offset)
        return index
    end if

    let map_len = msgpack.msgpack_unpack_map_len(buf, offset)
    offset = offset + map_header_size(buf, offset)

    // Iterate through map entries
    mut entry_idx = 0
    while entry_idx < map_len and offset < buf_len
        // Get key
        let key = msgpack.msgpack_unpack_string(buf, offset)
        offset = offset + msgpack.msgpack_value_size(buf, offset)

        if str.equals(key, "version")
            index.version = msgpack.msgpack_unpack_int(buf, offset)
            offset = offset + msgpack.msgpack_value_size(buf, offset)
        elif str.equals(key, "generated")
            index.generated = msgpack.msgpack_unpack_string(buf, offset)
            offset = offset + msgpack.msgpack_value_size(buf, offset)
        elif str.equals(key, "file_count")
            index.file_count = msgpack.msgpack_unpack_int(buf, offset)
            offset = offset + msgpack.msgpack_value_size(buf, offset)
        elif str.equals(key, "files")
            // Parse files map
            let files_map_len = msgpack.msgpack_unpack_map_len(buf, offset)
            offset = offset + map_header_size(buf, offset)

            mut file_idx = 0
            while file_idx < files_map_len and file_idx < MAX_FILES and offset < buf_len
                // Key is file path, value is owner
                let file_path = msgpack.msgpack_unpack_string(buf, offset)
                offset = offset + msgpack.msgpack_value_size(buf, offset)

                let owner = msgpack.msgpack_unpack_string(buf, offset)
                offset = offset + msgpack.msgpack_value_size(buf, offset)

                index.file_paths[file_idx] = file_path
                index.owners[file_idx] = owner
                file_idx = file_idx + 1
            end while

            index.file_count = file_idx
        else
            // Skip unknown key's value
            offset = offset + msgpack.msgpack_value_size(buf, offset)
        end if

        entry_idx = entry_idx + 1
    end while

    index.loaded = true
    return index
end load_files_index_rooted

// Binary search for file owner in sorted files index
// Returns package name or empty string if not found
fn binary_search_file_owner(index: FilesIndex, path: string): string
    if not index.loaded or index.file_count == 0
        return ""
    end if

    mut low = 0
    mut high = index.file_count - 1

    while low <= high
        let mid = (low + high) / 2
        let cmp = str.compare(path, index.file_paths[mid])

        if cmp == 0
            return index.owners[mid]
        elif cmp < 0
            high = mid - 1
        else
            low = mid + 1
        end if
    end while

    return ""  // Not found
end binary_search_file_owner

// Normalize file path for lookup (strip leading /)
fn normalize_path(path: string): string
    let len = str.length(path)
    if len > 0 and path[0] == '/'
        return str.substring(path, 1, len - 1)
    end if
    return path
end normalize_path

// Linear search fallback for file owner (when binary search fails)
fn linear_search_file_owner(index: FilesIndex, path: string): string
    if not index.loaded or index.file_count == 0
        return ""
    end if

    mut i = 0
    while i < index.file_count
        if str.equals(path, index.file_paths[i])
            return index.owners[i]
        end if
        i = i + 1
    end while

    return ""
end linear_search_file_owner

// ============================================================================
// Initialization
// ============================================================================

fn init_db(): bool
    let db = db_dir()
    if not dir.dir_exists(db)
        return dir.create_dir_all(db)
    end if
    return true
end init_db

fn indexes_exist(): bool
    return file.fileExists(packages_db_path()) and file.fileExists(files_db_path())
end indexes_exist

// ============================================================================
// Package Index Operations - Uses MsgPack index with fallback
// ============================================================================

fn get_package_count(): int
    // Try index first
    let index = load_packages_index_rooted("")
    if index.loaded
        return index.package_count
    end if

    // Fall back to database scan
    mut names: [string] = new [string](1024)
    return database.list_installed(names, 1024)
end get_package_count

fn list_packages(names: [string], versions: [string], max_count: int): int
    // Try index first
    let index = load_packages_index_rooted("")
    if index.loaded
        mut count = 0
        while count < index.package_count and count < max_count
            names[count] = index.entries[count].name
            versions[count] = index.entries[count].version
            count = count + 1
        end while
        return count
    end if

    // Fall back to database scan
    let count = database.list_installed(names, max_count)

    // Fill in versions
    mut i = 0
    while i < count
        let pkg = database.get_installed(names[i])
        versions[i] = pkg.info.version
        i = i + 1
    end while

    return count
end list_packages

fn is_indexed(name: string): bool
    // Try index first
    let index = load_packages_index_rooted("")
    if index.loaded
        mut i = 0
        while i < index.package_count
            if str.equals(index.entries[i].name, name)
                return true
            end if
            i = i + 1
        end while
        return false
    end if

    // Fall back to database check
    return database.is_installed(name)
end is_indexed

fn get_indexed_package(name: string): PkgIndexEntry
    // Try index first
    let index = load_packages_index_rooted("")
    if index.loaded
        mut i = 0
        while i < index.package_count
            if str.equals(index.entries[i].name, name)
                return index.entries[i]
            end if
            i = i + 1
        end while
        return empty_pkg_entry()
    end if

    // Fall back to database
    mut entry = empty_pkg_entry()

    if not database.is_installed(name)
        return entry
    end if

    let pkg = database.get_installed(name)
    entry.name = pkg.info.name
    entry.version = pkg.info.version
    entry.release = pkg.info.release
    entry.description = pkg.info.description
    entry.installed_date = pkg.install_date
    entry.file_count = pkg.files_count
    entry.found = true

    return entry
end get_indexed_package

// ============================================================================
// File Index Operations - Uses MsgPack index with fallback
// ============================================================================

fn find_file_owner(file_path: string): string
    return find_file_owner_rooted(file_path, "")
end find_file_owner

fn find_file_owner_rooted(file_path: string, root: string): string
    // Try index first (O(log N) binary search)
    let index = load_files_index_rooted(root)
    if index.loaded
        let normalized = normalize_path(file_path)
        let owner = binary_search_file_owner(index, normalized)
        if str.length(owner) > 0
            return owner
        end if
        // Binary search failed - try linear search as fallback
        // This helps diagnose if the index isn't sorted correctly
        let linear_owner = linear_search_file_owner(index, normalized)
        if str.length(linear_owner) > 0
            return linear_owner
        end if
        // File not in index - either not owned or index out of date
        return ""
    end if

    // Fall back to database scan (O(N*M))
    if str.length(root) > 0
        return database.find_owner_rooted(file_path, root)
    end if
    return database.find_owner(file_path)
end find_file_owner_rooted

// ============================================================================
// Index Modification (stub - no-op for now)
// ============================================================================

fn index_add_package(name: string, version: string, release: int, description: string): bool
    // Stub - no indexing yet
    return true
end index_add_package

fn index_remove_package(name: string): bool
    // Stub - no indexing yet
    return true
end index_remove_package

fn index_add_files(pkg_name: string, files: [string], file_count: int): bool
    // Stub - no indexing yet
    return true
end index_add_files

fn index_remove_files(pkg_name: string): bool
    // Stub - triggers full rebuild
    return true
end index_remove_files

// ============================================================================
// MsgPack Serialization
// ============================================================================

// Serialize packages index to MsgPack format
// Returns buffer and sets length via out parameter simulation (length stored at buf[0])
fn serialize_packages_db_rooted(root: string, buf: [int], max_size: int): int
    // Get list of installed packages
    mut names: [string] = new [string](MAX_PACKAGES)
    let pkg_count = database.list_installed_rooted(names, MAX_PACKAGES, root)

    mut pos = 0

    // Pack map header (4 keys: version, generated, package_count, packages)
    pos = pos + msgpack.msgpack_pack_map_header(4, buf, pos)

    // Pack "version" -> INDEX_VERSION
    pos = pos + msgpack.msgpack_pack_string("version", buf, pos)
    pos = pos + msgpack.msgpack_pack_int(INDEX_VERSION, buf, pos)

    // Pack "generated" -> timestamp
    pos = pos + msgpack.msgpack_pack_string("generated", buf, pos)
    pos = pos + msgpack.msgpack_pack_string(get_timestamp(), buf, pos)

    // Pack "package_count" -> count
    pos = pos + msgpack.msgpack_pack_string("package_count", buf, pos)
    pos = pos + msgpack.msgpack_pack_int(pkg_count, buf, pos)

    // Pack "packages" -> array of package entries
    pos = pos + msgpack.msgpack_pack_string("packages", buf, pos)
    pos = pos + msgpack.msgpack_pack_array_header(pkg_count, buf, pos)

    // Pack each package entry
    mut i = 0
    while i < pkg_count and pos < max_size - 1000
        let pkg = database.get_installed_rooted(names[i], root)

        // Each package is a map with 6 keys
        pos = pos + msgpack.msgpack_pack_map_header(6, buf, pos)

        // name
        pos = pos + msgpack.msgpack_pack_string("name", buf, pos)
        pos = pos + msgpack.msgpack_pack_string(pkg.info.name, buf, pos)

        // version
        pos = pos + msgpack.msgpack_pack_string("version", buf, pos)
        pos = pos + msgpack.msgpack_pack_string(pkg.info.version, buf, pos)

        // release
        pos = pos + msgpack.msgpack_pack_string("release", buf, pos)
        pos = pos + msgpack.msgpack_pack_int(pkg.info.release, buf, pos)

        // description
        pos = pos + msgpack.msgpack_pack_string("description", buf, pos)
        pos = pos + msgpack.msgpack_pack_string(pkg.info.description, buf, pos)

        // installed_date
        pos = pos + msgpack.msgpack_pack_string("installed_date", buf, pos)
        pos = pos + msgpack.msgpack_pack_string(pkg.install_date, buf, pos)

        // file_count
        pos = pos + msgpack.msgpack_pack_string("file_count", buf, pos)
        pos = pos + msgpack.msgpack_pack_int(pkg.files_count, buf, pos)

        i = i + 1
    end while

    return pos
end serialize_packages_db_rooted

// Count total installed files across all packages (cheap — no file content read)
fn count_total_files_rooted(root: string): int
    mut pkg_names: [string] = new [string](MAX_PACKAGES)
    let pkg_count = database.list_installed_rooted(pkg_names, MAX_PACKAGES, root)

    mut total = 0
    mut i = 0
    while i < pkg_count
        mut pkg_files: [string] = new [string](8192)
        let file_count = database.get_files_rooted(pkg_names[i], pkg_files, 8192, root)
        total = total + file_count
        i = i + 1
    end while

    return total
end count_total_files_rooted

// Serialize files index to MsgPack format
// Creates a map of file_path -> package_name for fast ownership lookup
fn serialize_files_db_rooted(root: string, buf: [int], max_size: int, alloc_size: int): int
    // Get all installed packages
    mut pkg_names: [string] = new [string](MAX_PACKAGES)
    let pkg_count = database.list_installed_rooted(pkg_names, MAX_PACKAGES, root)

    // Collect all files with their owners — sized to actual count + margin
    mut all_files: [string] = new [string](alloc_size)
    mut all_owners: [string] = new [string](alloc_size)
    mut total_files = 0

    mut i = 0
    while i < pkg_count and total_files < alloc_size - 256
        mut pkg_files: [string] = new [string](8192)
        let file_count = database.get_files_rooted(pkg_names[i], pkg_files, 8192, root)

        mut j = 0
        while j < file_count and total_files < alloc_size
            all_files[total_files] = pkg_files[j]
            all_owners[total_files] = pkg_names[i]
            total_files = total_files + 1
            j = j + 1
        end while

        i = i + 1
    end while

    // Sort files alphabetically for binary search (simple bubble sort for now)
    sort_file_index(all_files, all_owners, total_files)

    mut pos = 0

    // Pack map header (4 keys: version, generated, file_count, files)
    pos = pos + msgpack.msgpack_pack_map_header(4, buf, pos)

    // Pack "version" -> INDEX_VERSION
    pos = pos + msgpack.msgpack_pack_string("version", buf, pos)
    pos = pos + msgpack.msgpack_pack_int(INDEX_VERSION, buf, pos)

    // Pack "generated" -> timestamp
    pos = pos + msgpack.msgpack_pack_string("generated", buf, pos)
    pos = pos + msgpack.msgpack_pack_string(get_timestamp(), buf, pos)

    // Pack "file_count" -> count
    pos = pos + msgpack.msgpack_pack_string("file_count", buf, pos)
    pos = pos + msgpack.msgpack_pack_int(total_files, buf, pos)

    // Pack "files" -> map of path -> owner
    pos = pos + msgpack.msgpack_pack_string("files", buf, pos)
    pos = pos + msgpack.msgpack_pack_map_header(total_files, buf, pos)

    // Pack each file -> owner pair
    i = 0
    while i < total_files and pos < max_size - 500
        pos = pos + msgpack.msgpack_pack_string(all_files[i], buf, pos)
        pos = pos + msgpack.msgpack_pack_string(all_owners[i], buf, pos)
        i = i + 1
    end while

    return pos
end serialize_files_db_rooted

// Sort parallel arrays of files and owners alphabetically by file path
// Uses merge sort for O(n log n) performance on large file counts
proc sort_file_index(files: [string], owners: [string], count: int)
    if count <= 1
        return
    end if

    // Allocate temporary arrays for merge operations
    mut tmp_files: [string] = new [string](count)
    mut tmp_owners: [string] = new [string](count)

    merge_sort(files, owners, tmp_files, tmp_owners, 0, count - 1)
end sort_file_index

proc merge_sort(files: [string], owners: [string], tmp_files: [string], tmp_owners: [string], left: int, right: int)
    if left >= right
        return
    end if

    let mid = left + (right - left) / 2
    merge_sort(files, owners, tmp_files, tmp_owners, left, mid)
    merge_sort(files, owners, tmp_files, tmp_owners, mid + 1, right)
    merge(files, owners, tmp_files, tmp_owners, left, mid, right)
end merge_sort

proc merge(files: [string], owners: [string], tmp_files: [string], tmp_owners: [string], left: int, mid: int, right: int)
    // Copy both halves into temp arrays
    mut i = left
    while i <= right
        tmp_files[i] = files[i]
        tmp_owners[i] = owners[i]
        i = i + 1
    end while

    // Merge back from temp into original
    mut l = left
    mut r = mid + 1
    mut k = left

    while l <= mid and r <= right
        if str.compare(tmp_files[l], tmp_files[r]) <= 0
            files[k] = tmp_files[l]
            owners[k] = tmp_owners[l]
            l = l + 1
        else
            files[k] = tmp_files[r]
            owners[k] = tmp_owners[r]
            r = r + 1
        end if
        k = k + 1
    end while

    // Copy remaining left half
    while l <= mid
        files[k] = tmp_files[l]
        owners[k] = tmp_owners[l]
        l = l + 1
        k = k + 1
    end while

    // Right half remaining elements are already in place
end merge

// ============================================================================
// Index Rebuild
// ============================================================================

fn rebuild_indexes(): bool
    return rebuild_indexes_rooted("")
end rebuild_indexes

// ============================================================================
// Index Statistics
// ============================================================================

fn get_index_stats(): IndexStats
    mut stats = IndexStats{
        package_count: 0,
        file_count: 0,
        packages_db_size: 0,
        files_db_size: 0,
        last_updated: ""
    }

    // Get package count from source of truth
    mut names: [string] = new [string](1024)
    stats.package_count = database.list_installed(names, 1024)

    // Count files across all packages
    mut i = 0
    while i < stats.package_count
        mut files: [string] = new [string](4096)
        let file_count = database.get_files(names[i], files, 4096)
        stats.file_count = stats.file_count + file_count
        i = i + 1
    end while

    return stats
end get_index_stats

// ============================================================================
// Root-aware versions for alternate root
// ============================================================================

fn db_dir_rooted(root: string): string
    if str.length(root) == 0
        return types.get_index_dir()
    end if
    return root + types.get_index_dir()
end db_dir_rooted

fn packages_db_path_rooted(root: string): string
    return db_dir_rooted(root) + "/packages.db"
end packages_db_path_rooted

fn files_db_path_rooted(root: string): string
    return db_dir_rooted(root) + "/files.db"
end files_db_path_rooted

fn init_db_rooted(root: string): bool
    let db = db_dir_rooted(root)
    if not dir.dir_exists(db)
        return dir.create_dir_all(db)
    end if
    return true
end init_db_rooted

fn indexes_exist_rooted(root: string): bool
    return file.fileExists(packages_db_path_rooted(root)) and file.fileExists(files_db_path_rooted(root))
end indexes_exist_rooted

fn rebuild_indexes_rooted(root: string): bool
    if not init_db_rooted(root)
        return false
    end if

    // Serialize packages.db
    let pkg_buf_size = estimate_packages_buffer_size(MAX_PACKAGES)
    mut pkg_buf: [int] = new [int](pkg_buf_size)
    let pkg_len = serialize_packages_db_rooted(root, pkg_buf, pkg_buf_size)

    if pkg_len > 0
        // Encode to base64 and write
        let pkg_encoded = base64.base64_encode_bytes(pkg_buf, pkg_len)
        if not file.writeFile(packages_db_path_rooted(root), pkg_encoded)
            return false
        end if
    end if

    // Serialize files.db — count actual files first to avoid massive over-allocation
    let actual_file_count = count_total_files_rooted(root)
    let alloc_size = actual_file_count + 1024
    let files_buf_size = estimate_files_buffer_size(alloc_size)
    mut files_buf: [int] = new [int](files_buf_size)
    let files_len = serialize_files_db_rooted(root, files_buf, files_buf_size, alloc_size)

    if files_len > 0
        // Encode to base64 and write
        let files_encoded = base64.base64_encode_bytes(files_buf, files_len)
        if not file.writeFile(files_db_path_rooted(root), files_encoded)
            return false
        end if
    end if

    return true
end rebuild_indexes_rooted

fn get_index_stats_rooted(root: string): IndexStats
    mut stats = IndexStats{
        package_count: 0,
        file_count: 0,
        packages_db_size: 0,
        files_db_size: 0,
        last_updated: ""
    }

    // Get package count from source of truth in alternate root
    mut names: [string] = new [string](1024)
    stats.package_count = database.list_installed_rooted(names, 1024, root)

    // Count files across all packages
    mut i = 0
    while i < stats.package_count
        mut files: [string] = new [string](4096)
        let file_count = database.get_files_rooted(names[i], files, 4096, root)
        stats.file_count = stats.file_count + file_count
        i = i + 1
    end while

    return stats
end get_index_stats_rooted

// Debug: dump files index contents to arrays
fn dump_files_index_rooted(root: string, paths: [string], owners: [string], max_count: int): int
    let index = load_files_index_rooted(root)
    if not index.loaded
        return 0
    end if

    mut count = 0
    while count < index.file_count and count < max_count
        paths[count] = index.file_paths[count]
        owners[count] = index.owners[count]
        count = count + 1
    end while

    return count
end dump_files_index_rooted

end module