vole-document 0.1.0-alpha.20

//! PDF `/Length` / revision-chain proceduralization as a **size** mechanism.
//!
//! Phase 3 recovered a PDF's incremental revisions and resolved `/Length` values
//! as *observation* structure; Phase 11 persists them as queryable observation
//! nodes. Neither prices them. This candidate asks the Phase-13 question
//! directly: can the structurally determined bytes of a PDF's `/Length` values
//! and its revision/xref chain be **regenerated** instead of stored, and does
//! that pay its own framing?
//!
//! The mechanism reuses the Phase-5 positional algebra —
//! [`Op::PackSegments`] over [`PackItem::Literal`] / [`PackItem::Mark`] /
//! [`PackItem::Emit`] — with a single compact item table and one literal data
//! object. It regenerates three classes of field:
//!
//! * **xref entry offsets** — the 10-digit byte offset of each in-use entry that
//!   equals the position at which its target object's introducer is marked;
//! * **`startxref` and trailer `/Prev`** values — absolute byte offsets of a
//!   revision's `xref` section anchor (the revision-chain redundancy);
//! * **`/Length` values** — the payload byte count of each directly-sized stream,
//!   regenerated by marking the *output offset equal to the length* and emitting
//!   that mark. This is the only way a *relative* quantity can be reproduced by
//!   the deliberately position-only algebra: `EMIT_OFFSET` renders an absolute
//!   marked position as a fixed-width decimal, so a `/Length` `L` is reproduced
//!   exactly when the reconstruction passes through offset `L` before the field
//!   and a mark records it there.
//!
//! Every precondition failure — a non-classic xref section, an xref stream, too
//! many objects, a field whose digits do not match a marked position, a slot
//! budget exhausted — falls back to a literal or declines the whole candidate.
//! Prediction never invents bytes: a field is emitted only when the emitted
//! decimal reproduces the source digits exactly, and the finished program is
//! round-tripped through the normative decoder (serialize → parse → materialize →
//! byte-compare) before it is returned.
//!
//! This candidate is offered to the *same* complete-cost court as every other
//! lane; it is not assumed to win, and on the measured corpus it loses. The
//! honest limits (a `Mark` per predicted field and a slot per distinct length;
//! the offset-equality trick needs `value < field_offset`) are recorded in
//! [`docs/adr/0036-pdf-length-revision-size.md`](../../../docs/adr/0036-pdf-length-revision-size.md).

use crate::SOURCE_FORMAT_PDF;
use crate::container::{Descriptor, ObjectSource, UNIVERSE};
use crate::dra::op::PackItem;
use crate::dra::{Op, Program};
use crate::encode::candidates::{Candidate, CandidateKind};
use crate::error::Result;
use crate::integrity::sha256;
use crate::limits::Limits;

use super::layout::{
    MAX_MARKED_OBJECTS, XrefPiece, parse_classic_xref, parse_digits, push_literal,
};
use super::lexer::lex;
use super::physical::{LengthSource, ObjRole, PdfPhysical, PhysicalKind, scan};
use super::span::{Span, SpanKind};

/// Addressable positional slots (slot indices are `u8`, so `0..=255`).
const MAX_OFFSET_SLOTS: usize = 256;

/// A built proceduralization plan: the packed item table and its single literal
/// data object, plus the prediction counters used to describe the plan.
pub struct LengthRevisionPlan {
    /// Ordered reconstruction items consumed by [`Op::PackSegments`].
    pub items: Vec<PackItem>,
    /// Every literal byte, in item order; consumed exactly by `items`.
    pub data: Vec<u8>,
    /// Indirect objects whose introducer was marked.
    pub objects_marked: usize,
    /// `xref` sections whose start was marked (one slot per revision anchor).
    pub revisions_marked: usize,
    /// xref entry offsets regenerated from a marked object position.
    pub xref_predicted: usize,
    /// xref entries stored literally (precondition failed).
    pub xref_literal: usize,
    /// `startxref` values regenerated.
    pub startxref_predicted: usize,
    /// trailer `/Prev` values regenerated.
    pub prev_predicted: usize,
    /// `/Length` values regenerated from an offset mark.
    pub length_predicted: usize,
    /// `/Length` values stored literally (precondition failed).
    pub length_literal: usize,
}

