Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-svg

Source of release 0.9.2

0.9.2 / src / svg / tree_build.lucb

#==============================================================================================
#
#   svg/tree_build - Building the SVG tree from XML, with the cascade
#
#   DESCRIPTION:
#       Walks the XML tree and keeps its SVG elements. Each element's attributes are
#       gathered in cascade order, a later one replacing an earlier one of the same name:
#       presentation attributes first, then the declarations of every matching style rule
#       in order of specificity, then the `style` attribute's; a value marked
#       `!important` is never replaced by a later one. `inherit` takes the value
#       the parent's chain resolved, or the property's initial value. A `<use>` gets the
#       element it references built again as its child, with ids dropped; references
#       back to the `use` or its own ancestry are refused, so no copy contains itself.
#
#==============================================================================================

## How deeply elements, and `use` copies within copies, may nest; and how many nodes a
## tree may hold.
let depth_limit: usize = 1024
let node_limit: usize = 1000000

# mark: The document ==========================================================================

## Parse `source` into `tree`: XML first, then the style sheets, then the SVG tree.
func build_tree(source: str, tree: Tree*) -> !:
    try parse_xml(source, &tree.xml)
    let xml = &tree.xml
    try collect_sheets(tree)
    var xml_ids = List[IdEntry]()
    defer xml_ids.release()
    for index in 1..<xml.nodes.used:
        if xml.nodes.items[index].element:
            if let id = xml_attribute(xml, (u32)index, "id"):
                try xml_ids.push(IdEntry(id = id, node = (u32)index))
    try sort_ids(&xml_ids, true)
    try tree.nodes.push(Node())
    var builder = Builder(tree = tree, xml_ids = xml_ids.view())
    try builder.children(0, 0, 0, false, 0)
    let root = tree.root_element()
    if root == 0 or tree.tag(root) != Tag.svg:
        error(invalid, "the document's root element is not svg")
    for index in 1..<tree.nodes.used:
        if tree.nodes.items[index].kind == Kind.element:
            if let id = tree.attribute((u32)index, Attr.id):
                try tree.ids.push(IdEntry(id = id, node = (u32)index))
    try sort_ids(&tree.ids, false)
    try break_cycles(tree)

## Read every `<style>` element (of type text/css, or untyped) into the tree's sheet.
func collect_sheets(tree: Tree*) -> !:
    let xml = &tree.xml
    for index in 1..<xml.nodes.used:
        let node = xml.nodes.items[index]
        if not node.element or node.name != "style" or not (node.space == Space.absent or node.space == Space.svg):
            continue
        if let kind = xml_attribute(xml, (u32)index, "type"):
            if kind != "text/css" and kind != "":
                continue
        var child = node.first
        while child != 0:
            if not xml.nodes.items[child].element:
                try parse_sheet(&tree.sheet, xml.nodes.items[child].text)
            child = xml.nodes.items[child].next

## Sort `ids` by id, stably, then keep one entry per id: the first when `first`, else the
## last (an XML lookup takes the first element with an id, the tree the last).
func sort_ids(ids: List[IdEntry]*, first: bool) -> !:
    let items = ids.view()
    if items.length < 2:
        return
    let scratch = try new IdEntry[items.length] --- in memory.heap
    defer free(scratch) in memory.heap
    var width: usize = 1
    while width < items.length:
        var start: usize = 0
        while start < items.length:
            let middle = math_min(start + width, items.length)
            let end = math_min(start + 2 * width, items.length)
            var a = start
            var b = middle
            var out = start
            while out < end:
                if a < middle and (b >= end or compare_text(items[a].id, items[b].id) <= 0):
                    scratch[out] = items[a]
                    a += 1
                else:
                    scratch[out] = items[b]
                    b += 1
                out += 1
            start = end
        memory.copy(items, scratch, items.length)
        width *= 2
    var kept: usize = 0
    for index in 0..<items.length:
        if kept > 0 and items[kept - 1].id == items[index].id:
            if not first:
                items[kept - 1] = items[index]
            continue
        items[kept] = items[index]
        kept += 1
    ids.truncate(kept)

