Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-svg

Source of release 0.9.2

0.9.2 / src / svg / xml.lucb

#==============================================================================================
#
#   svg/xml - An XML reader for SVG documents
#
#   DESCRIPTION:
#       Parses a document into a tree of elements and text nodes, the shape the SVG tree
#       (tree.lucb) is built from. It reads the prolog and a DOCTYPE's internal subset,
#       whose `<!ENTITY>` declarations may then stand for text or for markup; decodes the
#       five predefined entities and character references; normalises white space in
#       attribute values; resolves namespace prefixes (only the SVG, XLink and XML
#       namespaces matter to SVG); and keeps CDATA as text. Comments and processing
#       instructions are dropped. Malformed markup, such as a mismatched end tag, is an
#       error, as it is for a browser showing an SVG file.
#
#==============================================================================================

## The namespaces SVG cares about; any other is `other`.
enum Space:
    absent
    svg
    xlink
    xml
    other

## An element or a run of text. Links are node indices; 0 (the document node, which is
## never a child) means none.
struct XmlNode:
    var element: bool = false
    var space: Space = Space.absent
    ## The local name, and the name as written (with its prefix) to match the end tag.
    var name: str = ""
    var qualified: str = ""
    var parent: u32 = 0
    var first: u32 = 0
    var last: u32 = 0
    var next: u32 = 0
    var attr_start: u32 = 0
    var attr_end: u32 = 0
    ## A text node's characters, entities decoded.
    var text: str = ""

## An attribute with its namespace resolved; namespace declarations are not kept.
struct XmlAttr:
    var space: Space = Space.absent
    var name: str = ""
    var value: str = ""

## An entity the DOCTYPE declares.
struct EntityDeclaration:
    var name: str = ""
    var value: str = ""

## A namespace prefix in scope: `prefix` ("" for the default) names `space` until the
## element at `depth` closes.
struct Binding:
    var prefix: str = ""
    var space: Space = Space.absent
    var depth: usize = 0

## A parsed XML document: node 0 is the document, its element children the root.
struct Xml:
    var nodes: List[XmlNode] = List[XmlNode]()
    var attrs: List[XmlAttr] = List[XmlAttr]()
    var arena: Arena = Arena()
    var entities: List[EntityDeclaration] = List[EntityDeclaration]()
    var bindings: List[Binding] = List[Binding]()
    var text: TextBuilder = TextBuilder()
    var current: u32 = 0
    var depth: usize = 0
    var expanded: usize = 0

    func release():
        self.nodes.release()
        self.attrs.release()
        self.arena.release()
        self.entities.release()
        self.bindings.release()
        self.text.release()

    ## Append `node` as the last child of the open element; answer its index.
    func append(node: XmlNode) -> u32!:
        var child = node
        child.parent = self.current
        let index = (u32)self.nodes.used
        try self.nodes.push(child)
        let parent = self.current
        if self.nodes.items[parent].last != 0:
            self.nodes.items[self.nodes.items[parent].last].next = index
        else:
            self.nodes.items[parent].first = index
        self.nodes.items[parent].last = index
        return index

    ## Turn the characters gathered so far into a text node.
    func flush_text() -> !:
        if self.text.bytes.used == 0:
            return
        let text = try self.text.finish(&self.arena)
        _ = try self.append(XmlNode(text = text))

## How deeply entities may expand inside one another, and how many bytes they may
## produce in all: enough for any honest document, too little for an entity bomb.
let entity_depth: usize = 8
let entity_budget: usize = 4194304

# mark: Scanning ==============================================================================

## A position in some text being parsed: the source, or an entity's replacement text.
struct Cursor:
    var data: const u8[]
    var pos: usize = 0

    func at_end() -> bool:
        return self.pos >= self.data.length

    func peek() -> u8:
        return self.data[self.pos] if self.pos < self.data.length else 0

    func looking_at(text: str) -> bool:
        if self.pos + text.length > self.data.length:
            return false
        for index in 0..<text.length:
            if self.data[self.pos + index] != text.bytes[index]:
                return false
        return true

    func skip_space():
        while self.pos < self.data.length and is_space(self.data[self.pos]):
            self.pos += 1

    ## Move past the next `text`, answering whether it was found.
    func skip_past(text: str) -> bool:
        while self.pos < self.data.length:
            if self.looking_at(text):
                self.pos += text.length
                return true
            self.pos += 1
        return false

    ## A name: everything up to white space or one of `=/>?'"[`.
    func name() -> str:
        let start = self.pos
        while self.pos < self.data.length:
            let byte = self.data[self.pos]
            if is_space(byte) or byte == '=' or byte == '/' or byte == '>' or byte == '?' or byte == '"' or byte == '\'' or byte == '[' or byte == ';':
                break
            self.pos += 1
        return (str)self.data[start..<self.pos]

