Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-usd

Source of release 0.9.3

0.9.3 / src / pcp / arcs.lucb

## References and payloads, after _EvalRefOrPayloadArcs and _AddArc
## (pxr/usd/pcp/primIndex.cpp) and PcpComposeSiteReferences/Payloads
## (composeSite.cpp). A node's arcs are its layer stack's list ops at its
## path applied weakest layer first, each item's asset path anchored at the
## layer that authored it, and each remembering that layer for its time
## offset. An arc targets a prim of the referenced layer's own layer stack
## (the node's own, for internal references), or its defaultPrim.

## How _AddArc adds a node (_ArcOptions): whether the new site contributes
## specs, whether its ancestral opinions come along (its index is built
## and added as a subtree), whether a site some graph up the stack frames
## already holds is skipped, and the tasks queued for the new nodes.
struct ArcOptions:
    var contribute: bool
    var ancestral: bool
    var skip_duplicates: bool
    ## Whether the new node takes its origin's dependency flags.
    var copy_ancestor: bool
    var tasks: u32

    static func plain() -> ArcOptions:
        return ArcOptions(contribute = true, ancestral = false, skip_duplicates = false, copy_ancestor = false, tasks = all_tasks)

## One composed arc: the item (asset anchored: its identifier's token) and
## the position in the layer stack of the layer that authored it.
struct ArcItem:
    var item: ListItem
    var layer: usize

