rpdfium_parser/

xref.rs

// Derived from PDFium's cpdf_cross_ref_table.cpp / cpdf_parser.cpp
// Original: Copyright 2014 The PDFium Authors
// Licensed under BSD-3-Clause / Apache-2.0
// See pdfium-upstream/LICENSE for the original license.

//! Cross-reference table parsing (traditional `xref` format).
//!
//! Parses the standard PDF cross-reference table format with subsection headers
//! (e.g., `xref\n0 6\n...`). Each entry is exactly 20 bytes.

use rpdfium_core::error::{ParseError, PdfError};
use rpdfium_core::fx_system::MAX_OBJECT_NUMBER;

use crate::object::ObjectId;
use crate::tokenizer::is_whitespace;

/// The type of a cross-reference entry.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum XrefEntryType {
    /// In-use object at a direct byte offset in the file.
    InUse { offset: u64 },
    /// Object stored inside an object stream (ObjStm).
    InStream { stream_id: ObjectId, index: u32 },
    /// A free (deleted) object.
    Free,
}

/// A single cross-reference entry.
#[derive(Debug, Clone)]
pub struct XrefEntry {
    pub id: ObjectId,
    pub entry_type: XrefEntryType,
}

/// A section of cross-reference entries from a single xref table or stream.
#[derive(Debug, Clone)]
pub struct XrefSection {
    pub entries: Vec<XrefEntry>,
}

/// The complete cross-reference table, potentially spanning multiple sections.
#[derive(Debug, Clone)]
pub struct XrefTable {
    pub sections: Vec<XrefSection>,
    /// The byte offset of the last (newest) xref start in the file.
    /// Used by incremental saves to set the `/Prev` trailer key.
    pub start_offset: u64,
}

impl XrefTable {
    pub fn new() -> Self {
        Self {
            sections: Vec::new(),
            start_offset: 0,
        }
    }

    /// Add a section (newest sections should be added first).
    pub fn push(&mut self, section: XrefSection) {
        self.sections.push(section);
    }
}

impl Default for XrefTable {
    fn default() -> Self {
        Self::new()
    }
}

/// Parse a traditional cross-reference table starting at `offset`.
///
/// The table begins with the `xref` keyword followed by one or more subsections.
/// Each subsection has a header `start_id count` and then `count` entries of
/// exactly 20 bytes each (`nnnnnnnnnn ggggg n \r\n` or `nnnnnnnnnn ggggg f \r\n`).
///
/// Returns the parsed `XrefSection` and the byte offset after the table
/// (positioned just before the `trailer` keyword).
pub fn parse_xref_table(source: &[u8], offset: u64) -> Result<(XrefSection, u64), PdfError> {
    let mut pos = offset as usize;

    // Skip whitespace before "xref"
    while pos < source.len() && is_whitespace(source[pos]) {
        pos += 1;
    }

    // Expect "xref" keyword
    if pos + 4 > source.len() || &source[pos..pos + 4] != b"xref" {
        return Err(PdfError::InvalidXref);
    }
    pos += 4;

    // Skip whitespace after "xref"
    skip_eol(source, &mut pos);

    let mut entries = Vec::new();

    // Parse subsections until we hit "trailer" or EOF
    loop {
        // Skip whitespace
        while pos < source.len() && is_whitespace(source[pos]) {
            pos += 1;
        }

        if pos >= source.len() {
            break;
        }

        // Check for "trailer" keyword
        if pos + 7 <= source.len() && &source[pos..pos + 7] == b"trailer" {
            break;
        }

        // Parse subsection header: start_id count
        let (start_id, count) = parse_subsection_header(source, &mut pos)?;

        // Validate object numbers
        if start_id.saturating_add(count) > MAX_OBJECT_NUMBER as u64 {
            return Err(PdfError::InvalidXref);
        }

        // Parse entries
        for i in 0..count {
            skip_eol_minimal(source, &mut pos);

            let entry_bytes = if pos + 20 <= source.len() {
                &source[pos..pos + 20]
            } else {
                return Err(PdfError::Parse(ParseError::InvalidXrefEntry {
                    offset: pos as u64,
                }));
            };

            let entry = parse_xref_entry(entry_bytes, start_id + i, pos as u64)?;
            pos += 20;

            entries.push(entry);
        }
    }

    Ok((XrefSection { entries }, pos as u64))
}

