Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-prism

Source of release 0.6.0

0.6.0 / src / composition / delta.lucb

## Sparse write-buffer layer. A layer is a map of (path, cell, name) → op, not a document.
import memory
import interop
from animation import Property, Sample
from collections.index import Index
import composition.layers as overlay_ops
from model import DocumentData, Element
from path import parent_path, element_path
from storage import Buffer, List, close_names, copied, text_copy, set_pair
from types import DType, missing
from value import ValueData, own_value, value_header
from names import Name

pub enum Cell as u8:
    element = 0
    property = 1
    metadata = 2
    connection = 3
    disconnect = 4
    reorder = 5
    asset = 6

pub struct Key:
    pub var path: Buffer
    pub var cell: Cell
    pub var name: Buffer

    pub func close():
        self.path.close()
        self.name.close()

pub struct Op:
    pub var deleted: bool
    pub var override: bool
    pub var identifier: usize
    pub var type_name: Buffer
    pub var value: ValueData = ValueData()
    pub var text: Buffer
    pub var children: List[Buffer]
    pub var samples: List[Sample]

    pub func close():
        self.type_name.close()
        self.value.close()
        self.text.close()
        close_names(&self.children)
        for i in 0..<self.samples.count:
            self.samples.items[i].close()
        self.samples.close()

pub struct Entry:
    pub var key: Key
    pub var op: Op

    func close():
        self.key.close()
        self.op.close()

func encode_slot(path: str, cell: Cell, name: str) -> Buffer!:
    var out: Buffer
    errdefer out.close()
    try out.text(path)
    try out.byte(0)
    try out.byte((u8)cell)
    try out.byte(0)
    try out.text(name)
    return out

func copy_names_owned(source: const List[Buffer]*) -> List[Buffer]!:
    var output: List[Buffer]
    errdefer close_names(&output)
    try output.reserve(source.count)
    for item in source.span():
        try output.push(try item.copy())
    return output

func copy_op(source: const Op*) -> Op!:
    var out = Op(deleted = source.deleted, override = source.override, identifier = source.identifier)
    errdefer out.close()
    out.type_name = try source.type_name.copy()
    out.value = try source.value.copy()
    out.text = try source.text.copy()
    out.children = try copy_names_owned(&source.children)
    try out.samples.reserve(source.samples.count)
    for sample in source.samples.span():
        try out.samples.push(try sample.copy())
    return out

func copy_key(source: const Key*) -> Key!:
    var out = Key(cell = source.cell)
    errdefer out.close()
    out.path = try source.path.copy()
    out.name = try source.name.copy()
    return out

pub struct Layer:
    pub var items: List[Entry]
    var index: Index
    var generation_base: u64

    pub func init():
        self.items = List[Entry]()
        self.index = Index()
        self.generation_base = 0

    pub func count() -> usize:
        return self.items.count

    pub func close():
        for i in 0..<self.items.count:
            self.items.items[i].close()
        self.items.close()
        self.index.close()

    pub func find(path: str, cell: Cell, name: str = "") -> usize?:
        var encoded = encode_slot(path, cell, name) catch failure:
            return none
        defer encoded.close()
        let bucket = self.index.find(encoded.view()) else return none
        if self.index.buckets.items[bucket].rows.count == 0:
            return none
        return self.index.buckets.items[bucket].rows.items[0]

    pub func get(path: str, cell: Cell, name: str = "") -> const Op*?:
        let row = self.find(path, cell, name) else return none
        return &self.items.items[row].op

    pub func put(path: str, cell: Cell, name: str, op: Op) -> !:
        var owned = op
        errdefer owned.close()
        if let row = self.find(path, cell, name):
            self.items.items[row].op.close()
            self.items.items[row].op = owned
            return
        var key = Key(cell = cell)
        errdefer key.close()
        key.path = try text_copy(path)
        key.name = try text_copy(name)
        var encoded = try encode_slot(path, cell, name)
        defer encoded.close()
        var entry = Entry(key = key, op = owned)
        key = Key()
        owned = Op()
        errdefer entry.close()
        try self.items.reserve(self.items.count + 1)
        _ = try self.index.add(encoded.view(), self.items.count)
        try self.items.push(entry)

    pub func copy() -> Layer!:
        var out = Layer()
        out.generation_base = self.generation_base
        errdefer out.close()
        try out.items.reserve(self.items.count)
        for entry in self.items.span():
            var key = try copy_key(&entry.key)
            errdefer key.close()
            var op = try copy_op(&entry.op)
            errdefer op.close()
            var encoded = try encode_slot(key.path.view(), key.cell, key.name.view())
            defer encoded.close()
            var copied_entry = Entry(key = key, op = op)
            key = Key()
            op = Op()
            errdefer copied_entry.close()
            _ = try out.index.add(encoded.view(), out.items.count)
            try out.items.push(copied_entry)
        return out