func math_min(a: usize, b: usize) -> usize:
    return a if a < b else b

# mark: Elements ==============================================================================

## The SVG tag of an XML element in the SVG namespace (or none), if SVG has it.
func svg_tag(xml: const Xml*, index: u32) -> Tag?:
    let node = xml.nodes.items[index]
    if not node.element or not (node.space == Space.absent or node.space == Space.svg):
        return none
    return tag_named(node.name)

## The state of one tree build.
struct Builder:
    var tree: Tree*
    var xml_ids: const IdEntry[]

    ## Build the XML children of `xml_parent` under tree node `parent`.
    func children(xml_parent: u32, origin: u32, parent: u32, ignore_ids: bool, depth: usize) -> !:
        var child = self.tree.xml.nodes.items[xml_parent].first
        while child != 0:
            try self.element(child, origin, parent, ignore_ids, depth)
            child = self.tree.xml.nodes.items[child].next

    ## Build XML element `index` under `parent`, with its content. `origin` is the `use`
    ## being expanded, if any.
    func element(index: u32, origin: u32, parent: u32, ignore_ids: bool, depth: usize) -> !:
        if depth > depth_limit:
            error(invalid, "elements nest too deeply")
        var tag = svg_tag(&self.tree.xml, index) else return
        if tag == Tag.style:
            return
        if tag == Tag.a:
            tag = Tag.g
        let node = try self.attributes(index, parent, tag, ignore_ids)
        if tag == Tag.text:
            try self.text(index, node)
        elif tag == Tag.use:
            try self.expand_use(index, origin, node, depth)
        else:
            try self.children(index, origin, node, ignore_ids, depth + 1)

    ## Append a tree node for XML element `index` with its cascaded attributes.
    func attributes(index: u32, parent: u32, tag: Tag, ignore_ids: bool) -> u32!:
        let tree = self.tree
        let xml = &tree.xml
        let start = tree.attrs.used
        var href_at: usize? = none
        let element = xml.nodes.items[index]
        for at in element.attr_start..<element.attr_end:
            let raw = xml.attrs.items[at]
            if raw.space == Space.other:
                continue
            let name = attr_named(raw.name) else continue
            if ignore_ids and name == Attr.id:
                continue
            # These are honoured only from CSS and `style`.
            if name == Attr.mix_blend_mode or name == Attr.isolation or name == Attr.font_kerning:
                continue
            if name == Attr.image_rendering and (raw.value == "smooth" or raw.value == "high-quality" or raw.value == "crisp-edges" or raw.value == "pixelated"):
                continue
            if name == Attr.href:
                if raw.space != Space.absent and raw.space != Space.xlink:
                    continue
                # A plain `href` wins over `xlink:href`, wherever they stand.
                if let previous = href_at:
                    if raw.space == Space.absent:
                        tree.attrs.items[previous].value = raw.value
                    continue
            let added = try self.append_attribute(parent, tag, name, raw.value, false)
            if added and name == Attr.href:
                href_at = tree.attrs.used - 1
        let sheet = &tree.sheet
        for rule in sheet.rules.view():
            if rule_matches(sheet, rule, xml, index):
                for d in rule.declaration_start..<rule.declaration_end:
                    try self.declare(sheet.declarations.items[d], parent, tag, start)
        if let style = xml_attribute(xml, index, "style"):
            var declarations = List[Declaration]()
            defer declarations.release()
            try parse_declarations(&declarations, style)
            for declaration in declarations.view():
                try self.declare(declaration, parent, tag, start)
        if tree.nodes.used >= node_limit:
            error(invalid, "the document has too many elements")
        return try append_node(tree, parent, Node(kind = Kind.element, tag = tag, attr_start = (u32)start, attr_end = (u32)tree.attrs.used))

    ## Apply one CSS declaration to the element whose attributes start at `start`.
    func declare(declaration: Declaration, parent: u32, tag: Tag, start: usize) -> !:
        let important = declaration.important
        let value = declaration.value
        if declaration.name == "marker":
            try self.insert(Attr.marker_start, value, important, parent, tag, start)
            try self.insert(Attr.marker_mid, value, important, parent, tag, start)
            try self.insert(Attr.marker_end, value, important, parent, tag, start)
        elif declaration.name == "font":
            try self.font_shorthand(value, important, parent, tag, start)
        elif let name = attr_named(declaration.name):
            if is_presentation(name):
                try self.insert(name, value, important, parent, tag, start)

    ## Set `name` from CSS: it replaces a value set earlier unless that one is important
    ## (important values are not replaced by later ones of any kind).
    func insert(name: Attr, value: str, important: bool, parent: u32, tag: Tag, start: usize) -> !:
        let tree = self.tree
        var existing: usize? = none
        for at in start..<tree.attrs.used:
            if tree.attrs.items[at].name == name:
                existing = at
                break
        let added = try self.append_attribute(parent, tag, name, value, important)
        if not added:
            return
        if let at = existing:
            let last = tree.attrs.used - 1
            if not tree.attrs.items[at].important:
                tree.attrs.items[at] = tree.attrs.items[last]
            tree.attrs.used -= 1

    ## Append an attribute unless it is one the tree does not keep; `inherit` resolves here.
    func append_attribute(parent: u32, tag: Tag, name: Attr, value: str, important: bool) -> bool!:
        if name == Attr.style or name == Attr.class_name:
            return false
        if tag == Tag.tspan and name == Attr.href:
            return false
        if accepts_inherit(name) and strings.trim(value) == "inherit":
            return try self.inherit(parent, name)
        try self.tree.attrs.push(Attribute(name = name, value = value, important = important))
        return true

    ## `name: inherit` under `parent`: an inherited property takes the nearest ancestor's
    ## value, any other the parent's; failing that, the initial value.
    func inherit(parent: u32, name: Attr) -> bool!:
        let tree = self.tree
        var at = parent
        while at != 0:
            if let value = tree.attribute(at, name):
                try tree.attrs.push(Attribute(name = name, value = value))
                return true
            if not is_inherited(name):
                break
            at = tree.nodes.items[at].parent
        let initial = attr_initial[(usize)(u16)name]
        if initial.length == 0:
            return false
        try tree.attrs.push(Attribute(name = name, value = initial))
        return true

    ## Expand `<use>` (XML `index`, tree `node`): build what it references as its child.
    func expand_use(index: u32, origin: u32, node: u32, depth: usize) -> !:
        let xml = &self.tree.xml
        let target_link = self.xml_link(index) else return
        if target_link == index or target_link == origin:
            return
        if svg_tag(xml, target_link) == none:
            return
        # A `use` inside the target that references this `use`, or the target itself, is
        # a cycle: the whole `use` is dropped.
        var stack = List[u32]()
        defer stack.release()
        try stack.push(xml.nodes.items[target_link].first)
        while stack.used > 0:
            var child = stack.items[stack.used - 1]
            stack.used -= 1
            while child != 0:
                if xml.nodes.items[child].element:
                    if svg_tag(xml, child) == Tag.use:
                        if let target = self.xml_link(child):
                            if target == index or target == target_link:
                                return
                    if xml.nodes.items[child].first != 0:
                        try stack.push(xml.nodes.items[child].first)
                child = xml.nodes.items[child].next
        try self.element(target_link, index, node, true, depth + 1)

    ## The XML element an XML element's `href` (or else `xlink:href`) names.
    func xml_link(index: u32) -> u32?:
        let xml = &self.tree.xml
        let element = xml.nodes.items[index]
        var value: str? = none
        for at in element.attr_start..<element.attr_end:
            let raw = xml.attrs.items[at]
            if raw.name == "href" and raw.space == Space.absent:
                value = raw.value
        if value == none:
            for at in element.attr_start..<element.attr_end:
                let raw = xml.attrs.items[at]
                if raw.name == "href" and raw.space == Space.xlink:
                    value = raw.value
        let text = value else return none
        let id = iri(text) else return none
        return find_id(self.xml_ids, id)

