DevUI is a team with both design and engineering perspectives, serving huawei DevCloud platform and huawei internal background systems, as well as designers and front-end engineers. Add devui Helper (Devui-Official) DevUIHelper plugin: Devuihelper-lsp (welcome Star)

The introduction

There’s a classic interview question at the front: What happens when you type in a URL in the browser’s address bar and end up on the page?

In the middle is the process of getting the HTML text returned from the background, which is parsed into a DOM tree by the browser rendering engine, and the CSS in the HTML is parsed into a style tree, and then the DOM tree and the style tree are combined into a layout tree, and finally drawn to the browser palette by the drawing program.

This article through hands-on practice, teach you step by step to implement a mini version of the browser engine, and then in-depth understanding of the working principle of the rendering engine, full of dry things.

It is mainly divided into seven parts:

  • Part one: Getting started
  • Part two: HTML
  • Part three: CSS
  • Part four: Style
  • Part five: The Box
  • Part 6: Block layout
  • Part seven: Drawing 101

Part one: Getting started

I’m building a “toy” rendering engine, and I think you should do the same. This is the first in a series of articles.

The full article series will describe the code I wrote and show you how to write your own. But first, let me explain why.

What are you building?

Let’s talk about terminology. A browser engine is the part of a Web browser that works “at the bottom”, taking web pages from the Internet and converting their content into a form that can be read, watched, listened to, and so on. Blink, Gecko, WebKit, and Trident are all browser engines. By contrast, the browser’s own user interface (tabs, toolbars, menus, etc.) is called Chrome. Firefox and SeaMonkey are two browsers that use different Chrome but the same Gecko engine.

The browser engine includes many sub-components: AN HTTP client, an HTML parser, a CSS parser, a JavaScript engine (itself made up of parsers, interpreters, and compilers), and so on. Components that are involved in parsing Web formats such as HTML and CSS and turning them into what you see on the screen are sometimes called layout engines or rendering engines.

Why a “toy” rendering engine?

A fully functional browser engine is complex. Blink, Gecko, WebKit, they each have millions of lines of code. Younger, simpler rendering engines such as Servo and WeasyPrint also have tens of thousands of rows. This is not easy for a novice to understand!

Speaking of very complex software: If you’ve taken a compiler or operating system course, you’ve probably created or modified a “toy” compiler or kernel at some point. This is a simple model for learning; It may never be managed by anyone other than the author. but

Making a toy system is a useful tool for understanding how real things work.

Even if you’ve never built a real compiler or kernel,

Understanding how they work can also help you make better use of them when writing your own programs.

So if you want to be a browser developer, or just want to understand what’s going on inside the browser engine, why not build a toy? Just like toy compilers that implement a subset of “real” programming languages, toy rendering engines can implement small portions of HTML and CSS. It won’t replace the engine in everyday browsers, but it should illustrate the basic steps needed to render a simple HTML document.

Try it at home.

I hope I’ve convinced you to give it a try. If you already have some solid programming experience and know some advanced HTML and CSS concepts, this series will be easy to follow. However, if you’re just starting to learn these things, or come across something you don’t understand, feel free to ask questions and I’ll try to make it clearer.

Before you begin, I’d like to tell you about some of the options available to you:

About Programming Languages

You can build a toy layout engine in any programming language, really! Use a language you know and love. If that sounds like fun, so can you

Use this as an excuse to learn a new language.

If you want to start contributing to major browser engines such as Gecko or WebKit, you may want to use C++ because C++ is the primary language used in those engines and it makes it easier to compare your code to theirs.

My own toy project, Robinson, was written in Rust. I’m a member of Mozilla’s Servo team, so I’m a big fan of Rust programming. In addition, one of my goals in creating this project was to learn more about Servo’s implementation. Robinson sometimes used simplified versions of Servo’s data structures and code.

Libraries and shortcuts

In this learning exercise, you have to decide whether to use someone else’s code or write your own code from scratch. Here’s my advice

Write your own code for the parts you really want to understand, but don’t be shy about using libraries for the rest.

Learning how to use a particular library is a valuable exercise in itself.

I wrote Robinson not just for myself, but as example code for these articles and exercises. For one reason or another, I wanted it to be as small and independent as possible. So far, I haven’t used any external code outside of the Rust standard library. (This also avoids the minor hassle of building multiple dependencies using the same version of Rust, which is still under development.) However, the rule is not set in stone. For example, I might later decide to use a graphics library instead of writing my own low-level drawing code.

Another way to avoid writing code is to omit something. Robinson, for example, does not yet have network code; It can only read local files. In a toy program, if you want to skip something, you can skip it. I’ll point out similar potential shortcuts during the discussion so you can skip the uninteresting steps and jump right to the good stuff. If you change your mind, you can fill in the blanks later.

Step 1: DOM

Are you ready to code? We’ll start with something small: the DOM’s data structure. Let’s look at Robinson’s DOM module.

The DOM is a tree of nodes. A node has zero or more child nodes. (It has various other properties and methods, but we can ignore most of them for now.)

struct Node {
  // data common to all nodes:
  children: Vec<Node>,

  // data specific to each node type:
  node_type: NodeType,
}
Copy the code

There are several node types, but for now we’ll ignore most of them and define nodes as element nodes or text nodes. In languages with inheritance, these are Node subtypes. In Rust, they can be enumerated enums (Rust’s keyword is used for “tagged Union” or “sum type”) :

enum NodeType {
  Text(String),
  Element(ElementData),
}
Copy the code

The element contains a tag name and any number of attributes that can be stored as a name-to-value mapping. Robinson doesn’t support namespaces, so it just stores tag and attribute names as simple strings.

struct ElementData {
    tag_name: String,
    attributes: AttrMap,
}

type AttrMap = HashMap<String, String>;
Copy the code

Finally, some constructors make it easy to create new nodes:

fn text(data: String) -> Node {
    Node { children: Vec::new(), node_type: NodeType::Text(data) }
}

fn elem(name: String, attrs: AttrMap, children: Vec<Node>) -> Node {
    Node {
        children: children,
        node_type: NodeType::Element(ElementData {
            tag_name: name,
            attributes: attrs,
        })
    }
}
Copy the code

This is it! A full-fledged DOM implementation will contain more data and dozens of methods, but that’s all we need to get started.

practice

These are just a few tips to follow at home. Do exercises that interest you and skip the ones that don’t.

  1. Start a new program in the language of your choice and write code to represent DOM text nodes and tree of elements.

  2. Install the latest version of Rust, then download and build Robinson. Open dom.rs and extend NodeType to include other types, such as comment nodes.

  3. Write code to beautify the DOM node tree.

In the next article, we’ll add a parser that converts HTML source code into a tree of these DOM nodes.

reference

For more details on the internals of the browser engine, see Tali Garsiel’s excellent how browsers work and links to more resources.

For example code, here is a short list of “small” open source Web rendering engines. Most of them are many times larger than Robinson, but still much smaller than Gecko or WebKit. With only 2000 lines of code, WebWhirr is the only one I call a “toy” engine.

  • CSSBox (Java)
  • Cocktail (Haxe)
  • gngr (Java)
  • litehtml (c++)
  • LURE (Lua)
  • NetSurf (C)
  • Servo (Rust)
  • Simple San Simon (Haskell)
  • WeasyPrint (Python)
  • WebWhirr (C++)

