gfx/wr/webrender/src/picture.rs
author Glenn Watson <github@intuitionlibrary.com>
Thu, 07 Feb 2019 15:42:06 +0000
changeset 457629 f526887aa3ae0087bbb9553627453eb9ecdec871
parent 457452 141cec39cdb87a2c5dae48f4921d87c6fd401cff
child 458529 8db55f13f405d58f343756ff8548736e4af627f9
child 458559 a856e1763485f529c7418494783bb8e68d0b23d9
permissions -rw-r--r--
Bug 1525740 - Visual artifacts in add-on menu with webrender enabled on mac intel. r=jrmuizel The existing picture caching code in WR assumes that the tiles are being drawn into the main framebuffer. This is true to the main content frame, however it's not the case for all popup windows. In the case of popup windows on mac, they have a rounded rect clip, which results in a surface being used. This breaks some assumptions in the picture caching code. The long term fix involves supporting picture caching on surfaces. However, we don't want picture caching on for non-content windows anyway (due to wasting texture memory), so for now we will simply disable picture cache composite modes if they are being drawn on a non-root surface. Differential Revision: https://phabricator.services.mozilla.com/D18917

/* 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 http://mozilla.org/MPL/2.0/. */

use api::{FilterOp, MixBlendMode, PipelineId, PremultipliedColorF, PictureRect, PicturePoint, WorldPoint};
use api::{DeviceIntRect, DeviceIntSize, DevicePoint, DeviceRect};
use api::{LayoutRect, PictureToRasterTransform, LayoutPixel, PropertyBinding, PropertyBindingId};
use api::{DevicePixelScale, RasterRect, RasterSpace, ColorF, ImageKey, DirtyRect, WorldSize, ClipMode, LayoutSize};
use api::{PicturePixel, RasterPixel, WorldPixel, WorldRect, ImageFormat, ImageDescriptor, WorldVector2D, LayoutPoint};
use api::{DebugFlags, DeviceHomogeneousVector, DeviceVector2D};
use box_shadow::{BLUR_SAMPLE_SCALE};
use clip::{ClipChainId, ClipChainNode, ClipItem, ClipStore, ClipDataStore, ClipChainStack};
use clip_scroll_tree::{ROOT_SPATIAL_NODE_INDEX, ClipScrollTree, SpatialNodeIndex, CoordinateSystemId};
use debug_colors;
use device::TextureFilter;
use euclid::{size2, vec3, TypedPoint2D, TypedScale, TypedSize2D};
use euclid::approxeq::ApproxEq;
use frame_builder::{FrameVisibilityContext, FrameVisibilityState};
use intern::ItemUid;
use internal_types::{FastHashMap, FastHashSet, PlaneSplitter};
use frame_builder::{FrameBuildingContext, FrameBuildingState, PictureState, PictureContext};
use gpu_cache::{GpuCache, GpuCacheAddress, GpuCacheHandle};
use gpu_types::{TransformPalette, TransformPaletteId, UvRectKind};
use plane_split::{Clipper, Polygon, Splitter};
use prim_store::{PictureIndex, PrimitiveInstance, SpaceMapper, VisibleFace, PrimitiveInstanceKind};
use prim_store::{get_raster_rects, PrimitiveScratchBuffer, VectorKey, PointKey};
use prim_store::{OpacityBindingStorage, ImageInstanceStorage, OpacityBindingIndex, RectangleKey};
use print_tree::PrintTreePrinter;
use render_backend::DataStores;
use render_task::{ClearMode, RenderTask, RenderTaskCacheEntryHandle, TileBlit};
use render_task::{RenderTaskId, RenderTaskLocation};
use resource_cache::ResourceCache;
use scene::{FilterOpHelpers, SceneProperties};
use scene_builder::Interners;
use smallvec::SmallVec;
use std::{mem, u16};
use std::sync::atomic::{AtomicUsize, Ordering};
use texture_cache::{Eviction, TextureCacheHandle};
use tiling::RenderTargetKind;
use util::{ComparableVec, TransformedRectKind, MatrixHelpers, MaxRect};

/*
 A picture represents a dynamically rendered image. It consists of:

 * A number of primitives that are drawn onto the picture.
 * A composite operation describing how to composite this
   picture into its parent.
 * A configuration describing how to draw the primitives on
   this picture (e.g. in screen space or local space).
 */

/// Information about a picture that is pushed / popped on the
/// PictureUpdateState during picture traversal pass.
struct PictureInfo {
    /// The spatial node for this picture.
    spatial_node_index: SpatialNodeIndex,
}

/// Stores a list of cached picture tiles that are retained
/// between new scenes.
pub struct RetainedTiles {
    /// The tiles retained between display lists.
    pub tiles: Vec<Tile>,
    /// List of reference primitives that we will compare
    /// to try and correlate the positioning of items
    /// between display lists.
    pub ref_prims: FastHashMap<ItemUid, WorldPoint>,
}

impl RetainedTiles {
    pub fn new() -> Self {
        RetainedTiles {
            tiles: Vec::new(),
            ref_prims: FastHashMap::default(),
        }
    }

    /// Merge items from one retained tiles into another.
    pub fn merge(&mut self, other: RetainedTiles) {
        assert!(self.tiles.is_empty() || other.tiles.is_empty());
        self.tiles.extend(other.tiles);
        self.ref_prims.extend(other.ref_prims);
    }
}

/// Unit for tile coordinates.
#[derive(Hash, Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)]
pub struct TileCoordinate;

// Geometry types for tile coordinates.
pub type TileOffset = TypedPoint2D<i32, TileCoordinate>;
pub type TileSize = TypedSize2D<i32, TileCoordinate>;
pub struct TileIndex(pub usize);

/// The size in device pixels of a cached tile. The currently chosen
/// size is arbitrary. We should do some profiling to find the best
/// size for real world pages.
///
/// Note that we use a separate, smaller size during wrench testing, so that
/// we get tighter dirty rects and can do more meaningful invalidation
/// tests.
pub const TILE_SIZE_WIDTH: i32 = 1024;
pub const TILE_SIZE_HEIGHT: i32 = 256;
pub const TILE_SIZE_TESTING: i32 = 64;
pub const FRAMES_BEFORE_PICTURE_CACHING: usize = 2;
const MAX_DIRTY_RECTS: usize = 3;

/// The maximum size per axis of a surface,
///  in WorldPixel coordinates.
const MAX_SURFACE_SIZE: f32 = 4096.0;


/// The maximum number of primitives to look for in a display
/// list, trying to find unique primitives.
const MAX_PRIMS_TO_SEARCH: usize = 128;

/// Used to get unique tile IDs, even when the tile cache is
/// destroyed between display lists / scenes.
static NEXT_TILE_ID: AtomicUsize = AtomicUsize::new(0);

fn clamp(value: i32, low: i32, high: i32) -> i32 {
    value.max(low).min(high)
}

/// Information about the state of an opacity binding.
#[derive(Debug)]
pub struct OpacityBindingInfo {
    /// The current value retrieved from dynamic scene properties.
    value: f32,
    /// True if it was changed (or is new) since the last frame build.
    changed: bool,
}

/// Information stored in a tile descriptor for an opacity binding.
#[derive(Debug, PartialEq, Clone)]
pub enum OpacityBinding {
    Value(f32),
    Binding(PropertyBindingId),
}

impl From<PropertyBinding<f32>> for OpacityBinding {
    fn from(binding: PropertyBinding<f32>) -> OpacityBinding {
        match binding {
            PropertyBinding::Binding(key, _) => OpacityBinding::Binding(key.id),
            PropertyBinding::Value(value) => OpacityBinding::Value(value),
        }
    }
}

/// A stable ID for a given tile, to help debugging.
#[derive(Debug, Copy, Clone, PartialEq)]
struct TileId(usize);

/// Information about a cached tile.
#[derive(Debug)]
pub struct Tile {
    /// The current world rect of thie tile.
    world_rect: WorldRect,
    /// The current local rect of this tile.
    pub local_rect: LayoutRect,
    /// The currently visible rect within this tile, updated per frame.
    /// If None, this tile is not currently visible.
    visible_rect: Option<WorldRect>,
    /// The currently valid rect of the tile, used to invalidate
    /// tiles that were only partially drawn.
    valid_rect: WorldRect,
    /// Uniquely describes the content of this tile, in a way that can be
    /// (reasonably) efficiently hashed and compared.
    descriptor: TileDescriptor,
    /// Handle to the cached texture for this tile.
    pub handle: TextureCacheHandle,
    /// If true, this tile is marked valid, and the existing texture
    /// cache handle can be used. Tiles are invalidated during the
    /// build_dirty_regions method.
    is_valid: bool,
    /// If true, the content on this tile is the same as last frame.
    is_same_content: bool,
    /// The number of frames this tile has had the same content.
    same_frames: usize,
    /// The tile id is stable between display lists and / or frames,
    /// if the tile is retained. Useful for debugging tile evictions.
    id: TileId,
    /// The set of transforms that affect primitives on this tile we
    /// care about. Stored as a set here, and then collected, sorted
    /// and converted to transform key values during post_update.
    transforms: FastHashSet<SpatialNodeIndex>,
    /// A list of potentially important clips. We can't know if
    /// they were important or can be discarded until we know the
    /// tile cache bounding rect.
    potential_clips: FastHashMap<RectangleKey, SpatialNodeIndex>,
    /// If true, this tile should still be considered as part of
    /// the dirty rect calculations.
    consider_for_dirty_rect: bool,
}

impl Tile {
    /// Construct a new, invalid tile.
    fn new(
        id: TileId,
    ) -> Self {
        Tile {
            local_rect: LayoutRect::zero(),
            world_rect: WorldRect::zero(),
            visible_rect: None,
            valid_rect: WorldRect::zero(),
            handle: TextureCacheHandle::invalid(),
            descriptor: TileDescriptor::new(),
            is_same_content: false,
            is_valid: false,
            same_frames: 0,
            transforms: FastHashSet::default(),
            potential_clips: FastHashMap::default(),
            id,
            consider_for_dirty_rect: false,
        }
    }

    /// Clear the dependencies for a tile.
    fn clear(&mut self) {
        self.transforms.clear();
        self.descriptor.clear();
        self.potential_clips.clear();
    }

    /// Invalidate a tile based on change in content. This
    /// muct be called even if the tile is not currently
    /// visible on screen. We might be able to improve this
    /// later by changing how ComparableVec is used.
    fn update_content_validity(&mut self) {
        // Check if the contents of the primitives, clips, and
        // other dependencies are the same.
        self.is_same_content &= self.descriptor.is_same_content();
        self.is_valid &= self.is_same_content;
    }

    /// Update state related to whether a tile has a valid rect that
    /// covers the required visible part of the tile.
    fn update_rect_validity(&mut self, tile_bounding_rect: &WorldRect) {
        // The tile is only valid if:
        // - The content is the same *and*
        // - The valid part of the tile includes the needed part.
        self.is_valid &= self.valid_rect.contains_rect(tile_bounding_rect);

        // Update count of how many times this tile has had the same content.
        if !self.is_same_content {
            self.same_frames = 0;
        }
        self.same_frames += 1;
    }
}

/// Defines a key that uniquely identifies a primitive instance.
#[derive(Debug, Clone, PartialEq)]
pub struct PrimitiveDescriptor {
    /// Uniquely identifies the content of the primitive template.
    prim_uid: ItemUid,
    /// The origin in world space of this primitive.
    origin: WorldPoint,
    /// The first clip in the clip_uids array of clips that affect this tile.
    first_clip: u16,
    /// The number of clips that affect this primitive instance.
    clip_count: u16,
    /// The combined local clips + prim rect for this primitive.
    world_culling_rect: WorldRect,
}

/// Uniquely describes the content of this tile, in a way that can be
/// (reasonably) efficiently hashed and compared.
#[derive(Debug)]
pub struct TileDescriptor {
    /// List of primitive instance unique identifiers. The uid is guaranteed
    /// to uniquely describe the content of the primitive template, while
    /// the other parameters describe the clip chain and instance params.
    prims: ComparableVec<PrimitiveDescriptor>,

    /// List of clip node unique identifiers. The uid is guaranteed
    /// to uniquely describe the content of the clip node.
    clip_uids: ComparableVec<ItemUid>,

    /// List of local offsets of the clip node origins. This
    /// ensures that if a clip node is supplied but has a different
    /// transform between frames that the tile is invalidated.
    clip_vertices: ComparableVec<PointKey>,

    /// List of image keys that this tile depends on.
    image_keys: ComparableVec<ImageKey>,

    /// The set of opacity bindings that this tile depends on.
    // TODO(gw): Ugh, get rid of all opacity binding support!
    opacity_bindings: ComparableVec<OpacityBinding>,

    /// List of the effects of transforms that we care about
    /// tracking for this tile.
    transforms: ComparableVec<PointKey>,
}

impl TileDescriptor {
    fn new() -> Self {
        TileDescriptor {
            prims: ComparableVec::new(),
            clip_uids: ComparableVec::new(),
            clip_vertices: ComparableVec::new(),
            opacity_bindings: ComparableVec::new(),
            image_keys: ComparableVec::new(),
            transforms: ComparableVec::new(),
        }
    }

    /// Clear the dependency information for a tile, when the dependencies
    /// are being rebuilt.
    fn clear(&mut self) {
        self.prims.reset();
        self.clip_uids.reset();
        self.clip_vertices.reset();
        self.opacity_bindings.reset();
        self.image_keys.reset();
        self.transforms.reset();
    }

    /// Return true if the content of the tile is the same
    /// as last frame. This doesn't check validity of the
    /// tile based on the currently valid regions.
    fn is_same_content(&self) -> bool {
        if !self.image_keys.is_valid() {
            return false;
        }
        if !self.opacity_bindings.is_valid() {
            return false;
        }
        if !self.clip_uids.is_valid() {
            return false;
        }
        if !self.clip_vertices.is_valid() {
            return false;
        }
        if !self.prims.is_valid() {
            return false;
        }
        if !self.transforms.is_valid() {
            return false;
        }

        true
    }
}

/// Stores both the world and devices rects for a single dirty rect.
#[derive(Debug, Clone)]
pub struct DirtyRegionRect {
    pub world_rect: WorldRect,
}

/// Represents the dirty region of a tile cache picture.
#[derive(Debug, Clone)]
pub struct DirtyRegion {
    /// The individual dirty rects of this region.
    pub dirty_rects: Vec<DirtyRegionRect>,

