dymokomi/luce-usd
Source of release 0.9.4
0.9.4 / src / pcp / relocations.lucb
## Relocations, after Pcp_ComputeRelocationsForLayerStack and
## _FilterRelocationsForPath (pxr/usd/pcp/layerStack.cpp). A layer stack's
## relocates come from its layers' layerRelocates, strongest layer first
## for a source (prim-level relocates are ignored in USD mode). Entries
## that are invalid or conflict (two sources with one target, a target that
## is another's source or lies under one, a source under another source)
## are dropped. Each entry keeps its incremental source (as authored) and
## its origin: the source with any ancestor that is itself a relocation's
## target mapped back to where that came from.
## One relocation: `source` moves to `target` (empty_path: to nowhere).
pub struct Relocate:
pub var source: u32
pub var target: u32
pub var origin: u32
## Build `stack.relocates` from its layers.
func compute_relocations(layers: Layers*, stack: LayerStack*, problems: Problems*) -> !:
let names = layers.names
for layer in stack.layers.view():
let found = layers.field(layer, layers.layer(layer).keys.layer_relocates) else continue
let pairs = found.ids()
var at: usize = 0
while at + 1 < pairs.length:
let source = pairs[at]
let target = pairs[at + 1]
at += 2
if not valid_relocate(names, source, target):
try problems.add("Invalid authored relocation")
continue
var known = false
for relocate in stack.relocates.view(): known = known or relocate.source == source
if not known: try stack.relocates.push(Relocate(source = source, target = target, origin = source))
if stack.relocates.count == 0: return
try drop_conflicts(names, stack, problems)
for at in 0..<stack.relocates.count: stack.relocates.items[at].origin = try origin_of(names, stack.relocates.view(), stack.relocates.items[at].source, 0)
## _IsValidRelocatesEntryForComposing: absolute prim paths without variant
## selections, a source that is not a root prim, a target (unless empty)
## that is neither the source nor above or below it.
func valid_relocate(names: const Names*, source: u32, target: u32) -> bool:
if source == empty_path or not plain_prim(names, source): return false
if names.node(source).depth == 1: return false
if target == empty_path: return true
if not plain_prim(names, target) or source == target: return false
return not names.has_prefix(target, source) and not names.has_prefix(source, target)
func plain_prim(names: const Names*, path: u32) -> bool:
return names.is_absolute(path) and names.is_prim(path) and not names.has_variant_selection(path)
## _ValidateAndRemoveConflictingRelocates.
func drop_conflicts(names: Names*, stack: LayerStack*, problems: Problems*) -> !:
let relocates = stack.relocates.view()
var dropped = Growing[bool]()
defer dropped.close()
try dropped.fill(relocates.length, false)
for at in 0..<relocates.length:
let entry = relocates[at]
if entry.target != empty_path:
for other in 0..<relocates.length:
if other == at: continue
# One target for two sources: all of them go.
if relocates[other].target == entry.target: dropped.items[at] = true
# A target that is another's source: both go.
if relocates[other].source == entry.target:
dropped.items[at] = true
dropped.items[other] = true
var up = names.parent(entry.target)
while up != absolute_root and up > relative_root:
if find_source(relocates, up) != none: dropped.items[at] = true
up = names.parent(up)
var up = names.parent(entry.source)
while up > relative_root and names.node(up).depth > 1:
if find_source(relocates, up) != none: dropped.items[at] = true
up = names.parent(up)
var kept: usize = 0
for at in 0..<relocates.length:
if dropped.items[at]:
try problems.add("Conflicting relocation")
continue
stack.relocates.items[kept] = stack.relocates.items[at]
kept += 1
stack.relocates.count = kept
func find_source(relocates: const Relocate[], source: u32) -> usize?:
for at in 0..<relocates.length:
if relocates[at].source == source: return at
return none
func find_target(relocates: const Relocate[], target: u32) -> usize?:
for at in 0..<relocates.length:
if relocates[at].target == target: return at
return none
## The source's origin (_ComputeSourceOriginForTargetIfNeeded): the nearest
## ancestor (or itself) another relocation targets, replaced by that
## relocation's own origin.
func origin_of(names: Names*, relocates: const Relocate[], source: u32, depth: usize) -> u32!:
if depth > 64: return source
var up = source
while up > relative_root and up != absolute_root:
if let found = find_target(relocates, up):
let origin = try origin_of(names, relocates, relocates[found].source, depth + 1)
return try names.replace_prefix(source, up, origin)
up = names.parent(up)
return source
extend LayerStack:
## HasRelocates.
pub func has_relocates() -> bool:
return self.relocates.count > 0
## The incremental source relocated to `target`, if any.
pub func relocated_to(target: u32) -> u32?:
if target == empty_path: return none
let found = find_target(self.relocates.view(), target) else return none
return self.relocates.items[found].source
## Whether `source` is relocated (incrementally).
pub func relocates_source(source: u32) -> bool:
return find_source(self.relocates.view(), source) != none
extend Composer:
## The map of an arc from `source` to a node at `target_path`
## (_CreateMapExpressionForArc): source to target (variant selections
## stripped), after the target layer stack's relocations at and below
## the target when it has any.
func arc_map(stack: usize, source: u32, target_path: u32, offset: Offset) -> MapFunction!:
let names = self.names
let target = try names.strip_variants(target_path)
var arc = try MapFunction.of_pair(source, target, offset)
let layer_stack = self.stacks.stack(stack)
if not layer_stack.has_relocates(): return arc
defer arc.close()
var relocated = try MapFunction.deferred_of(try self.relocation_pairs(stack, target))
defer relocated.close()
return try relocated.compose(names, &arc)
## The relocations affecting namespace at and below `path`
## (_FilterRelocationsForPath): origin to target, then incremental
## source to target for targets not yet seen, and the root identity.
func relocation_pairs(stack: usize, path: u32) -> PathPairs!:
let names = self.names
let relocates = self.stacks.stack(stack).relocates.view()
var pairs = PathPairs.empty(true)
errdefer pairs.close()
for relocate in relocates:
if relocate.target == empty_path or not names.has_prefix(relocate.origin, path): continue
try pairs.sources.push(relocate.origin)
try pairs.targets.push(relocate.target)
for relocate in relocates:
if relocate.target == empty_path or not names.has_prefix(relocate.source, path): continue
var seen = false
for target in pairs.targets.view(): seen = seen or target == relocate.target
if seen: continue
try pairs.sources.push(relocate.source)
try pairs.targets.push(relocate.target)
return pairs
## A node at a relocation's target brings the relocated source
## (_EvalNodeRelocations): its other arcs are elided, and a relocate
## arc adds the source's index, which only holds opinions below it.
func eval_relocations(indexer: Indexer*, node: u32) -> !:
let index = &indexer.index
if not index.node(node).contributes(): return
let stack = index.node(node).stack
let source = self.stacks.stack(stack).relocated_to(index.node(node).path) else return
var children = Growing[u32]()
defer children.close()
try children.assign(index.node(node).children.view())
for child in children.view():
if index.node(child).arc != ArcType.variant: elide_subtree(index, self.names, child)
var options = ArcOptions.plain()
options.contribute = false
options.ancestral = true
let added = try self.add_arc(indexer, ArcType.relocate, node, (i32)node, stack, source, MapFunction.identity(), 0, namespace_depth(self.names, index.node(node).path), options)
if let relocated = added: self.elide_relocated(index, relocated)
## Elide the subtrees under `node` rooted at a relocation's source
## (_ElideRelocatedSubtrees): their opinions moved with it.
func elide_relocated(index: PrimIndex*, node: u32):
let count = index.node(node).children.count
for at in 0..<count:
let child = index.node(node).children.items[at]
if index.node(child).arc == ArcType.relocate: continue
if index.node(child).contributes() and self.stacks.stack(index.node(child).stack).relocates_source(index.node(child).path):
elide_subtree(index, self.names, child)
continue
self.elide_relocated(index, child)
## A relocation node implies its source to its grandparent, mapped
## across its parent's arc (_EvalImpliedRelocations).
func eval_implied_relocations(indexer: Indexer*, node: u32) -> !:
let index = &indexer.index
let entry = index.node(node)
if entry.arc != ArcType.relocate or entry.due_to_ancestor or entry.parent < 0: return
let parent = (u32)entry.parent
let grandparent = index.node(parent).parent
if grandparent < 0: return
let source = try index.node(parent).map_to_parent.map(self.names, index.node(node).path, false)
if source == empty_path: return
for child in index.node((u32)grandparent).children.view():
if index.node(child).path == source and index.node(child).arc == ArcType.relocate: return
var options = ArcOptions.plain()
options.contribute = false
let stack = index.node((u32)grandparent).stack
_ = try self.add_arc(indexer, ArcType.relocate, (u32)grandparent, (i32)node, stack, source, MapFunction.identity(), 0, namespace_depth(self.names, index.node((u32)grandparent).path), options)
## Whether the index is of a prim a relocation moved away
## (_ComposeIsProhibitedPrimChild): a contributing node's site is a
## relocation's source.
func prohibited(index: const PrimIndex*, node: u32) -> bool:
let entry = index.node(node)
if entry.culled: return false
if not entry.inert and self.stacks.stack(entry.stack).relocates_source(entry.path): return true
for child in entry.children.view():
if self.prohibited(index, child): return true
return false
## Cull a subtree, no longer contributing even ancestrally (_ElideSubtree
## with culling).
func elide_subtree(index: PrimIndex*, names: const Names*, node: u32):
index.set_culled(names, node)
index.nodes.items[(usize)node].restricted = 1
let count = index.nodes.items[(usize)node].children.count
for at in 0..<count: elide_subtree(index, names, index.nodes.items[(usize)node].children.items[at])