# mark: Parsing ===============================================================================

## Parse `source` into `xml`.
func parse_xml(source: str, xml: Xml*) -> !:
    try xml.nodes.push(XmlNode())
    var cursor = Cursor(data = source.bytes)
    if cursor.looking_at("\u{FEFF}"):
        cursor.pos += 3
    try parse_content(xml, &cursor, 0)
    try xml.flush_text()
    if xml.depth != 0:
        error(invalid, "an element is not closed")

## Parse markup and character data until the cursor's end (or, inside an entity, its
## replacement text's end). `level` counts entity expansions in progress.
func parse_content(xml: Xml*, cursor: Cursor*, level: usize) -> !:
    while not cursor.at_end():
        let byte = cursor.peek()
        if byte == '<':
            if cursor.looking_at("<!--"):
                if not cursor.skip_past("-->"):
                    error(invalid, "an unclosed comment")
            elif cursor.looking_at("<![CDATA["):
                cursor.pos += 9
                let start = cursor.pos
                if not cursor.skip_past("]]>"):
                    error(invalid, "an unclosed CDATA section")
                try xml.text.add_all(cursor.data[start..<cursor.pos - 3])
            elif cursor.looking_at("<!DOCTYPE"):
                try parse_doctype(xml, cursor)
            elif cursor.looking_at("<?"):
                if not cursor.skip_past("?>"):
                    error(invalid, "an unclosed processing instruction")
            elif cursor.looking_at("</"):
                try xml.flush_text()
                try parse_end_tag(xml, cursor)
            else:
                try xml.flush_text()
                try parse_start_tag(xml, cursor)
        elif byte == '&':
            try parse_reference(xml, cursor, level)
        else:
            if xml.depth > 0:
                try xml.text.add(byte)
            cursor.pos += 1

## A `&...;` in content: a character, a predefined entity, or a declared one, whose text
## is parsed in place (so it may hold elements).
func parse_reference(xml: Xml*, cursor: Cursor*, level: usize) -> !:
    let start = cursor.pos
    cursor.pos += 1
    let name = cursor.name()
    if cursor.peek() != ';':
        error(invalid, "an unterminated entity reference")
    cursor.pos += 1
    if let character = predefined(name):
        if xml.depth > 0:
            try add_character(&xml.text, character)
        return
    for declared in xml.entities.view():
        if declared.name == name:
            if level >= entity_depth or xml.expanded + declared.value.length > entity_budget:
                error(invalid, "entities expand too far")
            xml.expanded += declared.value.length
            var inner = Cursor(data = declared.value.bytes)
            try parse_content(xml, &inner, level + 1)
            return
    # An unknown entity is kept as written.
    if xml.depth > 0:
        try xml.text.add_all(cursor.data[start..<cursor.pos])

## The character `&name;` stands for when it is predefined or a character reference.
func predefined(name: str) -> u32?:
    if name == "lt": return 60
    if name == "gt": return 62
    if name == "amp": return 38
    if name == "apos": return 39
    if name == "quot": return 34
    if name.length >= 2 and name.bytes[0] == '#':
        var value: u32 = 0
        let hexadecimal = name.bytes[1] == 'x' or name.bytes[1] == 'X'
        let digits = name.bytes[2..] if hexadecimal else name.bytes[1..]
        if digits.length == 0 or digits.length > 8:
            return none
        for digit in digits:
            if hexadecimal:
                let part = hex_digit(digit) else return none
                value = value * 16 + part
            elif is_digit(digit):
                value = value * 10 + (u32)(digit - '0')
            else:
                return none
        if value == 0 or value > 0x10FFFF or (value >= 0xD800 and value <= 0xDFFF):
            return none
        return value
    return none