    /// The overall dirty rect, a combination of dirty_rects
    pub combined: DirtyRegionRect,
}

impl DirtyRegion {
    /// Construct a new dirty region tracker.
    pub fn new() -> Self {
        DirtyRegion {
            dirty_rects: Vec::with_capacity(MAX_DIRTY_RECTS),
            combined: DirtyRegionRect {
                world_rect: WorldRect::zero(),
            },
        }
    }

    /// Reset the dirty regions back to empty
    pub fn clear(&mut self) {
        self.dirty_rects.clear();
        self.combined = DirtyRegionRect {
            world_rect: WorldRect::zero(),
        }
    }

    /// Push a dirty rect into this region
    pub fn push(
        &mut self,
        rect: WorldRect,
    ) {
        // Include this in the overall dirty rect
        self.combined.world_rect = self.combined.world_rect.union(&rect);

        // Store the individual dirty rect.
        self.dirty_rects.push(DirtyRegionRect {
            world_rect: rect,
        });
    }

    /// Returns true if this region has no dirty rects
    pub fn is_empty(&self) -> bool {
        self.dirty_rects.is_empty()
    }

    /// Collapse all dirty rects into a single dirty rect.
    pub fn collapse(&mut self) {
        self.dirty_rects.clear();
        self.dirty_rects.push(self.combined.clone());
    }

    pub fn inflate(
        &self,
        inflate_amount: f32,
    ) -> DirtyRegion {
        let mut dirty_rects = Vec::with_capacity(self.dirty_rects.len());
        let mut combined = DirtyRegionRect {
            world_rect: WorldRect::zero(),
        };

        for rect in &self.dirty_rects {
            let world_rect = rect.world_rect.inflate(inflate_amount, inflate_amount);
            combined.world_rect = combined.world_rect.union(&world_rect);
            dirty_rects.push(DirtyRegionRect {
                world_rect,
            });
        }

        DirtyRegion {
            dirty_rects,
            combined,
        }
    }

    /// Creates a record of this dirty region for exporting to test infrastructure.
    pub fn record(&self) -> RecordedDirtyRegion {
        let mut rects: Vec<WorldRect> =
            self.dirty_rects.iter().map(|r| r.world_rect.clone()).collect();
        rects.sort_unstable_by_key(|r| (r.origin.y as usize, r.origin.x as usize));
        RecordedDirtyRegion { rects }
    }
}

/// A recorded copy of the dirty region for exporting to test infrastructure.
pub struct RecordedDirtyRegion {
    pub rects: Vec<WorldRect>,
}

impl ::std::fmt::Display for RecordedDirtyRegion {
    fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
        for r in self.rects.iter() {
            let (x, y, w, h) = (r.origin.x, r.origin.y, r.size.width, r.size.height);
            write!(f, "[({},{}):{}x{}]", x, y, w, h)?;
        }
        Ok(())
    }
}

impl ::std::fmt::Debug for RecordedDirtyRegion {
    fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
        ::std::fmt::Display::fmt(self, f)
    }
}

/// A helper struct to build a (roughly) minimal set of dirty rectangles
/// from a list of individual dirty rectangles. This minimizes the number
/// of scissors rects and batch resubmissions that are needed.
struct DirtyRegionBuilder<'a> {
    tiles: &'a mut [Tile],
    tile_count: TileSize,
}

impl<'a> DirtyRegionBuilder<'a> {
    fn new(
        tiles: &'a mut [Tile],
        tile_count: TileSize,
    ) -> Self {
        DirtyRegionBuilder {
            tiles,
            tile_count,
        }
    }

    fn tile_index(&self, x: i32, y: i32) -> usize {
        (y * self.tile_count.width + x) as usize
    }

    fn is_dirty(&self, x: i32, y: i32) -> bool {
        if x == self.tile_count.width || y == self.tile_count.height {
            return false;
        }

        self.get_tile(x, y).consider_for_dirty_rect
    }

    fn get_tile(&self, x: i32, y: i32) -> &Tile {
        &self.tiles[self.tile_index(x, y)]
    }

    fn get_tile_mut(&mut self, x: i32, y: i32) -> &mut Tile {
        &mut self.tiles[self.tile_index(x, y)]
    }

    /// Return true if the entire column is dirty
    fn column_is_dirty(&self, x: i32, y0: i32, y1: i32) -> bool {
        for y in y0 .. y1 {
            if !self.is_dirty(x, y) {
                return false;
            }
        }

        true
    }

    /// Push a dirty rect into the final region list.
    fn push_dirty_rect(
        &mut self,
        x0: i32,
        y0: i32,
        x1: i32,
        y1: i32,
        dirty_region: &mut DirtyRegion,
    ) {
        // Construct the overall dirty rect by combining the visible
        // parts of the dirty rects that were combined.
        let mut dirty_world_rect = WorldRect::zero();

        for y in y0 .. y1 {
            for x in x0 .. x1 {
                let tile = self.get_tile_mut(x, y);
                tile.consider_for_dirty_rect = false;
                if let Some(visible_rect) = tile.visible_rect {
                    dirty_world_rect = dirty_world_rect.union(&visible_rect);
                }
            }
        }

        dirty_region.push(dirty_world_rect);
    }

    /// Simple sweep through the tile grid to try and coalesce individual
    /// dirty rects into a smaller number of larger dirty rectangles.
    fn build(&mut self, dirty_region: &mut DirtyRegion) {
        for x0 in 0 .. self.tile_count.width {
            for y0 in 0 .. self.tile_count.height {
                let mut y1 = y0;

                while self.is_dirty(x0, y1) {
                    y1 += 1;
                }

                if y1 > y0 {
                    let mut x1 = x0;

                    while self.column_is_dirty(x1, y0, y1) {
                        x1 += 1;
                    }

                    self.push_dirty_rect(x0, y0, x1, y1, dirty_region);
                }
            }
        }
    }
}

/// Represents a cache of tiles that make up a picture primitives.
pub struct TileCache {
    /// The positioning node for this tile cache.
    spatial_node_index: SpatialNodeIndex,
    /// List of tiles present in this picture (stored as a 2D array)
    pub tiles: Vec<Tile>,
    /// A helper struct to map local rects into world coords.
    map_local_to_world: SpaceMapper<LayoutPixel, WorldPixel>,
    /// A list of tiles to draw during batching.
    pub tiles_to_draw: Vec<TileIndex>,
    /// List of opacity bindings, with some extra information
    /// about whether they changed since last frame.
    opacity_bindings: FastHashMap<PropertyBindingId, OpacityBindingInfo>,
    /// The current dirty region tracker for this picture.
    pub dirty_region: DirtyRegion,
    /// The current world reference point that tiles are created around.
    world_origin: WorldPoint,
    /// Current size of tiles in world units.
    world_tile_size: WorldSize,
    /// Current number of tiles in the allocated grid.
    tile_count: TileSize,
    /// The current scroll offset for this frame builder. Reset when
    /// a new scene arrives.
    scroll_offset: Option<WorldVector2D>,
    /// A list of blits from the framebuffer to be applied during this frame.
    pub pending_blits: Vec<TileBlit>,
    /// The current world bounding rect of this tile cache. This is used
    /// to derive a local clip rect, such that we don't obscure in the
    /// z-buffer any items placed earlier in the render order (such as
    /// scroll bars in gecko, when the content overflows under the
    /// scroll bar).
    world_bounding_rect: WorldRect,
    /// World space clip rect of the root clipping node. Every primitive
    /// has this as the root of the clip chain attached to the primitive.
    root_clip_rect: WorldRect,
    /// List of reference primitive information used for
    /// correlating the position between display lists.
    reference_prims: ReferencePrimitiveList,
    /// The root clip chain for this tile cache.
    root_clip_chain_id: ClipChainId,
    /// If true, this tile cache is enabled. For now, it doesn't
    /// support tile caching if the surface is not the main framebuffer.
    pub is_enabled: bool,
}

/// Stores information about a primitive in the cache that we will
/// try to use to correlate positions between display lists.
#[derive(Clone)]
struct ReferencePrimitive {
    uid: ItemUid,
    local_pos: LayoutPoint,
    spatial_node_index: SpatialNodeIndex,
    ref_count: usize,
}

/// A list of primitive with uids that only exist once in a display
/// list. Used to obtain reference points to correlate the offset
/// between two similar display lists.
struct ReferencePrimitiveList {
    ref_prims: Vec<ReferencePrimitive>,
}

impl ReferencePrimitiveList {
    fn new(
        prim_instances: &[PrimitiveInstance],
        pictures: &[PicturePrimitive],
    ) -> Self {
        let mut map = FastHashMap::default();
        let mut search_count = 0;

        // Collect a set of primitives that we can
        // potentially use for correlation.
        collect_ref_prims(
            prim_instances,
            pictures,
            &mut map,
            &mut search_count,
        );

        // Select only primitives where the uid is unique
        // in the display list, giving the best chance
        // of finding correct correlations.
        let ref_prims = map.values().filter(|prim| {
            prim.ref_count == 1
        }).cloned().collect();

        ReferencePrimitiveList {
            ref_prims,
        }
    }
}

/// Collect a sample of primitives from the prim list that can
/// be used to correlate positions.
fn collect_ref_prims(
    prim_instances: &[PrimitiveInstance],
    pictures: &[PicturePrimitive],
    map: &mut FastHashMap<ItemUid, ReferencePrimitive>,
    search_count: &mut usize,
) {
    for prim_instance in prim_instances {
        if *search_count > MAX_PRIMS_TO_SEARCH {
            return;
        }

        match prim_instance.kind {
            PrimitiveInstanceKind::Picture { pic_index, .. } => {
                collect_ref_prims(
                    &pictures[pic_index.0].prim_list.prim_instances,
                    pictures,
                    map,
                    search_count,
                );
            }
            _ => {
                let uid = prim_instance.uid();

                let entry = map.entry(uid).or_insert_with(|| {
                    ReferencePrimitive {
                        uid,
                        local_pos: prim_instance.prim_origin,
                        spatial_node_index: prim_instance.spatial_node_index,
                        ref_count: 0,
                    }
                });
                entry.ref_count += 1;

                *search_count = *search_count + 1;
            }
        }
    }
}

impl TileCache {
    pub fn new(
        spatial_node_index: SpatialNodeIndex,
        prim_instances: &[PrimitiveInstance],
        root_clip_chain_id: ClipChainId,
        pictures: &[PicturePrimitive],
    ) -> Self {
        // Build the list of reference primitives
        // for this picture cache.
        let reference_prims = ReferencePrimitiveList::new(
            prim_instances,
            pictures,
        );

        TileCache {
            spatial_node_index,
            tiles: Vec::new(),
            map_local_to_world: SpaceMapper::new(
                ROOT_SPATIAL_NODE_INDEX,
                WorldRect::zero(),
            ),
            tiles_to_draw: Vec::new(),
            opacity_bindings: FastHashMap::default(),
            dirty_region: DirtyRegion::new(),
            world_origin: WorldPoint::zero(),
            world_tile_size: WorldSize::zero(),
            tile_count: TileSize::zero(),
            scroll_offset: None,
            pending_blits: Vec::new(),
            world_bounding_rect: WorldRect::zero(),
            root_clip_rect: WorldRect::max_rect(),
            reference_prims,
            root_clip_chain_id,
            is_enabled: true,
        }
    }

    /// Get the tile coordinates for a given rectangle.
    fn get_tile_coords_for_rect(
        &self,
        rect: &WorldRect,
    ) -> (TileOffset, TileOffset) {
        // Translate the rectangle into the virtual tile space
        let origin = rect.origin - self.world_origin;

        // Get the tile coordinates in the picture space.
        let mut p0 = TileOffset::new(
            (origin.x / self.world_tile_size.width).floor() as i32,
            (origin.y / self.world_tile_size.height).floor() as i32,
        );

        let mut p1 = TileOffset::new(
            ((origin.x + rect.size.width) / self.world_tile_size.width).ceil() as i32,
            ((origin.y + rect.size.height) / self.world_tile_size.height).ceil() as i32,
        );

        // Clamp the tile coordinates here to avoid looping over irrelevant tiles later on.
        p0.x = clamp(p0.x, 0, self.tile_count.width);
        p0.y = clamp(p0.y, 0, self.tile_count.height);
        p1.x = clamp(p1.x, 0, self.tile_count.width);
        p1.y = clamp(p1.y, 0, self.tile_count.height);

        (p0, p1)
    }