## Overlay-apply of `later` onto `earlier`. Not a per-key union across concurrent sessions.
pub func merge(earlier: const Layer*, later: const Layer*) -> Layer!:
    var out = Layer()
    errdefer out.close()
    for entry in earlier.items.span():
        if hidden_by_delete(later, entry.key.path.view()):
            continue
        var op = try copy_op(&entry.op)
        try out.put(entry.key.path.view(), entry.key.cell, entry.key.name.view(), op)
    for entry in later.items.span():
        var op = try copy_op(&entry.op)
        try out.put(entry.key.path.view(), entry.key.cell, entry.key.name.view(), op)
    return out

func tombstone_replaced(base: const DocumentData*, earlier: const Layer*, later: const Layer*, out: Layer*) -> !:
    for entry in later.items.span():
        if entry.key.cell != Cell.element or entry.op.deleted or entry.op.override:
            continue
        let path = entry.key.path.view()
        if visible(base, earlier, none, path):
            continue
        let index = base.find(path) else continue
        let element = &base.elements.items[index]
        for prop in element.properties.span():
            let name = prop.name.view()
            if later.get(path, Cell.property, name) == none:
                try out.put(path, Cell.property, name, Op(deleted = true))
        for meta in element.metadata.span():
            let name = meta.key.view()
            if later.get(path, Cell.metadata, name) == none:
                try out.put(path, Cell.metadata, name, Op(deleted = true))

pub func collapse(base: const DocumentData*, layers: const Layer[]) -> Layer!:
    var out = Layer()
    errdefer out.close()
    for layer in layers:
        var merged = try merge(&out, &layer)
        errdefer merged.close()
        try tombstone_replaced(base, &out, &layer, &merged)
        out.close()
        out = merged
    return out

func hidden_by_delete(layer: const Layer*, path: str) -> bool:
    var current = path
    while true:
        if let op = layer.get(current, Cell.element):
            if op.deleted:
                return true
        if current == "/":
            return false
        current = parent_path(current)

func deletes_path(layer: const Layer*, path: str) -> bool:
    let op = layer.get(path, Cell.element) else return false
    return op.deleted

func apply_element(layer: const Layer*, path: str, exists: bool) -> bool:
    var present = exists
    if deletes_path(layer, path):
        present = false
    let op = layer.get(path, Cell.element) else return present
    if op.deleted:
        return false
    if not op.override or present:
        return true
    return present

pub func visible(base: const DocumentData*, first: const Layer*, second: const Layer*?, path: str) -> bool:
    if path == "/":
        return true
    if not visible(base, first, second, parent_path(path)):
        return false
    var exists = base.contains(path)
    exists = apply_element(first, path, exists)
    if let extra = second:
        exists = apply_element(extra, path, exists)
    return exists

pub func has_metadata(base: const DocumentData*, first: const Layer*, second: const Layer*?, path: str, key: str) -> bool:
    if not visible(base, first, second, path):
        return false
    if let extra = second:
        if let op = extra.get(path, Cell.metadata, key):
            return not op.deleted
    if let op = first.get(path, Cell.metadata, key):
        return not op.deleted
    return base.has_metadata(path, key)

pub func read_metadata(base: const DocumentData*, first: const Layer*, second: const Layer*?, path: str, key: str) -> str!:
    if not visible(base, first, second, path):
        error(missing, "Prism metadata does not exist")
    if let extra = second:
        if let op = extra.get(path, Cell.metadata, key):
            if op.deleted:
                error(missing, "Prism metadata does not exist")
            return op.text.view()
    if let op = first.get(path, Cell.metadata, key):
        if op.deleted:
            error(missing, "Prism metadata does not exist")
        return op.text.view()
    return try base.metadata(path, key)

