DEV Community: Kirill Vasiltsov

Planespotting with Rust: using nom to parse ADS-B messages

Kirill Vasiltsov — Sat, 28 Oct 2023 06:12:06 +0000

Using software defined radio (SDR) to listen to ADS-B transmissions has been on my mind for a while. This article is inspired by the cool experiment by Charlie Gerard, who used JavaScript to parse and display ADS-B messages as they come through the WebUSB interface right in the browser. I wanted to do something similar, but use my go-to parsing library nom and the terminal.

You can find the full source code here: ads-b-parser. This is by no means a complete parser but here's what I was able to achieve with it:

ADS-B

ADS-B is a protocol used by aircrafts to broadcast their position, altitude, speed, and other information. Nowadays, the majority of aircrafts broadcast ADS-B messages constantly. Anyone with the right equipment can listen to these messages. You can buy a relatively cheap USB dongle with an antenna on Amazon and install drivers for it on Linux. In my case I used usbipd-win to mount the USB device inside Ubuntu running in WSL2. Then I installed the Linux drivers and dump1090, a program that makes use of these drivers and then outputs ADS-B messages in a format that is easy to parse. While you can use dump1090 to display a neat table full of information about aircrafts, I wanted to use its raw output capabilities to parse ADS-B messages myself. It starts a simple TCP server that outputs raw ADS-B messages wrapped in Mode-S Beast frames. I'm not sure what Beast means, but I found something that looks like its spec here.

The ADS-B specification is pretty easy to read. Basically every message is 112 bits long and has the following structure:

+----------+----------+-------------+------------------------+-----------+
|  DF (5)  |  CA (3)  |  ICAO (24)  |         ME (56)        |  PI (24)  |
+----------+----------+-------------+------------------------+-----------+

The DF (downlink format) field can be used to figure out whether this is an ADS-B message. This time I only care about DF=17 or DF=18 messages, the only messages in ADS-B format. CA (capability) is kind of boring: capabilities of the hardware that broadcasts the message. ICAO (International Civil Aviation Organization) 24-bit address or (informally) Mode-S "hex code" is a unique identifier of the aircraft that normally never changes. ME (message extension) is the actual message. The contents of this field depend on its first 5 bits, the typecode. For example, aircrafts identify themselves and send their altitude information in messages with different typecodes. This time I want to at least recognize aircrafts' callsigns (TC 1-4) and their altitude (TC 9-18, 20-22).

nom

Just in case you are not familiar with nom, it is a parser combinator written in Rust. The most basic thing you can do with it is import one of its parsing functions, give it some byte or string input and then get a Result as output with the parsed value and the rest of the input or an error if the parser failed. tag for example is used to recognize literal character/byte sequences.

use nom::bytes::complete::tag;

fn parser(s: &str) -> IResult<&str, &str> {
  tag("Hello")(s)
}

assert_eq!(parser("Hello, World!"), Ok((", World!", "Hello")));

nom also has a bunch of combinators, helpers that allow us to apply many parsers in a sequence, or apply parsers conditionally etc.

This time I am going to parse byte input (&[u8]), because this is what we get from a raw TCP server started by dump1090. Parsing bytes is as easy as parsing strings:

use nom::bytes::complete::tag;

fn parser(s: &[u8]) -> IResult<&[u8], &[u8]> {
  tag([0x01, 0x02, 0x03])(s)
}

Parsing ADS-B messages

Parsing ADS-B messages is basically a matter of recognizing some bytes, then taking some more bytes and interpreting them as either a number or a string. The only tricky part is that some parts of the message are 5 or 3 bits long. Normally you would take a byte and shift some bits but fortunately nom has nice helpers for bits as well.

Here is the ADSBFrame struct that we want to ultimately build:

struct ADSBFrame {
    downlink_format: u8,
    capability: u8,
    icao: String,
    payload: AdsbMessage,
}

enum AdsbMessage {
    Identification(Callsign),
    BarometricAltitude(f64),
    GNSSAltitude(usize),
    Unknown(u8),
}

First, I need to parse the Mode-S Beast frame header I mention above. I keep it very simple because I just want to discard it and read the information I'm interested in.

fn mode_s_beast_header(input: &[u8]) -> IResult<&[u8], &[u8], ()> {
    let header = tuple((tag([0x1a]), tag([0x33]), take(6u8), take(1u8)));
    recognize(header)(input)
}

All frames start with 0x1a. The next byte, 0x33 represents Mode S messages (apparently there are more modes) and since I'm only interested in Mode S messages I expect 0x33 and just error if the message is not Mode S. Next is the MLAT timestamp. Honestly, I don't know what it's for but I know that it's always 6 bytes long so I just take the next 6 bytes. Finally there is a single byte RSSI (received signal strength indicator). I'm not interested in this information either so I just take another byte. Then the recognize combinator is used to return the successfully parsed input as is.

The following bytes are the actual ADS-B message. First I parse DF and CA fields. DF is 5 bits long and CA is 3 bits long. I use bits module of nom to parse the two and return them as a tuple.

fn df_ca(input: (&[u8], usize)) -> IResult<(&[u8], usize), (u8, u8), ()> {
    use nom::bits::complete::take;

    let ((input, offset), df) = take(5u8)(input)?;
    let ((input, offset), ca) = take(3u8)((input, offset))?;
    assert!(offset == 0);
    Ok(((input, offset), (df, ca)))
}

Next, I parse the ICAO address. The returned input from the df_ca becomes the input for icao parser. We take 3 bytes and then format them as a hex string, which is what ICAO addresses are normally represented as.

fn icao(input: &[u8]) -> IResult<&[u8], String, ()> {
    let (input, icao) = take(3u8)(input)?;
    Ok((
        input,
        format!("{:02x}{:02x}{:02x}", icao[0], icao[1], icao[2]),
    ))
}

The next part is the actual message. It is a bit more complicated because the first 5 bits of the message determine the type of the message. Depending on what the type is, the rest of the message needs to be parsed differently. nom provides us with an alt combinator that tries to run multiple parsers and returns the result of the first one that succeeds. This is exactly what we need. The parsers that don't succeed need to "soft fail" so that alt can try the next one. This is possible by returning Err(nom::Err::Error(())) from the parser.

In each message parser we check what range the typecode falls into:

const TYPECODE_IDENTIFICATION_RANGE: Range<u8> = 1..5;
const TYPECODE_POSITION_BAROMETRIC_RANGE: Range<u8> = 9..19;
const TYPECODE_POSITION_GNSS_RANGE: Range<u8> = 20..23;

Here's how I parse the identification message:


fn identification(input: &[u8]) -> IResult<&[u8], AdsbMessage, ()> {
    let ((_, offset), tc) = typecode((input, 0))?;
    if !TYPECODE_IDENTIFICATION_RANGE.contains(&tc) {
        return Err(Err::Error(()));
    }

    let ((input, _), _) = aircraft_category((input, offset))?;
    let (input, callsign) = callsign(input)?;
    Ok((input, AdsbMessage::Identification(callsign)))
}

callsign is a bit tricky because it is not encoded as ASCII as you would maybe expect. Instead, every character (expect numbers) is encoded with just 6 bits, which are exactly the lower 6 bits of the ASCII representation of the character. This means that A-Z characters are 1 to 26 in decimal.