    /// Update transforms, opacity bindings and tile rects.
    pub fn pre_update(
        &mut self,
        pic_rect: LayoutRect,
        frame_context: &FrameVisibilityContext,
        frame_state: &mut FrameVisibilityState,
        surface_index: SurfaceIndex,
    ) {
        // If the tile cache is the first surface on the root
        // surface, then we can enable it. If the client has
        // requested caching on an offscreen surface, we will
        // need to disable it (for now).
        self.is_enabled = surface_index == SurfaceIndex(1);
        if !self.is_enabled {
            // TODO(gw): It's technically possible that this tile cache
            //           might have been enabled in a valid state, and
            //           then got an offscreen surface. In this case,
            //           there may be some pre-cached tiles still existing.
            //           They will expire from the texture cache as normal,
            //           but we should check this path a bit more carefully
            //           to see if any other memory should be freed.
            return;
        }

        let DeviceIntSize { width: tile_width, height: tile_height, _unit: _ } =
            self.tile_dimensions(frame_context.config.testing);

        // Work out the scroll offset to apply to the world reference point.
        let scroll_transform = frame_context.clip_scroll_tree.get_relative_transform(
            ROOT_SPATIAL_NODE_INDEX,
            self.spatial_node_index,
        ).expect("bug: unable to get scroll transform");
        let scroll_offset = WorldVector2D::new(
            scroll_transform.m41,
            scroll_transform.m42,
        );
        let scroll_delta = match self.scroll_offset {
            Some(prev) => prev - scroll_offset,
            None => WorldVector2D::zero(),
        };
        self.scroll_offset = Some(scroll_offset);

        // Pull any retained tiles from the previous scene.
        let world_offset = if frame_state.retained_tiles.tiles.is_empty() {
            None
        } else {
            assert!(self.tiles.is_empty());
            self.tiles = mem::replace(&mut frame_state.retained_tiles.tiles, Vec::new());

            // Get the positions of the reference primitives for this
            // new display list.
            let mut new_prim_map = FastHashMap::default();
            build_ref_prims(
                &self.reference_prims.ref_prims,
                &mut new_prim_map,
                frame_context.clip_scroll_tree,
            );

            // Attempt to correlate them to work out which offset to apply.
            correlate_prim_maps(
                &frame_state.retained_tiles.ref_prims,
                &new_prim_map,
            )
        }.unwrap_or(WorldVector2D::zero());

        // Assume no tiles are valid to draw by default
        self.tiles_to_draw.clear();

        self.map_local_to_world = SpaceMapper::new(
            ROOT_SPATIAL_NODE_INDEX,
            frame_context.screen_world_rect,
        );

        let world_mapper = SpaceMapper::new_with_target(
            ROOT_SPATIAL_NODE_INDEX,
            self.spatial_node_index,
            frame_context.screen_world_rect,
            frame_context.clip_scroll_tree,
        );

        // Do a hacky diff of opacity binding values from the last frame. This is
        // used later on during tile invalidation tests.
        let current_properties = frame_context.scene_properties.float_properties();
        let old_properties = mem::replace(&mut self.opacity_bindings, FastHashMap::default());

        for (id, value) in current_properties {
            let changed = match old_properties.get(id) {
                Some(old_property) => !old_property.value.approx_eq(value),
                None => true,
            };
            self.opacity_bindings.insert(*id, OpacityBindingInfo {
                value: *value,
                changed,
            });
        }

        // Map the picture rect to world space and work out the tiles that we need
        // in order to ensure the screen is covered.
        let pic_world_rect = world_mapper
            .map(&pic_rect)
            .expect("bug: unable to map picture rect to world");

        // If the bounding rect of the picture to cache doesn't intersect with
        // the visible world rect at all, just take the screen world rect as
        // a reference for the area to create tiles for. This allows existing
        // tiles to be retained in case they are still valid if / when they
        // get scrolled back onto the screen.

        let needed_world_rect = frame_context
            .screen_world_rect
            .intersection(&pic_world_rect)
            .unwrap_or(frame_context.screen_world_rect);

        // Get a reference point that serves as an origin that all tiles we create
        // must be aligned to. This ensures that tiles get reused correctly between
        // scrolls and display list changes, even with the different local coord
        // systems that gecko supplies.
        let mut world_ref_point = if self.tiles.is_empty() {
            needed_world_rect.origin.floor()
        } else {
            self.tiles[0].world_rect.origin + world_offset
        };

        // Apply the scroll delta so that existing tiles still get used.
        world_ref_point += scroll_delta;

        // Work out the required device rect that we need to cover the screen,
        // given the world reference point constraint.
        let device_ref_point = world_ref_point * frame_context.device_pixel_scale;
        let device_world_rect = frame_context.screen_world_rect * frame_context.device_pixel_scale;
        let pic_device_rect = pic_world_rect * frame_context.device_pixel_scale;
        let needed_device_rect = pic_device_rect
            .intersection(&device_world_rect)
            .unwrap_or(device_world_rect);

        // Expand the needed device rect vertically by a small number of tiles. This
        // ensures that as tiles are scrolled in/out of view, they are retained for
        // a while before being discarded.
        // TODO(gw): On some pages it might be worth also inflating horizontally.
        //           (is this locale specific?). It might be possible to make a good
        //           guess based on the size of the picture rect for the tile cache.
        let needed_device_rect = needed_device_rect.inflate(
            0.0,
            3.0 * tile_height as f32,
        );

        let p0 = needed_device_rect.origin;
        let p1 = needed_device_rect.bottom_right();

        let p0 = DevicePoint::new(
            device_ref_point.x + ((p0.x - device_ref_point.x) / tile_width as f32).floor() * tile_width as f32,
            device_ref_point.y + ((p0.y - device_ref_point.y) / tile_height as f32).floor() * tile_height as f32,
        );

        let p1 = DevicePoint::new(
            device_ref_point.x + ((p1.x - device_ref_point.x) / tile_width as f32).ceil() * tile_width as f32,
            device_ref_point.y + ((p1.y - device_ref_point.y) / tile_height as f32).ceil() * tile_height as f32,
        );

        // And now the number of tiles from that device rect.
        let x_tiles = ((p1.x - p0.x) / tile_width as f32).round() as i32;
        let y_tiles = ((p1.y - p0.y) / tile_height as f32).round() as i32;

        // Step through any old tiles, and retain them if we can. They are keyed only on
        // the (scroll adjusted) world position, relying on the descriptor content checks
        // later to invalidate them if the content has changed.
        let mut old_tiles = FastHashMap::default();
        for tile in self.tiles.drain(..) {
            let tile_device_pos = (tile.world_rect.origin + scroll_delta) * frame_context.device_pixel_scale;
            let key = (
                (tile_device_pos.x + world_offset.x).round() as i32,
                (tile_device_pos.y + world_offset.y).round() as i32,
            );
            old_tiles.insert(key, tile);
        }

        // Store parameters about the current tiling rect for use during dependency updates.
        self.world_origin = WorldPoint::new(
            p0.x / frame_context.device_pixel_scale.0,
            p0.y / frame_context.device_pixel_scale.0,
        );
        self.world_tile_size = WorldSize::new(
            tile_width as f32 / frame_context.device_pixel_scale.0,
            tile_height as f32 / frame_context.device_pixel_scale.0,
        );
        self.tile_count = TileSize::new(x_tiles, y_tiles);

        // Step through each tile and try to retain an old tile from the
        // previous frame, and update bounding rects.
        for y in 0 .. y_tiles {
            for x in 0 .. x_tiles {
                let px = p0.x + x as f32 * tile_width as f32;
                let py = p0.y + y as f32 * tile_height as f32;
                let key = (px.round() as i32, py.round() as i32);

                let mut tile = match old_tiles.remove(&key) {
                    Some(tile) => tile,
                    None => {
                        let next_id = TileId(NEXT_TILE_ID.fetch_add(1, Ordering::Relaxed));
                        Tile::new(next_id)
                    }
                };

                tile.world_rect = WorldRect::new(
                    WorldPoint::new(
                        px / frame_context.device_pixel_scale.0,
                        py / frame_context.device_pixel_scale.0,
                    ),
                    self.world_tile_size,
                );

                tile.local_rect = world_mapper
                    .unmap(&tile.world_rect)
                    .expect("bug: can't unmap world rect");

                tile.visible_rect = tile.world_rect.intersection(&frame_context.screen_world_rect);

                self.tiles.push(tile);
            }
        }

        if !old_tiles.is_empty() {
            // TODO(gw): Should we explicitly drop the tile texture cache handles here?
        }

        self.world_bounding_rect = WorldRect::zero();
        self.root_clip_rect = WorldRect::max_rect();

        // Calculate the world space of the root clip node, that every primitive has
        // at the root of its clip chain (this is enforced by the per-pipeline-root
        // clip node added implicitly during display list flattening). Doing it once
        // here saves doing it for every primitive during update_prim_dependencies.
        if self.root_clip_chain_id != ClipChainId::NONE {
            let root_clip_chain_node = &frame_state
                .clip_store
                .clip_chain_nodes[self.root_clip_chain_id.0 as usize];
            let root_clip_node = &frame_state
                .data_stores
                .clip[root_clip_chain_node.handle];
            if let Some(clip_rect) = root_clip_node.item.get_local_clip_rect(root_clip_chain_node.local_pos) {
                self.map_local_to_world.set_target_spatial_node(
                    root_clip_chain_node.spatial_node_index,
                    frame_context.clip_scroll_tree,
                );

                if let Some(world_clip_rect) = self.map_local_to_world.map(&clip_rect) {
                    self.root_clip_rect = world_clip_rect;
                }
            }
        }

        // Do tile invalidation for any dependencies that we know now.
        for tile in &mut self.tiles {
            // Start frame assuming that the tile has the same content.
            tile.is_same_content = true;

            // Content has changed if any images have changed
            for image_key in tile.descriptor.image_keys.items() {
                if frame_state.resource_cache.is_image_dirty(*image_key) {
                    tile.is_same_content = false;
                    break;
                }
            }

            // Content has changed if any opacity bindings changed.
            for binding in tile.descriptor.opacity_bindings.items() {
                if let OpacityBinding::Binding(id) = binding {
                    let changed = match self.opacity_bindings.get(id) {
                        Some(info) => info.changed,
                        None => true,
                    };
                    if changed {
                        tile.is_same_content = false;
                        break;
                    }
                }
            }

            // Clear any dependencies so that when we rebuild them we
            // can compare if the tile has the same content.
            tile.clear();
        }
    }

