Let's build a browser engine, Part 6: Block layout

pcwalton · on Sept 18, 2014

I especially like the use of Rust's pattern matching here:

    match (width == auto, margin_left == auto, margin_right == auto) {
        (false, false, false) => { ... }
        (false, false, true) => { ... }
        (false, true, false) => { ... }
        (true, _, _) => { ... }
        (false, true, true) => { ... }
    }

C-style switch isn't powerful enough to handle this due to the _ wildcards, so in a language without pattern matching you'd have little choice but to fall back to a chains of ifs and Boolean operators, which would make the code hard to read (and CSS layout code is notoriously time-consuming to debug, so anything that makes code easier to read is extremely valuable in practice). The compiler checks to make sure all cases are handled too.

This sort of thing has made Servo's layout much easier to understand.

akavel · on Sept 18, 2014

In case of just booleans, in C it's possible to use a "trick"/workaround with flags/bit operators. Although certainly more cumbersome and limited. E.g.:

  #define WIDTH 4
  #define MARGIN_LEFT 2
  #define MARGIN_RIGHT 1
  ...
  unsigned int flags =
    (width ? WIDTH : 0) |
    (margin_left ? MARGIN_LEFT : 0) |
    (margin_right ? MARGIN_RIGHT : 0);
  switch (flags) {
  case 0: //...
  case MARGIN_RIGHT: //...
  case MARGIN_LEFT: //...
  case WIDTH:                 // fallthrough
   case WIDTH | MARGIN_RIGHT: // fallthrough
   case WIDTH | MARGIN_LEFT:  // fallthrough
   case WIDTH | MARGIN_RIGHT | MARGIN_LEFT:
   //...
  case MARGIN_LEFT | MARGIN_RIGHT: //...
  }

Although you probably already knew it, and I totally admit it's much uglier and "workaround-ish". It's just that after reading "isn't powerful enough [...]" I felt a compulsory urge to show that It Can Be Done, and couldn't resist, sorry :)

userbinator · on Sept 18, 2014

Using a switch on an encoded value was my first thought too after seeing the pattern, and I think it's actually quite an elegant way of doing it - forming an array index from booleans and doing a table lookup with that. It's even clearer when the cases are ordered as

    (false, false, false) => { ... }  // 0
    (false, false, true ) => { ... }  // 1
    (false, true , false) => { ... }  // 2
    (false, true , true ) => { ... }  // 3
    (true , _    , _    ) => { ... }  // 4-7 (could be the default case)

Here's a possible small improvement that could, depending on the compiler, get rid of a few branches:

    #define WIDTH_BIT 2
    #define WIDTH (1<<WIDTH_BIT)
    #define MARGIN_LEFT_BIT 1
    #define MARGIN_LEFT (1<<MARGIN_LEFT_BIT)
    #define MARGIN_RIGHT_BIT 0
    #define MARGIN_RIGHT (1<<MARGIN_RIGHT_BIT)
    ...
    unsigned int flags = !!width << WIDTH_BIT
                       | !!margin_left << MARGIN_LEFT_BIT
                       | !!margin_right << MARGIN_RIGHT_BIT;
    ...

I'm not too familiar with Rust and Google isn't being helpful, so does anyone know how the Rust compiler implements pattern matching? Does it do something like the above or does it resort to if/else conversion?

pcwalton · on Sept 18, 2014

Rust uses OCaml's algorithm for pattern matching, which is basically a dynamic programming algorithm that minimizes the number of branches. (It's really clever, worth reading about if you're bored.) The Rust compiler also contains heuristics to decide whether to use a jump table (LLVM switch statement) or not.

akavel · on Sept 18, 2014

Is it 100% sure that !! gives only 0 or 1? I'd be very grateful for some hard citations/references for that (across various standards, C89/99/..., C++98/03/11...), I'd be happy to learn if I can safely rely on that?

ben0x539 · on Sept 19, 2014

C99: 6.5.3.3 p5: The result of the logical negation operator ! is 0 if the value of its operand compares unequal to 0, 1 if the value of its operand compares equal to 0. The result has type int. The expression !E is equivalent to (0==E).