You may find these useful inspirations or references. If you know of any other similar projects, or if you are starting your own, please let me know!

Part two: HTML

This is the second article in a series on building a toy browser rendering engine.

This article is about parsing HTML source code to generate a DOM node tree. Parsing is a fascinating topic, but I don’t have the time or expertise to cover it. You can get a detailed introduction to parsing from any good course or book on compilers. Or get your hands dirty by reading the documentation for parser generators that work with your programming language of choice.

HTML has its own unique parsing algorithm. Unlike parsers for most programming languages and file formats, HTML parsing algorithms do not reject invalid input. Instead, it contains specific error-handling instructions, so web browsers can agree on how to display every Web page, even those that don’t follow syntactical rules. Web browsers must do this before they can be used: because nonconforming HTML was supported in the early days of the Web, most existing Web pages now use it.

Simple HTML dialect

I didn’t even try to implement a standard HTML parsing algorithm. Instead, I wrote a basic parser for a small section of HTML syntax. My parser can handle simple pages like this:

<html> <body> <h1>Title</h1> <div id="main" class="test"> <p>Hello <em>world</em>! </p> </div> </body> </html>Copy the code

The following syntax is allowed:

  • Closed label:< p >... </p>
  • Quoted attributes:id="main"
  • Text node:<em>world</em>

All other content is not supported, including:

  • comments
  • Doctype declaration
  • Escape characters such as&amp;) and CDATA sections
  • Closing label:<br/>or<br>No closing tag
  • Error handling (such as unclosed or improperly nested labels)
  • Namespaces and other XHTML syntax:<html:body>
  • Character code detection

At each stage of the project, I wrote more or less the minimum code needed to support the later stages. But if you want to learn more about analytical theory and tools, you can be even more ambitious in your own projects!

The sample code

Next, let’s review my HTML parser, remembering that this is only one way (and probably not the best way). Its structure is loosely based on the Tokenizer module in Servo’s CSsparser library. It has no real error handling; In most cases, it simply breaks when it encounters unexpected syntax. The code is written in Rust, but I expect it to be reasonably readable to someone using a similar language such as Java, C++, or C#. It uses the DOM data structure from Part 1.

The parser stores its input string and current position in the string. The position is the index of the next character we haven’t processed yet.

struct Parser {
    pos: usize, // "usize" is an unsigned integer, similar to "size_t" in C
    input: String,
}
Copy the code

We can use it to implement some simple methods to peek into the next character in the input:

impl Parser { // Read the current character without consuming it. fn next_char(&self) -> char { self.input[self.pos..] .chars().next().unwrap() } // Do the next characters start with the given string? fn starts_with(&self, s: &str) -> bool { self.input[self.pos ..] .starts_with(s) } // Return true if all input is consumed. fn eof(&self) -> bool { self.pos >= self.input.len() } // ...  }Copy the code

Rust strings are stored as UTF-8-byte arrays. To get to the next character, we can’t just go one byte forward. Instead, we use char_indices to properly handle multi-byte characters. (If our string uses fixed-width characters, we can just increment pos by 1.)

// Return the current character, and advance self.pos to the next character. fn consume_char(&mut self) -> char { let mut iter = self.input[self.pos..] .char_indices(); let (_, cur_char) = iter.next().unwrap(); let (next_pos, _) = iter.next().unwrap_or((1, ' ')); self.pos += next_pos; return cur_char; }Copy the code

Usually we want to use a contiguous string. The consume_while method takes the characters that satisfy the given condition and returns them as strings. The argument to this method is a function that takes a char and returns a bool.

// Consume characters until `test` returns false. fn consume_while<F>(&mut self, test: F) -> String where F: Fn(char) -> bool { let mut result = String::new(); while ! self.eof() && test(self.next_char()) { result.push(self.consume_char()); } return result; }Copy the code

We can use it to ignore sequences of Spaces, or to use alphanumeric strings:

// Consume and discard zero or more whitespace characters. fn consume_whitespace(&mut self) { self.consume_while(CharExt::is_whitespace); } // Parse a tag or attribute name. fn parse_tag_name(&mut self) -> String { self.consume_while(|c| match c { 'a'... 'z' | 'A'... 'Z' | '0'... '9' => true, _ => false }) }Copy the code

Now we are ready to start parsing the HTML. To parse a single node, we look at its first character to see whether it is an element node or a text node. In our simplified version of HTML, text nodes can contain any character except <.

// Parse a single node. fn parse_node(&mut self) -> dom::Node { match self.next_char() { '<' => self.parse_element(), _ => self.parse_text() } } // Parse a text node. fn parse_text(&mut self) -> dom::Node { dom::text(self.consume_while(|c| c ! ))} = '<'Copy the code

One element is more complex. It includes the start and end tags, and any number of child nodes between them:

// Parse a single element, including its open tag, contents, and closing tag. fn parse_element(&mut self) -> dom::Node { // Opening tag. assert! (self.consume_char() == '<'); let tag_name = self.parse_tag_name(); let attrs = self.parse_attributes(); assert! (self.consume_char() == '>'); // Contents. let children = self.parse_nodes(); // Closing tag. assert! (self.consume_char() == '<'); assert! (self.consume_char() == '/'); assert! (self.parse_tag_name() == tag_name); assert! (self.consume_char() == '>'); return dom::elem(tag_name, attrs, children); }Copy the code

In our simplified syntax, parsing properties is easy. Before reaching the end of the opening tag (>), we repeatedly look for the name followed by =, and then the string enclosed in quotes.

// Parse a single name="value" pair. fn parse_attr(&mut self) -> (String, String) { let name = self.parse_tag_name(); assert! (self.consume_char() == '='); let value = self.parse_attr_value(); return (name, value); } // Parse a quoted value. fn parse_attr_value(&mut self) -> String { let open_quote = self.consume_char(); assert! (open_quote == '"' || open_quote == '\''); let value = self.consume_while(|c| c ! = open_quote); assert! (self.consume_char() == open_quote); return value; } // Parse a list of name="value" pairs, separated by whitespace. fn parse_attributes(&mut self) -> dom::AttrMap { let mut attributes = HashMap::new(); loop { self.consume_whitespace(); if self.next_char() == '>' { break; } let (name, value) = self.parse_attr(); attributes.insert(name, value); } return attributes; }Copy the code

To resolve the child nodes, we recursively call parse_node in the loop until the end tag is reached. This function returns a Vec, which is the name of the growable array of Rust pairs.

// Parse a sequence of sibling nodes.
fn parse_nodes(&mut self) -> Vec<dom::Node> {
    let mut nodes = Vec::new();
    loop {
        self.consume_whitespace();
        if self.eof() || self.starts_with("</") {
            break;
        }
        nodes.push(self.parse_node());
    }
    return nodes;
}
Copy the code

Finally, we can put all this together and parse the entire HTML document into a DOM tree. If the document does not explicitly contain a root node, this function creates the root node for the document; This is similar to the functionality of a real HTML parser.

// Parse an HTML document and return the root element.
pub fn parse(source: String) -> dom::Node {
    let mut nodes = Parser { pos: 0, input: source }.parse_nodes();

    // If the document contains a root element, just return it. Otherwise, create one.
    if nodes.len() == 1 {
        nodes.swap_remove(0)
    } else {
        dom::elem("html".to_string(), HashMap::new(), nodes)
    }
}
Copy the code

That’s it! Robinson HTML parser all the code. The entire program is just over 100 lines of code (not including blank lines and comments). If you use a good library or parser generator, you can probably build a similar toy parser in less space.

practice

Here are some alternatives you can try on your own. As before, you can select one or more of these and ignore the others.

