//! Reading the pages of a PDF document.

use crate::content::{TypedIter, UntypedIter};
use crate::object::Array;
use crate::object::Dict;
use crate::object::Name;
use crate::object::Rect;
use crate::object::Stream;
use crate::object::dict::keys::*;
use crate::object::{Object, ObjectIdentifier, ObjectLike};
use crate::reader::ReaderContext;
use crate::sync::OnceLock;
use crate::util::FloatExt;
use crate::xref::XRef;
use alloc::boxed::Box;
use alloc::collections::BTreeSet;
use alloc::vec;
use alloc::vec::Vec;
use core::ops::Deref;
use log::warn;

/// Attributes that can be inherited.
#[derive(Debug, Clone)]
struct PagesContext {
    media_box: Option<Rect>,
    crop_box: Option<Rect>,
    rotate: Option<u32>,
}

impl PagesContext {
    fn new() -> Self {
        Self {
            media_box: None,
            crop_box: None,
            rotate: None,
        }
    }
}

/// A structure holding the pages of a PDF document.
pub struct Pages<'a> {
    pages: Vec<Page<'a>>,
    xref: &'a XRef,
}

impl<'a> Pages<'a> {
    /// Create a new `Pages` object.
    pub(crate) fn new(
        pages_dict: &Dict<'a>,
        ctx: &ReaderContext<'a>,
        xref: &'a XRef,
    ) -> Option<Self> {
        let mut pages = vec![];
        let pages_ctx = PagesContext::new();
        resolve_pages(
            pages_dict,
            &mut pages,
            pages_ctx,
            Resources::new(Dict::empty(), None, ctx),
        )?;

        Some(Self { pages, xref })
    }

    /// Create a new `Pages` object by bruteforce-searching.
    ///
    /// Of course this could result in the order of pages being messed up, but
    /// this is still better than nothing.
    pub(crate) fn new_brute_force(ctx: &ReaderContext<'a>, xref: &'a XRef) -> Option<Self> {
        let mut pages = vec![];

        for object in xref.objects() {
            if let Some(dict) = object.into_dict()
                && let Some(page) = Page::new(
                    &dict,
                    &PagesContext::new(),
                    Resources::new(Dict::empty(), None, ctx),
                    true,
                )
            {
                pages.push(page);
            }
        }

        if pages.is_empty() {
            return None;
        }

        Some(Self { pages, xref })
    }

    /// Return the xref table (of the document the pages belong to).   
    pub fn xref(&self) -> &'a XRef {
        self.xref
    }
}

impl<'a> Deref for Pages<'a> {
    type Target = [Page<'a>];

    fn deref(&self) -> &Self::Target {
        &self.pages
    }
}

/// Maximum depth for recursive page tree traversal.
/// Prevents stack overflow on malformed PDFs with deeply nested or circular page trees.
const MAX_PAGE_TREE_DEPTH: usize = 256;

/// Maximum number of pages to collect from the page tree.
/// Prevents exponential blowup from "page tree bombs" where shared Kids nodes
/// cause the same subtrees to be visited multiple times (e.g., 8 KB PDF → 2^27 pages).
const MAX_PAGE_COUNT: usize = 100_000;

fn resolve_pages<'a>(
    pages_dict: &Dict<'a>,
    entries: &mut Vec<Page<'a>>,
    ctx: PagesContext,
    resources: Resources<'a>,
) -> Option<()> {
    let max_depth = resources
        .ctx
        .load_limits()
        .object_depth_limit()
        .map(|d| d as usize)
        .unwrap_or(MAX_PAGE_TREE_DEPTH);

    let mut visited = BTreeSet::new();
    resolve_pages_depth(
        pages_dict,
        entries,
        ctx,
        resources,
        0,
        max_depth,
        &mut visited,
    )
}

