/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */

use crate::cell::ArcRefCell;
use crate::context::LayoutContext;
use crate::display_list::stacking_context::{
    ContainingBlock, ContainingBlockInfo, StackingContext, StackingContextBuildMode,
};
use crate::dom_traversal::{iter_child_nodes, Contents, NodeAndStyleInfo, NodeExt};
use crate::element_data::LayoutBox;
use crate::flexbox::FlexLevelBox;
use crate::flow::construct::ContainsFloats;
use crate::flow::float::FloatBox;
use crate::flow::inline::InlineLevelBox;
use crate::flow::{BlockContainer, BlockFormattingContext, BlockLevelBox};
use crate::formatting_contexts::IndependentFormattingContext;
use crate::fragment_tree::Tag;
use crate::fragments::Fragment;
use crate::geom::flow_relative::Vec2;
use crate::geom::{PhysicalPoint, PhysicalRect, PhysicalSize};
use crate::positioned::AbsolutelyPositionedBox;
use crate::positioned::PositioningContext;
use crate::replaced::ReplacedContent;
use crate::style_ext::ComputedValuesExt;
use crate::style_ext::{Display, DisplayGeneratingBox, DisplayInside};
use crate::wrapper::GetStyleAndLayoutData;
use crate::DefiniteContainingBlock;
use app_units::Au;
use atomic_refcell::AtomicRef;
use euclid::default::{Point2D, Rect, Size2D};
use fxhash::FxHashSet;
use gfx_traits::print_tree::PrintTree;
use script_layout_interface::wrapper_traits::LayoutNode;
use script_layout_interface::{LayoutElementType, LayoutNodeType};
use servo_arc::Arc;
use style::animation::AnimationSetKey;
use style::dom::OpaqueNode;
use style::properties::ComputedValues;
use style::values::computed::Length;
use style_traits::CSSPixel;
use webrender_api::{ClipId, SpaceAndClipInfo, SpatialId};

#[derive(Serialize)]
pub struct BoxTree {
    /// Contains typically exactly one block-level box, which was generated by the root element.
    /// There may be zero if that element has `display: none`.
    root: BlockFormattingContext,

    /// https://drafts.csswg.org/css-backgrounds/#special-backgrounds
    canvas_background: CanvasBackground,
}

#[derive(Serialize)]
pub struct FragmentTree {
    /// Fragments at the top-level of the tree.
    ///
    /// If the root element has `display: none`, there are zero fragments.
    /// Otherwise, there is at least one:
    ///
    /// * The first fragment is generated by the root element.
    /// * There may be additional fragments generated by positioned boxes
    ///   that have the initial containing block.
    root_fragments: Vec<ArcRefCell<Fragment>>,

    /// The scrollable overflow rectangle for the entire tree
    /// https://drafts.csswg.org/css-overflow/#scrollable
    pub(crate) scrollable_overflow: PhysicalRect<Length>,

    /// The containing block used in the layout of this fragment tree.
    pub(crate) initial_containing_block: PhysicalRect<Length>,

    /// https://drafts.csswg.org/css-backgrounds/#special-backgrounds
    #[serde(skip)]
    pub(crate) canvas_background: CanvasBackground,
}

impl BoxTree {
    pub fn construct<'dom, Node>(context: &LayoutContext, root_element: Node) -> Self
    where
        Node: 'dom + Copy + LayoutNode<'dom> + Send + Sync,
    {
        let (contains_floats, boxes) = construct_for_root_element(&context, root_element);

        // Zero box for `:root { display: none }`, one for the root element otherwise.
        assert!(boxes.len() <= 1);

        Self {
            root: BlockFormattingContext {
                contains_floats: contains_floats == ContainsFloats::Yes,
                contents: BlockContainer::BlockLevelBoxes(boxes),
            },
            canvas_background: CanvasBackground::for_root_element(context, root_element),
        }
    }