extend Composer:
    ## Add the references (or payloads) of `node`.
    func eval_arcs(indexer: Indexer*, node: u32, payloads: bool) -> !:
        if not indexer.index.node(node).contributes(): return
        let stack = indexer.index.node(node).stack
        let path = indexer.index.node(node).path
        var arcs = Growing[ArcItem]()
        defer arcs.close()
        try self.compose_arcs(stack, path, payloads, &arcs)
        if payloads and arcs.count > 0:
            indexer.index.has_payloads = true
            if not try self.loads_payload(indexer, node): return
        for number in 0..<arcs.count:
            try self.add_ref_arc(indexer, node, arcs.items[number], (i32)number, payloads)

    ## Whether the node's payloads load (_EvalNodePayloads): its path mapped
    ## to the prim being indexed, across stack frames
    ## (MapNodePathToPayloadInclusionPath); a path that does not map there
    ## always loads.
    func loads_payload(indexer: const Indexer*, node: u32) -> bool!:
        if self.loads_all_payloads(): return true
        var path = try self.inclusion_path(&indexer.index, node, try self.names.strip_variants(indexer.index.node(node).path))
        var frame = indexer.frame
        while path != empty_path:
            let up = frame else break
            path = try self.to_parent_inclusion(up.map, up.kind, path)
            if path == empty_path: break
            path = try self.inclusion_path(up.index, up.parent, path)
            frame = up.previous
        if path == empty_path: return true
        return try self.payload_included(path)

    ## `path` mapped from `node` to its graph's root for payload inclusion
    ## (_MapPathToNodeRootPayloadInclusionPath): step by step, skipping
    ## internal arcs' root identities, when the map to the root leaves it
    ## unchanged through its root identity.
    func inclusion_path(index: const PrimIndex*, node: u32, path: u32) -> u32!:
        var map = try index.map_to_root(self.names, node)
        defer map.close()
        var mapped = try map.map(self.names, path, false)
        if mapped != path or not map.has_root_identity(): return mapped
        var at = node
        while mapped != empty_path and at != 0:
            mapped = try self.to_parent_inclusion(&index.node(at).map_to_parent, index.node(at).arc, mapped)
            at = (u32)index.node(at).parent
        return mapped

    ## `path` across one arc for payload inclusion: an internal reference's
    ## or payload's root identity does not count.
    func to_parent_inclusion(map: const MapFunction*, arc: ArcType, path: u32) -> u32!:
        if not map.has_root_identity() or (arc != ArcType.reference and arc != ArcType.payload): return try map.map(self.names, path, false)
        var pairs = try map.normalized(self.names)
        defer pairs.close()
        pairs.root_identity = false
        return try pairs.map(self.names, path, false)

    ## The site's reference (payload) list ops applied weakest layer first.
    func compose_arcs(stack: usize, path: u32, payloads: bool, out: Growing[ArcItem]*) -> !:
        let layers = self.stacks.stack(stack).layers.view()
        var position = layers.length
        while position > 0:
            position -= 1
            let layer = layers[position]
            let data = self.layers.layer(layer)
            let spec = data.find(path) else continue
            let key = data.keys.payload if payloads else data.keys.references
            let field = data.get(spec, key) else continue
            if field.kind == ValueKind.payload:
                # A single payload (crate 0.7 and older): an explicit list of one.
                let bytes = field.bytes()
                if bytes.length < 24: continue
                let record = memory.read[PayloadRecord]((void*)bytes.data)
                out.clear()
                if record.asset != 0 or record.prim != empty_path:
                    let single = ListItem(a = (u64)record.asset, b = (u64)record.prim, offset = record.offset, scale = record.scale, custom = none)
                    if let anchored = try self.anchored_item(single, stack, layer): try out.push(ArcItem(item = anchored, layer = position))
                continue
            let list = field.list_op() else continue
            try self.apply_arcs(list, stack, layer, position, out)

    ## Apply one layer's list op (SdfListOp::ApplyOperations), anchoring
    ## asset paths first and tagging new items with the layer; an item
    ## whose asset expression evaluates to nothing is left out.
    func apply_arcs(list: const ListOp*, stack: usize, layer: usize, position: usize, out: Growing[ArcItem]*) -> !:
        if list.explicit:
            out.clear()
            for item in list.items(ListPart.explicit):
                let anchored = (try self.anchored_item(item, stack, layer)) else continue
                if find_arc(out.view(), anchored) == none: try out.push(ArcItem(item = anchored, layer = position))
            return
        for item in list.items(ListPart.deleted):
            let anchored = (try self.anchored_item(item, stack, layer)) else continue
            if let at = find_arc(out.view(), anchored): remove_arc(out, at)
        for item in list.items(ListPart.added):
            let anchored = (try self.anchored_item(item, stack, layer)) else continue
            if find_arc(out.view(), anchored) == none: try out.push(ArcItem(item = anchored, layer = position))
        let prepended = list.items(ListPart.prepended)
        var at = prepended.length
        while at > 0:
            at -= 1
            let anchored = (try self.anchored_item(prepended[at], stack, layer)) else continue
            if let found = find_arc(out.view(), anchored): remove_arc(out, found)
            try out.push(ArcItem(item = anchored, layer = position))
            var move = out.count - 1
            while move > 0:
                out.items[move] = out.items[move - 1]
                move -= 1
            out.items[0] = ArcItem(item = anchored, layer = position)
        for item in list.items(ListPart.appended):
            let anchored = (try self.anchored_item(item, stack, layer)) else continue
            if let found = find_arc(out.view(), anchored): remove_arc(out, found)
            try out.push(ArcItem(item = anchored, layer = position))

    ## `item` with its asset path anchored at `layer`, an expression first
    ## evaluated with the stack's variables; none when that gives nothing.
    func anchored_item(item: ListItem, stack: usize, layer: usize) -> ListItem?!:
        var made = item
        var asset = (u32)item.a
        if is_expression(self.names.text_of(asset)):
            asset = try evaluate_to_string(self.names, self.names.text_of(asset), &self.stacks.stack(stack).variables)
            if asset == 0: return none
        made.a = (u64)(try self.anchor(asset, layer))
        return made

    ## The token of asset `asset` (a string token) anchored at `layer`; 0
    ## for an empty asset path.
    func anchor(asset: u32, layer: usize) -> u32!:
        let text = self.names.text_of(asset)
        if text.length == 0: return 0
        var anchored = Growing[u8]()
        defer anchored.close()
        try ar.anchored(text, self.layers.identifier(layer), &anchored)
        return try self.names.token((str)anchored.view())

    ## One reference or payload arc from `node`.
    func add_ref_arc(indexer: Indexer*, node: u32, arc: ArcItem, number: i32, payload: bool) -> !:
        let names = self.names
        let stack = indexer.index.node(node).stack
        let node_path = indexer.index.node(node).path
        var prim = (u32)arc.item.b
        if prim != empty_path and not (names.is_absolute(prim) and names.is_prim(prim) and not names.has_variant_selection(prim)):
            try self.problems.add("Invalid reference or payload prim path")
            return
        let internal = arc.item.a == 0
        var offset = Offset(offset = arc.item.offset, scale = arc.item.scale)
        if not offset.is_valid(): offset = Offset.identity()
        elif not internal: offset = self.stacks.stack(stack).offsets.items[arc.layer].times(offset)
        var target_stack = stack
        var target_layer = self.stacks.stack(stack).root
        if not internal:
            let identifier = names.text_of((u32)arc.item.a)
            let opened = try self.layers.find_or_open(identifier)
            if opened == none:
                try self.problems.add_with("Could not open asset @", identifier)
                return
            target_layer = opened else return
            # The referenced stack's expression variables are overridden by
            # the referencing stack's.
            let overrides = self.stacks.stack(stack).source
            target_stack = try self.stacks.find_or_build(&self.layers, target_layer, none, overrides, &self.problems)
            let source_rate = self.layers.time_codes_per_second(self.stacks.stack(stack).layers.items[arc.layer])
            let target_rate = self.stacks.stack(target_stack).time_codes_per_second
            if source_rate != target_rate: offset.scale = offset.scale * source_rate / target_rate
        var contribute = true
        if prim == empty_path:
            let found = self.layers.field(target_layer, self.layers.layer(target_layer).keys.default_prim)
            if found == none:
                try self.problems.add("Unresolved defaultPrim")
                prim = absolute_root
                contribute = false
            else:
                let named = found else return
                prim = try default_prim_path(names, named.as_token())
        var map = try self.arc_map(stack, prim, node_path, offset)
        # An internal arc also maps every other path to itself.
        if internal: map = try with_root(names, map)
        var options = ArcOptions.plain()
        options.contribute = contribute
        options.ancestral = not is_root_prim(names, prim)
        let kind = ArcType.payload if payload else ArcType.reference
        _ = try self.add_arc(indexer, kind, node, (i32)node, target_stack, prim, map, number, namespace_depth(names, node_path), options)

    ## Add an arc (_AddArc): unless it closes a cycle or its site is a
    ## duplicate to skip, a new child node, or (bringing ancestral opinions)
    ## its target's own index as a subtree; then queue the new nodes'
    ## tasks. `map` is taken. The new node, if any.
    func add_arc(indexer: Indexer*, kind: ArcType, parent: u32, origin: i32, stack: usize, path: u32, map: MapFunction, sibling: i32, depth: i32, options: ArcOptions) -> u32?!:
        var owned = map
        let index = &indexer.index
        var skip = options.skip_duplicates
        if let frame = indexer.frame: skip = skip or frame.skip_duplicates
        let refused = self.refuses_arc(index, kind, parent, (u32)origin, stack, path, indexer.frame, skip) catch failure:
            owned.close()
            error(failure.code, failure.message)
        if refused:
            owned.close()
            return none
        var added: u32 = 0
        if not options.ancestral:
            let node = Node(stack = stack, path = path, arc = kind, parent = (i32)parent, origin = origin, children = Growing[u32](), sibling = sibling, depth = depth, map_to_parent = owned, inert = false, culled = false, has_specs = self.site_has_specs(stack, path), restricted = 0, due_to_ancestor = false, direct = false, ancestral_arc = false)
            added = try index.insert_child(self.names, parent, node)
            if not options.contribute:
                index.set_inert(self.names, added)
                # Not even ancestrally (SetSpecContributionRestrictedDepth(1)).
                index.nodes.items[(usize)added].restricted = 1
        else:
            let below = Frame(index = index, parent = parent, stack = stack, path = path, previous = indexer.frame, kind = kind, skip_duplicates = skip, map = &owned)
            # Variants and implied specializes wait for the outer index,
            # which knows stronger opinions.
            var sub = self.build(stack, path, &below, options.contribute, false) catch failure:
                owned.close()
                error(failure.code, failure.message)
            defer sub.close()
            added = try append_subtree(index, self.names, parent, &sub, kind, origin, sibling, depth, owned)
            if sub.has_payloads: index.has_payloads = true
        # Dependency flags: a new node is direct unless it copies its
        # origin's; an ancestral subtree takes them from its new root.
        let entry = &index.nodes.items[(usize)added]
        if options.copy_ancestor and origin >= 0:
            let source = index.nodes.items[(usize)origin]
            entry.due_to_ancestor = source.due_to_ancestor
            entry.direct = source.direct
            entry.ancestral_arc = source.ancestral_arc
        else:
            entry.due_to_ancestor = false
            entry.direct = true
            entry.ancestral_arc = index.nodes.items[(usize)parent].ancestral_arc
        if options.ancestral and indexer.frame == none: spread_dependencies(index, added, entry.direct, entry.ancestral_arc)
        # A nested build evaluated the subtree's expressed arcs; its
        # ancestral variants are evaluated only where variants are.
        var tasks = options.tasks
        if options.ancestral: tasks = tasks & ~expressed_arc_tasks
        if not (indexer.outer and options.ancestral): tasks = tasks & ~ancestral_variant_tasks
        if not options.ancestral: tasks = tasks & ~task_implied_specializes
        try indexer.add_tasks_for_node(self.names, added, tasks)
        if path == absolute_root: inert_subtree(index, added, self.names)
        return added

    ## Whether an arc must not be added: it closes a cycle (variant arcs
    ## never do), or with `skip` its site is one a graph up the stack
    ## frames already holds.
    func refuses_arc(index: const PrimIndex*, kind: ArcType, parent: u32, origin: u32, stack: usize, path: u32, frame: const Frame*?, skip: bool) -> bool!:
        if kind != ArcType.variant and not Composer.implied_under_relocate(index, kind, parent, origin, frame):
            if try self.closes_cycle(index, parent, stack, path, frame):
                try self.problems.add("Cycle detected")
                return true
        if not skip: return false
        var graph = index
        var site = path
        var level = frame
        while true:
            if graph.node_using_site(stack, site) != none: return true
            let up = level else return false
            let root_path = graph.nodes.items[0].path
            site = up.path if root_path == site else try self.names.replace_prefix(up.path, root_path, site)
            graph = up.index
            level = up.previous

    ## An implied class arc under a relocation's class arcs, which is no
    ## cycle (the XXX:RelocatesSourceNodes case of _CheckForCycle).
    static func implied_under_relocate(index: const PrimIndex*, kind: ArcType, parent: u32, origin: u32, frame: const Frame*?) -> bool:
        if not is_class_based(kind) or parent == origin: return false
        var graph = index
        var node = (i32)parent
        var level = frame
        while true:
            # The arc to the node's parent, across stack frames.
            var arc = ArcType.root
            if node > 0: arc = graph.nodes.items[(usize)node].arc
            elif let up = level: arc = up.kind
            if arc != ArcType.inherit and arc != ArcType.specialize: return arc == ArcType.relocate
            if node > 0:
                node = graph.nodes.items[(usize)node].parent
            else:
                let up = level else return false
                graph = up.index
                node = (i32)up.parent
                level = up.previous

    ## Whether an arc from `parent` to (`stack`, `path`) returns to a site
    ## at, above or below one on the way to the root, through every stack
    ## frame (_CheckForCycle).
    func closes_cycle(index: const PrimIndex*, parent: u32, stack: usize, path: u32, frame: const Frame*?) -> bool!:
        var graph = index
        var node = (i32)parent
        var site = path
        var level = frame
        while true:
            while node >= 0:
                let entry = &graph.nodes.items[(usize)node]
                if entry.stack == stack and (self.names.has_prefix(entry.path, site) or self.names.has_prefix(site, entry.path)): return true
                node = entry.parent
            let up = level else return false
            let root_path = graph.nodes.items[0].path
            # The requested site with this graph's root replaced by the arc's
            # target: where the arc would lead in the enclosing graph.
            site = up.path if root_path == site else try self.names.replace_prefix(up.path, root_path, site)
            graph = up.index
            node = (i32)up.parent
            level = up.previous

