Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.7

0.7.7 / src / groups / program.lucb

## Group expressions: the text a node's Group parameter holds, and the form a
## viewport selection is stored in. The syntax is Houdini's (SOP group
## syntax, 22.0) plus a few functions of ours:
##
##   *  !*  12  3-9  0-100:2  0-100:1,3        numbers, ranges, steps
##   top  arm*  {arm* ^arm3*}  ?*                named groups, globs
##   a b   !a   ^b   &c                          union, all but, remove, intersect
##   @P.y>0  @Cd[2]<0.5  @id=1,2,90  @id="0-4 78"  @name=piece*  @flags&4
##   @ptnum<100  @primnum  @elemnum               element numbers
##   p3  p3-4  p3-4-5  7e2                        edges: at a point, between
##                                                points, along a chain, of a face
##   grow(x, 2) shrink(x) border(x) connected(x) loop(x) ring(x) convert(x, 1)
##   sharp(*, 30) sides(*, 4) path(p3 p40) similar(5, 1) nonmanifold(*) …
##
## Every select rule with a function name (selecting/registry.lucb) is a
## function: its first argument is the group it reads, the numbers after it
## its parameters in order (missing ones take their initial values), so
## `sides(*, 3, 3)` is the faces of more than three sides.
##
## Terms combine left to right into an accumulator that starts empty. The
## text compiles once into a program (terms, numbers and text spans), which
## evaluate.lucb runs to bits at word speed.
import interop
from luce_std import math
import memory
import sync
import errors
from luce_std import parallel
import core.attribute_ops
from core.growing import Growing
from core.hash import FullKey
from core.shared import Column
from core.bits import Bits, BitsBuilder, popcount, trailing_zeros
from core.attributes import Attribute, Domain, DataType, Storage
from core.strings import table_count, table_text, TableBuilder
from core.paths import glob
from core.float3 import Float3
from math.vector import Vector3
from core.geometry import Bounds
from geometry_set import append_text, append_number
from geometries.polygon import Mesh, with_group_bits
from geometries.topology.connectivity import Topology
from selecting import SelectRule, rule_at, rule_of_function, rule_named, run_rule, converted, grown, shrunk, bordered, connected

## How a term combines with what the terms before it selected.
pub enum Combine as u8:
    add = 0
    ## `!x`: everything but x.
    add_complement = 1
    ## `^x`
    remove = 2
    ## `&x`
    keep = 3

pub enum AtomKind as u8:
    all = 0
    ## numbers: first, last, keep, step (last -1: open ended)
    range = 1
    ## a group-name glob in the text span
    name = 2
    ## `{a* ^b}`: children are name terms
    names = 3
    attribute = 4
    ## `p a b c…`: numbers are the points of a chain; one point: its edges
    point_edges = 5
    ## `n e m`: numbers are the face and its side
    face_edge = 6
    call = 7

## Whether `text` is only spaces, tabs and newlines: a group that names
## everything.
pub func is_blank(text: str) -> bool:
    for byte in text.bytes:
        if byte != 32 and byte != 9 and byte != 10: return false
    return true

pub enum Compare as u8:
    exists = 0
    equal = 1
    not_equal = 2
    less = 3
    greater = 4
    less_equal = 5
    greater_equal = 6
    bits = 7

    ## Whether `value` passes this test: `values` are ranges as pairs for
    ## equal and not_equal, else one bound (or the mask for bits).
    pub func passes(values: const f64[], value: f64) -> bool:
        match self:
            .exists: return value != 0.0
            .equal, .not_equal:
                var hit = false
                for at in 0..<values.length // 2:
                    hit = hit or (value >= values[at * 2] and value <= values[at * 2 + 1])
                return hit if self == Compare.equal else not hit
            .less: return value < values[0]
            .greater: return value > values[0]
            .less_equal: return value <= values[0]
            .greater_equal: return value >= values[0]
            _: return ((i64)value & (i64)values[0]) != 0

pub enum Function as u8:
    grow = 0
    shrink = 1
    border = 2
    connected = 3
    loop = 4
    ring = 5
    convert = 6
    ## Any other select rule (`rule` names it).
    rule = 7

pub struct Term:
    pub var combine: Combine = Combine.add
    pub var kind: AtomKind = AtomKind.all
    ## Into `numbers` (ranges, edges, attribute values as low/high pairs) or,
    ## for calls and name filters, into `terms`.
    pub var first: u32 = 0
    pub var count: u32 = 0
    ## A text span of the source: a name or an attribute's name.
    pub var text: u32 = 0
    pub var text_length: u32 = 0
    ## Attributes: the component (-1: the first), the comparison, and glob
    ## values (text spans in `spans`) for text attributes.
    pub var component: i32 = -1
    pub var compare: Compare = Compare.exists
    pub var spans_first: u32 = 0
    pub var spans_count: u32 = 0
    ## Calls: the function, its first number (a count) and every number
    ## after the group (`args_count` of them in `numbers`), and the select
    ## rule it runs on polygons (-1: none).
    pub var function: Function = Function.grow
    pub var argument: f64 = 1.0
    pub var args_first: u32 = 0
    pub var args_count: u32 = 0
    pub var rule: i32 = -1

