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 https://mozilla.org/MPL/2.0/. */ 4 5 //! [Calc expressions][calc]. 6 //! 7 //! [calc]: https://drafts.csswg.org/css-values/#calc-notation 8 9 use crate::Zero; 10 use smallvec::SmallVec; 11 use std::fmt::{self, Write}; 12 use std::ops::Add; 13 use std::{cmp, mem}; 14 use style_traits::{CssWriter, ToCss}; 15 16 /// Whether we're a `min` or `max` function. 17 #[derive( 18 Clone, 19 Copy, 20 Debug, 21 Deserialize, 22 MallocSizeOf, 23 PartialEq, 24 Serialize, 25 ToAnimatedZero, 26 ToResolvedValue, 27 ToShmem, 28 )] 29 #[repr(u8)] 30 pub enum MinMaxOp { 31 /// `min()` 32 Min, 33 /// `max()` 34 Max, 35 } 36 37 /// This determines the order in which we serialize members of a calc() sum. 38 /// 39 /// See https://drafts.csswg.org/css-values-4/#sort-a-calculations-children 40 #[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)] 41 #[allow(missing_docs)] 42 pub enum SortKey { 43 Number, 44 Percentage, 45 Cap, 46 Ch, 47 Deg, 48 Em, 49 Ex, 50 Ic, 51 Px, 52 Rem, 53 Sec, 54 Vh, 55 Vmax, 56 Vmin, 57 Vw, 58 Other, 59 } 60 61 /// A generic node in a calc expression. 62 /// 63 /// FIXME: This would be much more elegant if we used `Self` in the types below, 64 /// but we can't because of https://github.com/serde-rs/serde/issues/1565. 65 /// 66 /// FIXME: The following annotations are to workaround an LLVM inlining bug, see 67 /// bug 1631929. 68 /// 69 /// cbindgen:destructor-attributes=MOZ_NEVER_INLINE 70 /// cbindgen:copy-constructor-attributes=MOZ_NEVER_INLINE 71 /// cbindgen:eq-attributes=MOZ_NEVER_INLINE 72 #[repr(u8)] 73 #[derive( 74 Clone, 75 Debug, 76 Deserialize, 77 MallocSizeOf, 78 PartialEq, 79 Serialize, 80 ToAnimatedZero, 81 ToResolvedValue, 82 ToShmem, 83 )] 84 pub enum GenericCalcNode<L> { 85 /// A leaf node. 86 Leaf(L), 87 /// A sum node, representing `a + b + c` where a, b, and c are the 88 /// arguments. 89 Sum(crate::OwnedSlice<GenericCalcNode<L>>), 90 /// A `min` or `max` function. 91 MinMax(crate::OwnedSlice<GenericCalcNode<L>>, MinMaxOp), 92 /// A `clamp()` function. 93 Clamp { 94 /// The minimum value. 95 min: Box<GenericCalcNode<L>>, 96 /// The central value. 97 center: Box<GenericCalcNode<L>>, 98 /// The maximum value. 99 max: Box<GenericCalcNode<L>>, 100 }, 101 } 102 103 pub use self::GenericCalcNode as CalcNode; 104 105 /// A trait that represents all the stuff a valid leaf of a calc expression. 106 pub trait CalcNodeLeaf: Clone + Sized + PartialOrd + PartialEq + ToCss { 107 /// Whether this value is known-negative. is_negative(&self) -> bool108 fn is_negative(&self) -> bool; 109 110 /// Tries to merge one sum to another, that is, perform `x` + `y`. try_sum_in_place(&mut self, other: &Self) -> Result<(), ()>111 fn try_sum_in_place(&mut self, other: &Self) -> Result<(), ()>; 112 113 /// Multiplies the leaf by a given scalar number. mul_by(&mut self, scalar: f32)114 fn mul_by(&mut self, scalar: f32); 115 116 /// Negates the leaf. negate(&mut self)117 fn negate(&mut self) { 118 self.mul_by(-1.); 119 } 120 121 /// Canonicalizes the expression if necessary. simplify(&mut self)122 fn simplify(&mut self); 123 124 /// Returns the sort key for simplification. sort_key(&self) -> SortKey125 fn sort_key(&self) -> SortKey; 126 } 127 128 impl<L: CalcNodeLeaf> CalcNode<L> { 129 /// Negates the node. negate(&mut self)130 pub fn negate(&mut self) { 131 self.mul_by(-1.); 132 } 133 sort_key(&self) -> SortKey134 fn sort_key(&self) -> SortKey { 135 match *self { 136 Self::Leaf(ref l) => l.sort_key(), 137 _ => SortKey::Other, 138 } 139 } 140 141 /// Tries to merge one sum to another, that is, perform `x` + `y`. try_sum_in_place(&mut self, other: &Self) -> Result<(), ()>142 fn try_sum_in_place(&mut self, other: &Self) -> Result<(), ()> { 143 match (self, other) { 144 (&mut CalcNode::Leaf(ref mut one), &CalcNode::Leaf(ref other)) => { 145 one.try_sum_in_place(other) 146 }, 147 _ => Err(()), 148 } 149 } 150 151 /// Convert this `CalcNode` into a `CalcNode` with a different leaf kind. map_leaves<O, F>(&self, mut map: F) -> CalcNode<O> where O: CalcNodeLeaf, F: FnMut(&L) -> O,152 pub fn map_leaves<O, F>(&self, mut map: F) -> CalcNode<O> 153 where 154 O: CalcNodeLeaf, 155 F: FnMut(&L) -> O, 156 { 157 self.map_leaves_internal(&mut map) 158 } 159 map_leaves_internal<O, F>(&self, map: &mut F) -> CalcNode<O> where O: CalcNodeLeaf, F: FnMut(&L) -> O,160 fn map_leaves_internal<O, F>(&self, map: &mut F) -> CalcNode<O> 161 where 162 O: CalcNodeLeaf, 163 F: FnMut(&L) -> O, 164 { 165 fn map_children<L, O, F>( 166 children: &[CalcNode<L>], 167 map: &mut F, 168 ) -> crate::OwnedSlice<CalcNode<O>> 169 where 170 L: CalcNodeLeaf, 171 O: CalcNodeLeaf, 172 F: FnMut(&L) -> O, 173 { 174 children 175 .iter() 176 .map(|c| c.map_leaves_internal(map)) 177 .collect() 178 } 179 180 match *self { 181 Self::Leaf(ref l) => CalcNode::Leaf(map(l)), 182 Self::Sum(ref c) => CalcNode::Sum(map_children(c, map)), 183 Self::MinMax(ref c, op) => CalcNode::MinMax(map_children(c, map), op), 184 Self::Clamp { 185 ref min, 186 ref center, 187 ref max, 188 } => { 189 let min = Box::new(min.map_leaves_internal(map)); 190 let center = Box::new(center.map_leaves_internal(map)); 191 let max = Box::new(max.map_leaves_internal(map)); 192 CalcNode::Clamp { min, center, max } 193 }, 194 } 195 } 196 197 /// Resolves the expression returning a value of `O`, given a function to 198 /// turn a leaf into the relevant value. resolve<O>( &self, mut leaf_to_output_fn: impl FnMut(&L) -> Result<O, ()>, ) -> Result<O, ()> where O: PartialOrd + PartialEq + Add<Output = O> + Zero,199 pub fn resolve<O>( 200 &self, 201 mut leaf_to_output_fn: impl FnMut(&L) -> Result<O, ()>, 202 ) -> Result<O, ()> 203 where 204 O: PartialOrd + PartialEq + Add<Output = O> + Zero, 205 { 206 self.resolve_internal(&mut leaf_to_output_fn) 207 } 208 resolve_internal<O, F>(&self, leaf_to_output_fn: &mut F) -> Result<O, ()> where O: PartialOrd + PartialEq + Add<Output = O> + Zero, F: FnMut(&L) -> Result<O, ()>,209 fn resolve_internal<O, F>(&self, leaf_to_output_fn: &mut F) -> Result<O, ()> 210 where 211 O: PartialOrd + PartialEq + Add<Output = O> + Zero, 212 F: FnMut(&L) -> Result<O, ()>, 213 { 214 Ok(match *self { 215 Self::Leaf(ref l) => return leaf_to_output_fn(l), 216 Self::Sum(ref c) => { 217 let mut result = Zero::zero(); 218 for child in &**c { 219 result = result + child.resolve_internal(leaf_to_output_fn)?; 220 } 221 result 222 }, 223 Self::MinMax(ref nodes, op) => { 224 let mut result = nodes[0].resolve_internal(leaf_to_output_fn)?; 225 for node in nodes.iter().skip(1) { 226 let candidate = node.resolve_internal(leaf_to_output_fn)?; 227 let candidate_wins = match op { 228 MinMaxOp::Min => candidate < result, 229 MinMaxOp::Max => candidate > result, 230 }; 231 if candidate_wins { 232 result = candidate; 233 } 234 } 235 result 236 }, 237 Self::Clamp { 238 ref min, 239 ref center, 240 ref max, 241 } => { 242 let min = min.resolve_internal(leaf_to_output_fn)?; 243 let center = center.resolve_internal(leaf_to_output_fn)?; 244 let max = max.resolve_internal(leaf_to_output_fn)?; 245 246 let mut result = center; 247 if result > max { 248 result = max; 249 } 250 if result < min { 251 result = min 252 } 253 result 254 }, 255 }) 256 } 257 is_negative_leaf(&self) -> bool258 fn is_negative_leaf(&self) -> bool { 259 match *self { 260 Self::Leaf(ref l) => l.is_negative(), 261 _ => false, 262 } 263 } 264 265 /// Multiplies the node by a scalar. mul_by(&mut self, scalar: f32)266 pub fn mul_by(&mut self, scalar: f32) { 267 match *self { 268 Self::Leaf(ref mut l) => l.mul_by(scalar), 269 // Multiplication is distributive across this. 270 Self::Sum(ref mut children) => { 271 for node in &mut **children { 272 node.mul_by(scalar); 273 } 274 }, 275 // This one is a bit trickier. 276 Self::MinMax(ref mut children, ref mut op) => { 277 for node in &mut **children { 278 node.mul_by(scalar); 279 } 280 281 // For negatives we need to invert the operation. 282 if scalar < 0. { 283 *op = match *op { 284 MinMaxOp::Min => MinMaxOp::Max, 285 MinMaxOp::Max => MinMaxOp::Min, 286 } 287 } 288 }, 289 // This one is slightly tricky too. 290 Self::Clamp { 291 ref mut min, 292 ref mut center, 293 ref mut max, 294 } => { 295 min.mul_by(scalar); 296 center.mul_by(scalar); 297 max.mul_by(scalar); 298 // For negatives we need to swap min / max. 299 if scalar < 0. { 300 mem::swap(min, max); 301 } 302 }, 303 } 304 } 305 306 /// Visits all the nodes in this calculation tree recursively, starting by 307 /// the leaves and bubbling all the way up. 308 /// 309 /// This is useful for simplification, but can also be used for validation 310 /// and such. visit_depth_first(&mut self, mut f: impl FnMut(&mut Self))311 pub fn visit_depth_first(&mut self, mut f: impl FnMut(&mut Self)) { 312 self.visit_depth_first_internal(&mut f); 313 } 314 visit_depth_first_internal(&mut self, f: &mut impl FnMut(&mut Self))315 fn visit_depth_first_internal(&mut self, f: &mut impl FnMut(&mut Self)) { 316 match *self { 317 Self::Clamp { 318 ref mut min, 319 ref mut center, 320 ref mut max, 321 } => { 322 min.visit_depth_first_internal(f); 323 center.visit_depth_first_internal(f); 324 max.visit_depth_first_internal(f); 325 }, 326 Self::Sum(ref mut children) | Self::MinMax(ref mut children, _) => { 327 for child in &mut **children { 328 child.visit_depth_first_internal(f); 329 } 330 }, 331 Self::Leaf(..) => {}, 332 } 333 f(self); 334 } 335 336 /// Simplifies and sorts the calculation of a given node. All the nodes 337 /// below it should be simplified already, this only takes care of 338 /// simplifying directly nested nodes. So, probably should always be used in 339 /// combination with `visit_depth_first()`. 340 /// 341 /// This is only needed if it's going to be preserved after parsing (so, for 342 /// `<length-percentage>`). Otherwise we can just evaluate it using 343 /// `resolve()`, and we'll come up with a simplified value anyways. simplify_and_sort_direct_children(&mut self)344 pub fn simplify_and_sort_direct_children(&mut self) { 345 macro_rules! replace_self_with { 346 ($slot:expr) => {{ 347 let dummy = Self::MinMax(Default::default(), MinMaxOp::Max); 348 let result = mem::replace($slot, dummy); 349 *self = result; 350 }}; 351 } 352 match *self { 353 Self::Clamp { 354 ref mut min, 355 ref mut center, 356 ref mut max, 357 } => { 358 // NOTE: clamp() is max(min, min(center, max)) 359 let min_cmp_center = match min.partial_cmp(¢er) { 360 Some(o) => o, 361 None => return, 362 }; 363 364 // So if we can prove that min is more than center, then we won, 365 // as that's what we should always return. 366 if matches!(min_cmp_center, cmp::Ordering::Greater) { 367 return replace_self_with!(&mut **min); 368 } 369 370 // Otherwise try with max. 371 let max_cmp_center = match max.partial_cmp(¢er) { 372 Some(o) => o, 373 None => return, 374 }; 375 376 if matches!(max_cmp_center, cmp::Ordering::Less) { 377 // max is less than center, so we need to return effectively 378 // `max(min, max)`. 379 let max_cmp_min = match max.partial_cmp(&min) { 380 Some(o) => o, 381 None => { 382 debug_assert!( 383 false, 384 "We compared center with min and max, how are \ 385 min / max not comparable with each other?" 386 ); 387 return; 388 }, 389 }; 390 391 if matches!(max_cmp_min, cmp::Ordering::Less) { 392 return replace_self_with!(&mut **min); 393 } 394 395 return replace_self_with!(&mut **max); 396 } 397 398 // Otherwise we're the center node. 399 return replace_self_with!(&mut **center); 400 }, 401 Self::MinMax(ref mut children, op) => { 402 let winning_order = match op { 403 MinMaxOp::Min => cmp::Ordering::Less, 404 MinMaxOp::Max => cmp::Ordering::Greater, 405 }; 406 407 let mut result = 0; 408 for i in 1..children.len() { 409 let o = match children[i].partial_cmp(&children[result]) { 410 // We can't compare all the children, so we can't 411 // know which one will actually win. Bail out and 412 // keep ourselves as a min / max function. 413 // 414 // TODO: Maybe we could simplify compatible children, 415 // see https://github.com/w3c/csswg-drafts/issues/4756 416 None => return, 417 Some(o) => o, 418 }; 419 420 if o == winning_order { 421 result = i; 422 } 423 } 424 425 replace_self_with!(&mut children[result]); 426 }, 427 Self::Sum(ref mut children_slot) => { 428 let mut sums_to_merge = SmallVec::<[_; 3]>::new(); 429 let mut extra_kids = 0; 430 for (i, child) in children_slot.iter().enumerate() { 431 if let Self::Sum(ref children) = *child { 432 extra_kids += children.len(); 433 sums_to_merge.push(i); 434 } 435 } 436 437 // If we only have one kid, we've already simplified it, and it 438 // doesn't really matter whether it's a sum already or not, so 439 // lift it up and continue. 440 if children_slot.len() == 1 { 441 return replace_self_with!(&mut children_slot[0]); 442 } 443 444 let mut children = mem::replace(children_slot, Default::default()).into_vec(); 445 446 if !sums_to_merge.is_empty() { 447 children.reserve(extra_kids - sums_to_merge.len()); 448 // Merge all our nested sums, in reverse order so that the 449 // list indices are not invalidated. 450 for i in sums_to_merge.drain(..).rev() { 451 let kid_children = match children.swap_remove(i) { 452 Self::Sum(c) => c, 453 _ => unreachable!(), 454 }; 455 456 // This would be nicer with 457 // https://github.com/rust-lang/rust/issues/59878 fixed. 458 children.extend(kid_children.into_vec()); 459 } 460 } 461 462 debug_assert!(children.len() >= 2, "Should still have multiple kids!"); 463 464 // Sort by spec order. 465 children.sort_unstable_by_key(|c| c.sort_key()); 466 467 // NOTE: if the function returns true, by the docs of dedup_by, 468 // a is removed. 469 children.dedup_by(|a, b| b.try_sum_in_place(a).is_ok()); 470 471 if children.len() == 1 { 472 // If only one children remains, lift it up, and carry on. 473 replace_self_with!(&mut children[0]); 474 } else { 475 // Else put our simplified children back. 476 *children_slot = children.into_boxed_slice().into(); 477 } 478 }, 479 Self::Leaf(ref mut l) => { 480 l.simplify(); 481 }, 482 } 483 } 484 485 /// Simplifies and sorts the kids in the whole calculation subtree. simplify_and_sort(&mut self)486 pub fn simplify_and_sort(&mut self) { 487 self.visit_depth_first(|node| node.simplify_and_sort_direct_children()) 488 } 489 to_css_impl<W>(&self, dest: &mut CssWriter<W>, is_outermost: bool) -> fmt::Result where W: Write,490 fn to_css_impl<W>(&self, dest: &mut CssWriter<W>, is_outermost: bool) -> fmt::Result 491 where 492 W: Write, 493 { 494 let write_closing_paren = match *self { 495 Self::MinMax(_, op) => { 496 dest.write_str(match op { 497 MinMaxOp::Max => "max(", 498 MinMaxOp::Min => "min(", 499 })?; 500 true 501 }, 502 Self::Clamp { .. } => { 503 dest.write_str("clamp(")?; 504 true 505 }, 506 _ => { 507 if is_outermost { 508 dest.write_str("calc(")?; 509 } 510 is_outermost 511 }, 512 }; 513 514 match *self { 515 Self::MinMax(ref children, _) => { 516 let mut first = true; 517 for child in &**children { 518 if !first { 519 dest.write_str(", ")?; 520 } 521 first = false; 522 child.to_css_impl(dest, false)?; 523 } 524 }, 525 Self::Sum(ref children) => { 526 let mut first = true; 527 for child in &**children { 528 if !first { 529 if child.is_negative_leaf() { 530 dest.write_str(" - ")?; 531 let mut c = child.clone(); 532 c.negate(); 533 c.to_css_impl(dest, false)?; 534 } else { 535 dest.write_str(" + ")?; 536 child.to_css_impl(dest, false)?; 537 } 538 } else { 539 first = false; 540 child.to_css_impl(dest, false)?; 541 } 542 } 543 }, 544 Self::Clamp { 545 ref min, 546 ref center, 547 ref max, 548 } => { 549 min.to_css_impl(dest, false)?; 550 dest.write_str(", ")?; 551 center.to_css_impl(dest, false)?; 552 dest.write_str(", ")?; 553 max.to_css_impl(dest, false)?; 554 }, 555 Self::Leaf(ref l) => l.to_css(dest)?, 556 } 557 558 if write_closing_paren { 559 dest.write_str(")")?; 560 } 561 Ok(()) 562 } 563 } 564 565 impl<L: CalcNodeLeaf> PartialOrd for CalcNode<L> { partial_cmp(&self, other: &Self) -> Option<cmp::Ordering>566 fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> { 567 match (self, other) { 568 (&CalcNode::Leaf(ref one), &CalcNode::Leaf(ref other)) => one.partial_cmp(other), 569 _ => None, 570 } 571 } 572 } 573 574 impl<L: CalcNodeLeaf> ToCss for CalcNode<L> { 575 /// <https://drafts.csswg.org/css-values/#calc-serialize> to_css<W>(&self, dest: &mut CssWriter<W>) -> fmt::Result where W: Write,576 fn to_css<W>(&self, dest: &mut CssWriter<W>) -> fmt::Result 577 where 578 W: Write, 579 { 580 self.to_css_impl(dest, /* is_outermost = */ true) 581 } 582 } 583