fn resolve_pages_depth<'a>(
    pages_dict: &Dict<'a>,
    entries: &mut Vec<Page<'a>>,
    mut ctx: PagesContext,
    resources: Resources<'a>,
    depth: usize,
    max_depth: usize,
    visited: &mut BTreeSet<ObjectIdentifier>,
) -> Option<()> {
    if depth > max_depth {
        log::warn!("Page tree depth exceeds {max_depth}, stopping traversal");
        return None;
    }

    // Cycle protection: a /Pages node reachable from itself (directly or via a
    // /Kids back-reference) would otherwise be re-walked, duplicating pages and
    // wasting work up to the depth cap. Stop the first time a node is re-entered.
    // Inline (non-indirect) nodes have no object id and are simply not tracked.
    if let Some(node_id) = pages_dict.obj_id()
        && !visited.insert(node_id)
    {
        log::warn!("Page tree cycle detected at {node_id:?}, stopping traversal");
        return Some(());
    }

    if let Some(media_box) = pages_dict.get::<Rect>(MEDIA_BOX) {
        ctx.media_box = Some(media_box);
    }

    if let Some(crop_box) = pages_dict.get::<Rect>(CROP_BOX) {
        ctx.crop_box = Some(crop_box);
    }

    // /Rotate may be negative (e.g. -90), which is valid per the PDF spec.
    // Normalise to [0, 360) via Euclidean remainder so u32 storage is safe.
    if let Some(rotate) = pages_dict.get::<i32>(ROTATE) {
        ctx.rotate = Some(rotate.rem_euclid(360) as u32);
    }

    let resources = Resources::from_parent(
        pages_dict.get::<Dict<'_>>(RESOURCES).unwrap_or_default(),
        resources.clone(),
    );

    let kids = pages_dict.get::<Array<'a>>(KIDS)?;

    for dict in kids.iter::<Dict<'_>>() {
        if entries.len() >= MAX_PAGE_COUNT {
            log::warn!("Page count exceeds {MAX_PAGE_COUNT}, stopping page tree traversal");
            return Some(());
        }

        match dict.get::<Name>(TYPE).as_deref() {
            Some(PAGES) => {
                resolve_pages_depth(
                    &dict,
                    entries,
                    ctx.clone(),
                    resources.clone(),
                    depth + 1,
                    max_depth,
                    visited,
                );
            }
            // Let's be lenient and assume it's a `Page` in case it's `None` or something else
            // (see corpus test case 0083781).
            _ => {
                if let Some(page) = Page::new(&dict, &ctx, resources.clone(), false) {
                    entries.push(page);
                }
            }
        }
    }

    Some(())
}

/// The rotation of the page.
#[derive(Debug, Copy, Clone)]
pub enum Rotation {
    /// No rotation.
    None,
    /// A rotation of 90 degrees.
    Horizontal,
    /// A rotation of 180 degrees.
    Flipped,
    /// A rotation of 270 degrees.
    FlippedHorizontal,
}

/// A PDF page.
pub struct Page<'a> {
    inner: Dict<'a>,
    media_box: Rect,
    crop_box: Rect,
    rotation: Rotation,
    page_streams: OnceLock<Option<Vec<u8>>>,
    resources: Resources<'a>,
    ctx: ReaderContext<'a>,
}

impl<'a> Page<'a> {
    fn new(
        dict: &Dict<'a>,
        ctx: &PagesContext,
        resources: Resources<'a>,
        brute_force: bool,
    ) -> Option<Self> {
        // In general, pages without content are allowed, but in case we are brute-forcing
        // we ignore them.
        if brute_force && !dict.contains_key(CONTENTS) {
            return None;
        }

        let media_box = dict
            .get::<Rect>(MEDIA_BOX)
            .or(ctx.media_box)
            .unwrap_or(US_LETTER);

        let crop_box = dict
            .get::<Rect>(CROP_BOX)
            .or(ctx.crop_box)
            .unwrap_or(media_box);

        let rotation = match dict
            .get::<i32>(ROTATE)
            .map(|r| r.rem_euclid(360) as u32)
            .or(ctx.rotate)
            .unwrap_or(0)
        {
            0 => Rotation::None,
            90 => Rotation::Horizontal,
            180 => Rotation::Flipped,
            270 => Rotation::FlippedHorizontal,
            _ => Rotation::None,
        };

        let ctx = resources.ctx.clone();
        let resources = Resources::from_parent(
            dict.get::<Dict<'_>>(RESOURCES).unwrap_or_default(),
            resources,
        );

        Some(Self {
            inner: dict.clone(),
            media_box,
            crop_box,
            rotation,
            page_streams: OnceLock::new(),
            resources,
            ctx,
        })
    }