/// Parse a subsection header: `start_id count\n`.
fn parse_subsection_header(source: &[u8], pos: &mut usize) -> Result<(u64, u64), PdfError> {
    // Read start_id
    let start_id = read_u64(source, pos)?;

    // Skip whitespace (not newlines)
    while *pos < source.len() && (source[*pos] == b' ' || source[*pos] == b'\t') {
        *pos += 1;
    }

    // Read count
    let count = read_u64(source, pos)?;

    // Skip to end of line
    skip_eol(source, pos);

    Ok((start_id, count))
}

/// Read an unsigned integer from the source at the given position.
fn read_u64(source: &[u8], pos: &mut usize) -> Result<u64, PdfError> {
    let start = *pos;

    while *pos < source.len() && source[*pos] >= b'0' && source[*pos] <= b'9' {
        *pos += 1;
    }

    if *pos == start {
        return Err(PdfError::InvalidXref);
    }

    let s = std::str::from_utf8(&source[start..*pos]).map_err(|_| PdfError::InvalidXref)?;
    s.parse::<u64>().map_err(|_| PdfError::InvalidXref)
}

/// Parse a single 20-byte xref entry.
///
/// Format: `nnnnnnnnnn ggggg n \r\n` or `nnnnnnnnnn ggggg f \r\n`
/// (10 digits offset, space, 5 digits generation, space, 'n' or 'f', space, EOL)
fn parse_xref_entry(entry: &[u8], object_number: u64, offset: u64) -> Result<XrefEntry, PdfError> {
    // Entry must be at least 18 bytes (10 + 1 + 5 + 1 + 1)
    if entry.len() < 18 {
        return Err(PdfError::Parse(ParseError::InvalidXrefEntry { offset }));
    }

    // Parse offset (10 digits)
    let offset_str = std::str::from_utf8(&entry[0..10])
        .map_err(|_| PdfError::Parse(ParseError::InvalidXrefEntry { offset }))?;
    let entry_offset: u64 = offset_str
        .trim()
        .parse()
        .map_err(|_| PdfError::Parse(ParseError::InvalidXrefEntry { offset }))?;

    // Parse generation number (5 digits after a space)
    let gen_str = std::str::from_utf8(&entry[11..16])
        .map_err(|_| PdfError::Parse(ParseError::InvalidXrefEntry { offset }))?;
    let generation: u16 = gen_str
        .trim()
        .parse()
        .map_err(|_| PdfError::Parse(ParseError::InvalidXrefEntry { offset }))?;

    // Parse type marker ('n' for in-use, 'f' for free)
    let type_marker = entry[17];

    let id = ObjectId::new(object_number as u32, generation);

    let entry_type = match type_marker {
        b'n' => XrefEntryType::InUse {
            offset: entry_offset,
        },
        b'f' => XrefEntryType::Free,
        _ => {
            return Err(PdfError::Parse(ParseError::InvalidXrefEntry { offset }));
        }
    };

    Ok(XrefEntry { id, entry_type })
}

/// Skip end-of-line characters (CR, LF, CR+LF).
fn skip_eol(source: &[u8], pos: &mut usize) {
    while *pos < source.len() && is_whitespace(source[*pos]) {
        *pos += 1;
    }
}

/// Skip line-ending characters (CR, LF) between xref entries.
fn skip_eol_minimal(source: &[u8], pos: &mut usize) {
    // Skip CR/LF to reach the start of the next 20-byte xref entry block.
    while *pos < source.len() && (source[*pos] == b'\r' || source[*pos] == b'\n') {
        *pos += 1;
    }
}