  1. Build a parser that takes a subset of HTML as input and generates a tree of DOM nodes (” manually “or using a library or parser generator).

  2. Modify Robinson’s HTML parser to add some missing features, such as comments. Or replace it with a better parser, perhaps built with a library or generator.

  3. Create an invalid HTML file that causes your (or my) parser to fail. Modify the parser to recover from errors and generate a DOM tree for the test file.

A shortcut

If you want to skip parsing entirely, you can build the DOM tree programmatically and add code to your program that looks like this (pseudocode, adjusted to match the DOM code you wrote in Part 1) :

// <html><body>Hello, world! </body></html> let root = element("html"); let body = element("body"); root.children.push(body); body.children.push(text("Hello, world!" ));Copy the code

Or you can find an existing HTML parser and incorporate it into your program.

The next article in this series will cover CSS data structures and parsing.

Part three: CSS

This is the third article in a series on building a toy browser rendering engine.

This article describes the code used to read cascading style sheets (CSS). As usual, I won’t try to cover everything in the specification. Instead, I try to implement enough to illustrate some concepts and generate input for the later rendering pipeline.

Profiling style sheets

Here is an example of CSS source code:

h1, h2, h3 { margin: auto; color: #cc0000; }
div.note { margin-bottom: 20px; padding: 10px; }
#answer { display: none; }
Copy the code

Next, I’ll browse the CSS modules from my toy browser engine Robinson. While these concepts can be easily translated into other programming languages, the code is written in Rust. Reading the previous article may help you understand some of the code below.

A CSS style sheet is a series of rules. (In the example stylesheet above, each line contains one rule.)

struct Stylesheet {
    rules: Vec<Rule>,
}
Copy the code

A rule consists of one or more selectors separated by commas, followed by a series of declarations enclosed in braces.

struct Rule {
    selectors: Vec<Selector>,
    declarations: Vec<Declaration>,
}
Copy the code

A selector can be a simple selector or a chain of selectors joined by combinators. Robinson currently supports only simple selectors.

Note: Confusingly, the new Selectors Level 3 standard uses the same terminology to mean something slightly different. In this article, I mainly refer to CSS2.1. Although outdated, it is a useful starting point because it is smaller and more independent (compared to CSS3, which is broken down into countless interdependent and CSS2.1 specifications).

In Robinson, a simple selector can include a tag name, an ID prefixed with ‘#’, any number of class names prefixed with ‘.’, or a combination of the above. If the label name is empty or ‘*’, then it is a ‘universal selector’ and can match any label.

There are many other types of selectors (especially in CSS3), but this will do for now.

enum Selector {
    Simple(SimpleSelector),
}

struct SimpleSelector {
    tag_name: Option<String>,
    id: Option<String>,
    class: Vec<String>,
}
Copy the code

A declaration is just a name/value pair, separated by a colon and terminated by a semicolon. For example, “margin: auto;” It’s a statement.

struct Declaration {
    name: String,
    value: Value,
}
Copy the code

My toy engine only supports a small number of CSS value types.

enum Value {
    Keyword(String),
    Length(f32, Unit),
    ColorValue(Color),
    // insert more values here
}

enum Unit {
    Px,
    // insert more units here
}

struct Color {
    r: u8,
    g: u8,
    b: u8,
    a: u8,
}
Copy the code

Note: u8 is an 8-bit unsigned integer and F32 is a 32-bit floating point number.

All other CSS syntax is not supported, including @-rules, comments, and any selectors/values/units not mentioned above.

parsing

CSS has a regular syntax that makes it easier to parse correctly than its quirky cousin, HTML. When a standards-compliant CSS parser encounters a parsing error, it discards the unrecognized portion of the stylesheet but still processes the rest. This is useful because it allows the stylesheet to include the new syntax but still produce well-defined output in older browsers.

Robinson uses a very simple (and completely non-standard) parser, built in the same way as the HTML parser in Part 2. Instead of repeating the entire process line by line, I’ll paste snippets of code. For example, here is the code to parse a single selector:

// Parse one simple selector, e.g.: `type#id.class1.class2.class3` fn parse_simple_selector(&mut self) -> SimpleSelector { let mut selector = SimpleSelector  { tag_name: None, id: None, class: Vec::new() }; while ! self.eof() { match self.next_char() { '#' => { self.consume_char(); selector.id = Some(self.parse_identifier()); } '.' => { self.consume_char(); selector.class.push(self.parse_identifier()); } '*' => { // universal selector self.consume_char(); } c if valid_identifier_char(c) => { selector.tag_name = Some(self.parse_identifier()); } _ => break } } return selector; }Copy the code

Note that there is no error checking. Some ill-formed input, such as ### or *foo*, will parse successfully and produce strange results. A real CSS parser would discard these invalid selectors.

priority

Priority is one of the ways the rendering engine decides which style overrides the other in a collision. If a stylesheet contains rules for two matching elements, the rule with the higher priority matching selector can override the values in the lower priority selector.

The priority of a selector is based on its component. ID selectors have higher priority than class selectors, and class selectors have higher priority than label selectors. The more selectors in each “hierarchy,” the higher the priority.

pub type Specificity = (usize, usize, usize);

impl Selector {
    pub fn specificity(&self) -> Specificity {
        // http://www.w3.org/TR/selectors/#specificity
        let Selector::Simple(ref simple) = *self;
        let a = simple.id.iter().count();
        let b = simple.class.len();
        let c = simple.tag_name.iter().count();
        (a, b, c)
    }
}
Copy the code

(If we support chain selectors, we can calculate the priority of the chain by adding the priorities of the parts of the chain.)

The selector for each rule is stored in the sorted vector, with the highest priority taking precedence. This is very important for matching, which I’ll cover in the next article.

// Parse a rule set: `<selectors> { <declarations> }`. fn parse_rule(&mut self) -> Rule { Rule { selectors: self.parse_selectors(), declarations: self.parse_declarations() } } // Parse a comma-separated list of selectors. fn parse_selectors(&mut self) -> Vec<Selector> { let mut selectors = Vec::new(); loop { selectors.push(Selector::Simple(self.parse_simple_selector())); self.consume_whitespace(); match self.next_char() { ',' => { self.consume_char(); self.consume_whitespace(); } '{' => break, // start of declarations c => panic! ("Unexpected character {} in selector list", c) } } // Return selectors with highest specificity first, for use in matching. selectors.sort_by(|a,b| b.specificity().cmp(&a.specificity())); return selectors; }Copy the code

The rest of the CSS parser is fairly simple. You can read the full article on GitHub. If you haven’t done so in Part 2, now is a good time to try parser generators. My hand-volume parser does the job of a simple sample file, but it has so many bugs that it will fail badly if you violate its assumptions. One day, I might replace it with rust-peg or something similar.

practice

As before, you should decide which exercises you want to do and skip the rest:

  1. Implement your own simplified CSS parser and priority calculation.

  2. Extends Robinson’s CSS parser to support more values, or one or more selector combinators.

  3. Extend the CSS parser to discard any declarations that contain parsing errors, and follow the error handling rules to continue parsing after the declaration.

  4. Have the HTML parser pass the contents of any

A shortcut

As in Part 2, you can skip parsing CSS data structures by hardcoding them directly into your program, or you can write them using alternative formats such as JSON that already have parsers.

To be continued

The next article will cover the Style module. This is where everything starts to come together, with selector matches to apply CSS styles to DOM nodes.

This series could slow down quickly because I’ll be busy later in the month, and I haven’t even written code for some upcoming articles. I’ll get them here as soon as possible!

Part four: Style

Welcome back to my series of articles on building your own toy browser engine.

This article introduces what the CSS standard calls assigning property values, which IS what I call a style module. This module takes DOM nodes and CSS rules as input and matches them to determine the value of each CSS property for any given node.

This section doesn’t contain a lot of code, because I didn’t implement the really complicated parts. However, I think the rest is still interesting, and I’ll explain how some of the missing pieces are implemented.

The style tree

The output of Robinson’s style module is what I call a style tree. Each node in the tree contains a pointer to the DOM node and its CSS property value:

// Map from CSS property names to values.
type PropertyMap = HashMap<String, Value>;

// A node with associated style data.
struct StyledNode<'a> {
    node: &'a Node, // pointer to a DOM node
    specified_values: PropertyMap,
    children: Vec<StyledNode<'a>>,
}
Copy the code

What are these ‘a’s? These are lifetimes, which is part of the reason why Rust ensures that Pointers are memory-safe without needing to do garbage collection. If you don’t work in Rust, you can ignore them; What they mean to the code is not important.

Instead of creating a new tree, we could add new fields to the DOM ::Node structure, but I want to keep the style code away from the early “lessons”. This also gives me the opportunity to discuss parallel trees in most rendering engines.

A browser engine module typically takes a tree as input and produces a different but related tree as output. For example, Gecko’s layout code takes a DOM tree and generates a frame tree, which it then uses to build a view tree. Blink and WebKit convert DOM trees to render trees. The later stages of all these engines produce more trees, both layer and part trees.

After we have completed more stages, the pipeline for our toy browser engine will look like this:

In my implementation, each node in the DOM tree has only one node in the style tree. But in the more complex pipeline phase, several input nodes may decompose into a single output node. Or an input node may be expanded to several output nodes, or skipped altogether. For example, a style tree can exclude elements whose attribute is set to ‘None’ from being displayed. (Instead, I’ll remove this during the layout phase, because it will make my code a little simpler.)

Selector matching

The first step in building a style tree is selector matching. This should be easy because my CSS parser only supports simple selectors. You can tell if a simple selector matches an element by looking at the element itself. Matching compound selectors traverse the DOM tree to see siblings, parents, and so on.

fn matches(elem: &ElementData, selector: &Selector) -> bool {
    match *selector {
        Simple(ref simple_selector) => matches_simple_selector(elem, simple_selector)
    }
}
Copy the code

To help, we’ll add some handy ids and class accessors to the DOM element types. The class attribute can contain multiple space-separated class names that we return in the hash table.

impl ElementData {
    pub fn id(&self) -> Option<&String> {
        self.attributes.get("id")
    }