    fn operations_impl(&self) -> Option<UntypedIter<'_>> {
        let stream = self.page_stream()?;
        let iter = UntypedIter::new(stream);

        Some(iter)
    }

    /// Return the decoded content stream of the page.
    pub fn page_stream(&self) -> Option<&[u8]> {
        let convert_single = |s: Stream<'_>| {
            let data = s.decoded().ok()?;
            Some(data.to_vec())
        };

        self.page_streams
            .get_or_init(|| {
                if let Some(stream) = self.inner.get::<Stream<'_>>(CONTENTS) {
                    convert_single(stream)
                } else if let Some(array) = self.inner.get::<Array<'_>>(CONTENTS) {
                    let streams = array.iter::<Stream<'_>>().flat_map(convert_single);

                    let mut collected = vec![];

                    for stream in streams {
                        collected.extend(stream);
                        // Streams must have at least one whitespace in-between.
                        collected.push(b' ');
                    }

                    Some(collected)
                } else {
                    warn!("contents entry of page was neither stream nor array of streams");

                    None
                }
            })
            .as_ref()
            .map(|d| d.as_slice())
    }

    /// Get the resources of the page.
    pub fn resources(&self) -> &Resources<'a> {
        &self.resources
    }

    /// Get the media box of the page.
    pub fn media_box(&self) -> Rect {
        self.media_box
    }

    /// Get the rotation of the page.
    pub fn rotation(&self) -> Rotation {
        self.rotation
    }

    /// Get the crop box of the page.
    pub fn crop_box(&self) -> Rect {
        self.crop_box
    }

    /// Return the intersection of crop box and media box.
    pub fn intersected_crop_box(&self) -> Rect {
        self.crop_box().intersect(self.media_box())
    }

    /// Return the base dimensions of the page used for the canvas size.
    ///
    /// When the CropBox origin is within the MediaBox (i.e. CropBox.x0 >=
    /// MediaBox.x0 and CropBox.y0 >= MediaBox.y0), the canvas is sized to
    /// intersect(CropBox, MediaBox).  This matches MuPDF's behaviour for
    /// spec-violating PDFs where CropBox.y1 > MediaBox.y1 (e.g. gen-271:
    /// CropBox=[0,0,595,793.7] vs MediaBox=[0,0,612,792] — using raw
    /// CropBox gives 1654px height, a 4px vertical content offset, and
    /// SSIM 0.49; intersecting gives 1650px matching MuPDF exactly).
    ///
    /// When CropBox extends below the MediaBox origin (gen-802 style:
    /// CropBox=[0,0,684,864] vs MediaBox=[36,36,648,828]), MuPDF still uses
    /// the full CropBox dimensions, so we do too. (#544, #558, gen-271)
    pub fn base_dimensions(&self) -> (f32, f32) {
        let crop_box = self.crop_box();
        let media_box = self.media_box();

        // Clip to MediaBox only when the CropBox origin lies within the
        // MediaBox (both axes).  When the CropBox extends below the MediaBox
        // origin MuPDF uses the raw CropBox, so preserve that behaviour.
        let effective = if crop_box.x0 >= media_box.x0 && crop_box.y0 >= media_box.y0 {
            crop_box.intersect(media_box)
        } else {
            crop_box
        };

        if (effective.width() as f32).is_nearly_zero()
            || (effective.height() as f32).is_nearly_zero()
        {
            (US_LETTER.width() as f32, US_LETTER.height() as f32)
        } else {
            (
                effective.width().max(1.0) as f32,
                effective.height().max(1.0) as f32,
            )
        }
    }

    /// Return the with and height of the page that should be assumed when rendering the page.
    ///
    /// Depending on the document, it is either based on the media box or the crop box
    /// of the page. In addition to that, it also takes the rotation of the page into account.
    pub fn render_dimensions(&self) -> (f32, f32) {
        let (mut base_width, mut base_height) = self.base_dimensions();

        if matches!(
            self.rotation(),
            Rotation::Horizontal | Rotation::FlippedHorizontal
        ) {
            core::mem::swap(&mut base_width, &mut base_height);
        }

        (base_width, base_height)
    }

    /// Return an untyped iterator over the operators of the page's content stream.
    pub fn operations(&self) -> UntypedIter<'_> {
        self.operations_impl().unwrap_or(UntypedIter::empty())
    }

    /// Get the raw dictionary of the page.
    pub fn raw(&self) -> &Dict<'a> {
        &self.inner
    }

    /// Get the xref table (of the document the page belongs to).
    pub fn xref(&self) -> &'a XRef {
        self.ctx.xref()
    }

    /// Return a typed iterator over the operators of the page's content stream.
    pub fn typed_operations(&self) -> TypedIter<'_> {
        TypedIter::from_untyped(self.operations())
    }

    /// Return the annotation dictionaries for this page, if any.
    pub fn annots(&self) -> Vec<Dict<'a>> {
        self.inner
            .get::<Array<'_>>(crate::object::dict::keys::ANNOTS)
            .map(|arr| arr.iter::<Dict<'_>>().collect())
            .unwrap_or_default()
    }
}

