roxml 0.4.2

Read-only, zero-copy, lazy XML reader for no_std environments, without allocation
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
// Copyright © 2026 Stephan Kunz
//! Low-level XML parsing helpers.

use core::ops::Range;

use crate::{
	MAX_DEPTH,
	body::{BodyComment, BodyNode, BodyPI},
	error::Error,
	xml_element::XmlElement,
	xml_text::XmlText,
};

/// Length of a leading UTF-8 byte order mark, `0` if there is none.
pub(crate) fn bom_len(text: &str) -> usize {
	if text.starts_with('\u{FEFF}') { 3 } else { 0 }
}

pub(crate) fn skip_whitespace(text: &str, mut pos: usize) -> usize {
	let b = text.as_bytes();
	while pos < b.len() && matches!(b[pos], b' ' | b'\t' | b'\n' | b'\r') {
		pos += 1;
	}
	pos
}

/// Search `bytes[start..]` for `needle`, which must not be empty; return
/// absolute index of first byte.
pub(crate) fn find_bytes(bytes: &[u8], start: usize, needle: &[u8]) -> Option<usize> {
	bytes
		.get(start..)
		.unwrap_or_default()
		.windows(needle.len())
		.position(|w| w == needle)
		.map(|p| p + start)
}

/// Position after the first `needle` at or after `start`, or the end of
/// `bytes` if there is none.
///
/// For navigation in checked content, where every construct is closed.
pub(crate) fn skip_past(bytes: &[u8], start: usize, needle: &[u8]) -> usize {
	find_bytes(bytes, start, needle).map_or(bytes.len(), |p| p + needle.len())
}

/// Scan from `start` (position after `<`) for the unquoted `>` that closes a
/// tag. Returns the index *after* `>`, or the end of `text` if there is none.
///
/// For navigation in checked content, where every open tag is closed.
pub(crate) fn find_tag_end(text: &str, start: usize) -> usize {
	let b = text.as_bytes();
	let mut q: u8 = 0;
	b[start..]
		.iter()
		.position(|&c| {
			match c {
				b'"' | b'\'' if q == 0 => q = c,
				_ if c == q => q = 0,
				b'>' if q == 0 => return true,
				_ => {}
			}
			false
		})
		.map_or(b.len(), |p| start + p + 1)
}

/// Check the rest of an open tag from `pos`, the end of its tag name, as
/// `(S Attribute)* S? '/'? '>'` with `Attribute ::= Name S? '=' S? AttValue`.
/// A name is any non-empty run of bytes other than whitespace, `=`, `/`, `>`
/// and quotes; its characters are not checked further. Returns the index
/// *after* `>`.
///
/// # Errors
/// [`Error::MalformedXml`] if the tag does not follow this grammar or is not
/// closed.
pub(crate) fn check_open_tag(text: &str, mut pos: usize) -> Result<usize, Error> {
	let b = text.as_bytes();
	loop {
		let start = skip_whitespace(text, pos);
		match b.get(start) {
			Some(b'>') => return Ok(start + 1),
			Some(b'/') if b.get(start + 1) == Some(&b'>') => return Ok(start + 2),
			// an attribute has to be preceded by whitespace
			Some(_) if start > pos => {}
			_ => return Err(Error::MalformedXml),
		}
		let name_len = b[start..]
			.iter()
			.position(|c| matches!(c, b' ' | b'\t' | b'\n' | b'\r' | b'=' | b'/' | b'>' | b'"' | b'\''))
			.unwrap_or(b.len() - start);
		if name_len == 0 {
			return Err(Error::MalformedXml);
		}
		let eq = skip_whitespace(text, start + name_len);
		if b.get(eq) != Some(&b'=') {
			return Err(Error::MalformedXml);
		}
		let open_quote = skip_whitespace(text, eq + 1);
		let quote = match b.get(open_quote) {
			Some(&q @ (b'"' | b'\'')) => q,
			_ => return Err(Error::MalformedXml),
		};
		pos = find_bytes(b, open_quote + 1, &[quote]).ok_or(Error::MalformedXml)? + 1;
	}
}