pub func has_property(base: const DocumentData*, first: const Layer*, second: const Layer*?, path: str, name: str) -> bool:
    if not visible(base, first, second, path):
        return false
    if let extra = second:
        if let op = extra.get(path, Cell.property, name):
            return not op.deleted
    if let op = first.get(path, Cell.property, name):
        return not op.deleted
    return base.has_property(path, name)

pub func read_property(base: const DocumentData*, first: const Layer*, second: const Layer*?, path: str, name: str) -> ValueData!:
    if not visible(base, first, second, path):
        error(missing, "Prism property does not exist")
    if let extra = second:
        if let op = extra.get(path, Cell.property, name):
            if op.deleted:
                error(missing, "Prism property does not exist")
            return try op.value.copy()
    if let op = first.get(path, Cell.property, name):
        if op.deleted:
            error(missing, "Prism property does not exist")
        return try op.value.copy()
    let element = &base.elements.items[try base.require(path)]
    let index = element.property(name) else error(missing, "Prism property does not exist")
    return try element.properties.items[index].value.copy()

func contains_path(paths: const List[str]*, path: str) -> bool:
    for item in paths.span():
        if item == path:
            return true
    return false

func emit_order_list(listed: const List[Buffer]*, acc: List[str]*) -> List[str]!:
    var out: List[str]
    errdefer out.close()
    var seen: List[str]
    defer seen.close()
    for child in listed.span():
        let path = child.view()
        if contains_path(acc, path) and not contains_path(&seen, path):
            try out.push(path)
            try seen.push(path)
    for path in acc.span():
        if not contains_path(&seen, path):
            try out.push(path)
            try seen.push(path)
    return out

pub func children(base: const DocumentData*, first: const Layer*, second: const Layer*?, parent: str) -> List[str]!:
    if parent != "/" and not visible(base, first, second, parent):
        return List[str]()
    var acc = try base.children(parent)
    errdefer acc.close()
    try apply_children(&acc, first, parent)
    if let extra = second:
        try apply_children(&acc, extra, parent)
    var out: List[str]
    errdefer out.close()
    for path in acc.span():
        if visible(base, first, second, path):
            try out.push(path)
    return out

func apply_children(acc: List[str]*, layer: const Layer*, parent: str) -> !:
    var kept: List[str]
    errdefer kept.close()
    for path in acc.span():
        if not deletes_path(layer, path) and not deletes_path(layer, parent):
            try kept.push(path)
    for entry in layer.items.span():
        if entry.key.cell != Cell.element:
            continue
        if parent_path(entry.key.path.view()) != parent:
            continue
        if entry.op.deleted:
            continue
        let path = entry.key.path.view()
        let exists = contains_path(&kept, path)
        if not entry.op.override or exists:
            if not exists:
                try kept.push(path)
    if let op = layer.get(parent, Cell.reorder):
        var ordered = try emit_order_list(&op.children, &kept)
        kept.close()
        kept = ordered
    acc.close()
    *acc = kept
    kept = List[str]()

func touches(layer: const Layer*, path: str) -> bool:
    for entry in layer.items.span():
        if entry.key.path.view() == path:
            return true
    return false

func layer_ops(base: const DocumentData*, first: const Layer*, second: const Layer*?, path: str) -> bool:
    if touches(first, path):
        return true
    if let extra = second:
        return touches(extra, path)
    return false

func later_element(first: const Layer*, second: const Layer*?, path: str) -> const Op*?:
    if let extra = second:
        if let op = extra.get(path, Cell.element):
            return op
    return first.get(path, Cell.element)

func later_property(first: const Layer*, second: const Layer*?, path: str, name: str) -> const Op*?:
    if let extra = second:
        if let op = extra.get(path, Cell.property, name):
            return op
    return first.get(path, Cell.property, name)

pub func read_type(base: const DocumentData*, first: const Layer*, second: const Layer*?, path: str) -> str!:
    if not visible(base, first, second, path):
        error(missing, "Prism element does not exist")
    if let op = later_element(first, second, path):
        if not op.deleted and op.type_name.used > 0:
            return op.type_name.view()
    return try base.type_at(path)