    /// This method attempts to incrementally update the box tree from an
    /// arbitrary node that is not necessarily the document's root element.
    ///
    /// If the node is not a valid candidate for incremental update, the method
    /// loops over its parent. The only valid candidates for now are absolutely
    /// positioned boxes which don't change their outside display mode (i.e. it
    /// will not attempt to update from an absolutely positioned inline element
    /// which became an absolutely positioned block element). The value `true`
    /// is returned if an incremental update could be done, and `false`
    /// otherwise.
    ///
    /// There are various pain points that need to be taken care of to extend
    /// the set of valid candidates:
    /// * it is not obvious how to incrementally check whether a block
    ///   formatting context still contains floats or not;
    /// * the propagation of text decorations towards node descendants is
    ///   hard to do incrementally with our current representation of boxes
    /// * how intrinsic content sizes are computed eagerly makes it hard
    ///   to update those sizes for ancestors of the node from which we
    ///   made an incremental update.
    pub fn update<'dom, Node>(context: &LayoutContext, mut dirty_node: Node) -> bool
    where
        Node: 'dom + Copy + LayoutNode<'dom> + Send + Sync,
    {
        enum UpdatePoint {
            AbsolutelyPositionedBlockLevelBox(ArcRefCell<BlockLevelBox>),
            AbsolutelyPositionedInlineLevelBox(ArcRefCell<InlineLevelBox>),
            AbsolutelyPositionedFlexLevelBox(ArcRefCell<FlexLevelBox>),
        }

        fn update_point<'dom, Node>(
            node: Node,
        ) -> Option<(Arc<ComputedValues>, DisplayInside, UpdatePoint)>
        where
            Node: NodeExt<'dom>,
        {
            if !node.is_element() {
                return None;
            }

            if node.type_id() == LayoutNodeType::Element(LayoutElementType::HTMLBodyElement) {
                // This can require changes to the canvas background.
                return None;
            }

            // Don't update unstyled nodes.
            let data = node.get_style_and_layout_data()?;

            // Don't update nodes that have pseudo-elements.
            let element_data = data.style_data.element_data.borrow();
            if !element_data.styles.pseudos.is_empty() {
                return None;
            }

            let layout_data = data.layout_data.borrow();
            if layout_data.pseudo_before_box.borrow().is_some() {
                return None;
            }
            if layout_data.pseudo_after_box.borrow().is_some() {
                return None;
            }

            let primary_style = element_data.styles.primary();
            let box_style = primary_style.get_box();

            if !box_style.position.is_absolutely_positioned() {
                return None;
            }

            let display_inside = match Display::from(box_style.display) {
                Display::GeneratingBox(DisplayGeneratingBox::OutsideInside { inside, .. }) => {
                    inside
                },
                _ => return None,
            };

            let update_point =
                match &*AtomicRef::filter_map(layout_data.self_box.borrow(), Option::as_ref)? {
                    LayoutBox::DisplayContents => return None,
                    LayoutBox::BlockLevel(block_level_box) => match &*block_level_box.borrow() {
                        BlockLevelBox::OutOfFlowAbsolutelyPositionedBox(_)
                            if box_style.position.is_absolutely_positioned() =>
                        {
                            UpdatePoint::AbsolutelyPositionedBlockLevelBox(block_level_box.clone())
                        },
                        _ => return None,
                    },
                    LayoutBox::InlineLevel(inline_level_box) => match &*inline_level_box.borrow() {
                        InlineLevelBox::OutOfFlowAbsolutelyPositionedBox(_)
                            if box_style.position.is_absolutely_positioned() =>
                        {
                            UpdatePoint::AbsolutelyPositionedInlineLevelBox(
                                inline_level_box.clone(),
                            )
                        },
                        _ => return None,
                    },
                    LayoutBox::FlexLevel(flex_level_box) => match &*flex_level_box.borrow() {
                        FlexLevelBox::OutOfFlowAbsolutelyPositionedBox(_)
                            if box_style.position.is_absolutely_positioned() =>
                        {
                            UpdatePoint::AbsolutelyPositionedFlexLevelBox(flex_level_box.clone())
                        },
                        _ => return None,
                    },
                };
            Some((primary_style.clone(), display_inside, update_point))
        }

