Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-usd

Source of release 0.9.3

0.9.3 / 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)