pub struct GroupProgram:
    pub var source: Growing[u8]
    pub var terms: Growing[Term]
    pub var numbers: Growing[f64]
    ## Start and length pairs into `source`.
    pub var spans: Growing[u32]
    ## The top-level terms.
    pub var top_first: u32 = 0
    pub var top_count: u32 = 0
    ## Where parsing stopped with an error (byte offset), else -1.
    pub var error_at: i64 = -1

    ## Compile `text`. Syntax errors fail with a message; `error_at` then
    ## holds the offset.
    pub static func parse(text: str) -> GroupProgram!:
        var program = GroupProgram(Growing[u8](), Growing[Term](), Growing[f64](), Growing[u32]())
        errdefer program.close()
        try program.source.assign(text.bytes)
        var parser = Parser(&program, 0)
        let (first, count) = try parser.expression(0)
        parser.skip_spaces()
        if parser.at < program.source.count:
            program.error_at = (i64)parser.at
            error(errors.invalid, "group syntax: unexpected ')' or ','")
        program.top_first = first
        program.top_count = count
        return program

    pub func text(term: const Term*) -> str:
        return (str)self.source.items[(usize)term.text..<(usize)(term.text + term.text_length)]

    pub func span(index: u32) -> str:
        let start = (usize)self.spans.items[(usize)index * 2]
        return (str)self.source.items[start..<start + (usize)self.spans.items[(usize)index * 2 + 1]]

    pub func is_empty() -> bool:
        return self.top_count == 0

    pub func close():
        self.source.close()
        self.terms.close()
        self.numbers.close()
        self.spans.close()

