Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-procreate

Source of release 0.5.1

0.5.1 / src / plist.lucb

#==============================================================================================
#
#   plist - Binary property lists (bplist00) and the NSKeyedArchiver graphs inside them
#
#   DESCRIPTION:
#       `parse` reads Apple's binary property list: the trailer at the end (offset and
#       reference sizes, object count, top object, offset table), then every object
#       the offset table names into one flat list of `Value`s. Scalars (null, bool,
#       integer, real, date, UID) are held in the value; data and ASCII strings borrow
#       the caller's bytes; UTF-16 strings are converted to UTF-8 into one text pool;
#       arrays and dictionaries hold a run of object indices in one reference pool (a
#       dictionary's keys, then its values). Every offset, length and reference is
#       checked against the bytes, the object count is capped, and containers are
#       walked once to reject cycles and nesting deeper than a limit.
#
#       `unarchive` reads what NSKeyedArchiver writes on top of that: a dictionary
#       whose `$objects` array holds every archived object and whose `$top` names the
#       root by UID. A member of an archived object is followed through its UID to the
#       object it names, and the "$null" placeholder reads as absent.
#
#       Base only: a `Plist` borrows the bytes it was parsed from; keep them alive.
#
#==============================================================================================
import memory
from luce_std import utf8

## The bytes are not a binary property list or keyed archive this reader understands.
pub let invalid: ErrorCode = ErrorCode.package(1)
## The property list is larger or deeper than the reader's limits.
pub let limit: ErrorCode = ErrorCode.package(2)

## What a `Value` holds.
pub let kind_null: u8 = 0
pub let kind_bool: u8 = 1
pub let kind_integer: u8 = 2
pub let kind_real: u8 = 3
## Seconds since 2001-01-01 UTC, in `real`.
pub let kind_date: u8 = 4
pub let kind_data: u8 = 5
pub let kind_string: u8 = 6
## A keyed archive's reference to an object in `$objects`, its index in `integer`.
pub let kind_uid: u8 = 7
pub let kind_array: u8 = 8
pub let kind_dictionary: u8 = 9

## The default cap on objects in one property list.
pub let default_object_limit: usize = 1048576
## The default cap on containers nested in containers.
pub let default_depth_limit: usize = 64

## One object of a property list.
pub struct Value:
    pub var kind: u8
    ## A bool (0/1), an integer, or a UID's index.
    pub var integer: i64
    ## A real or a date.
    pub var real: f64
    ## A data object's bytes, or a string's UTF-8.
    pub var bytes: const u8[]
    ## An array's or dictionary's first reference in `Plist.references`.
    pub var first: usize
    ## An array's items, or a dictionary's pairs.
    pub var count: usize

## A parsed property list. `close` frees its lists; the bytes stay the caller's.
pub struct Plist:
    pub var values: Value[]
    ## Object indices for every container: an array's items; a dictionary's keys then values.
    pub var references: usize[]
    ## The UTF-8 of every UTF-16 string.
    pub var text: u8[]
    ## The top object's index.
    pub var top: usize

    ## The `index`th item of array `container`.
    pub func item(container: usize, index: usize) -> usize:
        return self.references[self.values[container].first + index]

    ## The `index`th key of dictionary `container`.
    pub func key(container: usize, index: usize) -> usize:
        return self.references[self.values[container].first + index]

    ## The `index`th value of dictionary `container`.
    pub func member_at(container: usize, index: usize) -> usize:
        let value = self.values[container]
        return self.references[value.first + value.count + index]

    ## The value under the string key `name` in dictionary `container`, if both are so.
    pub func member(container: usize, name: str) -> usize?:
        let value = self.values[container]
        if value.kind != kind_dictionary:
            return none
        for index in 0..<value.count:
            let key = self.values[self.references[value.first + index]]
            if key.kind == kind_string and (str)key.bytes == name:
                return self.references[value.first + value.count + index]
        return none

    ## Object `index` as text, if it is a string.
    pub func string(index: usize) -> str?:
        let value = self.values[index]
        if value.kind != kind_string:
            return none
        return (str)value.bytes

    pub func close():
        if self.values.length > 0:
            free(self.values) in memory.heap
        if self.references.length > 0:
            free(self.references) in memory.heap
        if self.text.length > 0:
            free(self.text) in memory.heap
        var no_values: Value[]
        var no_references: usize[]
        var no_text: u8[]
        self.values = no_values
        self.references = no_references
        self.text = no_text