/// Rebuild a cross-reference table by scanning the file for `N G obj` markers.
///
/// This is a fallback for Lenient mode when standard XRef parsing fails
/// (e.g., corrupt or missing `startxref`). It iterates through the source
/// bytes looking for patterns like `\d+ \d+ obj` and records the offset of
/// each indirect object definition.
///
/// For the trailer, it scans backwards for a `trailer` keyword; if none is
/// found, it looks for the object with `/Type /Catalog` to reconstruct a
/// minimal [`crate::trailer::TrailerInfo`].
pub fn rebuild_xref(source: &[u8]) -> Result<(XrefTable, crate::trailer::TrailerInfo), PdfError> {
    let mut entries = Vec::new();
    let mut pos = 0;

    // Scan for `N G obj` patterns iteratively
    while pos < source.len() {
        // Skip to potential digit start
        if !source[pos].is_ascii_digit() {
            pos += 1;
            continue;
        }

        // Try to match: <digits> <space> <digits> <space> "obj"
        let start = pos;
        if let Some((number, generation, obj_keyword_end)) = try_parse_obj_marker(source, pos) {
            if number <= MAX_OBJECT_NUMBER {
                // Verify the byte before the object number is whitespace or start of file
                let valid_boundary = start == 0 || is_whitespace(source[start - 1]);
                if valid_boundary {
                    entries.push(XrefEntry {
                        id: ObjectId::new(number, generation),
                        entry_type: XrefEntryType::InUse {
                            offset: start as u64,
                        },
                    });
                }
            }
            // Advance past "obj" to avoid re-matching
            pos = obj_keyword_end;
        } else {
            pos += 1;
        }

        // Safety limit: prevent building an enormous table
        if entries.len() > MAX_OBJECT_NUMBER as usize {
            break;
        }
    }

    if entries.is_empty() {
        return Err(PdfError::InvalidXref);
    }

    let section = XrefSection { entries };

    // Try to find trailer info
    let trailer = rebuild_trailer_info(source, &section)?;

    let mut table = XrefTable::new();
    table.push(section);

    Ok((table, trailer))
}

/// Try to parse `N G obj` at the given position in source.
///
/// Returns `Some((number, generation, end_pos))` if matched, where `end_pos`
/// is the byte position just after `obj`.
fn try_parse_obj_marker(source: &[u8], pos: usize) -> Option<(u32, u16, usize)> {
    let mut p = pos;

    // Parse object number (digits)
    let num_start = p;
    while p < source.len() && source[p].is_ascii_digit() {
        p += 1;
    }
    if p == num_start || p >= source.len() {
        return None;
    }
    let num_str = std::str::from_utf8(&source[num_start..p]).ok()?;
    let number: u32 = num_str.parse().ok()?;

    // Expect exactly one space
    if p >= source.len() || source[p] != b' ' {
        return None;
    }
    p += 1;

    // Parse generation number (digits)
    let gen_start = p;
    while p < source.len() && source[p].is_ascii_digit() {
        p += 1;
    }
    if p == gen_start || p >= source.len() {
        return None;
    }
    let gen_str = std::str::from_utf8(&source[gen_start..p]).ok()?;
    let generation: u16 = gen_str.parse().ok()?;

    // Expect exactly one space
    if p >= source.len() || source[p] != b' ' {
        return None;
    }
    p += 1;

    // Expect "obj" keyword
    if p + 3 > source.len() || &source[p..p + 3] != b"obj" {
        return None;
    }
    p += 3;

    // After "obj", expect whitespace or end of file (not another letter, e.g. "object")
    if p < source.len() && source[p].is_ascii_alphabetic() {
        return None;
    }

    Some((number, generation, p))
}

/// Rebuild a minimal TrailerInfo by scanning for the trailer dictionary or
/// by finding the Catalog object.
fn rebuild_trailer_info(
    source: &[u8],
    section: &XrefSection,
) -> Result<crate::trailer::TrailerInfo, PdfError> {
    // First, try to find a `trailer` keyword and parse the dictionary after it
    if let Some(info) = try_find_trailer_dict(source) {
        return Ok(info);
    }

    // Fallback: scan objects to find the one with /Type /Catalog
    for entry in &section.entries {
        if let XrefEntryType::InUse { offset } = &entry.entry_type {
            let off = *offset as usize;
            // Look ahead from the object start for /Type /Catalog
            let search_end = (off + 512).min(source.len());
            let window = &source[off..search_end];
            if contains_catalog_marker(window) {
                let size = section
                    .entries
                    .iter()
                    .map(|e| e.id.number)
                    .max()
                    .unwrap_or(0)
                    + 1;
                return Ok(crate::trailer::TrailerInfo {
                    root: entry.id,
                    info: None,
                    encrypt: None,
                    id: None,
                    size,
                    prev: None,
                });
            }
        }
    }

    Err(PdfError::InvalidTrailer)
}

