css-to-xpath 0.3.0

//! The XML 1.0 `NCName` production, which is what a CSS namespace
//! prefix has to be to survive into the XPath this crate emits.
//!
//! A namespace prefix is passed through into a node test (`svg|rect`
//! becomes `svg:rect`) because XPath 1.0 has no way to resolve one
//! without the namespace URI, which this crate never sees. So a prefix
//! that cannot be written as an XPath name has nowhere to go and errors,
//! and the predicate here is what decides which those are. Local names
//! need no such test: one that cannot be a name test folds into a
//! `local-name()` comparison instead, so they stay on the deliberately
//! conservative ASCII-only [`is_safe_name`].
//!
//! [`is_safe_name`]: super::xpath_expr::is_safe_name
//!
//! # Which `NCName`
//!
//! An XPath 1.0 `NCName` is an XML 1.0 `Name` without a colon, and XML
//! 1.0 defined `Name` by the character tables in its Appendix B:
//! `Letter` (`BaseChar | Ideographic`), `Digit`, `CombiningChar` and
//! `Extender`. XML 1.0 Fifth Edition later replaced those tables with a
//! much broader set of ranges — but that revision is of XML, not of
//! XPath 1.0, and engines split on it. The tables below are the original
//! ones, which is both the definition XPath 1.0 cites and a subset of
//! the Fifth Edition set, so a prefix accepted here parses under either
//! reading. Concretely: libxml2 parses XPath names with the original
//! tables and rejects `nsɂ:e` (U+0242), while sxd-xpath (which the test
//! suite evaluates through) implements the Fifth Edition set and accepts
//! it. Emitting only the intersection keeps a translated prefix from
//! turning into a parse error one engine reports and the other does not.
//!
//! Erring narrow is safe in a way erring broad is not: a prefix rejected
//! here is reported as an unsupported construct, which is what every
//! non-ASCII prefix used to get, whereas one accepted here and refused
//! by the evaluator is a parse failure the caller cannot attribute.

use std::cmp::Ordering;