## The node of `id` in sorted `ids`.
func find_id(ids: const IdEntry[], id: str) -> u32?:
    var low: usize = 0
    var high = ids.length
    while low < high:
        let middle = (low + high) // 2
        let order = compare_text(ids[middle].id, id)
        if order == 0:
            return ids[middle].node
        if order < 0:
            low = middle + 1
        else:
            high = middle
    return none

## Append `node` as the last child of `parent`; answer its index.
func append_node(tree: Tree*, parent: u32, node: Node) -> u32!:
    var child = node
    child.parent = parent
    let index = (u32)tree.nodes.used
    try tree.nodes.push(child)
    if tree.nodes.items[parent].last != 0:
        tree.nodes.items[tree.nodes.items[parent].last].next = index
    else:
        tree.nodes.items[parent].first = index
    tree.nodes.items[parent].last = index
    return index

# mark: Reference cycles ======================================================================

## Break the reference cycles a document can make, as resvg does, by setting the
## attribute that closes each to `none`: a pattern's content painting with the pattern,
## and clip paths, masks and filters that apply themselves, directly or through what
## they reference.
func break_cycles(tree: Tree*) -> !:
    # An feImage drawing the element its own filter is on: that element loses the filter.
    for index in 1..<tree.nodes.used:
        let node = (u32)index
        if tree.nodes.items[node].kind != Kind.element or tree.tag(node) != Tag.fe_image:
            continue
        let target = tree.linked(node, Attr.href) else continue
        let filter = tree.nodes.items[node].parent
        let id = tree.element_id(filter)
        if id.length == 0:
            continue
        let value = tree.attribute(target, Attr.filter) else continue
        var wanted: u8[256]
        let reference = strings.format(wanted, f"url(#{id})") catch _:
            recover ""
        if reference.length > 0 and strings.contains(value, reference):
            set_none(tree, target, Attr.filter)
    for _ in 0..<1024:
        let found = (try find_cycle(tree)) else return
        set_none(tree, found.0, found.1)

