HTTP request and parsing

HTTP request and parsing

Browser Working Principles

·

20 min read

Introduction

The browser working principle is a piece of very important knowledge for frontend developers. We often use some knowledge of browser working principles to explain and understand the concept of repaint, reflow or CSS properties.

Trying to figure out how the browser works by going through all the theory is rather ineffective and it's just too boring.

Here we will start from scratch and develop a simple browser using JavaScript. By creating a simple browser on our own, we will gain a deeper understanding of the browser working principles.

Less talk more code! Let's go!


Browser rendering process

image

General understanding of this process:

  • First of all, the browser content is rendered in 5 different steps.
  • When we access a web page from a URL, the page is parsed by the browser and rendered as a Bitmap.
  • Last but not least, our graphics card renders the page so we can view it visually.

This is a browser's basic rendering process.

This part of the Frontend Advancement Series is only going to implement the basic functionality of the browser. For a real browser, it would include many more features, such as history, bookmarks management, user accounts, data syncing and many more.

Therefore the main goal for this part of the series is to have a good understanding of the browser's working principle.

In order to do that, we need to implement the entire process from URL request to Bitmap rendering.


Understanding the process of a browser

To understand the process a little deeper, we should go through each step of the process with more details:

  1. After a URL is entered into the browser, an HTTP request is sent. The browser then parses the returned content and extracts the HTML.
  2. After getting the HTML content, the browser will parse it and turn it into a DOM tree.
  3. The DOM is basically nake at this time. The next step is to perform a CSS computation to mount the CSS properties onto the DOM tree. At the end, we will get a styled DOM tree.
  4. The styled DOM tree we get after the computation is then useful to start forming out your page layout.
  5. Each DOM will get a calculated box. (Of course, in the real browser, every CSS will generate a box, but for simplicity, we only need to calculate one box per DOM.)
  6. Finally, we can start rendering the DOM tree, which should render CSS properties like the background-image or the background-color onto an image. Next, the user will be able to see it through the API interface provided by the operating system and the hardware driver.

Use Finite-state Machine to parse character strings

It is important to understand one more thing before we dive into some coding.

A character string parser is required in many places throughout the browser's process. We will have a tough time implementing the code if we do not have a good "logic" management system to manage these different character string's parsing processes.

Therefore we need to use a state management system called "Finite-state Machine".

So what is Finite-state Machine (FSM)?

A Finite State Machine is a model of computation based on a hypothetical machine made of one or more states. Only one single state of this machine can be active at the same time. It means the machine has to transition from one state to another to perform different actions.

A Finite State Machine is any device storing the state of something at a given time. The state will change based on inputs, providing the resulting output for the implemented changes.

The important points here are the following:

  • Every state is a machine
    • Every machine is decoupled from each other, it is a powerful abstract mechanism
    • In each machine, we can do calculations, storage, output and etc.
    • All these machines receive the same input
    • Each state machine itself should have no state. If we express it as a pure function, it should have no side effects.
  • Every machine knows the next state
    • Every machine has a definite next state (Moore state machine)
    • Each machine determines the next state based on input (Mealy state machine)

For an in-depth explanation of Finite-state Machine, check out the article here.

How to implement FSM in JavaScript?

Mealy state machine:

// Every function is a state
// Function's parameter is an input
function state (input) { 
  // Inside the function, we can write our code
  // for the current state

  // Return the next State function
  return state2;
}

/** ========= 
    * To run the state matching
    * ========= */
while (input) {
  state = state(input);
}
  • In the above code, we see that each function is a state
  • Then the parameter of the function is input
  • The return value of this function is the next state, which implies that the next return value must be a state function.
  • n ideal implementation of a state machine is: "A series of state functions that return a batch of state functions."
  • When state functions are invoked, a loop is often used to obtain the input, then state = state(input) is used to let the state machine receive input to complete the state switch.
  • Mealy type state machine's return value must be based on the input to return the next state.
  • Moore type state machine's return value is not related to input, instead, it returns a fixed state.

What if we don't want to use FSM?

Let's take a look at what we can use if we don't want to use FSM to process the character strings in our simple browser.

