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 use api::BorderRadius;
6 use api::units::*;
7 use euclid::{Point2D, Rect, Box2D, Size2D, Vector2D, point2};
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};
12 use std::borrow::Cow;
13 use std::num::NonZeroUsize;
14 use std::os::raw::c_void;
15 use std::sync::Arc;
16 use std::mem::replace;
17
18
19 // Matches the definition of SK_ScalarNearlyZero in Skia.
20 const NEARLY_ZERO: f32 = 1.0 / 4096.0;
21
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> {
25 vec: &'a mut Vec<T>,
26 index: usize,
27 }
28
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.
33 #[inline(always)]
init(self, value: T) -> usize34 pub fn init(self, value: T) -> usize {
35 unsafe {
36 ptr::write(self.vec.as_mut_ptr().add(self.index), value);
37 self.vec.set_len(self.index + 1);
38 }
39 self.index
40 }
41 }
42
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>),
46 Occupied(&'a mut T),
47 }
48
49 impl<'a, T> VecEntry<'a, T> {
50 #[inline(always)]
set(self, value: T)51 pub fn set(self, value: T) {
52 match self {
53 VecEntry::Vacant(alloc) => { alloc.init(value); }
54 VecEntry::Occupied(slot) => { *slot = value; }
55 }
56 }
57 }
58
59 pub trait VecHelper<T> {
60 /// Growns the vector by a single entry, returning the allocation.
alloc(&mut self) -> Allocation<T>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.
entry(&mut self, index: usize) -> VecEntry<T>64 fn entry(&mut self, index: usize) -> VecEntry<T>;
65
66 /// Equivalent to `mem::replace(&mut vec, Vec::new())`
take(&mut self) -> Self67 fn take(&mut self) -> Self;
68
69 /// Call clear and return self (useful for chaining with calls that move the vector).
cleared(self) -> Self70 fn cleared(self) -> Self;
71
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.
take_and_preallocate(&mut self) -> Self75 fn take_and_preallocate(&mut self) -> Self;
76 }
77
78 impl<T> VecHelper<T> for Vec<T> {
alloc(&mut self) -> Allocation<T>79 fn alloc(&mut self) -> Allocation<T> {
80 let index = self.len();
81 if self.capacity() == index {
82 self.reserve(1);
83 }
84 Allocation {
85 vec: self,
86 index,
87 }
88 }
89
entry(&mut self, index: usize) -> VecEntry<T>90 fn entry(&mut self, index: usize) -> VecEntry<T> {
91 if index < self.len() {
92 VecEntry::Occupied(unsafe {
93 self.get_unchecked_mut(index)
94 })
95 } else {
96 assert_eq!(index, self.len());
97 VecEntry::Vacant(self.alloc())
98 }
99 }
100
take(&mut self) -> Self101 fn take(&mut self) -> Self {
102 replace(self, Vec::new())
103 }
104
cleared(mut self) -> Self105 fn cleared(mut self) -> Self {
106 self.clear();
107
108 self
109 }
110
take_and_preallocate(&mut self) -> Self111 fn take_and_preallocate(&mut self) -> Self {
112 let len = self.len();
113 if len == 0 {
114 self.clear();
115 return Vec::new();
116 }
117 replace(self, Vec::with_capacity(len + 8))
118 }
119 }
120
121
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 #[cfg_attr(feature = "replay", derive(Deserialize))]
132 pub struct ScaleOffset {
133 pub scale: default::Vector2D<f32>,
134 pub offset: default::Vector2D<f32>,
135 }
136
137 impl ScaleOffset {
identity() -> Self138 pub fn identity() -> Self {
139 ScaleOffset {
140 scale: Vector2D::new(1.0, 1.0),
141 offset: Vector2D::zero(),
142 }
143 }
144
145 // Construct a ScaleOffset from a transform. Returns
146 // None if the matrix is not a pure scale / translation.
from_transform<F, T>( m: &Transform3D<f32, F, T>, ) -> Option<ScaleOffset>147 pub fn from_transform<F, T>(
148 m: &Transform3D<f32, F, T>,
149 ) -> Option<ScaleOffset> {
150
151 // To check that we have a pure scale / translation:
152 // Every field must match an identity matrix, except:
153 // - Any value present in tx,ty
154 // - Any value present in sx,sy
155
156 if m.m12.abs() > NEARLY_ZERO ||
157 m.m13.abs() > NEARLY_ZERO ||
158 m.m14.abs() > NEARLY_ZERO ||
159 m.m21.abs() > NEARLY_ZERO ||
160 m.m23.abs() > NEARLY_ZERO ||
161 m.m24.abs() > NEARLY_ZERO ||
162 m.m31.abs() > NEARLY_ZERO ||
163 m.m32.abs() > NEARLY_ZERO ||
164 (m.m33 - 1.0).abs() > NEARLY_ZERO ||
165 m.m34.abs() > NEARLY_ZERO ||
166 m.m43.abs() > NEARLY_ZERO ||
167 (m.m44 - 1.0).abs() > NEARLY_ZERO {
168 return None;
169 }
170
171 Some(ScaleOffset {
172 scale: Vector2D::new(m.m11, m.m22),
173 offset: Vector2D::new(m.m41, m.m42),
174 })
175 }
176
from_offset(offset: default::Vector2D<f32>) -> Self177 pub fn from_offset(offset: default::Vector2D<f32>) -> Self {
178 ScaleOffset {
179 scale: Vector2D::new(1.0, 1.0),
180 offset,
181 }
182 }
183
from_scale(scale: default::Vector2D<f32>) -> Self184 pub fn from_scale(scale: default::Vector2D<f32>) -> Self {
185 ScaleOffset {
186 scale,
187 offset: Vector2D::new(0.0, 0.0),
188 }
189 }
190
inverse(&self) -> Self191 pub fn inverse(&self) -> Self {
192 ScaleOffset {
193 scale: Vector2D::new(
194 1.0 / self.scale.x,
195 1.0 / self.scale.y,
196 ),
197 offset: Vector2D::new(
198 -self.offset.x / self.scale.x,
199 -self.offset.y / self.scale.y,
200 ),
201 }
202 }
203
offset(&self, offset: default::Vector2D<f32>) -> Self204 pub fn offset(&self, offset: default::Vector2D<f32>) -> Self {
205 self.accumulate(
206 &ScaleOffset {
207 scale: Vector2D::new(1.0, 1.0),
208 offset,
209 }
210 )
211 }
212
scale(&self, scale: f32) -> Self213 pub fn scale(&self, scale: f32) -> Self {
214 self.accumulate(
215 &ScaleOffset {
216 scale: Vector2D::new(scale, scale),
217 offset: Vector2D::zero(),
218 }
219 )
220 }
221
222 /// Produce a ScaleOffset that includes both self and other.
223 /// The 'self' ScaleOffset is applied after other.
224 /// This is equivalent to `Transform3D::pre_transform`.
accumulate(&self, other: &ScaleOffset) -> Self225 pub fn accumulate(&self, other: &ScaleOffset) -> Self {
226 ScaleOffset {
227 scale: Vector2D::new(
228 self.scale.x * other.scale.x,
229 self.scale.y * other.scale.y,
230 ),
231 offset: Vector2D::new(
232 self.offset.x + self.scale.x * other.offset.x,
233 self.offset.y + self.scale.y * other.offset.y,
234 ),
235 }
236 }
237
map_rect<F, T>(&self, rect: &Box2D<f32, F>) -> Box2D<f32, T>238 pub fn map_rect<F, T>(&self, rect: &Box2D<f32, F>) -> Box2D<f32, T> {
239 // TODO(gw): The logic below can return an unexpected result if the supplied
240 // rect is invalid (has size < 0). Since Gecko currently supplied
241 // invalid rects in some cases, adding a max(0) here ensures that
242 // mapping an invalid rect retains the property that rect.is_empty()
243 // will return true (the mapped rect output will have size 0 instead
244 // of a negative size). In future we could catch / assert / fix
245 // these invalid rects earlier, and assert here instead.
246
247 let w = rect.width().max(0.0);
248 let h = rect.height().max(0.0);
249
250 let mut x0 = rect.min.x * self.scale.x + self.offset.x;
251 let mut y0 = rect.min.y * self.scale.y + self.offset.y;
252
253 let mut sx = w * self.scale.x;
254 let mut sy = h * self.scale.y;
255 // Handle negative scale. Previously, branchless float math was used to find the
256 // min / max vertices and size. However, that sequence of operations was producind
257 // additional floating point accuracy on android emulator builds, causing one test
258 // to fail an assert. Instead, we retain the same math as previously, and adjust
259 // the origin / size if required.
260
261 if self.scale.x < 0.0 {
262 x0 += sx;
263 sx = -sx;
264 }
265 if self.scale.y < 0.0 {
266 y0 += sy;
267 sy = -sy;
268 }
269
270 Box2D::from_origin_and_size(
271 Point2D::new(x0, y0),
272 Size2D::new(sx, sy),
273 )
274 }
275
unmap_rect<F, T>(&self, rect: &Box2D<f32, F>) -> Box2D<f32, T>276 pub fn unmap_rect<F, T>(&self, rect: &Box2D<f32, F>) -> Box2D<f32, T> {
277 // TODO(gw): The logic below can return an unexpected result if the supplied
278 // rect is invalid (has size < 0). Since Gecko currently supplied
279 // invalid rects in some cases, adding a max(0) here ensures that
280 // mapping an invalid rect retains the property that rect.is_empty()
281 // will return true (the mapped rect output will have size 0 instead
282 // of a negative size). In future we could catch / assert / fix
283 // these invalid rects earlier, and assert here instead.
284
285 let w = rect.width().max(0.0);
286 let h = rect.height().max(0.0);
287
288 let mut x0 = (rect.min.x - self.offset.x) / self.scale.x;
289 let mut y0 = (rect.min.y - self.offset.y) / self.scale.y;
290
291 let mut sx = w / self.scale.x;
292 let mut sy = h / self.scale.y;
293
294 // Handle negative scale. Previously, branchless float math was used to find the
295 // min / max vertices and size. However, that sequence of operations was producind
296 // additional floating point accuracy on android emulator builds, causing one test
297 // to fail an assert. Instead, we retain the same math as previously, and adjust
298 // the origin / size if required.
299
300 if self.scale.x < 0.0 {
301 x0 += sx;
302 sx = -sx;
303 }
304 if self.scale.y < 0.0 {
305 y0 += sy;
306 sy = -sy;
307 }
308
309 Box2D::from_origin_and_size(
310 Point2D::new(x0, y0),
311 Size2D::new(sx, sy),
312 )
313 }
314
map_vector<F, T>(&self, vector: &Vector2D<f32, F>) -> Vector2D<f32, T>315 pub fn map_vector<F, T>(&self, vector: &Vector2D<f32, F>) -> Vector2D<f32, T> {
316 Vector2D::new(
317 vector.x * self.scale.x,
318 vector.y * self.scale.y,
319 )
320 }
321
unmap_vector<F, T>(&self, vector: &Vector2D<f32, F>) -> Vector2D<f32, T>322 pub fn unmap_vector<F, T>(&self, vector: &Vector2D<f32, F>) -> Vector2D<f32, T> {
323 Vector2D::new(
324 vector.x / self.scale.x,
325 vector.y / self.scale.y,
326 )
327 }
328
map_point<F, T>(&self, point: &Point2D<f32, F>) -> Point2D<f32, T>329 pub fn map_point<F, T>(&self, point: &Point2D<f32, F>) -> Point2D<f32, T> {
330 Point2D::new(
331 point.x * self.scale.x + self.offset.x,
332 point.y * self.scale.y + self.offset.y,
333 )
334 }
335
unmap_point<F, T>(&self, point: &Point2D<f32, F>) -> Point2D<f32, T>336 pub fn unmap_point<F, T>(&self, point: &Point2D<f32, F>) -> Point2D<f32, T> {
337 Point2D::new(
338 (point.x - self.offset.x) / self.scale.x,
339 (point.y - self.offset.y) / self.scale.y,
340 )
341 }
342
to_transform<F, T>(&self) -> Transform3D<f32, F, T>343 pub fn to_transform<F, T>(&self) -> Transform3D<f32, F, T> {
344 Transform3D::new(
345 self.scale.x,
346 0.0,
347 0.0,
348 0.0,
349
350 0.0,
351 self.scale.y,
352 0.0,
353 0.0,
354
355 0.0,
356 0.0,
357 1.0,
358 0.0,
359
360 self.offset.x,
361 self.offset.y,
362 0.0,
363 1.0,
364 )
365 }
366 }
367
368 // TODO: Implement these in euclid!
369 pub trait MatrixHelpers<Src, Dst> {
370 /// A port of the preserves2dAxisAlignment function in Skia.
371 /// Defined in the SkMatrix44 class.
preserves_2d_axis_alignment(&self) -> bool372 fn preserves_2d_axis_alignment(&self) -> bool;
has_perspective_component(&self) -> bool373 fn has_perspective_component(&self) -> bool;
has_2d_inverse(&self) -> bool374 fn has_2d_inverse(&self) -> bool;
375 /// Check if the matrix post-scaling on either the X or Y axes could cause geometry
376 /// transformed by this matrix to have scaling exceeding the supplied limit.
exceeds_2d_scale(&self, limit: f64) -> bool377 fn exceeds_2d_scale(&self, limit: f64) -> bool;
inverse_project(&self, target: &Point2D<f32, Dst>) -> Option<Point2D<f32, Src>>378 fn inverse_project(&self, target: &Point2D<f32, Dst>) -> Option<Point2D<f32, Src>>;
inverse_rect_footprint(&self, rect: &Box2D<f32, Dst>) -> Option<Box2D<f32, Src>>379 fn inverse_rect_footprint(&self, rect: &Box2D<f32, Dst>) -> Option<Box2D<f32, Src>>;
transform_kind(&self) -> TransformedRectKind380 fn transform_kind(&self) -> TransformedRectKind;
is_simple_translation(&self) -> bool381 fn is_simple_translation(&self) -> bool;
is_simple_2d_translation(&self) -> bool382 fn is_simple_2d_translation(&self) -> bool;
is_2d_scale_translation(&self) -> bool383 fn is_2d_scale_translation(&self) -> bool;
384 /// Return the determinant of the 2D part of the matrix.
determinant_2d(&self) -> f32385 fn determinant_2d(&self) -> f32;
386 /// This function returns a point in the `Src` space that projects into zero XY.
387 /// It ignores the Z coordinate and is usable for "flattened" transformations,
388 /// since they are not generally inversible.
inverse_project_2d_origin(&self) -> Option<Point2D<f32, Src>>389 fn inverse_project_2d_origin(&self) -> Option<Point2D<f32, Src>>;
390 /// Turn Z transformation into identity. This is useful when crossing "flat"
391 /// transform styled stacking contexts upon traversing the coordinate systems.
flatten_z_output(&mut self)392 fn flatten_z_output(&mut self);
393
cast_unit<NewSrc, NewDst>(&self) -> Transform3D<f32, NewSrc, NewDst>394 fn cast_unit<NewSrc, NewDst>(&self) -> Transform3D<f32, NewSrc, NewDst>;
395 }
396
397 impl<Src, Dst> MatrixHelpers<Src, Dst> for Transform3D<f32, Src, Dst> {
preserves_2d_axis_alignment(&self) -> bool398 fn preserves_2d_axis_alignment(&self) -> bool {
399 if self.m14 != 0.0 || self.m24 != 0.0 {
400 return false;
401 }
402
403 let mut col0 = 0;
404 let mut col1 = 0;
405 let mut row0 = 0;
406 let mut row1 = 0;
407
408 if self.m11.abs() > NEARLY_ZERO {
409 col0 += 1;
410 row0 += 1;
411 }
412 if self.m12.abs() > NEARLY_ZERO {
413 col1 += 1;
414 row0 += 1;
415 }
416 if self.m21.abs() > NEARLY_ZERO {
417 col0 += 1;
418 row1 += 1;
419 }
420 if self.m22.abs() > NEARLY_ZERO {
421 col1 += 1;
422 row1 += 1;
423 }
424
425 col0 < 2 && col1 < 2 && row0 < 2 && row1 < 2
426 }
427
has_perspective_component(&self) -> bool428 fn has_perspective_component(&self) -> bool {
429 self.m14.abs() > NEARLY_ZERO ||
430 self.m24.abs() > NEARLY_ZERO ||
431 self.m34.abs() > NEARLY_ZERO ||
432 (self.m44 - 1.0).abs() > NEARLY_ZERO
433 }
434
has_2d_inverse(&self) -> bool435 fn has_2d_inverse(&self) -> bool {
436 self.determinant_2d() != 0.0
437 }
438
exceeds_2d_scale(&self, limit: f64) -> bool439 fn exceeds_2d_scale(&self, limit: f64) -> bool {
440 let limit2 = (limit * limit) as f32;
441 self.m11 * self.m11 + self.m12 * self.m12 > limit2 ||
442 self.m21 * self.m21 + self.m22 * self.m22 > limit2
443 }
444
445 /// Find out a point in `Src` that would be projected into the `target`.
inverse_project(&self, target: &Point2D<f32, Dst>) -> Option<Point2D<f32, Src>>446 fn inverse_project(&self, target: &Point2D<f32, Dst>) -> Option<Point2D<f32, Src>> {
447 // form the linear equation for the hyperplane intersection
448 let m = Transform2D::<f32, Src, Dst>::new(
449 self.m11 - target.x * self.m14, self.m12 - target.y * self.m14,
450 self.m21 - target.x * self.m24, self.m22 - target.y * self.m24,
451 self.m41 - target.x * self.m44, self.m42 - target.y * self.m44,
452 );
453 let inv = m.inverse()?;
454 // we found the point, now check if it maps to the positive hemisphere
455 if inv.m31 * self.m14 + inv.m32 * self.m24 + self.m44 > 0.0 {
456 Some(Point2D::new(inv.m31, inv.m32))
457 } else {
458 None
459 }
460 }
461
inverse_rect_footprint(&self, rect: &Box2D<f32, Dst>) -> Option<Box2D<f32, Src>>462 fn inverse_rect_footprint(&self, rect: &Box2D<f32, Dst>) -> Option<Box2D<f32, Src>> {
463 Some(Box2D::from_points(&[
464 self.inverse_project(&rect.top_left())?,
465 self.inverse_project(&rect.top_right())?,
466 self.inverse_project(&rect.bottom_left())?,
467 self.inverse_project(&rect.bottom_right())?,
468 ]))
469 }
470
transform_kind(&self) -> TransformedRectKind471 fn transform_kind(&self) -> TransformedRectKind {
472 if self.preserves_2d_axis_alignment() {
473 TransformedRectKind::AxisAligned
474 } else {
475 TransformedRectKind::Complex
476 }
477 }
478
is_simple_translation(&self) -> bool479 fn is_simple_translation(&self) -> bool {
480 if (self.m11 - 1.0).abs() > NEARLY_ZERO ||
481 (self.m22 - 1.0).abs() > NEARLY_ZERO ||
482 (self.m33 - 1.0).abs() > NEARLY_ZERO ||
483 (self.m44 - 1.0).abs() > NEARLY_ZERO {
484 return false;
485 }
486
487 self.m12.abs() < NEARLY_ZERO && self.m13.abs() < NEARLY_ZERO &&
488 self.m14.abs() < NEARLY_ZERO && self.m21.abs() < NEARLY_ZERO &&
489 self.m23.abs() < NEARLY_ZERO && self.m24.abs() < NEARLY_ZERO &&
490 self.m31.abs() < NEARLY_ZERO && self.m32.abs() < NEARLY_ZERO &&
491 self.m34.abs() < NEARLY_ZERO
492 }
493
is_simple_2d_translation(&self) -> bool494 fn is_simple_2d_translation(&self) -> bool {
495 if !self.is_simple_translation() {
496 return false;
497 }
498
499 self.m43.abs() < NEARLY_ZERO
500 }
501
502 /* is this...
503 * X 0 0 0
504 * 0 Y 0 0
505 * 0 0 1 0
506 * a b 0 1
507 */
is_2d_scale_translation(&self) -> bool508 fn is_2d_scale_translation(&self) -> bool {
509 (self.m33 - 1.0).abs() < NEARLY_ZERO &&
510 (self.m44 - 1.0).abs() < NEARLY_ZERO &&
511 self.m12.abs() < NEARLY_ZERO && self.m13.abs() < NEARLY_ZERO && self.m14.abs() < NEARLY_ZERO &&
512 self.m21.abs() < NEARLY_ZERO && self.m23.abs() < NEARLY_ZERO && self.m24.abs() < NEARLY_ZERO &&
513 self.m31.abs() < NEARLY_ZERO && self.m32.abs() < NEARLY_ZERO && self.m34.abs() < NEARLY_ZERO &&
514 self.m43.abs() < NEARLY_ZERO
515 }
516
determinant_2d(&self) -> f32517 fn determinant_2d(&self) -> f32 {
518 self.m11 * self.m22 - self.m12 * self.m21
519 }
520
inverse_project_2d_origin(&self) -> Option<Point2D<f32, Src>>521 fn inverse_project_2d_origin(&self) -> Option<Point2D<f32, Src>> {
522 let det = self.determinant_2d();
523 if det != 0.0 {
524 let x = (self.m21 * self.m42 - self.m41 * self.m22) / det;
525 let y = (self.m12 * self.m41 - self.m11 * self.m42) / det;
526 Some(Point2D::new(x, y))
527 } else {
528 None
529 }
530 }
531
flatten_z_output(&mut self)532 fn flatten_z_output(&mut self) {
533 self.m13 = 0.0;
534 self.m23 = 0.0;
535 self.m33 = 1.0;
536 self.m43 = 0.0;
537 //Note: we used to zero out m3? as well, see "reftests/flatten-all-flat.yaml" test
538 }
539
cast_unit<NewSrc, NewDst>(&self) -> Transform3D<f32, NewSrc, NewDst>540 fn cast_unit<NewSrc, NewDst>(&self) -> Transform3D<f32, NewSrc, NewDst> {
541 Transform3D::new(
542 self.m11, self.m12, self.m13, self.m14,
543 self.m21, self.m22, self.m23, self.m24,
544 self.m31, self.m32, self.m33, self.m34,
545 self.m41, self.m42, self.m43, self.m44,
546 )
547 }
548 }
549
550 pub trait PointHelpers<U>
551 where
552 Self: Sized,
553 {
snap(&self) -> Self554 fn snap(&self) -> Self;
555 }
556
557 impl<U> PointHelpers<U> for Point2D<f32, U> {
snap(&self) -> Self558 fn snap(&self) -> Self {
559 Point2D::new(
560 (self.x + 0.5).floor(),
561 (self.y + 0.5).floor(),
562 )
563 }
564 }
565
566 pub trait RectHelpers<U>
567 where
568 Self: Sized,
569 {
from_floats(x0: f32, y0: f32, x1: f32, y1: f32) -> Self570 fn from_floats(x0: f32, y0: f32, x1: f32, y1: f32) -> Self;
snap(&self) -> Self571 fn snap(&self) -> Self;
572 }
573
574 impl<U> RectHelpers<U> for Rect<f32, U> {
from_floats(x0: f32, y0: f32, x1: f32, y1: f32) -> Self575 fn from_floats(x0: f32, y0: f32, x1: f32, y1: f32) -> Self {
576 Rect::new(
577 Point2D::new(x0, y0),
578 Size2D::new(x1 - x0, y1 - y0),
579 )
580 }
581
snap(&self) -> Self582 fn snap(&self) -> Self {
583 let origin = Point2D::new(
584 (self.origin.x + 0.5).floor(),
585 (self.origin.y + 0.5).floor(),
586 );
587 Rect::new(
588 origin,
589 Size2D::new(
590 (self.origin.x + self.size.width + 0.5).floor() - origin.x,
591 (self.origin.y + self.size.height + 0.5).floor() - origin.y,
592 ),
593 )
594 }
595 }
596
597 impl<U> RectHelpers<U> for Box2D<f32, U> {
from_floats(x0: f32, y0: f32, x1: f32, y1: f32) -> Self598 fn from_floats(x0: f32, y0: f32, x1: f32, y1: f32) -> Self {
599 Box2D {
600 min: Point2D::new(x0, y0),
601 max: Point2D::new(x1, y1),
602 }
603 }
604
snap(&self) -> Self605 fn snap(&self) -> Self {
606 self.round()
607 }
608 }
609
610 pub trait VectorHelpers<U>
611 where
612 Self: Sized,
613 {
snap(&self) -> Self614 fn snap(&self) -> Self;
615 }
616
617 impl<U> VectorHelpers<U> for Vector2D<f32, U> {
snap(&self) -> Self618 fn snap(&self) -> Self {
619 Vector2D::new(
620 (self.x + 0.5).floor(),
621 (self.y + 0.5).floor(),
622 )
623 }
624 }
625
lerp(a: f32, b: f32, t: f32) -> f32626 pub fn lerp(a: f32, b: f32, t: f32) -> f32 {
627 (b - a) * t + a
628 }
629
630 #[repr(u32)]
631 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
632 #[cfg_attr(feature = "capture", derive(Serialize))]
633 #[cfg_attr(feature = "replay", derive(Deserialize))]
634 pub enum TransformedRectKind {
635 AxisAligned = 0,
636 Complex = 1,
637 }
638
639 #[inline(always)]
pack_as_float(value: u32) -> f32640 pub fn pack_as_float(value: u32) -> f32 {
641 value as f32 + 0.5
642 }
643
644 #[inline]
extract_inner_rect_impl<U>( rect: &Box2D<f32, U>, radii: &BorderRadius, k: f32, ) -> Option<Box2D<f32, U>>645 fn extract_inner_rect_impl<U>(
646 rect: &Box2D<f32, U>,
647 radii: &BorderRadius,
648 k: f32,
649 ) -> Option<Box2D<f32, U>> {
650 // `k` defines how much border is taken into account
651 // We enforce the offsets to be rounded to pixel boundaries
652 // by `ceil`-ing and `floor`-ing them
653
654 let xl = (k * radii.top_left.width.max(radii.bottom_left.width)).ceil();
655 let xr = (rect.width() - k * radii.top_right.width.max(radii.bottom_right.width)).floor();
656 let yt = (k * radii.top_left.height.max(radii.top_right.height)).ceil();
657 let yb =
658 (rect.height() - k * radii.bottom_left.height.max(radii.bottom_right.height)).floor();
659
660 if xl <= xr && yt <= yb {
661 Some(Box2D::from_origin_and_size(
662 Point2D::new(rect.min.x + xl, rect.min.y + yt),
663 Size2D::new(xr - xl, yb - yt),
664 ))
665 } else {
666 None
667 }
668 }
669
670 /// Return an aligned rectangle that is inside the clip region and doesn't intersect
671 /// any of the bounding rectangles of the rounded corners.
extract_inner_rect_safe<U>( rect: &Box2D<f32, U>, radii: &BorderRadius, ) -> Option<Box2D<f32, U>>672 pub fn extract_inner_rect_safe<U>(
673 rect: &Box2D<f32, U>,
674 radii: &BorderRadius,
675 ) -> Option<Box2D<f32, U>> {
676 // value of `k==1.0` is used for extraction of the corner rectangles
677 // see `SEGMENT_CORNER_*` in `clip_shared.glsl`
678 extract_inner_rect_impl(rect, radii, 1.0)
679 }
680
681 #[cfg(test)]
682 use euclid::vec3;
683
684 #[cfg(test)]
685 pub mod test {
686 use super::*;
687 use euclid::default::{Point2D, Size2D, Transform3D};
688 use euclid::{Angle, approxeq::ApproxEq};
689 use std::f32::consts::PI;
690 use crate::clip::{is_left_of_line, polygon_contains_point};
691 use crate::prim_store::PolygonKey;
692 use api::FillRule;
693
694 #[test]
inverse_project()695 fn inverse_project() {
696 let m0 = Transform3D::identity();
697 let p0 = Point2D::new(1.0, 2.0);
698 // an identical transform doesn't need any inverse projection
699 assert_eq!(m0.inverse_project(&p0), Some(p0));
700 let m1 = Transform3D::rotation(0.0, 1.0, 0.0, Angle::radians(-PI / 3.0));
701 // rotation by 60 degrees would imply scaling of X component by a factor of 2
702 assert_eq!(m1.inverse_project(&p0), Some(Point2D::new(2.0, 2.0)));
703 }
704
705 #[test]
inverse_project_footprint()706 fn inverse_project_footprint() {
707 let m = Transform3D::new(
708 0.477499992, 0.135000005, -1.0, 0.000624999986,
709 -0.642787635, 0.766044438, 0.0, 0.0,
710 0.766044438, 0.642787635, 0.0, 0.0,
711 1137.10986, 113.71286, 402.0, 0.748749971,
712 );
713 let r = Box2D::from_size(Size2D::new(804.0, 804.0));
714 {
715 let points = &[
716 r.top_left(),
717 r.top_right(),
718 r.bottom_left(),
719 r.bottom_right(),
720 ];
721 let mi = m.inverse().unwrap();
722 // In this section, we do the forward and backward transformation
723 // to confirm that its bijective.
724 // We also do the inverse projection path, and confirm it functions the same way.
725 println!("Points:");
726 for p in points {
727 let pp = m.transform_point2d_homogeneous(*p);
728 let p3 = pp.to_point3d().unwrap();
729 let pi = mi.transform_point3d_homogeneous(p3);
730 let px = pi.to_point2d().unwrap();
731 let py = m.inverse_project(&pp.to_point2d().unwrap()).unwrap();
732 println!("\t{:?} -> {:?} -> {:?} -> ({:?} -> {:?}, {:?})", p, pp, p3, pi, px, py);
733 assert!(px.approx_eq_eps(p, &Point2D::new(0.001, 0.001)));
734 assert!(py.approx_eq_eps(p, &Point2D::new(0.001, 0.001)));
735 }
736 }
737 // project
738 let rp = project_rect(&m, &r, &Box2D::from_size(Size2D::new(1000.0, 1000.0))).unwrap();
739 println!("Projected {:?}", rp);
740 // one of the points ends up in the negative hemisphere
741 assert_eq!(m.inverse_project(&rp.min), None);
742 // inverse
743 if let Some(ri) = m.inverse_rect_footprint(&rp) {
744 // inverse footprint should be larger, since it doesn't know the original Z
745 assert!(ri.contains_box(&r), "Inverse {:?}", ri);
746 }
747 }
748
validate_convert(xref: &LayoutTransform)749 fn validate_convert(xref: &LayoutTransform) {
750 let so = ScaleOffset::from_transform(xref).unwrap();
751 let xf = so.to_transform();
752 assert!(xref.approx_eq(&xf));
753 }
754
755 #[test]
negative_scale_map_unmap()756 fn negative_scale_map_unmap() {
757 let xref = LayoutTransform::scale(1.0, -1.0, 1.0)
758 .pre_translate(LayoutVector3D::new(124.0, 38.0, 0.0));
759 let so = ScaleOffset::from_transform(&xref).unwrap();
760 let local_rect = Box2D {
761 min: LayoutPoint::new(50.0, -100.0),
762 max: LayoutPoint::new(250.0, 300.0),
763 };
764
765 let mapped_rect = so.map_rect::<LayoutPixel, DevicePixel>(&local_rect);
766 let xf_rect = project_rect(
767 &xref,
768 &local_rect,
769 &LayoutRect::max_rect(),
770 ).unwrap();
771
772 assert!(mapped_rect.min.x.approx_eq(&xf_rect.min.x));
773 assert!(mapped_rect.min.y.approx_eq(&xf_rect.min.y));
774 assert!(mapped_rect.max.x.approx_eq(&xf_rect.max.x));
775 assert!(mapped_rect.max.y.approx_eq(&xf_rect.max.y));
776
777 let unmapped_rect = so.unmap_rect::<DevicePixel, LayoutPixel>(&mapped_rect);
778 assert!(unmapped_rect.min.x.approx_eq(&local_rect.min.x));
779 assert!(unmapped_rect.min.y.approx_eq(&local_rect.min.y));
780 assert!(unmapped_rect.max.x.approx_eq(&local_rect.max.x));
781 assert!(unmapped_rect.max.y.approx_eq(&local_rect.max.y));
782 }
783
784 #[test]
scale_offset_convert()785 fn scale_offset_convert() {
786 let xref = LayoutTransform::translation(130.0, 200.0, 0.0);
787 validate_convert(&xref);
788
789 let xref = LayoutTransform::scale(13.0, 8.0, 1.0);
790 validate_convert(&xref);
791
792 let xref = LayoutTransform::scale(0.5, 0.5, 1.0)
793 .pre_translate(LayoutVector3D::new(124.0, 38.0, 0.0));
794 validate_convert(&xref);
795
796 let xref = LayoutTransform::scale(30.0, 11.0, 1.0)
797 .then_translate(vec3(50.0, 240.0, 0.0));
798 validate_convert(&xref);
799 }
800
validate_inverse(xref: &LayoutTransform)801 fn validate_inverse(xref: &LayoutTransform) {
802 let s0 = ScaleOffset::from_transform(xref).unwrap();
803 let s1 = s0.inverse().accumulate(&s0);
804 assert!((s1.scale.x - 1.0).abs() < NEARLY_ZERO &&
805 (s1.scale.y - 1.0).abs() < NEARLY_ZERO &&
806 s1.offset.x.abs() < NEARLY_ZERO &&
807 s1.offset.y.abs() < NEARLY_ZERO,
808 "{:?}",
809 s1);
810 }
811
812 #[test]
scale_offset_inverse()813 fn scale_offset_inverse() {
814 let xref = LayoutTransform::translation(130.0, 200.0, 0.0);
815 validate_inverse(&xref);
816
817 let xref = LayoutTransform::scale(13.0, 8.0, 1.0);
818 validate_inverse(&xref);
819
820 let xref = LayoutTransform::translation(124.0, 38.0, 0.0).
821 then_scale(0.5, 0.5, 1.0);
822
823 validate_inverse(&xref);
824
825 let xref = LayoutTransform::scale(30.0, 11.0, 1.0)
826 .then_translate(vec3(50.0, 240.0, 0.0));
827 validate_inverse(&xref);
828 }
829
validate_accumulate(x0: &LayoutTransform, x1: &LayoutTransform)830 fn validate_accumulate(x0: &LayoutTransform, x1: &LayoutTransform) {
831 let x = x1.then(&x0);
832
833 let s0 = ScaleOffset::from_transform(x0).unwrap();
834 let s1 = ScaleOffset::from_transform(x1).unwrap();
835
836 let s = s0.accumulate(&s1).to_transform();
837
838 assert!(x.approx_eq(&s), "{:?}\n{:?}", x, s);
839 }
840
841 #[test]
scale_offset_accumulate()842 fn scale_offset_accumulate() {
843 let x0 = LayoutTransform::translation(130.0, 200.0, 0.0);
844 let x1 = LayoutTransform::scale(7.0, 3.0, 1.0);
845
846 validate_accumulate(&x0, &x1);
847 }
848
849 #[test]
inverse_project_2d_origin()850 fn inverse_project_2d_origin() {
851 let mut m = Transform3D::identity();
852 assert_eq!(m.inverse_project_2d_origin(), Some(Point2D::zero()));
853 m.m11 = 0.0;
854 assert_eq!(m.inverse_project_2d_origin(), None);
855 m.m21 = -2.0;
856 m.m22 = 0.0;
857 m.m12 = -0.5;
858 m.m41 = 1.0;
859 m.m42 = 0.5;
860 let origin = m.inverse_project_2d_origin().unwrap();
861 assert_eq!(origin, Point2D::new(1.0, 0.5));
862 assert_eq!(m.transform_point2d(origin), Some(Point2D::zero()));
863 }
864
865 #[test]
polygon_clip_is_left_of_point()866 fn polygon_clip_is_left_of_point() {
867 // Define points of a line through (1, -3) and (-2, 6) to test against.
868 // If the triplet consisting of these two points and the test point
869 // form a counter-clockwise triangle, then the test point is on the
870 // left. The easiest way to visualize this is with an "ascending"
871 // line from low-Y to high-Y.
872 let p0_x = 1.0;
873 let p0_y = -3.0;
874 let p1_x = -2.0;
875 let p1_y = 6.0;
876
877 // Test some points to the left of the line.
878 assert!(is_left_of_line(-9.0, 0.0, p0_x, p0_y, p1_x, p1_y) > 0.0);
879 assert!(is_left_of_line(-1.0, 1.0, p0_x, p0_y, p1_x, p1_y) > 0.0);
880 assert!(is_left_of_line(1.0, -4.0, p0_x, p0_y, p1_x, p1_y) > 0.0);
881
882 // Test some points on the line.
883 assert!(is_left_of_line(-3.0, 9.0, p0_x, p0_y, p1_x, p1_y) == 0.0);
884 assert!(is_left_of_line(0.0, 0.0, p0_x, p0_y, p1_x, p1_y) == 0.0);
885 assert!(is_left_of_line(100.0, -300.0, p0_x, p0_y, p1_x, p1_y) == 0.0);
886
887 // Test some points to the right of the line.
888 assert!(is_left_of_line(0.0, 1.0, p0_x, p0_y, p1_x, p1_y) < 0.0);
889 assert!(is_left_of_line(-4.0, 13.0, p0_x, p0_y, p1_x, p1_y) < 0.0);
890 assert!(is_left_of_line(5.0, -12.0, p0_x, p0_y, p1_x, p1_y) < 0.0);
891 }
892
893 #[test]
polygon_clip_contains_point()894 fn polygon_clip_contains_point() {
895 // We define the points of a self-overlapping polygon, which we will
896 // use to create polygons with different windings and fill rules.
897 let p0 = LayoutPoint::new(4.0, 4.0);
898 let p1 = LayoutPoint::new(6.0, 4.0);
899 let p2 = LayoutPoint::new(4.0, 7.0);
900 let p3 = LayoutPoint::new(2.0, 1.0);
901 let p4 = LayoutPoint::new(8.0, 1.0);
902 let p5 = LayoutPoint::new(6.0, 7.0);
903
904 let poly_clockwise_nonzero = PolygonKey::new(
905 &[p5, p4, p3, p2, p1, p0].to_vec(), FillRule::Nonzero
906 );
907 let poly_clockwise_evenodd = PolygonKey::new(
908 &[p5, p4, p3, p2, p1, p0].to_vec(), FillRule::Evenodd
909 );
910 let poly_counter_clockwise_nonzero = PolygonKey::new(
911 &[p0, p1, p2, p3, p4, p5].to_vec(), FillRule::Nonzero
912 );
913 let poly_counter_clockwise_evenodd = PolygonKey::new(
914 &[p0, p1, p2, p3, p4, p5].to_vec(), FillRule::Evenodd
915 );
916
917 // We define a rect that provides a bounding clip area of
918 // the polygon.
919 let rect = LayoutRect::from_size(LayoutSize::new(10.0, 10.0));
920
921 // And we'll test three points of interest.
922 let p_inside_once = LayoutPoint::new(5.0, 3.0);
923 let p_inside_twice = LayoutPoint::new(5.0, 5.0);
924 let p_outside = LayoutPoint::new(9.0, 9.0);
925
926 // We should get the same results for both clockwise and
927 // counter-clockwise polygons.
928 // For nonzero polygons, the inside twice point is considered inside.
929 for poly_nonzero in vec![poly_clockwise_nonzero, poly_counter_clockwise_nonzero].iter() {
930 assert_eq!(polygon_contains_point(&p_inside_once, &rect, &poly_nonzero), true);
931 assert_eq!(polygon_contains_point(&p_inside_twice, &rect, &poly_nonzero), true);
932 assert_eq!(polygon_contains_point(&p_outside, &rect, &poly_nonzero), false);
933 }
934 // For evenodd polygons, the inside twice point is considered outside.
935 for poly_evenodd in vec![poly_clockwise_evenodd, poly_counter_clockwise_evenodd].iter() {
936 assert_eq!(polygon_contains_point(&p_inside_once, &rect, &poly_evenodd), true);
937 assert_eq!(polygon_contains_point(&p_inside_twice, &rect, &poly_evenodd), false);
938 assert_eq!(polygon_contains_point(&p_outside, &rect, &poly_evenodd), false);
939 }
940 }
941 }
942
943 pub trait MaxRect {
max_rect() -> Self944 fn max_rect() -> Self;
945 }
946
947 impl MaxRect for DeviceIntRect {
max_rect() -> Self948 fn max_rect() -> Self {
949 DeviceIntRect::from_origin_and_size(
950 DeviceIntPoint::new(i32::MIN / 2, i32::MIN / 2),
951 DeviceIntSize::new(i32::MAX, i32::MAX),
952 )
953 }
954 }
955
956 impl<U> MaxRect for Rect<f32, U> {
max_rect() -> Self957 fn max_rect() -> Self {
958 // Having an unlimited bounding box is fine up until we try
959 // to cast it to `i32`, where we get `-2147483648` for any
960 // values larger than or equal to 2^31.
961 //
962 // Note: clamping to i32::MIN and i32::MAX is not a solution,
963 // with explanation left as an exercise for the reader.
964 const MAX_COORD: f32 = 1.0e9;
965
966 Rect::new(
967 Point2D::new(-MAX_COORD, -MAX_COORD),
968 Size2D::new(2.0 * MAX_COORD, 2.0 * MAX_COORD),
969 )
970 }
971 }
972
973 impl<U> MaxRect for Box2D<f32, U> {
max_rect() -> Self974 fn max_rect() -> Self {
975 // Having an unlimited bounding box is fine up until we try
976 // to cast it to `i32`, where we get `-2147483648` for any
977 // values larger than or equal to 2^31.
978 //
979 // Note: clamping to i32::MIN and i32::MAX is not a solution,
980 // with explanation left as an exercise for the reader.
981 const MAX_COORD: f32 = 1.0e9;
982
983 Box2D::new(
984 Point2D::new(-MAX_COORD, -MAX_COORD),
985 Point2D::new(MAX_COORD, MAX_COORD),
986 )
987 }
988 }
989
990 /// An enum that tries to avoid expensive transformation matrix calculations
991 /// when possible when dealing with non-perspective axis-aligned transformations.
992 #[derive(Debug, MallocSizeOf)]
993 pub enum FastTransform<Src, Dst> {
994 /// A simple offset, which can be used without doing any matrix math.
995 Offset(Vector2D<f32, Src>),
996
997 /// A 2D transformation with an inverse.
998 Transform {
999 transform: Transform3D<f32, Src, Dst>,
1000 inverse: Option<Transform3D<f32, Dst, Src>>,
1001 is_2d: bool,
1002 },
1003 }
1004
1005 impl<Src, Dst> Clone for FastTransform<Src, Dst> {
clone(&self) -> Self1006 fn clone(&self) -> Self {
1007 *self
1008 }
1009 }
1010
1011 impl<Src, Dst> Copy for FastTransform<Src, Dst> { }
1012
1013 impl<Src, Dst> FastTransform<Src, Dst> {
identity() -> Self1014 pub fn identity() -> Self {
1015 FastTransform::Offset(Vector2D::zero())
1016 }
1017
with_vector(offset: Vector2D<f32, Src>) -> Self1018 pub fn with_vector(offset: Vector2D<f32, Src>) -> Self {
1019 FastTransform::Offset(offset)
1020 }
1021
with_scale_offset(scale_offset: ScaleOffset) -> Self1022 pub fn with_scale_offset(scale_offset: ScaleOffset) -> Self {
1023 if scale_offset.scale == Vector2D::new(1.0, 1.0) {
1024 FastTransform::Offset(Vector2D::from_untyped(scale_offset.offset))
1025 } else {
1026 FastTransform::Transform {
1027 transform: scale_offset.to_transform(),
1028 inverse: Some(scale_offset.inverse().to_transform()),
1029 is_2d: true,
1030 }
1031 }
1032 }
1033
1034 #[inline(always)]
with_transform(transform: Transform3D<f32, Src, Dst>) -> Self1035 pub fn with_transform(transform: Transform3D<f32, Src, Dst>) -> Self {
1036 if transform.is_simple_2d_translation() {
1037 return FastTransform::Offset(Vector2D::new(transform.m41, transform.m42));
1038 }
1039 let inverse = transform.inverse();
1040 let is_2d = transform.is_2d();
1041 FastTransform::Transform { transform, inverse, is_2d}
1042 }
1043
to_transform(&self) -> Cow<Transform3D<f32, Src, Dst>>1044 pub fn to_transform(&self) -> Cow<Transform3D<f32, Src, Dst>> {
1045 match *self {
1046 FastTransform::Offset(offset) => Cow::Owned(
1047 Transform3D::translation(offset.x, offset.y, 0.0)
1048 ),
1049 FastTransform::Transform { ref transform, .. } => Cow::Borrowed(transform),
1050 }
1051 }
1052
1053 /// Return true if this is an identity transform
1054 #[allow(unused)]
is_identity(&self)-> bool1055 pub fn is_identity(&self)-> bool {
1056 match *self {
1057 FastTransform::Offset(offset) => {
1058 offset == Vector2D::zero()
1059 }
1060 FastTransform::Transform { ref transform, .. } => {
1061 *transform == Transform3D::identity()
1062 }
1063 }
1064 }
1065
then<NewDst>(&self, other: &FastTransform<Dst, NewDst>) -> FastTransform<Src, NewDst>1066 pub fn then<NewDst>(&self, other: &FastTransform<Dst, NewDst>) -> FastTransform<Src, NewDst> {
1067 match *self {
1068 FastTransform::Offset(offset) => match *other {
1069 FastTransform::Offset(other_offset) => {
1070 FastTransform::Offset(offset + other_offset * Scale::<_, _, Src>::new(1.0))
1071 }
1072 FastTransform::Transform { transform: ref other_transform, .. } => {
1073 FastTransform::with_transform(
1074 other_transform
1075 .with_source::<Src>()
1076 .pre_translate(offset.to_3d())
1077 )
1078 }
1079 }
1080 FastTransform::Transform { ref transform, ref inverse, is_2d } => match *other {
1081 FastTransform::Offset(other_offset) => {
1082 FastTransform::with_transform(
1083 transform
1084 .then_translate(other_offset.to_3d())
1085 .with_destination::<NewDst>()
1086 )
1087 }
1088 FastTransform::Transform { transform: ref other_transform, inverse: ref other_inverse, is_2d: other_is_2d } => {
1089 FastTransform::Transform {
1090 transform: transform.then(other_transform),
1091 inverse: inverse.as_ref().and_then(|self_inv|
1092 other_inverse.as_ref().map(|other_inv| other_inv.then(self_inv))
1093 ),
1094 is_2d: is_2d & other_is_2d,
1095 }
1096 }
1097 }
1098 }
1099 }
1100
pre_transform<NewSrc>( &self, other: &FastTransform<NewSrc, Src> ) -> FastTransform<NewSrc, Dst>1101 pub fn pre_transform<NewSrc>(
1102 &self,
1103 other: &FastTransform<NewSrc, Src>
1104 ) -> FastTransform<NewSrc, Dst> {
1105 other.then(self)
1106 }
1107
pre_translate(&self, other_offset: Vector2D<f32, Src>) -> Self1108 pub fn pre_translate(&self, other_offset: Vector2D<f32, Src>) -> Self {
1109 match *self {
1110 FastTransform::Offset(offset) =>
1111 FastTransform::Offset(offset + other_offset),
1112 FastTransform::Transform { transform, .. } =>
1113 FastTransform::with_transform(transform.pre_translate(other_offset.to_3d()))
1114 }
1115 }
1116
then_translate(&self, other_offset: Vector2D<f32, Dst>) -> Self1117 pub fn then_translate(&self, other_offset: Vector2D<f32, Dst>) -> Self {
1118 match *self {
1119 FastTransform::Offset(offset) => {
1120 FastTransform::Offset(offset + other_offset * Scale::<_, _, Src>::new(1.0))
1121 }
1122 FastTransform::Transform { ref transform, .. } => {
1123 let transform = transform.then_translate(other_offset.to_3d());
1124 FastTransform::with_transform(transform)
1125 }
1126 }
1127 }
1128
1129 #[inline(always)]
is_backface_visible(&self) -> bool1130 pub fn is_backface_visible(&self) -> bool {
1131 match *self {
1132 FastTransform::Offset(..) => false,
1133 FastTransform::Transform { inverse: None, .. } => false,
1134 //TODO: fix this properly by taking "det|M33| * det|M34| > 0"
1135 // see https://www.w3.org/Bugs/Public/show_bug.cgi?id=23014
1136 FastTransform::Transform { inverse: Some(ref inverse), .. } => inverse.m33 < 0.0,
1137 }
1138 }
1139
1140 #[inline(always)]
transform_point2d(&self, point: Point2D<f32, Src>) -> Option<Point2D<f32, Dst>>1141 pub fn transform_point2d(&self, point: Point2D<f32, Src>) -> Option<Point2D<f32, Dst>> {
1142 match *self {
1143 FastTransform::Offset(offset) => {
1144 let new_point = point + offset;
1145 Some(Point2D::from_untyped(new_point.to_untyped()))
1146 }
1147 FastTransform::Transform { ref transform, .. } => transform.transform_point2d(point),
1148 }
1149 }
1150
1151 #[inline(always)]
inverse(&self) -> Option<FastTransform<Dst, Src>>1152 pub fn inverse(&self) -> Option<FastTransform<Dst, Src>> {
1153 match *self {
1154 FastTransform::Offset(offset) =>
1155 Some(FastTransform::Offset(Vector2D::new(-offset.x, -offset.y))),
1156 FastTransform::Transform { transform, inverse: Some(inverse), is_2d, } =>
1157 Some(FastTransform::Transform {
1158 transform: inverse,
1159 inverse: Some(transform),
1160 is_2d
1161 }),
1162 FastTransform::Transform { inverse: None, .. } => None,
1163
1164 }
1165 }
1166 }
1167
1168 impl<Src, Dst> From<Transform3D<f32, Src, Dst>> for FastTransform<Src, Dst> {
from(transform: Transform3D<f32, Src, Dst>) -> Self1169 fn from(transform: Transform3D<f32, Src, Dst>) -> Self {
1170 FastTransform::with_transform(transform)
1171 }
1172 }
1173
1174 impl<Src, Dst> From<Vector2D<f32, Src>> for FastTransform<Src, Dst> {
from(vector: Vector2D<f32, Src>) -> Self1175 fn from(vector: Vector2D<f32, Src>) -> Self {
1176 FastTransform::with_vector(vector)
1177 }
1178 }
1179
1180 pub type LayoutFastTransform = FastTransform<LayoutPixel, LayoutPixel>;
1181 pub type LayoutToWorldFastTransform = FastTransform<LayoutPixel, WorldPixel>;
1182
project_rect<F, T>( transform: &Transform3D<f32, F, T>, rect: &Box2D<f32, F>, bounds: &Box2D<f32, T>, ) -> Option<Box2D<f32, T>> where F: fmt::Debug1183 pub fn project_rect<F, T>(
1184 transform: &Transform3D<f32, F, T>,
1185 rect: &Box2D<f32, F>,
1186 bounds: &Box2D<f32, T>,
1187 ) -> Option<Box2D<f32, T>>
1188 where F: fmt::Debug
1189 {
1190 let homogens = [
1191 transform.transform_point2d_homogeneous(rect.top_left()),
1192 transform.transform_point2d_homogeneous(rect.top_right()),
1193 transform.transform_point2d_homogeneous(rect.bottom_left()),
1194 transform.transform_point2d_homogeneous(rect.bottom_right()),
1195 ];
1196
1197 // Note: we only do the full frustum collision when the polygon approaches the camera plane.
1198 // Otherwise, it will be clamped to the screen bounds anyway.
1199 if homogens.iter().any(|h| h.w <= 0.0 || h.w.is_nan()) {
1200 let mut clipper = Clipper::new();
1201 let polygon = Polygon::from_rect(rect.to_rect(), 1);
1202
1203 let planes = match Clipper::<_, _, usize>::frustum_planes(
1204 transform,
1205 Some(bounds.to_rect()),
1206 ) {
1207 Ok(planes) => planes,
1208 Err(..) => return None,
1209 };
1210
1211 for plane in planes {
1212 clipper.add(plane);
1213 }
1214
1215 let results = clipper.clip(polygon);
1216 if results.is_empty() {
1217 return None
1218 }
1219
1220 Some(Box2D::from_points(results
1221 .into_iter()
1222 // filter out parts behind the view plane
1223 .flat_map(|poly| &poly.points)
1224 .map(|p| {
1225 let mut homo = transform.transform_point2d_homogeneous(p.to_2d());
1226 homo.w = homo.w.max(0.00000001); // avoid infinite values
1227 homo.to_point2d().unwrap()
1228 })
1229 ))
1230 } else {
1231 // we just checked for all the points to be in positive hemisphere, so `unwrap` is valid
1232 Some(Box2D::from_points(&[
1233 homogens[0].to_point2d().unwrap(),
1234 homogens[1].to_point2d().unwrap(),
1235 homogens[2].to_point2d().unwrap(),
1236 homogens[3].to_point2d().unwrap(),
1237 ]))
1238 }
1239 }
1240
raster_rect_to_device_pixels( rect: RasterRect, device_pixel_scale: DevicePixelScale, ) -> DeviceRect1241 pub fn raster_rect_to_device_pixels(
1242 rect: RasterRect,
1243 device_pixel_scale: DevicePixelScale,
1244 ) -> DeviceRect {
1245 let world_rect = rect * Scale::new(1.0);
1246 let device_rect = world_rect * device_pixel_scale;
1247 device_rect.round_out()
1248 }
1249
1250 /// Run the first callback over all elements in the array. If the callback returns true,
1251 /// the element is removed from the array and moved to a second callback.
1252 ///
1253 /// This is a simple implementation waiting for Vec::drain_filter to be stable.
1254 /// When that happens, code like:
1255 ///
1256 /// let filter = |op| {
1257 /// match *op {
1258 /// Enum::Foo | Enum::Bar => true,
1259 /// Enum::Baz => false,
1260 /// }
1261 /// };
1262 /// drain_filter(
1263 /// &mut ops,
1264 /// filter,
1265 /// |op| {
1266 /// match op {
1267 /// Enum::Foo => { foo(); }
1268 /// Enum::Bar => { bar(); }
1269 /// Enum::Baz => { unreachable!(); }
1270 /// }
1271 /// },
1272 /// );
1273 ///
1274 /// Can be rewritten as:
1275 ///
1276 /// let filter = |op| {
1277 /// match *op {
1278 /// Enum::Foo | Enum::Bar => true,
1279 /// Enum::Baz => false,
1280 /// }
1281 /// };
1282 /// for op in ops.drain_filter(filter) {
1283 /// match op {
1284 /// Enum::Foo => { foo(); }
1285 /// Enum::Bar => { bar(); }
1286 /// Enum::Baz => { unreachable!(); }
1287 /// }
1288 /// }
1289 ///
1290 /// See https://doc.rust-lang.org/std/vec/struct.Vec.html#method.drain_filter
drain_filter<T, Filter, Action>( vec: &mut Vec<T>, mut filter: Filter, mut action: Action, ) where Filter: FnMut(&mut T) -> bool, Action: FnMut(T)1291 pub fn drain_filter<T, Filter, Action>(
1292 vec: &mut Vec<T>,
1293 mut filter: Filter,
1294 mut action: Action,
1295 )
1296 where
1297 Filter: FnMut(&mut T) -> bool,
1298 Action: FnMut(T)
1299 {
1300 let mut i = 0;
1301 while i != vec.len() {
1302 if filter(&mut vec[i]) {
1303 action(vec.remove(i));
1304 } else {
1305 i += 1;
1306 }
1307 }
1308 }
1309
1310
1311 #[derive(Debug)]
1312 pub struct Recycler {
1313 pub num_allocations: usize,
1314 }
1315
1316 impl Recycler {
1317 /// Maximum extra capacity that a recycled vector is allowed to have. If the actual capacity
1318 /// is larger, we re-allocate the vector storage with lower capacity.
1319 const MAX_EXTRA_CAPACITY_PERCENT: usize = 200;
1320 /// Minimum extra capacity to keep when re-allocating the vector storage.
1321 const MIN_EXTRA_CAPACITY_PERCENT: usize = 20;
1322 /// Minimum sensible vector length to consider for re-allocation.
1323 const MIN_VECTOR_LENGTH: usize = 16;
1324
new() -> Self1325 pub fn new() -> Self {
1326 Recycler {
1327 num_allocations: 0,
1328 }
1329 }
1330
1331 /// Clear a vector for re-use, while retaining the backing memory buffer. May shrink the buffer
1332 /// if it's currently much larger than was actually used.
recycle_vec<T>(&mut self, vec: &mut Vec<T>)1333 pub fn recycle_vec<T>(&mut self, vec: &mut Vec<T>) {
1334 let extra_capacity = (vec.capacity() - vec.len()) * 100 / vec.len().max(Self::MIN_VECTOR_LENGTH);
1335
1336 if extra_capacity > Self::MAX_EXTRA_CAPACITY_PERCENT {
1337 // Reduce capacity of the buffer if it is a lot larger than it needs to be. This prevents
1338 // a frame with exceptionally large allocations to cause subsequent frames to retain
1339 // more memory than they need.
1340 //TODO: use `shrink_to` when it's stable
1341 *vec = Vec::with_capacity(vec.len() + vec.len() * Self::MIN_EXTRA_CAPACITY_PERCENT / 100);
1342 self.num_allocations += 1;
1343 } else {
1344 vec.clear();
1345 }
1346 }
1347 }
1348
1349 /// Record the size of a data structure to preallocate a similar size
1350 /// at the next frame and avoid growing it too many time.
1351 #[derive(Copy, Clone, Debug)]
1352 pub struct Preallocator {
1353 size: usize,
1354 }
1355
1356 impl Preallocator {
new(initial_size: usize) -> Self1357 pub fn new(initial_size: usize) -> Self {
1358 Preallocator {
1359 size: initial_size,
1360 }
1361 }
1362
1363 /// Record the size of a vector to preallocate it the next frame.
record_vec<T>(&mut self, vec: &Vec<T>)1364 pub fn record_vec<T>(&mut self, vec: &Vec<T>) {
1365 let len = vec.len();
1366 if len > self.size {
1367 self.size = len;
1368 } else {
1369 self.size = (self.size + len) / 2;
1370 }
1371 }
1372
1373 /// The size that we'll preallocate the vector with.
preallocation_size(&self) -> usize1374 pub fn preallocation_size(&self) -> usize {
1375 // Round up to multiple of 16 to avoid small tiny
1376 // variations causing reallocations.
1377 (self.size + 15) & !15
1378 }
1379
1380 /// Preallocate vector storage.
1381 ///
1382 /// The preallocated amount depends on the length recorded in the last
1383 /// record_vec call.
preallocate_vec<T>(&self, vec: &mut Vec<T>)1384 pub fn preallocate_vec<T>(&self, vec: &mut Vec<T>) {
1385 let len = vec.len();
1386 let cap = self.preallocation_size();
1387 if len < cap {
1388 vec.reserve(cap - len);
1389 }
1390 }
1391 }
1392
1393 impl Default for Preallocator {
default() -> Self1394 fn default() -> Self {
1395 Self::new(0)
1396 }
1397 }
1398
1399 /// Arc wrapper to support measurement via MallocSizeOf.
1400 ///
1401 /// Memory reporting for Arcs is tricky because of the risk of double-counting.
1402 /// One way to measure them is to keep a table of pointers that have already been
1403 /// traversed. The other way is to use knowledge of the program structure to
1404 /// identify which Arc instances should be measured and which should be skipped to
1405 /// avoid double-counting.
1406 ///
1407 /// This struct implements the second approach. It identifies the "main" pointer
1408 /// to the Arc-ed resource, and measures the buffer as if it were an owned pointer.
1409 /// The programmer should ensure that there is at most one PrimaryArc for a given
1410 /// underlying ArcInner.
1411 #[cfg_attr(feature = "capture", derive(Serialize))]
1412 #[cfg_attr(feature = "replay", derive(Deserialize))]
1413 #[derive(Clone, Debug, Hash, PartialEq, Eq)]
1414 pub struct PrimaryArc<T>(pub Arc<T>);
1415
1416 impl<T> ::std::ops::Deref for PrimaryArc<T> {
1417 type Target = Arc<T>;
1418
1419 #[inline]
deref(&self) -> &Arc<T>1420 fn deref(&self) -> &Arc<T> {
1421 &self.0
1422 }
1423 }
1424
1425 impl<T> MallocShallowSizeOf for PrimaryArc<T> {
shallow_size_of(&self, ops: &mut MallocSizeOfOps) -> usize1426 fn shallow_size_of(&self, ops: &mut MallocSizeOfOps) -> usize {
1427 unsafe {
1428 // This is a bit sketchy, but std::sync::Arc doesn't expose the
1429 // base pointer.
1430 let raw_arc_ptr: *const Arc<T> = &self.0;
1431 let raw_ptr_ptr: *const *const c_void = raw_arc_ptr as _;
1432 let raw_ptr = *raw_ptr_ptr;
1433 (ops.size_of_op)(raw_ptr)
1434 }
1435 }
1436 }
1437
1438 impl<T: MallocSizeOf> MallocSizeOf for PrimaryArc<T> {
size_of(&self, ops: &mut MallocSizeOfOps) -> usize1439 fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize {
1440 self.shallow_size_of(ops) + (**self).size_of(ops)
1441 }
1442 }
1443
1444 /// Computes the scale factors of this matrix; that is,
1445 /// the amounts each basis vector is scaled by.
1446 ///
1447 /// This code comes from gecko gfx/2d/Matrix.h with the following
1448 /// modifications:
1449 ///
1450 /// * Removed `xMajor` parameter.
scale_factors<Src, Dst>( mat: &Transform3D<f32, Src, Dst> ) -> (f32, f32)1451 pub fn scale_factors<Src, Dst>(
1452 mat: &Transform3D<f32, Src, Dst>
1453 ) -> (f32, f32) {
1454 // Determinant is just of the 2D component.
1455 let det = mat.m11 * mat.m22 - mat.m12 * mat.m21;
1456 if det == 0.0 {
1457 return (0.0, 0.0);
1458 }
1459
1460 // ignore mirroring
1461 let det = det.abs();
1462
1463 let major = (mat.m11 * mat.m11 + mat.m12 * mat.m12).sqrt();
1464 let minor = if major != 0.0 { det / major } else { 0.0 };
1465
1466 (major, minor)
1467 }
1468
1469 /// Clamp scaling factor to a power of two.
1470 ///
1471 /// This code comes from gecko gfx/thebes/gfxUtils.cpp with the following
1472 /// modification:
1473 ///
1474 /// * logs are taken in base 2 instead of base e.
clamp_to_scale_factor(val: f32, round_down: bool) -> f321475 pub fn clamp_to_scale_factor(val: f32, round_down: bool) -> f32 {
1476 // Arbitary scale factor limitation. We can increase this
1477 // for better scaling performance at the cost of worse
1478 // quality.
1479 const SCALE_RESOLUTION: f32 = 2.0;
1480
1481 // Negative scaling is just a flip and irrelevant to
1482 // our resolution calculation.
1483 let val = val.abs();
1484
1485 let (val, inverse) = if val < 1.0 {
1486 (1.0 / val, true)
1487 } else {
1488 (val, false)
1489 };
1490
1491 let power = val.log2() / SCALE_RESOLUTION.log2();
1492
1493 // If power is within 1e-5 of an integer, round to nearest to
1494 // prevent floating point errors, otherwise round up to the
1495 // next integer value.
1496 let power = if (power - power.round()).abs() < 1e-5 {
1497 power.round()
1498 } else if inverse != round_down {
1499 // Use floor when we are either inverted or rounding down, but
1500 // not both.
1501 power.floor()
1502 } else {
1503 // Otherwise, ceil when we are not inverted and not rounding
1504 // down, or we are inverted and rounding down.
1505 power.ceil()
1506 };
1507
1508 let scale = SCALE_RESOLUTION.powf(power);
1509
1510 if inverse {
1511 1.0 / scale
1512 } else {
1513 scale
1514 }
1515 }
1516
1517 /// Rounds a value up to the nearest multiple of mul
round_up_to_multiple(val: usize, mul: NonZeroUsize) -> usize1518 pub fn round_up_to_multiple(val: usize, mul: NonZeroUsize) -> usize {
1519 match val % mul.get() {
1520 0 => val,
1521 rem => val - rem + mul.get(),
1522 }
1523 }
1524
1525
1526 #[macro_export]
1527 macro_rules! c_str {
1528 ($lit:expr) => {
1529 unsafe {
1530 std::ffi::CStr::from_ptr(concat!($lit, "\0").as_ptr()
1531 as *const std::os::raw::c_char)
1532 }
1533 }
1534 }
1535
1536 // Find a rectangle that is contained by the sum of r1 and r2.
conservative_union_rect<U>(r1: &Box2D<f32, U>, r2: &Box2D<f32, U>) -> Box2D<f32, U>1537 pub fn conservative_union_rect<U>(r1: &Box2D<f32, U>, r2: &Box2D<f32, U>) -> Box2D<f32, U> {
1538 // +---+---+ +--+-+--+
1539 // | | | | | | |
1540 // | | | | | | |
1541 // +---+---+ +--+-+--+
1542 if r1.min.y == r2.min.y && r1.max.y == r2.max.y {
1543 if r2.min.x <= r1.max.x && r2.max.x >= r1.min.x {
1544 let min_x = f32::min(r1.min.x, r2.min.x);
1545 let max_x = f32::max(r1.max.x, r2.max.x);
1546
1547 return Box2D {
1548 min: point2(min_x, r1.min.y),
1549 max: point2(max_x, r1.max.y),
1550 }
1551 }
1552 }
1553
1554 // +----+ +----+
1555 // | | | |
1556 // | | +----+
1557 // +----+ | |
1558 // | | +----+
1559 // | | | |
1560 // +----+ +----+
1561 if r1.min.x == r2.min.x && r1.max.x == r2.max.x {
1562 if r2.min.y <= r1.max.y && r2.max.y >= r1.min.y {
1563 let min_y = f32::min(r1.min.y, r2.min.y);
1564 let max_y = f32::max(r1.max.y, r2.max.y);
1565
1566 return Box2D {
1567 min: point2(r1.min.x, min_y),
1568 max: point2(r1.max.x, max_y),
1569 }
1570 }
1571 }
1572
1573 if r1.area() >= r2.area() { *r1 } else {*r2 }
1574 }
1575
1576 #[test]
test_conservative_union_rect()1577 fn test_conservative_union_rect() {
1578 // Adjacent, x axis
1579 let r = conservative_union_rect(
1580 &LayoutRect { min: point2(1.0, 2.0), max: point2(4.0, 6.0) },
1581 &LayoutRect { min: point2(4.0, 2.0), max: point2(9.0, 6.0) },
1582 );
1583 assert_eq!(r, LayoutRect { min: point2(1.0, 2.0), max: point2(9.0, 6.0) });
1584
1585 let r = conservative_union_rect(
1586 &LayoutRect { min: point2(4.0, 2.0), max: point2(9.0, 6.0) },
1587 &LayoutRect { min: point2(1.0, 2.0), max: point2(4.0, 6.0) },
1588 );
1589 assert_eq!(r, LayoutRect { min: point2(1.0, 2.0), max: point2(9.0, 6.0) });
1590
1591 // Averlapping adjacent, x axis
1592 let r = conservative_union_rect(
1593 &LayoutRect { min: point2(1.0, 2.0), max: point2(4.0, 6.0) },
1594 &LayoutRect { min: point2(3.0, 2.0), max: point2(8.0, 6.0) },
1595 );
1596 assert_eq!(r, LayoutRect { min: point2(1.0, 2.0), max: point2(8.0, 6.0) });
1597
1598 let r = conservative_union_rect(
1599 &LayoutRect { min: point2(5.0, 2.0), max: point2(8.0, 6.0) },
1600 &LayoutRect { min: point2(1.0, 2.0), max: point2(6.0, 6.0) },
1601 );
1602 assert_eq!(r, LayoutRect { min: point2(1.0, 2.0), max: point2(8.0, 6.0) });
1603
1604 // Adjacent but not touching, x axis
1605 let r = conservative_union_rect(
1606 &LayoutRect { min: point2(1.0, 2.0), max: point2(4.0, 6.0) },
1607 &LayoutRect { min: point2(6.0, 2.0), max: point2(11.0, 6.0) },
1608 );
1609 assert_eq!(r, LayoutRect { min: point2(6.0, 2.0), max: point2(11.0, 6.0) });
1610
1611 let r = conservative_union_rect(
1612 &LayoutRect { min: point2(1.0, 2.0), max: point2(4.0, 6.0) },
1613 &LayoutRect { min: point2(-6.0, 2.0), max: point2(-5.0, 6.0) },
1614 );
1615 assert_eq!(r, LayoutRect { min: point2(1.0, 2.0), max: point2(4.0, 6.0) });
1616
1617
1618 // Adjacent, y axis
1619 let r = conservative_union_rect(
1620 &LayoutRect { min: point2(1.0, 2.0), max: point2(4.0, 6.0) },
1621 &LayoutRect { min: point2(1.0, 6.0), max: point2(4.0, 10.0) },
1622 );
1623 assert_eq!(r, LayoutRect { min: point2(1.0, 2.0), max: point2(4.0, 10.0) });
1624
1625 let r = conservative_union_rect(
1626 &LayoutRect { min: point2(1.0, 5.0), max: point2(4.0, 9.0) },
1627 &LayoutRect { min: point2(1.0, 1.0), max: point2(4.0, 5.0) },
1628 );
1629 assert_eq!(r, LayoutRect { min: point2(1.0, 1.0), max: point2(4.0, 9.0) });
1630
1631 // Averlapping adjacent, y axis
1632 let r = conservative_union_rect(
1633 &LayoutRect { min: point2(1.0, 2.0), max: point2(4.0, 6.0) },
1634 &LayoutRect { min: point2(1.0, 3.0), max: point2(4.0, 7.0) },
1635 );
1636 assert_eq!(r, LayoutRect { min: point2(1.0, 2.0), max: point2(4.0, 7.0) });
1637
1638 let r = conservative_union_rect(
1639 &LayoutRect { min: point2(1.0, 4.0), max: point2(4.0, 8.0) },
1640 &LayoutRect { min: point2(1.0, 2.0), max: point2(4.0, 6.0) },
1641 );
1642 assert_eq!(r, LayoutRect { min: point2(1.0, 2.0), max: point2(4.0, 8.0) });
1643
1644 // Adjacent but not touching, y axis
1645 let r = conservative_union_rect(
1646 &LayoutRect { min: point2(1.0, 2.0), max: point2(4.0, 6.0) },
1647 &LayoutRect { min: point2(1.0, 10.0), max: point2(4.0, 15.0) },
1648 );
1649 assert_eq!(r, LayoutRect { min: point2(1.0, 10.0), max: point2(4.0, 15.0) });
1650
1651 let r = conservative_union_rect(
1652 &LayoutRect { min: point2(1.0, 5.0), max: point2(4.0, 9.0) },
1653 &LayoutRect { min: point2(1.0, 0.0), max: point2(4.0, 3.0) },
1654 );
1655 assert_eq!(r, LayoutRect { min: point2(1.0, 5.0), max: point2(4.0, 9.0) });
1656
1657
1658 // Contained
1659 let r = conservative_union_rect(
1660 &LayoutRect { min: point2(1.0, 2.0), max: point2(4.0, 6.0) },
1661 &LayoutRect { min: point2(0.0, 1.0), max: point2(10.0, 12.0) },
1662 );
1663 assert_eq!(r, LayoutRect { min: point2(0.0, 1.0), max: point2(10.0, 12.0) });
1664
1665 let r = conservative_union_rect(
1666 &LayoutRect { min: point2(0.0, 1.0), max: point2(10.0, 12.0) },
1667 &LayoutRect { min: point2(1.0, 2.0), max: point2(4.0, 6.0) },
1668 );
1669 assert_eq!(r, LayoutRect { min: point2(0.0, 1.0), max: point2(10.0, 12.0) });
1670 }
1671
1672 /// This is inspired by the `weak-table` crate.
1673 /// It holds a Vec of weak pointers that are garbage collected as the Vec
1674 pub struct WeakTable {
1675 inner: Vec<std::sync::Weak<Vec<u8>>>
1676 }
1677
1678 impl WeakTable {
new() -> WeakTable1679 pub fn new() -> WeakTable {
1680 WeakTable { inner: Vec::new() }
1681 }
insert(&mut self, x: std::sync::Weak<Vec<u8>>)1682 pub fn insert(&mut self, x: std::sync::Weak<Vec<u8>>) {
1683 if self.inner.len() == self.inner.capacity() {
1684 self.remove_expired();
1685
1686 // We want to make sure that we change capacity()
1687 // even if remove_expired() removes some entries
1688 // so that we don't repeatedly hit remove_expired()
1689 if self.inner.len() * 3 < self.inner.capacity() {
1690 // We use a different multiple for shrinking then
1691 // expanding so that we we don't accidentally
1692 // oscilate.
1693 self.inner.shrink_to_fit();
1694 } else {
1695 // Otherwise double our size
1696 self.inner.reserve(self.inner.len())
1697 }
1698 }
1699 self.inner.push(x);
1700 }
1701
remove_expired(&mut self)1702 fn remove_expired(&mut self) {
1703 self.inner.retain(|x| x.strong_count() > 0)
1704 }
1705
iter(&self) -> impl Iterator<Item = Arc<Vec<u8>>> + '_1706 pub fn iter(&self) -> impl Iterator<Item = Arc<Vec<u8>>> + '_ {
1707 self.inner.iter().filter_map(|x| x.upgrade())
1708 }
1709 }
1710
1711 #[test]
weak_table()1712 fn weak_table() {
1713 let mut tbl = WeakTable::new();
1714 let mut things = Vec::new();
1715 let target_count = 50;
1716 for _ in 0..target_count {
1717 things.push(Arc::new(vec![4]));
1718 }
1719 for i in &things {
1720 tbl.insert(Arc::downgrade(i))
1721 }
1722 assert_eq!(tbl.inner.len(), target_count);
1723 drop(things);
1724 assert_eq!(tbl.iter().count(), 0);
1725
1726 // make sure that we shrink the table if it gets too big
1727 // by adding a bunch of dead items
1728 for _ in 0..target_count*2 {
1729 tbl.insert(Arc::downgrade(&Arc::new(vec![5])))
1730 }
1731 assert!(tbl.inner.capacity() <= 4);
1732 }
1733