~ knotless Search/
↑↓ move↵ open⇧↵ all results
0
0
427 lines · 13.7 KB Raw History
//! The lexicon string formats (`atproto/lexicon.md`), as `spec/VALIDATION.md`
//! says the server holds them: atproto's syntax vectors, but where the
//! reference differs (`cid`, `uri`).

use pds_repo::data::{
    valid_at_identifier, valid_cid_string, valid_did, valid_handle, valid_nsid, valid_rkey,
};

/// Whether `s` is a string of `format`; a format the server does not know takes any string.
pub fn valid(format: &str, s: &str) -> bool {
    match format {
        "at-identifier" => valid_at_identifier(s),
        "did" => valid_did(s),
        "handle" => valid_handle(s),
        "nsid" => valid_nsid(s),
        "record-key" => valid_rkey(s),
        "space-ref" => pds_space::SpaceRef::parse(s).is_some(),
        "tid" => pds_repo::valid_tid(s),
        "cid" => valid_cid_string(s),
        "at-uri" => valid_at_uri(s),
        "uri" => valid_uri(s),
        "datetime" => valid_datetime(s),
        "language" => valid_language(s),
        _ => true,
    }
}

/// An AT URI as lexicons use them: `at://`, a DID or handle, then
/// optionally a collection's NSID and then a record key; no trailing slash,
/// query or fragment, and at most 8 KB.
pub fn valid_at_uri(s: &str) -> bool {
    let Some(rest) = s.strip_prefix("at://").filter(|_| s.len() <= 8 * 1024) else {
        return false;
    };
    let mut parts = rest.split('/');
    let authority = parts.next().unwrap_or_default();
    valid_at_identifier(authority)
        && parts.next().is_none_or(|collection| {
            valid_nsid(collection)
                && parts
                    .next()
                    .is_none_or(|rkey| valid_rkey(rkey) && parts.next().is_none())
        })
}

/// What JavaScript's `\s` matches.
fn js_space(c: char) -> bool {
    matches!(
        c,
        '\t' | '\n' | '\u{b}' | '\u{c}' | '\r' | ' ' | '\u{a0}' | '\u{1680}' | '\u{2000}'
            ..='\u{200a}'
                | '\u{2028}'
                | '\u{2029}'
                | '\u{202f}'
                | '\u{205f}'
                | '\u{3000}'
                | '\u{feff}'
    )
}

/// A URI as the reference takes one: what `^\w+:(?:\/\/)?[^\s/][^\s]*$`
/// matches, `\w` being ASCII letters, digits and `_`, of any length.
pub fn valid_uri(s: &str) -> bool {
    let Some((scheme, rest)) = s.split_once(':') else {
        return false;
    };
    if scheme.is_empty()
        || !scheme
            .bytes()
            .all(|c| c.is_ascii_alphanumeric() || c == b'_')
        || rest.chars().any(js_space)
    {
        return false;
    }
    // `[^\s/]` after the scheme, or after a `//` that follows it.
    let after = |r: &str| r.chars().next().is_some_and(|c| c != '/');
    after(rest) || rest.strip_prefix("//").is_some_and(after)
}

/// The days from 1970-01-01 to the first of `month` in `year`, proleptic Gregorian.
fn days_from_civil(year: i64, month: i64) -> i64 {
    let y = if month <= 2 { year - 1 } else { year };
    let era = y.div_euclid(400);
    let yoe = y - era * 400;
    let mp = (month + 9) % 12;
    let doy = (153 * mp + 2) / 5;
    let doe = yoe * 365 + yoe / 4 - yoe / 100 + doy;
    era * 146_097 + doe - 719_468
}