/// Extract the tag name starting at `pos` (first char after `<` or `</`).
pub(crate) fn extract_tag_name(text: &str, pos: usize) -> &str {
	let b = text.as_bytes();
	let mut end = pos;
	while end < b.len() && !matches!(b[end], b' ' | b'\t' | b'\n' | b'\r' | b'>' | b'/' | b'?') {
		end += 1;
	}
	&text[pos..end]
}

/// Whether `name` is acceptable as the name of an open tag: not empty and
/// without quotes, which navigation would take for the start of an attribute
/// value when it looks for the end of the tag.
pub(crate) fn is_tag_name(name: &str) -> bool {
	!name.is_empty() && !name.contains(['"', '\''])
}

/// Split a qualified name `prefix:local` into its prefix and local part.
pub(crate) fn split_qname(name: &str) -> (Option<&str>, &str) {
	match name.split_once(':') {
		Some((prefix, local)) => (Some(prefix), local),
		None => (None, name),
	}
}

/// Whether the tag ending before `tag_end` is self-closing; a tag is at least
/// two bytes long.
pub(crate) fn self_closing(bytes: &[u8], tag_end: usize) -> bool {
	bytes[tag_end - 2] == b'/'
}

/// Strip `<!--` and `-->` from a comment's source slice.
pub(crate) fn comment_text(source: &str) -> &str {
	source
		.strip_prefix("<!--")
		.and_then(|r| r.strip_suffix("-->"))
		.unwrap_or(source)
}

/// Target of the processing instruction occupying `range`.
pub(crate) fn pi_target<'a>(text: &'a str, range: &Range<usize>) -> &'a str {
	extract_tag_name(text, range.start + 2)
}

/// Content of the processing instruction occupying `range`: everything after
/// the target and its trailing whitespace, up to (but not including) `?>`.
pub(crate) fn pi_content<'a>(text: &'a str, range: &Range<usize>) -> &'a str {
	let after_target = range.start + 2 + pi_target(text, range).len();
	let end = range.end.saturating_sub(2).max(after_target);
	text[after_target..end].trim_start_matches(|c: char| c.is_ascii_whitespace())
}

/// Whether a DOCTYPE declaration starts at `pos` (which points to `<`).
pub(crate) fn is_doctype_at(bytes: &[u8], pos: usize) -> bool {
	bytes.get(pos + 1..pos + 9) == Some(b"!DOCTYPE")
}

/// Find the end of the DOCTYPE declaration starting at `pos` (which points to
/// `<`). Returns the index *after* the closing `>`.
///
/// Quoted literals and an internal subset `[ … ]` (including comments and
/// processing instructions inside it) may contain `>`, which does not end the
/// declaration.
pub(crate) fn find_doctype_end(bytes: &[u8], pos: usize) -> Option<usize> {
	let mut i = pos + 9;
	let mut quote: u8 = 0;
	let mut in_subset = false;
	while i < bytes.len() {
		let c = bytes[i];
		if quote != 0 {
			if c == quote {
				quote = 0;
			}
			i += 1;
			continue;
		}
		match c {
			b'"' | b'\'' => quote = c,
			b'[' if !in_subset => in_subset = true,
			b']' if in_subset => in_subset = false,
			b'<' if in_subset && bytes.get(i + 1..i + 4) == Some(b"!--") => {
				i = find_bytes(bytes, i + 4, b"-->")? + 3;
				continue;
			}
			b'<' if in_subset && bytes.get(i + 1) == Some(&b'?') => {
				i = find_bytes(bytes, i + 2, b"?>")? + 2;
				continue;
			}
			b'>' if !in_subset => return Some(i + 1),
			_ => {}
		}
		i += 1;
	}
	None
}