## An object's marker and length, and where its contents start.
struct Head:
    var marker: u8
    var length: usize
    var start: usize

## Reads the objects of one property list; `end` is where the trailer starts.
struct Reader:
    var data: const u8[]
    var end: usize
    var offset_size: usize
    var reference_size: usize
    var count: usize
    var table: usize

    ## The `size`-byte big-endian number at `at`, which must lie before `end`.
    func number(at: usize, size: usize) -> u64!:
        if at > self.end or self.end - at < size:
            error(invalid, "a property list field runs past its end")
        var value: u64 = 0
        for index in 0..<size:
            value = (value << 8) | (u64)self.data[at + index]
        return value

    ## Where object `index` starts.
    func offset(index: usize) -> usize!:
        let at = try self.number(self.table + index * self.offset_size, self.offset_size)
        if at < 8 or at >= (u64)self.table:
            error(invalid, "a property list object lies outside the object area")
        return (usize)at

    ## The object reference at `at`, checked against the object count.
    func reference(at: usize) -> usize!:
        let value = try self.number(at, self.reference_size)
        if value >= (u64)self.count:
            error(invalid, "a property list reference names no object")
        return (usize)value

    ## The marker of the object at `at` and its length: the marker's low nibble, or
    ## the integer after it when that is 15.
    func head(at: usize) -> Head!:
        let marker = (u8)(try self.number(at, 1))
        var length = (usize)(marker & 15)
        var start = at + 1
        if length == 15 and marker >> 4 != 0 and marker >> 4 != 1 and marker >> 4 != 2 and marker >> 4 != 3 and marker >> 4 != 8:
            let size_marker = (u8)(try self.number(start, 1))
            if size_marker >> 4 != 1 or (size_marker & 15) > 3:
                error(invalid, "a property list length is not an integer")
            let size = (usize)1 << (usize)(size_marker & 15)
            let value = try self.number(start + 1, size)
            if value > (u64)self.end:
                error(invalid, "a property list length runs past its end")
            length = (usize)value
            start += 1 + size
        return Head(marker = marker, length = length, start = start)

    ## The bytes object `head` covers, `width` bytes per element.
    func span(head: Head, width: usize) -> const u8[]!:
        if head.start > self.end or (self.end - head.start) // width < head.length:
            error(invalid, "a property list object runs past its end")
        if head.length == 0:
            return b""
        return self.data[head.start..<head.start + head.length * width]

