blue_lang_runtime/
xml.rs

1use std::sync::Arc;
2
3use quick_xml::escape::resolve_predefined_entity;
4use quick_xml::events::{BytesStart, Event};
5use quick_xml::Reader;
6use tatara_lisp_eval::ffi::Arity;
7use tatara_lisp_eval::{EvalError, Interpreter, MapKey, Value};
8
9use crate::errors::raise_kind;
10
11pub const MALFORMED: &str = "xml_malformed";
12pub const REFUSED: &str = "xml_refused";
13pub const MAX_DEPTH: usize = 1024;
14
15pub fn install_xml_stdlib<H: 'static>(interp: &mut Interpreter<H>) {
16    interp.register_fn(
17        "xml_parse",
18        Arity::Exact(1),
19        |args: &[Value], _h: &mut H, span| match &args[0] {
20            Value::Str(s) => parse(s).map_err(|f| f.raise(span)),
21            other => Err(EvalError::native_fn(
22                "xml_parse",
23                format!("expected a string of XML text, got {}", other.type_name()),
24                span,
25            )),
26        },
27    );
28    interp.register_fn(
29        "xml_render",
30        Arity::Exact(1),
31        |args: &[Value], _h: &mut H, span| {
32            render(&args[0])
33                .map(|s| Value::Str(Arc::from(s)))
34                .map_err(|f| f.raise(span))
35        },
36    );
37}
38
39#[derive(Debug, Clone, PartialEq, Eq)]
40pub enum Fault {
41    Malformed(String),
42    Refused(String),
43}
44
45impl Fault {
46    fn raise(self, span: tatara_lisp::Span) -> EvalError {
47        match self {
48            Fault::Malformed(m) => raise_kind(MALFORMED, m, span),
49            Fault::Refused(m) => raise_kind(REFUSED, m, span),
50        }
51    }
52}
53
54struct Open {
55    name: String,
56    attributes: Vec<(String, String)>,
57    children: Vec<Value>,
58    texts: Vec<String>,
59}
60
61impl Open {
62    fn close(self) -> Value {
63        let text = if self.children.is_empty() {
64            self.texts.concat()
65        } else {
66            self.texts
67                .into_iter()
68                .filter(|t| !t.chars().all(char::is_whitespace))
69                .collect::<String>()
70        };
71        element(self.name, self.attributes, self.children, text)
72    }
73}
74
75fn key(name: &str) -> MapKey {
76    MapKey::Keyword(Arc::from(name))
77}
78
79fn element(
80    name: String,
81    attributes: Vec<(String, String)>,
82    children: Vec<Value>,
83    text: String,
84) -> Value {
85    Value::map([
86        (key("name"), Value::Str(Arc::from(name))),
87        (
88            key("attributes"),
89            Value::map(
90                attributes
91                    .into_iter()
92                    .map(|(k, v)| (MapKey::Str(Arc::from(k)), Value::Str(Arc::from(v)))),
93            ),
94        ),
95        (key("children"), Value::list(children)),
96        (key("text"), Value::Str(Arc::from(text))),
97    ])
98}
99
100fn position(src: &str, byte: u64) -> String {
101    let end = usize::try_from(byte).unwrap_or(src.len()).min(src.len());
102    let before = src.get(..end).unwrap_or(src);
103    let line = before.matches('\n').count() + 1;
104    let col = before.rsplit('\n').next().map_or(0, |l| l.chars().count()) + 1;
105    format!("line {line}, column {col}")
106}
107
108fn entity_refused(name: &str) -> Fault {
109    Fault::Refused(format!(
110        "entity &{name}; is not expanded: blue reads only the five predefined entities and character references, never a DTD entity"
111    ))
112}
113
114fn resolve_ref(name: &str) -> Result<String, Fault> {
115    if let Some(num) = name.strip_prefix('#') {
116        let code = match num.strip_prefix('x') {
117            Some(hex) => u32::from_str_radix(hex, 16).ok(),
118            None => num.parse::<u32>().ok(),
119        };
120        return code
121            .and_then(char::from_u32)
122            .filter(|c| legal_char(*c))
123            .map(String::from)
124            .ok_or_else(|| {
125                Fault::Malformed(format!("&{name}; is not a legal character reference"))
126            });
127    }
128    resolve_predefined_entity(name)
129        .map(str::to_owned)
130        .ok_or_else(|| entity_refused(name))
131}
132
133fn legal_char(c: char) -> bool {
134    matches!(c, '\t' | '\n' | '\r') || (c >= ' ' && c != '\u{FFFE}' && c != '\u{FFFF}')
135}
136
137fn open(start: &BytesStart<'_>, src: &str, at: u64) -> Result<Open, Fault> {
138    let name = std::str::from_utf8(start.name().as_ref())
139        .map_err(|e| Fault::Malformed(e.to_string()))?
140        .to_owned();
141    let mut attributes: Vec<(String, String)> = Vec::new();
142    for attr in start.attributes() {
143        let attr = attr.map_err(|e| Fault::Malformed(format!("{e} at {}", position(src, at))))?;
144        let k = std::str::from_utf8(attr.key.as_ref())
145            .map_err(|e| Fault::Malformed(e.to_string()))?
146            .to_owned();
147        let mut unknown: Option<String> = None;
148        let v = attr
149            .unescape_value_with(|ent| {
150                let hit = resolve_predefined_entity(ent);
151                if hit.is_none() {
152                    unknown = Some(ent.to_owned());
153                }
154                hit
155            })
156            .map_err(|e| match unknown.take() {
157                Some(ent) => entity_refused(&ent),
158                None => Fault::Malformed(format!("{e} at {}", position(src, at))),
159            })?
160            .into_owned();
161        attributes.push((k, v));
162    }
163    Ok(Open {
164        name,
165        attributes,
166        children: Vec::new(),
167        texts: Vec::new(),
168    })
169}
170
171fn doctype_declares_entity(body: &str) -> bool {
172    body.contains("<!ENTITY")
173}
174
175pub fn parse(src: &str) -> Result<Value, Fault> {
176    let mut reader = Reader::from_str(src);
177    reader.config_mut().check_end_names = true;
178    reader.config_mut().expand_empty_elements = false;
179    reader.config_mut().check_comments = true;
180    let mut stack: Vec<Open> = Vec::new();
181    let mut root: Option<Value> = None;
182    loop {
183        let at = reader.buffer_position();
184        let event = reader.read_event().map_err(|e| {
185            Fault::Malformed(format!("{e} at {}", position(src, reader.error_position())))
186        })?;
187        match event {
188            Event::Start(start) => {
189                if root.is_some() && stack.is_empty() {
190                    return Err(Fault::Malformed(format!(
191                        "a second root element at {}",
192                        position(src, at)
193                    )));
194                }
195                if stack.len() >= MAX_DEPTH {
196                    return Err(Fault::Refused(format!(
197                        "elements nest deeper than {MAX_DEPTH} at {}",
198                        position(src, at)
199                    )));
200                }
201                stack.push(open(&start, src, at)?);
202            }
203            Event::Empty(start) => {
204                if root.is_some() && stack.is_empty() {
205                    return Err(Fault::Malformed(format!(
206                        "a second root element at {}",
207                        position(src, at)
208                    )));
209                }
210                let done = open(&start, src, at)?.close();
211                match stack.last_mut() {
212                    Some(parent) => parent.children.push(done),
213                    None => root = Some(done),
214                }
215            }
216            Event::End(_) => {
217                let done = stack
218                    .pop()
219                    .ok_or_else(|| {
220                        Fault::Malformed(format!(
221                            "an end tag with no start at {}",
222                            position(src, at)
223                        ))
224                    })?
225                    .close();
226                match stack.last_mut() {
227                    Some(parent) => parent.children.push(done),
228                    None => root = Some(done),
229                }
230            }
231            Event::Text(t) => {
232                let text = t
233                    .decode()
234                    .map_err(|e| Fault::Malformed(e.to_string()))?
235                    .into_owned();
236                match stack.last_mut() {
237                    Some(el) => el.texts.push(text),
238                    None if text.chars().all(char::is_whitespace) => {}
239                    None => {
240                        return Err(Fault::Malformed(format!(
241                            "text outside the root element at {}",
242                            position(src, at)
243                        )))
244                    }
245                }
246            }
247            Event::CData(c) => {
248                let text = c
249                    .decode()
250                    .map_err(|e| Fault::Malformed(e.to_string()))?
251                    .into_owned();
252                match stack.last_mut() {
253                    Some(el) => el.texts.push(text),
254                    None => {
255                        return Err(Fault::Malformed(format!(
256                            "CDATA outside the root element at {}",
257                            position(src, at)
258                        )))
259                    }
260                }
261            }
262            Event::GeneralRef(r) => {
263                let name = r.decode().map_err(|e| Fault::Malformed(e.to_string()))?;
264                let text = resolve_ref(&name)?;
265                match stack.last_mut() {
266                    Some(el) => el.texts.push(text),
267                    None => {
268                        return Err(Fault::Malformed(format!(
269                            "a reference outside the root element at {}",
270                            position(src, at)
271                        )))
272                    }
273                }
274            }
275            Event::DocType(d) => {
276                let body = d.decode().map_err(|e| Fault::Malformed(e.to_string()))?;
277                if root.is_some() || !stack.is_empty() {
278                    return Err(Fault::Malformed(format!(
279                        "a DOCTYPE after the root element began at {}",
280                        position(src, at)
281                    )));
282                }
283                if doctype_declares_entity(&body) {
284                    return Err(Fault::Refused(
285                        "the DOCTYPE declares an entity: blue never expands or fetches DTD entities"
286                            .to_owned(),
287                    ));
288                }
289            }
290            Event::Comment(_) | Event::Decl(_) | Event::PI(_) => {}
291            Event::Eof => break,
292        }
293    }
294    if let Some(unclosed) = stack.last() {
295        return Err(Fault::Malformed(format!(
296            "<{}> is never closed",
297            unclosed.name
298        )));
299    }
300    root.ok_or_else(|| Fault::Malformed("the document has no root element".to_owned()))
301}
302
303fn field<'a>(el: &'a Value, name: &str) -> Option<&'a Value> {
304    match el {
305        Value::Map(m) => m
306            .iter()
307            .find(|(k, _)| matches!(k, MapKey::Keyword(s) | MapKey::Str(s) if &**s == name))
308            .map(|(_, v)| v),
309        _ => None,
310    }
311}
312
313fn scalar(v: &Value) -> Option<String> {
314    match v {
315        Value::Str(s) | Value::Symbol(s) | Value::Keyword(s) => Some(s.to_string()),
316        Value::Int(n) => Some(n.to_string()),
317        Value::Float(n) => Some(n.to_string()),
318        Value::Bool(b) => Some(b.to_string()),
319        _ => None,
320    }
321}
322
323fn map_key_text(k: &MapKey) -> Option<String> {
324    match k {
325        MapKey::Str(s) | MapKey::Symbol(s) | MapKey::Keyword(s) => Some(s.to_string()),
326        _ => None,
327    }
328}
329
330fn name_char(c: char, first: bool) -> bool {
331    c == '_'
332        || c == ':'
333        || c.is_alphabetic()
334        || (!first && (c == '-' || c == '.' || c.is_numeric()))
335        || (!c.is_ascii() && !c.is_whitespace() && !c.is_control())
336}
337
338fn checked_name(name: &str, what: &str) -> Result<(), Fault> {
339    let mut chars = name.chars();
340    let ok = chars.next().is_some_and(|c| name_char(c, true)) && chars.all(|c| name_char(c, false));
341    if ok {
342        Ok(())
343    } else {
344        Err(Fault::Refused(format!(
345            "{what} {name:?} is not an XML name"
346        )))
347    }
348}
349
350fn escape_into(out: &mut String, text: &str, in_attribute: bool) -> Result<(), Fault> {
351    for c in text.chars() {
352        match c {
353            '&' => out.push_str("&amp;"),
354            '<' => out.push_str("&lt;"),
355            '>' => out.push_str("&gt;"),
356            '"' if in_attribute => out.push_str("&quot;"),
357            '\t' if in_attribute => out.push_str("&#9;"),
358            '\n' if in_attribute => out.push_str("&#10;"),
359            '\r' => out.push_str("&#13;"),
360            c if legal_char(c) => out.push(c),
361            c => {
362                return Err(Fault::Refused(format!(
363                    "U+{:04X} cannot appear in an XML 1.0 document",
364                    u32::from(c)
365                )))
366            }
367        }
368    }
369    Ok(())
370}
371
372fn render_into(out: &mut String, el: &Value, depth: usize) -> Result<(), Fault> {
373    if depth >= MAX_DEPTH {
374        return Err(Fault::Refused(format!(
375            "elements nest deeper than {MAX_DEPTH}"
376        )));
377    }
378    let name = field(el, "name").and_then(scalar).ok_or_else(|| {
379        Fault::Refused(format!(
380            "an element is a map with a name; got {}",
381            el.type_name()
382        ))
383    })?;
384    checked_name(&name, "element name")?;
385    out.push('<');
386    out.push_str(&name);
387    match field(el, "attributes") {
388        None | Some(Value::Nil) => {}
389        Some(Value::Map(attrs)) => {
390            let mut pairs: Vec<(String, &Value)> = Vec::new();
391            for (k, v) in attrs.iter() {
392                let k = map_key_text(k)
393                    .ok_or_else(|| Fault::Refused("an attribute name is text".to_owned()))?;
394                pairs.push((k, v));
395            }
396            pairs.sort_by(|a, b| a.0.cmp(&b.0));
397            for (k, v) in pairs {
398                checked_name(&k, "attribute name")?;
399                let v = scalar(v).ok_or_else(|| {
400                    Fault::Refused(format!("attribute {k} is not text: {}", v.type_name()))
401                })?;
402                out.push(' ');
403                out.push_str(&k);
404                out.push_str("=\"");
405                escape_into(out, &v, true)?;
406                out.push('"');
407            }
408        }
409        Some(other) => {
410            return Err(Fault::Refused(format!(
411                "attributes is a map; got {}",
412                other.type_name()
413            )))
414        }
415    }
416    let text = match field(el, "text") {
417        None | Some(Value::Nil) => String::new(),
418        Some(v) => scalar(v)
419            .ok_or_else(|| Fault::Refused(format!("text is text; got {}", v.type_name())))?,
420    };
421    let children: Vec<Value> = match field(el, "children") {
422        None | Some(Value::Nil) => Vec::new(),
423        Some(Value::List(xs)) => xs.iter().cloned().collect(),
424        Some(other) => {
425            return Err(Fault::Refused(format!(
426                "children is a list; got {}",
427                other.type_name()
428            )))
429        }
430    };
431    if text.is_empty() && children.is_empty() {
432        out.push_str("/>");
433        return Ok(());
434    }
435    out.push('>');
436    escape_into(out, &text, false)?;
437    for child in &children {
438        render_into(out, child, depth + 1)?;
439    }
440    out.push_str("</");
441    out.push_str(&name);
442    out.push('>');
443    Ok(())
444}
445
446pub fn render(el: &Value) -> Result<String, Fault> {
447    let mut out = String::new();
448    render_into(&mut out, el, 0)?;
449    Ok(out)
450}
451
452#[cfg(test)]
453mod tests {
454    use super::*;
455
456    fn get<'a>(el: &'a Value, k: &str) -> &'a Value {
457        field(el, k).unwrap_or_else(|| panic!("no {k} in {el:?}"))
458    }
459
460    fn text(el: &Value) -> String {
461        scalar(get(el, "text")).unwrap_or_default()
462    }
463
464    fn kids(el: &Value) -> Vec<Value> {
465        match get(el, "children") {
466            Value::List(xs) => xs.iter().cloned().collect(),
467            other => panic!("children {other:?}"),
468        }
469    }
470
471    #[test]
472    fn an_empty_document_is_malformed_not_nil() {
473        assert!(matches!(parse(""), Err(Fault::Malformed(_))));
474        assert!(matches!(parse("   \n"), Err(Fault::Malformed(_))));
475    }
476
477    #[test]
478    fn a_parsed_document_renders_and_parses_back_to_itself() {
479        let src = "<?xml version=\"1.0\"?><!DOCTYPE r><r a=\"1 &amp; &lt;2&gt; &quot;q&quot;\" ns:b=\"x&#10;y\"><c>t &amp; u</c><c/><![CDATA[<raw>&]]></r>";
480        let once = render(&parse(src).expect("parses")).expect("renders");
481        let again = render(&parse(&once).expect("reparses")).expect("renders again");
482        assert_eq!(once, again);
483        assert_eq!(
484            once,
485            "<r a=\"1 &amp; &lt;2&gt; &quot;q&quot;\" ns:b=\"x&#10;y\">&lt;raw&gt;&amp;<c>t &amp; u</c><c/></r>"
486        );
487    }
488
489    #[test]
490    fn values_are_unescaped_and_prefixes_kept() {
491        let el = parse("<x:r xmlns:x=\"urn:example\" a=\"&lt;&#65;&#x42;\">1 &gt; 0</x:r>")
492            .expect("parses");
493        assert_eq!(scalar(get(&el, "name")).as_deref(), Some("x:r"));
494        let Value::Map(attrs) = get(&el, "attributes") else {
495            panic!()
496        };
497        assert_eq!(
498            attrs
499                .get(&MapKey::Str(Arc::from("a")))
500                .and_then(scalar)
501                .as_deref(),
502            Some("<AB")
503        );
504        assert_eq!(
505            attrs
506                .get(&MapKey::Str(Arc::from("xmlns:x")))
507                .and_then(scalar)
508                .as_deref(),
509            Some("urn:example")
510        );
511        assert_eq!(text(&el), "1 > 0");
512    }
513
514    #[test]
515    fn whitespace_between_elements_is_not_text() {
516        let el = parse("<a>\n  <b> x </b>\n  <c/>\n</a>").expect("parses");
517        assert_eq!(text(&el), "");
518        assert_eq!(kids(&el).len(), 2);
519        assert_eq!(text(&kids(&el)[0]), " x ");
520    }
521
522    #[test]
523    fn malformed_documents_are_refused_by_kind() {
524        for bad in [
525            "<a>",
526            "<a></b>",
527            "<a><b></a></b>",
528            "</a>",
529            "<a/><b/>",
530            "text<a/>",
531            "<a x=1/>",
532            "<a x=\"1\" x=\"2\"/>",
533            "<a>&#0;</a>",
534        ] {
535            assert!(
536                matches!(parse(bad), Err(Fault::Malformed(_))),
537                "{bad}: {:?}",
538                parse(bad)
539            );
540        }
541    }
542
543    #[test]
544    fn external_and_internal_entities_are_never_expanded() {
545        let xxe = "<?xml version=\"1.0\"?><!DOCTYPE r [<!ENTITY x SYSTEM \"file:///etc/passwd\">]><r>&x;</r>";
546        assert!(matches!(parse(xxe), Err(Fault::Refused(_))));
547        let laughs = "<!DOCTYPE r [<!ENTITY a \"ha\"><!ENTITY b \"&a;&a;&a;&a;&a;&a;&a;&a;&a;&a;\">]><r>&b;</r>";
548        assert!(matches!(parse(laughs), Err(Fault::Refused(_))));
549        assert!(matches!(parse("<r>&x;</r>"), Err(Fault::Refused(_))));
550        assert!(matches!(parse("<r a=\"&x;\"/>"), Err(Fault::Refused(_))));
551        let unreferenced = "<!DOCTYPE r [<!ENTITY x SYSTEM \"file:///etc/passwd\">]><r/>";
552        assert!(matches!(parse(unreferenced), Err(Fault::Refused(_))));
553        let declared_only =
554            "<!DOCTYPE issues [<!ELEMENT issues (issue*)><!ATTLIST issues v CDATA \"\">]><issues/>";
555        assert!(parse(declared_only).is_ok());
556    }
557
558    #[test]
559    fn nesting_beyond_the_bound_is_refused() {
560        let deep = format!(
561            "{}{}",
562            "<a>".repeat(MAX_DEPTH + 1),
563            "</a>".repeat(MAX_DEPTH + 1)
564        );
565        assert!(matches!(parse(&deep), Err(Fault::Refused(_))));
566        let ok = format!("{}{}", "<a>".repeat(MAX_DEPTH), "</a>".repeat(MAX_DEPTH));
567        assert!(parse(&ok).is_ok());
568    }
569
570    #[test]
571    fn faults_name_their_line_and_column() {
572        let Err(Fault::Malformed(m)) = parse("<a>\n\n  x <b></a>") else {
573            panic!()
574        };
575        assert!(m.contains("line 3, column"), "{m}");
576        let Err(Fault::Malformed(m)) = parse("<a/>\n  <b/>") else {
577            panic!()
578        };
579        assert!(m.ends_with("line 2, column 3"), "{m}");
580        let Err(Fault::Malformed(m)) = parse("<a/>\n<!DOCTYPE a>") else {
581            panic!()
582        };
583        assert!(m.contains("DOCTYPE"), "{m}");
584        assert!(parse("\n <r/>\n").is_ok());
585    }
586
587    #[test]
588    fn render_is_bounded_like_parse_and_checks_names() {
589        let mut el = element("a".into(), vec![], vec![], String::new());
590        for _ in 1..MAX_DEPTH {
591            el = element("a".into(), vec![], vec![el], String::new());
592        }
593        let text = render(&el).expect("the deepest document parse accepts renders");
594        assert!(parse(&text).is_ok());
595        let deeper = element("a".into(), vec![], vec![el], String::new());
596        assert!(matches!(render(&deeper), Err(Fault::Refused(_))));
597        for ok in ["a", "a1", "a-b.c", "_x", "x:y", "\u{e9}t\u{e9}"] {
598            let el = element(ok.into(), vec![], vec![], String::new());
599            assert!(render(&el).is_ok(), "{ok}");
600        }
601        for bad in ["1a", "-a", ".a", "a b", "a\u{2003}b", "a\u{85}b", ""] {
602            let el = element(bad.into(), vec![], vec![], String::new());
603            assert!(matches!(render(&el), Err(Fault::Refused(_))), "{bad:?}");
604        }
605        let kinds = Value::map([
606            (key("name"), Value::Str(Arc::from("r"))),
607            (
608                key("attributes"),
609                Value::map([
610                    (MapKey::Str(Arc::from("b")), Value::Bool(true)),
611                    (MapKey::Str(Arc::from("f")), Value::Float(1.5)),
612                    (MapKey::Str(Arc::from("n")), Value::Int(7)),
613                ]),
614            ),
615        ]);
616        assert_eq!(
617            render(&kinds).expect("renders"),
618            "<r b=\"true\" f=\"1.5\" n=\"7\"/>"
619        );
620    }
621
622    #[test]
623    fn render_escapes_and_refuses_what_xml_cannot_hold() {
624        let el = element(
625            "r".into(),
626            vec![("q".into(), "a\"<&>\t".into())],
627            vec![],
628            "x < y & z".into(),
629        );
630        assert_eq!(
631            render(&el).expect("renders"),
632            "<r q=\"a&quot;&lt;&amp;&gt;&#9;\">x &lt; y &amp; z</r>"
633        );
634        let plain = element("r".into(), vec![], vec![], "a\"b\n\tc".into());
635        assert_eq!(render(&plain).expect("renders"), "<r>a\"b\n\tc</r>");
636        let bad = element("r x".into(), vec![], vec![], String::new());
637        assert!(matches!(render(&bad), Err(Fault::Refused(_))));
638        let ctl = element("r".into(), vec![], vec![], "\u{1}".into());
639        assert!(matches!(render(&ctl), Err(Fault::Refused(_))));
640        assert!(matches!(render(&Value::Int(1)), Err(Fault::Refused(_))));
641    }
642
643    #[test]
644    fn the_primitives_raise_typed_kinds_in_blue() {
645        let err = crate::run(r#"xml_parse("<a>")"#).expect_err("must raise");
646        assert!(err.to_string().contains(MALFORMED), "{err}");
647        let err = crate::run(r#"xml_parse("<r>&x;</r>")"#).expect_err("must raise");
648        assert!(err.to_string().contains(REFUSED), "{err}");
649        let v = crate::run(r#"xml_render(xml_parse("<a b=\"1\"><c/></a>"))"#)
650            .expect("runs")
651            .value;
652        assert_eq!(scalar(&v).as_deref(), Some("<a b=\"1\"><c/></a>"));
653    }
654}
blue_lang_runtime/xml.rs

blue_lang_runtime/
xml.rs