func property_from_op(name: str, op: const Op*) -> Property!:
    var prop = Property()
    errdefer prop.close()
    prop.name = try Name.of(name)
    prop.type_name = try Name.of(op.type_name.view())
    prop.value = try op.value.copy()
    try prop.samples.reserve(op.samples.count)
    for sample in op.samples.span():
        try prop.samples.push(try sample.copy())
    return prop

func add_named(names: List[str]*, layer: const Layer*, path: str, cell: Cell) -> !:
    for entry in layer.items.span():
        if entry.key.cell != cell or entry.key.path.view() != path or entry.op.deleted:
            continue
        let name = entry.key.name.view()
        if not contains_path(names, name):
            try names.push(name)

func property_names(base: const DocumentData*, first: const Layer*, second: const Layer*?, path: str) -> List[str]!:
    var names: List[str]
    errdefer names.close()
    if let index = base.find(path):
        for prop in base.elements.items[index].properties.span():
            if has_property(base, first, second, path, prop.name.view()):
                try names.push(prop.name.view())
    try add_named(&names, first, path, Cell.property)
    if let extra = second:
        try add_named(&names, extra, path, Cell.property)
    return names

func metadata_names(base: const DocumentData*, first: const Layer*, second: const Layer*?, path: str) -> List[str]!:
    var names: List[str]
    errdefer names.close()
    if let index = base.find(path):
        for item in base.elements.items[index].metadata.span():
            if has_metadata(base, first, second, path, item.key.view()):
                try names.push(item.key.view())
    try add_named(&names, first, path, Cell.metadata)
    if let extra = second:
        try add_named(&names, extra, path, Cell.metadata)
    return names

func assemble_property(base: const DocumentData*, first: const Layer*, second: const Layer*?, path: str, name: str) -> Property!:
    if let op = later_property(first, second, path, name):
        if op.deleted:
            error(missing, "Prism property does not exist")
        return try property_from_op(name, op)
    let element = &base.elements.items[try base.require(path)]
    let index = element.property(name) else error(missing, "Prism property does not exist")
    return try element.properties.items[index].copy()

pub func assemble(base: const DocumentData*, first: const Layer*, second: const Layer*?, path: str) -> Element!:
    if not visible(base, first, second, path):
        error(missing, "Prism element does not exist")
    if not layer_ops(base, first, second, path):
        return try base.elements.items[try base.require(path)].copy()
    var row = Element()
    errdefer row.close()
    row.path = try text_copy(path)
    row.kind = try text_copy(try read_type(base, first, second, path))
    if let op = later_element(first, second, path):
        if not op.deleted:
            row.identifier = op.identifier
            row.override = op.override
    if row.identifier == 0:
        if let index = base.find(path):
            row.identifier = base.elements.items[index].identifier
            if later_element(first, second, path) == none:
                row.override = base.elements.items[index].override
    var names = try property_names(base, first, second, path)
    defer names.close()
    for name in names.span():
        var prop = try assemble_property(base, first, second, path, name)
        errdefer prop.close()
        try row.put_property(&prop)
        prop.close()
        prop = Property()
    var metas = try metadata_names(base, first, second, path)
    defer metas.close()
    for key in metas.span():
        try set_pair(&row.metadata, key, try read_metadata(base, first, second, path, key))
    return row

func layer_connection(layer: const Layer*, target: str) -> str?:
    let op = layer.get(target, Cell.connection) else return none
    return op.text.view()

func layer_disconnects(layer: const Layer*, target: str) -> bool:
    if layer.get(target, Cell.connection) != none:
        return false
    return layer.get(target, Cell.disconnect) != none

func connected_if_visible(base: const DocumentData*, first: const Layer*, second: const Layer*?, target: str, source: str) -> str?:
    if not visible(base, first, second, element_path(target)):
        return none
    if not visible(base, first, second, element_path(source)):
        return none
    return source

pub func incoming(base: const DocumentData*, first: const Layer*, second: const Layer*?, target: str) -> str?:
    if let extra = second:
        if let source = layer_connection(extra, target):
            return connected_if_visible(base, first, second, target, source)
        if layer_disconnects(extra, target):
            return none
    if let source = layer_connection(first, target):
        return connected_if_visible(base, first, second, target, source)
    if layer_disconnects(first, target):
        return none
    let source = base.incoming(target) else return none
    return connected_if_visible(base, first, second, target, source)

