Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_text/src/xml/read.rs

11.5 KiB, 1 run

created by r1870400018:22558, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Reading XML into a tree that remembers its bytes.
2//!
3//! Stricter than [`crate::doc::html::read`], which is written for a browser's forgiveness. XML is not
4//! forgiving and neither is this: a close tag that names the wrong element, an element left open at
5//! the end, a quotation mark that never closes, are all refused by name rather than recovered from.
6//! The documents this reads are generator output, and a generator that emits mismatched tags has a
7//! bug the caller should hear about rather than have papered over.
8//!
9//! The one thing it is deliberately lenient about is *content it has no opinion on*. A processing
10//! instruction, a comment, a CDATA section and a doctype are each read whole, as one node holding
11//! their bytes, and are never looked into. They travel through an edit untouched because there is no
12//! code here that could touch them.
13//!
14//! # Where the `>` is
15//!
16//! A tag's end is found by parsing its attributes rather than by searching for `>`, because `>` is a
17//! legal character inside an attribute value and appears in real documents. Searching for it is the
18//! bug this is written to not have.
19
20use crate::xml::{
21 Attr,
22 DEPTH_LIMIT,
23 Elem,
24 Name,
25 Node,
26 Span,
27 Xml,
28 write::decode,
29};
30
31use oxedyne_fe2o3_core::prelude::*;
32
33/// The namespace URI of the `xml` prefix, which is bound everywhere and declared nowhere.
34pub const XML_NS: &str = "http://www.w3.org/XML/1998/namespace";
35
36impl Xml {
37
38 /// Reads a document.
39 ///
40 /// The source is kept, because every byte nobody edits is written back out of it.
41 pub fn parse(src: &str) -> Outcome<Self> {
42 let mut p = Parse {
43 src,
44 b: src.as_bytes(),
45 i: 0,
46 uris: Vec::new(),
47 scope: Vec::new(),
48 stack: Vec::new(),
49 marks: Vec::new(),
50 top: Vec::new(),
51 };
52 res!(p.run());
53 Ok(Self {
54 src: src.to_string(),
55 nodes: p.top,
56 uris: p.uris,
57 edits: Vec::new(),
58 })
59 }
60}
61
62/// The state of one pass over a document.
63struct Parse<'a> {
64 /// The source.
65 src: &'a str,
66 /// The source as bytes, which is what the scanning is over.
67 b: &'a [u8],
68 /// Where the next token begins.
69 i: usize,
70 /// The namespace URIs seen so far, once each.
71 uris: Vec<String>,
72 /// The namespace declarations in scope: a prefix, empty for the default, and what it is bound to.
73 scope: Vec<(String, Option<usize>)>,
74 /// The elements left open, outermost first.
75 stack: Vec<Elem>,
76 /// How much of `scope` was in force when each open element began.
77 marks: Vec<usize>,
78 /// The nodes at the top of the document.
79 top: Vec<Node>,
80}
81
82impl<'a> Parse<'a> {
83
84 /// Reads the whole document.
85 fn run(&mut self) -> Outcome<()> {
86 while self.i < self.b.len() {
87 match self.b[self.i] {
88 b'<' => res!(self.markup()),
89 _ => res!(self.chars()),
90 }
91 }
92 if let Some(e) = self.stack.last() {
93 return Err(err!(
94 "<{}> is still open at the end of the document, which began at byte {}.",
95 e.name.qname, e.span.start; Invalid, Input, Missing));
96 }
97 Ok(())
98 }
99
100 /// Reads a run of character data, up to the next `<`.
101 fn chars(&mut self) -> Outcome<()> {
102 let from = self.i;
103 let to = match self.src[from..].find('<') {
104 Some(k) => from + k,
105 None => self.b.len(),
106 };
107 self.i = to;
108 self.push(Node::Text(from..to));
109 Ok(())
110 }
111
112 /// Reads whatever begins with a `<`.
113 fn markup(&mut self) -> Outcome<()> {
114 let from = self.i;
115 let rest = &self.src[from..];
116 if rest.starts_with("<!--") {
117 let to = res!(self.until(from + 4, "-->", "a comment"));
118 self.i = to;
119 self.push(Node::Comment(from..to));
120 return Ok(());
121 }
122 if rest.starts_with("<![CDATA[") {
123 let to = res!(self.until(from + 9, "]]>", "a CDATA section"));
124 self.i = to;
125 self.push(Node::CData(from..to));
126 return Ok(());
127 }
128 if rest.starts_with("<?") {
129 let to = res!(self.until(from + 2, "?>", "a processing instruction"));
130 self.i = to;
131 self.push(Node::Pi(from..to));
132 return Ok(());
133 }
134 if rest.starts_with("<!") {
135 // A doctype, which may carry an internal subset in square brackets. The subset can hold a
136 // `>`, so the end is the bracket's where there is one.
137 let to = match rest.find('[') {
138 Some(k) if k < rest.find('>').unwrap_or(usize::MAX)
139 => res!(self.until(from + k + 1, "]>", "a document type declaration")),
140 _ => res!(self.until(from + 2, ">", "a document type declaration")),
141 };
142 self.i = to;
143 self.push(Node::DocType(from..to));
144 return Ok(());
145 }
146 if rest.starts_with("</") {
147 return self.close(from);
148 }
149 self.open(from)
150 }
151
152 /// Where a run ends, just past the marker that ends it.
153 fn until(&self, at: usize, marker: &str, what: &str) -> Outcome<usize> {
154 match self.src[at..].find(marker) {
155 Some(k) => Ok(at + k + marker.len()),
156 None => Err(err!(
157 "{} opened at byte {} and never closed with `{}`.", what, at, marker;
158 Invalid, Input, Missing)),
159 }
160 }
161
162 /// Reads an open tag, and the element it opens.
163 fn open(&mut self, from: usize) -> Outcome<()> {
164 let ns = from + 1;
165 let ne = name_end(self.b, ns);
166 if ne == ns {
167 return Err(err!(
168 "A tag at byte {} opens with no element name.", from; Invalid, Input));
169 }
170 let (raw, empty, end) = res!(self.attrs(ne));
171 let mark = self.scope.len();
172 // The declarations an element carries are in force for the element itself, so they are read
173 // before either its own name or its attributes are resolved.
174 for a in &raw {
175 let name = &self.src[a.name.clone()];
176 let prefix = match name {
177 "xmlns" => Some(String::new()),
178 n if n.starts_with("xmlns:") => Some(n[6..].to_string()),
179 _ => None,
180 };
181 if let Some(prefix) = prefix {
182 let uri = decode(&self.src[a.value.clone()]);
183 // An empty URI undeclares the prefix, which is legal and means what it says.
184 let at = match uri.is_empty() {
185 true => None,
186 false => Some(self.intern(uri)),
187 };
188 self.scope.push((prefix, at));
189 }
190 }
191 let name = res!(self.name(ns..ne, true));
192 let mut attrs = Vec::with_capacity(raw.len());
193 for a in raw {
194 attrs.push(Attr {
195 name: res!(self.name(a.name.clone(), false)),
196 value: decode(&self.src[a.value.clone()]),
197 span: a.span,
198 val_span: a.value,
199 });
200 }
201 self.i = end;
202 if empty {
203 let elem = Elem { name, attrs, kids: Vec::new(), span: from..end, open: from..end, inner: None };
204 self.scope.truncate(mark);
205 self.push(Node::Elem(elem));
206 return Ok(());
207 }
208 if self.stack.len() >= DEPTH_LIMIT {
209 return Err(err!(
210 "<{}> at byte {} nests deeper than the limit of {}. A document this deep was built \
211 to exhaust the stack of whatever reads it.", name.qname, from, DEPTH_LIMIT;
212 Excessive, Input));
213 }
214 self.stack.push(Elem { name, attrs, kids: Vec::new(), span: from..end, open: from..end, inner: None });
215 self.marks.push(mark);
216 Ok(())
217 }
218
219 /// Reads a close tag, and closes the element it names.
220 fn close(&mut self, from: usize) -> Outcome<()> {
221 let ns = from + 2;
222 let ne = name_end(self.b, ns);
223 let qname = &self.src[ns..ne];
224 let end = res!(self.until(ne, ">", "a closing tag"));
225 let mut elem = match self.stack.pop() {
226 Some(e) => e,
227 None => return Err(err!(
228 "</{}> at byte {} closes an element that was never opened.", qname, from;
229 Invalid, Input)),
230 };
231 if elem.name.qname != qname {
232 return Err(err!(
233 "</{}> at byte {} closes <{}>, which was opened at byte {}.",
234 qname, from, elem.name.qname, elem.span.start; Invalid, Input, Mismatch));
235 }
236 let mark = match self.marks.pop() {
237 Some(m) => m,
238 None => return Err(err!(
239 "The namespace scopes and the open elements went out of step at byte {}.", from;
240 Bug)),
241 };
242 self.scope.truncate(mark);
243 elem.inner = Some(elem.open.end..from);
244 elem.span = elem.span.start..end;
245 self.i = end;
246 self.push(Node::Elem(elem));
247 Ok(())
248 }
249
250 /// Adds a node to whatever is open, or to the top of the document.
251 fn push(&mut self, node: Node) {
252 match self.stack.last_mut() {
253 Some(e) => e.kids.push(node),
254 None => self.top.push(node),
255 }
256 }
257
258 /// Reads the attributes of a tag, saying whether it closed itself and where it ended.
259 ///
260 /// Attributes are parsed rather than skipped over, so a `>` inside a value ends nothing.
261 fn attrs(&self, from: usize) -> Outcome<(Vec<Raw>, bool, usize)> {
262 let mut out = Vec::new();
263 let mut i = from;
264 loop {
265 while i < self.b.len() && self.b[i].is_ascii_whitespace() {
266 i += 1;
267 }
268 match self.b.get(i) {
269 None => return Err(err!(
270 "A tag opened at byte {} and never closed.", from; Invalid, Input, Missing)),
271 Some(b'>') => return Ok((out, false, i + 1)),
272 Some(b'/') => {
273 match self.b.get(i + 1) {
274 Some(b'>') => return Ok((out, true, i + 2)),
275 _ => return Err(err!(
276 "A `/` at byte {} is not followed by the `>` that would close the \
277 tag.", i; Invalid, Input)),
278 }
279 }
280 Some(_) => {}
281 }
282 let ns = i;
283 let ne = name_end(self.b, ns);
284 if ne == ns {
285 return Err(err!(
286 "Byte {} of the tag opened at byte {} is neither an attribute name nor the end \
287 of the tag.", i, from; Invalid, Input));
288 }
289 i = ne;
290 while i < self.b.len() && self.b[i].is_ascii_whitespace() {
291 i += 1;
292 }
293 if self.b.get(i) != Some(&b'=') {
294 return Err(err!(
295 "The attribute `{}` at byte {} has no value. XML has no bare attribute.",
296 &self.src[ns..ne], ns; Invalid, Input, Missing));
297 }
298 i += 1;
299 while i < self.b.len() && self.b[i].is_ascii_whitespace() {
300 i += 1;
301 }
302 let quote = match self.b.get(i) {
303 Some(q) if *q == b'"' || *q == b'\'' => *q,
304 _ => return Err(err!(
305 "The value of `{}` at byte {} is not quoted.", &self.src[ns..ne], i;
306 Invalid, Input)),
307 };
308 let vs = i + 1;
309 let ve = match self.b[vs..].iter().position(|c| *c == quote) {
310 Some(k) => vs + k,
311 None => return Err(err!(
312 "The value of `{}`, which opens at byte {}, is never closed.",
313 &self.src[ns..ne], i; Invalid, Input, Missing)),
314 };
315 i = ve + 1;
316 out.push(Raw { name: ns..ne, value: vs..ve, span: ns..i });
317 }
318 }
319
320 /// Resolves a qualified name against the declarations in scope.
321 ///
322 /// An element with no prefix takes the default namespace; an attribute with no prefix takes none,
323 /// which is what the specification says and what a reader that treated them alike would get wrong
324 /// for every unprefixed attribute in a namespaced document.
325 fn name(&mut self, span: Span, is_elem: bool) -> Outcome<Name> {
326 let qname = self.src[span.clone()].to_string();
327 let prefix = match qname.find(':') {
328 Some(k) => &qname[..k],
329 None => "",
330 };
331 let ns = match (prefix, is_elem) {
332 ("xmlns", _) => None,
333 ("xml", _) => Some(self.intern(XML_NS.to_string())),
334 ("", false) => None,
335 (p, _) => {
336 match self.scope.iter().rev().find(|(q, _)| q == p) {
337 Some((_, at)) => *at,
338 None => match p.is_empty() {
339 true => None,
340 false => return Err(err!(
341 "The prefix `{}` at byte {} is not bound to a namespace.",
342 p, span.start; Invalid, Input, Missing)),
343 },
344 }
345 }
346 };
347 Ok(Name { qname, span, ns })
348 }
349
350 /// Where a URI sits in the document's table, adding it if it is new.
351 fn intern(&mut self, uri: String) -> usize {
352 match self.uris.iter().position(|u| *u == uri) {
353 Some(k) => k,
354 None => {
355 self.uris.push(uri);
356 self.uris.len() - 1
357 }
358 }
359 }
360}
361
362/// One attribute as it was found, before its name is resolved.
363struct Raw {
364 /// The name.
365 name: Span,
366 /// The value, between its quotes.
367 value: Span,
368 /// The whole of it.
369 span: Span,
370}
371
372/// Where a name ends: at whitespace, or at any of the characters that end or divide a tag.
373fn name_end(b: &[u8], from: usize) -> usize {
374 let mut i = from;
375 while i < b.len() {
376 match b[i] {
377 c if c.is_ascii_whitespace() => break,
378 b'>' | b'/' | b'=' => break,
379 _ => i += 1,
380 }
381 }
382 i
383}