dymokomi/luce-usd
Source of release 0.9.6
0.9.6 / src / pcp / build.lucb
## Building prim indexes, after Pcp_BuildPrimIndex and PcpComputePrimIndex
## (pxr/usd/pcp/primIndex.cpp). A prim's index starts as its parent's with
## every site extended by the prim's name (ancestral opinions); a variant
## selection's starts as its one site. Then tasks run in priority order
## (tasks.lucb): each node's references, payloads and variant sets, the
## variants those select. An arc to a prim that is not a root prim brings
## that prim's own ancestral opinions, so its target's index is built first
## (one stack frame down, variants left for the outer index to choose) and
## added as a subtree. The finished index culls subtrees with no opinions
## and is stored in strength order.
import strings
## The session identifier that stands for a stage's anonymous session
## layer (UsdStage::Open makes one).
pub let anonymous_session: str = "anon:session.usda"
## One level of nested index building (PcpPrimIndex_StackFrame): the graph
## and node the index being built will hang under, and the site requested.
struct Frame:
var index: const PrimIndex*
var parent: u32
var stack: usize
var path: u32
var previous: const Frame*?
## The arc the built index will hang by, and whether sites the outer
## graphs already hold are skipped.
var kind: ArcType
var skip_duplicates: bool
## The arc's map to the parent node.
var map: const MapFunction*
## A composition: the layers and layer stacks it opened, its root layer
## stack, and the indexes of the root stack's prims (each once).
pub struct Composer:
pub var names: Names*
pub var layers: Layers
pub var stacks: Stacks
pub var problems: Problems
pub var root_stack: usize
## Path texts whose prims' payloads are not loaded (a prefix each).
pub var unloaded: Growing[Growing[u8]]
## Path texts one of which a prim's must contain for its payloads to
## load (none: any).
pub var loaded_containing: Growing[Growing[u8]]
## Glob patterns one of which a prim's path must match for its
## payloads to load (none: any).
pub var loaded_matching: Growing[Growing[u8]]
## Variant fallbacks: (set, selection) token pairs, preferred first.
pub var variant_fallbacks: Growing[u32]
## The prim whose index is being built (payload loading asks about it).
var composing: u32
## Built indexes, each on the heap so pointers to them stay valid, and
## per path id the index's slot + 1 (0: not built).
var cached: Growing[PrimIndex*]
var slots: Growing[u32]
## A composition of the layer stack rooted at `root` (an identifier),
## with `session` (an identifier, or "") before it.
pub func init(names: Names*, root: str, session: str) -> !:
var layers = Layers(names)
errdefer layers.close()
var stacks = Stacks()
errdefer stacks.close()
var problems = Problems()
errdefer problems.close()
let opened = try layers.find_or_open(root)
if opened == none: error(errors.invalid, unreadable("root", root, layers.problem(root)))
let root_layer = opened else return
var session_layer: usize? = none
if session == anonymous_session:
# UsdStage::Open's empty session layer: no opinions, but the
# root layer stack differs from its root layer referenced alone.
session_layer = try layers.anonymous(session)
elif session.length > 0:
session_layer = try layers.find_or_open(session)
if session_layer == none: error(errors.invalid, unreadable("session", session, layers.problem(session)))
let root_stack = try stacks.find_or_build(&layers, root_layer, session_layer, none, &problems)
self.names = names
self.layers = layers
self.stacks = stacks
self.problems = problems
self.root_stack = root_stack
self.unloaded = Growing[Growing[u8]]()
self.loaded_containing = Growing[Growing[u8]]()
self.loaded_matching = Growing[Growing[u8]]()
self.variant_fallbacks = Growing[u32]()
self.composing = absolute_root
self.cached = Growing[PrimIndex*]()
self.slots = Growing[u32]()
pub func close():
for at in 0..<self.unloaded.count: self.unloaded.items[at].close()
self.unloaded.close()
for at in 0..<self.loaded_containing.count: self.loaded_containing.items[at].close()
self.loaded_containing.close()
for at in 0..<self.loaded_matching.count: self.loaded_matching.items[at].close()
self.loaded_matching.close()
self.variant_fallbacks.close()
for at in 0..<self.cached.count:
self.cached.items[at].close()
free(PrimIndex[](self.cached.items[at], 1)) in memory.heap
self.cached.close()
self.slots.close()
self.problems.close()
self.stacks.close()
self.layers.close()
pub func keys() -> const FieldKeys*:
return &self.layers.layer(self.stacks.stack(self.root_stack).layers.items[0]).keys
## The index of prim `path` of the root layer stack (built once):
## culled and stored in strength order (PcpComputePrimIndex).
pub func index(path: u32) -> const PrimIndex*!:
if let found = self.cached_index(path): return found
let outer = self.composing
self.composing = path
defer self.composing = outer
var built = try self.build(self.root_stack, path, none, true, true)
defer built.close()
cull(&built, self.names, self.root_stack)
built.instanceable = try self.is_instanceable(&built)
var made = try finalized(&built)
errdefer made.close()
let storage = try new PrimIndex[1] --- in memory.heap
storage[0] = made
self.cached.push(storage.data) catch failure:
free(storage) in memory.heap
error(failure.code, failure.message)
# The heap copy owns the index now.
made = PrimIndex()
while self.slots.count <= (usize)path: try self.slots.push(0)
self.slots.items[(usize)path] = (u32)self.cached.count
return storage.data
## The index of `path` if it was built.
func cached_index(path: u32) -> const PrimIndex*?:
if (usize)path >= self.slots.count or self.slots.items[(usize)path] == 0: return none
return self.cached.items[(usize)self.slots.items[(usize)path] - 1]
## The index of `path` in layer stack `stack` (Pcp_BuildPrimIndex).
## `outer`: an outermost build, which evaluates variant sets and
## implied specializes.
func build(stack: usize, path: u32, frame: const Frame*?, contribute_root: bool, outer: bool) -> PrimIndex!:
if path == absolute_root:
var index = try PrimIndex.rooted(stack, path)
index.nodes.items[0].has_specs = self.site_has_specs(stack, path)
return index
var indexer = Indexer(index = PrimIndex(), queue = Growing[Task](), frame = frame, outer = outer)
defer indexer.close()
if self.names.kind(path) == PathKind.variant:
# A variant selection's ancestral opinions come with its prim's.
indexer.index = try PrimIndex.rooted(stack, path)
indexer.index.nodes.items[0].has_specs = self.site_has_specs(stack, path)
else:
indexer.index = try self.ancestral(stack, path, frame, outer)
if not contribute_root: indexer.index.set_inert(self.names, 0)
# A prim a relocation moved away has no opinions here
# (_ElidePrimIndexIfProhibited).
if self.names.kind(path) != PathKind.variant and self.prohibited(&indexer.index, 0):
indexer.index.set_inert(self.names, 0)
let count = indexer.index.nodes.items[0].children.count
for at in 0..<count: elide_subtree(&indexer.index, self.names, indexer.index.nodes.items[0].children.items[at])
let elided = indexer.index
indexer.index = PrimIndex()
return elided
try indexer.add_tasks(0, all_tasks & ~ancestral_variant_tasks)
try self.run_tasks(&indexer)
let done = indexer.index
indexer.index = PrimIndex()
return done
## The parent's index with every site extended by the prim's name.
func ancestral(stack: usize, path: u32, frame: const Frame*?, outer: bool) -> PrimIndex!:
let parent_path = self.names.parent(path)
var index = PrimIndex()
errdefer index.close()
var instance = false
if frame == none and stack == self.root_stack:
let cached = try self.index(parent_path)
index = try copy_index(cached)
instance = cached.instanceable
else:
index = try self.build(stack, parent_path, frame, true, outer)
instance = try self.ancestor_is_instance(stack, parent_path, &index)
# Below an instance only its instanceable opinions count.
if instance: disable_non_instanceable(&index, self.names)
index.has_payloads = false
let name = self.names.name(path)
for at in 0..<index.nodes.count:
let node = &index.nodes.items[at]
node.path = path if node.path == parent_path else try self.names.child(node.path, name)
if node.has_specs: node.has_specs = self.site_has_specs(node.stack, node.path)
if at > 0:
# _ConvertNodeForChild: every node but the root now comes
# from an ancestor.
node.due_to_ancestor = true
node.direct = false
node.ancestral_arc = true
return index
## Whether the stage is its root layer alone: no sublayers, session
## layer with opinions or composition arcs, so the layer's specs are
## the stage's.
pub func is_single_layer() -> bool:
let stack = self.stacks.stack(self.root_stack)
var count = stack.layers.count
if let session = stack.session:
if self.layers.layer(session).spec_count() > 1: return false
count -= 1
if count != 1: return false
let layer = self.layers.layer(stack.root)
let keys = &layer.keys
let arcs: u32[7] = [keys.references, keys.payload, keys.inherit_paths, keys.specializes, keys.variant_set_names, keys.relocates, keys.instanceable]
for index in 0..<layer.spec_count():
let spec = layer.spec(index)
if spec.kind != SpecType.prim: continue
for field in spec.fields.view():
for key in arcs:
if field.name == key: return false
return true
## The root layer's data.
pub func root_layer() -> const LayerData*:
return self.layers.layer(self.stacks.stack(self.root_stack).root)
## Leave the payloads of prims whose path text starts with `prefix` unloaded.
pub func exclude_payloads(prefix: str) -> !:
var text = Growing[u8]()
errdefer text.close()
try text.assign(prefix.bytes)
try self.unloaded.push(text)
## Load payloads only for prims whose path text contains `part` (with
## several calls, any of them).
pub func include_payloads_containing(part: str) -> !:
var text = Growing[u8]()
errdefer text.close()
try text.assign(part.bytes)
try self.loaded_containing.push(text)
## Whether every payload loads.
func loads_all_payloads() -> bool:
return self.unloaded.count == 0 and self.loaded_containing.count == 0 and self.loaded_matching.count == 0
## Whether the payloads of the prim at `path` load.
func payload_included(path: u32) -> bool!:
var text = Growing[u8]()
defer text.close()
try self.names.write_path(path, &text)
for prefix in self.unloaded.view():
if text.count >= prefix.count and (str)text.items[..<prefix.count] == (str)prefix.view(): return false
if self.loaded_matching.count > 0:
var matched = false
for pattern in self.loaded_matching.view(): matched = matched or glob_matches(pattern.view(), text.view())
if not matched: return false
if self.loaded_containing.count == 0: return true
for part in self.loaded_containing.view():
var at: usize = 0
while at + part.count <= text.count:
if (str)text.items[at..<at + part.count] == (str)part.view(): return true
at += 1
return false
## Whether any layer of `stack` has a spec at `path` (PcpComposeSiteHasSpecs).
pub func site_has_specs(stack: usize, path: u32) -> bool:
for layer in self.stacks.stack(stack).layers.view():
if self.layers.layer(layer).find(path) != none: return true
return false
## Run the queue's tasks until none is left; tasks add nodes, and the
## nodes' own tasks.
func run_tasks(indexer: Indexer*) -> !:
while true:
let task = indexer.pop(self.names) else return
let kind = task.kind
if kind == task_relocations: try self.eval_relocations(indexer, task.node)
elif kind == task_implied_relocations: try self.eval_implied_relocations(indexer, task.node)
elif kind == task_references: try self.eval_arcs(indexer, task.node, false)
elif kind == task_payloads: try self.eval_arcs(indexer, task.node, true)
elif kind == task_inherits: try self.eval_class_arcs(indexer, task.node, ArcType.inherit)
elif kind == task_specializes: try self.eval_class_arcs(indexer, task.node, ArcType.specialize)
elif kind == task_implied_classes: try self.eval_implied_classes(indexer, task.node)
elif kind == task_implied_specializes: try self.eval_implied_specializes(indexer, task.node)
elif kind == task_variant_sets: try self.eval_variant_sets(indexer, task.node)
elif kind == task_ancestral_variant_sets: try self.eval_ancestral_variant_sets(indexer, task.node)
elif kind == task_variant_authored or kind == task_ancestral_variant_authored:
try self.eval_authored_variant(indexer, task, kind == task_ancestral_variant_authored)
elif kind == task_variant_fallback or kind == task_ancestral_variant_fallback:
try self.eval_fallback_variant(indexer, task, kind == task_ancestral_variant_fallback)
# None-found tasks only wait for retry_variants.
## A copy of `index`.
func copy_index(index: const PrimIndex*) -> PrimIndex!:
var made = PrimIndex()
errdefer made.close()
for at in 0..<index.nodes.count:
let node = &index.nodes.items[at]
var children = Growing[u32]()
errdefer children.close()
try children.assign(node.children.view())
let map = try node.map_to_parent.copy()
var copied = *node
copied.children = children
copied.map_to_parent = map
try made.nodes.push(copied)
made.instanceable = index.instanceable
made.has_payloads = index.has_payloads
return made
## `index` finalized (PcpPrimIndex_Graph::Finalize): nodes renumbered in
## strength order, and culled nodes left out unless a kept node's chain
## of origins passes through them.
func finalized(index: const PrimIndex*) -> PrimIndex!:
var order = Growing[u32]()
defer order.close()
try index.order(&order, false)
var erasable = Growing[bool]()
defer erasable.close()
for at in 0..<index.nodes.count: try erasable.push(index.nodes.items[at].culled)
for at in 0..<index.nodes.count:
if index.nodes.items[at].origin >= 0: keep_origin_chain(index, &erasable, (u32)at)
var mapping = Growing[i32]()
defer mapping.close()
try mapping.fill(index.nodes.count, -1)
var kept: i32 = 0
for node in order.view():
if erasable.items[(usize)node]: continue
mapping.items[(usize)node] = kept
kept += 1
var made = PrimIndex()
errdefer made.close()
for node in order.view():
if mapping.items[(usize)node] < 0: continue
let entry = &index.nodes.items[(usize)node]
var children = Growing[u32]()
errdefer children.close()
for child in entry.children.view():
if mapping.items[(usize)child] >= 0: try children.push((u32)mapping.items[(usize)child])
let map = try entry.map_to_parent.copy()
var copied = *entry
copied.children = children
copied.map_to_parent = map
copied.parent = mapping.items[(usize)entry.parent] if entry.parent >= 0 else -1
copied.origin = mapping.items[(usize)entry.origin] if entry.origin >= 0 else -1
try made.nodes.push(copied)
made.instanceable = index.instanceable
made.has_payloads = index.has_payloads
return made
## Culled nodes on a kept node's chain of origins, and their parents, stay
## (_ComputeEraseCulledNodeIndexMapping's processOriginChain).
func keep_origin_chain(index: const PrimIndex*, erasable: Growing[bool]*, start: u32):
var node = start
var subsequent = false
while true:
let entry = &index.nodes.items[(usize)node]
if not erasable.items[(usize)node]:
subsequent = true
elif subsequent:
var at = (i32)node
while at >= 0 and erasable.items[(usize)at]:
erasable.items[(usize)at] = false
if at != (i32)node: keep_origin_chain(index, erasable, (u32)at)
at = index.nodes.items[(usize)at].parent
if entry.origin == entry.parent or entry.origin < 0: return
node = (u32)entry.origin
## Mark subtrees without opinions culled (_CullSubtreesWithNoOpinions);
## `root_stack` is the index's own layer stack.
func cull(index: PrimIndex*, names: const Names*, root_stack: usize):
if index.nodes.count == 0: return
for child in index.nodes.items[0].children.view(): cull_subtree(index, child, names, root_stack)
func cull_subtree(index: PrimIndex*, node: u32, names: const Names*, root_stack: usize):
for child in index.nodes.items[(usize)node].children.view(): cull_subtree(index, child, names, root_stack)
if can_cull(index, node, names, root_stack): index.set_culled(names, node)
## _NodeCanBeCulled: a node stays when it is the root, when its arc was
## introduced at its own namespace depth, when it is a subroot inherit in
## the root layer stack, when a child stays, or when it contributes specs.
func can_cull(index: const PrimIndex*, node: u32, names: const Names*, root_stack: usize) -> bool:
let entry = &index.nodes.items[(usize)node]
if entry.culled: return true
if entry.parent < 0: return false
if entry.depth == namespace_depth(names, index.nodes.items[(usize)entry.parent].path): return false
if entry.arc == ArcType.inherit and entry.stack == root_stack:
# A subroot class exists in the composed scene; keep its node.
let origin = node if entry.origin == entry.parent else index.origin_root(node)
let intro = index.path_at_introduction(names, origin)
if not (names.node(intro).depth == 1 and names.is_prim(intro)): return false
for child in entry.children.view():
if not index.nodes.items[(usize)child].culled: return false
return not (entry.has_specs and entry.contributes())
## The message of a stage layer that cannot be read: which one, its path
## and why.
local var unreadable_text: u8[1536]
func unreadable(role: str, identifier: str, problem: str) -> str:
return strings.format(unreadable_text, f"cannot read the {role} layer {identifier}: {problem}") catch failure:
recover "cannot read a stage layer"