dymokomi/luce-usd
Source of release 0.9.3
0.9.3 / src / sdf / names / path_ops.lucb
## Path algebra over ids, after SdfPath's HasPrefix, ReplacePrefix,
## StripAllVariantSelections and MakeAbsolutePath (pxr/usd/sdf/path.cpp).
## Composition maps namespaces with these; a rebuilt path re-interns each
## element, so the result is again one id per distinct path.
extend Names:
## The ancestor of `path` at `depth` (the roots are depth 0).
pub func ancestor_at(path: u32, depth: u32) -> u32:
var at = path
while self.node(at).depth > depth: at = self.node(at).parent
return at
## Whether `prefix` is `path` or one of its ancestors. The empty path is
## nobody's prefix.
pub func has_prefix(path: u32, prefix: u32) -> bool:
if path == empty_path or prefix == empty_path: return false
let want = self.node(prefix)
let have = self.node(path)
if want.absolute != have.absolute or want.depth > have.depth: return false
return self.ancestor_at(path, want.depth) == prefix
## `path` with its prefix `prefix` replaced by `replacement`, and every target path
## inside it too; `path` itself when `prefix` is not its prefix.
pub func replace_prefix(path: u32, prefix: u32, replacement: u32) -> u32!:
if path == empty_path or prefix == replacement: return path
if self.has_prefix(path, prefix):
return try self.rebuilt(path, self.node(prefix).depth, replacement, prefix, replacement)
if not self.has_target(path): return path
let root = absolute_root if self.node(path).absolute else relative_root
return try self.rebuilt(path, 0, root, prefix, replacement)
## `path` with every variant selection removed, targets included.
pub func strip_variants(path: u32) -> u32!:
if path <= relative_root: return path
var chain: u32[4096] = ---
let count = try self.chain_of(path, 0, chain)
var at = absolute_root if self.node(path).absolute else relative_root
var index = count
while index > 0:
index -= 1
let node = self.node(chain[index])
if node.kind == PathKind.variant: continue
var element = node.element
if node.kind == PathKind.target or node.kind == PathKind.mapper: element = try self.strip_variants(element)
at = try self.find_or_add(at, node.kind, element, node.extra)
return at
## `path` anchored at the prim path `anchor` when it is relative: `..`
## steps to the parent prim. Target paths inside are anchored too.
pub func make_absolute(path: u32, anchor: u32) -> u32!:
if path == empty_path or self.node(path).absolute: return path
if path == relative_root: return anchor
var chain: u32[4096] = ---
let count = try self.chain_of(path, 0, chain)
var at = anchor
var index = count
while index > 0:
index -= 1
let node = self.node(chain[index])
if node.kind == PathKind.prim and node.element == self.dot_dot:
if at == absolute_root: error(errors.invalid, "a relative path climbs above the root")
at = self.node(self.prim_part(at)).parent
continue
var element = node.element
if node.kind == PathKind.target or node.kind == PathKind.mapper: element = try self.make_absolute(element, anchor)
at = try self.find_or_add(at, node.kind, element, node.extra)
return at
## `path`'s elements below `depth`, re-appended onto `base`, with target
## paths' `prefix` prefixes replaced by `replacement`.
func rebuilt(path: u32, depth: u32, base: u32, prefix: u32, replacement: u32) -> u32!:
var chain: u32[4096] = ---
let count = try self.chain_of(path, depth, chain)
var at = base
var index = count
while index > 0:
index -= 1
let node = self.node(chain[index])
var element = node.element
if node.kind == PathKind.target or node.kind == PathKind.mapper: element = try self.replace_prefix(element, prefix, replacement)
at = try self.find_or_add(at, node.kind, element, node.extra)
return at
## The nodes of `path` deeper than `depth`, deepest first; their count.
func chain_of(path: u32, depth: u32, chain: u32[]) -> usize!:
var count: usize = 0
var at = path
while self.node(at).depth > depth:
if count == chain.length: error(errors.limit, "a path deeper than 4096 elements")
chain[count] = at
count += 1
at = self.node(at).parent
return count
func has_target(path: u32) -> bool:
var at = path
while at > relative_root:
let kind = self.node(at).kind
if kind == PathKind.target or kind == PathKind.mapper: return true
at = self.node(at).parent
return false
## `path` relative to the prim (or variant, or root) path `anchor`, with
## the fewest `..` steps (SdfPath::MakeRelativePath).
pub func make_relative(path: u32, anchor: u32) -> u32!:
if path == empty_path: return empty_path
if not self.node(path).absolute:
return try self.make_relative(try self.make_absolute(path, anchor), anchor)
var chain: u32[4096] = ---
let prim = self.prim_part(path)
# The property part, deepest first.
var tail: u32[64] = ---
var tail_count: usize = 0
var at = path
while at != prim:
if tail_count == tail.length: error(errors.limit, "a property path too deep")
tail[tail_count] = at
tail_count += 1
at = self.node(at).parent
var this_node = prim
var anchor_node = anchor
var count: usize = 0
var dot_dots: usize = 0
while self.node(this_node).depth > self.node(anchor_node).depth:
chain[count] = this_node
count += 1
this_node = self.node(this_node).parent
while self.node(this_node).depth < self.node(anchor_node).depth:
dot_dots += 1
anchor_node = self.node(anchor_node).parent
while this_node != anchor_node:
dot_dots += 1
chain[count] = this_node
count += 1
this_node = self.node(this_node).parent
anchor_node = self.node(anchor_node).parent
var result = relative_root
for _ in 0..<dot_dots: result = try self.child(result, self.dot_dot)
var index = count
while index > 0:
index -= 1
let node = self.node(chain[index])
result = try self.find_or_add(result, node.kind, node.element, node.extra)
index = tail_count
while index > 0:
index -= 1
let node = self.node(tail[index])
result = try self.find_or_add(result, node.kind, node.element, node.extra)
return result
## SdfPath's order: absolute before relative, the prim part before the
## property part, then element by element from the root (kinds in node
## type order, names by bytes, targets by this order), a prefix first.
pub func path_less(left: u32, right: u32) -> bool:
if left == right: return false
if left == empty_path or right == empty_path: return left == empty_path
let l_absolute = self.node(left).absolute
let r_absolute = self.node(right).absolute
if l_absolute != r_absolute: return l_absolute
let l_prim = self.prim_part(left)
let r_prim = self.prim_part(right)
if l_prim != r_prim: return self.chain_less(l_prim, r_prim, 0)
return self.chain_less(left, right, self.node(l_prim).depth)
## The order of two paths over their nodes deeper than `base`.
func chain_less(left: u32, right: u32, base: u32) -> bool:
let l_depth = self.node(left).depth
let r_depth = self.node(right).depth
if l_depth == base or r_depth == base: return l_depth == base and r_depth != base
var l = left
var r = right
while self.node(l).depth > self.node(r).depth: l = self.node(l).parent
while self.node(r).depth > self.node(l).depth: r = self.node(r).parent
if l == r: return l_depth < r_depth
while self.node(l).parent != self.node(r).parent:
l = self.node(l).parent
r = self.node(r).parent
return self.node_less(l, r)
## Two sibling nodes: by kind, then by content.
func node_less(left: u32, right: u32) -> bool:
let a = self.node(left)
let b = self.node(right)
if a.kind != b.kind: return (u8)a.kind < (u8)b.kind
match a.kind:
.variant:
let set_a = self.text_of(a.element)
let set_b = self.text_of(b.element)
if set_a != set_b: return bytes_less(set_a, set_b)
return bytes_less(self.text_of(a.extra), self.text_of(b.extra))
.target, .mapper:
return self.path_less(a.element, b.element)
.expression, .root:
return false
_:
return bytes_less(self.text_of(a.element), self.text_of(b.element))
func bytes_less(a: str, b: str) -> bool:
let common = a.length if a.length < b.length else b.length
for index in 0..<common:
if a.bytes[index] != b.bytes[index]: return a.bytes[index] < b.bytes[index]
return a.length < b.length