/// The year of the day `days` after 1970-01-01, proleptic Gregorian.
fn year_of(days: i64) -> i64 {
    let z = days + 719_468;
    let era = z.div_euclid(146_097);
    let doe = z - era * 146_097;
    let yoe = (doe - doe / 1460 + doe / 36_524 - doe / 146_096) / 365;
    let doy = doe - (365 * yoe + yoe / 4 - yoe / 100);
    let mp = (5 * doy + 2) / 153;
    let month = if mp < 10 { mp + 3 } else { mp - 9 };
    yoe + era * 400 + i64::from(month <= 2)
}

/// A datetime: `YYYY-MM-DDTHH:MM:SS`, an optional fraction, then `Z` or an
/// offset `±HH:MM` other than `-00:00`; at most 64 characters, no leap
/// second, the day held to 01–31 but not to its month, and its instant in
/// UTC in the years 0000 to 9999.
pub fn valid_datetime(s: &str) -> bool {
    let b = s.as_bytes();
    if b.len() > 64 || b.len() < 20 || s.ends_with("-00:00") {
        return false;
    }
    let num = |from: usize, to: usize| -> Option<i64> {
        b[from..to].iter().try_fold(0i64, |n, c| {
            c.is_ascii_digit().then(|| n * 10 + i64::from(c - b'0'))
        })
    };
    let punct = [(4, b'-'), (7, b'-'), (10, b'T'), (13, b':'), (16, b':')];
    if punct.iter().any(|&(i, c)| b[i] != c) {
        return false;
    }
    let (Some(year), Some(month), Some(day), Some(hour), Some(minute), Some(second)) = (
        num(0, 4),
        num(5, 7),
        num(8, 10),
        num(11, 13),
        num(14, 16),
        num(17, 19),
    ) else {
        return false;
    };
    if !(1..=12).contains(&month)
        || !(1..=31).contains(&day)
        || hour > 23
        || minute > 59
        || second > 59
    {
        return false;
    }
    let mut rest = &b[19..];
    if let Some(frac) = rest.strip_prefix(b".") {
        let digits = frac.iter().take_while(|c| c.is_ascii_digit()).count();
        if digits == 0 {
            return false;
        }
        rest = &frac[digits..];
    }
    let offset = match *rest {
        [b'Z'] => 0,
        [sign @ (b'+' | b'-'), h1, h2, b':', m1, m2] => {
            if ![h1, h2, m1, m2].iter().all(u8::is_ascii_digit) {
                return false;
            }
            let (h, m) = (
                i64::from(h1 - b'0') * 10 + i64::from(h2 - b'0'),
                i64::from(m1 - b'0') * 10 + i64::from(m2 - b'0'),
            );
            if h > 23 || m > 59 {
                return false;
            }
            if sign == b'+' {
                h * 60 + m
            } else {
                -(h * 60 + m)
            }
        }
        _ => return false,
    };
    // The instant, in minutes since the epoch; a day past its month's end runs on into the next.
    let minutes = (days_from_civil(year, month) + day - 1) * 1440 + hour * 60 + minute - offset;
    (0..=9999).contains(&year_of(minutes.div_euclid(1440)))
}

/// The irregular grandfathered tags of RFC 5646, taken only exactly as it
/// writes them; its grammar takes none of them.
const IRREGULAR: &[&str] = &[
    "en-GB-oed",
    "i-ami",
    "i-bnn",
    "i-default",
    "i-enochian",
    "i-hak",
    "i-klingon",
    "i-lux",
    "i-mingo",
    "i-navajo",
    "i-pwn",
    "i-tao",
    "i-tay",
    "i-tsu",
    "sgn-BE-FR",
    "sgn-BE-NL",
    "sgn-CH-DE",
];

