Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-usd

Source of release 0.9.2

0.9.2 / 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