dymokomi/luce-usd
Source of release 0.9.1
0.9.1 / src / sdf / names / names.lucb
## Names: the interned tokens and paths every layer of one load shares,
## after OpenUSD's TfToken and SdfPath (pxr/usd/sdf/path.cpp, pathNode.cpp).
##
## A path is a u32 id of a node in one table: its parent, its kind and its
## element (a name token, a variant selection's two tokens, or the path a
## target names). Equal paths are equal ids, so paths compare, hash and
## store as integers, and a path's prefixes are its ancestors. Id 0 is the
## empty path, 1 the absolute root `/`, 2 the relative root `.`.
##
## Fragments, in ORDER:
##
## names.lucb the table: tokens, nodes, construction and queries
## path_parse.lucb path text to ids (the grammar of pathParser.h)
## path_text.lucb ids to text (pathNode.cpp's _WriteTextToBuffer)
## path_ops.lucb prefixes, prefix replacement, variant stripping, anchoring
import memory
import errors
from sdf.tokens import Tokens
from luce_geocore.core.growing import Growing
## The empty path.
pub let empty_path: u32 = 0
## The absolute root, `/`.
pub let absolute_root: u32 = 1
## The relative root, `.`.
pub let relative_root: u32 = 2
## The most nodes one table holds.
pub let most_paths: usize = 268435456
## What a path node adds to its parent, after Sdf_PathNode::NodeType.
pub enum PathKind as u8:
## `/` and `.`.
root = 0
## A prim name (also `..` in relative paths).
prim = 1
## `{set=selection}` after a prim.
variant = 2
## `.name` after a prim or variant selection.
property = 3
## `[path]` after a property: a relationship target or connection.
target = 4
## `.mapper[path]` after a property.
mapper = 5
## `.name` after a target: a relational attribute.
relational = 6
## `.name` after a mapper.
mapper_arg = 7
## `.expression` after a property.
expression = 8
pub struct PathNode:
pub var parent: u32
pub var kind: PathKind
## Whether the path starts at `/`.
pub var absolute: bool
## A name token; a variant set's token; or the path a target or mapper names.
pub var element: u32
## A variant selection's selection token; 0 otherwise.
pub var extra: u32
## Nodes from the root: `/` and `.` are 0.
pub var depth: u32
## The token and path tables of one load.
pub struct Names:
pub var tokens: Tokens
var nodes: Growing[PathNode]
## Node id + 1 per slot, 0 empty; capacity a power of two.
var slots: Growing[u32]
## Tokens the path grammar and writers use.
pub var dot_dot: u32
pub var mapper_word: u32
pub var expression_word: u32
pub func init() -> !:
var tokens = try Tokens()
errdefer tokens.close()
let dot_dot = try tokens.intern("..")
let mapper_word = try tokens.intern("mapper")
let expression_word = try tokens.intern("expression")
var nodes = Growing[PathNode]()
errdefer nodes.close()
try nodes.push(PathNode(parent = 0, kind = PathKind.root, absolute = false, element = 0, extra = 0, depth = 0))
try nodes.push(PathNode(parent = 0, kind = PathKind.root, absolute = true, element = 0, extra = 0, depth = 0))
try nodes.push(PathNode(parent = 0, kind = PathKind.root, absolute = false, element = 0, extra = 0, depth = 0))
self.tokens = tokens
self.nodes = nodes
self.slots = Growing[u32]()
self.dot_dot = dot_dot
self.mapper_word = mapper_word
self.expression_word = expression_word
pub func close():
self.tokens.close()
self.nodes.close()
self.slots.close()
## The id of `text`, interned.
pub func token(text: str) -> u32!:
return try self.tokens.intern(text)
## The text of `token`.
pub func text_of(token: u32) -> str:
return self.tokens.text(token)
## Distinct paths, the empty path and both roots included.
pub func path_count() -> usize:
return self.nodes.count
pub func node(path: u32) -> PathNode:
return self.nodes.items[(usize)path]
pub func parent(path: u32) -> u32:
return self.nodes.items[(usize)path].parent
pub func kind(path: u32) -> PathKind:
return self.nodes.items[(usize)path].kind
## The name token of a prim, property or relational attribute path; the
## variant set of a variant selection; 0 otherwise.
pub func name(path: u32) -> u32:
let node = self.nodes.items[(usize)path]
match node.kind:
.prim, .property, .relational, .mapper_arg, .variant: return node.element
_: return 0
## The name's text ("" for the roots and target nodes).
pub func name_text(path: u32) -> str:
return self.tokens.text(self.name(path))
pub func is_absolute(path: u32) -> bool:
return self.nodes.items[(usize)path].absolute
## A prim path: its last element names a prim.
pub func is_prim(path: u32) -> bool:
let node = self.nodes.items[(usize)path]
return node.kind == PathKind.prim and node.element != self.dot_dot
## A prim or variant selection path, the ones prims and variants are
## authored at.
pub func is_prim_or_variant(path: u32) -> bool:
let kind = self.nodes.items[(usize)path].kind
return kind == PathKind.prim or kind == PathKind.variant
## A property path (a prim's property, or a relational attribute).
pub func is_property(path: u32) -> bool:
let kind = self.nodes.items[(usize)path].kind
return kind == PathKind.property or kind == PathKind.relational
## The path itself when it is a prim, variant or root path; else the
## prim or variant path its property part hangs from.
pub func prim_part(path: u32) -> u32:
var at = path
while true:
let kind = self.nodes.items[(usize)at].kind
if kind == PathKind.root or kind == PathKind.prim or kind == PathKind.variant: return at
at = self.nodes.items[(usize)at].parent
## Whether the path holds a variant selection anywhere.
pub func has_variant_selection(path: u32) -> bool:
var at = path
while at > relative_root:
if self.nodes.items[(usize)at].kind == PathKind.variant: return true
at = self.nodes.items[(usize)at].parent
return false
## The child prim `name` of a prim, variant or root path.
pub func child(parent: u32, name: u32) -> u32!:
return try self.find_or_add(parent, PathKind.prim, name, 0)
## The variant selection `{set=selection}` of a prim path.
pub func variant(parent: u32, set: u32, selection: u32) -> u32!:
return try self.find_or_add(parent, PathKind.variant, set, selection)
## The property `name` of a prim, variant or relative root path.
pub func property(parent: u32, name: u32) -> u32!:
return try self.find_or_add(parent, PathKind.property, name, 0)
## The target `[target]` of a property path.
pub func target(parent: u32, target: u32) -> u32!:
return try self.find_or_add(parent, PathKind.target, target, 0)
## The relational attribute `name` of a target path.
pub func relational(parent: u32, name: u32) -> u32!:
return try self.find_or_add(parent, PathKind.relational, name, 0)
## The mapper `.mapper[target]` of a property path.
pub func mapper(parent: u32, target: u32) -> u32!:
return try self.find_or_add(parent, PathKind.mapper, target, 0)
## The mapper argument `name` of a mapper path.
pub func mapper_arg(parent: u32, name: u32) -> u32!:
return try self.find_or_add(parent, PathKind.mapper_arg, name, 0)
## The expression `.expression` of a property path.
pub func expression(parent: u32) -> u32!:
return try self.find_or_add(parent, PathKind.expression, 0, 0)
## The node for (parent, kind, element, extra), added when new.
pub func find_or_add(parent: u32, kind: PathKind, element: u32, extra: u32) -> u32!:
if self.slots.count == 0 or self.nodes.count * 2 >= self.slots.count:
try self.rehash(1024 if self.slots.count == 0 else self.slots.count * 2)
let mask = self.slots.count - 1
var slot = (usize)key_hash(parent, kind, element, extra) & mask
while self.slots.items[slot] != 0:
let id = self.slots.items[slot] - 1
let node = self.nodes.items[(usize)id]
if node.parent == parent and node.kind == kind and node.element == element and node.extra == extra: return id
slot = (slot + 1) & mask
if self.nodes.count >= most_paths:
error(errors.limit, "a path table holds at most 256M paths")
let above = self.nodes.items[(usize)parent]
let id = (u32)self.nodes.count
try self.nodes.push(PathNode(parent = parent, kind = kind, absolute = above.absolute, element = element, extra = extra, depth = above.depth + 1))
self.slots.items[slot] = id + 1
return id
func rehash(capacity: usize) -> !:
try self.slots.fill(capacity, 0)
let mask = capacity - 1
for id in 3..<self.nodes.count:
let node = self.nodes.items[id]
var slot = (usize)key_hash(node.parent, node.kind, node.element, node.extra) & mask
while self.slots.items[slot] != 0: slot = (slot + 1) & mask
self.slots.items[slot] = (u32)id + 1
func key_hash(parent: u32, kind: PathKind, element: u32, extra: u32) -> u64:
var key = (u64)parent *% 0x9E3779B97F4A7C15
key = (key ^ ((u64)element << 8) ^ (u64)(u8)kind) *% 0xC2B2AE3D27D4EB4F
key = (key ^ (u64)extra) *% 0x165667B19E3779F9
return key ^ (key >> 29)