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/. */
7 use euclid::{Point2D, Rect, Size2D, Vector2D, point2, size2};
8 use euclid::{default, Transform2D, Transform3D, Scale};
9 use malloc_size_of::{MallocShallowSizeOf, MallocSizeOf, MallocSizeOfOps};
10 use plane_split::{Clipper, Polygon};
11 use std::{i32, f32, fmt, ptr};
13 use std::num::NonZeroUsize;
14 use std::os::raw::c_void;
16 use std::mem::replace;
19 // Matches the definition of SK_ScalarNearlyZero in Skia.
20 const NEARLY_ZERO: f32 = 1.0 / 4096.0;
22 /// A typesafe helper that separates new value construction from
23 /// vector growing, allowing LLVM to ideally construct the element in place.
24 pub struct Allocation<'a, T: 'a> {
29 impl<'a, T> Allocation<'a, T> {
30 // writing is safe because alloc() ensured enough capacity
31 // and `Allocation` holds a mutable borrow to prevent anyone else
32 // from breaking this invariant.
34 pub fn init(self, value: T) -> usize {
36 ptr::write(self.vec.as_mut_ptr().add(self.index), value);
37 self.vec.set_len(self.index + 1);
43 /// An entry into a vector, similar to `std::collections::hash_map::Entry`.
44 pub enum VecEntry<'a, T: 'a> {
45 Vacant(Allocation<'a, T>),
49 impl<'a, T> VecEntry<'a, T> {
51 pub fn set(self, value: T) {
53 VecEntry::Vacant(alloc) => { alloc.init(value); }
54 VecEntry::Occupied(slot) => { *slot = value; }
59 pub trait VecHelper<T> {
60 /// Growns the vector by a single entry, returning the allocation.
61 fn alloc(&mut self) -> Allocation<T>;
62 /// Either returns an existing elemenet, or grows the vector by one.
63 /// Doesn't expect indices to be higher than the current length.
64 fn entry(&mut self, index: usize) -> VecEntry<T>;
66 /// Equivalent to `mem::replace(&mut vec, Vec::new())`
67 fn take(&mut self) -> Self;
69 /// Call clear and return self (useful for chaining with calls that move the vector).
70 fn cleared(self) -> Self;
72 /// Functionally equivalent to `mem::replace(&mut vec, Vec::new())` but tries
73 /// to keep the allocation in the caller if it is empty or replace it with a
74 /// pre-allocated vector.
75 fn take_and_preallocate(&mut self) -> Self;
78 impl<T> VecHelper<T> for Vec<T> {
79 fn alloc(&mut self) -> Allocation<T> {
80 let index = self.len();
81 if self.capacity() == index {
90 fn entry(&mut self, index: usize) -> VecEntry<T> {
91 if index < self.len() {
92 VecEntry::Occupied(unsafe {
93 self.get_unchecked_mut(index)
96 assert_eq!(index, self.len());
97 VecEntry::Vacant(self.alloc())
101 fn take(&mut self) -> Self {
102 replace(self, Vec::new())
105 fn cleared(mut self) -> Self {
111 fn take_and_preallocate(&mut self) -> Self {
112 let len = self.len();
117 replace(self, Vec::with_capacity(len + 8))
122 // Represents an optimized transform where there is only
123 // a scale and translation (which are guaranteed to maintain
124 // an axis align rectangle under transformation). The
125 // scaling is applied first, followed by the translation.
126 // TODO(gw): We should try and incorporate F <-> T units here,
127 // but it's a bit tricky to do that now with the
128 // way the current spatial tree works.
129 #[derive(Debug, Clone, Copy, MallocSizeOf)]
130 #[cfg_attr(feature = "capture", derive(Serialize))]
131 pub struct ScaleOffset {
132 pub scale: default::Vector2D<f32>,
133 pub offset: default::Vector2D<f32>,
137 pub fn identity() -> Self {
139 scale: Vector2D::new(1.0, 1.0),
140 offset: Vector2D::zero(),
144 // Construct a ScaleOffset from a transform. Returns
145 // None if the matrix is not a pure scale / translation.
146 pub fn from_transform<F, T>(
147 m: &Transform3D<f32, F, T>,
148 ) -> Option<ScaleOffset> {
150 // To check that we have a pure scale / translation:
151 // Every field must match an identity matrix, except:
152 // - Any value present in tx,ty
153 // - Any value present in sx,sy
155 if m.m12.abs() > NEARLY_ZERO ||
156 m.m13.abs() > NEARLY_ZERO ||
157 m.m14.abs() > NEARLY_ZERO ||
158 m.m21.abs() > NEARLY_ZERO ||
159 m.m23.abs() > NEARLY_ZERO ||
160 m.m24.abs() > NEARLY_ZERO ||
161 m.m31.abs() > NEARLY_ZERO ||
162 m.m32.abs() > NEARLY_ZERO ||
163 (m.m33 - 1.0).abs() > NEARLY_ZERO ||
164 m.m34.abs() > NEARLY_ZERO ||
165 m.m43.abs() > NEARLY_ZERO ||
166 (m.m44 - 1.0).abs() > NEARLY_ZERO {
171 scale: Vector2D::new(m.m11, m.m22),
172 offset: Vector2D::new(m.m41, m.m42),
176 pub fn from_offset(offset: default::Vector2D<f32>) -> Self {
178 scale: Vector2D::new(1.0, 1.0),
183 pub fn inverse(&self) -> Self {
185 scale: Vector2D::new(
189 offset: Vector2D::new(
190 -self.offset.x / self.scale.x,
191 -self.offset.y / self.scale.y,
196 pub fn offset(&self, offset: default::Vector2D<f32>) -> Self {
199 scale: Vector2D::new(1.0, 1.0),
205 pub fn scale(&self, scale: f32) -> Self {
208 scale: Vector2D::new(scale, scale),
209 offset: Vector2D::zero(),
214 /// Produce a ScaleOffset that includes both self and other.
215 /// The 'self' ScaleOffset is applied after other.
216 /// This is equivalent to `Transform3D::pre_transform`.
217 pub fn accumulate(&self, other: &ScaleOffset) -> Self {
219 scale: Vector2D::new(
220 self.scale.x * other.scale.x,
221 self.scale.y * other.scale.y,
223 offset: Vector2D::new(
224 self.offset.x + self.scale.x * other.offset.x,
225 self.offset.y + self.scale.y * other.offset.y,
230 pub fn map_rect<F, T>(&self, rect: &Rect<f32, F>) -> Rect<f32, T> {
231 // TODO(gw): The logic below can return an unexpected result if the supplied
232 // rect is invalid (has size < 0). Since Gecko currently supplied
233 // invalid rects in some cases, adding a max(0) here ensures that
234 // mapping an invalid rect retains the property that rect.is_empty()
235 // will return true (the mapped rect output will have size 0 instead
236 // of a negative size). In future we could catch / assert / fix
237 // these invalid rects earlier, and assert here instead.
239 let w = rect.size.width.max(0.0);
240 let h = rect.size.height.max(0.0);
242 let mut x0 = rect.origin.x * self.scale.x + self.offset.x;
243 let mut y0 = rect.origin.y * self.scale.y + self.offset.y;
245 let mut sx = w * self.scale.x;
246 let mut sy = h * self.scale.y;
248 // Handle negative scale. Previously, branchless float math was used to find the
249 // min / max vertices and size. However, that sequence of operations was producind
250 // additional floating point accuracy on android emulator builds, causing one test
251 // to fail an assert. Instead, we retain the same math as previously, and adjust
252 // the origin / size if required.
254 if self.scale.x < 0.0 {
258 if self.scale.y < 0.0 {
264 Point2D::new(x0, y0),
269 pub fn unmap_rect<F, T>(&self, rect: &Rect<f32, F>) -> Rect<f32, T> {
270 // TODO(gw): The logic below can return an unexpected result if the supplied
271 // rect is invalid (has size < 0). Since Gecko currently supplied
272 // invalid rects in some cases, adding a max(0) here ensures that
273 // mapping an invalid rect retains the property that rect.is_empty()
274 // will return true (the mapped rect output will have size 0 instead
275 // of a negative size). In future we could catch / assert / fix
276 // these invalid rects earlier, and assert here instead.
278 let w = rect.size.width.max(0.0);
279 let h = rect.size.height.max(0.0);
281 let mut x0 = (rect.origin.x - self.offset.x) / self.scale.x;
282 let mut y0 = (rect.origin.y - self.offset.y) / self.scale.y;
284 let mut sx = w / self.scale.x;
285 let mut sy = h / self.scale.y;
287 // Handle negative scale. Previously, branchless float math was used to find the
288 // min / max vertices and size. However, that sequence of operations was producind
289 // additional floating point accuracy on android emulator builds, causing one test
290 // to fail an assert. Instead, we retain the same math as previously, and adjust
291 // the origin / size if required.
293 if self.scale.x < 0.0 {
297 if self.scale.y < 0.0 {
303 Point2D::new(x0, y0),
308 pub fn map_vector<F, T>(&self, vector: &Vector2D<f32, F>) -> Vector2D<f32, T> {
310 vector.x * self.scale.x,
311 vector.y * self.scale.y,
315 pub fn unmap_vector<F, T>(&self, vector: &Vector2D<f32, F>) -> Vector2D<f32, T> {
317 vector.x / self.scale.x,
318 vector.y / self.scale.y,
322 pub fn map_point<F, T>(&self, point: &Point2D<f32, F>) -> Point2D<f32, T> {
324 point.x * self.scale.x + self.offset.x,
325 point.y * self.scale.y + self.offset.y,
329 pub fn unmap_point<F, T>(&self, point: &Point2D<f32, F>) -> Point2D<f32, T> {
331 (point.x - self.offset.x) / self.scale.x,
332 (point.y - self.offset.y) / self.scale.y,
336 pub fn to_transform<F, T>(&self) -> Transform3D<f32, F, T> {
361 // TODO: Implement these in euclid!
362 pub trait MatrixHelpers<Src, Dst> {
363 /// A port of the preserves2dAxisAlignment function in Skia.
364 /// Defined in the SkMatrix44 class.
365 fn preserves_2d_axis_alignment(&self) -> bool;
366 fn has_perspective_component(&self) -> bool;
367 fn has_2d_inverse(&self) -> bool;
368 /// Check if the matrix post-scaling on either the X or Y axes could cause geometry
369 /// transformed by this matrix to have scaling exceeding the supplied limit.
370 fn exceeds_2d_scale(&self, limit: f64) -> bool;
371 fn inverse_project(&self, target: &Point2D<f32, Dst>) -> Option<Point2D<f32, Src>>;
372 fn inverse_rect_footprint(&self, rect: &Rect<f32, Dst>) -> Option<Rect<f32, Src>>;
373 fn transform_kind(&self) -> TransformedRectKind;
374 fn is_simple_translation(&self) -> bool;
375 fn is_simple_2d_translation(&self) -> bool;
376 fn is_2d_scale_translation(&self) -> bool;
377 /// Return the determinant of the 2D part of the matrix.
378 fn determinant_2d(&self) -> f32;
379 /// This function returns a point in the `Src` space that projects into zero XY.
380 /// It ignores the Z coordinate and is usable for "flattened" transformations,
381 /// since they are not generally inversible.
382 fn inverse_project_2d_origin(&self) -> Option<Point2D<f32, Src>>;
383 /// Turn Z transformation into identity. This is useful when crossing "flat"
384 /// transform styled stacking contexts upon traversing the coordinate systems.
385 fn flatten_z_output(&mut self);
387 fn cast_unit<NewSrc, NewDst>(&self) -> Transform3D<f32, NewSrc, NewDst>;
390 impl<Src, Dst> MatrixHelpers<Src, Dst> for Transform3D<f32, Src, Dst> {
391 fn preserves_2d_axis_alignment(&self) -> bool {
392 if self.m14 != 0.0 || self.m24 != 0.0 {
401 if self.m11.abs() > NEARLY_ZERO {
405 if self.m12.abs() > NEARLY_ZERO {
409 if self.m21.abs() > NEARLY_ZERO {
413 if self.m22.abs() > NEARLY_ZERO {
418 col0 < 2 && col1 < 2 && row0 < 2 && row1 < 2
421 fn has_perspective_component(&self) -> bool {
422 self.m14.abs() > NEARLY_ZERO ||
423 self.m24.abs() > NEARLY_ZERO ||
424 self.m34.abs() > NEARLY_ZERO ||
425 (self.m44 - 1.0).abs() > NEARLY_ZERO
428 fn has_2d_inverse(&self) -> bool {
429 self.determinant_2d() != 0.0
432 fn exceeds_2d_scale(&self, limit: f64) -> bool {
433 let limit2 = (limit * limit) as f32;
434 self.m11 * self.m11 + self.m12 * self.m12 > limit2 ||
435 self.m21 * self.m21 + self.m22 * self.m22 > limit2
438 /// Find out a point in `Src` that would be projected into the `target`.
439 fn inverse_project(&self, target: &Point2D<f32, Dst>) -> Option<Point2D<f32, Src>> {
440 // form the linear equation for the hyperplane intersection
441 let m = Transform2D::<f32, Src, Dst>::new(
442 self.m11 - target.x * self.m14, self.m12 - target.y * self.m14,
443 self.m21 - target.x * self.m24, self.m22 - target.y * self.m24,
444 self.m41 - target.x * self.m44, self.m42 - target.y * self.m44,
446 let inv = m.inverse()?;
447 // we found the point, now check if it maps to the positive hemisphere
448 if inv.m31 * self.m14 + inv.m32 * self.m24 + self.m44 > 0.0 {
449 Some(Point2D::new(inv.m31, inv.m32))
455 fn inverse_rect_footprint(&self, rect: &Rect<f32, Dst>) -> Option<Rect<f32, Src>> {
456 Some(Rect::from_points(&[
457 self.inverse_project(&rect.origin)?,
458 self.inverse_project(&rect.top_right())?,
459 self.inverse_project(&rect.bottom_left())?,
460 self.inverse_project(&rect.bottom_right())?,
464 fn transform_kind(&self) -> TransformedRectKind {
465 if self.preserves_2d_axis_alignment() {
466 TransformedRectKind::AxisAligned
468 TransformedRectKind::Complex
472 fn is_simple_translation(&self) -> bool {
473 if (self.m11 - 1.0).abs() > NEARLY_ZERO ||
474 (self.m22 - 1.0).abs() > NEARLY_ZERO ||
475 (self.m33 - 1.0).abs() > NEARLY_ZERO ||
476 (self.m44 - 1.0).abs() > NEARLY_ZERO {
480 self.m12.abs() < NEARLY_ZERO && self.m13.abs() < NEARLY_ZERO &&
481 self.m14.abs() < NEARLY_ZERO && self.m21.abs() < NEARLY_ZERO &&
482 self.m23.abs() < NEARLY_ZERO && self.m24.abs() < NEARLY_ZERO &&
483 self.m31.abs() < NEARLY_ZERO && self.m32.abs() < NEARLY_ZERO &&
484 self.m34.abs() < NEARLY_ZERO
487 fn is_simple_2d_translation(&self) -> bool {
488 if !self.is_simple_translation() {
492 self.m43.abs() < NEARLY_ZERO
501 fn is_2d_scale_translation(&self) -> bool {
502 (self.m33 - 1.0).abs() < NEARLY_ZERO &&
503 (self.m44 - 1.0).abs() < NEARLY_ZERO &&
504 self.m12.abs() < NEARLY_ZERO && self.m13.abs() < NEARLY_ZERO && self.m14.abs() < NEARLY_ZERO &&
505 self.m21.abs() < NEARLY_ZERO && self.m23.abs() < NEARLY_ZERO && self.m24.abs() < NEARLY_ZERO &&
506 self.m31.abs() < NEARLY_ZERO && self.m32.abs() < NEARLY_ZERO && self.m34.abs() < NEARLY_ZERO &&
507 self.m43.abs() < NEARLY_ZERO
510 fn determinant_2d(&self) -> f32 {
511 self.m11 * self.m22 - self.m12 * self.m21
514 fn inverse_project_2d_origin(&self) -> Option<Point2D<f32, Src>> {
515 let det = self.determinant_2d();
517 let x = (self.m21 * self.m42 - self.m41 * self.m22) / det;
518 let y = (self.m12 * self.m41 - self.m11 * self.m42) / det;
519 Some(Point2D::new(x, y))
525 fn flatten_z_output(&mut self) {
530 //Note: we used to zero out m3? as well, see "reftests/flatten-all-flat.yaml" test
533 fn cast_unit<NewSrc, NewDst>(&self) -> Transform3D<f32, NewSrc, NewDst> {
535 self.m11, self.m12, self.m13, self.m14,
536 self.m21, self.m22, self.m23, self.m24,
537 self.m31, self.m32, self.m33, self.m34,
538 self.m41, self.m42, self.m43, self.m44,
543 pub trait PointHelpers<U>
547 fn snap(&self) -> Self;
550 impl<U> PointHelpers<U> for Point2D<f32, U> {
551 fn snap(&self) -> Self {
553 (self.x + 0.5).floor(),
554 (self.y + 0.5).floor(),
559 pub trait RectHelpers<U>
563 fn from_floats(x0: f32, y0: f32, x1: f32, y1: f32) -> Self;
564 fn snap(&self) -> Self;
567 impl<U> RectHelpers<U> for Rect<f32, U> {
568 fn from_floats(x0: f32, y0: f32, x1: f32, y1: f32) -> Self {
570 Point2D::new(x0, y0),
571 Size2D::new(x1 - x0, y1 - y0),
575 fn snap(&self) -> Self {
576 let origin = Point2D::new(
577 (self.origin.x + 0.5).floor(),
578 (self.origin.y + 0.5).floor(),
583 (self.origin.x + self.size.width + 0.5).floor() - origin.x,
584 (self.origin.y + self.size.height + 0.5).floor() - origin.y,
590 pub trait VectorHelpers<U>
594 fn snap(&self) -> Self;
597 impl<U> VectorHelpers<U> for Vector2D<f32, U> {
598 fn snap(&self) -> Self {
600 (self.x + 0.5).floor(),
601 (self.y + 0.5).floor(),
606 pub fn lerp(a: f32, b: f32, t: f32) -> f32 {
611 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
612 #[cfg_attr(feature = "capture", derive(Serialize))]
613 #[cfg_attr(feature = "replay", derive(Deserialize))]
614 pub enum TransformedRectKind {
620 pub fn pack_as_float(value: u32) -> f32 {
625 fn extract_inner_rect_impl<U>(
627 radii: &BorderRadius,
629 ) -> Option<Rect<f32, U>> {
630 // `k` defines how much border is taken into account
631 // We enforce the offsets to be rounded to pixel boundaries
632 // by `ceil`-ing and `floor`-ing them
634 let xl = (k * radii.top_left.width.max(radii.bottom_left.width)).ceil();
635 let xr = (rect.size.width - k * radii.top_right.width.max(radii.bottom_right.width)).floor();
636 let yt = (k * radii.top_left.height.max(radii.top_right.height)).ceil();
638 (rect.size.height - k * radii.bottom_left.height.max(radii.bottom_right.height)).floor();
640 if xl <= xr && yt <= yb {
642 Point2D::new(rect.origin.x + xl, rect.origin.y + yt),
643 Size2D::new(xr - xl, yb - yt),
650 /// Return an aligned rectangle that is inside the clip region and doesn't intersect
651 /// any of the bounding rectangles of the rounded corners.
652 pub fn extract_inner_rect_safe<U>(
654 radii: &BorderRadius,
655 ) -> Option<Rect<f32, U>> {
656 // value of `k==1.0` is used for extraction of the corner rectangles
657 // see `SEGMENT_CORNER_*` in `clip_shared.glsl`
658 extract_inner_rect_impl(rect, radii, 1.0)
667 use euclid::default::{Point2D, Rect, Size2D, Transform3D};
668 use euclid::{Angle, approxeq::ApproxEq};
669 use std::f32::consts::PI;
670 use crate::clip::{is_left_of_line, polygon_contains_point};
671 use crate::prim_store::PolygonKey;
675 fn inverse_project() {
676 let m0 = Transform3D::identity();
677 let p0 = Point2D::new(1.0, 2.0);
678 // an identical transform doesn't need any inverse projection
679 assert_eq!(m0.inverse_project(&p0), Some(p0));
680 let m1 = Transform3D::rotation(0.0, 1.0, 0.0, Angle::radians(-PI / 3.0));
681 // rotation by 60 degrees would imply scaling of X component by a factor of 2
682 assert_eq!(m1.inverse_project(&p0), Some(Point2D::new(2.0, 2.0)));
686 fn inverse_project_footprint() {
687 let m = Transform3D::new(
688 0.477499992, 0.135000005, -1.0, 0.000624999986,
689 -0.642787635, 0.766044438, 0.0, 0.0,
690 0.766044438, 0.642787635, 0.0, 0.0,
691 1137.10986, 113.71286, 402.0, 0.748749971,
693 let r = Rect::new(Point2D::zero(), Size2D::new(804.0, 804.0));
701 let mi = m.inverse().unwrap();
702 // In this section, we do the forward and backward transformation
703 // to confirm that its bijective.
704 // We also do the inverse projection path, and confirm it functions the same way.
707 let pp = m.transform_point2d_homogeneous(*p);
708 let p3 = pp.to_point3d().unwrap();
709 let pi = mi.transform_point3d_homogeneous(p3);
710 let px = pi.to_point2d().unwrap();
711 let py = m.inverse_project(&pp.to_point2d().unwrap()).unwrap();
712 println!("\t{:?} -> {:?} -> {:?} -> ({:?} -> {:?}, {:?})", p, pp, p3, pi, px, py);
713 assert!(px.approx_eq_eps(p, &Point2D::new(0.001, 0.001)));
714 assert!(py.approx_eq_eps(p, &Point2D::new(0.001, 0.001)));
718 let rp = project_rect(&m, &r, &Rect::new(Point2D::zero(), Size2D::new(1000.0, 1000.0))).unwrap();
719 println!("Projected {:?}", rp);
720 // one of the points ends up in the negative hemisphere
721 assert_eq!(m.inverse_project(&rp.origin), None);
723 if let Some(ri) = m.inverse_rect_footprint(&rp) {
724 // inverse footprint should be larger, since it doesn't know the original Z
725 assert!(ri.contains_rect(&r), "Inverse {:?}", ri);
729 fn validate_convert(xref: &LayoutTransform) {
730 let so = ScaleOffset::from_transform(xref).unwrap();
731 let xf = so.to_transform();
732 assert!(xref.approx_eq(&xf));
736 fn negative_scale_map_unmap() {
737 let xref = LayoutTransform::scale(1.0, -1.0, 1.0)
738 .pre_translate(LayoutVector3D::new(124.0, 38.0, 0.0));
739 let so = ScaleOffset::from_transform(&xref).unwrap();
740 let local_rect = LayoutRect::new(
741 LayoutPoint::new(50.0, -100.0),
742 LayoutSize::new(200.0, 400.0),
745 let mapped_rect: LayoutRect = so.map_rect(&local_rect);
746 let xf_rect = project_rect(
749 &LayoutRect::max_rect(),
752 assert!(mapped_rect.origin.x.approx_eq(&xf_rect.origin.x));
753 assert!(mapped_rect.origin.y.approx_eq(&xf_rect.origin.y));
754 assert!(mapped_rect.size.width.approx_eq(&xf_rect.size.width));
755 assert!(mapped_rect.size.height.approx_eq(&xf_rect.size.height));
757 let unmapped_rect: LayoutRect = so.unmap_rect(&mapped_rect);
758 assert!(unmapped_rect.origin.x.approx_eq(&local_rect.origin.x));
759 assert!(unmapped_rect.origin.y.approx_eq(&local_rect.origin.y));
760 assert!(unmapped_rect.size.width.approx_eq(&local_rect.size.width));
761 assert!(unmapped_rect.size.height.approx_eq(&local_rect.size.height));
765 fn scale_offset_convert() {
766 let xref = LayoutTransform::translation(130.0, 200.0, 0.0);
767 validate_convert(&xref);
769 let xref = LayoutTransform::scale(13.0, 8.0, 1.0);
770 validate_convert(&xref);
772 let xref = LayoutTransform::scale(0.5, 0.5, 1.0)
773 .pre_translate(LayoutVector3D::new(124.0, 38.0, 0.0));
774 validate_convert(&xref);
776 let xref = LayoutTransform::scale(30.0, 11.0, 1.0)
777 .then_translate(vec3(50.0, 240.0, 0.0));
778 validate_convert(&xref);
781 fn validate_inverse(xref: &LayoutTransform) {
782 let s0 = ScaleOffset::from_transform(xref).unwrap();
783 let s1 = s0.inverse().accumulate(&s0);
784 assert!((s1.scale.x - 1.0).abs() < NEARLY_ZERO &&
785 (s1.scale.y - 1.0).abs() < NEARLY_ZERO &&
786 s1.offset.x.abs() < NEARLY_ZERO &&
787 s1.offset.y.abs() < NEARLY_ZERO,
793 fn scale_offset_inverse() {
794 let xref = LayoutTransform::translation(130.0, 200.0, 0.0);
795 validate_inverse(&xref);
797 let xref = LayoutTransform::scale(13.0, 8.0, 1.0);
798 validate_inverse(&xref);
800 let xref = LayoutTransform::translation(124.0, 38.0, 0.0).
801 then_scale(0.5, 0.5, 1.0);
803 validate_inverse(&xref);
805 let xref = LayoutTransform::scale(30.0, 11.0, 1.0)
806 .then_translate(vec3(50.0, 240.0, 0.0));
807 validate_inverse(&xref);
810 fn validate_accumulate(x0: &LayoutTransform, x1: &LayoutTransform) {
811 let x = x1.then(&x0);
813 let s0 = ScaleOffset::from_transform(x0).unwrap();
814 let s1 = ScaleOffset::from_transform(x1).unwrap();
816 let s = s0.accumulate(&s1).to_transform();
818 assert!(x.approx_eq(&s), "{:?}\n{:?}", x, s);
822 fn scale_offset_accumulate() {
823 let x0 = LayoutTransform::translation(130.0, 200.0, 0.0);
824 let x1 = LayoutTransform::scale(7.0, 3.0, 1.0);
826 validate_accumulate(&x0, &x1);
830 fn inverse_project_2d_origin() {
831 let mut m = Transform3D::identity();
832 assert_eq!(m.inverse_project_2d_origin(), Some(Point2D::zero()));
834 assert_eq!(m.inverse_project_2d_origin(), None);
840 let origin = m.inverse_project_2d_origin().unwrap();
841 assert_eq!(origin, Point2D::new(1.0, 0.5));
842 assert_eq!(m.transform_point2d(origin), Some(Point2D::zero()));
846 fn polygon_clip_is_left_of_point() {
847 // Define points of a line through (1, -3) and (-2, 6) to test against.
848 // If the triplet consisting of these two points and the test point
849 // form a counter-clockwise triangle, then the test point is on the
850 // left. The easiest way to visualize this is with an "ascending"
851 // line from low-Y to high-Y.
857 // Test some points to the left of the line.
858 assert!(is_left_of_line(-9.0, 0.0, p0_x, p0_y, p1_x, p1_y) > 0.0);
859 assert!(is_left_of_line(-1.0, 1.0, p0_x, p0_y, p1_x, p1_y) > 0.0);
860 assert!(is_left_of_line(1.0, -4.0, p0_x, p0_y, p1_x, p1_y) > 0.0);
862 // Test some points on the line.
863 assert!(is_left_of_line(-3.0, 9.0, p0_x, p0_y, p1_x, p1_y) == 0.0);
864 assert!(is_left_of_line(0.0, 0.0, p0_x, p0_y, p1_x, p1_y) == 0.0);
865 assert!(is_left_of_line(100.0, -300.0, p0_x, p0_y, p1_x, p1_y) == 0.0);
867 // Test some points to the right of the line.
868 assert!(is_left_of_line(0.0, 1.0, p0_x, p0_y, p1_x, p1_y) < 0.0);
869 assert!(is_left_of_line(-4.0, 13.0, p0_x, p0_y, p1_x, p1_y) < 0.0);
870 assert!(is_left_of_line(5.0, -12.0, p0_x, p0_y, p1_x, p1_y) < 0.0);
874 fn polygon_clip_contains_point() {
875 // We define the points of a self-overlapping polygon, which we will
876 // use to create polygons with different windings and fill rules.
877 let p0 = LayoutPoint::new(4.0, 4.0);
878 let p1 = LayoutPoint::new(6.0, 4.0);
879 let p2 = LayoutPoint::new(4.0, 7.0);
880 let p3 = LayoutPoint::new(2.0, 1.0);
881 let p4 = LayoutPoint::new(8.0, 1.0);
882 let p5 = LayoutPoint::new(6.0, 7.0);
884 let poly_clockwise_nonzero = PolygonKey::new(
885 &[p5, p4, p3, p2, p1, p0].to_vec(), FillRule::Nonzero
887 let poly_clockwise_evenodd = PolygonKey::new(
888 &[p5, p4, p3, p2, p1, p0].to_vec(), FillRule::Evenodd
890 let poly_counter_clockwise_nonzero = PolygonKey::new(
891 &[p0, p1, p2, p3, p4, p5].to_vec(), FillRule::Nonzero
893 let poly_counter_clockwise_evenodd = PolygonKey::new(
894 &[p0, p1, p2, p3, p4, p5].to_vec(), FillRule::Evenodd
897 // We define a rect that provides a bounding clip area of
899 let rect = LayoutRect::new(LayoutPoint::new(0.0, 0.0),
900 LayoutSize::new(10.0, 10.0));
902 // And we'll test three points of interest.
903 let p_inside_once = LayoutPoint::new(5.0, 3.0);
904 let p_inside_twice = LayoutPoint::new(5.0, 5.0);
905 let p_outside = LayoutPoint::new(9.0, 9.0);
907 // We should get the same results for both clockwise and
908 // counter-clockwise polygons.
909 // For nonzero polygons, the inside twice point is considered inside.
910 for poly_nonzero in vec![poly_clockwise_nonzero, poly_counter_clockwise_nonzero].iter() {
911 assert_eq!(polygon_contains_point(&p_inside_once, &rect, &poly_nonzero), true);
912 assert_eq!(polygon_contains_point(&p_inside_twice, &rect, &poly_nonzero), true);
913 assert_eq!(polygon_contains_point(&p_outside, &rect, &poly_nonzero), false);
915 // For evenodd polygons, the inside twice point is considered outside.
916 for poly_evenodd in vec![poly_clockwise_evenodd, poly_counter_clockwise_evenodd].iter() {
917 assert_eq!(polygon_contains_point(&p_inside_once, &rect, &poly_evenodd), true);
918 assert_eq!(polygon_contains_point(&p_inside_twice, &rect, &poly_evenodd), false);
919 assert_eq!(polygon_contains_point(&p_outside, &rect, &poly_evenodd), false);
925 fn max_rect() -> Self;
928 impl MaxRect for DeviceIntRect {
929 fn max_rect() -> Self {
931 DeviceIntPoint::new(i32::MIN / 2, i32::MIN / 2),
932 DeviceIntSize::new(i32::MAX, i32::MAX),
937 impl<U> MaxRect for Rect<f32, U> {
938 fn max_rect() -> Self {
939 // Having an unlimited bounding box is fine up until we try
940 // to cast it to `i32`, where we get `-2147483648` for any
941 // values larger than or equal to 2^31.
943 // Note: clamping to i32::MIN and i32::MAX is not a solution,
944 // with explanation left as an exercise for the reader.
945 const MAX_COORD: f32 = 1.0e9;
948 Point2D::new(-MAX_COORD, -MAX_COORD),
949 Size2D::new(2.0 * MAX_COORD, 2.0 * MAX_COORD),
954 /// An enum that tries to avoid expensive transformation matrix calculations
955 /// when possible when dealing with non-perspective axis-aligned transformations.
956 #[derive(Debug, MallocSizeOf)]
957 pub enum FastTransform<Src, Dst> {
958 /// A simple offset, which can be used without doing any matrix math.
959 Offset(Vector2D<f32, Src>),
961 /// A 2D transformation with an inverse.
963 transform: Transform3D<f32, Src, Dst>,
964 inverse: Option<Transform3D<f32, Dst, Src>>,
969 impl<Src, Dst> Clone for FastTransform<Src, Dst> {
970 fn clone(&self) -> Self {
975 impl<Src, Dst> Copy for FastTransform<Src, Dst> { }
977 impl<Src, Dst> FastTransform<Src, Dst> {
978 pub fn identity() -> Self {
979 FastTransform::Offset(Vector2D::zero())
982 pub fn with_vector(offset: Vector2D<f32, Src>) -> Self {
983 FastTransform::Offset(offset)
986 pub fn with_scale_offset(scale_offset: ScaleOffset) -> Self {
987 if scale_offset.scale == Vector2D::new(1.0, 1.0) {
988 FastTransform::Offset(Vector2D::from_untyped(scale_offset.offset))
990 FastTransform::Transform {
991 transform: scale_offset.to_transform(),
992 inverse: Some(scale_offset.inverse().to_transform()),
999 pub fn with_transform(transform: Transform3D<f32, Src, Dst>) -> Self {
1000 if transform.is_simple_2d_translation() {
1001 return FastTransform::Offset(Vector2D::new(transform.m41, transform.m42));
1003 let inverse = transform.inverse();
1004 let is_2d = transform.is_2d();
1005 FastTransform::Transform { transform, inverse, is_2d}
1008 pub fn to_transform(&self) -> Cow<Transform3D<f32, Src, Dst>> {
1010 FastTransform::Offset(offset) => Cow::Owned(
1011 Transform3D::translation(offset.x, offset.y, 0.0)
1013 FastTransform::Transform { ref transform, .. } => Cow::Borrowed(transform),
1017 /// Return true if this is an identity transform
1019 pub fn is_identity(&self)-> bool {
1021 FastTransform::Offset(offset) => {
1022 offset == Vector2D::zero()
1024 FastTransform::Transform { ref transform, .. } => {
1025 *transform == Transform3D::identity()
1030 pub fn then<NewDst>(&self, other: &FastTransform<Dst, NewDst>) -> FastTransform<Src, NewDst> {
1032 FastTransform::Offset(offset) => match *other {
1033 FastTransform::Offset(other_offset) => {
1034 FastTransform::Offset(offset + other_offset * Scale::<_, _, Src>::new(1.0))
1036 FastTransform::Transform { transform: ref other_transform, .. } => {
1037 FastTransform::with_transform(
1039 .with_source::<Src>()
1040 .pre_translate(offset.to_3d())
1044 FastTransform::Transform { ref transform, ref inverse, is_2d } => match *other {
1045 FastTransform::Offset(other_offset) => {
1046 FastTransform::with_transform(
1048 .then_translate(other_offset.to_3d())
1049 .with_destination::<NewDst>()
1052 FastTransform::Transform { transform: ref other_transform, inverse: ref other_inverse, is_2d: other_is_2d } => {
1053 FastTransform::Transform {
1054 transform: transform.then(other_transform),
1055 inverse: inverse.as_ref().and_then(|self_inv|
1056 other_inverse.as_ref().map(|other_inv| other_inv.then(self_inv))
1058 is_2d: is_2d & other_is_2d,
1065 pub fn pre_transform<NewSrc>(
1067 other: &FastTransform<NewSrc, Src>
1068 ) -> FastTransform<NewSrc, Dst> {
1072 pub fn pre_translate(&self, other_offset: Vector2D<f32, Src>) -> Self {
1074 FastTransform::Offset(offset) =>
1075 FastTransform::Offset(offset + other_offset),
1076 FastTransform::Transform { transform, .. } =>
1077 FastTransform::with_transform(transform.pre_translate(other_offset.to_3d()))
1081 pub fn then_translate(&self, other_offset: Vector2D<f32, Dst>) -> Self {
1083 FastTransform::Offset(offset) => {
1084 FastTransform::Offset(offset + other_offset * Scale::<_, _, Src>::new(1.0))
1086 FastTransform::Transform { ref transform, .. } => {
1087 let transform = transform.then_translate(other_offset.to_3d());
1088 FastTransform::with_transform(transform)
1094 pub fn is_backface_visible(&self) -> bool {
1096 FastTransform::Offset(..) => false,
1097 FastTransform::Transform { inverse: None, .. } => false,
1098 //TODO: fix this properly by taking "det|M33| * det|M34| > 0"
1099 // see https://www.w3.org/Bugs/Public/show_bug.cgi?id=23014
1100 FastTransform::Transform { inverse: Some(ref inverse), .. } => inverse.m33 < 0.0,
1105 pub fn transform_point2d(&self, point: Point2D<f32, Src>) -> Option<Point2D<f32, Dst>> {
1107 FastTransform::Offset(offset) => {
1108 let new_point = point + offset;
1109 Some(Point2D::from_untyped(new_point.to_untyped()))
1111 FastTransform::Transform { ref transform, .. } => transform.transform_point2d(point),
1116 pub fn inverse(&self) -> Option<FastTransform<Dst, Src>> {
1118 FastTransform::Offset(offset) =>
1119 Some(FastTransform::Offset(Vector2D::new(-offset.x, -offset.y))),
1120 FastTransform::Transform { transform, inverse: Some(inverse), is_2d, } =>
1121 Some(FastTransform::Transform {
1123 inverse: Some(transform),
1126 FastTransform::Transform { inverse: None, .. } => None,
1132 impl<Src, Dst> From<Transform3D<f32, Src, Dst>> for FastTransform<Src, Dst> {
1133 fn from(transform: Transform3D<f32, Src, Dst>) -> Self {
1134 FastTransform::with_transform(transform)
1138 impl<Src, Dst> From<Vector2D<f32, Src>> for FastTransform<Src, Dst> {
1139 fn from(vector: Vector2D<f32, Src>) -> Self {
1140 FastTransform::with_vector(vector)
1144 pub type LayoutFastTransform = FastTransform<LayoutPixel, LayoutPixel>;
1145 pub type LayoutToWorldFastTransform = FastTransform<LayoutPixel, WorldPixel>;
1147 pub fn project_rect<F, T>(
1148 transform: &Transform3D<f32, F, T>,
1149 rect: &Rect<f32, F>,
1150 bounds: &Rect<f32, T>,
1151 ) -> Option<Rect<f32, T>>
1155 transform.transform_point2d_homogeneous(rect.origin),
1156 transform.transform_point2d_homogeneous(rect.top_right()),
1157 transform.transform_point2d_homogeneous(rect.bottom_left()),
1158 transform.transform_point2d_homogeneous(rect.bottom_right()),
1161 // Note: we only do the full frustum collision when the polygon approaches the camera plane.
1162 // Otherwise, it will be clamped to the screen bounds anyway.
1163 if homogens.iter().any(|h| h.w <= 0.0 || h.w.is_nan()) {
1164 let mut clipper = Clipper::new();
1165 let polygon = Polygon::from_rect(*rect, 1);
1167 let planes = match Clipper::<_, _, usize>::frustum_planes(
1171 Ok(planes) => planes,
1172 Err(..) => return None,
1175 for plane in planes {
1179 let results = clipper.clip(polygon);
1180 if results.is_empty() {
1184 Some(Rect::from_points(results
1186 // filter out parts behind the view plane
1187 .flat_map(|poly| &poly.points)
1189 let mut homo = transform.transform_point2d_homogeneous(p.to_2d());
1190 homo.w = homo.w.max(0.00000001); // avoid infinite values
1191 homo.to_point2d().unwrap()
1195 // we just checked for all the points to be in positive hemisphere, so `unwrap` is valid
1196 Some(Rect::from_points(&[
1197 homogens[0].to_point2d().unwrap(),
1198 homogens[1].to_point2d().unwrap(),
1199 homogens[2].to_point2d().unwrap(),
1200 homogens[3].to_point2d().unwrap(),
1205 pub fn raster_rect_to_device_pixels(
1207 device_pixel_scale: DevicePixelScale,
1209 let world_rect = rect * Scale::new(1.0);
1210 let device_rect = world_rect * device_pixel_scale;
1211 device_rect.round_out()
1214 /// Run the first callback over all elements in the array. If the callback returns true,
1215 /// the element is removed from the array and moved to a second callback.
1217 /// This is a simple implementation waiting for Vec::drain_filter to be stable.
1218 /// When that happens, code like:
1220 /// let filter = |op| {
1222 /// Enum::Foo | Enum::Bar => true,
1223 /// Enum::Baz => false,
1231 /// Enum::Foo => { foo(); }
1232 /// Enum::Bar => { bar(); }
1233 /// Enum::Baz => { unreachable!(); }
1238 /// Can be rewritten as:
1240 /// let filter = |op| {
1242 /// Enum::Foo | Enum::Bar => true,
1243 /// Enum::Baz => false,
1246 /// for op in ops.drain_filter(filter) {
1248 /// Enum::Foo => { foo(); }
1249 /// Enum::Bar => { bar(); }
1250 /// Enum::Baz => { unreachable!(); }
1254 /// See https://doc.rust-lang.org/std/vec/struct.Vec.html#method.drain_filter
1255 pub fn drain_filter<T, Filter, Action>(
1261 Filter: FnMut(&mut T) -> bool,
1265 while i != vec.len() {
1266 if filter(&mut vec[i]) {
1267 action(vec.remove(i));
1276 pub struct Recycler {
1277 pub num_allocations: usize,
1281 /// Maximum extra capacity that a recycled vector is allowed to have. If the actual capacity
1282 /// is larger, we re-allocate the vector storage with lower capacity.
1283 const MAX_EXTRA_CAPACITY_PERCENT: usize = 200;
1284 /// Minimum extra capacity to keep when re-allocating the vector storage.
1285 const MIN_EXTRA_CAPACITY_PERCENT: usize = 20;
1286 /// Minimum sensible vector length to consider for re-allocation.
1287 const MIN_VECTOR_LENGTH: usize = 16;
1289 pub fn new() -> Self {
1295 /// Clear a vector for re-use, while retaining the backing memory buffer. May shrink the buffer
1296 /// if it's currently much larger than was actually used.
1297 pub fn recycle_vec<T>(&mut self, vec: &mut Vec<T>) {
1298 let extra_capacity = (vec.capacity() - vec.len()) * 100 / vec.len().max(Self::MIN_VECTOR_LENGTH);
1300 if extra_capacity > Self::MAX_EXTRA_CAPACITY_PERCENT {
1301 // Reduce capacity of the buffer if it is a lot larger than it needs to be. This prevents
1302 // a frame with exceptionally large allocations to cause subsequent frames to retain
1303 // more memory than they need.
1304 //TODO: use `shrink_to` when it's stable
1305 *vec = Vec::with_capacity(vec.len() + vec.len() * Self::MIN_EXTRA_CAPACITY_PERCENT / 100);
1306 self.num_allocations += 1;
1313 /// Record the size of a data structure to preallocate a similar size
1314 /// at the next frame and avoid growing it too many time.
1315 #[derive(Copy, Clone, Debug)]
1316 pub struct Preallocator {
1321 pub fn new(initial_size: usize) -> Self {
1327 /// Record the size of a vector to preallocate it the next frame.
1328 pub fn record_vec<T>(&mut self, vec: &Vec<T>) {
1329 let len = vec.len();
1330 if len > self.size {
1333 self.size = (self.size + len) / 2;
1337 /// The size that we'll preallocate the vector with.
1338 pub fn preallocation_size(&self) -> usize {
1339 // Round up to multiple of 16 to avoid small tiny
1340 // variations causing reallocations.
1341 (self.size + 15) & !15
1344 /// Preallocate vector storage.
1346 /// The preallocated amount depends on the length recorded in the last
1347 /// record_vec call.
1348 pub fn preallocate_vec<T>(&self, vec: &mut Vec<T>) {
1349 let len = vec.len();
1350 let cap = self.preallocation_size();
1352 vec.reserve(cap - len);
1357 impl Default for Preallocator {
1358 fn default() -> Self {
1363 /// Arc wrapper to support measurement via MallocSizeOf.
1365 /// Memory reporting for Arcs is tricky because of the risk of double-counting.
1366 /// One way to measure them is to keep a table of pointers that have already been
1367 /// traversed. The other way is to use knowledge of the program structure to
1368 /// identify which Arc instances should be measured and which should be skipped to
1369 /// avoid double-counting.
1371 /// This struct implements the second approach. It identifies the "main" pointer
1372 /// to the Arc-ed resource, and measures the buffer as if it were an owned pointer.
1373 /// The programmer should ensure that there is at most one PrimaryArc for a given
1374 /// underlying ArcInner.
1375 #[cfg_attr(feature = "capture", derive(Serialize))]
1376 #[cfg_attr(feature = "replay", derive(Deserialize))]
1377 #[derive(Clone, Debug, Hash, PartialEq, Eq)]
1378 pub struct PrimaryArc<T>(pub Arc<T>);
1380 impl<T> ::std::ops::Deref for PrimaryArc<T> {
1381 type Target = Arc<T>;
1384 fn deref(&self) -> &Arc<T> {
1389 impl<T> MallocShallowSizeOf for PrimaryArc<T> {
1390 fn shallow_size_of(&self, ops: &mut MallocSizeOfOps) -> usize {
1392 // This is a bit sketchy, but std::sync::Arc doesn't expose the
1394 let raw_arc_ptr: *const Arc<T> = &self.0;
1395 let raw_ptr_ptr: *const *const c_void = raw_arc_ptr as _;
1396 let raw_ptr = *raw_ptr_ptr;
1397 (ops.size_of_op)(raw_ptr)
1402 impl<T: MallocSizeOf> MallocSizeOf for PrimaryArc<T> {
1403 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize {
1404 self.shallow_size_of(ops) + (**self).size_of(ops)
1408 /// Computes the scale factors of this matrix; that is,
1409 /// the amounts each basis vector is scaled by.
1411 /// This code comes from gecko gfx/2d/Matrix.h with the following
1414 /// * Removed `xMajor` parameter.
1415 pub fn scale_factors<Src, Dst>(
1416 mat: &Transform3D<f32, Src, Dst>
1418 // Determinant is just of the 2D component.
1419 let det = mat.m11 * mat.m22 - mat.m12 * mat.m21;
1425 let det = det.abs();
1427 let major = (mat.m11 * mat.m11 + mat.m12 * mat.m12).sqrt();
1428 let minor = if major != 0.0 { det / major } else { 0.0 };
1433 /// Clamp scaling factor to a power of two.
1435 /// This code comes from gecko gfx/thebes/gfxUtils.cpp with the following
1438 /// * logs are taken in base 2 instead of base e.
1439 pub fn clamp_to_scale_factor(val: f32, round_down: bool) -> f32 {
1440 // Arbitary scale factor limitation. We can increase this
1441 // for better scaling performance at the cost of worse
1443 const SCALE_RESOLUTION: f32 = 2.0;
1445 // Negative scaling is just a flip and irrelevant to
1446 // our resolution calculation.
1447 let val = val.abs();
1449 let (val, inverse) = if val < 1.0 {
1455 let power = val.log2() / SCALE_RESOLUTION.log2();
1457 // If power is within 1e-5 of an integer, round to nearest to
1458 // prevent floating point errors, otherwise round up to the
1459 // next integer value.
1460 let power = if (power - power.round()).abs() < 1e-5 {
1462 } else if inverse != round_down {
1463 // Use floor when we are either inverted or rounding down, but
1467 // Otherwise, ceil when we are not inverted and not rounding
1468 // down, or we are inverted and rounding down.
1472 let scale = SCALE_RESOLUTION.powf(power);
1481 /// Rounds a value up to the nearest multiple of mul
1482 pub fn round_up_to_multiple(val: usize, mul: NonZeroUsize) -> usize {
1483 match val % mul.get() {
1485 rem => val - rem + mul.get(),
1491 macro_rules! c_str {
1494 std::ffi::CStr::from_ptr(concat!($lit, "\0").as_ptr()
1495 as *const std::os::raw::c_char)
1500 // Find a rectangle that is contained by the sum of r1 and r2.
1501 pub fn conservative_union_rect<U>(r1: &Rect<f32, U>, r2: &Rect<f32, U>) -> Rect<f32, U> {
1502 // +---+---+ +--+-+--+
1505 // +---+---+ +--+-+--+
1506 if r1.origin.y == r2.origin.y && r1.size.height == r2.size.height {
1507 if r2.min_x() <= r1.max_x() && r2.max_x() >= r1.min_x() {
1508 let origin_x = f32::min(r1.origin.x, r2.origin.x);
1509 let width = f32::max(r1.max_x(), r2.max_x()) - origin_x;
1512 origin: point2(origin_x, r1.origin.y),
1513 size: size2(width, r1.size.height),
1525 if r1.origin.x == r2.origin.x && r1.size.width == r2.size.width {
1526 if r2.min_y() <= r1.max_y() && r2.max_y() >= r1.min_y() {
1527 let origin_y = f32::min(r1.origin.y, r2.origin.y);
1528 let height = f32::max(r1.max_y(), r2.max_y()) - origin_y;
1531 origin: point2(r1.origin.x, origin_y),
1532 size: size2(r1.size.width, height),
1537 if r1.area() >= r2.area() { *r1 } else {*r2 }
1541 fn test_conservative_union_rect() {
1543 let r = conservative_union_rect(
1544 &LayoutRect { origin: point2(1.0, 2.0), size: size2(3.0, 4.0) },
1545 &LayoutRect { origin: point2(4.0, 2.0), size: size2(5.0, 4.0) },
1547 assert_eq!(r, LayoutRect { origin: point2(1.0, 2.0), size: size2(8.0, 4.0) });
1549 let r = conservative_union_rect(
1550 &LayoutRect { origin: point2(4.0, 2.0), size: size2(5.0, 4.0) },
1551 &LayoutRect { origin: point2(1.0, 2.0), size: size2(3.0, 4.0) },
1553 assert_eq!(r, LayoutRect { origin: point2(1.0, 2.0), size: size2(8.0, 4.0) });
1555 // Averlapping adjacent, x axis
1556 let r = conservative_union_rect(
1557 &LayoutRect { origin: point2(1.0, 2.0), size: size2(3.0, 4.0) },
1558 &LayoutRect { origin: point2(3.0, 2.0), size: size2(5.0, 4.0) },
1560 assert_eq!(r, LayoutRect { origin: point2(1.0, 2.0), size: size2(7.0, 4.0) });
1562 let r = conservative_union_rect(
1563 &LayoutRect { origin: point2(5.0, 2.0), size: size2(3.0, 4.0) },
1564 &LayoutRect { origin: point2(1.0, 2.0), size: size2(5.0, 4.0) },
1566 assert_eq!(r, LayoutRect { origin: point2(1.0, 2.0), size: size2(7.0, 4.0) });
1568 // Adjacent but not touching, x axis
1569 let r = conservative_union_rect(
1570 &LayoutRect { origin: point2(1.0, 2.0), size: size2(3.0, 4.0) },
1571 &LayoutRect { origin: point2(6.0, 2.0), size: size2(5.0, 4.0) },
1573 assert_eq!(r, LayoutRect { origin: point2(6.0, 2.0), size: size2(5.0, 4.0) });
1575 let r = conservative_union_rect(
1576 &LayoutRect { origin: point2(1.0, 2.0), size: size2(3.0, 4.0) },
1577 &LayoutRect { origin: point2(-6.0, 2.0), size: size2(1.0, 4.0) },
1579 assert_eq!(r, LayoutRect { origin: point2(1.0, 2.0), size: size2(3.0, 4.0) });
1583 let r = conservative_union_rect(
1584 &LayoutRect { origin: point2(1.0, 2.0), size: size2(3.0, 4.0) },
1585 &LayoutRect { origin: point2(1.0, 6.0), size: size2(3.0, 4.0) },
1587 assert_eq!(r, LayoutRect { origin: point2(1.0, 2.0), size: size2(3.0, 8.0) });
1589 let r = conservative_union_rect(
1590 &LayoutRect { origin: point2(1.0, 5.0), size: size2(3.0, 4.0) },
1591 &LayoutRect { origin: point2(1.0, 1.0), size: size2(3.0, 4.0) },
1593 assert_eq!(r, LayoutRect { origin: point2(1.0, 1.0), size: size2(3.0, 8.0) });
1595 // Averlapping adjacent, y axis
1596 let r = conservative_union_rect(
1597 &LayoutRect { origin: point2(1.0, 2.0), size: size2(3.0, 4.0) },
1598 &LayoutRect { origin: point2(1.0, 3.0), size: size2(3.0, 4.0) },
1600 assert_eq!(r, LayoutRect { origin: point2(1.0, 2.0), size: size2(3.0, 5.0) });
1602 let r = conservative_union_rect(
1603 &LayoutRect { origin: point2(1.0, 4.0), size: size2(3.0, 4.0) },
1604 &LayoutRect { origin: point2(1.0, 2.0), size: size2(3.0, 4.0) },
1606 assert_eq!(r, LayoutRect { origin: point2(1.0, 2.0), size: size2(3.0, 6.0) });
1608 // Adjacent but not touching, y axis
1609 let r = conservative_union_rect(
1610 &LayoutRect { origin: point2(1.0, 2.0), size: size2(3.0, 4.0) },
1611 &LayoutRect { origin: point2(1.0, 10.0), size: size2(3.0, 5.0) },
1613 assert_eq!(r, LayoutRect { origin: point2(1.0, 10.0), size: size2(3.0, 5.0) });
1615 let r = conservative_union_rect(
1616 &LayoutRect { origin: point2(1.0, 5.0), size: size2(3.0, 4.0) },
1617 &LayoutRect { origin: point2(1.0, 0.0), size: size2(3.0, 3.0) },
1619 assert_eq!(r, LayoutRect { origin: point2(1.0, 5.0), size: size2(3.0, 4.0) });
1623 let r = conservative_union_rect(
1624 &LayoutRect { origin: point2(1.0, 2.0), size: size2(3.0, 4.0) },
1625 &LayoutRect { origin: point2(0.0, 1.0), size: size2(10.0, 11.0) },
1627 assert_eq!(r, LayoutRect { origin: point2(0.0, 1.0), size: size2(10.0, 11.0) });
1629 let r = conservative_union_rect(
1630 &LayoutRect { origin: point2(0.0, 1.0), size: size2(10.0, 11.0) },
1631 &LayoutRect { origin: point2(1.0, 2.0), size: size2(3.0, 4.0) },
1633 assert_eq!(r, LayoutRect { origin: point2(0.0, 1.0), size: size2(10.0, 11.0) });
1636 /// This is inspired by the `weak-table` crate.
1637 /// It holds a Vec of weak pointers that are garbage collected as the Vec
1638 pub struct WeakTable {
1639 inner: Vec<std::sync::Weak<Vec<u8>>>
1643 pub fn new() -> WeakTable {
1644 WeakTable { inner: Vec::new() }
1646 pub fn insert(&mut self, x: std::sync::Weak<Vec<u8>>) {
1647 if self.inner.len() == self.inner.capacity() {
1648 self.remove_expired();
1650 // We want to make sure that we change capacity()
1651 // even if remove_expired() removes some entries
1652 // so that we don't repeatedly hit remove_expired()
1653 if self.inner.len() * 3 < self.inner.capacity() {
1654 // We use a different multiple for shrinking then
1655 // expanding so that we we don't accidentally
1657 self.inner.shrink_to_fit();
1659 // Otherwise double our size
1660 self.inner.reserve(self.inner.len())
1666 fn remove_expired(&mut self) {
1667 self.inner.retain(|x| x.strong_count() > 0)
1670 pub fn iter(&self) -> impl Iterator<Item = Arc<Vec<u8>>> + '_ {
1671 self.inner.iter().filter_map(|x| x.upgrade())
1677 let mut tbl = WeakTable::new();
1678 let mut things = Vec::new();
1679 let target_count = 50;
1680 for _ in 0..target_count {
1681 things.push(Arc::new(vec![4]));
1684 tbl.insert(Arc::downgrade(i))
1686 assert_eq!(tbl.inner.len(), target_count);
1688 assert_eq!(tbl.iter().count(), 0);
1690 // make sure that we shrink the table if it gets too big
1691 // by adding a bunch of dead items
1692 for _ in 0..target_count*2 {
1693 tbl.insert(Arc::downgrade(&Arc::new(vec![5])))
1695 assert!(tbl.inner.capacity() <= 4);