/// A structure keeping track of the resources of a page.
#[derive(Clone, Debug)]
pub struct Resources<'a> {
    parent: Option<Box<Self>>,
    ctx: ReaderContext<'a>,
    /// The raw dictionary of external graphics states.
    pub ext_g_states: Dict<'a>,
    /// The raw dictionary of fonts.
    pub fonts: Dict<'a>,
    /// The raw dictionary of properties.
    pub properties: Dict<'a>,
    /// The raw dictionary of color spaces.
    pub color_spaces: Dict<'a>,
    /// The raw dictionary of x objects.
    pub x_objects: Dict<'a>,
    /// The raw dictionary of patterns.
    pub patterns: Dict<'a>,
    /// The raw dictionary of shadings.
    pub shadings: Dict<'a>,
}

impl<'a> Resources<'a> {
    /// Create a new `Resources` object from a dictionary with a parent.
    pub fn from_parent(resources: Dict<'a>, parent: Self) -> Self {
        let ctx = parent.ctx.clone();

        Self::new(resources, Some(parent), &ctx)
    }

    /// Create a new `Resources` object.
    pub(crate) fn new(resources: Dict<'a>, parent: Option<Self>, ctx: &ReaderContext<'a>) -> Self {
        let ext_g_states = resources.get::<Dict<'_>>(EXT_G_STATE).unwrap_or_default();
        let fonts = resources.get::<Dict<'_>>(FONT).unwrap_or_default();
        let color_spaces = resources.get::<Dict<'_>>(COLORSPACE).unwrap_or_default();
        let x_objects = resources.get::<Dict<'_>>(XOBJECT).unwrap_or_default();
        let patterns = resources.get::<Dict<'_>>(PATTERN).unwrap_or_default();
        let shadings = resources.get::<Dict<'_>>(SHADING).unwrap_or_default();
        let properties = resources.get::<Dict<'_>>(PROPERTIES).unwrap_or_default();

        let parent = parent.map(Box::new);

        Self {
            parent,
            ext_g_states,
            fonts,
            color_spaces,
            properties,
            x_objects,
            patterns,
            shadings,
            ctx: ctx.clone(),
        }
    }