/// Scan backwards through the source for a `trailer` keyword and try to
/// parse a trailer dictionary from it.
fn try_find_trailer_dict(source: &[u8]) -> Option<crate::trailer::TrailerInfo> {
    let marker = b"trailer";
    // Search backwards from end
    let start = source.len().saturating_sub(4096);
    for i in (start..source.len().saturating_sub(marker.len())).rev() {
        if &source[i..i + marker.len()] == marker {
            // Try to parse the trailer dict after "trailer"
            let mut pos = i + marker.len();
            while pos < source.len() && is_whitespace(source[pos]) {
                pos += 1;
            }
            if let Ok(crate::object::Object::Dictionary(dict)) = crate::object_parser::parse_object(
                source,
                pos as u64,
                rpdfium_core::ParsingMode::Lenient,
            ) {
                return extract_trailer_from_dict(&dict);
            }
        }
    }
    None
}

/// Extract TrailerInfo from a dictionary, returning None if required fields are missing.
fn extract_trailer_from_dict(
    dict: &std::collections::HashMap<rpdfium_core::Name, crate::object::Object>,
) -> Option<crate::trailer::TrailerInfo> {
    let root = match dict.get(&rpdfium_core::Name::root()) {
        Some(crate::object::Object::Reference(id)) => *id,
        _ => return None,
    };
    let size = match dict.get(&rpdfium_core::Name::size()) {
        Some(crate::object::Object::Integer(n)) if *n > 0 => *n as u32,
        _ => return None,
    };
    let info = match dict.get(&rpdfium_core::Name::info()) {
        Some(crate::object::Object::Reference(id)) => Some(*id),
        _ => None,
    };
    let encrypt = match dict.get(&rpdfium_core::Name::encrypt()) {
        Some(crate::object::Object::Reference(id)) => Some(*id),
        _ => None,
    };
    Some(crate::trailer::TrailerInfo {
        root,
        info,
        encrypt,
        id: None,
        size,
        prev: None,
    })
}