C++11 (or a near enough draft): 5.3.1 p9: The operand of the logical negation operator ! is contextually converted to bool (Clause 4); its value is true if the converted operand is false and false otherwise. The type of the result is bool.

and 4.7 p4 on integral conversion: If the source type is bool, the value false is converted to zero and the value true is converted to one.

Both seem to suggest that when you apply !, you end up with something that is 0 or 1 when used as a number, and adding more ! won't get you out of that.

akavel · on Sept 19, 2014

Thanks a lot! And still interested in earlier C/C++ standards, I'm much more likely to encounter them in the wild for long time.

ben0x539 · on Sept 19, 2014

Ah, sorry. Looks like C++03 has the same wording in the same sections as C++11, and ANSI C's Unary arithmetic operators section is numbered 3.3.3.3 and also has the same wording as C99.

akavel · on Sept 19, 2014

Great, thanks!

jacquesm · on Sept 18, 2014

I find that a lot easier to follow than the isolated 'true' and 'false' values in the rust code, especially considering that if you have any code at all in the body of such an 8 pronged switch the header will surely scroll out of view by the time you get to the bottom entries.

pcwalton · on Sept 18, 2014

> Although you probably already knew it

No, I didn't. Clever! I love Hacker News sometimes :)

tOkeshu · on Sept 18, 2014

I generally find that using tuples of booleans this way is (sometimes) blurring the intent. Indeed, not only you have to keep in mind which boolean value correspond to which variable, but you also have to not forget what's the meaning of true and false here.

So what about the following?:

    match (width, margin_left, margin_right) {
        (auto, _, _) => { ... }
        (_, auto, auto) => { ... }
        (_, auto, _) => { ... }
        (_, _, auto) => { ... }
        (_, _, _) => { ... }
    }

Now that I write this, I can understand this style is trickier as the order here is critical. The "debate" between `match` and `if` reminds me of the same one that exists in Erlang, where I saw people more often use `case of` with booleans instead of `if`.

Moreover, is there any performance issue with matching auto for every tuple?

mercurial · on Sept 18, 2014

I thought about aliasing true to width_is_auto/margin_right_is_auto, margin_left_is_auto, but sadly you don't seem to be able to use the aliases as patterns with my version of Rust.

dbaupp · on Sept 18, 2014

Using static variables like

  static width_is_auto: bool = true;

should work.

ceronman · on Sept 18, 2014

I really like Rust's pattern matching, but my opinion on this particular part of the code is exactly the opposite. I think it would have been more readable if it used simple if statements:

    if (width == auto) {
        ...
    }
    else if (margin_left == auto && margin_right == auto) {
        ...
    }
    else if (margin_left == auto) {
        ...
    }
    else if (margin_right == auto) {
        ...
    }
    else {
        ...
    }

Perhaps I'm not very used to the pattern matching notation.

8_hours_ago · on Sept 18, 2014

The code from the article has comments at the beginning of each block, which makes it very easy to read to me. But of course, that requires the programmer to actually write comments and keep them up-to-date. I bet you could write some incredible spaghetti code with this style of pattern matching. The if statements you wrote are at least somewhat self-documenting, and harder to shoot yourself in the foot with.

mbrubeck · on Sept 19, 2014

I agree this is more readable on its own, but it no longer matches the order of the prose in the CSS spec. One of my goals was easy comparison against the specification text.

dllthomas · on Sept 18, 2014

"C-style switch isn't powerful enough to handle this due to the _ wildcards"

Doesn't fallthrough enable you to implement wildcards? You still have to exhaustively list every option, but that's not hard here.

nly · on Sept 18, 2014

Just combine the booleans in to an integer and then switch-case 0 to 7.

hayksaakian · on Sept 18, 2014

at first i thought:

in a language like javascript, this is could one use for objects;

o = {}

o[true, true, true] = function(){something} ... and so on

then do

o[[width, margin_left, margin_right]]()

on second thought:

the biggest strength i see in rust is the wild card, making the switch statement much more useful than in other languages

userbinator · on Sept 18, 2014

JS does not have multidimensional arrays but it does have a comma operator. "o[true, true, true]" won't do what you want.

dubcanada · on Sept 18, 2014

This is by far my favorite rust series. Though probably the only one I've seen, ignoring that it's absolutely amazing.

Really nice job!