vole-document 0.1.0-alpha.5

//! Byte-authoritative PDF lexical scanner.
//!
//! `lex` partitions an input into ordered [`Span`]s such that every byte belongs
//! to exactly one span. It performs no structural interpretation: keywords,
//! numbers, references, and object boundaries remain inside `Regular` and
//! `LiteralString` spans for the Phase 3.2 parser to resolve. In particular a
//! literal string is a single opaque span, so occurrences of `obj`, `endobj`, or
//! `stream` *inside* a string can never be mistaken for structure.
//!
//! Unterminated constructs are not errors here: they extend to EOF and are
//! reported as non-fatal [`LexIssue`]s, because a byte cover must still be
//! produced for hostile or truncated input.

use crate::error::{Error, Result};
use crate::limits::Limits;

use super::span::{Span, SpanKind, SpanSet};

/// A tolerated lexical anomaly. Coverage is still complete when one is present.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum LexIssue {
    /// A `(` literal string reached EOF before its matching `)`.
    UnterminatedLiteralString { at: u64 },
    /// A `<` hex string reached EOF before its closing `>`.
    UnterminatedHexString { at: u64 },
    /// A `%` comment reached EOF without a closing CR or LF.
    UnterminatedComment { at: u64 },
}

/// The lexical cover of an input plus any non-fatal issues encountered.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct LexResult {
    /// The exact byte cover.
    pub spans: SpanSet,
    /// Anomalies tolerated while building the cover, in source order.
    pub issues: Vec<LexIssue>,
}

/// PDF whitespace: NUL, HT, LF, FF, CR, SP.
const fn is_whitespace(b: u8) -> bool {
    matches!(b, 0x00 | 0x09 | 0x0A | 0x0C | 0x0D | 0x20)
}

/// PDF delimiters, none of which may appear inside a name or regular token.
const fn is_delimiter(b: u8) -> bool {
    matches!(
        b,
        b'(' | b')' | b'<' | b'>' | b'[' | b']' | b'{' | b'}' | b'/' | b'%'
    )
}

/// A regular byte is neither whitespace nor a delimiter.
const fn is_regular(b: u8) -> bool {
    !is_whitespace(b) && !is_delimiter(b)
}

/// Lex `input` under `limits`, returning a complete byte cover.
///
/// Every byte of `input` appears in exactly one span, in ascending order. The
/// cover is validated against the input length before returning, so an internal
/// scanner bug surfaces as [`crate::ErrorClass::CoverageViolation`] rather than
/// silent data loss. Exceeding `limits.max_pdf_spans` returns
/// [`crate::ErrorClass::ResourceLimit`].
pub fn lex(input: &[u8], limits: Limits) -> Result<LexResult> {
    let n = input.len();
    let max = limits.max_pdf_spans;
    let mut spans: Vec<Span> = Vec::new();
    let mut issues: Vec<LexIssue> = Vec::new();
    let mut pos: usize = 0;

    while pos < n {
        let b = input[pos];
        if is_whitespace(b) {
            let start = pos;
            while pos < n && is_whitespace(input[pos]) {
                pos += 1;
            }
            push(&mut spans, start, pos - start, SpanKind::Whitespace, max)?;
        } else if b == b'%' {
            let start = pos;
            pos += 1;
            while pos < n && input[pos] != b'\r' && input[pos] != b'\n' {
                pos += 1;
            }
            if pos >= n {
                issues.push(LexIssue::UnterminatedComment { at: start as u64 });
            }
            push(&mut spans, start, pos - start, SpanKind::Comment, max)?;
        } else if b == b'(' {
            let start = pos;
            pos = scan_literal_string(input, start, &mut issues);
            push(&mut spans, start, pos - start, SpanKind::LiteralString, max)?;
        } else if b == b'<' {
            if pos + 1 < n && input[pos + 1] == b'<' {
                push(&mut spans, pos, 2, SpanKind::DictOpen, max)?;
                pos += 2;
            } else {
                let start = pos;
                pos += 1;
                while pos < n && input[pos] != b'>' {
                    pos += 1;
                }
                if pos < n {
                    pos += 1; // include the closing '>'
                } else {
                    issues.push(LexIssue::UnterminatedHexString { at: start as u64 });
                }
                push(&mut spans, start, pos - start, SpanKind::HexString, max)?;
            }
        } else if b == b'>' {
            if pos + 1 < n && input[pos + 1] == b'>' {
                push(&mut spans, pos, 2, SpanKind::DictClose, max)?;
                pos += 2;
            } else {
                // A lone '>' is a delimiter with no lexical role; keep it as a
                // single-byte token so the cover stays complete.
                push(&mut spans, pos, 1, SpanKind::Regular, max)?;
                pos += 1;
            }
        } else if b == b'[' {
            push(&mut spans, pos, 1, SpanKind::ArrayOpen, max)?;
            pos += 1;
        } else if b == b']' {
            push(&mut spans, pos, 1, SpanKind::ArrayClose, max)?;
            pos += 1;
        } else if b == b'{' {
            push(&mut spans, pos, 1, SpanKind::BraceOpen, max)?;
            pos += 1;
        } else if b == b'}' {
            push(&mut spans, pos, 1, SpanKind::BraceClose, max)?;
            pos += 1;
        } else if b == b'/' {
            let start = pos;
            pos += 1;
            while pos < n && is_regular(input[pos]) {
                pos += 1;
            }
            push(&mut spans, start, pos - start, SpanKind::Name, max)?;
        } else if b == b')' {
            // Unmatched ')' cannot open a literal string; keep it as a
            // single-byte token to preserve coverage.
            push(&mut spans, pos, 1, SpanKind::Regular, max)?;
            pos += 1;
        } else {
            let start = pos;
            while pos < n && is_regular(input[pos]) {
                pos += 1;
            }
            push(&mut spans, start, pos - start, SpanKind::Regular, max)?;
        }
    }

    let spans = SpanSet { spans };
    spans.validate(n as u64)?;
    Ok(LexResult { spans, issues })
}

