summaryrefslogtreecommitdiffstats
path: root/vendor/markup5ever/util
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-17 12:02:58 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-17 12:02:58 +0000
commit698f8c2f01ea549d77d7dc3338a12e04c11057b9 (patch)
tree173a775858bd501c378080a10dca74132f05bc50 /vendor/markup5ever/util
parentInitial commit. (diff)
downloadrustc-698f8c2f01ea549d77d7dc3338a12e04c11057b9.tar.xz
rustc-698f8c2f01ea549d77d7dc3338a12e04c11057b9.zip
Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'vendor/markup5ever/util')
-rw-r--r--vendor/markup5ever/util/buffer_queue.rs303
-rw-r--r--vendor/markup5ever/util/smallcharset.rs90
2 files changed, 393 insertions, 0 deletions
diff --git a/vendor/markup5ever/util/buffer_queue.rs b/vendor/markup5ever/util/buffer_queue.rs
new file mode 100644
index 000000000..d5724890c
--- /dev/null
+++ b/vendor/markup5ever/util/buffer_queue.rs
@@ -0,0 +1,303 @@
+// Copyright 2014-2017 The html5ever Project Developers. See the
+// COPYRIGHT file at the top-level directory of this distribution.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! The `BufferQueue` struct and helper types.
+//!
+//! This type is designed for the efficient parsing of string data, especially where many
+//! significant characters are from the ascii range 0-63. This includes, for example, important
+//! characters in xml/html parsing.
+//!
+//! Good and predictable performance is achieved by avoiding allocation where possible (a.k.a. zero
+//! copy).
+//!
+//! [`BufferQueue`]: struct.BufferQueue.html
+
+use std::collections::VecDeque;
+
+use tendril::StrTendril;
+
+pub use self::SetResult::{FromSet, NotFromSet};
+use crate::util::smallcharset::SmallCharSet;
+
+/// Result from [`pop_except_from`] containing either a character from a [`SmallCharSet`], or a
+/// string buffer of characters not from the set.
+///
+/// [`pop_except_from`]: struct.BufferQueue.html#method.pop_except_from
+/// [`SmallCharSet`]: ../struct.SmallCharSet.html
+#[derive(PartialEq, Eq, Debug)]
+pub enum SetResult {
+ /// A character from the `SmallCharSet`.
+ FromSet(char),
+ /// A string buffer containing no characters from the `SmallCharSet`.
+ NotFromSet(StrTendril),
+}
+
+/// A queue of owned string buffers, which supports incrementally consuming characters.
+///
+/// Internally it uses [`VecDeque`] and has the same complexity properties.
+///
+/// [`VecDeque`]: https://doc.rust-lang.org/std/collections/struct.VecDeque.html
+#[derive(Debug)]
+pub struct BufferQueue {
+ /// Buffers to process.
+ buffers: VecDeque<StrTendril>,
+}
+
+impl BufferQueue {
+ /// Create an empty BufferQueue.
+ #[inline]
+ pub fn new() -> BufferQueue {
+ BufferQueue {
+ buffers: VecDeque::with_capacity(16),
+ }
+ }
+
+ /// Returns whether the queue is empty.
+ #[inline]
+ pub fn is_empty(&self) -> bool {
+ self.buffers.is_empty()
+ }
+
+ /// Get the buffer at the beginning of the queue.
+ #[inline]
+ pub fn pop_front(&mut self) -> Option<StrTendril> {
+ self.buffers.pop_front()
+ }
+
+ /// Add a buffer to the beginning of the queue.
+ ///
+ /// If the buffer is empty, it will be skipped.
+ pub fn push_front(&mut self, buf: StrTendril) {
+ if buf.len32() == 0 {
+ return;
+ }
+ self.buffers.push_front(buf);
+ }
+
+ /// Add a buffer to the end of the queue.
+ ///
+ /// If the buffer is empty, it will be skipped.
+ pub fn push_back(&mut self, buf: StrTendril) {
+ if buf.len32() == 0 {
+ return;
+ }
+ self.buffers.push_back(buf);
+ }
+
+ /// Look at the next available character without removing it, if the queue is not empty.
+ pub fn peek(&self) -> Option<char> {
+ debug_assert!(
+ self.buffers
+ .iter()
+ .find(|el| el.len32() == 0)
+ .is_none(),
+ "invariant \"all buffers in the queue are non-empty\" failed"
+ );
+ self.buffers.front().map(|b| b.chars().next().unwrap())
+ }
+
+ /// Get the next character if one is available, removing it from the queue.
+ ///
+ /// This function manages the buffers, removing them as they become empty.
+ pub fn next(&mut self) -> Option<char> {
+ let (result, now_empty) = match self.buffers.front_mut() {
+ None => (None, false),
+ Some(buf) => {
+ let c = buf.pop_front_char().expect("empty buffer in queue");
+ (Some(c), buf.is_empty())
+ },
+ };
+
+ if now_empty {
+ self.buffers.pop_front();
+ }
+
+ result
+ }
+
+ /// Pops and returns either a single character from the given set, or
+ /// a buffer of characters none of which are in the set.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # #[macro_use] extern crate markup5ever;
+ /// # #[macro_use] extern crate tendril;
+ /// # fn main() {
+ /// use markup5ever::buffer_queue::{BufferQueue, SetResult};
+ ///
+ /// let mut queue = BufferQueue::new();
+ /// queue.push_back(format_tendril!(r#"<some_tag attr="text">SomeText</some_tag>"#));
+ /// let set = small_char_set!(b'<' b'>' b' ' b'=' b'"' b'/');
+ /// let tag = format_tendril!("some_tag");
+ /// let attr = format_tendril!("attr");
+ /// let attr_val = format_tendril!("text");
+ /// assert_eq!(queue.pop_except_from(set), Some(SetResult::FromSet('<')));
+ /// assert_eq!(queue.pop_except_from(set), Some(SetResult::NotFromSet(tag)));
+ /// assert_eq!(queue.pop_except_from(set), Some(SetResult::FromSet(' ')));
+ /// assert_eq!(queue.pop_except_from(set), Some(SetResult::NotFromSet(attr)));
+ /// assert_eq!(queue.pop_except_from(set), Some(SetResult::FromSet('=')));
+ /// assert_eq!(queue.pop_except_from(set), Some(SetResult::FromSet('"')));
+ /// assert_eq!(queue.pop_except_from(set), Some(SetResult::NotFromSet(attr_val)));
+ /// // ...
+ /// # }
+ /// ```
+ pub fn pop_except_from(&mut self, set: SmallCharSet) -> Option<SetResult> {
+ let (result, now_empty) = match self.buffers.front_mut() {
+ None => (None, false),
+ Some(buf) => {
+ let n = set.nonmember_prefix_len(&buf);
+ if n > 0 {
+ let out;
+ unsafe {
+ out = buf.unsafe_subtendril(0, n);
+ buf.unsafe_pop_front(n);
+ }
+ (Some(NotFromSet(out)), buf.is_empty())
+ } else {
+ let c = buf.pop_front_char().expect("empty buffer in queue");
+ (Some(FromSet(c)), buf.is_empty())
+ }
+ },
+ };
+
+ // Unborrow self for this part.
+ if now_empty {
+ self.buffers.pop_front();
+ }
+
+ result
+ }
+
+ /// Consume bytes matching the pattern, using a custom comparison function `eq`.
+ ///
+ /// Returns `Some(true)` if there is a match, `Some(false)` if there is no match, or `None` if
+ /// it wasn't possible to know (more data is needed).
+ ///
+ /// The custom comparison function is used elsewhere to compare ascii-case-insensitively.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # extern crate markup5ever;
+ /// # #[macro_use] extern crate tendril;
+ /// # fn main() {
+ /// use markup5ever::buffer_queue::{BufferQueue};
+ ///
+ /// let mut queue = BufferQueue::new();
+ /// queue.push_back(format_tendril!("testtext"));
+ /// let test_str = "test";
+ /// assert_eq!(queue.eat("test", |&a, &b| a == b), Some(true));
+ /// assert_eq!(queue.eat("text", |&a, &b| a == b), Some(true));
+ /// assert!(queue.is_empty());
+ /// # }
+ /// ```
+ pub fn eat<F: Fn(&u8, &u8) -> bool>(&mut self, pat: &str, eq: F) -> Option<bool> {
+ let mut buffers_exhausted = 0;
+ let mut consumed_from_last = 0;
+
+ self.buffers.front()?;
+
+ for pattern_byte in pat.bytes() {
+ if buffers_exhausted >= self.buffers.len() {
+ return None;
+ }
+ let buf = &self.buffers[buffers_exhausted];
+
+ if !eq(&buf.as_bytes()[consumed_from_last], &pattern_byte) {
+ return Some(false);
+ }
+
+ consumed_from_last += 1;
+ if consumed_from_last >= buf.len() {
+ buffers_exhausted += 1;
+ consumed_from_last = 0;
+ }
+ }
+
+ // We have a match. Commit changes to the BufferQueue.
+ for _ in 0..buffers_exhausted {
+ self.buffers.pop_front();
+ }
+
+ match self.buffers.front_mut() {
+ None => assert_eq!(consumed_from_last, 0),
+ Some(ref mut buf) => buf.pop_front(consumed_from_last as u32),
+ }
+
+ Some(true)
+ }
+}
+
+#[cfg(test)]
+#[allow(non_snake_case)]
+mod test {
+ use tendril::SliceExt;
+
+ use super::BufferQueue;
+ use super::SetResult::{FromSet, NotFromSet};
+
+ #[test]
+ fn smoke_test() {
+ let mut bq = BufferQueue::new();
+ assert_eq!(bq.peek(), None);
+ assert_eq!(bq.next(), None);
+
+ bq.push_back("abc".to_tendril());
+ assert_eq!(bq.peek(), Some('a'));
+ assert_eq!(bq.next(), Some('a'));
+ assert_eq!(bq.peek(), Some('b'));
+ assert_eq!(bq.peek(), Some('b'));
+ assert_eq!(bq.next(), Some('b'));
+ assert_eq!(bq.peek(), Some('c'));
+ assert_eq!(bq.next(), Some('c'));
+ assert_eq!(bq.peek(), None);
+ assert_eq!(bq.next(), None);
+ }
+
+ #[test]
+ fn can_unconsume() {
+ let mut bq = BufferQueue::new();
+ bq.push_back("abc".to_tendril());
+ assert_eq!(bq.next(), Some('a'));
+
+ bq.push_front("xy".to_tendril());
+ assert_eq!(bq.next(), Some('x'));
+ assert_eq!(bq.next(), Some('y'));
+ assert_eq!(bq.next(), Some('b'));
+ assert_eq!(bq.next(), Some('c'));
+ assert_eq!(bq.next(), None);
+ }
+
+ #[test]
+ fn can_pop_except_set() {
+ let mut bq = BufferQueue::new();
+ bq.push_back("abc&def".to_tendril());
+ let mut pop = || bq.pop_except_from(small_char_set!('&'));
+ assert_eq!(pop(), Some(NotFromSet("abc".to_tendril())));
+ assert_eq!(pop(), Some(FromSet('&')));
+ assert_eq!(pop(), Some(NotFromSet("def".to_tendril())));
+ assert_eq!(pop(), None);
+ }
+
+ #[test]
+ fn can_eat() {
+ // This is not very comprehensive. We rely on the tokenizer
+ // integration tests for more thorough testing with many
+ // different input buffer splits.
+ let mut bq = BufferQueue::new();
+ bq.push_back("a".to_tendril());
+ bq.push_back("bc".to_tendril());
+ assert_eq!(bq.eat("abcd", u8::eq_ignore_ascii_case), None);
+ assert_eq!(bq.eat("ax", u8::eq_ignore_ascii_case), Some(false));
+ assert_eq!(bq.eat("ab", u8::eq_ignore_ascii_case), Some(true));
+ assert_eq!(bq.next(), Some('c'));
+ assert_eq!(bq.next(), None);
+ }
+}
diff --git a/vendor/markup5ever/util/smallcharset.rs b/vendor/markup5ever/util/smallcharset.rs
new file mode 100644
index 000000000..957dad730
--- /dev/null
+++ b/vendor/markup5ever/util/smallcharset.rs
@@ -0,0 +1,90 @@
+// Copyright 2014-2017 The html5ever Project Developers. See the
+// COPYRIGHT file at the top-level directory of this distribution.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! This module contains a single struct [`SmallCharSet`]. See its documentation for details.
+//!
+//! [`SmallCharSet`]: struct.SmallCharSet.html
+
+/// Represents a set of "small characters", those with Unicode scalar
+/// values less than 64.
+///
+/// This is stored as a bitmap, with 1 bit for each value.
+#[derive(Debug, Eq, PartialEq, Clone, Copy, Hash)]
+pub struct SmallCharSet {
+ pub bits: u64,
+}
+
+impl SmallCharSet {
+ /// Checks whether a character (u8 value below 64) is stored in the SmallCharSet.
+ ///
+ /// # Examples
+ ///
+ /// ```ignore
+ /// # use markup5ever::SmallCharSet;
+ /// let set = SmallCharSet {
+ /// bits: 0b00000000_01000000_00000100_00000000_00000000_00000000_00010000_00000000
+ /// };
+ /// assert!(set.contains(64));
+ /// assert!(set.contains(b'6')); // `b'6'` is the same as 64u8
+ /// ```
+ #[inline]
+ fn contains(&self, n: u8) -> bool {
+ 0 != (self.bits & (1 << (n as usize)))
+ }
+
+ /// Count the number of bytes of characters at the beginning of `buf` which are not in the set.
+ ///
+ /// This functionality is used in [`BufferQueue::pop_except_from`].
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # #[macro_use] extern crate markup5ever;
+ /// # fn main() {
+ /// let set = small_char_set!(48 49 50); // '0' '1' '2'
+ /// // `test` is 4 chars, ๐Ÿ˜ is 4 chars, then we meet a character in the set
+ /// let test_str = "test๐Ÿ˜01232afd";
+ /// assert_eq!(set.nonmember_prefix_len(test_str), 8);
+ /// # }
+ /// ```
+ ///
+ /// [`BufferQueue::pop_except_from`]: buffer_queue/struct.BufferQueue.html#method.pop_except_from
+ pub fn nonmember_prefix_len(&self, buf: &str) -> u32 {
+ let mut n = 0;
+ for b in buf.bytes() {
+ if b >= 64 || !self.contains(b) {
+ n += 1;
+ } else {
+ break;
+ }
+ }
+ n
+ }
+}
+
+#[cfg(test)]
+mod test {
+ use std::iter::repeat;
+
+ #[test]
+ fn nonmember_prefix() {
+ for &c in ['&', '\0'].iter() {
+ for x in 0..48u32 {
+ for y in 0..48u32 {
+ let mut s = repeat("x").take(x as usize).collect::<String>();
+ s.push(c);
+ s.push_str(&repeat("x").take(y as usize).collect::<String>());
+ let set = small_char_set!('&' '\0');
+
+ assert_eq!(x, set.nonmember_prefix_len(&s));
+ }
+ }
+ }
+ }
+}