/// Ignore-marked events over the contiguous output: a zero-width position mark
/// or a fixed-width regenerated decimal field.
#[derive(Clone, Copy)]
enum Event {
    Mark(u8),
    Emit { slot: u8, width: u8 },
}

/// Build the `/Length` + revision-chain plan for `input`, or `None` when the
/// input is not a classic-cross-reference PDF this mechanism can express.
///
/// Declines (`Ok(None)`) on a non-contiguous cover, a cross-reference stream, no
/// classic `xref` section, more objects than the slot budget, or a field whose
/// regenerated digits would not reproduce the source. The caller owns the final
/// byte-exactness check through the normative decoder.
pub fn build_length_revision_plan(
    input: &[u8],
    limits: Limits,
) -> Result<Option<LengthRevisionPlan>> {
    let physical = match scan(input, limits) {
        Ok(p) => p,
        Err(_) => return Ok(None),
    };
    build_length_revision_plan_with(input, limits, &physical)
}

/// [`build_length_revision_plan`] against an already-computed physical scan.
pub(crate) fn build_length_revision_plan_with(
    input: &[u8],
    limits: Limits,
    physical: &PdfPhysical,
) -> Result<Option<LengthRevisionPlan>> {
    // Preconditions: classic cross-reference table, no xref stream, bounded
    // object count (object slots are indices `0..n_obj`).
    if !physical
        .spans
        .iter()
        .any(|s| s.kind == PhysicalKind::XrefSection)
    {
        return Ok(None);
    }
    if physical
        .objects
        .iter()
        .any(|o| o.role == ObjRole::XRefStream)
    {
        return Ok(None);
    }
    let n_obj = physical.objects.len();
    if n_obj > MAX_MARKED_OBJECTS {
        return Ok(None);
    }

    let lexed = match lex(input, limits) {
        Ok(l) => l,
        Err(_) => return Ok(None),
    };
    let spans: Vec<Span> = lexed.spans.spans;
    let total = input.len() as u64;

    // Per-revision xref anchors, in file order.
    let xref_sections: Vec<(u64, u64)> = physical
        .spans
        .iter()
        .filter(|s| s.kind == PhysicalKind::XrefSection)
        .map(|s| (s.start, s.len))
        .collect();
    let n_xref = xref_sections.len();
    // Object slots `0..n_obj`, revision slots `n_obj..n_obj+n_xref`; the length
    // slots are handed out from `255` downward (see below).
    if n_obj + n_xref > MAX_OFFSET_SLOTS {
        return Ok(None);
    }
    let xref_starts: Vec<u64> = xref_sections.iter().map(|&(s, _)| s).collect();

    // (offset, order, event): order 0 sorts marks before emits at one offset.
    let mut events: Vec<(u64, u8, Event)> = Vec::new();

    // 1. Object introducer marks (one slot per object).
    for (i, o) in physical.objects.iter().enumerate() {
        events.push((o.start, 0, Event::Mark(i as u8)));
    }

    // 2. xref section anchors (one slot per revision) + entry offset prediction.
    let mut xref_predicted = 0usize;
    let mut xref_literal = 0usize;
    for (r, &(start, len)) in xref_sections.iter().enumerate() {
        events.push((start, 0, Event::Mark((n_obj + r) as u8)));
        let bytes = &input[start as usize..(start + len) as usize];
        if let Some(pieces) = parse_classic_xref(bytes) {
            for piece in pieces {
                if let XrefPiece::Entry {
                    start: at,
                    number,
                    offset,
                    in_use,
                } = piece
                {
                    let target = if in_use {
                        offset.and_then(|off| {
                            physical
                                .objects
                                .iter()
                                .position(|o| o.number == number && o.start == off)
                        })
                    } else {
                        None
                    };
                    match target {
                        Some(i) => {
                            events.push((
                                start + at as u64,
                                1,
                                Event::Emit {
                                    slot: i as u8,
                                    width: 10,
                                },
                            ));
                            xref_predicted += 1;
                        }
                        None => xref_literal += 1,
                    }
                }
            }
        }
    }

    // 3. `startxref` values: equal to the revision's own xref anchor offset.
    let mut startxref_predicted = 0usize;
    for s in &physical.spans {
        if s.kind != PhysicalKind::StartXref {
            continue;
        }
        if let Some((field_start, width, value)) =
            trailing_digits(input, &spans, s.start, s.start + s.len)
            && let Some(r) = xref_starts.iter().position(|&x| x == value)
            && field_start > xref_starts[r]
        {
            events.push((
                field_start,
                1,
                Event::Emit {
                    slot: (n_obj + r) as u8,
                    width,
                },
            ));
            startxref_predicted += 1;
        }
    }

    // 4. trailer `/Prev`: an absolute offset of an earlier revision anchor (or,
    //    for an indirect reference, of the referenced object's introducer).
    let mut prev_predicted = 0usize;
    for (idx, sp) in spans.iter().enumerate() {
        if sp.kind != SpanKind::Name || span_bytes(input, *sp) != Some(b"/Prev".as_slice()) {
            continue;
        }
        let Some(t0) = next_significant_in(&spans, idx + 1, total) else {
            continue;
        };
        if spans[t0].kind != SpanKind::Regular {
            continue;
        }
        let Some(bytes) = span_bytes(input, spans[t0]) else {
            continue;
        };
        if bytes.is_empty() || !bytes.iter().all(u8::is_ascii_digit) {
            continue;
        }
        let Some(value) = parse_digits(bytes) else {
            continue;
        };
        let field_start = spans[t0].start;
        let width = spans[t0].len;
        if width == 0 || width > 20 || value >= field_start {
            continue;
        }
        let slot = xref_starts
            .iter()
            .position(|&x| x == value)
            .map(|r| (n_obj + r) as u8)
            .or_else(|| {
                physical
                    .objects
                    .iter()
                    .position(|o| o.start == value)
                    .map(|i| i as u8)
            });
        if let Some(slot) = slot {
            events.push((
                field_start,
                1,
                Event::Emit {
                    slot,
                    width: width as u8,
                },
            ));
            prev_predicted += 1;
        }
    }

    // 5. `/Length` fields of directly-sized streams: (field_start, width, value).
    let length_fields = collect_length_fields(input, &spans, physical);
    let mut length_literal = length_fields.len();

    // Forbid a length mark anywhere inside a fixed-width emitted field (an xref
    // entry, `startxref`, `/Prev`, or any `/Length` field): those offsets cannot
    // host a zero-width mark without splitting a field.
    let mut forbid: Vec<(u64, u64)> = Vec::new();
    for (off, _, ev) in &events {
        if let Event::Emit { width, .. } = ev {
            forbid.push((*off, off + *width as u64));
        }
    }
    for &(fs, w, _) in &length_fields {
        forbid.push((fs, fs + w as u64));
    }
    let forbidden = |off: u64| forbid.iter().any(|&(a, b)| off >= a && off < b);

    // Distinct regenerable lengths, ascending for a deterministic slot map.
    let mut distinct: Vec<u64> = length_fields
        .iter()
        .filter(|&&(fs, _, v)| v < fs && !forbidden(v))
        .map(|&(_, _, v)| v)
        .collect();
    distinct.sort_unstable();
    distinct.dedup();
    let max_len_slots = MAX_OFFSET_SLOTS - (n_obj + n_xref);
    distinct.truncate(max_len_slots);
    let len_slot: Vec<(u64, u8)> = distinct
        .iter()
        .enumerate()
        .map(|(k, &v)| (v, (MAX_OFFSET_SLOTS - 1 - k) as u8))
        .collect();

    let mut length_predicted = 0usize;
    for &(fs, w, v) in &length_fields {
        let Some(slot) = len_slot.iter().find(|&&(lv, _)| lv == v).map(|&(_, s)| s) else {
            continue;
        };
        if v >= fs {
            continue;
        }
        events.push((fs, 1, Event::Emit { slot, width: w }));
        length_predicted += 1;
    }
    length_literal -= length_predicted;
    for &(v, slot) in &len_slot {
        events.push((v, 0, Event::Mark(slot)));
    }

    // Assemble: order events by output offset; copy the gaps into the data
    // object; render marks and fixed-width emits. Positions track source offsets
    // exactly, so every regenerated field consumes the same width it replaces.
    events.sort_by(|a, b| a.0.cmp(&b.0).then(a.1.cmp(&b.1)));
    let mut items: Vec<PackItem> = Vec::new();
    let mut data: Vec<u8> = Vec::new();
    let mut pos: u64 = 0;
    for (off, _, ev) in events {
        if off > total || off < pos {
            return Ok(None);
        }
        if off > pos {
            if !push_literal(&mut items, &mut data, &input[pos as usize..off as usize]) {
                return Ok(None);
            }
            pos = off;
        }
        match ev {
            Event::Mark(slot) => items.push(PackItem::Mark { slot }),
            Event::Emit { slot, width } => {
                items.push(PackItem::Emit { slot, width });
                pos += width as u64;
            }
        }
    }
    if pos < total && !push_literal(&mut items, &mut data, &input[pos as usize..]) {
        return Ok(None);
    }

    Ok(Some(LengthRevisionPlan {
        items,
        data,
        objects_marked: n_obj,
        revisions_marked: n_xref,
        xref_predicted,
        xref_literal,
        startxref_predicted,
        prev_predicted,
        length_predicted,
        length_literal,
    }))
}

