dymokomi/luce-usd
Source of release 0.9.6
0.9.6 / src / pcp / graph.lucb
## A prim index's node graph, after PcpPrimIndex_Graph and PcpNodeRef
## (pxr/usd/pcp/primIndex_Graph.cpp, node.cpp, strengthOrdering.cpp). Each
## node is a site (a layer stack and a path in it) reached from its parent
## by an arc. A parent's children are kept strongest first, so the graph's
## strength order is its depth-first pre-order: siblings compare by arc type,
## then the namespace depth the arc was introduced at (deeper is stronger),
## then their origins' strength, then their order among the arcs authored.
pub struct Node:
pub var stack: usize
pub var path: u32
pub var arc: ArcType
## -1 for the root.
pub var parent: i32
## The node whose opinion introduced this arc (the parent, for direct arcs).
pub var origin: i32
pub var children: Growing[u32]
## The arc's position among its origin's arcs of its type.
pub var sibling: i32
## Non-variant path elements of the path the arc was introduced at.
pub var depth: i32
pub var map_to_parent: MapFunction
pub var inert: bool
pub var culled: bool
pub var has_specs: bool
## The path depth at which the node was first kept from contributing
## (GetSpecContributionRestrictedDepth); 0 while it is not.
pub var restricted: u32
## Whether the node came with a namespace ancestor's index
## (IsDueToAncestor), and whether it or an arc above it was added
## directly or ancestrally (HasTransitiveDirect/AncestralDependency).
pub var due_to_ancestor: bool
pub var direct: bool
pub var ancestral_arc: bool
pub func close():
self.children.close()
self.map_to_parent.close()
## PcpNodeRef::CanContributeSpecs (Usd mode: no permissions).
pub func contributes() -> bool:
return not self.inert and not self.culled
## The composed index of one prim.
pub struct PrimIndex:
pub var nodes: Growing[Node]
## Whether the prim is an instance (Pcp_PrimIndexIsInstanceable).
pub var instanceable: bool
## Whether this prim's own nodes author payloads (HasAnyPayloads).
pub var has_payloads: bool
pub func init():
self.nodes = Growing[Node]()
self.instanceable = false
self.has_payloads = false
pub func close():
for at in 0..<self.nodes.count: self.nodes.items[at].close()
self.nodes.close()
pub func node(index: u32) -> const Node*:
return &self.nodes.items[(usize)index]
## The root node alone at `path` of layer stack `stack`.
pub static func rooted(stack: usize, path: u32) -> PrimIndex!:
var index = PrimIndex()
errdefer index.close()
try index.nodes.push(Node(stack = stack, path = path, arc = ArcType.root, parent = -1, origin = -1, children = Growing[u32](), sibling = 0, depth = 0, map_to_parent = MapFunction.identity(), inert = false, culled = false, has_specs = false, restricted = 0, due_to_ancestor = false, direct = false, ancestral_arc = false))
return index
## Nodes strongest first (pre-order), culled subtrees included unless
## `skip_culled`.
pub func order(out: Growing[u32]*, skip_culled: bool) -> !:
out.clear()
if self.nodes.count > 0: try self.visit(0, out, skip_culled)
func visit(node: u32, out: Growing[u32]*, skip_culled: bool) -> !:
if skip_culled and self.nodes.items[(usize)node].culled: return
try out.push(node)
for child in self.nodes.items[(usize)node].children.view(): try self.visit(child, out, skip_culled)
## A node's map to the root's namespace (PcpNodeRef::GetMapToRoot).
pub func map_to_root(names: Names*, node: u32) -> MapFunction!:
var made = try self.nodes.items[(usize)node].map_to_parent.copy()
var at = self.nodes.items[(usize)node].parent
while at >= 0:
let parent = &self.nodes.items[(usize)at]
let composed = parent.map_to_parent.compose(names, &made) catch failure:
made.close()
error(failure.code, failure.message)
made.close()
made = composed
at = parent.parent
return made
## A node's time offset to the root's (the offset of map_to_root),
## without composing the path maps.
pub func offset_to_root(node: u32) -> Offset:
var offset = self.nodes.items[(usize)node].map_to_parent.offset
var at = self.nodes.items[(usize)node].parent
while at >= 0:
let parent = &self.nodes.items[(usize)at]
offset = parent.map_to_parent.offset.times(offset)
at = parent.parent
return offset
## Add `node` (taken) as a child of `parent`, among its siblings by
## strength; its index.
pub func insert_child(names: const Names*, parent: u32, node: Node) -> u32!:
var owned = node
errdefer owned.close()
owned.parent = (i32)parent
let index = (u32)self.nodes.count
try self.nodes.push(owned)
errdefer self.nodes.count -= 1
try self.link_child(names, parent, index)
return index
## List node `index` among `parent`'s children by strength
## (_InsertChildInStrengthOrder: first, last, else before the first
## weaker one).
pub func link_child(names: const Names*, parent: u32, index: u32) -> !:
let count = self.nodes.items[(usize)parent].children.count
var at = count
if count > 0:
let children = self.nodes.items[(usize)parent].children.view()
if self.compare_siblings(names, index, children[0]) < 0: at = 0
elif self.compare_siblings(names, index, children[count - 1]) < 0:
at = 1
while at < count and not (self.compare_siblings(names, index, children[at]) < 0): at += 1
let children = &self.nodes.items[(usize)parent].children
try children.push(index)
var move = children.count - 1
while move > at:
children.items[move] = children.items[move - 1]
move -= 1
children.items[at] = index
## The first node of the site that is neither inert nor culled
## (PcpPrimIndex_Graph::GetNodeUsingSite).
pub func node_using_site(stack: usize, path: u32) -> u32?:
for at in 0..<self.nodes.count:
let node = &self.nodes.items[at]
if not node.inert and not node.culled and node.stack == stack and node.path == path: return (u32)at
return none
## The child of `parent` at the site, if any (_FindMatchingChild).
pub func matching_child(parent: u32, stack: usize, path: u32) -> u32?:
for child in self.nodes.items[(usize)parent].children.view():
let node = &self.nodes.items[(usize)child]
if node.stack == stack and node.path == path: return child
return none
## Make `node` inert, recording where it was first restricted
## (PcpNodeRef::SetInert).
pub func set_inert(names: const Names*, node: u32):
let entry = &self.nodes.items[(usize)node]
let was = entry.inert or entry.culled
entry.inert = true
if not was and entry.restricted == 0: entry.restricted = names.node(entry.path).depth
## Mark `node` culled, recording where it was first restricted.
pub func set_culled(names: const Names*, node: u32):
let entry = &self.nodes.items[(usize)node]
if entry.culled: return
if entry.restricted == 0: entry.restricted = names.node(entry.path).depth
entry.culled = true
## Whether `node` may contribute opinions at the ancestral `path`
## (_NodeCanContributeAncestralOpinions).
pub func contributes_at(names: const Names*, node: u32, path: u32) -> bool:
let restricted = self.nodes.items[(usize)node].restricted
return restricted == 0 or restricted > names.node(path).depth
## Whether a node is, or lies under, an inherit added at this prim.
pub func due_to_direct_inherit(node: u32) -> bool:
var at = (i32)node
while at >= 0:
let entry = &self.nodes.items[(usize)at]
if entry.arc == ArcType.inherit and not entry.due_to_ancestor: return true
at = entry.parent
return false
## The node's path at the namespace depth its arc was introduced at
## (GetPathAtIntroduction): variant selections above that depth stay.
pub func path_at_introduction(names: const Names*, node: u32) -> u32:
let entry = &self.nodes.items[(usize)node]
if entry.parent < 0: return entry.path
var below = namespace_depth(names, self.nodes.items[(usize)entry.parent].path) - entry.depth
var path = entry.path
while below > 0:
while names.kind(path) == PathKind.variant: path = names.parent(path)
path = names.parent(path)
below -= 1
return path