In the same way that you would perform a science experience, you would attempt to defend your solution by using a different method or theory. It turns out that you already have the right solution.

What we do here is the same, let's look at how to implement the parse character strings without using a state machine.

We will learn this by going through a few challenges:

Challenge 1: Find the character "a" in a character string.

function match(string) {
  for (let letter of string) {
    if (letter == 'a') return true;
  }
  return false;
}

console.log(match('I am TriDiamond'));

Easy, isn't it?

Challenge 2: Find the character "ab" in a character string without using regular expression. Try implementing it with just pure JavaScript.

Tip: Look for a and b directly, return when both are found

function matchAB(string) {
  let hasA = false;
  for (let letter of string) {
    if (letter == 'a') {
      hasA = true;
    } else if (hasA && letter == 'b') {
      return true;
    } else {
      hasA = false;
    }
  }
  return false;
}

console.log( matchAB('hello abert'));

Challange 3: Find the character "abcdef" in a character string without using regular expression. Again try implementing it with just pure JavaScript.

There are 3 ways to approach this challenge.

Method1: By using storage space and move the key pointer to find our target.

/**
 * @param {*} match String that you need to match
 * @param {*} string String that you are matching against
 */
function matchString(match, string) {
  // Break up matching string characters into an array
  const resultLetters = match.split('');
  // Break up the string characters that you are matching against into an array
  const stringArray = string.split('');
  let index = 0; // The matching index

  for (let i = 0; i <= stringArray.length; i++) {
    // Make sure the strings are absolutely matched
    // eg. "abc" and "ab" should not be matched.

    // Therefore we require the string characters have
    // the correct orders
    if (stringArray[i] == resultLetters[index]) {
      // If one matching character is found
      // index + 1 to move to the next character
      index++;
    } else {
      // If the next character is not matched
      // reset the index and match all over again
      index = 0;
    }
    // If all characters of the string is matched
    // return true immediately, which means
    // `match` string is founded in our `string`
    if (index > resultLetters.length - 1) return true;
  }
  return false;
}

console.log('Method 1', matchString('abcdef', 'hello abert abcdef'));

Method2: Using the substring function to intercept the matching string characters to check whether they are equal to the answer.

function matchWithSubstring(match, string) {
  for (let i = 0; i &lt; string.length - 1; i++) {
    if (string.substring(i, i + match.length) === match) {
      return true;
    }
  }
  return false;
}

console.log('Method 2', matchWithSubstring('abcdef', 'hello abert abcdef'));

Method 3: Search the characters one by one until you find the final result.

function match(string) {
  let matchStatus = [false, false, false, false, false, false];
  let matchLetters = ['a', 'b', 'c', 'd', 'e', 'f'];
  let statusIndex = 0;

  for (let letter of string) {
    if (letter == matchLetters[0]) {
      matchStatus[0] = true;
      statusIndex++;
    } else if (matchStatus[statusIndex - 1] && letter == matchLetters[statusIndex]) {
      matchStatus[statusIndex] = true;
      statusIndex++;
    } else {
      matchStatus = [false, false, false, false, false, false];
      statusIndex = 0;
    }

    if (statusIndex > matchLetters.length - 1) return true;
  }
  return false;
}

console.log('Method 3', match('hello abert abcdef'));

Parsing characters using a state machine

Now let's look at how we process the characters by using a state machine.

To demonstrate how to process characters using a state machine, we going to solve the 3rd challenge using state machine:

Challange 3: Find the character "abcdef" in a character string without using regular expression. Again try implementing it with just pure JavaScript.

First, let's think about how are we going to do it with state machine:

  • First of all, every state is a state function
  • We should have a start state and an end state function, which we would call them starting and ending respectively
  • Every state function's name represents the previous matched state of a specific character
    • Eg. matchedA means the a character is being matched in the previous state function.
  • The logic in each state matches the next character
    • Therefore the current state function is processing the next state logic.
    • Eg. If the current function name is matchedA, the logic inside it is to process when the character is equal to b
  • If the match fails, return the start state
  • Because the last of the characters is an f, therefore after matchedE succeeds, we can directly return to the end state
  • The End state is also known as the 'Trap method' since the state transition is finished, we can let the state stay here until the loop is finished.