/// `BaseChar | Ideographic`, minus the ASCII letters that
/// [`is_name_start`] tests directly. Sorted and disjoint, so membership
/// is a binary search.
#[rustfmt::skip]
static LETTERS: &[(u32, u32)] = &[
    (0x00C0, 0x00D6), (0x00D8, 0x00F6), (0x00F8, 0x0131), (0x0134, 0x013E), (0x0141, 0x0148),
    (0x014A, 0x017E), (0x0180, 0x01C3), (0x01CD, 0x01F0), (0x01F4, 0x01F5), (0x01FA, 0x0217),
    (0x0250, 0x02A8), (0x02BB, 0x02C1), (0x0386, 0x0386), (0x0388, 0x038A), (0x038C, 0x038C),
    (0x038E, 0x03A1), (0x03A3, 0x03CE), (0x03D0, 0x03D6), (0x03DA, 0x03DA), (0x03DC, 0x03DC),
    (0x03DE, 0x03DE), (0x03E0, 0x03E0), (0x03E2, 0x03F3), (0x0401, 0x040C), (0x040E, 0x044F),
    (0x0451, 0x045C), (0x045E, 0x0481), (0x0490, 0x04C4), (0x04C7, 0x04C8), (0x04CB, 0x04CC),
    (0x04D0, 0x04EB), (0x04EE, 0x04F5), (0x04F8, 0x04F9), (0x0531, 0x0556), (0x0559, 0x0559),
    (0x0561, 0x0586), (0x05D0, 0x05EA), (0x05F0, 0x05F2), (0x0621, 0x063A), (0x0641, 0x064A),
    (0x0671, 0x06B7), (0x06BA, 0x06BE), (0x06C0, 0x06CE), (0x06D0, 0x06D3), (0x06D5, 0x06D5),
    (0x06E5, 0x06E6), (0x0905, 0x0939), (0x093D, 0x093D), (0x0958, 0x0961), (0x0985, 0x098C),
    (0x098F, 0x0990), (0x0993, 0x09A8), (0x09AA, 0x09B0), (0x09B2, 0x09B2), (0x09B6, 0x09B9),
    (0x09DC, 0x09DD), (0x09DF, 0x09E1), (0x09F0, 0x09F1), (0x0A05, 0x0A0A), (0x0A0F, 0x0A10),
    (0x0A13, 0x0A28), (0x0A2A, 0x0A30), (0x0A32, 0x0A33), (0x0A35, 0x0A36), (0x0A38, 0x0A39),
    (0x0A59, 0x0A5C), (0x0A5E, 0x0A5E), (0x0A72, 0x0A74), (0x0A85, 0x0A8B), (0x0A8D, 0x0A8D),
    (0x0A8F, 0x0A91), (0x0A93, 0x0AA8), (0x0AAA, 0x0AB0), (0x0AB2, 0x0AB3), (0x0AB5, 0x0AB9),
    (0x0ABD, 0x0ABD), (0x0AE0, 0x0AE0), (0x0B05, 0x0B0C), (0x0B0F, 0x0B10), (0x0B13, 0x0B28),
    (0x0B2A, 0x0B30), (0x0B32, 0x0B33), (0x0B36, 0x0B39), (0x0B3D, 0x0B3D), (0x0B5C, 0x0B5D),
    (0x0B5F, 0x0B61), (0x0B85, 0x0B8A), (0x0B8E, 0x0B90), (0x0B92, 0x0B95), (0x0B99, 0x0B9A),
    (0x0B9C, 0x0B9C), (0x0B9E, 0x0B9F), (0x0BA3, 0x0BA4), (0x0BA8, 0x0BAA), (0x0BAE, 0x0BB5),
    (0x0BB7, 0x0BB9), (0x0C05, 0x0C0C), (0x0C0E, 0x0C10), (0x0C12, 0x0C28), (0x0C2A, 0x0C33),
    (0x0C35, 0x0C39), (0x0C60, 0x0C61), (0x0C85, 0x0C8C), (0x0C8E, 0x0C90), (0x0C92, 0x0CA8),
    (0x0CAA, 0x0CB3), (0x0CB5, 0x0CB9), (0x0CDE, 0x0CDE), (0x0CE0, 0x0CE1), (0x0D05, 0x0D0C),
    (0x0D0E, 0x0D10), (0x0D12, 0x0D28), (0x0D2A, 0x0D39), (0x0D60, 0x0D61), (0x0E01, 0x0E2E),
    (0x0E30, 0x0E30), (0x0E32, 0x0E33), (0x0E40, 0x0E45), (0x0E81, 0x0E82), (0x0E84, 0x0E84),
    (0x0E87, 0x0E88), (0x0E8A, 0x0E8A), (0x0E8D, 0x0E8D), (0x0E94, 0x0E97), (0x0E99, 0x0E9F),
    (0x0EA1, 0x0EA3), (0x0EA5, 0x0EA5), (0x0EA7, 0x0EA7), (0x0EAA, 0x0EAB), (0x0EAD, 0x0EAE),
    (0x0EB0, 0x0EB0), (0x0EB2, 0x0EB3), (0x0EBD, 0x0EBD), (0x0EC0, 0x0EC4), (0x0F40, 0x0F47),
    (0x0F49, 0x0F69), (0x10A0, 0x10C5), (0x10D0, 0x10F6), (0x1100, 0x1100), (0x1102, 0x1103),
    (0x1105, 0x1107), (0x1109, 0x1109), (0x110B, 0x110C), (0x110E, 0x1112), (0x113C, 0x113C),
    (0x113E, 0x113E), (0x1140, 0x1140), (0x114C, 0x114C), (0x114E, 0x114E), (0x1150, 0x1150),
    (0x1154, 0x1155), (0x1159, 0x1159), (0x115F, 0x1161), (0x1163, 0x1163), (0x1165, 0x1165),
    (0x1167, 0x1167), (0x1169, 0x1169), (0x116D, 0x116E), (0x1172, 0x1173), (0x1175, 0x1175),
    (0x119E, 0x119E), (0x11A8, 0x11A8), (0x11AB, 0x11AB), (0x11AE, 0x11AF), (0x11B7, 0x11B8),
    (0x11BA, 0x11BA), (0x11BC, 0x11C2), (0x11EB, 0x11EB), (0x11F0, 0x11F0), (0x11F9, 0x11F9),
    (0x1E00, 0x1E9B), (0x1EA0, 0x1EF9), (0x1F00, 0x1F15), (0x1F18, 0x1F1D), (0x1F20, 0x1F45),
    (0x1F48, 0x1F4D), (0x1F50, 0x1F57), (0x1F59, 0x1F59), (0x1F5B, 0x1F5B), (0x1F5D, 0x1F5D),
    (0x1F5F, 0x1F7D), (0x1F80, 0x1FB4), (0x1FB6, 0x1FBC), (0x1FBE, 0x1FBE), (0x1FC2, 0x1FC4),
    (0x1FC6, 0x1FCC), (0x1FD0, 0x1FD3), (0x1FD6, 0x1FDB), (0x1FE0, 0x1FEC), (0x1FF2, 0x1FF4),
    (0x1FF6, 0x1FFC), (0x2126, 0x2126), (0x212A, 0x212B), (0x212E, 0x212E), (0x2180, 0x2182),
    (0x3007, 0x3007), (0x3021, 0x3029), (0x3041, 0x3094), (0x30A1, 0x30FA), (0x3105, 0x312C),
    (0x4E00, 0x9FA5), (0xAC00, 0xD7A3),
];