pub func intern_path(base: const DocumentData*, first: const Layer*, second: const Layer*?, path: str) -> str?:
    if let index = base.find(path):
        return base.elements.items[index].path.view()
    if let extra = second:
        if let row = extra.find(path, Cell.element):
            return extra.items.items[row].key.path.view()
    if let row = first.find(path, Cell.element):
        return first.items.items[row].key.path.view()
    return none

func give(layer: Layer*, path: str, cell: Cell, name: str, op: Op) -> !:
    var owned = op
    try layer.put(path, cell, name, owned)

pub func from_document(data: const DocumentData*) -> Layer!:
    var layer = Layer()
    errdefer layer.close()
    for deletion in data.deletions.span():
        try give(&layer, deletion.view(), Cell.element, "", Op(deleted = true))
    for element in data.elements.span():
        var element_op = Op(deleted = false, override = element.override, identifier = element.identifier)
        errdefer element_op.close()
        element_op.type_name = try element.kind.copy()
        var give_element = element_op
        element_op = Op()
        try give(&layer, element.path.view(), Cell.element, "", give_element)
        for prop in element.properties.span():
            var op = Op()
            errdefer op.close()
            op.type_name = try text_copy(prop.type_name.view())
            op.value = try prop.value.copy()
            try op.samples.reserve(prop.samples.count)
            for sample in prop.samples.span():
                try op.samples.push(try sample.copy())
            var give_prop = op
            op = Op()
            try give(&layer, element.path.view(), Cell.property, prop.name.view(), give_prop)
        for name in element.removed_properties.span():
            try give(&layer, element.path.view(), Cell.property, name.view(), Op(deleted = true))
        for meta in element.metadata.span():
            var op = Op()
            errdefer op.close()
            op.text = try meta.value.copy()
            var give_meta = op
            op = Op()
            try give(&layer, element.path.view(), Cell.metadata, meta.key.view(), give_meta)
        for name in element.removed_metadata.span():
            try give(&layer, element.path.view(), Cell.metadata, name.view(), Op(deleted = true))
    for connection in data.connections.span():
        var op = Op()
        errdefer op.close()
        op.text = try connection.value.copy()
        var give_conn = op
        op = Op()
        try give(&layer, connection.key.view(), Cell.connection, "", give_conn)
    for disconnected in data.disconnections.span():
        try give(&layer, disconnected.view(), Cell.disconnect, "", Op(deleted = true))
    for order in data.reorders.span():
        var op = Op()
        errdefer op.close()
        op.children = try copy_names_owned(&order.children)
        var give_order = op
        op = Op()
        try give(&layer, order.parent.view(), Cell.reorder, "", give_order)
    for asset in data.assets.span():
        var op = Op()
        errdefer op.close()
        var shape: u32[1] = [(u32)asset.bytes.used]
        op.value = try value_header(DType.uint8, shape)
        op.value.payload = try copied(asset.bytes.bytes())
        op.text = try asset.mime.copy()
        var give_asset = op
        op = Op()
        try give(&layer, asset.path.view(), Cell.asset, "", give_asset)
    return layer