## The property list in `data`, every object read and checked. Fails with `invalid`
## when it is not a bplist00 or contradicts itself, and with `limit` beyond
## `max_objects` objects or `max_depth` nested containers. Close the result.
pub func parse(data: const u8[], max_objects: usize = default_object_limit, max_depth: usize = default_depth_limit) -> Plist!:
    if data.length < 40 or (str)data[..<8] != "bplist00":
        error(invalid, "not a binary property list")
    let end = data.length - 32
    var reader = Reader(data = data, end = data.length, offset_size = (usize)data[end + 6], reference_size = (usize)data[end + 7])
    if reader.offset_size < 1 or reader.offset_size > 8 or reader.reference_size < 1 or reader.reference_size > 8:
        error(invalid, "a property list's offset or reference size is not 1 to 8 bytes")
    let count = try reader.number(end + 8, 8)
    let top = try reader.number(end + 16, 8)
    let table = try reader.number(end + 24, 8)
    if count == 0 or top >= count or table < 9 or table > (u64)end:
        error(invalid, "a property list's trailer is inconsistent")
    if count > (u64)max_objects:
        error(limit, "the property list has more objects than the limit")
    if count > ((u64)end - table) // (u64)reader.offset_size:
        error(invalid, "a property list's offset table runs past its end")
    reader.count = (usize)count
    reader.table = (usize)table
    reader.end = end
    # First pass: how many references and how much UTF-8 the containers and UTF-16 need.
    var reference_total: usize = 0
    var text_total: usize = 0
    for index in 0..<reader.count:
        let head = try reader.head(try reader.offset(index))
        let tag = head.marker >> 4
        if tag == 10:
            reference_total += head.length
        elif tag == 13:
            reference_total += head.length * 2
        elif tag == 6:
            text_total += (try reader.span(head, 2)).length // 2 * 3
        if reference_total > reader.table or text_total > reader.table * 2:
            error(invalid, "a property list's containers outnumber its bytes")
    var plist = Plist(top = (usize)top)
    errdefer plist.close()
    plist.values = try new Value[reader.count] --- in memory.heap
    if reference_total > 0:
        plist.references = try new usize[reference_total] --- in memory.heap
    if text_total > 0:
        plist.text = try new u8[text_total] --- in memory.heap
    var references_used: usize = 0
    var text_used: usize = 0
    for index in 0..<reader.count:
        plist.values[index] = try read_value(&reader, index, &plist, &references_used, &text_used)
    try check_depth(&plist, max_depth)
    return plist

## Object `index`, its container references copied into `plist.references` and its
## UTF-16 converted into `plist.text` at the running totals.
func read_value(reader: Reader*, index: usize, plist: Plist*, references_used: usize*, text_used: usize*) -> Value!:
    let head = try reader.head(try reader.offset(index))
    let tag = head.marker >> 4
    let low = head.marker & 15
    var value = Value(kind = kind_null)
    if tag == 0:
        if low == 8 or low == 9:
            value.kind = kind_bool
            value.integer = (i64)(low == 9)
        elif low != 0 and low != 15:
            error(invalid, "an unknown property list marker")
    elif tag == 1:
        if low > 4:
            error(invalid, "a property list integer is wider than 16 bytes")
        let size = (usize)1 << (usize)low
        # A 16-byte integer keeps its low eight bytes; eight bytes are signed.
        let bits = try reader.number(head.start + (size - 8 if size > 8 else 0), size if size <= 8 else 8)
        value.kind = kind_integer
        value.integer = (i64)bits
    elif tag == 2 or head.marker == 0x33:
        if head.marker == 0x33 or low == 3:
            value.real = f64.bits(try reader.number(head.start, 8))
        elif low == 2:
            value.real = (f64)f32.bits((u32)(try reader.number(head.start, 4)))
        else:
            error(invalid, "a property list real is not 4 or 8 bytes")
        value.kind = kind_date if head.marker == 0x33 else kind_real
    elif tag == 4 or tag == 5:
        value.kind = kind_data if tag == 4 else kind_string
        value.bytes = try reader.span(head, 1)
    elif tag == 6:
        let units = try reader.span(head, 2)
        let used = *text_used
        let written = utf16_to_utf8(units, plist.text[used..])
        value.kind = kind_string
        value.bytes = plist.text[used..<used + written] if written > 0 else b""
        *text_used = used + written
    elif tag == 8:
        value.kind = kind_uid
        value.integer = (i64)(try reader.number(head.start, (usize)low + 1 if low < 8 else 8))
    elif tag == 10 or tag == 13:
        let pairs = head.length * (2 if tag == 13 else 1)
        let first = *references_used
        for at in 0..<pairs:
            plist.references[first + at] = try reader.reference(head.start + at * reader.reference_size)
        value.kind = kind_dictionary if tag == 13 else kind_array
        value.first = first
        value.count = head.length
        *references_used = first + pairs
    else:
        error(invalid, "an unknown property list marker")
    return value