/**
 * Character matching state machine
 * @param {*} string
 */
function match(string) {
  let state = start;

  for (let letter of string) {
    state = state(letter); // Switch state
  }

  // If the ending state is `end` return true
  return state === end; 
}

function start(letter) {
  if (letter === 'a') return matchedA;
  return start;
}

function end(letter) {
  return end;
}

function matchedA(letter) {
  if (letter === 'b') return matchedB;
  return start(letter);
}

function matchedB(letter) {
  if (letter === 'c') return matchedC;
  return start(letter);
}

function matchedC(letter) {
  if (letter === 'd') return matchedD;
  return start(letter);
}

function matchedD(letter) {
  if (letter === 'e') return matchedE;
  return start(letter);
}

function matchedE(letter) {
  if (letter === 'f') return end(letter);
  return start(letter);
}

console.log(match('I am abcdef'));

Escalation of the challenge: Parsing of the character string "abcabx" with a state machine.

  • The main difference in this challenge is that the letters "ab" appears twice.
  • So the logic of our analysis should be:
    • The first "b" is followed by a "c", while the second "b" should be followed by an "x"
    • Go back to the previous state function if the character after the second "b" isn't an "x"
function match(string) {
  let state = start;

  for (let letter of string) {
    state = state(letter);
  }

  return state === end;
}

function start(letter) {
  if (letter === 'a') return matchedA;
  return start;
}

function end(letter) {
  return end;
}

function matchedA(letter) {
  if (letter === 'b') return matchedB;
  return start(letter);
}

function matchedB(letter) {
  if (letter === 'c') return matchedC;
  return start(letter);
}

function matchedC(letter) {
  if (letter === 'a') return matchedA2;
  return start(letter);
}

function matchedA2(letter) {
  if (letter === 'b') return matchedB2;
  return start(letter);
}

function matchedB2(letter) {
  if (letter === 'x') return end;
  return matchedB(letter);
}

console.log('result: ', match('abcabcabx'));

That's it!

After we had compared the parsing of a character string with and without a state machine. There is an obvious difference that we can observe.

When parsing with a state machine, the logic is much more manageable, while without a state machine it can be confusing and hard to understand.


The basics of HTTP protocol parsing

To understand the basic of the HTTP protocol, first we need to know what is the OSI Model.

The OSI Model (Open Systems Interconnection Model) is a conceptual framework used to describe the functions of a networking system.

ISO-OSI 7 layer model

HTTP

  • Composition:
    • Application
    • Representation
    • Conversation

In node.js, we have a very familiar package called http

TCP

  • Composition:
    • Network
  • There are two meanings for the term "internet"
    • Protocol (extranet) of the application layer where the web page is located —— it is the internet that is responsible for data transmission
    • Company intranet —— it's the local network build inside a company.

4G/5G/Wi-Fi

  • Composition:
    • Data link
    • Physical layer
  • In order to complete an accurate transmission of data
  • Transmissions are all done by point-to-point
  • There must be a direct connection for transmissions

TCP and IP

  • Stream
    • Stream is the main concept of transmitting data in the TCP layer
    • A stream is a unit that has no apparent division
    • It only guarantees that the order before and after is consistent
  • Port
    • The TCP protocol is used by the software inside the computer
    • Every piece of software get the data from the network card
    • The port identifies which data is allocated to which software
    • Just like the net package in node.js
  • Package
    • Packages in TCP is transported one after another
    • Each package can be large or small
    • The size of each package is depended on the transmission capacity of your network intermediate equipment
  • IP Address
    • An IP address is used to locate where the package should go.
    • The connection relationship on the internet is very complicated, and there will be some large routing nodes in the middle.
    • When we connected to an IP address, it first connects to the address of our house cable, then goes to the telecommunication company's cable.
    • If you are visiting a foreign country's IP address, you will go to the main international address
    • Every IP address is a unique identifier that connects to every device on the internet
    • So the IP packet find out where it needs to be transmitted through the IP address
  • Libnet/libpcap
    • The IP protocol needs to call these two libraries in C++
    • Libnet is responsible for constructing IP packets and sending them out
    • Labpcap is responsible for grabbing all IP packets flowing through the network card.
    • If we use switches instead of routers to build our network, we can use the labpcap package to catch many IP packages that do not belong to us

