extends RefCounted
## COLLECTIONS IN THE FOLD (#120 F1, docs/node-tree-and-stacks.md §2): col.* journal
## records -> the room's collection tree. Pure and deterministic, like ShapeFold and
## OpFold, and it touches no brush: a collection is organisation (and later a stack,
## §2.1a), so a collection edit never re-folds the level.
##
## col.create {name, parent} a collection; its dot is its id
## col.set {target, name?, parent?} the latest wins, per field
## col.remove {target, hierarchy} false: its children and members move to ITS
## parent (Blender relinks, collection.cc:626-647);
## true: the whole subtree goes
## col.link {target, members} members = "g:<group>" (a brush object: its
## col.unlink {target, members} DCBrush::group), "obj:<dot>" (a scene object),
## "a:<dot>" (a placed asset) or "c:<dot>" (a
## curve); the latest wins per (col, member)
##
## A member may sit in several collections (Shift+M, Blender's Link to Collection). The
## root is Scene (""): it holds everything, and a collection whose parent is gone sits
## under the nearest live ancestor.
##
## CYCLES. A col.set parent that would make a collection its own ancestor is IGNORED, in
## (seq, author) order, so every peer drops the same record. It is reported (`ignored`),
## never silent.
const KINDS := ["col.create", "col.set", "col.remove", "col.link", "col.unlink"]
static func handles(kind: String) -> bool:
return KINDS.has(kind)
static func _before(a: Dictionary, b: Dictionary) -> bool:
if int(a["seq"]) != int(b["seq"]):
return int(a["seq"]) < int(b["seq"])
return String(a["author"]) < String(b["author"])
## Every collection's final state: {"cols": {dot: {dot, seq, author, name, parent,
## removed, hierarchy, members: {member: true}}}, "ignored": [record dots]}.
## Undone records are ignored.
static func resolve_states(records: Array) -> Dictionary:
var live: Array = []
for r: Dictionary in records:
if handles(String(r.get("kind", ""))) and not bool(r.get("undone", false)):
live.append(r)
live.sort_custom(_before)
var cols := {}
var ignored: Array = []
for r: Dictionary in live:
var kind := String(r["kind"])
var rdot := "%s:%d" % [String(r["author"]), int(r["seq"])]
if kind == "col.create":
cols[rdot] = {"dot": rdot, "seq": int(r["seq"]), "author": String(r["author"]),
"name": String(r.get("name", "Collection")), "parent": String(r.get("parent", "")),
"removed": false, "hierarchy": false, "members": {}}
continue
var t := String(r.get("target", ""))
if not cols.has(t):
continue
var c: Dictionary = cols[t]
match kind:
"col.set":
if r.has("name"):
c["name"] = String(r["name"])
if r.has("parent"):
var p := String(r["parent"])
if _would_cycle(cols, t, p):
ignored.append(rdot)
else:
c["parent"] = p
"col.remove":
c["removed"] = true
c["hierarchy"] = bool(r.get("hierarchy", false))
"col.link":
for m: Variant in r.get("members", []):
(c["members"] as Dictionary)[String(m)] = true
"col.unlink":
for m: Variant in r.get("members", []):
(c["members"] as Dictionary).erase(String(m))
return {"cols": cols, "ignored": ignored}
## Would making `p` the parent of `t` put `t` among its own ancestors?
static func _would_cycle(cols: Dictionary, t: String, p: String) -> bool:
var seen := {}
var at := p
while at != "" and cols.has(at) and not seen.has(at):
if at == t:
return true
seen[at] = true
at = String(cols[at]["parent"])
return false
## The live tree: {"cols": {dot: {name, parent, children: [dot], members: [member]}},
## "ignored": [...]}. `parent` is the EFFECTIVE parent ("" = Scene); children in creation
## order, members sorted. A collection removed with its contents kept is gone, and its
## children and members appear under its parent instead.
static func tree(records: Array) -> Dictionary:
var st := resolve_states(records)
var cols: Dictionary = st["cols"]
var out := {}
var order: Array = cols.values()
order.sort_custom(_before)
for c: Dictionary in order:
if bool(c["removed"]) or _dead(cols, String(c["dot"])):
continue
out[c["dot"]] = {"name": c["name"], "parent": _live_parent(cols, String(c["parent"])),
"children": [], "members": {}}
# Members: each collection's own, plus those of every kept-contents removal that
# lands on it.
for c: Dictionary in order:
if _dead(cols, String(c["dot"])):
continue
var home := String(c["dot"]) if out.has(c["dot"]) else _live_parent(cols, String(c["parent"]))
if home == "":
continue # Scene holds everything already
for m: String in (c["members"] as Dictionary):
(out[home]["members"] as Dictionary)[m] = true
for d: String in out:
var ms: Array = (out[d]["members"] as Dictionary).keys()
ms.sort()
out[d]["members"] = ms
for c: Dictionary in order:
var dot := String(c["dot"])
if out.has(dot) and String(out[dot]["parent"]) != "":
(out[String(out[dot]["parent"])]["children"] as Array).append(dot)
return {"cols": out, "ignored": st["ignored"]}
## Removed WITH its hierarchy, or under something that was.
static func _dead(cols: Dictionary, dot: String) -> bool:
var seen := {}
var at := dot
while at != "" and cols.has(at) and not seen.has(at):
seen[at] = true
var c: Dictionary = cols[at]
if bool(c["removed"]) and bool(c["hierarchy"]):
return true
at = String(c["parent"])
return false
## The nearest ancestor (from `p` up) that is live, or "" (Scene).
static func _live_parent(cols: Dictionary, p: String) -> String:
var seen := {}
var at := p
while at != "" and not seen.has(at):
seen[at] = true
if not cols.has(at):
return ""
var c: Dictionary = cols[at]
if not bool(c["removed"]):
return at
at = String(c["parent"])
return ""
## The members of `col`, and with `recursive` of every collection under it, once each.
static func members_of(t: Dictionary, col: String, recursive: bool) -> Array:
var cols: Dictionary = t["cols"]
if not cols.has(col):
return []
var seen := {}
var out: Array = []
var stack: Array = [col]
while not stack.is_empty():
var c: String = stack.pop_back()
for m: String in cols[c]["members"]:
if not seen.has(m):
seen[m] = true
out.append(m)
if recursive:
stack.append_array(cols[c]["children"])
out.sort()
return out
## Every live collection a member is linked into, in dot order.
static func collections_of(t: Dictionary, member: String) -> Array:
var out: Array = []
for d: String in t["cols"]:
if (t["cols"][d]["members"] as Array).has(member):
out.append(d)
out.sort()
return out