xml.bend

gralha-xml-doc@0.1.0.1 · 476 lines · 80 definitions

1# XML: tokens, element tree, entities, attributes and serialization.
2import Base
3import gralha-text-scan@0.1.0.1/scan.bend as U
4
5# Reverse a scan's accumulator while decoding XML entities: the reversed
6# text shows an entity as its ';' first, then its name backwards, then '&';
7# a ';' without a short name and '&' behind it is plain text.
8def entity.push(+e: String, +out: String) -> String:
9  match e:
10    case SNil{}: out
11    case SCon{c, t}: SCon{c, entity.push(t, out)}
12
13def entity.of(+name: String) -> String:
14  U.choose(String, U.string.equal(name, "amp"), "&", U.choose(String, U.string.equal(name, "lt"), "<",
15    U.choose(String, U.string.equal(name, "gt"), ">", U.choose(String, U.string.equal(name, "quot"), "\"",
16      U.choose(String, U.string.equal(name, "apos"), "'", U.choose(String, U.prefix(name, "#x"), SCon{Chr{U.hex(U.drop(name, "#x"), 0)}, ""},
17        U.choose(String, U.prefix(name, "#"), SCon{Chr{F32.to_u32(U.scalar(U.drop(name, "#"), 65533.0))}, ""}, "&" ++ name ++ ";")))))))
18
19# One step of the decoding reversal: kind 0 a plain character, 1 an entity
20# (its name collected backwards up to the '&'), 2 a ';' that began no
21# entity (the collected text stays as it was), 3 the end.
22type Step is Data:
23  Step{kind: U32, ch: U32, name: String, rest: String}
24
25@unsafe
26def entity.take(s: String, +name: String, +n: U32) -> Step:
27  match s:
28    case SNil{}: Step{2, 0, name, ""}
29    case SCon{Chr{c}, t}:
30      +ch = c
31      +tail = t
32      U.branch(Step, U32.is_eq(ch, 38), _ => Step{1, 0, name, tail},
33        _ => U.branch(Step, U32.is_lt(n, 12) && (U.digit(ch) || (U32.is_ge(ch, 65) && U32.is_le(ch, 90)) || (U32.is_ge(ch, 97) && U32.is_le(ch, 122)) || U32.is_eq(ch, 35)),
34          _ => entity.take(tail, SCon{Chr{ch}, name}, (n + 1 : U32)), _ => Step{2, 0, name, SCon{Chr{ch}, tail}}))
35
36def rev.next.at(semi: Bool, +ch: U32, t: String) -> Step:
37  match semi:
38    case True{}: entity.take(t, "", 0)
39    case False{}: Step{0, ch, "", t}
40
41def rev.next(s: String) -> Step:
42  match s:
43    case SNil{}: Step{3, 0, "", ""}
44    case SCon{Chr{c}, t}:
45      +ch = c
46      rev.next.at(U32.is_eq(ch, 59), ch, t)
47
48@unsafe
49def rev.decode.go(st: Step, +out: String) -> String:
50  match st:
51    case Step{kind, ch, name, rest}:
52      match kind:
53        case 0: rev.decode.go(rev.next(rest), SCon{Chr{ch}, out})
54        case 1: rev.decode.go(rev.next(rest), entity.push(entity.of(name), out))
55        case 2: rev.decode.go(rev.next(rest), entity.push(name, SCon{Chr{59}, out}))
56        case _: out
57
58def rev.decode(s: String, +out: String) -> String:
59  rev.decode.go(rev.next(s), out)
60
61# Like until, with entities decoded in the reversal.
62@unsafe
63def until.decoded.go(hit: Bool, +c: U32, t: String, +end: U32, acc: String) -> U.Scan:
64  match hit:
65    case True{}: U.Scan{rev.decode(acc, ""), t}
66    case False{}:
67      match t:
68        case SNil{}: U.Scan{rev.decode(SCon{Chr{c}, acc}, ""), ""}
69        case SCon{Chr{c2}, t2}:
70          +cc = c2
71          until.decoded.go(U32.is_eq(cc, end), cc, t2, end, SCon{Chr{c}, acc})
72
73def until.decoded(s: String, +end: U32, acc: String) -> U.Scan:
74  match s:
75    case SNil{}: U.Scan{rev.decode(acc, ""), ""}
76    case SCon{Chr{c}, t}:
77      +cc = c
78      until.decoded.go(U32.is_eq(cc, end), cc, t, end, acc)
79
80def name.stop(+c: U32) -> Bool:
81  U.space(c) || U32.is_eq(c, 61) || U32.is_eq(c, 47) || U32.is_eq(c, 62)
82
83# Each step is decided one character ahead (`stop` says whether `c` ends
84# the name) so the text after the name is held once, never shared.
85@unsafe
86def name.go(stop: Bool, +c: U32, t: String, acc: String) -> U.Scan:
87  match stop:
88    case True{}: U.Scan{U.rev(acc, ""), SCon{Chr{c}, t}}
89    case False{}:
90      match t:
91        case SNil{}: U.Scan{U.rev(SCon{Chr{c}, acc}, ""), ""}
92        case SCon{Chr{c2}, t2}:
93          +cc = c2
94          name.go(name.stop(cc), cc, t2, SCon{Chr{c}, acc})
95
96def xml.name(s: String, acc: String) -> U.Scan:
97  match s:
98    case SNil{}: U.Scan{U.rev(acc, ""), ""}
99    case SCon{Chr{c}, t}:
100      +cc = c
101      name.go(name.stop(cc), cc, t, acc)
102
103def value.go(quoted: Bool, +ch: U32, rest: String) -> U.Scan:
104  match quoted:
105    case True{}: until.decoded(rest, ch, "")
106    case False{}: xml.name(SCon{Chr{ch}, rest}, "")
107
108def value(s: String) -> U.Scan:
109  match s:
110    case SNil{}: U.Scan{"", ""}
111    case SCon{Chr{c}, t}:
112      +ch = c
113      value.go(U32.is_eq(ch, 34) || U32.is_eq(ch, 39), ch, t)
114
115def equals(s: String) -> U.Scan:
116  match s:
117    case SNil{}: U.Scan{"", ""}
118    case SCon{Chr{c}, t}:
119      U.branch(U.Scan, U32.is_eq(c, 61), _ => value(U.trim(t)), _ => U.Scan{"", ""})
120
121type Attr is Data:
122  Attr{key: String, val: String}
123
124type Tag is Data:
125  Tag{attrs: List<&2, Attr>, tail: String, closed: Bool}
126
127# The parse position after an attribute: the kind of the next character
128# (see attr.kind; 4 at the end of the text) with the attributes so far.
129# What a character starts inside a tag: 0 space, 1 the end of the tag,
130# 2 a self-closing slash, 3 an attribute.
131def attr.kind(+c: U32) -> U32:
132  U.choose(U32, U.space(c), 0, U.choose(U32, U32.is_eq(c, 62), 1, U.choose(U32, U32.is_eq(c, 47), 2, 3)))
133
134type Next is Data:
135  Next{kind: U32, ch: U32, attrs: List<&2, Attr>, tail: String}
136
137def next.of(attrs: List<&2, Attr>, tail: String) -> Next:
138  match tail:
139    case SNil{}: Next{4, 0, attrs, ""}
140    case SCon{Chr{c}, t}:
141      +cc = c
142      Next{attr.kind(cc), cc, attrs, t}
143
144def attr.append(k: String, b: U.Scan, attrs: List<&2, Attr>) -> Next:
145  U.Scan{v, t} = b
146  next.of(Con{Attr{k, v}, attrs}, t)
147
148def attr.read.scan(a: U.Scan, attrs: List<&2, Attr>) -> Next:
149  U.Scan{k, t} = a
150  attr.append(k, equals(U.trim(t)), attrs)
151
152def attr.read(s: String, attrs: List<&2, Attr>) -> Next:
153  attr.read.scan(xml.name(s, ""), attrs)
154
155def attributes.close(scan: U.Scan, attrs: List<&2, Attr>) -> Tag:
156  U.Scan{h, t} = scan
157  Tag{attrs, t, True{}}
158
159@unsafe
160def attributes.go(step: Next) -> Tag:
161  match step:
162    case Next{kind, ch, as, tail}:
163      match kind:
164        case 0: attributes.go(next.of(as, tail))
165        case 1: Tag{as, tail, False{}}
166        case 2: attributes.close(U.until(tail, 62, ""), as)
167        case 3: attributes.go(attr.read(SCon{Chr{ch}, tail}, as))
168        case _: Tag{as, "", False{}}
169
170def attributes(s: String, attrs: List<&2, Attr>) -> Tag:
171  attributes.go(next.of(attrs, s))
172
173type Token is Data:
174  Open{name: String, attrs: List<&2, Attr>, closed: Bool}
175  Shut{name: String}
176  Chars{content: String}
177
178type Lexeme is Data:
179  Lexeme{token: Token, tail: String}
180
181def lex.open(n: String, tag: Tag) -> Lexeme:
182  Tag{attrs, tail, closed} = tag
183  Lexeme{Open{n, attrs, closed}, tail}
184
185def lex.named(scan: U.Scan) -> Lexeme:
186  U.Scan{n, t} = scan
187  lex.open(n, attributes(t, Nil{}))
188
189def lex.shut(scan: U.Scan) -> Lexeme:
190  U.Scan{n, t} = scan
191  Lexeme{Shut{n}, t}
192
193def xml.raw(s: String) -> String:
194  match s:
195    case SNil{}: ""
196    case SCon{Chr{c}, t}:
197      +ch = c
198      U.choose(String, U32.is_eq(ch, 38), "&amp;", SCon{Chr{ch}, ""}) ++ xml.raw(t)
199
200def lex.cdata(scan: U.Scan) -> Lexeme:
201  U.Scan{h, t} = scan
202  Lexeme{Chars{xml.raw(h)}, t}
203
204def lex.tag(+s: String) -> Lexeme:
205  U.branch(Lexeme, U.prefix(s, "![CDATA["), _ => lex.cdata(U.until.sequence(U.drop(s, "![CDATA["), "]]>", "")),
206    _ => U.branch(Lexeme, U.prefix(s, "!--"), _ => Lexeme{Chars{""}, U.through(s, "-->")},
207    _ => U.branch(Lexeme, U.prefix(s, "?"), _ => Lexeme{Chars{""}, U.through(s, "?>")},
208      _ => U.branch(Lexeme, U.prefix(s, "!"), _ => Lexeme{Chars{""}, U.through(s, ">")},
209        _ => U.branch(Lexeme, U.prefix(s, "/"), _ => lex.shut(U.until(U.drop(s, "/"), 62, "")),
210          _ => lex.named(xml.name(s, "")))))))
211
212def lex.more(item: Lexeme, next: String -> List<&2, Token>) -> List<&2, Token>:
213  Lexeme{tok, t} = item
214  Con{tok, next(t)}
215
216def lex.after(s: String, next: String -> List<&2, Token>) -> List<&2, Token>:
217  match s:
218    case SNil{}: Nil{}
219    case SCon{c, t}: lex.more(lex.tag(SCon{c, t}), next)
220
221def lex.text(scan: U.Scan, next: String -> List<&2, Token>) -> List<&2, Token>:
222  U.Scan{h, t} = scan
223  Con{Chars{h}, lex.after(t, next)}
224
225@unsafe
226def tokenize(s: String) -> List<&2, Token>:
227  match s:
228    case SNil{}: Nil{}
229    case SCon{c, t}:
230      lex.text(U.until(SCon{c, t}, 60, ""), next => tokenize(next))
231
232type Element is Data:
233  Element{name: String, attrs: List<&2, Attr>, children: List<&2, Element>, text: String}
234
235def elements.rev(xs: List<&2, Element>, acc: List<&2, Element>) -> List<&2, Element>:
236  match xs:
237    case Nil{}: acc
238    case Con{h, t}: elements.rev(t, Con{h, acc})
239
240def element.finish(e: Element) -> Element:
241  Element{n, a, kids, txt} = e
242  Element{n, a, elements.rev(kids, Nil{}), txt}
243
244def stack.add(s: List<&2, Element>, node: Element) -> List<&2, Element>:
245  match s:
246    case Nil{}: Con{Element{"#document", Nil{}, Con{node, Nil{}}, ""}, Nil{}}
247    case Con{Element{n, a, kids, txt}, rest}:
248      Con{Element{n, a, Con{node, kids}, txt}, rest}
249
250def stack.text(+s: List<&2, Element>, +text: String) -> List<&2, Element>:
251  U.branch(List<&2, Element>, U.string.equal(text, ""), _ => s,
252    _ => stack.add(s, Element{"#text", Nil{}, Nil{}, text}))
253
254def stack.close(s: List<&2, Element>) -> List<&2, Element>:
255  match s:
256    case Nil{}: Nil{}
257    case Con{node, rest}: stack.add(rest, element.finish(node))
258
259def tree.step(tok: Token, +s: List<&2, Element>) -> List<&2, Element>:
260  match tok:
261    case Chars{txt}: stack.text(s, txt)
262    case Shut{n}: stack.close(s)
263    case Open{n, a, closed}:
264      +node = {Element{n, a, Nil{}, ""} : Element}
265      U.choose(List<&2, Element>, closed, stack.add(s, node), Con{node, s})
266
267def tree(tokens: List<&2, Token>, s: List<&2, Element>) -> List<&2, Element>:
268  match tokens:
269    case Nil{}: s
270    case Con{tok, rest}: tree(rest, tree.step(tok, s))
271
272def tree.root(s: List<&2, Element>) -> Element:
273  match s:
274    case Nil{}: Element{"#document", Nil{}, Nil{}, ""}
275    case Con{node, rest}: element.finish(node)
276
277def annotate(xs: List<&2, Token>, +i: U32) -> List<&2, Token>:
278  match xs:
279    case Nil{}: Nil{}
280    case Con{Open{n, as, closed}, rest}:
281      Con{Open{n, Con{Attr{"#editor-id", U32.show(i)}, as}, closed}, annotate(rest, U32.inc(i))}
282    case Con{tok, rest}: Con{tok, annotate(rest, i)}
283
284def attr.pick(hit: Bool, +v: String, rest: Maybe<&2, String>) -> Maybe<&2, String>:
285  match hit:
286    case True{}: Some{v}
287    case False{}: rest
288
289# The attribute's value when present. Attribute lists are short, so the whole
290# list is walked without a lambda per entry.
291# The first attribute with the key, decided one entry ahead so the walk
292# stops at the hit instead of comparing every key.
293@unsafe
294def attr.find.go(hit: Bool, v: String, t: List<&2, Attr>, +key: String) -> Maybe<&2, String>:
295  match hit:
296    case True{}: Some{v}
297    case False{}:
298      match t:
299        case Nil{}: None{}
300        case Con{Attr{k2, v2}, t2}: attr.find.go(U.string.equal(k2, key), v2, t2, key)
301
302def attr.find(attrs: List<&2, Attr>, +key: String) -> Maybe<&2, String>:
303  match attrs:
304    case Nil{}: None{}
305    case Con{Attr{k, v}, t}: attr.find.go(U.string.equal(k, key), v, t, key)
306
307def attr.or(found: Maybe<&2, String>, +fallback: String) -> String:
308  match found:
309    case None{}: fallback
310    case Some{v}: v
311
312def attr.get(attrs: List<&2, Attr>, +key: String, +fallback: String) -> String:
313  attr.or(attr.find(attrs, key), fallback)
314
315def attrs.append(xs: List<&2, Attr>, ys: List<&2, Attr>) -> List<&2, Attr>:
316  match xs:
317    case Nil{}: ys
318    case Con{h, t}: Con{h, attrs.append(t, ys)}
319
320def element.prefer(a: Maybe<&2, Element>, b: Maybe<&2, Element>) -> Maybe<&2, Element>:
321  match a:
322    case Some{e}: Some{e}
323    case None{}: b
324
325def element.find(+xs: List<&2, Element>, +id: String) -> Maybe<&2, Element>:
326  match xs:
327    case Nil{}: None{}
328    case Con{Element{n, as, kids, txt}, rest}:
329      U.branch(Maybe<&2, Element>, U.string.equal(attr.get(as, "id", ""), id),
330        _ => Some{Element{n, as, kids, txt}},
331        _ => element.prefer(U.branch(Maybe<&2, Element>, U.string.equal(n, "#svg-image"), _ => None{}, _ => element.find(kids, id)), element.find(rest, id)))
332
333# Decode XML entities before interpreting attributes or exposing source editing.
334def entity(+s: String) -> String:
335  U.branch(String, U.string.equal(s, "amp"), _ => "&",
336    _ => U.branch(String, U.string.equal(s, "lt"), _ => "<",
337      _ => U.branch(String, U.string.equal(s, "gt"), _ => ">",
338        _ => U.branch(String, U.string.equal(s, "quot"), _ => "\"",
339          _ => U.branch(String, U.string.equal(s, "apos"), _ => "'",
340            _ => U.branch(String, U.prefix(s, "#x"), _ => SCon{Chr{U.hex(U.drop(s, "#x"), 0)}, ""},
341              _ => U.branch(String, U.prefix(s, "#"), _ => SCon{Chr{F32.to_u32(U.scalar(U.drop(s, "#"), 65533.0))}, ""},
342                _ => "&" ++ s ++ ";")))))))
343
344def entities.more(scan: U.Scan, acc: String, next: String -> String -> String) -> String:
345  U.Scan{h, t} = scan
346  next(t)(U.rev(entity(h), acc))
347
348@unsafe
349def entities.loop(s: String, +acc: String) -> String:
350  match s:
351    case SNil{}: U.rev(acc, "")
352    case SCon{Chr{c}, t}:
353      +ch = c
354      +tail = t
355      U.branch(String, U32.is_eq(ch, 38),
356        _ => entities.more(U.until(tail, 59, ""), acc, rest => text => entities.loop(rest, text)),
357        _ => entities.loop(tail, SCon{Chr{ch}, acc}))
358
359def entities(s: String) -> String:
360  entities.loop(s, "")
361
362def decode.attrs(as: List<&2, Attr>) -> List<&2, Attr>:
363  match as:
364    case Nil{}: Nil{}
365    case Con{Attr{k, v}, rest}: Con{Attr{k, entities(v)}, decode.attrs(rest)}
366
367# Attribute values were decoded as they were read; text still is here.
368def decode.nodes(xs: List<&2, Element>) -> List<&2, Element>:
369  match xs:
370    case Nil{}: Nil{}
371    case Con{Element{n, as, kids, txt}, rest}:
372      Con{Element{n, as, decode.nodes(kids), entities(txt)}, decode.nodes(rest)}
373
374def parse(s: String) -> Element:
375  tree.root(decode.nodes(tree(annotate(tokenize(s), 1), Con{Element{"#document", Nil{}, Nil{}, ""}, Nil{}})))
376
377# Editor support: identifiers are private metadata and never serialized.
378def attrs.remove(+as: List<&2, Attr>, +key: String) -> List<&2, Attr>:
379  match as:
380    case Nil{}: Nil{}
381    case Con{Attr{k, v}, rest}:
382      +kk = k
383      U.branch(List<&2, Attr>, U.string.equal(kk, key), _ => attrs.remove(rest, key),
384        _ => Con{Attr{kk, v}, attrs.remove(rest, key)})
385
386def attrs.set(as: List<&2, Attr>, +key: String, value: String) -> List<&2, Attr>:
387  Con{Attr{key, value}, attrs.remove(as, key)}
388
389# One attribute's value taken out of the list, so its text has a single
390# owner; "" and the untouched list when absent.
391type Taken is Data:
392  Taken{value: String, rest: List<&2, Attr>}
393
394def taken.push(t: Taken, a: Attr) -> Taken:
395  Taken{v, rest} = t
396  Taken{v, Con{a, rest}}
397
398@unsafe
399def attrs.take.go(hit: Bool, kk: String, v: String, rest: List<&2, Attr>, +key: String) -> Taken:
400  match hit:
401    case True{}: Taken{v, rest}
402    case False{}:
403      match rest:
404        case Nil{}: Taken{"", Con{Attr{kk, v}, Nil{}}}
405        case Con{Attr{k2, v2}, r2}:
406          +kk2 = k2
407          taken.push(attrs.take.go(U.string.equal(kk2, key), kk2, v2, r2, key), Attr{kk, v})
408
409def attrs.take(as: List<&2, Attr>, +key: String) -> Taken:
410  match as:
411    case Nil{}: Taken{"", Nil{}}
412    case Con{Attr{k, v}, rest}:
413      +kk = k
414      attrs.take.go(U.string.equal(kk, key), kk, v, rest, key)
415
416# Build escaped XML in reverse, so large data URIs do not grow the host stack.
417def escape.rev(s: String, acc: String) -> String:
418  match s:
419    case SNil{}: acc
420    case SCon{Chr{c}, t}:
421      +ch = c
422      escape.rev(t, U.rev(U.choose(String, U32.is_eq(ch, 38), "&amp;",
423        U.choose(String, U32.is_eq(ch, 60), "&lt;",
424          U.choose(String, U32.is_eq(ch, 62), "&gt;",
425            U.choose(String, U32.is_eq(ch, 34), "&quot;", SCon{Chr{ch}, ""})))), acc))
426
427def escape(s: String) -> String:
428  U.rev(escape.rev(s, ""), "")
429
430def serialize.attrs.rev(as: List<&2, Attr>, +acc: String) -> String:
431  match as:
432    case Nil{}: acc
433    case Con{Attr{k, v}, rest}:
434      +key = k
435      serialize.attrs.rev(rest, U.branch(String, U.prefix(key, "#"), _ => acc,
436        _ => SCon{Chr{34}, escape.rev(v, SCon{Chr{34}, SCon{Chr{61}, U.rev(key, SCon{Chr{32}, acc})}})}))
437
438def serialize.attrs(as: List<&2, Attr>) -> String:
439  U.rev(serialize.attrs.rev(as, ""), "")
440
441def serialize.element(+n: String, as: List<&2, Attr>, kids: List<&2, Element>, txt: String, +acc: String,
442  children: List<&2, Element> -> String -> String) -> String:
443  +isDocument = U.string.equal(n, "#document")
444  +isText = U.string.equal(n, "#text")
445  +open = U.branch(String, isDocument || isText, _ => acc,
446    _ => SCon{Chr{62}, serialize.attrs.rev(as, U.rev(n, SCon{Chr{60}, acc}))})
447  +body = children(U.choose(List<&2, Element>, isText, Nil{}, kids))(U.choose(String, isDocument, open, escape.rev(txt, open)))
448  U.branch(String, isDocument || isText, _ => body, _ => SCon{Chr{62}, U.rev(n, SCon{Chr{47}, SCon{Chr{60}, body}})})
449
450@unsafe
451def serialize.nodes.rev(xs: List<&2, Element>, acc: String) -> String:
452  match xs:
453    case Nil{}: acc
454    case Con{Element{n, as, kids, txt}, rest}:
455      serialize.nodes.rev(rest, serialize.element(n, as, kids, txt, acc, nodes => tail => serialize.nodes.rev(nodes, tail)))
456
457def serialize.nodes(xs: List<&2, Element>) -> String:
458  U.rev(serialize.nodes.rev(xs, ""), "")
459
460def serialize(root: Element) -> String:
461  serialize.nodes(Con{root, Nil{}})
462
463# The number of elements in a forest, the roots included.
464# Which of four element names the tree holds, as bits: 1 image, 2 use, 4 text, 8 style.
465def elements.kinds(xs: List<&2, Element>, +acc: U32) -> U32:
466  match xs:
467    case Nil{}: acc
468    case Con{Element{name, attrs, kids, text}, rest}:
469      +n = name
470      elements.kinds(rest, elements.kinds(kids, U32.or(acc, U.choose(U32, U.string.equal(n, "image"), 1,
471        U.choose(U32, U.string.equal(n, "use"), 2, U.choose(U32, U.string.equal(n, "text"), 4, U.choose(U32, U.string.equal(n, "style"), 8, 0)))))))
472
473def elements.count(xs: List<&2, Element>) -> U32:
474  match xs:
475    case Nil{}: 0
476    case Con{Element{name, attrs, kids, text}, rest}: (1 + elements.count(kids) + elements.count(rest) : U32)