    /// Update the dependencies for each tile for a given primitive instance.
    pub fn update_prim_dependencies(
        &mut self,
        prim_instance: &PrimitiveInstance,
        clip_chain_stack: &ClipChainStack,
        prim_rect: LayoutRect,
        clip_scroll_tree: &ClipScrollTree,
        data_stores: &DataStores,
        clip_chain_nodes: &[ClipChainNode],
        pictures: &[PicturePrimitive],
        resource_cache: &ResourceCache,
        opacity_binding_store: &OpacityBindingStorage,
        image_instances: &ImageInstanceStorage,
    ) -> bool {
        // If the tile cache is disabled, there's no need to update
        // the primitive dependencies.
        if !self.is_enabled {
            // Return true to signal that we didn't early cull this primitive.
            return true;
        }

        self.map_local_to_world.set_target_spatial_node(
            prim_instance.spatial_node_index,
            clip_scroll_tree,
        );

        // Map the primitive local rect into world space.
        let world_rect = match self.map_local_to_world.map(&prim_rect) {
            Some(rect) => rect,
            None => return false,
        };

        // If the rect is invalid, no need to create dependencies.
        if world_rect.size.width <= 0.0 || world_rect.size.height <= 0.0 {
            return false;
        }

        // Get the tile coordinates in the picture space.
        let (p0, p1) = self.get_tile_coords_for_rect(&world_rect);

        // If the primitive is outside the tiling rects, it's known to not
        // be visible.
        if p0.x == p1.x || p0.y == p1.y {
            return false;
        }

        // Build the list of resources that this primitive has dependencies on.
        let mut opacity_bindings: SmallVec<[OpacityBinding; 4]> = SmallVec::new();
        let mut clip_chain_uids: SmallVec<[ItemUid; 8]> = SmallVec::new();
        let mut clip_vertices: SmallVec<[WorldPoint; 8]> = SmallVec::new();
        let mut image_keys: SmallVec<[ImageKey; 8]> = SmallVec::new();
        let mut clip_spatial_nodes = FastHashSet::default();

        // TODO(gw): We only care about world clip rects that don't have the main
        //           scroll root as an ancestor. It may be a worthwhile optimization
        //           to check for these and skip them.
        let mut world_clips: SmallVec<[(RectangleKey, SpatialNodeIndex); 4]> = SmallVec::default();

        // Some primitives can not be cached (e.g. external video images)
        let is_cacheable = prim_instance.is_cacheable(
            &data_stores,
            resource_cache,
        );

        // For pictures, we don't (yet) know the valid clip rect, so we can't correctly
        // use it to calculate the local bounding rect for the tiles. If we include them
        // then we may calculate a bounding rect that is too large, since it won't include
        // the clip bounds of the picture. Excluding them from the bounding rect here
        // fixes any correctness issues (the clips themselves are considered when we
        // consider the bounds of the primitives that are *children* of the picture),
        // however it does potentially result in some un-necessary invalidations of a
        // tile (in cases where the picture local rect affects the tile, but the clip
        // rect eventually means it doesn't affect that tile).
        // TODO(gw): Get picture clips earlier (during the initial picture traversal
        //           pass) so that we can calculate these correctly.
        let include_clip_rect = match prim_instance.kind {
            PrimitiveInstanceKind::Picture { pic_index,.. } => {
                // Pictures can depend on animated opacity bindings.
                let pic = &pictures[pic_index.0];
                if let Some(PictureCompositeMode::Filter(FilterOp::Opacity(binding, _))) = pic.requested_composite_mode {
                    opacity_bindings.push(binding.into());
                }

                false
            }
            PrimitiveInstanceKind::Rectangle { opacity_binding_index, .. } => {
                if opacity_binding_index != OpacityBindingIndex::INVALID {
                    let opacity_binding = &opacity_binding_store[opacity_binding_index];
                    for binding in &opacity_binding.bindings {
                        opacity_bindings.push(OpacityBinding::from(*binding));
                    }
                }

                true
            }
            PrimitiveInstanceKind::Image { data_handle, image_instance_index, .. } => {
                let image_data = &data_stores.image[data_handle].kind;
                let image_instance = &image_instances[image_instance_index];
                let opacity_binding_index = image_instance.opacity_binding_index;

                if opacity_binding_index != OpacityBindingIndex::INVALID {
                    let opacity_binding = &opacity_binding_store[opacity_binding_index];
                    for binding in &opacity_binding.bindings {
                        opacity_bindings.push(OpacityBinding::from(*binding));
                    }
                }

                image_keys.push(image_data.key);
                true
            }
            PrimitiveInstanceKind::YuvImage { data_handle, .. } => {
                let yuv_image_data = &data_stores.yuv_image[data_handle].kind;
                image_keys.extend_from_slice(&yuv_image_data.yuv_key);
                true
            }
            PrimitiveInstanceKind::TextRun { .. } |
            PrimitiveInstanceKind::LineDecoration { .. } |
            PrimitiveInstanceKind::Clear { .. } |
            PrimitiveInstanceKind::NormalBorder { .. } |
            PrimitiveInstanceKind::LinearGradient { .. } |
            PrimitiveInstanceKind::RadialGradient { .. } |
            PrimitiveInstanceKind::ImageBorder { .. } => {
                // These don't contribute dependencies
                true
            }
        };

        // The transforms of any clips that are relative to the picture may affect
        // the content rendered by this primitive.
        let mut world_clip_rect = world_rect;
        let mut culling_rect = prim_rect
            .intersection(&prim_instance.local_clip_rect)
            .unwrap_or(LayoutRect::zero());

        // To maintain the previous logic, consider every clip in the current active
        // clip stack that could affect this primitive.
        // TODO(gw): We can make this much more efficient now, by taking advantage
        //           of the per-picture clip chain information, rather then considering
        //           it for every primitive, as we do here for simplicity.
        for clip_stack in &clip_chain_stack.stack {
            for clip_chain_id in clip_stack {
                let mut current_clip_chain_id = *clip_chain_id;
                while current_clip_chain_id != ClipChainId::NONE {
                    let clip_chain_node = &clip_chain_nodes[current_clip_chain_id.0 as usize];
                    let clip_node = &data_stores.clip[clip_chain_node.handle];

                    // We can skip the root clip node - it will be taken care of by the
                    // world bounding rect calculated for the cache.
                    if current_clip_chain_id == self.root_clip_chain_id {
                        current_clip_chain_id = clip_chain_node.parent_clip_chain_id;
                        continue;
                    }

                    self.map_local_to_world.set_target_spatial_node(
                        clip_chain_node.spatial_node_index,
                        clip_scroll_tree,
                    );

                    // Clips that are simple rects and handled by collapsing them into a single
                    // clip rect. This avoids the need to store vertices for these cases, and also
                    // allows easy calculation of the overall bounds of the tile cache.
                    let add_to_clip_deps = match clip_node.item {
                        ClipItem::Rectangle(size, ClipMode::Clip) => {
                            let clip_spatial_node = &clip_scroll_tree.spatial_nodes[clip_chain_node.spatial_node_index.0 as usize];

                            let local_clip_rect = LayoutRect::new(
                                clip_chain_node.local_pos,
                                size,
                            );

                            if clip_spatial_node.coordinate_system_id == CoordinateSystemId(0) {
                                // Clips that are not in the root coordinate system are not axis-aligned,
                                // so we need to treat them as normal style clips with vertices.
                                match self.map_local_to_world.map(&local_clip_rect) {
                                    Some(clip_world_rect) => {
                                        // Even if this ends up getting clipped out by the current clip
                                        // stack, we want to ensure the primitive gets added to the tiles
                                        // below, to ensure invalidation isn't tripped up by the wrong
                                        // number of primitives that affect this tile.
                                        world_clip_rect = world_clip_rect
                                            .intersection(&clip_world_rect)
                                            .unwrap_or(WorldRect::zero());

                                        // If the clip rect is in the same spatial node, it can be handled by the
                                        // local clip rect.
                                        if clip_chain_node.spatial_node_index == prim_instance.spatial_node_index {
                                            culling_rect = culling_rect.intersection(&local_clip_rect).unwrap_or(LayoutRect::zero());

                                            false
                                        } else if !clip_scroll_tree.is_same_or_child_of(
                                            clip_chain_node.spatial_node_index,
                                            self.spatial_node_index,
                                        ) {
                                            // If the clip node is *not* a child of the main scroll root,
                                            // add it to the list of potential world clips to be checked later.
                                            // If it *is* a child of the main scroll root, then just track
                                            // it as a normal clip dependency, since it likely moves in
                                            // the same way as the primitive when scrolling (and if it doesn't,
                                            // we want to invalidate and rasterize).
                                            world_clips.push((
                                                clip_world_rect.into(),
                                                clip_chain_node.spatial_node_index,
                                            ));

                                            false
                                        } else {
                                            true
                                        }
                                    }
                                    None => {
                                        true
                                    }
                                }
                            } else {
                                true
                            }
                        }
                        ClipItem::Rectangle(_, ClipMode::ClipOut) |
                        ClipItem::RoundedRectangle(..) |
                        ClipItem::Image { .. } |
                        ClipItem::BoxShadow(..) => {
                            true
                        }
                    };

                    if add_to_clip_deps {
                        clip_chain_uids.push(clip_chain_node.handle.uid());

                        // If the clip has the same spatial node, the relative transform
                        // will always be the same, so there's no need to depend on it.
                        if clip_chain_node.spatial_node_index != self.spatial_node_index {
                            clip_spatial_nodes.insert(clip_chain_node.spatial_node_index);
                        }

                        let local_clip_rect = LayoutRect::new(
                            clip_chain_node.local_pos,
                            LayoutSize::zero(),
                        );
                        if let Some(world_clip_rect) = self.map_local_to_world.map(&local_clip_rect) {
                            clip_vertices.push(world_clip_rect.origin);
                        }
                    }

                    current_clip_chain_id = clip_chain_node.parent_clip_chain_id;
                }
            }
        }

        if include_clip_rect {
            // Intersect the calculated prim bounds with the root clip rect, to save
            // having to process and transform the root clip rect in every primitive.
            if let Some(clipped_world_rect) = world_clip_rect.intersection(&self.root_clip_rect) {
                self.world_bounding_rect = self.world_bounding_rect.union(&clipped_world_rect);
            }
        }

        self.map_local_to_world.set_target_spatial_node(
            prim_instance.spatial_node_index,
            clip_scroll_tree,
        );
        let world_culling_rect = match self.map_local_to_world.map(&culling_rect) {
            Some(rect) => rect,
            None => return false,
        };

        // Normalize the tile coordinates before adding to tile dependencies.
        // For each affected tile, mark any of the primitive dependencies.
        for y in p0.y .. p1.y {
            for x in p0.x .. p1.x {
                let index = (y * self.tile_count.width + x) as usize;
                let tile = &mut self.tiles[index];

                // Store the local clip rect by calculating what portion
                // of the tile it covers.
                let world_culling_rect = world_culling_rect
                    .intersection(&tile.world_rect)
                    .map(|rect| {
                        rect.translate(&-tile.world_rect.origin.to_vector())
                    })
                    .unwrap_or(WorldRect::zero())
                    .round();

                // Work out the needed rect for the primitive on this tile.
                // TODO(gw): We should be able to remove this for any tile that is not
                //           a partially clipped tile, which would be a significant
                //           optimization for the common case (non-clipped tiles).

                // Mark if the tile is cacheable at all.
                tile.is_same_content &= is_cacheable;

                // Include any image keys this tile depends on.
                tile.descriptor.image_keys.extend_from_slice(&image_keys);

                // // Include any opacity bindings this primitive depends on.
                tile.descriptor.opacity_bindings.extend_from_slice(&opacity_bindings);

                // Update the tile descriptor, used for tile comparison during scene swaps.
                tile.descriptor.prims.push(PrimitiveDescriptor {
                    prim_uid: prim_instance.uid(),
                    origin: (world_rect.origin - tile.world_rect.origin.to_vector()).round(),
                    first_clip: tile.descriptor.clip_uids.len() as u16,
                    clip_count: clip_chain_uids.len() as u16,
                    world_culling_rect,
                });
                tile.descriptor.clip_uids.extend_from_slice(&clip_chain_uids);
                for clip_vertex in &clip_vertices {
                    let clip_vertex = (*clip_vertex - tile.world_rect.origin.to_vector()).round();
                    tile.descriptor.clip_vertices.push(clip_vertex.into());
                }

                // If the primitive has the same spatial node, the relative transform
                // will always be the same, so there's no need to depend on it.
                if prim_instance.spatial_node_index != self.spatial_node_index {
                    tile.transforms.insert(prim_instance.spatial_node_index);
                }

                for spatial_node_index in &clip_spatial_nodes {
                    tile.transforms.insert(*spatial_node_index);
                }
                for (world_rect, spatial_node_index) in &world_clips {
                    tile.potential_clips.insert(world_rect.clone(), *spatial_node_index);
                }
            }
        }

        true
    }

    /// Apply any updates after prim dependency updates. This applies
    /// any late tile invalidations, and sets up the dirty rect and
    /// set of tile blits.
    pub fn post_update(
        &mut self,
        resource_cache: &mut ResourceCache,
        gpu_cache: &mut GpuCache,
        frame_context: &FrameVisibilityContext,
        scratch: &mut PrimitiveScratchBuffer,
    ) -> LayoutRect {
        self.dirty_region.clear();
        self.pending_blits.clear();

        // If the tile cache is disabled, just return a no-op local clip rect.
        if !self.is_enabled {
            return LayoutRect::max_rect();
        }

        let dim = self.tile_dimensions(frame_context.config.testing);
        let descriptor = ImageDescriptor::new(
            dim.width,
            dim.height,
            ImageFormat::BGRA8,
            true,
            false,
        );

        // Skip all tiles if completely off-screen.
        if !self.world_bounding_rect.intersects(&frame_context.screen_world_rect) {
            return LayoutRect::zero();
        }

        let map_surface_to_world: SpaceMapper<LayoutPixel, WorldPixel> = SpaceMapper::new_with_target(
            ROOT_SPATIAL_NODE_INDEX,
            self.spatial_node_index,
            frame_context.screen_world_rect,
            frame_context.clip_scroll_tree,
        );

        let local_clip_rect = map_surface_to_world
            .unmap(&self.world_bounding_rect)
            .expect("bug: unable to map local clip rect");

        // Step through each tile and invalidate if the dependencies have changed.
        for (i, tile) in self.tiles.iter_mut().enumerate() {
            // Deal with any potential world clips. Check to see if they are
            // outside the tile cache bounding rect. If they are, they're not
            // relevant and we don't care if they move relative to the content
            // itself. This avoids a lot of redundant invalidations.
            for (clip_world_rect, spatial_node_index) in &tile.potential_clips {
                let clip_world_rect = WorldRect::from(clip_world_rect.clone());
                if !clip_world_rect.contains_rect(&self.world_bounding_rect) {
                    tile.transforms.insert(*spatial_node_index);
                }
            }

            // Update tile transforms
            let mut transform_spatial_nodes: Vec<SpatialNodeIndex> = tile.transforms.drain().collect();
            transform_spatial_nodes.sort();
            for spatial_node_index in transform_spatial_nodes {
                let xf = frame_context.clip_scroll_tree.get_relative_transform(
                    self.spatial_node_index,
                    spatial_node_index,
                ).expect("BUG: unable to get relative transform");
                // Store the result of transforming a fixed point by this
                // transform.
                // TODO(gw): This could in theory give incorrect results for a
                //           primitive behind the near plane.
                let key = xf.transform_point2d(&LayoutPoint::zero()).unwrap_or(LayoutPoint::zero()).round();
                tile.descriptor.transforms.push(key.into());
            }

            // Invalidate if the backing texture was evicted.
            if resource_cache.texture_cache.is_allocated(&tile.handle) {
                // Request the backing texture so it won't get evicted this frame.
                // We specifically want to mark the tile texture as used, even
                // if it's detected not visible below and skipped. This is because
                // we maintain the set of tiles we care about based on visibility
                // during pre_update. If a tile still exists after that, we are
                // assuming that it's either visible or we want to retain it for
                // a while in case it gets scrolled back onto screen soon.
                // TODO(gw): Consider switching to manual eviction policy?
                resource_cache.texture_cache.request(&tile.handle, gpu_cache);
            } else {
                tile.is_valid = false;
            }

            // Invalidate the tile based on the content changing.
            tile.update_content_validity();

            let visible_rect = match tile.visible_rect {
                Some(rect) => rect,
                None => continue,
            };

            // Check the valid rect of the primitive is sufficient.
            let tile_bounding_rect = match visible_rect.intersection(&self.world_bounding_rect) {
                Some(rect) => rect.translate(&-tile.world_rect.origin.to_vector()),
                None => continue,
            };

            tile.update_rect_validity(&tile_bounding_rect);

            // If there are no primitives there is no need to draw or cache it.
            if tile.descriptor.prims.is_empty() {
                continue;
            }

            // Decide how to handle this tile when drawing this frame.
            if tile.is_valid {
                // No need to include this is any dirty rect calculations.
                tile.consider_for_dirty_rect = false;
                self.tiles_to_draw.push(TileIndex(i));

                if frame_context.debug_flags.contains(DebugFlags::PICTURE_CACHING_DBG) {
                    if let Some(world_rect) = tile.world_rect.intersection(&self.world_bounding_rect) {
                        let tile_device_rect = world_rect * frame_context.device_pixel_scale;
                        let mut label_offset = DeviceVector2D::new(20.0, 30.0);
                        scratch.push_debug_rect(
                            tile_device_rect,
                            debug_colors::GREEN,
                        );
                        if tile_device_rect.size.height >= label_offset.y {
                            scratch.push_debug_string(
                                tile_device_rect.origin + label_offset,
                                debug_colors::RED,
                                format!("{:?} {:?} {:?}", tile.id, tile.handle, tile.world_rect),
                            );
                        }
                        label_offset.y += 20.0;
                        if tile_device_rect.size.height >= label_offset.y {
                            scratch.push_debug_string(
                                tile_device_rect.origin + label_offset,
                                debug_colors::RED,
                                format!("same: {} frames", tile.same_frames),
                            );
                        }
                    }
                }
            } else {
                if frame_context.debug_flags.contains(DebugFlags::PICTURE_CACHING_DBG) {
                    if let Some(world_rect) = visible_rect.intersection(&self.world_bounding_rect) {
                        scratch.push_debug_rect(
                            world_rect * frame_context.device_pixel_scale,
                            debug_colors::RED,
                        );
                    }
                }

                // Only cache tiles that have had the same content for at least two
                // frames. This skips caching on pages / benchmarks that are changing
                // every frame, which is wasteful.
                if tile.same_frames >= FRAMES_BEFORE_PICTURE_CACHING {
                    // Ensure that this texture is allocated.
                    resource_cache.texture_cache.update(
                        &mut tile.handle,
                        descriptor,
                        TextureFilter::Linear,
                        None,
                        [0.0; 3],
                        DirtyRect::All,
                        gpu_cache,
                        None,
                        UvRectKind::Rect,
                        Eviction::Eager,
                    );

                    let cache_item = resource_cache
                        .get_texture_cache_item(&tile.handle);

                    let src_origin = (visible_rect.origin * frame_context.device_pixel_scale).round().to_i32();
                    let valid_rect = visible_rect.translate(&-tile.world_rect.origin.to_vector());

                    tile.valid_rect = visible_rect
                        .intersection(&self.world_bounding_rect)
                        .map(|rect| rect.translate(&-tile.world_rect.origin.to_vector()))
                        .unwrap_or(WorldRect::zero());

                    // Store a blit operation to be done after drawing the
                    // frame in order to update the cached texture tile.
                    let dest_rect = (valid_rect * frame_context.device_pixel_scale).round().to_i32();
                    self.pending_blits.push(TileBlit {
                        target: cache_item,
                        src_offset: src_origin,
                        dest_offset: dest_rect.origin,
                        size: dest_rect.size,
                    });

                    // We can consider this tile valid now.
                    tile.is_valid = true;
                }

                // This tile should be considered as part of the dirty rect calculations.
                tile.consider_for_dirty_rect = true;
            }
        }

        // Build a minimal set of dirty rects from the set of dirty tiles that
        // were found above.
        let mut builder = DirtyRegionBuilder::new(
            &mut self.tiles,
            self.tile_count,
        );

        builder.build(&mut self.dirty_region);

        // When under test, record a copy of the dirty region to support
        // invalidation testing in wrench.
        if frame_context.config.testing {
            scratch.recorded_dirty_regions.push(self.dirty_region.record());
        }

        // If we end up with too many dirty rects, then it's going to be a lot
        // of extra draw calls to submit (since we currently just submit every
        // draw call for every dirty rect). In this case, bail out and work
        // with a single, large dirty rect. In future we can consider improving
        // on this by supporting batching per dirty region.
        if self.dirty_region.dirty_rects.len() > MAX_DIRTY_RECTS {
            self.dirty_region.collapse();
        }

        local_clip_rect
    }