/// `CombiningChar | Digit | Extender`, minus the ASCII digits. These may
/// follow the first character of a name but cannot be it.
#[rustfmt::skip]
static TRAILING: &[(u32, u32)] = &[
    (0x00B7, 0x00B7), (0x02D0, 0x02D1), (0x0300, 0x0345), (0x0360, 0x0361), (0x0387, 0x0387),
    (0x0483, 0x0486), (0x0591, 0x05A1), (0x05A3, 0x05B9), (0x05BB, 0x05BD), (0x05BF, 0x05BF),
    (0x05C1, 0x05C2), (0x05C4, 0x05C4), (0x0640, 0x0640), (0x064B, 0x0652), (0x0660, 0x0669),
    (0x0670, 0x0670), (0x06D6, 0x06E4), (0x06E7, 0x06E8), (0x06EA, 0x06ED), (0x06F0, 0x06F9),
    (0x0901, 0x0903), (0x093C, 0x093C), (0x093E, 0x094D), (0x0951, 0x0954), (0x0962, 0x0963),
    (0x0966, 0x096F), (0x0981, 0x0983), (0x09BC, 0x09BC), (0x09BE, 0x09C4), (0x09C7, 0x09C8),
    (0x09CB, 0x09CD), (0x09D7, 0x09D7), (0x09E2, 0x09E3), (0x09E6, 0x09EF), (0x0A02, 0x0A02),
    (0x0A3C, 0x0A3C), (0x0A3E, 0x0A42), (0x0A47, 0x0A48), (0x0A4B, 0x0A4D), (0x0A66, 0x0A71),
    (0x0A81, 0x0A83), (0x0ABC, 0x0ABC), (0x0ABE, 0x0AC5), (0x0AC7, 0x0AC9), (0x0ACB, 0x0ACD),
    (0x0AE6, 0x0AEF), (0x0B01, 0x0B03), (0x0B3C, 0x0B3C), (0x0B3E, 0x0B43), (0x0B47, 0x0B48),
    (0x0B4B, 0x0B4D), (0x0B56, 0x0B57), (0x0B66, 0x0B6F), (0x0B82, 0x0B83), (0x0BBE, 0x0BC2),
    (0x0BC6, 0x0BC8), (0x0BCA, 0x0BCD), (0x0BD7, 0x0BD7), (0x0BE7, 0x0BEF), (0x0C01, 0x0C03),
    (0x0C3E, 0x0C44), (0x0C46, 0x0C48), (0x0C4A, 0x0C4D), (0x0C55, 0x0C56), (0x0C66, 0x0C6F),
    (0x0C82, 0x0C83), (0x0CBE, 0x0CC4), (0x0CC6, 0x0CC8), (0x0CCA, 0x0CCD), (0x0CD5, 0x0CD6),
    (0x0CE6, 0x0CEF), (0x0D02, 0x0D03), (0x0D3E, 0x0D43), (0x0D46, 0x0D48), (0x0D4A, 0x0D4D),
    (0x0D57, 0x0D57), (0x0D66, 0x0D6F), (0x0E31, 0x0E31), (0x0E34, 0x0E3A), (0x0E46, 0x0E4E),
    (0x0E50, 0x0E59), (0x0EB1, 0x0EB1), (0x0EB4, 0x0EB9), (0x0EBB, 0x0EBC), (0x0EC6, 0x0EC6),
    (0x0EC8, 0x0ECD), (0x0ED0, 0x0ED9), (0x0F18, 0x0F19), (0x0F20, 0x0F29), (0x0F35, 0x0F35),
    (0x0F37, 0x0F37), (0x0F39, 0x0F39), (0x0F3E, 0x0F3F), (0x0F71, 0x0F84), (0x0F86, 0x0F8B),
    (0x0F90, 0x0F95), (0x0F97, 0x0F97), (0x0F99, 0x0FAD), (0x0FB1, 0x0FB7), (0x0FB9, 0x0FB9),
    (0x20D0, 0x20DC), (0x20E1, 0x20E1), (0x3005, 0x3005), (0x302A, 0x302F), (0x3031, 0x3035),
    (0x3099, 0x309A), (0x309D, 0x309E), (0x30FC, 0x30FE),
];

