Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-usd

Source of release 0.9.6

0.9.6 / src / sdf / expressions.lucb

## Variable expressions, after SdfVariableExpression (pxr/usd/sdf/
## variableExpressionParser.cpp, variableExpressionImpl.cpp): a backquoted
## expression over a layer stack's expression variables, as sublayer,
## reference and payload asset paths and variant selections may be. An
## expression is a variable `${NAME}`, a string ("..." or '...', with
## `${NAME}` substituted inside), an integer, a boolean, None, a list of
## those in brackets, or a function call: if, eq, neq, lt, leq, gt, geq,
## and, or, not, contains, at, len, defined (matches_regex is refused).
## A variable whose value is itself an expression is evaluated in turn;
## circular ones fail. Parsing and evaluating go together: arguments an
## and/or no longer needs are parsed without being evaluated.
from luce_std import math
from sdf.names import Names
from sdf.values import Value, Dictionary
from sdf.value_types import ValueKind, scalar_of
from luce_geocore.core.growing import Growing

## A result's type.
pub enum ExpressionKind as u8:
    nothing = 0
    string = 1
    boolean = 2
    integer = 3
    ## A list of strings, booleans or integers, or an empty list.
    strings = 4
    booleans = 5
    integers = 6
    empty_list = 7

## A value: a string as its token, a boolean as 0 or 1, list elements in
## `items`; `failed` when evaluating it failed.
pub struct Evaluated:
    pub var kind: ExpressionKind
    pub var number: i64
    pub var items: Growing[i64]
    pub var failed: bool

    pub static func of(kind: ExpressionKind, number: i64) -> Evaluated:
        return Evaluated(kind = kind, number = number, items = Growing[i64](), failed = false)

    pub static func failure() -> Evaluated:
        return Evaluated(kind = ExpressionKind.nothing, number = 0, items = Growing[i64](), failed = true)

    pub func close():
        self.items.close()

    func is_list() -> bool:
        return (u8)self.kind >= (u8)ExpressionKind.strings

## Whether `text` is an expression: backquoted (SdfVariableExpression::
## IsExpression).
pub func is_expression(text: str) -> bool:
    return text.length >= 2 and text.bytes[0] == '`' and text.bytes[text.length - 1] == '`'

## The string an expression evaluates to with `variables` (a dictionary
## value, or empty), as a token; the empty string (token 0) when it fails
## or is not a string (Pcp_EvaluateVariableExpression).
pub func evaluate_to_string(names: Names*, expression: str, variables: const Value*) -> u32!:
    var evaluator = Evaluator(names = names, variables = variables, stack = Growing[u32]())
    defer evaluator.close()
    var result = try evaluator.evaluate(expression)
    defer result.close()
    if result.failed or result.kind != ExpressionKind.string: return 0
    return (u32)result.number

## Evaluate an expression with `variables`.
pub func evaluate(names: Names*, expression: str, variables: const Value*) -> Evaluated!:
    var evaluator = Evaluator(names = names, variables = variables, stack = Growing[u32]())
    defer evaluator.close()
    return try evaluator.evaluate(expression)