## Append `scalar` to `builder` as UTF-8.
func add_character(builder: TextBuilder*, scalar: u32) -> !:
    if scalar < 0x80:
        try builder.add((u8)scalar)
    elif scalar < 0x800:
        try builder.add((u8)(0xC0 | (scalar >> 6)))
        try builder.add((u8)(0x80 | (scalar & 0x3F)))
    elif scalar < 0x10000:
        try builder.add((u8)(0xE0 | (scalar >> 12)))
        try builder.add((u8)(0x80 | ((scalar >> 6) & 0x3F)))
        try builder.add((u8)(0x80 | (scalar & 0x3F)))
    else:
        try builder.add((u8)(0xF0 | (scalar >> 18)))
        try builder.add((u8)(0x80 | ((scalar >> 12) & 0x3F)))
        try builder.add((u8)(0x80 | ((scalar >> 6) & 0x3F)))
        try builder.add((u8)(0x80 | (scalar & 0x3F)))

## `<!DOCTYPE ...>`: its internal subset's entity declarations are kept, the rest skipped.
func parse_doctype(xml: Xml*, cursor: Cursor*) -> !:
    cursor.pos += 9
    while not cursor.at_end() and cursor.peek() != '[' and cursor.peek() != '>':
        let byte = cursor.peek()
        cursor.pos += 1
        if byte == '"' or byte == '\'':
            while not cursor.at_end() and cursor.peek() != byte:
                cursor.pos += 1
            cursor.pos += 1
    if cursor.peek() == '[':
        cursor.pos += 1
        while not cursor.at_end() and cursor.peek() != ']':
            if cursor.looking_at("<!ENTITY"):
                cursor.pos += 8
                cursor.skip_space()
                if cursor.peek() == '%':
                    cursor.pos += 1
                    cursor.skip_space()
                let name = cursor.name()
                cursor.skip_space()
                let quote = cursor.peek()
                if quote == '"' or quote == '\'':
                    cursor.pos += 1
                    let start = cursor.pos
                    while not cursor.at_end() and cursor.peek() != quote:
                        cursor.pos += 1
                    try xml.entities.push(EntityDeclaration(name = name, value = (str)cursor.data[start..<cursor.pos]))
                if not cursor.skip_past(">"):
                    error(invalid, "an unclosed entity declaration")
            elif cursor.looking_at("<!--"):
                _ = cursor.skip_past("-->")
            elif cursor.peek() == '<':
                # Other declarations, with any quoted text in them.
                while not cursor.at_end() and cursor.peek() != '>':
                    let byte = cursor.peek()
                    cursor.pos += 1
                    if byte == '"' or byte == '\'':
                        while not cursor.at_end() and cursor.peek() != byte:
                            cursor.pos += 1
                        cursor.pos += 1
                cursor.pos += 1
            else:
                cursor.pos += 1
        cursor.pos += 1
    if not cursor.skip_past(">"):
        error(invalid, "an unclosed DOCTYPE")

## `<name attr="value" ...>` or `<name .../>`.
func parse_start_tag(xml: Xml*, cursor: Cursor*) -> !:
    cursor.pos += 1
    let qualified = cursor.name()
    if qualified.length == 0:
        error(invalid, "an element without a name")
    let attr_start = xml.attrs.used
    let depth = xml.depth + 1
    while true:
        cursor.skip_space()
        if cursor.at_end():
            error(invalid, "an unclosed start tag")
        let byte = cursor.peek()
        if byte == '>' or byte == '/':
            break
        let name = cursor.name()
        cursor.skip_space()
        if name.length == 0 or cursor.peek() != '=':
            error(invalid, "an attribute without a value")
        cursor.pos += 1
        cursor.skip_space()
        let quote = cursor.peek()
        if quote != '"' and quote != '\'':
            error(invalid, "an unquoted attribute value")
        cursor.pos += 1
        let start = cursor.pos
        while not cursor.at_end() and cursor.peek() != quote:
            cursor.pos += 1
        if cursor.at_end():
            error(invalid, "an unclosed attribute value")
        let value = try attribute_value(xml, cursor.data[start..<cursor.pos], 0)
        cursor.pos += 1
        if name == "xmlns":
            try xml.bindings.push(Binding(prefix = "", space = space_of(value), depth = depth))
        elif strings.starts_with(name, "xmlns:"):
            try xml.bindings.push(Binding(prefix = (str)name.bytes[6..], space = space_of(value), depth = depth))
        else:
            try xml.attrs.push(XmlAttr(name = name, value = value))
    # Prefixes resolve once every declaration on the tag is known.
    for index in attr_start..<xml.attrs.used:
        let (prefix, local_name) = split_name(xml.attrs.items[index].name)
        if prefix.length > 0:
            xml.attrs.items[index].space = lookup(xml, prefix)
            xml.attrs.items[index].name = local_name
    let (prefix, local_name) = split_name(qualified)
    let node = try xml.append(XmlNode(element = true, space = lookup(xml, prefix), name = local_name, qualified = qualified,
                                      attr_start = (u32)attr_start, attr_end = (u32)xml.attrs.used))
    if cursor.peek() == '/':
        cursor.pos += 1
        if cursor.peek() != '>':
            error(invalid, "a malformed empty-element tag")
        cursor.pos += 1
        pop_bindings(xml, depth)
        return
    cursor.pos += 1
    xml.current = node
    xml.depth = depth