/// Whether `name` is an XML 1.0 `NCName`, and so can be written into an
/// XPath expression as a namespace prefix.
pub(crate) fn is_ncname(name: &str) -> bool {
    let mut chars = name.chars();
    let Some(first) = chars.next() else {
        return false;
    };
    is_name_start(first) && chars.all(is_name_char)
}

/// The `(Letter | '_')` a name has to begin with.
fn is_name_start(c: char) -> bool {
    if c.is_ascii() {
        return c.is_ascii_alphabetic() || c == '_';
    }
    in_table(c, LETTERS)
}

/// `NameChar` minus the colon: a start character, or one of the
/// combining marks, digits, extenders, `.` and `-` that may only follow.
fn is_name_char(c: char) -> bool {
    if c.is_ascii() {
        return c.is_ascii_alphanumeric() || matches!(c, '_' | '.' | '-');
    }
    in_table(c, LETTERS) || in_table(c, TRAILING)
}

fn in_table(c: char, table: &[(u32, u32)]) -> bool {
    let c = c as u32;
    table
        .binary_search_by(|&(lo, hi)| {
            if hi < c {
                Ordering::Less
            } else if lo > c {
                Ordering::Greater
            } else {
                Ordering::Equal
            }
        })
        .is_ok()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn ascii_names() {
        assert!(is_ncname("div"));
        assert!(is_ncname("_x"));
        assert!(is_ncname("a-b.c_1"));
        assert!(!is_ncname(""));
        assert!(!is_ncname("1a"));
        assert!(!is_ncname("-a"));
        assert!(!is_ncname(".a"));
        assert!(!is_ncname("di[v"));
        assert!(!is_ncname("a b"));
        // A prefix is exactly one name: the colon that joins it to a
        // local part is not part of it.
        assert!(!is_ncname("a:b"));
    }

    #[test]
    fn non_ascii_names() {
        assert!(is_ncname("nsé"));
        assert!(is_ncname("é"));
        assert!(is_ncname("Ελληνικά"));
        assert!(is_ncname("русский"));
        assert!(is_ncname("中文"));
        // U+00B7 MIDDLE DOT is an Extender, so it may follow but not
        // lead; U+0301 COMBINING ACUTE ACCENT is a CombiningChar and
        // behaves the same way.
        assert!(is_ncname("a·b"));
        assert!(!is_ncname("·a"));
        assert!(is_ncname("a\u{301}"));
        assert!(!is_ncname("\u{301}a"));
        // U+00A0 NO-BREAK SPACE is in none of the tables, and neither
        // is U+0242, which only the Fifth Edition tables added.
        assert!(!is_ncname("di\u{a0}v"));
        assert!(!is_ncname("ns\u{242}"));
        // Nor is anything outside the BMP: the tables predate it.
        assert!(!is_ncname("\u{10330}"));
    }

    /// Both tables are sorted, disjoint and non-adjacent — what the
    /// binary search in `in_table` assumes, and what keeps each range a
    /// canonical one rather than a split of its neighbour.
    #[test]
    fn tables_are_sorted_and_disjoint() {
        for table in [LETTERS, TRAILING] {
            for pair in table.windows(2) {
                let ((lo, hi), (next_lo, _)) = (pair[0], pair[1]);
                assert!(lo <= hi, "range {lo:#X}-{hi:#X} is inverted");
                assert!(
                    hi + 1 < next_lo,
                    "range {lo:#X}-{hi:#X} touches {next_lo:#X}"
                );
            }
        }
        // The two tables partition their characters, so a trailing-only
        // character is never also a letter.
        for &(lo, hi) in TRAILING {
            for c in lo..=hi {
                let c = char::from_u32(c).expect("table holds scalar values");
                assert!(!in_table(c, LETTERS), "{c:?} is in both tables");
            }
        }
    }
}