struct Evaluator:
    var names: Names*
    var variables: const Value*
    ## Variables being evaluated, to catch circular ones.
    var stack: Growing[u32]

    func close():
        self.stack.close()

    func evaluate(expression: str) -> Evaluated!:
        var parser = Parser(text = expression, at = 0, broken = false)
        if not parser.take('`'): return Evaluated.failure()
        var result = try self.body(&parser, false)
        if parser.broken or not parser.take('`'):
            result.close()
            return Evaluated.failure()
        return result

    ## ExpressionBody: a list or a scalar.
    func body(parser: Parser*, skip: bool) -> Evaluated!:
        if parser.peek() == '[': return try self.list(parser, skip)
        return try self.scalar(parser, skip)

    func scalar(parser: Parser*, skip: bool) -> Evaluated!:
        let byte = parser.peek()
        if byte == '$':
            let name = parser.variable() else return parser.fail()
            if skip: return Evaluated.of(ExpressionKind.nothing, 0)
            return try self.variable(try self.names.token(name))
        if byte == '"' or byte == 39: return try self.quoted(parser, byte, skip)
        if byte == '-' or (byte >= '0' and byte <= '9'):
            let value = parser.integer() else return parser.fail()
            return Evaluated.of(ExpressionKind.integer, value)
        let word = parser.identifier()
        if word.length == 0: return parser.fail()
        if word == "true" or word == "True": return Evaluated.of(ExpressionKind.boolean, 1)
        if word == "false" or word == "False": return Evaluated.of(ExpressionKind.boolean, 0)
        if word == "None" or word == "none": return Evaluated.of(ExpressionKind.nothing, 0)
        return try self.function(parser, word, skip)

    ## The value variable `name` is set to, if any.
    func lookup(name: u32) -> const Value*?:
        let dictionary = self.variables.dictionary() else return none
        return dictionary.find(name)

    ## The value of variable `name` (a failure when it has none).
    func variable(name: u32) -> Evaluated!:
        for held in self.stack.view():
            if held == name: return Evaluated.failure()
        let value = self.lookup(name) else return Evaluated.failure()
        var result = try from_value(self.names, value)
        if result.kind != ExpressionKind.string or result.failed: return result
        let text = self.names.text_of((u32)result.number)
        if not is_expression(text): return result
        try self.stack.push(name)
        defer self.stack.count -= 1
        result.close()
        return try self.evaluate(text)

    ## A quoted string, with `${NAME}` substituted and escapes processed
    ## (TfEscapeString).
    func quoted(parser: Parser*, quote: u8, skip: bool) -> Evaluated!:
        parser.at += 1
        var text = Growing[u8]()
        defer text.close()
        var failed = false
        while true:
            if parser.at >= parser.text.length: return parser.fail()
            let byte = parser.text.bytes[parser.at]
            if byte == quote:
                parser.at += 1
                break
            if byte == '$' and parser.at + 1 < parser.text.length and parser.text.bytes[parser.at + 1] == '{':
                let name = parser.variable() else return parser.fail()
                if skip or failed: continue
                let token = try self.names.token(name)
                if self.lookup(token) == none:
                    # An unset variable leaves its name (StringNode::Evaluate).
                    for part in name.bytes: try text.push(part)
                    continue
                var value = try self.variable(token)
                defer value.close()
                if value.failed: failed = true
                elif value.kind == ExpressionKind.string:
                    for part in self.names.text_of((u32)value.number).bytes: try text.push(part)
                elif value.kind != ExpressionKind.nothing: failed = true
                continue
            if byte == '\\' and parser.at + 1 < parser.text.length:
                parser.at += 1
                try unescape(parser, &text)
                continue
            try text.push(byte)
            parser.at += 1
        if skip: return Evaluated.of(ExpressionKind.nothing, 0)
        if failed: return Evaluated.failure()
        return Evaluated.of(ExpressionKind.string, (i64)(try self.names.token((str)text.view())))

    ## A list of scalars of one type: spaces only around its commas, or
    ## alone in an empty list.
    func list(parser: Parser*, skip: bool) -> Evaluated!:
        parser.at += 1
        var result = Evaluated.of(ExpressionKind.empty_list, 0)
        errdefer result.close()
        var first = true
        if parser.peek() == ' ' or parser.peek() == ']':
            parser.spaces()
            if parser.take(']'): return result
            return parser.fail_with(&result)
        while true:
            var element = try self.scalar(parser, skip)
            defer element.close()
            if parser.broken: return Evaluated.take_failure(&result)
            if not skip:
                if element.failed or element.is_list() or element.kind == ExpressionKind.nothing: result.failed = true
                elif not result.failed:
                    let kind = list_of(element.kind)
                    if first: result.kind = kind
                    elif result.kind != kind: result.failed = true
                    try result.items.push(element.number)
            first = false
            if parser.take(']'): return result
            parser.spaces()
            if not parser.take(','): return parser.fail_with(&result)
            parser.spaces()

    ## A function call: its arguments, then the function. Spaces pad its
    ## parentheses and commas.
    func function(parser: Parser*, name: str, skip: bool) -> Evaluated!:
        parser.spaces()
        if not parser.take('('): return parser.fail()
        parser.spaces()
        var arguments = Growing[Evaluated]()
        defer close_all(&arguments)
        var done = skip
        # and/or stop evaluating once the answer is known.
        let short = name == "and" or name == "or"
        if not parser.take(')'):
            while true:
                var argument = try self.body(parser, done)
                if parser.broken:
                    argument.close()
                    return parser.fail()
                if short and not done and not argument.failed and argument.kind == ExpressionKind.boolean:
                    if (name == "and" and argument.number == 0) or (name == "or" and argument.number != 0): done = true
                arguments.push(argument) catch failure:
                    argument.close()
                    error(failure.code, failure.message)
                parser.spaces()
                if parser.take(')'): break
                if not parser.take(','): return parser.fail()
                parser.spaces()
        parser.spaces()
        # An unknown function or argument count is a syntax error.
        if not known_call(name, arguments.count): return parser.fail()
        if skip: return Evaluated.of(ExpressionKind.nothing, 0)
        return try self.call(name, arguments.view())

    func call(name: str, arguments: const Evaluated[]) -> Evaluated!:
        let count = arguments.length
        if name == "if":
            if count != 2 and count != 3: return Evaluated.failure()
            if arguments[0].failed or arguments[0].kind != ExpressionKind.boolean: return Evaluated.failure()
            if count == 3 and arguments[1].kind != arguments[2].kind and arguments[1].kind != ExpressionKind.nothing and arguments[2].kind != ExpressionKind.nothing: return Evaluated.failure()
            if arguments[0].number != 0: return try copy_of(&arguments[1])
            if count == 3: return try copy_of(&arguments[2])
            return Evaluated.of(ExpressionKind.nothing, 0)
        for argument in arguments:
            if argument.failed: return Evaluated.failure()
        if name == "eq" or name == "neq" or name == "lt" or name == "leq" or name == "gt" or name == "geq":
            if count != 2: return Evaluated.failure()
            return compare(self.names, name, &arguments[0], &arguments[1])
        if name == "and" or name == "or":
            if count < 2: return Evaluated.failure()
            var result: i64 = -1
            for argument in arguments:
                if argument.kind != ExpressionKind.boolean: return Evaluated.failure()
                if name == "and" and argument.number == 0: return Evaluated.of(ExpressionKind.boolean, 0)
                if name == "or" and argument.number != 0: return Evaluated.of(ExpressionKind.boolean, 1)
                result = argument.number
            return Evaluated.of(ExpressionKind.boolean, result)
        if name == "not":
            if count != 1 or arguments[0].kind != ExpressionKind.boolean: return Evaluated.failure()
            return Evaluated.of(ExpressionKind.boolean, 1 - arguments[0].number)
        if name == "contains":
            if count != 2: return Evaluated.failure()
            return contains(self.names, &arguments[0], &arguments[1])
        if name == "at":
            if count != 2 or arguments[1].kind != ExpressionKind.integer: return Evaluated.failure()
            return try element_at(self.names, &arguments[0], arguments[1].number)
        if name == "len":
            if count != 1: return Evaluated.failure()
            if arguments[0].kind == ExpressionKind.string: return Evaluated.of(ExpressionKind.integer, (i64)self.names.text_of((u32)arguments[0].number).length)
            if arguments[0].is_list(): return Evaluated.of(ExpressionKind.integer, (i64)arguments[0].items.count)
            return Evaluated.failure()
        if name == "defined":
            if count < 1: return Evaluated.failure()
            var all = true
            for argument in arguments:
                if argument.kind != ExpressionKind.string: return Evaluated.failure()
                var known = false
                if let dictionary = self.variables.dictionary(): known = dictionary.find((u32)argument.number) != none
                all = all and known
            return Evaluated.of(ExpressionKind.boolean, 1 if all else 0)
        # Unknown functions, and matches_regex (no regex engine here).
        return Evaluated.failure()

