Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-usd

Source of release 0.9.2

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