# Implementation Plan: MsgPack Package Database Indexes

**Date:** 2026-01-29
**Status:** Planned
**Target:** Coral v0.2

## Overview

Implement the MsgPack-based package database indexes that were planned as the key feature of Coral v0.2. Currently `src/core/pkgdb.reef` is entirely stubs that fall back to slow file scanning. This causes:

- `coral list` - O(N) TOML file reads
- `coral owner` - O(N*M) full scan of all packages' file lists (CRITICAL bottleneck)
- `coral info` - O(1) but requires TOML parsing

## Target Performance

| Command | Current | With MsgPack |
|---------|---------|--------------|
| `coral list` (100 pkgs) | ~500ms | ~10ms |
| `coral owner /usr/bin/vim` (50K files) | ~2000ms | ~1ms |
| `coral info vim` | ~50ms | ~5ms |

---

## File Format Specifications

### packages.db (MsgPack + Base64)

```
Structure:
{
  "version": 1,
  "generated": "2026-01-29T...",
  "package_count": N,
  "packages": [
    { "name": "vim", "version": "9.1", "release": 1,
      "description": "...", "installed_date": "...", "file_count": 423 },
    ...
  ]
}
```

### files.db (MsgPack + Base64)

```
Structure:
{
  "version": 1,
  "generated": "2026-01-29T...",
  "file_count": M,
  "files": {
    "usr/bin/vim": "vim",
    "usr/lib/libz.so": "zlib",
    ...
  }
}
```

**Note:** Base64 encoding required because Reef's `file.readFile()`/`file.writeFile()` work with strings.

---

## Implementation Phases

### Phase 1: Foundation (in pkgdb.reef)

Add new types:

```reef
type PackagesIndex = struct
    version: int
    generated: string
    package_count: int
    entries: [PkgIndexEntry]
    loaded: bool
end PackagesIndex

type FilesIndex = struct
    version: int
    generated: string
    file_count: int
    file_paths: [string]    // Sorted for binary search
    owners: [string]        // Parallel array - owner at same index
    loaded: bool
end FilesIndex
```

Add helper functions:
- `base64_encode(buf: [int], length: int): string`
- `base64_decode(encoded: string, buf: [int]): int`
- `estimate_packages_buffer_size(pkg_count: int): int`
- `estimate_files_buffer_size(file_count: int): int`

### Phase 2: Serialization

Implement MsgPack serialization:

```reef
fn serialize_packages_db(root: string): [int]
    // 1. Get list of installed packages from database module
    // 2. Allocate buffer based on count estimate
    // 3. Pack map header (4 keys: version, generated, package_count, packages)
    // 4. Pack array of package entries
    // Returns packed buffer
end serialize_packages_db

fn serialize_files_db(root: string): [int]
    // 1. Get all packages, collect all files with owners
    // 2. Sort file paths for binary search later
    // 3. Allocate buffer
    // 4. Pack map header + files map
    // Returns packed buffer
end serialize_files_db
```

Implement `rebuild_indexes_rooted()`:
```reef
fn rebuild_indexes_rooted(root: string): bool
    // 1. Serialize packages.db, base64 encode, write file
    // 2. Serialize files.db, base64 encode, write file
    // 3. Return success
end rebuild_indexes_rooted
```

### Phase 3: Deserialization

Implement loading functions:

```reef
fn load_packages_index(root: string): PackagesIndex
    // 1. Read base64 string from packages.db file
    // 2. Decode to binary buffer
    // 3. Unpack MsgPack structure
    // 4. Return populated PackagesIndex
end load_packages_index

fn load_files_index(root: string): FilesIndex
    // 1. Read base64 string from files.db file
    // 2. Decode to binary buffer
    // 3. Unpack MsgPack map into parallel arrays
    // 4. Return populated FilesIndex (already sorted from serialize)
end load_files_index

fn binary_search_file(index: FilesIndex, path: string): string
    // O(log N) binary search in sorted file_paths array
    // Return owner or empty string
end binary_search_file
```

### Phase 4: Update Public API

Replace stub implementations:

```reef
fn list_packages(names: [string], versions: [string], max_count: int): int
    let index = load_packages_index("")
    if not index.loaded
        return fallback_list_packages(names, versions, max_count)
    end if
    // Copy from index to arrays
end list_packages

fn find_file_owner(file_path: string): string
    let index = load_files_index("")
    if not index.loaded
        return database.find_owner(file_path)  // Fallback
    end if
    return binary_search_file(index, normalize_path(file_path))
end find_file_owner

fn get_indexed_package(name: string): PkgIndexEntry
    let index = load_packages_index("")
    if not index.loaded
        return fallback_get_indexed_package(name)
    end if
    // Search index for package by name
end get_indexed_package
```

Add rooted variants:
- `find_file_owner_rooted(file_path: string, root: string): string`

### Phase 5: Command Integration

**install.reef** - After registering package:
```reef
// Rebuild indexes after install
pkgdb.rebuild_indexes_rooted(root_path)
```

**remove.reef** - After unregistering package:
```reef
// Rebuild indexes after remove
pkgdb.rebuild_indexes_rooted(root_path)
```

**owner.reef** - Use indexed lookup:
```reef
// Change from database.find_owner() to pkgdb.find_file_owner()
```

---

## Files to Modify

| File | Changes |
|------|---------|
| `src/core/pkgdb.reef` | Main implementation - add types, serialization, deserialization, binary search |
| `src/commands/install.reef` | Call `rebuild_indexes_rooted()` after registration |
| `src/commands/remove.reef` | Call `rebuild_indexes_rooted()` after unregistration |
| `src/commands/owner.reef` | Use `pkgdb.find_file_owner()` instead of `database.find_owner()` |

---

## Key Implementation Details

### Base64 Encoding (required for file I/O)

Reef's `encoding.base64` module exists in reef-stdlib. Use:
```reef
import encoding.base64
let encoded = base64.base64_encode(binary_string)
let decoded = base64.base64_decode(encoded)
```

**Issue:** base64 module works with strings, but MsgPack produces `[int]` buffer. Need conversion helpers.

### MsgPack Usage (from reef-stdlib/encoding/msgpack.reef)

```reef
import encoding.msgpack

// Packing
let buf = msgpack.msgpack_alloc_buffer(size)
let pos = 0
pos = pos + msgpack.msgpack_pack_map_header(4, buf, pos)
pos = pos + msgpack.msgpack_pack_string("version", buf, pos)
pos = pos + msgpack.msgpack_pack_int(1, buf, pos)
// ... etc

// Unpacking
let map_len = msgpack.msgpack_unpack_map_len(buf, offset)
offset = offset + msgpack.msgpack_value_size(buf, offset)
// ... iterate through map entries
```

### Buffer to String Conversion

Need helper to convert `[int]` buffer to string for base64:
```reef
fn buffer_to_string(buf: [int], length: int): string
    mut result = ""
    mut i = 0
    while i < length
        result = result + chr(buf[i])
        i = i + 1
    end while
    return result
end buffer_to_string
```

---

## Verification

### Test Commands

```bash
# Initialize database (should create packages.db and files.db)
sudo coral --root /tmp/coral-chroot db init
ls -la /tmp/coral-chroot/var/lib/coral/db/

# Verify files exist
file /tmp/coral-chroot/var/lib/coral/db/packages.db
file /tmp/coral-chroot/var/lib/coral/db/files.db

# Build and install a test package
coral build core/zlib
sudo coral --root /tmp/coral-chroot install zlib

# Verify index updated
sudo coral --root /tmp/coral-chroot db status

# Test fast list
time sudo coral --root /tmp/coral-chroot list

# Test fast owner lookup
time sudo coral --root /tmp/coral-chroot owner /usr/lib/libz.so

# Test rebuild from scratch
sudo rm /tmp/coral-chroot/var/lib/coral/db/*.db
sudo coral --root /tmp/coral-chroot db rebuild
```

### Performance Validation

- `coral list` with 100 packages should complete in <50ms
- `coral owner` should complete in <10ms regardless of file count
- Index files should be created after install/remove

---

## Design Decisions

1. **Full Rebuild on Changes:** Each install/remove triggers a complete index rebuild. Simpler, always consistent, acceptable performance for typical package counts (<500 packages).

2. **Trust the Index:** Commands trust the index is correct. If indexes get out of sync (e.g., manual edits to installed/ directory), user runs `coral db rebuild` to fix.

3. **No Caching:** Reload index from disk on each command invocation. Keeps implementation simple and avoids stale memory issues.