    pub fn classes(&self) -> HashSet<&str> {
        match self.attributes.get("class") {
            Some(classlist) => classlist.split(' ').collect(),
            None => HashSet::new()
        }
    }
}
Copy the code

To test whether a simple selector matches an element, simply look at each selector component and return false if the element has no matching class, ID, or tag name.

fn matches_simple_selector(elem: &ElementData, selector: &SimpleSelector) -> bool { // Check type selector if selector.tag_name.iter().any(|name| elem.tag_name ! = *name) { return false; } // Check ID selector if selector.id.iter().any(|id| elem.id() ! = Some(id)) { return false; } // Check class selectors let elem_classes = elem.classes(); if selector.class.iter().any(|class| ! elem_classes.contains(&**class)) { return false; } // We didn't find any non-matching selector components. return true; }Copy the code

Note: This function uses the any method, which returns true if the iterator contains an element that passes the provided test. This is the same as the any function in Python (or Haskell) or the some method in JavaScript.

Building a style tree

Next, we need to traverse the DOM tree. For each element in the tree, we search the stylesheet for matching rules.

When comparing two rules that match the same element, we need to use the highest priority selector from each match. Since our CSS parser stores selectors in ascending order of priority, we can stop as soon as we find a matching selector and return its priority and a pointer to the rule.

type MatchedRule<'a> = (Specificity, &'a Rule);

// If `rule` matches `elem`, return a `MatchedRule`. Otherwise return `None`.
fn match_rule<'a>(elem: &ElementData, rule: &'a Rule) -> Option<MatchedRule<'a>> {
    // Find the first (highest-specificity) matching selector.
    rule.selectors.iter()
        .find(|selector| matches(elem, *selector))
        .map(|selector| (selector.specificity(), rule))
}
Copy the code

To find all the rules that match an element, we call it filter_map, which does a linear scan of the stylesheet, checking each rule and excluding rules that don’t match. A real browser engine would speed things up by storing rules in multiple hash tables based on tag names, IDS, classes, and so on.

// Find all CSS rules that match the given element.
fn matching_rules<'a>(elem: &ElementData, stylesheet: &'a Stylesheet) -> Vec<MatchedRule<'a>> {
    stylesheet.rules.iter().filter_map(|rule| match_rule(elem, rule)).collect()
}
Copy the code

Once you have a matching rule, you can find the specified value for the element. We insert the attribute values for each rule into the HashMap. We sort matches by priority, so that more specific rules are processed after less specific rules and can override their values in the HashMap.

// Apply styles to a single element, returning the specified values.
fn specified_values(elem: &ElementData, stylesheet: &Stylesheet) -> PropertyMap {
    let mut values = HashMap::new();
    let mut rules = matching_rules(elem, stylesheet);

    // Go through the rules from lowest to highest specificity.
    rules.sort_by(|&(a, _), &(b, _)| a.cmp(&b));
    for (_, rule) in rules {
        for declaration in &rule.declarations {
            values.insert(declaration.name.clone(), declaration.value.clone());
        }
    }
    return values;
}
Copy the code

We now have everything we need to traverse the DOM tree and build the style tree. Note that the selector match is valid only for elements, so the specified value of the text node is just an empty map.

// Apply a stylesheet to an entire DOM tree, returning a StyledNode tree.
pub fn style_tree<'a>(root: &'a Node, stylesheet: &'a Stylesheet) -> StyledNode<'a> {
    StyledNode {
        node: root,
        specified_values: match root.node_type {
            Element(ref elem) => specified_values(elem, stylesheet),
            Text(_) => HashMap::new()
        },
        children: root.children.iter().map(|child| style_tree(child, stylesheet)).collect(),
    }
}
Copy the code