## Set attribute `name` of `node` to `none`.
func set_none(tree: Tree*, node: u32, name: Attr):
    let item = tree.nodes.items[node]
    for at in item.attr_start..<item.attr_end:
        if tree.attrs.items[at].name == name:
            tree.attrs.items[at].value = "none"

## The first (element, attribute) that closes a cycle, if any.
func find_cycle(tree: const Tree*) -> (u32, Attr)?!:
    let pairs: Tag[3] = [Tag.clip_path, Tag.mask, Tag.filter]
    let names: Attr[3] = [Attr.clip_path, Attr.mask, Attr.filter]
    var below = List[u32]()
    defer below.release()
    var inner = List[u32]()
    defer inner.release()
    for index in 1..<tree.nodes.used:
        let node = (u32)index
        if tree.nodes.items[node].kind != Kind.element:
            continue
        let tag = tree.tag(node)
        for kind in 0..<pairs.length:
            if tag != pairs[kind]:
                continue
            let name = names[kind]
            below.used = 0
            try descendants(tree, node, &below)
            for child in below.view():
                let target = tree.linked(child, name) else continue
                if target == node:
                    return (child, name)
                inner.used = 0
                try descendants(tree, target, &inner)
                for deeper in inner.view():
                    if tree.linked(deeper, name) == node:
                        return (deeper, name)
        if tag == Tag.pattern:
            let id = tree.element_id(node)
            if id.length == 0:
                continue
            for paint_name in [Attr.fill, Attr.stroke]:
                below.used = 0
                try descendants(tree, node, &below)
                for child in below.view():
                    let value = tree.attribute(child, paint_name) else continue
                    let link = func_iri(value) else continue
                    if link == id:
                        return (child, paint_name)
                    let target = tree.element_by_id(link) else continue
                    inner.used = 0
                    try descendants(tree, target, &inner)
                    for deeper in inner.view():
                        let other = tree.attribute(deeper, paint_name) else continue
                        if (func_iri(other) else "") == id:
                            return (deeper, paint_name)
    return none

## `node` and every element below it, in document order.
func descendants(tree: const Tree*, node: u32, out: List[u32]*) -> !:
    try out.push(node)
    var child = tree.nodes.items[node].first
    while child != 0:
        if tree.nodes.items[child].kind == Kind.element:
            try descendants(tree, child, out)
        child = tree.nodes.items[child].next