Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-usd

Source of release 0.9.6

0.9.6 / src / pcp / compose.lucb

## What a prim index composes, after PcpPrimIndex::ComputePrimChildNames,
## ComputePrimPropertyNames, PcpComputePrimStackForPrimIndex,
## Pcp_BuildPrimPropertyIndex and PcpComputeRelationshipTargetPaths
## (pxr/usd/pcp/primIndex.cpp, propertyIndex.cpp, targetIndex.cpp). Names
## compose weakest node first (a node after its children, weaker children
## first), and within a node weakest layer first, each name once, primOrder
## reordering after each layer. Stacks list specs strongest first.

## One spec of a stack: the layer and the path in it.
pub struct Site:
    pub var layer: usize
    pub var path: u32

extend Composer:
    ## The prim's specs, strongest first.
    pub func prim_stack(index: const PrimIndex*, out: Growing[Site]*) -> !:
        out.clear()
        var order = Growing[u32]()
        defer order.close()
        try index.order(&order, true)
        for node in order.view():
            let entry = index.node(node)
            if not entry.contributes(): continue
            for layer in self.stacks.stack(entry.stack).layers.view():
                if self.layers.layer(layer).find(entry.path) != none: try out.push(Site(layer = layer, path = entry.path))

    ## The prim's child names (tokens) in order; an instance's come from
    ## its instanceable nodes only (_ComposePrimChildNamesForInstance).
    ## Relocations rename, remove and add children; names relocated away
    ## are prohibited and left out.
    pub func child_names(index: const PrimIndex*, out: Growing[u32]*) -> !:
        var prohibited = Growing[u32]()
        defer prohibited.close()
        try self.prohibited_names(index, out, &prohibited)

    ## The prim's child names, and the names relocations prohibit.
    pub func prohibited_names(index: const PrimIndex*, out: Growing[u32]*, prohibited: Growing[u32]*) -> !:
        out.clear()
        prohibited.clear()
        if index.nodes.count > 0: try self.names_at(index, 0, true, index.instanceable, out, prohibited)
        if prohibited.count == 0: return
        var kept: usize = 0
        for at in 0..<out.count:
            if contains(prohibited.view(), out.items[at]): continue
            out.items[kept] = out.items[at]
            kept += 1
        out.count = kept

    ## The prim's property names in order.
    pub func property_names(index: const PrimIndex*, out: Growing[u32]*) -> !:
        out.clear()
        var unused = Growing[u32]()
        defer unused.close()
        if index.nodes.count > 0: try self.names_at(index, 0, false, false, out, &unused)

    func names_at(index: const PrimIndex*, node: u32, prims: bool, instance: bool, out: Growing[u32]*, prohibited: Growing[u32]*) -> !:
        let entry = index.node(node)
        if entry.culled: return
        var at = entry.children.count
        while at > 0:
            at -= 1
            try self.names_at(index, entry.children.items[at], prims, instance, out, prohibited)
        if instance:
            if node == 0 or not index.node_instanceable(node): return
        elif not entry.contributes(): return
        if prims and self.stacks.stack(entry.stack).has_relocates(): try self.relocate_names(entry.stack, entry.path, out, prohibited)
        let layers = self.stacks.stack(entry.stack).layers.view()
        var position = layers.length
        while position > 0:
            position -= 1
            let data = self.layers.layer(layers[position])
            let spec = data.find(entry.path) else continue
            if let found = data.get(spec, data.keys.prim_children if prims else data.keys.properties):
                for name in found.ids():
                    var seen = false
                    for known in out.view(): seen = seen or known == name
                    if not seen: try out.push(name)
            if prims:
                if let order = data.get(spec, data.keys.prim_order): try apply_ordering(out, order.ids())

    ## The children relocations change at a node's path
    ## (_ComposePrimChildNamesAtNode): a child relocated under the same
    ## parent is renamed, one relocated elsewhere removed (both prohibited),
    ## and one relocated here from elsewhere added (in name order).
    func relocate_names(stack: usize, path: u32, out: Growing[u32]*, prohibited: Growing[u32]*) -> !:
        let names = self.names
        var renamed_from = Growing[u32]()
        defer renamed_from.close()
        var renamed_to = Growing[u32]()
        defer renamed_to.close()
        var removed = Growing[u32]()
        defer removed.close()
        var added = Growing[u32]()
        defer added.close()
        for relocate in self.stacks.stack(stack).relocates.view():
            if names.parent(relocate.source) == path:
                let old = names.name(relocate.source)
                if relocate.target != empty_path and names.parent(relocate.target) == path:
                    try renamed_from.push(old)
                    try renamed_to.push(names.name(relocate.target))
                else:
                    try removed.push(old)
                if not contains(prohibited.view(), old): try prohibited.push(old)
        for relocate in self.stacks.stack(stack).relocates.view():
            if relocate.target == empty_path or names.parent(relocate.target) != path or names.parent(relocate.source) == path: continue
            let name = names.name(relocate.target)
            if not contains(out.view(), name) and not contains(added.view(), name): try added.push(name)
        if renamed_from.count > 0 or removed.count > 0:
            var kept = Growing[u32]()
            defer kept.close()
            for name in out.view():
                var replaced = false
                for at in 0..<renamed_from.count:
                    if renamed_from.items[at] == name:
                        replaced = true
                        if not contains(kept.view(), renamed_to.items[at]) and not contains(out.view(), renamed_to.items[at]): try kept.push(renamed_to.items[at])
                if replaced or contains(removed.view(), name): continue
                try kept.push(name)
            try out.assign(kept.view())
        # std::set order: by name text.
        sort_by_text(names, &added)
        for name in added.view(): try out.push(name)

    ## The specs of property `name` of the prim, strongest first.
    pub func property_stack(index: const PrimIndex*, name: u32, out: Growing[Site]*) -> !:
        out.clear()
        var order = Growing[u32]()
        defer order.close()
        try index.order(&order, true)
        # Specs of another kind than the strongest (attribute or relationship)
        # are left out (Pcp_PropertyIndexer::_GetPrimProperty).
        var kind = SpecType.unknown
        for node in order.view():
            let entry = index.node(node)
            if not entry.contributes(): continue
            let path = try self.names.property(entry.path, name)
            for layer in self.stacks.stack(entry.stack).layers.view():
                let data = self.layers.layer(layer)
                let spec = data.find(path) else continue
                let found = data.spec(spec).kind
                if kind == SpecType.unknown: kind = found
                elif found != kind: continue
                try out.push(Site(layer = layer, path = path))

    ## A relationship's targets (`connections`: an attribute's connections)
    ## in the root namespace: each node's opinions applied weakest first,
    ## relative paths anchored at the property, then mapped to the root.
    ## `deleted` gets the paths deletes named since the last explicit list.
    ## `validate` (PcpCache's validation): a target a class authors that
    ## leaves the class for one of its instances is left out.
    pub func target_paths(index: const PrimIndex*, name: u32, connections: bool, validate: bool, out: Growing[u32]*, deleted: Growing[u32]*) -> !:
        out.clear()
        deleted.clear()
        var order = Growing[u32]()
        defer order.close()
        try index.order(&order, true)
        var items = Growing[ListItem]()
        defer items.close()
        var at = order.count
        while at > 0:
            at -= 1
            let node = order.items[at]
            let entry = index.node(node)
            if not entry.contributes(): continue
            # The node's map to the root, made once it has an opinion.
            var map = MapFunction.identity()
            defer map.close()
            var mapped_yet = false
            let property = try self.names.property(entry.path, name)
            let layers = self.stacks.stack(entry.stack).layers.view()
            var position = layers.length
            while position > 0:
                position -= 1
                let data = self.layers.layer(layers[position])
                let spec = data.find(property) else continue
                let field = data.get(spec, data.keys.connection_paths if connections else data.keys.target_paths) else continue
                let list = field.list_op() else continue
                if not mapped_yet:
                    let made = try index.map_to_root(self.names, node)
                    map.close()
                    map = made
                    mapped_yet = true
                # Translate this layer's opinion into the root namespace, then apply it.
                var translated = try ListOp.create()
                var owner = Value.of_object(ValueKind.path_list_op, (void*)translated)
                defer owner.release()
                translated.explicit = list.explicit
                if list.explicit: deleted.clear()
                for part in 0..<(usize)6:
                    for item in list.parts[part].view():
                        let absolute = try self.names.make_absolute((u32)item.a, property)
                        let mapped = try map.map(self.names, absolute, false)
                        if mapped == empty_path: continue
                        if part == (usize)(u8)ListPart.deleted: try deleted.push(mapped)
                        elif validate and try self.targets_instance(index, node, absolute, mapped): continue
                        try translated.push(ListPart((u8)part), ListItem(a = (u64)mapped, b = 0, offset = 0.0, scale = 1.0, custom = none))
                try apply_list_op(translated, &items)
        for item in items.view(): try out.push((u32)item.a)