fn callsign(input: &[u8]) -> IResult<&[u8], String, ()> {
    // https://mode-s.org/decode/content/ads-b/2-identification.html
    let ((input, offset), mut chunks) = count(nom::bits::complete::take(6u8), 8)((input, 0))?;
    assert!(offset == 0);
    chunks.iter_mut().for_each(|chunk| {
        if (1..27).contains(chunk) {
            *chunk |= 0x40;
        }
    });
    Ok((
        input,
        String::from_utf8_lossy(&chunks).trim_end().to_owned(),
    ))
}

There are two types of position messages: barometric and GNSS (geometric). Geometric altitude is measured with GPS but I actually couldn't get any messages of this type.

// https://mode-s.org/decode/content/ads-b/3-airborne-position.html#altitude-decoding
fn barometric_altitude(input: &[u8]) -> IResult<&[u8], AdsbMessage, ()> {
    use nom::bits::complete::take;

    const ALTITUDE_BITS: u8 = 12u8;

    let ((_, offset), tc) = typecode((input, 0))?;
    if !TYPECODE_POSITION_BAROMETRIC_RANGE.contains(&tc) {
        return Err(Err::Error(()));
    }

    // Skip surveillance status and single antenna flag
    let ((input, offset), _) = tuple::<_, (u8, u8), _, _>((take(2u8), take(1u8)))((input, offset))?;
    let ((input, _), alt) = take::<_, u16, _, _>(ALTITUDE_BITS)((input, offset))?;
    let q = (alt >> 8) & 1;
    let alt = remove_nth_bit(alt, 4);

    // TODO: Parse altitudes for q=1 (> 50175ft) using Gray code
    match q {
        1 => {
            let ft: f64 = (alt as f64) * 25.0 - 1000.0;
            Ok((input, AdsbMessage::BarometricAltitude(ft * 0.3048)))
        }
        _ => Err(Err::Error(())),
    }
}

fn remove_nth_bit(input: u16, n: u8) -> u16 {
    let upper = input & (0xfffe << n);
    let lower = input & ((1 << n) - 1);
    (upper >> 1) | lower
}

Parsing barometric altitude requires removing one so-called Q-bit from the sequence of 12 bits. This bit affects which formula should be used that changes at ~15293m altitude. Then it is as simple as putting the decimal representation of the remaining 11 bits in the formula:

# For q=0
h = (25 * N - 1000)

Now we just need to put it all together, redirect outputs of parsers to inputs of other parsers until we get the final ADSBFrame struct.

fn adsb_frame(input: &[u8]) -> IResult<&[u8], ADSBFrame, ()> {
    let (input, _) = mode_s_beast_header(input)?;
    let ((input, _), (df, ca)) = df_ca((input, 0))?;
    if !ADS_B_DOWNLINK_FORMAT_RANGE.contains(&df) {
        return Err(Err::Failure(()));
    }

    let (input, icao) = icao(input)?;
    let (input, payload) =
        alt((identification, barometric_altitude, gnss_altitude, unknown))(input)?;
    Ok((
        input,
        ADSBFrame {
            downlink_format: df,
            capability: ca,
            icao,
            payload,
        },
    ))
}

The rest is just connecting to the raw TCP server and parsing the messages as they come in. There is nothing interesting about that so this where I'm going to stop. I hope you enjoyed this article and learned something new about ADS-B and nom.

What happens when you type a URL into your browser: The whole story

Kirill Vasiltsov — Wed, 07 Dec 2022 03:50:49 +0000

A lot of things happen after you type a URL in the address bar of your browser and press Enter, and before the browser can show the page to you. First of all, the browser needs to resolve the hostname part of the URL to an IP address of the web server. This is because other computers on the Internet are accessible by their IP addresses, not their names.

IP addresses look like this 172.217.175.78 (IPv4) or like this 2001:4860:4860::8888 (IPv6). The browser tries to learn both and then use an algorithm with a weird name "Happy Eyeballs" to decide which to use for better performance. In fact you can skip the domain name resolution altogether and just type the IP address directly if you know it.

The mapping from the (sub)domain to the address could be right in the browser's cache, but sometimes the browser needs to get the answer elsewhere. For example, in your operating system's cache or even from a remote DNS (Domain Name System) server, which is also called a nameserver. DNS is also the name of the protocol that is used to query these specially designed servers and find out which (sub)domains map to which IP addresses. A protocol is a language that two computers on the network can understand and DNS is just one of the many. Your OS likely has an API that applications like a browser can use to send DNS queries to the Internet. For example, the getaddrinfo function from C library, which has many other useful functions used by both applications and the operating system. If your OS does not find the answer in its DNS cache either, it sends a DNS query to the configured nameserver. The query asks the server for the A (or AAAA) record, which is an entry in the database that maps the (sub)domain to an IPv4 (or IPv6) address.

Yet another way to resolve the domain name is mDNS (Multicast DNS). In some cases, like when the top-level domain is .local, the computer would send a special message to every device on the LAN that asks "whoever has this domain name - tell me your IP address". If some device indeed has the domain name in question it sends its IP address in the response to your computer. Sending to every device on LAN is possible by using a multicast IP address.

