dymokomi/luce-usd
Source of release 0.9.1
## Maps between namespaces, after PcpMapFunction (pxr/usd/pcp/mapFunction.cpp):
## source → target path pairs, optionally the root identity (paths no pair
## covers map to themselves), and a time offset. A path maps through the
## pair whose source is its longest prefix; a result that a pair with a
## longer target would also claim is ambiguous and does not map. Composing
## f after g maps g's targets through f, then adds f's pairs whose sources
## g's inverse reaches and g's pairs do not already cover. A layer stack's
## relocations defer composition (DeferredComposition): such a function is
## a chain of pair sets a path goes through in turn, innermost first, and
## is folded into one set only where a single set is needed.
## One set of path pairs.
pub struct PathPairs:
pub var sources: Growing[u32]
pub var targets: Growing[u32]
pub var root_identity: bool
pub static func empty(root_identity: bool) -> PathPairs:
return PathPairs(sources = Growing[u32](), targets = Growing[u32](), root_identity = root_identity)
pub func close():
self.sources.close()
self.targets.close()
pub func copy() -> PathPairs!:
var made = PathPairs.empty(self.root_identity)
errdefer made.close()
try made.sources.assign(self.sources.view())
try made.targets.assign(self.targets.view())
return made
func is_identity() -> bool:
return self.root_identity and self.sources.count == 0
## `path` mapped from the source namespace to the target one (from
## target to source when `invert`); empty_path when it does not map.
pub func map(names: Names*, path: u32, invert: bool) -> u32!:
let from_side = self.targets.view() if invert else self.sources.view()
let to_side = self.sources.view() if invert else self.targets.view()
let best = best_match(names, path, from_side, 0)
var result = empty_path
if best == from_side.length:
if self.root_identity: result = path
else:
result = try names.replace_prefix(path, from_side[best], to_side[best])
if result == empty_path: return result
# A pair with a longer target claiming the result makes it ambiguous.
let floor = names.node(to_side[best]).depth if best < to_side.length else 0
let better = best_match(names, result, to_side, floor)
if better < to_side.length and better != best: return empty_path
return result
## `self` after `inner` (_ComposePathPairs).
func compose(names: Names*, inner: const PathPairs*) -> PathPairs!:
var made = PathPairs.empty(self.root_identity and inner.root_identity)
errdefer made.close()
for at in 0..<inner.sources.count:
try made.sources.push(inner.sources.items[at])
try made.targets.push(try self.map(names, inner.targets.items[at], false))
let covered = made.sources.count
for at in 0..<self.sources.count:
let source = try inner.map(names, self.sources.items[at], true)
if source == empty_path: continue
var known = false
for earlier in made.sources.items[..<covered]: known = known or earlier == source
if known: continue
try made.sources.push(source)
try made.targets.push(self.targets.items[at])
return made
## Whether two sets hold the same pairs.
func same_as(other: const PathPairs*) -> bool:
if self.root_identity != other.root_identity or self.sources.count != other.sources.count: return false
for at in 0..<self.sources.count:
var found = false
for there in 0..<other.sources.count:
found = found or (other.sources.items[there] == self.sources.items[at] and other.targets.items[there] == self.targets.items[at])
if not found: return false
return true
pub struct MapFunction:
## The pairs, unless composition was deferred.
pub var pairs: PathPairs
## A deferred composition's sets, outermost first (empty otherwise).
var chain: Growing[PathPairs]
pub var offset: Offset
## The identity map (PcpMapFunction::Identity).
pub static func identity() -> MapFunction:
return MapFunction(pairs = PathPairs.empty(true), chain = Growing[PathPairs](), offset = Offset.identity())
## The map of one pair; "/" to "/" becomes the root identity.
pub static func of_pair(source: u32, target: u32, offset: Offset) -> MapFunction!:
var made = MapFunction(pairs = PathPairs.empty(false), chain = Growing[PathPairs](), offset = offset)
errdefer made.close()
if source == absolute_root and target == absolute_root: made.pairs.root_identity = true
else:
try made.pairs.sources.push(source)
try made.pairs.targets.push(target)
return made
## The map of `pairs` (taken), its composition deferred
## (PcpMapFunction::DeferredComposition); the identity stays plain.
pub static func deferred_of(pairs: PathPairs) -> MapFunction!:
var owned = pairs
if owned.is_identity(): return MapFunction(pairs = owned, chain = Growing[PathPairs](), offset = Offset.identity())
var made = MapFunction(pairs = PathPairs.empty(true), chain = Growing[PathPairs](), offset = Offset.identity())
made.chain.push(owned) catch failure:
owned.close()
error(failure.code, failure.message)
return made
pub func close():
self.pairs.close()
for at in 0..<self.chain.count: self.chain.items[at].close()
self.chain.close()
pub func copy() -> MapFunction!:
var made = MapFunction(pairs = try self.pairs.copy(), chain = Growing[PathPairs](), offset = self.offset)
errdefer made.close()
for set in self.chain.view():
var copied = try set.copy()
made.chain.push(copied) catch failure:
copied.close()
error(failure.code, failure.message)
return made
func deferred() -> bool:
return self.chain.count > 0
## IsIdentity: every path maps to itself, with no offset.
pub func is_identity() -> bool:
return self.is_identity_mapping() and self.offset.is_identity()
func is_identity_mapping() -> bool:
if not self.deferred(): return self.pairs.is_identity()
for set in self.chain.view():
if not set.is_identity(): return false
return true
## HasRootIdentity.
pub func has_root_identity() -> bool:
if not self.deferred(): return self.pairs.root_identity
for set in self.chain.view():
if not set.root_identity: return false
return true
## `path` mapped from the source namespace to the target one (from
## target to source when `invert`); empty_path when it does not map.
pub func map(names: Names*, path: u32, invert: bool) -> u32!:
if not self.deferred(): return try self.pairs.map(names, path, invert)
var result = path
let count = self.chain.count
for step in 0..<count:
# Inverted: outermost first; else innermost first.
let set = &self.chain.items[step if invert else count - 1 - step]
result = try set.map(names, result, invert)
if result == empty_path: return result
return result
## `self` after `inner`: inner's source namespace to self's target one.
pub func compose(names: Names*, inner: const MapFunction*) -> MapFunction!:
if self.is_identity(): return try inner.copy()
if inner.is_identity(): return try self.copy()
let offset = self.offset.times(inner.offset)
if not self.deferred() and not inner.deferred():
return MapFunction(pairs = try self.pairs.compose(names, &inner.pairs), chain = Growing[PathPairs](), offset = offset)
var made = MapFunction(pairs = PathPairs.empty(true), chain = Growing[PathPairs](), offset = offset)
errdefer made.close()
try made.append_sets(&self)
try made.append_sets(inner)
return made
func append_sets(other: const MapFunction*) -> !:
if not other.deferred():
var copied = try other.pairs.copy()
self.chain.push(copied) catch failure:
copied.close()
error(failure.code, failure.message)
return
for set in other.chain.view():
var copied = try set.copy()
self.chain.push(copied) catch failure:
copied.close()
error(failure.code, failure.message)
## The pairs a deferred chain folds into (_GetNormalized).
pub func normalized(names: Names*) -> PathPairs!:
if not self.deferred(): return try self.pairs.copy()
var result = try self.chain.items[self.chain.count - 1].copy()
var at = self.chain.count - 1
while at > 0:
at -= 1
let folded = self.chain.items[at].compose(names, &result) catch failure:
result.close()
error(failure.code, failure.message)
result.close()
result = folded
return result
## AddRootIdentity: `/` maps to `/` too.
pub func with_root_identity(names: Names*) -> MapFunction!:
if self.has_root_identity(): return try self.copy()
var pairs = try self.normalized(names)
pairs.root_identity = true
return MapFunction(pairs = pairs, chain = Growing[PathPairs](), offset = self.offset)
## The map the other way (the offset inverted too).
pub func inverse() -> MapFunction!:
let offset = Offset(offset = -self.offset.offset / self.offset.scale, scale = 1.0 / self.offset.scale)
var made = MapFunction(pairs = PathPairs.empty(self.pairs.root_identity), chain = Growing[PathPairs](), offset = offset)
errdefer made.close()
try made.pairs.sources.assign(self.pairs.targets.view())
try made.pairs.targets.assign(self.pairs.sources.view())
var at = self.chain.count
while at > 0:
at -= 1
var flipped = PathPairs.empty(self.chain.items[at].root_identity)
try flipped.sources.assign(self.chain.items[at].targets.view())
try flipped.targets.assign(self.chain.items[at].sources.view())
made.chain.push(flipped) catch failure:
flipped.close()
error(failure.code, failure.message)
return made
## Whether two maps are the same once folded: pairs, root identity and
## offset.
pub func equals(names: Names*, other: const MapFunction*) -> bool!:
if self.offset.offset != other.offset.offset or self.offset.scale != other.offset.scale: return false
var mine = try self.normalized(names)
defer mine.close()
var theirs = try other.normalized(names)
defer theirs.close()
return mine.same_as(&theirs)
## The map of the class arc `class_arc` implied across `self`, the
## transfer from a node to its parent (PcpMapFunction::ImpliedClass):
## each class pair mapped through the transfer, plus the pairs the
## transfer gives descendants of class targets; always with the root
## identity, and the class arc's offset.
pub func implied_class(names: Names*, class_arc: const MapFunction*) -> MapFunction!:
if self.is_identity() or class_arc.is_identity(): return try class_arc.copy()
var transfer = try self.normalized(names)
defer transfer.close()
var arc = try class_arc.normalized(names)
defer arc.close()
var made = MapFunction(pairs = PathPairs.empty(true), chain = Growing[PathPairs](), offset = class_arc.offset)
errdefer made.close()
for at in 0..<arc.sources.count:
let source = try transfer.map(names, arc.sources.items[at], false)
if source == empty_path: continue
try made.pairs.sources.push(source)
try made.pairs.targets.push(try transfer.map(names, arc.targets.items[at], false))
for at in 0..<transfer.sources.count:
let transfer_source = transfer.sources.items[at]
for pair in 0..<arc.sources.count:
let class_target = arc.targets.items[pair]
if transfer_source == class_target or not names.has_prefix(transfer_source, class_target): continue
let source = try names.replace_prefix(transfer_source, class_target, arc.sources.items[pair])
if try arc.map(names, source, false) != transfer_source: continue
let mapped = try transfer.map(names, source, false)
if mapped == empty_path: continue
try made.pairs.sources.push(mapped)
try made.pairs.targets.push(transfer.targets.items[at])
return made
## `map` (taken) with the root identity added.
func with_root(names: Names*, map: MapFunction) -> MapFunction!:
var owned = map
defer owned.close()
return try owned.with_root_identity(names)
## The index in `side` of the longest path that is a prefix of `path` with
## at least `floor` depth, or side.length.
func best_match(names: Names*, path: u32, side: const u32[], floor: u32) -> usize:
var best = side.length
var best_depth: u32 = 0
for at in 0..<side.length:
let candidate = side[at]
if candidate == empty_path: continue
let depth = names.node(candidate).depth
if depth < floor: continue
if (best == side.length or depth > best_depth) and names.has_prefix(path, candidate):
best = at
best_depth = depth
return best
## Path elements that are not variant selections (PcpNode_GetNonVariantPathElementCount).
pub func namespace_depth(names: const Names*, path: u32) -> i32:
var count: i32 = 0
var at = path
while at > relative_root:
if names.kind(at) != PathKind.variant: count += 1
at = names.parent(at)
return count