HTTP

  • Composition
    • Request
    • Response
  • HTTP works as a full-duplex channel, which means it can do both sending and receiving, and there is no priority relationship between them.
  • In particular, HTTP must first be initiated by the client with a request
  • Then the server comes back with a response
  • So every request must have a response

Implement HTTP request

HTTP requests - server-side environment preparation

Before we write our own browser, we need to set up a node.js server.

First by writing the following node.js script:

const http = require('http');

http
  .createServer((request, response) =&gt; {
    let body = [];
    request
      .on('error', err => {
        console.error(err);
      })
      .on('data', chunk => {
        body.push(chunk.toString());
      })
      .on('end', () => {
        body = Buffer.concat(body).toString();
        console.log('body', body);
        response.writeHead(200, { 'Content-Type': 'text/html' });
        response.end(' Hello World\n');
      });
  })
  .listen(8080);

console.log('server started');

Understanding HTTP Request Protocol

Before writing our client code, we need to understand the HTTP request protocol.

Let's first look at the request section of the HTTP protocol

POST/HTTP/1.1

Host: 127.0.0.1

Content-Type: application/x-www-form-urlencoded

field1=aaa&code=x%3D1

The HTTP protocol is a text type protocol, text type protocol is generally relative to the binary protocol. In another word, means that all the contents of this protocol are character strings and each byte is part of the character string.

  • The first line: request line and contains three parts
    • Method: Eg. POST, GET
    • Path: default is "/"
    • HTTP and HTTP version: HTTP/1.1
  • Follow by headers
    • Each row is split with a colon in key: value format
    • Headers end with a blank line
  • Last part is body
    • The content of this section is determined by Content-Type
    • The body's content format is based on Content-Type specify,

Implement HTTP Requests

Goal:

  • Design an HTTP request class
  • Content-type is a required field with a default value
  • Body is in key-value format
  • Different Content-type affect body formatting

Request Class

class Request {
  constructor(options) {
    // Fill in the default values
    this.method = options.method || 'GET';
    this.host = options.host;
    this.port = options.port || 80;
    this.path = options.path || '/';
    this.body = options.body || {};
    this.headers = options.headers || {};

    if (!this.headers['Content-Type']) {
      this.headers['Content-Type'] = 'application/x-www-form-urlencoded';
    }
    // Convert the body format base on Content-Type
    if (this.headers['Content-Type'] === 'application/json') {
      this.bodyText = JSON.stringify(this.body);
    } else if (this.headers['Content-Type'] === 'application/x-www-form-urlencoded') {
      this.bodyText = Object.keys(this.body)
        .map(key => `${key}=${encodeURIComponent(this.body[key])}`)
        .join('&');
    }
    // Auto calculate body content length, if the length isn't valid, meaning it's an invalid request
    this.headers['Content-Length'] = this.bodyText.length;
  }
  // Sending request, return Promise object
  send() {
    return new Promise((resolve, reject) => {
      //......
    });
  }
}

Request Method

/**
 * Request method using the Request Class
 */
void (async function () {
  let request = new Request({
    method: 'POST',
    host: '127.0.0.1',
    port: '8080',
    path: '/',
    headers: {
      ['X-Foo2']: 'custom',
    },
    body: {
      name: 'tridiamond',
    },
  });

  let response = await request.end();

  console.log(response);
})();

Implement the send function

The logic of our send function:

  • Send function is in a form of Promise
  • The response content will be gradually received during the sending process
  • Construct the response and let the Promise resolve
  • Because the process receives information one by one, we need to design a ResponseParser
  • In this way, the parser can construct different parts of the response object while gradually receiving the response information
  send() {
    return new Promise((resolve, reject) => {
      const parser = new ResponseParser();
      resolve('');
    });
  }

Implement HTTP response

Design the ResponseParser

The logic of our ResponseParser:

  • Need a receive function that collects the character string
  • Then use the state machine to process the string character by character
  • So we need to loop each character string and then add the recieveChar function to process each of them
