Cache the directionality of the HTML element

Now Chromium supports :dir pseudo-class as experimental (--enable-blink-features=CSSPseudoDir) since M89. I actively worked on this feature funded by eyeo. When I was working on :dir pseudo-class on Chromium, it was necessary to solve issues regarding the performance and functionality of existing direction implementations. This posting is about explaining these issues and how I had solved them in more detail. I also had a talk about this at BlinkOn14.

What is directionality?

All HTML elements have their own directionality. Let’s see a simple example.
1) LTR
When we add explicitly a dir attribute to an element like <div dir="ltr">, or in cases where an element that doesn’t have the dir attribute inherits it from its parent that has ltr direction, the element’s directionality is ltr.
2) RTL
When we add explicitly the dir attribute to an element like <div dir="rtl">, or when an element that doesn’t have the dir attribute inherits it from its parent that has rtl direction, the element’s directionality is rtl.
3) dir=auto
The element’s directionality is resolved through its own descendants, and it is determined as the directionality of the closest descendant that can determine directionality among the descendants. This is usually a character with bidirectional information.

How do elements have directionality in Blink?

Before the element had a caching value for its direction, it depended on the direction property in ComputedStyle, and there were functionality and performance problems.
  • We didn’t know the directionality if ComputedStyle was not created yet.
  • We used it with the direction property of CSS in ComputedStyle, but not exactly the same with the element’s directionality.
  • There were cases when the directionality of the element needed to be recalculated even when there is no change in the element.
  • We need to recalculate more for :dir pseudo-class.
To solve these problems, we now cache the directionality of the element. We can see the detailed signatures in node.h. There are the rules to cache the element directionality like
  • If dir=ltr|rtl, update the directionality of the element and its descendant immediately.
  • If dir=auto, resolve the directionality and update the element and its descendant immediately.
  • If no valid dir, use the directionality of the parent before parsing children.
  • If the child is inserted with no valid dir, use the directionality of the parent.
  • Complete caching the directionality of all elements before calculating the style.
Note: We have exception handling for the <slot> element to access it via the flattened tree, but it’s still in the middle of the implementation since it is still unclear and under discussion on the Web Spec.

Improved the performance for dir=auto by reducing a calculation of the directionality

Unfortunately, there are no comprehensive measurements of how much performance has improved after caching the directionality of all elements, because it is tricky to measure. However, theoretically, this is clearly a way to improve performance. In addition, a few additional patches had a chance to measure performance and we were able to see improvement. For instance, we do not adjust directionality if the new text’s direction is the same as the old one, or doesn’t have a strong directionality and drop out of the tree walk if the node changed children is passed during traversing. The following results were obtained. You can also watch the talk online (47:40 min) presented on BlinkOn14. I will post about :dir pseudo-class when we clarify <slot> and support the feature by default on Chromium. Thanks all!

Why should we use a precise-width integer type?

Introduction
A few months ago, I’ve finished the task of replacing imprecise-width integer types like (unsigned) short, int, long, long long by precise-width integer types like (u)int16/int32/int64_t in Blink.. I’ve been working on the Onion Soup project and it was my first task of this project. When I took this task, I thought it would be comparatively simple and quite mechanical work, but this was not the case. It was sometimes required to understand whole code flow in-depth even out of blink or to explain the benefit of such changes to reviewers.

I’d like to introduce why we should prefer using the precise-width integer type and what I did for this task.

Why should we use the precise-width integer type?
We should keep in mind the fact that the c++ standards don’t specify the specific size of each integer type.

Data Model Table

Data model sizeof(int) sizeof(long) sizeof(long long) example
LP32 16b 32b 64b Win16
ILP32 32b 32b 64b Win32, i386 OSX & Linux
LP64 32b 64b 64b x86-64 OSX & Linux
LLP64 32b 32b 64b Win64

Chromium supports various platforms with one repository and shows definitely the variable of different sizes with (unsigned) long between Android-Kitkat/MacOS/Win7 buildbots and other buildbots for try-bots. It means that it would have potential security issues like the stack overflow if we treat that long has 64 bits precise since the size of long is 64 bits like long long on almost all of build systems. And we should avoid mixing the use of the precise-width integer type and the imprecise-width integer type to store the same value.

Actually, after working on this I got a report mentioning that my changes to move from imprecise-width to precise-width types fixed a security issue. This made me realize that more existing issues could still be fixed this way, and I started fixing other ones reported via ClusterFuzz after that.