That’s all the code Robinson used to build the style tree. I’ll discuss some obvious omissions next.

cascade

A style sheet provided by the author of a Web page is called an author style sheet. In addition, the browser provides default styles through user agent style sheets. They may allow users to add custom styles through user stylesheets such as Gecko’s UserContent.css.

The cascade defines which of these three “origins” takes precedence over the other. There are six levels of cascades: one for each origin’s “normal” declaration, and one for each origin! Important statement.

Robinson’s style code does not cascade; All it needs is a stylesheet. The lack of a default style sheet means that HTML elements will not have any of the default styles you might expect. For example, the contents of the element are not hidden unless you explicitly add this rule to your stylesheet:

head { display: none; }
Copy the code

Implementing the cascade should be fairly simple: just trace the origin of each rule and sort the statements according to origin and importance, as well as particularity. A simplified, two-level cascade should suffice to support the most common case: the plain user agent style and the plain author style.

Calculate the value of the

In addition to the “specified values” mentioned above, CSS also defines initial values, calculated values, used values, and actual values.

The initial value is the default value for attributes that are not specified in the cascade. The computed value is based on the specified value, but some property-specific normalization rules may be applied.

As defined in the CSS specification, implementing these correctly requires separate code for each property. This work is necessary for a real browser engine, but I wanted to avoid it in this toy project. At a later stage, when the specified values are missing, the code that uses them will (to some extent) emulate the initial values by using the default values.

The used and actual values are calculated during and after the layout, which I’ll cover in a future article.

inheritance

How do text nodes get colors, fonts, and other styles if they can’t match a selector? The answer is inheritance.

When an attribute is inherited, any node that does not have a cascading value receives the parent value of the attribute. Some attributes, such as ‘color’, are inherited by default; Other parameters are used only when the special value inherit is specified for cascading.

My code does not support inheritance. To implement this, you pass the style data of the parent class to the specified_values function and use a hard-coded lookup table to determine which attributes should be inherited.

Style properties

Any HTML element can contain a style attribute that contains a list of CSS declarations. There are no selectors because these declarations automatically apply only to the elements themselves.

<span style="color: red; background: yellow;" >Copy the code

If you want to support the style attribute, check it using the specified_values function. If it exists, it is passed from the CSS parser to parse_declarations. Apply the result declaration after the normal author declaration, because properties are more specific than any CSS selector.

practice

In addition to writing your own selector matching and value assignment code, you can implement one or more of the missing parts discussed above in your own projects or in Robinson’s branch:

  1. cascade
  2. Initial and/or calculated values
  3. inheritance
  4. Style properties

In addition, if you extended the CSS parser from Part 3 to include compound selectors, you can now match those compound selectors.

To be continued

Part 5 covers the layout module. I haven’t finished the code yet, so there will be another delay before I start writing this article. I plan to split the layout into at least two articles (one block layout and one possibly inline layout).

In the meantime, I’d love to see anything you create based on these articles or exercises. If your code is somewhere, please add a link below! So far, I’ve seen Martin Tomasi’s Java implementation and the Swift version of Pohl Longsin.

Part 5: Boxes

This is the fifth article in a series on writing a simple HTML rendering engine.

This article begins by laying out the module that takes the style tree and transforms it into a bunch of rectangles in a two-dimensional space. This is a large module, so I will break it up into several articles. Also, some of the code I share in this article may need to be changed as I write the code for the sections that follow.

The input to the layout module is the style tree from Part 4, and its output is another tree, the layout tree. This takes our mini render pipeline one step further:

I’ll start with a basic HTML/CSS layout model. If you’ve ever learned how to develop Web pages, you’re probably already familiar with this, but from an implementer’s point of view, it might be a little different.

The box model

A layout is a box. A box is a rectangular section of a web page. It has the width, height, and position on the page. This rectangle is called the content area because it is where the contents of the box are drawn. The content can be text, images, video, or other boxes.

A box can also have inside margins, borders, and margins around its content area. There is a diagram in the CSS specification that shows how all these layers fit together.

Robinson stores the content area and surrounding area of the box in the structure below. [Rust note: F32 is a 32-bit floating point type.]

// CSS box model. All sizes are in px.

struct Dimensions {
    // Position of the content area relative to the document origin:
    content: Rect,

    // Surrounding edges:
    padding: EdgeSizes,
    border: EdgeSizes,
    margin: EdgeSizes,
}

struct Rect {
    x: f32,
    y: f32,
    width: f32,
    height: f32,
}

struct EdgeSizes {
    left: f32,
    right: f32,
    top: f32,
    bottom: f32,
}
Copy the code

Block and inline layout

Note: This section contains diagrams that are meaningless without associated visual styles. If you are reading this article in a feed reader, try opening the original page in a regular browser TAB. I also provide text descriptions for readers who use screen readers or other assistive technologies.

The CSS display property determines what type of box an element generates. CSS defines several box types, each with its own layout rules. I’ll just talk about two of them: blocks and inlining.

I’ll use this bit of pseudo-HTML to illustrate the difference:

<container>
  <a></a>
  <b></b>
  <c></c>
  <d></d>
</container>
Copy the code

Block-level boxes are placed vertically in the container from top to bottom.

a, b, c, d { display: block; }
Copy the code

Row inner boxes are placed horizontally in the container from left to right. If they reach the right edge of the container, they wrap around and continue to the new line below.

a, b, c, d { display: inline; }
Copy the code

Each box must contain only block-level children or inline children. When a DOM element contains block-level and inline child elements, the layout engine inserts an anonymous box to separate the two types. (These boxes are “anonymous” because they are not associated with nodes in the DOM tree.)

In this example, inline boxes B and C are surrounded by an anonymous block box, shown in pink:

a    { display: block; }
b, c { display: inline; }
d    { display: block; }
Copy the code

Notice that content grows vertically by default. That is, adding child elements to a container usually makes it taller, not wider. Another way of saying this is that by default, the width of a block or row depends on the width of its container, and the height of the container depends on the height of its children.

This becomes more complicated if you override default values for attributes like width and height, and even more complicated if you want to support features like vertical writing.

Layout of the tree

A layout tree is a collection of boxes. A box has dimensions, and it may contain subboxes.

struct LayoutBox<'a> {
    dimensions: Dimensions,
    box_type: BoxType<'a>,
    children: Vec<LayoutBox<'a>>,
}
Copy the code

A box can be a block node, an inline node, or an anonymous block box. This needs to change when I implement text layout, because line wrapping causes an inline node to be split into boxes. But now it’s ok.)

enum BoxType<'a> {
    BlockNode(&'a StyledNode<'a>),
    InlineNode(&'a StyledNode<'a>),
    AnonymousBlock,
}
Copy the code

To build the layout tree, we need to look at the display property of each DOM node. I added some code to the Style module to get the display value of the node. If no value is specified, the initial value ‘inline’ is returned.

enum Display {
    Inline,
    Block,
    None,
}