## `units` (UTF-16, big-endian) as UTF-8 in `out`; returns the bytes written. An
## unpaired surrogate becomes U+FFFD.
func utf16_to_utf8(units: const u8[], out: u8[]) -> usize:
    var written: usize = 0
    var at: usize = 0
    let count = units.length // 2
    while at < count:
        var scalar = ((u32)units[at * 2] << 8) | (u32)units[at * 2 + 1]
        at += 1
        if scalar >= 0xD800 and scalar < 0xDC00 and at < count:
            let next = ((u32)units[at * 2] << 8) | (u32)units[at * 2 + 1]
            if next >= 0xDC00 and next < 0xE000:
                scalar = 0x10000 + ((scalar - 0xD800) << 10) + (next - 0xDC00)
                at += 1
        if scalar >= 0xD800 and scalar < 0xE000:
            scalar = 0xFFFD
        let size = utf8.encode(scalar, out[written..]) else 0
        written += size
    return written

## Rejects containers that hold themselves or nest deeper than `max_depth`: each
## container is walked once, depth first, marked while it is on the path.
func check_depth(plist: Plist*, max_depth: usize) -> !:
    let state = try new u8[plist.values.length] --- in memory.heap
    defer free(state) in memory.heap
    for index in 0..<state.length:
        state[index] = 0
    for index in 0..<plist.values.length:
        try visit(plist, state, index, 0, max_depth)

## Walks container `index` at `depth`: state 1 while on the path, 2 once done.
func visit(plist: Plist*, state: u8[], index: usize, depth: usize, max_depth: usize) -> !:
    let value = plist.values[index]
    if value.kind != kind_array and value.kind != kind_dictionary or state[index] == 2:
        return
    if state[index] == 1:
        error(invalid, "a property list container holds itself")
    if depth >= max_depth:
        error(limit, "the property list nests deeper than the limit")
    state[index] = 1
    let references = value.count * (2 if value.kind == kind_dictionary else 1)
    for at in 0..<references:
        try visit(plist, state, plist.references[value.first + at], depth + 1, max_depth)
    state[index] = 2

## An NSKeyedArchiver graph over a parsed property list. `close` frees it.
pub struct KeyedArchive:
    pub var plist: Plist
    ## The `$objects` array's index.
    pub var objects: usize
    ## The root object's index, from `$top`'s "root".
    pub var root: usize

    ## Object `index` with a UID followed to the archived object it names; none for
    ## "$null" or a UID that names nothing.
    pub func resolve(index: usize) -> usize?:
        let value = self.plist.values[index]
        if value.kind != kind_uid:
            return index
        let archived = self.plist.values[self.objects]
        if value.integer < 0 or (u64)value.integer >= (u64)archived.count:
            return none
        let target = self.plist.item(self.objects, (usize)value.integer)
        if let text = self.plist.string(target):
            if text == "$null":
                return none
        return target

    ## Member `name` of archived object `object`, followed through its UID.
    pub func member(object: usize, name: str) -> usize?:
        let found = self.plist.member(object, name) else return none
        return self.resolve(found)

    ## Object `index` as text: a string, or an archived NSString's "NS.string".
    pub func text(index: usize) -> str?:
        if let text = self.plist.string(index):
            return text
        let inner = self.member(index, "NS.string") else return none
        return self.plist.string(inner)

    pub func close():
        self.plist.close()

## The NSKeyedArchiver archive in `data`: parsed, with `$objects` and the root
## found. Fails with `invalid` when the top object is not a keyed archive.
pub func unarchive(data: const u8[], max_objects: usize = default_object_limit, max_depth: usize = default_depth_limit) -> KeyedArchive!:
    var plist = try parse(data, max_objects, max_depth)
    errdefer plist.close()
    let objects = plist.member(plist.top, "$objects") else error(invalid, "not a keyed archive: no $objects")
    let top = plist.member(plist.top, "$top") else error(invalid, "not a keyed archive: no $top")
    if plist.values[objects].kind != kind_array or plist.values[top].kind != kind_dictionary:
        error(invalid, "not a keyed archive: $objects or $top has the wrong type")
    var archive = KeyedArchive(plist = plist, objects = objects, root = 0)
    let root_reference = plist.member(top, "root") else error(invalid, "a keyed archive without a root")
    archive.root = archive.resolve(root_reference) else error(invalid, "a keyed archive's root is null")
    return archive