        loop {
            if let Some((primary_style, display_inside, update_point)) = update_point(dirty_node) {
                let contents = ReplacedContent::for_element(dirty_node)
                    .map_or(Contents::OfElement, Contents::Replaced);
                let info = NodeAndStyleInfo::new(dirty_node, Arc::clone(&primary_style));
                let out_of_flow_absolutely_positioned_box = ArcRefCell::new(
                    AbsolutelyPositionedBox::construct(context, &info, display_inside, contents),
                );
                match update_point {
                    UpdatePoint::AbsolutelyPositionedBlockLevelBox(block_level_box) => {
                        *block_level_box.borrow_mut() =
                            BlockLevelBox::OutOfFlowAbsolutelyPositionedBox(
                                out_of_flow_absolutely_positioned_box,
                            );
                    },
                    UpdatePoint::AbsolutelyPositionedInlineLevelBox(inline_level_box) => {
                        *inline_level_box.borrow_mut() =
                            InlineLevelBox::OutOfFlowAbsolutelyPositionedBox(
                                out_of_flow_absolutely_positioned_box,
                            );
                    },
                    UpdatePoint::AbsolutelyPositionedFlexLevelBox(flex_level_box) => {
                        *flex_level_box.borrow_mut() =
                            FlexLevelBox::OutOfFlowAbsolutelyPositionedBox(
                                out_of_flow_absolutely_positioned_box,
                            );
                    },
                }
                return true;
            }
            dirty_node = match dirty_node.parent_node() {
                Some(parent) => parent,
                None => return false,
            };
        }
    }
}

fn construct_for_root_element<'dom>(
    context: &LayoutContext,
    root_element: impl NodeExt<'dom>,
) -> (ContainsFloats, Vec<ArcRefCell<BlockLevelBox>>) {
    let info = NodeAndStyleInfo::new(root_element, root_element.style(context));
    let box_style = info.style.get_box();

    let display_inside = match Display::from(box_style.display) {
        Display::None => {
            root_element.unset_all_boxes();
            return (ContainsFloats::No, Vec::new());
        },
        Display::Contents => {
            // Unreachable because the style crate adjusts the computed values:
            // https://drafts.csswg.org/css-display-3/#transformations
            // “'display' of 'contents' computes to 'block' on the root element”
            unreachable!()
        },
        // The root element is blockified, ignore DisplayOutside
        Display::GeneratingBox(DisplayGeneratingBox::OutsideInside { inside, .. }) => inside,
    };

    let contents =
        ReplacedContent::for_element(root_element).map_or(Contents::OfElement, Contents::Replaced);
    let (contains_floats, root_box) = if box_style.position.is_absolutely_positioned() {
        (
            ContainsFloats::No,
            BlockLevelBox::OutOfFlowAbsolutelyPositionedBox(ArcRefCell::new(
                AbsolutelyPositionedBox::construct(context, &info, display_inside, contents),
            )),
        )
    } else if box_style.float.is_floating() {
        (
            ContainsFloats::Yes,
            BlockLevelBox::OutOfFlowFloatBox(FloatBox::construct(
                context,
                &info,
                display_inside,
                contents,
            )),
        )
    } else {
        let propagated_text_decoration_line = info.style.clone_text_decoration_line();
        (
            ContainsFloats::No,
            BlockLevelBox::Independent(IndependentFormattingContext::construct(
                context,
                &info,
                display_inside,
                contents,
                propagated_text_decoration_line,
            )),
        )
    };
    let root_box = ArcRefCell::new(root_box);
    root_element
        .element_box_slot()
        .set(LayoutBox::BlockLevel(root_box.clone()));
    (contains_floats, vec![root_box])
}