/// Whether the XML declaration starts at `pos`: `<?xml` followed by white
/// space or `?`.
pub(crate) fn is_declaration_at(bytes: &[u8], pos: usize) -> bool {
	bytes.get(pos..pos + 5) == Some(b"<?xml") && matches!(bytes.get(pos + 5), Some(b' ' | b'\t' | b'\n' | b'\r' | b'?'))
}

/// Whether the processing instruction at `pos` has the target `xml` in any
/// case, which is reserved for the XML declaration at the start of the
/// document.
pub(crate) fn is_reserved_pi_at(bytes: &[u8], pos: usize) -> bool {
	bytes
		.get(pos + 2..pos + 5)
		.is_some_and(|target| target.eq_ignore_ascii_case(b"xml"))
		&& matches!(bytes.get(pos + 5), Some(b' ' | b'\t' | b'\n' | b'\r' | b'?'))
}

/// Skip whitespace, comments, processing instructions and, if
/// `allow_doctype`, DOCTYPE declarations, starting at `pos`.
///
/// Returns the position of the next other markup, or `text.len()`.
///
/// # Errors
/// - [`Error::MalformedXml`] if character data is found, a skipped
///   construct is unclosed or a processing instruction has the reserved
///   target `xml`.
pub(crate) fn skip_misc(text: &str, mut pos: usize, allow_doctype: bool) -> Result<usize, Error> {
	let b = text.as_bytes();
	loop {
		pos = skip_whitespace(text, pos);
		if pos >= b.len() {
			return Ok(b.len());
		}
		if b[pos] != b'<' {
			return Err(Error::MalformedXml);
		}
		if b.get(pos + 1) == Some(&b'?') {
			if is_reserved_pi_at(b, pos) {
				return Err(Error::MalformedXml);
			}
			pos = find_bytes(b, pos + 2, b"?>").ok_or(Error::MalformedXml)? + 2;
		} else if b.get(pos + 1..pos + 4) == Some(b"!--") {
			pos = find_bytes(b, pos + 4, b"-->").ok_or(Error::MalformedXml)? + 3;
		} else if allow_doctype && is_doctype_at(b, pos) {
			pos = find_doctype_end(b, pos).ok_or(Error::MalformedXml)?;
		} else {
			return Ok(pos);
		}
	}
}

/// Type of the offsets that [`check_element_content`] keeps on its stack.
///
/// `u16` halves the stack space for content up to 64 KiB, which is the
/// common case on embedded targets; `usize` covers everything else.
pub(crate) trait Offset: Copy + Default + TryFrom<usize> + Into<usize> {}
impl Offset for u16 {}
impl Offset for usize {}