/// Check if a byte window contains `/Type /Catalog` (or `/Type/Catalog`).
fn contains_catalog_marker(window: &[u8]) -> bool {
    // Look for /Type followed by optional whitespace and /Catalog
    let type_marker = b"/Type";
    let catalog_marker = b"/Catalog";
    for i in 0..window.len().saturating_sub(type_marker.len()) {
        if &window[i..i + type_marker.len()] == type_marker {
            // Skip whitespace after /Type
            let mut j = i + type_marker.len();
            while j < window.len() && (window[j] == b' ' || window[j] == b'\t') {
                j += 1;
            }
            if j + catalog_marker.len() <= window.len()
                && &window[j..j + catalog_marker.len()] == catalog_marker
            {
                return true;
            }
        }
    }
    false
}

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

    #[test]
    fn parse_simple_xref_table() {
        let source = b"xref\n\
                        0 3\n\
                        0000000000 65535 f \r\n\
                        0000000009 00000 n \r\n\
                        0000000074 00000 n \r\n\
                        trailer";
        let (section, end_pos) = parse_xref_table(source, 0).unwrap();
        assert_eq!(section.entries.len(), 3);

        // First entry: free
        assert_eq!(section.entries[0].id.number, 0);
        assert_eq!(section.entries[0].entry_type, XrefEntryType::Free);

        // Second entry: in-use at offset 9
        assert_eq!(section.entries[1].id.number, 1);
        assert_eq!(
            section.entries[1].entry_type,
            XrefEntryType::InUse { offset: 9 }
        );

        // Third entry: in-use at offset 74
        assert_eq!(section.entries[2].id.number, 2);
        assert_eq!(
            section.entries[2].entry_type,
            XrefEntryType::InUse { offset: 74 }
        );

        // Should be positioned at "trailer"
        assert!(source[end_pos as usize..].starts_with(b"trailer"));
    }

    #[test]
    fn parse_xref_with_multiple_subsections() {
        let source = b"xref\n\
                        0 1\n\
                        0000000000 65535 f \r\n\
                        3 1\n\
                        0000025325 00000 n \r\n\
                        trailer";
        let (section, _) = parse_xref_table(source, 0).unwrap();
        assert_eq!(section.entries.len(), 2);
        assert_eq!(section.entries[0].id.number, 0);
        assert_eq!(section.entries[1].id.number, 3);
    }

    #[test]
    fn reject_object_number_exceeding_limit() {
        // Object number that exceeds MAX_OBJECT_NUMBER
        let source = format!(
            "xref\n{} 1\n0000000000 00000 n \r\ntrailer",
            MAX_OBJECT_NUMBER + 1
        );
        let result = parse_xref_table(source.as_bytes(), 0);
        assert!(result.is_err());
    }

    #[test]
    fn parse_xref_entry_in_use() {
        let entry = b"0000000009 00000 n \r\n";
        let result = parse_xref_entry(entry, 1, 0).unwrap();
        assert_eq!(result.id.number, 1);
        assert_eq!(result.id.generation, 0);
        assert_eq!(result.entry_type, XrefEntryType::InUse { offset: 9 });
    }

    #[test]
    fn parse_xref_entry_free() {
        let entry = b"0000000000 65535 f \r\n";
        let result = parse_xref_entry(entry, 0, 0).unwrap();
        assert_eq!(result.id.number, 0);
        assert_eq!(result.id.generation, 65535);
        assert_eq!(result.entry_type, XrefEntryType::Free);
    }

    #[test]
    fn xref_table_default() {
        let table = XrefTable::default();
        assert!(table.sections.is_empty());
    }

    #[test]
    fn parse_xref_at_offset() {
        let prefix = b"some garbage before ";
        let xref = b"xref\n0 1\n0000000000 65535 f \r\ntrailer";
        let mut source = prefix.to_vec();
        source.extend_from_slice(xref);
        let (section, _) = parse_xref_table(&source, prefix.len() as u64).unwrap();
        assert_eq!(section.entries.len(), 1);
    }

    // -----------------------------------------------------------------------
    // Upstream-derived xref table tests (cpdf_parser_unittest.cpp)
    // -----------------------------------------------------------------------

    /// Upstream: LoadCrossRefV4 — multiple non-contiguous subsections.
    /// Ported from cpdf_parser_unittest.cpp: subsections 0 1, 3 1, 8 2, 12 1.
    #[test]
    fn parse_xref_multiple_subsections_non_contiguous() {
        let source = b"xref\n\
                        0 1\n\
                        0000000000 65535 f \r\n\
                        3 1\n\
                        0000025325 00000 n \r\n\
                        8 2\n\
                        0000025518 00002 n \r\n\
                        0000025635 00000 n \r\n\
                        12 1\n\
                        0000025777 00000 n \r\n\
                        trailer";
        let (section, end_pos) = parse_xref_table(source, 0).unwrap();
        assert_eq!(section.entries.len(), 5);

        // Object 0: free
        assert_eq!(section.entries[0].id.number, 0);
        assert_eq!(section.entries[0].id.generation, 65535);
        assert_eq!(section.entries[0].entry_type, XrefEntryType::Free);

        // Object 3: in-use at offset 25325
        assert_eq!(section.entries[1].id.number, 3);
        assert_eq!(section.entries[1].id.generation, 0);
        assert_eq!(
            section.entries[1].entry_type,
            XrefEntryType::InUse { offset: 25325 }
        );

        // Object 8: in-use at offset 25518, generation 2
        assert_eq!(section.entries[2].id.number, 8);
        assert_eq!(section.entries[2].id.generation, 2);
        assert_eq!(
            section.entries[2].entry_type,
            XrefEntryType::InUse { offset: 25518 }
        );

        // Object 9: in-use at offset 25635
        assert_eq!(section.entries[3].id.number, 9);
        assert_eq!(section.entries[3].id.generation, 0);
        assert_eq!(
            section.entries[3].entry_type,
            XrefEntryType::InUse { offset: 25635 }
        );

        // Object 12: in-use at offset 25777
        assert_eq!(section.entries[4].id.number, 12);
        assert_eq!(section.entries[4].id.generation, 0);
        assert_eq!(
            section.entries[4].entry_type,
            XrefEntryType::InUse { offset: 25777 }
        );

        // End position should be at "trailer"
        assert!(source[end_pos as usize..].starts_with(b"trailer"));
    }

    /// Upstream: LoadCrossRefV4 — large table (regression for crbug.com/945624).
    /// 2048-entry xref table should not cause issues.
    #[test]
    fn parse_xref_large_table() {
        let count = 2048u64;
        let mut source = Vec::new();
        source.extend_from_slice(format!("xref\n0 {count}\n").as_bytes());

        // First entry is free
        source.extend_from_slice(b"0000000000 65535 f \r\n");

        // Remaining entries are in-use with incrementing offsets
        for i in 1..count {
            source.extend_from_slice(format!("{:010} 00000 n \r\n", i * 100).as_bytes());
        }
        source.extend_from_slice(b"trailer");

        let (section, end_pos) = parse_xref_table(&source, 0).unwrap();
        assert_eq!(section.entries.len(), count as usize);

        // Verify first and last entries
        assert_eq!(section.entries[0].id.number, 0);
        assert_eq!(section.entries[0].entry_type, XrefEntryType::Free);

        let last = &section.entries[count as usize - 1];
        assert_eq!(last.id.number, (count - 1) as u32);
        assert_eq!(
            last.entry_type,
            XrefEntryType::InUse {
                offset: (count - 1) * 100
            }
        );

        assert!(source[end_pos as usize..].starts_with(b"trailer"));
    }

    /// Upstream: free entries form a chain. We should parse them correctly.
    #[test]
    fn parse_xref_free_entry_chain() {
        let source = b"xref\n\
                        0 4\n\
                        0000000003 65535 f \r\n\
                        0000000100 00000 n \r\n\
                        0000000000 65535 f \r\n\
                        0000000000 65535 f \r\n\
                        trailer";
        let (section, _) = parse_xref_table(source, 0).unwrap();
        assert_eq!(section.entries.len(), 4);

        // Object 0: free (points to next free: 3)
        assert_eq!(section.entries[0].entry_type, XrefEntryType::Free);
        // Object 1: in-use
        assert_eq!(
            section.entries[1].entry_type,
            XrefEntryType::InUse { offset: 100 }
        );
        // Object 2: free
        assert_eq!(section.entries[2].entry_type, XrefEntryType::Free);
        // Object 3: free
        assert_eq!(section.entries[3].entry_type, XrefEntryType::Free);
    }

    /// Single-entry subsection.
    #[test]
    fn parse_xref_single_entry() {
        let source = b"xref\n\
                        5 1\n\
                        0000012345 00003 n \r\n\
                        trailer";
        let (section, _) = parse_xref_table(source, 0).unwrap();
        assert_eq!(section.entries.len(), 1);
        assert_eq!(section.entries[0].id.number, 5);
        assert_eq!(section.entries[0].id.generation, 3);
        assert_eq!(
            section.entries[0].entry_type,
            XrefEntryType::InUse { offset: 12345 }
        );
    }

    /// Empty xref table (0 entries).
    #[test]
    fn parse_xref_zero_entries() {
        let source = b"xref\n\
                        0 0\n\
                        trailer";
        let (section, _) = parse_xref_table(source, 0).unwrap();
        assert!(section.entries.is_empty());
    }

    /// Truncated xref entry (< 20 bytes) should fail.
    #[test]
    fn parse_xref_truncated_entry() {
        let source = b"xref\n\
                        0 1\n\
                        0000000000 65535";
        let result = parse_xref_table(source, 0);
        assert!(result.is_err());
    }

    /// Missing "xref" keyword should fail.
    #[test]
    fn parse_xref_missing_keyword() {
        let source = b"0 1\n0000000000 65535 f \r\ntrailer";
        let result = parse_xref_table(source, 0);
        assert!(result.is_err());
    }

    /// Invalid type marker (not 'n' or 'f') should fail.
    #[test]
    fn parse_xref_entry_invalid_marker() {
        let entry = b"0000000009 00000 x \r\n";
        let result = parse_xref_entry(entry, 1, 0);
        assert!(result.is_err());
    }

    /// Xref entry with high generation number.
    #[test]
    fn parse_xref_entry_high_generation() {
        let entry = b"0000000009 12345 n \r\n";
        let result = parse_xref_entry(entry, 1, 0).unwrap();
        assert_eq!(result.id.generation, 12345);
    }

    /// Xref entry with large offset.
    #[test]
    fn parse_xref_entry_large_offset() {
        let entry = b"9999999999 00000 n \r\n";
        let result = parse_xref_entry(entry, 1, 0).unwrap();
        assert_eq!(
            result.entry_type,
            XrefEntryType::InUse { offset: 9999999999 }
        );
    }

    // -----------------------------------------------------------------------
    // rebuild_xref tests
    // -----------------------------------------------------------------------

    /// rebuild_xref finds objects and reconstructs the trailer from a
    /// PDF with a valid trailer dict but no valid startxref/xref table.
    #[test]
    fn rebuild_xref_with_trailer() {
        let mut pdf = Vec::new();
        pdf.extend_from_slice(b"%PDF-1.4\n");

        let obj1_offset = pdf.len();
        pdf.extend_from_slice(b"1 0 obj\n<< /Type /Catalog /Pages 2 0 R >>\nendobj\n");

        let obj2_offset = pdf.len();
        pdf.extend_from_slice(b"2 0 obj\n<< /Type /Pages /Kids [] /Count 0 >>\nendobj\n");

        // Add a trailer dict but with a corrupt xref
        pdf.extend_from_slice(b"trailer\n<< /Size 3 /Root 1 0 R >>\n");
        // No valid startxref

        let (table, trailer) = rebuild_xref(&pdf).unwrap();
        assert_eq!(table.sections.len(), 1);

        let entries = &table.sections[0].entries;
        assert_eq!(entries.len(), 2);

        // Verify object 1 found at correct offset
        let entry1 = entries.iter().find(|e| e.id.number == 1).unwrap();
        assert_eq!(
            entry1.entry_type,
            XrefEntryType::InUse {
                offset: obj1_offset as u64
            }
        );

        // Verify object 2 found at correct offset
        let entry2 = entries.iter().find(|e| e.id.number == 2).unwrap();
        assert_eq!(
            entry2.entry_type,
            XrefEntryType::InUse {
                offset: obj2_offset as u64
            }
        );

        // Trailer extracted from the trailer dict
        assert_eq!(trailer.root, ObjectId::new(1, 0));
        assert_eq!(trailer.size, 3);
    }

    /// rebuild_xref finds the catalog object when there is no trailer dict.
    #[test]
    fn rebuild_xref_catalog_fallback() {
        let mut pdf = Vec::new();
        pdf.extend_from_slice(b"%PDF-1.4\n");

        let obj1_offset = pdf.len();
        pdf.extend_from_slice(b"1 0 obj\n<< /Type /Catalog /Pages 2 0 R >>\nendobj\n");

        let obj2_offset = pdf.len();
        pdf.extend_from_slice(b"2 0 obj\n<< /Type /Pages /Kids [] /Count 0 >>\nendobj\n");

        // No trailer at all

        let (table, trailer) = rebuild_xref(&pdf).unwrap();
        assert_eq!(table.sections.len(), 1);

        let entries = &table.sections[0].entries;
        assert_eq!(entries.len(), 2);

        let entry1 = entries.iter().find(|e| e.id.number == 1).unwrap();
        assert_eq!(
            entry1.entry_type,
            XrefEntryType::InUse {
                offset: obj1_offset as u64
            }
        );

        let entry2 = entries.iter().find(|e| e.id.number == 2).unwrap();
        assert_eq!(
            entry2.entry_type,
            XrefEntryType::InUse {
                offset: obj2_offset as u64
            }
        );

        // Root should be object 1 (the Catalog)
        assert_eq!(trailer.root, ObjectId::new(1, 0));
        // Size = max object number + 1
        assert_eq!(trailer.size, 3);
    }

    /// rebuild_xref on source with no objects returns an error.
    #[test]
    fn rebuild_xref_no_objects() {
        let source = b"%PDF-1.4\nno objects here at all\n%%EOF";
        let result = rebuild_xref(source);
        assert!(result.is_err());
    }

    /// rebuild_xref does not match partial keywords like "object".
    #[test]
    fn rebuild_xref_ignores_non_obj_keywords() {
        let source = b"%PDF-1.4\nThis is an object keyword test\n";
        let result = rebuild_xref(source);
        assert!(result.is_err());
    }

    /// try_parse_obj_marker correctly parses "N G obj".
    #[test]
    fn try_parse_obj_marker_basic() {
        let source = b"1 0 obj\n";
        let result = try_parse_obj_marker(source, 0);
        assert!(result.is_some());
        let (number, generation, end) = result.unwrap();
        assert_eq!(number, 1);
        assert_eq!(generation, 0);
        assert_eq!(end, 7); // past "obj"
    }

    /// try_parse_obj_marker rejects "1 0 object" (alphabetic continuation).
    #[test]
    fn try_parse_obj_marker_rejects_object_word() {
        let source = b"1 0 object\n";
        let result = try_parse_obj_marker(source, 0);
        assert!(result.is_none());
    }

    /// contains_catalog_marker detects /Type /Catalog with various spacing.
    #[test]
    fn contains_catalog_marker_test() {
        assert!(contains_catalog_marker(b"/Type /Catalog"));
        assert!(contains_catalog_marker(b"/Type/Catalog"));
        assert!(contains_catalog_marker(
            b"<< /Type  /Catalog /Pages 2 0 R >>"
        ));
        assert!(!contains_catalog_marker(b"/Type /Pages"));
        assert!(!contains_catalog_marker(b"no catalog here"));
    }
}