dymokomi/luce-git
Source of release 0.5.1
## Owning bounded SHA-1 pack reader, with optional borrowed external bases.
import memory
from luce_compress import compress
from luce_crypto import native as crypto_native
import object
import delta
pub struct Item:
pub var kind: str
pub var payload: u8[]
pub var id: u8[20]
var offset: usize
var base_offset: usize
var base_id: u8[20]
var form: u8
var resolved: bool
var depth: usize
pub struct Pack:
pub var items: Item[]
pub func close():
for i in 0..<self.items.length:
if self.items[i].payload.length > 0: free(self.items[i].payload) in memory.heap
if self.items.length > 0: free(self.items) in memory.heap
var empty: Item[]
self.items = empty
func release_bytes(bytes: u8[]):
if bytes.length > 0: free(bytes) in memory.heap
func byte(input: const u8[], at: usize*) -> u8!:
if *at >= input.length: error(object.invalid, "truncated pack")
let value = input[*at]
*at += 1
return value
func uint32(input: const u8[], at: usize*) -> usize!:
var value: usize = 0
for i in 0..<4:
_ = i
value = (value << 8) | (usize)try byte(input, at)
return value
func kind_name(kind: u8) -> str!:
if kind == 1: return "commit"
if kind == 2: return "tree"
if kind == 3: return "blob"
if kind == 4: return "tag"
error(object.invalid, "invalid full-object pack kind")
func identify(item: Item*) -> !:
_ = try object.hash_object(item.kind, item.payload, item.id)
item.resolved = true
## Return none for a missing base. The result borrows caller storage until the
## next lookup or decode return. No returned borrow is retained by the pack.
pub type Lookup = func(const u8[], void*?) -> object.Object?!
func missing(id: const u8[], context: void*?) -> object.Object?!:
_ = id
_ = context
return none
func expand(item: Item*, base: object.Object, depth: usize, bytes: usize*) -> !:
if depth >= 64: error(object.invalid, "pack delta chain too deep")
# Canonicalize kind: external storage may disappear on the next lookup.
var kind: str
if base.kind == "blob": kind = "blob"
elif base.kind == "tree": kind = "tree"
elif base.kind == "commit": kind = "commit"
elif base.kind == "tag": kind = "tag"
else: error(object.invalid, "invalid external pack base kind")
let size = try delta.result_size(base.payload.length, item.payload)
if size > 67108864 - *bytes: error(object.invalid, "pack expanded byte limit exceeded")
var result: u8[]
if size > 0: result = try new u8[size] --- in memory.heap
errdefer release_bytes(result)
_ = try delta.apply(base.payload, item.payload, result)
if item.payload.length > 0: free(item.payload) in memory.heap
item.payload = result
var empty: u8[]
result = empty
item.kind = kind
item.depth = depth + 1
try identify(item)
*bytes += size
## The item at pack offset `offset`, by binary search: items are parsed, and so lie, in
## increasing offset order.
func at_offset(pack: Pack*, offset: usize) -> Item*?:
var low: usize = 0
var high = pack.items.length
while low < high:
let middle = low + (high - low) // 2
let found = pack.items[middle].offset
if found == offset: return &pack.items[middle]
if found < offset: low = middle + 1
else: high = middle
return none
## The resolved item of the pack whose object ID is `id`. A scan, charged to `budget`:
## git sends a ref-delta against an in-pack base rarely, usually naming an external one.
func with_id(pack: Pack*, id: const u8[], budget: usize*) -> Item*?!:
for i in 0..<pack.items.length:
if *budget == 0: error(object.invalid, "pack resolution work limit exceeded")
*budget -= 1
let base = &pack.items[i]
if base.resolved and crypto_native.equal(base.id, id): return base
return none
## Resolve every delta: each pass expands all items whose base is resolved, so the passes
## number about the deepest delta chain; an ofs-delta finds its base by offset at once.
## Ref-deltas whose base is in neither the pack nor `lookup` leave the pack unresolvable.
func resolve(pack: Pack*, total: usize, lookup: Lookup, context: void*?) -> !:
var bytes = total
var budget: usize = 16777216
var lookups: usize = 0
var external_bytes: usize = 0
var unresolved: usize = 0
for i in 0..<pack.items.length:
if not pack.items[i].resolved: unresolved += 1
while unresolved > 0:
var progress = false
for i in 0..<pack.items.length:
let item = &pack.items[i]
if item.resolved: continue
let found = at_offset(pack, item.base_offset) if item.form == 6 else try with_id(pack, item.base_id, &budget)
let base = found else continue
if not base.resolved: continue
try expand(item, object.Object(base.kind, base.payload), base.depth, &bytes)
unresolved -= 1
progress = true
if progress: continue
for i in 0..<pack.items.length:
let item = &pack.items[i]
if item.resolved or item.form != 7: continue
if lookups >= object.max_pack_objects: error(object.invalid, "external pack lookup limit exceeded")
lookups += 1
let base = (try lookup(item.base_id, context)) else continue
if base.payload.length > 67108864 - external_bytes:
error(object.invalid, "external pack base byte limit exceeded")
external_bytes += base.payload.length
var actual: u8[20]
_ = try object.hash_object(base.kind, base.payload, actual)
if not crypto_native.equal(actual, item.base_id):
error(object.invalid, "external pack base ID mismatch")
try expand(item, base, 0, &bytes)
unresolved -= 1
progress = true
if not progress: error(object.invalid, "missing or cyclic pack delta base")
## Accept complete self-contained version 2/3 SHA-1 packs. All returned bytes are
## owned; close exactly once (close itself is idempotent), never copy ownership.
pub func decode(input: const u8[], lookup: Lookup = missing, context: void*? = none) -> Pack!:
if input.length < 32 or input.length > 67108864: error(object.invalid, "pack byte limit invalid")
let end = input.length - 20
var checksum: u8[20]
_ = try crypto_native.sha1_digest(input[..<end], checksum)
if not crypto_native.equal(checksum, input[end..]): error(object.invalid, "pack checksum mismatch")
let wire = input[..<end]
if (str)wire[..<4] != "PACK": error(object.invalid, "invalid pack magic")
var at: usize = 4
let version = try uint32(wire, &at)
if version != 2 and version != 3: error(object.invalid, "unsupported pack version")
let count = try uint32(wire, &at)
if count > object.max_pack_objects: error(object.invalid, "pack object count limit exceeded")
var result = Pack()
errdefer result.close()
if count > 0:
result.items = try new Item[count] --- in memory.heap
# alloc supplies storage, not initialized Item values. Initialize every
# slot before parsing so both resolution and partial-error close are safe.
for i in 0..<count: result.items[i] = Item()
var total: usize = 0
for i in 0..<count:
let item = &result.items[i]
item.offset = at
var value = try byte(wire, &at)
item.form = (value >> 4) & 7
if item.form == 0 or item.form == 5: error(object.invalid, "reserved pack object type")
var size = (usize)(value & 15)
var factor: usize = 16
while value & 128 != 0:
value = try byte(wire, &at)
let part = (usize)(value & 127) *? factor else error(object.invalid, "pack size overflow")
size = size +? part else error(object.invalid, "pack size overflow")
if value & 128 != 0:
factor = factor *? 128 else error(object.invalid, "pack size overflow")
if size > 67108864 - total: error(object.invalid, "pack inflated byte limit exceeded")
if item.form == 6:
value = try byte(wire, &at)
var distance = (usize)(value & 127)
while value & 128 != 0:
value = try byte(wire, &at)
let bumped = distance +? 1 else error(object.invalid, "pack offset overflow")
let scaled = bumped *? 128 else error(object.invalid, "pack offset overflow")
distance = scaled +? (usize)(value & 127) else error(object.invalid, "pack offset overflow")
if distance == 0 or distance > item.offset: error(object.invalid, "pack base offset invalid")
item.base_offset = item.offset - distance
elif item.form == 7:
for j in 0..<20: item.base_id[j] = try byte(wire, &at)
else:
item.kind = try kind_name(item.form)
let decoded = try compress.decode(wire[at..], (i64)size, allow_trailing = true)
defer decoded.release()
let payload = try decoded.value().bytes()
if payload.length != size: error(object.invalid, "pack object length mismatch")
at += (usize)try decoded.value().consumed()
if size > 0:
item.payload = try new u8[size] --- in memory.heap
for j in 0..<size: item.payload[j] = payload[j]
total += size
if item.form < 5: try identify(item)
if at != end: error(object.invalid, "trailing pack entries or bytes")
try resolve(&result, total, lookup, context)
return result