webrender/
clip.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
4
5//! Internal representation of clips in WebRender.
6//!
7//! # Data structures
8//!
9//! There are a number of data structures involved in the clip module:
10//!
11//! - ClipStore - Main interface used by other modules.
12//!
13//! - ClipItem - A single clip item (e.g. a rounded rect, or a box shadow).
14//!              These are an exposed API type, stored inline in a ClipNode.
15//!
16//! - ClipNode - A ClipItem with an attached GPU handle. The GPU handle is populated
17//!              when a ClipNodeInstance is built from this node (which happens while
18//!              preparing primitives for render).
19//!
20//! ClipNodeInstance - A ClipNode with attached positioning information (a spatial
21//!                    node index). This is stored as a contiguous array of nodes
22//!                    within the ClipStore.
23//!
24//! ```ascii
25//! +-----------------------+-----------------------+-----------------------+
26//! | ClipNodeInstance      | ClipNodeInstance      | ClipNodeInstance      |
27//! +-----------------------+-----------------------+-----------------------+
28//! | ClipItem              | ClipItem              | ClipItem              |
29//! | Spatial Node Index    | Spatial Node Index    | Spatial Node Index    |
30//! | GPU cache handle      | GPU cache handle      | GPU cache handle      |
31//! | ...                   | ...                   | ...                   |
32//! +-----------------------+-----------------------+-----------------------+
33//!            0                        1                       2
34//!    +----------------+    |                                              |
35//!    | ClipNodeRange  |____|                                              |
36//!    |    index: 1    |                                                   |
37//!    |    count: 2    |___________________________________________________|
38//!    +----------------+
39//! ```
40//!
41//! - ClipNodeRange - A clip item range identifies a range of clip nodes instances.
42//!                   It is stored as an (index, count).
43//!
44//! - ClipChainNode - A clip chain node contains a handle to an interned clip item,
45//!                   positioning information (from where the clip was defined), and
46//!                   an optional parent link to another ClipChainNode. ClipChainId
47//!                   is an index into an array, or ClipChainId::NONE for no parent.
48//!
49//! ```ascii
50//! +----------------+    ____+----------------+    ____+----------------+   /---> ClipChainId::NONE
51//! | ClipChainNode  |   |    | ClipChainNode  |   |    | ClipChainNode  |   |
52//! +----------------+   |    +----------------+   |    +----------------+   |
53//! | ClipDataHandle |   |    | ClipDataHandle |   |    | ClipDataHandle |   |
54//! | Spatial index  |   |    | Spatial index  |   |    | Spatial index  |   |
55//! | Parent Id      |___|    | Parent Id      |___|    | Parent Id      |___|
56//! | ...            |        | ...            |        | ...            |
57//! +----------------+        +----------------+        +----------------+
58//! ```
59//!
60//! - ClipChainInstance - A ClipChain that has been built for a specific primitive + positioning node.
61//!
62//!    When given a clip chain ID, and a local primitive rect and its spatial node, the clip module
63//!    creates a clip chain instance. This is a struct with various pieces of useful information
64//!    (such as a local clip rect). It also contains a (index, count)
65//!    range specifier into an index buffer of the ClipNodeInstance structures that are actually relevant
66//!    for this clip chain instance. The index buffer structure allows a single array to be used for
67//!    all of the clip-chain instances built in a single frame. Each entry in the index buffer
68//!    also stores some flags relevant to the clip node in this positioning context.
69//!
70//! ```ascii
71//! +----------------------+
72//! | ClipChainInstance    |
73//! +----------------------+
74//! | ...                  |
75//! | local_clip_rect      |________________________________________________________________________
76//! | clips_range          |_______________                                                        |
77//! +----------------------+              |                                                        |
78//!                                       |                                                        |
79//! +------------------+------------------+------------------+------------------+------------------+
80//! | ClipNodeInstance | ClipNodeInstance | ClipNodeInstance | ClipNodeInstance | ClipNodeInstance |
81//! +------------------+------------------+------------------+------------------+------------------+
82//! | flags            | flags            | flags            | flags            | flags            |
83//! | ...              | ...              | ...              | ...              | ...              |
84//! +------------------+------------------+------------------+------------------+------------------+
85//! ```
86//!
87//! # Rendering clipped primitives
88//!
89//! See the [`segment` module documentation][segment.rs].
90//!
91//!
92//! [segment.rs]: ../segment/index.html
93//!
94
95use api::{BorderRadius, ClipMode, ImageMask, ClipId, ClipChainId};
96use api::{BoxShadowClipMode, FillRule, ImageKey, ImageRendering};
97use api::units::*;
98use crate::image_tiling::{self, Repetition};
99use crate::border::{ensure_no_corner_overlap, BorderRadiusAu};
100use crate::box_shadow::{BLUR_SAMPLE_SCALE, BoxShadowClipSource, BoxShadowCacheKey};
101use crate::spatial_tree::{SpatialTree, SpatialNodeIndex};
102use crate::ellipse::Ellipse;
103use crate::gpu_cache::GpuCache;
104use crate::gpu_types::{BoxShadowStretchMode};
105use crate::intern;
106use crate::internal_types::{FastHashMap, FastHashSet, LayoutPrimitiveInfo};
107use crate::prim_store::{VisibleMaskImageTile};
108use crate::prim_store::{PointKey, SizeKey, RectangleKey, PolygonKey};
109use crate::render_task_cache::to_cache_size;
110use crate::render_task::RenderTask;
111use crate::render_task_graph::RenderTaskGraphBuilder;
112use crate::resource_cache::{ImageRequest, ResourceCache};
113use crate::scene_builder_thread::Interners;
114use crate::space::SpaceMapper;
115use crate::util::{clamp_to_scale_factor, extract_inner_rect_safe, project_rect, MatrixHelpers, MaxRect, ScaleOffset};
116use euclid::approxeq::ApproxEq;
117use std::{iter, ops, u32, mem};
118
119/// A (non-leaf) node inside a clip-tree
120#[cfg_attr(feature = "capture", derive(Serialize))]
121#[cfg_attr(feature = "replay", derive(Deserialize))]
122#[derive(MallocSizeOf)]
123pub struct ClipTreeNode {
124    pub handle: ClipDataHandle,
125    pub parent: ClipNodeId,
126
127    children: Vec<ClipNodeId>,
128
129    // TODO(gw): Consider adding a default leaf for cases when the local_clip_rect is not relevant,
130    //           that can be shared among primitives (to reduce amount of clip-chain building).
131}
132
133/// A leaf node in a clip-tree. Any primitive that is clipped will have a handle to
134/// a clip-tree leaf.
135#[cfg_attr(feature = "capture", derive(Serialize))]
136#[cfg_attr(feature = "replay", derive(Deserialize))]
137#[derive(MallocSizeOf)]
138pub struct ClipTreeLeaf {
139    pub node_id: ClipNodeId,
140
141    // TODO(gw): For now, this preserves the ability to build a culling rect
142    //           from the supplied leaf local clip rect on the primitive. In
143    //           future, we'll expand this to be more efficient by combining
144    //           it will compatible clip rects from the `node_id`.
145    pub local_clip_rect: LayoutRect,
146}
147
148/// ID for a ClipTreeNode
149#[derive(Debug, Copy, Clone, PartialEq, MallocSizeOf, Eq, Hash)]
150#[cfg_attr(feature = "capture", derive(Serialize))]
151#[cfg_attr(feature = "replay", derive(Deserialize))]
152pub struct ClipNodeId(u32);
153
154impl ClipNodeId {
155    pub const NONE: ClipNodeId = ClipNodeId(0);
156}
157
158/// ID for a ClipTreeLeaf
159#[derive(Debug, Copy, Clone, PartialEq, MallocSizeOf, Eq, Hash)]
160#[cfg_attr(feature = "capture", derive(Serialize))]
161#[cfg_attr(feature = "replay", derive(Deserialize))]
162pub struct ClipLeafId(u32);
163
164/// A clip-tree built during scene building and used during frame-building to apply clips to primitives.
165#[cfg_attr(feature = "capture", derive(Serialize))]
166#[cfg_attr(feature = "replay", derive(Deserialize))]
167pub struct ClipTree {
168    nodes: Vec<ClipTreeNode>,
169    leaves: Vec<ClipTreeLeaf>,
170    clip_root_stack: Vec<ClipNodeId>,
171}
172
173impl ClipTree {
174    pub fn new() -> Self {
175        ClipTree {
176            nodes: vec![
177                ClipTreeNode {
178                    handle: ClipDataHandle::INVALID,
179                    children: Vec::new(),
180                    parent: ClipNodeId::NONE,
181                }
182            ],
183            leaves: Vec::new(),
184            clip_root_stack: vec![
185                ClipNodeId::NONE,
186            ],
187        }
188    }
189
190    pub fn reset(&mut self) {
191        self.nodes.clear();
192        self.nodes.push(ClipTreeNode {
193            handle: ClipDataHandle::INVALID,
194            children: Vec::new(),
195            parent: ClipNodeId::NONE,
196        });
197
198        self.leaves.clear();
199
200        self.clip_root_stack.clear();
201        self.clip_root_stack.push(ClipNodeId::NONE);
202    }
203
204    /// Add a set of clips to the provided tree node id, reusing existing
205    /// nodes in the tree where possible
206    fn add_impl(
207        id: ClipNodeId,
208        clips: &[ClipDataHandle],
209        nodes: &mut Vec<ClipTreeNode>,
210    ) -> ClipNodeId {
211        if clips.is_empty() {
212            return id;
213        }
214
215        let handle = clips[0];
216        let next_clips = &clips[1..];
217
218        let node_index = nodes[id.0 as usize]
219            .children
220            .iter()
221            .find(|n| nodes[n.0 as usize].handle == handle)
222            .cloned();
223
224        let node_index = match node_index {
225            Some(node_index) => node_index,
226            None => {
227                let node_index = ClipNodeId(nodes.len() as u32);
228                nodes[id.0 as usize].children.push(node_index);
229                let node = ClipTreeNode {
230                    handle,
231                    children: Vec::new(),
232                    parent: id,
233                };
234                nodes.push(node);
235                node_index
236            }
237        };
238
239        ClipTree::add_impl(
240            node_index,
241            next_clips,
242            nodes,
243        )
244    }
245
246    /// Add a set of clips to the provided tree node id, reusing existing
247    /// nodes in the tree where possible
248    pub fn add(
249        &mut self,
250        root: ClipNodeId,
251        clips: &[ClipDataHandle],
252    ) -> ClipNodeId {
253        ClipTree::add_impl(
254            root,
255            clips,
256            &mut self.nodes,
257        )
258    }
259
260    /// Get the current clip root (the node in the clip-tree where clips can be
261    /// ignored when building the clip-chain instance for a primitive)
262    pub fn current_clip_root(&self) -> ClipNodeId {
263        self.clip_root_stack.last().cloned().unwrap()
264    }
265
266    /// Push a clip root (e.g. when a surface is encountered) that prevents clips
267    /// from this node and above being applied to primitives within the root.
268    pub fn push_clip_root_leaf(&mut self, clip_leaf_id: ClipLeafId) {
269        let leaf = &self.leaves[clip_leaf_id.0 as usize];
270        self.clip_root_stack.push(leaf.node_id);
271    }
272
273    /// Push a clip root (e.g. when a surface is encountered) that prevents clips
274    /// from this node and above being applied to primitives within the root.
275    pub fn push_clip_root_node(&mut self, clip_node_id: ClipNodeId) {
276        self.clip_root_stack.push(clip_node_id);
277    }
278
279    /// Pop a clip root, when exiting a surface.
280    pub fn pop_clip_root(&mut self) {
281        self.clip_root_stack.pop().unwrap();
282    }
283
284    /// Retrieve a clip tree node by id
285    pub fn get_node(&self, id: ClipNodeId) -> &ClipTreeNode {
286        assert!(id != ClipNodeId::NONE);
287
288        &self.nodes[id.0 as usize]
289    }
290
291    pub fn get_parent(&self, id: ClipNodeId) -> Option<ClipNodeId> {
292        // Invalid ids point to the first item in the nodes vector which
293        // has an invalid id for the parent so we don't need to handle
294        // `id` being invalid separately.
295        let parent = self.nodes[id.0 as usize].parent;
296        if parent == ClipNodeId::NONE {
297            return None;
298        }
299
300        return Some(parent)
301    }
302
303    /// Retrieve a clip tree leaf by id
304    pub fn get_leaf(&self, id: ClipLeafId) -> &ClipTreeLeaf {
305        &self.leaves[id.0 as usize]
306    }
307
308    /// Debug print the clip-tree
309    #[allow(unused)]
310    pub fn print(&self) {
311        use crate::print_tree::PrintTree;
312
313        fn print_node<T: crate::print_tree::PrintTreePrinter>(
314            id: ClipNodeId,
315            nodes: &[ClipTreeNode],
316            pt: &mut T,
317        ) {
318            let node = &nodes[id.0 as usize];
319
320            pt.new_level(format!("{:?}", id));
321            pt.add_item(format!("{:?}", node.handle));
322
323            for child_id in &node.children {
324                print_node(*child_id, nodes, pt);
325            }
326
327            pt.end_level();
328        }
329
330        fn print_leaf<T: crate::print_tree::PrintTreePrinter>(
331            id: ClipLeafId,
332            leaves: &[ClipTreeLeaf],
333            pt: &mut T,
334        ) {
335            let leaf = &leaves[id.0 as usize];
336
337            pt.new_level(format!("{:?}", id));
338            pt.add_item(format!("node_id: {:?}", leaf.node_id));
339            pt.add_item(format!("local_clip_rect: {:?}", leaf.local_clip_rect));
340            pt.end_level();
341        }
342
343        let mut pt = PrintTree::new("clip tree");
344        print_node(ClipNodeId::NONE, &self.nodes, &mut pt);
345
346        for i in 0 .. self.leaves.len() {
347            print_leaf(ClipLeafId(i as u32), &self.leaves, &mut pt);
348        }
349    }
350
351    /// Find the lowest common ancestor of two clip tree nodes. This is useful
352    /// to identify shared clips between primitives attached to different clip-leaves.
353    pub fn find_lowest_common_ancestor(
354        &self,
355        mut node1: ClipNodeId,
356        mut node2: ClipNodeId,
357    ) -> ClipNodeId {
358        // TODO(gw): Consider caching / storing the depth in the node?
359        fn get_node_depth(
360            id: ClipNodeId,
361            nodes: &[ClipTreeNode],
362        ) -> usize {
363            let mut depth = 0;
364            let mut current = id;
365
366            while current != ClipNodeId::NONE {
367                let node = &nodes[current.0 as usize];
368                depth += 1;
369                current = node.parent;
370            }
371
372            depth
373        }
374
375        let mut depth1 = get_node_depth(node1, &self.nodes);
376        let mut depth2 = get_node_depth(node2, &self.nodes);
377
378        while depth1 > depth2 {
379            node1 = self.nodes[node1.0 as usize].parent;
380            depth1 -= 1;
381        }
382
383        while depth2 > depth1 {
384            node2 = self.nodes[node2.0 as usize].parent;
385            depth2 -= 1;
386        }
387
388        while node1 != node2 {
389            node1 = self.nodes[node1.0 as usize].parent;
390            node2 = self.nodes[node2.0 as usize].parent;
391        }
392
393        node1
394    }
395}
396
397/// Represents a clip-chain as defined by the public API that we decompose in to
398/// the clip-tree. In future, we would like to remove this and have Gecko directly
399/// build the clip-tree.
400#[cfg_attr(feature = "capture", derive(Serialize))]
401#[cfg_attr(feature = "replay", derive(Deserialize))]
402pub struct ClipChain {
403    parent: Option<usize>,
404    clips: Vec<ClipDataHandle>,
405}
406
407#[cfg_attr(feature = "capture", derive(Serialize))]
408#[cfg_attr(feature = "replay", derive(Deserialize))]
409pub struct ClipStackEntry {
410    /// Cache the previous clip-chain build, since this is a common case
411    last_clip_chain_cache: Option<(ClipChainId, ClipNodeId)>,
412
413    /// Set of clips that were already seen and included in clip_node_id
414    seen_clips: FastHashSet<ClipDataHandle>,
415
416    /// The build clip_node_id for this level of the stack
417    clip_node_id: ClipNodeId,
418}
419
420/// Used by the scene builder to build the clip-tree that is part of the built scene.
421#[cfg_attr(feature = "capture", derive(Serialize))]
422#[cfg_attr(feature = "replay", derive(Deserialize))]
423pub struct ClipTreeBuilder {
424    /// Clips defined by the display list
425    clip_map: FastHashMap<ClipId, ClipDataHandle>,
426
427    /// Clip-chains defined by the display list
428    clip_chains: Vec<ClipChain>,
429    clip_chain_map: FastHashMap<ClipChainId, usize>,
430
431    /// List of clips pushed/popped by grouping items, such as stacking contexts and iframes
432    clip_stack: Vec<ClipStackEntry>,
433
434    /// The tree we are building
435    tree: ClipTree,
436
437    /// A temporary buffer stored here to avoid constant heap allocs/frees
438    clip_handles_buffer: Vec<ClipDataHandle>,
439}
440
441impl ClipTreeBuilder {
442    pub fn new() -> Self {
443        ClipTreeBuilder {
444            clip_map: FastHashMap::default(),
445            clip_chain_map: FastHashMap::default(),
446            clip_chains: Vec::new(),
447            clip_stack: vec![
448                ClipStackEntry {
449                    clip_node_id: ClipNodeId::NONE,
450                    last_clip_chain_cache: None,
451                    seen_clips: FastHashSet::default(),
452                },
453            ],
454            tree: ClipTree::new(),
455            clip_handles_buffer: Vec::new(),
456        }
457    }
458
459    pub fn begin(&mut self) {
460        self.clip_map.clear();
461        self.clip_chain_map.clear();
462        self.clip_chains.clear();
463        self.clip_stack.clear();
464        self.clip_stack.push(ClipStackEntry {
465            clip_node_id: ClipNodeId::NONE,
466            last_clip_chain_cache: None,
467            seen_clips: FastHashSet::default(),
468        });
469        self.tree.reset();
470        self.clip_handles_buffer.clear();
471    }
472
473    pub fn recycle_tree(&mut self, tree: ClipTree) {
474        self.tree = tree;
475    }
476
477    /// Define a new rect clip
478    pub fn define_rect_clip(
479        &mut self,
480        id: ClipId,
481        handle: ClipDataHandle,
482    ) {
483        self.clip_map.insert(id, handle);
484    }
485
486    /// Define a new rounded rect clip
487    pub fn define_rounded_rect_clip(
488        &mut self,
489        id: ClipId,
490        handle: ClipDataHandle,
491    ) {
492        self.clip_map.insert(id, handle);
493    }
494
495    /// Define a image mask clip
496    pub fn define_image_mask_clip(
497        &mut self,
498        id: ClipId,
499        handle: ClipDataHandle,
500    ) {
501        self.clip_map.insert(id, handle);
502    }
503
504    /// Define a clip-chain
505    pub fn define_clip_chain<I: Iterator<Item = ClipId>>(
506        &mut self,
507        id: ClipChainId,
508        parent: Option<ClipChainId>,
509        clips: I,
510    ) {
511        let parent = parent.map(|ref id| self.clip_chain_map[id]);
512        let index = self.clip_chains.len();
513        let clips = clips.map(|clip_id| {
514            self.clip_map[&clip_id]
515        }).collect();
516        self.clip_chains.push(ClipChain {
517            parent,
518            clips,
519        });
520        self.clip_chain_map.insert(id, index);
521    }
522
523    /// Push a clip-chain that will be applied to any prims built prior to next pop
524    pub fn push_clip_chain(
525        &mut self,
526        clip_chain_id: Option<ClipChainId>,
527        reset_seen: bool,
528    ) {
529        let (mut clip_node_id, mut seen_clips) = {
530            let prev = self.clip_stack.last().unwrap();
531            (prev.clip_node_id, prev.seen_clips.clone())
532        };
533
534        if let Some(clip_chain_id) = clip_chain_id {
535            if clip_chain_id != ClipChainId::INVALID {
536                self.clip_handles_buffer.clear();
537
538                let clip_chain_index = self.clip_chain_map[&clip_chain_id];
539                ClipTreeBuilder::add_clips(
540                    clip_chain_index,
541                    &mut seen_clips,
542                    &mut self.clip_handles_buffer,
543                    &self.clip_chains,
544                );
545
546                clip_node_id = self.tree.add(
547                    clip_node_id,
548                    &self.clip_handles_buffer,
549                );
550            }
551        }
552
553        if reset_seen {
554            seen_clips.clear();
555        }
556
557        self.clip_stack.push(ClipStackEntry {
558            last_clip_chain_cache: None,
559            clip_node_id,
560            seen_clips,
561        });
562    }
563
564    /// Push a clip-id that will be applied to any prims built prior to next pop
565    pub fn push_clip_id(
566        &mut self,
567        clip_id: ClipId,
568    ) {
569        let (clip_node_id, mut seen_clips) = {
570            let prev = self.clip_stack.last().unwrap();
571            (prev.clip_node_id, prev.seen_clips.clone())
572        };
573
574        self.clip_handles_buffer.clear();
575        let clip_index = self.clip_map[&clip_id];
576
577        if seen_clips.insert(clip_index) {
578            self.clip_handles_buffer.push(clip_index);
579        }
580
581        let clip_node_id = self.tree.add(
582            clip_node_id,
583            &self.clip_handles_buffer,
584        );
585
586        self.clip_stack.push(ClipStackEntry {
587            last_clip_chain_cache: None,
588            seen_clips,
589            clip_node_id,
590        });
591    }
592
593    /// Pop a clip off the clip_stack, when exiting a grouping item
594    pub fn pop_clip(&mut self) {
595        self.clip_stack.pop().unwrap();
596    }
597
598    /// Add clips from a given clip-chain to the set of clips for a primitive during clip-set building
599    fn add_clips(
600        clip_chain_index: usize,
601        seen_clips: &mut FastHashSet<ClipDataHandle>,
602        output: &mut Vec<ClipDataHandle>,
603        clip_chains: &[ClipChain],
604    ) {
605        // TODO(gw): It's possible that we may see clip outputs that include identical clips
606        //           (e.g. if there is a clip positioned by two spatial nodes, where one spatial
607        //           node is a child of the other, and has an identity transform). If we ever
608        //           see this in real-world cases, it might be worth checking for that here and
609        //           excluding them, to ensure the shape of the tree matches what we need for
610        //           finding shared_clips for tile caches etc.
611
612        let clip_chain = &clip_chains[clip_chain_index];
613
614        if let Some(parent) = clip_chain.parent {
615            ClipTreeBuilder::add_clips(
616                parent,
617                seen_clips,
618                output,
619                clip_chains,
620            );
621        }
622
623        for clip_index in clip_chain.clips.iter().rev() {
624            if seen_clips.insert(*clip_index) {
625                output.push(*clip_index);
626            }
627        }
628    }
629
630    /// Main entry point to build a path in the clip-tree for a given primitive
631    pub fn build_clip_set(
632        &mut self,
633        clip_chain_id: ClipChainId,
634    ) -> ClipNodeId {
635        let clip_stack = self.clip_stack.last_mut().unwrap();
636
637        if clip_chain_id == ClipChainId::INVALID {
638            clip_stack.clip_node_id
639        } else {
640            if let Some((cached_clip_chain, cached_clip_node)) = clip_stack.last_clip_chain_cache {
641                if cached_clip_chain == clip_chain_id {
642                    return cached_clip_node;
643                }
644            }
645
646            let clip_chain_index = self.clip_chain_map[&clip_chain_id];
647
648            self.clip_handles_buffer.clear();
649
650            ClipTreeBuilder::add_clips(
651                clip_chain_index,
652                &mut clip_stack.seen_clips,
653                &mut self.clip_handles_buffer,
654                &self.clip_chains,
655            );
656
657            // We mutated the `clip_stack.seen_clips` in order to remove duplicate clips from
658            // the supplied `clip_chain_id`. Now step through and remove any clips we added
659            // to the set, so we don't get incorrect results next time `build_clip_set` is
660            // called for a different clip-chain. Doing it this way rather than cloning means
661            // we avoid heap allocations for each `build_clip_set` call.
662            for handle in &self.clip_handles_buffer {
663                clip_stack.seen_clips.remove(handle);
664            }
665
666            let clip_node_id = self.tree.add(
667                clip_stack.clip_node_id,
668                &self.clip_handles_buffer,
669            );
670
671            clip_stack.last_clip_chain_cache = Some((clip_chain_id, clip_node_id));
672
673            clip_node_id
674        }
675    }
676
677    /// Recursive impl to check if a clip-chain has complex (non-rectangular) clips
678    fn has_complex_clips_impl(
679        &self,
680        clip_chain_index: usize,
681        interners: &Interners,
682    ) -> bool {
683        let clip_chain = &self.clip_chains[clip_chain_index];
684
685        for clip_handle in &clip_chain.clips {
686            let clip_info = &interners.clip[*clip_handle];
687
688            if let ClipNodeKind::Complex = clip_info.key.kind.node_kind() {
689                return true;
690            }
691        }
692
693        match clip_chain.parent {
694            Some(parent) => self.has_complex_clips_impl(parent, interners),
695            None => false,
696        }
697    }
698
699    /// Check if a clip-chain has complex (non-rectangular) clips
700    pub fn clip_chain_has_complex_clips(
701        &self,
702        clip_chain_id: ClipChainId,
703        interners: &Interners,
704    ) -> bool {
705        let clip_chain_index = self.clip_chain_map[&clip_chain_id];
706        self.has_complex_clips_impl(clip_chain_index, interners)
707    }
708
709    /// Check if a clip-node has complex (non-rectangular) clips
710    pub fn clip_node_has_complex_clips(
711        &self,
712        clip_node_id: ClipNodeId,
713        interners: &Interners,
714    ) -> bool {
715        let mut current = clip_node_id;
716
717        while current != ClipNodeId::NONE {
718            let node = &self.tree.nodes[current.0 as usize];
719            let clip_info = &interners.clip[node.handle];
720
721            if let ClipNodeKind::Complex = clip_info.key.kind.node_kind() {
722                return true;
723            }
724
725            current = node.parent;
726        }
727
728        false
729    }
730
731    pub fn get_parent(&self, id: ClipNodeId) -> Option<ClipNodeId> {
732        self.tree.get_parent(id)
733    }
734
735    /// Finalize building and return the clip-tree
736    pub fn finalize(&mut self) -> ClipTree {
737        // Note: After this, the builder's clip tree does not hold allocations and
738        // is not in valid state. `ClipTreeBuilder::begin()` must be called before
739        // building can happen again.
740        std::mem::replace(&mut self.tree, ClipTree {
741            nodes: Vec::new(),
742            leaves: Vec::new(),
743            clip_root_stack: Vec::new(),
744        })
745    }
746
747    /// Get a clip node by id
748    pub fn get_node(&self, id: ClipNodeId) -> &ClipTreeNode {
749        assert!(id != ClipNodeId::NONE);
750
751        &self.tree.nodes[id.0 as usize]
752    }
753
754    /// Get a clip leaf by id
755    pub fn get_leaf(&self, id: ClipLeafId) -> &ClipTreeLeaf {
756        &self.tree.leaves[id.0 as usize]
757    }
758
759    /// Build a clip-leaf for a tile-cache
760    pub fn build_for_tile_cache(
761        &mut self,
762        clip_node_id: ClipNodeId,
763        extra_clips: &[ClipId],
764    ) -> ClipLeafId {
765        self.clip_handles_buffer.clear();
766
767        for clip_id in extra_clips {
768            let handle = self.clip_map[clip_id];
769            self.clip_handles_buffer.push(handle);
770        }
771
772        let node_id = self.tree.add(
773            clip_node_id,
774            &self.clip_handles_buffer,
775        );
776
777        let clip_leaf_id = ClipLeafId(self.tree.leaves.len() as u32);
778
779        self.tree.leaves.push(ClipTreeLeaf {
780            node_id,
781            local_clip_rect: LayoutRect::max_rect(),
782        });
783
784        clip_leaf_id
785    }
786
787    /// Build a clip-leaf for a picture
788    pub fn build_for_picture(
789        &mut self,
790        clip_node_id: ClipNodeId,
791    ) -> ClipLeafId {
792        let node_id = self.tree.add(
793            clip_node_id,
794            &[],
795        );
796
797        let clip_leaf_id = ClipLeafId(self.tree.leaves.len() as u32);
798
799        self.tree.leaves.push(ClipTreeLeaf {
800            node_id,
801            local_clip_rect: LayoutRect::max_rect(),
802        });
803
804        clip_leaf_id
805    }
806
807    /// Build a clip-leaf for a normal primitive
808    pub fn build_for_prim(
809        &mut self,
810        clip_node_id: ClipNodeId,
811        info: &LayoutPrimitiveInfo,
812        extra_clips: &[ClipItemKey],
813        interners: &mut Interners,
814    ) -> ClipLeafId {
815
816        let node_id = if extra_clips.is_empty() {
817            clip_node_id
818        } else {
819            // TODO(gw): Cache the previous build of clip-node / clip-leaf to handle cases where we get a
820            //           lot of primitives referencing the same clip set (e.g. dl_mutate and similar tests)
821            self.clip_handles_buffer.clear();
822
823            for item in extra_clips {
824                // Intern this clip item, and store the handle
825                // in the clip chain node.
826                let handle = interners.clip.intern(item, || {
827                    ClipInternData {
828                        key: item.clone(),
829                    }
830                });
831
832                self.clip_handles_buffer.push(handle);
833            }
834
835            self.tree.add(
836                clip_node_id,
837                &self.clip_handles_buffer,
838            )
839        };
840
841        let clip_leaf_id = ClipLeafId(self.tree.leaves.len() as u32);
842
843        self.tree.leaves.push(ClipTreeLeaf {
844            node_id,
845            local_clip_rect: info.clip_rect,
846        });
847
848        clip_leaf_id
849    }
850
851    // Find the LCA for two given clip nodes
852    pub fn find_lowest_common_ancestor(
853        &self,
854        node1: ClipNodeId,
855        node2: ClipNodeId,
856    ) -> ClipNodeId {
857        self.tree.find_lowest_common_ancestor(node1, node2)
858    }
859}
860
861// Type definitions for interning clip nodes.
862
863#[derive(Copy, Clone, Debug, MallocSizeOf, PartialEq, Eq, Hash)]
864#[cfg_attr(any(feature = "serde"), derive(Deserialize, Serialize))]
865pub enum ClipIntern {}
866
867pub type ClipDataStore = intern::DataStore<ClipIntern>;
868pub type ClipDataHandle = intern::Handle<ClipIntern>;
869
870/// Helper to identify simple clips (normal rects) from other kinds of clips,
871/// which can often be handled via fast code paths.
872#[cfg_attr(feature = "capture", derive(Serialize))]
873#[cfg_attr(feature = "replay", derive(Deserialize))]
874#[derive(Debug, Copy, Clone, MallocSizeOf)]
875pub enum ClipNodeKind {
876    /// A normal clip rectangle, with Clip mode.
877    Rectangle,
878    /// A rectangle with ClipOut, or any other kind of clip.
879    Complex,
880}
881
882// Result of comparing a clip node instance against a local rect.
883#[derive(Debug)]
884enum ClipResult {
885    // The clip does not affect the region at all.
886    Accept,
887    // The clip prevents the region from being drawn.
888    Reject,
889    // The clip affects part of the region. This may
890    // require a clip mask, depending on other factors.
891    Partial,
892}
893
894// A clip node is a single clip source, along with some
895// positioning information and implementation details
896// that control where the GPU data for this clip source
897// can be found.
898#[derive(Debug)]
899#[cfg_attr(feature = "capture", derive(Serialize))]
900#[cfg_attr(feature = "replay", derive(Deserialize))]
901#[derive(MallocSizeOf)]
902pub struct ClipNode {
903    pub item: ClipItem,
904}
905
906// Convert from an interning key for a clip item
907// to a clip node, which is cached in the document.
908impl From<ClipItemKey> for ClipNode {
909    fn from(item: ClipItemKey) -> Self {
910        let kind = match item.kind {
911            ClipItemKeyKind::Rectangle(rect, mode) => {
912                ClipItemKind::Rectangle { rect: rect.into(), mode }
913            }
914            ClipItemKeyKind::RoundedRectangle(rect, radius, mode) => {
915                ClipItemKind::RoundedRectangle {
916                    rect: rect.into(),
917                    radius: radius.into(),
918                    mode,
919                }
920            }
921            ClipItemKeyKind::ImageMask(rect, image, polygon_handle) => {
922                ClipItemKind::Image {
923                    image,
924                    rect: rect.into(),
925                    polygon_handle,
926                }
927            }
928            ClipItemKeyKind::BoxShadow(shadow_rect_fract_offset, shadow_rect_size, shadow_radius, prim_shadow_rect, blur_radius, clip_mode) => {
929                ClipItemKind::new_box_shadow(
930                    shadow_rect_fract_offset.into(),
931                    shadow_rect_size.into(),
932                    shadow_radius.into(),
933                    prim_shadow_rect.into(),
934                    blur_radius.to_f32_px(),
935                    clip_mode,
936                )
937            }
938        };
939
940        ClipNode {
941            item: ClipItem {
942                kind,
943                spatial_node_index: item.spatial_node_index,
944            },
945        }
946    }
947}
948
949// Flags that are attached to instances of clip nodes.
950#[cfg_attr(feature = "capture", derive(Serialize))]
951#[cfg_attr(feature = "replay", derive(Deserialize))]
952#[derive(Copy, PartialEq, Eq, Clone, PartialOrd, Ord, Hash, MallocSizeOf)]
953pub struct ClipNodeFlags(u8);
954
955bitflags! {
956    impl ClipNodeFlags : u8 {
957        const SAME_SPATIAL_NODE = 0x1;
958        const SAME_COORD_SYSTEM = 0x2;
959        const USE_FAST_PATH = 0x4;
960    }
961}
962
963impl core::fmt::Debug for ClipNodeFlags {
964    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
965        if self.is_empty() {
966            write!(f, "{:#x}", Self::empty().bits())
967        } else {
968            bitflags::parser::to_writer(self, f)
969        }
970    }
971}
972
973// When a clip node is found to be valid for a
974// clip chain instance, it's stored in an index
975// buffer style structure. This struct contains
976// an index to the node data itself, as well as
977// some flags describing how this clip node instance
978// is positioned.
979#[derive(Debug, Clone, MallocSizeOf)]
980#[cfg_attr(feature = "capture", derive(Serialize))]
981#[cfg_attr(feature = "replay", derive(Deserialize))]
982pub struct ClipNodeInstance {
983    pub handle: ClipDataHandle,
984    pub flags: ClipNodeFlags,
985    pub visible_tiles: Option<ops::Range<usize>>,
986}
987
988impl ClipNodeInstance {
989    pub fn has_visible_tiles(&self) -> bool {
990        self.visible_tiles.is_some()
991    }
992}
993
994// A range of clip node instances that were found by
995// building a clip chain instance.
996#[derive(Debug, Copy, Clone)]
997#[cfg_attr(feature = "capture", derive(Serialize))]
998#[cfg_attr(feature = "replay", derive(Deserialize))]
999pub struct ClipNodeRange {
1000    pub first: u32,
1001    pub count: u32,
1002}
1003
1004impl ClipNodeRange {
1005    pub fn to_range(&self) -> ops::Range<usize> {
1006        let start = self.first as usize;
1007        let end = start + self.count as usize;
1008
1009        ops::Range {
1010            start,
1011            end,
1012        }
1013    }
1014}
1015
1016/// A helper struct for converting between coordinate systems
1017/// of clip sources and primitives.
1018// todo(gw): optimize:
1019//  separate arrays for matrices
1020//  cache and only build as needed.
1021//TODO: merge with `CoordinateSpaceMapping`?
1022#[derive(Debug, MallocSizeOf)]
1023#[cfg_attr(feature = "capture", derive(Serialize))]
1024pub enum ClipSpaceConversion {
1025    Local,
1026    ScaleOffset(ScaleOffset),
1027    Transform(LayoutToVisTransform),
1028}
1029
1030impl ClipSpaceConversion {
1031    /// Construct a new clip space converter between two spatial nodes.
1032    pub fn new(
1033        prim_spatial_node_index: SpatialNodeIndex,
1034        clip_spatial_node_index: SpatialNodeIndex,
1035        visibility_spatial_node_index: SpatialNodeIndex,
1036        spatial_tree: &SpatialTree,
1037    ) -> Self {
1038        //Note: this code is different from `get_relative_transform` in a way that we only try
1039        // getting the relative transform if it's Local or ScaleOffset,
1040        // falling back to the world transform otherwise.
1041        let clip_spatial_node = spatial_tree.get_spatial_node(clip_spatial_node_index);
1042        let prim_spatial_node = spatial_tree.get_spatial_node(prim_spatial_node_index);
1043
1044        if prim_spatial_node_index == clip_spatial_node_index {
1045            ClipSpaceConversion::Local
1046        } else if prim_spatial_node.coordinate_system_id == clip_spatial_node.coordinate_system_id {
1047            let scale_offset = clip_spatial_node.content_transform
1048                .then(&prim_spatial_node.content_transform.inverse());
1049            ClipSpaceConversion::ScaleOffset(scale_offset)
1050        } else {
1051            ClipSpaceConversion::Transform(
1052                spatial_tree.get_relative_transform(
1053                    clip_spatial_node_index,
1054                    visibility_spatial_node_index,
1055                ).into_transform().cast_unit()
1056            )
1057        }
1058    }
1059
1060    fn to_flags(&self) -> ClipNodeFlags {
1061        match *self {
1062            ClipSpaceConversion::Local => {
1063                ClipNodeFlags::SAME_SPATIAL_NODE | ClipNodeFlags::SAME_COORD_SYSTEM
1064            }
1065            ClipSpaceConversion::ScaleOffset(..) => {
1066                ClipNodeFlags::SAME_COORD_SYSTEM
1067            }
1068            ClipSpaceConversion::Transform(..) => {
1069                ClipNodeFlags::empty()
1070            }
1071        }
1072    }
1073}
1074
1075// Temporary information that is cached and reused
1076// during building of a clip chain instance.
1077#[derive(MallocSizeOf)]
1078#[cfg_attr(feature = "capture", derive(Serialize))]
1079struct ClipNodeInfo {
1080    conversion: ClipSpaceConversion,
1081    handle: ClipDataHandle,
1082}
1083
1084impl ClipNodeInfo {
1085    fn create_instance(
1086        &self,
1087        node: &ClipNode,
1088        clipped_rect: &LayoutRect,
1089        gpu_cache: &mut GpuCache,
1090        resource_cache: &mut ResourceCache,
1091        mask_tiles: &mut Vec<VisibleMaskImageTile>,
1092        spatial_tree: &SpatialTree,
1093        rg_builder: &mut RenderTaskGraphBuilder,
1094        request_resources: bool,
1095    ) -> Option<ClipNodeInstance> {
1096        // Calculate some flags that are required for the segment
1097        // building logic.
1098        let mut flags = self.conversion.to_flags();
1099
1100        // Some clip shaders support a fast path mode for simple clips.
1101        // TODO(gw): We could also apply fast path when segments are created, since we only write
1102        //           the mask for a single corner at a time then, so can always consider radii uniform.
1103        let is_raster_2d =
1104            flags.contains(ClipNodeFlags::SAME_COORD_SYSTEM) ||
1105            spatial_tree
1106                .get_world_viewport_transform(node.item.spatial_node_index)
1107                .is_2d_axis_aligned();
1108        if is_raster_2d && node.item.kind.supports_fast_path_rendering() {
1109            flags |= ClipNodeFlags::USE_FAST_PATH;
1110        }
1111
1112        let mut visible_tiles = None;
1113
1114        if let ClipItemKind::Image { rect, image, .. } = node.item.kind {
1115            let request = ImageRequest {
1116                key: image,
1117                rendering: ImageRendering::Auto,
1118                tile: None,
1119            };
1120
1121            if let Some(props) = resource_cache.get_image_properties(image) {
1122                if let Some(tile_size) = props.tiling {
1123                    let tile_range_start = mask_tiles.len();
1124
1125                    // Bug 1648323 - It is unclear why on rare occasions we get
1126                    // a clipped_rect that does not intersect the clip's mask rect.
1127                    // defaulting to clipped_rect here results in zero repetitions
1128                    // which clips the primitive entirely.
1129                    let visible_rect =
1130                        clipped_rect.intersection(&rect).unwrap_or(*clipped_rect);
1131
1132                    let repetitions = image_tiling::repetitions(
1133                        &rect,
1134                        &visible_rect,
1135                        rect.size(),
1136                    );
1137
1138                    for Repetition { origin, .. } in repetitions {
1139                        let layout_image_rect = LayoutRect::from_origin_and_size(
1140                            origin,
1141                            rect.size(),
1142                        );
1143                        let tiles = image_tiling::tiles(
1144                            &layout_image_rect,
1145                            &visible_rect,
1146                            &props.visible_rect,
1147                            tile_size as i32,
1148                        );
1149                        for tile in tiles {
1150                            let req = request.with_tile(tile.offset);
1151
1152                            if request_resources {
1153                                resource_cache.request_image(
1154                                    req,
1155                                    gpu_cache,
1156                                );
1157                            }
1158
1159                            let task_id = rg_builder.add().init(
1160                                RenderTask::new_image(props.descriptor.size, req)
1161                            );
1162
1163                            mask_tiles.push(VisibleMaskImageTile {
1164                                tile_offset: tile.offset,
1165                                tile_rect: tile.rect,
1166                                task_id,
1167                            });
1168                        }
1169                    }
1170                    visible_tiles = Some(tile_range_start..mask_tiles.len());
1171                } else {
1172                    if request_resources {
1173                        resource_cache.request_image(request, gpu_cache);
1174                    }
1175
1176                    let tile_range_start = mask_tiles.len();
1177
1178                    let task_id = rg_builder.add().init(
1179                        RenderTask::new_image(props.descriptor.size, request)
1180                    );
1181
1182                    mask_tiles.push(VisibleMaskImageTile {
1183                        tile_rect: rect,
1184                        tile_offset: TileOffset::zero(),
1185                        task_id,
1186                    });
1187
1188                    visible_tiles = Some(tile_range_start .. mask_tiles.len());
1189                }
1190            } else {
1191                // If the supplied image key doesn't exist in the resource cache,
1192                // skip the clip node since there is nothing to mask with.
1193                warn!("Clip mask with missing image key {:?}", request.key);
1194                return None;
1195            }
1196        }
1197
1198        Some(ClipNodeInstance {
1199            handle: self.handle,
1200            flags,
1201            visible_tiles,
1202        })
1203    }
1204}
1205
1206impl ClipNode {
1207    pub fn update(
1208        &mut self,
1209        device_pixel_scale: DevicePixelScale,
1210    ) {
1211        match self.item.kind {
1212            ClipItemKind::Image { .. } |
1213            ClipItemKind::Rectangle { .. } |
1214            ClipItemKind::RoundedRectangle { .. } => {}
1215
1216            ClipItemKind::BoxShadow { ref mut source } => {
1217                // Quote from https://drafts.csswg.org/css-backgrounds-3/#shadow-blur
1218                // "the image that would be generated by applying to the shadow a
1219                // Gaussian blur with a standard deviation equal to half the blur radius."
1220                let blur_radius_dp = source.blur_radius * 0.5;
1221
1222                // Create scaling from requested size to cache size.
1223                let mut content_scale = LayoutToWorldScale::new(1.0) * device_pixel_scale;
1224                content_scale.0 = clamp_to_scale_factor(content_scale.0, false);
1225
1226                // Create the cache key for this box-shadow render task.
1227                let cache_size = to_cache_size(source.shadow_rect_alloc_size, &mut content_scale);
1228
1229                let bs_cache_key = BoxShadowCacheKey {
1230                    blur_radius_dp: (blur_radius_dp * content_scale.0).round() as i32,
1231                    clip_mode: source.clip_mode,
1232                    original_alloc_size: (source.original_alloc_size * content_scale).round().to_i32(),
1233                    br_top_left: (source.shadow_radius.top_left * content_scale).round().to_i32(),
1234                    br_top_right: (source.shadow_radius.top_right * content_scale).round().to_i32(),
1235                    br_bottom_right: (source.shadow_radius.bottom_right * content_scale).round().to_i32(),
1236                    br_bottom_left: (source.shadow_radius.bottom_left * content_scale).round().to_i32(),
1237                    device_pixel_scale: Au::from_f32_px(content_scale.0),
1238                };
1239
1240                source.cache_key = Some((cache_size, bs_cache_key));
1241            }
1242        }
1243    }
1244}
1245
1246#[derive(Default)]
1247pub struct ClipStoreScratchBuffer {
1248    clip_node_instances: Vec<ClipNodeInstance>,
1249    mask_tiles: Vec<VisibleMaskImageTile>,
1250}
1251
1252/// The main clipping public interface that other modules access.
1253#[derive(MallocSizeOf)]
1254#[cfg_attr(feature = "capture", derive(Serialize))]
1255pub struct ClipStore {
1256    pub clip_node_instances: Vec<ClipNodeInstance>,
1257    mask_tiles: Vec<VisibleMaskImageTile>,
1258
1259    active_clip_node_info: Vec<ClipNodeInfo>,
1260    active_local_clip_rect: Option<LayoutRect>,
1261    active_pic_coverage_rect: PictureRect,
1262}
1263
1264// A clip chain instance is what gets built for a given clip
1265// chain id + local primitive region + positioning node.
1266#[derive(Debug)]
1267#[cfg_attr(feature = "capture", derive(Serialize))]
1268pub struct ClipChainInstance {
1269    pub clips_range: ClipNodeRange,
1270    // Combined clip rect for clips that are in the
1271    // same coordinate system as the primitive.
1272    pub local_clip_rect: LayoutRect,
1273    pub has_non_local_clips: bool,
1274    // If true, this clip chain requires allocation
1275    // of a clip mask.
1276    pub needs_mask: bool,
1277    // Combined clip rect in picture space (may
1278    // be more conservative that local_clip_rect).
1279    pub pic_coverage_rect: PictureRect,
1280    // Space, in which the `pic_coverage_rect` is defined.
1281    pub pic_spatial_node_index: SpatialNodeIndex,
1282}
1283
1284impl ClipChainInstance {
1285    pub fn empty() -> Self {
1286        ClipChainInstance {
1287            clips_range: ClipNodeRange {
1288                first: 0,
1289                count: 0,
1290            },
1291            local_clip_rect: LayoutRect::zero(),
1292            has_non_local_clips: false,
1293            needs_mask: false,
1294            pic_coverage_rect: PictureRect::zero(),
1295            pic_spatial_node_index: SpatialNodeIndex::INVALID,
1296        }
1297    }
1298}
1299
1300impl ClipStore {
1301    pub fn new() -> Self {
1302        ClipStore {
1303            clip_node_instances: Vec::new(),
1304            mask_tiles: Vec::new(),
1305            active_clip_node_info: Vec::new(),
1306            active_local_clip_rect: None,
1307            active_pic_coverage_rect: PictureRect::max_rect(),
1308        }
1309    }
1310
1311    pub fn reset(&mut self) {
1312        self.clip_node_instances.clear();
1313        self.mask_tiles.clear();
1314        self.active_clip_node_info.clear();
1315        self.active_local_clip_rect = None;
1316        self.active_pic_coverage_rect = PictureRect::max_rect();
1317    }
1318
1319    pub fn get_instance_from_range(
1320        &self,
1321        node_range: &ClipNodeRange,
1322        index: u32,
1323    ) -> &ClipNodeInstance {
1324        &self.clip_node_instances[(node_range.first + index) as usize]
1325    }
1326
1327    /// Setup the active clip chains for building a clip chain instance.
1328    pub fn set_active_clips(
1329        &mut self,
1330        prim_spatial_node_index: SpatialNodeIndex,
1331        pic_spatial_node_index: SpatialNodeIndex,
1332        visibility_spatial_node_index: SpatialNodeIndex,
1333        clip_leaf_id: ClipLeafId,
1334        spatial_tree: &SpatialTree,
1335        clip_data_store: &ClipDataStore,
1336        clip_tree: &ClipTree,
1337    ) {
1338        self.active_clip_node_info.clear();
1339        self.active_local_clip_rect = None;
1340        self.active_pic_coverage_rect = PictureRect::max_rect();
1341
1342        let clip_root = clip_tree.current_clip_root();
1343        let clip_leaf = clip_tree.get_leaf(clip_leaf_id);
1344
1345        let mut local_clip_rect = clip_leaf.local_clip_rect;
1346        let mut current = clip_leaf.node_id;
1347
1348        while current != clip_root {
1349            let node = clip_tree.get_node(current);
1350
1351            if !add_clip_node_to_current_chain(
1352                node.handle,
1353                prim_spatial_node_index,
1354                pic_spatial_node_index,
1355                visibility_spatial_node_index,
1356                &mut local_clip_rect,
1357                &mut self.active_clip_node_info,
1358                &mut self.active_pic_coverage_rect,
1359                clip_data_store,
1360                spatial_tree,
1361            ) {
1362                return;
1363            }
1364
1365            current = node.parent;
1366        }
1367
1368        self.active_local_clip_rect = Some(local_clip_rect);
1369    }
1370
1371    /// Setup the active clip chains, based on an existing primitive clip chain instance.
1372    pub fn set_active_clips_from_clip_chain(
1373        &mut self,
1374        prim_clip_chain: &ClipChainInstance,
1375        prim_spatial_node_index: SpatialNodeIndex,
1376        visibility_spatial_node_index: SpatialNodeIndex,
1377        spatial_tree: &SpatialTree,
1378        clip_data_store: &ClipDataStore,
1379    ) {
1380        // TODO(gw): Although this does less work than set_active_clips(), it does
1381        //           still do some unnecessary work (such as the clip space conversion).
1382        //           We could consider optimizing this if it ever shows up in a profile.
1383
1384        self.active_clip_node_info.clear();
1385        self.active_local_clip_rect = Some(prim_clip_chain.local_clip_rect);
1386        self.active_pic_coverage_rect = prim_clip_chain.pic_coverage_rect;
1387
1388        let clip_instances = &self
1389            .clip_node_instances[prim_clip_chain.clips_range.to_range()];
1390        for clip_instance in clip_instances {
1391            let clip = &clip_data_store[clip_instance.handle];
1392            let conversion = ClipSpaceConversion::new(
1393                prim_spatial_node_index,
1394                clip.item.spatial_node_index,
1395                visibility_spatial_node_index,
1396                spatial_tree,
1397            );
1398            self.active_clip_node_info.push(ClipNodeInfo {
1399                handle: clip_instance.handle,
1400                conversion,
1401            });
1402        }
1403    }
1404
1405    /// Given a clip-chain instance, return a safe rect within the visible region
1406    /// that can be assumed to be unaffected by clip radii. Returns None if it
1407    /// encounters any complex cases, just handling rounded rects in the same
1408    /// coordinate system as the clip-chain for now.
1409    pub fn get_inner_rect_for_clip_chain(
1410        &self,
1411        clip_chain: &ClipChainInstance,
1412        clip_data_store: &ClipDataStore,
1413        spatial_tree: &SpatialTree,
1414    ) -> Option<PictureRect> {
1415        let mut inner_rect = clip_chain.pic_coverage_rect;
1416        let clip_instances = &self
1417            .clip_node_instances[clip_chain.clips_range.to_range()];
1418
1419        for clip_instance in clip_instances {
1420            // Don't handle mapping between coord systems for now
1421            if !clip_instance.flags.contains(ClipNodeFlags::SAME_COORD_SYSTEM) {
1422                return None;
1423            }
1424
1425            let clip_node = &clip_data_store[clip_instance.handle];
1426
1427            match clip_node.item.kind {
1428                // Ignore any clips which are complex or impossible to calculate
1429                // inner rects for now
1430                ClipItemKind::Rectangle { mode: ClipMode::ClipOut, .. } |
1431                ClipItemKind::Image { .. } |
1432                ClipItemKind::BoxShadow { .. } |
1433                ClipItemKind::RoundedRectangle { mode: ClipMode::ClipOut, .. } => {
1434                    return None;
1435                }
1436                // Normal Clip rects are already handled by the clip-chain pic_coverage_rect,
1437                // no need to do anything here
1438                ClipItemKind::Rectangle { mode: ClipMode::Clip, .. } => {}
1439                ClipItemKind::RoundedRectangle { mode: ClipMode::Clip, rect, radius } => {
1440                    // Get an inner rect for the rounded-rect clip
1441                    let local_inner_rect = match extract_inner_rect_safe(&rect, &radius) {
1442                        Some(rect) => rect,
1443                        None => return None,
1444                    };
1445
1446                    // Map it from local -> picture space
1447                    let mapper = SpaceMapper::new_with_target(
1448                        clip_chain.pic_spatial_node_index,
1449                        clip_node.item.spatial_node_index,
1450                        PictureRect::max_rect(),
1451                        spatial_tree,
1452                    );
1453
1454                    // Accumulate in to the inner_rect, in case there are multiple rounded-rect clips
1455                    if let Some(pic_inner_rect) = mapper.map(&local_inner_rect) {
1456                        inner_rect = inner_rect.intersection(&pic_inner_rect).unwrap_or(PictureRect::zero());
1457                    }
1458                }
1459            }
1460        }
1461
1462        Some(inner_rect)
1463    }
1464
1465    // Directly construct a clip node range, ready for rendering, from an interned clip handle.
1466    // Typically useful for drawing specific clips on custom pattern / child render tasks that
1467    // aren't primitives.
1468    // TODO(gw): For now, we assume they are local clips only - in future we might want to support
1469    //           non-local clips.
1470    pub fn push_clip_instance(
1471        &mut self,
1472        handle: ClipDataHandle,
1473    ) -> ClipNodeRange {
1474        let first = self.clip_node_instances.len() as u32;
1475
1476        self.clip_node_instances.push(ClipNodeInstance {
1477            handle,
1478            flags: ClipNodeFlags::SAME_COORD_SYSTEM | ClipNodeFlags::SAME_SPATIAL_NODE,
1479            visible_tiles: None,
1480        });
1481
1482        ClipNodeRange {
1483            first,
1484            count: 1,
1485        }
1486    }
1487
1488    /// The main interface external code uses. Given a local primitive, positioning
1489    /// information, and a clip chain id, build an optimized clip chain instance.
1490    pub fn build_clip_chain_instance(
1491        &mut self,
1492        local_prim_rect: LayoutRect,
1493        prim_to_pic_mapper: &SpaceMapper<LayoutPixel, PicturePixel>,
1494        pic_to_vis_mapper: &SpaceMapper<PicturePixel, VisPixel>,
1495        spatial_tree: &SpatialTree,
1496        gpu_cache: &mut GpuCache,
1497        resource_cache: &mut ResourceCache,
1498        device_pixel_scale: DevicePixelScale,
1499        culling_rect: &VisRect,
1500        clip_data_store: &mut ClipDataStore,
1501        rg_builder: &mut RenderTaskGraphBuilder,
1502        request_resources: bool,
1503    ) -> Option<ClipChainInstance> {
1504        let local_clip_rect = match self.active_local_clip_rect {
1505            Some(rect) => rect,
1506            None => return None,
1507        };
1508        profile_scope!("build_clip_chain_instance");
1509
1510        let local_bounding_rect = local_prim_rect.intersection(&local_clip_rect)?;
1511        let mut pic_coverage_rect = prim_to_pic_mapper.map(&local_bounding_rect)?;
1512        let vis_clip_rect = pic_to_vis_mapper.map(&pic_coverage_rect)?;
1513
1514        // Now, we've collected all the clip nodes that *potentially* affect this
1515        // primitive region, and reduced the size of the prim region as much as possible.
1516
1517        // Run through the clip nodes, and see which ones affect this prim region.
1518
1519        let first_clip_node_index = self.clip_node_instances.len() as u32;
1520        let mut has_non_local_clips = false;
1521        let mut needs_mask = false;
1522
1523        // For each potential clip node
1524        for node_info in self.active_clip_node_info.drain(..) {
1525            let node = &mut clip_data_store[node_info.handle];
1526
1527            // See how this clip affects the prim region.
1528            let clip_result = match node_info.conversion {
1529                ClipSpaceConversion::Local => {
1530                    node.item.kind.get_clip_result(&local_bounding_rect)
1531                }
1532                ClipSpaceConversion::ScaleOffset(ref scale_offset) => {
1533                    has_non_local_clips = true;
1534                    node.item.kind.get_clip_result(&scale_offset.unmap_rect(&local_bounding_rect))
1535                }
1536                ClipSpaceConversion::Transform(ref transform) => {
1537                    has_non_local_clips = true;
1538                    node.item.kind.get_clip_result_complex(
1539                        transform,
1540                        &vis_clip_rect,
1541                        culling_rect,
1542                    )
1543                }
1544            };
1545
1546            match clip_result {
1547                ClipResult::Accept => {
1548                    // Doesn't affect the primitive at all, so skip adding to list
1549                }
1550                ClipResult::Reject => {
1551                    // Completely clips the supplied prim rect
1552                    return None;
1553                }
1554                ClipResult::Partial => {
1555                    // Needs a mask -> add to clip node indices
1556
1557                    // TODO(gw): Ensure this only runs once on each node per frame?
1558                    node.update(device_pixel_scale);
1559
1560                    // Create the clip node instance for this clip node
1561                    if let Some(instance) = node_info.create_instance(
1562                        node,
1563                        &local_bounding_rect,
1564                        gpu_cache,
1565                        resource_cache,
1566                        &mut self.mask_tiles,
1567                        spatial_tree,
1568                        rg_builder,
1569                        request_resources,
1570                    ) {
1571                        // As a special case, a partial accept of a clip rect that is
1572                        // in the same coordinate system as the primitive doesn't need
1573                        // a clip mask. Instead, it can be handled by the primitive
1574                        // vertex shader as part of the local clip rect. This is an
1575                        // important optimization for reducing the number of clip
1576                        // masks that are allocated on common pages.
1577                        needs_mask |= match node.item.kind {
1578                            ClipItemKind::Rectangle { mode: ClipMode::ClipOut, .. } |
1579                            ClipItemKind::RoundedRectangle { .. } |
1580                            ClipItemKind::Image { .. } |
1581                            ClipItemKind::BoxShadow { .. } => {
1582                                true
1583                            }
1584
1585                            ClipItemKind::Rectangle { mode: ClipMode::Clip, .. } => {
1586                                !instance.flags.contains(ClipNodeFlags::SAME_COORD_SYSTEM)
1587                            }
1588                        };
1589
1590                        // Store this in the index buffer for this clip chain instance.
1591                        self.clip_node_instances.push(instance);
1592                    }
1593                }
1594            }
1595        }
1596
1597        // Get the range identifying the clip nodes in the index buffer.
1598        let clips_range = ClipNodeRange {
1599            first: first_clip_node_index,
1600            count: self.clip_node_instances.len() as u32 - first_clip_node_index,
1601        };
1602
1603        // If this clip chain needs a mask, reduce the size of the mask allocation
1604        // by any clips that were in the same space as the picture. This can result
1605        // in much smaller clip mask allocations in some cases. Note that the ordering
1606        // here is important - the reduction must occur *after* the clip item accept
1607        // reject checks above, so that we don't eliminate masks accidentally (since
1608        // we currently only support a local clip rect in the vertex shader).
1609        if needs_mask {
1610            pic_coverage_rect = pic_coverage_rect.intersection(&self.active_pic_coverage_rect)?;
1611        }
1612
1613        // Return a valid clip chain instance
1614        Some(ClipChainInstance {
1615            clips_range,
1616            has_non_local_clips,
1617            local_clip_rect,
1618            pic_coverage_rect,
1619            pic_spatial_node_index: prim_to_pic_mapper.ref_spatial_node_index,
1620            needs_mask,
1621        })
1622    }
1623
1624    pub fn begin_frame(&mut self, scratch: &mut ClipStoreScratchBuffer) {
1625        mem::swap(&mut self.clip_node_instances, &mut scratch.clip_node_instances);
1626        mem::swap(&mut self.mask_tiles, &mut scratch.mask_tiles);
1627        self.clip_node_instances.clear();
1628        self.mask_tiles.clear();
1629    }
1630
1631    pub fn end_frame(&mut self, scratch: &mut ClipStoreScratchBuffer) {
1632        mem::swap(&mut self.clip_node_instances, &mut scratch.clip_node_instances);
1633        mem::swap(&mut self.mask_tiles, &mut scratch.mask_tiles);
1634    }
1635
1636    pub fn visible_mask_tiles(&self, instance: &ClipNodeInstance) -> &[VisibleMaskImageTile] {
1637        if let Some(range) = &instance.visible_tiles {
1638            &self.mask_tiles[range.clone()]
1639        } else {
1640            &[]
1641        }
1642    }
1643}
1644
1645impl Default for ClipStore {
1646    fn default() -> Self {
1647        ClipStore::new()
1648    }
1649}
1650
1651// The ClipItemKey is a hashable representation of the contents
1652// of a clip item. It is used during interning to de-duplicate
1653// clip nodes between frames and display lists. This allows quick
1654// comparison of clip node equality by handle, and also allows
1655// the uploaded GPU cache handle to be retained between display lists.
1656// TODO(gw): Maybe we should consider constructing these directly
1657//           in the DL builder?
1658#[derive(Copy, Debug, Clone, Eq, MallocSizeOf, PartialEq, Hash)]
1659#[cfg_attr(feature = "capture", derive(Serialize))]
1660#[cfg_attr(feature = "replay", derive(Deserialize))]
1661pub enum ClipItemKeyKind {
1662    Rectangle(RectangleKey, ClipMode),
1663    RoundedRectangle(RectangleKey, BorderRadiusAu, ClipMode),
1664    ImageMask(RectangleKey, ImageKey, Option<PolygonDataHandle>),
1665    BoxShadow(PointKey, SizeKey, BorderRadiusAu, RectangleKey, Au, BoxShadowClipMode),
1666}
1667
1668impl ClipItemKeyKind {
1669    pub fn rectangle(rect: LayoutRect, mode: ClipMode) -> Self {
1670        ClipItemKeyKind::Rectangle(rect.into(), mode)
1671    }
1672
1673    pub fn rounded_rect(rect: LayoutRect, mut radii: BorderRadius, mode: ClipMode) -> Self {
1674        if radii.is_zero() {
1675            ClipItemKeyKind::rectangle(rect, mode)
1676        } else {
1677            ensure_no_corner_overlap(&mut radii, rect.size());
1678            ClipItemKeyKind::RoundedRectangle(
1679                rect.into(),
1680                radii.into(),
1681                mode,
1682            )
1683        }
1684    }
1685
1686    pub fn image_mask(image_mask: &ImageMask, mask_rect: LayoutRect,
1687                      polygon_handle: Option<PolygonDataHandle>) -> Self {
1688        ClipItemKeyKind::ImageMask(
1689            mask_rect.into(),
1690            image_mask.image,
1691            polygon_handle,
1692        )
1693    }
1694
1695    pub fn box_shadow(
1696        shadow_rect: LayoutRect,
1697        shadow_radius: BorderRadius,
1698        prim_shadow_rect: LayoutRect,
1699        blur_radius: f32,
1700        clip_mode: BoxShadowClipMode,
1701    ) -> Self {
1702        // Get the fractional offsets required to match the
1703        // source rect with a minimal rect.
1704        let fract_offset = LayoutPoint::new(
1705            shadow_rect.min.x.fract().abs(),
1706            shadow_rect.min.y.fract().abs(),
1707        );
1708
1709        ClipItemKeyKind::BoxShadow(
1710            fract_offset.into(),
1711            shadow_rect.size().into(),
1712            shadow_radius.into(),
1713            prim_shadow_rect.into(),
1714            Au::from_f32_px(blur_radius),
1715            clip_mode,
1716        )
1717    }
1718
1719    pub fn node_kind(&self) -> ClipNodeKind {
1720        match *self {
1721            ClipItemKeyKind::Rectangle(_, ClipMode::Clip) => ClipNodeKind::Rectangle,
1722
1723            ClipItemKeyKind::Rectangle(_, ClipMode::ClipOut) |
1724            ClipItemKeyKind::RoundedRectangle(..) |
1725            ClipItemKeyKind::ImageMask(..) |
1726            ClipItemKeyKind::BoxShadow(..) => ClipNodeKind::Complex,
1727        }
1728    }
1729}
1730
1731#[derive(Debug, Copy, Clone, Eq, MallocSizeOf, PartialEq, Hash)]
1732#[cfg_attr(feature = "capture", derive(Serialize))]
1733#[cfg_attr(feature = "replay", derive(Deserialize))]
1734pub struct ClipItemKey {
1735    pub kind: ClipItemKeyKind,
1736    pub spatial_node_index: SpatialNodeIndex,
1737}
1738
1739/// The data available about an interned clip node during scene building
1740#[derive(Debug, MallocSizeOf)]
1741#[cfg_attr(feature = "capture", derive(Serialize))]
1742#[cfg_attr(feature = "replay", derive(Deserialize))]
1743pub struct ClipInternData {
1744    pub key: ClipItemKey,
1745}
1746
1747impl intern::InternDebug for ClipItemKey {}
1748
1749impl intern::Internable for ClipIntern {
1750    type Key = ClipItemKey;
1751    type StoreData = ClipNode;
1752    type InternData = ClipInternData;
1753    const PROFILE_COUNTER: usize = crate::profiler::INTERNED_CLIPS;
1754}
1755
1756#[derive(Debug, MallocSizeOf)]
1757#[cfg_attr(feature = "capture", derive(Serialize))]
1758#[cfg_attr(feature = "replay", derive(Deserialize))]
1759pub enum ClipItemKind {
1760    Rectangle {
1761        rect: LayoutRect,
1762        mode: ClipMode,
1763    },
1764    RoundedRectangle {
1765        rect: LayoutRect,
1766        radius: BorderRadius,
1767        mode: ClipMode,
1768    },
1769    Image {
1770        image: ImageKey,
1771        rect: LayoutRect,
1772        polygon_handle: Option<PolygonDataHandle>,
1773    },
1774    BoxShadow {
1775        source: BoxShadowClipSource,
1776    },
1777}
1778
1779#[derive(Debug, MallocSizeOf)]
1780#[cfg_attr(feature = "capture", derive(Serialize))]
1781#[cfg_attr(feature = "replay", derive(Deserialize))]
1782pub struct ClipItem {
1783    pub kind: ClipItemKind,
1784    pub spatial_node_index: SpatialNodeIndex,
1785}
1786
1787fn compute_box_shadow_parameters(
1788    shadow_rect_fract_offset: LayoutPoint,
1789    shadow_rect_size: LayoutSize,
1790    mut shadow_radius: BorderRadius,
1791    prim_shadow_rect: LayoutRect,
1792    blur_radius: f32,
1793    clip_mode: BoxShadowClipMode,
1794) -> BoxShadowClipSource {
1795    // Make sure corners don't overlap.
1796    ensure_no_corner_overlap(&mut shadow_radius, shadow_rect_size);
1797
1798    let fract_size = LayoutSize::new(
1799        shadow_rect_size.width.fract().abs(),
1800        shadow_rect_size.height.fract().abs(),
1801    );
1802
1803    // Create a minimal size primitive mask to blur. In this
1804    // case, we ensure the size of each corner is the same,
1805    // to simplify the shader logic that stretches the blurred
1806    // result across the primitive.
1807    let max_corner_width = shadow_radius.top_left.width
1808                                .max(shadow_radius.bottom_left.width)
1809                                .max(shadow_radius.top_right.width)
1810                                .max(shadow_radius.bottom_right.width);
1811    let max_corner_height = shadow_radius.top_left.height
1812                                .max(shadow_radius.bottom_left.height)
1813                                .max(shadow_radius.top_right.height)
1814                                .max(shadow_radius.bottom_right.height);
1815
1816    // Get maximum distance that can be affected by given blur radius.
1817    let blur_region = (BLUR_SAMPLE_SCALE * blur_radius).ceil();
1818
1819    // If the largest corner is smaller than the blur radius, we need to ensure
1820    // that it's big enough that the corners don't affect the middle segments.
1821    let used_corner_width = max_corner_width.max(blur_region);
1822    let used_corner_height = max_corner_height.max(blur_region);
1823
1824    // Minimal nine-patch size, corner + internal + corner.
1825    let min_shadow_rect_size = LayoutSize::new(
1826        2.0 * used_corner_width + blur_region,
1827        2.0 * used_corner_height + blur_region,
1828    );
1829
1830    // The minimal rect to blur.
1831    let mut minimal_shadow_rect = LayoutRect::from_origin_and_size(
1832        LayoutPoint::new(
1833            blur_region + shadow_rect_fract_offset.x,
1834            blur_region + shadow_rect_fract_offset.y,
1835        ),
1836        LayoutSize::new(
1837            min_shadow_rect_size.width + fract_size.width,
1838            min_shadow_rect_size.height + fract_size.height,
1839        ),
1840    );
1841
1842    // If the width or height ends up being bigger than the original
1843    // primitive shadow rect, just blur the entire rect along that
1844    // axis and draw that as a simple blit. This is necessary for
1845    // correctness, since the blur of one corner may affect the blur
1846    // in another corner.
1847    let mut stretch_mode_x = BoxShadowStretchMode::Stretch;
1848    if shadow_rect_size.width < minimal_shadow_rect.width() {
1849        minimal_shadow_rect.max.x = minimal_shadow_rect.min.x + shadow_rect_size.width;
1850        stretch_mode_x = BoxShadowStretchMode::Simple;
1851    }
1852
1853    let mut stretch_mode_y = BoxShadowStretchMode::Stretch;
1854    if shadow_rect_size.height < minimal_shadow_rect.height() {
1855        minimal_shadow_rect.max.y = minimal_shadow_rect.min.y + shadow_rect_size.height;
1856        stretch_mode_y = BoxShadowStretchMode::Simple;
1857    }
1858
1859    // Expand the shadow rect by enough room for the blur to take effect.
1860    let shadow_rect_alloc_size = LayoutSize::new(
1861        2.0 * blur_region + minimal_shadow_rect.width().ceil(),
1862        2.0 * blur_region + minimal_shadow_rect.height().ceil(),
1863    );
1864
1865    BoxShadowClipSource {
1866        original_alloc_size: shadow_rect_alloc_size,
1867        shadow_rect_alloc_size,
1868        shadow_radius,
1869        prim_shadow_rect,
1870        blur_radius,
1871        clip_mode,
1872        stretch_mode_x,
1873        stretch_mode_y,
1874        render_task: None,
1875        cache_key: None,
1876        minimal_shadow_rect,
1877    }
1878}
1879
1880impl ClipItemKind {
1881    pub fn new_box_shadow(
1882        shadow_rect_fract_offset: LayoutPoint,
1883        shadow_rect_size: LayoutSize,
1884        mut shadow_radius: BorderRadius,
1885        prim_shadow_rect: LayoutRect,
1886        blur_radius: f32,
1887        clip_mode: BoxShadowClipMode,
1888    ) -> Self {
1889        let mut source = compute_box_shadow_parameters(
1890            shadow_rect_fract_offset,
1891            shadow_rect_size,
1892            shadow_radius,
1893            prim_shadow_rect,
1894            blur_radius,
1895            clip_mode,
1896        );
1897
1898        fn needed_downscaling(source: &BoxShadowClipSource) -> Option<f32> {
1899            // This size is fairly arbitrary, but it's the same as the size that
1900            // we use to avoid caching big blurred stacking contexts.
1901            //
1902            // If you change it, ensure that the reftests
1903            // box-shadow-large-blur-radius-* still hit the downscaling path,
1904            // and that they render correctly.
1905            const MAX_SIZE: f32 = 2048.;
1906
1907            let max_dimension =
1908                source.shadow_rect_alloc_size.width.max(source.shadow_rect_alloc_size.height);
1909
1910            if max_dimension > MAX_SIZE {
1911                Some(MAX_SIZE / max_dimension)
1912            } else {
1913                None
1914            }
1915        }
1916
1917        if let Some(downscale) = needed_downscaling(&source) {
1918            shadow_radius.bottom_left.height *= downscale;
1919            shadow_radius.bottom_left.width *= downscale;
1920            shadow_radius.bottom_right.height *= downscale;
1921            shadow_radius.bottom_right.width *= downscale;
1922            shadow_radius.top_left.height *= downscale;
1923            shadow_radius.top_left.width *= downscale;
1924            shadow_radius.top_right.height *= downscale;
1925            shadow_radius.top_right.width *= downscale;
1926
1927            let original_alloc_size = source.shadow_rect_alloc_size;
1928
1929            source = compute_box_shadow_parameters(
1930                shadow_rect_fract_offset * downscale,
1931                shadow_rect_size * downscale,
1932                shadow_radius,
1933                prim_shadow_rect,
1934                blur_radius * downscale,
1935                clip_mode,
1936            );
1937            source.original_alloc_size = original_alloc_size;
1938        }
1939        ClipItemKind::BoxShadow { source }
1940    }
1941
1942    /// Returns true if this clip mask can run through the fast path
1943    /// for the given clip item type.
1944    ///
1945    /// Note: this logic has to match `ClipBatcher::add` behavior.
1946    fn supports_fast_path_rendering(&self) -> bool {
1947        match *self {
1948            ClipItemKind::Rectangle { .. } |
1949            ClipItemKind::Image { .. } |
1950            ClipItemKind::BoxShadow { .. } => {
1951                false
1952            }
1953            ClipItemKind::RoundedRectangle { ref rect, ref radius, .. } => {
1954                radius.can_use_fast_path_in(rect)
1955            }
1956        }
1957    }
1958
1959    // Get an optional clip rect that a clip source can provide to
1960    // reduce the size of a primitive region. This is typically
1961    // used to eliminate redundant clips, and reduce the size of
1962    // any clip mask that eventually gets drawn.
1963    pub fn get_local_clip_rect(&self) -> Option<LayoutRect> {
1964        match *self {
1965            ClipItemKind::Rectangle { rect, mode: ClipMode::Clip } => Some(rect),
1966            ClipItemKind::Rectangle { mode: ClipMode::ClipOut, .. } => None,
1967            ClipItemKind::RoundedRectangle { rect, mode: ClipMode::Clip, .. } => Some(rect),
1968            ClipItemKind::RoundedRectangle { mode: ClipMode::ClipOut, .. } => None,
1969            ClipItemKind::Image { rect, .. } => {
1970                Some(rect)
1971            }
1972            ClipItemKind::BoxShadow { .. } => None,
1973        }
1974    }
1975
1976    fn get_clip_result_complex(
1977        &self,
1978        transform: &LayoutToVisTransform,
1979        prim_rect: &VisRect,
1980        culling_rect: &VisRect,
1981    ) -> ClipResult {
1982        let visible_rect = match prim_rect.intersection(culling_rect) {
1983            Some(rect) => rect,
1984            None => return ClipResult::Reject,
1985        };
1986
1987        let (clip_rect, inner_rect, mode) = match *self {
1988            ClipItemKind::Rectangle { rect, mode } => {
1989                (rect, Some(rect), mode)
1990            }
1991            ClipItemKind::RoundedRectangle { rect, ref radius, mode } => {
1992                let inner_clip_rect = extract_inner_rect_safe(&rect, radius);
1993                (rect, inner_clip_rect, mode)
1994            }
1995            ClipItemKind::Image { rect, .. } => {
1996                (rect, None, ClipMode::Clip)
1997            }
1998            ClipItemKind::BoxShadow { .. } => {
1999                return ClipResult::Partial;
2000            }
2001        };
2002
2003        if let Some(ref inner_clip_rect) = inner_rect {
2004            if let Some(()) = projected_rect_contains(inner_clip_rect, transform, &visible_rect) {
2005                return match mode {
2006                    ClipMode::Clip => ClipResult::Accept,
2007                    ClipMode::ClipOut => ClipResult::Reject,
2008                };
2009            }
2010        }
2011
2012        match mode {
2013            ClipMode::Clip => {
2014                let outer_clip_rect = match project_rect(
2015                    transform,
2016                    &clip_rect,
2017                    &culling_rect,
2018                ) {
2019                    Some(outer_clip_rect) => outer_clip_rect,
2020                    None => return ClipResult::Partial,
2021                };
2022
2023                match outer_clip_rect.intersection(prim_rect) {
2024                    Some(..) => {
2025                        ClipResult::Partial
2026                    }
2027                    None => {
2028                        ClipResult::Reject
2029                    }
2030                }
2031            }
2032            ClipMode::ClipOut => ClipResult::Partial,
2033        }
2034    }
2035
2036    // Check how a given clip source affects a local primitive region.
2037    fn get_clip_result(
2038        &self,
2039        prim_rect: &LayoutRect,
2040    ) -> ClipResult {
2041        match *self {
2042            ClipItemKind::Rectangle { rect, mode: ClipMode::Clip } => {
2043                if rect.contains_box(prim_rect) {
2044                    return ClipResult::Accept;
2045                }
2046
2047                match rect.intersection(prim_rect) {
2048                    Some(..) => {
2049                        ClipResult::Partial
2050                    }
2051                    None => {
2052                        ClipResult::Reject
2053                    }
2054                }
2055            }
2056            ClipItemKind::Rectangle { rect, mode: ClipMode::ClipOut } => {
2057                if rect.contains_box(prim_rect) {
2058                    return ClipResult::Reject;
2059                }
2060
2061                match rect.intersection(prim_rect) {
2062                    Some(_) => {
2063                        ClipResult::Partial
2064                    }
2065                    None => {
2066                        ClipResult::Accept
2067                    }
2068                }
2069            }
2070            ClipItemKind::RoundedRectangle { rect, ref radius, mode: ClipMode::Clip } => {
2071                // TODO(gw): Consider caching this in the ClipNode
2072                //           if it ever shows in profiles.
2073                if rounded_rectangle_contains_box_quick(&rect, radius, &prim_rect) {
2074                    return ClipResult::Accept;
2075                }
2076
2077                match rect.intersection(prim_rect) {
2078                    Some(..) => {
2079                        ClipResult::Partial
2080                    }
2081                    None => {
2082                        ClipResult::Reject
2083                    }
2084                }
2085            }
2086            ClipItemKind::RoundedRectangle { rect, ref radius, mode: ClipMode::ClipOut } => {
2087                // TODO(gw): Consider caching this in the ClipNode
2088                //           if it ever shows in profiles.
2089                if rounded_rectangle_contains_box_quick(&rect, radius, &prim_rect) {
2090                    return ClipResult::Reject;
2091                }
2092
2093                match rect.intersection(prim_rect) {
2094                    Some(_) => {
2095                        ClipResult::Partial
2096                    }
2097                    None => {
2098                        ClipResult::Accept
2099                    }
2100                }
2101            }
2102            ClipItemKind::Image { rect, .. } => {
2103                match rect.intersection(prim_rect) {
2104                    Some(..) => {
2105                        ClipResult::Partial
2106                    }
2107                    None => {
2108                        ClipResult::Reject
2109                    }
2110                }
2111            }
2112            ClipItemKind::BoxShadow { .. } => {
2113                ClipResult::Partial
2114            }
2115        }
2116    }
2117}
2118
2119/// Represents a local rect and a device space
2120/// rectangles that are either outside or inside bounds.
2121#[derive(Clone, Debug, PartialEq)]
2122pub struct Geometry {
2123    pub local_rect: LayoutRect,
2124    pub device_rect: DeviceIntRect,
2125}
2126
2127impl From<LayoutRect> for Geometry {
2128    fn from(local_rect: LayoutRect) -> Self {
2129        Geometry {
2130            local_rect,
2131            device_rect: DeviceIntRect::zero(),
2132        }
2133    }
2134}
2135
2136pub fn rounded_rectangle_contains_point(
2137    point: &LayoutPoint,
2138    rect: &LayoutRect,
2139    radii: &BorderRadius
2140) -> bool {
2141    if !rect.contains(*point) {
2142        return false;
2143    }
2144
2145    let top_left_center = rect.min + radii.top_left.to_vector();
2146    if top_left_center.x > point.x && top_left_center.y > point.y &&
2147       !Ellipse::new(radii.top_left).contains(*point - top_left_center.to_vector()) {
2148        return false;
2149    }
2150
2151    let bottom_right_center = rect.bottom_right() - radii.bottom_right.to_vector();
2152    if bottom_right_center.x < point.x && bottom_right_center.y < point.y &&
2153       !Ellipse::new(radii.bottom_right).contains(*point - bottom_right_center.to_vector()) {
2154        return false;
2155    }
2156
2157    let top_right_center = rect.top_right() +
2158                           LayoutVector2D::new(-radii.top_right.width, radii.top_right.height);
2159    if top_right_center.x < point.x && top_right_center.y > point.y &&
2160       !Ellipse::new(radii.top_right).contains(*point - top_right_center.to_vector()) {
2161        return false;
2162    }
2163
2164    let bottom_left_center = rect.bottom_left() +
2165                             LayoutVector2D::new(radii.bottom_left.width, -radii.bottom_left.height);
2166    if bottom_left_center.x > point.x && bottom_left_center.y < point.y &&
2167       !Ellipse::new(radii.bottom_left).contains(*point - bottom_left_center.to_vector()) {
2168        return false;
2169    }
2170
2171    true
2172}
2173
2174/// Return true if the rounded rectangle described by `container` and `radii`
2175/// definitely contains `containee`. May return false negatives, but never false
2176/// positives.
2177fn rounded_rectangle_contains_box_quick(
2178    container: &LayoutRect,
2179    radii: &BorderRadius,
2180    containee: &LayoutRect,
2181) -> bool {
2182    if !container.contains_box(containee) {
2183        return false;
2184    }
2185
2186    /// Return true if `point` falls within `corner`. This only covers the
2187    /// upper-left case; we transform the other corners into that form.
2188    fn foul(point: LayoutPoint, corner: LayoutPoint) -> bool {
2189        point.x < corner.x && point.y < corner.y
2190    }
2191
2192    /// Flip `pt` about the y axis (i.e. negate `x`).
2193    fn flip_x(pt: LayoutPoint) -> LayoutPoint {
2194        LayoutPoint { x: -pt.x, .. pt }
2195    }
2196
2197    /// Flip `pt` about the x axis (i.e. negate `y`).
2198    fn flip_y(pt: LayoutPoint) -> LayoutPoint {
2199        LayoutPoint { y: -pt.y, .. pt }
2200    }
2201
2202    if foul(containee.top_left(), container.top_left() + radii.top_left) ||
2203        foul(flip_x(containee.top_right()), flip_x(container.top_right()) + radii.top_right) ||
2204        foul(flip_y(containee.bottom_left()), flip_y(container.bottom_left()) + radii.bottom_left) ||
2205        foul(-containee.bottom_right(), -container.bottom_right() + radii.bottom_right)
2206    {
2207        return false;
2208    }
2209
2210    true
2211}
2212
2213/// Test where point p is relative to the infinite line that passes through the segment
2214/// defined by p0 and p1. Point p is on the "left" of the line if the triangle (p0, p1, p)
2215/// forms a counter-clockwise triangle.
2216/// > 0 is left of the line
2217/// < 0 is right of the line
2218/// == 0 is on the line
2219pub fn is_left_of_line(
2220    p_x: f32,
2221    p_y: f32,
2222    p0_x: f32,
2223    p0_y: f32,
2224    p1_x: f32,
2225    p1_y: f32,
2226) -> f32 {
2227    (p1_x - p0_x) * (p_y - p0_y) - (p_x - p0_x) * (p1_y - p0_y)
2228}
2229
2230pub fn polygon_contains_point(
2231    point: &LayoutPoint,
2232    rect: &LayoutRect,
2233    polygon: &PolygonKey,
2234) -> bool {
2235    if !rect.contains(*point) {
2236        return false;
2237    }
2238
2239    // p is a LayoutPoint that we'll be comparing to dimensionless PointKeys,
2240    // which were created from LayoutPoints, so it all works out.
2241    let p = LayoutPoint::new(point.x - rect.min.x, point.y - rect.min.y);
2242
2243    // Calculate a winding number for this point.
2244    let mut winding_number: i32 = 0;
2245
2246    let count = polygon.point_count as usize;
2247
2248    for i in 0..count {
2249        let p0 = polygon.points[i];
2250        let p1 = polygon.points[(i + 1) % count];
2251
2252        if p0.y <= p.y {
2253            if p1.y > p.y {
2254                if is_left_of_line(p.x, p.y, p0.x, p0.y, p1.x, p1.y) > 0.0 {
2255                    winding_number = winding_number + 1;
2256                }
2257            }
2258        } else if p1.y <= p.y {
2259            if is_left_of_line(p.x, p.y, p0.x, p0.y, p1.x, p1.y) < 0.0 {
2260                winding_number = winding_number - 1;
2261            }
2262        }
2263    }
2264
2265    match polygon.fill_rule {
2266        FillRule::Nonzero => winding_number != 0,
2267        FillRule::Evenodd => winding_number.abs() % 2 == 1,
2268    }
2269}
2270
2271pub fn projected_rect_contains(
2272    source_rect: &LayoutRect,
2273    transform: &LayoutToVisTransform,
2274    target_rect: &VisRect,
2275) -> Option<()> {
2276    let points = [
2277        transform.transform_point2d(source_rect.top_left())?,
2278        transform.transform_point2d(source_rect.top_right())?,
2279        transform.transform_point2d(source_rect.bottom_right())?,
2280        transform.transform_point2d(source_rect.bottom_left())?,
2281    ];
2282    let target_points = [
2283        target_rect.top_left(),
2284        target_rect.top_right(),
2285        target_rect.bottom_right(),
2286        target_rect.bottom_left(),
2287    ];
2288    // iterate the edges of the transformed polygon
2289    for (a, b) in points
2290        .iter()
2291        .cloned()
2292        .zip(points[1..].iter().cloned().chain(iter::once(points[0])))
2293    {
2294        // If this edge is redundant, it's a weird, case, and we shouldn't go
2295        // length in trying to take the fast path (e.g. when the whole rectangle is a point).
2296        // If any of edges of the target rectangle crosses the edge, it's not completely
2297        // inside our transformed polygon either.
2298        if a.approx_eq(&b) || target_points.iter().any(|&c| (b - a).cross(c - a) < 0.0) {
2299            return None
2300        }
2301    }
2302
2303    Some(())
2304}
2305
2306
2307// Add a clip node into the list of clips to be processed
2308// for the current clip chain. Returns false if the clip
2309// results in the entire primitive being culled out.
2310fn add_clip_node_to_current_chain(
2311    handle: ClipDataHandle,
2312    prim_spatial_node_index: SpatialNodeIndex,
2313    pic_spatial_node_index: SpatialNodeIndex,
2314    visibility_spatial_node_index: SpatialNodeIndex,
2315    local_clip_rect: &mut LayoutRect,
2316    clip_node_info: &mut Vec<ClipNodeInfo>,
2317    pic_coverage_rect: &mut PictureRect,
2318    clip_data_store: &ClipDataStore,
2319    spatial_tree: &SpatialTree,
2320) -> bool {
2321    let clip_node = &clip_data_store[handle];
2322
2323    // Determine the most efficient way to convert between coordinate
2324    // systems of the primitive and clip node.
2325    let conversion = ClipSpaceConversion::new(
2326        prim_spatial_node_index,
2327        clip_node.item.spatial_node_index,
2328        visibility_spatial_node_index,
2329        spatial_tree,
2330    );
2331
2332    // If we can convert spaces, try to reduce the size of the region
2333    // requested, and cache the conversion information for the next step.
2334    if let Some(clip_rect) = clip_node.item.kind.get_local_clip_rect() {
2335        match conversion {
2336            ClipSpaceConversion::Local => {
2337                *local_clip_rect = match local_clip_rect.intersection(&clip_rect) {
2338                    Some(rect) => rect,
2339                    None => return false,
2340                };
2341            }
2342            ClipSpaceConversion::ScaleOffset(ref scale_offset) => {
2343                let clip_rect = scale_offset.map_rect(&clip_rect);
2344                *local_clip_rect = match local_clip_rect.intersection(&clip_rect) {
2345                    Some(rect) => rect,
2346                    None => return false,
2347                };
2348            }
2349            ClipSpaceConversion::Transform(..) => {
2350                // Map the local clip rect directly into the same space as the picture
2351                // surface. This will often be the same space as the clip itself, which
2352                // results in a reduction in allocated clip mask size.
2353
2354                // For simplicity, only apply this optimization if the clip is in the
2355                // same coord system as the picture. There are some 'advanced' perspective
2356                // clip tests in wrench that break without this check. Those cases are
2357                // never used in Gecko, and we aim to remove support in WR for that
2358                // in future to simplify the clipping pipeline.
2359                let pic_coord_system = spatial_tree
2360                    .get_spatial_node(pic_spatial_node_index)
2361                    .coordinate_system_id;
2362
2363                let clip_coord_system = spatial_tree
2364                    .get_spatial_node(clip_node.item.spatial_node_index)
2365                    .coordinate_system_id;
2366
2367                if pic_coord_system == clip_coord_system {
2368                    let mapper = SpaceMapper::new_with_target(
2369                        pic_spatial_node_index,
2370                        clip_node.item.spatial_node_index,
2371                        PictureRect::max_rect(),
2372                        spatial_tree,
2373                    );
2374
2375                    if let Some(pic_clip_rect) = mapper.map(&clip_rect) {
2376                        *pic_coverage_rect = pic_clip_rect
2377                            .intersection(pic_coverage_rect)
2378                            .unwrap_or(PictureRect::zero());
2379                    }
2380                }
2381            }
2382        }
2383    }
2384
2385    clip_node_info.push(ClipNodeInfo {
2386        conversion,
2387        handle,
2388    });
2389
2390    true
2391}
2392
2393#[cfg(test)]
2394mod tests {
2395    use super::projected_rect_contains;
2396    use euclid::{Transform3D, rect};
2397
2398    #[test]
2399    fn test_empty_projected_rect() {
2400        assert_eq!(
2401            None,
2402            projected_rect_contains(
2403                &rect(10.0, 10.0, 0.0, 0.0).to_box2d(),
2404                &Transform3D::identity(),
2405                &rect(20.0, 20.0, 10.0, 10.0).to_box2d(),
2406            ),
2407            "Empty rectangle is considered to include a non-empty!"
2408        );
2409    }
2410}
2411
2412/// PolygonKeys get interned, because it's a convenient way to move the data
2413/// for the polygons out of the ClipItemKind and ClipItemKeyKind enums. The
2414/// polygon data is both interned and retrieved by the scene builder, and not
2415/// accessed at all by the frame builder. Another oddity is that the
2416/// PolygonKey contains the totality of the information about the polygon, so
2417/// the InternData and StoreData types are both PolygonKey.
2418#[derive(Copy, Clone, Debug, Hash, MallocSizeOf, PartialEq, Eq)]
2419#[cfg_attr(any(feature = "serde"), derive(Deserialize, Serialize))]
2420pub enum PolygonIntern {}
2421
2422pub type PolygonDataHandle = intern::Handle<PolygonIntern>;
2423
2424impl intern::InternDebug for PolygonKey {}
2425
2426impl intern::Internable for PolygonIntern {
2427    type Key = PolygonKey;
2428    type StoreData = PolygonKey;
2429    type InternData = PolygonKey;
2430    const PROFILE_COUNTER: usize = crate::profiler::INTERNED_POLYGONS;
2431}