mtree.reef - zygaena/coral

root / src / util / mtree.reef
mtree.reef Reef 612 lines 17.8 KB
/******************************************************************************
               __               ____                __
              / /   ___  ____ _/ __/_____________ _/ /__
             / /   / _ \/ __ `/ /_/ ___/ ___/ __ `/ / _ \
            / /___/  __/ /_/ / __(__  ) /__/ /_/ / /  __/
           /_____/\___/\__,_/_/ /____/\___/\__,_/_/\___/

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

   Project: Zygaena
  Filename: mtree.reef
   Authors: Chris Tusa <chris.tusa@leafscale.com>
   License: <see LICENSE file included with this source code>
Description: mtree-format manifest for package file inventory

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

module util.mtree

import io.file
import io.dir
import io.path
import core.str
import fs.stat
import fs.link
import crypto.sha256 as sha
import util.checksum
import text.stringbuilder as sb
import core.result as res
import core.option as opt

export
    // Manifest entry representing a single file, directory, or symlink
    type ManifestEntry

    // Parse an mtree manifest string into an array of entries
    // Returns the number of entries parsed
    fn parse_manifest(content: string, entries: [ManifestEntry], max_entries: int): int

    // Generate an mtree manifest string from a package staging directory
    fn generate_manifest(pkg_dir: string): string

    // Accessors
    fn entry_path(entry: ManifestEntry): string
    fn entry_type(entry: ManifestEntry): string
    fn entry_mode(entry: ManifestEntry): int
    fn entry_uname(entry: ManifestEntry): string
    fn entry_gname(entry: ManifestEntry): string
    fn entry_sha256(entry: ManifestEntry): string
    fn entry_link(entry: ManifestEntry): string

    // Format a ManifestEntry as an mtree line
    fn format_entry(entry: ManifestEntry): string

    // Uid/gid name resolution helpers
    fn uid_to_name(uid: int): string
    fn gid_to_name(gid: int): string
    fn name_to_uid(name: string): int
    fn name_to_gid(name: string): int
end export

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

type ManifestEntry = struct
    epath: string       // Relative path (e.g., ./usr/bin/foo)
    etype: string       // "file", "dir", or "link"
    mode: int           // Permission bits as integer (e.g., 0755 = 493)
    uname: string       // Owner user name
    gname: string       // Owner group name
    sha256: string      // SHA256 checksum (files only)
    link_target: string // Symlink target (links only)
end ManifestEntry

// ============================================================================
// Accessors
// ============================================================================

fn entry_path(entry: ManifestEntry): string
    return entry.epath
end entry_path

fn entry_type(entry: ManifestEntry): string
    return entry.etype
end entry_type

fn entry_mode(entry: ManifestEntry): int
    return entry.mode
end entry_mode

fn entry_uname(entry: ManifestEntry): string
    return entry.uname
end entry_uname

fn entry_gname(entry: ManifestEntry): string
    return entry.gname
end entry_gname

fn entry_sha256(entry: ManifestEntry): string
    return entry.sha256
end entry_sha256

fn entry_link(entry: ManifestEntry): string
    return entry.link_target
end entry_link

// ============================================================================
// Parser
// ============================================================================

// Parse an mtree manifest string into entries.
// Format per line: ./path type=T mode=OOOO uname=U gname=G [sha256=H] [link=T]
// Lines starting with # are comments. Empty lines are skipped.
fn parse_manifest(content: string, entries: [ManifestEntry], max_entries: int): int
    if str.length(content) == 0
        return 0
    end if

    // Split into lines
    mut lines: [string] = new [string](max_entries + 64)
    let line_count = str.split(content, '\n', lines, max_entries + 64)

    mut count = 0
    mut i = 0
    while i < line_count and count < max_entries
        let line = str.trim_ws(lines[i])
        let line_len = str.length(line)

        // Skip empty lines and comments
        if line_len == 0
            i = i + 1
            continue
        end if
        if line[0] == '#'
            i = i + 1
            continue
        end if

        // Parse the line: first token is path, rest are key=value
        let entry = parse_entry_line(line)
        if str.length(entry.epath) > 0
            entries[count] = entry
            count = count + 1
        end if

        i = i + 1
    end while

    return count
end parse_manifest

// Parse a single mtree line into a ManifestEntry
fn parse_entry_line(line: string): ManifestEntry
    mut entry = ManifestEntry{
        epath: "",
        etype: "",
        mode: 0,
        uname: "root",
        gname: "root",
        sha256: "",
        link_target: ""
    }

    // Split line by spaces
    mut tokens: [string] = new [string](16)
    let token_count = str.split(line, ' ', tokens, 16)
    if token_count == 0
        return entry
    end if

    // First token is always the path
    entry.epath = tokens[0]

    // Remaining tokens are key=value pairs
    mut t = 1
    while t < token_count
        let token = tokens[t]
        let eq_pos = str.index_of_char(token, '=')
        if eq_pos > 0
            let key = str.substring(token, 0, eq_pos)
            let val = str.substring(token, eq_pos + 1, str.length(token) - eq_pos - 1)

            if str.equals(key, "type")
                entry.etype = val
            elif str.equals(key, "mode")
                entry.mode = octal_to_int(val)
            elif str.equals(key, "uname")
                entry.uname = val
            elif str.equals(key, "gname")
                entry.gname = val
            elif str.equals(key, "sha256")
                entry.sha256 = val
            elif str.equals(key, "link")
                entry.link_target = val
            end if
        end if
        t = t + 1
    end while

    return entry
end parse_entry_line

// ============================================================================
// Generator
// ============================================================================

// Generate an mtree manifest for all files in a package staging directory.
// Walks the directory tree, collects entries, sorts them, and returns the
// formatted manifest string.
fn generate_manifest(pkg_dir: string): string
    // Collect entries by walking the directory tree
    mut entries: [ManifestEntry] = new [ManifestEntry](8192)
    let count = walk_directory(pkg_dir, pkg_dir, entries, 0, 8192)

    if count == 0
        return ""
    end if

    // Sort entries by path (simple insertion sort — fine for package file counts)
    sort_entries(entries, count)

    // Build the output string using StringBuilder to avoid O(n²) heap
    // fragmentation from repeated string concatenation (Reef BUG-027)
    let builder = sb.sb_new()
    sb.sb_append(builder, "#mtree\n")
    mut i = 0
    while i < count
        sb.sb_append(builder, format_entry(entries[i]))
        sb.sb_append(builder, "\n")
        i = i + 1
    end while

    return sb.sb_build(builder)
end generate_manifest

// Recursively walk a directory, collecting ManifestEntry records.
// base_dir is the package root (for computing relative paths).
// current_dir is the directory being walked.
// Returns total number of entries added (starting from offset).
fn walk_directory(base_dir: string, current_dir: string, entries: [ManifestEntry], offset: int, max: int): int
    mut count = offset

    // Add the current directory itself (unless it's the base)
    if not str.equals(current_dir, base_dir) and count < max
        let rel = get_relative_path(base_dir, current_dir)
        if not is_metadata_path(rel)
            let mode = res.unwrap_or(stat.file_mode(current_dir), 0)
            let uid = res.unwrap_or(stat.file_uid(current_dir), 0)
            let gid = res.unwrap_or(stat.file_gid(current_dir), 0)
            entries[count] = ManifestEntry{
                epath: "./" + rel,
                etype: "dir",
                mode: mode,
                uname: uid_to_name(uid),
                gname: gid_to_name(gid),
                sha256: "",
                link_target: ""
            }
            count = count + 1
        end if
    end if

    // List directory contents
    let dir_entries = res.unwrap_or(dir.list_dir(current_dir), new [string](0))
    let entry_count = dir_entries.length()

    mut i = 0
    while i < entry_count and count < max
        let name = dir_entries[i]

        // Skip . and .. to prevent infinite recursion
        if str.equals(name, ".") or str.equals(name, "..")
            i = i + 1
            continue
        end if

        let full_path = path.join_path(current_dir, name)
        let rel = get_relative_path(base_dir, full_path)

        // Skip metadata files and directories
        if is_metadata_path(rel)
            i = i + 1
            continue
        end if

        // Check type: symlink first (symlinks to dirs would match is_directory)
        if stat.is_symlink(full_path)
            let target = res.unwrap_or(link.readlink(full_path), "")
            let uid = res.unwrap_or(stat.file_uid(current_dir), 0)
            let gid = res.unwrap_or(stat.file_gid(current_dir), 0)
            entries[count] = ManifestEntry{
                epath: "./" + rel,
                etype: "link",
                mode: 0,
                uname: uid_to_name(uid),
                gname: gid_to_name(gid),
                sha256: "",
                link_target: target
            }
            count = count + 1
        elif stat.is_directory(full_path)
            // Recurse into subdirectory
            count = walk_directory(base_dir, full_path, entries, count, max)
        elif stat.is_file(full_path)
            let mode = res.unwrap_or(stat.file_mode(full_path), 0)
            let uid = res.unwrap_or(stat.file_uid(full_path), 0)
            let gid = res.unwrap_or(stat.file_gid(full_path), 0)
            let hash = checksum.sha256_file(full_path)
            entries[count] = ManifestEntry{
                epath: "./" + rel,
                etype: "file",
                mode: mode,
                uname: uid_to_name(uid),
                gname: gid_to_name(gid),
                sha256: hash,
                link_target: ""
            }
            count = count + 1
        end if

        i = i + 1
    end while

    return count
end walk_directory

// Check if a relative path is a package metadata file/directory
fn is_metadata_path(rel: string): bool
    if str.equals(rel, ".PKGINFO") or str.equals(rel, ".MANIFEST")
        return true
    end if
    if str.equals(rel, ".FOOTPRINT") or str.equals(rel, ".CONFIG")
        return true
    end if
    if str.equals(rel, ".SCRIPTS")
        return true
    end if
    if str.starts_with(rel, ".SCRIPTS/")
        return true
    end if
    return false
end is_metadata_path

// Get relative path by stripping the base directory prefix
fn get_relative_path(base: string, full: string): string
    let base_len = str.length(base)
    let full_len = str.length(full)

    if full_len <= base_len
        return ""
    end if

    // Skip the base prefix and the trailing /
    mut start = base_len
    if start < full_len and full[start] == '/'
        start = start + 1
    end if

    return str.substring(full, start, full_len - start)
end get_relative_path

// ============================================================================
// Formatting
// ============================================================================

// Format a ManifestEntry as a single mtree line
fn format_entry(entry: ManifestEntry): string
    mut line = entry.epath + " type=" + entry.etype

    if str.equals(entry.etype, "file") or str.equals(entry.etype, "dir")
        line = line + " mode=" + int_to_octal(entry.mode)
    end if

    line = line + " uname=" + entry.uname
    line = line + " gname=" + entry.gname

    if str.equals(entry.etype, "file") and str.length(entry.sha256) > 0
        line = line + " sha256=" + entry.sha256
    end if

    if str.equals(entry.etype, "link") and str.length(entry.link_target) > 0
        line = line + " link=" + entry.link_target
    end if

    return line
end format_entry

// ============================================================================
// Sorting
// ============================================================================

// Insertion sort entries by path (lexicographic).
// Package file counts are typically <1000, so insertion sort is adequate.
proc sort_entries(entries: [ManifestEntry], count: int)
    mut i = 1
    while i < count
        let key_entry = entries[i]
        let key_path = entries[i].epath
        mut j = i - 1
        while j >= 0 and str.compare(entries[j].epath, key_path) > 0
            entries[j + 1] = entries[j]
            j = j - 1
        end while
        entries[j + 1] = key_entry
        i = i + 1
    end while
end sort_entries

// ============================================================================
// Numeric Conversion Helpers
// ============================================================================

// Convert an octal string (e.g., "0755", "4755") to an integer
fn octal_to_int(s: string): int
    let slen = str.length(s)
    if slen == 0
        return 0
    end if

    mut result = 0
    mut i = 0
    while i < slen
        let c = s[i]
        if c >= '0' and c <= '7'
            result = result * 8 + (c - '0')
        end if
        i = i + 1
    end while

    return result
end octal_to_int

// Convert an integer to a 4-digit octal string (e.g., 493 -> "0755")
fn int_to_octal(n: int): string
    if n == 0
        return "0000"
    end if

    mut value = n
    mut digits: [int] = new [int](16)
    mut count = 0

    while value > 0 and count < 16
        digits[count] = value - (value / 8 * 8)
        value = value / 8
        count = count + 1
    end while

    // Pad to 4 digits minimum
    while count < 4
        digits[count] = 0
        count = count + 1
    end while

    // Build string in reverse (most significant first)
    mut result = ""
    mut i = count - 1
    while i >= 0
        result = result + digit_char(digits[i])
        i = i - 1
    end while

    return result
end int_to_octal

// Single digit to string character
fn digit_char(d: int): string
    if d == 0
        return "0"
    elif d == 1
        return "1"
    elif d == 2
        return "2"
    elif d == 3
        return "3"
    elif d == 4
        return "4"
    elif d == 5
        return "5"
    elif d == 6
        return "6"
    elif d == 7
        return "7"
    end if
    return "0"
end digit_char

// Convert int to decimal string (local helper to avoid circular imports)
fn int_to_str(n: int): string
    if n == 0
        return "0"
    end if

    mut negative = false
    mut value = n
    if n < 0
        negative = true
        value = 0 - n
    end if

    mut result = ""
    while value > 0
        let digit = value - (value / 10 * 10)
        result = str.concat(digit_char(digit), result)
        value = value / 10
    end while

    if negative
        result = str.concat("-", result)
    end if

    return result
end int_to_str

// ============================================================================
// UID/GID Name Resolution
// ============================================================================

// Resolve a numeric uid to a username.
// Uses POSIX getpwuid() via Reef's fs.stat.uid_name() — zero heap allocation.
fn uid_to_name(uid: int): string
    return opt.unwrap_or(stat.uid_name(uid), "")
end uid_to_name

// Resolve a numeric gid to a group name.
// Uses POSIX getgrgid() via Reef's fs.stat.gid_name() — zero heap allocation.
fn gid_to_name(gid: int): string
    return opt.unwrap_or(stat.gid_name(gid), "")
end gid_to_name

// Resolve a username to numeric uid by reading /etc/passwd.
// Only used during verify/install (low call count), not the hot manifest walk.
fn name_to_uid(name: string): int
    if str.equals(name, "root")
        return 0
    end if

    let content = res.unwrap_or(file.readFile("/etc/passwd"), "")
    if str.length(content) == 0
        return 0
    end if

    mut lines: [string] = new [string](256)
    let line_count = str.split(content, '\n', lines, 256)

    mut i = 0
    while i < line_count
        let line = lines[i]
        if str.length(line) > 0
            mut fields: [string] = new [string](8)
            let field_count = str.split(line, ':', fields, 8)
            if field_count >= 3 and str.equals(fields[0], name)
                return str_to_int(fields[2])
            end if
        end if
        i = i + 1
    end while
    return 0
end name_to_uid

// Resolve a group name to numeric gid by reading /etc/group.
// Only used during verify/install (low call count), not the hot manifest walk.
fn name_to_gid(name: string): int
    if str.equals(name, "root")
        return 0
    end if

    let content = res.unwrap_or(file.readFile("/etc/group"), "")
    if str.length(content) == 0
        return 0
    end if

    mut lines: [string] = new [string](256)
    let line_count = str.split(content, '\n', lines, 256)

    mut i = 0
    while i < line_count
        let line = lines[i]
        if str.length(line) > 0
            mut fields: [string] = new [string](8)
            let field_count = str.split(line, ':', fields, 8)
            if field_count >= 3 and str.equals(fields[0], name)
                return str_to_int(fields[2])
            end if
        end if
        i = i + 1
    end while
    return 0
end name_to_gid

// Simple string-to-int conversion
fn str_to_int(s: string): int
    let slen = str.length(s)
    if slen == 0
        return 0
    end if

    mut result = 0
    mut i = 0
    while i < slen
        let c = s[i]
        if c >= '0' and c <= '9'
            result = result * 10 + (c - '0')
        end if
        i = i + 1
    end while
    return result
end str_to_int

end module