How does your computer know the address of the DNS server? You might have configured it manually (like 8.8.8.8) or it might have been configured automatically by DHCP (Dynamic Host Configuration Protocol), which is also used by your computer to get its own IP address from your LAN (or your ISP's) router. Once the nameserver's IP address is known, the operating system opens a UDP socket, a special entity (an actual file in Linux) that is used to communicate on the network. The socket is assigned a port number from 1024 to 65535 that identifies the socket locally. The remote server has a similar open UDP socket but with a port number 53. UDP is a transport-level protocol that is used to "carry" higher-level messages like DNS queries over the Internet.

I know what you are thinking: "That's a lot of protocols!". And you are right, because there are more, so buckle up for the ride.

Quite a few things happen before the UDP messages called datagrams reach the nameserver and before the response comes back to your computer. Because getting the actual page from the web server is a similar process, I return to it in detail below. For now, imagine that the nameserver successfully received your query. The nameserver might not have an answer for you, in which case it forwards the query to other nameservers and those nameservers can repeat the process until the authoritative nameserver for that domain either gives you the answer or just says "I don't know" and ruins your day. Suppose the address exists and getaddrinfo function used by your browser returns with an IP address, which the browser can finally use to send the request for the page.

To get a web page, browsers use HTTP and HTTPS. HTTP is an application-level protocol that makes it easier to express requests like "I want a resource at path /cats.html" or "Save this user's data at path /users". It would be almost impossible to make this a part of a transport-level protocol. The browser assumes that there is an HTTP server listening for requests at the IP address it just learned. That server usually has an open TCP socket with port number 80 or 443. TCP, like UDP, is the transport-level protocol which usually "carries" HTTP messages, though it can be used to "carry" DNS as well. The browser needs to only create a valid HTTP (or HTTPS) request that looks like this, literally:

GET / HTTP/1.1
Host: github.com

It contains a verb (GET) that reflects what the browser wants to do, the path of the resource (/), the protocol version used (HTTP/1.1) and the Host header that is a (sub)domain name. There is a bunch of other headers that can reflect the user's preference for a certain language of the page (Accept-Language header), information that identifies the user (Cookie or Authorization header) etc.

Then the browser asks the operating system to open a TCP socket and send the HTTP(S) request to the IP address of the server and port 80 or 443 (which is usually expressed together as 172.217.175.78:80). The opened TCP socket is assigned some port number from 1024 to 65535.

The browser does not need to know how to create TCP messages (called segments) at all - that is handled by the implementation of the TCP/IP stack that is part of any major operating system. The OS creates the first TCP segment and sets the source and destination port numbers along with some other useful information like sequence number to guarantee ordered delivery. It would be a mess if the verb GET became EGT in the process. The sequence number is needed because a single application-level message can be too big to fit in a data link layer frame, which usually has a maximum size of about 1500 bytes. Because of this limit HTTP messages very often need to be split into many small transport layer segments.

The sequence number only makes sense within a single connection, which is a transport layer concept. This means that two devices on the network must first establish a connection and only then exchange messages. In TCP connections are created through a three-way handshake. First, your computer sends a TCP segment with its flag field set to SYN. The web server responds with a TCP segment with a flag SYN-ACK and finally your computer sends the ACK segment as the response. After that your computer and the web server are ready to exchange messages. Like I said, even delivering the first segment is a lot of work so read further.

Nowadays web servers often only expect HTTPS messages at port 443, designed for encrypted communication. This prevents eavesdropping which is very easy with plain HTTP thanks to traffic analyzers like tcpdump or Wireshark (see some examples below). HTTPS is basically HTTP that enables privacy by adding another layer of communication - TLS (Transport Layer Security). TLS relies on public key cryptography for creating a private session between the client and the server. TLS version 1.3 uses the X25519 algorithm to make two computers exchange their public keys and then agree on some shared secret that will be used to encrypt (and decrypt) individual HTTP messages (or other application data).

This secret relies on some symmetric encryption algorithm, like AES. For example, AES is used when you access this blog.

This key exchange happens via the TLS handshake which takes only one round trip from the client to the server.

Simply encrypting your communication channel is not enough. The browser needs to know if it can trust whoever it is about to talk to, so it checks the validity of the TLS certificate that is sent in a ServerHello response during the handshake. This certificate contains the server's public key and is itself encoded with the public key of some certificate authority (CA) that your browser/computer trusts a priori. Not all certificates are valid all the time - they can expire or be revoked. Because of this, the browser sometimes needs to use OCSP (Online Certificate Status Protocol) to send a request to the CA's server and verify that the TLS certificate is valid.

If everything is alright, the TCP connection and the secure TLS channel is established.

Once the connection is established the browser encrypts the first HTTP request and sets the now-encrypted HTTPS request as the TCP segment's payload. Then the operating system "wraps" this TCP segment in an IP packet and sets the source and destination addresses along with other useful information like protocol version (4 or 6). This is a good time to point out that IP itself is a protocol. After all IP is an abbreviation of Internet Protocol! This is the level at which routing across networks happens and allows your packet to reach the destination. Finally, the OS "wraps" the IP packet in an Ethernet frame. Ethernet is the lowest, link layer protocol that uses MAC addresses to send messages between NICs (Network Interface Controller) of two or more devices. The OS uses the driver software of the network interface (which is called something like eth0 on your computer) to send the Ethernet frame as physical signals.

You are probably noticing some pattern. The system keeps wrapping, or encapsulating things into other things. This is the known as the TCP/IP model of networking. The TCP/IP model organizes protocols in layers such that each layer is only concerned with its own "job": data link layer only needs to deliver (and verify integrity of) Ethernet messages by MAC address within a LAN. Network layer is concerned with routing IP packets (which encapsulate link layer messages) across networks separated by routers. Transport layer can provide retransmission of lost network layer packets and their order. Application layer can be used for whatever you want.

A message at every layer begins with a header that is just a bunch of bytes in certain order. These bytes have special meaning that is defined in a RFC. For example, HTTP/1.1 specification lives in RFC 9112. IP packet headers include information like protocol version and total length of contents before the source address field. TCP segment headers include information like sequence number, source/destination port number, window size etc. In the screenshot below, I used Wireshark to analyze my own traffic. I ran a dig command to resolve my blog's domain name kirillvasiltsov.com to an IP address. You can see encapsulation in action: Ethernet header is marked with yellow, IP header with blue, UDP header with orange and the rest is DNS header + message.

Up until now we assumed that our IP packets containing TCP/TLS handshake messages magically reach the web server. Before we look at the HTTP exchange, we need to clear up how the first TCP connection initiation segment that is sent out of your computers's network interface even reaches the destination. Well, most home computers only have one network interface so there is only one way out anyway. While your computer is not a router, it has a routing table that it uses to make routing decisions too. The decision making is the same for all devices - if the destination IP address is not in your subnet (which is usually your whole home network) then send the message to the default gateway. The default gateway is your router and both its IP address and MAC address is what your computer learns via DHCP at some point during the boot.

If you have several computers on your LAN connected with a switch, then if you try to access some web page hosted on one of those computers, the HTTP request will not go through the router but go directly to the neighbor. How can the message find its way? Your computer, like a router, has ARP (Address Resolution Protocol) cache. ARP is yet another protocol that is used to learn MAC addresses of devices that have a particular IP addresses. So when you send a HTTP request to a local web server with an IP in your subnet, your OS checks the ARP table to set the correct destination MAC address, which is then used by the switch to forward the message out of the correct network interface.

Suppose that the web page you want to see is hosted by a server in a remote network. The router checks for an existing route in its routing table. If there is no exact match, the router makes a similar decision to your computer - forward the packet out of its own default gateway. The router usually has only one way out to the WAN (Wide Area Network) too, so it just forwards the packet to your ISP's router on the other side, using its default route 0.0.0.0/0 with an associated network interface. This route is used for all destinations that your router does not know (not directly connected or learned from other routers in the network). Before the router even makes the decision it needs to unwrap (or de-encapsulate) the Ethernet frame and read the IP packet to know where it is headed. After that, the router creates a new Ethernet frame, sets its own source MAC address, wraps the IP packet and sends it out of the chosen network interface.

Next, it is your ISP's job to make sure the IP packets reach the correct destination. Your ISP is probably a very big network with many ways in and out. But even then, it is likely that the web server is not directly connected to that network. It could be on the other continent! However, ISPs do not have a "default route" because there is no hierarchy between autonomous networks (called autonomous systems) on the Internet. Instead autonomous systems choose to exchange NLRI (Network Layer Reachability Information) which is basically the list of subnets reachable from that network. BGP (Border Gateway Protocol) is another protocol used by AS to exchange this kind of messages. The ISP's routers probably have a matching entry in their BGP routing table (which is synchronized across literally all routers on the ISP's network via iBGP). Your request is forwarded through the correct router. Then it passes through as many AS as needed until it finally reaches the web server.

BGP exchange does not happen during the request so I will not go deeper and I frankly don't know much more anyway.

It is also possible that the IP address that the domain name resolved to is not really the web server's address. Very often there is more than one server instance with the same software to spread the burden of processing requests. Because of this, web server instances have a load balancing reverse proxy in front of them that proxies TCP connections to the proper instance's IP address that remains private. The IP address you get though is the IP address of the reverse proxy. So strictly speaking, the process of choosing the best proxy target (such as round robin) also takes place during the request.

Now that it is clear what route the TCP and TLS handshake messages take, we can look at the HTTP request/response exchange.

The server's machine receives Ethernet frames destined for the machine's MAC address. The server's operating system de-encapsulates the frame and looks at the IP packet. If there are no internal firewall rules that ban IP packets from certain addresses, the system de-encapsulates the IP packet and reads the TCP segment. If it appears to be out of order, the system does not send an ACK response until it receives all segments and potentially waits for the client to re-transmit the lost segment. If everything is OK, the system puts the TCP segment in the TCP receive buffer. If the buffer is full it send the TCP response with a window size set to 0 meaning that the server is busy and cannot receive TCP segments right now.

At the same time the OS notifies the process listening at the port that matches the destination port in the segment that there is TCP data to receive. The process reads the data from the buffer until there is nothing left (EOF) and processes it as the software engineer intended.

In this case, the TCP data can be either of the following:

HTTPS message encrypted using the shared secret that two parties agreed on earlier during the TLS handshake
plain HTTP message forwared from the reverse proxy if the proxy is configured to terminate TLS connections

Suppose we receive the decrypted form of the HTTP request that the browser sent.

GET / HTTP/1.1
Host: github.com

The server parses the request and applies some logic based on the verb and path (and other headers if present). For example it might check whether the user is authenticated and authorized to access the resource. Depending on the request, the server crafts an HTTP response that looks something like this:

HTTP/1.1 200 OK
content-type: text/html; charset=utf-8
cache-control: max-age=0, private, must-revalidate
set-cookie: _gh_sess=...; path=/; secure; HttpOnly; SameSite=Lax

<body>

The response always includes the status code. In this case it's 200 which means OK. It may include other headers like cache-control that tell the browser (or the caching servers along the way) whether to cache the response for some time. In the example above the server asks to not cache the response at all. Another header is content-type that specifies the format and encoding of the body. In this case your response includes an HTML page as its body. The server program (or the library it uses) asks the OS to encapsulate the response in one or more TCP segments and send it by using the send() system call. These TCP segments have a destination port number chosen by the client earlier as its source port number. The operating system then puts the segments into the TCP send buffer. Segments in the buffer are ultimately encapsulated in IP packets with the server instance's IP address as the source address. Then the IP packets are encapsulated in Ethernet frames and sent out of the network interface.

The response tracks the similar route out of the server instance's network as the route that your request took. When it reaches the browser's machine, the system de-encapsulates the Ethernet frames, the IP packets and the TCP segments. All segments with the destination port that matches the port the browser asked the OS to open are forwarded to the browser's process. The browser's code is responsible for reading the appropriate buffer until EOF (until there is nothing to read). Those bytes represent an encrypted HTTPS response.

In fact the bytes might be a compressed version of the encrypted response. This is regulated by the Accept-Encoding request header that tells the server that it is OK to compress the response with something like gzip. In practice, it appears that compressing TLS messages undoes the protection to some degree so it's not recommended to compress encrypted responses. However, if plain HTTP is used, then the browser must first decompress the response before parsing it as HTTP.

The browser uses the shared secret agreed on earlier during the TLS handshake to decrypt the response. Then the encrypted bytes are parsed as HTTP. If the content-type header happens to be text/html the browser starts to parse the response body as HTML. It starts with the <head> element. Usually a web page contains a few links to the page's asset files like CSS or JavaScript. As soon as the browser discovers a <link rel="stylesheet"> to a CSS file or a <script> tag with JavaScript inside or a src attribute link to the JavaScript file, it blocks rendering until the CSS can be downloaded and JavaScript - downloaded and executed. To download asset files the browser opens new TCP connections that follow the similar proccess we saw earlier. In some cases (which I am not sure about) the same TCP connection can be re-used.

The assets do not necessarily live on the same server as the page. Often the resources are served from a CDN (Content Delivery Network). This is the network of servers around the globe that cache the origin server's responses physically closer to the user to reduce request latency and load on origin servers. If the requested page has links to CDN-hosted assets, the domain resolution is required for those domain names as well.

By specification, a single TCP connection is re-used for assets in HTTP/2. Interleaving TCP segments belonging to different responses on the wire by dividing an HTTP message itself into frames is one of the advantages of HTTP/2. This is called multiplexing.

After the browser downloads CSS, it parses it to build CSSOM (CSS Object Model). This is a tree representation of the styles and their scope in the page. The downloaded JavaScript also has to be executed before the browser can continue to render the page. To do that, the browser uses a JavaScript engine that turns JavaScript code into machine instructions. Different browsers use different engines.

For example, V8 engine used in Chrome runs JavaScript in one or more isolates, small virtual machines with their own heap.

Once the browser is done building CSSOM and executing JavaScript, it parses the rest of the HTML document to build DOM (Document Object Model). DOM is a tree representation of the structure of the page. DOM and CSSOM are combined into a render tree, the information that is actually used to calculate the size and position of DOM nodes and determine their visibility. The browser uses the result of calculation to finally paint visible objects to the viewport.

If CSS contains animations then depending on what property is animated the browser may also render them on a separate, compositor thread that is not blocked by executing JavaScript. That thread does not need to bother about re-calculating the layout every single frame because many animations are treated as not changing the layout, or the place of the animated element in the document flow.

The browser also looks at the Cache-Control header that may ask the browser to cache the response locally. If caching is enabled, the browser caches the response for the specified time. Subsequent requests will not go all the way to the origin serve and instead the cached response will be returned immediately.

And that's pretty much the whole story. I am sure that it is possible to go even deeper but I feel like those pieces are less relevant to the actual request-response cycle. If I missed something or if some information is just wrong, please let me know on Twitter or send me an e-mail!

Writing and deploying Rust Lambda function to AWS: Image glitch as a service

Kirill Vasiltsov — Fri, 10 Dec 2021 01:46:15 +0000

Japanese version: https://tech.prog-8.com/entry/2021/11/16/174709

Ever since AWS released Rust runtime for AWS lambda I've been wanting to try it out. In this article I am going to walk you through every step required to write and deploy a lambda written in Rust to AWS.

To avoid making this article too big I assume you are familiar with basic Rust, Docker and Node. Also make sure you have Rust toolchain, Docker and Node.js installed in your environment.

To avoid building yet another boring hello-world-like handler, we will build a n a n o s e r v i c e that takes an image and returns a glitched version of it (which you can use as a profile picture etc. but that is up to you). Pretty useless in isolation but still fun and just enough for a good walkthrough.

Start a fresh Rust project

Let's begin with a fresh Rust project.

cargo new glitch
cd glitch

Let's build the core of our API: a glitch function. Actually, two glitch functions. I must warn you that I'm not a professional glitch artist and that there is a lot of depth to glitch art, but the two simple tricks below will suffice. One trick is to just take a byte of the image you want to glitch and replace it with some random byte. Another trick is to take an arbitrary sequence of bytes and sort it. Rust does not come with a random number generator so we need to install it first:

[dependencies]
rand = "0.8.4"

And here's the byte-replacing glitch function. We put it in src/lib.rs.

use rand::{self, Rng};

pub fn glitch_replace(image: &mut [u8]) {
    let mut rng = rand::thread_rng();
    let size = image.len() - 1;
    let rand_idx: usize = rng.gen_range(0..=size);
    image[rand_idx] = rng.gen_range(0..=255);
}

Nothing extraordinary here, we just take a reference to our image as a mutable slice of bytes and replace one. Next is the sort glitch:

const CHUNK_LEN: usize = 19;

pub fn glitch_sort(image: &mut [u8]) {
    let mut rng = rand::thread_rng();
    let size = image.len() - 1;
    let split_idx: usize = rng.gen_range(0..=size - CHUNK_LEN);
    let (_left, right) = image.split_at_mut(split_idx);
    let (glitched, _rest) = right.split_at_mut(CHUNK_LEN);
    glitched.sort();
}

Again there is nothing complicated here. Note a very convenient split_at_mut method that easily lets us select the chunk we want to sort. CHUNK_LEN is a variable in the sense that you can try different values and expected different glitch outcomes. I randomly chose 19.

Finally, for more noticeable effect we apply these two functions multiple times as steps of one big glitch job.

pub fn glitch(image: &mut [u8]) {
    glitch_replace(image);
    glitch_sort(image);
    glitch_replace(image);
    glitch_sort(image);
    glitch_replace(image);
    glitch_sort(image);
    glitch_sort(image);
}

Next we move on to building a lambda.

Cargo.toml: Download required dependencies

These are the minimal dependencies we'll need.

[dependencies]
lambda_http = "0.4.1"
lambda_runtime = "0.4.1"
tokio = "1.12.0"
rand = "0.8.4"
jemallocator = "0.3.2"

lambda_runtime is the runtime for our functions. This is required because Rust is not (yet) in the list of default runtimes at the time of writing. It possible, however to BYOR (bring your own runtime) to AWS and that's what we're doing here. lambda_http is a helper library that gives us type definitions for the request and context of the lambda. tokio is an async runtime. Our handler is so simple that we don't need async but lambda_runtime requires it so we have no choice but to play along. Just in case you are unfamiliar with it think of it as a library that runs Rust futures. We won't need to worry much about async apart from defining our functions as async. Finally, there is jemallocator. We will get to it later.

main.rs: Handler

Alright, we have a glitch function but how do use it in our request handler? Let us define apply_glitch handler that takes the request, extracts image bytes from the body and copies the glitched version into the response.

use lambda_http::handler;
use lambda_http::Body;
use lambda_http::{IntoResponse, Request};

async fn apply_glitch(mut req: Request, _c: Context) -> Result<impl IntoResponse, Error> {
    let payload = req.body_mut();
    match payload {
        Body::Binary(image) => {
            glitch(image);
            Ok(image.to_owned())
        }
        // Ideally you want to handle Text and Empty cases too.
        // We use a special macro unimplemented!() that prevents the compiler from failing without all cases handled.
        _ => unimplemented!(),
    }
}

Note the useful IntoResponse trait that allows us to just return things like Strings and Vec<u8>s without thinking much about response headers.

main.rs: Main

Next, we need to simply wrap our actual handler in a lambda_http::handler. This creates an actual lambda that can be run by the lambda runtime we installed. Literally two lines of code to hook everything up.

use lambda_runtime::{self, Error};
use lambda_http::handler;
use jemallocator;

#[global_allocator]
static ALLOC: jemallocator::Jemalloc = jemallocator::Jemalloc;

#[tokio::main]
async fn main() -> Result<(), Error> {
    let func = handler(apply_glitch);
    lambda_runtime::run(func).await?;
    Ok(())
}

Don't forget the #[tokio::main] bit. This is an attribute macro from tokio that does some magic under the hood to make our main function async. The #[global_allocator] part is also needed to make the lambda work but we will get to it later.

Deploying to AWS

There are multiple ways to deploy this to AWS. One of them is using the AWS console. I find the console confusing for many tasks, even simple ones, so I am very excited that there exists another way: CDK. It is a Node.js library that allows us to define the required AWS resources declaratively with real code. It comes with TypeScript type definitions so in a lot of cases we don't even need to look into the documentation.

CDK project

The only downside of CDK is that it requires a couple things in our local environment: aws CLI and Node.js. Make sure the CLI is configured with your credentials. Next, install CDK:

npm install -g aws-cdk
cdk --version

CDK requires that some resources exist prior to any deployments like buckets that your CDK output (which is basically a CloudFormation stack) and other artifacts like Lambda functions are uploaded to. This is done with bootstrap command.

cdk bootstrap aws://ACCOUNT-NUMBER/REGION

Now we are ready to create a new CDK project which is responsible for deploying our lambda to the cloud. Create a lambda folder (or choose whatever name you want) in the root of your Rust project and execute the following command in it:

cdk init app --language=typescript

This will generate all the files we'll need. Open lambda\lib\lambda-stack.ts which should look like this:

import * as cdk from "@aws-cdk/core";

export class LambdaStack extends cdk.Stack {
  constructor(scope: cdk.Construct, id: string, props?: cdk.StackProps) {
    super(scope, id, props);

    // The code that defines your stack goes here
  }
}

Let's check that everything is OK by running cdk synth which does a dry run and shows you the CloudFormation code it would generate. Right now, there is not much we can do without installing additional constructs - the basic building blocks of AWS CDK apps, so let's do it first.

npm install @aws-cdk/aws-lambda @aws-cdk/aws-apigatewayv2-integrations @aws-cdk/aws-apigatewayv2 @aws-cdk/aws-apigatewayv2

Import these in your lambda/lib/lambda-stack.ts:

import * as apigw from "@aws-cdk/aws-apigatewayv2";
import * as intg from "@aws-cdk/aws-apigatewayv2-integrations";
import * as lambda from "@aws-cdk/aws-lambda";
import * as cdk from "@aws-cdk/core";

Now we can actually define a lambda function inside the constructor above:

const glitchHandler = new lambda.Function(this, "GlitchHandler", {
  code: lambda.Code.fromAsset("../artifacts"),
  handler: "unrelated",
  runtime: lambda.Runtime.PROVIDED_AL2,
});

code is where our binary lies (we will get to it soon). handler, normally, is the name of the actual function to call but it seems to be irrelevant when using custom runtimes, so just choose any string you want. Finally, runtime is PROVIDED_AL2 which simply means we bring our own runtime (which we earlier installed as a Rust dependency) that will work on Amazon Linux 2. Just a lambda is not enough, however. Lambdas are not publicly accessible from outside of the cloud by default and we need to use API Gateway to connect the function to the outside world. To do this, add the following to your CDK code:

const glitchApi = new apigw.HttpApi(this, "GlitchAPI", {
  description: "Image glitching API",
  defaultIntegration: new intg.LambdaProxyIntegration({
    handler: glitchHandler,
  }),
});

This code is pretty self-explanatory. It creates an HTTP API Gateway that will trigger our lambda, glitchHandler, which we defined above, on incoming requests. Note how CDK makes it easy to refer to other resources: by using actual references within code.

Building a binary

We're almost ready but we need to make sure that CDK can see and upload our lambda binary. Normally Rust puts the build output inside target/ folder and gives it the same name as your package name:

[package]
name = "glitch"

One weird thing about AWS Rust lambdas is that the binary needs to be named bootstrap. To do this, we need to add some settings to Cargo.toml:

[package]
autobins = false

[[bin]]
name = "bootstrap"
path = "src/main.rs"

This takes care of the name. Next, we could also change the output folder to artifacts so CDK can see it and cargo build the project directly but let's imagine that you want to work on this project in different environments. The bootstrap binary actually MUST be built with x86_64-unknown-linux-gnu target. This is not possible on e.g. Windows, so let's use Docker!

If you've ever used Docker with Rust you probably know that compiling can be painfully slow. This is because there is no cargo option to build only dependencies at the moment of writing.
Luckily, there is a very good project cargo-chef that provides a workaround. Here's how we use it in our Dockerfile (mostly copy-paste from the project's README):

FROM lukemathwalker/cargo-chef:latest-rust-1.53.0 AS chef
WORKDIR /app

FROM chef AS planner
COPY . .
RUN cargo chef prepare --recipe-path recipe.json

FROM chef AS builder 
COPY --from=planner /app/recipe.json recipe.json
# Build dependencies - this is the caching Docker layer!
RUN cargo chef cook --release --recipe-path recipe.json
COPY . .
RUN cargo build --release

FROM scratch AS export
COPY --from=builder /app/target/release/bootstrap /

With this, if we run:

docker build -o artifacts .

Docker will build a x86_64-unknown-linux-gnu binary and put it inside artifacts folder. Finally, CDK has all it needs to successfully deploy our lambda! So let's do it (you need to be inside the lambda folder):

cdk deploy

Ideally we want to know the URL of our API Gateway immediately and there is a nice way to make CDK output this info by writing a couple more lines:

new cdk.CfnOutput(this, "glitchApi", {
      value: glitchApi.url!,
    });

Now if we add the --outputs-file option to the cdk command like this:

cdk deploy --outputs-file cdk-outputs.json

we will see a lambda/cdk-outputs.json file that has the URL inside:

{
  "LambdaStack": {
    "glitchApi": "https://your-gateway-api-url.amazonaws.com/"
  }
}

Glitch!

That was a lot of work but now we can finally call our glitch API. It would be mean of me to not share a working link here as well. So here's the command that you can try right now to get a feel of the API:

curl -X POST https://ifzc7embya.execute-api.ap-northeast-1.amazonaws.com --data-binary "@pic.jpg" -o "glitches/$(date +%s).jpg"

I cannot guarantee that the service is going to be always up, though.

Generally, to use the API ypu need to prepare an image file you want to glitch and do this:

curl -X POST https://your-gateway-api-url.amazonaws.com --data-binary "@pic.jpg" -o glitched.jpg

You should see a glitched.jpg file that is glitched and hopefully looks aesthetically pleasing! Now that everything is working, you can play with the settings like the number and order of glitches, the size of the chunk that is sorted etc. If you know other simple ways to achieve nice-looking glitches, feel free to tell me on Twitter!

Examples

Here are some of my favorite glitches I generated while playing with the API.

Wait...what about jemallocator? Oh yes, I promised to explain this as well. So, it seems that for quite a long time AWS lambdas needed to be built for x86_64-unknown-linux-musl target. This was a pain because it needed a musl toolchain which is not available by default. However, it looks like now you CAN use x86_64-unknown-linux-gnu but with a caveat: you need to use jemallocator. This is literally just one install and one more line to your code. The default allocator Rust uses on Unix platforms is malloc. I do not know if this limitation will disappear in the future.

Visitor pattern in TypeScript

Kirill Vasiltsov — Thu, 28 Jan 2021 11:14:28 +0000

Imagine that you are writing a program that can draw different shapes: circles, triangles, squares, etc. You represent them by corresponding data types. Depending on a language you use, these shapes become distinct classes, structs, members of an enum or parts of some algebraic data type. Because you also want to be able to do something with these shapes, you describe that behavior somewhere. For example, if you chose to represent shapes as classes, behavior can be described as methods on these classes. Suppose you decide to support one basic behavior: drawing.

The goal of this article is not to show you some quick way to make your shapes drawable and call it a day. Instead, before we implement an outline of such a program, let's think about how we could structure our code. Let's start with a simple table of our shapes and their (possible) behavior.

Somewhere in our code we just want to call draw() and watch it magically draw a correct shape depending on which option is currently selected. We definitely don't want to concern ourselves with the details of drawing in the same place we handle a user's click. But each shape is drawn differently so we need to describe the behavior three times -- once for each shape. If we had four shapes, we would need to describe the behavior four times.

Like I said, where exactly we have to describe this behavior depends on the language we choose. Some languages allow for more than one way to do this and deciding which is better is no easy task. It was even called the "The Expression Problem" and Bob Nystrom has a nice short explanation in his book Crafting Interpreters. The "problem" refers to the fact that when we have a lot of shapes AND a lot of behaviors, some languages require us to do a lot of work just to add a new shape and some languages require us to do a lot of work just to add a new behavior. There is no easy compromise. However (as you probably already have guessed) there is a design pattern that makes our lives easier in such situations -- the Visitor pattern.

JavaScript and TypeScript are among those languages which give us a little bit more freedom than others. Today I want to talk specifically about TypeScript because it makes some type-safe patterns like the Visitor pattern possible and useful in an otherwise dynamic language.

So, in TypeScript we have a bunch of ways to achieve what we want, but not all of them are good. Assume we have three classes that represent our shapes.

class Square {}
class Circle {}
class Triangle {}

type Shape = Square | Circle | Triangle

The bad way would be to just have a single draw() function and use conditions to find out how to draw a particular shape:

function draw(shapes: Array<Shape>) {
  for (const shape of shapes) {
    if (shape instanceof Square) {
      // draw Square
    } else if (shape instanceof Circle) {
      // draw Circle
    }
  }
}

The problem with this approach is that it is not type-safe. The compiler does not tell us that we forgot to handle the Triangle case. This will cause a runtime error when we try to draw a Triangle. Note that in languages with pattern matching like Haskell or Rust, the compiler would warn us about unhandled cases.

One type-safe alternative is to define a Drawable interface. interface here means roughly the same thing it means in many other OOP languages.

interface Drawable {
  draw: () => void
}

Now if we slightly modify our draw function to expect an array of Drawable things, not just Shapes, we will get a compile error if we try to pass it an array that contains something that does not implement draw().

class Square {
  draw() {}
}

class Triangle {}

function draw(shapes: Array<Drawable>) {
  for (const shape of shapes) {
    shape.draw() // Square, etc...
  }
}

draw([new Triangle()]) // Compile error!

Good. Even better if we force every shape to implement it which is another nice thing possible in TypeScript!

class Square implements Drawable {
  draw() {}
}

class Circle implements Drawable {
  draw() {}
}

class Triangle implements Drawable {
  draw() {}
}

Imagine at some point we decide to support one more behavior -- area calculation with area(). This is where we run into the "Expression problem" I mentioned above. First we would need to define a new interface:

interface Area {
  area: () => number
}

and make each shape implement it in addition to Drawable!

class Square implements Drawable, Area {
  draw() {}
  area() {}
}

class Triangle implements Drawable, Area {
  draw() {}
  area() {}
}
// omitted

So how can we reduce the amount of code we have to touch every single time we add a new behavior? How can we make sure that we didn't forget to handle a particular behavior on a particular share? Meet the Visitor pattern.

Visitor pattern

There are probably many ways to explain this pattern. I think that it is easy to understand it from the point of view of the bad example I gave in the beginning of the article. Let me repeat it here.

function draw(shapes: Array<Shape>) {
  for (const shape of shapes) {
    if (shape instanceof Square) {
      // draw Square
    } else if (shape instanceof Circle) {
      // draw Circle
    }
  }
}

What if there was a way to group all possible cases in one place, just like we grouped conditions in one function? Here's one such way:

interface ShapeVisitor {
  visitCircle(shape: Circle): void
  visitSquare(shape: Square): void
  visitTriangle(shape: Triangle): void
}

visit is a weird word, but in this context it basically means "handle". Just in case you want to complain, know that I am not the one who came up with the pattern. Now, a class that implements this interface is a class that must have all of these methods which describe concrete steps needed to draw a shape. To make sure some class implements all of these "handlers" we can just use the implement keyword. Only classes can implement things in TypeScript so instead of a function we create a class, Drawer, whose responsibility is to draw.

class Drawer implements ShapeVisitor {
  visitCircle(shape: Circle) {}

  visitSquare(shape: Square) {}

  visitTriangle(shape: Triangle) {}
}

Remember, our goal here is to get rid of the need to add new behavior to each class. This means our old interface Drawable with a draw method won't do. Let us change Drawable interface to this:

interface Drawable {
  accept(visitor: ShapeVisitor): void
}

What is accept? That's just another convention of this pattern. You can name it anything you want but accept makes it clear that you are trying to follow the pattern. This method's job is to take the visitor and then choose which of the visitor's methods we should use to draw this particular shape. Let's implement Drawable for one of our shapes:

class Square implements Drawable {
  accept(visitor: ShapeVisitor) {
    visitor.visitSquare(this)
  }
}

// similar for every other shape

This finally allows us to add a draw method to Drawer.

class Drawer implements ShapeVisitor {
  /* visit functions */

  draw(shape: Drawable) {
    shape.accept(this)
  }
}

Quite a lot of indirection but hopefully now you see how it works. Somewhere in our code we draw a shape a like this:

const drawer = new Drawer()
drawer.draw(new Square())

Now if we decide to support one more shape, e.g. a Star, we don't have to add code for every possible behavior to this new class. Instead we make it visitable and then implement the details in relevant visitors. The visitors, of course, will need to have a new method, like visitStar. We would start with adding it to the interface ShapeVisitor to make sure that every class that implements it has a visitStar method.

interface ShapeVisitor {
  visitCircle(shape: Circle): void
  visitSquare(shape: Square): void
  visitTriangle(shape: Triangle): void
  visitStar(shape: Star): void
}

This is type-safety that we could not have with a bunch of conditions.

The names visit and accept are not completely random, though, if you picture what's happening.

Sometimes it's best to just read the whole code so here's what we have written so far:

interface Drawable {
  accept(visitor: ShapeVisitor): void
}

interface ShapeVisitor {
  visitCircle(shape: Circle): void
  visitSquare(shape: Square): void
  visitTriangle(shape: Triangle): void
}

class Drawer implements ShapeVisitor {
  visitCircle(shape: Circle) {}

  visitSquare(shape: Square) {}

  visitTriangle(shape: Triangle) {}

  draw(shape: Drawable) {
    shape.accept(this)
  }
}

class Square implements Drawable {
  accept(visitor: ShapeVisitor) {
    visitor.visitSquare(this)
  }
}

class Circle implements Drawable {
  accept(visitor: ShapeVisitor) {
    visitor.visitCircle(this)
  }
}

class Triangle implements Drawable {
  accept(visitor: ShapeVisitor) {
    visitor.visitTriangle(this)
  }
}

You may have noticed that there is no need to call the Drawable interface Drawable. That is true. ShapeVisitor can be implemented by many different classes, not just Drawer but also Filesystem or Animate or whatever. We want to be able accept all of them without editing every shape class. That's why it probably makes sense to just call it VisitableShape or something.

Caveats

If you are a sharp reader, you probably noticed that nothing prevents us from doing this:

class Triangle implements Drawable {
  accept(visitor: ShapeVisitor) {
    visitor.visitSquare(this) // Attention here.
  }
}

I expected it to work out of the box like in some other languages, but it didn't. This is something I couldn't find a workaround for, so if you know, let me know!

Optional arguments in Rust

Kirill Vasiltsov — Fri, 18 Sep 2020 08:24:31 +0000

If you come to Rust from languages like Javascript which have support for optional arguments in functions, you might find it inconvenient that there is no way to omit arguments in Rust. However, there are good ways to simulate optionality and I'm even starting to think that they make code more readable than simply omitting things here and there.

Approach #1: two functions

This is the least creative approach, but absolutely legitimate. The idea is to create two functions with different number of arguments.

fn add_two(a: usize, b: usize) -> usize {
    a + b
}

fn add_three(a: usize, b: usize, c: usize) -> usize {
    a + b + c
}

The third argument here is "optional" in the sense that you have the option to not use the function and use add_two instead.

Approach #2: Option

Option is meant to represent something that might exist or might not exist. We can definitely use it to represent optionality in function arguments!

fn greet_name_optional(name: Option<String>) {
    println!("Hello, {}!", name.unwrap_or(String::from("world")))
}

greet_name_optional(None);
greet_name_optional(Some(String::from("Ferris")));

// Hello, world!
// Hello, Ferris!

unwrap_or is handy when you want to provide a "default" value if None is passed. The cons of this approach is that you still have to pass None to greet_name_optional when there is nothing else to pass and wrap existing values in Some.

Approach #3: Enum

Just like Option is simply an enum, we can create our own enum that better represents the thing that the function expects.

enum Name {
    Empty,
    Is(String),
}

This also allows us to provide the default value by implementing the Default trait:

impl Default for Name {
    fn default() -> Self {
        Name::Is(String::from("world"))
    }
}

The function then becomes very intuitive and easy to read:

fn greet_name(name: Name) {
    match name {
        Name::Empty => println!("Hello, {}!", Name::default()),
        Name::Is(value) => println!("Hello, {}!", value),
    }
}

greet_name(Name::Empty);
greet_name(Name::Is(String::from("Ferris")));

// Hello, world!
// Hello, Ferris!

I personally prefer the third approach for its readability, but it requires some work, because you might need to implement other traits like Display too.

How do you pronounce href?

Kirill Vasiltsov — Thu, 20 Aug 2020 11:05:49 +0000

I pronounce it as [href] where h is as h in the word "hello".

How to schedule serverless lambda execution with Github Actions

Kirill Vasiltsov — Fri, 14 Aug 2020 08:43:26 +0000

My Workflow

This workflow allows to schedule execution of serverless lambda functions. Some services like Vercel make deployment of lambdas very easy, but do not give you an option to execute them on schedule. I needed it in my own app (link below) to regularly cleanup a database of items that users save.

The trick is the cron jobs. For example, by adding this to your action:

on:
  schedule:
    - cron: "0 */1 * * *"

you can schedule your workflow to be run every 1 hour.

The cool thing is that you can manage authentication and all kinds of environment variables INSIDE your lambda and turn in into a simple API for the workflow to call: no credentials and arguments needed.

curl is accessible out-of-the-box so you can just run the command using the run field of the job.

Submission Category:

Maintainer Must-Haves

Yaml File or Link to Code

This is a relatively simple workflow so I'm going to just share YAML code here:

name: lambda-scheduler

on:
  schedule:
    - cron: "0 */1 * * *"

jobs:
  request:
    name: Request
    runs-on: ubuntu-latest
    steps:
      - name: Cleanup
        run: curl https://yourcoolwebsite.com/api/cleanup

Additional Resources / Info

The workflow is used in this repository. This is a Pocket-like app that allows you to save links for further reading without keeping them as open tabs. Any link older than 24 hours is automatically removed.

jlkiri / untab

Untab

https://untab.vercel.app/

View on GitHub

Read CLI command output in VSCode

Kirill Vasiltsov — Thu, 30 Jul 2020 08:55:14 +0000

VSCode can read from stdin. You need to use - flag to do it.

[command] --help | code -

Example:

node --help | code -

How to write a Queue in Rust

Kirill Vasiltsov — Wed, 15 Jul 2020 12:07:14 +0000

In this series I show the simplest way to build some data structures in Rust.

These implementations are not guaranteed to be the most performant. I only guarantee that they work as they are intended to work theoretically. If you are looking for the most performant solution consider using libraries (crates).

What is a queue?

A queue is a very common data structure, which can be used in a variety of situations. It is needed for solving low level problems such as CPU job scheduling, but also for modeling a real-life queue - such as technical support requests that need to be processed in sequence. It is called Queue because it works exactly like a real queue: first in - first out (FIFO).

When we add something to a queue we say that we enqueue it. When we remove something from a queue we say that we dequeue it. Here's a simple model of how it works:

Like a stack it can be implemented using Vec.

Create

First of all, let us define a struct and call it Queue:

struct Queue<T> {
  queue: Vec<T>,
}

We want our queue to be able to store different kinds of types so we make it generic by using T instead of any specific type like i32.

Now, to create a new queue we can do this:

let q = Queue { queue: Vec::new() };

But the more idiomatic way would be to define a new method for our queue, just like the one you used to create a new Vec:

impl<T> Queue<T> {
  fn new() -> Self {
    Queue { queue: Vec::new() }
  }
}

If you are not familiar with the impl (method) syntax you can read more about it here.

Enqueue and dequeue

Both enqueue and dequeue are easy to implement. We can use methods that are available on Vec:

fn enqueue(&mut self, item: T) {
    self.queue.push(item)
}

fn dequeue(&mut self) -> T {
    self.queue.remove(0)
}

Dequeuing can be done with remove - a very handy method which shifts (moves) the remaining elements to the left. The first item in the array we use to implement the queue is the head of our queue.

Utility methods

There are some other methods that are associated with queues. They are length, peek and is_empty.

length

Here we just reuse the len method of Vec.

fn length(&self) -> usize {
    self.queue.len()
}

is_empty

Same for is_empty.

fn is_empty(&self) -> bool {
    self.queue.is_empty()
}

peek

Here, again, we can use a very convenient method first that lets us take a look at the first item, or the head of our queue.

fn peek(&self) -> Option<&T> {
    self.queue.first()
}

Note that it returns a reference (&) and the reference itself is wrapped in an Option.

Now we have a functioning queue! Here's the full code:

struct Queue<T> {
  queue: Vec<T>,
}

impl<T> Queue<T> {
  fn new() -> Self {
    Queue { queue: Vec::new() }
  }

  fn length(&self) -> usize {
    self.queue.len()
  }

  fn enqueue(&mut self, item: T) {
    self.queue.push(item)
  }

  fn dequeue(&mut self) -> T {
    self.queue.remove(0)
  }
  fn is_empty(&self) -> bool {
    self.queue.is_empty()
  }

  fn peek(&self) -> Option<&T> {
    self.queue.first()
  }
}

And this is how you would you use it in code:

let mut queue: Queue<isize> = Queue::new();
queue.enqueue(1);
let item = queue.dequeue();
assert_eq!(item, 1);
assert_eq!(queue.is_empty(), true);

You can also see the full code on my Github.

What concept in programming you struggled with the most while learning?

Kirill Vasiltsov — Fri, 10 Jul 2020 11:45:55 +0000

Name anything, whether it is web-related programming, or not. The most difficult concept for me for a very long time has been asynchronicity. It was really hard to stop thinking in sequential execution.

React rendering cheatsheet

Kirill Vasiltsov — Thu, 09 Jul 2020 14:55:31 +0000

A few days ago I came across this awesome article about React rendering behaviour by Mark Erikson. It's pretty deep and covers things that you won't find in the official docs and I think even on Overreacted. I had problems with some rendering behaviours when building react-easy-flip and the article was very helpful.

For example, I didn't know that not everything re-renders when context value changes: under certain conditions (like when the child of the context provider is memoized with React.memo) only the providing component and the component that uses the context with useContext are re-rendered. Sometimes we really want a re-render even when props do not change, because we need to trigger some effect with useEffect or useLayoutEffect. If you notice that effect is not triggered for some reason, make sure the component is actually rendered by React.

Cheatsheeted version

However, it is a BIG article so I decided to create a visual aid to it: with pictures and live Codesandbox examples that you can play with.

I thought that making it into an independent page is better so here's the link when you can see it:

https://will-it-render.vercel.app/

How to write a Stack in Rust

Kirill Vasiltsov — Tue, 07 Jul 2020 04:20:05 +0000

In this series I show the simplest way to build some data structures in Rust.

What is a stack?

We'll start with a very commonly used data structure called Stack. Even you if you have never heard about stacks, you probably are already indirectly familiar with them: arrays/vectors are a more powerful version of stacks. Basically, a stack is a collection of items to which you can add items and from which you can remove items, but only in a certain order: last in - first out (LIFO). If you get on a very crowded train, you will be the first who needs to get off so that other people can too.

Unlike in arrays, you cannot directly access any item in a stack. You can only peek at the last added one. To further the analogy, if you need to interact with a friend on the train above, you cannot do so until every person in front of your friend gets off first.

Here's the more schematic version of a stack:

Adding items is usually called push and removing items is usually called pop.

Since these methods are already available to us in Rust via the Vec (vector) data structure, let us build a stack on top of it.

Note that both Vecs and arrays have push and pop but we use Vecs because they do not have a fixed size.

Create

First, let's define a struct and call it Stack:

struct Stack<T> {
  stack: Vec<T>,
}

We want our stack to be able to store different kinds of types so we make it generic by using T instead of any specific type like i32.

Now, to create a new stack we can do this:

let s = Stack { stack: Vec::new() };

But the more idiomatic way would be to define a new method for our stack, just like the one you used to create a new Vec.

impl<T> Stack<T> {
  fn new() -> Self {
    Stack { stack: Vec::new() }
  }
}

If you are not familiar with the impl (method) syntax you can read more about it here.

Push and pop

Implementing push and pop methods is very easy: we can simply reuse the methods defined on Vec:

fn pop(&mut self) -> Option<T> {
  self.stack.pop()
}

fn push(&mut self, item: T) {
  self.stack.push(item)
}

One caveat here is the return type of pop: you do not get the actual item, but an Option, because the vector may be empty, in which case you get a None.

Utilities

One good method to have is is_empty which tells us whether our stack is empty. Luckily, Vecs already have this method, so we just reuse it.

fn is_empty(&self) -> bool {
  self.stack.is_empty()
}

We also need a length method which purpose is obvious:

fn length(&self) -> usize {
   self.stack.len()
}

Another method that is associated with a stack is peek. It allows us to see the last added item.

fn peek(&self) -> Option<&T> {
   self.stack.get(self.length() - 1)
}

This one is a little bit more complicated. The reason is that we cannot just return the item itself - that would be equal to removing it. Instead we only return a reference (&) to it. And the reference itself is wrapped in an Option because the index passed to get may be out of bounds (in which case you get a None).

Now we have a functioning a stack! Here's the full code:

struct Stack<T> {
  stack: Vec<T>,
}

impl<T> Stack<T> {
  fn new() -> Self {
    Stack { stack: Vec::new() }
  }

  fn length(&self) -> usize {
    self.stack.len()
  }

  fn pop(&mut self) -> Option<T> {
    self.stack.pop()
  }

  fn push(&mut self, item: T) {
    self.stack.push(item)
  }

  fn is_empty(&self) -> bool {
    self.stack.is_empty()
  }

  fn peek(&self) -> Option<&T> {
    self.stack.get(self.length() - 1)
  }
}

And this is how you would you use it in code:

let mut stack: Stack<isize> = Stack::new();
stack.push(1);
let item = stack.pop();
assert_eq!(item.unwrap(), 1);

You can also see the full code on my github.

Next time

In the next part of this series I will show how to build another common and useful structure - Queue. In the meantime, you can get the latest updates if you follow me on Twitter.