dymokomi/luce-usd
Source of release 0.9.4
0.9.4 / src / pcp / tasks.lucb
## The work queue of one index build, after Pcp_PrimIndexer's tasks
## (pxr/usd/pcp/primIndex.cpp): each node's arcs are tasks, taken in the
## priority order of their kinds (references, payloads, inherits,
## specializes, implied specializes and classes, ancestral variants,
## variants), and among tasks of one kind in node order, except that
## variant selections go strongest node first, so a stronger node's
## selection is found before a weaker one asks, and implied classes go
## descendants first, then strongest first.
## Task kinds in priority order (Pcp's Task::Type).
let task_relocations: u32 = 1
let task_implied_relocations: u32 = 2
let task_references: u32 = 4
let task_payloads: u32 = 8
let task_inherits: u32 = 16
let task_specializes: u32 = 32
let task_implied_specializes: u32 = 64
let task_implied_classes: u32 = 128
let task_ancestral_variant_sets: u32 = 256
let task_ancestral_variant_authored: u32 = 512
let task_ancestral_variant_fallback: u32 = 1024
let task_ancestral_variant_none: u32 = 2048
let task_variant_sets: u32 = 8192
let task_variant_authored: u32 = 16384
let task_variant_fallback: u32 = 32768
let task_variant_none: u32 = 65536
## Every kind; the arcs a node's own opinions express; the ancestral and
## the plain variant kinds.
let all_tasks: u32 = 0x1FFFF
let expressed_arc_tasks: u32 = task_relocations | task_references | task_payloads | task_inherits | task_specializes
let ancestral_variant_tasks: u32 = task_ancestral_variant_sets
let variant_tasks: u32 = task_variant_sets
## One task: a kind and a node, and for variant tasks the prim path the
## variant set is at, its name and its position among the node's sets.
struct Task:
var kind: u32
var node: u32
var path: u32
var name: u32
var number: i32
## One index being built and its queue.
struct Indexer:
var index: PrimIndex
var queue: Growing[Task]
var frame: const Frame*?
## Whether this is an outermost build, where variants and implied
## specializes are evaluated (not the nested builds arcs make).
var outer: bool
func close():
self.index.close()
self.queue.close()
## Queue a task; implied class and specializes tasks once per node.
func add(task: Task) -> !:
if task.kind == task_implied_classes or task.kind == task_implied_specializes:
for queued in self.queue.view():
if queued.kind == task.kind and queued.node == task.node: return
try self.queue.push(task)
## Queue a new node's tasks (AddTasksForNode): the implied classes of
## the class hierarchy it joins or brings, its subtree's specializes to
## propagate, then `kinds` for it and every node under it.
func add_tasks_for_node(names: const Names*, node: u32, kinds: u32) -> !:
let index = &self.index
if kinds & task_implied_classes != 0:
if is_class_based(index.node(node).arc):
try self.add(Task(kind = task_implied_classes, node = implied_classes_start(index, names, node), path = 0, name = 0, number = 0))
elif index.has_class_based_child(node):
try self.add(Task(kind = task_implied_classes, node = node, path = 0, name = 0, number = 0))
if kinds & task_implied_specializes != 0 and self.outer and index.has_specializes_below(node):
try self.add(Task(kind = task_implied_specializes, node = node, path = 0, name = 0, number = 0))
try self.add_tasks(node, kinds)
## Queue `kinds` for `node` and every node under it (Pcp's
## _AddTasksForNodeRecursively): the node sets for variant kinds, the
## kind itself for arc kinds.
func add_tasks(node: u32, kinds: u32) -> !:
var mask = kinds
if not self.outer: mask = mask & ~variant_tasks
let children = self.index.nodes.items[(usize)node].children.view()
for child in children: try self.add_tasks(child, mask)
# Only a relocation node implies relocations to its grandparent.
if self.index.nodes.items[(usize)node].arc != ArcType.relocate: mask = mask & ~task_implied_relocations
for kind in [task_ancestral_variant_sets, task_variant_sets, task_specializes, task_inherits, task_payloads, task_references, task_relocations, task_implied_relocations]:
if mask & kind != 0: try self.add(Task(kind = kind, node = node, path = 0, name = 0, number = 0))
## The next task, highest priority first (none when done).
func pop(names: const Names*) -> Task?:
if self.queue.count == 0: return none
var best: usize = 0
for at in 1..<self.queue.count:
if self.before(names, self.queue.items[at], self.queue.items[best]): best = at
let task = self.queue.items[best]
self.queue.items[best] = self.queue.items[self.queue.count - 1]
self.queue.count -= 1
return task
## Whether task `a` runs before task `b` (Task::PriorityOrder).
func before(names: const Names*, a: Task, b: Task) -> bool:
if a.kind != b.kind: return a.kind < b.kind
let selection = a.kind == task_variant_authored or a.kind == task_variant_fallback or a.kind == task_ancestral_variant_authored or a.kind == task_ancestral_variant_fallback
if selection:
if a.node != b.node: return self.index.compare_nodes(a.node, b.node) < 0
if a.path != b.path: return names.path_less(a.path, b.path)
return a.number < b.number
if a.kind == task_implied_classes:
# Descendants before their ancestors, else strongest first.
if b.node > a.node and self.index.is_ancestor(a.node, b.node): return false
if a.node > b.node and self.index.is_ancestor(b.node, a.node): return true
return self.index.compare_nodes(a.node, b.node) < 0
if a.node != b.node: return a.node < b.node
if a.path != b.path: return names.path_less(a.path, b.path)
return a.number < b.number
## Queued fallback and none-found variant tasks become authored ones
## again: a new variant may author selections (RetryVariantTasks).
func retry_variants():
for at in 0..<self.queue.count:
let kind = self.queue.items[at].kind
if kind == task_variant_fallback or kind == task_variant_none: self.queue.items[at].kind = task_variant_authored
elif kind == task_ancestral_variant_fallback or kind == task_ancestral_variant_none: self.queue.items[at].kind = task_ancestral_variant_authored
## Where a class hierarchy's implied classes start propagating from
## (_FindStartingNodeForImpliedClasses): its instance, or further up while
## that instance is itself a class not containing this hierarchy.
func implied_classes_start(index: const PrimIndex*, names: const Names*, node: u32) -> u32:
var start = node
while is_class_based(index.node(start).arc):
let found = index.hierarchy_start(names, start)
start = found.instance
if is_class_based(index.node(start).arc) and found.class_node >= 0:
let ancestral = index.path_at_introduction(names, start)
if names.has_prefix(index.node((u32)found.class_node).path, ancestral): break
return start