    fn get_resource<T: ObjectLike<'a>>(&self, name: Name, dict: &Dict<'a>) -> Option<T> {
        dict.get::<T>(name.deref())
    }

    /// Get the parent in the resource, chain, if available.
    pub fn parent(&self) -> Option<&Self> {
        self.parent.as_deref()
    }

    /// Get an external graphics state by name.
    pub fn get_ext_g_state(&self, name: Name) -> Option<Dict<'a>> {
        self.get_resource::<Dict<'_>>(name.clone(), &self.ext_g_states)
            .or_else(|| self.parent.as_ref().and_then(|p| p.get_ext_g_state(name)))
    }

    /// Get a color space by name.
    pub fn get_color_space(&self, name: Name) -> Option<Object<'a>> {
        self.get_resource::<Object<'_>>(name.clone(), &self.color_spaces)
            .or_else(|| self.parent.as_ref().and_then(|p| p.get_color_space(name)))
    }

    /// Get a font by name.
    pub fn get_font(&self, name: Name) -> Option<Dict<'a>> {
        self.get_resource::<Dict<'_>>(name.clone(), &self.fonts)
            .or_else(|| self.parent.as_ref().and_then(|p| p.get_font(name)))
    }

    /// Get a pattern by name.
    pub fn get_pattern(&self, name: Name) -> Option<Object<'a>> {
        self.get_resource::<Object<'_>>(name.clone(), &self.patterns)
            .or_else(|| self.parent.as_ref().and_then(|p| p.get_pattern(name)))
    }

    /// Get an x object by name.
    pub fn get_x_object(&self, name: Name) -> Option<Stream<'a>> {
        self.get_resource::<Stream<'_>>(name.clone(), &self.x_objects)
            .or_else(|| self.parent.as_ref().and_then(|p| p.get_x_object(name)))
    }

    /// Get a shading by name.
    pub fn get_shading(&self, name: Name) -> Option<Object<'a>> {
        self.get_resource::<Object<'_>>(name.clone(), &self.shadings)
            .or_else(|| self.parent.as_ref().and_then(|p| p.get_shading(name)))
    }
}

// <https://github.com/apache/pdfbox/blob/a53a70db16ea3133994120bcf1e216b9e760c05b/pdfbox/src/main/java/org/apache/pdfbox/pdmodel/common/PDRectangle.java#L38>
const POINTS_PER_INCH: f64 = 72.0;
const POINTS_PER_MM: f64 = 1.0 / (10.0 * 2.54) * POINTS_PER_INCH;

/// The dimension of an A4 page (kept for completeness).
pub const A4: Rect = Rect {
    x0: 0.0,
    y0: 0.0,
    x1: 210.0 * POINTS_PER_MM,
    y1: 297.0 * POINTS_PER_MM,
};

/// US Letter (8.5×11 in) — used as fallback when no MediaBox is present.
///
/// Old PDF 1.0/1.1 documents (especially US-government publications from the
/// 1990s) omit MediaBox entirely and assume a US-Letter canvas, which matches
/// the PostScript default and MuPDF's behaviour.  Using A4 here causes a
/// ~5 % scale mismatch that tanks SSIM against MuPDF's oracle renders.
/// See render_mupdf_oracle failures gen-059, gen-069, …  (#544)
const US_LETTER: Rect = Rect {
    x0: 0.0,
    y0: 0.0,
    x1: 8.5 * POINTS_PER_INCH,
    y1: 11.0 * POINTS_PER_INCH,
};

pub(crate) mod cached {
    use crate::page::Pages;
    use crate::reader::ReaderContext;
    use crate::xref::XRef;
    use core::ops::Deref;

    // Keep in sync with the implementation in `sync`. We duplicate it here
    // to make it more visible since we have unsafe code here.
    #[cfg(feature = "std")]
    pub(crate) use std::sync::Arc;

    #[cfg(not(feature = "std"))]
    pub(crate) use alloc::rc::Rc as Arc;