impl StyledNode {
    // Return the specified value of a property if it exists, otherwise `None`.
    fn value(&self, name: &str) -> Option<Value> {
        self.specified_values.get(name).map(|v| v.clone())
    }

    // The value of the `display` property (defaults to inline).
    fn display(&self) -> Display {
        match self.value("display") {
            Some(Keyword(s)) => match &*s {
                "block" => Display::Block,
                "none" => Display::None,
                _ => Display::Inline
            },
            _ => Display::Inline
        }
    }
}
Copy the code

Now we can traverse the style tree, build a LayoutBox for each node, and insert boxes for the node’s children. If a node’s display property is set to ‘None’, it is not included in the layout tree.

// Build the tree of LayoutBoxes, but don't perform any layout calculations yet. fn build_layout_tree<'a>(style_node: &'a StyledNode<'a>) -> LayoutBox<'a> { // Create the root box. let mut root = LayoutBox::new(match style_node.display() { Block => BlockNode(style_node), Inline => InlineNode(style_node), DisplayNone => panic! ("Root node has display: none.") }); // Create the descendant boxes. for child in &style_node.children { match child.display() { Block => root.children.push(build_layout_tree(child)), Inline => root.get_inline_container().children.push(build_layout_tree(child)), DisplayNone => {} // Skip nodes with `display: none; ` } } return root; } impl LayoutBox { // Constructor function fn new(box_type: BoxType) -> LayoutBox { LayoutBox { box_type: Box_type, dimensions: Default:: Default (), // initially Set All fields to 0.0 children: Vec::new(),}} //... }Copy the code

If the block node contains inline child nodes, an anonymous block box is created to contain it. If there are several inline child elements in a row, place them all in the same anonymous container.

// Where a new inline child should go. fn get_inline_container(&mut self) -> &mut LayoutBox { match self.box_type { InlineNode(_) | AnonymousBlock => self, BlockNode(_) => { // If we've just generated an anonymous block box, keep using it. // Otherwise, create a new one. match self.children.last() { Some(&LayoutBox { box_type: AnonymousBlock,.. }) => {} _ => self.children.push(LayoutBox::new(AnonymousBlock)) } self.children.last_mut().unwrap() } } }Copy the code

This is intentionally simplified in a variety of ways from the standard CSS box generation algorithm. For example, it does not handle the case where an inline box contains block-level subboxes. Also, if a block-level node has only inline child nodes, an unnecessary anonymous box is generated.

To be continued

Wow, it’s longer than I thought. I think I’ll stop there, but don’t worry: Part 6 is coming up soon, and it will discuss block-level layouts.

Once the block layout is complete, we can jump to the next stage of the pipeline: draw! I think I’ll probably do that, because then we can finally see the rendering engine output as pretty images instead of numbers.

However, these images will just be a bunch of colored rectangles unless we complete the layout module by implementing inline layout and text layout. If I don’t achieve these before I start painting, I hope to return to them later.

Part 6: Block layout

Welcome back to the sixth article in my series on building a toy HTML rendering engine.

This article continues the layout module we started in Part 5. This time, we’ll add layout block box functionality. These boxes are stacked vertically, such as headings and paragraphs.

For simplicity, this code just implements normal flow: no floating, no absolute positioning, and no fixed positioning.

Walk through the layout tree

The entry point for this code is the Layout function, which takes a LayoutBox and calculates its size. We will divide this function into three cases, only one of which is implemented so far:

impl LayoutBox {
    // Lay out a box and its descendants.
    fn layout(&mut self, containing_block: Dimensions) {
        match self.box_type {
            BlockNode(_) => self.layout_block(containing_block),
            InlineNode(_) => {} // TODO
            AnonymousBlock => {} // TODO
        }
    }

    // ...
}
Copy the code

The layout of a block depends on the size of the blocks it contains. For a block box in normal flow, this is just the parent of the box. For the root element, it is the size of the browser window (or “viewport”).

You may recall from the previous article that a block’s width depends on its parent block and its height depends on its children. This means that our code needs to traverse the tree from the top down to compute the width, so it can lay out the subclass after the parent’s width is known and traverse bottom-up to compute the height, so the height of the parent class is computed after the height of its subclass.

fn layout_block(&mut self, containing_block: Dimensions) {
    // Child width can depend on parent width, so we need to calculate
    // this box's width before laying out its children.
    self.calculate_block_width(containing_block);

    // Determine where the box is located within its container.
    self.calculate_block_position(containing_block);

    // Recursively lay out the children of this box.
    self.layout_block_children();

    // Parent height can depend on child height, so `calculate_height`
    // must be called *after* the children are laid out.
    self.calculate_block_height();
}
Copy the code

This function traverses the layout tree once, counting the width as it goes down and the height as it goes up. A real layout engine might perform several tree traversals, some top down and some bottom up.

Calculate the width of the

Width calculation is the first and most complex step in the block layout function. I’ll take it one step at a time. First, we need the value of the CSS width property and the size of all the left and right edges:

fn calculate_block_width(&mut self, containing_block: Dimensions) { let style = self.get_style_node(); // `width` has initial value `auto`. let auto = Keyword("auto".to_string()); let mut width = style.value("width").unwrap_or(auto.clone()); // margin, border, and padding have initial value 0. let mut margin_left = style.lookup("margin-left", "margin", &zero); let mut margin_right = style.lookup("margin-right", "margin", &zero); let border_left = style.lookup("border-left-width", "border-width", &zero); let border_right = style.lookup("border-right-width", "border-width", &zero); let padding_left = style.lookup("padding-left", "padding", &zero); let padding_right = style.lookup("padding-right", "padding", &zero); / /... }Copy the code

This uses a helper function called lookup, which simply tries a series of values in sequence. If the first property is not set, it tries the second property. If not, it will return the given default value. This provides an incomplete (but simple) implementation of shorthand properties and initial values.

Note: This is similar to the following code in JavaScript or Ruby:

margin_left = style["margin-left"] || style["margin"] || zero;
Copy the code

Since a child cannot change the width of its parent, it needs to make sure that its own width matches that of the parent. The CSS specification expresses this as a set of constraints and algorithms to resolve them. The following code implements this algorithm.

First, we add the margins, padding, border, and content width. The to_PX helper method converts the lengths to their values. If a property is set to’ auto’, it returns 0, so it does not affect and.

let total = [&margin_left, &margin_right, &border_left, &border_right,
             &padding_left, &padding_right, &width].iter().map(|v| v.to_px()).sum();
Copy the code

This is the minimum horizontal space required for the box. If it’s not equal to the width of the container, we need to adjust something to make it equal.

If the width or margin is set to “auto”, they can be expanded or contracted to fit the available space. According to the instructions, we first check whether the box is too big. If so, we set any expandable margins to zero.

// If width is not auto and the total is wider than the container, treat auto margins as 0. if width ! Auto && total > containing_block.content.width {if margin_left == auto {margin_left = Length(0.0, Px); } if margin_right == auto {margin_right = Length(0.0, Px); }}Copy the code

If the box is too big for the container, it will overflow the container. If it’s too small, it will deflate, leaving extra room. We will calculate the underflow, which is the amount of space left in the container. (If the number is negative, it’s actually an overflow.)

let underflow = containing_block.content.width - total;
Copy the code

We now follow the canonical algorithm to eliminate any overflows or underflows by adjusting the scalable size. If there is no “automatic” size, we adjust the right margin. (Yes, this means that in the case of overflow, the boundary could be negative!)

match (width == auto, margin_left == auto, margin_right == auto) { // If the values are overconstrained, calculate margin_right. (false, false, false) => { margin_right = Length(margin_right.to_px() + underflow, Px); } // If exactly one size is auto, its used value follows from the equality. (false, false, true) => { margin_right = Length(underflow, Px); } (false, true, false) => { margin_left = Length(underflow, Px); } // If width is set to auto, any other auto values become 0. (true, _, _) => {if margin_left == auto {margin_left = Length(0.0, Px); } if margin_right == auto {margin_right = Length(0.0, Px); Width = Length(underflow, Px); // Expand width to fill the underflow. Width = Length(underflow, Px); } else {// Width can't be negative. Adjust the right margin invested. Width = Length(0.0, Px); margin_right = Length(margin_right.to_px() + underflow, Px); } } // If margin-left and margin-right are both auto, their used values are equal. (false, true, True) => {margin_left = Length(underflow / 2.0, Px); Margin_right = Length(underflow / 2.0, Px); margin_right = Length(underflow / 2.0, Px); }}Copy the code

At this point, the constraint is satisfied and any ‘auto’ value has been converted to length. The result is the used value for the horizontal box size, which we will store in the layout tree. You can see the final code in layout.rs.

positioning

The next step is easy. This function looks for the remaining margin/padding/border styles and uses those styles and the contained block size to determine the position of the block on the page.

fn calculate_block_position(&mut self, containing_block: Dimensions) { let style = self.get_style_node(); let d = &mut self.dimensions; // margin, border, and padding have initial value 0. // If margin-top or margin-bottom is `auto`, the used value is zero. d.margin.top = style.lookup("margin-top", "margin", &zero).to_px(); d.margin.bottom = style.lookup("margin-bottom", "margin", &zero).to_px(); d.border.top = style.lookup("border-top-width", "border-width", &zero).to_px(); d.border.bottom = style.lookup("border-bottom-width", "border-width", &zero).to_px(); d.padding.top = style.lookup("padding-top", "padding", &zero).to_px(); d.padding.bottom = style.lookup("padding-bottom", "padding", &zero).to_px(); d.content.x = containing_block.content.x + d.margin.left + d.border.left + d.padding.left; // Position the box below all the previous boxes in the container. d.content.y = containing_block.content.height + containing_block.content.y + d.margin.top + d.border.top + d.padding.top; }Copy the code

Take a closer look at the last statement, which sets the position of y. This is why block layouts have unique vertical stacking behavior. To do this, we need to ensure the contents of the parent node. The height is updated after each child element is laid out.

Child elements

Below is the code for recursive layout box content. As it loops through the subbox, it keeps track of the total content height. The positioning code (above) uses this function to find the vertical position of the next child element.

fn layout_block_children(&mut self) { let d = &mut self.dimensions; for child in &mut self.children { child.layout(*d); // Track the height so each child is laid out below the previous content. d.content.height = d.content.height + child.dimensions.margin_box().height; }}Copy the code

The total vertical space occupied by each child node is the height of its margin box, which is calculated as follows:

impl Dimensions {
    // The area covered by the content area plus its padding.
    fn padding_box(self) -> Rect {
        self.content.expanded_by(self.padding)
    }
    // The area covered by the content area plus padding and borders.
    fn border_box(self) -> Rect {
        self.padding_box().expanded_by(self.border)
    }
    // The area covered by the content area plus padding, borders, and margin.
    fn margin_box(self) -> Rect {
        self.border_box().expanded_by(self.margin)
    }
}

impl Rect {
    fn expanded_by(self, edge: EdgeSizes) -> Rect {
        Rect {
            x: self.x - edge.left,
            y: self.y - edge.top,
            width: self.width + edge.left + edge.right,
            height: self.height + edge.top + edge.bottom,
        }
    }
}
Copy the code

Margin folding is not implemented here for simplicity. A real layout engine would allow the bottom edge of one box to overlap with the top edge of the next, rather than each box being completely underneath the previous one.

Height attribute

By default, the height of a box is equal to the height of its contents. But if the ‘height’ attribute is explicitly set to length, we’ll use it instead:

fn calculate_block_height(&mut self) { // If the height is set to an explicit length, use that exact length. // Otherwise, just keep the value set by `layout_block_children`. if let Some(Length(h, Px)) = self.get_style_node().value("height") { self.dimensions.content.height = h; }}Copy the code

This is the block layout algorithm. Now you can call Layout () on an HTML document, which generates a bunch of rectangles, including width, height, margins, and so on. Cool, right?

practice

Some additional thoughts for ambitious implementers:

  1. The vertical edge of the collapse.

  2. Relative positioning.

  3. Parallelize the layout process and measure the impact on performance.

If you’re trying to parallelize your project, you might want to separate width and height calculations into two different channels. Traversing the width from top to bottom is easy to parallelize by generating a separate task for each subtask. The height calculation is a little more complicated, because you need to go back and adjust the Y position of each child element after it has been laid out.

To be continued

Thank you to all who have followed me to this point!

These articles took longer and longer to write as I delved into the unfamiliar territory of layout and rendering. There will be a long hiatus before I experiment with the next part of the font and graphics code, but I will resume this series as soon as possible.

Update: Part 7 is now ready.

Part seven: Drawing 101

Welcome back to the seventh and final article in my series on building a simple HTML rendering engine.

In this article, I’ll add very basic painting code. This code takes the box trees from the layout module and converts them into an array of pixels. This process is also called “rasterization”.

Browsers are typically rasterized with the help of graphical apis and libraries such as Skia, Cairo, and Direct2D. These apis provide functions for drawing polygons, lines, curves, gradients, and text. Now, I’ll write my own rasterizer that can only draw one thing: rectangles.

Finally I want to implement text rendering. At this point, I would probably ditch the toy drawing code and use a “real” 2D graphics library instead. But for now, rectangles are enough to turn the output of my block layout algorithm into a picture.

To catch up

Since the last article, I’ve made some minor changes to the code from the previous article. This includes some minor refactorings, as well as some updates to keep the code compatible with the latest Rust night builds. None of these changes are critical to understanding the code, but you can check the commit history if you’re curious.

Building a display list

Before drawing, we will traverse the layout tree and build a display list. This is a list of graphical operations, such as “Draw circles” or “Draw text Strings.” Or in our case, just “draw a rectangle.”

Why put commands in a display list instead of executing them immediately? Displaying lists is useful for several reasons. You can search for items that have been completely covered up by later operations and remove them to eliminate wasted paint. Display lists can be modified and reused when only certain items are known to have changed. You can use the same display list to generate different types of output: pixels for display on the screen, for example, or vector graphics for sending to the printer.

Robinson’s display list is a vector of display commands. Currently, there is only one type of DisplayCommand, a solid color rectangle:

type DisplayList = Vec<DisplayCommand>;

enum DisplayCommand {
    SolidColor(Color, Rect),
    // insert more commands here
}
Copy the code

To build the display list, we traverse the layout tree and generate a series of commands for each box. First, we draw the background of the box, then draw the border and content at the top of the background.

fn build_display_list(layout_root: &LayoutBox) -> DisplayList { let mut list = Vec::new(); render_layout_box(&mut list, layout_root); return list; } fn render_layout_box(list: &mut DisplayList, layout_box: &LayoutBox) { render_background(list, layout_box); render_borders(list, layout_box); // TODO: render text for child in &layout_box.children { render_layout_box(list, child); }}Copy the code

By default, HTML elements are stacked in the order in which they appear: if two elements overlap, the following element is drawn on top of the preceding one. This is reflected in our display list, which draws elements in the order in which they appear in the DOM tree. If this code supports the Z-index attribute, then the individual elements will override the stack order, and we need to sort the display list accordingly.

The background is simple. It’s just a solid rectangle. If the background color is not specified, the background is transparent and we do not need to generate display commands.

fn render_background(list: &mut DisplayList, layout_box: &LayoutBox) {
    get_color(layout_box, "background").map(|color|
        list.push(DisplayCommand::SolidColor(color, layout_box.dimensions.border_box())));
}

// Return the specified color for CSS property `name`, or None if no color was specified.
fn get_color(layout_box: &LayoutBox, name: &str) -> Option<Color> {
    match layout_box.box_type {
        BlockNode(style) | InlineNode(style) => match style.value(name) {
            Some(Value::ColorValue(color)) => Some(color),
            _ => None
        },
        AnonymousBlock => None
    }
}
Copy the code

The borders are similar, but instead of drawing a single rectangle, we draw each border 4-1.

fn render_borders(list: &mut DisplayList, layout_box: &LayoutBox) {
    let color = match get_color(layout_box, "border-color") {
        Some(color) => color,
        _ => return // bail out if no border-color is specified
    };

    let d = &layout_box.dimensions;
    let border_box = d.border_box();

    // Left border
    list.push(DisplayCommand::SolidColor(color, Rect {
        x: border_box.x,
        y: border_box.y,
        width: d.border.left,
        height: border_box.height,
    }));

    // Right border
    list.push(DisplayCommand::SolidColor(color, Rect {
        x: border_box.x + border_box.width - d.border.right,
        y: border_box.y,
        width: d.border.right,
        height: border_box.height,
    }));

    // Top border
    list.push(DisplayCommand::SolidColor(color, Rect {
        x: border_box.x,
        y: border_box.y,
        width: border_box.width,
        height: d.border.top,
    }));

    // Bottom border
    list.push(DisplayCommand::SolidColor(color, Rect {
        x: border_box.x,
        y: border_box.y + border_box.height - d.border.bottom,
        width: border_box.width,
        height: d.border.bottom,
    }));
}
Copy the code

Next, the render function draws each child element of the box until the entire layout tree is converted into a display command.

rasterizer

Now that we have built the display list, we need to convert each DisplayCommand to pixels. We will store the pixels in the canvas:

struct Canvas {
    pixels: Vec<Color>,
    width: usize,
    height: usize,
}

impl Canvas {
    // Create a blank canvas
    fn new(width: usize, height: usize) -> Canvas {
        let white = Color { r: 255, g: 255, b: 255, a: 255 };
        return Canvas {
            pixels: repeat(white).take(width * height).collect(),
            width: width,
            height: height,
        }
    }
    // ...
}
Copy the code

To draw a rectangle on a canvas, just loop through its rows and columns, using helper methods to make sure you don’t go beyond the canvas.

fn paint_item(&mut self, item: &DisplayCommand) { match item { &DisplayCommand::SolidColor(color, Rect) => {// Clip the rectangle to the canvas boundaries. Let x0 = rect.x.lamp (0.0, self.width as f32) as usize; Let y0 = rect.y.lamp (0.0, self.height as f32) as usize; Let x1 = (rect.x + rect.width).clamp(0.0, self.width as f32) as usize; Let y1 = (rect.y + rect.height).clamp(0.0, self.height as f32) as usize; for y in (y0 .. y1) { for x in (x0 .. x1) { // TODO: alpha compositing with existing pixel self.pixels[x + y * self.width] = color; } } } } }Copy the code

Note that this code only works with opaque colors. If we added transparency (either by reading the opacity property, or by adding support for rGBA () values in the CSS parser), it would need to mix each new pixel with whatever it was drawing.

Now we can put everything into the paint function, which builds a display list and rasterizes it onto the canvas:

// Paint a tree of LayoutBoxes to an array of pixels.
fn paint(layout_root: &LayoutBox, bounds: Rect) -> Canvas {
    let display_list = build_display_list(layout_root);
    let mut canvas = Canvas::new(bounds.width as usize, bounds.height as usize);
    for item in display_list {
        canvas.paint_item(&item);
    }
    return canvas;
}
Copy the code

Finally, we can write a few lines of code to save the pixel array as a PNG file using the Rust image library. Beautiful picture

Finally, we have reached the end of the render pipeline. In less than 1000 lines of code, Robinson can now parse the HTML file:

<div class="a">
  <div class="b">
    <div class="c">
      <div class="d">
        <div class="e">
          <div class="f">
            <div class="g">
            </div>
          </div>
        </div>
      </div>
    </div>
  </div>
</div>
Copy the code

And this CSS file:

* { display: block; padding: 12px; }
.a { background: #ff0000; }
.b { background: #ffa500; }
.c { background: #ffff00; }
.d { background: #008000; }
.e { background: #0000ff; }
.f { background: #4b0082; }
.g { background: #800080; }
Copy the code

The following results are obtained:

Yeah!

practice

If you’re playing alone at home, here are a few things you might want to try:

Write an alternative drawing function that takes a display list and generates vector output (for example, an SVG file) instead of a raster image.

Added support for blending opacity and alpha.

Write a function to optimize the display list by removing items that are completely outside the canvas boundary.

If you are familiar with OpenGL, you can write a hardware-accelerated drawing function that uses GL shaders to draw rectangles.

The end of the

Now that we’ve got the basic functionality for each stage in the render pipeline, it’s time to go back and fill in some missing features — especially inline layout and text rendering. Future articles may also add additional phases, such as networking and scripting.

I’ll be giving a short talk at the Bay Area Rust gathering this month, “Let’s Build a Browser Engine!” The conference will be held tomorrow (Thursday, November 6th) at 7pm at Mozilla’s San Francisco office, where my fellow server developers will also be giving presentations on servos. A video of the talks will be streamed live on Air Mozilla, and a recording will be released at a later date.

Join us

We are DevUI team, welcome to come here and build elegant and efficient human-computer design/research and development system with us. Email: [email protected].

The copyright of this article belongs to the original author and is only used for learning and communication.

If you need to reprint the translation, please indicate the source information below, thank you!

Original link: limpet.net/mbrubeck/20…

By Matt Brubeck

Translator: DevUI Kagol

Previous articles are recommended

“After setting flags, you may need to quantify them.”

“Arming” your Project with Lint

Denver “🏆 DevUI x | of 2020”