1use std::rc::Rc;
6use std::sync::Arc;
7
8use app_units::Au;
9use servo_base::id::ScrollTreeNodeId;
10use style::values::computed::TextDecorationLine;
11
12use crate::display_list::{
13 ClipId, ContainerTimingRootChain, ContainerTimingRoots, FragmentTextDecoration,
14 StackingContext, StackingContextFragments,
15};
16use crate::fragment_tree::{
17 BoxFragment, BoxFragmentWithStyle, Fragment, FragmentFlags, IFrameFragment, ImageFragment,
18 PositioningFragment, Tag, TextFragment,
19};
20use crate::geom::{PhysicalPoint, PhysicalRect};
21use crate::style_ext::ComputedValuesExt;
22
23pub(crate) struct PaintTraversal<'a, Handler: PaintTraversalHandler> {
24 handler: &'a mut Handler,
25 outlines: Vec<(TraversalState, Arc<BoxFragment>)>,
26 floats: Vec<(TraversalState, Arc<BoxFragment>)>,
27}
28
29impl<'a, Handler: PaintTraversalHandler> PaintTraversal<'a, Handler> {
30 pub(crate) fn traverse(root_stacking_context: &StackingContext, handler: &'a mut Handler) {
31 Self {
32 handler,
33 outlines: Vec::new(),
34 floats: Vec::new(),
35 }
36 .traverse_stacking_context(&TraversalState::default(), root_stacking_context);
37 }
38
39 fn traverse_stacking_context(
41 &mut self,
42 state: &TraversalState,
43 stacking_context: &StackingContext,
44 ) {
45 let old_outlines_length = self.outlines.len();
46 let state = state.push_stacking_context(stacking_context);
47 let stacking_context_state = self.handler.visit_stacking_context(stacking_context);
48
49 if let StackingContextFragments::Root = &stacking_context.fragment {
59 self.handler.visit_box_for_root_background(&state);
60 }
61
62 let root_fragment = stacking_context.fragment();
65 let root_fragment = root_fragment
66 .as_ref()
67 .map(|root_fragment| root_fragment.with_style());
68 if let Some(root_fragment) = &root_fragment &&
69 !root_fragment.is_inline_box()
70 {
71 self.handle_box(&state, root_fragment);
72 }
73
74 let mut children = stacking_context.children.iter().peekable();
78 while children.peek().is_some_and(|child| child.z_index < 0) {
79 self.traverse_stacking_context(
80 &state,
81 children.next().expect("Should have a value due to peek."),
82 );
83 }
84
85 if let Some(root_fragment) = &root_fragment {
86 self.traverse_stacking_context_inner(&state, root_fragment);
87 }
88
89 for child in children {
100 assert!(child.z_index >= 0);
101 self.traverse_stacking_context(&state, child);
102 }
103
104 if old_outlines_length < self.outlines.len() {
108 for (state, outline_fragment) in &self.outlines.split_off(old_outlines_length) {
109 self.handler.visit_box_for_outline(state, outline_fragment);
110 }
111 }
112
113 self.handler
114 .leave_stacking_context(&state, stacking_context_state);
115 }
116
117 fn traverse_stacking_context_inner(
118 &mut self,
119 state: &TraversalState,
120 root: &BoxFragmentWithStyle<'_>,
121 ) {
122 let old_float_length = self.floats.len();
123 let mut saw_inline_level_or_replaced = root.is_replaced();
124
125 let inner_state = state.push_box_fragment(root);
128 for child in root.children.iter() {
129 saw_inline_level_or_replaced |=
130 self.traverse_block_level_descendants_decorations(&inner_state, child);
131 }
132
133 if root.is_table_grid_with_collapsed_borders() {
136 self.handler
137 .visit_box_for_collapsed_table_borders(state, root);
138 }
139
140 if old_float_length < self.floats.len() {
143 for (state, float_fragment) in &self.floats.split_off(old_float_length) {
144 let float_fragment = &float_fragment.with_style();
145 self.handle_box(state, float_fragment);
146 self.traverse_stacking_context_inner(state, float_fragment);
147 }
148 }
149
150 if root.is_inline_box() {
152 let line_box_rect = PhysicalRect::new(inner_state.origin, root.content_rect().size);
162 self.traverse_box_in_a_line_box(
163 state,
164 root,
165 line_box_rect,
166 true, );
168 } else if saw_inline_level_or_replaced {
169 self.traverse_line_boxes_and_replaced_for_box(
178 state, root, true, );
180 }
181 }
182
183 fn traverse_stacking_container(
189 &mut self,
190 state: &TraversalState,
191 root: &BoxFragmentWithStyle<'_>,
192 is_block_level: bool,
193 ) {
194 let old_outlines_length = self.outlines.len();
195
196 if is_block_level {
199 self.handle_box(state, root);
200 }
201
202 self.traverse_stacking_context_inner(state, root);
204
205 if old_outlines_length < self.outlines.len() {
209 for (state, outline_fragment) in &self.outlines.split_off(old_outlines_length) {
210 self.handler.visit_box_for_outline(state, outline_fragment);
211 }
212 }
213 }
214
215 fn traverse_block_level_descendants_decorations(
216 &mut self,
217 state: &TraversalState,
218 fragment: &Fragment,
219 ) -> bool {
220 let mut saw_inline_level_or_replaced = false;
221
222 match fragment {
223 Fragment::LayoutRoot(layout_root_fragment) => {
224 saw_inline_level_or_replaced = self.traverse_block_level_descendants_decorations(
225 state,
226 &layout_root_fragment.inner(),
227 );
228 },
229 Fragment::Box(box_fragment) => {
230 let box_fragment = &box_fragment.with_style();
231
232 if box_fragment
235 .base
236 .flags
237 .contains(FragmentFlags::IS_COLLAPSED)
238 {
239 return false;
240 }
241
242 if box_fragment.stacking_context_type().is_some() {
246 return false;
247 }
248
249 if box_fragment.is_atomic_inline_level() || box_fragment.is_flex_or_grid_item() {
251 return true;
252 }
253
254 if box_fragment.is_inline_box() {
256 saw_inline_level_or_replaced = true;
257 } else {
258 self.handle_box(state, box_fragment);
259 }
260
261 if box_fragment.is_replaced() {
262 return true;
263 }
264
265 let state_for_children = state.push_box_fragment(box_fragment);
266 for child in box_fragment.children.iter() {
267 saw_inline_level_or_replaced |= self
268 .traverse_block_level_descendants_decorations(&state_for_children, child);
269 }
270
271 if box_fragment.is_table_grid_with_collapsed_borders() {
274 self.handler
275 .visit_box_for_collapsed_table_borders(state, box_fragment);
276 }
277 },
278 Fragment::Float(float_box_fragment) => {
279 if float_box_fragment.stacking_context_type().is_none() {
280 self.floats
281 .push((state.without_text_decorations(), float_box_fragment.clone()));
282 }
283 },
284 Fragment::Positioning(positioning_fragment) => {
285 self.handler.visit_positioning(state, positioning_fragment);
286
287 if positioning_fragment.is_line_box() {
288 saw_inline_level_or_replaced = true;
289 }
290
291 if !positioning_fragment.children.is_empty() {
292 let state = state.push_positioning_fragment(positioning_fragment);
293 for child in positioning_fragment.children.iter() {
294 saw_inline_level_or_replaced |=
295 self.traverse_block_level_descendants_decorations(&state, child);
296 }
297 }
298 },
299 Fragment::AbsoluteOrFixedPositionedPlaceholder(..) |
300 Fragment::Text(..) |
301 Fragment::Image(..) |
302 Fragment::IFrame(..) => {},
303 }
304
305 saw_inline_level_or_replaced
306 }
307
308 fn traverse_line_boxes_and_replaced_for_box(
309 &mut self,
310 state: &TraversalState,
311 fragment: &BoxFragmentWithStyle<'_>,
312 at_root_of_stacking_context: bool,
313 ) {
314 let is_flex_or_grid = fragment.is_flex_or_grid_item();
315 if fragment.is_replaced() {
316 if is_flex_or_grid {
317 self.handle_box(state, fragment);
318 }
319
320 let inner_state = state.push_box_fragment(fragment);
321 self.traverse_replaced_content(&inner_state, fragment);
322 return;
323 }
324
325 if !at_root_of_stacking_context && is_flex_or_grid {
326 self.traverse_stacking_container(state, fragment, true );
327 return;
328 }
329
330 let inner_state = state.push_box_fragment(fragment);
331 for child in fragment.children.iter() {
332 self.traverse_line_boxes_and_replaced(
333 &inner_state,
334 child,
335 false, );
337 }
338 }
339
340 fn traverse_line_boxes_and_replaced(
341 &mut self,
342 state: &TraversalState,
343 fragment: &Fragment,
344 at_root_of_stacking_context: bool,
345 ) {
346 match fragment {
347 Fragment::LayoutRoot(layout_root_fragment) => self.traverse_line_boxes_and_replaced(
348 state,
349 &layout_root_fragment.inner(),
350 at_root_of_stacking_context,
351 ),
352 Fragment::Box(box_fragment) => {
353 if box_fragment
356 .base
357 .flags
358 .contains(FragmentFlags::IS_COLLAPSED)
359 {
360 return;
361 }
362
363 if box_fragment.stacking_context_type().is_some() {
367 return;
368 }
369 self.traverse_line_boxes_and_replaced_for_box(
370 state,
371 &box_fragment.with_style(),
372 at_root_of_stacking_context,
373 );
374 },
375 Fragment::Positioning(positioning_fragment) if positioning_fragment.is_line_box() => {
376 let state = state.push_positioning_fragment(positioning_fragment);
377 let line_box_rect =
378 PhysicalRect::new(state.origin, positioning_fragment.base.rect().size);
379 for child in &positioning_fragment.children {
380 self.traverse_fragment_in_a_line_box(&state, child, line_box_rect);
381 }
382 },
383 Fragment::Positioning(positioning_fragment) => {
384 if !positioning_fragment.children.is_empty() {
385 let state = state.push_positioning_fragment(positioning_fragment);
386 for child in &positioning_fragment.children {
387 self.traverse_line_boxes_and_replaced(
388 &state, child, false, );
390 }
391 }
392 },
393 Fragment::AbsoluteOrFixedPositionedPlaceholder(_) |
394 Fragment::Float(..) |
395 Fragment::IFrame(_) |
396 Fragment::Image(_) |
397 Fragment::Text(..) => {},
398 }
399 }
400
401 fn traverse_fragment_in_a_line_box(
402 &mut self,
403 state: &TraversalState,
404 fragment: &Fragment,
405 line_box_rect: PhysicalRect<Au>,
406 ) {
407 match fragment {
408 Fragment::LayoutRoot(layout_root_fragment) => self.traverse_fragment_in_a_line_box(
409 state,
410 &layout_root_fragment.inner(),
411 line_box_rect,
412 ),
413 Fragment::Box(box_fragment) => self.traverse_box_in_a_line_box(
414 state,
415 &box_fragment.with_style(),
416 line_box_rect,
417 false, ),
419 Fragment::Text(text_fragment) => {
420 self.handler.visit_text(state, line_box_rect, text_fragment);
421 },
422 Fragment::AbsoluteOrFixedPositionedPlaceholder(..) | Fragment::Float(..) => {},
423 Fragment::Positioning(..) => {
424 unreachable!("Unexpected direct descendant PositioningContext of inline.")
425 },
426 Fragment::Image(..) | Fragment::IFrame(..) => {
427 unreachable!("Unexpected replaced content direct descendant of inline.")
428 },
429 }
430 }
431
432 fn traverse_box_in_a_line_box(
434 &mut self,
435 state: &TraversalState,
436 box_fragment: &BoxFragmentWithStyle<'_>,
437 line_box_rect: PhysicalRect<Au>,
438 at_stacking_context_root: bool,
439 ) {
440 if !at_stacking_context_root && box_fragment.stacking_context_type().is_some() {
444 return;
445 }
446
447 let is_atomic_inline_level = box_fragment.is_atomic_inline_level();
449 if !is_atomic_inline_level && !box_fragment.is_inline_box() {
450 self.traverse_line_boxes_and_replaced_for_box(
451 state,
452 box_fragment,
453 at_stacking_context_root,
454 );
455 return;
456 }
457
458 self.handle_box(state, box_fragment);
461
462 if box_fragment.is_replaced() {
470 let state = state.push_box_fragment(box_fragment);
471 self.traverse_replaced_content(&state, box_fragment);
472
473 } else if is_atomic_inline_level || box_fragment.is_flex_or_grid_item() {
476 self.traverse_stacking_container(state, box_fragment, false );
477
478 } else {
481 let state = state.push_box_fragment(box_fragment);
482 for child in &box_fragment.children {
483 self.traverse_fragment_in_a_line_box(&state, child, line_box_rect);
484 }
485 }
486 }
487
488 fn traverse_replaced_content(
489 &mut self,
490 state: &TraversalState,
491 box_fragment: &Arc<BoxFragment>,
492 ) {
493 for child in &box_fragment.children {
494 match child {
495 Fragment::LayoutRoot(layout_root_fragment) => {
496 self.traverse_stacking_container(
497 &state.without_text_decorations(),
498 &layout_root_fragment.inner_box_fragment().with_style(),
499 true, );
501 },
502 Fragment::Image(image_fragment) => {
503 let containing_block =
504 PhysicalRect::new(state.origin, box_fragment.content_rect().size);
505 self.handler
506 .visit_image(state, containing_block, image_fragment);
507 },
508 Fragment::IFrame(iframe_fragment) => {
509 self.handler.visit_iframe(state, iframe_fragment);
510 },
511 Fragment::Box(box_fragment) => {
512 self.traverse_stacking_container(
513 &state.without_text_decorations(),
514 &box_fragment.with_style(),
515 true, );
517 },
518 _ => {},
519 }
520 }
521 }
522
523 fn handle_box(&mut self, state: &TraversalState, fragment: &BoxFragmentWithStyle<'_>) {
524 if fragment.has_outline() {
525 self.outlines
526 .push((state.clone(), fragment.box_fragment.clone()));
527 }
528 self.handler.visit_box(state, fragment);
529 }
530}
531
532pub(crate) trait PaintTraversalHandler {
533 type StackingContextState;
534
535 fn visit_stacking_context(
536 &mut self,
537 stacking_context: &StackingContext,
538 ) -> Self::StackingContextState;
539 fn leave_stacking_context(
540 &mut self,
541 state: &TraversalState,
542 stacking_context_state: Self::StackingContextState,
543 );
544
545 fn visit_box(&mut self, state: &TraversalState, fragment: &BoxFragmentWithStyle<'_>);
546 fn visit_iframe(&mut self, _state: &TraversalState, _fragment: &Arc<IFrameFragment>) {}
547 fn visit_image(
548 &mut self,
549 _state: &TraversalState,
550 _containing_block: PhysicalRect<Au>,
551 _fragment: &Arc<ImageFragment>,
552 ) {
553 }
554 fn visit_text(
555 &mut self,
556 state: &TraversalState,
557 line_box_rect: PhysicalRect<Au>,
558 fragment: &Arc<TextFragment>,
559 );
560 fn visit_positioning(&mut self, _state: &TraversalState, _fragment: &Arc<PositioningFragment>) {
561 }
562
563 fn visit_box_for_root_background(&mut self, _state: &TraversalState) {}
564 fn visit_box_for_outline(&mut self, _state: &TraversalState, _fragment: &Arc<BoxFragment>) {}
565 fn visit_box_for_collapsed_table_borders(
566 &mut self,
567 _state: &TraversalState,
568 _fragment: &BoxFragmentWithStyle<'_>,
569 ) {
570 }
571}
572
573#[derive(Clone, Debug)]
574pub(crate) struct TraversalState {
575 pub spatial_id: ScrollTreeNodeId,
576 pub clip_id: ClipId,
577 pub origin: PhysicalPoint<Au>,
578 pub text_decorations: Rc<Vec<FragmentTextDecoration>>,
579 pub accumulated_opacity: f32,
581 pub containing_element_tag: Option<Tag>,
586 pub container_timing_roots: ContainerTimingRoots,
590}
591
592impl Default for TraversalState {
593 fn default() -> Self {
594 Self {
595 spatial_id: Default::default(),
596 clip_id: Default::default(),
597 origin: Default::default(),
598 text_decorations: Default::default(),
599 accumulated_opacity: 1.0,
600 containing_element_tag: Default::default(),
601 container_timing_roots: Default::default(),
602 }
603 }
604}
605
606impl TraversalState {
607 pub(crate) fn push_box_fragment(&self, box_fragment: &BoxFragmentWithStyle<'_>) -> Self {
608 let style = box_fragment.style();
609
610 let mut propagated_text_decorations = self.text_decorations.clone();
619 if box_fragment.is_atomic_inline_level() ||
620 box_fragment.base.flags.contains(
621 FragmentFlags::IS_OUTSIDE_LIST_ITEM_MARKER | FragmentFlags::IS_REPLACED,
622 )
623 {
624 propagated_text_decorations = Default::default();
625 }
626
627 let text_decorations = match style.get_text_decoration_line() {
628 &TextDecorationLine::NONE => propagated_text_decorations,
629 line => {
630 let mut new_vector = (*propagated_text_decorations).clone();
631 let color = &style.get_inherited_text().color;
632 new_vector.push(FragmentTextDecoration {
633 line: *line,
634 color: style.get_text_decoration_color().resolve_to_absolute(color),
635 style: style.slow_clone_text_decoration_style(),
636 thickness: style.slow_clone_text_decoration_thickness(),
637 });
638 Rc::new(new_vector)
639 },
640 };
641
642 Self {
643 origin: self.origin + box_fragment.content_rect().origin.to_vector(),
644 spatial_id: box_fragment
645 .generated_scroll_tree_node_id()
646 .unwrap_or(self.spatial_id),
647 clip_id: box_fragment.generated_clip_id().unwrap_or(self.clip_id),
648 text_decorations,
649 accumulated_opacity: self.accumulated_opacity * style.slow_clone_opacity(),
650 container_timing_roots: self.container_timing_roots_including(box_fragment),
651 containing_element_tag: if !box_fragment.is_inline_box() ||
660 style.establishes_containing_block_for_absolute_descendants(
661 box_fragment.base.flags,
662 ) {
663 box_fragment.base.tag.or(self.containing_element_tag)
664 } else {
665 self.containing_element_tag
666 },
667 }
668 }
669
670 pub(crate) fn container_timing_roots_including(
673 &self,
674 box_fragment: &BoxFragment,
675 ) -> ContainerTimingRoots {
676 ContainerTimingRootChain::for_contents_of(&self.container_timing_roots, &box_fragment.base)
677 }
678
679 pub(crate) fn without_text_decorations(&self) -> Self {
680 Self {
681 text_decorations: Default::default(),
682 container_timing_roots: self.container_timing_roots.clone(),
683 ..*self
684 }
685 }
686
687 pub(crate) fn push_positioning_fragment(
688 &self,
689 positioning_fragment: &PositioningFragment,
690 ) -> Self {
691 Self {
692 origin: self.origin + positioning_fragment.base.rect().origin.to_vector(),
693 spatial_id: self.spatial_id,
694 clip_id: self.clip_id,
695 text_decorations: self.text_decorations.clone(),
696 accumulated_opacity: self.accumulated_opacity *
697 positioning_fragment.style.borrow().slow_clone_opacity(),
698 containing_element_tag: self.containing_element_tag,
699 container_timing_roots: self.container_timing_roots.clone(),
700 }
701 }
702
703 pub(crate) fn push_stacking_context(&self, stacking_context: &StackingContext) -> Self {
704 Self {
705 origin: stacking_context.containing_block_origin,
706 spatial_id: stacking_context.scroll_tree_node_id,
707 clip_id: stacking_context.clip_id,
708 text_decorations: stacking_context.text_decorations.clone(),
709 accumulated_opacity: self.accumulated_opacity *
710 stacking_context
711 .fragment()
712 .map_or(1.0, |fragment| fragment.style().slow_clone_opacity()),
713 containing_element_tag: self.containing_element_tag,
714 container_timing_roots: stacking_context.container_timing_roots.clone(),
715 }
716 }
717}