Skip to main content

teixml/
document.rs

1//! Adapts a parsed `roxmltree` document to the validator's [`Element`] trait.
2
3use std::fmt;
4
5use std::collections::HashMap;
6
7use crate::relaxng::{
8    Content, Element, ElementPath, ExpandedName, IdType, IdTypes, ValidationErrorKind,
9};
10
11/// A 1-based line and column in the source document.
12#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
13pub struct Position {
14    /// Line number, starting at 1.
15    pub line: u32,
16    /// Column number (in characters), starting at 1.
17    pub column: u32,
18}
19
20impl fmt::Display for Position {
21    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
22        write!(f, "{}:{}", self.line, self.column)
23    }
24}
25
26/// Converts byte offsets in a document to line and column numbers. Built once
27/// per document, so each lookup is a binary search instead of a scan from
28/// the start of the text.
29pub(crate) struct LineIndex<'a> {
30    text: &'a str,
31    line_starts: Vec<usize>,
32}
33
34impl<'a> LineIndex<'a> {
35    pub(crate) fn new(text: &'a str) -> Self {
36        let line_starts = std::iter::once(0)
37            .chain(text.match_indices('\n').map(|(offset, _)| offset + 1))
38            .collect();
39        Self { text, line_starts }
40    }
41
42    /// The 1-based line and column (counted in characters, as `roxmltree`
43    /// does) of the byte at `offset`.
44    pub(crate) fn position(&self, offset: usize) -> Position {
45        let line = self.line_starts.partition_point(|&start| start <= offset);
46        let start = self.line_starts[line - 1];
47        let column = self.text[start..offset].chars().count() + 1;
48        Position {
49            line: u32::try_from(line).unwrap_or(u32::MAX),
50            column: u32::try_from(column).unwrap_or(u32::MAX),
51        }
52    }
53}
54
55/// An element node in a `roxmltree` document.
56#[derive(Clone, Copy)]
57pub(crate) struct Node<'a, 'input> {
58    node: roxmltree::Node<'a, 'input>,
59}
60
61impl<'a, 'input> Node<'a, 'input> {
62    pub(crate) fn root(doc: &'a roxmltree::Document<'input>) -> Self {
63        Self {
64            node: doc.root_element(),
65        }
66    }
67}
68
69impl Element for Node<'_, '_> {
70    /// The byte offset of the element's start tag; see [`LineIndex`].
71    type Location = usize;
72
73    fn name(&self) -> ExpandedName {
74        let tag = self.node.tag_name();
75        ExpandedName::new(tag.namespace(), tag.name())
76    }
77
78    fn attributes(&self) -> impl Iterator<Item = (ExpandedName, String)> {
79        self.node.attributes().map(|attribute| {
80            (
81                ExpandedName::new(attribute.namespace(), attribute.name()),
82                attribute.value().to_owned(),
83            )
84        })
85    }
86
87    fn children(&self) -> impl Iterator<Item = Content<Self>> {
88        Children {
89            next: self.node.first_child(),
90            text: String::new(),
91            pending: None,
92        }
93    }
94
95    /// Just past the `>` that ends the element's start tag, where Jing
96    /// reports problems with the element and its attributes.
97    fn location(&self) -> Option<usize> {
98        Some(start_tag_end(self.node))
99    }
100
101    fn start_location(&self) -> Option<usize> {
102        Some(self.node.range().start)
103    }
104
105    fn end_tag_location(&self) -> Option<usize> {
106        let range = self.node.range();
107        let text = &self.node.document().input_text()[range.clone()];
108        text.rfind("</").map(|offset| range.start + offset)
109    }
110
111    /// Just past the element's end tag, where Jing also reports it.
112    fn end_location(&self) -> Option<usize> {
113        Some(self.node.range().end)
114    }
115
116    fn namespace_bindings(&self) -> impl Iterator<Item = (String, String)> {
117        self.node.namespaces().map(|namespace| {
118            (
119                namespace.name().unwrap_or_default().to_owned(),
120                namespace.uri().to_owned(),
121            )
122        })
123    }
124}
125
126/// The offset just past the `>` that ends `node`'s start tag.
127fn start_tag_end(node: roxmltree::Node<'_, '_>) -> usize {
128    let text = node.document().input_text().as_bytes();
129    let mut quote = None;
130    for (offset, &byte) in text.iter().enumerate().skip(node.range().start) {
131        match (quote, byte) {
132            (Some(q), _) if byte == q => quote = None,
133            (Some(_), _) => {}
134            (None, b'"' | b'\'') => quote = Some(byte),
135            (None, b'>') => return offset + 1,
136            _ => {}
137        }
138    }
139    node.range().start
140}
141
142/// A problem found by [`id_errors`]: where (a byte offset), what, and the
143/// path of element names to it.
144pub(crate) type IdError = (usize, ValidationErrorKind, ElementPath);
145
146/// Checks the attributes `ids` gives an ID-type, as Jing does: every ID value
147/// is unique, and every IDREF names one. Returns the duplicates (each
148/// followed by where that ID first occurred), in document order, and the
149/// unresolved references, which are only known at the end.
150pub(crate) fn id_errors(
151    doc: &roxmltree::Document<'_>,
152    ids: &IdTypes,
153) -> (Vec<IdError>, Vec<IdError>) {
154    let mut defined: HashMap<&str, roxmltree::Node<'_, '_>> = HashMap::new();
155    let mut references: Vec<(&str, roxmltree::Node<'_, '_>)> = Vec::new();
156    let mut duplicates = Vec::new();
157    for element in doc.descendants().filter(roxmltree::Node::is_element) {
158        let element_name = (
159            element.tag_name().namespace().unwrap_or_default(),
160            element.tag_name().name(),
161        );
162        for attribute in element.attributes() {
163            let attribute_name = (attribute.namespace().unwrap_or_default(), attribute.name());
164            let Some(id_type) = ids.get(element_name, attribute_name) else {
165                continue;
166            };
167            let value = attribute.value();
168            match id_type {
169                IdType::Id => {
170                    let id = value.trim_matches(|c: char| c.is_ascii_whitespace());
171                    if let Some(&first) = defined.get(id) {
172                        duplicates.push((
173                            start_tag_end(element),
174                            ValidationErrorKind::DuplicateId(id.into()),
175                            path(element),
176                        ));
177                        duplicates.push((
178                            start_tag_end(first),
179                            ValidationErrorKind::FirstIdOccurrence(id.into()),
180                            path(first),
181                        ));
182                    } else {
183                        defined.insert(id, element);
184                    }
185                }
186                IdType::Idref => references.push((
187                    value.trim_matches(|c: char| c.is_ascii_whitespace()),
188                    element,
189                )),
190                IdType::Idrefs => {
191                    references.extend(value.split_ascii_whitespace().map(|id| (id, element)))
192                }
193            }
194        }
195    }
196    let unresolved = references
197        .into_iter()
198        .filter(|(id, _)| !defined.contains_key(id))
199        .map(|(id, element)| {
200            (
201                start_tag_end(element),
202                ValidationErrorKind::UnresolvedIdref(id.into()),
203                path(element),
204            )
205        })
206        .collect();
207    (duplicates, unresolved)
208}
209
210/// The names of `element` and its ancestors.
211pub(crate) fn path(element: roxmltree::Node<'_, '_>) -> ElementPath {
212    let mut names: Vec<ExpandedName> = element
213        .ancestors()
214        .filter(roxmltree::Node::is_element)
215        .map(|ancestor| {
216            let tag = ancestor.tag_name();
217            ExpandedName::new(tag.namespace(), tag.name())
218        })
219        .collect();
220    names.reverse();
221    ElementPath::from_names(names)
222}
223
224/// Yields child elements and merged runs of text, skipping comments and
225/// processing instructions (and merging text across them, as RELAX NG
226/// requires).
227struct Children<'a, 'input> {
228    next: Option<roxmltree::Node<'a, 'input>>,
229    text: String,
230    pending: Option<Node<'a, 'input>>,
231}
232
233impl<'a, 'input> Iterator for Children<'a, 'input> {
234    type Item = Content<Node<'a, 'input>>;
235
236    fn next(&mut self) -> Option<Self::Item> {
237        if let Some(element) = self.pending.take() {
238            return Some(Content::Element(element));
239        }
240        while let Some(node) = self.next {
241            self.next = node.next_sibling();
242            if node.is_element() {
243                let element = Node { node };
244                if self.text.is_empty() {
245                    return Some(Content::Element(element));
246                }
247                self.pending = Some(element);
248                return Some(Content::Text(std::mem::take(&mut self.text)));
249            }
250            if let Some(text) = node.text().filter(|_| node.is_text()) {
251                self.text.push_str(text);
252            }
253        }
254        (!self.text.is_empty()).then(|| Content::Text(std::mem::take(&mut self.text)))
255    }
256}
257
258#[cfg(test)]
259mod tests {
260    use super::*;
261
262    #[test]
263    fn line_index_matches_roxmltree() {
264        let text = "<a>\n  <b/>\r\n<c>é<d/></c>\n\n<e/></a>";
265        let doc = roxmltree::Document::parse(text).unwrap();
266        let index = LineIndex::new(text);
267        for node in doc.descendants().filter(roxmltree::Node::is_element) {
268            let start = node.range().start;
269            let expected = doc.text_pos_at(start);
270            assert_eq!(
271                index.position(start),
272                Position {
273                    line: expected.row,
274                    column: expected.col
275                },
276                "{:?}",
277                node.tag_name()
278            );
279        }
280    }
281}