func find_arc(items: const ArcItem[], item: ListItem) -> usize?:
    for at in 0..<items.length:
        if same_item(items[at].item, item): return at
    return none

func remove_arc(items: Growing[ArcItem]*, at: usize):
    var index = at
    while index + 1 < items.count:
        items.items[index] = items.items[index + 1]
        index += 1
    items.count -= 1

## Append `sub`'s nodes under `parent`, its root reached by the given arc
## (`map` taken); the new root's index.
func append_subtree(index: PrimIndex*, names: const Names*, parent: u32, sub: const PrimIndex*, kind: ArcType, origin: i32, sibling: i32, depth: i32, map: MapFunction) -> u32!:
    var owned = map
    errdefer owned.close()
    let base = (u32)index.nodes.count
    for at in 0..<sub.nodes.count:
        let node = &sub.nodes.items[at]
        var children = Growing[u32]()
        errdefer children.close()
        for child in node.children.view(): try children.push(child + base)
        let root = at == 0
        var node_map = MapFunction.identity()
        if root:
            node_map = owned
            owned = MapFunction.identity()
        else:
            node_map = try node.map_to_parent.copy()
        index.nodes.push(Node(stack = node.stack, path = node.path, arc = kind if root else node.arc, parent = (i32)parent if root else node.parent + (i32)base, origin = origin if root else (node.origin + (i32)base if node.origin >= 0 else -1), children = children, sibling = sibling if root else node.sibling, depth = depth if root else node.depth, map_to_parent = node_map, inert = node.inert, culled = node.culled, has_specs = node.has_specs, restricted = node.restricted, due_to_ancestor = node.due_to_ancestor, direct = node.direct, ancestral_arc = node.ancestral_arc)) catch failure:
            node_map.close()
            error(failure.code, failure.message)
    try index.link_child(names, parent, base)
    return base