impl BoxTree {
    pub fn layout(
        &self,
        layout_context: &LayoutContext,
        viewport: euclid::Size2D<f32, CSSPixel>,
    ) -> FragmentTree {
        let style = ComputedValues::initial_values();

        // FIXME: use the document’s mode:
        // https://drafts.csswg.org/css-writing-modes/#principal-flow
        let physical_containing_block = PhysicalRect::new(
            PhysicalPoint::zero(),
            PhysicalSize::new(Length::new(viewport.width), Length::new(viewport.height)),
        );
        let initial_containing_block = DefiniteContainingBlock {
            size: Vec2 {
                inline: physical_containing_block.size.width,
                block: physical_containing_block.size.height,
            },
            style,
        };

        let dummy_tree_rank = 0;
        let mut positioning_context =
            PositioningContext::new_for_containing_block_for_all_descendants();
        let independent_layout = self.root.layout(
            layout_context,
            &mut positioning_context,
            &(&initial_containing_block).into(),
            dummy_tree_rank,
        );

        let mut root_fragments = independent_layout
            .fragments
            .into_iter()
            .map(|fragment| ArcRefCell::new(fragment))
            .collect::<Vec<_>>();

        // Zero box for `:root { display: none }`, one for the root element otherwise.
        assert!(root_fragments.len() <= 1);

        // There may be more fragments at the top-level
        // (for positioned boxes whose containing is the initial containing block)
        // but only if there was one fragment for the root element.
        positioning_context.layout_initial_containing_block_children(
            layout_context,
            &initial_containing_block,
            &mut root_fragments,
        );

        let scrollable_overflow = root_fragments
            .iter()
            .fold(PhysicalRect::zero(), |acc, child| {
                let child_overflow = child
                    .borrow()
                    .scrollable_overflow(&physical_containing_block);

                // https://drafts.csswg.org/css-overflow/#scrolling-direction
                // We want to clip scrollable overflow on box-start and inline-start
                // sides of the scroll container.
                //
                // FIXME(mrobinson, bug 25564): This should take into account writing
                // mode.
                let child_overflow = PhysicalRect::new(
                    euclid::Point2D::zero(),
                    euclid::Size2D::new(
                        child_overflow.size.width + child_overflow.origin.x,
                        child_overflow.size.height + child_overflow.origin.y,
                    ),
                );
                acc.union(&child_overflow)
            });

        FragmentTree {
            root_fragments,
            scrollable_overflow,
            initial_containing_block: physical_containing_block,
            canvas_background: self.canvas_background.clone(),
        }
    }
}

impl FragmentTree {
    pub fn build_display_list(&self, builder: &mut crate::display_list::DisplayListBuilder) {
        let stacking_context = self.build_stacking_context_tree(builder);

        // Paint the canvas’ background (if any) before/under everything else
        stacking_context.build_canvas_background_display_list(
            builder,
            self,
            &self.initial_containing_block,
        );

        stacking_context.build_display_list(builder);
    }

    fn build_stacking_context_tree(
        &self,
        builder: &mut crate::display_list::DisplayListBuilder,
    ) -> StackingContext {
        let mut stacking_context = StackingContext::create_root(&builder.wr);
        let pipeline_id = builder.wr.pipeline_id;
        let cb_for_non_fixed_descendants = ContainingBlock::new(
            &self.initial_containing_block,
            SpaceAndClipInfo::root_scroll(pipeline_id),
        );
        let cb_for_fixed_descendants = ContainingBlock::new(
            &self.initial_containing_block,
            SpaceAndClipInfo {
                spatial_id: SpatialId::root_reference_frame(pipeline_id),
                clip_id: ClipId::root(pipeline_id),
            },
        );

        for fragment in &self.root_fragments {
            fragment.borrow().build_stacking_context_tree(
                fragment,
                &mut builder.wr,
                // We need to specify all three containing blocks here, because absolute
                // descdendants of the root cannot share the containing block we specify
                // for fixed descendants. In this case, they need to have the spatial
                // id of the root scroll frame, whereas fixed descendants need the
                // spatial id of the root reference frame so that they do not scroll with
                // page content.
                &ContainingBlockInfo {
                    for_non_absolute_descendants: &cb_for_non_fixed_descendants,
                    for_absolute_descendants: Some(&cb_for_non_fixed_descendants),
                    for_absolute_and_fixed_descendants: &cb_for_fixed_descendants,
                },
                &mut stacking_context,
                StackingContextBuildMode::SkipHoisted,
            );
        }
        stacking_context.sort();
        stacking_context
    }