/// Propose a `/Length` + revision-chain candidate, or `None`.
///
/// Wraps [`build_length_revision_plan`] into one [`Op::PackSegments`] program
/// over one literal data object and verifies the finished candidate end to end
/// through the normative decoder (serialize → parse → materialize →
/// byte-compare); an inexact program declines rather than being emitted.
pub fn propose_pdf_length_revision(input: &[u8], limits: Limits) -> Result<Option<Candidate>> {
    let physical = match scan(input, limits) {
        Ok(p) => p,
        Err(_) => return Ok(None),
    };
    propose_pdf_length_revision_with(input, limits, &physical)
}

/// [`propose_pdf_length_revision`] against an already-computed physical scan.
pub(crate) fn propose_pdf_length_revision_with(
    input: &[u8],
    limits: Limits,
    physical: &PdfPhysical,
) -> Result<Option<Candidate>> {
    let plan = match build_length_revision_plan_with(input, limits, physical)? {
        Some(p) => p,
        None => return Ok(None),
    };

    let format_basis = format!(
        "pdf-length-revision;objects={};revisions={};xref_predicted={};xref_literal={};\
         startxref_predicted={};prev_predicted={};length_predicted={};length_literal={}",
        plan.objects_marked,
        plan.revisions_marked,
        plan.xref_predicted,
        plan.xref_literal,
        plan.startxref_predicted,
        plan.prev_predicted,
        plan.length_predicted,
        plan.length_literal,
    );

    let descriptor = Descriptor {
        universe: UNIVERSE.to_string(),
        source_format: SOURCE_FORMAT_PDF,
        format_basis,
        models: vec![],
        channels: vec![],
        objects: vec![ObjectSource::Inline(plan.data)],
        program: Program::new(vec![Op::PackSegments {
            data_object: 0,
            items: plan.items,
        }]),
        observation_index: None,
        seek_directory: false,
        checkpoints: None,
        source_sha256: sha256(input),
        source_len: input.len() as u64,
    };

    let candidate = Candidate {
        kind: CandidateKind::PdfLengthRevision,
        descriptor,
    };

    // Verify byte-exactness through the normative decoder before returning.
    let (encoded, _) = candidate.descriptor.serialize()?;
    let parsed = match Descriptor::parse(&encoded, limits) {
        Ok(p) => p,
        Err(_) => return Ok(None),
    };
    let out = match crate::materialize::materialize(&parsed, limits) {
        Ok(o) => o,
        Err(_) => return Ok(None),
    };
    if out != input {
        return Ok(None);
    }

    Ok(Some(candidate))
}