## Make a node and everything under it inert (_InertSubtree).
func inert_subtree(index: PrimIndex*, node: u32, names: const Names*):
    index.set_inert(names, node)
    for child in index.nodes.items[(usize)node].children.view(): inert_subtree(index, child, names)

## A layer's defaultPrim as a path: a root prim's name, or a prim path
## (SdfLayer::GetDefaultPrimAsPath).
func default_prim_path(names: Names*, token: u32) -> u32!:
    let text = names.text_of(token)
    if text.length > 0 and text.bytes[0] == '/': return try names.parse_path(text)
    for byte in text.bytes:
        if byte == '/': return try names.make_absolute(try names.parse_path(text), absolute_root)
    return try names.child(absolute_root, token)

## Whether a path is a root prim's (SdfPath::IsRootPrimPath).
func is_root_prim(names: const Names*, path: u32) -> bool:
    return names.node(path).depth == 1 and names.is_prim(path)

## Give a subtree its new root's dependency flags too.
func spread_dependencies(index: PrimIndex*, node: u32, direct: bool, ancestral: bool):
    let entry = &index.nodes.items[(usize)node]
    entry.direct = entry.direct or direct
    entry.ancestral_arc = entry.ancestral_arc or ancestral
    for child in index.nodes.items[(usize)node].children.view(): spread_dependencies(index, child, direct, ancestral)