pub func to_document(layer: const Layer*) -> DocumentData!:
    var output = DocumentData()
    errdefer output.close()
    for entry in layer.items.span():
        if entry.key.cell == Cell.element and entry.op.deleted:
            try output.mark_deleted(entry.key.path.view())
    for entry in layer.items.span():
        if entry.key.cell != Cell.element or entry.op.deleted:
            continue
        try output.insert(entry.key.path.view(), entry.op.type_name.view(), entry.op.override)
        if entry.op.identifier != 0:
            output.elements.items[output.elements.count - 1].identifier = entry.op.identifier
    for entry in layer.items.span():
        let path = entry.key.path.view()
        if entry.key.cell == Cell.property:
            if entry.op.deleted:
                try output.mark_unset(path, entry.key.name.view())
                continue
            var prop = Property()
            errdefer prop.close()
            prop.name = try Name.of(entry.key.name.view())
            prop.type_name = try Name.of(entry.op.type_name.view())
            prop.value = try entry.op.value.copy()
            try prop.samples.reserve(entry.op.samples.count)
            for sample in entry.op.samples.span():
                try prop.samples.push(try sample.copy())
            try output.elements.items[try output.require(path)].put_property(&prop)
            prop.close()
            prop = Property()
        elif entry.key.cell == Cell.metadata:
            if entry.op.deleted:
                try output.mark_unset(path, entry.key.name.view(), true)
            else:
                try output.set_metadata(path, entry.key.name.view(), entry.op.text.view())
        elif entry.key.cell == Cell.connection:
            try output.connect(entry.op.text.view(), path)
        elif entry.key.cell == Cell.disconnect:
            try output.mark_disconnected(path)
        elif entry.key.cell == Cell.reorder:
            var names: List[str]
            defer names.close()
            for child in entry.op.children.span():
                try names.push(child.view())
            try output.reorder(path, names.span())
        elif entry.key.cell == Cell.asset:
            try output.set_asset(path, entry.op.value.payload.bytes(), entry.op.text.view())
    return output

## In-place apply of one layer onto unique-owner tables. Same order as overlay().
pub func apply(base: DocumentData*, layer: const Layer*) -> !:
    for entry in layer.items.span():
        if entry.key.cell == Cell.element and entry.op.deleted:
            let path = entry.key.path.view()
            if base.contains(path):
                try base.remove(path)
    for entry in layer.items.span():
        if entry.key.cell == Cell.disconnect:
            base.disconnect(entry.key.path.view())
    for entry in layer.items.span():
        if entry.key.cell != Cell.element or entry.op.deleted:
            continue
        let path = entry.key.path.view()
        if base.find(path) != none:
            if entry.op.type_name.used > 0:
                try base.set_type(path, entry.op.type_name.view())
        elif not entry.op.override:
            try base.insert(path, entry.op.type_name.view(), false)
            if entry.op.identifier != 0:
                base.elements.items[base.elements.count - 1].identifier = entry.op.identifier
    for entry in layer.items.span():
        let path = entry.key.path.view()
        if not base.contains(path):
            continue
        if entry.key.cell == Cell.property:
            if entry.op.deleted:
                if base.has_property(path, entry.key.name.view()):
                    try base.remove_property(path, entry.key.name.view())
                continue
            var prop = Property()
            errdefer prop.close()
            prop.name = try Name.of(entry.key.name.view())
            prop.type_name = try Name.of(entry.op.type_name.view())
            prop.value = try entry.op.value.copy()
            try prop.samples.reserve(entry.op.samples.count)
            for sample in entry.op.samples.span():
                try prop.samples.push(try sample.copy())
            try base.elements.items[try base.require(path)].put_property(&prop)
            prop.close()
            prop = Property()
        elif entry.key.cell == Cell.metadata:
            if entry.op.deleted:
                if base.has_metadata(path, entry.key.name.view()):
                    try base.remove_metadata(path, entry.key.name.view())
            else:
                try base.set_metadata(path, entry.key.name.view(), entry.op.text.view())
        elif entry.key.cell == Cell.asset:
            try base.set_asset(path, entry.op.value.payload.bytes(), entry.op.text.view())
    for entry in layer.items.span():
        if entry.key.cell == Cell.connection:
            try base.connect(entry.op.text.view(), entry.key.path.view())
    var reordered = false
    for entry in layer.items.span():
        if entry.key.cell != Cell.reorder:
            continue
        var names: List[str]
        defer names.close()
        for child in entry.op.children.span():
            try names.push(child.view())
        try base.reorder(entry.key.path.view(), names.span())
        reordered = true
    if reordered:
        var ordered = try overlay_ops.rebuild_order(base)
        errdefer ordered.close()
        base.close()
        base[0] = ordered
        base.references.store(1, .relaxed)
        ordered = DocumentData()
    overlay_ops.prune_connections(base)

pub let layer_type = interop.Type[Layer]("Prism layer", Layer.close, closeable = true)

pub func own_layer(layer: Layer) -> interop.Reference[Layer]!:
    var owned = layer
    errdefer owned.close()
    let native = try new Layer() in memory.heap
    native[0] = owned
    owned = Layer()
    return try interop.Reference[Layer].adopt(native, layer_type, memory.heap)