New upstream version 1.58.1+dfsg1

[rustc.git] / vendor / pulldown-cmark-0.7.2 / src / escape.rs

// Copyright 2015 Google Inc. All rights reserved.\r
//\r
// Permission is hereby granted, free of charge, to any person obtaining a copy\r
// of this software and associated documentation files (the "Software"), to deal\r
// in the Software without restriction, including without limitation the rights\r
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\r
// copies of the Software, and to permit persons to whom the Software is\r
// furnished to do so, subject to the following conditions:\r
//\r
// The above copyright notice and this permission notice shall be included in\r
// all copies or substantial portions of the Software.\r
//\r
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN\r
// THE SOFTWARE.\r
\r
//! Utility functions for HTML escaping\r
\r
use std::io;\r
use std::str::from_utf8;\r
\r
use crate::html::StrWrite;\r
\r
#[rustfmt::skip]\r
static HREF_SAFE: [u8; 128] = [\r
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
    0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,\r
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1,\r
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\r
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1,\r
    0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\r
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0,\r
];\r
\r
static HEX_CHARS: &[u8] = b"0123456789ABCDEF";\r
static AMP_ESCAPE: &str = "&";\r
static SLASH_ESCAPE: &str = "'";\r
\r
pub(crate) fn escape_href<W>(mut w: W, s: &str) -> io::Result<()>\r
where\r
    W: StrWrite,\r
{\r
    let bytes = s.as_bytes();\r
    let mut mark = 0;\r
    for i in 0..bytes.len() {\r
        let c = bytes[i];\r
        if c >= 0x80 || HREF_SAFE[c as usize] == 0 {\r
            // character needing escape\r
\r
            // write partial substring up to mark\r
            if mark < i {\r
                w.write_str(&s[mark..i])?;\r
            }\r
            match c {\r
                b'&' => {\r
                    w.write_str(AMP_ESCAPE)?;\r
                }\r
                b'\'' => {\r
                    w.write_str(SLASH_ESCAPE)?;\r
                }\r
                _ => {\r
                    let mut buf = [0u8; 3];\r
                    buf[0] = b'%';\r
                    buf[1] = HEX_CHARS[((c as usize) >> 4) & 0xF];\r
                    buf[2] = HEX_CHARS[(c as usize) & 0xF];\r
                    let escaped = from_utf8(&buf).unwrap();\r
                    w.write_str(escaped)?;\r
                }\r
            }\r
            mark = i + 1; // all escaped characters are ASCII\r
        }\r
    }\r
    w.write_str(&s[mark..])\r
}\r
\r
const fn create_html_escape_table() -> [u8; 256] {\r
    let mut table = [0; 256];\r
    table[b'"' as usize] = 1;\r
    table[b'&' as usize] = 2;\r
    table[b'<' as usize] = 3;\r
    table[b'>' as usize] = 4;\r
    table\r
}\r
\r
static HTML_ESCAPE_TABLE: [u8; 256] = create_html_escape_table();\r
\r
static HTML_ESCAPES: [&'static str; 5] = ["", "&quot;", "&amp;", "&lt;", "&gt;"];\r
\r
/// Writes the given string to the Write sink, replacing special HTML bytes\r
/// (<, >, &, ") by escape sequences.\r
pub(crate) fn escape_html<W: StrWrite>(w: W, s: &str) -> io::Result<()> {\r
    #[cfg(all(target_arch = "x86_64", feature = "simd"))]\r
    {\r
        simd::escape_html(w, s)\r
    }\r
    #[cfg(not(all(target_arch = "x86_64", feature = "simd")))]\r
    {\r
        escape_html_scalar(w, s)\r
    }\r
}\r
\r
fn escape_html_scalar<W: StrWrite>(mut w: W, s: &str) -> io::Result<()> {\r
    let bytes = s.as_bytes();\r
    let mut mark = 0;\r
    let mut i = 0;\r
    while i < s.len() {\r
        match bytes[i..]\r
            .iter()\r
            .position(|&c| HTML_ESCAPE_TABLE[c as usize] != 0)\r
        {\r
            Some(pos) => {\r
                i += pos;\r
            }\r
            None => break,\r
        }\r
        let c = bytes[i];\r
        let escape = HTML_ESCAPE_TABLE[c as usize];\r
        let escape_seq = HTML_ESCAPES[escape as usize];\r
        w.write_str(&s[mark..i])?;\r
        w.write_str(escape_seq)?;\r
        i += 1;\r
        mark = i; // all escaped characters are ASCII\r
    }\r
    w.write_str(&s[mark..])\r
}\r
\r
#[cfg(all(target_arch = "x86_64", feature = "simd"))]\r
mod simd {\r
    use crate::html::StrWrite;\r
    use std::arch::x86_64::*;\r
    use std::io;\r
    use std::mem::size_of;\r
\r
    const VECTOR_SIZE: usize = size_of::<__m128i>();\r
\r
    pub(crate) fn escape_html<W: StrWrite>(mut w: W, s: &str) -> io::Result<()> {\r
        // The SIMD accelerated code uses the PSHUFB instruction, which is part\r
        // of the SSSE3 instruction set. Further, we can only use this code if\r
        // the buffer is at least one VECTOR_SIZE in length to prevent reading\r
        // out of bounds. If either of these conditions is not met, we fall back\r
        // to scalar code.\r
        if is_x86_feature_detected!("ssse3") && s.len() >= VECTOR_SIZE {\r
            let bytes = s.as_bytes();\r
            let mut mark = 0;\r
\r
            unsafe {\r
                foreach_special_simd(bytes, 0, |i| {\r
                    let escape_ix = *bytes.get_unchecked(i) as usize;\r
                    let replacement =\r
                        super::HTML_ESCAPES[super::HTML_ESCAPE_TABLE[escape_ix] as usize];\r
                    w.write_str(&s.get_unchecked(mark..i))?;\r
                    mark = i + 1; // all escaped characters are ASCII\r
                    w.write_str(replacement)\r
                })?;\r
                w.write_str(&s.get_unchecked(mark..))\r
            }\r
        } else {\r
            super::escape_html_scalar(w, s)\r
        }\r
    }\r
\r
    /// Creates the lookup table for use in `compute_mask`.\r
    const fn create_lookup() -> [u8; 16] {\r
        let mut table = [0; 16];\r
        table[(b'<' & 0x0f) as usize] = b'<';\r
        table[(b'>' & 0x0f) as usize] = b'>';\r
        table[(b'&' & 0x0f) as usize] = b'&';\r
        table[(b'"' & 0x0f) as usize] = b'"';\r
        table[0] = 0b0111_1111;\r
        table\r
    }\r
\r
    #[target_feature(enable = "ssse3")]\r
    /// Computes a byte mask at given offset in the byte buffer. Its first 16 (least significant)\r
    /// bits correspond to whether there is an HTML special byte (&, <, ", >) at the 16 bytes\r
    /// `bytes[offset..]`. For example, the mask `(1 << 3)` states that there is an HTML byte\r
    /// at `offset + 3`. It is only safe to call this function when\r
    /// `bytes.len() >= offset + VECTOR_SIZE`.\r
    unsafe fn compute_mask(bytes: &[u8], offset: usize) -> i32 {\r
        debug_assert!(bytes.len() >= offset + VECTOR_SIZE);\r
\r
        let table = create_lookup();\r
        let lookup = _mm_loadu_si128(table.as_ptr() as *const __m128i);\r
        let raw_ptr = bytes.as_ptr().offset(offset as isize) as *const __m128i;\r
\r
        // Load the vector from memory.\r
        let vector = _mm_loadu_si128(raw_ptr);\r
        // We take the least significant 4 bits of every byte and use them as indices\r
        // to map into the lookup vector.\r
        // Note that shuffle maps bytes with their most significant bit set to lookup[0].\r
        // Bytes that share their lower nibble with an HTML special byte get mapped to that\r
        // corresponding special byte. Note that all HTML special bytes have distinct lower\r
        // nibbles. Other bytes either get mapped to 0 or 127.\r
        let expected = _mm_shuffle_epi8(lookup, vector);\r
        // We compare the original vector to the mapped output. Bytes that shared a lower\r
        // nibble with an HTML special byte match *only* if they are that special byte. Bytes\r
        // that have either a 0 lower nibble or their most significant bit set were mapped to\r
        // 127 and will hence never match. All other bytes have non-zero lower nibbles but\r
        // were mapped to 0 and will therefore also not match.\r
        let matches = _mm_cmpeq_epi8(expected, vector);\r
\r
        // Translate matches to a bitmask, where every 1 corresponds to a HTML special character\r
        // and a 0 is a non-HTML byte.\r
        _mm_movemask_epi8(matches)\r
    }\r
\r
    /// Calls the given function with the index of every byte in the given byteslice\r
    /// that is either ", &, <, or > and for no other byte.\r
    /// Make sure to only call this when `bytes.len() >= 16`, undefined behaviour may\r
    /// occur otherwise.\r
    #[target_feature(enable = "ssse3")]\r
    unsafe fn foreach_special_simd<F>(\r
        bytes: &[u8],\r
        mut offset: usize,\r
        mut callback: F,\r
    ) -> io::Result<()>\r
    where\r
        F: FnMut(usize) -> io::Result<()>,\r
    {\r
        // The strategy here is to walk the byte buffer in chunks of VECTOR_SIZE (16)\r
        // bytes at a time starting at the given offset. For each chunk, we compute a\r
        // a bitmask indicating whether the corresponding byte is a HTML special byte.\r
        // We then iterate over all the 1 bits in this mask and call the callback function\r
        // with the corresponding index in the buffer.\r
        // When the number of HTML special bytes in the buffer is relatively low, this\r
        // allows us to quickly go through the buffer without a lookup and for every\r
        // single byte.\r
\r
        debug_assert!(bytes.len() >= VECTOR_SIZE);\r
        let upperbound = bytes.len() - VECTOR_SIZE;\r
        while offset < upperbound {\r
            let mut mask = compute_mask(bytes, offset);\r
            while mask != 0 {\r
                let ix = mask.trailing_zeros();\r
                callback(offset + ix as usize)?;\r
                mask ^= mask & -mask;\r
            }\r
            offset += VECTOR_SIZE;\r
        }\r
\r
        // Final iteration. We align the read with the end of the slice and\r
        // shift off the bytes at start we have already scanned.\r
        let mut mask = compute_mask(bytes, upperbound);\r
        mask >>= offset - upperbound;\r
        while mask != 0 {\r
            let ix = mask.trailing_zeros();\r
            callback(offset + ix as usize)?;\r
            mask ^= mask & -mask;\r
        }\r
        Ok(())\r
    }\r
\r
    #[cfg(test)]\r
    mod html_scan_tests {\r
        #[test]\r
        fn multichunk() {\r
            let mut vec = Vec::new();\r
            unsafe {\r
                super::foreach_special_simd("&aXaaaa.a'aa9a<>aab&".as_bytes(), 0, |ix| {\r
                    Ok(vec.push(ix))\r
                })\r
                .unwrap();\r
            }\r
            assert_eq!(vec, vec![0, 14, 15, 19]);\r
        }\r
\r
        // only match these bytes, and when we match them, match them VECTOR_SIZE times\r
        #[test]\r
        fn only_right_bytes_matched() {\r
            for b in 0..255u8 {\r
                let right_byte = b == b'&' || b == b'<' || b == b'>' || b == b'"';\r
                let vek = vec![b; super::VECTOR_SIZE];\r
                let mut match_count = 0;\r
                unsafe {\r
                    super::foreach_special_simd(&vek, 0, |_| {\r
                        match_count += 1;\r
                        Ok(())\r
                    })\r
                    .unwrap();\r
                }\r
                assert!((match_count > 0) == (match_count == super::VECTOR_SIZE));\r
                assert_eq!(\r
                    (match_count == super::VECTOR_SIZE),\r
                    right_byte,\r
                    "match_count: {}, byte: {:?}",\r
                    match_count,\r
                    b as char\r
                );\r
            }\r
        }\r
    }\r
}\r