/// Check the content of the element whose open tag `tag_name` ends at
/// `start` and return the range of its close tag.
///
/// Checks that every element inside is properly nested and that comments,
/// processing instructions and CDATA sections are closed. The names of the
/// pending open tags are remembered on a fixed-size stack as offsets from
/// `start`, so no allocation takes place. The element itself counts as one
/// level. All offsets must fit into `O`.
///
/// Only [`check_root_at`] uses this. It is never inlined, so the stack of
/// names occupies the stack only during the check and not during navigation.
///
/// # Errors
/// - [`Error::MalformedXml`] if a close tag does not match its open tag, an
///   open tag is malformed or has a name that is empty or contains a quote, a
///   tag, comment, PI or CDATA section is unclosed,
///   or other markup is misplaced.
/// - [`Error::TooDeep`] if elements are nested deeper than [`MAX_DEPTH`].
#[inline(never)]
pub(crate) fn check_element_content<O: Offset>(text: &str, start: usize, tag_name: &str) -> Result<Range<usize>, Error> {
	let b = text.as_bytes();
	// offsets from `start` of the names of the open tags that are still pending
	let mut open = [O::default(); MAX_DEPTH - 1];
	let mut depth = 0usize;
	let mut pos = start;

	loop {
		pos += b[pos..]
			.iter()
			.position(|&c| c == b'<')
			.ok_or(Error::MalformedXml)?;

		match b.get(pos + 1) {
			// Comment, CDATA — skipped
			Some(b'!') => {
				if b.get(pos + 2..pos + 4) == Some(b"--") {
					pos = find_bytes(b, pos + 4, b"-->").ok_or(Error::MalformedXml)? + 3;
				} else if b.get(pos + 2..pos + 9) == Some(b"[CDATA[") {
					pos = find_bytes(b, pos + 9, b"]]>").ok_or(Error::MalformedXml)? + 3;
				} else {
					return Err(Error::MalformedXml);
				}
			}
			// PI — skipped
			Some(b'?') => {
				if is_reserved_pi_at(b, pos) {
					return Err(Error::MalformedXml);
				}
				pos = find_bytes(b, pos + 2, b"?>").ok_or(Error::MalformedXml)? + 2;
			}
			// Close tag — must match the innermost pending open tag
			Some(b'/') => {
				let name = extract_tag_name(text, pos + 2);
				let expected = if depth == 0 {
					tag_name
				} else {
					extract_tag_name(text, start + open[depth - 1].into())
				};
				if name != expected {
					return Err(Error::MalformedXml);
				}
				let gt = skip_whitespace(text, pos + 2 + name.len());
				if b.get(gt) != Some(&b'>') {
					return Err(Error::MalformedXml);
				}
				if depth == 0 {
					return Ok(pos..gt + 1);
				}
				depth -= 1;
				pos = gt + 1;
			}
			// Open tag — remembered unless self-closing
			_ => {
				let name = extract_tag_name(text, pos + 1);
				if !is_tag_name(name) {
					return Err(Error::MalformedXml);
				}
				let tag_end = check_open_tag(text, pos + 1 + name.len())?;
				if !self_closing(b, tag_end) {
					if depth == open.len() {
						return Err(Error::TooDeep);
					}
					// always fits: `check_root_at` selects `O` for the length of the content
					open[depth] = O::try_from(pos + 1 - start).unwrap_or_default();
					depth += 1;
				}
				pos = tag_end;
			}
		}
	}
}

/// Check the root element starting at `pos` (must point to `<`) including its
/// whole content.
///
/// # Errors
/// - [`Error::MalformedXml`] if there is no well-formed element at `pos`.
/// - [`Error::TooDeep`] if elements are nested deeper than [`MAX_DEPTH`].
pub(crate) fn check_root_at(xml_text: &str, pos: usize) -> Result<XmlElement<'_>, Error> {
	let b = xml_text.as_bytes();
	let tag_name = extract_tag_name(xml_text, pos + 1);
	if !is_tag_name(tag_name) || tag_name.starts_with('!') {
		return Err(Error::MalformedXml);
	}

	let tag_end = check_open_tag(xml_text, pos + 1 + tag_name.len())?;
	let close = if self_closing(b, tag_end) {
		tag_end..tag_end
	} else if b.len() - tag_end <= usize::from(u16::MAX) {
		check_element_content::<u16>(xml_text, tag_end, tag_name)?
	} else {
		check_element_content::<usize>(xml_text, tag_end, tag_name)?
	};
	// the root element has no siblings
	let end = close.end;
	Ok(XmlElement::new(xml_text, pos..tag_end, close, end))
}