/// Consume a `(` literal string starting at `start`; returns the first offset
/// after the span. `\` escapes the next byte, and `\` before a CR, LF, or CRLF
/// is a line continuation that also swallows the EOL.
fn scan_literal_string(input: &[u8], start: usize, issues: &mut Vec<LexIssue>) -> usize {
    let n = input.len();
    let mut pos = start;
    let mut depth: u64 = 0;
    loop {
        if pos >= n {
            issues.push(LexIssue::UnterminatedLiteralString { at: start as u64 });
            return pos;
        }
        let c = input[pos];
        if c == b'\\' {
            pos += 1;
            if pos < n {
                let escaped = input[pos];
                pos += 1;
                if escaped == b'\r' && pos < n && input[pos] == b'\n' {
                    pos += 1;
                }
            }
        } else if c == b'(' {
            depth = depth.saturating_add(1);
            pos += 1;
        } else if c == b')' {
            depth = depth.saturating_sub(1);
            pos += 1;
            if depth == 0 {
                return pos;
            }
        } else {
            pos += 1;
        }
    }
}

/// Append a span, enforcing the span-count bound.
fn push(spans: &mut Vec<Span>, start: usize, len: usize, kind: SpanKind, max: u32) -> Result<()> {
    if spans.len() as u64 >= max as u64 {
        return Err(Error::resource_limit(format!(
            "pdf span count exceeds limit {max}"
        )));
    }
    spans.push(Span {
        start: start as u64,
        len: len as u64,
        kind,
    });
    Ok(())
}

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

    fn run(input: &[u8]) -> LexResult {
        lex(input, Limits::DEFAULT).expect("lex must succeed")
    }

    fn kinds(r: &LexResult) -> Vec<SpanKind> {
        r.spans.spans.iter().map(|s| s.kind).collect()
    }

    #[test]
    fn empty_input() {
        let r = run(b"");
        assert!(r.spans.spans.is_empty());
        assert!(r.issues.is_empty());
        assert!(r.spans.validate(0).is_ok());
    }

    #[test]
    fn single_whitespace() {
        let r = run(b" ");
        assert_eq!(r.spans.spans.len(), 1);
        assert_eq!(r.spans.spans[0].kind, SpanKind::Whitespace);
        assert_eq!(r.spans.spans[0].len, 1);
    }

    #[test]
    fn whitespace_run_coalesces() {
        let input = b" \t\r\n\x0c\x00 ";
        let r = run(input);
        assert_eq!(r.spans.spans.len(), 1);
        assert_eq!(r.spans.spans[0].kind, SpanKind::Whitespace);
        assert_eq!(r.spans.spans[0].len, input.len() as u64);
    }

    #[test]
    fn comment_to_eol_excludes_eol() {
        let r = run(b"%hello\n");
        assert_eq!(kinds(&r), vec![SpanKind::Comment, SpanKind::Whitespace]);
        assert_eq!(r.spans.spans[0].start, 0);
        assert_eq!(r.spans.spans[0].len, 6);
        assert_eq!(r.spans.spans[1].start, 6);
        assert_eq!(r.spans.spans[1].len, 1);
        assert!(r.issues.is_empty());
    }

    #[test]
    fn comment_stops_before_cr() {
        let r = run(b"%x\r\n");
        assert_eq!(kinds(&r), vec![SpanKind::Comment, SpanKind::Whitespace]);
        assert_eq!(r.spans.spans[0].len, 2);
        assert_eq!(r.spans.spans[1].len, 2);
        assert!(r.issues.is_empty());
    }

    #[test]
    fn comment_to_eof_is_issue() {
        let r = run(b"%abc");
        assert_eq!(kinds(&r), vec![SpanKind::Comment]);
        assert_eq!(r.spans.spans[0].len, 4);
        assert_eq!(r.issues, vec![LexIssue::UnterminatedComment { at: 0 }]);
    }

    #[test]
    fn literal_string_with_escape() {
        // ( a \ ) b )  -- the escaped ')' does not close the string.
        let r = run(b"(a\\)b)");
        assert_eq!(kinds(&r), vec![SpanKind::LiteralString]);
        assert_eq!(r.spans.spans[0].len, 6);
        assert!(r.issues.is_empty());
    }

    #[test]
    fn literal_string_with_line_continuation() {
        // ( a \ CR LF b ) -- backslash before CRLF swallows the EOL.
        let r = run(b"(a\\\r\nb)");
        assert_eq!(kinds(&r), vec![SpanKind::LiteralString]);
        assert_eq!(r.spans.spans[0].len, 7);
        assert!(r.issues.is_empty());
    }

    #[test]
    fn literal_string_with_nested_parens() {
        let r = run(b"(a(b)c)");
        assert_eq!(kinds(&r), vec![SpanKind::LiteralString]);
        assert_eq!(r.spans.spans[0].len, 7);
        assert!(r.issues.is_empty());
    }

    #[test]
    fn unterminated_literal_string_is_issue() {
        let r = run(b"(abc");
        assert_eq!(kinds(&r), vec![SpanKind::LiteralString]);
        assert_eq!(r.spans.spans[0].len, 4);
        assert_eq!(
            r.issues,
            vec![LexIssue::UnterminatedLiteralString { at: 0 }]
        );
    }

    #[test]
    fn percent_inside_literal_string_is_not_a_comment() {
        let r = run(b"( % )");
        assert_eq!(kinds(&r), vec![SpanKind::LiteralString]);
        assert_eq!(r.spans.spans[0].len, 5);
        assert!(r.issues.is_empty());
    }

    #[test]
    fn paren_inside_hex_string_is_not_special() {
        let r = run(b"<4(2>");
        assert_eq!(kinds(&r), vec![SpanKind::HexString]);
        assert_eq!(r.spans.spans[0].len, 5);
        assert!(r.issues.is_empty());
    }

    #[test]
    fn hex_string_basic() {
        let r = run(b"<4142>");
        assert_eq!(kinds(&r), vec![SpanKind::HexString]);
        assert_eq!(r.spans.spans[0].len, 6);
    }

    #[test]
    fn unterminated_hex_string_is_issue() {
        let r = run(b"<41");
        assert_eq!(kinds(&r), vec![SpanKind::HexString]);
        assert_eq!(r.spans.spans[0].len, 3);
        assert_eq!(r.issues, vec![LexIssue::UnterminatedHexString { at: 0 }]);
    }

    #[test]
    fn dict_delimiters() {
        let r = run(b"<<>>");
        assert_eq!(kinds(&r), vec![SpanKind::DictOpen, SpanKind::DictClose]);
        assert_eq!(r.spans.spans[0].len, 2);
        assert_eq!(r.spans.spans[1].len, 2);
    }

    #[test]
    fn lone_closers_are_regular_tokens() {
        let r = run(b")>");
        assert_eq!(kinds(&r), vec![SpanKind::Regular, SpanKind::Regular]);
        let r = run(b">>>");
        assert_eq!(kinds(&r), vec![SpanKind::DictClose, SpanKind::Regular]);
    }

    #[test]
    fn name_and_empty_name() {
        let r = run(b"/Name");
        assert_eq!(kinds(&r), vec![SpanKind::Name]);
        assert_eq!(r.spans.spans[0].len, 5);
        let r = run(b"/");
        assert_eq!(kinds(&r), vec![SpanKind::Name]);
        assert_eq!(r.spans.spans[0].len, 1);
    }

    #[test]
    fn arrays_and_braces() {
        let r = run(b"[]{}");
        assert_eq!(
            kinds(&r),
            vec![
                SpanKind::ArrayOpen,
                SpanKind::ArrayClose,
                SpanKind::BraceOpen,
                SpanKind::BraceClose,
            ]
        );
    }

    #[test]
    fn numbers_and_reference_are_regular_tokens() {
        let r = run(b"12 0 R");
        assert_eq!(
            kinds(&r),
            vec![
                SpanKind::Regular,
                SpanKind::Whitespace,
                SpanKind::Regular,
                SpanKind::Whitespace,
                SpanKind::Regular,
            ]
        );
        let text: Vec<&[u8]> = r
            .spans
            .spans
            .iter()
            .map(|s| &b"12 0 R"[s.start as usize..(s.start + s.len) as usize])
            .collect();
        assert_eq!(text, vec![&b"12"[..], b" ", b"0", b" ", b"R"]);
    }

    #[test]
    fn endobj_inside_literal_string_stays_one_span() {
        let r = run(b"(1 0 obj endobj)5");
        assert_eq!(kinds(&r), vec![SpanKind::LiteralString, SpanKind::Regular]);
        assert_eq!(r.spans.spans[0].start, 0);
        assert_eq!(r.spans.spans[0].len, 16);
        assert_eq!(r.spans.spans[1].start, 16);
        assert_eq!(r.spans.spans[1].len, 1);
    }

    #[test]
    fn span_at_over_lexed_input() {
        let r = run(b"12 0 R");
        assert_eq!(r.spans.span_at(0).map(|s| s.kind), Some(SpanKind::Regular));
        assert_eq!(r.spans.span_at(1).map(|s| s.kind), Some(SpanKind::Regular));
        assert_eq!(
            r.spans.span_at(2).map(|s| s.kind),
            Some(SpanKind::Whitespace)
        );
        assert_eq!(r.spans.span_at(3).map(|s| s.kind), Some(SpanKind::Regular));
        assert_eq!(
            r.spans.span_at(4).map(|s| s.kind),
            Some(SpanKind::Whitespace)
        );
        assert_eq!(r.spans.span_at(5).map(|s| s.kind), Some(SpanKind::Regular));
        assert_eq!(r.spans.span_at(6), None);
    }

    #[test]
    fn span_limit_triggers_resource_limit() {
        let limits = Limits {
            max_pdf_spans: 2,
            ..Limits::DEFAULT
        };
        let e = lex(b"a b c", limits).unwrap_err();
        assert_eq!(e.class(), ErrorClass::ResourceLimit);
    }

    #[test]
    fn cover_invariant_holds_for_a_battery() {
        let inputs: [&[u8]; 15] = [
            b"",
            b" ",
            b"%%EOF",
            b"<< /Type /Catalog >>",
            b"[1 2.5 -3 (str) <4142> /Name]",
            b"(unterminated",
            b"<414243",
            b"%comment with ( and < and >>",
            b"()<>[]{}",
            b"\x00\x09\x0a\x0c\x0d\x20mixed",
            b"trailing>",
            b")))",
            b"<<<<<<",
            b"(nested (deep (deeper)) end)",
            b"1 0 obj\n<< /A (x) >>\nendobj",
        ];
        for input in inputs {
            let r = lex(input, Limits::DEFAULT).expect("lex must succeed");
            r.spans
                .validate(input.len() as u64)
                .expect("cover must validate");
        }
    }

    fn xorshift64(state: &mut u64) -> u64 {
        let mut x = *state;
        x ^= x << 13;
        x ^= x >> 7;
        x ^= x << 17;
        *state = x;
        x
    }

    #[test]
    fn cover_invariant_holds_for_random_bytes() {
        let mut state: u64 = 0x9E37_79B9_7F4A_7C15;
        for _ in 0..500 {
            let len = (xorshift64(&mut state) % 300) as usize;
            let mut buf = Vec::with_capacity(len);
            for _ in 0..len {
                buf.push((xorshift64(&mut state) & 0xFF) as u8);
            }
            let r = lex(&buf, Limits::STRICT).expect("lex must not fail on bounded input");
            r.spans
                .validate(buf.len() as u64)
                .expect("random cover must validate");
            assert!(r.spans.spans.len() <= buf.len());
        }
    }
}