## The text being parsed and the position in it.
struct Parser:
    var text: str
    var at: usize
    ## A syntax error: the whole expression fails.
    var broken: bool

    func peek() -> u8:
        return self.text.bytes[self.at] if self.at < self.text.length else 0

    func take(byte: u8) -> bool:
        if self.peek() != byte: return false
        self.at += 1
        return true

    func spaces():
        while self.peek() == ' ': self.at += 1

    func fail() -> Evaluated:
        self.broken = true
        return Evaluated.failure()

    func fail_with(held: Evaluated*) -> Evaluated:
        held.close()
        return self.fail()

    ## A C identifier.
    func identifier() -> str:
        let start = self.at
        let first = self.peek()
        if not (first == '_' or (first >= 'a' and first <= 'z') or (first >= 'A' and first <= 'Z')): return ""
        self.at += 1
        while true:
            let byte = self.peek()
            if not (byte == '_' or (byte >= 'a' and byte <= 'z') or (byte >= 'A' and byte <= 'Z') or (byte >= '0' and byte <= '9')): break
            self.at += 1
        return (str)self.text.bytes[start..<self.at]

    ## `${NAME}`: the name.
    func variable() -> str?:
        if not self.take('$') or not self.take('{'): return none
        let name = self.identifier()
        if name.length == 0 or not self.take('}'): return none
        return name

    ## An optionally negative decimal integer.
    func integer() -> i64?:
        let negative = self.take('-')
        var value: i64 = 0
        var digits: usize = 0
        while self.peek() >= '0' and self.peek() <= '9':
            if value > 922337203685477579: return none
            value = value * 10 + (i64)(self.peek() - '0')
            self.at += 1
            digits += 1
        if digits == 0: return none
        return -value if negative else value