## `</name>`, which must close the open element.
func parse_end_tag(xml: Xml*, cursor: Cursor*) -> !:
    cursor.pos += 2
    let name = cursor.name()
    cursor.skip_space()
    if cursor.peek() != '>':
        error(invalid, "a malformed end tag")
    cursor.pos += 1
    if xml.depth == 0 or xml.nodes.items[xml.current].qualified != name:
        error(invalid, "an end tag that does not match its start tag")
    pop_bindings(xml, xml.depth)
    xml.current = xml.nodes.items[xml.current].parent
    xml.depth -= 1

## Drop the namespace declarations made by the element at `depth`.
func pop_bindings(xml: Xml*, depth: usize):
    while xml.bindings.used > 0 and xml.bindings.items[xml.bindings.used - 1].depth >= depth:
        xml.bindings.used -= 1

## The namespace a URI names.
func space_of(uri: str) -> Space:
    if uri == "http://www.w3.org/2000/svg":
        return Space.svg
    if uri == "http://www.w3.org/1999/xlink":
        return Space.xlink
    if uri == "http://www.w3.org/XML/1998/namespace":
        return Space.xml
    return Space.other

## The namespace `prefix` names where the parser stands; "" is the default namespace.
func lookup(xml: const Xml*, prefix: str) -> Space:
    if prefix == "xml":
        return Space.xml
    var index = xml.bindings.used
    while index > 0:
        index -= 1
        if xml.bindings.items[index].prefix == prefix:
            return xml.bindings.items[index].space
    return Space.absent if prefix.length == 0 else Space.other

## A qualified name's prefix and local part.
func split_name(name: str) -> (str, str):
    for index in 0..<name.length:
        if name.bytes[index] == ':':
            return ((str)name.bytes[..<index], (str)name.bytes[index + 1..])
    return ("", name)

## An attribute value with references decoded and white space characters made spaces.
## A value that needs no change stays a view of the source.
func attribute_value(xml: Xml*, raw: const u8[], level: usize) -> str!:
    var plain = true
    for byte in raw:
        if byte == '&' or byte == '\t' or byte == '\n' or byte == '\r':
            plain = false
            break
    if plain:
        return (str)raw
    var builder = TextBuilder()
    defer builder.release()
    try expand_value(xml, &builder, raw, level)
    return try builder.finish(&xml.arena)

func expand_value(xml: Xml*, builder: TextBuilder*, raw: const u8[], level: usize) -> !:
    var cursor = Cursor(data = raw)
    while not cursor.at_end():
        let byte = cursor.peek()
        if byte == '&':
            let start = cursor.pos
            cursor.pos += 1
            let name = cursor.name()
            if cursor.peek() == ';':
                cursor.pos += 1
                if let character = predefined(name):
                    try add_character(builder, character)
                    continue
                var found = false
                for declared in xml.entities.view():
                    if declared.name == name and level < entity_depth:
                        try expand_value(xml, builder, declared.value.bytes, level + 1)
                        found = true
                        break
                if found:
                    continue
            try builder.add_all(raw[start..<cursor.pos])
        else:
            try builder.add(' ' if byte == '\t' or byte == '\n' or byte == '\r' else byte)
            cursor.pos += 1