/// Find the range of the close tag that matches the open tag ending at
/// `start`.
///
/// Only counts the nesting depth, the content must have been checked by
/// [`check_root_at`] before, so the close tag exists. Unchecked, unclosed
/// content ends at the end of the text.
pub(crate) fn find_close_tag(text: &str, start: usize) -> Range<usize> {
	let b = text.as_bytes();
	let mut depth = 0usize;
	let mut pos = start;

	loop {
		pos += b[pos..]
			.iter()
			.position(|&c| c == b'<')
			.unwrap_or(b.len() - pos);
		match b.get(pos + 1) {
			// Comment or CDATA — skipped
			Some(b'!') if b.get(pos + 2) == Some(&b'-') => pos = skip_past(b, pos + 4, b"-->"),
			Some(b'!') => pos = skip_past(b, pos + 9, b"]]>"),
			// PI — skipped
			Some(b'?') => pos = skip_past(b, pos + 2, b"?>"),
			// Close tag, or the end of the text
			Some(b'/') | None => {
				let gt = skip_past(b, pos, b">");
				if depth == 0 {
					return pos..gt;
				}
				depth -= 1;
				pos = gt;
			}
			// Open tag
			Some(_) => {
				let tag_end = find_tag_end(text, pos + 1);
				if !self_closing(b, tag_end) {
					depth += 1;
				}
				pos = tag_end;
			}
		}
	}
}

/// Parse the element starting at `pos` (must point to the `<` of an open tag)
/// inside content checked by [`check_root_at`].
/// `content_end` is the limit for sibling searches on the returned element.
pub(crate) fn parse_element_at(xml_text: &str, pos: usize, content_end: usize) -> XmlElement<'_> {
	let tag_end = find_tag_end(xml_text, pos + 1);
	let close = if self_closing(xml_text.as_bytes(), tag_end) {
		tag_end..tag_end
	} else {
		find_close_tag(xml_text, tag_end)
	};
	XmlElement::new(xml_text, pos..tag_end, close, content_end)
}

/// Find the start of the next body node at or after `pos`, or `None` if `end`
/// is reached first.
///
/// `end` is the start of the parent's close tag, so in checked content every
/// `<` before it starts a node. Whitespace-only text between markup is skipped.
/// A text node that contains anything else starts at `pos`, so its leading
/// whitespace is preserved.
pub(crate) fn advance_body_cursor(xml_text: &str, pos: usize, end: usize) -> Option<usize> {
	let b = xml_text.as_bytes();
	let next = skip_whitespace(xml_text, pos);
	if next >= end {
		return None;
	}
	if b[next] == b'<' {
		Some(next)
	} else {
		Some(pos) // text node, including its leading whitespace
	}
}

/// Parse one body node at `pos` (result of `advance_body_cursor`) inside
/// content checked by [`check_root_at`].
pub(crate) fn parse_body_node_at(xml_text: &str, pos: usize, content_end: usize) -> BodyNode<'_> {
	let b = xml_text.as_bytes();

	if b[pos] != b'<' {
		// Plain text node — scan to next '<' or content_end
		let len = b[pos..content_end]
			.iter()
			.position(|&c| c == b'<')
			.unwrap_or(content_end - pos);
		return BodyNode::Text(XmlText::new(xml_text, pos..pos + len, content_end));
	}

	// Comment
	if b.get(pos + 1..pos + 4) == Some(b"!--") {
		let end = skip_past(b, pos + 4, b"-->");
		return BodyNode::Comment(BodyComment::new(xml_text, pos..end, content_end));
	}

	// CDATA — surfaces as Text
	if b.get(pos + 1..pos + 9) == Some(b"![CDATA[") {
		let end = skip_past(b, pos + 9, b"]]>");
		return BodyNode::Text(XmlText::new(xml_text, pos..end, content_end));
	}

	// Processing instruction
	if b.get(pos + 1) == Some(&b'?') {
		let end = skip_past(b, pos + 2, b"?>");
		return BodyNode::PI(BodyPI::new(xml_text, pos..end, content_end));
	}

	// Regular element
	BodyNode::Element(parse_element_at(xml_text, pos, content_end))
}

/// The next body node at or after `pos`, bounded by `content_end`.
pub(crate) fn next_body_sibling(xml_text: &str, pos: usize, content_end: usize) -> Option<BodyNode<'_>> {
	advance_body_cursor(xml_text, pos, content_end).map(|pos| parse_body_node_at(xml_text, pos, content_end))
}