## A backslash escape (TfEscapeStringReplaceChar); the parser is past the
## backslash.
func unescape(parser: Parser*, out: Growing[u8]*) -> !:
    let byte = parser.peek()
    parser.at += 1
    if byte == 'a': try out.push(7)
    elif byte == 'b': try out.push(8)
    elif byte == 'f': try out.push(12)
    elif byte == 'n': try out.push(10)
    elif byte == 'r': try out.push(13)
    elif byte == 't': try out.push(9)
    elif byte == 'v': try out.push(11)
    elif byte == 'x':
        var value: u8 = 0
        var count = 0
        while count < 2 and hex_digit(parser.peek()) >= 0:
            value = value * 16 + (u8)hex_digit(parser.peek())
            parser.at += 1
            count += 1
        try out.push(value)
    elif byte >= '0' and byte <= '7':
        var value: u8 = byte - '0'
        var count = 1
        while count < 3 and parser.peek() >= '0' and parser.peek() <= '7':
            value = value * 8 + (parser.peek() - '0')
            parser.at += 1
            count += 1
        try out.push(value)
    else: try out.push(byte)

func hex_digit(byte: u8) -> i32:
    if byte >= '0' and byte <= '9': return (i32)(byte - '0')
    if byte >= 'a' and byte <= 'f': return (i32)(byte - 'a') + 10
    if byte >= 'A' and byte <= 'F': return (i32)(byte - 'A') + 10
    return -1

## Whether a function exists with that many arguments.
func known_call(name: str, count: usize) -> bool:
    if name == "if": return count == 2 or count == 3
    if name == "and" or name == "or": return count >= 2
    if name == "defined": return count >= 1
    if name == "not" or name == "len": return count == 1
    return count == 2 and (name == "eq" or name == "neq" or name == "lt" or name == "leq" or name == "gt" or name == "geq" or name == "contains" or name == "matches_regex" or name == "at")

## An expression variable's value as an expression value: strings,
## booleans and integers, and arrays of them.
func from_value(names: Names*, value: const Value*) -> Evaluated!:
    let scalar = scalar_of(value.kind)
    if not value.array:
        match value.kind:
            .string, .token: return Evaluated.of(ExpressionKind.string, (i64)value.as_token())
            .boolean: return Evaluated.of(ExpressionKind.boolean, 1 if value.as_bool() else 0)
            .int, .int64, .uint, .uint64, .uchar: return Evaluated.of(ExpressionKind.integer, value.as_int())
            _: return Evaluated.failure()
    var result = Evaluated.of(ExpressionKind.empty_list, 0)
    errdefer result.close()
    match scalar:
        .string, .token:
            result.kind = ExpressionKind.strings
            for id in value.ids(): try result.items.push((i64)id)
        .boolean:
            result.kind = ExpressionKind.booleans
            for byte in value.bytes(): try result.items.push(1 if byte != 0 else 0)
        .int:
            result.kind = ExpressionKind.integers
            for id in value.ids(): try result.items.push((i64)(i32)id)
        _:
            result.failed = true
    if value.count == 0: result.kind = ExpressionKind.empty_list
    return result

