dymokomi/luce-usd
Source of release 0.9.3
## References and payloads, after _EvalRefOrPayloadArcs and _AddArc
## (pxr/usd/pcp/primIndex.cpp) and PcpComposeSiteReferences/Payloads
## (composeSite.cpp). A node's arcs are its layer stack's list ops at its
## path applied weakest layer first, each item's asset path anchored at the
## layer that authored it, and each remembering that layer for its time
## offset. An arc targets a prim of the referenced layer's own layer stack
## (the node's own, for internal references), or its defaultPrim.
## How _AddArc adds a node (_ArcOptions): whether the new site contributes
## specs, whether its ancestral opinions come along (its index is built
## and added as a subtree), whether a site some graph up the stack frames
## already holds is skipped, and the tasks queued for the new nodes.
struct ArcOptions:
var contribute: bool
var ancestral: bool
var skip_duplicates: bool
## Whether the new node takes its origin's dependency flags.
var copy_ancestor: bool
var tasks: u32
static func plain() -> ArcOptions:
return ArcOptions(contribute = true, ancestral = false, skip_duplicates = false, copy_ancestor = false, tasks = all_tasks)
## One composed arc: the item (asset anchored: its identifier's token) and
## the position in the layer stack of the layer that authored it.
struct ArcItem:
var item: ListItem
var layer: usize
extend Composer:
## Add the references (or payloads) of `node`.
func eval_arcs(indexer: Indexer*, node: u32, payloads: bool) -> !:
if not indexer.index.node(node).contributes(): return
let stack = indexer.index.node(node).stack
let path = indexer.index.node(node).path
var arcs = Growing[ArcItem]()
defer arcs.close()
try self.compose_arcs(stack, path, payloads, &arcs)
if payloads and arcs.count > 0:
indexer.index.has_payloads = true
if not try self.loads_payload(indexer, node): return
for number in 0..<arcs.count:
try self.add_ref_arc(indexer, node, arcs.items[number], (i32)number, payloads)
## Whether the node's payloads load (_EvalNodePayloads): its path mapped
## to the prim being indexed, across stack frames
## (MapNodePathToPayloadInclusionPath); a path that does not map there
## always loads.
func loads_payload(indexer: const Indexer*, node: u32) -> bool!:
if self.loads_all_payloads(): return true
var path = try self.inclusion_path(&indexer.index, node, try self.names.strip_variants(indexer.index.node(node).path))
var frame = indexer.frame
while path != empty_path:
let up = frame else break
path = try self.to_parent_inclusion(up.map, up.kind, path)
if path == empty_path: break
path = try self.inclusion_path(up.index, up.parent, path)
frame = up.previous
if path == empty_path: return true
return try self.payload_included(path)
## `path` mapped from `node` to its graph's root for payload inclusion
## (_MapPathToNodeRootPayloadInclusionPath): step by step, skipping
## internal arcs' root identities, when the map to the root leaves it
## unchanged through its root identity.
func inclusion_path(index: const PrimIndex*, node: u32, path: u32) -> u32!:
var map = try index.map_to_root(self.names, node)
defer map.close()
var mapped = try map.map(self.names, path, false)
if mapped != path or not map.has_root_identity(): return mapped
var at = node
while mapped != empty_path and at != 0:
mapped = try self.to_parent_inclusion(&index.node(at).map_to_parent, index.node(at).arc, mapped)
at = (u32)index.node(at).parent
return mapped
## `path` across one arc for payload inclusion: an internal reference's
## or payload's root identity does not count.
func to_parent_inclusion(map: const MapFunction*, arc: ArcType, path: u32) -> u32!:
if not map.has_root_identity() or (arc != ArcType.reference and arc != ArcType.payload): return try map.map(self.names, path, false)
var pairs = try map.normalized(self.names)
defer pairs.close()
pairs.root_identity = false
return try pairs.map(self.names, path, false)
## The site's reference (payload) list ops applied weakest layer first.
func compose_arcs(stack: usize, path: u32, payloads: bool, out: Growing[ArcItem]*) -> !:
let layers = self.stacks.stack(stack).layers.view()
var position = layers.length
while position > 0:
position -= 1
let layer = layers[position]
let data = self.layers.layer(layer)
let spec = data.find(path) else continue
let key = data.keys.payload if payloads else data.keys.references
let field = data.get(spec, key) else continue
if field.kind == ValueKind.payload:
# A single payload (crate 0.7 and older): an explicit list of one.
let bytes = field.bytes()
if bytes.length < 24: continue
let record = memory.read[PayloadRecord]((void*)bytes.data)
out.clear()
if record.asset != 0 or record.prim != empty_path:
let single = ListItem(a = (u64)record.asset, b = (u64)record.prim, offset = record.offset, scale = record.scale, custom = none)
if let anchored = try self.anchored_item(single, stack, layer): try out.push(ArcItem(item = anchored, layer = position))
continue
let list = field.list_op() else continue
try self.apply_arcs(list, stack, layer, position, out)
## Apply one layer's list op (SdfListOp::ApplyOperations), anchoring
## asset paths first and tagging new items with the layer; an item
## whose asset expression evaluates to nothing is left out.
func apply_arcs(list: const ListOp*, stack: usize, layer: usize, position: usize, out: Growing[ArcItem]*) -> !:
if list.explicit:
out.clear()
for item in list.items(ListPart.explicit):
let anchored = (try self.anchored_item(item, stack, layer)) else continue
if find_arc(out.view(), anchored) == none: try out.push(ArcItem(item = anchored, layer = position))
return
for item in list.items(ListPart.deleted):
let anchored = (try self.anchored_item(item, stack, layer)) else continue
if let at = find_arc(out.view(), anchored): remove_arc(out, at)
for item in list.items(ListPart.added):
let anchored = (try self.anchored_item(item, stack, layer)) else continue
if find_arc(out.view(), anchored) == none: try out.push(ArcItem(item = anchored, layer = position))
let prepended = list.items(ListPart.prepended)
var at = prepended.length
while at > 0:
at -= 1
let anchored = (try self.anchored_item(prepended[at], stack, layer)) else continue
if let found = find_arc(out.view(), anchored): remove_arc(out, found)
try out.push(ArcItem(item = anchored, layer = position))
var move = out.count - 1
while move > 0:
out.items[move] = out.items[move - 1]
move -= 1
out.items[0] = ArcItem(item = anchored, layer = position)
for item in list.items(ListPart.appended):
let anchored = (try self.anchored_item(item, stack, layer)) else continue
if let found = find_arc(out.view(), anchored): remove_arc(out, found)
try out.push(ArcItem(item = anchored, layer = position))
## `item` with its asset path anchored at `layer`, an expression first
## evaluated with the stack's variables; none when that gives nothing.
func anchored_item(item: ListItem, stack: usize, layer: usize) -> ListItem?!:
var made = item
var asset = (u32)item.a
if is_expression(self.names.text_of(asset)):
asset = try evaluate_to_string(self.names, self.names.text_of(asset), &self.stacks.stack(stack).variables)
if asset == 0: return none
made.a = (u64)(try self.anchor(asset, layer))
return made
## The token of asset `asset` (a string token) anchored at `layer`; 0
## for an empty asset path.
func anchor(asset: u32, layer: usize) -> u32!:
let text = self.names.text_of(asset)
if text.length == 0: return 0
var anchored = Growing[u8]()
defer anchored.close()
try ar.anchored(text, self.layers.identifier(layer), &anchored)
return try self.names.token((str)anchored.view())
## One reference or payload arc from `node`.
func add_ref_arc(indexer: Indexer*, node: u32, arc: ArcItem, number: i32, payload: bool) -> !:
let names = self.names
let stack = indexer.index.node(node).stack
let node_path = indexer.index.node(node).path
var prim = (u32)arc.item.b
if prim != empty_path and not (names.is_absolute(prim) and names.is_prim(prim) and not names.has_variant_selection(prim)):
try self.problems.add("Invalid reference or payload prim path")
return
let internal = arc.item.a == 0
var offset = Offset(offset = arc.item.offset, scale = arc.item.scale)
if not offset.is_valid(): offset = Offset.identity()
elif not internal: offset = self.stacks.stack(stack).offsets.items[arc.layer].times(offset)
var target_stack = stack
var target_layer = self.stacks.stack(stack).root
if not internal:
let identifier = names.text_of((u32)arc.item.a)
let opened = try self.layers.find_or_open(identifier)
if opened == none:
try self.problems.add_with("Could not open asset @", identifier)
return
target_layer = opened else return
# The referenced stack's expression variables are overridden by
# the referencing stack's.
let overrides = self.stacks.stack(stack).source
target_stack = try self.stacks.find_or_build(&self.layers, target_layer, none, overrides, &self.problems)
let source_rate = self.layers.time_codes_per_second(self.stacks.stack(stack).layers.items[arc.layer])
let target_rate = self.stacks.stack(target_stack).time_codes_per_second
if source_rate != target_rate: offset.scale = offset.scale * source_rate / target_rate
var contribute = true
if prim == empty_path:
let found = self.layers.field(target_layer, self.layers.layer(target_layer).keys.default_prim)
if found == none:
try self.problems.add("Unresolved defaultPrim")
prim = absolute_root
contribute = false
else:
let named = found else return
prim = try default_prim_path(names, named.as_token())
var map = try self.arc_map(stack, prim, node_path, offset)
# An internal arc also maps every other path to itself.
if internal: map = try with_root(names, map)
var options = ArcOptions.plain()
options.contribute = contribute
options.ancestral = not is_root_prim(names, prim)
let kind = ArcType.payload if payload else ArcType.reference
_ = try self.add_arc(indexer, kind, node, (i32)node, target_stack, prim, map, number, namespace_depth(names, node_path), options)
## Add an arc (_AddArc): unless it closes a cycle or its site is a
## duplicate to skip, a new child node, or (bringing ancestral opinions)
## its target's own index as a subtree; then queue the new nodes'
## tasks. `map` is taken. The new node, if any.
func add_arc(indexer: Indexer*, kind: ArcType, parent: u32, origin: i32, stack: usize, path: u32, map: MapFunction, sibling: i32, depth: i32, options: ArcOptions) -> u32?!:
var owned = map
let index = &indexer.index
var skip = options.skip_duplicates
if let frame = indexer.frame: skip = skip or frame.skip_duplicates
let refused = self.refuses_arc(index, kind, parent, (u32)origin, stack, path, indexer.frame, skip) catch failure:
owned.close()
error(failure.code, failure.message)
if refused:
owned.close()
return none
var added: u32 = 0
if not options.ancestral:
let node = Node(stack = stack, path = path, arc = kind, parent = (i32)parent, origin = origin, children = Growing[u32](), sibling = sibling, depth = depth, map_to_parent = owned, inert = false, culled = false, has_specs = self.site_has_specs(stack, path), restricted = 0, due_to_ancestor = false, direct = false, ancestral_arc = false)
added = try index.insert_child(self.names, parent, node)
if not options.contribute:
index.set_inert(self.names, added)
# Not even ancestrally (SetSpecContributionRestrictedDepth(1)).
index.nodes.items[(usize)added].restricted = 1
else:
let below = Frame(index = index, parent = parent, stack = stack, path = path, previous = indexer.frame, kind = kind, skip_duplicates = skip, map = &owned)
# Variants and implied specializes wait for the outer index,
# which knows stronger opinions.
var sub = self.build(stack, path, &below, options.contribute, false) catch failure:
owned.close()
error(failure.code, failure.message)
defer sub.close()
added = try append_subtree(index, self.names, parent, &sub, kind, origin, sibling, depth, owned)
if sub.has_payloads: index.has_payloads = true
# Dependency flags: a new node is direct unless it copies its
# origin's; an ancestral subtree takes them from its new root.
let entry = &index.nodes.items[(usize)added]
if options.copy_ancestor and origin >= 0:
let source = index.nodes.items[(usize)origin]
entry.due_to_ancestor = source.due_to_ancestor
entry.direct = source.direct
entry.ancestral_arc = source.ancestral_arc
else:
entry.due_to_ancestor = false
entry.direct = true
entry.ancestral_arc = index.nodes.items[(usize)parent].ancestral_arc
if options.ancestral and indexer.frame == none: spread_dependencies(index, added, entry.direct, entry.ancestral_arc)
# A nested build evaluated the subtree's expressed arcs; its
# ancestral variants are evaluated only where variants are.
var tasks = options.tasks
if options.ancestral: tasks = tasks & ~expressed_arc_tasks
if not (indexer.outer and options.ancestral): tasks = tasks & ~ancestral_variant_tasks
if not options.ancestral: tasks = tasks & ~task_implied_specializes
try indexer.add_tasks_for_node(self.names, added, tasks)
if path == absolute_root: inert_subtree(index, added, self.names)
return added
## Whether an arc must not be added: it closes a cycle (variant arcs
## never do), or with `skip` its site is one a graph up the stack
## frames already holds.
func refuses_arc(index: const PrimIndex*, kind: ArcType, parent: u32, origin: u32, stack: usize, path: u32, frame: const Frame*?, skip: bool) -> bool!:
if kind != ArcType.variant and not Composer.implied_under_relocate(index, kind, parent, origin, frame):
if try self.closes_cycle(index, parent, stack, path, frame):
try self.problems.add("Cycle detected")
return true
if not skip: return false
var graph = index
var site = path
var level = frame
while true:
if graph.node_using_site(stack, site) != none: return true
let up = level else return false
let root_path = graph.nodes.items[0].path
site = up.path if root_path == site else try self.names.replace_prefix(up.path, root_path, site)
graph = up.index
level = up.previous
## An implied class arc under a relocation's class arcs, which is no
## cycle (the XXX:RelocatesSourceNodes case of _CheckForCycle).
static func implied_under_relocate(index: const PrimIndex*, kind: ArcType, parent: u32, origin: u32, frame: const Frame*?) -> bool:
if not is_class_based(kind) or parent == origin: return false
var graph = index
var node = (i32)parent
var level = frame
while true:
# The arc to the node's parent, across stack frames.
var arc = ArcType.root
if node > 0: arc = graph.nodes.items[(usize)node].arc
elif let up = level: arc = up.kind
if arc != ArcType.inherit and arc != ArcType.specialize: return arc == ArcType.relocate
if node > 0:
node = graph.nodes.items[(usize)node].parent
else:
let up = level else return false
graph = up.index
node = (i32)up.parent
level = up.previous
## Whether an arc from `parent` to (`stack`, `path`) returns to a site
## at, above or below one on the way to the root, through every stack
## frame (_CheckForCycle).
func closes_cycle(index: const PrimIndex*, parent: u32, stack: usize, path: u32, frame: const Frame*?) -> bool!:
var graph = index
var node = (i32)parent
var site = path
var level = frame
while true:
while node >= 0:
let entry = &graph.nodes.items[(usize)node]
if entry.stack == stack and (self.names.has_prefix(entry.path, site) or self.names.has_prefix(site, entry.path)): return true
node = entry.parent
let up = level else return false
let root_path = graph.nodes.items[0].path
# The requested site with this graph's root replaced by the arc's
# target: where the arc would lead in the enclosing graph.
site = up.path if root_path == site else try self.names.replace_prefix(up.path, root_path, site)
graph = up.index
node = (i32)up.parent
level = up.previous
func find_arc(items: const ArcItem[], item: ListItem) -> usize?:
for at in 0..<items.length:
if same_item(items[at].item, item): return at
return none
func remove_arc(items: Growing[ArcItem]*, at: usize):
var index = at
while index + 1 < items.count:
items.items[index] = items.items[index + 1]
index += 1
items.count -= 1
## Append `sub`'s nodes under `parent`, its root reached by the given arc
## (`map` taken); the new root's index.
func append_subtree(index: PrimIndex*, names: const Names*, parent: u32, sub: const PrimIndex*, kind: ArcType, origin: i32, sibling: i32, depth: i32, map: MapFunction) -> u32!:
var owned = map
errdefer owned.close()
let base = (u32)index.nodes.count
for at in 0..<sub.nodes.count:
let node = &sub.nodes.items[at]
var children = Growing[u32]()
errdefer children.close()
for child in node.children.view(): try children.push(child + base)
let root = at == 0
var node_map = MapFunction.identity()
if root:
node_map = owned
owned = MapFunction.identity()
else:
node_map = try node.map_to_parent.copy()
index.nodes.push(Node(stack = node.stack, path = node.path, arc = kind if root else node.arc, parent = (i32)parent if root else node.parent + (i32)base, origin = origin if root else (node.origin + (i32)base if node.origin >= 0 else -1), children = children, sibling = sibling if root else node.sibling, depth = depth if root else node.depth, map_to_parent = node_map, inert = node.inert, culled = node.culled, has_specs = node.has_specs, restricted = node.restricted, due_to_ancestor = node.due_to_ancestor, direct = node.direct, ancestral_arc = node.ancestral_arc)) catch failure:
node_map.close()
error(failure.code, failure.message)
try index.link_child(names, parent, base)
return base
## Make a node and everything under it inert (_InertSubtree).
func inert_subtree(index: PrimIndex*, node: u32, names: const Names*):
index.set_inert(names, node)
for child in index.nodes.items[(usize)node].children.view(): inert_subtree(index, child, names)
## A layer's defaultPrim as a path: a root prim's name, or a prim path
## (SdfLayer::GetDefaultPrimAsPath).
func default_prim_path(names: Names*, token: u32) -> u32!:
let text = names.text_of(token)
if text.length > 0 and text.bytes[0] == '/': return try names.parse_path(text)
for byte in text.bytes:
if byte == '/': return try names.make_absolute(try names.parse_path(text), absolute_root)
return try names.child(absolute_root, token)
## Whether a path is a root prim's (SdfPath::IsRootPrimPath).
func is_root_prim(names: const Names*, path: u32) -> bool:
return names.node(path).depth == 1 and names.is_prim(path)
## Give a subtree its new root's dependency flags too.
func spread_dependencies(index: PrimIndex*, node: u32, direct: bool, ancestral: bool):
let entry = &index.nodes.items[(usize)node]
entry.direct = entry.direct or direct
entry.ancestral_arc = entry.ancestral_arc or ancestral
for child in index.nodes.items[(usize)node].children.view(): spread_dependencies(index, child, direct, ancestral)