/// `(field_start, width, value)` of every directly-sized stream's `/Length`
/// field: the first `Name` span `/Length` in the enclosing object's byte range,
/// followed by a simple `Regular` decimal whose value is the resolved payload
/// length and which is not the head of an `int int R` reference.
fn collect_length_fields(
    input: &[u8],
    spans: &[Span],
    physical: &super::physical::PdfPhysical,
) -> Vec<(u64, u8, u64)> {
    let mut out = Vec::new();
    for stream in &physical.streams {
        if stream.length_source != LengthSource::Direct {
            continue;
        }
        let Some(obj) = physical
            .objects
            .iter()
            .find(|o| o.number == stream.object && o.generation == stream.generation)
        else {
            continue;
        };
        let (lo, hi) = (obj.start, obj.end);
        // First `/Length` name fully inside the object range.
        let start_idx = spans.partition_point(|s| s.start < lo);
        let mut name_idx = None;
        let mut j = start_idx;
        while j < spans.len() && spans[j].start < hi {
            if spans[j].kind == SpanKind::Name
                && spans[j].start + spans[j].len <= hi
                && span_bytes(input, spans[j]) == Some(b"/Length".as_slice())
            {
                name_idx = Some(j);
                break;
            }
            j += 1;
        }
        let Some(ni) = name_idx else { continue };
        let Some(t0) = next_significant_in(spans, ni + 1, hi) else {
            continue;
        };
        if spans[t0].kind != SpanKind::Regular {
            continue;
        }
        let Some(bytes) = span_bytes(input, spans[t0]) else {
            continue;
        };
        if bytes.is_empty() || !bytes.iter().all(u8::is_ascii_digit) {
            continue;
        }
        let Some(value) = parse_digits(bytes) else {
            continue;
        };
        // Reject the reference shape `int Whitespace int Whitespace R`.
        if let Some(t1) = next_significant_in(spans, t0 + 1, hi)
            && spans[t1].kind == SpanKind::Regular
            && next_significant_in(spans, t1 + 1, hi).is_some_and(|t2| {
                spans[t2].kind == SpanKind::Regular && bytes_eq(input, spans[t2], b"R")
            })
        {
            continue;
        }
        if value != stream.data_len {
            continue;
        }
        let width = spans[t0].len;
        if width == 0 || width > 20 {
            continue;
        }
        out.push((spans[t0].start, width as u8, value));
    }
    out
}

