1# xml - reading and writing XML.2#3# Parse gives back the root element, and an element is a plain object with4# four fields: Name, Attr, Children and Text.5#6# xml = import("encoding/xml")7#8# doc = xml.Parse(`<catalog n="2">9# <book id="a"><title>Tau</title></book>10# <book id="b"><title>More tau</title></book>11# </catalog>`)12#13# println(doc.Name, doc.Attr["n"])14# for i = 0; i < len(doc.Children); i++ {15# b = doc.Children[i]16# println(xml.Get(b, "id"), xml.Child(b, "title").Text)17# }18#19# A node holds no functions of its own, and that is on purpose: Child, All and20# Get are module functions taking a node. A document of any size is tens of21# thousands of elements, and three closures on each of them would cost more22# than the document does.23#24# Names are kept as they are written, prefix and all: an attribute called25# c:identifier is looked up under that name. Resolving prefixes to the URI26# their xmlns declared would mean carrying a scope through the whole parse,27# and a reader that wants it can read the xmlns attributes, which are there28# like any others.29#30# Text is the character data directly inside an element, as written. Nothing31# is trimmed: whitespace between elements is data as far as this is concerned,32# and strings.TrimSpace is there for whoever knows it is not.33#34# Text is all of an element's character data put together, so where text and35# elements are interleaved - a paragraph with emphasis in the middle of it -36# the order between the two is not kept, and writing such a node back out puts37# its text first. XML that carries data rather than prose does not interleave38# them, and that is the XML this is for.39#40# What it does not do: validation, DTDs, entities of your own. The five named41# ones are understood, and so are &#nn; and &#xhh;.42#43# How it goes about it, because it decides how fast it is:44#45# - The scan runs over the bytes of the source and not its characters.46# Indexing a string gives back a string, which is an allocation for every47# character looked at; indexing bytes gives an integer and allocates48# nothing.49# - A run of text with no entity in it is handed back as one slice of the50# source, which shares the buffer rather than copying it.51# - The hot loops read their state into locals first. Reading a field of an52# object costs a hash and a walk, and doing that per character is most of53# the time a parser written the obvious way spends.54# - Where and what line an error is on is worked out when there is an error,55# never before. Counting lines while scanning costs every document to56# serve the ones that fail.5758utf8 = import("unicode/utf8")59buffer = import("buffer")6061# The bytes the grammar turns on.62bTab = 963bLF = 1064bCR = 1365bSpace = 3266bBang = 3367bQuote = 3468bHash = 3569bAmp = 3870bApos = 3971bDash = 4572bSlash = 4773bSemi = 5974bLT = 6075bEq = 6176bGT = 6277bQuestion = 6378bUpperX = 8879bLBracket = 9180bRBracket = 9381bLowerX = 1208283# What may sit inside a name, and what counts as space, as tables indexed by84# the byte. A lexer asks these questions once per character of the document,85# and a table answers in one index where a chain of comparisons takes as many86# branches as there are characters it has to rule out.87nameByte = fn() {88 t = []89 for c = 0; c < 256; c++ {90 t = append(t, c > bSpace)91 }92 t[bLT] = false93 t[bGT] = false94 t[bSlash] = false95 t[bEq] = false96 t[bQuote] = false97 t[bApos] = false98 t[bQuestion] = false99 t[bBang] = false100 return t101}()102103spaceByte = fn() {104 t = []105 for c = 0; c < 256; c++ {106 t = append(t, false)107 }108 t[bSpace] = true109 t[bLF] = true110 t[bTab] = true111 t[bCR] = true112 return t113}()114115# Node builds an element. Exported because a program that writes XML rather116# than reading it has to make one.117Node = fn(name) {118 n = new()119 n.Name = name120 n.Attr = {}121 n.Children = []122 n.Text = ""123 return n124}125126# --- reading127128Parser = fn(src) {129 p = new()130 p.s = src131 p.b = bytes(src)132 p.n = len(src)133 p.i = 0134135 # fail says where it went wrong, working the line and the column out from136 # the offset. It runs once per parse at the most.137 p.fail = fn(msg) {138 line = 1139 col = 1140 b = p.b141142 for k = 0; k < p.i && k < p.n; k++ {143 if b[k] == bLF {144 line++145 col = 1146 } else {147 col++148 }149 }150 return error("xml parse error at {line}:{col} -> {msg}")151 }152153 p.skipSpace = fn() {154 b = p.b155 n = p.n156 i = p.i157158 for i < n && spaceByte[b[i]] { i++ }159 p.i = i160 }161162 # looking reports whether the source at the cursor starts with lit. Used163 # where the shape is rare enough that a slice and a compare are cheaper164 # than spelling the bytes out.165 p.looking = fn(lit) {166 if p.i + len(lit) > p.n {167 return false168 }169 return slice(p.s, p.i, p.i + len(lit)) == lit170 }171172 # skipUntil moves past the next occurrence of a two or three byte marker.173 # An unterminated one is a mistake, not an empty document.174 p.skipUntil = fn(c0, c1, c2, what) {175 b = p.b176 n = p.n177 i = p.i178 last = if c2 < 0 { 2 } else { 3 }179180 for i + last <= n {181 if b[i] == c0 && b[i + 1] == c1 && (c2 < 0 || b[i + 2] == c2) {182 p.i = i + last183 return null184 }185 i++186 }187 p.i = n188 return p.fail("unterminated {what}")189 }190191 # skipDoctype steps over a DOCTYPE, internal subset included. The subset192 # is between brackets and holds '>' of its own, so the depth is counted.193 p.skipDoctype = fn() {194 b = p.b195 n = p.n196 i = p.i197 depth = 0198199 for i < n {200 c = b[i]201 if c == bLBracket {202 depth++203 } else if c == bRBracket {204 depth--205 } else if c == bGT && depth <= 0 {206 p.i = i + 1207 return null208 }209 i++210 }211 p.i = n212 return p.fail("unterminated DOCTYPE")213 }214215 # skipMisc steps over what may sit before and after the root: processing216 # instructions, the declaration, comments and a DOCTYPE.217 p.skipMisc = fn() {218 for {219 p.skipSpace()220 if p.i + 1 >= p.n || p.b[p.i] != bLT {221 return null222 }223224 c = p.b[p.i + 1]225 if c == bQuestion {226 p.i += 2227 if failed(e = p.skipUntil(bQuestion, bGT, -1, "processing instruction")) {228 return e229 }230 } else if c == bBang && p.looking("<!--") {231 p.i += 4232 if failed(e = p.skipUntil(bDash, bDash, bGT, "comment")) {233 return e234 }235 } else if c == bBang && p.looking("<!DOCTYPE") {236 p.i += 9237 if failed(e = p.skipDoctype()) {238 return e239 }240 } else {241 return null242 }243 }244 }245246 p.name = fn() {247 b = p.b248 n = p.n249 i = p.i250 start = i251252 # The table lets through more than a name may hold, which costs253 # nothing: the job here is to find where it ends.254 for i < n && nameByte[b[i]] { i++ }255 if i == start {256 return p.fail("expected a name")257 }258 p.i = i259 return slice(p.s, start, i)260 }261262 # reference reads what follows an '&' and gives back what it stands for.263 p.reference = fn() {264 p.i++265 b = p.b266 n = p.n267 i = p.i268 start = i269270 for i < n && b[i] != bSemi && b[i] > bSpace && b[i] != bLT {271 i++272 }273 if i >= n || b[i] != bSemi {274 p.i = i275 return p.fail("unterminated entity reference")276 }277278 name = slice(p.s, start, i)279 p.i = i + 1280281 if name == "lt" { return "<" }282 if name == "gt" { return ">" }283 if name == "amp" { return "&" }284 if name == "quot" { return "\"" }285 if name == "apos" { return "'" }286287 if b[start] == bHash && i > start + 1 {288 from = start + 1289 base = 10290291 if b[from] == bLowerX || b[from] == bUpperX {292 from++293 base = 16294 }295 if failed(r = digits(p.b, from, i, base)) {296 p.i = start297 return p.fail("bad character reference &{name};")298 }299 return utf8.EncodeRune(r)300 }301 p.i = start302 return p.fail("unknown entity &{name};")303 }304305 # scan runs to the next byte that ends a run of character data, either the306 # stop byte or an '&'. It is the innermost loop of the whole parser.307 p.scan = fn(stop) {308 b = p.b309 n = p.n310 i = p.i311312 for i < n {313 c = b[i]314 if c == stop || c == bAmp {315 break316 }317 i++318 }319 p.i = i320 return i321 }322323 # run reads character data up to stop. A run without references is one324 # slice of the source and costs no copy at all; one with them is joined325 # once at the end.326 p.run = fn(stop) {327 start = p.i328 end = p.scan(stop)329330 if end >= p.n || p.b[end] != bAmp {331 return slice(p.s, start, end)332 }333334 out = buffer.Builder()335 out.Write(slice(p.s, start, end))336337 for p.i < p.n && p.b[p.i] == bAmp {338 if failed(r = p.reference()) {339 return r340 }341 out.Write(r)342343 start = p.i344 end = p.scan(stop)345 out.Write(slice(p.s, start, end))346 }347 return out.String()348 }349350 p.attrValue = fn() {351 if p.i >= p.n {352 return p.fail("an attribute value is quoted")353 }354 quote = p.b[p.i]355 if quote != bQuote && quote != bApos {356 return p.fail("an attribute value is quoted")357 }358 p.i++359360 if failed(v = p.run(quote)) {361 return v362 }363 if p.i >= p.n || p.b[p.i] != quote {364 return p.fail("unterminated attribute value")365 }366 p.i++367 return v368 }369370 # element reads one element, the '<' already under the cursor.371 p.element = fn() {372 p.i++373 if failed(name = p.name()) {374 return name375 }376 node = Node(name)377378 for {379 p.skipSpace()380 if p.i >= p.n {381 return p.fail("unterminated tag <{name}>")382 }383 c = p.b[p.i]384385 if c == bSlash {386 p.i++387 if p.i >= p.n || p.b[p.i] != bGT {388 return p.fail("expected '>' after '/'")389 }390 p.i++391 return node392 }393 if c == bGT {394 p.i++395 return p.content(node)396 }397398 if failed(attr = p.name()) {399 return attr400 }401 p.skipSpace()402 if p.i >= p.n || p.b[p.i] != bEq {403 return p.fail("expected '=' after attribute {attr}")404 }405 p.i++406 p.skipSpace()407408 if failed(val = p.attrValue()) {409 return val410 }411 node.Attr[attr] = val412 }413 }414415 # content reads what lies between a start tag and its end tag.416 p.content = fn(node) {417 text = buffer.Builder()418 children = []419420 for {421 if p.i >= p.n {422 return p.fail("unterminated element <{node.Name}>")423 }424425 if p.b[p.i] != bLT {426 if failed(t = p.run(bLT)) {427 return t428 }429 text.Write(t)430 continue431 }432433 c = if p.i + 1 < p.n { p.b[p.i + 1] } else { -1 }434435 if c == bSlash {436 p.i += 2437 if failed(name = p.name()) {438 return name439 }440 if name != node.Name {441 return p.fail("</{name}> closes <{node.Name}>")442 }443 p.skipSpace()444 if p.i >= p.n || p.b[p.i] != bGT {445 return p.fail("expected '>' after </{name}>")446 }447 p.i++448449 node.Text = text.String()450 node.Children = children451 return node452 }453454 if c == bBang {455 if p.looking("<![CDATA[") {456 p.i += 9457 start = p.i458 if failed(e = p.skipUntil(bRBracket, bRBracket, bGT, "CDATA section")) {459 return e460 }461 text.Write(slice(p.s, start, p.i - 3))462 continue463 }464 if p.looking("<!--") {465 p.i += 4466 if failed(e = p.skipUntil(bDash, bDash, bGT, "comment")) {467 return e468 }469 continue470 }471 return p.fail("expected a comment or a CDATA section")472 }473474 if c == bQuestion {475 p.i += 2476 if failed(e = p.skipUntil(bQuestion, bGT, -1, "processing instruction")) {477 return e478 }479 continue480 }481482 if failed(child = p.element()) {483 return child484 }485 children = append(children, child)486 }487 }488489 p.document = fn() {490 if failed(e = p.skipMisc()) {491 return e492 }493 if p.i >= p.n || p.b[p.i] != bLT {494 return p.fail("expected an element")495 }496 if failed(root = p.element()) {497 return root498 }499500 # What follows the root may only be a comment or an instruction.501 if failed(e = p.skipMisc()) {502 return e503 }504 if p.i < p.n {505 return p.fail("text after the root element")506 }507 return root508 }509510 return p511}512513# digits reads an unsigned number out of the bytes between from and to.514digits = fn(b, from, to, base) {515 if from >= to {516 return error("no digits")517 }518 n = 0519520 for i = from; i < to; i++ {521 c = b[i]522 d = -1523524 if c >= 48 && c <= 57 {525 d = c - 48526 } else if c >= 97 && c <= 102 {527 d = c - 87528 } else if c >= 65 && c <= 70 {529 d = c - 55530 }531 if d < 0 || d >= base {532 return error("not a digit in base {base}")533 }534 n = n * base + d535 }536 return n537}538539# Parse reads a document and gives back its root element.540Parse = fn(src) {541 p = Parser(src)542 return p.document()543}544545# --- looking around a tree546547# Child is the first child element called name, and null when there is none.548Child = fn(node, name) {549 cs = node.Children550 for i = 0; i < len(cs); i++ {551 if cs[i].Name == name {552 return cs[i]553 }554 }555 return null556}557558# All is every child element called name, in the order they were written.559All = fn(node, name) {560 cs = node.Children561 out = []562563 for i = 0; i < len(cs); i++ {564 if cs[i].Name == name {565 out = append(out, cs[i])566 }567 }568 return out569}570571# Get is the value of an attribute, and "" when it is not there. An attribute572# written empty and one that is absent are told apart by node.Attr.573Get = fn(node, name) {574 v = node.Attr[name]575 if v == null {576 return ""577 }578 return v579}580581# --- writing582583# Escape makes a string safe between tags and inside an attribute value. A584# string with nothing to escape comes back as it was, without a copy.585Escape = fn(s) {586 b = bytes(s)587 n = len(s)588 out = null589 start = 0590591 for i = 0; i < n; i++ {592 c = b[i]593 r = ""594595 if c == bLT {596 r = "<"597 } else if c == bGT {598 r = ">"599 } else if c == bAmp {600 r = "&"601 } else if c == bQuote {602 r = """603 } else if c == bApos {604 r = "'"605 } else {606 continue607 }608609 if out == null {610 out = buffer.Builder()611 }612 out.Write(slice(s, start, i))613 out.Write(r)614 start = i + 1615 }616617 if out == null {618 return s619 }620 out.Write(slice(s, start, n))621 return out.String()622}623624# String writes a node back out. Attributes come out in the order keys gives625# them and not the order they were written: XML says an attribute list is a626# set, and this holds one.627String = fn(node) {628 out = buffer.Builder()629 write(out, node)630 return out.String()631}632633write = fn(out, node) {634 out.Write("<")635 out.Write(node.Name)636637 ks = keys(node.Attr)638 for i = 0; i < len(ks); i++ {639 out.Write(" ")640 out.Write(ks[i])641 out.Write("=\"")642 out.Write(Escape(node.Attr[ks[i]]))643 out.Write("\"")644 }645646 if len(node.Children) == 0 && node.Text == "" {647 out.Write("/>")648 return null649 }650 out.Write(">")651 out.Write(Escape(node.Text))652653 cs = node.Children654 for i = 0; i < len(cs); i++ {655 write(out, cs[i])656 }657658 out.Write("</")659 out.Write(node.Name)660 out.Write(">")661}