    fn tile_dimensions(&self, testing: bool) -> DeviceIntSize {
        if testing {
            size2(TILE_SIZE_TESTING, TILE_SIZE_TESTING)
        } else {
            size2(TILE_SIZE_WIDTH, TILE_SIZE_HEIGHT)
        }
    }
}

/// Maintains a stack of picture and surface information, that
/// is used during the initial picture traversal.
pub struct PictureUpdateState<'a> {
    surfaces: &'a mut Vec<SurfaceInfo>,
    surface_stack: Vec<SurfaceIndex>,
    picture_stack: Vec<PictureInfo>,
    are_raster_roots_assigned: bool,
}

impl<'a> PictureUpdateState<'a> {
    pub fn update_all(
        surfaces: &'a mut Vec<SurfaceInfo>,
        pic_index: PictureIndex,
        picture_primitives: &mut [PicturePrimitive],
        frame_context: &FrameBuildingContext,
        gpu_cache: &mut GpuCache,
        clip_store: &ClipStore,
        clip_data_store: &ClipDataStore,
    ) {
        let mut state = PictureUpdateState {
            surfaces,
            surface_stack: vec![SurfaceIndex(0)],
            picture_stack: Vec::new(),
            are_raster_roots_assigned: true,
        };

        state.update(
            pic_index,
            ClipChainId::NONE,
            picture_primitives,
            frame_context,
            gpu_cache,
            clip_store,
            clip_data_store,
        );

        if !state.are_raster_roots_assigned {
            state.assign_raster_roots(
                pic_index,
                picture_primitives,
                ROOT_SPATIAL_NODE_INDEX,
            );
        }
    }

    /// Return the current surface
    fn current_surface(&self) -> &SurfaceInfo {
        &self.surfaces[self.surface_stack.last().unwrap().0]
    }

    /// Return the current surface (mutable)
    fn current_surface_mut(&mut self) -> &mut SurfaceInfo {
        &mut self.surfaces[self.surface_stack.last().unwrap().0]
    }

    /// Push a new surface onto the update stack.
    fn push_surface(
        &mut self,
        surface: SurfaceInfo,
    ) -> SurfaceIndex {
        let surface_index = SurfaceIndex(self.surfaces.len());
        self.surfaces.push(surface);
        self.surface_stack.push(surface_index);
        surface_index
    }

    /// Pop a surface on the way up the picture traversal
    fn pop_surface(&mut self) -> SurfaceIndex{
        self.surface_stack.pop().unwrap()
    }

    /// Return the current picture, or None if stack is empty.
    fn current_picture(&self) -> Option<&PictureInfo> {
        self.picture_stack.last()
    }

    /// Push information about a picture on the update stack
    fn push_picture(
        &mut self,
        info: PictureInfo,
    ) {
        self.picture_stack.push(info);
    }

    /// Pop the picture info off, on the way up the picture traversal
    fn pop_picture(
        &mut self,
    ) -> PictureInfo {
        self.picture_stack.pop().unwrap()
    }

    /// Update a picture, determining surface configuration,
    /// rasterization roots, and (in future) whether there
    /// are cached surfaces that can be used by this picture.
    fn update(
        &mut self,
        pic_index: PictureIndex,
        clip_chain_id: ClipChainId,
        picture_primitives: &mut [PicturePrimitive],
        frame_context: &FrameBuildingContext,
        gpu_cache: &mut GpuCache,
        clip_store: &ClipStore,
        clip_data_store: &ClipDataStore,
    ) {
        if let Some(prim_list) = picture_primitives[pic_index.0].pre_update(
            clip_chain_id,
            self,
            frame_context,
            clip_store,
            clip_data_store,
        ) {
            for (child_pic_index, clip_chain_id) in &prim_list.pictures {
                self.update(
                    *child_pic_index,
                    *clip_chain_id,
                    picture_primitives,
                    frame_context,
                    gpu_cache,
                    clip_store,
                    clip_data_store,
                );
            }

            picture_primitives[pic_index.0].post_update(
                prim_list,
                self,
                frame_context,
                gpu_cache,
            );
        }
    }

    /// Process the picture tree again in a depth-first order,
    /// and adjust the raster roots of the pictures that want to establish
    /// their own roots but are not able to due to the size constraints.
    fn assign_raster_roots(
        &mut self,
        pic_index: PictureIndex,
        picture_primitives: &[PicturePrimitive],
        fallback_raster_spatial_node: SpatialNodeIndex,
    ) {
        let picture = &picture_primitives[pic_index.0];
        if !picture.is_visible() {
            return
        }

        let new_fallback = match picture.raster_config {
            Some(ref config) => {
                let surface = &mut self.surfaces[config.surface_index.0];
                if !config.establishes_raster_root {
                    surface.raster_spatial_node_index = fallback_raster_spatial_node;
                }
                surface.raster_spatial_node_index
            }
            None => fallback_raster_spatial_node,
        };

        for (child_pic_index, _) in &picture.prim_list.pictures {
            self.assign_raster_roots(*child_pic_index, picture_primitives, new_fallback);
        }
    }
}

#[derive(Debug, Copy, Clone, PartialEq)]
pub struct SurfaceIndex(pub usize);

pub const ROOT_SURFACE_INDEX: SurfaceIndex = SurfaceIndex(0);

/// Information about an offscreen surface. For now,
/// it contains information about the size and coordinate
/// system of the surface. In the future, it will contain
/// information about the contents of the surface, which
/// will allow surfaces to be cached / retained between
/// frames and display lists.
#[derive(Debug)]
pub struct SurfaceInfo {
    /// A local rect defining the size of this surface, in the
    /// coordinate system of the surface itself.
    pub rect: PictureRect,
    /// Helper structs for mapping local rects in different
    /// coordinate systems into the surface coordinates.
    pub map_local_to_surface: SpaceMapper<LayoutPixel, PicturePixel>,
    /// Defines the positioning node for the surface itself,
    /// and the rasterization root for this surface.
    pub raster_spatial_node_index: SpatialNodeIndex,
    pub surface_spatial_node_index: SpatialNodeIndex,
    /// This is set when the render task is created.
    pub surface: Option<PictureSurface>,
    /// A list of render tasks that are dependencies of this surface.
    pub tasks: Vec<RenderTaskId>,
    /// How much the local surface rect should be inflated (for blur radii).
    pub inflation_factor: f32,
}

impl SurfaceInfo {
    pub fn new(
        surface_spatial_node_index: SpatialNodeIndex,
        raster_spatial_node_index: SpatialNodeIndex,
        inflation_factor: f32,
        world_rect: WorldRect,
        clip_scroll_tree: &ClipScrollTree,
    ) -> Self {
        let map_surface_to_world = SpaceMapper::new_with_target(
            ROOT_SPATIAL_NODE_INDEX,
            surface_spatial_node_index,
            world_rect,
            clip_scroll_tree,
        );

        let pic_bounds = map_surface_to_world
            .unmap(&map_surface_to_world.bounds)
            .unwrap_or(PictureRect::max_rect());

        let map_local_to_surface = SpaceMapper::new(
            surface_spatial_node_index,
            pic_bounds,
        );

        SurfaceInfo {
            rect: PictureRect::zero(),
            map_local_to_surface,
            surface: None,
            raster_spatial_node_index,
            surface_spatial_node_index,
            tasks: Vec::new(),
            inflation_factor,
        }
    }

    /// Take the set of child render tasks for this surface. This is
    /// used when constructing the render task tree.
    pub fn take_render_tasks(&mut self) -> Vec<RenderTaskId> {
        mem::replace(&mut self.tasks, Vec::new())
    }
}

#[derive(Debug)]
pub struct RasterConfig {
    /// How this picture should be composited into
    /// the parent surface.
    pub composite_mode: PictureCompositeMode,
    /// Index to the surface descriptor for this
    /// picture.
    pub surface_index: SurfaceIndex,
    /// Whether this picture establishes a rasterization root.
    pub establishes_raster_root: bool,
}

bitflags! {
    /// A set of flags describing why a picture may need a backing surface.
    pub struct BlitReason: u32 {
        /// Mix-blend-mode on a child that requires isolation.
        const ISOLATE = 1;
        /// Clip node that _might_ require a surface.
        const CLIP = 2;
        /// Preserve-3D requires a surface for plane-splitting.
        const PRESERVE3D = 4;
    }
}

/// Specifies how this Picture should be composited
/// onto the target it belongs to.
#[allow(dead_code)]
#[derive(Debug, Copy, Clone, PartialEq)]
pub enum PictureCompositeMode {
    /// Apply CSS mix-blend-mode effect.
    MixBlend(MixBlendMode),
    /// Apply a CSS filter.
    Filter(FilterOp),
    /// Draw to intermediate surface, copy straight across. This
    /// is used for CSS isolation, and plane splitting.
    Blit(BlitReason),
    /// Used to cache a picture as a series of tiles.
    TileCache {
        clear_color: ColorF,
    },
}

// Stores the location of the picture if it is drawn to
// an intermediate surface. This can be a render task if
// it is not persisted, or a texture cache item if the
// picture is cached in the texture cache.
#[derive(Debug)]
pub enum PictureSurface {
    RenderTask(RenderTaskId),
    #[allow(dead_code)]
    TextureCache(RenderTaskCacheEntryHandle),
}

/// Enum value describing the place of a picture in a 3D context.
#[derive(Clone, Debug)]
pub enum Picture3DContext<C> {
    /// The picture is not a part of 3D context sub-hierarchy.
    Out,
    /// The picture is a part of 3D context.
    In {
        /// Additional data per child for the case of this a root of 3D hierarchy.
        root_data: Option<Vec<C>>,
        /// The spatial node index of an "ancestor" element, i.e. one
        /// that establishes the transformed element’s containing block.
        ///
        /// See CSS spec draft for more details:
        /// https://drafts.csswg.org/css-transforms-2/#accumulated-3d-transformation-matrix-computation
        ancestor_index: SpatialNodeIndex,
    },
}

/// Information about a preserve-3D hierarchy child that has been plane-split
/// and ordered according to the view direction.
#[derive(Clone, Debug)]
pub struct OrderedPictureChild {
    pub anchor: usize,
    pub transform_id: TransformPaletteId,
    pub gpu_address: GpuCacheAddress,
}

/// Defines the grouping key for a cluster of primitives in a picture.
/// In future this will also contain spatial grouping details.
#[derive(Hash, Eq, PartialEq, Copy, Clone)]
struct PrimitiveClusterKey {
    /// Grouping primitives by spatial node ensures that we can calculate a local
    /// bounding volume for the cluster, and then transform that by the spatial
    /// node transform once to get an updated bounding volume for the entire cluster.
    spatial_node_index: SpatialNodeIndex,
    /// We want to separate clusters that have different backface visibility properties
    /// so that we can accept / reject an entire cluster at once if the backface is not
    /// visible.
    is_backface_visible: bool,
}

/// Descriptor for a cluster of primitives. For now, this is quite basic but will be
/// extended to handle more spatial clustering of primitives.
pub struct PrimitiveCluster {
    /// The positioning node for this cluster.
    spatial_node_index: SpatialNodeIndex,
    /// Whether this cluster is visible when the position node is a backface.
    is_backface_visible: bool,
    /// The bounding rect of the cluster, in the local space of the spatial node.
    /// This is used to quickly determine the overall bounding rect for a picture
    /// during the first picture traversal, which is needed for local scale
    /// determination, and render task size calculations.
    bounding_rect: LayoutRect,
    /// This flag is set during the first pass picture traversal, depending on whether
    /// the cluster is visible or not. It's read during the second pass when primitives
    /// consult their owning clusters to see if the primitive itself is visible.
    pub is_visible: bool,
}

impl PrimitiveCluster {
    fn new(
        spatial_node_index: SpatialNodeIndex,
        is_backface_visible: bool,
    ) -> Self {
        PrimitiveCluster {
            bounding_rect: LayoutRect::zero(),
            spatial_node_index,
            is_backface_visible,
            is_visible: false,
        }
    }
}

#[derive(Debug, Copy, Clone)]
pub struct PrimitiveClusterIndex(pub u32);

#[derive(Debug, Copy, Clone)]
pub struct ClusterIndex(pub u16);

impl ClusterIndex {
    pub const INVALID: ClusterIndex = ClusterIndex(u16::MAX);
}

/// A list of pictures, stored by the PrimitiveList to enable a
/// fast traversal of just the pictures.
pub type PictureList = SmallVec<[(PictureIndex, ClipChainId); 4]>;

/// A list of primitive instances that are added to a picture
/// This ensures we can keep a list of primitives that
/// are pictures, for a fast initial traversal of the picture
/// tree without walking the instance list.
pub struct PrimitiveList {
    /// The primitive instances, in render order.
    pub prim_instances: Vec<PrimitiveInstance>,
    /// List of pictures that are part of this list.
    /// Used to implement the picture traversal pass.
    pub pictures: PictureList,
    /// List of primitives grouped into clusters.
    pub clusters: SmallVec<[PrimitiveCluster; 4]>,
}

impl PrimitiveList {
    /// Construct an empty primitive list. This is
    /// just used during the take_context / restore_context
    /// borrow check dance, which will be removed as the
    /// picture traversal pass is completed.
    pub fn empty() -> Self {
        PrimitiveList {
            prim_instances: Vec::new(),
            pictures: SmallVec::new(),
            clusters: SmallVec::new(),
        }
    }