class ResponseParser {
  constructor() {}
  receive(string) {
    for (let i = 0; i &lt; string.length; i++) {
      this.receiveChar(string.charAt(i));
    }
  }
  receiveChar(char) {}
}

This is the basic structure of our ResponseParser.

Understanding HTTP Response Protocol

In this section, we need to parse the contents in the HTTP response. So we will first analyse the HTTP response content.

HTTP / 1.1 200 OK

Content-Type: text/html
Date: Mon, 23 Dec 2019 06:46:19 GMT
Connection: keep-alive

26
<html><body> Hello World <body></html>
0
  • The status line in the first line is opposite to the request line
    • The first part is the version of the HTTP protocol: HTTP/1.1
    • The second part is the HTTP status code: 200 (We can mark the state other than 200 as an error in our browser implementation to make it easier.)
    • The third part is HTTP status: OK
  • Follow by the header section
    • HTML requests and responses contain headers
    • Its format is exactly the same as the request
    • The final line of this section will be a blank line, used to divide the headers and the body content
  • Body part:
    • The format of the body here is also determined by Content-Type
    • Here is a typical format called chunked body (A default format returned by Node)
    • The chunked body will start with a line with a hexadecimal number
    • Follow by the content section
    • Finally ended with a hexadecimal 0, this is the end of the whole body

Implement the logic of send request

After we have a good understanding of the response protocol, we need a working send request to test and implement our Response Parser.

Design thoughts:

  • Supports existing connections or adding new connections
  • Passing the received data to the parser
  • Resolve the Promise base on the parser's status

Let's see how we implement this.

  send(connection) {
    return new Promise((resolve, reject) =&gt; {
      const parser = new ResponseParser();
      // First check if connection is avaliable
      // If not use Host and Port to create a TCP connection
      // `toString` is used to build our HTTP Request
      if (connection) {
        connection.write(this.toString());
      } else {
        connection = net.createConnection(
          {
            host: this.host,
            port: this.port,
          },
          () => {
            connection.write(this.toString());
          }
        );
      }
      // Listen to connection's data
      // Pass the data to the parser
      // If parser had finished, we can start the resolve
      // Then break off the connection
      connection.on('data', data => {
        console.log(data.toString());
        parser.receive(data.toString());

        if (parser.isFinished) {
          resolve(parser.response);
          connection.end();
        }
      });
      // Listen to connection's error
      // If the request had an error,
      // first reject this Promise
      // Then break off the connection
      connection.on('error', err => {
        reject(err);
        connection.end();
      });
    });
  }
  /**
   * Building HTTP Request text content
   */
  toString() {
    return `${this.method} ${this.path} HTTP/1.1\r
      ${Object.keys(this.headers)
        .map(key =&gt; `${key}: ${this.headers[key]}`)
        .join('\r\n')}\r\r
      ${this.bodyText}`;
  }

Implement the RequestParser Class

Now let's implement the logic for our RequestParser Class.

Logic:

  • Response must be constructed by sections, so we are going to use Response Parser to assemble it.
  • Use a state machine to analyze the text structure

Parsing the header

class ResponseParser {
  constructor() {
    this.state = this.waitingStatusLine;
    this.statusLine = '';
    this.headers = {};
    this.headerName = '';
    this.headerValue = '';
    this.bodyParser = null;
  }

  receive(string) {
    for (let i = 0; i &lt; string.length; i++) {
      this.state = this.state(string.charAt(i));
    }
  }

  receiveEnd(char) {
    return receiveEnd;
  }

  /**
   * Waiting status line context
   * @param {*} char
   */
  waitingStatusLine(char) {
    if (char === '\r') return this.waitingStatusLineEnd;
    this.statusLine += char;
    return this.waitingStatusLine;
  }

  /**
   * Waiting for status line ends
   * @param {*} char
   */
  waitingStatusLineEnd(char) {
    if (char === '\n') return this.waitingHeaderName;
    return this.waitingStatusLineEnd;
  }