extend Composer:
    ## _TargetInClassAndTargetsInstance: a target authored in an inherited
    ## class that points outside the class, at an object whose prim
    ## inherits that class too (an instance).
    func targets_instance(index: const PrimIndex*, node: u32, authored: u32, mapped: u32) -> bool!:
        let entry = index.node(node)
        if entry.arc != ArcType.inherit: return false
        let class_path = index.path_at_introduction(self.names, node)
        if self.names.has_prefix(authored, class_path): return false
        let stack = entry.stack
        let target = try self.index(prim_of(self.names, mapped))
        for other in target.nodes.view():
            if other.arc == ArcType.inherit and other.stack == stack and self.names.has_prefix(other.path, class_path): return true
        return false

## SdfApplyListOrdering (SdfListOp's _ReorderKeysHelper): each name of
## `order` that is present starts a run taking the names after it up to the
## next ordered one; the runs follow `order`, and names before any ordered
## one stay first.
func apply_ordering(names: Growing[u32]*, order: const u32[]) -> !:
    if order.length == 0 or names.count == 0: return
    var unique = Growing[u32]()
    defer unique.close()
    for name in order:
        if not contains(unique.view(), name): try unique.push(name)
    var scratch = Growing[u32]()
    defer scratch.close()
    try scratch.assign(names.view())
    var taken = Growing[bool]()
    defer taken.close()
    try taken.fill(scratch.count, false)
    var tail = Growing[u32]()
    defer tail.close()
    for name in unique.view():
        var start = scratch.count
        for at in 0..<scratch.count:
            if scratch.items[at] == name and not taken.items[at]: start = at
        if start == scratch.count: continue
        var end = start
        while true:
            try tail.push(scratch.items[end])
            taken.items[end] = true
            end += 1
            if end >= scratch.count or contains(unique.view(), scratch.items[end]): break
    names.clear()
    for at in 0..<scratch.count:
        if not taken.items[at]: try names.push(scratch.items[at])
    for name in tail.view(): try names.push(name)

func contains(names: const u32[], name: u32) -> bool:
    for known in names:
        if known == name: return true
    return false

## Sort name tokens by their text's bytes.
func sort_by_text(names: const Names*, list: Growing[u32]*):
    for at in 1..<list.count:
        var move = at
        while move > 0 and bytes_before(names.text_of(list.items[move]), names.text_of(list.items[move - 1])):
            let swap = list.items[move]
            list.items[move] = list.items[move - 1]
            list.items[move - 1] = swap
            move -= 1

func bytes_before(a: str, b: str) -> bool:
    let count = a.length if a.length < b.length else b.length
    for at in 0..<count:
        if a.bytes[at] != b.bytes[at]: return a.bytes[at] < b.bytes[at]
    return a.length < b.length