    /// Construct a new prim list from a list of instances
    /// in render order. This does some work during scene
    /// building which makes the frame building traversals
    /// significantly faster.
    pub fn new(
        mut prim_instances: Vec<PrimitiveInstance>,
        interners: &Interners
    ) -> Self {
        let mut pictures = SmallVec::new();
        let mut clusters_map = FastHashMap::default();
        let mut clusters: SmallVec<[PrimitiveCluster; 4]> = SmallVec::new();

        // Walk the list of primitive instances and extract any that
        // are pictures.
        for prim_instance in &mut prim_instances {
            // Check if this primitive is a picture. In future we should
            // remove this match and embed this info directly in the primitive instance.
            let is_pic = match prim_instance.kind {
                PrimitiveInstanceKind::Picture { pic_index, .. } => {
                    pictures.push((pic_index, prim_instance.clip_chain_id));
                    true
                }
                _ => {
                    false
                }
            };

            let prim_data = match prim_instance.kind {
                PrimitiveInstanceKind::Rectangle { data_handle, .. } |
                PrimitiveInstanceKind::Clear { data_handle, .. } => {
                    &interners.prim[data_handle]
                }
                PrimitiveInstanceKind::Image { data_handle, .. } => {
                    &interners.image[data_handle]
                }
                PrimitiveInstanceKind::ImageBorder { data_handle, .. } => {
                    &interners.image_border[data_handle]
                }
                PrimitiveInstanceKind::LineDecoration { data_handle, .. } => {
                    &interners.line_decoration[data_handle]
                }
                PrimitiveInstanceKind::LinearGradient { data_handle, .. } => {
                    &interners.linear_grad[data_handle]
                }
                PrimitiveInstanceKind::NormalBorder { data_handle, .. } => {
                    &interners.normal_border[data_handle]
                }
                PrimitiveInstanceKind::Picture { data_handle, .. } => {
                    &interners.picture[data_handle]
                }
                PrimitiveInstanceKind::RadialGradient { data_handle, ..} => {
                    &interners.radial_grad[data_handle]
                }
                PrimitiveInstanceKind::TextRun { data_handle, .. } => {
                    &interners.text_run[data_handle]
                }
                PrimitiveInstanceKind::YuvImage { data_handle, .. } => {
                    &interners.yuv_image[data_handle]
                }
            };

            // Get the key for the cluster that this primitive should
            // belong to.
            let key = PrimitiveClusterKey {
                spatial_node_index: prim_instance.spatial_node_index,
                is_backface_visible: prim_data.is_backface_visible,
            };

            // Find the cluster, or create a new one.
            let cluster_index = *clusters_map
                .entry(key)
                .or_insert_with(|| {
                    let index = clusters.len();
                    clusters.push(PrimitiveCluster::new(
                        prim_instance.spatial_node_index,
                        prim_data.is_backface_visible,
                    ));
                    index
                }
            );

            // Pictures don't have a known static local bounding rect (they are
            // calculated during the picture traversal dynamically). If not
            // a picture, include a minimal bounding rect in the cluster bounds.
            let cluster = &mut clusters[cluster_index];
            if !is_pic {
                let prim_rect = LayoutRect::new(
                    prim_instance.prim_origin,
                    prim_data.prim_size,
                );
                let culling_rect = prim_instance.local_clip_rect
                    .intersection(&prim_rect)
                    .unwrap_or(LayoutRect::zero());

                cluster.bounding_rect = cluster.bounding_rect.union(&culling_rect);
            }

            prim_instance.cluster_index = ClusterIndex(cluster_index as u16);
        }

        PrimitiveList {
            prim_instances,
            pictures,
            clusters,
        }
    }
}

/// Defines configuration options for a given picture primitive.
pub struct PictureOptions {
    /// If true, WR should inflate the bounding rect of primitives when
    /// using a filter effect that requires inflation.
    pub inflate_if_required: bool,
}

impl Default for PictureOptions {
    fn default() -> Self {
        PictureOptions {
            inflate_if_required: true,
        }
    }
}

pub struct PicturePrimitive {
    /// List of primitives, and associated info for this picture.
    pub prim_list: PrimitiveList,

    pub state: Option<(PictureState, PictureContext)>,

    // The pipeline that the primitives on this picture belong to.
    pub pipeline_id: PipelineId,

    // If true, apply the local clip rect to primitive drawn
    // in this picture.
    pub apply_local_clip_rect: bool,

    // If a mix-blend-mode, contains the render task for
    // the readback of the framebuffer that we use to sample
    // from in the mix-blend-mode shader.
    // For drop-shadow filter, this will store the original
    // picture task which would be rendered on screen after
    // blur pass.
    pub secondary_render_task_id: Option<RenderTaskId>,
    /// How this picture should be composited.
    /// If None, don't composite - just draw directly on parent surface.
    pub requested_composite_mode: Option<PictureCompositeMode>,
    /// Requested rasterization space for this picture. It is
    /// a performance hint only.
    pub requested_raster_space: RasterSpace,

    pub raster_config: Option<RasterConfig>,
    pub context_3d: Picture3DContext<OrderedPictureChild>,

    // If requested as a frame output (for rendering
    // pages to a texture), this is the pipeline this
    // picture is the root of.
    pub frame_output_pipeline_id: Option<PipelineId>,
    // An optional cache handle for storing extra data
    // in the GPU cache, depending on the type of
    // picture.
    pub extra_gpu_data_handle: GpuCacheHandle,

    /// The spatial node index of this picture when it is
    /// composited into the parent picture.
    pub spatial_node_index: SpatialNodeIndex,

    /// The local rect of this picture. It is built
    /// dynamically during the first picture traversal.
    pub local_rect: LayoutRect,

    /// Local clip rect for this picture.
    pub local_clip_rect: LayoutRect,

    pub gpu_location: GpuCacheHandle,

    /// If Some(..) the tile cache that is associated with this picture.
    pub tile_cache: Option<TileCache>,

    /// The config options for this picture.
    options: PictureOptions,
}

impl PicturePrimitive {
    pub fn print<T: PrintTreePrinter>(
        &self,
        pictures: &[Self],
        self_index: PictureIndex,
        pt: &mut T,
    ) {
        pt.new_level(format!("{:?}", self_index));
        pt.add_item(format!("prim_count: {:?}", self.prim_list.prim_instances.len()));
        pt.add_item(format!("local_rect: {:?}", self.local_rect));
        if self.apply_local_clip_rect {
            pt.add_item(format!("local_clip_rect: {:?}", self.local_clip_rect));
        }
        pt.add_item(format!("spatial_node_index: {:?}", self.spatial_node_index));
        pt.add_item(format!("raster_config: {:?}", self.raster_config));
        pt.add_item(format!("requested_composite_mode: {:?}", self.requested_composite_mode));

        for (index, _) in &self.prim_list.pictures {
            pictures[index.0].print(pictures, *index, pt);
        }

        pt.end_level();
    }

    fn resolve_scene_properties(&mut self, properties: &SceneProperties) -> bool {
        match self.requested_composite_mode {
            Some(PictureCompositeMode::Filter(ref mut filter)) => {
                match *filter {
                    FilterOp::Opacity(ref binding, ref mut value) => {
                        *value = properties.resolve_float(binding);
                    }
                    _ => {}
                }

                filter.is_visible()
            }
            _ => true,
        }
    }

    pub fn is_visible(&self) -> bool {
        match self.requested_composite_mode {
            Some(PictureCompositeMode::Filter(ref filter)) => {
                filter.is_visible()
            }
            _ => true,
        }
    }

    /// Destroy an existing picture. This is called just before
    /// a frame builder is replaced with a newly built scene. It
    /// gives a picture a chance to retain any cached tiles that
    /// may be useful during the next scene build.
    pub fn destroy(
        mut self,
        retained_tiles: &mut RetainedTiles,
        clip_scroll_tree: &ClipScrollTree,
    ) {
        if let Some(tile_cache) = self.tile_cache.take() {
            // Calculate and store positions of the reference
            // primitives for this tile cache.
            build_ref_prims(
                &tile_cache.reference_prims.ref_prims,
                &mut retained_tiles.ref_prims,
                clip_scroll_tree,
            );

            for tile in tile_cache.tiles {
                retained_tiles.tiles.push(tile);
            }
        }
    }

    // TODO(gw): We have the PictureOptions struct available. We
    //           should move some of the parameter list in this
    //           method to be part of the PictureOptions, and
    //           avoid adding new parameters here.
    pub fn new_image(
        requested_composite_mode: Option<PictureCompositeMode>,
        context_3d: Picture3DContext<OrderedPictureChild>,
        pipeline_id: PipelineId,
        frame_output_pipeline_id: Option<PipelineId>,
        apply_local_clip_rect: bool,
        requested_raster_space: RasterSpace,
        prim_list: PrimitiveList,
        spatial_node_index: SpatialNodeIndex,
        local_clip_rect: LayoutRect,
        tile_cache: Option<TileCache>,
        options: PictureOptions,
    ) -> Self {
        PicturePrimitive {
            prim_list,
            state: None,
            secondary_render_task_id: None,
            requested_composite_mode,
            raster_config: None,
            context_3d,
            frame_output_pipeline_id,
            extra_gpu_data_handle: GpuCacheHandle::new(),
            apply_local_clip_rect,
            pipeline_id,
            requested_raster_space,
            spatial_node_index,
            local_rect: LayoutRect::zero(),
            local_clip_rect,
            gpu_location: GpuCacheHandle::new(),
            tile_cache,
            options,
        }
    }

    pub fn take_context(
        &mut self,
        pic_index: PictureIndex,
        surface_spatial_node_index: SpatialNodeIndex,
        raster_spatial_node_index: SpatialNodeIndex,
        surface_index: SurfaceIndex,
        parent_allows_subpixel_aa: bool,
        frame_state: &mut FrameBuildingState,
        frame_context: &FrameBuildingContext,
    ) -> Option<(PictureContext, PictureState, PrimitiveList)> {
        if !self.is_visible() {
            return None;
        }

        // Extract the raster and surface spatial nodes from the raster
        // config, if this picture establishes a surface. Otherwise just
        // pass in the spatial node indices from the parent context.
        let (raster_spatial_node_index, surface_spatial_node_index, surface_index, inflation_factor) = match self.raster_config {
            Some(ref raster_config) => {
                let surface = &frame_state.surfaces[raster_config.surface_index.0];

                (
                    surface.raster_spatial_node_index,
                    self.spatial_node_index,
                    raster_config.surface_index,
                    surface.inflation_factor,
                )
            }
            None => {
                (
                    raster_spatial_node_index,
                    surface_spatial_node_index,
                    surface_index,
                    0.0,
                )
            }
        };

        let map_pic_to_world = SpaceMapper::new_with_target(
            ROOT_SPATIAL_NODE_INDEX,
            surface_spatial_node_index,
            frame_context.screen_world_rect,
            frame_context.clip_scroll_tree,
        );

        let pic_bounds = map_pic_to_world.unmap(&map_pic_to_world.bounds)
                                         .unwrap_or(PictureRect::max_rect());

        let map_local_to_pic = SpaceMapper::new(
            surface_spatial_node_index,
            pic_bounds,
        );

        let (map_raster_to_world, map_pic_to_raster) = create_raster_mappers(
            surface_spatial_node_index,
            raster_spatial_node_index,
            frame_context.screen_world_rect,
            frame_context.clip_scroll_tree,
        );

        let plane_splitter = match self.context_3d {
            Picture3DContext::Out => {
                None
            }
            Picture3DContext::In { root_data: Some(_), .. } => {
                Some(PlaneSplitter::new())
            }
            Picture3DContext::In { root_data: None, .. } => {
                None
            }
        };

        let state = PictureState {
            //TODO: check for MAX_CACHE_SIZE here?
            is_cacheable: true,
            map_local_to_pic,
            map_pic_to_world,
            map_pic_to_raster,
            map_raster_to_world,
            plane_splitter,
        };

        // Disallow subpixel AA if an intermediate surface is needed.
        // TODO(lsalzman): allow overriding parent if intermediate surface is opaque
        let allow_subpixel_aa = match self.raster_config {
            Some(RasterConfig { composite_mode: PictureCompositeMode::TileCache { clear_color, .. }, .. }) => {
                // If the tile cache has an opaque background, then it's fine to use
                // subpixel rendering (this is the common case).
                clear_color.a >= 1.0
            },
            Some(_) => {
                false
            }
            None => {
                true
            }
        };
        // Still disable subpixel AA if parent forbids it
        let allow_subpixel_aa = parent_allows_subpixel_aa && allow_subpixel_aa;

        let mut dirty_region_count = 0;

        // If this is a picture cache, push the dirty region to ensure any
        // child primitives are culled and clipped to the dirty rect(s).
        if let Some(ref tile_cache) = self.tile_cache {
            // If the tile cache is disabled, it doesn't have a valid
            // dirty region to exclude primitives from.
            if tile_cache.is_enabled {
                frame_state.push_dirty_region(tile_cache.dirty_region.clone());
                dirty_region_count += 1;
            }
        }

        if inflation_factor > 0.0 {
            let inflated_region = frame_state.current_dirty_region().inflate(inflation_factor);
            frame_state.push_dirty_region(inflated_region);
            dirty_region_count += 1;
        }

        let context = PictureContext {
            pic_index,
            pipeline_id: self.pipeline_id,
            apply_local_clip_rect: self.apply_local_clip_rect,
            allow_subpixel_aa,
            is_passthrough: self.raster_config.is_none(),
            raster_space: self.requested_raster_space,
            raster_spatial_node_index,
            surface_spatial_node_index,
            surface_index,
            dirty_region_count,
        };

        let prim_list = mem::replace(&mut self.prim_list, PrimitiveList::empty());

        Some((context, state, prim_list))
    }

    pub fn restore_context(
        &mut self,
        prim_list: PrimitiveList,
        context: PictureContext,
        state: PictureState,
        frame_state: &mut FrameBuildingState,
    ) {
        // Pop any dirty regions this picture set
        for _ in 0 .. context.dirty_region_count {
            frame_state.pop_dirty_region();
        }

        self.prim_list = prim_list;
        self.state = Some((state, context));
    }

    pub fn take_state_and_context(&mut self) -> (PictureState, PictureContext) {
        self.state.take().expect("bug: no state present!")
    }

