dymokomi/luce-prism
Source of release 0.6.0
## Persistent path AVL. Snapshots hold a Tables root; unique-owner Document mutates in place.
import memory
import composition.delta
from animation import Property
import model
from model import DocumentData
from path import is_descendant, parent_path
from storage import Buffer, List, Pair, close_names, copied, copy_pairs, text_copy
from types import limit_exceeded, missing, max_items, invalid
from value import is_stub
from names import Name
extern func memcmp(a: const void*, b: const void*, count: usize) -> i32
## Keys order bytewise, then shorter first, as text does. Raw by_id keys are not UTF-8,
## so this compares their bytes rather than going through `str`.
func compare_keys(a: const u8[], b: const u8[]) -> i32:
let n = a.length if a.length < b.length else b.length
if n > 0:
let order = memcmp(a.data, b.data, n)
if order != 0:
return -1 if order < 0 else 1
return -1 if a.length < b.length else (1 if a.length > b.length else 0)
pub func id_key(identifier: usize) -> Buffer!:
var bytes: u8[8]
var value = (u64)identifier
var i: usize = 8
while i > 0:
i -= 1
bytes[i] = (u8)(value & 255)
value = value >> 8
return try copied(bytes)
pub struct Element:
var references: @u64
pub var identifier: usize
pub var path: Buffer
pub var kind: Buffer
pub var properties: List[Property]
pub var metadata: List[Pair]
## The `apply_cow` that created this copy, 0 for none: such an element is private
## to the tables being built, so later writes of the same apply edit it in place.
var stamp: u64
pub func init():
return
pub func close():
self.path.close()
self.kind.close()
for i in 0..<self.properties.count:
self.properties.items[i].close()
self.properties.close()
for i in 0..<self.metadata.count:
self.metadata.items[i].close()
self.metadata.close()
pub func hold_element(element: Element*):
_ = element.references.add(1, .relaxed)
pub func drop_element(element: Element*):
if element.references.sub(1, .acq_rel) == 1:
element.close()
free(element) in memory.heap
pub func own_element(source: const model.Element*) -> Element*!:
let out = try new Element() in memory.heap
out.references.store(1, .relaxed)
errdefer drop_element(out)
out.identifier = source.identifier
out.path = try source.path.copy()
out.kind = try source.kind.copy()
try out.properties.reserve(source.properties.count)
for prop in source.properties.span():
var owned = try prop.copy()
errdefer owned.close()
try out.properties.push(owned)
out.metadata = try copy_pairs(&source.metadata)
return out
pub struct ChildList:
var references: @u64
pub var paths: List[Buffer]
## The `apply_cow` that created this list, 0 for none; see append_existing_child.
var stamp: u64
pub func init():
return
pub func close():
close_names(&self.paths)
pub func hold_children(children: ChildList*):
_ = children.references.add(1, .relaxed)
pub func drop_children(children: ChildList*):
if children.references.sub(1, .acq_rel) == 1:
children.close()
free(children) in memory.heap
pub func own_children() -> ChildList*!:
let out = try new ChildList() in memory.heap
out.references.store(1, .relaxed)
return out
pub struct Asset:
var references: @u64
pub var path: Buffer
pub var mime: Buffer
pub var bytes: Buffer
pub func init():
return
pub func close():
self.path.close()
self.mime.close()
self.bytes.close()
pub func hold_asset(asset: Asset*):
_ = asset.references.add(1, .relaxed)
pub func drop_asset(asset: Asset*):
if asset.references.sub(1, .acq_rel) == 1:
asset.close()
free(asset) in memory.heap
pub struct Node:
var references: @u64
pub var key: Buffer
pub var element: Element*?
pub var children: ChildList*?
pub var path: Buffer
pub var conn_src: Buffer
pub var asset: Asset*?
pub var left: Node*?
pub var right: Node*?
pub var height: i32
pub var count: usize
pub func init():
return
pub func hold(node: Node*?) -> Node*?:
if let n = node:
_ = n.references.add(1, .relaxed)
return node
pub func drop(node: Node*?):
if let n = node:
if n.references.sub(1, .acq_rel) == 1:
drop(n.left)
drop(n.right)
if let element = n.element:
drop_element(element)
if let children = n.children:
drop_children(children)
if let asset = n.asset:
drop_asset(asset)
n.key.close()
n.path.close()
n.conn_src.close()
free(n) in memory.heap
func height_of(node: Node*?) -> i32:
let n = node else return 0
return n.height
pub func node_count(node: Node*?) -> usize:
let n = node else return 0
return n.count
func make(key: Buffer, left: Node*?, right: Node*?) -> Node*!:
var owned = key
errdefer owned.close()
let total = node_count(left) + node_count(right) + 1
if total > max_items:
error(limit_exceeded, "Prism table limit exceeded")
let hl = height_of(left)
let hr = height_of(right)
let h = hl if hl > hr else hr
let out = try new Node() in memory.heap
out.key = owned
owned = Buffer()
out.left = left
out.right = right
out.height = h + 1
out.count = total
_ = hold(left)
_ = hold(right)
out.references.store(1, .relaxed)
return out
func with_element(node: Node*, element: Element*):
node.element = element
hold_element(element)
func with_children(node: Node*, children: ChildList*):
node.children = children
hold_children(children)
func with_path(node: Node*, path: Buffer):
node.path = path
func with_conn(node: Node*, source: Buffer):
node.conn_src = source
func with_asset(node: Node*, asset: Asset*):
node.asset = asset
hold_asset(asset)
func clone_node(src: const Node*, left: Node*?, right: Node*?) -> Node*!:
var key = try src.key.copy()
let out = try make(key, left, right)
errdefer drop(out)
if let element = src.element:
with_element(out, element)
if let children = src.children:
with_children(out, children)
if src.path.used > 0:
out.path = try src.path.copy()
if src.conn_src.used > 0:
out.conn_src = try src.conn_src.copy()
if let asset = src.asset:
with_asset(out, asset)
return out
func balanced(src: const Node*, left: Node*?, right: Node*?) -> Node*!:
if height_of(left) > height_of(right) + 1:
let l = left else trap("AVL left invariant")
if height_of(l.left) >= height_of(l.right):
let r = try clone_node(src, l.right, right)
defer drop(r)
return try clone_node(l, l.left, r)
let middle = l.right else trap("AVL left-right invariant")
let a = try clone_node(l, l.left, middle.left)
defer drop(a)
let b = try clone_node(src, middle.right, right)
defer drop(b)
return try clone_node(middle, a, b)
if height_of(right) > height_of(left) + 1:
let r = right else trap("AVL right invariant")
if height_of(r.right) >= height_of(r.left):
let l = try clone_node(src, left, r.left)
defer drop(l)
return try clone_node(r, l, r.right)
let middle = r.left else trap("AVL right-left invariant")
let a = try clone_node(src, left, middle.left)
defer drop(a)
let b = try clone_node(r, middle.right, r.right)
defer drop(b)
return try clone_node(middle, a, b)
return try clone_node(src, left, right)
pub func find(root: Node*?, key: const u8[]) -> Node*?:
var cursor = root
while let n = cursor:
let order = compare_keys(key, n.key.bytes())
if order == 0:
return n
cursor = n.left if order < 0 else n.right
return none
pub func put(root: Node*?, node: Node*) -> Node*!:
if let n = root:
let order = compare_keys(node.key.bytes(), n.key.bytes())
if order == 0:
return try clone_node(node, n.left, n.right)
if order < 0:
let left = try put(n.left, node)
defer drop(left)
return try balanced(n, left, n.right)
let right = try put(n.right, node)
defer drop(right)
return try balanced(n, n.left, right)
_ = hold(node)
return node
pub func remove(root: Node*?, key: const u8[]) -> Node*?!:
let n = root else return none
let order = compare_keys(key, n.key.bytes())
if order < 0:
let left = try remove(n.left, key)
defer drop(left)
return try balanced(n, left, n.right)
if order > 0:
let right = try remove(n.right, key)
defer drop(right)
return try balanced(n, n.left, right)
if n.left == none:
return hold(n.right)
if n.right == none:
return hold(n.left)
var next = n.right else trap("AVL removal invariant")
while let l = next.left:
next = l
let right = try remove(n.right, next.key.bytes())
defer drop(right)
return try balanced(next, n.left, right)
pub func at(root: Node*?, index: usize) -> Node*?:
let n = root else return none
let left = node_count(n.left)
if index < left:
return at(n.left, index)
if index == left:
return n
return at(n.right, index - left - 1)
pub func validate(root: Node*?) -> bool:
let n = root else return true
let difference = height_of(n.left) - height_of(n.right)
let hl = height_of(n.left)
let hr = height_of(n.right)
let h = hl if hl > hr else hr
return difference >= -1 and difference <= 1 and n.height == h + 1 and n.count == node_count(n.left) + node_count(n.right) + 1 and validate(n.left) and validate(n.right)
pub struct Tables:
var references: @u64
## Nonzero while `apply_cow` builds these tables: the stamp of the lists it creates.
var stamp: u64
pub var by_path: Node*?
var by_parent: Node*?
var by_id: Node*?
var connections: Node*?
var assets: Node*?
var globs: List[Pair]
pub var bytes: usize
pub func init():
return
pub func valid(tables: const Tables*) -> bool:
return validate(tables.by_path) and validate(tables.by_parent) and validate(tables.by_id) and validate(tables.connections) and validate(tables.assets)
pub func hold_tables(tables: Tables*):
_ = tables.references.add(1, .relaxed)
pub func drop_tables(tables: Tables*):
if tables.references.sub(1, .acq_rel) == 1:
drop(tables.by_path)
drop(tables.by_parent)
drop(tables.by_id)
drop(tables.connections)
drop(tables.assets)
for i in 0..<tables.globs.count:
tables.globs.items[i].close()
tables.globs.close()
free(tables) in memory.heap
pub func empty_tables() -> Tables*!:
let out = try new Tables() in memory.heap
out.references.store(1, .relaxed)
return out
func fork(tables: const Tables*) -> Tables*!:
let out = try new Tables() in memory.heap
out.references.store(1, .relaxed)
errdefer drop_tables(out)
out.by_path = hold(tables.by_path)
out.by_parent = hold(tables.by_parent)
out.by_id = hold(tables.by_id)
out.connections = hold(tables.connections)
out.assets = hold(tables.assets)
out.globs = try copy_pairs(&tables.globs)
out.bytes = tables.bytes
return out
func replace_root(tables: Tables*, which: usize, next: Node*?):
if which == 0:
drop(tables.by_path)
tables.by_path = next
elif which == 1:
drop(tables.by_parent)
tables.by_parent = next
elif which == 2:
drop(tables.by_id)
tables.by_id = next
elif which == 3:
drop(tables.connections)
tables.connections = next
else:
drop(tables.assets)
tables.assets = next
pub func find_element(tables: const Tables*, path: str) -> Element*?:
let node = find(tables.by_path, path.bytes) else return none
return node.element
pub func children_of(tables: const Tables*, parent: str) -> ChildList*?:
let node = find(tables.by_parent, parent.bytes) else return none
return node.children
pub func element_count(tables: const Tables*) -> usize:
return node_count(tables.by_path)
pub func payload_bytes(tables: const Tables*) -> usize:
var total: usize = 0
var i: usize = 0
let n = node_count(tables.by_path)
while i < n:
if let node = at(tables.by_path, i):
if let element = node.element:
for prop in element.properties.span():
if not is_stub(&prop.value):
total += prop.value.payload.used
i += 1
return total
pub func logical_payload_bytes(tables: const Tables*) -> usize:
var total: usize = 0
var i: usize = 0
let n = node_count(tables.by_path)
while i < n:
if let node = at(tables.by_path, i):
if let element = node.element:
for prop in element.properties.span():
if is_stub(&prop.value):
if let found = prop.value.locator:
total += found.size
else:
total += prop.value.payload.used
i += 1
return total
pub func max_identifier(tables: const Tables*) -> usize:
var highest: usize = 0
var i: usize = 0
let n = node_count(tables.by_path)
while i < n:
if let node = at(tables.by_path, i):
if let element = node.element:
if element.identifier > highest:
highest = element.identifier
i += 1
return highest
pub func incoming_at(tables: const Tables*, target: str) -> str?:
let node = find(tables.connections, target.bytes) else return none
if node.conn_src.used == 0:
return none
return node.conn_src.view()
pub func path_by_id(tables: const Tables*, identifier: usize) -> str?:
var key = id_key(identifier) catch failure:
return none
defer key.close()
let node = find(tables.by_id, key.bytes()) else return none
if node.path.used == 0:
return none
return node.path.view()
func leaf_element(path: str, element: Element*) -> Node*!:
var key = try text_copy(path)
let node = try make(key, none, none)
with_element(node, element)
return node
func leaf_children(parent: str, children: ChildList*) -> Node*!:
var key = try text_copy(parent)
let node = try make(key, none, none)
with_children(node, children)
return node
func leaf_id(identifier: usize, path: str) -> Node*!:
var key = try id_key(identifier)
let node = try make(key, none, none)
errdefer drop(node)
node.path = try text_copy(path)
return node
func leaf_conn(target: str, source: str) -> Node*!:
var key = try text_copy(target)
let node = try make(key, none, none)
errdefer drop(node)
node.conn_src = try text_copy(source)
return node
func leaf_asset(path: str, asset: Asset*) -> Node*!:
var key = try text_copy(path)
let node = try make(key, none, none)
with_asset(node, asset)
return node
func drop_pending_element(element: Element*?):
if let item = element:
drop_element(item)
func drop_pending_children(children: ChildList*?):
if let item = children:
drop_children(item)
func drop_pending_asset(asset: Asset*?):
if let item = asset:
drop_asset(item)
func element_node(source: const model.Element*) -> Node*!:
let element = try own_element(source)
var pending: Element*? = element
errdefer drop_pending_element(pending)
let node = try leaf_element(source.path.view(), element)
drop_element(element)
pending = none
return node
## A node for `source` whose properties and metadata move out of it.
func moved_element_node(source: model.Element*) -> Node*!:
let out = try new Element() in memory.heap
out.references.store(1, .relaxed)
var pending: Element*? = out
errdefer drop_pending_element(pending)
out.identifier = source.identifier
out.path = try source.path.copy()
out.kind = try source.kind.copy()
out.properties = source.properties
source.properties = List[Property]()
out.metadata = source.metadata
source.metadata = List[Pair]()
let node = try leaf_element(out.path.view(), out)
drop_element(out)
pending = none
return node
func push_text(list: List[Buffer]*, path: str) -> !:
var copy = try text_copy(path)
errdefer copy.close()
try list.push(copy)
func push_buffer(list: List[Buffer]*, source: const Buffer*) -> !:
var copy = try source.copy()
errdefer copy.close()
try list.push(copy)
func parent_node(parent: str, path: str) -> Node*!:
let list = try own_children()
var pending: ChildList*? = list
errdefer drop_pending_children(pending)
try push_text(&list.paths, path)
let node = try leaf_children(parent, list)
drop_children(list)
pending = none
return node
func copied_parent_node(parent: str, existing: ChildList*, path: str, stamp: u64 = 0, fresh: bool = false) -> Node*!:
let list = try copy_child_list(existing)
list.stamp = stamp
var pending: ChildList*? = list
errdefer drop_pending_children(pending)
if fresh or child_index(list, path) == none:
try push_text(&list.paths, path)
let node = try leaf_children(parent, list)
drop_children(list)
pending = none
return node
func asset_node(path: str, mime: str, bytes: const u8[]) -> Node*!:
let held = try new Asset() in memory.heap
held.references.store(1, .relaxed)
var pending: Asset*? = held
errdefer drop_pending_asset(pending)
held.path = try text_copy(path)
held.mime = try text_copy(mime)
held.bytes = try copied(bytes)
let node = try leaf_asset(path, held)
drop_asset(held)
pending = none
return node
func child_index(children: const ChildList*, path: str) -> usize?:
for i in 0..<children.paths.count:
if children.paths.items[i].view() == path:
return i
return none
func copy_child_list(children: const ChildList*) -> ChildList*!:
let out = try own_children()
errdefer drop_children(out)
try out.paths.reserve(children.paths.count)
for path in children.paths.span():
try push_buffer(&out.paths, &path)
return out
## `fresh` says `path` had no element before this put. A child list holds exactly the
## paths of existing elements, so a fresh path cannot be listed yet and the scan for
## it is skipped: adding k children to a directory of n is O(k), not O(k * n).
func append_child(tables: Tables*, parent: str, path: str, cow: bool, fresh: bool = false) -> !:
if let existing = children_of(tables, parent):
try append_existing_child(tables, parent, path, existing, cow, fresh)
return
let node = try parent_node(parent, path)
defer drop(node)
let next = try put(tables.by_parent, node)
replace_root(tables, 1, next)
## Copy-on-write copies a list the source tables may share. A list this same apply
## already copied (its stamp) is private to the new tables and grows in place, so a
## layer adding k children to a directory of n costs O(n + k) copies, not O(k * n).
func append_existing_child(tables: Tables*, parent: str, path: str, existing: ChildList*, cow: bool, fresh: bool = false) -> !:
let private = tables.stamp != 0 and existing.stamp == tables.stamp
if (cow and not private) or existing.references.load(.relaxed) > 1:
let node = try copied_parent_node(parent, existing, path, tables.stamp, fresh)
defer drop(node)
let next = try put(tables.by_parent, node)
replace_root(tables, 1, next)
return
if fresh or child_index(existing, path) == none:
try push_text(&existing.paths, path)
let node = try leaf_children(parent, existing)
defer drop(node)
let next = try put(tables.by_parent, node)
replace_root(tables, 1, next)
func drop_child(tables: Tables*, parent: str, path: str, cow: bool) -> !:
let existing = children_of(tables, parent) else return
if child_index(existing, path) == none:
return
if cow or existing.references.load(.relaxed) > 1:
try drop_copied_child(tables, parent, existing, path)
return
let slot = child_index(existing, path) else return
existing.paths.items[slot].close()
existing.paths.remove(slot)
if existing.paths.count == 0:
let next = try remove(tables.by_parent, parent.bytes)
replace_root(tables, 1, next)
return
let node = try leaf_children(parent, existing)
defer drop(node)
let next = try put(tables.by_parent, node)
replace_root(tables, 1, next)
func drop_copied_child(tables: Tables*, parent: str, existing: ChildList*, path: str) -> !:
let kids = try copy_child_list(existing)
var pending: ChildList*? = kids
defer drop_pending_children(pending)
let slot = child_index(kids, path) else return
kids.paths.items[slot].close()
kids.paths.remove(slot)
if kids.paths.count == 0:
let next = try remove(tables.by_parent, parent.bytes)
replace_root(tables, 1, next)
return
let node = try leaf_children(parent, kids)
drop_children(kids)
pending = none
defer drop(node)
let next = try put(tables.by_parent, node)
replace_root(tables, 1, next)
pub func put_element(tables: Tables*, source: const model.Element*, cow: bool) -> !:
let path = source.path.view()
let fresh = find(tables.by_path, path.bytes) == none
let node = try element_node(source)
defer drop(node)
if let element = node.element:
element.stamp = tables.stamp
let next = try put(tables.by_path, node)
replace_root(tables, 0, next)
if source.identifier != 0:
let id_node = try leaf_id(source.identifier, path)
defer drop(id_node)
let ids = try put(tables.by_id, id_node)
replace_root(tables, 2, ids)
try append_child(tables, parent_path(path), path, cow, fresh)
pub func remove_path(tables: Tables*, path: str, cow: bool) -> !:
if let kids = children_of(tables, path):
var copies: List[Buffer]
defer close_names(&copies)
try copies.reserve(kids.paths.count)
for child in kids.paths.span():
try push_buffer(&copies, &child)
for child in copies.span():
try remove_path(tables, child.view(), cow)
if let element = find_element(tables, path):
if element.identifier != 0:
var key = try id_key(element.identifier)
defer key.close()
let ids = try remove(tables.by_id, key.bytes())
replace_root(tables, 2, ids)
let paths = try remove(tables.by_path, path.bytes)
replace_root(tables, 0, paths)
try drop_child(tables, parent_path(path), path, cow)
try remove_incident(tables, path, cow)
func remove_incident(tables: Tables*, path: str, cow: bool) -> !:
var targets: List[Buffer]
defer close_names(&targets)
var n = node_count(tables.connections)
var i: usize = 0
while i < n:
if let node = at(tables.connections, i):
if is_descendant(node.key.view(), path) or is_descendant(node.conn_src.view(), path):
try push_buffer(&targets, &node.key)
i += 1
for target in targets.span():
let next = try remove(tables.connections, target.bytes())
replace_root(tables, 3, next)
var asset_paths: List[Buffer]
defer close_names(&asset_paths)
n = node_count(tables.assets)
i = 0
while i < n:
if let node = at(tables.assets, i):
if is_descendant(node.key.view(), path):
try push_buffer(&asset_paths, &node.key)
i += 1
for asset_path in asset_paths.span():
let next = try remove(tables.assets, asset_path.bytes())
replace_root(tables, 4, next)
## Tables for a whole document at once, as a load builds them: each tree is built
## balanced from its keys in order, O(n log n) comparisons and one node per entry,
## instead of n inserts that each copy a path of nodes.
pub func from_data(data: const DocumentData*) -> Tables*!:
return try build_tables(data, none)
## `from_data` for a document its caller discards, as a load does: each element's
## properties and metadata move into the tables instead of being copied, so the
## load never holds them twice. Paths stay, for the trees built from them.
pub func adopt_data(data: DocumentData*) -> Tables*!:
return try build_tables(data, data)
func build_tables(data: const DocumentData*, moving: DocumentData*?) -> Tables*!:
let out = try empty_tables()
errdefer drop_tables(out)
let count = data.elements.count
if count > max_items:
error(limit_exceeded, "Prism table limit exceeded")
var built = Built()
defer built.close()
# Built frees what has a length, so an empty document allocates nothing.
if count > 0:
built.paths = try new Node*[count] --- in memory.heap
built.ids = try new Node*[count] --- in memory.heap
built.scratch = try new Node*[count] --- in memory.heap
for row in 0..<count:
let element = &data.elements.items[row]
var node: Node*? = none
if let source = moving:
node = try moved_element_node(&source.elements.items[row])
else:
node = try element_node(element)
built.paths[built.path_count] = node else trap("element node")
built.path_count += 1
if element.identifier != 0:
built.ids[built.id_count] = try leaf_id(element.identifier, element.path.view())
built.id_count += 1
sort_nodes(built.paths[..<built.path_count], built.scratch)
for row in 1..<built.path_count:
if compare_keys(built.paths[row - 1].key.bytes(), built.paths[row].key.bytes()) == 0:
error(invalid, "Prism document repeats an element path")
sort_nodes(built.ids[..<built.id_count], built.scratch)
out.by_id = link_balanced(built.ids, 0, built.id_count)
built.id_count = 0
out.by_parent = try children_tree(data, &built)
out.by_path = link_balanced(built.paths, 0, built.path_count)
built.path_count = 0
for connection in data.connections.span():
let node = try leaf_conn(connection.key.view(), connection.value.view())
defer drop(node)
let next = try put(out.connections, node)
replace_root(out, 3, next)
for asset in data.assets.span():
let node = try asset_node(asset.path.view(), asset.mime.view(), asset.bytes.bytes())
defer drop(node)
let next = try put(out.assets, node)
replace_root(out, 4, next)
out.bytes += asset.bytes.used
out.globs = try copy_pairs(&data.globs)
out.bytes += payload_bytes(out)
return out
## Nodes `from_data` has made and not yet linked into a tree; close drops them.
struct Built:
var paths: Node*[]
var path_count: usize
var ids: Node*[]
var id_count: usize
var scratch: Node*[]
func close():
for row in 0..<self.path_count:
drop(self.paths[row])
for row in 0..<self.id_count:
drop(self.ids[row])
if self.paths.length > 0: free(self.paths) in memory.heap
if self.ids.length > 0: free(self.ids) in memory.heap
if self.scratch.length > 0: free(self.scratch) in memory.heap
## Each parent's list of children, in document order, as one balanced tree. The
## parents are grouped by a stable sort of the elements' rows on their parent path.
func children_tree(data: const DocumentData*, built: Built*) -> Node*?!:
let count = data.elements.count
if count == 0:
return none
let rows = try new usize[count] --- in memory.heap
defer free(rows) in memory.heap
let spare = try new usize[count] --- in memory.heap
defer free(spare) in memory.heap
for row in 0..<count:
rows[row] = row
sort_by_parent(data, rows, spare)
var parents: usize = 0
errdefer drop_nodes(built.scratch[..<parents])
var start: usize = 0
while start < count:
let parent = parent_path(data.elements.items[rows[start]].path.view())
var end = start + 1
while end < count and parent_path(data.elements.items[rows[end]].path.view()) == parent:
end += 1
let list = try own_children()
var pending: ChildList*? = list
errdefer drop_pending_children(pending)
try list.paths.reserve(end - start)
for row in start..<end:
try push_text(&list.paths, data.elements.items[rows[row]].path.view())
built.scratch[parents] = try leaf_children(parent, list)
drop_children(list)
pending = none
parents += 1
start = end
return link_balanced(built.scratch, 0, parents)
func drop_nodes(nodes: Node*[]):
for node in nodes:
drop(node)
## Order `rows` by their elements' parent paths, keeping document order within one
## parent (a stable merge sort into `spare`).
func sort_by_parent(data: const DocumentData*, rows: usize[], spare: usize[]):
var width: usize = 1
while width < rows.length:
var low: usize = 0
while low < rows.length:
let middle = low + width if low + width < rows.length else rows.length
let high = low + 2 * width if low + 2 * width < rows.length else rows.length
var left = low
var right = middle
for out in low..<high:
var take_left = right >= high
if not take_left and left < middle:
let a = parent_path(data.elements.items[rows[left]].path.view())
let b = parent_path(data.elements.items[rows[right]].path.view())
take_left = compare_keys(a.bytes, b.bytes) <= 0
if take_left:
spare[out] = rows[left]
left += 1
else:
spare[out] = rows[right]
right += 1
low = high
for row in 0..<rows.length:
rows[row] = spare[row]
width *= 2
## Order `nodes` by key (a merge sort into `scratch`).
func sort_nodes(nodes: Node*[], scratch: Node*[]):
var width: usize = 1
while width < nodes.length:
var low: usize = 0
while low < nodes.length:
let middle = low + width if low + width < nodes.length else nodes.length
let high = low + 2 * width if low + 2 * width < nodes.length else nodes.length
var left = low
var right = middle
for out in low..<high:
if right >= high or (left < middle and compare_keys(nodes[left].key.bytes(), nodes[right].key.bytes()) <= 0):
scratch[out] = nodes[left]
left += 1
else:
scratch[out] = nodes[right]
right += 1
low = high
for row in 0..<nodes.length:
nodes[row] = scratch[row]
width *= 2
## Link `nodes[low..<high]`, in key order and without subtrees, into one balanced
## tree. Each node's reference moves into its parent; the root's is returned.
func link_balanced(nodes: Node*[], low: usize, high: usize) -> Node*?:
if low >= high:
return none
let middle = low + (high - low) // 2
let node = nodes[middle]
node.left = link_balanced(nodes, low, middle)
node.right = link_balanced(nodes, middle + 1, high)
let hl = height_of(node.left)
let hr = height_of(node.right)
node.height = (hl if hl > hr else hr) + 1
node.count = node_count(node.left) + node_count(node.right) + 1
return node
func emit_elements(tables: const Tables*, parent: str, output: DocumentData*) -> !:
let kids = children_of(tables, parent) else return
for child in kids.paths.span():
let path = child.view()
let row = find_element(tables, path) else continue
var source = model.Element(identifier = row.identifier)
# insert_copy clones this temporary; it is not an ownership transfer.
defer source.close()
source.path = try row.path.copy()
source.kind = try row.kind.copy()
try source.properties.reserve(row.properties.count)
for prop in row.properties.span():
var owned = try prop.copy()
errdefer owned.close()
try source.properties.push(owned)
source.metadata = try copy_pairs(&row.metadata)
try output.insert_copy(&source)
try emit_elements(tables, path, output)
pub func to_data(tables: const Tables*) -> DocumentData!:
var output = DocumentData()
errdefer output.close()
output.references.store(1, .relaxed)
try emit_elements(tables, "/", &output)
var n = node_count(tables.connections)
var i: usize = 0
while i < n:
if let node = at(tables.connections, i):
try output.connect(node.conn_src.view(), node.key.view())
i += 1
n = node_count(tables.assets)
i = 0
while i < n:
if let node = at(tables.assets, i):
if let asset = node.asset:
try output.set_asset(asset.path.view(), asset.bytes.bytes(), asset.mime.view())
i += 1
output.globs = try copy_pairs(&tables.globs)
return output
func apply_one(tables: Tables*, layer: const delta.Layer*, cow: bool) -> !:
for entry in layer.items.span():
if entry.key.cell == delta.Cell.element and entry.op.deleted:
let path = entry.key.path.view()
if find_element(tables, path) != none:
try remove_path(tables, path, cow)
for entry in layer.items.span():
if entry.key.cell == delta.Cell.disconnect:
let next = try remove(tables.connections, entry.key.path.bytes())
replace_root(tables, 3, next)
for entry in layer.items.span():
if entry.key.cell != delta.Cell.element or entry.op.deleted:
continue
let path = entry.key.path.view()
if find_element(tables, path) != none:
if entry.op.type_name.used > 0:
try set_kind(tables, path, entry.op.type_name.view(), cow)
elif not entry.op.override:
var source = model.Element(identifier = entry.op.identifier)
defer source.close()
source.path = try text_copy(path)
source.kind = try entry.op.type_name.copy()
try put_element(tables, &source, cow)
for entry in layer.items.span():
let path = entry.key.path.view()
if find_element(tables, path) == none:
continue
if entry.key.cell == delta.Cell.property:
try apply_property(tables, path, &entry, cow)
elif entry.key.cell == delta.Cell.metadata:
try apply_metadata(tables, path, &entry, cow)
elif entry.key.cell == delta.Cell.asset:
try apply_asset(tables, path, &entry, cow)
for entry in layer.items.span():
if entry.key.cell == delta.Cell.connection:
let node = try leaf_conn(entry.key.path.view(), entry.op.text.view())
defer drop(node)
let next = try put(tables.connections, node)
replace_root(tables, 3, next)
for entry in layer.items.span():
if entry.key.cell != delta.Cell.reorder:
continue
try apply_reorder(tables, entry.key.path.view(), &entry.op, cow)
func unique_element(tables: Tables*, path: str, cow: bool) -> Element*!:
let current = find_element(tables, path) else error(missing, "Prism element does not exist")
if tables.stamp != 0 and current.stamp == tables.stamp:
return current
if not cow and current.references.load(.relaxed) == 1:
return current
var source = model.Element(identifier = current.identifier)
defer source.close()
source.path = try current.path.copy()
source.kind = try current.kind.copy()
try source.properties.reserve(current.properties.count)
for prop in current.properties.span():
var owned = try prop.copy()
errdefer owned.close()
try source.properties.push(owned)
source.metadata = try copy_pairs(¤t.metadata)
let node = try element_node(&source)
defer drop(node)
let root = try put(tables.by_path, node)
replace_root(tables, 0, root)
let copy = find_element(tables, path) else error(missing, "Prism element does not exist")
copy.stamp = tables.stamp
return copy
func set_kind(tables: Tables*, path: str, name: str, cow: bool) -> !:
let element = try unique_element(tables, path, cow)
element.kind.close()
element.kind = try text_copy(name)
func apply_property(tables: Tables*, path: str, entry: const delta.Entry*, cow: bool) -> !:
let element = try unique_element(tables, path, cow)
if entry.op.deleted:
element_remove_property(element, entry.key.name.view())
return
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():
var owned = try sample.copy()
errdefer owned.close()
try prop.samples.push(owned)
try element_put_property(element, &prop)
prop.close()
prop = Property()
func element_remove_property(element: Element*, name: str):
for i in 0..<element.properties.count:
if element.properties.items[i].name.view() == name:
element.properties.items[i].close()
element.properties.remove(i)
return
func element_put_property(element: Element*, prop: const Property*) -> !:
var owned = try prop.copy()
errdefer owned.close()
for i in 0..<element.properties.count:
if element.properties.items[i].name.view() == prop.name.view():
element.properties.items[i].close()
element.properties.items[i] = owned
return
try element.properties.push(owned)
func apply_metadata(tables: Tables*, path: str, entry: const delta.Entry*, cow: bool) -> !:
let element = try unique_element(tables, path, cow)
if entry.op.deleted:
for i in 0..<element.metadata.count:
if element.metadata.items[i].key.view() == entry.key.name.view():
element.metadata.items[i].close()
element.metadata.remove(i)
return
return
var found = false
for i in 0..<element.metadata.count:
if element.metadata.items[i].key.view() == entry.key.name.view():
element.metadata.items[i].value.close()
element.metadata.items[i].value = try entry.op.text.copy()
found = true
break
if not found:
var pair = Pair()
errdefer pair.close()
pair.key = try entry.key.name.copy()
pair.value = try entry.op.text.copy()
try element.metadata.push(pair)
pair = Pair()
func apply_asset(tables: Tables*, path: str, entry: const delta.Entry*, cow: bool) -> !:
let node = try asset_node(path, entry.op.text.view(), entry.op.value.payload.bytes())
defer drop(node)
let next = try put(tables.assets, node)
replace_root(tables, 4, next)
func apply_reorder(tables: Tables*, parent: str, op: const delta.Op*, cow: bool) -> !:
let kids = try own_children()
var pending: ChildList*? = kids
errdefer drop_pending_children(pending)
var seen: List[Buffer]
defer close_names(&seen)
for child in op.children.span():
if find_element(tables, child.view()) == none:
continue
if parent_path(child.view()) != parent:
continue
try push_buffer(&kids.paths, &child)
try push_buffer(&seen, &child)
if let existing = children_of(tables, parent):
for child in existing.paths.span():
var known = false
for item in seen.span():
if item.view() == child.view():
known = true
break
if not known and find_element(tables, child.view()) != none:
try push_buffer(&kids.paths, &child)
let node = try leaf_children(parent, kids)
drop_children(kids)
pending = none
defer drop(node)
let next = try put(tables.by_parent, node)
replace_root(tables, 1, next)
pub func apply_in_place(tables: Tables*, layer: const delta.Layer*) -> !:
if tables.references.load(.relaxed) != 1:
error(limit_exceeded, "in-place table apply requires a unique owner")
try apply_one(tables, layer, false)
var apply_stamps: @u64
pub func apply_cow(tables: Tables*, layer: const delta.Layer*) -> Tables*!:
let out = try fork(tables)
errdefer drop_tables(out)
out.stamp = apply_stamps.add(1, .relaxed) + 1
try apply_one(out, layer, true)
out.stamp = 0
return out