/// A `Language-Tag` of RFC 5646 §2.1's grammar, with no variant or
/// extension singleton repeated, compared in any case (§4.1), as
/// `spec/VALIDATION.md` says: a primary language subtag of exactly 2 or 3
/// lower-case letters, later subtags in any case, private use alone from
/// `x` or `X`, and the irregular grandfathered tags exactly as written.
pub fn valid_language(s: &str) -> bool {
    if IRREGULAR.contains(&s) {
        return true;
    }
    let tags: Vec<&str> = s.split('-').collect();
    let n = tags.len();
    let alpha = |t: &str, len: std::ops::RangeInclusive<usize>| {
        len.contains(&t.len()) && t.bytes().all(|c| c.is_ascii_alphabetic())
    };
    let alnum = |t: &str, len: std::ops::RangeInclusive<usize>| {
        len.contains(&t.len()) && t.bytes().all(|c| c.is_ascii_alphanumeric())
    };
    // A private use subtag sequence from `i`: `x` and one or more of 1–8 alphanumerics, to the end.
    let private = |i: usize| {
        tags[i].eq_ignore_ascii_case("x")
            && i + 1 < n
            && tags[i + 1..].iter().all(|t| alnum(t, 1..=8))
    };
    if private(0) {
        return true;
    }
    if !((2..=3).contains(&tags[0].len()) && tags[0].bytes().all(|c| c.is_ascii_lowercase())) {
        return false;
    }
    let mut i = 1;
    while i < n && i <= 3 && alpha(tags[i], 3..=3) {
        i += 1;
    }
    if i < n && alpha(tags[i], 4..=4) {
        i += 1;
    }
    if i < n
        && (alpha(tags[i], 2..=2)
            || (tags[i].len() == 3 && tags[i].bytes().all(|c| c.is_ascii_digit())))
    {
        i += 1;
    }
    let mut variants: Vec<String> = Vec::new();
    while i < n
        && (alnum(tags[i], 5..=8)
            || (tags[i].len() == 4
                && tags[i].as_bytes()[0].is_ascii_digit()
                && alnum(tags[i], 4..=4)))
    {
        let v = tags[i].to_ascii_lowercase();
        if variants.contains(&v) {
            return false;
        }
        variants.push(v);
        i += 1;
    }
    let mut singletons: Vec<u8> = Vec::new();
    while i < n && alnum(tags[i], 1..=1) && !tags[i].eq_ignore_ascii_case("x") {
        let c = tags[i].as_bytes()[0].to_ascii_lowercase();
        if singletons.contains(&c) {
            return false;
        }
        singletons.push(c);
        i += 1;
        let start = i;
        while i < n && alnum(tags[i], 2..=8) {
            i += 1;
        }
        if i == start {
            return false;
        }
    }
    i == n || private(i)
}

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

    /// Each `<format>_syntax_valid.txt` string is valid, and each
    /// `*_syntax_invalid.txt` and `*_parse_invalid.txt` one is not, but where
    /// `spec/VALIDATION.md` says the reference differs.
    #[test]
    fn interop_syntax_vectors() {
        let dir = concat!(env!("CARGO_MANIFEST_DIR"), "/../../spec/interop/syntax");
        // The reference takes a CIDv0, refuses a CIDv1 in any base but
        // base32, and takes a URI of any length matching its pattern.
        let differs = [
            ("cid", "QmbWqxBEKC3P8tqsKc98xmWNzrzDtRLMiMPL8wBuTGsMnR"),
            ("cid", "zdj7WWeQ43G6JJvLWQWZpyHuAMq6uYWRjkBXFad11vE2LHhQ7"),
            ("cid", "mBcDxtdWx0aWhhc2g+"),
            ("cid", "z7x3CtScH765HvShXT"),
            ("cid", "zdj7WhuEjrB52m1BisYCtmjH1hSKa7yZ3jEZ9JcXaFRD51wVz"),
            ("cid", "7134036155352661643226414134664076"),
            (
                "cid",
                "f017012202c5f688262e0ece8569aa6f94d60aad55ca8d9d83734e4a7430d0cff6588ec2b",
            ),
            ("uri", "content-type:text/plan"),
            ("uri", "microsoft.windows.camera:thing"),
        ];
        let formats = [
            ("atidentifier", "at-identifier"),
            ("aturi", "at-uri"),
            ("cid", "cid"),
            ("datetime", "datetime"),
            ("did", "did"),
            ("handle", "handle"),
            ("language", "language"),
            ("nsid", "nsid"),
            ("recordkey", "record-key"),
            ("tid", "tid"),
            ("uri", "uri"),
        ];
        let (mut seen, mut wrong) = (0, Vec::new());
        for entry in std::fs::read_dir(dir).unwrap() {
            let path = entry.unwrap().path();
            let name = path.file_name().unwrap().to_str().unwrap().to_string();
            let Some((stem, kind)) = name.strip_suffix(".txt").and_then(|n| n.split_once('_'))
            else {
                continue;
            };
            let format = formats
                .iter()
                .find(|(f, _)| *f == stem)
                .unwrap_or_else(|| panic!("{name}: no format"))
                .1;
            let want = kind == "syntax_valid";
            for line in std::fs::read_to_string(&path).unwrap().lines() {
                if line.is_empty() || line.starts_with('#') {
                    continue;
                }
                // The very long URI the vectors call invalid matches the reference's pattern.
                let long_uri = format == "uri" && line.len() > 8000;
                let expect = if differs.contains(&(format, line)) || long_uri {
                    !want
                } else {
                    want
                };
                if valid(format, line) != expect {
                    wrong.push(format!("{name}: {line:?}"));
                }
                seen += 1;
            }
        }
        assert!(wrong.is_empty(), "{wrong:#?}");
        assert!(seen > 500, "{seen} vectors");
    }

    #[test]
    fn datetimes() {
        for ok in [
            "2023-02-30T00:00:00Z",
            "2023-04-31T00:00:00Z",
            "9999-12-31T23:59:59.999Z",
            "0000-01-01T01:00:00+01:00",
            "9999-12-31T22:00:00-01:00",
        ] {
            assert!(valid_datetime(ok), "{ok}");
        }
        for bad in [
            "1985-04-12T23:20:60Z",
            "0000-01-01T00:00:00+01:00",
            "9999-12-31T23:30:00-01:00",
            "1985-04-12T23:20:50-00:00",
            &format!("1985-04-12T23:20:50.{}Z", "1".repeat(44)),
            "1985-04-12T23:20:50+24:00",
        ] {
            assert!(!valid_datetime(bad), "{bad}");
        }
        assert!(valid_datetime(&format!(
            "1985-04-12T23:20:50.{}Z",
            "1".repeat(43)
        )));
    }

    #[test]
    fn uris() {
        for ok in ["a:b", "at://x", "a_1://b", "x:a/b", "a:b:/c"] {
            assert!(valid_uri(ok), "{ok}");
        }
        for bad in ["a:", "a:/b", "a:///b", "a://", "a-b:c", "a:b\u{feff}", ":b"] {
            assert!(!valid_uri(bad), "{bad}");
        }
        assert!(valid_uri("a:b\u{85}"), "U+0085 is no JavaScript space");
    }

    #[test]
    fn languages() {
        for ok in [
            "ja",
            "ban",
            "ja-jpn",
            "en-latn-us",
            "zh-YUE-hk",
            "en-X-A",
            "x-fr-ch",
            "X-fr-CH",
            "en-GB-oed",
            "i-default",
            "sgn-BE-NL",
            "zh-hakka",
            "zh-Hakka",
            "art-lojban",
            "no-bok",
            "zh-min-nan",
            "sl-rozaj-biske",
        ] {
            assert!(valid_language(ok), "{ok}");
        }
        for bad in [
            "JA",
            "Ja",
            "ZH-HAKKA",
            "Zh-hakka",
            "jaja",
            "abcde",
            "x",
            "I-default",
            "i-Klingon",
            "en-gb-oed",
            "sgn-be-nl",
            "i-foo",
            "de-DE-1901-1901",
            "en-u-co-phonebk-U-ca-buddhist",
            "en-a",
            "en-",
            "",
        ] {
            assert!(!valid_language(bad), "{bad}");
        }
    }
}