struct Parser:
    let program: GroupProgram*
    var at: usize

    func peek() -> u8:
        return self.program.source.items[self.at] if self.at < self.program.source.count else 0

    func peek_at(offset: usize) -> u8:
        let index = self.at + offset
        return self.program.source.items[index] if index < self.program.source.count else 0

    func skip_spaces():
        while self.peek() == 32 or self.peek() == 9 or self.peek() == 10: self.at += 1

    func fail(message: str) -> !:
        self.program.error_at = (i64)self.at
        error(errors.invalid, message)

    ## Terms until the end, a ')' or a ',' (inside a call): appended in one
    ## run after any children they contain.
    func expression(depth: usize) -> (u32, u32)!:
        if depth > 32: try self.fail("group syntax: calls nest too deep")
        var collected = Growing[Term]()
        defer collected.close()
        while true:
            self.skip_spaces()
            let byte = self.peek()
            if byte == 0 or byte == 41 or byte == 44: break
            try collected.push(try self.term(depth))
        let first = (u32)self.program.terms.count
        for term in collected.view(): try self.program.terms.push(term)
        return (first, (u32)collected.count)

    func term(depth: usize) -> Term!:
        var combine = Combine.add
        let prefix = self.peek()
        if prefix == 33: combine = Combine.add_complement
        elif prefix == 94: combine = Combine.remove
        elif prefix == 38: combine = Combine.keep
        if combine != Combine.add: self.at += 1
        var term = try self.atom(depth)
        term.combine = combine
        return term

    func atom(depth: usize) -> Term!:
        let byte = self.peek()
        if byte == 42 and ends_word(self.peek_at(1)):
            self.at += 1
            return Term(kind = AtomKind.all)
        if is_digit(byte): return try self.numbers_atom()
        if byte == 112 and is_digit(self.peek_at(1)): return try self.point_edges()
        if byte == 64: return try self.attribute()
        if byte == 123: return try self.name_filter()
        if byte == 0 or byte == 32: try self.fail("group syntax: expected a term")
        # A word: a function call or a name glob.
        let start = self.at
        while not ends_word(self.peek()) and self.peek() != 40: self.at += 1
        let word = (str)self.program.source.items[start..<self.at]
        if self.peek() == 40:
            let rule = rule_of_function(word)
            var function = Function.rule
            if let builtin = function_named(word): function = builtin
            elif rule < 0: try self.fail("group syntax: unknown function (grow, shrink, border, connected, loop, ring, convert, or a select rule's)")
            self.at += 1
            let (first, count) = try self.expression(depth + 1)
            var argument = 1.0 if function != Function.convert else 0.0
            let args_first = (u32)self.program.numbers.count
            self.skip_spaces()
            while self.peek() == 44:
                self.at += 1
                self.skip_spaces()
                let value = try self.signed_number()
                if self.program.numbers.count == (usize)args_first: argument = value
                try self.program.numbers.push(value)
                self.skip_spaces()
            if self.peek() != 41: try self.fail("group syntax: expected ')'")
            self.at += 1
            return Term(kind = AtomKind.call, first = first, count = count, function = function, argument = argument, args_first = args_first, args_count = (u32)self.program.numbers.count - args_first, rule = (i32)rule)
        if word.length == 0: try self.fail("group syntax: expected a term")
        return Term(kind = AtomKind.name, text = (u32)start, text_length = (u32)word.length)

    ## `n`, `n-m`, `n-m:step`, `n-m:keep,step`, `n-`, or `n e m`.
    func numbers_atom() -> Term!:
        let first = try self.number()
        if self.peek() == 101 and is_digit(self.peek_at(1)):
            self.at += 1
            let side = try self.number()
            let index = (u32)self.program.numbers.count
            try self.program.numbers.push(first)
            try self.program.numbers.push(side)
            return Term(kind = AtomKind.face_edge, first = index, count = 2)
        var last = first
        var keep = 1.0
        var step = 1.0
        if self.peek() == 45:
            self.at += 1
            last = try self.number() if is_digit(self.peek()) else -1.0
            if self.peek() == 58:
                self.at += 1
                step = try self.number()
                if self.peek() == 44:
                    self.at += 1
                    keep = step
                    step = try self.number()
                if step < 1.0 or keep < 1.0: try self.fail("group syntax: steps are at least 1")
        let index = (u32)self.program.numbers.count
        try self.program.numbers.push(first)
        try self.program.numbers.push(last)
        try self.program.numbers.push(keep)
        try self.program.numbers.push(step)
        if not ends_word(self.peek()): try self.fail("group syntax: unexpected text after a number")
        return Term(kind = AtomKind.range, first = index, count = 4)

    ## `p a`, `p a-b`, `p a-b-c…`.
    func point_edges() -> Term!:
        self.at += 1
        let index = (u32)self.program.numbers.count
        try self.program.numbers.push(try self.number())
        while self.peek() == 45:
            self.at += 1
            try self.program.numbers.push(try self.number())
        if not ends_word(self.peek()): try self.fail("group syntax: expected p<point>-<point>")
        return Term(kind = AtomKind.point_edges, first = index, count = (u32)(self.program.numbers.count - (usize)index))

    ## `{glob ^glob …}`: each a name term.
    func name_filter() -> Term!:
        self.at += 1
        var collected = Growing[Term]()
        defer collected.close()
        while true:
            self.skip_spaces()
            if self.peek() == 125:
                self.at += 1
                break
            if self.peek() == 0: try self.fail("group syntax: expected '}'")
            var combine = Combine.add
            if self.peek() == 94:
                combine = Combine.remove
                self.at += 1
            let start = self.at
            while not ends_word(self.peek()) and self.peek() != 125: self.at += 1
            if self.at == start: try self.fail("group syntax: expected a name")
            try collected.push(Term(combine = combine, kind = AtomKind.name, text = (u32)start, text_length = (u32)(self.at - start)))
        let first = (u32)self.program.terms.count
        for term in collected.view(): try self.program.terms.push(term)
        return Term(kind = AtomKind.names, first = first, count = (u32)collected.count)

    ## `@name[.x|[i]][op values]`. No spaces inside.
    func attribute() -> Term!:
        self.at += 1
        let start = self.at
        while is_name_byte(self.peek()) or self.peek() == 58: self.at += 1
        if self.at == start: try self.fail("group syntax: expected an attribute name after '@'")
        var term = Term(kind = AtomKind.attribute, text = (u32)start, text_length = (u32)(self.at - start))
        if self.peek() == 46 and component_of(self.peek_at(1)) >= 0 and not is_name_byte(self.peek_at(2)):
            term.component = component_of(self.peek_at(1))
            self.at += 2
        elif self.peek() == 91:
            self.at += 1
            term.component = (i32)(try self.number())
            if self.peek() != 93: try self.fail("group syntax: expected ']'")
            self.at += 1
        term.compare = self.comparison()
        if term.compare == Compare.exists: return term
        term.first = (u32)self.program.numbers.count
        term.spans_first = (u32)(self.program.spans.count // 2)
        if self.peek() == 34:
            self.at += 1
            while self.peek() != 34:
                if self.peek() == 0: try self.fail("group syntax: expected '\"'")
                self.skip_spaces()
                if self.peek() == 34: break
                try self.value(true)
            self.at += 1
        else:
            try self.value(false)
            while self.peek() == 44:
                self.at += 1
                try self.value(false)
        term.count = (u32)(self.program.numbers.count - (usize)term.first) // 2
        term.spans_count = (u32)(self.program.spans.count // 2) - term.spans_first
        if term.count == 0 and term.spans_count == 0: try self.fail("group syntax: expected a value")
        if not ends_word(self.peek()): try self.fail("group syntax: unexpected text after a value")
        return term

    func comparison() -> Compare:
        let a = self.peek()
        let b = self.peek_at(1)
        if a == 61 and b == 61:
            self.at += 2
            return Compare.equal
        if a == 33 and b == 61:
            self.at += 2
            return Compare.not_equal
        if a == 60 and b == 61:
            self.at += 2
            return Compare.less_equal
        if a == 62 and b == 61:
            self.at += 2
            return Compare.greater_equal
        if a == 61 or a == 60 or a == 62 or a == 38:
            self.at += 1
            return Compare.equal if a == 61 else (Compare.less if a == 60 else (Compare.greater if a == 62 else Compare.bits))
        return Compare.exists

    ## One value: a number, a range `a-b` (low/high pair), or a text glob.
    func value(quoted: bool) -> !:
        let start = self.at
        while not (self.peek() == 0 or self.peek() == 32 or self.peek() == 9 or self.peek() == 41 or (self.peek() == 44 and not quoted) or (self.peek() == 34 and quoted)): self.at += 1
        let text = (str)self.program.source.items[start..<self.at]
        if text.length == 0: try self.fail("group syntax: expected a value")
        if let low = parse_number(text):
            try self.program.numbers.push(low)
            try self.program.numbers.push(low)
            return
        # `a-b` (the dash after the first character, so `-5` stays a number).
        for split in 1..<text.length:
            if text.bytes[split] != 45: continue
            let low = parse_number((str)text.bytes[..<split]) else break
            let high = parse_number((str)text.bytes[split + 1..]) else break
            try self.program.numbers.push(low)
            try self.program.numbers.push(high)
            return
        try self.program.spans.push((u32)start)
        try self.program.spans.push((u32)text.length)

    ## A number with an optional leading minus (a call's argument).
    func signed_number() -> f64!:
        if self.peek() == 45:
            self.at += 1
            return -(try self.number())
        return try self.number()

    func number() -> f64!:
        let start = self.at
        while is_digit(self.peek()) or self.peek() == 46: self.at += 1
        if let value = parse_number((str)self.program.source.items[start..<self.at]): return value
        try self.fail("group syntax: expected a number")
        return 0.0

## A decimal number (`-12`, `0.5`, `3e2` is not accepted), or none.
pub func parse_number(text: str) -> f64?:
    var at: usize = 0
    var negative = false
    if at < text.length and (text.bytes[at] == 45 or text.bytes[at] == 43):
        negative = text.bytes[at] == 45
        at += 1
    if at == text.length: return none
    var value = 0.0
    var digits = 0
    while at < text.length and is_digit(text.bytes[at]):
        value = value * 10.0 + (f64)(text.bytes[at] - 48)
        at += 1
        digits += 1
    if at < text.length and text.bytes[at] == 46:
        at += 1
        var scale = 0.1
        while at < text.length and is_digit(text.bytes[at]):
            value += (f64)(text.bytes[at] - 48) * scale
            scale *= 0.1
            at += 1
            digits += 1
    if at != text.length or digits == 0: return none
    return -value if negative else value

func function_named(word: str) -> Function?:
    if word == "grow": return Function.grow
    if word == "shrink": return Function.shrink
    if word == "border": return Function.border
    if word == "connected": return Function.connected
    if word == "loop": return Function.loop
    if word == "ring": return Function.ring
    if word == "convert": return Function.convert
    return none

## x y z w, r g b a, u v w: the component a suffix names.
func component_of(byte: u8) -> i32:
    if byte == 120 or byte == 114 or byte == 117: return 0
    if byte == 121 or byte == 103 or byte == 118: return 1
    if byte == 122 or byte == 98: return 2
    if byte == 119 or byte == 97: return 3
    return -1

func is_digit(byte: u8) -> bool:
    return byte >= 48 and byte <= 57

func is_name_byte(byte: u8) -> bool:
    return (byte >= 97 and byte <= 122) or (byte >= 65 and byte <= 90) or is_digit(byte) or byte == 95

## Whether `byte` ends a word: the end, a space, ')' or ','.
func ends_word(byte: u8) -> bool:
    return byte == 0 or byte == 32 or byte == 9 or byte == 10 or byte == 41 or byte == 44