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

http://limpet.net/mbrubeck/2014/09/17/toy-layout-engine-6-block.html

by mbrubeck • 12 years ago

120 22 12 years ago

pcwalton3• 12 years ago

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.

hayksaakian• 12 years ago

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

userbinator2• 12 years ago

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

akavel4• 12 years ago

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 :)

userbinator2• 12 years ago

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?

jacquesm• 12 years ago

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.

pcwalton3• 12 years ago

Although you probably already knew it

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

tOkeshu• 12 years ago

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• 12 years ago

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.

nly• 12 years ago

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

ceronman• 12 years ago

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• 12 years ago

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• 12 years ago

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• 12 years ago

"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.

dubcanada• 12 years ago

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!

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

Related Stories