  /**
   * Waiting for the Header name
   * @param {*} char
   */
  waitingHeaderName(char) {
    if (char === ':') return this.waitingHeaderSpace;
    if (char === '\r') return this.waitingHeaderBlockEnd;
    this.headerName += char;
    return this.waitingHeaderName;
  }

  /**
   * Waiting for Header empty space
   * @param {*} char
   */
  waitingHeaderSpace(char) {
    if (char === ' ') return this.waitingHeaderValue;
    return this.waitingHeaderSpace;
  }

  /**
   * Waiting for the Header value
   * @param {*} char
   */
  waitingHeaderValue(char) {
    if (char === '\r') {
      this.headers[this.headerName] = this.headerValue;
      this.headerName = '';
      this.headerValue = '';
      return this.waitingHeaderLineEnd;
    }
    this.headerValue += char;
    return this.waitingHeaderValue;
  }

  /**
   * Waiting for the Header ending line
   * @param {*} char
   */
  waitingHeaderLineEnd(char) {
    if (char === '\n') return this.waitingHeaderName;
    return this.waitingHeaderLineEnd;
  }

  /**
   * Waiting for Header content end
   * @param {*} char
   */
  waitingHeaderBlockEnd(char) {
    if (char === '\n') return this.waitingBody;
    return this.waitingHeaderBlockEnd;
  }
}

Parsing the body content

Logic:

  • Response body may have a different structure depending on the Content-Type, so we will use the structure of the sub-parser to solve this problem
  • Take ChunkedBodyParser as an example, we also use a state machine to deal with the format of the body

Adding a state function for body parsing:

/**
 * Response 解析器
 */
class ResponseParser {
  constructor() {
    this.state = this.waitingStatusLine;
    this.statusLine = '';
    this.headers = {};
    this.headerName = '';
    this.headerValue = '';
    this.bodyParser = null;
  }

  /** ... Previous codes ... **/

  /**
   * Waiting for Header content end
   * @param {*} char
   */
  waitingHeaderBlockEnd(char) {
    if (char === '\n') return this.waitingBody;
    return this.waitingHeaderBlockEnd;
  }

  /** Adding a state function for body parsing **/

  /**
   * Waiting for body content
   * @param {*} char
   */
  waitingBody(char) {
    this.bodyParser.receiveChar(char);
    return this.waitingBody;
  }
}

Adding ChunkedBodyParser class:

class ChunkedBodyParser {
  constructor() {
    this.state = this.waitingLength;
    this.length = 0;
    this.content = [];
    this.isFinished = false;
  }

  receiveChar(char) {
    this.state = this.state(char);
  }

  /**
   * Waiting for Body length
   * @param {*} char
   */
  waitingLength(char) {
    if (char === '\r') {
      if (this.length === 0) this.isFinished = true;
      return this.waitingLengthLineEnd;
    } else {
      // Convert the hexdecimal number
      this.length *= 16;
      this.length += parseInt(char, 16);
    }
    return this.waitingLength;
  }

  /**
   * Waiting for Body line end
   * @param {*} char
   */
  waitingLengthLineEnd(char) {
    if (char === '\n') return this.readingTrunk;
    return this.waitingLengthLineEnd;
  }

  /**
   * Reading Trunk content
   * @param {*} char
   */
  readingTrunk(char) {
    this.content.push(char);
    this.length--;
    if (this.length === 0) return this.waitingNewLine;
    return this.readingTrunk;
  }

  /**
   * Waiting for a new line
   * @param {*} char
   */
  waitingNewLine(char) {
    if (char === '\r') return this.waitingNewLineEnd;
    return this.waitingNewLine;
  }

  /**
   * Waiting for line end
   * @param {*} char
   */
  waitingNewLineEnd(char) {
    if (char === '\n') return this.waitingLength;
    return this.waitingNewLineEnd;
  }
}

Finally

In this section of the Frontend Advancement Series, we have implemented the browser HTTP Request, HTTP Response parser.

In the next section, we will talk about how to use the parsed HTTP to build a DOM tree.

Happy coding!~


Recommended Open Source Projects

Hexo Theme Aurora

Usage Document


VSCode Aurora Future theme


Firefox Aurora Future

Theme page