func list_of(kind: ExpressionKind) -> ExpressionKind:
    if kind == ExpressionKind.string: return ExpressionKind.strings
    if kind == ExpressionKind.boolean: return ExpressionKind.booleans
    return ExpressionKind.integers

func element_of(kind: ExpressionKind) -> ExpressionKind:
    if kind == ExpressionKind.strings: return ExpressionKind.string
    if kind == ExpressionKind.booleans: return ExpressionKind.boolean
    return ExpressionKind.integer

func copy_of(value: const Evaluated*) -> Evaluated!:
    var made = Evaluated.of(value.kind, value.number)
    made.failed = value.failed
    errdefer made.close()
    try made.items.assign(value.items.view())
    return made

func close_all(list: Growing[Evaluated]*):
    for at in 0..<list.count: list.items[at].close()
    list.close()

## eq, neq, lt, leq, gt and geq of two scalars of one type (None equals
## None and is otherwise not comparable).
func compare(names: const Names*, name: str, a: const Evaluated*, b: const Evaluated*) -> Evaluated:
    if a.kind != b.kind or a.is_list(): return Evaluated.failure()
    var order: i32 = 0
    if a.kind == ExpressionKind.nothing:
        if name == "eq": return Evaluated.of(ExpressionKind.boolean, 1)
        if name == "neq": return Evaluated.of(ExpressionKind.boolean, 0)
        return Evaluated.failure()
    if a.kind == ExpressionKind.string: order = text_order(names.text_of((u32)a.number), names.text_of((u32)b.number))
    else: order = -1 if a.number < b.number else (1 if a.number > b.number else 0)
    var result = false
    if name == "eq": result = order == 0
    elif name == "neq": result = order != 0
    elif name == "lt": result = order < 0
    elif name == "leq": result = order <= 0
    elif name == "gt": result = order > 0
    else: result = order >= 0
    return Evaluated.of(ExpressionKind.boolean, 1 if result else 0)

func text_order(a: str, b: str) -> i32:
    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 -1 if a.bytes[at] < b.bytes[at] else 1
    return -1 if a.length < b.length else (1 if a.length > b.length else 0)

## Whether a string holds a substring, or a list an element.
func contains(names: const Names*, within: const Evaluated*, part: const Evaluated*) -> Evaluated:
    if within.kind == ExpressionKind.empty_list: return Evaluated.of(ExpressionKind.boolean, 0)
    if within.kind == ExpressionKind.string:
        if part.kind != ExpressionKind.string: return Evaluated.failure()
        let text = names.text_of((u32)within.number)
        let wanted = names.text_of((u32)part.number)
        var at: usize = 0
        while at + wanted.length <= text.length:
            if (str)text.bytes[at..<at + wanted.length] == wanted: return Evaluated.of(ExpressionKind.boolean, 1)
            at += 1
        return Evaluated.of(ExpressionKind.boolean, 0)
    if not within.is_list(): return Evaluated.failure()
    if part.kind != element_of(within.kind): return Evaluated.failure()
    for item in within.items.view():
        if item == part.number: return Evaluated.of(ExpressionKind.boolean, 1)
    return Evaluated.of(ExpressionKind.boolean, 0)

## Element `index` of a list or string (negative from the end).
func element_at(names: Names*, source: const Evaluated*, index: i64) -> Evaluated!:
    var size: i64 = 0
    if source.kind == ExpressionKind.string: size = (i64)names.text_of((u32)source.number).length
    elif source.is_list() and source.kind != ExpressionKind.empty_list: size = (i64)source.items.count
    else: return Evaluated.failure()
    let position = index + size if index < 0 else index
    if position < 0 or position >= size: return Evaluated.failure()
    if source.kind == ExpressionKind.string:
        let text = names.text_of((u32)source.number)
        return Evaluated.of(ExpressionKind.string, (i64)(try names.token((str)text.bytes[(usize)position..<(usize)position + 1])))
    return Evaluated.of(element_of(source.kind), source.items.items[(usize)position])

extend Evaluated:
    ## Close `held` and give a failure (for a broken parse).
    static func take_failure(held: Evaluated*) -> Evaluated:
        held.close()
        return Evaluated.failure()