Skip to main content

zumen_xml/
parse.rs

1//! XML 1.0 と XML の名前空間 1.0 の文書を読む(決定 0209)。
2//!
3//! 入れ子は再帰でなく、開いた要素の並びでたどる。要素を予算のレコード、入れ子を深さで数える(決定 0010)。
4
5use core::ops::Range;
6use std::collections::{BTreeMap, BTreeSet};
7
8use zumen_base::{Cx, Diagnostic, Error, Kind, Ref, Stop, codes};
9
10use crate::{Attribute, Document, Element, Encoding, Name, Namespace, Node, name, text, utf16};
11
12/// 読めない理由
13enum Fail {
14    /// XML の形になっていない。範囲はその場所
15    Invalid(Range<usize>),
16    /// 予算か中断の合図で止めた。範囲は扱っていた場所
17    Stop(Stop, Range<usize>),
18}
19
20/// XML の文書を読む。XML の形になっていなければ `xml.document.invalid`、UTF-8・Shift_JIS・UTF-16 のほかの文字コードなら
21/// `xml.encoding.unsupported` を報告して読まない。文書型宣言は処理せず `xml.dtd.dropped` を報告する
22pub fn read(src: &[u8], cx: &mut Cx) -> Result<Document, Error> {
23    cx.check(Kind::InputBytes, src.len() as u64)
24        .map_err(|stop| stopped(cx, stop, None))?;
25    if utf16::is_utf32(src) {
26        return Err(unsupported(cx, "UTF-32"));
27    }
28    if let Some(detection) = utf16::detect(src) {
29        return read_utf16(src, detection, cx);
30    }
31    let mut p = Parser::new(src);
32    let encoding = p.encoding(cx)?;
33    match p.document(cx) {
34        Ok(()) => Ok(Document {
35            src: src.to_vec(),
36            encoding,
37            elements: p.elements,
38            doctype: p.doctype,
39            decoded: None,
40        }),
41        Err(Fail::Invalid(range)) => {
42            cx.report(Diagnostic::new(codes::XML_DOCUMENT_INVALID).at(at(range)));
43            Err(Error::Invalid)
44        }
45        Err(Fail::Stop(stop, range)) => Err(stopped(cx, stop, Some(range))),
46    }
47}
48
49fn read_utf16(src: &[u8], detection: utf16::Detection, cx: &mut Cx) -> Result<Document, Error> {
50    let decoded = utf16::Decoded::read(src, detection, cx)?;
51    let mut p = Parser::new(&decoded.bytes);
52    p.mapping = Some(&decoded);
53    let encoding = p.encoding_expected(cx, Some(detection))?;
54    match p.document(cx) {
55        Ok(()) => {}
56        Err(Fail::Invalid(range)) => {
57            cx.report(Diagnostic::new(codes::XML_DOCUMENT_INVALID).at(p.place(range)));
58            return Err(Error::Invalid);
59        }
60        Err(Fail::Stop(stop, range)) => {
61            return Err(stopped(cx, stop, Some(decoded.original_range(range))));
62        }
63    }
64    let mut elements = p.elements;
65    let mut doctype = p.doctype;
66    // 全公開範囲を原本へ戻す。要素番号と親子の順は動かさない。
67    for element in &mut elements {
68        let span = element.span.clone();
69        map_charge(cx, &decoded, span.clone())?;
70        element.span = decoded.original_range(span.clone());
71        map_name(&mut element.name, &decoded);
72        for attribute in &mut element.attributes {
73            map_charge(cx, &decoded, attribute.name.raw.clone())?;
74            map_name(&mut attribute.name, &decoded);
75            attribute.value = decoded.original_range(attribute.value.clone());
76        }
77        for node in &mut element.children {
78            let range = match node {
79                Node::Text(range) | Node::CData(range) => range.clone(),
80                Node::Element(_) => span.clone(),
81            };
82            map_charge(cx, &decoded, range)?;
83            if let Node::Text(range) | Node::CData(range) = node {
84                *range = decoded.original_range(range.clone());
85            }
86        }
87    }
88    if let Some(range) = &mut doctype {
89        map_charge(cx, &decoded, range.clone())?;
90        *range = decoded.original_range(range.clone());
91    }
92    Ok(Document {
93        src: src.to_vec(),
94        encoding,
95        elements,
96        doctype,
97        decoded: Some(decoded),
98    })
99}
100
101fn map_charge(cx: &mut Cx, decoded: &utf16::Decoded, range: Range<usize>) -> Result<(), Error> {
102    cx.check(Kind::Work, 1)
103        .map_err(|stop| stopped(cx, stop, Some(decoded.original_range(range))))
104}
105
106fn map_name(name: &mut Name, decoded: &utf16::Decoded) {
107    name.raw = decoded.original_range(name.raw.clone());
108    name.local = decoded.original_range(name.local..name.local).start;
109    name.prefix_end = name
110        .prefix_end
111        .map(|end| decoded.original_range(end..end).start);
112    if let Some(Namespace::Declared(range)) = &mut name.namespace {
113        *range = decoded.original_range(range.clone());
114    }
115}
116
117fn at(range: Range<usize>) -> Ref {
118    Ref::at_bytes(range.start as u64, range.end as u64)
119}
120
121/// 止めた理由を報告する。扱っていたバイト範囲があれば、場所にする(決定 0119)
122fn stopped(cx: &mut Cx, stop: Stop, place: Option<Range<usize>>) -> Error {
123    let diagnostic = stop.to_diagnostic();
124    cx.report(match place {
125        Some(range) => diagnostic.at(at(range)),
126        None => diagnostic,
127    });
128    Error::Stopped(stop)
129}
130
131fn unsupported(cx: &mut Cx, encoding: &str) -> Error {
132    cx.report(Diagnostic::new(codes::XML_ENCODING_UNSUPPORTED).with("encoding", encoding));
133    Error::Unsupported
134}
135
136fn is_space(byte: u8) -> bool {
137    matches!(byte, b' ' | b'\t' | b'\r' | b'\n')
138}
139
140/// 名前に使えないバイト。0x80 以上は、どの文字コードでも名前の文字として通す
141fn is_delimiter(byte: u8) -> bool {
142    is_space(byte)
143        || matches!(
144            byte,
145            b'<' | b'>' | b'/' | b'=' | b'!' | b'?' | b'"' | b'\'' | b'&' | b';' | b'[' | b']'
146        )
147}
148
149fn find(src: &[u8], pattern: &[u8], from: usize) -> Option<usize> {
150    src.get(from..)?
151        .windows(pattern.len())
152        .position(|window| window == pattern)
153        .map(|at| from + at)
154}
155
156/// `src` の `range` の中で、`byte` の最初の位置。見たバイトの数を `seen` に足す
157fn find_in(src: &[u8], byte: u8, range: Range<usize>, seen: &mut usize) -> Option<usize> {
158    let from = range.start;
159    let rest = src.get(range).unwrap_or_default();
160    let found = rest.iter().position(|b| *b == byte);
161    *seen += found.map_or(rest.len(), |at| at + 1);
162    found.map(|at| from + at)
163}
164
165/// XML 宣言の擬似属性(`version="1.0" encoding="…"`)の名前と値。形が違えば `None`
166fn pseudo_attributes(declaration: &[u8]) -> Option<Vec<(&[u8], &[u8])>> {
167    let mut pairs = Vec::new();
168    let mut rest = declaration;
169    loop {
170        let trimmed = rest.trim_ascii_start();
171        if trimmed.is_empty() {
172            return Some(pairs);
173        }
174        if trimmed.len() == rest.len() && !pairs.is_empty() {
175            return None;
176        }
177        let name_end = trimmed.iter().position(|b| *b == b'=' || is_space(*b))?;
178        let (name, after) = trimmed.split_at(name_end);
179        let after = after
180            .trim_ascii_start()
181            .strip_prefix(b"=")?
182            .trim_ascii_start();
183        let (&quote, after) = after.split_first()?;
184        if !matches!(quote, b'"' | b'\'') {
185            return None;
186        }
187        let end = after.iter().position(|b| *b == quote)?;
188        let (value, after) = after.split_at(end);
189        pairs.push((name, value));
190        rest = after.get(1..).unwrap_or_default();
191    }
192}
193
194/// 名前空間の宣言の接頭辞。既定の名前空間は `None`
195type Prefix<'s> = Option<&'s [u8]>;
196
197/// 名前空間の宣言の値の範囲。`xmlns=""` は `None`
198type Declared = Option<Range<usize>>;
199
200struct Parser<'s> {
201    src: &'s [u8],
202    mapping: Option<&'s utf16::Decoded>,
203    shift_jis: bool,
204    pos: usize,
205    elements: Vec<Element>,
206    /// 開いている要素の名前空間の宣言を、接頭辞ごとに積む。内側の宣言が後。名前を引く手間は、宣言の数に比例せず、
207    /// 接頭辞の種類の数の対数になる(#721)
208    namespaces: BTreeMap<Prefix<'s>, Vec<Declared>>,
209    /// 開いている要素の名前空間の宣言の接頭辞。内側の宣言が後
210    scopes: Vec<Prefix<'s>>,
211    /// 開いている要素ごとの、`scopes` の長さ。閉じるときに戻す
212    marks: Vec<usize>,
213    doctype: Option<Range<usize>>,
214}
215
216impl<'s> Parser<'s> {
217    fn new(src: &'s [u8]) -> Self {
218        Self {
219            src,
220            mapping: None,
221            shift_jis: false,
222            pos: 0,
223            elements: Vec::new(),
224            namespaces: BTreeMap::new(),
225            scopes: Vec::new(),
226            marks: Vec::new(),
227            doctype: None,
228        }
229    }
230
231    fn peek(&self) -> Option<u8> {
232        self.src.get(self.pos).copied()
233    }
234
235    fn place(&self, range: Range<usize>) -> Ref {
236        at(match self.mapping {
237            Some(decoded) => decoded.original_range(range),
238            None => range,
239        })
240    }
241
242    fn starts(&self, pattern: &[u8]) -> bool {
243        self.src
244            .get(self.pos..)
245            .is_some_and(|rest| rest.starts_with(pattern))
246    }
247
248    fn bytes(&self, range: Range<usize>) -> &'s [u8] {
249        self.src.get(range).unwrap_or_default()
250    }
251
252    /// 名前空間を宣言する
253    fn declare(&mut self, prefix: Prefix<'s>, value: Declared) {
254        self.namespaces.entry(prefix).or_default().push(value);
255        self.scopes.push(prefix);
256    }
257
258    /// `scopes` を `mark` の長さに戻し、そのあとの宣言を外す
259    fn unwind(&mut self, mark: usize) {
260        while self.scopes.len() > mark {
261            let Some(prefix) = self.scopes.pop() else {
262                break;
263            };
264            if let Some(stack) = self.namespaces.get_mut(&prefix) {
265                stack.pop();
266                if stack.is_empty() {
267                    self.namespaces.remove(&prefix);
268                }
269            }
270        }
271    }
272
273    /// 接頭辞のいちばん内側の宣言。宣言がなければ `None`
274    fn declared(&self, prefix: Prefix<'s>) -> Option<&Declared> {
275        self.namespaces.get(&prefix).and_then(|stack| stack.last())
276    }
277
278    /// 空白を飛ばす。飛ばしたら真
279    fn skip_space(&mut self) -> bool {
280        let start = self.pos;
281        while self.peek().is_some_and(is_space) {
282            self.pos += 1;
283        }
284        self.pos > start
285    }
286
287    fn work(&self, cx: &mut Cx, amount: u64, start: usize) -> Result<(), Fail> {
288        cx.check(Kind::Work, amount)
289            .map_err(|stop| Fail::Stop(stop, start..self.pos))
290    }
291
292    /// バイト順マークと XML 宣言から、文字コードを決める
293    fn encoding(&mut self, cx: &mut Cx) -> Result<Encoding, Error> {
294        let encoding = self.encoding_expected(cx, None)?;
295        self.shift_jis = encoding == Encoding::ShiftJis;
296        Ok(encoding)
297    }
298
299    fn encoding_expected(
300        &mut self,
301        cx: &mut Cx,
302        expected: Option<utf16::Detection>,
303    ) -> Result<Encoding, Error> {
304        // UTF-16 の原本の BOM は復号時に除去済み。残る U+FEFF は文書の文字なので除かない。
305        let bom = expected.is_none() && self.starts(&[0xef, 0xbb, 0xbf]);
306        if bom {
307            self.pos = 3;
308        } else if matches!(
309            self.src,
310            [0xfe, 0xff, ..] | [0xff, 0xfe, ..] | [0, _, ..] | [_, 0, ..]
311        ) {
312            return Err(unsupported(cx, "UTF-16"));
313        }
314        if !(self.starts(b"<?xml") && self.src.get(self.pos + 5).copied().is_some_and(is_space)) {
315            if let Some(expected) = expected {
316                if !expected.bom {
317                    cx.report(
318                        Diagnostic::new(codes::XML_DOCUMENT_INVALID)
319                            .at(self.place(0..self.src.len().min(1))),
320                    );
321                    return Err(Error::Invalid);
322                }
323                return Ok(match expected.order {
324                    utf16::Order::Little => Encoding::Utf16Le,
325                    utf16::Order::Big => Encoding::Utf16Be,
326                });
327            }
328            return Ok(Encoding::Utf8);
329        }
330        let start = self.pos;
331        let Some(end) = find(self.src, b"?>", start) else {
332            cx.report(
333                Diagnostic::new(codes::XML_DOCUMENT_INVALID).at(self.place(start..self.src.len())),
334            );
335            return Err(Error::Invalid);
336        };
337        let src = self.src;
338        let declaration = src.get(start + 5..end).unwrap_or_default();
339        let Some(pairs) = pseudo_attributes(declaration) else {
340            cx.report(Diagnostic::new(codes::XML_DOCUMENT_INVALID).at(self.place(start..end + 2)));
341            return Err(Error::Invalid);
342        };
343        if pairs.first().map(|(name, _)| *name) != Some(&b"version"[..]) {
344            cx.report(Diagnostic::new(codes::XML_DOCUMENT_INVALID).at(self.place(start..end + 2)));
345            return Err(Error::Invalid);
346        }
347        self.pos = end + 2;
348        if let Some(expected) = expected {
349            let label = pairs
350                .iter()
351                .find(|(name, _)| *name == b"encoding")
352                .map(|(_, label)| *label);
353            // XML 1.0 4.3.3 と RFC 2781 3.3。generic UTF-16 は BOM、LE/BE ラベルは BOM なし。
354            let valid = if expected.bom {
355                label.is_none_or(|label| label.eq_ignore_ascii_case(b"UTF-16"))
356            } else {
357                label.is_some_and(|label| {
358                    label.eq_ignore_ascii_case(match expected.order {
359                        utf16::Order::Little => b"UTF-16LE",
360                        utf16::Order::Big => b"UTF-16BE",
361                    })
362                })
363            };
364            if !valid {
365                cx.report(
366                    Diagnostic::new(codes::XML_DOCUMENT_INVALID).at(self.place(start..end + 2)),
367                );
368                return Err(Error::Invalid);
369            }
370            return Ok(match expected.order {
371                utf16::Order::Little => Encoding::Utf16Le,
372                utf16::Order::Big => Encoding::Utf16Be,
373            });
374        }
375        let Some((_, label)) = pairs.iter().find(|(name, _)| *name == b"encoding") else {
376            return Ok(Encoding::Utf8);
377        };
378        let found = encoding_rs::Encoding::for_label(label);
379        let label = String::from_utf8_lossy(label);
380        if found == Some(encoding_rs::UTF_8) {
381            Ok(Encoding::Utf8)
382        } else if found == Some(encoding_rs::SHIFT_JIS) && !bom {
383            Ok(Encoding::ShiftJis)
384        } else {
385            Err(unsupported(cx, &label))
386        }
387    }
388
389    /// 文書。ルートの要素の前と後には、空白・注記・処理命令と、前に 1 つの文書型宣言だけを置ける
390    fn document(&mut self, cx: &mut Cx) -> Result<(), Fail> {
391        let mut root = false;
392        loop {
393            self.skip_space();
394            let start = self.pos;
395            if self.pos >= self.src.len() {
396                return if root {
397                    Ok(())
398                } else {
399                    Err(Fail::Invalid(start..start))
400                };
401            }
402            self.work(cx, 1, start)?;
403            if self.starts(b"<?") {
404                self.skip_to(b"?>", start)?;
405            } else if self.starts(b"<!--") {
406                self.skip_to(b"-->", start)?;
407            } else if !root && self.doctype.is_none() && self.starts(b"<!DOCTYPE") {
408                self.doctype(cx)?;
409            } else if !root && self.peek() == Some(b'<') {
410                self.tree(cx)?;
411                root = true;
412            } else {
413                return Err(Fail::Invalid(start..self.src.len()));
414            }
415        }
416    }
417
418    /// `pattern` の後まで飛ばす。なければ、`start` から終わりまでを壊れているとする
419    fn skip_to(&mut self, pattern: &[u8], start: usize) -> Result<(), Fail> {
420        let end =
421            find(self.src, pattern, self.pos + 2).ok_or(Fail::Invalid(start..self.src.len()))?;
422        self.pos = end + pattern.len();
423        Ok(())
424    }
425
426    /// 文書型宣言を、内部の部分集合ごと飛ばす。中は処理しない
427    fn doctype(&mut self, cx: &mut Cx) -> Result<(), Fail> {
428        let start = self.pos;
429        self.pos += b"<!DOCTYPE".len();
430        let mut depth = 0usize;
431        loop {
432            let byte = self.peek().ok_or(Fail::Invalid(start..self.src.len()))?;
433            if self.shift_jis && matches!(byte, 0x81..=0x9f | 0xe0..=0xfc) {
434                self.pos += name::shift_jis_width(self.src, self.pos)
435                    .ok_or(Fail::Invalid(self.pos..(self.pos + 2).min(self.src.len())))?;
436                continue;
437            }
438            match byte {
439                b'"' | b'\'' => {
440                    let end = self
441                        .src
442                        .get(self.pos + 1..)
443                        .and_then(|rest| rest.iter().position(|b| *b == byte))
444                        .ok_or(Fail::Invalid(start..self.src.len()))?;
445                    self.pos += end + 2;
446                    continue;
447                }
448                b'<' if self.starts(b"<!--") => {
449                    self.skip_to(b"-->", start)?;
450                    continue;
451                }
452                b'[' => depth += 1,
453                b']' => depth = depth.checked_sub(1).ok_or(Fail::Invalid(start..self.pos))?,
454                b'>' if depth == 0 => break,
455                _ => {}
456            }
457            self.pos += 1;
458        }
459        self.pos += 1;
460        self.doctype = Some(start..self.pos);
461        cx.report(Diagnostic::new(codes::XML_DTD_DROPPED).at(self.place(start..self.pos)));
462        Ok(())
463    }
464
465    /// 名前。`:` で接頭辞と分け、接頭辞を除いた名前の始まりを返す
466    fn name(&mut self, cx: &mut Cx) -> Result<(Range<usize>, usize), Fail> {
467        let start = self.pos;
468        while self.peek().is_some_and(|b| !is_delimiter(b)) {
469            self.pos += if self.shift_jis {
470                name::shift_jis_width(self.src, self.pos)
471                    .ok_or(Fail::Invalid(self.pos..(self.pos + 2).min(self.src.len())))?
472            } else {
473                1
474            };
475        }
476        let raw = start..self.pos;
477        let bytes = self.bytes(raw.clone());
478        if self.mapping.is_some() {
479            self.work(cx, raw.len() as u64, start)?;
480            if !utf16::valid_name(bytes) {
481                return Err(Fail::Invalid(raw));
482            }
483        }
484        if self.shift_jis && !name::valid_shift_jis(bytes) {
485            return Err(Fail::Invalid(raw));
486        }
487        let first = bytes.first().copied();
488        if first.is_none_or(|b| b.is_ascii_digit() || matches!(b, b'-' | b'.' | b':')) {
489            return Err(Fail::Invalid(start..self.pos.max(start + 1)));
490        }
491        let colons: Vec<usize> = bytes
492            .iter()
493            .enumerate()
494            .filter_map(|(at, b)| (*b == b':').then_some(at))
495            .collect();
496        match colons.as_slice() {
497            [] => Ok((raw, start)),
498            [colon] if start + colon + 1 < self.pos => Ok((raw, start + colon + 1)),
499            _ => Err(Fail::Invalid(raw)),
500        }
501    }
502
503    /// 文字か属性の値の参照を確かめる。DTD で宣言する実体の参照は、報告して残す。`&` と `;` は `range` の中だけで
504    /// 探すので、手間は範囲の長さに比例する(#721)。見たバイトの数を返す
505    fn references(&self, range: Range<usize>, cx: &mut Cx) -> Result<usize, Fail> {
506        let mut seen = 0;
507        let mut at = range.start;
508        while let Some(amp) = find_in(self.src, b'&', at..range.end, &mut seen) {
509            let end = find_in(self.src, b';', amp + 1..range.end, &mut seen)
510                .ok_or(Fail::Invalid(amp..range.end))?;
511            let name = core::str::from_utf8(self.bytes(amp + 1..end))
512                .map_err(|_| Fail::Invalid(amp..end + 1))?;
513            if text::reference(name).is_none() {
514                let valid = name
515                    .bytes()
516                    .next()
517                    .is_some_and(|b| !b.is_ascii_digit() && !matches!(b, b'#' | b'-' | b'.'))
518                    && name.bytes().all(|b| !is_delimiter(b));
519                if !valid {
520                    return Err(Fail::Invalid(amp..end + 1));
521                }
522                cx.report(
523                    Diagnostic::new(codes::XML_ENTITY_UNSUPPORTED)
524                        .with("name", name)
525                        .at(self.place(amp..end + 1)),
526                );
527            }
528            at = end + 1;
529        }
530        Ok(seen)
531    }
532
533    /// 接頭辞の名前空間。`element` なら、接頭辞のない名前は既定の名前空間に入る
534    fn resolve(
535        &self,
536        raw: &Range<usize>,
537        local: usize,
538        element: bool,
539        cx: &mut Cx,
540    ) -> Option<Namespace> {
541        if local == raw.start {
542            if element {
543                return self
544                    .declared(None)
545                    .and_then(|value| value.clone().map(Namespace::Declared));
546            }
547            return (self.bytes(raw.clone()) == b"xmlns").then_some(Namespace::Xmlns);
548        }
549        let prefix = self.bytes(raw.start..local - 1);
550        match prefix {
551            b"xml" => return Some(Namespace::Xml),
552            b"xmlns" => return Some(Namespace::Xmlns),
553            _ => {}
554        }
555        match self.declared(Some(prefix)) {
556            Some(value) => value.clone().map(Namespace::Declared),
557            None => {
558                cx.report(
559                    Diagnostic::new(codes::XML_NAMESPACE_MISSING)
560                        .with(
561                            "prefix",
562                            if self.shift_jis {
563                                encoding_rs::SHIFT_JIS
564                                    .decode_without_bom_handling(prefix)
565                                    .0
566                                    .into_owned()
567                            } else {
568                                String::from_utf8_lossy(prefix).into_owned()
569                            },
570                        )
571                        .at(self.place(raw.clone())),
572                );
573                None
574            }
575        }
576    }
577
578    /// ルートの要素と、その中を読む
579    fn tree(&mut self, cx: &mut Cx) -> Result<(), Fail> {
580        let mut open = Vec::new();
581        if self.open(None, cx)? {
582            open.push(0);
583        }
584        while let Some(&current) = open.last() {
585            let start = self.pos;
586            self.work(cx, 1, start)?;
587            let Some(byte) = self.peek() else {
588                let from = self.elements.get(current).map_or(start, |e| e.span.start);
589                return Err(Fail::Invalid(from..start));
590            };
591            if byte != b'<' {
592                let end = find(self.src, b"<", start).unwrap_or(self.src.len());
593                self.pos = end;
594                self.references(start..end, cx)?;
595                self.child(current, Node::Text(start..end));
596            } else if self.starts(b"</") {
597                self.pos += 2;
598                let (raw, _) = self.name(cx)?;
599                self.skip_space();
600                let expected = self
601                    .elements
602                    .get(current)
603                    .map(|e| e.name.raw.clone())
604                    .unwrap_or_default();
605                if self.peek() != Some(b'>') || self.bytes(raw) != self.bytes(expected) {
606                    return Err(Fail::Invalid(start..self.pos + 1));
607                }
608                self.pos += 1;
609                if let Some(element) = self.elements.get_mut(current) {
610                    element.span.end = self.pos;
611                }
612                if let Some(mark) = self.marks.pop() {
613                    self.unwind(mark);
614                }
615                cx.leave();
616                open.pop();
617            } else if self.starts(b"<!--") {
618                self.skip_to(b"-->", start)?;
619            } else if self.starts(b"<![CDATA[") {
620                let inner = start + b"<![CDATA[".len();
621                let end =
622                    find(self.src, b"]]>", inner).ok_or(Fail::Invalid(start..self.src.len()))?;
623                self.pos = end + 3;
624                self.child(current, Node::CData(inner..end));
625            } else if self.starts(b"<?") {
626                self.skip_to(b"?>", start)?;
627            } else if self.starts(b"<!") {
628                return Err(Fail::Invalid(start..start + 2));
629            } else {
630                let index = self.elements.len();
631                if self.open(Some(current), cx)? {
632                    open.push(index);
633                }
634            }
635        }
636        Ok(())
637    }
638
639    fn child(&mut self, parent: usize, node: Node) {
640        if let Some(parent) = self.elements.get_mut(parent) {
641            parent.children.push(node);
642        }
643    }
644
645    /// 開始タグか空要素のタグを読み、要素を足す。中身を持つ要素なら真
646    fn open(&mut self, parent: Option<usize>, cx: &mut Cx) -> Result<bool, Fail> {
647        let start = self.pos;
648        self.pos += 1;
649        let (raw, local) = self.name(cx)?;
650        let mut pairs: Vec<(Range<usize>, usize, Range<usize>)> = Vec::new();
651        let empty = loop {
652            let spaced = self.skip_space();
653            match self.peek() {
654                Some(b'>') => {
655                    self.pos += 1;
656                    break false;
657                }
658                Some(b'/') if self.starts(b"/>") => {
659                    self.pos += 2;
660                    break true;
661                }
662                Some(_) if spaced => {
663                    let (name, name_local) = self.name(cx)?;
664                    self.skip_space();
665                    if self.peek() != Some(b'=') {
666                        return Err(Fail::Invalid(name.start..self.pos + 1));
667                    }
668                    self.pos += 1;
669                    self.skip_space();
670                    let quote = self
671                        .peek()
672                        .filter(|b| matches!(b, b'"' | b'\''))
673                        .ok_or(Fail::Invalid(name.start..self.pos + 1))?;
674                    let value_start = self.pos + 1;
675                    let value_end = self
676                        .src
677                        .get(value_start..)
678                        .and_then(|rest| rest.iter().position(|b| *b == quote))
679                        .map(|end| value_start + end)
680                        .ok_or(Fail::Invalid(name.start..self.src.len()))?;
681                    let value = value_start..value_end;
682                    if self.bytes(value.clone()).contains(&b'<') {
683                        return Err(Fail::Invalid(name.start..value_end + 1));
684                    }
685                    self.pos = value_end + 1;
686                    self.references(value.clone(), cx)?;
687                    pairs.push((name, name_local, value));
688                }
689                _ => return Err(Fail::Invalid(start..self.pos.max(start + 1))),
690            }
691        };
692        cx.check(Kind::Records, 1)
693            .map_err(|stop| Fail::Stop(stop, start..self.pos))?;
694        self.work(cx, 1 + pairs.len() as u64, start)?;
695        cx.enter()
696            .map_err(|stop| Fail::Stop(stop, start..self.pos))?;
697        let mut seen = BTreeSet::new();
698        for (name, _, _) in &pairs {
699            if !seen.insert(self.bytes(name.clone())) {
700                return Err(Fail::Invalid(name.clone()));
701            }
702        }
703        let mark = self.scopes.len();
704        for (name, _, value) in &pairs {
705            let bytes = self.bytes(name.clone());
706            let declared = (!value.is_empty()).then(|| value.clone());
707            if bytes == b"xmlns" {
708                self.declare(None, declared);
709            } else if let Some(prefix) = bytes.strip_prefix(b"xmlns:") {
710                if matches!(prefix, b"xml" | b"xmlns") {
711                    continue;
712                }
713                if declared.is_none() {
714                    return Err(Fail::Invalid(name.clone()));
715                }
716                self.declare(Some(prefix), declared);
717            }
718        }
719        let namespace = self.resolve(&raw, local, true, cx);
720        let attributes = pairs
721            .into_iter()
722            .map(|(name, name_local, value)| Attribute {
723                name: Name {
724                    prefix_end: (name_local > name.start).then_some(name_local.saturating_sub(1)),
725                    namespace: self.resolve(&name, name_local, false, cx),
726                    raw: name,
727                    local: name_local,
728                },
729                value,
730            })
731            .collect();
732        let index = self.elements.len();
733        self.elements.push(Element {
734            span: start..self.pos,
735            name: Name {
736                prefix_end: (local > raw.start).then_some(local.saturating_sub(1)),
737                raw,
738                local,
739                namespace,
740            },
741            attributes,
742            children: Vec::new(),
743            parent,
744        });
745        if let Some(parent) = parent.and_then(|parent| self.elements.get_mut(parent)) {
746            parent.children.push(Node::Element(index));
747        }
748        if empty {
749            self.unwind(mark);
750            cx.leave();
751        } else {
752            self.marks.push(mark);
753        }
754        Ok(!empty)
755    }
756}
757
758#[cfg(test)]
759mod tests {
760    use super::*;
761    use zumen_base::{Budget, CancelToken, Diagnostics};
762
763    /// 参照は範囲の中だけで探し、文書の残りを見ない。小さな範囲を多く確かめても、見たバイトの数は範囲の長さの
764    /// 和を超えない(#721)
765    #[test]
766    fn references_look_only_inside_the_range() {
767        let mut src = b"<a>".to_vec();
768        src.extend(std::iter::repeat_n(b'x', 100_000));
769        src.extend(b"&amp;</a>");
770        let parser = Parser::new(&src);
771        let mut budget = Budget::default();
772        let mut diag = Diagnostics::new();
773        let cancel = CancelToken::new();
774        let mut cx = Cx::new(&mut budget, &mut diag, &cancel);
775        let mut seen = 0;
776        let mut ranges = 0;
777        for start in (3..100_003).step_by(10) {
778            let Ok(found) = parser.references(start..start + 10, &mut cx) else {
779                panic!("{start}");
780            };
781            seen += found;
782            ranges += 10;
783        }
784        assert_eq!(seen, ranges);
785        // 範囲の中の参照は、前と同じく読む
786        let Ok(found) = parser.references(100_003..100_008, &mut cx) else {
787            panic!("&amp;");
788        };
789        assert_eq!(found, 5);
790        assert!(diag.is_empty());
791    }
792
793    /// 名前空間の宣言は接頭辞ごとに積み、閉じた要素の宣言を外す。読み終えたら、積みは空になる(#721)
794    #[test]
795    fn namespaces_are_stacked_by_prefix_and_unwound() {
796        let src = b"<r xmlns:p='urn:r' xmlns='urn:d' xmlns:q='urn:q'>\
797            <p:a xmlns:p='urn:a'><b xmlns=''/></p:a><c xmlns:s='urn:c'/></r>";
798        let mut budget = Budget::default();
799        let mut diag = Diagnostics::new();
800        let cancel = CancelToken::new();
801        let mut cx = Cx::new(&mut budget, &mut diag, &cancel);
802        let mut parser = Parser::new(src);
803        assert!(parser.encoding(&mut cx).is_ok());
804        // ルートの開始タグのあとは、接頭辞ごとに 1 つずつ
805        assert!(matches!(parser.open(None, &mut cx), Ok(true)));
806        assert_eq!(parser.namespaces.len(), 3);
807        assert!(parser.namespaces.values().all(|stack| stack.len() == 1));
808        // `p:a` の中では、`p` の宣言が 2 つ積まれ、内側で引く
809        assert!(matches!(parser.open(Some(0), &mut cx), Ok(true)));
810        let p = Some(&b"p"[..]);
811        assert_eq!(parser.namespaces.get(&p).map(Vec::len), Some(2));
812        let inner = parser.declared(p).cloned().flatten();
813        assert_eq!(inner.map(|value| parser.bytes(value)), Some(&b"urn:a"[..]));
814        assert!(diag.is_empty());
815
816        // 読み終えたら、すべて外れる
817        let mut budget = Budget::default();
818        let mut diag = Diagnostics::new();
819        let mut cx = Cx::new(&mut budget, &mut diag, &cancel);
820        let mut parser = Parser::new(src);
821        assert!(parser.encoding(&mut cx).is_ok());
822        assert!(parser.document(&mut cx).is_ok());
823        assert!(parser.namespaces.is_empty());
824        assert!(parser.scopes.is_empty());
825        assert!(parser.marks.is_empty());
826        assert!(diag.is_empty());
827    }
828}