    pub fn print(&self) {
        let mut print_tree = PrintTree::new("Fragment Tree".to_string());
        for fragment in &self.root_fragments {
            fragment.borrow().print(&mut print_tree);
        }
    }

    pub fn scrollable_overflow(&self) -> webrender_api::units::LayoutSize {
        webrender_api::units::LayoutSize::from_untyped(Size2D::new(
            self.scrollable_overflow.size.width.px(),
            self.scrollable_overflow.size.height.px(),
        ))
    }

    pub(crate) fn find<T>(
        &self,
        mut process_func: impl FnMut(&Fragment, usize, &PhysicalRect<Length>) -> Option<T>,
    ) -> Option<T> {
        self.root_fragments.iter().find_map(|child| {
            child
                .borrow()
                .find(&self.initial_containing_block, 0, &mut process_func)
        })
    }

    pub fn remove_nodes_in_fragment_tree_from_set(&self, set: &mut FxHashSet<AnimationSetKey>) {
        self.find(|fragment, _, _| {
            let tag = fragment.tag()?;
            set.remove(&AnimationSetKey::new(tag.node, tag.pseudo));
            None::<()>
        });
    }

    pub fn get_content_box_for_node(&self, requested_node: OpaqueNode) -> Rect<Au> {
        let mut bounding_box = PhysicalRect::zero();
        let tag_to_find = Tag::new(requested_node);
        self.find(|fragment, _, containing_block| {
            if fragment.tag() != Some(tag_to_find) {
                return None::<()>;
            }

            let fragment_relative_rect = match fragment {
                Fragment::Box(fragment) => fragment
                    .border_rect()
                    .to_physical(fragment.style.writing_mode, &containing_block),
                Fragment::Text(fragment) => fragment
                    .rect
                    .to_physical(fragment.parent_style.writing_mode, &containing_block),
                Fragment::AbsoluteOrFixedPositioned(_) |
                Fragment::Image(_) |
                Fragment::IFrame(_) |
                Fragment::Anonymous(_) => return None,
            };

            bounding_box = fragment_relative_rect
                .translate(containing_block.origin.to_vector())
                .union(&bounding_box);
            None::<()>
        });

        Rect::new(
            Point2D::new(
                Au::from_f32_px(bounding_box.origin.x.px()),
                Au::from_f32_px(bounding_box.origin.y.px()),
            ),
            Size2D::new(
                Au::from_f32_px(bounding_box.size.width.px()),
                Au::from_f32_px(bounding_box.size.height.px()),
            ),
        )
    }

