Luce packages
LuceLuce BaseLuciaOS

dymokomi/luc

Source of release 0.24.0

0.24.0 / src / pack_check.lucb

## Full-pack graph checks before publishing downloaded source objects: every object a
## commit, tree or tag names is in the pack with the kind it is named as, and no object is
## there twice. An index over the objects' IDs keeps the checks linear in the pack, so a
## large release (thousands of files) costs what its size does.
import memory
from luce_git import git
from luce_crypto import native as crypto_native

let invalid: ErrorCode = ErrorCode.package(3)

## The pack's objects by ID: open addressing over twice as many slots as objects, each
## slot an object's index plus one, 0 when free.
struct Index:
    var pack: git.Pack*
    var slots: u32[]

    static func over(pack: git.Pack*) -> Index!:
        var size: usize = 16
        while size < pack.items.length * 2:
            size *= 2
        var slots = try new u32[size] --- in memory.heap
        for i in 0..<size: slots[i] = 0
        var index = Index(pack = pack, slots = slots)
        for i in 0..<pack.items.length:
            var slot = index.start(pack.items[i].id)
            while index.slots[slot] != 0:
                if crypto_native.equal(pack.items[(usize)index.slots[slot] - 1].id, pack.items[i].id):
                    index.release()
                    error(invalid, "duplicate download object")
                slot = (slot + 1) & (index.slots.length - 1)
            index.slots[slot] = u32(i + 1)
        return index

    func release():
        free(self.slots) in memory.heap

    ## The first slot of `id`'s probe sequence: its leading bytes, which a SHA-1 spreads.
    func start(id: const u8[]) -> usize:
        var h: usize = 0
        for k in 0..<(usize)8: h = (h << 8) | (usize)id[k]
        return h & (self.slots.length - 1)

    ## The object `id` names, which must be of `kind`.
    func lookup(id: const u8[], kind: str) -> git.PackItem*!:
        var slot = self.start(id)
        while self.slots[slot] != 0:
            let item = &self.pack.items[(usize)self.slots[slot] - 1]
            if crypto_native.equal(item.id, id):
                if item.kind != kind: error(invalid, "download graph object type mismatch")
                return item
            slot = (slot + 1) & (self.slots.length - 1)
        error(invalid, "download graph object is missing")

    func require(id: const u8[], kind: str) -> !:
        _ = try self.lookup(id, kind)

    func require_hex(text: str, kind: str) -> !:
        var id: u8[20]
        try git.decode_id(text, id)
        try self.require(id, kind)

## A registry release pack holds one commit and its tree, without history; pass
## `history = false` so the commit's parents are not required.
pub func validate(pack: git.Pack*, requested: const u8[], history: bool = true) -> !:
    var index = try Index.over(pack)
    defer index.release()
    try index.require(requested, "commit")
    for item in pack.items:
        if item.kind == "tree":
            _ = try git.validate_tree(item.payload)
            var at: usize = 0
            while at < item.payload.length:
                let entry = try git.decode_tree_entry(item.payload[at..])
                if entry.mode != "160000":
                    try index.require(entry.id, "tree" if entry.mode == "40000" else "blob")
                at += entry.consumed
        elif item.kind == "commit":
            let commit = try git.decode_commit(item.payload)
            try index.require_hex(commit.tree, "tree")
            if history:
                for j in 0..<commit.parent_count: try index.require_hex(try commit.parent(j), "commit")
        elif item.kind == "tag":
            let tag = try git.decode_tag(item.payload)
            try index.require_hex(tag.object, tag.kind)