    pub(crate) struct CachedPages {
        pages: Pages<'static>,
        // NOTE: `pages` references the data in `xref`, so it's important that `xref`
        // appears after `pages` in the struct definition to ensure correct drop order.
        _xref: Arc<XRef>,
        /// `true` if the normal page-tree walk failed and pages were recovered
        /// via brute-force scan (page order may differ from the source).
        page_tree_rebuilt: bool,
    }

    impl CachedPages {
        pub(crate) fn new(xref: Arc<XRef>) -> Option<Self> {
            // SAFETY:
            // - The XRef's location is stable in memory:
            //   - We wrapped it in a `Arc` (or `Rc` in `no_std`), which implements `StableDeref`.
            //   - The struct owns the `Arc`, ensuring that the inner value is not dropped during the whole
            //     duration.
            // - The internal 'static lifetime is not leaked because its rewritten
            //   to the self-lifetime in `pages()`.
            let xref_reference: &'static XRef = unsafe { core::mem::transmute(xref.deref()) };

            let ctx = ReaderContext::new(xref_reference, false);
            // Detect whether the normal page-tree walk succeeded: if it returns
            // `None` and we fall back to a brute-force scan, the page tree was
            // rebuilt (recovery is still always attempted).
            let normal = xref_reference
                .get_with(xref.trailer_data().pages_ref, &ctx)
                .and_then(|p| Pages::new(&p, &ctx, xref_reference));
            let page_tree_rebuilt = normal.is_none();
            let pages = normal.or_else(|| Pages::new_brute_force(&ctx, xref_reference))?;

            Some(Self {
                pages,
                _xref: xref,
                page_tree_rebuilt,
            })
        }

        pub(crate) fn get(&self) -> &Pages<'_> {
            &self.pages
        }

        /// Whether the page tree was recovered via brute-force scan.
        pub(crate) fn page_tree_rebuilt(&self) -> bool {
            self.page_tree_rebuilt
        }
    }
}

#[cfg(test)]
mod cycle_tests {
    use crate::pdf::Pdf;
    use alloc::format;
    use alloc::vec::Vec;

    /// Build a minimal PDF whose page tree contains a self-cycle: the single
    /// `/Pages` node lists a real `/Page` followed by a back-reference to
    /// itself. Without cycle detection the walker re-enters the node up to the
    /// depth cap, duplicating the page hundreds of times.
    fn cyclic_pages_pdf() -> Vec<u8> {
        let mut buf: Vec<u8> = Vec::new();
        let mut offsets = [0usize; 4];
        buf.extend_from_slice(b"%PDF-1.7\n");
        offsets[1] = buf.len();
        buf.extend_from_slice(b"1 0 obj\n<< /Type /Catalog /Pages 2 0 R >>\nendobj\n");
        offsets[2] = buf.len();
        buf.extend_from_slice(
            b"2 0 obj\n<< /Type /Pages /Kids [3 0 R 2 0 R] /Count 1 >>\nendobj\n",
        );
        offsets[3] = buf.len();
        buf.extend_from_slice(
            b"3 0 obj\n<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792] >>\nendobj\n",
        );
        let xref_off = buf.len();
        buf.extend_from_slice(b"xref\n0 4\n0000000000 65535 f \n");
        for off in &offsets[1..4] {
            buf.extend_from_slice(format!("{off:010} 00000 n \n").as_bytes());
        }
        buf.extend_from_slice(
            format!("trailer\n<< /Size 4 /Root 1 0 R >>\nstartxref\n{xref_off}\n%%EOF").as_bytes(),
        );
        buf
    }

    #[test]
    fn cyclic_page_tree_yields_one_page_without_runaway() {
        let pdf = Pdf::new(cyclic_pages_pdf()).expect("cyclic PDF should still load");
        // Exactly the one real page; the /Kids self-reference is detected and
        // skipped. Without cycle detection this would be hundreds of duplicates.
        assert_eq!(
            pdf.pages().len(),
            1,
            "page-tree cycle must not duplicate pages"
        );
    }
}