    /// Add a primitive instance to the plane splitter. The function would generate
    /// an appropriate polygon, clip it against the frustum, and register with the
    /// given plane splitter.
    pub fn add_split_plane(
        splitter: &mut PlaneSplitter,
        transforms: &TransformPalette,
        prim_instance: &PrimitiveInstance,
        original_local_rect: LayoutRect,
        combined_local_clip_rect: &LayoutRect,
        world_rect: WorldRect,
        plane_split_anchor: usize,
    ) -> bool {
        let transform = transforms
            .get_world_transform(prim_instance.spatial_node_index);
        let matrix = transform.cast();

        // Apply the local clip rect here, before splitting. This is
        // because the local clip rect can't be applied in the vertex
        // shader for split composites, since we are drawing polygons
        // rather that rectangles. The interpolation still works correctly
        // since we determine the UVs by doing a bilerp with a factor
        // from the original local rect.
        let local_rect = match original_local_rect
            .intersection(combined_local_clip_rect)
        {
            Some(rect) => rect.cast(),
            None => return false,
        };
        let world_rect = world_rect.cast();

        match transform.transform_kind() {
            TransformedRectKind::AxisAligned => {
                let inv_transform = transforms
                    .get_world_inv_transform(prim_instance.spatial_node_index);
                let polygon = Polygon::from_transformed_rect_with_inverse(
                    local_rect,
                    &matrix,
                    &inv_transform.cast(),
                    plane_split_anchor,
                ).unwrap();
                splitter.add(polygon);
            }
            TransformedRectKind::Complex => {
                let mut clipper = Clipper::new();
                let results = clipper.clip_transformed(
                    Polygon::from_rect(
                        local_rect,
                        plane_split_anchor,
                    ),
                    &matrix,
                    Some(world_rect),
                );
                if let Ok(results) = results {
                    for poly in results {
                        splitter.add(poly);
                    }
                }
            }
        }

        true
    }

    pub fn resolve_split_planes(
        &mut self,
        splitter: &mut PlaneSplitter,
        frame_state: &mut FrameBuildingState,
        clip_scroll_tree: &ClipScrollTree,
    ) {
        let ordered = match self.context_3d {
            Picture3DContext::In { root_data: Some(ref mut list), .. } => list,
            _ => panic!("Expected to find 3D context root"),
        };
        ordered.clear();

        // Process the accumulated split planes and order them for rendering.
        // Z axis is directed at the screen, `sort` is ascending, and we need back-to-front order.
        for poly in splitter.sort(vec3(0.0, 0.0, 1.0)) {
            let spatial_node_index = self.prim_list.prim_instances[poly.anchor].spatial_node_index;

            let transform = frame_state.transforms.get_world_inv_transform(spatial_node_index);
            let transform_id = frame_state.transforms.get_id(
                spatial_node_index,
                ROOT_SPATIAL_NODE_INDEX,
                clip_scroll_tree,
            );

            let local_points = [
                transform.transform_point3d(&poly.points[0].cast()).unwrap(),
                transform.transform_point3d(&poly.points[1].cast()).unwrap(),
                transform.transform_point3d(&poly.points[2].cast()).unwrap(),
                transform.transform_point3d(&poly.points[3].cast()).unwrap(),
            ];
            let gpu_blocks = [
                [local_points[0].x, local_points[0].y, local_points[1].x, local_points[1].y].into(),
                [local_points[2].x, local_points[2].y, local_points[3].x, local_points[3].y].into(),
            ];
            let gpu_handle = frame_state.gpu_cache.push_per_frame_blocks(&gpu_blocks);
            let gpu_address = frame_state.gpu_cache.get_address(&gpu_handle);

            ordered.push(OrderedPictureChild {
                anchor: poly.anchor,
                transform_id,
                gpu_address,
            });
        }
    }

    /// Called during initial picture traversal, before we know the
    /// bounding rect of children. It is possible to determine the
    /// surface / raster config now though.
    fn pre_update(
        &mut self,
        clip_chain_id: ClipChainId,
        state: &mut PictureUpdateState,
        frame_context: &FrameBuildingContext,
        clip_store: &ClipStore,
        clip_data_store: &ClipDataStore,
    ) -> Option<PrimitiveList> {
        // Reset raster config in case we early out below.
        self.raster_config = None;

        // Resolve animation properties, and early out if the filter
        // properties make this picture invisible.
        if !self.resolve_scene_properties(frame_context.scene_properties) {
            return None;
        }

        // Push information about this pic on stack for children to read.
        state.push_picture(PictureInfo {
            spatial_node_index: self.spatial_node_index,
        });

        // See if this picture actually needs a surface for compositing.
        let actual_composite_mode = match self.requested_composite_mode {
            Some(PictureCompositeMode::Filter(filter)) if filter.is_noop() => None,
            Some(PictureCompositeMode::Blit(reason)) if reason == BlitReason::CLIP => {
                // If the only reason a picture has requested a surface is due to the clip
                // chain node, we might choose to skip drawing a surface, and instead apply
                // the clips to each individual primitive. The logic below works out which
                // option to choose.

                // Assume that we will apply clips to individual items
                let mut apply_clip_to_picture = false;
                let mut current_clip_chain_id = clip_chain_id;

                // Walk each clip in this chain, to see whether to allocate a surface and clip
                // that, or whether to apply clips to each primitive.
                while current_clip_chain_id != ClipChainId::NONE {
                    let clip_chain_node = &clip_store.clip_chain_nodes[current_clip_chain_id.0 as usize];
                    let clip_node = &clip_data_store[clip_chain_node.handle];

                    match clip_node.item {
                        ClipItem::Rectangle(_, ClipMode::Clip) => {
                            // Normal rectangle clips can be handled as per-item clips.
                            // TODO(gw): In future, we might want to consider selecting
                            //           a surface in some situations here (e.g. if the
                            //           stacking context is in a different coord system
                            //           from the clip, and there are enough primitives
                            //           in the stacking context to justify a surface).
                        }
                        ClipItem::Rectangle(_, ClipMode::ClipOut) |
                        ClipItem::RoundedRectangle(..) |
                        ClipItem::Image { .. } |
                        ClipItem::BoxShadow(..) => {
                            // Any of these clip types will require a surface.
                            apply_clip_to_picture = true;
                            break;
                        }
                    }

                    current_clip_chain_id = clip_chain_node.parent_clip_chain_id;
                }

                // If we decided not to use a surfce for clipping, then skip and draw straight
                // into the parent surface.
                if apply_clip_to_picture {
                    Some(PictureCompositeMode::Blit(reason))
                } else {
                    None
                }
            }
            mode => mode,
        };

        if let Some(composite_mode) = actual_composite_mode {
            // Retrieve the positioning node information for the parent surface.
            let parent_raster_node_index = state.current_surface().raster_spatial_node_index;
            let surface_spatial_node_index = self.spatial_node_index;

            // This inflation factor is to be applied to all primitives within the surface.
            let inflation_factor = match composite_mode {
                PictureCompositeMode::Filter(FilterOp::Blur(blur_radius)) => {
                    // Only inflate if the caller hasn't already inflated
                    // the bounding rects for this filter.
                    if self.options.inflate_if_required {
                        // The amount of extra space needed for primitives inside
                        // this picture to ensure the visibility check is correct.
                        BLUR_SAMPLE_SCALE * blur_radius
                    } else {
                        0.0
                    }
                }
                _ => {
                    0.0
                }
            };

            // Check if there is perspective, and thus whether a new
            // rasterization root should be established.
            let establishes_raster_root = frame_context.clip_scroll_tree
                .get_relative_transform(parent_raster_node_index, surface_spatial_node_index)
                .expect("BUG: unable to get relative transform")
                .has_perspective_component();

            let surface = SurfaceInfo::new(
                surface_spatial_node_index,
                if establishes_raster_root {
                    surface_spatial_node_index
                } else {
                    parent_raster_node_index
                },
                inflation_factor,
                frame_context.screen_world_rect,
                &frame_context.clip_scroll_tree,
            );

            self.raster_config = Some(RasterConfig {
                composite_mode,
                establishes_raster_root,
                surface_index: state.push_surface(surface),
            });
        }

        Some(mem::replace(&mut self.prim_list, PrimitiveList::empty()))
    }

    /// Called after updating child pictures during the initial
    /// picture traversal.
    fn post_update(
        &mut self,
        prim_list: PrimitiveList,
        state: &mut PictureUpdateState,
        frame_context: &FrameBuildingContext,
        gpu_cache: &mut GpuCache,
    ) {
        // Restore the pictures list used during recursion.
        self.prim_list = prim_list;

        // Pop the state information about this picture.
        state.pop_picture();

        for cluster in &mut self.prim_list.clusters {
            // Skip the cluster if backface culled.
            if !cluster.is_backface_visible {
                let containing_block_index = match self.context_3d {
                    Picture3DContext::Out => {
                        state.current_picture().map_or(ROOT_SPATIAL_NODE_INDEX, |info| {
                            info.spatial_node_index
                        })
                    }
                    Picture3DContext::In { root_data: Some(_), ancestor_index } => {
                        ancestor_index
                    }
                    Picture3DContext::In { root_data: None, ancestor_index } => {
                        ancestor_index
                    }
                };

                let map_local_to_containing_block: SpaceMapper<LayoutPixel, LayoutPixel> = SpaceMapper::new_with_target(
                    containing_block_index,
                    cluster.spatial_node_index,
                    LayoutRect::zero(), // bounds aren't going to be used for this mapping
                    &frame_context.clip_scroll_tree,
                );

                match map_local_to_containing_block.visible_face() {
                    VisibleFace::Back => continue,
                    VisibleFace::Front => {}
                }
            }

            // No point including this cluster if it can't be transformed
            let spatial_node = &frame_context
                .clip_scroll_tree
                .spatial_nodes[cluster.spatial_node_index.0 as usize];
            if !spatial_node.invertible {
                continue;
            }

            // Map the cluster bounding rect into the space of the surface, and
            // include it in the surface bounding rect.
            let surface = state.current_surface_mut();
            surface.map_local_to_surface.set_target_spatial_node(
                cluster.spatial_node_index,
                frame_context.clip_scroll_tree,
            );

            // Mark the cluster visible, since it passed the invertible and
            // backface checks. In future, this will include spatial clustering
            // which will allow the frame building code to skip most of the
            // current per-primitive culling code.
            cluster.is_visible = true;
            if let Some(cluster_rect) = surface.map_local_to_surface.map(&cluster.bounding_rect) {
                surface.rect = surface.rect.union(&cluster_rect);
            }
        }

        // If this picture establishes a surface, then map the surface bounding
        // rect into the parent surface coordinate space, and propagate that up
        // to the parent.
        if let Some(ref mut raster_config) = self.raster_config {
            let mut surface_rect = {
                let surface = state.current_surface_mut();
                // Inflate the local bounding rect if required by the filter effect.
                // This inflaction factor is to be applied to the surface itsefl.
                let inflation_size = match raster_config.composite_mode {
                    PictureCompositeMode::Filter(FilterOp::Blur(_)) => surface.inflation_factor,
                    PictureCompositeMode::Filter(FilterOp::DropShadow(_, blur_radius, _)) =>
                        (blur_radius * BLUR_SAMPLE_SCALE).ceil(),
                    _ => 0.0,
                };
                surface.rect = surface.rect.inflate(inflation_size, inflation_size);
                surface.rect * TypedScale::new(1.0)
            };

            // Pop this surface from the stack
            let surface_index = state.pop_surface();
            debug_assert_eq!(surface_index, raster_config.surface_index);

            // If the local rect changed (due to transforms in child primitives) then
            // invalidate the GPU cache location to re-upload the new local rect
            // and stretch size. Drop shadow filters also depend on the local rect
            // size for the extra GPU cache data handle.
            // TODO(gw): In future, if we support specifying a flag which gets the
            //           stretch size from the segment rect in the shaders, we can
            //           remove this invalidation here completely.
            if self.local_rect != surface_rect {
                gpu_cache.invalidate(&self.gpu_location);
                if let PictureCompositeMode::Filter(FilterOp::DropShadow(..)) = raster_config.composite_mode {
                    gpu_cache.invalidate(&self.extra_gpu_data_handle);
                }
                self.local_rect = surface_rect;
            }

            // Check if any of the surfaces can't be rasterized in local space but want to.
            if raster_config.establishes_raster_root {
                if surface_rect.size.width > MAX_SURFACE_SIZE ||
                    surface_rect.size.height > MAX_SURFACE_SIZE
                {
                    raster_config.establishes_raster_root = false;
                    state.are_raster_roots_assigned = false;
                }
            }

            // Drop shadows draw both a content and shadow rect, so need to expand the local
            // rect of any surfaces to be composited in parent surfaces correctly.
            if let PictureCompositeMode::Filter(FilterOp::DropShadow(offset, ..)) = raster_config.composite_mode {
                let content_rect = surface_rect;
                let shadow_rect = surface_rect.translate(&offset);
                surface_rect = content_rect.union(&shadow_rect);
            }

            // Propagate up to parent surface, now that we know this surface's static rect
            let parent_surface = state.current_surface_mut();
            parent_surface.map_local_to_surface.set_target_spatial_node(
                self.spatial_node_index,
                frame_context.clip_scroll_tree,
            );
            if let Some(parent_surface_rect) = parent_surface
                .map_local_to_surface
                .map(&surface_rect)
            {
                parent_surface.rect = parent_surface.rect.union(&parent_surface_rect);
            }
        }
    }