Google also recommends this in its own coding styleguide, see here.

Summary of my contributions in Blink
1) Decided the order of the changing type.

unsigned short -> uint16_t / short -> int16_t
unsigned long long -> uint64_t / long long -> int64_t
unsigned long -> uint32_t or uint64_t, long -> int32_t or int64_t

2) Wrote the patch including only related codes.

3) Found what is the proper type.
Which type is proper between uint32_t and uint64_t when I should change unsigned long?
Every time I asked myself the question since I had to consider the fact that unsigned long was 32 bit on Mac, Android-kitkat and Window7 buildbot and was 64 bit on others so far. So I needed to understand its code flow and the use cases not only in Blink but also out of Blink. In general, it would be best to avoid integer-width conversions where possible and to only convert to larger types when needed.

4) Utilized the template instead of the functions for each type
I reduced the code quantity with the template and avoided the build error by duplicated definition.

5) Used base::Optional when the initial value is ambiguous.
In general the variable’s initial value would be 0 or -1, but base::Optional is more readable and simple than comparing 0 or -1 to check the initial value. Actually, I needed to reach a consensus with the review since it could change the code logic.

bool HasValidSnapshotMetadata() const { return snapshot_size_ >= 0; }
long long snapshot_size_;

Instead,

bool HasValidSnapshotMetadata() const { return snapshot_size_.has_value(); }
base::Optional<uint64_t> snapshot_size_;

6) Used CheckedNumeric to check the overflow of the variable.

static bool SizeCalculationMayOverflow(unsigned width,
                                         unsigned height,
                                         unsigned decoded_bytes_per_pixel) {
    unsigned long long total_size = static_cast<unsigned long long>(width) *
                                    static_cast<unsigned long long>(height);
    if (decoded_bytes_per_pixel == 4)
      return total_size > ((1 << 29) - 1);
    return total_size > ((1 << 28) - 1);
}

The above code was the old one before I changed and it was for checking if the variable has the overflow, I took some time to fully understand it.
I’ve used CheckedNumeric since the reviewer let me know this utility. As you can see from the code below, it has been changed to be simple and readable.

  inline bool SizeCalculationMayOverflow(unsigned width,
                                         unsigned height,
                                         unsigned decoded_bytes_per_pixel) {
    base::CheckedNumeric<int32_t> total_size = width;
    total_size *= height;
    total_size *= decoded_bytes_per_pixel;
    return !total_size.IsValid();
  }

7) Oops! MSVC!
The below code shows the different results due to compilers.

class Foo {
    uint16_t a;
    unsigned b : 16;
};
std::cout << sizeof(Foo);

The results are from clang : 4 bytes, gcc : 4 bytes and msvc : 8 bytes

So, it caused the build break with MSVC toolchain on Windows buildbots as the class size was increased. It took a long time to analyze the cause and solve this issue.

In conclusion, it was very simple to fix. See the code below.

class Foo {
    unsigned a : 16;
    unsigned b : 16;
};

8) Brought out the potential issue with with the overflow.
Blink can handle the width and height within 4 bytes range. The old code showed the abnormal layout result with overflowed width/height but it did not crash. I added the assertion code to check if there is the overflow when changing the type. Finally, we prevent the overflow and solve to layout the object’s position and size within the maximum value of 4 bytes.

9) Added PRESUBMIT check.
Now that we cleaned up the Blink code from the imprecise-width types, a PRESUBMIT hook was added to prevent them from being reintroduced to the sourcebase. So I added the PRESUBMIT check to ensure new uses do not come in again.

10) Why do we still use int and unsigned?
This is the comment of the reviewer and I also agree with it.

Thee C++ style guide states "We use int very often, for integers we know are not going to be too big, e.g., loop counters. Use plain old int for such things. You should assume that an int is at least 32 bits, but don't assume that it has more than 32 bits. If you need a 64-bit integer type, use int64_t or uint64_t."
The style guide does state not to use the imprecise-width integers like long long/long/short, but int is the imprecise-width type that is explicitly preferred. Among other reasons, this is likely for readability and the fact that ints are by default the "native"/fastest type, and potentially large concerns over code churn. More there is not any benefit to replace int to int32t and potentially large concerns over code churn.

I’m happy to contribute to Chromium & Blink with more stable code through changing to the precise-width integer type and to learn more about this particular domain.

References
[1] https://en.cppreference.com/w/cpp/language/types
[2] http://nickdesaulniers.github.io/blog/2016/05/30/data-models-and-word-size/