    pub fn get_border_dimensions_for_node(&self, requested_node: OpaqueNode) -> Rect<i32> {
        let tag_to_find = Tag::new(requested_node);
        self.find(|fragment, _, containing_block| {
            if fragment.tag() != Some(tag_to_find) {
                return None;
            }

            let (style, padding_rect) = match fragment {
                Fragment::Box(fragment) => (&fragment.style, fragment.padding_rect()),
                _ => return None,
            };

            // https://drafts.csswg.org/cssom-view/#dom-element-clienttop
            // " If the element has no associated CSS layout box or if the
            //   CSS layout box is inline, return zero." For this check we
            // also explicitly ignore the list item portion of the display
            // style.
            let display = &style.get_box().display;
            if display.inside() == style::values::specified::box_::DisplayInside::Flow &&
                display.outside() == style::values::specified::box_::DisplayOutside::Inline
            {
                return Some(Rect::zero());
            }

            let padding_rect = padding_rect.to_physical(style.writing_mode, &containing_block);
            let border = style.get_border();
            Some(Rect::new(
                Point2D::new(
                    border.border_left_width.px() as i32,
                    border.border_top_width.px() as i32,
                ),
                Size2D::new(
                    padding_rect.size.width.px() as i32,
                    padding_rect.size.height.px() as i32,
                ),
            ))
        })
        .unwrap_or_else(Rect::zero)
    }

    pub fn get_scroll_area_for_node(&self, requested_node: OpaqueNode) -> Rect<i32> {
        let mut scroll_area: PhysicalRect<Length> = PhysicalRect::zero();
        let tag_to_find = Tag::new(requested_node);
        self.find(|fragment, _, containing_block| {
            if fragment.tag() != Some(tag_to_find) {
                return None::<()>;
            }

            scroll_area = match fragment {
                Fragment::Box(fragment) => fragment
                    .scrollable_overflow(&containing_block)
                    .translate(containing_block.origin.to_vector()),
                Fragment::Text(_) |
                Fragment::AbsoluteOrFixedPositioned(_) |
                Fragment::Image(_) |
                Fragment::IFrame(_) |
                Fragment::Anonymous(_) => return None,
            };
            None::<()>
        });

        Rect::new(
            Point2D::new(
                scroll_area.origin.x.px() as i32,
                scroll_area.origin.y.px() as i32,
            ),
            Size2D::new(
                scroll_area.size.width.px() as i32,
                scroll_area.size.height.px() as i32,
            ),
        )
    }
}

/// https://drafts.csswg.org/css-backgrounds/#root-background
#[derive(Clone, Serialize)]
pub(crate) struct CanvasBackground {
    /// DOM node for the root element
    pub root_element: OpaqueNode,

    /// The element whose style the canvas takes background properties from (see next field).
    /// This can be the root element (same as the previous field), or the HTML `<body>` element.
    /// See https://drafts.csswg.org/css-backgrounds/#body-background
    pub from_element: OpaqueNode,

    /// The computed styles to take background properties from.
    #[serde(skip)]
    pub style: Option<Arc<ComputedValues>>,
}

impl CanvasBackground {
    fn for_root_element<'dom>(context: &LayoutContext, root_element: impl NodeExt<'dom>) -> Self {
        let root_style = root_element.style(context);

        let mut style = root_style;
        let mut from_element = root_element;

        // https://drafts.csswg.org/css-backgrounds/#body-background
        // “if the computed value of background-image on the root element is none
        //  and its background-color is transparent”
        if style.background_is_transparent() &&
            // “For documents whose root element is an HTML `HTML` element
            //  or an XHTML `html` element”
            root_element.type_id() == LayoutNodeType::Element(LayoutElementType::HTMLHtmlElement) &&
            // Don’t try to access styles for an unstyled subtree
            !matches!(style.clone_display().into(), Display::None)
        {
            // “that element’s first HTML `BODY` or XHTML `body` child element”
            if let Some(body) = iter_child_nodes(root_element).find(|child| {
                child.is_element() &&
                    child.type_id() ==
                        LayoutNodeType::Element(LayoutElementType::HTMLBodyElement)
            }) {
                style = body.style(context);
                from_element = body;
            }
        }

        Self {
            root_element: root_element.opaque(),
            from_element: from_element.opaque(),

            // “However, if no boxes are generated for the element
            //  whose background would be used for the canvas
            //  (for example, if the root element has display: none),
            //  then the canvas background is transparent.”
            style: if let Display::GeneratingBox(_) = style.clone_display().into() {
                Some(style)
            } else {
                None
            },
        }
    }
}