/// Byte range for a span, or `None` when it leaves the input.
fn span_bytes(input: &[u8], sp: Span) -> Option<&[u8]> {
    let start = usize::try_from(sp.start).ok()?;
    let end = usize::try_from(sp.start.checked_add(sp.len)?).ok()?;
    if start > end || end > input.len() {
        return None;
    }
    Some(&input[start..end])
}

/// Whether `sp`'s bytes equal `want`.
fn bytes_eq(input: &[u8], sp: Span, want: &[u8]) -> bool {
    sp.kind == SpanKind::Regular && span_bytes(input, sp) == Some(want)
}

/// Index of the next non-whitespace, non-comment span at or after `from` whose
/// start is before `hi`.
fn next_significant_in(spans: &[Span], from: usize, hi: u64) -> Option<usize> {
    let mut j = from;
    while j < spans.len() {
        let sp = spans[j];
        if sp.start >= hi {
            return None;
        }
        match sp.kind {
            SpanKind::Whitespace | SpanKind::Comment => j += 1,
            _ => return Some(j),
        }
    }
    None
}

/// The trailing run of decimal digits of the field spanning `[lo, hi)` in the
/// lexed cover, as `(start, width, value)`. `None` when it is not one simple
/// `Regular` decimal within `1..=20` bytes.
fn trailing_digits(input: &[u8], spans: &[Span], lo: u64, hi: u64) -> Option<(u64, u8, u64)> {
    let mut found: Option<(u64, u8, u64)> = None;
    for sp in spans {
        if sp.start < lo {
            continue;
        }
        if sp.start + sp.len > hi {
            break;
        }
        if sp.kind != SpanKind::Regular {
            continue;
        }
        let bytes = span_bytes(input, *sp)?;
        if bytes.is_empty() || !bytes.iter().all(u8::is_ascii_digit) || bytes.len() > 20 {
            continue;
        }
        let value = parse_digits(bytes)?;
        found = Some((sp.start, bytes.len() as u8, value));
    }
    found
}

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

    fn classic_pdf() -> Vec<u8> {
        // A tiny classic-cross-reference PDF with three streams and a correct
        // xref table + startxref, computed so offsets agree by construction.
        let mut offsets = vec![0usize; 5];
        let push = |s: &mut String, offsets: &mut [usize], n: usize, body: &str| {
            offsets[n] = s.len();
            s.push_str(&format!("{n} 0 obj\n{body}\nendobj\n"));
        };
        let mut s = String::from("%PDF-1.7\n");
        push(&mut s, &mut offsets, 1, "<< /Type /Catalog /Pages 2 0 R >>");
        push(
            &mut s,
            &mut offsets,
            2,
            "<< /Length 6 >>\nstream\nhello\nendstream",
        );
        push(
            &mut s,
            &mut offsets,
            3,
            "<< /Length 7 >>\nstream\nworld!\nendstream",
        );
        push(
            &mut s,
            &mut offsets,
            4,
            "<< /Length 4 >>\nstream\nxyz\nendstream",
        );
        let xref_at = s.len();
        s.push_str("xref\n0 5\n0000000000 65535 f \n");
        for off in offsets.iter().skip(1) {
            s.push_str(&format!("{off:010} 00000 n \n"));
        }
        s.push_str("trailer\n<< /Size 5 /Root 1 0 R >>\n");
        s.push_str(&format!("startxref\n{xref_at}\n%%EOF"));
        s.into_bytes()
    }

    fn exact(name: &str, bytes: &[u8]) {
        let cand = propose_pdf_length_revision(bytes, Limits::DEFAULT)
            .unwrap()
            .unwrap_or_else(|| panic!("{name} must propose the length/revision candidate"));
        assert_eq!(cand.kind, CandidateKind::PdfLengthRevision);
        assert_eq!(cand.descriptor.source_len, bytes.len() as u64);
        let (encoded, _) = cand.descriptor.serialize().unwrap();
        let parsed = Descriptor::parse(&encoded, Limits::DEFAULT).unwrap();
        let out = crate::materialize::materialize(&parsed, Limits::DEFAULT).unwrap();
        assert_eq!(out, bytes, "{name} materializes byte-exactly");
        assert_eq!(sha256(&out), sha256(bytes), "{name} sha256");

        // The forced lane must survive the court's own decode-before-commit.
        let (forced, report) = crate::encode::encode_with(
            bytes,
            Limits::DEFAULT,
            Some(CandidateKind::PdfLengthRevision),
        )
        .unwrap();
        assert_eq!(report.kind, CandidateKind::PdfLengthRevision);
        let (forced_out, _) =
            crate::materialize::decode_to_bytes(&forced, Limits::DEFAULT).unwrap();
        assert_eq!(forced_out, bytes, "{name} forced bytes");
    }

    #[test]
    fn exact_on_classic_pdf() {
        exact("classic", &classic_pdf());
    }

    #[test]
    fn predicate_lengths_and_xref() {
        let bytes = classic_pdf();
        let plan = build_length_revision_plan(&bytes, Limits::DEFAULT)
            .unwrap()
            .unwrap();
        // All three direct `/Length` values are small and every field appears
        // after its own length offset, so all three are regenerated.
        assert_eq!(plan.length_predicted, 3, "length_predicted");
        assert_eq!(plan.length_literal, 0, "length_literal");
        assert!(plan.xref_predicted >= 1, "at least one xref offset");
        assert_eq!(plan.startxref_predicted, 1, "one startxref");
        assert!(
            plan.items
                .iter()
                .any(|i| matches!(i, PackItem::Emit { .. }))
        );
    }

    #[test]
    fn declines_on_non_pdf() {
        assert!(
            propose_pdf_length_revision(b"not a pdf at all", Limits::DEFAULT)
                .unwrap()
                .is_none(),
            "a non-PDF must decline"
        );
    }

    #[test]
    fn deterministic() {
        let bytes = classic_pdf();
        let a = propose_pdf_length_revision(&bytes, Limits::DEFAULT)
            .unwrap()
            .unwrap()
            .descriptor
            .serialize()
            .unwrap()
            .0;
        let b = propose_pdf_length_revision(&bytes, Limits::DEFAULT)
            .unwrap()
            .unwrap()
            .descriptor
            .serialize()
            .unwrap()
            .0;
        assert_eq!(a, b, "encode must be deterministic");
    }

    #[test]
    fn exact_on_sample_corpus() {
        use super::super::samples::{is_negative_control, sample_pdfs};
        let mut proposed = 0;
        for (name, bytes) in sample_pdfs() {
            if is_negative_control(name) {
                continue;
            }
            if propose_pdf_length_revision(&bytes, Limits::DEFAULT)
                .unwrap()
                .is_some()
            {
                exact(name, &bytes);
                proposed += 1;
            }
        }
        assert!(proposed >= 1, "must apply to at least one sample");
    }
}