    pub fn prepare_for_render(
        &mut self,
        pic_index: PictureIndex,
        prim_instance: &PrimitiveInstance,
        clipped_prim_bounding_rect: WorldRect,
        surface_index: SurfaceIndex,
        frame_context: &FrameBuildingContext,
        frame_state: &mut FrameBuildingState,
    ) -> bool {
        let (mut pic_state_for_children, pic_context) = self.take_state_and_context();

        if let Some(ref mut splitter) = pic_state_for_children.plane_splitter {
            self.resolve_split_planes(
                splitter,
                frame_state,
                frame_context.clip_scroll_tree,
            );
        }

        let raster_config = match self.raster_config {
            Some(ref mut raster_config) => raster_config,
            None => {
                return true
            }
        };

        let (raster_spatial_node_index, child_tasks) = {
            let surface_info = &mut frame_state.surfaces[raster_config.surface_index.0];
            (surface_info.raster_spatial_node_index, surface_info.take_render_tasks())
        };
        let surfaces = &mut frame_state.surfaces;

        let (map_raster_to_world, map_pic_to_raster) = create_raster_mappers(
            prim_instance.spatial_node_index,
            raster_spatial_node_index,
            frame_context.screen_world_rect,
            frame_context.clip_scroll_tree,
        );

        let pic_rect = PictureRect::from_untyped(&self.local_rect.to_untyped());

        let (clipped, unclipped) = match get_raster_rects(
            pic_rect,
            &map_pic_to_raster,
            &map_raster_to_world,
            clipped_prim_bounding_rect,
            frame_context.device_pixel_scale,
        ) {
            Some(info) => info,
            None => return false,
        };
        let transform = map_pic_to_raster.get_transform();

        // TODO(gw): Almost all of the Picture types below use extra_gpu_cache_data
        //           to store the same type of data. The exception is the filter
        //           with a ColorMatrix, which stores the color matrix here. It's
        //           probably worth tidying this code up to be a bit more consistent.
        //           Perhaps store the color matrix after the common data, even though
        //           it's not used by that shader.

        let surface = match raster_config.composite_mode {
            PictureCompositeMode::TileCache { .. } => {
                // For a picture surface, just push any child tasks and tile
                // blits up to the parent surface.
                let surface = &mut surfaces[surface_index.0];
                surface.tasks.extend(child_tasks);

                return true;
            }
            PictureCompositeMode::Filter(FilterOp::Blur(blur_radius)) => {
                let blur_std_deviation = blur_radius * frame_context.device_pixel_scale.0;
                let inflation_factor = surfaces[raster_config.surface_index.0].inflation_factor;
                let inflation_factor = (inflation_factor * frame_context.device_pixel_scale.0).ceil() as i32;

                // The clipped field is the part of the picture that is visible
                // on screen. The unclipped field is the screen-space rect of
                // the complete picture, if no screen / clip-chain was applied
                // (this includes the extra space for blur region). To ensure
                // that we draw a large enough part of the picture to get correct
                // blur results, inflate that clipped area by the blur range, and
                // then intersect with the total screen rect, to minimize the
                // allocation size.
                let device_rect = clipped
                    .inflate(inflation_factor, inflation_factor)
                    .intersection(&unclipped.to_i32())
                    .unwrap();

                let uv_rect_kind = calculate_uv_rect_kind(
                    &pic_rect,
                    &transform,
                    &device_rect,
                    frame_context.device_pixel_scale,
                    true,
                );

                let picture_task = RenderTask::new_picture(
                    RenderTaskLocation::Dynamic(None, device_rect.size),
                    unclipped.size,
                    pic_index,
                    device_rect.origin,
                    child_tasks,
                    uv_rect_kind,
                    pic_context.raster_spatial_node_index,
                );

                let picture_task_id = frame_state.render_tasks.add(picture_task);

                let blur_render_task = RenderTask::new_blur(
                    blur_std_deviation,
                    picture_task_id,
                    frame_state.render_tasks,
                    RenderTargetKind::Color,
                    ClearMode::Transparent,
                );

                let render_task_id = frame_state.render_tasks.add(blur_render_task);

                surfaces[surface_index.0].tasks.push(render_task_id);

                PictureSurface::RenderTask(render_task_id)
            }
            PictureCompositeMode::Filter(FilterOp::DropShadow(offset, blur_radius, color)) => {
                let blur_std_deviation = blur_radius * frame_context.device_pixel_scale.0;
                let blur_range = (blur_std_deviation * BLUR_SAMPLE_SCALE).ceil() as i32;

                // The clipped field is the part of the picture that is visible
                // on screen. The unclipped field is the screen-space rect of
                // the complete picture, if no screen / clip-chain was applied
                // (this includes the extra space for blur region). To ensure
                // that we draw a large enough part of the picture to get correct
                // blur results, inflate that clipped area by the blur range, and
                // then intersect with the total screen rect, to minimize the
                // allocation size.
                let device_rect = clipped
                    .inflate(blur_range, blur_range)
                    .intersection(&unclipped.to_i32())
                    .unwrap();

                let uv_rect_kind = calculate_uv_rect_kind(
                    &pic_rect,
                    &transform,
                    &device_rect,
                    frame_context.device_pixel_scale,
                    true,
                );

                let mut picture_task = RenderTask::new_picture(
                    RenderTaskLocation::Dynamic(None, device_rect.size),
                    unclipped.size,
                    pic_index,
                    device_rect.origin,
                    child_tasks,
                    uv_rect_kind,
                    pic_context.raster_spatial_node_index,
                );
                picture_task.mark_for_saving();

                let picture_task_id = frame_state.render_tasks.add(picture_task);

                let blur_render_task = RenderTask::new_blur(
                    blur_std_deviation.round(),
                    picture_task_id,
                    frame_state.render_tasks,
                    RenderTargetKind::Color,
                    ClearMode::Transparent,
                );

                self.secondary_render_task_id = Some(picture_task_id);

                let render_task_id = frame_state.render_tasks.add(blur_render_task);
                surfaces[surface_index.0].tasks.push(render_task_id);

                if let Some(mut request) = frame_state.gpu_cache.request(&mut self.extra_gpu_data_handle) {
                    // TODO(gw): This is very hacky code below! It stores an extra
                    //           brush primitive below for the special case of a
                    //           drop-shadow where we need a different local
                    //           rect for the shadow. To tidy this up in future,
                    //           we could consider abstracting the code in prim_store.rs
                    //           that writes a brush primitive header.

                    // Basic brush primitive header is (see end of prepare_prim_for_render_inner in prim_store.rs)
                    //  [brush specific data]
                    //  [segment_rect, segment data]
                    let shadow_rect = self.local_rect.translate(&offset);

                    // ImageBrush colors
                    request.push(color.premultiplied());
                    request.push(PremultipliedColorF::WHITE);
                    request.push([
                        self.local_rect.size.width,
                        self.local_rect.size.height,
                        0.0,
                        0.0,
                    ]);

                    // segment rect / extra data
                    request.push(shadow_rect);
                    request.push([0.0, 0.0, 0.0, 0.0]);
                }

                PictureSurface::RenderTask(render_task_id)
            }
            PictureCompositeMode::MixBlend(..) => {
                let uv_rect_kind = calculate_uv_rect_kind(
                    &pic_rect,
                    &transform,
                    &clipped,
                    frame_context.device_pixel_scale,
                    true,
                );

                let picture_task = RenderTask::new_picture(
                    RenderTaskLocation::Dynamic(None, clipped.size),
                    unclipped.size,
                    pic_index,
                    clipped.origin,
                    child_tasks,
                    uv_rect_kind,
                    pic_context.raster_spatial_node_index,
                );

                let readback_task_id = frame_state.render_tasks.add(
                    RenderTask::new_readback(clipped)
                );

                self.secondary_render_task_id = Some(readback_task_id);
                surfaces[surface_index.0].tasks.push(readback_task_id);

                let render_task_id = frame_state.render_tasks.add(picture_task);
                surfaces[surface_index.0].tasks.push(render_task_id);
                PictureSurface::RenderTask(render_task_id)
            }
            PictureCompositeMode::Filter(filter) => {
                if let FilterOp::ColorMatrix(m) = filter {
                    if let Some(mut request) = frame_state.gpu_cache.request(&mut self.extra_gpu_data_handle) {
                        for i in 0..5 {
                            request.push([m[i*4], m[i*4+1], m[i*4+2], m[i*4+3]]);
                        }
                    }
                }

                let uv_rect_kind = calculate_uv_rect_kind(
                    &pic_rect,
                    &transform,
                    &clipped,
                    frame_context.device_pixel_scale,
                    true,
                );

                let picture_task = RenderTask::new_picture(
                    RenderTaskLocation::Dynamic(None, clipped.size),
                    unclipped.size,
                    pic_index,
                    clipped.origin,
                    child_tasks,
                    uv_rect_kind,
                    pic_context.raster_spatial_node_index,
                );

                let render_task_id = frame_state.render_tasks.add(picture_task);
                surfaces[surface_index.0].tasks.push(render_task_id);
                PictureSurface::RenderTask(render_task_id)
            }
            PictureCompositeMode::Blit(_) => {
                // The SplitComposite shader used for 3d contexts doesn't snap
                // to pixels, so we shouldn't snap our uv coordinates either.
                let supports_snapping = match self.context_3d {
                    Picture3DContext::In{ .. } => false,
                    _ => true,
                };

                let uv_rect_kind = calculate_uv_rect_kind(
                    &pic_rect,
                    &transform,
                    &clipped,
                    frame_context.device_pixel_scale,
                    supports_snapping,
                );

                let picture_task = RenderTask::new_picture(
                    RenderTaskLocation::Dynamic(None, clipped.size),
                    unclipped.size,
                    pic_index,
                    clipped.origin,
                    child_tasks,
                    uv_rect_kind,
                    pic_context.raster_spatial_node_index,
                );

                let render_task_id = frame_state.render_tasks.add(picture_task);
                surfaces[surface_index.0].tasks.push(render_task_id);
                PictureSurface::RenderTask(render_task_id)
            }
        };

        surfaces[raster_config.surface_index.0].surface = Some(surface);

        true
    }
}

// Calculate a single homogeneous screen-space UV for a picture.
fn calculate_screen_uv(
    local_pos: &PicturePoint,
    transform: &PictureToRasterTransform,
    rendered_rect: &DeviceRect,
    device_pixel_scale: DevicePixelScale,
    supports_snapping: bool,
) -> DeviceHomogeneousVector {
    let raster_pos = transform.transform_point2d_homogeneous(local_pos);

    let mut device_vec = DeviceHomogeneousVector::new(
        raster_pos.x * device_pixel_scale.0,
        raster_pos.y * device_pixel_scale.0,
        0.0,
        raster_pos.w,
    );

    // Apply snapping for axis-aligned scroll nodes, as per prim_shared.glsl.
    if transform.transform_kind() == TransformedRectKind::AxisAligned && supports_snapping {
        device_vec = DeviceHomogeneousVector::new(
            (device_vec.x / device_vec.w + 0.5).floor(),
            (device_vec.y / device_vec.w + 0.5).floor(),
            0.0,
            1.0,
        );
    }

    DeviceHomogeneousVector::new(
        (device_vec.x - rendered_rect.origin.x * device_vec.w) / rendered_rect.size.width,
        (device_vec.y - rendered_rect.origin.y * device_vec.w) / rendered_rect.size.height,
        0.0,
        device_vec.w,
    )
}

// Calculate a UV rect within an image based on the screen space
// vertex positions of a picture.
fn calculate_uv_rect_kind(
    pic_rect: &PictureRect,
    transform: &PictureToRasterTransform,
    rendered_rect: &DeviceIntRect,
    device_pixel_scale: DevicePixelScale,
    supports_snapping: bool,
) -> UvRectKind {
    let rendered_rect = rendered_rect.to_f32();

    let top_left = calculate_screen_uv(
        &pic_rect.origin,
        transform,
        &rendered_rect,
        device_pixel_scale,
        supports_snapping,
    );

    let top_right = calculate_screen_uv(
        &pic_rect.top_right(),
        transform,
        &rendered_rect,
        device_pixel_scale,
        supports_snapping,
    );

    let bottom_left = calculate_screen_uv(
        &pic_rect.bottom_left(),
        transform,
        &rendered_rect,
        device_pixel_scale,
        supports_snapping,
    );

    let bottom_right = calculate_screen_uv(
        &pic_rect.bottom_right(),
        transform,
        &rendered_rect,
        device_pixel_scale,
        supports_snapping,
    );

    UvRectKind::Quad {
        top_left,
        top_right,
        bottom_left,
        bottom_right,
    }
}

fn create_raster_mappers(
    surface_spatial_node_index: SpatialNodeIndex,
    raster_spatial_node_index: SpatialNodeIndex,
    world_rect: WorldRect,
    clip_scroll_tree: &ClipScrollTree,
) -> (SpaceMapper<RasterPixel, WorldPixel>, SpaceMapper<PicturePixel, RasterPixel>) {
    let map_raster_to_world = SpaceMapper::new_with_target(
        ROOT_SPATIAL_NODE_INDEX,
        raster_spatial_node_index,
        world_rect,
        clip_scroll_tree,
    );

    let raster_bounds = map_raster_to_world.unmap(&world_rect)
                                           .unwrap_or(RasterRect::max_rect());

    let map_pic_to_raster = SpaceMapper::new_with_target(
        raster_spatial_node_index,
        surface_spatial_node_index,
        raster_bounds,
        clip_scroll_tree,
    );

    (map_raster_to_world, map_pic_to_raster)
}

// Convert a list of reference primitives into a map of prim uid -> world position.
fn build_ref_prims(
    ref_prims: &[ReferencePrimitive],
    prim_map: &mut FastHashMap<ItemUid, WorldPoint>,
    clip_scroll_tree: &ClipScrollTree,
) {
    prim_map.clear();

    let mut map_local_to_world = SpaceMapper::new(
        ROOT_SPATIAL_NODE_INDEX,
        WorldRect::zero(),
    );

    for ref_prim in ref_prims {
        map_local_to_world.set_target_spatial_node(
            ref_prim.spatial_node_index,
            clip_scroll_tree,
        );

        // We only care about the origin.
        // TODO(gw): Consider adding a map_point to SpaceMapper.
        let rect = LayoutRect::new(
            ref_prim.local_pos,
            LayoutSize::zero(),
        );

        if let Some(rect) = map_local_to_world.map(&rect) {
            prim_map.insert(ref_prim.uid, rect.origin);
        }
    }
}

// Attempt to correlate the offset between two display lists by
// comparing the offsets between a small number of primitives in
// each display list.
// TODO(gw): This is basically a horrible hack - there must be a better
//           way to achieve this!
fn correlate_prim_maps(
    old_prims: &FastHashMap<ItemUid, WorldPoint>,
    new_prims: &FastHashMap<ItemUid, WorldPoint>,
) -> Option<WorldVector2D> {
    let mut map: FastHashMap<VectorKey, usize> = FastHashMap::default();

    // Find primitives with the same uid, find the difference
    // between them and store the frequency of this offset
    // in a hash map.
    for (uid, old_point) in old_prims {
        if let Some(new_point) = new_prims.get(uid) {
            let key = (*new_point - *old_point).round().into();

            let key_count = map.entry(key).or_insert(0);
            *key_count += 1;
        }
    }

    // Calculate the mode (the most common frequency of offset). This
    // can be different for some primitives, if they've animated, or
    // are attached to a different scroll node etc.
    map.into_iter()
        .max_by_key(|&(_, count)| count)
        .and_then(|(offset, count)| {
            // We will assume we can use the calculated offset if we
            // found more than one quarter of the selected reference
            // primitives to have the same offset.
            let prims_available = new_prims.len().min(old_prims.len());
            if count >= prims_available / 4 {
                Some(offset.into())
            } else {
                None
            }
        })
}